File: /usr/src/linux/fs/reiserfs/do_balan.c
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5 /* Now we have all buffers that must be used in balancing of the tree */
6 /* Further calculations can not cause schedule(), and thus the buffer */
7 /* tree will be stable until the balancing will be finished */
8 /* balance the tree according to the analysis made before, */
9 /* and using buffers obtained after all above. */
10
11
12 /**
13 ** balance_leaf_when_delete
14 ** balance_leaf
15 ** do_balance
16 **
17 **/
18
19 #include <linux/config.h>
20 #include <asm/uaccess.h>
21 #include <linux/sched.h>
22 #include <linux/reiserfs_fs.h>
23
24 #ifdef CONFIG_REISERFS_CHECK
25
26 struct tree_balance * cur_tb = NULL; /* detects whether more than one
27 copy of tb exists as a means
28 of checking whether schedule
29 is interrupting do_balance */
30 #endif
31
32
33 inline void do_balance_mark_leaf_dirty (struct tree_balance * tb,
34 struct buffer_head * bh, int flag)
35 {
36 if (reiserfs_dont_log(tb->tb_sb)) {
37 if (!test_and_set_bit(BH_Dirty, &bh->b_state)) {
38 __mark_buffer_dirty(bh) ;
39 tb->need_balance_dirty = 1;
40 }
41 } else {
42 int windex = push_journal_writer("do_balance") ;
43 journal_mark_dirty(tb->transaction_handle, tb->transaction_handle->t_super, bh) ;
44 pop_journal_writer(windex) ;
45 }
46 }
47
48 #define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
49 #define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
50
51
52 /* summary:
53 if deleting something ( tb->insert_size[0] < 0 )
54 return(balance_leaf_when_delete()); (flag d handled here)
55 else
56 if lnum is larger than 0 we put items into the left node
57 if rnum is larger than 0 we put items into the right node
58 if snum1 is larger than 0 we put items into the new node s1
59 if snum2 is larger than 0 we put items into the new node s2
60 Note that all *num* count new items being created.
61
62 It would be easier to read balance_leaf() if each of these summary
63 lines was a separate procedure rather than being inlined. I think
64 that there are many passages here and in balance_leaf_when_delete() in
65 which two calls to one procedure can replace two passages, and it
66 might save cache space and improve software maintenance costs to do so.
67
68 Vladimir made the perceptive comment that we should offload most of
69 the decision making in this function into fix_nodes/check_balance, and
70 then create some sort of structure in tb that says what actions should
71 be performed by do_balance.
72
73 -Hans */
74
75
76
77 /* Balance leaf node in case of delete or cut: insert_size[0] < 0
78 *
79 * lnum, rnum can have values >= -1
80 * -1 means that the neighbor must be joined with S
81 * 0 means that nothing should be done with the neighbor
82 * >0 means to shift entirely or partly the specified number of items to the neighbor
83 */
84 static int balance_leaf_when_delete (struct tree_balance * tb, int flag)
85 {
86 struct buffer_head * tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
87 int item_pos = PATH_LAST_POSITION (tb->tb_path);
88 int pos_in_item = tb->tb_path->pos_in_item;
89 struct buffer_info bi;
90 int n;
91 struct item_head * ih;
92
93 #ifdef CONFIG_REISERFS_CHECK
94 if ( tb->FR[0] && B_LEVEL (tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1)
95 reiserfs_panic (tb->tb_sb,
96 "vs- 12000: balance_leaf_when_delete:level: wrong FR %z\n", tb->FR[0]);
97 if ( tb->blknum[0] > 1 )
98 reiserfs_panic (tb->tb_sb,
99 "PAP-12005: balance_leaf_when_delete: "
100 "tb->blknum == %d, can not be > 1", tb->blknum[0]);
101
102 if ( ! tb->blknum[0] && ! PATH_H_PPARENT(tb->tb_path, 0))
103 reiserfs_panic (tb->tb_sb, "PAP-12010: balance_leaf_when_delete: tree can not be empty");
104 #endif
105
106 ih = B_N_PITEM_HEAD (tbS0, item_pos);
107
108 /* Delete or truncate the item */
109
110 switch (flag) {
111 case M_DELETE: /* delete item in S[0] */
112
113 #ifdef CONFIG_REISERFS_CHECK
114 if (le16_to_cpu (ih->ih_item_len) + IH_SIZE != -tb->insert_size [0])
115 reiserfs_panic (tb->tb_sb, "vs-12013: balance_leaf_when_delete: "
116 "mode Delete, insert size %d, ih to be deleted %h", ih);
117
118 #if 0 /* rigth delim key not supported */
119 if ( ! item_pos && (! tb->L[0] || COMP_KEYS(B_PRIGHT_DELIM_KEY(tb->L[0]), B_N_PKEY(tbS0, 0))) ) {
120 print_cur_tb ("12015");
121 reiserfs_panic (tb->tb_sb, "PAP-12015: balance_leaf_when_delete: L0's rkey does not match to 1st key of S0: "
122 "rkey in L %k, first key in S0 %k, rkey in CFL %k",
123 tb->L[0] ? B_PRIGHT_DELIM_KEY(tb->L[0]) : 0,
124 B_N_PKEY(tbS0, 0),
125 tb->CFL[0] ? B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]) : 0);
126 }
127 #endif
128
129 #endif
130
131 bi.tb = tb;
132 bi.bi_bh = tbS0;
133 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
134 bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
135 leaf_delete_items (&bi, 0, item_pos, 1, -1);
136
137 if ( ! item_pos && tb->CFL[0] ) {
138 if ( B_NR_ITEMS(tbS0) ) {
139 replace_key(tb, tb->CFL[0],tb->lkey[0],tbS0,0);
140 #if 0 /* right delim key support */
141 copy_key(B_PRIGHT_DELIM_KEY(tb->L[0]), B_N_PKEY(tbS0, 0));
142 reiserfs_mark_buffer_dirty (tb->L[0], 0);
143 #endif
144 }
145 else {
146 if ( ! PATH_H_POSITION (tb->tb_path, 1) )
147 replace_key(tb, tb->CFL[0],tb->lkey[0],PATH_H_PPARENT(tb->tb_path, 0),0);
148 #if 0 /* right delim key support */
149 copy_key(B_PRIGHT_DELIM_KEY(tb->L[0]), B_PRIGHT_DELIM_KEY(tbS0));
150 reiserfs_mark_buffer_dirty (tb->L[0], 0);
151 #endif
152 }
153 }
154
155 #ifdef CONFIG_REISERFS_CHECK
156 #if 0
157 if (! item_pos && (!tb->CFL[0] || !tb->L[0]))
158 #endif
159 if (! item_pos && !tb->CFL[0])
160 reiserfs_panic (tb->tb_sb, "PAP-12020: balance_leaf_when_delete: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0], tb->L[0]);
161 #endif
162
163 break;
164
165 case M_CUT: { /* cut item in S[0] */
166 bi.tb = tb;
167 bi.bi_bh = tbS0;
168 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
169 bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
170 if (is_direntry_le_ih (ih)) {
171
172 #ifdef CONFIG_REISERFS_CHECK
173 #if 0 /* right delim key support */
174 if ( ! item_pos && ! pos_in_item && (! tb->L[0] || COMP_KEYS(B_PRIGHT_DELIM_KEY(tb->L[0]),
175 B_N_PKEY(tbS0, 0))) )
176 reiserfs_panic(tb->tb_sb, "PAP-12025: balance_leaf_when_delete: illegal right delimiting key");
177 #endif
178 #endif
179
180 /* UFS unlink semantics are such that you can only delete one directory entry at a time. */
181 /* when we cut a directory tb->insert_size[0] means number of entries to be cut (always 1) */
182 tb->insert_size[0] = -1;
183 leaf_cut_from_buffer (&bi, item_pos, pos_in_item, -tb->insert_size[0]);
184
185 #ifdef CONFIG_REISERFS_CHECK
186 if (! item_pos && ! pos_in_item && ! tb->CFL[0])
187 reiserfs_panic (tb->tb_sb, "PAP-12030: balance_leaf_when_delete: can not change delimiting key. CFL[0]=%p", tb->CFL[0]);
188 #endif /* CONFIG_REISERFS_CHECK */
189
190 if ( ! item_pos && ! pos_in_item && tb->CFL[0] ) {
191 replace_key(tb, tb->CFL[0],tb->lkey[0],tbS0,0);
192 #if 0/* right delim key support */
193 copy_key(B_PRIGHT_DELIM_KEY(tb->L[0]), B_N_PKEY(tbS0, 0));
194 reiserfs_mark_buffer_dirty (tb->L[0], 0);
195 #endif
196 }
197 } else {
198 leaf_cut_from_buffer (&bi, item_pos, pos_in_item, -tb->insert_size[0]);
199
200 #ifdef CONFIG_REISERFS_CHECK
201 if (! ih->ih_item_len)
202 reiserfs_panic (tb->tb_sb, "PAP-12035: balance_leaf_when_delete: cut must leave non-zero dynamic length of item");
203 #endif /* CONFIG_REISERFS_CHECK */
204 }
205 break;
206 }
207
208 default:
209 print_cur_tb ("12040");
210 reiserfs_panic (tb->tb_sb, "PAP-12040: balance_leaf_when_delete: unexpectable mode: %s(%d)",
211 (flag == M_PASTE) ? "PASTE" : ((flag == M_INSERT) ? "INSERT" : "UNKNOWN"), flag);
212 }
213
214 /* the rule is that no shifting occurs unless by shifting a node can be freed */
215 n = B_NR_ITEMS(tbS0);
216 if ( tb->lnum[0] ) /* L[0] takes part in balancing */
217 {
218 if ( tb->lnum[0] == -1 ) /* L[0] must be joined with S[0] */
219 {
220 if ( tb->rnum[0] == -1 ) /* R[0] must be also joined with S[0] */
221 {
222 if ( tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0) )
223 {
224 /* all contents of all the 3 buffers will be in L[0] */
225 if ( PATH_H_POSITION (tb->tb_path, 1) == 0 && 1 < B_NR_ITEMS(tb->FR[0]) )
226 replace_key(tb, tb->CFL[0],tb->lkey[0],tb->FR[0],1);
227
228 /* update right_delimiting_key field */
229 #if 0
230 copy_key (B_PRIGHT_DELIM_KEY (tb->L[0]), B_PRIGHT_DELIM_KEY (tb->R[0]));
231 #endif
232 leaf_move_items (LEAF_FROM_S_TO_L, tb, n, -1, 0);
233 leaf_move_items (LEAF_FROM_R_TO_L, tb, B_NR_ITEMS(tb->R[0]), -1, 0);
234
235 #if 0/*preserve list*/
236 preserve_invalidate(tb, tbS0, tb->L[0]);
237 preserve_invalidate(tb, tb->R[0], tb->L[0]);
238 #endif
239 reiserfs_invalidate_buffer (tb, tbS0);
240 reiserfs_invalidate_buffer (tb, tb->R[0]);
241
242 return 0;
243 }
244 /* all contents of all the 3 buffers will be in R[0] */
245 leaf_move_items (LEAF_FROM_S_TO_R, tb, n, -1, 0);
246 leaf_move_items (LEAF_FROM_L_TO_R, tb, B_NR_ITEMS(tb->L[0]), -1, 0);
247
248 /* right_delimiting_key is correct in R[0] */
249 replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);
250
251 #if 0
252 /* mark tb->R[0] as suspected recipient */
253 preserve_invalidate(tb,tbS0, tb->R[0]);
254 preserve_invalidate(tb,tb->L[0], tb->R[0]);
255 #endif
256 reiserfs_invalidate_buffer (tb, tbS0);
257 reiserfs_invalidate_buffer (tb, tb->L[0]);
258
259 return -1;
260 }
261
262 #ifdef CONFIG_REISERFS_CHECK
263 if ( tb->rnum[0] != 0 )
264 reiserfs_panic (tb->tb_sb, "PAP-12045: balance_leaf_when_delete: "
265 "rnum must be 0 (%d)", tb->rnum[0]);
266 #endif /* CONFIG_REISERFS_CHECK */
267
268 /* all contents of L[0] and S[0] will be in L[0] */
269 leaf_shift_left(tb, n, -1);
270
271 #if 0/*preserve list*/
272 preserve_invalidate(tb, tbS0, tb->L[0]); /* preserved, shifting */
273 #endif
274 reiserfs_invalidate_buffer (tb, tbS0);
275
276 return 0;
277 }
278 /* a part of contents of S[0] will be in L[0] and the rest part of S[0] will be in R[0] */
279
280 #ifdef CONFIG_REISERFS_CHECK
281 if (( tb->lnum[0] + tb->rnum[0] < n ) || ( tb->lnum[0] + tb->rnum[0] > n+1 ))
282 reiserfs_panic (tb->tb_sb, "PAP-12050: balance_leaf_when_delete: "
283 "rnum(%d) and lnum(%d) and item number in S[0] are not consistent",
284 tb->rnum[0], tb->lnum[0], n);
285
286 if (( tb->lnum[0] + tb->rnum[0] == n ) && (tb->lbytes != -1 || tb->rbytes != -1))
287 reiserfs_panic (tb->tb_sb, "PAP-12055: balance_leaf_when_delete: "
288 "bad rbytes (%d)/lbytes (%d) parameters when items are not split",
289 tb->rbytes, tb->lbytes);
290 if (( tb->lnum[0] + tb->rnum[0] == n + 1 ) && (tb->lbytes < 1 || tb->rbytes != -1))
291 reiserfs_panic (tb->tb_sb, "PAP-12060: balance_leaf_when_delete: "
292 "bad rbytes (%d)/lbytes (%d) parameters when items are split",
293 tb->rbytes, tb->lbytes);
294 #endif
295
296 leaf_shift_left (tb, tb->lnum[0], tb->lbytes);
297 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
298
299 #if 0/*preserve list*/
300 preserve_invalidate (tb, tbS0, tb->L[0]);
301 mark_suspected_recipient (tb->tb_sb, tb->R[0]);
302 #endif
303 reiserfs_invalidate_buffer (tb, tbS0);
304
305 return 0;
306 }
307
308 if ( tb->rnum[0] == -1 ) {
309 /* all contents of R[0] and S[0] will be in R[0] */
310 leaf_shift_right(tb, n, -1);
311 #if 0/*preserve list*/
312 preserve_invalidate(tb, tbS0, tb->R[0]);
313 #endif
314 reiserfs_invalidate_buffer (tb, tbS0);
315 return 0;
316 }
317
318 #ifdef CONFIG_REISERFS_CHECK
319 if ( tb->rnum[0] )
320 reiserfs_panic (tb->tb_sb, "PAP-12065: balance_leaf_when_delete: "
321 "bad rnum parameter must be 0 (%d)", tb->rnum[0]);
322 #endif
323
324 return 0;
325 }
326
327
328 static int balance_leaf (struct tree_balance * tb,
329 struct item_head * ih, /* item header of inserted item (this is on little endian) */
330 const char * body, /* body of inserted item or bytes to paste */
331 int flag, /* i - insert, d - delete, c - cut, p - paste
332 (see comment to do_balance) */
333 struct item_head * insert_key, /* in our processing of one level we sometimes determine what
334 must be inserted into the next higher level. This insertion
335 consists of a key or two keys and their corresponding
336 pointers */
337 struct buffer_head ** insert_ptr /* inserted node-ptrs for the next level */
338 )
339 {
340 struct buffer_head * tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
341 #if 0/*preserve list*/
342 struct buffer_head * tbF0 = PATH_H_PPARENT (tb->tb_path, 0);
343 int S0_b_item_order = PATH_H_B_ITEM_ORDER (tb->tb_path, 0);
344 #endif
345 int item_pos = PATH_LAST_POSITION (tb->tb_path); /* index into the array of item headers in S[0]
346 of the affected item */
347 struct buffer_info bi;
348 struct buffer_head *S_new[2]; /* new nodes allocated to hold what could not fit into S */
349 int snum[2]; /* number of items that will be placed
350 into S_new (includes partially shifted
351 items) */
352 int sbytes[2]; /* if an item is partially shifted into S_new then
353 if it is a directory item
354 it is the number of entries from the item that are shifted into S_new
355 else
356 it is the number of bytes from the item that are shifted into S_new
357 */
358 int n, i;
359 int ret_val;
360 int pos_in_item;
361 int zeros_num;
362
363 #if 0
364 if (tb->insert_size [0] % 4) {
365 reiserfs_panic (tb->tb_sb, "balance_leaf: wrong insert_size %d",
366 tb->insert_size [0]);
367 }
368 #endif
369 /* Make balance in case insert_size[0] < 0 */
370 if ( tb->insert_size[0] < 0 )
371 return balance_leaf_when_delete (tb, flag);
372
373 zeros_num = 0;
374 if (flag == M_INSERT && body == 0)
375 zeros_num = le16_to_cpu (ih->ih_item_len);
376
377 pos_in_item = tb->tb_path->pos_in_item;
378 /* for indirect item pos_in_item is measured in unformatted node
379 pointers. Recalculate to bytes */
380 if (flag != M_INSERT && is_indirect_le_ih (B_N_PITEM_HEAD (tbS0, item_pos)))
381 pos_in_item *= UNFM_P_SIZE;
382
383 if ( tb->lnum[0] > 0 ) {
384 /* Shift lnum[0] items from S[0] to the left neighbor L[0] */
385 if ( item_pos < tb->lnum[0] ) {
386 /* new item or it part falls to L[0], shift it too */
387 n = B_NR_ITEMS(tb->L[0]);
388
389 switch (flag) {
390 case M_INSERT: /* insert item into L[0] */
391
392 if ( item_pos == tb->lnum[0] - 1 && tb->lbytes != -1 ) {
393 /* part of new item falls into L[0] */
394 int new_item_len;
395 int version;
396
397 #ifdef CONFIG_REISERFS_CHECK
398 if (!is_direct_le_ih (ih))
399 reiserfs_panic (tb->tb_sb, "PAP-12075: balance_leaf: "
400 "only direct inserted item can be broken. %h", ih);
401 #endif
402 ret_val = leaf_shift_left (tb, tb->lnum[0]-1, -1);
403 /* when reading the if conditions preceding the subsequent preserve_shifted
404 lines understand that their goal is to determine if all that we are
405 shifting is the new data being added */
406 #if 0/*preserve list*/
407 if (tb->lnum[0] - 1 > 0) {
408 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
409 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
410 }
411 #endif
412
413 /* Calculate item length to insert to S[0] */
414 new_item_len = le16_to_cpu (ih->ih_item_len) - tb->lbytes;
415 /* Calculate and check item length to insert to L[0] */
416 ih->ih_item_len -= new_item_len;
417
418 #ifdef CONFIG_REISERFS_CHECK
419 if ( (int)(ih->ih_item_len) <= 0 )
420 reiserfs_panic(tb->tb_sb, "PAP-12080: balance_leaf: "
421 "there is nothing to insert into L[0]: ih_item_len=%d",
422 (int)ih->ih_item_len);
423 #endif
424
425 /* Insert new item into L[0] */
426 bi.tb = tb;
427 bi.bi_bh = tb->L[0];
428 bi.bi_parent = tb->FL[0];
429 bi.bi_position = get_left_neighbor_position (tb, 0);
430 leaf_insert_into_buf (&bi, n + item_pos - ret_val, ih, body,
431 zeros_num > ih->ih_item_len ? ih->ih_item_len : zeros_num);
432
433 version = ih_version (ih);
434
435 /* Calculate key component, item length and body to insert into S[0] */
436 set_le_key_k_offset (ih_version (ih), &(ih->ih_key),
437 le_key_k_offset (ih_version (ih), &(ih->ih_key)) + tb->lbytes);
438 ih->ih_item_len = cpu_to_le16 (new_item_len);
439 if ( tb->lbytes > zeros_num ) {
440 body += (tb->lbytes - zeros_num);
441 zeros_num = 0;
442 }
443 else
444 zeros_num -= tb->lbytes;
445
446 #ifdef CONFIG_REISERFS_CHECK
447 if ( (int)(ih->ih_item_len) <= 0 )
448 reiserfs_panic(tb->tb_sb, "PAP-12085: balance_leaf: "
449 "there is nothing to insert into S[0]: ih_item_len=%d",
450 (int)ih->ih_item_len);
451 #endif
452 } else {
453 /* new item in whole falls into L[0] */
454 /* Shift lnum[0]-1 items to L[0] */
455 ret_val = leaf_shift_left(tb, tb->lnum[0]-1, tb->lbytes);
456 #if 0/*preserve list*/
457 if (tb->lnum[0] > 1) {
458 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
459 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
460 }
461 #endif
462 /* Insert new item into L[0] */
463 bi.tb = tb;
464 bi.bi_bh = tb->L[0];
465 bi.bi_parent = tb->FL[0];
466 bi.bi_position = get_left_neighbor_position (tb, 0);
467 leaf_insert_into_buf (&bi, n + item_pos - ret_val, ih, body, zeros_num);
468 #if 0/*preserve list*/
469 if (tb->preserve_mode == PRESERVE_INDIRECT_TO_DIRECT){
470 mark_suspected_recipient (tb->tb_sb, bi.bi_bh);
471 }
472 #endif
473 tb->insert_size[0] = 0;
474 zeros_num = 0;
475 }
476 break;
477
478 case M_PASTE: /* append item in L[0] */
479
480 if ( item_pos == tb->lnum[0] - 1 && tb->lbytes != -1 ) {
481 /* we must shift the part of the appended item */
482 if ( is_direntry_le_ih (B_N_PITEM_HEAD (tbS0, item_pos))) {
483
484 #ifdef CONFIG_REISERFS_CHECK
485 if ( zeros_num )
486 reiserfs_panic(tb->tb_sb, "PAP-12090: balance_leaf: illegal parameter in case of a directory");
487 #endif
488
489 /* directory item */
490 if ( tb->lbytes > pos_in_item ) {
491 /* new directory entry falls into L[0] */
492 struct item_head * pasted;
493 int l_pos_in_item = pos_in_item;
494
495 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
496 ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes - 1);
497 #if 0/*preserve list*/
498 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
499 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
500 #endif
501 if ( ret_val && ! item_pos ) {
502 pasted = B_N_PITEM_HEAD(tb->L[0],B_NR_ITEMS(tb->L[0])-1);
503 l_pos_in_item += I_ENTRY_COUNT(pasted) - (tb->lbytes-1);
504 }
505
506 /* Append given directory entry to directory item */
507 bi.tb = tb;
508 bi.bi_bh = tb->L[0];
509 bi.bi_parent = tb->FL[0];
510 bi.bi_position = get_left_neighbor_position (tb, 0);
511 leaf_paste_in_buffer (&bi, n + item_pos - ret_val, l_pos_in_item,
512 tb->insert_size[0], body, zeros_num);
513
514 /* previous string prepared space for pasting new entry, following string pastes this entry */
515
516 /* when we have merge directory item, pos_in_item has been changed too */
517
518 /* paste new directory entry. 1 is entry number */
519 leaf_paste_entries (bi.bi_bh, n + item_pos - ret_val, l_pos_in_item, 1,
520 (struct reiserfs_de_head *)body,
521 body + DEH_SIZE, tb->insert_size[0]
522 );
523 tb->insert_size[0] = 0;
524 } else {
525 /* new directory item doesn't fall into L[0] */
526 /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
527 leaf_shift_left (tb, tb->lnum[0], tb->lbytes);
528 #if 0/*preserve list*/
529 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
530 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
531 #endif
532 }
533 /* Calculate new position to append in item body */
534 pos_in_item -= tb->lbytes;
535 }
536 else {
537 /* regular object */
538
539 #ifdef CONFIG_REISERFS_CHECK
540 if ( tb->lbytes <= 0 )
541 reiserfs_panic(tb->tb_sb, "PAP-12095: balance_leaf: "
542 "there is nothing to shift to L[0]. lbytes=%d",
543 tb->lbytes);
544 if ( pos_in_item != B_N_PITEM_HEAD(tbS0, item_pos)->ih_item_len )
545 reiserfs_panic(tb->tb_sb, "PAP-12100: balance_leaf: "
546 "incorrect position to paste: item_len=%d, pos_in_item=%d",
547 B_N_PITEM_HEAD(tbS0,item_pos)->ih_item_len, pos_in_item);
548 #endif
549
550 if ( tb->lbytes >= pos_in_item ) {
551 /* appended item will be in L[0] in whole */
552 int l_n;
553
554 /* this bytes number must be appended to the last item of L[h] */
555 l_n = tb->lbytes - pos_in_item;
556
557 /* Calculate new insert_size[0] */
558 tb->insert_size[0] -= l_n;
559
560 #ifdef CONFIG_REISERFS_CHECK
561 if ( tb->insert_size[0] <= 0 )
562 reiserfs_panic(tb->tb_sb, "PAP-12105: balance_leaf: "
563 "there is nothing to paste into L[0]. insert_size=%d",
564 tb->insert_size[0]);
565 #endif
566
567 ret_val = leaf_shift_left(tb,tb->lnum[0],
568 B_N_PITEM_HEAD(tbS0,item_pos)->ih_item_len);
569 #if 0/*preserve list*/
570 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
571 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
572 #endif
573 /* Append to body of item in L[0] */
574 bi.tb = tb;
575 bi.bi_bh = tb->L[0];
576 bi.bi_parent = tb->FL[0];
577 bi.bi_position = get_left_neighbor_position (tb, 0);
578 leaf_paste_in_buffer(
579 &bi,n + item_pos - ret_val,
580 B_N_PITEM_HEAD(tb->L[0],n+item_pos-ret_val)->ih_item_len,
581 l_n,body, zeros_num > l_n ? l_n : zeros_num
582 );
583
584 #ifdef CONFIG_REISERFS_CHECK
585 if (l_n && is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0],
586 n + item_pos - ret_val)))
587 reiserfs_panic(tb->tb_sb, "PAP-12110: balance_leaf: "
588 "pasting more than 1 unformatted node pointer into indirect item");
589 #endif
590
591 /* 0-th item in S0 can be only of DIRECT type when l_n != 0*/
592 {
593 int version;
594
595 version = le16_to_cpu (B_N_PITEM_HEAD (tbS0, 0)->ih_version);
596 set_le_key_k_offset (version, B_N_PKEY (tbS0, 0),
597 le_key_k_offset (version, B_N_PKEY (tbS0, 0)) + l_n);
598 set_le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]),
599 le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0])) + l_n);
600 }
601 #if 0
602 set_le_key_k_offset (B_PRIGHT_DELIM_KEY(tb->L[0]), le_key_k_offset (B_PRIGHT_DELIM_KEY(tb->L[0])) + l_n);
603 #endif
604 /* k_offset (B_N_PKEY (tbS0, 0)) += l_n;
605 k_offset (B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0])) += l_n;
606 k_offset (B_PRIGHT_DELIM_KEY(tb->L[0])) += l_n;*/
607
608 #ifdef NO_CONFIG_REISERFS_CHECK /* journal victim */
609 if (!buffer_dirty (tbS0) || !buffer_dirty (tb->CFL[0]) || !buffer_dirty (tb->L[0]))
610 reiserfs_panic(tb->tb_sb, "PAP-12115: balance_leaf: L, CLF and S must be dirty already");
611 #endif
612
613 /* Calculate new body, position in item and insert_size[0] */
614 if ( l_n > zeros_num ) {
615 body += (l_n - zeros_num);
616 zeros_num = 0;
617 }
618 else
619 zeros_num -= l_n;
620 pos_in_item = 0;
621
622 #ifdef CONFIG_REISERFS_CHECK
623 if (comp_short_le_keys (B_N_PKEY(tbS0,0),
624 B_N_PKEY(tb->L[0],B_NR_ITEMS(tb->L[0])-1)) ||
625 !op_is_left_mergeable (B_N_PKEY (tbS0, 0), tbS0->b_size) ||
626 !op_is_left_mergeable(B_N_PDELIM_KEY(tb->CFL[0],tb->lkey[0]), tbS0->b_size))
627 reiserfs_panic (tb->tb_sb, "PAP-12120: balance_leaf: "
628 "item must be merge-able with left neighboring item");
629 #endif
630
631 }
632 else /* only part of the appended item will be in L[0] */
633 {
634 /* Calculate position in item for append in S[0] */
635 pos_in_item -= tb->lbytes;
636
637 #ifdef CONFIG_REISERFS_CHECK
638 if ( pos_in_item <= 0 )
639 reiserfs_panic(tb->tb_sb, "PAP-12125: balance_leaf: "
640 "no place for paste. pos_in_item=%d", pos_in_item);
641 #endif
642
643 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
644 leaf_shift_left(tb,tb->lnum[0],tb->lbytes);
645 #if 0/*preserve list*/
646 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
647 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
648 #endif
649 }
650 }
651 }
652 else /* appended item will be in L[0] in whole */
653 {
654 struct item_head * pasted;
655
656 if ( ! item_pos && op_is_left_mergeable (B_N_PKEY (tbS0, 0), tbS0->b_size) )
657 { /* if we paste into first item of S[0] and it is left mergable */
658 /* then increment pos_in_item by the size of the last item in L[0] */
659 pasted = B_N_PITEM_HEAD(tb->L[0],n-1);
660 if ( is_direntry_le_ih (pasted) )
661 pos_in_item += le16_to_cpu (pasted->u.ih_entry_count);
662 else
663 pos_in_item += le16_to_cpu (pasted->ih_item_len);
664 }
665
666 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
667 ret_val = leaf_shift_left(tb,tb->lnum[0],tb->lbytes);
668 #if 0/*preserve list*/
669 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
670 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
671 #endif
672 /* Append to body of item in L[0] */
673 bi.tb = tb;
674 bi.bi_bh = tb->L[0];
675 bi.bi_parent = tb->FL[0];
676 bi.bi_position = get_left_neighbor_position (tb, 0);
677 leaf_paste_in_buffer (&bi, n + item_pos - ret_val, pos_in_item, tb->insert_size[0],
678 body, zeros_num);
679
680 /* if appended item is directory, paste entry */
681 pasted = B_N_PITEM_HEAD (tb->L[0], n + item_pos - ret_val);
682 if (is_direntry_le_ih (pasted))
683 leaf_paste_entries (
684 bi.bi_bh, n + item_pos - ret_val, pos_in_item, 1,
685 (struct reiserfs_de_head *)body, body + DEH_SIZE, tb->insert_size[0]
686 );
687 /* if appended item is indirect item, put unformatted node into un list */
688 if (is_indirect_le_ih (pasted))
689 set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
690 tb->insert_size[0] = 0;
691 zeros_num = 0;
692 }
693 break;
694 default: /* cases d and t */
695 reiserfs_panic (tb->tb_sb, "PAP-12130: balance_leaf: lnum > 0: unexpectable mode: %s(%d)",
696 (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
697 }
698 } else {
699 /* new item doesn't fall into L[0] */
700 leaf_shift_left(tb,tb->lnum[0],tb->lbytes);
701 #if 0/*preserve list*/
702 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->L[0]);
703 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
704 #endif
705 }
706 } /* tb->lnum[0] > 0 */
707
708 /* Calculate new item position */
709 item_pos -= ( tb->lnum[0] - (( tb->lbytes != -1 ) ? 1 : 0));
710
711 if ( tb->rnum[0] > 0 ) {
712 /* shift rnum[0] items from S[0] to the right neighbor R[0] */
713 n = B_NR_ITEMS(tbS0);
714 switch ( flag ) {
715
716 case M_INSERT: /* insert item */
717 if ( n - tb->rnum[0] < item_pos )
718 { /* new item or its part falls to R[0] */
719 if ( item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1 )
720 { /* part of new item falls into R[0] */
721 int old_key_comp, old_len, r_zeros_number;
722 const char * r_body;
723 int version;
724 loff_t offset;
725
726 #ifdef CONFIG_REISERFS_CHECK
727 if ( !is_direct_le_ih (ih) )
728 reiserfs_panic(tb->tb_sb, "PAP-12135: balance_leaf: "
729 "only direct item can be split. (%h)", ih);
730 #endif
731
732 leaf_shift_right(tb,tb->rnum[0]-1,-1);
733 #if 0/*preserve list*/
734 if (tb->rnum[0]>1) {
735 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
736 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
737 }
738 #endif
739
740 version = le16_to_cpu (ih->ih_version);
741 /* Remember key component and item length */
742 old_key_comp = le_key_k_offset (version, &(ih->ih_key));
743 old_len = le16_to_cpu (ih->ih_item_len);
744
745 /* Calculate key component and item length to insert into R[0] */
746 offset = le_key_k_offset (version, &(ih->ih_key)) + (old_len - tb->rbytes);
747 set_le_key_k_offset (version, &(ih->ih_key), offset);
748 ih->ih_item_len = cpu_to_le16 (tb->rbytes);
749 /* Insert part of the item into R[0] */
750 bi.tb = tb;
751 bi.bi_bh = tb->R[0];
752 bi.bi_parent = tb->FR[0];
753 bi.bi_position = get_right_neighbor_position (tb, 0);
754 if ( offset - old_key_comp > zeros_num ) {
755 r_zeros_number = 0;
756 r_body = body + offset - old_key_comp - zeros_num;
757 }
758 else {
759 r_body = body;
760 r_zeros_number = zeros_num - (offset - old_key_comp);
761 zeros_num -= r_zeros_number;
762 }
763
764 leaf_insert_into_buf (&bi, 0, ih, r_body, r_zeros_number);
765
766 /* Replace right delimiting key by first key in R[0] */
767 replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);
768
769 /* Calculate key component and item length to insert into S[0] */
770 set_le_key_k_offset (version, &(ih->ih_key), old_key_comp);
771 ih->ih_item_len = cpu_to_le16 (old_len - tb->rbytes);
772
773 tb->insert_size[0] -= tb->rbytes;
774
775 }
776 else /* whole new item falls into R[0] */
777 {
778 /* Shift rnum[0]-1 items to R[0] */
779 ret_val = leaf_shift_right(tb,tb->rnum[0]-1,tb->rbytes);
780 #if 0/*preserve list*/
781 if (tb->rnum[0]>1) {
782 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
783 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
784 }
785 #endif
786 /* Insert new item into R[0] */
787 bi.tb = tb;
788 bi.bi_bh = tb->R[0];
789 bi.bi_parent = tb->FR[0];
790 bi.bi_position = get_right_neighbor_position (tb, 0);
791 leaf_insert_into_buf (&bi, item_pos - n + tb->rnum[0] - 1, ih, body, zeros_num);
792 #if 0/*preserve list*/
793 if (tb->preserve_mode == PRESERVE_INDIRECT_TO_DIRECT){
794 mark_suspected_recipient (tb->tb_sb, bi.bi_bh);
795 }
796 #endif
797
798 /* If we insert new item in the begin of R[0] change the right delimiting key */
799 if ( item_pos - n + tb->rnum[0] - 1 == 0 ) {
800 replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);
801
802 #if 0
803 /* update right delimiting key */
804 copy_key(B_PRIGHT_DELIM_KEY(tbS0), &(ih->ih_key));
805 reiserfs_mark_buffer_dirty (tbS0, 0);
806 #endif
807 }
808 zeros_num = tb->insert_size[0] = 0;
809 }
810 }
811 else /* new item or part of it doesn't fall into R[0] */
812 {
813 leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
814 #if 0/*preserve list*/
815 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
816 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
817 #endif
818 }
819 break;
820
821 case M_PASTE: /* append item */
822
823 if ( n - tb->rnum[0] <= item_pos ) /* pasted item or part of it falls to R[0] */
824 {
825 if ( item_pos == n - tb->rnum[0] && tb->rbytes != -1 )
826 { /* we must shift the part of the appended item */
827 if ( is_direntry_le_ih (B_N_PITEM_HEAD(tbS0, item_pos)))
828 { /* we append to directory item */
829 int entry_count;
830
831 #ifdef CONFIG_REISERFS_CHECK
832 if ( zeros_num )
833 reiserfs_panic(tb->tb_sb, "PAP-12145: balance_leaf: illegal parametr in case of a directory");
834 #endif
835
836 entry_count = I_ENTRY_COUNT(B_N_PITEM_HEAD(tbS0, item_pos));
837 if ( entry_count - tb->rbytes < pos_in_item )
838 /* new directory entry falls into R[0] */
839 {
840 int paste_entry_position;
841
842 #ifdef CONFIG_REISERFS_CHECK
843 if ( tb->rbytes - 1 >= entry_count || ! tb->insert_size[0] )
844 reiserfs_panic(tb->tb_sb, "PAP-12150: balance_leaf: "
845 "no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
846 tb->rbytes, entry_count);
847 #endif
848
849 /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
850 leaf_shift_right(tb,tb->rnum[0],tb->rbytes - 1);
851 #if 0/*preserve list*/
852 /* if we are shifting more than just the new entry */
853 if (tb->rbytes > 1 || tb->rnum[0] > 1) {
854 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
855 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
856 }
857 #endif
858 /* Paste given directory entry to directory item */
859 paste_entry_position = pos_in_item - entry_count + tb->rbytes - 1;
860 bi.tb = tb;
861 bi.bi_bh = tb->R[0];
862 bi.bi_parent = tb->FR[0];
863 bi.bi_position = get_right_neighbor_position (tb, 0);
864 leaf_paste_in_buffer (&bi, 0, paste_entry_position,
865 tb->insert_size[0],body,zeros_num);
866 /* paste entry */
867 leaf_paste_entries (
868 bi.bi_bh, 0, paste_entry_position, 1, (struct reiserfs_de_head *)body,
869 body + DEH_SIZE, tb->insert_size[0]
870 );
871
872 if ( paste_entry_position == 0 ) {
873 /* change delimiting keys */
874 replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);
875 #if 0
876 copy_key(B_PRIGHT_DELIM_KEY(tbS0), B_N_PKEY(tb->R[0], 0));
877 reiserfs_mark_buffer_dirty (tbS0, 0);
878 #endif
879 }
880
881 tb->insert_size[0] = 0;
882 pos_in_item++;
883 }
884 else /* new directory entry doesn't fall into R[0] */
885 {
886 leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
887 #if 0/*preserve list*/
888 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
889 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
890 #endif
891 }
892 }
893 else /* regular object */
894 {
895 int n_shift, n_rem, r_zeros_number;
896 const char * r_body;
897
898 /* Calculate number of bytes which must be shifted from appended item */
899 if ( (n_shift = tb->rbytes - tb->insert_size[0]) < 0 )
900 n_shift = 0;
901
902 #ifdef CONFIG_REISERFS_CHECK
903 if (pos_in_item != B_N_PITEM_HEAD (tbS0, item_pos)->ih_item_len)
904 reiserfs_panic(tb->tb_sb,"PAP-12155: balance_leaf: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
905 pos_in_item, B_N_PITEM_HEAD(tbS0,item_pos)->ih_item_len);
906 #endif
907
908 leaf_shift_right(tb,tb->rnum[0],n_shift);
909 #if 0/*preserve list*/
910 /* if we are shifting an old part from the appended item or more than the appended item is going into R */
911 if (n_shift || tb->rnum[0] > 1) {
912 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
913 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
914 }
915 #endif
916 /* Calculate number of bytes which must remain in body after appending to R[0] */
917 if ( (n_rem = tb->insert_size[0] - tb->rbytes) < 0 )
918 n_rem = 0;
919
920 {
921 int version;
922
923 version = ih_version (B_N_PITEM_HEAD (tb->R[0],0));
924 set_le_key_k_offset (version, B_N_PKEY(tb->R[0],0),
925 le_key_k_offset (version, B_N_PKEY(tb->R[0],0)) + n_rem);
926 set_le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0]),
927 le_key_k_offset (version, B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) + n_rem);
928 }
929 /* k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
930 k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;*/
931 do_balance_mark_internal_dirty (tb, tb->CFR[0], 0);
932
933 #if 0
934 set_le_key_k_offset (B_PRIGHT_DELIM_KEY(tbS0), le_key_k_offset (B_PRIGHT_DELIM_KEY(tbS0)) + n_rem);
935 /* k_offset (B_PRIGHT_DELIM_KEY(tbS0)) += n_rem;*/
936 reiserfs_mark_buffer_dirty (tbS0, 0);
937 #endif
938 /* Append part of body into R[0] */
939 bi.tb = tb;
940 bi.bi_bh = tb->R[0];
941 bi.bi_parent = tb->FR[0];
942 bi.bi_position = get_right_neighbor_position (tb, 0);
943 if ( n_rem > zeros_num ) {
944 r_zeros_number = 0;
945 r_body = body + n_rem - zeros_num;
946 }
947 else {
948 r_body = body;
949 r_zeros_number = zeros_num - n_rem;
950 zeros_num -= r_zeros_number;
951 }
952
953 leaf_paste_in_buffer(&bi, 0, n_shift, tb->insert_size[0] - n_rem, r_body, r_zeros_number);
954
955 if (is_indirect_le_ih (B_N_PITEM_HEAD(tb->R[0],0))) {
956
957 #ifdef CONFIG_REISERFS_CHECK
958 if (n_rem)
959 reiserfs_panic(tb->tb_sb, "PAP-12160: balance_leaf: paste more than one unformatted node pointer");
960 #endif
961
962 set_ih_free_space (B_N_PITEM_HEAD(tb->R[0],0), ((struct unfm_nodeinfo*)body)->unfm_freespace);
963 }
964
965 tb->insert_size[0] = n_rem;
966 if ( ! n_rem )
967 pos_in_item ++;
968 }
969 }
970 else /* pasted item in whole falls into R[0] */
971 {
972 struct item_head * pasted;
973
974 ret_val = leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
975 #if 0/*preserve list*/
976 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
977 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
978 #endif
979 /* append item in R[0] */
980 if ( pos_in_item >= 0 ) {
981 bi.tb = tb;
982 bi.bi_bh = tb->R[0];
983 bi.bi_parent = tb->FR[0];
984 bi.bi_position = get_right_neighbor_position (tb, 0);
985 leaf_paste_in_buffer(&bi,item_pos - n + tb->rnum[0], pos_in_item,
986 tb->insert_size[0],body, zeros_num);
987 }
988
989 /* paste new entry, if item is directory item */
990 pasted = B_N_PITEM_HEAD(tb->R[0], item_pos - n + tb->rnum[0]);
991 if (is_direntry_le_ih (pasted) && pos_in_item >= 0 ) {
992 leaf_paste_entries (
993 bi.bi_bh, item_pos - n + tb->rnum[0], pos_in_item, 1,
994 (struct reiserfs_de_head *)body, body + DEH_SIZE, tb->insert_size[0]
995 );
996 if ( ! pos_in_item ) {
997
998 #ifdef CONFIG_REISERFS_CHECK
999 if ( item_pos - n + tb->rnum[0] )
1000 reiserfs_panic (tb->tb_sb, "PAP-12165: balance_leaf: "
1001 "directory item must be first item of node when pasting is in 0th position");
1002 #endif
1003
1004 /* update delimiting keys */
1005 replace_key(tb, tb->CFR[0],tb->rkey[0],tb->R[0],0);
1006 #if 0
1007 copy_key(B_PRIGHT_DELIM_KEY(tbS0),B_N_PKEY(tb->R[0], 0));
1008 reiserfs_mark_buffer_dirty (tbS0, 0);
1009 #endif
1010 }
1011 }
1012
1013 if (is_indirect_le_ih (pasted))
1014 set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
1015 zeros_num = tb->insert_size[0] = 0;
1016 }
1017 }
1018 else /* new item doesn't fall into R[0] */
1019 {
1020 leaf_shift_right(tb,tb->rnum[0],tb->rbytes);
1021 #if 0/*preserve list*/
1022 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, tb->R[0]);
1023 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
1024 #endif
1025 }
1026 break;
1027 default: /* cases d and t */
1028 reiserfs_panic (tb->tb_sb, "PAP-12175: balance_leaf: rnum > 0: unexpectable mode: %s(%d)",
1029 (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
1030 }
1031
1032 } /* tb->rnum[0] > 0 */
1033
1034
1035 #ifdef CONFIG_REISERFS_CHECK
1036 if ( tb->blknum[0] > 3 )
1037 reiserfs_panic (tb->tb_sb, "PAP-12180: balance_leaf: blknum can not be %d. It must be <= 3", tb->blknum[0]);
1038
1039 if ( tb->blknum[0] < 0 )
1040 reiserfs_panic (tb->tb_sb, "PAP-12185: balance_leaf: blknum can not be %d. It must be >= 0", tb->blknum[0]);
1041 #endif
1042
1043 /* if while adding to a node we discover that it is possible to split
1044 it in two, and merge the left part into the left neighbor and the
1045 right part into the right neighbor, eliminating the node */
1046 if ( tb->blknum[0] == 0 ) { /* node S[0] is empty now */
1047
1048 #ifdef CONFIG_REISERFS_CHECK
1049 if ( ! tb->lnum[0] || ! tb->rnum[0] )
1050 reiserfs_panic(tb->tb_sb, "PAP-12190: balance_leaf: lnum and rnum must not be zero");
1051 #if 0
1052 if (COMP_KEYS (B_N_PKEY(tb->R[0], 0), B_PRIGHT_DELIM_KEY(tbS0)))
1053 reiserfs_panic (tb->tb_sb, "vs-12192: balance_leaf: S[0] is being removed from the tree, it has incorrect right delimiting key");
1054 #endif
1055 #endif
1056
1057 #if 0
1058 /* if insertion was done before 0-th position in R[0], right
1059 delimiting key of the tb->L[0]'s and left delimiting key are
1060 not set correctly */
1061 if (tb->L[0]) {
1062 copy_key(B_PRIGHT_DELIM_KEY(tb->L[0]), B_PRIGHT_DELIM_KEY(tbS0));
1063 reiserfs_mark_buffer_dirty (tb->L[0], 0);
1064 }
1065
1066 if (tb->CFL[0]) {
1067 copy_key (B_N_PDELIM_KEY (tb->CFL[0], tb->lkey[0]), B_PRIGHT_DELIM_KEY(tbS0));
1068 reiserfs_mark_buffer_dirty (tb->CFL[0], 0);
1069 }
1070 #endif
1071
1072 /* if insertion was done before 0-th position in R[0], right
1073 delimiting key of the tb->L[0]'s and left delimiting key are
1074 not set correctly */
1075 if (tb->CFL[0]) {
1076 if (!tb->CFR[0])
1077 reiserfs_panic (tb->tb_sb, "vs-12195: balance_leaf: CFR not initialized");
1078 copy_key (B_N_PDELIM_KEY (tb->CFL[0], tb->lkey[0]), B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]));
1079 do_balance_mark_internal_dirty (tb, tb->CFL[0], 0);
1080 }
1081
1082 reiserfs_invalidate_buffer(tb,tbS0);
1083 return 0;
1084 }
1085
1086
1087 /* Fill new nodes that appear in place of S[0] */
1088
1089 /* I am told that this copying is because we need an array to enable
1090 the looping code. -Hans */
1091 snum[0] = tb->s1num,
1092 snum[1] = tb->s2num;
1093 sbytes[0] = tb->s1bytes;
1094 sbytes[1] = tb->s2bytes;
1095 for( i = tb->blknum[0] - 2; i >= 0; i-- ) {
1096
1097 #ifdef CONFIG_REISERFS_CHECK
1098 if (!snum[i])
1099 reiserfs_panic(tb->tb_sb,"PAP-12200: balance_leaf: snum[%d] == %d. Must be > 0", i, snum[i]);
1100 #endif /* CONFIG_REISERFS_CHECK */
1101
1102 /* here we shift from S to S_new nodes */
1103
1104 S_new[i] = get_FEB(tb);
1105
1106 /* initialized block type and tree level */
1107 B_BLK_HEAD(S_new[i])->blk_level = cpu_to_le16 (DISK_LEAF_NODE_LEVEL);
1108
1109
1110 n = B_NR_ITEMS(tbS0);
1111
1112 switch (flag) {
1113 case M_INSERT: /* insert item */
1114
1115 if ( n - snum[i] < item_pos )
1116 { /* new item or it's part falls to first new node S_new[i]*/
1117 if ( item_pos == n - snum[i] + 1 && sbytes[i] != -1 )
1118 { /* part of new item falls into S_new[i] */
1119 int old_key_comp, old_len, r_zeros_number;
1120 const char * r_body;
1121 int version;
1122
1123 #ifdef CONFIG_REISERFS_CHECK
1124 if ( !is_direct_le_ih(ih) )
1125 /* The items which can be inserted are:
1126 Stat_data item, direct item, indirect item and directory item which consist of only two entries "." and "..".
1127 These items must not be broken except for a direct one. */
1128 reiserfs_panic(tb->tb_sb, "PAP-12205: balance_leaf: "
1129 "non-direct item can not be broken when inserting");
1130 #endif
1131
1132 /* Move snum[i]-1 items from S[0] to S_new[i] */
1133 leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i] - 1, -1, S_new[i]);
1134 #if 0/*preserve list*/
1135 if (snum[i] > 1 ) {
1136 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, S_new[i]);
1137 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
1138 }
1139 #endif
1140 /* Remember key component and item length */
1141 version = ih_version (ih);
1142 old_key_comp = le_key_k_offset (version, &(ih->ih_key));
1143 old_len = le16_to_cpu (ih->ih_item_len);
1144
1145 /* Calculate key component and item length to insert into S_new[i] */
1146 set_le_key_k_offset (version, &(ih->ih_key),
1147 le_key_k_offset (version, &(ih->ih_key)) + (old_len - sbytes[i]));
1148
1149 ih->ih_item_len = cpu_to_le16 (sbytes[i]);
1150
1151 /* Insert part of the item into S_new[i] before 0-th item */
1152 bi.tb = tb;
1153 bi.bi_bh = S_new[i];
1154 bi.bi_parent = 0;
1155 bi.bi_position = 0;
1156
1157 if ( le_key_k_offset (version, &(ih->ih_key)) - old_key_comp > zeros_num ) {
1158 r_zeros_number = 0;
1159 r_body = body + (le_key_k_offset (version, &(ih->ih_key)) - old_key_comp) - zeros_num;
1160 }
1161 else {
1162 r_body = body;
1163 r_zeros_number = zeros_num - (le_key_k_offset (version, &(ih->ih_key)) - old_key_comp);
1164 zeros_num -= r_zeros_number;
1165 }
1166
1167 leaf_insert_into_buf (&bi, 0, ih, r_body, r_zeros_number);
1168
1169 /* Calculate key component and item length to insert into S[i] */
1170 set_le_key_k_offset (version, &(ih->ih_key), old_key_comp);
1171 ih->ih_item_len = cpu_to_le16 (old_len - sbytes[i]);
1172 tb->insert_size[0] -= sbytes[i];
1173 }
1174 else /* whole new item falls into S_new[i] */
1175 {
1176 /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
1177 leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i] - 1, sbytes[i], S_new[i]);
1178
1179 /* Insert new item into S_new[i] */
1180 bi.tb = tb;
1181 bi.bi_bh = S_new[i];
1182 bi.bi_parent = 0;
1183 bi.bi_position = 0;
1184 leaf_insert_into_buf (&bi, item_pos - n + snum[i] - 1, ih, body, zeros_num);
1185 #if 0/*preserve list*/
1186 if (tb->preserve_mode == PRESERVE_INDIRECT_TO_DIRECT){
1187 mark_suspected_recipient (tb->tb_sb, bi.bi_bh);
1188 }
1189 #endif
1190
1191 zeros_num = tb->insert_size[0] = 0;
1192 }
1193 }
1194
1195 else /* new item or it part don't falls into S_new[i] */
1196 {
1197 leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
1198 #if 0/*preserve list*/
1199 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, S_new[i]);
1200 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
1201 #endif
1202 }
1203 break;
1204
1205 case M_PASTE: /* append item */
1206
1207 if ( n - snum[i] <= item_pos ) /* pasted item or part if it falls to S_new[i] */
1208 {
1209 if ( item_pos == n - snum[i] && sbytes[i] != -1 )
1210 { /* we must shift part of the appended item */
1211 struct item_head * aux_ih;
1212
1213 #ifdef CONFIG_REISERFS_CHECK
1214 if ( ih )
1215 reiserfs_panic (tb->tb_sb, "PAP-12210: balance_leaf: ih must be 0");
1216 #endif /* CONFIG_REISERFS_CHECK */
1217
1218 if ( is_direntry_le_ih (aux_ih = B_N_PITEM_HEAD(tbS0,item_pos))) {
1219 /* we append to directory item */
1220
1221 int entry_count;
1222
1223 entry_count = le16_to_cpu (aux_ih->u.ih_entry_count);
1224
1225 if ( entry_count - sbytes[i] < pos_in_item && pos_in_item <= entry_count ) {
1226 /* new directory entry falls into S_new[i] */
1227
1228 #ifdef CONFIG_REISERFS_CHECK
1229 if ( ! tb->insert_size[0] )
1230 reiserfs_panic (tb->tb_sb, "PAP-12215: balance_leaif: insert_size is already 0");
1231 if ( sbytes[i] - 1 >= entry_count )
1232 reiserfs_panic (tb->tb_sb, "PAP-12220: balance_leaf: "
1233 "there are no so much entries (%d), only %d",
1234 sbytes[i] - 1, entry_count);
1235 #endif
1236
1237 /* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
1238 leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i]-1, S_new[i]);
1239 #if 0/*preserve list*/
1240 /* if more than the affected item is shifted, or if more than
1241 one entry (from the affected item) is shifted */
1242 if (snum[i] > 1 || sbytes[i] > 1) {
1243 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, S_new[i]);
1244 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
1245 }
1246 #endif
1247 /* Paste given directory entry to directory item */
1248 bi.tb = tb;
1249 bi.bi_bh = S_new[i];
1250 bi.bi_parent = 0;
1251 bi.bi_position = 0;
1252 leaf_paste_in_buffer (&bi, 0, pos_in_item - entry_count + sbytes[i] - 1,
1253 tb->insert_size[0], body,zeros_num);
1254 /* paste new directory entry */
1255 leaf_paste_entries (
1256 bi.bi_bh, 0, pos_in_item - entry_count + sbytes[i] - 1,
1257 1, (struct reiserfs_de_head *)body, body + DEH_SIZE,
1258 tb->insert_size[0]
1259 );
1260 tb->insert_size[0] = 0;
1261 pos_in_item++;
1262 } else { /* new directory entry doesn't fall into S_new[i] */
1263 leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
1264 }
1265 }
1266 else /* regular object */
1267 {
1268 int n_shift, n_rem, r_zeros_number;
1269 const char * r_body;
1270
1271 #ifdef CONFIG_REISERFS_CHECK
1272 if ( pos_in_item != B_N_PITEM_HEAD(tbS0,item_pos)->ih_item_len ||
1273 tb->insert_size[0] <= 0 )
1274 reiserfs_panic (tb->tb_sb, "PAP-12225: balance_leaf: item too short or insert_size <= 0");
1275 #endif
1276
1277 /* Calculate number of bytes which must be shifted from appended item */
1278 n_shift = sbytes[i] - tb->insert_size[0];
1279 if ( n_shift < 0 )
1280 n_shift = 0;
1281 leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], n_shift, S_new[i]);
1282
1283 /* Calculate number of bytes which must remain in body after append to S_new[i] */
1284 n_rem = tb->insert_size[0] - sbytes[i];
1285 if ( n_rem < 0 )
1286 n_rem = 0;
1287 /* Append part of body into S_new[0] */
1288 bi.tb = tb;
1289 bi.bi_bh = S_new[i];
1290 bi.bi_parent = 0;
1291 bi.bi_position = 0;
1292
1293 if ( n_rem > zeros_num ) {
1294 r_zeros_number = 0;
1295 r_body = body + n_rem - zeros_num;
1296 }
1297 else {
1298 r_body = body;
1299 r_zeros_number = zeros_num - n_rem;
1300 zeros_num -= r_zeros_number;
1301 }
1302
1303 leaf_paste_in_buffer(&bi, 0, n_shift, tb->insert_size[0]-n_rem, r_body,r_zeros_number);
1304 {
1305 struct item_head * tmp;
1306
1307 tmp = B_N_PITEM_HEAD(S_new[i],0);
1308 if (is_indirect_le_ih (tmp)) {
1309 if (n_rem)
1310 reiserfs_panic (tb->tb_sb, "PAP-12230: balance_leaf: invalid action with indirect item");
1311 set_ih_free_space (tmp, ((struct unfm_nodeinfo*)body)->unfm_freespace);
1312 }
1313 set_le_key_k_offset (ih_version (tmp), &tmp->ih_key,
1314 le_key_k_offset (ih_version (tmp), &tmp->ih_key) + n_rem);
1315 }
1316
1317 tb->insert_size[0] = n_rem;
1318 if ( ! n_rem )
1319 pos_in_item++;
1320 }
1321 }
1322 else
1323 /* item falls wholly into S_new[i] */
1324 {
1325 int ret_val;
1326 struct item_head * pasted;
1327
1328 #ifdef CONFIG_REISERFS_CHECK
1329 struct item_head * ih = B_N_PITEM_HEAD(tbS0,item_pos);
1330
1331 if ( ! is_direntry_le_ih(ih) && (pos_in_item != ih->ih_item_len ||
1332 tb->insert_size[0] <= 0) )
1333 reiserfs_panic (tb->tb_sb, "PAP-12235: balance_leaf: pos_in_item must be equal to ih_item_len");
1334 #endif /* CONFIG_REISERFS_CHECK */
1335
1336 ret_val = leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
1337 #if 0/*preserve list*/
1338 /* we must preserve that which we are pasting onto the end of and shifting */
1339 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, S_new[i]);
1340 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
1341 #endif
1342
1343 #ifdef CONFIG_REISERFS_CHECK
1344 if ( ret_val )
1345 reiserfs_panic (tb->tb_sb, "PAP-12240: balance_leaf: "
1346 "unexpected value returned by leaf_move_items (%d)",
1347 ret_val);
1348 #endif /* CONFIG_REISERFS_CHECK */
1349
1350 /* paste into item */
1351 bi.tb = tb;
1352 bi.bi_bh = S_new[i];
1353 bi.bi_parent = 0;
1354 bi.bi_position = 0;
1355 leaf_paste_in_buffer(&bi, item_pos - n + snum[i], pos_in_item, tb->insert_size[0], body, zeros_num);
1356
1357 pasted = B_N_PITEM_HEAD(S_new[i], item_pos - n + snum[i]);
1358 if (is_direntry_le_ih (pasted))
1359 {
1360 leaf_paste_entries (
1361 bi.bi_bh, item_pos - n + snum[i], pos_in_item, 1,
1362 (struct reiserfs_de_head *)body, body + DEH_SIZE, tb->insert_size[0]
1363 );
1364 }
1365
1366 /* if we paste to indirect item update ih_free_space */
1367 if (is_indirect_le_ih (pasted))
1368 set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
1369 zeros_num = tb->insert_size[0] = 0;
1370 }
1371 }
1372
1373 else /* pasted item doesn't fall into S_new[i] */
1374 {
1375 leaf_move_items (LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i], S_new[i]);
1376 #if 0/*preserve list*/
1377 preserve_shifted(tb, &(PATH_PLAST_BUFFER (tb->tb_path)), tbF0, S0_b_item_order, S_new[i]);
1378 tbS0 = PATH_PLAST_BUFFER (tb->tb_path);
1379 #endif
1380 }
1381 break;
1382 default: /* cases d and t */
1383 reiserfs_panic (tb->tb_sb, "PAP-12245: balance_leaf: blknum > 2: unexpectable mode: %s(%d)",
1384 (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
1385 }
1386
1387 memcpy (insert_key + i,B_N_PKEY(S_new[i],0),KEY_SIZE);
1388 insert_ptr[i] = S_new[i];
1389
1390 #ifdef CONFIG_REISERFS_CHECK
1391 if (atomic_read (&(S_new[i]->b_count)) != 1) {
1392 if (atomic_read(&(S_new[i]->b_count)) != 2 ||
1393 !(buffer_journaled(S_new[i]) || buffer_journal_dirty(S_new[i]))) {
1394 reiserfs_panic (tb->tb_sb, "PAP-12247: balance_leaf: S_new[%d] : (%b)\n", i, S_new[i]);
1395 }
1396 }
1397 #endif
1398
1399 #if 0
1400 /* update right_delimiting_key fields */
1401 copy_key (B_PRIGHT_DELIM_KEY (S_new[i]), B_PRIGHT_DELIM_KEY (tbS0));
1402 copy_key (B_PRIGHT_DELIM_KEY (tbS0), B_N_PKEY (S_new[i], 0));
1403 reiserfs_mark_buffer_dirty (tbS0, 0);
1404 #endif
1405
1406 }
1407
1408 /* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
1409 affected item which remains in S */
1410 if ( 0 <= item_pos && item_pos < tb->s0num )
1411 { /* if we must insert or append into buffer S[0] */
1412
1413 switch (flag)
1414 {
1415 case M_INSERT: /* insert item into S[0] */
1416 bi.tb = tb;
1417 bi.bi_bh = tbS0;
1418 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
1419 bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
1420 leaf_insert_into_buf (&bi, item_pos, ih, body, zeros_num);
1421 #if 0/*preserve list*/
1422 if (tb->preserve_mode == PRESERVE_INDIRECT_TO_DIRECT){
1423 mark_suspected_recipient (tb->tb_sb, bi.bi_bh);
1424 }
1425 #endif
1426
1427 /* If we insert the first key change the delimiting key */
1428 if( item_pos == 0 ) {
1429 if (tb->CFL[0]) /* can be 0 in reiserfsck */
1430 replace_key(tb, tb->CFL[0], tb->lkey[0],tbS0,0);
1431
1432 #if 0 /* right delim key support */
1433 #ifdef CONFIG_REISERFS_CHECK
1434 if ( ! tb->CFL[0] || ! tb->L[0] || (B_NR_ITEMS (tbS0) > 1 &&
1435 COMP_KEYS(B_PRIGHT_DELIM_KEY(tb->L[0]), B_N_PKEY(tbS0, 1))) )
1436 reiserfs_panic(tb->tb_sb, "PAP-12250: balance_leaf: invalid right delimiting key");
1437 if (!buffer_dirty (tb->L[0]) && !(buffer_journaled(tb->L[0]) ||
1438 buffer_journal_dirty(tb->L[0])))
1439 reiserfs_panic (tb->tb_sb, "PAP-12255: balance_leaf: tb->L[0] must be dirty");
1440 #endif
1441 if (tb->L[0]) /* can be 0 in reiserfsck */
1442 copy_key (B_PRIGHT_DELIM_KEY (tb->L[0]), &(ih->ih_key));
1443 #endif /* right delim key support */
1444 }
1445 break;
1446
1447 case M_PASTE: { /* append item in S[0] */
1448 struct item_head * pasted;
1449
1450 pasted = B_N_PITEM_HEAD (tbS0, item_pos);
1451 /* when directory, may be new entry already pasted */
1452 if (is_direntry_le_ih (pasted)) {
1453 if ( pos_in_item >= 0 && pos_in_item <= le16_to_cpu (pasted->u.ih_entry_count) ) {
1454
1455 #ifdef CONFIG_REISERFS_CHECK
1456 if ( ! tb->insert_size[0] )
1457 reiserfs_panic (tb->tb_sb, "PAP-12260: balance_leaf: insert_size is 0 already");
1458 #endif /* CONFIG_REISERFS_CHECK */
1459
1460 /* prepare space */
1461 bi.tb = tb;
1462 bi.bi_bh = tbS0;
1463 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
1464 bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
1465 leaf_paste_in_buffer(&bi, item_pos, pos_in_item, tb->insert_size[0], body, zeros_num);
1466
1467
1468 #ifdef CONFIG_REISERFS_CHECK
1469 #if 0
1470 if ( ! item_pos && ! pos_in_item && (! tb->L[0] || COMP_KEYS(B_PRIGHT_DELIM_KEY(tb->L[0]),
1471 B_N_PKEY(tbS0, 0))) )
1472 reiserfs_panic(tb->tb_sb, "PAP-12265: balance_leaf: invalid right delimiting key");
1473 #endif
1474 #endif
1475
1476 /* paste entry */
1477 leaf_paste_entries (
1478 bi.bi_bh, item_pos, pos_in_item, 1, (struct reiserfs_de_head *)body,
1479 body + DEH_SIZE, tb->insert_size[0]
1480 );
1481 if ( ! item_pos && ! pos_in_item ) {
1482
1483 #ifdef CONFIG_REISERFS_CHECK
1484 if (!tb->CFL[0] || !tb->L[0])
1485 reiserfs_panic (tb->tb_sb, "PAP-12270: balance_leaf: CFL[0]/L[0] must be specified");
1486 #endif /* CONFIG_REISERFS_CHECK */
1487
1488 if (tb->CFL[0]) {
1489 replace_key(tb, tb->CFL[0], tb->lkey[0],tbS0,0);
1490
1491 #if 0
1492 /* update right delimiting key */
1493 copy_key (B_PRIGHT_DELIM_KEY (tb->L[0]), B_N_PKEY(tbS0, 0));
1494 /* probably not needed as something has been shifted to tb->L[0] already */
1495 reiserfs_mark_buffer_dirty (tb->L[0], 0);
1496 #endif
1497 }
1498 }
1499 tb->insert_size[0] = 0;
1500 }
1501 } else { /* regular object */
1502 if ( pos_in_item == pasted->ih_item_len ) {
1503
1504 #ifdef CONFIG_REISERFS_CHECK
1505 if ( tb->insert_size[0] <= 0 )
1506 reiserfs_panic (tb->tb_sb,
1507 "PAP-12275: balance_leaf: insert size must not be %d", tb->insert_size[0]);
1508 #endif /* CONFIG_REISERFS_CHECK */
1509 bi.tb = tb;
1510 bi.bi_bh = tbS0;
1511 bi.bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
1512 bi.bi_position = PATH_H_POSITION (tb->tb_path, 1);
1513 leaf_paste_in_buffer (&bi, item_pos, pos_in_item, tb->insert_size[0], body, zeros_num);
1514
1515 if (is_indirect_le_ih (pasted)) {
1516
1517 #ifdef CONFIG_REISERFS_CHECK
1518 if ( tb->insert_size[0] != UNFM_P_SIZE )
1519 reiserfs_panic (tb->tb_sb,
1520 "PAP-12280: balance_leaf: insert_size for indirect item must be %d, not %d",
1521 UNFM_P_SIZE, tb->insert_size[0]);
1522 #endif /* CONFIG_REISERFS_CHECK */
1523
1524 set_ih_free_space (pasted, ((struct unfm_nodeinfo*)body)->unfm_freespace);
1525 }
1526 tb->insert_size[0] = 0;
1527 }
1528
1529 #ifdef CONFIG_REISERFS_CHECK
1530 else {
1531 if ( tb->insert_size[0] ) {
1532 print_cur_tb ("12285");
1533 reiserfs_panic (tb->tb_sb, "PAP-12285: balance_leaf: insert_size must be 0 (%d)", tb->insert_size[0]);
1534 }
1535 }
1536 #endif /* CONFIG_REISERFS_CHECK */
1537
1538 }
1539 } /* case M_PASTE: */
1540 }
1541 }
1542
1543 #ifdef CONFIG_REISERFS_CHECK
1544 if ( flag == M_PASTE && tb->insert_size[0] ) {
1545 print_cur_tb ("12290");
1546 reiserfs_panic (tb->tb_sb, "PAP-12290: balance_leaf: insert_size is still not 0 (%d)", tb->insert_size[0]);
1547 }
1548 #endif /* CONFIG_REISERFS_CHECK */
1549
1550 return 0;
1551 } /* Leaf level of the tree is balanced (end of balance_leaf) */
1552
1553
1554
1555 /* Make empty node */
1556 void make_empty_node (struct buffer_info * bi)
1557 {
1558 struct block_head * blkh;
1559
1560 #ifdef CONFIG_REISERFS_CHECK
1561 if (bi->bi_bh == NULL)
1562 reiserfs_panic (0, "PAP-12295: make_empty_node: pointer to the buffer is NULL");
1563 #endif
1564
1565 (blkh = B_BLK_HEAD(bi->bi_bh))->blk_nr_item = cpu_to_le16 (0);
1566 blkh->blk_free_space = cpu_to_le16 (MAX_CHILD_SIZE(bi->bi_bh));
1567
1568 if (bi->bi_parent)
1569 B_N_CHILD (bi->bi_parent, bi->bi_position)->dc_size = 0;
1570 }
1571
1572
1573 /* Get first empty buffer */
1574 struct buffer_head * get_FEB (struct tree_balance * tb)
1575 {
1576 int i;
1577 struct buffer_head * first_b;
1578 struct buffer_info bi;
1579
1580 for (i = 0; i < MAX_FEB_SIZE; i ++)
1581 if (tb->FEB[i] != 0)
1582 break;
1583
1584 if (i == MAX_FEB_SIZE)
1585 reiserfs_panic(tb->tb_sb, "vs-12300: get_FEB: FEB list is empty");
1586
1587 bi.tb = tb;
1588 bi.bi_bh = first_b = tb->FEB[i];
1589 bi.bi_parent = 0;
1590 bi.bi_position = 0;
1591 make_empty_node (&bi);
1592 set_bit(BH_Uptodate, &first_b->b_state);
1593 tb->FEB[i] = 0;
1594 tb->used[i] = first_b;
1595
1596 return(first_b);
1597 }
1598
1599
1600 /* This is now used because reiserfs_free_block has to be able to
1601 ** schedule.
1602 */
1603 static void store_thrown (struct tree_balance * tb, struct buffer_head * bh)
1604 {
1605 int i;
1606
1607 if (buffer_dirty (bh))
1608 printk ("store_thrown deals with dirty buffer\n");
1609 for (i = 0; i < sizeof (tb->thrown)/sizeof (tb->thrown[0]); i ++)
1610 if (!tb->thrown[i]) {
1611 tb->thrown[i] = bh;
1612 get_bh(bh) ; /* free_thrown puts this */
1613 return;
1614 }
1615 reiserfs_warning ("store_thrown: too many thrown buffers\n");
1616 }
1617
1618 static void free_thrown(struct tree_balance *tb) {
1619 int i ;
1620 unsigned long blocknr ;
1621 for (i = 0; i < sizeof (tb->thrown)/sizeof (tb->thrown[0]); i++) {
1622 if (tb->thrown[i]) {
1623 blocknr = tb->thrown[i]->b_blocknr ;
1624 if (buffer_dirty (tb->thrown[i]))
1625 printk ("free_thrown deals with dirty buffer %ld\n", blocknr);
1626 brelse(tb->thrown[i]) ; /* incremented in store_thrown */
1627 reiserfs_free_block (tb->transaction_handle, blocknr);
1628 }
1629 }
1630 }
1631
1632 void reiserfs_invalidate_buffer (struct tree_balance * tb, struct buffer_head * bh)
1633 {
1634 B_BLK_HEAD (bh)->blk_level = cpu_to_le16 (FREE_LEVEL)/*0*/;
1635 B_BLK_HEAD (bh)->blk_nr_item = cpu_to_le16 (0);
1636 mark_buffer_clean (bh);
1637 /* reiserfs_free_block is no longer schedule safe
1638 reiserfs_free_block (tb->transaction_handle, tb->tb_sb, bh->b_blocknr);
1639 */
1640
1641 store_thrown (tb, bh);
1642 }
1643
1644 /* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
1645 void replace_key (struct tree_balance * tb, struct buffer_head * dest, int n_dest,
1646 struct buffer_head * src, int n_src)
1647 {
1648
1649 #ifdef CONFIG_REISERFS_CHECK
1650 if (dest == NULL || src == NULL)
1651 reiserfs_panic (0, "vs-12305: replace_key: sourse or destination buffer is 0 (src=%p, dest=%p)", src, dest);
1652
1653 if ( ! B_IS_KEYS_LEVEL (dest) )
1654 reiserfs_panic (0, "vs-12310: replace_key: invalid level (%z) for destination buffer. dest must be leaf",
1655 dest);
1656
1657 if (n_dest < 0 || n_src < 0)
1658 reiserfs_panic (0, "vs-12315: replace_key: src(%d) or dest(%d) key number less than 0", n_src, n_dest);
1659
1660 if (n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src))
1661 reiserfs_panic (0, "vs-12320: replace_key: src(%d(%d)) or dest(%d(%d)) key number is too big",
1662 n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
1663 #endif /* CONFIG_REISERFS_CHECK */
1664
1665 if (B_IS_ITEMS_LEVEL (src))
1666 /* source buffer contains leaf node */
1667 memcpy (B_N_PDELIM_KEY(dest,n_dest), B_N_PITEM_HEAD(src,n_src), KEY_SIZE);
1668 else
1669 memcpy (B_N_PDELIM_KEY(dest,n_dest), B_N_PDELIM_KEY(src,n_src), KEY_SIZE);
1670
1671 do_balance_mark_internal_dirty (tb, dest, 0);
1672 }
1673
1674
1675 int get_left_neighbor_position (
1676 struct tree_balance * tb,
1677 int h
1678 )
1679 {
1680 int Sh_position = PATH_H_POSITION (tb->tb_path, h + 1);
1681
1682 #ifdef CONFIG_REISERFS_CHECK
1683 if (PATH_H_PPARENT (tb->tb_path, h) == 0 || tb->FL[h] == 0)
1684 reiserfs_panic (tb->tb_sb, "vs-12325: get_left_neighbor_position: FL[%d](%p) or F[%d](%p) does not exist",
1685 h, tb->FL[h], h, PATH_H_PPARENT (tb->tb_path, h));
1686 #endif
1687
1688 if (Sh_position == 0)
1689 return B_NR_ITEMS (tb->FL[h]);
1690 else
1691 return Sh_position - 1;
1692 }
1693
1694
1695 int get_right_neighbor_position (struct tree_balance * tb, int h)
1696 {
1697 int Sh_position = PATH_H_POSITION (tb->tb_path, h + 1);
1698
1699 #ifdef CONFIG_REISERFS_CHECK
1700 if (PATH_H_PPARENT (tb->tb_path, h) == 0 || tb->FR[h] == 0)
1701 reiserfs_panic (tb->tb_sb, "vs-12330: get_right_neighbor_position: F[%d](%p) or FR[%d](%p) does not exist",
1702 h, PATH_H_PPARENT (tb->tb_path, h), h, tb->FR[h]);
1703 #endif
1704
1705 if (Sh_position == B_NR_ITEMS (PATH_H_PPARENT (tb->tb_path, h)))
1706 return 0;
1707 else
1708 return Sh_position + 1;
1709 }
1710
1711
1712 #ifdef CONFIG_REISERFS_CHECK
1713
1714 int is_reusable (struct super_block * s, unsigned long block, int bit_value);
1715 static void check_internal_node (struct super_block * s, struct buffer_head * bh, char * mes)
1716 {
1717 struct disk_child * dc;
1718 int i;
1719
1720 if (!bh)
1721 reiserfs_panic (s, "PAP-12336: check_internal_node: bh == 0");
1722
1723 if (!bh || !B_IS_IN_TREE (bh))
1724 return;
1725
1726 if (!buffer_dirty (bh) &&
1727 !(buffer_journaled(bh) || buffer_journal_dirty(bh))) {
1728 reiserfs_panic (s, "PAP-12337: check_internal_node: buffer (%b) must be dirty", bh);
1729 }
1730
1731 dc = B_N_CHILD (bh, 0);
1732
1733 for (i = 0; i <= B_NR_ITEMS (bh); i ++, dc ++) {
1734 if (!is_reusable (s, dc->dc_block_number, 1) ) {
1735 print_cur_tb (mes);
1736 reiserfs_panic (s, "PAP-12338: check_internal_node: invalid child pointer %y in %b", dc, bh);
1737 }
1738 }
1739 }
1740
1741
1742 static int locked_or_not_in_tree (struct buffer_head * bh, char * which)
1743 {
1744 if ( buffer_locked (bh) || !B_IS_IN_TREE (bh) ) {
1745 reiserfs_warning ("vs-12339: locked_or_not_in_tree: %s (%b)\n", which, bh);
1746 return 1;
1747 }
1748 return 0;
1749 }
1750
1751
1752 static int check_before_balancing (struct tree_balance * tb)
1753 {
1754 int retval = 0;
1755
1756 if ( cur_tb ) {
1757 reiserfs_panic (tb->tb_sb, "vs-12335: check_before_balancing: "
1758 "suspect that schedule occurred based on cur_tb not being null at this point in code. "
1759 "do_balance cannot properly handle schedule occuring while it runs.");
1760 }
1761
1762 /* double check that buffers that we will modify are unlocked. (fix_nodes should already have
1763 prepped all of these for us). */
1764 if ( tb->lnum[0] ) {
1765 retval |= locked_or_not_in_tree (tb->L[0], "L[0]");
1766 retval |= locked_or_not_in_tree (tb->FL[0], "FL[0]");
1767 retval |= locked_or_not_in_tree (tb->CFL[0], "CFL[0]");
1768 check_leaf (tb->L[0]);
1769 }
1770 if ( tb->rnum[0] ) {
1771 retval |= locked_or_not_in_tree (tb->R[0], "R[0]");
1772 retval |= locked_or_not_in_tree (tb->FR[0], "FR[0]");
1773 retval |= locked_or_not_in_tree (tb->CFR[0], "CFR[0]");
1774 check_leaf (tb->R[0]);
1775 }
1776 retval |= locked_or_not_in_tree (PATH_PLAST_BUFFER (tb->tb_path), "S[0]");
1777 check_leaf (PATH_PLAST_BUFFER (tb->tb_path));
1778
1779 return retval;
1780 }
1781
1782
1783 void check_after_balance_leaf (struct tree_balance * tb)
1784 {
1785 if (tb->lnum[0]) {
1786 if (B_FREE_SPACE (tb->L[0]) !=
1787 MAX_CHILD_SIZE (tb->L[0]) - B_N_CHILD (tb->FL[0], get_left_neighbor_position (tb, 0))->dc_size) {
1788 print_cur_tb ("12221");
1789 reiserfs_panic (tb->tb_sb, "PAP-12355: check_after_balance_leaf: shift to left was incorrect");
1790 }
1791 }
1792 if (tb->rnum[0]) {
1793 if (B_FREE_SPACE (tb->R[0]) !=
1794 MAX_CHILD_SIZE (tb->R[0]) - B_N_CHILD (tb->FR[0], get_right_neighbor_position (tb, 0))->dc_size) {
1795 print_cur_tb ("12222");
1796 reiserfs_panic (tb->tb_sb, "PAP-12360: check_after_balance_leaf: shift to right was incorrect");
1797 }
1798 }
1799 if (PATH_H_PBUFFER(tb->tb_path,1) && (B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) !=
1800 (MAX_CHILD_SIZE (PATH_H_PBUFFER(tb->tb_path,0)) -
1801 B_N_CHILD (PATH_H_PBUFFER(tb->tb_path,1),
1802 PATH_H_POSITION (tb->tb_path, 1))->dc_size))) {
1803 print_cur_tb ("12223");
1804 reiserfs_panic (tb->tb_sb, "PAP-12365: check_after_balance_leaf: S is incorrect");
1805 }
1806 }
1807
1808
1809 void check_leaf_level (struct tree_balance * tb)
1810 {
1811 check_leaf (tb->L[0]);
1812 check_leaf (tb->R[0]);
1813 check_leaf (PATH_PLAST_BUFFER (tb->tb_path));
1814 }
1815
1816 void check_internal_levels (struct tree_balance * tb)
1817 {
1818 int h;
1819
1820 /* check all internal nodes */
1821 for (h = 1; tb->insert_size[h]; h ++) {
1822 check_internal_node (tb->tb_sb, PATH_H_PBUFFER (tb->tb_path, h), "BAD BUFFER ON PATH");
1823 if (tb->lnum[h])
1824 check_internal_node (tb->tb_sb, tb->L[h], "BAD L");
1825 if (tb->rnum[h])
1826 check_internal_node (tb->tb_sb, tb->R[h], "BAD R");
1827 }
1828
1829 }
1830
1831 #endif
1832
1833
1834
1835
1836
1837
1838 /* Now we have all of the buffers that must be used in balancing of
1839 the tree. We rely on the assumption that schedule() will not occur
1840 while do_balance works. ( Only interrupt handlers are acceptable.)
1841 We balance the tree according to the analysis made before this,
1842 using buffers already obtained. For SMP support it will someday be
1843 necessary to add ordered locking of tb. */
1844
1845 /* Some interesting rules of balancing:
1846
1847 we delete a maximum of two nodes per level per balancing: we never
1848 delete R, when we delete two of three nodes L, S, R then we move
1849 them into R.
1850
1851 we only delete L if we are deleting two nodes, if we delete only
1852 one node we delete S
1853
1854 if we shift leaves then we shift as much as we can: this is a
1855 deliberate policy of extremism in node packing which results in
1856 higher average utilization after repeated random balance operations
1857 at the cost of more memory copies and more balancing as a result of
1858 small insertions to full nodes.
1859
1860 if we shift internal nodes we try to evenly balance the node
1861 utilization, with consequent less balancing at the cost of lower
1862 utilization.
1863
1864 one could argue that the policy for directories in leaves should be
1865 that of internal nodes, but we will wait until another day to
1866 evaluate this.... It would be nice to someday measure and prove
1867 these assumptions as to what is optimal....
1868
1869 */
1870
1871 static inline void do_balance_starts (struct tree_balance *tb)
1872 {
1873 /* use print_cur_tb() to see initial state of struct
1874 tree_balance */
1875
1876 /* store_print_tb (tb); */
1877
1878 #ifdef CONFIG_REISERFS_CHECK
1879
1880 /* do not delete, just comment it out */
1881 /* print_tb(flag, PATH_LAST_POSITION(tb->tb_path), tb->tb_path->pos_in_item, tb,
1882 "check");*/
1883
1884 if (check_before_balancing (tb))
1885 reiserfs_panic (tb->tb_sb, "PAP-12340: do_balance: locked buffers in TB");
1886
1887 cur_tb = tb;
1888
1889 #endif /* CONFIG_REISERFS_CHECK */
1890 }
1891
1892
1893 static inline void do_balance_completed (struct tree_balance * tb)
1894 {
1895
1896 #ifdef CONFIG_REISERFS_CHECK
1897 check_leaf_level (tb);
1898 check_internal_levels (tb);
1899 cur_tb = NULL;
1900 #endif
1901
1902 /* reiserfs_free_block is no longer schedule safe. So, we need to
1903 ** put the buffers we want freed on the thrown list during do_balance,
1904 ** and then free them now
1905 */
1906
1907 tb->tb_sb->u.reiserfs_sb.s_do_balance ++;
1908
1909
1910 /* release all nodes hold to perform the balancing */
1911 unfix_nodes(tb);
1912
1913 free_thrown(tb) ;
1914 }
1915
1916
1917
1918
1919
1920 void do_balance (struct tree_balance * tb, /* tree_balance structure */
1921 struct item_head * ih, /* item header of inserted item */
1922 const char * body, /* body of inserted item or bytes to paste */
1923 int flag) /* i - insert, d - delete
1924 c - cut, p - paste
1925
1926 Cut means delete part of an item
1927 (includes removing an entry from a
1928 directory).
1929
1930 Delete means delete whole item.
1931
1932 Insert means add a new item into the
1933 tree.
1934
1935 Paste means to append to the end of an
1936 existing file or to insert a directory
1937 entry. */
1938 {
1939 int child_pos, /* position of a child node in its parent */
1940 h; /* level of the tree being processed */
1941 struct item_head insert_key[2]; /* in our processing of one level
1942 we sometimes determine what
1943 must be inserted into the next
1944 higher level. This insertion
1945 consists of a key or two keys
1946 and their corresponding
1947 pointers */
1948 struct buffer_head *insert_ptr[2]; /* inserted node-ptrs for the next
1949 level */
1950
1951 tb->tb_mode = flag;
1952 tb->need_balance_dirty = 0;
1953
1954 if (FILESYSTEM_CHANGED_TB(tb)) {
1955 reiserfs_panic(tb->tb_sb, "clm-6000: do_balance, fs generation has changed\n") ;
1956 }
1957 /* if we have no real work to do */
1958 if ( ! tb->insert_size[0] ) {
1959 reiserfs_warning ("PAP-12350: do_balance: insert_size == 0, mode == %c",
1960 flag);
1961 unfix_nodes(tb);
1962 return;
1963 }
1964
1965 atomic_inc (&(fs_generation (tb->tb_sb)));
1966 do_balance_starts (tb);
1967
1968 /* balance leaf returns 0 except if combining L R and S into
1969 one node. see balance_internal() for explanation of this
1970 line of code.*/
1971 child_pos = PATH_H_B_ITEM_ORDER (tb->tb_path, 0) +
1972 balance_leaf (tb, ih, body, flag, insert_key, insert_ptr);
1973
1974 #ifdef CONFIG_REISERFS_CHECK
1975 check_after_balance_leaf (tb);
1976 #endif
1977
1978 /* Balance internal level of the tree. */
1979 for ( h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++ )
1980 child_pos = balance_internal (tb, h, child_pos, insert_key, insert_ptr);
1981
1982
1983 do_balance_completed (tb);
1984
1985 }
1986