ti-processor-sdk-linux/fs/reiserfs/fix_node.c

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

#include <linux/time.h>
#include <linux/slab.h>
#include <linux/string.h>
#include "reiserfs.h"
#include <linux/buffer_head.h>

/*
 * To make any changes in the tree we find a node that contains item
 * to be changed/deleted or position in the node we insert a new item
 * to. We call this node S. To do balancing we need to decide what we
 * will shift to left/right neighbor, or to a new node, where new item
 * will be etc. To make this analysis simpler we build virtual
 * node. Virtual node is an array of items, that will replace items of
 * node S. (For instance if we are going to delete an item, virtual
 * node does not contain it). Virtual node keeps information about
 * item sizes and types, mergeability of first and last items, sizes
 * of all entries in directory item. We use this array of items when
 * calculating what we can shift to neighbors and how many nodes we
 * have to have if we do not any shiftings, if we shift to left/right
 * neighbor or to both.
 */

/*
 * Takes item number in virtual node, returns number of item
 * that it has in source buffer
 */
static inline int old_item_num(int new_num, int affected_item_num, int mode)
{
	if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
		return new_num;

	if (mode == M_INSERT) {

		RFALSE(new_num == 0,
		       "vs-8005: for INSERT mode and item number of inserted item");

		return new_num - 1;
	}

	RFALSE(mode != M_DELETE,
	       "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
	       mode);
	/* delete mode */
	return new_num + 1;
}

static void create_virtual_node(struct tree_balance *tb, int h)
{
	struct item_head *ih;
	struct virtual_node *vn = tb->tb_vn;
	int new_num;
	struct buffer_head *Sh;	/* this comes from tb->S[h] */

	Sh = PATH_H_PBUFFER(tb->tb_path, h);

	/* size of changed node */
	vn->vn_size =
	    MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];

	/* for internal nodes array if virtual items is not created */
	if (h) {
		vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
		return;
	}

	/* number of items in virtual node  */
	vn->vn_nr_item =
	    B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
	    ((vn->vn_mode == M_DELETE) ? 1 : 0);

	/* first virtual item */
	vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
	memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
	vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);

	/* first item in the node */
	ih = item_head(Sh, 0);

	/* define the mergeability for 0-th item (if it is not being deleted) */
	if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size)
	    && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
		vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;

	/*
	 * go through all items that remain in the virtual
	 * node (except for the new (inserted) one)
	 */
	for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
		int j;
		struct virtual_item *vi = vn->vn_vi + new_num;
		int is_affected =
		    ((new_num != vn->vn_affected_item_num) ? 0 : 1);

		if (is_affected && vn->vn_mode == M_INSERT)
			continue;

		/* get item number in source node */
		j = old_item_num(new_num, vn->vn_affected_item_num,
				 vn->vn_mode);

		vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
		vi->vi_ih = ih + j;
		vi->vi_item = ih_item_body(Sh, ih + j);
		vi->vi_uarea = vn->vn_free_ptr;

		/*
		 * FIXME: there is no check that item operation did not
		 * consume too much memory
		 */
		vn->vn_free_ptr +=
		    op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
		if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
			reiserfs_panic(tb->tb_sb, "vs-8030",
				       "virtual node space consumed");

		if (!is_affected)
			/* this is not being changed */
			continue;

		if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
			vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
			/* pointer to data which is going to be pasted */
			vi->vi_new_data = vn->vn_data;
		}
	}

	/* virtual inserted item is not defined yet */
	if (vn->vn_mode == M_INSERT) {
		struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;

		RFALSE(vn->vn_ins_ih == NULL,
		       "vs-8040: item header of inserted item is not specified");
		vi->vi_item_len = tb->insert_size[0];
		vi->vi_ih = vn->vn_ins_ih;
		vi->vi_item = vn->vn_data;
		vi->vi_uarea = vn->vn_free_ptr;

		op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
			     tb->insert_size[0]);
	}

	/*
	 * set right merge flag we take right delimiting key and
	 * check whether it is a mergeable item
	 */
	if (tb->CFR[0]) {
		struct reiserfs_key *key;

		key = internal_key(tb->CFR[0], tb->rkey[0]);
		if (op_is_left_mergeable(key, Sh->b_size)
		    && (vn->vn_mode != M_DELETE
			|| vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
			vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
			    VI_TYPE_RIGHT_MERGEABLE;

#ifdef CONFIG_REISERFS_CHECK
		if (op_is_left_mergeable(key, Sh->b_size) &&
		    !(vn->vn_mode != M_DELETE
		      || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
			/*
			 * we delete last item and it could be merged
			 * with right neighbor's first item
			 */
			if (!
			    (B_NR_ITEMS(Sh) == 1
			     && is_direntry_le_ih(item_head(Sh, 0))
			     && ih_entry_count(item_head(Sh, 0)) == 1)) {
				/*
				 * node contains more than 1 item, or item
				 * is not directory item, or this item
				 * contains more than 1 entry
				 */
				print_block(Sh, 0, -1, -1);
				reiserfs_panic(tb->tb_sb, "vs-8045",
					       "rdkey %k, affected item==%d "
					       "(mode==%c) Must be %c",
					       key, vn->vn_affected_item_num,
					       vn->vn_mode, M_DELETE);
			}
		}
#endif

	}
}

/*
 * Using virtual node check, how many items can be
 * shifted to left neighbor
 */
static void check_left(struct tree_balance *tb, int h, int cur_free)
{
	int i;
	struct virtual_node *vn = tb->tb_vn;
	struct virtual_item *vi;
	int d_size, ih_size;

	RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);

	/* internal level */
	if (h > 0) {
		tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
		return;
	}

	/* leaf level */

	if (!cur_free || !vn->vn_nr_item) {
		/* no free space or nothing to move */
		tb->lnum[h] = 0;
		tb->lbytes = -1;
		return;
	}

	RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
	       "vs-8055: parent does not exist or invalid");

	vi = vn->vn_vi;
	if ((unsigned int)cur_free >=
	    (vn->vn_size -
	     ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
		/* all contents of S[0] fits into L[0] */

		RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
		       "vs-8055: invalid mode or balance condition failed");

		tb->lnum[0] = vn->vn_nr_item;
		tb->lbytes = -1;
		return;
	}

	d_size = 0, ih_size = IH_SIZE;

	/* first item may be merge with last item in left neighbor */
	if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
		d_size = -((int)IH_SIZE), ih_size = 0;

	tb->lnum[0] = 0;
	for (i = 0; i < vn->vn_nr_item;
	     i++, ih_size = IH_SIZE, d_size = 0, vi++) {
		d_size += vi->vi_item_len;
		if (cur_free >= d_size) {
			/* the item can be shifted entirely */
			cur_free -= d_size;
			tb->lnum[0]++;
			continue;
		}

		/* the item cannot be shifted entirely, try to split it */
		/*
		 * check whether L[0] can hold ih and at least one byte
		 * of the item body
		 */

		/* cannot shift even a part of the current item */
		if (cur_free <= ih_size) {
			tb->lbytes = -1;
			return;
		}
		cur_free -= ih_size;

		tb->lbytes = op_check_left(vi, cur_free, 0, 0);
		if (tb->lbytes != -1)
			/* count partially shifted item */
			tb->lnum[0]++;

		break;
	}

	return;
}

/*
 * Using virtual node check, how many items can be
 * shifted to right neighbor
 */
