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