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