blob: 5e5a4e6fbaf8290d2bf91799d7e116390256ccf0 [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)) {
1025 __wait_on_buffer(*pcom_father);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001026 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001027 brelse(*pcom_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001028 return REPEAT_SEARCH;
1029 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001030 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001031
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001032 /* So, we got common parent of the current node and its left/right neighbor.
1033 Now we are geting the parent of the left/right neighbor. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001035 /* Form key to get parent of the left/right neighbor. */
1036 le_key2cpu_key(&s_lr_father_key,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001037 B_N_PDELIM_KEY(*pcom_father,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001038 (c_lr_par ==
Jeff Mahoneyee939612009-03-30 14:02:50 -04001039 LEFT_PARENTS) ? (tb->lkey[h - 1] =
1040 position -
1041 1) : (tb->rkey[h -
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001042 1] =
Jeff Mahoneyee939612009-03-30 14:02:50 -04001043 position)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001045 if (c_lr_par == LEFT_PARENTS)
1046 decrement_key(&s_lr_father_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001047
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001048 if (search_by_key
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001049 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001050 h + 1) == IO_ERROR)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001051 // path is released
1052 return IO_ERROR;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001053
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001054 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -04001055 pathrelse(&s_path_to_neighbor_father);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001056 brelse(*pcom_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001057 return REPEAT_SEARCH;
1058 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001059
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001060 *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001061
Jeff Mahoneyee939612009-03-30 14:02:50 -04001062 RFALSE(B_LEVEL(*pfather) != h + 1,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001063 "PAP-8190: (%b %z) level too small", *pfather, *pfather);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001064 RFALSE(s_path_to_neighbor_father.path_length <
1065 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1066
1067 s_path_to_neighbor_father.path_length--;
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -04001068 pathrelse(&s_path_to_neighbor_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001069 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001070}
1071
Jeff Mahoneyee939612009-03-30 14:02:50 -04001072/* Get parents of neighbors of node in the path(S[path_offset]) and common parents of
1073 * S[path_offset] and L[path_offset]/R[path_offset]: F[path_offset], FL[path_offset],
1074 * FR[path_offset], CFL[path_offset], CFR[path_offset].
1075 * Calculate numbers of left and right delimiting keys position: lkey[path_offset], rkey[path_offset].
Linus Torvalds1da177e2005-04-16 15:20:36 -07001076 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1077 * CARRY_ON - schedule didn't occur while the function worked;
1078 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001079static int get_parents(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001080{
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001081 struct treepath *path = tb->tb_path;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001082 int position,
1083 ret,
1084 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001085 struct buffer_head *curf, *curcf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001086
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001087 /* Current node is the root of the tree or will be root of the tree */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001088 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001089 /* The root can not have parents.
1090 Release nodes which previously were obtained as parents of the current node neighbors. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001091 brelse(tb->FL[h]);
1092 brelse(tb->CFL[h]);
1093 brelse(tb->FR[h]);
1094 brelse(tb->CFR[h]);
1095 tb->FL[h] = NULL;
1096 tb->CFL[h] = NULL;
1097 tb->FR[h] = NULL;
1098 tb->CFR[h] = NULL;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001099 return CARRY_ON;
1100 }
1101
Jeff Mahoneyee939612009-03-30 14:02:50 -04001102 /* Get parent FL[path_offset] of L[path_offset]. */
1103 position = PATH_OFFSET_POSITION(path, path_offset - 1);
1104 if (position) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001105 /* Current node is not the first child of its parent. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001106 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1107 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001108 get_bh(curf);
1109 get_bh(curf);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001110 tb->lkey[h] = position - 1;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001111 } else {
Jeff Mahoneyee939612009-03-30 14:02:50 -04001112 /* Calculate current parent of L[path_offset], which is the left neighbor of the current node.
1113 Calculate current common parent of L[path_offset] and the current node. Note that
1114 CFL[path_offset] not equal FL[path_offset] and CFL[path_offset] not equal F[path_offset].
1115 Calculate lkey[path_offset]. */
1116 if ((ret = get_far_parent(tb, h + 1, &curf,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001117 &curcf,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001118 LEFT_PARENTS)) != CARRY_ON)
Jeff Mahoneyee939612009-03-30 14:02:50 -04001119 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001120 }
1121
Jeff Mahoneyee939612009-03-30 14:02:50 -04001122 brelse(tb->FL[h]);
1123 tb->FL[h] = curf; /* New initialization of FL[h]. */
1124 brelse(tb->CFL[h]);
1125 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001126
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001127 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1128 (curcf && !B_IS_IN_TREE(curcf)),
1129 "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130
Jeff Mahoneyee939612009-03-30 14:02:50 -04001131/* Get parent FR[h] of R[h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001132
Jeff Mahoneyee939612009-03-30 14:02:50 -04001133/* Current node is the last child of F[h]. FR[h] != F[h]. */
1134 if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {
1135/* Calculate current parent of R[h], which is the right neighbor of F[h].
1136 Calculate current common parent of R[h] and current node. Note that CFR[h]
1137 not equal FR[path_offset] and CFR[h] not equal F[h]. */
1138 if ((ret =
1139 get_far_parent(tb, h + 1, &curf, &curcf,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001140 RIGHT_PARENTS)) != CARRY_ON)
Jeff Mahoneyee939612009-03-30 14:02:50 -04001141 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001142 } else {
Jeff Mahoneyee939612009-03-30 14:02:50 -04001143/* Current node is not the last child of its parent F[h]. */
1144 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1145 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001146 get_bh(curf);
1147 get_bh(curf);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001148 tb->rkey[h] = position;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001149 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150
Jeff Mahoneyee939612009-03-30 14:02:50 -04001151 brelse(tb->FR[h]);
1152 /* New initialization of FR[path_offset]. */
1153 tb->FR[h] = curf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154
Jeff Mahoneyee939612009-03-30 14:02:50 -04001155 brelse(tb->CFR[h]);
1156 /* New initialization of CFR[path_offset]. */
1157 tb->CFR[h] = curcf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001159 RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1160 (curcf && !B_IS_IN_TREE(curcf)),
1161 "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001162
1163 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001164}
1165
Linus Torvalds1da177e2005-04-16 15:20:36 -07001166/* it is possible to remove node as result of shiftings to
1167 neighbors even when we insert or paste item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001168static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1169 struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001171 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1172 int levbytes = tb->insert_size[h];
1173 struct item_head *ih;
1174 struct reiserfs_key *r_key = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001175
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001176 ih = B_N_PITEM_HEAD(Sh, 0);
1177 if (tb->CFR[h])
1178 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
1179
1180 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1181 /* shifting may merge items which might save space */
1182 -
1183 ((!h
1184 && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1185 -
1186 ((!h && r_key
1187 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1188 + ((h) ? KEY_SIZE : 0)) {
1189 /* node can not be removed */
1190 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1191 if (!h)
1192 tb->s0num =
1193 B_NR_ITEMS(Sh) +
1194 ((mode == M_INSERT) ? 1 : 0);
1195 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1196 return NO_BALANCING_NEEDED;
1197 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001198 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001199 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1200 return !NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201}
1202
Linus Torvalds1da177e2005-04-16 15:20:36 -07001203/* Check whether current node S[h] is balanced when increasing its size by
1204 * Inserting or Pasting.
1205 * Calculate parameters for balancing for current level h.
1206 * Parameters:
1207 * tb tree_balance structure;
1208 * h current level of the node;
1209 * inum item number in S[h];
1210 * mode i - insert, p - paste;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001211 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001212 * 0 - balancing for higher levels needed;
1213 * -1 - no balancing for higher levels needed;
1214 * -2 - no disk space.
1215 */
1216/* ip means Inserting or Pasting */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001217static int ip_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001218{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001219 struct virtual_node *vn = tb->tb_vn;
1220 int levbytes, /* Number of bytes that must be inserted into (value
1221 is negative if bytes are deleted) buffer which
1222 contains node being balanced. The mnemonic is
1223 that the attempted change in node space used level
1224 is levbytes bytes. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001225 ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001226
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001227 int lfree, sfree, rfree /* free space in L, S and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001228
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001229 /* nver is short for number of vertixes, and lnver is the number if
1230 we shift to the left, rnver is the number if we shift to the
1231 right, and lrnver is the number if we shift in both directions.
1232 The goal is to minimize first the number of vertixes, and second,
1233 the number of vertixes whose contents are changed by shifting,
1234 and third the number of uncached vertixes whose contents are
1235 changed by shifting and must be read from disk. */
1236 int nver, lnver, rnver, lrnver;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001237
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001238 /* used at leaf level only, S0 = S[0] is the node being balanced,
1239 sInum [ I = 0,1,2 ] is the number of items that will
1240 remain in node SI after balancing. S1 and S2 are new
1241 nodes that might be created. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001242
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001243 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
1244 where 4th parameter is s1bytes and 5th - s2bytes
Linus Torvalds1da177e2005-04-16 15:20:36 -07001245 */
Jeff Mahoney0222e652009-03-30 14:02:44 -04001246 short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001247 0,1 - do not shift and do not shift but bottle
1248 2 - shift only whole item to left
1249 3 - shift to left and bottle as much as possible
1250 4,5 - shift to right (whole items and as much as possible
1251 6,7 - shift to both directions (whole items and as much as possible)
1252 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001253
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001254 /* Sh is the node whose balance is currently being checked */
1255 struct buffer_head *Sh;
1256
1257 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1258 levbytes = tb->insert_size[h];
1259
1260 /* Calculate balance parameters for creating new root. */
1261 if (!Sh) {
1262 if (!h)
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001263 reiserfs_panic(tb->tb_sb, "vs-8210",
1264 "S[0] can not be 0");
Jeff Mahoneyee939612009-03-30 14:02:50 -04001265 switch (ret = get_empty_nodes(tb, h)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001266 case CARRY_ON:
1267 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1268 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1269
1270 case NO_DISK_SPACE:
1271 case REPEAT_SEARCH:
Jeff Mahoneyee939612009-03-30 14:02:50 -04001272 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001273 default:
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001274 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1275 "return value of get_empty_nodes");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001276 }
1277 }
1278
Jeff Mahoneyee939612009-03-30 14:02:50 -04001279 if ((ret = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */
1280 return ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001281
1282 sfree = B_FREE_SPACE(Sh);
1283
1284 /* get free space of neighbors */
1285 rfree = get_rfree(tb, h);
1286 lfree = get_lfree(tb, h);
1287
1288 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1289 NO_BALANCING_NEEDED)
1290 /* and new item fits into node S[h] without any shifting */
1291 return NO_BALANCING_NEEDED;
1292
1293 create_virtual_node(tb, h);
1294
Jeff Mahoney0222e652009-03-30 14:02:44 -04001295 /*
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001296 determine maximal number of items we can shift to the left neighbor (in tb structure)
1297 and the maximal number of bytes that can flow to the left neighbor
1298 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1299 */
1300 check_left(tb, h, lfree);
1301
1302 /*
1303 determine maximal number of items we can shift to the right neighbor (in tb structure)
1304 and the maximal number of bytes that can flow to the right neighbor
1305 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1306 */
1307 check_right(tb, h, rfree);
1308
1309 /* all contents of internal node S[h] can be moved into its
1310 neighbors, S[h] will be removed after balancing */
1311 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1312 int to_r;
1313
1314 /* Since we are working on internal nodes, and our internal
1315 nodes have fixed size entries, then we can balance by the
1316 number of items rather than the space they consume. In this
1317 routine we set the left node equal to the right node,
1318 allowing a difference of less than or equal to 1 child
1319 pointer. */
1320 to_r =
1321 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1322 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1323 tb->rnum[h]);
1324 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1325 -1, -1);
1326 return CARRY_ON;
1327 }
1328
1329 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1330 RFALSE(h &&
1331 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1332 tb->rnum[h] >= vn->vn_nr_item + 1),
1333 "vs-8220: tree is not balanced on internal level");
1334 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1335 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1336 "vs-8225: tree is not balanced on leaf level");
1337
1338 /* all contents of S[0] can be moved into its neighbors
1339 S[0] will be removed after balancing. */
1340 if (!h && is_leaf_removable(tb))
1341 return CARRY_ON;
1342
1343 /* why do we perform this check here rather than earlier??
1344 Answer: we can win 1 node in some cases above. Moreover we
1345 checked it above, when we checked, that S[0] is not removable
1346 in principle */
1347 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1348 if (!h)
1349 tb->s0num = vn->vn_nr_item;
1350 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1351 return NO_BALANCING_NEEDED;
1352 }
1353
1354 {
1355 int lpar, rpar, nset, lset, rset, lrset;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001356 /*
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001357 * regular overflowing of the node
1358 */
1359
Jeff Mahoney0222e652009-03-30 14:02:44 -04001360 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001361 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
Jeff Mahoney0222e652009-03-30 14:02:44 -04001362 nset, lset, rset, lrset - shows, whether flowing items give better packing
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001363 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001364#define FLOW 1
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001365#define NO_FLOW 0 /* do not any splitting */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001366
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001367 /* we choose one the following */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001368#define NOTHING_SHIFT_NO_FLOW 0
1369#define NOTHING_SHIFT_FLOW 5
1370#define LEFT_SHIFT_NO_FLOW 10
1371#define LEFT_SHIFT_FLOW 15
1372#define RIGHT_SHIFT_NO_FLOW 20
1373#define RIGHT_SHIFT_FLOW 25
1374#define LR_SHIFT_NO_FLOW 30
1375#define LR_SHIFT_FLOW 35
1376
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001377 lpar = tb->lnum[h];
1378 rpar = tb->rnum[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001379
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001380 /* calculate number of blocks S[h] must be split into when
1381 nothing is shifted to the neighbors,
1382 as well as number of items in each part of the split node (s012 numbers),
1383 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1384 nset = NOTHING_SHIFT_NO_FLOW;
1385 nver = get_num_ver(vn->vn_mode, tb, h,
1386 0, -1, h ? vn->vn_nr_item : 0, -1,
1387 snum012, NO_FLOW);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001388
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001389 if (!h) {
1390 int nver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001392 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1393 nver1 = get_num_ver(vn->vn_mode, tb, h,
1394 0, -1, 0, -1,
1395 snum012 + NOTHING_SHIFT_FLOW, FLOW);
1396 if (nver > nver1)
1397 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1398 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001399
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001400 /* calculate number of blocks S[h] must be split into when
1401 l_shift_num first items and l_shift_bytes of the right most
1402 liquid item to be shifted are shifted to the left neighbor,
1403 as well as number of items in each part of the splitted node (s012 numbers),
1404 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1405 */
1406 lset = LEFT_SHIFT_NO_FLOW;
1407 lnver = get_num_ver(vn->vn_mode, tb, h,
1408 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1409 -1, h ? vn->vn_nr_item : 0, -1,
1410 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1411 if (!h) {
1412 int lnver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001413
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001414 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1415 lpar -
1416 ((tb->lbytes != -1) ? 1 : 0),
1417 tb->lbytes, 0, -1,
1418 snum012 + LEFT_SHIFT_FLOW, FLOW);
1419 if (lnver > lnver1)
1420 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1421 }
1422
1423 /* calculate number of blocks S[h] must be split into when
1424 r_shift_num first items and r_shift_bytes of the left most
1425 liquid item to be shifted are shifted to the right neighbor,
1426 as well as number of items in each part of the splitted node (s012 numbers),
1427 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1428 */
1429 rset = RIGHT_SHIFT_NO_FLOW;
1430 rnver = get_num_ver(vn->vn_mode, tb, h,
1431 0, -1,
1432 h ? (vn->vn_nr_item - rpar) : (rpar -
1433 ((tb->
1434 rbytes !=
1435 -1) ? 1 :
1436 0)), -1,
1437 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1438 if (!h) {
1439 int rnver1;
1440
1441 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1442 0, -1,
1443 (rpar -
1444 ((tb->rbytes != -1) ? 1 : 0)),
1445 tb->rbytes,
1446 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1447
1448 if (rnver > rnver1)
1449 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1450 }
1451
1452 /* calculate number of blocks S[h] must be split into when
1453 items are shifted in both directions,
1454 as well as number of items in each part of the splitted node (s012 numbers),
1455 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1456 */
1457 lrset = LR_SHIFT_NO_FLOW;
1458 lrnver = get_num_ver(vn->vn_mode, tb, h,
1459 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1460 -1,
1461 h ? (vn->vn_nr_item - rpar) : (rpar -
1462 ((tb->
1463 rbytes !=
1464 -1) ? 1 :
1465 0)), -1,
1466 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1467 if (!h) {
1468 int lrnver1;
1469
1470 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1471 lpar -
1472 ((tb->lbytes != -1) ? 1 : 0),
1473 tb->lbytes,
1474 (rpar -
1475 ((tb->rbytes != -1) ? 1 : 0)),
1476 tb->rbytes,
1477 snum012 + LR_SHIFT_FLOW, FLOW);
1478 if (lrnver > lrnver1)
1479 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1480 }
1481
1482 /* Our general shifting strategy is:
1483 1) to minimized number of new nodes;
1484 2) to minimized number of neighbors involved in shifting;
1485 3) to minimized number of disk reads; */
1486
1487 /* we can win TWO or ONE nodes by shifting in both directions */
1488 if (lrnver < lnver && lrnver < rnver) {
1489 RFALSE(h &&
1490 (tb->lnum[h] != 1 ||
1491 tb->rnum[h] != 1 ||
1492 lrnver != 1 || rnver != 2 || lnver != 2
1493 || h != 1), "vs-8230: bad h");
1494 if (lrset == LR_SHIFT_FLOW)
1495 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1496 lrnver, snum012 + lrset,
1497 tb->lbytes, tb->rbytes);
1498 else
1499 set_parameters(tb, h,
1500 tb->lnum[h] -
1501 ((tb->lbytes == -1) ? 0 : 1),
1502 tb->rnum[h] -
1503 ((tb->rbytes == -1) ? 0 : 1),
1504 lrnver, snum012 + lrset, -1, -1);
1505
1506 return CARRY_ON;
1507 }
1508
1509 /* if shifting doesn't lead to better packing then don't shift */
1510 if (nver == lrnver) {
1511 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1512 -1);
1513 return CARRY_ON;
1514 }
1515
1516 /* now we know that for better packing shifting in only one
1517 direction either to the left or to the right is required */
1518
1519 /* if shifting to the left is better than shifting to the right */
1520 if (lnver < rnver) {
1521 SET_PAR_SHIFT_LEFT;
1522 return CARRY_ON;
1523 }
1524
1525 /* if shifting to the right is better than shifting to the left */
1526 if (lnver > rnver) {
1527 SET_PAR_SHIFT_RIGHT;
1528 return CARRY_ON;
1529 }
1530
1531 /* now shifting in either direction gives the same number
1532 of nodes and we can make use of the cached neighbors */
1533 if (is_left_neighbor_in_cache(tb, h)) {
1534 SET_PAR_SHIFT_LEFT;
1535 return CARRY_ON;
1536 }
1537
1538 /* shift to the right independently on whether the right neighbor in cache or not */
1539 SET_PAR_SHIFT_RIGHT;
1540 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001541 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001542}
1543
Linus Torvalds1da177e2005-04-16 15:20:36 -07001544/* Check whether current node S[h] is balanced when Decreasing its size by
1545 * Deleting or Cutting for INTERNAL node of S+tree.
1546 * Calculate parameters for balancing for current level h.
1547 * Parameters:
1548 * tb tree_balance structure;
1549 * h current level of the node;
1550 * inum item number in S[h];
1551 * mode i - insert, p - paste;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001552 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001553 * 0 - balancing for higher levels needed;
1554 * -1 - no balancing for higher levels needed;
1555 * -2 - no disk space.
1556 *
1557 * Note: Items of internal nodes have fixed size, so the balance condition for
1558 * the internal part of S+tree is as for the B-trees.
1559 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001560static int dc_check_balance_internal(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001561{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001562 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001563
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001564 /* Sh is the node whose balance is currently being checked,
1565 and Fh is its father. */
1566 struct buffer_head *Sh, *Fh;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001567 int maxsize, ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001568 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001569
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001570 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1571 Fh = PATH_H_PPARENT(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001572
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001573 maxsize = MAX_CHILD_SIZE(Sh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001574
1575/* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1576/* new_nr_item = number of items node would have if operation is */
1577/* performed without balancing (new_nr_item); */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001578 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001579
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001580 if (!Fh) { /* S[h] is the root. */
1581 if (vn->vn_nr_item > 0) {
1582 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1583 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1584 }
1585 /* new_nr_item == 0.
1586 * Current root will be deleted resulting in
1587 * decrementing the tree height. */
1588 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1589 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001590 }
1591
Jeff Mahoneyee939612009-03-30 14:02:50 -04001592 if ((ret = get_parents(tb, h)) != CARRY_ON)
1593 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001594
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001595 /* get free space of neighbors */
1596 rfree = get_rfree(tb, h);
1597 lfree = get_lfree(tb, h);
1598
1599 /* determine maximal number of items we can fit into neighbors */
1600 check_left(tb, h, lfree);
1601 check_right(tb, h, rfree);
1602
1603 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
1604 * In this case we balance only if it leads to better packing. */
1605 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
1606 * which is impossible with greater values of new_nr_item. */
1607 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1608 /* All contents of S[h] can be moved to L[h]. */
1609 int n;
1610 int order_L;
1611
1612 order_L =
1613 ((n =
1614 PATH_H_B_ITEM_ORDER(tb->tb_path,
1615 h)) ==
1616 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1617 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1618 (DC_SIZE + KEY_SIZE);
1619 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1620 -1);
1621 return CARRY_ON;
1622 }
1623
1624 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1625 /* All contents of S[h] can be moved to R[h]. */
1626 int n;
1627 int order_R;
1628
1629 order_R =
1630 ((n =
1631 PATH_H_B_ITEM_ORDER(tb->tb_path,
1632 h)) ==
1633 B_NR_ITEMS(Fh)) ? 0 : n + 1;
1634 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1635 (DC_SIZE + KEY_SIZE);
1636 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1637 -1);
1638 return CARRY_ON;
1639 }
1640 }
1641
1642 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1643 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1644 int to_r;
1645
1646 to_r =
1647 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1648 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1649 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1650 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1651 0, NULL, -1, -1);
1652 return CARRY_ON;
1653 }
1654
1655 /* Balancing does not lead to better packing. */
1656 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1657 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001658 }
1659
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001660 /* Current node contain insufficient number of items. Balancing is required. */
1661 /* Check whether we can merge S[h] with left neighbor. */
1662 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1663 if (is_left_neighbor_in_cache(tb, h)
1664 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1665 int n;
1666 int order_L;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001667
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001668 order_L =
1669 ((n =
1670 PATH_H_B_ITEM_ORDER(tb->tb_path,
1671 h)) ==
1672 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1673 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1674 KEY_SIZE);
1675 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1676 return CARRY_ON;
1677 }
1678
1679 /* Check whether we can merge S[h] with right neighbor. */
1680 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1681 int n;
1682 int order_R;
1683
1684 order_R =
1685 ((n =
1686 PATH_H_B_ITEM_ORDER(tb->tb_path,
1687 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1688 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1689 KEY_SIZE);
1690 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1691 return CARRY_ON;
1692 }
1693
1694 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1695 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1696 int to_r;
1697
1698 to_r =
1699 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1700 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1701 tb->rnum[h]);
1702 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1703 -1, -1);
1704 return CARRY_ON;
1705 }
1706
1707 /* For internal nodes try to borrow item from a neighbor */
1708 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1709
1710 /* Borrow one or two items from caching neighbor */
1711 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1712 int from_l;
1713
1714 from_l =
1715 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1716 1) / 2 - (vn->vn_nr_item + 1);
1717 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1718 return CARRY_ON;
1719 }
1720
1721 set_parameters(tb, h, 0,
1722 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1723 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001724 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001725}
1726
Linus Torvalds1da177e2005-04-16 15:20:36 -07001727/* Check whether current node S[h] is balanced when Decreasing its size by
1728 * Deleting or Truncating for LEAF node of S+tree.
1729 * Calculate parameters for balancing for current level h.
1730 * Parameters:
1731 * tb tree_balance structure;
1732 * h current level of the node;
1733 * inum item number in S[h];
1734 * mode i - insert, p - paste;
Jeff Mahoney0222e652009-03-30 14:02:44 -04001735 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001736 * 0 - balancing for higher levels needed;
1737 * -1 - no balancing for higher levels needed;
1738 * -2 - no disk space.
1739 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001740static int dc_check_balance_leaf(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001741{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001742 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001743
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001744 /* Number of bytes that must be deleted from
1745 (value is negative if bytes are deleted) buffer which
1746 contains node being balanced. The mnemonic is that the
1747 attempted change in node space used level is levbytes bytes. */
1748 int levbytes;
1749 /* the maximal item size */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001750 int maxsize, ret;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001751 /* S0 is the node whose balance is currently being checked,
1752 and F0 is its father. */
1753 struct buffer_head *S0, *F0;
1754 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001755
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001756 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1757 F0 = PATH_H_PPARENT(tb->tb_path, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001758
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001759 levbytes = tb->insert_size[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001760
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001761 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001762
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001763 if (!F0) { /* S[0] is the root now. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001764
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001765 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1766 "vs-8240: attempt to create empty buffer tree");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001767
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001768 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1769 return NO_BALANCING_NEEDED;
1770 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001771
Jeff Mahoneyee939612009-03-30 14:02:50 -04001772 if ((ret = get_parents(tb, h)) != CARRY_ON)
1773 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001774
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001775 /* get free space of neighbors */
1776 rfree = get_rfree(tb, h);
1777 lfree = get_lfree(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001778
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001779 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001780
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001781 /* if 3 leaves can be merge to one, set parameters and return */
1782 if (are_leaves_removable(tb, lfree, rfree))
1783 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001784
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001785 /* determine maximal number of items we can shift to the left/right neighbor
1786 and the maximal number of bytes that can flow to the left/right neighbor
1787 from the left/right most liquid item that cannot be shifted from S[0] entirely
1788 */
1789 check_left(tb, h, lfree);
1790 check_right(tb, h, rfree);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001791
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001792 /* check whether we can merge S with left neighbor. */
1793 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1794 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 */
1795 !tb->FR[h]) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001796
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001797 RFALSE(!tb->FL[h],
1798 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001799
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001800 /* set parameter to merge S[0] with its left neighbor */
1801 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1802 return CARRY_ON;
1803 }
1804
1805 /* check whether we can merge S[0] with right neighbor. */
1806 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1807 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
1808 return CARRY_ON;
1809 }
1810
1811 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1812 if (is_leaf_removable(tb))
1813 return CARRY_ON;
1814
1815 /* Balancing is not required. */
1816 tb->s0num = vn->vn_nr_item;
1817 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1818 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001819}
1820
Linus Torvalds1da177e2005-04-16 15:20:36 -07001821/* Check whether current node S[h] is balanced when Decreasing its size by
1822 * Deleting or Cutting.
1823 * Calculate parameters for balancing for current level h.
1824 * Parameters:
1825 * tb tree_balance structure;
1826 * h current level of the node;
1827 * inum item number in S[h];
1828 * mode d - delete, c - cut.
Jeff Mahoney0222e652009-03-30 14:02:44 -04001829 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001830 * 0 - balancing for higher levels needed;
1831 * -1 - no balancing for higher levels needed;
1832 * -2 - no disk space.
1833 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001834static int dc_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001835{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001836 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1837 "vs-8250: S is not initialized");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001838
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001839 if (h)
1840 return dc_check_balance_internal(tb, h);
1841 else
1842 return dc_check_balance_leaf(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001843}
1844
Linus Torvalds1da177e2005-04-16 15:20:36 -07001845/* Check whether current node S[h] is balanced.
1846 * Calculate parameters for balancing for current level h.
1847 * Parameters:
1848 *
1849 * tb tree_balance structure:
1850 *
1851 * tb is a large structure that must be read about in the header file
1852 * at the same time as this procedure if the reader is to successfully
1853 * understand this procedure
1854 *
1855 * h current level of the node;
1856 * inum item number in S[h];
1857 * mode i - insert, p - paste, d - delete, c - cut.
Jeff Mahoney0222e652009-03-30 14:02:44 -04001858 * Returns: 1 - schedule occurred;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001859 * 0 - balancing for higher levels needed;
1860 * -1 - no balancing for higher levels needed;
1861 * -2 - no disk space.
1862 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001863static int check_balance(int mode,
1864 struct tree_balance *tb,
1865 int h,
1866 int inum,
1867 int pos_in_item,
1868 struct item_head *ins_ih, const void *data)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001869{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001870 struct virtual_node *vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001871
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001872 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
1873 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
1874 vn->vn_mode = mode;
1875 vn->vn_affected_item_num = inum;
1876 vn->vn_pos_in_item = pos_in_item;
1877 vn->vn_ins_ih = ins_ih;
1878 vn->vn_data = data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001879
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001880 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1881 "vs-8255: ins_ih can not be 0 in insert mode");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001882
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001883 if (tb->insert_size[h] > 0)
1884 /* Calculate balance parameters when size of node is increasing. */
1885 return ip_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001886
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001887 /* Calculate balance parameters when size of node is decreasing. */
1888 return dc_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001889}
1890
Linus Torvalds1da177e2005-04-16 15:20:36 -07001891/* Check whether parent at the path is the really parent of the current node.*/
Jeff Mahoneyee939612009-03-30 14:02:50 -04001892static int get_direct_parent(struct tree_balance *tb, int h)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001893{
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001894 struct buffer_head *bh;
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001895 struct treepath *path = tb->tb_path;
Jeff Mahoneyee939612009-03-30 14:02:50 -04001896 int position,
1897 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001898
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001899 /* We are in the root or in the new root. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001900 if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001901
Jeff Mahoneyee939612009-03-30 14:02:50 -04001902 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001903 "PAP-8260: invalid offset in the path");
1904
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001905 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001906 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001907 /* Root is not changed. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001908 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;
1909 PATH_OFFSET_POSITION(path, path_offset - 1) = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001910 return CARRY_ON;
1911 }
1912 return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001913 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001914
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001915 if (!B_IS_IN_TREE
Jeff Mahoneyee939612009-03-30 14:02:50 -04001916 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001917 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001918
Jeff Mahoneyee939612009-03-30 14:02:50 -04001919 if ((position =
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04001920 PATH_OFFSET_POSITION(path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001921 path_offset - 1)) > B_NR_ITEMS(bh))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001922 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001923
Jeff Mahoneyee939612009-03-30 14:02:50 -04001924 if (B_N_CHILD_NUM(bh, position) !=
1925 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001926 /* Parent in the path is not parent of the current node in the tree. */
1927 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001928
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001929 if (buffer_locked(bh)) {
1930 __wait_on_buffer(bh);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001931 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001932 return REPEAT_SEARCH;
1933 }
1934
1935 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001936}
1937
Jeff Mahoneyee939612009-03-30 14:02:50 -04001938/* Using lnum[h] and rnum[h] we should determine what neighbors
1939 * of S[h] we
1940 * need in order to balance S[h], and get them if necessary.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001941 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1942 * CARRY_ON - schedule didn't occur while the function worked;
1943 */
Jeff Mahoneyee939612009-03-30 14:02:50 -04001944static int get_neighbors(struct tree_balance *tb, int h)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001945{
Jeff Mahoneyee939612009-03-30 14:02:50 -04001946 int child_position,
1947 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
1948 unsigned long son_number;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001949 struct super_block *sb = tb->tb_sb;
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001950 struct buffer_head *bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001951
Jeff Mahoneyee939612009-03-30 14:02:50 -04001952 PROC_INFO_INC(sb, get_neighbors[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001953
Jeff Mahoneyee939612009-03-30 14:02:50 -04001954 if (tb->lnum[h]) {
1955 /* We need left neighbor to balance S[h]. */
1956 PROC_INFO_INC(sb, need_l_neighbor[h]);
1957 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001958
Jeff Mahoneyee939612009-03-30 14:02:50 -04001959 RFALSE(bh == tb->FL[h] &&
1960 !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001961 "PAP-8270: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001962
Jeff Mahoneyee939612009-03-30 14:02:50 -04001963 child_position =
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001964 (bh ==
Jeff Mahoneyee939612009-03-30 14:02:50 -04001965 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
1966 FL[h]);
1967 son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
1968 bh = sb_bread(sb, son_number);
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001969 if (!bh)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001970 return IO_ERROR;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001971 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001972 brelse(bh);
Jeff Mahoneyee939612009-03-30 14:02:50 -04001973 PROC_INFO_INC(sb, get_neighbors_restart[h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001974 return REPEAT_SEARCH;
1975 }
1976
Jeff Mahoneyee939612009-03-30 14:02:50 -04001977 RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||
1978 child_position > B_NR_ITEMS(tb->FL[h]) ||
1979 B_N_CHILD_NUM(tb->FL[h], child_position) !=
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001980 bh->b_blocknr, "PAP-8275: invalid parent");
1981 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
Jeff Mahoneyee939612009-03-30 14:02:50 -04001982 RFALSE(!h &&
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04001983 B_FREE_SPACE(bh) !=
1984 MAX_CHILD_SIZE(bh) -
Jeff Mahoneyee939612009-03-30 14:02:50 -04001985 dc_size(B_N_CHILD(tb->FL[0], child_position)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001986 "PAP-8290: invalid child size of left neighbor");
1987
Jeff Mahoneyee939612009-03-30 14:02:50 -04001988 brelse(tb->L[h]);
1989 tb->L[h] = bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001990 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001991
Jeff Mahoneyee939612009-03-30 14:02:50 -04001992 /* We need right neighbor to balance S[path_offset]. */
1993 if (tb->rnum[h]) { /* We need right neighbor to balance S[path_offset]. */
1994 PROC_INFO_INC(sb, need_r_neighbor[h]);
1995 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001996
Jeff Mahoneyee939612009-03-30 14:02:50 -04001997 RFALSE(bh == tb->FR[h] &&
Jeff Mahoneya063ae12009-03-30 14:02:48 -04001998 PATH_OFFSET_POSITION(tb->tb_path,
Jeff Mahoneyee939612009-03-30 14:02:50 -04001999 path_offset) >=
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002000 B_NR_ITEMS(bh),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002001 "PAP-8295: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07002002
Jeff Mahoneyee939612009-03-30 14:02:50 -04002003 child_position =
2004 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
2005 son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
2006 bh = sb_bread(sb, son_number);
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002007 if (!bh)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002008 return IO_ERROR;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002009 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002010 brelse(bh);
Jeff Mahoneyee939612009-03-30 14:02:50 -04002011 PROC_INFO_INC(sb, get_neighbors_restart[h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002012 return REPEAT_SEARCH;
2013 }
Jeff Mahoneyee939612009-03-30 14:02:50 -04002014 brelse(tb->R[h]);
2015 tb->R[h] = bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002016
Jeff Mahoneyee939612009-03-30 14:02:50 -04002017 RFALSE(!h
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002018 && B_FREE_SPACE(bh) !=
2019 MAX_CHILD_SIZE(bh) -
Jeff Mahoneyee939612009-03-30 14:02:50 -04002020 dc_size(B_N_CHILD(tb->FR[0], child_position)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002021 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002022 B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
Jeff Mahoneyee939612009-03-30 14:02:50 -04002023 dc_size(B_N_CHILD(tb->FR[0], child_position)));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002024
Linus Torvalds1da177e2005-04-16 15:20:36 -07002025 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002026 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002027}
2028
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002029static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002030{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002031 int max_num_of_items;
2032 int max_num_of_entries;
2033 unsigned long blocksize = sb->s_blocksize;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002034
2035#define MIN_NAME_LEN 1
2036
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002037 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2038 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2039 (DEH_SIZE + MIN_NAME_LEN);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002040
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002041 return sizeof(struct virtual_node) +
2042 max(max_num_of_items * sizeof(struct virtual_item),
2043 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2044 (max_num_of_entries - 1) * sizeof(__u16));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002045}
2046
Linus Torvalds1da177e2005-04-16 15:20:36 -07002047/* maybe we should fail balancing we are going to perform when kmalloc
2048 fails several times. But now it will loop until kmalloc gets
2049 required memory */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002050static int get_mem_for_virtual_node(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002051{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002052 int check_fs = 0;
2053 int size;
2054 char *buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002055
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002056 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002057
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002058 if (size > tb->vn_buf_size) {
2059 /* we have to allocate more memory for virtual node */
2060 if (tb->vn_buf) {
2061 /* free memory allocated before */
Pekka Enbergd739b422006-02-01 03:06:43 -08002062 kfree(tb->vn_buf);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002063 /* this is not needed if kfree is atomic */
2064 check_fs = 1;
2065 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002066
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002067 /* virtual node requires now more memory */
2068 tb->vn_buf_size = size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002069
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002070 /* get memory for virtual item */
Pekka Enbergd739b422006-02-01 03:06:43 -08002071 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002072 if (!buf) {
2073 /* getting memory with GFP_KERNEL priority may involve
2074 balancing now (due to indirect_to_direct conversion on
2075 dcache shrinking). So, release path and collected
2076 resources here */
2077 free_buffers_in_tb(tb);
Pekka Enbergd739b422006-02-01 03:06:43 -08002078 buf = kmalloc(size, GFP_NOFS);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002079 if (!buf) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002080 tb->vn_buf_size = 0;
2081 }
2082 tb->vn_buf = buf;
2083 schedule();
2084 return REPEAT_SEARCH;
2085 }
2086
2087 tb->vn_buf = buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002088 }
2089
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002090 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2091 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002092
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002093 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002094}
2095
Linus Torvalds1da177e2005-04-16 15:20:36 -07002096#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002097static void tb_buffer_sanity_check(struct super_block *sb,
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002098 struct buffer_head *bh,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002099 const char *descr, int level)
2100{
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002101 if (bh) {
2102 if (atomic_read(&(bh->b_count)) <= 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002103
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002104 reiserfs_panic(sb, "jmacd-1", "negative or zero "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002105 "reference counter for buffer %s[%d] "
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002106 "(%b)", descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002107
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002108 if (!buffer_uptodate(bh))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002109 reiserfs_panic(sb, "jmacd-2", "buffer is not up "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002110 "to date %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002111 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002112
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002113 if (!B_IS_IN_TREE(bh))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002114 reiserfs_panic(sb, "jmacd-3", "buffer is not "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002115 "in tree %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002116 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002117
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002118 if (bh->b_bdev != sb->s_bdev)
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002119 reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002120 "device %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002121 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002122
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002123 if (bh->b_size != sb->s_blocksize)
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002124 reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002125 "blocksize %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002126 descr, level, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002127
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002128 if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002129 reiserfs_panic(sb, "jmacd-6", "buffer block "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002130 "number too high %s[%d] (%b)",
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002131 descr, level, bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002132 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002133}
2134#else
Jeff Mahoneya9dd3642009-03-30 14:02:45 -04002135static void tb_buffer_sanity_check(struct super_block *sb,
Jeff Mahoneyad31a4f2009-03-30 14:02:46 -04002136 struct buffer_head *bh,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002137 const char *descr, int level)
2138{;
2139}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002140#endif
2141
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002142static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002143{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002144 return reiserfs_prepare_for_journal(s, bh, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002145}
2146
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002147static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002148{
2149 struct buffer_head *locked;
2150#ifdef CONFIG_REISERFS_CHECK
2151 int repeat_counter = 0;
2152#endif
2153 int i;
2154
2155 do {
2156
2157 locked = NULL;
2158
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002159 for (i = tb->tb_path->path_length;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002160 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002161 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002162 /* if I understand correctly, we can only be sure the last buffer
2163 ** in the path is in the tree --clm
2164 */
2165#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002166 if (PATH_PLAST_BUFFER(tb->tb_path) ==
2167 PATH_OFFSET_PBUFFER(tb->tb_path, i))
2168 tb_buffer_sanity_check(tb->tb_sb,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002169 PATH_OFFSET_PBUFFER
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002170 (tb->tb_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002171 i), "S",
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002172 tb->tb_path->
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002173 path_length - i);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002174#endif
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002175 if (!clear_all_dirty_bits(tb->tb_sb,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002176 PATH_OFFSET_PBUFFER
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002177 (tb->tb_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002178 i))) {
2179 locked =
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002180 PATH_OFFSET_PBUFFER(tb->tb_path,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002181 i);
2182 }
2183 }
2184 }
2185
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002186 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002187 i++) {
2188
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002189 if (tb->lnum[i]) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002190
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002191 if (tb->L[i]) {
2192 tb_buffer_sanity_check(tb->tb_sb,
2193 tb->L[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002194 "L", i);
2195 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002196 (tb->tb_sb, tb->L[i]))
2197 locked = tb->L[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002198 }
2199
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002200 if (!locked && tb->FL[i]) {
2201 tb_buffer_sanity_check(tb->tb_sb,
2202 tb->FL[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002203 "FL", i);
2204 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002205 (tb->tb_sb, tb->FL[i]))
2206 locked = tb->FL[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002207 }
2208
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002209 if (!locked && tb->CFL[i]) {
2210 tb_buffer_sanity_check(tb->tb_sb,
2211 tb->CFL[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002212 "CFL", i);
2213 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002214 (tb->tb_sb, tb->CFL[i]))
2215 locked = tb->CFL[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002216 }
2217
2218 }
2219
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002220 if (!locked && (tb->rnum[i])) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002221
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002222 if (tb->R[i]) {
2223 tb_buffer_sanity_check(tb->tb_sb,
2224 tb->R[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002225 "R", i);
2226 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002227 (tb->tb_sb, tb->R[i]))
2228 locked = tb->R[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002229 }
2230
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002231 if (!locked && tb->FR[i]) {
2232 tb_buffer_sanity_check(tb->tb_sb,
2233 tb->FR[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002234 "FR", i);
2235 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002236 (tb->tb_sb, tb->FR[i]))
2237 locked = tb->FR[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002238 }
2239
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002240 if (!locked && tb->CFR[i]) {
2241 tb_buffer_sanity_check(tb->tb_sb,
2242 tb->CFR[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002243 "CFR", i);
2244 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002245 (tb->tb_sb, tb->CFR[i]))
2246 locked = tb->CFR[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002247 }
2248 }
2249 }
2250 /* as far as I can tell, this is not required. The FEB list seems
2251 ** to be full of newly allocated nodes, which will never be locked,
2252 ** dirty, or anything else.
2253 ** To be safe, I'm putting in the checks and waits in. For the moment,
2254 ** they are needed to keep the code in journal.c from complaining
2255 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2256 ** --clm
2257 */
2258 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002259 if (tb->FEB[i]) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002260 if (!clear_all_dirty_bits
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002261 (tb->tb_sb, tb->FEB[i]))
2262 locked = tb->FEB[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002263 }
2264 }
2265
2266 if (locked) {
2267#ifdef CONFIG_REISERFS_CHECK
2268 repeat_counter++;
2269 if ((repeat_counter % 10000) == 0) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002270 reiserfs_warning(tb->tb_sb, "reiserfs-8200",
Jeff Mahoney45b03d52009-03-30 14:02:21 -04002271 "too many iterations waiting "
2272 "for buffer to unlock "
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002273 "(%b)", locked);
2274
2275 /* Don't loop forever. Try to recover from possible error. */
2276
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002277 return (FILESYSTEM_CHANGED_TB(tb)) ?
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002278 REPEAT_SEARCH : CARRY_ON;
2279 }
2280#endif
2281 __wait_on_buffer(locked);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002282 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002283 return REPEAT_SEARCH;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002284 }
2285
2286 } while (locked);
2287
2288 return CARRY_ON;
2289}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002290
2291/* Prepare for balancing, that is
2292 * get all necessary parents, and neighbors;
2293 * analyze what and where should be moved;
2294 * get sufficient number of new nodes;
2295 * Balancing will start only after all resources will be collected at a time.
Jeff Mahoney0222e652009-03-30 14:02:44 -04002296 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07002297 * When ported to SMP kernels, only at the last moment after all needed nodes
2298 * are collected in cache, will the resources be locked using the usual
2299 * textbook ordered lock acquisition algorithms. Note that ensuring that
2300 * this code neither write locks what it does not need to write lock nor locks out of order
2301 * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans
Jeff Mahoney0222e652009-03-30 14:02:44 -04002302 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07002303 * fix is meant in the sense of render unchanging
Jeff Mahoney0222e652009-03-30 14:02:44 -04002304 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07002305 * Latency might be improved by first gathering a list of what buffers are needed
2306 * and then getting as many of them in parallel as possible? -Hans
2307 *
2308 * Parameters:
2309 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2310 * tb tree_balance structure;
2311 * inum item number in S[h];
2312 * pos_in_item - comment this if you can
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002313 * ins_ih item head of item being inserted
2314 * data inserted item or data to be pasted
Linus Torvalds1da177e2005-04-16 15:20:36 -07002315 * Returns: 1 - schedule occurred while the function worked;
2316 * 0 - schedule didn't occur while the function worked;
Jeff Mahoney0222e652009-03-30 14:02:44 -04002317 * -1 - if no_disk_space
Linus Torvalds1da177e2005-04-16 15:20:36 -07002318 */
2319
Jeff Mahoneyee939612009-03-30 14:02:50 -04002320int fix_nodes(int op_mode, struct tree_balance *tb,
Jeff Mahoneyd68caa92009-03-30 14:02:49 -04002321 struct item_head *ins_ih, const void *data)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002322{
Jeff Mahoneyee939612009-03-30 14:02:50 -04002323 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2324 int pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002325
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002326 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2327 ** during wait_tb_buffers_run
2328 */
2329 int wait_tb_buffers_run = 0;
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002330 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002331
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002332 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002333
Jeff Mahoneyee939612009-03-30 14:02:50 -04002334 pos_in_item = tb->tb_path->pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002335
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002336 tb->fs_gen = get_generation(tb->tb_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002337
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002338 /* we prepare and log the super here so it will already be in the
2339 ** transaction when do_balance needs to change it.
2340 ** This way do_balance won't have to schedule when trying to prepare
2341 ** the super for logging
2342 */
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002343 reiserfs_prepare_for_journal(tb->tb_sb,
2344 SB_BUFFER_WITH_SB(tb->tb_sb), 1);
2345 journal_mark_dirty(tb->transaction_handle, tb->tb_sb,
2346 SB_BUFFER_WITH_SB(tb->tb_sb));
2347 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002348 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002349
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002350 /* if it possible in indirect_to_direct conversion */
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002351 if (buffer_locked(tbS0)) {
2352 __wait_on_buffer(tbS0);
2353 if (FILESYSTEM_CHANGED_TB(tb))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002354 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002355 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002356#ifdef CONFIG_REISERFS_CHECK
2357 if (cur_tb) {
2358 print_cur_tb("fix_nodes");
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002359 reiserfs_panic(tb->tb_sb, "PAP-8305",
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002360 "there is pending do_balance");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002361 }
2362
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002363 if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
2364 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002365 "not uptodate at the beginning of fix_nodes "
2366 "or not in tree (mode %c)",
Jeff Mahoneyee939612009-03-30 14:02:50 -04002367 tbS0, tbS0, op_mode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002368
2369 /* Check parameters. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04002370 switch (op_mode) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002371 case M_INSERT:
Jeff Mahoneyee939612009-03-30 14:02:50 -04002372 if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002373 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002374 "item number %d (in S0 - %d) in case "
Jeff Mahoneyee939612009-03-30 14:02:50 -04002375 "of insert", item_num,
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002376 B_NR_ITEMS(tbS0));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002377 break;
2378 case M_PASTE:
2379 case M_DELETE:
2380 case M_CUT:
Jeff Mahoneyee939612009-03-30 14:02:50 -04002381 if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002382 print_block(tbS0, 0, -1, -1);
2383 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002384 "item number(%d); mode = %c "
2385 "insert_size = %d",
Jeff Mahoneyee939612009-03-30 14:02:50 -04002386 item_num, op_mode,
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002387 tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002388 }
2389 break;
2390 default:
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002391 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04002392 "of operation");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002393 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002394#endif
2395
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002396 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002397 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2398 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002399
Jeff Mahoneyee939612009-03-30 14:02:50 -04002400 /* Starting from the leaf level; for all levels h of the tree. */
2401 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
2402 ret = get_direct_parent(tb, h);
2403 if (ret != CARRY_ON)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002404 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002405
Jeff Mahoneyee939612009-03-30 14:02:50 -04002406 ret = check_balance(op_mode, tb, h, item_num,
2407 pos_in_item, ins_ih, data);
2408 if (ret != CARRY_ON) {
2409 if (ret == NO_BALANCING_NEEDED) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002410 /* No balancing for higher levels needed. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04002411 ret = get_neighbors(tb, h);
2412 if (ret != CARRY_ON)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002413 goto repeat;
Jeff Mahoneyee939612009-03-30 14:02:50 -04002414 if (h != MAX_HEIGHT - 1)
2415 tb->insert_size[h + 1] = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002416 /* ok, analysis and resource gathering are complete */
2417 break;
2418 }
2419 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002420 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002421
Jeff Mahoneyee939612009-03-30 14:02:50 -04002422 ret = get_neighbors(tb, h);
2423 if (ret != CARRY_ON)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002424 goto repeat;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002425
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002426 /* No disk space, or schedule occurred and analysis may be
2427 * invalid and needs to be redone. */
Jeff Mahoneyee939612009-03-30 14:02:50 -04002428 ret = get_empty_nodes(tb, h);
2429 if (ret != CARRY_ON)
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002430 goto repeat;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002431
Jeff Mahoneyee939612009-03-30 14:02:50 -04002432 if (!PATH_H_PBUFFER(tb->tb_path, h)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002433 /* We have a positive insert size but no nodes exist on this
2434 level, this means that we are creating a new root. */
2435
Jeff Mahoneyee939612009-03-30 14:02:50 -04002436 RFALSE(tb->blknum[h] != 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002437 "PAP-8350: creating new empty root");
2438
Jeff Mahoneyee939612009-03-30 14:02:50 -04002439 if (h < MAX_HEIGHT - 1)
2440 tb->insert_size[h + 1] = 0;
2441 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
2442 if (tb->blknum[h] > 1) {
2443 /* The tree needs to be grown, so this node S[h]
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002444 which is the root node is split into two nodes,
Jeff Mahoneyee939612009-03-30 14:02:50 -04002445 and a new node (S[h+1]) will be created to
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002446 become the root node. */
2447
Jeff Mahoneyee939612009-03-30 14:02:50 -04002448 RFALSE(h == MAX_HEIGHT - 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002449 "PAP-8355: attempt to create too high of a tree");
2450
Jeff Mahoneyee939612009-03-30 14:02:50 -04002451 tb->insert_size[h + 1] =
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002452 (DC_SIZE +
Jeff Mahoneyee939612009-03-30 14:02:50 -04002453 KEY_SIZE) * (tb->blknum[h] - 1) +
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002454 DC_SIZE;
Jeff Mahoneyee939612009-03-30 14:02:50 -04002455 } else if (h < MAX_HEIGHT - 1)
2456 tb->insert_size[h + 1] = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002457 } else
Jeff Mahoneyee939612009-03-30 14:02:50 -04002458 tb->insert_size[h + 1] =
2459 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002460 }
2461
Jeff Mahoneyee939612009-03-30 14:02:50 -04002462 ret = wait_tb_buffers_until_unlocked(tb);
2463 if (ret == CARRY_ON) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002464 if (FILESYSTEM_CHANGED_TB(tb)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002465 wait_tb_buffers_run = 1;
Jeff Mahoneyee939612009-03-30 14:02:50 -04002466 ret = REPEAT_SEARCH;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002467 goto repeat;
2468 } else {
2469 return CARRY_ON;
2470 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002471 } else {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002472 wait_tb_buffers_run = 1;
2473 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002474 }
2475
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002476 repeat:
2477 // fix_nodes was unable to perform its calculation due to
2478 // filesystem got changed under us, lack of free disk space or i/o
2479 // failure. If the first is the case - the search will be
2480 // repeated. For now - free all resources acquired so far except
2481 // for the new allocated nodes
2482 {
2483 int i;
2484
2485 /* Release path buffers. */
2486 if (wait_tb_buffers_run) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002487 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002488 } else {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002489 pathrelse(tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002490 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002491 /* brelse all resources collected for balancing */
2492 for (i = 0; i < MAX_HEIGHT; i++) {
2493 if (wait_tb_buffers_run) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002494 reiserfs_restore_prepared_buffer(tb->tb_sb,
2495 tb->L[i]);
2496 reiserfs_restore_prepared_buffer(tb->tb_sb,
2497 tb->R[i]);
2498 reiserfs_restore_prepared_buffer(tb->tb_sb,
2499 tb->FL[i]);
2500 reiserfs_restore_prepared_buffer(tb->tb_sb,
2501 tb->FR[i]);
2502 reiserfs_restore_prepared_buffer(tb->tb_sb,
2503 tb->
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002504 CFL[i]);
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002505 reiserfs_restore_prepared_buffer(tb->tb_sb,
2506 tb->
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002507 CFR[i]);
2508 }
2509
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002510 brelse(tb->L[i]);
2511 brelse(tb->R[i]);
2512 brelse(tb->FL[i]);
2513 brelse(tb->FR[i]);
2514 brelse(tb->CFL[i]);
2515 brelse(tb->CFR[i]);
Jeff Mahoney3cd6dbe2009-03-30 14:02:43 -04002516
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002517 tb->L[i] = NULL;
2518 tb->R[i] = NULL;
2519 tb->FL[i] = NULL;
2520 tb->FR[i] = NULL;
2521 tb->CFL[i] = NULL;
2522 tb->CFR[i] = NULL;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002523 }
2524
2525 if (wait_tb_buffers_run) {
2526 for (i = 0; i < MAX_FEB_SIZE; i++) {
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002527 if (tb->FEB[i])
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002528 reiserfs_restore_prepared_buffer
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002529 (tb->tb_sb, tb->FEB[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002530 }
2531 }
Jeff Mahoneyee939612009-03-30 14:02:50 -04002532 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002533 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002534
2535}
2536
Jeff Mahoneya063ae12009-03-30 14:02:48 -04002537/* Anatoly will probably forgive me renaming tb to tb. I just
Linus Torvalds1da177e2005-04-16 15:20:36 -07002538 wanted to make lines shorter */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002539void unfix_nodes(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002540{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002541 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002542
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002543 /* Release path buffers. */
2544 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002545
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002546 /* brelse all resources collected for balancing */
2547 for (i = 0; i < MAX_HEIGHT; i++) {
2548 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2549 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2550 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2551 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2552 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2553 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002554
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002555 brelse(tb->L[i]);
2556 brelse(tb->R[i]);
2557 brelse(tb->FL[i]);
2558 brelse(tb->FR[i]);
2559 brelse(tb->CFL[i]);
2560 brelse(tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002561 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002562
2563 /* deal with list of allocated (used and unused) nodes */
2564 for (i = 0; i < MAX_FEB_SIZE; i++) {
2565 if (tb->FEB[i]) {
2566 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2567 /* de-allocated block which was not used by balancing and
2568 bforget about buffer for it */
2569 brelse(tb->FEB[i]);
2570 reiserfs_free_block(tb->transaction_handle, NULL,
2571 blocknr, 0);
2572 }
2573 if (tb->used[i]) {
2574 /* release used as new nodes including a new root */
2575 brelse(tb->used[i]);
2576 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002577 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002578
Pekka Enbergd739b422006-02-01 03:06:43 -08002579 kfree(tb->vn_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002580
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002581}