static void check_right(struct tree_balance *tb, int h, int cur_free)
{
	int i;
	struct virtual_node *vn = tb->tb_vn;
	struct virtual_item *vi;
	int d_size, ih_size;

	RFALSE(cur_free < 0, "vs-8070: cur_free < 0");

	/* internal level */
	if (h > 0) {
		tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
		return;
	}

	/* leaf level */

	if (!cur_free || !vn->vn_nr_item) {
		/* no free space  */
		tb->rnum[h] = 0;
		tb->rbytes = -1;
		return;
	}

	RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
	       "vs-8075: parent does not exist or invalid");

	vi = vn->vn_vi + vn->vn_nr_item - 1;
	if ((unsigned int)cur_free >=
	    (vn->vn_size -
	     ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
		/* all contents of S[0] fits into R[0] */

		RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
		       "vs-8080: invalid mode or balance condition failed");

		tb->rnum[h] = vn->vn_nr_item;
		tb->rbytes = -1;
		return;
	}

	d_size = 0, ih_size = IH_SIZE;

	/* last item may be merge with first item in right neighbor */
	if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
		d_size = -(int)IH_SIZE, ih_size = 0;

	tb->rnum[0] = 0;
	for (i = vn->vn_nr_item - 1; i >= 0;
	     i--, d_size = 0, ih_size = IH_SIZE, vi--) {
		d_size += vi->vi_item_len;
		if (cur_free >= d_size) {
			/* the item can be shifted entirely */
			cur_free -= d_size;
			tb->rnum[0]++;
			continue;
		}

		/*
		 * check whether R[0] can hold ih and at least one
		 * byte of the item body
		 */

		/* cannot shift even a part of the current item */
		if (cur_free <= ih_size) {
			tb->rbytes = -1;
			return;
		}

		/*
		 * R[0] can hold the header of the item and at least
		 * one byte of its body
		 */
		cur_free -= ih_size;	/* cur_free is still > 0 */

		tb->rbytes = op_check_right(vi, cur_free);
		if (tb->rbytes != -1)
			/* count partially shifted item */
			tb->rnum[0]++;

		break;
	}

	return;
}

/*
 * from - number of items, which are shifted to left neighbor entirely
 * to - number of item, which are shifted to right neighbor entirely
 * from_bytes - number of bytes of boundary item (or directory entries)
 *              which are shifted to left neighbor
 * to_bytes - number of bytes of boundary item (or directory entries)
 *            which are shifted to right neighbor
 */
static int get_num_ver(int mode, struct tree_balance *tb, int h,
		       int from, int from_bytes,
		       int to, int to_bytes, short *snum012, int flow)
{
	int i;
	int cur_free;
	int units;
	struct virtual_node *vn = tb->tb_vn;
	int total_node_size, max_node_size, current_item_size;
	int needed_nodes;

	/* position of item we start filling node from */
	int start_item;

	/* position of item we finish filling node by */
	int end_item;

	/*
	 * number of first bytes (entries for directory) of start_item-th item
	 * we do not include into node that is being filled
	 */
	int start_bytes;

	/*
	 * number of last bytes (entries for directory) of end_item-th item
	 * we do node include into node that is being filled
	 */
	int end_bytes;

	/*
	 * these are positions in virtual item of items, that are split
	 * between S[0] and S1new and S1new and S2new
	 */
	int split_item_positions[2];

	split_item_positions[0] = -1;
	split_item_positions[1] = -1;

	/*
	 * We only create additional nodes if we are in insert or paste mode
	 * or we are in replace mode at the internal level. If h is 0 and
	 * the mode is M_REPLACE then in fix_nodes we change the mode to
	 * paste or insert before we get here in the code.
	 */
	RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
	       "vs-8100: insert_size < 0 in overflow");

	max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));

	/*
	 * snum012 [0-2] - number of items, that lay
	 * to S[0], first new node and second new node
	 */
	snum012[3] = -1;	/* s1bytes */
	snum012[4] = -1;	/* s2bytes */

	/* internal level */
	if (h > 0) {
		i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
		if (i == max_node_size)
			return 1;
		return (i / max_node_size + 1);
	}

	/* leaf level */
	needed_nodes = 1;
	total_node_size = 0;
	cur_free = max_node_size;

	/* start from 'from'-th item */
	start_item = from;
	/* skip its first 'start_bytes' units */
	start_bytes = ((from_bytes != -1) ? from_bytes : 0);

	/* last included item is the 'end_item'-th one */
	end_item = vn->vn_nr_item - to - 1;
	/* do not count last 'end_bytes' units of 'end_item'-th item */
	end_bytes = (to_bytes != -1) ? to_bytes : 0;

	/*
	 * go through all item beginning from the start_item-th item
	 * and ending by the end_item-th item. Do not count first
	 * 'start_bytes' units of 'start_item'-th item and last
	 * 'end_bytes' of 'end_item'-th item
	 */
	for (i = start_item; i <= end_item; i++) {
		struct virtual_item *vi = vn->vn_vi + i;
		int skip_from_end = ((i == end_item) ? end_bytes : 0);

		RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");

		/* get size of current item */
		current_item_size = vi->vi_item_len;

		/*
		 * do not take in calculation head part (from_bytes)
		 * of from-th item
		 */
		current_item_size -=
		    op_part_size(vi, 0 /*from start */ , start_bytes);

		/* do not take in calculation tail part of last item */
		current_item_size -=
		    op_part_size(vi, 1 /*from end */ , skip_from_end);

		/* if item fits into current node entierly */
		if (total_node_size + current_item_size <= max_node_size) {
			snum012[needed_nodes - 1]++;
			total_node_size += current_item_size;
			start_bytes = 0;
			continue;
		}

		/*
		 * virtual item length is longer, than max size of item in
		 * a node. It is impossible for direct item
		 */
		if (current_item_size > max_node_size) {
			RFALSE(is_direct_le_ih(vi->vi_ih),
			       "vs-8110: "
			       "direct item length is %d. It can not be longer than %d",
			       current_item_size, max_node_size);
			/* we will try to split it */
			flow = 1;
		}

		/* as we do not split items, take new node and continue */
		if (!flow) {
			needed_nodes++;
			i--;
			total_node_size = 0;
			continue;
		}

		/*
		 * calculate number of item units which fit into node being
		 * filled
		 */
		{
			int free_space;

			free_space = max_node_size - total_node_size - IH_SIZE;
			units =
			    op_check_left(vi, free_space, start_bytes,
					  skip_from_end);
			/*
			 * nothing fits into current node, take new
			 * node and continue
			 */
			if (units == -1) {
				needed_nodes++, i--, total_node_size = 0;
				continue;
			}
		}

		/* something fits into the current node */
		start_bytes += units;
		snum012[needed_nodes - 1 + 3] = units;

		if (needed_nodes > 2)
			reiserfs_warning(tb->tb_sb, "vs-8111",
					 "split_item_position is out of range");
		snum012[needed_nodes - 1]++;
		split_item_positions[needed_nodes - 1] = i;
		needed_nodes++;
		/* continue from the same item with start_bytes != -1 */
		start_item = i;
		i--;
		total_node_size = 0;
	}

	/*
	 * sum012[4] (if it is not -1) contains number of units of which
	 * are to be in S1new, snum012[3] - to be in S0. They are supposed
	 * to be S1bytes and S2bytes correspondingly, so recalculate
	 */
	if (snum012[4] > 0) {
		int split_item_num;
		int bytes_to_r, bytes_to_l;
		int bytes_to_S1new;

		split_item_num = split_item_positions[1];
		bytes_to_l =
		    ((from == split_item_num
		      && from_bytes != -1) ? from_bytes : 0);
		bytes_to_r =
		    ((end_item == split_item_num
		      && end_bytes != -1) ? end_bytes : 0);
		bytes_to_S1new =
		    ((split_item_positions[0] ==
		      split_item_positions[1]) ? snum012[3] : 0);

		/* s2bytes */
		snum012[4] =
		    op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
		    bytes_to_r - bytes_to_l - bytes_to_S1new;

		if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
		    vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
			reiserfs_warning(tb->tb_sb, "vs-8115",
					 "not directory or indirect item");
	}

	/* now we know S2bytes, calculate S1bytes */
	if (snum012[3] > 0) {
		int split_item_num;
		int bytes_to_r, bytes_to_l;
		int bytes_to_S2new;

		split_item_num = split_item_positions[0];
		bytes_to_l =
		    ((from == split_item_num
		      && from_bytes != -1) ? from_bytes : 0);
		bytes_to_r =
		    ((end_item == split_item_num
		      && end_bytes != -1) ? end_bytes : 0);
		bytes_to_S2new =
		    ((split_item_positions[0] == split_item_positions[1]
		      && snum012[4] != -1) ? snum012[4] : 0);

		/* s1bytes */
		snum012[3] =
		    op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
		    bytes_to_r - bytes_to_l - bytes_to_S2new;
	}

	return needed_nodes;
}


