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  */
old_item_num(int new_num,int affected_item_num,int mode)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 
create_virtual_node(struct tree_balance * tb,int h)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(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  */
check_left(struct tree_balance * tb,int h,int cur_free)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  */
check_right(struct tree_balance * tb,int h,int cur_free)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  */
get_num_ver(int mode,struct tree_balance * tb,int h,int from,int from_bytes,int to,int to_bytes,short * snum012,int flow)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 
set_parameters(struct tree_balance * tb,int h,int lnum,int rnum,int blk_num,short * s012,int lb,int rb)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  */
is_leaf_removable(struct tree_balance * tb)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, 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 */
are_leaves_removable(struct tree_balance * tb,int lfree,int rfree)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(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 \
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 
free_buffers_in_tb(struct tree_balance * tb)797 static 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! */
get_empty_nodes(struct tree_balance * tb,int h)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, 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  */
get_lfree(struct tree_balance * tb,int h)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  */
get_rfree(struct tree_balance * tb,int h)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. */
is_left_neighbor_in_cache(struct tree_balance * tb,int h)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, 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 
decrement_key(struct cpu_key * key)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  */
get_far_parent(struct tree_balance * tb,int h,struct buffer_head ** pfather,struct buffer_head ** pcom_father,char c_lr_par)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(*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  */
get_parents(struct tree_balance * tb,int h)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(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  */
can_node_be_removed(int mode,int lfree,int sfree,int rfree,struct tree_balance * tb,int h)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(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 */
ip_check_balance(struct tree_balance * tb,int h)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, 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  */
dc_check_balance_internal(struct tree_balance * tb,int h)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, 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  */
dc_check_balance_leaf(struct tree_balance * tb,int h)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, 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  */
dc_check_balance(struct tree_balance * tb,int h)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  */
check_balance(int mode,struct tree_balance * tb,int h,int inum,int pos_in_item,struct item_head * ins_ih,const void * data)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.*/
get_direct_parent(struct tree_balance * tb,int h)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(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  */
get_neighbors(struct tree_balance * tb,int h)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(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 
get_virtual_node_size(struct super_block * sb,struct buffer_head * bh)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  */
get_mem_for_virtual_node(struct tree_balance * tb)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(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(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
tb_buffer_sanity_check(struct super_block * sb,struct buffer_head * bh,const char * descr,int level)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(&(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
tb_buffer_sanity_check(struct super_block * sb,struct buffer_head * bh,const char * descr,int level)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 
clear_all_dirty_bits(struct super_block * s,struct buffer_head * bh)2359 static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
2360 {
2361 	return reiserfs_prepare_for_journal(s, bh, 0);
2362 }
2363 
wait_tb_buffers_until_unlocked(struct tree_balance * tb)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(tb->tb_sb,
2388 							       PATH_OFFSET_PBUFFER
2389 							       (tb->tb_path,
2390 								i), "S",
2391 							       tb->tb_path->
2392 							       path_length - i);
2393 #endif
2394 				if (!clear_all_dirty_bits(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(tb->tb_sb,
2412 							       tb->L[i],
2413 							       "L", i);
2414 					if (!clear_all_dirty_bits
2415 					    (tb->tb_sb, tb->L[i]))
2416 						locked = tb->L[i];
2417 				}
2418 
2419 				if (!locked && tb->FL[i]) {
2420 					tb_buffer_sanity_check(tb->tb_sb,
2421 							       tb->FL[i],
2422 							       "FL", i);
2423 					if (!clear_all_dirty_bits
2424 					    (tb->tb_sb, tb->FL[i]))
2425 						locked = tb->FL[i];
2426 				}
2427 
2428 				if (!locked && tb->CFL[i]) {
2429 					tb_buffer_sanity_check(tb->tb_sb,
2430 							       tb->CFL[i],
2431 							       "CFL", i);
2432 					if (!clear_all_dirty_bits
2433 					    (tb->tb_sb, 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(tb->tb_sb,
2443 							       tb->R[i],
2444 							       "R", i);
2445 					if (!clear_all_dirty_bits
2446 					    (tb->tb_sb, tb->R[i]))
2447 						locked = tb->R[i];
2448 				}
2449 
2450 				if (!locked && tb->FR[i]) {
2451 					tb_buffer_sanity_check(tb->tb_sb,
2452 							       tb->FR[i],
2453 							       "FR", i);
2454 					if (!clear_all_dirty_bits
2455 					    (tb->tb_sb, tb->FR[i]))
2456 						locked = tb->FR[i];
2457 				}
2458 
2459 				if (!locked && tb->CFR[i]) {
2460 					tb_buffer_sanity_check(tb->tb_sb,
2461 							       tb->CFR[i],
2462 							       "CFR", i);
2463 					if (!clear_all_dirty_bits
2464 					    (tb->tb_sb, 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 				    (tb->tb_sb, 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(tb->tb_sb);
2504 			__wait_on_buffer(locked);
2505 			reiserfs_write_lock_nested(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 
fix_nodes(int op_mode,struct tree_balance * tb,struct item_head * ins_ih,const void * data)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(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), 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(tbS0)) {
2580 		int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2581 		__wait_on_buffer(tbS0);
2582 		reiserfs_write_lock_nested(tb->tb_sb, depth);
2583 		if (FILESYSTEM_CHANGED_TB(tb))
2584 			return REPEAT_SEARCH;
2585 	}
2586 #ifdef CONFIG_REISERFS_CHECK
2587 	if (REISERFS_SB(tb->tb_sb)->cur_tb) {
2588 		print_cur_tb("fix_nodes");
2589 		reiserfs_panic(tb->tb_sb, "PAP-8305",
2590 			       "there is pending do_balance");
2591 	}
2592 
2593 	if (!buffer_uptodate(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(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(op_mode, tb, h, 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(tb->tb_sb, tb->tb_path);
2729 		} else {
2730 			pathrelse(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 								 tb->L[i]);
2737 				reiserfs_restore_prepared_buffer(tb->tb_sb,
2738 								 tb->R[i]);
2739 				reiserfs_restore_prepared_buffer(tb->tb_sb,
2740 								 tb->FL[i]);
2741 				reiserfs_restore_prepared_buffer(tb->tb_sb,
2742 								 tb->FR[i]);
2743 				reiserfs_restore_prepared_buffer(tb->tb_sb,
2744 								 tb->
2745 								 CFL[i]);
2746 				reiserfs_restore_prepared_buffer(tb->tb_sb,
2747 								 tb->
2748 								 CFR[i]);
2749 			}
2750 
2751 			brelse(tb->L[i]);
2752 			brelse(tb->R[i]);
2753 			brelse(tb->FL[i]);
2754 			brelse(tb->FR[i]);
2755 			brelse(tb->CFL[i]);
2756 			brelse(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, tb->FEB[i]);
2771 			}
2772 		}
2773 		return ret;
2774 	}
2775 
2776 }
2777 
unfix_nodes(struct tree_balance * tb)2778 void unfix_nodes(struct tree_balance *tb)
2779 {
2780 	int i;
2781 
2782 	/* Release path buffers. */
2783 	pathrelse_and_restore(tb->tb_sb, 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, tb->L[i]);
2788 		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2789 		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2790 		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2791 		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2792 		reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
2793 
2794 		brelse(tb->L[i]);
2795 		brelse(tb->R[i]);
2796 		brelse(tb->FL[i]);
2797 		brelse(tb->FR[i]);
2798 		brelse(tb->CFL[i]);
2799 		brelse(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(tb->FEB[i]);
2811 			reiserfs_free_block(tb->transaction_handle, NULL,
2812 					    blocknr, 0);
2813 		}
2814 		if (tb->used[i]) {
2815 			/* release used as new nodes including a new root */
2816 			brelse(tb->used[i]);
2817 		}
2818 	}
2819 
2820 	kfree(tb->vn_buf);
2821 
2822 }
2823