1 /* 1
2 * Copyright 2000 by Hans Reiser, licensing go
3 */
4
5 #include <linux/uaccess.h>
6 #include <linux/string.h>
7 #include <linux/time.h>
8 #include "reiserfs.h"
9 #include <linux/buffer_head.h>
10
11 /*
12 * copy copy_count entries from source directo
13 * (creating new item if needed)
14 */
15 static void leaf_copy_dir_entries(struct buffe
16 struct buffe
17 int item_num
18 {
19 struct buffer_head *dest = dest_bi->bi
20 /*
21 * either the number of target item, o
22 * new item, the number of the item we
23 */
24 int item_num_in_dest;
25
26 struct item_head *ih;
27 struct reiserfs_de_head *deh;
28 int copy_records_len; /* length of a
29 char *records;
30
31 ih = item_head(source, item_num);
32
33 RFALSE(!is_direntry_le_ih(ih), "vs-100
34
35 /*
36 * length of all record to be copied a
37 * the last of them
38 */
39 deh = B_I_DEH(source, ih);
40 if (copy_count) {
41 copy_records_len = (from ? deh
42 ih_item_le
43 deh_location(&deh[from + c
44 records =
45 source->b_data + ih_locati
46 deh_location(&deh[from + c
47 } else {
48 copy_records_len = 0;
49 records = NULL;
50 }
51
52 /* when copy last to first, dest buffe
53 item_num_in_dest =
54 (last_first ==
55 LAST_TO_FIRST) ? ((B_NR_ITEMS(des
56
57
58 /*
59 * if there are no items in dest or th
60 * dest is not item of the same direct
61 */
62 if ((item_num_in_dest == -1) ||
63 (last_first == FIRST_TO_LAST && le
64 (last_first == LAST_TO_FIRST
65 && comp_short_le_keys /*COMP_SHOR
66
67
68 {
69 /* create new item in dest */
70 struct item_head new_ih;
71
72 /* form item header */
73 memcpy(&new_ih.ih_key, &ih->ih
74 put_ih_version(&new_ih, KEY_FO
75 /* calculate item len */
76 put_ih_item_len(&new_ih,
77 DEH_SIZE * cop
78 put_ih_entry_count(&new_ih, 0)
79
80 if (last_first == LAST_TO_FIRS
81 /* form key by the fol
82 if (from < ih_entry_co
83 set_le_ih_k_of
84
85 } else {
86 /*
87 * no entries
88 * item in thi
89 */
90 set_le_ih_k_of
91 /*
92 * this item i
93 * want I_IS_D
94 * for it, so
95 */
96 }
97 set_le_key_k_type(KEY_
98 TYPE
99 }
100
101 /* insert item into dest buffe
102 leaf_insert_into_buf(dest_bi,
103 (last_fir
104 LAST_TO_
105 &new_ih,
106 } else {
107 /* prepare space for entries *
108 leaf_paste_in_buffer(dest_bi,
109 (last_fir
110 FIRST_TO
111
112 DEH_SIZE
113 records,
114 }
115
116 item_num_in_dest =
117 (last_first == FIRST_TO_LAST) ? (B
118
119 leaf_paste_entries(dest_bi, item_num_i
120 (last_first ==
121 FIRST_TO_LAST) ? i
122
123 : 0, copy_count, de
124 DEH_SIZE * copy_cou
125 }
126
127 /*
128 * Copy the first (if last_first == FIRST_TO_L
129 * (last_first == LAST_TO_FIRST) item or part
130 * (see the return 0 below) from SOURCE to the
131 * or beginning (!last_first) of the DEST
132 */
133 /* returns 1 if anything was copied, else 0 */
134 static int leaf_copy_boundary_item(struct buff
135 struct buff
136 int bytes_o
137 {
138 struct buffer_head *dest = dest_bi->bi
139 /* number of items in the source and d
140 int dest_nr_item, src_nr_item;
141 struct item_head *ih;
142 struct item_head *dih;
143
144 dest_nr_item = B_NR_ITEMS(dest);
145
146 /*
147 * if ( DEST is empty or first item of
148 * DEST are the items of different obj
149 * then there is no need to treat this
150 * other items that we copy, so we ret
151 */
152 if (last_first == FIRST_TO_LAST) {
153 ih = item_head(src, 0);
154 dih = item_head(dest, dest_nr_
155
156 /* there is nothing to merge *
157 if (!dest_nr_item
158 || (!op_is_left_mergeable(
159 return 0;
160
161 RFALSE(!ih_item_len(ih),
162 "vs-10010: item can not
163
164 if (is_direntry_le_ih(ih)) {
165 if (bytes_or_entries =
166 /* copy all en
167 bytes_or_entri
168 leaf_copy_dir_entries(
169
170 return 1;
171 }
172
173 /*
174 * copy part of the body of th
175 * to the end of the body of t
176 * part defined by 'bytes_or_e
177 * == -1 copy whole body; don'
178 */
179 if (bytes_or_entries == -1)
180 bytes_or_entries = ih_
181
182 #ifdef CONFIG_REISERFS_CHECK
183 else {
184 if (bytes_or_entries =
185 && is_indirect_le_
186 if (get_ih_fre
187 reiser
188
189
190
191
192 }
193 #endif
194
195 /*
196 * merge first item (or its pa
197 * item of dest buffer. Both a
198 */
199 leaf_paste_in_buffer(dest_bi,
200 dest_nr_i
201 bytes_or_
202
203 if (is_indirect_le_ih(dih)) {
204 RFALSE(get_ih_free_spa
205 "vs-10030: merg
206 ih);
207 if (bytes_or_entries =
208 set_ih_free_sp
209 }
210
211 return 1;
212 }
213
214 /* copy boundary item to right (last_f
215
216 /*
217 * (DEST is empty or last item of SOUR
218 * are the items of different object o
219 */
220 src_nr_item = B_NR_ITEMS(src);
221 ih = item_head(src, src_nr_item - 1);
222 dih = item_head(dest, 0);
223
224 if (!dest_nr_item || !op_is_left_merge
225 return 0;
226
227 if (is_direntry_le_ih(ih)) {
228 /*
229 * bytes_or_entries = entries
230 * item body of SOURCE
231 */
232 if (bytes_or_entries == -1)
233 bytes_or_entries = ih_
234
235 leaf_copy_dir_entries(dest_bi,
236 src_nr_i
237 ih_entry
238 bytes_or
239 return 1;
240 }
241
242 /*
243 * copy part of the body of the last i
244 * begin of the body of the first item
245 * by 'bytes_or_entries'; if byte_or_e
246 * change first item key of the DEST;
247 */
248
249 RFALSE(is_indirect_le_ih(ih) && get_ih
250 "vs-10040: merge to right: last
251 ih);
252
253 if (bytes_or_entries == -1) {
254 /* bytes_or_entries = length o
255 bytes_or_entries = ih_item_len
256
257 RFALSE(le_ih_k_offset(dih) !=
258 le_ih_k_offset(ih) + op
259 "vs-10050: items %h and
260
261 /* change first item key of th
262 set_le_ih_k_offset(dih, le_ih_
263
264 /* item becomes non-mergeable
265 /* or mergeable if left item w
266 set_le_ih_k_type(dih, le_ih_k_
267 } else {
268 /* merge to right only part of
269 RFALSE(ih_item_len(ih) <= byte
270 "vs-10060: no so much b
271 (unsigned long)ih_item_
272 (unsigned long)bytes_or
273
274 /* change first item key of th
275 if (is_direct_le_ih(dih)) {
276 RFALSE(le_ih_k_offset(
277 (unsigned long)
278 "vs-10070: dih
279 bytes_or_entrie
280 set_le_ih_k_offset(dih
281 le_
282 byt
283 } else {
284 RFALSE(le_ih_k_offset(
285 (bytes_or_entri
286 "vs-10080: dih
287 dih,
288 (bytes_or_entri
289 set_le_ih_k_offset(dih
290 le_
291 ((b
292 de
293 }
294 }
295
296 leaf_paste_in_buffer(dest_bi, 0, 0, by
297 ih_item_body(src,
298 ih) + i
299 0);
300 return 1;
301 }
302
303 /*
304 * copy cpy_mun items from buffer src to buffe
305 * last_first == FIRST_TO_LAST means, that we
306 * from first-th i
307 * last_first == LAST_TO_FIRST means, that we
308 * from first-th i
309 */
310 static void leaf_copy_items_entirely(struct bu
311 struct bu
312 int first
313 {
314 struct buffer_head *dest;
315 int nr, free_space;
316 int dest_before;
317 int last_loc, last_inserted_loc, locat
318 int i, j;
319 struct block_head *blkh;
320 struct item_head *ih;
321
322 RFALSE(last_first != LAST_TO_FIRST &&
323 "vs-10090: bad last_first param
324 RFALSE(B_NR_ITEMS(src) - first < cpy_n
325 "vs-10100: too few items in sou
326 B_NR_ITEMS(src), cpy_num, first
327 RFALSE(cpy_num < 0, "vs-10110: can not
328 RFALSE(!dest_bi, "vs-10120: can not co
329
330 dest = dest_bi->bi_bh;
331
332 RFALSE(!dest, "vs-10130: can not copy
333
334 if (cpy_num == 0)
335 return;
336
337 blkh = B_BLK_HEAD(dest);
338 nr = blkh_nr_item(blkh);
339 free_space = blkh_free_space(blkh);
340
341 /*
342 * we will insert items before 0-th or
343 * It depends of last_first parameter
344 */
345 dest_before = (last_first == LAST_TO_F
346
347 /* location of head of first new item
348 ih = item_head(dest, dest_before);
349
350 RFALSE(blkh_free_space(blkh) < cpy_num
351 "vs-10140: not enough free spac
352 B_FREE_SPACE(dest), cpy_num * I
353
354 /* prepare space for headers */
355 memmove(ih + cpy_num, ih, (nr - dest_b
356
357 /* copy item headers */
358 memcpy(ih, item_head(src, first), cpy_
359
360 free_space -= (IH_SIZE * cpy_num);
361 set_blkh_free_space(blkh, free_space);
362
363 /* location of unmovable item */
364 j = location = (dest_before == 0) ? de
365 for (i = dest_before; i < nr + cpy_num
366 location -= ih_item_len(ih + i
367 put_ih_location(ih + i - dest_
368 }
369
370 /* prepare space for items */
371 last_loc = ih_location(&ih[nr + cpy_nu
372 last_inserted_loc = ih_location(&ih[cp
373
374 /* check free space */
375 RFALSE(free_space < j - last_inserted_
376 "vs-10150: not enough free spac
377 free_space, j - last_inserted_l
378
379 memmove(dest->b_data + last_loc,
380 dest->b_data + last_loc + j -
381 last_inserted_loc - last_loc);
382
383 /* copy items */
384 memcpy(dest->b_data + last_inserted_lo
385 item_body(src, (first + cpy_num
386 j - last_inserted_loc);
387
388 /* sizes, item number */
389 set_blkh_nr_item(blkh, nr + cpy_num);
390 set_blkh_free_space(blkh, free_space -
391
392 do_balance_mark_leaf_dirty(dest_bi->tb
393
394 if (dest_bi->bi_parent) {
395 struct disk_child *t_dc;
396 t_dc = B_N_CHILD(dest_bi->bi_p
397 RFALSE(dc_block_number(t_dc) !
398 "vs-10160: block number
399 (long unsigned)dest->b_
400 (long unsigned)dc_block
401 put_dc_size(t_dc,
402 dc_size(t_dc) + (j
403 I
404
405 do_balance_mark_internal_dirty
406
407 }
408 }
409
410 /*
411 * This function splits the (liquid) item into
412 * shifting part of an item into another node.
413 */
414 static void leaf_item_bottle(struct buffer_inf
415 struct buffer_hea
416 int item_num, int
417 {
418 struct buffer_head *dest = dest_bi->bi
419 struct item_head *ih;
420
421 RFALSE(cpy_bytes == -1,
422 "vs-10170: bytes == - 1 means:
423
424 if (last_first == FIRST_TO_LAST) {
425 /*
426 * if ( if item in position it
427 * is directory item )
428 */
429 ih = item_head(src, item_num);
430 if (is_direntry_le_ih(ih))
431 leaf_copy_dir_entries(
432
433 else {
434 struct item_head n_ih;
435
436 /*
437 * copy part of the bo
438 * of SOURCE to the en
439 * 'cpy_bytes'; create
440 * item_header (????);
441 */
442 memcpy(&n_ih, ih, IH_S
443 put_ih_item_len(&n_ih,
444 if (is_indirect_le_ih(
445 RFALSE(cpy_byt
446 && get_
447 "vs-101
448 (long u
449 set_ih_free_sp
450 }
451
452 RFALSE(op_is_left_merg
453 "vs-10190: bad
454 n_ih.ih_version = ih->
455 leaf_insert_into_buf(d
456 i
457 }
458 } else {
459 /*
460 * if ( if item in position it
461 * SOURCE is directory item )
462 */
463 ih = item_head(src, item_num);
464 if (is_direntry_le_ih(ih))
465 leaf_copy_dir_entries(
466
467
468
469 else {
470 struct item_head n_ih;
471
472 /*
473 * copy part of the bo
474 * of SOURCE to the be
475 * 'cpy_bytes'; create
476 * n_ih = new item_hea
477 */
478 memcpy(&n_ih.ih_key, &
479
480 /* Endian safe, both l
481 n_ih.ih_version = ih->
482
483 if (is_direct_le_ih(ih
484 set_le_ih_k_of
485
486
487 set_le_ih_k_ty
488 set_ih_free_sp
489 } else {
490 /* indirect it
491 RFALSE(!cpy_by
492 "vs-102
493 set_le_ih_k_of
494
495
496
497
498 set_le_ih_k_ty
499 set_ih_free_sp
500 }
501
502 /* set item length */
503 put_ih_item_len(&n_ih,
504
505 /* Endian safe, both l
506 n_ih.ih_version = ih->
507
508 leaf_insert_into_buf(d
509 i
510
511 }
512 }
513 }
514
515 /*
516 * If cpy_bytes equals minus one than copy cpy
517 * to DEST. If cpy_bytes not equal to minus o
518 * items from SOURCE to DEST. From last item
519 * item and cpy_num directory entries for dire
520 */
521 static int leaf_copy_items(struct buffer_info
522 int last_first, int
523 {
524 struct buffer_head *dest;
525 int pos, i, src_nr_item, bytes;
526
527 dest = dest_bi->bi_bh;
528 RFALSE(!dest || !src, "vs-10210: !dest
529 RFALSE(last_first != FIRST_TO_LAST &&
530 "vs-10220:last_first != FIRST_T
531 RFALSE(B_NR_ITEMS(src) < cpy_num,
532 "vs-10230: No enough items: %d,
533 cpy_num);
534 RFALSE(cpy_num < 0, "vs-10240: cpy_num
535
536 if (cpy_num == 0)
537 return 0;
538
539 if (last_first == FIRST_TO_LAST) {
540 /* copy items to left */
541 pos = 0;
542 if (cpy_num == 1)
543 bytes = cpy_bytes;
544 else
545 bytes = -1;
546
547 /*
548 * copy the first item or it p
549 * the DEST (i = leaf_copy_bou
550 */
551 i = leaf_copy_boundary_item(de
552 cpy_num -= i;
553 if (cpy_num == 0)
554 return i;
555 pos += i;
556 if (cpy_bytes == -1)
557 /*
558 * copy first cpy_num
559 * 'pos' of SOURCE to
560 */
561 leaf_copy_items_entire
562
563 else {
564 /*
565 * copy first cpy_num-
566 * 'pos-1' of the SOUR
567 */
568 leaf_copy_items_entire
569
570
571 /*
572 * copy part of the it
573 * cpy_num+pos-1 to th
574 */
575 leaf_item_bottle(dest_
576 cpy_n
577 }
578 } else {
579 /* copy items to right */
580 src_nr_item = B_NR_ITEMS(src);
581 if (cpy_num == 1)
582 bytes = cpy_bytes;
583 else
584 bytes = -1;
585
586 /*
587 * copy the last item or it pa
588 * begin of the DEST
589 * (i = leaf_copy_boundary_ite
590 */
591 i = leaf_copy_boundary_item(de
592
593 cpy_num -= i;
594 if (cpy_num == 0)
595 return i;
596
597 pos = src_nr_item - cpy_num -
598 if (cpy_bytes == -1) {
599 /*
600 * starting from posit
601 * items of SOURCE to
602 */
603 leaf_copy_items_entire
604
605 } else {
606 /*
607 * copy last cpy_num-1
608 * 'pos+1' of the SOUR
609 */
610 leaf_copy_items_entire
611
612
613 /*
614 * copy part of the it
615 * the begin of the DE
616 */
617 leaf_item_bottle(dest_
618 cpy_b
619 }
620 }
621 return i;
622 }
623
624 /*
625 * there are types of coping: from S[0] to L[0
626 * from R[0] to L[0]. for each of these we hav
627 * positions of destination and source buffers
628 */
629 static void leaf_define_dest_src_infos(int shi
630 struct
631 struct
632 int *fi
633 struct
634 {
635 memset(dest_bi, 0, sizeof(struct buffe
636 memset(src_bi, 0, sizeof(struct buffer
637
638 /* define dest, src, dest parent, dest
639 switch (shift_mode) {
640 case LEAF_FROM_S_TO_L: /* it is used
641 src_bi->tb = tb;
642 src_bi->bi_bh = PATH_PLAST_BUF
643 src_bi->bi_parent = PATH_H_PPA
644
645 /* src->b_item_order */
646 src_bi->bi_position = PATH_H_B
647 dest_bi->tb = tb;
648 dest_bi->bi_bh = tb->L[0];
649 dest_bi->bi_parent = tb->FL[0]
650 dest_bi->bi_position = get_lef
651 *first_last = FIRST_TO_LAST;
652 break;
653
654 case LEAF_FROM_S_TO_R: /* it is used
655 src_bi->tb = tb;
656 src_bi->bi_bh = PATH_PLAST_BUF
657 src_bi->bi_parent = PATH_H_PPA
658 src_bi->bi_position = PATH_H_B
659 dest_bi->tb = tb;
660 dest_bi->bi_bh = tb->R[0];
661 dest_bi->bi_parent = tb->FR[0]
662 dest_bi->bi_position = get_rig
663 *first_last = LAST_TO_FIRST;
664 break;
665
666 case LEAF_FROM_R_TO_L: /* it is used
667 src_bi->tb = tb;
668 src_bi->bi_bh = tb->R[0];
669 src_bi->bi_parent = tb->FR[0];
670 src_bi->bi_position = get_righ
671 dest_bi->tb = tb;
672 dest_bi->bi_bh = tb->L[0];
673 dest_bi->bi_parent = tb->FL[0]
674 dest_bi->bi_position = get_lef
675 *first_last = FIRST_TO_LAST;
676 break;
677
678 case LEAF_FROM_L_TO_R: /* it is used
679 src_bi->tb = tb;
680 src_bi->bi_bh = tb->L[0];
681 src_bi->bi_parent = tb->FL[0];
682 src_bi->bi_position = get_left
683 dest_bi->tb = tb;
684 dest_bi->bi_bh = tb->R[0];
685 dest_bi->bi_parent = tb->FR[0]
686 dest_bi->bi_position = get_rig
687 *first_last = LAST_TO_FIRST;
688 break;
689
690 case LEAF_FROM_S_TO_SNEW:
691 src_bi->tb = tb;
692 src_bi->bi_bh = PATH_PLAST_BUF
693 src_bi->bi_parent = PATH_H_PPA
694 src_bi->bi_position = PATH_H_B
695 dest_bi->tb = tb;
696 dest_bi->bi_bh = Snew;
697 dest_bi->bi_parent = NULL;
698 dest_bi->bi_position = 0;
699 *first_last = LAST_TO_FIRST;
700 break;
701
702 default:
703 reiserfs_panic(sb_from_bi(src_
704 "shift type is
705 }
706 RFALSE(!src_bi->bi_bh || !dest_bi->bi_
707 "vs-10260: mode==%d, source (%p
708 shift_mode, src_bi->bi_bh, dest
709 }
710
711 /*
712 * copy mov_num items and mov_bytes of the (mo
713 * neighbor. Delete them from source
714 */
715 int leaf_move_items(int shift_mode, struct tre
716 int mov_bytes, struct buff
717 {
718 int ret_value;
719 struct buffer_info dest_bi, src_bi;
720 int first_last;
721
722 leaf_define_dest_src_infos(shift_mode,
723 &first_last
724
725 ret_value =
726 leaf_copy_items(&dest_bi, src_bi.b
727 mov_bytes);
728
729 leaf_delete_items(&src_bi, first_last,
730 (first_last ==
731 FIRST_TO_LAST) ? 0
732
733
734 return ret_value;
735 }
736
737 /*
738 * Shift shift_num items (and shift_bytes of l
739 * shift_bytes != -1) from S[0] to L[0] and re
740 */
741 int leaf_shift_left(struct tree_balance *tb, i
742 {
743 struct buffer_head *S0 = PATH_PLAST_BU
744 int i;
745
746 /*
747 * move shift_num (and shift_bytes byt
748 * to left neighbor L[0]
749 */
750 i = leaf_move_items(LEAF_FROM_S_TO_L,
751
752 if (shift_num) {
753 /* number of items in S[0] ==
754 if (B_NR_ITEMS(S0) == 0) {
755
756 RFALSE(shift_bytes !=
757 "vs-10270: S0 i
758 shift_bytes);
759 #ifdef CONFIG_REISERFS_CHECK
760 if (tb->tb_mode == M_P
761 print_cur_tb("
762 reiserfs_panic
763
764
765 }
766 #endif
767
768 if (PATH_H_POSITION(tb
769 replace_key(tb
770 PA
771
772 } else {
773 /* replace lkey in CFL
774 replace_key(tb, tb->CF
775
776 RFALSE((shift_bytes !=
777 !(is_direntry_
778 && !ih_entry
779 (!op_is_left_me
780 (leaf_key(S0,
781 "vs-10280: item
782 }
783 }
784
785 return i;
786 }
787
788 /* CLEANING STOPPED HERE */
789
790 /*
791 * Shift shift_num (shift_bytes) items from S[
792 * and replace the delimiting key
793 */
794 int leaf_shift_right(struct tree_balance *tb,
795 {
796 int ret_value;
797
798 /*
799 * move shift_num (and shift_bytes) it
800 * right neighbor R[0]
801 */
802 ret_value =
803 leaf_move_items(LEAF_FROM_S_TO_R,
804
805 /* replace rkey in CFR[0] by the 0-th
806 if (shift_num) {
807 replace_key(tb, tb->CFR[0], tb
808
809 }
810
811 return ret_value;
812 }
813
814 static void leaf_delete_items_entirely(struct
815 int fir
816 /*
817 * If del_bytes == -1, starting from position
818 * items in whole in buffer CUR.
819 * If not.
820 * If last_first == 0. Starting from positio
821 * items in whole. Delete part of body of th
822 * del_bytes. Don't delete first item header
823 * If last_first == 1. Starting from positio
824 * items in whole. Delete part of body of th
825 * del_bytes. Don't delete last item header.
826 */
827 void leaf_delete_items(struct buffer_info *cur
828 int first, int del_num,
829 {
830 struct buffer_head *bh;
831 int item_amount = B_NR_ITEMS(bh = cur_
832
833 RFALSE(!bh, "10155: bh is not defined"
834 RFALSE(del_num < 0, "10160: del_num ca
835 del_num);
836 RFALSE(first < 0
837 || first + del_num > item_amoun
838 "10165: invalid number of first
839 "no so much items (%d) to delet
840 first + del_num, item_amount);
841
842 if (del_num == 0)
843 return;
844
845 if (first == 0 && del_num == item_amou
846 make_empty_node(cur_bi);
847 do_balance_mark_leaf_dirty(cur
848 return;
849 }
850
851 if (del_bytes == -1)
852 /* delete del_num items beginn
853 leaf_delete_items_entirely(cur
854 else {
855 if (last_first == FIRST_TO_LAS
856 /*
857 * delete del_num-1 it
858 * item in position fi
859 */
860 leaf_delete_items_enti
861
862 /*
863 * delete the part of
864 * do not delete item
865 */
866 leaf_cut_from_buffer(c
867 } else {
868 struct item_head *ih;
869 int len;
870
871 /*
872 * delete del_num-1 it
873 * item in position fi
874 */
875 leaf_delete_items_enti
876
877
878 ih = item_head(bh, B_N
879 if (is_direntry_le_ih(
880 /* the last it
881 /*
882 * len = numbe
883 * in this ite
884 */
885 len = ih_entry
886 else
887 /* len = body
888 len = ih_item_
889
890 /*
891 * delete the part of
892 * do not delete item
893 */
894 leaf_cut_from_buffer(c
895 l
896 }
897 }
898 }
899
900 /* insert item into the leaf node in position
901 void leaf_insert_into_buf(struct buffer_info *
902 struct item_head * c
903 const char * const i
904 int zeros_number)
905 {
906 struct buffer_head *bh = bi->bi_bh;
907 int nr, free_space;
908 struct block_head *blkh;
909 struct item_head *ih;
910 int i;
911 int last_loc, unmoved_loc;
912 char *to;
913
914 blkh = B_BLK_HEAD(bh);
915 nr = blkh_nr_item(blkh);
916 free_space = blkh_free_space(blkh);
917
918 /* check free space */
919 RFALSE(free_space < ih_item_len(insert
920 "vs-10170: not enough free spac
921 bh, inserted_item_ih);
922 RFALSE(zeros_number > ih_item_len(inse
923 "vs-10172: zero number == %d, i
924 zeros_number, ih_item_len(inser
925
926 /* get item new item must be inserted
927 ih = item_head(bh, before);
928
929 /* prepare space for the body of new i
930 last_loc = nr ? ih_location(&ih[nr - b
931 unmoved_loc = before ? ih_location(ih
932
933 memmove(bh->b_data + last_loc - ih_ite
934 bh->b_data + last_loc, unmoved
935
936 to = bh->b_data + unmoved_loc - ih_ite
937 memset(to, 0, zeros_number);
938 to += zeros_number;
939
940 /* copy body to prepared space */
941 if (inserted_item_body)
942 memmove(to, inserted_item_body
943 ih_item_len(inserted_i
944 else
945 memset(to, '\0', ih_item_len(i
946
947 /* insert item header */
948 memmove(ih + 1, ih, IH_SIZE * (nr - be
949 memmove(ih, inserted_item_ih, IH_SIZE)
950
951 /* change locations */
952 for (i = before; i < nr + 1; i++) {
953 unmoved_loc -= ih_item_len(&ih
954 put_ih_location(&ih[i - before
955 }
956
957 /* sizes, free space, item number */
958 set_blkh_nr_item(blkh, blkh_nr_item(bl
959 set_blkh_free_space(blkh,
960 free_space - (IH_S
961 ih_i
962 do_balance_mark_leaf_dirty(bi->tb, bh,
963
964 if (bi->bi_parent) {
965 struct disk_child *t_dc;
966 t_dc = B_N_CHILD(bi->bi_parent
967 put_dc_size(t_dc,
968 dc_size(t_dc) + (I
969 i
970 do_balance_mark_internal_dirty
971 }
972 }
973
974 /*
975 * paste paste_size bytes to affected_item_num
976 * When item is a directory, this only prepare
977 */
978 void leaf_paste_in_buffer(struct buffer_info *
979 int pos_in_item, int
980 const char *body, in
981 {
982 struct buffer_head *bh = bi->bi_bh;
983 int nr, free_space;
984 struct block_head *blkh;
985 struct item_head *ih;
986 int i;
987 int last_loc, unmoved_loc;
988
989 blkh = B_BLK_HEAD(bh);
990 nr = blkh_nr_item(blkh);
991 free_space = blkh_free_space(blkh);
992
993 /* check free space */
994 RFALSE(free_space < paste_size,
995 "vs-10175: not enough free spac
996 paste_size, free_space);
997
998 #ifdef CONFIG_REISERFS_CHECK
999 if (zeros_number > paste_size) {
1000 struct super_block *sb = NULL
1001 if (bi && bi->tb)
1002 sb = bi->tb->tb_sb;
1003 print_cur_tb("10177");
1004 reiserfs_panic(sb, "vs-10177"
1005 "zeros_number
1006 zeros_number,
1007 }
1008 #endif /* CONFIG_REI
1009
1010 /* item to be appended */
1011 ih = item_head(bh, affected_item_num)
1012
1013 last_loc = ih_location(&ih[nr - affec
1014 unmoved_loc = affected_item_num ? ih_
1015
1016 /* prepare space */
1017 memmove(bh->b_data + last_loc - paste
1018 unmoved_loc - last_loc);
1019
1020 /* change locations */
1021 for (i = affected_item_num; i < nr; i
1022 put_ih_location(&ih[i - affec
1023 ih_location(&
1024 paste_size);
1025
1026 if (body) {
1027 if (!is_direntry_le_ih(ih)) {
1028 if (!pos_in_item) {
1029 /* shift data
1030 memmove(bh->b
1031 paste
1032 bh->b
1033 ih_it
1034 /* paste data
1035 memset(bh->b_
1036 zeros_
1037 memcpy(bh->b_
1038 zeros_
1039 paste_
1040 } else {
1041 memset(bh->b_
1042 zeros_
1043 memcpy(bh->b_
1044 zeros_
1045 paste_
1046 }
1047 }
1048 } else
1049 memset(bh->b_data + unmoved_l
1050
1051 put_ih_item_len(ih, ih_item_len(ih) +
1052
1053 /* change free space */
1054 set_blkh_free_space(blkh, free_space
1055
1056 do_balance_mark_leaf_dirty(bi->tb, bh
1057
1058 if (bi->bi_parent) {
1059 struct disk_child *t_dc =
1060 B_N_CHILD(bi->bi_parent,
1061 put_dc_size(t_dc, dc_size(t_d
1062 do_balance_mark_internal_dirt
1063 }
1064 }
1065
1066 /*
1067 * cuts DEL_COUNT entries beginning from FROM
1068 * does not have free space, so it moves DEHs
1069 * necessary. Return value is size of removed
1070 * in bytes.
1071 */
1072 static int leaf_cut_entries(struct buffer_hea
1073 struct item_head
1074 {
1075 char *item;
1076 struct reiserfs_de_head *deh;
1077 int prev_record_offset; /* offset of
1078 char *prev_record; /* */
1079 int cut_records_len; /* length of
1080 int i;
1081
1082 /*
1083 * make sure that item is directory a
1084 * remove
1085 */
1086 RFALSE(!is_direntry_le_ih(ih), "10180
1087 RFALSE(ih_entry_count(ih) < from + de
1088 "10185: item contains not enou
1089 ih_entry_count(ih), from, del_
1090
1091 if (del_count == 0)
1092 return 0;
1093
1094 /* first byte of item */
1095 item = bh->b_data + ih_location(ih);
1096
1097 /* entry head array */
1098 deh = B_I_DEH(bh, ih);
1099
1100 /*
1101 * first byte of remaining entries, t
1102 * (prev_record) and length of all re
1103 */
1104 prev_record_offset =
1105 (from ? deh_location(&deh[from -
1106 cut_records_len = prev_record_offset
1107 deh_location(&deh[from + del_coun
1108 prev_record = item + prev_record_offs
1109
1110 /* adjust locations of remaining entr
1111 for (i = ih_entry_count(ih) - 1; i >
1112 put_deh_location(&deh[i],
1113 deh_location
1114 (DEH_SIZE *
1115
1116 for (i = 0; i < from; i++)
1117 put_deh_location(&deh[i],
1118 deh_location
1119
1120
1121 put_ih_entry_count(ih, ih_entry_count
1122
1123 /* shift entry head array and entries
1124 memmove((char *)(deh + from),
1125 deh + from + del_count,
1126 prev_record - cut_records_len
1127
1128
1129 /* shift records, those are BEFORE re
1130 memmove(prev_record - cut_records_len
1131 prev_record, item + ih_item_l
1132
1133 return DEH_SIZE * del_count + cut_rec
1134 }
1135
1136 /*
1137 * when cut item is part of regular file
1138 * pos_in_item - first byte that must be
1139 * cut_size - number of bytes to be cut
1140 *
1141 * when cut item is part of directory
1142 * pos_in_item - number of first deleted
1143 * cut_size - count of deleted entries
1144 */
1145 void leaf_cut_from_buffer(struct buffer_info
1146 int pos_in_item, in
1147 {
1148 int nr;
1149 struct buffer_head *bh = bi->bi_bh;
1150 struct block_head *blkh;
1151 struct item_head *ih;
1152 int last_loc, unmoved_loc;
1153 int i;
1154
1155 blkh = B_BLK_HEAD(bh);
1156 nr = blkh_nr_item(blkh);
1157
1158 /* item head of truncated item */
1159 ih = item_head(bh, cut_item_num);
1160
1161 if (is_direntry_le_ih(ih)) {
1162 /* first cut entry () */
1163 cut_size = leaf_cut_entries(b
1164 if (pos_in_item == 0) {
1165 /* change key */
1166 RFALSE(cut_item_num,
1167 "when 0-th enr
1168 cut_item_num);
1169 /* change item key by
1170 set_le_ih_k_offset(ih
1171 }
1172 } else {
1173 /* item is direct or indirect
1174 RFALSE(is_statdata_le_ih(ih),
1175 RFALSE(pos_in_item && pos_in_
1176 "10200: invalid offset
1177 (long unsigned)pos_in_
1178 (long unsigned)ih_item
1179
1180 /* shift item body to left if
1181 if (pos_in_item == 0) {
1182 memmove(bh->b_data +
1183 bh->b_data +
1184 ih_item_len(i
1185
1186 /* change key of item
1187 if (is_direct_le_ih(i
1188 set_le_ih_k_o
1189
1190
1191 else {
1192 set_le_ih_k_o
1193
1194
1195
1196 RFALSE(ih_ite
1197 && get
1198 "10205
1199 }
1200 }
1201 }
1202
1203 /* location of the last item */
1204 last_loc = ih_location(&ih[nr - cut_i
1205
1206 /* location of the item, which is rem
1207 unmoved_loc = cut_item_num ? ih_locat
1208
1209 /* shift */
1210 memmove(bh->b_data + last_loc + cut_s
1211 unmoved_loc - last_loc - cut_
1212
1213 /* change item length */
1214 put_ih_item_len(ih, ih_item_len(ih) -
1215
1216 if (is_indirect_le_ih(ih)) {
1217 if (pos_in_item)
1218 set_ih_free_space(ih,
1219 }
1220
1221 /* change locations */
1222 for (i = cut_item_num; i < nr; i++)
1223 put_ih_location(&ih[i - cut_i
1224 ih_location(&
1225
1226 /* size, free space */
1227 set_blkh_free_space(blkh, blkh_free_s
1228
1229 do_balance_mark_leaf_dirty(bi->tb, bh
1230
1231 if (bi->bi_parent) {
1232 struct disk_child *t_dc;
1233 t_dc = B_N_CHILD(bi->bi_paren
1234 put_dc_size(t_dc, dc_size(t_d
1235 do_balance_mark_internal_dirt
1236 }
1237 }
1238
1239 /* delete del_num items from buffer starting
1240 static void leaf_delete_items_entirely(struct
1241 int fi
1242 {
1243 struct buffer_head *bh = bi->bi_bh;
1244 int nr;
1245 int i, j;
1246 int last_loc, last_removed_loc;
1247 struct block_head *blkh;
1248 struct item_head *ih;
1249
1250 RFALSE(bh == NULL, "10210: buffer is
1251 RFALSE(del_num < 0, "10215: del_num l
1252
1253 if (del_num == 0)
1254 return;
1255
1256 blkh = B_BLK_HEAD(bh);
1257 nr = blkh_nr_item(blkh);
1258
1259 RFALSE(first < 0 || first + del_num >
1260 "10220: first=%d, number=%d, t
1261 nr);
1262
1263 if (first == 0 && del_num == nr) {
1264 /* this does not work */
1265 make_empty_node(bi);
1266
1267 do_balance_mark_leaf_dirty(bi
1268 return;
1269 }
1270
1271 ih = item_head(bh, first);
1272
1273 /* location of unmovable item */
1274 j = (first == 0) ? bh->b_size : ih_lo
1275
1276 /* delete items */
1277 last_loc = ih_location(&ih[nr - 1 - f
1278 last_removed_loc = ih_location(&ih[de
1279
1280 memmove(bh->b_data + last_loc + j - l
1281 bh->b_data + last_loc, last_r
1282
1283 /* delete item headers */
1284 memmove(ih, ih + del_num, (nr - first
1285
1286 /* change item location */
1287 for (i = first; i < nr - del_num; i++
1288 put_ih_location(&ih[i - first
1289 ih_location(&
1290
1291
1292 /* sizes, item number */
1293 set_blkh_nr_item(blkh, blkh_nr_item(b
1294 set_blkh_free_space(blkh,
1295 blkh_free_space(b
1296
1297
1298 do_balance_mark_leaf_dirty(bi->tb, bh
1299
1300 if (bi->bi_parent) {
1301 struct disk_child *t_dc =
1302 B_N_CHILD(bi->bi_parent,
1303 put_dc_size(t_dc,
1304 dc_size(t_dc) - (
1305
1306 do_balance_mark_internal_dirt
1307 }
1308 }
1309
1310 /*
1311 * paste new_entry_count entries (new_dehs, r
1312 * before to item_num-th item
1313 */
1314 void leaf_paste_entries(struct buffer_info *b
1315 int item_num,
1316 int before,
1317 int new_entry_count,
1318 struct reiserfs_de_he
1319 const char *records,
1320 {
1321 struct item_head *ih;
1322 char *item;
1323 struct reiserfs_de_head *deh;
1324 char *insert_point;
1325 int i;
1326 struct buffer_head *bh = bi->bi_bh;
1327
1328 if (new_entry_count == 0)
1329 return;
1330
1331 ih = item_head(bh, item_num);
1332
1333 /*
1334 * make sure, that item is directory,
1335 * records in it
1336 */
1337 RFALSE(!is_direntry_le_ih(ih), "10225
1338 RFALSE(ih_entry_count(ih) < before,
1339 "10230: there are no entry we
1340 ih_entry_count(ih), before);
1341
1342 /* first byte of dest item */
1343 item = bh->b_data + ih_location(ih);
1344
1345 /* entry head array */
1346 deh = B_I_DEH(bh, ih);
1347
1348 /* new records will be pasted at this
1349 insert_point =
1350 item +
1351 (before ? deh_location(&deh[befor
1352 : (ih_item_len(ih) - paste_size)
1353
1354 /* adjust locations of records that w
1355 for (i = ih_entry_count(ih) - 1; i >=
1356 put_deh_location(&deh[i],
1357 deh_location
1358 (DEH_SIZE *
1359
1360 /* adjust locations of records that w
1361 for (i = 0; i < before; i++)
1362 put_deh_location(&deh[i],
1363 deh_location
1364
1365 put_ih_entry_count(ih, ih_entry_count
1366
1367 /* prepare space for pasted records *
1368 memmove(insert_point + paste_size, in
1369 item + (ih_item_len(ih) - pas
1370
1371 /* copy new records */
1372 memcpy(insert_point + DEH_SIZE * new_
1373 paste_size - DEH_SIZE * new_en
1374
1375 /* prepare space for new entry heads
1376 deh += before;
1377 memmove((char *)(deh + new_entry_coun
1378 insert_point - (char *)deh);
1379
1380 /* copy new entry heads */
1381 deh = (struct reiserfs_de_head *)((ch
1382 memcpy(deh, new_dehs, DEH_SIZE * new_
1383
1384 /* set locations of new records */
1385 for (i = 0; i < new_entry_count; i++)
1386 put_deh_location(&deh[i],
1387 deh_location
1388 (-deh_locati
1389 (&new_dehs[
1390 insert_poin
1391 item));
1392 }
1393
1394 /* change item key if necessary (when
1395 if (!before) {
1396 set_le_ih_k_offset(ih, deh_of
1397 }
1398 #ifdef CONFIG_REISERFS_CHECK
1399 {
1400 int prev, next;
1401 /* check record locations */
1402 deh = B_I_DEH(bh, ih);
1403 for (i = 0; i < ih_entry_coun
1404 next =
1405 (i <
1406 ih_entry_count(i
1407 1) ? deh_locatio
1408 prev = (i != 0) ? deh
1409
1410 if (prev && prev <= d
1411 reiserfs_erro
1412
1413
1414
1415
1416 if (next && next >= d
1417 reiserfs_erro
1418
1419
1420
1421
1422 }
1423 }
1424 #endif
1425
1426 }
1427
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.