/*
 * Set parameters for balancing.
 * Performs write of results of analysis of balancing into structure tb,
 * where it will later be used by the functions that actually do the balancing.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	lnum	number of items from S[h] that must be shifted to L[h];
 *	rnum	number of items from S[h] that must be shifted to R[h];
 *	blk_num	number of blocks that S[h] will be splitted into;
 *	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;

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

	PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
	PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
}

/*
 * check if node disappears 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);

	/* all content of node can be shifted to neighbors */
	if (remain_items < 1) {
		set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
			       NULL, -1, -1);
		return 1;
	}

	/* S[0] is not removable */
	if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
		return 0;

	/* check whether we can divide 1 remaining item between neighbors */

	/* get size of remaining item (in item units) */
	size = op_unit_num(&(vn->vn_vi[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;

		RFALSE(B_NR_ITEMS(S0) != 1,
		       "vs-8125: item number must be 1: it is %d",
		       B_NR_ITEMS(S0));

		ih = item_head(S0, 0);
		if (tb->CFR[0]
		    && !comp_short_le_keys(&(ih->ih_key),
					   internal_key(tb->CFR[0],
							  tb->rkey[0])))
			/*
			 * Directory must be in correct state here: that is
			 * somewhere at the left side should exist first
			 * directory item. But the item being deleted can
			 * not be that first one because its right neighbor
			 * is item of the same directory. (But first item
			 * always gets deleted in last turn). So, neighbors
			 * of deleted item can be merged, so we can save
			 * ih_size
			 */
			if (is_direntry_le_ih(ih)) {
				ih_size = IH_SIZE;

				/*
				 * we might check that left neighbor exists
				 * and is of the same directory
				 */
				RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
				       "vs-8130: first directory item can not be removed until directory is not empty");
			}

	}

	if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
		set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
		PROC_INFO_INC(tb->tb_sb, leaves_removable);
		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);\
}

static void free_buffers_in_tb(struct tree_balance *tb)
{
	int i;

	pathrelse(tb->tb_path);

	for (i = 0; i < MAX_HEIGHT; i++) {
		brelse(tb->L[i]);
		brelse(tb->R[i]);
		brelse(tb->FL[i]);
		brelse(tb->FR[i]);
		brelse(tb->CFL[i]);
		brelse(tb->CFR[i]);

		tb->L[i] = NULL;
		tb->R[i] = NULL;
		tb->FL[i] = NULL;
		tb->FR[i] = NULL;
		tb->CFL[i] = NULL;
		tb->CFR[i] = NULL;
	}
}

/*
 * Get new buffers for storing new nodes that are created while balancing.
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 *	        NO_DISK_SPACE - no disk space.
 */
