OpenCores
URL https://opencores.org/ocsvn/test_project/test_project/trunk

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [fs/] [reiserfs/] [do_balan.c] - Blame information for rev 62

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2025 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.