fix_node.c

linux 内核源代码

				order_R =
				    ((n =
				      PATH_H_B_ITEM_ORDER(tb->tb_path,
							  h)) ==
				     B_NR_ITEMS(Fh)) ? 0 : n + 1;
				n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
				    (DC_SIZE + KEY_SIZE);
				set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
					       -1);
				return CARRY_ON;
			}
		}

		if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
			/* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
			int to_r;

			to_r =
			    ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
			     tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
			    (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
			set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
				       0, NULL, -1, -1);
			return CARRY_ON;
		}

		/* Balancing does not lead to better packing. */
		set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
		return NO_BALANCING_NEEDED;
	}

	/* Current node contain insufficient number of items. Balancing is required. */
	/* Check whether we can merge S[h] with left neighbor. */
	if (tb->lnum[h] >= vn->vn_nr_item + 1)
		if (is_left_neighbor_in_cache(tb, h)
		    || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
			int n;
			int order_L;

			order_L =
			    ((n =
			      PATH_H_B_ITEM_ORDER(tb->tb_path,
						  h)) ==
			     0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
			n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
								      KEY_SIZE);
			set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
			return CARRY_ON;
		}

	/* Check whether we can merge S[h] with right neighbor. */
	if (tb->rnum[h] >= vn->vn_nr_item + 1) {
		int n;
		int order_R;

		order_R =
		    ((n =
		      PATH_H_B_ITEM_ORDER(tb->tb_path,
					  h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
		n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
							      KEY_SIZE);
		set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
		return CARRY_ON;
	}

	/* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
	if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
		int to_r;

		to_r =
		    ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
		     vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
						tb->rnum[h]);
		set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
			       -1, -1);
		return CARRY_ON;
	}

	/* For internal nodes try to borrow item from a neighbor */
	RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");

	/* Borrow one or two items from caching neighbor */
	if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
		int from_l;

		from_l =
		    (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
		     1) / 2 - (vn->vn_nr_item + 1);
		set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
		return CARRY_ON;
	}

	set_parameters(tb, h, 0,
		       -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
			  1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
	return CARRY_ON;
}

/* Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Truncating for LEAF node of S+tree.
 * 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 occurred; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int dc_check_balance_leaf(struct tree_balance *tb, int h)
{
	struct virtual_node *vn = tb->tb_vn;

	/* Number of bytes that must be deleted from
	   (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. */
	int levbytes;
	/* the maximal item size */
	int maxsize, n_ret_value;
	/* S0 is the node whose balance is currently being checked,
	   and F0 is its father.  */
	struct buffer_head *S0, *F0;
	int lfree, rfree /* free space in L and R */ ;

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

	levbytes = tb->insert_size[h];

	maxsize = MAX_CHILD_SIZE(S0);	/* maximal possible size of an item */

	if (!F0) {		/* S[0] is the root now. */

		RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
		       "vs-8240: attempt to create empty buffer tree");

		set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
		return NO_BALANCING_NEEDED;
	}

	if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
		return n_ret_value;

	/* get free space of neighbors */
	rfree = get_rfree(tb, h);
	lfree = get_lfree(tb, h);

	create_virtual_node(tb, h);

	/* if 3 leaves can be merge to one, set parameters and return */
	if (are_leaves_removable(tb, lfree, rfree))
		return CARRY_ON;

	/* determine maximal number of items we can shift to the left/right  neighbor
	   and the maximal number of bytes that can flow to the left/right neighbor
	   from the left/right most liquid item that cannot be shifted from S[0] entirely
	 */
	check_left(tb, h, lfree);
	check_right(tb, h, rfree);

	/* check whether we can merge S with left neighbor. */
	if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
		if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) ||	/* S can not be merged with R */
		    !tb->FR[h]) {

			RFALSE(!tb->FL[h],
			       "vs-8245: dc_check_balance_leaf: FL[h] must exist");

			/* set parameter to merge S[0] with its left neighbor */
			set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
			return CARRY_ON;
		}

	/* check whether we can merge S[0] with right neighbor. */
	if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
		set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
		return CARRY_ON;
	}

	/* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
	if (is_leaf_removable(tb))
		return CARRY_ON;

	/* Balancing is not required. */
	tb->s0num = vn->vn_nr_item;
	set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
	return NO_BALANCING_NEEDED;
}

/* Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Cutting.
 * 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	d - delete, c - cut.
 * Returns:	1 - schedule occurred; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int dc_check_balance(struct tree_balance *tb, int h)
{
	RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
	       "vs-8250: S is not initialized");

	if (h)
		return dc_check_balance_internal(tb, h);
	else
		return dc_check_balance_leaf(tb, h);
}

/* Check whether current node S[h] is balanced.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *
 *	tb	tree_balance structure:
 *
 *              tb is a large structure that must be read about in the header file
 *              at the same time as this procedure if the reader is to successfully
 *              understand this procedure
 *
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste, d - delete, c - cut.
 * Returns:	1 - schedule occurred; 
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int check_balance(int mode,
			 struct tree_balance *tb,
			 int h,
			 int inum,
			 int pos_in_item,
			 struct item_head *ins_ih, const void *data)
{
	struct virtual_node *vn;

	vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
	vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
	vn->vn_mode = mode;
	vn->vn_affected_item_num = inum;
	vn->vn_pos_in_item = pos_in_item;
	vn->vn_ins_ih = ins_ih;
	vn->vn_data = data;

	RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
	       "vs-8255: ins_ih can not be 0 in insert mode");

	if (tb->insert_size[h] > 0)
		/* Calculate balance parameters when size of node is increasing. */
		return ip_check_balance(tb, h);

	/* Calculate balance parameters when  size of node is decreasing. */
	return dc_check_balance(tb, h);
}

