blob: 03d85cbf90bf644e40ef046c606c0dff61d99506 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
Linus Torvalds1da177e2005-04-16 15:20:36 -07005#include <asm/uaccess.h>
6#include <linux/string.h>
7#include <linux/time.h>
8#include <linux/reiserfs_fs.h>
9#include <linux/buffer_head.h>
10
11/* these are used in do_balance.c */
12
13/* leaf_move_items
14 leaf_shift_left
15 leaf_shift_right
16 leaf_delete_items
17 leaf_insert_into_buf
18 leaf_paste_in_buffer
19 leaf_cut_from_buffer
20 leaf_paste_entries
21 */
22
Linus Torvalds1da177e2005-04-16 15:20:36 -070023/* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070024static 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)
Linus Torvalds1da177e2005-04-16 15:20:36 -070027{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070028 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -070037
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070038 ih = B_N_PITEM_HEAD(source, item_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -070039
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070040 RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
Linus Torvalds1da177e2005-04-16 15:20:36 -070041
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070042 /* 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -070054 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070055
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070056 /* when copy last to first, dest buffer can contain 0 items */
57 item_num_in_dest =
58 (last_first ==
59 LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
60 - 1);
61
62 /* if there are no items in dest or the first/last item in dest is not item of the same directory */
63 if ((item_num_in_dest == -1) ||
64 (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
65 (last_first == LAST_TO_FIRST
66 && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
67 B_N_PKEY(dest,
68 item_num_in_dest))))
69 {
70 /* create new item in dest */
71 struct item_head new_ih;
72
73 /* form item header */
74 memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
75 put_ih_version(&new_ih, KEY_FORMAT_3_5);
76 /* calculate item len */
77 put_ih_item_len(&new_ih,
78 DEH_SIZE * copy_count + copy_records_len);
79 put_ih_entry_count(&new_ih, 0);
80
81 if (last_first == LAST_TO_FIRST) {
82 /* form key by the following way */
83 if (from < I_ENTRY_COUNT(ih)) {
84 set_le_ih_k_offset(&new_ih,
85 deh_offset(&(deh[from])));
86 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */
87 } else {
88 /* no entries will be copied to this item in this function */
89 set_le_ih_k_offset(&new_ih, U32_MAX);
90 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
91 }
92 set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key),
93 TYPE_DIRENTRY);
94 }
95
96 /* insert item into dest buffer */
97 leaf_insert_into_buf(dest_bi,
98 (last_first ==
99 LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
100 &new_ih, NULL, 0);
101 } else {
102 /* prepare space for entries */
103 leaf_paste_in_buffer(dest_bi,
104 (last_first ==
105 FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
106 1) : 0, MAX_US_INT,
107 DEH_SIZE * copy_count + copy_records_len,
108 records, 0);
109 }
110
111 item_num_in_dest =
112 (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
113
Jeff Mahoneyeba00302009-03-30 14:02:18 -0400114 leaf_paste_entries(dest_bi, item_num_in_dest,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700115 (last_first ==
116 FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest,
117 item_num_in_dest))
118 : 0, copy_count, deh + from, records,
119 DEH_SIZE * copy_count + copy_records_len);
120}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121
Jeff Mahoney0222e652009-03-30 14:02:44 -0400122/* 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
Linus Torvalds1da177e2005-04-16 15:20:36 -0700124 (if last_first) or beginning (!last_first) of the DEST */
125/* returns 1 if anything was copied, else 0 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700126static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
127 struct buffer_head *src, int last_first,
128 int bytes_or_entries)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700130 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165
166#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700167 else {
168 if (bytes_or_entries == ih_item_len(ih)
169 && is_indirect_le_ih(ih))
170 if (get_ih_free_space(ih))
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400171 reiserfs_panic(sb_from_bi(dest_bi),
172 "vs-10020",
173 "last unformatted node "
174 "must be filled "
175 "entirely (%h)", ih);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700176 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700177#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700179 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700184
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700185 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 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700193 return 1;
194 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700195
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700196 /* copy boundary item to right (last_first == LAST_TO_FIRST) */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700197
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700198 /* ( 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700205 if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size))
206 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700208 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700212
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700213 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277}
278
Linus Torvalds1da177e2005-04-16 15:20:36 -0700279/* 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 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700283static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
284 struct buffer_head *src, int last_first,
285 int first, int cpy_num)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700286{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700287 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700295 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");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700303 dest = dest_bi->bi_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700304
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700305 RFALSE(!dest, "vs-10130: can not copy negative amount of items");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700307 if (cpy_num == 0)
308 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700309
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700310 blkh = B_BLK_HEAD(dest);
311 nr = blkh_nr_item(blkh);
312 free_space = blkh_free_space(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700313
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700314 /* 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700316
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700317 /* location of head of first new item */
318 ih = B_N_PITEM_HEAD(dest, dest_before);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700320 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700323
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700324 /* prepare space for headers */
325 memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700326
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700327 /* copy item headers */
328 memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700329
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700330 free_space -= (IH_SIZE * cpy_num);
331 set_blkh_free_space(blkh, free_space);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700332
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700333 /* 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 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700340 /* 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]));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700343
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700344 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700349 memmove(dest->b_data + last_loc,
350 dest->b_data + last_loc + j - last_inserted_loc,
351 last_inserted_loc - last_loc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700352
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700353 /* copy items */
354 memcpy(dest->b_data + last_inserted_loc,
355 B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700357 /* sizes, item number */
358 set_blkh_nr_item(blkh, nr + cpy_num);
359 set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700360
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700361 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 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377}
378
Linus Torvalds1da177e2005-04-16 15:20:36 -0700379/* This function splits the (liquid) item into two items (useful when
380 shifting part of an item into another node.) */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700381static void leaf_item_bottle(struct buffer_info *dest_bi,
382 struct buffer_head *src, int last_first,
383 int item_num, int cpy_bytes)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700385 struct buffer_head *dest = dest_bi->bi_bh;
386 struct item_head *ih;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700388 RFALSE(cpy_bytes == -1,
389 "vs-10170: bytes == - 1 means: do not split item");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700391 if (last_first == FIRST_TO_LAST) {
392 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
Jeff Mahoney1d965fe2009-06-17 16:26:29 -0700393 ih = B_N_PITEM_HEAD(src, item_num);
394 if (is_direntry_le_ih(ih))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700395 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
Jeff Mahoney0222e652009-03-30 14:02:44 -0400400 /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700401 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 ) */
Jeff Mahoney1d965fe2009-06-17 16:26:29 -0700422 ih = B_N_PITEM_HEAD(src, item_num);
423 if (is_direntry_le_ih(ih))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700424 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
Jeff Mahoney0222e652009-03-30 14:02:44 -0400431 /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700432 part defined by 'cpy_bytes'; create new item header;
433 n_ih = new item_header;
434 */
435 memcpy(&n_ih, ih, SHORT_KEY_SIZE);
436
437 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
438
439 if (is_direct_le_ih(ih)) {
440 set_le_ih_k_offset(&n_ih,
441 le_ih_k_offset(ih) +
442 ih_item_len(ih) - cpy_bytes);
443 set_le_ih_k_type(&n_ih, TYPE_DIRECT);
444 set_ih_free_space(&n_ih, MAX_US_INT);
445 } else {
446 /* indirect item */
447 RFALSE(!cpy_bytes && get_ih_free_space(ih),
448 "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
449 set_le_ih_k_offset(&n_ih,
450 le_ih_k_offset(ih) +
451 (ih_item_len(ih) -
452 cpy_bytes) / UNFM_P_SIZE *
453 dest->b_size);
454 set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
455 set_ih_free_space(&n_ih, get_ih_free_space(ih));
456 }
457
458 /* set item length */
459 put_ih_item_len(&n_ih, cpy_bytes);
460
461 n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
462
463 leaf_insert_into_buf(dest_bi, 0, &n_ih,
464 B_N_PITEM(src,
465 item_num) +
466 ih_item_len(ih) - cpy_bytes, 0);
467 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469}
470
Linus Torvalds1da177e2005-04-16 15:20:36 -0700471/* 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. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700475static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
476 int last_first, int cpy_num, int cpy_bytes)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700478 struct buffer_head *dest;
479 int pos, i, src_nr_item, bytes;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700480
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700481 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700490 if (cpy_num == 0)
491 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700493 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700551}
552
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553/* 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 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700556static 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)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700562 memset(dest_bi, 0, sizeof(struct buffer_info));
563 memset(src_bi, 0, sizeof(struct buffer_info));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700565 /* 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700578
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700579 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700590
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700591 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700602
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700603 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:
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400628 reiserfs_panic(sb_from_bi(src_bi), "vs-10250",
629 "shift type is unknown (%d)", shift_mode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700630 }
Al Viro9dce07f2008-03-29 03:07:28 +0000631 RFALSE(!src_bi->bi_bh || !dest_bi->bi_bh,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700632 "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
633 shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634}
635
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636/* copy mov_num items and mov_bytes of the (mov_num-1)th item to
637 neighbor. Delete them from source */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700638int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
639 int mov_bytes, struct buffer_head *Snew)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700641 int ret_value;
642 struct buffer_info dest_bi, src_bi;
643 int first_last;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700645 leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
646 &first_last, Snew);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700648 ret_value =
649 leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
650 mov_bytes);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700651
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700652 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700657 return ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700658}
659
Linus Torvalds1da177e2005-04-16 15:20:36 -0700660/* 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 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700662int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700664 struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
665 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700667 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700669
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700670 if (shift_num) {
671 if (B_NR_ITEMS(S0) == 0) { /* number of items in S[0] == 0 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700673 RFALSE(shift_bytes != -1,
674 "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
675 shift_bytes);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700676#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700677 if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
678 print_cur_tb("vs-10275");
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400679 reiserfs_panic(tb->tb_sb, "vs-10275",
680 "balance condition corrupted "
681 "(%c)", tb->tb_mode);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700682 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700683#endif
684
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700685 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700689 } else {
690 /* replace lkey in CFL[0] by 0-th key from S[0]; */
691 replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
692
693 RFALSE((shift_bytes != -1 &&
694 !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
695 && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
696 (!op_is_left_mergeable
697 (B_N_PKEY(S0, 0), S0->b_size)),
698 "vs-10280: item must be mergeable");
699 }
700 }
701
702 return i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700703}
704
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705/* CLEANING STOPPED HERE */
706
Linus Torvalds1da177e2005-04-16 15:20:36 -0700707/* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700708int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700709{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700710 // struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
711 int ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700713 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700717 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700721 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700722
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700723 return ret_value;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700724}
725
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700726static void leaf_delete_items_entirely(struct buffer_info *bi,
727 int first, int del_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700728/* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
Jeff Mahoney0222e652009-03-30 14:02:44 -0400729 If not.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730 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*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700735void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
736 int first, int del_num, int del_bytes)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700737{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700738 struct buffer_head *bh;
739 int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700740
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700741 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700750 if (del_num == 0)
751 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700752
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700753 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700758
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700759 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
Jeff Mahoney1d965fe2009-06-17 16:26:29 -0700779 ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1);
780 if (is_direntry_le_ih(ih))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700781 /* 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
Jeff Mahoney0222e652009-03-30 14:02:44 -0400788 /* delete the part of the last item of the bh
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700789 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}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796
797/* insert item into the leaf node in position before */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700798void 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)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700802 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700809
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700810 blkh = B_BLK_HEAD(bh);
811 nr = blkh_nr_item(blkh);
812 free_space = blkh_free_space(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700813
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700814 /* 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700821
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700822 /* get item new item must be inserted before */
823 ih = B_N_PITEM_HEAD(bh, before);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700825 /* 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700828
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700829 memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
830 bh->b_data + last_loc, unmoved_loc - last_loc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700832 to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
833 memset(to, 0, zeros_number);
834 to += zeros_number;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700835
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700836 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700842
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700843 /* insert item header */
844 memmove(ih + 1, ih, IH_SIZE * (nr - before));
845 memmove(ih, inserted_item_ih, IH_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700847 /* 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 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700853 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700860 if (bi->bi_parent) {
861 struct disk_child *t_dc;
862 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
863 put_dc_size(t_dc,
864 dc_size(t_dc) + (IH_SIZE +
865 ih_item_len(inserted_item_ih)));
866 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
867 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700868}
869
Jeff Mahoney0222e652009-03-30 14:02:44 -0400870/* paste paste_size bytes to affected_item_num-th item.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871 When item is a directory, this only prepare space for new entries */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700872void 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)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700876 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700882
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700883 blkh = B_BLK_HEAD(bh);
884 nr = blkh_nr_item(blkh);
885 free_space = blkh_free_space(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700886
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700887 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700891
892#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700893 if (zeros_number > paste_size) {
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400894 struct super_block *sb = NULL;
895 if (bi && bi->tb)
896 sb = bi->tb->tb_sb;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700897 print_cur_tb("10177");
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400898 reiserfs_panic(sb, "vs-10177",
899 "zeros_number == %d, paste_size == %d",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700900 zeros_number, paste_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700901 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700902#endif /* CONFIG_REISERFS_CHECK */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700904 /* item to be appended */
905 ih = B_N_PITEM_HEAD(bh, affected_item_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700906
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700907 last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
908 unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700909
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700910 /* prepare space */
911 memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
912 unmoved_loc - last_loc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700914 /* change locations */
915 for (i = affected_item_num; i < nr; i++)
916 put_ih_location(&(ih[i - affected_item_num]),
917 ih_location(&(ih[i - affected_item_num])) -
918 paste_size);
919
920 if (body) {
921 if (!is_direntry_le_ih(ih)) {
922 if (!pos_in_item) {
923 /* shift data to right */
924 memmove(bh->b_data + ih_location(ih) +
925 paste_size,
926 bh->b_data + ih_location(ih),
927 ih_item_len(ih));
928 /* paste data in the head of item */
929 memset(bh->b_data + ih_location(ih), 0,
930 zeros_number);
931 memcpy(bh->b_data + ih_location(ih) +
932 zeros_number, body,
933 paste_size - zeros_number);
934 } else {
935 memset(bh->b_data + unmoved_loc - paste_size, 0,
936 zeros_number);
937 memcpy(bh->b_data + unmoved_loc - paste_size +
938 zeros_number, body,
939 paste_size - zeros_number);
940 }
941 }
942 } else
943 memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
944
945 put_ih_item_len(ih, ih_item_len(ih) + paste_size);
946
947 /* change free space */
948 set_blkh_free_space(blkh, free_space - paste_size);
949
950 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
951
952 if (bi->bi_parent) {
953 struct disk_child *t_dc =
954 B_N_CHILD(bi->bi_parent, bi->bi_position);
955 put_dc_size(t_dc, dc_size(t_dc) + paste_size);
956 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
957 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700958}
959
Linus Torvalds1da177e2005-04-16 15:20:36 -0700960/* 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. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700964static int leaf_cut_entries(struct buffer_head *bh,
965 struct item_head *ih, int from, int del_count)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700967 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700974 /* 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_cout = %d, from = %d, to delete = %d",
979 I_ENTRY_COUNT(ih), from, del_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700981 if (del_count == 0)
982 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700983
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700984 /* first byte of item */
985 item = bh->b_data + ih_location(ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700986
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700987 /* entry head array */
988 deh = B_I_DEH(bh, ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700989
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700990 /* 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700997
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700998 /* 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001003
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001004 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001008
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001009 put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001011 /* 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001017 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001020
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001021 return DEH_SIZE * del_count + cut_records_len;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001022}
1023
Linus Torvalds1da177e2005-04-16 15:20:36 -07001024/* 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
Jeff Mahoney0222e652009-03-30 14:02:44 -04001027
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028 when cut item is part of directory
1029 pos_in_item - number of first deleted entry
1030 cut_size - count of deleted entries
1031 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001032void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
1033 int pos_in_item, int cut_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001035 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001041
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001042 blkh = B_BLK_HEAD(bh);
1043 nr = blkh_nr_item(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001045 /* item head of truncated item */
1046 ih = B_N_PITEM_HEAD(bh, cut_item_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001047
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001048 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001067
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001068 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001073
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001074 /* 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 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001091 /* location of the last item */
1092 last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001093
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001094 /* location of the item, which is remaining at the same place */
1095 unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001096
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001097 /* shift */
1098 memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1099 unmoved_loc - last_loc - cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001100
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001101 /* change item length */
1102 put_ih_item_len(ih, ih_item_len(ih) - cut_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001103
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001104 if (is_indirect_le_ih(ih)) {
1105 if (pos_in_item)
1106 set_ih_free_space(ih, 0);
1107 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001108
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001109 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001113
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001114 /* size, free space */
1115 set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
1116
1117 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1118
1119 if (bi->bi_parent) {
1120 struct disk_child *t_dc;
1121 t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
1122 put_dc_size(t_dc, dc_size(t_dc) - cut_size);
1123 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1124 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001125}
1126
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127/* delete del_num items from buffer starting from the first'th item */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001128static void leaf_delete_items_entirely(struct buffer_info *bi,
1129 int first, int del_num)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001131 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001138 RFALSE(bh == NULL, "10210: buffer is 0");
1139 RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001140
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001141 if (del_num == 0)
1142 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001143
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001144 blkh = B_BLK_HEAD(bh);
1145 nr = blkh_nr_item(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001146
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001147 RFALSE(first < 0 || first + del_num > nr,
1148 "10220: first=%d, number=%d, there is %d items", first, del_num,
1149 nr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001151 if (first == 0 && del_num == nr) {
1152 /* this does not work */
1153 make_empty_node(bi);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001155 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1156 return;
1157 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001159 ih = B_N_PITEM_HEAD(bh, first);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001160
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001161 /* location of unmovable item */
1162 j = (first == 0) ? bh->b_size : ih_location(ih - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001164 /* delete items */
1165 last_loc = ih_location(&(ih[nr - 1 - first]));
1166 last_removed_loc = ih_location(&(ih[del_num - 1]));
1167
1168 memmove(bh->b_data + last_loc + j - last_removed_loc,
1169 bh->b_data + last_loc, last_removed_loc - last_loc);
1170
1171 /* delete item headers */
1172 memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1173
1174 /* change item location */
1175 for (i = first; i < nr - del_num; i++)
1176 put_ih_location(&(ih[i - first]),
1177 ih_location(&(ih[i - first])) + (j -
1178 last_removed_loc));
1179
1180 /* sizes, item number */
1181 set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
1182 set_blkh_free_space(blkh,
1183 blkh_free_space(blkh) + (j - last_removed_loc +
1184 IH_SIZE * del_num));
1185
1186 do_balance_mark_leaf_dirty(bi->tb, bh, 0);
1187
1188 if (bi->bi_parent) {
1189 struct disk_child *t_dc =
1190 B_N_CHILD(bi->bi_parent, bi->bi_position);
1191 put_dc_size(t_dc,
1192 dc_size(t_dc) - (j - last_removed_loc +
1193 IH_SIZE * del_num));
1194 do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
1195 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001196}
1197
Linus Torvalds1da177e2005-04-16 15:20:36 -07001198/* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
Jeff Mahoneyeba00302009-03-30 14:02:18 -04001199void leaf_paste_entries(struct buffer_info *bi,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200 int item_num,
1201 int before,
1202 int new_entry_count,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001203 struct reiserfs_de_head *new_dehs,
1204 const char *records, int paste_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001206 struct item_head *ih;
1207 char *item;
1208 struct reiserfs_de_head *deh;
1209 char *insert_point;
1210 int i, old_entry_num;
Jeff Mahoneyeba00302009-03-30 14:02:18 -04001211 struct buffer_head *bh = bi->bi_bh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001212
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001213 if (new_entry_count == 0)
1214 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001216 ih = B_N_PITEM_HEAD(bh, item_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001217
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001218 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001223
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001224 /* first byte of dest item */
1225 item = bh->b_data + ih_location(ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001226
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001227 /* entry head array */
1228 deh = B_I_DEH(bh, ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001229
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001230 /* 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001235
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001236 /* 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));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001241
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001242 /* 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);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001246
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001247 old_entry_num = I_ENTRY_COUNT(ih);
1248 put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001249
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001250 /* prepare space for pasted records */
1251 memmove(insert_point + paste_size, insert_point,
1252 item + (ih_item_len(ih) - paste_size) - insert_point);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001253
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001254 /* copy new records */
1255 memcpy(insert_point + DEH_SIZE * new_entry_count, records,
1256 paste_size - DEH_SIZE * new_entry_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001257
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001258 /* prepare space for new entry heads */
1259 deh += before;
1260 memmove((char *)(deh + new_entry_count), deh,
1261 insert_point - (char *)deh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001262
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001263 /* copy new entry heads */
1264 deh = (struct reiserfs_de_head *)((char *)deh);
1265 memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001266
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001267 /* 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 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001276
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001277 /* 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));
Jeff Mahoney0222e652009-03-30 14:02:44 -04001280/* memcpy (&ih->ih_key.k_offset,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001281 &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001282 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001283#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001284 {
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])))
Jeff Mahoney0030b642009-03-30 14:02:28 -04001296 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);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001301 if (next && next >= deh_location(&(deh[i])))
Jeff Mahoney0030b642009-03-30 14:02:28 -04001302 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);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001307 }
1308 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001309#endif
1310
1311}