bitmap.c

来自「Linux Kernel 2.6.9 for OMAP1710」· C语言 代码 · 共 1,146 行 · 第 1/3 页

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */
/* Reiserfs block (de)allocator, bitmap-based. */

#include <linux/config.h>
#include <linux/time.h>
#include <linux/reiserfs_fs.h>
#include <linux/errno.h>
#include <linux/buffer_head.h>
#include <linux/kernel.h>
#include <linux/pagemap.h>
#include <linux/reiserfs_fs_sb.h>
#include <linux/reiserfs_fs_i.h>
#include <linux/quotaops.h>

#define PREALLOCATION_SIZE 9

/* different reiserfs block allocator options */

#define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits)

#define  _ALLOC_concentrating_formatted_nodes 0
#define  _ALLOC_displacing_large_files 1
#define  _ALLOC_displacing_new_packing_localities 2
#define  _ALLOC_old_hashed_relocation 3
#define  _ALLOC_new_hashed_relocation 4
#define  _ALLOC_skip_busy 5
#define  _ALLOC_displace_based_on_dirid 6
#define  _ALLOC_hashed_formatted_nodes 7
#define  _ALLOC_old_way 8
#define  _ALLOC_hundredth_slices 9
#define  _ALLOC_dirid_groups 10
#define  _ALLOC_oid_groups 11
#define  _ALLOC_packing_groups 12

#define  concentrating_formatted_nodes(s)	test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
#define  displacing_large_files(s)		test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
#define  displacing_new_packing_localities(s)	test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))

#define SET_OPTION(optname) \
   do { \
        reiserfs_warning(s, "reiserfs: option \"%s\" is set", #optname); \
        set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
    } while(0)
#define TEST_OPTION(optname, s) \
    test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))

static inline void get_bit_address (struct super_block * s,
				    b_blocknr_t block, int * bmap_nr, int * offset)
{
    /* It is in the bitmap block number equal to the block
     * number divided by the number of bits in a block. */
    *bmap_nr = block / (s->s_blocksize << 3);
    /* Within that bitmap block it is located at bit offset *offset. */
    *offset = block & ((s->s_blocksize << 3) - 1 );
    return;
}

#ifdef CONFIG_REISERFS_CHECK
int is_reusable (struct super_block * s, b_blocknr_t block, int bit_value)
{
    int i, j;

    if (block == 0 || block >= SB_BLOCK_COUNT (s)) {
	reiserfs_warning (s, "vs-4010: is_reusable: block number is out of range %lu (%u)",
			  block, SB_BLOCK_COUNT (s));
	return 0;
    }

    /* it can't be one of the bitmap blocks */
    for (i = 0; i < SB_BMAP_NR (s); i ++)
	if (block == SB_AP_BITMAP (s)[i].bh->b_blocknr) {
	    reiserfs_warning (s, "vs: 4020: is_reusable: "
			      "bitmap block %lu(%u) can't be freed or reused",
			      block, SB_BMAP_NR (s));
	    return 0;
	}
  
    get_bit_address (s, block, &i, &j);

    if (i >= SB_BMAP_NR (s)) {
	reiserfs_warning (s, "vs-4030: is_reusable: there is no so many bitmap blocks: "
			  "block=%lu, bitmap_nr=%d", block, i);
	return 0;
    }

    if ((bit_value == 0 && 
         reiserfs_test_le_bit(j, SB_AP_BITMAP(s)[i].bh->b_data)) ||
	(bit_value == 1 && 
	 reiserfs_test_le_bit(j, SB_AP_BITMAP (s)[i].bh->b_data) == 0)) {
	reiserfs_warning (s, "vs-4040: is_reusable: corresponding bit of block %lu does not "
			  "match required value (i==%d, j==%d) test_bit==%d",
		block, i, j, reiserfs_test_le_bit (j, SB_AP_BITMAP (s)[i].bh->b_data));

	return 0;
    }

    if (bit_value == 0 && block == SB_ROOT_BLOCK (s)) {
	reiserfs_warning (s, "vs-4050: is_reusable: this is root block (%u), "
			  "it must be busy", SB_ROOT_BLOCK (s));
	return 0;
    }

    return 1;
}
#endif /* CONFIG_REISERFS_CHECK */

/* searches in journal structures for a given block number (bmap, off). If block
   is found in reiserfs journal it suggests next free block candidate to test. */
static inline  int is_block_in_journal (struct super_block * s, int bmap, int
off, int *next)
{
    b_blocknr_t tmp;

    if (reiserfs_in_journal (s, bmap, off, 1, &tmp)) {
	if (tmp) {              /* hint supplied */
	    *next = tmp;
	    PROC_INFO_INC( s, scan_bitmap.in_journal_hint );
	} else {
	    (*next) = off + 1;          /* inc offset to avoid looping. */
	    PROC_INFO_INC( s, scan_bitmap.in_journal_nohint );
	}
	PROC_INFO_INC( s, scan_bitmap.retry );
	return 1;
    }
    return 0;
}

