blob: 07d05e0842b72525b32eabac59dda28e7e3cc26a [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5/**
6 ** old_item_num
7 ** old_entry_num
8 ** set_entry_sizes
9 ** create_virtual_node
10 ** check_left
11 ** check_right
12 ** directory_part_size
13 ** get_num_ver
14 ** set_parameters
15 ** is_leaf_removable
16 ** are_leaves_removable
17 ** get_empty_nodes
18 ** get_lfree
19 ** get_rfree
20 ** is_left_neighbor_in_cache
21 ** decrement_key
22 ** get_far_parent
23 ** get_parents
24 ** can_node_be_removed
25 ** ip_check_balance
26 ** dc_check_balance_internal
27 ** dc_check_balance_leaf
28 ** dc_check_balance
29 ** check_balance
30 ** get_direct_parent
31 ** get_neighbors
32 ** fix_nodes
33 **
34 **
35 **/
36
Linus Torvalds1da177e2005-04-16 15:20:36 -070037#include <linux/time.h>
38#include <linux/string.h>
39#include <linux/reiserfs_fs.h>
40#include <linux/buffer_head.h>
41
Linus Torvalds1da177e2005-04-16 15:20:36 -070042/* To make any changes in the tree we find a node, that contains item
43 to be changed/deleted or position in the node we insert a new item
44 to. We call this node S. To do balancing we need to decide what we
45 will shift to left/right neighbor, or to a new node, where new item
46 will be etc. To make this analysis simpler we build virtual
47 node. Virtual node is an array of items, that will replace items of
48 node S. (For instance if we are going to delete an item, virtual
49 node does not contain it). Virtual node keeps information about
50 item sizes and types, mergeability of first and last items, sizes
51 of all entries in directory item. We use this array of items when
52 calculating what we can shift to neighbors and how many nodes we
53 have to have if we do not any shiftings, if we shift to left/right
54 neighbor or to both. */
55
Linus Torvalds1da177e2005-04-16 15:20:36 -070056/* taking item number in virtual node, returns number of item, that it has in source buffer */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070057static inline int old_item_num(int new_num, int affected_item_num, int mode)
Linus Torvalds1da177e2005-04-16 15:20:36 -070058{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070059 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
60 return new_num;
Linus Torvalds1da177e2005-04-16 15:20:36 -070061
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070062 if (mode == M_INSERT) {
Linus Torvalds1da177e2005-04-16 15:20:36 -070063
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070064 RFALSE(new_num == 0,
65 "vs-8005: for INSERT mode and item number of inserted item");
Linus Torvalds1da177e2005-04-16 15:20:36 -070066
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070067 return new_num - 1;
68 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070069
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070070 RFALSE(mode != M_DELETE,
71 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
72 mode);
73 /* delete mode */
74 return new_num + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070075}
76
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070077static void create_virtual_node(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -070078{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070079 struct item_head *ih;
80 struct virtual_node *vn = tb->tb_vn;
81 int new_num;
82 struct buffer_head *Sh; /* this comes from tb->S[h] */
Linus Torvalds1da177e2005-04-16 15:20:36 -070083
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070084 Sh = PATH_H_PBUFFER(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -070085
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070086 /* size of changed node */
87 vn->vn_size =
88 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070090 /* for internal nodes array if virtual items is not created */
91 if (h) {
92 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
93 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -070094 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070095
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070096 /* number of items in virtual node */
97 vn->vn_nr_item =
98 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
99 ((vn->vn_mode == M_DELETE) ? 1 : 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700100
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700101 /* first virtual item */
102 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
103 memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
104 vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
105
106 /* first item in the node */
107 ih = B_N_PITEM_HEAD(Sh, 0);
108
109 /* define the mergeability for 0-th item (if it is not being deleted) */
110 if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size)
111 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
112 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
113
114 /* go through all items those remain in the virtual node (except for the new (inserted) one) */
115 for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
116 int j;
117 struct virtual_item *vi = vn->vn_vi + new_num;
118 int is_affected =
119 ((new_num != vn->vn_affected_item_num) ? 0 : 1);
120
121 if (is_affected && vn->vn_mode == M_INSERT)
122 continue;
123
124 /* get item number in source node */
125 j = old_item_num(new_num, vn->vn_affected_item_num,
126 vn->vn_mode);
127
128 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
129 vi->vi_ih = ih + j;
130 vi->vi_item = B_I_PITEM(Sh, ih + j);
131 vi->vi_uarea = vn->vn_free_ptr;
132
133 // FIXME: there is no check, that item operation did not
134 // consume too much memory
135 vn->vn_free_ptr +=
136 op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
137 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
138 reiserfs_panic(tb->tb_sb,
139 "vs-8030: create_virtual_node: "
140 "virtual node space consumed");
141
142 if (!is_affected)
143 /* this is not being changed */
144 continue;
145
146 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
147 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
148 vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
149 }
150 }
151
152 /* virtual inserted item is not defined yet */
153 if (vn->vn_mode == M_INSERT) {
154 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
155
Al Viro9dce07f2008-03-29 03:07:28 +0000156 RFALSE(vn->vn_ins_ih == NULL,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700157 "vs-8040: item header of inserted item is not specified");
158 vi->vi_item_len = tb->insert_size[0];
159 vi->vi_ih = vn->vn_ins_ih;
160 vi->vi_item = vn->vn_data;
161 vi->vi_uarea = vn->vn_free_ptr;
162
163 op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
164 tb->insert_size[0]);
165 }
166
167 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
168 if (tb->CFR[0]) {
169 struct reiserfs_key *key;
170
171 key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]);
172 if (op_is_left_mergeable(key, Sh->b_size)
173 && (vn->vn_mode != M_DELETE
174 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
175 vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
176 VI_TYPE_RIGHT_MERGEABLE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700177
178#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700179 if (op_is_left_mergeable(key, Sh->b_size) &&
180 !(vn->vn_mode != M_DELETE
181 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
182 /* we delete last item and it could be merged with right neighbor's first item */
183 if (!
184 (B_NR_ITEMS(Sh) == 1
185 && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0))
186 && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) {
187 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
188 print_block(Sh, 0, -1, -1);
189 reiserfs_panic(tb->tb_sb,
190 "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c",
191 key, vn->vn_affected_item_num,
192 vn->vn_mode, M_DELETE);
Vladimir V. Savelievcd02b962006-03-25 03:07:15 -0800193 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700194 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700195#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700197 }
198}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199
200/* using virtual node check, how many items can be shifted to left
201 neighbor */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700202static void check_left(struct tree_balance *tb, int h, int cur_free)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700204 int i;
205 struct virtual_node *vn = tb->tb_vn;
206 struct virtual_item *vi;
207 int d_size, ih_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700209 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700211 /* internal level */
212 if (h > 0) {
213 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
214 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700216
217 /* leaf level */
218
219 if (!cur_free || !vn->vn_nr_item) {
220 /* no free space or nothing to move */
221 tb->lnum[h] = 0;
222 tb->lbytes = -1;
223 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700225
226 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
227 "vs-8055: parent does not exist or invalid");
228
229 vi = vn->vn_vi;
230 if ((unsigned int)cur_free >=
231 (vn->vn_size -
232 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
233 /* all contents of S[0] fits into L[0] */
234
235 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
236 "vs-8055: invalid mode or balance condition failed");
237
238 tb->lnum[0] = vn->vn_nr_item;
239 tb->lbytes = -1;
240 return;
241 }
242
243 d_size = 0, ih_size = IH_SIZE;
244
245 /* first item may be merge with last item in left neighbor */
246 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
247 d_size = -((int)IH_SIZE), ih_size = 0;
248
249 tb->lnum[0] = 0;
250 for (i = 0; i < vn->vn_nr_item;
251 i++, ih_size = IH_SIZE, d_size = 0, vi++) {
252 d_size += vi->vi_item_len;
253 if (cur_free >= d_size) {
254 /* the item can be shifted entirely */
255 cur_free -= d_size;
256 tb->lnum[0]++;
257 continue;
258 }
259
260 /* the item cannot be shifted entirely, try to split it */
261 /* check whether L[0] can hold ih and at least one byte of the item body */
262 if (cur_free <= ih_size) {
263 /* cannot shift even a part of the current item */
264 tb->lbytes = -1;
265 return;
266 }
267 cur_free -= ih_size;
268
269 tb->lbytes = op_check_left(vi, cur_free, 0, 0);
270 if (tb->lbytes != -1)
271 /* count partially shifted item */
272 tb->lnum[0]++;
273
274 break;
275 }
276
277 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278}
279
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280/* using virtual node check, how many items can be shifted to right
281 neighbor */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700282static void check_right(struct tree_balance *tb, int h, int cur_free)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700284 int i;
285 struct virtual_node *vn = tb->tb_vn;
286 struct virtual_item *vi;
287 int d_size, ih_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700289 RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700290
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700291 /* internal level */
292 if (h > 0) {
293 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
294 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700297 /* leaf level */
298
299 if (!cur_free || !vn->vn_nr_item) {
300 /* no free space */
301 tb->rnum[h] = 0;
302 tb->rbytes = -1;
303 return;
304 }
305
306 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
307 "vs-8075: parent does not exist or invalid");
308
309 vi = vn->vn_vi + vn->vn_nr_item - 1;
310 if ((unsigned int)cur_free >=
311 (vn->vn_size -
312 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
313 /* all contents of S[0] fits into R[0] */
314
315 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
316 "vs-8080: invalid mode or balance condition failed");
317
318 tb->rnum[h] = vn->vn_nr_item;
319 tb->rbytes = -1;
320 return;
321 }
322
323 d_size = 0, ih_size = IH_SIZE;
324
325 /* last item may be merge with first item in right neighbor */
326 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
327 d_size = -(int)IH_SIZE, ih_size = 0;
328
329 tb->rnum[0] = 0;
330 for (i = vn->vn_nr_item - 1; i >= 0;
331 i--, d_size = 0, ih_size = IH_SIZE, vi--) {
332 d_size += vi->vi_item_len;
333 if (cur_free >= d_size) {
334 /* the item can be shifted entirely */
335 cur_free -= d_size;
336 tb->rnum[0]++;
337 continue;
338 }
339
340 /* check whether R[0] can hold ih and at least one byte of the item body */
341 if (cur_free <= ih_size) { /* cannot shift even a part of the current item */
342 tb->rbytes = -1;
343 return;
344 }
345
346 /* R[0] can hold the header of the item and at least one byte of its body */
347 cur_free -= ih_size; /* cur_free is still > 0 */
348
349 tb->rbytes = op_check_right(vi, cur_free);
350 if (tb->rbytes != -1)
351 /* count partially shifted item */
352 tb->rnum[0]++;
353
354 break;
355 }
356
357 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358}
359
Linus Torvalds1da177e2005-04-16 15:20:36 -0700360/*
361 * from - number of items, which are shifted to left neighbor entirely
362 * to - number of item, which are shifted to right neighbor entirely
363 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
364 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700365static int get_num_ver(int mode, struct tree_balance *tb, int h,
366 int from, int from_bytes,
367 int to, int to_bytes, short *snum012, int flow)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700369 int i;
370 int cur_free;
371 // int bytes;
372 int units;
373 struct virtual_node *vn = tb->tb_vn;
374 // struct virtual_item * vi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700375
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700376 int total_node_size, max_node_size, current_item_size;
377 int needed_nodes;
378 int start_item, /* position of item we start filling node from */
379 end_item, /* position of item we finish filling node by */
380 start_bytes, /* number of first bytes (entries for directory) of start_item-th item
381 we do not include into node that is being filled */
382 end_bytes; /* number of last bytes (entries for directory) of end_item-th item
383 we do node include into node that is being filled */
384 int split_item_positions[2]; /* these are positions in virtual item of
385 items, that are split between S[0] and
386 S1new and S1new and S2new */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700388 split_item_positions[0] = -1;
389 split_item_positions[1] = -1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700391 /* We only create additional nodes if we are in insert or paste mode
392 or we are in replace mode at the internal level. If h is 0 and
393 the mode is M_REPLACE then in fix_nodes we change the mode to
394 paste or insert before we get here in the code. */
395 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
396 "vs-8100: insert_size < 0 in overflow");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700397
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700398 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700400 /* snum012 [0-2] - number of items, that lay
401 to S[0], first new node and second new node */
402 snum012[3] = -1; /* s1bytes */
403 snum012[4] = -1; /* s2bytes */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700404
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700405 /* internal level */
406 if (h > 0) {
407 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
408 if (i == max_node_size)
409 return 1;
410 return (i / max_node_size + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 }
412
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700413 /* leaf level */
414 needed_nodes = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 total_node_size = 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700416 cur_free = max_node_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700418 // start from 'from'-th item
419 start_item = from;
420 // skip its first 'start_bytes' units
421 start_bytes = ((from_bytes != -1) ? from_bytes : 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700422
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700423 // last included item is the 'end_item'-th one
424 end_item = vn->vn_nr_item - to - 1;
425 // do not count last 'end_bytes' units of 'end_item'-th item
426 end_bytes = (to_bytes != -1) ? to_bytes : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700428 /* go through all item beginning from the start_item-th item and ending by
429 the end_item-th item. Do not count first 'start_bytes' units of
430 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700432 for (i = start_item; i <= end_item; i++) {
433 struct virtual_item *vi = vn->vn_vi + i;
434 int skip_from_end = ((i == end_item) ? end_bytes : 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700435
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700436 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
437
438 /* get size of current item */
439 current_item_size = vi->vi_item_len;
440
441 /* do not take in calculation head part (from_bytes) of from-th item */
442 current_item_size -=
443 op_part_size(vi, 0 /*from start */ , start_bytes);
444
445 /* do not take in calculation tail part of last item */
446 current_item_size -=
447 op_part_size(vi, 1 /*from end */ , skip_from_end);
448
449 /* if item fits into current node entierly */
450 if (total_node_size + current_item_size <= max_node_size) {
451 snum012[needed_nodes - 1]++;
452 total_node_size += current_item_size;
453 start_bytes = 0;
454 continue;
455 }
456
457 if (current_item_size > max_node_size) {
458 /* virtual item length is longer, than max size of item in
459 a node. It is impossible for direct item */
460 RFALSE(is_direct_le_ih(vi->vi_ih),
461 "vs-8110: "
462 "direct item length is %d. It can not be longer than %d",
463 current_item_size, max_node_size);
464 /* we will try to split it */
465 flow = 1;
466 }
467
468 if (!flow) {
469 /* as we do not split items, take new node and continue */
470 needed_nodes++;
471 i--;
472 total_node_size = 0;
473 continue;
474 }
475 // calculate number of item units which fit into node being
476 // filled
477 {
478 int free_space;
479
480 free_space = max_node_size - total_node_size - IH_SIZE;
481 units =
482 op_check_left(vi, free_space, start_bytes,
483 skip_from_end);
484 if (units == -1) {
485 /* nothing fits into current node, take new node and continue */
486 needed_nodes++, i--, total_node_size = 0;
487 continue;
488 }
489 }
490
491 /* something fits into the current node */
492 //if (snum012[3] != -1 || needed_nodes != 1)
493 // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
494 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
495 start_bytes += units;
496 snum012[needed_nodes - 1 + 3] = units;
497
498 if (needed_nodes > 2)
499 reiserfs_warning(tb->tb_sb, "vs-8111: get_num_ver: "
500 "split_item_position is out of boundary");
501 snum012[needed_nodes - 1]++;
502 split_item_positions[needed_nodes - 1] = i;
503 needed_nodes++;
504 /* continue from the same item with start_bytes != -1 */
505 start_item = i;
506 i--;
507 total_node_size = 0;
508 }
509
510 // sum012[4] (if it is not -1) contains number of units of which
511 // are to be in S1new, snum012[3] - to be in S0. They are supposed
512 // to be S1bytes and S2bytes correspondingly, so recalculate
513 if (snum012[4] > 0) {
514 int split_item_num;
515 int bytes_to_r, bytes_to_l;
516 int bytes_to_S1new;
517
518 split_item_num = split_item_positions[1];
519 bytes_to_l =
520 ((from == split_item_num
521 && from_bytes != -1) ? from_bytes : 0);
522 bytes_to_r =
523 ((end_item == split_item_num
524 && end_bytes != -1) ? end_bytes : 0);
525 bytes_to_S1new =
526 ((split_item_positions[0] ==
527 split_item_positions[1]) ? snum012[3] : 0);
528
529 // s2bytes
530 snum012[4] =
531 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
532 bytes_to_r - bytes_to_l - bytes_to_S1new;
533
534 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
535 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
536 reiserfs_warning(tb->tb_sb, "vs-8115: get_num_ver: not "
537 "directory or indirect item");
538 }
539
540 /* now we know S2bytes, calculate S1bytes */
541 if (snum012[3] > 0) {
542 int split_item_num;
543 int bytes_to_r, bytes_to_l;
544 int bytes_to_S2new;
545
546 split_item_num = split_item_positions[0];
547 bytes_to_l =
548 ((from == split_item_num
549 && from_bytes != -1) ? from_bytes : 0);
550 bytes_to_r =
551 ((end_item == split_item_num
552 && end_bytes != -1) ? end_bytes : 0);
553 bytes_to_S2new =
554 ((split_item_positions[0] == split_item_positions[1]
555 && snum012[4] != -1) ? snum012[4] : 0);
556
557 // s1bytes
558 snum012[3] =
559 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
560 bytes_to_r - bytes_to_l - bytes_to_S2new;
561 }
562
563 return needed_nodes;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564}
565
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700567extern struct tree_balance *cur_tb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568#endif
569
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570/* Set parameters for balancing.
571 * Performs write of results of analysis of balancing into structure tb,
572 * where it will later be used by the functions that actually do the balancing.
573 * Parameters:
574 * tb tree_balance structure;
575 * h current level of the node;
576 * lnum number of items from S[h] that must be shifted to L[h];
577 * rnum number of items from S[h] that must be shifted to R[h];
578 * blk_num number of blocks that S[h] will be splitted into;
579 * s012 number of items that fall into splitted nodes.
580 * lbytes number of bytes which flow to the left neighbor from the item that is not
581 * not shifted entirely
582 * rbytes number of bytes which flow to the right neighbor from the item that is not
583 * not shifted entirely
584 * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array)
585 */
586
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700587static void set_parameters(struct tree_balance *tb, int h, int lnum,
588 int rnum, int blk_num, short *s012, int lb, int rb)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589{
590
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700591 tb->lnum[h] = lnum;
592 tb->rnum[h] = rnum;
593 tb->blknum[h] = blk_num;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700594
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700595 if (h == 0) { /* only for leaf level */
596 if (s012 != NULL) {
597 tb->s0num = *s012++,
598 tb->s1num = *s012++, tb->s2num = *s012++;
599 tb->s1bytes = *s012++;
600 tb->s2bytes = *s012;
601 }
602 tb->lbytes = lb;
603 tb->rbytes = rb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700604 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700605 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
606 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700607
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700608 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
609 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700610}
611
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612/* check, does node disappear if we shift tb->lnum[0] items to left
613 neighbor and tb->rnum[0] to the right one. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700614static int is_leaf_removable(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700615{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700616 struct virtual_node *vn = tb->tb_vn;
617 int to_left, to_right;
618 int size;
619 int remain_items;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700620
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700621 /* number of items, that will be shifted to left (right) neighbor
622 entirely */
623 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
624 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
625 remain_items = vn->vn_nr_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700627 /* how many items remain in S[0] after shiftings to neighbors */
628 remain_items -= (to_left + to_right);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700630 if (remain_items < 1) {
631 /* all content of node can be shifted to neighbors */
632 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
633 NULL, -1, -1);
634 return 1;
635 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700637 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
638 /* S[0] is not removable */
639 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700641 /* check, whether we can divide 1 remaining item between neighbors */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700642
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700643 /* get size of remaining item (in item units) */
644 size = op_unit_num(&(vn->vn_vi[to_left]));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700646 if (tb->lbytes + tb->rbytes >= size) {
647 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
648 tb->lbytes, -1);
649 return 1;
650 }
651
652 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653}
654
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655/* check whether L, S, R can be joined in one node */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700656static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700658 struct virtual_node *vn = tb->tb_vn;
659 int ih_size;
660 struct buffer_head *S0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700662 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700664 ih_size = 0;
665 if (vn->vn_nr_item) {
666 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
667 ih_size += IH_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700668
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700669 if (vn->vn_vi[vn->vn_nr_item - 1].
670 vi_type & VI_TYPE_RIGHT_MERGEABLE)
671 ih_size += IH_SIZE;
672 } else {
673 /* there was only one item and it will be deleted */
674 struct item_head *ih;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700676 RFALSE(B_NR_ITEMS(S0) != 1,
677 "vs-8125: item number must be 1: it is %d",
678 B_NR_ITEMS(S0));
679
680 ih = B_N_PITEM_HEAD(S0, 0);
681 if (tb->CFR[0]
682 && !comp_short_le_keys(&(ih->ih_key),
683 B_N_PDELIM_KEY(tb->CFR[0],
684 tb->rkey[0])))
685 if (is_direntry_le_ih(ih)) {
686 /* Directory must be in correct state here: that is
687 somewhere at the left side should exist first directory
688 item. But the item being deleted can not be that first
689 one because its right neighbor is item of the same
690 directory. (But first item always gets deleted in last
691 turn). So, neighbors of deleted item can be merged, so
692 we can save ih_size */
693 ih_size = IH_SIZE;
694
695 /* we might check that left neighbor exists and is of the
696 same directory */
697 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
698 "vs-8130: first directory item can not be removed until directory is not empty");
699 }
700
701 }
702
703 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
704 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
705 PROC_INFO_INC(tb->tb_sb, leaves_removable);
706 return 1;
707 }
708 return 0;
709
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710}
711
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712/* when we do not split item, lnum and rnum are numbers of entire items */
713#define SET_PAR_SHIFT_LEFT \
714if (h)\
715{\
716 int to_l;\
717 \
718 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
719 (MAX_NR_KEY(Sh) + 1 - lpar);\
720 \
721 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
722}\
723else \
724{\
725 if (lset==LEFT_SHIFT_FLOW)\
726 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
727 tb->lbytes, -1);\
728 else\
729 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
730 -1, -1);\
731}
732
Linus Torvalds1da177e2005-04-16 15:20:36 -0700733#define SET_PAR_SHIFT_RIGHT \
734if (h)\
735{\
736 int to_r;\
737 \
738 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
739 \
740 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
741}\
742else \
743{\
744 if (rset==RIGHT_SHIFT_FLOW)\
745 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
746 -1, tb->rbytes);\
747 else\
748 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
749 -1, -1);\
750}
751
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700752static void free_buffers_in_tb(struct tree_balance *p_s_tb)
753{
754 int n_counter;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700756 decrement_counters_in_path(p_s_tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700758 for (n_counter = 0; n_counter < MAX_HEIGHT; n_counter++) {
759 decrement_bcount(p_s_tb->L[n_counter]);
760 p_s_tb->L[n_counter] = NULL;
761 decrement_bcount(p_s_tb->R[n_counter]);
762 p_s_tb->R[n_counter] = NULL;
763 decrement_bcount(p_s_tb->FL[n_counter]);
764 p_s_tb->FL[n_counter] = NULL;
765 decrement_bcount(p_s_tb->FR[n_counter]);
766 p_s_tb->FR[n_counter] = NULL;
767 decrement_bcount(p_s_tb->CFL[n_counter]);
768 p_s_tb->CFL[n_counter] = NULL;
769 decrement_bcount(p_s_tb->CFR[n_counter]);
770 p_s_tb->CFR[n_counter] = NULL;
771 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700772}
773
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774/* Get new buffers for storing new nodes that are created while balancing.
775 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
776 * CARRY_ON - schedule didn't occur while the function worked;
777 * NO_DISK_SPACE - no disk space.
778 */
779/* The function is NOT SCHEDULE-SAFE! */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700780static int get_empty_nodes(struct tree_balance *p_s_tb, int n_h)
781{
782 struct buffer_head *p_s_new_bh,
783 *p_s_Sh = PATH_H_PBUFFER(p_s_tb->tb_path, n_h);
784 b_blocknr_t *p_n_blocknr, a_n_blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
785 int n_counter, n_number_of_freeblk, n_amount_needed, /* number of needed empty blocks */
786 n_retval = CARRY_ON;
787 struct super_block *p_s_sb = p_s_tb->tb_sb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700788
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700789 /* number_of_freeblk is the number of empty blocks which have been
790 acquired for use by the balancing algorithm minus the number of
791 empty blocks used in the previous levels of the analysis,
792 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
793 after empty blocks are acquired, and the balancing analysis is
794 then restarted, amount_needed is the number needed by this level
795 (n_h) of the balancing analysis.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700797 Note that for systems with many processes writing, it would be
798 more layout optimal to calculate the total number needed by all
799 levels and then to run reiserfs_new_blocks to get all of them at once. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700800
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700801 /* Initiate number_of_freeblk to the amount acquired prior to the restart of
802 the analysis or 0 if not restarted, then subtract the amount needed
803 by all of the levels of the tree below n_h. */
804 /* blknum includes S[n_h], so we subtract 1 in this calculation */
805 for (n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum;
806 n_counter < n_h; n_counter++)
807 n_number_of_freeblk -=
808 (p_s_tb->blknum[n_counter]) ? (p_s_tb->blknum[n_counter] -
809 1) : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700810
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700811 /* Allocate missing empty blocks. */
812 /* if p_s_Sh == 0 then we are getting a new root */
813 n_amount_needed = (p_s_Sh) ? (p_s_tb->blknum[n_h] - 1) : 1;
814 /* Amount_needed = the amount that we need more than the amount that we have. */
815 if (n_amount_needed > n_number_of_freeblk)
816 n_amount_needed -= n_number_of_freeblk;
817 else /* If we have enough already then there is nothing to do. */
818 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700820 /* No need to check quota - is not allocated for blocks used for formatted nodes */
821 if (reiserfs_new_form_blocknrs(p_s_tb, a_n_blocknrs,
822 n_amount_needed) == NO_DISK_SPACE)
823 return NO_DISK_SPACE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700825 /* for each blocknumber we just got, get a buffer and stick it on FEB */
826 for (p_n_blocknr = a_n_blocknrs, n_counter = 0;
827 n_counter < n_amount_needed; p_n_blocknr++, n_counter++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700828
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700829 RFALSE(!*p_n_blocknr,
830 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700832 p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr);
833 RFALSE(buffer_dirty(p_s_new_bh) ||
834 buffer_journaled(p_s_new_bh) ||
835 buffer_journal_dirty(p_s_new_bh),
836 "PAP-8140: journlaled or dirty buffer %b for the new block",
837 p_s_new_bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700839 /* Put empty buffers into the array. */
840 RFALSE(p_s_tb->FEB[p_s_tb->cur_blknum],
841 "PAP-8141: busy slot for new buffer");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700842
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700843 set_buffer_journal_new(p_s_new_bh);
844 p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
845 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700847 if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(p_s_tb))
848 n_retval = REPEAT_SEARCH;
849
850 return n_retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851}
852
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853/* Get free space of the left neighbor, which is stored in the parent
854 * node of the left neighbor. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700855static int get_lfree(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700856{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700857 struct buffer_head *l, *f;
858 int order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859
Al Viro9dce07f2008-03-29 03:07:28 +0000860 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
861 (l = tb->FL[h]) == NULL)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700862 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700863
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700864 if (f == l)
865 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
866 else {
867 order = B_NR_ITEMS(l);
868 f = l;
869 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700870
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700871 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700872}
873
Linus Torvalds1da177e2005-04-16 15:20:36 -0700874/* Get free space of the right neighbor,
875 * which is stored in the parent node of the right neighbor.
876 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700877static int get_rfree(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700878{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700879 struct buffer_head *r, *f;
880 int order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881
Al Viro9dce07f2008-03-29 03:07:28 +0000882 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
883 (r = tb->FR[h]) == NULL)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700884 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700885
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700886 if (f == r)
887 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
888 else {
889 order = 0;
890 f = r;
891 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700893 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700894
895}
896
Linus Torvalds1da177e2005-04-16 15:20:36 -0700897/* Check whether left neighbor is in memory. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700898static int is_left_neighbor_in_cache(struct tree_balance *p_s_tb, int n_h)
899{
900 struct buffer_head *p_s_father, *left;
901 struct super_block *p_s_sb = p_s_tb->tb_sb;
902 b_blocknr_t n_left_neighbor_blocknr;
903 int n_left_neighbor_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700904
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700905 if (!p_s_tb->FL[n_h]) /* Father of the left neighbor does not exist. */
906 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700907
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700908 /* Calculate father of the node to be balanced. */
909 p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700911 RFALSE(!p_s_father ||
912 !B_IS_IN_TREE(p_s_father) ||
913 !B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
914 !buffer_uptodate(p_s_father) ||
915 !buffer_uptodate(p_s_tb->FL[n_h]),
916 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
917 p_s_father, p_s_tb->FL[n_h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700918
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700919 /* Get position of the pointer to the left neighbor into the left father. */
920 n_left_neighbor_position = (p_s_father == p_s_tb->FL[n_h]) ?
921 p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->FL[n_h]);
922 /* Get left neighbor block number. */
923 n_left_neighbor_blocknr =
924 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
925 /* Look for the left neighbor in the cache. */
926 if ((left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700927
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700928 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
929 "vs-8170: left neighbor (%b %z) is not in the tree",
930 left, left);
931 put_bh(left);
932 return 1;
933 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700934
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700935 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936}
937
Linus Torvalds1da177e2005-04-16 15:20:36 -0700938#define LEFT_PARENTS 'l'
939#define RIGHT_PARENTS 'r'
940
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700941static void decrement_key(struct cpu_key *p_s_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700942{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700943 // call item specific function for this key
944 item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945}
946
Linus Torvalds1da177e2005-04-16 15:20:36 -0700947/* Calculate far left/right parent of the left/right neighbor of the current node, that
948 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
949 * Calculate left/right common parent of the current node and L[h]/R[h].
950 * Calculate left/right delimiting key position.
951 * Returns: PATH_INCORRECT - path in the tree is not correct;
952 SCHEDULE_OCCURRED - schedule occurred while the function worked;
953 * CARRY_ON - schedule didn't occur while the function worked;
954 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700955static int get_far_parent(struct tree_balance *p_s_tb,
956 int n_h,
957 struct buffer_head **pp_s_father,
958 struct buffer_head **pp_s_com_father, char c_lr_par)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700959{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700960 struct buffer_head *p_s_parent;
961 INITIALIZE_PATH(s_path_to_neighbor_father);
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -0800962 struct treepath *p_s_path = p_s_tb->tb_path;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700963 struct cpu_key s_lr_father_key;
964 int n_counter,
965 n_position = INT_MAX,
966 n_first_last_position = 0,
967 n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700969 /* Starting from F[n_h] go upwards in the tree, and look for the common
970 ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700971
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700972 n_counter = n_path_offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700974 RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET,
975 "PAP-8180: invalid path length");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700976
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700977 for (; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--) {
978 /* Check whether parent of the current buffer in the path is really parent in the tree. */
979 if (!B_IS_IN_TREE
980 (p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)))
981 return REPEAT_SEARCH;
982 /* Check whether position in the parent is correct. */
983 if ((n_position =
984 PATH_OFFSET_POSITION(p_s_path,
985 n_counter - 1)) >
986 B_NR_ITEMS(p_s_parent))
987 return REPEAT_SEARCH;
988 /* Check whether parent at the path really points to the child. */
989 if (B_N_CHILD_NUM(p_s_parent, n_position) !=
990 PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr)
991 return REPEAT_SEARCH;
992 /* Return delimiting key if position in the parent is not equal to first/last one. */
993 if (c_lr_par == RIGHT_PARENTS)
994 n_first_last_position = B_NR_ITEMS(p_s_parent);
995 if (n_position != n_first_last_position) {
996 *pp_s_com_father = p_s_parent;
997 get_bh(*pp_s_com_father);
998 /*(*pp_s_com_father = p_s_parent)->b_count++; */
999 break;
1000 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001001 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001002
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001003 /* if we are in the root of the tree, then there is no common father */
1004 if (n_counter == FIRST_PATH_ELEMENT_OFFSET) {
1005 /* Check whether first buffer in the path is the root of the tree. */
1006 if (PATH_OFFSET_PBUFFER
1007 (p_s_tb->tb_path,
1008 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1009 SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
1010 *pp_s_father = *pp_s_com_father = NULL;
1011 return CARRY_ON;
1012 }
1013 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001014 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001015
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001016 RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
1017 "PAP-8185: (%b %z) level too small",
1018 *pp_s_com_father, *pp_s_com_father);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001019
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001020 /* Check whether the common parent is locked. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001022 if (buffer_locked(*pp_s_com_father)) {
1023 __wait_on_buffer(*pp_s_com_father);
1024 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1025 decrement_bcount(*pp_s_com_father);
1026 return REPEAT_SEARCH;
1027 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001029
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001030 /* So, we got common parent of the current node and its left/right neighbor.
1031 Now we are geting the parent of the left/right neighbor. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001032
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001033 /* Form key to get parent of the left/right neighbor. */
1034 le_key2cpu_key(&s_lr_father_key,
1035 B_N_PDELIM_KEY(*pp_s_com_father,
1036 (c_lr_par ==
1037 LEFT_PARENTS) ? (p_s_tb->lkey[n_h - 1] =
1038 n_position -
1039 1) : (p_s_tb->rkey[n_h -
1040 1] =
1041 n_position)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001042
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001043 if (c_lr_par == LEFT_PARENTS)
1044 decrement_key(&s_lr_father_key);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001045
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001046 if (search_by_key
1047 (p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1048 n_h + 1) == IO_ERROR)
1049 // path is released
1050 return IO_ERROR;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001052 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1053 decrement_counters_in_path(&s_path_to_neighbor_father);
1054 decrement_bcount(*pp_s_com_father);
1055 return REPEAT_SEARCH;
1056 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001057
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001058 *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1059
1060 RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
1061 "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
1062 RFALSE(s_path_to_neighbor_father.path_length <
1063 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1064
1065 s_path_to_neighbor_father.path_length--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066 decrement_counters_in_path(&s_path_to_neighbor_father);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001067 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001068}
1069
Linus Torvalds1da177e2005-04-16 15:20:36 -07001070/* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
1071 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
1072 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
1073 * Calculate numbers of left and right delimiting keys position: lkey[n_path_offset], rkey[n_path_offset].
1074 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1075 * CARRY_ON - schedule didn't occur while the function worked;
1076 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001077static int get_parents(struct tree_balance *p_s_tb, int n_h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001078{
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -08001079 struct treepath *p_s_path = p_s_tb->tb_path;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001080 int n_position,
1081 n_ret_value,
1082 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1083 struct buffer_head *p_s_curf, *p_s_curcf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001084
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001085 /* Current node is the root of the tree or will be root of the tree */
1086 if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1087 /* The root can not have parents.
1088 Release nodes which previously were obtained as parents of the current node neighbors. */
1089 decrement_bcount(p_s_tb->FL[n_h]);
1090 decrement_bcount(p_s_tb->CFL[n_h]);
1091 decrement_bcount(p_s_tb->FR[n_h]);
1092 decrement_bcount(p_s_tb->CFR[n_h]);
1093 p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] =
1094 p_s_tb->CFR[n_h] = NULL;
1095 return CARRY_ON;
1096 }
1097
1098 /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1099 if ((n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1))) {
1100 /* Current node is not the first child of its parent. */
1101 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1102 p_s_curf = p_s_curcf =
1103 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1104 get_bh(p_s_curf);
1105 get_bh(p_s_curf);
1106 p_s_tb->lkey[n_h] = n_position - 1;
1107 } else {
1108 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1109 Calculate current common parent of L[n_path_offset] and the current node. Note that
1110 CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1111 Calculate lkey[n_path_offset]. */
1112 if ((n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
1113 &p_s_curcf,
1114 LEFT_PARENTS)) != CARRY_ON)
1115 return n_ret_value;
1116 }
1117
Linus Torvalds1da177e2005-04-16 15:20:36 -07001118 decrement_bcount(p_s_tb->FL[n_h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001119 p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001120 decrement_bcount(p_s_tb->CFL[n_h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001121 p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001122
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001123 RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1124 (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1125 "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001126
1127/* Get parent FR[n_h] of R[n_h]. */
1128
1129/* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001130 if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001131/* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1132 Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1133 not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001134 if ((n_ret_value =
1135 get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf,
1136 RIGHT_PARENTS)) != CARRY_ON)
1137 return n_ret_value;
1138 } else {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001139/* Current node is not the last child of its parent F[n_h]. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001140 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1141 p_s_curf = p_s_curcf =
1142 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1143 get_bh(p_s_curf);
1144 get_bh(p_s_curf);
1145 p_s_tb->rkey[n_h] = n_position;
1146 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001147
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001148 decrement_bcount(p_s_tb->FR[n_h]);
1149 p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001151 decrement_bcount(p_s_tb->CFR[n_h]);
1152 p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001153
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001154 RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1155 (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1156 "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
1157
1158 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001159}
1160
Linus Torvalds1da177e2005-04-16 15:20:36 -07001161/* it is possible to remove node as result of shiftings to
1162 neighbors even when we insert or paste item. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001163static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1164 struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001165{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001166 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1167 int levbytes = tb->insert_size[h];
1168 struct item_head *ih;
1169 struct reiserfs_key *r_key = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001171 ih = B_N_PITEM_HEAD(Sh, 0);
1172 if (tb->CFR[h])
1173 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
1174
1175 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1176 /* shifting may merge items which might save space */
1177 -
1178 ((!h
1179 && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1180 -
1181 ((!h && r_key
1182 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1183 + ((h) ? KEY_SIZE : 0)) {
1184 /* node can not be removed */
1185 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1186 if (!h)
1187 tb->s0num =
1188 B_NR_ITEMS(Sh) +
1189 ((mode == M_INSERT) ? 1 : 0);
1190 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1191 return NO_BALANCING_NEEDED;
1192 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001193 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001194 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1195 return !NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001196}
1197
Linus Torvalds1da177e2005-04-16 15:20:36 -07001198/* Check whether current node S[h] is balanced when increasing its size by
1199 * Inserting or Pasting.
1200 * Calculate parameters for balancing for current level h.
1201 * Parameters:
1202 * tb tree_balance structure;
1203 * h current level of the node;
1204 * inum item number in S[h];
1205 * mode i - insert, p - paste;
1206 * Returns: 1 - schedule occurred;
1207 * 0 - balancing for higher levels needed;
1208 * -1 - no balancing for higher levels needed;
1209 * -2 - no disk space.
1210 */
1211/* ip means Inserting or Pasting */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001212static int ip_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001213{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001214 struct virtual_node *vn = tb->tb_vn;
1215 int levbytes, /* Number of bytes that must be inserted into (value
1216 is negative if bytes are deleted) buffer which
1217 contains node being balanced. The mnemonic is
1218 that the attempted change in node space used level
1219 is levbytes bytes. */
1220 n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001221
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001222 int lfree, sfree, rfree /* free space in L, S and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001223
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001224 /* nver is short for number of vertixes, and lnver is the number if
1225 we shift to the left, rnver is the number if we shift to the
1226 right, and lrnver is the number if we shift in both directions.
1227 The goal is to minimize first the number of vertixes, and second,
1228 the number of vertixes whose contents are changed by shifting,
1229 and third the number of uncached vertixes whose contents are
1230 changed by shifting and must be read from disk. */
1231 int nver, lnver, rnver, lrnver;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001232
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001233 /* used at leaf level only, S0 = S[0] is the node being balanced,
1234 sInum [ I = 0,1,2 ] is the number of items that will
1235 remain in node SI after balancing. S1 and S2 are new
1236 nodes that might be created. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001237
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001238 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
1239 where 4th parameter is s1bytes and 5th - s2bytes
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001241 short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
1242 0,1 - do not shift and do not shift but bottle
1243 2 - shift only whole item to left
1244 3 - shift to left and bottle as much as possible
1245 4,5 - shift to right (whole items and as much as possible
1246 6,7 - shift to both directions (whole items and as much as possible)
1247 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001248
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001249 /* Sh is the node whose balance is currently being checked */
1250 struct buffer_head *Sh;
1251
1252 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1253 levbytes = tb->insert_size[h];
1254
1255 /* Calculate balance parameters for creating new root. */
1256 if (!Sh) {
1257 if (!h)
1258 reiserfs_panic(tb->tb_sb,
1259 "vs-8210: ip_check_balance: S[0] can not be 0");
1260 switch (n_ret_value = get_empty_nodes(tb, h)) {
1261 case CARRY_ON:
1262 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1263 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1264
1265 case NO_DISK_SPACE:
1266 case REPEAT_SEARCH:
1267 return n_ret_value;
1268 default:
1269 reiserfs_panic(tb->tb_sb,
1270 "vs-8215: ip_check_balance: incorrect return value of get_empty_nodes");
1271 }
1272 }
1273
1274 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */
1275 return n_ret_value;
1276
1277 sfree = B_FREE_SPACE(Sh);
1278
1279 /* get free space of neighbors */
1280 rfree = get_rfree(tb, h);
1281 lfree = get_lfree(tb, h);
1282
1283 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1284 NO_BALANCING_NEEDED)
1285 /* and new item fits into node S[h] without any shifting */
1286 return NO_BALANCING_NEEDED;
1287
1288 create_virtual_node(tb, h);
1289
1290 /*
1291 determine maximal number of items we can shift to the left neighbor (in tb structure)
1292 and the maximal number of bytes that can flow to the left neighbor
1293 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1294 */
1295 check_left(tb, h, lfree);
1296
1297 /*
1298 determine maximal number of items we can shift to the right neighbor (in tb structure)
1299 and the maximal number of bytes that can flow to the right neighbor
1300 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1301 */
1302 check_right(tb, h, rfree);
1303
1304 /* all contents of internal node S[h] can be moved into its
1305 neighbors, S[h] will be removed after balancing */
1306 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1307 int to_r;
1308
1309 /* Since we are working on internal nodes, and our internal
1310 nodes have fixed size entries, then we can balance by the
1311 number of items rather than the space they consume. In this
1312 routine we set the left node equal to the right node,
1313 allowing a difference of less than or equal to 1 child
1314 pointer. */
1315 to_r =
1316 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1317 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1318 tb->rnum[h]);
1319 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1320 -1, -1);
1321 return CARRY_ON;
1322 }
1323
1324 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1325 RFALSE(h &&
1326 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1327 tb->rnum[h] >= vn->vn_nr_item + 1),
1328 "vs-8220: tree is not balanced on internal level");
1329 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1330 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1331 "vs-8225: tree is not balanced on leaf level");
1332
1333 /* all contents of S[0] can be moved into its neighbors
1334 S[0] will be removed after balancing. */
1335 if (!h && is_leaf_removable(tb))
1336 return CARRY_ON;
1337
1338 /* why do we perform this check here rather than earlier??
1339 Answer: we can win 1 node in some cases above. Moreover we
1340 checked it above, when we checked, that S[0] is not removable
1341 in principle */
1342 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1343 if (!h)
1344 tb->s0num = vn->vn_nr_item;
1345 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1346 return NO_BALANCING_NEEDED;
1347 }
1348
1349 {
1350 int lpar, rpar, nset, lset, rset, lrset;
1351 /*
1352 * regular overflowing of the node
1353 */
1354
1355 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
1356 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
1357 nset, lset, rset, lrset - shows, whether flowing items give better packing
1358 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359#define FLOW 1
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001360#define NO_FLOW 0 /* do not any splitting */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001362 /* we choose one the following */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363#define NOTHING_SHIFT_NO_FLOW 0
1364#define NOTHING_SHIFT_FLOW 5
1365#define LEFT_SHIFT_NO_FLOW 10
1366#define LEFT_SHIFT_FLOW 15
1367#define RIGHT_SHIFT_NO_FLOW 20
1368#define RIGHT_SHIFT_FLOW 25
1369#define LR_SHIFT_NO_FLOW 30
1370#define LR_SHIFT_FLOW 35
1371
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001372 lpar = tb->lnum[h];
1373 rpar = tb->rnum[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001374
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001375 /* calculate number of blocks S[h] must be split into when
1376 nothing is shifted to the neighbors,
1377 as well as number of items in each part of the split node (s012 numbers),
1378 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1379 nset = NOTHING_SHIFT_NO_FLOW;
1380 nver = get_num_ver(vn->vn_mode, tb, h,
1381 0, -1, h ? vn->vn_nr_item : 0, -1,
1382 snum012, NO_FLOW);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001383
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001384 if (!h) {
1385 int nver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001387 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1388 nver1 = get_num_ver(vn->vn_mode, tb, h,
1389 0, -1, 0, -1,
1390 snum012 + NOTHING_SHIFT_FLOW, FLOW);
1391 if (nver > nver1)
1392 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1393 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001394
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001395 /* calculate number of blocks S[h] must be split into when
1396 l_shift_num first items and l_shift_bytes of the right most
1397 liquid item to be shifted are shifted to the left neighbor,
1398 as well as number of items in each part of the splitted node (s012 numbers),
1399 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1400 */
1401 lset = LEFT_SHIFT_NO_FLOW;
1402 lnver = get_num_ver(vn->vn_mode, tb, h,
1403 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1404 -1, h ? vn->vn_nr_item : 0, -1,
1405 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1406 if (!h) {
1407 int lnver1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001408
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001409 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1410 lpar -
1411 ((tb->lbytes != -1) ? 1 : 0),
1412 tb->lbytes, 0, -1,
1413 snum012 + LEFT_SHIFT_FLOW, FLOW);
1414 if (lnver > lnver1)
1415 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1416 }
1417
1418 /* calculate number of blocks S[h] must be split into when
1419 r_shift_num first items and r_shift_bytes of the left most
1420 liquid item to be shifted are shifted to the right neighbor,
1421 as well as number of items in each part of the splitted node (s012 numbers),
1422 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1423 */
1424 rset = RIGHT_SHIFT_NO_FLOW;
1425 rnver = get_num_ver(vn->vn_mode, tb, h,
1426 0, -1,
1427 h ? (vn->vn_nr_item - rpar) : (rpar -
1428 ((tb->
1429 rbytes !=
1430 -1) ? 1 :
1431 0)), -1,
1432 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1433 if (!h) {
1434 int rnver1;
1435
1436 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1437 0, -1,
1438 (rpar -
1439 ((tb->rbytes != -1) ? 1 : 0)),
1440 tb->rbytes,
1441 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1442
1443 if (rnver > rnver1)
1444 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1445 }
1446
1447 /* calculate number of blocks S[h] must be split into when
1448 items are shifted in both directions,
1449 as well as number of items in each part of the splitted node (s012 numbers),
1450 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1451 */
1452 lrset = LR_SHIFT_NO_FLOW;
1453 lrnver = get_num_ver(vn->vn_mode, tb, h,
1454 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1455 -1,
1456 h ? (vn->vn_nr_item - rpar) : (rpar -
1457 ((tb->
1458 rbytes !=
1459 -1) ? 1 :
1460 0)), -1,
1461 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1462 if (!h) {
1463 int lrnver1;
1464
1465 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1466 lpar -
1467 ((tb->lbytes != -1) ? 1 : 0),
1468 tb->lbytes,
1469 (rpar -
1470 ((tb->rbytes != -1) ? 1 : 0)),
1471 tb->rbytes,
1472 snum012 + LR_SHIFT_FLOW, FLOW);
1473 if (lrnver > lrnver1)
1474 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1475 }
1476
1477 /* Our general shifting strategy is:
1478 1) to minimized number of new nodes;
1479 2) to minimized number of neighbors involved in shifting;
1480 3) to minimized number of disk reads; */
1481
1482 /* we can win TWO or ONE nodes by shifting in both directions */
1483 if (lrnver < lnver && lrnver < rnver) {
1484 RFALSE(h &&
1485 (tb->lnum[h] != 1 ||
1486 tb->rnum[h] != 1 ||
1487 lrnver != 1 || rnver != 2 || lnver != 2
1488 || h != 1), "vs-8230: bad h");
1489 if (lrset == LR_SHIFT_FLOW)
1490 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1491 lrnver, snum012 + lrset,
1492 tb->lbytes, tb->rbytes);
1493 else
1494 set_parameters(tb, h,
1495 tb->lnum[h] -
1496 ((tb->lbytes == -1) ? 0 : 1),
1497 tb->rnum[h] -
1498 ((tb->rbytes == -1) ? 0 : 1),
1499 lrnver, snum012 + lrset, -1, -1);
1500
1501 return CARRY_ON;
1502 }
1503
1504 /* if shifting doesn't lead to better packing then don't shift */
1505 if (nver == lrnver) {
1506 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1507 -1);
1508 return CARRY_ON;
1509 }
1510
1511 /* now we know that for better packing shifting in only one
1512 direction either to the left or to the right is required */
1513
1514 /* if shifting to the left is better than shifting to the right */
1515 if (lnver < rnver) {
1516 SET_PAR_SHIFT_LEFT;
1517 return CARRY_ON;
1518 }
1519
1520 /* if shifting to the right is better than shifting to the left */
1521 if (lnver > rnver) {
1522 SET_PAR_SHIFT_RIGHT;
1523 return CARRY_ON;
1524 }
1525
1526 /* now shifting in either direction gives the same number
1527 of nodes and we can make use of the cached neighbors */
1528 if (is_left_neighbor_in_cache(tb, h)) {
1529 SET_PAR_SHIFT_LEFT;
1530 return CARRY_ON;
1531 }
1532
1533 /* shift to the right independently on whether the right neighbor in cache or not */
1534 SET_PAR_SHIFT_RIGHT;
1535 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001536 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001537}
1538
Linus Torvalds1da177e2005-04-16 15:20:36 -07001539/* Check whether current node S[h] is balanced when Decreasing its size by
1540 * Deleting or Cutting for INTERNAL node of S+tree.
1541 * Calculate parameters for balancing for current level h.
1542 * Parameters:
1543 * tb tree_balance structure;
1544 * h current level of the node;
1545 * inum item number in S[h];
1546 * mode i - insert, p - paste;
1547 * Returns: 1 - schedule occurred;
1548 * 0 - balancing for higher levels needed;
1549 * -1 - no balancing for higher levels needed;
1550 * -2 - no disk space.
1551 *
1552 * Note: Items of internal nodes have fixed size, so the balance condition for
1553 * the internal part of S+tree is as for the B-trees.
1554 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001555static int dc_check_balance_internal(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001556{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001557 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001558
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001559 /* Sh is the node whose balance is currently being checked,
1560 and Fh is its father. */
1561 struct buffer_head *Sh, *Fh;
1562 int maxsize, n_ret_value;
1563 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001564
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001565 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1566 Fh = PATH_H_PPARENT(tb->tb_path, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001567
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001568 maxsize = MAX_CHILD_SIZE(Sh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001569
1570/* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1571/* new_nr_item = number of items node would have if operation is */
1572/* performed without balancing (new_nr_item); */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001573 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001574
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001575 if (!Fh) { /* S[h] is the root. */
1576 if (vn->vn_nr_item > 0) {
1577 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1578 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1579 }
1580 /* new_nr_item == 0.
1581 * Current root will be deleted resulting in
1582 * decrementing the tree height. */
1583 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1584 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001585 }
1586
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001587 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1588 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001589
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001590 /* get free space of neighbors */
1591 rfree = get_rfree(tb, h);
1592 lfree = get_lfree(tb, h);
1593
1594 /* determine maximal number of items we can fit into neighbors */
1595 check_left(tb, h, lfree);
1596 check_right(tb, h, rfree);
1597
1598 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
1599 * In this case we balance only if it leads to better packing. */
1600 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
1601 * which is impossible with greater values of new_nr_item. */
1602 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1603 /* All contents of S[h] can be moved to L[h]. */
1604 int n;
1605 int order_L;
1606
1607 order_L =
1608 ((n =
1609 PATH_H_B_ITEM_ORDER(tb->tb_path,
1610 h)) ==
1611 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1612 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1613 (DC_SIZE + KEY_SIZE);
1614 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1615 -1);
1616 return CARRY_ON;
1617 }
1618
1619 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1620 /* All contents of S[h] can be moved to R[h]. */
1621 int n;
1622 int order_R;
1623
1624 order_R =
1625 ((n =
1626 PATH_H_B_ITEM_ORDER(tb->tb_path,
1627 h)) ==
1628 B_NR_ITEMS(Fh)) ? 0 : n + 1;
1629 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1630 (DC_SIZE + KEY_SIZE);
1631 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1632 -1);
1633 return CARRY_ON;
1634 }
1635 }
1636
1637 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1638 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1639 int to_r;
1640
1641 to_r =
1642 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1643 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1644 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1645 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1646 0, NULL, -1, -1);
1647 return CARRY_ON;
1648 }
1649
1650 /* Balancing does not lead to better packing. */
1651 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1652 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001653 }
1654
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001655 /* Current node contain insufficient number of items. Balancing is required. */
1656 /* Check whether we can merge S[h] with left neighbor. */
1657 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1658 if (is_left_neighbor_in_cache(tb, h)
1659 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1660 int n;
1661 int order_L;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001662
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001663 order_L =
1664 ((n =
1665 PATH_H_B_ITEM_ORDER(tb->tb_path,
1666 h)) ==
1667 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1668 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1669 KEY_SIZE);
1670 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1671 return CARRY_ON;
1672 }
1673
1674 /* Check whether we can merge S[h] with right neighbor. */
1675 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1676 int n;
1677 int order_R;
1678
1679 order_R =
1680 ((n =
1681 PATH_H_B_ITEM_ORDER(tb->tb_path,
1682 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1683 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1684 KEY_SIZE);
1685 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1686 return CARRY_ON;
1687 }
1688
1689 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1690 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1691 int to_r;
1692
1693 to_r =
1694 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1695 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1696 tb->rnum[h]);
1697 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1698 -1, -1);
1699 return CARRY_ON;
1700 }
1701
1702 /* For internal nodes try to borrow item from a neighbor */
1703 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1704
1705 /* Borrow one or two items from caching neighbor */
1706 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1707 int from_l;
1708
1709 from_l =
1710 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1711 1) / 2 - (vn->vn_nr_item + 1);
1712 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1713 return CARRY_ON;
1714 }
1715
1716 set_parameters(tb, h, 0,
1717 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1718 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001719 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001720}
1721
Linus Torvalds1da177e2005-04-16 15:20:36 -07001722/* Check whether current node S[h] is balanced when Decreasing its size by
1723 * Deleting or Truncating for LEAF node of S+tree.
1724 * Calculate parameters for balancing for current level h.
1725 * Parameters:
1726 * tb tree_balance structure;
1727 * h current level of the node;
1728 * inum item number in S[h];
1729 * mode i - insert, p - paste;
1730 * Returns: 1 - schedule occurred;
1731 * 0 - balancing for higher levels needed;
1732 * -1 - no balancing for higher levels needed;
1733 * -2 - no disk space.
1734 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001735static int dc_check_balance_leaf(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001736{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001737 struct virtual_node *vn = tb->tb_vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001738
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001739 /* Number of bytes that must be deleted from
1740 (value is negative if bytes are deleted) buffer which
1741 contains node being balanced. The mnemonic is that the
1742 attempted change in node space used level is levbytes bytes. */
1743 int levbytes;
1744 /* the maximal item size */
1745 int maxsize, n_ret_value;
1746 /* S0 is the node whose balance is currently being checked,
1747 and F0 is its father. */
1748 struct buffer_head *S0, *F0;
1749 int lfree, rfree /* free space in L and R */ ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001750
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001751 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1752 F0 = PATH_H_PPARENT(tb->tb_path, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001753
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001754 levbytes = tb->insert_size[h];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001755
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001756 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001757
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001758 if (!F0) { /* S[0] is the root now. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001759
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001760 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1761 "vs-8240: attempt to create empty buffer tree");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001762
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001763 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1764 return NO_BALANCING_NEEDED;
1765 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001766
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001767 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1768 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001769
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001770 /* get free space of neighbors */
1771 rfree = get_rfree(tb, h);
1772 lfree = get_lfree(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001773
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001774 create_virtual_node(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001775
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001776 /* if 3 leaves can be merge to one, set parameters and return */
1777 if (are_leaves_removable(tb, lfree, rfree))
1778 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001779
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001780 /* determine maximal number of items we can shift to the left/right neighbor
1781 and the maximal number of bytes that can flow to the left/right neighbor
1782 from the left/right most liquid item that cannot be shifted from S[0] entirely
1783 */
1784 check_left(tb, h, lfree);
1785 check_right(tb, h, rfree);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001786
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001787 /* check whether we can merge S with left neighbor. */
1788 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1789 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 */
1790 !tb->FR[h]) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001791
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001792 RFALSE(!tb->FL[h],
1793 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001794
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001795 /* set parameter to merge S[0] with its left neighbor */
1796 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1797 return CARRY_ON;
1798 }
1799
1800 /* check whether we can merge S[0] with right neighbor. */
1801 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1802 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
1803 return CARRY_ON;
1804 }
1805
1806 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1807 if (is_leaf_removable(tb))
1808 return CARRY_ON;
1809
1810 /* Balancing is not required. */
1811 tb->s0num = vn->vn_nr_item;
1812 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1813 return NO_BALANCING_NEEDED;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001814}
1815
Linus Torvalds1da177e2005-04-16 15:20:36 -07001816/* Check whether current node S[h] is balanced when Decreasing its size by
1817 * Deleting or Cutting.
1818 * Calculate parameters for balancing for current level h.
1819 * Parameters:
1820 * tb tree_balance structure;
1821 * h current level of the node;
1822 * inum item number in S[h];
1823 * mode d - delete, c - cut.
1824 * Returns: 1 - schedule occurred;
1825 * 0 - balancing for higher levels needed;
1826 * -1 - no balancing for higher levels needed;
1827 * -2 - no disk space.
1828 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001829static int dc_check_balance(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001830{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001831 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1832 "vs-8250: S is not initialized");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001833
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001834 if (h)
1835 return dc_check_balance_internal(tb, h);
1836 else
1837 return dc_check_balance_leaf(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001838}
1839
Linus Torvalds1da177e2005-04-16 15:20:36 -07001840/* Check whether current node S[h] is balanced.
1841 * Calculate parameters for balancing for current level h.
1842 * Parameters:
1843 *
1844 * tb tree_balance structure:
1845 *
1846 * tb is a large structure that must be read about in the header file
1847 * at the same time as this procedure if the reader is to successfully
1848 * understand this procedure
1849 *
1850 * h current level of the node;
1851 * inum item number in S[h];
1852 * mode i - insert, p - paste, d - delete, c - cut.
1853 * Returns: 1 - schedule occurred;
1854 * 0 - balancing for higher levels needed;
1855 * -1 - no balancing for higher levels needed;
1856 * -2 - no disk space.
1857 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001858static int check_balance(int mode,
1859 struct tree_balance *tb,
1860 int h,
1861 int inum,
1862 int pos_in_item,
1863 struct item_head *ins_ih, const void *data)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001864{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001865 struct virtual_node *vn;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001866
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001867 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
1868 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
1869 vn->vn_mode = mode;
1870 vn->vn_affected_item_num = inum;
1871 vn->vn_pos_in_item = pos_in_item;
1872 vn->vn_ins_ih = ins_ih;
1873 vn->vn_data = data;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001874
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001875 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1876 "vs-8255: ins_ih can not be 0 in insert mode");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001877
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001878 if (tb->insert_size[h] > 0)
1879 /* Calculate balance parameters when size of node is increasing. */
1880 return ip_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001881
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001882 /* Calculate balance parameters when size of node is decreasing. */
1883 return dc_check_balance(tb, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001884}
1885
Linus Torvalds1da177e2005-04-16 15:20:36 -07001886/* Check whether parent at the path is the really parent of the current node.*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001887static int get_direct_parent(struct tree_balance *p_s_tb, int n_h)
1888{
1889 struct buffer_head *p_s_bh;
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -08001890 struct treepath *p_s_path = p_s_tb->tb_path;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001891 int n_position,
1892 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001893
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001894 /* We are in the root or in the new root. */
1895 if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1896
1897 RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
1898 "PAP-8260: invalid offset in the path");
1899
1900 if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->
1901 b_blocknr == SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
1902 /* Root is not changed. */
1903 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
1904 PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
1905 return CARRY_ON;
1906 }
1907 return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001908 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001909
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001910 if (!B_IS_IN_TREE
1911 (p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)))
1912 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001913
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001914 if ((n_position =
1915 PATH_OFFSET_POSITION(p_s_path,
1916 n_path_offset - 1)) > B_NR_ITEMS(p_s_bh))
1917 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001918
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001919 if (B_N_CHILD_NUM(p_s_bh, n_position) !=
1920 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr)
1921 /* Parent in the path is not parent of the current node in the tree. */
1922 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001923
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001924 if (buffer_locked(p_s_bh)) {
1925 __wait_on_buffer(p_s_bh);
1926 if (FILESYSTEM_CHANGED_TB(p_s_tb))
1927 return REPEAT_SEARCH;
1928 }
1929
1930 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001931}
1932
Linus Torvalds1da177e2005-04-16 15:20:36 -07001933/* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1934 * of S[n_h] we
1935 * need in order to balance S[n_h], and get them if necessary.
1936 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1937 * CARRY_ON - schedule didn't occur while the function worked;
1938 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001939static int get_neighbors(struct tree_balance *p_s_tb, int n_h)
1940{
1941 int n_child_position,
1942 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
1943 unsigned long n_son_number;
1944 struct super_block *p_s_sb = p_s_tb->tb_sb;
1945 struct buffer_head *p_s_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001946
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001947 PROC_INFO_INC(p_s_sb, get_neighbors[n_h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001948
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001949 if (p_s_tb->lnum[n_h]) {
1950 /* We need left neighbor to balance S[n_h]. */
1951 PROC_INFO_INC(p_s_sb, need_l_neighbor[n_h]);
1952 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001953
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001954 RFALSE(p_s_bh == p_s_tb->FL[n_h] &&
1955 !PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
1956 "PAP-8270: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001957
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001958 n_child_position =
1959 (p_s_bh ==
1960 p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->
1961 FL[n_h]);
1962 n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
1963 p_s_bh = sb_bread(p_s_sb, n_son_number);
1964 if (!p_s_bh)
1965 return IO_ERROR;
1966 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1967 decrement_bcount(p_s_bh);
1968 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
1969 return REPEAT_SEARCH;
1970 }
1971
1972 RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
1973 n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
1974 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
1975 p_s_bh->b_blocknr, "PAP-8275: invalid parent");
1976 RFALSE(!B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child");
1977 RFALSE(!n_h &&
1978 B_FREE_SPACE(p_s_bh) !=
1979 MAX_CHILD_SIZE(p_s_bh) -
1980 dc_size(B_N_CHILD(p_s_tb->FL[0], n_child_position)),
1981 "PAP-8290: invalid child size of left neighbor");
1982
1983 decrement_bcount(p_s_tb->L[n_h]);
1984 p_s_tb->L[n_h] = p_s_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001985 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001986
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001987 if (p_s_tb->rnum[n_h]) { /* We need right neighbor to balance S[n_path_offset]. */
1988 PROC_INFO_INC(p_s_sb, need_r_neighbor[n_h]);
1989 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001990
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001991 RFALSE(p_s_bh == p_s_tb->FR[n_h] &&
1992 PATH_OFFSET_POSITION(p_s_tb->tb_path,
1993 n_path_offset) >=
1994 B_NR_ITEMS(p_s_bh),
1995 "PAP-8295: invalid position in the parent");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001996
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001997 n_child_position =
1998 (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0;
1999 n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
2000 p_s_bh = sb_bread(p_s_sb, n_son_number);
2001 if (!p_s_bh)
2002 return IO_ERROR;
2003 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2004 decrement_bcount(p_s_bh);
2005 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
2006 return REPEAT_SEARCH;
2007 }
2008 decrement_bcount(p_s_tb->R[n_h]);
2009 p_s_tb->R[n_h] = p_s_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002010
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002011 RFALSE(!n_h
2012 && B_FREE_SPACE(p_s_bh) !=
2013 MAX_CHILD_SIZE(p_s_bh) -
2014 dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)),
2015 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2016 B_FREE_SPACE(p_s_bh), MAX_CHILD_SIZE(p_s_bh),
2017 dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)));
2018
Linus Torvalds1da177e2005-04-16 15:20:36 -07002019 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002020 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002021}
2022
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002023static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002024{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002025 int max_num_of_items;
2026 int max_num_of_entries;
2027 unsigned long blocksize = sb->s_blocksize;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002028
2029#define MIN_NAME_LEN 1
2030
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002031 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2032 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2033 (DEH_SIZE + MIN_NAME_LEN);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002034
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002035 return sizeof(struct virtual_node) +
2036 max(max_num_of_items * sizeof(struct virtual_item),
2037 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2038 (max_num_of_entries - 1) * sizeof(__u16));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002039}
2040
Linus Torvalds1da177e2005-04-16 15:20:36 -07002041/* maybe we should fail balancing we are going to perform when kmalloc
2042 fails several times. But now it will loop until kmalloc gets
2043 required memory */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002044static int get_mem_for_virtual_node(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002045{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002046 int check_fs = 0;
2047 int size;
2048 char *buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002049
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002050 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002051
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002052 if (size > tb->vn_buf_size) {
2053 /* we have to allocate more memory for virtual node */
2054 if (tb->vn_buf) {
2055 /* free memory allocated before */
Pekka Enbergd739b422006-02-01 03:06:43 -08002056 kfree(tb->vn_buf);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002057 /* this is not needed if kfree is atomic */
2058 check_fs = 1;
2059 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002060
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002061 /* virtual node requires now more memory */
2062 tb->vn_buf_size = size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002063
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002064 /* get memory for virtual item */
Pekka Enbergd739b422006-02-01 03:06:43 -08002065 buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002066 if (!buf) {
2067 /* getting memory with GFP_KERNEL priority may involve
2068 balancing now (due to indirect_to_direct conversion on
2069 dcache shrinking). So, release path and collected
2070 resources here */
2071 free_buffers_in_tb(tb);
Pekka Enbergd739b422006-02-01 03:06:43 -08002072 buf = kmalloc(size, GFP_NOFS);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002073 if (!buf) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002074 tb->vn_buf_size = 0;
2075 }
2076 tb->vn_buf = buf;
2077 schedule();
2078 return REPEAT_SEARCH;
2079 }
2080
2081 tb->vn_buf = buf;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002082 }
2083
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002084 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2085 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002086
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002087 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002088}
2089
Linus Torvalds1da177e2005-04-16 15:20:36 -07002090#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002091static void tb_buffer_sanity_check(struct super_block *p_s_sb,
2092 struct buffer_head *p_s_bh,
2093 const char *descr, int level)
2094{
2095 if (p_s_bh) {
2096 if (atomic_read(&(p_s_bh->b_count)) <= 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002097
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002098 reiserfs_panic(p_s_sb,
2099 "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n",
2100 descr, level, p_s_bh);
2101 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002102
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002103 if (!buffer_uptodate(p_s_bh)) {
2104 reiserfs_panic(p_s_sb,
2105 "jmacd-2: tb_buffer_sanity_check(): buffer is not up to date %s[%d] (%b)\n",
2106 descr, level, p_s_bh);
2107 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002108
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002109 if (!B_IS_IN_TREE(p_s_bh)) {
2110 reiserfs_panic(p_s_sb,
2111 "jmacd-3: tb_buffer_sanity_check(): buffer is not in tree %s[%d] (%b)\n",
2112 descr, level, p_s_bh);
2113 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002114
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002115 if (p_s_bh->b_bdev != p_s_sb->s_bdev) {
2116 reiserfs_panic(p_s_sb,
2117 "jmacd-4: tb_buffer_sanity_check(): buffer has wrong device %s[%d] (%b)\n",
2118 descr, level, p_s_bh);
2119 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002120
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002121 if (p_s_bh->b_size != p_s_sb->s_blocksize) {
2122 reiserfs_panic(p_s_sb,
2123 "jmacd-5: tb_buffer_sanity_check(): buffer has wrong blocksize %s[%d] (%b)\n",
2124 descr, level, p_s_bh);
2125 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002126
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002127 if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(p_s_sb)) {
2128 reiserfs_panic(p_s_sb,
2129 "jmacd-6: tb_buffer_sanity_check(): buffer block number too high %s[%d] (%b)\n",
2130 descr, level, p_s_bh);
2131 }
2132 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002133}
2134#else
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002135static void tb_buffer_sanity_check(struct super_block *p_s_sb,
2136 struct buffer_head *p_s_bh,
2137 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
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002147static int wait_tb_buffers_until_unlocked(struct tree_balance *p_s_tb)
2148{
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
2159 for (i = p_s_tb->tb_path->path_length;
2160 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2161 if (PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2162 /* 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
2166 if (PATH_PLAST_BUFFER(p_s_tb->tb_path) ==
2167 PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2168 tb_buffer_sanity_check(p_s_tb->tb_sb,
2169 PATH_OFFSET_PBUFFER
2170 (p_s_tb->tb_path,
2171 i), "S",
2172 p_s_tb->tb_path->
2173 path_length - i);
2174 }
2175#endif
2176 if (!clear_all_dirty_bits(p_s_tb->tb_sb,
2177 PATH_OFFSET_PBUFFER
2178 (p_s_tb->tb_path,
2179 i))) {
2180 locked =
2181 PATH_OFFSET_PBUFFER(p_s_tb->tb_path,
2182 i);
2183 }
2184 }
2185 }
2186
2187 for (i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i];
2188 i++) {
2189
2190 if (p_s_tb->lnum[i]) {
2191
2192 if (p_s_tb->L[i]) {
2193 tb_buffer_sanity_check(p_s_tb->tb_sb,
2194 p_s_tb->L[i],
2195 "L", i);
2196 if (!clear_all_dirty_bits
2197 (p_s_tb->tb_sb, p_s_tb->L[i]))
2198 locked = p_s_tb->L[i];
2199 }
2200
2201 if (!locked && p_s_tb->FL[i]) {
2202 tb_buffer_sanity_check(p_s_tb->tb_sb,
2203 p_s_tb->FL[i],
2204 "FL", i);
2205 if (!clear_all_dirty_bits
2206 (p_s_tb->tb_sb, p_s_tb->FL[i]))
2207 locked = p_s_tb->FL[i];
2208 }
2209
2210 if (!locked && p_s_tb->CFL[i]) {
2211 tb_buffer_sanity_check(p_s_tb->tb_sb,
2212 p_s_tb->CFL[i],
2213 "CFL", i);
2214 if (!clear_all_dirty_bits
2215 (p_s_tb->tb_sb, p_s_tb->CFL[i]))
2216 locked = p_s_tb->CFL[i];
2217 }
2218
2219 }
2220
2221 if (!locked && (p_s_tb->rnum[i])) {
2222
2223 if (p_s_tb->R[i]) {
2224 tb_buffer_sanity_check(p_s_tb->tb_sb,
2225 p_s_tb->R[i],
2226 "R", i);
2227 if (!clear_all_dirty_bits
2228 (p_s_tb->tb_sb, p_s_tb->R[i]))
2229 locked = p_s_tb->R[i];
2230 }
2231
2232 if (!locked && p_s_tb->FR[i]) {
2233 tb_buffer_sanity_check(p_s_tb->tb_sb,
2234 p_s_tb->FR[i],
2235 "FR", i);
2236 if (!clear_all_dirty_bits
2237 (p_s_tb->tb_sb, p_s_tb->FR[i]))
2238 locked = p_s_tb->FR[i];
2239 }
2240
2241 if (!locked && p_s_tb->CFR[i]) {
2242 tb_buffer_sanity_check(p_s_tb->tb_sb,
2243 p_s_tb->CFR[i],
2244 "CFR", i);
2245 if (!clear_all_dirty_bits
2246 (p_s_tb->tb_sb, p_s_tb->CFR[i]))
2247 locked = p_s_tb->CFR[i];
2248 }
2249 }
2250 }
2251 /* as far as I can tell, this is not required. The FEB list seems
2252 ** to be full of newly allocated nodes, which will never be locked,
2253 ** dirty, or anything else.
2254 ** To be safe, I'm putting in the checks and waits in. For the moment,
2255 ** they are needed to keep the code in journal.c from complaining
2256 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2257 ** --clm
2258 */
2259 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2260 if (p_s_tb->FEB[i]) {
2261 if (!clear_all_dirty_bits
2262 (p_s_tb->tb_sb, p_s_tb->FEB[i]))
2263 locked = p_s_tb->FEB[i];
2264 }
2265 }
2266
2267 if (locked) {
2268#ifdef CONFIG_REISERFS_CHECK
2269 repeat_counter++;
2270 if ((repeat_counter % 10000) == 0) {
2271 reiserfs_warning(p_s_tb->tb_sb,
2272 "wait_tb_buffers_until_released(): too many "
2273 "iterations waiting for buffer to unlock "
2274 "(%b)", locked);
2275
2276 /* Don't loop forever. Try to recover from possible error. */
2277
2278 return (FILESYSTEM_CHANGED_TB(p_s_tb)) ?
2279 REPEAT_SEARCH : CARRY_ON;
2280 }
2281#endif
2282 __wait_on_buffer(locked);
2283 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2284 return REPEAT_SEARCH;
2285 }
2286 }
2287
2288 } while (locked);
2289
2290 return CARRY_ON;
2291}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002292
2293/* Prepare for balancing, that is
2294 * get all necessary parents, and neighbors;
2295 * analyze what and where should be moved;
2296 * get sufficient number of new nodes;
2297 * Balancing will start only after all resources will be collected at a time.
2298 *
2299 * When ported to SMP kernels, only at the last moment after all needed nodes
2300 * are collected in cache, will the resources be locked using the usual
2301 * textbook ordered lock acquisition algorithms. Note that ensuring that
2302 * this code neither write locks what it does not need to write lock nor locks out of order
2303 * will be a pain in the butt that could have been avoided. Grumble grumble. -Hans
2304 *
2305 * fix is meant in the sense of render unchanging
2306 *
2307 * Latency might be improved by first gathering a list of what buffers are needed
2308 * and then getting as many of them in parallel as possible? -Hans
2309 *
2310 * Parameters:
2311 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2312 * tb tree_balance structure;
2313 * inum item number in S[h];
2314 * pos_in_item - comment this if you can
2315 * ins_ih & ins_sd are used when inserting
2316 * Returns: 1 - schedule occurred while the function worked;
2317 * 0 - schedule didn't occur while the function worked;
2318 * -1 - if no_disk_space
2319 */
2320
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002321int fix_nodes(int n_op_mode, struct tree_balance *p_s_tb, struct item_head *p_s_ins_ih, // item head of item being inserted
2322 const void *data // inserted item or data to be pasted
2323 )
2324{
2325 int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
2326 int n_pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002327
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002328 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2329 ** during wait_tb_buffers_run
2330 */
2331 int wait_tb_buffers_run = 0;
2332 struct buffer_head *p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002333
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002334 ++REISERFS_SB(p_s_tb->tb_sb)->s_fix_nodes;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002335
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002336 n_pos_in_item = p_s_tb->tb_path->pos_in_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002337
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002338 p_s_tb->fs_gen = get_generation(p_s_tb->tb_sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002339
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002340 /* we prepare and log the super here so it will already be in the
2341 ** transaction when do_balance needs to change it.
2342 ** This way do_balance won't have to schedule when trying to prepare
2343 ** the super for logging
2344 */
2345 reiserfs_prepare_for_journal(p_s_tb->tb_sb,
2346 SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1);
2347 journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb,
2348 SB_BUFFER_WITH_SB(p_s_tb->tb_sb));
2349 if (FILESYSTEM_CHANGED_TB(p_s_tb))
2350 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002351
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002352 /* if it possible in indirect_to_direct conversion */
2353 if (buffer_locked(p_s_tbS0)) {
2354 __wait_on_buffer(p_s_tbS0);
2355 if (FILESYSTEM_CHANGED_TB(p_s_tb))
2356 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002357 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002358#ifdef CONFIG_REISERFS_CHECK
2359 if (cur_tb) {
2360 print_cur_tb("fix_nodes");
2361 reiserfs_panic(p_s_tb->tb_sb,
2362 "PAP-8305: fix_nodes: there is pending do_balance");
2363 }
2364
2365 if (!buffer_uptodate(p_s_tbS0) || !B_IS_IN_TREE(p_s_tbS0)) {
2366 reiserfs_panic(p_s_tb->tb_sb,
2367 "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate "
2368 "at the beginning of fix_nodes or not in tree (mode %c)",
2369 p_s_tbS0, p_s_tbS0, n_op_mode);
2370 }
2371
2372 /* Check parameters. */
2373 switch (n_op_mode) {
2374 case M_INSERT:
2375 if (n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0))
2376 reiserfs_panic(p_s_tb->tb_sb,
2377 "PAP-8330: fix_nodes: Incorrect item number %d (in S0 - %d) in case of insert",
2378 n_item_num, B_NR_ITEMS(p_s_tbS0));
2379 break;
2380 case M_PASTE:
2381 case M_DELETE:
2382 case M_CUT:
2383 if (n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0)) {
2384 print_block(p_s_tbS0, 0, -1, -1);
2385 reiserfs_panic(p_s_tb->tb_sb,
2386 "PAP-8335: fix_nodes: Incorrect item number(%d); mode = %c insert_size = %d\n",
2387 n_item_num, n_op_mode,
2388 p_s_tb->insert_size[0]);
2389 }
2390 break;
2391 default:
2392 reiserfs_panic(p_s_tb->tb_sb,
2393 "PAP-8340: fix_nodes: Incorrect mode of operation");
2394 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002395#endif
2396
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002397 if (get_mem_for_virtual_node(p_s_tb) == REPEAT_SEARCH)
2398 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2399 return REPEAT_SEARCH;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002400
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002401 /* Starting from the leaf level; for all levels n_h of the tree. */
2402 for (n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++) {
2403 if ((n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON) {
2404 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002405 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002406
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002407 if ((n_ret_value =
2408 check_balance(n_op_mode, p_s_tb, n_h, n_item_num,
2409 n_pos_in_item, p_s_ins_ih,
2410 data)) != CARRY_ON) {
2411 if (n_ret_value == NO_BALANCING_NEEDED) {
2412 /* No balancing for higher levels needed. */
2413 if ((n_ret_value =
2414 get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2415 goto repeat;
2416 }
2417 if (n_h != MAX_HEIGHT - 1)
2418 p_s_tb->insert_size[n_h + 1] = 0;
2419 /* ok, analysis and resource gathering are complete */
2420 break;
2421 }
2422 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002423 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002424
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002425 if ((n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2426 goto repeat;
2427 }
2428
2429 if ((n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON) {
2430 goto repeat; /* No disk space, or schedule occurred and
2431 analysis may be invalid and needs to be redone. */
2432 }
2433
2434 if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h)) {
2435 /* We have a positive insert size but no nodes exist on this
2436 level, this means that we are creating a new root. */
2437
2438 RFALSE(p_s_tb->blknum[n_h] != 1,
2439 "PAP-8350: creating new empty root");
2440
2441 if (n_h < MAX_HEIGHT - 1)
2442 p_s_tb->insert_size[n_h + 1] = 0;
2443 } else if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1)) {
2444 if (p_s_tb->blknum[n_h] > 1) {
2445 /* The tree needs to be grown, so this node S[n_h]
2446 which is the root node is split into two nodes,
2447 and a new node (S[n_h+1]) will be created to
2448 become the root node. */
2449
2450 RFALSE(n_h == MAX_HEIGHT - 1,
2451 "PAP-8355: attempt to create too high of a tree");
2452
2453 p_s_tb->insert_size[n_h + 1] =
2454 (DC_SIZE +
2455 KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) +
2456 DC_SIZE;
2457 } else if (n_h < MAX_HEIGHT - 1)
2458 p_s_tb->insert_size[n_h + 1] = 0;
2459 } else
2460 p_s_tb->insert_size[n_h + 1] =
2461 (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1);
2462 }
2463
2464 if ((n_ret_value = wait_tb_buffers_until_unlocked(p_s_tb)) == CARRY_ON) {
2465 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2466 wait_tb_buffers_run = 1;
2467 n_ret_value = REPEAT_SEARCH;
2468 goto repeat;
2469 } else {
2470 return CARRY_ON;
2471 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002472 } else {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002473 wait_tb_buffers_run = 1;
2474 goto repeat;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002475 }
2476
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002477 repeat:
2478 // fix_nodes was unable to perform its calculation due to
2479 // filesystem got changed under us, lack of free disk space or i/o
2480 // failure. If the first is the case - the search will be
2481 // repeated. For now - free all resources acquired so far except
2482 // for the new allocated nodes
2483 {
2484 int i;
2485
2486 /* Release path buffers. */
2487 if (wait_tb_buffers_run) {
2488 pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path);
2489 } else {
2490 pathrelse(p_s_tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002491 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002492 /* brelse all resources collected for balancing */
2493 for (i = 0; i < MAX_HEIGHT; i++) {
2494 if (wait_tb_buffers_run) {
2495 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2496 p_s_tb->L[i]);
2497 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2498 p_s_tb->R[i]);
2499 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2500 p_s_tb->FL[i]);
2501 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2502 p_s_tb->FR[i]);
2503 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2504 p_s_tb->
2505 CFL[i]);
2506 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2507 p_s_tb->
2508 CFR[i]);
2509 }
2510
2511 brelse(p_s_tb->L[i]);
2512 p_s_tb->L[i] = NULL;
2513 brelse(p_s_tb->R[i]);
2514 p_s_tb->R[i] = NULL;
2515 brelse(p_s_tb->FL[i]);
2516 p_s_tb->FL[i] = NULL;
2517 brelse(p_s_tb->FR[i]);
2518 p_s_tb->FR[i] = NULL;
2519 brelse(p_s_tb->CFL[i]);
2520 p_s_tb->CFL[i] = NULL;
2521 brelse(p_s_tb->CFR[i]);
2522 p_s_tb->CFR[i] = NULL;
2523 }
2524
2525 if (wait_tb_buffers_run) {
2526 for (i = 0; i < MAX_FEB_SIZE; i++) {
2527 if (p_s_tb->FEB[i]) {
2528 reiserfs_restore_prepared_buffer
2529 (p_s_tb->tb_sb, p_s_tb->FEB[i]);
2530 }
2531 }
2532 }
2533 return n_ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002534 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002535
2536}
2537
Linus Torvalds1da177e2005-04-16 15:20:36 -07002538/* Anatoly will probably forgive me renaming p_s_tb to tb. I just
2539 wanted to make lines shorter */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002540void unfix_nodes(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002541{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002542 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002543
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002544 /* Release path buffers. */
2545 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002546
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002547 /* brelse all resources collected for balancing */
2548 for (i = 0; i < MAX_HEIGHT; i++) {
2549 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2550 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2551 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2552 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2553 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2554 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002555
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002556 brelse(tb->L[i]);
2557 brelse(tb->R[i]);
2558 brelse(tb->FL[i]);
2559 brelse(tb->FR[i]);
2560 brelse(tb->CFL[i]);
2561 brelse(tb->CFR[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002562 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002563
2564 /* deal with list of allocated (used and unused) nodes */
2565 for (i = 0; i < MAX_FEB_SIZE; i++) {
2566 if (tb->FEB[i]) {
2567 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2568 /* de-allocated block which was not used by balancing and
2569 bforget about buffer for it */
2570 brelse(tb->FEB[i]);
2571 reiserfs_free_block(tb->transaction_handle, NULL,
2572 blocknr, 0);
2573 }
2574 if (tb->used[i]) {
2575 /* release used as new nodes including a new root */
2576 brelse(tb->used[i]);
2577 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002578 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002579
Pekka Enbergd739b422006-02-01 03:06:43 -08002580 kfree(tb->vn_buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002581
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07002582}