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