fix_node.c

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

	order = get_blkh_nr_items (B_BLK_HEAD(l));
	f = l;
    }

    if (get_dc_child_size (B_N_CHILD(f,order)) == 0) {
	reiserfs_warning (stderr, "get_lfree: block %u block_head %z has bad child pointer %y, order %d\n",
			  l->b_blocknr, l, B_N_CHILD(f,order), order);
    }
    return (MAX_CHILD_SIZE(f->b_size) - get_dc_child_size (B_N_CHILD(f,order)));
}


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

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

    if (f == r)
	order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) + 1;
    else {
	order = 0;
	f = r;
    }

    return (MAX_CHILD_SIZE(f->b_size) - get_dc_child_size (B_N_CHILD(f,order)));

}


/* Check whether left neighbor is in memory. */
static int  is_left_neighbor_in_cache (struct tree_balance * p_s_tb,
				       int n_h)
{
    struct buffer_head  * p_s_father;
    reiserfs_filsys_t * fs = p_s_tb->tb_fs;
    unsigned long         n_left_neighbor_blocknr;
    int                   n_left_neighbor_position;

    if ( ! p_s_tb->FL[n_h] ) /* Father of the left neighbor does not exist. */
	return 0;

    /* Calculate father of the node to be balanced. */
    p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
    /* Get position of the pointer to the left neighbor into the left father. */
    n_left_neighbor_position = ( p_s_father == p_s_tb->FL[n_h] ) ?
	p_s_tb->lkey[n_h] : get_blkh_nr_items (B_BLK_HEAD(p_s_tb->FL[n_h]));
    /* Get left neighbor block number. */
    n_left_neighbor_blocknr = get_dc_child_blocknr (B_N_CHILD (p_s_tb->FL[n_h], n_left_neighbor_position));
    /* Look for the left neighbor in the cache. */
    if ( (p_s_father = find_buffer(fs->fs_dev, n_left_neighbor_blocknr, fs->fs_blocksize)) )
	return 1;

    return 0;
}


#define LEFT_PARENTS  'l'
#define RIGHT_PARENTS 'r'



void init_path (struct path * path)
{
    path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}


/* Calculate far left/right parent of the left/right neighbor of the current node, that
 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
 * Calculate left/right common parent of the current node and L[h]/R[h].
 * Calculate left/right delimiting key position.
 * Returns:	PATH_INCORRECT   - path in the tree is not correct;
 		SCHEDULE_OCCURRED - schedule occured while the function worked;
 *	        CARRY_ON         - schedule didn't occur while the function worked;
 */
static int get_far_parent (struct tree_balance *   p_s_tb,
			   int n_h,
			   struct buffer_head  **  pp_s_father,
			   struct buffer_head  **  pp_s_com_father,
			   char c_lr_par)
{
    struct buffer_head  * p_s_parent;
    struct path         	s_path_to_neighbor_father,
	* p_s_path = p_s_tb->tb_path;
    struct key		s_lr_father_key;
    int                   n_counter,
	n_position = -1,
	n_first_last_position = 0,
	n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
    
    /* Starting from F[n_h] go upwards in the tree, and look for the common
       ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
    
    n_counter = n_path_offset;
    
    for ( ; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--  )  {
	/* Check whether parent of the current buffer in the path is really parent in the tree. */
	if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)) )
	    reiserfs_panic ("get_far_parent: buffer of path is notin the tree");

	/* Check whether position in the parent is correct. */
	if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_counter - 1)) > B_NR_ITEMS(p_s_parent) )
	    reiserfs_panic ("get_far_parent: incorrect position in the parent");

	/* Check whether parent at the path really points to the child. */
	if ( get_dc_child_blocknr (B_N_CHILD (p_s_parent, n_position)) !=
	     PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr )
	    reiserfs_panic ("get_far_parent: incorrect disk child in the parent");

	/* Return delimiting key if position in the parent is not equal to first/last one. */
	if ( c_lr_par == RIGHT_PARENTS )
	    n_first_last_position = get_blkh_nr_items (B_BLK_HEAD(p_s_parent));
	if ( n_position != n_first_last_position ) {
	    (*pp_s_com_father = p_s_parent)->b_count++;
	    break;
	}
    }
    
    /* we are in the root of the tree. */
    if ( n_counter == FIRST_PATH_ELEMENT_OFFSET ) {
	struct reiserfs_super_block * sb;

	sb = p_s_tb->tb_fs->fs_ondisk_sb;

	/* Check whether first buffer in the path is the root of the tree. */
	if ( PATH_OFFSET_PBUFFER(p_s_tb->tb_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
	     get_sb_root_block (sb) ) {
	    *pp_s_father = *pp_s_com_father = NULL;
	    return CARRY_ON;
	}
	reiserfs_panic ("get_far_parent: root not found in the path");
    }
    
    if (n_position == -1)
	reiserfs_panic ("get_far_parent: position is not defined");

    /* So, we got common parent of the current node and its left/right
       neighbor.  Now we are geting the parent of the left/right neighbor. */

    /* Form key to get parent of the left/right neighbor. */
    copy_key(&s_lr_father_key, B_N_PDELIM_KEY(*pp_s_com_father, ( c_lr_par == LEFT_PARENTS ) ?
					      (p_s_tb->lkey[n_h - 1] = n_position - 1) : (p_s_tb->rkey[n_h - 1] = n_position)));

    if ( c_lr_par == LEFT_PARENTS ) {
	//reiserfs_warning ("decrememnting key %k\n", &s_lr_father_key);
	decrement_key(&s_lr_father_key);
	//reiserfs_warning ("done: %k\n", &s_lr_father_key);
    }

    init_path (&s_path_to_neighbor_father);
    
    if (search_by_key(p_s_tb->tb_fs, &s_lr_father_key, &s_path_to_neighbor_father, n_h + 1) == IO_ERROR)
	return IO_ERROR;
    
    *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
    s_path_to_neighbor_father.path_length--;
    pathrelse (&s_path_to_neighbor_father);
    //decrement_counters_in_path(&s_path_to_neighbor_father);
    return CARRY_ON;
}


/* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
 * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
 * Returns:	SCHEDULE_OCCURRED - schedule occured while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 */
static int  get_parents (struct tree_balance * p_s_tb, int n_h)
{
    struct path         * p_s_path = p_s_tb->tb_path;
    int                   n_position,
	n_ret_value,
	n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
    struct buffer_head  * p_s_curf,
	* p_s_curcf;

    /* Current node is the root of the tree or will be root of the tree */
    if ( n_path_offset <= FIRST_PATH_ELEMENT_OFFSET ) {
	/* The root can not have parents.
	   Release nodes which previously were obtained as parents of the current node neighbors. */
	brelse(p_s_tb->FL[n_h]);
	brelse(p_s_tb->CFL[n_h]);
	brelse(p_s_tb->FR[n_h]);
	brelse(p_s_tb->CFR[n_h]);
	//decrement_bcount(p_s_tb->FL[n_h]);
	//decrement_bcount(p_s_tb->CFL[n_h]);
	//decrement_bcount(p_s_tb->FR[n_h]);
	//decrement_bcount(p_s_tb->CFR[n_h]);
	p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] = p_s_tb->CFR[n_h] = NULL;
	return CARRY_ON;
    }
  
    /* Get parent FL[n_path_offset] of L[n_path_offset]. */
    if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1)) )  {
	/* Current node is not the first child of its parent. */
	(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;
	p_s_tb->lkey[n_h] = n_position - 1;
    }
    else  {
	/* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
	   Calculate current common parent of L[n_path_offset] and the current node. Note that
	   CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
	   Calculate lkey[n_path_offset]. */
	if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
					   &p_s_curcf, LEFT_PARENTS)) != CARRY_ON )
	    return n_ret_value; /*schedule() occured or path is not correct*/
    }

    brelse(p_s_tb->FL[n_h]);	
    p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
 
    brelse(p_s_tb->CFL[n_h]);
    p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */

/* Get parent FR[n_h] of R[n_h]. */

/* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
    if ( n_position == get_blkh_nr_items (B_BLK_HEAD(PATH_H_PBUFFER(p_s_path, n_h + 1))) ) {
/* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
   Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
   not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
	if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,  &p_s_curcf, RIGHT_PARENTS)) != CARRY_ON )
	    return n_ret_value; /*schedule() occured while get_far_parent() worked.*/
    }
    else {
/* Current node is not the last child of its parent F[n_h]. */
	(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;
	p_s_tb->rkey[n_h] = n_position;
    }	

    brelse/*decrement_bcount*/(p_s_tb->FR[n_h]);
    p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */

    brelse/*decrement_bcount*/(p_s_tb->CFR[n_h]);
    p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */

    return CARRY_ON; /* schedule not occured while get_parents() worked. */
}


/* it is possible to remove node as result of shiftings to
   neighbors even when we insert or paste item. */
