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