2 * btree.c - NILFS B-tree.
4 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * Written by Koji Sato.
19 #include <linux/slab.h>
20 #include <linux/string.h>
21 #include <linux/errno.h>
22 #include <linux/pagevec.h>
30 static void __nilfs_btree_init(struct nilfs_bmap
*bmap
);
32 static struct nilfs_btree_path
*nilfs_btree_alloc_path(void)
34 struct nilfs_btree_path
*path
;
35 int level
= NILFS_BTREE_LEVEL_DATA
;
37 path
= kmem_cache_alloc(nilfs_btree_path_cache
, GFP_NOFS
);
41 for (; level
< NILFS_BTREE_LEVEL_MAX
; level
++) {
42 path
[level
].bp_bh
= NULL
;
43 path
[level
].bp_sib_bh
= NULL
;
44 path
[level
].bp_index
= 0;
45 path
[level
].bp_oldreq
.bpr_ptr
= NILFS_BMAP_INVALID_PTR
;
46 path
[level
].bp_newreq
.bpr_ptr
= NILFS_BMAP_INVALID_PTR
;
47 path
[level
].bp_op
= NULL
;
54 static void nilfs_btree_free_path(struct nilfs_btree_path
*path
)
56 int level
= NILFS_BTREE_LEVEL_DATA
;
58 for (; level
< NILFS_BTREE_LEVEL_MAX
; level
++)
59 brelse(path
[level
].bp_bh
);
61 kmem_cache_free(nilfs_btree_path_cache
, path
);
65 * B-tree node operations
67 static int nilfs_btree_get_new_block(const struct nilfs_bmap
*btree
,
68 __u64 ptr
, struct buffer_head
**bhp
)
70 struct address_space
*btnc
= &NILFS_BMAP_I(btree
)->i_btnode_cache
;
71 struct buffer_head
*bh
;
73 bh
= nilfs_btnode_create_block(btnc
, ptr
);
77 set_buffer_nilfs_volatile(bh
);
82 static int nilfs_btree_node_get_flags(const struct nilfs_btree_node
*node
)
84 return node
->bn_flags
;
88 nilfs_btree_node_set_flags(struct nilfs_btree_node
*node
, int flags
)
90 node
->bn_flags
= flags
;
93 static int nilfs_btree_node_root(const struct nilfs_btree_node
*node
)
95 return nilfs_btree_node_get_flags(node
) & NILFS_BTREE_NODE_ROOT
;
98 static int nilfs_btree_node_get_level(const struct nilfs_btree_node
*node
)
100 return node
->bn_level
;
104 nilfs_btree_node_set_level(struct nilfs_btree_node
*node
, int level
)
106 node
->bn_level
= level
;
109 static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node
*node
)
111 return le16_to_cpu(node
->bn_nchildren
);
115 nilfs_btree_node_set_nchildren(struct nilfs_btree_node
*node
, int nchildren
)
117 node
->bn_nchildren
= cpu_to_le16(nchildren
);
120 static int nilfs_btree_node_size(const struct nilfs_bmap
*btree
)
122 return i_blocksize(btree
->b_inode
);
125 static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap
*btree
)
127 return btree
->b_nchildren_per_block
;
131 nilfs_btree_node_dkeys(const struct nilfs_btree_node
*node
)
133 return (__le64
*)((char *)(node
+ 1) +
134 (nilfs_btree_node_root(node
) ?
135 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE
));
139 nilfs_btree_node_dptrs(const struct nilfs_btree_node
*node
, int ncmax
)
141 return (__le64
*)(nilfs_btree_node_dkeys(node
) + ncmax
);
145 nilfs_btree_node_get_key(const struct nilfs_btree_node
*node
, int index
)
147 return le64_to_cpu(*(nilfs_btree_node_dkeys(node
) + index
));
151 nilfs_btree_node_set_key(struct nilfs_btree_node
*node
, int index
, __u64 key
)
153 *(nilfs_btree_node_dkeys(node
) + index
) = cpu_to_le64(key
);
157 nilfs_btree_node_get_ptr(const struct nilfs_btree_node
*node
, int index
,
160 return le64_to_cpu(*(nilfs_btree_node_dptrs(node
, ncmax
) + index
));
164 nilfs_btree_node_set_ptr(struct nilfs_btree_node
*node
, int index
, __u64 ptr
,
167 *(nilfs_btree_node_dptrs(node
, ncmax
) + index
) = cpu_to_le64(ptr
);
170 static void nilfs_btree_node_init(struct nilfs_btree_node
*node
, int flags
,
171 int level
, int nchildren
, int ncmax
,
172 const __u64
*keys
, const __u64
*ptrs
)
178 nilfs_btree_node_set_flags(node
, flags
);
179 nilfs_btree_node_set_level(node
, level
);
180 nilfs_btree_node_set_nchildren(node
, nchildren
);
182 dkeys
= nilfs_btree_node_dkeys(node
);
183 dptrs
= nilfs_btree_node_dptrs(node
, ncmax
);
184 for (i
= 0; i
< nchildren
; i
++) {
185 dkeys
[i
] = cpu_to_le64(keys
[i
]);
186 dptrs
[i
] = cpu_to_le64(ptrs
[i
]);
190 /* Assume the buffer heads corresponding to left and right are locked. */
191 static void nilfs_btree_node_move_left(struct nilfs_btree_node
*left
,
192 struct nilfs_btree_node
*right
,
193 int n
, int lncmax
, int rncmax
)
195 __le64
*ldkeys
, *rdkeys
;
196 __le64
*ldptrs
, *rdptrs
;
197 int lnchildren
, rnchildren
;
199 ldkeys
= nilfs_btree_node_dkeys(left
);
200 ldptrs
= nilfs_btree_node_dptrs(left
, lncmax
);
201 lnchildren
= nilfs_btree_node_get_nchildren(left
);
203 rdkeys
= nilfs_btree_node_dkeys(right
);
204 rdptrs
= nilfs_btree_node_dptrs(right
, rncmax
);
205 rnchildren
= nilfs_btree_node_get_nchildren(right
);
207 memcpy(ldkeys
+ lnchildren
, rdkeys
, n
* sizeof(*rdkeys
));
208 memcpy(ldptrs
+ lnchildren
, rdptrs
, n
* sizeof(*rdptrs
));
209 memmove(rdkeys
, rdkeys
+ n
, (rnchildren
- n
) * sizeof(*rdkeys
));
210 memmove(rdptrs
, rdptrs
+ n
, (rnchildren
- n
) * sizeof(*rdptrs
));
214 nilfs_btree_node_set_nchildren(left
, lnchildren
);
215 nilfs_btree_node_set_nchildren(right
, rnchildren
);
218 /* Assume that the buffer heads corresponding to left and right are locked. */
219 static void nilfs_btree_node_move_right(struct nilfs_btree_node
*left
,
220 struct nilfs_btree_node
*right
,
221 int n
, int lncmax
, int rncmax
)
223 __le64
*ldkeys
, *rdkeys
;
224 __le64
*ldptrs
, *rdptrs
;
225 int lnchildren
, rnchildren
;
227 ldkeys
= nilfs_btree_node_dkeys(left
);
228 ldptrs
= nilfs_btree_node_dptrs(left
, lncmax
);
229 lnchildren
= nilfs_btree_node_get_nchildren(left
);
231 rdkeys
= nilfs_btree_node_dkeys(right
);
232 rdptrs
= nilfs_btree_node_dptrs(right
, rncmax
);
233 rnchildren
= nilfs_btree_node_get_nchildren(right
);
235 memmove(rdkeys
+ n
, rdkeys
, rnchildren
* sizeof(*rdkeys
));
236 memmove(rdptrs
+ n
, rdptrs
, rnchildren
* sizeof(*rdptrs
));
237 memcpy(rdkeys
, ldkeys
+ lnchildren
- n
, n
* sizeof(*rdkeys
));
238 memcpy(rdptrs
, ldptrs
+ lnchildren
- n
, n
* sizeof(*rdptrs
));
242 nilfs_btree_node_set_nchildren(left
, lnchildren
);
243 nilfs_btree_node_set_nchildren(right
, rnchildren
);
246 /* Assume that the buffer head corresponding to node is locked. */
247 static void nilfs_btree_node_insert(struct nilfs_btree_node
*node
, int index
,
248 __u64 key
, __u64 ptr
, int ncmax
)
254 dkeys
= nilfs_btree_node_dkeys(node
);
255 dptrs
= nilfs_btree_node_dptrs(node
, ncmax
);
256 nchildren
= nilfs_btree_node_get_nchildren(node
);
257 if (index
< nchildren
) {
258 memmove(dkeys
+ index
+ 1, dkeys
+ index
,
259 (nchildren
- index
) * sizeof(*dkeys
));
260 memmove(dptrs
+ index
+ 1, dptrs
+ index
,
261 (nchildren
- index
) * sizeof(*dptrs
));
263 dkeys
[index
] = cpu_to_le64(key
);
264 dptrs
[index
] = cpu_to_le64(ptr
);
266 nilfs_btree_node_set_nchildren(node
, nchildren
);
269 /* Assume that the buffer head corresponding to node is locked. */
270 static void nilfs_btree_node_delete(struct nilfs_btree_node
*node
, int index
,
271 __u64
*keyp
, __u64
*ptrp
, int ncmax
)
279 dkeys
= nilfs_btree_node_dkeys(node
);
280 dptrs
= nilfs_btree_node_dptrs(node
, ncmax
);
281 key
= le64_to_cpu(dkeys
[index
]);
282 ptr
= le64_to_cpu(dptrs
[index
]);
283 nchildren
= nilfs_btree_node_get_nchildren(node
);
289 if (index
< nchildren
- 1) {
290 memmove(dkeys
+ index
, dkeys
+ index
+ 1,
291 (nchildren
- index
- 1) * sizeof(*dkeys
));
292 memmove(dptrs
+ index
, dptrs
+ index
+ 1,
293 (nchildren
- index
- 1) * sizeof(*dptrs
));
296 nilfs_btree_node_set_nchildren(node
, nchildren
);
299 static int nilfs_btree_node_lookup(const struct nilfs_btree_node
*node
,
300 __u64 key
, int *indexp
)
303 int index
, low
, high
, s
;
307 high
= nilfs_btree_node_get_nchildren(node
) - 1;
310 while (low
<= high
) {
311 index
= (low
+ high
) / 2;
312 nkey
= nilfs_btree_node_get_key(node
, index
);
316 } else if (nkey
< key
) {
326 if (nilfs_btree_node_get_level(node
) > NILFS_BTREE_LEVEL_NODE_MIN
) {
327 if (s
> 0 && index
> 0)
339 * nilfs_btree_node_broken - verify consistency of btree node
340 * @node: btree node block to be examined
341 * @size: node size (in bytes)
342 * @inode: host inode of btree
343 * @blocknr: block number
345 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
347 static int nilfs_btree_node_broken(const struct nilfs_btree_node
*node
,
348 size_t size
, struct inode
*inode
,
351 int level
, flags
, nchildren
;
354 level
= nilfs_btree_node_get_level(node
);
355 flags
= nilfs_btree_node_get_flags(node
);
356 nchildren
= nilfs_btree_node_get_nchildren(node
);
358 if (unlikely(level
< NILFS_BTREE_LEVEL_NODE_MIN
||
359 level
>= NILFS_BTREE_LEVEL_MAX
||
360 (flags
& NILFS_BTREE_NODE_ROOT
) ||
362 nchildren
> NILFS_BTREE_NODE_NCHILDREN_MAX(size
))) {
363 nilfs_msg(inode
->i_sb
, KERN_CRIT
,
364 "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d",
365 inode
->i_ino
, (unsigned long long)blocknr
, level
,
373 * nilfs_btree_root_broken - verify consistency of btree root node
374 * @node: btree root node to be examined
375 * @inode: host inode of btree
377 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
379 static int nilfs_btree_root_broken(const struct nilfs_btree_node
*node
,
382 int level
, flags
, nchildren
;
385 level
= nilfs_btree_node_get_level(node
);
386 flags
= nilfs_btree_node_get_flags(node
);
387 nchildren
= nilfs_btree_node_get_nchildren(node
);
389 if (unlikely(level
< NILFS_BTREE_LEVEL_NODE_MIN
||
390 level
>= NILFS_BTREE_LEVEL_MAX
||
392 nchildren
> NILFS_BTREE_ROOT_NCHILDREN_MAX
)) {
393 nilfs_msg(inode
->i_sb
, KERN_CRIT
,
394 "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d",
395 inode
->i_ino
, level
, flags
, nchildren
);
401 int nilfs_btree_broken_node_block(struct buffer_head
*bh
)
406 if (buffer_nilfs_checked(bh
))
409 inode
= bh
->b_page
->mapping
->host
;
410 ret
= nilfs_btree_node_broken((struct nilfs_btree_node
*)bh
->b_data
,
411 bh
->b_size
, inode
, bh
->b_blocknr
);
413 set_buffer_nilfs_checked(bh
);
417 static struct nilfs_btree_node
*
418 nilfs_btree_get_root(const struct nilfs_bmap
*btree
)
420 return (struct nilfs_btree_node
*)btree
->b_u
.u_data
;
423 static struct nilfs_btree_node
*
424 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path
*path
, int level
)
426 return (struct nilfs_btree_node
*)path
[level
].bp_bh
->b_data
;
429 static struct nilfs_btree_node
*
430 nilfs_btree_get_sib_node(const struct nilfs_btree_path
*path
, int level
)
432 return (struct nilfs_btree_node
*)path
[level
].bp_sib_bh
->b_data
;
435 static int nilfs_btree_height(const struct nilfs_bmap
*btree
)
437 return nilfs_btree_node_get_level(nilfs_btree_get_root(btree
)) + 1;
440 static struct nilfs_btree_node
*
441 nilfs_btree_get_node(const struct nilfs_bmap
*btree
,
442 const struct nilfs_btree_path
*path
,
443 int level
, int *ncmaxp
)
445 struct nilfs_btree_node
*node
;
447 if (level
== nilfs_btree_height(btree
) - 1) {
448 node
= nilfs_btree_get_root(btree
);
449 *ncmaxp
= NILFS_BTREE_ROOT_NCHILDREN_MAX
;
451 node
= nilfs_btree_get_nonroot_node(path
, level
);
452 *ncmaxp
= nilfs_btree_nchildren_per_block(btree
);
457 static int nilfs_btree_bad_node(const struct nilfs_bmap
*btree
,
458 struct nilfs_btree_node
*node
, int level
)
460 if (unlikely(nilfs_btree_node_get_level(node
) != level
)) {
462 nilfs_msg(btree
->b_inode
->i_sb
, KERN_CRIT
,
463 "btree level mismatch (ino=%lu): %d != %d",
464 btree
->b_inode
->i_ino
,
465 nilfs_btree_node_get_level(node
), level
);
471 struct nilfs_btree_readahead_info
{
472 struct nilfs_btree_node
*node
; /* parent node */
473 int max_ra_blocks
; /* max nof blocks to read ahead */
474 int index
; /* current index on the parent node */
475 int ncmax
; /* nof children in the parent node */
478 static int __nilfs_btree_get_block(const struct nilfs_bmap
*btree
, __u64 ptr
,
479 struct buffer_head
**bhp
,
480 const struct nilfs_btree_readahead_info
*ra
)
482 struct address_space
*btnc
= &NILFS_BMAP_I(btree
)->i_btnode_cache
;
483 struct buffer_head
*bh
, *ra_bh
;
484 sector_t submit_ptr
= 0;
487 ret
= nilfs_btnode_submit_block(btnc
, ptr
, 0, REQ_OP_READ
, 0, &bh
,
499 /* read ahead sibling nodes */
500 for (n
= ra
->max_ra_blocks
, i
= ra
->index
+ 1;
501 n
> 0 && i
< ra
->ncmax
; n
--, i
++) {
502 ptr2
= nilfs_btree_node_get_ptr(ra
->node
, i
, ra
->ncmax
);
504 ret
= nilfs_btnode_submit_block(btnc
, ptr2
, 0,
505 REQ_OP_READ
, REQ_RAHEAD
,
506 &ra_bh
, &submit_ptr
);
507 if (likely(!ret
|| ret
== -EEXIST
))
509 else if (ret
!= -EBUSY
)
511 if (!buffer_locked(bh
))
519 if (!buffer_uptodate(bh
)) {
520 nilfs_msg(btree
->b_inode
->i_sb
, KERN_ERR
,
521 "I/O error reading b-tree node block (ino=%lu, blocknr=%llu)",
522 btree
->b_inode
->i_ino
, (unsigned long long)ptr
);
528 if (nilfs_btree_broken_node_block(bh
)) {
529 clear_buffer_uptodate(bh
);
538 static int nilfs_btree_get_block(const struct nilfs_bmap
*btree
, __u64 ptr
,
539 struct buffer_head
**bhp
)
541 return __nilfs_btree_get_block(btree
, ptr
, bhp
, NULL
);
544 static int nilfs_btree_do_lookup(const struct nilfs_bmap
*btree
,
545 struct nilfs_btree_path
*path
,
546 __u64 key
, __u64
*ptrp
, int minlevel
,
549 struct nilfs_btree_node
*node
;
550 struct nilfs_btree_readahead_info p
, *ra
;
552 int level
, index
, found
, ncmax
, ret
;
554 node
= nilfs_btree_get_root(btree
);
555 level
= nilfs_btree_node_get_level(node
);
556 if (level
< minlevel
|| nilfs_btree_node_get_nchildren(node
) <= 0)
559 found
= nilfs_btree_node_lookup(node
, key
, &index
);
560 ptr
= nilfs_btree_node_get_ptr(node
, index
,
561 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
562 path
[level
].bp_bh
= NULL
;
563 path
[level
].bp_index
= index
;
565 ncmax
= nilfs_btree_nchildren_per_block(btree
);
567 while (--level
>= minlevel
) {
569 if (level
== NILFS_BTREE_LEVEL_NODE_MIN
&& readahead
) {
570 p
.node
= nilfs_btree_get_node(btree
, path
, level
+ 1,
576 ret
= __nilfs_btree_get_block(btree
, ptr
, &path
[level
].bp_bh
,
581 node
= nilfs_btree_get_nonroot_node(path
, level
);
582 if (nilfs_btree_bad_node(btree
, node
, level
))
585 found
= nilfs_btree_node_lookup(node
, key
, &index
);
589 ptr
= nilfs_btree_node_get_ptr(node
, index
, ncmax
);
591 WARN_ON(found
|| level
!= NILFS_BTREE_LEVEL_NODE_MIN
);
593 ptr
= NILFS_BMAP_INVALID_PTR
;
595 path
[level
].bp_index
= index
;
606 static int nilfs_btree_do_lookup_last(const struct nilfs_bmap
*btree
,
607 struct nilfs_btree_path
*path
,
608 __u64
*keyp
, __u64
*ptrp
)
610 struct nilfs_btree_node
*node
;
612 int index
, level
, ncmax
, ret
;
614 node
= nilfs_btree_get_root(btree
);
615 index
= nilfs_btree_node_get_nchildren(node
) - 1;
618 level
= nilfs_btree_node_get_level(node
);
619 ptr
= nilfs_btree_node_get_ptr(node
, index
,
620 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
621 path
[level
].bp_bh
= NULL
;
622 path
[level
].bp_index
= index
;
623 ncmax
= nilfs_btree_nchildren_per_block(btree
);
625 for (level
--; level
> 0; level
--) {
626 ret
= nilfs_btree_get_block(btree
, ptr
, &path
[level
].bp_bh
);
629 node
= nilfs_btree_get_nonroot_node(path
, level
);
630 if (nilfs_btree_bad_node(btree
, node
, level
))
632 index
= nilfs_btree_node_get_nchildren(node
) - 1;
633 ptr
= nilfs_btree_node_get_ptr(node
, index
, ncmax
);
634 path
[level
].bp_index
= index
;
638 *keyp
= nilfs_btree_node_get_key(node
, index
);
646 * nilfs_btree_get_next_key - get next valid key from btree path array
647 * @btree: bmap struct of btree
648 * @path: array of nilfs_btree_path struct
649 * @minlevel: start level
650 * @nextkey: place to store the next valid key
652 * Return Value: If a next key was found, 0 is returned. Otherwise,
653 * -ENOENT is returned.
655 static int nilfs_btree_get_next_key(const struct nilfs_bmap
*btree
,
656 const struct nilfs_btree_path
*path
,
657 int minlevel
, __u64
*nextkey
)
659 struct nilfs_btree_node
*node
;
660 int maxlevel
= nilfs_btree_height(btree
) - 1;
661 int index
, next_adj
, level
;
663 /* Next index is already set to bp_index for leaf nodes. */
665 for (level
= minlevel
; level
<= maxlevel
; level
++) {
666 if (level
== maxlevel
)
667 node
= nilfs_btree_get_root(btree
);
669 node
= nilfs_btree_get_nonroot_node(path
, level
);
671 index
= path
[level
].bp_index
+ next_adj
;
672 if (index
< nilfs_btree_node_get_nchildren(node
)) {
673 /* Next key is in this node */
674 *nextkey
= nilfs_btree_node_get_key(node
, index
);
677 /* For non-leaf nodes, next index is stored at bp_index + 1. */
683 static int nilfs_btree_lookup(const struct nilfs_bmap
*btree
,
684 __u64 key
, int level
, __u64
*ptrp
)
686 struct nilfs_btree_path
*path
;
689 path
= nilfs_btree_alloc_path();
693 ret
= nilfs_btree_do_lookup(btree
, path
, key
, ptrp
, level
, 0);
695 nilfs_btree_free_path(path
);
700 static int nilfs_btree_lookup_contig(const struct nilfs_bmap
*btree
,
701 __u64 key
, __u64
*ptrp
,
702 unsigned int maxblocks
)
704 struct nilfs_btree_path
*path
;
705 struct nilfs_btree_node
*node
;
706 struct inode
*dat
= NULL
;
709 int level
= NILFS_BTREE_LEVEL_NODE_MIN
;
710 int ret
, cnt
, index
, maxlevel
, ncmax
;
711 struct nilfs_btree_readahead_info p
;
713 path
= nilfs_btree_alloc_path();
717 ret
= nilfs_btree_do_lookup(btree
, path
, key
, &ptr
, level
, 1);
721 if (NILFS_BMAP_USE_VBN(btree
)) {
722 dat
= nilfs_bmap_get_dat(btree
);
723 ret
= nilfs_dat_translate(dat
, ptr
, &blocknr
);
729 if (cnt
== maxblocks
)
732 maxlevel
= nilfs_btree_height(btree
) - 1;
733 node
= nilfs_btree_get_node(btree
, path
, level
, &ncmax
);
734 index
= path
[level
].bp_index
+ 1;
736 while (index
< nilfs_btree_node_get_nchildren(node
)) {
737 if (nilfs_btree_node_get_key(node
, index
) !=
740 ptr2
= nilfs_btree_node_get_ptr(node
, index
, ncmax
);
742 ret
= nilfs_dat_translate(dat
, ptr2
, &blocknr
);
747 if (ptr2
!= ptr
+ cnt
|| ++cnt
== maxblocks
)
752 if (level
== maxlevel
)
755 /* look-up right sibling node */
756 p
.node
= nilfs_btree_get_node(btree
, path
, level
+ 1, &p
.ncmax
);
757 p
.index
= path
[level
+ 1].bp_index
+ 1;
759 if (p
.index
>= nilfs_btree_node_get_nchildren(p
.node
) ||
760 nilfs_btree_node_get_key(p
.node
, p
.index
) != key
+ cnt
)
762 ptr2
= nilfs_btree_node_get_ptr(p
.node
, p
.index
, p
.ncmax
);
763 path
[level
+ 1].bp_index
= p
.index
;
765 brelse(path
[level
].bp_bh
);
766 path
[level
].bp_bh
= NULL
;
768 ret
= __nilfs_btree_get_block(btree
, ptr2
, &path
[level
].bp_bh
,
772 node
= nilfs_btree_get_nonroot_node(path
, level
);
773 ncmax
= nilfs_btree_nchildren_per_block(btree
);
775 path
[level
].bp_index
= index
;
781 nilfs_btree_free_path(path
);
785 static void nilfs_btree_promote_key(struct nilfs_bmap
*btree
,
786 struct nilfs_btree_path
*path
,
787 int level
, __u64 key
)
789 if (level
< nilfs_btree_height(btree
) - 1) {
791 nilfs_btree_node_set_key(
792 nilfs_btree_get_nonroot_node(path
, level
),
793 path
[level
].bp_index
, key
);
794 if (!buffer_dirty(path
[level
].bp_bh
))
795 mark_buffer_dirty(path
[level
].bp_bh
);
796 } while ((path
[level
].bp_index
== 0) &&
797 (++level
< nilfs_btree_height(btree
) - 1));
801 if (level
== nilfs_btree_height(btree
) - 1) {
802 nilfs_btree_node_set_key(nilfs_btree_get_root(btree
),
803 path
[level
].bp_index
, key
);
807 static void nilfs_btree_do_insert(struct nilfs_bmap
*btree
,
808 struct nilfs_btree_path
*path
,
809 int level
, __u64
*keyp
, __u64
*ptrp
)
811 struct nilfs_btree_node
*node
;
814 if (level
< nilfs_btree_height(btree
) - 1) {
815 node
= nilfs_btree_get_nonroot_node(path
, level
);
816 ncblk
= nilfs_btree_nchildren_per_block(btree
);
817 nilfs_btree_node_insert(node
, path
[level
].bp_index
,
818 *keyp
, *ptrp
, ncblk
);
819 if (!buffer_dirty(path
[level
].bp_bh
))
820 mark_buffer_dirty(path
[level
].bp_bh
);
822 if (path
[level
].bp_index
== 0)
823 nilfs_btree_promote_key(btree
, path
, level
+ 1,
824 nilfs_btree_node_get_key(node
,
827 node
= nilfs_btree_get_root(btree
);
828 nilfs_btree_node_insert(node
, path
[level
].bp_index
,
830 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
834 static void nilfs_btree_carry_left(struct nilfs_bmap
*btree
,
835 struct nilfs_btree_path
*path
,
836 int level
, __u64
*keyp
, __u64
*ptrp
)
838 struct nilfs_btree_node
*node
, *left
;
839 int nchildren
, lnchildren
, n
, move
, ncblk
;
841 node
= nilfs_btree_get_nonroot_node(path
, level
);
842 left
= nilfs_btree_get_sib_node(path
, level
);
843 nchildren
= nilfs_btree_node_get_nchildren(node
);
844 lnchildren
= nilfs_btree_node_get_nchildren(left
);
845 ncblk
= nilfs_btree_nchildren_per_block(btree
);
848 n
= (nchildren
+ lnchildren
+ 1) / 2 - lnchildren
;
849 if (n
> path
[level
].bp_index
) {
850 /* move insert point */
855 nilfs_btree_node_move_left(left
, node
, n
, ncblk
, ncblk
);
857 if (!buffer_dirty(path
[level
].bp_bh
))
858 mark_buffer_dirty(path
[level
].bp_bh
);
859 if (!buffer_dirty(path
[level
].bp_sib_bh
))
860 mark_buffer_dirty(path
[level
].bp_sib_bh
);
862 nilfs_btree_promote_key(btree
, path
, level
+ 1,
863 nilfs_btree_node_get_key(node
, 0));
866 brelse(path
[level
].bp_bh
);
867 path
[level
].bp_bh
= path
[level
].bp_sib_bh
;
868 path
[level
].bp_sib_bh
= NULL
;
869 path
[level
].bp_index
+= lnchildren
;
870 path
[level
+ 1].bp_index
--;
872 brelse(path
[level
].bp_sib_bh
);
873 path
[level
].bp_sib_bh
= NULL
;
874 path
[level
].bp_index
-= n
;
877 nilfs_btree_do_insert(btree
, path
, level
, keyp
, ptrp
);
880 static void nilfs_btree_carry_right(struct nilfs_bmap
*btree
,
881 struct nilfs_btree_path
*path
,
882 int level
, __u64
*keyp
, __u64
*ptrp
)
884 struct nilfs_btree_node
*node
, *right
;
885 int nchildren
, rnchildren
, n
, move
, ncblk
;
887 node
= nilfs_btree_get_nonroot_node(path
, level
);
888 right
= nilfs_btree_get_sib_node(path
, level
);
889 nchildren
= nilfs_btree_node_get_nchildren(node
);
890 rnchildren
= nilfs_btree_node_get_nchildren(right
);
891 ncblk
= nilfs_btree_nchildren_per_block(btree
);
894 n
= (nchildren
+ rnchildren
+ 1) / 2 - rnchildren
;
895 if (n
> nchildren
- path
[level
].bp_index
) {
896 /* move insert point */
901 nilfs_btree_node_move_right(node
, right
, n
, ncblk
, ncblk
);
903 if (!buffer_dirty(path
[level
].bp_bh
))
904 mark_buffer_dirty(path
[level
].bp_bh
);
905 if (!buffer_dirty(path
[level
].bp_sib_bh
))
906 mark_buffer_dirty(path
[level
].bp_sib_bh
);
908 path
[level
+ 1].bp_index
++;
909 nilfs_btree_promote_key(btree
, path
, level
+ 1,
910 nilfs_btree_node_get_key(right
, 0));
911 path
[level
+ 1].bp_index
--;
914 brelse(path
[level
].bp_bh
);
915 path
[level
].bp_bh
= path
[level
].bp_sib_bh
;
916 path
[level
].bp_sib_bh
= NULL
;
917 path
[level
].bp_index
-= nilfs_btree_node_get_nchildren(node
);
918 path
[level
+ 1].bp_index
++;
920 brelse(path
[level
].bp_sib_bh
);
921 path
[level
].bp_sib_bh
= NULL
;
924 nilfs_btree_do_insert(btree
, path
, level
, keyp
, ptrp
);
927 static void nilfs_btree_split(struct nilfs_bmap
*btree
,
928 struct nilfs_btree_path
*path
,
929 int level
, __u64
*keyp
, __u64
*ptrp
)
931 struct nilfs_btree_node
*node
, *right
;
932 int nchildren
, n
, move
, ncblk
;
934 node
= nilfs_btree_get_nonroot_node(path
, level
);
935 right
= nilfs_btree_get_sib_node(path
, level
);
936 nchildren
= nilfs_btree_node_get_nchildren(node
);
937 ncblk
= nilfs_btree_nchildren_per_block(btree
);
940 n
= (nchildren
+ 1) / 2;
941 if (n
> nchildren
- path
[level
].bp_index
) {
946 nilfs_btree_node_move_right(node
, right
, n
, ncblk
, ncblk
);
948 if (!buffer_dirty(path
[level
].bp_bh
))
949 mark_buffer_dirty(path
[level
].bp_bh
);
950 if (!buffer_dirty(path
[level
].bp_sib_bh
))
951 mark_buffer_dirty(path
[level
].bp_sib_bh
);
954 path
[level
].bp_index
-= nilfs_btree_node_get_nchildren(node
);
955 nilfs_btree_node_insert(right
, path
[level
].bp_index
,
956 *keyp
, *ptrp
, ncblk
);
958 *keyp
= nilfs_btree_node_get_key(right
, 0);
959 *ptrp
= path
[level
].bp_newreq
.bpr_ptr
;
961 brelse(path
[level
].bp_bh
);
962 path
[level
].bp_bh
= path
[level
].bp_sib_bh
;
963 path
[level
].bp_sib_bh
= NULL
;
965 nilfs_btree_do_insert(btree
, path
, level
, keyp
, ptrp
);
967 *keyp
= nilfs_btree_node_get_key(right
, 0);
968 *ptrp
= path
[level
].bp_newreq
.bpr_ptr
;
970 brelse(path
[level
].bp_sib_bh
);
971 path
[level
].bp_sib_bh
= NULL
;
974 path
[level
+ 1].bp_index
++;
977 static void nilfs_btree_grow(struct nilfs_bmap
*btree
,
978 struct nilfs_btree_path
*path
,
979 int level
, __u64
*keyp
, __u64
*ptrp
)
981 struct nilfs_btree_node
*root
, *child
;
984 root
= nilfs_btree_get_root(btree
);
985 child
= nilfs_btree_get_sib_node(path
, level
);
986 ncblk
= nilfs_btree_nchildren_per_block(btree
);
988 n
= nilfs_btree_node_get_nchildren(root
);
990 nilfs_btree_node_move_right(root
, child
, n
,
991 NILFS_BTREE_ROOT_NCHILDREN_MAX
, ncblk
);
992 nilfs_btree_node_set_level(root
, level
+ 1);
994 if (!buffer_dirty(path
[level
].bp_sib_bh
))
995 mark_buffer_dirty(path
[level
].bp_sib_bh
);
997 path
[level
].bp_bh
= path
[level
].bp_sib_bh
;
998 path
[level
].bp_sib_bh
= NULL
;
1000 nilfs_btree_do_insert(btree
, path
, level
, keyp
, ptrp
);
1002 *keyp
= nilfs_btree_node_get_key(child
, 0);
1003 *ptrp
= path
[level
].bp_newreq
.bpr_ptr
;
1006 static __u64
nilfs_btree_find_near(const struct nilfs_bmap
*btree
,
1007 const struct nilfs_btree_path
*path
)
1009 struct nilfs_btree_node
*node
;
1013 return NILFS_BMAP_INVALID_PTR
;
1016 level
= NILFS_BTREE_LEVEL_NODE_MIN
;
1017 if (path
[level
].bp_index
> 0) {
1018 node
= nilfs_btree_get_node(btree
, path
, level
, &ncmax
);
1019 return nilfs_btree_node_get_ptr(node
,
1020 path
[level
].bp_index
- 1,
1025 level
= NILFS_BTREE_LEVEL_NODE_MIN
+ 1;
1026 if (level
<= nilfs_btree_height(btree
) - 1) {
1027 node
= nilfs_btree_get_node(btree
, path
, level
, &ncmax
);
1028 return nilfs_btree_node_get_ptr(node
, path
[level
].bp_index
,
1032 return NILFS_BMAP_INVALID_PTR
;
1035 static __u64
nilfs_btree_find_target_v(const struct nilfs_bmap
*btree
,
1036 const struct nilfs_btree_path
*path
,
1041 ptr
= nilfs_bmap_find_target_seq(btree
, key
);
1042 if (ptr
!= NILFS_BMAP_INVALID_PTR
)
1043 /* sequential access */
1046 ptr
= nilfs_btree_find_near(btree
, path
);
1047 if (ptr
!= NILFS_BMAP_INVALID_PTR
)
1052 return nilfs_bmap_find_target_in_group(btree
);
1055 static int nilfs_btree_prepare_insert(struct nilfs_bmap
*btree
,
1056 struct nilfs_btree_path
*path
,
1057 int *levelp
, __u64 key
, __u64 ptr
,
1058 struct nilfs_bmap_stats
*stats
)
1060 struct buffer_head
*bh
;
1061 struct nilfs_btree_node
*node
, *parent
, *sib
;
1063 int pindex
, level
, ncmax
, ncblk
, ret
;
1064 struct inode
*dat
= NULL
;
1066 stats
->bs_nblocks
= 0;
1067 level
= NILFS_BTREE_LEVEL_DATA
;
1069 /* allocate a new ptr for data block */
1070 if (NILFS_BMAP_USE_VBN(btree
)) {
1071 path
[level
].bp_newreq
.bpr_ptr
=
1072 nilfs_btree_find_target_v(btree
, path
, key
);
1073 dat
= nilfs_bmap_get_dat(btree
);
1076 ret
= nilfs_bmap_prepare_alloc_ptr(btree
, &path
[level
].bp_newreq
, dat
);
1080 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1082 for (level
= NILFS_BTREE_LEVEL_NODE_MIN
;
1083 level
< nilfs_btree_height(btree
) - 1;
1085 node
= nilfs_btree_get_nonroot_node(path
, level
);
1086 if (nilfs_btree_node_get_nchildren(node
) < ncblk
) {
1087 path
[level
].bp_op
= nilfs_btree_do_insert
;
1088 stats
->bs_nblocks
++;
1092 parent
= nilfs_btree_get_node(btree
, path
, level
+ 1, &ncmax
);
1093 pindex
= path
[level
+ 1].bp_index
;
1097 sibptr
= nilfs_btree_node_get_ptr(parent
, pindex
- 1,
1099 ret
= nilfs_btree_get_block(btree
, sibptr
, &bh
);
1101 goto err_out_child_node
;
1102 sib
= (struct nilfs_btree_node
*)bh
->b_data
;
1103 if (nilfs_btree_node_get_nchildren(sib
) < ncblk
) {
1104 path
[level
].bp_sib_bh
= bh
;
1105 path
[level
].bp_op
= nilfs_btree_carry_left
;
1106 stats
->bs_nblocks
++;
1114 if (pindex
< nilfs_btree_node_get_nchildren(parent
) - 1) {
1115 sibptr
= nilfs_btree_node_get_ptr(parent
, pindex
+ 1,
1117 ret
= nilfs_btree_get_block(btree
, sibptr
, &bh
);
1119 goto err_out_child_node
;
1120 sib
= (struct nilfs_btree_node
*)bh
->b_data
;
1121 if (nilfs_btree_node_get_nchildren(sib
) < ncblk
) {
1122 path
[level
].bp_sib_bh
= bh
;
1123 path
[level
].bp_op
= nilfs_btree_carry_right
;
1124 stats
->bs_nblocks
++;
1132 path
[level
].bp_newreq
.bpr_ptr
=
1133 path
[level
- 1].bp_newreq
.bpr_ptr
+ 1;
1134 ret
= nilfs_bmap_prepare_alloc_ptr(btree
,
1135 &path
[level
].bp_newreq
, dat
);
1137 goto err_out_child_node
;
1138 ret
= nilfs_btree_get_new_block(btree
,
1139 path
[level
].bp_newreq
.bpr_ptr
,
1142 goto err_out_curr_node
;
1144 stats
->bs_nblocks
++;
1146 sib
= (struct nilfs_btree_node
*)bh
->b_data
;
1147 nilfs_btree_node_init(sib
, 0, level
, 0, ncblk
, NULL
, NULL
);
1148 path
[level
].bp_sib_bh
= bh
;
1149 path
[level
].bp_op
= nilfs_btree_split
;
1153 node
= nilfs_btree_get_root(btree
);
1154 if (nilfs_btree_node_get_nchildren(node
) <
1155 NILFS_BTREE_ROOT_NCHILDREN_MAX
) {
1156 path
[level
].bp_op
= nilfs_btree_do_insert
;
1157 stats
->bs_nblocks
++;
1162 path
[level
].bp_newreq
.bpr_ptr
= path
[level
- 1].bp_newreq
.bpr_ptr
+ 1;
1163 ret
= nilfs_bmap_prepare_alloc_ptr(btree
, &path
[level
].bp_newreq
, dat
);
1165 goto err_out_child_node
;
1166 ret
= nilfs_btree_get_new_block(btree
, path
[level
].bp_newreq
.bpr_ptr
,
1169 goto err_out_curr_node
;
1171 nilfs_btree_node_init((struct nilfs_btree_node
*)bh
->b_data
,
1172 0, level
, 0, ncblk
, NULL
, NULL
);
1173 path
[level
].bp_sib_bh
= bh
;
1174 path
[level
].bp_op
= nilfs_btree_grow
;
1177 path
[level
].bp_op
= nilfs_btree_do_insert
;
1179 /* a newly-created node block and a data block are added */
1180 stats
->bs_nblocks
+= 2;
1189 nilfs_bmap_abort_alloc_ptr(btree
, &path
[level
].bp_newreq
, dat
);
1191 for (level
--; level
> NILFS_BTREE_LEVEL_DATA
; level
--) {
1192 nilfs_btnode_delete(path
[level
].bp_sib_bh
);
1193 nilfs_bmap_abort_alloc_ptr(btree
, &path
[level
].bp_newreq
, dat
);
1197 nilfs_bmap_abort_alloc_ptr(btree
, &path
[level
].bp_newreq
, dat
);
1200 stats
->bs_nblocks
= 0;
1204 static void nilfs_btree_commit_insert(struct nilfs_bmap
*btree
,
1205 struct nilfs_btree_path
*path
,
1206 int maxlevel
, __u64 key
, __u64 ptr
)
1208 struct inode
*dat
= NULL
;
1211 set_buffer_nilfs_volatile((struct buffer_head
*)((unsigned long)ptr
));
1212 ptr
= path
[NILFS_BTREE_LEVEL_DATA
].bp_newreq
.bpr_ptr
;
1213 if (NILFS_BMAP_USE_VBN(btree
)) {
1214 nilfs_bmap_set_target_v(btree
, key
, ptr
);
1215 dat
= nilfs_bmap_get_dat(btree
);
1218 for (level
= NILFS_BTREE_LEVEL_NODE_MIN
; level
<= maxlevel
; level
++) {
1219 nilfs_bmap_commit_alloc_ptr(btree
,
1220 &path
[level
- 1].bp_newreq
, dat
);
1221 path
[level
].bp_op(btree
, path
, level
, &key
, &ptr
);
1224 if (!nilfs_bmap_dirty(btree
))
1225 nilfs_bmap_set_dirty(btree
);
1228 static int nilfs_btree_insert(struct nilfs_bmap
*btree
, __u64 key
, __u64 ptr
)
1230 struct nilfs_btree_path
*path
;
1231 struct nilfs_bmap_stats stats
;
1234 path
= nilfs_btree_alloc_path();
1238 ret
= nilfs_btree_do_lookup(btree
, path
, key
, NULL
,
1239 NILFS_BTREE_LEVEL_NODE_MIN
, 0);
1240 if (ret
!= -ENOENT
) {
1246 ret
= nilfs_btree_prepare_insert(btree
, path
, &level
, key
, ptr
, &stats
);
1249 nilfs_btree_commit_insert(btree
, path
, level
, key
, ptr
);
1250 nilfs_inode_add_blocks(btree
->b_inode
, stats
.bs_nblocks
);
1253 nilfs_btree_free_path(path
);
1257 static void nilfs_btree_do_delete(struct nilfs_bmap
*btree
,
1258 struct nilfs_btree_path
*path
,
1259 int level
, __u64
*keyp
, __u64
*ptrp
)
1261 struct nilfs_btree_node
*node
;
1264 if (level
< nilfs_btree_height(btree
) - 1) {
1265 node
= nilfs_btree_get_nonroot_node(path
, level
);
1266 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1267 nilfs_btree_node_delete(node
, path
[level
].bp_index
,
1269 if (!buffer_dirty(path
[level
].bp_bh
))
1270 mark_buffer_dirty(path
[level
].bp_bh
);
1271 if (path
[level
].bp_index
== 0)
1272 nilfs_btree_promote_key(btree
, path
, level
+ 1,
1273 nilfs_btree_node_get_key(node
, 0));
1275 node
= nilfs_btree_get_root(btree
);
1276 nilfs_btree_node_delete(node
, path
[level
].bp_index
,
1278 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
1282 static void nilfs_btree_borrow_left(struct nilfs_bmap
*btree
,
1283 struct nilfs_btree_path
*path
,
1284 int level
, __u64
*keyp
, __u64
*ptrp
)
1286 struct nilfs_btree_node
*node
, *left
;
1287 int nchildren
, lnchildren
, n
, ncblk
;
1289 nilfs_btree_do_delete(btree
, path
, level
, keyp
, ptrp
);
1291 node
= nilfs_btree_get_nonroot_node(path
, level
);
1292 left
= nilfs_btree_get_sib_node(path
, level
);
1293 nchildren
= nilfs_btree_node_get_nchildren(node
);
1294 lnchildren
= nilfs_btree_node_get_nchildren(left
);
1295 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1297 n
= (nchildren
+ lnchildren
) / 2 - nchildren
;
1299 nilfs_btree_node_move_right(left
, node
, n
, ncblk
, ncblk
);
1301 if (!buffer_dirty(path
[level
].bp_bh
))
1302 mark_buffer_dirty(path
[level
].bp_bh
);
1303 if (!buffer_dirty(path
[level
].bp_sib_bh
))
1304 mark_buffer_dirty(path
[level
].bp_sib_bh
);
1306 nilfs_btree_promote_key(btree
, path
, level
+ 1,
1307 nilfs_btree_node_get_key(node
, 0));
1309 brelse(path
[level
].bp_sib_bh
);
1310 path
[level
].bp_sib_bh
= NULL
;
1311 path
[level
].bp_index
+= n
;
1314 static void nilfs_btree_borrow_right(struct nilfs_bmap
*btree
,
1315 struct nilfs_btree_path
*path
,
1316 int level
, __u64
*keyp
, __u64
*ptrp
)
1318 struct nilfs_btree_node
*node
, *right
;
1319 int nchildren
, rnchildren
, n
, ncblk
;
1321 nilfs_btree_do_delete(btree
, path
, level
, keyp
, ptrp
);
1323 node
= nilfs_btree_get_nonroot_node(path
, level
);
1324 right
= nilfs_btree_get_sib_node(path
, level
);
1325 nchildren
= nilfs_btree_node_get_nchildren(node
);
1326 rnchildren
= nilfs_btree_node_get_nchildren(right
);
1327 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1329 n
= (nchildren
+ rnchildren
) / 2 - nchildren
;
1331 nilfs_btree_node_move_left(node
, right
, n
, ncblk
, ncblk
);
1333 if (!buffer_dirty(path
[level
].bp_bh
))
1334 mark_buffer_dirty(path
[level
].bp_bh
);
1335 if (!buffer_dirty(path
[level
].bp_sib_bh
))
1336 mark_buffer_dirty(path
[level
].bp_sib_bh
);
1338 path
[level
+ 1].bp_index
++;
1339 nilfs_btree_promote_key(btree
, path
, level
+ 1,
1340 nilfs_btree_node_get_key(right
, 0));
1341 path
[level
+ 1].bp_index
--;
1343 brelse(path
[level
].bp_sib_bh
);
1344 path
[level
].bp_sib_bh
= NULL
;
1347 static void nilfs_btree_concat_left(struct nilfs_bmap
*btree
,
1348 struct nilfs_btree_path
*path
,
1349 int level
, __u64
*keyp
, __u64
*ptrp
)
1351 struct nilfs_btree_node
*node
, *left
;
1354 nilfs_btree_do_delete(btree
, path
, level
, keyp
, ptrp
);
1356 node
= nilfs_btree_get_nonroot_node(path
, level
);
1357 left
= nilfs_btree_get_sib_node(path
, level
);
1358 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1360 n
= nilfs_btree_node_get_nchildren(node
);
1362 nilfs_btree_node_move_left(left
, node
, n
, ncblk
, ncblk
);
1364 if (!buffer_dirty(path
[level
].bp_sib_bh
))
1365 mark_buffer_dirty(path
[level
].bp_sib_bh
);
1367 nilfs_btnode_delete(path
[level
].bp_bh
);
1368 path
[level
].bp_bh
= path
[level
].bp_sib_bh
;
1369 path
[level
].bp_sib_bh
= NULL
;
1370 path
[level
].bp_index
+= nilfs_btree_node_get_nchildren(left
);
1373 static void nilfs_btree_concat_right(struct nilfs_bmap
*btree
,
1374 struct nilfs_btree_path
*path
,
1375 int level
, __u64
*keyp
, __u64
*ptrp
)
1377 struct nilfs_btree_node
*node
, *right
;
1380 nilfs_btree_do_delete(btree
, path
, level
, keyp
, ptrp
);
1382 node
= nilfs_btree_get_nonroot_node(path
, level
);
1383 right
= nilfs_btree_get_sib_node(path
, level
);
1384 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1386 n
= nilfs_btree_node_get_nchildren(right
);
1388 nilfs_btree_node_move_left(node
, right
, n
, ncblk
, ncblk
);
1390 if (!buffer_dirty(path
[level
].bp_bh
))
1391 mark_buffer_dirty(path
[level
].bp_bh
);
1393 nilfs_btnode_delete(path
[level
].bp_sib_bh
);
1394 path
[level
].bp_sib_bh
= NULL
;
1395 path
[level
+ 1].bp_index
++;
1398 static void nilfs_btree_shrink(struct nilfs_bmap
*btree
,
1399 struct nilfs_btree_path
*path
,
1400 int level
, __u64
*keyp
, __u64
*ptrp
)
1402 struct nilfs_btree_node
*root
, *child
;
1405 nilfs_btree_do_delete(btree
, path
, level
, keyp
, ptrp
);
1407 root
= nilfs_btree_get_root(btree
);
1408 child
= nilfs_btree_get_nonroot_node(path
, level
);
1409 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1411 nilfs_btree_node_delete(root
, 0, NULL
, NULL
,
1412 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
1413 nilfs_btree_node_set_level(root
, level
);
1414 n
= nilfs_btree_node_get_nchildren(child
);
1415 nilfs_btree_node_move_left(root
, child
, n
,
1416 NILFS_BTREE_ROOT_NCHILDREN_MAX
, ncblk
);
1418 nilfs_btnode_delete(path
[level
].bp_bh
);
1419 path
[level
].bp_bh
= NULL
;
1422 static void nilfs_btree_nop(struct nilfs_bmap
*btree
,
1423 struct nilfs_btree_path
*path
,
1424 int level
, __u64
*keyp
, __u64
*ptrp
)
1428 static int nilfs_btree_prepare_delete(struct nilfs_bmap
*btree
,
1429 struct nilfs_btree_path
*path
,
1431 struct nilfs_bmap_stats
*stats
,
1434 struct buffer_head
*bh
;
1435 struct nilfs_btree_node
*node
, *parent
, *sib
;
1437 int pindex
, dindex
, level
, ncmin
, ncmax
, ncblk
, ret
;
1440 stats
->bs_nblocks
= 0;
1441 ncmin
= NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree
));
1442 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1444 for (level
= NILFS_BTREE_LEVEL_NODE_MIN
, dindex
= path
[level
].bp_index
;
1445 level
< nilfs_btree_height(btree
) - 1;
1447 node
= nilfs_btree_get_nonroot_node(path
, level
);
1448 path
[level
].bp_oldreq
.bpr_ptr
=
1449 nilfs_btree_node_get_ptr(node
, dindex
, ncblk
);
1450 ret
= nilfs_bmap_prepare_end_ptr(btree
,
1451 &path
[level
].bp_oldreq
, dat
);
1453 goto err_out_child_node
;
1455 if (nilfs_btree_node_get_nchildren(node
) > ncmin
) {
1456 path
[level
].bp_op
= nilfs_btree_do_delete
;
1457 stats
->bs_nblocks
++;
1461 parent
= nilfs_btree_get_node(btree
, path
, level
+ 1, &ncmax
);
1462 pindex
= path
[level
+ 1].bp_index
;
1467 sibptr
= nilfs_btree_node_get_ptr(parent
, pindex
- 1,
1469 ret
= nilfs_btree_get_block(btree
, sibptr
, &bh
);
1471 goto err_out_curr_node
;
1472 sib
= (struct nilfs_btree_node
*)bh
->b_data
;
1473 if (nilfs_btree_node_get_nchildren(sib
) > ncmin
) {
1474 path
[level
].bp_sib_bh
= bh
;
1475 path
[level
].bp_op
= nilfs_btree_borrow_left
;
1476 stats
->bs_nblocks
++;
1479 path
[level
].bp_sib_bh
= bh
;
1480 path
[level
].bp_op
= nilfs_btree_concat_left
;
1481 stats
->bs_nblocks
++;
1485 nilfs_btree_node_get_nchildren(parent
) - 1) {
1487 sibptr
= nilfs_btree_node_get_ptr(parent
, pindex
+ 1,
1489 ret
= nilfs_btree_get_block(btree
, sibptr
, &bh
);
1491 goto err_out_curr_node
;
1492 sib
= (struct nilfs_btree_node
*)bh
->b_data
;
1493 if (nilfs_btree_node_get_nchildren(sib
) > ncmin
) {
1494 path
[level
].bp_sib_bh
= bh
;
1495 path
[level
].bp_op
= nilfs_btree_borrow_right
;
1496 stats
->bs_nblocks
++;
1499 path
[level
].bp_sib_bh
= bh
;
1500 path
[level
].bp_op
= nilfs_btree_concat_right
;
1501 stats
->bs_nblocks
++;
1503 * When merging right sibling node
1504 * into the current node, pointer to
1505 * the right sibling node must be
1506 * terminated instead. The adjustment
1507 * below is required for that.
1509 dindex
= pindex
+ 1;
1514 /* the only child of the root node */
1515 WARN_ON(level
!= nilfs_btree_height(btree
) - 2);
1516 if (nilfs_btree_node_get_nchildren(node
) - 1 <=
1517 NILFS_BTREE_ROOT_NCHILDREN_MAX
) {
1518 path
[level
].bp_op
= nilfs_btree_shrink
;
1519 stats
->bs_nblocks
+= 2;
1521 path
[level
].bp_op
= nilfs_btree_nop
;
1522 goto shrink_root_child
;
1524 path
[level
].bp_op
= nilfs_btree_do_delete
;
1525 stats
->bs_nblocks
++;
1531 /* child of the root node is deleted */
1532 path
[level
].bp_op
= nilfs_btree_do_delete
;
1533 stats
->bs_nblocks
++;
1536 node
= nilfs_btree_get_root(btree
);
1537 path
[level
].bp_oldreq
.bpr_ptr
=
1538 nilfs_btree_node_get_ptr(node
, dindex
,
1539 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
1541 ret
= nilfs_bmap_prepare_end_ptr(btree
, &path
[level
].bp_oldreq
, dat
);
1543 goto err_out_child_node
;
1552 nilfs_bmap_abort_end_ptr(btree
, &path
[level
].bp_oldreq
, dat
);
1554 for (level
--; level
>= NILFS_BTREE_LEVEL_NODE_MIN
; level
--) {
1555 brelse(path
[level
].bp_sib_bh
);
1556 nilfs_bmap_abort_end_ptr(btree
, &path
[level
].bp_oldreq
, dat
);
1559 stats
->bs_nblocks
= 0;
1563 static void nilfs_btree_commit_delete(struct nilfs_bmap
*btree
,
1564 struct nilfs_btree_path
*path
,
1565 int maxlevel
, struct inode
*dat
)
1569 for (level
= NILFS_BTREE_LEVEL_NODE_MIN
; level
<= maxlevel
; level
++) {
1570 nilfs_bmap_commit_end_ptr(btree
, &path
[level
].bp_oldreq
, dat
);
1571 path
[level
].bp_op(btree
, path
, level
, NULL
, NULL
);
1574 if (!nilfs_bmap_dirty(btree
))
1575 nilfs_bmap_set_dirty(btree
);
1578 static int nilfs_btree_delete(struct nilfs_bmap
*btree
, __u64 key
)
1581 struct nilfs_btree_path
*path
;
1582 struct nilfs_bmap_stats stats
;
1586 path
= nilfs_btree_alloc_path();
1590 ret
= nilfs_btree_do_lookup(btree
, path
, key
, NULL
,
1591 NILFS_BTREE_LEVEL_NODE_MIN
, 0);
1596 dat
= NILFS_BMAP_USE_VBN(btree
) ? nilfs_bmap_get_dat(btree
) : NULL
;
1598 ret
= nilfs_btree_prepare_delete(btree
, path
, &level
, &stats
, dat
);
1601 nilfs_btree_commit_delete(btree
, path
, level
, dat
);
1602 nilfs_inode_sub_blocks(btree
->b_inode
, stats
.bs_nblocks
);
1605 nilfs_btree_free_path(path
);
1609 static int nilfs_btree_seek_key(const struct nilfs_bmap
*btree
, __u64 start
,
1612 struct nilfs_btree_path
*path
;
1613 const int minlevel
= NILFS_BTREE_LEVEL_NODE_MIN
;
1616 path
= nilfs_btree_alloc_path();
1620 ret
= nilfs_btree_do_lookup(btree
, path
, start
, NULL
, minlevel
, 0);
1623 else if (ret
== -ENOENT
)
1624 ret
= nilfs_btree_get_next_key(btree
, path
, minlevel
, keyp
);
1626 nilfs_btree_free_path(path
);
1630 static int nilfs_btree_last_key(const struct nilfs_bmap
*btree
, __u64
*keyp
)
1632 struct nilfs_btree_path
*path
;
1635 path
= nilfs_btree_alloc_path();
1639 ret
= nilfs_btree_do_lookup_last(btree
, path
, keyp
, NULL
);
1641 nilfs_btree_free_path(path
);
1646 static int nilfs_btree_check_delete(struct nilfs_bmap
*btree
, __u64 key
)
1648 struct buffer_head
*bh
;
1649 struct nilfs_btree_node
*root
, *node
;
1650 __u64 maxkey
, nextmaxkey
;
1654 root
= nilfs_btree_get_root(btree
);
1655 switch (nilfs_btree_height(btree
)) {
1661 nchildren
= nilfs_btree_node_get_nchildren(root
);
1664 ptr
= nilfs_btree_node_get_ptr(root
, nchildren
- 1,
1665 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
1666 ret
= nilfs_btree_get_block(btree
, ptr
, &bh
);
1669 node
= (struct nilfs_btree_node
*)bh
->b_data
;
1675 nchildren
= nilfs_btree_node_get_nchildren(node
);
1676 maxkey
= nilfs_btree_node_get_key(node
, nchildren
- 1);
1677 nextmaxkey
= (nchildren
> 1) ?
1678 nilfs_btree_node_get_key(node
, nchildren
- 2) : 0;
1682 return (maxkey
== key
) && (nextmaxkey
< NILFS_BMAP_LARGE_LOW
);
1685 static int nilfs_btree_gather_data(struct nilfs_bmap
*btree
,
1686 __u64
*keys
, __u64
*ptrs
, int nitems
)
1688 struct buffer_head
*bh
;
1689 struct nilfs_btree_node
*node
, *root
;
1693 int nchildren
, ncmax
, i
, ret
;
1695 root
= nilfs_btree_get_root(btree
);
1696 switch (nilfs_btree_height(btree
)) {
1700 ncmax
= NILFS_BTREE_ROOT_NCHILDREN_MAX
;
1703 nchildren
= nilfs_btree_node_get_nchildren(root
);
1704 WARN_ON(nchildren
> 1);
1705 ptr
= nilfs_btree_node_get_ptr(root
, nchildren
- 1,
1706 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
1707 ret
= nilfs_btree_get_block(btree
, ptr
, &bh
);
1710 node
= (struct nilfs_btree_node
*)bh
->b_data
;
1711 ncmax
= nilfs_btree_nchildren_per_block(btree
);
1718 nchildren
= nilfs_btree_node_get_nchildren(node
);
1719 if (nchildren
< nitems
)
1721 dkeys
= nilfs_btree_node_dkeys(node
);
1722 dptrs
= nilfs_btree_node_dptrs(node
, ncmax
);
1723 for (i
= 0; i
< nitems
; i
++) {
1724 keys
[i
] = le64_to_cpu(dkeys
[i
]);
1725 ptrs
[i
] = le64_to_cpu(dptrs
[i
]);
1735 nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap
*btree
, __u64 key
,
1736 union nilfs_bmap_ptr_req
*dreq
,
1737 union nilfs_bmap_ptr_req
*nreq
,
1738 struct buffer_head
**bhp
,
1739 struct nilfs_bmap_stats
*stats
)
1741 struct buffer_head
*bh
;
1742 struct inode
*dat
= NULL
;
1745 stats
->bs_nblocks
= 0;
1748 /* cannot find near ptr */
1749 if (NILFS_BMAP_USE_VBN(btree
)) {
1750 dreq
->bpr_ptr
= nilfs_btree_find_target_v(btree
, NULL
, key
);
1751 dat
= nilfs_bmap_get_dat(btree
);
1754 ret
= nilfs_bmap_prepare_alloc_ptr(btree
, dreq
, dat
);
1759 stats
->bs_nblocks
++;
1761 nreq
->bpr_ptr
= dreq
->bpr_ptr
+ 1;
1762 ret
= nilfs_bmap_prepare_alloc_ptr(btree
, nreq
, dat
);
1766 ret
= nilfs_btree_get_new_block(btree
, nreq
->bpr_ptr
, &bh
);
1771 stats
->bs_nblocks
++;
1779 nilfs_bmap_abort_alloc_ptr(btree
, nreq
, dat
);
1781 nilfs_bmap_abort_alloc_ptr(btree
, dreq
, dat
);
1782 stats
->bs_nblocks
= 0;
1788 nilfs_btree_commit_convert_and_insert(struct nilfs_bmap
*btree
,
1789 __u64 key
, __u64 ptr
,
1790 const __u64
*keys
, const __u64
*ptrs
,
1792 union nilfs_bmap_ptr_req
*dreq
,
1793 union nilfs_bmap_ptr_req
*nreq
,
1794 struct buffer_head
*bh
)
1796 struct nilfs_btree_node
*node
;
1801 /* free resources */
1802 if (btree
->b_ops
->bop_clear
!= NULL
)
1803 btree
->b_ops
->bop_clear(btree
);
1805 /* ptr must be a pointer to a buffer head. */
1806 set_buffer_nilfs_volatile((struct buffer_head
*)((unsigned long)ptr
));
1808 /* convert and insert */
1809 dat
= NILFS_BMAP_USE_VBN(btree
) ? nilfs_bmap_get_dat(btree
) : NULL
;
1810 __nilfs_btree_init(btree
);
1812 nilfs_bmap_commit_alloc_ptr(btree
, dreq
, dat
);
1813 nilfs_bmap_commit_alloc_ptr(btree
, nreq
, dat
);
1815 /* create child node at level 1 */
1816 node
= (struct nilfs_btree_node
*)bh
->b_data
;
1817 ncblk
= nilfs_btree_nchildren_per_block(btree
);
1818 nilfs_btree_node_init(node
, 0, 1, n
, ncblk
, keys
, ptrs
);
1819 nilfs_btree_node_insert(node
, n
, key
, dreq
->bpr_ptr
, ncblk
);
1820 if (!buffer_dirty(bh
))
1821 mark_buffer_dirty(bh
);
1822 if (!nilfs_bmap_dirty(btree
))
1823 nilfs_bmap_set_dirty(btree
);
1827 /* create root node at level 2 */
1828 node
= nilfs_btree_get_root(btree
);
1829 tmpptr
= nreq
->bpr_ptr
;
1830 nilfs_btree_node_init(node
, NILFS_BTREE_NODE_ROOT
, 2, 1,
1831 NILFS_BTREE_ROOT_NCHILDREN_MAX
,
1834 nilfs_bmap_commit_alloc_ptr(btree
, dreq
, dat
);
1836 /* create root node at level 1 */
1837 node
= nilfs_btree_get_root(btree
);
1838 nilfs_btree_node_init(node
, NILFS_BTREE_NODE_ROOT
, 1, n
,
1839 NILFS_BTREE_ROOT_NCHILDREN_MAX
,
1841 nilfs_btree_node_insert(node
, n
, key
, dreq
->bpr_ptr
,
1842 NILFS_BTREE_ROOT_NCHILDREN_MAX
);
1843 if (!nilfs_bmap_dirty(btree
))
1844 nilfs_bmap_set_dirty(btree
);
1847 if (NILFS_BMAP_USE_VBN(btree
))
1848 nilfs_bmap_set_target_v(btree
, key
, dreq
->bpr_ptr
);
1852 * nilfs_btree_convert_and_insert -
1860 int nilfs_btree_convert_and_insert(struct nilfs_bmap
*btree
,
1861 __u64 key
, __u64 ptr
,
1862 const __u64
*keys
, const __u64
*ptrs
, int n
)
1864 struct buffer_head
*bh
= NULL
;
1865 union nilfs_bmap_ptr_req dreq
, nreq
, *di
, *ni
;
1866 struct nilfs_bmap_stats stats
;
1869 if (n
+ 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX
) {
1872 } else if ((n
+ 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
1873 nilfs_btree_node_size(btree
))) {
1882 ret
= nilfs_btree_prepare_convert_and_insert(btree
, key
, di
, ni
, &bh
,
1886 nilfs_btree_commit_convert_and_insert(btree
, key
, ptr
, keys
, ptrs
, n
,
1888 nilfs_inode_add_blocks(btree
->b_inode
, stats
.bs_nblocks
);
1892 static int nilfs_btree_propagate_p(struct nilfs_bmap
*btree
,
1893 struct nilfs_btree_path
*path
,
1895 struct buffer_head
*bh
)
1897 while ((++level
< nilfs_btree_height(btree
) - 1) &&
1898 !buffer_dirty(path
[level
].bp_bh
))
1899 mark_buffer_dirty(path
[level
].bp_bh
);
1904 static int nilfs_btree_prepare_update_v(struct nilfs_bmap
*btree
,
1905 struct nilfs_btree_path
*path
,
1906 int level
, struct inode
*dat
)
1908 struct nilfs_btree_node
*parent
;
1911 parent
= nilfs_btree_get_node(btree
, path
, level
+ 1, &ncmax
);
1912 path
[level
].bp_oldreq
.bpr_ptr
=
1913 nilfs_btree_node_get_ptr(parent
, path
[level
+ 1].bp_index
,
1915 path
[level
].bp_newreq
.bpr_ptr
= path
[level
].bp_oldreq
.bpr_ptr
+ 1;
1916 ret
= nilfs_dat_prepare_update(dat
, &path
[level
].bp_oldreq
.bpr_req
,
1917 &path
[level
].bp_newreq
.bpr_req
);
1921 if (buffer_nilfs_node(path
[level
].bp_bh
)) {
1922 path
[level
].bp_ctxt
.oldkey
= path
[level
].bp_oldreq
.bpr_ptr
;
1923 path
[level
].bp_ctxt
.newkey
= path
[level
].bp_newreq
.bpr_ptr
;
1924 path
[level
].bp_ctxt
.bh
= path
[level
].bp_bh
;
1925 ret
= nilfs_btnode_prepare_change_key(
1926 &NILFS_BMAP_I(btree
)->i_btnode_cache
,
1927 &path
[level
].bp_ctxt
);
1929 nilfs_dat_abort_update(dat
,
1930 &path
[level
].bp_oldreq
.bpr_req
,
1931 &path
[level
].bp_newreq
.bpr_req
);
1939 static void nilfs_btree_commit_update_v(struct nilfs_bmap
*btree
,
1940 struct nilfs_btree_path
*path
,
1941 int level
, struct inode
*dat
)
1943 struct nilfs_btree_node
*parent
;
1946 nilfs_dat_commit_update(dat
, &path
[level
].bp_oldreq
.bpr_req
,
1947 &path
[level
].bp_newreq
.bpr_req
,
1948 btree
->b_ptr_type
== NILFS_BMAP_PTR_VS
);
1950 if (buffer_nilfs_node(path
[level
].bp_bh
)) {
1951 nilfs_btnode_commit_change_key(
1952 &NILFS_BMAP_I(btree
)->i_btnode_cache
,
1953 &path
[level
].bp_ctxt
);
1954 path
[level
].bp_bh
= path
[level
].bp_ctxt
.bh
;
1956 set_buffer_nilfs_volatile(path
[level
].bp_bh
);
1958 parent
= nilfs_btree_get_node(btree
, path
, level
+ 1, &ncmax
);
1959 nilfs_btree_node_set_ptr(parent
, path
[level
+ 1].bp_index
,
1960 path
[level
].bp_newreq
.bpr_ptr
, ncmax
);
1963 static void nilfs_btree_abort_update_v(struct nilfs_bmap
*btree
,
1964 struct nilfs_btree_path
*path
,
1965 int level
, struct inode
*dat
)
1967 nilfs_dat_abort_update(dat
, &path
[level
].bp_oldreq
.bpr_req
,
1968 &path
[level
].bp_newreq
.bpr_req
);
1969 if (buffer_nilfs_node(path
[level
].bp_bh
))
1970 nilfs_btnode_abort_change_key(
1971 &NILFS_BMAP_I(btree
)->i_btnode_cache
,
1972 &path
[level
].bp_ctxt
);
1975 static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap
*btree
,
1976 struct nilfs_btree_path
*path
,
1977 int minlevel
, int *maxlevelp
,
1983 if (!buffer_nilfs_volatile(path
[level
].bp_bh
)) {
1984 ret
= nilfs_btree_prepare_update_v(btree
, path
, level
, dat
);
1988 while ((++level
< nilfs_btree_height(btree
) - 1) &&
1989 !buffer_dirty(path
[level
].bp_bh
)) {
1991 WARN_ON(buffer_nilfs_volatile(path
[level
].bp_bh
));
1992 ret
= nilfs_btree_prepare_update_v(btree
, path
, level
, dat
);
1998 *maxlevelp
= level
- 1;
2003 while (--level
> minlevel
)
2004 nilfs_btree_abort_update_v(btree
, path
, level
, dat
);
2005 if (!buffer_nilfs_volatile(path
[level
].bp_bh
))
2006 nilfs_btree_abort_update_v(btree
, path
, level
, dat
);
2010 static void nilfs_btree_commit_propagate_v(struct nilfs_bmap
*btree
,
2011 struct nilfs_btree_path
*path
,
2012 int minlevel
, int maxlevel
,
2013 struct buffer_head
*bh
,
2018 if (!buffer_nilfs_volatile(path
[minlevel
].bp_bh
))
2019 nilfs_btree_commit_update_v(btree
, path
, minlevel
, dat
);
2021 for (level
= minlevel
+ 1; level
<= maxlevel
; level
++)
2022 nilfs_btree_commit_update_v(btree
, path
, level
, dat
);
2025 static int nilfs_btree_propagate_v(struct nilfs_bmap
*btree
,
2026 struct nilfs_btree_path
*path
,
2027 int level
, struct buffer_head
*bh
)
2029 int maxlevel
= 0, ret
;
2030 struct nilfs_btree_node
*parent
;
2031 struct inode
*dat
= nilfs_bmap_get_dat(btree
);
2036 path
[level
].bp_bh
= bh
;
2037 ret
= nilfs_btree_prepare_propagate_v(btree
, path
, level
, &maxlevel
,
2042 if (buffer_nilfs_volatile(path
[level
].bp_bh
)) {
2043 parent
= nilfs_btree_get_node(btree
, path
, level
+ 1, &ncmax
);
2044 ptr
= nilfs_btree_node_get_ptr(parent
,
2045 path
[level
+ 1].bp_index
,
2047 ret
= nilfs_dat_mark_dirty(dat
, ptr
);
2052 nilfs_btree_commit_propagate_v(btree
, path
, level
, maxlevel
, bh
, dat
);
2055 brelse(path
[level
].bp_bh
);
2056 path
[level
].bp_bh
= NULL
;
2060 static int nilfs_btree_propagate(struct nilfs_bmap
*btree
,
2061 struct buffer_head
*bh
)
2063 struct nilfs_btree_path
*path
;
2064 struct nilfs_btree_node
*node
;
2068 WARN_ON(!buffer_dirty(bh
));
2070 path
= nilfs_btree_alloc_path();
2074 if (buffer_nilfs_node(bh
)) {
2075 node
= (struct nilfs_btree_node
*)bh
->b_data
;
2076 key
= nilfs_btree_node_get_key(node
, 0);
2077 level
= nilfs_btree_node_get_level(node
);
2079 key
= nilfs_bmap_data_get_key(btree
, bh
);
2080 level
= NILFS_BTREE_LEVEL_DATA
;
2083 ret
= nilfs_btree_do_lookup(btree
, path
, key
, NULL
, level
+ 1, 0);
2085 if (unlikely(ret
== -ENOENT
))
2086 nilfs_msg(btree
->b_inode
->i_sb
, KERN_CRIT
,
2087 "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d",
2088 btree
->b_inode
->i_ino
,
2089 (unsigned long long)key
, level
);
2093 ret
= NILFS_BMAP_USE_VBN(btree
) ?
2094 nilfs_btree_propagate_v(btree
, path
, level
, bh
) :
2095 nilfs_btree_propagate_p(btree
, path
, level
, bh
);
2098 nilfs_btree_free_path(path
);
2103 static int nilfs_btree_propagate_gc(struct nilfs_bmap
*btree
,
2104 struct buffer_head
*bh
)
2106 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree
), bh
->b_blocknr
);
2109 static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap
*btree
,
2110 struct list_head
*lists
,
2111 struct buffer_head
*bh
)
2113 struct list_head
*head
;
2114 struct buffer_head
*cbh
;
2115 struct nilfs_btree_node
*node
, *cnode
;
2120 node
= (struct nilfs_btree_node
*)bh
->b_data
;
2121 key
= nilfs_btree_node_get_key(node
, 0);
2122 level
= nilfs_btree_node_get_level(node
);
2123 if (level
< NILFS_BTREE_LEVEL_NODE_MIN
||
2124 level
>= NILFS_BTREE_LEVEL_MAX
) {
2126 nilfs_msg(btree
->b_inode
->i_sb
, KERN_WARNING
,
2127 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",
2128 level
, (unsigned long long)key
,
2129 btree
->b_inode
->i_ino
,
2130 (unsigned long long)bh
->b_blocknr
);
2134 list_for_each(head
, &lists
[level
]) {
2135 cbh
= list_entry(head
, struct buffer_head
, b_assoc_buffers
);
2136 cnode
= (struct nilfs_btree_node
*)cbh
->b_data
;
2137 ckey
= nilfs_btree_node_get_key(cnode
, 0);
2141 list_add_tail(&bh
->b_assoc_buffers
, head
);
2144 static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap
*btree
,
2145 struct list_head
*listp
)
2147 struct address_space
*btcache
= &NILFS_BMAP_I(btree
)->i_btnode_cache
;
2148 struct list_head lists
[NILFS_BTREE_LEVEL_MAX
];
2149 struct pagevec pvec
;
2150 struct buffer_head
*bh
, *head
;
2154 for (level
= NILFS_BTREE_LEVEL_NODE_MIN
;
2155 level
< NILFS_BTREE_LEVEL_MAX
;
2157 INIT_LIST_HEAD(&lists
[level
]);
2159 pagevec_init(&pvec
, 0);
2161 while (pagevec_lookup_tag(&pvec
, btcache
, &index
, PAGECACHE_TAG_DIRTY
,
2163 for (i
= 0; i
< pagevec_count(&pvec
); i
++) {
2164 bh
= head
= page_buffers(pvec
.pages
[i
]);
2166 if (buffer_dirty(bh
))
2167 nilfs_btree_add_dirty_buffer(btree
,
2169 } while ((bh
= bh
->b_this_page
) != head
);
2171 pagevec_release(&pvec
);
2175 for (level
= NILFS_BTREE_LEVEL_NODE_MIN
;
2176 level
< NILFS_BTREE_LEVEL_MAX
;
2178 list_splice_tail(&lists
[level
], listp
);
2181 static int nilfs_btree_assign_p(struct nilfs_bmap
*btree
,
2182 struct nilfs_btree_path
*path
,
2184 struct buffer_head
**bh
,
2186 union nilfs_binfo
*binfo
)
2188 struct nilfs_btree_node
*parent
;
2193 parent
= nilfs_btree_get_node(btree
, path
, level
+ 1, &ncmax
);
2194 ptr
= nilfs_btree_node_get_ptr(parent
, path
[level
+ 1].bp_index
,
2196 if (buffer_nilfs_node(*bh
)) {
2197 path
[level
].bp_ctxt
.oldkey
= ptr
;
2198 path
[level
].bp_ctxt
.newkey
= blocknr
;
2199 path
[level
].bp_ctxt
.bh
= *bh
;
2200 ret
= nilfs_btnode_prepare_change_key(
2201 &NILFS_BMAP_I(btree
)->i_btnode_cache
,
2202 &path
[level
].bp_ctxt
);
2205 nilfs_btnode_commit_change_key(
2206 &NILFS_BMAP_I(btree
)->i_btnode_cache
,
2207 &path
[level
].bp_ctxt
);
2208 *bh
= path
[level
].bp_ctxt
.bh
;
2211 nilfs_btree_node_set_ptr(parent
, path
[level
+ 1].bp_index
, blocknr
,
2214 key
= nilfs_btree_node_get_key(parent
, path
[level
+ 1].bp_index
);
2215 /* on-disk format */
2216 binfo
->bi_dat
.bi_blkoff
= cpu_to_le64(key
);
2217 binfo
->bi_dat
.bi_level
= level
;
2222 static int nilfs_btree_assign_v(struct nilfs_bmap
*btree
,
2223 struct nilfs_btree_path
*path
,
2225 struct buffer_head
**bh
,
2227 union nilfs_binfo
*binfo
)
2229 struct nilfs_btree_node
*parent
;
2230 struct inode
*dat
= nilfs_bmap_get_dat(btree
);
2233 union nilfs_bmap_ptr_req req
;
2236 parent
= nilfs_btree_get_node(btree
, path
, level
+ 1, &ncmax
);
2237 ptr
= nilfs_btree_node_get_ptr(parent
, path
[level
+ 1].bp_index
,
2240 ret
= nilfs_dat_prepare_start(dat
, &req
.bpr_req
);
2243 nilfs_dat_commit_start(dat
, &req
.bpr_req
, blocknr
);
2245 key
= nilfs_btree_node_get_key(parent
, path
[level
+ 1].bp_index
);
2246 /* on-disk format */
2247 binfo
->bi_v
.bi_vblocknr
= cpu_to_le64(ptr
);
2248 binfo
->bi_v
.bi_blkoff
= cpu_to_le64(key
);
2253 static int nilfs_btree_assign(struct nilfs_bmap
*btree
,
2254 struct buffer_head
**bh
,
2256 union nilfs_binfo
*binfo
)
2258 struct nilfs_btree_path
*path
;
2259 struct nilfs_btree_node
*node
;
2263 path
= nilfs_btree_alloc_path();
2267 if (buffer_nilfs_node(*bh
)) {
2268 node
= (struct nilfs_btree_node
*)(*bh
)->b_data
;
2269 key
= nilfs_btree_node_get_key(node
, 0);
2270 level
= nilfs_btree_node_get_level(node
);
2272 key
= nilfs_bmap_data_get_key(btree
, *bh
);
2273 level
= NILFS_BTREE_LEVEL_DATA
;
2276 ret
= nilfs_btree_do_lookup(btree
, path
, key
, NULL
, level
+ 1, 0);
2278 WARN_ON(ret
== -ENOENT
);
2282 ret
= NILFS_BMAP_USE_VBN(btree
) ?
2283 nilfs_btree_assign_v(btree
, path
, level
, bh
, blocknr
, binfo
) :
2284 nilfs_btree_assign_p(btree
, path
, level
, bh
, blocknr
, binfo
);
2287 nilfs_btree_free_path(path
);
2292 static int nilfs_btree_assign_gc(struct nilfs_bmap
*btree
,
2293 struct buffer_head
**bh
,
2295 union nilfs_binfo
*binfo
)
2297 struct nilfs_btree_node
*node
;
2301 ret
= nilfs_dat_move(nilfs_bmap_get_dat(btree
), (*bh
)->b_blocknr
,
2306 if (buffer_nilfs_node(*bh
)) {
2307 node
= (struct nilfs_btree_node
*)(*bh
)->b_data
;
2308 key
= nilfs_btree_node_get_key(node
, 0);
2310 key
= nilfs_bmap_data_get_key(btree
, *bh
);
2312 /* on-disk format */
2313 binfo
->bi_v
.bi_vblocknr
= cpu_to_le64((*bh
)->b_blocknr
);
2314 binfo
->bi_v
.bi_blkoff
= cpu_to_le64(key
);
2319 static int nilfs_btree_mark(struct nilfs_bmap
*btree
, __u64 key
, int level
)
2321 struct buffer_head
*bh
;
2322 struct nilfs_btree_path
*path
;
2326 path
= nilfs_btree_alloc_path();
2330 ret
= nilfs_btree_do_lookup(btree
, path
, key
, &ptr
, level
+ 1, 0);
2332 WARN_ON(ret
== -ENOENT
);
2335 ret
= nilfs_btree_get_block(btree
, ptr
, &bh
);
2337 WARN_ON(ret
== -ENOENT
);
2341 if (!buffer_dirty(bh
))
2342 mark_buffer_dirty(bh
);
2344 if (!nilfs_bmap_dirty(btree
))
2345 nilfs_bmap_set_dirty(btree
);
2348 nilfs_btree_free_path(path
);
2352 static const struct nilfs_bmap_operations nilfs_btree_ops
= {
2353 .bop_lookup
= nilfs_btree_lookup
,
2354 .bop_lookup_contig
= nilfs_btree_lookup_contig
,
2355 .bop_insert
= nilfs_btree_insert
,
2356 .bop_delete
= nilfs_btree_delete
,
2359 .bop_propagate
= nilfs_btree_propagate
,
2361 .bop_lookup_dirty_buffers
= nilfs_btree_lookup_dirty_buffers
,
2363 .bop_assign
= nilfs_btree_assign
,
2364 .bop_mark
= nilfs_btree_mark
,
2366 .bop_seek_key
= nilfs_btree_seek_key
,
2367 .bop_last_key
= nilfs_btree_last_key
,
2369 .bop_check_insert
= NULL
,
2370 .bop_check_delete
= nilfs_btree_check_delete
,
2371 .bop_gather_data
= nilfs_btree_gather_data
,
2374 static const struct nilfs_bmap_operations nilfs_btree_ops_gc
= {
2376 .bop_lookup_contig
= NULL
,
2381 .bop_propagate
= nilfs_btree_propagate_gc
,
2383 .bop_lookup_dirty_buffers
= nilfs_btree_lookup_dirty_buffers
,
2385 .bop_assign
= nilfs_btree_assign_gc
,
2388 .bop_seek_key
= NULL
,
2389 .bop_last_key
= NULL
,
2391 .bop_check_insert
= NULL
,
2392 .bop_check_delete
= NULL
,
2393 .bop_gather_data
= NULL
,
2396 static void __nilfs_btree_init(struct nilfs_bmap
*bmap
)
2398 bmap
->b_ops
= &nilfs_btree_ops
;
2399 bmap
->b_nchildren_per_block
=
2400 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap
));
2403 int nilfs_btree_init(struct nilfs_bmap
*bmap
)
2407 __nilfs_btree_init(bmap
);
2409 if (nilfs_btree_root_broken(nilfs_btree_get_root(bmap
), bmap
->b_inode
))
2414 void nilfs_btree_init_gc(struct nilfs_bmap
*bmap
)
2416 bmap
->b_ops
= &nilfs_btree_ops_gc
;
2417 bmap
->b_nchildren_per_block
=
2418 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap
));