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