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