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