~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/reiserfs/do_balan.c

Version: ~ [ linux-5.4-rc3 ] ~ [ linux-5.3.6 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.79 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.149 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.196 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.196 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.75 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp