]> bbs.cooldavid.org Git - net-next-2.6.git/blame - fs/reiserfs/fix_node.c
git://bbs.cooldavid.org / net-next-2.6.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
xps: Transmit Packet Steering
[net-next-2.6.git] / fs / reiserfs / fix_node.c
CommitLineData
1da177e4
LT		 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
0222e657
JM		 33 **
34 **
1da177e4
LT		 35 **/
36
1da177e4 37#include <linux/time.h>
5a0e3ad6 38#include <linux/slab.h>
1da177e4
LT		 39#include <linux/string.h>
40#include <linux/reiserfs_fs.h>
41#include <linux/buffer_head.h>
42
1da177e4
LT		 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
1da177e4 57/* taking item number in virtual node, returns number of item, that it has in source buffer */
bd4c625c 58static inline int old_item_num(int new_num, int affected_item_num, int mode)
1da177e4 59{
bd4c625c
LT		 60 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
61 return new_num;
1da177e4 62
bd4c625c 63 if (mode == M_INSERT) {
1da177e4 64
bd4c625c
LT		 65 RFALSE(new_num == 0,
66 "vs-8005: for INSERT mode and item number of inserted item");
1da177e4 67
bd4c625c
LT		 68 return new_num - 1;
69 }
1da177e4 70
bd4c625c
LT		 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;
1da177e4
LT		 76}
77
bd4c625c 78static void create_virtual_node(struct tree_balance *tb, int h)
1da177e4 79{
bd4c625c
LT		 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] */
1da177e4 84
bd4c625c 85 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1da177e4 86
bd4c625c
LT		 87 /* size of changed node */
88 vn->vn_size =
89 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
1da177e4 90
bd4c625c
LT		 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;
1da177e4 95 }
1da177e4 96
bd4c625c
LT		 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)
c3a9c210 139 reiserfs_panic(tb->tb_sb, "vs-8030",
bd4c625c
LT		 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 }
1da177e4 150 }
bd4c625c
LT		 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
9dce07f1 156 RFALSE(vn->vn_ins_ih == NULL,
bd4c625c
LT		 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);
c3a9c210
JM		 189 reiserfs_panic(tb->tb_sb, "vs-8045",
190 "rdkey %k, affected item==%d "
191 "(mode==%c) Must be %c",
bd4c625c
LT		 192 key, vn->vn_affected_item_num,
193 vn->vn_mode, M_DELETE);
cd02b966 194 }
bd4c625c 195 }
1da177e4 196#endif
1da177e4 197
bd4c625c
LT		 198 }
199}
1da177e4
LT		 200
201/* using virtual node check, how many items can be shifted to left
202 neighbor */
bd4c625c 203static void check_left(struct tree_balance *tb, int h, int cur_free)
1da177e4 204{
bd4c625c
LT		 205 int i;
206 struct virtual_node *vn = tb->tb_vn;
207 struct virtual_item *vi;
208 int d_size, ih_size;
1da177e4 209
bd4c625c 210 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
1da177e4 211
bd4c625c
LT		 212 /* internal level */
213 if (h > 0) {
214 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
215 return;
216 }
1da177e4 217
bd4c625c 218 /* leaf level */
1da177e4 219
bd4c625c
LT		 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 }
1da177e4 226
bd4c625c
LT		 227 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
228 "vs-8055: parent does not exist or invalid");
1da177e4 229
bd4c625c
LT		 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] */
1da177e4 235
bd4c625c
LT		 236 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
237 "vs-8055: invalid mode or balance condition failed");
1da177e4 238
bd4c625c
LT		 239 tb->lnum[0] = vn->vn_nr_item;
240 tb->lbytes = -1;
241 return;
1da177e4 242 }
bd4c625c
LT		 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;
1da177e4 276 }
1da177e4 277
bd4c625c
LT		 278 return;
279}
1da177e4
LT		 280
281/* using virtual node check, how many items can be shifted to right
282 neighbor */
bd4c625c 283static void check_right(struct tree_balance *tb, int h, int cur_free)
1da177e4 284{
bd4c625c
LT		 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;
1da177e4 296 }
bd4c625c
LT		 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;
1da177e4 305 }
1da177e4 306
bd4c625c
LT		 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}
1da177e4
LT		 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 */
bd4c625c
LT		 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)
1da177e4 369{
bd4c625c
LT		 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 */
0222e657 381 start_bytes, /* number of first bytes (entries for directory) of start_item-th item
bd4c625c 382 we do not include into node that is being filled */
0222e657 383 end_bytes; /* number of last bytes (entries for directory) of end_item-th item
bd4c625c
LT		 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);
1da177e4
LT		 412 }
413
bd4c625c
LT		 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)
45b03d5e
JM		 500 reiserfs_warning(tb->tb_sb, "vs-8111",
501 "split_item_position is out of range");
bd4c625c
LT		 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;
1da177e4
LT		 509 }
510
bd4c625c
LT		 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)
45b03d5e
JM		 537 reiserfs_warning(tb->tb_sb, "vs-8115",
538 "not directory or indirect item");
1da177e4
LT		 539 }
540
bd4c625c
LT		 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;
1da177e4
LT		 562 }
563
bd4c625c 564 return needed_nodes;
1da177e4
LT		 565}
566
1da177e4 567
1da177e4
LT		 568/* Set parameters for balancing.
569 * Performs write of results of analysis of balancing into structure tb,
0222e657 570 * where it will later be used by the functions that actually do the balancing.
1da177e4
LT		 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
bd4c625c
LT		 585static void set_parameters(struct tree_balance *tb, int h, int lnum,
586 int rnum, int blk_num, short *s012, int lb, int rb)
1da177e4
LT		 587{
588
bd4c625c
LT		 589 tb->lnum[h] = lnum;
590 tb->rnum[h] = rnum;
591 tb->blknum[h] = blk_num;
1da177e4 592
bd4c625c
LT		 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;
1da177e4 602 }
bd4c625c
LT		 603 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
604 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
1da177e4 605
bd4c625c
LT		 606 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
607 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
608}
1da177e4
LT		 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. */
bd4c625c 612static int is_leaf_removable(struct tree_balance *tb)
1da177e4 613{
bd4c625c
LT		 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 }
1da177e4 634
bd4c625c
LT		 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}
1da177e4
LT		 652
653/* check whether L, S, R can be joined in one node */
bd4c625c 654static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
1da177e4 655{
bd4c625c
LT		 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 }
1da177e4 698
bd4c625c
LT		 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;
1da177e4 707
bd4c625c 708}
1da177e4
LT		 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
1da177e4
LT		 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
a063ae17 750static void free_buffers_in_tb(struct tree_balance *tb)
bd4c625c 751{
ee93961b 752 int i;
bd4c625c 753
a063ae17 754 pathrelse(tb->tb_path);
bd4c625c 755
ee93961b
JM		 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;
bd4c625c 770 }
1da177e4
LT		 771}
772
1da177e4
LT		 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! */
ee93961b 779static int get_empty_nodes(struct tree_balance *tb, int h)
bd4c625c 780{
d68caa95 781 struct buffer_head *new_bh,
ee93961b
JM		 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;
a063ae17 786 struct super_block *sb = tb->tb_sb;
bd4c625c
LT		 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
ee93961b 794 (h) of the balancing analysis.
bd4c625c
LT		 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
ee93961b
JM		 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] -
bd4c625c
LT		 808 1) : 0;
809
810 /* Allocate missing empty blocks. */
d68caa95 811 /* if Sh == 0 then we are getting a new root */
ee93961b 812 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
bd4c625c 813 /* Amount_needed = the amount that we need more than the amount that we have. */
ee93961b
JM		 814 if (amount_needed > number_of_freeblk)
815 amount_needed -= number_of_freeblk;
bd4c625c
LT		 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 */
ee93961b
JM		 820 if (reiserfs_new_form_blocknrs(tb, blocknrs,
821 amount_needed) == NO_DISK_SPACE)
bd4c625c
LT		 822 return NO_DISK_SPACE;
823
824 /* for each blocknumber we just got, get a buffer and stick it on FEB */
ee93961b
JM		 825 for (blocknr = blocknrs, counter = 0;
826 counter < amount_needed; blocknr++, counter++) {
bd4c625c 827
d68caa95 828 RFALSE(!*blocknr,
bd4c625c
LT		 829 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
830
d68caa95
JM		 831 new_bh = sb_getblk(sb, *blocknr);
832 RFALSE(buffer_dirty(new_bh) ||
833 buffer_journaled(new_bh) ||
834 buffer_journal_dirty(new_bh),
febe29d9 835 "PAP-8140: journaled or dirty buffer %b for the new block",
d68caa95 836 new_bh);
bd4c625c
LT		 837
838 /* Put empty buffers into the array. */
a063ae17 839 RFALSE(tb->FEB[tb->cur_blknum],
bd4c625c
LT		 840 "PAP-8141: busy slot for new buffer");
841
d68caa95
JM		 842 set_buffer_journal_new(new_bh);
843 tb->FEB[tb->cur_blknum++] = new_bh;
bd4c625c
LT		 844 }
845
ee93961b
JM		 846 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
847 retval = REPEAT_SEARCH;
1da177e4 848
ee93961b 849 return retval;
bd4c625c 850}
1da177e4
LT		 851
852/* Get free space of the left neighbor, which is stored in the parent
853 * node of the left neighbor. */
bd4c625c 854static int get_lfree(struct tree_balance *tb, int h)
1da177e4 855{
bd4c625c
LT		 856 struct buffer_head *l, *f;
857 int order;
1da177e4 858
9dce07f1
AV		 859 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
860 (l = tb->FL[h]) == NULL)
bd4c625c 861 return 0;
1da177e4 862
bd4c625c
LT		 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 }
1da177e4 869
bd4c625c 870 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
1da177e4
LT		 871}
872
1da177e4
LT		 873/* Get free space of the right neighbor,
874 * which is stored in the parent node of the right neighbor.
875 */
bd4c625c 876static int get_rfree(struct tree_balance *tb, int h)
1da177e4 877{
bd4c625c
LT		 878 struct buffer_head *r, *f;
879 int order;
1da177e4 880
9dce07f1
AV		 881 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
882 (r = tb->FR[h]) == NULL)
bd4c625c 883 return 0;
1da177e4 884
bd4c625c
LT		 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 }
1da177e4 891
bd4c625c 892 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
1da177e4
LT		 893
894}
895
1da177e4 896/* Check whether left neighbor is in memory. */
ee93961b 897static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
bd4c625c 898{
d68caa95 899 struct buffer_head *father, *left;
a063ae17 900 struct super_block *sb = tb->tb_sb;
ee93961b
JM		 901 b_blocknr_t left_neighbor_blocknr;
902 int left_neighbor_position;
bd4c625c 903
a063ae17 904 /* Father of the left neighbor does not exist. */
ee93961b 905 if (!tb->FL[h])
bd4c625c
LT		 906 return 0;
907
908 /* Calculate father of the node to be balanced. */
ee93961b 909 father = PATH_H_PBUFFER(tb->tb_path, h + 1);
bd4c625c 910
d68caa95
JM		 911 RFALSE(!father ||
912 !B_IS_IN_TREE(father) ||
ee93961b 913 !B_IS_IN_TREE(tb->FL[h]) ||
d68caa95 914 !buffer_uptodate(father) ||
ee93961b 915 !buffer_uptodate(tb->FL[h]),
bd4c625c 916 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
ee93961b 917 father, tb->FL[h]);
bd4c625c
LT		 918
919 /* Get position of the pointer to the left neighbor into the left father. */
ee93961b
JM		 920 left_neighbor_position = (father == tb->FL[h]) ?
921 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
bd4c625c 922 /* Get left neighbor block number. */
ee93961b
JM		 923 left_neighbor_blocknr =
924 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
bd4c625c 925 /* Look for the left neighbor in the cache. */
ee93961b 926 if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) {
bd4c625c
LT		 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 }
1da177e4 934
bd4c625c
LT		 935 return 0;
936}
1da177e4
LT		 937
938#define LEFT_PARENTS 'l'
939#define RIGHT_PARENTS 'r'
940
d68caa95 941static void decrement_key(struct cpu_key *key)
1da177e4 942{
bd4c625c 943 // call item specific function for this key
d68caa95 944 item_ops[cpu_key_k_type(key)]->decrement_key(key);
1da177e4
LT		 945}
946
1da177e4
LT		 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 */
a063ae17 955static int get_far_parent(struct tree_balance *tb,
ee93961b 956 int h,
d68caa95
JM		 957 struct buffer_head **pfather,
958 struct buffer_head **pcom_father, char c_lr_par)
1da177e4 959{
d68caa95 960 struct buffer_head *parent;
bd4c625c 961 INITIALIZE_PATH(s_path_to_neighbor_father);
d68caa95 962 struct treepath *path = tb->tb_path;
bd4c625c 963 struct cpu_key s_lr_father_key;
ee93961b
JM		 964 int counter,
965 position = INT_MAX,
966 first_last_position = 0,
967 path_offset = PATH_H_PATH_OFFSET(path, h);
bd4c625c 968
ee93961b
JM		 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. */
bd4c625c 971
ee93961b 972 counter = path_offset;
bd4c625c 973
ee93961b 974 RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET,
bd4c625c
LT		 975 "PAP-8180: invalid path length");
976
ee93961b 977 for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {
bd4c625c
LT		 978 /* Check whether parent of the current buffer in the path is really parent in the tree. */
979 if (!B_IS_IN_TREE
ee93961b 980 (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))
bd4c625c
LT		 981 return REPEAT_SEARCH;
982 /* Check whether position in the parent is correct. */
ee93961b 983 if ((position =
d68caa95 984 PATH_OFFSET_POSITION(path,
ee93961b 985 counter - 1)) >
d68caa95 986 B_NR_ITEMS(parent))
bd4c625c
LT		 987 return REPEAT_SEARCH;
988 /* Check whether parent at the path really points to the child. */
ee93961b
JM		 989 if (B_N_CHILD_NUM(parent, position) !=
990 PATH_OFFSET_PBUFFER(path, counter)->b_blocknr)
bd4c625c
LT		 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)
ee93961b
JM		 994 first_last_position = B_NR_ITEMS(parent);
995 if (position != first_last_position) {
d68caa95
JM		 996 *pcom_father = parent;
997 get_bh(*pcom_father);
998 /*(*pcom_father = parent)->b_count++; */
bd4c625c
LT		 999 break;
1000 }
1da177e4 1001 }
bd4c625c
LT		 1002
1003 /* if we are in the root of the tree, then there is no common father */
ee93961b 1004 if (counter == FIRST_PATH_ELEMENT_OFFSET) {
bd4c625c
LT		 1005 /* Check whether first buffer in the path is the root of the tree. */
1006 if (PATH_OFFSET_PBUFFER
a063ae17 1007 (tb->tb_path,
bd4c625c 1008 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
a063ae17 1009 SB_ROOT_BLOCK(tb->tb_sb)) {
d68caa95 1010 *pfather = *pcom_father = NULL;
bd4c625c
LT		 1011 return CARRY_ON;
1012 }
1013 return REPEAT_SEARCH;
1da177e4 1014 }
1da177e4 1015
d68caa95 1016 RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL,
bd4c625c 1017 "PAP-8185: (%b %z) level too small",
d68caa95 1018 *pcom_father, *pcom_father);
1da177e4 1019
bd4c625c 1020 /* Check whether the common parent is locked. */
1da177e4 1021
d68caa95 1022 if (buffer_locked(*pcom_father)) {
8ebc4232
FW		 1023
1024 /* Release the write lock while the buffer is busy */
1025 reiserfs_write_unlock(tb->tb_sb);
d68caa95 1026 __wait_on_buffer(*pcom_father);
8ebc4232 1027 reiserfs_write_lock(tb->tb_sb);
a063ae17 1028 if (FILESYSTEM_CHANGED_TB(tb)) {
d68caa95 1029 brelse(*pcom_father);
bd4c625c
LT		 1030 return REPEAT_SEARCH;
1031 }
1da177e4 1032 }
1da177e4 1033
bd4c625c
LT		 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. */
1da177e4 1036
bd4c625c
LT		 1037 /* Form key to get parent of the left/right neighbor. */
1038 le_key2cpu_key(&s_lr_father_key,
d68caa95 1039 B_N_PDELIM_KEY(*pcom_father,
bd4c625c 1040 (c_lr_par ==
ee93961b
JM		 1041 LEFT_PARENTS) ? (tb->lkey[h - 1] =
1042 position -
1043 1) : (tb->rkey[h -
bd4c625c 1044 1] =
ee93961b 1045 position)));
1da177e4 1046
bd4c625c
LT		 1047 if (c_lr_par == LEFT_PARENTS)
1048 decrement_key(&s_lr_father_key);
1da177e4 1049
bd4c625c 1050 if (search_by_key
a063ae17 1051 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
ee93961b 1052 h + 1) == IO_ERROR)
bd4c625c
LT		 1053 // path is released
1054 return IO_ERROR;
1da177e4 1055
a063ae17 1056 if (FILESYSTEM_CHANGED_TB(tb)) {
3cd6dbe6 1057 pathrelse(&s_path_to_neighbor_father);
d68caa95 1058 brelse(*pcom_father);
bd4c625c
LT		 1059 return REPEAT_SEARCH;
1060 }
1da177e4 1061
d68caa95 1062 *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1da177e4 1063
ee93961b 1064 RFALSE(B_LEVEL(*pfather) != h + 1,
d68caa95 1065 "PAP-8190: (%b %z) level too small", *pfather, *pfather);
bd4c625c
LT		 1066 RFALSE(s_path_to_neighbor_father.path_length <
1067 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1da177e4 1068
bd4c625c 1069 s_path_to_neighbor_father.path_length--;
3cd6dbe6 1070 pathrelse(&s_path_to_neighbor_father);
bd4c625c 1071 return CARRY_ON;
1da177e4
LT		 1072}
1073
ee93961b
JM		 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].
1da177e4
LT		 1078 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1079 * CARRY_ON - schedule didn't occur while the function worked;
1080 */
ee93961b 1081static int get_parents(struct tree_balance *tb, int h)
1da177e4 1082{
d68caa95 1083 struct treepath *path = tb->tb_path;
ee93961b
JM		 1084 int position,
1085 ret,
1086 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
d68caa95 1087 struct buffer_head *curf, *curcf;
bd4c625c
LT		 1088
1089 /* Current node is the root of the tree or will be root of the tree */
ee93961b 1090 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
bd4c625c
LT		 1091 /* The root can not have parents.
1092 Release nodes which previously were obtained as parents of the current node neighbors. */
ee93961b
JM		 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;
bd4c625c
LT		 1101 return CARRY_ON;
1102 }
1103
ee93961b
JM		 1104 /* Get parent FL[path_offset] of L[path_offset]. */
1105 position = PATH_OFFSET_POSITION(path, path_offset - 1);
1106 if (position) {
bd4c625c 1107 /* Current node is not the first child of its parent. */
ee93961b
JM		 1108 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1109 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
d68caa95
JM		 1110 get_bh(curf);
1111 get_bh(curf);
ee93961b 1112 tb->lkey[h] = position - 1;
bd4c625c 1113 } else {
ee93961b
JM		 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,
d68caa95 1119 &curcf,
bd4c625c 1120 LEFT_PARENTS)) != CARRY_ON)
ee93961b 1121 return ret;
bd4c625c
LT		 1122 }
1123
ee93961b
JM		 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]. */
bd4c625c 1128
d68caa95
JM		 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);
1da177e4 1132
ee93961b 1133/* Get parent FR[h] of R[h]. */
1da177e4 1134
ee93961b
JM		 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,
bd4c625c 1142 RIGHT_PARENTS)) != CARRY_ON)
ee93961b 1143 return ret;
bd4c625c 1144 } else {
ee93961b
JM		 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);
d68caa95
JM		 1148 get_bh(curf);
1149 get_bh(curf);
ee93961b 1150 tb->rkey[h] = position;
bd4c625c 1151 }
1da177e4 1152
ee93961b
JM		 1153 brelse(tb->FR[h]);
1154 /* New initialization of FR[path_offset]. */
1155 tb->FR[h] = curf;
bd4c625c 1156
ee93961b
JM		 1157 brelse(tb->CFR[h]);
1158 /* New initialization of CFR[path_offset]. */
1159 tb->CFR[h] = curcf;
bd4c625c 1160
d68caa95
JM		 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);
bd4c625c
LT		 1164
1165 return CARRY_ON;
1166}
1da177e4
LT		 1167
1168/* it is possible to remove node as result of shiftings to
1169 neighbors even when we insert or paste item. */
bd4c625c
LT		 1170static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1171 struct tree_balance *tb, int h)
1da177e4 1172{
bd4c625c
LT		 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 }
1da177e4 1200 }
bd4c625c
LT		 1201 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1202 return !NO_BALANCING_NEEDED;
1da177e4
LT		 1203}
1204
1da177e4
LT		 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;
0222e657 1213 * Returns: 1 - schedule occurred;
1da177e4
LT		 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 */
bd4c625c 1219static int ip_check_balance(struct tree_balance *tb, int h)
1da177e4 1220{
bd4c625c
LT		 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. */
ee93961b 1227 ret;
bd4c625c
LT		 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 */
0222e657 1248 short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
bd4c625c
LT		 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)
c3a9c210
JM		 1265 reiserfs_panic(tb->tb_sb, "vs-8210",
1266 "S[0] can not be 0");
ee93961b 1267 switch (ret = get_empty_nodes(tb, h)) {
bd4c625c
LT		 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:
ee93961b 1274 return ret;
bd4c625c 1275 default:
c3a9c210
JM		 1276 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1277 "return value of get_empty_nodes");
bd4c625c 1278 }
1da177e4 1279 }
1da177e4 1280
ee93961b
JM		 1281 if ((ret = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */
1282 return ret;
1da177e4 1283
bd4c625c
LT		 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;
1da177e4 1294
bd4c625c 1295 create_virtual_node(tb, h);
1da177e4 1296
0222e657 1297 /*
bd4c625c
LT		 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)
1da177e4 1301 */
bd4c625c 1302 check_left(tb, h, lfree);
1da177e4 1303
bd4c625c
LT		 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;
0222e657 1358 /*
bd4c625c
LT		 1359 * regular overflowing of the node
1360 */
1361
0222e657 1362 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
bd4c625c 1363 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
0222e657 1364 nset, lset, rset, lrset - shows, whether flowing items give better packing
bd4c625c 1365 */
1da177e4 1366#define FLOW 1
bd4c625c 1367#define NO_FLOW 0 /* do not any splitting */
1da177e4 1368
bd4c625c 1369 /* we choose one the following */
1da177e4
LT		 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
bd4c625c
LT		 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 }
1da177e4 1401
bd4c625c
LT		 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 }
1da177e4 1424
bd4c625c
LT		 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 }
1da177e4 1453
bd4c625c
LT		 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 }
1da177e4 1483
bd4c625c
LT		 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 }
1da177e4 1510
bd4c625c
LT		 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 }
1da177e4 1517
bd4c625c
LT		 1518 /* now we know that for better packing shifting in only one
1519 direction either to the left or to the right is required */
1da177e4 1520
bd4c625c
LT		 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 }
1da177e4 1526
bd4c625c
LT		 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 }
1da177e4 1532
bd4c625c
LT		 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 }
1da177e4 1539
bd4c625c
LT		 1540 /* shift to the right independently on whether the right neighbor in cache or not */
1541 SET_PAR_SHIFT_RIGHT;
1542 return CARRY_ON;
1da177e4 1543 }
1da177e4
LT		 1544}
1545
1da177e4
LT		 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;
0222e657 1554 * Returns: 1 - schedule occurred;
1da177e4
LT		 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 */
bd4c625c 1562static int dc_check_balance_internal(struct tree_balance *tb, int h)
1da177e4 1563{
bd4c625c 1564 struct virtual_node *vn = tb->tb_vn;
1da177e4 1565
bd4c625c
LT		 1566 /* Sh is the node whose balance is currently being checked,
1567 and Fh is its father. */
1568 struct buffer_head *Sh, *Fh;
ee93961b 1569 int maxsize, ret;
bd4c625c 1570 int lfree, rfree /* free space in L and R */ ;
1da177e4 1571
bd4c625c
LT		 1572 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1573 Fh = PATH_H_PPARENT(tb->tb_path, h);
1da177e4 1574
bd4c625c 1575 maxsize = MAX_CHILD_SIZE(Sh);
1da177e4
LT		 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); */
bd4c625c 1580 create_virtual_node(tb, h);
1da177e4 1581
bd4c625c
LT		 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
ee93961b
JM		 1594 if ((ret = get_parents(tb, h)) != CARRY_ON)
1595 return ret;
bd4c625c
LT		 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;
1da177e4 1660 }
bd4c625c
LT		 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;
1da177e4
LT		 1694 }
1695
bd4c625c
LT		 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 }
1da177e4 1708
bd4c625c
LT		 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;
1da177e4
LT		 1721 }
1722
bd4c625c
LT		 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);
1da177e4 1726 return CARRY_ON;
1da177e4
LT		 1727}
1728
1da177e4
LT		 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;
0222e657 1737 * Returns: 1 - schedule occurred;
1da177e4
LT		 1738 * 0 - balancing for higher levels needed;
1739 * -1 - no balancing for higher levels needed;
1740 * -2 - no disk space.
1741 */
bd4c625c 1742static int dc_check_balance_leaf(struct tree_balance *tb, int h)
1da177e4 1743{
bd4c625c
LT		 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 */
ee93961b 1752 int maxsize, ret;
bd4c625c
LT		 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);
1da177e4 1760
bd4c625c 1761 levbytes = tb->insert_size[h];
1da177e4 1762
bd4c625c
LT		 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
ee93961b
JM		 1774 if ((ret = get_parents(tb, h)) != CARRY_ON)
1775 return ret;
bd4c625c
LT		 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}
1da177e4
LT		 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.
0222e657 1831 * Returns: 1 - schedule occurred;
1da177e4
LT		 1832 * 0 - balancing for higher levels needed;
1833 * -1 - no balancing for higher levels needed;
1834 * -2 - no disk space.
1835 */
bd4c625c 1836static int dc_check_balance(struct tree_balance *tb, int h)
1da177e4 1837{
bd4c625c
LT		 1838 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1839 "vs-8250: S is not initialized");
1da177e4 1840
bd4c625c
LT		 1841 if (h)
1842 return dc_check_balance_internal(tb, h);
1843 else
1844 return dc_check_balance_leaf(tb, h);
1da177e4
LT		 1845}
1846
1da177e4
LT		 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.
0222e657 1860 * Returns: 1 - schedule occurred;
1da177e4
LT		 1861 * 0 - balancing for higher levels needed;
1862 * -1 - no balancing for higher levels needed;
1863 * -2 - no disk space.
1864 */
bd4c625c
LT		 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)
1da177e4 1871{
bd4c625c 1872 struct virtual_node *vn;
1da177e4 1873
bd4c625c
LT		 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;
1da177e4 1881
bd4c625c
LT		 1882 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1883 "vs-8255: ins_ih can not be 0 in insert mode");
1da177e4 1884
bd4c625c
LT		 1885 if (tb->insert_size[h] > 0)
1886 /* Calculate balance parameters when size of node is increasing. */
1887 return ip_check_balance(tb, h);
1da177e4 1888
bd4c625c
LT		 1889 /* Calculate balance parameters when size of node is decreasing. */
1890 return dc_check_balance(tb, h);
1da177e4
LT		 1891}
1892
bd4c625c 1893/* Check whether parent at the path is the really parent of the current node.*/
ee93961b 1894static int get_direct_parent(struct tree_balance *tb, int h)
bd4c625c 1895{
ad31a4fc 1896 struct buffer_head *bh;
d68caa95 1897 struct treepath *path = tb->tb_path;
ee93961b
JM		 1898 int position,
1899 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
bd4c625c
LT		 1900
1901 /* We are in the root or in the new root. */
ee93961b 1902 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
bd4c625c 1903
ee93961b 1904 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
bd4c625c
LT		 1905 "PAP-8260: invalid offset in the path");
1906
d68caa95 1907 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->
a063ae17 1908 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
bd4c625c 1909 /* Root is not changed. */
ee93961b
JM		 1910 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;
1911 PATH_OFFSET_POSITION(path, path_offset - 1) = 0;
bd4c625c
LT		 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
ee93961b 1918 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))
bd4c625c 1919 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
1da177e4 1920
ee93961b 1921 if ((position =
d68caa95 1922 PATH_OFFSET_POSITION(path,
ee93961b 1923 path_offset - 1)) > B_NR_ITEMS(bh))
bd4c625c 1924 return REPEAT_SEARCH;
1da177e4 1925
ee93961b
JM		 1926 if (B_N_CHILD_NUM(bh, position) !=
1927 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)
bd4c625c
LT		 1928 /* Parent in the path is not parent of the current node in the tree. */
1929 return REPEAT_SEARCH;
1930
ad31a4fc 1931 if (buffer_locked(bh)) {
8ebc4232 1932 reiserfs_write_unlock(tb->tb_sb);
ad31a4fc 1933 __wait_on_buffer(bh);
8ebc4232 1934 reiserfs_write_lock(tb->tb_sb);
a063ae17 1935 if (FILESYSTEM_CHANGED_TB(tb))
bd4c625c 1936 return REPEAT_SEARCH;
1da177e4 1937 }
1da177e4 1938
bd4c625c
LT		 1939 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
1940}
1da177e4 1941
ee93961b
JM		 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.
1da177e4
LT		 1945 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1946 * CARRY_ON - schedule didn't occur while the function worked;
1947 */
ee93961b 1948static int get_neighbors(struct tree_balance *tb, int h)
bd4c625c 1949{
ee93961b
JM		 1950 int child_position,
1951 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
1952 unsigned long son_number;
a063ae17 1953 struct super_block *sb = tb->tb_sb;
ad31a4fc 1954 struct buffer_head *bh;
bd4c625c 1955
ee93961b 1956 PROC_INFO_INC(sb, get_neighbors[h]);
bd4c625c 1957
ee93961b
JM		 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);
bd4c625c 1962
ee93961b
JM		 1963 RFALSE(bh == tb->FL[h] &&
1964 !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
bd4c625c
LT		 1965 "PAP-8270: invalid position in the parent");
1966
ee93961b 1967 child_position =
ad31a4fc 1968 (bh ==
ee93961b
JM		 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);
148d3504 1972 reiserfs_write_unlock(sb);
ee93961b 1973 bh = sb_bread(sb, son_number);
148d3504 1974 reiserfs_write_lock(sb);
ad31a4fc 1975 if (!bh)
bd4c625c 1976 return IO_ERROR;
a063ae17 1977 if (FILESYSTEM_CHANGED_TB(tb)) {
ad31a4fc 1978 brelse(bh);
ee93961b 1979 PROC_INFO_INC(sb, get_neighbors_restart[h]);
bd4c625c
LT		 1980 return REPEAT_SEARCH;
1981 }
1982
ee93961b
JM		 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) !=
ad31a4fc
JM		 1986 bh->b_blocknr, "PAP-8275: invalid parent");
1987 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
ee93961b 1988 RFALSE(!h &&
ad31a4fc
JM		 1989 B_FREE_SPACE(bh) !=
1990 MAX_CHILD_SIZE(bh) -
ee93961b 1991 dc_size(B_N_CHILD(tb->FL[0], child_position)),
bd4c625c
LT		 1992 "PAP-8290: invalid child size of left neighbor");
1993
ee93961b
JM		 1994 brelse(tb->L[h]);
1995 tb->L[h] = bh;
1da177e4 1996 }
bd4c625c 1997
ee93961b
JM		 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);
bd4c625c 2002
ee93961b 2003 RFALSE(bh == tb->FR[h] &&
a063ae17 2004 PATH_OFFSET_POSITION(tb->tb_path,
ee93961b 2005 path_offset) >=
ad31a4fc 2006 B_NR_ITEMS(bh),
bd4c625c
LT		 2007 "PAP-8295: invalid position in the parent");
2008
ee93961b
JM		 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);
148d3504 2012 reiserfs_write_unlock(sb);
ee93961b 2013 bh = sb_bread(sb, son_number);
148d3504 2014 reiserfs_write_lock(sb);
ad31a4fc 2015 if (!bh)
bd4c625c 2016 return IO_ERROR;
a063ae17 2017 if (FILESYSTEM_CHANGED_TB(tb)) {
ad31a4fc 2018 brelse(bh);
ee93961b 2019 PROC_INFO_INC(sb, get_neighbors_restart[h]);
bd4c625c
LT		 2020 return REPEAT_SEARCH;
2021 }
ee93961b
JM		 2022 brelse(tb->R[h]);
2023 tb->R[h] = bh;
bd4c625c 2024
ee93961b 2025 RFALSE(!h
ad31a4fc
JM		 2026 && B_FREE_SPACE(bh) !=
2027 MAX_CHILD_SIZE(bh) -
ee93961b 2028 dc_size(B_N_CHILD(tb->FR[0], child_position)),
bd4c625c 2029 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
ad31a4fc 2030 B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
ee93961b 2031 dc_size(B_N_CHILD(tb->FR[0], child_position)));
bd4c625c 2032
1da177e4 2033 }
bd4c625c 2034 return CARRY_ON;
1da177e4
LT		 2035}
2036
bd4c625c 2037static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
1da177e4 2038{
bd4c625c
LT		 2039 int max_num_of_items;
2040 int max_num_of_entries;
2041 unsigned long blocksize = sb->s_blocksize;
1da177e4
LT		 2042
2043#define MIN_NAME_LEN 1
2044
bd4c625c
LT		 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);
1da177e4 2048
bd4c625c
LT		 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));
1da177e4
LT		 2053}
2054
1da177e4
LT		 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 */
bd4c625c 2058static int get_mem_for_virtual_node(struct tree_balance *tb)
1da177e4 2059{
bd4c625c
LT		 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 */
d739b42b 2070 kfree(tb->vn_buf);
bd4c625c
LT		 2071 /* this is not needed if kfree is atomic */
2072 check_fs = 1;
2073 }
1da177e4 2074
bd4c625c
LT		 2075 /* virtual node requires now more memory */
2076 tb->vn_buf_size = size;
2077
2078 /* get memory for virtual item */
d739b42b 2079 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
bd4c625c
LT		 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);
d739b42b 2086 buf = kmalloc(size, GFP_NOFS);
bd4c625c 2087 if (!buf) {
bd4c625c
LT		 2088 tb->vn_buf_size = 0;
2089 }
2090 tb->vn_buf = buf;
2091 schedule();
2092 return REPEAT_SEARCH;
2093 }
1da177e4 2094
bd4c625c
LT		 2095 tb->vn_buf = buf;
2096 }
1da177e4 2097
bd4c625c
LT		 2098 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2099 return REPEAT_SEARCH;
1da177e4 2100
bd4c625c 2101 return CARRY_ON;
1da177e4
LT		 2102}
2103
1da177e4 2104#ifdef CONFIG_REISERFS_CHECK
a9dd3643 2105static void tb_buffer_sanity_check(struct super_block *sb,
ad31a4fc 2106 struct buffer_head *bh,
bd4c625c 2107 const char *descr, int level)
1da177e4 2108{
ad31a4fc
JM		 2109 if (bh) {
2110 if (atomic_read(&(bh->b_count)) <= 0)
1da177e4 2111
a9dd3643 2112 reiserfs_panic(sb, "jmacd-1", "negative or zero "
c3a9c210 2113 "reference counter for buffer %s[%d] "
ad31a4fc 2114 "(%b)", descr, level, bh);
1da177e4 2115
ad31a4fc 2116 if (!buffer_uptodate(bh))
a9dd3643 2117 reiserfs_panic(sb, "jmacd-2", "buffer is not up "
c3a9c210 2118 "to date %s[%d] (%b)",
ad31a4fc 2119 descr, level, bh);
1da177e4 2120
ad31a4fc 2121 if (!B_IS_IN_TREE(bh))
a9dd3643 2122 reiserfs_panic(sb, "jmacd-3", "buffer is not "
c3a9c210 2123 "in tree %s[%d] (%b)",
ad31a4fc 2124 descr, level, bh);
1da177e4 2125
ad31a4fc 2126 if (bh->b_bdev != sb->s_bdev)
a9dd3643 2127 reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
c3a9c210 2128 "device %s[%d] (%b)",
ad31a4fc 2129 descr, level, bh);
1da177e4 2130
ad31a4fc 2131 if (bh->b_size != sb->s_blocksize)
a9dd3643 2132 reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
c3a9c210 2133 "blocksize %s[%d] (%b)",
ad31a4fc 2134 descr, level, bh);
1da177e4 2135
ad31a4fc 2136 if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
a9dd3643 2137 reiserfs_panic(sb, "jmacd-6", "buffer block "
c3a9c210 2138 "number too high %s[%d] (%b)",
ad31a4fc 2139 descr, level, bh);
bd4c625c
LT		 2140 }
2141}
2142#else
a9dd3643 2143static void tb_buffer_sanity_check(struct super_block *sb,
ad31a4fc 2144 struct buffer_head *bh,
bd4c625c
LT		 2145 const char *descr, int level)
2146{;
2147}
2148#endif
1da177e4 2149
bd4c625c
LT		 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}
1da177e4 2154
a063ae17 2155static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
bd4c625c
LT		 2156{
2157 struct buffer_head *locked;
2158#ifdef CONFIG_REISERFS_CHECK
2159 int repeat_counter = 0;
2160#endif
2161 int i;
1da177e4 2162
bd4c625c 2163 do {
1da177e4 2164
bd4c625c
LT		 2165 locked = NULL;
2166
a063ae17 2167 for (i = tb->tb_path->path_length;
bd4c625c 2168 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
a063ae17 2169 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
bd4c625c
LT		 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
a063ae17
JM		 2174 if (PATH_PLAST_BUFFER(tb->tb_path) ==
2175 PATH_OFFSET_PBUFFER(tb->tb_path, i))
2176 tb_buffer_sanity_check(tb->tb_sb,
bd4c625c 2177 PATH_OFFSET_PBUFFER
a063ae17 2178 (tb->tb_path,
bd4c625c 2179 i), "S",
a063ae17 2180 tb->tb_path->
bd4c625c 2181 path_length - i);
bd4c625c 2182#endif
a063ae17 2183 if (!clear_all_dirty_bits(tb->tb_sb,
bd4c625c 2184 PATH_OFFSET_PBUFFER
a063ae17 2185 (tb->tb_path,
bd4c625c
LT		 2186 i))) {
2187 locked =
a063ae17 2188 PATH_OFFSET_PBUFFER(tb->tb_path,
bd4c625c
LT		 2189 i);
2190 }
2191 }
1da177e4
LT		 2192 }
2193
a063ae17 2194 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
bd4c625c
LT		 2195 i++) {
2196
a063ae17 2197 if (tb->lnum[i]) {
bd4c625c 2198
a063ae17
JM		 2199 if (tb->L[i]) {
2200 tb_buffer_sanity_check(tb->tb_sb,
2201 tb->L[i],
bd4c625c
LT		 2202 "L", i);
2203 if (!clear_all_dirty_bits
a063ae17
JM		 2204 (tb->tb_sb, tb->L[i]))
2205 locked = tb->L[i];
bd4c625c
LT		 2206 }
2207
a063ae17
JM		 2208 if (!locked && tb->FL[i]) {
2209 tb_buffer_sanity_check(tb->tb_sb,
2210 tb->FL[i],
bd4c625c
LT		 2211 "FL", i);
2212 if (!clear_all_dirty_bits
a063ae17
JM		 2213 (tb->tb_sb, tb->FL[i]))
2214 locked = tb->FL[i];
bd4c625c
LT		 2215 }
2216
a063ae17
JM		 2217 if (!locked && tb->CFL[i]) {
2218 tb_buffer_sanity_check(tb->tb_sb,
2219 tb->CFL[i],
bd4c625c
LT		 2220 "CFL", i);
2221 if (!clear_all_dirty_bits
a063ae17
JM		 2222 (tb->tb_sb, tb->CFL[i]))
2223 locked = tb->CFL[i];
bd4c625c
LT		 2224 }
2225
2226 }
2227
a063ae17 2228 if (!locked && (tb->rnum[i])) {
bd4c625c 2229
a063ae17
JM		 2230 if (tb->R[i]) {
2231 tb_buffer_sanity_check(tb->tb_sb,
2232 tb->R[i],
bd4c625c
LT		 2233 "R", i);
2234 if (!clear_all_dirty_bits
a063ae17
JM		 2235 (tb->tb_sb, tb->R[i]))
2236 locked = tb->R[i];
bd4c625c
LT		 2237 }
2238
a063ae17
JM		 2239 if (!locked && tb->FR[i]) {
2240 tb_buffer_sanity_check(tb->tb_sb,
2241 tb->FR[i],
bd4c625c
LT		 2242 "FR", i);
2243 if (!clear_all_dirty_bits
a063ae17
JM		 2244 (tb->tb_sb, tb->FR[i]))
2245 locked = tb->FR[i];
bd4c625c
LT		 2246 }
2247
a063ae17
JM		 2248 if (!locked && tb->CFR[i]) {
2249 tb_buffer_sanity_check(tb->tb_sb,
2250 tb->CFR[i],
bd4c625c
LT		 2251 "CFR", i);
2252 if (!clear_all_dirty_bits
a063ae17
JM		 2253 (tb->tb_sb, tb->CFR[i]))
2254 locked = tb->CFR[i];
bd4c625c
LT		 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++) {
a063ae17 2267 if (tb->FEB[i]) {
bd4c625c 2268 if (!clear_all_dirty_bits
a063ae17
JM		 2269 (tb->tb_sb, tb->FEB[i]))
2270 locked = tb->FEB[i];
bd4c625c 2271 }
1da177e4 2272 }
1da177e4 2273
bd4c625c 2274 if (locked) {
1da177e4 2275#ifdef CONFIG_REISERFS_CHECK
bd4c625c
LT		 2276 repeat_counter++;
2277 if ((repeat_counter % 10000) == 0) {
a063ae17 2278 reiserfs_warning(tb->tb_sb, "reiserfs-8200",
45b03d5e
JM		 2279 "too many iterations waiting "
2280 "for buffer to unlock "
bd4c625c
LT		 2281 "(%b)", locked);
2282
2283 /* Don't loop forever. Try to recover from possible error. */
2284
a063ae17 2285 return (FILESYSTEM_CHANGED_TB(tb)) ?
bd4c625c
LT		 2286 REPEAT_SEARCH : CARRY_ON;
2287 }
1da177e4 2288#endif
8ebc4232 2289 reiserfs_write_unlock(tb->tb_sb);
bd4c625c 2290 __wait_on_buffer(locked);
8ebc4232 2291 reiserfs_write_lock(tb->tb_sb);
a063ae17 2292 if (FILESYSTEM_CHANGED_TB(tb))
bd4c625c 2293 return REPEAT_SEARCH;
bd4c625c 2294 }
1da177e4 2295
bd4c625c 2296 } while (locked);
1da177e4 2297
bd4c625c 2298 return CARRY_ON;
1da177e4
LT		 2299}
2300
1da177e4
LT		 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.
0222e657 2306 *
1da177e4
LT		 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
0222e657 2312 *
1da177e4 2313 * fix is meant in the sense of render unchanging
0222e657 2314 *
1da177e4
LT		 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
a063ae17
JM		 2323 * ins_ih item head of item being inserted
2324 * data inserted item or data to be pasted
1da177e4
LT		 2325 * Returns: 1 - schedule occurred while the function worked;
2326 * 0 - schedule didn't occur while the function worked;
0222e657 2327 * -1 - if no_disk_space
1da177e4
LT		 2328 */
2329
ee93961b 2330int fix_nodes(int op_mode, struct tree_balance *tb,
d68caa95 2331 struct item_head *ins_ih, const void *data)
bd4c625c 2332{
ee93961b
JM		 2333 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2334 int pos_in_item;
1da177e4 2335
bd4c625c
LT		 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;
a063ae17 2340 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
1da177e4 2341
a063ae17 2342 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
bd4c625c 2343
ee93961b 2344 pos_in_item = tb->tb_path->pos_in_item;
bd4c625c 2345
a063ae17 2346 tb->fs_gen = get_generation(tb->tb_sb);
1da177e4 2347
bd4c625c
LT		 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 */
a063ae17
JM		 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))
bd4c625c 2358 return REPEAT_SEARCH;
1da177e4 2359
bd4c625c 2360 /* if it possible in indirect_to_direct conversion */
a063ae17 2361 if (buffer_locked(tbS0)) {
8ebc4232 2362 reiserfs_write_unlock(tb->tb_sb);
a063ae17 2363 __wait_on_buffer(tbS0);
8ebc4232 2364 reiserfs_write_lock(tb->tb_sb);
a063ae17 2365 if (FILESYSTEM_CHANGED_TB(tb))
bd4c625c
LT		 2366 return REPEAT_SEARCH;
2367 }
2368#ifdef CONFIG_REISERFS_CHECK
08f14fc8 2369 if (REISERFS_SB(tb->tb_sb)->cur_tb) {
bd4c625c 2370 print_cur_tb("fix_nodes");
a063ae17 2371 reiserfs_panic(tb->tb_sb, "PAP-8305",
c3a9c210 2372 "there is pending do_balance");
bd4c625c 2373 }
1da177e4 2374
a063ae17
JM		 2375 if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
2376 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
c3a9c210
JM		 2377 "not uptodate at the beginning of fix_nodes "
2378 "or not in tree (mode %c)",
ee93961b 2379 tbS0, tbS0, op_mode);
1da177e4 2380
bd4c625c 2381 /* Check parameters. */
ee93961b 2382 switch (op_mode) {
bd4c625c 2383 case M_INSERT:
ee93961b 2384 if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
a063ae17 2385 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
c3a9c210 2386 "item number %d (in S0 - %d) in case "
ee93961b 2387 "of insert", item_num,
a063ae17 2388 B_NR_ITEMS(tbS0));
bd4c625c
LT		 2389 break;
2390 case M_PASTE:
2391 case M_DELETE:
2392 case M_CUT:
ee93961b 2393 if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
a063ae17
JM		 2394 print_block(tbS0, 0, -1, -1);
2395 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
c3a9c210
JM		 2396 "item number(%d); mode = %c "
2397 "insert_size = %d",
ee93961b 2398 item_num, op_mode,
a063ae17 2399 tb->insert_size[0]);
1da177e4 2400 }
1da177e4 2401 break;
bd4c625c 2402 default:
a063ae17 2403 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
c3a9c210 2404 "of operation");
1da177e4 2405 }
bd4c625c 2406#endif
1da177e4 2407
a063ae17 2408 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
bd4c625c
LT		 2409 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2410 return REPEAT_SEARCH;
1da177e4 2411
ee93961b
JM		 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)
bd4c625c 2416 goto repeat;
1da177e4 2417
ee93961b
JM		 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) {
bd4c625c 2422 /* No balancing for higher levels needed. */
ee93961b
JM		 2423 ret = get_neighbors(tb, h);
2424 if (ret != CARRY_ON)
bd4c625c 2425 goto repeat;
ee93961b
JM		 2426 if (h != MAX_HEIGHT - 1)
2427 tb->insert_size[h + 1] = 0;
bd4c625c
LT		 2428 /* ok, analysis and resource gathering are complete */
2429 break;
2430 }
2431 goto repeat;
2432 }
1da177e4 2433
ee93961b
JM		 2434 ret = get_neighbors(tb, h);
2435 if (ret != CARRY_ON)
bd4c625c 2436 goto repeat;
bd4c625c 2437
a063ae17
JM		 2438 /* No disk space, or schedule occurred and analysis may be
2439 * invalid and needs to be redone. */
ee93961b
JM		 2440 ret = get_empty_nodes(tb, h);
2441 if (ret != CARRY_ON)
a063ae17 2442 goto repeat;
bd4c625c 2443
ee93961b 2444 if (!PATH_H_PBUFFER(tb->tb_path, h)) {
bd4c625c
LT		 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
ee93961b 2448 RFALSE(tb->blknum[h] != 1,
bd4c625c
LT		 2449 "PAP-8350: creating new empty root");
2450
ee93961b
JM		 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]
bd4c625c 2456 which is the root node is split into two nodes,
ee93961b 2457 and a new node (S[h+1]) will be created to
bd4c625c
LT		 2458 become the root node. */
2459
ee93961b 2460 RFALSE(h == MAX_HEIGHT - 1,
bd4c625c
LT		 2461 "PAP-8355: attempt to create too high of a tree");
2462
ee93961b 2463 tb->insert_size[h + 1] =
bd4c625c 2464 (DC_SIZE +
ee93961b 2465 KEY_SIZE) * (tb->blknum[h] - 1) +
bd4c625c 2466 DC_SIZE;
ee93961b
JM		 2467 } else if (h < MAX_HEIGHT - 1)
2468 tb->insert_size[h + 1] = 0;
bd4c625c 2469 } else
ee93961b
JM		 2470 tb->insert_size[h + 1] =
2471 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
1da177e4 2472 }
1da177e4 2473
ee93961b
JM		 2474 ret = wait_tb_buffers_until_unlocked(tb);
2475 if (ret == CARRY_ON) {
a063ae17 2476 if (FILESYSTEM_CHANGED_TB(tb)) {
bd4c625c 2477 wait_tb_buffers_run = 1;
ee93961b 2478 ret = REPEAT_SEARCH;
bd4c625c
LT		 2479 goto repeat;
2480 } else {
2481 return CARRY_ON;
2482 }
1da177e4 2483 } else {
bd4c625c
LT		 2484 wait_tb_buffers_run = 1;
2485 goto repeat;
1da177e4
LT		 2486 }
2487
bd4c625c
LT		 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) {
a063ae17 2499 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
bd4c625c 2500 } else {
a063ae17 2501 pathrelse(tb->tb_path);
bd4c625c
LT		 2502 }
2503 /* brelse all resources collected for balancing */
2504 for (i = 0; i < MAX_HEIGHT; i++) {
2505 if (wait_tb_buffers_run) {
a063ae17
JM		 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->
bd4c625c 2516 CFL[i]);
a063ae17
JM		 2517 reiserfs_restore_prepared_buffer(tb->tb_sb,
2518 tb->
bd4c625c
LT		 2519 CFR[i]);
2520 }
2521
a063ae17
JM		 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;
bd4c625c
LT		 2535 }
2536
2537 if (wait_tb_buffers_run) {
2538 for (i = 0; i < MAX_FEB_SIZE; i++) {
a063ae17 2539 if (tb->FEB[i])
bd4c625c 2540 reiserfs_restore_prepared_buffer
a063ae17 2541 (tb->tb_sb, tb->FEB[i]);
bd4c625c 2542 }
1da177e4 2543 }
ee93961b 2544 return ret;
1da177e4 2545 }
1da177e4
LT		 2546
2547}
2548
a063ae17 2549/* Anatoly will probably forgive me renaming tb to tb. I just
1da177e4 2550 wanted to make lines shorter */
bd4c625c 2551void unfix_nodes(struct tree_balance *tb)
1da177e4 2552{
bd4c625c 2553 int i;
1da177e4 2554
bd4c625c
LT		 2555 /* Release path buffers. */
2556 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
1da177e4 2557
bd4c625c
LT		 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 }
1da177e4 2574
bd4c625c
LT		 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 }
1da177e4 2590
d739b42b 2591 kfree(tb->vn_buf);
1da177e4 2592
bd4c625c 2593}
Clone of davem's net-next-2.6 tree