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