/* The function is NOT SCHEDULE-SAFE! */
static int get_empty_nodes(struct tree_balance *tb, int h)
{
	struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h);
	b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
	int counter, number_of_freeblk;
	int  amount_needed;	/* number of needed empty blocks */
	int  retval = CARRY_ON;
	struct super_block *sb = tb->tb_sb;

	/*
	 * 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 (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 h.
	 */
	/* blknum includes S[h], so we subtract 1 in this calculation */
	for (counter = 0, number_of_freeblk = tb->cur_blknum;
	     counter < h; counter++)
		number_of_freeblk -=
		    (tb->blknum[counter]) ? (tb->blknum[counter] -
						   1) : 0;

	/* Allocate missing empty blocks. */
	/* if Sh == 0  then we are getting a new root */
	amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
	/*
	 * Amount_needed = the amount that we need more than the
	 * amount that we have.
	 */
	if (amount_needed > number_of_freeblk)
		amount_needed -= 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(tb, blocknrs,
				       amount_needed) == NO_DISK_SPACE)
		return NO_DISK_SPACE;

	/* for each blocknumber we just got, get a buffer and stick it on FEB */
	for (blocknr = blocknrs, counter = 0;
	     counter < amount_needed; blocknr++, counter++) {

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

		new_bh = sb_getblk(sb, *blocknr);
		RFALSE(buffer_dirty(new_bh) ||
		       buffer_journaled(new_bh) ||
		       buffer_journal_dirty(new_bh),
		       "PAP-8140: journaled or dirty buffer %b for the new block",
		       new_bh);

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

		set_buffer_journal_new(new_bh);
		tb->FEB[tb->cur_blknum++] = new_bh;
	}

	if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
		retval = REPEAT_SEARCH;

	return 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)) == NULL ||
	    (l = tb->FL[h]) == NULL)
		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)) == NULL ||
	    (r = tb->FR[h]) == NULL)
		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 *tb, int h)
{
	struct buffer_head *father, *left;
	struct super_block *sb = tb->tb_sb;
	b_blocknr_t left_neighbor_blocknr;
	int left_neighbor_position;

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

	/* Calculate father of the node to be balanced. */
	father = PATH_H_PBUFFER(tb->tb_path, h + 1);

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

	/*
	 * Get position of the pointer to the left neighbor
	 * into the left father.
	 */
	left_neighbor_position = (father == tb->FL[h]) ?
	    tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
	/* Get left neighbor block number. */
	left_neighbor_blocknr =
	    B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
	/* Look for the left neighbor in the cache. */
	if ((left = sb_find_get_block(sb, 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 *key)
{
	/* call item specific function for this key */
	item_ops[cpu_key_k_type(key)]->decrement_key(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 *tb,
			  int h,
			  struct buffer_head **pfather,
			  struct buffer_head **pcom_father, char c_lr_par)
{
	struct buffer_head *parent;
	INITIALIZE_PATH(s_path_to_neighbor_father);
	struct treepath *path = tb->tb_path;
	struct cpu_key s_lr_father_key;
	int counter,
	    position = INT_MAX,
	    first_last_position = 0,
	    path_offset = PATH_H_PATH_OFFSET(path, h);

	/*
	 * Starting from F[h] go upwards in the tree, and look for the common
	 * ancestor of F[h], and its neighbor l/r, that should be obtained.
	 */

	counter = path_offset;

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

	for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {
		/*
		 * Check whether parent of the current buffer in the path
		 * is really parent in the tree.
		 */
		if (!B_IS_IN_TREE
		    (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))
			return REPEAT_SEARCH;

		/* Check whether position in the parent is correct. */
		if ((position =
		     PATH_OFFSET_POSITION(path,
					  counter - 1)) >
		    B_NR_ITEMS(parent))
			return REPEAT_SEARCH;

		/*
		 * Check whether parent at the path really points
		 * to the child.
		 */
		if (B_N_CHILD_NUM(parent, position) !=
		    PATH_OFFSET_PBUFFER(path, 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)
			first_last_position = B_NR_ITEMS(parent);
		if (position != first_last_position) {
			*pcom_father = parent;
			get_bh(*pcom_father);
			/*(*pcom_father = parent)->b_count++; */
			break;
		}
	}

	/* if we are in the root of the tree, then there is no common father */
	if (counter == FIRST_PATH_ELEMENT_OFFSET) {
		/*
		 * Check whether first buffer in the path is the
		 * root of the tree.
		 */
		if (PATH_OFFSET_PBUFFER
		    (tb->tb_path,
		     FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
		    SB_ROOT_BLOCK(tb->tb_sb)) {
			*pfather = *pcom_father = NULL;
			return CARRY_ON;
		}
		return REPEAT_SEARCH;
	}

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

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

	if (buffer_locked(*pcom_father)) {

		/* Release the write lock while the buffer is busy */
		int depth = reiserfs_write_unlock_nested(tb->tb_sb);
		__wait_on_buffer(*pcom_father);
		reiserfs_write_lock_nested(tb->tb_sb, depth);
		if (FILESYSTEM_CHANGED_TB(tb)) {
			brelse(*pcom_father);
			return REPEAT_SEARCH;
		}
	}

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

	/* Form key to get parent of the left/right neighbor. */
	le_key2cpu_key(&s_lr_father_key,
		       internal_key(*pcom_father,
				      (c_lr_par ==
				       LEFT_PARENTS) ? (tb->lkey[h - 1] =
							position -
							1) : (tb->rkey[h -
									   1] =
							      position)));

	if (c_lr_par == LEFT_PARENTS)
		decrement_key(&s_lr_father_key);

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

	if (FILESYSTEM_CHANGED_TB(tb)) {
		pathrelse(&s_path_to_neighbor_father);
		brelse(*pcom_father);
		return REPEAT_SEARCH;
	}

	*pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);

	RFALSE(B_LEVEL(*pfather) != h + 1,
	       "PAP-8190: (%b %z) level too small", *pfather, *pfather);
	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--;
	pathrelse(&s_path_to_neighbor_father);
	return CARRY_ON;
}

/*
 * Get parents of neighbors of node in the path(S[path_offset]) and
 * common parents of S[path_offset] and L[path_offset]/R[path_offset]:
 * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],
 * CFR[path_offset].
 * Calculate numbers of left and right delimiting keys position:
 * lkey[path_offset], rkey[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 *tb, int h)
{
	struct treepath *path = tb->tb_path;
	int position,
	    ret,
	    path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
	struct buffer_head *curf, *curcf;

	/* Current node is the root of the tree or will be root of the tree */
	if (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(tb->FL[h]);
		brelse(tb->CFL[h]);
		brelse(tb->FR[h]);
		brelse(tb->CFR[h]);
		tb->FL[h]  = NULL;
		tb->CFL[h] = NULL;
		tb->FR[h]  = NULL;
		tb->CFR[h] = NULL;
		return CARRY_ON;
	}

	/* Get parent FL[path_offset] of L[path_offset]. */
	position = PATH_OFFSET_POSITION(path, path_offset - 1);
	if (position) {
		/* Current node is not the first child of its parent. */
		curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
		curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
		get_bh(curf);
		get_bh(curf);
		tb->lkey[h] = position - 1;
	} else {
		/*
		 * Calculate current parent of L[path_offset], which is the
		 * left neighbor of the current node.  Calculate current
		 * common parent of L[path_offset] and the current node.
		 * Note that CFL[path_offset] not equal FL[path_offset] and
		 * CFL[path_offset] not equal F[path_offset].
		 * Calculate lkey[path_offset].
		 */
		if ((ret = get_far_parent(tb, h + 1, &curf,
						  &curcf,
						  LEFT_PARENTS)) != CARRY_ON)
			return ret;
	}

	brelse(tb->FL[h]);
	tb->FL[h] = curf;	/* New initialization of FL[h]. */
	brelse(tb->CFL[h]);
	tb->CFL[h] = curcf;	/* New initialization of CFL[h]. */

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

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

	/* Current node is the last child of F[h]. FR[h] != F[h]. */
	if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {
		/*
		 * Calculate current parent of R[h], which is the right
		 * neighbor of F[h].  Calculate current common parent of
		 * R[h] and current node. Note that CFR[h] not equal
		 * FR[path_offset] and CFR[h] not equal F[h].
		 */
		if ((ret =
		     get_far_parent(tb, h + 1, &curf, &curcf,
				    RIGHT_PARENTS)) != CARRY_ON)
			return ret;
	} else {
		/* Current node is not the last child of its parent F[h]. */
		curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
		curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
		get_bh(curf);
		get_bh(curf);
		tb->rkey[h] = position;
	}

	brelse(tb->FR[h]);
	/* New initialization of FR[path_offset]. */
	tb->FR[h] = curf;

	brelse(tb->CFR[h]);
	/* New initialization of CFR[path_offset]. */
	tb->CFR[h] = curcf;

	RFALSE((curf && !B_IS_IN_TREE(curf)) ||
	       (curcf && !B_IS_IN_TREE(curcf)),
	       "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, 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 = item_head(Sh, 0);
	if (tb->CFR[h])
		r_key = internal_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;
	/*
	 * 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.
	 */
	int levbytes;
	int ret;

	int lfree, sfree, rfree /* free space in L, S and R */ ;

	/*
	 * nver is short for number of vertixes, 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 vertixes, and second,
	 * the number of vertixes whose contents are changed by shifting,
	 * and third the number of uncached vertixes 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
	 *
	 * 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)
	 */
	short snum012[40] = { 0, };

	/* Sh is the node whose balance is currently being checked */
	struct buffer_head *Sh;

	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(tb->tb_sb, "vs-8210",
				       "S[0] can not be 0");
		switch (ret = get_empty_nodes(tb, h)) {
		/* no balancing for higher levels needed */
		case CARRY_ON:
			set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
			return NO_BALANCING_NEEDED;

		case NO_DISK_SPACE:
		case REPEAT_SEARCH:
			return ret;
		default:
			reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
				       "return value of get_empty_nodes");
		}
	}

	/* get parents of S[h] neighbors. */
	ret = get_parents(tb, h);
	if (ret != CARRY_ON)
		return ret;

	sfree = B_FREE_SPACE(Sh);

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

	/* and new item fits into node S[h] without any shifting */
	if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
	    NO_BALANCING_NEEDED)
		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;

		/*
		 * Since we are working on internal nodes, and our internal
		 * nodes have fixed size entries, then we can balance by the
		 * number of items rather than the space they consume.  In this
		 * routine we set the left node equal to the right node,
		 * allowing a difference of less than or equal to 1 child
		 * pointer.
		 */
		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;
	}

	/*
	 * this checks balance condition, that any two neighboring nodes
	 * can not fit in one node
	 */
	RFALSE(h &&
	       (tb->lnum[h] >= vn->vn_nr_item + 1 ||
		tb->rnum[h] >= vn->vn_nr_item + 1),
	       "vs-8220: tree is not balanced on internal level");
	RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
		      (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
	       "vs-8225: tree is not balanced on leaf level");

	/*
	 * all contents of S[0] can be moved into its neighbors
	 * S[0] will be removed after balancing.
	 */
	if (!h && is_leaf_removable(tb))
		return CARRY_ON;

	/*
	 * why do we perform this check here rather than earlier??
	 * Answer: we can win 1 node in some cases above. Moreover we
	 * checked it above, when we checked, that S[0] is not removable
	 * in principle
	 */

	 /* new item fits into node S[h] without any shifting */
	if (sfree >= levbytes) {
		if (!h)
			tb->s0num = vn->vn_nr_item;
		set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
		return NO_BALANCING_NEEDED;
	}

	{
		int lpar, rpar, nset, lset, rset, lrset;
		/* regular overflowing of the node */

		/*
		 * get_num_ver works in 2 modes (FLOW & NO_FLOW)
		 * lpar, rpar - number of items we can shift to left/right
		 *              neighbor (including splitting item)
		 * nset, lset, rset, lrset - shows, whether flowing items
		 *                           give better packing
		 */
#define FLOW 1
#define NO_FLOW 0		/* do not any splitting */

		/* we choose one of the following */
#define NOTHING_SHIFT_NO_FLOW	0
#define NOTHING_SHIFT_FLOW	5
#define LEFT_SHIFT_NO_FLOW	10
#define LEFT_SHIFT_FLOW		15
#define RIGHT_SHIFT_NO_FLOW	20
#define RIGHT_SHIFT_FLOW	25
#define LR_SHIFT_NO_FLOW	30
#define LR_SHIFT_FLOW		35

		lpar = tb->lnum[h];
		rpar = tb->rnum[h];

		/*
		 * calculate number of blocks S[h] must be split into when
		 * nothing is shifted to the neighbors, as well as number of
		 * items in each part of the split node (s012 numbers),
		 * and number of bytes (s1bytes) of the shared drop which
		 * flow to S1 if any
		 */
		nset = NOTHING_SHIFT_NO_FLOW;
		nver = get_num_ver(vn->vn_mode, tb, h,
				   0, -1, h ? vn->vn_nr_item : 0, -1,
				   snum012, NO_FLOW);

		if (!h) {
			int nver1;

			/*
			 * note, that in this case we try to bottle
			 * between S[0] and S1 (S1 - the first new node)
			 */
			nver1 = get_num_ver(vn->vn_mode, tb, h,
					    0, -1, 0, -1,
					    snum012 + NOTHING_SHIFT_FLOW, FLOW);
			if (nver > nver1)
				nset = NOTHING_SHIFT_FLOW, nver = nver1;
		}

		/*
		 * calculate number of blocks S[h] must be split into when
		 * l_shift_num first items and l_shift_bytes of the right
		 * most liquid item to be shifted are shifted to the left
		 * neighbor, as well as number of items in each part of the
		 * splitted node (s012 numbers), and number of bytes
		 * (s1bytes) of the shared drop which flow to S1 if any
		 */
		lset = LEFT_SHIFT_NO_FLOW;
		lnver = get_num_ver(vn->vn_mode, tb, h,
				    lpar - ((h || tb->lbytes == -1) ? 0 : 1),
				    -1, h ? vn->vn_nr_item : 0, -1,
				    snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
		if (!h) {
			int lnver1;

			lnver1 = get_num_ver(vn->vn_mode, tb, h,
					     lpar -
					     ((tb->lbytes != -1) ? 1 : 0),
					     tb->lbytes, 0, -1,
					     snum012 + LEFT_SHIFT_FLOW, FLOW);
			if (lnver > lnver1)
				lset = LEFT_SHIFT_FLOW, lnver = lnver1;
		}

		/*
		 * calculate number of blocks S[h] must be split into when
		 * r_shift_num first items and r_shift_bytes of the left most
		 * liquid item to be shifted are shifted to the right neighbor,
		 * as well as number of items in each part of the splitted
		 * node (s012 numbers), and number of bytes (s1bytes) of the
		 * shared drop which flow to S1 if any
		 */
		rset = RIGHT_SHIFT_NO_FLOW;
		rnver = get_num_ver(vn->vn_mode, tb, h,
				    0, -1,
				    h ? (vn->vn_nr_item - rpar) : (rpar -
								   ((tb->
								     rbytes !=
								     -1) ? 1 :
								    0)), -1,
				    snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
		if (!h) {
			int rnver1;

			rnver1 = get_num_ver(vn->vn_mode, tb, h,
					     0, -1,
					     (rpar -
					      ((tb->rbytes != -1) ? 1 : 0)),
					     tb->rbytes,
					     snum012 + RIGHT_SHIFT_FLOW, FLOW);

			if (rnver > rnver1)
				rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
		}

		/*
		 * calculate number of blocks S[h] must be split into when
		 * items are shifted in both directions, as well as number
		 * of items in each part of the splitted node (s012 numbers),
		 * and number of bytes (s1bytes) of the shared drop which
		 * flow to S1 if any
		 */
		lrset = LR_SHIFT_NO_FLOW;
		lrnver = get_num_ver(vn->vn_mode, tb, h,
				     lpar - ((h || tb->lbytes == -1) ? 0 : 1),
				     -1,
				     h ? (vn->vn_nr_item - rpar) : (rpar -
								    ((tb->
								      rbytes !=
								      -1) ? 1 :
								     0)), -1,
				     snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
		if (!h) {
			int lrnver1;

			lrnver1 = get_num_ver(vn->vn_mode, tb, h,
					      lpar -
					      ((tb->lbytes != -1) ? 1 : 0),
					      tb->lbytes,
					      (rpar -
					       ((tb->rbytes != -1) ? 1 : 0)),
					      tb->rbytes,
					      snum012 + LR_SHIFT_FLOW, FLOW);
			if (lrnver > lrnver1)
				lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
		}

		/*
		 * Our general shifting strategy is:
		 * 1) to minimized number of new nodes;
		 * 2) to minimized number of neighbors involved in shifting;
		 * 3) to minimized number of disk reads;
		 */

		/* we can win TWO or ONE nodes by shifting in both directions */
		if (lrnver < lnver && lrnver < rnver) {
			RFALSE(h &&
			       (tb->lnum[h] != 1 ||
				tb->rnum[h] != 1 ||
				lrnver != 1 || rnver != 2 || lnver != 2
				|| h != 1), "vs-8230: bad h");
			if (lrset == LR_SHIFT_FLOW)
				set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
					       lrnver, snum012 + lrset,
					       tb->lbytes, tb->rbytes);
			else
				set_parameters(tb, h,
					       tb->lnum[h] -
					       ((tb->lbytes == -1) ? 0 : 1),
					       tb->rnum[h] -
					       ((tb->rbytes == -1) ? 0 : 1),
					       lrnver, snum012 + lrset, -1, -1);

			return CARRY_ON;
		}

		/*
		 * if shifting doesn't lead to better packing
		 * then don't shift
		 */
		if (nver == lrnver) {
			set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
				       -1);
			return CARRY_ON;
		}

		/*
		 * now we know that for better packing shifting in only one
		 * direction either to the left or to the right is required
		 */

		/*
		 * if shifting to the left is better than
		 * shifting to the right
		 */
		if (lnver < rnver) {
			SET_PAR_SHIFT_LEFT;
			return CARRY_ON;
		}

		/*
		 * if shifting to the right is better than
		 * shifting to the left
		 */
		if (lnver > rnver) {
			SET_PAR_SHIFT_RIGHT;
			return CARRY_ON;
		}

		/*
		 * now shifting in either direction gives the same number
		 * of nodes and we can make use of the cached neighbors
		 */
		if (is_left_neighbor_in_cache(tb, h)) {
			SET_PAR_SHIFT_LEFT;
			return CARRY_ON;
		}

		/*
		 * shift to the right independently on whether the
		 * right neighbor in cache or not
		 */
		SET_PAR_SHIFT_RIGHT;
		return CARRY_ON;
	}
}

/*
 * Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Cutting for INTERNAL 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.
 *
 * Note: Items of internal nodes have fixed size, so the balance condition for
 * the internal part of S+tree is as for the B-trees.
 */
static int dc_check_balance_internal(struct tree_balance *tb, int h)
{
	struct virtual_node *vn = tb->tb_vn;

	/*
	 * Sh is the node whose balance is currently being checked,
	 * and Fh is its father.
	 */
	struct buffer_head *Sh, *Fh;
	int maxsize, ret;
	int lfree, rfree /* free space in L and R */ ;

	Sh = PATH_H_PBUFFER(tb->tb_path, h);
	Fh = PATH_H_PPARENT(tb->tb_path, h);

	maxsize = MAX_CHILD_SIZE(Sh);

	/*
	 * using tb->insert_size[h], which is negative in this case,
	 * create_virtual_node calculates:
	 * new_nr_item = number of items node would have if operation is
	 * performed without balancing (new_nr_item);
	 */
	create_virtual_node(tb, h);

	if (!Fh) {		/* S[h] is the root. */
		/* no balancing for higher levels needed */
		if (vn->vn_nr_item > 0) {
			set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
			return NO_BALANCING_NEEDED;
		}
		/*
		 * new_nr_item == 0.
		 * Current root will be deleted resulting in
		 * decrementing the tree height.
		 */
		set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
		return CARRY_ON;
	}

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

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

	/* determine maximal number of items we can fit into neighbors */
	check_left(tb, h, lfree);
	check_right(tb, h, rfree);

	/*
	 * Balance condition for the internal node is valid.
	 * In this case we balance only if it leads to better packing.
	 */
	if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) {
		/*
		 * Here we join S[h] with one of its neighbors,
		 * which is impossible with greater values of new_nr_item.
		 */
		if (vn->vn_nr_item == MIN_NR_KEY(Sh)) {
			/* All contents of S[h] can be moved to L[h]. */
			if (tb->lnum[h] >= vn->vn_nr_item + 1) {
				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;
			}

			/* All contents of S[h] can be moved to R[h]. */
			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;
		}

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

	/*
	 * 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 ((ret = get_parents(tb, h)) != CARRY_ON)
		return ret;

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

	/* Calculate balance parameters when size of node is increasing. */
	if (tb->insert_size[h] > 0)
		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 *tb, int h)
{
	struct buffer_head *bh;
	struct treepath *path = tb->tb_path;
	int position,
	    path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);

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

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

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

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

	if ((position =
	     PATH_OFFSET_POSITION(path,
				  path_offset - 1)) > B_NR_ITEMS(bh))
		return REPEAT_SEARCH;

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

	if (buffer_locked(bh)) {
		int depth = reiserfs_write_unlock_nested(tb->tb_sb);
		__wait_on_buffer(bh);
		reiserfs_write_lock_nested(tb->tb_sb, depth);
		if (FILESYSTEM_CHANGED_TB(tb))
			return REPEAT_SEARCH;
	}

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

/*
 * Using lnum[h] and rnum[h] we should determine what neighbors
 * of S[h] we
 * need in order to balance S[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 *tb, int h)
{
	int child_position,
	    path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
	unsigned long son_number;
	struct super_block *sb = tb->tb_sb;
	struct buffer_head *bh;
	int depth;

	PROC_INFO_INC(sb, get_neighbors[h]);

	if (tb->lnum[h]) {
		/* We need left neighbor to balance S[h]. */
		PROC_INFO_INC(sb, need_l_neighbor[h]);
		bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);

		RFALSE(bh == tb->FL[h] &&
		       !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
		       "PAP-8270: invalid position in the parent");

		child_position =
		    (bh ==
		     tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
								       FL[h]);
		son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
		depth = reiserfs_write_unlock_nested(tb->tb_sb);
		bh = sb_bread(sb, son_number);
		reiserfs_write_lock_nested(tb->tb_sb, depth);
		if (!bh)
			return IO_ERROR;
		if (FILESYSTEM_CHANGED_TB(tb)) {
			brelse(bh);
			PROC_INFO_INC(sb, get_neighbors_restart[h]);
			return REPEAT_SEARCH;
		}

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

		brelse(tb->L[h]);
		tb->L[h] = bh;
	}

	/* We need right neighbor to balance S[path_offset]. */
	if (tb->rnum[h]) {
		PROC_INFO_INC(sb, need_r_neighbor[h]);
		bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);

		RFALSE(bh == tb->FR[h] &&
		       PATH_OFFSET_POSITION(tb->tb_path,
					    path_offset) >=
		       B_NR_ITEMS(bh),
		       "PAP-8295: invalid position in the parent");

		child_position =
		    (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
		son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
		depth = reiserfs_write_unlock_nested(tb->tb_sb);
		bh = sb_bread(sb, son_number);
		reiserfs_write_lock_nested(tb->tb_sb, depth);
		if (!bh)
			return IO_ERROR;
		if (FILESYSTEM_CHANGED_TB(tb)) {
			brelse(bh);
			PROC_INFO_INC(sb, get_neighbors_restart[h]);
			return REPEAT_SEARCH;
		}
		brelse(tb->R[h]);
		tb->R[h] = bh;

		RFALSE(!h
		       && B_FREE_SPACE(bh) !=
		       MAX_CHILD_SIZE(bh) -
		       dc_size(B_N_CHILD(tb->FR[0], child_position)),
		       "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
		       B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
		       dc_size(B_N_CHILD(tb->FR[0], 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;
	unsigned long blocksize = sb->s_blocksize;

#define MIN_NAME_LEN 1

	max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
	max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
	    (DEH_SIZE + MIN_NAME_LEN);

	return sizeof(struct virtual_node) +
	    max(max_num_of_items * sizeof(struct virtual_item),
		sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
		(max_num_of_entries - 1) * sizeof(__u16));
}

/*
 * maybe we should fail balancing we are going to perform when kmalloc
 * fails several times. But now it will loop until kmalloc gets
 * required memory
 */
static int get_mem_for_virtual_node(struct tree_balance *tb)
{
	int check_fs = 0;
	int size;
	char *buf;

	size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));

	/* we have to allocate more memory for virtual node */
	if (size > tb->vn_buf_size) {
		if (tb->vn_buf) {
			/* free memory allocated before */
			kfree(tb->vn_buf);
			/* this is not needed if kfree is atomic */
			check_fs = 1;
		}

		/* virtual node requires now more memory */
		tb->vn_buf_size = size;

		/* get memory for virtual item */
		buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
		if (!buf) {
			/*
			 * getting memory with GFP_KERNEL priority may involve
			 * balancing now (due to indirect_to_direct conversion
			 * on dcache shrinking). So, release path and collected
			 * resources here
			 */
			free_buffers_in_tb(tb);
			buf = kmalloc(size, GFP_NOFS);
			if (!buf) {
				tb->vn_buf_size = 0;
			}
			tb->vn_buf = buf;
			schedule();
			return REPEAT_SEARCH;
		}

		tb->vn_buf = buf;
	}

	if (check_fs && FILESYSTEM_CHANGED_TB(tb))
		return REPEAT_SEARCH;

	return CARRY_ON;
}

#ifdef CONFIG_REISERFS_CHECK
static void tb_buffer_sanity_check(struct super_block *sb,
				   struct buffer_head *bh,
				   const char *descr, int level)
{
	if (bh) {
		if (atomic_read(&(bh->b_count)) <= 0)

			reiserfs_panic(sb, "jmacd-1", "negative or zero "
				       "reference counter for buffer %s[%d] "
				       "(%b)", descr, level, bh);

		if (!buffer_uptodate(bh))
			reiserfs_panic(sb, "jmacd-2", "buffer is not up "
				       "to date %s[%d] (%b)",
				       descr, level, bh);

		if (!B_IS_IN_TREE(bh))
			reiserfs_panic(sb, "jmacd-3", "buffer is not "
				       "in tree %s[%d] (%b)",
				       descr, level, bh);

		if (bh->b_bdev != sb->s_bdev)
			reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
				       "device %s[%d] (%b)",
				       descr, level, bh);

		if (bh->b_size != sb->s_blocksize)
			reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
				       "blocksize %s[%d] (%b)",
				       descr, level, bh);

		if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
			reiserfs_panic(sb, "jmacd-6", "buffer block "
				       "number too high %s[%d] (%b)",
				       descr, level, bh);
	}
}
#else
static void tb_buffer_sanity_check(struct super_block *sb,
				   struct buffer_head *bh,
				   const char *descr, int level)
{;
}
#endif

