Subversion Repositories or1k

/*

 *  linux/fs/xiafs/bitmap.c

 *

 *  Copyright (C) Q. Frank Xia, 1993.

 *

 *  Based on Linus' minix/bitmap.c

 *  Copyright (C) Linus Torvalds, 1991, 1992.

 *

 *  This software may be redistributed per Linux Copyright.

 */

/* bitmap.c contains the code that handles the inode and block bitmaps */

#include <linux/sched.h>

#include <linux/locks.h>

#include <linux/xia_fs.h>

#include <linux/stat.h>

#include <linux/kernel.h>

#include <linux/string.h>

#include <asm/bitops.h>

#include "xiafs_mac.h"

char internal_error_message[]="XIA-FS: internal error %s %d\n";

static int find_first_zero(struct buffer_head *bh, int start_bit, int end_bit)

{

    /* This routine searches first 0 bit from (start_bit) to (end_bit-1).

     * If found the bit is set to 1 and the bit # is returned, otherwise,

     * -1 is returned. Race condition is avoid by using "btsl" and

     * "goto repeat".  ---Frank.

     */

    int end, i, j, tmp;

    u_long *bmap;

    bmap=(u_long *)bh->b_data;

    end = end_bit >> 5;

repeat:

    i=start_bit >> 5;

    if ( (tmp=(~bmap[i]) & (0xffffffff << (start_bit & 31))) )

        goto zone_found;

    while (++i < end)

        if (~bmap[i]) {

            tmp=~bmap[i];

            goto zone_found;

        }

    if ( !(tmp=~bmap[i] & ((1 << (end_bit & 31)) -1)) )

        return -1;

zone_found:

    for (j=0; j < 32; j++)

        if (tmp & (1 << j))

            break;

    if (set_bit(j,bmap+i)) {

        start_bit=j + (i << 5) + 1;

        goto repeat;

    }

    mark_buffer_dirty(bh, 1);

    return j + (i << 5);

}

static void clear_buf(struct buffer_head * bh)

{

    register int i;

    register long * lp;

    lp=(long *)bh->b_data;

    for (i= bh->b_size >> 2; i-- > 0; )

        *lp++=0;

}

static void que(struct buffer_head * bmap[], int bznr[], int pos)

{

    struct buffer_head * tbh;

    int tmp;

    int i;

    tbh=bmap[pos];

    tmp=bznr[pos];

    for (i=pos; i > 0; i--) {

        bmap[i]=bmap[i-1];

        bznr[i]=bznr[i-1];

    }

    bmap[0]=tbh;

    bznr[0]=tmp;

}

#define get_imap_zone(sb, bit_nr, not_que) \

        get__map_zone((sb), (sb)->u.xiafs_sb.s_imap_buf, \

                      (sb)->u.xiafs_sb.s_imap_iznr, \

                      (sb)->u.xiafs_sb.s_imap_cached, 1, \

                      (sb)->u.xiafs_sb.s_imap_zones, _XIAFS_IMAP_SLOTS, \

                      bit_nr, not_que)

#define get_zmap_zone(sb, bit_nr, not_que) \

        get__map_zone((sb), (sb)->u.xiafs_sb.s_zmap_buf, \

                      (sb)->u.xiafs_sb.s_zmap_zznr, \

                      (sb)->u.xiafs_sb.s_zmap_cached, \

                      1+(sb)->u.xiafs_sb.s_imap_zones, \

                      (sb)->u.xiafs_sb.s_zmap_zones, _XIAFS_ZMAP_SLOTS, \

                      bit_nr, not_que)

static struct buffer_head *

get__map_zone(struct super_block *sb, struct buffer_head * bmap_buf[],

          int bznr[], u_char cache, int first_zone,

          int bmap_zones, int slots, u_long bit_nr, int * not_que)

{

    struct buffer_head * tmp_bh;

    int z_nr, i;

    z_nr = bit_nr >> XIAFS_BITS_PER_Z_BITS(sb);

    if (z_nr >= bmap_zones) {

        printk("XIA-FS: bad inode/zone number (%s %d)\n", WHERE_ERR);

        return NULL;

    }

    if (!cache)

        return bmap_buf[z_nr];

    lock_super(sb);

    for (i=0; i < slots; i++)

        if (bznr[i]==z_nr)

            break;

    if (i < slots) {                    /* cache hit */

        if (not_que) {

            *not_que=i;

            return bmap_buf[i];

        } else {

            que(bmap_buf, bznr, i);

            return bmap_buf[0];

        }

    }

    tmp_bh=bread(sb->s_dev, z_nr+first_zone, XIAFS_ZSIZE(sb)); /* cache not hit */

    if (!tmp_bh) {

        printk("XIA-FS: read bitmap failed (%s %d)\n", WHERE_ERR);

        unlock_super(sb);

        return NULL;

    }

    brelse(bmap_buf[slots-1]);

    bmap_buf[slots-1]=tmp_bh;

    bznr[slots-1]=z_nr;

    if (not_que)

        *not_que=slots-1;

    else

        que(bmap_buf, bznr, slots-1);

    return tmp_bh;

}