static inline int can_node_be_removed (int mode, int lfree, int sfree, int rfree, struct tree_balance * tb, int h)
{
    struct buffer_head * Sh = PATH_H_PBUFFER (tb->tb_path, h);
    int levbytes = tb->insert_size[h];
    struct item_head * r_ih = NULL;
  
    if ( tb->CFR[h] )
	r_ih = (struct item_head *)B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]);
  
    if (lfree + rfree + sfree < (int)(MAX_CHILD_SIZE(Sh->b_size) + levbytes
	/* shifting may merge items which might save space */
	- (( ! h && is_left_mergeable (tb->tb_fs, tb->tb_path) == 1 ) ? IH_SIZE : 0)
	- (( ! h && r_ih && is_right_mergeable (tb->tb_fs, tb->tb_path) == 1 ) ? IH_SIZE : 0)
	+ (( h ) ? KEY_SIZE : 0)))
    {
	/* node can not be removed */
	if (sfree >= levbytes ) /* new item fits into node S[h] without any shifting */
	{
	    if ( ! h )
		tb->s0num = B_NR_ITEMS(Sh) + ((mode == M_INSERT ) ? 1 : 0);
	    set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
	    return NO_BALANCING_NEEDED;
	}
    }
    return !NO_BALANCING_NEEDED;
}



/* Check whether current node S[h] is balanced when increasing its size by
 * Inserting or Pasting.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste;
 * Returns:	1 - schedule occured; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
/* ip means Inserting or Pasting */
static int ip_check_balance (/*struct reiserfs_transaction_handle *th,*/ struct tree_balance * tb, int h)
{
    struct virtual_node * vn = tb->tb_vn;
    int levbytes,  /* Number of bytes that must be inserted into (value is
		      negative if bytes are deleted) buffer which contains
		      node being balanced.  The mnemonic is that the attempted
		      change in node space used level is levbytes bytes. */
	n_ret_value;
    
    int lfree, sfree, rfree /* free space in L, S and R */;

    /* nver is short for number of vertices, and lnver is the number if we
       shift to the left, rnver is the number if we shift to the right, and
       lrnver is the number if we shift in both directions.  The goal is to
       minimize first the number of vertices, and second, the number of
       vertices whose contents are changed by shifting, and third the number
       of uncached vertices whose contents are changed by shifting and must be
       read from disk.  */
    int nver, lnver, rnver, lrnver;

    /* used at leaf level only, S0 = S[0] is the node being balanced, sInum [
       I = 0,1,2 ] is the number of items that will remain in node SI after
       balancing.  S1 and S2 are new nodes that might be created. */
  
    /* we perform 8 calls to get_num_ver().  For each call we calculate five
     parameters.  where 4th parameter is s1bytes and 5th - s2bytes */
    short snum012[40] = {0,};	/* s0num, s1num, s2num for 8 cases 
				   0,1 - do not shift and do not shift but bottle
				   2 - shift only whole item to left
				   3 - shift to left and bottle as much as possible
				   4,5 - shift to right	(whole items and as much as possible
				   6,7 - shift to both directions (whole items and as much as possible)
				   */

    /* Sh is the node whose balance is currently being checked */
    struct buffer_head * Sh;
  
    /* special mode for insert pointer to the most low internal node */
    if (h == 0 && vn->vn_mode == M_INTERNAL) {
	/* blk_num == 2 is to get pointer inserted to the next level */
	set_parameters (tb, h, 0, 0, 2, NULL, -1, -1);
	return 0;
    }

    Sh = PATH_H_PBUFFER (tb->tb_path, h);
    levbytes = tb->insert_size[h];
    
    /* Calculate balance parameters for creating new root. */
    if ( ! Sh )  {
	if ( ! h )
	    reiserfs_panic ("vs-8210: ip_check_balance: S[0] can not be 0");
	switch ( n_ret_value = get_empty_nodes (tb, h) )  {
	case CARRY_ON:
	    set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
	    return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
	    
	case NO_DISK_SPACE:
	    return n_ret_value;

	default:   
	    reiserfs_panic("vs-8215: ip_check_balance: incorrect return value of get_empty_nodes");
	}
    }
    
    if ( (n_ret_value = get_parents (tb, h)) != CARRY_ON ) /* get parents of S[h] neighbors. */
	return n_ret_value;
    
    sfree = get_blkh_free_space (B_BLK_HEAD(Sh));
    
    /* get free space of neighbors */
    rfree = get_rfree (tb, h);
    lfree = get_lfree (tb, h);
    
    if (can_node_be_removed (vn->vn_mode, lfree, sfree, rfree, tb, h) == NO_BALANCING_NEEDED)
	/* and new item fits into node S[h] without any shifting */
	return NO_BALANCING_NEEDED;
    
    create_virtual_node (tb, h);
    
     /* determine maximal number of items we can shift to the left neighbor
	(in tb structure) and the maximal number of bytes that can flow to the
	left neighbor from the left most liquid item that cannot be shifted
	from S[0] entirely (returned value) */
    check_left (tb, h, lfree);
    
    /* determine maximal number of items we can shift to the right neighbor
       (in tb structure) and the maximal number of bytes that can flow to the
       right neighbor from the right most liquid item that cannot be shifted
       from S[0] entirely (returned value) */
    check_right (tb, h, rfree);
    

    /* all contents of internal node S[h] can be moved into its neighbors,
       S[h] will be removed after balancing */
    if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
	int to_r;