static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
{
	return reiserfs_prepare_for_journal(s, bh, 0);
}

static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
{
	struct buffer_head *locked;
#ifdef CONFIG_REISERFS_CHECK
	int repeat_counter = 0;
#endif
	int i;

	do {

		locked = NULL;

		for (i = tb->tb_path->path_length;
		     !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
			if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
				/*
				 * if I understand correctly, we can only
				 * be sure the last buffer in the path is
				 * in the tree --clm
				 */
#ifdef CONFIG_REISERFS_CHECK
				if (PATH_PLAST_BUFFER(tb->tb_path) ==
				    PATH_OFFSET_PBUFFER(tb->tb_path, i))
					tb_buffer_sanity_check(tb->tb_sb,
							       PATH_OFFSET_PBUFFER
							       (tb->tb_path,
								i), "S",
							       tb->tb_path->
							       path_length - i);
#endif
				if (!clear_all_dirty_bits(tb->tb_sb,
							  PATH_OFFSET_PBUFFER
							  (tb->tb_path,
							   i))) {
					locked =
					    PATH_OFFSET_PBUFFER(tb->tb_path,
								i);
				}
			}
		}

		for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
		     i++) {

			if (tb->lnum[i]) {

				if (tb->L[i]) {
					tb_buffer_sanity_check(tb->tb_sb,
							       tb->L[i],
							       "L", i);
					if (!clear_all_dirty_bits
					    (tb->tb_sb, tb->L[i]))
						locked = tb->L[i];
				}

				if (!locked && tb->FL[i]) {
					tb_buffer_sanity_check(tb->tb_sb,
							       tb->FL[i],
							       "FL", i);
					if (!clear_all_dirty_bits
					    (tb->tb_sb, tb->FL[i]))
						locked = tb->FL[i];
				}

				if (!locked && tb->CFL[i]) {
					tb_buffer_sanity_check(tb->tb_sb,
							       tb->CFL[i],
							       "CFL", i);
					if (!clear_all_dirty_bits
					    (tb->tb_sb, tb->CFL[i]))
						locked = tb->CFL[i];
				}

			}

			if (!locked && (tb->rnum[i])) {

				if (tb->R[i]) {
					tb_buffer_sanity_check(tb->tb_sb,
							       tb->R[i],
							       "R", i);
					if (!clear_all_dirty_bits
					    (tb->tb_sb, tb->R[i]))
						locked = tb->R[i];
				}

				if (!locked && tb->FR[i]) {
					tb_buffer_sanity_check(tb->tb_sb,
							       tb->FR[i],
							       "FR", i);
					if (!clear_all_dirty_bits
					    (tb->tb_sb, tb->FR[i]))
						locked = tb->FR[i];
				}

				if (!locked && tb->CFR[i]) {
					tb_buffer_sanity_check(tb->tb_sb,
							       tb->CFR[i],
							       "CFR", i);
					if (!clear_all_dirty_bits
					    (tb->tb_sb, tb->CFR[i]))
						locked = tb->CFR[i];
				}
			}
		}

		/*
		 * as far as I can tell, this is not required.  The FEB list
		 * seems to be full of newly allocated nodes, which will
		 * never be locked, dirty, or anything else.
		 * To be safe, I'm putting in the checks and waits in.
		 * For the moment, they are needed to keep the code in
		 * journal.c from complaining about the buffer.
		 * That code is inside CONFIG_REISERFS_CHECK as well.  --clm
		 */
		for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
			if (tb->FEB[i]) {
				if (!clear_all_dirty_bits
				    (tb->tb_sb, tb->FEB[i]))
					locked = tb->FEB[i];
			}
		}

		if (locked) {
			int depth;
#ifdef CONFIG_REISERFS_CHECK
			repeat_counter++;
			if ((repeat_counter % 10000) == 0) {
				reiserfs_warning(tb->tb_sb, "reiserfs-8200",
						 "too many iterations waiting "
						 "for buffer to unlock "
						 "(%b)", locked);

				/* Don't loop forever.  Try to recover from possible error. */

				return (FILESYSTEM_CHANGED_TB(tb)) ?
				    REPEAT_SEARCH : CARRY_ON;
			}
#endif
			depth = reiserfs_write_unlock_nested(tb->tb_sb);
			__wait_on_buffer(locked);
			reiserfs_write_lock_nested(tb->tb_sb, depth);
			if (FILESYSTEM_CHANGED_TB(tb))
				return REPEAT_SEARCH;
		}

	} while (locked);

	return CARRY_ON;
}

