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