fs/affs/bitmap.c

   1 /*
   2  *  linux/fs/affs/bitmap.c
   3  *
   4  *  (c) 1996 Hans-Joachim Widmaier
   5  *
   6  *  bitmap.c contains the code that handles all bitmap related stuff -
   7  *  block allocation, deallocation, calculation of free space.
   8  */
   9
  10 #include <linux/slab.h>
  11 #include "affs.h"
  12
  13 u32
  14 affs_count_free_blocks(struct super_block *sb)
  15 {
  16         struct affs_bm_info *bm;
  17         u32 free;
  18         int i;
  19
  20         pr_debug("AFFS: count_free_blocks()\n");
  21
  22         if (sb->s_flags & MS_RDONLY)
  23                 return 0;
  24
  25         mutex_lock(&AFFS_SB(sb)->s_bmlock);
  26
  27         bm = AFFS_SB(sb)->s_bitmap;
  28         free = 0;
  29         for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
  30                 free += bm->bm_free;
  31
  32         mutex_unlock(&AFFS_SB(sb)->s_bmlock);
  33
  34         return free;
  35 }
  36
  37 void
  38 affs_free_block(struct super_block *sb, u32 block)
  39 {
  40         struct affs_sb_info *sbi = AFFS_SB(sb);
  41         struct affs_bm_info *bm;
  42         struct buffer_head *bh;
  43         u32 blk, bmap, bit, mask, tmp;
  44         __be32 *data;
  45
  46         pr_debug("AFFS: free_block(%u)\n", block);
  47
  48         if (block > sbi->s_partition_size)
  49                 goto err_range;
  50
  51         blk     = block - sbi->s_reserved;
  52         bmap    = blk / sbi->s_bmap_bits;
  53         bit     = blk % sbi->s_bmap_bits;
  54         bm      = &sbi->s_bitmap[bmap];
  55
  56         mutex_lock(&sbi->s_bmlock);
  57
  58         bh = sbi->s_bmap_bh;
  59         if (sbi->s_last_bmap != bmap) {
  60                 affs_brelse(bh);
  61                 bh = affs_bread(sb, bm->bm_key);
  62                 if (!bh)
  63                         goto err_bh_read;
  64                 sbi->s_bmap_bh = bh;
  65                 sbi->s_last_bmap = bmap;
  66         }
  67
  68         mask = 1 << (bit & 31);
  69         data = (__be32 *)bh->b_data + bit / 32 + 1;
  70
  71         /* mark block free */
  72         tmp = be32_to_cpu(*data);
  73         if (tmp & mask)
  74                 goto err_free;
  75         *data = cpu_to_be32(tmp | mask);
  76
  77         /* fix checksum */
  78         tmp = be32_to_cpu(*(__be32 *)bh->b_data);
  79         *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
  80
  81         mark_buffer_dirty(bh);
  82         affs_mark_sb_dirty(sb);
  83         bm->bm_free++;
  84
  85         mutex_unlock(&sbi->s_bmlock);
  86         return;
  87
  88 err_free:
  89         affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
  90         mutex_unlock(&sbi->s_bmlock);
  91         return;
  92
  93 err_bh_read:
  94         affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
  95         sbi->s_bmap_bh = NULL;
  96         sbi->s_last_bmap = ~0;
  97         mutex_unlock(&sbi->s_bmlock);
  98         return;
  99
 100 err_range:
 101         affs_error(sb, "affs_free_block","Block %u outside partition", block);
 102         return;
 103 }
 104
 105 /*
 106  * Allocate a block in the given allocation zone.
 107  * Since we have to byte-swap the bitmap on little-endian
 108  * machines, this is rather expensive. Therefore we will
 109  * preallocate up to 16 blocks from the same word, if
 110  * possible. We are not doing preallocations in the
 111  * header zone, though.
 112  */
 113
 114 u32
 115 affs_alloc_block(struct inode *inode, u32 goal)
 116 {
 117         struct super_block *sb;
 118         struct affs_sb_info *sbi;
 119         struct affs_bm_info *bm;
 120         struct buffer_head *bh;
 121         __be32 *data, *enddata;
 122         u32 blk, bmap, bit, mask, mask2, tmp;
 123         int i;
 124
 125         sb = inode->i_sb;
 126         sbi = AFFS_SB(sb);
 127
 128         pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
 129
 130         if (AFFS_I(inode)->i_pa_cnt) {
 131                 pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
 132                 AFFS_I(inode)->i_pa_cnt--;
 133                 return ++AFFS_I(inode)->i_lastalloc;
 134         }
 135
 136         if (!goal || goal > sbi->s_partition_size) {
 137                 if (goal)
 138                         affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
 139                 //if (!AFFS_I(inode)->i_last_block)
 140                 //      affs_warning(sb, "affs_balloc", "no last alloc block");
 141                 goal = sbi->s_reserved;
 142         }
 143
 144         blk = goal - sbi->s_reserved;
 145         bmap = blk / sbi->s_bmap_bits;
 146         bm = &sbi->s_bitmap[bmap];
 147
 148         mutex_lock(&sbi->s_bmlock);
 149
 150         if (bm->bm_free)
 151                 goto find_bmap_bit;
 152
 153 find_bmap:
 154         /* search for the next bmap buffer with free bits */
 155         i = sbi->s_bmap_count;
 156         do {
 157                 if (--i < 0)
 158                         goto err_full;
 159                 bmap++;
 160                 bm++;
 161                 if (bmap < sbi->s_bmap_count)
 162                         continue;
 163                 /* restart search at zero */
 164                 bmap = 0;
 165                 bm = sbi->s_bitmap;
 166         } while (!bm->bm_free);
 167         blk = bmap * sbi->s_bmap_bits;
 168
 169 find_bmap_bit:
 170
 171         bh = sbi->s_bmap_bh;
 172         if (sbi->s_last_bmap != bmap) {
 173                 affs_brelse(bh);
 174                 bh = affs_bread(sb, bm->bm_key);
 175                 if (!bh)
 176                         goto err_bh_read;
 177                 sbi->s_bmap_bh = bh;
 178                 sbi->s_last_bmap = bmap;
 179         }
 180
 181         /* find an unused block in this bitmap block */
 182         bit = blk % sbi->s_bmap_bits;
 183         data = (__be32 *)bh->b_data + bit / 32 + 1;
 184         enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
 185         mask = ~0UL << (bit & 31);
 186         blk &= ~31UL;
 187
 188         tmp = be32_to_cpu(*data);
 189         if (tmp & mask)
 190                 goto find_bit;
 191
 192         /* scan the rest of the buffer */
 193         do {
 194                 blk += 32;
 195                 if (++data >= enddata)
 196                         /* didn't find something, can only happen
 197                          * if scan didn't start at 0, try next bmap
 198                          */
 199                         goto find_bmap;
 200         } while (!*data);
 201         tmp = be32_to_cpu(*data);
 202         mask = ~0;
 203
 204 find_bit:
 205         /* finally look for a free bit in the word */
 206         bit = ffs(tmp & mask) - 1;
 207         blk += bit + sbi->s_reserved;
 208         mask2 = mask = 1 << (bit & 31);
 209         AFFS_I(inode)->i_lastalloc = blk;
 210
 211         /* prealloc as much as possible within this word */
 212         while ((mask2 <<= 1)) {
 213                 if (!(tmp & mask2))
 214                         break;
 215                 AFFS_I(inode)->i_pa_cnt++;
 216                 mask |= mask2;
 217         }
 218         bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
 219
 220         *data = cpu_to_be32(tmp & ~mask);
 221
 222         /* fix checksum */
 223         tmp = be32_to_cpu(*(__be32 *)bh->b_data);
 224         *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
 225
 226         mark_buffer_dirty(bh);
 227         affs_mark_sb_dirty(sb);
 228
 229         mutex_unlock(&sbi->s_bmlock);
 230
 231         pr_debug("%d\n", blk);
 232         return blk;
 233
 234 err_bh_read:
 235         affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
 236         sbi->s_bmap_bh = NULL;
 237         sbi->s_last_bmap = ~0;
 238 err_full:
 239         mutex_unlock(&sbi->s_bmlock);
 240         pr_debug("failed\n");
 241         return 0;
 242 }
 243
 244 int affs_init_bitmap(struct super_block *sb, int *flags)
 245 {
 246         struct affs_bm_info *bm;
 247         struct buffer_head *bmap_bh = NULL, *bh = NULL;
 248         __be32 *bmap_blk;
 249         u32 size, blk, end, offset, mask;
 250         int i, res = 0;
 251         struct affs_sb_info *sbi = AFFS_SB(sb);
 252
 253         if (*flags & MS_RDONLY)
 254                 return 0;
 255
 256         if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
 257                 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
 258                         sb->s_id);
 259                 *flags |= MS_RDONLY;
 260                 return 0;
 261         }
 262
 263         sbi->s_last_bmap = ~0;
 264         sbi->s_bmap_bh = NULL;
 265         sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
 266         sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
 267                                  sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
 268         size = sbi->s_bmap_count * sizeof(*bm);
 269         bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
 270         if (!sbi->s_bitmap) {
 271                 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
 272                 return -ENOMEM;
 273         }
 274
 275         bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
 276         blk = sb->s_blocksize / 4 - 49;
 277         end = blk + 25;
 278
 279         for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
 280                 affs_brelse(bh);
 281
 282                 bm->bm_key = be32_to_cpu(bmap_blk[blk]);
 283                 bh = affs_bread(sb, bm->bm_key);
 284                 if (!bh) {
 285                         printk(KERN_ERR "AFFS: Cannot read bitmap\n");
 286                         res = -EIO;
 287                         goto out;
 288                 }
 289                 if (affs_checksum_block(sb, bh)) {
 290                         printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
 291                                bm->bm_key, sb->s_id);
 292                         *flags |= MS_RDONLY;
 293                         goto out;
 294                 }
 295                 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
 296                 bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
 297
 298                 /* Don't try read the extension if this is the last block,
 299                  * but we also need the right bm pointer below
 300                  */
 301                 if (++blk < end || i == 1)
 302                         continue;
 303                 if (bmap_bh)
 304                         affs_brelse(bmap_bh);
 305                 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
 306                 if (!bmap_bh) {
 307                         printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
 308                         res = -EIO;
 309                         goto out;
 310                 }
 311                 bmap_blk = (__be32 *)bmap_bh->b_data;
 312                 blk = 0;
 313                 end = sb->s_blocksize / 4 - 1;
 314         }
 315
 316         offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
 317         mask = ~(0xFFFFFFFFU << (offset & 31));
 318         pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
 319         offset = offset / 32 + 1;
 320
 321         if (mask) {
 322                 u32 old, new;
 323
 324                 /* Mark unused bits in the last word as allocated */
 325                 old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
 326                 new = old & mask;
 327                 //if (old != new) {
 328                         ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
 329                         /* fix checksum */
 330                         //new -= old;
 331                         //old = be32_to_cpu(*(__be32 *)bh->b_data);
 332                         //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
 333                         //mark_buffer_dirty(bh);
 334                 //}
 335                 /* correct offset for the bitmap count below */
 336                 //offset++;
 337         }
 338         while (++offset < sb->s_blocksize / 4)
 339                 ((__be32 *)bh->b_data)[offset] = 0;
 340         ((__be32 *)bh->b_data)[0] = 0;
 341         ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
 342         mark_buffer_dirty(bh);
 343
 344         /* recalculate bitmap count for last block */
 345         bm--;
 346         bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
 347
 348 out:
 349         affs_brelse(bh);
 350         affs_brelse(bmap_bh);
 351         return res;
 352 }
 353
 354 void affs_free_bitmap(struct super_block *sb)
 355 {
 356         struct affs_sb_info *sbi = AFFS_SB(sb);
 357
 358         if (!sbi->s_bitmap)
 359                 return;
 360
 361         affs_brelse(sbi->s_bmap_bh);
 362         sbi->s_bmap_bh = NULL;
 363         sbi->s_last_bmap = ~0;
 364         kfree(sbi->s_bitmap);
 365         sbi->s_bitmap = NULL;
 366 }