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