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