fix_node.c

reiserfsprogs-3.6.19.tar.gz 源码 给有需要的人！

 *	s012	number of items that fall into splitted nodes.
 *	lbytes	number of bytes which flow to the left neighbor from the item that is not
 *		not shifted entirely
 *	rbytes	number of bytes which flow to the right neighbor from the item that is not
 *		not shifted entirely
 *	s1bytes	number of bytes which flow to the first  new node when S[0] splits (this number is contained in s012 array)
 */

static void set_parameters (struct tree_balance * tb, int h, int lnum,
			    int rnum, int blk_num, short * s012, int lb, int rb)
{

    tb->lnum[h] = lnum;
    tb->rnum[h] = rnum;
    tb->blknum[h] = blk_num;

    if (h == 0)
    {  /* only for leaf level */
	if (s012 != NULL)
	{
	    tb->s0num = * s012 ++,
		tb->s1num = * s012 ++,
		tb->s2num = * s012 ++;
	    tb->s1bytes = * s012 ++;
	    tb->s2bytes = * s012;
	}
	tb->lbytes = lb;
	tb->rbytes = rb;
    }
}

static void decrement_key (struct key * p_s_key) 
{
    int type;

    type = get_type (p_s_key);
    switch (type) {
    case TYPE_STAT_DATA:
	set_key_objectid (p_s_key, get_key_objectid (p_s_key) - 1);
	set_type_and_offset (key_format (p_s_key), p_s_key,
			     (loff_t)MAX_FILE_SIZE_V2, TYPE_INDIRECT);
	return;

    case TYPE_INDIRECT:
    case TYPE_DIRECT:
    case TYPE_DIRENTRY:
	set_offset (key_format (p_s_key), p_s_key, get_offset (p_s_key) - 1);
	if (get_offset (p_s_key) == 0)
	    set_type (key_format (p_s_key), p_s_key, TYPE_STAT_DATA);
	return;
    }
    reiserfs_warning (stderr, "vs-8125: decrement_key: item of wrong type found %k",
		      p_s_key);
}


int are_items_mergeable (struct item_head * left, struct item_head * right, int bsize)
{
    if (comp_keys (&left->ih_key, &right->ih_key) != -1) {
	reiserfs_panic ("vs-16070: are_items_mergeable: left %k, right %k", &(left->ih_key), &(right->ih_key));
    }

    if (not_of_one_file (&left->ih_key, &right->ih_key))
	return 0;

    if (I_IS_DIRECTORY_ITEM (left)) {
	return 1;
    }

    if ((I_IS_DIRECT_ITEM (left) && I_IS_DIRECT_ITEM (right)) || 
	(I_IS_INDIRECT_ITEM (left) && I_IS_INDIRECT_ITEM (right)))
	return (get_offset (&left->ih_key) + get_bytes_number (left, bsize) == get_offset (&right->ih_key)) ? 1 : 0;

    return 0;
}

/* get left neighbor of the leaf node */
static struct buffer_head * get_left_neighbor (reiserfs_filsys_t * s, struct path * path)
{
    struct key key;
    struct path path_to_left_neighbor;
    struct buffer_head * bh;

    copy_key (&key, B_N_PKEY (PATH_PLAST_BUFFER (path), 0));
    decrement_key (&key);

    init_path (&path_to_left_neighbor);
    search_by_key (s, &key, &path_to_left_neighbor, DISK_LEAF_NODE_LEVEL);
    if (PATH_LAST_POSITION (&path_to_left_neighbor) == 0) {
	pathrelse (&path_to_left_neighbor);
	return 0;
    }
    bh = PATH_PLAST_BUFFER (&path_to_left_neighbor);
    bh->b_count ++;
    pathrelse (&path_to_left_neighbor);
    return bh;
}


extern struct key  MIN_KEY;
static struct buffer_head * get_right_neighbor (reiserfs_filsys_t * s, struct path * path)
{
    struct key key;
    struct key * rkey;
    struct path path_to_right_neighbor;
    struct buffer_head * bh;
    
    rkey = get_rkey (path, s);
    if (comp_keys (rkey, &MIN_KEY) == 0)
	reiserfs_panic ("vs-16080: get_right_neighbor: get_rkey returned min key (path has changed)");
    copy_key (&key, rkey);
    
  
    init_path (&path_to_right_neighbor);
    search_by_key (s, &key, &path_to_right_neighbor, DISK_LEAF_NODE_LEVEL);
    if (PATH_PLAST_BUFFER (&path_to_right_neighbor) == PATH_PLAST_BUFFER (path)) {
	pathrelse (&path_to_right_neighbor);
	return 0;
    }
    bh = PATH_PLAST_BUFFER (&path_to_right_neighbor);
    bh->b_count ++;
    pathrelse (&path_to_right_neighbor);
    return bh;
}


