fs/xiafs/bitmap.c

/* */
This source file includes following definitions.
find_first_zero
clear_buf
que
get__map_zone
get_free__bit
xiafs_free_zone
xiafs_new_zone
xiafs_free_inode
xiafs_new_inode
count_zone
xiafs_count_free_inodes
xiafs_count_free_zones
   1 /*
   2  *  linux/fs/xiafs/bitmap.c
   3  *
   4  *  Copyright (C) Q. Frank Xia, 1993.
   5  *  
   6  *  Based on Linus' minix/bitmap.c
   7  *  Copyright (C) Linus Torvalds, 1991, 1992.
   8  *  
   9  *  This software may be redistributed per Linux Copyright.
  10  */
  11 
  12 /* bitmap.c contains the code that handles the inode and block bitmaps */
  13 
  14 #include <linux/sched.h>
  15 #include <linux/locks.h>
  16 #include <linux/xia_fs.h>
  17 #include <linux/stat.h>
  18 #include <linux/kernel.h>
  19 #include <linux/string.h>
  20 
  21 #include <asm/bitops.h>
  22 
  23 #include "xiafs_mac.h"
  24 
  25 
  26 char internal_error_message[]="XIA-FS: internal error %s %d\n"; 
  27 
  28 static int find_first_zero(struct buffer_head *bh, int start_bit, int end_bit) 
     /*  */
  29 {
  30     /* This routine searches first 0 bit from (start_bit) to (end_bit-1).
  31      * If found the bit is set to 1 and the bit # is returned, otherwise,
  32      * -1 is returned. Race condition is avoid by using "btsl" and 
  33      * "goto repeat".  ---Frank.
  34      */
  35 
  36     int end, i, j, tmp;
  37     u_long *bmap;
  38 
  39     bmap=(u_long *)bh->b_data;
  40     end = end_bit >> 5;
  41 
  42 repeat:
  43     i=start_bit >> 5;
  44     if ( (tmp=(~bmap[i]) & (0xffffffff << (start_bit & 31))) )        
  45         goto zone_found;
  46     while (++i < end)
  47         if (~bmap[i]) {
  48             tmp=~bmap[i];
  49             goto zone_found;
  50         }
  51     if ( !(tmp=~bmap[i] & ((1 << (end_bit & 31)) -1)) )
  52         return -1;
  53 zone_found:    
  54     for (j=0; j < 32; j++)
  55         if (tmp & (1 << j))
  56             break;
  57     if (set_bit(j,bmap+i)) {
  58         start_bit=j + (i << 5) + 1;
  59         goto repeat;
  60     }
  61     mark_buffer_dirty(bh, 1);
  62     return j + (i << 5);
  63 }
  64 
  65 static void clear_buf(struct buffer_head * bh) 
     /*  */
  66 {
  67     register int i;
  68     register long * lp;
  69 
  70     lp=(long *)bh->b_data;
  71     for (i= bh->b_size >> 2; i-- > 0; )
  72         *lp++=0;
  73 }
  74 
  75 static void que(struct buffer_head * bmap[], int bznr[], int pos)
     /*  */
  76 {
  77     struct buffer_head * tbh;
  78     int tmp;
  79     int i;
  80     
  81     tbh=bmap[pos];
  82     tmp=bznr[pos];
  83     for (i=pos; i > 0; i--) {
  84         bmap[i]=bmap[i-1];
  85         bznr[i]=bznr[i-1];
  86     }
  87     bmap[0]=tbh;
  88     bznr[0]=tmp;
  89 }
  90 
  91 #define get_imap_zone(sb, bit_nr, not_que) \
  92         get__map_zone((sb), (sb)->u.xiafs_sb.s_imap_buf, \
  93                       (sb)->u.xiafs_sb.s_imap_iznr, \
  94                       (sb)->u.xiafs_sb.s_imap_cached, 1, \
  95                       (sb)->u.xiafs_sb.s_imap_zones, _XIAFS_IMAP_SLOTS, \
  96                       bit_nr, not_que)
  97 
  98 #define get_zmap_zone(sb, bit_nr, not_que) \
  99         get__map_zone((sb), (sb)->u.xiafs_sb.s_zmap_buf, \
 100                       (sb)->u.xiafs_sb.s_zmap_zznr, \
 101                       (sb)->u.xiafs_sb.s_zmap_cached, \
 102                       1+(sb)->u.xiafs_sb.s_imap_zones, \
 103                       (sb)->u.xiafs_sb.s_zmap_zones, _XIAFS_ZMAP_SLOTS, \
 104                       bit_nr, not_que)
 105 
 106 static struct buffer_head * 
 107 get__map_zone(struct super_block *sb, struct buffer_head * bmap_buf[],
     /*  */
 108           int bznr[], u_char cache, int first_zone, 
 109           int bmap_zones, int slots, u_long bit_nr, int * not_que)
 110 {
 111     struct buffer_head * tmp_bh;
 112     int z_nr, i;
 113 
 114     z_nr = bit_nr >> XIAFS_BITS_PER_Z_BITS(sb);
 115     if (z_nr >= bmap_zones) {
 116         printk("XIA-FS: bad inode/zone number (%s %d)\n", WHERE_ERR);
 117         return NULL;
 118     }
 119     if (!cache)
 120         return bmap_buf[z_nr];
 121     lock_super(sb);
 122     for (i=0; i < slots; i++) 
 123         if (bznr[i]==z_nr)
 124             break;
 125     if (i < slots) {                    /* cache hit */
 126         if (not_que) {
 127             *not_que=i;
 128             return bmap_buf[i];
 129         } else {
 130             que(bmap_buf, bznr, i);
 131             return bmap_buf[0];
 132         }
 133     }
 134     tmp_bh=bread(sb->s_dev, z_nr+first_zone, XIAFS_ZSIZE(sb)); /* cache not hit */
 135     if (!tmp_bh) {
 136         printk("XIA-FS: read bitmap failed (%s %d)\n", WHERE_ERR);
 137         unlock_super(sb);
 138         return NULL;
 139     }
 140     brelse(bmap_buf[slots-1]);
 141     bmap_buf[slots-1]=tmp_bh;
 142     bznr[slots-1]=z_nr;
 143     if (not_que)
 144         *not_que=slots-1;
 145     else
 146         que(bmap_buf, bznr, slots-1);
 147     return tmp_bh;
 148 }
 149 
 150 #define xiafs_unlock_super(sb, cache)   if (cache) unlock_super(sb);
 151 
 152 #define get_free_ibit(sb, prev_bit) \
 153         get_free__bit(sb, sb->u.xiafs_sb.s_imap_buf, \
 154                       sb->u.xiafs_sb.s_imap_iznr, \
 155                       sb->u.xiafs_sb.s_imap_cached, \
 156                       1, sb->u.xiafs_sb.s_imap_zones, \
 157                       _XIAFS_IMAP_SLOTS, prev_bit);
 158 
 159 #define get_free_zbit(sb, prev_bit) \
 160         get_free__bit(sb, sb->u.xiafs_sb.s_zmap_buf, \
 161                       sb->u.xiafs_sb.s_zmap_zznr, \
 162                       sb->u.xiafs_sb.s_zmap_cached, \
 163                       1 + sb->u.xiafs_sb.s_imap_zones, \
 164                       sb->u.xiafs_sb.s_zmap_zones, \
 165                       _XIAFS_ZMAP_SLOTS, prev_bit);
 166 
 167 static u_long 
 168 get_free__bit(struct super_block *sb, struct buffer_head * bmap_buf[],
     /*  */
 169               int bznr[], u_char cache, int first_zone, int bmap_zones, 
 170               int slots, u_long prev_bit)
 171 {
 172     struct buffer_head * bh;
 173     int not_done=0;
 174     u_long pos, start_bit, end_bit, total_bits;
 175     int z_nr, tmp;
 176  
 177     total_bits=bmap_zones << XIAFS_BITS_PER_Z_BITS(sb); 
 178     if (prev_bit >= total_bits)
 179         prev_bit=0;
 180     pos=prev_bit+1;
 181     end_bit=XIAFS_BITS_PER_Z(sb);
 182 
 183     do {
 184         if (pos >= total_bits)
 185             pos=0;
 186         if (!not_done) {                /* first time */
 187             not_done=1;
 188             start_bit= pos & (end_bit-1);     
 189         } else 
 190             start_bit=0;
 191         if ( pos < prev_bit && pos+end_bit >= prev_bit) {   /* last time */
 192             not_done=0;
 193             end_bit=prev_bit & (end_bit-1);   /* only here end_bit modified */
 194         }
 195         bh = get__map_zone(sb, bmap_buf, bznr, cache, first_zone, 
 196                            bmap_zones, slots, pos, &z_nr);
 197         if (!bh)
 198             return 0;
 199         tmp=find_first_zero(bh, start_bit, end_bit);
 200         if (tmp >= 0)
 201             break;
 202         xiafs_unlock_super(sb, sb->u.xiafs_sb.s_zmap_cached);
 203         pos=(pos & ~(end_bit-1))+end_bit;
 204     } while (not_done);
 205 
 206     if (tmp < 0) 
 207         return 0;
 208     if (cache)
 209       que(bmap_buf, bznr, z_nr);
 210     xiafs_unlock_super(sb, cache);
 211     return (pos & ~(XIAFS_BITS_PER_Z(sb)-1))+tmp;
 212 }
 213 
 214 void xiafs_free_zone(struct super_block * sb, int d_addr)
     /*  */
 215 {
 216     struct buffer_head * bh;
 217     unsigned int bit, offset;
 218 
 219     if (!sb) {
 220         printk(INTERN_ERR);
 221         return;
 222     }
 223     if (d_addr < sb->u.xiafs_sb.s_firstdatazone ||
 224         d_addr >= sb->u.xiafs_sb.s_nzones) {
 225         printk("XIA-FS: bad zone number (%s %d)\n", WHERE_ERR);
 226         return;
 227     }
 228     bh = get_hash_table(sb->s_dev, d_addr, XIAFS_ZSIZE(sb));
 229     if (bh)
 230         mark_buffer_clean(bh);
 231     brelse(bh);
 232     bit=d_addr - sb->u.xiafs_sb.s_firstdatazone + 1;
 233     bh = get_zmap_zone(sb, bit, NULL);
 234     if (!bh)
 235         return;
 236     offset = bit & (XIAFS_BITS_PER_Z(sb) -1);
 237     if (!clear_bit(offset, bh->b_data))
 238         printk("XIA-FS: dev %s"
 239                " block bit %u (0x%x) already cleared (%s %d)\n",
 240                kdevname(sb->s_dev), bit, bit, WHERE_ERR);
 241     mark_buffer_dirty(bh, 1);
 242     xiafs_unlock_super(sb, sb->u.xiafs_sb.s_zmap_cached);
 243 }
 244 
 245 int xiafs_new_zone(struct super_block * sb, u_long prev_addr)
     /*  */
 246 {
 247     struct buffer_head * bh;
 248     int prev_znr, tmp;
 249 
 250     if (!sb) {
 251         printk(INTERN_ERR);
 252         return 0;
 253     }
 254     if (prev_addr < sb->u.xiafs_sb.s_firstdatazone || 
 255         prev_addr >= sb->u.xiafs_sb.s_nzones) {
 256         prev_addr=sb->u.xiafs_sb.s_firstdatazone;
 257     }      
 258     prev_znr=prev_addr-sb->u.xiafs_sb.s_firstdatazone+1;
 259     tmp=get_free_zbit(sb, prev_znr);
 260     if (!tmp)
 261         return 0;
 262     tmp += sb->u.xiafs_sb.s_firstdatazone -1;
 263     if (!(bh = getblk(sb->s_dev, tmp, XIAFS_ZSIZE(sb)))) {
 264         printk("XIA-FS: I/O error (%s %d)\n", WHERE_ERR);
 265         return 0;
 266     }
 267     if (bh->b_count != 1) {
 268         printk(INTERN_ERR);
 269         return 0;
 270     }
 271     clear_buf(bh);
 272     mark_buffer_uptodate(bh, 1);
 273     mark_buffer_dirty(bh, 1);
 274     brelse(bh);
 275     return tmp;
 276 }
 277 
 278 void xiafs_free_inode(struct inode * inode)
     /*  */
 279 {
 280     struct buffer_head * bh;
 281     struct super_block * sb;
 282     unsigned long ino;
 283 
 284     if (!inode)
 285         return;
 286     if (!inode->i_dev || inode->i_count!=1
 287         || inode->i_nlink || !inode->i_sb || inode->i_ino < 3
 288         || inode->i_ino > inode->i_sb->u.xiafs_sb.s_ninodes) {
 289         printk("XIA-FS: bad inode (%s %d)\n", WHERE_ERR);
 290         return;
 291     }
 292     sb = inode->i_sb;
 293     ino = inode->i_ino;
 294     bh = get_imap_zone(sb, ino, NULL);
 295     if (!bh)
 296         return;
 297     clear_inode(inode);
 298     if (!clear_bit(ino & (XIAFS_BITS_PER_Z(sb)-1), bh->b_data))
 299         printk("XIA-FS: dev %s"
 300                "inode bit %ld (0x%lx) already cleared (%s %d)\n",
 301                kdevname(inode->i_dev), ino, ino, WHERE_ERR);
 302     mark_buffer_dirty(bh, 1);
 303     xiafs_unlock_super(sb, sb->u.xiafs_sb.s_imap_cached);
 304 }
 305 
 306 struct inode * xiafs_new_inode(struct inode * dir)
     /*  */
 307 {
 308     struct super_block * sb;
 309     struct inode * inode;
 310     ino_t tmp;
 311 
 312     sb = dir->i_sb;
 313     if (!dir || !(inode = get_empty_inode()))
 314         return NULL;
 315     inode->i_sb = sb;
 316     inode->i_flags = inode->i_sb->s_flags;
 317 
 318     tmp=get_free_ibit(sb, dir->i_ino); 
 319     if (!tmp) {
 320         iput(inode);
 321         return NULL;
 322     }
 323     inode->i_count = 1;
 324     inode->i_nlink = 1;
 325     inode->i_dev = sb->s_dev;
 326     inode->i_uid = current->fsuid;
 327     inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->fsgid;
 328     inode->i_dirt = 1;
 329     inode->i_ino = tmp;
 330     inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 331     inode->i_op = NULL;
 332     inode->i_blocks = 0;
 333     inode->i_blksize = XIAFS_ZSIZE(inode->i_sb);
 334     insert_inode_hash(inode);
 335     return inode;
 336 }
 337 
 338 static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
 339 
 340 static u_long count_zone(struct buffer_head * bh)
     /*  */
 341 {
 342     int i, tmp;
 343     u_long sum;
 344 
 345     sum=0;
 346     for (i=bh->b_size; i-- > 0; ) {
 347         tmp=bh->b_data[i];
 348         sum += nibblemap[tmp & 0xf] + nibblemap[(tmp & 0xff) >> 4];
 349     }
 350     return sum;
 351 } 
 352 
 353 unsigned long xiafs_count_free_inodes(struct super_block *sb)
     /*  */
 354 {
 355     struct buffer_head * bh;
 356     int izones, i, not_que;
 357     u_long sum;
 358 
 359     sum=0;
 360     izones=sb->u.xiafs_sb.s_imap_zones;
 361     for (i=0; i < izones; i++) {
 362         bh=get_imap_zone(sb, i << XIAFS_BITS_PER_Z_BITS(sb), &not_que);
 363         if (bh) {
 364             sum += count_zone(bh);
 365             xiafs_unlock_super(sb, sb->u.xiafs_sb.s_imap_cached);
 366         }
 367     }
 368     i=izones << XIAFS_BITS_PER_Z_BITS(sb);
 369     return i - sum;
 370 }
 371 
 372 unsigned long xiafs_count_free_zones(struct super_block *sb)
     /*  */
 373 {
 374     struct buffer_head * bh;
 375     int zzones, i, not_que;
 376     u_long sum;
 377 
 378     sum=0;
 379     zzones=sb->u.xiafs_sb.s_zmap_zones;
 380     for (i=0; i < zzones; i++) {
 381         bh=get_zmap_zone(sb, i << XIAFS_BITS_PER_Z_BITS(sb), &not_que);
 382         if (bh) {
 383             sum += count_zone(bh);
 384             xiafs_unlock_super(sb, sb->u.xiafs_sb.s_zmap_cached);
 385         }
 386     }
 387     i=zzones << XIAFS_BITS_PER_Z_BITS(sb);
 388     return i - sum;
 389 }
/* */
root/fs/xiafs/bitmap.c

DEFINITIONS
