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