Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
lbalance.c
Go to the documentation of this file.
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) */
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);
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),
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 ==
117  item_num_in_dest))
118  : 0, copy_count, deh + from, records,
119  DEH_SIZE * copy_count + copy_records_len);
120 }
121 
122 /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or
123  part of it or nothing (see the return 0 below) from SOURCE to the end
124  (if last_first) or beginning (!last_first) of the DEST */
125 /* returns 1 if anything was copied, else 0 */
126 static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
127  struct buffer_head *src, int last_first,
128  int bytes_or_entries)
129 {
130  struct buffer_head *dest = dest_bi->bi_bh;
131  int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */
132  struct item_head *ih;
133  struct item_head *dih;
134 
135  dest_nr_item = B_NR_ITEMS(dest);
136 
137  if (last_first == FIRST_TO_LAST) {
138  /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
139  or of different types ) then there is no need to treat this item differently from the other items
140  that we copy, so we return */
141  ih = B_N_PITEM_HEAD(src, 0);
142  dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1);
143  if (!dest_nr_item
144  || (!op_is_left_mergeable(&(ih->ih_key), src->b_size)))
145  /* there is nothing to merge */
146  return 0;
147 
148  RFALSE(!ih_item_len(ih),
149  "vs-10010: item can not have empty length");
150 
151  if (is_direntry_le_ih(ih)) {
152  if (bytes_or_entries == -1)
153  /* copy all entries to dest */
154  bytes_or_entries = ih_entry_count(ih);
155  leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
156  bytes_or_entries);
157  return 1;
158  }
159 
160  /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
161  part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
162  */
163  if (bytes_or_entries == -1)
164  bytes_or_entries = ih_item_len(ih);
165 
166 #ifdef CONFIG_REISERFS_CHECK
167  else {
168  if (bytes_or_entries == ih_item_len(ih)
169  && is_indirect_le_ih(ih))
170  if (get_ih_free_space(ih))
171  reiserfs_panic(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)) {
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))
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  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);
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);
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. */
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 */
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 */
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 */
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)))) &&
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 */
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 */
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 */
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)));
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 */
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);
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. */
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  */
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);
1124  }
1125 }
1126 
1127 /* delete del_num items from buffer starting from the first'th item */
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));
1195  }
1196 }
1197 
1198 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
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 }