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