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