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