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

DEFINITIONS
