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