aboutsummaryrefslogtreecommitdiffstats
path: root/fs/reiserfs/fix_node.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@g5.osdl.org>2005-07-12 23:21:28 -0400
committerLinus Torvalds <torvalds@g5.osdl.org>2005-07-12 23:21:28 -0400
commitbd4c625c061c2a38568d0add3478f59172455159 (patch)
tree1c44a17c55bce2ee7ad5ea3d15a208ecc0955f74 /fs/reiserfs/fix_node.c
parent7fa94c8868edfef8cb6a201fcc9a5078b7b961da (diff)
reiserfs: run scripts/Lindent on reiserfs code
This was a pure indentation change, using: scripts/Lindent fs/reiserfs/*.c include/linux/reiserfs_*.h to make reiserfs match the regular Linux indentation style. As Jeff Mahoney <jeffm@suse.com> writes: The ReiserFS code is a mix of a number of different coding styles, sometimes different even from line-to-line. Since the code has been relatively stable for quite some time and there are few outstanding patches to be applied, it is time to reformat the code to conform to the Linux style standard outlined in Documentation/CodingStyle. This patch contains the result of running scripts/Lindent against fs/reiserfs/*.c and include/linux/reiserfs_*.h. There are places where the code can be made to look better, but I'd rather keep those patches separate so that there isn't a subtle by-hand hand accident in the middle of a huge patch. To be clear: This patch is reformatting *only*. A number of patches may follow that continue to make the code more consistent with the Linux coding style. Hans wasn't particularly enthusiastic about these patches, but said he wouldn't really oppose them either. Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'fs/reiserfs/fix_node.c')
-rw-r--r--fs/reiserfs/fix_node.c4051
1 files changed, 2079 insertions, 1972 deletions
diff --git a/fs/reiserfs/fix_node.c b/fs/reiserfs/fix_node.c
index e4f64be9e15b..2706e2adffab 100644
--- a/fs/reiserfs/fix_node.c
+++ b/fs/reiserfs/fix_node.c
@@ -34,14 +34,12 @@
34 ** 34 **
35 **/ 35 **/
36 36
37
38#include <linux/config.h> 37#include <linux/config.h>
39#include <linux/time.h> 38#include <linux/time.h>
40#include <linux/string.h> 39#include <linux/string.h>
41#include <linux/reiserfs_fs.h> 40#include <linux/reiserfs_fs.h>
42#include <linux/buffer_head.h> 41#include <linux/buffer_head.h>
43 42
44
45/* To make any changes in the tree we find a node, that contains item 43/* To make any changes in the tree we find a node, that contains item
46 to be changed/deleted or position in the node we insert a new item 44 to be changed/deleted or position in the node we insert a new item
47 to. We call this node S. To do balancing we need to decide what we 45 to. We call this node S. To do balancing we need to decide what we
@@ -56,490 +54,522 @@
56 have to have if we do not any shiftings, if we shift to left/right 54 have to have if we do not any shiftings, if we shift to left/right
57 neighbor or to both. */ 55 neighbor or to both. */
58 56
59
60/* taking item number in virtual node, returns number of item, that it has in source buffer */ 57/* taking item number in virtual node, returns number of item, that it has in source buffer */
61static inline int old_item_num (int new_num, int affected_item_num, int mode) 58static inline int old_item_num(int new_num, int affected_item_num, int mode)
62{ 59{
63 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num) 60 if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
64 return new_num; 61 return new_num;
65 62
66 if (mode == M_INSERT) { 63 if (mode == M_INSERT) {
67 64
68 RFALSE( new_num == 0, 65 RFALSE(new_num == 0,
69 "vs-8005: for INSERT mode and item number of inserted item"); 66 "vs-8005: for INSERT mode and item number of inserted item");
70 67
71 return new_num - 1; 68 return new_num - 1;
72 } 69 }
73 70
74 RFALSE( mode != M_DELETE, 71 RFALSE(mode != M_DELETE,
75 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", mode); 72 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
76 /* delete mode */ 73 mode);
77 return new_num + 1; 74 /* delete mode */
75 return new_num + 1;
78} 76}
79 77
80static void create_virtual_node (struct tree_balance * tb, int h) 78static void create_virtual_node(struct tree_balance *tb, int h)
81{ 79{
82 struct item_head * ih; 80 struct item_head *ih;
83 struct virtual_node * vn = tb->tb_vn; 81 struct virtual_node *vn = tb->tb_vn;
84 int new_num; 82 int new_num;
85 struct buffer_head * Sh; /* this comes from tb->S[h] */ 83 struct buffer_head *Sh; /* this comes from tb->S[h] */
86 84
87 Sh = PATH_H_PBUFFER (tb->tb_path, h); 85 Sh = PATH_H_PBUFFER(tb->tb_path, h);
88 86
89 /* size of changed node */ 87 /* size of changed node */
90 vn->vn_size = MAX_CHILD_SIZE (Sh) - B_FREE_SPACE (Sh) + tb->insert_size[h]; 88 vn->vn_size =
89 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
91 90
92 /* for internal nodes array if virtual items is not created */ 91 /* for internal nodes array if virtual items is not created */
93 if (h) { 92 if (h) {
94 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE); 93 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
95 return; 94 return;
96 }
97
98 /* number of items in virtual node */
99 vn->vn_nr_item = B_NR_ITEMS (Sh) + ((vn->vn_mode == M_INSERT)? 1 : 0) - ((vn->vn_mode == M_DELETE)? 1 : 0);
100
101 /* first virtual item */
102 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
103 memset (vn->vn_vi, 0, vn->vn_nr_item * sizeof (struct virtual_item));
104 vn->vn_free_ptr += vn->vn_nr_item * sizeof (struct virtual_item);
105
106
107 /* first item in the node */
108 ih = B_N_PITEM_HEAD (Sh, 0);
109
110 /* define the mergeability for 0-th item (if it is not being deleted) */
111 if (op_is_left_mergeable (&(ih->ih_key), Sh->b_size) && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
112 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
113
114 /* go through all items those remain in the virtual node (except for the new (inserted) one) */
115 for (new_num = 0; new_num < vn->vn_nr_item; new_num ++) {
116 int j;
117 struct virtual_item * vi = vn->vn_vi + new_num;
118 int is_affected = ((new_num != vn->vn_affected_item_num) ? 0 : 1);
119
120
121 if (is_affected && vn->vn_mode == M_INSERT)
122 continue;
123
124 /* get item number in source node */
125 j = old_item_num (new_num, vn->vn_affected_item_num, vn->vn_mode);
126
127 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
128 vi->vi_ih = ih + j;
129 vi->vi_item = B_I_PITEM (Sh, ih + j);
130 vi->vi_uarea = vn->vn_free_ptr;
131
132 // FIXME: there is no check, that item operation did not
133 // consume too much memory
134 vn->vn_free_ptr += op_create_vi (vn, vi, is_affected, tb->insert_size [0]);
135 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
136 reiserfs_panic (tb->tb_sb, "vs-8030: create_virtual_node: "
137 "virtual node space consumed");
138
139 if (!is_affected)
140 /* this is not being changed */
141 continue;
142
143 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
144 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
145 vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
146 } 95 }
147 }
148
149
150 /* virtual inserted item is not defined yet */
151 if (vn->vn_mode == M_INSERT) {
152 struct virtual_item * vi = vn->vn_vi + vn->vn_affected_item_num;
153
154 RFALSE( vn->vn_ins_ih == 0,
155 "vs-8040: item header of inserted item is not specified");
156 vi->vi_item_len = tb->insert_size[0];
157 vi->vi_ih = vn->vn_ins_ih;
158 vi->vi_item = vn->vn_data;
159 vi->vi_uarea = vn->vn_free_ptr;
160
161 op_create_vi (vn, vi, 0/*not pasted or cut*/, tb->insert_size [0]);
162 }
163
164 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
165 if (tb->CFR[0]) {
166 struct reiserfs_key * key;
167
168 key = B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]);
169 if (op_is_left_mergeable (key, Sh->b_size) && (vn->vn_mode != M_DELETE ||
170 vn->vn_affected_item_num != B_NR_ITEMS (Sh) - 1))
171 vn->vn_vi[vn->vn_nr_item-1].vi_type |= VI_TYPE_RIGHT_MERGEABLE;
172 96
173#ifdef CONFIG_REISERFS_CHECK 97 /* number of items in virtual node */
174 if (op_is_left_mergeable (key, Sh->b_size) && 98 vn->vn_nr_item =
175 !(vn->vn_mode != M_DELETE || vn->vn_affected_item_num != B_NR_ITEMS (Sh) - 1) ) { 99 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
176 /* we delete last item and it could be merged with right neighbor's first item */ 100 ((vn->vn_mode == M_DELETE) ? 1 : 0);
177 if (!(B_NR_ITEMS (Sh) == 1 && is_direntry_le_ih (B_N_PITEM_HEAD (Sh, 0)) && 101
178 I_ENTRY_COUNT (B_N_PITEM_HEAD (Sh, 0)) == 1)) { 102 /* first virtual item */
179 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */ 103 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
180 print_block (Sh, 0, -1, -1); 104 memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
181 reiserfs_panic (tb->tb_sb, "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c", 105 vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
182 key, vn->vn_affected_item_num, vn->vn_mode, M_DELETE); 106
183 } else 107 /* first item in the node */
184 /* we can delete directory item, that has only one directory entry in it */ 108 ih = B_N_PITEM_HEAD(Sh, 0);
185 ; 109
110 /* define the mergeability for 0-th item (if it is not being deleted) */
111 if (op_is_left_mergeable(&(ih->ih_key), Sh->b_size)
112 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
113 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
114
115 /* go through all items those remain in the virtual node (except for the new (inserted) one) */
116 for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
117 int j;
118 struct virtual_item *vi = vn->vn_vi + new_num;
119 int is_affected =
120 ((new_num != vn->vn_affected_item_num) ? 0 : 1);
121
122 if (is_affected && vn->vn_mode == M_INSERT)
123 continue;
124
125 /* get item number in source node */
126 j = old_item_num(new_num, vn->vn_affected_item_num,
127 vn->vn_mode);
128
129 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
130 vi->vi_ih = ih + j;
131 vi->vi_item = B_I_PITEM(Sh, ih + j);
132 vi->vi_uarea = vn->vn_free_ptr;
133
134 // FIXME: there is no check, that item operation did not
135 // consume too much memory
136 vn->vn_free_ptr +=
137 op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
138 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
139 reiserfs_panic(tb->tb_sb,
140 "vs-8030: create_virtual_node: "
141 "virtual node space consumed");
142
143 if (!is_affected)
144 /* this is not being changed */
145 continue;
146
147 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
148 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
149 vi->vi_new_data = vn->vn_data; // pointer to data which is going to be pasted
150 }
186 } 151 }
152
153 /* virtual inserted item is not defined yet */
154 if (vn->vn_mode == M_INSERT) {
155 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
156
157 RFALSE(vn->vn_ins_ih == 0,
158 "vs-8040: item header of inserted item is not specified");
159 vi->vi_item_len = tb->insert_size[0];
160 vi->vi_ih = vn->vn_ins_ih;
161 vi->vi_item = vn->vn_data;
162 vi->vi_uarea = vn->vn_free_ptr;
163
164 op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
165 tb->insert_size[0]);
166 }
167
168 /* set right merge flag we take right delimiting key and check whether it is a mergeable item */
169 if (tb->CFR[0]) {
170 struct reiserfs_key *key;
171
172 key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]);
173 if (op_is_left_mergeable(key, Sh->b_size)
174 && (vn->vn_mode != M_DELETE
175 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
176 vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
177 VI_TYPE_RIGHT_MERGEABLE;
178
179#ifdef CONFIG_REISERFS_CHECK
180 if (op_is_left_mergeable(key, Sh->b_size) &&
181 !(vn->vn_mode != M_DELETE
182 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
183 /* we delete last item and it could be merged with right neighbor's first item */
184 if (!
185 (B_NR_ITEMS(Sh) == 1
186 && is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0))
187 && I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) {
188 /* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
189 print_block(Sh, 0, -1, -1);
190 reiserfs_panic(tb->tb_sb,
191 "vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c",
192 key, vn->vn_affected_item_num,
193 vn->vn_mode, M_DELETE);
194 } else
195 /* we can delete directory item, that has only one directory entry in it */
196 ;
197 }
187#endif 198#endif
188
189 }
190}
191 199
200 }
201}
192 202
193/* using virtual node check, how many items can be shifted to left 203/* using virtual node check, how many items can be shifted to left
194 neighbor */ 204 neighbor */
195static void check_left (struct tree_balance * tb, int h, int cur_free) 205static void check_left(struct tree_balance *tb, int h, int cur_free)
196{ 206{
197 int i; 207 int i;
198 struct virtual_node * vn = tb->tb_vn; 208 struct virtual_node *vn = tb->tb_vn;
199 struct virtual_item * vi; 209 struct virtual_item *vi;
200 int d_size, ih_size; 210 int d_size, ih_size;
201 211
202 RFALSE( cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free); 212 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
203 213
204 /* internal level */ 214 /* internal level */
205 if (h > 0) { 215 if (h > 0) {
206 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); 216 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
207 return; 217 return;
208 } 218 }
209 219
210 /* leaf level */ 220 /* leaf level */
211 221
212 if (!cur_free || !vn->vn_nr_item) { 222 if (!cur_free || !vn->vn_nr_item) {
213 /* no free space or nothing to move */ 223 /* no free space or nothing to move */
214 tb->lnum[h] = 0; 224 tb->lnum[h] = 0;
215 tb->lbytes = -1; 225 tb->lbytes = -1;
216 return; 226 return;
217 } 227 }
218 228
219 RFALSE( !PATH_H_PPARENT (tb->tb_path, 0), 229 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
220 "vs-8055: parent does not exist or invalid"); 230 "vs-8055: parent does not exist or invalid");
221 231
222 vi = vn->vn_vi; 232 vi = vn->vn_vi;
223 if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) { 233 if ((unsigned int)cur_free >=
224 /* all contents of S[0] fits into L[0] */ 234 (vn->vn_size -
235 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
236 /* all contents of S[0] fits into L[0] */
225 237
226 RFALSE( vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, 238 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
227 "vs-8055: invalid mode or balance condition failed"); 239 "vs-8055: invalid mode or balance condition failed");
228 240
229 tb->lnum[0] = vn->vn_nr_item; 241 tb->lnum[0] = vn->vn_nr_item;
230 tb->lbytes = -1; 242 tb->lbytes = -1;
231 return; 243 return;
232 }
233
234
235 d_size = 0, ih_size = IH_SIZE;
236
237 /* first item may be merge with last item in left neighbor */
238 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
239 d_size = -((int)IH_SIZE), ih_size = 0;
240
241 tb->lnum[0] = 0;
242 for (i = 0; i < vn->vn_nr_item; i ++, ih_size = IH_SIZE, d_size = 0, vi ++) {
243 d_size += vi->vi_item_len;
244 if (cur_free >= d_size) {
245 /* the item can be shifted entirely */
246 cur_free -= d_size;
247 tb->lnum[0] ++;
248 continue;
249 } 244 }
250 245
251 /* the item cannot be shifted entirely, try to split it */ 246 d_size = 0, ih_size = IH_SIZE;
252 /* check whether L[0] can hold ih and at least one byte of the item body */ 247
253 if (cur_free <= ih_size) { 248 /* first item may be merge with last item in left neighbor */
254 /* cannot shift even a part of the current item */ 249 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
255 tb->lbytes = -1; 250 d_size = -((int)IH_SIZE), ih_size = 0;
256 return; 251
252 tb->lnum[0] = 0;
253 for (i = 0; i < vn->vn_nr_item;
254 i++, ih_size = IH_SIZE, d_size = 0, vi++) {
255 d_size += vi->vi_item_len;
256 if (cur_free >= d_size) {
257 /* the item can be shifted entirely */
258 cur_free -= d_size;
259 tb->lnum[0]++;
260 continue;
261 }
262
263 /* the item cannot be shifted entirely, try to split it */
264 /* check whether L[0] can hold ih and at least one byte of the item body */
265 if (cur_free <= ih_size) {
266 /* cannot shift even a part of the current item */
267 tb->lbytes = -1;
268 return;
269 }
270 cur_free -= ih_size;
271
272 tb->lbytes = op_check_left(vi, cur_free, 0, 0);
273 if (tb->lbytes != -1)
274 /* count partially shifted item */
275 tb->lnum[0]++;
276
277 break;
257 } 278 }
258 cur_free -= ih_size;
259
260 tb->lbytes = op_check_left (vi, cur_free, 0, 0);
261 if (tb->lbytes != -1)
262 /* count partially shifted item */
263 tb->lnum[0] ++;
264
265 break;
266 }
267
268 return;
269}
270 279
280 return;
281}
271 282
272/* using virtual node check, how many items can be shifted to right 283/* using virtual node check, how many items can be shifted to right
273 neighbor */ 284 neighbor */
274static void check_right (struct tree_balance * tb, int h, int cur_free) 285static void check_right(struct tree_balance *tb, int h, int cur_free)
275{ 286{
276 int i; 287 int i;
277 struct virtual_node * vn = tb->tb_vn; 288 struct virtual_node *vn = tb->tb_vn;
278 struct virtual_item * vi; 289 struct virtual_item *vi;
279 int d_size, ih_size; 290 int d_size, ih_size;
280 291
281 RFALSE( cur_free < 0, "vs-8070: cur_free < 0"); 292 RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
282 293
283 /* internal level */ 294 /* internal level */
284 if (h > 0) { 295 if (h > 0) {
285 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); 296 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
286 return; 297 return;
287 }
288
289 /* leaf level */
290
291 if (!cur_free || !vn->vn_nr_item) {
292 /* no free space */
293 tb->rnum[h] = 0;
294 tb->rbytes = -1;
295 return;
296 }
297
298 RFALSE( !PATH_H_PPARENT (tb->tb_path, 0),
299 "vs-8075: parent does not exist or invalid");
300
301 vi = vn->vn_vi + vn->vn_nr_item - 1;
302 if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
303 /* all contents of S[0] fits into R[0] */
304
305 RFALSE( vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
306 "vs-8080: invalid mode or balance condition failed");
307
308 tb->rnum[h] = vn->vn_nr_item;
309 tb->rbytes = -1;
310 return;
311 }
312
313 d_size = 0, ih_size = IH_SIZE;
314
315 /* last item may be merge with first item in right neighbor */
316 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
317 d_size = -(int)IH_SIZE, ih_size = 0;
318
319 tb->rnum[0] = 0;
320 for (i = vn->vn_nr_item - 1; i >= 0; i --, d_size = 0, ih_size = IH_SIZE, vi --) {
321 d_size += vi->vi_item_len;
322 if (cur_free >= d_size) {
323 /* the item can be shifted entirely */
324 cur_free -= d_size;
325 tb->rnum[0] ++;
326 continue;
327 } 298 }
328 299
329 /* check whether R[0] can hold ih and at least one byte of the item body */ 300 /* leaf level */
330 if ( cur_free <= ih_size ) { /* cannot shift even a part of the current item */ 301
331 tb->rbytes = -1; 302 if (!cur_free || !vn->vn_nr_item) {
332 return; 303 /* no free space */
304 tb->rnum[h] = 0;
305 tb->rbytes = -1;
306 return;
333 } 307 }
334
335 /* R[0] can hold the header of the item and at least one byte of its body */
336 cur_free -= ih_size; /* cur_free is still > 0 */
337
338 tb->rbytes = op_check_right (vi, cur_free);
339 if (tb->rbytes != -1)
340 /* count partially shifted item */
341 tb->rnum[0] ++;
342
343 break;
344 }
345
346 return;
347}
348 308
309 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
310 "vs-8075: parent does not exist or invalid");
311
312 vi = vn->vn_vi + vn->vn_nr_item - 1;
313 if ((unsigned int)cur_free >=
314 (vn->vn_size -
315 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
316 /* all contents of S[0] fits into R[0] */
317
318 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
319 "vs-8080: invalid mode or balance condition failed");
320
321 tb->rnum[h] = vn->vn_nr_item;
322 tb->rbytes = -1;
323 return;
324 }
325
326 d_size = 0, ih_size = IH_SIZE;
327
328 /* last item may be merge with first item in right neighbor */
329 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
330 d_size = -(int)IH_SIZE, ih_size = 0;
331
332 tb->rnum[0] = 0;
333 for (i = vn->vn_nr_item - 1; i >= 0;
334 i--, d_size = 0, ih_size = IH_SIZE, vi--) {
335 d_size += vi->vi_item_len;
336 if (cur_free >= d_size) {
337 /* the item can be shifted entirely */
338 cur_free -= d_size;
339 tb->rnum[0]++;
340 continue;
341 }
342
343 /* check whether R[0] can hold ih and at least one byte of the item body */
344 if (cur_free <= ih_size) { /* cannot shift even a part of the current item */
345 tb->rbytes = -1;
346 return;
347 }
348
349 /* R[0] can hold the header of the item and at least one byte of its body */
350 cur_free -= ih_size; /* cur_free is still > 0 */
351
352 tb->rbytes = op_check_right(vi, cur_free);
353 if (tb->rbytes != -1)
354 /* count partially shifted item */
355 tb->rnum[0]++;
356
357 break;
358 }
359
360 return;
361}
349 362
350/* 363/*
351 * from - number of items, which are shifted to left neighbor entirely 364 * from - number of items, which are shifted to left neighbor entirely
352 * to - number of item, which are shifted to right neighbor entirely 365 * to - number of item, which are shifted to right neighbor entirely
353 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor 366 * from_bytes - number of bytes of boundary item (or directory entries) which are shifted to left neighbor
354 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */ 367 * to_bytes - number of bytes of boundary item (or directory entries) which are shifted to right neighbor */
355static int get_num_ver (int mode, struct tree_balance * tb, int h, 368static int get_num_ver(int mode, struct tree_balance *tb, int h,
356 int from, int from_bytes, 369 int from, int from_bytes,
357 int to, int to_bytes, 370 int to, int to_bytes, short *snum012, int flow)
358 short * snum012, int flow
359 )
360{ 371{
361 int i; 372 int i;
362 int cur_free; 373 int cur_free;
363 // int bytes; 374 // int bytes;
364 int units; 375 int units;
365 struct virtual_node * vn = tb->tb_vn; 376 struct virtual_node *vn = tb->tb_vn;
366 // struct virtual_item * vi; 377 // struct virtual_item * vi;
367 378
368 int total_node_size, max_node_size, current_item_size; 379 int total_node_size, max_node_size, current_item_size;
369 int needed_nodes; 380 int needed_nodes;
370 int start_item, /* position of item we start filling node from */ 381 int start_item, /* position of item we start filling node from */
371 end_item, /* position of item we finish filling node by */ 382 end_item, /* position of item we finish filling node by */
372 start_bytes,/* number of first bytes (entries for directory) of start_item-th item 383 start_bytes, /* number of first bytes (entries for directory) of start_item-th item
373 we do not include into node that is being filled */ 384 we do not include into node that is being filled */
374 end_bytes; /* number of last bytes (entries for directory) of end_item-th item 385 end_bytes; /* number of last bytes (entries for directory) of end_item-th item
375 we do node include into node that is being filled */ 386 we do node include into node that is being filled */
376 int split_item_positions[2]; /* these are positions in virtual item of 387 int split_item_positions[2]; /* these are positions in virtual item of
377 items, that are split between S[0] and 388 items, that are split between S[0] and
378 S1new and S1new and S2new */ 389 S1new and S1new and S2new */
379 390
380 split_item_positions[0] = -1; 391 split_item_positions[0] = -1;
381 split_item_positions[1] = -1; 392 split_item_positions[1] = -1;
382 393
383 /* We only create additional nodes if we are in insert or paste mode 394 /* We only create additional nodes if we are in insert or paste mode
384 or we are in replace mode at the internal level. If h is 0 and 395 or we are in replace mode at the internal level. If h is 0 and
385 the mode is M_REPLACE then in fix_nodes we change the mode to 396 the mode is M_REPLACE then in fix_nodes we change the mode to
386 paste or insert before we get here in the code. */ 397 paste or insert before we get here in the code. */
387 RFALSE( tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), 398 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
388 "vs-8100: insert_size < 0 in overflow"); 399 "vs-8100: insert_size < 0 in overflow");
389 400
390 max_node_size = MAX_CHILD_SIZE (PATH_H_PBUFFER (tb->tb_path, h)); 401 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
391 402
392 /* snum012 [0-2] - number of items, that lay 403 /* snum012 [0-2] - number of items, that lay
393 to S[0], first new node and second new node */ 404 to S[0], first new node and second new node */
394 snum012[3] = -1; /* s1bytes */ 405 snum012[3] = -1; /* s1bytes */
395 snum012[4] = -1; /* s2bytes */ 406 snum012[4] = -1; /* s2bytes */
396 407
397 /* internal level */ 408 /* internal level */
398 if (h > 0) { 409 if (h > 0) {
399 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE); 410 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
400 if (i == max_node_size) 411 if (i == max_node_size)
401 return 1; 412 return 1;
402 return (i / max_node_size + 1); 413 return (i / max_node_size + 1);
403 }
404
405 /* leaf level */
406 needed_nodes = 1;
407 total_node_size = 0;
408 cur_free = max_node_size;
409
410 // start from 'from'-th item
411 start_item = from;
412 // skip its first 'start_bytes' units
413 start_bytes = ((from_bytes != -1) ? from_bytes : 0);
414
415 // last included item is the 'end_item'-th one
416 end_item = vn->vn_nr_item - to - 1;
417 // do not count last 'end_bytes' units of 'end_item'-th item
418 end_bytes = (to_bytes != -1) ? to_bytes : 0;
419
420 /* go through all item beginning from the start_item-th item and ending by
421 the end_item-th item. Do not count first 'start_bytes' units of
422 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
423
424 for (i = start_item; i <= end_item; i ++) {
425 struct virtual_item * vi = vn->vn_vi + i;
426 int skip_from_end = ((i == end_item) ? end_bytes : 0);
427
428 RFALSE( needed_nodes > 3, "vs-8105: too many nodes are needed");
429
430 /* get size of current item */
431 current_item_size = vi->vi_item_len;
432
433 /* do not take in calculation head part (from_bytes) of from-th item */
434 current_item_size -= op_part_size (vi, 0/*from start*/, start_bytes);
435
436 /* do not take in calculation tail part of last item */
437 current_item_size -= op_part_size (vi, 1/*from end*/, skip_from_end);
438
439 /* if item fits into current node entierly */
440 if (total_node_size + current_item_size <= max_node_size) {
441 snum012[needed_nodes - 1] ++;
442 total_node_size += current_item_size;
443 start_bytes = 0;
444 continue;
445 } 414 }
446 415
447 if (current_item_size > max_node_size) { 416 /* leaf level */
448 /* virtual item length is longer, than max size of item in 417 needed_nodes = 1;
449 a node. It is impossible for direct item */ 418 total_node_size = 0;
450 RFALSE( is_direct_le_ih (vi->vi_ih), 419 cur_free = max_node_size;
451 "vs-8110: " 420
452 "direct item length is %d. It can not be longer than %d", 421 // start from 'from'-th item
453 current_item_size, max_node_size); 422 start_item = from;
454 /* we will try to split it */ 423 // skip its first 'start_bytes' units
455 flow = 1; 424 start_bytes = ((from_bytes != -1) ? from_bytes : 0);
425
426 // last included item is the 'end_item'-th one
427 end_item = vn->vn_nr_item - to - 1;
428 // do not count last 'end_bytes' units of 'end_item'-th item
429 end_bytes = (to_bytes != -1) ? to_bytes : 0;
430
431 /* go through all item beginning from the start_item-th item and ending by
432 the end_item-th item. Do not count first 'start_bytes' units of
433 'start_item'-th item and last 'end_bytes' of 'end_item'-th item */
434
435 for (i = start_item; i <= end_item; i++) {
436 struct virtual_item *vi = vn->vn_vi + i;
437 int skip_from_end = ((i == end_item) ? end_bytes : 0);
438
439 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
440
441 /* get size of current item */
442 current_item_size = vi->vi_item_len;
443
444 /* do not take in calculation head part (from_bytes) of from-th item */
445 current_item_size -=
446 op_part_size(vi, 0 /*from start */ , start_bytes);
447
448 /* do not take in calculation tail part of last item */
449 current_item_size -=
450 op_part_size(vi, 1 /*from end */ , skip_from_end);
451
452 /* if item fits into current node entierly */
453 if (total_node_size + current_item_size <= max_node_size) {
454 snum012[needed_nodes - 1]++;
455 total_node_size += current_item_size;
456 start_bytes = 0;
457 continue;
458 }
459
460 if (current_item_size > max_node_size) {
461 /* virtual item length is longer, than max size of item in
462 a node. It is impossible for direct item */
463 RFALSE(is_direct_le_ih(vi->vi_ih),
464 "vs-8110: "
465 "direct item length is %d. It can not be longer than %d",
466 current_item_size, max_node_size);
467 /* we will try to split it */
468 flow = 1;
469 }
470
471 if (!flow) {
472 /* as we do not split items, take new node and continue */
473 needed_nodes++;
474 i--;
475 total_node_size = 0;
476 continue;
477 }
478 // calculate number of item units which fit into node being
479 // filled
480 {
481 int free_space;
482
483 free_space = max_node_size - total_node_size - IH_SIZE;
484 units =
485 op_check_left(vi, free_space, start_bytes,
486 skip_from_end);
487 if (units == -1) {
488 /* nothing fits into current node, take new node and continue */
489 needed_nodes++, i--, total_node_size = 0;
490 continue;
491 }
492 }
493
494 /* something fits into the current node */
495 //if (snum012[3] != -1 || needed_nodes != 1)
496 // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
497 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
498 start_bytes += units;
499 snum012[needed_nodes - 1 + 3] = units;
500
501 if (needed_nodes > 2)
502 reiserfs_warning(tb->tb_sb, "vs-8111: get_num_ver: "
503 "split_item_position is out of boundary");
504 snum012[needed_nodes - 1]++;
505 split_item_positions[needed_nodes - 1] = i;
506 needed_nodes++;
507 /* continue from the same item with start_bytes != -1 */
508 start_item = i;
509 i--;
510 total_node_size = 0;
456 } 511 }
457 512
458 if (!flow) { 513 // sum012[4] (if it is not -1) contains number of units of which
459 /* as we do not split items, take new node and continue */ 514 // are to be in S1new, snum012[3] - to be in S0. They are supposed
460 needed_nodes ++; i --; total_node_size = 0; 515 // to be S1bytes and S2bytes correspondingly, so recalculate
461 continue; 516 if (snum012[4] > 0) {
517 int split_item_num;
518 int bytes_to_r, bytes_to_l;
519 int bytes_to_S1new;
520
521 split_item_num = split_item_positions[1];
522 bytes_to_l =
523 ((from == split_item_num
524 && from_bytes != -1) ? from_bytes : 0);
525 bytes_to_r =
526 ((end_item == split_item_num
527 && end_bytes != -1) ? end_bytes : 0);
528 bytes_to_S1new =
529 ((split_item_positions[0] ==
530 split_item_positions[1]) ? snum012[3] : 0);
531
532 // s2bytes
533 snum012[4] =
534 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
535 bytes_to_r - bytes_to_l - bytes_to_S1new;
536
537 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
538 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
539 reiserfs_warning(tb->tb_sb, "vs-8115: get_num_ver: not "
540 "directory or indirect item");
462 } 541 }
463 542
464 // calculate number of item units which fit into node being 543 /* now we know S2bytes, calculate S1bytes */
465 // filled 544 if (snum012[3] > 0) {
466 { 545 int split_item_num;
467 int free_space; 546 int bytes_to_r, bytes_to_l;
468 547 int bytes_to_S2new;
469 free_space = max_node_size - total_node_size - IH_SIZE; 548
470 units = op_check_left (vi, free_space, start_bytes, skip_from_end); 549 split_item_num = split_item_positions[0];
471 if (units == -1) { 550 bytes_to_l =
472 /* nothing fits into current node, take new node and continue */ 551 ((from == split_item_num
473 needed_nodes ++, i--, total_node_size = 0; 552 && from_bytes != -1) ? from_bytes : 0);
474 continue; 553 bytes_to_r =
475 } 554 ((end_item == split_item_num
555 && end_bytes != -1) ? end_bytes : 0);
556 bytes_to_S2new =
557 ((split_item_positions[0] == split_item_positions[1]
558 && snum012[4] != -1) ? snum012[4] : 0);
559
560 // s1bytes
561 snum012[3] =
562 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
563 bytes_to_r - bytes_to_l - bytes_to_S2new;
476 } 564 }
477 565
478 /* something fits into the current node */ 566 return needed_nodes;
479 //if (snum012[3] != -1 || needed_nodes != 1)
480 // reiserfs_panic (tb->tb_sb, "vs-8115: get_num_ver: too many nodes required");
481 //snum012[needed_nodes - 1 + 3] = op_unit_num (vi) - start_bytes - units;
482 start_bytes += units;
483 snum012[needed_nodes - 1 + 3] = units;
484
485 if (needed_nodes > 2)
486 reiserfs_warning (tb->tb_sb, "vs-8111: get_num_ver: "
487 "split_item_position is out of boundary");
488 snum012[needed_nodes - 1] ++;
489 split_item_positions[needed_nodes - 1] = i;
490 needed_nodes ++;
491 /* continue from the same item with start_bytes != -1 */
492 start_item = i;
493 i --;
494 total_node_size = 0;
495 }
496
497 // sum012[4] (if it is not -1) contains number of units of which
498 // are to be in S1new, snum012[3] - to be in S0. They are supposed
499 // to be S1bytes and S2bytes correspondingly, so recalculate
500 if (snum012[4] > 0) {
501 int split_item_num;
502 int bytes_to_r, bytes_to_l;
503 int bytes_to_S1new;
504
505 split_item_num = split_item_positions[1];
506 bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
507 bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
508 bytes_to_S1new = ((split_item_positions[0] == split_item_positions[1]) ? snum012[3] : 0);
509
510 // s2bytes
511 snum012[4] = op_unit_num (&vn->vn_vi[split_item_num]) - snum012[4] - bytes_to_r - bytes_to_l - bytes_to_S1new;
512
513 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
514 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
515 reiserfs_warning (tb->tb_sb, "vs-8115: get_num_ver: not "
516 "directory or indirect item");
517 }
518
519 /* now we know S2bytes, calculate S1bytes */
520 if (snum012[3] > 0) {
521 int split_item_num;
522 int bytes_to_r, bytes_to_l;
523 int bytes_to_S2new;
524
525 split_item_num = split_item_positions[0];
526 bytes_to_l = ((from == split_item_num && from_bytes != -1) ? from_bytes : 0);
527 bytes_to_r = ((end_item == split_item_num && end_bytes != -1) ? end_bytes : 0);
528 bytes_to_S2new = ((split_item_positions[0] == split_item_positions[1] && snum012[4] != -1) ? snum012[4] : 0);
529
530 // s1bytes
531 snum012[3] = op_unit_num (&vn->vn_vi[split_item_num]) - snum012[3] - bytes_to_r - bytes_to_l - bytes_to_S2new;
532 }
533
534 return needed_nodes;
535} 567}
536 568
537
538#ifdef CONFIG_REISERFS_CHECK 569#ifdef CONFIG_REISERFS_CHECK
539extern struct tree_balance * cur_tb; 570extern struct tree_balance *cur_tb;
540#endif 571#endif
541 572
542
543/* Set parameters for balancing. 573/* Set parameters for balancing.
544 * Performs write of results of analysis of balancing into structure tb, 574 * Performs write of results of analysis of balancing into structure tb,
545 * where it will later be used by the functions that actually do the balancing. 575 * where it will later be used by the functions that actually do the balancing.
@@ -557,131 +587,130 @@ extern struct tree_balance * cur_tb;
557 * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array) 587 * s1bytes number of bytes which flow to the first new node when S[0] splits (this number is contained in s012 array)
558 */ 588 */
559 589
560static void set_parameters (struct tree_balance * tb, int h, int lnum, 590static void set_parameters(struct tree_balance *tb, int h, int lnum,
561 int rnum, int blk_num, short * s012, int lb, int rb) 591 int rnum, int blk_num, short *s012, int lb, int rb)
562{ 592{
563 593
564 tb->lnum[h] = lnum; 594 tb->lnum[h] = lnum;
565 tb->rnum[h] = rnum; 595 tb->rnum[h] = rnum;
566 tb->blknum[h] = blk_num; 596 tb->blknum[h] = blk_num;
567 597
568 if (h == 0) 598 if (h == 0) { /* only for leaf level */
569 { /* only for leaf level */ 599 if (s012 != NULL) {
570 if (s012 != NULL) 600 tb->s0num = *s012++,
571 { 601 tb->s1num = *s012++, tb->s2num = *s012++;
572 tb->s0num = * s012 ++, 602 tb->s1bytes = *s012++;
573 tb->s1num = * s012 ++, 603 tb->s2bytes = *s012;
574 tb->s2num = * s012 ++; 604 }
575 tb->s1bytes = * s012 ++; 605 tb->lbytes = lb;
576 tb->s2bytes = * s012; 606 tb->rbytes = rb;
577 } 607 }
578 tb->lbytes = lb; 608 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
579 tb->rbytes = rb; 609 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
580 }
581 PROC_INFO_ADD( tb -> tb_sb, lnum[ h ], lnum );
582 PROC_INFO_ADD( tb -> tb_sb, rnum[ h ], rnum );
583
584 PROC_INFO_ADD( tb -> tb_sb, lbytes[ h ], lb );
585 PROC_INFO_ADD( tb -> tb_sb, rbytes[ h ], rb );
586}
587
588 610
611 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
612 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
613}
589 614
590/* check, does node disappear if we shift tb->lnum[0] items to left 615/* check, does node disappear if we shift tb->lnum[0] items to left
591 neighbor and tb->rnum[0] to the right one. */ 616 neighbor and tb->rnum[0] to the right one. */
592static int is_leaf_removable (struct tree_balance * tb) 617static int is_leaf_removable(struct tree_balance *tb)
593{ 618{
594 struct virtual_node * vn = tb->tb_vn; 619 struct virtual_node *vn = tb->tb_vn;
595 int to_left, to_right; 620 int to_left, to_right;
596 int size; 621 int size;
597 int remain_items; 622 int remain_items;
598 623
599 /* number of items, that will be shifted to left (right) neighbor 624 /* number of items, that will be shifted to left (right) neighbor
600 entirely */ 625 entirely */
601 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0); 626 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
602 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0); 627 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
603 remain_items = vn->vn_nr_item; 628 remain_items = vn->vn_nr_item;
604 629
605 /* how many items remain in S[0] after shiftings to neighbors */ 630 /* how many items remain in S[0] after shiftings to neighbors */
606 remain_items -= (to_left + to_right); 631 remain_items -= (to_left + to_right);
607 632
608 if (remain_items < 1) { 633 if (remain_items < 1) {
609 /* all content of node can be shifted to neighbors */ 634 /* all content of node can be shifted to neighbors */
610 set_parameters (tb, 0, to_left, vn->vn_nr_item - to_left, 0, NULL, -1, -1); 635 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
611 return 1; 636 NULL, -1, -1);
612 } 637 return 1;
613 638 }
614 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
615 /* S[0] is not removable */
616 return 0;
617
618 /* check, whether we can divide 1 remaining item between neighbors */
619
620 /* get size of remaining item (in item units) */
621 size = op_unit_num (&(vn->vn_vi[to_left]));
622
623 if (tb->lbytes + tb->rbytes >= size) {
624 set_parameters (tb, 0, to_left + 1, to_right + 1, 0, NULL, tb->lbytes, -1);
625 return 1;
626 }
627
628 return 0;
629}
630 639
640 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
641 /* S[0] is not removable */
642 return 0;
643
644 /* check, whether we can divide 1 remaining item between neighbors */
645
646 /* get size of remaining item (in item units) */
647 size = op_unit_num(&(vn->vn_vi[to_left]));
648
649 if (tb->lbytes + tb->rbytes >= size) {
650 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
651 tb->lbytes, -1);
652 return 1;
653 }
654
655 return 0;
656}
631 657
632/* check whether L, S, R can be joined in one node */ 658/* check whether L, S, R can be joined in one node */
633static int are_leaves_removable (struct tree_balance * tb, int lfree, int rfree) 659static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
634{ 660{
635 struct virtual_node * vn = tb->tb_vn; 661 struct virtual_node *vn = tb->tb_vn;
636 int ih_size; 662 int ih_size;
637 struct buffer_head *S0; 663 struct buffer_head *S0;
638 664
639 S0 = PATH_H_PBUFFER (tb->tb_path, 0); 665 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
640 666
641 ih_size = 0; 667 ih_size = 0;
642 if (vn->vn_nr_item) { 668 if (vn->vn_nr_item) {
643 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE) 669 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
644 ih_size += IH_SIZE; 670 ih_size += IH_SIZE;
645 671
646 if (vn->vn_vi[vn->vn_nr_item-1].vi_type & VI_TYPE_RIGHT_MERGEABLE) 672 if (vn->vn_vi[vn->vn_nr_item - 1].
647 ih_size += IH_SIZE; 673 vi_type & VI_TYPE_RIGHT_MERGEABLE)
648 } else { 674 ih_size += IH_SIZE;
649 /* there was only one item and it will be deleted */ 675 } else {
650 struct item_head * ih; 676 /* there was only one item and it will be deleted */
651 677 struct item_head *ih;
652 RFALSE( B_NR_ITEMS (S0) != 1, 678
653 "vs-8125: item number must be 1: it is %d", B_NR_ITEMS(S0)); 679 RFALSE(B_NR_ITEMS(S0) != 1,
654 680 "vs-8125: item number must be 1: it is %d",
655 ih = B_N_PITEM_HEAD (S0, 0); 681 B_NR_ITEMS(S0));
656 if (tb->CFR[0] && !comp_short_le_keys (&(ih->ih_key), B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]))) 682
657 if (is_direntry_le_ih (ih)) { 683 ih = B_N_PITEM_HEAD(S0, 0);
658 /* Directory must be in correct state here: that is 684 if (tb->CFR[0]
659 somewhere at the left side should exist first directory 685 && !comp_short_le_keys(&(ih->ih_key),
660 item. But the item being deleted can not be that first 686 B_N_PDELIM_KEY(tb->CFR[0],
661 one because its right neighbor is item of the same 687 tb->rkey[0])))
662 directory. (But first item always gets deleted in last 688 if (is_direntry_le_ih(ih)) {
663 turn). So, neighbors of deleted item can be merged, so 689 /* Directory must be in correct state here: that is
664 we can save ih_size */ 690 somewhere at the left side should exist first directory
665 ih_size = IH_SIZE; 691 item. But the item being deleted can not be that first
666 692 one because its right neighbor is item of the same
667 /* we might check that left neighbor exists and is of the 693 directory. (But first item always gets deleted in last
668 same directory */ 694 turn). So, neighbors of deleted item can be merged, so
669 RFALSE(le_ih_k_offset (ih) == DOT_OFFSET, 695 we can save ih_size */
670 "vs-8130: first directory item can not be removed until directory is not empty"); 696 ih_size = IH_SIZE;
671 } 697
672 698 /* we might check that left neighbor exists and is of the
673 } 699 same directory */
674 700 RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
675 if (MAX_CHILD_SIZE (S0) + vn->vn_size <= rfree + lfree + ih_size) { 701 "vs-8130: first directory item can not be removed until directory is not empty");
676 set_parameters (tb, 0, -1, -1, -1, NULL, -1, -1); 702 }
677 PROC_INFO_INC( tb -> tb_sb, leaves_removable );
678 return 1;
679 }
680 return 0;
681
682}
683 703
704 }
705
706 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
707 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
708 PROC_INFO_INC(tb->tb_sb, leaves_removable);
709 return 1;
710 }
711 return 0;
684 712
713}
685 714
686/* when we do not split item, lnum and rnum are numbers of entire items */ 715/* when we do not split item, lnum and rnum are numbers of entire items */
687#define SET_PAR_SHIFT_LEFT \ 716#define SET_PAR_SHIFT_LEFT \
@@ -704,7 +733,6 @@ else \
704 -1, -1);\ 733 -1, -1);\
705} 734}
706 735
707
708#define SET_PAR_SHIFT_RIGHT \ 736#define SET_PAR_SHIFT_RIGHT \
709if (h)\ 737if (h)\
710{\ 738{\
@@ -724,214 +752,199 @@ else \
724 -1, -1);\ 752 -1, -1);\
725} 753}
726 754
727 755static void free_buffers_in_tb(struct tree_balance *p_s_tb)
728static void free_buffers_in_tb ( 756{
729 struct tree_balance * p_s_tb 757 int n_counter;
730 ) { 758
731 int n_counter; 759 decrement_counters_in_path(p_s_tb->tb_path);
732 760
733 decrement_counters_in_path(p_s_tb->tb_path); 761 for (n_counter = 0; n_counter < MAX_HEIGHT; n_counter++) {
734 762 decrement_bcount(p_s_tb->L[n_counter]);
735 for ( n_counter = 0; n_counter < MAX_HEIGHT; n_counter++ ) { 763 p_s_tb->L[n_counter] = NULL;
736 decrement_bcount(p_s_tb->L[n_counter]); 764 decrement_bcount(p_s_tb->R[n_counter]);
737 p_s_tb->L[n_counter] = NULL; 765 p_s_tb->R[n_counter] = NULL;
738 decrement_bcount(p_s_tb->R[n_counter]); 766 decrement_bcount(p_s_tb->FL[n_counter]);
739 p_s_tb->R[n_counter] = NULL; 767 p_s_tb->FL[n_counter] = NULL;
740 decrement_bcount(p_s_tb->FL[n_counter]); 768 decrement_bcount(p_s_tb->FR[n_counter]);
741 p_s_tb->FL[n_counter] = NULL; 769 p_s_tb->FR[n_counter] = NULL;
742 decrement_bcount(p_s_tb->FR[n_counter]); 770 decrement_bcount(p_s_tb->CFL[n_counter]);
743 p_s_tb->FR[n_counter] = NULL; 771 p_s_tb->CFL[n_counter] = NULL;
744 decrement_bcount(p_s_tb->CFL[n_counter]); 772 decrement_bcount(p_s_tb->CFR[n_counter]);
745 p_s_tb->CFL[n_counter] = NULL; 773 p_s_tb->CFR[n_counter] = NULL;
746 decrement_bcount(p_s_tb->CFR[n_counter]); 774 }
747 p_s_tb->CFR[n_counter] = NULL;
748 }
749} 775}
750 776
751
752/* Get new buffers for storing new nodes that are created while balancing. 777/* Get new buffers for storing new nodes that are created while balancing.
753 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 778 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
754 * CARRY_ON - schedule didn't occur while the function worked; 779 * CARRY_ON - schedule didn't occur while the function worked;
755 * NO_DISK_SPACE - no disk space. 780 * NO_DISK_SPACE - no disk space.
756 */ 781 */
757/* The function is NOT SCHEDULE-SAFE! */ 782/* The function is NOT SCHEDULE-SAFE! */
758static int get_empty_nodes( 783static int get_empty_nodes(struct tree_balance *p_s_tb, int n_h)
759 struct tree_balance * p_s_tb, 784{
760 int n_h 785 struct buffer_head *p_s_new_bh,
761 ) { 786 *p_s_Sh = PATH_H_PBUFFER(p_s_tb->tb_path, n_h);
762 struct buffer_head * p_s_new_bh, 787 b_blocknr_t *p_n_blocknr, a_n_blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
763 * p_s_Sh = PATH_H_PBUFFER (p_s_tb->tb_path, n_h); 788 int n_counter, n_number_of_freeblk, n_amount_needed, /* number of needed empty blocks */
764 b_blocknr_t * p_n_blocknr, 789 n_retval = CARRY_ON;
765 a_n_blocknrs[MAX_AMOUNT_NEEDED] = {0, }; 790 struct super_block *p_s_sb = p_s_tb->tb_sb;
766 int n_counter, 791
767 n_number_of_freeblk, 792 /* number_of_freeblk is the number of empty blocks which have been
768 n_amount_needed,/* number of needed empty blocks */ 793 acquired for use by the balancing algorithm minus the number of
769 n_retval = CARRY_ON; 794 empty blocks used in the previous levels of the analysis,
770 struct super_block * p_s_sb = p_s_tb->tb_sb; 795 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs
771 796 after empty blocks are acquired, and the balancing analysis is
772 797 then restarted, amount_needed is the number needed by this level
773 /* number_of_freeblk is the number of empty blocks which have been 798 (n_h) of the balancing analysis.
774 acquired for use by the balancing algorithm minus the number of 799
775 empty blocks used in the previous levels of the analysis, 800 Note that for systems with many processes writing, it would be
776 number_of_freeblk = tb->cur_blknum can be non-zero if a schedule occurs 801 more layout optimal to calculate the total number needed by all
777 after empty blocks are acquired, and the balancing analysis is 802 levels and then to run reiserfs_new_blocks to get all of them at once. */
778 then restarted, amount_needed is the number needed by this level 803
779 (n_h) of the balancing analysis. 804 /* Initiate number_of_freeblk to the amount acquired prior to the restart of
780 805 the analysis or 0 if not restarted, then subtract the amount needed
781 Note that for systems with many processes writing, it would be 806 by all of the levels of the tree below n_h. */
782 more layout optimal to calculate the total number needed by all 807 /* blknum includes S[n_h], so we subtract 1 in this calculation */
783 levels and then to run reiserfs_new_blocks to get all of them at once. */ 808 for (n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum;
784 809 n_counter < n_h; n_counter++)
785 /* Initiate number_of_freeblk to the amount acquired prior to the restart of 810 n_number_of_freeblk -=
786 the analysis or 0 if not restarted, then subtract the amount needed 811 (p_s_tb->blknum[n_counter]) ? (p_s_tb->blknum[n_counter] -
787 by all of the levels of the tree below n_h. */ 812 1) : 0;
788 /* blknum includes S[n_h], so we subtract 1 in this calculation */ 813
789 for ( n_counter = 0, n_number_of_freeblk = p_s_tb->cur_blknum; n_counter < n_h; n_counter++ ) 814 /* Allocate missing empty blocks. */
790 n_number_of_freeblk -= ( p_s_tb->blknum[n_counter] ) ? (p_s_tb->blknum[n_counter] - 1) : 0; 815 /* if p_s_Sh == 0 then we are getting a new root */
791 816 n_amount_needed = (p_s_Sh) ? (p_s_tb->blknum[n_h] - 1) : 1;
792 /* Allocate missing empty blocks. */ 817 /* Amount_needed = the amount that we need more than the amount that we have. */
793 /* if p_s_Sh == 0 then we are getting a new root */ 818 if (n_amount_needed > n_number_of_freeblk)
794 n_amount_needed = ( p_s_Sh ) ? (p_s_tb->blknum[n_h] - 1) : 1; 819 n_amount_needed -= n_number_of_freeblk;
795 /* Amount_needed = the amount that we need more than the amount that we have. */ 820 else /* If we have enough already then there is nothing to do. */
796 if ( n_amount_needed > n_number_of_freeblk ) 821 return CARRY_ON;
797 n_amount_needed -= n_number_of_freeblk; 822
798 else /* If we have enough already then there is nothing to do. */ 823 /* No need to check quota - is not allocated for blocks used for formatted nodes */
799 return CARRY_ON; 824 if (reiserfs_new_form_blocknrs(p_s_tb, a_n_blocknrs,
800 825 n_amount_needed) == NO_DISK_SPACE)
801 /* No need to check quota - is not allocated for blocks used for formatted nodes */ 826 return NO_DISK_SPACE;
802 if (reiserfs_new_form_blocknrs (p_s_tb, a_n_blocknrs, 827
803 n_amount_needed) == NO_DISK_SPACE) 828 /* for each blocknumber we just got, get a buffer and stick it on FEB */
804 return NO_DISK_SPACE; 829 for (p_n_blocknr = a_n_blocknrs, n_counter = 0;
805 830 n_counter < n_amount_needed; p_n_blocknr++, n_counter++) {
806 /* for each blocknumber we just got, get a buffer and stick it on FEB */ 831
807 for ( p_n_blocknr = a_n_blocknrs, n_counter = 0; n_counter < n_amount_needed; 832 RFALSE(!*p_n_blocknr,
808 p_n_blocknr++, n_counter++ ) { 833 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
809 834
810 RFALSE( ! *p_n_blocknr, 835 p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr);
811 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks"); 836 RFALSE(buffer_dirty(p_s_new_bh) ||
812 837 buffer_journaled(p_s_new_bh) ||
813 p_s_new_bh = sb_getblk(p_s_sb, *p_n_blocknr); 838 buffer_journal_dirty(p_s_new_bh),
814 RFALSE (buffer_dirty (p_s_new_bh) || 839 "PAP-8140: journlaled or dirty buffer %b for the new block",
815 buffer_journaled (p_s_new_bh) || 840 p_s_new_bh);
816 buffer_journal_dirty (p_s_new_bh), 841
817 "PAP-8140: journlaled or dirty buffer %b for the new block", 842 /* Put empty buffers into the array. */
818 p_s_new_bh); 843 RFALSE(p_s_tb->FEB[p_s_tb->cur_blknum],
819 844 "PAP-8141: busy slot for new buffer");
820 /* Put empty buffers into the array. */ 845
821 RFALSE (p_s_tb->FEB[p_s_tb->cur_blknum], 846 set_buffer_journal_new(p_s_new_bh);
822 "PAP-8141: busy slot for new buffer"); 847 p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh;
823 848 }
824 set_buffer_journal_new (p_s_new_bh); 849
825 p_s_tb->FEB[p_s_tb->cur_blknum++] = p_s_new_bh; 850 if (n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB(p_s_tb))
826 } 851 n_retval = REPEAT_SEARCH;
827
828 if ( n_retval == CARRY_ON && FILESYSTEM_CHANGED_TB (p_s_tb) )
829 n_retval = REPEAT_SEARCH ;
830
831 return n_retval;
832}
833 852
853 return n_retval;
854}
834 855
835/* Get free space of the left neighbor, which is stored in the parent 856/* Get free space of the left neighbor, which is stored in the parent
836 * node of the left neighbor. */ 857 * node of the left neighbor. */
837static int get_lfree (struct tree_balance * tb, int h) 858static int get_lfree(struct tree_balance *tb, int h)
838{ 859{
839 struct buffer_head * l, * f; 860 struct buffer_head *l, *f;
840 int order; 861 int order;
841 862
842 if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0) 863 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == 0 || (l = tb->FL[h]) == 0)
843 return 0; 864 return 0;
844 865
845 if (f == l) 866 if (f == l)
846 order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) - 1; 867 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
847 else { 868 else {
848 order = B_NR_ITEMS (l); 869 order = B_NR_ITEMS(l);
849 f = l; 870 f = l;
850 } 871 }
851 872
852 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f,order))); 873 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
853} 874}
854 875
855
856/* Get free space of the right neighbor, 876/* Get free space of the right neighbor,
857 * which is stored in the parent node of the right neighbor. 877 * which is stored in the parent node of the right neighbor.
858 */ 878 */
859static int get_rfree (struct tree_balance * tb, int h) 879static int get_rfree(struct tree_balance *tb, int h)
860{ 880{
861 struct buffer_head * r, * f; 881 struct buffer_head *r, *f;
862 int order; 882 int order;
863 883
864 if ((f = PATH_H_PPARENT (tb->tb_path, h)) == 0 || (r = tb->FR[h]) == 0) 884 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == 0 || (r = tb->FR[h]) == 0)
865 return 0; 885 return 0;
866 886
867 if (f == r) 887 if (f == r)
868 order = PATH_H_B_ITEM_ORDER (tb->tb_path, h) + 1; 888 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
869 else { 889 else {
870 order = 0; 890 order = 0;
871 f = r; 891 f = r;
872 } 892 }
873 893
874 return (MAX_CHILD_SIZE(f) - dc_size( B_N_CHILD(f,order))); 894 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
875 895
876} 896}
877 897
878
879/* Check whether left neighbor is in memory. */ 898/* Check whether left neighbor is in memory. */
880static int is_left_neighbor_in_cache( 899static int is_left_neighbor_in_cache(struct tree_balance *p_s_tb, int n_h)
881 struct tree_balance * p_s_tb, 900{
882 int n_h 901 struct buffer_head *p_s_father, *left;
883 ) { 902 struct super_block *p_s_sb = p_s_tb->tb_sb;
884 struct buffer_head * p_s_father, * left; 903 b_blocknr_t n_left_neighbor_blocknr;
885 struct super_block * p_s_sb = p_s_tb->tb_sb; 904 int n_left_neighbor_position;
886 b_blocknr_t n_left_neighbor_blocknr; 905
887 int n_left_neighbor_position; 906 if (!p_s_tb->FL[n_h]) /* Father of the left neighbor does not exist. */
888 907 return 0;
889 if ( ! p_s_tb->FL[n_h] ) /* Father of the left neighbor does not exist. */ 908
890 return 0; 909 /* Calculate father of the node to be balanced. */
891 910 p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1);
892 /* Calculate father of the node to be balanced. */ 911
893 p_s_father = PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1); 912 RFALSE(!p_s_father ||
894 913 !B_IS_IN_TREE(p_s_father) ||
895 RFALSE( ! p_s_father || 914 !B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
896 ! B_IS_IN_TREE (p_s_father) || 915 !buffer_uptodate(p_s_father) ||
897 ! B_IS_IN_TREE (p_s_tb->FL[n_h]) || 916 !buffer_uptodate(p_s_tb->FL[n_h]),
898 ! buffer_uptodate (p_s_father) || 917 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
899 ! buffer_uptodate (p_s_tb->FL[n_h]), 918 p_s_father, p_s_tb->FL[n_h]);
900 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid", 919
901 p_s_father, p_s_tb->FL[n_h]); 920 /* Get position of the pointer to the left neighbor into the left father. */
902 921 n_left_neighbor_position = (p_s_father == p_s_tb->FL[n_h]) ?
903 922 p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->FL[n_h]);
904 /* Get position of the pointer to the left neighbor into the left father. */ 923 /* Get left neighbor block number. */
905 n_left_neighbor_position = ( p_s_father == p_s_tb->FL[n_h] ) ? 924 n_left_neighbor_blocknr =
906 p_s_tb->lkey[n_h] : B_NR_ITEMS (p_s_tb->FL[n_h]); 925 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position);
907 /* Get left neighbor block number. */ 926 /* Look for the left neighbor in the cache. */
908 n_left_neighbor_blocknr = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_left_neighbor_position); 927 if ((left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr))) {
909 /* Look for the left neighbor in the cache. */ 928
910 if ( (left = sb_find_get_block(p_s_sb, n_left_neighbor_blocknr)) ) { 929 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
911 930 "vs-8170: left neighbor (%b %z) is not in the tree",
912 RFALSE( buffer_uptodate (left) && ! B_IS_IN_TREE(left), 931 left, left);
913 "vs-8170: left neighbor (%b %z) is not in the tree", left, left); 932 put_bh(left);
914 put_bh(left) ; 933 return 1;
915 return 1; 934 }
916 }
917
918 return 0;
919}
920 935
936 return 0;
937}
921 938
922#define LEFT_PARENTS 'l' 939#define LEFT_PARENTS 'l'
923#define RIGHT_PARENTS 'r' 940#define RIGHT_PARENTS 'r'
924 941
925 942static void decrement_key(struct cpu_key *p_s_key)
926static void decrement_key (struct cpu_key * p_s_key)
927{ 943{
928 // call item specific function for this key 944 // call item specific function for this key
929 item_ops[cpu_key_k_type (p_s_key)]->decrement_key (p_s_key); 945 item_ops[cpu_key_k_type(p_s_key)]->decrement_key(p_s_key);
930} 946}
931 947
932
933
934
935/* Calculate far left/right parent of the left/right neighbor of the current node, that 948/* Calculate far left/right parent of the left/right neighbor of the current node, that
936 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h]. 949 * is calculate the left/right (FL[h]/FR[h]) neighbor of the parent F[h].
937 * Calculate left/right common parent of the current node and L[h]/R[h]. 950 * Calculate left/right common parent of the current node and L[h]/R[h].
@@ -940,111 +953,121 @@ static void decrement_key (struct cpu_key * p_s_key)
940 SCHEDULE_OCCURRED - schedule occurred while the function worked; 953 SCHEDULE_OCCURRED - schedule occurred while the function worked;
941 * CARRY_ON - schedule didn't occur while the function worked; 954 * CARRY_ON - schedule didn't occur while the function worked;
942 */ 955 */
943static int get_far_parent (struct tree_balance * p_s_tb, 956static int get_far_parent(struct tree_balance *p_s_tb,
944 int n_h, 957 int n_h,
945 struct buffer_head ** pp_s_father, 958 struct buffer_head **pp_s_father,
946 struct buffer_head ** pp_s_com_father, 959 struct buffer_head **pp_s_com_father, char c_lr_par)
947 char c_lr_par)
948{ 960{
949 struct buffer_head * p_s_parent; 961 struct buffer_head *p_s_parent;
950 INITIALIZE_PATH (s_path_to_neighbor_father); 962 INITIALIZE_PATH(s_path_to_neighbor_father);
951 struct path * p_s_path = p_s_tb->tb_path; 963 struct path *p_s_path = p_s_tb->tb_path;
952 struct cpu_key s_lr_father_key; 964 struct cpu_key s_lr_father_key;
953 int n_counter, 965 int n_counter,
954 n_position = INT_MAX, 966 n_position = INT_MAX,
955 n_first_last_position = 0, 967 n_first_last_position = 0,
956 n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h); 968 n_path_offset = PATH_H_PATH_OFFSET(p_s_path, n_h);
957 969
958 /* Starting from F[n_h] go upwards in the tree, and look for the common 970 /* Starting from F[n_h] go upwards in the tree, and look for the common
959 ancestor of F[n_h], and its neighbor l/r, that should be obtained. */ 971 ancestor of F[n_h], and its neighbor l/r, that should be obtained. */
960 972
961 n_counter = n_path_offset; 973 n_counter = n_path_offset;
962 974
963 RFALSE( n_counter < FIRST_PATH_ELEMENT_OFFSET, 975 RFALSE(n_counter < FIRST_PATH_ELEMENT_OFFSET,
964 "PAP-8180: invalid path length"); 976 "PAP-8180: invalid path length");
965 977
966 978 for (; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter--) {
967 for ( ; n_counter > FIRST_PATH_ELEMENT_OFFSET; n_counter-- ) { 979 /* Check whether parent of the current buffer in the path is really parent in the tree. */
968 /* Check whether parent of the current buffer in the path is really parent in the tree. */ 980 if (!B_IS_IN_TREE
969 if ( ! B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)) ) 981 (p_s_parent = PATH_OFFSET_PBUFFER(p_s_path, n_counter - 1)))
970 return REPEAT_SEARCH; 982 return REPEAT_SEARCH;
971 /* Check whether position in the parent is correct. */ 983 /* Check whether position in the parent is correct. */
972 if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_counter - 1)) > B_NR_ITEMS(p_s_parent) ) 984 if ((n_position =
973 return REPEAT_SEARCH; 985 PATH_OFFSET_POSITION(p_s_path,
974 /* Check whether parent at the path really points to the child. */ 986 n_counter - 1)) >
975 if ( B_N_CHILD_NUM(p_s_parent, n_position) != 987 B_NR_ITEMS(p_s_parent))
976 PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr ) 988 return REPEAT_SEARCH;
977 return REPEAT_SEARCH; 989 /* Check whether parent at the path really points to the child. */
978 /* Return delimiting key if position in the parent is not equal to first/last one. */ 990 if (B_N_CHILD_NUM(p_s_parent, n_position) !=
979 if ( c_lr_par == RIGHT_PARENTS ) 991 PATH_OFFSET_PBUFFER(p_s_path, n_counter)->b_blocknr)
980 n_first_last_position = B_NR_ITEMS (p_s_parent); 992 return REPEAT_SEARCH;
981 if ( n_position != n_first_last_position ) { 993 /* Return delimiting key if position in the parent is not equal to first/last one. */
982 *pp_s_com_father = p_s_parent; 994 if (c_lr_par == RIGHT_PARENTS)
983 get_bh(*pp_s_com_father) ; 995 n_first_last_position = B_NR_ITEMS(p_s_parent);
984 /*(*pp_s_com_father = p_s_parent)->b_count++;*/ 996 if (n_position != n_first_last_position) {
985 break; 997 *pp_s_com_father = p_s_parent;
998 get_bh(*pp_s_com_father);
999 /*(*pp_s_com_father = p_s_parent)->b_count++; */
1000 break;
1001 }
986 } 1002 }
987 } 1003
988 1004 /* if we are in the root of the tree, then there is no common father */
989 /* if we are in the root of the tree, then there is no common father */ 1005 if (n_counter == FIRST_PATH_ELEMENT_OFFSET) {
990 if ( n_counter == FIRST_PATH_ELEMENT_OFFSET ) { 1006 /* Check whether first buffer in the path is the root of the tree. */
991 /* Check whether first buffer in the path is the root of the tree. */ 1007 if (PATH_OFFSET_PBUFFER
992 if ( PATH_OFFSET_PBUFFER(p_s_tb->tb_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr == 1008 (p_s_tb->tb_path,
993 SB_ROOT_BLOCK (p_s_tb->tb_sb) ) { 1009 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
994 *pp_s_father = *pp_s_com_father = NULL; 1010 SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
995 return CARRY_ON; 1011 *pp_s_father = *pp_s_com_father = NULL;
1012 return CARRY_ON;
1013 }
1014 return REPEAT_SEARCH;
996 } 1015 }
997 return REPEAT_SEARCH;
998 }
999 1016
1000 RFALSE( B_LEVEL (*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL, 1017 RFALSE(B_LEVEL(*pp_s_com_father) <= DISK_LEAF_NODE_LEVEL,
1001 "PAP-8185: (%b %z) level too small", 1018 "PAP-8185: (%b %z) level too small",
1002 *pp_s_com_father, *pp_s_com_father); 1019 *pp_s_com_father, *pp_s_com_father);
1003 1020
1004 /* Check whether the common parent is locked. */ 1021 /* Check whether the common parent is locked. */
1005 1022
1006 if ( buffer_locked (*pp_s_com_father) ) { 1023 if (buffer_locked(*pp_s_com_father)) {
1007 __wait_on_buffer(*pp_s_com_father); 1024 __wait_on_buffer(*pp_s_com_father);
1008 if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) { 1025 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1009 decrement_bcount(*pp_s_com_father); 1026 decrement_bcount(*pp_s_com_father);
1010 return REPEAT_SEARCH; 1027 return REPEAT_SEARCH;
1028 }
1011 } 1029 }
1012 }
1013
1014 /* So, we got common parent of the current node and its left/right neighbor.
1015 Now we are geting the parent of the left/right neighbor. */
1016 1030
1017 /* Form key to get parent of the left/right neighbor. */ 1031 /* So, we got common parent of the current node and its left/right neighbor.
1018 le_key2cpu_key (&s_lr_father_key, B_N_PDELIM_KEY(*pp_s_com_father, ( c_lr_par == LEFT_PARENTS ) ? 1032 Now we are geting the parent of the left/right neighbor. */
1019 (p_s_tb->lkey[n_h - 1] = n_position - 1) : (p_s_tb->rkey[n_h - 1] = n_position)));
1020 1033
1034 /* Form key to get parent of the left/right neighbor. */
1035 le_key2cpu_key(&s_lr_father_key,
1036 B_N_PDELIM_KEY(*pp_s_com_father,
1037 (c_lr_par ==
1038 LEFT_PARENTS) ? (p_s_tb->lkey[n_h - 1] =
1039 n_position -
1040 1) : (p_s_tb->rkey[n_h -
1041 1] =
1042 n_position)));
1021 1043
1022 if ( c_lr_par == LEFT_PARENTS ) 1044 if (c_lr_par == LEFT_PARENTS)
1023 decrement_key(&s_lr_father_key); 1045 decrement_key(&s_lr_father_key);
1024 1046
1025 if (search_by_key(p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father, n_h + 1) == IO_ERROR) 1047 if (search_by_key
1026 // path is released 1048 (p_s_tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1027 return IO_ERROR; 1049 n_h + 1) == IO_ERROR)
1050 // path is released
1051 return IO_ERROR;
1028 1052
1029 if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) { 1053 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1030 decrement_counters_in_path(&s_path_to_neighbor_father); 1054 decrement_counters_in_path(&s_path_to_neighbor_father);
1031 decrement_bcount(*pp_s_com_father); 1055 decrement_bcount(*pp_s_com_father);
1032 return REPEAT_SEARCH; 1056 return REPEAT_SEARCH;
1033 } 1057 }
1034 1058
1035 *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father); 1059 *pp_s_father = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
1036 1060
1037 RFALSE( B_LEVEL (*pp_s_father) != n_h + 1, 1061 RFALSE(B_LEVEL(*pp_s_father) != n_h + 1,
1038 "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father); 1062 "PAP-8190: (%b %z) level too small", *pp_s_father, *pp_s_father);
1039 RFALSE( s_path_to_neighbor_father.path_length < FIRST_PATH_ELEMENT_OFFSET, 1063 RFALSE(s_path_to_neighbor_father.path_length <
1040 "PAP-8192: path length is too small"); 1064 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
1041 1065
1042 s_path_to_neighbor_father.path_length--; 1066 s_path_to_neighbor_father.path_length--;
1043 decrement_counters_in_path(&s_path_to_neighbor_father); 1067 decrement_counters_in_path(&s_path_to_neighbor_father);
1044 return CARRY_ON; 1068 return CARRY_ON;
1045} 1069}
1046 1070
1047
1048/* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of 1071/* Get parents of neighbors of node in the path(S[n_path_offset]) and common parents of
1049 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset], 1072 * S[n_path_offset] and L[n_path_offset]/R[n_path_offset]: F[n_path_offset], FL[n_path_offset],
1050 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset]. 1073 * FR[n_path_offset], CFL[n_path_offset], CFR[n_path_offset].
@@ -1052,122 +1075,127 @@ static int get_far_parent (struct tree_balance * p_s_tb,
1052 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 1075 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1053 * CARRY_ON - schedule didn't occur while the function worked; 1076 * CARRY_ON - schedule didn't occur while the function worked;
1054 */ 1077 */
1055static int get_parents (struct tree_balance * p_s_tb, int n_h) 1078static int get_parents(struct tree_balance *p_s_tb, int n_h)
1056{ 1079{
1057 struct path * p_s_path = p_s_tb->tb_path; 1080 struct path *p_s_path = p_s_tb->tb_path;
1058 int n_position, 1081 int n_position,
1059 n_ret_value, 1082 n_ret_value,
1060 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h); 1083 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1061 struct buffer_head * p_s_curf, 1084 struct buffer_head *p_s_curf, *p_s_curcf;
1062 * p_s_curcf; 1085
1063 1086 /* Current node is the root of the tree or will be root of the tree */
1064 /* Current node is the root of the tree or will be root of the tree */ 1087 if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1065 if ( n_path_offset <= FIRST_PATH_ELEMENT_OFFSET ) { 1088 /* The root can not have parents.
1066 /* The root can not have parents. 1089 Release nodes which previously were obtained as parents of the current node neighbors. */
1067 Release nodes which previously were obtained as parents of the current node neighbors. */ 1090 decrement_bcount(p_s_tb->FL[n_h]);
1091 decrement_bcount(p_s_tb->CFL[n_h]);
1092 decrement_bcount(p_s_tb->FR[n_h]);
1093 decrement_bcount(p_s_tb->CFR[n_h]);
1094 p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] =
1095 p_s_tb->CFR[n_h] = NULL;
1096 return CARRY_ON;
1097 }
1098
1099 /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1100 if ((n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1))) {
1101 /* Current node is not the first child of its parent. */
1102 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1103 p_s_curf = p_s_curcf =
1104 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1105 get_bh(p_s_curf);
1106 get_bh(p_s_curf);
1107 p_s_tb->lkey[n_h] = n_position - 1;
1108 } else {
1109 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1110 Calculate current common parent of L[n_path_offset] and the current node. Note that
1111 CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1112 Calculate lkey[n_path_offset]. */
1113 if ((n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
1114 &p_s_curcf,
1115 LEFT_PARENTS)) != CARRY_ON)
1116 return n_ret_value;
1117 }
1118
1068 decrement_bcount(p_s_tb->FL[n_h]); 1119 decrement_bcount(p_s_tb->FL[n_h]);
1120 p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
1069 decrement_bcount(p_s_tb->CFL[n_h]); 1121 decrement_bcount(p_s_tb->CFL[n_h]);
1070 decrement_bcount(p_s_tb->FR[n_h]); 1122 p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */
1071 decrement_bcount(p_s_tb->CFR[n_h]); 1123
1072 p_s_tb->FL[n_h] = p_s_tb->CFL[n_h] = p_s_tb->FR[n_h] = p_s_tb->CFR[n_h] = NULL; 1124 RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1073 return CARRY_ON; 1125 (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1074 } 1126 "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
1075
1076 /* Get parent FL[n_path_offset] of L[n_path_offset]. */
1077 if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1)) ) {
1078 /* Current node is not the first child of its parent. */
1079 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;*/
1080 p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1081 get_bh(p_s_curf) ;
1082 get_bh(p_s_curf) ;
1083 p_s_tb->lkey[n_h] = n_position - 1;
1084 }
1085 else {
1086 /* Calculate current parent of L[n_path_offset], which is the left neighbor of the current node.
1087 Calculate current common parent of L[n_path_offset] and the current node. Note that
1088 CFL[n_path_offset] not equal FL[n_path_offset] and CFL[n_path_offset] not equal F[n_path_offset].
1089 Calculate lkey[n_path_offset]. */
1090 if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf,
1091 &p_s_curcf, LEFT_PARENTS)) != CARRY_ON )
1092 return n_ret_value;
1093 }
1094
1095 decrement_bcount(p_s_tb->FL[n_h]);
1096 p_s_tb->FL[n_h] = p_s_curf; /* New initialization of FL[n_h]. */
1097 decrement_bcount(p_s_tb->CFL[n_h]);
1098 p_s_tb->CFL[n_h] = p_s_curcf; /* New initialization of CFL[n_h]. */
1099
1100 RFALSE( (p_s_curf && !B_IS_IN_TREE (p_s_curf)) ||
1101 (p_s_curcf && !B_IS_IN_TREE (p_s_curcf)),
1102 "PAP-8195: FL (%b) or CFL (%b) is invalid", p_s_curf, p_s_curcf);
1103 1127
1104/* Get parent FR[n_h] of R[n_h]. */ 1128/* Get parent FR[n_h] of R[n_h]. */
1105 1129
1106/* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */ 1130/* Current node is the last child of F[n_h]. FR[n_h] != F[n_h]. */
1107 if ( n_position == B_NR_ITEMS (PATH_H_PBUFFER(p_s_path, n_h + 1)) ) { 1131 if (n_position == B_NR_ITEMS(PATH_H_PBUFFER(p_s_path, n_h + 1))) {
1108/* Calculate current parent of R[n_h], which is the right neighbor of F[n_h]. 1132/* Calculate current parent of R[n_h], which is the right neighbor of F[n_h].
1109 Calculate current common parent of R[n_h] and current node. Note that CFR[n_h] 1133 Calculate current common parent of R[n_h] and current node. Note that CFR[n_h]
1110 not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */ 1134 not equal FR[n_path_offset] and CFR[n_h] not equal F[n_h]. */
1111 if ( (n_ret_value = get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf, RIGHT_PARENTS)) != CARRY_ON ) 1135 if ((n_ret_value =
1112 return n_ret_value; 1136 get_far_parent(p_s_tb, n_h + 1, &p_s_curf, &p_s_curcf,
1113 } 1137 RIGHT_PARENTS)) != CARRY_ON)
1114 else { 1138 return n_ret_value;
1139 } else {
1115/* Current node is not the last child of its parent F[n_h]. */ 1140/* Current node is not the last child of its parent F[n_h]. */
1116 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2;*/ 1141 /*(p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1))->b_count += 2; */
1117 p_s_curf = p_s_curcf = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1); 1142 p_s_curf = p_s_curcf =
1118 get_bh(p_s_curf) ; 1143 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1);
1119 get_bh(p_s_curf) ; 1144 get_bh(p_s_curf);
1120 p_s_tb->rkey[n_h] = n_position; 1145 get_bh(p_s_curf);
1121 } 1146 p_s_tb->rkey[n_h] = n_position;
1122 1147 }
1123 decrement_bcount(p_s_tb->FR[n_h]);
1124 p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
1125
1126 decrement_bcount(p_s_tb->CFR[n_h]);
1127 p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */
1128
1129 RFALSE( (p_s_curf && !B_IS_IN_TREE (p_s_curf)) ||
1130 (p_s_curcf && !B_IS_IN_TREE (p_s_curcf)),
1131 "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
1132
1133 return CARRY_ON;
1134}
1135 1148
1149 decrement_bcount(p_s_tb->FR[n_h]);
1150 p_s_tb->FR[n_h] = p_s_curf; /* New initialization of FR[n_path_offset]. */
1151
1152 decrement_bcount(p_s_tb->CFR[n_h]);
1153 p_s_tb->CFR[n_h] = p_s_curcf; /* New initialization of CFR[n_path_offset]. */
1154
1155 RFALSE((p_s_curf && !B_IS_IN_TREE(p_s_curf)) ||
1156 (p_s_curcf && !B_IS_IN_TREE(p_s_curcf)),
1157 "PAP-8205: FR (%b) or CFR (%b) is invalid", p_s_curf, p_s_curcf);
1158
1159 return CARRY_ON;
1160}
1136 1161
1137/* it is possible to remove node as result of shiftings to 1162/* it is possible to remove node as result of shiftings to
1138 neighbors even when we insert or paste item. */ 1163 neighbors even when we insert or paste item. */
1139static inline int can_node_be_removed (int mode, int lfree, int sfree, int rfree, struct tree_balance * tb, int h) 1164static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1165 struct tree_balance *tb, int h)
1140{ 1166{
1141 struct buffer_head * Sh = PATH_H_PBUFFER (tb->tb_path, h); 1167 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1142 int levbytes = tb->insert_size[h]; 1168 int levbytes = tb->insert_size[h];
1143 struct item_head * ih; 1169 struct item_head *ih;
1144 struct reiserfs_key * r_key = NULL; 1170 struct reiserfs_key *r_key = NULL;
1145 1171
1146 ih = B_N_PITEM_HEAD (Sh, 0); 1172 ih = B_N_PITEM_HEAD(Sh, 0);
1147 if ( tb->CFR[h] ) 1173 if (tb->CFR[h])
1148 r_key = B_N_PDELIM_KEY(tb->CFR[h],tb->rkey[h]); 1174 r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
1149 1175
1150 if ( 1176 if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
1151 lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes 1177 /* shifting may merge items which might save space */
1152 /* shifting may merge items which might save space */ 1178 -
1153 - (( ! h && op_is_left_mergeable (&(ih->ih_key), Sh->b_size) ) ? IH_SIZE : 0) 1179 ((!h
1154 - (( ! h && r_key && op_is_left_mergeable (r_key, Sh->b_size) ) ? IH_SIZE : 0) 1180 && op_is_left_mergeable(&(ih->ih_key), Sh->b_size)) ? IH_SIZE : 0)
1155 + (( h ) ? KEY_SIZE : 0)) 1181 -
1156 { 1182 ((!h && r_key
1157 /* node can not be removed */ 1183 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1158 if (sfree >= levbytes ) { /* new item fits into node S[h] without any shifting */ 1184 + ((h) ? KEY_SIZE : 0)) {
1159 if ( ! h ) 1185 /* node can not be removed */
1160 tb->s0num = B_NR_ITEMS(Sh) + ((mode == M_INSERT ) ? 1 : 0); 1186 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1161 set_parameters (tb, h, 0, 0, 1, NULL, -1, -1); 1187 if (!h)
1162 return NO_BALANCING_NEEDED; 1188 tb->s0num =
1189 B_NR_ITEMS(Sh) +
1190 ((mode == M_INSERT) ? 1 : 0);
1191 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1192 return NO_BALANCING_NEEDED;
1193 }
1163 } 1194 }
1164 } 1195 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1165 PROC_INFO_INC( tb -> tb_sb, can_node_be_removed[ h ] ); 1196 return !NO_BALANCING_NEEDED;
1166 return !NO_BALANCING_NEEDED;
1167} 1197}
1168 1198
1169
1170
1171/* Check whether current node S[h] is balanced when increasing its size by 1199/* Check whether current node S[h] is balanced when increasing its size by
1172 * Inserting or Pasting. 1200 * Inserting or Pasting.
1173 * Calculate parameters for balancing for current level h. 1201 * Calculate parameters for balancing for current level h.
@@ -1182,154 +1210,157 @@ static inline int can_node_be_removed (int mode, int lfree, int sfree, int rfree
1182 * -2 - no disk space. 1210 * -2 - no disk space.
1183 */ 1211 */
1184/* ip means Inserting or Pasting */ 1212/* ip means Inserting or Pasting */
1185static int ip_check_balance (struct tree_balance * tb, int h) 1213static int ip_check_balance(struct tree_balance *tb, int h)
1186{ 1214{
1187 struct virtual_node * vn = tb->tb_vn; 1215 struct virtual_node *vn = tb->tb_vn;
1188 int levbytes, /* Number of bytes that must be inserted into (value 1216 int levbytes, /* Number of bytes that must be inserted into (value
1189 is negative if bytes are deleted) buffer which 1217 is negative if bytes are deleted) buffer which
1190 contains node being balanced. The mnemonic is 1218 contains node being balanced. The mnemonic is
1191 that the attempted change in node space used level 1219 that the attempted change in node space used level
1192 is levbytes bytes. */ 1220 is levbytes bytes. */
1193 n_ret_value; 1221 n_ret_value;
1194 1222
1195 int lfree, sfree, rfree /* free space in L, S and R */; 1223 int lfree, sfree, rfree /* free space in L, S and R */ ;
1196 1224
1197 /* nver is short for number of vertixes, and lnver is the number if 1225 /* nver is short for number of vertixes, and lnver is the number if
1198 we shift to the left, rnver is the number if we shift to the 1226 we shift to the left, rnver is the number if we shift to the
1199 right, and lrnver is the number if we shift in both directions. 1227 right, and lrnver is the number if we shift in both directions.
1200 The goal is to minimize first the number of vertixes, and second, 1228 The goal is to minimize first the number of vertixes, and second,
1201 the number of vertixes whose contents are changed by shifting, 1229 the number of vertixes whose contents are changed by shifting,
1202 and third the number of uncached vertixes whose contents are 1230 and third the number of uncached vertixes whose contents are
1203 changed by shifting and must be read from disk. */ 1231 changed by shifting and must be read from disk. */
1204 int nver, lnver, rnver, lrnver; 1232 int nver, lnver, rnver, lrnver;
1205 1233
1206 /* used at leaf level only, S0 = S[0] is the node being balanced, 1234 /* used at leaf level only, S0 = S[0] is the node being balanced,
1207 sInum [ I = 0,1,2 ] is the number of items that will 1235 sInum [ I = 0,1,2 ] is the number of items that will
1208 remain in node SI after balancing. S1 and S2 are new 1236 remain in node SI after balancing. S1 and S2 are new
1209 nodes that might be created. */ 1237 nodes that might be created. */
1210 1238
1211 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters. 1239 /* we perform 8 calls to get_num_ver(). For each call we calculate five parameters.
1212 where 4th parameter is s1bytes and 5th - s2bytes 1240 where 4th parameter is s1bytes and 5th - s2bytes
1213 */ 1241 */
1214 short snum012[40] = {0,}; /* s0num, s1num, s2num for 8 cases 1242 short snum012[40] = { 0, }; /* s0num, s1num, s2num for 8 cases
1215 0,1 - do not shift and do not shift but bottle 1243 0,1 - do not shift and do not shift but bottle
1216 2 - shift only whole item to left 1244 2 - shift only whole item to left
1217 3 - shift to left and bottle as much as possible 1245 3 - shift to left and bottle as much as possible
1218 4,5 - shift to right (whole items and as much as possible 1246 4,5 - shift to right (whole items and as much as possible
1219 6,7 - shift to both directions (whole items and as much as possible) 1247 6,7 - shift to both directions (whole items and as much as possible)
1220 */ 1248 */
1221 1249
1222 /* Sh is the node whose balance is currently being checked */ 1250 /* Sh is the node whose balance is currently being checked */
1223 struct buffer_head * Sh; 1251 struct buffer_head *Sh;
1224 1252
1225 Sh = PATH_H_PBUFFER (tb->tb_path, h); 1253 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1226 levbytes = tb->insert_size[h]; 1254 levbytes = tb->insert_size[h];
1227 1255
1228 /* Calculate balance parameters for creating new root. */ 1256 /* Calculate balance parameters for creating new root. */
1229 if ( ! Sh ) { 1257 if (!Sh) {
1230 if ( ! h ) 1258 if (!h)
1231 reiserfs_panic (tb->tb_sb, "vs-8210: ip_check_balance: S[0] can not be 0"); 1259 reiserfs_panic(tb->tb_sb,
1232 switch ( n_ret_value = get_empty_nodes (tb, h) ) { 1260 "vs-8210: ip_check_balance: S[0] can not be 0");
1233 case CARRY_ON: 1261 switch (n_ret_value = get_empty_nodes(tb, h)) {
1234 set_parameters (tb, h, 0, 0, 1, NULL, -1, -1); 1262 case CARRY_ON:
1235 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */ 1263 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1236 1264 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1237 case NO_DISK_SPACE: 1265
1238 case REPEAT_SEARCH: 1266 case NO_DISK_SPACE:
1239 return n_ret_value; 1267 case REPEAT_SEARCH:
1240 default: 1268 return n_ret_value;
1241 reiserfs_panic(tb->tb_sb, "vs-8215: ip_check_balance: incorrect return value of get_empty_nodes"); 1269 default:
1270 reiserfs_panic(tb->tb_sb,
1271 "vs-8215: ip_check_balance: incorrect return value of get_empty_nodes");
1272 }
1242 } 1273 }
1243 }
1244
1245 if ( (n_ret_value = get_parents (tb, h)) != CARRY_ON ) /* get parents of S[h] neighbors. */
1246 return n_ret_value;
1247
1248 sfree = B_FREE_SPACE (Sh);
1249
1250 /* get free space of neighbors */
1251 rfree = get_rfree (tb, h);
1252 lfree = get_lfree (tb, h);
1253
1254 if (can_node_be_removed (vn->vn_mode, lfree, sfree, rfree, tb, h) == NO_BALANCING_NEEDED)
1255 /* and new item fits into node S[h] without any shifting */
1256 return NO_BALANCING_NEEDED;
1257
1258 create_virtual_node (tb, h);
1259
1260 /*
1261 determine maximal number of items we can shift to the left neighbor (in tb structure)
1262 and the maximal number of bytes that can flow to the left neighbor
1263 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1264 */
1265 check_left (tb, h, lfree);
1266
1267 /*
1268 determine maximal number of items we can shift to the right neighbor (in tb structure)
1269 and the maximal number of bytes that can flow to the right neighbor
1270 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1271 */
1272 check_right (tb, h, rfree);
1273
1274
1275 /* all contents of internal node S[h] can be moved into its
1276 neighbors, S[h] will be removed after balancing */
1277 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1278 int to_r;
1279
1280 /* Since we are working on internal nodes, and our internal
1281 nodes have fixed size entries, then we can balance by the
1282 number of items rather than the space they consume. In this
1283 routine we set the left node equal to the right node,
1284 allowing a difference of less than or equal to 1 child
1285 pointer. */
1286 to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -
1287 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1288 set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
1289 return CARRY_ON;
1290 }
1291
1292 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1293 RFALSE( h &&
1294 ( tb->lnum[h] >= vn->vn_nr_item + 1 ||
1295 tb->rnum[h] >= vn->vn_nr_item + 1),
1296 "vs-8220: tree is not balanced on internal level");
1297 RFALSE( ! h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1298 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1)) ),
1299 "vs-8225: tree is not balanced on leaf level");
1300
1301 /* all contents of S[0] can be moved into its neighbors
1302 S[0] will be removed after balancing. */
1303 if (!h && is_leaf_removable (tb))
1304 return CARRY_ON;
1305 1274
1275 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON) /* get parents of S[h] neighbors. */
1276 return n_ret_value;
1306 1277
1307 /* why do we perform this check here rather than earlier?? 1278 sfree = B_FREE_SPACE(Sh);
1308 Answer: we can win 1 node in some cases above. Moreover we 1279
1309 checked it above, when we checked, that S[0] is not removable 1280 /* get free space of neighbors */
1310 in principle */ 1281 rfree = get_rfree(tb, h);
1311 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */ 1282 lfree = get_lfree(tb, h);
1312 if ( ! h ) 1283
1313 tb->s0num = vn->vn_nr_item; 1284 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1314 set_parameters (tb, h, 0, 0, 1, NULL, -1, -1); 1285 NO_BALANCING_NEEDED)
1315 return NO_BALANCING_NEEDED; 1286 /* and new item fits into node S[h] without any shifting */
1316 } 1287 return NO_BALANCING_NEEDED;
1317 1288
1289 create_virtual_node(tb, h);
1318 1290
1319 { 1291 /*
1320 int lpar, rpar, nset, lset, rset, lrset; 1292 determine maximal number of items we can shift to the left neighbor (in tb structure)
1321 /* 1293 and the maximal number of bytes that can flow to the left neighbor
1322 * regular overflowing of the node 1294 from the left most liquid item that cannot be shifted from S[0] entirely (returned value)
1323 */ 1295 */
1296 check_left(tb, h, lfree);
1324 1297
1325 /* get_num_ver works in 2 modes (FLOW & NO_FLOW) 1298 /*
1326 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item) 1299 determine maximal number of items we can shift to the right neighbor (in tb structure)
1327 nset, lset, rset, lrset - shows, whether flowing items give better packing 1300 and the maximal number of bytes that can flow to the right neighbor
1328 */ 1301 from the right most liquid item that cannot be shifted from S[0] entirely (returned value)
1302 */
1303 check_right(tb, h, rfree);
1304
1305 /* all contents of internal node S[h] can be moved into its
1306 neighbors, S[h] will be removed after balancing */
1307 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1308 int to_r;
1309
1310 /* Since we are working on internal nodes, and our internal
1311 nodes have fixed size entries, then we can balance by the
1312 number of items rather than the space they consume. In this
1313 routine we set the left node equal to the right node,
1314 allowing a difference of less than or equal to 1 child
1315 pointer. */
1316 to_r =
1317 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1318 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1319 tb->rnum[h]);
1320 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1321 -1, -1);
1322 return CARRY_ON;
1323 }
1324
1325 /* this checks balance condition, that any two neighboring nodes can not fit in one node */
1326 RFALSE(h &&
1327 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1328 tb->rnum[h] >= vn->vn_nr_item + 1),
1329 "vs-8220: tree is not balanced on internal level");
1330 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1331 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1332 "vs-8225: tree is not balanced on leaf level");
1333
1334 /* all contents of S[0] can be moved into its neighbors
1335 S[0] will be removed after balancing. */
1336 if (!h && is_leaf_removable(tb))
1337 return CARRY_ON;
1338
1339 /* why do we perform this check here rather than earlier??
1340 Answer: we can win 1 node in some cases above. Moreover we
1341 checked it above, when we checked, that S[0] is not removable
1342 in principle */
1343 if (sfree >= levbytes) { /* new item fits into node S[h] without any shifting */
1344 if (!h)
1345 tb->s0num = vn->vn_nr_item;
1346 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1347 return NO_BALANCING_NEEDED;
1348 }
1349
1350 {
1351 int lpar, rpar, nset, lset, rset, lrset;
1352 /*
1353 * regular overflowing of the node
1354 */
1355
1356 /* get_num_ver works in 2 modes (FLOW & NO_FLOW)
1357 lpar, rpar - number of items we can shift to left/right neighbor (including splitting item)
1358 nset, lset, rset, lrset - shows, whether flowing items give better packing
1359 */
1329#define FLOW 1 1360#define FLOW 1
1330#define NO_FLOW 0 /* do not any splitting */ 1361#define NO_FLOW 0 /* do not any splitting */
1331 1362
1332 /* we choose one the following */ 1363 /* we choose one the following */
1333#define NOTHING_SHIFT_NO_FLOW 0 1364#define NOTHING_SHIFT_NO_FLOW 0
1334#define NOTHING_SHIFT_FLOW 5 1365#define NOTHING_SHIFT_FLOW 5
1335#define LEFT_SHIFT_NO_FLOW 10 1366#define LEFT_SHIFT_NO_FLOW 10
@@ -1339,164 +1370,173 @@ static int ip_check_balance (struct tree_balance * tb, int h)
1339#define LR_SHIFT_NO_FLOW 30 1370#define LR_SHIFT_NO_FLOW 30
1340#define LR_SHIFT_FLOW 35 1371#define LR_SHIFT_FLOW 35
1341 1372
1373 lpar = tb->lnum[h];
1374 rpar = tb->rnum[h];
1375
1376 /* calculate number of blocks S[h] must be split into when
1377 nothing is shifted to the neighbors,
1378 as well as number of items in each part of the split node (s012 numbers),
1379 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */
1380 nset = NOTHING_SHIFT_NO_FLOW;
1381 nver = get_num_ver(vn->vn_mode, tb, h,
1382 0, -1, h ? vn->vn_nr_item : 0, -1,
1383 snum012, NO_FLOW);
1384
1385 if (!h) {
1386 int nver1;
1387
1388 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */
1389 nver1 = get_num_ver(vn->vn_mode, tb, h,
1390 0, -1, 0, -1,
1391 snum012 + NOTHING_SHIFT_FLOW, FLOW);
1392 if (nver > nver1)
1393 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1394 }
1342 1395
1343 lpar = tb->lnum[h]; 1396 /* calculate number of blocks S[h] must be split into when
1344 rpar = tb->rnum[h]; 1397 l_shift_num first items and l_shift_bytes of the right most
1345 1398 liquid item to be shifted are shifted to the left neighbor,
1346 1399 as well as number of items in each part of the splitted node (s012 numbers),
1347 /* calculate number of blocks S[h] must be split into when 1400 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1348 nothing is shifted to the neighbors, 1401 */
1349 as well as number of items in each part of the split node (s012 numbers), 1402 lset = LEFT_SHIFT_NO_FLOW;
1350 and number of bytes (s1bytes) of the shared drop which flow to S1 if any */ 1403 lnver = get_num_ver(vn->vn_mode, tb, h,
1351 nset = NOTHING_SHIFT_NO_FLOW; 1404 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1352 nver = get_num_ver (vn->vn_mode, tb, h, 1405 -1, h ? vn->vn_nr_item : 0, -1,
1353 0, -1, h?vn->vn_nr_item:0, -1, 1406 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1354 snum012, NO_FLOW); 1407 if (!h) {
1355 1408 int lnver1;
1356 if (!h) 1409
1357 { 1410 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1358 int nver1; 1411 lpar -
1359 1412 ((tb->lbytes != -1) ? 1 : 0),
1360 /* note, that in this case we try to bottle between S[0] and S1 (S1 - the first new node) */ 1413 tb->lbytes, 0, -1,
1361 nver1 = get_num_ver (vn->vn_mode, tb, h, 1414 snum012 + LEFT_SHIFT_FLOW, FLOW);
1362 0, -1, 0, -1, 1415 if (lnver > lnver1)
1363 snum012 + NOTHING_SHIFT_FLOW, FLOW); 1416 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1364 if (nver > nver1) 1417 }
1365 nset = NOTHING_SHIFT_FLOW, nver = nver1;
1366 }
1367
1368
1369 /* calculate number of blocks S[h] must be split into when
1370 l_shift_num first items and l_shift_bytes of the right most
1371 liquid item to be shifted are shifted to the left neighbor,
1372 as well as number of items in each part of the splitted node (s012 numbers),
1373 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1374 */
1375 lset = LEFT_SHIFT_NO_FLOW;
1376 lnver = get_num_ver (vn->vn_mode, tb, h,
1377 lpar - (( h || tb->lbytes == -1 ) ? 0 : 1), -1, h ? vn->vn_nr_item:0, -1,
1378 snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1379 if (!h)
1380 {
1381 int lnver1;
1382
1383 lnver1 = get_num_ver (vn->vn_mode, tb, h,
1384 lpar - ((tb->lbytes != -1) ? 1 : 0), tb->lbytes, 0, -1,
1385 snum012 + LEFT_SHIFT_FLOW, FLOW);
1386 if (lnver > lnver1)
1387 lset = LEFT_SHIFT_FLOW, lnver = lnver1;
1388 }
1389
1390
1391 /* calculate number of blocks S[h] must be split into when
1392 r_shift_num first items and r_shift_bytes of the left most
1393 liquid item to be shifted are shifted to the right neighbor,
1394 as well as number of items in each part of the splitted node (s012 numbers),
1395 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1396 */
1397 rset = RIGHT_SHIFT_NO_FLOW;
1398 rnver = get_num_ver (vn->vn_mode, tb, h,
1399 0, -1, h ? (vn->vn_nr_item-rpar) : (rpar - (( tb->rbytes != -1 ) ? 1 : 0)), -1,
1400 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1401 if (!h)
1402 {
1403 int rnver1;
1404
1405 rnver1 = get_num_ver (vn->vn_mode, tb, h,
1406 0, -1, (rpar - ((tb->rbytes != -1) ? 1 : 0)), tb->rbytes,
1407 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1408
1409 if (rnver > rnver1)
1410 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1411 }
1412
1413
1414 /* calculate number of blocks S[h] must be split into when
1415 items are shifted in both directions,
1416 as well as number of items in each part of the splitted node (s012 numbers),
1417 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1418 */
1419 lrset = LR_SHIFT_NO_FLOW;
1420 lrnver = get_num_ver (vn->vn_mode, tb, h,
1421 lpar - ((h || tb->lbytes == -1) ? 0 : 1), -1, h ? (vn->vn_nr_item-rpar):(rpar - ((tb->rbytes != -1) ? 1 : 0)), -1,
1422 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1423 if (!h)
1424 {
1425 int lrnver1;
1426
1427 lrnver1 = get_num_ver (vn->vn_mode, tb, h,
1428 lpar - ((tb->lbytes != -1) ? 1 : 0), tb->lbytes, (rpar - ((tb->rbytes != -1) ? 1 : 0)), tb->rbytes,
1429 snum012 + LR_SHIFT_FLOW, FLOW);
1430 if (lrnver > lrnver1)
1431 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1432 }
1433
1434
1435 1418
1436 /* Our general shifting strategy is: 1419 /* calculate number of blocks S[h] must be split into when
1437 1) to minimized number of new nodes; 1420 r_shift_num first items and r_shift_bytes of the left most
1438 2) to minimized number of neighbors involved in shifting; 1421 liquid item to be shifted are shifted to the right neighbor,
1439 3) to minimized number of disk reads; */ 1422 as well as number of items in each part of the splitted node (s012 numbers),
1423 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1424 */
1425 rset = RIGHT_SHIFT_NO_FLOW;
1426 rnver = get_num_ver(vn->vn_mode, tb, h,
1427 0, -1,
1428 h ? (vn->vn_nr_item - rpar) : (rpar -
1429 ((tb->
1430 rbytes !=
1431 -1) ? 1 :
1432 0)), -1,
1433 snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1434 if (!h) {
1435 int rnver1;
1436
1437 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1438 0, -1,
1439 (rpar -
1440 ((tb->rbytes != -1) ? 1 : 0)),
1441 tb->rbytes,
1442 snum012 + RIGHT_SHIFT_FLOW, FLOW);
1443
1444 if (rnver > rnver1)
1445 rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
1446 }
1440 1447
1441 /* we can win TWO or ONE nodes by shifting in both directions */ 1448 /* calculate number of blocks S[h] must be split into when
1442 if (lrnver < lnver && lrnver < rnver) 1449 items are shifted in both directions,
1443 { 1450 as well as number of items in each part of the splitted node (s012 numbers),
1444 RFALSE( h && 1451 and number of bytes (s1bytes) of the shared drop which flow to S1 if any
1445 (tb->lnum[h] != 1 || 1452 */
1446 tb->rnum[h] != 1 || 1453 lrset = LR_SHIFT_NO_FLOW;
1447 lrnver != 1 || rnver != 2 || lnver != 2 || h != 1), 1454 lrnver = get_num_ver(vn->vn_mode, tb, h,
1448 "vs-8230: bad h"); 1455 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1449 if (lrset == LR_SHIFT_FLOW) 1456 -1,
1450 set_parameters (tb, h, tb->lnum[h], tb->rnum[h], lrnver, snum012 + lrset, 1457 h ? (vn->vn_nr_item - rpar) : (rpar -
1451 tb->lbytes, tb->rbytes); 1458 ((tb->
1452 else 1459 rbytes !=
1453 set_parameters (tb, h, tb->lnum[h] - ((tb->lbytes == -1) ? 0 : 1), 1460 -1) ? 1 :
1454 tb->rnum[h] - ((tb->rbytes == -1) ? 0 : 1), lrnver, snum012 + lrset, -1, -1); 1461 0)), -1,
1455 1462 snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1456 return CARRY_ON; 1463 if (!h) {
1457 } 1464 int lrnver1;
1465
1466 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1467 lpar -
1468 ((tb->lbytes != -1) ? 1 : 0),
1469 tb->lbytes,
1470 (rpar -
1471 ((tb->rbytes != -1) ? 1 : 0)),
1472 tb->rbytes,
1473 snum012 + LR_SHIFT_FLOW, FLOW);
1474 if (lrnver > lrnver1)
1475 lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
1476 }
1458 1477
1459 /* if shifting doesn't lead to better packing then don't shift */ 1478 /* Our general shifting strategy is:
1460 if (nver == lrnver) 1479 1) to minimized number of new nodes;
1461 { 1480 2) to minimized number of neighbors involved in shifting;
1462 set_parameters (tb, h, 0, 0, nver, snum012 + nset, -1, -1); 1481 3) to minimized number of disk reads; */
1463 return CARRY_ON; 1482
1464 } 1483 /* we can win TWO or ONE nodes by shifting in both directions */
1484 if (lrnver < lnver && lrnver < rnver) {
1485 RFALSE(h &&
1486 (tb->lnum[h] != 1 ||
1487 tb->rnum[h] != 1 ||
1488 lrnver != 1 || rnver != 2 || lnver != 2
1489 || h != 1), "vs-8230: bad h");
1490 if (lrset == LR_SHIFT_FLOW)
1491 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1492 lrnver, snum012 + lrset,
1493 tb->lbytes, tb->rbytes);
1494 else
1495 set_parameters(tb, h,
1496 tb->lnum[h] -
1497 ((tb->lbytes == -1) ? 0 : 1),
1498 tb->rnum[h] -
1499 ((tb->rbytes == -1) ? 0 : 1),
1500 lrnver, snum012 + lrset, -1, -1);
1501
1502 return CARRY_ON;
1503 }
1465 1504
1505 /* if shifting doesn't lead to better packing then don't shift */
1506 if (nver == lrnver) {
1507 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1508 -1);
1509 return CARRY_ON;
1510 }
1466 1511
1467 /* now we know that for better packing shifting in only one 1512 /* now we know that for better packing shifting in only one
1468 direction either to the left or to the right is required */ 1513 direction either to the left or to the right is required */
1469 1514
1470 /* if shifting to the left is better than shifting to the right */ 1515 /* if shifting to the left is better than shifting to the right */
1471 if (lnver < rnver) 1516 if (lnver < rnver) {
1472 { 1517 SET_PAR_SHIFT_LEFT;
1473 SET_PAR_SHIFT_LEFT; 1518 return CARRY_ON;
1474 return CARRY_ON; 1519 }
1475 }
1476 1520
1477 /* if shifting to the right is better than shifting to the left */ 1521 /* if shifting to the right is better than shifting to the left */
1478 if (lnver > rnver) 1522 if (lnver > rnver) {
1479 { 1523 SET_PAR_SHIFT_RIGHT;
1480 SET_PAR_SHIFT_RIGHT; 1524 return CARRY_ON;
1481 return CARRY_ON; 1525 }
1482 }
1483 1526
1527 /* now shifting in either direction gives the same number
1528 of nodes and we can make use of the cached neighbors */
1529 if (is_left_neighbor_in_cache(tb, h)) {
1530 SET_PAR_SHIFT_LEFT;
1531 return CARRY_ON;
1532 }
1484 1533
1485 /* now shifting in either direction gives the same number 1534 /* shift to the right independently on whether the right neighbor in cache or not */
1486 of nodes and we can make use of the cached neighbors */ 1535 SET_PAR_SHIFT_RIGHT;
1487 if (is_left_neighbor_in_cache (tb,h)) 1536 return CARRY_ON;
1488 {
1489 SET_PAR_SHIFT_LEFT;
1490 return CARRY_ON;
1491 } 1537 }
1492
1493 /* shift to the right independently on whether the right neighbor in cache or not */
1494 SET_PAR_SHIFT_RIGHT;
1495 return CARRY_ON;
1496 }
1497} 1538}
1498 1539
1499
1500/* Check whether current node S[h] is balanced when Decreasing its size by 1540/* Check whether current node S[h] is balanced when Decreasing its size by
1501 * Deleting or Cutting for INTERNAL node of S+tree. 1541 * Deleting or Cutting for INTERNAL node of S+tree.
1502 * Calculate parameters for balancing for current level h. 1542 * Calculate parameters for balancing for current level h.
@@ -1513,157 +1553,173 @@ static int ip_check_balance (struct tree_balance * tb, int h)
1513 * Note: Items of internal nodes have fixed size, so the balance condition for 1553 * Note: Items of internal nodes have fixed size, so the balance condition for
1514 * the internal part of S+tree is as for the B-trees. 1554 * the internal part of S+tree is as for the B-trees.
1515 */ 1555 */
1516static int dc_check_balance_internal (struct tree_balance * tb, int h) 1556static int dc_check_balance_internal(struct tree_balance *tb, int h)
1517{ 1557{
1518 struct virtual_node * vn = tb->tb_vn; 1558 struct virtual_node *vn = tb->tb_vn;
1519 1559
1520 /* Sh is the node whose balance is currently being checked, 1560 /* Sh is the node whose balance is currently being checked,
1521 and Fh is its father. */ 1561 and Fh is its father. */
1522 struct buffer_head * Sh, * Fh; 1562 struct buffer_head *Sh, *Fh;
1523 int maxsize, 1563 int maxsize, n_ret_value;
1524 n_ret_value; 1564 int lfree, rfree /* free space in L and R */ ;
1525 int lfree, rfree /* free space in L and R */;
1526 1565
1527 Sh = PATH_H_PBUFFER (tb->tb_path, h); 1566 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1528 Fh = PATH_H_PPARENT (tb->tb_path, h); 1567 Fh = PATH_H_PPARENT(tb->tb_path, h);
1529 1568
1530 maxsize = MAX_CHILD_SIZE(Sh); 1569 maxsize = MAX_CHILD_SIZE(Sh);
1531 1570
1532/* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */ 1571/* using tb->insert_size[h], which is negative in this case, create_virtual_node calculates: */
1533/* new_nr_item = number of items node would have if operation is */ 1572/* new_nr_item = number of items node would have if operation is */
1534/* performed without balancing (new_nr_item); */ 1573/* performed without balancing (new_nr_item); */
1535 create_virtual_node (tb, h); 1574 create_virtual_node(tb, h);
1536 1575
1537 if ( ! Fh ) 1576 if (!Fh) { /* S[h] is the root. */
1538 { /* S[h] is the root. */ 1577 if (vn->vn_nr_item > 0) {
1539 if ( vn->vn_nr_item > 0 ) 1578 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1540 { 1579 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */
1541 set_parameters (tb, h, 0, 0, 1, NULL, -1, -1); 1580 }
1542 return NO_BALANCING_NEEDED; /* no balancing for higher levels needed */ 1581 /* new_nr_item == 0.
1582 * Current root will be deleted resulting in
1583 * decrementing the tree height. */
1584 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1585 return CARRY_ON;
1586 }
1587
1588 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1589 return n_ret_value;
1590
1591 /* get free space of neighbors */
1592 rfree = get_rfree(tb, h);
1593 lfree = get_lfree(tb, h);
1594
1595 /* determine maximal number of items we can fit into neighbors */
1596 check_left(tb, h, lfree);
1597 check_right(tb, h, rfree);
1598
1599 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { /* Balance condition for the internal node is valid.
1600 * In this case we balance only if it leads to better packing. */
1601 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { /* Here we join S[h] with one of its neighbors,
1602 * which is impossible with greater values of new_nr_item. */
1603 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1604 /* All contents of S[h] can be moved to L[h]. */
1605 int n;
1606 int order_L;
1607
1608 order_L =
1609 ((n =
1610 PATH_H_B_ITEM_ORDER(tb->tb_path,
1611 h)) ==
1612 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1613 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1614 (DC_SIZE + KEY_SIZE);
1615 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1616 -1);
1617 return CARRY_ON;
1618 }
1619
1620 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1621 /* All contents of S[h] can be moved to R[h]. */
1622 int n;
1623 int order_R;
1624
1625 order_R =
1626 ((n =
1627 PATH_H_B_ITEM_ORDER(tb->tb_path,
1628 h)) ==
1629 B_NR_ITEMS(Fh)) ? 0 : n + 1;
1630 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1631 (DC_SIZE + KEY_SIZE);
1632 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1633 -1);
1634 return CARRY_ON;
1635 }
1636 }
1637
1638 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1639 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1640 int to_r;
1641
1642 to_r =
1643 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1644 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1645 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1646 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1647 0, NULL, -1, -1);
1648 return CARRY_ON;
1649 }
1650
1651 /* Balancing does not lead to better packing. */
1652 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1653 return NO_BALANCING_NEEDED;
1543 } 1654 }
1544 /* new_nr_item == 0. 1655
1545 * Current root will be deleted resulting in 1656 /* Current node contain insufficient number of items. Balancing is required. */
1546 * decrementing the tree height. */ 1657 /* Check whether we can merge S[h] with left neighbor. */
1547 set_parameters (tb, h, 0, 0, 0, NULL, -1, -1); 1658 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1548 return CARRY_ON; 1659 if (is_left_neighbor_in_cache(tb, h)
1549 } 1660 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1550 1661 int n;
1551 if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON ) 1662 int order_L;
1552 return n_ret_value; 1663
1553 1664 order_L =
1554 1665 ((n =
1555 /* get free space of neighbors */ 1666 PATH_H_B_ITEM_ORDER(tb->tb_path,
1556 rfree = get_rfree (tb, h); 1667 h)) ==
1557 lfree = get_lfree (tb, h); 1668 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1558 1669 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1559 /* determine maximal number of items we can fit into neighbors */ 1670 KEY_SIZE);
1560 check_left (tb, h, lfree); 1671 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1561 check_right (tb, h, rfree); 1672 return CARRY_ON;
1562 1673 }
1563 1674
1564 if ( vn->vn_nr_item >= MIN_NR_KEY(Sh) ) 1675 /* Check whether we can merge S[h] with right neighbor. */
1565 { /* Balance condition for the internal node is valid. 1676 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1566 * In this case we balance only if it leads to better packing. */ 1677 int n;
1567 if ( vn->vn_nr_item == MIN_NR_KEY(Sh) ) 1678 int order_R;
1568 { /* Here we join S[h] with one of its neighbors, 1679
1569 * which is impossible with greater values of new_nr_item. */ 1680 order_R =
1570 if ( tb->lnum[h] >= vn->vn_nr_item + 1 ) 1681 ((n =
1571 { 1682 PATH_H_B_ITEM_ORDER(tb->tb_path,
1572 /* All contents of S[h] can be moved to L[h]. */ 1683 h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1573 int n; 1684 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1574 int order_L; 1685 KEY_SIZE);
1575 1686 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1576 order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; 1687 return CARRY_ON;
1577 n = dc_size(B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);
1578 set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);
1579 return CARRY_ON;
1580 }
1581
1582 if ( tb->rnum[h] >= vn->vn_nr_item + 1 )
1583 {
1584 /* All contents of S[h] can be moved to R[h]. */
1585 int n;
1586 int order_R;
1587
1588 order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : n + 1;
1589 n = dc_size(B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);
1590 set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);
1591 return CARRY_ON;
1592 }
1593 } 1688 }
1594 1689
1595 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) 1690 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1596 { 1691 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1597 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */ 1692 int to_r;
1598 int to_r; 1693
1694 to_r =
1695 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1696 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1697 tb->rnum[h]);
1698 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1699 -1, -1);
1700 return CARRY_ON;
1701 }
1599 1702
1600 to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 - 1703 /* For internal nodes try to borrow item from a neighbor */
1601 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]); 1704 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1602 set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1); 1705
1603 return CARRY_ON; 1706 /* Borrow one or two items from caching neighbor */
1707 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1708 int from_l;
1709
1710 from_l =
1711 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1712 1) / 2 - (vn->vn_nr_item + 1);
1713 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1714 return CARRY_ON;
1604 } 1715 }
1605 1716
1606 /* Balancing does not lead to better packing. */ 1717 set_parameters(tb, h, 0,
1607 set_parameters (tb, h, 0, 0, 1, NULL, -1, -1); 1718 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1608 return NO_BALANCING_NEEDED; 1719 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
1609 }
1610
1611 /* Current node contain insufficient number of items. Balancing is required. */
1612 /* Check whether we can merge S[h] with left neighbor. */
1613 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1614 if (is_left_neighbor_in_cache (tb,h) || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h])
1615 {
1616 int n;
1617 int order_L;
1618
1619 order_L = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1620 n = dc_size(B_N_CHILD(tb->FL[h],order_L)) / (DC_SIZE + KEY_SIZE);
1621 set_parameters (tb, h, -n-1, 0, 0, NULL, -1, -1);
1622 return CARRY_ON; 1720 return CARRY_ON;
1623 }
1624
1625 /* Check whether we can merge S[h] with right neighbor. */
1626 if (tb->rnum[h] >= vn->vn_nr_item + 1)
1627 {
1628 int n;
1629 int order_R;
1630
1631 order_R = ((n=PATH_H_B_ITEM_ORDER(tb->tb_path, h))==B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1632 n = dc_size(B_N_CHILD(tb->FR[h],order_R)) / (DC_SIZE + KEY_SIZE);
1633 set_parameters (tb, h, 0, -n-1, 0, NULL, -1, -1);
1634 return CARRY_ON;
1635 }
1636
1637 /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1638 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)
1639 {
1640 int to_r;
1641
1642 to_r = ((MAX_NR_KEY(Sh)<<1)+2-tb->lnum[h]-tb->rnum[h]+vn->vn_nr_item+1)/2 -
1643 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1644 set_parameters (tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, -1, -1);
1645 return CARRY_ON;
1646 }
1647
1648 /* For internal nodes try to borrow item from a neighbor */
1649 RFALSE( !tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1650
1651 /* Borrow one or two items from caching neighbor */
1652 if (is_left_neighbor_in_cache (tb,h) || !tb->FR[h])
1653 {
1654 int from_l;
1655
1656 from_l = (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + 1) / 2 - (vn->vn_nr_item + 1);
1657 set_parameters (tb, h, -from_l, 0, 1, NULL, -1, -1);
1658 return CARRY_ON;
1659 }
1660
1661 set_parameters (tb, h, 0, -((MAX_NR_KEY(Sh)+1-tb->rnum[h]+vn->vn_nr_item+1)/2-(vn->vn_nr_item+1)), 1,
1662 NULL, -1, -1);
1663 return CARRY_ON;
1664} 1721}
1665 1722
1666
1667/* Check whether current node S[h] is balanced when Decreasing its size by 1723/* Check whether current node S[h] is balanced when Decreasing its size by
1668 * Deleting or Truncating for LEAF node of S+tree. 1724 * Deleting or Truncating for LEAF node of S+tree.
1669 * Calculate parameters for balancing for current level h. 1725 * Calculate parameters for balancing for current level h.
@@ -1677,90 +1733,86 @@ static int dc_check_balance_internal (struct tree_balance * tb, int h)
1677 * -1 - no balancing for higher levels needed; 1733 * -1 - no balancing for higher levels needed;
1678 * -2 - no disk space. 1734 * -2 - no disk space.
1679 */ 1735 */
1680static int dc_check_balance_leaf (struct tree_balance * tb, int h) 1736static int dc_check_balance_leaf(struct tree_balance *tb, int h)
1681{ 1737{
1682 struct virtual_node * vn = tb->tb_vn; 1738 struct virtual_node *vn = tb->tb_vn;
1683 1739
1684 /* Number of bytes that must be deleted from 1740 /* Number of bytes that must be deleted from
1685 (value is negative if bytes are deleted) buffer which 1741 (value is negative if bytes are deleted) buffer which
1686 contains node being balanced. The mnemonic is that the 1742 contains node being balanced. The mnemonic is that the
1687 attempted change in node space used level is levbytes bytes. */ 1743 attempted change in node space used level is levbytes bytes. */
1688 int levbytes; 1744 int levbytes;
1689 /* the maximal item size */ 1745 /* the maximal item size */
1690 int maxsize, 1746 int maxsize, n_ret_value;
1691 n_ret_value; 1747 /* S0 is the node whose balance is currently being checked,
1692 /* S0 is the node whose balance is currently being checked, 1748 and F0 is its father. */
1693 and F0 is its father. */ 1749 struct buffer_head *S0, *F0;
1694 struct buffer_head * S0, * F0; 1750 int lfree, rfree /* free space in L and R */ ;
1695 int lfree, rfree /* free space in L and R */; 1751
1696 1752 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1697 S0 = PATH_H_PBUFFER (tb->tb_path, 0); 1753 F0 = PATH_H_PPARENT(tb->tb_path, 0);
1698 F0 = PATH_H_PPARENT (tb->tb_path, 0);
1699
1700 levbytes = tb->insert_size[h];
1701
1702 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
1703
1704 if ( ! F0 )
1705 { /* S[0] is the root now. */
1706
1707 RFALSE( -levbytes >= maxsize - B_FREE_SPACE (S0),
1708 "vs-8240: attempt to create empty buffer tree");
1709
1710 set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
1711 return NO_BALANCING_NEEDED;
1712 }
1713
1714 if ( (n_ret_value = get_parents(tb,h)) != CARRY_ON )
1715 return n_ret_value;
1716
1717 /* get free space of neighbors */
1718 rfree = get_rfree (tb, h);
1719 lfree = get_lfree (tb, h);
1720
1721 create_virtual_node (tb, h);
1722
1723 /* if 3 leaves can be merge to one, set parameters and return */
1724 if (are_leaves_removable (tb, lfree, rfree))
1725 return CARRY_ON;
1726
1727 /* determine maximal number of items we can shift to the left/right neighbor
1728 and the maximal number of bytes that can flow to the left/right neighbor
1729 from the left/right most liquid item that cannot be shifted from S[0] entirely
1730 */
1731 check_left (tb, h, lfree);
1732 check_right (tb, h, rfree);
1733
1734 /* check whether we can merge S with left neighbor. */
1735 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1736 if (is_left_neighbor_in_cache (tb,h) ||
1737 ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) || /* S can not be merged with R */
1738 !tb->FR[h]) {
1739
1740 RFALSE( !tb->FL[h], "vs-8245: dc_check_balance_leaf: FL[h] must exist");
1741
1742 /* set parameter to merge S[0] with its left neighbor */
1743 set_parameters (tb, h, -1, 0, 0, NULL, -1, -1);
1744 return CARRY_ON;
1745 }
1746
1747 /* check whether we can merge S[0] with right neighbor. */
1748 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1749 set_parameters (tb, h, 0, -1, 0, NULL, -1, -1);
1750 return CARRY_ON;
1751 }
1752
1753 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1754 if (is_leaf_removable (tb))
1755 return CARRY_ON;
1756
1757 /* Balancing is not required. */
1758 tb->s0num = vn->vn_nr_item;
1759 set_parameters (tb, h, 0, 0, 1, NULL, -1, -1);
1760 return NO_BALANCING_NEEDED;
1761}
1762 1754
1755 levbytes = tb->insert_size[h];
1763 1756
1757 maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
1758
1759 if (!F0) { /* S[0] is the root now. */
1760
1761 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
1762 "vs-8240: attempt to create empty buffer tree");
1763
1764 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1765 return NO_BALANCING_NEEDED;
1766 }
1767
1768 if ((n_ret_value = get_parents(tb, h)) != CARRY_ON)
1769 return n_ret_value;
1770
1771 /* get free space of neighbors */
1772 rfree = get_rfree(tb, h);
1773 lfree = get_lfree(tb, h);
1774
1775 create_virtual_node(tb, h);
1776
1777 /* if 3 leaves can be merge to one, set parameters and return */
1778 if (are_leaves_removable(tb, lfree, rfree))
1779 return CARRY_ON;
1780
1781 /* determine maximal number of items we can shift to the left/right neighbor
1782 and the maximal number of bytes that can flow to the left/right neighbor
1783 from the left/right most liquid item that cannot be shifted from S[0] entirely
1784 */
1785 check_left(tb, h, lfree);
1786 check_right(tb, h, rfree);
1787
1788 /* check whether we can merge S with left neighbor. */
1789 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1790 if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) || /* S can not be merged with R */
1791 !tb->FR[h]) {
1792
1793 RFALSE(!tb->FL[h],
1794 "vs-8245: dc_check_balance_leaf: FL[h] must exist");
1795
1796 /* set parameter to merge S[0] with its left neighbor */
1797 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1798 return CARRY_ON;
1799 }
1800
1801 /* check whether we can merge S[0] with right neighbor. */
1802 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
1803 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
1804 return CARRY_ON;
1805 }
1806
1807 /* All contents of S[0] can be moved to the neighbors (L[0] & R[0]). Set parameters and return */
1808 if (is_leaf_removable(tb))
1809 return CARRY_ON;
1810
1811 /* Balancing is not required. */
1812 tb->s0num = vn->vn_nr_item;
1813 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1814 return NO_BALANCING_NEEDED;
1815}
1764 1816
1765/* Check whether current node S[h] is balanced when Decreasing its size by 1817/* Check whether current node S[h] is balanced when Decreasing its size by
1766 * Deleting or Cutting. 1818 * Deleting or Cutting.
@@ -1775,18 +1827,17 @@ static int dc_check_balance_leaf (struct tree_balance * tb, int h)
1775 * -1 - no balancing for higher levels needed; 1827 * -1 - no balancing for higher levels needed;
1776 * -2 - no disk space. 1828 * -2 - no disk space.
1777 */ 1829 */
1778static int dc_check_balance (struct tree_balance * tb, int h) 1830static int dc_check_balance(struct tree_balance *tb, int h)
1779{ 1831{
1780 RFALSE( ! (PATH_H_PBUFFER (tb->tb_path, h)), "vs-8250: S is not initialized"); 1832 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
1833 "vs-8250: S is not initialized");
1781 1834
1782 if ( h ) 1835 if (h)
1783 return dc_check_balance_internal (tb, h); 1836 return dc_check_balance_internal(tb, h);
1784 else 1837 else
1785 return dc_check_balance_leaf (tb, h); 1838 return dc_check_balance_leaf(tb, h);
1786} 1839}
1787 1840
1788
1789
1790/* Check whether current node S[h] is balanced. 1841/* Check whether current node S[h] is balanced.
1791 * Calculate parameters for balancing for current level h. 1842 * Calculate parameters for balancing for current level h.
1792 * Parameters: 1843 * Parameters:
@@ -1805,83 +1856,80 @@ static int dc_check_balance (struct tree_balance * tb, int h)
1805 * -1 - no balancing for higher levels needed; 1856 * -1 - no balancing for higher levels needed;
1806 * -2 - no disk space. 1857 * -2 - no disk space.
1807 */ 1858 */
1808static int check_balance (int mode, 1859static int check_balance(int mode,
1809 struct tree_balance * tb, 1860 struct tree_balance *tb,
1810 int h, 1861 int h,
1811 int inum, 1862 int inum,
1812 int pos_in_item, 1863 int pos_in_item,
1813 struct item_head * ins_ih, 1864 struct item_head *ins_ih, const void *data)
1814 const void * data
1815 )
1816{ 1865{
1817 struct virtual_node * vn; 1866 struct virtual_node *vn;
1818 1867
1819 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf); 1868 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
1820 vn->vn_free_ptr = (char *)(tb->tb_vn + 1); 1869 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
1821 vn->vn_mode = mode; 1870 vn->vn_mode = mode;
1822 vn->vn_affected_item_num = inum; 1871 vn->vn_affected_item_num = inum;
1823 vn->vn_pos_in_item = pos_in_item; 1872 vn->vn_pos_in_item = pos_in_item;
1824 vn->vn_ins_ih = ins_ih; 1873 vn->vn_ins_ih = ins_ih;
1825 vn->vn_data = data; 1874 vn->vn_data = data;
1826 1875
1827 RFALSE( mode == M_INSERT && !vn->vn_ins_ih, 1876 RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
1828 "vs-8255: ins_ih can not be 0 in insert mode"); 1877 "vs-8255: ins_ih can not be 0 in insert mode");
1829 1878
1830 if ( tb->insert_size[h] > 0 ) 1879 if (tb->insert_size[h] > 0)
1831 /* Calculate balance parameters when size of node is increasing. */ 1880 /* Calculate balance parameters when size of node is increasing. */
1832 return ip_check_balance (tb, h); 1881 return ip_check_balance(tb, h);
1833 1882
1834 /* Calculate balance parameters when size of node is decreasing. */ 1883 /* Calculate balance parameters when size of node is decreasing. */
1835 return dc_check_balance (tb, h); 1884 return dc_check_balance(tb, h);
1836} 1885}
1837 1886
1887/* Check whether parent at the path is the really parent of the current node.*/
1888static int get_direct_parent(struct tree_balance *p_s_tb, int n_h)
1889{
1890 struct buffer_head *p_s_bh;
1891 struct path *p_s_path = p_s_tb->tb_path;
1892 int n_position,
1893 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h);
1894
1895 /* We are in the root or in the new root. */
1896 if (n_path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1897
1898 RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
1899 "PAP-8260: invalid offset in the path");
1900
1901 if (PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->
1902 b_blocknr == SB_ROOT_BLOCK(p_s_tb->tb_sb)) {
1903 /* Root is not changed. */
1904 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
1905 PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
1906 return CARRY_ON;
1907 }
1908 return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
1909 }
1910
1911 if (!B_IS_IN_TREE
1912 (p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)))
1913 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
1838 1914
1915 if ((n_position =
1916 PATH_OFFSET_POSITION(p_s_path,
1917 n_path_offset - 1)) > B_NR_ITEMS(p_s_bh))
1918 return REPEAT_SEARCH;
1839 1919
1840/* Check whether parent at the path is the really parent of the current node.*/ 1920 if (B_N_CHILD_NUM(p_s_bh, n_position) !=
1841static int get_direct_parent( 1921 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr)
1842 struct tree_balance * p_s_tb, 1922 /* Parent in the path is not parent of the current node in the tree. */
1843 int n_h 1923 return REPEAT_SEARCH;
1844 ) { 1924
1845 struct buffer_head * p_s_bh; 1925 if (buffer_locked(p_s_bh)) {
1846 struct path * p_s_path = p_s_tb->tb_path; 1926 __wait_on_buffer(p_s_bh);
1847 int n_position, 1927 if (FILESYSTEM_CHANGED_TB(p_s_tb))
1848 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h); 1928 return REPEAT_SEARCH;
1849
1850 /* We are in the root or in the new root. */
1851 if ( n_path_offset <= FIRST_PATH_ELEMENT_OFFSET ) {
1852
1853 RFALSE( n_path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
1854 "PAP-8260: invalid offset in the path");
1855
1856 if ( PATH_OFFSET_PBUFFER(p_s_path, FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1857 SB_ROOT_BLOCK (p_s_tb->tb_sb) ) {
1858 /* Root is not changed. */
1859 PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1) = NULL;
1860 PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1) = 0;
1861 return CARRY_ON;
1862 } 1929 }
1863 return REPEAT_SEARCH; /* Root is changed and we must recalculate the path. */
1864 }
1865
1866 if ( ! B_IS_IN_TREE(p_s_bh = PATH_OFFSET_PBUFFER(p_s_path, n_path_offset - 1)) )
1867 return REPEAT_SEARCH; /* Parent in the path is not in the tree. */
1868
1869 if ( (n_position = PATH_OFFSET_POSITION(p_s_path, n_path_offset - 1)) > B_NR_ITEMS(p_s_bh) )
1870 return REPEAT_SEARCH;
1871
1872 if ( B_N_CHILD_NUM(p_s_bh, n_position) != PATH_OFFSET_PBUFFER(p_s_path, n_path_offset)->b_blocknr )
1873 /* Parent in the path is not parent of the current node in the tree. */
1874 return REPEAT_SEARCH;
1875
1876 if ( buffer_locked(p_s_bh) ) {
1877 __wait_on_buffer(p_s_bh);
1878 if ( FILESYSTEM_CHANGED_TB (p_s_tb) )
1879 return REPEAT_SEARCH;
1880 }
1881
1882 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
1883}
1884 1930
1931 return CARRY_ON; /* Parent in the path is unlocked and really parent of the current node. */
1932}
1885 1933
1886/* Using lnum[n_h] and rnum[n_h] we should determine what neighbors 1934/* Using lnum[n_h] and rnum[n_h] we should determine what neighbors
1887 * of S[n_h] we 1935 * of S[n_h] we
@@ -1889,356 +1937,401 @@ static int get_direct_parent(
1889 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked; 1937 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
1890 * CARRY_ON - schedule didn't occur while the function worked; 1938 * CARRY_ON - schedule didn't occur while the function worked;
1891 */ 1939 */
1892static int get_neighbors( 1940static int get_neighbors(struct tree_balance *p_s_tb, int n_h)
1893 struct tree_balance * p_s_tb, 1941{
1894 int n_h 1942 int n_child_position,
1895 ) { 1943 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1);
1896 int n_child_position, 1944 unsigned long n_son_number;
1897 n_path_offset = PATH_H_PATH_OFFSET(p_s_tb->tb_path, n_h + 1); 1945 struct super_block *p_s_sb = p_s_tb->tb_sb;
1898 unsigned long n_son_number; 1946 struct buffer_head *p_s_bh;
1899 struct super_block * p_s_sb = p_s_tb->tb_sb; 1947
1900 struct buffer_head * p_s_bh; 1948 PROC_INFO_INC(p_s_sb, get_neighbors[n_h]);
1901 1949
1902 1950 if (p_s_tb->lnum[n_h]) {
1903 PROC_INFO_INC( p_s_sb, get_neighbors[ n_h ] ); 1951 /* We need left neighbor to balance S[n_h]. */
1904 1952 PROC_INFO_INC(p_s_sb, need_l_neighbor[n_h]);
1905 if ( p_s_tb->lnum[n_h] ) { 1953 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
1906 /* We need left neighbor to balance S[n_h]. */ 1954
1907 PROC_INFO_INC( p_s_sb, need_l_neighbor[ n_h ] ); 1955 RFALSE(p_s_bh == p_s_tb->FL[n_h] &&
1908 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset); 1956 !PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset),
1909 1957 "PAP-8270: invalid position in the parent");
1910 RFALSE( p_s_bh == p_s_tb->FL[n_h] && 1958
1911 ! PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset), 1959 n_child_position =
1912 "PAP-8270: invalid position in the parent"); 1960 (p_s_bh ==
1913 1961 p_s_tb->FL[n_h]) ? p_s_tb->lkey[n_h] : B_NR_ITEMS(p_s_tb->
1914 n_child_position = ( p_s_bh == p_s_tb->FL[n_h] ) ? p_s_tb->lkey[n_h] : B_NR_ITEMS (p_s_tb->FL[n_h]); 1962 FL[n_h]);
1915 n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position); 1963 n_son_number = B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position);
1916 p_s_bh = sb_bread(p_s_sb, n_son_number); 1964 p_s_bh = sb_bread(p_s_sb, n_son_number);
1917 if (!p_s_bh) 1965 if (!p_s_bh)
1918 return IO_ERROR; 1966 return IO_ERROR;
1919 if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) { 1967 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1920 decrement_bcount(p_s_bh); 1968 decrement_bcount(p_s_bh);
1921 PROC_INFO_INC( p_s_sb, get_neighbors_restart[ n_h ] ); 1969 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
1922 return REPEAT_SEARCH; 1970 return REPEAT_SEARCH;
1971 }
1972
1973 RFALSE(!B_IS_IN_TREE(p_s_tb->FL[n_h]) ||
1974 n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) ||
1975 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) !=
1976 p_s_bh->b_blocknr, "PAP-8275: invalid parent");
1977 RFALSE(!B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child");
1978 RFALSE(!n_h &&
1979 B_FREE_SPACE(p_s_bh) !=
1980 MAX_CHILD_SIZE(p_s_bh) -
1981 dc_size(B_N_CHILD(p_s_tb->FL[0], n_child_position)),
1982 "PAP-8290: invalid child size of left neighbor");
1983
1984 decrement_bcount(p_s_tb->L[n_h]);
1985 p_s_tb->L[n_h] = p_s_bh;
1923 } 1986 }
1924 1987
1925 RFALSE( ! B_IS_IN_TREE(p_s_tb->FL[n_h]) || 1988 if (p_s_tb->rnum[n_h]) { /* We need right neighbor to balance S[n_path_offset]. */
1926 n_child_position > B_NR_ITEMS(p_s_tb->FL[n_h]) || 1989 PROC_INFO_INC(p_s_sb, need_r_neighbor[n_h]);
1927 B_N_CHILD_NUM(p_s_tb->FL[n_h], n_child_position) != 1990 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset);
1928 p_s_bh->b_blocknr, "PAP-8275: invalid parent"); 1991
1929 RFALSE( ! B_IS_IN_TREE(p_s_bh), "PAP-8280: invalid child"); 1992 RFALSE(p_s_bh == p_s_tb->FR[n_h] &&
1930 RFALSE( ! n_h && 1993 PATH_OFFSET_POSITION(p_s_tb->tb_path,
1931 B_FREE_SPACE (p_s_bh) != MAX_CHILD_SIZE (p_s_bh) - dc_size(B_N_CHILD (p_s_tb->FL[0],n_child_position)), 1994 n_path_offset) >=
1932 "PAP-8290: invalid child size of left neighbor"); 1995 B_NR_ITEMS(p_s_bh),
1933 1996 "PAP-8295: invalid position in the parent");
1934 decrement_bcount(p_s_tb->L[n_h]); 1997
1935 p_s_tb->L[n_h] = p_s_bh; 1998 n_child_position =
1936 } 1999 (p_s_bh == p_s_tb->FR[n_h]) ? p_s_tb->rkey[n_h] + 1 : 0;
1937 2000 n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position);
1938 2001 p_s_bh = sb_bread(p_s_sb, n_son_number);
1939 if ( p_s_tb->rnum[n_h] ) { /* We need right neighbor to balance S[n_path_offset]. */ 2002 if (!p_s_bh)
1940 PROC_INFO_INC( p_s_sb, need_r_neighbor[ n_h ] ); 2003 return IO_ERROR;
1941 p_s_bh = PATH_OFFSET_PBUFFER(p_s_tb->tb_path, n_path_offset); 2004 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
1942 2005 decrement_bcount(p_s_bh);
1943 RFALSE( p_s_bh == p_s_tb->FR[n_h] && 2006 PROC_INFO_INC(p_s_sb, get_neighbors_restart[n_h]);
1944 PATH_OFFSET_POSITION(p_s_tb->tb_path, n_path_offset) >= B_NR_ITEMS(p_s_bh), 2007 return REPEAT_SEARCH;
1945 "PAP-8295: invalid position in the parent"); 2008 }
1946 2009 decrement_bcount(p_s_tb->R[n_h]);
1947 n_child_position = ( p_s_bh == p_s_tb->FR[n_h] ) ? p_s_tb->rkey[n_h] + 1 : 0; 2010 p_s_tb->R[n_h] = p_s_bh;
1948 n_son_number = B_N_CHILD_NUM(p_s_tb->FR[n_h], n_child_position); 2011
1949 p_s_bh = sb_bread(p_s_sb, n_son_number); 2012 RFALSE(!n_h
1950 if (!p_s_bh) 2013 && B_FREE_SPACE(p_s_bh) !=
1951 return IO_ERROR; 2014 MAX_CHILD_SIZE(p_s_bh) -
1952 if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) { 2015 dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)),
1953 decrement_bcount(p_s_bh); 2016 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
1954 PROC_INFO_INC( p_s_sb, get_neighbors_restart[ n_h ] ); 2017 B_FREE_SPACE(p_s_bh), MAX_CHILD_SIZE(p_s_bh),
1955 return REPEAT_SEARCH; 2018 dc_size(B_N_CHILD(p_s_tb->FR[0], n_child_position)));
2019
1956 } 2020 }
1957 decrement_bcount(p_s_tb->R[n_h]); 2021 return CARRY_ON;
1958 p_s_tb->R[n_h] = p_s_bh;
1959
1960 RFALSE( ! n_h && B_FREE_SPACE (p_s_bh) != MAX_CHILD_SIZE (p_s_bh) - dc_size(B_N_CHILD (p_s_tb->FR[0],n_child_position)),
1961 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
1962 B_FREE_SPACE (p_s_bh), MAX_CHILD_SIZE (p_s_bh),
1963 dc_size(B_N_CHILD (p_s_tb->FR[0],n_child_position)));
1964
1965 }
1966 return CARRY_ON;
1967} 2022}
1968 2023
1969#ifdef CONFIG_REISERFS_CHECK 2024#ifdef CONFIG_REISERFS_CHECK
1970void * reiserfs_kmalloc (size_t size, int flags, struct super_block * s) 2025void *reiserfs_kmalloc(size_t size, int flags, struct super_block *s)
1971{ 2026{
1972 void * vp; 2027 void *vp;
1973 static size_t malloced; 2028 static size_t malloced;
1974 2029
1975 2030 vp = kmalloc(size, flags);
1976 vp = kmalloc (size, flags); 2031 if (vp) {
1977 if (vp) { 2032 REISERFS_SB(s)->s_kmallocs += size;
1978 REISERFS_SB(s)->s_kmallocs += size; 2033 if (REISERFS_SB(s)->s_kmallocs > malloced + 200000) {
1979 if (REISERFS_SB(s)->s_kmallocs > malloced + 200000) { 2034 reiserfs_warning(s,
1980 reiserfs_warning (s, 2035 "vs-8301: reiserfs_kmalloc: allocated memory %d",
1981 "vs-8301: reiserfs_kmalloc: allocated memory %d", 2036 REISERFS_SB(s)->s_kmallocs);
1982 REISERFS_SB(s)->s_kmallocs); 2037 malloced = REISERFS_SB(s)->s_kmallocs;
1983 malloced = REISERFS_SB(s)->s_kmallocs; 2038 }
1984 } 2039 }
1985 } 2040 return vp;
1986 return vp;
1987} 2041}
1988 2042
1989void reiserfs_kfree (const void * vp, size_t size, struct super_block * s) 2043void reiserfs_kfree(const void *vp, size_t size, struct super_block *s)
1990{ 2044{
1991 kfree (vp); 2045 kfree(vp);
1992 2046
1993 REISERFS_SB(s)->s_kmallocs -= size; 2047 REISERFS_SB(s)->s_kmallocs -= size;
1994 if (REISERFS_SB(s)->s_kmallocs < 0) 2048 if (REISERFS_SB(s)->s_kmallocs < 0)
1995 reiserfs_warning (s, "vs-8302: reiserfs_kfree: allocated memory %d", 2049 reiserfs_warning(s,
1996 REISERFS_SB(s)->s_kmallocs); 2050 "vs-8302: reiserfs_kfree: allocated memory %d",
2051 REISERFS_SB(s)->s_kmallocs);
1997 2052
1998} 2053}
1999#endif 2054#endif
2000 2055
2001 2056static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
2002static int get_virtual_node_size (struct super_block * sb, struct buffer_head * bh)
2003{ 2057{
2004 int max_num_of_items; 2058 int max_num_of_items;
2005 int max_num_of_entries; 2059 int max_num_of_entries;
2006 unsigned long blocksize = sb->s_blocksize; 2060 unsigned long blocksize = sb->s_blocksize;
2007 2061
2008#define MIN_NAME_LEN 1 2062#define MIN_NAME_LEN 1
2009 2063
2010 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN); 2064 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
2011 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) / 2065 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
2012 (DEH_SIZE + MIN_NAME_LEN); 2066 (DEH_SIZE + MIN_NAME_LEN);
2013 2067
2014 return sizeof(struct virtual_node) + 2068 return sizeof(struct virtual_node) +
2015 max(max_num_of_items * sizeof (struct virtual_item), 2069 max(max_num_of_items * sizeof(struct virtual_item),
2016 sizeof (struct virtual_item) + sizeof(struct direntry_uarea) + 2070 sizeof(struct virtual_item) + sizeof(struct direntry_uarea) +
2017 (max_num_of_entries - 1) * sizeof (__u16)); 2071 (max_num_of_entries - 1) * sizeof(__u16));
2018} 2072}
2019 2073
2020
2021
2022/* maybe we should fail balancing we are going to perform when kmalloc 2074/* maybe we should fail balancing we are going to perform when kmalloc
2023 fails several times. But now it will loop until kmalloc gets 2075 fails several times. But now it will loop until kmalloc gets
2024 required memory */ 2076 required memory */
2025static int get_mem_for_virtual_node (struct tree_balance * tb) 2077static int get_mem_for_virtual_node(struct tree_balance *tb)
2026{ 2078{
2027 int check_fs = 0; 2079 int check_fs = 0;
2028 int size; 2080 int size;
2029 char * buf; 2081 char *buf;
2030 2082
2031 size = get_virtual_node_size (tb->tb_sb, PATH_PLAST_BUFFER (tb->tb_path)); 2083 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
2032 2084
2033 if (size > tb->vn_buf_size) { 2085 if (size > tb->vn_buf_size) {
2034 /* we have to allocate more memory for virtual node */ 2086 /* we have to allocate more memory for virtual node */
2035 if (tb->vn_buf) { 2087 if (tb->vn_buf) {
2036 /* free memory allocated before */ 2088 /* free memory allocated before */
2037 reiserfs_kfree (tb->vn_buf, tb->vn_buf_size, tb->tb_sb); 2089 reiserfs_kfree(tb->vn_buf, tb->vn_buf_size, tb->tb_sb);
2038 /* this is not needed if kfree is atomic */ 2090 /* this is not needed if kfree is atomic */
2039 check_fs = 1; 2091 check_fs = 1;
2040 } 2092 }
2041 2093
2042 /* virtual node requires now more memory */ 2094 /* virtual node requires now more memory */
2043 tb->vn_buf_size = size; 2095 tb->vn_buf_size = size;
2044 2096
2045 /* get memory for virtual item */ 2097 /* get memory for virtual item */
2046 buf = reiserfs_kmalloc(size, GFP_ATOMIC | __GFP_NOWARN, tb->tb_sb); 2098 buf =
2047 if ( ! buf ) { 2099 reiserfs_kmalloc(size, GFP_ATOMIC | __GFP_NOWARN,
2048 /* getting memory with GFP_KERNEL priority may involve 2100 tb->tb_sb);
2049 balancing now (due to indirect_to_direct conversion on 2101 if (!buf) {
2050 dcache shrinking). So, release path and collected 2102 /* getting memory with GFP_KERNEL priority may involve
2051 resources here */ 2103 balancing now (due to indirect_to_direct conversion on
2052 free_buffers_in_tb (tb); 2104 dcache shrinking). So, release path and collected
2053 buf = reiserfs_kmalloc(size, GFP_NOFS, tb->tb_sb); 2105 resources here */
2054 if ( !buf ) { 2106 free_buffers_in_tb(tb);
2107 buf = reiserfs_kmalloc(size, GFP_NOFS, tb->tb_sb);
2108 if (!buf) {
2055#ifdef CONFIG_REISERFS_CHECK 2109#ifdef CONFIG_REISERFS_CHECK
2056 reiserfs_warning (tb->tb_sb, 2110 reiserfs_warning(tb->tb_sb,
2057 "vs-8345: get_mem_for_virtual_node: " 2111 "vs-8345: get_mem_for_virtual_node: "
2058 "kmalloc failed. reiserfs kmalloced %d bytes", 2112 "kmalloc failed. reiserfs kmalloced %d bytes",
2059 REISERFS_SB(tb->tb_sb)->s_kmallocs); 2113 REISERFS_SB(tb->tb_sb)->
2114 s_kmallocs);
2060#endif 2115#endif
2061 tb->vn_buf_size = 0; 2116 tb->vn_buf_size = 0;
2062 } 2117 }
2063 tb->vn_buf = buf; 2118 tb->vn_buf = buf;
2064 schedule() ; 2119 schedule();
2065 return REPEAT_SEARCH; 2120 return REPEAT_SEARCH;
2066 } 2121 }
2067 2122
2068 tb->vn_buf = buf; 2123 tb->vn_buf = buf;
2069 } 2124 }
2070 2125
2071 if ( check_fs && FILESYSTEM_CHANGED_TB (tb) ) 2126 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2072 return REPEAT_SEARCH; 2127 return REPEAT_SEARCH;
2073 2128
2074 return CARRY_ON; 2129 return CARRY_ON;
2075} 2130}
2076 2131
2077
2078#ifdef CONFIG_REISERFS_CHECK 2132#ifdef CONFIG_REISERFS_CHECK
2079static void tb_buffer_sanity_check (struct super_block * p_s_sb, 2133static void tb_buffer_sanity_check(struct super_block *p_s_sb,
2080 struct buffer_head * p_s_bh, 2134 struct buffer_head *p_s_bh,
2081 const char *descr, int level) { 2135 const char *descr, int level)
2082 if (p_s_bh) {
2083 if (atomic_read (&(p_s_bh->b_count)) <= 0) {
2084
2085 reiserfs_panic (p_s_sb, "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n", descr, level, p_s_bh);
2086 }
2087
2088 if ( ! buffer_uptodate (p_s_bh) ) {
2089 reiserfs_panic (p_s_sb, "jmacd-2: tb_buffer_sanity_check(): buffer is not up to date %s[%d] (%b)\n", descr, level, p_s_bh);
2090 }
2091
2092 if ( ! B_IS_IN_TREE (p_s_bh) ) {
2093 reiserfs_panic (p_s_sb, "jmacd-3: tb_buffer_sanity_check(): buffer is not in tree %s[%d] (%b)\n", descr, level, p_s_bh);
2094 }
2095
2096 if (p_s_bh->b_bdev != p_s_sb->s_bdev) {
2097 reiserfs_panic (p_s_sb, "jmacd-4: tb_buffer_sanity_check(): buffer has wrong device %s[%d] (%b)\n", descr, level, p_s_bh);
2098 }
2099
2100 if (p_s_bh->b_size != p_s_sb->s_blocksize) {
2101 reiserfs_panic (p_s_sb, "jmacd-5: tb_buffer_sanity_check(): buffer has wrong blocksize %s[%d] (%b)\n", descr, level, p_s_bh);
2102 }
2103
2104 if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(p_s_sb)) {
2105 reiserfs_panic (p_s_sb, "jmacd-6: tb_buffer_sanity_check(): buffer block number too high %s[%d] (%b)\n", descr, level, p_s_bh);
2106 }
2107 }
2108}
2109#else
2110static void tb_buffer_sanity_check (struct super_block * p_s_sb,
2111 struct buffer_head * p_s_bh,
2112 const char *descr, int level)
2113{;}
2114#endif
2115
2116static int clear_all_dirty_bits(struct super_block *s,
2117 struct buffer_head *bh) {
2118 return reiserfs_prepare_for_journal(s, bh, 0) ;
2119}
2120
2121static int wait_tb_buffers_until_unlocked (struct tree_balance * p_s_tb)
2122{ 2136{
2123 struct buffer_head * locked; 2137 if (p_s_bh) {
2124#ifdef CONFIG_REISERFS_CHECK 2138 if (atomic_read(&(p_s_bh->b_count)) <= 0) {
2125 int repeat_counter = 0;
2126#endif
2127 int i;
2128 2139
2129 do { 2140 reiserfs_panic(p_s_sb,
2130 2141 "jmacd-1: tb_buffer_sanity_check(): negative or zero reference counter for buffer %s[%d] (%b)\n",
2131 locked = NULL; 2142 descr, level, p_s_bh);
2132
2133 for ( i = p_s_tb->tb_path->path_length; !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i-- ) {
2134 if ( PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i) ) {
2135 /* if I understand correctly, we can only be sure the last buffer
2136 ** in the path is in the tree --clm
2137 */
2138#ifdef CONFIG_REISERFS_CHECK
2139 if (PATH_PLAST_BUFFER(p_s_tb->tb_path) ==
2140 PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2141 tb_buffer_sanity_check (p_s_tb->tb_sb,
2142 PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i),
2143 "S",
2144 p_s_tb->tb_path->path_length - i);
2145 } 2143 }
2146#endif
2147 if (!clear_all_dirty_bits(p_s_tb->tb_sb,
2148 PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i)))
2149 {
2150 locked = PATH_OFFSET_PBUFFER (p_s_tb->tb_path, i);
2151 }
2152 }
2153 }
2154 2144
2155 for ( i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i]; i++ ) { 2145 if (!buffer_uptodate(p_s_bh)) {
2146 reiserfs_panic(p_s_sb,
2147 "jmacd-2: tb_buffer_sanity_check(): buffer is not up to date %s[%d] (%b)\n",
2148 descr, level, p_s_bh);
2149 }
2156 2150
2157 if (p_s_tb->lnum[i] ) { 2151 if (!B_IS_IN_TREE(p_s_bh)) {
2152 reiserfs_panic(p_s_sb,
2153 "jmacd-3: tb_buffer_sanity_check(): buffer is not in tree %s[%d] (%b)\n",
2154 descr, level, p_s_bh);
2155 }
2158 2156
2159 if ( p_s_tb->L[i] ) { 2157 if (p_s_bh->b_bdev != p_s_sb->s_bdev) {
2160 tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->L[i], "L", i); 2158 reiserfs_panic(p_s_sb,
2161 if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->L[i])) 2159 "jmacd-4: tb_buffer_sanity_check(): buffer has wrong device %s[%d] (%b)\n",
2162 locked = p_s_tb->L[i]; 2160 descr, level, p_s_bh);
2163 } 2161 }
2164 2162
2165 if ( !locked && p_s_tb->FL[i] ) { 2163 if (p_s_bh->b_size != p_s_sb->s_blocksize) {
2166 tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->FL[i], "FL", i); 2164 reiserfs_panic(p_s_sb,
2167 if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->FL[i])) 2165 "jmacd-5: tb_buffer_sanity_check(): buffer has wrong blocksize %s[%d] (%b)\n",
2168 locked = p_s_tb->FL[i]; 2166 descr, level, p_s_bh);
2169 } 2167 }
2170 2168
2171 if ( !locked && p_s_tb->CFL[i] ) { 2169 if (p_s_bh->b_blocknr > SB_BLOCK_COUNT(p_s_sb)) {
2172 tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->CFL[i], "CFL", i); 2170 reiserfs_panic(p_s_sb,
2173 if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->CFL[i])) 2171 "jmacd-6: tb_buffer_sanity_check(): buffer block number too high %s[%d] (%b)\n",
2174 locked = p_s_tb->CFL[i]; 2172 descr, level, p_s_bh);
2175 } 2173 }
2174 }
2175}
2176#else
2177static void tb_buffer_sanity_check(struct super_block *p_s_sb,
2178 struct buffer_head *p_s_bh,
2179 const char *descr, int level)
2180{;
2181}
2182#endif
2176 2183
2177 } 2184static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
2185{
2186 return reiserfs_prepare_for_journal(s, bh, 0);
2187}
2178 2188
2179 if ( !locked && (p_s_tb->rnum[i]) ) { 2189static int wait_tb_buffers_until_unlocked(struct tree_balance *p_s_tb)
2190{
2191 struct buffer_head *locked;
2192#ifdef CONFIG_REISERFS_CHECK
2193 int repeat_counter = 0;
2194#endif
2195 int i;
2180 2196
2181 if ( p_s_tb->R[i] ) { 2197 do {
2182 tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->R[i], "R", i);
2183 if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->R[i]))
2184 locked = p_s_tb->R[i];
2185 }
2186 2198
2187 2199 locked = NULL;
2188 if ( !locked && p_s_tb->FR[i] ) { 2200
2189 tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->FR[i], "FR", i); 2201 for (i = p_s_tb->tb_path->path_length;
2190 if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->FR[i])) 2202 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2191 locked = p_s_tb->FR[i]; 2203 if (PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2204 /* if I understand correctly, we can only be sure the last buffer
2205 ** in the path is in the tree --clm
2206 */
2207#ifdef CONFIG_REISERFS_CHECK
2208 if (PATH_PLAST_BUFFER(p_s_tb->tb_path) ==
2209 PATH_OFFSET_PBUFFER(p_s_tb->tb_path, i)) {
2210 tb_buffer_sanity_check(p_s_tb->tb_sb,
2211 PATH_OFFSET_PBUFFER
2212 (p_s_tb->tb_path,
2213 i), "S",
2214 p_s_tb->tb_path->
2215 path_length - i);
2216 }
2217#endif
2218 if (!clear_all_dirty_bits(p_s_tb->tb_sb,
2219 PATH_OFFSET_PBUFFER
2220 (p_s_tb->tb_path,
2221 i))) {
2222 locked =
2223 PATH_OFFSET_PBUFFER(p_s_tb->tb_path,
2224 i);
2225 }
2226 }
2192 } 2227 }
2193 2228
2194 if ( !locked && p_s_tb->CFR[i] ) { 2229 for (i = 0; !locked && i < MAX_HEIGHT && p_s_tb->insert_size[i];
2195 tb_buffer_sanity_check (p_s_tb->tb_sb, p_s_tb->CFR[i], "CFR", i); 2230 i++) {
2196 if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->CFR[i])) 2231
2197 locked = p_s_tb->CFR[i]; 2232 if (p_s_tb->lnum[i]) {
2233
2234 if (p_s_tb->L[i]) {
2235 tb_buffer_sanity_check(p_s_tb->tb_sb,
2236 p_s_tb->L[i],
2237 "L", i);
2238 if (!clear_all_dirty_bits
2239 (p_s_tb->tb_sb, p_s_tb->L[i]))
2240 locked = p_s_tb->L[i];
2241 }
2242
2243 if (!locked && p_s_tb->FL[i]) {
2244 tb_buffer_sanity_check(p_s_tb->tb_sb,
2245 p_s_tb->FL[i],
2246 "FL", i);
2247 if (!clear_all_dirty_bits
2248 (p_s_tb->tb_sb, p_s_tb->FL[i]))
2249 locked = p_s_tb->FL[i];
2250 }
2251
2252 if (!locked && p_s_tb->CFL[i]) {
2253 tb_buffer_sanity_check(p_s_tb->tb_sb,
2254 p_s_tb->CFL[i],
2255 "CFL", i);
2256 if (!clear_all_dirty_bits
2257 (p_s_tb->tb_sb, p_s_tb->CFL[i]))
2258 locked = p_s_tb->CFL[i];
2259 }
2260
2261 }
2262
2263 if (!locked && (p_s_tb->rnum[i])) {
2264
2265 if (p_s_tb->R[i]) {
2266 tb_buffer_sanity_check(p_s_tb->tb_sb,
2267 p_s_tb->R[i],
2268 "R", i);
2269 if (!clear_all_dirty_bits
2270 (p_s_tb->tb_sb, p_s_tb->R[i]))
2271 locked = p_s_tb->R[i];
2272 }
2273
2274 if (!locked && p_s_tb->FR[i]) {
2275 tb_buffer_sanity_check(p_s_tb->tb_sb,
2276 p_s_tb->FR[i],
2277 "FR", i);
2278 if (!clear_all_dirty_bits
2279 (p_s_tb->tb_sb, p_s_tb->FR[i]))
2280 locked = p_s_tb->FR[i];
2281 }
2282
2283 if (!locked && p_s_tb->CFR[i]) {
2284 tb_buffer_sanity_check(p_s_tb->tb_sb,
2285 p_s_tb->CFR[i],
2286 "CFR", i);
2287 if (!clear_all_dirty_bits
2288 (p_s_tb->tb_sb, p_s_tb->CFR[i]))
2289 locked = p_s_tb->CFR[i];
2290 }
2291 }
2292 }
2293 /* as far as I can tell, this is not required. The FEB list seems
2294 ** to be full of newly allocated nodes, which will never be locked,
2295 ** dirty, or anything else.
2296 ** To be safe, I'm putting in the checks and waits in. For the moment,
2297 ** they are needed to keep the code in journal.c from complaining
2298 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2299 ** --clm
2300 */
2301 for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2302 if (p_s_tb->FEB[i]) {
2303 if (!clear_all_dirty_bits
2304 (p_s_tb->tb_sb, p_s_tb->FEB[i]))
2305 locked = p_s_tb->FEB[i];
2306 }
2198 } 2307 }
2199 }
2200 }
2201 /* as far as I can tell, this is not required. The FEB list seems
2202 ** to be full of newly allocated nodes, which will never be locked,
2203 ** dirty, or anything else.
2204 ** To be safe, I'm putting in the checks and waits in. For the moment,
2205 ** they are needed to keep the code in journal.c from complaining
2206 ** about the buffer. That code is inside CONFIG_REISERFS_CHECK as well.
2207 ** --clm
2208 */
2209 for ( i = 0; !locked && i < MAX_FEB_SIZE; i++ ) {
2210 if ( p_s_tb->FEB[i] ) {
2211 if (!clear_all_dirty_bits(p_s_tb->tb_sb, p_s_tb->FEB[i]))
2212 locked = p_s_tb->FEB[i] ;
2213 }
2214 }
2215 2308
2216 if (locked) { 2309 if (locked) {
2217#ifdef CONFIG_REISERFS_CHECK 2310#ifdef CONFIG_REISERFS_CHECK
2218 repeat_counter++; 2311 repeat_counter++;
2219 if ( (repeat_counter % 10000) == 0) { 2312 if ((repeat_counter % 10000) == 0) {
2220 reiserfs_warning (p_s_tb->tb_sb, 2313 reiserfs_warning(p_s_tb->tb_sb,
2221 "wait_tb_buffers_until_released(): too many " 2314 "wait_tb_buffers_until_released(): too many "
2222 "iterations waiting for buffer to unlock " 2315 "iterations waiting for buffer to unlock "
2223 "(%b)", locked); 2316 "(%b)", locked);
2224 2317
2225 /* Don't loop forever. Try to recover from possible error. */ 2318 /* Don't loop forever. Try to recover from possible error. */
2226 2319
2227 return ( FILESYSTEM_CHANGED_TB (p_s_tb) ) ? REPEAT_SEARCH : CARRY_ON; 2320 return (FILESYSTEM_CHANGED_TB(p_s_tb)) ?
2228 } 2321 REPEAT_SEARCH : CARRY_ON;
2322 }
2229#endif 2323#endif
2230 __wait_on_buffer (locked); 2324 __wait_on_buffer(locked);
2231 if ( FILESYSTEM_CHANGED_TB (p_s_tb) ) { 2325 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2232 return REPEAT_SEARCH; 2326 return REPEAT_SEARCH;
2233 } 2327 }
2234 } 2328 }
2235 2329
2236 } while (locked); 2330 } while (locked);
2237 2331
2238 return CARRY_ON; 2332 return CARRY_ON;
2239} 2333}
2240 2334
2241
2242/* Prepare for balancing, that is 2335/* Prepare for balancing, that is
2243 * get all necessary parents, and neighbors; 2336 * get all necessary parents, and neighbors;
2244 * analyze what and where should be moved; 2337 * analyze what and where should be moved;
@@ -2267,252 +2360,266 @@ static int wait_tb_buffers_until_unlocked (struct tree_balance * p_s_tb)
2267 * -1 - if no_disk_space 2360 * -1 - if no_disk_space
2268 */ 2361 */
2269 2362
2363int fix_nodes(int n_op_mode, struct tree_balance *p_s_tb, struct item_head *p_s_ins_ih, // item head of item being inserted
2364 const void *data // inserted item or data to be pasted
2365 )
2366{
2367 int n_ret_value, n_h, n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
2368 int n_pos_in_item;
2270 2369
2271int fix_nodes (int n_op_mode, 2370 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2272 struct tree_balance * p_s_tb, 2371 ** during wait_tb_buffers_run
2273 struct item_head * p_s_ins_ih, // item head of item being inserted 2372 */
2274 const void * data // inserted item or data to be pasted 2373 int wait_tb_buffers_run = 0;
2275 ) { 2374 struct buffer_head *p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path);
2276 int n_ret_value,
2277 n_h,
2278 n_item_num = PATH_LAST_POSITION(p_s_tb->tb_path);
2279 int n_pos_in_item;
2280
2281 /* we set wait_tb_buffers_run when we have to restore any dirty bits cleared
2282 ** during wait_tb_buffers_run
2283 */
2284 int wait_tb_buffers_run = 0 ;
2285 struct buffer_head * p_s_tbS0 = PATH_PLAST_BUFFER(p_s_tb->tb_path);
2286
2287 ++ REISERFS_SB(p_s_tb -> tb_sb) -> s_fix_nodes;
2288
2289 n_pos_in_item = p_s_tb->tb_path->pos_in_item;
2290
2291
2292 p_s_tb->fs_gen = get_generation (p_s_tb->tb_sb);
2293
2294 /* we prepare and log the super here so it will already be in the
2295 ** transaction when do_balance needs to change it.
2296 ** This way do_balance won't have to schedule when trying to prepare
2297 ** the super for logging
2298 */
2299 reiserfs_prepare_for_journal(p_s_tb->tb_sb,
2300 SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1) ;
2301 journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb,
2302 SB_BUFFER_WITH_SB(p_s_tb->tb_sb)) ;
2303 if ( FILESYSTEM_CHANGED_TB (p_s_tb) )
2304 return REPEAT_SEARCH;
2305
2306 /* if it possible in indirect_to_direct conversion */
2307 if (buffer_locked (p_s_tbS0)) {
2308 __wait_on_buffer (p_s_tbS0);
2309 if ( FILESYSTEM_CHANGED_TB (p_s_tb) )
2310 return REPEAT_SEARCH;
2311 }
2312 2375
2313#ifdef CONFIG_REISERFS_CHECK 2376 ++REISERFS_SB(p_s_tb->tb_sb)->s_fix_nodes;
2314 if ( cur_tb ) { 2377
2315 print_cur_tb ("fix_nodes"); 2378 n_pos_in_item = p_s_tb->tb_path->pos_in_item;
2316 reiserfs_panic(p_s_tb->tb_sb,"PAP-8305: fix_nodes: there is pending do_balance"); 2379
2317 } 2380 p_s_tb->fs_gen = get_generation(p_s_tb->tb_sb);
2318
2319 if (!buffer_uptodate (p_s_tbS0) || !B_IS_IN_TREE (p_s_tbS0)) {
2320 reiserfs_panic (p_s_tb->tb_sb, "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate "
2321 "at the beginning of fix_nodes or not in tree (mode %c)", p_s_tbS0, p_s_tbS0, n_op_mode);
2322 }
2323
2324 /* Check parameters. */
2325 switch (n_op_mode) {
2326 case M_INSERT:
2327 if ( n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0) )
2328 reiserfs_panic(p_s_tb->tb_sb,"PAP-8330: fix_nodes: Incorrect item number %d (in S0 - %d) in case of insert",
2329 n_item_num, B_NR_ITEMS(p_s_tbS0));
2330 break;
2331 case M_PASTE:
2332 case M_DELETE:
2333 case M_CUT:
2334 if ( n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0) ) {
2335 print_block (p_s_tbS0, 0, -1, -1);
2336 reiserfs_panic(p_s_tb->tb_sb,"PAP-8335: fix_nodes: Incorrect item number(%d); mode = %c insert_size = %d\n", n_item_num, n_op_mode, p_s_tb->insert_size[0]);
2337 }
2338 break;
2339 default:
2340 reiserfs_panic(p_s_tb->tb_sb,"PAP-8340: fix_nodes: Incorrect mode of operation");
2341 }
2342#endif
2343 2381
2344 if (get_mem_for_virtual_node (p_s_tb) == REPEAT_SEARCH) 2382 /* we prepare and log the super here so it will already be in the
2345 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat 2383 ** transaction when do_balance needs to change it.
2346 return REPEAT_SEARCH; 2384 ** This way do_balance won't have to schedule when trying to prepare
2385 ** the super for logging
2386 */
2387 reiserfs_prepare_for_journal(p_s_tb->tb_sb,
2388 SB_BUFFER_WITH_SB(p_s_tb->tb_sb), 1);
2389 journal_mark_dirty(p_s_tb->transaction_handle, p_s_tb->tb_sb,
2390 SB_BUFFER_WITH_SB(p_s_tb->tb_sb));
2391 if (FILESYSTEM_CHANGED_TB(p_s_tb))
2392 return REPEAT_SEARCH;
2347 2393
2394 /* if it possible in indirect_to_direct conversion */
2395 if (buffer_locked(p_s_tbS0)) {
2396 __wait_on_buffer(p_s_tbS0);
2397 if (FILESYSTEM_CHANGED_TB(p_s_tb))
2398 return REPEAT_SEARCH;
2399 }
2400#ifdef CONFIG_REISERFS_CHECK
2401 if (cur_tb) {
2402 print_cur_tb("fix_nodes");
2403 reiserfs_panic(p_s_tb->tb_sb,
2404 "PAP-8305: fix_nodes: there is pending do_balance");
2405 }
2348 2406
2349 /* Starting from the leaf level; for all levels n_h of the tree. */ 2407 if (!buffer_uptodate(p_s_tbS0) || !B_IS_IN_TREE(p_s_tbS0)) {
2350 for ( n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++ ) { 2408 reiserfs_panic(p_s_tb->tb_sb,
2351 if ( (n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON ) { 2409 "PAP-8320: fix_nodes: S[0] (%b %z) is not uptodate "
2352 goto repeat; 2410 "at the beginning of fix_nodes or not in tree (mode %c)",
2411 p_s_tbS0, p_s_tbS0, n_op_mode);
2353 } 2412 }
2354 2413
2355 if ( (n_ret_value = check_balance (n_op_mode, p_s_tb, n_h, n_item_num, 2414 /* Check parameters. */
2356 n_pos_in_item, p_s_ins_ih, data)) != CARRY_ON ) { 2415 switch (n_op_mode) {
2357 if ( n_ret_value == NO_BALANCING_NEEDED ) { 2416 case M_INSERT:
2358 /* No balancing for higher levels needed. */ 2417 if (n_item_num <= 0 || n_item_num > B_NR_ITEMS(p_s_tbS0))
2359 if ( (n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON ) { 2418 reiserfs_panic(p_s_tb->tb_sb,
2360 goto repeat; 2419 "PAP-8330: fix_nodes: Incorrect item number %d (in S0 - %d) in case of insert",
2420 n_item_num, B_NR_ITEMS(p_s_tbS0));
2421 break;
2422 case M_PASTE:
2423 case M_DELETE:
2424 case M_CUT:
2425 if (n_item_num < 0 || n_item_num >= B_NR_ITEMS(p_s_tbS0)) {
2426 print_block(p_s_tbS0, 0, -1, -1);
2427 reiserfs_panic(p_s_tb->tb_sb,
2428 "PAP-8335: fix_nodes: Incorrect item number(%d); mode = %c insert_size = %d\n",
2429 n_item_num, n_op_mode,
2430 p_s_tb->insert_size[0]);
2361 } 2431 }
2362 if ( n_h != MAX_HEIGHT - 1 )
2363 p_s_tb->insert_size[n_h + 1] = 0;
2364 /* ok, analysis and resource gathering are complete */
2365 break; 2432 break;
2366 } 2433 default:
2367 goto repeat; 2434 reiserfs_panic(p_s_tb->tb_sb,
2435 "PAP-8340: fix_nodes: Incorrect mode of operation");
2368 } 2436 }
2437#endif
2369 2438
2370 if ( (n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON ) { 2439 if (get_mem_for_virtual_node(p_s_tb) == REPEAT_SEARCH)
2371 goto repeat; 2440 // FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat
2372 } 2441 return REPEAT_SEARCH;
2373 2442
2374 if ( (n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON ) { 2443 /* Starting from the leaf level; for all levels n_h of the tree. */
2375 goto repeat; /* No disk space, or schedule occurred and 2444 for (n_h = 0; n_h < MAX_HEIGHT && p_s_tb->insert_size[n_h]; n_h++) {
2376 analysis may be invalid and needs to be redone. */ 2445 if ((n_ret_value = get_direct_parent(p_s_tb, n_h)) != CARRY_ON) {
2377 } 2446 goto repeat;
2378 2447 }
2379 if ( ! PATH_H_PBUFFER(p_s_tb->tb_path, n_h) ) {
2380 /* We have a positive insert size but no nodes exist on this
2381 level, this means that we are creating a new root. */
2382 2448
2383 RFALSE( p_s_tb->blknum[n_h] != 1, 2449 if ((n_ret_value =
2384 "PAP-8350: creating new empty root"); 2450 check_balance(n_op_mode, p_s_tb, n_h, n_item_num,
2451 n_pos_in_item, p_s_ins_ih,
2452 data)) != CARRY_ON) {
2453 if (n_ret_value == NO_BALANCING_NEEDED) {
2454 /* No balancing for higher levels needed. */
2455 if ((n_ret_value =
2456 get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2457 goto repeat;
2458 }
2459 if (n_h != MAX_HEIGHT - 1)
2460 p_s_tb->insert_size[n_h + 1] = 0;
2461 /* ok, analysis and resource gathering are complete */
2462 break;
2463 }
2464 goto repeat;
2465 }
2385 2466
2386 if ( n_h < MAX_HEIGHT - 1 ) 2467 if ((n_ret_value = get_neighbors(p_s_tb, n_h)) != CARRY_ON) {
2387 p_s_tb->insert_size[n_h + 1] = 0; 2468 goto repeat;
2388 }
2389 else
2390 if ( ! PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1) ) {
2391 if ( p_s_tb->blknum[n_h] > 1 ) {
2392 /* The tree needs to be grown, so this node S[n_h]
2393 which is the root node is split into two nodes,
2394 and a new node (S[n_h+1]) will be created to
2395 become the root node. */
2396
2397 RFALSE( n_h == MAX_HEIGHT - 1,
2398 "PAP-8355: attempt to create too high of a tree");
2399
2400 p_s_tb->insert_size[n_h + 1] = (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) + DC_SIZE;
2401 } 2469 }
2402 else 2470
2403 if ( n_h < MAX_HEIGHT - 1 ) 2471 if ((n_ret_value = get_empty_nodes(p_s_tb, n_h)) != CARRY_ON) {
2404 p_s_tb->insert_size[n_h + 1] = 0; 2472 goto repeat; /* No disk space, or schedule occurred and
2405 } 2473 analysis may be invalid and needs to be redone. */
2406 else 2474 }
2407 p_s_tb->insert_size[n_h + 1] = (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1); 2475
2408 } 2476 if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h)) {
2409 2477 /* We have a positive insert size but no nodes exist on this
2410 if ((n_ret_value = wait_tb_buffers_until_unlocked (p_s_tb)) == CARRY_ON) { 2478 level, this means that we are creating a new root. */
2411 if (FILESYSTEM_CHANGED_TB(p_s_tb)) { 2479
2412 wait_tb_buffers_run = 1 ; 2480 RFALSE(p_s_tb->blknum[n_h] != 1,
2413 n_ret_value = REPEAT_SEARCH ; 2481 "PAP-8350: creating new empty root");
2414 goto repeat; 2482
2415 } else { 2483 if (n_h < MAX_HEIGHT - 1)
2416 return CARRY_ON; 2484 p_s_tb->insert_size[n_h + 1] = 0;
2485 } else if (!PATH_H_PBUFFER(p_s_tb->tb_path, n_h + 1)) {
2486 if (p_s_tb->blknum[n_h] > 1) {
2487 /* The tree needs to be grown, so this node S[n_h]
2488 which is the root node is split into two nodes,
2489 and a new node (S[n_h+1]) will be created to
2490 become the root node. */
2491
2492 RFALSE(n_h == MAX_HEIGHT - 1,
2493 "PAP-8355: attempt to create too high of a tree");
2494
2495 p_s_tb->insert_size[n_h + 1] =
2496 (DC_SIZE +
2497 KEY_SIZE) * (p_s_tb->blknum[n_h] - 1) +
2498 DC_SIZE;
2499 } else if (n_h < MAX_HEIGHT - 1)
2500 p_s_tb->insert_size[n_h + 1] = 0;
2501 } else
2502 p_s_tb->insert_size[n_h + 1] =
2503 (DC_SIZE + KEY_SIZE) * (p_s_tb->blknum[n_h] - 1);
2417 } 2504 }
2418 } else {
2419 wait_tb_buffers_run = 1 ;
2420 goto repeat;
2421 }
2422
2423 repeat:
2424 // fix_nodes was unable to perform its calculation due to
2425 // filesystem got changed under us, lack of free disk space or i/o
2426 // failure. If the first is the case - the search will be
2427 // repeated. For now - free all resources acquired so far except
2428 // for the new allocated nodes
2429 {
2430 int i;
2431 2505
2432 /* Release path buffers. */ 2506 if ((n_ret_value = wait_tb_buffers_until_unlocked(p_s_tb)) == CARRY_ON) {
2433 if (wait_tb_buffers_run) { 2507 if (FILESYSTEM_CHANGED_TB(p_s_tb)) {
2434 pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path) ; 2508 wait_tb_buffers_run = 1;
2509 n_ret_value = REPEAT_SEARCH;
2510 goto repeat;
2511 } else {
2512 return CARRY_ON;
2513 }
2435 } else { 2514 } else {
2436 pathrelse (p_s_tb->tb_path); 2515 wait_tb_buffers_run = 1;
2437 } 2516 goto repeat;
2438 /* brelse all resources collected for balancing */
2439 for ( i = 0; i < MAX_HEIGHT; i++ ) {
2440 if (wait_tb_buffers_run) {
2441 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->L[i]);
2442 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->R[i]);
2443 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->FL[i]);
2444 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->FR[i]);
2445 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->CFL[i]);
2446 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, p_s_tb->CFR[i]);
2447 }
2448
2449 brelse (p_s_tb->L[i]);p_s_tb->L[i] = NULL;
2450 brelse (p_s_tb->R[i]);p_s_tb->R[i] = NULL;
2451 brelse (p_s_tb->FL[i]);p_s_tb->FL[i] = NULL;
2452 brelse (p_s_tb->FR[i]);p_s_tb->FR[i] = NULL;
2453 brelse (p_s_tb->CFL[i]);p_s_tb->CFL[i] = NULL;
2454 brelse (p_s_tb->CFR[i]);p_s_tb->CFR[i] = NULL;
2455 } 2517 }
2456 2518
2457 if (wait_tb_buffers_run) { 2519 repeat:
2458 for ( i = 0; i < MAX_FEB_SIZE; i++ ) { 2520 // fix_nodes was unable to perform its calculation due to
2459 if ( p_s_tb->FEB[i] ) { 2521 // filesystem got changed under us, lack of free disk space or i/o
2460 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb, 2522 // failure. If the first is the case - the search will be
2461 p_s_tb->FEB[i]) ; 2523 // repeated. For now - free all resources acquired so far except
2524 // for the new allocated nodes
2525 {
2526 int i;
2527
2528 /* Release path buffers. */
2529 if (wait_tb_buffers_run) {
2530 pathrelse_and_restore(p_s_tb->tb_sb, p_s_tb->tb_path);
2531 } else {
2532 pathrelse(p_s_tb->tb_path);
2533 }
2534 /* brelse all resources collected for balancing */
2535 for (i = 0; i < MAX_HEIGHT; i++) {
2536 if (wait_tb_buffers_run) {
2537 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2538 p_s_tb->L[i]);
2539 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2540 p_s_tb->R[i]);
2541 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2542 p_s_tb->FL[i]);
2543 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2544 p_s_tb->FR[i]);
2545 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2546 p_s_tb->
2547 CFL[i]);
2548 reiserfs_restore_prepared_buffer(p_s_tb->tb_sb,
2549 p_s_tb->
2550 CFR[i]);
2551 }
2552
2553 brelse(p_s_tb->L[i]);
2554 p_s_tb->L[i] = NULL;
2555 brelse(p_s_tb->R[i]);
2556 p_s_tb->R[i] = NULL;
2557 brelse(p_s_tb->FL[i]);
2558 p_s_tb->FL[i] = NULL;
2559 brelse(p_s_tb->FR[i]);
2560 p_s_tb->FR[i] = NULL;
2561 brelse(p_s_tb->CFL[i]);
2562 p_s_tb->CFL[i] = NULL;
2563 brelse(p_s_tb->CFR[i]);
2564 p_s_tb->CFR[i] = NULL;
2565 }
2566
2567 if (wait_tb_buffers_run) {
2568 for (i = 0; i < MAX_FEB_SIZE; i++) {
2569 if (p_s_tb->FEB[i]) {
2570 reiserfs_restore_prepared_buffer
2571 (p_s_tb->tb_sb, p_s_tb->FEB[i]);
2572 }
2573 }
2462 } 2574 }
2463 } 2575 return n_ret_value;
2464 } 2576 }
2465 return n_ret_value;
2466 }
2467 2577
2468} 2578}
2469 2579
2470
2471/* Anatoly will probably forgive me renaming p_s_tb to tb. I just 2580/* Anatoly will probably forgive me renaming p_s_tb to tb. I just
2472 wanted to make lines shorter */ 2581 wanted to make lines shorter */
2473void unfix_nodes (struct tree_balance * tb) 2582void unfix_nodes(struct tree_balance *tb)
2474{ 2583{
2475 int i; 2584 int i;
2476
2477 /* Release path buffers. */
2478 pathrelse_and_restore (tb->tb_sb, tb->tb_path);
2479
2480 /* brelse all resources collected for balancing */
2481 for ( i = 0; i < MAX_HEIGHT; i++ ) {
2482 reiserfs_restore_prepared_buffer (tb->tb_sb, tb->L[i]);
2483 reiserfs_restore_prepared_buffer (tb->tb_sb, tb->R[i]);
2484 reiserfs_restore_prepared_buffer (tb->tb_sb, tb->FL[i]);
2485 reiserfs_restore_prepared_buffer (tb->tb_sb, tb->FR[i]);
2486 reiserfs_restore_prepared_buffer (tb->tb_sb, tb->CFL[i]);
2487 reiserfs_restore_prepared_buffer (tb->tb_sb, tb->CFR[i]);
2488
2489 brelse (tb->L[i]);
2490 brelse (tb->R[i]);
2491 brelse (tb->FL[i]);
2492 brelse (tb->FR[i]);
2493 brelse (tb->CFL[i]);
2494 brelse (tb->CFR[i]);
2495 }
2496
2497 /* deal with list of allocated (used and unused) nodes */
2498 for ( i = 0; i < MAX_FEB_SIZE; i++ ) {
2499 if ( tb->FEB[i] ) {
2500 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr ;
2501 /* de-allocated block which was not used by balancing and
2502 bforget about buffer for it */
2503 brelse (tb->FEB[i]);
2504 reiserfs_free_block (tb->transaction_handle, NULL, blocknr, 0);
2505 }
2506 if (tb->used[i]) {
2507 /* release used as new nodes including a new root */
2508 brelse (tb->used[i]);
2509 }
2510 }
2511 2585
2512 if (tb->vn_buf) 2586 /* Release path buffers. */
2513 reiserfs_kfree (tb->vn_buf, tb->vn_buf_size, tb->tb_sb); 2587 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2514 2588
2515} 2589 /* brelse all resources collected for balancing */
2590 for (i = 0; i < MAX_HEIGHT; i++) {
2591 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2592 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2593 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2594 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2595 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2596 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
2597
2598 brelse(tb->L[i]);
2599 brelse(tb->R[i]);
2600 brelse(tb->FL[i]);
2601 brelse(tb->FR[i]);
2602 brelse(tb->CFL[i]);
2603 brelse(tb->CFR[i]);
2604 }
2516 2605
2606 /* deal with list of allocated (used and unused) nodes */
2607 for (i = 0; i < MAX_FEB_SIZE; i++) {
2608 if (tb->FEB[i]) {
2609 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2610 /* de-allocated block which was not used by balancing and
2611 bforget about buffer for it */
2612 brelse(tb->FEB[i]);
2613 reiserfs_free_block(tb->transaction_handle, NULL,
2614 blocknr, 0);
2615 }
2616 if (tb->used[i]) {
2617 /* release used as new nodes including a new root */
2618 brelse(tb->used[i]);
2619 }
2620 }
2517 2621
2622 if (tb->vn_buf)
2623 reiserfs_kfree(tb->vn_buf, tb->vn_buf_size, tb->tb_sb);
2518 2624
2625}
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-25 00:02:24 -0500