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) */
leaf_copy_dir_entries(struct buffer_info * dest_bi,struct buffer_head * source,int last_first,int item_num,int from,int copy_count)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, 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 */
leaf_copy_boundary_item(struct buffer_info * dest_bi,struct buffer_head * src,int last_first,int bytes_or_entries)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(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 */
leaf_copy_items_entirely(struct buffer_info * dest_bi,struct buffer_head * src,int last_first,int first,int cpy_num)283 static 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.) */
leaf_item_bottle(struct buffer_info * dest_bi,struct buffer_head * src,int last_first,int item_num,int cpy_bytes)381 static 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. */
leaf_copy_items(struct buffer_info * dest_bi,struct buffer_head * src,int last_first,int cpy_num,int cpy_bytes)475 static 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 */
leaf_define_dest_src_infos(int shift_mode,struct tree_balance * tb,struct buffer_info * dest_bi,struct buffer_info * src_bi,int * first_last,struct buffer_head * Snew)556 static 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 */
leaf_move_items(int shift_mode,struct tree_balance * tb,int mov_num,int mov_bytes,struct buffer_head * Snew)638 int 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 */
leaf_shift_left(struct tree_balance * tb,int shift_num,int shift_bytes)662 int 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 */
leaf_shift_right(struct tree_balance * tb,int shift_num,int shift_bytes)708 int 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
726 static 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 */
leaf_delete_items(struct buffer_info * cur_bi,int last_first,int first,int del_num,int del_bytes)735 void 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 */
leaf_insert_into_buf(struct buffer_info * bi,int before,struct item_head * inserted_item_ih,const char * inserted_item_body,int zeros_number)798 void 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 */
leaf_paste_in_buffer(struct buffer_info * bi,int affected_item_num,int pos_in_item,int paste_size,const char * body,int zeros_number)872 void 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. */
leaf_cut_entries(struct buffer_head * bh,struct item_head * ih,int from,int del_count)964 static 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 */
leaf_cut_from_buffer(struct buffer_info * bi,int cut_item_num,int pos_in_item,int cut_size)1032 void 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 */
leaf_delete_items_entirely(struct buffer_info * bi,int first,int del_num)1128 static 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 */
leaf_paste_entries(struct buffer_info * bi,int item_num,int before,int new_entry_count,struct reiserfs_de_head * new_dehs,const char * records,int paste_size)1199 void 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 }
1312