blob: bfed0f6d9185a0d82ba59fcefdb05258fe51578f [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
Jeff Mahoney098297b2014-04-23 10:00:36 -04005/*
6 * Now we have all buffers that must be used in balancing of the tree
7 * Further calculations can not cause schedule(), and thus the buffer
8 * tree will be stable until the balancing will be finished
9 * balance the tree according to the analysis made before,
10 * and using buffers obtained after all above.
11 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070012
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <asm/uaccess.h>
14#include <linux/time.h>
Al Virof466c6f2012-03-17 01:16:43 -040015#include "reiserfs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070016#include <linux/buffer_head.h>
Ahmed S. Darwish79a81ae2007-02-12 00:52:09 -080017#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070018
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -040019static inline void buffer_info_init_left(struct tree_balance *tb,
20 struct buffer_info *bi)
21{
22 bi->tb = tb;
23 bi->bi_bh = tb->L[0];
24 bi->bi_parent = tb->FL[0];
25 bi->bi_position = get_left_neighbor_position(tb, 0);
26}
27
28static inline void buffer_info_init_right(struct tree_balance *tb,
29 struct buffer_info *bi)
30{
31 bi->tb = tb;
32 bi->bi_bh = tb->R[0];
33 bi->bi_parent = tb->FR[0];
34 bi->bi_position = get_right_neighbor_position(tb, 0);
35}
36
37static inline void buffer_info_init_tbS0(struct tree_balance *tb,
38 struct buffer_info *bi)
39{
40 bi->tb = tb;
41 bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
42 bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
43 bi->bi_position = PATH_H_POSITION(tb->tb_path, 1);
44}
45
46static inline void buffer_info_init_bh(struct tree_balance *tb,
47 struct buffer_info *bi,
48 struct buffer_head *bh)
49{
50 bi->tb = tb;
51 bi->bi_bh = bh;
52 bi->bi_parent = NULL;
53 bi->bi_position = 0;
54}
55
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070056inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
57 struct buffer_head *bh, int flag)
Linus Torvalds1da177e2005-04-16 15:20:36 -070058{
Jeff Mahoney09f1b802014-04-23 10:00:39 -040059 journal_mark_dirty(tb->transaction_handle, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -070060}
61
62#define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
63#define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
64
Jeff Mahoney098297b2014-04-23 10:00:36 -040065/*
66 * summary:
67 * if deleting something ( tb->insert_size[0] < 0 )
68 * return(balance_leaf_when_delete()); (flag d handled here)
69 * else
70 * if lnum is larger than 0 we put items into the left node
71 * if rnum is larger than 0 we put items into the right node
72 * if snum1 is larger than 0 we put items into the new node s1
73 * if snum2 is larger than 0 we put items into the new node s2
74 * Note that all *num* count new items being created.
75 *
76 * It would be easier to read balance_leaf() if each of these summary
77 * lines was a separate procedure rather than being inlined. I think
78 * that there are many passages here and in balance_leaf_when_delete() in
79 * which two calls to one procedure can replace two passages, and it
80 * might save cache space and improve software maintenance costs to do so.
81 *
82 * Vladimir made the perceptive comment that we should offload most of
83 * the decision making in this function into fix_nodes/check_balance, and
84 * then create some sort of structure in tb that says what actions should
85 * be performed by do_balance.
86 *
87 * -Hans
88 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
Jeff Mahoney098297b2014-04-23 10:00:36 -040090/*
91 * Balance leaf node in case of delete or cut: insert_size[0] < 0
Linus Torvalds1da177e2005-04-16 15:20:36 -070092 *
93 * lnum, rnum can have values >= -1
94 * -1 means that the neighbor must be joined with S
95 * 0 means that nothing should be done with the neighbor
Jeff Mahoney098297b2014-04-23 10:00:36 -040096 * >0 means to shift entirely or partly the specified number of items
97 * to the neighbor
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070099static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700100{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700101 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
102 int item_pos = PATH_LAST_POSITION(tb->tb_path);
103 int pos_in_item = tb->tb_path->pos_in_item;
104 struct buffer_info bi;
105 int n;
106 struct item_head *ih;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700107
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700108 RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1,
109 "vs- 12000: level: wrong FR %z", tb->FR[0]);
110 RFALSE(tb->blknum[0] > 1,
111 "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]);
112 RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0),
113 "PAP-12010: tree can not be empty");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400115 ih = item_head(tbS0, item_pos);
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400116 buffer_info_init_tbS0(tb, &bi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700117
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700118 /* Delete or truncate the item */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700120 switch (flag) {
121 case M_DELETE: /* delete item in S[0] */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700122
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700123 RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0],
124 "vs-12013: mode Delete, insert size %d, ih to be deleted %h",
125 -tb->insert_size[0], ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700127 leaf_delete_items(&bi, 0, item_pos, 1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700129 if (!item_pos && tb->CFL[0]) {
130 if (B_NR_ITEMS(tbS0)) {
131 replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0,
132 0);
133 } else {
134 if (!PATH_H_POSITION(tb->tb_path, 1))
135 replace_key(tb, tb->CFL[0], tb->lkey[0],
136 PATH_H_PPARENT(tb->tb_path,
137 0), 0);
138 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700139 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700141 RFALSE(!item_pos && !tb->CFL[0],
142 "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0],
143 tb->L[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700145 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700147 case M_CUT:{ /* cut item in S[0] */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700148 if (is_direntry_le_ih(ih)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
Jeff Mahoney098297b2014-04-23 10:00:36 -0400150 /*
151 * UFS unlink semantics are such that you
152 * can only delete one directory entry at
153 * a time.
154 */
155
156 /*
157 * when we cut a directory tb->insert_size[0]
158 * means number of entries to be cut (always 1)
159 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700160 tb->insert_size[0] = -1;
161 leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
162 -tb->insert_size[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700164 RFALSE(!item_pos && !pos_in_item && !tb->CFL[0],
165 "PAP-12030: can not change delimiting key. CFL[0]=%p",
166 tb->CFL[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700168 if (!item_pos && !pos_in_item && tb->CFL[0]) {
169 replace_key(tb, tb->CFL[0], tb->lkey[0],
170 tbS0, 0);
171 }
172 } else {
173 leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
174 -tb->insert_size[0]);
175
176 RFALSE(!ih_item_len(ih),
177 "PAP-12035: cut must leave non-zero dynamic length of item");
178 }
179 break;
180 }
181
182 default:
183 print_cur_tb("12040");
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400184 reiserfs_panic(tb->tb_sb, "PAP-12040",
185 "unexpected mode: %s(%d)",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700186 (flag ==
187 M_PASTE) ? "PASTE" : ((flag ==
188 M_INSERT) ? "INSERT" :
189 "UNKNOWN"), flag);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700190 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191
Jeff Mahoney098297b2014-04-23 10:00:36 -0400192 /*
193 * the rule is that no shifting occurs unless by shifting
194 * a node can be freed
195 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700196 n = B_NR_ITEMS(tbS0);
Jeff Mahoney098297b2014-04-23 10:00:36 -0400197 /* L[0] takes part in balancing */
198 if (tb->lnum[0]) {
199 /* L[0] must be joined with S[0] */
200 if (tb->lnum[0] == -1) {
201 /* R[0] must be also joined with S[0] */
202 if (tb->rnum[0] == -1) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700203 if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400204 /*
205 * all contents of all the 3 buffers
206 * will be in L[0]
207 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700208 if (PATH_H_POSITION(tb->tb_path, 1) == 0
209 && 1 < B_NR_ITEMS(tb->FR[0]))
210 replace_key(tb, tb->CFL[0],
211 tb->lkey[0],
212 tb->FR[0], 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700213
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700214 leaf_move_items(LEAF_FROM_S_TO_L, tb, n,
215 -1, NULL);
216 leaf_move_items(LEAF_FROM_R_TO_L, tb,
217 B_NR_ITEMS(tb->R[0]),
218 -1, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700220 reiserfs_invalidate_buffer(tb, tbS0);
221 reiserfs_invalidate_buffer(tb,
222 tb->R[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700224 return 0;
225 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400226 /*
227 * all contents of all the 3 buffers will
228 * be in R[0]
229 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700230 leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1,
231 NULL);
232 leaf_move_items(LEAF_FROM_L_TO_R, tb,
233 B_NR_ITEMS(tb->L[0]), -1, NULL);
234
235 /* right_delimiting_key is correct in R[0] */
236 replace_key(tb, tb->CFR[0], tb->rkey[0],
237 tb->R[0], 0);
238
239 reiserfs_invalidate_buffer(tb, tbS0);
240 reiserfs_invalidate_buffer(tb, tb->L[0]);
241
242 return -1;
243 }
244
245 RFALSE(tb->rnum[0] != 0,
246 "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]);
247 /* all contents of L[0] and S[0] will be in L[0] */
248 leaf_shift_left(tb, n, -1);
249
250 reiserfs_invalidate_buffer(tb, tbS0);
251
252 return 0;
253 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400254
255 /*
256 * a part of contents of S[0] will be in L[0] and the
257 * rest part of S[0] will be in R[0]
258 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700259
260 RFALSE((tb->lnum[0] + tb->rnum[0] < n) ||
261 (tb->lnum[0] + tb->rnum[0] > n + 1),
262 "PAP-12050: rnum(%d) and lnum(%d) and item number(%d) in S[0] are not consistent",
263 tb->rnum[0], tb->lnum[0], n);
264 RFALSE((tb->lnum[0] + tb->rnum[0] == n) &&
265 (tb->lbytes != -1 || tb->rbytes != -1),
266 "PAP-12055: bad rbytes (%d)/lbytes (%d) parameters when items are not split",
267 tb->rbytes, tb->lbytes);
268 RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) &&
269 (tb->lbytes < 1 || tb->rbytes != -1),
270 "PAP-12060: bad rbytes (%d)/lbytes (%d) parameters when items are split",
271 tb->rbytes, tb->lbytes);
272
273 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
274 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
275
276 reiserfs_invalidate_buffer(tb, tbS0);
277
278 return 0;
279 }
280
281 if (tb->rnum[0] == -1) {
282 /* all contents of R[0] and S[0] will be in R[0] */
283 leaf_shift_right(tb, n, -1);
284 reiserfs_invalidate_buffer(tb, tbS0);
285 return 0;
286 }
287
288 RFALSE(tb->rnum[0],
289 "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700290 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700291}
292
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700293static int balance_leaf(struct tree_balance *tb, struct item_head *ih, /* item header of inserted item (this is on little endian) */
294 const char *body, /* body of inserted item or bytes to paste */
295 int flag, /* i - insert, d - delete, c - cut, p - paste
296 (see comment to do_balance) */
297 struct item_head *insert_key, /* in our processing of one level we sometimes determine what
298 must be inserted into the next higher level. This insertion
299 consists of a key or two keys and their corresponding
300 pointers */
301 struct buffer_head **insert_ptr /* inserted node-ptrs for the next level */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302 )
303{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700304 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
Jeff Mahoney0222e652009-03-30 14:02:44 -0400305 int item_pos = PATH_LAST_POSITION(tb->tb_path); /* index into the array of item headers in S[0]
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700306 of the affected item */
307 struct buffer_info bi;
308 struct buffer_head *S_new[2]; /* new nodes allocated to hold what could not fit into S */
309 int snum[2]; /* number of items that will be placed
310 into S_new (includes partially shifted
311 items) */
Jeff Mahoney0222e652009-03-30 14:02:44 -0400312 int sbytes[2]; /* if an item is partially shifted into S_new then
313 if it is a directory item
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700314 it is the number of entries from the item that are shifted into S_new
315 else
316 it is the number of bytes from the item that are shifted into S_new
317 */
318 int n, i;
319 int ret_val;
320 int pos_in_item;
321 int zeros_num;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700322
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700323 PROC_INFO_INC(tb->tb_sb, balance_at[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700324
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700325 /* Make balance in case insert_size[0] < 0 */
326 if (tb->insert_size[0] < 0)
327 return balance_leaf_when_delete(tb, flag);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700329 zeros_num = 0;
Al Viro9dce07f2008-03-29 03:07:28 +0000330 if (flag == M_INSERT && !body)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700331 zeros_num = ih_item_len(ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700332
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700333 pos_in_item = tb->tb_path->pos_in_item;
334 /* for indirect item pos_in_item is measured in unformatted node
335 pointers. Recalculate to bytes */
336 if (flag != M_INSERT
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400337 && is_indirect_le_ih(item_head(tbS0, item_pos)))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700338 pos_in_item *= UNFM_P_SIZE;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700340 if (tb->lnum[0] > 0) {
341 /* Shift lnum[0] items from S[0] to the left neighbor L[0] */
342 if (item_pos < tb->lnum[0]) {
343 /* new item or it part falls to L[0], shift it too */
344 n = B_NR_ITEMS(tb->L[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700345
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700346 switch (flag) {
347 case M_INSERT: /* insert item into L[0] */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348
Dave Jones416e2ab2014-02-17 16:21:24 -0500349 if (item_pos == tb->lnum[0] - 1 && tb->lbytes != -1) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700350 /* part of new item falls into L[0] */
351 int new_item_len;
352 int version;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353
Dave Jones416e2ab2014-02-17 16:21:24 -0500354 ret_val = leaf_shift_left(tb, tb->lnum[0] - 1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700355
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700356 /* Calculate item length to insert to S[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500357 new_item_len = ih_item_len(ih) - tb->lbytes;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700358 /* Calculate and check item length to insert to L[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500359 put_ih_item_len(ih, ih_item_len(ih) - new_item_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700360
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700361 RFALSE(ih_item_len(ih) <= 0,
362 "PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d",
363 ih_item_len(ih));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700364
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700365 /* Insert new item into L[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400366 buffer_info_init_left(tb, &bi);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700367 leaf_insert_into_buf(&bi,
Dave Jones416e2ab2014-02-17 16:21:24 -0500368 n + item_pos - ret_val, ih, body,
369 zeros_num > ih_item_len(ih) ? ih_item_len(ih) : zeros_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700371 version = ih_version(ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700372
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700373 /* Calculate key component, item length and body to insert into S[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500374 set_le_ih_k_offset(ih, le_ih_k_offset(ih) +
375 (tb-> lbytes << (is_indirect_le_ih(ih) ? tb->tb_sb-> s_blocksize_bits - UNFM_P_SHIFT : 0)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700377 put_ih_item_len(ih, new_item_len);
378 if (tb->lbytes > zeros_num) {
Dave Jones416e2ab2014-02-17 16:21:24 -0500379 body += (tb->lbytes - zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700380 zeros_num = 0;
381 } else
382 zeros_num -= tb->lbytes;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700383
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700384 RFALSE(ih_item_len(ih) <= 0,
385 "PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d",
386 ih_item_len(ih));
387 } else {
388 /* new item in whole falls into L[0] */
389 /* Shift lnum[0]-1 items to L[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500390 ret_val = leaf_shift_left(tb, tb->lnum[0] - 1, tb->lbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700391 /* Insert new item into L[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400392 buffer_info_init_left(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -0500393 leaf_insert_into_buf(&bi, n + item_pos - ret_val, ih, body, zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700394 tb->insert_size[0] = 0;
395 zeros_num = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700397 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700399 case M_PASTE: /* append item in L[0] */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700400
Dave Jones416e2ab2014-02-17 16:21:24 -0500401 if (item_pos == tb->lnum[0] - 1 && tb->lbytes != -1) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700402 /* we must shift the part of the appended item */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400403 if (is_direntry_le_ih(item_head(tbS0, item_pos))) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700404
405 RFALSE(zeros_num,
406 "PAP-12090: invalid parameter in case of a directory");
407 /* directory item */
408 if (tb->lbytes > pos_in_item) {
409 /* new directory entry falls into L[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500410 struct item_head *pasted;
411 int l_pos_in_item = pos_in_item;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700412
413 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 entries from given directory item */
Dave Jones416e2ab2014-02-17 16:21:24 -0500414 ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes-1);
415 if (ret_val && !item_pos) {
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400416 pasted = item_head(tb->L[0], B_NR_ITEMS(tb->L[0]) - 1);
417 l_pos_in_item += ih_entry_count(pasted) - (tb->lbytes -1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700418 }
419
420 /* Append given directory entry to directory item */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400421 buffer_info_init_left(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -0500422 leaf_paste_in_buffer(&bi, n + item_pos - ret_val, l_pos_in_item, tb->insert_size[0], body, zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700423
424 /* previous string prepared space for pasting new entry, following string pastes this entry */
425
426 /* when we have merge directory item, pos_in_item has been changed too */
427
428 /* paste new directory entry. 1 is entry number */
Dave Jones416e2ab2014-02-17 16:21:24 -0500429 leaf_paste_entries(&bi, n + item_pos - ret_val, l_pos_in_item,
430 1, (struct reiserfs_de_head *) body,
431 body + DEH_SIZE, tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700432 tb->insert_size[0] = 0;
433 } else {
434 /* new directory item doesn't fall into L[0] */
435 /* Shift lnum[0]-1 items in whole. Shift lbytes directory entries from directory item number lnum[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500436 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700437 }
438 /* Calculate new position to append in item body */
439 pos_in_item -= tb->lbytes;
440 } else {
441 /* regular object */
Dave Jones416e2ab2014-02-17 16:21:24 -0500442 RFALSE(tb->lbytes <= 0, "PAP-12095: there is nothing to shift to L[0]. lbytes=%d", tb->lbytes);
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400443 RFALSE(pos_in_item != ih_item_len(item_head(tbS0, item_pos)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700444 "PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400445 ih_item_len(item_head(tbS0, item_pos)),pos_in_item);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700446
447 if (tb->lbytes >= pos_in_item) {
448 /* appended item will be in L[0] in whole */
449 int l_n;
450
451 /* this bytes number must be appended to the last item of L[h] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500452 l_n = tb->lbytes - pos_in_item;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700453
454 /* Calculate new insert_size[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500455 tb->insert_size[0] -= l_n;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700456
Dave Jones416e2ab2014-02-17 16:21:24 -0500457 RFALSE(tb->insert_size[0] <= 0,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700458 "PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
Dave Jones416e2ab2014-02-17 16:21:24 -0500459 tb->insert_size[0]);
460 ret_val = leaf_shift_left(tb, tb->lnum[0], ih_item_len
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400461 (item_head(tbS0, item_pos)));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700462 /* Append to body of item in L[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400463 buffer_info_init_left(tb, &bi);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700464 leaf_paste_in_buffer
Dave Jones416e2ab2014-02-17 16:21:24 -0500465 (&bi, n + item_pos - ret_val, ih_item_len
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400466 (item_head(tb->L[0], n + item_pos - ret_val)),
Dave Jones416e2ab2014-02-17 16:21:24 -0500467 l_n, body,
468 zeros_num > l_n ? l_n : zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700469 /* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
470 {
471 int version;
Dave Jones416e2ab2014-02-17 16:21:24 -0500472 int temp_l = l_n;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700473
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400474 RFALSE(ih_item_len(item_head(tbS0, 0)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700475 "PAP-12106: item length must be 0");
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400476 RFALSE(comp_short_le_keys(leaf_key(tbS0, 0), leaf_key
Dave Jones416e2ab2014-02-17 16:21:24 -0500477 (tb->L[0], n + item_pos - ret_val)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700478 "PAP-12107: items must be of the same file");
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400479 if (is_indirect_le_ih(item_head(tb->L[0], n + item_pos - ret_val))) {
Dave Jones416e2ab2014-02-17 16:21:24 -0500480 temp_l = l_n << (tb->tb_sb-> s_blocksize_bits - UNFM_P_SHIFT);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700481 }
482 /* update key of first item in S0 */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400483 version = ih_version(item_head(tbS0, 0));
484 set_le_key_k_offset(version, leaf_key(tbS0, 0),
485 le_key_k_offset(version,leaf_key(tbS0, 0)) + temp_l);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700486 /* update left delimiting key */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400487 set_le_key_k_offset(version, internal_key(tb->CFL[0], tb->lkey[0]),
488 le_key_k_offset(version, internal_key(tb->CFL[0], tb->lkey[0])) + temp_l);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700489 }
490
491 /* Calculate new body, position in item and insert_size[0] */
492 if (l_n > zeros_num) {
Dave Jones416e2ab2014-02-17 16:21:24 -0500493 body += (l_n - zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700494 zeros_num = 0;
495 } else
Dave Jones416e2ab2014-02-17 16:21:24 -0500496 zeros_num -= l_n;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700497 pos_in_item = 0;
498
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400499 RFALSE(comp_short_le_keys(leaf_key(tbS0, 0), leaf_key(tb->L[0], B_NR_ITEMS(tb->L[0]) - 1))
500 || !op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size)
501 || !op_is_left_mergeable(internal_key(tb->CFL[0], tb->lkey[0]), tbS0->b_size),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700502 "PAP-12120: item must be merge-able with left neighboring item");
503 } else { /* only part of the appended item will be in L[0] */
504
505 /* Calculate position in item for append in S[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500506 pos_in_item -= tb->lbytes;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700507
Dave Jones416e2ab2014-02-17 16:21:24 -0500508 RFALSE(pos_in_item <= 0, "PAP-12125: no place for paste. pos_in_item=%d", pos_in_item);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700509
510 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500511 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700512 }
513 }
514 } else { /* appended item will be in L[0] in whole */
515
516 struct item_head *pasted;
517
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400518 if (!item_pos && op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size)) { /* if we paste into first item of S[0] and it is left mergable */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700519 /* then increment pos_in_item by the size of the last item in L[0] */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400520 pasted = item_head(tb->L[0], n - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700521 if (is_direntry_le_ih(pasted))
Dave Jones416e2ab2014-02-17 16:21:24 -0500522 pos_in_item += ih_entry_count(pasted);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700523 else
Dave Jones416e2ab2014-02-17 16:21:24 -0500524 pos_in_item += ih_item_len(pasted);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700525 }
526
527 /* Shift lnum[0] - 1 items in whole. Shift lbytes - 1 byte from item number lnum[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500528 ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700529 /* Append to body of item in L[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400530 buffer_info_init_left(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -0500531 leaf_paste_in_buffer(&bi, n + item_pos - ret_val,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700532 pos_in_item,
533 tb->insert_size[0],
534 body, zeros_num);
535
536 /* if appended item is directory, paste entry */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400537 pasted = item_head(tb->L[0], n + item_pos - ret_val);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700538 if (is_direntry_le_ih(pasted))
Dave Jones416e2ab2014-02-17 16:21:24 -0500539 leaf_paste_entries(&bi, n + item_pos - ret_val,
540 pos_in_item, 1,
541 (struct reiserfs_de_head *) body,
542 body + DEH_SIZE,
543 tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700544 /* if appended item is indirect item, put unformatted node into un list */
545 if (is_indirect_le_ih(pasted))
546 set_ih_free_space(pasted, 0);
547 tb->insert_size[0] = 0;
548 zeros_num = 0;
549 }
550 break;
551 default: /* cases d and t */
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400552 reiserfs_panic(tb->tb_sb, "PAP-12130",
553 "lnum > 0: unexpected mode: "
554 " %s(%d)",
Dave Jones416e2ab2014-02-17 16:21:24 -0500555 (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700557 } else {
558 /* new item doesn't fall into L[0] */
559 leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700560 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700562
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700563 /* tb->lnum[0] > 0 */
564 /* Calculate new item position */
565 item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700567 if (tb->rnum[0] > 0) {
568 /* shift rnum[0] items from S[0] to the right neighbor R[0] */
569 n = B_NR_ITEMS(tbS0);
570 switch (flag) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700572 case M_INSERT: /* insert item */
573 if (n - tb->rnum[0] < item_pos) { /* new item or its part falls to R[0] */
574 if (item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) { /* part of new item falls into R[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500575 loff_t old_key_comp, old_len, r_zeros_number;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700576 const char *r_body;
577 int version;
578 loff_t offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579
Dave Jones416e2ab2014-02-17 16:21:24 -0500580 leaf_shift_right(tb, tb->rnum[0] - 1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700582 version = ih_version(ih);
583 /* Remember key component and item length */
584 old_key_comp = le_ih_k_offset(ih);
585 old_len = ih_item_len(ih);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700586
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700587 /* Calculate key component and item length to insert into R[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500588 offset = le_ih_k_offset(ih) + ((old_len - tb->rbytes) << (is_indirect_le_ih(ih) ? tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT : 0));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700589 set_le_ih_k_offset(ih, offset);
590 put_ih_item_len(ih, tb->rbytes);
591 /* Insert part of the item into R[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400592 buffer_info_init_right(tb, &bi);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700593 if ((old_len - tb->rbytes) > zeros_num) {
594 r_zeros_number = 0;
Dave Jones416e2ab2014-02-17 16:21:24 -0500595 r_body = body + (old_len - tb->rbytes) - zeros_num;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700596 } else {
597 r_body = body;
Dave Jones416e2ab2014-02-17 16:21:24 -0500598 r_zeros_number = zeros_num - (old_len - tb->rbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700599 zeros_num -= r_zeros_number;
600 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700601
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700602 leaf_insert_into_buf(&bi, 0, ih, r_body,
603 r_zeros_number);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700604
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700605 /* Replace right delimiting key by first key in R[0] */
606 replace_key(tb, tb->CFR[0], tb->rkey[0],
607 tb->R[0], 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700608
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700609 /* Calculate key component and item length to insert into S[0] */
610 set_le_ih_k_offset(ih, old_key_comp);
Dave Jones416e2ab2014-02-17 16:21:24 -0500611 put_ih_item_len(ih, old_len - tb->rbytes);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700613 tb->insert_size[0] -= tb->rbytes;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700614
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700615 } else { /* whole new item falls into R[0] */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700616
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700617 /* Shift rnum[0]-1 items to R[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500618 ret_val = leaf_shift_right(tb, tb->rnum[0] - 1, tb->rbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700619 /* Insert new item into R[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400620 buffer_info_init_right(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -0500621 leaf_insert_into_buf(&bi, item_pos - n + tb->rnum[0] - 1,
622 ih, body, zeros_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700624 if (item_pos - n + tb->rnum[0] - 1 == 0) {
625 replace_key(tb, tb->CFR[0],
626 tb->rkey[0],
627 tb->R[0], 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700628
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700629 }
630 zeros_num = tb->insert_size[0] = 0;
631 }
632 } else { /* new item or part of it doesn't fall into R[0] */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700633
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700634 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700636 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700638 case M_PASTE: /* append item */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700640 if (n - tb->rnum[0] <= item_pos) { /* pasted item or part of it falls to R[0] */
641 if (item_pos == n - tb->rnum[0] && tb->rbytes != -1) { /* we must shift the part of the appended item */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400642 if (is_direntry_le_ih(item_head(tbS0, item_pos))) { /* we append to directory item */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700643 int entry_count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700645 RFALSE(zeros_num,
646 "PAP-12145: invalid parameter in case of a directory");
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400647 entry_count = ih_entry_count(item_head
Dave Jones416e2ab2014-02-17 16:21:24 -0500648 (tbS0, item_pos));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700649 if (entry_count - tb->rbytes <
650 pos_in_item)
651 /* new directory entry falls into R[0] */
652 {
653 int paste_entry_position;
654
Dave Jones416e2ab2014-02-17 16:21:24 -0500655 RFALSE(tb->rbytes - 1 >= entry_count || !tb-> insert_size[0],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700656 "PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
Dave Jones416e2ab2014-02-17 16:21:24 -0500657 tb->rbytes, entry_count);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700658 /* Shift rnum[0]-1 items in whole. Shift rbytes-1 directory entries from directory item number rnum[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500659 leaf_shift_right(tb, tb->rnum[0], tb->rbytes - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700660 /* Paste given directory entry to directory item */
Dave Jones416e2ab2014-02-17 16:21:24 -0500661 paste_entry_position = pos_in_item - entry_count + tb->rbytes - 1;
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400662 buffer_info_init_right(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -0500663 leaf_paste_in_buffer(&bi, 0, paste_entry_position, tb->insert_size[0], body, zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700664 /* paste entry */
Dave Jones416e2ab2014-02-17 16:21:24 -0500665 leaf_paste_entries(&bi, 0, paste_entry_position, 1,
666 (struct reiserfs_de_head *) body,
667 body + DEH_SIZE, tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700668
Dave Jones416e2ab2014-02-17 16:21:24 -0500669 if (paste_entry_position == 0) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700670 /* change delimiting keys */
Dave Jones416e2ab2014-02-17 16:21:24 -0500671 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0],0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700672 }
673
674 tb->insert_size[0] = 0;
675 pos_in_item++;
676 } else { /* new directory entry doesn't fall into R[0] */
677
Dave Jones416e2ab2014-02-17 16:21:24 -0500678 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700679 }
680 } else { /* regular object */
681
Dave Jones416e2ab2014-02-17 16:21:24 -0500682 int n_shift, n_rem, r_zeros_number;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700683 const char *r_body;
684
685 /* Calculate number of bytes which must be shifted from appended item */
Dave Jones416e2ab2014-02-17 16:21:24 -0500686 if ((n_shift = tb->rbytes - tb->insert_size[0]) < 0)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700687 n_shift = 0;
688
Dave Jones416e2ab2014-02-17 16:21:24 -0500689 RFALSE(pos_in_item != ih_item_len
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400690 (item_head(tbS0, item_pos)),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700691 "PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
Dave Jones416e2ab2014-02-17 16:21:24 -0500692 pos_in_item, ih_item_len
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400693 (item_head(tbS0, item_pos)));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700694
Dave Jones416e2ab2014-02-17 16:21:24 -0500695 leaf_shift_right(tb, tb->rnum[0], n_shift);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700696 /* Calculate number of bytes which must remain in body after appending to R[0] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500697 if ((n_rem = tb->insert_size[0] - tb->rbytes) < 0)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700698 n_rem = 0;
699
700 {
701 int version;
Dave Jones416e2ab2014-02-17 16:21:24 -0500702 unsigned long temp_rem = n_rem;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700703
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400704 version = ih_version(item_head(tb->R[0], 0));
705 if (is_indirect_le_key(version, leaf_key(tb->R[0], 0))) {
Dave Jones416e2ab2014-02-17 16:21:24 -0500706 temp_rem = n_rem << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700707 }
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400708 set_le_key_k_offset(version, leaf_key(tb->R[0], 0),
709 le_key_k_offset(version, leaf_key(tb->R[0], 0)) + temp_rem);
710 set_le_key_k_offset(version, internal_key(tb->CFR[0], tb->rkey[0]),
711 le_key_k_offset(version, internal_key(tb->CFR[0], tb->rkey[0])) + temp_rem);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700712 }
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400713/* k_offset (leaf_key(tb->R[0],0)) += n_rem;
714 k_offset (internal_key(tb->CFR[0],tb->rkey[0])) += n_rem;*/
Dave Jones416e2ab2014-02-17 16:21:24 -0500715 do_balance_mark_internal_dirty(tb, tb->CFR[0], 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700717 /* Append part of body into R[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400718 buffer_info_init_right(tb, &bi);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700719 if (n_rem > zeros_num) {
720 r_zeros_number = 0;
Dave Jones416e2ab2014-02-17 16:21:24 -0500721 r_body = body + n_rem - zeros_num;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700722 } else {
723 r_body = body;
Dave Jones416e2ab2014-02-17 16:21:24 -0500724 r_zeros_number = zeros_num - n_rem;
725 zeros_num -= r_zeros_number;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700726 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700727
Dave Jones416e2ab2014-02-17 16:21:24 -0500728 leaf_paste_in_buffer(&bi, 0, n_shift,
729 tb->insert_size[0] - n_rem,
730 r_body, r_zeros_number);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700731
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400732 if (is_indirect_le_ih(item_head(tb->R[0], 0))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700733#if 0
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700734 RFALSE(n_rem,
735 "PAP-12160: paste more than one unformatted node pointer");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736#endif
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400737 set_ih_free_space(item_head(tb->R[0], 0), 0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700738 }
739 tb->insert_size[0] = n_rem;
740 if (!n_rem)
741 pos_in_item++;
742 }
743 } else { /* pasted item in whole falls into R[0] */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700744
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700745 struct item_head *pasted;
746
Dave Jones416e2ab2014-02-17 16:21:24 -0500747 ret_val = leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700748 /* append item in R[0] */
749 if (pos_in_item >= 0) {
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400750 buffer_info_init_right(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -0500751 leaf_paste_in_buffer(&bi, item_pos - n + tb->rnum[0], pos_in_item,
752 tb->insert_size[0], body, zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700753 }
754
755 /* paste new entry, if item is directory item */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400756 pasted = item_head(tb->R[0], item_pos - n + tb->rnum[0]);
Dave Jones416e2ab2014-02-17 16:21:24 -0500757 if (is_direntry_le_ih(pasted) && pos_in_item >= 0) {
758 leaf_paste_entries(&bi, item_pos - n + tb->rnum[0],
759 pos_in_item, 1,
760 (struct reiserfs_de_head *) body,
761 body + DEH_SIZE, tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700762 if (!pos_in_item) {
763
Dave Jones416e2ab2014-02-17 16:21:24 -0500764 RFALSE(item_pos - n + tb->rnum[0],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700765 "PAP-12165: directory item must be first item of node when pasting is in 0th position");
766
767 /* update delimiting keys */
Dave Jones416e2ab2014-02-17 16:21:24 -0500768 replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700769 }
770 }
771
772 if (is_indirect_le_ih(pasted))
773 set_ih_free_space(pasted, 0);
774 zeros_num = tb->insert_size[0] = 0;
775 }
776 } else { /* new item doesn't fall into R[0] */
777
778 leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
779 }
780 break;
781 default: /* cases d and t */
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400782 reiserfs_panic(tb->tb_sb, "PAP-12175",
783 "rnum > 0: unexpected mode: %s(%d)",
Dave Jones416e2ab2014-02-17 16:21:24 -0500784 (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700785 }
786
787 }
788
789 /* tb->rnum[0] > 0 */
790 RFALSE(tb->blknum[0] > 3,
Dave Jones416e2ab2014-02-17 16:21:24 -0500791 "PAP-12180: blknum can not be %d. It must be <= 3", tb->blknum[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700792 RFALSE(tb->blknum[0] < 0,
Dave Jones416e2ab2014-02-17 16:21:24 -0500793 "PAP-12185: blknum can not be %d. It must be >= 0", tb->blknum[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700794
795 /* if while adding to a node we discover that it is possible to split
796 it in two, and merge the left part into the left neighbor and the
797 right part into the right neighbor, eliminating the node */
798 if (tb->blknum[0] == 0) { /* node S[0] is empty now */
799
800 RFALSE(!tb->lnum[0] || !tb->rnum[0],
801 "PAP-12190: lnum and rnum must not be zero");
802 /* if insertion was done before 0-th position in R[0], right
803 delimiting key of the tb->L[0]'s and left delimiting key are
804 not set correctly */
805 if (tb->CFL[0]) {
806 if (!tb->CFR[0])
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400807 reiserfs_panic(tb->tb_sb, "vs-12195",
808 "CFR not initialized");
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400809 copy_key(internal_key(tb->CFL[0], tb->lkey[0]),
810 internal_key(tb->CFR[0], tb->rkey[0]));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700811 do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
812 }
813
814 reiserfs_invalidate_buffer(tb, tbS0);
815 return 0;
816 }
817
818 /* Fill new nodes that appear in place of S[0] */
819
820 /* I am told that this copying is because we need an array to enable
821 the looping code. -Hans */
822 snum[0] = tb->s1num, snum[1] = tb->s2num;
823 sbytes[0] = tb->s1bytes;
824 sbytes[1] = tb->s2bytes;
825 for (i = tb->blknum[0] - 2; i >= 0; i--) {
826
827 RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i,
828 snum[i]);
829
830 /* here we shift from S to S_new nodes */
831
832 S_new[i] = get_FEB(tb);
833
834 /* initialized block type and tree level */
835 set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
836
837 n = B_NR_ITEMS(tbS0);
838
839 switch (flag) {
840 case M_INSERT: /* insert item */
841
842 if (n - snum[i] < item_pos) { /* new item or it's part falls to first new node S_new[i] */
843 if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) { /* part of new item falls into S_new[i] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500844 int old_key_comp, old_len, r_zeros_number;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700845 const char *r_body;
846 int version;
847
848 /* Move snum[i]-1 items from S[0] to S_new[i] */
849 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
850 snum[i] - 1, -1,
851 S_new[i]);
852 /* Remember key component and item length */
853 version = ih_version(ih);
854 old_key_comp = le_ih_k_offset(ih);
855 old_len = ih_item_len(ih);
856
857 /* Calculate key component and item length to insert into S_new[i] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500858 set_le_ih_k_offset(ih, le_ih_k_offset(ih) +
859 ((old_len - sbytes[i]) << (is_indirect_le_ih(ih) ? tb->tb_sb-> s_blocksize_bits - UNFM_P_SHIFT : 0)));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700860
861 put_ih_item_len(ih, sbytes[i]);
862
863 /* Insert part of the item into S_new[i] before 0-th item */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400864 buffer_info_init_bh(tb, &bi, S_new[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700865
866 if ((old_len - sbytes[i]) > zeros_num) {
867 r_zeros_number = 0;
Dave Jones416e2ab2014-02-17 16:21:24 -0500868 r_body = body + (old_len - sbytes[i]) - zeros_num;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700869 } else {
870 r_body = body;
Dave Jones416e2ab2014-02-17 16:21:24 -0500871 r_zeros_number = zeros_num - (old_len - sbytes[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700872 zeros_num -= r_zeros_number;
873 }
874
Dave Jones416e2ab2014-02-17 16:21:24 -0500875 leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeros_number);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700876
877 /* Calculate key component and item length to insert into S[i] */
878 set_le_ih_k_offset(ih, old_key_comp);
Dave Jones416e2ab2014-02-17 16:21:24 -0500879 put_ih_item_len(ih, old_len - sbytes[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700880 tb->insert_size[0] -= sbytes[i];
881 } else { /* whole new item falls into S_new[i] */
882
883 /* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
884 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
Dave Jones416e2ab2014-02-17 16:21:24 -0500885 snum[i] - 1, sbytes[i], S_new[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700886
887 /* Insert new item into S_new[i] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400888 buffer_info_init_bh(tb, &bi, S_new[i]);
Dave Jones416e2ab2014-02-17 16:21:24 -0500889 leaf_insert_into_buf(&bi, item_pos - n + snum[i] - 1,
890 ih, body, zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700891
892 zeros_num = tb->insert_size[0] = 0;
893 }
894 }
895
896 else { /* new item or it part don't falls into S_new[i] */
897
898 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
899 snum[i], sbytes[i], S_new[i]);
900 }
901 break;
902
903 case M_PASTE: /* append item */
904
905 if (n - snum[i] <= item_pos) { /* pasted item or part if it falls to S_new[i] */
906 if (item_pos == n - snum[i] && sbytes[i] != -1) { /* we must shift part of the appended item */
907 struct item_head *aux_ih;
908
909 RFALSE(ih, "PAP-12210: ih must be 0");
910
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400911 aux_ih = item_head(tbS0, item_pos);
Jeff Mahoney1d965fe2009-06-17 16:26:29 -0700912 if (is_direntry_le_ih(aux_ih)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700913 /* we append to directory item */
914
915 int entry_count;
916
Dave Jones416e2ab2014-02-17 16:21:24 -0500917 entry_count = ih_entry_count(aux_ih);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700918
Dave Jones416e2ab2014-02-17 16:21:24 -0500919 if (entry_count - sbytes[i] < pos_in_item && pos_in_item <= entry_count) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700920 /* new directory entry falls into S_new[i] */
921
Dave Jones416e2ab2014-02-17 16:21:24 -0500922 RFALSE(!tb->insert_size[0], "PAP-12215: insert_size is already 0");
923 RFALSE(sbytes[i] - 1 >= entry_count,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700924 "PAP-12220: there are no so much entries (%d), only %d",
Dave Jones416e2ab2014-02-17 16:21:24 -0500925 sbytes[i] - 1, entry_count);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700926
927 /* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500928 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum[i], sbytes[i] - 1, S_new[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700929 /* Paste given directory entry to directory item */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400930 buffer_info_init_bh(tb, &bi, S_new[i]);
Dave Jones416e2ab2014-02-17 16:21:24 -0500931 leaf_paste_in_buffer(&bi, 0, pos_in_item - entry_count + sbytes[i] - 1,
932 tb->insert_size[0], body, zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700933 /* paste new directory entry */
Dave Jones416e2ab2014-02-17 16:21:24 -0500934 leaf_paste_entries(&bi, 0, pos_in_item - entry_count + sbytes[i] - 1, 1,
935 (struct reiserfs_de_head *) body,
936 body + DEH_SIZE, tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700937 tb->insert_size[0] = 0;
938 pos_in_item++;
939 } else { /* new directory entry doesn't fall into S_new[i] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500940 leaf_move_items(LEAF_FROM_S_TO_SNEW,tb, snum[i], sbytes[i], S_new[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700941 }
942 } else { /* regular object */
943
Dave Jones416e2ab2014-02-17 16:21:24 -0500944 int n_shift, n_rem, r_zeros_number;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700945 const char *r_body;
946
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400947 RFALSE(pos_in_item != ih_item_len(item_head(tbS0, item_pos)) || tb->insert_size[0] <= 0,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700948 "PAP-12225: item too short or insert_size <= 0");
949
950 /* Calculate number of bytes which must be shifted from appended item */
Dave Jones416e2ab2014-02-17 16:21:24 -0500951 n_shift = sbytes[i] - tb->insert_size[0];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700952 if (n_shift < 0)
953 n_shift = 0;
Dave Jones416e2ab2014-02-17 16:21:24 -0500954 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum[i], n_shift, S_new[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700955
956 /* Calculate number of bytes which must remain in body after append to S_new[i] */
Dave Jones416e2ab2014-02-17 16:21:24 -0500957 n_rem = tb->insert_size[0] - sbytes[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700958 if (n_rem < 0)
959 n_rem = 0;
960 /* Append part of body into S_new[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -0400961 buffer_info_init_bh(tb, &bi, S_new[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700962 if (n_rem > zeros_num) {
963 r_zeros_number = 0;
Dave Jones416e2ab2014-02-17 16:21:24 -0500964 r_body = body + n_rem - zeros_num;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700965 } else {
966 r_body = body;
Dave Jones416e2ab2014-02-17 16:21:24 -0500967 r_zeros_number = zeros_num - n_rem;
968 zeros_num -= r_zeros_number;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700969 }
970
Dave Jones416e2ab2014-02-17 16:21:24 -0500971 leaf_paste_in_buffer(&bi, 0, n_shift,
972 tb->insert_size[0] - n_rem,
973 r_body, r_zeros_number);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700974 {
975 struct item_head *tmp;
976
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400977 tmp = item_head(S_new[i], 0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700978 if (is_indirect_le_ih
979 (tmp)) {
Dave Jones416e2ab2014-02-17 16:21:24 -0500980 set_ih_free_space(tmp, 0);
981 set_le_ih_k_offset(tmp, le_ih_k_offset(tmp) + (n_rem << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT)));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700982 } else {
Dave Jones416e2ab2014-02-17 16:21:24 -0500983 set_le_ih_k_offset(tmp, le_ih_k_offset(tmp) + n_rem);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700984 }
985 }
986
987 tb->insert_size[0] = n_rem;
988 if (!n_rem)
989 pos_in_item++;
990 }
991 } else
992 /* item falls wholly into S_new[i] */
993 {
Harvey Harrison8acc5702008-04-28 02:16:21 -0700994 int leaf_mi;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700995 struct item_head *pasted;
996
997#ifdef CONFIG_REISERFS_CHECK
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400998 struct item_head *ih_check = item_head(tbS0, item_pos);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700999
Harvey Harrison8acc5702008-04-28 02:16:21 -07001000 if (!is_direntry_le_ih(ih_check)
1001 && (pos_in_item != ih_item_len(ih_check)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001002 || tb->insert_size[0] <= 0))
1003 reiserfs_panic(tb->tb_sb,
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001004 "PAP-12235",
1005 "pos_in_item "
1006 "must be equal "
1007 "to ih_item_len");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001008#endif /* CONFIG_REISERFS_CHECK */
1009
Dave Jones416e2ab2014-02-17 16:21:24 -05001010 leaf_mi = leaf_move_items(LEAF_FROM_S_TO_SNEW,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001011 tb, snum[i],
1012 sbytes[i],
1013 S_new[i]);
1014
Harvey Harrison8acc5702008-04-28 02:16:21 -07001015 RFALSE(leaf_mi,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001016 "PAP-12240: unexpected value returned by leaf_move_items (%d)",
Harvey Harrison8acc5702008-04-28 02:16:21 -07001017 leaf_mi);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001018
1019 /* paste into item */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -04001020 buffer_info_init_bh(tb, &bi, S_new[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001021 leaf_paste_in_buffer(&bi,
Dave Jones416e2ab2014-02-17 16:21:24 -05001022 item_pos - n + snum[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001023 pos_in_item,
1024 tb->insert_size[0],
1025 body, zeros_num);
1026
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001027 pasted = item_head(S_new[i], item_pos - n + snum[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001028 if (is_direntry_le_ih(pasted)) {
Jeff Mahoneyeba00302009-03-30 14:02:18 -04001029 leaf_paste_entries(&bi,
Dave Jones416e2ab2014-02-17 16:21:24 -05001030 item_pos - n + snum[i],
1031 pos_in_item, 1,
1032 (struct reiserfs_de_head *)body,
1033 body + DEH_SIZE,
1034 tb->insert_size[0]
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001035 );
1036 }
1037
1038 /* if we paste to indirect item update ih_free_space */
1039 if (is_indirect_le_ih(pasted))
1040 set_ih_free_space(pasted, 0);
1041 zeros_num = tb->insert_size[0] = 0;
1042 }
1043 }
1044
1045 else { /* pasted item doesn't fall into S_new[i] */
1046
1047 leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
1048 snum[i], sbytes[i], S_new[i]);
1049 }
1050 break;
1051 default: /* cases d and t */
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001052 reiserfs_panic(tb->tb_sb, "PAP-12245",
1053 "blknum > 2: unexpected mode: %s(%d)",
Dave Jones416e2ab2014-02-17 16:21:24 -05001054 (flag == M_DELETE) ? "DELETE" : ((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001055 }
1056
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001057 memcpy(insert_key + i, leaf_key(S_new[i], 0), KEY_SIZE);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001058 insert_ptr[i] = S_new[i];
1059
1060 RFALSE(!buffer_journaled(S_new[i])
1061 || buffer_journal_dirty(S_new[i])
1062 || buffer_dirty(S_new[i]), "PAP-12247: S_new[%d] : (%b)",
1063 i, S_new[i]);
1064 }
1065
1066 /* if the affected item was not wholly shifted then we perform all necessary operations on that part or whole of the
1067 affected item which remains in S */
1068 if (0 <= item_pos && item_pos < tb->s0num) { /* if we must insert or append into buffer S[0] */
1069
1070 switch (flag) {
1071 case M_INSERT: /* insert item into S[0] */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -04001072 buffer_info_init_tbS0(tb, &bi);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001073 leaf_insert_into_buf(&bi, item_pos, ih, body,
1074 zeros_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001075
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001076 /* If we insert the first key change the delimiting key */
1077 if (item_pos == 0) {
1078 if (tb->CFL[0]) /* can be 0 in reiserfsck */
Dave Jones416e2ab2014-02-17 16:21:24 -05001079 replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001080 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001081 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001082
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001083 case M_PASTE:{ /* append item in S[0] */
1084 struct item_head *pasted;
1085
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001086 pasted = item_head(tbS0, item_pos);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001087 /* when directory, may be new entry already pasted */
1088 if (is_direntry_le_ih(pasted)) {
Dave Jones416e2ab2014-02-17 16:21:24 -05001089 if (pos_in_item >= 0 && pos_in_item <= ih_entry_count(pasted)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001090
1091 RFALSE(!tb->insert_size[0],
1092 "PAP-12260: insert_size is 0 already");
1093
1094 /* prepare space */
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -04001095 buffer_info_init_tbS0(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -05001096 leaf_paste_in_buffer(&bi, item_pos, pos_in_item,
1097 tb->insert_size[0], body,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001098 zeros_num);
1099
1100 /* paste entry */
Dave Jones416e2ab2014-02-17 16:21:24 -05001101 leaf_paste_entries(&bi, item_pos, pos_in_item, 1,
1102 (struct reiserfs_de_head *)body,
1103 body + DEH_SIZE,
1104 tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001105 if (!item_pos && !pos_in_item) {
Dave Jones416e2ab2014-02-17 16:21:24 -05001106 RFALSE(!tb->CFL[0] || !tb->L[0],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001107 "PAP-12270: CFL[0]/L[0] must be specified");
Dave Jones416e2ab2014-02-17 16:21:24 -05001108 if (tb->CFL[0])
1109 replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0, 0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001110 }
1111 tb->insert_size[0] = 0;
1112 }
1113 } else { /* regular object */
1114 if (pos_in_item == ih_item_len(pasted)) {
1115
1116 RFALSE(tb->insert_size[0] <= 0,
1117 "PAP-12275: insert size must not be %d",
1118 tb->insert_size[0]);
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -04001119 buffer_info_init_tbS0(tb, &bi);
Dave Jones416e2ab2014-02-17 16:21:24 -05001120 leaf_paste_in_buffer(&bi, item_pos, pos_in_item,
1121 tb->insert_size[0], body, zeros_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001122
1123 if (is_indirect_le_ih(pasted)) {
1124#if 0
1125 RFALSE(tb->
1126 insert_size[0] !=
1127 UNFM_P_SIZE,
1128 "PAP-12280: insert_size for indirect item must be %d, not %d",
1129 UNFM_P_SIZE,
1130 tb->
1131 insert_size[0]);
1132#endif
Dave Jones416e2ab2014-02-17 16:21:24 -05001133 set_ih_free_space(pasted, 0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001134 }
1135 tb->insert_size[0] = 0;
1136 }
1137#ifdef CONFIG_REISERFS_CHECK
1138 else {
1139 if (tb->insert_size[0]) {
1140 print_cur_tb("12285");
Dave Jones416e2ab2014-02-17 16:21:24 -05001141 reiserfs_panic(tb->tb_sb,
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001142 "PAP-12285",
1143 "insert_size "
1144 "must be 0 "
1145 "(%d)",
1146 tb->insert_size[0]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001147 }
1148 }
1149#endif /* CONFIG_REISERFS_CHECK */
1150
1151 }
1152 } /* case M_PASTE: */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001153 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001155#ifdef CONFIG_REISERFS_CHECK
1156 if (flag == M_PASTE && tb->insert_size[0]) {
1157 print_cur_tb("12290");
1158 reiserfs_panic(tb->tb_sb,
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001159 "PAP-12290", "insert_size is still not 0 (%d)",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001160 tb->insert_size[0]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001161 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001162#endif /* CONFIG_REISERFS_CHECK */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163 return 0;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001164} /* Leaf level of the tree is balanced (end of balance_leaf) */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001165
1166/* Make empty node */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001167void make_empty_node(struct buffer_info *bi)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001168{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001169 struct block_head *blkh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001171 RFALSE(bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001172
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001173 blkh = B_BLK_HEAD(bi->bi_bh);
1174 set_blkh_nr_item(blkh, 0);
1175 set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001176
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001177 if (bi->bi_parent)
1178 B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0; /* Endian safe if 0 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179}
1180
Linus Torvalds1da177e2005-04-16 15:20:36 -07001181/* Get first empty buffer */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001182struct buffer_head *get_FEB(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001183{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001184 int i;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001185 struct buffer_info bi;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001186
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001187 for (i = 0; i < MAX_FEB_SIZE; i++)
Al Viro9dce07f2008-03-29 03:07:28 +00001188 if (tb->FEB[i] != NULL)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001189 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001190
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001191 if (i == MAX_FEB_SIZE)
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001192 reiserfs_panic(tb->tb_sb, "vs-12300", "FEB list is empty");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001193
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -04001194 buffer_info_init_bh(tb, &bi, tb->FEB[i]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001195 make_empty_node(&bi);
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -04001196 set_buffer_uptodate(tb->FEB[i]);
1197 tb->used[i] = tb->FEB[i];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001198 tb->FEB[i] = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001199
Jeff Mahoneyfba4ebb2009-03-30 14:02:42 -04001200 return tb->used[i];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201}
1202
Jeff Mahoney098297b2014-04-23 10:00:36 -04001203/* This is now used because reiserfs_free_block has to be able to schedule. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001204static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001206 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001207
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001208 if (buffer_dirty(bh))
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001209 reiserfs_warning(tb->tb_sb, "reiserfs-12320",
1210 "called with dirty buffer");
Ahmed S. Darwish79a81ae2007-02-12 00:52:09 -08001211 for (i = 0; i < ARRAY_SIZE(tb->thrown); i++)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001212 if (!tb->thrown[i]) {
1213 tb->thrown[i] = bh;
1214 get_bh(bh); /* free_thrown puts this */
1215 return;
1216 }
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001217 reiserfs_warning(tb->tb_sb, "reiserfs-12321",
1218 "too many thrown buffers");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001219}
1220
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001221static void free_thrown(struct tree_balance *tb)
1222{
1223 int i;
1224 b_blocknr_t blocknr;
Ahmed S. Darwish79a81ae2007-02-12 00:52:09 -08001225 for (i = 0; i < ARRAY_SIZE(tb->thrown); i++) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001226 if (tb->thrown[i]) {
1227 blocknr = tb->thrown[i]->b_blocknr;
1228 if (buffer_dirty(tb->thrown[i]))
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001229 reiserfs_warning(tb->tb_sb, "reiserfs-12322",
1230 "called with dirty buffer %d",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001231 blocknr);
1232 brelse(tb->thrown[i]); /* incremented in store_thrown */
1233 reiserfs_free_block(tb->transaction_handle, NULL,
1234 blocknr, 0);
1235 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001236 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001237}
1238
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001239void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001241 struct block_head *blkh;
1242 blkh = B_BLK_HEAD(bh);
1243 set_blkh_level(blkh, FREE_LEVEL);
1244 set_blkh_nr_item(blkh, 0);
1245
1246 clear_buffer_dirty(bh);
1247 store_thrown(tb, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001248}
1249
1250/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001251void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
1252 struct buffer_head *src, int n_src)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001253{
1254
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001255 RFALSE(dest == NULL || src == NULL,
1256 "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
1257 src, dest);
1258 RFALSE(!B_IS_KEYS_LEVEL(dest),
1259 "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
1260 dest);
1261 RFALSE(n_dest < 0 || n_src < 0,
1262 "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
1263 RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
1264 "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
1265 n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001266
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001267 if (B_IS_ITEMS_LEVEL(src))
1268 /* source buffer contains leaf node */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001269 memcpy(internal_key(dest, n_dest), item_head(src, n_src),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001270 KEY_SIZE);
1271 else
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001272 memcpy(internal_key(dest, n_dest), internal_key(src, n_src),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001273 KEY_SIZE);
1274
1275 do_balance_mark_internal_dirty(tb, dest, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001276}
1277
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001278int get_left_neighbor_position(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001279{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001280 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001281
Al Viro9dce07f2008-03-29 03:07:28 +00001282 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FL[h] == NULL,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001283 "vs-12325: FL[%d](%p) or F[%d](%p) does not exist",
1284 h, tb->FL[h], h, PATH_H_PPARENT(tb->tb_path, h));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001285
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001286 if (Sh_position == 0)
1287 return B_NR_ITEMS(tb->FL[h]);
1288 else
1289 return Sh_position - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001290}
1291
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001292int get_right_neighbor_position(struct tree_balance *tb, int h)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001293{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001294 int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001295
Al Viro9dce07f2008-03-29 03:07:28 +00001296 RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FR[h] == NULL,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001297 "vs-12330: F[%d](%p) or FR[%d](%p) does not exist",
1298 h, PATH_H_PPARENT(tb->tb_path, h), h, tb->FR[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001300 if (Sh_position == B_NR_ITEMS(PATH_H_PPARENT(tb->tb_path, h)))
1301 return 0;
1302 else
1303 return Sh_position + 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001304}
1305
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306#ifdef CONFIG_REISERFS_CHECK
1307
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001308int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
1309static void check_internal_node(struct super_block *s, struct buffer_head *bh,
1310 char *mes)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001311{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001312 struct disk_child *dc;
1313 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001314
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001315 RFALSE(!bh, "PAP-12336: bh == 0");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001316
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001317 if (!bh || !B_IS_IN_TREE(bh))
1318 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001320 RFALSE(!buffer_dirty(bh) &&
1321 !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
1322 "PAP-12337: buffer (%b) must be dirty", bh);
1323 dc = B_N_CHILD(bh, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001324
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001325 for (i = 0; i <= B_NR_ITEMS(bh); i++, dc++) {
1326 if (!is_reusable(s, dc_block_number(dc), 1)) {
1327 print_cur_tb(mes);
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001328 reiserfs_panic(s, "PAP-12338",
1329 "invalid child pointer %y in %b",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001330 dc, bh);
1331 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001332 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001333}
1334
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001335static int locked_or_not_in_tree(struct tree_balance *tb,
1336 struct buffer_head *bh, char *which)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001337{
1338 if ((!buffer_journal_prepared(bh) && buffer_locked(bh)) ||
1339 !B_IS_IN_TREE(bh)) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001340 reiserfs_warning(tb->tb_sb, "vs-12339", "%s (%b)", which, bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001341 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001342 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001343 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344}
1345
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001346static int check_before_balancing(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001347{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001348 int retval = 0;
1349
Frederic Weisbecker08f14fc2009-05-16 19:10:38 +02001350 if (REISERFS_SB(tb->tb_sb)->cur_tb) {
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001351 reiserfs_panic(tb->tb_sb, "vs-12335", "suspect that schedule "
1352 "occurred based on cur_tb not being null at "
1353 "this point in code. do_balance cannot properly "
Frederic Weisbecker08f14fc2009-05-16 19:10:38 +02001354 "handle concurrent tree accesses on a same "
1355 "mount point.");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001356 }
1357
Jeff Mahoney098297b2014-04-23 10:00:36 -04001358 /*
1359 * double check that buffers that we will modify are unlocked.
1360 * (fix_nodes should already have prepped all of these for us).
1361 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001362 if (tb->lnum[0]) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001363 retval |= locked_or_not_in_tree(tb, tb->L[0], "L[0]");
1364 retval |= locked_or_not_in_tree(tb, tb->FL[0], "FL[0]");
1365 retval |= locked_or_not_in_tree(tb, tb->CFL[0], "CFL[0]");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001366 check_leaf(tb->L[0]);
1367 }
1368 if (tb->rnum[0]) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001369 retval |= locked_or_not_in_tree(tb, tb->R[0], "R[0]");
1370 retval |= locked_or_not_in_tree(tb, tb->FR[0], "FR[0]");
1371 retval |= locked_or_not_in_tree(tb, tb->CFR[0], "CFR[0]");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001372 check_leaf(tb->R[0]);
1373 }
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001374 retval |= locked_or_not_in_tree(tb, PATH_PLAST_BUFFER(tb->tb_path),
1375 "S[0]");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001376 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1377
1378 return retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001379}
1380
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001381static void check_after_balance_leaf(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001382{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001383 if (tb->lnum[0]) {
1384 if (B_FREE_SPACE(tb->L[0]) !=
1385 MAX_CHILD_SIZE(tb->L[0]) -
1386 dc_size(B_N_CHILD
1387 (tb->FL[0], get_left_neighbor_position(tb, 0)))) {
1388 print_cur_tb("12221");
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001389 reiserfs_panic(tb->tb_sb, "PAP-12355",
1390 "shift to left was incorrect");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001391 }
1392 }
1393 if (tb->rnum[0]) {
1394 if (B_FREE_SPACE(tb->R[0]) !=
1395 MAX_CHILD_SIZE(tb->R[0]) -
1396 dc_size(B_N_CHILD
1397 (tb->FR[0], get_right_neighbor_position(tb, 0)))) {
1398 print_cur_tb("12222");
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001399 reiserfs_panic(tb->tb_sb, "PAP-12360",
1400 "shift to right was incorrect");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001401 }
1402 }
1403 if (PATH_H_PBUFFER(tb->tb_path, 1) &&
1404 (B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0)) !=
1405 (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1406 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1407 PATH_H_POSITION(tb->tb_path, 1)))))) {
1408 int left = B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0));
1409 int right = (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
1410 dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
1411 PATH_H_POSITION(tb->tb_path,
1412 1))));
1413 print_cur_tb("12223");
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001414 reiserfs_warning(tb->tb_sb, "reiserfs-12363",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001415 "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
1416 "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d",
1417 left,
1418 MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)),
1419 PATH_H_PBUFFER(tb->tb_path, 1),
1420 PATH_H_POSITION(tb->tb_path, 1),
1421 dc_size(B_N_CHILD
1422 (PATH_H_PBUFFER(tb->tb_path, 1),
1423 PATH_H_POSITION(tb->tb_path, 1))),
1424 right);
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001425 reiserfs_panic(tb->tb_sb, "PAP-12365", "S is incorrect");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001426 }
1427}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001429static void check_leaf_level(struct tree_balance *tb)
1430{
1431 check_leaf(tb->L[0]);
1432 check_leaf(tb->R[0]);
1433 check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
1434}
1435
1436static void check_internal_levels(struct tree_balance *tb)
1437{
1438 int h;
1439
1440 /* check all internal nodes */
1441 for (h = 1; tb->insert_size[h]; h++) {
1442 check_internal_node(tb->tb_sb, PATH_H_PBUFFER(tb->tb_path, h),
1443 "BAD BUFFER ON PATH");
1444 if (tb->lnum[h])
1445 check_internal_node(tb->tb_sb, tb->L[h], "BAD L");
1446 if (tb->rnum[h])
1447 check_internal_node(tb->tb_sb, tb->R[h], "BAD R");
1448 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001449
1450}
1451
1452#endif
1453
Jeff Mahoney098297b2014-04-23 10:00:36 -04001454/*
1455 * Now we have all of the buffers that must be used in balancing of
1456 * the tree. We rely on the assumption that schedule() will not occur
1457 * while do_balance works. ( Only interrupt handlers are acceptable.)
1458 * We balance the tree according to the analysis made before this,
1459 * using buffers already obtained. For SMP support it will someday be
1460 * necessary to add ordered locking of tb.
1461 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001462
Jeff Mahoney098297b2014-04-23 10:00:36 -04001463/*
1464 * Some interesting rules of balancing:
1465 * we delete a maximum of two nodes per level per balancing: we never
1466 * delete R, when we delete two of three nodes L, S, R then we move
1467 * them into R.
1468 *
1469 * we only delete L if we are deleting two nodes, if we delete only
1470 * one node we delete S
1471 *
1472 * if we shift leaves then we shift as much as we can: this is a
1473 * deliberate policy of extremism in node packing which results in
1474 * higher average utilization after repeated random balance operations
1475 * at the cost of more memory copies and more balancing as a result of
1476 * small insertions to full nodes.
1477 *
1478 * if we shift internal nodes we try to evenly balance the node
1479 * utilization, with consequent less balancing at the cost of lower
1480 * utilization.
1481 *
1482 * one could argue that the policy for directories in leaves should be
1483 * that of internal nodes, but we will wait until another day to
1484 * evaluate this.... It would be nice to someday measure and prove
1485 * these assumptions as to what is optimal....
1486 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001487
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001488static inline void do_balance_starts(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001489{
Jeff Mahoney098297b2014-04-23 10:00:36 -04001490 /* use print_cur_tb() to see initial state of struct tree_balance */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001491
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001492 /* store_print_tb (tb); */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001493
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001494 /* do not delete, just comment it out */
Jeff Mahoney098297b2014-04-23 10:00:36 -04001495 /*
1496 print_tb(flag, PATH_LAST_POSITION(tb->tb_path),
1497 tb->tb_path->pos_in_item, tb, "check");
1498 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001499 RFALSE(check_before_balancing(tb), "PAP-12340: locked buffers in TB");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001500#ifdef CONFIG_REISERFS_CHECK
Frederic Weisbecker08f14fc2009-05-16 19:10:38 +02001501 REISERFS_SB(tb->tb_sb)->cur_tb = tb;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001502#endif
1503}
1504
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001505static inline void do_balance_completed(struct tree_balance *tb)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001506{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001507
Linus Torvalds1da177e2005-04-16 15:20:36 -07001508#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001509 check_leaf_level(tb);
1510 check_internal_levels(tb);
Frederic Weisbecker08f14fc2009-05-16 19:10:38 +02001511 REISERFS_SB(tb->tb_sb)->cur_tb = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001512#endif
1513
Jeff Mahoney098297b2014-04-23 10:00:36 -04001514 /*
1515 * reiserfs_free_block is no longer schedule safe. So, we need to
1516 * put the buffers we want freed on the thrown list during do_balance,
1517 * and then free them now
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001518 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001519
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001520 REISERFS_SB(tb->tb_sb)->s_do_balance++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001521
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001522 /* release all nodes hold to perform the balancing */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001523 unfix_nodes(tb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001524
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001525 free_thrown(tb);
1526}
1527
Jeff Mahoney098297b2014-04-23 10:00:36 -04001528/*
1529 * do_balance - balance the tree
1530 *
1531 * @tb: tree_balance structure
1532 * @ih: item header of inserted item
1533 * @body: body of inserted item or bytes to paste
1534 * @flag: 'i' - insert, 'd' - delete, 'c' - cut, 'p' paste
1535 *
1536 * Cut means delete part of an item (includes removing an entry from a
1537 * directory).
1538 *
1539 * Delete means delete whole item.
1540 *
1541 * Insert means add a new item into the tree.
1542 *
1543 * Paste means to append to the end of an existing file or to
1544 * insert a directory entry.
1545 */
1546void do_balance(struct tree_balance *tb, struct item_head *ih,
1547 const char *body, int flag)
1548{
1549 int child_pos; /* position of a child node in its parent */
1550 int h; /* level of the tree being processed */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001551
Jeff Mahoney098297b2014-04-23 10:00:36 -04001552 /*
1553 * in our processing of one level we sometimes determine what
1554 * must be inserted into the next higher level. This insertion
1555 * consists of a key or two keys and their corresponding
1556 * pointers
1557 */
1558 struct item_head insert_key[2];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001559
Jeff Mahoney098297b2014-04-23 10:00:36 -04001560 /* inserted node-ptrs for the next level */
1561 struct buffer_head *insert_ptr[2];
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001562
1563 tb->tb_mode = flag;
1564 tb->need_balance_dirty = 0;
1565
1566 if (FILESYSTEM_CHANGED_TB(tb)) {
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001567 reiserfs_panic(tb->tb_sb, "clm-6000", "fs generation has "
1568 "changed");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001569 }
1570 /* if we have no real work to do */
1571 if (!tb->insert_size[0]) {
Jeff Mahoney45b03d52009-03-30 14:02:21 -04001572 reiserfs_warning(tb->tb_sb, "PAP-12350",
1573 "insert_size == 0, mode == %c", flag);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001574 unfix_nodes(tb);
1575 return;
1576 }
1577
Jeff Mahoneya228bf82014-04-23 10:00:42 -04001578 atomic_inc(&fs_generation(tb->tb_sb));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001579 do_balance_starts(tb);
1580
Jeff Mahoney098297b2014-04-23 10:00:36 -04001581 /*
1582 * balance_leaf returns 0 except if combining L R and S into
1583 * one node. see balance_internal() for explanation of this
1584 * line of code.
1585 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001586 child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
1587 balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001588
1589#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001590 check_after_balance_leaf(tb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001591#endif
1592
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001593 /* Balance internal level of the tree. */
1594 for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
1595 child_pos =
1596 balance_internal(tb, h, child_pos, insert_key, insert_ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001597
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001598 do_balance_completed(tb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001599
1600}