/*
 * Prepare for balancing, that is
 *	get all necessary parents, and neighbors;
 *	analyze what and where should be moved;
 *	get sufficient number of new nodes;
 * Balancing will start only after all resources will be collected at a time.
 *
 * When ported to SMP kernels, only at the last moment after all needed nodes
 * are collected in cache, will the resources be locked using the usual
 * textbook ordered lock acquisition algorithms.  Note that ensuring that
 * this code neither write locks what it does not need to write lock nor locks
 * out of order will be a pain in the butt that could have been avoided.
 * Grumble grumble. -Hans
 *
 * fix is meant in the sense of render unchanging
 *
 * Latency might be improved by first gathering a list of what buffers
 * are needed and then getting as many of them in parallel as possible? -Hans
 *
 * Parameters:
 *	op_mode	i - insert, d - delete, c - cut (truncate), p - paste (append)
 *	tb	tree_balance structure;
 *	inum	item number in S[h];
 *      pos_in_item - comment this if you can
 *      ins_ih	item head of item being inserted
 *	data	inserted item or data to be pasted
 * Returns:	1 - schedule occurred while the function worked;
 *	        0 - schedule didn't occur while the function worked;
 *             -1 - if no_disk_space
 */

int fix_nodes(int op_mode, struct tree_balance *tb,
	      struct item_head *ins_ih, const void *data)
{
	int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
	int pos_in_item;