int is_left_mergeable (reiserfs_filsys_t * s, struct path * path)
{
    struct item_head * right;
    struct buffer_head * bh;
    int retval;
    
    right = B_N_PITEM_HEAD (PATH_PLAST_BUFFER (path), 0);
    
    bh = get_left_neighbor (s, path);
    if (bh == 0) {
	return 0;
    }
    retval = are_items_mergeable (B_N_PITEM_HEAD (bh, B_NR_ITEMS (bh) - 1), right, bh->b_size);
    brelse (bh);
    return retval;
}


int is_right_mergeable (reiserfs_filsys_t * s, struct path * path)
{
    struct item_head * left;
    struct buffer_head * bh;
    int retval;
    
    left = B_N_PITEM_HEAD (PATH_PLAST_BUFFER (path), B_NR_ITEMS (PATH_PLAST_BUFFER (path)) - 1);
    
    bh = get_right_neighbor (s, path);
    if (bh == 0) {
	return 0;
    }
    retval = are_items_mergeable (left, B_N_PITEM_HEAD (bh, 0), bh->b_size);
    brelse (bh);
    return retval;
}



/* check, does node disappear if we shift tb->lnum[0] items to left neighbor
   and tb->rnum[0] to the right one. */
static int is_leaf_removable (struct tree_balance * tb)
{
    struct virtual_node * vn = tb->tb_vn;
    int to_left, to_right;
    int size;
    int remain_items;
    
    /* number of items, that will be shifted to left (right) neighbor entirely */
    to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
    to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
    remain_items = vn->vn_nr_item;
    
    /* how many items remain in S[0] after shiftings to neighbors */
    remain_items -= (to_left + to_right);
    
    if (remain_items < 1) {
	/* all content of node can be shifted to neighbors */
	set_parameters (tb, 0, to_left, vn->vn_nr_item - to_left, 0, NULL, -1, -1);    
	return 1;
    }
    
    if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
	/* S[0] is not removable */
	return 0;
    
    /* check, whether we can divide 1 remaining item between neighbors */
    
    /* get size of remaining item (in directory entry count if directory) */
    size = item_length (tb, to_left);
    
    if (tb->lbytes + tb->rbytes >= size) {
	set_parameters (tb, 0, to_left + 1, to_right + 1, 0, NULL, tb->lbytes, -1);
	return 1;
    }
    
    return 0;
}


/* check whether L, S, R can be joined in one node */
static int are_leaves_removable (struct tree_balance * tb, int lfree, int rfree)
{
    struct virtual_node * vn = tb->tb_vn;
    int ih_size;
    struct buffer_head *S0;

    S0 = PATH_H_PBUFFER (tb->tb_path, 0);

    ih_size = 0;
    if (vn->vn_nr_item) {
	if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
	    ih_size += IH_SIZE;
    
	if (vn->vn_vi[vn->vn_nr_item-1].vi_type & VI_TYPE_RIGHT_MERGEABLE)
	    ih_size += IH_SIZE;
    } else {
	/* there was only one item and it will be deleted */
	struct item_head * ih;
    
	ih = B_N_PITEM_HEAD (S0, 0);
	if (tb->CFR[0] && !not_of_one_file (&(ih->ih_key), B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0])))
	    if (I_IS_DIRECTORY_ITEM(ih)) {
		/* we can delete any directory item in fsck (if it is unreachable) */
		if (get_offset (&ih->ih_key) != DOT_OFFSET) {
		    /* must get left neighbor here to make sure, that
                       left neighbor is of the same directory */
		    struct buffer_head * left;
		    
		    left = get_left_neighbor (tb->tb_fs, tb->tb_path);
		    if (left) {
			struct item_head * last;

			if (B_NR_ITEMS (left) == 0)
			    reiserfs_panic ("vs-8135: are_leaves_removable: "
					    "empty node in the tree");
			last = B_N_PITEM_HEAD (left, B_NR_ITEMS (left) - 1);
			if (!comp_short_keys (&last->ih_key, &ih->ih_key))
			    ih_size = IH_SIZE;
			brelse (left);
		    }
		}
	    }
    
    }

    if ((int)MAX_CHILD_SIZE(S0->b_size) + vn->vn_size <= rfree + lfree + ih_size) {
	set_parameters (tb, 0, -1, -1, -1, NULL, -1, -1);
	return 1;  
    }
    return 0;
  
}



