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