aboutsummaryrefslogtreecommitdiffstats
path: root/fs/nilfs2/btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/nilfs2/btree.c')
-rw-r--r--fs/nilfs2/btree.c914
1 files changed, 507 insertions, 407 deletions
diff --git a/fs/nilfs2/btree.c b/fs/nilfs2/btree.c
index b27a342c5af6..300c2bc00c3f 100644
--- a/fs/nilfs2/btree.c
+++ b/fs/nilfs2/btree.c
@@ -66,30 +66,10 @@ static void nilfs_btree_free_path(struct nilfs_btree_path *path)
66/* 66/*
67 * B-tree node operations 67 * B-tree node operations
68 */ 68 */
69static int nilfs_btree_get_block(const struct nilfs_btree *btree, __u64 ptr, 69static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
70 struct buffer_head **bhp)
71{
72 struct address_space *btnc =
73 &NILFS_BMAP_I((struct nilfs_bmap *)btree)->i_btnode_cache;
74 int err;
75
76 err = nilfs_btnode_submit_block(btnc, ptr, 0, bhp);
77 if (err)
78 return err == -EEXIST ? 0 : err;
79
80 wait_on_buffer(*bhp);
81 if (!buffer_uptodate(*bhp)) {
82 brelse(*bhp);
83 return -EIO;
84 }
85 return 0;
86}
87
88static int nilfs_btree_get_new_block(const struct nilfs_btree *btree,
89 __u64 ptr, struct buffer_head **bhp) 70 __u64 ptr, struct buffer_head **bhp)
90{ 71{
91 struct address_space *btnc = 72 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
92 &NILFS_BMAP_I((struct nilfs_bmap *)btree)->i_btnode_cache;
93 struct buffer_head *bh; 73 struct buffer_head *bh;
94 74
95 bh = nilfs_btnode_create_block(btnc, ptr); 75 bh = nilfs_btnode_create_block(btnc, ptr);
@@ -101,71 +81,55 @@ static int nilfs_btree_get_new_block(const struct nilfs_btree *btree,
101 return 0; 81 return 0;
102} 82}
103 83
104static inline int 84static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
105nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
106{ 85{
107 return node->bn_flags; 86 return node->bn_flags;
108} 87}
109 88
110static inline void 89static void
111nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags) 90nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
112{ 91{
113 node->bn_flags = flags; 92 node->bn_flags = flags;
114} 93}
115 94
116static inline int nilfs_btree_node_root(const struct nilfs_btree_node *node) 95static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
117{ 96{
118 return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT; 97 return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
119} 98}
120 99
121static inline int 100static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
122nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
123{ 101{
124 return node->bn_level; 102 return node->bn_level;
125} 103}
126 104
127static inline void 105static void
128nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) 106nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
129{ 107{
130 node->bn_level = level; 108 node->bn_level = level;
131} 109}
132 110
133static inline int 111static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
134nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
135{ 112{
136 return le16_to_cpu(node->bn_nchildren); 113 return le16_to_cpu(node->bn_nchildren);
137} 114}
138 115
139static inline void 116static void
140nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren) 117nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
141{ 118{
142 node->bn_nchildren = cpu_to_le16(nchildren); 119 node->bn_nchildren = cpu_to_le16(nchildren);
143} 120}
144 121
145static inline int nilfs_btree_node_size(const struct nilfs_btree *btree) 122static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
146{ 123{
147 return 1 << btree->bt_bmap.b_inode->i_blkbits; 124 return 1 << btree->b_inode->i_blkbits;
148} 125}
149 126
150static inline int 127static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
151nilfs_btree_node_nchildren_min(const struct nilfs_btree_node *node,
152 const struct nilfs_btree *btree)
153{ 128{
154 return nilfs_btree_node_root(node) ? 129 return btree->b_nchildren_per_block;
155 NILFS_BTREE_ROOT_NCHILDREN_MIN :
156 NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
157} 130}
158 131
159static inline int 132static __le64 *
160nilfs_btree_node_nchildren_max(const struct nilfs_btree_node *node,
161 const struct nilfs_btree *btree)
162{
163 return nilfs_btree_node_root(node) ?
164 NILFS_BTREE_ROOT_NCHILDREN_MAX :
165 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree));
166}
167
168static inline __le64 *
169nilfs_btree_node_dkeys(const struct nilfs_btree_node *node) 133nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
170{ 134{
171 return (__le64 *)((char *)(node + 1) + 135 return (__le64 *)((char *)(node + 1) +
@@ -173,45 +137,40 @@ nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
173 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE)); 137 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
174} 138}
175 139
176static inline __le64 * 140static __le64 *
177nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, 141nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
178 const struct nilfs_btree *btree)
179{ 142{
180 return (__le64 *)(nilfs_btree_node_dkeys(node) + 143 return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
181 nilfs_btree_node_nchildren_max(node, btree));
182} 144}
183 145
184static inline __u64 146static __u64
185nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index) 147nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
186{ 148{
187 return nilfs_bmap_dkey_to_key(*(nilfs_btree_node_dkeys(node) + index)); 149 return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
188} 150}
189 151
190static inline void 152static void
191nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key) 153nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
192{ 154{
193 *(nilfs_btree_node_dkeys(node) + index) = nilfs_bmap_key_to_dkey(key); 155 *(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
194} 156}
195 157
196static inline __u64 158static __u64
197nilfs_btree_node_get_ptr(const struct nilfs_btree *btree, 159nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
198 const struct nilfs_btree_node *node, int index) 160 int ncmax)
199{ 161{
200 return nilfs_bmap_dptr_to_ptr(*(nilfs_btree_node_dptrs(node, btree) + 162 return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
201 index));
202} 163}
203 164
204static inline void 165static void
205nilfs_btree_node_set_ptr(struct nilfs_btree *btree, 166nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
206 struct nilfs_btree_node *node, int index, __u64 ptr) 167 int ncmax)
207{ 168{
208 *(nilfs_btree_node_dptrs(node, btree) + index) = 169 *(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
209 nilfs_bmap_ptr_to_dptr(ptr);
210} 170}
211 171
212static void nilfs_btree_node_init(struct nilfs_btree *btree, 172static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
213 struct nilfs_btree_node *node, 173 int level, int nchildren, int ncmax,
214 int flags, int level, int nchildren,
215 const __u64 *keys, const __u64 *ptrs) 174 const __u64 *keys, const __u64 *ptrs)
216{ 175{
217 __le64 *dkeys; 176 __le64 *dkeys;
@@ -223,29 +182,28 @@ static void nilfs_btree_node_init(struct nilfs_btree *btree,
223 nilfs_btree_node_set_nchildren(node, nchildren); 182 nilfs_btree_node_set_nchildren(node, nchildren);
224 183
225 dkeys = nilfs_btree_node_dkeys(node); 184 dkeys = nilfs_btree_node_dkeys(node);
226 dptrs = nilfs_btree_node_dptrs(node, btree); 185 dptrs = nilfs_btree_node_dptrs(node, ncmax);
227 for (i = 0; i < nchildren; i++) { 186 for (i = 0; i < nchildren; i++) {
228 dkeys[i] = nilfs_bmap_key_to_dkey(keys[i]); 187 dkeys[i] = cpu_to_le64(keys[i]);
229 dptrs[i] = nilfs_bmap_ptr_to_dptr(ptrs[i]); 188 dptrs[i] = cpu_to_le64(ptrs[i]);
230 } 189 }
231} 190}
232 191
233/* Assume the buffer heads corresponding to left and right are locked. */ 192/* Assume the buffer heads corresponding to left and right are locked. */
234static void nilfs_btree_node_move_left(struct nilfs_btree *btree, 193static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
235 struct nilfs_btree_node *left,
236 struct nilfs_btree_node *right, 194 struct nilfs_btree_node *right,
237 int n) 195 int n, int lncmax, int rncmax)
238{ 196{
239 __le64 *ldkeys, *rdkeys; 197 __le64 *ldkeys, *rdkeys;
240 __le64 *ldptrs, *rdptrs; 198 __le64 *ldptrs, *rdptrs;
241 int lnchildren, rnchildren; 199 int lnchildren, rnchildren;
242 200
243 ldkeys = nilfs_btree_node_dkeys(left); 201 ldkeys = nilfs_btree_node_dkeys(left);
244 ldptrs = nilfs_btree_node_dptrs(left, btree); 202 ldptrs = nilfs_btree_node_dptrs(left, lncmax);
245 lnchildren = nilfs_btree_node_get_nchildren(left); 203 lnchildren = nilfs_btree_node_get_nchildren(left);
246 204
247 rdkeys = nilfs_btree_node_dkeys(right); 205 rdkeys = nilfs_btree_node_dkeys(right);
248 rdptrs = nilfs_btree_node_dptrs(right, btree); 206 rdptrs = nilfs_btree_node_dptrs(right, rncmax);
249 rnchildren = nilfs_btree_node_get_nchildren(right); 207 rnchildren = nilfs_btree_node_get_nchildren(right);
250 208
251 memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys)); 209 memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
@@ -260,21 +218,20 @@ static void nilfs_btree_node_move_left(struct nilfs_btree *btree,
260} 218}
261 219
262/* Assume that the buffer heads corresponding to left and right are locked. */ 220/* Assume that the buffer heads corresponding to left and right are locked. */
263static void nilfs_btree_node_move_right(struct nilfs_btree *btree, 221static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
264 struct nilfs_btree_node *left,
265 struct nilfs_btree_node *right, 222 struct nilfs_btree_node *right,
266 int n) 223 int n, int lncmax, int rncmax)
267{ 224{
268 __le64 *ldkeys, *rdkeys; 225 __le64 *ldkeys, *rdkeys;
269 __le64 *ldptrs, *rdptrs; 226 __le64 *ldptrs, *rdptrs;
270 int lnchildren, rnchildren; 227 int lnchildren, rnchildren;
271 228
272 ldkeys = nilfs_btree_node_dkeys(left); 229 ldkeys = nilfs_btree_node_dkeys(left);
273 ldptrs = nilfs_btree_node_dptrs(left, btree); 230 ldptrs = nilfs_btree_node_dptrs(left, lncmax);
274 lnchildren = nilfs_btree_node_get_nchildren(left); 231 lnchildren = nilfs_btree_node_get_nchildren(left);
275 232
276 rdkeys = nilfs_btree_node_dkeys(right); 233 rdkeys = nilfs_btree_node_dkeys(right);
277 rdptrs = nilfs_btree_node_dptrs(right, btree); 234 rdptrs = nilfs_btree_node_dptrs(right, rncmax);
278 rnchildren = nilfs_btree_node_get_nchildren(right); 235 rnchildren = nilfs_btree_node_get_nchildren(right);
279 236
280 memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys)); 237 memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
@@ -289,16 +246,15 @@ static void nilfs_btree_node_move_right(struct nilfs_btree *btree,
289} 246}
290 247
291/* Assume that the buffer head corresponding to node is locked. */ 248/* Assume that the buffer head corresponding to node is locked. */
292static void nilfs_btree_node_insert(struct nilfs_btree *btree, 249static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
293 struct nilfs_btree_node *node, 250 __u64 key, __u64 ptr, int ncmax)
294 __u64 key, __u64 ptr, int index)
295{ 251{
296 __le64 *dkeys; 252 __le64 *dkeys;
297 __le64 *dptrs; 253 __le64 *dptrs;
298 int nchildren; 254 int nchildren;
299 255
300 dkeys = nilfs_btree_node_dkeys(node); 256 dkeys = nilfs_btree_node_dkeys(node);
301 dptrs = nilfs_btree_node_dptrs(node, btree); 257 dptrs = nilfs_btree_node_dptrs(node, ncmax);
302 nchildren = nilfs_btree_node_get_nchildren(node); 258 nchildren = nilfs_btree_node_get_nchildren(node);
303 if (index < nchildren) { 259 if (index < nchildren) {
304 memmove(dkeys + index + 1, dkeys + index, 260 memmove(dkeys + index + 1, dkeys + index,
@@ -306,16 +262,15 @@ static void nilfs_btree_node_insert(struct nilfs_btree *btree,
306 memmove(dptrs + index + 1, dptrs + index, 262 memmove(dptrs + index + 1, dptrs + index,
307 (nchildren - index) * sizeof(*dptrs)); 263 (nchildren - index) * sizeof(*dptrs));
308 } 264 }
309 dkeys[index] = nilfs_bmap_key_to_dkey(key); 265 dkeys[index] = cpu_to_le64(key);
310 dptrs[index] = nilfs_bmap_ptr_to_dptr(ptr); 266 dptrs[index] = cpu_to_le64(ptr);
311 nchildren++; 267 nchildren++;
312 nilfs_btree_node_set_nchildren(node, nchildren); 268 nilfs_btree_node_set_nchildren(node, nchildren);
313} 269}
314 270
315/* Assume that the buffer head corresponding to node is locked. */ 271/* Assume that the buffer head corresponding to node is locked. */
316static void nilfs_btree_node_delete(struct nilfs_btree *btree, 272static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
317 struct nilfs_btree_node *node, 273 __u64 *keyp, __u64 *ptrp, int ncmax)
318 __u64 *keyp, __u64 *ptrp, int index)
319{ 274{
320 __u64 key; 275 __u64 key;
321 __u64 ptr; 276 __u64 ptr;
@@ -324,9 +279,9 @@ static void nilfs_btree_node_delete(struct nilfs_btree *btree,
324 int nchildren; 279 int nchildren;
325 280
326 dkeys = nilfs_btree_node_dkeys(node); 281 dkeys = nilfs_btree_node_dkeys(node);
327 dptrs = nilfs_btree_node_dptrs(node, btree); 282 dptrs = nilfs_btree_node_dptrs(node, ncmax);
328 key = nilfs_bmap_dkey_to_key(dkeys[index]); 283 key = le64_to_cpu(dkeys[index]);
329 ptr = nilfs_bmap_dptr_to_ptr(dptrs[index]); 284 ptr = le64_to_cpu(dptrs[index]);
330 nchildren = nilfs_btree_node_get_nchildren(node); 285 nchildren = nilfs_btree_node_get_nchildren(node);
331 if (keyp != NULL) 286 if (keyp != NULL)
332 *keyp = key; 287 *keyp = key;
@@ -382,40 +337,92 @@ static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
382 return s == 0; 337 return s == 0;
383} 338}
384 339
385static inline struct nilfs_btree_node * 340/**
386nilfs_btree_get_root(const struct nilfs_btree *btree) 341 * nilfs_btree_node_broken - verify consistency of btree node
342 * @node: btree node block to be examined
343 * @size: node size (in bytes)
344 * @blocknr: block number
345 *
346 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
347 */
348static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
349 size_t size, sector_t blocknr)
387{ 350{
388 return (struct nilfs_btree_node *)btree->bt_bmap.b_u.u_data; 351 int level, flags, nchildren;
352 int ret = 0;
353
354 level = nilfs_btree_node_get_level(node);
355 flags = nilfs_btree_node_get_flags(node);
356 nchildren = nilfs_btree_node_get_nchildren(node);
357
358 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
359 level >= NILFS_BTREE_LEVEL_MAX ||
360 (flags & NILFS_BTREE_NODE_ROOT) ||
361 nchildren < 0 ||
362 nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
363 printk(KERN_CRIT "NILFS: bad btree node (blocknr=%llu): "
364 "level = %d, flags = 0x%x, nchildren = %d\n",
365 (unsigned long long)blocknr, level, flags, nchildren);
366 ret = 1;
367 }
368 return ret;
389} 369}
390 370
391static inline struct nilfs_btree_node * 371int nilfs_btree_broken_node_block(struct buffer_head *bh)
372{
373 int ret;
374
375 if (buffer_nilfs_checked(bh))
376 return 0;
377
378 ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
379 bh->b_size, bh->b_blocknr);
380 if (likely(!ret))
381 set_buffer_nilfs_checked(bh);
382 return ret;
383}
384
385static struct nilfs_btree_node *
386nilfs_btree_get_root(const struct nilfs_bmap *btree)
387{
388 return (struct nilfs_btree_node *)btree->b_u.u_data;
389}
390
391static struct nilfs_btree_node *
392nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) 392nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
393{ 393{
394 return (struct nilfs_btree_node *)path[level].bp_bh->b_data; 394 return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
395} 395}
396 396
397static inline struct nilfs_btree_node * 397static struct nilfs_btree_node *
398nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) 398nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
399{ 399{
400 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; 400 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
401} 401}
402 402
403static inline int nilfs_btree_height(const struct nilfs_btree *btree) 403static int nilfs_btree_height(const struct nilfs_bmap *btree)
404{ 404{
405 return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1; 405 return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
406} 406}
407 407
408static inline struct nilfs_btree_node * 408static struct nilfs_btree_node *
409nilfs_btree_get_node(const struct nilfs_btree *btree, 409nilfs_btree_get_node(const struct nilfs_bmap *btree,
410 const struct nilfs_btree_path *path, 410 const struct nilfs_btree_path *path,
411 int level) 411 int level, int *ncmaxp)
412{ 412{
413 return (level == nilfs_btree_height(btree) - 1) ? 413 struct nilfs_btree_node *node;
414 nilfs_btree_get_root(btree) : 414
415 nilfs_btree_get_nonroot_node(path, level); 415 if (level == nilfs_btree_height(btree) - 1) {
416 node = nilfs_btree_get_root(btree);
417 *ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
418 } else {
419 node = nilfs_btree_get_nonroot_node(path, level);
420 *ncmaxp = nilfs_btree_nchildren_per_block(btree);
421 }
422 return node;
416} 423}
417 424
418static inline int 425static int
419nilfs_btree_bad_node(struct nilfs_btree_node *node, int level) 426nilfs_btree_bad_node(struct nilfs_btree_node *node, int level)
420{ 427{
421 if (unlikely(nilfs_btree_node_get_level(node) != level)) { 428 if (unlikely(nilfs_btree_node_get_level(node) != level)) {
@@ -427,13 +434,83 @@ nilfs_btree_bad_node(struct nilfs_btree_node *node, int level)
427 return 0; 434 return 0;
428} 435}
429 436
430static int nilfs_btree_do_lookup(const struct nilfs_btree *btree, 437struct nilfs_btree_readahead_info {
438 struct nilfs_btree_node *node; /* parent node */
439 int max_ra_blocks; /* max nof blocks to read ahead */
440 int index; /* current index on the parent node */
441 int ncmax; /* nof children in the parent node */
442};
443
444static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
445 struct buffer_head **bhp,
446 const struct nilfs_btree_readahead_info *ra)
447{
448 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
449 struct buffer_head *bh, *ra_bh;
450 sector_t submit_ptr = 0;
451 int ret;
452
453 ret = nilfs_btnode_submit_block(btnc, ptr, 0, READ, &bh, &submit_ptr);
454 if (ret) {
455 if (ret != -EEXIST)
456 return ret;
457 goto out_check;
458 }
459
460 if (ra) {
461 int i, n;
462 __u64 ptr2;
463
464 /* read ahead sibling nodes */
465 for (n = ra->max_ra_blocks, i = ra->index + 1;
466 n > 0 && i < ra->ncmax; n--, i++) {
467 ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);
468
469 ret = nilfs_btnode_submit_block(btnc, ptr2, 0, READA,
470 &ra_bh, &submit_ptr);
471 if (likely(!ret || ret == -EEXIST))
472 brelse(ra_bh);
473 else if (ret != -EBUSY)
474 break;
475 if (!buffer_locked(bh))
476 goto out_no_wait;
477 }
478 }
479
480 wait_on_buffer(bh);
481
482 out_no_wait:
483 if (!buffer_uptodate(bh)) {
484 brelse(bh);
485 return -EIO;
486 }
487
488 out_check:
489 if (nilfs_btree_broken_node_block(bh)) {
490 clear_buffer_uptodate(bh);
491 brelse(bh);
492 return -EINVAL;
493 }
494
495 *bhp = bh;
496 return 0;
497}
498
499static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
500 struct buffer_head **bhp)
501{
502 return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
503}
504
505static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
431 struct nilfs_btree_path *path, 506 struct nilfs_btree_path *path,
432 __u64 key, __u64 *ptrp, int minlevel) 507 __u64 key, __u64 *ptrp, int minlevel,
508 int readahead)
433{ 509{
434 struct nilfs_btree_node *node; 510 struct nilfs_btree_node *node;
511 struct nilfs_btree_readahead_info p, *ra;
435 __u64 ptr; 512 __u64 ptr;
436 int level, index, found, ret; 513 int level, index, found, ncmax, ret;
437 514
438 node = nilfs_btree_get_root(btree); 515 node = nilfs_btree_get_root(btree);
439 level = nilfs_btree_node_get_level(node); 516 level = nilfs_btree_node_get_level(node);
@@ -441,14 +518,27 @@ static int nilfs_btree_do_lookup(const struct nilfs_btree *btree,
441 return -ENOENT; 518 return -ENOENT;
442 519
443 found = nilfs_btree_node_lookup(node, key, &index); 520 found = nilfs_btree_node_lookup(node, key, &index);
444 ptr = nilfs_btree_node_get_ptr(btree, node, index); 521 ptr = nilfs_btree_node_get_ptr(node, index,
522 NILFS_BTREE_ROOT_NCHILDREN_MAX);
445 path[level].bp_bh = NULL; 523 path[level].bp_bh = NULL;
446 path[level].bp_index = index; 524 path[level].bp_index = index;
447 525
448 for (level--; level >= minlevel; level--) { 526 ncmax = nilfs_btree_nchildren_per_block(btree);
449 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); 527
528 while (--level >= minlevel) {
529 ra = NULL;
530 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
531 p.node = nilfs_btree_get_node(btree, path, level + 1,
532 &p.ncmax);
533 p.index = index;
534 p.max_ra_blocks = 7;
535 ra = &p;
536 }
537 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
538 ra);
450 if (ret < 0) 539 if (ret < 0)
451 return ret; 540 return ret;
541
452 node = nilfs_btree_get_nonroot_node(path, level); 542 node = nilfs_btree_get_nonroot_node(path, level);
453 if (nilfs_btree_bad_node(node, level)) 543 if (nilfs_btree_bad_node(node, level))
454 return -EINVAL; 544 return -EINVAL;
@@ -456,9 +546,9 @@ static int nilfs_btree_do_lookup(const struct nilfs_btree *btree,
456 found = nilfs_btree_node_lookup(node, key, &index); 546 found = nilfs_btree_node_lookup(node, key, &index);
457 else 547 else
458 index = 0; 548 index = 0;
459 if (index < nilfs_btree_node_nchildren_max(node, btree)) 549 if (index < ncmax) {
460 ptr = nilfs_btree_node_get_ptr(btree, node, index); 550 ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
461 else { 551 } else {
462 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); 552 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
463 /* insert */ 553 /* insert */
464 ptr = NILFS_BMAP_INVALID_PTR; 554 ptr = NILFS_BMAP_INVALID_PTR;
@@ -474,22 +564,24 @@ static int nilfs_btree_do_lookup(const struct nilfs_btree *btree,
474 return 0; 564 return 0;
475} 565}
476 566
477static int nilfs_btree_do_lookup_last(const struct nilfs_btree *btree, 567static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
478 struct nilfs_btree_path *path, 568 struct nilfs_btree_path *path,
479 __u64 *keyp, __u64 *ptrp) 569 __u64 *keyp, __u64 *ptrp)
480{ 570{
481 struct nilfs_btree_node *node; 571 struct nilfs_btree_node *node;
482 __u64 ptr; 572 __u64 ptr;
483 int index, level, ret; 573 int index, level, ncmax, ret;
484 574
485 node = nilfs_btree_get_root(btree); 575 node = nilfs_btree_get_root(btree);
486 index = nilfs_btree_node_get_nchildren(node) - 1; 576 index = nilfs_btree_node_get_nchildren(node) - 1;
487 if (index < 0) 577 if (index < 0)
488 return -ENOENT; 578 return -ENOENT;
489 level = nilfs_btree_node_get_level(node); 579 level = nilfs_btree_node_get_level(node);
490 ptr = nilfs_btree_node_get_ptr(btree, node, index); 580 ptr = nilfs_btree_node_get_ptr(node, index,
581 NILFS_BTREE_ROOT_NCHILDREN_MAX);
491 path[level].bp_bh = NULL; 582 path[level].bp_bh = NULL;
492 path[level].bp_index = index; 583 path[level].bp_index = index;
584 ncmax = nilfs_btree_nchildren_per_block(btree);
493 585
494 for (level--; level > 0; level--) { 586 for (level--; level > 0; level--) {
495 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); 587 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
@@ -499,7 +591,7 @@ static int nilfs_btree_do_lookup_last(const struct nilfs_btree *btree,
499 if (nilfs_btree_bad_node(node, level)) 591 if (nilfs_btree_bad_node(node, level))
500 return -EINVAL; 592 return -EINVAL;
501 index = nilfs_btree_node_get_nchildren(node) - 1; 593 index = nilfs_btree_node_get_nchildren(node) - 1;
502 ptr = nilfs_btree_node_get_ptr(btree, node, index); 594 ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
503 path[level].bp_index = index; 595 path[level].bp_index = index;
504 } 596 }
505 597
@@ -511,51 +603,45 @@ static int nilfs_btree_do_lookup_last(const struct nilfs_btree *btree,
511 return 0; 603 return 0;
512} 604}
513 605
514static int nilfs_btree_lookup(const struct nilfs_bmap *bmap, 606static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
515 __u64 key, int level, __u64 *ptrp) 607 __u64 key, int level, __u64 *ptrp)
516{ 608{
517 struct nilfs_btree *btree;
518 struct nilfs_btree_path *path; 609 struct nilfs_btree_path *path;
519 __u64 ptr;
520 int ret; 610 int ret;
521 611
522 btree = (struct nilfs_btree *)bmap;
523 path = nilfs_btree_alloc_path(); 612 path = nilfs_btree_alloc_path();
524 if (path == NULL) 613 if (path == NULL)
525 return -ENOMEM; 614 return -ENOMEM;
526 615
527 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level); 616 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
528
529 if (ptrp != NULL)
530 *ptrp = ptr;
531 617
532 nilfs_btree_free_path(path); 618 nilfs_btree_free_path(path);
533 619
534 return ret; 620 return ret;
535} 621}
536 622
537static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap, 623static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
538 __u64 key, __u64 *ptrp, unsigned maxblocks) 624 __u64 key, __u64 *ptrp, unsigned maxblocks)
539{ 625{
540 struct nilfs_btree *btree = (struct nilfs_btree *)bmap;
541 struct nilfs_btree_path *path; 626 struct nilfs_btree_path *path;
542 struct nilfs_btree_node *node; 627 struct nilfs_btree_node *node;
543 struct inode *dat = NULL; 628 struct inode *dat = NULL;
544 __u64 ptr, ptr2; 629 __u64 ptr, ptr2;
545 sector_t blocknr; 630 sector_t blocknr;
546 int level = NILFS_BTREE_LEVEL_NODE_MIN; 631 int level = NILFS_BTREE_LEVEL_NODE_MIN;
547 int ret, cnt, index, maxlevel; 632 int ret, cnt, index, maxlevel, ncmax;
633 struct nilfs_btree_readahead_info p;
548 634
549 path = nilfs_btree_alloc_path(); 635 path = nilfs_btree_alloc_path();
550 if (path == NULL) 636 if (path == NULL)
551 return -ENOMEM; 637 return -ENOMEM;
552 638
553 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level); 639 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
554 if (ret < 0) 640 if (ret < 0)
555 goto out; 641 goto out;
556 642
557 if (NILFS_BMAP_USE_VBN(bmap)) { 643 if (NILFS_BMAP_USE_VBN(btree)) {
558 dat = nilfs_bmap_get_dat(bmap); 644 dat = nilfs_bmap_get_dat(btree);
559 ret = nilfs_dat_translate(dat, ptr, &blocknr); 645 ret = nilfs_dat_translate(dat, ptr, &blocknr);
560 if (ret < 0) 646 if (ret < 0)
561 goto out; 647 goto out;
@@ -566,14 +652,14 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap,
566 goto end; 652 goto end;
567 653
568 maxlevel = nilfs_btree_height(btree) - 1; 654 maxlevel = nilfs_btree_height(btree) - 1;
569 node = nilfs_btree_get_node(btree, path, level); 655 node = nilfs_btree_get_node(btree, path, level, &ncmax);
570 index = path[level].bp_index + 1; 656 index = path[level].bp_index + 1;
571 for (;;) { 657 for (;;) {
572 while (index < nilfs_btree_node_get_nchildren(node)) { 658 while (index < nilfs_btree_node_get_nchildren(node)) {
573 if (nilfs_btree_node_get_key(node, index) != 659 if (nilfs_btree_node_get_key(node, index) !=
574 key + cnt) 660 key + cnt)
575 goto end; 661 goto end;
576 ptr2 = nilfs_btree_node_get_ptr(btree, node, index); 662 ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax);
577 if (dat) { 663 if (dat) {
578 ret = nilfs_dat_translate(dat, ptr2, &blocknr); 664 ret = nilfs_dat_translate(dat, ptr2, &blocknr);
579 if (ret < 0) 665 if (ret < 0)
@@ -589,20 +675,24 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap,
589 break; 675 break;
590 676
591 /* look-up right sibling node */ 677 /* look-up right sibling node */
592 node = nilfs_btree_get_node(btree, path, level + 1); 678 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
593 index = path[level + 1].bp_index + 1; 679 p.index = path[level + 1].bp_index + 1;
594 if (index >= nilfs_btree_node_get_nchildren(node) || 680 p.max_ra_blocks = 7;
595 nilfs_btree_node_get_key(node, index) != key + cnt) 681 if (p.index >= nilfs_btree_node_get_nchildren(p.node) ||
682 nilfs_btree_node_get_key(p.node, p.index) != key + cnt)
596 break; 683 break;
597 ptr2 = nilfs_btree_node_get_ptr(btree, node, index); 684 ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax);
598 path[level + 1].bp_index = index; 685 path[level + 1].bp_index = p.index;
599 686
600 brelse(path[level].bp_bh); 687 brelse(path[level].bp_bh);
601 path[level].bp_bh = NULL; 688 path[level].bp_bh = NULL;
602 ret = nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh); 689
690 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
691 &p);
603 if (ret < 0) 692 if (ret < 0)
604 goto out; 693 goto out;
605 node = nilfs_btree_get_nonroot_node(path, level); 694 node = nilfs_btree_get_nonroot_node(path, level);
695 ncmax = nilfs_btree_nchildren_per_block(btree);
606 index = 0; 696 index = 0;
607 path[level].bp_index = index; 697 path[level].bp_index = index;
608 } 698 }
@@ -614,7 +704,7 @@ static int nilfs_btree_lookup_contig(const struct nilfs_bmap *bmap,
614 return ret; 704 return ret;
615} 705}
616 706
617static void nilfs_btree_promote_key(struct nilfs_btree *btree, 707static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
618 struct nilfs_btree_path *path, 708 struct nilfs_btree_path *path,
619 int level, __u64 key) 709 int level, __u64 key)
620{ 710{
@@ -636,16 +726,18 @@ static void nilfs_btree_promote_key(struct nilfs_btree *btree,
636 } 726 }
637} 727}
638 728
639static void nilfs_btree_do_insert(struct nilfs_btree *btree, 729static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
640 struct nilfs_btree_path *path, 730 struct nilfs_btree_path *path,
641 int level, __u64 *keyp, __u64 *ptrp) 731 int level, __u64 *keyp, __u64 *ptrp)
642{ 732{
643 struct nilfs_btree_node *node; 733 struct nilfs_btree_node *node;
734 int ncblk;
644 735
645 if (level < nilfs_btree_height(btree) - 1) { 736 if (level < nilfs_btree_height(btree) - 1) {
646 node = nilfs_btree_get_nonroot_node(path, level); 737 node = nilfs_btree_get_nonroot_node(path, level);
647 nilfs_btree_node_insert(btree, node, *keyp, *ptrp, 738 ncblk = nilfs_btree_nchildren_per_block(btree);
648 path[level].bp_index); 739 nilfs_btree_node_insert(node, path[level].bp_index,
740 *keyp, *ptrp, ncblk);
649 if (!buffer_dirty(path[level].bp_bh)) 741 if (!buffer_dirty(path[level].bp_bh))
650 nilfs_btnode_mark_dirty(path[level].bp_bh); 742 nilfs_btnode_mark_dirty(path[level].bp_bh);
651 743
@@ -655,22 +747,24 @@ static void nilfs_btree_do_insert(struct nilfs_btree *btree,
655 0)); 747 0));
656 } else { 748 } else {
657 node = nilfs_btree_get_root(btree); 749 node = nilfs_btree_get_root(btree);
658 nilfs_btree_node_insert(btree, node, *keyp, *ptrp, 750 nilfs_btree_node_insert(node, path[level].bp_index,
659 path[level].bp_index); 751 *keyp, *ptrp,
752 NILFS_BTREE_ROOT_NCHILDREN_MAX);
660 } 753 }
661} 754}
662 755
663static void nilfs_btree_carry_left(struct nilfs_btree *btree, 756static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
664 struct nilfs_btree_path *path, 757 struct nilfs_btree_path *path,
665 int level, __u64 *keyp, __u64 *ptrp) 758 int level, __u64 *keyp, __u64 *ptrp)
666{ 759{
667 struct nilfs_btree_node *node, *left; 760 struct nilfs_btree_node *node, *left;
668 int nchildren, lnchildren, n, move; 761 int nchildren, lnchildren, n, move, ncblk;
669 762
670 node = nilfs_btree_get_nonroot_node(path, level); 763 node = nilfs_btree_get_nonroot_node(path, level);
671 left = nilfs_btree_get_sib_node(path, level); 764 left = nilfs_btree_get_sib_node(path, level);
672 nchildren = nilfs_btree_node_get_nchildren(node); 765 nchildren = nilfs_btree_node_get_nchildren(node);
673 lnchildren = nilfs_btree_node_get_nchildren(left); 766 lnchildren = nilfs_btree_node_get_nchildren(left);
767 ncblk = nilfs_btree_nchildren_per_block(btree);
674 move = 0; 768 move = 0;
675 769
676 n = (nchildren + lnchildren + 1) / 2 - lnchildren; 770 n = (nchildren + lnchildren + 1) / 2 - lnchildren;
@@ -680,7 +774,7 @@ static void nilfs_btree_carry_left(struct nilfs_btree *btree,
680 move = 1; 774 move = 1;
681 } 775 }
682 776
683 nilfs_btree_node_move_left(btree, left, node, n); 777 nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
684 778
685 if (!buffer_dirty(path[level].bp_bh)) 779 if (!buffer_dirty(path[level].bp_bh))
686 nilfs_btnode_mark_dirty(path[level].bp_bh); 780 nilfs_btnode_mark_dirty(path[level].bp_bh);
@@ -705,17 +799,18 @@ static void nilfs_btree_carry_left(struct nilfs_btree *btree,
705 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); 799 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
706} 800}
707 801
708static void nilfs_btree_carry_right(struct nilfs_btree *btree, 802static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
709 struct nilfs_btree_path *path, 803 struct nilfs_btree_path *path,
710 int level, __u64 *keyp, __u64 *ptrp) 804 int level, __u64 *keyp, __u64 *ptrp)
711{ 805{
712 struct nilfs_btree_node *node, *right; 806 struct nilfs_btree_node *node, *right;
713 int nchildren, rnchildren, n, move; 807 int nchildren, rnchildren, n, move, ncblk;
714 808
715 node = nilfs_btree_get_nonroot_node(path, level); 809 node = nilfs_btree_get_nonroot_node(path, level);
716 right = nilfs_btree_get_sib_node(path, level); 810 right = nilfs_btree_get_sib_node(path, level);
717 nchildren = nilfs_btree_node_get_nchildren(node); 811 nchildren = nilfs_btree_node_get_nchildren(node);
718 rnchildren = nilfs_btree_node_get_nchildren(right); 812 rnchildren = nilfs_btree_node_get_nchildren(right);
813 ncblk = nilfs_btree_nchildren_per_block(btree);
719 move = 0; 814 move = 0;
720 815
721 n = (nchildren + rnchildren + 1) / 2 - rnchildren; 816 n = (nchildren + rnchildren + 1) / 2 - rnchildren;
@@ -725,7 +820,7 @@ static void nilfs_btree_carry_right(struct nilfs_btree *btree,
725 move = 1; 820 move = 1;
726 } 821 }
727 822
728 nilfs_btree_node_move_right(btree, node, right, n); 823 nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
729 824
730 if (!buffer_dirty(path[level].bp_bh)) 825 if (!buffer_dirty(path[level].bp_bh))
731 nilfs_btnode_mark_dirty(path[level].bp_bh); 826 nilfs_btnode_mark_dirty(path[level].bp_bh);
@@ -751,18 +846,19 @@ static void nilfs_btree_carry_right(struct nilfs_btree *btree,
751 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); 846 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
752} 847}
753 848
754static void nilfs_btree_split(struct nilfs_btree *btree, 849static void nilfs_btree_split(struct nilfs_bmap *btree,
755 struct nilfs_btree_path *path, 850 struct nilfs_btree_path *path,
756 int level, __u64 *keyp, __u64 *ptrp) 851 int level, __u64 *keyp, __u64 *ptrp)
757{ 852{
758 struct nilfs_btree_node *node, *right; 853 struct nilfs_btree_node *node, *right;
759 __u64 newkey; 854 __u64 newkey;
760 __u64 newptr; 855 __u64 newptr;
761 int nchildren, n, move; 856 int nchildren, n, move, ncblk;
762 857
763 node = nilfs_btree_get_nonroot_node(path, level); 858 node = nilfs_btree_get_nonroot_node(path, level);
764 right = nilfs_btree_get_sib_node(path, level); 859 right = nilfs_btree_get_sib_node(path, level);
765 nchildren = nilfs_btree_node_get_nchildren(node); 860 nchildren = nilfs_btree_node_get_nchildren(node);
861 ncblk = nilfs_btree_nchildren_per_block(btree);
766 move = 0; 862 move = 0;
767 863
768 n = (nchildren + 1) / 2; 864 n = (nchildren + 1) / 2;
@@ -771,7 +867,7 @@ static void nilfs_btree_split(struct nilfs_btree *btree,
771 move = 1; 867 move = 1;
772 } 868 }
773 869
774 nilfs_btree_node_move_right(btree, node, right, n); 870 nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
775 871
776 if (!buffer_dirty(path[level].bp_bh)) 872 if (!buffer_dirty(path[level].bp_bh))
777 nilfs_btnode_mark_dirty(path[level].bp_bh); 873 nilfs_btnode_mark_dirty(path[level].bp_bh);
@@ -783,8 +879,8 @@ static void nilfs_btree_split(struct nilfs_btree *btree,
783 879
784 if (move) { 880 if (move) {
785 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); 881 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
786 nilfs_btree_node_insert(btree, right, *keyp, *ptrp, 882 nilfs_btree_node_insert(right, path[level].bp_index,
787 path[level].bp_index); 883 *keyp, *ptrp, ncblk);
788 884
789 *keyp = nilfs_btree_node_get_key(right, 0); 885 *keyp = nilfs_btree_node_get_key(right, 0);
790 *ptrp = path[level].bp_newreq.bpr_ptr; 886 *ptrp = path[level].bp_newreq.bpr_ptr;
@@ -805,19 +901,21 @@ static void nilfs_btree_split(struct nilfs_btree *btree,
805 path[level + 1].bp_index++; 901 path[level + 1].bp_index++;
806} 902}
807 903
808static void nilfs_btree_grow(struct nilfs_btree *btree, 904static void nilfs_btree_grow(struct nilfs_bmap *btree,
809 struct nilfs_btree_path *path, 905 struct nilfs_btree_path *path,
810 int level, __u64 *keyp, __u64 *ptrp) 906 int level, __u64 *keyp, __u64 *ptrp)
811{ 907{
812 struct nilfs_btree_node *root, *child; 908 struct nilfs_btree_node *root, *child;
813 int n; 909 int n, ncblk;
814 910
815 root = nilfs_btree_get_root(btree); 911 root = nilfs_btree_get_root(btree);
816 child = nilfs_btree_get_sib_node(path, level); 912 child = nilfs_btree_get_sib_node(path, level);
913 ncblk = nilfs_btree_nchildren_per_block(btree);
817 914
818 n = nilfs_btree_node_get_nchildren(root); 915 n = nilfs_btree_node_get_nchildren(root);
819 916
820 nilfs_btree_node_move_right(btree, root, child, n); 917 nilfs_btree_node_move_right(root, child, n,
918 NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
821 nilfs_btree_node_set_level(root, level + 1); 919 nilfs_btree_node_set_level(root, level + 1);
822 920
823 if (!buffer_dirty(path[level].bp_sib_bh)) 921 if (!buffer_dirty(path[level].bp_sib_bh))
@@ -832,11 +930,11 @@ static void nilfs_btree_grow(struct nilfs_btree *btree,
832 *ptrp = path[level].bp_newreq.bpr_ptr; 930 *ptrp = path[level].bp_newreq.bpr_ptr;
833} 931}
834 932
835static __u64 nilfs_btree_find_near(const struct nilfs_btree *btree, 933static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
836 const struct nilfs_btree_path *path) 934 const struct nilfs_btree_path *path)
837{ 935{
838 struct nilfs_btree_node *node; 936 struct nilfs_btree_node *node;
839 int level; 937 int level, ncmax;
840 938
841 if (path == NULL) 939 if (path == NULL)
842 return NILFS_BMAP_INVALID_PTR; 940 return NILFS_BMAP_INVALID_PTR;
@@ -844,29 +942,30 @@ static __u64 nilfs_btree_find_near(const struct nilfs_btree *btree,
844 /* left sibling */ 942 /* left sibling */
845 level = NILFS_BTREE_LEVEL_NODE_MIN; 943 level = NILFS_BTREE_LEVEL_NODE_MIN;
846 if (path[level].bp_index > 0) { 944 if (path[level].bp_index > 0) {
847 node = nilfs_btree_get_node(btree, path, level); 945 node = nilfs_btree_get_node(btree, path, level, &ncmax);
848 return nilfs_btree_node_get_ptr(btree, node, 946 return nilfs_btree_node_get_ptr(node,
849 path[level].bp_index - 1); 947 path[level].bp_index - 1,
948 ncmax);
850 } 949 }
851 950
852 /* parent */ 951 /* parent */
853 level = NILFS_BTREE_LEVEL_NODE_MIN + 1; 952 level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
854 if (level <= nilfs_btree_height(btree) - 1) { 953 if (level <= nilfs_btree_height(btree) - 1) {
855 node = nilfs_btree_get_node(btree, path, level); 954 node = nilfs_btree_get_node(btree, path, level, &ncmax);
856 return nilfs_btree_node_get_ptr(btree, node, 955 return nilfs_btree_node_get_ptr(node, path[level].bp_index,
857 path[level].bp_index); 956 ncmax);
858 } 957 }
859 958
860 return NILFS_BMAP_INVALID_PTR; 959 return NILFS_BMAP_INVALID_PTR;
861} 960}
862 961
863static __u64 nilfs_btree_find_target_v(const struct nilfs_btree *btree, 962static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
864 const struct nilfs_btree_path *path, 963 const struct nilfs_btree_path *path,
865 __u64 key) 964 __u64 key)
866{ 965{
867 __u64 ptr; 966 __u64 ptr;
868 967
869 ptr = nilfs_bmap_find_target_seq(&btree->bt_bmap, key); 968 ptr = nilfs_bmap_find_target_seq(btree, key);
870 if (ptr != NILFS_BMAP_INVALID_PTR) 969 if (ptr != NILFS_BMAP_INVALID_PTR)
871 /* sequential access */ 970 /* sequential access */
872 return ptr; 971 return ptr;
@@ -877,17 +976,10 @@ static __u64 nilfs_btree_find_target_v(const struct nilfs_btree *btree,
877 return ptr; 976 return ptr;
878 } 977 }
879 /* block group */ 978 /* block group */
880 return nilfs_bmap_find_target_in_group(&btree->bt_bmap); 979 return nilfs_bmap_find_target_in_group(btree);
881}
882
883static void nilfs_btree_set_target_v(struct nilfs_btree *btree, __u64 key,
884 __u64 ptr)
885{
886 btree->bt_bmap.b_last_allocated_key = key;
887 btree->bt_bmap.b_last_allocated_ptr = ptr;
888} 980}
889 981
890static int nilfs_btree_prepare_insert(struct nilfs_btree *btree, 982static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
891 struct nilfs_btree_path *path, 983 struct nilfs_btree_path *path,
892 int *levelp, __u64 key, __u64 ptr, 984 int *levelp, __u64 key, __u64 ptr,
893 struct nilfs_bmap_stats *stats) 985 struct nilfs_bmap_stats *stats)
@@ -895,79 +987,78 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree,
895 struct buffer_head *bh; 987 struct buffer_head *bh;
896 struct nilfs_btree_node *node, *parent, *sib; 988 struct nilfs_btree_node *node, *parent, *sib;
897 __u64 sibptr; 989 __u64 sibptr;
898 int pindex, level, ret; 990 int pindex, level, ncmax, ncblk, ret;
899 struct inode *dat = NULL; 991 struct inode *dat = NULL;
900 992
901 stats->bs_nblocks = 0; 993 stats->bs_nblocks = 0;
902 level = NILFS_BTREE_LEVEL_DATA; 994 level = NILFS_BTREE_LEVEL_DATA;
903 995
904 /* allocate a new ptr for data block */ 996 /* allocate a new ptr for data block */
905 if (NILFS_BMAP_USE_VBN(&btree->bt_bmap)) { 997 if (NILFS_BMAP_USE_VBN(btree)) {
906 path[level].bp_newreq.bpr_ptr = 998 path[level].bp_newreq.bpr_ptr =
907 nilfs_btree_find_target_v(btree, path, key); 999 nilfs_btree_find_target_v(btree, path, key);
908 dat = nilfs_bmap_get_dat(&btree->bt_bmap); 1000 dat = nilfs_bmap_get_dat(btree);
909 } 1001 }
910 1002
911 ret = nilfs_bmap_prepare_alloc_ptr(&btree->bt_bmap, 1003 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
912 &path[level].bp_newreq, dat);
913 if (ret < 0) 1004 if (ret < 0)
914 goto err_out_data; 1005 goto err_out_data;
915 1006
1007 ncblk = nilfs_btree_nchildren_per_block(btree);
1008
916 for (level = NILFS_BTREE_LEVEL_NODE_MIN; 1009 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
917 level < nilfs_btree_height(btree) - 1; 1010 level < nilfs_btree_height(btree) - 1;
918 level++) { 1011 level++) {
919 node = nilfs_btree_get_nonroot_node(path, level); 1012 node = nilfs_btree_get_nonroot_node(path, level);
920 if (nilfs_btree_node_get_nchildren(node) < 1013 if (nilfs_btree_node_get_nchildren(node) < ncblk) {
921 nilfs_btree_node_nchildren_max(node, btree)) {
922 path[level].bp_op = nilfs_btree_do_insert; 1014 path[level].bp_op = nilfs_btree_do_insert;
923 stats->bs_nblocks++; 1015 stats->bs_nblocks++;
924 goto out; 1016 goto out;
925 } 1017 }
926 1018
927 parent = nilfs_btree_get_node(btree, path, level + 1); 1019 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
928 pindex = path[level + 1].bp_index; 1020 pindex = path[level + 1].bp_index;
929 1021
930 /* left sibling */ 1022 /* left sibling */
931 if (pindex > 0) { 1023 if (pindex > 0) {
932 sibptr = nilfs_btree_node_get_ptr(btree, parent, 1024 sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
933 pindex - 1); 1025 ncmax);
934 ret = nilfs_btree_get_block(btree, sibptr, &bh); 1026 ret = nilfs_btree_get_block(btree, sibptr, &bh);
935 if (ret < 0) 1027 if (ret < 0)
936 goto err_out_child_node; 1028 goto err_out_child_node;
937 sib = (struct nilfs_btree_node *)bh->b_data; 1029 sib = (struct nilfs_btree_node *)bh->b_data;
938 if (nilfs_btree_node_get_nchildren(sib) < 1030 if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
939 nilfs_btree_node_nchildren_max(sib, btree)) {
940 path[level].bp_sib_bh = bh; 1031 path[level].bp_sib_bh = bh;
941 path[level].bp_op = nilfs_btree_carry_left; 1032 path[level].bp_op = nilfs_btree_carry_left;
942 stats->bs_nblocks++; 1033 stats->bs_nblocks++;
943 goto out; 1034 goto out;
944 } else 1035 } else {
945 brelse(bh); 1036 brelse(bh);
1037 }
946 } 1038 }
947 1039
948 /* right sibling */ 1040 /* right sibling */
949 if (pindex < 1041 if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) {
950 nilfs_btree_node_get_nchildren(parent) - 1) { 1042 sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
951 sibptr = nilfs_btree_node_get_ptr(btree, parent, 1043 ncmax);
952 pindex + 1);
953 ret = nilfs_btree_get_block(btree, sibptr, &bh); 1044 ret = nilfs_btree_get_block(btree, sibptr, &bh);
954 if (ret < 0) 1045 if (ret < 0)
955 goto err_out_child_node; 1046 goto err_out_child_node;
956 sib = (struct nilfs_btree_node *)bh->b_data; 1047 sib = (struct nilfs_btree_node *)bh->b_data;
957 if (nilfs_btree_node_get_nchildren(sib) < 1048 if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
958 nilfs_btree_node_nchildren_max(sib, btree)) {
959 path[level].bp_sib_bh = bh; 1049 path[level].bp_sib_bh = bh;
960 path[level].bp_op = nilfs_btree_carry_right; 1050 path[level].bp_op = nilfs_btree_carry_right;
961 stats->bs_nblocks++; 1051 stats->bs_nblocks++;
962 goto out; 1052 goto out;
963 } else 1053 } else {
964 brelse(bh); 1054 brelse(bh);
1055 }
965 } 1056 }
966 1057
967 /* split */ 1058 /* split */
968 path[level].bp_newreq.bpr_ptr = 1059 path[level].bp_newreq.bpr_ptr =
969 path[level - 1].bp_newreq.bpr_ptr + 1; 1060 path[level - 1].bp_newreq.bpr_ptr + 1;
970 ret = nilfs_bmap_prepare_alloc_ptr(&btree->bt_bmap, 1061 ret = nilfs_bmap_prepare_alloc_ptr(btree,
971 &path[level].bp_newreq, dat); 1062 &path[level].bp_newreq, dat);
972 if (ret < 0) 1063 if (ret < 0)
973 goto err_out_child_node; 1064 goto err_out_child_node;
@@ -979,9 +1070,8 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree,
979 1070
980 stats->bs_nblocks++; 1071 stats->bs_nblocks++;
981 1072
982 nilfs_btree_node_init(btree, 1073 sib = (struct nilfs_btree_node *)bh->b_data;
983 (struct nilfs_btree_node *)bh->b_data, 1074 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);
984 0, level, 0, NULL, NULL);
985 path[level].bp_sib_bh = bh; 1075 path[level].bp_sib_bh = bh;
986 path[level].bp_op = nilfs_btree_split; 1076 path[level].bp_op = nilfs_btree_split;
987 } 1077 }
@@ -989,7 +1079,7 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree,
989 /* root */ 1079 /* root */
990 node = nilfs_btree_get_root(btree); 1080 node = nilfs_btree_get_root(btree);
991 if (nilfs_btree_node_get_nchildren(node) < 1081 if (nilfs_btree_node_get_nchildren(node) <
992 nilfs_btree_node_nchildren_max(node, btree)) { 1082 NILFS_BTREE_ROOT_NCHILDREN_MAX) {
993 path[level].bp_op = nilfs_btree_do_insert; 1083 path[level].bp_op = nilfs_btree_do_insert;
994 stats->bs_nblocks++; 1084 stats->bs_nblocks++;
995 goto out; 1085 goto out;
@@ -997,8 +1087,7 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree,
997 1087
998 /* grow */ 1088 /* grow */
999 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; 1089 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
1000 ret = nilfs_bmap_prepare_alloc_ptr(&btree->bt_bmap, 1090 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1001 &path[level].bp_newreq, dat);
1002 if (ret < 0) 1091 if (ret < 0)
1003 goto err_out_child_node; 1092 goto err_out_child_node;
1004 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, 1093 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
@@ -1006,8 +1095,8 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree,
1006 if (ret < 0) 1095 if (ret < 0)
1007 goto err_out_curr_node; 1096 goto err_out_curr_node;
1008 1097
1009 nilfs_btree_node_init(btree, (struct nilfs_btree_node *)bh->b_data, 1098 nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data,
1010 0, level, 0, NULL, NULL); 1099 0, level, 0, ncblk, NULL, NULL);
1011 path[level].bp_sib_bh = bh; 1100 path[level].bp_sib_bh = bh;
1012 path[level].bp_op = nilfs_btree_grow; 1101 path[level].bp_op = nilfs_btree_grow;
1013 1102
@@ -1024,25 +1113,22 @@ static int nilfs_btree_prepare_insert(struct nilfs_btree *btree,
1024 1113
1025 /* error */ 1114 /* error */
1026 err_out_curr_node: 1115 err_out_curr_node:
1027 nilfs_bmap_abort_alloc_ptr(&btree->bt_bmap, &path[level].bp_newreq, 1116 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1028 dat);
1029 err_out_child_node: 1117 err_out_child_node:
1030 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { 1118 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
1031 nilfs_btnode_delete(path[level].bp_sib_bh); 1119 nilfs_btnode_delete(path[level].bp_sib_bh);
1032 nilfs_bmap_abort_alloc_ptr(&btree->bt_bmap, 1120 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1033 &path[level].bp_newreq, dat);
1034 1121
1035 } 1122 }
1036 1123
1037 nilfs_bmap_abort_alloc_ptr(&btree->bt_bmap, &path[level].bp_newreq, 1124 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1038 dat);
1039 err_out_data: 1125 err_out_data:
1040 *levelp = level; 1126 *levelp = level;
1041 stats->bs_nblocks = 0; 1127 stats->bs_nblocks = 0;
1042 return ret; 1128 return ret;
1043} 1129}
1044 1130
1045static void nilfs_btree_commit_insert(struct nilfs_btree *btree, 1131static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
1046 struct nilfs_btree_path *path, 1132 struct nilfs_btree_path *path,
1047 int maxlevel, __u64 key, __u64 ptr) 1133 int maxlevel, __u64 key, __u64 ptr)
1048{ 1134{
@@ -1051,35 +1137,33 @@ static void nilfs_btree_commit_insert(struct nilfs_btree *btree,
1051 1137
1052 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr)); 1138 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1053 ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr; 1139 ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
1054 if (NILFS_BMAP_USE_VBN(&btree->bt_bmap)) { 1140 if (NILFS_BMAP_USE_VBN(btree)) {
1055 nilfs_btree_set_target_v(btree, key, ptr); 1141 nilfs_bmap_set_target_v(btree, key, ptr);
1056 dat = nilfs_bmap_get_dat(&btree->bt_bmap); 1142 dat = nilfs_bmap_get_dat(btree);
1057 } 1143 }
1058 1144
1059 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { 1145 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
1060 nilfs_bmap_commit_alloc_ptr(&btree->bt_bmap, 1146 nilfs_bmap_commit_alloc_ptr(btree,
1061 &path[level - 1].bp_newreq, dat); 1147 &path[level - 1].bp_newreq, dat);
1062 path[level].bp_op(btree, path, level, &key, &ptr); 1148 path[level].bp_op(btree, path, level, &key, &ptr);
1063 } 1149 }
1064 1150
1065 if (!nilfs_bmap_dirty(&btree->bt_bmap)) 1151 if (!nilfs_bmap_dirty(btree))
1066 nilfs_bmap_set_dirty(&btree->bt_bmap); 1152 nilfs_bmap_set_dirty(btree);
1067} 1153}
1068 1154
1069static int nilfs_btree_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr) 1155static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
1070{ 1156{
1071 struct nilfs_btree *btree;
1072 struct nilfs_btree_path *path; 1157 struct nilfs_btree_path *path;
1073 struct nilfs_bmap_stats stats; 1158 struct nilfs_bmap_stats stats;
1074 int level, ret; 1159 int level, ret;
1075 1160
1076 btree = (struct nilfs_btree *)bmap;
1077 path = nilfs_btree_alloc_path(); 1161 path = nilfs_btree_alloc_path();
1078 if (path == NULL) 1162 if (path == NULL)
1079 return -ENOMEM; 1163 return -ENOMEM;
1080 1164
1081 ret = nilfs_btree_do_lookup(btree, path, key, NULL, 1165 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1082 NILFS_BTREE_LEVEL_NODE_MIN); 1166 NILFS_BTREE_LEVEL_NODE_MIN, 0);
1083 if (ret != -ENOENT) { 1167 if (ret != -ENOENT) {
1084 if (ret == 0) 1168 if (ret == 0)
1085 ret = -EEXIST; 1169 ret = -EEXIST;
@@ -1090,23 +1174,25 @@ static int nilfs_btree_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr)
1090 if (ret < 0) 1174 if (ret < 0)
1091 goto out; 1175 goto out;
1092 nilfs_btree_commit_insert(btree, path, level, key, ptr); 1176 nilfs_btree_commit_insert(btree, path, level, key, ptr);
1093 nilfs_bmap_add_blocks(bmap, stats.bs_nblocks); 1177 nilfs_bmap_add_blocks(btree, stats.bs_nblocks);
1094 1178
1095 out: 1179 out:
1096 nilfs_btree_free_path(path); 1180 nilfs_btree_free_path(path);
1097 return ret; 1181 return ret;
1098} 1182}
1099 1183
1100static void nilfs_btree_do_delete(struct nilfs_btree *btree, 1184static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
1101 struct nilfs_btree_path *path, 1185 struct nilfs_btree_path *path,
1102 int level, __u64 *keyp, __u64 *ptrp) 1186 int level, __u64 *keyp, __u64 *ptrp)
1103{ 1187{
1104 struct nilfs_btree_node *node; 1188 struct nilfs_btree_node *node;
1189 int ncblk;
1105 1190
1106 if (level < nilfs_btree_height(btree) - 1) { 1191 if (level < nilfs_btree_height(btree) - 1) {
1107 node = nilfs_btree_get_nonroot_node(path, level); 1192 node = nilfs_btree_get_nonroot_node(path, level);
1108 nilfs_btree_node_delete(btree, node, keyp, ptrp, 1193 ncblk = nilfs_btree_nchildren_per_block(btree);
1109 path[level].bp_index); 1194 nilfs_btree_node_delete(node, path[level].bp_index,
1195 keyp, ptrp, ncblk);
1110 if (!buffer_dirty(path[level].bp_bh)) 1196 if (!buffer_dirty(path[level].bp_bh))
1111 nilfs_btnode_mark_dirty(path[level].bp_bh); 1197 nilfs_btnode_mark_dirty(path[level].bp_bh);
1112 if (path[level].bp_index == 0) 1198 if (path[level].bp_index == 0)
@@ -1114,17 +1200,18 @@ static void nilfs_btree_do_delete(struct nilfs_btree *btree,
1114 nilfs_btree_node_get_key(node, 0)); 1200 nilfs_btree_node_get_key(node, 0));
1115 } else { 1201 } else {
1116 node = nilfs_btree_get_root(btree); 1202 node = nilfs_btree_get_root(btree);
1117 nilfs_btree_node_delete(btree, node, keyp, ptrp, 1203 nilfs_btree_node_delete(node, path[level].bp_index,
1118 path[level].bp_index); 1204 keyp, ptrp,
1205 NILFS_BTREE_ROOT_NCHILDREN_MAX);
1119 } 1206 }
1120} 1207}
1121 1208
1122static void nilfs_btree_borrow_left(struct nilfs_btree *btree, 1209static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
1123 struct nilfs_btree_path *path, 1210 struct nilfs_btree_path *path,
1124 int level, __u64 *keyp, __u64 *ptrp) 1211 int level, __u64 *keyp, __u64 *ptrp)
1125{ 1212{
1126 struct nilfs_btree_node *node, *left; 1213 struct nilfs_btree_node *node, *left;
1127 int nchildren, lnchildren, n; 1214 int nchildren, lnchildren, n, ncblk;
1128 1215
1129 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); 1216 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1130 1217
@@ -1132,10 +1219,11 @@ static void nilfs_btree_borrow_left(struct nilfs_btree *btree,
1132 left = nilfs_btree_get_sib_node(path, level); 1219 left = nilfs_btree_get_sib_node(path, level);
1133 nchildren = nilfs_btree_node_get_nchildren(node); 1220 nchildren = nilfs_btree_node_get_nchildren(node);
1134 lnchildren = nilfs_btree_node_get_nchildren(left); 1221 lnchildren = nilfs_btree_node_get_nchildren(left);
1222 ncblk = nilfs_btree_nchildren_per_block(btree);
1135 1223
1136 n = (nchildren + lnchildren) / 2 - nchildren; 1224 n = (nchildren + lnchildren) / 2 - nchildren;
1137 1225
1138 nilfs_btree_node_move_right(btree, left, node, n); 1226 nilfs_btree_node_move_right(left, node, n, ncblk, ncblk);
1139 1227
1140 if (!buffer_dirty(path[level].bp_bh)) 1228 if (!buffer_dirty(path[level].bp_bh))
1141 nilfs_btnode_mark_dirty(path[level].bp_bh); 1229 nilfs_btnode_mark_dirty(path[level].bp_bh);
@@ -1150,12 +1238,12 @@ static void nilfs_btree_borrow_left(struct nilfs_btree *btree,
1150 path[level].bp_index += n; 1238 path[level].bp_index += n;
1151} 1239}
1152 1240
1153static void nilfs_btree_borrow_right(struct nilfs_btree *btree, 1241static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
1154 struct nilfs_btree_path *path, 1242 struct nilfs_btree_path *path,
1155 int level, __u64 *keyp, __u64 *ptrp) 1243 int level, __u64 *keyp, __u64 *ptrp)
1156{ 1244{
1157 struct nilfs_btree_node *node, *right; 1245 struct nilfs_btree_node *node, *right;
1158 int nchildren, rnchildren, n; 1246 int nchildren, rnchildren, n, ncblk;
1159 1247
1160 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); 1248 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1161 1249
@@ -1163,10 +1251,11 @@ static void nilfs_btree_borrow_right(struct nilfs_btree *btree,
1163 right = nilfs_btree_get_sib_node(path, level); 1251 right = nilfs_btree_get_sib_node(path, level);
1164 nchildren = nilfs_btree_node_get_nchildren(node); 1252 nchildren = nilfs_btree_node_get_nchildren(node);
1165 rnchildren = nilfs_btree_node_get_nchildren(right); 1253 rnchildren = nilfs_btree_node_get_nchildren(right);
1254 ncblk = nilfs_btree_nchildren_per_block(btree);
1166 1255
1167 n = (nchildren + rnchildren) / 2 - nchildren; 1256 n = (nchildren + rnchildren) / 2 - nchildren;
1168 1257
1169 nilfs_btree_node_move_left(btree, node, right, n); 1258 nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
1170 1259
1171 if (!buffer_dirty(path[level].bp_bh)) 1260 if (!buffer_dirty(path[level].bp_bh))
1172 nilfs_btnode_mark_dirty(path[level].bp_bh); 1261 nilfs_btnode_mark_dirty(path[level].bp_bh);
@@ -1182,21 +1271,22 @@ static void nilfs_btree_borrow_right(struct nilfs_btree *btree,
1182 path[level].bp_sib_bh = NULL; 1271 path[level].bp_sib_bh = NULL;
1183} 1272}
1184 1273
1185static void nilfs_btree_concat_left(struct nilfs_btree *btree, 1274static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
1186 struct nilfs_btree_path *path, 1275 struct nilfs_btree_path *path,
1187 int level, __u64 *keyp, __u64 *ptrp) 1276 int level, __u64 *keyp, __u64 *ptrp)
1188{ 1277{
1189 struct nilfs_btree_node *node, *left; 1278 struct nilfs_btree_node *node, *left;
1190 int n; 1279 int n, ncblk;
1191 1280
1192 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); 1281 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1193 1282
1194 node = nilfs_btree_get_nonroot_node(path, level); 1283 node = nilfs_btree_get_nonroot_node(path, level);
1195 left = nilfs_btree_get_sib_node(path, level); 1284 left = nilfs_btree_get_sib_node(path, level);
1285 ncblk = nilfs_btree_nchildren_per_block(btree);
1196 1286
1197 n = nilfs_btree_node_get_nchildren(node); 1287 n = nilfs_btree_node_get_nchildren(node);
1198 1288
1199 nilfs_btree_node_move_left(btree, left, node, n); 1289 nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
1200 1290
1201 if (!buffer_dirty(path[level].bp_sib_bh)) 1291 if (!buffer_dirty(path[level].bp_sib_bh))
1202 nilfs_btnode_mark_dirty(path[level].bp_sib_bh); 1292 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
@@ -1207,21 +1297,22 @@ static void nilfs_btree_concat_left(struct nilfs_btree *btree,
1207 path[level].bp_index += nilfs_btree_node_get_nchildren(left); 1297 path[level].bp_index += nilfs_btree_node_get_nchildren(left);
1208} 1298}
1209 1299
1210static void nilfs_btree_concat_right(struct nilfs_btree *btree, 1300static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
1211 struct nilfs_btree_path *path, 1301 struct nilfs_btree_path *path,
1212 int level, __u64 *keyp, __u64 *ptrp) 1302 int level, __u64 *keyp, __u64 *ptrp)
1213{ 1303{
1214 struct nilfs_btree_node *node, *right; 1304 struct nilfs_btree_node *node, *right;
1215 int n; 1305 int n, ncblk;
1216 1306
1217 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); 1307 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1218 1308
1219 node = nilfs_btree_get_nonroot_node(path, level); 1309 node = nilfs_btree_get_nonroot_node(path, level);
1220 right = nilfs_btree_get_sib_node(path, level); 1310 right = nilfs_btree_get_sib_node(path, level);
1311 ncblk = nilfs_btree_nchildren_per_block(btree);
1221 1312
1222 n = nilfs_btree_node_get_nchildren(right); 1313 n = nilfs_btree_node_get_nchildren(right);
1223 1314
1224 nilfs_btree_node_move_left(btree, node, right, n); 1315 nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
1225 1316
1226 if (!buffer_dirty(path[level].bp_bh)) 1317 if (!buffer_dirty(path[level].bp_bh))
1227 nilfs_btnode_mark_dirty(path[level].bp_bh); 1318 nilfs_btnode_mark_dirty(path[level].bp_bh);
@@ -1231,29 +1322,32 @@ static void nilfs_btree_concat_right(struct nilfs_btree *btree,
1231 path[level + 1].bp_index++; 1322 path[level + 1].bp_index++;
1232} 1323}
1233 1324
1234static void nilfs_btree_shrink(struct nilfs_btree *btree, 1325static void nilfs_btree_shrink(struct nilfs_bmap *btree,
1235 struct nilfs_btree_path *path, 1326 struct nilfs_btree_path *path,
1236 int level, __u64 *keyp, __u64 *ptrp) 1327 int level, __u64 *keyp, __u64 *ptrp)
1237{ 1328{
1238 struct nilfs_btree_node *root, *child; 1329 struct nilfs_btree_node *root, *child;
1239 int n; 1330 int n, ncblk;
1240 1331
1241 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); 1332 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1242 1333
1243 root = nilfs_btree_get_root(btree); 1334 root = nilfs_btree_get_root(btree);
1244 child = nilfs_btree_get_nonroot_node(path, level); 1335 child = nilfs_btree_get_nonroot_node(path, level);
1336 ncblk = nilfs_btree_nchildren_per_block(btree);
1245 1337
1246 nilfs_btree_node_delete(btree, root, NULL, NULL, 0); 1338 nilfs_btree_node_delete(root, 0, NULL, NULL,
1339 NILFS_BTREE_ROOT_NCHILDREN_MAX);
1247 nilfs_btree_node_set_level(root, level); 1340 nilfs_btree_node_set_level(root, level);
1248 n = nilfs_btree_node_get_nchildren(child); 1341 n = nilfs_btree_node_get_nchildren(child);
1249 nilfs_btree_node_move_left(btree, root, child, n); 1342 nilfs_btree_node_move_left(root, child, n,
1343 NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
1250 1344
1251 nilfs_btnode_delete(path[level].bp_bh); 1345 nilfs_btnode_delete(path[level].bp_bh);
1252 path[level].bp_bh = NULL; 1346 path[level].bp_bh = NULL;
1253} 1347}
1254 1348
1255 1349
1256static int nilfs_btree_prepare_delete(struct nilfs_btree *btree, 1350static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1257 struct nilfs_btree_path *path, 1351 struct nilfs_btree_path *path,
1258 int *levelp, 1352 int *levelp,
1259 struct nilfs_bmap_stats *stats, 1353 struct nilfs_bmap_stats *stats,
@@ -1262,42 +1356,43 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree,
1262 struct buffer_head *bh; 1356 struct buffer_head *bh;
1263 struct nilfs_btree_node *node, *parent, *sib; 1357 struct nilfs_btree_node *node, *parent, *sib;
1264 __u64 sibptr; 1358 __u64 sibptr;
1265 int pindex, level, ret; 1359 int pindex, level, ncmin, ncmax, ncblk, ret;
1266 1360
1267 ret = 0; 1361 ret = 0;
1268 stats->bs_nblocks = 0; 1362 stats->bs_nblocks = 0;
1363 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1364 ncblk = nilfs_btree_nchildren_per_block(btree);
1365
1269 for (level = NILFS_BTREE_LEVEL_NODE_MIN; 1366 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
1270 level < nilfs_btree_height(btree) - 1; 1367 level < nilfs_btree_height(btree) - 1;
1271 level++) { 1368 level++) {
1272 node = nilfs_btree_get_nonroot_node(path, level); 1369 node = nilfs_btree_get_nonroot_node(path, level);
1273 path[level].bp_oldreq.bpr_ptr = 1370 path[level].bp_oldreq.bpr_ptr =
1274 nilfs_btree_node_get_ptr(btree, node, 1371 nilfs_btree_node_get_ptr(node, path[level].bp_index,
1275 path[level].bp_index); 1372 ncblk);
1276 ret = nilfs_bmap_prepare_end_ptr(&btree->bt_bmap, 1373 ret = nilfs_bmap_prepare_end_ptr(btree,
1277 &path[level].bp_oldreq, dat); 1374 &path[level].bp_oldreq, dat);
1278 if (ret < 0) 1375 if (ret < 0)
1279 goto err_out_child_node; 1376 goto err_out_child_node;
1280 1377
1281 if (nilfs_btree_node_get_nchildren(node) > 1378 if (nilfs_btree_node_get_nchildren(node) > ncmin) {
1282 nilfs_btree_node_nchildren_min(node, btree)) {
1283 path[level].bp_op = nilfs_btree_do_delete; 1379 path[level].bp_op = nilfs_btree_do_delete;
1284 stats->bs_nblocks++; 1380 stats->bs_nblocks++;
1285 goto out; 1381 goto out;
1286 } 1382 }
1287 1383
1288 parent = nilfs_btree_get_node(btree, path, level + 1); 1384 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1289 pindex = path[level + 1].bp_index; 1385 pindex = path[level + 1].bp_index;
1290 1386
1291 if (pindex > 0) { 1387 if (pindex > 0) {
1292 /* left sibling */ 1388 /* left sibling */
1293 sibptr = nilfs_btree_node_get_ptr(btree, parent, 1389 sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
1294 pindex - 1); 1390 ncmax);
1295 ret = nilfs_btree_get_block(btree, sibptr, &bh); 1391 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1296 if (ret < 0) 1392 if (ret < 0)
1297 goto err_out_curr_node; 1393 goto err_out_curr_node;
1298 sib = (struct nilfs_btree_node *)bh->b_data; 1394 sib = (struct nilfs_btree_node *)bh->b_data;
1299 if (nilfs_btree_node_get_nchildren(sib) > 1395 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
1300 nilfs_btree_node_nchildren_min(sib, btree)) {
1301 path[level].bp_sib_bh = bh; 1396 path[level].bp_sib_bh = bh;
1302 path[level].bp_op = nilfs_btree_borrow_left; 1397 path[level].bp_op = nilfs_btree_borrow_left;
1303 stats->bs_nblocks++; 1398 stats->bs_nblocks++;
@@ -1311,14 +1406,13 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree,
1311 } else if (pindex < 1406 } else if (pindex <
1312 nilfs_btree_node_get_nchildren(parent) - 1) { 1407 nilfs_btree_node_get_nchildren(parent) - 1) {
1313 /* right sibling */ 1408 /* right sibling */
1314 sibptr = nilfs_btree_node_get_ptr(btree, parent, 1409 sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
1315 pindex + 1); 1410 ncmax);
1316 ret = nilfs_btree_get_block(btree, sibptr, &bh); 1411 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1317 if (ret < 0) 1412 if (ret < 0)
1318 goto err_out_curr_node; 1413 goto err_out_curr_node;
1319 sib = (struct nilfs_btree_node *)bh->b_data; 1414 sib = (struct nilfs_btree_node *)bh->b_data;
1320 if (nilfs_btree_node_get_nchildren(sib) > 1415 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
1321 nilfs_btree_node_nchildren_min(sib, btree)) {
1322 path[level].bp_sib_bh = bh; 1416 path[level].bp_sib_bh = bh;
1323 path[level].bp_op = nilfs_btree_borrow_right; 1417 path[level].bp_op = nilfs_btree_borrow_right;
1324 stats->bs_nblocks++; 1418 stats->bs_nblocks++;
@@ -1349,10 +1443,10 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree,
1349 1443
1350 node = nilfs_btree_get_root(btree); 1444 node = nilfs_btree_get_root(btree);
1351 path[level].bp_oldreq.bpr_ptr = 1445 path[level].bp_oldreq.bpr_ptr =
1352 nilfs_btree_node_get_ptr(btree, node, path[level].bp_index); 1446 nilfs_btree_node_get_ptr(node, path[level].bp_index,
1447 NILFS_BTREE_ROOT_NCHILDREN_MAX);
1353 1448
1354 ret = nilfs_bmap_prepare_end_ptr(&btree->bt_bmap, 1449 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1355 &path[level].bp_oldreq, dat);
1356 if (ret < 0) 1450 if (ret < 0)
1357 goto err_out_child_node; 1451 goto err_out_child_node;
1358 1452
@@ -1367,75 +1461,68 @@ static int nilfs_btree_prepare_delete(struct nilfs_btree *btree,
1367 1461
1368 /* error */ 1462 /* error */
1369 err_out_curr_node: 1463 err_out_curr_node:
1370 nilfs_bmap_abort_end_ptr(&btree->bt_bmap, &path[level].bp_oldreq, dat); 1464 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1371 err_out_child_node: 1465 err_out_child_node:
1372 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { 1466 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {
1373 brelse(path[level].bp_sib_bh); 1467 brelse(path[level].bp_sib_bh);
1374 nilfs_bmap_abort_end_ptr(&btree->bt_bmap, 1468 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1375 &path[level].bp_oldreq, dat);
1376 } 1469 }
1377 *levelp = level; 1470 *levelp = level;
1378 stats->bs_nblocks = 0; 1471 stats->bs_nblocks = 0;
1379 return ret; 1472 return ret;
1380} 1473}
1381 1474
1382static void nilfs_btree_commit_delete(struct nilfs_btree *btree, 1475static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
1383 struct nilfs_btree_path *path, 1476 struct nilfs_btree_path *path,
1384 int maxlevel, struct inode *dat) 1477 int maxlevel, struct inode *dat)
1385{ 1478{
1386 int level; 1479 int level;
1387 1480
1388 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { 1481 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
1389 nilfs_bmap_commit_end_ptr(&btree->bt_bmap, 1482 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1390 &path[level].bp_oldreq, dat);
1391 path[level].bp_op(btree, path, level, NULL, NULL); 1483 path[level].bp_op(btree, path, level, NULL, NULL);
1392 } 1484 }
1393 1485
1394 if (!nilfs_bmap_dirty(&btree->bt_bmap)) 1486 if (!nilfs_bmap_dirty(btree))
1395 nilfs_bmap_set_dirty(&btree->bt_bmap); 1487 nilfs_bmap_set_dirty(btree);
1396} 1488}
1397 1489
1398static int nilfs_btree_delete(struct nilfs_bmap *bmap, __u64 key) 1490static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
1399 1491
1400{ 1492{
1401 struct nilfs_btree *btree;
1402 struct nilfs_btree_path *path; 1493 struct nilfs_btree_path *path;
1403 struct nilfs_bmap_stats stats; 1494 struct nilfs_bmap_stats stats;
1404 struct inode *dat; 1495 struct inode *dat;
1405 int level, ret; 1496 int level, ret;
1406 1497
1407 btree = (struct nilfs_btree *)bmap;
1408 path = nilfs_btree_alloc_path(); 1498 path = nilfs_btree_alloc_path();
1409 if (path == NULL) 1499 if (path == NULL)
1410 return -ENOMEM; 1500 return -ENOMEM;
1411 1501
1412 ret = nilfs_btree_do_lookup(btree, path, key, NULL, 1502 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1413 NILFS_BTREE_LEVEL_NODE_MIN); 1503 NILFS_BTREE_LEVEL_NODE_MIN, 0);
1414 if (ret < 0) 1504 if (ret < 0)
1415 goto out; 1505 goto out;
1416 1506
1417 1507
1418 dat = NILFS_BMAP_USE_VBN(&btree->bt_bmap) ? 1508 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1419 nilfs_bmap_get_dat(&btree->bt_bmap) : NULL;
1420 1509
1421 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); 1510 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1422 if (ret < 0) 1511 if (ret < 0)
1423 goto out; 1512 goto out;
1424 nilfs_btree_commit_delete(btree, path, level, dat); 1513 nilfs_btree_commit_delete(btree, path, level, dat);
1425 nilfs_bmap_sub_blocks(bmap, stats.bs_nblocks); 1514 nilfs_bmap_sub_blocks(btree, stats.bs_nblocks);
1426 1515
1427out: 1516out:
1428 nilfs_btree_free_path(path); 1517 nilfs_btree_free_path(path);
1429 return ret; 1518 return ret;
1430} 1519}
1431 1520
1432static int nilfs_btree_last_key(const struct nilfs_bmap *bmap, __u64 *keyp) 1521static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
1433{ 1522{
1434 struct nilfs_btree *btree;
1435 struct nilfs_btree_path *path; 1523 struct nilfs_btree_path *path;
1436 int ret; 1524 int ret;
1437 1525
1438 btree = (struct nilfs_btree *)bmap;
1439 path = nilfs_btree_alloc_path(); 1526 path = nilfs_btree_alloc_path();
1440 if (path == NULL) 1527 if (path == NULL)
1441 return -ENOMEM; 1528 return -ENOMEM;
@@ -1447,16 +1534,14 @@ static int nilfs_btree_last_key(const struct nilfs_bmap *bmap, __u64 *keyp)
1447 return ret; 1534 return ret;
1448} 1535}
1449 1536
1450static int nilfs_btree_check_delete(struct nilfs_bmap *bmap, __u64 key) 1537static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
1451{ 1538{
1452 struct buffer_head *bh; 1539 struct buffer_head *bh;
1453 struct nilfs_btree *btree;
1454 struct nilfs_btree_node *root, *node; 1540 struct nilfs_btree_node *root, *node;
1455 __u64 maxkey, nextmaxkey; 1541 __u64 maxkey, nextmaxkey;
1456 __u64 ptr; 1542 __u64 ptr;
1457 int nchildren, ret; 1543 int nchildren, ret;
1458 1544
1459 btree = (struct nilfs_btree *)bmap;
1460 root = nilfs_btree_get_root(btree); 1545 root = nilfs_btree_get_root(btree);
1461 switch (nilfs_btree_height(btree)) { 1546 switch (nilfs_btree_height(btree)) {
1462 case 2: 1547 case 2:
@@ -1467,7 +1552,8 @@ static int nilfs_btree_check_delete(struct nilfs_bmap *bmap, __u64 key)
1467 nchildren = nilfs_btree_node_get_nchildren(root); 1552 nchildren = nilfs_btree_node_get_nchildren(root);
1468 if (nchildren > 1) 1553 if (nchildren > 1)
1469 return 0; 1554 return 0;
1470 ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1); 1555 ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
1556 NILFS_BTREE_ROOT_NCHILDREN_MAX);
1471 ret = nilfs_btree_get_block(btree, ptr, &bh); 1557 ret = nilfs_btree_get_block(btree, ptr, &bh);
1472 if (ret < 0) 1558 if (ret < 0)
1473 return ret; 1559 return ret;
@@ -1487,32 +1573,33 @@ static int nilfs_btree_check_delete(struct nilfs_bmap *bmap, __u64 key)
1487 return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW); 1573 return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
1488} 1574}
1489 1575
1490static int nilfs_btree_gather_data(struct nilfs_bmap *bmap, 1576static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
1491 __u64 *keys, __u64 *ptrs, int nitems) 1577 __u64 *keys, __u64 *ptrs, int nitems)
1492{ 1578{
1493 struct buffer_head *bh; 1579 struct buffer_head *bh;
1494 struct nilfs_btree *btree;
1495 struct nilfs_btree_node *node, *root; 1580 struct nilfs_btree_node *node, *root;
1496 __le64 *dkeys; 1581 __le64 *dkeys;
1497 __le64 *dptrs; 1582 __le64 *dptrs;
1498 __u64 ptr; 1583 __u64 ptr;
1499 int nchildren, i, ret; 1584 int nchildren, ncmax, i, ret;
1500 1585
1501 btree = (struct nilfs_btree *)bmap;
1502 root = nilfs_btree_get_root(btree); 1586 root = nilfs_btree_get_root(btree);
1503 switch (nilfs_btree_height(btree)) { 1587 switch (nilfs_btree_height(btree)) {
1504 case 2: 1588 case 2:
1505 bh = NULL; 1589 bh = NULL;
1506 node = root; 1590 node = root;
1591 ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX;
1507 break; 1592 break;
1508 case 3: 1593 case 3:
1509 nchildren = nilfs_btree_node_get_nchildren(root); 1594 nchildren = nilfs_btree_node_get_nchildren(root);
1510 WARN_ON(nchildren > 1); 1595 WARN_ON(nchildren > 1);
1511 ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1); 1596 ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
1597 NILFS_BTREE_ROOT_NCHILDREN_MAX);
1512 ret = nilfs_btree_get_block(btree, ptr, &bh); 1598 ret = nilfs_btree_get_block(btree, ptr, &bh);
1513 if (ret < 0) 1599 if (ret < 0)
1514 return ret; 1600 return ret;
1515 node = (struct nilfs_btree_node *)bh->b_data; 1601 node = (struct nilfs_btree_node *)bh->b_data;
1602 ncmax = nilfs_btree_nchildren_per_block(btree);
1516 break; 1603 break;
1517 default: 1604 default:
1518 node = NULL; 1605 node = NULL;
@@ -1523,10 +1610,10 @@ static int nilfs_btree_gather_data(struct nilfs_bmap *bmap,
1523 if (nchildren < nitems) 1610 if (nchildren < nitems)
1524 nitems = nchildren; 1611 nitems = nchildren;
1525 dkeys = nilfs_btree_node_dkeys(node); 1612 dkeys = nilfs_btree_node_dkeys(node);
1526 dptrs = nilfs_btree_node_dptrs(node, btree); 1613 dptrs = nilfs_btree_node_dptrs(node, ncmax);
1527 for (i = 0; i < nitems; i++) { 1614 for (i = 0; i < nitems; i++) {
1528 keys[i] = nilfs_bmap_dkey_to_key(dkeys[i]); 1615 keys[i] = le64_to_cpu(dkeys[i]);
1529 ptrs[i] = nilfs_bmap_dptr_to_ptr(dptrs[i]); 1616 ptrs[i] = le64_to_cpu(dptrs[i]);
1530 } 1617 }
1531 1618
1532 if (bh != NULL) 1619 if (bh != NULL)
@@ -1536,14 +1623,13 @@ static int nilfs_btree_gather_data(struct nilfs_bmap *bmap,
1536} 1623}
1537 1624
1538static int 1625static int
1539nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *bmap, __u64 key, 1626nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
1540 union nilfs_bmap_ptr_req *dreq, 1627 union nilfs_bmap_ptr_req *dreq,
1541 union nilfs_bmap_ptr_req *nreq, 1628 union nilfs_bmap_ptr_req *nreq,
1542 struct buffer_head **bhp, 1629 struct buffer_head **bhp,
1543 struct nilfs_bmap_stats *stats) 1630 struct nilfs_bmap_stats *stats)
1544{ 1631{
1545 struct buffer_head *bh; 1632 struct buffer_head *bh;
1546 struct nilfs_btree *btree = (struct nilfs_btree *)bmap;
1547 struct inode *dat = NULL; 1633 struct inode *dat = NULL;
1548 int ret; 1634 int ret;
1549 1635
@@ -1551,12 +1637,12 @@ nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *bmap, __u64 key,
1551 1637
1552 /* for data */ 1638 /* for data */
1553 /* cannot find near ptr */ 1639 /* cannot find near ptr */
1554 if (NILFS_BMAP_USE_VBN(bmap)) { 1640 if (NILFS_BMAP_USE_VBN(btree)) {
1555 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key); 1641 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
1556 dat = nilfs_bmap_get_dat(bmap); 1642 dat = nilfs_bmap_get_dat(btree);
1557 } 1643 }
1558 1644
1559 ret = nilfs_bmap_prepare_alloc_ptr(bmap, dreq, dat); 1645 ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
1560 if (ret < 0) 1646 if (ret < 0)
1561 return ret; 1647 return ret;
1562 1648
@@ -1564,7 +1650,7 @@ nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *bmap, __u64 key,
1564 stats->bs_nblocks++; 1650 stats->bs_nblocks++;
1565 if (nreq != NULL) { 1651 if (nreq != NULL) {
1566 nreq->bpr_ptr = dreq->bpr_ptr + 1; 1652 nreq->bpr_ptr = dreq->bpr_ptr + 1;
1567 ret = nilfs_bmap_prepare_alloc_ptr(bmap, nreq, dat); 1653 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
1568 if (ret < 0) 1654 if (ret < 0)
1569 goto err_out_dreq; 1655 goto err_out_dreq;
1570 1656
@@ -1581,16 +1667,16 @@ nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *bmap, __u64 key,
1581 1667
1582 /* error */ 1668 /* error */
1583 err_out_nreq: 1669 err_out_nreq:
1584 nilfs_bmap_abort_alloc_ptr(bmap, nreq, dat); 1670 nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
1585 err_out_dreq: 1671 err_out_dreq:
1586 nilfs_bmap_abort_alloc_ptr(bmap, dreq, dat); 1672 nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
1587 stats->bs_nblocks = 0; 1673 stats->bs_nblocks = 0;
1588 return ret; 1674 return ret;
1589 1675
1590} 1676}
1591 1677
1592static void 1678static void
1593nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *bmap, 1679nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
1594 __u64 key, __u64 ptr, 1680 __u64 key, __u64 ptr,
1595 const __u64 *keys, const __u64 *ptrs, 1681 const __u64 *keys, const __u64 *ptrs,
1596 int n, 1682 int n,
@@ -1598,57 +1684,59 @@ nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *bmap,
1598 union nilfs_bmap_ptr_req *nreq, 1684 union nilfs_bmap_ptr_req *nreq,
1599 struct buffer_head *bh) 1685 struct buffer_head *bh)
1600{ 1686{
1601 struct nilfs_btree *btree = (struct nilfs_btree *)bmap;
1602 struct nilfs_btree_node *node; 1687 struct nilfs_btree_node *node;
1603 struct inode *dat; 1688 struct inode *dat;
1604 __u64 tmpptr; 1689 __u64 tmpptr;
1690 int ncblk;
1605 1691
1606 /* free resources */ 1692 /* free resources */
1607 if (bmap->b_ops->bop_clear != NULL) 1693 if (btree->b_ops->bop_clear != NULL)
1608 bmap->b_ops->bop_clear(bmap); 1694 btree->b_ops->bop_clear(btree);
1609 1695
1610 /* ptr must be a pointer to a buffer head. */ 1696 /* ptr must be a pointer to a buffer head. */
1611 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr)); 1697 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1612 1698
1613 /* convert and insert */ 1699 /* convert and insert */
1614 dat = NILFS_BMAP_USE_VBN(bmap) ? nilfs_bmap_get_dat(bmap) : NULL; 1700 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1615 nilfs_btree_init(bmap); 1701 nilfs_btree_init(btree);
1616 if (nreq != NULL) { 1702 if (nreq != NULL) {
1617 nilfs_bmap_commit_alloc_ptr(bmap, dreq, dat); 1703 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1618 nilfs_bmap_commit_alloc_ptr(bmap, nreq, dat); 1704 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
1619 1705
1620 /* create child node at level 1 */ 1706 /* create child node at level 1 */
1621 node = (struct nilfs_btree_node *)bh->b_data; 1707 node = (struct nilfs_btree_node *)bh->b_data;
1622 nilfs_btree_node_init(btree, node, 0, 1, n, keys, ptrs); 1708 ncblk = nilfs_btree_nchildren_per_block(btree);
1623 nilfs_btree_node_insert(btree, node, 1709 nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs);
1624 key, dreq->bpr_ptr, n); 1710 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk);
1625 if (!buffer_dirty(bh)) 1711 if (!buffer_dirty(bh))
1626 nilfs_btnode_mark_dirty(bh); 1712 nilfs_btnode_mark_dirty(bh);
1627 if (!nilfs_bmap_dirty(bmap)) 1713 if (!nilfs_bmap_dirty(btree))
1628 nilfs_bmap_set_dirty(bmap); 1714 nilfs_bmap_set_dirty(btree);
1629 1715
1630 brelse(bh); 1716 brelse(bh);
1631 1717
1632 /* create root node at level 2 */ 1718 /* create root node at level 2 */
1633 node = nilfs_btree_get_root(btree); 1719 node = nilfs_btree_get_root(btree);
1634 tmpptr = nreq->bpr_ptr; 1720 tmpptr = nreq->bpr_ptr;
1635 nilfs_btree_node_init(btree, node, NILFS_BTREE_NODE_ROOT, 1721 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1,
1636 2, 1, &keys[0], &tmpptr); 1722 NILFS_BTREE_ROOT_NCHILDREN_MAX,
1723 &keys[0], &tmpptr);
1637 } else { 1724 } else {
1638 nilfs_bmap_commit_alloc_ptr(bmap, dreq, dat); 1725 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1639 1726
1640 /* create root node at level 1 */ 1727 /* create root node at level 1 */
1641 node = nilfs_btree_get_root(btree); 1728 node = nilfs_btree_get_root(btree);
1642 nilfs_btree_node_init(btree, node, NILFS_BTREE_NODE_ROOT, 1729 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n,
1643 1, n, keys, ptrs); 1730 NILFS_BTREE_ROOT_NCHILDREN_MAX,
1644 nilfs_btree_node_insert(btree, node, 1731 keys, ptrs);
1645 key, dreq->bpr_ptr, n); 1732 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr,
1646 if (!nilfs_bmap_dirty(bmap)) 1733 NILFS_BTREE_ROOT_NCHILDREN_MAX);
1647 nilfs_bmap_set_dirty(bmap); 1734 if (!nilfs_bmap_dirty(btree))
1735 nilfs_bmap_set_dirty(btree);
1648 } 1736 }
1649 1737
1650 if (NILFS_BMAP_USE_VBN(bmap)) 1738 if (NILFS_BMAP_USE_VBN(btree))
1651 nilfs_btree_set_target_v(btree, key, dreq->bpr_ptr); 1739 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
1652} 1740}
1653 1741
1654/** 1742/**
@@ -1660,7 +1748,7 @@ nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *bmap,
1660 * @ptrs: 1748 * @ptrs:
1661 * @n: 1749 * @n:
1662 */ 1750 */
1663int nilfs_btree_convert_and_insert(struct nilfs_bmap *bmap, 1751int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
1664 __u64 key, __u64 ptr, 1752 __u64 key, __u64 ptr,
1665 const __u64 *keys, const __u64 *ptrs, int n) 1753 const __u64 *keys, const __u64 *ptrs, int n)
1666{ 1754{
@@ -1673,7 +1761,7 @@ int nilfs_btree_convert_and_insert(struct nilfs_bmap *bmap,
1673 di = &dreq; 1761 di = &dreq;
1674 ni = NULL; 1762 ni = NULL;
1675 } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX( 1763 } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
1676 1 << bmap->b_inode->i_blkbits)) { 1764 1 << btree->b_inode->i_blkbits)) {
1677 di = &dreq; 1765 di = &dreq;
1678 ni = &nreq; 1766 ni = &nreq;
1679 } else { 1767 } else {
@@ -1682,17 +1770,17 @@ int nilfs_btree_convert_and_insert(struct nilfs_bmap *bmap,
1682 BUG(); 1770 BUG();
1683 } 1771 }
1684 1772
1685 ret = nilfs_btree_prepare_convert_and_insert(bmap, key, di, ni, &bh, 1773 ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
1686 &stats); 1774 &stats);
1687 if (ret < 0) 1775 if (ret < 0)
1688 return ret; 1776 return ret;
1689 nilfs_btree_commit_convert_and_insert(bmap, key, ptr, keys, ptrs, n, 1777 nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
1690 di, ni, bh); 1778 di, ni, bh);
1691 nilfs_bmap_add_blocks(bmap, stats.bs_nblocks); 1779 nilfs_bmap_add_blocks(btree, stats.bs_nblocks);
1692 return 0; 1780 return 0;
1693} 1781}
1694 1782
1695static int nilfs_btree_propagate_p(struct nilfs_btree *btree, 1783static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
1696 struct nilfs_btree_path *path, 1784 struct nilfs_btree_path *path,
1697 int level, 1785 int level,
1698 struct buffer_head *bh) 1786 struct buffer_head *bh)
@@ -1704,17 +1792,17 @@ static int nilfs_btree_propagate_p(struct nilfs_btree *btree,
1704 return 0; 1792 return 0;
1705} 1793}
1706 1794
1707static int nilfs_btree_prepare_update_v(struct nilfs_btree *btree, 1795static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
1708 struct nilfs_btree_path *path, 1796 struct nilfs_btree_path *path,
1709 int level, struct inode *dat) 1797 int level, struct inode *dat)
1710{ 1798{
1711 struct nilfs_btree_node *parent; 1799 struct nilfs_btree_node *parent;
1712 int ret; 1800 int ncmax, ret;
1713 1801
1714 parent = nilfs_btree_get_node(btree, path, level + 1); 1802 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1715 path[level].bp_oldreq.bpr_ptr = 1803 path[level].bp_oldreq.bpr_ptr =
1716 nilfs_btree_node_get_ptr(btree, parent, 1804 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
1717 path[level + 1].bp_index); 1805 ncmax);
1718 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; 1806 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
1719 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, 1807 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
1720 &path[level].bp_newreq.bpr_req); 1808 &path[level].bp_newreq.bpr_req);
@@ -1726,7 +1814,7 @@ static int nilfs_btree_prepare_update_v(struct nilfs_btree *btree,
1726 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr; 1814 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
1727 path[level].bp_ctxt.bh = path[level].bp_bh; 1815 path[level].bp_ctxt.bh = path[level].bp_bh;
1728 ret = nilfs_btnode_prepare_change_key( 1816 ret = nilfs_btnode_prepare_change_key(
1729 &NILFS_BMAP_I(&btree->bt_bmap)->i_btnode_cache, 1817 &NILFS_BMAP_I(btree)->i_btnode_cache,
1730 &path[level].bp_ctxt); 1818 &path[level].bp_ctxt);
1731 if (ret < 0) { 1819 if (ret < 0) {
1732 nilfs_dat_abort_update(dat, 1820 nilfs_dat_abort_update(dat,
@@ -1739,30 +1827,31 @@ static int nilfs_btree_prepare_update_v(struct nilfs_btree *btree,
1739 return 0; 1827 return 0;
1740} 1828}
1741 1829
1742static void nilfs_btree_commit_update_v(struct nilfs_btree *btree, 1830static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
1743 struct nilfs_btree_path *path, 1831 struct nilfs_btree_path *path,
1744 int level, struct inode *dat) 1832 int level, struct inode *dat)
1745{ 1833{
1746 struct nilfs_btree_node *parent; 1834 struct nilfs_btree_node *parent;
1835 int ncmax;
1747 1836
1748 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, 1837 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
1749 &path[level].bp_newreq.bpr_req, 1838 &path[level].bp_newreq.bpr_req,
1750 btree->bt_bmap.b_ptr_type == NILFS_BMAP_PTR_VS); 1839 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
1751 1840
1752 if (buffer_nilfs_node(path[level].bp_bh)) { 1841 if (buffer_nilfs_node(path[level].bp_bh)) {
1753 nilfs_btnode_commit_change_key( 1842 nilfs_btnode_commit_change_key(
1754 &NILFS_BMAP_I(&btree->bt_bmap)->i_btnode_cache, 1843 &NILFS_BMAP_I(btree)->i_btnode_cache,
1755 &path[level].bp_ctxt); 1844 &path[level].bp_ctxt);
1756 path[level].bp_bh = path[level].bp_ctxt.bh; 1845 path[level].bp_bh = path[level].bp_ctxt.bh;
1757 } 1846 }
1758 set_buffer_nilfs_volatile(path[level].bp_bh); 1847 set_buffer_nilfs_volatile(path[level].bp_bh);
1759 1848
1760 parent = nilfs_btree_get_node(btree, path, level + 1); 1849 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1761 nilfs_btree_node_set_ptr(btree, parent, path[level + 1].bp_index, 1850 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
1762 path[level].bp_newreq.bpr_ptr); 1851 path[level].bp_newreq.bpr_ptr, ncmax);
1763} 1852}
1764 1853
1765static void nilfs_btree_abort_update_v(struct nilfs_btree *btree, 1854static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
1766 struct nilfs_btree_path *path, 1855 struct nilfs_btree_path *path,
1767 int level, struct inode *dat) 1856 int level, struct inode *dat)
1768{ 1857{
@@ -1770,11 +1859,11 @@ static void nilfs_btree_abort_update_v(struct nilfs_btree *btree,
1770 &path[level].bp_newreq.bpr_req); 1859 &path[level].bp_newreq.bpr_req);
1771 if (buffer_nilfs_node(path[level].bp_bh)) 1860 if (buffer_nilfs_node(path[level].bp_bh))
1772 nilfs_btnode_abort_change_key( 1861 nilfs_btnode_abort_change_key(
1773 &NILFS_BMAP_I(&btree->bt_bmap)->i_btnode_cache, 1862 &NILFS_BMAP_I(btree)->i_btnode_cache,
1774 &path[level].bp_ctxt); 1863 &path[level].bp_ctxt);
1775} 1864}
1776 1865
1777static int nilfs_btree_prepare_propagate_v(struct nilfs_btree *btree, 1866static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
1778 struct nilfs_btree_path *path, 1867 struct nilfs_btree_path *path,
1779 int minlevel, int *maxlevelp, 1868 int minlevel, int *maxlevelp,
1780 struct inode *dat) 1869 struct inode *dat)
@@ -1809,7 +1898,7 @@ static int nilfs_btree_prepare_propagate_v(struct nilfs_btree *btree,
1809 return ret; 1898 return ret;
1810} 1899}
1811 1900
1812static void nilfs_btree_commit_propagate_v(struct nilfs_btree *btree, 1901static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
1813 struct nilfs_btree_path *path, 1902 struct nilfs_btree_path *path,
1814 int minlevel, int maxlevel, 1903 int minlevel, int maxlevel,
1815 struct buffer_head *bh, 1904 struct buffer_head *bh,
@@ -1824,14 +1913,15 @@ static void nilfs_btree_commit_propagate_v(struct nilfs_btree *btree,
1824 nilfs_btree_commit_update_v(btree, path, level, dat); 1913 nilfs_btree_commit_update_v(btree, path, level, dat);
1825} 1914}
1826 1915
1827static int nilfs_btree_propagate_v(struct nilfs_btree *btree, 1916static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
1828 struct nilfs_btree_path *path, 1917 struct nilfs_btree_path *path,
1829 int level, struct buffer_head *bh) 1918 int level, struct buffer_head *bh)
1830{ 1919{
1831 int maxlevel = 0, ret; 1920 int maxlevel = 0, ret;
1832 struct nilfs_btree_node *parent; 1921 struct nilfs_btree_node *parent;
1833 struct inode *dat = nilfs_bmap_get_dat(&btree->bt_bmap); 1922 struct inode *dat = nilfs_bmap_get_dat(btree);
1834 __u64 ptr; 1923 __u64 ptr;
1924 int ncmax;
1835 1925
1836 get_bh(bh); 1926 get_bh(bh);
1837 path[level].bp_bh = bh; 1927 path[level].bp_bh = bh;
@@ -1841,9 +1931,10 @@ static int nilfs_btree_propagate_v(struct nilfs_btree *btree,
1841 goto out; 1931 goto out;
1842 1932
1843 if (buffer_nilfs_volatile(path[level].bp_bh)) { 1933 if (buffer_nilfs_volatile(path[level].bp_bh)) {
1844 parent = nilfs_btree_get_node(btree, path, level + 1); 1934 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1845 ptr = nilfs_btree_node_get_ptr(btree, parent, 1935 ptr = nilfs_btree_node_get_ptr(parent,
1846 path[level + 1].bp_index); 1936 path[level + 1].bp_index,
1937 ncmax);
1847 ret = nilfs_dat_mark_dirty(dat, ptr); 1938 ret = nilfs_dat_mark_dirty(dat, ptr);
1848 if (ret < 0) 1939 if (ret < 0)
1849 goto out; 1940 goto out;
@@ -1857,10 +1948,9 @@ static int nilfs_btree_propagate_v(struct nilfs_btree *btree,
1857 return ret; 1948 return ret;
1858} 1949}
1859 1950
1860static int nilfs_btree_propagate(const struct nilfs_bmap *bmap, 1951static int nilfs_btree_propagate(struct nilfs_bmap *btree,
1861 struct buffer_head *bh) 1952 struct buffer_head *bh)
1862{ 1953{
1863 struct nilfs_btree *btree;
1864 struct nilfs_btree_path *path; 1954 struct nilfs_btree_path *path;
1865 struct nilfs_btree_node *node; 1955 struct nilfs_btree_node *node;
1866 __u64 key; 1956 __u64 key;
@@ -1868,7 +1958,6 @@ static int nilfs_btree_propagate(const struct nilfs_bmap *bmap,
1868 1958
1869 WARN_ON(!buffer_dirty(bh)); 1959 WARN_ON(!buffer_dirty(bh));
1870 1960
1871 btree = (struct nilfs_btree *)bmap;
1872 path = nilfs_btree_alloc_path(); 1961 path = nilfs_btree_alloc_path();
1873 if (path == NULL) 1962 if (path == NULL)
1874 return -ENOMEM; 1963 return -ENOMEM;
@@ -1878,11 +1967,11 @@ static int nilfs_btree_propagate(const struct nilfs_bmap *bmap,
1878 key = nilfs_btree_node_get_key(node, 0); 1967 key = nilfs_btree_node_get_key(node, 0);
1879 level = nilfs_btree_node_get_level(node); 1968 level = nilfs_btree_node_get_level(node);
1880 } else { 1969 } else {
1881 key = nilfs_bmap_data_get_key(bmap, bh); 1970 key = nilfs_bmap_data_get_key(btree, bh);
1882 level = NILFS_BTREE_LEVEL_DATA; 1971 level = NILFS_BTREE_LEVEL_DATA;
1883 } 1972 }
1884 1973
1885 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1); 1974 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
1886 if (ret < 0) { 1975 if (ret < 0) {
1887 if (unlikely(ret == -ENOENT)) 1976 if (unlikely(ret == -ENOENT))
1888 printk(KERN_CRIT "%s: key = %llu, level == %d\n", 1977 printk(KERN_CRIT "%s: key = %llu, level == %d\n",
@@ -1890,7 +1979,7 @@ static int nilfs_btree_propagate(const struct nilfs_bmap *bmap,
1890 goto out; 1979 goto out;
1891 } 1980 }
1892 1981
1893 ret = NILFS_BMAP_USE_VBN(bmap) ? 1982 ret = NILFS_BMAP_USE_VBN(btree) ?
1894 nilfs_btree_propagate_v(btree, path, level, bh) : 1983 nilfs_btree_propagate_v(btree, path, level, bh) :
1895 nilfs_btree_propagate_p(btree, path, level, bh); 1984 nilfs_btree_propagate_p(btree, path, level, bh);
1896 1985
@@ -1900,13 +1989,13 @@ static int nilfs_btree_propagate(const struct nilfs_bmap *bmap,
1900 return ret; 1989 return ret;
1901} 1990}
1902 1991
1903static int nilfs_btree_propagate_gc(const struct nilfs_bmap *bmap, 1992static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
1904 struct buffer_head *bh) 1993 struct buffer_head *bh)
1905{ 1994{
1906 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(bmap), bh->b_blocknr); 1995 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
1907} 1996}
1908 1997
1909static void nilfs_btree_add_dirty_buffer(struct nilfs_btree *btree, 1998static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
1910 struct list_head *lists, 1999 struct list_head *lists,
1911 struct buffer_head *bh) 2000 struct buffer_head *bh)
1912{ 2001{
@@ -1920,6 +2009,18 @@ static void nilfs_btree_add_dirty_buffer(struct nilfs_btree *btree,
1920 node = (struct nilfs_btree_node *)bh->b_data; 2009 node = (struct nilfs_btree_node *)bh->b_data;
1921 key = nilfs_btree_node_get_key(node, 0); 2010 key = nilfs_btree_node_get_key(node, 0);
1922 level = nilfs_btree_node_get_level(node); 2011 level = nilfs_btree_node_get_level(node);
2012 if (level < NILFS_BTREE_LEVEL_NODE_MIN ||
2013 level >= NILFS_BTREE_LEVEL_MAX) {
2014 dump_stack();
2015 printk(KERN_WARNING
2016 "%s: invalid btree level: %d (key=%llu, ino=%lu, "
2017 "blocknr=%llu)\n",
2018 __func__, level, (unsigned long long)key,
2019 NILFS_BMAP_I(btree)->vfs_inode.i_ino,
2020 (unsigned long long)bh->b_blocknr);
2021 return;
2022 }
2023
1923 list_for_each(head, &lists[level]) { 2024 list_for_each(head, &lists[level]) {
1924 cbh = list_entry(head, struct buffer_head, b_assoc_buffers); 2025 cbh = list_entry(head, struct buffer_head, b_assoc_buffers);
1925 cnode = (struct nilfs_btree_node *)cbh->b_data; 2026 cnode = (struct nilfs_btree_node *)cbh->b_data;
@@ -1930,11 +2031,10 @@ static void nilfs_btree_add_dirty_buffer(struct nilfs_btree *btree,
1930 list_add_tail(&bh->b_assoc_buffers, head); 2031 list_add_tail(&bh->b_assoc_buffers, head);
1931} 2032}
1932 2033
1933static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *bmap, 2034static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
1934 struct list_head *listp) 2035 struct list_head *listp)
1935{ 2036{
1936 struct nilfs_btree *btree = (struct nilfs_btree *)bmap; 2037 struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache;
1937 struct address_space *btcache = &NILFS_BMAP_I(bmap)->i_btnode_cache;
1938 struct list_head lists[NILFS_BTREE_LEVEL_MAX]; 2038 struct list_head lists[NILFS_BTREE_LEVEL_MAX];
1939 struct pagevec pvec; 2039 struct pagevec pvec;
1940 struct buffer_head *bh, *head; 2040 struct buffer_head *bh, *head;
@@ -1968,7 +2068,7 @@ static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *bmap,
1968 list_splice_tail(&lists[level], listp); 2068 list_splice_tail(&lists[level], listp);
1969} 2069}
1970 2070
1971static int nilfs_btree_assign_p(struct nilfs_btree *btree, 2071static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
1972 struct nilfs_btree_path *path, 2072 struct nilfs_btree_path *path,
1973 int level, 2073 int level,
1974 struct buffer_head **bh, 2074 struct buffer_head **bh,
@@ -1978,38 +2078,38 @@ static int nilfs_btree_assign_p(struct nilfs_btree *btree,
1978 struct nilfs_btree_node *parent; 2078 struct nilfs_btree_node *parent;
1979 __u64 key; 2079 __u64 key;
1980 __u64 ptr; 2080 __u64 ptr;
1981 int ret; 2081 int ncmax, ret;
1982 2082
1983 parent = nilfs_btree_get_node(btree, path, level + 1); 2083 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1984 ptr = nilfs_btree_node_get_ptr(btree, parent, 2084 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
1985 path[level + 1].bp_index); 2085 ncmax);
1986 if (buffer_nilfs_node(*bh)) { 2086 if (buffer_nilfs_node(*bh)) {
1987 path[level].bp_ctxt.oldkey = ptr; 2087 path[level].bp_ctxt.oldkey = ptr;
1988 path[level].bp_ctxt.newkey = blocknr; 2088 path[level].bp_ctxt.newkey = blocknr;
1989 path[level].bp_ctxt.bh = *bh; 2089 path[level].bp_ctxt.bh = *bh;
1990 ret = nilfs_btnode_prepare_change_key( 2090 ret = nilfs_btnode_prepare_change_key(
1991 &NILFS_BMAP_I(&btree->bt_bmap)->i_btnode_cache, 2091 &NILFS_BMAP_I(btree)->i_btnode_cache,
1992 &path[level].bp_ctxt); 2092 &path[level].bp_ctxt);
1993 if (ret < 0) 2093 if (ret < 0)
1994 return ret; 2094 return ret;
1995 nilfs_btnode_commit_change_key( 2095 nilfs_btnode_commit_change_key(
1996 &NILFS_BMAP_I(&btree->bt_bmap)->i_btnode_cache, 2096 &NILFS_BMAP_I(btree)->i_btnode_cache,
1997 &path[level].bp_ctxt); 2097 &path[level].bp_ctxt);
1998 *bh = path[level].bp_ctxt.bh; 2098 *bh = path[level].bp_ctxt.bh;
1999 } 2099 }
2000 2100
2001 nilfs_btree_node_set_ptr(btree, parent, 2101 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
2002 path[level + 1].bp_index, blocknr); 2102 ncmax);
2003 2103
2004 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); 2104 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2005 /* on-disk format */ 2105 /* on-disk format */
2006 binfo->bi_dat.bi_blkoff = nilfs_bmap_key_to_dkey(key); 2106 binfo->bi_dat.bi_blkoff = cpu_to_le64(key);
2007 binfo->bi_dat.bi_level = level; 2107 binfo->bi_dat.bi_level = level;
2008 2108
2009 return 0; 2109 return 0;
2010} 2110}
2011 2111
2012static int nilfs_btree_assign_v(struct nilfs_btree *btree, 2112static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
2013 struct nilfs_btree_path *path, 2113 struct nilfs_btree_path *path,
2014 int level, 2114 int level,
2015 struct buffer_head **bh, 2115 struct buffer_head **bh,
@@ -2017,15 +2117,15 @@ static int nilfs_btree_assign_v(struct nilfs_btree *btree,
2017 union nilfs_binfo *binfo) 2117 union nilfs_binfo *binfo)
2018{ 2118{
2019 struct nilfs_btree_node *parent; 2119 struct nilfs_btree_node *parent;
2020 struct inode *dat = nilfs_bmap_get_dat(&btree->bt_bmap); 2120 struct inode *dat = nilfs_bmap_get_dat(btree);
2021 __u64 key; 2121 __u64 key;
2022 __u64 ptr; 2122 __u64 ptr;
2023 union nilfs_bmap_ptr_req req; 2123 union nilfs_bmap_ptr_req req;
2024 int ret; 2124 int ncmax, ret;
2025 2125
2026 parent = nilfs_btree_get_node(btree, path, level + 1); 2126 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2027 ptr = nilfs_btree_node_get_ptr(btree, parent, 2127 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2028 path[level + 1].bp_index); 2128 ncmax);
2029 req.bpr_ptr = ptr; 2129 req.bpr_ptr = ptr;
2030 ret = nilfs_dat_prepare_start(dat, &req.bpr_req); 2130 ret = nilfs_dat_prepare_start(dat, &req.bpr_req);
2031 if (ret < 0) 2131 if (ret < 0)
@@ -2034,24 +2134,22 @@ static int nilfs_btree_assign_v(struct nilfs_btree *btree,
2034 2134
2035 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); 2135 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2036 /* on-disk format */ 2136 /* on-disk format */
2037 binfo->bi_v.bi_vblocknr = nilfs_bmap_ptr_to_dptr(ptr); 2137 binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr);
2038 binfo->bi_v.bi_blkoff = nilfs_bmap_key_to_dkey(key); 2138 binfo->bi_v.bi_blkoff = cpu_to_le64(key);
2039 2139
2040 return 0; 2140 return 0;
2041} 2141}
2042 2142
2043static int nilfs_btree_assign(struct nilfs_bmap *bmap, 2143static int nilfs_btree_assign(struct nilfs_bmap *btree,
2044 struct buffer_head **bh, 2144 struct buffer_head **bh,
2045 sector_t blocknr, 2145 sector_t blocknr,
2046 union nilfs_binfo *binfo) 2146 union nilfs_binfo *binfo)
2047{ 2147{
2048 struct nilfs_btree *btree;
2049 struct nilfs_btree_path *path; 2148 struct nilfs_btree_path *path;
2050 struct nilfs_btree_node *node; 2149 struct nilfs_btree_node *node;
2051 __u64 key; 2150 __u64 key;
2052 int level, ret; 2151 int level, ret;
2053 2152
2054 btree = (struct nilfs_btree *)bmap;
2055 path = nilfs_btree_alloc_path(); 2153 path = nilfs_btree_alloc_path();
2056 if (path == NULL) 2154 if (path == NULL)
2057 return -ENOMEM; 2155 return -ENOMEM;
@@ -2061,17 +2159,17 @@ static int nilfs_btree_assign(struct nilfs_bmap *bmap,
2061 key = nilfs_btree_node_get_key(node, 0); 2159 key = nilfs_btree_node_get_key(node, 0);
2062 level = nilfs_btree_node_get_level(node); 2160 level = nilfs_btree_node_get_level(node);
2063 } else { 2161 } else {
2064 key = nilfs_bmap_data_get_key(bmap, *bh); 2162 key = nilfs_bmap_data_get_key(btree, *bh);
2065 level = NILFS_BTREE_LEVEL_DATA; 2163 level = NILFS_BTREE_LEVEL_DATA;
2066 } 2164 }
2067 2165
2068 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1); 2166 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2069 if (ret < 0) { 2167 if (ret < 0) {
2070 WARN_ON(ret == -ENOENT); 2168 WARN_ON(ret == -ENOENT);
2071 goto out; 2169 goto out;
2072 } 2170 }
2073 2171
2074 ret = NILFS_BMAP_USE_VBN(bmap) ? 2172 ret = NILFS_BMAP_USE_VBN(btree) ?
2075 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : 2173 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2076 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); 2174 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2077 2175
@@ -2081,7 +2179,7 @@ static int nilfs_btree_assign(struct nilfs_bmap *bmap,
2081 return ret; 2179 return ret;
2082} 2180}
2083 2181
2084static int nilfs_btree_assign_gc(struct nilfs_bmap *bmap, 2182static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
2085 struct buffer_head **bh, 2183 struct buffer_head **bh,
2086 sector_t blocknr, 2184 sector_t blocknr,
2087 union nilfs_binfo *binfo) 2185 union nilfs_binfo *binfo)
@@ -2090,7 +2188,7 @@ static int nilfs_btree_assign_gc(struct nilfs_bmap *bmap,
2090 __u64 key; 2188 __u64 key;
2091 int ret; 2189 int ret;
2092 2190
2093 ret = nilfs_dat_move(nilfs_bmap_get_dat(bmap), (*bh)->b_blocknr, 2191 ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
2094 blocknr); 2192 blocknr);
2095 if (ret < 0) 2193 if (ret < 0)
2096 return ret; 2194 return ret;
@@ -2099,29 +2197,27 @@ static int nilfs_btree_assign_gc(struct nilfs_bmap *bmap,
2099 node = (struct nilfs_btree_node *)(*bh)->b_data; 2197 node = (struct nilfs_btree_node *)(*bh)->b_data;
2100 key = nilfs_btree_node_get_key(node, 0); 2198 key = nilfs_btree_node_get_key(node, 0);
2101 } else 2199 } else
2102 key = nilfs_bmap_data_get_key(bmap, *bh); 2200 key = nilfs_bmap_data_get_key(btree, *bh);
2103 2201
2104 /* on-disk format */ 2202 /* on-disk format */
2105 binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr); 2203 binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr);
2106 binfo->bi_v.bi_blkoff = nilfs_bmap_key_to_dkey(key); 2204 binfo->bi_v.bi_blkoff = cpu_to_le64(key);
2107 2205
2108 return 0; 2206 return 0;
2109} 2207}
2110 2208
2111static int nilfs_btree_mark(struct nilfs_bmap *bmap, __u64 key, int level) 2209static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
2112{ 2210{
2113 struct buffer_head *bh; 2211 struct buffer_head *bh;
2114 struct nilfs_btree *btree;
2115 struct nilfs_btree_path *path; 2212 struct nilfs_btree_path *path;
2116 __u64 ptr; 2213 __u64 ptr;
2117 int ret; 2214 int ret;
2118 2215
2119 btree = (struct nilfs_btree *)bmap;
2120 path = nilfs_btree_alloc_path(); 2216 path = nilfs_btree_alloc_path();
2121 if (path == NULL) 2217 if (path == NULL)
2122 return -ENOMEM; 2218 return -ENOMEM;
2123 2219
2124 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1); 2220 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2125 if (ret < 0) { 2221 if (ret < 0) {
2126 WARN_ON(ret == -ENOENT); 2222 WARN_ON(ret == -ENOENT);
2127 goto out; 2223 goto out;
@@ -2135,8 +2231,8 @@ static int nilfs_btree_mark(struct nilfs_bmap *bmap, __u64 key, int level)
2135 if (!buffer_dirty(bh)) 2231 if (!buffer_dirty(bh))
2136 nilfs_btnode_mark_dirty(bh); 2232 nilfs_btnode_mark_dirty(bh);
2137 brelse(bh); 2233 brelse(bh);
2138 if (!nilfs_bmap_dirty(&btree->bt_bmap)) 2234 if (!nilfs_bmap_dirty(btree))
2139 nilfs_bmap_set_dirty(&btree->bt_bmap); 2235 nilfs_bmap_set_dirty(btree);
2140 2236
2141 out: 2237 out:
2142 nilfs_btree_free_path(path); 2238 nilfs_btree_free_path(path);
@@ -2186,10 +2282,14 @@ static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
2186int nilfs_btree_init(struct nilfs_bmap *bmap) 2282int nilfs_btree_init(struct nilfs_bmap *bmap)
2187{ 2283{
2188 bmap->b_ops = &nilfs_btree_ops; 2284 bmap->b_ops = &nilfs_btree_ops;
2285 bmap->b_nchildren_per_block =
2286 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
2189 return 0; 2287 return 0;
2190} 2288}
2191 2289
2192void nilfs_btree_init_gc(struct nilfs_bmap *bmap) 2290void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
2193{ 2291{
2194 bmap->b_ops = &nilfs_btree_ops_gc; 2292 bmap->b_ops = &nilfs_btree_ops_gc;
2293 bmap->b_nchildren_per_block =
2294 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
2195} 2295}
generated by cgit v1.2.2 (git 2.25.0) at 2025-05-02 11:03:43 -0400