/* it searches for a window of zero bits with given minimum and maximum lengths in one bitmap
 * block; */
static int scan_bitmap_block (struct reiserfs_transaction_handle *th,
			      int bmap_n, int *beg, int boundary, int min, int max, int unfm)
{
    struct super_block *s = th->t_super;
    struct reiserfs_bitmap_info *bi=&SB_AP_BITMAP(s)[bmap_n];
    int end, next;
    int org = *beg;

    RFALSE(bmap_n >= SB_BMAP_NR (s), "Bitmap %d is out of range (0..%d)",bmap_n, SB_BMAP_NR (s) - 1);
    PROC_INFO_INC( s, scan_bitmap.bmap );
/* this is unclear and lacks comments, explain how journal bitmaps
   work here for the reader.  Convey a sense of the design here. What
   is a window? */
/* - I mean `a window of zero bits' as in description of this function - Zam. */
  
    if ( !bi ) {
	reiserfs_warning (s, "NULL bitmap info pointer for bitmap %d", bmap_n);
	return 0;
    }
    if (buffer_locked (bi->bh)) {
       PROC_INFO_INC( s, scan_bitmap.wait );
       __wait_on_buffer (bi->bh);
    }

    while (1) {
	cont:
	if (bi->free_count < min)
		return 0; // No free blocks in this bitmap

	/* search for a first zero bit -- beggining of a window */
	*beg = reiserfs_find_next_zero_le_bit
	        ((unsigned long*)(bi->bh->b_data), boundary, *beg);
  
	if (*beg + min > boundary) { /* search for a zero bit fails or the rest of bitmap block
				      * cannot contain a zero window of minimum size */
	    return 0;
	}

	if (unfm && is_block_in_journal(s,bmap_n, *beg, beg))
	    continue;
	/* first zero bit found; we check next bits */
	for (end = *beg + 1;; end ++) {
	    if (end >= *beg + max || end >= boundary || reiserfs_test_le_bit (end, bi->bh->b_data)) {
		next = end;
		break;
	    }
	    /* finding the other end of zero bit window requires looking into journal structures (in
	     * case of searching for free blocks for unformatted nodes) */
	    if (unfm && is_block_in_journal(s, bmap_n, end, &next))
		break;
	}

	/* now (*beg) points to beginning of zero bits window,
	 * (end) points to one bit after the window end */
	if (end - *beg >= min) { /* it seems we have found window of proper size */
	    int i;
	    reiserfs_prepare_for_journal (s, bi->bh, 1);
	    /* try to set all blocks used checking are they still free */
	    for (i = *beg; i < end; i++) {
		/* It seems that we should not check in journal again. */
		if (reiserfs_test_and_set_le_bit (i, bi->bh->b_data)) {
		    /* bit was set by another process
		     * while we slept in prepare_for_journal() */
		    PROC_INFO_INC( s, scan_bitmap.stolen );
		    if (i >= *beg + min)	{ /* we can continue with smaller set of allocated blocks,
					   * if length of this set is more or equal to `min' */
			end = i;
			break;
		    }
		    /* otherwise we clear all bit were set ... */
		    while (--i >= *beg)
			reiserfs_test_and_clear_le_bit (i, bi->bh->b_data);
		    reiserfs_restore_prepared_buffer (s, bi->bh);
		    *beg = org;
		    /* ... and search again in current block from beginning */
		    goto cont;	
		}
	    }
	    bi->free_count -= (end - *beg);
	    journal_mark_dirty (th, s, bi->bh);

	    /* free block count calculation */
	    reiserfs_prepare_for_journal (s, SB_BUFFER_WITH_SB(s), 1);
	    PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
	    journal_mark_dirty (th, s, SB_BUFFER_WITH_SB(s));

	    return end - (*beg);
	} else {
	    *beg = next;
	}
    }
}

static int bmap_hash_id(struct super_block *s, u32 id) {
    char * hash_in = NULL;
    unsigned long hash;
    unsigned bm;

    if (id <= 2) {
	bm = 1;
    } else {
        hash_in = (char *)(&id);
        hash = keyed_hash(hash_in, 4);
	bm = hash % SB_BMAP_NR(s);
	if (!bm)
	    bm = 1;
    }
    return bm;
}

/*
 * hashes the id and then returns > 0 if the block group for the
 * corresponding hash is full
 */
static inline int block_group_used(struct super_block *s, u32 id) {
    int bm;
    bm = bmap_hash_id(s, id);
    if (SB_AP_BITMAP(s)[bm].free_count > ((s->s_blocksize << 3) * 60 / 100) ) {
        return 0;
    }
    return 1;
}

