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(bh: 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(bh: dest, |
67 | item_num: 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(ih: &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(ih: &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, key: &new_ih.ih_key, |
98 | TYPE_DIRENTRY); |
99 | } |
100 | |
101 | /* insert item into dest buffer */ |
102 | leaf_insert_into_buf(bi: dest_bi, |
103 | before: (last_first == |
104 | LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest), |
105 | inserted_item_ih: &new_ih, NULL, zeros_number: 0); |
106 | } else { |
107 | /* prepare space for entries */ |
108 | leaf_paste_in_buffer(bi: dest_bi, |
109 | pasted_item_num: (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 | body: records, zeros_number: 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(bi: dest_bi, item_num: item_num_in_dest, |
120 | before: (last_first == |
121 | FIRST_TO_LAST) ? ih_entry_count(item_head(dest, |
122 | item_num_in_dest)) |
123 | : 0, new_entry_count: copy_count, new_dehs: 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(bh: src, item_num: 0); |
154 | dih = item_head(bh: dest, item_num: 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, source: src, FIRST_TO_LAST, item_num: 0, from: 0, |
169 | copy_count: 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(bi: dest_bi, |
200 | pasted_item_num: dest_nr_item - 1, ih_item_len(dih), |
201 | paste_size: bytes_or_entries, body: ih_item_body(bh: src, ih), zeros_number: 0); |
202 | |
203 | if (is_indirect_le_ih(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(bh: src, item_num: src_nr_item - 1); |
222 | dih = item_head(bh: dest, item_num: 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, source: src, LAST_TO_FIRST, |
236 | item_num: src_nr_item - 1, |
237 | ih_entry_count(ih) - bytes_or_entries, |
238 | copy_count: 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(ih: dih, offset: le_ih_k_offset(ih)); |
263 | |
264 | /* item becomes non-mergeable */ |
265 | /* or mergeable if left item was */ |
266 | set_le_ih_k_type(ih: dih, type: 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(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(ih: dih, |
281 | offset: le_ih_k_offset(ih: 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(ih: dih, |
290 | offset: le_ih_k_offset(ih: dih) - |
291 | ((bytes_or_entries / UNFM_P_SIZE) * |
292 | dest->b_size)); |
293 | } |
294 | } |
295 | |
296 | leaf_paste_in_buffer(bi: dest_bi, pasted_item_num: 0, pos_in_item: 0, paste_size: bytes_or_entries, |
297 | body: ih_item_body(bh: src, |
298 | ih) + ih_item_len(ih) - bytes_or_entries, |
299 | zeros_number: 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(bh: dest, item_num: 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(tb: dest_bi->tb, bh: dest, flag: 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(tb: dest_bi->tb, bh: dest_bi->bi_parent, |
406 | flag: 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(bh: src, item_num); |
430 | if (is_direntry_le_ih(ih)) |
431 | leaf_copy_dir_entries(dest_bi, source: src, FIRST_TO_LAST, |
432 | item_num, from: 0, copy_count: 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(bi: dest_bi, B_NR_ITEMS(dest), inserted_item_ih: &n_ih, |
456 | inserted_item_body: item_body(bh: src, item_num), zeros_number: 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(bh: src, item_num); |
464 | if (is_direntry_le_ih(ih)) |
465 | leaf_copy_dir_entries(dest_bi, source: src, LAST_TO_FIRST, |
466 | item_num, |
467 | ih_entry_count(ih) - cpy_bytes, |
468 | copy_count: 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(ih: &n_ih, |
485 | offset: le_ih_k_offset(ih) + |
486 | ih_item_len(ih) - cpy_bytes); |
487 | set_le_ih_k_type(ih: &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(ih: &n_ih, |
494 | offset: 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(ih: &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(bi: dest_bi, before: 0, inserted_item_ih: &n_ih, |
509 | inserted_item_body: item_body(bh: src, item_num) + |
510 | ih_item_len(ih) - cpy_bytes, zeros_number: 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_or_entries: 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 | first: 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 | first: pos, cpy_num: 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 | item_num: 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_or_entries: 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 | first: 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 | first: pos + 1, cpy_num: 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, item_num: 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, h: 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, h: 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, h: 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, h: 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, h: 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, h: 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: &dest_bi, src_bi: &src_bi, |
723 | first_last: &first_last, Snew); |
724 | |
725 | ret_value = |
726 | leaf_copy_items(dest_bi: &dest_bi, src: src_bi.bi_bh, last_first: first_last, cpy_num: mov_num, |
727 | cpy_bytes: mov_bytes); |
728 | |
729 | leaf_delete_items(cur_bi: &src_bi, last_first: first_last, |
730 | first: (first_last == |
731 | FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) - |
732 | mov_num), del_num: mov_num, del_bytes: 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, mov_num: shift_num, mov_bytes: 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(mes: "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, mov_num: shift_num, mov_bytes: 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(tb: cur_bi->tb, bh, flag: 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(bi: 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(bi: cur_bi, first, del_num: 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(bi: cur_bi, cut_item_num: 0, pos_in_item: 0, cut_size: 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(bi: cur_bi, first: first + 1, |
876 | del_num: 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(bi: cur_bi, B_NR_ITEMS(bh) - 1, |
895 | pos_in_item: len - del_bytes, cut_size: 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, item_num: 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(tb: bi->tb, bh, flag: 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(tb: bi->tb, bh: bi->bi_parent, flag: 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(mes: "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, item_num: 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(tb: bi->tb, bh, flag: 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(tb: bi->tb, bh: bi->bi_parent, flag: 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, item_num: cut_item_num); |
1160 | |
1161 | if (is_direntry_le_ih(ih)) { |
1162 | /* first cut entry () */ |
1163 | cut_size = leaf_cut_entries(bh, ih, from: pos_in_item, del_count: 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 | offset: le_ih_k_offset(ih) + |
1190 | cut_size); |
1191 | else { |
1192 | set_le_ih_k_offset(ih, |
1193 | offset: 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(tb: bi->tb, bh, flag: 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(tb: bi->tb, bh: bi->bi_parent, flag: 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(tb: bi->tb, bh, flag: 0); |
1268 | return; |
1269 | } |
1270 | |
1271 | ih = item_head(bh, item_num: 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(tb: bi->tb, bh, flag: 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(tb: bi->tb, bh: bi->bi_parent, flag: 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 | } |
1427 | |