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