/*
 * the packing is returned in disk byte order
 */
u32 reiserfs_choose_packing(struct inode *dir) {
    u32 packing;
    if (TEST_OPTION(packing_groups, dir->i_sb)) {
	u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id);
	/*
	 * some versions of reiserfsck expect packing locality 1 to be
	 * special
	 */
	if (parent_dir == 1 || block_group_used(dir->i_sb,parent_dir))
            packing = INODE_PKEY(dir)->k_objectid;
        else
            packing = INODE_PKEY(dir)->k_dir_id;
    } else
        packing = INODE_PKEY(dir)->k_objectid;
    return packing;
}
  
/* Tries to find contiguous zero bit window (given size) in given region of
 * bitmap and place new blocks there. Returns number of allocated blocks. */
static int scan_bitmap (struct reiserfs_transaction_handle *th,
			b_blocknr_t *start, b_blocknr_t finish,
			int min, int max, int unfm, unsigned long file_block)
{
    int nr_allocated=0;
    struct super_block * s = th->t_super;
    /* find every bm and bmap and bmap_nr in this file, and change them all to bitmap_blocknr
     * - Hans, it is not a block number - Zam. */

    int bm, off;
    int end_bm, end_off;
    int off_max = s->s_blocksize << 3;

    PROC_INFO_INC( s, scan_bitmap.call ); 
    if ( SB_FREE_BLOCKS(s) <= 0)
	return 0; // No point in looking for more free blocks

    get_bit_address (s, *start, &bm, &off);
    get_bit_address (s, finish, &end_bm, &end_off);

    /* When the bitmap is more than 10% free, anyone can allocate.
     * When it's less than 10% free, only files that already use the
     * bitmap are allowed. Once we pass 80% full, this restriction
     * is lifted.
     *
     * We do this so that files that grow later still have space close to
     * their original allocation. This improves locality, and presumably
     * performance as a result.
     *
     * This is only an allocation policy and does not make up for getting a
     * bad hint. Decent hinting must be implemented for this to work well.
     */
    if ( TEST_OPTION(skip_busy, s) && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s)/20 ) {
	for (;bm < end_bm; bm++, off = 0) {
	    if ( ( off && (!unfm || (file_block != 0))) || SB_AP_BITMAP(s)[bm].free_count > (s->s_blocksize << 3) / 10 )
		nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
	    if (nr_allocated)
		goto ret;
        }
	get_bit_address (s, *start, &bm, &off);
    }

    for (;bm < end_bm; bm++, off = 0) {
	nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
	if (nr_allocated)
	    goto ret;
    }

    nr_allocated = scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
  
 ret:
    *start = bm * off_max + off;
    return nr_allocated;

}

static void _reiserfs_free_block (struct reiserfs_transaction_handle *th,
				  struct inode *inode, b_blocknr_t block,
				  int for_unformatted)
{
    struct super_block * s = th->t_super;
    struct reiserfs_super_block * rs;
    struct buffer_head * sbh;
    struct reiserfs_bitmap_info *apbi;
    int nr, offset;

    PROC_INFO_INC( s, free_block );

    rs = SB_DISK_SUPER_BLOCK (s);
    sbh = SB_BUFFER_WITH_SB (s);
    apbi = SB_AP_BITMAP(s);

    get_bit_address (s, block, &nr, &offset);

    if (nr >= sb_bmap_nr (rs)) {
	reiserfs_warning (s, "vs-4075: reiserfs_free_block: "
			  "block %lu is out of range on %s",
			  block, reiserfs_bdevname (s));
	return;
    }

    reiserfs_prepare_for_journal(s, apbi[nr].bh, 1 ) ;

    /* clear bit for the given block in bit map */
    if (!reiserfs_test_and_clear_le_bit (offset, apbi[nr].bh->b_data)) {
	reiserfs_warning (s, "vs-4080: reiserfs_free_block: "
			  "free_block (%s:%lu)[dev:blocknr]: bit already cleared",
			  reiserfs_bdevname (s), block);
    }
    apbi[nr].free_count ++;
    journal_mark_dirty (th, s, apbi[nr].bh);

    reiserfs_prepare_for_journal(s, sbh, 1) ;
    /* update super block */
    set_sb_free_blocks( rs, sb_free_blocks(rs) + 1 );

    journal_mark_dirty (th, s, sbh);
    if (for_unformatted)
        DQUOT_FREE_BLOCK_NODIRTY(inode, 1);
}

void reiserfs_free_block (struct reiserfs_transaction_handle *th, 
			  struct inode *inode, b_blocknr_t block,
			  int for_unformatted)
{
    struct super_block * s = th->t_super;