]> bbs.cooldavid.org Git - net-next-2.6.git/blame - fs/reiserfs/do_balan.c
git://bbs.cooldavid.org / net-next-2.6.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
ufs: sector_t cannot be negative
[net-next-2.6.git] / fs / reiserfs / do_balan.c
CommitLineData
1da177e4
LT		 1/*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5/* Now we have all buffers that must be used in balancing of the tree */
6/* Further calculations can not cause schedule(), and thus the buffer */
7/* tree will be stable until the balancing will be finished */
8/* balance the tree according to the analysis made before, */
9/* and using buffers obtained after all above. */
10
1da177e4
LT		 11/**
12 ** balance_leaf_when_delete
13 ** balance_leaf
14 ** do_balance
15 **
16 **/
17
1da177e4
LT		 18#include <asm/uaccess.h>
19#include <linux/time.h>
20#include <linux/reiserfs_fs.h>
21#include <linux/buffer_head.h>
79a81aef 22#include <linux/kernel.h>
1da177e4
LT		 23
24#ifdef CONFIG_REISERFS_CHECK
25
bd4c625c
LT		 26struct tree_balance *cur_tb = NULL; /* detects whether more than one
27 copy of tb exists as a means
28 of checking whether schedule
29 is interrupting do_balance */
1da177e4
LT		 30#endif
31
fba4ebb5
JM		 32static inline void buffer_info_init_left(struct tree_balance *tb,
33 struct buffer_info *bi)
34{
35 bi->tb = tb;
36 bi->bi_bh = tb->L[0];
37 bi->bi_parent = tb->FL[0];
38 bi->bi_position = get_left_neighbor_position(tb, 0);
39}
40
41static inline void buffer_info_init_right(struct tree_balance *tb,
42 struct buffer_info *bi)
43{
44 bi->tb = tb;
45 bi->bi_bh = tb->R[0];
46 bi->bi_parent = tb->FR[0];
47 bi->bi_position = get_right_neighbor_position(tb, 0);
48}
49
50static inline void buffer_info_init_tbS0(struct tree_balance *tb,
51 struct buffer_info *bi)
52{
53 bi->tb = tb;
54 bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
55 bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
56 bi->bi_position = PATH_H_POSITION(tb->tb_path, 1);
57}
58
59static inline void buffer_info_init_bh(struct tree_balance *tb,
60 struct buffer_info *bi,
61 struct buffer_head *bh)
62{
63 bi->tb = tb;
64 bi->bi_bh = bh;
65 bi->bi_parent = NULL;
66 bi->bi_position = 0;
67}
68
bd4c625c
LT		 69inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
70 struct buffer_head *bh, int flag)
1da177e4 71{
bd4c625c
LT		 72 journal_mark_dirty(tb->transaction_handle,
73 tb->transaction_handle->t_super, bh);
1da177e4
LT		 74}
75
76#define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
77#define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
78
0222e657 79/* summary:
1da177e4
LT		 80 if deleting something ( tb->insert_size[0] < 0 )
81 return(balance_leaf_when_delete()); (flag d handled here)
82 else
83 if lnum is larger than 0 we put items into the left node
84 if rnum is larger than 0 we put items into the right node
85 if snum1 is larger than 0 we put items into the new node s1
0222e657 86 if snum2 is larger than 0 we put items into the new node s2
1da177e4
LT		 87Note that all *num* count new items being created.
88
89It would be easier to read balance_leaf() if each of these summary
90lines was a separate procedure rather than being inlined. I think
91that there are many passages here and in balance_leaf_when_delete() in
92which two calls to one procedure can replace two passages, and it
0222e657 93might save cache space and improve software maintenance costs to do so.
1da177e4
LT		 94
95Vladimir made the perceptive comment that we should offload most of
96the decision making in this function into fix_nodes/check_balance, and
97then create some sort of structure in tb that says what actions should
98be performed by do_balance.
99
100-Hans */
101
1da177e4
LT		 102/* Balance leaf node in case of delete or cut: insert_size[0] < 0
103 *
104 * lnum, rnum can have values >= -1
105 * -1 means that the neighbor must be joined with S
106 * 0 means that nothing should be done with the neighbor
107 * >0 means to shift entirely or partly the specified number of items to the neighbor
108 */
bd4c625c 109static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
1da177e4 110{
bd4c625c
LT		 111 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
112 int item_pos = PATH_LAST_POSITION(tb->tb_path);
113 int pos_in_item = tb->tb_path->pos_in_item;
114 struct buffer_info bi;
115 int n;
116 struct item_head *ih;
1da177e4 117
bd4c625c
LT		 118 RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1,
119 "vs- 12000: level: wrong FR %z", tb->FR[0]);
120 RFALSE(tb->blknum[0] > 1,
121 "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]);
122 RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0),
123 "PAP-12010: tree can not be empty");
1da177e4 124
bd4c625c 125 ih = B_N_PITEM_HEAD(tbS0, item_pos);
fba4ebb5 126 buffer_info_init_tbS0(tb, &bi);
1da177e4 127
bd4c625c 128 /* Delete or truncate the item */
1da177e4 129
bd4c625c
LT		 130 switch (flag) {
131 case M_DELETE: /* delete item in S[0] */
132
133 RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0],
134 "vs-12013: mode Delete, insert size %d, ih to be deleted %h",
135 -tb->insert_size[0], ih);
136
bd4c625c
LT		 137 leaf_delete_items(&bi, 0, item_pos, 1, -1);
138
139 if (!item_pos && tb->CFL[0]) {
140 if (B_NR_ITEMS(tbS0)) {
141 replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0,
142 0);
143 } else {
144 if (!PATH_H_POSITION(tb->tb_path, 1))
145 replace_key(tb, tb->CFL[0], tb->lkey[0],
146 PATH_H_PPARENT(tb->tb_path,
147 0), 0);
148 }
149 }
1da177e4 150
bd4c625c
LT		 151 RFALSE(!item_pos && !tb->CFL[0],
152 "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0],
153 tb->L[0]);
1da177e4 154
bd4c625c
LT		 155 break;
156
157 case M_CUT:{ /* cut item in S[0] */
bd4c625c
LT		 158 if (is_direntry_le_ih(ih)) {
159
160 /* UFS unlink semantics are such that you can only delete one directory entry at a time. */
161 /* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */
162 tb->insert_size[0] = -1;
163 leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
164 -tb->insert_size[0]);
165
166 RFALSE(!item_pos && !pos_in_item && !tb->CFL[0],
167 "PAP-12030: can not change delimiting key. CFL[0]=%p",
168 tb->CFL[0]);
169
170 if (!item_pos && !pos_in_item && tb->CFL[0]) {
171 replace_key(tb, tb->CFL[0], tb->lkey[0],
172 tbS0, 0);
173 }
174 } else {
175 leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
176 -tb->insert_size[0]);
177
178 RFALSE(!ih_item_len(ih),
179 "PAP-12035: cut must leave non-zero dynamic length of item");
180 }
181 break;
1da177e4 182 }
1da177e4 183
bd4c625c
LT		 184 default:
185 print_cur_tb("12040");
c3a9c210
JM		 186 reiserfs_panic(tb->tb_sb, "PAP-12040",
187 "unexpected mode: %s(%d)",
bd4c625c
LT		 188 (flag ==
189 M_PASTE) ? "PASTE" : ((flag ==
190 M_INSERT) ? "INSERT" :
191 "UNKNOWN"), flag);
192 }
1da177e4 193
bd4c625c
LT		 194 /* the rule is that no shifting occurs unless by shifting a node can be freed */
195 n = B_NR_ITEMS(tbS0);
196 if (tb->lnum[0]) { /* L[0] takes part in balancing */
197 if (tb->lnum[0] == -1) { /* L[0] must be joined with S[0] */
198 if (tb->rnum[0] == -1) { /* R[0] must be also joined with S[0] */
199 if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) {
200 /* all contents of all the 3 buffers will be in L[0] */
201 if (PATH_H_POSITION(tb->tb_path, 1) == 0
202 && 1 < B_NR_ITEMS(tb->FR[0]))
203 replace_key(tb, tb->CFL[0],
204 tb->lkey[0],
205 tb->FR[0], 1);
206
207 leaf_move_items(LEAF_FROM_S_TO_L, tb, n,
208 -1, NULL);
209 leaf_move_items(LEAF_FROM_R_TO_L, tb,
210 B_NR_ITEMS(tb->R[0]),
211 -1, NULL);
212
213 reiserfs_invalidate_buffer(tb, tbS0);
214 reiserfs_invalidate_buffer(tb,
215 tb->R[0]);
216
217 return 0;
218 }
219 /* all contents of all the 3 buffers will be in R[0] */
220 leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1,
221 NULL);
222 leaf_move_items(LEAF_FROM_L_TO_R, tb,
223 B_NR_ITEMS(tb->L[0]), -1, NULL);
224
225 /* right_delimiting_key is correct in R[0] */
226 replace_key(tb, tb->CFR[0], tb->rkey[0],
227 tb->R[0], 0);
1da177e4 228
bd4c625c
LT		 229 reiserfs_invalidate_buffer(tb, tbS0);
230 reiserfs_invalidate_buffer(tb, tb->L[0]);
1da177e4 231
bd4c625c
LT		 232 return -1;
233 }
1da177e4 234
bd4c625c
LT		 235 RFALSE(tb->rnum[0] != 0,
236 "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]);
237 /* all contents of L[0] and S[0] will be in L[0] */
238 leaf_shift_left(tb, n, -1);
1da177e4 239
bd4c625c
LT		 240 reiserfs_invalidate_buffer(tb, tbS0);
241
242 return 0;
243 }
244 /* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */
245
246 RFALSE((tb->lnum[0] + tb->rnum[0] < n) ||
247 (tb->lnum[0] + tb->rnum[0] > n + 1),
248 "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent",
249 tb->rnum[0], tb->lnum[0], n);
250 RFALSE((tb->lnum[0] + tb->rnum[0] == n) &&
251 (tb->lbytes != -1 || tb->rbytes != -1),
252 "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split",
253 tb->rbytes, tb->lbytes);
254 RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) &&
255 (tb->lbytes < 1 || tb->rbytes != -1),
256 "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split",
257 tb->rbytes, tb->lbytes);
258
259 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
260 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
261
262 reiserfs_invalidate_buffer(tb, tbS0);
263
264 return 0;
1da177e4 265 }
1da177e4 266
bd4c625c
LT		 267 if (tb->rnum[0] == -1) {
268 /* all contents of R[0] and S[0] will be in R[0] */
269 leaf_shift_right(tb, n, -1);
270 reiserfs_invalidate_buffer(tb, tbS0);
271 return 0;
272 }
1da177e4 273
bd4c625c
LT		 274 RFALSE(tb->rnum[0],
275 "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]);
1da177e4 276 return 0;
1da177e4
LT		 277}
278
bd4c625c
LT		 279static int balance_leaf(struct tree_balance *tb, struct item_head *ih, /* item header of inserted item (this is on little endian) */
280 const char *body, /* body of inserted item or bytes to paste */
281 int flag, /* i - insert, d - delete, c - cut, p - paste
282 (see comment to do_balance) */
283 struct item_head *insert_key, /* in our processing of one level we sometimes determine what
284 must be inserted into the next higher level. This insertion
285 consists of a key or two keys and their corresponding
286 pointers */
287 struct buffer_head **insert_ptr /* inserted node-ptrs for the next level */
1da177e4
LT		 288 )
289{
bd4c625c 290 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
0222e657 291 int item_pos = PATH_LAST_POSITION(tb->tb_path); /* index into the array of item headers in S[0]
bd4c625c
LT		 292 of the affected item */
293 struct buffer_info bi;
294 struct buffer_head *S_new[2]; /* new nodes allocated to hold what could not fit into S */
295 int snum[2]; /* number of items that will be placed
296 into S_new (includes partially shifted
297 items) */
0222e657
JM		 298 int sbytes[2]; /* if an item is partially shifted into S_new then
299 if it is a directory item
bd4c625c
LT		 300 it is the number of entries from the item that are shifted into S_new
301 else
302 it is the number of bytes from the item that are shifted into S_new
303 */
304 int n, i;
305 int ret_val;
306 int pos_in_item;
307 int zeros_num;
308
309 PROC_INFO_INC(tb->tb_sb, balance_at[0]);
310
311 /* Make balance in case insert_size[0] < 0 */
312 if (tb->insert_size[0] < 0)
313 return balance_leaf_when_delete(tb, flag);
314
315 zeros_num = 0;
9dce07f1 316 if (flag == M_INSERT && !body)
bd4c625c
LT		 317 zeros_num = ih_item_len(ih);
318
319 pos_in_item = tb->tb_path->pos_in_item;
320 /* for indirect item pos_in_item is measured in unformatted node
321 pointers. Recalculate to bytes */
322 if (flag != M_INSERT
323 && is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
324 pos_in_item *= UNFM_P_SIZE;
325
326 if (tb->lnum[0] > 0) {
327 /* Shift lnum[0] items from S[0] to the left neighbor L[0] */
328 if (item_pos < tb->lnum[0]) {
329 /* new item or it part falls to L[0], shift it too */
330 n = B_NR_ITEMS(tb->L[0]);
331
332 switch (flag) {
333 case M_INSERT: /* insert item into L[0] */
334
335 if (item_pos == tb->lnum[0] - 1
336 && tb->lbytes != -1) {
337 /* part of new item falls into L[0] */
338 int new_item_len;
339 int version;
340
341 ret_val =
342 leaf_shift_left(tb, tb->lnum[0] - 1,
343 -1);
344
345 /* Calculate item length to insert to S[0] */
346 new_item_len =
347 ih_item_len(ih) - tb->lbytes;
348 /* Calculate and check item length to insert to L[0] */
349 put_ih_item_len(ih,
350 ih_item_len(ih) -
351 new_item_len);
352
353 RFALSE(ih_item_len(ih) <= 0,
354 "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d",
355 ih_item_len(ih));
356
357 /* Insert new item into L[0] */
fba4ebb5 358 buffer_info_init_left(tb, &bi);
bd4c625c
LT		 359 leaf_insert_into_buf(&bi,
360 n + item_pos -
361 ret_val, ih, body,
362 zeros_num >
363 ih_item_len(ih) ?
364 ih_item_len(ih) :
365 zeros_num);
366
367 version = ih_version(ih);
368
369 /* Calculate key component, item length and body to insert into S[0] */
370 set_le_ih_k_offset(ih,
371 le_ih_k_offset(ih) +
372 (tb->
373 lbytes <<
374 (is_indirect_le_ih
375 (ih) ? tb->tb_sb->
376 s_blocksize_bits -
377 UNFM_P_SHIFT :
378 0)));
379
380 put_ih_item_len(ih, new_item_len);
381 if (tb->lbytes > zeros_num) {
382 body +=
383 (tb->lbytes - zeros_num);
384 zeros_num = 0;
385 } else
386 zeros_num -= tb->lbytes;
387
388 RFALSE(ih_item_len(ih) <= 0,
389 "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d",
390 ih_item_len(ih));
391 } else {
392 /* new item in whole falls into L[0] */
393 /* Shift lnum[0]-1 items to L[0] */
394 ret_val =
395 leaf_shift_left(tb, tb->lnum[0] - 1,
396 tb->lbytes);
397 /* Insert new item into L[0] */
fba4ebb5 398 buffer_info_init_left(tb, &bi);
bd4c625c
LT		 399 leaf_insert_into_buf(&bi,
400 n + item_pos -
401 ret_val, ih, body,
402 zeros_num);
403 tb->insert_size[0] = 0;
404 zeros_num = 0;
1da177e4 405 }
bd4c625c
LT		 406 break;
407
408 case M_PASTE: /* append item in L[0] */
409
410 if (item_pos == tb->lnum[0] - 1
411 && tb->lbytes != -1) {
412 /* we must shift the part of the appended item */
413 if (is_direntry_le_ih
414 (B_N_PITEM_HEAD(tbS0, item_pos))) {
415
416 RFALSE(zeros_num,
417 "PAP-12090: invalid parameter in case of a directory");
418 /* directory item */
419 if (tb->lbytes > pos_in_item) {
420 /* new directory entry falls into L[0] */
421 struct item_head
422 *pasted;
423 int l_pos_in_item =
424 pos_in_item;
425
426 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
427 ret_val =
428 leaf_shift_left(tb,
429 tb->
430 lnum
431 [0],
432 tb->
433 lbytes
434 -
435 1);
436 if (ret_val
437 && !item_pos) {
438 pasted =
439 B_N_PITEM_HEAD
440 (tb->L[0],
441 B_NR_ITEMS
442 (tb->
443 L[0]) -
444 1);
445 l_pos_in_item +=
446 I_ENTRY_COUNT
447 (pasted) -
448 (tb->
449 lbytes -
450 1);
451 }
452
453 /* Append given directory entry to directory item */
fba4ebb5 454 buffer_info_init_left(tb, &bi);
bd4c625c
LT		 455 leaf_paste_in_buffer
456 (&bi,
457 n + item_pos -
458 ret_val,
459 l_pos_in_item,
460 tb->insert_size[0],
461 body, zeros_num);
462
463 /* previous string prepared space for pasting new entry, following string pastes this entry */
464
465 /* when we have merge directory item, pos_in_item has been changed too */
466
467 /* paste new directory entry. 1 is entry number */
eba00305 468 leaf_paste_entries(&bi,
bd4c625c
LT		 469 n +
470 item_pos
471 -
472 ret_val,
473 l_pos_in_item,
474 1,
475 (struct
476 reiserfs_de_head
477 *)
478 body,
479 body
480 +
481 DEH_SIZE,
482 tb->
483 insert_size
484 [0]
485 );
486 tb->insert_size[0] = 0;
487 } else {
488 /* new directory item doesn't fall into L[0] */
489 /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
490 leaf_shift_left(tb,
491 tb->
492 lnum[0],
493 tb->
494 lbytes);
495 }
496 /* Calculate new position to append in item body */
497 pos_in_item -= tb->lbytes;
498 } else {
499 /* regular object */
500 RFALSE(tb->lbytes <= 0,
501 "PAP-12095: there is nothing to shift to L[0]. lbytes=%d",
502 tb->lbytes);
503 RFALSE(pos_in_item !=
504 ih_item_len
505 (B_N_PITEM_HEAD
506 (tbS0, item_pos)),
507 "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
508 ih_item_len
509 (B_N_PITEM_HEAD
510 (tbS0, item_pos)),
511 pos_in_item);
512
513 if (tb->lbytes >= pos_in_item) {
514 /* appended item will be in L[0] in whole */
515 int l_n;
516
517 /* this bytes number must be appended to the last item of L[h] */
518 l_n =
519 tb->lbytes -
520 pos_in_item;
521
522 /* Calculate new insert_size[0] */
523 tb->insert_size[0] -=
524 l_n;
525
526 RFALSE(tb->
527 insert_size[0] <=
528 0,
529 "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
530 tb->
531 insert_size[0]);
532 ret_val =
533 leaf_shift_left(tb,
534 tb->
535 lnum
536 [0],
537 ih_item_len
538 (B_N_PITEM_HEAD
539 (tbS0,
540 item_pos)));
541 /* Append to body of item in L[0] */
fba4ebb5 542 buffer_info_init_left(tb, &bi);
bd4c625c
LT		 543 leaf_paste_in_buffer
544 (&bi,
545 n + item_pos -
546 ret_val,
547 ih_item_len
548 (B_N_PITEM_HEAD
549 (tb->L[0],
550 n + item_pos -
551 ret_val)), l_n,
552 body,
553 zeros_num >
554 l_n ? l_n :
555 zeros_num);
556 /* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
557 {
558 int version;
559 int temp_l =
560 l_n;
561
562 RFALSE
563 (ih_item_len
564 (B_N_PITEM_HEAD
565 (tbS0,
566 0)),
567 "PAP-12106: item length must be 0");
568 RFALSE
569 (comp_short_le_keys
570 (B_N_PKEY
571 (tbS0, 0),
572 B_N_PKEY
573 (tb->L[0],
574 n +
575 item_pos
576 -
577 ret_val)),
578 "PAP-12107: items must be of the same file");
579 if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val))) {
580 temp_l =
581 l_n
582 <<
583 (tb->
584 tb_sb->
585 s_blocksize_bits
586 -
587 UNFM_P_SHIFT);
588 }
589 /* update key of first item in S0 */
590 version =
591 ih_version
592 (B_N_PITEM_HEAD
593 (tbS0, 0));
594 set_le_key_k_offset
595 (version,
596 B_N_PKEY
597 (tbS0, 0),
598 le_key_k_offset
599 (version,
600 B_N_PKEY
601 (tbS0,
602 0)) +
603 temp_l);
604 /* update left delimiting key */
605 set_le_key_k_offset
606 (version,
607 B_N_PDELIM_KEY
608 (tb->
609 CFL[0],
610 tb->
611 lkey[0]),
612 le_key_k_offset
613 (version,
614 B_N_PDELIM_KEY
615 (tb->
616 CFL[0],
617 tb->
618 lkey[0]))
619 + temp_l);
620 }
621
622 /* Calculate new body, position in item and insert_size[0] */
623 if (l_n > zeros_num) {
624 body +=
625 (l_n -
626 zeros_num);
627 zeros_num = 0;
628 } else
629 zeros_num -=
630 l_n;
631 pos_in_item = 0;
632
633 RFALSE
634 (comp_short_le_keys
635 (B_N_PKEY(tbS0, 0),
636 B_N_PKEY(tb->L[0],
637 B_NR_ITEMS
638 (tb->
639 L[0]) -
640 1))
641 ||
642 !op_is_left_mergeable
643 (B_N_PKEY(tbS0, 0),
644 tbS0->b_size)
645 ||
646 !op_is_left_mergeable
647 (B_N_PDELIM_KEY
648 (tb->CFL[0],
649 tb->lkey[0]),
650 tbS0->b_size),
651 "PAP-12120: item must be merge-able with left neighboring item");
652 } else { /* only part of the appended item will be in L[0] */
653
654 /* Calculate position in item for append in S[0] */
655 pos_in_item -=
656 tb->lbytes;
657
658 RFALSE(pos_in_item <= 0,
659 "PAP-12125: no place for paste. pos_in_item=%d",
660 pos_in_item);
661
662 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
663 leaf_shift_left(tb,
664 tb->
665 lnum[0],
666 tb->
667 lbytes);
668 }
669 }
670 } else { /* appended item will be in L[0] in whole */
671
672 struct item_head *pasted;
673
674 if (!item_pos && op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)) { /* if we paste into first item of S[0] and it is left mergable */
675 /* then increment pos_in_item by the size of the last item in L[0] */
676 pasted =
677 B_N_PITEM_HEAD(tb->L[0],
678 n - 1);
679 if (is_direntry_le_ih(pasted))
680 pos_in_item +=
681 ih_entry_count
682 (pasted);
683 else
684 pos_in_item +=
685 ih_item_len(pasted);
686 }
687
688 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
689 ret_val =
690 leaf_shift_left(tb, tb->lnum[0],
691 tb->lbytes);
692 /* Append to body of item in L[0] */
fba4ebb5 693 buffer_info_init_left(tb, &bi);
bd4c625c
LT		 694 leaf_paste_in_buffer(&bi,
695 n + item_pos -
696 ret_val,
697 pos_in_item,
698 tb->insert_size[0],
699 body, zeros_num);
700
701 /* if appended item is directory, paste entry */
702 pasted =
703 B_N_PITEM_HEAD(tb->L[0],
704 n + item_pos -
705 ret_val);
706 if (is_direntry_le_ih(pasted))
eba00305 707 leaf_paste_entries(&bi,
bd4c625c
LT		 708 n +
709 item_pos -
710 ret_val,
711 pos_in_item,
712 1,
713 (struct
714 reiserfs_de_head
715 *)body,
716 body +
717 DEH_SIZE,
718 tb->
719 insert_size
720 [0]
721 );
722 /* if appended item is indirect item, put unformatted node into un list */
723 if (is_indirect_le_ih(pasted))
724 set_ih_free_space(pasted, 0);
725 tb->insert_size[0] = 0;
726 zeros_num = 0;
727 }
728 break;
729 default: /* cases d and t */
c3a9c210
JM		 730 reiserfs_panic(tb->tb_sb, "PAP-12130",
731 "lnum > 0: unexpected mode: "
732 " %s(%d)",
bd4c625c
LT		 733 (flag ==
734 M_DELETE) ? "DELETE" : ((flag ==
735 M_CUT)
736 ? "CUT"
737 :
738 "UNKNOWN"),
739 flag);
1da177e4 740 }
bd4c625c
LT		 741 } else {
742 /* new item doesn't fall into L[0] */
743 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
1da177e4 744 }
1da177e4 745 }
1da177e4 746
bd4c625c
LT		 747 /* tb->lnum[0] > 0 */
748 /* Calculate new item position */
749 item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
750
751 if (tb->rnum[0] > 0) {
752 /* shift rnum[0] items from S[0] to the right neighbor R[0] */
753 n = B_NR_ITEMS(tbS0);
754 switch (flag) {
755
756 case M_INSERT: /* insert item */
757 if (n - tb->rnum[0] < item_pos) { /* new item or its part falls to R[0] */
758 if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) { /* part of new item falls into R[0] */
759 loff_t old_key_comp, old_len,
760 r_zeros_number;
761 const char *r_body;
762 int version;
763 loff_t offset;
764
765 leaf_shift_right(tb, tb->rnum[0] - 1,
766 -1);
767
768 version = ih_version(ih);
769 /* Remember key component and item length */
770 old_key_comp = le_ih_k_offset(ih);
771 old_len = ih_item_len(ih);
772
773 /* Calculate key component and item length to insert into R[0] */
774 offset =
775 le_ih_k_offset(ih) +
776 ((old_len -
777 tb->
778 rbytes) << (is_indirect_le_ih(ih)
779 ? tb->tb_sb->
780 s_blocksize_bits -
781 UNFM_P_SHIFT : 0));
782 set_le_ih_k_offset(ih, offset);
783 put_ih_item_len(ih, tb->rbytes);
784 /* Insert part of the item into R[0] */
fba4ebb5 785 buffer_info_init_right(tb, &bi);
bd4c625c
LT		 786 if ((old_len - tb->rbytes) > zeros_num) {
787 r_zeros_number = 0;
788 r_body =
789 body + (old_len -
790 tb->rbytes) -
791 zeros_num;
792 } else {
793 r_body = body;
794 r_zeros_number =
795 zeros_num - (old_len -
796 tb->rbytes);
797 zeros_num -= r_zeros_number;
798 }
799
800 leaf_insert_into_buf(&bi, 0, ih, r_body,
801 r_zeros_number);
802
803 /* Replace right delimiting key by first key in R[0] */
804 replace_key(tb, tb->CFR[0], tb->rkey[0],
805 tb->R[0], 0);
806
807 /* Calculate key component and item length to insert into S[0] */
808 set_le_ih_k_offset(ih, old_key_comp);
809 put_ih_item_len(ih,
810 old_len - tb->rbytes);
811
812 tb->insert_size[0] -= tb->rbytes;
813
814 } else { /* whole new item falls into R[0] */
815
816 /* Shift rnum[0]-1 items to R[0] */
817 ret_val =
818 leaf_shift_right(tb,
819 tb->rnum[0] - 1,
820 tb->rbytes);
821 /* Insert new item into R[0] */
fba4ebb5 822 buffer_info_init_right(tb, &bi);
bd4c625c
LT		 823 leaf_insert_into_buf(&bi,
824 item_pos - n +
825 tb->rnum[0] - 1,
826 ih, body,
827 zeros_num);
828
829 if (item_pos - n + tb->rnum[0] - 1 == 0) {
830 replace_key(tb, tb->CFR[0],
831 tb->rkey[0],
832 tb->R[0], 0);
833
834 }
835 zeros_num = tb->insert_size[0] = 0;
836 }
837 } else { /* new item or part of it doesn't fall into R[0] */
1da177e4 838
bd4c625c 839 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
1da177e4 840 }
bd4c625c
LT		 841 break;
842
843 case M_PASTE: /* append item */
844
845 if (n - tb->rnum[0] <= item_pos) { /* pasted item or part of it falls to R[0] */
846 if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) { /* we must shift the part of the appended item */
847 if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) { /* we append to directory item */
848 int entry_count;
849
850 RFALSE(zeros_num,
851 "PAP-12145: invalid parameter in case of a directory");
852 entry_count =
853 I_ENTRY_COUNT(B_N_PITEM_HEAD
854 (tbS0,
855 item_pos));
856 if (entry_count - tb->rbytes <
857 pos_in_item)
858 /* new directory entry falls into R[0] */
859 {
860 int paste_entry_position;
861
862 RFALSE(tb->rbytes - 1 >=
863 entry_count
864 || !tb->
865 insert_size[0],
866 "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
867 tb->rbytes,
868 entry_count);
869 /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
870 leaf_shift_right(tb,
871 tb->
872 rnum
873 [0],
874 tb->
875 rbytes
876 - 1);
877 /* Paste given directory entry to directory item */
878 paste_entry_position =
879 pos_in_item -
880 entry_count +
881 tb->rbytes - 1;
fba4ebb5 882 buffer_info_init_right(tb, &bi);
bd4c625c
LT		 883 leaf_paste_in_buffer
884 (&bi, 0,
885 paste_entry_position,
886 tb->insert_size[0],
887 body, zeros_num);
888 /* paste entry */
eba00305 889 leaf_paste_entries(&bi,
bd4c625c
LT		 890 0,
891 paste_entry_position,
892 1,
893 (struct
894 reiserfs_de_head
895 *)
896 body,
897 body
898 +
899 DEH_SIZE,
900 tb->
901 insert_size
902 [0]
903 );
904
905 if (paste_entry_position
906 == 0) {
907 /* change delimiting keys */
908 replace_key(tb,
909 tb->
910 CFR
911 [0],
912 tb->
913 rkey
914 [0],
915 tb->
916 R
917 [0],
918 0);
919 }
920
921 tb->insert_size[0] = 0;
922 pos_in_item++;
923 } else { /* new directory entry doesn't fall into R[0] */
924
925 leaf_shift_right(tb,
926 tb->
927 rnum
928 [0],
929 tb->
930 rbytes);
931 }
932 } else { /* regular object */
933
934 int n_shift, n_rem,
935 r_zeros_number;
936 const char *r_body;
937
938 /* Calculate number of bytes which must be shifted from appended item */
939 if ((n_shift =
940 tb->rbytes -
941 tb->insert_size[0]) < 0)
942 n_shift = 0;
943
944 RFALSE(pos_in_item !=
945 ih_item_len
946 (B_N_PITEM_HEAD
947 (tbS0, item_pos)),
948 "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
949 pos_in_item,
950 ih_item_len
951 (B_N_PITEM_HEAD
952 (tbS0, item_pos)));
953
954 leaf_shift_right(tb,
955 tb->rnum[0],
956 n_shift);
957 /* Calculate number of bytes which must remain in body after appending to R[0] */
958 if ((n_rem =
959 tb->insert_size[0] -
960 tb->rbytes) < 0)
961 n_rem = 0;
962
963 {
964 int version;
965 unsigned long temp_rem =
966 n_rem;
967
968 version =
969 ih_version
970 (B_N_PITEM_HEAD
971 (tb->R[0], 0));
972 if (is_indirect_le_key
973 (version,
974 B_N_PKEY(tb->R[0],
975 0))) {
976 temp_rem =
977 n_rem <<
978 (tb->tb_sb->
979 s_blocksize_bits
980 -
981 UNFM_P_SHIFT);
982 }
983 set_le_key_k_offset
984 (version,
985 B_N_PKEY(tb->R[0],
986 0),
987 le_key_k_offset
988 (version,
989 B_N_PKEY(tb->R[0],
990 0)) +
991 temp_rem);
992 set_le_key_k_offset
993 (version,
994 B_N_PDELIM_KEY(tb->
995 CFR
996 [0],
997 tb->
998 rkey
999 [0]),
1000 le_key_k_offset
1001 (version,
1002 B_N_PDELIM_KEY
1003 (tb->CFR[0],
1004 tb->rkey[0])) +
1005 temp_rem);
1006 }
1da177e4
LT		 1007/* k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
1008 k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
bd4c625c
LT		 1009 do_balance_mark_internal_dirty
1010 (tb, tb->CFR[0], 0);
1011
1012 /* Append part of body into R[0] */
fba4ebb5 1013 buffer_info_init_right(tb, &bi);
bd4c625c
LT		 1014 if (n_rem > zeros_num) {
1015 r_zeros_number = 0;
1016 r_body =
1017 body + n_rem -
1018 zeros_num;
1019 } else {
1020 r_body = body;
1021 r_zeros_number =
1022 zeros_num - n_rem;
1023 zeros_num -=
1024 r_zeros_number;
1025 }
1026
1027 leaf_paste_in_buffer(&bi, 0,
1028 n_shift,
1029 tb->
1030 insert_size
1031 [0] -
1032 n_rem,
1033 r_body,
1034 r_zeros_number);
1035
1036 if (is_indirect_le_ih
1037 (B_N_PITEM_HEAD
1038 (tb->R[0], 0))) {
1da177e4 1039#if 0
bd4c625c
LT		 1040 RFALSE(n_rem,
1041 "PAP-12160: paste more than one unformatted node pointer");
1da177e4 1042#endif
bd4c625c
LT		 1043 set_ih_free_space
1044 (B_N_PITEM_HEAD
1045 (tb->R[0], 0), 0);
1046 }
1047 tb->insert_size[0] = n_rem;
1048 if (!n_rem)
1049 pos_in_item++;
1050 }
1051 } else { /* pasted item in whole falls into R[0] */
1052
1053 struct item_head *pasted;
1054
1055 ret_val =
1056 leaf_shift_right(tb, tb->rnum[0],
1057 tb->rbytes);
1058 /* append item in R[0] */
1059 if (pos_in_item >= 0) {
fba4ebb5 1060 buffer_info_init_right(tb, &bi);
bd4c625c
LT		 1061 leaf_paste_in_buffer(&bi,
1062 item_pos -
1063 n +
1064 tb->
1065 rnum[0],
1066 pos_in_item,
1067 tb->
1068 insert_size
1069 [0], body,
1070 zeros_num);
1071 }
1072
1073 /* paste new entry, if item is directory item */
1074 pasted =
1075 B_N_PITEM_HEAD(tb->R[0],
1076 item_pos - n +
1077 tb->rnum[0]);
1078 if (is_direntry_le_ih(pasted)
1079 && pos_in_item >= 0) {
eba00305 1080 leaf_paste_entries(&bi,
bd4c625c
LT		 1081 item_pos -
1082 n +
1083 tb->rnum[0],
1084 pos_in_item,
1085 1,
1086 (struct
1087 reiserfs_de_head
1088 *)body,
1089 body +
1090 DEH_SIZE,
1091 tb->
1092 insert_size
1093 [0]
1094 );
1095 if (!pos_in_item) {
1096
1097 RFALSE(item_pos - n +
1098 tb->rnum[0],
1099 "PAP-12165: directory item must be first item of node when pasting is in 0th position");
1100
1101 /* update delimiting keys */
1102 replace_key(tb,
1103 tb->CFR[0],
1104 tb->rkey[0],
1105 tb->R[0],
1106 0);
1107 }
1108 }
1109
1110 if (is_indirect_le_ih(pasted))
1111 set_ih_free_space(pasted, 0);
1112 zeros_num = tb->insert_size[0] = 0;
1113 }
1114 } else { /* new item doesn't fall into R[0] */
1da177e4 1115
bd4c625c 1116 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
1da177e4 1117 }
bd4c625c
LT		 1118 break;
1119 default: /* cases d and t */
c3a9c210
JM		 1120 reiserfs_panic(tb->tb_sb, "PAP-12175",
1121 "rnum > 0: unexpected mode: %s(%d)",
bd4c625c
LT		 1122 (flag ==
1123 M_DELETE) ? "DELETE" : ((flag ==
1124 M_CUT) ? "CUT"
1125 : "UNKNOWN"),
1126 flag);
1da177e4 1127 }
1da177e4 1128
bd4c625c 1129 }
1da177e4 1130
bd4c625c
LT		 1131 /* tb->rnum[0] > 0 */
1132 RFALSE(tb->blknum[0] > 3,
1133 "PAP-12180: blknum can not be %d. It must be <= 3",
1134 tb->blknum[0]);
1135 RFALSE(tb->blknum[0] < 0,
1136 "PAP-12185: blknum can not be %d. It must be >= 0",
1137 tb->blknum[0]);
1138
1139 /* if while adding to a node we discover that it is possible to split
1140 it in two, and merge the left part into the left neighbor and the
1141 right part into the right neighbor, eliminating the node */
1142 if (tb->blknum[0] == 0) { /* node S[0] is empty now */
1143
1144 RFALSE(!tb->lnum[0] || !tb->rnum[0],
1145 "PAP-12190: lnum and rnum must not be zero");
1146 /* if insertion was done before 0-th position in R[0], right
1147 delimiting key of the tb->L[0]'s and left delimiting key are
1148 not set correctly */
1149 if (tb->CFL[0]) {
1150 if (!tb->CFR[0])
c3a9c210
JM		 1151 reiserfs_panic(tb->tb_sb, "vs-12195",
1152 "CFR not initialized");
bd4c625c
LT		 1153 copy_key(B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]),
1154 B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]));
1155 do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
1156 }
1da177e4 1157
bd4c625c
LT		 1158 reiserfs_invalidate_buffer(tb, tbS0);
1159 return 0;
1160 }
1da177e4 1161
bd4c625c
LT		 1162 /* Fill new nodes that appear in place of S[0] */
1163
1164 /* I am told that this copying is because we need an array to enable
1165 the looping code. -Hans */
1166 snum[0] = tb->s1num, snum[1] = tb->s2num;
1167 sbytes[0] = tb->s1bytes;
1168 sbytes[1] = tb->s2bytes;
1169 for (i = tb->blknum[0] - 2; i >= 0; i--) {
1170
1171 RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i,
1172 snum[i]);
1173
1174 /* here we shift from S to S_new nodes */
1175
1176 S_new[i] = get_FEB(tb);
1177
1178 /* initialized block type and tree level */
1179 set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
1180
1181 n = B_NR_ITEMS(tbS0);
1182
1183 switch (flag) {
1184 case M_INSERT: /* insert item */
1185
1186 if (n - snum[i] < item_pos) { /* new item or it's part falls to first new node S_new[i] */
1187 if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) { /* part of new item falls into S_new[i] */
1188 int old_key_comp, old_len,
1189 r_zeros_number;
1190 const char *r_body;
1191 int version;
1192
1193 /* Move snum[i]-1 items from S[0] to S_new[i] */
1194 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1195 snum[i] - 1, -1,
1196 S_new[i]);
1197 /* Remember key component and item length */
1198 version = ih_version(ih);
1199 old_key_comp = le_ih_k_offset(ih);
1200 old_len = ih_item_len(ih);
1201
1202 /* Calculate key component and item length to insert into S_new[i] */
1203 set_le_ih_k_offset(ih,
1204 le_ih_k_offset(ih) +
1205 ((old_len -
1206 sbytes[i]) <<
1207 (is_indirect_le_ih
1208 (ih) ? tb->tb_sb->
1209 s_blocksize_bits -
1210 UNFM_P_SHIFT :
1211 0)));
1212
1213 put_ih_item_len(ih, sbytes[i]);
1214
1215 /* Insert part of the item into S_new[i] before 0-th item */
fba4ebb5 1216 buffer_info_init_bh(tb, &bi, S_new[i]);
bd4c625c
LT		 1217
1218 if ((old_len - sbytes[i]) > zeros_num) {
1219 r_zeros_number = 0;
1220 r_body =
1221 body + (old_len -
1222 sbytes[i]) -
1223 zeros_num;
1224 } else {
1225 r_body = body;
1226 r_zeros_number =
1227 zeros_num - (old_len -
1228 sbytes[i]);
1229 zeros_num -= r_zeros_number;
1230 }
1231
1232 leaf_insert_into_buf(&bi, 0, ih, r_body,
1233 r_zeros_number);
1234
1235 /* Calculate key component and item length to insert into S[i] */
1236 set_le_ih_k_offset(ih, old_key_comp);
1237 put_ih_item_len(ih,
1238 old_len - sbytes[i]);
1239 tb->insert_size[0] -= sbytes[i];
1240 } else { /* whole new item falls into S_new[i] */
1241
1242 /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
1243 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1244 snum[i] - 1, sbytes[i],
1245 S_new[i]);
1246
1247 /* Insert new item into S_new[i] */
fba4ebb5 1248 buffer_info_init_bh(tb, &bi, S_new[i]);
bd4c625c
LT		 1249 leaf_insert_into_buf(&bi,
1250 item_pos - n +
1251 snum[i] - 1, ih,
1252 body, zeros_num);
1253
1254 zeros_num = tb->insert_size[0] = 0;
1255 }
1256 }
1da177e4 1257
bd4c625c 1258 else { /* new item or it part don't falls into S_new[i] */
1da177e4 1259
bd4c625c
LT		 1260 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1261 snum[i], sbytes[i], S_new[i]);
1da177e4 1262 }
bd4c625c
LT		 1263 break;
1264
1265 case M_PASTE: /* append item */
1266
1267 if (n - snum[i] <= item_pos) { /* pasted item or part if it falls to S_new[i] */
1268 if (item_pos == n - snum[i] && sbytes[i] != -1) { /* we must shift part of the appended item */
1269 struct item_head *aux_ih;
1270
1271 RFALSE(ih, "PAP-12210: ih must be 0");
1272
1273 if (is_direntry_le_ih
1274 (aux_ih =
1275 B_N_PITEM_HEAD(tbS0, item_pos))) {
1276 /* we append to directory item */
1277
1278 int entry_count;
1279
1280 entry_count =
1281 ih_entry_count(aux_ih);
1282
1283 if (entry_count - sbytes[i] <
1284 pos_in_item
1285 && pos_in_item <=
1286 entry_count) {
1287 /* new directory entry falls into S_new[i] */
1288
1289 RFALSE(!tb->
1290 insert_size[0],
1291 "PAP-12215: insert_size is already 0");
1292 RFALSE(sbytes[i] - 1 >=
1293 entry_count,
1294 "PAP-12220: there are no so much entries (%d), only %d",
1295 sbytes[i] - 1,
1296 entry_count);
1297
1298 /* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
1299 leaf_move_items
1300 (LEAF_FROM_S_TO_SNEW,
1301 tb, snum[i],
1302 sbytes[i] - 1,
1303 S_new[i]);
1304 /* Paste given directory entry to directory item */
fba4ebb5 1305 buffer_info_init_bh(tb, &bi, S_new[i]);
bd4c625c
LT		 1306 leaf_paste_in_buffer
1307 (&bi, 0,
1308 pos_in_item -
1309 entry_count +
1310 sbytes[i] - 1,
1311 tb->insert_size[0],
1312 body, zeros_num);
1313 /* paste new directory entry */
eba00305 1314 leaf_paste_entries(&bi,
bd4c625c
LT		 1315 0,
1316 pos_in_item
1317 -
1318 entry_count
1319 +
1320 sbytes
1321 [i] -
1322 1, 1,
1323 (struct
1324 reiserfs_de_head
1325 *)
1326 body,
1327 body
1328 +
1329 DEH_SIZE,
1330 tb->
1331 insert_size
1332 [0]
1333 );
1334 tb->insert_size[0] = 0;
1335 pos_in_item++;
1336 } else { /* new directory entry doesn't fall into S_new[i] */
1337 leaf_move_items
1338 (LEAF_FROM_S_TO_SNEW,
1339 tb, snum[i],
1340 sbytes[i],
1341 S_new[i]);
1342 }
1343 } else { /* regular object */
1344
1345 int n_shift, n_rem,
1346 r_zeros_number;
1347 const char *r_body;
1348
1349 RFALSE(pos_in_item !=
1350 ih_item_len
1351 (B_N_PITEM_HEAD
1352 (tbS0, item_pos))
1353 || tb->insert_size[0] <=
1354 0,
1355 "PAP-12225: item too short or insert_size <= 0");
1356
1357 /* Calculate number of bytes which must be shifted from appended item */
1358 n_shift =
1359 sbytes[i] -
1360 tb->insert_size[0];
1361 if (n_shift < 0)
1362 n_shift = 0;
1363 leaf_move_items
1364 (LEAF_FROM_S_TO_SNEW, tb,
1365 snum[i], n_shift,
1366 S_new[i]);
1367
1368 /* Calculate number of bytes which must remain in body after append to S_new[i] */
1369 n_rem =
1370 tb->insert_size[0] -
1371 sbytes[i];
1372 if (n_rem < 0)
1373 n_rem = 0;
1374 /* Append part of body into S_new[0] */
fba4ebb5 1375 buffer_info_init_bh(tb, &bi, S_new[i]);
bd4c625c
LT		 1376 if (n_rem > zeros_num) {
1377 r_zeros_number = 0;
1378 r_body =
1379 body + n_rem -
1380 zeros_num;
1381 } else {
1382 r_body = body;
1383 r_zeros_number =
1384 zeros_num - n_rem;
1385 zeros_num -=
1386 r_zeros_number;
1387 }
1388
1389 leaf_paste_in_buffer(&bi, 0,
1390 n_shift,
1391 tb->
1392 insert_size
1393 [0] -
1394 n_rem,
1395 r_body,
1396 r_zeros_number);
1397 {
1398 struct item_head *tmp;
1399
1400 tmp =
1401 B_N_PITEM_HEAD(S_new
1402 [i],
1403 0);
1404 if (is_indirect_le_ih
1405 (tmp)) {
1406 set_ih_free_space
1407 (tmp, 0);
1408 set_le_ih_k_offset
1409 (tmp,
1410 le_ih_k_offset
1411 (tmp) +
1412 (n_rem <<
1413 (tb->
1414 tb_sb->
1415 s_blocksize_bits
1416 -
1417 UNFM_P_SHIFT)));
1418 } else {
1419 set_le_ih_k_offset
1420 (tmp,
1421 le_ih_k_offset
1422 (tmp) +
1423 n_rem);
1424 }
1425 }
1426
1427 tb->insert_size[0] = n_rem;
1428 if (!n_rem)
1429 pos_in_item++;
1430 }
1431 } else
1432 /* item falls wholly into S_new[i] */
1433 {
8acc570f 1434 int leaf_mi;
bd4c625c 1435 struct item_head *pasted;
1da177e4 1436
bd4c625c 1437#ifdef CONFIG_REISERFS_CHECK
8acc570f 1438 struct item_head *ih_check =
bd4c625c
LT		 1439 B_N_PITEM_HEAD(tbS0, item_pos);
1440
8acc570f
HH		 1441 if (!is_direntry_le_ih(ih_check)
1442 && (pos_in_item != ih_item_len(ih_check)
bd4c625c
LT		 1443 || tb->insert_size[0] <= 0))
1444 reiserfs_panic(tb->tb_sb,
c3a9c210
JM		 1445 "PAP-12235",
1446 "pos_in_item "
1447 "must be equal "
1448 "to ih_item_len");
bd4c625c
LT		 1449#endif /* CONFIG_REISERFS_CHECK */
1450
8acc570f 1451 leaf_mi =
bd4c625c
LT		 1452 leaf_move_items(LEAF_FROM_S_TO_SNEW,
1453 tb, snum[i],
1454 sbytes[i],
1455 S_new[i]);
1456
8acc570f 1457 RFALSE(leaf_mi,
bd4c625c 1458 "PAP-12240: unexpected value returned by leaf_move_items (%d)",
8acc570f 1459 leaf_mi);
bd4c625c
LT		 1460
1461 /* paste into item */
fba4ebb5 1462 buffer_info_init_bh(tb, &bi, S_new[i]);
bd4c625c
LT		 1463 leaf_paste_in_buffer(&bi,
1464 item_pos - n +
1465 snum[i],
1466 pos_in_item,
1467 tb->insert_size[0],
1468 body, zeros_num);
1469
1470 pasted =
1471 B_N_PITEM_HEAD(S_new[i],
1472 item_pos - n +
1473 snum[i]);
1474 if (is_direntry_le_ih(pasted)) {
eba00305 1475 leaf_paste_entries(&bi,
bd4c625c
LT		 1476 item_pos -
1477 n + snum[i],
1478 pos_in_item,
1479 1,
1480 (struct
1481 reiserfs_de_head
1482 *)body,
1483 body +
1484 DEH_SIZE,
1485 tb->
1486 insert_size
1487 [0]
1488 );
1489 }
1490
1491 /* if we paste to indirect item update ih_free_space */
1492 if (is_indirect_le_ih(pasted))
1493 set_ih_free_space(pasted, 0);
1494 zeros_num = tb->insert_size[0] = 0;
1495 }
1da177e4
LT		 1496 }
1497
bd4c625c 1498 else { /* pasted item doesn't fall into S_new[i] */
1da177e4 1499
bd4c625c
LT		 1500 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1501 snum[i], sbytes[i], S_new[i]);
1502 }
1503 break;
1504 default: /* cases d and t */
c3a9c210
JM		 1505 reiserfs_panic(tb->tb_sb, "PAP-12245",
1506 "blknum > 2: unexpected mode: %s(%d)",
bd4c625c
LT		 1507 (flag ==
1508 M_DELETE) ? "DELETE" : ((flag ==
1509 M_CUT) ? "CUT"
1510 : "UNKNOWN"),
1511 flag);
1da177e4 1512 }
1da177e4 1513
bd4c625c
LT		 1514 memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
1515 insert_ptr[i] = S_new[i];
1516
1517 RFALSE(!buffer_journaled(S_new[i])
1518 || buffer_journal_dirty(S_new[i])
1519 || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)",
1520 i, S_new[i]);
1da177e4
LT		 1521 }
1522
bd4c625c
LT		 1523 /* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
1524 affected item which remains in S */
1525 if (0 <= item_pos && item_pos < tb->s0num) { /* if we must insert or append into buffer S[0] */
1526
1527 switch (flag) {
1528 case M_INSERT: /* insert item into S[0] */
fba4ebb5 1529 buffer_info_init_tbS0(tb, &bi);
bd4c625c
LT		 1530 leaf_insert_into_buf(&bi, item_pos, ih, body,
1531 zeros_num);
1532
1533 /* If we insert the first key change the delimiting key */
1534 if (item_pos == 0) {
1535 if (tb->CFL[0]) /* can be 0 in reiserfsck */
1536 replace_key(tb, tb->CFL[0], tb->lkey[0],
1537 tbS0, 0);
1da177e4
LT		 1538
1539 }
bd4c625c
LT		 1540 break;
1541
1542 case M_PASTE:{ /* append item in S[0] */
1543 struct item_head *pasted;
1544
1545 pasted = B_N_PITEM_HEAD(tbS0, item_pos);
1546 /* when directory, may be new entry already pasted */
1547 if (is_direntry_le_ih(pasted)) {
1548 if (pos_in_item >= 0 &&
1549 pos_in_item <=
1550 ih_entry_count(pasted)) {
1551
1552 RFALSE(!tb->insert_size[0],
1553 "PAP-12260: insert_size is 0 already");
1554
1555 /* prepare space */
fba4ebb5 1556 buffer_info_init_tbS0(tb, &bi);
bd4c625c
LT		 1557 leaf_paste_in_buffer(&bi,
1558 item_pos,
1559 pos_in_item,
1560 tb->
1561 insert_size
1562 [0], body,
1563 zeros_num);
1564
1565 /* paste entry */
eba00305 1566 leaf_paste_entries(&bi,
bd4c625c
LT		 1567 item_pos,
1568 pos_in_item,
1569 1,
1570 (struct
1571 reiserfs_de_head
1572 *)body,
1573 body +
1574 DEH_SIZE,
1575 tb->
1576 insert_size
1577 [0]
1578 );
1579 if (!item_pos && !pos_in_item) {
1580 RFALSE(!tb->CFL[0]
1581 || !tb->L[0],
1582 "PAP-12270: CFL[0]/L[0] must be specified");
1583 if (tb->CFL[0]) {
1584 replace_key(tb,
1585 tb->
1586 CFL
1587 [0],
1588 tb->
1589 lkey
1590 [0],
1591 tbS0,
1592 0);
1593
1594 }
1595 }
1596 tb->insert_size[0] = 0;
1597 }
1598 } else { /* regular object */
1599 if (pos_in_item == ih_item_len(pasted)) {
1600
1601 RFALSE(tb->insert_size[0] <= 0,
1602 "PAP-12275: insert size must not be %d",
1603 tb->insert_size[0]);
fba4ebb5 1604 buffer_info_init_tbS0(tb, &bi);
bd4c625c
LT		 1605 leaf_paste_in_buffer(&bi,
1606 item_pos,
1607 pos_in_item,
1608 tb->
1609 insert_size
1610 [0], body,
1611 zeros_num);
1612
1613 if (is_indirect_le_ih(pasted)) {
1da177e4 1614#if 0
bd4c625c
LT		 1615 RFALSE(tb->
1616 insert_size[0] !=
1617 UNFM_P_SIZE,
1618 "PAP-12280: insert_size for indirect item must be %d, not %d",
1619 UNFM_P_SIZE,
1620 tb->
1621 insert_size[0]);
1da177e4 1622#endif
bd4c625c
LT		 1623 set_ih_free_space
1624 (pasted, 0);
1625 }
1626 tb->insert_size[0] = 0;
1627 }
1da177e4 1628#ifdef CONFIG_REISERFS_CHECK
bd4c625c
LT		 1629 else {
1630 if (tb->insert_size[0]) {
1631 print_cur_tb("12285");
1632 reiserfs_panic(tb->
1633 tb_sb,
c3a9c210
JM		 1634 "PAP-12285",
1635 "insert_size "
1636 "must be 0 "
1637 "(%d)",
1638 tb->insert_size[0]);
bd4c625c
LT		 1639 }
1640 }
1641#endif /* CONFIG_REISERFS_CHECK */
1642
1643 }
1644 } /* case M_PASTE: */
1da177e4 1645 }
1da177e4 1646 }
1da177e4 1647#ifdef CONFIG_REISERFS_CHECK
bd4c625c
LT		 1648 if (flag == M_PASTE && tb->insert_size[0]) {
1649 print_cur_tb("12290");
1650 reiserfs_panic(tb->tb_sb,
c3a9c210 1651 "PAP-12290", "insert_size is still not 0 (%d)",
bd4c625c
LT		 1652 tb->insert_size[0]);
1653 }
1654#endif /* CONFIG_REISERFS_CHECK */
bd4c625c
LT		 1655 return 0;
1656} /* Leaf level of the tree is balanced (end of balance_leaf) */
1da177e4
LT		 1657
1658/* Make empty node */
bd4c625c 1659void make_empty_node(struct buffer_info *bi)
1da177e4 1660{
bd4c625c 1661 struct block_head *blkh;
1da177e4 1662
bd4c625c 1663 RFALSE(bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");
1da177e4 1664
bd4c625c
LT		 1665 blkh = B_BLK_HEAD(bi->bi_bh);
1666 set_blkh_nr_item(blkh, 0);
1667 set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
1da177e4 1668
bd4c625c
LT		 1669 if (bi->bi_parent)
1670 B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0; /* Endian safe if 0 */
1da177e4
LT		 1671}
1672
1da177e4 1673/* Get first empty buffer */
bd4c625c 1674struct buffer_head *get_FEB(struct tree_balance *tb)
1da177e4 1675{
bd4c625c 1676 int i;
bd4c625c 1677 struct buffer_info bi;
1da177e4 1678
bd4c625c 1679 for (i = 0; i < MAX_FEB_SIZE; i++)
9dce07f1 1680 if (tb->FEB[i] != NULL)
bd4c625c
LT		 1681 break;
1682
1683 if (i == MAX_FEB_SIZE)
c3a9c210 1684 reiserfs_panic(tb->tb_sb, "vs-12300", "FEB list is empty");
bd4c625c 1685
fba4ebb5 1686 buffer_info_init_bh(tb, &bi, tb->FEB[i]);
bd4c625c 1687 make_empty_node(&bi);
fba4ebb5
JM		 1688 set_buffer_uptodate(tb->FEB[i]);
1689 tb->used[i] = tb->FEB[i];
bd4c625c 1690 tb->FEB[i] = NULL;
bd4c625c 1691
fba4ebb5 1692 return tb->used[i];
bd4c625c 1693}
1da177e4
LT		 1694
1695/* This is now used because reiserfs_free_block has to be able to
1696** schedule.
1697*/
bd4c625c 1698static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
1da177e4 1699{
bd4c625c
LT		 1700 int i;
1701
1702 if (buffer_dirty(bh))
45b03d5e
JM		 1703 reiserfs_warning(tb->tb_sb, "reiserfs-12320",
1704 "called with dirty buffer");
79a81aef 1705 for (i = 0; i < ARRAY_SIZE(tb->thrown); i++)
bd4c625c
LT		 1706 if (!tb->thrown[i]) {
1707 tb->thrown[i] = bh;
1708 get_bh(bh); /* free_thrown puts this */
1709 return;
1710 }
45b03d5e
JM		 1711 reiserfs_warning(tb->tb_sb, "reiserfs-12321",
1712 "too many thrown buffers");
1da177e4
LT		 1713}
1714
bd4c625c
LT		 1715static void free_thrown(struct tree_balance *tb)
1716{
1717 int i;
1718 b_blocknr_t blocknr;
79a81aef 1719 for (i = 0; i < ARRAY_SIZE(tb->thrown); i++) {
bd4c625c
LT		 1720 if (tb->thrown[i]) {
1721 blocknr = tb->thrown[i]->b_blocknr;
1722 if (buffer_dirty(tb->thrown[i]))
45b03d5e
JM		 1723 reiserfs_warning(tb->tb_sb, "reiserfs-12322",
1724 "called with dirty buffer %d",
bd4c625c
LT		 1725 blocknr);
1726 brelse(tb->thrown[i]); /* incremented in store_thrown */
1727 reiserfs_free_block(tb->transaction_handle, NULL,
1728 blocknr, 0);
1729 }
1da177e4 1730 }
1da177e4
LT		 1731}
1732
bd4c625c 1733void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
1da177e4 1734{
bd4c625c
LT		 1735 struct block_head *blkh;
1736 blkh = B_BLK_HEAD(bh);
1737 set_blkh_level(blkh, FREE_LEVEL);
1738 set_blkh_nr_item(blkh, 0);
1739
1740 clear_buffer_dirty(bh);
1741 store_thrown(tb, bh);
1da177e4
LT		 1742}
1743
1744/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
bd4c625c
LT		 1745void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
1746 struct buffer_head *src, int n_src)
1da177e4
LT		 1747{
1748
bd4c625c
LT		 1749 RFALSE(dest == NULL || src == NULL,
1750 "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
1751 src, dest);
1752 RFALSE(!B_IS_KEYS_LEVEL(dest),
1753 "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
1754 dest);
1755 RFALSE(n_dest < 0 || n_src < 0,
1756 "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
1757 RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
1758 "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
1759 n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
1760
1761 if (B_IS_ITEMS_LEVEL(src))
1762 /* source buffer contains leaf node */
1763 memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PITEM_HEAD(src, n_src),
1764 KEY_SIZE);
1765 else
1766 memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PDELIM_KEY(src, n_src),
1767 KEY_SIZE);
1768
1769 do_balance_mark_internal_dirty(tb, dest, 0);
1da177e4
LT		 1770}
1771
bd4c625c 1772int get_left_neighbor_position(struct tree_balance *tb, int h)
1da177e4 1773{
bd4c625c 1774 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1da177e4 1775
9dce07f1 1776 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FL[h] == NULL,
bd4c625c
LT		 1777 "vs-12325: FL[%d](%p) or F[%d](%p) does not exist",
1778 h, tb->FL[h], h, PATH_H_PPARENT(tb->tb_path, h));
1da177e4 1779
bd4c625c
LT		 1780 if (Sh_position == 0)
1781 return B_NR_ITEMS(tb->FL[h]);
1782 else
1783 return Sh_position - 1;
1da177e4
LT		 1784}
1785
bd4c625c 1786int get_right_neighbor_position(struct tree_balance *tb, int h)
1da177e4 1787{
bd4c625c 1788 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1da177e4 1789
9dce07f1 1790 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FR[h] == NULL,
bd4c625c
LT		 1791 "vs-12330: F[%d](%p) or FR[%d](%p) does not exist",
1792 h, PATH_H_PPARENT(tb->tb_path, h), h, tb->FR[h]);
1da177e4 1793
bd4c625c
LT		 1794 if (Sh_position == B_NR_ITEMS(PATH_H_PPARENT(tb->tb_path, h)))
1795 return 0;
1796 else
1797 return Sh_position + 1;
1da177e4
LT		 1798}
1799
1da177e4
LT		 1800#ifdef CONFIG_REISERFS_CHECK
1801
bd4c625c
LT		 1802int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
1803static void check_internal_node(struct super_block *s, struct buffer_head *bh,
1804 char *mes)
1da177e4 1805{
bd4c625c
LT		 1806 struct disk_child *dc;
1807 int i;
1da177e4 1808
bd4c625c 1809 RFALSE(!bh, "PAP-12336: bh == 0");
1da177e4 1810
bd4c625c
LT		 1811 if (!bh || !B_IS_IN_TREE(bh))
1812 return;
1da177e4 1813
bd4c625c
LT		 1814 RFALSE(!buffer_dirty(bh) &&
1815 !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
1816 "PAP-12337: buffer (%b) must be dirty", bh);
1817 dc = B_N_CHILD(bh, 0);
1da177e4 1818
bd4c625c
LT		 1819 for (i = 0; i <= B_NR_ITEMS(bh); i++, dc++) {
1820 if (!is_reusable(s, dc_block_number(dc), 1)) {
1821 print_cur_tb(mes);
c3a9c210
JM		 1822 reiserfs_panic(s, "PAP-12338",
1823 "invalid child pointer %y in %b",
bd4c625c
LT		 1824 dc, bh);
1825 }
1826 }
1da177e4
LT		 1827}
1828
45b03d5e
JM		 1829static int locked_or_not_in_tree(struct tree_balance *tb,
1830 struct buffer_head *bh, char *which)
bd4c625c
LT		 1831{
1832 if ((!buffer_journal_prepared(bh) && buffer_locked(bh)) ||
1833 !B_IS_IN_TREE(bh)) {
45b03d5e 1834 reiserfs_warning(tb->tb_sb, "vs-12339", "%s (%b)", which, bh);
bd4c625c
LT		 1835 return 1;
1836 }
1837 return 0;
1838}
1da177e4 1839
bd4c625c 1840static int check_before_balancing(struct tree_balance *tb)
1da177e4 1841{
bd4c625c
LT		 1842 int retval = 0;
1843
1844 if (cur_tb) {
c3a9c210
JM		 1845 reiserfs_panic(tb->tb_sb, "vs-12335", "suspect that schedule "
1846 "occurred based on cur_tb not being null at "
1847 "this point in code. do_balance cannot properly "
1848 "handle schedule occurring while it runs.");
1da177e4 1849 }
bd4c625c
LT		 1850
1851 /* double check that buffers that we will modify are unlocked. (fix_nodes should already have
1852 prepped all of these for us). */
1853 if (tb->lnum[0]) {
45b03d5e
JM		 1854 retval |= locked_or_not_in_tree(tb, tb->L[0], "L[0]");
1855 retval |= locked_or_not_in_tree(tb, tb->FL[0], "FL[0]");
1856 retval |= locked_or_not_in_tree(tb, tb->CFL[0], "CFL[0]");
bd4c625c 1857 check_leaf(tb->L[0]);
1da177e4 1858 }
bd4c625c 1859 if (tb->rnum[0]) {
45b03d5e
JM		 1860 retval |= locked_or_not_in_tree(tb, tb->R[0], "R[0]");
1861 retval |= locked_or_not_in_tree(tb, tb->FR[0], "FR[0]");
1862 retval |= locked_or_not_in_tree(tb, tb->CFR[0], "CFR[0]");
bd4c625c
LT		 1863 check_leaf(tb->R[0]);
1864 }
45b03d5e
JM		 1865 retval |= locked_or_not_in_tree(tb, PATH_PLAST_BUFFER(tb->tb_path),
1866 "S[0]");
bd4c625c 1867 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1da177e4 1868
bd4c625c
LT		 1869 return retval;
1870}
1da177e4 1871
bd4c625c 1872static void check_after_balance_leaf(struct tree_balance *tb)
1da177e4 1873{
bd4c625c
LT		 1874 if (tb->lnum[0]) {
1875 if (B_FREE_SPACE(tb->L[0]) !=
1876 MAX_CHILD_SIZE(tb->L[0]) -
1877 dc_size(B_N_CHILD
1878 (tb->FL[0], get_left_neighbor_position(tb, 0)))) {
1879 print_cur_tb("12221");
c3a9c210
JM		 1880 reiserfs_panic(tb->tb_sb, "PAP-12355",
1881 "shift to left was incorrect");
bd4c625c
LT		 1882 }
1883 }
1884 if (tb->rnum[0]) {
1885 if (B_FREE_SPACE(tb->R[0]) !=
1886 MAX_CHILD_SIZE(tb->R[0]) -
1887 dc_size(B_N_CHILD
1888 (tb->FR[0], get_right_neighbor_position(tb, 0)))) {
1889 print_cur_tb("12222");
c3a9c210
JM		 1890 reiserfs_panic(tb->tb_sb, "PAP-12360",
1891 "shift to right was incorrect");
bd4c625c
LT		 1892 }
1893 }
1894 if (PATH_H_PBUFFER(tb->tb_path, 1) &&
1895 (B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0)) !=
1896 (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1897 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1898 PATH_H_POSITION(tb->tb_path, 1)))))) {
1899 int left = B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0));
1900 int right = (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1901 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1902 PATH_H_POSITION(tb->tb_path,
1903 1))));
1904 print_cur_tb("12223");
45b03d5e 1905 reiserfs_warning(tb->tb_sb, "reiserfs-12363",
bd4c625c
LT		 1906 "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
1907 "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d",
1908 left,
1909 MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)),
1910 PATH_H_PBUFFER(tb->tb_path, 1),
1911 PATH_H_POSITION(tb->tb_path, 1),
1912 dc_size(B_N_CHILD
1913 (PATH_H_PBUFFER(tb->tb_path, 1),
1914 PATH_H_POSITION(tb->tb_path, 1))),
1915 right);
c3a9c210 1916 reiserfs_panic(tb->tb_sb, "PAP-12365", "S is incorrect");
bd4c625c 1917 }
1da177e4
LT		 1918}
1919
bd4c625c 1920static void check_leaf_level(struct tree_balance *tb)
1da177e4 1921{
bd4c625c
LT		 1922 check_leaf(tb->L[0]);
1923 check_leaf(tb->R[0]);
1924 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1925}
1da177e4 1926
bd4c625c
LT		 1927static void check_internal_levels(struct tree_balance *tb)
1928{
1929 int h;
1930
1931 /* check all internal nodes */
1932 for (h = 1; tb->insert_size[h]; h++) {
1933 check_internal_node(tb->tb_sb, PATH_H_PBUFFER(tb->tb_path, h),
1934 "BAD BUFFER ON PATH");
1935 if (tb->lnum[h])
1936 check_internal_node(tb->tb_sb, tb->L[h], "BAD L");
1937 if (tb->rnum[h])
1938 check_internal_node(tb->tb_sb, tb->R[h], "BAD R");
1939 }
1da177e4
LT		 1940
1941}
1942
1943#endif
1944
1da177e4
LT		 1945/* Now we have all of the buffers that must be used in balancing of
1946 the tree. We rely on the assumption that schedule() will not occur
1947 while do_balance works. ( Only interrupt handlers are acceptable.)
1948 We balance the tree according to the analysis made before this,
1949 using buffers already obtained. For SMP support it will someday be
1950 necessary to add ordered locking of tb. */
1951
1952/* Some interesting rules of balancing:
1953
1954 we delete a maximum of two nodes per level per balancing: we never
1955 delete R, when we delete two of three nodes L, S, R then we move
1956 them into R.
1957
1958 we only delete L if we are deleting two nodes, if we delete only
1959 one node we delete S
1960
1961 if we shift leaves then we shift as much as we can: this is a
1962 deliberate policy of extremism in node packing which results in
1963 higher average utilization after repeated random balance operations
1964 at the cost of more memory copies and more balancing as a result of
1965 small insertions to full nodes.
1966
1967 if we shift internal nodes we try to evenly balance the node
1968 utilization, with consequent less balancing at the cost of lower
1969 utilization.
1970
1971 one could argue that the policy for directories in leaves should be
1972 that of internal nodes, but we will wait until another day to
1973 evaluate this.... It would be nice to someday measure and prove
1974 these assumptions as to what is optimal....
1975
1976*/
1977
bd4c625c 1978static inline void do_balance_starts(struct tree_balance *tb)
1da177e4 1979{
bd4c625c
LT		 1980 /* use print_cur_tb() to see initial state of struct
1981 tree_balance */
1da177e4 1982
bd4c625c 1983 /* store_print_tb (tb); */
1da177e4 1984
bd4c625c 1985 /* do not delete, just comment it out */
0222e657 1986/* print_tb(flag, PATH_LAST_POSITION(tb->tb_path), tb->tb_path->pos_in_item, tb,
1da177e4 1987 "check");*/
bd4c625c 1988 RFALSE(check_before_balancing(tb), "PAP-12340: locked buffers in TB");
1da177e4 1989#ifdef CONFIG_REISERFS_CHECK
bd4c625c 1990 cur_tb = tb;
1da177e4
LT		 1991#endif
1992}
1993
bd4c625c 1994static inline void do_balance_completed(struct tree_balance *tb)
1da177e4 1995{
bd4c625c 1996
1da177e4 1997#ifdef CONFIG_REISERFS_CHECK
bd4c625c
LT		 1998 check_leaf_level(tb);
1999 check_internal_levels(tb);
2000 cur_tb = NULL;
1da177e4
LT		 2001#endif
2002
bd4c625c
LT		 2003 /* reiserfs_free_block is no longer schedule safe. So, we need to
2004 ** put the buffers we want freed on the thrown list during do_balance,
2005 ** and then free them now
2006 */
1da177e4 2007
bd4c625c 2008 REISERFS_SB(tb->tb_sb)->s_do_balance++;
1da177e4 2009
bd4c625c
LT		 2010 /* release all nodes hold to perform the balancing */
2011 unfix_nodes(tb);
1da177e4 2012
bd4c625c 2013 free_thrown(tb);
1da177e4
LT		 2014}
2015
bd4c625c
LT		 2016void do_balance(struct tree_balance *tb, /* tree_balance structure */
2017 struct item_head *ih, /* item header of inserted item */
2018 const char *body, /* body of inserted item or bytes to paste */
2019 int flag)
2020{ /* i - insert, d - delete
2021 c - cut, p - paste
2022
2023 Cut means delete part of an item
2024 (includes removing an entry from a
2025 directory).
2026
2027 Delete means delete whole item.
2028
2029 Insert means add a new item into the
2030 tree.
2031
2032 Paste means to append to the end of an
2033 existing file or to insert a directory
2034 entry. */
2035 int child_pos, /* position of a child node in its parent */
2036 h; /* level of the tree being processed */
2037 struct item_head insert_key[2]; /* in our processing of one level
2038 we sometimes determine what
2039 must be inserted into the next
2040 higher level. This insertion
2041 consists of a key or two keys
2042 and their corresponding
2043 pointers */
2044 struct buffer_head *insert_ptr[2]; /* inserted node-ptrs for the next
2045 level */
2046
2047 tb->tb_mode = flag;
2048 tb->need_balance_dirty = 0;
2049
2050 if (FILESYSTEM_CHANGED_TB(tb)) {
c3a9c210
JM		 2051 reiserfs_panic(tb->tb_sb, "clm-6000", "fs generation has "
2052 "changed");
bd4c625c
LT		 2053 }
2054 /* if we have no real work to do */
2055 if (!tb->insert_size[0]) {
45b03d5e
JM		 2056 reiserfs_warning(tb->tb_sb, "PAP-12350",
2057 "insert_size == 0, mode == %c", flag);
bd4c625c
LT		 2058 unfix_nodes(tb);
2059 return;
2060 }
1da177e4 2061
bd4c625c
LT		 2062 atomic_inc(&(fs_generation(tb->tb_sb)));
2063 do_balance_starts(tb);
1da177e4 2064
1da177e4
LT		 2065 /* balance leaf returns 0 except if combining L R and S into
2066 one node. see balance_internal() for explanation of this
bd4c625c
LT		 2067 line of code. */
2068 child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
2069 balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
1da177e4
LT		 2070
2071#ifdef CONFIG_REISERFS_CHECK
bd4c625c 2072 check_after_balance_leaf(tb);
1da177e4
LT		 2073#endif
2074
bd4c625c
LT		 2075 /* Balance internal level of the tree. */
2076 for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
2077 child_pos =
2078 balance_internal(tb, h, child_pos, insert_key, insert_ptr);
1da177e4 2079
bd4c625c 2080 do_balance_completed(tb);
1da177e4
LT		 2081
2082}
Clone of davem's net-next-2.6 tree