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