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