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