/* Check whether parent at the path is the really parent of the current node.*/
static int get_direct_parent(struct tree_balance *p_s_tb, int n_h)
{
	struct buffer_head *p_s_bh;
	struct treepath *p_s_path = p_s_tb->tb_path;
	int n_position,
	    n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);

	/* We are in the root or in the new root. */
	if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
		       "PAP-8260: invalid offset in the path");

		if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->
		    b_blocknr == SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
			/* Root is not changed. */
			PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
			PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
			return CARRY_ON;
		}
		return REPEAT_SEARCH;	/* Root is changed and we must recalculate the path. */
	}

	if (!B_IS_IN_TREE
	    (p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)))
		return REPEAT_SEARCH;	/* Parent in the path is not in the tree. */

	if ((n_position =
	     PATH_OFFSET_POSITION(p_s_path,
				  n_path_offset - 1)) > B_NR_ITEMS(p_s_bh))
		return REPEAT_SEARCH;

	if (B_N_CHILD_NUM(p_s_bh, n_position) !=
	    PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr)
		/* Parent in the path is not parent of the current node in the tree. */
		return REPEAT_SEARCH;

	if (buffer_locked(p_s_bh)) {
		__wait_on_buffer(p_s_bh);
		if (FILESYSTEM_CHANGED_TB(p_s_tb))
			return REPEAT_SEARCH;
	}

	return CARRY_ON;	/* Parent in the path is unlocked and really parent of the current node.  */
}

/* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
 * of S[n_h] we
 * need in order to balance S[n_h], and get them if necessary.
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 */
static int get_neighbors(struct tree_balance *p_s_tb, int n_h)
{
	int n_child_position,
	    n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
	unsigned long n_son_number;
	struct super_block *p_s_sb = p_s_tb->tb_sb;
	struct buffer_head *p_s_bh;

	PROC_INFO_INC(p_s_sb, get_neighbors[n_h]);

	if (p_s_tb->lnum[n_h]) {
		/* We need left neighbor to balance S[n_h]. */
		PROC_INFO_INC(p_s_sb, need_l_neighbor[n_h]);
		p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);

		RFALSE(p_s_bh == p_s_tb->FL[n_h] &&
		       !PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
		       "PAP-8270: invalid position in the parent");

		n_child_position =
		    (p_s_bh ==
		     p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->
								       FL[n_h]);
		n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
		p_s_bh = sb_bread(p_s_sb, n_son_number);
		if (!p_s_bh)
			return IO_ERROR;
		if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
			decrement_bcount(p_s_bh);
			PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
			return REPEAT_SEARCH;
		}

		RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
		       n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
		       B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
		       p_s_bh->b_blocknr, "PAP-8275: invalid parent");
		RFALSE(!B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child");
		RFALSE(!n_h &&
		       B_FREE_SPACE(p_s_bh) !=
		       MAX_CHILD_SIZE(p_s_bh) -
		       dc_size(B_N_CHILD(p_s_tb->FL[0], n_child_position)),
		       "PAP-8290: invalid child size of left neighbor");

		decrement_bcount(p_s_tb->L[n_h]);
		p_s_tb->L[n_h] = p_s_bh;
	}

	if (p_s_tb->rnum[n_h]) {	/* We need right neighbor to balance S[n_path_offset]. */
		PROC_INFO_INC(p_s_sb, need_r_neighbor[n_h]);
		p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);

		RFALSE(p_s_bh == p_s_tb->FR[n_h] &&
		       PATH_OFFSET_POSITION(p_s_tb->tb_path,
					    n_path_offset) >=
		       B_NR_ITEMS(p_s_bh),
		       "PAP-8295: invalid position in the parent");

		n_child_position =
		    (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0;
		n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
		p_s_bh = sb_bread(p_s_sb, n_son_number);
		if (!p_s_bh)
			return IO_ERROR;
		if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
			decrement_bcount(p_s_bh);
			PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
			return REPEAT_SEARCH;
		}
		decrement_bcount(p_s_tb->R[n_h]);
		p_s_tb->R[n_h] = p_s_bh;

		RFALSE(!n_h
		       && B_FREE_SPACE(p_s_bh) !=
		       MAX_CHILD_SIZE(p_s_bh) -
		       dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)),
		       "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
		       B_FREE_SPACE(p_s_bh), MAX_CHILD_SIZE(p_s_bh),
		       dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)));

	}
	return CARRY_ON;
}

static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
{
	int max_num_of_items;
	int max_num_of_entries;