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 | ||
114 | leaf_paste_entries(dest_bi->bi_bh, item_num_in_dest, | |
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 LT |
121 | |
122 | /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or | |
123 | part of it or nothing (see the return 0 below) from SOURCE to the end | |
124 | (if last_first) or beginning (!last_first) of the DEST */ | |
125 | /* returns 1 if anything was copied, else 0 */ | |
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)) | |
171 | reiserfs_panic(NULL, | |
172 | "vs-10020: leaf_copy_boundary_item: " | |
173 | "last unformatted node must be filled entirely (%h)", | |
174 | ih); | |
175 | } | |
1da177e4 | 176 | #endif |
1da177e4 | 177 | |
bd4c625c LT |
178 | /* merge first item (or its part) of src buffer with the last |
179 | item of dest buffer. Both are of the same file */ | |
180 | leaf_paste_in_buffer(dest_bi, | |
181 | dest_nr_item - 1, ih_item_len(dih), | |
182 | bytes_or_entries, B_I_PITEM(src, ih), 0); | |
183 | ||
184 | if (is_indirect_le_ih(dih)) { | |
185 | RFALSE(get_ih_free_space(dih), | |
186 | "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space", | |
187 | ih); | |
188 | if (bytes_or_entries == ih_item_len(ih)) | |
189 | set_ih_free_space(dih, get_ih_free_space(ih)); | |
190 | } | |
191 | ||
192 | return 1; | |
193 | } | |
194 | ||
195 | /* copy boundary item to right (last_first == LAST_TO_FIRST) */ | |
196 | ||
197 | /* ( DEST is empty or last item of SOURCE and first item of DEST | |
198 | are the items of different object or of different types ) | |
199 | */ | |
200 | src_nr_item = B_NR_ITEMS(src); | |
201 | ih = B_N_PITEM_HEAD(src, src_nr_item - 1); | |
202 | dih = B_N_PITEM_HEAD(dest, 0); | |
203 | ||
204 | if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size)) | |
205 | return 0; | |
206 | ||
207 | if (is_direntry_le_ih(ih)) { | |
208 | if (bytes_or_entries == -1) | |
209 | /* bytes_or_entries = entries number in last item body of SOURCE */ | |
210 | bytes_or_entries = ih_entry_count(ih); | |
211 | ||
212 | leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST, | |
213 | src_nr_item - 1, | |
214 | ih_entry_count(ih) - bytes_or_entries, | |
215 | bytes_or_entries); | |
216 | return 1; | |
217 | } | |
218 | ||
219 | /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST; | |
220 | part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST; | |
221 | don't create new item header | |
222 | */ | |
223 | ||
224 | RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih), | |
225 | "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)", | |
226 | ih); | |
227 | ||
228 | if (bytes_or_entries == -1) { | |
229 | /* bytes_or_entries = length of last item body of SOURCE */ | |
230 | bytes_or_entries = ih_item_len(ih); | |
231 | ||
232 | RFALSE(le_ih_k_offset(dih) != | |
233 | le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size), | |
234 | "vs-10050: items %h and %h do not match", ih, dih); | |
235 | ||
236 | /* change first item key of the DEST */ | |
237 | set_le_ih_k_offset(dih, le_ih_k_offset(ih)); | |
238 | ||
239 | /* item becomes non-mergeable */ | |
240 | /* or mergeable if left item was */ | |
241 | set_le_ih_k_type(dih, le_ih_k_type(ih)); | |
242 | } else { | |
243 | /* merge to right only part of item */ | |
244 | RFALSE(ih_item_len(ih) <= bytes_or_entries, | |
245 | "vs-10060: no so much bytes %lu (needed %lu)", | |
246 | (unsigned long)ih_item_len(ih), | |
247 | (unsigned long)bytes_or_entries); | |
248 | ||
249 | /* change first item key of the DEST */ | |
250 | if (is_direct_le_ih(dih)) { | |
251 | RFALSE(le_ih_k_offset(dih) <= | |
252 | (unsigned long)bytes_or_entries, | |
253 | "vs-10070: dih %h, bytes_or_entries(%d)", dih, | |
254 | bytes_or_entries); | |
255 | set_le_ih_k_offset(dih, | |
256 | le_ih_k_offset(dih) - | |
257 | bytes_or_entries); | |
258 | } else { | |
259 | RFALSE(le_ih_k_offset(dih) <= | |
260 | (bytes_or_entries / UNFM_P_SIZE) * dest->b_size, | |
261 | "vs-10080: dih %h, bytes_or_entries(%d)", | |
262 | dih, | |
263 | (bytes_or_entries / UNFM_P_SIZE) * dest->b_size); | |
264 | set_le_ih_k_offset(dih, | |
265 | le_ih_k_offset(dih) - | |
266 | ((bytes_or_entries / UNFM_P_SIZE) * | |
267 | dest->b_size)); | |
268 | } | |
269 | } | |
270 | ||
271 | leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries, | |
272 | B_I_PITEM(src, | |
273 | ih) + ih_item_len(ih) - bytes_or_entries, | |
274 | 0); | |
275 | return 1; | |
276 | } | |
1da177e4 LT |
277 | |
278 | /* copy cpy_mun items from buffer src to buffer dest | |
279 | * last_first == FIRST_TO_LAST means, that we copy cpy_num items beginning from first-th item in src to tail of dest | |
280 | * last_first == LAST_TO_FIRST means, that we copy cpy_num items beginning from first-th item in src to head of dest | |
281 | */ | |
bd4c625c LT |
282 | static void leaf_copy_items_entirely(struct buffer_info *dest_bi, |
283 | struct buffer_head *src, int last_first, | |
284 | int first, int cpy_num) | |
1da177e4 | 285 | { |
bd4c625c LT |
286 | struct buffer_head *dest; |
287 | int nr, free_space; | |
288 | int dest_before; | |
289 | int last_loc, last_inserted_loc, location; | |
290 | int i, j; | |
291 | struct block_head *blkh; | |
292 | struct item_head *ih; | |
293 | ||
294 | RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST, | |
295 | "vs-10090: bad last_first parameter %d", last_first); | |
296 | RFALSE(B_NR_ITEMS(src) - first < cpy_num, | |
297 | "vs-10100: too few items in source %d, required %d from %d", | |
298 | B_NR_ITEMS(src), cpy_num, first); | |
299 | RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items"); | |
300 | RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items"); | |
301 | ||
302 | dest = dest_bi->bi_bh; | |
303 | ||
304 | RFALSE(!dest, "vs-10130: can not copy negative amount of items"); | |
305 | ||
306 | if (cpy_num == 0) | |
307 | return; | |
308 | ||
309 | blkh = B_BLK_HEAD(dest); | |
310 | nr = blkh_nr_item(blkh); | |
311 | free_space = blkh_free_space(blkh); | |
312 | ||
313 | /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */ | |
314 | dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr; | |
315 | ||
316 | /* location of head of first new item */ | |
317 | ih = B_N_PITEM_HEAD(dest, dest_before); | |
318 | ||
319 | RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE, | |
320 | "vs-10140: not enough free space for headers %d (needed %d)", | |
321 | B_FREE_SPACE(dest), cpy_num * IH_SIZE); | |
322 | ||
323 | /* prepare space for headers */ | |
324 | memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE); | |
1da177e4 | 325 | |
bd4c625c LT |
326 | /* copy item headers */ |
327 | memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE); | |
328 | ||
329 | free_space -= (IH_SIZE * cpy_num); | |
330 | set_blkh_free_space(blkh, free_space); | |
331 | ||
332 | /* location of unmovable item */ | |
333 | j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1); | |
334 | for (i = dest_before; i < nr + cpy_num; i++) { | |
335 | location -= ih_item_len(ih + i - dest_before); | |
336 | put_ih_location(ih + i - dest_before, location); | |
337 | } | |
338 | ||
339 | /* prepare space for items */ | |
340 | last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before])); | |
341 | last_inserted_loc = ih_location(&(ih[cpy_num - 1])); | |
342 | ||
343 | /* check free space */ | |
344 | RFALSE(free_space < j - last_inserted_loc, | |
345 | "vs-10150: not enough free space for items %d (needed %d)", | |
346 | free_space, j - last_inserted_loc); | |
347 | ||
348 | memmove(dest->b_data + last_loc, | |
349 | dest->b_data + last_loc + j - last_inserted_loc, | |
350 | last_inserted_loc - last_loc); | |
351 | ||
352 | /* copy items */ | |
353 | memcpy(dest->b_data + last_inserted_loc, | |
354 | B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc); | |
355 | ||
356 | /* sizes, item number */ | |
357 | set_blkh_nr_item(blkh, nr + cpy_num); | |
358 | set_blkh_free_space(blkh, free_space - (j - last_inserted_loc)); | |
359 | ||
360 | do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0); | |
361 | ||
362 | if (dest_bi->bi_parent) { | |
363 | struct disk_child *t_dc; | |
364 | t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position); | |
365 | RFALSE(dc_block_number(t_dc) != dest->b_blocknr, | |
366 | "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu", | |
367 | (long unsigned)dest->b_blocknr, | |
368 | (long unsigned)dc_block_number(t_dc)); | |
369 | put_dc_size(t_dc, | |
370 | dc_size(t_dc) + (j - last_inserted_loc + | |
371 | IH_SIZE * cpy_num)); | |
372 | ||
373 | do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent, | |
374 | 0); | |
375 | } | |
376 | } | |
1da177e4 LT |
377 | |
378 | /* This function splits the (liquid) item into two items (useful when | |
379 | shifting part of an item into another node.) */ | |
bd4c625c LT |
380 | static void leaf_item_bottle(struct buffer_info *dest_bi, |
381 | struct buffer_head *src, int last_first, | |
382 | int item_num, int cpy_bytes) | |
1da177e4 | 383 | { |
bd4c625c LT |
384 | struct buffer_head *dest = dest_bi->bi_bh; |
385 | struct item_head *ih; | |
386 | ||
387 | RFALSE(cpy_bytes == -1, | |
388 | "vs-10170: bytes == - 1 means: do not split item"); | |
389 | ||
390 | if (last_first == FIRST_TO_LAST) { | |
391 | /* if ( if item in position item_num in buffer SOURCE is directory item ) */ | |
392 | if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num))) | |
393 | leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, | |
394 | item_num, 0, cpy_bytes); | |
395 | else { | |
396 | struct item_head n_ih; | |
397 | ||
398 | /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST | |
399 | part defined by 'cpy_bytes'; create new item header; change old item_header (????); | |
400 | n_ih = new item_header; | |
401 | */ | |
402 | memcpy(&n_ih, ih, IH_SIZE); | |
403 | put_ih_item_len(&n_ih, cpy_bytes); | |
404 | if (is_indirect_le_ih(ih)) { | |
405 | RFALSE(cpy_bytes == ih_item_len(ih) | |
406 | && get_ih_free_space(ih), | |
407 | "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)", | |
408 | (long unsigned)get_ih_free_space(ih)); | |
409 | set_ih_free_space(&n_ih, 0); | |
410 | } | |
411 | ||
412 | RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size), | |
413 | "vs-10190: bad mergeability of item %h", ih); | |
414 | n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */ | |
415 | leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih, | |
416 | B_N_PITEM(src, item_num), 0); | |
417 | } | |
418 | } else { | |
419 | /* if ( if item in position item_num in buffer SOURCE is directory item ) */ | |
420 | if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num))) | |
421 | leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST, | |
422 | item_num, | |
423 | I_ENTRY_COUNT(ih) - cpy_bytes, | |
424 | cpy_bytes); | |
425 | else { | |
426 | struct item_head n_ih; | |
427 | ||
428 | /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST | |
429 | part defined by 'cpy_bytes'; create new item header; | |
430 | n_ih = new item_header; | |
431 | */ | |
432 | memcpy(&n_ih, ih, SHORT_KEY_SIZE); | |
433 | ||
434 | n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */ | |
435 | ||
436 | if (is_direct_le_ih(ih)) { | |
437 | set_le_ih_k_offset(&n_ih, | |
438 | le_ih_k_offset(ih) + | |
439 | ih_item_len(ih) - cpy_bytes); | |
440 | set_le_ih_k_type(&n_ih, TYPE_DIRECT); | |
441 | set_ih_free_space(&n_ih, MAX_US_INT); | |
442 | } else { | |
443 | /* indirect item */ | |
444 | RFALSE(!cpy_bytes && get_ih_free_space(ih), | |
445 | "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended"); | |
446 | set_le_ih_k_offset(&n_ih, | |
447 | le_ih_k_offset(ih) + | |
448 | (ih_item_len(ih) - | |
449 | cpy_bytes) / UNFM_P_SIZE * | |
450 | dest->b_size); | |
451 | set_le_ih_k_type(&n_ih, TYPE_INDIRECT); | |
452 | set_ih_free_space(&n_ih, get_ih_free_space(ih)); | |
453 | } | |
454 | ||
455 | /* set item length */ | |
456 | put_ih_item_len(&n_ih, cpy_bytes); | |
457 | ||
458 | n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */ | |
459 | ||
460 | leaf_insert_into_buf(dest_bi, 0, &n_ih, | |
461 | B_N_PITEM(src, | |
462 | item_num) + | |
463 | ih_item_len(ih) - cpy_bytes, 0); | |
464 | } | |
1da177e4 | 465 | } |
1da177e4 LT |
466 | } |
467 | ||
1da177e4 LT |
468 | /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST. |
469 | If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST. | |
470 | From last item copy cpy_num bytes for regular item and cpy_num directory entries for | |
471 | directory item. */ | |
bd4c625c LT |
472 | static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src, |
473 | int last_first, int cpy_num, int cpy_bytes) | |
1da177e4 | 474 | { |
bd4c625c LT |
475 | struct buffer_head *dest; |
476 | int pos, i, src_nr_item, bytes; | |
477 | ||
478 | dest = dest_bi->bi_bh; | |
479 | RFALSE(!dest || !src, "vs-10210: !dest || !src"); | |
480 | RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST, | |
481 | "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST"); | |
482 | RFALSE(B_NR_ITEMS(src) < cpy_num, | |
483 | "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src), | |
484 | cpy_num); | |
485 | RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num); | |
486 | ||
487 | if (cpy_num == 0) | |
488 | return 0; | |
489 | ||
490 | if (last_first == FIRST_TO_LAST) { | |
491 | /* copy items to left */ | |
492 | pos = 0; | |
493 | if (cpy_num == 1) | |
494 | bytes = cpy_bytes; | |
495 | else | |
496 | bytes = -1; | |
497 | ||
498 | /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */ | |
499 | i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes); | |
500 | cpy_num -= i; | |
501 | if (cpy_num == 0) | |
502 | return i; | |
503 | pos += i; | |
504 | if (cpy_bytes == -1) | |
505 | /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */ | |
506 | leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST, | |
507 | pos, cpy_num); | |
508 | else { | |
509 | /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */ | |
510 | leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST, | |
511 | pos, cpy_num - 1); | |
512 | ||
513 | /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */ | |
514 | leaf_item_bottle(dest_bi, src, FIRST_TO_LAST, | |
515 | cpy_num + pos - 1, cpy_bytes); | |
516 | } | |
517 | } else { | |
518 | /* copy items to right */ | |
519 | src_nr_item = B_NR_ITEMS(src); | |
520 | if (cpy_num == 1) | |
521 | bytes = cpy_bytes; | |
522 | else | |
523 | bytes = -1; | |
524 | ||
525 | /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */ | |
526 | i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes); | |
527 | ||
528 | cpy_num -= i; | |
529 | if (cpy_num == 0) | |
530 | return i; | |
531 | ||
532 | pos = src_nr_item - cpy_num - i; | |
533 | if (cpy_bytes == -1) { | |
534 | /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */ | |
535 | leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST, | |
536 | pos, cpy_num); | |
537 | } else { | |
538 | /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */ | |
539 | leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST, | |
540 | pos + 1, cpy_num - 1); | |
541 | ||
542 | /* copy part of the item which number is pos to the begin of the DEST */ | |
543 | leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos, | |
544 | cpy_bytes); | |
545 | } | |
546 | } | |
547 | return i; | |
1da177e4 LT |
548 | } |
549 | ||
1da177e4 LT |
550 | /* there are types of coping: from S[0] to L[0], from S[0] to R[0], |
551 | from R[0] to L[0]. for each of these we have to define parent and | |
552 | positions of destination and source buffers */ | |
bd4c625c LT |
553 | static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb, |
554 | struct buffer_info *dest_bi, | |
555 | struct buffer_info *src_bi, | |
556 | int *first_last, | |
557 | struct buffer_head *Snew) | |
1da177e4 | 558 | { |
bd4c625c LT |
559 | memset(dest_bi, 0, sizeof(struct buffer_info)); |
560 | memset(src_bi, 0, sizeof(struct buffer_info)); | |
561 | ||
562 | /* define dest, src, dest parent, dest position */ | |
563 | switch (shift_mode) { | |
564 | case LEAF_FROM_S_TO_L: /* it is used in leaf_shift_left */ | |
565 | src_bi->tb = tb; | |
566 | src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path); | |
567 | src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0); | |
568 | src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); /* src->b_item_order */ | |
569 | dest_bi->tb = tb; | |
570 | dest_bi->bi_bh = tb->L[0]; | |
571 | dest_bi->bi_parent = tb->FL[0]; | |
572 | dest_bi->bi_position = get_left_neighbor_position(tb, 0); | |
573 | *first_last = FIRST_TO_LAST; | |
574 | break; | |
575 | ||
576 | case LEAF_FROM_S_TO_R: /* it is used in leaf_shift_right */ | |
577 | src_bi->tb = tb; | |
578 | src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path); | |
579 | src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0); | |
580 | src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); | |
581 | dest_bi->tb = tb; | |
582 | dest_bi->bi_bh = tb->R[0]; | |
583 | dest_bi->bi_parent = tb->FR[0]; | |
584 | dest_bi->bi_position = get_right_neighbor_position(tb, 0); | |
585 | *first_last = LAST_TO_FIRST; | |
586 | break; | |
587 | ||
588 | case LEAF_FROM_R_TO_L: /* it is used in balance_leaf_when_delete */ | |
589 | src_bi->tb = tb; | |
590 | src_bi->bi_bh = tb->R[0]; | |
591 | src_bi->bi_parent = tb->FR[0]; | |
592 | src_bi->bi_position = get_right_neighbor_position(tb, 0); | |
593 | dest_bi->tb = tb; | |
594 | dest_bi->bi_bh = tb->L[0]; | |
595 | dest_bi->bi_parent = tb->FL[0]; | |
596 | dest_bi->bi_position = get_left_neighbor_position(tb, 0); | |
597 | *first_last = FIRST_TO_LAST; | |
598 | break; | |
599 | ||
600 | case LEAF_FROM_L_TO_R: /* it is used in balance_leaf_when_delete */ | |
601 | src_bi->tb = tb; | |
602 | src_bi->bi_bh = tb->L[0]; | |
603 | src_bi->bi_parent = tb->FL[0]; | |
604 | src_bi->bi_position = get_left_neighbor_position(tb, 0); | |
605 | dest_bi->tb = tb; | |
606 | dest_bi->bi_bh = tb->R[0]; | |
607 | dest_bi->bi_parent = tb->FR[0]; | |
608 | dest_bi->bi_position = get_right_neighbor_position(tb, 0); | |
609 | *first_last = LAST_TO_FIRST; | |
610 | break; | |
611 | ||
612 | case LEAF_FROM_S_TO_SNEW: | |
613 | src_bi->tb = tb; | |
614 | src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path); | |
615 | src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0); | |
616 | src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); | |
617 | dest_bi->tb = tb; | |
618 | dest_bi->bi_bh = Snew; | |
619 | dest_bi->bi_parent = NULL; | |
620 | dest_bi->bi_position = 0; | |
621 | *first_last = LAST_TO_FIRST; | |
622 | break; | |
623 | ||
624 | default: | |
625 | reiserfs_panic(NULL, | |
626 | "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)", | |
627 | shift_mode); | |
628 | } | |
629 | RFALSE(src_bi->bi_bh == 0 || dest_bi->bi_bh == 0, | |
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"); | |
677 | reiserfs_panic(tb->tb_sb, | |
678 | "vs-10275: leaf_shift_left: balance condition corrupted (%c)", | |
679 | tb->tb_mode); | |
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 LT |
726 | /* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR. |
727 | If not. | |
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 | ||
786 | /* delete the part of the last item of the bh | |
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 LT |
867 | |
868 | /* paste paste_size bytes to affected_item_num-th item. | |
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 LT |
891 | if (zeros_number > paste_size) { |
892 | print_cur_tb("10177"); | |
893 | reiserfs_panic(NULL, | |
894 | "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d", | |
895 | zeros_number, paste_size); | |
896 | } | |
897 | #endif /* CONFIG_REISERFS_CHECK */ | |
898 | ||
899 | /* item to be appended */ | |
900 | ih = B_N_PITEM_HEAD(bh, affected_item_num); | |
901 | ||
902 | last_loc = ih_location(&(ih[nr - affected_item_num - 1])); | |
903 | unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size; | |
904 | ||
905 | /* prepare space */ | |
906 | memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc, | |
907 | unmoved_loc - last_loc); | |
908 | ||
909 | /* change locations */ | |
910 | for (i = affected_item_num; i < nr; i++) | |
911 | put_ih_location(&(ih[i - affected_item_num]), | |
912 | ih_location(&(ih[i - affected_item_num])) - | |
913 | paste_size); | |
914 | ||
915 | if (body) { | |
916 | if (!is_direntry_le_ih(ih)) { | |
917 | if (!pos_in_item) { | |
918 | /* shift data to right */ | |
919 | memmove(bh->b_data + ih_location(ih) + | |
920 | paste_size, | |
921 | bh->b_data + ih_location(ih), | |
922 | ih_item_len(ih)); | |
923 | /* paste data in the head of item */ | |
924 | memset(bh->b_data + ih_location(ih), 0, | |
925 | zeros_number); | |
926 | memcpy(bh->b_data + ih_location(ih) + | |
927 | zeros_number, body, | |
928 | paste_size - zeros_number); | |
929 | } else { | |
930 | memset(bh->b_data + unmoved_loc - paste_size, 0, | |
931 | zeros_number); | |
932 | memcpy(bh->b_data + unmoved_loc - paste_size + | |
933 | zeros_number, body, | |
934 | paste_size - zeros_number); | |
935 | } | |
936 | } | |
937 | } else | |
938 | memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size); | |
939 | ||
940 | put_ih_item_len(ih, ih_item_len(ih) + paste_size); | |
941 | ||
942 | /* change free space */ | |
943 | set_blkh_free_space(blkh, free_space - paste_size); | |
944 | ||
945 | do_balance_mark_leaf_dirty(bi->tb, bh, 0); | |
946 | ||
947 | if (bi->bi_parent) { | |
948 | struct disk_child *t_dc = | |
949 | B_N_CHILD(bi->bi_parent, bi->bi_position); | |
950 | put_dc_size(t_dc, dc_size(t_dc) + paste_size); | |
951 | do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0); | |
1da177e4 | 952 | } |
1da177e4 LT |
953 | } |
954 | ||
1da177e4 LT |
955 | /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item |
956 | does not have free space, so it moves DEHs and remaining records as | |
957 | necessary. Return value is size of removed part of directory item | |
958 | in bytes. */ | |
bd4c625c LT |
959 | static int leaf_cut_entries(struct buffer_head *bh, |
960 | struct item_head *ih, int from, int del_count) | |
1da177e4 | 961 | { |
bd4c625c LT |
962 | char *item; |
963 | struct reiserfs_de_head *deh; | |
964 | int prev_record_offset; /* offset of record, that is (from-1)th */ | |
965 | char *prev_record; /* */ | |
966 | int cut_records_len; /* length of all removed records */ | |
967 | int i; | |
968 | ||
969 | /* make sure, that item is directory and there are enough entries to | |
970 | remove */ | |
971 | RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item"); | |
972 | RFALSE(I_ENTRY_COUNT(ih) < from + del_count, | |
973 | "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d", | |
974 | I_ENTRY_COUNT(ih), from, del_count); | |
975 | ||
976 | if (del_count == 0) | |
977 | return 0; | |
978 | ||
979 | /* first byte of item */ | |
980 | item = bh->b_data + ih_location(ih); | |
981 | ||
982 | /* entry head array */ | |
983 | deh = B_I_DEH(bh, ih); | |
984 | ||
985 | /* first byte of remaining entries, those are BEFORE cut entries | |
986 | (prev_record) and length of all removed records (cut_records_len) */ | |
987 | prev_record_offset = | |
988 | (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih)); | |
989 | cut_records_len = prev_record_offset /*from_record */ - | |
990 | deh_location(&(deh[from + del_count - 1])); | |
991 | prev_record = item + prev_record_offset; | |
992 | ||
993 | /* adjust locations of remaining entries */ | |
994 | for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--) | |
995 | put_deh_location(&(deh[i]), | |
996 | deh_location(&deh[i]) - | |
997 | (DEH_SIZE * del_count)); | |
998 | ||
999 | for (i = 0; i < from; i++) | |
1000 | put_deh_location(&(deh[i]), | |
1001 | deh_location(&deh[i]) - (DEH_SIZE * del_count + | |
1002 | cut_records_len)); | |
1003 | ||
1004 | put_ih_entry_count(ih, ih_entry_count(ih) - del_count); | |
1005 | ||
1006 | /* shift entry head array and entries those are AFTER removed entries */ | |
1007 | memmove((char *)(deh + from), | |
1008 | deh + from + del_count, | |
1009 | prev_record - cut_records_len - (char *)(deh + from + | |
1010 | del_count)); | |
1011 | ||
1012 | /* shift records, those are BEFORE removed entries */ | |
1013 | memmove(prev_record - cut_records_len - DEH_SIZE * del_count, | |
1014 | prev_record, item + ih_item_len(ih) - prev_record); | |
1015 | ||
1016 | return DEH_SIZE * del_count + cut_records_len; | |
1da177e4 LT |
1017 | } |
1018 | ||
1da177e4 LT |
1019 | /* when cut item is part of regular file |
1020 | pos_in_item - first byte that must be cut | |
1021 | cut_size - number of bytes to be cut beginning from pos_in_item | |
1022 | ||
1023 | when cut item is part of directory | |
1024 | pos_in_item - number of first deleted entry | |
1025 | cut_size - count of deleted entries | |
1026 | */ | |
bd4c625c LT |
1027 | void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num, |
1028 | int pos_in_item, int cut_size) | |
1da177e4 | 1029 | { |
bd4c625c LT |
1030 | int nr; |
1031 | struct buffer_head *bh = bi->bi_bh; | |
1032 | struct block_head *blkh; | |
1033 | struct item_head *ih; | |
1034 | int last_loc, unmoved_loc; | |
1035 | int i; | |
1036 | ||
1037 | blkh = B_BLK_HEAD(bh); | |
1038 | nr = blkh_nr_item(blkh); | |
1039 | ||
1040 | /* item head of truncated item */ | |
1041 | ih = B_N_PITEM_HEAD(bh, cut_item_num); | |
1042 | ||
1043 | if (is_direntry_le_ih(ih)) { | |
1044 | /* first cut entry () */ | |
1045 | cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size); | |
1046 | if (pos_in_item == 0) { | |
1047 | /* change key */ | |
1048 | RFALSE(cut_item_num, | |
1049 | "when 0-th enrty of item is cut, that item must be first in the node, not %d-th", | |
1050 | cut_item_num); | |
1051 | /* change item key by key of first entry in the item */ | |
1052 | set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih))); | |
1053 | /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */ | |
1054 | } | |
1055 | } else { | |
1056 | /* item is direct or indirect */ | |
1057 | RFALSE(is_statdata_le_ih(ih), "10195: item is stat data"); | |
1058 | RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih), | |
1059 | "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)", | |
1060 | (long unsigned)pos_in_item, (long unsigned)cut_size, | |
1061 | (long unsigned)ih_item_len(ih)); | |
1062 | ||
1063 | /* shift item body to left if cut is from the head of item */ | |
1064 | if (pos_in_item == 0) { | |
1065 | memmove(bh->b_data + ih_location(ih), | |
1066 | bh->b_data + ih_location(ih) + cut_size, | |
1067 | ih_item_len(ih) - cut_size); | |
1068 | ||
1069 | /* change key of item */ | |
1070 | if (is_direct_le_ih(ih)) | |
1071 | set_le_ih_k_offset(ih, | |
1072 | le_ih_k_offset(ih) + | |
1073 | cut_size); | |
1074 | else { | |
1075 | set_le_ih_k_offset(ih, | |
1076 | le_ih_k_offset(ih) + | |
1077 | (cut_size / UNFM_P_SIZE) * | |
1078 | bh->b_size); | |
1079 | RFALSE(ih_item_len(ih) == cut_size | |
1080 | && get_ih_free_space(ih), | |
1081 | "10205: invalid ih_free_space (%h)", ih); | |
1082 | } | |
1083 | } | |
1084 | } | |
1085 | ||
1086 | /* location of the last item */ | |
1087 | last_loc = ih_location(&(ih[nr - cut_item_num - 1])); | |
1088 | ||
1089 | /* location of the item, which is remaining at the same place */ | |
1090 | unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size; | |
1091 | ||
1092 | /* shift */ | |
1093 | memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc, | |
1094 | unmoved_loc - last_loc - cut_size); | |
1095 | ||
1096 | /* change item length */ | |
1097 | put_ih_item_len(ih, ih_item_len(ih) - cut_size); | |
1da177e4 | 1098 | |
bd4c625c LT |
1099 | if (is_indirect_le_ih(ih)) { |
1100 | if (pos_in_item) | |
1101 | set_ih_free_space(ih, 0); | |
1102 | } | |
1103 | ||
1104 | /* change locations */ | |
1105 | for (i = cut_item_num; i < nr; i++) | |
1106 | put_ih_location(&(ih[i - cut_item_num]), | |
1107 | ih_location(&ih[i - cut_item_num]) + cut_size); | |
1108 | ||
1109 | /* size, free space */ | |
1110 | set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size); | |
1111 | ||
1112 | do_balance_mark_leaf_dirty(bi->tb, bh, 0); | |
1113 | ||
1114 | if (bi->bi_parent) { | |
1115 | struct disk_child *t_dc; | |
1116 | t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position); | |
1117 | put_dc_size(t_dc, dc_size(t_dc) - cut_size); | |
1118 | do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0); | |
1119 | } | |
1120 | } | |
1da177e4 LT |
1121 | |
1122 | /* delete del_num items from buffer starting from the first'th item */ | |
bd4c625c LT |
1123 | static void leaf_delete_items_entirely(struct buffer_info *bi, |
1124 | int first, int del_num) | |
1da177e4 | 1125 | { |
bd4c625c LT |
1126 | struct buffer_head *bh = bi->bi_bh; |
1127 | int nr; | |
1128 | int i, j; | |
1129 | int last_loc, last_removed_loc; | |
1130 | struct block_head *blkh; | |
1131 | struct item_head *ih; | |
1132 | ||
1133 | RFALSE(bh == NULL, "10210: buffer is 0"); | |
1134 | RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num); | |
1135 | ||
1136 | if (del_num == 0) | |
1137 | return; | |
1138 | ||
1139 | blkh = B_BLK_HEAD(bh); | |
1140 | nr = blkh_nr_item(blkh); | |
1da177e4 | 1141 | |
bd4c625c LT |
1142 | RFALSE(first < 0 || first + del_num > nr, |
1143 | "10220: first=%d, number=%d, there is %d items", first, del_num, | |
1144 | nr); | |
1145 | ||
1146 | if (first == 0 && del_num == nr) { | |
1147 | /* this does not work */ | |
1148 | make_empty_node(bi); | |
1149 | ||
1150 | do_balance_mark_leaf_dirty(bi->tb, bh, 0); | |
1151 | return; | |
1152 | } | |
1da177e4 | 1153 | |
bd4c625c | 1154 | ih = B_N_PITEM_HEAD(bh, first); |
1da177e4 | 1155 | |
bd4c625c LT |
1156 | /* location of unmovable item */ |
1157 | j = (first == 0) ? bh->b_size : ih_location(ih - 1); | |
1da177e4 | 1158 | |
bd4c625c LT |
1159 | /* delete items */ |
1160 | last_loc = ih_location(&(ih[nr - 1 - first])); | |
1161 | last_removed_loc = ih_location(&(ih[del_num - 1])); | |
1162 | ||
1163 | memmove(bh->b_data + last_loc + j - last_removed_loc, | |
1164 | bh->b_data + last_loc, last_removed_loc - last_loc); | |
1165 | ||
1166 | /* delete item headers */ | |
1167 | memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE); | |
1168 | ||
1169 | /* change item location */ | |
1170 | for (i = first; i < nr - del_num; i++) | |
1171 | put_ih_location(&(ih[i - first]), | |
1172 | ih_location(&(ih[i - first])) + (j - | |
1173 | last_removed_loc)); | |
1174 | ||
1175 | /* sizes, item number */ | |
1176 | set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num); | |
1177 | set_blkh_free_space(blkh, | |
1178 | blkh_free_space(blkh) + (j - last_removed_loc + | |
1179 | IH_SIZE * del_num)); | |
1180 | ||
1181 | do_balance_mark_leaf_dirty(bi->tb, bh, 0); | |
1182 | ||
1183 | if (bi->bi_parent) { | |
1184 | struct disk_child *t_dc = | |
1185 | B_N_CHILD(bi->bi_parent, bi->bi_position); | |
1186 | put_dc_size(t_dc, | |
1187 | dc_size(t_dc) - (j - last_removed_loc + | |
1188 | IH_SIZE * del_num)); | |
1189 | do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0); | |
1190 | } | |
1191 | } | |
1da177e4 LT |
1192 | |
1193 | /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */ | |
bd4c625c | 1194 | void leaf_paste_entries(struct buffer_head *bh, |
1da177e4 LT |
1195 | int item_num, |
1196 | int before, | |
1197 | int new_entry_count, | |
bd4c625c LT |
1198 | struct reiserfs_de_head *new_dehs, |
1199 | const char *records, int paste_size) | |
1da177e4 | 1200 | { |
bd4c625c LT |
1201 | struct item_head *ih; |
1202 | char *item; | |
1203 | struct reiserfs_de_head *deh; | |
1204 | char *insert_point; | |
1205 | int i, old_entry_num; | |
1206 | ||
1207 | if (new_entry_count == 0) | |
1208 | return; | |
1209 | ||
1210 | ih = B_N_PITEM_HEAD(bh, item_num); | |
1211 | ||
1212 | /* make sure, that item is directory, and there are enough records in it */ | |
1213 | RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item"); | |
1214 | RFALSE(I_ENTRY_COUNT(ih) < before, | |
1215 | "10230: there are no entry we paste entries before. entry_count = %d, before = %d", | |
1216 | I_ENTRY_COUNT(ih), before); | |
1217 | ||
1218 | /* first byte of dest item */ | |
1219 | item = bh->b_data + ih_location(ih); | |
1220 | ||
1221 | /* entry head array */ | |
1222 | deh = B_I_DEH(bh, ih); | |
1223 | ||
1224 | /* new records will be pasted at this point */ | |
1225 | insert_point = | |
1226 | item + | |
1227 | (before ? deh_location(&(deh[before - 1])) | |
1228 | : (ih_item_len(ih) - paste_size)); | |
1229 | ||
1230 | /* adjust locations of records that will be AFTER new records */ | |
1231 | for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--) | |
1232 | put_deh_location(&(deh[i]), | |
1233 | deh_location(&(deh[i])) + | |
1234 | (DEH_SIZE * new_entry_count)); | |
1235 | ||
1236 | /* adjust locations of records that will be BEFORE new records */ | |
1237 | for (i = 0; i < before; i++) | |
1238 | put_deh_location(&(deh[i]), | |
1239 | deh_location(&(deh[i])) + paste_size); | |
1240 | ||
1241 | old_entry_num = I_ENTRY_COUNT(ih); | |
1242 | put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count); | |
1243 | ||
1244 | /* prepare space for pasted records */ | |
1245 | memmove(insert_point + paste_size, insert_point, | |
1246 | item + (ih_item_len(ih) - paste_size) - insert_point); | |
1247 | ||
1248 | /* copy new records */ | |
1249 | memcpy(insert_point + DEH_SIZE * new_entry_count, records, | |
1250 | paste_size - DEH_SIZE * new_entry_count); | |
1251 | ||
1252 | /* prepare space for new entry heads */ | |
1253 | deh += before; | |
1254 | memmove((char *)(deh + new_entry_count), deh, | |
1255 | insert_point - (char *)deh); | |
1256 | ||
1257 | /* copy new entry heads */ | |
1258 | deh = (struct reiserfs_de_head *)((char *)deh); | |
1259 | memcpy(deh, new_dehs, DEH_SIZE * new_entry_count); | |
1260 | ||
1261 | /* set locations of new records */ | |
1262 | for (i = 0; i < new_entry_count; i++) { | |
1263 | put_deh_location(&(deh[i]), | |
1264 | deh_location(&(deh[i])) + | |
1265 | (-deh_location | |
1266 | (&(new_dehs[new_entry_count - 1])) + | |
1267 | insert_point + DEH_SIZE * new_entry_count - | |
1268 | item)); | |
1269 | } | |
1270 | ||
1271 | /* change item key if necessary (when we paste before 0-th entry */ | |
1272 | if (!before) { | |
1273 | set_le_ih_k_offset(ih, deh_offset(new_dehs)); | |
1da177e4 LT |
1274 | /* memcpy (&ih->ih_key.k_offset, |
1275 | &new_dehs->deh_offset, SHORT_KEY_SIZE);*/ | |
bd4c625c | 1276 | } |
1da177e4 | 1277 | #ifdef CONFIG_REISERFS_CHECK |
bd4c625c LT |
1278 | { |
1279 | int prev, next; | |
1280 | /* check record locations */ | |
1281 | deh = B_I_DEH(bh, ih); | |
1282 | for (i = 0; i < I_ENTRY_COUNT(ih); i++) { | |
1283 | next = | |
1284 | (i < | |
1285 | I_ENTRY_COUNT(ih) - | |
1286 | 1) ? deh_location(&(deh[i + 1])) : 0; | |
1287 | prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0; | |
1288 | ||
1289 | if (prev && prev <= deh_location(&(deh[i]))) | |
1290 | reiserfs_warning(NULL, | |
1291 | "vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)", | |
1292 | ih, deh + i - 1, i, deh + i); | |
1293 | if (next && next >= deh_location(&(deh[i]))) | |
1294 | reiserfs_warning(NULL, | |
1295 | "vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)", | |
1296 | ih, i, deh + i, deh + i + 1); | |
1297 | } | |
1298 | } | |
1da177e4 LT |
1299 | #endif |
1300 | ||
1301 | } |