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 #define DEBUG 0
  11 #include <linux/sched.h>
  12 #include <linux/affs_fs.h>
  13 #include <linux/stat.h>
  14 #include <linux/kernel.h>
  15 #include <linux/string.h>
  16 #include <linux/locks.h>
  17 #include <linux/amigaffs.h>
  18
  19 #include <asm/bitops.h>
  20
  21 /* This is, of course, shamelessly stolen from fs/minix */
  22
  23 static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
  24
  25 int
  26 affs_count_free_bits(int blocksize, const char *data)
  27 {
  28   int    free;
  29   int    i;
  30
  31   free = 0;
  32   for (i = 0; i < blocksize; i++) {
  33     free  += nibblemap[data[i] & 0xF] + nibblemap[(data[i]>>4) & 0xF];
  34   }
  35
  36   return free;
  37 }
  38
  39 int
  40 affs_count_free_blocks(struct super_block *s)
  41 {
  42         int      free;
  43         int      i;
  44
  45         pr_debug("AFFS: count_free_blocks()\n");
  46
  47         free = 0;
  48         if (s->u.affs_sb.s_flags & SF_BM_VALID) {
  49                 for (i = 0; i < s->u.affs_sb.s_num_az; i++) {
  50                         free += s->u.affs_sb.s_alloc[i].az_free;
  51                 }
  52         }
  53         return free;
  54 }
  55
  56 void
  57 affs_free_block(struct super_block *sb, s32 block)
  58 {
  59         int                      bmap;
  60         int                      bit;
  61         int                      blk;
  62         int                      zone_no;
  63         struct affs_bm_info     *bm;
  64
  65         pr_debug("AFFS: free_block(%d)\n",block);
  66
  67         blk     = block - sb->u.affs_sb.s_reserved;
  68         bmap    = blk / (sb->s_blocksize * 8 - 32);
  69         bit     = blk % (sb->s_blocksize * 8 - 32);
  70         zone_no = (bmap << (sb->s_blocksize_bits - 7)) + bit / 1024;
  71         bm      = &sb->u.affs_sb.s_bitmap[bmap];
  72         if (bmap >= sb->u.affs_sb.s_bm_count) {
  73                 affs_error(sb,"affs_free_block","Block %d outside partition",block);
  74                 return;
  75         }
  76         blk = 0;
  77         set_bit(bit & 31,&blk);
  78
  79         lock_super(sb);
  80         bm->bm_count++;
  81         if (!bm->bm_bh) {
  82                 bm->bm_bh = affs_bread(sb->s_dev,bm->bm_key,sb->s_blocksize);
  83                 if (!bm->bm_bh) {
  84                         bm->bm_count--;
  85                         unlock_super(sb);
  86                         affs_error(sb,"affs_free_block","Cannot read bitmap block %d",bm->bm_key);
  87                         return;
  88                 }
  89         }
  90         if (test_and_set_bit(bit ^ BO_EXBITS,bm->bm_bh->b_data + 4))
  91                 affs_warning(sb,"affs_free_block","Trying to free block %d which is already free",
  92                                 block);
  93         else {
  94                 sb->u.affs_sb.s_alloc[zone_no].az_free++;
  95                 ((u32 *)bm->bm_bh->b_data)[0] = cpu_to_be32(be32_to_cpu(((u32 *)bm->bm_bh->b_data)[0]) - blk);
  96                 mark_buffer_dirty(bm->bm_bh);
  97                 sb->s_dirt = 1;
  98         }
  99         if (--bm->bm_count == 0) {
 100                 affs_brelse(bm->bm_bh);
 101                 bm->bm_bh = NULL;
 102         }
 103         unlock_super(sb);
 104 }
 105
 106 /*
 107  * Allocate a block in the given allocation zone.
 108  * Since we have to byte-swap the bitmap on little-endian
 109  * machines, this is rather expensive. Therefor we will
 110  * preallocate up to 16 blocks from the same word, if
 111  * possible. We are not doing preallocations in the
 112  * header zone, though.
 113  */
 114
 115 static s32
 116 affs_balloc(struct inode *inode, int zone_no)
 117 {
 118         u32                      w;
 119         u32                     *bm;
 120         int                      fb;
 121         int                      i;
 122         int                      fwb;
 123         s32                      block;
 124         struct affs_zone        *zone;
 125         struct affs_alloc_zone  *az;
 126         struct super_block      *sb;
 127
 128         sb   = inode->i_sb;
 129         zone = &sb->u.affs_sb.s_zones[zone_no];
 130
 131         if (!zone->z_bm || !zone->z_bm->bm_bh)
 132                 return 0;
 133
 134         pr_debug("AFFS: balloc(inode=%lu,zone=%d)\n",inode->i_ino,zone_no);
 135
 136         az = &sb->u.affs_sb.s_alloc[zone->z_az_no];
 137         bm = (u32 *)zone->z_bm->bm_bh->b_data;
 138 repeat:
 139         for (i = zone->z_start; i < zone->z_end; i++) {
 140                 if (bm[i])
 141                         goto found;
 142         }
 143         return 0;
 144
 145 found:
 146         fwb = zone->z_bm->bm_firstblk + (i - 1) * 32;
 147         lock_super(sb);
 148         zone->z_start = i;
 149         w   = ~be32_to_cpu(bm[i]);
 150         fb  = find_first_zero_bit(&w,32);
 151         if (fb > 31 || !test_and_clear_bit(fb ^ BO_EXBITS,&bm[i])) {
 152                 unlock_super(sb);
 153                 affs_warning(sb,"balloc","Empty block disappeared somehow");
 154                 goto repeat;
 155         }
 156         block = fwb + fb;
 157         az->az_free--;
 158
 159         /* prealloc as much as possible within this word, but not in header zone */
 160
 161         if (zone_no) {
 162                 while (inode->u.affs_i.i_pa_cnt < AFFS_MAX_PREALLOC && ++fb < 32) {
 163                         fb = find_next_zero_bit(&w,32,fb);
 164                         if (fb > 31)
 165                                 break;
 166                         if (!test_and_clear_bit(fb ^ BO_EXBITS,&bm[i])) {
 167                                 affs_warning(sb,"balloc","Empty block disappeared somehow");
 168                                 break;
 169                         }
 170                         inode->u.affs_i.i_data[inode->u.affs_i.i_pa_last++] = fwb + fb;
 171                         inode->u.affs_i.i_pa_last &= AFFS_MAX_PREALLOC - 1;
 172                         inode->u.affs_i.i_pa_cnt++;
 173                         az->az_free--;
 174                 }
 175         }
 176         w     = ~w - be32_to_cpu(bm[i]);
 177         bm[0] = cpu_to_be32(be32_to_cpu(bm[0]) + w);
 178         unlock_super(sb);
 179         mark_buffer_dirty(zone->z_bm->bm_bh);
 180         sb->s_dirt = 1;
 181         zone->z_lru_time = jiffies;
 182
 183         return block;
 184 }
 185
 186 /* Find a new allocation zone, starting at zone_no. */
 187
 188 static int
 189 affs_find_new_zone(struct super_block *sb, int zone_no)
 190 {
 191         struct affs_bm_info     *bm;
 192         struct affs_zone        *zone;
 193         struct affs_alloc_zone  *az;
 194         int                      bestfree;
 195         int                      bestno;
 196         int                      bestused;
 197         int                      lusers;
 198         int                      i;
 199         int                      min;
 200
 201         pr_debug("AFFS: find_new_zone(zone_no=%d)\n",zone_no);
 202
 203         bestfree = 0;
 204         bestused = -1;
 205         bestno   = -1;
 206         lusers   = MAX_ZONES;
 207         min      = zone_no ? AFFS_DATA_MIN_FREE : AFFS_HDR_MIN_FREE;
 208         lock_super(sb);
 209         zone = &sb->u.affs_sb.s_zones[zone_no];
 210         i    = zone->z_az_no;
 211         az   = &sb->u.affs_sb.s_alloc[i];
 212         if (zone->z_bm && zone->z_bm->bm_count) {
 213                 if (--zone->z_bm->bm_count == 0) {
 214                         affs_brelse(zone->z_bm->bm_bh);
 215                         zone->z_bm->bm_bh = NULL;
 216                 }
 217                 if (az->az_count)
 218                         az->az_count--;
 219                 else
 220                         affs_error(sb,"find_new_zone","az_count=0, but bm used");
 221
 222         }
 223         while (1) {
 224                 az = &sb->u.affs_sb.s_alloc[i];
 225                 if (!az->az_count) {
 226                         if (az->az_free > min) {
 227                                 break;
 228                         }
 229                         if (az->az_free > bestfree) {
 230                                 bestfree = az->az_free;
 231                                 bestno   = i;
 232                         }
 233                 } else if (az->az_free && az->az_count < lusers) {
 234                         lusers   = az->az_count;
 235                         bestused = i;
 236                 }
 237                 if (++i >= sb->u.affs_sb.s_num_az)
 238                         i = 0;
 239                 if (i == zone->z_az_no) {               /* Seen all */
 240                         if (bestno >= 0) {
 241                                 i = bestno;
 242                         } else {
 243                                 i = bestused;
 244                         }
 245                         break;
 246                 }
 247         }
 248         if (i < 0) {
 249                 /* Didn't find a single free block anywhere. */
 250                 unlock_super(sb);
 251                 return 0;
 252         }
 253         az = &sb->u.affs_sb.s_alloc[i];
 254         az->az_count++;
 255         bm = &sb->u.affs_sb.s_bitmap[i >> (sb->s_blocksize_bits - 7)];
 256         bm->bm_count++;
 257         if (!bm->bm_bh)
 258                 bm->bm_bh = affs_bread(sb->s_dev,bm->bm_key,sb->s_blocksize);
 259         if (!bm->bm_bh) {
 260                 bm->bm_count--;
 261                 az->az_count--;
 262                 unlock_super(sb);
 263                 affs_error(sb,"find_new_zone","Cannot read bitmap");
 264                 return 0;
 265         }
 266         zone->z_bm    = bm;
 267         zone->z_start = (i & ((sb->s_blocksize / 128) - 1)) * 32 + 1;
 268         zone->z_end   = zone->z_start + az->az_size;
 269         zone->z_az_no = i;
 270         zone->z_lru_time = jiffies;
 271         pr_debug("AFFS: found zone (%d) in bm %d at lw offset %d with %d free blocks\n",
 272                  i,(i >> (sb->s_blocksize_bits - 7)),zone->z_start,az->az_free);
 273         unlock_super(sb);
 274         return az->az_free;
 275 }
 276
 277 /* Allocate a new header block. */
 278
 279 s32
 280 affs_new_header(struct inode *inode)
 281 {
 282         s32                      block;
 283
 284         pr_debug("AFFS: new_header(ino=%lu)\n",inode->i_ino);
 285
 286         if (!(block = affs_balloc(inode,0))) {
 287                 while (affs_find_new_zone(inode->i_sb,0)) {
 288                         if ((block = affs_balloc(inode,0)))
 289                                 return block;
 290                         schedule();
 291                 }
 292                 return 0;
 293         }
 294         return block;
 295 }
 296
 297 /* Allocate a new data block. */
 298
 299 s32
 300 affs_new_data(struct inode *inode)
 301 {
 302         int                      empty, old;
 303         unsigned long            oldest;
 304         struct affs_zone        *zone;
 305         struct super_block      *sb;
 306         int                      i = 0;
 307         s32                      block;
 308
 309         pr_debug("AFFS: new_data(ino=%lu)\n",inode->i_ino);
 310
 311         sb = inode->i_sb;
 312         lock_super(sb);
 313         if (inode->u.affs_i.i_pa_cnt) {
 314                 inode->u.affs_i.i_pa_cnt--;
 315                 unlock_super(sb);
 316                 block = inode->u.affs_i.i_data[inode->u.affs_i.i_pa_next++];
 317                 inode->u.affs_i.i_pa_next &= AFFS_MAX_PREALLOC - 1;
 318                 return block;
 319         }
 320         unlock_super(sb);
 321         oldest = jiffies;
 322         old    = 0;
 323         empty  = 0;
 324         zone   = &sb->u.affs_sb.s_zones[inode->u.affs_i.i_zone];
 325         if (zone->z_ino == inode->i_ino) {
 326                 i = inode->u.affs_i.i_zone;
 327                 goto found;
 328         }
 329         for (i = 1; i < MAX_ZONES; i++) {
 330                 zone = &sb->u.affs_sb.s_zones[i];
 331                 if (!empty && zone->z_bm && !zone->z_ino)
 332                         empty = i;
 333                 if (zone->z_bm && zone->z_lru_time < oldest) {
 334                         old    = i;
 335                         oldest = zone->z_lru_time;
 336                 }
 337         }
 338         if (empty)
 339                 i = empty;
 340         else if (old)
 341                 i = old;
 342         else {
 343                 inode->u.affs_i.i_zone = 0;
 344                 return affs_new_header(inode);
 345         }
 346
 347         inode->u.affs_i.i_zone = i;
 348         zone->z_ino            = inode->i_ino;
 349
 350 found:
 351         zone = &sb->u.affs_sb.s_zones[i];
 352         if (!(block = affs_balloc(inode,i))) {          /* No data zones left */
 353                 while (affs_find_new_zone(sb,i)) {
 354                         if ((block = affs_balloc(inode,i)))
 355                                 return block;
 356                         schedule();
 357                 }
 358                 inode->u.affs_i.i_zone = 0;
 359                 zone->z_ino            = -1;
 360                 return 0;
 361         }
 362         return block;
 363 }
 364
 365 void
 366 affs_make_zones(struct super_block *sb)
 367 {
 368         int      i, mid;
 369
 370         pr_debug("AFFS: make_zones(): num_zones=%d\n",sb->u.affs_sb.s_num_az);
 371
 372         mid = (sb->u.affs_sb.s_num_az + 1) / 2;
 373         for (i = 0; i < MAX_ZONES; i++) {
 374                 sb->u.affs_sb.s_zones[i].z_az_no = mid;
 375                 affs_find_new_zone(sb,i);
 376         }
 377 }