#define xiafs_unlock_super(sb, cache)   if (cache) unlock_super(sb);

#define get_free_ibit(sb, prev_bit) \

        get_free__bit(sb, sb->u.xiafs_sb.s_imap_buf, \

                      sb->u.xiafs_sb.s_imap_iznr, \

                      sb->u.xiafs_sb.s_imap_cached, \

                      1, sb->u.xiafs_sb.s_imap_zones, \

                      _XIAFS_IMAP_SLOTS, prev_bit);

#define get_free_zbit(sb, prev_bit) \

        get_free__bit(sb, sb->u.xiafs_sb.s_zmap_buf, \

                      sb->u.xiafs_sb.s_zmap_zznr, \

                      sb->u.xiafs_sb.s_zmap_cached, \

                      1 + sb->u.xiafs_sb.s_imap_zones, \

                      sb->u.xiafs_sb.s_zmap_zones, \

                      _XIAFS_ZMAP_SLOTS, prev_bit);

static u_long

get_free__bit(struct super_block *sb, struct buffer_head * bmap_buf[],

              int bznr[], u_char cache, int first_zone, int bmap_zones,

              int slots, u_long prev_bit)

{

    struct buffer_head * bh;

    int not_done=0;

    u_long pos, start_bit, end_bit, total_bits;

    int z_nr, tmp;

    total_bits=bmap_zones << XIAFS_BITS_PER_Z_BITS(sb);

    if (prev_bit >= total_bits)

        prev_bit=0;

    pos=prev_bit+1;

    end_bit=XIAFS_BITS_PER_Z(sb);

    do {

        if (pos >= total_bits)

            pos=0;

        if (!not_done) {                /* first time */

            not_done=1;

            start_bit= pos & (end_bit-1);

        } else

            start_bit=0;

        if ( pos < prev_bit && pos+end_bit >= prev_bit) {   /* last time */

            not_done=0;

            end_bit=prev_bit & (end_bit-1);   /* only here end_bit modified */

        }

        bh = get__map_zone(sb, bmap_buf, bznr, cache, first_zone,

                           bmap_zones, slots, pos, &z_nr);

        if (!bh)

            return 0;

        tmp=find_first_zero(bh, start_bit, end_bit);

        if (tmp >= 0)

            break;

        xiafs_unlock_super(sb, sb->u.xiafs_sb.s_zmap_cached);

        pos=(pos & ~(end_bit-1))+end_bit;

    } while (not_done);

    if (tmp < 0)

        return 0;

    if (cache)

      que(bmap_buf, bznr, z_nr);

    xiafs_unlock_super(sb, cache);

    return (pos & ~(XIAFS_BITS_PER_Z(sb)-1))+tmp;

}

void xiafs_free_zone(struct super_block * sb, int d_addr)

{

    struct buffer_head * bh;

    unsigned int bit, offset;

    if (!sb) {

        printk(INTERN_ERR);

        return;

    }

    if (d_addr < sb->u.xiafs_sb.s_firstdatazone ||

        d_addr >= sb->u.xiafs_sb.s_nzones) {

        printk("XIA-FS: bad zone number (%s %d)\n", WHERE_ERR);

        return;

    }

    bh = get_hash_table(sb->s_dev, d_addr, XIAFS_ZSIZE(sb));

    if (bh)

        mark_buffer_clean(bh);

    brelse(bh);

    bit=d_addr - sb->u.xiafs_sb.s_firstdatazone + 1;

    bh = get_zmap_zone(sb, bit, NULL);

    if (!bh)

        return;

    offset = bit & (XIAFS_BITS_PER_Z(sb) -1);

    if (!clear_bit(offset, bh->b_data))

        printk("XIA-FS: dev %s"

               " block bit %u (0x%x) already cleared (%s %d)\n",

               kdevname(sb->s_dev), bit, bit, WHERE_ERR);

    mark_buffer_dirty(bh, 1);

    xiafs_unlock_super(sb, sb->u.xiafs_sb.s_zmap_cached);

}

int xiafs_new_zone(struct super_block * sb, u_long prev_addr)

