fs/affs/bitmap.c

/* */
This source file includes following definitions.
affs_count_free_bits
affs_count_free_blocks
affs_free_block
affs_balloc
affs_find_new_zone
affs_new_header
affs_new_data
affs_make_zones
   1 /*
   2  *  linux/fs/affs/bitmap.c
   3  *
   4  *  (c) 1996 Hans-Joachim Widmaier
   5  */
   6 
   7 /* bitmap.c contains the code that handles the inode and block bitmaps */
   8 
   9 #include <linux/sched.h>
  10 #include <linux/affs_fs.h>
  11 #include <linux/stat.h>
  12 #include <linux/kernel.h>
  13 #include <linux/string.h>
  14 #include <linux/amigaffs.h>
  15 #include <linux/locks.h>
  16 
  17 #include <asm/bitops.h>
  18 
  19 static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
  20 
  21 int
  22 affs_count_free_bits(int blocksize, const UBYTE *data)
     /*  */
  23 {
  24   int    free;
  25   int    i;
  26 
  27   free = 0;
  28   for (i = 0; i < blocksize; i++) {
  29     free  += nibblemap[data[i] & 0xF] + nibblemap[(data[i]>>4) & 0xF];
  30   }
  31 
  32   return free;
  33 }
  34 
  35 int
  36 affs_count_free_blocks(struct super_block *s)
     /*  */
  37 {
  38         int      free;
  39         int      i;
  40 
  41         pr_debug("AFFS: count_free_blocks()\n");
  42 
  43         free = 0;
  44         if (s->u.affs_sb.s_flags & SF_BM_VALID) {
  45                 for (i = 0; i < s->u.affs_sb.s_bm_count; i++) {
  46                         free += s->u.affs_sb.s_bitmap[i].bm_free;
  47                 }
  48         }
  49         return free;
  50 }
  51 
  52 void
  53 affs_free_block(struct super_block *sb, LONG block)
     /*  */
  54 {
  55         int                      bmap;
  56         int                      bit;
  57         ULONG                    blk;
  58         struct affs_bm_info     *bm;
  59 
  60         pr_debug("AFFS: free_block(%d)\n",block);
  61 
  62         blk    = block - sb->u.affs_sb.s_reserved;
  63         bmap   = blk / (sb->s_blocksize * 8 - 32);
  64         bit    = blk % (sb->s_blocksize * 8 - 32);
  65         bm     = &sb->u.affs_sb.s_bitmap[bmap];
  66         if (bmap >= sb->u.affs_sb.s_bm_count || bit >= bm->bm_size) {
  67                 printk("AFFS: free_block(): block %d outside partition.\n",block);
  68                 return;
  69         }
  70         blk  = 0;
  71         set_bit(bit & 31,&blk);
  72 
  73         lock_super(sb);
  74         if (set_bit(bit ^ BO_EXBITS,bm->bm_bh->b_data + 4))
  75                 printk("AFFS: free_block(): block %d is already free.\n",block);
  76         else {
  77                 bm->bm_free++;
  78                 ((ULONG *)bm->bm_bh->b_data)[0] = ntohl(htonl(((ULONG *)bm->bm_bh->b_data)[0]) - blk);
  79                 mark_buffer_dirty(bm->bm_bh,1);
  80                 sb->s_dirt = 1;
  81         }
  82         unlock_super(sb);
  83 }
  84 
  85 static ULONG
  86 affs_balloc(struct inode *inode, int zone_no)
     /*  */
  87 {
  88         ULONG                    w;
  89         ULONG                   *bm;
  90         int                      fb;
  91         int                      i;
  92         int                      fwb;
  93         ULONG                    block;
  94         struct affs_zone        *zone;
  95         struct super_block      *sb;
  96 
  97         sb   = inode->i_sb;
  98         zone = &sb->u.affs_sb.s_zones[zone_no];
  99 
 100         if (!zone || !zone->z_bm || !zone->z_bm->bm_bh)
 101                 return 0;
 102         
 103         pr_debug("AFFS: balloc(inode=%lu,zone=%d)\n",inode->i_ino,zone_no);
 104 
 105         bm = (ULONG *)zone->z_bm->bm_bh->b_data;
 106 repeat:
 107         fb = (zone->z_bm->bm_size + 31) >> 5;
 108         for (i = zone->z_start; i <= fb; i++) {
 109                 if (bm[i])
 110                         goto found;
 111         }
 112         return 0;
 113 
 114 found:
 115         fwb = zone->z_bm->bm_firstblk + (i - 1) * 32;
 116         lock_super(sb);
 117         zone->z_start = i;
 118         w   = htonl(bm[i]);
 119         fb  = find_first_one_bit(&w,32);
 120         if (fb > 31 || !clear_bit(fb ^ BO_EXBITS,&bm[i])) {
 121                 unlock_super(sb);
 122                 printk("AFFS: balloc(): empty block disappeared somehow\n");
 123                 goto repeat;
 124         }
 125         block = fwb + fb;
 126         zone->z_bm->bm_free--;
 127 
 128         /* prealloc as much as possible within this word, but not for headers */
 129 
 130         if (zone_no) {
 131                 while (inode->u.affs_i.i_pa_cnt < MAX_PREALLOC && ++fb < 32) {
 132                         fb = find_next_one_bit(&w,32,fb);
 133                         if (fb > 31)
 134                                 break;
 135                         if (!clear_bit(fb ^ BO_EXBITS,&bm[i])) {
 136                                 printk("AFFS: balloc(): empty block disappeared\n");
 137                                 break;
 138                         }
 139                         inode->u.affs_i.i_data[inode->u.affs_i.i_pa_last++] = fwb + fb;
 140                         inode->u.affs_i.i_pa_last &= MAX_PREALLOC - 1;
 141                         inode->u.affs_i.i_pa_cnt++;
 142                         zone->z_bm->bm_free--;
 143                 }
 144         }
 145         w    -= htonl(bm[i]);
 146         bm[0] = ntohl(htonl(bm[0]) + w);
 147         unlock_super(sb);
 148         mark_buffer_dirty(zone->z_bm->bm_bh,1);
 149 
 150         return block;
 151 }
 152 
 153 static void
 154 affs_find_new_zone(struct super_block *sb,struct affs_zone *z, int minfree, int start)
     /*  */
 155 {
 156         struct affs_bm_info     *bm;
 157         int                      offs;
 158         int                      zone;
 159         int                      free;
 160         int                      len;
 161 
 162         pr_debug("AFFS: find_new_zone()\n");
 163 
 164         lock_super(sb);
 165 
 166         zone    = start;
 167         z->z_bm = NULL;
 168         while (1) {
 169                 if (zone >= sb->u.affs_sb.s_num_zones) {
 170                         zone = 0;
 171                         continue;
 172                 }
 173 
 174                 if (!set_bit(zone,sb->u.affs_sb.s_zonemap)) {
 175                         bm   = &sb->u.affs_sb.s_bitmap[zone >> (sb->s_blocksize_bits - 8)];
 176                         offs = zone * 256 & (sb->s_blocksize - 1);
 177                         len  = bm->bm_size / 8 - offs;
 178                         if (len > 256)
 179                                 len = 256;
 180                         offs += 4;
 181                         free  = affs_count_free_bits(len,(char *)bm->bm_bh->b_data + offs);
 182                         if (free && (100 * free) / (len * 8) > minfree) {
 183                                 z->z_bm       = bm;
 184                                 z->z_start    = offs / 4;
 185                                 z->z_ino      = 0;
 186                                 z->z_zone_no  = zone;
 187                                 pr_debug("  ++ found zone (%d) in bh %d at offset %d with %d free blocks\n",
 188                                          zone,(zone >> (sb->s_blocksize_bits - 8)),offs,free);
 189                                 break;
 190                         }
 191                         clear_bit(zone,sb->u.affs_sb.s_zonemap);
 192                 }
 193 
 194                 /* Skip to next possible zone */
 195 
 196                 pr_debug("  ++ Skipping to next zone\n");
 197                 if (++zone == start)
 198                         break;
 199         }
 200         unlock_super(sb);
 201         return;
 202 }
 203 
 204 LONG
 205 affs_new_header(struct inode *inode)
     /*  */
 206 {
 207         struct affs_zone        *zone;
 208         LONG                     block;
 209         struct super_block      *sb;
 210         struct buffer_head      *bh;
 211 
 212         sb   = inode->i_sb;
 213         zone = &sb->u.affs_sb.s_zones[0];
 214 
 215         /* We try up to 3 times to find a free block:
 216          * If there is no more room in the current header zone,
 217          * we try to get a new one and allocate the block there.
 218          * If there is no zone with at least AFFS_HDR_MIN_FREE
 219          * percent of free blocks, we try to find a zone with
 220          * at least one free block.
 221          */
 222 
 223         if (!(block = affs_balloc(inode,0))) {
 224                 clear_bit(zone->z_zone_no,sb->u.affs_sb.s_zonemap);
 225                 affs_find_new_zone(sb,zone,AFFS_HDR_MIN_FREE,(sb->u.affs_sb.s_num_zones + 1) / 2);
 226                 if (!(block = affs_balloc(inode,0))) {
 227                         clear_bit(zone->z_zone_no,sb->u.affs_sb.s_zonemap);
 228                         affs_find_new_zone(sb,zone,0,(sb->u.affs_sb.s_num_zones + 1) / 2);
 229                         if (!(block = affs_balloc(inode,0)))
 230                                 return 0;
 231                 }
 232         }
 233         if (!(bh = getblk(inode->i_dev,block,sb->s_blocksize))) {
 234                 printk("AFFS: balloc(): cannot read block %d\n",block);
 235                 return 0;
 236         }
 237         memset(bh->b_data,0,sb->s_blocksize);
 238         mark_buffer_uptodate(bh,1);
 239         mark_buffer_dirty(bh,1);
 240         affs_brelse(bh);
 241 
 242         return block;
 243 }
 244 
 245 LONG
 246 affs_new_data(struct inode *inode)
     /*  */
 247 {
 248         int                      empty, old;
 249         unsigned long            oldest;
 250         struct affs_zone        *zone;
 251         struct super_block      *sb;
 252         struct buffer_head      *bh;
 253         int                      i = 0;
 254         LONG                     block;
 255 
 256         pr_debug("AFFS: new_data(ino=%lu)\n",inode->i_ino);
 257 
 258         sb = inode->i_sb;
 259         lock_super(sb);
 260         if (inode->u.affs_i.i_pa_cnt) {
 261                 inode->u.affs_i.i_pa_cnt--;
 262                 unlock_super(sb);
 263                 block = inode->u.affs_i.i_data[inode->u.affs_i.i_pa_next++];
 264                 inode->u.affs_i.i_pa_next &= MAX_PREALLOC - 1;
 265                 goto init_block;
 266         }
 267         unlock_super(sb);
 268 repeat:
 269         oldest = jiffies;
 270         old    = 0;
 271         empty  = 0;
 272         zone   = &sb->u.affs_sb.s_zones[inode->u.affs_i.i_zone];
 273         if (zone->z_ino == inode->i_ino) {
 274                 i = inode->u.affs_i.i_zone;
 275                 goto found;
 276         }
 277         for (i = 1; i < MAX_ZONES; i++) {
 278                 zone = &sb->u.affs_sb.s_zones[i];
 279                 if (!empty && zone->z_bm && !zone->z_ino)
 280                         empty = i;
 281                 if (zone->z_bm && zone->z_lru_time < oldest) {
 282                         old    = i;
 283                         oldest = zone->z_lru_time;
 284                 }
 285         }
 286         if (empty)
 287                 i = empty;
 288         else if (old)
 289                 i = old;
 290         else
 291                 return affs_new_header(inode);
 292 
 293         inode->u.affs_i.i_zone = i;
 294         zone->z_ino            = inode->i_ino;
 295 
 296 found:
 297         zone = &sb->u.affs_sb.s_zones[i];
 298         if (!(block = affs_balloc(inode,i))) {                          /* Zone is full */
 299                 clear_bit(zone->z_zone_no,sb->u.affs_sb.s_zonemap);
 300                 affs_find_new_zone(sb,zone,AFFS_DATA_MIN_FREE,sb->u.affs_sb.s_nextzone);
 301                 sb->u.affs_sb.s_nextzone = zone->z_zone_no + 1;
 302                 goto repeat;
 303         }
 304 
 305 init_block:
 306         if (!(bh = getblk(inode->i_dev,block,sb->s_blocksize))) {
 307                 printk("AFFS: balloc(): cannot read block %u\n",block);
 308                 return 0;
 309         }
 310         memset(bh->b_data,0,sb->s_blocksize);
 311         mark_buffer_uptodate(bh,1);
 312         mark_buffer_dirty(bh,1);
 313         affs_brelse(bh);
 314 
 315         return block;
 316 }
 317 
 318 void
 319 affs_make_zones(struct super_block *sb)
     /*  */
 320 {
 321         int      i, j;
 322 
 323         pr_debug("AFFS: make_zones(): num_zones=%d\n",sb->u.affs_sb.s_num_zones);
 324 
 325         j = (sb->u.affs_sb.s_num_zones + 1) / 2;
 326 
 327         affs_find_new_zone(sb,&sb->u.affs_sb.s_zones[0],AFFS_HDR_MIN_FREE,j);
 328         for (i = 1; i < MAX_ZONES; i++) {
 329                 affs_find_new_zone(sb,&sb->u.affs_sb.s_zones[i],AFFS_DATA_MIN_FREE,j);
 330                 j = sb->u.affs_sb.s_zones[i].z_zone_no + 1;
 331         }
 332 }
/* */
root/fs/affs/bitmap.c

DEFINITIONS
