blob: bf5f2cbdb0638cb69fd1d7010bb21740130d2611 [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
Jeff Mahoney0222e652009-03-30 14:02:44 -040033 **
34 **
Linus Torvalds1da177e2005-04-16 15:20:36 -070035 **/
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)
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400138 reiserfs_panic(tb->tb_sb, "vs-8030",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700139 "virtual node space consumed");
140
141 if (!is_affected)
142 /* this is not being changed */
143 continue;
144
145 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
146 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
147 vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
148 }
149 }
150
151 /* virtual inserted item is not defined yet */
152 if (vn->vn_mode == M_INSERT) {
153 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
154
Al Viro9dce07f2008-03-29 03:07:28 +0000155 RFALSE(vn->vn_ins_ih == NULL,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700156 "vs-8040: item header of inserted item is not specified");
157 vi->vi_item_len = tb->insert_size[0];
158 vi->vi_ih = vn->vn_ins_ih;
159 vi->vi_item = vn->vn_data;
160 vi->vi_uarea = vn->vn_free_ptr;
161
162 op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
163 tb->insert_size[0]);
164 }
165
166 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
167 if (tb->CFR[0]) {
168 struct reiserfs_key *key;
169
170 key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]);
171 if (op_is_left_mergeable(key, Sh->b_size)
172 && (vn->vn_mode != M_DELETE
173 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
174 vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
175 VI_TYPE_RIGHT_MERGEABLE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700176
177#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700178 if (op_is_left_mergeable(key, Sh->b_size) &&
179 !(vn->vn_mode != M_DELETE
180 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
181 /* we delete last item and it could be merged with right neighbor's first item */
182 if (!
183 (B_NR_ITEMS(Sh) == 1
184 && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0))
185 && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) {
186 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
187 print_block(Sh, 0, -1, -1);
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400188 reiserfs_panic(tb->tb_sb, "vs-8045",
189 "rdkey %k, affected item==%d "
190 "(mode==%c) Must be %c",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700191 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 */
Jeff Mahoney0222e652009-03-30 14:02:44 -0400380 start_bytes, /* number of first bytes (entries for directory) of start_item-th item
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700381 we do not include into node that is being filled */
Jeff Mahoney0222e652009-03-30 14:02:44 -0400382 end_bytes; /* number of last bytes (entries for directory) of end_item-th item
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700383 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)
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400499 reiserfs_warning(tb->tb_sb, "vs-8111",
500 "split_item_position is out of range");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700501 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)
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400536 reiserfs_warning(tb->tb_sb, "vs-8115",
537 "not directory or indirect item");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700538 }
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,
Jeff Mahoney0222e652009-03-30 14:02:44 -0400572 * where it will later be used by the functions that actually do the balancing.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700573 * 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
Jeff Mahoneya063ae12009-03-30 14:02:48 -0400752static void free_buffers_in_tb(struct tree_balance *tb)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700753{
Jeff Mahoneyee939612009-03-30 14:02:50 -0400754 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755
Jeff Mahoneya063ae12009-03-30 14:02:48 -0400756 pathrelse(tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757
Jeff Mahoneyee939612009-03-30 14:02:50 -0400758 for (i = 0; i < MAX_HEIGHT; i++) {
759 brelse(tb->L[i]);
760 brelse(tb->R[i]);
761 brelse(tb->FL[i]);
762 brelse(tb->FR[i]);
763 brelse(tb->CFL[i]);
764 brelse(tb->CFR[i]);
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -0400765
Jeff Mahoneyee939612009-03-30 14:02:50 -0400766 tb->L[i] = NULL;
767 tb->R[i] = NULL;
768 tb->FL[i] = NULL;
769 tb->FR[i] = NULL;
770 tb->CFL[i] = NULL;
771 tb->CFR[i] = NULL;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700772 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700773}
774
Linus Torvalds1da177e2005-04-16 15:20:36 -0700775/* Get new buffers for storing new nodes that are created while balancing.
776 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
777 * CARRY_ON - schedule didn't occur while the function worked;
778 * NO_DISK_SPACE - no disk space.
779 */
780/* The function is NOT SCHEDULE-SAFE! */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400781static int get_empty_nodes(struct tree_balance *tb, int h)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700782{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400783 struct buffer_head *new_bh,
Jeff Mahoneyee939612009-03-30 14:02:50 -0400784 *Sh = PATH_H_PBUFFER(tb->tb_path, h);
785 b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
786 int counter, number_of_freeblk, amount_needed, /* number of needed empty blocks */
787 retval = CARRY_ON;
Jeff Mahoneya063ae12009-03-30 14:02:48 -0400788 struct super_block *sb = tb->tb_sb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700789
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700790 /* number_of_freeblk is the number of empty blocks which have been
791 acquired for use by the balancing algorithm minus the number of
792 empty blocks used in the previous levels of the analysis,
793 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
794 after empty blocks are acquired, and the balancing analysis is
795 then restarted, amount_needed is the number needed by this level
Jeff Mahoneyee939612009-03-30 14:02:50 -0400796 (h) of the balancing analysis.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700797
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700798 Note that for systems with many processes writing, it would be
799 more layout optimal to calculate the total number needed by all
800 levels and then to run reiserfs_new_blocks to get all of them at once. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700802 /* Initiate number_of_freeblk to the amount acquired prior to the restart of
803 the analysis or 0 if not restarted, then subtract the amount needed
Jeff Mahoneyee939612009-03-30 14:02:50 -0400804 by all of the levels of the tree below h. */
805 /* blknum includes S[h], so we subtract 1 in this calculation */
806 for (counter = 0, number_of_freeblk = tb->cur_blknum;
807 counter < h; counter++)
808 number_of_freeblk -=
809 (tb->blknum[counter]) ? (tb->blknum[counter] -
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700810 1) : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700811
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700812 /* Allocate missing empty blocks. */
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400813 /* if Sh == 0 then we are getting a new root */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400814 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700815 /* Amount_needed = the amount that we need more than the amount that we have. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400816 if (amount_needed > number_of_freeblk)
817 amount_needed -= number_of_freeblk;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700818 else /* If we have enough already then there is nothing to do. */
819 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700820
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700821 /* No need to check quota - is not allocated for blocks used for formatted nodes */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400822 if (reiserfs_new_form_blocknrs(tb, blocknrs,
823 amount_needed) == NO_DISK_SPACE)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700824 return NO_DISK_SPACE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700825
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700826 /* for each blocknumber we just got, get a buffer and stick it on FEB */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400827 for (blocknr = blocknrs, counter = 0;
828 counter < amount_needed; blocknr++, counter++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700829
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400830 RFALSE(!*blocknr,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700831 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400833 new_bh = sb_getblk(sb, *blocknr);
834 RFALSE(buffer_dirty(new_bh) ||
835 buffer_journaled(new_bh) ||
836 buffer_journal_dirty(new_bh),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700837 "PAP-8140: journlaled or dirty buffer %b for the new block",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400838 new_bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700839
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700840 /* Put empty buffers into the array. */
Jeff Mahoneya063ae12009-03-30 14:02:48 -0400841 RFALSE(tb->FEB[tb->cur_blknum],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700842 "PAP-8141: busy slot for new buffer");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700843
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400844 set_buffer_journal_new(new_bh);
845 tb->FEB[tb->cur_blknum++] = new_bh;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700846 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700847
Jeff Mahoneyee939612009-03-30 14:02:50 -0400848 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
849 retval = REPEAT_SEARCH;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700850
Jeff Mahoneyee939612009-03-30 14:02:50 -0400851 return retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852}
853
Linus Torvalds1da177e2005-04-16 15:20:36 -0700854/* Get free space of the left neighbor, which is stored in the parent
855 * node of the left neighbor. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700856static int get_lfree(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700857{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700858 struct buffer_head *l, *f;
859 int order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860
Al Viro9dce07f2008-03-29 03:07:28 +0000861 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
862 (l = tb->FL[h]) == NULL)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700863 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700864
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700865 if (f == l)
866 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
867 else {
868 order = B_NR_ITEMS(l);
869 f = l;
870 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700872 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700873}
874
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875/* Get free space of the right neighbor,
876 * which is stored in the parent node of the right neighbor.
877 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700878static int get_rfree(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700879{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700880 struct buffer_head *r, *f;
881 int order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700882
Al Viro9dce07f2008-03-29 03:07:28 +0000883 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
884 (r = tb->FR[h]) == NULL)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700885 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700886
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700887 if (f == r)
888 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
889 else {
890 order = 0;
891 f = r;
892 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700893
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700894 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895
896}
897
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898/* Check whether left neighbor is in memory. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400899static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700900{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400901 struct buffer_head *father, *left;
Jeff Mahoneya063ae12009-03-30 14:02:48 -0400902 struct super_block *sb = tb->tb_sb;
Jeff Mahoneyee939612009-03-30 14:02:50 -0400903 b_blocknr_t left_neighbor_blocknr;
904 int left_neighbor_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905
Jeff Mahoneya063ae12009-03-30 14:02:48 -0400906 /* Father of the left neighbor does not exist. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400907 if (!tb->FL[h])
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700908 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700909
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700910 /* Calculate father of the node to be balanced. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400911 father = PATH_H_PBUFFER(tb->tb_path, h + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700912
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400913 RFALSE(!father ||
914 !B_IS_IN_TREE(father) ||
Jeff Mahoneyee939612009-03-30 14:02:50 -0400915 !B_IS_IN_TREE(tb->FL[h]) ||
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400916 !buffer_uptodate(father) ||
Jeff Mahoneyee939612009-03-30 14:02:50 -0400917 !buffer_uptodate(tb->FL[h]),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700918 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
Jeff Mahoneyee939612009-03-30 14:02:50 -0400919 father, tb->FL[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700920
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700921 /* Get position of the pointer to the left neighbor into the left father. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400922 left_neighbor_position = (father == tb->FL[h]) ?
923 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700924 /* Get left neighbor block number. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400925 left_neighbor_blocknr =
926 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700927 /* Look for the left neighbor in the cache. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400928 if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700929
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700930 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
931 "vs-8170: left neighbor (%b %z) is not in the tree",
932 left, left);
933 put_bh(left);
934 return 1;
935 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700937 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700938}
939
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940#define LEFT_PARENTS 'l'
941#define RIGHT_PARENTS 'r'
942
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400943static void decrement_key(struct cpu_key *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700944{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700945 // call item specific function for this key
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400946 item_ops[cpu_key_k_type(key)]->decrement_key(key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700947}
948
Linus Torvalds1da177e2005-04-16 15:20:36 -0700949/* Calculate far left/right parent of the left/right neighbor of the current node, that
950 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
951 * Calculate left/right common parent of the current node and L[h]/R[h].
952 * Calculate left/right delimiting key position.
953 * Returns: PATH_INCORRECT - path in the tree is not correct;
954 SCHEDULE_OCCURRED - schedule occurred while the function worked;
955 * CARRY_ON - schedule didn't occur while the function worked;
956 */
Jeff Mahoneya063ae12009-03-30 14:02:48 -0400957static int get_far_parent(struct tree_balance *tb,
Jeff Mahoneyee939612009-03-30 14:02:50 -0400958 int h,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400959 struct buffer_head **pfather,
960 struct buffer_head **pcom_father, char c_lr_par)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700961{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400962 struct buffer_head *parent;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700963 INITIALIZE_PATH(s_path_to_neighbor_father);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400964 struct treepath *path = tb->tb_path;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700965 struct cpu_key s_lr_father_key;
Jeff Mahoneyee939612009-03-30 14:02:50 -0400966 int counter,
967 position = INT_MAX,
968 first_last_position = 0,
969 path_offset = PATH_H_PATH_OFFSET(path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970
Jeff Mahoneyee939612009-03-30 14:02:50 -0400971 /* Starting from F[h] go upwards in the tree, and look for the common
972 ancestor of F[h], and its neighbor l/r, that should be obtained. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973
Jeff Mahoneyee939612009-03-30 14:02:50 -0400974 counter = path_offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975
Jeff Mahoneyee939612009-03-30 14:02:50 -0400976 RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700977 "PAP-8180: invalid path length");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700978
Jeff Mahoneyee939612009-03-30 14:02:50 -0400979 for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700980 /* Check whether parent of the current buffer in the path is really parent in the tree. */
981 if (!B_IS_IN_TREE
Jeff Mahoneyee939612009-03-30 14:02:50 -0400982 (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700983 return REPEAT_SEARCH;
984 /* Check whether position in the parent is correct. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400985 if ((position =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400986 PATH_OFFSET_POSITION(path,
Jeff Mahoneyee939612009-03-30 14:02:50 -0400987 counter - 1)) >
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400988 B_NR_ITEMS(parent))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700989 return REPEAT_SEARCH;
990 /* Check whether parent at the path really points to the child. */
Jeff Mahoneyee939612009-03-30 14:02:50 -0400991 if (B_N_CHILD_NUM(parent, position) !=
992 PATH_OFFSET_PBUFFER(path, counter)->b_blocknr)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700993 return REPEAT_SEARCH;
994 /* Return delimiting key if position in the parent is not equal to first/last one. */
995 if (c_lr_par == RIGHT_PARENTS)
Jeff Mahoneyee939612009-03-30 14:02:50 -0400996 first_last_position = B_NR_ITEMS(parent);
997 if (position != first_last_position) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -0400998 *pcom_father = parent;
999 get_bh(*pcom_father);
1000 /*(*pcom_father = parent)->b_count++; */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001001 break;
1002 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001003 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001004
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001005 /* if we are in the root of the tree, then there is no common father */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001006 if (counter == FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001007 /* Check whether first buffer in the path is the root of the tree. */
1008 if (PATH_OFFSET_PBUFFER
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001009 (tb->tb_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001010 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001011 SB_ROOT_BLOCK(tb->tb_sb)) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001012 *pfather = *pcom_father = NULL;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001013 return CARRY_ON;
1014 }
1015 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001017
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001018 RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001019 "PAP-8185: (%b %z) level too small",
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001020 *pcom_father, *pcom_father);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001022 /* Check whether the common parent is locked. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001023
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001024 if (buffer_locked(*pcom_father)) {
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02001025
1026 /* Release the write lock while the buffer is busy */
1027 reiserfs_write_unlock(tb->tb_sb);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001028 __wait_on_buffer(*pcom_father);
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02001029 reiserfs_write_lock(tb->tb_sb);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001030 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001031 brelse(*pcom_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001032 return REPEAT_SEARCH;
1033 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001035
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001036 /* So, we got common parent of the current node and its left/right neighbor.
1037 Now we are geting the parent of the left/right neighbor. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001038
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001039 /* Form key to get parent of the left/right neighbor. */
1040 le_key2cpu_key(&s_lr_father_key,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001041 B_N_PDELIM_KEY(*pcom_father,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001042 (c_lr_par ==
Jeff Mahoneyee939612009-03-30 14:02:50 -04001043 LEFT_PARENTS) ? (tb->lkey[h - 1] =
1044 position -
1045 1) : (tb->rkey[h -
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001046 1] =
Jeff Mahoneyee939612009-03-30 14:02:50 -04001047 position)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001048
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001049 if (c_lr_par == LEFT_PARENTS)
1050 decrement_key(&s_lr_father_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001052 if (search_by_key
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001053 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001054 h + 1) == IO_ERROR)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001055 // path is released
1056 return IO_ERROR;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001057
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001058 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -04001059 pathrelse(&s_path_to_neighbor_father);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001060 brelse(*pcom_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001061 return REPEAT_SEARCH;
1062 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001063
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001064 *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001065
Jeff Mahoneyee939612009-03-30 14:02:50 -04001066 RFALSE(B_LEVEL(*pfather) != h + 1,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001067 "PAP-8190: (%b %z) level too small", *pfather, *pfather);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001068 RFALSE(s_path_to_neighbor_father.path_length <
1069 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1070
1071 s_path_to_neighbor_father.path_length--;
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -04001072 pathrelse(&s_path_to_neighbor_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001073 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001074}
1075
Jeff Mahoneyee939612009-03-30 14:02:50 -04001076/* Get parents of neighbors of node in the path(S[path_offset]) and common parents of
1077 * S[path_offset] and L[path_offset]/R[path_offset]: F[path_offset], FL[path_offset],
1078 * FR[path_offset], CFL[path_offset], CFR[path_offset].
1079 * Calculate numbers of left and right delimiting keys position: lkey[path_offset], rkey[path_offset].
Linus Torvalds1da177e2005-04-16 15:20:36 -07001080 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1081 * CARRY_ON - schedule didn't occur while the function worked;
1082 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001083static int get_parents(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001084{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001085 struct treepath *path = tb->tb_path;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001086 int position,
1087 ret,
1088 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001089 struct buffer_head *curf, *curcf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001091 /* Current node is the root of the tree or will be root of the tree */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001092 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001093 /* The root can not have parents.
1094 Release nodes which previously were obtained as parents of the current node neighbors. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001095 brelse(tb->FL[h]);
1096 brelse(tb->CFL[h]);
1097 brelse(tb->FR[h]);
1098 brelse(tb->CFR[h]);
1099 tb->FL[h] = NULL;
1100 tb->CFL[h] = NULL;
1101 tb->FR[h] = NULL;
1102 tb->CFR[h] = NULL;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001103 return CARRY_ON;
1104 }
1105
Jeff Mahoneyee939612009-03-30 14:02:50 -04001106 /* Get parent FL[path_offset] of L[path_offset]. */
1107 position = PATH_OFFSET_POSITION(path, path_offset - 1);
1108 if (position) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001109 /* Current node is not the first child of its parent. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001110 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1111 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001112 get_bh(curf);
1113 get_bh(curf);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001114 tb->lkey[h] = position - 1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001115 } else {
Jeff Mahoneyee939612009-03-30 14:02:50 -04001116 /* Calculate current parent of L[path_offset], which is the left neighbor of the current node.
1117 Calculate current common parent of L[path_offset] and the current node. Note that
1118 CFL[path_offset] not equal FL[path_offset] and CFL[path_offset] not equal F[path_offset].
1119 Calculate lkey[path_offset]. */
1120 if ((ret = get_far_parent(tb, h + 1, &curf,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001121 &curcf,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001122 LEFT_PARENTS)) != CARRY_ON)
Jeff Mahoneyee939612009-03-30 14:02:50 -04001123 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001124 }
1125
Jeff Mahoneyee939612009-03-30 14:02:50 -04001126 brelse(tb->FL[h]);
1127 tb->FL[h] = curf; /* New initialization of FL[h]. */
1128 brelse(tb->CFL[h]);
1129 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001131 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1132 (curcf && !B_IS_IN_TREE(curcf)),
1133 "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001134
Jeff Mahoneyee939612009-03-30 14:02:50 -04001135/* Get parent FR[h] of R[h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001136
Jeff Mahoneyee939612009-03-30 14:02:50 -04001137/* Current node is the last child of F[h]. FR[h] != F[h]. */
1138 if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {
1139/* Calculate current parent of R[h], which is the right neighbor of F[h].
1140 Calculate current common parent of R[h] and current node. Note that CFR[h]
1141 not equal FR[path_offset] and CFR[h] not equal F[h]. */
1142 if ((ret =
1143 get_far_parent(tb, h + 1, &curf, &curcf,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001144 RIGHT_PARENTS)) != CARRY_ON)
Jeff Mahoneyee939612009-03-30 14:02:50 -04001145 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001146 } else {
Jeff Mahoneyee939612009-03-30 14:02:50 -04001147/* Current node is not the last child of its parent F[h]. */
1148 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1149 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001150 get_bh(curf);
1151 get_bh(curf);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001152 tb->rkey[h] = position;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001153 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154
Jeff Mahoneyee939612009-03-30 14:02:50 -04001155 brelse(tb->FR[h]);
1156 /* New initialization of FR[path_offset]. */
1157 tb->FR[h] = curf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158
Jeff Mahoneyee939612009-03-30 14:02:50 -04001159 brelse(tb->CFR[h]);
1160 /* New initialization of CFR[path_offset]. */
1161 tb->CFR[h] = curcf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001162
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001163 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1164 (curcf && !B_IS_IN_TREE(curcf)),
1165 "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001166
1167 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001168}
1169
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170/* it is possible to remove node as result of shiftings to
1171 neighbors even when we insert or paste item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001172static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1173 struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001174{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001175 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1176 int levbytes = tb->insert_size[h];
1177 struct item_head *ih;
1178 struct reiserfs_key *r_key = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001180 ih = B_N_PITEM_HEAD(Sh, 0);
1181 if (tb->CFR[h])
1182 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
1183
1184 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1185 /* shifting may merge items which might save space */
1186 -
1187 ((!h
1188 && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1189 -
1190 ((!h && r_key
1191 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1192 + ((h) ? KEY_SIZE : 0)) {
1193 /* node can not be removed */
1194 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1195 if (!h)
1196 tb->s0num =
1197 B_NR_ITEMS(Sh) +
1198 ((mode == M_INSERT) ? 1 : 0);
1199 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1200 return NO_BALANCING_NEEDED;
1201 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001202 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001203 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1204 return !NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205}
1206
Linus Torvalds1da177e2005-04-16 15:20:36 -07001207/* Check whether current node S[h] is balanced when increasing its size by
1208 * Inserting or Pasting.
1209 * Calculate parameters for balancing for current level h.
1210 * Parameters:
1211 * tb tree_balance structure;
1212 * h current level of the node;
1213 * inum item number in S[h];
1214 * mode i - insert, p - paste;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001215 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001216 * 0 - balancing for higher levels needed;
1217 * -1 - no balancing for higher levels needed;
1218 * -2 - no disk space.
1219 */
1220/* ip means Inserting or Pasting */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001221static int ip_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001223 struct virtual_node *vn = tb->tb_vn;
1224 int levbytes, /* Number of bytes that must be inserted into (value
1225 is negative if bytes are deleted) buffer which
1226 contains node being balanced. The mnemonic is
1227 that the attempted change in node space used level
1228 is levbytes bytes. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001229 ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001230
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001231 int lfree, sfree, rfree /* free space in L, S and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001232
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001233 /* nver is short for number of vertixes, and lnver is the number if
1234 we shift to the left, rnver is the number if we shift to the
1235 right, and lrnver is the number if we shift in both directions.
1236 The goal is to minimize first the number of vertixes, and second,
1237 the number of vertixes whose contents are changed by shifting,
1238 and third the number of uncached vertixes whose contents are
1239 changed by shifting and must be read from disk. */
1240 int nver, lnver, rnver, lrnver;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001241
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001242 /* used at leaf level only, S0 = S[0] is the node being balanced,
1243 sInum [ I = 0,1,2 ] is the number of items that will
1244 remain in node SI after balancing. S1 and S2 are new
1245 nodes that might be created. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001246
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001247 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
1248 where 4th parameter is s1bytes and 5th - s2bytes
Linus Torvalds1da177e2005-04-16 15:20:36 -07001249 */
Jeff Mahoney0222e652009-03-30 14:02:44 -04001250 short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001251 0,1 - do not shift and do not shift but bottle
1252 2 - shift only whole item to left
1253 3 - shift to left and bottle as much as possible
1254 4,5 - shift to right (whole items and as much as possible
1255 6,7 - shift to both directions (whole items and as much as possible)
1256 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001257
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001258 /* Sh is the node whose balance is currently being checked */
1259 struct buffer_head *Sh;
1260
1261 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1262 levbytes = tb->insert_size[h];
1263
1264 /* Calculate balance parameters for creating new root. */
1265 if (!Sh) {
1266 if (!h)
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001267 reiserfs_panic(tb->tb_sb, "vs-8210",
1268 "S[0] can not be 0");
Jeff Mahoneyee939612009-03-30 14:02:50 -04001269 switch (ret = get_empty_nodes(tb, h)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001270 case CARRY_ON:
1271 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1272 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1273
1274 case NO_DISK_SPACE:
1275 case REPEAT_SEARCH:
Jeff Mahoneyee939612009-03-30 14:02:50 -04001276 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001277 default:
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001278 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1279 "return value of get_empty_nodes");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001280 }
1281 }
1282
Jeff Mahoneyee939612009-03-30 14:02:50 -04001283 if ((ret = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */
1284 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001285
1286 sfree = B_FREE_SPACE(Sh);
1287
1288 /* get free space of neighbors */
1289 rfree = get_rfree(tb, h);
1290 lfree = get_lfree(tb, h);
1291
1292 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1293 NO_BALANCING_NEEDED)
1294 /* and new item fits into node S[h] without any shifting */
1295 return NO_BALANCING_NEEDED;
1296
1297 create_virtual_node(tb, h);
1298
Jeff Mahoney0222e652009-03-30 14:02:44 -04001299 /*
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001300 determine maximal number of items we can shift to the left neighbor (in tb structure)
1301 and the maximal number of bytes that can flow to the left neighbor
1302 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1303 */
1304 check_left(tb, h, lfree);
1305
1306 /*
1307 determine maximal number of items we can shift to the right neighbor (in tb structure)
1308 and the maximal number of bytes that can flow to the right neighbor
1309 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1310 */
1311 check_right(tb, h, rfree);
1312
1313 /* all contents of internal node S[h] can be moved into its
1314 neighbors, S[h] will be removed after balancing */
1315 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1316 int to_r;
1317
1318 /* Since we are working on internal nodes, and our internal
1319 nodes have fixed size entries, then we can balance by the
1320 number of items rather than the space they consume. In this
1321 routine we set the left node equal to the right node,
1322 allowing a difference of less than or equal to 1 child
1323 pointer. */
1324 to_r =
1325 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1326 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1327 tb->rnum[h]);
1328 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1329 -1, -1);
1330 return CARRY_ON;
1331 }
1332
1333 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1334 RFALSE(h &&
1335 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1336 tb->rnum[h] >= vn->vn_nr_item + 1),
1337 "vs-8220: tree is not balanced on internal level");
1338 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1339 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1340 "vs-8225: tree is not balanced on leaf level");
1341
1342 /* all contents of S[0] can be moved into its neighbors
1343 S[0] will be removed after balancing. */
1344 if (!h && is_leaf_removable(tb))
1345 return CARRY_ON;
1346
1347 /* why do we perform this check here rather than earlier??
1348 Answer: we can win 1 node in some cases above. Moreover we
1349 checked it above, when we checked, that S[0] is not removable
1350 in principle */
1351 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1352 if (!h)
1353 tb->s0num = vn->vn_nr_item;
1354 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1355 return NO_BALANCING_NEEDED;
1356 }
1357
1358 {
1359 int lpar, rpar, nset, lset, rset, lrset;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001360 /*
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001361 * regular overflowing of the node
1362 */
1363
Jeff Mahoney0222e652009-03-30 14:02:44 -04001364 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001365 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
Jeff Mahoney0222e652009-03-30 14:02:44 -04001366 nset, lset, rset, lrset - shows, whether flowing items give better packing
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001367 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001368#define FLOW 1
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001369#define NO_FLOW 0 /* do not any splitting */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001370
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001371 /* we choose one the following */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372#define NOTHING_SHIFT_NO_FLOW 0
1373#define NOTHING_SHIFT_FLOW 5
1374#define LEFT_SHIFT_NO_FLOW 10
1375#define LEFT_SHIFT_FLOW 15
1376#define RIGHT_SHIFT_NO_FLOW 20
1377#define RIGHT_SHIFT_FLOW 25
1378#define LR_SHIFT_NO_FLOW 30
1379#define LR_SHIFT_FLOW 35
1380
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001381 lpar = tb->lnum[h];
1382 rpar = tb->rnum[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001383
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001384 /* calculate number of blocks S[h] must be split into when
1385 nothing is shifted to the neighbors,
1386 as well as number of items in each part of the split node (s012 numbers),
1387 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1388 nset = NOTHING_SHIFT_NO_FLOW;
1389 nver = get_num_ver(vn->vn_mode, tb, h,
1390 0, -1, h ? vn->vn_nr_item : 0, -1,
1391 snum012, NO_FLOW);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001392
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001393 if (!h) {
1394 int nver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001395
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001396 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1397 nver1 = get_num_ver(vn->vn_mode, tb, h,
1398 0, -1, 0, -1,
1399 snum012 + NOTHING_SHIFT_FLOW, FLOW);
1400 if (nver > nver1)
1401 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1402 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001403
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001404 /* calculate number of blocks S[h] must be split into when
1405 l_shift_num first items and l_shift_bytes of the right most
1406 liquid item to be shifted are shifted to the left neighbor,
1407 as well as number of items in each part of the splitted node (s012 numbers),
1408 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1409 */
1410 lset = LEFT_SHIFT_NO_FLOW;
1411 lnver = get_num_ver(vn->vn_mode, tb, h,
1412 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1413 -1, h ? vn->vn_nr_item : 0, -1,
1414 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1415 if (!h) {
1416 int lnver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001417
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001418 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1419 lpar -
1420 ((tb->lbytes != -1) ? 1 : 0),
1421 tb->lbytes, 0, -1,
1422 snum012 + LEFT_SHIFT_FLOW, FLOW);
1423 if (lnver > lnver1)
1424 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1425 }
1426
1427 /* calculate number of blocks S[h] must be split into when
1428 r_shift_num first items and r_shift_bytes of the left most
1429 liquid item to be shifted are shifted to the right neighbor,
1430 as well as number of items in each part of the splitted node (s012 numbers),
1431 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1432 */
1433 rset = RIGHT_SHIFT_NO_FLOW;
1434 rnver = get_num_ver(vn->vn_mode, tb, h,
1435 0, -1,
1436 h ? (vn->vn_nr_item - rpar) : (rpar -
1437 ((tb->
1438 rbytes !=
1439 -1) ? 1 :
1440 0)), -1,
1441 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1442 if (!h) {
1443 int rnver1;
1444
1445 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1446 0, -1,
1447 (rpar -
1448 ((tb->rbytes != -1) ? 1 : 0)),
1449 tb->rbytes,
1450 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1451
1452 if (rnver > rnver1)
1453 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1454 }
1455
1456 /* calculate number of blocks S[h] must be split into when
1457 items are shifted in both directions,
1458 as well as number of items in each part of the splitted node (s012 numbers),
1459 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1460 */
1461 lrset = LR_SHIFT_NO_FLOW;
1462 lrnver = get_num_ver(vn->vn_mode, tb, h,
1463 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1464 -1,
1465 h ? (vn->vn_nr_item - rpar) : (rpar -
1466 ((tb->
1467 rbytes !=
1468 -1) ? 1 :
1469 0)), -1,
1470 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1471 if (!h) {
1472 int lrnver1;
1473
1474 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1475 lpar -
1476 ((tb->lbytes != -1) ? 1 : 0),
1477 tb->lbytes,
1478 (rpar -
1479 ((tb->rbytes != -1) ? 1 : 0)),
1480 tb->rbytes,
1481 snum012 + LR_SHIFT_FLOW, FLOW);
1482 if (lrnver > lrnver1)
1483 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1484 }
1485
1486 /* Our general shifting strategy is:
1487 1) to minimized number of new nodes;
1488 2) to minimized number of neighbors involved in shifting;
1489 3) to minimized number of disk reads; */
1490
1491 /* we can win TWO or ONE nodes by shifting in both directions */
1492 if (lrnver < lnver && lrnver < rnver) {
1493 RFALSE(h &&
1494 (tb->lnum[h] != 1 ||
1495 tb->rnum[h] != 1 ||
1496 lrnver != 1 || rnver != 2 || lnver != 2
1497 || h != 1), "vs-8230: bad h");
1498 if (lrset == LR_SHIFT_FLOW)
1499 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1500 lrnver, snum012 + lrset,
1501 tb->lbytes, tb->rbytes);
1502 else
1503 set_parameters(tb, h,
1504 tb->lnum[h] -
1505 ((tb->lbytes == -1) ? 0 : 1),
1506 tb->rnum[h] -
1507 ((tb->rbytes == -1) ? 0 : 1),
1508 lrnver, snum012 + lrset, -1, -1);
1509
1510 return CARRY_ON;
1511 }
1512
1513 /* if shifting doesn't lead to better packing then don't shift */
1514 if (nver == lrnver) {
1515 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1516 -1);
1517 return CARRY_ON;
1518 }
1519
1520 /* now we know that for better packing shifting in only one
1521 direction either to the left or to the right is required */
1522
1523 /* if shifting to the left is better than shifting to the right */
1524 if (lnver < rnver) {
1525 SET_PAR_SHIFT_LEFT;
1526 return CARRY_ON;
1527 }
1528
1529 /* if shifting to the right is better than shifting to the left */
1530 if (lnver > rnver) {
1531 SET_PAR_SHIFT_RIGHT;
1532 return CARRY_ON;
1533 }
1534
1535 /* now shifting in either direction gives the same number
1536 of nodes and we can make use of the cached neighbors */
1537 if (is_left_neighbor_in_cache(tb, h)) {
1538 SET_PAR_SHIFT_LEFT;
1539 return CARRY_ON;
1540 }
1541
1542 /* shift to the right independently on whether the right neighbor in cache or not */
1543 SET_PAR_SHIFT_RIGHT;
1544 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001545 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001546}
1547
Linus Torvalds1da177e2005-04-16 15:20:36 -07001548/* Check whether current node S[h] is balanced when Decreasing its size by
1549 * Deleting or Cutting for INTERNAL node of S+tree.
1550 * Calculate parameters for balancing for current level h.
1551 * Parameters:
1552 * tb tree_balance structure;
1553 * h current level of the node;
1554 * inum item number in S[h];
1555 * mode i - insert, p - paste;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001556 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001557 * 0 - balancing for higher levels needed;
1558 * -1 - no balancing for higher levels needed;
1559 * -2 - no disk space.
1560 *
1561 * Note: Items of internal nodes have fixed size, so the balance condition for
1562 * the internal part of S+tree is as for the B-trees.
1563 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001564static int dc_check_balance_internal(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001565{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001566 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001567
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001568 /* Sh is the node whose balance is currently being checked,
1569 and Fh is its father. */
1570 struct buffer_head *Sh, *Fh;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001571 int maxsize, ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001572 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001573
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001574 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1575 Fh = PATH_H_PPARENT(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001576
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001577 maxsize = MAX_CHILD_SIZE(Sh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001578
1579/* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1580/* new_nr_item = number of items node would have if operation is */
1581/* performed without balancing (new_nr_item); */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001582 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001583
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001584 if (!Fh) { /* S[h] is the root. */
1585 if (vn->vn_nr_item > 0) {
1586 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1587 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1588 }
1589 /* new_nr_item == 0.
1590 * Current root will be deleted resulting in
1591 * decrementing the tree height. */
1592 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1593 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001594 }
1595
Jeff Mahoneyee939612009-03-30 14:02:50 -04001596 if ((ret = get_parents(tb, h)) != CARRY_ON)
1597 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001598
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001599 /* get free space of neighbors */
1600 rfree = get_rfree(tb, h);
1601 lfree = get_lfree(tb, h);
1602
1603 /* determine maximal number of items we can fit into neighbors */
1604 check_left(tb, h, lfree);
1605 check_right(tb, h, rfree);
1606
1607 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
1608 * In this case we balance only if it leads to better packing. */
1609 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
1610 * which is impossible with greater values of new_nr_item. */
1611 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1612 /* All contents of S[h] can be moved to L[h]. */
1613 int n;
1614 int order_L;
1615
1616 order_L =
1617 ((n =
1618 PATH_H_B_ITEM_ORDER(tb->tb_path,
1619 h)) ==
1620 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1621 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1622 (DC_SIZE + KEY_SIZE);
1623 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1624 -1);
1625 return CARRY_ON;
1626 }
1627
1628 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1629 /* All contents of S[h] can be moved to R[h]. */
1630 int n;
1631 int order_R;
1632
1633 order_R =
1634 ((n =
1635 PATH_H_B_ITEM_ORDER(tb->tb_path,
1636 h)) ==
1637 B_NR_ITEMS(Fh)) ? 0 : n + 1;
1638 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1639 (DC_SIZE + KEY_SIZE);
1640 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1641 -1);
1642 return CARRY_ON;
1643 }
1644 }
1645
1646 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1647 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1648 int to_r;
1649
1650 to_r =
1651 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1652 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1653 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1654 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1655 0, NULL, -1, -1);
1656 return CARRY_ON;
1657 }
1658
1659 /* Balancing does not lead to better packing. */
1660 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1661 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001662 }
1663
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001664 /* Current node contain insufficient number of items. Balancing is required. */
1665 /* Check whether we can merge S[h] with left neighbor. */
1666 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1667 if (is_left_neighbor_in_cache(tb, h)
1668 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1669 int n;
1670 int order_L;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001671
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001672 order_L =
1673 ((n =
1674 PATH_H_B_ITEM_ORDER(tb->tb_path,
1675 h)) ==
1676 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1677 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1678 KEY_SIZE);
1679 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1680 return CARRY_ON;
1681 }
1682
1683 /* Check whether we can merge S[h] with right neighbor. */
1684 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1685 int n;
1686 int order_R;
1687
1688 order_R =
1689 ((n =
1690 PATH_H_B_ITEM_ORDER(tb->tb_path,
1691 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1692 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1693 KEY_SIZE);
1694 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1695 return CARRY_ON;
1696 }
1697
1698 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1699 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1700 int to_r;
1701
1702 to_r =
1703 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1704 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1705 tb->rnum[h]);
1706 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1707 -1, -1);
1708 return CARRY_ON;
1709 }
1710
1711 /* For internal nodes try to borrow item from a neighbor */
1712 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1713
1714 /* Borrow one or two items from caching neighbor */
1715 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1716 int from_l;
1717
1718 from_l =
1719 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1720 1) / 2 - (vn->vn_nr_item + 1);
1721 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1722 return CARRY_ON;
1723 }
1724
1725 set_parameters(tb, h, 0,
1726 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1727 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001728 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001729}
1730
Linus Torvalds1da177e2005-04-16 15:20:36 -07001731/* Check whether current node S[h] is balanced when Decreasing its size by
1732 * Deleting or Truncating for LEAF node of S+tree.
1733 * Calculate parameters for balancing for current level h.
1734 * Parameters:
1735 * tb tree_balance structure;
1736 * h current level of the node;
1737 * inum item number in S[h];
1738 * mode i - insert, p - paste;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001739 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001740 * 0 - balancing for higher levels needed;
1741 * -1 - no balancing for higher levels needed;
1742 * -2 - no disk space.
1743 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001744static int dc_check_balance_leaf(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001745{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001746 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001747
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001748 /* Number of bytes that must be deleted from
1749 (value is negative if bytes are deleted) buffer which
1750 contains node being balanced. The mnemonic is that the
1751 attempted change in node space used level is levbytes bytes. */
1752 int levbytes;
1753 /* the maximal item size */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001754 int maxsize, ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001755 /* S0 is the node whose balance is currently being checked,
1756 and F0 is its father. */
1757 struct buffer_head *S0, *F0;
1758 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001759
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001760 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1761 F0 = PATH_H_PPARENT(tb->tb_path, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001762
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001763 levbytes = tb->insert_size[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001764
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001765 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001766
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001767 if (!F0) { /* S[0] is the root now. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001768
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001769 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1770 "vs-8240: attempt to create empty buffer tree");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001771
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001772 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1773 return NO_BALANCING_NEEDED;
1774 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001775
Jeff Mahoneyee939612009-03-30 14:02:50 -04001776 if ((ret = get_parents(tb, h)) != CARRY_ON)
1777 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001778
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001779 /* get free space of neighbors */
1780 rfree = get_rfree(tb, h);
1781 lfree = get_lfree(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001782
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001783 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001784
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001785 /* if 3 leaves can be merge to one, set parameters and return */
1786 if (are_leaves_removable(tb, lfree, rfree))
1787 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001788
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001789 /* determine maximal number of items we can shift to the left/right neighbor
1790 and the maximal number of bytes that can flow to the left/right neighbor
1791 from the left/right most liquid item that cannot be shifted from S[0] entirely
1792 */
1793 check_left(tb, h, lfree);
1794 check_right(tb, h, rfree);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001795
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001796 /* check whether we can merge S with left neighbor. */
1797 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1798 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 */
1799 !tb->FR[h]) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001800
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001801 RFALSE(!tb->FL[h],
1802 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001803
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001804 /* set parameter to merge S[0] with its left neighbor */
1805 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1806 return CARRY_ON;
1807 }
1808
1809 /* check whether we can merge S[0] with right neighbor. */
1810 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1811 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
1812 return CARRY_ON;
1813 }
1814
1815 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1816 if (is_leaf_removable(tb))
1817 return CARRY_ON;
1818
1819 /* Balancing is not required. */
1820 tb->s0num = vn->vn_nr_item;
1821 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1822 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001823}
1824
Linus Torvalds1da177e2005-04-16 15:20:36 -07001825/* Check whether current node S[h] is balanced when Decreasing its size by
1826 * Deleting or Cutting.
1827 * Calculate parameters for balancing for current level h.
1828 * Parameters:
1829 * tb tree_balance structure;
1830 * h current level of the node;
1831 * inum item number in S[h];
1832 * mode d - delete, c - cut.
Jeff Mahoney0222e652009-03-30 14:02:44 -04001833 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001834 * 0 - balancing for higher levels needed;
1835 * -1 - no balancing for higher levels needed;
1836 * -2 - no disk space.
1837 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001838static int dc_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001839{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001840 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1841 "vs-8250: S is not initialized");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001842
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001843 if (h)
1844 return dc_check_balance_internal(tb, h);
1845 else
1846 return dc_check_balance_leaf(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001847}
1848
Linus Torvalds1da177e2005-04-16 15:20:36 -07001849/* Check whether current node S[h] is balanced.
1850 * Calculate parameters for balancing for current level h.
1851 * Parameters:
1852 *
1853 * tb tree_balance structure:
1854 *
1855 * tb is a large structure that must be read about in the header file
1856 * at the same time as this procedure if the reader is to successfully
1857 * understand this procedure
1858 *
1859 * h current level of the node;
1860 * inum item number in S[h];
1861 * mode i - insert, p - paste, d - delete, c - cut.
Jeff Mahoney0222e652009-03-30 14:02:44 -04001862 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001863 * 0 - balancing for higher levels needed;
1864 * -1 - no balancing for higher levels needed;
1865 * -2 - no disk space.
1866 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001867static int check_balance(int mode,
1868 struct tree_balance *tb,
1869 int h,
1870 int inum,
1871 int pos_in_item,
1872 struct item_head *ins_ih, const void *data)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001873{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001874 struct virtual_node *vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001875
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001876 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
1877 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
1878 vn->vn_mode = mode;
1879 vn->vn_affected_item_num = inum;
1880 vn->vn_pos_in_item = pos_in_item;
1881 vn->vn_ins_ih = ins_ih;
1882 vn->vn_data = data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001883
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001884 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1885 "vs-8255: ins_ih can not be 0 in insert mode");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001886
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001887 if (tb->insert_size[h] > 0)
1888 /* Calculate balance parameters when size of node is increasing. */
1889 return ip_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001890
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001891 /* Calculate balance parameters when size of node is decreasing. */
1892 return dc_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001893}
1894
Linus Torvalds1da177e2005-04-16 15:20:36 -07001895/* Check whether parent at the path is the really parent of the current node.*/
Jeff Mahoneyee939612009-03-30 14:02:50 -04001896static int get_direct_parent(struct tree_balance *tb, int h)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001897{
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001898 struct buffer_head *bh;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001899 struct treepath *path = tb->tb_path;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001900 int position,
1901 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001902
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001903 /* We are in the root or in the new root. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001904 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001905
Jeff Mahoneyee939612009-03-30 14:02:50 -04001906 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001907 "PAP-8260: invalid offset in the path");
1908
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001909 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001910 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001911 /* Root is not changed. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001912 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;
1913 PATH_OFFSET_POSITION(path, path_offset - 1) = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001914 return CARRY_ON;
1915 }
1916 return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001917 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001918
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001919 if (!B_IS_IN_TREE
Jeff Mahoneyee939612009-03-30 14:02:50 -04001920 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001921 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001922
Jeff Mahoneyee939612009-03-30 14:02:50 -04001923 if ((position =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001924 PATH_OFFSET_POSITION(path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001925 path_offset - 1)) > B_NR_ITEMS(bh))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001926 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001927
Jeff Mahoneyee939612009-03-30 14:02:50 -04001928 if (B_N_CHILD_NUM(bh, position) !=
1929 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001930 /* Parent in the path is not parent of the current node in the tree. */
1931 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001932
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001933 if (buffer_locked(bh)) {
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02001934 reiserfs_write_unlock(tb->tb_sb);
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001935 __wait_on_buffer(bh);
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02001936 reiserfs_write_lock(tb->tb_sb);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001937 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001938 return REPEAT_SEARCH;
1939 }
1940
1941 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001942}
1943
Jeff Mahoneyee939612009-03-30 14:02:50 -04001944/* Using lnum[h] and rnum[h] we should determine what neighbors
1945 * of S[h] we
1946 * need in order to balance S[h], and get them if necessary.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001947 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1948 * CARRY_ON - schedule didn't occur while the function worked;
1949 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001950static int get_neighbors(struct tree_balance *tb, int h)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001951{
Jeff Mahoneyee939612009-03-30 14:02:50 -04001952 int child_position,
1953 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
1954 unsigned long son_number;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001955 struct super_block *sb = tb->tb_sb;
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001956 struct buffer_head *bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001957
Jeff Mahoneyee939612009-03-30 14:02:50 -04001958 PROC_INFO_INC(sb, get_neighbors[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001959
Jeff Mahoneyee939612009-03-30 14:02:50 -04001960 if (tb->lnum[h]) {
1961 /* We need left neighbor to balance S[h]. */
1962 PROC_INFO_INC(sb, need_l_neighbor[h]);
1963 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001964
Jeff Mahoneyee939612009-03-30 14:02:50 -04001965 RFALSE(bh == tb->FL[h] &&
1966 !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001967 "PAP-8270: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001968
Jeff Mahoneyee939612009-03-30 14:02:50 -04001969 child_position =
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001970 (bh ==
Jeff Mahoneyee939612009-03-30 14:02:50 -04001971 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
1972 FL[h]);
1973 son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
1974 bh = sb_bread(sb, son_number);
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001975 if (!bh)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001976 return IO_ERROR;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001977 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001978 brelse(bh);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001979 PROC_INFO_INC(sb, get_neighbors_restart[h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001980 return REPEAT_SEARCH;
1981 }
1982
Jeff Mahoneyee939612009-03-30 14:02:50 -04001983 RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||
1984 child_position > B_NR_ITEMS(tb->FL[h]) ||
1985 B_N_CHILD_NUM(tb->FL[h], child_position) !=
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001986 bh->b_blocknr, "PAP-8275: invalid parent");
1987 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
Jeff Mahoneyee939612009-03-30 14:02:50 -04001988 RFALSE(!h &&
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001989 B_FREE_SPACE(bh) !=
1990 MAX_CHILD_SIZE(bh) -
Jeff Mahoneyee939612009-03-30 14:02:50 -04001991 dc_size(B_N_CHILD(tb->FL[0], child_position)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001992 "PAP-8290: invalid child size of left neighbor");
1993
Jeff Mahoneyee939612009-03-30 14:02:50 -04001994 brelse(tb->L[h]);
1995 tb->L[h] = bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001996 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001997
Jeff Mahoneyee939612009-03-30 14:02:50 -04001998 /* We need right neighbor to balance S[path_offset]. */
1999 if (tb->rnum[h]) { /* We need right neighbor to balance S[path_offset]. */
2000 PROC_INFO_INC(sb, need_r_neighbor[h]);
2001 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002002
Jeff Mahoneyee939612009-03-30 14:02:50 -04002003 RFALSE(bh == tb->FR[h] &&
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002004 PATH_OFFSET_POSITION(tb->tb_path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04002005 path_offset) >=
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002006 B_NR_ITEMS(bh),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002007 "PAP-8295: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07002008
Jeff Mahoneyee939612009-03-30 14:02:50 -04002009 child_position =
2010 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
2011 son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
2012 bh = sb_bread(sb, son_number);
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002013 if (!bh)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002014 return IO_ERROR;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002015 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002016 brelse(bh);
Jeff Mahoneyee939612009-03-30 14:02:50 -04002017 PROC_INFO_INC(sb, get_neighbors_restart[h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002018 return REPEAT_SEARCH;
2019 }
Jeff Mahoneyee939612009-03-30 14:02:50 -04002020 brelse(tb->R[h]);
2021 tb->R[h] = bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002022
Jeff Mahoneyee939612009-03-30 14:02:50 -04002023 RFALSE(!h
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002024 && B_FREE_SPACE(bh) !=
2025 MAX_CHILD_SIZE(bh) -
Jeff Mahoneyee939612009-03-30 14:02:50 -04002026 dc_size(B_N_CHILD(tb->FR[0], child_position)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002027 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002028 B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
Jeff Mahoneyee939612009-03-30 14:02:50 -04002029 dc_size(B_N_CHILD(tb->FR[0], child_position)));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002030
Linus Torvalds1da177e2005-04-16 15:20:36 -07002031 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002032 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002033}
2034
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002035static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002036{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002037 int max_num_of_items;
2038 int max_num_of_entries;
2039 unsigned long blocksize = sb->s_blocksize;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002040
2041#define MIN_NAME_LEN 1
2042
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002043 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2044 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2045 (DEH_SIZE + MIN_NAME_LEN);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002046
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002047 return sizeof(struct virtual_node) +
2048 max(max_num_of_items * sizeof(struct virtual_item),
2049 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2050 (max_num_of_entries - 1) * sizeof(__u16));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002051}
2052
Linus Torvalds1da177e2005-04-16 15:20:36 -07002053/* maybe we should fail balancing we are going to perform when kmalloc
2054 fails several times. But now it will loop until kmalloc gets
2055 required memory */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002056static int get_mem_for_virtual_node(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002057{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002058 int check_fs = 0;
2059 int size;
2060 char *buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002061
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002062 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002063
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002064 if (size > tb->vn_buf_size) {
2065 /* we have to allocate more memory for virtual node */
2066 if (tb->vn_buf) {
2067 /* free memory allocated before */
Pekka Enbergd739b422006-02-01 03:06:43 -08002068 kfree(tb->vn_buf);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002069 /* this is not needed if kfree is atomic */
2070 check_fs = 1;
2071 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002072
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002073 /* virtual node requires now more memory */
2074 tb->vn_buf_size = size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002075
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002076 /* get memory for virtual item */
Pekka Enbergd739b422006-02-01 03:06:43 -08002077 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002078 if (!buf) {
2079 /* getting memory with GFP_KERNEL priority may involve
2080 balancing now (due to indirect_to_direct conversion on
2081 dcache shrinking). So, release path and collected
2082 resources here */
2083 free_buffers_in_tb(tb);
Pekka Enbergd739b422006-02-01 03:06:43 -08002084 buf = kmalloc(size, GFP_NOFS);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002085 if (!buf) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002086 tb->vn_buf_size = 0;
2087 }
2088 tb->vn_buf = buf;
2089 schedule();
2090 return REPEAT_SEARCH;
2091 }
2092
2093 tb->vn_buf = buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002094 }
2095
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002096 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2097 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002098
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002099 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002100}
2101
Linus Torvalds1da177e2005-04-16 15:20:36 -07002102#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002103static void tb_buffer_sanity_check(struct super_block *sb,
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002104 struct buffer_head *bh,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002105 const char *descr, int level)
2106{
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002107 if (bh) {
2108 if (atomic_read(&(bh->b_count)) <= 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002109
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002110 reiserfs_panic(sb, "jmacd-1", "negative or zero "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002111 "reference counter for buffer %s[%d] "
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002112 "(%b)", descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002113
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002114 if (!buffer_uptodate(bh))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002115 reiserfs_panic(sb, "jmacd-2", "buffer is not up "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002116 "to date %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002117 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002118
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002119 if (!B_IS_IN_TREE(bh))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002120 reiserfs_panic(sb, "jmacd-3", "buffer is not "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002121 "in tree %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002122 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002123
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002124 if (bh->b_bdev != sb->s_bdev)
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002125 reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002126 "device %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002127 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002128
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002129 if (bh->b_size != sb->s_blocksize)
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002130 reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002131 "blocksize %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002132 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002133
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002134 if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002135 reiserfs_panic(sb, "jmacd-6", "buffer block "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002136 "number too high %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002137 descr, level, bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002138 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002139}
2140#else
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002141static void tb_buffer_sanity_check(struct super_block *sb,
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002142 struct buffer_head *bh,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002143 const char *descr, int level)
2144{;
2145}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002146#endif
2147
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002148static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002149{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002150 return reiserfs_prepare_for_journal(s, bh, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002151}
2152
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002153static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002154{
2155 struct buffer_head *locked;
2156#ifdef CONFIG_REISERFS_CHECK
2157 int repeat_counter = 0;
2158#endif
2159 int i;
2160
2161 do {
2162
2163 locked = NULL;
2164
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002165 for (i = tb->tb_path->path_length;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002166 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002167 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002168 /* if I understand correctly, we can only be sure the last buffer
2169 ** in the path is in the tree --clm
2170 */
2171#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002172 if (PATH_PLAST_BUFFER(tb->tb_path) ==
2173 PATH_OFFSET_PBUFFER(tb->tb_path, i))
2174 tb_buffer_sanity_check(tb->tb_sb,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002175 PATH_OFFSET_PBUFFER
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002176 (tb->tb_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002177 i), "S",
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002178 tb->tb_path->
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002179 path_length - i);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002180#endif
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002181 if (!clear_all_dirty_bits(tb->tb_sb,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002182 PATH_OFFSET_PBUFFER
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002183 (tb->tb_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002184 i))) {
2185 locked =
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002186 PATH_OFFSET_PBUFFER(tb->tb_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002187 i);
2188 }
2189 }
2190 }
2191
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002192 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002193 i++) {
2194
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002195 if (tb->lnum[i]) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002196
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002197 if (tb->L[i]) {
2198 tb_buffer_sanity_check(tb->tb_sb,
2199 tb->L[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002200 "L", i);
2201 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002202 (tb->tb_sb, tb->L[i]))
2203 locked = tb->L[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002204 }
2205
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002206 if (!locked && tb->FL[i]) {
2207 tb_buffer_sanity_check(tb->tb_sb,
2208 tb->FL[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002209 "FL", i);
2210 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002211 (tb->tb_sb, tb->FL[i]))
2212 locked = tb->FL[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002213 }
2214
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002215 if (!locked && tb->CFL[i]) {
2216 tb_buffer_sanity_check(tb->tb_sb,
2217 tb->CFL[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002218 "CFL", i);
2219 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002220 (tb->tb_sb, tb->CFL[i]))
2221 locked = tb->CFL[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002222 }
2223
2224 }
2225
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002226 if (!locked && (tb->rnum[i])) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002227
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002228 if (tb->R[i]) {
2229 tb_buffer_sanity_check(tb->tb_sb,
2230 tb->R[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002231 "R", i);
2232 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002233 (tb->tb_sb, tb->R[i]))
2234 locked = tb->R[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002235 }
2236
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002237 if (!locked && tb->FR[i]) {
2238 tb_buffer_sanity_check(tb->tb_sb,
2239 tb->FR[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002240 "FR", i);
2241 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002242 (tb->tb_sb, tb->FR[i]))
2243 locked = tb->FR[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002244 }
2245
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002246 if (!locked && tb->CFR[i]) {
2247 tb_buffer_sanity_check(tb->tb_sb,
2248 tb->CFR[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002249 "CFR", i);
2250 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002251 (tb->tb_sb, tb->CFR[i]))
2252 locked = tb->CFR[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002253 }
2254 }
2255 }
2256 /* as far as I can tell, this is not required. The FEB list seems
2257 ** to be full of newly allocated nodes, which will never be locked,
2258 ** dirty, or anything else.
2259 ** To be safe, I'm putting in the checks and waits in. For the moment,
2260 ** they are needed to keep the code in journal.c from complaining
2261 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2262 ** --clm
2263 */
2264 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002265 if (tb->FEB[i]) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002266 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002267 (tb->tb_sb, tb->FEB[i]))
2268 locked = tb->FEB[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002269 }
2270 }
2271
2272 if (locked) {
2273#ifdef CONFIG_REISERFS_CHECK
2274 repeat_counter++;
2275 if ((repeat_counter % 10000) == 0) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002276 reiserfs_warning(tb->tb_sb, "reiserfs-8200",
Jeff Mahoney45b03d52009-03-30 14:02:21 -04002277 "too many iterations waiting "
2278 "for buffer to unlock "
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002279 "(%b)", locked);
2280
2281 /* Don't loop forever. Try to recover from possible error. */
2282
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002283 return (FILESYSTEM_CHANGED_TB(tb)) ?
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002284 REPEAT_SEARCH : CARRY_ON;
2285 }
2286#endif
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02002287 reiserfs_write_unlock(tb->tb_sb);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002288 __wait_on_buffer(locked);
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02002289 reiserfs_write_lock(tb->tb_sb);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002290 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002291 return REPEAT_SEARCH;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002292 }
2293
2294 } while (locked);
2295
2296 return CARRY_ON;
2297}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002298
2299/* Prepare for balancing, that is
2300 * get all necessary parents, and neighbors;
2301 * analyze what and where should be moved;
2302 * get sufficient number of new nodes;
2303 * Balancing will start only after all resources will be collected at a time.
Jeff Mahoney0222e652009-03-30 14:02:44 -04002304 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07002305 * When ported to SMP kernels, only at the last moment after all needed nodes
2306 * are collected in cache, will the resources be locked using the usual
2307 * textbook ordered lock acquisition algorithms. Note that ensuring that
2308 * this code neither write locks what it does not need to write lock nor locks out of order
2309 * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans
Jeff Mahoney0222e652009-03-30 14:02:44 -04002310 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07002311 * fix is meant in the sense of render unchanging
Jeff Mahoney0222e652009-03-30 14:02:44 -04002312 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07002313 * Latency might be improved by first gathering a list of what buffers are needed
2314 * and then getting as many of them in parallel as possible? -Hans
2315 *
2316 * Parameters:
2317 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2318 * tb tree_balance structure;
2319 * inum item number in S[h];
2320 * pos_in_item - comment this if you can
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002321 * ins_ih item head of item being inserted
2322 * data inserted item or data to be pasted
Linus Torvalds1da177e2005-04-16 15:20:36 -07002323 * Returns: 1 - schedule occurred while the function worked;
2324 * 0 - schedule didn't occur while the function worked;
Jeff Mahoney0222e652009-03-30 14:02:44 -04002325 * -1 - if no_disk_space
Linus Torvalds1da177e2005-04-16 15:20:36 -07002326 */
2327
Jeff Mahoneyee939612009-03-30 14:02:50 -04002328int fix_nodes(int op_mode, struct tree_balance *tb,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002329 struct item_head *ins_ih, const void *data)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002330{
Jeff Mahoneyee939612009-03-30 14:02:50 -04002331 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2332 int pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002333
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002334 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2335 ** during wait_tb_buffers_run
2336 */
2337 int wait_tb_buffers_run = 0;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002338 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002339
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002340 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002341
Jeff Mahoneyee939612009-03-30 14:02:50 -04002342 pos_in_item = tb->tb_path->pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002343
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002344 tb->fs_gen = get_generation(tb->tb_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002345
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002346 /* we prepare and log the super here so it will already be in the
2347 ** transaction when do_balance needs to change it.
2348 ** This way do_balance won't have to schedule when trying to prepare
2349 ** the super for logging
2350 */
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002351 reiserfs_prepare_for_journal(tb->tb_sb,
2352 SB_BUFFER_WITH_SB(tb->tb_sb), 1);
2353 journal_mark_dirty(tb->transaction_handle, tb->tb_sb,
2354 SB_BUFFER_WITH_SB(tb->tb_sb));
2355 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002356 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002357
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002358 /* if it possible in indirect_to_direct conversion */
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002359 if (buffer_locked(tbS0)) {
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02002360 reiserfs_write_unlock(tb->tb_sb);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002361 __wait_on_buffer(tbS0);
Frederic Weisbecker8ebc4232009-04-07 04:19:49 +02002362 reiserfs_write_lock(tb->tb_sb);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002363 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002364 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002365 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002366#ifdef CONFIG_REISERFS_CHECK
2367 if (cur_tb) {
2368 print_cur_tb("fix_nodes");
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002369 reiserfs_panic(tb->tb_sb, "PAP-8305",
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002370 "there is pending do_balance");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002371 }
2372
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002373 if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
2374 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002375 "not uptodate at the beginning of fix_nodes "
2376 "or not in tree (mode %c)",
Jeff Mahoneyee939612009-03-30 14:02:50 -04002377 tbS0, tbS0, op_mode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002378
2379 /* Check parameters. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04002380 switch (op_mode) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002381 case M_INSERT:
Jeff Mahoneyee939612009-03-30 14:02:50 -04002382 if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002383 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002384 "item number %d (in S0 - %d) in case "
Jeff Mahoneyee939612009-03-30 14:02:50 -04002385 "of insert", item_num,
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002386 B_NR_ITEMS(tbS0));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002387 break;
2388 case M_PASTE:
2389 case M_DELETE:
2390 case M_CUT:
Jeff Mahoneyee939612009-03-30 14:02:50 -04002391 if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002392 print_block(tbS0, 0, -1, -1);
2393 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002394 "item number(%d); mode = %c "
2395 "insert_size = %d",
Jeff Mahoneyee939612009-03-30 14:02:50 -04002396 item_num, op_mode,
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002397 tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002398 }
2399 break;
2400 default:
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002401 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002402 "of operation");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002403 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002404#endif
2405
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002406 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002407 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2408 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002409
Jeff Mahoneyee939612009-03-30 14:02:50 -04002410 /* Starting from the leaf level; for all levels h of the tree. */
2411 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
2412 ret = get_direct_parent(tb, h);
2413 if (ret != CARRY_ON)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002414 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002415
Jeff Mahoneyee939612009-03-30 14:02:50 -04002416 ret = check_balance(op_mode, tb, h, item_num,
2417 pos_in_item, ins_ih, data);
2418 if (ret != CARRY_ON) {
2419 if (ret == NO_BALANCING_NEEDED) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002420 /* No balancing for higher levels needed. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04002421 ret = get_neighbors(tb, h);
2422 if (ret != CARRY_ON)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002423 goto repeat;
Jeff Mahoneyee939612009-03-30 14:02:50 -04002424 if (h != MAX_HEIGHT - 1)
2425 tb->insert_size[h + 1] = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002426 /* ok, analysis and resource gathering are complete */
2427 break;
2428 }
2429 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002430 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002431
Jeff Mahoneyee939612009-03-30 14:02:50 -04002432 ret = get_neighbors(tb, h);
2433 if (ret != CARRY_ON)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002434 goto repeat;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002435
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002436 /* No disk space, or schedule occurred and analysis may be
2437 * invalid and needs to be redone. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04002438 ret = get_empty_nodes(tb, h);
2439 if (ret != CARRY_ON)
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002440 goto repeat;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002441
Jeff Mahoneyee939612009-03-30 14:02:50 -04002442 if (!PATH_H_PBUFFER(tb->tb_path, h)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002443 /* We have a positive insert size but no nodes exist on this
2444 level, this means that we are creating a new root. */
2445
Jeff Mahoneyee939612009-03-30 14:02:50 -04002446 RFALSE(tb->blknum[h] != 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002447 "PAP-8350: creating new empty root");
2448
Jeff Mahoneyee939612009-03-30 14:02:50 -04002449 if (h < MAX_HEIGHT - 1)
2450 tb->insert_size[h + 1] = 0;
2451 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
2452 if (tb->blknum[h] > 1) {
2453 /* The tree needs to be grown, so this node S[h]
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002454 which is the root node is split into two nodes,
Jeff Mahoneyee939612009-03-30 14:02:50 -04002455 and a new node (S[h+1]) will be created to
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002456 become the root node. */
2457
Jeff Mahoneyee939612009-03-30 14:02:50 -04002458 RFALSE(h == MAX_HEIGHT - 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002459 "PAP-8355: attempt to create too high of a tree");
2460
Jeff Mahoneyee939612009-03-30 14:02:50 -04002461 tb->insert_size[h + 1] =
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002462 (DC_SIZE +
Jeff Mahoneyee939612009-03-30 14:02:50 -04002463 KEY_SIZE) * (tb->blknum[h] - 1) +
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002464 DC_SIZE;
Jeff Mahoneyee939612009-03-30 14:02:50 -04002465 } else if (h < MAX_HEIGHT - 1)
2466 tb->insert_size[h + 1] = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002467 } else
Jeff Mahoneyee939612009-03-30 14:02:50 -04002468 tb->insert_size[h + 1] =
2469 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002470 }
2471
Jeff Mahoneyee939612009-03-30 14:02:50 -04002472 ret = wait_tb_buffers_until_unlocked(tb);
2473 if (ret == CARRY_ON) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002474 if (FILESYSTEM_CHANGED_TB(tb)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002475 wait_tb_buffers_run = 1;
Jeff Mahoneyee939612009-03-30 14:02:50 -04002476 ret = REPEAT_SEARCH;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002477 goto repeat;
2478 } else {
2479 return CARRY_ON;
2480 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002481 } else {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002482 wait_tb_buffers_run = 1;
2483 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002484 }
2485
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002486 repeat:
2487 // fix_nodes was unable to perform its calculation due to
2488 // filesystem got changed under us, lack of free disk space or i/o
2489 // failure. If the first is the case - the search will be
2490 // repeated. For now - free all resources acquired so far except
2491 // for the new allocated nodes
2492 {
2493 int i;
2494
2495 /* Release path buffers. */
2496 if (wait_tb_buffers_run) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002497 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002498 } else {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002499 pathrelse(tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002500 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002501 /* brelse all resources collected for balancing */
2502 for (i = 0; i < MAX_HEIGHT; i++) {
2503 if (wait_tb_buffers_run) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002504 reiserfs_restore_prepared_buffer(tb->tb_sb,
2505 tb->L[i]);
2506 reiserfs_restore_prepared_buffer(tb->tb_sb,
2507 tb->R[i]);
2508 reiserfs_restore_prepared_buffer(tb->tb_sb,
2509 tb->FL[i]);
2510 reiserfs_restore_prepared_buffer(tb->tb_sb,
2511 tb->FR[i]);
2512 reiserfs_restore_prepared_buffer(tb->tb_sb,
2513 tb->
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002514 CFL[i]);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002515 reiserfs_restore_prepared_buffer(tb->tb_sb,
2516 tb->
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002517 CFR[i]);
2518 }
2519
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002520 brelse(tb->L[i]);
2521 brelse(tb->R[i]);
2522 brelse(tb->FL[i]);
2523 brelse(tb->FR[i]);
2524 brelse(tb->CFL[i]);
2525 brelse(tb->CFR[i]);
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -04002526
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002527 tb->L[i] = NULL;
2528 tb->R[i] = NULL;
2529 tb->FL[i] = NULL;
2530 tb->FR[i] = NULL;
2531 tb->CFL[i] = NULL;
2532 tb->CFR[i] = NULL;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002533 }
2534
2535 if (wait_tb_buffers_run) {
2536 for (i = 0; i < MAX_FEB_SIZE; i++) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002537 if (tb->FEB[i])
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002538 reiserfs_restore_prepared_buffer
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002539 (tb->tb_sb, tb->FEB[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002540 }
2541 }
Jeff Mahoneyee939612009-03-30 14:02:50 -04002542 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002543 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002544
2545}
2546
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002547/* Anatoly will probably forgive me renaming tb to tb. I just
Linus Torvalds1da177e2005-04-16 15:20:36 -07002548 wanted to make lines shorter */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002549void unfix_nodes(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002550{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002551 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002552
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002553 /* Release path buffers. */
2554 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002555
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002556 /* brelse all resources collected for balancing */
2557 for (i = 0; i < MAX_HEIGHT; i++) {
2558 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2559 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2560 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2561 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2562 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2563 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002564
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002565 brelse(tb->L[i]);
2566 brelse(tb->R[i]);
2567 brelse(tb->FL[i]);
2568 brelse(tb->FR[i]);
2569 brelse(tb->CFL[i]);
2570 brelse(tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002571 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002572
2573 /* deal with list of allocated (used and unused) nodes */
2574 for (i = 0; i < MAX_FEB_SIZE; i++) {
2575 if (tb->FEB[i]) {
2576 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2577 /* de-allocated block which was not used by balancing and
2578 bforget about buffer for it */
2579 brelse(tb->FEB[i]);
2580 reiserfs_free_block(tb->transaction_handle, NULL,
2581 blocknr, 0);
2582 }
2583 if (tb->used[i]) {
2584 /* release used as new nodes including a new root */
2585 brelse(tb->used[i]);
2586 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002587 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002588
Pekka Enbergd739b422006-02-01 03:06:43 -08002589 kfree(tb->vn_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002590
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002591}