{

    struct buffer_head * bh;

    int prev_znr, tmp;

    if (!sb) {

        printk(INTERN_ERR);

        return 0;

    }

    if (prev_addr < sb->u.xiafs_sb.s_firstdatazone ||

        prev_addr >= sb->u.xiafs_sb.s_nzones) {

        prev_addr=sb->u.xiafs_sb.s_firstdatazone;

    }

    prev_znr=prev_addr-sb->u.xiafs_sb.s_firstdatazone+1;

    tmp=get_free_zbit(sb, prev_znr);

    if (!tmp)

        return 0;

    tmp += sb->u.xiafs_sb.s_firstdatazone -1;

    if (!(bh = getblk(sb->s_dev, tmp, XIAFS_ZSIZE(sb)))) {

        printk("XIA-FS: I/O error (%s %d)\n", WHERE_ERR);

        return 0;

    }

    if (bh->b_count != 1) {

        printk(INTERN_ERR);

        return 0;

    }

    clear_buf(bh);

    mark_buffer_uptodate(bh, 1);

    mark_buffer_dirty(bh, 1);

    brelse(bh);

    return tmp;

}

void xiafs_free_inode(struct inode * inode)

{

    struct buffer_head * bh;

    struct super_block * sb;

    unsigned long ino;

    if (!inode)

        return;

    if (!inode->i_dev || inode->i_count!=1

        || inode->i_nlink || !inode->i_sb || inode->i_ino < 3

        || inode->i_ino > inode->i_sb->u.xiafs_sb.s_ninodes) {

        printk("XIA-FS: bad inode (%s %d)\n", WHERE_ERR);

        return;

    }

    sb = inode->i_sb;

    ino = inode->i_ino;

    bh = get_imap_zone(sb, ino, NULL);

    if (!bh)

        return;

    clear_inode(inode);

    if (!clear_bit(ino & (XIAFS_BITS_PER_Z(sb)-1), bh->b_data))

        printk("XIA-FS: dev %s"

               "inode bit %ld (0x%lx) already cleared (%s %d)\n",

               kdevname(inode->i_dev), ino, ino, WHERE_ERR);

    mark_buffer_dirty(bh, 1);

    xiafs_unlock_super(sb, sb->u.xiafs_sb.s_imap_cached);

}

struct inode * xiafs_new_inode(struct inode * dir)

{

    struct super_block * sb;

    struct inode * inode;

    ino_t tmp;

    sb = dir->i_sb;

    if (!dir || !(inode = get_empty_inode()))

        return NULL;

    inode->i_sb = sb;

    inode->i_flags = inode->i_sb->s_flags;

    tmp=get_free_ibit(sb, dir->i_ino);

    if (!tmp) {

        iput(inode);

        return NULL;

    }

    inode->i_count = 1;

    inode->i_nlink = 1;

    inode->i_dev = sb->s_dev;

    inode->i_uid = current->fsuid;

    inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->fsgid;

    inode->i_dirt = 1;

    inode->i_ino = tmp;

    inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;

    inode->i_op = NULL;

    inode->i_blocks = 0;

    inode->i_blksize = XIAFS_ZSIZE(inode->i_sb);

    insert_inode_hash(inode);

    return inode;

}

static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };

static u_long count_zone(struct buffer_head * bh)

{

    int i, tmp;

    u_long sum;

    sum=0;

    for (i=bh->b_size; i-- > 0; ) {

        tmp=bh->b_data[i];

        sum += nibblemap[tmp & 0xf] + nibblemap[(tmp & 0xff) >> 4];

    }

    return sum;

}

unsigned long xiafs_count_free_inodes(struct super_block *sb)

{

    struct buffer_head * bh;

    int izones, i, not_que;

    u_long sum;

    sum=0;

    izones=sb->u.xiafs_sb.s_imap_zones;

    for (i=0; i < izones; i++) {

        bh=get_imap_zone(sb, i << XIAFS_BITS_PER_Z_BITS(sb), &not_que);

        if (bh) {

            sum += count_zone(bh);

            xiafs_unlock_super(sb, sb->u.xiafs_sb.s_imap_cached);

        }

    }

    i=izones << XIAFS_BITS_PER_Z_BITS(sb);

    return i - sum;

}

unsigned long xiafs_count_free_zones(struct super_block *sb)

{

    struct buffer_head * bh;

    int zzones, i, not_que;

    u_long sum;

    sum=0;

    zzones=sb->u.xiafs_sb.s_zmap_zones;

    for (i=0; i < zzones; i++) {

        bh=get_zmap_zone(sb, i << XIAFS_BITS_PER_Z_BITS(sb), &not_que);

        if (bh) {

            sum += count_zone(bh);

            xiafs_unlock_super(sb, sb->u.xiafs_sb.s_zmap_cached);

        }

    }

    i=zzones << XIAFS_BITS_PER_Z_BITS(sb);

    return i - sum;

}