]> Git Repo - linux.git/blame - fs/reiserfs/do_balan.c
projects / linux.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
[PATCH] reiserfs: fix unaligned bitmap usage
[linux.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
18#include <linux/config.h>
19#include <asm/uaccess.h>
20#include <linux/time.h>
21#include <linux/reiserfs_fs.h>
22#include <linux/buffer_head.h>
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;
286 if (flag == M_INSERT && body == 0)
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 */
452 leaf_paste_entries(bi.
453 bi_bh,
454 n +
455 item_pos
456 -
457 ret_val,
458 l_pos_in_item,
459 1,
460 (struct
461 reiserfs_de_head
462 *)
463 body,
464 body
465 +
466 DEH_SIZE,
467 tb->
468 insert_size
469 [0]
470 );
471 tb->insert_size[0] = 0;
472 } else {
473 /* new directory item doesn't fall into L[0] */
474 /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
475 leaf_shift_left(tb,
476 tb->
477 lnum[0],
478 tb->
479 lbytes);
480 }
481 /* Calculate new position to append in item body */
482 pos_in_item -= tb->lbytes;
483 } else {
484 /* regular object */
485 RFALSE(tb->lbytes <= 0,
486 "PAP-12095: there is nothing to shift to L[0]. lbytes=%d",
487 tb->lbytes);
488 RFALSE(pos_in_item !=
489 ih_item_len
490 (B_N_PITEM_HEAD
491 (tbS0, item_pos)),
492 "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
493 ih_item_len
494 (B_N_PITEM_HEAD
495 (tbS0, item_pos)),
496 pos_in_item);
497
498 if (tb->lbytes >= pos_in_item) {
499 /* appended item will be in L[0] in whole */
500 int l_n;
501
502 /* this bytes number must be appended to the last item of L[h] */
503 l_n =
504 tb->lbytes -
505 pos_in_item;
506
507 /* Calculate new insert_size[0] */
508 tb->insert_size[0] -=
509 l_n;
510
511 RFALSE(tb->
512 insert_size[0] <=
513 0,
514 "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
515 tb->
516 insert_size[0]);
517 ret_val =
518 leaf_shift_left(tb,
519 tb->
520 lnum
521 [0],
522 ih_item_len
523 (B_N_PITEM_HEAD
524 (tbS0,
525 item_pos)));
526 /* Append to body of item in L[0] */
527 bi.tb = tb;
528 bi.bi_bh = tb->L[0];
529 bi.bi_parent =
530 tb->FL[0];
531 bi.bi_position =
532 get_left_neighbor_position
533 (tb, 0);
534 leaf_paste_in_buffer
535 (&bi,
536 n + item_pos -
537 ret_val,
538 ih_item_len
539 (B_N_PITEM_HEAD
540 (tb->L[0],
541 n + item_pos -
542 ret_val)), l_n,
543 body,
544 zeros_num >
545 l_n ? l_n :
546 zeros_num);
547 /* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
548 {
549 int version;
550 int temp_l =
551 l_n;
552
553 RFALSE
554 (ih_item_len
555 (B_N_PITEM_HEAD
556 (tbS0,
557 0)),
558 "PAP-12106: item length must be 0");
559 RFALSE
560 (comp_short_le_keys
561 (B_N_PKEY
562 (tbS0, 0),
563 B_N_PKEY
564 (tb->L[0],
565 n +
566 item_pos
567 -
568 ret_val)),
569 "PAP-12107: items must be of the same file");
570 if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val))) {
571 temp_l =
572 l_n
573 <<
574 (tb->
575 tb_sb->
576 s_blocksize_bits
577 -
578 UNFM_P_SHIFT);
579 }
580 /* update key of first item in S0 */
581 version =
582 ih_version
583 (B_N_PITEM_HEAD
584 (tbS0, 0));
585 set_le_key_k_offset
586 (version,
587 B_N_PKEY
588 (tbS0, 0),
589 le_key_k_offset
590 (version,
591 B_N_PKEY
592 (tbS0,
593 0)) +
594 temp_l);
595 /* update left delimiting key */
596 set_le_key_k_offset
597 (version,
598 B_N_PDELIM_KEY
599 (tb->
600 CFL[0],
601 tb->
602 lkey[0]),
603 le_key_k_offset
604 (version,
605 B_N_PDELIM_KEY
606 (tb->
607 CFL[0],
608 tb->
609 lkey[0]))
610 + temp_l);
611 }
612
613 /* Calculate new body, position in item and insert_size[0] */
614 if (l_n > zeros_num) {
615 body +=
616 (l_n -
617 zeros_num);
618 zeros_num = 0;
619 } else
620 zeros_num -=
621 l_n;
622 pos_in_item = 0;
623
624 RFALSE
625 (comp_short_le_keys
626 (B_N_PKEY(tbS0, 0),
627 B_N_PKEY(tb->L[0],
628 B_NR_ITEMS
629 (tb->
630 L[0]) -
631 1))
632 ||
633 !op_is_left_mergeable
634 (B_N_PKEY(tbS0, 0),
635 tbS0->b_size)
636 ||
637 !op_is_left_mergeable
638 (B_N_PDELIM_KEY
639 (tb->CFL[0],
640 tb->lkey[0]),
641 tbS0->b_size),
642 "PAP-12120: item must be merge-able with left neighboring item");
643 } else { /* only part of the appended item will be in L[0] */
644
645 /* Calculate position in item for append in S[0] */
646 pos_in_item -=
647 tb->lbytes;
648
649 RFALSE(pos_in_item <= 0,
650 "PAP-12125: no place for paste. pos_in_item=%d",
651 pos_in_item);
652
653 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
654 leaf_shift_left(tb,
655 tb->
656 lnum[0],
657 tb->
658 lbytes);
659 }
660 }
661 } else { /* appended item will be in L[0] in whole */
662
663 struct item_head *pasted;
664
665 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 */
666 /* then increment pos_in_item by the size of the last item in L[0] */
667 pasted =
668 B_N_PITEM_HEAD(tb->L[0],
669 n - 1);
670 if (is_direntry_le_ih(pasted))
671 pos_in_item +=
672 ih_entry_count
673 (pasted);
674 else
675 pos_in_item +=
676 ih_item_len(pasted);
677 }
678
679 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
680 ret_val =
681 leaf_shift_left(tb, tb->lnum[0],
682 tb->lbytes);
683 /* Append to body of item in L[0] */
684 bi.tb = tb;
685 bi.bi_bh = tb->L[0];
686 bi.bi_parent = tb->FL[0];
687 bi.bi_position =
688 get_left_neighbor_position(tb, 0);
689 leaf_paste_in_buffer(&bi,
690 n + item_pos -
691 ret_val,
692 pos_in_item,
693 tb->insert_size[0],
694 body, zeros_num);
695
696 /* if appended item is directory, paste entry */
697 pasted =
698 B_N_PITEM_HEAD(tb->L[0],
699 n + item_pos -
700 ret_val);
701 if (is_direntry_le_ih(pasted))
702 leaf_paste_entries(bi.bi_bh,
703 n +
704 item_pos -
705 ret_val,
706 pos_in_item,
707 1,
708 (struct
709 reiserfs_de_head
710 *)body,
711 body +
712 DEH_SIZE,
713 tb->
714 insert_size
715 [0]
716 );
717 /* if appended item is indirect item, put unformatted node into un list */
718 if (is_indirect_le_ih(pasted))
719 set_ih_free_space(pasted, 0);
720 tb->insert_size[0] = 0;
721 zeros_num = 0;
722 }
723 break;
724 default: /* cases d and t */
725 reiserfs_panic(tb->tb_sb,
726 "PAP-12130: balance_leaf: lnum > 0: unexpectable mode: %s(%d)",
727 (flag ==
728 M_DELETE) ? "DELETE" : ((flag ==
729 M_CUT)
730 ? "CUT"
731 :
732 "UNKNOWN"),
733 flag);
1da177e4 734 }
bd4c625c
LT		 735 } else {
736 /* new item doesn't fall into L[0] */
737 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
1da177e4 738 }
1da177e4 739 }
1da177e4 740
bd4c625c
LT		 741 /* tb->lnum[0] > 0 */
742 /* Calculate new item position */
743 item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
744
745 if (tb->rnum[0] > 0) {
746 /* shift rnum[0] items from S[0] to the right neighbor R[0] */
747 n = B_NR_ITEMS(tbS0);
748 switch (flag) {
749
750 case M_INSERT: /* insert item */
751 if (n - tb->rnum[0] < item_pos) { /* new item or its part falls to R[0] */
752 if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) { /* part of new item falls into R[0] */
753 loff_t old_key_comp, old_len,
754 r_zeros_number;
755 const char *r_body;
756 int version;
757 loff_t offset;
758
759 leaf_shift_right(tb, tb->rnum[0] - 1,
760 -1);
761
762 version = ih_version(ih);
763 /* Remember key component and item length */
764 old_key_comp = le_ih_k_offset(ih);
765 old_len = ih_item_len(ih);
766
767 /* Calculate key component and item length to insert into R[0] */
768 offset =
769 le_ih_k_offset(ih) +
770 ((old_len -
771 tb->
772 rbytes) << (is_indirect_le_ih(ih)
773 ? tb->tb_sb->
774 s_blocksize_bits -
775 UNFM_P_SHIFT : 0));
776 set_le_ih_k_offset(ih, offset);
777 put_ih_item_len(ih, tb->rbytes);
778 /* Insert part of the item into R[0] */
779 bi.tb = tb;
780 bi.bi_bh = tb->R[0];
781 bi.bi_parent = tb->FR[0];
782 bi.bi_position =
783 get_right_neighbor_position(tb, 0);
784 if ((old_len - tb->rbytes) > zeros_num) {
785 r_zeros_number = 0;
786 r_body =
787 body + (old_len -
788 tb->rbytes) -
789 zeros_num;
790 } else {
791 r_body = body;
792 r_zeros_number =
793 zeros_num - (old_len -
794 tb->rbytes);
795 zeros_num -= r_zeros_number;
796 }
797
798 leaf_insert_into_buf(&bi, 0, ih, r_body,
799 r_zeros_number);
800
801 /* Replace right delimiting key by first key in R[0] */
802 replace_key(tb, tb->CFR[0], tb->rkey[0],
803 tb->R[0], 0);
804
805 /* Calculate key component and item length to insert into S[0] */
806 set_le_ih_k_offset(ih, old_key_comp);
807 put_ih_item_len(ih,
808 old_len - tb->rbytes);
809
810 tb->insert_size[0] -= tb->rbytes;
811
812 } else { /* whole new item falls into R[0] */
813
814 /* Shift rnum[0]-1 items to R[0] */
815 ret_val =
816 leaf_shift_right(tb,
817 tb->rnum[0] - 1,
818 tb->rbytes);
819 /* Insert new item into R[0] */
820 bi.tb = tb;
821 bi.bi_bh = tb->R[0];
822 bi.bi_parent = tb->FR[0];
823 bi.bi_position =
824 get_right_neighbor_position(tb, 0);
825 leaf_insert_into_buf(&bi,
826 item_pos - n +
827 tb->rnum[0] - 1,
828 ih, body,
829 zeros_num);
830
831 if (item_pos - n + tb->rnum[0] - 1 == 0) {
832 replace_key(tb, tb->CFR[0],
833 tb->rkey[0],
834 tb->R[0], 0);
835
836 }
837 zeros_num = tb->insert_size[0] = 0;
838 }
839 } else { /* new item or part of it doesn't fall into R[0] */
1da177e4 840
bd4c625c 841 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
1da177e4 842 }
bd4c625c
LT		 843 break;
844
845 case M_PASTE: /* append item */
846
847 if (n - tb->rnum[0] <= item_pos) { /* pasted item or part of it falls to R[0] */
848 if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) { /* we must shift the part of the appended item */
849 if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) { /* we append to directory item */
850 int entry_count;
851
852 RFALSE(zeros_num,
853 "PAP-12145: invalid parameter in case of a directory");
854 entry_count =
855 I_ENTRY_COUNT(B_N_PITEM_HEAD
856 (tbS0,
857 item_pos));
858 if (entry_count - tb->rbytes <
859 pos_in_item)
860 /* new directory entry falls into R[0] */
861 {
862 int paste_entry_position;
863
864 RFALSE(tb->rbytes - 1 >=
865 entry_count
866 || !tb->
867 insert_size[0],
868 "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
869 tb->rbytes,
870 entry_count);
871 /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
872 leaf_shift_right(tb,
873 tb->
874 rnum
875 [0],
876 tb->
877 rbytes
878 - 1);
879 /* Paste given directory entry to directory item */
880 paste_entry_position =
881 pos_in_item -
882 entry_count +
883 tb->rbytes - 1;
884 bi.tb = tb;
885 bi.bi_bh = tb->R[0];
886 bi.bi_parent =
887 tb->FR[0];
888 bi.bi_position =
889 get_right_neighbor_position
890 (tb, 0);
891 leaf_paste_in_buffer
892 (&bi, 0,
893 paste_entry_position,
894 tb->insert_size[0],
895 body, zeros_num);
896 /* paste entry */
897 leaf_paste_entries(bi.
898 bi_bh,
899 0,
900 paste_entry_position,
901 1,
902 (struct
903 reiserfs_de_head
904 *)
905 body,
906 body
907 +
908 DEH_SIZE,
909 tb->
910 insert_size
911 [0]
912 );
913
914 if (paste_entry_position
915 == 0) {
916 /* change delimiting keys */
917 replace_key(tb,
918 tb->
919 CFR
920 [0],
921 tb->
922 rkey
923 [0],
924 tb->
925 R
926 [0],
927 0);
928 }
929
930 tb->insert_size[0] = 0;
931 pos_in_item++;
932 } else { /* new directory entry doesn't fall into R[0] */
933
934 leaf_shift_right(tb,
935 tb->
936 rnum
937 [0],
938 tb->
939 rbytes);
940 }
941 } else { /* regular object */
942
943 int n_shift, n_rem,
944 r_zeros_number;
945 const char *r_body;
946
947 /* Calculate number of bytes which must be shifted from appended item */
948 if ((n_shift =
949 tb->rbytes -
950 tb->insert_size[0]) < 0)
951 n_shift = 0;
952
953 RFALSE(pos_in_item !=
954 ih_item_len
955 (B_N_PITEM_HEAD
956 (tbS0, item_pos)),
957 "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
958 pos_in_item,
959 ih_item_len
960 (B_N_PITEM_HEAD
961 (tbS0, item_pos)));
962
963 leaf_shift_right(tb,
964 tb->rnum[0],
965 n_shift);
966 /* Calculate number of bytes which must remain in body after appending to R[0] */
967 if ((n_rem =
968 tb->insert_size[0] -
969 tb->rbytes) < 0)
970 n_rem = 0;
971
972 {
973 int version;
974 unsigned long temp_rem =
975 n_rem;
976
977 version =
978 ih_version
979 (B_N_PITEM_HEAD
980 (tb->R[0], 0));
981 if (is_indirect_le_key
982 (version,
983 B_N_PKEY(tb->R[0],
984 0))) {
985 temp_rem =
986 n_rem <<
987 (tb->tb_sb->
988 s_blocksize_bits
989 -
990 UNFM_P_SHIFT);
991 }
992 set_le_key_k_offset
993 (version,
994 B_N_PKEY(tb->R[0],
995 0),
996 le_key_k_offset
997 (version,
998 B_N_PKEY(tb->R[0],
999 0)) +
1000 temp_rem);
1001 set_le_key_k_offset
1002 (version,
1003 B_N_PDELIM_KEY(tb->
1004 CFR
1005 [0],
1006 tb->
1007 rkey
1008 [0]),
1009 le_key_k_offset
1010 (version,
1011 B_N_PDELIM_KEY
1012 (tb->CFR[0],
1013 tb->rkey[0])) +
1014 temp_rem);
1015 }
1da177e4
LT		 1016/* k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
1017 k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
bd4c625c
LT		 1018 do_balance_mark_internal_dirty
1019 (tb, tb->CFR[0], 0);
1020
1021 /* Append part of body into R[0] */
1022 bi.tb = tb;
1023 bi.bi_bh = tb->R[0];
1024 bi.bi_parent = tb->FR[0];
1025 bi.bi_position =
1026 get_right_neighbor_position
1027 (tb, 0);
1028 if (n_rem > zeros_num) {
1029 r_zeros_number = 0;
1030 r_body =
1031 body + n_rem -
1032 zeros_num;
1033 } else {
1034 r_body = body;
1035 r_zeros_number =
1036 zeros_num - n_rem;
1037 zeros_num -=
1038 r_zeros_number;
1039 }
1040
1041 leaf_paste_in_buffer(&bi, 0,
1042 n_shift,
1043 tb->
1044 insert_size
1045 [0] -
1046 n_rem,
1047 r_body,
1048 r_zeros_number);
1049
1050 if (is_indirect_le_ih
1051 (B_N_PITEM_HEAD
1052 (tb->R[0], 0))) {
1da177e4 1053#if 0
bd4c625c
LT		 1054 RFALSE(n_rem,
1055 "PAP-12160: paste more than one unformatted node pointer");
1da177e4 1056#endif
bd4c625c
LT		 1057 set_ih_free_space
1058 (B_N_PITEM_HEAD
1059 (tb->R[0], 0), 0);
1060 }
1061 tb->insert_size[0] = n_rem;
1062 if (!n_rem)
1063 pos_in_item++;
1064 }
1065 } else { /* pasted item in whole falls into R[0] */
1066
1067 struct item_head *pasted;
1068
1069 ret_val =
1070 leaf_shift_right(tb, tb->rnum[0],
1071 tb->rbytes);
1072 /* append item in R[0] */
1073 if (pos_in_item >= 0) {
1074 bi.tb = tb;
1075 bi.bi_bh = tb->R[0];
1076 bi.bi_parent = tb->FR[0];
1077 bi.bi_position =
1078 get_right_neighbor_position
1079 (tb, 0);
1080 leaf_paste_in_buffer(&bi,
1081 item_pos -
1082 n +
1083 tb->
1084 rnum[0],
1085 pos_in_item,
1086 tb->
1087 insert_size
1088 [0], body,
1089 zeros_num);
1090 }
1091
1092 /* paste new entry, if item is directory item */
1093 pasted =
1094 B_N_PITEM_HEAD(tb->R[0],
1095 item_pos - n +
1096 tb->rnum[0]);
1097 if (is_direntry_le_ih(pasted)
1098 && pos_in_item >= 0) {
1099 leaf_paste_entries(bi.bi_bh,
1100 item_pos -
1101 n +
1102 tb->rnum[0],
1103 pos_in_item,
1104 1,
1105 (struct
1106 reiserfs_de_head
1107 *)body,
1108 body +
1109 DEH_SIZE,
1110 tb->
1111 insert_size
1112 [0]
1113 );
1114 if (!pos_in_item) {
1115
1116 RFALSE(item_pos - n +
1117 tb->rnum[0],
1118 "PAP-12165: directory item must be first item of node when pasting is in 0th position");
1119
1120 /* update delimiting keys */
1121 replace_key(tb,
1122 tb->CFR[0],
1123 tb->rkey[0],
1124 tb->R[0],
1125 0);
1126 }
1127 }
1128
1129 if (is_indirect_le_ih(pasted))
1130 set_ih_free_space(pasted, 0);
1131 zeros_num = tb->insert_size[0] = 0;
1132 }
1133 } else { /* new item doesn't fall into R[0] */
1da177e4 1134
bd4c625c 1135 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
1da177e4 1136 }
bd4c625c
LT		 1137 break;
1138 default: /* cases d and t */
1139 reiserfs_panic(tb->tb_sb,
1140 "PAP-12175: balance_leaf: rnum > 0: unexpectable mode: %s(%d)",
1141 (flag ==
1142 M_DELETE) ? "DELETE" : ((flag ==
1143 M_CUT) ? "CUT"
1144 : "UNKNOWN"),
1145 flag);
1da177e4 1146 }
1da177e4 1147
bd4c625c 1148 }
1da177e4 1149
bd4c625c
LT		 1150 /* tb->rnum[0] > 0 */
1151 RFALSE(tb->blknum[0] > 3,
1152 "PAP-12180: blknum can not be %d. It must be <= 3",
1153 tb->blknum[0]);
1154 RFALSE(tb->blknum[0] < 0,
1155 "PAP-12185: blknum can not be %d. It must be >= 0",
1156 tb->blknum[0]);
1157
1158 /* if while adding to a node we discover that it is possible to split
1159 it in two, and merge the left part into the left neighbor and the
1160 right part into the right neighbor, eliminating the node */
1161 if (tb->blknum[0] == 0) { /* node S[0] is empty now */
1162
1163 RFALSE(!tb->lnum[0] || !tb->rnum[0],
1164 "PAP-12190: lnum and rnum must not be zero");
1165 /* if insertion was done before 0-th position in R[0], right
1166 delimiting key of the tb->L[0]'s and left delimiting key are
1167 not set correctly */
1168 if (tb->CFL[0]) {
1169 if (!tb->CFR[0])
1170 reiserfs_panic(tb->tb_sb,
1171 "vs-12195: balance_leaf: CFR not initialized");
1172 copy_key(B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]),
1173 B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]));
1174 do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
1175 }
1da177e4 1176
bd4c625c
LT		 1177 reiserfs_invalidate_buffer(tb, tbS0);
1178 return 0;
1179 }
1da177e4 1180
bd4c625c
LT		 1181 /* Fill new nodes that appear in place of S[0] */
1182
1183 /* I am told that this copying is because we need an array to enable
1184 the looping code. -Hans */
1185 snum[0] = tb->s1num, snum[1] = tb->s2num;
1186 sbytes[0] = tb->s1bytes;
1187 sbytes[1] = tb->s2bytes;
1188 for (i = tb->blknum[0] - 2; i >= 0; i--) {
1189
1190 RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i,
1191 snum[i]);
1192
1193 /* here we shift from S to S_new nodes */
1194
1195 S_new[i] = get_FEB(tb);
1196
1197 /* initialized block type and tree level */
1198 set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
1199
1200 n = B_NR_ITEMS(tbS0);
1201
1202 switch (flag) {
1203 case M_INSERT: /* insert item */
1204
1205 if (n - snum[i] < item_pos) { /* new item or it's part falls to first new node S_new[i] */
1206 if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) { /* part of new item falls into S_new[i] */
1207 int old_key_comp, old_len,
1208 r_zeros_number;
1209 const char *r_body;
1210 int version;
1211
1212 /* Move snum[i]-1 items from S[0] to S_new[i] */
1213 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1214 snum[i] - 1, -1,
1215 S_new[i]);
1216 /* Remember key component and item length */
1217 version = ih_version(ih);
1218 old_key_comp = le_ih_k_offset(ih);
1219 old_len = ih_item_len(ih);
1220
1221 /* Calculate key component and item length to insert into S_new[i] */
1222 set_le_ih_k_offset(ih,
1223 le_ih_k_offset(ih) +
1224 ((old_len -
1225 sbytes[i]) <<
1226 (is_indirect_le_ih
1227 (ih) ? tb->tb_sb->
1228 s_blocksize_bits -
1229 UNFM_P_SHIFT :
1230 0)));
1231
1232 put_ih_item_len(ih, sbytes[i]);
1233
1234 /* Insert part of the item into S_new[i] before 0-th item */
1235 bi.tb = tb;
1236 bi.bi_bh = S_new[i];
1237 bi.bi_parent = NULL;
1238 bi.bi_position = 0;
1239
1240 if ((old_len - sbytes[i]) > zeros_num) {
1241 r_zeros_number = 0;
1242 r_body =
1243 body + (old_len -
1244 sbytes[i]) -
1245 zeros_num;
1246 } else {
1247 r_body = body;
1248 r_zeros_number =
1249 zeros_num - (old_len -
1250 sbytes[i]);
1251 zeros_num -= r_zeros_number;
1252 }
1253
1254 leaf_insert_into_buf(&bi, 0, ih, r_body,
1255 r_zeros_number);
1256
1257 /* Calculate key component and item length to insert into S[i] */
1258 set_le_ih_k_offset(ih, old_key_comp);
1259 put_ih_item_len(ih,
1260 old_len - sbytes[i]);
1261 tb->insert_size[0] -= sbytes[i];
1262 } else { /* whole new item falls into S_new[i] */
1263
1264 /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
1265 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1266 snum[i] - 1, sbytes[i],
1267 S_new[i]);
1268
1269 /* Insert new item into S_new[i] */
1270 bi.tb = tb;
1271 bi.bi_bh = S_new[i];
1272 bi.bi_parent = NULL;
1273 bi.bi_position = 0;
1274 leaf_insert_into_buf(&bi,
1275 item_pos - n +
1276 snum[i] - 1, ih,
1277 body, zeros_num);
1278
1279 zeros_num = tb->insert_size[0] = 0;
1280 }
1281 }
1da177e4 1282
bd4c625c 1283 else { /* new item or it part don't falls into S_new[i] */
1da177e4 1284
bd4c625c
LT		 1285 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1286 snum[i], sbytes[i], S_new[i]);
1da177e4 1287 }
bd4c625c
LT		 1288 break;
1289
1290 case M_PASTE: /* append item */
1291
1292 if (n - snum[i] <= item_pos) { /* pasted item or part if it falls to S_new[i] */
1293 if (item_pos == n - snum[i] && sbytes[i] != -1) { /* we must shift part of the appended item */
1294 struct item_head *aux_ih;
1295
1296 RFALSE(ih, "PAP-12210: ih must be 0");
1297
1298 if (is_direntry_le_ih
1299 (aux_ih =
1300 B_N_PITEM_HEAD(tbS0, item_pos))) {
1301 /* we append to directory item */
1302
1303 int entry_count;
1304
1305 entry_count =
1306 ih_entry_count(aux_ih);
1307
1308 if (entry_count - sbytes[i] <
1309 pos_in_item
1310 && pos_in_item <=
1311 entry_count) {
1312 /* new directory entry falls into S_new[i] */
1313
1314 RFALSE(!tb->
1315 insert_size[0],
1316 "PAP-12215: insert_size is already 0");
1317 RFALSE(sbytes[i] - 1 >=
1318 entry_count,
1319 "PAP-12220: there are no so much entries (%d), only %d",
1320 sbytes[i] - 1,
1321 entry_count);
1322
1323 /* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
1324 leaf_move_items
1325 (LEAF_FROM_S_TO_SNEW,
1326 tb, snum[i],
1327 sbytes[i] - 1,
1328 S_new[i]);
1329 /* Paste given directory entry to directory item */
1330 bi.tb = tb;
1331 bi.bi_bh = S_new[i];
1332 bi.bi_parent = NULL;
1333 bi.bi_position = 0;
1334 leaf_paste_in_buffer
1335 (&bi, 0,
1336 pos_in_item -
1337 entry_count +
1338 sbytes[i] - 1,
1339 tb->insert_size[0],
1340 body, zeros_num);
1341 /* paste new directory entry */
1342 leaf_paste_entries(bi.
1343 bi_bh,
1344 0,
1345 pos_in_item
1346 -
1347 entry_count
1348 +
1349 sbytes
1350 [i] -
1351 1, 1,
1352 (struct
1353 reiserfs_de_head
1354 *)
1355 body,
1356 body
1357 +
1358 DEH_SIZE,
1359 tb->
1360 insert_size
1361 [0]
1362 );
1363 tb->insert_size[0] = 0;
1364 pos_in_item++;
1365 } else { /* new directory entry doesn't fall into S_new[i] */
1366 leaf_move_items
1367 (LEAF_FROM_S_TO_SNEW,
1368 tb, snum[i],
1369 sbytes[i],
1370 S_new[i]);
1371 }
1372 } else { /* regular object */
1373
1374 int n_shift, n_rem,
1375 r_zeros_number;
1376 const char *r_body;
1377
1378 RFALSE(pos_in_item !=
1379 ih_item_len
1380 (B_N_PITEM_HEAD
1381 (tbS0, item_pos))
1382 || tb->insert_size[0] <=
1383 0,
1384 "PAP-12225: item too short or insert_size <= 0");
1385
1386 /* Calculate number of bytes which must be shifted from appended item */
1387 n_shift =
1388 sbytes[i] -
1389 tb->insert_size[0];
1390 if (n_shift < 0)
1391 n_shift = 0;
1392 leaf_move_items
1393 (LEAF_FROM_S_TO_SNEW, tb,
1394 snum[i], n_shift,
1395 S_new[i]);
1396
1397 /* Calculate number of bytes which must remain in body after append to S_new[i] */
1398 n_rem =
1399 tb->insert_size[0] -
1400 sbytes[i];
1401 if (n_rem < 0)
1402 n_rem = 0;
1403 /* Append part of body into S_new[0] */
1404 bi.tb = tb;
1405 bi.bi_bh = S_new[i];
1406 bi.bi_parent = NULL;
1407 bi.bi_position = 0;
1408
1409 if (n_rem > zeros_num) {
1410 r_zeros_number = 0;
1411 r_body =
1412 body + n_rem -
1413 zeros_num;
1414 } else {
1415 r_body = body;
1416 r_zeros_number =
1417 zeros_num - n_rem;
1418 zeros_num -=
1419 r_zeros_number;
1420 }
1421
1422 leaf_paste_in_buffer(&bi, 0,
1423 n_shift,
1424 tb->
1425 insert_size
1426 [0] -
1427 n_rem,
1428 r_body,
1429 r_zeros_number);
1430 {
1431 struct item_head *tmp;
1432
1433 tmp =
1434 B_N_PITEM_HEAD(S_new
1435 [i],
1436 0);
1437 if (is_indirect_le_ih
1438 (tmp)) {
1439 set_ih_free_space
1440 (tmp, 0);
1441 set_le_ih_k_offset
1442 (tmp,
1443 le_ih_k_offset
1444 (tmp) +
1445 (n_rem <<
1446 (tb->
1447 tb_sb->
1448 s_blocksize_bits
1449 -
1450 UNFM_P_SHIFT)));
1451 } else {
1452 set_le_ih_k_offset
1453 (tmp,
1454 le_ih_k_offset
1455 (tmp) +
1456 n_rem);
1457 }
1458 }
1459
1460 tb->insert_size[0] = n_rem;
1461 if (!n_rem)
1462 pos_in_item++;
1463 }
1464 } else
1465 /* item falls wholly into S_new[i] */
1466 {
1467 int ret_val;
1468 struct item_head *pasted;
1da177e4 1469
bd4c625c
LT		 1470#ifdef CONFIG_REISERFS_CHECK
1471 struct item_head *ih =
1472 B_N_PITEM_HEAD(tbS0, item_pos);
1473
1474 if (!is_direntry_le_ih(ih)
1475 && (pos_in_item != ih_item_len(ih)
1476 || tb->insert_size[0] <= 0))
1477 reiserfs_panic(tb->tb_sb,
1478 "PAP-12235: balance_leaf: pos_in_item must be equal to ih_item_len");
1479#endif /* CONFIG_REISERFS_CHECK */
1480
1481 ret_val =
1482 leaf_move_items(LEAF_FROM_S_TO_SNEW,
1483 tb, snum[i],
1484 sbytes[i],
1485 S_new[i]);
1486
1487 RFALSE(ret_val,
1488 "PAP-12240: unexpected value returned by leaf_move_items (%d)",
1489 ret_val);
1490
1491 /* paste into item */
1492 bi.tb = tb;
1493 bi.bi_bh = S_new[i];
1494 bi.bi_parent = NULL;
1495 bi.bi_position = 0;
1496 leaf_paste_in_buffer(&bi,
1497 item_pos - n +
1498 snum[i],
1499 pos_in_item,
1500 tb->insert_size[0],
1501 body, zeros_num);
1502
1503 pasted =
1504 B_N_PITEM_HEAD(S_new[i],
1505 item_pos - n +
1506 snum[i]);
1507 if (is_direntry_le_ih(pasted)) {
1508 leaf_paste_entries(bi.bi_bh,
1509 item_pos -
1510 n + snum[i],
1511 pos_in_item,
1512 1,
1513 (struct
1514 reiserfs_de_head
1515 *)body,
1516 body +
1517 DEH_SIZE,
1518 tb->
1519 insert_size
1520 [0]
1521 );
1522 }
1523
1524 /* if we paste to indirect item update ih_free_space */
1525 if (is_indirect_le_ih(pasted))
1526 set_ih_free_space(pasted, 0);
1527 zeros_num = tb->insert_size[0] = 0;
1528 }
1da177e4
LT		 1529 }
1530
bd4c625c 1531 else { /* pasted item doesn't fall into S_new[i] */
1da177e4 1532
bd4c625c
LT		 1533 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1534 snum[i], sbytes[i], S_new[i]);
1535 }
1536 break;
1537 default: /* cases d and t */
1538 reiserfs_panic(tb->tb_sb,
1539 "PAP-12245: balance_leaf: blknum > 2: unexpectable mode: %s(%d)",
1540 (flag ==
1541 M_DELETE) ? "DELETE" : ((flag ==
1542 M_CUT) ? "CUT"
1543 : "UNKNOWN"),
1544 flag);
1da177e4 1545 }
1da177e4 1546
bd4c625c
LT		 1547 memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
1548 insert_ptr[i] = S_new[i];
1549
1550 RFALSE(!buffer_journaled(S_new[i])
1551 || buffer_journal_dirty(S_new[i])
1552 || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)",
1553 i, S_new[i]);
1da177e4
LT		 1554 }
1555
bd4c625c
LT		 1556 /* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
1557 affected item which remains in S */
1558 if (0 <= item_pos && item_pos < tb->s0num) { /* if we must insert or append into buffer S[0] */
1559
1560 switch (flag) {
1561 case M_INSERT: /* insert item into S[0] */
1562 bi.tb = tb;
1563 bi.bi_bh = tbS0;
1564 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
1565 bi.bi_position = PATH_H_POSITION(tb->tb_path, 1);
1566 leaf_insert_into_buf(&bi, item_pos, ih, body,
1567 zeros_num);
1568
1569 /* If we insert the first key change the delimiting key */
1570 if (item_pos == 0) {
1571 if (tb->CFL[0]) /* can be 0 in reiserfsck */
1572 replace_key(tb, tb->CFL[0], tb->lkey[0],
1573 tbS0, 0);
1da177e4
LT		 1574
1575 }
bd4c625c
LT		 1576 break;
1577
1578 case M_PASTE:{ /* append item in S[0] */
1579 struct item_head *pasted;
1580
1581 pasted = B_N_PITEM_HEAD(tbS0, item_pos);
1582 /* when directory, may be new entry already pasted */
1583 if (is_direntry_le_ih(pasted)) {
1584 if (pos_in_item >= 0 &&
1585 pos_in_item <=
1586 ih_entry_count(pasted)) {
1587
1588 RFALSE(!tb->insert_size[0],
1589 "PAP-12260: insert_size is 0 already");
1590
1591 /* prepare space */
1592 bi.tb = tb;
1593 bi.bi_bh = tbS0;
1594 bi.bi_parent =
1595 PATH_H_PPARENT(tb->tb_path,
1596 0);
1597 bi.bi_position =
1598 PATH_H_POSITION(tb->tb_path,
1599 1);
1600 leaf_paste_in_buffer(&bi,
1601 item_pos,
1602 pos_in_item,
1603 tb->
1604 insert_size
1605 [0], body,
1606 zeros_num);
1607
1608 /* paste entry */
1609 leaf_paste_entries(bi.bi_bh,
1610 item_pos,
1611 pos_in_item,
1612 1,
1613 (struct
1614 reiserfs_de_head
1615 *)body,
1616 body +
1617 DEH_SIZE,
1618 tb->
1619 insert_size
1620 [0]
1621 );
1622 if (!item_pos && !pos_in_item) {
1623 RFALSE(!tb->CFL[0]
1624 || !tb->L[0],
1625 "PAP-12270: CFL[0]/L[0] must be specified");
1626 if (tb->CFL[0]) {
1627 replace_key(tb,
1628 tb->
1629 CFL
1630 [0],
1631 tb->
1632 lkey
1633 [0],
1634 tbS0,
1635 0);
1636
1637 }
1638 }
1639 tb->insert_size[0] = 0;
1640 }
1641 } else { /* regular object */
1642 if (pos_in_item == ih_item_len(pasted)) {
1643
1644 RFALSE(tb->insert_size[0] <= 0,
1645 "PAP-12275: insert size must not be %d",
1646 tb->insert_size[0]);
1647 bi.tb = tb;
1648 bi.bi_bh = tbS0;
1649 bi.bi_parent =
1650 PATH_H_PPARENT(tb->tb_path,
1651 0);
1652 bi.bi_position =
1653 PATH_H_POSITION(tb->tb_path,
1654 1);
1655 leaf_paste_in_buffer(&bi,
1656 item_pos,
1657 pos_in_item,
1658 tb->
1659 insert_size
1660 [0], body,
1661 zeros_num);
1662
1663 if (is_indirect_le_ih(pasted)) {
1da177e4 1664#if 0
bd4c625c
LT		 1665 RFALSE(tb->
1666 insert_size[0] !=
1667 UNFM_P_SIZE,
1668 "PAP-12280: insert_size for indirect item must be %d, not %d",
1669 UNFM_P_SIZE,
1670 tb->
1671 insert_size[0]);
1da177e4 1672#endif
bd4c625c
LT		 1673 set_ih_free_space
1674 (pasted, 0);
1675 }
1676 tb->insert_size[0] = 0;
1677 }
1da177e4 1678#ifdef CONFIG_REISERFS_CHECK
bd4c625c
LT		 1679 else {
1680 if (tb->insert_size[0]) {
1681 print_cur_tb("12285");
1682 reiserfs_panic(tb->
1683 tb_sb,
1684 "PAP-12285: balance_leaf: insert_size must be 0 (%d)",
1685 tb->
1686 insert_size
1687 [0]);
1688 }
1689 }
1690#endif /* CONFIG_REISERFS_CHECK */
1691
1692 }
1693 } /* case M_PASTE: */
1da177e4 1694 }
1da177e4 1695 }
1da177e4 1696#ifdef CONFIG_REISERFS_CHECK
bd4c625c
LT		 1697 if (flag == M_PASTE && tb->insert_size[0]) {
1698 print_cur_tb("12290");
1699 reiserfs_panic(tb->tb_sb,
1700 "PAP-12290: balance_leaf: insert_size is still not 0 (%d)",
1701 tb->insert_size[0]);
1702 }
1703#endif /* CONFIG_REISERFS_CHECK */
1da177e4 1704
bd4c625c
LT		 1705 return 0;
1706} /* Leaf level of the tree is balanced (end of balance_leaf) */
1da177e4
LT		 1707
1708/* Make empty node */
bd4c625c 1709void make_empty_node(struct buffer_info *bi)
1da177e4 1710{
bd4c625c 1711 struct block_head *blkh;
1da177e4 1712
bd4c625c 1713 RFALSE(bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");
1da177e4 1714
bd4c625c
LT		 1715 blkh = B_BLK_HEAD(bi->bi_bh);
1716 set_blkh_nr_item(blkh, 0);
1717 set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
1da177e4 1718
bd4c625c
LT		 1719 if (bi->bi_parent)
1720 B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0; /* Endian safe if 0 */
1da177e4
LT		 1721}
1722
1da177e4 1723/* Get first empty buffer */
bd4c625c 1724struct buffer_head *get_FEB(struct tree_balance *tb)
1da177e4 1725{
bd4c625c
LT		 1726 int i;
1727 struct buffer_head *first_b;
1728 struct buffer_info bi;
1da177e4 1729
bd4c625c
LT		 1730 for (i = 0; i < MAX_FEB_SIZE; i++)
1731 if (tb->FEB[i] != 0)
1732 break;
1733
1734 if (i == MAX_FEB_SIZE)
1735 reiserfs_panic(tb->tb_sb,
1736 "vs-12300: get_FEB: FEB list is empty");
1737
1738 bi.tb = tb;
1739 bi.bi_bh = first_b = tb->FEB[i];
1740 bi.bi_parent = NULL;
1741 bi.bi_position = 0;
1742 make_empty_node(&bi);
1743 set_buffer_uptodate(first_b);
1744 tb->FEB[i] = NULL;
1745 tb->used[i] = first_b;
1746
1747 return (first_b);
1748}
1da177e4
LT		 1749
1750/* This is now used because reiserfs_free_block has to be able to
1751** schedule.
1752*/
bd4c625c 1753static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
1da177e4 1754{
bd4c625c
LT		 1755 int i;
1756
1757 if (buffer_dirty(bh))
1758 reiserfs_warning(tb->tb_sb,
1759 "store_thrown deals with dirty buffer");
1760 for (i = 0; i < sizeof(tb->thrown) / sizeof(tb->thrown[0]); i++)
1761 if (!tb->thrown[i]) {
1762 tb->thrown[i] = bh;
1763 get_bh(bh); /* free_thrown puts this */
1764 return;
1765 }
1766 reiserfs_warning(tb->tb_sb, "store_thrown: too many thrown buffers");
1da177e4
LT		 1767}
1768
bd4c625c
LT		 1769static void free_thrown(struct tree_balance *tb)
1770{
1771 int i;
1772 b_blocknr_t blocknr;
1773 for (i = 0; i < sizeof(tb->thrown) / sizeof(tb->thrown[0]); i++) {
1774 if (tb->thrown[i]) {
1775 blocknr = tb->thrown[i]->b_blocknr;
1776 if (buffer_dirty(tb->thrown[i]))
1777 reiserfs_warning(tb->tb_sb,
1778 "free_thrown deals with dirty buffer %d",
1779 blocknr);
1780 brelse(tb->thrown[i]); /* incremented in store_thrown */
1781 reiserfs_free_block(tb->transaction_handle, NULL,
1782 blocknr, 0);
1783 }
1da177e4 1784 }
1da177e4
LT		 1785}
1786
bd4c625c 1787void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
1da177e4 1788{
bd4c625c
LT		 1789 struct block_head *blkh;
1790 blkh = B_BLK_HEAD(bh);
1791 set_blkh_level(blkh, FREE_LEVEL);
1792 set_blkh_nr_item(blkh, 0);
1793
1794 clear_buffer_dirty(bh);
1795 store_thrown(tb, bh);
1da177e4
LT		 1796}
1797
1798/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
bd4c625c
LT		 1799void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
1800 struct buffer_head *src, int n_src)
1da177e4
LT		 1801{
1802
bd4c625c
LT		 1803 RFALSE(dest == NULL || src == NULL,
1804 "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
1805 src, dest);
1806 RFALSE(!B_IS_KEYS_LEVEL(dest),
1807 "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
1808 dest);
1809 RFALSE(n_dest < 0 || n_src < 0,
1810 "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
1811 RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
1812 "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
1813 n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
1814
1815 if (B_IS_ITEMS_LEVEL(src))
1816 /* source buffer contains leaf node */
1817 memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PITEM_HEAD(src, n_src),
1818 KEY_SIZE);
1819 else
1820 memcpy(B_N_PDELIM_KEY(dest, n_dest), B_N_PDELIM_KEY(src, n_src),
1821 KEY_SIZE);
1822
1823 do_balance_mark_internal_dirty(tb, dest, 0);
1da177e4
LT		 1824}
1825
bd4c625c 1826int get_left_neighbor_position(struct tree_balance *tb, int h)
1da177e4 1827{
bd4c625c 1828 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1da177e4 1829
bd4c625c
LT		 1830 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == 0 || tb->FL[h] == 0,
1831 "vs-12325: FL[%d](%p) or F[%d](%p) does not exist",
1832 h, tb->FL[h], h, PATH_H_PPARENT(tb->tb_path, h));
1da177e4 1833
bd4c625c
LT		 1834 if (Sh_position == 0)
1835 return B_NR_ITEMS(tb->FL[h]);
1836 else
1837 return Sh_position - 1;
1da177e4
LT		 1838}
1839
bd4c625c 1840int get_right_neighbor_position(struct tree_balance *tb, int h)
1da177e4 1841{
bd4c625c 1842 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
1da177e4 1843
bd4c625c
LT		 1844 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == 0 || tb->FR[h] == 0,
1845 "vs-12330: F[%d](%p) or FR[%d](%p) does not exist",
1846 h, PATH_H_PPARENT(tb->tb_path, h), h, tb->FR[h]);
1da177e4 1847
bd4c625c
LT		 1848 if (Sh_position == B_NR_ITEMS(PATH_H_PPARENT(tb->tb_path, h)))
1849 return 0;
1850 else
1851 return Sh_position + 1;
1da177e4
LT		 1852}
1853
1da177e4
LT		 1854#ifdef CONFIG_REISERFS_CHECK
1855
bd4c625c
LT		 1856int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
1857static void check_internal_node(struct super_block *s, struct buffer_head *bh,
1858 char *mes)
1da177e4 1859{
bd4c625c
LT		 1860 struct disk_child *dc;
1861 int i;
1da177e4 1862
bd4c625c 1863 RFALSE(!bh, "PAP-12336: bh == 0");
1da177e4 1864
bd4c625c
LT		 1865 if (!bh || !B_IS_IN_TREE(bh))
1866 return;
1da177e4 1867
bd4c625c
LT		 1868 RFALSE(!buffer_dirty(bh) &&
1869 !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
1870 "PAP-12337: buffer (%b) must be dirty", bh);
1871 dc = B_N_CHILD(bh, 0);
1da177e4 1872
bd4c625c
LT		 1873 for (i = 0; i <= B_NR_ITEMS(bh); i++, dc++) {
1874 if (!is_reusable(s, dc_block_number(dc), 1)) {
1875 print_cur_tb(mes);
1876 reiserfs_panic(s,
1877 "PAP-12338: check_internal_node: invalid child pointer %y in %b",
1878 dc, bh);
1879 }
1880 }
1da177e4
LT		 1881}
1882
bd4c625c
LT		 1883static int locked_or_not_in_tree(struct buffer_head *bh, char *which)
1884{
1885 if ((!buffer_journal_prepared(bh) && buffer_locked(bh)) ||
1886 !B_IS_IN_TREE(bh)) {
1887 reiserfs_warning(NULL,
1888 "vs-12339: locked_or_not_in_tree: %s (%b)",
1889 which, bh);
1890 return 1;
1891 }
1892 return 0;
1893}
1da177e4 1894
bd4c625c 1895static int check_before_balancing(struct tree_balance *tb)
1da177e4 1896{
bd4c625c
LT		 1897 int retval = 0;
1898
1899 if (cur_tb) {
1900 reiserfs_panic(tb->tb_sb, "vs-12335: check_before_balancing: "
1901 "suspect that schedule occurred based on cur_tb not being null at this point in code. "
1902 "do_balance cannot properly handle schedule occurring while it runs.");
1da177e4 1903 }
bd4c625c
LT		 1904
1905 /* double check that buffers that we will modify are unlocked. (fix_nodes should already have
1906 prepped all of these for us). */
1907 if (tb->lnum[0]) {
1908 retval |= locked_or_not_in_tree(tb->L[0], "L[0]");
1909 retval |= locked_or_not_in_tree(tb->FL[0], "FL[0]");
1910 retval |= locked_or_not_in_tree(tb->CFL[0], "CFL[0]");
1911 check_leaf(tb->L[0]);
1da177e4 1912 }
bd4c625c
LT		 1913 if (tb->rnum[0]) {
1914 retval |= locked_or_not_in_tree(tb->R[0], "R[0]");
1915 retval |= locked_or_not_in_tree(tb->FR[0], "FR[0]");
1916 retval |= locked_or_not_in_tree(tb->CFR[0], "CFR[0]");
1917 check_leaf(tb->R[0]);
1918 }
1919 retval |= locked_or_not_in_tree(PATH_PLAST_BUFFER(tb->tb_path), "S[0]");
1920 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1da177e4 1921
bd4c625c
LT		 1922 return retval;
1923}
1da177e4 1924
bd4c625c 1925static void check_after_balance_leaf(struct tree_balance *tb)
1da177e4 1926{
bd4c625c
LT		 1927 if (tb->lnum[0]) {
1928 if (B_FREE_SPACE(tb->L[0]) !=
1929 MAX_CHILD_SIZE(tb->L[0]) -
1930 dc_size(B_N_CHILD
1931 (tb->FL[0], get_left_neighbor_position(tb, 0)))) {
1932 print_cur_tb("12221");
1933 reiserfs_panic(tb->tb_sb,
1934 "PAP-12355: check_after_balance_leaf: shift to left was incorrect");
1935 }
1936 }
1937 if (tb->rnum[0]) {
1938 if (B_FREE_SPACE(tb->R[0]) !=
1939 MAX_CHILD_SIZE(tb->R[0]) -
1940 dc_size(B_N_CHILD
1941 (tb->FR[0], get_right_neighbor_position(tb, 0)))) {
1942 print_cur_tb("12222");
1943 reiserfs_panic(tb->tb_sb,
1944 "PAP-12360: check_after_balance_leaf: shift to right was incorrect");
1945 }
1946 }
1947 if (PATH_H_PBUFFER(tb->tb_path, 1) &&
1948 (B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0)) !=
1949 (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1950 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1951 PATH_H_POSITION(tb->tb_path, 1)))))) {
1952 int left = B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0));
1953 int right = (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1954 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1955 PATH_H_POSITION(tb->tb_path,
1956 1))));
1957 print_cur_tb("12223");
1958 reiserfs_warning(tb->tb_sb,
1959 "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
1960 "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d",
1961 left,
1962 MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)),
1963 PATH_H_PBUFFER(tb->tb_path, 1),
1964 PATH_H_POSITION(tb->tb_path, 1),
1965 dc_size(B_N_CHILD
1966 (PATH_H_PBUFFER(tb->tb_path, 1),
1967 PATH_H_POSITION(tb->tb_path, 1))),
1968 right);
1969 reiserfs_panic(tb->tb_sb,
1970 "PAP-12365: check_after_balance_leaf: S is incorrect");
1971 }
1da177e4
LT		 1972}
1973
bd4c625c 1974static void check_leaf_level(struct tree_balance *tb)
1da177e4 1975{
bd4c625c
LT		 1976 check_leaf(tb->L[0]);
1977 check_leaf(tb->R[0]);
1978 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1979}
1da177e4 1980
bd4c625c
LT		 1981static void check_internal_levels(struct tree_balance *tb)
1982{
1983 int h;
1984
1985 /* check all internal nodes */
1986 for (h = 1; tb->insert_size[h]; h++) {
1987 check_internal_node(tb->tb_sb, PATH_H_PBUFFER(tb->tb_path, h),
1988 "BAD BUFFER ON PATH");
1989 if (tb->lnum[h])
1990 check_internal_node(tb->tb_sb, tb->L[h], "BAD L");
1991 if (tb->rnum[h])
1992 check_internal_node(tb->tb_sb, tb->R[h], "BAD R");
1993 }
1da177e4
LT		 1994
1995}
1996
1997#endif
1998
1da177e4
LT		 1999/* Now we have all of the buffers that must be used in balancing of
2000 the tree. We rely on the assumption that schedule() will not occur
2001 while do_balance works. ( Only interrupt handlers are acceptable.)
2002 We balance the tree according to the analysis made before this,
2003 using buffers already obtained. For SMP support it will someday be
2004 necessary to add ordered locking of tb. */
2005
2006/* Some interesting rules of balancing:
2007
2008 we delete a maximum of two nodes per level per balancing: we never
2009 delete R, when we delete two of three nodes L, S, R then we move
2010 them into R.
2011
2012 we only delete L if we are deleting two nodes, if we delete only
2013 one node we delete S
2014
2015 if we shift leaves then we shift as much as we can: this is a
2016 deliberate policy of extremism in node packing which results in
2017 higher average utilization after repeated random balance operations
2018 at the cost of more memory copies and more balancing as a result of
2019 small insertions to full nodes.
2020
2021 if we shift internal nodes we try to evenly balance the node
2022 utilization, with consequent less balancing at the cost of lower
2023 utilization.
2024
2025 one could argue that the policy for directories in leaves should be
2026 that of internal nodes, but we will wait until another day to
2027 evaluate this.... It would be nice to someday measure and prove
2028 these assumptions as to what is optimal....
2029
2030*/
2031
bd4c625c 2032static inline void do_balance_starts(struct tree_balance *tb)
1da177e4 2033{
bd4c625c
LT		 2034 /* use print_cur_tb() to see initial state of struct
2035 tree_balance */
1da177e4 2036
bd4c625c 2037 /* store_print_tb (tb); */
1da177e4 2038
bd4c625c 2039 /* do not delete, just comment it out */
1da177e4
LT		 2040/* print_tb(flag, PATH_LAST_POSITION(tb->tb_path), tb->tb_path->pos_in_item, tb,
2041 "check");*/
bd4c625c 2042 RFALSE(check_before_balancing(tb), "PAP-12340: locked buffers in TB");
1da177e4 2043#ifdef CONFIG_REISERFS_CHECK
bd4c625c 2044 cur_tb = tb;
1da177e4
LT		 2045#endif
2046}
2047
bd4c625c 2048static inline void do_balance_completed(struct tree_balance *tb)
1da177e4 2049{
bd4c625c 2050
1da177e4 2051#ifdef CONFIG_REISERFS_CHECK
bd4c625c
LT		 2052 check_leaf_level(tb);
2053 check_internal_levels(tb);
2054 cur_tb = NULL;
1da177e4
LT		 2055#endif
2056
bd4c625c
LT		 2057 /* reiserfs_free_block is no longer schedule safe. So, we need to
2058 ** put the buffers we want freed on the thrown list during do_balance,
2059 ** and then free them now
2060 */
1da177e4 2061
bd4c625c 2062 REISERFS_SB(tb->tb_sb)->s_do_balance++;
1da177e4 2063
bd4c625c
LT		 2064 /* release all nodes hold to perform the balancing */
2065 unfix_nodes(tb);
1da177e4 2066
bd4c625c 2067 free_thrown(tb);
1da177e4
LT		 2068}
2069
bd4c625c
LT		 2070void do_balance(struct tree_balance *tb, /* tree_balance structure */
2071 struct item_head *ih, /* item header of inserted item */
2072 const char *body, /* body of inserted item or bytes to paste */
2073 int flag)
2074{ /* i - insert, d - delete
2075 c - cut, p - paste
2076
2077 Cut means delete part of an item
2078 (includes removing an entry from a
2079 directory).
2080
2081 Delete means delete whole item.
2082
2083 Insert means add a new item into the
2084 tree.
2085
2086 Paste means to append to the end of an
2087 existing file or to insert a directory
2088 entry. */
2089 int child_pos, /* position of a child node in its parent */
2090 h; /* level of the tree being processed */
2091 struct item_head insert_key[2]; /* in our processing of one level
2092 we sometimes determine what
2093 must be inserted into the next
2094 higher level. This insertion
2095 consists of a key or two keys
2096 and their corresponding
2097 pointers */
2098 struct buffer_head *insert_ptr[2]; /* inserted node-ptrs for the next
2099 level */
2100
2101 tb->tb_mode = flag;
2102 tb->need_balance_dirty = 0;
2103
2104 if (FILESYSTEM_CHANGED_TB(tb)) {
2105 reiserfs_panic(tb->tb_sb,
2106 "clm-6000: do_balance, fs generation has changed\n");
2107 }
2108 /* if we have no real work to do */
2109 if (!tb->insert_size[0]) {
2110 reiserfs_warning(tb->tb_sb,
2111 "PAP-12350: do_balance: insert_size == 0, mode == %c",
2112 flag);
2113 unfix_nodes(tb);
2114 return;
2115 }
1da177e4 2116
bd4c625c
LT		 2117 atomic_inc(&(fs_generation(tb->tb_sb)));
2118 do_balance_starts(tb);
1da177e4 2119
1da177e4
LT		 2120 /* balance leaf returns 0 except if combining L R and S into
2121 one node. see balance_internal() for explanation of this
bd4c625c
LT		 2122 line of code. */
2123 child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
2124 balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
1da177e4
LT		 2125
2126#ifdef CONFIG_REISERFS_CHECK
bd4c625c 2127 check_after_balance_leaf(tb);
1da177e4
LT		 2128#endif
2129
bd4c625c
LT		 2130 /* Balance internal level of the tree. */
2131 for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
2132 child_pos =
2133 balance_internal(tb, h, child_pos, insert_key, insert_ptr);
1da177e4 2134
bd4c625c 2135 do_balance_completed(tb);
1da177e4
LT		 2136
2137}
Empty description
This page took 0.413289 seconds and 4 git commands to generate.