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	*/
31	static 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
51	static 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(bh: Sh, item_num: 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, affected_item_num: vn->vn_affected_item_num,
103	mode: 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(bh: Sh, ih: 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(bh: tb->CFR[0], item_num: 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(ih: item_head(bh: Sh, item_num: 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(bh: 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	*/
194	static 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	*/
280	static 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	*/
374	static 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
621	static 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	*/
652	static 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, h: 0, lnum: to_left, rnum: vn->vn_nr_item - to_left, blk_num: 0,
673	NULL, lb: -1, rb: -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, h: 0, lnum: to_left + 1, rnum: to_right + 1, blk_num: 0, NULL,
688	lb: tb->lbytes, rb: -1);
689	return 1;
690	}
691
692	return 0;
693	}
694
695	/* check whether L, S, R can be joined in one node */
696	static 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(bh: S0, item_num: 0);
721	if (tb->CFR[0]
722	&& !comp_short_le_keys(&ih->ih_key,
723	internal_key(bh: tb->CFR[0],
724	item_num: 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, h: 0, lnum: -1, rnum: -1, blk_num: -1, NULL, lb: -1, rb: -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 \
759	if (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	}\
768	else \
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 \
779	if (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	}\
787	else \
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
797	static void free_buffers_in_tb(struct tree_balance *tb)
798	{
799	int i;
800
801	pathrelse(search_path: tb->tb_path);
802
803	for (i = 0; i < MAX_HEIGHT; i++) {
804	brelse(bh: tb->L[i]);
805	brelse(bh: tb->R[i]);
806	brelse(bh: tb->FL[i]);
807	brelse(bh: tb->FR[i]);
808	brelse(bh: tb->CFL[i]);
809	brelse(bh: 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! */
827	static 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, new_blocknrs: 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, block: *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	*/
915	static 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	*/
938	static 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. */
959	static 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, block: 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(bh: left);
997	return 1;
998	}
999
1000	return 0;
1001	}
1002
1003	#define LEFT_PARENTS 'l'
1004	#define RIGHT_PARENTS 'r'
1005
1006	static 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	*/
1023	static 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(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(bh: *pcom_father)) {
1108
1109	/* Release the write lock while the buffer is busy */
1110	int depth = reiserfs_write_unlock_nested(s: tb->tb_sb);
1111	__wait_on_buffer(*pcom_father);
1112	reiserfs_write_lock_nested(s: tb->tb_sb, depth);
1113	if (FILESYSTEM_CHANGED_TB(tb)) {
1114	brelse(bh: *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(to: &s_lr_father_key,
1127	from: internal_key(bh: *pcom_father,
1128	item_num: (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(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(search_path: &s_path_to_neighbor_father);
1146	brelse(bh: *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(search_path: &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	*/
1172	static 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(bh: tb->FL[h]);
1188	brelse(bh: tb->CFL[h]);
1189	brelse(bh: tb->FR[h]);
1190	brelse(bh: 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(bh: curf);
1205	get_bh(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: h + 1, pfather: &curf,
1217	pcom_father: &curcf,
1218	LEFT_PARENTS)) != CARRY_ON)
1219	return ret;
1220	}
1221
1222	brelse(bh: tb->FL[h]);
1223	tb->FL[h] = curf; /* New initialization of FL[h]. */
1224	brelse(bh: 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: h + 1, pfather: &curf, pcom_father: &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(bh: curf);
1250	get_bh(bh: curf);
1251	tb->rkey[h] = position;
1252	}
1253
1254	brelse(bh: tb->FR[h]);
1255	/* New initialization of FR[path_offset]. */
1256	tb->FR[h] = curf;
1257
1258	brelse(bh: 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	*/
1273	static 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(bh: Sh, item_num: 0);
1282	if (tb->CFR[h])
1283	r_key = internal_key(bh: tb->CFR[h], item_num: 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, lnum: 0, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -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 */
1324	static 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, lnum: 0, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -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(mode: 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, cur_free: 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, cur_free: 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, lnum: vn->vn_nr_item + 1 - to_r, rnum: to_r, blk_num: 0, NULL,
1450	lb: -1, rb: -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, lnum: 0, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -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(mode: vn->vn_mode, tb, h,
1524	from: 0, from_bytes: -1, to: h ? vn->vn_nr_item : 0, to_bytes: -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(mode: vn->vn_mode, tb, h,
1535	from: 0, from_bytes: -1, to: 0, to_bytes: -1,
1536	snum012: 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(mode: vn->vn_mode, tb, h,
1551	from: lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1552	from_bytes: -1, to: h ? vn->vn_nr_item : 0, to_bytes: -1,
1553	snum012: snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1554	if (!h) {
1555	int lnver1;
1556
1557	lnver1 = get_num_ver(mode: vn->vn_mode, tb, h,
1558	from: lpar -
1559	((tb->lbytes != -1) ? 1 : 0),
1560	from_bytes: tb->lbytes, to: 0, to_bytes: -1,
1561	snum012: 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(mode: vn->vn_mode, tb, h,
1576	from: 0, from_bytes: -1,
1577	to: h ? (vn->vn_nr_item - rpar) : (rpar -
1578	((tb->
1579	rbytes !=
1580	-1) ? 1 :
1581	0)), to_bytes: -1,
1582	snum012: snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1583	if (!h) {
1584	int rnver1;
1585
1586	rnver1 = get_num_ver(mode: vn->vn_mode, tb, h,
1587	from: 0, from_bytes: -1,
1588	to: (rpar -
1589	((tb->rbytes != -1) ? 1 : 0)),
1590	to_bytes: tb->rbytes,
1591	snum012: 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(mode: vn->vn_mode, tb, h,
1606	from: lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1607	from_bytes: -1,
1608	to: h ? (vn->vn_nr_item - rpar) : (rpar -
1609	((tb->
1610	rbytes !=
1611	-1) ? 1 :
1612	0)), to_bytes: -1,
1613	snum012: snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1614	if (!h) {
1615	int lrnver1;
1616
1617	lrnver1 = get_num_ver(mode: vn->vn_mode, tb, h,
1618	from: lpar -
1619	((tb->lbytes != -1) ? 1 : 0),
1620	from_bytes: tb->lbytes,
1621	to: (rpar -
1622	((tb->rbytes != -1) ? 1 : 0)),
1623	to_bytes: tb->rbytes,
1624	snum012: 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, lnum: tb->lnum[h], rnum: tb->rnum[h],
1645	blk_num: lrnver, s012: snum012 + lrset,
1646	lb: tb->lbytes, rb: tb->rbytes);
1647	else
1648	set_parameters(tb, h,
1649	lnum: tb->lnum[h] -
1650	((tb->lbytes == -1) ? 0 : 1),
1651	rnum: tb->rnum[h] -
1652	((tb->rbytes == -1) ? 0 : 1),
1653	blk_num: lrnver, s012: snum012 + lrset, lb: -1, rb: -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, lnum: 0, rnum: 0, blk_num: nver, s012: snum012 + nset, lb: -1,
1664	rb: -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	*/
1726	static 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, lnum: 0, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -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, lnum: 0, rnum: 0, blk_num: 0, NULL, lb: -1, rb: -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, cur_free: lfree);
1773	check_right(tb, h, cur_free: 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, lnum: -n - 1, rnum: 0, blk_num: 0, NULL, lb: -1,
1798	rb: -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, lnum: 0, rnum: -n - 1, blk_num: 0, NULL, lb: -1,
1815	rb: -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, lnum: vn->vn_nr_item + 1 - to_r, rnum: to_r,
1832	blk_num: 0, NULL, lb: -1, rb: -1);
1833	return CARRY_ON;
1834	}
1835
1836	/* Balancing does not lead to better packing. */
1837	set_parameters(tb, h, lnum: 0, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -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, lnum: -n - 1, rnum: 0, blk_num: 0, NULL, lb: -1, rb: -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, lnum: 0, rnum: -n - 1, blk_num: 0, NULL, lb: -1, rb: -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, lnum: vn->vn_nr_item + 1 - to_r, rnum: to_r, blk_num: 0, NULL,
1887	lb: -1, rb: -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, lnum: -from_l, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -1);
1902	return CARRY_ON;
1903	}
1904
1905	set_parameters(tb, h, lnum: 0,
1906	rnum: -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1907	1) / 2 - (vn->vn_nr_item + 1)), blk_num: 1, NULL, lb: -1, rb: -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	*/
1925	static 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, lnum: 0, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -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, cur_free: lfree);
1983	check_right(tb, h, cur_free: 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, lnum: -1, rnum: 0, blk_num: 0, NULL, lb: -1, rb: -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, lnum: 0, rnum: -1, blk_num: 0, NULL, lb: -1, rb: -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, lnum: 0, rnum: 0, blk_num: 1, NULL, lb: -1, rb: -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	*/
2031	static 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	*/
2061	static 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.*/
2090	static 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(s: tb->tb_sb);
2131	__wait_on_buffer(bh);
2132	reiserfs_write_lock_nested(s: 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	*/
2151	static 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(s: tb->tb_sb);
2177	bh = sb_bread(sb, block: son_number);
2178	reiserfs_write_lock_nested(s: 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(bh: 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(s: tb->tb_sb);
2217	bh = sb_bread(sb, block: son_number);
2218	reiserfs_write_lock_nested(s: 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(bh: 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
2241	static 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) +
2256	struct_size_t(struct direntry_uarea, entry_sizes,
2257	max_num_of_entries));
2258	}
2259
2260	/*
2261	* maybe we should fail balancing we are going to perform when kmalloc
2262	* fails several times. But now it will loop until kmalloc gets
2263	* required memory
2264	*/
2265	static int get_mem_for_virtual_node(struct tree_balance *tb)
2266	{
2267	int check_fs = 0;
2268	int size;
2269	char *buf;
2270
2271	size = get_virtual_node_size(sb: tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
2272
2273	/* we have to allocate more memory for virtual node */
2274	if (size > tb->vn_buf_size) {
2275	if (tb->vn_buf) {
2276	/* free memory allocated before */
2277	kfree(objp: tb->vn_buf);
2278	/* this is not needed if kfree is atomic */
2279	check_fs = 1;
2280	}
2281
2282	/* virtual node requires now more memory */
2283	tb->vn_buf_size = size;
2284
2285	/* get memory for virtual item */
2286	buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
2287	if (!buf) {
2288	/*
2289	* getting memory with GFP_KERNEL priority may involve
2290	* balancing now (due to indirect_to_direct conversion
2291	* on dcache shrinking). So, release path and collected
2292	* resources here
2293	*/
2294	free_buffers_in_tb(tb);
2295	buf = kmalloc(size, GFP_NOFS);
2296	if (!buf) {
2297	tb->vn_buf_size = 0;
2298	}
2299	tb->vn_buf = buf;
2300	schedule();
2301	return REPEAT_SEARCH;
2302	}
2303
2304	tb->vn_buf = buf;
2305	}
2306
2307	if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2308	return REPEAT_SEARCH;
2309
2310	return CARRY_ON;
2311	}
2312
2313	#ifdef CONFIG_REISERFS_CHECK
2314	static void tb_buffer_sanity_check(struct super_block *sb,
2315	struct buffer_head *bh,
2316	const char *descr, int level)
2317	{
2318	if (bh) {
2319	if (atomic_read(v: &(bh->b_count)) <= 0)
2320
2321	reiserfs_panic(sb, "jmacd-1", "negative or zero "
2322	"reference counter for buffer %s[%d] "
2323	"(%b)", descr, level, bh);
2324
2325	if (!buffer_uptodate(bh))
2326	reiserfs_panic(sb, "jmacd-2", "buffer is not up "
2327	"to date %s[%d] (%b)",
2328	descr, level, bh);
2329
2330	if (!B_IS_IN_TREE(bh))
2331	reiserfs_panic(sb, "jmacd-3", "buffer is not "
2332	"in tree %s[%d] (%b)",
2333	descr, level, bh);
2334
2335	if (bh->b_bdev != sb->s_bdev)
2336	reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
2337	"device %s[%d] (%b)",
2338	descr, level, bh);
2339
2340	if (bh->b_size != sb->s_blocksize)
2341	reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
2342	"blocksize %s[%d] (%b)",
2343	descr, level, bh);
2344
2345	if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
2346	reiserfs_panic(sb, "jmacd-6", "buffer block "
2347	"number too high %s[%d] (%b)",
2348	descr, level, bh);
2349	}
2350	}
2351	#else
2352	static void tb_buffer_sanity_check(struct super_block *sb,
2353	struct buffer_head *bh,
2354	const char *descr, int level)
2355	{;
2356	}
2357	#endif
2358
2359	static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
2360	{
2361	return reiserfs_prepare_for_journal(s, bh, wait: 0);
2362	}
2363
2364	static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
2365	{
2366	struct buffer_head *locked;
2367	#ifdef CONFIG_REISERFS_CHECK
2368	int repeat_counter = 0;
2369	#endif
2370	int i;
2371
2372	do {
2373
2374	locked = NULL;
2375
2376	for (i = tb->tb_path->path_length;
2377	!locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2378	if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
2379	/*
2380	* if I understand correctly, we can only
2381	* be sure the last buffer in the path is
2382	* in the tree --clm
2383	*/
2384	#ifdef CONFIG_REISERFS_CHECK
2385	if (PATH_PLAST_BUFFER(tb->tb_path) ==
2386	PATH_OFFSET_PBUFFER(tb->tb_path, i))
2387	tb_buffer_sanity_check(sb: tb->tb_sb,
2388	PATH_OFFSET_PBUFFER
2389	(tb->tb_path,
2390	i), descr: "S",
2391	level: tb->tb_path->
2392	path_length - i);
2393	#endif
2394	if (!clear_all_dirty_bits(s: tb->tb_sb,
2395	PATH_OFFSET_PBUFFER
2396	(tb->tb_path,
2397	i))) {
2398	locked =
2399	PATH_OFFSET_PBUFFER(tb->tb_path,
2400	i);
2401	}
2402	}
2403	}
2404
2405	for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
2406	i++) {
2407
2408	if (tb->lnum[i]) {
2409
2410	if (tb->L[i]) {
2411	tb_buffer_sanity_check(sb: tb->tb_sb,
2412	bh: tb->L[i],
2413	descr: "L", level: i);
2414	if (!clear_all_dirty_bits
2415	(s: tb->tb_sb, bh: tb->L[i]))
2416	locked = tb->L[i];
2417	}
2418
2419	if (!locked && tb->FL[i]) {
2420	tb_buffer_sanity_check(sb: tb->tb_sb,
2421	bh: tb->FL[i],
2422	descr: "FL", level: i);
2423	if (!clear_all_dirty_bits
2424	(s: tb->tb_sb, bh: tb->FL[i]))
2425	locked = tb->FL[i];
2426	}
2427
2428	if (!locked && tb->CFL[i]) {
2429	tb_buffer_sanity_check(sb: tb->tb_sb,
2430	bh: tb->CFL[i],
2431	descr: "CFL", level: i);
2432	if (!clear_all_dirty_bits
2433	(s: tb->tb_sb, bh: tb->CFL[i]))
2434	locked = tb->CFL[i];
2435	}
2436
2437	}
2438
2439	if (!locked && (tb->rnum[i])) {
2440
2441	if (tb->R[i]) {
2442	tb_buffer_sanity_check(sb: tb->tb_sb,
2443	bh: tb->R[i],
2444	descr: "R", level: i);
2445	if (!clear_all_dirty_bits
2446	(s: tb->tb_sb, bh: tb->R[i]))
2447	locked = tb->R[i];
2448	}
2449
2450	if (!locked && tb->FR[i]) {
2451	tb_buffer_sanity_check(sb: tb->tb_sb,
2452	bh: tb->FR[i],
2453	descr: "FR", level: i);
2454	if (!clear_all_dirty_bits
2455	(s: tb->tb_sb, bh: tb->FR[i]))
2456	locked = tb->FR[i];
2457	}
2458
2459	if (!locked && tb->CFR[i]) {
2460	tb_buffer_sanity_check(sb: tb->tb_sb,
2461	bh: tb->CFR[i],
2462	descr: "CFR", level: i);
2463	if (!clear_all_dirty_bits
2464	(s: tb->tb_sb, bh: tb->CFR[i]))
2465	locked = tb->CFR[i];
2466	}
2467	}
2468	}
2469
2470	/*
2471	* as far as I can tell, this is not required. The FEB list
2472	* seems to be full of newly allocated nodes, which will
2473	* never be locked, dirty, or anything else.
2474	* To be safe, I'm putting in the checks and waits in.
2475	* For the moment, they are needed to keep the code in
2476	* journal.c from complaining about the buffer.
2477	* That code is inside CONFIG_REISERFS_CHECK as well. --clm
2478	*/
2479	for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2480	if (tb->FEB[i]) {
2481	if (!clear_all_dirty_bits
2482	(s: tb->tb_sb, bh: tb->FEB[i]))
2483	locked = tb->FEB[i];
2484	}
2485	}
2486
2487	if (locked) {
2488	int depth;
2489	#ifdef CONFIG_REISERFS_CHECK
2490	repeat_counter++;
2491	if ((repeat_counter % 10000) == 0) {
2492	reiserfs_warning(tb->tb_sb, "reiserfs-8200",
2493	"too many iterations waiting "
2494	"for buffer to unlock "
2495	"(%b)", locked);
2496
2497	/* Don't loop forever. Try to recover from possible error. */
2498
2499	return (FILESYSTEM_CHANGED_TB(tb)) ?
2500	REPEAT_SEARCH : CARRY_ON;
2501	}
2502	#endif
2503	depth = reiserfs_write_unlock_nested(s: tb->tb_sb);
2504	__wait_on_buffer(locked);
2505	reiserfs_write_lock_nested(s: tb->tb_sb, depth);
2506	if (FILESYSTEM_CHANGED_TB(tb))
2507	return REPEAT_SEARCH;
2508	}
2509
2510	} while (locked);
2511
2512	return CARRY_ON;
2513	}
2514
2515	/*
2516	* Prepare for balancing, that is
2517	* get all necessary parents, and neighbors;
2518	* analyze what and where should be moved;
2519	* get sufficient number of new nodes;
2520	* Balancing will start only after all resources will be collected at a time.
2521	*
2522	* When ported to SMP kernels, only at the last moment after all needed nodes
2523	* are collected in cache, will the resources be locked using the usual
2524	* textbook ordered lock acquisition algorithms. Note that ensuring that
2525	* this code neither write locks what it does not need to write lock nor locks
2526	* out of order will be a pain in the butt that could have been avoided.
2527	* Grumble grumble. -Hans
2528	*
2529	* fix is meant in the sense of render unchanging
2530	*
2531	* Latency might be improved by first gathering a list of what buffers
2532	* are needed and then getting as many of them in parallel as possible? -Hans
2533	*
2534	* Parameters:
2535	* op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2536	* tb tree_balance structure;
2537	* inum item number in S[h];
2538	* pos_in_item - comment this if you can
2539	* ins_ih item head of item being inserted
2540	* data inserted item or data to be pasted
2541	* Returns: 1 - schedule occurred while the function worked;
2542	* 0 - schedule didn't occur while the function worked;
2543	* -1 - if no_disk_space
2544	*/
2545
2546	int fix_nodes(int op_mode, struct tree_balance *tb,
2547	struct item_head *ins_ih, const void *data)
2548	{
2549	int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2550	int pos_in_item;
2551
2552	/*
2553	* we set wait_tb_buffers_run when we have to restore any dirty
2554	* bits cleared during wait_tb_buffers_run
2555	*/
2556	int wait_tb_buffers_run = 0;
2557	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
2558
2559	++REISERFS_SB(sb: tb->tb_sb)->s_fix_nodes;
2560
2561	pos_in_item = tb->tb_path->pos_in_item;
2562
2563	tb->fs_gen = get_generation(tb->tb_sb);
2564
2565	/*
2566	* we prepare and log the super here so it will already be in the
2567	* transaction when do_balance needs to change it.
2568	* This way do_balance won't have to schedule when trying to prepare
2569	* the super for logging
2570	*/
2571	reiserfs_prepare_for_journal(tb->tb_sb,
2572	SB_BUFFER_WITH_SB(tb->tb_sb), wait: 1);
2573	journal_mark_dirty(tb->transaction_handle,
2574	SB_BUFFER_WITH_SB(tb->tb_sb));
2575	if (FILESYSTEM_CHANGED_TB(tb))
2576	return REPEAT_SEARCH;
2577
2578	/* if it possible in indirect_to_direct conversion */
2579	if (buffer_locked(bh: tbS0)) {
2580	int depth = reiserfs_write_unlock_nested(s: tb->tb_sb);
2581	__wait_on_buffer(tbS0);
2582	reiserfs_write_lock_nested(s: tb->tb_sb, depth);
2583	if (FILESYSTEM_CHANGED_TB(tb))
2584	return REPEAT_SEARCH;
2585	}
2586	#ifdef CONFIG_REISERFS_CHECK
2587	if (REISERFS_SB(sb: tb->tb_sb)->cur_tb) {
2588	print_cur_tb(mes: "fix_nodes");
2589	reiserfs_panic(tb->tb_sb, "PAP-8305",
2590	"there is pending do_balance");
2591	}
2592
2593	if (!buffer_uptodate(bh: tbS0) || !B_IS_IN_TREE(tbS0))
2594	reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
2595	"not uptodate at the beginning of fix_nodes "
2596	"or not in tree (mode %c)",
2597	tbS0, tbS0, op_mode);
2598
2599	/* Check parameters. */
2600	switch (op_mode) {
2601	case M_INSERT:
2602	if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
2603	reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
2604	"item number %d (in S0 - %d) in case "
2605	"of insert", item_num,
2606	B_NR_ITEMS(tbS0));
2607	break;
2608	case M_PASTE:
2609	case M_DELETE:
2610	case M_CUT:
2611	if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
2612	print_block(bh: tbS0, 0, -1, -1);
2613	reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
2614	"item number(%d); mode = %c "
2615	"insert_size = %d",
2616	item_num, op_mode,
2617	tb->insert_size[0]);
2618	}
2619	break;
2620	default:
2621	reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
2622	"of operation");
2623	}
2624	#endif
2625
2626	if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
2627	/* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
2628	return REPEAT_SEARCH;
2629
2630	/* Starting from the leaf level; for all levels h of the tree. */
2631	for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
2632	ret = get_direct_parent(tb, h);
2633	if (ret != CARRY_ON)
2634	goto repeat;
2635
2636	ret = check_balance(mode: op_mode, tb, h, inum: item_num,
2637	pos_in_item, ins_ih, data);
2638	if (ret != CARRY_ON) {
2639	if (ret == NO_BALANCING_NEEDED) {
2640	/* No balancing for higher levels needed. */
2641	ret = get_neighbors(tb, h);
2642	if (ret != CARRY_ON)
2643	goto repeat;
2644	if (h != MAX_HEIGHT - 1)
2645	tb->insert_size[h + 1] = 0;
2646	/*
2647	* ok, analysis and resource gathering
2648	* are complete
2649	*/
2650	break;
2651	}
2652	goto repeat;
2653	}
2654
2655	ret = get_neighbors(tb, h);
2656	if (ret != CARRY_ON)
2657	goto repeat;
2658
2659	/*
2660	* No disk space, or schedule occurred and analysis may be
2661	* invalid and needs to be redone.
2662	*/
2663	ret = get_empty_nodes(tb, h);
2664	if (ret != CARRY_ON)
2665	goto repeat;
2666
2667	/*
2668	* We have a positive insert size but no nodes exist on this
2669	* level, this means that we are creating a new root.
2670	*/
2671	if (!PATH_H_PBUFFER(tb->tb_path, h)) {
2672
2673	RFALSE(tb->blknum[h] != 1,
2674	"PAP-8350: creating new empty root");
2675
2676	if (h < MAX_HEIGHT - 1)
2677	tb->insert_size[h + 1] = 0;
2678	} else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
2679	/*
2680	* The tree needs to be grown, so this node S[h]
2681	* which is the root node is split into two nodes,
2682	* and a new node (S[h+1]) will be created to
2683	* become the root node.
2684	*/
2685	if (tb->blknum[h] > 1) {
2686
2687	RFALSE(h == MAX_HEIGHT - 1,
2688	"PAP-8355: attempt to create too high of a tree");
2689
2690	tb->insert_size[h + 1] =
2691	(DC_SIZE +
2692	KEY_SIZE) * (tb->blknum[h] - 1) +
2693	DC_SIZE;
2694	} else if (h < MAX_HEIGHT - 1)
2695	tb->insert_size[h + 1] = 0;
2696	} else
2697	tb->insert_size[h + 1] =
2698	(DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
2699	}
2700
2701	ret = wait_tb_buffers_until_unlocked(tb);
2702	if (ret == CARRY_ON) {
2703	if (FILESYSTEM_CHANGED_TB(tb)) {
2704	wait_tb_buffers_run = 1;
2705	ret = REPEAT_SEARCH;
2706	goto repeat;
2707	} else {
2708	return CARRY_ON;
2709	}
2710	} else {
2711	wait_tb_buffers_run = 1;
2712	goto repeat;
2713	}
2714
2715	repeat:
2716	/*
2717	* fix_nodes was unable to perform its calculation due to
2718	* filesystem got changed under us, lack of free disk space or i/o
2719	* failure. If the first is the case - the search will be
2720	* repeated. For now - free all resources acquired so far except
2721	* for the new allocated nodes
2722	*/
2723	{
2724	int i;
2725
2726	/* Release path buffers. */
2727	if (wait_tb_buffers_run) {
2728	pathrelse_and_restore(s: tb->tb_sb, search_path: tb->tb_path);
2729	} else {
2730	pathrelse(search_path: tb->tb_path);
2731	}
2732	/* brelse all resources collected for balancing */
2733	for (i = 0; i < MAX_HEIGHT; i++) {
2734	if (wait_tb_buffers_run) {
2735	reiserfs_restore_prepared_buffer(tb->tb_sb,
2736	bh: tb->L[i]);
2737	reiserfs_restore_prepared_buffer(tb->tb_sb,
2738	bh: tb->R[i]);
2739	reiserfs_restore_prepared_buffer(tb->tb_sb,
2740	bh: tb->FL[i]);
2741	reiserfs_restore_prepared_buffer(tb->tb_sb,
2742	bh: tb->FR[i]);
2743	reiserfs_restore_prepared_buffer(tb->tb_sb,
2744	bh: tb->
2745	CFL[i]);
2746	reiserfs_restore_prepared_buffer(tb->tb_sb,
2747	bh: tb->
2748	CFR[i]);
2749	}
2750
2751	brelse(bh: tb->L[i]);
2752	brelse(bh: tb->R[i]);
2753	brelse(bh: tb->FL[i]);
2754	brelse(bh: tb->FR[i]);
2755	brelse(bh: tb->CFL[i]);
2756	brelse(bh: tb->CFR[i]);
2757
2758	tb->L[i] = NULL;
2759	tb->R[i] = NULL;
2760	tb->FL[i] = NULL;
2761	tb->FR[i] = NULL;
2762	tb->CFL[i] = NULL;
2763	tb->CFR[i] = NULL;
2764	}
2765
2766	if (wait_tb_buffers_run) {
2767	for (i = 0; i < MAX_FEB_SIZE; i++) {
2768	if (tb->FEB[i])
2769	reiserfs_restore_prepared_buffer
2770	(tb->tb_sb, bh: tb->FEB[i]);
2771	}
2772	}
2773	return ret;
2774	}
2775
2776	}
2777
2778	void unfix_nodes(struct tree_balance *tb)
2779	{
2780	int i;
2781
2782	/* Release path buffers. */
2783	pathrelse_and_restore(s: tb->tb_sb, search_path: tb->tb_path);
2784
2785	/* brelse all resources collected for balancing */
2786	for (i = 0; i < MAX_HEIGHT; i++) {
2787	reiserfs_restore_prepared_buffer(tb->tb_sb, bh: tb->L[i]);
2788	reiserfs_restore_prepared_buffer(tb->tb_sb, bh: tb->R[i]);
2789	reiserfs_restore_prepared_buffer(tb->tb_sb, bh: tb->FL[i]);
2790	reiserfs_restore_prepared_buffer(tb->tb_sb, bh: tb->FR[i]);
2791	reiserfs_restore_prepared_buffer(tb->tb_sb, bh: tb->CFL[i]);
2792	reiserfs_restore_prepared_buffer(tb->tb_sb, bh: tb->CFR[i]);
2793
2794	brelse(bh: tb->L[i]);
2795	brelse(bh: tb->R[i]);
2796	brelse(bh: tb->FL[i]);
2797	brelse(bh: tb->FR[i]);
2798	brelse(bh: tb->CFL[i]);
2799	brelse(bh: tb->CFR[i]);
2800	}
2801
2802	/* deal with list of allocated (used and unused) nodes */
2803	for (i = 0; i < MAX_FEB_SIZE; i++) {
2804	if (tb->FEB[i]) {
2805	b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2806	/*
2807	* de-allocated block which was not used by
2808	* balancing and bforget about buffer for it
2809	*/
2810	brelse(bh: tb->FEB[i]);
2811	reiserfs_free_block(th: tb->transaction_handle, NULL,
2812	blocknr, for_unformatted: 0);
2813	}
2814	if (tb->used[i]) {
2815	/* release used as new nodes including a new root */
2816	brelse(bh: tb->used[i]);
2817	}
2818	}
2819
2820	kfree(objp: tb->vn_buf);
2821
2822	}
2823