fix_node.c

linux 内核源代码

	/* 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;

	/* No need to check quota - is not allocated for blocks used for formatted nodes */
	if (reiserfs_new_form_blocknrs(p_s_tb, a_n_blocknrs,
				       n_amount_needed) == NO_DISK_SPACE)
		return NO_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++) {

		RFALSE(!*p_n_blocknr,
		       "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");

		p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr);
		RFALSE(buffer_dirty(p_s_new_bh) ||
		       buffer_journaled(p_s_new_bh) ||
		       buffer_journal_dirty(p_s_new_bh),
		       "PAP-8140: journlaled or dirty buffer %b for the new block",
		       p_s_new_bh);

		/* Put empty buffers into the array. */
		RFALSE(p_s_tb->FEB[p_s_tb->cur_blknum],
		       "PAP-8141: busy slot for new buffer");

		set_buffer_journal_new(p_s_new_bh);
		p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
	}

	if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(p_s_tb))
		n_retval = REPEAT_SEARCH;

	return n_retval;
}

/* 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 {
		order = B_NR_ITEMS(l);
		f = l;
	}

	return (MAX_CHILD_SIZE(f) - dc_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) - dc_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, *left;
	struct super_block *p_s_sb = p_s_tb->tb_sb;
	b_blocknr_t 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);

	RFALSE(!p_s_father ||
	       !B_IS_IN_TREE(p_s_father) ||
	       !B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
	       !buffer_uptodate(p_s_father) ||
	       !buffer_uptodate(p_s_tb->FL[n_h]),
	       "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
	       p_s_father, p_s_tb->FL[n_h]);

	/* 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] : B_NR_ITEMS(p_s_tb->FL[n_h]);
	/* Get left neighbor block number. */
	n_left_neighbor_blocknr =
	    B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
	/* Look for the left neighbor in the cache. */
	if ((left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr))) {

		RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
		       "vs-8170: left neighbor (%b %z) is not in the tree",
		       left, left);
		put_bh(left);
		return 1;
	}

	return 0;
}

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

static void decrement_key(struct cpu_key *p_s_key)
{
	// call item specific function for this key
	item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key);
}

/* 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 occurred 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;
	INITIALIZE_PATH(s_path_to_neighbor_father);
	struct treepath *p_s_path = p_s_tb->tb_path;
	struct cpu_key s_lr_father_key;
	int n_counter,
	    n_position = INT_MAX,
	    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;

	RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-8180: invalid path length");

	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)))
			return REPEAT_SEARCH;
		/* 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))
			return REPEAT_SEARCH;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(p_s_parent, n_position) !=
		    PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr)
			return REPEAT_SEARCH;
		/* 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 = B_NR_ITEMS(p_s_parent);
		if (n_position != n_first_last_position) {
			*pp_s_com_father = p_s_parent;
			get_bh(*pp_s_com_father);
			/*(*pp_s_com_father = p_s_parent)->b_count++; */
			break;
		}
	}

	/* if we are in the root of the tree, then there is no common father */
	if (n_counter == FIRST_PATH_ELEMENT_OFFSET) {
		/* 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 ==
		    SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
			*pp_s_father = *pp_s_com_father = NULL;
			return CARRY_ON;
		}
		return REPEAT_SEARCH;
	}

	RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
	       "PAP-8185: (%b %z) level too small",
	       *pp_s_com_father, *pp_s_com_father);

	/* Check whether the common parent is locked. */

	if (buffer_locked(*pp_s_com_father)) {
		__wait_on_buffer(*pp_s_com_father);
		if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
			decrement_bcount(*pp_s_com_father);
			return REPEAT_SEARCH;
		}
	}

	/* 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. */
	le_key2cpu_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)
		decrement_key(&s_lr_father_key);

	if (search_by_key
	    (p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
	     n_h + 1) == IO_ERROR)
		// path is released
		return IO_ERROR;

	if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
		decrement_counters_in_path(&s_path_to_neighbor_father);
		decrement_bcount(*pp_s_com_father);
		return REPEAT_SEARCH;
	}

	*pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);

	RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
	       "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
	RFALSE(s_path_to_neighbor_father.path_length <
	       FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");

	s_path_to_neighbor_father.path_length--;
	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 occurred 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 treepath *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. */
		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_curf = p_s_curcf =
		    PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
		get_bh(p_s_curf);
		get_bh(p_s_curf);
		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;
	}

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

	RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
	       (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
	       "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);

/* 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 == B_NR_ITEMS(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;
	} 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_curf = p_s_curcf =
		    PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
		get_bh(p_s_curf);
		get_bh(p_s_curf);
		p_s_tb->rkey[n_h] = n_position;
	}

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

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

	RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
	       (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
	       "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);

	return CARRY_ON;
}

/* 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 *ih;
	struct reiserfs_key *r_key = NULL;

	ih = B_N_PITEM_HEAD(Sh, 0);
	if (tb->CFR[h])
		r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);

	if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
	    /* shifting may merge items which might save space */
	    -
	    ((!h
	      && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
	    -
	    ((!h && r_key
	      && op_is_left_mergeable(r_key, Sh->b_size)) ? 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;
		}
	}
	PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
	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 occurred; 
 *	        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 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