?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] Switch Kprobes inline functions to __kprobes for x86_64
[linux-2.6/linux-acpi-2.6/ibm-acpi-2.6.git] / fs / reiserfs / lbalance.c
blob2533c1f64aba16b1d30d27ba3420afb1217cf092
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5 #include <linux/config.h>
6 #include <asm/uaccess.h>
7 #include <linux/string.h>
8 #include <linux/time.h>
9 #include <linux/reiserfs_fs.h>
10 #include <linux/buffer_head.h>
11
12 /* these are used in do_balance.c */
13
14 /* leaf_move_items
15 leaf_shift_left
16 leaf_shift_right
17 leaf_delete_items
18 leaf_insert_into_buf
19 leaf_paste_in_buffer
20 leaf_cut_from_buffer
21 leaf_paste_entries
22 */
23
24 /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
25 static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
26 struct buffer_head *source, int last_first,
27 int item_num, int from, int copy_count)
28 {
29 struct buffer_head *dest = dest_bi->bi_bh;
30 int item_num_in_dest; /* either the number of target item,
31 or if we must create a new item,
32 the number of the item we will
33 create it next to */
34 struct item_head *ih;
35 struct reiserfs_de_head *deh;
36 int copy_records_len; /* length of all records in item to be copied */
37 char *records;
38
39 ih = B_N_PITEM_HEAD(source, item_num);
40
41 RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
42
43 /* length of all record to be copied and first byte of the last of them */
44 deh = B_I_DEH(source, ih);
45 if (copy_count) {
46 copy_records_len = (from ? deh_location(&(deh[from - 1])) :
47 ih_item_len(ih)) -
48 deh_location(&(deh[from + copy_count - 1]));
49 records =
50 source->b_data + ih_location(ih) +
51 deh_location(&(deh[from + copy_count - 1]));
52 } else {
53 copy_records_len = 0;
54 records = NULL;
55 }
56
57 /* when copy last to first, dest buffer can contain 0 items */
58 item_num_in_dest =
59 (last_first ==
60 LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
61 - 1);
62
63 /* if there are no items in dest or the first/last item in dest is not item of the same directory */
64 if ((item_num_in_dest == -1) ||
65 (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
66 (last_first == LAST_TO_FIRST
67 && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
68 B_N_PKEY(dest,
69 item_num_in_dest))))
70 {
71 /* create new item in dest */
72 struct item_head new_ih;
73
74 /* form item header */
75 memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
76 put_ih_version(&new_ih, KEY_FORMAT_3_5);
77 /* calculate item len */
78 put_ih_item_len(&new_ih,
79 DEH_SIZE * copy_count + copy_records_len);
80 put_ih_entry_count(&new_ih, 0);
81
82 if (last_first == LAST_TO_FIRST) {
83 /* form key by the following way */
84 if (from < I_ENTRY_COUNT(ih)) {
85 set_le_ih_k_offset(&new_ih,
86 deh_offset(&(deh[from])));
87 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */
88 } else {
89 /* no entries will be copied to this item in this function */
90 set_le_ih_k_offset(&new_ih, U32_MAX);
91 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
92 }
93 set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key),
94 TYPE_DIRENTRY);
95 }
96
97 /* insert item into dest buffer */
98 leaf_insert_into_buf(dest_bi,
99 (last_first ==
100 LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
101 &new_ih, NULL, 0);
102 } else {
103 /* prepare space for entries */
104 leaf_paste_in_buffer(dest_bi,
105 (last_first ==
106 FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
107 1) : 0, MAX_US_INT,
108 DEH_SIZE * copy_count + copy_records_len,
109 records, 0);
110 }
111
112 item_num_in_dest =
113 (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
114
115 leaf_paste_entries(dest_bi->bi_bh, item_num_in_dest,
116 (last_first ==
117 FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest,
118 item_num_in_dest))
119 : 0, copy_count, deh + from, records,
120 DEH_SIZE * copy_count + copy_records_len);
121 }
122
123 /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or
124 part of it or nothing (see the return 0 below) from SOURCE to the end
125 (if last_first) or beginning (!last_first) of the DEST */
126 /* returns 1 if anything was copied, else 0 */
127 static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
128 struct buffer_head *src, int last_first,
129 int bytes_or_entries)
130 {
131 struct buffer_head *dest = dest_bi->bi_bh;
132 int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */
133 struct item_head *ih;
134 struct item_head *dih;
135
136 dest_nr_item = B_NR_ITEMS(dest);
137
138 if (last_first == FIRST_TO_LAST) {
139 /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
140 or of different types ) then there is no need to treat this item differently from the other items
141 that we copy, so we return */
142 ih = B_N_PITEM_HEAD(src, 0);
143 dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1);
144 if (!dest_nr_item
145 || (!op_is_left_mergeable(&(ih->ih_key), src->b_size)))
146 /* there is nothing to merge */
147 return 0;
148
149 RFALSE(!ih_item_len(ih),
150 "vs-10010: item can not have empty length");
151
152 if (is_direntry_le_ih(ih)) {
153 if (bytes_or_entries == -1)
154 /* copy all entries to dest */
155 bytes_or_entries = ih_entry_count(ih);
156 leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
157 bytes_or_entries);
158 return 1;
159 }
160
161 /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
162 part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
163 */
164 if (bytes_or_entries == -1)
165 bytes_or_entries = ih_item_len(ih);
166
167 #ifdef CONFIG_REISERFS_CHECK
168 else {
169 if (bytes_or_entries == ih_item_len(ih)
170 && is_indirect_le_ih(ih))
171 if (get_ih_free_space(ih))
172 reiserfs_panic(NULL,
173 "vs-10020: leaf_copy_boundary_item: "
174 "last unformatted node must be filled entirely (%h)",
175 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 */
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.) */
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 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
394 leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
395 item_num, 0, cpy_bytes);
396 else {
397 struct item_head n_ih;
398
399 /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
400 part defined by 'cpy_bytes'; create new item header; change old item_header (????);
401 n_ih = new item_header;
402 */
403 memcpy(&n_ih, ih, IH_SIZE);
404 put_ih_item_len(&n_ih, cpy_bytes);
405 if (is_indirect_le_ih(ih)) {
406 RFALSE(cpy_bytes == ih_item_len(ih)
407 && get_ih_free_space(ih),
408 "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
409 (long unsigned)get_ih_free_space(ih));
410 set_ih_free_space(&n_ih, 0);
411 }
412
413 RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
414 "vs-10190: bad mergeability of item %h", ih);
415 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
416 leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
417 B_N_PITEM(src, item_num), 0);
418 }
419 } else {
420 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
421 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
422 leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
423 item_num,
424 I_ENTRY_COUNT(ih) - cpy_bytes,
425 cpy_bytes);
426 else {
427 struct item_head n_ih;
428
429 /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
430 part defined by 'cpy_bytes'; create new item header;
431 n_ih = new item_header;
432 */
433 memcpy(&n_ih, ih, SHORT_KEY_SIZE);
434
435 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
436
437 if (is_direct_le_ih(ih)) {
438 set_le_ih_k_offset(&n_ih,
439 le_ih_k_offset(ih) +
440 ih_item_len(ih) - cpy_bytes);
441 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
442 set_ih_free_space(&n_ih, MAX_US_INT);
443 } else {
444 /* indirect item */
445 RFALSE(!cpy_bytes && get_ih_free_space(ih),
446 "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
447 set_le_ih_k_offset(&n_ih,
448 le_ih_k_offset(ih) +
449 (ih_item_len(ih) -
450 cpy_bytes) / UNFM_P_SIZE *
451 dest->b_size);
452 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
453 set_ih_free_space(&n_ih, get_ih_free_space(ih));
454 }
455
456 /* set item length */
457 put_ih_item_len(&n_ih, cpy_bytes);
458
459 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
460
461 leaf_insert_into_buf(dest_bi, 0, &n_ih,
462 B_N_PITEM(src,
463 item_num) +
464 ih_item_len(ih) - cpy_bytes, 0);
465 }
466 }
467 }
468
469 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
470 If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
471 From last item copy cpy_num bytes for regular item and cpy_num directory entries for
472 directory item. */
473 static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
474 int last_first, int cpy_num, int cpy_bytes)
475 {
476 struct buffer_head *dest;
477 int pos, i, src_nr_item, bytes;
478
479 dest = dest_bi->bi_bh;
480 RFALSE(!dest || !src, "vs-10210: !dest || !src");
481 RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
482 "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
483 RFALSE(B_NR_ITEMS(src) < cpy_num,
484 "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
485 cpy_num);
486 RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
487
488 if (cpy_num == 0)
489 return 0;
490
491 if (last_first == FIRST_TO_LAST) {
492 /* copy items to left */
493 pos = 0;
494 if (cpy_num == 1)
495 bytes = cpy_bytes;
496 else
497 bytes = -1;
498
499 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
500 i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
501 cpy_num -= i;
502 if (cpy_num == 0)
503 return i;
504 pos += i;
505 if (cpy_bytes == -1)
506 /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
507 leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
508 pos, cpy_num);
509 else {
510 /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
511 leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
512 pos, cpy_num - 1);
513
514 /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
515 leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
516 cpy_num + pos - 1, cpy_bytes);
517 }
518 } else {
519 /* copy items to right */
520 src_nr_item = B_NR_ITEMS(src);
521 if (cpy_num == 1)
522 bytes = cpy_bytes;
523 else
524 bytes = -1;
525
526 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
527 i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
528
529 cpy_num -= i;
530 if (cpy_num == 0)
531 return i;
532
533 pos = src_nr_item - cpy_num - i;
534 if (cpy_bytes == -1) {
535 /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
536 leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
537 pos, cpy_num);
538 } else {
539 /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
540 leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
541 pos + 1, cpy_num - 1);
542
543 /* copy part of the item which number is pos to the begin of the DEST */
544 leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
545 cpy_bytes);
546 }
547 }
548 return i;
549 }
550
551 /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
552 from R[0] to L[0]. for each of these we have to define parent and
553 positions of destination and source buffers */
554 static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
555 struct buffer_info *dest_bi,
556 struct buffer_info *src_bi,
557 int *first_last,
558 struct buffer_head *Snew)
559 {
560 memset(dest_bi, 0, sizeof(struct buffer_info));
561 memset(src_bi, 0, sizeof(struct buffer_info));
562
563 /* define dest, src, dest parent, dest position */
564 switch (shift_mode) {
565 case LEAF_FROM_S_TO_L: /* it is used in leaf_shift_left */
566 src_bi->tb = tb;
567 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
568 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
569 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); /* src->b_item_order */
570 dest_bi->tb = tb;
571 dest_bi->bi_bh = tb->L[0];
572 dest_bi->bi_parent = tb->FL[0];
573 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
574 *first_last = FIRST_TO_LAST;
575 break;
576
577 case LEAF_FROM_S_TO_R: /* it is used in leaf_shift_right */
578 src_bi->tb = tb;
579 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
580 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
581 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
582 dest_bi->tb = tb;
583 dest_bi->bi_bh = tb->R[0];
584 dest_bi->bi_parent = tb->FR[0];
585 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
586 *first_last = LAST_TO_FIRST;
587 break;
588
589 case LEAF_FROM_R_TO_L: /* it is used in balance_leaf_when_delete */
590 src_bi->tb = tb;
591 src_bi->bi_bh = tb->R[0];
592 src_bi->bi_parent = tb->FR[0];
593 src_bi->bi_position = get_right_neighbor_position(tb, 0);
594 dest_bi->tb = tb;
595 dest_bi->bi_bh = tb->L[0];
596 dest_bi->bi_parent = tb->FL[0];
597 dest_bi->bi_position = get_left_neighbor_position(tb, 0);
598 *first_last = FIRST_TO_LAST;
599 break;
600
601 case LEAF_FROM_L_TO_R: /* it is used in balance_leaf_when_delete */
602 src_bi->tb = tb;
603 src_bi->bi_bh = tb->L[0];
604 src_bi->bi_parent = tb->FL[0];
605 src_bi->bi_position = get_left_neighbor_position(tb, 0);
606 dest_bi->tb = tb;
607 dest_bi->bi_bh = tb->R[0];
608 dest_bi->bi_parent = tb->FR[0];
609 dest_bi->bi_position = get_right_neighbor_position(tb, 0);
610 *first_last = LAST_TO_FIRST;
611 break;
612
613 case LEAF_FROM_S_TO_SNEW:
614 src_bi->tb = tb;
615 src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
616 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
617 src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
618 dest_bi->tb = tb;
619 dest_bi->bi_bh = Snew;
620 dest_bi->bi_parent = NULL;
621 dest_bi->bi_position = 0;
622 *first_last = LAST_TO_FIRST;
623 break;
624
625 default:
626 reiserfs_panic(NULL,
627 "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)",
628 shift_mode);
629 }
630 RFALSE(src_bi->bi_bh == 0 || dest_bi->bi_bh == 0,
631 "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
632 shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
633 }
634
635 /* copy mov_num items and mov_bytes of the (mov_num-1)th item to
636 neighbor. Delete them from source */
637 int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
638 int mov_bytes, struct buffer_head *Snew)
639 {
640 int ret_value;
641 struct buffer_info dest_bi, src_bi;
642 int first_last;
643
644 leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
645 &first_last, Snew);
646
647 ret_value =
648 leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
649 mov_bytes);
650
651 leaf_delete_items(&src_bi, first_last,
652 (first_last ==
653 FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
654 mov_num), mov_num, mov_bytes);
655
656 return ret_value;
657 }
658
659 /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
660 from S[0] to L[0] and replace the delimiting key */
661 int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
662 {
663 struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
664 int i;
665
666 /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
667 i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
668
669 if (shift_num) {
670 if (B_NR_ITEMS(S0) == 0) { /* number of items in S[0] == 0 */
671
672 RFALSE(shift_bytes != -1,
673 "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
674 shift_bytes);
675 #ifdef CONFIG_REISERFS_CHECK
676 if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
677 print_cur_tb("vs-10275");
678 reiserfs_panic(tb->tb_sb,
679 "vs-10275: leaf_shift_left: balance condition corrupted (%c)",
680 tb->tb_mode);
681 }
682 #endif
683
684 if (PATH_H_POSITION(tb->tb_path, 1) == 0)
685 replace_key(tb, tb->CFL[0], tb->lkey[0],
686 PATH_H_PPARENT(tb->tb_path, 0), 0);
687
688 } else {
689 /* replace lkey in CFL[0] by 0-th key from S[0]; */
690 replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
691
692 RFALSE((shift_bytes != -1 &&
693 !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
694 && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
695 (!op_is_left_mergeable
696 (B_N_PKEY(S0, 0), S0->b_size)),
697 "vs-10280: item must be mergeable");
698 }
699 }
700
701 return i;
702 }
703
704 /* CLEANING STOPPED HERE */
705
706 /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
707 int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
708 {
709 // struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
710 int ret_value;
711
712 /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
713 ret_value =
714 leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
715
716 /* replace rkey in CFR[0] by the 0-th key from R[0] */
717 if (shift_num) {
718 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
719
720 }
721
722 return ret_value;
723 }
724
725 static void leaf_delete_items_entirely(struct buffer_info *bi,
726 int first, int del_num);
727 /* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
728 If not.
729 If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
730 the first item. Part defined by del_bytes. Don't delete first item header
731 If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
732 the last item . Part defined by del_bytes. Don't delete last item header.
733 */
734 void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
735 int first, int del_num, int del_bytes)
736 {
737 struct buffer_head *bh;
738 int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
739
740 RFALSE(!bh, "10155: bh is not defined");
741 RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
742 del_num);
743 RFALSE(first < 0
744 || first + del_num > item_amount,
745 "10165: invalid number of first item to be deleted (%d) or "
746 "no so much items (%d) to delete (only %d)", first,
747 first + del_num, item_amount);
748
749 if (del_num == 0)
750 return;
751
752 if (first == 0 && del_num == item_amount && del_bytes == -1) {
753 make_empty_node(cur_bi);
754 do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
755 return;
756 }
757
758 if (del_bytes == -1)
759 /* delete del_num items beginning from item in position first */
760 leaf_delete_items_entirely(cur_bi, first, del_num);
761 else {
762 if (last_first == FIRST_TO_LAST) {
763 /* delete del_num-1 items beginning from item in position first */
764 leaf_delete_items_entirely(cur_bi, first, del_num - 1);
765
766 /* delete the part of the first item of the bh
767 do not delete item header
768 */
769 leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
770 } else {
771 struct item_head *ih;
772 int len;
773
774 /* delete del_num-1 items beginning from item in position first+1 */
775 leaf_delete_items_entirely(cur_bi, first + 1,
776 del_num - 1);
777
778 if (is_direntry_le_ih
779 (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1)))
780 /* the last item is directory */
781 /* len = numbers of directory entries in this item */
782 len = ih_entry_count(ih);
783 else
784 /* len = body len of item */
785 len = ih_item_len(ih);
786
787 /* delete the part of the last item of the bh
788 do not delete item header
789 */
790 leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
791 len - del_bytes, del_bytes);
792 }
793 }
794 }
795
796 /* insert item into the leaf node in position before */
797 void leaf_insert_into_buf(struct buffer_info *bi, int before,
798 struct item_head *inserted_item_ih,
799 const char *inserted_item_body, int zeros_number)
800 {
801 struct buffer_head *bh = bi->bi_bh;
802 int nr, free_space;
803 struct block_head *blkh;
804 struct item_head *ih;
805 int i;
806 int last_loc, unmoved_loc;
807 char *to;
808
809 blkh = B_BLK_HEAD(bh);
810 nr = blkh_nr_item(blkh);
811 free_space = blkh_free_space(blkh);
812
813 /* check free space */
814 RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
815 "vs-10170: not enough free space in block %z, new item %h",
816 bh, inserted_item_ih);
817 RFALSE(zeros_number > ih_item_len(inserted_item_ih),
818 "vs-10172: zero number == %d, item length == %d",
819 zeros_number, ih_item_len(inserted_item_ih));
820
821 /* get item new item must be inserted before */
822 ih = B_N_PITEM_HEAD(bh, before);
823
824 /* prepare space for the body of new item */
825 last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size;
826 unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
827
828 memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
829 bh->b_data + last_loc, unmoved_loc - last_loc);
830
831 to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
832 memset(to, 0, zeros_number);
833 to += zeros_number;
834
835 /* copy body to prepared space */
836 if (inserted_item_body)
837 memmove(to, inserted_item_body,
838 ih_item_len(inserted_item_ih) - zeros_number);
839 else
840 memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
841
842 /* insert item header */
843 memmove(ih + 1, ih, IH_SIZE * (nr - before));
844 memmove(ih, inserted_item_ih, IH_SIZE);
845
846 /* change locations */
847 for (i = before; i < nr + 1; i++) {
848 unmoved_loc -= ih_item_len(&(ih[i - before]));
849 put_ih_location(&(ih[i - before]), unmoved_loc);
850 }
851
852 /* sizes, free space, item number */
853 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
854 set_blkh_free_space(blkh,
855 free_space - (IH_SIZE +
856 ih_item_len(inserted_item_ih)));
857 do_balance_mark_leaf_dirty(bi->tb, bh, 1);
858
859 if (bi->bi_parent) {
860 struct disk_child *t_dc;
861 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
862 put_dc_size(t_dc,
863 dc_size(t_dc) + (IH_SIZE +
864 ih_item_len(inserted_item_ih)));
865 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
866 }
867 }
868
869 /* paste paste_size bytes to affected_item_num-th item.
870 When item is a directory, this only prepare space for new entries */
871 void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
872 int pos_in_item, int paste_size,
873 const char *body, int zeros_number)
874 {
875 struct buffer_head *bh = bi->bi_bh;
876 int nr, free_space;
877 struct block_head *blkh;
878 struct item_head *ih;
879 int i;
880 int last_loc, unmoved_loc;
881
882 blkh = B_BLK_HEAD(bh);
883 nr = blkh_nr_item(blkh);
884 free_space = blkh_free_space(blkh);
885
886 /* check free space */
887 RFALSE(free_space < paste_size,
888 "vs-10175: not enough free space: needed %d, available %d",
889 paste_size, free_space);
890
891 #ifdef CONFIG_REISERFS_CHECK
892 if (zeros_number > paste_size) {
893 print_cur_tb("10177");
894 reiserfs_panic(NULL,
895 "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d",
896 zeros_number, paste_size);
897 }
898 #endif /* CONFIG_REISERFS_CHECK */
899
900 /* item to be appended */
901 ih = B_N_PITEM_HEAD(bh, affected_item_num);
902
903 last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
904 unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
905
906 /* prepare space */
907 memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
908 unmoved_loc - last_loc);
909
910 /* change locations */
911 for (i = affected_item_num; i < nr; i++)
912 put_ih_location(&(ih[i - affected_item_num]),
913 ih_location(&(ih[i - affected_item_num])) -
914 paste_size);
915
916 if (body) {
917 if (!is_direntry_le_ih(ih)) {
918 if (!pos_in_item) {
919 /* shift data to right */
920 memmove(bh->b_data + ih_location(ih) +
921 paste_size,
922 bh->b_data + ih_location(ih),
923 ih_item_len(ih));
924 /* paste data in the head of item */
925 memset(bh->b_data + ih_location(ih), 0,
926 zeros_number);
927 memcpy(bh->b_data + ih_location(ih) +
928 zeros_number, body,
929 paste_size - zeros_number);
930 } else {
931 memset(bh->b_data + unmoved_loc - paste_size, 0,
932 zeros_number);
933 memcpy(bh->b_data + unmoved_loc - paste_size +
934 zeros_number, body,
935 paste_size - zeros_number);
936 }
937 }
938 } else
939 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
940
941 put_ih_item_len(ih, ih_item_len(ih) + paste_size);
942
943 /* change free space */
944 set_blkh_free_space(blkh, free_space - paste_size);
945
946 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
947
948 if (bi->bi_parent) {
949 struct disk_child *t_dc =
950 B_N_CHILD(bi->bi_parent, bi->bi_position);
951 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
952 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
953 }
954 }
955
956 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
957 does not have free space, so it moves DEHs and remaining records as
958 necessary. Return value is size of removed part of directory item
959 in bytes. */
960 static int leaf_cut_entries(struct buffer_head *bh,
961 struct item_head *ih, int from, int del_count)
962 {
963 char *item;
964 struct reiserfs_de_head *deh;
965 int prev_record_offset; /* offset of record, that is (from-1)th */
966 char *prev_record; /* */
967 int cut_records_len; /* length of all removed records */
968 int i;
969
970 /* make sure, that item is directory and there are enough entries to
971 remove */
972 RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
973 RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
974 "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
975 I_ENTRY_COUNT(ih), from, del_count);
976
977 if (del_count == 0)
978 return 0;
979
980 /* first byte of item */
981 item = bh->b_data + ih_location(ih);
982
983 /* entry head array */
984 deh = B_I_DEH(bh, ih);
985
986 /* first byte of remaining entries, those are BEFORE cut entries
987 (prev_record) and length of all removed records (cut_records_len) */
988 prev_record_offset =
989 (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
990 cut_records_len = prev_record_offset /*from_record */ -
991 deh_location(&(deh[from + del_count - 1]));
992 prev_record = item + prev_record_offset;
993
994 /* adjust locations of remaining entries */
995 for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
996 put_deh_location(&(deh[i]),
997 deh_location(&deh[i]) -
998 (DEH_SIZE * del_count));
999
1000 for (i = 0; i < from; i++)
1001 put_deh_location(&(deh[i]),
1002 deh_location(&deh[i]) - (DEH_SIZE * del_count +
1003 cut_records_len));
1004
1005 put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
1006
1007 /* shift entry head array and entries those are AFTER removed entries */
1008 memmove((char *)(deh + from),
1009 deh + from + del_count,
1010 prev_record - cut_records_len - (char *)(deh + from +
1011 del_count));
1012
1013 /* shift records, those are BEFORE removed entries */
1014 memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
1015 prev_record, item + ih_item_len(ih) - prev_record);
1016
1017 return DEH_SIZE * del_count + cut_records_len;
1018 }
1019
1020 /* when cut item is part of regular file
1021 pos_in_item - first byte that must be cut
1022 cut_size - number of bytes to be cut beginning from pos_in_item
1023
1024 when cut item is part of directory
1025 pos_in_item - number of first deleted entry
1026 cut_size - count of deleted entries
1027 */
1028 void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1029 int pos_in_item, int cut_size)
1030 {
1031 int nr;
1032 struct buffer_head *bh = bi->bi_bh;
1033 struct block_head *blkh;
1034 struct item_head *ih;
1035 int last_loc, unmoved_loc;
1036 int i;
1037
1038 blkh = B_BLK_HEAD(bh);
1039 nr = blkh_nr_item(blkh);
1040
1041 /* item head of truncated item */
1042 ih = B_N_PITEM_HEAD(bh, cut_item_num);
1043
1044 if (is_direntry_le_ih(ih)) {
1045 /* first cut entry () */
1046 cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
1047 if (pos_in_item == 0) {
1048 /* change key */
1049 RFALSE(cut_item_num,
1050 "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
1051 cut_item_num);
1052 /* change item key by key of first entry in the item */
1053 set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
1054 /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
1055 }
1056 } else {
1057 /* item is direct or indirect */
1058 RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
1059 RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
1060 "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1061 (long unsigned)pos_in_item, (long unsigned)cut_size,
1062 (long unsigned)ih_item_len(ih));
1063
1064 /* shift item body to left if cut is from the head of item */
1065 if (pos_in_item == 0) {
1066 memmove(bh->b_data + ih_location(ih),
1067 bh->b_data + ih_location(ih) + cut_size,
1068 ih_item_len(ih) - cut_size);
1069
1070 /* change key of item */
1071 if (is_direct_le_ih(ih))
1072 set_le_ih_k_offset(ih,
1073 le_ih_k_offset(ih) +
1074 cut_size);
1075 else {
1076 set_le_ih_k_offset(ih,
1077 le_ih_k_offset(ih) +
1078 (cut_size / UNFM_P_SIZE) *
1079 bh->b_size);
1080 RFALSE(ih_item_len(ih) == cut_size
1081 && get_ih_free_space(ih),
1082 "10205: invalid ih_free_space (%h)", ih);
1083 }
1084 }
1085 }
1086
1087 /* location of the last item */
1088 last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
1089
1090 /* location of the item, which is remaining at the same place */
1091 unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
1092
1093 /* shift */
1094 memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1095 unmoved_loc - last_loc - cut_size);
1096
1097 /* change item length */
1098 put_ih_item_len(ih, ih_item_len(ih) - cut_size);
1099
1100 if (is_indirect_le_ih(ih)) {
1101 if (pos_in_item)
1102 set_ih_free_space(ih, 0);
1103 }
1104
1105 /* change locations */
1106 for (i = cut_item_num; i < nr; i++)
1107 put_ih_location(&(ih[i - cut_item_num]),
1108 ih_location(&ih[i - cut_item_num]) + cut_size);
1109
1110 /* size, free space */
1111 set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1112
1113 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1114
1115 if (bi->bi_parent) {
1116 struct disk_child *t_dc;
1117 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1118 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1119 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1120 }
1121 }
1122
1123 /* delete del_num items from buffer starting from the first'th item */
1124 static void leaf_delete_items_entirely(struct buffer_info *bi,
1125 int first, int del_num)
1126 {
1127 struct buffer_head *bh = bi->bi_bh;
1128 int nr;
1129 int i, j;
1130 int last_loc, last_removed_loc;
1131 struct block_head *blkh;
1132 struct item_head *ih;
1133
1134 RFALSE(bh == NULL, "10210: buffer is 0");
1135 RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
1136
1137 if (del_num == 0)
1138 return;
1139
1140 blkh = B_BLK_HEAD(bh);
1141 nr = blkh_nr_item(blkh);
1142
1143 RFALSE(first < 0 || first + del_num > nr,
1144 "10220: first=%d, number=%d, there is %d items", first, del_num,
1145 nr);
1146
1147 if (first == 0 && del_num == nr) {
1148 /* this does not work */
1149 make_empty_node(bi);
1150
1151 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1152 return;
1153 }
1154
1155 ih = B_N_PITEM_HEAD(bh, first);
1156
1157 /* location of unmovable item */
1158 j = (first == 0) ? bh->b_size : ih_location(ih - 1);
1159
1160 /* delete items */
1161 last_loc = ih_location(&(ih[nr - 1 - first]));
1162 last_removed_loc = ih_location(&(ih[del_num - 1]));
1163
1164 memmove(bh->b_data + last_loc + j - last_removed_loc,
1165 bh->b_data + last_loc, last_removed_loc - last_loc);
1166
1167 /* delete item headers */
1168 memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1169
1170 /* change item location */
1171 for (i = first; i < nr - del_num; i++)
1172 put_ih_location(&(ih[i - first]),
1173 ih_location(&(ih[i - first])) + (j -
1174 last_removed_loc));
1175
1176 /* sizes, item number */
1177 set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1178 set_blkh_free_space(blkh,
1179 blkh_free_space(blkh) + (j - last_removed_loc +
1180 IH_SIZE * del_num));
1181
1182 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1183
1184 if (bi->bi_parent) {
1185 struct disk_child *t_dc =
1186 B_N_CHILD(bi->bi_parent, bi->bi_position);
1187 put_dc_size(t_dc,
1188 dc_size(t_dc) - (j - last_removed_loc +
1189 IH_SIZE * del_num));
1190 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1191 }
1192 }
1193
1194 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1195 void leaf_paste_entries(struct buffer_head *bh,
1196 int item_num,
1197 int before,
1198 int new_entry_count,
1199 struct reiserfs_de_head *new_dehs,
1200 const char *records, int paste_size)
1201 {
1202 struct item_head *ih;
1203 char *item;
1204 struct reiserfs_de_head *deh;
1205 char *insert_point;
1206 int i, old_entry_num;
1207
1208 if (new_entry_count == 0)
1209 return;
1210
1211 ih = B_N_PITEM_HEAD(bh, item_num);
1212
1213 /* make sure, that item is directory, and there are enough records in it */
1214 RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
1215 RFALSE(I_ENTRY_COUNT(ih) < before,
1216 "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1217 I_ENTRY_COUNT(ih), before);
1218
1219 /* first byte of dest item */
1220 item = bh->b_data + ih_location(ih);
1221
1222 /* entry head array */
1223 deh = B_I_DEH(bh, ih);
1224
1225 /* new records will be pasted at this point */
1226 insert_point =
1227 item +
1228 (before ? deh_location(&(deh[before - 1]))
1229 : (ih_item_len(ih) - paste_size));
1230
1231 /* adjust locations of records that will be AFTER new records */
1232 for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
1233 put_deh_location(&(deh[i]),
1234 deh_location(&(deh[i])) +
1235 (DEH_SIZE * new_entry_count));
1236
1237 /* adjust locations of records that will be BEFORE new records */
1238 for (i = 0; i < before; i++)
1239 put_deh_location(&(deh[i]),
1240 deh_location(&(deh[i])) + paste_size);
1241
1242 old_entry_num = I_ENTRY_COUNT(ih);
1243 put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
1244
1245 /* prepare space for pasted records */
1246 memmove(insert_point + paste_size, insert_point,
1247 item + (ih_item_len(ih) - paste_size) - insert_point);
1248
1249 /* copy new records */
1250 memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1251 paste_size - DEH_SIZE * new_entry_count);
1252
1253 /* prepare space for new entry heads */
1254 deh += before;
1255 memmove((char *)(deh + new_entry_count), deh,
1256 insert_point - (char *)deh);
1257
1258 /* copy new entry heads */
1259 deh = (struct reiserfs_de_head *)((char *)deh);
1260 memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
1261
1262 /* set locations of new records */
1263 for (i = 0; i < new_entry_count; i++) {
1264 put_deh_location(&(deh[i]),
1265 deh_location(&(deh[i])) +
1266 (-deh_location
1267 (&(new_dehs[new_entry_count - 1])) +
1268 insert_point + DEH_SIZE * new_entry_count -
1269 item));
1270 }
1271
1272 /* change item key if necessary (when we paste before 0-th entry */
1273 if (!before) {
1274 set_le_ih_k_offset(ih, deh_offset(new_dehs));
1275 /* memcpy (&ih->ih_key.k_offset,
1276 &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1277 }
1278 #ifdef CONFIG_REISERFS_CHECK
1279 {
1280 int prev, next;
1281 /* check record locations */
1282 deh = B_I_DEH(bh, ih);
1283 for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
1284 next =
1285 (i <
1286 I_ENTRY_COUNT(ih) -
1287 1) ? deh_location(&(deh[i + 1])) : 0;
1288 prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
1289
1290 if (prev && prev <= deh_location(&(deh[i])))
1291 reiserfs_warning(NULL,
1292 "vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)",
1293 ih, deh + i - 1, i, deh + i);
1294 if (next && next >= deh_location(&(deh[i])))
1295 reiserfs_warning(NULL,
1296 "vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)",
1297 ih, i, deh + i, deh + i + 1);
1298 }
1299 }
1300 #endif
1301
1302 }
Linux 2.6 ibm-acpi/thinkpad-acpi driver git tree