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