blob: 6d0e554daa9d845fd9a608826654f84cc6834f59 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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
Linus Torvalds1da177e2005-04-16 15:20:36 -070037#include <linux/time.h>
38#include <linux/string.h>
39#include <linux/reiserfs_fs.h>
40#include <linux/buffer_head.h>
41
Linus Torvalds1da177e2005-04-16 15:20:36 -070042/* To make any changes in the tree we find a node, that contains item
43 to be changed/deleted or position in the node we insert a new item
44 to. We call this node S. To do balancing we need to decide what we
45 will shift to left/right neighbor, or to a new node, where new item
46 will be etc. To make this analysis simpler we build virtual
47 node. Virtual node is an array of items, that will replace items of
48 node S. (For instance if we are going to delete an item, virtual
49 node does not contain it). Virtual node keeps information about
50 item sizes and types, mergeability of first and last items, sizes
51 of all entries in directory item. We use this array of items when
52 calculating what we can shift to neighbors and how many nodes we
53 have to have if we do not any shiftings, if we shift to left/right
54 neighbor or to both. */
55
Linus Torvalds1da177e2005-04-16 15:20:36 -070056/* taking item number in virtual node, returns number of item, that it has in source buffer */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070057static inline int old_item_num(int new_num, int affected_item_num, int mode)
Linus Torvalds1da177e2005-04-16 15:20:36 -070058{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070059 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
60 return new_num;
Linus Torvalds1da177e2005-04-16 15:20:36 -070061
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070062 if (mode == M_INSERT) {
Linus Torvalds1da177e2005-04-16 15:20:36 -070063
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070064 RFALSE(new_num == 0,
65 "vs-8005: for INSERT mode and item number of inserted item");
Linus Torvalds1da177e2005-04-16 15:20:36 -070066
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070067 return new_num - 1;
68 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070069
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070070 RFALSE(mode != M_DELETE,
71 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
72 mode);
73 /* delete mode */
74 return new_num + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070075}
76
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070077static void create_virtual_node(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -070078{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070079 struct item_head *ih;
80 struct virtual_node *vn = tb->tb_vn;
81 int new_num;
82 struct buffer_head *Sh; /* this comes from tb->S[h] */
Linus Torvalds1da177e2005-04-16 15:20:36 -070083
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070084 Sh = PATH_H_PBUFFER(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -070085
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070086 /* size of changed node */
87 vn->vn_size =
88 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070090 /* for internal nodes array if virtual items is not created */
91 if (h) {
92 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
93 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -070094 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070095
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070096 /* number of items in virtual node */
97 vn->vn_nr_item =
98 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
99 ((vn->vn_mode == M_DELETE) ? 1 : 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700100
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700101 /* 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 /* first item in the node */
107 ih = B_N_PITEM_HEAD(Sh, 0);
108
109 /* define the mergeability for 0-th item (if it is not being deleted) */
110 if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size)
111 && (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 =
119 ((new_num != vn->vn_affected_item_num) ? 0 : 1);
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,
126 vn->vn_mode);
127
128 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
129 vi->vi_ih = ih + j;
130 vi->vi_item = B_I_PITEM(Sh, ih + j);
131 vi->vi_uarea = vn->vn_free_ptr;
132
133 // FIXME: there is no check, that item operation did not
134 // consume too much memory
135 vn->vn_free_ptr +=
136 op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
137 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
138 reiserfs_panic(tb->tb_sb,
139 "vs-8030: create_virtual_node: "
140 "virtual node space consumed");
141
142 if (!is_affected)
143 /* this is not being changed */
144 continue;
145
146 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
147 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
148 vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
149 }
150 }
151
152 /* virtual inserted item is not defined yet */
153 if (vn->vn_mode == M_INSERT) {
154 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
155
156 RFALSE(vn->vn_ins_ih == 0,
157 "vs-8040: item header of inserted item is not specified");
158 vi->vi_item_len = tb->insert_size[0];
159 vi->vi_ih = vn->vn_ins_ih;
160 vi->vi_item = vn->vn_data;
161 vi->vi_uarea = vn->vn_free_ptr;
162
163 op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
164 tb->insert_size[0]);
165 }
166
167 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
168 if (tb->CFR[0]) {
169 struct reiserfs_key *key;
170
171 key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]);
172 if (op_is_left_mergeable(key, Sh->b_size)
173 && (vn->vn_mode != M_DELETE
174 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
175 vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
176 VI_TYPE_RIGHT_MERGEABLE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700177
178#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700179 if (op_is_left_mergeable(key, Sh->b_size) &&
180 !(vn->vn_mode != M_DELETE
181 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
182 /* we delete last item and it could be merged with right neighbor's first item */
183 if (!
184 (B_NR_ITEMS(Sh) == 1
185 && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0))
186 && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) {
187 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
188 print_block(Sh, 0, -1, -1);
189 reiserfs_panic(tb->tb_sb,
190 "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c",
191 key, vn->vn_affected_item_num,
192 vn->vn_mode, M_DELETE);
Vladimir V. Savelievcd02b962006-03-25 03:07:15 -0800193 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700194 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700195#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700197 }
198}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199
200/* using virtual node check, how many items can be shifted to left
201 neighbor */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700202static void check_left(struct tree_balance *tb, int h, int cur_free)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700204 int i;
205 struct virtual_node *vn = tb->tb_vn;
206 struct virtual_item *vi;
207 int d_size, ih_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700209 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700211 /* internal level */
212 if (h > 0) {
213 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
214 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700216
217 /* leaf level */
218
219 if (!cur_free || !vn->vn_nr_item) {
220 /* no free space or nothing to move */
221 tb->lnum[h] = 0;
222 tb->lbytes = -1;
223 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700225
226 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
227 "vs-8055: parent does not exist or invalid");
228
229 vi = vn->vn_vi;
230 if ((unsigned int)cur_free >=
231 (vn->vn_size -
232 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
233 /* all contents of S[0] fits into L[0] */
234
235 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
236 "vs-8055: invalid mode or balance condition failed");
237
238 tb->lnum[0] = vn->vn_nr_item;
239 tb->lbytes = -1;
240 return;
241 }
242
243 d_size = 0, ih_size = IH_SIZE;
244
245 /* first item may be merge with last item in left neighbor */
246 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
247 d_size = -((int)IH_SIZE), ih_size = 0;
248
249 tb->lnum[0] = 0;
250 for (i = 0; i < vn->vn_nr_item;
251 i++, ih_size = IH_SIZE, d_size = 0, vi++) {
252 d_size += vi->vi_item_len;
253 if (cur_free >= d_size) {
254 /* the item can be shifted entirely */
255 cur_free -= d_size;
256 tb->lnum[0]++;
257 continue;
258 }
259
260 /* the item cannot be shifted entirely, try to split it */
261 /* check whether L[0] can hold ih and at least one byte of the item body */
262 if (cur_free <= ih_size) {
263 /* cannot shift even a part of the current item */
264 tb->lbytes = -1;
265 return;
266 }
267 cur_free -= ih_size;
268
269 tb->lbytes = op_check_left(vi, cur_free, 0, 0);
270 if (tb->lbytes != -1)
271 /* count partially shifted item */
272 tb->lnum[0]++;
273
274 break;
275 }
276
277 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278}
279
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280/* using virtual node check, how many items can be shifted to right
281 neighbor */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700282static void check_right(struct tree_balance *tb, int h, int cur_free)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700284 int i;
285 struct virtual_node *vn = tb->tb_vn;
286 struct virtual_item *vi;
287 int d_size, ih_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700289 RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700290
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700291 /* internal level */
292 if (h > 0) {
293 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
294 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700297 /* leaf level */
298
299 if (!cur_free || !vn->vn_nr_item) {
300 /* no free space */
301 tb->rnum[h] = 0;
302 tb->rbytes = -1;
303 return;
304 }
305
306 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
307 "vs-8075: parent does not exist or invalid");
308
309 vi = vn->vn_vi + vn->vn_nr_item - 1;
310 if ((unsigned int)cur_free >=
311 (vn->vn_size -
312 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
313 /* all contents of S[0] fits into R[0] */
314
315 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
316 "vs-8080: invalid mode or balance condition failed");
317
318 tb->rnum[h] = vn->vn_nr_item;
319 tb->rbytes = -1;
320 return;
321 }
322
323 d_size = 0, ih_size = IH_SIZE;
324
325 /* last item may be merge with first item in right neighbor */
326 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
327 d_size = -(int)IH_SIZE, ih_size = 0;
328
329 tb->rnum[0] = 0;
330 for (i = vn->vn_nr_item - 1; i >= 0;
331 i--, d_size = 0, ih_size = IH_SIZE, vi--) {
332 d_size += vi->vi_item_len;
333 if (cur_free >= d_size) {
334 /* the item can be shifted entirely */
335 cur_free -= d_size;
336 tb->rnum[0]++;
337 continue;
338 }
339
340 /* check whether R[0] can hold ih and at least one byte of the item body */
341 if (cur_free <= ih_size) { /* cannot shift even a part of the current item */
342 tb->rbytes = -1;
343 return;
344 }
345
346 /* R[0] can hold the header of the item and at least one byte of its body */
347 cur_free -= ih_size; /* cur_free is still > 0 */
348
349 tb->rbytes = op_check_right(vi, cur_free);
350 if (tb->rbytes != -1)
351 /* count partially shifted item */
352 tb->rnum[0]++;
353
354 break;
355 }
356
357 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358}
359
Linus Torvalds1da177e2005-04-16 15:20:36 -0700360/*
361 * from - number of items, which are shifted to left neighbor entirely
362 * to - number of item, which are shifted to right neighbor entirely
363 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
364 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700365static int get_num_ver(int mode, struct tree_balance *tb, int h,
366 int from, int from_bytes,
367 int to, int to_bytes, short *snum012, int flow)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700369 int i;
370 int cur_free;
371 // int bytes;
372 int units;
373 struct virtual_node *vn = tb->tb_vn;
374 // struct virtual_item * vi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700375
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700376 int total_node_size, max_node_size, current_item_size;
377 int needed_nodes;
378 int start_item, /* position of item we start filling node from */
379 end_item, /* position of item we finish filling node by */
380 start_bytes, /* number of first bytes (entries for directory) of start_item-th item
381 we do not include into node that is being filled */
382 end_bytes; /* number of last bytes (entries for directory) of end_item-th item
383 we do node include into node that is being filled */
384 int split_item_positions[2]; /* these are positions in virtual item of
385 items, that are split between S[0] and
386 S1new and S1new and S2new */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700388 split_item_positions[0] = -1;
389 split_item_positions[1] = -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700391 /* We only create additional nodes if we are in insert or paste mode
392 or we are in replace mode at the internal level. If h is 0 and
393 the mode is M_REPLACE then in fix_nodes we change the mode to
394 paste or insert before we get here in the code. */
395 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
396 "vs-8100: insert_size < 0 in overflow");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700397
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700398 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700400 /* snum012 [0-2] - number of items, that lay
401 to S[0], first new node and second new node */
402 snum012[3] = -1; /* s1bytes */
403 snum012[4] = -1; /* s2bytes */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700404
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700405 /* internal level */
406 if (h > 0) {
407 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
408 if (i == max_node_size)
409 return 1;
410 return (i / max_node_size + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 }
412
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700413 /* leaf level */
414 needed_nodes = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 total_node_size = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700416 cur_free = max_node_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700418 // start from 'from'-th item
419 start_item = from;
420 // skip its first 'start_bytes' units
421 start_bytes = ((from_bytes != -1) ? from_bytes : 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700422
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700423 // last included item is the 'end_item'-th one
424 end_item = vn->vn_nr_item - to - 1;
425 // do not count last 'end_bytes' units of 'end_item'-th item
426 end_bytes = (to_bytes != -1) ? to_bytes : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700428 /* go through all item beginning from the start_item-th item and ending by
429 the end_item-th item. Do not count first 'start_bytes' units of
430 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700432 for (i = start_item; i <= end_item; i++) {
433 struct virtual_item *vi = vn->vn_vi + i;
434 int skip_from_end = ((i == end_item) ? end_bytes : 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700435
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700436 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
437
438 /* get size of current item */
439 current_item_size = vi->vi_item_len;
440
441 /* do not take in calculation head part (from_bytes) of from-th item */
442 current_item_size -=
443 op_part_size(vi, 0 /*from start */ , start_bytes);
444
445 /* do not take in calculation tail part of last item */
446 current_item_size -=
447 op_part_size(vi, 1 /*from end */ , skip_from_end);
448
449 /* if item fits into current node entierly */
450 if (total_node_size + current_item_size <= max_node_size) {
451 snum012[needed_nodes - 1]++;
452 total_node_size += current_item_size;
453 start_bytes = 0;
454 continue;
455 }
456
457 if (current_item_size > max_node_size) {
458 /* virtual item length is longer, than max size of item in
459 a node. It is impossible for direct item */
460 RFALSE(is_direct_le_ih(vi->vi_ih),
461 "vs-8110: "
462 "direct item length is %d. It can not be longer than %d",
463 current_item_size, max_node_size);
464 /* we will try to split it */
465 flow = 1;
466 }
467
468 if (!flow) {
469 /* as we do not split items, take new node and continue */
470 needed_nodes++;
471 i--;
472 total_node_size = 0;
473 continue;
474 }
475 // calculate number of item units which fit into node being
476 // filled
477 {
478 int free_space;
479
480 free_space = max_node_size - total_node_size - IH_SIZE;
481 units =
482 op_check_left(vi, free_space, start_bytes,
483 skip_from_end);
484 if (units == -1) {
485 /* nothing fits into current node, take new node and continue */
486 needed_nodes++, i--, total_node_size = 0;
487 continue;
488 }
489 }
490
491 /* something fits into the current node */
492 //if (snum012[3] != -1 || needed_nodes != 1)
493 // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
494 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
495 start_bytes += units;
496 snum012[needed_nodes - 1 + 3] = units;
497
498 if (needed_nodes > 2)
499 reiserfs_warning(tb->tb_sb, "vs-8111: get_num_ver: "
500 "split_item_position is out of boundary");
501 snum012[needed_nodes - 1]++;
502 split_item_positions[needed_nodes - 1] = i;
503 needed_nodes++;
504 /* continue from the same item with start_bytes != -1 */
505 start_item = i;
506 i--;
507 total_node_size = 0;
508 }
509
510 // sum012[4] (if it is not -1) contains number of units of which
511 // are to be in S1new, snum012[3] - to be in S0. They are supposed
512 // to be S1bytes and S2bytes correspondingly, so recalculate
513 if (snum012[4] > 0) {
514 int split_item_num;
515 int bytes_to_r, bytes_to_l;
516 int bytes_to_S1new;
517
518 split_item_num = split_item_positions[1];
519 bytes_to_l =
520 ((from == split_item_num
521 && from_bytes != -1) ? from_bytes : 0);
522 bytes_to_r =
523 ((end_item == split_item_num
524 && end_bytes != -1) ? end_bytes : 0);
525 bytes_to_S1new =
526 ((split_item_positions[0] ==
527 split_item_positions[1]) ? snum012[3] : 0);
528
529 // s2bytes
530 snum012[4] =
531 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
532 bytes_to_r - bytes_to_l - bytes_to_S1new;
533
534 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
535 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
536 reiserfs_warning(tb->tb_sb, "vs-8115: get_num_ver: not "
537 "directory or indirect item");
538 }
539
540 /* now we know S2bytes, calculate S1bytes */
541 if (snum012[3] > 0) {
542 int split_item_num;
543 int bytes_to_r, bytes_to_l;
544 int bytes_to_S2new;
545
546 split_item_num = split_item_positions[0];
547 bytes_to_l =
548 ((from == split_item_num
549 && from_bytes != -1) ? from_bytes : 0);
550 bytes_to_r =
551 ((end_item == split_item_num
552 && end_bytes != -1) ? end_bytes : 0);
553 bytes_to_S2new =
554 ((split_item_positions[0] == split_item_positions[1]
555 && snum012[4] != -1) ? snum012[4] : 0);
556
557 // s1bytes
558 snum012[3] =
559 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
560 bytes_to_r - bytes_to_l - bytes_to_S2new;
561 }
562
563 return needed_nodes;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564}
565
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700567extern struct tree_balance *cur_tb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568#endif
569
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570/* Set parameters for balancing.
571 * Performs write of results of analysis of balancing into structure tb,
572 * where it will later be used by the functions that actually do the balancing.
573 * Parameters:
574 * tb tree_balance structure;
575 * h current level of the node;
576 * lnum number of items from S[h] that must be shifted to L[h];
577 * rnum number of items from S[h] that must be shifted to R[h];
578 * blk_num number of blocks that S[h] will be splitted into;
579 * s012 number of items that fall into splitted nodes.
580 * lbytes number of bytes which flow to the left neighbor from the item that is not
581 * not shifted entirely
582 * rbytes number of bytes which flow to the right neighbor from the item that is not
583 * not shifted entirely
584 * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array)
585 */
586
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700587static void set_parameters(struct tree_balance *tb, int h, int lnum,
588 int rnum, int blk_num, short *s012, int lb, int rb)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589{
590
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700591 tb->lnum[h] = lnum;
592 tb->rnum[h] = rnum;
593 tb->blknum[h] = blk_num;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700594
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700595 if (h == 0) { /* only for leaf level */
596 if (s012 != NULL) {
597 tb->s0num = *s012++,
598 tb->s1num = *s012++, tb->s2num = *s012++;
599 tb->s1bytes = *s012++;
600 tb->s2bytes = *s012;
601 }
602 tb->lbytes = lb;
603 tb->rbytes = rb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700604 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700605 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
606 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700607
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700608 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
609 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700610}
611
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612/* check, does node disappear if we shift tb->lnum[0] items to left
613 neighbor and tb->rnum[0] to the right one. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700614static int is_leaf_removable(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700615{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700616 struct virtual_node *vn = tb->tb_vn;
617 int to_left, to_right;
618 int size;
619 int remain_items;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700620
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700621 /* number of items, that will be shifted to left (right) neighbor
622 entirely */
623 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
624 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
625 remain_items = vn->vn_nr_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700627 /* how many items remain in S[0] after shiftings to neighbors */
628 remain_items -= (to_left + to_right);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700630 if (remain_items < 1) {
631 /* all content of node can be shifted to neighbors */
632 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
633 NULL, -1, -1);
634 return 1;
635 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700637 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
638 /* S[0] is not removable */
639 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700641 /* check, whether we can divide 1 remaining item between neighbors */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700642
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700643 /* get size of remaining item (in item units) */
644 size = op_unit_num(&(vn->vn_vi[to_left]));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700646 if (tb->lbytes + tb->rbytes >= size) {
647 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
648 tb->lbytes, -1);
649 return 1;
650 }
651
652 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653}
654
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655/* check whether L, S, R can be joined in one node */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700656static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700658 struct virtual_node *vn = tb->tb_vn;
659 int ih_size;
660 struct buffer_head *S0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700662 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700664 ih_size = 0;
665 if (vn->vn_nr_item) {
666 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
667 ih_size += IH_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700668
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700669 if (vn->vn_vi[vn->vn_nr_item - 1].
670 vi_type & VI_TYPE_RIGHT_MERGEABLE)
671 ih_size += IH_SIZE;
672 } else {
673 /* there was only one item and it will be deleted */
674 struct item_head *ih;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700676 RFALSE(B_NR_ITEMS(S0) != 1,
677 "vs-8125: item number must be 1: it is %d",
678 B_NR_ITEMS(S0));
679
680 ih = B_N_PITEM_HEAD(S0, 0);
681 if (tb->CFR[0]
682 && !comp_short_le_keys(&(ih->ih_key),
683 B_N_PDELIM_KEY(tb->CFR[0],
684 tb->rkey[0])))
685 if (is_direntry_le_ih(ih)) {
686 /* Directory must be in correct state here: that is
687 somewhere at the left side should exist first directory
688 item. But the item being deleted can not be that first
689 one because its right neighbor is item of the same
690 directory. (But first item always gets deleted in last
691 turn). So, neighbors of deleted item can be merged, so
692 we can save ih_size */
693 ih_size = IH_SIZE;
694
695 /* we might check that left neighbor exists and is of the
696 same directory */
697 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
698 "vs-8130: first directory item can not be removed until directory is not empty");
699 }
700
701 }
702
703 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
704 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
705 PROC_INFO_INC(tb->tb_sb, leaves_removable);
706 return 1;
707 }
708 return 0;
709
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710}
711
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712/* when we do not split item, lnum and rnum are numbers of entire items */
713#define SET_PAR_SHIFT_LEFT \
714if (h)\
715{\
716 int to_l;\
717 \
718 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
719 (MAX_NR_KEY(Sh) + 1 - lpar);\
720 \
721 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
722}\
723else \
724{\
725 if (lset==LEFT_SHIFT_FLOW)\
726 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
727 tb->lbytes, -1);\
728 else\
729 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
730 -1, -1);\
731}
732
Linus Torvalds1da177e2005-04-16 15:20:36 -0700733#define SET_PAR_SHIFT_RIGHT \
734if (h)\
735{\
736 int to_r;\
737 \
738 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
739 \
740 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
741}\
742else \
743{\
744 if (rset==RIGHT_SHIFT_FLOW)\
745 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
746 -1, tb->rbytes);\
747 else\
748 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
749 -1, -1);\
750}
751
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700752static void free_buffers_in_tb(struct tree_balance *p_s_tb)
753{
754 int n_counter;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700756 decrement_counters_in_path(p_s_tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700758 for (n_counter = 0; n_counter < MAX_HEIGHT; n_counter++) {
759 decrement_bcount(p_s_tb->L[n_counter]);
760 p_s_tb->L[n_counter] = NULL;
761 decrement_bcount(p_s_tb->R[n_counter]);
762 p_s_tb->R[n_counter] = NULL;
763 decrement_bcount(p_s_tb->FL[n_counter]);
764 p_s_tb->FL[n_counter] = NULL;
765 decrement_bcount(p_s_tb->FR[n_counter]);
766 p_s_tb->FR[n_counter] = NULL;
767 decrement_bcount(p_s_tb->CFL[n_counter]);
768 p_s_tb->CFL[n_counter] = NULL;
769 decrement_bcount(p_s_tb->CFR[n_counter]);
770 p_s_tb->CFR[n_counter] = NULL;
771 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700772}
773
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774/* Get new buffers for storing new nodes that are created while balancing.
775 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
776 * CARRY_ON - schedule didn't occur while the function worked;
777 * NO_DISK_SPACE - no disk space.
778 */
779/* The function is NOT SCHEDULE-SAFE! */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700780static int get_empty_nodes(struct tree_balance *p_s_tb, int n_h)
781{
782 struct buffer_head *p_s_new_bh,
783 *p_s_Sh = PATH_H_PBUFFER(p_s_tb->tb_path, n_h);
784 b_blocknr_t *p_n_blocknr, a_n_blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
785 int n_counter, n_number_of_freeblk, n_amount_needed, /* number of needed empty blocks */
786 n_retval = CARRY_ON;
787 struct super_block *p_s_sb = p_s_tb->tb_sb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700788
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700789 /* number_of_freeblk is the number of empty blocks which have been
790 acquired for use by the balancing algorithm minus the number of
791 empty blocks used in the previous levels of the analysis,
792 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
793 after empty blocks are acquired, and the balancing analysis is
794 then restarted, amount_needed is the number needed by this level
795 (n_h) of the balancing analysis.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700797 Note that for systems with many processes writing, it would be
798 more layout optimal to calculate the total number needed by all
799 levels and then to run reiserfs_new_blocks to get all of them at once. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700800
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700801 /* Initiate number_of_freeblk to the amount acquired prior to the restart of
802 the analysis or 0 if not restarted, then subtract the amount needed
803 by all of the levels of the tree below n_h. */
804 /* blknum includes S[n_h], so we subtract 1 in this calculation */
805 for (n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum;
806 n_counter < n_h; n_counter++)
807 n_number_of_freeblk -=
808 (p_s_tb->blknum[n_counter]) ? (p_s_tb->blknum[n_counter] -
809 1) : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700810
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700811 /* Allocate missing empty blocks. */
812 /* if p_s_Sh == 0 then we are getting a new root */
813 n_amount_needed = (p_s_Sh) ? (p_s_tb->blknum[n_h] - 1) : 1;
814 /* Amount_needed = the amount that we need more than the amount that we have. */
815 if (n_amount_needed > n_number_of_freeblk)
816 n_amount_needed -= n_number_of_freeblk;
817 else /* If we have enough already then there is nothing to do. */
818 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700820 /* No need to check quota - is not allocated for blocks used for formatted nodes */
821 if (reiserfs_new_form_blocknrs(p_s_tb, a_n_blocknrs,
822 n_amount_needed) == NO_DISK_SPACE)
823 return NO_DISK_SPACE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700825 /* for each blocknumber we just got, get a buffer and stick it on FEB */
826 for (p_n_blocknr = a_n_blocknrs, n_counter = 0;
827 n_counter < n_amount_needed; p_n_blocknr++, n_counter++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700828
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700829 RFALSE(!*p_n_blocknr,
830 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700832 p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr);
833 RFALSE(buffer_dirty(p_s_new_bh) ||
834 buffer_journaled(p_s_new_bh) ||
835 buffer_journal_dirty(p_s_new_bh),
836 "PAP-8140: journlaled or dirty buffer %b for the new block",
837 p_s_new_bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700839 /* Put empty buffers into the array. */
840 RFALSE(p_s_tb->FEB[p_s_tb->cur_blknum],
841 "PAP-8141: busy slot for new buffer");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700842
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700843 set_buffer_journal_new(p_s_new_bh);
844 p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
845 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700847 if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(p_s_tb))
848 n_retval = REPEAT_SEARCH;
849
850 return n_retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851}
852
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853/* Get free space of the left neighbor, which is stored in the parent
854 * node of the left neighbor. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700855static int get_lfree(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700856{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700857 struct buffer_head *l, *f;
858 int order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700860 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0)
861 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700862
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700863 if (f == l)
864 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
865 else {
866 order = B_NR_ITEMS(l);
867 f = l;
868 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700869
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700870 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871}
872
Linus Torvalds1da177e2005-04-16 15:20:36 -0700873/* Get free space of the right neighbor,
874 * which is stored in the parent node of the right neighbor.
875 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700876static int get_rfree(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700877{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700878 struct buffer_head *r, *f;
879 int order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700880
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700881 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == 0 || (r = tb->FR[h]) == 0)
882 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700883
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700884 if (f == r)
885 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
886 else {
887 order = 0;
888 f = r;
889 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700890
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700891 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892
893}
894
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895/* Check whether left neighbor is in memory. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700896static int is_left_neighbor_in_cache(struct tree_balance *p_s_tb, int n_h)
897{
898 struct buffer_head *p_s_father, *left;
899 struct super_block *p_s_sb = p_s_tb->tb_sb;
900 b_blocknr_t n_left_neighbor_blocknr;
901 int n_left_neighbor_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700903 if (!p_s_tb->FL[n_h]) /* Father of the left neighbor does not exist. */
904 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700906 /* Calculate father of the node to be balanced. */
907 p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700908
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700909 RFALSE(!p_s_father ||
910 !B_IS_IN_TREE(p_s_father) ||
911 !B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
912 !buffer_uptodate(p_s_father) ||
913 !buffer_uptodate(p_s_tb->FL[n_h]),
914 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
915 p_s_father, p_s_tb->FL[n_h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700916
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700917 /* Get position of the pointer to the left neighbor into the left father. */
918 n_left_neighbor_position = (p_s_father == p_s_tb->FL[n_h]) ?
919 p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->FL[n_h]);
920 /* Get left neighbor block number. */
921 n_left_neighbor_blocknr =
922 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
923 /* Look for the left neighbor in the cache. */
924 if ((left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700925
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700926 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
927 "vs-8170: left neighbor (%b %z) is not in the tree",
928 left, left);
929 put_bh(left);
930 return 1;
931 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700932
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700933 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700934}
935
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936#define LEFT_PARENTS 'l'
937#define RIGHT_PARENTS 'r'
938
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700939static void decrement_key(struct cpu_key *p_s_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700941 // call item specific function for this key
942 item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700943}
944
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945/* Calculate far left/right parent of the left/right neighbor of the current node, that
946 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
947 * Calculate left/right common parent of the current node and L[h]/R[h].
948 * Calculate left/right delimiting key position.
949 * Returns: PATH_INCORRECT - path in the tree is not correct;
950 SCHEDULE_OCCURRED - schedule occurred while the function worked;
951 * CARRY_ON - schedule didn't occur while the function worked;
952 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700953static int get_far_parent(struct tree_balance *p_s_tb,
954 int n_h,
955 struct buffer_head **pp_s_father,
956 struct buffer_head **pp_s_com_father, char c_lr_par)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700957{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700958 struct buffer_head *p_s_parent;
959 INITIALIZE_PATH(s_path_to_neighbor_father);
960 struct path *p_s_path = p_s_tb->tb_path;
961 struct cpu_key s_lr_father_key;
962 int n_counter,
963 n_position = INT_MAX,
964 n_first_last_position = 0,
965 n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700967 /* Starting from F[n_h] go upwards in the tree, and look for the common
968 ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700969
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700970 n_counter = n_path_offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700971
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700972 RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET,
973 "PAP-8180: invalid path length");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700974
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700975 for (; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--) {
976 /* Check whether parent of the current buffer in the path is really parent in the tree. */
977 if (!B_IS_IN_TREE
978 (p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)))
979 return REPEAT_SEARCH;
980 /* Check whether position in the parent is correct. */
981 if ((n_position =
982 PATH_OFFSET_POSITION(p_s_path,
983 n_counter - 1)) >
984 B_NR_ITEMS(p_s_parent))
985 return REPEAT_SEARCH;
986 /* Check whether parent at the path really points to the child. */
987 if (B_N_CHILD_NUM(p_s_parent, n_position) !=
988 PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr)
989 return REPEAT_SEARCH;
990 /* Return delimiting key if position in the parent is not equal to first/last one. */
991 if (c_lr_par == RIGHT_PARENTS)
992 n_first_last_position = B_NR_ITEMS(p_s_parent);
993 if (n_position != n_first_last_position) {
994 *pp_s_com_father = p_s_parent;
995 get_bh(*pp_s_com_father);
996 /*(*pp_s_com_father = p_s_parent)->b_count++; */
997 break;
998 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700999 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001000
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001001 /* if we are in the root of the tree, then there is no common father */
1002 if (n_counter == FIRST_PATH_ELEMENT_OFFSET) {
1003 /* Check whether first buffer in the path is the root of the tree. */
1004 if (PATH_OFFSET_PBUFFER
1005 (p_s_tb->tb_path,
1006 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1007 SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
1008 *pp_s_father = *pp_s_com_father = NULL;
1009 return CARRY_ON;
1010 }
1011 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001012 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001013
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001014 RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
1015 "PAP-8185: (%b %z) level too small",
1016 *pp_s_com_father, *pp_s_com_father);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001017
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001018 /* Check whether the common parent is locked. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001019
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001020 if (buffer_locked(*pp_s_com_father)) {
1021 __wait_on_buffer(*pp_s_com_father);
1022 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1023 decrement_bcount(*pp_s_com_father);
1024 return REPEAT_SEARCH;
1025 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001026 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001027
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001028 /* So, we got common parent of the current node and its left/right neighbor.
1029 Now we are geting the parent of the left/right neighbor. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001030
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001031 /* Form key to get parent of the left/right neighbor. */
1032 le_key2cpu_key(&s_lr_father_key,
1033 B_N_PDELIM_KEY(*pp_s_com_father,
1034 (c_lr_par ==
1035 LEFT_PARENTS) ? (p_s_tb->lkey[n_h - 1] =
1036 n_position -
1037 1) : (p_s_tb->rkey[n_h -
1038 1] =
1039 n_position)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001040
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001041 if (c_lr_par == LEFT_PARENTS)
1042 decrement_key(&s_lr_father_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001044 if (search_by_key
1045 (p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1046 n_h + 1) == IO_ERROR)
1047 // path is released
1048 return IO_ERROR;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001049
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001050 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1051 decrement_counters_in_path(&s_path_to_neighbor_father);
1052 decrement_bcount(*pp_s_com_father);
1053 return REPEAT_SEARCH;
1054 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001055
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001056 *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1057
1058 RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
1059 "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
1060 RFALSE(s_path_to_neighbor_father.path_length <
1061 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1062
1063 s_path_to_neighbor_father.path_length--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001064 decrement_counters_in_path(&s_path_to_neighbor_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001065 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066}
1067
Linus Torvalds1da177e2005-04-16 15:20:36 -07001068/* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
1069 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
1070 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
1071 * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
1072 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1073 * CARRY_ON - schedule didn't occur while the function worked;
1074 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001075static int get_parents(struct tree_balance *p_s_tb, int n_h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001076{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001077 struct path *p_s_path = p_s_tb->tb_path;
1078 int n_position,
1079 n_ret_value,
1080 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1081 struct buffer_head *p_s_curf, *p_s_curcf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001082
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001083 /* Current node is the root of the tree or will be root of the tree */
1084 if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1085 /* The root can not have parents.
1086 Release nodes which previously were obtained as parents of the current node neighbors. */
1087 decrement_bcount(p_s_tb->FL[n_h]);
1088 decrement_bcount(p_s_tb->CFL[n_h]);
1089 decrement_bcount(p_s_tb->FR[n_h]);
1090 decrement_bcount(p_s_tb->CFR[n_h]);
1091 p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] =
1092 p_s_tb->CFR[n_h] = NULL;
1093 return CARRY_ON;
1094 }
1095
1096 /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1097 if ((n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1))) {
1098 /* Current node is not the first child of its parent. */
1099 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1100 p_s_curf = p_s_curcf =
1101 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1102 get_bh(p_s_curf);
1103 get_bh(p_s_curf);
1104 p_s_tb->lkey[n_h] = n_position - 1;
1105 } else {
1106 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1107 Calculate current common parent of L[n_path_offset] and the current node. Note that
1108 CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1109 Calculate lkey[n_path_offset]. */
1110 if ((n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
1111 &p_s_curcf,
1112 LEFT_PARENTS)) != CARRY_ON)
1113 return n_ret_value;
1114 }
1115
Linus Torvalds1da177e2005-04-16 15:20:36 -07001116 decrement_bcount(p_s_tb->FL[n_h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001117 p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001118 decrement_bcount(p_s_tb->CFL[n_h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001119 p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001120
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001121 RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1122 (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1123 "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001124
1125/* Get parent FR[n_h] of R[n_h]. */
1126
1127/* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001128 if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001129/* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1130 Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1131 not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001132 if ((n_ret_value =
1133 get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf,
1134 RIGHT_PARENTS)) != CARRY_ON)
1135 return n_ret_value;
1136 } else {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137/* Current node is not the last child of its parent F[n_h]. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001138 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1139 p_s_curf = p_s_curcf =
1140 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1141 get_bh(p_s_curf);
1142 get_bh(p_s_curf);
1143 p_s_tb->rkey[n_h] = n_position;
1144 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001145
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001146 decrement_bcount(p_s_tb->FR[n_h]);
1147 p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001149 decrement_bcount(p_s_tb->CFR[n_h]);
1150 p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001151
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001152 RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1153 (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1154 "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
1155
1156 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001157}
1158
Linus Torvalds1da177e2005-04-16 15:20:36 -07001159/* it is possible to remove node as result of shiftings to
1160 neighbors even when we insert or paste item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001161static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1162 struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001164 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1165 int levbytes = tb->insert_size[h];
1166 struct item_head *ih;
1167 struct reiserfs_key *r_key = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001168
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001169 ih = B_N_PITEM_HEAD(Sh, 0);
1170 if (tb->CFR[h])
1171 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
1172
1173 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1174 /* shifting may merge items which might save space */
1175 -
1176 ((!h
1177 && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1178 -
1179 ((!h && r_key
1180 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1181 + ((h) ? KEY_SIZE : 0)) {
1182 /* node can not be removed */
1183 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1184 if (!h)
1185 tb->s0num =
1186 B_NR_ITEMS(Sh) +
1187 ((mode == M_INSERT) ? 1 : 0);
1188 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1189 return NO_BALANCING_NEEDED;
1190 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001191 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001192 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1193 return !NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001194}
1195
Linus Torvalds1da177e2005-04-16 15:20:36 -07001196/* Check whether current node S[h] is balanced when increasing its size by
1197 * Inserting or Pasting.
1198 * Calculate parameters for balancing for current level h.
1199 * Parameters:
1200 * tb tree_balance structure;
1201 * h current level of the node;
1202 * inum item number in S[h];
1203 * mode i - insert, p - paste;
1204 * Returns: 1 - schedule occurred;
1205 * 0 - balancing for higher levels needed;
1206 * -1 - no balancing for higher levels needed;
1207 * -2 - no disk space.
1208 */
1209/* ip means Inserting or Pasting */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001210static int ip_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001211{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001212 struct virtual_node *vn = tb->tb_vn;
1213 int levbytes, /* Number of bytes that must be inserted into (value
1214 is negative if bytes are deleted) buffer which
1215 contains node being balanced. The mnemonic is
1216 that the attempted change in node space used level
1217 is levbytes bytes. */
1218 n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001219
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001220 int lfree, sfree, rfree /* free space in L, S and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001221
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001222 /* nver is short for number of vertixes, and lnver is the number if
1223 we shift to the left, rnver is the number if we shift to the
1224 right, and lrnver is the number if we shift in both directions.
1225 The goal is to minimize first the number of vertixes, and second,
1226 the number of vertixes whose contents are changed by shifting,
1227 and third the number of uncached vertixes whose contents are
1228 changed by shifting and must be read from disk. */
1229 int nver, lnver, rnver, lrnver;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001230
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001231 /* used at leaf level only, S0 = S[0] is the node being balanced,
1232 sInum [ I = 0,1,2 ] is the number of items that will
1233 remain in node SI after balancing. S1 and S2 are new
1234 nodes that might be created. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001235
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001236 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
1237 where 4th parameter is s1bytes and 5th - s2bytes
Linus Torvalds1da177e2005-04-16 15:20:36 -07001238 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001239 short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
1240 0,1 - do not shift and do not shift but bottle
1241 2 - shift only whole item to left
1242 3 - shift to left and bottle as much as possible
1243 4,5 - shift to right (whole items and as much as possible
1244 6,7 - shift to both directions (whole items and as much as possible)
1245 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001246
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001247 /* Sh is the node whose balance is currently being checked */
1248 struct buffer_head *Sh;
1249
1250 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1251 levbytes = tb->insert_size[h];
1252
1253 /* Calculate balance parameters for creating new root. */
1254 if (!Sh) {
1255 if (!h)
1256 reiserfs_panic(tb->tb_sb,
1257 "vs-8210: ip_check_balance: S[0] can not be 0");
1258 switch (n_ret_value = get_empty_nodes(tb, h)) {
1259 case CARRY_ON:
1260 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1261 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1262
1263 case NO_DISK_SPACE:
1264 case REPEAT_SEARCH:
1265 return n_ret_value;
1266 default:
1267 reiserfs_panic(tb->tb_sb,
1268 "vs-8215: ip_check_balance: incorrect return value of get_empty_nodes");
1269 }
1270 }
1271
1272 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */
1273 return n_ret_value;
1274
1275 sfree = B_FREE_SPACE(Sh);
1276
1277 /* get free space of neighbors */
1278 rfree = get_rfree(tb, h);
1279 lfree = get_lfree(tb, h);
1280
1281 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1282 NO_BALANCING_NEEDED)
1283 /* and new item fits into node S[h] without any shifting */
1284 return NO_BALANCING_NEEDED;
1285
1286 create_virtual_node(tb, h);
1287
1288 /*
1289 determine maximal number of items we can shift to the left neighbor (in tb structure)
1290 and the maximal number of bytes that can flow to the left neighbor
1291 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1292 */
1293 check_left(tb, h, lfree);
1294
1295 /*
1296 determine maximal number of items we can shift to the right neighbor (in tb structure)
1297 and the maximal number of bytes that can flow to the right neighbor
1298 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1299 */
1300 check_right(tb, h, rfree);
1301
1302 /* all contents of internal node S[h] can be moved into its
1303 neighbors, S[h] will be removed after balancing */
1304 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1305 int to_r;
1306
1307 /* Since we are working on internal nodes, and our internal
1308 nodes have fixed size entries, then we can balance by the
1309 number of items rather than the space they consume. In this
1310 routine we set the left node equal to the right node,
1311 allowing a difference of less than or equal to 1 child
1312 pointer. */
1313 to_r =
1314 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1315 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1316 tb->rnum[h]);
1317 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1318 -1, -1);
1319 return CARRY_ON;
1320 }
1321
1322 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1323 RFALSE(h &&
1324 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1325 tb->rnum[h] >= vn->vn_nr_item + 1),
1326 "vs-8220: tree is not balanced on internal level");
1327 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1328 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1329 "vs-8225: tree is not balanced on leaf level");
1330
1331 /* all contents of S[0] can be moved into its neighbors
1332 S[0] will be removed after balancing. */
1333 if (!h && is_leaf_removable(tb))
1334 return CARRY_ON;
1335
1336 /* why do we perform this check here rather than earlier??
1337 Answer: we can win 1 node in some cases above. Moreover we
1338 checked it above, when we checked, that S[0] is not removable
1339 in principle */
1340 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1341 if (!h)
1342 tb->s0num = vn->vn_nr_item;
1343 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1344 return NO_BALANCING_NEEDED;
1345 }
1346
1347 {
1348 int lpar, rpar, nset, lset, rset, lrset;
1349 /*
1350 * regular overflowing of the node
1351 */
1352
1353 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
1354 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
1355 nset, lset, rset, lrset - shows, whether flowing items give better packing
1356 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001357#define FLOW 1
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001358#define NO_FLOW 0 /* do not any splitting */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001360 /* we choose one the following */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361#define NOTHING_SHIFT_NO_FLOW 0
1362#define NOTHING_SHIFT_FLOW 5
1363#define LEFT_SHIFT_NO_FLOW 10
1364#define LEFT_SHIFT_FLOW 15
1365#define RIGHT_SHIFT_NO_FLOW 20
1366#define RIGHT_SHIFT_FLOW 25
1367#define LR_SHIFT_NO_FLOW 30
1368#define LR_SHIFT_FLOW 35
1369
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001370 lpar = tb->lnum[h];
1371 rpar = tb->rnum[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001373 /* calculate number of blocks S[h] must be split into when
1374 nothing is shifted to the neighbors,
1375 as well as number of items in each part of the split node (s012 numbers),
1376 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1377 nset = NOTHING_SHIFT_NO_FLOW;
1378 nver = get_num_ver(vn->vn_mode, tb, h,
1379 0, -1, h ? vn->vn_nr_item : 0, -1,
1380 snum012, NO_FLOW);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001381
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001382 if (!h) {
1383 int nver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001384
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001385 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1386 nver1 = get_num_ver(vn->vn_mode, tb, h,
1387 0, -1, 0, -1,
1388 snum012 + NOTHING_SHIFT_FLOW, FLOW);
1389 if (nver > nver1)
1390 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1391 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001392
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001393 /* calculate number of blocks S[h] must be split into when
1394 l_shift_num first items and l_shift_bytes of the right most
1395 liquid item to be shifted are shifted to the left neighbor,
1396 as well as number of items in each part of the splitted node (s012 numbers),
1397 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1398 */
1399 lset = LEFT_SHIFT_NO_FLOW;
1400 lnver = get_num_ver(vn->vn_mode, tb, h,
1401 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1402 -1, h ? vn->vn_nr_item : 0, -1,
1403 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1404 if (!h) {
1405 int lnver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001406
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001407 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1408 lpar -
1409 ((tb->lbytes != -1) ? 1 : 0),
1410 tb->lbytes, 0, -1,
1411 snum012 + LEFT_SHIFT_FLOW, FLOW);
1412 if (lnver > lnver1)
1413 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1414 }
1415
1416 /* calculate number of blocks S[h] must be split into when
1417 r_shift_num first items and r_shift_bytes of the left most
1418 liquid item to be shifted are shifted to the right neighbor,
1419 as well as number of items in each part of the splitted node (s012 numbers),
1420 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1421 */
1422 rset = RIGHT_SHIFT_NO_FLOW;
1423 rnver = get_num_ver(vn->vn_mode, tb, h,
1424 0, -1,
1425 h ? (vn->vn_nr_item - rpar) : (rpar -
1426 ((tb->
1427 rbytes !=
1428 -1) ? 1 :
1429 0)), -1,
1430 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1431 if (!h) {
1432 int rnver1;
1433
1434 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1435 0, -1,
1436 (rpar -
1437 ((tb->rbytes != -1) ? 1 : 0)),
1438 tb->rbytes,
1439 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1440
1441 if (rnver > rnver1)
1442 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1443 }
1444
1445 /* calculate number of blocks S[h] must be split into when
1446 items are shifted in both directions,
1447 as well as number of items in each part of the splitted node (s012 numbers),
1448 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1449 */
1450 lrset = LR_SHIFT_NO_FLOW;
1451 lrnver = get_num_ver(vn->vn_mode, tb, h,
1452 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1453 -1,
1454 h ? (vn->vn_nr_item - rpar) : (rpar -
1455 ((tb->
1456 rbytes !=
1457 -1) ? 1 :
1458 0)), -1,
1459 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1460 if (!h) {
1461 int lrnver1;
1462
1463 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1464 lpar -
1465 ((tb->lbytes != -1) ? 1 : 0),
1466 tb->lbytes,
1467 (rpar -
1468 ((tb->rbytes != -1) ? 1 : 0)),
1469 tb->rbytes,
1470 snum012 + LR_SHIFT_FLOW, FLOW);
1471 if (lrnver > lrnver1)
1472 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1473 }
1474
1475 /* Our general shifting strategy is:
1476 1) to minimized number of new nodes;
1477 2) to minimized number of neighbors involved in shifting;
1478 3) to minimized number of disk reads; */
1479
1480 /* we can win TWO or ONE nodes by shifting in both directions */
1481 if (lrnver < lnver && lrnver < rnver) {
1482 RFALSE(h &&
1483 (tb->lnum[h] != 1 ||
1484 tb->rnum[h] != 1 ||
1485 lrnver != 1 || rnver != 2 || lnver != 2
1486 || h != 1), "vs-8230: bad h");
1487 if (lrset == LR_SHIFT_FLOW)
1488 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1489 lrnver, snum012 + lrset,
1490 tb->lbytes, tb->rbytes);
1491 else
1492 set_parameters(tb, h,
1493 tb->lnum[h] -
1494 ((tb->lbytes == -1) ? 0 : 1),
1495 tb->rnum[h] -
1496 ((tb->rbytes == -1) ? 0 : 1),
1497 lrnver, snum012 + lrset, -1, -1);
1498
1499 return CARRY_ON;
1500 }
1501
1502 /* if shifting doesn't lead to better packing then don't shift */
1503 if (nver == lrnver) {
1504 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1505 -1);
1506 return CARRY_ON;
1507 }
1508
1509 /* now we know that for better packing shifting in only one
1510 direction either to the left or to the right is required */
1511
1512 /* if shifting to the left is better than shifting to the right */
1513 if (lnver < rnver) {
1514 SET_PAR_SHIFT_LEFT;
1515 return CARRY_ON;
1516 }
1517
1518 /* if shifting to the right is better than shifting to the left */
1519 if (lnver > rnver) {
1520 SET_PAR_SHIFT_RIGHT;
1521 return CARRY_ON;
1522 }
1523
1524 /* now shifting in either direction gives the same number
1525 of nodes and we can make use of the cached neighbors */
1526 if (is_left_neighbor_in_cache(tb, h)) {
1527 SET_PAR_SHIFT_LEFT;
1528 return CARRY_ON;
1529 }
1530
1531 /* shift to the right independently on whether the right neighbor in cache or not */
1532 SET_PAR_SHIFT_RIGHT;
1533 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001534 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001535}
1536
Linus Torvalds1da177e2005-04-16 15:20:36 -07001537/* Check whether current node S[h] is balanced when Decreasing its size by
1538 * Deleting or Cutting for INTERNAL node of S+tree.
1539 * Calculate parameters for balancing for current level h.
1540 * Parameters:
1541 * tb tree_balance structure;
1542 * h current level of the node;
1543 * inum item number in S[h];
1544 * mode i - insert, p - paste;
1545 * Returns: 1 - schedule occurred;
1546 * 0 - balancing for higher levels needed;
1547 * -1 - no balancing for higher levels needed;
1548 * -2 - no disk space.
1549 *
1550 * Note: Items of internal nodes have fixed size, so the balance condition for
1551 * the internal part of S+tree is as for the B-trees.
1552 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001553static int dc_check_balance_internal(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001554{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001555 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001556
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001557 /* Sh is the node whose balance is currently being checked,
1558 and Fh is its father. */
1559 struct buffer_head *Sh, *Fh;
1560 int maxsize, n_ret_value;
1561 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001562
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001563 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1564 Fh = PATH_H_PPARENT(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001565
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001566 maxsize = MAX_CHILD_SIZE(Sh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001567
1568/* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1569/* new_nr_item = number of items node would have if operation is */
1570/* performed without balancing (new_nr_item); */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001571 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001572
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001573 if (!Fh) { /* S[h] is the root. */
1574 if (vn->vn_nr_item > 0) {
1575 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1576 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1577 }
1578 /* new_nr_item == 0.
1579 * Current root will be deleted resulting in
1580 * decrementing the tree height. */
1581 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1582 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001583 }
1584
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001585 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1586 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001587
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001588 /* get free space of neighbors */
1589 rfree = get_rfree(tb, h);
1590 lfree = get_lfree(tb, h);
1591
1592 /* determine maximal number of items we can fit into neighbors */
1593 check_left(tb, h, lfree);
1594 check_right(tb, h, rfree);
1595
1596 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
1597 * In this case we balance only if it leads to better packing. */
1598 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
1599 * which is impossible with greater values of new_nr_item. */
1600 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1601 /* All contents of S[h] can be moved to L[h]. */
1602 int n;
1603 int order_L;
1604
1605 order_L =
1606 ((n =
1607 PATH_H_B_ITEM_ORDER(tb->tb_path,
1608 h)) ==
1609 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1610 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1611 (DC_SIZE + KEY_SIZE);
1612 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1613 -1);
1614 return CARRY_ON;
1615 }
1616
1617 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1618 /* All contents of S[h] can be moved to R[h]. */
1619 int n;
1620 int order_R;
1621
1622 order_R =
1623 ((n =
1624 PATH_H_B_ITEM_ORDER(tb->tb_path,
1625 h)) ==
1626 B_NR_ITEMS(Fh)) ? 0 : n + 1;
1627 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1628 (DC_SIZE + KEY_SIZE);
1629 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1630 -1);
1631 return CARRY_ON;
1632 }
1633 }
1634
1635 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1636 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1637 int to_r;
1638
1639 to_r =
1640 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1641 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1642 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1643 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1644 0, NULL, -1, -1);
1645 return CARRY_ON;
1646 }
1647
1648 /* Balancing does not lead to better packing. */
1649 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1650 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001651 }
1652
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001653 /* Current node contain insufficient number of items. Balancing is required. */
1654 /* Check whether we can merge S[h] with left neighbor. */
1655 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1656 if (is_left_neighbor_in_cache(tb, h)
1657 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1658 int n;
1659 int order_L;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001660
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001661 order_L =
1662 ((n =
1663 PATH_H_B_ITEM_ORDER(tb->tb_path,
1664 h)) ==
1665 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1666 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1667 KEY_SIZE);
1668 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1669 return CARRY_ON;
1670 }
1671
1672 /* Check whether we can merge S[h] with right neighbor. */
1673 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1674 int n;
1675 int order_R;
1676
1677 order_R =
1678 ((n =
1679 PATH_H_B_ITEM_ORDER(tb->tb_path,
1680 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1681 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1682 KEY_SIZE);
1683 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1684 return CARRY_ON;
1685 }
1686
1687 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1688 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1689 int to_r;
1690
1691 to_r =
1692 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1693 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1694 tb->rnum[h]);
1695 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1696 -1, -1);
1697 return CARRY_ON;
1698 }
1699
1700 /* For internal nodes try to borrow item from a neighbor */
1701 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1702
1703 /* Borrow one or two items from caching neighbor */
1704 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1705 int from_l;
1706
1707 from_l =
1708 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1709 1) / 2 - (vn->vn_nr_item + 1);
1710 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1711 return CARRY_ON;
1712 }
1713
1714 set_parameters(tb, h, 0,
1715 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1716 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001717 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001718}
1719
Linus Torvalds1da177e2005-04-16 15:20:36 -07001720/* Check whether current node S[h] is balanced when Decreasing its size by
1721 * Deleting or Truncating for LEAF node of S+tree.
1722 * Calculate parameters for balancing for current level h.
1723 * Parameters:
1724 * tb tree_balance structure;
1725 * h current level of the node;
1726 * inum item number in S[h];
1727 * mode i - insert, p - paste;
1728 * Returns: 1 - schedule occurred;
1729 * 0 - balancing for higher levels needed;
1730 * -1 - no balancing for higher levels needed;
1731 * -2 - no disk space.
1732 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001733static int dc_check_balance_leaf(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001734{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001735 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001736
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001737 /* Number of bytes that must be deleted from
1738 (value is negative if bytes are deleted) buffer which
1739 contains node being balanced. The mnemonic is that the
1740 attempted change in node space used level is levbytes bytes. */
1741 int levbytes;
1742 /* the maximal item size */
1743 int maxsize, n_ret_value;
1744 /* S0 is the node whose balance is currently being checked,
1745 and F0 is its father. */
1746 struct buffer_head *S0, *F0;
1747 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001748
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001749 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1750 F0 = PATH_H_PPARENT(tb->tb_path, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001751
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001752 levbytes = tb->insert_size[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001753
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001754 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001755
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001756 if (!F0) { /* S[0] is the root now. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001757
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001758 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1759 "vs-8240: attempt to create empty buffer tree");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001760
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001761 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1762 return NO_BALANCING_NEEDED;
1763 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001764
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001765 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1766 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001767
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001768 /* get free space of neighbors */
1769 rfree = get_rfree(tb, h);
1770 lfree = get_lfree(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001771
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001772 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001773
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001774 /* if 3 leaves can be merge to one, set parameters and return */
1775 if (are_leaves_removable(tb, lfree, rfree))
1776 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001777
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001778 /* determine maximal number of items we can shift to the left/right neighbor
1779 and the maximal number of bytes that can flow to the left/right neighbor
1780 from the left/right most liquid item that cannot be shifted from S[0] entirely
1781 */
1782 check_left(tb, h, lfree);
1783 check_right(tb, h, rfree);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001784
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001785 /* check whether we can merge S with left neighbor. */
1786 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1787 if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) || /* S can not be merged with R */
1788 !tb->FR[h]) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001789
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001790 RFALSE(!tb->FL[h],
1791 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001792
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001793 /* set parameter to merge S[0] with its left neighbor */
1794 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1795 return CARRY_ON;
1796 }
1797
1798 /* check whether we can merge S[0] with right neighbor. */
1799 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1800 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
1801 return CARRY_ON;
1802 }
1803
1804 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1805 if (is_leaf_removable(tb))
1806 return CARRY_ON;
1807
1808 /* Balancing is not required. */
1809 tb->s0num = vn->vn_nr_item;
1810 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1811 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001812}
1813
Linus Torvalds1da177e2005-04-16 15:20:36 -07001814/* Check whether current node S[h] is balanced when Decreasing its size by
1815 * Deleting or Cutting.
1816 * Calculate parameters for balancing for current level h.
1817 * Parameters:
1818 * tb tree_balance structure;
1819 * h current level of the node;
1820 * inum item number in S[h];
1821 * mode d - delete, c - cut.
1822 * Returns: 1 - schedule occurred;
1823 * 0 - balancing for higher levels needed;
1824 * -1 - no balancing for higher levels needed;
1825 * -2 - no disk space.
1826 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001827static int dc_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001828{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001829 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1830 "vs-8250: S is not initialized");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001831
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001832 if (h)
1833 return dc_check_balance_internal(tb, h);
1834 else
1835 return dc_check_balance_leaf(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001836}
1837
Linus Torvalds1da177e2005-04-16 15:20:36 -07001838/* Check whether current node S[h] is balanced.
1839 * Calculate parameters for balancing for current level h.
1840 * Parameters:
1841 *
1842 * tb tree_balance structure:
1843 *
1844 * tb is a large structure that must be read about in the header file
1845 * at the same time as this procedure if the reader is to successfully
1846 * understand this procedure
1847 *
1848 * h current level of the node;
1849 * inum item number in S[h];
1850 * mode i - insert, p - paste, d - delete, c - cut.
1851 * Returns: 1 - schedule occurred;
1852 * 0 - balancing for higher levels needed;
1853 * -1 - no balancing for higher levels needed;
1854 * -2 - no disk space.
1855 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001856static int check_balance(int mode,
1857 struct tree_balance *tb,
1858 int h,
1859 int inum,
1860 int pos_in_item,
1861 struct item_head *ins_ih, const void *data)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001862{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001863 struct virtual_node *vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001864
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001865 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
1866 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
1867 vn->vn_mode = mode;
1868 vn->vn_affected_item_num = inum;
1869 vn->vn_pos_in_item = pos_in_item;
1870 vn->vn_ins_ih = ins_ih;
1871 vn->vn_data = data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001872
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001873 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1874 "vs-8255: ins_ih can not be 0 in insert mode");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001875
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001876 if (tb->insert_size[h] > 0)
1877 /* Calculate balance parameters when size of node is increasing. */
1878 return ip_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001879
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001880 /* Calculate balance parameters when size of node is decreasing. */
1881 return dc_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001882}
1883
Linus Torvalds1da177e2005-04-16 15:20:36 -07001884/* Check whether parent at the path is the really parent of the current node.*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001885static int get_direct_parent(struct tree_balance *p_s_tb, int n_h)
1886{
1887 struct buffer_head *p_s_bh;
1888 struct path *p_s_path = p_s_tb->tb_path;
1889 int n_position,
1890 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001891
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001892 /* We are in the root or in the new root. */
1893 if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1894
1895 RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
1896 "PAP-8260: invalid offset in the path");
1897
1898 if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->
1899 b_blocknr == SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
1900 /* Root is not changed. */
1901 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
1902 PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
1903 return CARRY_ON;
1904 }
1905 return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001906 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001907
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001908 if (!B_IS_IN_TREE
1909 (p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)))
1910 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001911
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001912 if ((n_position =
1913 PATH_OFFSET_POSITION(p_s_path,
1914 n_path_offset - 1)) > B_NR_ITEMS(p_s_bh))
1915 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001916
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001917 if (B_N_CHILD_NUM(p_s_bh, n_position) !=
1918 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr)
1919 /* Parent in the path is not parent of the current node in the tree. */
1920 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001921
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001922 if (buffer_locked(p_s_bh)) {
1923 __wait_on_buffer(p_s_bh);
1924 if (FILESYSTEM_CHANGED_TB(p_s_tb))
1925 return REPEAT_SEARCH;
1926 }
1927
1928 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001929}
1930
Linus Torvalds1da177e2005-04-16 15:20:36 -07001931/* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1932 * of S[n_h] we
1933 * need in order to balance S[n_h], and get them if necessary.
1934 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1935 * CARRY_ON - schedule didn't occur while the function worked;
1936 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001937static int get_neighbors(struct tree_balance *p_s_tb, int n_h)
1938{
1939 int n_child_position,
1940 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
1941 unsigned long n_son_number;
1942 struct super_block *p_s_sb = p_s_tb->tb_sb;
1943 struct buffer_head *p_s_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001944
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001945 PROC_INFO_INC(p_s_sb, get_neighbors[n_h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001946
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001947 if (p_s_tb->lnum[n_h]) {
1948 /* We need left neighbor to balance S[n_h]. */
1949 PROC_INFO_INC(p_s_sb, need_l_neighbor[n_h]);
1950 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001951
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001952 RFALSE(p_s_bh == p_s_tb->FL[n_h] &&
1953 !PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
1954 "PAP-8270: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001955
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001956 n_child_position =
1957 (p_s_bh ==
1958 p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->
1959 FL[n_h]);
1960 n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
1961 p_s_bh = sb_bread(p_s_sb, n_son_number);
1962 if (!p_s_bh)
1963 return IO_ERROR;
1964 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1965 decrement_bcount(p_s_bh);
1966 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
1967 return REPEAT_SEARCH;
1968 }
1969
1970 RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
1971 n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
1972 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
1973 p_s_bh->b_blocknr, "PAP-8275: invalid parent");
1974 RFALSE(!B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child");
1975 RFALSE(!n_h &&
1976 B_FREE_SPACE(p_s_bh) !=
1977 MAX_CHILD_SIZE(p_s_bh) -
1978 dc_size(B_N_CHILD(p_s_tb->FL[0], n_child_position)),
1979 "PAP-8290: invalid child size of left neighbor");
1980
1981 decrement_bcount(p_s_tb->L[n_h]);
1982 p_s_tb->L[n_h] = p_s_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001983 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001984
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001985 if (p_s_tb->rnum[n_h]) { /* We need right neighbor to balance S[n_path_offset]. */
1986 PROC_INFO_INC(p_s_sb, need_r_neighbor[n_h]);
1987 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001988
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001989 RFALSE(p_s_bh == p_s_tb->FR[n_h] &&
1990 PATH_OFFSET_POSITION(p_s_tb->tb_path,
1991 n_path_offset) >=
1992 B_NR_ITEMS(p_s_bh),
1993 "PAP-8295: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001994
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001995 n_child_position =
1996 (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0;
1997 n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
1998 p_s_bh = sb_bread(p_s_sb, n_son_number);
1999 if (!p_s_bh)
2000 return IO_ERROR;
2001 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2002 decrement_bcount(p_s_bh);
2003 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
2004 return REPEAT_SEARCH;
2005 }
2006 decrement_bcount(p_s_tb->R[n_h]);
2007 p_s_tb->R[n_h] = p_s_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002008
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002009 RFALSE(!n_h
2010 && B_FREE_SPACE(p_s_bh) !=
2011 MAX_CHILD_SIZE(p_s_bh) -
2012 dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)),
2013 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2014 B_FREE_SPACE(p_s_bh), MAX_CHILD_SIZE(p_s_bh),
2015 dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)));
2016
Linus Torvalds1da177e2005-04-16 15:20:36 -07002017 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002018 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002019}
2020
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002021static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002022{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002023 int max_num_of_items;
2024 int max_num_of_entries;
2025 unsigned long blocksize = sb->s_blocksize;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002026
2027#define MIN_NAME_LEN 1
2028
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002029 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2030 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2031 (DEH_SIZE + MIN_NAME_LEN);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002032
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002033 return sizeof(struct virtual_node) +
2034 max(max_num_of_items * sizeof(struct virtual_item),
2035 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2036 (max_num_of_entries - 1) * sizeof(__u16));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002037}
2038
Linus Torvalds1da177e2005-04-16 15:20:36 -07002039/* maybe we should fail balancing we are going to perform when kmalloc
2040 fails several times. But now it will loop until kmalloc gets
2041 required memory */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002042static int get_mem_for_virtual_node(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002043{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002044 int check_fs = 0;
2045 int size;
2046 char *buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002047
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002048 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002049
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002050 if (size > tb->vn_buf_size) {
2051 /* we have to allocate more memory for virtual node */
2052 if (tb->vn_buf) {
2053 /* free memory allocated before */
Pekka Enbergd739b422006-02-01 03:06:43 -08002054 kfree(tb->vn_buf);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002055 /* this is not needed if kfree is atomic */
2056 check_fs = 1;
2057 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002058
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002059 /* virtual node requires now more memory */
2060 tb->vn_buf_size = size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002061
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002062 /* get memory for virtual item */
Pekka Enbergd739b422006-02-01 03:06:43 -08002063 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002064 if (!buf) {
2065 /* getting memory with GFP_KERNEL priority may involve
2066 balancing now (due to indirect_to_direct conversion on
2067 dcache shrinking). So, release path and collected
2068 resources here */
2069 free_buffers_in_tb(tb);
Pekka Enbergd739b422006-02-01 03:06:43 -08002070 buf = kmalloc(size, GFP_NOFS);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002071 if (!buf) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002072 tb->vn_buf_size = 0;
2073 }
2074 tb->vn_buf = buf;
2075 schedule();
2076 return REPEAT_SEARCH;
2077 }
2078
2079 tb->vn_buf = buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002080 }
2081
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002082 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2083 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002084
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002085 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002086}
2087
Linus Torvalds1da177e2005-04-16 15:20:36 -07002088#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002089static void tb_buffer_sanity_check(struct super_block *p_s_sb,
2090 struct buffer_head *p_s_bh,
2091 const char *descr, int level)
2092{
2093 if (p_s_bh) {
2094 if (atomic_read(&(p_s_bh->b_count)) <= 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002095
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002096 reiserfs_panic(p_s_sb,
2097 "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n",
2098 descr, level, p_s_bh);
2099 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002100
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002101 if (!buffer_uptodate(p_s_bh)) {
2102 reiserfs_panic(p_s_sb,
2103 "jmacd-2: tb_buffer_sanity_check(): buffer is not up to date %s[%d] (%b)\n",
2104 descr, level, p_s_bh);
2105 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002106
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002107 if (!B_IS_IN_TREE(p_s_bh)) {
2108 reiserfs_panic(p_s_sb,
2109 "jmacd-3: tb_buffer_sanity_check(): buffer is not in tree %s[%d] (%b)\n",
2110 descr, level, p_s_bh);
2111 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002112
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002113 if (p_s_bh->b_bdev != p_s_sb->s_bdev) {
2114 reiserfs_panic(p_s_sb,
2115 "jmacd-4: tb_buffer_sanity_check(): buffer has wrong device %s[%d] (%b)\n",
2116 descr, level, p_s_bh);
2117 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002118
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002119 if (p_s_bh->b_size != p_s_sb->s_blocksize) {
2120 reiserfs_panic(p_s_sb,
2121 "jmacd-5: tb_buffer_sanity_check(): buffer has wrong blocksize %s[%d] (%b)\n",
2122 descr, level, p_s_bh);
2123 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002124
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002125 if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(p_s_sb)) {
2126 reiserfs_panic(p_s_sb,
2127 "jmacd-6: tb_buffer_sanity_check(): buffer block number too high %s[%d] (%b)\n",
2128 descr, level, p_s_bh);
2129 }
2130 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002131}
2132#else
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002133static void tb_buffer_sanity_check(struct super_block *p_s_sb,
2134 struct buffer_head *p_s_bh,
2135 const char *descr, int level)
2136{;
2137}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002138#endif
2139
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002140static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002141{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002142 return reiserfs_prepare_for_journal(s, bh, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002143}
2144
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002145static int wait_tb_buffers_until_unlocked(struct tree_balance *p_s_tb)
2146{
2147 struct buffer_head *locked;
2148#ifdef CONFIG_REISERFS_CHECK
2149 int repeat_counter = 0;
2150#endif
2151 int i;
2152
2153 do {
2154
2155 locked = NULL;
2156
2157 for (i = p_s_tb->tb_path->path_length;
2158 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2159 if (PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2160 /* if I understand correctly, we can only be sure the last buffer
2161 ** in the path is in the tree --clm
2162 */
2163#ifdef CONFIG_REISERFS_CHECK
2164 if (PATH_PLAST_BUFFER(p_s_tb->tb_path) ==
2165 PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2166 tb_buffer_sanity_check(p_s_tb->tb_sb,
2167 PATH_OFFSET_PBUFFER
2168 (p_s_tb->tb_path,
2169 i), "S",
2170 p_s_tb->tb_path->
2171 path_length - i);
2172 }
2173#endif
2174 if (!clear_all_dirty_bits(p_s_tb->tb_sb,
2175 PATH_OFFSET_PBUFFER
2176 (p_s_tb->tb_path,
2177 i))) {
2178 locked =
2179 PATH_OFFSET_PBUFFER(p_s_tb->tb_path,
2180 i);
2181 }
2182 }
2183 }
2184
2185 for (i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i];
2186 i++) {
2187
2188 if (p_s_tb->lnum[i]) {
2189
2190 if (p_s_tb->L[i]) {
2191 tb_buffer_sanity_check(p_s_tb->tb_sb,
2192 p_s_tb->L[i],
2193 "L", i);
2194 if (!clear_all_dirty_bits
2195 (p_s_tb->tb_sb, p_s_tb->L[i]))
2196 locked = p_s_tb->L[i];
2197 }
2198
2199 if (!locked && p_s_tb->FL[i]) {
2200 tb_buffer_sanity_check(p_s_tb->tb_sb,
2201 p_s_tb->FL[i],
2202 "FL", i);
2203 if (!clear_all_dirty_bits
2204 (p_s_tb->tb_sb, p_s_tb->FL[i]))
2205 locked = p_s_tb->FL[i];
2206 }
2207
2208 if (!locked && p_s_tb->CFL[i]) {
2209 tb_buffer_sanity_check(p_s_tb->tb_sb,
2210 p_s_tb->CFL[i],
2211 "CFL", i);
2212 if (!clear_all_dirty_bits
2213 (p_s_tb->tb_sb, p_s_tb->CFL[i]))
2214 locked = p_s_tb->CFL[i];
2215 }
2216
2217 }
2218
2219 if (!locked && (p_s_tb->rnum[i])) {
2220
2221 if (p_s_tb->R[i]) {
2222 tb_buffer_sanity_check(p_s_tb->tb_sb,
2223 p_s_tb->R[i],
2224 "R", i);
2225 if (!clear_all_dirty_bits
2226 (p_s_tb->tb_sb, p_s_tb->R[i]))
2227 locked = p_s_tb->R[i];
2228 }
2229
2230 if (!locked && p_s_tb->FR[i]) {
2231 tb_buffer_sanity_check(p_s_tb->tb_sb,
2232 p_s_tb->FR[i],
2233 "FR", i);
2234 if (!clear_all_dirty_bits
2235 (p_s_tb->tb_sb, p_s_tb->FR[i]))
2236 locked = p_s_tb->FR[i];
2237 }
2238
2239 if (!locked && p_s_tb->CFR[i]) {
2240 tb_buffer_sanity_check(p_s_tb->tb_sb,
2241 p_s_tb->CFR[i],
2242 "CFR", i);
2243 if (!clear_all_dirty_bits
2244 (p_s_tb->tb_sb, p_s_tb->CFR[i]))
2245 locked = p_s_tb->CFR[i];
2246 }
2247 }
2248 }
2249 /* as far as I can tell, this is not required. The FEB list seems
2250 ** to be full of newly allocated nodes, which will never be locked,
2251 ** dirty, or anything else.
2252 ** To be safe, I'm putting in the checks and waits in. For the moment,
2253 ** they are needed to keep the code in journal.c from complaining
2254 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2255 ** --clm
2256 */
2257 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2258 if (p_s_tb->FEB[i]) {
2259 if (!clear_all_dirty_bits
2260 (p_s_tb->tb_sb, p_s_tb->FEB[i]))
2261 locked = p_s_tb->FEB[i];
2262 }
2263 }
2264
2265 if (locked) {
2266#ifdef CONFIG_REISERFS_CHECK
2267 repeat_counter++;
2268 if ((repeat_counter % 10000) == 0) {
2269 reiserfs_warning(p_s_tb->tb_sb,
2270 "wait_tb_buffers_until_released(): too many "
2271 "iterations waiting for buffer to unlock "
2272 "(%b)", locked);
2273
2274 /* Don't loop forever. Try to recover from possible error. */
2275
2276 return (FILESYSTEM_CHANGED_TB(p_s_tb)) ?
2277 REPEAT_SEARCH : CARRY_ON;
2278 }
2279#endif
2280 __wait_on_buffer(locked);
2281 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2282 return REPEAT_SEARCH;
2283 }
2284 }
2285
2286 } while (locked);
2287
2288 return CARRY_ON;
2289}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002290
2291/* Prepare for balancing, that is
2292 * get all necessary parents, and neighbors;
2293 * analyze what and where should be moved;
2294 * get sufficient number of new nodes;
2295 * Balancing will start only after all resources will be collected at a time.
2296 *
2297 * When ported to SMP kernels, only at the last moment after all needed nodes
2298 * are collected in cache, will the resources be locked using the usual
2299 * textbook ordered lock acquisition algorithms. Note that ensuring that
2300 * this code neither write locks what it does not need to write lock nor locks out of order
2301 * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans
2302 *
2303 * fix is meant in the sense of render unchanging
2304 *
2305 * Latency might be improved by first gathering a list of what buffers are needed
2306 * and then getting as many of them in parallel as possible? -Hans
2307 *
2308 * Parameters:
2309 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2310 * tb tree_balance structure;
2311 * inum item number in S[h];
2312 * pos_in_item - comment this if you can
2313 * ins_ih & ins_sd are used when inserting
2314 * Returns: 1 - schedule occurred while the function worked;
2315 * 0 - schedule didn't occur while the function worked;
2316 * -1 - if no_disk_space
2317 */
2318
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002319int fix_nodes(int n_op_mode, struct tree_balance *p_s_tb, struct item_head *p_s_ins_ih, // item head of item being inserted
2320 const void *data // inserted item or data to be pasted
2321 )
2322{
2323 int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
2324 int n_pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002325
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002326 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2327 ** during wait_tb_buffers_run
2328 */
2329 int wait_tb_buffers_run = 0;
2330 struct buffer_head *p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002331
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002332 ++REISERFS_SB(p_s_tb->tb_sb)->s_fix_nodes;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002333
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002334 n_pos_in_item = p_s_tb->tb_path->pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002335
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002336 p_s_tb->fs_gen = get_generation(p_s_tb->tb_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002337
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002338 /* we prepare and log the super here so it will already be in the
2339 ** transaction when do_balance needs to change it.
2340 ** This way do_balance won't have to schedule when trying to prepare
2341 ** the super for logging
2342 */
2343 reiserfs_prepare_for_journal(p_s_tb->tb_sb,
2344 SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1);
2345 journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb,
2346 SB_BUFFER_WITH_SB(p_s_tb->tb_sb));
2347 if (FILESYSTEM_CHANGED_TB(p_s_tb))
2348 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002349
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002350 /* if it possible in indirect_to_direct conversion */
2351 if (buffer_locked(p_s_tbS0)) {
2352 __wait_on_buffer(p_s_tbS0);
2353 if (FILESYSTEM_CHANGED_TB(p_s_tb))
2354 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002355 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002356#ifdef CONFIG_REISERFS_CHECK
2357 if (cur_tb) {
2358 print_cur_tb("fix_nodes");
2359 reiserfs_panic(p_s_tb->tb_sb,
2360 "PAP-8305: fix_nodes: there is pending do_balance");
2361 }
2362
2363 if (!buffer_uptodate(p_s_tbS0) || !B_IS_IN_TREE(p_s_tbS0)) {
2364 reiserfs_panic(p_s_tb->tb_sb,
2365 "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate "
2366 "at the beginning of fix_nodes or not in tree (mode %c)",
2367 p_s_tbS0, p_s_tbS0, n_op_mode);
2368 }
2369
2370 /* Check parameters. */
2371 switch (n_op_mode) {
2372 case M_INSERT:
2373 if (n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0))
2374 reiserfs_panic(p_s_tb->tb_sb,
2375 "PAP-8330: fix_nodes: Incorrect item number %d (in S0 - %d) in case of insert",
2376 n_item_num, B_NR_ITEMS(p_s_tbS0));
2377 break;
2378 case M_PASTE:
2379 case M_DELETE:
2380 case M_CUT:
2381 if (n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0)) {
2382 print_block(p_s_tbS0, 0, -1, -1);
2383 reiserfs_panic(p_s_tb->tb_sb,
2384 "PAP-8335: fix_nodes: Incorrect item number(%d); mode = %c insert_size = %d\n",
2385 n_item_num, n_op_mode,
2386 p_s_tb->insert_size[0]);
2387 }
2388 break;
2389 default:
2390 reiserfs_panic(p_s_tb->tb_sb,
2391 "PAP-8340: fix_nodes: Incorrect mode of operation");
2392 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002393#endif
2394
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002395 if (get_mem_for_virtual_node(p_s_tb) == REPEAT_SEARCH)
2396 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2397 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002398
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002399 /* Starting from the leaf level; for all levels n_h of the tree. */
2400 for (n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++) {
2401 if ((n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON) {
2402 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002403 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002404
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002405 if ((n_ret_value =
2406 check_balance(n_op_mode, p_s_tb, n_h, n_item_num,
2407 n_pos_in_item, p_s_ins_ih,
2408 data)) != CARRY_ON) {
2409 if (n_ret_value == NO_BALANCING_NEEDED) {
2410 /* No balancing for higher levels needed. */
2411 if ((n_ret_value =
2412 get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2413 goto repeat;
2414 }
2415 if (n_h != MAX_HEIGHT - 1)
2416 p_s_tb->insert_size[n_h + 1] = 0;
2417 /* ok, analysis and resource gathering are complete */
2418 break;
2419 }
2420 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002421 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002422
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002423 if ((n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2424 goto repeat;
2425 }
2426
2427 if ((n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON) {
2428 goto repeat; /* No disk space, or schedule occurred and
2429 analysis may be invalid and needs to be redone. */
2430 }
2431
2432 if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h)) {
2433 /* We have a positive insert size but no nodes exist on this
2434 level, this means that we are creating a new root. */
2435
2436 RFALSE(p_s_tb->blknum[n_h] != 1,
2437 "PAP-8350: creating new empty root");
2438
2439 if (n_h < MAX_HEIGHT - 1)
2440 p_s_tb->insert_size[n_h + 1] = 0;
2441 } else if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1)) {
2442 if (p_s_tb->blknum[n_h] > 1) {
2443 /* The tree needs to be grown, so this node S[n_h]
2444 which is the root node is split into two nodes,
2445 and a new node (S[n_h+1]) will be created to
2446 become the root node. */
2447
2448 RFALSE(n_h == MAX_HEIGHT - 1,
2449 "PAP-8355: attempt to create too high of a tree");
2450
2451 p_s_tb->insert_size[n_h + 1] =
2452 (DC_SIZE +
2453 KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) +
2454 DC_SIZE;
2455 } else if (n_h < MAX_HEIGHT - 1)
2456 p_s_tb->insert_size[n_h + 1] = 0;
2457 } else
2458 p_s_tb->insert_size[n_h + 1] =
2459 (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1);
2460 }
2461
2462 if ((n_ret_value = wait_tb_buffers_until_unlocked(p_s_tb)) == CARRY_ON) {
2463 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2464 wait_tb_buffers_run = 1;
2465 n_ret_value = REPEAT_SEARCH;
2466 goto repeat;
2467 } else {
2468 return CARRY_ON;
2469 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002470 } else {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002471 wait_tb_buffers_run = 1;
2472 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002473 }
2474
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002475 repeat:
2476 // fix_nodes was unable to perform its calculation due to
2477 // filesystem got changed under us, lack of free disk space or i/o
2478 // failure. If the first is the case - the search will be
2479 // repeated. For now - free all resources acquired so far except
2480 // for the new allocated nodes
2481 {
2482 int i;
2483
2484 /* Release path buffers. */
2485 if (wait_tb_buffers_run) {
2486 pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path);
2487 } else {
2488 pathrelse(p_s_tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002489 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002490 /* brelse all resources collected for balancing */
2491 for (i = 0; i < MAX_HEIGHT; i++) {
2492 if (wait_tb_buffers_run) {
2493 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2494 p_s_tb->L[i]);
2495 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2496 p_s_tb->R[i]);
2497 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2498 p_s_tb->FL[i]);
2499 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2500 p_s_tb->FR[i]);
2501 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2502 p_s_tb->
2503 CFL[i]);
2504 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2505 p_s_tb->
2506 CFR[i]);
2507 }
2508
2509 brelse(p_s_tb->L[i]);
2510 p_s_tb->L[i] = NULL;
2511 brelse(p_s_tb->R[i]);
2512 p_s_tb->R[i] = NULL;
2513 brelse(p_s_tb->FL[i]);
2514 p_s_tb->FL[i] = NULL;
2515 brelse(p_s_tb->FR[i]);
2516 p_s_tb->FR[i] = NULL;
2517 brelse(p_s_tb->CFL[i]);
2518 p_s_tb->CFL[i] = NULL;
2519 brelse(p_s_tb->CFR[i]);
2520 p_s_tb->CFR[i] = NULL;
2521 }
2522
2523 if (wait_tb_buffers_run) {
2524 for (i = 0; i < MAX_FEB_SIZE; i++) {
2525 if (p_s_tb->FEB[i]) {
2526 reiserfs_restore_prepared_buffer
2527 (p_s_tb->tb_sb, p_s_tb->FEB[i]);
2528 }
2529 }
2530 }
2531 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002532 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002533
2534}
2535
Linus Torvalds1da177e2005-04-16 15:20:36 -07002536/* Anatoly will probably forgive me renaming p_s_tb to tb. I just
2537 wanted to make lines shorter */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002538void unfix_nodes(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002539{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002540 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002541
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002542 /* Release path buffers. */
2543 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002544
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002545 /* brelse all resources collected for balancing */
2546 for (i = 0; i < MAX_HEIGHT; i++) {
2547 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2548 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2549 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2550 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2551 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2552 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002553
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002554 brelse(tb->L[i]);
2555 brelse(tb->R[i]);
2556 brelse(tb->FL[i]);
2557 brelse(tb->FR[i]);
2558 brelse(tb->CFL[i]);
2559 brelse(tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002560 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002561
2562 /* deal with list of allocated (used and unused) nodes */
2563 for (i = 0; i < MAX_FEB_SIZE; i++) {
2564 if (tb->FEB[i]) {
2565 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2566 /* de-allocated block which was not used by balancing and
2567 bforget about buffer for it */
2568 brelse(tb->FEB[i]);
2569 reiserfs_free_block(tb->transaction_handle, NULL,
2570 blocknr, 0);
2571 }
2572 if (tb->used[i]) {
2573 /* release used as new nodes including a new root */
2574 brelse(tb->used[i]);
2575 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002576 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002577
Pekka Enbergd739b422006-02-01 03:06:43 -08002578 kfree(tb->vn_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002579
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002580}