/* when we do not split item, lnum and rnum are numbers of entire items */
#define SET_PAR_SHIFT_LEFT \
if (h)\
{\
   int to_l;\
   \
   to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
	      (MAX_NR_KEY(Sh) + 1 - lpar);\
	      \
	      set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
}\
else \
{\
   if (lset==LEFT_SHIFT_FLOW)\
     set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
		     tb->lbytes, -1);\
   else\
     set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
		     -1, -1);\
}


#define SET_PAR_SHIFT_RIGHT \
if (h)\
{\
   int to_r;\
   \
   to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
   \
   set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
}\
else \
{\
   if (rset==RIGHT_SHIFT_FLOW)\
     set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
		  -1, tb->rbytes);\
   else\
     set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
		  -1, -1);\
}



/* Get new buffers for storing new nodes that are created while balancing.
 * Returns:	SCHEDULE_OCCURED - schedule occured while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 *	        NO_DISK_SPACE - no disk space.
 */
static int  get_empty_nodes (struct tree_balance * p_s_tb,
			     int n_h)
{
    struct buffer_head  * p_s_new_bh,
	*	p_s_Sh = PATH_H_PBUFFER (p_s_tb->tb_path, n_h);
    unsigned long	      *	p_n_blocknr,
	a_n_blocknrs[MAX_AMOUNT_NEEDED] = {0, };
    int       		n_counter,
	n_number_of_freeblk,
	n_amount_needed,/* number of needed empty blocks */
	n_repeat;
    reiserfs_filsys_t *	fs = p_s_tb->tb_fs;


    if (n_h == 0 && p_s_tb->insert_size[n_h] == 0x7fff)
	return CARRY_ON;
    
    /* number_of_freeblk is the number of empty blocks which have been
       acquired for use by the balancing algorithm minus the number of
       empty blocks used in the previous levels of the analysis,
       number_of_freeblk = tb->cur_blknum can be non-zero if a
       schedule occurs after empty blocks are acquired, and the
       balancing analysis is then restarted, amount_needed is the
       number needed by this level (n_h) of the balancing analysis.
			    
       Note that for systems with many processes writing, it would be
       more layout optimal to calculate the total number needed by all
       levels and then to run reiserfs_new_blocks to get all of them
       at once.  */

    /* Initiate number_of_freeblk to the amount acquired prior to the restart of
       the analysis or 0 if not restarted, then subtract the amount needed
       by all of the levels of the tree below n_h. */
    /* blknum includes S[n_h], so we subtract 1 in this calculation */
    for ( n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum; n_counter < n_h; n_counter++ )
	n_number_of_freeblk -= ( p_s_tb->blknum[n_counter] ) ? (p_s_tb->blknum[n_counter] - 1) : 0;

    /* Allocate missing empty blocks. */
    /* if p_s_Sh == 0  then we are getting a new root */
    n_amount_needed = ( p_s_Sh ) ? (p_s_tb->blknum[n_h] - 1) : 1;
    /*  Amount_needed = the amount that we need more than the amount that we have. */
    if ( n_amount_needed > n_number_of_freeblk )
	n_amount_needed -= n_number_of_freeblk;
    else /* If we have enough already then there is nothing to do. */
	return CARRY_ON;

    if ( (n_repeat = reiserfs_new_blocknrs (p_s_tb->tb_fs, a_n_blocknrs,
					    PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_blocknr, n_amount_needed)) != CARRY_ON ) {
	return n_repeat; /* Out of disk space. */ 
    }

    /* for each blocknumber we just got, get a buffer and stick it on FEB */
    for ( p_n_blocknr = a_n_blocknrs, n_counter = 0; n_counter < n_amount_needed;
	  p_n_blocknr++, n_counter++ ) { 
	p_s_new_bh = getblk (fs->fs_dev, *p_n_blocknr, fs->fs_blocksize);
	if (p_s_new_bh->b_count > 1) {
	    die ("get_empty_nodes: not free empty buffer");
	}
	
	/* Put empty buffers into the array. */
	p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
    }
    
    return CARRY_ON;
}


/* Get free space of the left neighbor,
 * which is stored in the parent node of the left neighbor.
 */
static int get_lfree (struct tree_balance * tb, int h)
{
    struct buffer_head * l, * f;
    int order;

    if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0)
	return 0;

    if (f == l)
	order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) - 1;
    else {