	/*
	 * we set wait_tb_buffers_run when we have to restore any dirty
	 * bits cleared during wait_tb_buffers_run
	 */
	int wait_tb_buffers_run = 0;
	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);

	++REISERFS_SB(tb->tb_sb)->s_fix_nodes;

	pos_in_item = tb->tb_path->pos_in_item;

	tb->fs_gen = get_generation(tb->tb_sb);

	/*
	 * we prepare and log the super here so it will already be in the
	 * transaction when do_balance needs to change it.
	 * This way do_balance won't have to schedule when trying to prepare
	 * the super for logging
	 */
	reiserfs_prepare_for_journal(tb->tb_sb,
				     SB_BUFFER_WITH_SB(tb->tb_sb), 1);
	journal_mark_dirty(tb->transaction_handle,
			   SB_BUFFER_WITH_SB(tb->tb_sb));
	if (FILESYSTEM_CHANGED_TB(tb))
		return REPEAT_SEARCH;

	/* if it possible in indirect_to_direct conversion */
	if (buffer_locked(tbS0)) {
		int depth = reiserfs_write_unlock_nested(tb->tb_sb);
		__wait_on_buffer(tbS0);
		reiserfs_write_lock_nested(tb->tb_sb, depth);
		if (FILESYSTEM_CHANGED_TB(tb))
			return REPEAT_SEARCH;
	}
