cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

fix_node.c (79117B)


      1/*
      2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
      3 */
      4
      5#include <linux/time.h>
      6#include <linux/slab.h>
      7#include <linux/string.h>
      8#include "reiserfs.h"
      9#include <linux/buffer_head.h>
     10
     11/*
     12 * To make any changes in the tree we find a node that contains item
     13 * to be changed/deleted or position in the node we insert a new item
     14 * to. We call this node S. To do balancing we need to decide what we
     15 * will shift to left/right neighbor, or to a new node, where new item
     16 * will be etc. To make this analysis simpler we build virtual
     17 * node. Virtual node is an array of items, that will replace items of
     18 * node S. (For instance if we are going to delete an item, virtual
     19 * node does not contain it). Virtual node keeps information about
     20 * item sizes and types, mergeability of first and last items, sizes
     21 * of all entries in directory item. We use this array of items when
     22 * calculating what we can shift to neighbors and how many nodes we
     23 * have to have if we do not any shiftings, if we shift to left/right
     24 * neighbor or to both.
     25 */
     26
     27/*
     28 * Takes item number in virtual node, returns number of item
     29 * that it has in source buffer
     30 */
     31static inline int old_item_num(int new_num, int affected_item_num, int mode)
     32{
     33	if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
     34		return new_num;
     35
     36	if (mode == M_INSERT) {
     37
     38		RFALSE(new_num == 0,
     39		       "vs-8005: for INSERT mode and item number of inserted item");
     40
     41		return new_num - 1;
     42	}
     43
     44	RFALSE(mode != M_DELETE,
     45	       "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
     46	       mode);
     47	/* delete mode */
     48	return new_num + 1;
     49}
     50
     51static void create_virtual_node(struct tree_balance *tb, int h)
     52{
     53	struct item_head *ih;
     54	struct virtual_node *vn = tb->tb_vn;
     55	int new_num;
     56	struct buffer_head *Sh;	/* this comes from tb->S[h] */
     57
     58	Sh = PATH_H_PBUFFER(tb->tb_path, h);
     59
     60	/* size of changed node */
     61	vn->vn_size =
     62	    MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
     63
     64	/* for internal nodes array if virtual items is not created */
     65	if (h) {
     66		vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
     67		return;
     68	}
     69
     70	/* number of items in virtual node  */
     71	vn->vn_nr_item =
     72	    B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
     73	    ((vn->vn_mode == M_DELETE) ? 1 : 0);
     74
     75	/* first virtual item */
     76	vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
     77	memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
     78	vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
     79
     80	/* first item in the node */
     81	ih = item_head(Sh, 0);
     82
     83	/* define the mergeability for 0-th item (if it is not being deleted) */
     84	if (op_is_left_mergeable(&ih->ih_key, Sh->b_size)
     85	    && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
     86		vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
     87
     88	/*
     89	 * go through all items that remain in the virtual
     90	 * node (except for the new (inserted) one)
     91	 */
     92	for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
     93		int j;
     94		struct virtual_item *vi = vn->vn_vi + new_num;
     95		int is_affected =
     96		    ((new_num != vn->vn_affected_item_num) ? 0 : 1);
     97
     98		if (is_affected && vn->vn_mode == M_INSERT)
     99			continue;
    100
    101		/* get item number in source node */
    102		j = old_item_num(new_num, vn->vn_affected_item_num,
    103				 vn->vn_mode);
    104
    105		vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
    106		vi->vi_ih = ih + j;
    107		vi->vi_item = ih_item_body(Sh, ih + j);
    108		vi->vi_uarea = vn->vn_free_ptr;
    109
    110		/*
    111		 * FIXME: there is no check that item operation did not
    112		 * consume too much memory
    113		 */
    114		vn->vn_free_ptr +=
    115		    op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
    116		if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
    117			reiserfs_panic(tb->tb_sb, "vs-8030",
    118				       "virtual node space consumed");
    119
    120		if (!is_affected)
    121			/* this is not being changed */
    122			continue;
    123
    124		if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
    125			vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
    126			/* pointer to data which is going to be pasted */
    127			vi->vi_new_data = vn->vn_data;
    128		}
    129	}
    130
    131	/* virtual inserted item is not defined yet */
    132	if (vn->vn_mode == M_INSERT) {
    133		struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
    134
    135		RFALSE(vn->vn_ins_ih == NULL,
    136		       "vs-8040: item header of inserted item is not specified");
    137		vi->vi_item_len = tb->insert_size[0];
    138		vi->vi_ih = vn->vn_ins_ih;
    139		vi->vi_item = vn->vn_data;
    140		vi->vi_uarea = vn->vn_free_ptr;
    141
    142		op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
    143			     tb->insert_size[0]);
    144	}
    145
    146	/*
    147	 * set right merge flag we take right delimiting key and
    148	 * check whether it is a mergeable item
    149	 */
    150	if (tb->CFR[0]) {
    151		struct reiserfs_key *key;
    152
    153		key = internal_key(tb->CFR[0], tb->rkey[0]);
    154		if (op_is_left_mergeable(key, Sh->b_size)
    155		    && (vn->vn_mode != M_DELETE
    156			|| vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
    157			vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
    158			    VI_TYPE_RIGHT_MERGEABLE;
    159
    160#ifdef CONFIG_REISERFS_CHECK
    161		if (op_is_left_mergeable(key, Sh->b_size) &&
    162		    !(vn->vn_mode != M_DELETE
    163		      || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
    164			/*
    165			 * we delete last item and it could be merged
    166			 * with right neighbor's first item
    167			 */
    168			if (!
    169			    (B_NR_ITEMS(Sh) == 1
    170			     && is_direntry_le_ih(item_head(Sh, 0))
    171			     && ih_entry_count(item_head(Sh, 0)) == 1)) {
    172				/*
    173				 * node contains more than 1 item, or item
    174				 * is not directory item, or this item
    175				 * contains more than 1 entry
    176				 */
    177				print_block(Sh, 0, -1, -1);
    178				reiserfs_panic(tb->tb_sb, "vs-8045",
    179					       "rdkey %k, affected item==%d "
    180					       "(mode==%c) Must be %c",
    181					       key, vn->vn_affected_item_num,
    182					       vn->vn_mode, M_DELETE);
    183			}
    184		}
    185#endif
    186
    187	}
    188}
    189
    190/*
    191 * Using virtual node check, how many items can be
    192 * shifted to left neighbor
    193 */
    194static void check_left(struct tree_balance *tb, int h, int cur_free)
    195{
    196	int i;
    197	struct virtual_node *vn = tb->tb_vn;
    198	struct virtual_item *vi;
    199	int d_size, ih_size;
    200
    201	RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
    202
    203	/* internal level */
    204	if (h > 0) {
    205		tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
    206		return;
    207	}
    208
    209	/* leaf level */
    210
    211	if (!cur_free || !vn->vn_nr_item) {
    212		/* no free space or nothing to move */
    213		tb->lnum[h] = 0;
    214		tb->lbytes = -1;
    215		return;
    216	}
    217
    218	RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
    219	       "vs-8055: parent does not exist or invalid");
    220
    221	vi = vn->vn_vi;
    222	if ((unsigned int)cur_free >=
    223	    (vn->vn_size -
    224	     ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
    225		/* all contents of S[0] fits into L[0] */
    226
    227		RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
    228		       "vs-8055: invalid mode or balance condition failed");
    229
    230		tb->lnum[0] = vn->vn_nr_item;
    231		tb->lbytes = -1;
    232		return;
    233	}
    234
    235	d_size = 0, ih_size = IH_SIZE;
    236
    237	/* first item may be merge with last item in left neighbor */
    238	if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
    239		d_size = -((int)IH_SIZE), ih_size = 0;
    240
    241	tb->lnum[0] = 0;
    242	for (i = 0; i < vn->vn_nr_item;
    243	     i++, ih_size = IH_SIZE, d_size = 0, vi++) {
    244		d_size += vi->vi_item_len;
    245		if (cur_free >= d_size) {
    246			/* the item can be shifted entirely */
    247			cur_free -= d_size;
    248			tb->lnum[0]++;
    249			continue;
    250		}
    251
    252		/* the item cannot be shifted entirely, try to split it */
    253		/*
    254		 * check whether L[0] can hold ih and at least one byte
    255		 * of the item body
    256		 */
    257
    258		/* cannot shift even a part of the current item */
    259		if (cur_free <= ih_size) {
    260			tb->lbytes = -1;
    261			return;
    262		}
    263		cur_free -= ih_size;
    264
    265		tb->lbytes = op_check_left(vi, cur_free, 0, 0);
    266		if (tb->lbytes != -1)
    267			/* count partially shifted item */
    268			tb->lnum[0]++;
    269
    270		break;
    271	}
    272
    273	return;
    274}
    275
    276/*
    277 * Using virtual node check, how many items can be
    278 * shifted to right neighbor
    279 */
    280static void check_right(struct tree_balance *tb, int h, int cur_free)
    281{
    282	int i;
    283	struct virtual_node *vn = tb->tb_vn;
    284	struct virtual_item *vi;
    285	int d_size, ih_size;
    286
    287	RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
    288
    289	/* internal level */
    290	if (h > 0) {
    291		tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
    292		return;
    293	}
    294
    295	/* leaf level */
    296
    297	if (!cur_free || !vn->vn_nr_item) {
    298		/* no free space  */
    299		tb->rnum[h] = 0;
    300		tb->rbytes = -1;
    301		return;
    302	}
    303
    304	RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
    305	       "vs-8075: parent does not exist or invalid");
    306
    307	vi = vn->vn_vi + vn->vn_nr_item - 1;
    308	if ((unsigned int)cur_free >=
    309	    (vn->vn_size -
    310	     ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
    311		/* all contents of S[0] fits into R[0] */
    312
    313		RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
    314		       "vs-8080: invalid mode or balance condition failed");
    315
    316		tb->rnum[h] = vn->vn_nr_item;
    317		tb->rbytes = -1;
    318		return;
    319	}
    320
    321	d_size = 0, ih_size = IH_SIZE;
    322
    323	/* last item may be merge with first item in right neighbor */
    324	if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
    325		d_size = -(int)IH_SIZE, ih_size = 0;
    326
    327	tb->rnum[0] = 0;
    328	for (i = vn->vn_nr_item - 1; i >= 0;
    329	     i--, d_size = 0, ih_size = IH_SIZE, vi--) {
    330		d_size += vi->vi_item_len;
    331		if (cur_free >= d_size) {
    332			/* the item can be shifted entirely */
    333			cur_free -= d_size;
    334			tb->rnum[0]++;
    335			continue;
    336		}
    337
    338		/*
    339		 * check whether R[0] can hold ih and at least one
    340		 * byte of the item body
    341		 */
    342
    343		/* cannot shift even a part of the current item */
    344		if (cur_free <= ih_size) {
    345			tb->rbytes = -1;
    346			return;
    347		}
    348
    349		/*
    350		 * R[0] can hold the header of the item and at least
    351		 * one byte of its body
    352		 */
    353		cur_free -= ih_size;	/* cur_free is still > 0 */
    354
    355		tb->rbytes = op_check_right(vi, cur_free);
    356		if (tb->rbytes != -1)
    357			/* count partially shifted item */
    358			tb->rnum[0]++;
    359
    360		break;
    361	}
    362
    363	return;
    364}
    365
    366/*
    367 * from - number of items, which are shifted to left neighbor entirely
    368 * to - number of item, which are shifted to right neighbor entirely
    369 * from_bytes - number of bytes of boundary item (or directory entries)
    370 *              which are shifted to left neighbor
    371 * to_bytes - number of bytes of boundary item (or directory entries)
    372 *            which are shifted to right neighbor
    373 */
    374static int get_num_ver(int mode, struct tree_balance *tb, int h,
    375		       int from, int from_bytes,
    376		       int to, int to_bytes, short *snum012, int flow)
    377{
    378	int i;
    379	int units;
    380	struct virtual_node *vn = tb->tb_vn;
    381	int total_node_size, max_node_size, current_item_size;
    382	int needed_nodes;
    383
    384	/* position of item we start filling node from */
    385	int start_item;
    386
    387	/* position of item we finish filling node by */
    388	int end_item;
    389
    390	/*
    391	 * number of first bytes (entries for directory) of start_item-th item
    392	 * we do not include into node that is being filled
    393	 */
    394	int start_bytes;
    395
    396	/*
    397	 * number of last bytes (entries for directory) of end_item-th item
    398	 * we do node include into node that is being filled
    399	 */
    400	int end_bytes;
    401
    402	/*
    403	 * these are positions in virtual item of items, that are split
    404	 * between S[0] and S1new and S1new and S2new
    405	 */
    406	int split_item_positions[2];
    407
    408	split_item_positions[0] = -1;
    409	split_item_positions[1] = -1;
    410
    411	/*
    412	 * We only create additional nodes if we are in insert or paste mode
    413	 * or we are in replace mode at the internal level. If h is 0 and
    414	 * the mode is M_REPLACE then in fix_nodes we change the mode to
    415	 * paste or insert before we get here in the code.
    416	 */
    417	RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
    418	       "vs-8100: insert_size < 0 in overflow");
    419
    420	max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
    421
    422	/*
    423	 * snum012 [0-2] - number of items, that lay
    424	 * to S[0], first new node and second new node
    425	 */
    426	snum012[3] = -1;	/* s1bytes */
    427	snum012[4] = -1;	/* s2bytes */
    428
    429	/* internal level */
    430	if (h > 0) {
    431		i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
    432		if (i == max_node_size)
    433			return 1;
    434		return (i / max_node_size + 1);
    435	}
    436
    437	/* leaf level */
    438	needed_nodes = 1;
    439	total_node_size = 0;
    440
    441	/* start from 'from'-th item */
    442	start_item = from;
    443	/* skip its first 'start_bytes' units */
    444	start_bytes = ((from_bytes != -1) ? from_bytes : 0);
    445
    446	/* last included item is the 'end_item'-th one */
    447	end_item = vn->vn_nr_item - to - 1;
    448	/* do not count last 'end_bytes' units of 'end_item'-th item */
    449	end_bytes = (to_bytes != -1) ? to_bytes : 0;
    450
    451	/*
    452	 * go through all item beginning from the start_item-th item
    453	 * and ending by the end_item-th item. Do not count first
    454	 * 'start_bytes' units of 'start_item'-th item and last
    455	 * 'end_bytes' of 'end_item'-th item
    456	 */
    457	for (i = start_item; i <= end_item; i++) {
    458		struct virtual_item *vi = vn->vn_vi + i;
    459		int skip_from_end = ((i == end_item) ? end_bytes : 0);
    460
    461		RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
    462
    463		/* get size of current item */
    464		current_item_size = vi->vi_item_len;
    465
    466		/*
    467		 * do not take in calculation head part (from_bytes)
    468		 * of from-th item
    469		 */
    470		current_item_size -=
    471		    op_part_size(vi, 0 /*from start */ , start_bytes);
    472
    473		/* do not take in calculation tail part of last item */
    474		current_item_size -=
    475		    op_part_size(vi, 1 /*from end */ , skip_from_end);
    476
    477		/* if item fits into current node entierly */
    478		if (total_node_size + current_item_size <= max_node_size) {
    479			snum012[needed_nodes - 1]++;
    480			total_node_size += current_item_size;
    481			start_bytes = 0;
    482			continue;
    483		}
    484
    485		/*
    486		 * virtual item length is longer, than max size of item in
    487		 * a node. It is impossible for direct item
    488		 */
    489		if (current_item_size > max_node_size) {
    490			RFALSE(is_direct_le_ih(vi->vi_ih),
    491			       "vs-8110: "
    492			       "direct item length is %d. It can not be longer than %d",
    493			       current_item_size, max_node_size);
    494			/* we will try to split it */
    495			flow = 1;
    496		}
    497
    498		/* as we do not split items, take new node and continue */
    499		if (!flow) {
    500			needed_nodes++;
    501			i--;
    502			total_node_size = 0;
    503			continue;
    504		}
    505
    506		/*
    507		 * calculate number of item units which fit into node being
    508		 * filled
    509		 */
    510		{
    511			int free_space;
    512
    513			free_space = max_node_size - total_node_size - IH_SIZE;
    514			units =
    515			    op_check_left(vi, free_space, start_bytes,
    516					  skip_from_end);
    517			/*
    518			 * nothing fits into current node, take new
    519			 * node and continue
    520			 */
    521			if (units == -1) {
    522				needed_nodes++, i--, total_node_size = 0;
    523				continue;
    524			}
    525		}
    526
    527		/* something fits into the current node */
    528		start_bytes += units;
    529		snum012[needed_nodes - 1 + 3] = units;
    530
    531		if (needed_nodes > 2)
    532			reiserfs_warning(tb->tb_sb, "vs-8111",
    533					 "split_item_position is out of range");
    534		snum012[needed_nodes - 1]++;
    535		split_item_positions[needed_nodes - 1] = i;
    536		needed_nodes++;
    537		/* continue from the same item with start_bytes != -1 */
    538		start_item = i;
    539		i--;
    540		total_node_size = 0;
    541	}
    542
    543	/*
    544	 * sum012[4] (if it is not -1) contains number of units of which
    545	 * are to be in S1new, snum012[3] - to be in S0. They are supposed
    546	 * to be S1bytes and S2bytes correspondingly, so recalculate
    547	 */
    548	if (snum012[4] > 0) {
    549		int split_item_num;
    550		int bytes_to_r, bytes_to_l;
    551		int bytes_to_S1new;
    552
    553		split_item_num = split_item_positions[1];
    554		bytes_to_l =
    555		    ((from == split_item_num
    556		      && from_bytes != -1) ? from_bytes : 0);
    557		bytes_to_r =
    558		    ((end_item == split_item_num
    559		      && end_bytes != -1) ? end_bytes : 0);
    560		bytes_to_S1new =
    561		    ((split_item_positions[0] ==
    562		      split_item_positions[1]) ? snum012[3] : 0);
    563
    564		/* s2bytes */
    565		snum012[4] =
    566		    op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
    567		    bytes_to_r - bytes_to_l - bytes_to_S1new;
    568
    569		if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
    570		    vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
    571			reiserfs_warning(tb->tb_sb, "vs-8115",
    572					 "not directory or indirect item");
    573	}
    574
    575	/* now we know S2bytes, calculate S1bytes */
    576	if (snum012[3] > 0) {
    577		int split_item_num;
    578		int bytes_to_r, bytes_to_l;
    579		int bytes_to_S2new;
    580
    581		split_item_num = split_item_positions[0];
    582		bytes_to_l =
    583		    ((from == split_item_num
    584		      && from_bytes != -1) ? from_bytes : 0);
    585		bytes_to_r =
    586		    ((end_item == split_item_num
    587		      && end_bytes != -1) ? end_bytes : 0);
    588		bytes_to_S2new =
    589		    ((split_item_positions[0] == split_item_positions[1]
    590		      && snum012[4] != -1) ? snum012[4] : 0);
    591
    592		/* s1bytes */
    593		snum012[3] =
    594		    op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
    595		    bytes_to_r - bytes_to_l - bytes_to_S2new;
    596	}
    597
    598	return needed_nodes;
    599}
    600
    601
    602/*
    603 * Set parameters for balancing.
    604 * Performs write of results of analysis of balancing into structure tb,
    605 * where it will later be used by the functions that actually do the balancing.
    606 * Parameters:
    607 *	tb	tree_balance structure;
    608 *	h	current level of the node;
    609 *	lnum	number of items from S[h] that must be shifted to L[h];
    610 *	rnum	number of items from S[h] that must be shifted to R[h];
    611 *	blk_num	number of blocks that S[h] will be splitted into;
    612 *	s012	number of items that fall into splitted nodes.
    613 *	lbytes	number of bytes which flow to the left neighbor from the
    614 *              item that is not shifted entirely
    615 *	rbytes	number of bytes which flow to the right neighbor from the
    616 *              item that is not shifted entirely
    617 *	s1bytes	number of bytes which flow to the first  new node when
    618 *              S[0] splits (this number is contained in s012 array)
    619 */
    620
    621static void set_parameters(struct tree_balance *tb, int h, int lnum,
    622			   int rnum, int blk_num, short *s012, int lb, int rb)
    623{
    624
    625	tb->lnum[h] = lnum;
    626	tb->rnum[h] = rnum;
    627	tb->blknum[h] = blk_num;
    628
    629	/* only for leaf level */
    630	if (h == 0) {
    631		if (s012 != NULL) {
    632			tb->s0num = *s012++;
    633			tb->snum[0] = *s012++;
    634			tb->snum[1] = *s012++;
    635			tb->sbytes[0] = *s012++;
    636			tb->sbytes[1] = *s012;
    637		}
    638		tb->lbytes = lb;
    639		tb->rbytes = rb;
    640	}
    641	PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
    642	PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
    643
    644	PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
    645	PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
    646}
    647
    648/*
    649 * check if node disappears if we shift tb->lnum[0] items to left
    650 * neighbor and tb->rnum[0] to the right one.
    651 */
    652static int is_leaf_removable(struct tree_balance *tb)
    653{
    654	struct virtual_node *vn = tb->tb_vn;
    655	int to_left, to_right;
    656	int size;
    657	int remain_items;
    658
    659	/*
    660	 * number of items that will be shifted to left (right) neighbor
    661	 * entirely
    662	 */
    663	to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
    664	to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
    665	remain_items = vn->vn_nr_item;
    666
    667	/* how many items remain in S[0] after shiftings to neighbors */
    668	remain_items -= (to_left + to_right);
    669
    670	/* all content of node can be shifted to neighbors */
    671	if (remain_items < 1) {
    672		set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
    673			       NULL, -1, -1);
    674		return 1;
    675	}
    676
    677	/* S[0] is not removable */
    678	if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
    679		return 0;
    680
    681	/* check whether we can divide 1 remaining item between neighbors */
    682
    683	/* get size of remaining item (in item units) */
    684	size = op_unit_num(&vn->vn_vi[to_left]);
    685
    686	if (tb->lbytes + tb->rbytes >= size) {
    687		set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
    688			       tb->lbytes, -1);
    689		return 1;
    690	}
    691
    692	return 0;
    693}
    694
    695/* check whether L, S, R can be joined in one node */
    696static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
    697{
    698	struct virtual_node *vn = tb->tb_vn;
    699	int ih_size;
    700	struct buffer_head *S0;
    701
    702	S0 = PATH_H_PBUFFER(tb->tb_path, 0);
    703
    704	ih_size = 0;
    705	if (vn->vn_nr_item) {
    706		if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
    707			ih_size += IH_SIZE;
    708
    709		if (vn->vn_vi[vn->vn_nr_item - 1].
    710		    vi_type & VI_TYPE_RIGHT_MERGEABLE)
    711			ih_size += IH_SIZE;
    712	} else {
    713		/* there was only one item and it will be deleted */
    714		struct item_head *ih;
    715
    716		RFALSE(B_NR_ITEMS(S0) != 1,
    717		       "vs-8125: item number must be 1: it is %d",
    718		       B_NR_ITEMS(S0));
    719
    720		ih = item_head(S0, 0);
    721		if (tb->CFR[0]
    722		    && !comp_short_le_keys(&ih->ih_key,
    723					   internal_key(tb->CFR[0],
    724							  tb->rkey[0])))
    725			/*
    726			 * Directory must be in correct state here: that is
    727			 * somewhere at the left side should exist first
    728			 * directory item. But the item being deleted can
    729			 * not be that first one because its right neighbor
    730			 * is item of the same directory. (But first item
    731			 * always gets deleted in last turn). So, neighbors
    732			 * of deleted item can be merged, so we can save
    733			 * ih_size
    734			 */
    735			if (is_direntry_le_ih(ih)) {
    736				ih_size = IH_SIZE;
    737
    738				/*
    739				 * we might check that left neighbor exists
    740				 * and is of the same directory
    741				 */
    742				RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
    743				       "vs-8130: first directory item can not be removed until directory is not empty");
    744			}
    745
    746	}
    747
    748	if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
    749		set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
    750		PROC_INFO_INC(tb->tb_sb, leaves_removable);
    751		return 1;
    752	}
    753	return 0;
    754
    755}
    756
    757/* when we do not split item, lnum and rnum are numbers of entire items */
    758#define SET_PAR_SHIFT_LEFT \
    759if (h)\
    760{\
    761   int to_l;\
    762   \
    763   to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
    764	      (MAX_NR_KEY(Sh) + 1 - lpar);\
    765	      \
    766	      set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
    767}\
    768else \
    769{\
    770   if (lset==LEFT_SHIFT_FLOW)\
    771     set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
    772		     tb->lbytes, -1);\
    773   else\
    774     set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
    775		     -1, -1);\
    776}
    777
    778#define SET_PAR_SHIFT_RIGHT \
    779if (h)\
    780{\
    781   int to_r;\
    782   \
    783   to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
    784   \
    785   set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
    786}\
    787else \
    788{\
    789   if (rset==RIGHT_SHIFT_FLOW)\
    790     set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
    791		  -1, tb->rbytes);\
    792   else\
    793     set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
    794		  -1, -1);\
    795}
    796
    797static void free_buffers_in_tb(struct tree_balance *tb)
    798{
    799	int i;
    800
    801	pathrelse(tb->tb_path);
    802
    803	for (i = 0; i < MAX_HEIGHT; i++) {
    804		brelse(tb->L[i]);
    805		brelse(tb->R[i]);
    806		brelse(tb->FL[i]);
    807		brelse(tb->FR[i]);
    808		brelse(tb->CFL[i]);
    809		brelse(tb->CFR[i]);
    810
    811		tb->L[i] = NULL;
    812		tb->R[i] = NULL;
    813		tb->FL[i] = NULL;
    814		tb->FR[i] = NULL;
    815		tb->CFL[i] = NULL;
    816		tb->CFR[i] = NULL;
    817	}
    818}
    819
    820/*
    821 * Get new buffers for storing new nodes that are created while balancing.
    822 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
    823 *	        CARRY_ON - schedule didn't occur while the function worked;
    824 *	        NO_DISK_SPACE - no disk space.
    825 */
    826/* The function is NOT SCHEDULE-SAFE! */
    827static int get_empty_nodes(struct tree_balance *tb, int h)
    828{
    829	struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h);
    830	b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
    831	int counter, number_of_freeblk;
    832	int  amount_needed;	/* number of needed empty blocks */
    833	int  retval = CARRY_ON;
    834	struct super_block *sb = tb->tb_sb;
    835
    836	/*
    837	 * number_of_freeblk is the number of empty blocks which have been
    838	 * acquired for use by the balancing algorithm minus the number of
    839	 * empty blocks used in the previous levels of the analysis,
    840	 * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule
    841	 * occurs after empty blocks are acquired, and the balancing analysis
    842	 * is then restarted, amount_needed is the number needed by this
    843	 * level (h) of the balancing analysis.
    844	 *
    845	 * Note that for systems with many processes writing, it would be
    846	 * more layout optimal to calculate the total number needed by all
    847	 * levels and then to run reiserfs_new_blocks to get all of them at
    848	 * once.
    849	 */
    850
    851	/*
    852	 * Initiate number_of_freeblk to the amount acquired prior to the
    853	 * restart of the analysis or 0 if not restarted, then subtract the
    854	 * amount needed by all of the levels of the tree below h.
    855	 */
    856	/* blknum includes S[h], so we subtract 1 in this calculation */
    857	for (counter = 0, number_of_freeblk = tb->cur_blknum;
    858	     counter < h; counter++)
    859		number_of_freeblk -=
    860		    (tb->blknum[counter]) ? (tb->blknum[counter] -
    861						   1) : 0;
    862
    863	/* Allocate missing empty blocks. */
    864	/* if Sh == 0  then we are getting a new root */
    865	amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
    866	/*
    867	 * Amount_needed = the amount that we need more than the
    868	 * amount that we have.
    869	 */
    870	if (amount_needed > number_of_freeblk)
    871		amount_needed -= number_of_freeblk;
    872	else	/* If we have enough already then there is nothing to do. */
    873		return CARRY_ON;
    874
    875	/*
    876	 * No need to check quota - is not allocated for blocks used
    877	 * for formatted nodes
    878	 */
    879	if (reiserfs_new_form_blocknrs(tb, blocknrs,
    880				       amount_needed) == NO_DISK_SPACE)
    881		return NO_DISK_SPACE;
    882
    883	/* for each blocknumber we just got, get a buffer and stick it on FEB */
    884	for (blocknr = blocknrs, counter = 0;
    885	     counter < amount_needed; blocknr++, counter++) {
    886
    887		RFALSE(!*blocknr,
    888		       "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
    889
    890		new_bh = sb_getblk(sb, *blocknr);
    891		RFALSE(buffer_dirty(new_bh) ||
    892		       buffer_journaled(new_bh) ||
    893		       buffer_journal_dirty(new_bh),
    894		       "PAP-8140: journaled or dirty buffer %b for the new block",
    895		       new_bh);
    896
    897		/* Put empty buffers into the array. */
    898		RFALSE(tb->FEB[tb->cur_blknum],
    899		       "PAP-8141: busy slot for new buffer");
    900
    901		set_buffer_journal_new(new_bh);
    902		tb->FEB[tb->cur_blknum++] = new_bh;
    903	}
    904
    905	if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
    906		retval = REPEAT_SEARCH;
    907
    908	return retval;
    909}
    910
    911/*
    912 * Get free space of the left neighbor, which is stored in the parent
    913 * node of the left neighbor.
    914 */
    915static int get_lfree(struct tree_balance *tb, int h)
    916{
    917	struct buffer_head *l, *f;
    918	int order;
    919
    920	if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
    921	    (l = tb->FL[h]) == NULL)
    922		return 0;
    923
    924	if (f == l)
    925		order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
    926	else {
    927		order = B_NR_ITEMS(l);
    928		f = l;
    929	}
    930
    931	return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
    932}
    933
    934/*
    935 * Get free space of the right neighbor,
    936 * which is stored in the parent node of the right neighbor.
    937 */
    938static int get_rfree(struct tree_balance *tb, int h)
    939{
    940	struct buffer_head *r, *f;
    941	int order;
    942
    943	if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
    944	    (r = tb->FR[h]) == NULL)
    945		return 0;
    946
    947	if (f == r)
    948		order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
    949	else {
    950		order = 0;
    951		f = r;
    952	}
    953
    954	return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
    955
    956}
    957
    958/* Check whether left neighbor is in memory. */
    959static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
    960{
    961	struct buffer_head *father, *left;
    962	struct super_block *sb = tb->tb_sb;
    963	b_blocknr_t left_neighbor_blocknr;
    964	int left_neighbor_position;
    965
    966	/* Father of the left neighbor does not exist. */
    967	if (!tb->FL[h])
    968		return 0;
    969
    970	/* Calculate father of the node to be balanced. */
    971	father = PATH_H_PBUFFER(tb->tb_path, h + 1);
    972
    973	RFALSE(!father ||
    974	       !B_IS_IN_TREE(father) ||
    975	       !B_IS_IN_TREE(tb->FL[h]) ||
    976	       !buffer_uptodate(father) ||
    977	       !buffer_uptodate(tb->FL[h]),
    978	       "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
    979	       father, tb->FL[h]);
    980
    981	/*
    982	 * Get position of the pointer to the left neighbor
    983	 * into the left father.
    984	 */
    985	left_neighbor_position = (father == tb->FL[h]) ?
    986	    tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
    987	/* Get left neighbor block number. */
    988	left_neighbor_blocknr =
    989	    B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
    990	/* Look for the left neighbor in the cache. */
    991	if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) {
    992
    993		RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
    994		       "vs-8170: left neighbor (%b %z) is not in the tree",
    995		       left, left);
    996		put_bh(left);
    997		return 1;
    998	}
    999
   1000	return 0;
   1001}
   1002
   1003#define LEFT_PARENTS  'l'
   1004#define RIGHT_PARENTS 'r'
   1005
   1006static void decrement_key(struct cpu_key *key)
   1007{
   1008	/* call item specific function for this key */
   1009	item_ops[cpu_key_k_type(key)]->decrement_key(key);
   1010}
   1011
   1012/*
   1013 * Calculate far left/right parent of the left/right neighbor of the
   1014 * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor
   1015 * of the parent F[h].
   1016 * Calculate left/right common parent of the current node and L[h]/R[h].
   1017 * Calculate left/right delimiting key position.
   1018 * Returns:	PATH_INCORRECT    - path in the tree is not correct
   1019 *		SCHEDULE_OCCURRED - schedule occurred while the function worked
   1020 *	        CARRY_ON          - schedule didn't occur while the function
   1021 *				    worked
   1022 */
   1023static int get_far_parent(struct tree_balance *tb,
   1024			  int h,
   1025			  struct buffer_head **pfather,
   1026			  struct buffer_head **pcom_father, char c_lr_par)
   1027{
   1028	struct buffer_head *parent;
   1029	INITIALIZE_PATH(s_path_to_neighbor_father);
   1030	struct treepath *path = tb->tb_path;
   1031	struct cpu_key s_lr_father_key;
   1032	int counter,
   1033	    position = INT_MAX,
   1034	    first_last_position = 0,
   1035	    path_offset = PATH_H_PATH_OFFSET(path, h);
   1036
   1037	/*
   1038	 * Starting from F[h] go upwards in the tree, and look for the common
   1039	 * ancestor of F[h], and its neighbor l/r, that should be obtained.
   1040	 */
   1041
   1042	counter = path_offset;
   1043
   1044	RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET,
   1045	       "PAP-8180: invalid path length");
   1046
   1047	for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {
   1048		/*
   1049		 * Check whether parent of the current buffer in the path
   1050		 * is really parent in the tree.
   1051		 */
   1052		if (!B_IS_IN_TREE
   1053		    (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))
   1054			return REPEAT_SEARCH;
   1055
   1056		/* Check whether position in the parent is correct. */
   1057		if ((position =
   1058		     PATH_OFFSET_POSITION(path,
   1059					  counter - 1)) >
   1060		    B_NR_ITEMS(parent))
   1061			return REPEAT_SEARCH;
   1062
   1063		/*
   1064		 * Check whether parent at the path really points
   1065		 * to the child.
   1066		 */
   1067		if (B_N_CHILD_NUM(parent, position) !=
   1068		    PATH_OFFSET_PBUFFER(path, counter)->b_blocknr)
   1069			return REPEAT_SEARCH;
   1070
   1071		/*
   1072		 * Return delimiting key if position in the parent is not
   1073		 * equal to first/last one.
   1074		 */
   1075		if (c_lr_par == RIGHT_PARENTS)
   1076			first_last_position = B_NR_ITEMS(parent);
   1077		if (position != first_last_position) {
   1078			*pcom_father = parent;
   1079			get_bh(*pcom_father);
   1080			/*(*pcom_father = parent)->b_count++; */
   1081			break;
   1082		}
   1083	}
   1084
   1085	/* if we are in the root of the tree, then there is no common father */
   1086	if (counter == FIRST_PATH_ELEMENT_OFFSET) {
   1087		/*
   1088		 * Check whether first buffer in the path is the
   1089		 * root of the tree.
   1090		 */
   1091		if (PATH_OFFSET_PBUFFER
   1092		    (tb->tb_path,
   1093		     FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
   1094		    SB_ROOT_BLOCK(tb->tb_sb)) {
   1095			*pfather = *pcom_father = NULL;
   1096			return CARRY_ON;
   1097		}
   1098		return REPEAT_SEARCH;
   1099	}
   1100
   1101	RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL,
   1102	       "PAP-8185: (%b %z) level too small",
   1103	       *pcom_father, *pcom_father);
   1104
   1105	/* Check whether the common parent is locked. */
   1106
   1107	if (buffer_locked(*pcom_father)) {
   1108
   1109		/* Release the write lock while the buffer is busy */
   1110		int depth = reiserfs_write_unlock_nested(tb->tb_sb);
   1111		__wait_on_buffer(*pcom_father);
   1112		reiserfs_write_lock_nested(tb->tb_sb, depth);
   1113		if (FILESYSTEM_CHANGED_TB(tb)) {
   1114			brelse(*pcom_father);
   1115			return REPEAT_SEARCH;
   1116		}
   1117	}
   1118
   1119	/*
   1120	 * So, we got common parent of the current node and its
   1121	 * left/right neighbor.  Now we are getting the parent of the
   1122	 * left/right neighbor.
   1123	 */
   1124
   1125	/* Form key to get parent of the left/right neighbor. */
   1126	le_key2cpu_key(&s_lr_father_key,
   1127		       internal_key(*pcom_father,
   1128				      (c_lr_par ==
   1129				       LEFT_PARENTS) ? (tb->lkey[h - 1] =
   1130							position -
   1131							1) : (tb->rkey[h -
   1132									   1] =
   1133							      position)));
   1134
   1135	if (c_lr_par == LEFT_PARENTS)
   1136		decrement_key(&s_lr_father_key);
   1137
   1138	if (search_by_key
   1139	    (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
   1140	     h + 1) == IO_ERROR)
   1141		/* path is released */
   1142		return IO_ERROR;
   1143
   1144	if (FILESYSTEM_CHANGED_TB(tb)) {
   1145		pathrelse(&s_path_to_neighbor_father);
   1146		brelse(*pcom_father);
   1147		return REPEAT_SEARCH;
   1148	}
   1149
   1150	*pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
   1151
   1152	RFALSE(B_LEVEL(*pfather) != h + 1,
   1153	       "PAP-8190: (%b %z) level too small", *pfather, *pfather);
   1154	RFALSE(s_path_to_neighbor_father.path_length <
   1155	       FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
   1156
   1157	s_path_to_neighbor_father.path_length--;
   1158	pathrelse(&s_path_to_neighbor_father);
   1159	return CARRY_ON;
   1160}
   1161
   1162/*
   1163 * Get parents of neighbors of node in the path(S[path_offset]) and
   1164 * common parents of S[path_offset] and L[path_offset]/R[path_offset]:
   1165 * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],
   1166 * CFR[path_offset].
   1167 * Calculate numbers of left and right delimiting keys position:
   1168 * lkey[path_offset], rkey[path_offset].
   1169 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked
   1170 *	        CARRY_ON - schedule didn't occur while the function worked
   1171 */
   1172static int get_parents(struct tree_balance *tb, int h)
   1173{
   1174	struct treepath *path = tb->tb_path;
   1175	int position,
   1176	    ret,
   1177	    path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
   1178	struct buffer_head *curf, *curcf;
   1179
   1180	/* Current node is the root of the tree or will be root of the tree */
   1181	if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
   1182		/*
   1183		 * The root can not have parents.
   1184		 * Release nodes which previously were obtained as
   1185		 * parents of the current node neighbors.
   1186		 */
   1187		brelse(tb->FL[h]);
   1188		brelse(tb->CFL[h]);
   1189		brelse(tb->FR[h]);
   1190		brelse(tb->CFR[h]);
   1191		tb->FL[h]  = NULL;
   1192		tb->CFL[h] = NULL;
   1193		tb->FR[h]  = NULL;
   1194		tb->CFR[h] = NULL;
   1195		return CARRY_ON;
   1196	}
   1197
   1198	/* Get parent FL[path_offset] of L[path_offset]. */
   1199	position = PATH_OFFSET_POSITION(path, path_offset - 1);
   1200	if (position) {
   1201		/* Current node is not the first child of its parent. */
   1202		curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
   1203		curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
   1204		get_bh(curf);
   1205		get_bh(curf);
   1206		tb->lkey[h] = position - 1;
   1207	} else {
   1208		/*
   1209		 * Calculate current parent of L[path_offset], which is the
   1210		 * left neighbor of the current node.  Calculate current
   1211		 * common parent of L[path_offset] and the current node.
   1212		 * Note that CFL[path_offset] not equal FL[path_offset] and
   1213		 * CFL[path_offset] not equal F[path_offset].
   1214		 * Calculate lkey[path_offset].
   1215		 */
   1216		if ((ret = get_far_parent(tb, h + 1, &curf,
   1217						  &curcf,
   1218						  LEFT_PARENTS)) != CARRY_ON)
   1219			return ret;
   1220	}
   1221
   1222	brelse(tb->FL[h]);
   1223	tb->FL[h] = curf;	/* New initialization of FL[h]. */
   1224	brelse(tb->CFL[h]);
   1225	tb->CFL[h] = curcf;	/* New initialization of CFL[h]. */
   1226
   1227	RFALSE((curf && !B_IS_IN_TREE(curf)) ||
   1228	       (curcf && !B_IS_IN_TREE(curcf)),
   1229	       "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf);
   1230
   1231	/* Get parent FR[h] of R[h]. */
   1232
   1233	/* Current node is the last child of F[h]. FR[h] != F[h]. */
   1234	if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {
   1235		/*
   1236		 * Calculate current parent of R[h], which is the right
   1237		 * neighbor of F[h].  Calculate current common parent of
   1238		 * R[h] and current node. Note that CFR[h] not equal
   1239		 * FR[path_offset] and CFR[h] not equal F[h].
   1240		 */
   1241		if ((ret =
   1242		     get_far_parent(tb, h + 1, &curf, &curcf,
   1243				    RIGHT_PARENTS)) != CARRY_ON)
   1244			return ret;
   1245	} else {
   1246		/* Current node is not the last child of its parent F[h]. */
   1247		curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
   1248		curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
   1249		get_bh(curf);
   1250		get_bh(curf);
   1251		tb->rkey[h] = position;
   1252	}
   1253
   1254	brelse(tb->FR[h]);
   1255	/* New initialization of FR[path_offset]. */
   1256	tb->FR[h] = curf;
   1257
   1258	brelse(tb->CFR[h]);
   1259	/* New initialization of CFR[path_offset]. */
   1260	tb->CFR[h] = curcf;
   1261
   1262	RFALSE((curf && !B_IS_IN_TREE(curf)) ||
   1263	       (curcf && !B_IS_IN_TREE(curcf)),
   1264	       "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf);
   1265
   1266	return CARRY_ON;
   1267}
   1268
   1269/*
   1270 * it is possible to remove node as result of shiftings to
   1271 * neighbors even when we insert or paste item.
   1272 */
   1273static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
   1274				      struct tree_balance *tb, int h)
   1275{
   1276	struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
   1277	int levbytes = tb->insert_size[h];
   1278	struct item_head *ih;
   1279	struct reiserfs_key *r_key = NULL;
   1280
   1281	ih = item_head(Sh, 0);
   1282	if (tb->CFR[h])
   1283		r_key = internal_key(tb->CFR[h], tb->rkey[h]);
   1284
   1285	if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
   1286	    /* shifting may merge items which might save space */
   1287	    -
   1288	    ((!h
   1289	      && op_is_left_mergeable(&ih->ih_key, Sh->b_size)) ? IH_SIZE : 0)
   1290	    -
   1291	    ((!h && r_key
   1292	      && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
   1293	    + ((h) ? KEY_SIZE : 0)) {
   1294		/* node can not be removed */
   1295		if (sfree >= levbytes) {
   1296			/* new item fits into node S[h] without any shifting */
   1297			if (!h)
   1298				tb->s0num =
   1299				    B_NR_ITEMS(Sh) +
   1300				    ((mode == M_INSERT) ? 1 : 0);
   1301			set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
   1302			return NO_BALANCING_NEEDED;
   1303		}
   1304	}
   1305	PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
   1306	return !NO_BALANCING_NEEDED;
   1307}
   1308
   1309/*
   1310 * Check whether current node S[h] is balanced when increasing its size by
   1311 * Inserting or Pasting.
   1312 * Calculate parameters for balancing for current level h.
   1313 * Parameters:
   1314 *	tb	tree_balance structure;
   1315 *	h	current level of the node;
   1316 *	inum	item number in S[h];
   1317 *	mode	i - insert, p - paste;
   1318 * Returns:	1 - schedule occurred;
   1319 *	        0 - balancing for higher levels needed;
   1320 *	       -1 - no balancing for higher levels needed;
   1321 *	       -2 - no disk space.
   1322 */
   1323/* ip means Inserting or Pasting */
   1324static int ip_check_balance(struct tree_balance *tb, int h)
   1325{
   1326	struct virtual_node *vn = tb->tb_vn;
   1327	/*
   1328	 * Number of bytes that must be inserted into (value is negative
   1329	 * if bytes are deleted) buffer which contains node being balanced.
   1330	 * The mnemonic is that the attempted change in node space used
   1331	 * level is levbytes bytes.
   1332	 */
   1333	int levbytes;
   1334	int ret;
   1335
   1336	int lfree, sfree, rfree /* free space in L, S and R */ ;
   1337
   1338	/*
   1339	 * nver is short for number of vertixes, and lnver is the number if
   1340	 * we shift to the left, rnver is the number if we shift to the
   1341	 * right, and lrnver is the number if we shift in both directions.
   1342	 * The goal is to minimize first the number of vertixes, and second,
   1343	 * the number of vertixes whose contents are changed by shifting,
   1344	 * and third the number of uncached vertixes whose contents are
   1345	 * changed by shifting and must be read from disk.
   1346	 */
   1347	int nver, lnver, rnver, lrnver;
   1348
   1349	/*
   1350	 * used at leaf level only, S0 = S[0] is the node being balanced,
   1351	 * sInum [ I = 0,1,2 ] is the number of items that will
   1352	 * remain in node SI after balancing.  S1 and S2 are new
   1353	 * nodes that might be created.
   1354	 */
   1355
   1356	/*
   1357	 * we perform 8 calls to get_num_ver().  For each call we
   1358	 * calculate five parameters.  where 4th parameter is s1bytes
   1359	 * and 5th - s2bytes
   1360	 *
   1361	 * s0num, s1num, s2num for 8 cases
   1362	 * 0,1 - do not shift and do not shift but bottle
   1363	 * 2   - shift only whole item to left
   1364	 * 3   - shift to left and bottle as much as possible
   1365	 * 4,5 - shift to right (whole items and as much as possible
   1366	 * 6,7 - shift to both directions (whole items and as much as possible)
   1367	 */
   1368	short snum012[40] = { 0, };
   1369
   1370	/* Sh is the node whose balance is currently being checked */
   1371	struct buffer_head *Sh;
   1372
   1373	Sh = PATH_H_PBUFFER(tb->tb_path, h);
   1374	levbytes = tb->insert_size[h];
   1375
   1376	/* Calculate balance parameters for creating new root. */
   1377	if (!Sh) {
   1378		if (!h)
   1379			reiserfs_panic(tb->tb_sb, "vs-8210",
   1380				       "S[0] can not be 0");
   1381		switch (ret = get_empty_nodes(tb, h)) {
   1382		/* no balancing for higher levels needed */
   1383		case CARRY_ON:
   1384			set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
   1385			return NO_BALANCING_NEEDED;
   1386
   1387		case NO_DISK_SPACE:
   1388		case REPEAT_SEARCH:
   1389			return ret;
   1390		default:
   1391			reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
   1392				       "return value of get_empty_nodes");
   1393		}
   1394	}
   1395
   1396	/* get parents of S[h] neighbors. */
   1397	ret = get_parents(tb, h);
   1398	if (ret != CARRY_ON)
   1399		return ret;
   1400
   1401	sfree = B_FREE_SPACE(Sh);
   1402
   1403	/* get free space of neighbors */
   1404	rfree = get_rfree(tb, h);
   1405	lfree = get_lfree(tb, h);
   1406
   1407	/* and new item fits into node S[h] without any shifting */
   1408	if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
   1409	    NO_BALANCING_NEEDED)
   1410		return NO_BALANCING_NEEDED;
   1411
   1412	create_virtual_node(tb, h);
   1413
   1414	/*
   1415	 * determine maximal number of items we can shift to the left
   1416	 * neighbor (in tb structure) and the maximal number of bytes
   1417	 * that can flow to the left neighbor from the left most liquid
   1418	 * item that cannot be shifted from S[0] entirely (returned value)
   1419	 */
   1420	check_left(tb, h, lfree);
   1421
   1422	/*
   1423	 * determine maximal number of items we can shift to the right
   1424	 * neighbor (in tb structure) and the maximal number of bytes
   1425	 * that can flow to the right neighbor from the right most liquid
   1426	 * item that cannot be shifted from S[0] entirely (returned value)
   1427	 */
   1428	check_right(tb, h, rfree);
   1429
   1430	/*
   1431	 * all contents of internal node S[h] can be moved into its
   1432	 * neighbors, S[h] will be removed after balancing
   1433	 */
   1434	if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
   1435		int to_r;
   1436
   1437		/*
   1438		 * Since we are working on internal nodes, and our internal
   1439		 * nodes have fixed size entries, then we can balance by the
   1440		 * number of items rather than the space they consume.  In this
   1441		 * routine we set the left node equal to the right node,
   1442		 * allowing a difference of less than or equal to 1 child
   1443		 * pointer.
   1444		 */
   1445		to_r =
   1446		    ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
   1447		     vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
   1448						tb->rnum[h]);
   1449		set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
   1450			       -1, -1);
   1451		return CARRY_ON;
   1452	}
   1453
   1454	/*
   1455	 * this checks balance condition, that any two neighboring nodes
   1456	 * can not fit in one node
   1457	 */
   1458	RFALSE(h &&
   1459	       (tb->lnum[h] >= vn->vn_nr_item + 1 ||
   1460		tb->rnum[h] >= vn->vn_nr_item + 1),
   1461	       "vs-8220: tree is not balanced on internal level");
   1462	RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
   1463		      (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
   1464	       "vs-8225: tree is not balanced on leaf level");
   1465
   1466	/*
   1467	 * all contents of S[0] can be moved into its neighbors
   1468	 * S[0] will be removed after balancing.
   1469	 */
   1470	if (!h && is_leaf_removable(tb))
   1471		return CARRY_ON;
   1472
   1473	/*
   1474	 * why do we perform this check here rather than earlier??
   1475	 * Answer: we can win 1 node in some cases above. Moreover we
   1476	 * checked it above, when we checked, that S[0] is not removable
   1477	 * in principle
   1478	 */
   1479
   1480	 /* new item fits into node S[h] without any shifting */
   1481	if (sfree >= levbytes) {
   1482		if (!h)
   1483			tb->s0num = vn->vn_nr_item;
   1484		set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
   1485		return NO_BALANCING_NEEDED;
   1486	}
   1487
   1488	{
   1489		int lpar, rpar, nset, lset, rset, lrset;
   1490		/* regular overflowing of the node */
   1491
   1492		/*
   1493		 * get_num_ver works in 2 modes (FLOW & NO_FLOW)
   1494		 * lpar, rpar - number of items we can shift to left/right
   1495		 *              neighbor (including splitting item)
   1496		 * nset, lset, rset, lrset - shows, whether flowing items
   1497		 *                           give better packing
   1498		 */
   1499#define FLOW 1
   1500#define NO_FLOW 0		/* do not any splitting */
   1501
   1502		/* we choose one of the following */
   1503#define NOTHING_SHIFT_NO_FLOW	0
   1504#define NOTHING_SHIFT_FLOW	5
   1505#define LEFT_SHIFT_NO_FLOW	10
   1506#define LEFT_SHIFT_FLOW		15
   1507#define RIGHT_SHIFT_NO_FLOW	20
   1508#define RIGHT_SHIFT_FLOW	25
   1509#define LR_SHIFT_NO_FLOW	30
   1510#define LR_SHIFT_FLOW		35
   1511
   1512		lpar = tb->lnum[h];
   1513		rpar = tb->rnum[h];
   1514
   1515		/*
   1516		 * calculate number of blocks S[h] must be split into when
   1517		 * nothing is shifted to the neighbors, as well as number of
   1518		 * items in each part of the split node (s012 numbers),
   1519		 * and number of bytes (s1bytes) of the shared drop which
   1520		 * flow to S1 if any
   1521		 */
   1522		nset = NOTHING_SHIFT_NO_FLOW;
   1523		nver = get_num_ver(vn->vn_mode, tb, h,
   1524				   0, -1, h ? vn->vn_nr_item : 0, -1,
   1525				   snum012, NO_FLOW);
   1526
   1527		if (!h) {
   1528			int nver1;
   1529
   1530			/*
   1531			 * note, that in this case we try to bottle
   1532			 * between S[0] and S1 (S1 - the first new node)
   1533			 */
   1534			nver1 = get_num_ver(vn->vn_mode, tb, h,
   1535					    0, -1, 0, -1,
   1536					    snum012 + NOTHING_SHIFT_FLOW, FLOW);
   1537			if (nver > nver1)
   1538				nset = NOTHING_SHIFT_FLOW, nver = nver1;
   1539		}
   1540
   1541		/*
   1542		 * calculate number of blocks S[h] must be split into when
   1543		 * l_shift_num first items and l_shift_bytes of the right
   1544		 * most liquid item to be shifted are shifted to the left
   1545		 * neighbor, as well as number of items in each part of the
   1546		 * splitted node (s012 numbers), and number of bytes
   1547		 * (s1bytes) of the shared drop which flow to S1 if any
   1548		 */
   1549		lset = LEFT_SHIFT_NO_FLOW;
   1550		lnver = get_num_ver(vn->vn_mode, tb, h,
   1551				    lpar - ((h || tb->lbytes == -1) ? 0 : 1),
   1552				    -1, h ? vn->vn_nr_item : 0, -1,
   1553				    snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
   1554		if (!h) {
   1555			int lnver1;
   1556
   1557			lnver1 = get_num_ver(vn->vn_mode, tb, h,
   1558					     lpar -
   1559					     ((tb->lbytes != -1) ? 1 : 0),
   1560					     tb->lbytes, 0, -1,
   1561					     snum012 + LEFT_SHIFT_FLOW, FLOW);
   1562			if (lnver > lnver1)
   1563				lset = LEFT_SHIFT_FLOW, lnver = lnver1;
   1564		}
   1565
   1566		/*
   1567		 * calculate number of blocks S[h] must be split into when
   1568		 * r_shift_num first items and r_shift_bytes of the left most
   1569		 * liquid item to be shifted are shifted to the right neighbor,
   1570		 * as well as number of items in each part of the splitted
   1571		 * node (s012 numbers), and number of bytes (s1bytes) of the
   1572		 * shared drop which flow to S1 if any
   1573		 */
   1574		rset = RIGHT_SHIFT_NO_FLOW;
   1575		rnver = get_num_ver(vn->vn_mode, tb, h,
   1576				    0, -1,
   1577				    h ? (vn->vn_nr_item - rpar) : (rpar -
   1578								   ((tb->
   1579								     rbytes !=
   1580								     -1) ? 1 :
   1581								    0)), -1,
   1582				    snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
   1583		if (!h) {
   1584			int rnver1;
   1585
   1586			rnver1 = get_num_ver(vn->vn_mode, tb, h,
   1587					     0, -1,
   1588					     (rpar -
   1589					      ((tb->rbytes != -1) ? 1 : 0)),
   1590					     tb->rbytes,
   1591					     snum012 + RIGHT_SHIFT_FLOW, FLOW);
   1592
   1593			if (rnver > rnver1)
   1594				rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
   1595		}
   1596
   1597		/*
   1598		 * calculate number of blocks S[h] must be split into when
   1599		 * items are shifted in both directions, as well as number
   1600		 * of items in each part of the splitted node (s012 numbers),
   1601		 * and number of bytes (s1bytes) of the shared drop which
   1602		 * flow to S1 if any
   1603		 */
   1604		lrset = LR_SHIFT_NO_FLOW;
   1605		lrnver = get_num_ver(vn->vn_mode, tb, h,
   1606				     lpar - ((h || tb->lbytes == -1) ? 0 : 1),
   1607				     -1,
   1608				     h ? (vn->vn_nr_item - rpar) : (rpar -
   1609								    ((tb->
   1610								      rbytes !=
   1611								      -1) ? 1 :
   1612								     0)), -1,
   1613				     snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
   1614		if (!h) {
   1615			int lrnver1;
   1616
   1617			lrnver1 = get_num_ver(vn->vn_mode, tb, h,
   1618					      lpar -
   1619					      ((tb->lbytes != -1) ? 1 : 0),
   1620					      tb->lbytes,
   1621					      (rpar -
   1622					       ((tb->rbytes != -1) ? 1 : 0)),
   1623					      tb->rbytes,
   1624					      snum012 + LR_SHIFT_FLOW, FLOW);
   1625			if (lrnver > lrnver1)
   1626				lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
   1627		}
   1628
   1629		/*
   1630		 * Our general shifting strategy is:
   1631		 * 1) to minimized number of new nodes;
   1632		 * 2) to minimized number of neighbors involved in shifting;
   1633		 * 3) to minimized number of disk reads;
   1634		 */
   1635
   1636		/* we can win TWO or ONE nodes by shifting in both directions */
   1637		if (lrnver < lnver && lrnver < rnver) {
   1638			RFALSE(h &&
   1639			       (tb->lnum[h] != 1 ||
   1640				tb->rnum[h] != 1 ||
   1641				lrnver != 1 || rnver != 2 || lnver != 2
   1642				|| h != 1), "vs-8230: bad h");
   1643			if (lrset == LR_SHIFT_FLOW)
   1644				set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
   1645					       lrnver, snum012 + lrset,
   1646					       tb->lbytes, tb->rbytes);
   1647			else
   1648				set_parameters(tb, h,
   1649					       tb->lnum[h] -
   1650					       ((tb->lbytes == -1) ? 0 : 1),
   1651					       tb->rnum[h] -
   1652					       ((tb->rbytes == -1) ? 0 : 1),
   1653					       lrnver, snum012 + lrset, -1, -1);
   1654
   1655			return CARRY_ON;
   1656		}
   1657
   1658		/*
   1659		 * if shifting doesn't lead to better packing
   1660		 * then don't shift
   1661		 */
   1662		if (nver == lrnver) {
   1663			set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
   1664				       -1);
   1665			return CARRY_ON;
   1666		}
   1667
   1668		/*
   1669		 * now we know that for better packing shifting in only one
   1670		 * direction either to the left or to the right is required
   1671		 */
   1672
   1673		/*
   1674		 * if shifting to the left is better than
   1675		 * shifting to the right
   1676		 */
   1677		if (lnver < rnver) {
   1678			SET_PAR_SHIFT_LEFT;
   1679			return CARRY_ON;
   1680		}
   1681
   1682		/*
   1683		 * if shifting to the right is better than
   1684		 * shifting to the left
   1685		 */
   1686		if (lnver > rnver) {
   1687			SET_PAR_SHIFT_RIGHT;
   1688			return CARRY_ON;
   1689		}
   1690
   1691		/*
   1692		 * now shifting in either direction gives the same number
   1693		 * of nodes and we can make use of the cached neighbors
   1694		 */
   1695		if (is_left_neighbor_in_cache(tb, h)) {
   1696			SET_PAR_SHIFT_LEFT;
   1697			return CARRY_ON;
   1698		}
   1699
   1700		/*
   1701		 * shift to the right independently on whether the
   1702		 * right neighbor in cache or not
   1703		 */
   1704		SET_PAR_SHIFT_RIGHT;
   1705		return CARRY_ON;
   1706	}
   1707}
   1708
   1709/*
   1710 * Check whether current node S[h] is balanced when Decreasing its size by
   1711 * Deleting or Cutting for INTERNAL node of S+tree.
   1712 * Calculate parameters for balancing for current level h.
   1713 * Parameters:
   1714 *	tb	tree_balance structure;
   1715 *	h	current level of the node;
   1716 *	inum	item number in S[h];
   1717 *	mode	i - insert, p - paste;
   1718 * Returns:	1 - schedule occurred;
   1719 *	        0 - balancing for higher levels needed;
   1720 *	       -1 - no balancing for higher levels needed;
   1721 *	       -2 - no disk space.
   1722 *
   1723 * Note: Items of internal nodes have fixed size, so the balance condition for
   1724 * the internal part of S+tree is as for the B-trees.
   1725 */
   1726static int dc_check_balance_internal(struct tree_balance *tb, int h)
   1727{
   1728	struct virtual_node *vn = tb->tb_vn;
   1729
   1730	/*
   1731	 * Sh is the node whose balance is currently being checked,
   1732	 * and Fh is its father.
   1733	 */
   1734	struct buffer_head *Sh, *Fh;
   1735	int ret;
   1736	int lfree, rfree /* free space in L and R */ ;
   1737
   1738	Sh = PATH_H_PBUFFER(tb->tb_path, h);
   1739	Fh = PATH_H_PPARENT(tb->tb_path, h);
   1740
   1741	/*
   1742	 * using tb->insert_size[h], which is negative in this case,
   1743	 * create_virtual_node calculates:
   1744	 * new_nr_item = number of items node would have if operation is
   1745	 * performed without balancing (new_nr_item);
   1746	 */
   1747	create_virtual_node(tb, h);
   1748
   1749	if (!Fh) {		/* S[h] is the root. */
   1750		/* no balancing for higher levels needed */
   1751		if (vn->vn_nr_item > 0) {
   1752			set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
   1753			return NO_BALANCING_NEEDED;
   1754		}
   1755		/*
   1756		 * new_nr_item == 0.
   1757		 * Current root will be deleted resulting in
   1758		 * decrementing the tree height.
   1759		 */
   1760		set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
   1761		return CARRY_ON;
   1762	}
   1763
   1764	if ((ret = get_parents(tb, h)) != CARRY_ON)
   1765		return ret;
   1766
   1767	/* get free space of neighbors */
   1768	rfree = get_rfree(tb, h);
   1769	lfree = get_lfree(tb, h);
   1770
   1771	/* determine maximal number of items we can fit into neighbors */
   1772	check_left(tb, h, lfree);
   1773	check_right(tb, h, rfree);
   1774
   1775	/*
   1776	 * Balance condition for the internal node is valid.
   1777	 * In this case we balance only if it leads to better packing.
   1778	 */
   1779	if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) {
   1780		/*
   1781		 * Here we join S[h] with one of its neighbors,
   1782		 * which is impossible with greater values of new_nr_item.
   1783		 */
   1784		if (vn->vn_nr_item == MIN_NR_KEY(Sh)) {
   1785			/* All contents of S[h] can be moved to L[h]. */
   1786			if (tb->lnum[h] >= vn->vn_nr_item + 1) {
   1787				int n;
   1788				int order_L;
   1789
   1790				order_L =
   1791				    ((n =
   1792				      PATH_H_B_ITEM_ORDER(tb->tb_path,
   1793							  h)) ==
   1794				     0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
   1795				n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
   1796				    (DC_SIZE + KEY_SIZE);
   1797				set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
   1798					       -1);
   1799				return CARRY_ON;
   1800			}
   1801
   1802			/* All contents of S[h] can be moved to R[h]. */
   1803			if (tb->rnum[h] >= vn->vn_nr_item + 1) {
   1804				int n;
   1805				int order_R;
   1806
   1807				order_R =
   1808				    ((n =
   1809				      PATH_H_B_ITEM_ORDER(tb->tb_path,
   1810							  h)) ==
   1811				     B_NR_ITEMS(Fh)) ? 0 : n + 1;
   1812				n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
   1813				    (DC_SIZE + KEY_SIZE);
   1814				set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
   1815					       -1);
   1816				return CARRY_ON;
   1817			}
   1818		}
   1819
   1820		/*
   1821		 * All contents of S[h] can be moved to the neighbors
   1822		 * (L[h] & R[h]).
   1823		 */
   1824		if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
   1825			int to_r;
   1826
   1827			to_r =
   1828			    ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
   1829			     tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
   1830			    (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
   1831			set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
   1832				       0, NULL, -1, -1);
   1833			return CARRY_ON;
   1834		}
   1835
   1836		/* Balancing does not lead to better packing. */
   1837		set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
   1838		return NO_BALANCING_NEEDED;
   1839	}
   1840
   1841	/*
   1842	 * Current node contain insufficient number of items.
   1843	 * Balancing is required.
   1844	 */
   1845	/* Check whether we can merge S[h] with left neighbor. */
   1846	if (tb->lnum[h] >= vn->vn_nr_item + 1)
   1847		if (is_left_neighbor_in_cache(tb, h)
   1848		    || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
   1849			int n;
   1850			int order_L;
   1851
   1852			order_L =
   1853			    ((n =
   1854			      PATH_H_B_ITEM_ORDER(tb->tb_path,
   1855						  h)) ==
   1856			     0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
   1857			n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
   1858								      KEY_SIZE);
   1859			set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
   1860			return CARRY_ON;
   1861		}
   1862
   1863	/* Check whether we can merge S[h] with right neighbor. */
   1864	if (tb->rnum[h] >= vn->vn_nr_item + 1) {
   1865		int n;
   1866		int order_R;
   1867
   1868		order_R =
   1869		    ((n =
   1870		      PATH_H_B_ITEM_ORDER(tb->tb_path,
   1871					  h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
   1872		n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
   1873							      KEY_SIZE);
   1874		set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
   1875		return CARRY_ON;
   1876	}
   1877
   1878	/* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
   1879	if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
   1880		int to_r;
   1881
   1882		to_r =
   1883		    ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
   1884		     vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
   1885						tb->rnum[h]);
   1886		set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
   1887			       -1, -1);
   1888		return CARRY_ON;
   1889	}
   1890
   1891	/* For internal nodes try to borrow item from a neighbor */
   1892	RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
   1893
   1894	/* Borrow one or two items from caching neighbor */
   1895	if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
   1896		int from_l;
   1897
   1898		from_l =
   1899		    (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
   1900		     1) / 2 - (vn->vn_nr_item + 1);
   1901		set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
   1902		return CARRY_ON;
   1903	}
   1904
   1905	set_parameters(tb, h, 0,
   1906		       -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
   1907			  1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
   1908	return CARRY_ON;
   1909}
   1910
   1911/*
   1912 * Check whether current node S[h] is balanced when Decreasing its size by
   1913 * Deleting or Truncating for LEAF node of S+tree.
   1914 * Calculate parameters for balancing for current level h.
   1915 * Parameters:
   1916 *	tb	tree_balance structure;
   1917 *	h	current level of the node;
   1918 *	inum	item number in S[h];
   1919 *	mode	i - insert, p - paste;
   1920 * Returns:	1 - schedule occurred;
   1921 *	        0 - balancing for higher levels needed;
   1922 *	       -1 - no balancing for higher levels needed;
   1923 *	       -2 - no disk space.
   1924 */
   1925static int dc_check_balance_leaf(struct tree_balance *tb, int h)
   1926{
   1927	struct virtual_node *vn = tb->tb_vn;
   1928
   1929	/*
   1930	 * Number of bytes that must be deleted from
   1931	 * (value is negative if bytes are deleted) buffer which
   1932	 * contains node being balanced.  The mnemonic is that the
   1933	 * attempted change in node space used level is levbytes bytes.
   1934	 */
   1935	int levbytes;
   1936
   1937	/* the maximal item size */
   1938	int maxsize, ret;
   1939
   1940	/*
   1941	 * S0 is the node whose balance is currently being checked,
   1942	 * and F0 is its father.
   1943	 */
   1944	struct buffer_head *S0, *F0;
   1945	int lfree, rfree /* free space in L and R */ ;
   1946
   1947	S0 = PATH_H_PBUFFER(tb->tb_path, 0);
   1948	F0 = PATH_H_PPARENT(tb->tb_path, 0);
   1949
   1950	levbytes = tb->insert_size[h];
   1951
   1952	maxsize = MAX_CHILD_SIZE(S0);	/* maximal possible size of an item */
   1953
   1954	if (!F0) {		/* S[0] is the root now. */
   1955
   1956		RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
   1957		       "vs-8240: attempt to create empty buffer tree");
   1958
   1959		set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
   1960		return NO_BALANCING_NEEDED;
   1961	}
   1962
   1963	if ((ret = get_parents(tb, h)) != CARRY_ON)
   1964		return ret;
   1965
   1966	/* get free space of neighbors */
   1967	rfree = get_rfree(tb, h);
   1968	lfree = get_lfree(tb, h);
   1969
   1970	create_virtual_node(tb, h);
   1971
   1972	/* if 3 leaves can be merge to one, set parameters and return */
   1973	if (are_leaves_removable(tb, lfree, rfree))
   1974		return CARRY_ON;
   1975
   1976	/*
   1977	 * determine maximal number of items we can shift to the left/right
   1978	 * neighbor and the maximal number of bytes that can flow to the
   1979	 * left/right neighbor from the left/right most liquid item that
   1980	 * cannot be shifted from S[0] entirely
   1981	 */
   1982	check_left(tb, h, lfree);
   1983	check_right(tb, h, rfree);
   1984
   1985	/* check whether we can merge S with left neighbor. */
   1986	if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
   1987		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 */
   1988		    !tb->FR[h]) {
   1989
   1990			RFALSE(!tb->FL[h],
   1991			       "vs-8245: dc_check_balance_leaf: FL[h] must exist");
   1992
   1993			/* set parameter to merge S[0] with its left neighbor */
   1994			set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
   1995			return CARRY_ON;
   1996		}
   1997
   1998	/* check whether we can merge S[0] with right neighbor. */
   1999	if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
   2000		set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
   2001		return CARRY_ON;
   2002	}
   2003
   2004	/*
   2005	 * All contents of S[0] can be moved to the neighbors (L[0] & R[0]).
   2006	 * Set parameters and return
   2007	 */
   2008	if (is_leaf_removable(tb))
   2009		return CARRY_ON;
   2010
   2011	/* Balancing is not required. */
   2012	tb->s0num = vn->vn_nr_item;
   2013	set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
   2014	return NO_BALANCING_NEEDED;
   2015}
   2016
   2017/*
   2018 * Check whether current node S[h] is balanced when Decreasing its size by
   2019 * Deleting or Cutting.
   2020 * Calculate parameters for balancing for current level h.
   2021 * Parameters:
   2022 *	tb	tree_balance structure;
   2023 *	h	current level of the node;
   2024 *	inum	item number in S[h];
   2025 *	mode	d - delete, c - cut.
   2026 * Returns:	1 - schedule occurred;
   2027 *	        0 - balancing for higher levels needed;
   2028 *	       -1 - no balancing for higher levels needed;
   2029 *	       -2 - no disk space.
   2030 */
   2031static int dc_check_balance(struct tree_balance *tb, int h)
   2032{
   2033	RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
   2034	       "vs-8250: S is not initialized");
   2035
   2036	if (h)
   2037		return dc_check_balance_internal(tb, h);
   2038	else
   2039		return dc_check_balance_leaf(tb, h);
   2040}
   2041
   2042/*
   2043 * Check whether current node S[h] is balanced.
   2044 * Calculate parameters for balancing for current level h.
   2045 * Parameters:
   2046 *
   2047 *	tb	tree_balance structure:
   2048 *
   2049 *              tb is a large structure that must be read about in the header
   2050 *		file at the same time as this procedure if the reader is
   2051 *		to successfully understand this procedure
   2052 *
   2053 *	h	current level of the node;
   2054 *	inum	item number in S[h];
   2055 *	mode	i - insert, p - paste, d - delete, c - cut.
   2056 * Returns:	1 - schedule occurred;
   2057 *	        0 - balancing for higher levels needed;
   2058 *	       -1 - no balancing for higher levels needed;
   2059 *	       -2 - no disk space.
   2060 */
   2061static int check_balance(int mode,
   2062			 struct tree_balance *tb,
   2063			 int h,
   2064			 int inum,
   2065			 int pos_in_item,
   2066			 struct item_head *ins_ih, const void *data)
   2067{
   2068	struct virtual_node *vn;
   2069
   2070	vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
   2071	vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
   2072	vn->vn_mode = mode;
   2073	vn->vn_affected_item_num = inum;
   2074	vn->vn_pos_in_item = pos_in_item;
   2075	vn->vn_ins_ih = ins_ih;
   2076	vn->vn_data = data;
   2077
   2078	RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
   2079	       "vs-8255: ins_ih can not be 0 in insert mode");
   2080
   2081	/* Calculate balance parameters when size of node is increasing. */
   2082	if (tb->insert_size[h] > 0)
   2083		return ip_check_balance(tb, h);
   2084
   2085	/* Calculate balance parameters when  size of node is decreasing. */
   2086	return dc_check_balance(tb, h);
   2087}
   2088
   2089/* Check whether parent at the path is the really parent of the current node.*/
   2090static int get_direct_parent(struct tree_balance *tb, int h)
   2091{
   2092	struct buffer_head *bh;
   2093	struct treepath *path = tb->tb_path;
   2094	int position,
   2095	    path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
   2096
   2097	/* We are in the root or in the new root. */
   2098	if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
   2099
   2100		RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
   2101		       "PAP-8260: invalid offset in the path");
   2102
   2103		if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->
   2104		    b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
   2105			/* Root is not changed. */
   2106			PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;
   2107			PATH_OFFSET_POSITION(path, path_offset - 1) = 0;
   2108			return CARRY_ON;
   2109		}
   2110		/* Root is changed and we must recalculate the path. */
   2111		return REPEAT_SEARCH;
   2112	}
   2113
   2114	/* Parent in the path is not in the tree. */
   2115	if (!B_IS_IN_TREE
   2116	    (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))
   2117		return REPEAT_SEARCH;
   2118
   2119	if ((position =
   2120	     PATH_OFFSET_POSITION(path,
   2121				  path_offset - 1)) > B_NR_ITEMS(bh))
   2122		return REPEAT_SEARCH;
   2123
   2124	/* Parent in the path is not parent of the current node in the tree. */
   2125	if (B_N_CHILD_NUM(bh, position) !=
   2126	    PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)
   2127		return REPEAT_SEARCH;
   2128
   2129	if (buffer_locked(bh)) {
   2130		int depth = reiserfs_write_unlock_nested(tb->tb_sb);
   2131		__wait_on_buffer(bh);
   2132		reiserfs_write_lock_nested(tb->tb_sb, depth);
   2133		if (FILESYSTEM_CHANGED_TB(tb))
   2134			return REPEAT_SEARCH;
   2135	}
   2136
   2137	/*
   2138	 * Parent in the path is unlocked and really parent
   2139	 * of the current node.
   2140	 */
   2141	return CARRY_ON;
   2142}
   2143
   2144/*
   2145 * Using lnum[h] and rnum[h] we should determine what neighbors
   2146 * of S[h] we
   2147 * need in order to balance S[h], and get them if necessary.
   2148 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
   2149 *	        CARRY_ON - schedule didn't occur while the function worked;
   2150 */
   2151static int get_neighbors(struct tree_balance *tb, int h)
   2152{
   2153	int child_position,
   2154	    path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
   2155	unsigned long son_number;
   2156	struct super_block *sb = tb->tb_sb;
   2157	struct buffer_head *bh;
   2158	int depth;
   2159
   2160	PROC_INFO_INC(sb, get_neighbors[h]);
   2161
   2162	if (tb->lnum[h]) {
   2163		/* We need left neighbor to balance S[h]. */
   2164		PROC_INFO_INC(sb, need_l_neighbor[h]);
   2165		bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
   2166
   2167		RFALSE(bh == tb->FL[h] &&
   2168		       !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
   2169		       "PAP-8270: invalid position in the parent");
   2170
   2171		child_position =
   2172		    (bh ==
   2173		     tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
   2174								       FL[h]);
   2175		son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
   2176		depth = reiserfs_write_unlock_nested(tb->tb_sb);
   2177		bh = sb_bread(sb, son_number);
   2178		reiserfs_write_lock_nested(tb->tb_sb, depth);
   2179		if (!bh)
   2180			return IO_ERROR;
   2181		if (FILESYSTEM_CHANGED_TB(tb)) {
   2182			brelse(bh);
   2183			PROC_INFO_INC(sb, get_neighbors_restart[h]);
   2184			return REPEAT_SEARCH;
   2185		}
   2186
   2187		RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||
   2188		       child_position > B_NR_ITEMS(tb->FL[h]) ||
   2189		       B_N_CHILD_NUM(tb->FL[h], child_position) !=
   2190		       bh->b_blocknr, "PAP-8275: invalid parent");
   2191		RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
   2192		RFALSE(!h &&
   2193		       B_FREE_SPACE(bh) !=
   2194		       MAX_CHILD_SIZE(bh) -
   2195		       dc_size(B_N_CHILD(tb->FL[0], child_position)),
   2196		       "PAP-8290: invalid child size of left neighbor");
   2197
   2198		brelse(tb->L[h]);
   2199		tb->L[h] = bh;
   2200	}
   2201
   2202	/* We need right neighbor to balance S[path_offset]. */
   2203	if (tb->rnum[h]) {
   2204		PROC_INFO_INC(sb, need_r_neighbor[h]);
   2205		bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
   2206
   2207		RFALSE(bh == tb->FR[h] &&
   2208		       PATH_OFFSET_POSITION(tb->tb_path,
   2209					    path_offset) >=
   2210		       B_NR_ITEMS(bh),
   2211		       "PAP-8295: invalid position in the parent");
   2212
   2213		child_position =
   2214		    (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
   2215		son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
   2216		depth = reiserfs_write_unlock_nested(tb->tb_sb);
   2217		bh = sb_bread(sb, son_number);
   2218		reiserfs_write_lock_nested(tb->tb_sb, depth);
   2219		if (!bh)
   2220			return IO_ERROR;
   2221		if (FILESYSTEM_CHANGED_TB(tb)) {
   2222			brelse(bh);
   2223			PROC_INFO_INC(sb, get_neighbors_restart[h]);
   2224			return REPEAT_SEARCH;
   2225		}
   2226		brelse(tb->R[h]);
   2227		tb->R[h] = bh;
   2228
   2229		RFALSE(!h
   2230		       && B_FREE_SPACE(bh) !=
   2231		       MAX_CHILD_SIZE(bh) -
   2232		       dc_size(B_N_CHILD(tb->FR[0], child_position)),
   2233		       "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
   2234		       B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
   2235		       dc_size(B_N_CHILD(tb->FR[0], child_position)));
   2236
   2237	}
   2238	return CARRY_ON;
   2239}
   2240
   2241static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
   2242{
   2243	int max_num_of_items;
   2244	int max_num_of_entries;
   2245	unsigned long blocksize = sb->s_blocksize;
   2246
   2247#define MIN_NAME_LEN 1
   2248
   2249	max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
   2250	max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
   2251	    (DEH_SIZE + MIN_NAME_LEN);
   2252
   2253	return sizeof(struct virtual_node) +
   2254	    max(max_num_of_items * sizeof(struct virtual_item),
   2255		sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
   2256		(max_num_of_entries - 1) * sizeof(__u16));
   2257}
   2258
   2259/*
   2260 * maybe we should fail balancing we are going to perform when kmalloc
   2261 * fails several times. But now it will loop until kmalloc gets
   2262 * required memory
   2263 */
   2264static int get_mem_for_virtual_node(struct tree_balance *tb)
   2265{
   2266	int check_fs = 0;
   2267	int size;
   2268	char *buf;
   2269
   2270	size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
   2271
   2272	/* we have to allocate more memory for virtual node */
   2273	if (size > tb->vn_buf_size) {
   2274		if (tb->vn_buf) {
   2275			/* free memory allocated before */
   2276			kfree(tb->vn_buf);
   2277			/* this is not needed if kfree is atomic */
   2278			check_fs = 1;
   2279		}
   2280
   2281		/* virtual node requires now more memory */
   2282		tb->vn_buf_size = size;
   2283
   2284		/* get memory for virtual item */
   2285		buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
   2286		if (!buf) {
   2287			/*
   2288			 * getting memory with GFP_KERNEL priority may involve
   2289			 * balancing now (due to indirect_to_direct conversion
   2290			 * on dcache shrinking). So, release path and collected
   2291			 * resources here
   2292			 */
   2293			free_buffers_in_tb(tb);
   2294			buf = kmalloc(size, GFP_NOFS);
   2295			if (!buf) {
   2296				tb->vn_buf_size = 0;
   2297			}
   2298			tb->vn_buf = buf;
   2299			schedule();
   2300			return REPEAT_SEARCH;
   2301		}
   2302
   2303		tb->vn_buf = buf;
   2304	}
   2305
   2306	if (check_fs && FILESYSTEM_CHANGED_TB(tb))
   2307		return REPEAT_SEARCH;
   2308
   2309	return CARRY_ON;
   2310}
   2311
   2312#ifdef CONFIG_REISERFS_CHECK
   2313static void tb_buffer_sanity_check(struct super_block *sb,
   2314				   struct buffer_head *bh,
   2315				   const char *descr, int level)
   2316{
   2317	if (bh) {
   2318		if (atomic_read(&(bh->b_count)) <= 0)
   2319
   2320			reiserfs_panic(sb, "jmacd-1", "negative or zero "
   2321				       "reference counter for buffer %s[%d] "
   2322				       "(%b)", descr, level, bh);
   2323
   2324		if (!buffer_uptodate(bh))
   2325			reiserfs_panic(sb, "jmacd-2", "buffer is not up "
   2326				       "to date %s[%d] (%b)",
   2327				       descr, level, bh);
   2328
   2329		if (!B_IS_IN_TREE(bh))
   2330			reiserfs_panic(sb, "jmacd-3", "buffer is not "
   2331				       "in tree %s[%d] (%b)",
   2332				       descr, level, bh);
   2333
   2334		if (bh->b_bdev != sb->s_bdev)
   2335			reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
   2336				       "device %s[%d] (%b)",
   2337				       descr, level, bh);
   2338
   2339		if (bh->b_size != sb->s_blocksize)
   2340			reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
   2341				       "blocksize %s[%d] (%b)",
   2342				       descr, level, bh);
   2343
   2344		if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
   2345			reiserfs_panic(sb, "jmacd-6", "buffer block "
   2346				       "number too high %s[%d] (%b)",
   2347				       descr, level, bh);
   2348	}
   2349}
   2350#else
   2351static void tb_buffer_sanity_check(struct super_block *sb,
   2352				   struct buffer_head *bh,
   2353				   const char *descr, int level)
   2354{;
   2355}
   2356#endif
   2357
   2358static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
   2359{
   2360	return reiserfs_prepare_for_journal(s, bh, 0);
   2361}
   2362
   2363static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
   2364{
   2365	struct buffer_head *locked;
   2366#ifdef CONFIG_REISERFS_CHECK
   2367	int repeat_counter = 0;
   2368#endif
   2369	int i;
   2370
   2371	do {
   2372
   2373		locked = NULL;
   2374
   2375		for (i = tb->tb_path->path_length;
   2376		     !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
   2377			if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
   2378				/*
   2379				 * if I understand correctly, we can only
   2380				 * be sure the last buffer in the path is
   2381				 * in the tree --clm
   2382				 */
   2383#ifdef CONFIG_REISERFS_CHECK
   2384				if (PATH_PLAST_BUFFER(tb->tb_path) ==
   2385				    PATH_OFFSET_PBUFFER(tb->tb_path, i))
   2386					tb_buffer_sanity_check(tb->tb_sb,
   2387							       PATH_OFFSET_PBUFFER
   2388							       (tb->tb_path,
   2389								i), "S",
   2390							       tb->tb_path->
   2391							       path_length - i);
   2392#endif
   2393				if (!clear_all_dirty_bits(tb->tb_sb,
   2394							  PATH_OFFSET_PBUFFER
   2395							  (tb->tb_path,
   2396							   i))) {
   2397					locked =
   2398					    PATH_OFFSET_PBUFFER(tb->tb_path,
   2399								i);
   2400				}
   2401			}
   2402		}
   2403
   2404		for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
   2405		     i++) {
   2406
   2407			if (tb->lnum[i]) {
   2408
   2409				if (tb->L[i]) {
   2410					tb_buffer_sanity_check(tb->tb_sb,
   2411							       tb->L[i],
   2412							       "L", i);
   2413					if (!clear_all_dirty_bits
   2414					    (tb->tb_sb, tb->L[i]))
   2415						locked = tb->L[i];
   2416				}
   2417
   2418				if (!locked && tb->FL[i]) {
   2419					tb_buffer_sanity_check(tb->tb_sb,
   2420							       tb->FL[i],
   2421							       "FL", i);
   2422					if (!clear_all_dirty_bits
   2423					    (tb->tb_sb, tb->FL[i]))
   2424						locked = tb->FL[i];
   2425				}
   2426
   2427				if (!locked && tb->CFL[i]) {
   2428					tb_buffer_sanity_check(tb->tb_sb,
   2429							       tb->CFL[i],
   2430							       "CFL", i);
   2431					if (!clear_all_dirty_bits
   2432					    (tb->tb_sb, tb->CFL[i]))
   2433						locked = tb->CFL[i];
   2434				}
   2435
   2436			}
   2437
   2438			if (!locked && (tb->rnum[i])) {
   2439
   2440				if (tb->R[i]) {
   2441					tb_buffer_sanity_check(tb->tb_sb,
   2442							       tb->R[i],
   2443							       "R", i);
   2444					if (!clear_all_dirty_bits
   2445					    (tb->tb_sb, tb->R[i]))
   2446						locked = tb->R[i];
   2447				}
   2448
   2449				if (!locked && tb->FR[i]) {
   2450					tb_buffer_sanity_check(tb->tb_sb,
   2451							       tb->FR[i],
   2452							       "FR", i);
   2453					if (!clear_all_dirty_bits
   2454					    (tb->tb_sb, tb->FR[i]))
   2455						locked = tb->FR[i];
   2456				}
   2457
   2458				if (!locked && tb->CFR[i]) {
   2459					tb_buffer_sanity_check(tb->tb_sb,
   2460							       tb->CFR[i],
   2461							       "CFR", i);
   2462					if (!clear_all_dirty_bits
   2463					    (tb->tb_sb, tb->CFR[i]))
   2464						locked = tb->CFR[i];
   2465				}
   2466			}
   2467		}
   2468
   2469		/*
   2470		 * as far as I can tell, this is not required.  The FEB list
   2471		 * seems to be full of newly allocated nodes, which will
   2472		 * never be locked, dirty, or anything else.
   2473		 * To be safe, I'm putting in the checks and waits in.
   2474		 * For the moment, they are needed to keep the code in
   2475		 * journal.c from complaining about the buffer.
   2476		 * That code is inside CONFIG_REISERFS_CHECK as well.  --clm
   2477		 */
   2478		for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
   2479			if (tb->FEB[i]) {
   2480				if (!clear_all_dirty_bits
   2481				    (tb->tb_sb, tb->FEB[i]))
   2482					locked = tb->FEB[i];
   2483			}
   2484		}
   2485
   2486		if (locked) {
   2487			int depth;
   2488#ifdef CONFIG_REISERFS_CHECK
   2489			repeat_counter++;
   2490			if ((repeat_counter % 10000) == 0) {
   2491				reiserfs_warning(tb->tb_sb, "reiserfs-8200",
   2492						 "too many iterations waiting "
   2493						 "for buffer to unlock "
   2494						 "(%b)", locked);
   2495
   2496				/* Don't loop forever.  Try to recover from possible error. */
   2497
   2498				return (FILESYSTEM_CHANGED_TB(tb)) ?
   2499				    REPEAT_SEARCH : CARRY_ON;
   2500			}
   2501#endif
   2502			depth = reiserfs_write_unlock_nested(tb->tb_sb);
   2503			__wait_on_buffer(locked);
   2504			reiserfs_write_lock_nested(tb->tb_sb, depth);
   2505			if (FILESYSTEM_CHANGED_TB(tb))
   2506				return REPEAT_SEARCH;
   2507		}
   2508
   2509	} while (locked);
   2510
   2511	return CARRY_ON;
   2512}
   2513
   2514/*
   2515 * Prepare for balancing, that is
   2516 *	get all necessary parents, and neighbors;
   2517 *	analyze what and where should be moved;
   2518 *	get sufficient number of new nodes;
   2519 * Balancing will start only after all resources will be collected at a time.
   2520 *
   2521 * When ported to SMP kernels, only at the last moment after all needed nodes
   2522 * are collected in cache, will the resources be locked using the usual
   2523 * textbook ordered lock acquisition algorithms.  Note that ensuring that
   2524 * this code neither write locks what it does not need to write lock nor locks
   2525 * out of order will be a pain in the butt that could have been avoided.
   2526 * Grumble grumble. -Hans
   2527 *
   2528 * fix is meant in the sense of render unchanging
   2529 *
   2530 * Latency might be improved by first gathering a list of what buffers
   2531 * are needed and then getting as many of them in parallel as possible? -Hans
   2532 *
   2533 * Parameters:
   2534 *	op_mode	i - insert, d - delete, c - cut (truncate), p - paste (append)
   2535 *	tb	tree_balance structure;
   2536 *	inum	item number in S[h];
   2537 *      pos_in_item - comment this if you can
   2538 *      ins_ih	item head of item being inserted
   2539 *	data	inserted item or data to be pasted
   2540 * Returns:	1 - schedule occurred while the function worked;
   2541 *	        0 - schedule didn't occur while the function worked;
   2542 *             -1 - if no_disk_space
   2543 */
   2544
   2545int fix_nodes(int op_mode, struct tree_balance *tb,
   2546	      struct item_head *ins_ih, const void *data)
   2547{
   2548	int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
   2549	int pos_in_item;
   2550
   2551	/*
   2552	 * we set wait_tb_buffers_run when we have to restore any dirty
   2553	 * bits cleared during wait_tb_buffers_run
   2554	 */
   2555	int wait_tb_buffers_run = 0;
   2556	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
   2557
   2558	++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
   2559
   2560	pos_in_item = tb->tb_path->pos_in_item;
   2561
   2562	tb->fs_gen = get_generation(tb->tb_sb);
   2563
   2564	/*
   2565	 * we prepare and log the super here so it will already be in the
   2566	 * transaction when do_balance needs to change it.
   2567	 * This way do_balance won't have to schedule when trying to prepare
   2568	 * the super for logging
   2569	 */
   2570	reiserfs_prepare_for_journal(tb->tb_sb,
   2571				     SB_BUFFER_WITH_SB(tb->tb_sb), 1);
   2572	journal_mark_dirty(tb->transaction_handle,
   2573			   SB_BUFFER_WITH_SB(tb->tb_sb));
   2574	if (FILESYSTEM_CHANGED_TB(tb))
   2575		return REPEAT_SEARCH;
   2576
   2577	/* if it possible in indirect_to_direct conversion */
   2578	if (buffer_locked(tbS0)) {
   2579		int depth = reiserfs_write_unlock_nested(tb->tb_sb);
   2580		__wait_on_buffer(tbS0);
   2581		reiserfs_write_lock_nested(tb->tb_sb, depth);
   2582		if (FILESYSTEM_CHANGED_TB(tb))
   2583			return REPEAT_SEARCH;
   2584	}
   2585#ifdef CONFIG_REISERFS_CHECK
   2586	if (REISERFS_SB(tb->tb_sb)->cur_tb) {
   2587		print_cur_tb("fix_nodes");
   2588		reiserfs_panic(tb->tb_sb, "PAP-8305",
   2589			       "there is pending do_balance");
   2590	}
   2591
   2592	if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
   2593		reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
   2594			       "not uptodate at the beginning of fix_nodes "
   2595			       "or not in tree (mode %c)",
   2596			       tbS0, tbS0, op_mode);
   2597
   2598	/* Check parameters. */
   2599	switch (op_mode) {
   2600	case M_INSERT:
   2601		if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
   2602			reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
   2603				       "item number %d (in S0 - %d) in case "
   2604				       "of insert", item_num,
   2605				       B_NR_ITEMS(tbS0));
   2606		break;
   2607	case M_PASTE:
   2608	case M_DELETE:
   2609	case M_CUT:
   2610		if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
   2611			print_block(tbS0, 0, -1, -1);
   2612			reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
   2613				       "item number(%d); mode = %c "
   2614				       "insert_size = %d",
   2615				       item_num, op_mode,
   2616				       tb->insert_size[0]);
   2617		}
   2618		break;
   2619	default:
   2620		reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
   2621			       "of operation");
   2622	}
   2623#endif
   2624
   2625	if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
   2626		/* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
   2627		return REPEAT_SEARCH;
   2628
   2629	/* Starting from the leaf level; for all levels h of the tree. */
   2630	for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
   2631		ret = get_direct_parent(tb, h);
   2632		if (ret != CARRY_ON)
   2633			goto repeat;
   2634
   2635		ret = check_balance(op_mode, tb, h, item_num,
   2636				    pos_in_item, ins_ih, data);
   2637		if (ret != CARRY_ON) {
   2638			if (ret == NO_BALANCING_NEEDED) {
   2639				/* No balancing for higher levels needed. */
   2640				ret = get_neighbors(tb, h);
   2641				if (ret != CARRY_ON)
   2642					goto repeat;
   2643				if (h != MAX_HEIGHT - 1)
   2644					tb->insert_size[h + 1] = 0;
   2645				/*
   2646				 * ok, analysis and resource gathering
   2647				 * are complete
   2648				 */
   2649				break;
   2650			}
   2651			goto repeat;
   2652		}
   2653
   2654		ret = get_neighbors(tb, h);
   2655		if (ret != CARRY_ON)
   2656			goto repeat;
   2657
   2658		/*
   2659		 * No disk space, or schedule occurred and analysis may be
   2660		 * invalid and needs to be redone.
   2661		 */
   2662		ret = get_empty_nodes(tb, h);
   2663		if (ret != CARRY_ON)
   2664			goto repeat;
   2665
   2666		/*
   2667		 * We have a positive insert size but no nodes exist on this
   2668		 * level, this means that we are creating a new root.
   2669		 */
   2670		if (!PATH_H_PBUFFER(tb->tb_path, h)) {
   2671
   2672			RFALSE(tb->blknum[h] != 1,
   2673			       "PAP-8350: creating new empty root");
   2674
   2675			if (h < MAX_HEIGHT - 1)
   2676				tb->insert_size[h + 1] = 0;
   2677		} else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
   2678			/*
   2679			 * The tree needs to be grown, so this node S[h]
   2680			 * which is the root node is split into two nodes,
   2681			 * and a new node (S[h+1]) will be created to
   2682			 * become the root node.
   2683			 */
   2684			if (tb->blknum[h] > 1) {
   2685
   2686				RFALSE(h == MAX_HEIGHT - 1,
   2687				       "PAP-8355: attempt to create too high of a tree");
   2688
   2689				tb->insert_size[h + 1] =
   2690				    (DC_SIZE +
   2691				     KEY_SIZE) * (tb->blknum[h] - 1) +
   2692				    DC_SIZE;
   2693			} else if (h < MAX_HEIGHT - 1)
   2694				tb->insert_size[h + 1] = 0;
   2695		} else
   2696			tb->insert_size[h + 1] =
   2697			    (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
   2698	}
   2699
   2700	ret = wait_tb_buffers_until_unlocked(tb);
   2701	if (ret == CARRY_ON) {
   2702		if (FILESYSTEM_CHANGED_TB(tb)) {
   2703			wait_tb_buffers_run = 1;
   2704			ret = REPEAT_SEARCH;
   2705			goto repeat;
   2706		} else {
   2707			return CARRY_ON;
   2708		}
   2709	} else {
   2710		wait_tb_buffers_run = 1;
   2711		goto repeat;
   2712	}
   2713
   2714repeat:
   2715	/*
   2716	 * fix_nodes was unable to perform its calculation due to
   2717	 * filesystem got changed under us, lack of free disk space or i/o
   2718	 * failure. If the first is the case - the search will be
   2719	 * repeated. For now - free all resources acquired so far except
   2720	 * for the new allocated nodes
   2721	 */
   2722	{
   2723		int i;
   2724
   2725		/* Release path buffers. */
   2726		if (wait_tb_buffers_run) {
   2727			pathrelse_and_restore(tb->tb_sb, tb->tb_path);
   2728		} else {
   2729			pathrelse(tb->tb_path);
   2730		}
   2731		/* brelse all resources collected for balancing */
   2732		for (i = 0; i < MAX_HEIGHT; i++) {
   2733			if (wait_tb_buffers_run) {
   2734				reiserfs_restore_prepared_buffer(tb->tb_sb,
   2735								 tb->L[i]);
   2736				reiserfs_restore_prepared_buffer(tb->tb_sb,
   2737								 tb->R[i]);
   2738				reiserfs_restore_prepared_buffer(tb->tb_sb,
   2739								 tb->FL[i]);
   2740				reiserfs_restore_prepared_buffer(tb->tb_sb,
   2741								 tb->FR[i]);
   2742				reiserfs_restore_prepared_buffer(tb->tb_sb,
   2743								 tb->
   2744								 CFL[i]);
   2745				reiserfs_restore_prepared_buffer(tb->tb_sb,
   2746								 tb->
   2747								 CFR[i]);
   2748			}
   2749
   2750			brelse(tb->L[i]);
   2751			brelse(tb->R[i]);
   2752			brelse(tb->FL[i]);
   2753			brelse(tb->FR[i]);
   2754			brelse(tb->CFL[i]);
   2755			brelse(tb->CFR[i]);
   2756
   2757			tb->L[i] = NULL;
   2758			tb->R[i] = NULL;
   2759			tb->FL[i] = NULL;
   2760			tb->FR[i] = NULL;
   2761			tb->CFL[i] = NULL;
   2762			tb->CFR[i] = NULL;
   2763		}
   2764
   2765		if (wait_tb_buffers_run) {
   2766			for (i = 0; i < MAX_FEB_SIZE; i++) {
   2767				if (tb->FEB[i])
   2768					reiserfs_restore_prepared_buffer
   2769					    (tb->tb_sb, tb->FEB[i]);
   2770			}
   2771		}
   2772		return ret;
   2773	}
   2774
   2775}
   2776
   2777void unfix_nodes(struct tree_balance *tb)
   2778{
   2779	int i;
   2780
   2781	/* Release path buffers. */
   2782	pathrelse_and_restore(tb->tb_sb, tb->tb_path);
   2783
   2784	/* brelse all resources collected for balancing */
   2785	for (i = 0; i < MAX_HEIGHT; i++) {
   2786		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
   2787		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
   2788		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
   2789		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
   2790		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
   2791		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
   2792
   2793		brelse(tb->L[i]);
   2794		brelse(tb->R[i]);
   2795		brelse(tb->FL[i]);
   2796		brelse(tb->FR[i]);
   2797		brelse(tb->CFL[i]);
   2798		brelse(tb->CFR[i]);
   2799	}
   2800
   2801	/* deal with list of allocated (used and unused) nodes */
   2802	for (i = 0; i < MAX_FEB_SIZE; i++) {
   2803		if (tb->FEB[i]) {
   2804			b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
   2805			/*
   2806			 * de-allocated block which was not used by
   2807			 * balancing and bforget about buffer for it
   2808			 */
   2809			brelse(tb->FEB[i]);
   2810			reiserfs_free_block(tb->transaction_handle, NULL,
   2811					    blocknr, 0);
   2812		}
   2813		if (tb->used[i]) {
   2814			/* release used as new nodes including a new root */
   2815			brelse(tb->used[i]);
   2816		}
   2817	}
   2818
   2819	kfree(tb->vn_buf);
   2820
   2821}