#ifdef CONFIG_REISERFS_CHECK
	if (REISERFS_SB(tb->tb_sb)->cur_tb) {
		print_cur_tb("fix_nodes");
		reiserfs_panic(tb->tb_sb, "PAP-8305",
			       "there is pending do_balance");
	}

	if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
		reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
			       "not uptodate at the beginning of fix_nodes "
			       "or not in tree (mode %c)",
			       tbS0, tbS0, op_mode);

	/* Check parameters. */
	switch (op_mode) {
	case M_INSERT:
		if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
			reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
				       "item number %d (in S0 - %d) in case "
				       "of insert", item_num,
				       B_NR_ITEMS(tbS0));
		break;
	case M_PASTE:
	case M_DELETE:
	case M_CUT:
		if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
			print_block(tbS0, 0, -1, -1);
			reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
				       "item number(%d); mode = %c "
				       "insert_size = %d",
				       item_num, op_mode,
				       tb->insert_size[0]);
		}
		break;
	default:
		reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
			       "of operation");
	}
#endif

	if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
		/* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
		return REPEAT_SEARCH;

	/* Starting from the leaf level; for all levels h of the tree. */
	for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
		ret = get_direct_parent(tb, h);
		if (ret != CARRY_ON)
			goto repeat;

		ret = check_balance(op_mode, tb, h, item_num,
				    pos_in_item, ins_ih, data);
		if (ret != CARRY_ON) {
			if (ret == NO_BALANCING_NEEDED) {
				/* No balancing for higher levels needed. */
				ret = get_neighbors(tb, h);
				if (ret != CARRY_ON)
					goto repeat;
				if (h != MAX_HEIGHT - 1)
					tb->insert_size[h + 1] = 0;
				/*
				 * ok, analysis and resource gathering
				 * are complete
				 */
				break;
			}
			goto repeat;
		}

		ret = get_neighbors(tb, h);
		if (ret != CARRY_ON)
			goto repeat;

		/*
		 * No disk space, or schedule occurred and analysis may be
		 * invalid and needs to be redone.
		 */
		ret = get_empty_nodes(tb, h);
		if (ret != CARRY_ON)
			goto repeat;

		/*
		 * We have a positive insert size but no nodes exist on this
		 * level, this means that we are creating a new root.
		 */
		if (!PATH_H_PBUFFER(tb->tb_path, h)) {

			RFALSE(tb->blknum[h] != 1,
			       "PAP-8350: creating new empty root");

			if (h < MAX_HEIGHT - 1)
				tb->insert_size[h + 1] = 0;
		} else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
			/*
			 * The tree needs to be grown, so this node S[h]
			 * which is the root node is split into two nodes,
			 * and a new node (S[h+1]) will be created to
			 * become the root node.
			 */
			if (tb->blknum[h] > 1) {

				RFALSE(h == MAX_HEIGHT - 1,
				       "PAP-8355: attempt to create too high of a tree");

				tb->insert_size[h + 1] =
				    (DC_SIZE +
				     KEY_SIZE) * (tb->blknum[h] - 1) +
				    DC_SIZE;
			} else if (h < MAX_HEIGHT - 1)
				tb->insert_size[h + 1] = 0;
		} else
			tb->insert_size[h + 1] =
			    (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
	}

	ret = wait_tb_buffers_until_unlocked(tb);
	if (ret == CARRY_ON) {
		if (FILESYSTEM_CHANGED_TB(tb)) {
			wait_tb_buffers_run = 1;
			ret = REPEAT_SEARCH;
			goto repeat;
		} else {
			return CARRY_ON;
		}
	} else {
		wait_tb_buffers_run = 1;
		goto repeat;
	}

      repeat:
	/*
	 * fix_nodes was unable to perform its calculation due to
	 * filesystem got changed under us, lack of free disk space or i/o
	 * failure. If the first is the case - the search will be
	 * repeated. For now - free all resources acquired so far except
	 * for the new allocated nodes
	 */
	{
		int i;

		/* Release path buffers. */
		if (wait_tb_buffers_run) {
			pathrelse_and_restore(tb->tb_sb, tb->tb_path);
		} else {
			pathrelse(tb->tb_path);
		}
		/* brelse all resources collected for balancing */
		for (i = 0; i < MAX_HEIGHT; i++) {
			if (wait_tb_buffers_run) {
				reiserfs_restore_prepared_buffer(tb->tb_sb,
								 tb->L[i]);
				reiserfs_restore_prepared_buffer(tb->tb_sb,
								 tb->R[i]);
				reiserfs_restore_prepared_buffer(tb->tb_sb,
								 tb->FL[i]);
				reiserfs_restore_prepared_buffer(tb->tb_sb,
								 tb->FR[i]);
				reiserfs_restore_prepared_buffer(tb->tb_sb,
								 tb->
								 CFL[i]);
				reiserfs_restore_prepared_buffer(tb->tb_sb,
								 tb->
								 CFR[i]);
			}

			brelse(tb->L[i]);
			brelse(tb->R[i]);
			brelse(tb->FL[i]);
			brelse(tb->FR[i]);
			brelse(tb->CFL[i]);
			brelse(tb->CFR[i]);

			tb->L[i] = NULL;
			tb->R[i] = NULL;
			tb->FL[i] = NULL;
			tb->FR[i] = NULL;
			tb->CFL[i] = NULL;
			tb->CFR[i] = NULL;
		}

		if (wait_tb_buffers_run) {
			for (i = 0; i < MAX_FEB_SIZE; i++) {
				if (tb->FEB[i])
					reiserfs_restore_prepared_buffer
					    (tb->tb_sb, tb->FEB[i]);
			}
		}
		return ret;
	}

}

void unfix_nodes(struct tree_balance *tb)
{
	int i;

	/* Release path buffers. */
	pathrelse_and_restore(tb->tb_sb, tb->tb_path);

	/* brelse all resources collected for balancing */
	for (i = 0; i < MAX_HEIGHT; i++) {
		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);

		brelse(tb->L[i]);
		brelse(tb->R[i]);
		brelse(tb->FL[i]);
		brelse(tb->FR[i]);
		brelse(tb->CFL[i]);
		brelse(tb->CFR[i]);
	}

	/* deal with list of allocated (used and unused) nodes */
	for (i = 0; i < MAX_FEB_SIZE; i++) {
		if (tb->FEB[i]) {
			b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
			/*
			 * de-allocated block which was not used by
			 * balancing and bforget about buffer for it
			 */
			brelse(tb->FEB[i]);
			reiserfs_free_block(tb->transaction_handle, NULL,
					    blocknr, 0);
		}
		if (tb->used[i]) {
			/* release used as new nodes including a new root */
			brelse(tb->used[i]);
		}
	}

	kfree(tb->vn_buf);

}