1ae98043fSRyusuke Konishi // SPDX-License-Identifier: GPL-2.0+
217c76b01SKoji Sato /*
394ee1d91SRyusuke Konishi * NILFS B-tree.
417c76b01SKoji Sato *
517c76b01SKoji Sato * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
617c76b01SKoji Sato *
74b420ab4SRyusuke Konishi * Written by Koji Sato.
817c76b01SKoji Sato */
917c76b01SKoji Sato
1017c76b01SKoji Sato #include <linux/slab.h>
1117c76b01SKoji Sato #include <linux/string.h>
1217c76b01SKoji Sato #include <linux/errno.h>
1317c76b01SKoji Sato #include <linux/pagevec.h>
1417c76b01SKoji Sato #include "nilfs.h"
1517c76b01SKoji Sato #include "page.h"
1617c76b01SKoji Sato #include "btnode.h"
1717c76b01SKoji Sato #include "btree.h"
1817c76b01SKoji Sato #include "alloc.h"
19c3a7abf0SRyusuke Konishi #include "dat.h"
2017c76b01SKoji Sato
21957ed60bSRyusuke Konishi static void __nilfs_btree_init(struct nilfs_bmap *bmap);
22957ed60bSRyusuke Konishi
nilfs_btree_alloc_path(void)23f905440fSLi Hong static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
2417c76b01SKoji Sato {
25f905440fSLi Hong struct nilfs_btree_path *path;
26f905440fSLi Hong int level = NILFS_BTREE_LEVEL_DATA;
2717c76b01SKoji Sato
28f905440fSLi Hong path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
29f905440fSLi Hong if (path == NULL)
30f905440fSLi Hong goto out;
3117c76b01SKoji Sato
32f905440fSLi Hong for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
3317c76b01SKoji Sato path[level].bp_bh = NULL;
3417c76b01SKoji Sato path[level].bp_sib_bh = NULL;
3517c76b01SKoji Sato path[level].bp_index = 0;
3617c76b01SKoji Sato path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
3717c76b01SKoji Sato path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
3817c76b01SKoji Sato path[level].bp_op = NULL;
3917c76b01SKoji Sato }
40f905440fSLi Hong
41f905440fSLi Hong out:
42f905440fSLi Hong return path;
43f905440fSLi Hong }
44f905440fSLi Hong
nilfs_btree_free_path(struct nilfs_btree_path * path)4573bb4886SLi Hong static void nilfs_btree_free_path(struct nilfs_btree_path *path)
46f905440fSLi Hong {
4773bb4886SLi Hong int level = NILFS_BTREE_LEVEL_DATA;
4817c76b01SKoji Sato
4973bb4886SLi Hong for (; level < NILFS_BTREE_LEVEL_MAX; level++)
50087d01b4SRyusuke Konishi brelse(path[level].bp_bh);
5173bb4886SLi Hong
5273bb4886SLi Hong kmem_cache_free(nilfs_btree_path_cache, path);
5317c76b01SKoji Sato }
5417c76b01SKoji Sato
5517c76b01SKoji Sato /*
5617c76b01SKoji Sato * B-tree node operations
5717c76b01SKoji Sato */
nilfs_btree_get_new_block(const struct nilfs_bmap * btree,__u64 ptr,struct buffer_head ** bhp)58e7c274f8SRyusuke Konishi static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
59f198dbb9SRyusuke Konishi __u64 ptr, struct buffer_head **bhp)
60f198dbb9SRyusuke Konishi {
61e897be17SRyusuke Konishi struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
62e897be17SRyusuke Konishi struct address_space *btnc = btnc_inode->i_mapping;
6345f4910bSRyusuke Konishi struct buffer_head *bh;
64f198dbb9SRyusuke Konishi
6545f4910bSRyusuke Konishi bh = nilfs_btnode_create_block(btnc, ptr);
6645f4910bSRyusuke Konishi if (!bh)
6745f4910bSRyusuke Konishi return -ENOMEM;
6845f4910bSRyusuke Konishi
6945f4910bSRyusuke Konishi set_buffer_nilfs_volatile(bh);
7045f4910bSRyusuke Konishi *bhp = bh;
7145f4910bSRyusuke Konishi return 0;
72f198dbb9SRyusuke Konishi }
7317c76b01SKoji Sato
nilfs_btree_node_get_flags(const struct nilfs_btree_node * node)747c397a81SRyusuke Konishi static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
7517c76b01SKoji Sato {
7617c76b01SKoji Sato return node->bn_flags;
7717c76b01SKoji Sato }
7817c76b01SKoji Sato
797c397a81SRyusuke Konishi static void
nilfs_btree_node_set_flags(struct nilfs_btree_node * node,int flags)806d28f7eaSRyusuke Konishi nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
8117c76b01SKoji Sato {
8217c76b01SKoji Sato node->bn_flags = flags;
8317c76b01SKoji Sato }
8417c76b01SKoji Sato
nilfs_btree_node_root(const struct nilfs_btree_node * node)857c397a81SRyusuke Konishi static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
8617c76b01SKoji Sato {
876d28f7eaSRyusuke Konishi return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
8817c76b01SKoji Sato }
8917c76b01SKoji Sato
nilfs_btree_node_get_level(const struct nilfs_btree_node * node)907c397a81SRyusuke Konishi static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
9117c76b01SKoji Sato {
9217c76b01SKoji Sato return node->bn_level;
9317c76b01SKoji Sato }
9417c76b01SKoji Sato
957c397a81SRyusuke Konishi static void
nilfs_btree_node_set_level(struct nilfs_btree_node * node,int level)966d28f7eaSRyusuke Konishi nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
9717c76b01SKoji Sato {
9817c76b01SKoji Sato node->bn_level = level;
9917c76b01SKoji Sato }
10017c76b01SKoji Sato
nilfs_btree_node_get_nchildren(const struct nilfs_btree_node * node)1017c397a81SRyusuke Konishi static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
10217c76b01SKoji Sato {
10317c76b01SKoji Sato return le16_to_cpu(node->bn_nchildren);
10417c76b01SKoji Sato }
10517c76b01SKoji Sato
1067c397a81SRyusuke Konishi static void
nilfs_btree_node_set_nchildren(struct nilfs_btree_node * node,int nchildren)1076d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
10817c76b01SKoji Sato {
10917c76b01SKoji Sato node->bn_nchildren = cpu_to_le16(nchildren);
11017c76b01SKoji Sato }
11117c76b01SKoji Sato
nilfs_btree_node_size(const struct nilfs_bmap * btree)1127c397a81SRyusuke Konishi static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
11317c76b01SKoji Sato {
114f3048d17SGeliang Tang return i_blocksize(btree->b_inode);
11517c76b01SKoji Sato }
11617c76b01SKoji Sato
nilfs_btree_nchildren_per_block(const struct nilfs_bmap * btree)1179b7b265cSRyusuke Konishi static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
11817c76b01SKoji Sato {
1195ad2686eSRyusuke Konishi return btree->b_nchildren_per_block;
12017c76b01SKoji Sato }
12117c76b01SKoji Sato
1227c397a81SRyusuke Konishi static __le64 *
nilfs_btree_node_dkeys(const struct nilfs_btree_node * node)1236d28f7eaSRyusuke Konishi nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
12417c76b01SKoji Sato {
12517c76b01SKoji Sato return (__le64 *)((char *)(node + 1) +
1266d28f7eaSRyusuke Konishi (nilfs_btree_node_root(node) ?
12717c76b01SKoji Sato 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
12817c76b01SKoji Sato }
12917c76b01SKoji Sato
1307c397a81SRyusuke Konishi static __le64 *
nilfs_btree_node_dptrs(const struct nilfs_btree_node * node,int ncmax)1319b7b265cSRyusuke Konishi nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
13217c76b01SKoji Sato {
1339b7b265cSRyusuke Konishi return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
13417c76b01SKoji Sato }
13517c76b01SKoji Sato
1367c397a81SRyusuke Konishi static __u64
nilfs_btree_node_get_key(const struct nilfs_btree_node * node,int index)1376d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
13817c76b01SKoji Sato {
13925b8d7deSRyusuke Konishi return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
14017c76b01SKoji Sato }
14117c76b01SKoji Sato
1427c397a81SRyusuke Konishi static void
nilfs_btree_node_set_key(struct nilfs_btree_node * node,int index,__u64 key)1436d28f7eaSRyusuke Konishi nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
14417c76b01SKoji Sato {
14525b8d7deSRyusuke Konishi *(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
14617c76b01SKoji Sato }
14717c76b01SKoji Sato
1487c397a81SRyusuke Konishi static __u64
nilfs_btree_node_get_ptr(const struct nilfs_btree_node * node,int index,int ncmax)1499b7b265cSRyusuke Konishi nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
1509b7b265cSRyusuke Konishi int ncmax)
15117c76b01SKoji Sato {
1529b7b265cSRyusuke Konishi return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
15317c76b01SKoji Sato }
15417c76b01SKoji Sato
1557c397a81SRyusuke Konishi static void
nilfs_btree_node_set_ptr(struct nilfs_btree_node * node,int index,__u64 ptr,int ncmax)1569b7b265cSRyusuke Konishi nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
1579b7b265cSRyusuke Konishi int ncmax)
15817c76b01SKoji Sato {
1599b7b265cSRyusuke Konishi *(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
16017c76b01SKoji Sato }
16117c76b01SKoji Sato
nilfs_btree_node_init(struct nilfs_btree_node * node,int flags,int level,int nchildren,int ncmax,const __u64 * keys,const __u64 * ptrs)1629b7b265cSRyusuke Konishi static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
1639b7b265cSRyusuke Konishi int level, int nchildren, int ncmax,
16417c76b01SKoji Sato const __u64 *keys, const __u64 *ptrs)
16517c76b01SKoji Sato {
16617c76b01SKoji Sato __le64 *dkeys;
16717c76b01SKoji Sato __le64 *dptrs;
16817c76b01SKoji Sato int i;
16917c76b01SKoji Sato
1706d28f7eaSRyusuke Konishi nilfs_btree_node_set_flags(node, flags);
1716d28f7eaSRyusuke Konishi nilfs_btree_node_set_level(node, level);
1726d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(node, nchildren);
17317c76b01SKoji Sato
1746d28f7eaSRyusuke Konishi dkeys = nilfs_btree_node_dkeys(node);
1759b7b265cSRyusuke Konishi dptrs = nilfs_btree_node_dptrs(node, ncmax);
17617c76b01SKoji Sato for (i = 0; i < nchildren; i++) {
17725b8d7deSRyusuke Konishi dkeys[i] = cpu_to_le64(keys[i]);
17825b8d7deSRyusuke Konishi dptrs[i] = cpu_to_le64(ptrs[i]);
17917c76b01SKoji Sato }
18017c76b01SKoji Sato }
18117c76b01SKoji Sato
18217c76b01SKoji Sato /* Assume the buffer heads corresponding to left and right are locked. */
nilfs_btree_node_move_left(struct nilfs_btree_node * left,struct nilfs_btree_node * right,int n,int lncmax,int rncmax)1839b7b265cSRyusuke Konishi static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
18417c76b01SKoji Sato struct nilfs_btree_node *right,
1859b7b265cSRyusuke Konishi int n, int lncmax, int rncmax)
18617c76b01SKoji Sato {
18717c76b01SKoji Sato __le64 *ldkeys, *rdkeys;
18817c76b01SKoji Sato __le64 *ldptrs, *rdptrs;
18917c76b01SKoji Sato int lnchildren, rnchildren;
19017c76b01SKoji Sato
1916d28f7eaSRyusuke Konishi ldkeys = nilfs_btree_node_dkeys(left);
1929b7b265cSRyusuke Konishi ldptrs = nilfs_btree_node_dptrs(left, lncmax);
1936d28f7eaSRyusuke Konishi lnchildren = nilfs_btree_node_get_nchildren(left);
19417c76b01SKoji Sato
1956d28f7eaSRyusuke Konishi rdkeys = nilfs_btree_node_dkeys(right);
1969b7b265cSRyusuke Konishi rdptrs = nilfs_btree_node_dptrs(right, rncmax);
1976d28f7eaSRyusuke Konishi rnchildren = nilfs_btree_node_get_nchildren(right);
19817c76b01SKoji Sato
19917c76b01SKoji Sato memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
20017c76b01SKoji Sato memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
20117c76b01SKoji Sato memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
20217c76b01SKoji Sato memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));
20317c76b01SKoji Sato
20417c76b01SKoji Sato lnchildren += n;
20517c76b01SKoji Sato rnchildren -= n;
2066d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(left, lnchildren);
2076d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(right, rnchildren);
20817c76b01SKoji Sato }
20917c76b01SKoji Sato
21017c76b01SKoji Sato /* Assume that the buffer heads corresponding to left and right are locked. */
nilfs_btree_node_move_right(struct nilfs_btree_node * left,struct nilfs_btree_node * right,int n,int lncmax,int rncmax)2119b7b265cSRyusuke Konishi static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
21217c76b01SKoji Sato struct nilfs_btree_node *right,
2139b7b265cSRyusuke Konishi int n, int lncmax, int rncmax)
21417c76b01SKoji Sato {
21517c76b01SKoji Sato __le64 *ldkeys, *rdkeys;
21617c76b01SKoji Sato __le64 *ldptrs, *rdptrs;
21717c76b01SKoji Sato int lnchildren, rnchildren;
21817c76b01SKoji Sato
2196d28f7eaSRyusuke Konishi ldkeys = nilfs_btree_node_dkeys(left);
2209b7b265cSRyusuke Konishi ldptrs = nilfs_btree_node_dptrs(left, lncmax);
2216d28f7eaSRyusuke Konishi lnchildren = nilfs_btree_node_get_nchildren(left);
22217c76b01SKoji Sato
2236d28f7eaSRyusuke Konishi rdkeys = nilfs_btree_node_dkeys(right);
2249b7b265cSRyusuke Konishi rdptrs = nilfs_btree_node_dptrs(right, rncmax);
2256d28f7eaSRyusuke Konishi rnchildren = nilfs_btree_node_get_nchildren(right);
22617c76b01SKoji Sato
22717c76b01SKoji Sato memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
22817c76b01SKoji Sato memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
22917c76b01SKoji Sato memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
23017c76b01SKoji Sato memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));
23117c76b01SKoji Sato
23217c76b01SKoji Sato lnchildren -= n;
23317c76b01SKoji Sato rnchildren += n;
2346d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(left, lnchildren);
2356d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(right, rnchildren);
23617c76b01SKoji Sato }
23717c76b01SKoji Sato
23817c76b01SKoji Sato /* Assume that the buffer head corresponding to node is locked. */
nilfs_btree_node_insert(struct nilfs_btree_node * node,int index,__u64 key,__u64 ptr,int ncmax)2399b7b265cSRyusuke Konishi static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
2409b7b265cSRyusuke Konishi __u64 key, __u64 ptr, int ncmax)
24117c76b01SKoji Sato {
24217c76b01SKoji Sato __le64 *dkeys;
24317c76b01SKoji Sato __le64 *dptrs;
24417c76b01SKoji Sato int nchildren;
24517c76b01SKoji Sato
2466d28f7eaSRyusuke Konishi dkeys = nilfs_btree_node_dkeys(node);
2479b7b265cSRyusuke Konishi dptrs = nilfs_btree_node_dptrs(node, ncmax);
2486d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
24917c76b01SKoji Sato if (index < nchildren) {
25017c76b01SKoji Sato memmove(dkeys + index + 1, dkeys + index,
25117c76b01SKoji Sato (nchildren - index) * sizeof(*dkeys));
25217c76b01SKoji Sato memmove(dptrs + index + 1, dptrs + index,
25317c76b01SKoji Sato (nchildren - index) * sizeof(*dptrs));
25417c76b01SKoji Sato }
25525b8d7deSRyusuke Konishi dkeys[index] = cpu_to_le64(key);
25625b8d7deSRyusuke Konishi dptrs[index] = cpu_to_le64(ptr);
25717c76b01SKoji Sato nchildren++;
2586d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(node, nchildren);
25917c76b01SKoji Sato }
26017c76b01SKoji Sato
26117c76b01SKoji Sato /* Assume that the buffer head corresponding to node is locked. */
nilfs_btree_node_delete(struct nilfs_btree_node * node,int index,__u64 * keyp,__u64 * ptrp,int ncmax)2629b7b265cSRyusuke Konishi static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
2639b7b265cSRyusuke Konishi __u64 *keyp, __u64 *ptrp, int ncmax)
26417c76b01SKoji Sato {
26517c76b01SKoji Sato __u64 key;
26617c76b01SKoji Sato __u64 ptr;
26717c76b01SKoji Sato __le64 *dkeys;
26817c76b01SKoji Sato __le64 *dptrs;
26917c76b01SKoji Sato int nchildren;
27017c76b01SKoji Sato
2716d28f7eaSRyusuke Konishi dkeys = nilfs_btree_node_dkeys(node);
2729b7b265cSRyusuke Konishi dptrs = nilfs_btree_node_dptrs(node, ncmax);
27325b8d7deSRyusuke Konishi key = le64_to_cpu(dkeys[index]);
27425b8d7deSRyusuke Konishi ptr = le64_to_cpu(dptrs[index]);
2756d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
27617c76b01SKoji Sato if (keyp != NULL)
27717c76b01SKoji Sato *keyp = key;
27817c76b01SKoji Sato if (ptrp != NULL)
27917c76b01SKoji Sato *ptrp = ptr;
28017c76b01SKoji Sato
28117c76b01SKoji Sato if (index < nchildren - 1) {
28217c76b01SKoji Sato memmove(dkeys + index, dkeys + index + 1,
28317c76b01SKoji Sato (nchildren - index - 1) * sizeof(*dkeys));
28417c76b01SKoji Sato memmove(dptrs + index, dptrs + index + 1,
28517c76b01SKoji Sato (nchildren - index - 1) * sizeof(*dptrs));
28617c76b01SKoji Sato }
28717c76b01SKoji Sato nchildren--;
2886d28f7eaSRyusuke Konishi nilfs_btree_node_set_nchildren(node, nchildren);
28917c76b01SKoji Sato }
29017c76b01SKoji Sato
nilfs_btree_node_lookup(const struct nilfs_btree_node * node,__u64 key,int * indexp)2916d28f7eaSRyusuke Konishi static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
29217c76b01SKoji Sato __u64 key, int *indexp)
29317c76b01SKoji Sato {
29417c76b01SKoji Sato __u64 nkey;
29517c76b01SKoji Sato int index, low, high, s;
29617c76b01SKoji Sato
29717c76b01SKoji Sato /* binary search */
29817c76b01SKoji Sato low = 0;
2996d28f7eaSRyusuke Konishi high = nilfs_btree_node_get_nchildren(node) - 1;
30017c76b01SKoji Sato index = 0;
30117c76b01SKoji Sato s = 0;
30217c76b01SKoji Sato while (low <= high) {
30317c76b01SKoji Sato index = (low + high) / 2;
3046d28f7eaSRyusuke Konishi nkey = nilfs_btree_node_get_key(node, index);
30517c76b01SKoji Sato if (nkey == key) {
30617c76b01SKoji Sato s = 0;
30717c76b01SKoji Sato goto out;
30817c76b01SKoji Sato } else if (nkey < key) {
30917c76b01SKoji Sato low = index + 1;
31017c76b01SKoji Sato s = -1;
31117c76b01SKoji Sato } else {
31217c76b01SKoji Sato high = index - 1;
31317c76b01SKoji Sato s = 1;
31417c76b01SKoji Sato }
31517c76b01SKoji Sato }
31617c76b01SKoji Sato
31717c76b01SKoji Sato /* adjust index */
3186d28f7eaSRyusuke Konishi if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
3196d28f7eaSRyusuke Konishi if (s > 0 && index > 0)
32017c76b01SKoji Sato index--;
32117c76b01SKoji Sato } else if (s < 0)
32217c76b01SKoji Sato index++;
32317c76b01SKoji Sato
32417c76b01SKoji Sato out:
32517c76b01SKoji Sato *indexp = index;
32617c76b01SKoji Sato
32717c76b01SKoji Sato return s == 0;
32817c76b01SKoji Sato }
32917c76b01SKoji Sato
3301d5385b9SRyusuke Konishi /**
3311d5385b9SRyusuke Konishi * nilfs_btree_node_broken - verify consistency of btree node
3321d5385b9SRyusuke Konishi * @node: btree node block to be examined
3331d5385b9SRyusuke Konishi * @size: node size (in bytes)
334feee880fSRyusuke Konishi * @inode: host inode of btree
3351d5385b9SRyusuke Konishi * @blocknr: block number
3361d5385b9SRyusuke Konishi *
3371d5385b9SRyusuke Konishi * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
3381d5385b9SRyusuke Konishi */
nilfs_btree_node_broken(const struct nilfs_btree_node * node,size_t size,struct inode * inode,sector_t blocknr)3391d5385b9SRyusuke Konishi static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
340feee880fSRyusuke Konishi size_t size, struct inode *inode,
341feee880fSRyusuke Konishi sector_t blocknr)
3421d5385b9SRyusuke Konishi {
3431d5385b9SRyusuke Konishi int level, flags, nchildren;
3441d5385b9SRyusuke Konishi int ret = 0;
3451d5385b9SRyusuke Konishi
3461d5385b9SRyusuke Konishi level = nilfs_btree_node_get_level(node);
3471d5385b9SRyusuke Konishi flags = nilfs_btree_node_get_flags(node);
3481d5385b9SRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
3491d5385b9SRyusuke Konishi
3501d5385b9SRyusuke Konishi if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
3511d5385b9SRyusuke Konishi level >= NILFS_BTREE_LEVEL_MAX ||
3521d5385b9SRyusuke Konishi (flags & NILFS_BTREE_NODE_ROOT) ||
3531d5385b9SRyusuke Konishi nchildren < 0 ||
3541d5385b9SRyusuke Konishi nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
355a1d0747aSJoe Perches nilfs_crit(inode->i_sb,
356feee880fSRyusuke Konishi "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d",
357feee880fSRyusuke Konishi inode->i_ino, (unsigned long long)blocknr, level,
358feee880fSRyusuke Konishi flags, nchildren);
3591d5385b9SRyusuke Konishi ret = 1;
3601d5385b9SRyusuke Konishi }
3611d5385b9SRyusuke Konishi return ret;
3621d5385b9SRyusuke Konishi }
3631d5385b9SRyusuke Konishi
364957ed60bSRyusuke Konishi /**
365957ed60bSRyusuke Konishi * nilfs_btree_root_broken - verify consistency of btree root node
366957ed60bSRyusuke Konishi * @node: btree root node to be examined
367feee880fSRyusuke Konishi * @inode: host inode of btree
368957ed60bSRyusuke Konishi *
369957ed60bSRyusuke Konishi * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
370957ed60bSRyusuke Konishi */
nilfs_btree_root_broken(const struct nilfs_btree_node * node,struct inode * inode)371957ed60bSRyusuke Konishi static int nilfs_btree_root_broken(const struct nilfs_btree_node *node,
372feee880fSRyusuke Konishi struct inode *inode)
373957ed60bSRyusuke Konishi {
374957ed60bSRyusuke Konishi int level, flags, nchildren;
375957ed60bSRyusuke Konishi int ret = 0;
376957ed60bSRyusuke Konishi
377957ed60bSRyusuke Konishi level = nilfs_btree_node_get_level(node);
378957ed60bSRyusuke Konishi flags = nilfs_btree_node_get_flags(node);
379957ed60bSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
380957ed60bSRyusuke Konishi
381957ed60bSRyusuke Konishi if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
382d8fd150fSRyusuke Konishi level >= NILFS_BTREE_LEVEL_MAX ||
383957ed60bSRyusuke Konishi nchildren < 0 ||
384957ed60bSRyusuke Konishi nchildren > NILFS_BTREE_ROOT_NCHILDREN_MAX)) {
385a1d0747aSJoe Perches nilfs_crit(inode->i_sb,
386feee880fSRyusuke Konishi "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d",
387feee880fSRyusuke Konishi inode->i_ino, level, flags, nchildren);
388957ed60bSRyusuke Konishi ret = 1;
389957ed60bSRyusuke Konishi }
390957ed60bSRyusuke Konishi return ret;
391957ed60bSRyusuke Konishi }
392957ed60bSRyusuke Konishi
nilfs_btree_broken_node_block(struct buffer_head * bh)3931d5385b9SRyusuke Konishi int nilfs_btree_broken_node_block(struct buffer_head *bh)
3941d5385b9SRyusuke Konishi {
395feee880fSRyusuke Konishi struct inode *inode;
3964e13e66bSRyusuke Konishi int ret;
3974e13e66bSRyusuke Konishi
3984e13e66bSRyusuke Konishi if (buffer_nilfs_checked(bh))
3994e13e66bSRyusuke Konishi return 0;
4004e13e66bSRyusuke Konishi
4016ad4cd7fSMatthew Wilcox (Oracle) inode = bh->b_folio->mapping->host;
4024e13e66bSRyusuke Konishi ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
403feee880fSRyusuke Konishi bh->b_size, inode, bh->b_blocknr);
4044e13e66bSRyusuke Konishi if (likely(!ret))
4054e13e66bSRyusuke Konishi set_buffer_nilfs_checked(bh);
4064e13e66bSRyusuke Konishi return ret;
4071d5385b9SRyusuke Konishi }
4081d5385b9SRyusuke Konishi
4097c397a81SRyusuke Konishi static struct nilfs_btree_node *
nilfs_btree_get_root(const struct nilfs_bmap * btree)410e7c274f8SRyusuke Konishi nilfs_btree_get_root(const struct nilfs_bmap *btree)
41117c76b01SKoji Sato {
412e7c274f8SRyusuke Konishi return (struct nilfs_btree_node *)btree->b_u.u_data;
41317c76b01SKoji Sato }
41417c76b01SKoji Sato
4157c397a81SRyusuke Konishi static struct nilfs_btree_node *
nilfs_btree_get_nonroot_node(const struct nilfs_btree_path * path,int level)4166d28f7eaSRyusuke Konishi nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
41717c76b01SKoji Sato {
41817c76b01SKoji Sato return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
41917c76b01SKoji Sato }
42017c76b01SKoji Sato
4217c397a81SRyusuke Konishi static struct nilfs_btree_node *
nilfs_btree_get_sib_node(const struct nilfs_btree_path * path,int level)4226d28f7eaSRyusuke Konishi nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
42317c76b01SKoji Sato {
42417c76b01SKoji Sato return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
42517c76b01SKoji Sato }
42617c76b01SKoji Sato
nilfs_btree_height(const struct nilfs_bmap * btree)4277c397a81SRyusuke Konishi static int nilfs_btree_height(const struct nilfs_bmap *btree)
42817c76b01SKoji Sato {
4296d28f7eaSRyusuke Konishi return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
43017c76b01SKoji Sato }
43117c76b01SKoji Sato
4329b7b265cSRyusuke Konishi static struct nilfs_btree_node *
nilfs_btree_get_node(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path,int level,int * ncmaxp)433e7c274f8SRyusuke Konishi nilfs_btree_get_node(const struct nilfs_bmap *btree,
43417c76b01SKoji Sato const struct nilfs_btree_path *path,
4359b7b265cSRyusuke Konishi int level, int *ncmaxp)
43617c76b01SKoji Sato {
4379b7b265cSRyusuke Konishi struct nilfs_btree_node *node;
4389b7b265cSRyusuke Konishi
4399b7b265cSRyusuke Konishi if (level == nilfs_btree_height(btree) - 1) {
4409b7b265cSRyusuke Konishi node = nilfs_btree_get_root(btree);
4419b7b265cSRyusuke Konishi *ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
4429b7b265cSRyusuke Konishi } else {
4439b7b265cSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
4449b7b265cSRyusuke Konishi *ncmaxp = nilfs_btree_nchildren_per_block(btree);
4459b7b265cSRyusuke Konishi }
4469b7b265cSRyusuke Konishi return node;
44717c76b01SKoji Sato }
44817c76b01SKoji Sato
nilfs_btree_bad_node(const struct nilfs_bmap * btree,struct nilfs_btree_node * node,int level)449feee880fSRyusuke Konishi static int nilfs_btree_bad_node(const struct nilfs_bmap *btree,
450feee880fSRyusuke Konishi struct nilfs_btree_node *node, int level)
4519b945d53SRyusuke Konishi {
4529b945d53SRyusuke Konishi if (unlikely(nilfs_btree_node_get_level(node) != level)) {
4539b945d53SRyusuke Konishi dump_stack();
454a1d0747aSJoe Perches nilfs_crit(btree->b_inode->i_sb,
455feee880fSRyusuke Konishi "btree level mismatch (ino=%lu): %d != %d",
456feee880fSRyusuke Konishi btree->b_inode->i_ino,
4579b945d53SRyusuke Konishi nilfs_btree_node_get_level(node), level);
4589b945d53SRyusuke Konishi return 1;
4599b945d53SRyusuke Konishi }
4609b945d53SRyusuke Konishi return 0;
4619b945d53SRyusuke Konishi }
4629b945d53SRyusuke Konishi
463464ece88SRyusuke Konishi struct nilfs_btree_readahead_info {
464464ece88SRyusuke Konishi struct nilfs_btree_node *node; /* parent node */
465464ece88SRyusuke Konishi int max_ra_blocks; /* max nof blocks to read ahead */
466464ece88SRyusuke Konishi int index; /* current index on the parent node */
467464ece88SRyusuke Konishi int ncmax; /* nof children in the parent node */
468464ece88SRyusuke Konishi };
469464ece88SRyusuke Konishi
__nilfs_btree_get_block(const struct nilfs_bmap * btree,__u64 ptr,struct buffer_head ** bhp,const struct nilfs_btree_readahead_info * ra)470464ece88SRyusuke Konishi static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
471464ece88SRyusuke Konishi struct buffer_head **bhp,
472464ece88SRyusuke Konishi const struct nilfs_btree_readahead_info *ra)
473464ece88SRyusuke Konishi {
474e897be17SRyusuke Konishi struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
475e897be17SRyusuke Konishi struct address_space *btnc = btnc_inode->i_mapping;
476464ece88SRyusuke Konishi struct buffer_head *bh, *ra_bh;
477464ece88SRyusuke Konishi sector_t submit_ptr = 0;
478464ece88SRyusuke Konishi int ret;
479464ece88SRyusuke Konishi
480ed451259SBart Van Assche ret = nilfs_btnode_submit_block(btnc, ptr, 0, REQ_OP_READ, &bh,
4812a222ca9SMike Christie &submit_ptr);
482464ece88SRyusuke Konishi if (ret) {
4837633355eSRyusuke Konishi if (likely(ret == -EEXIST))
484464ece88SRyusuke Konishi goto out_check;
4857633355eSRyusuke Konishi if (ret == -ENOENT) {
4867633355eSRyusuke Konishi /*
4877633355eSRyusuke Konishi * Block address translation failed due to invalid
4887633355eSRyusuke Konishi * value of 'ptr'. In this case, return internal code
4897633355eSRyusuke Konishi * -EINVAL (broken bmap) to notify bmap layer of fatal
4907633355eSRyusuke Konishi * metadata corruption.
4917633355eSRyusuke Konishi */
4927633355eSRyusuke Konishi ret = -EINVAL;
4937633355eSRyusuke Konishi }
4947633355eSRyusuke Konishi return ret;
495464ece88SRyusuke Konishi }
496464ece88SRyusuke Konishi
497464ece88SRyusuke Konishi if (ra) {
498464ece88SRyusuke Konishi int i, n;
499464ece88SRyusuke Konishi __u64 ptr2;
500464ece88SRyusuke Konishi
501464ece88SRyusuke Konishi /* read ahead sibling nodes */
502464ece88SRyusuke Konishi for (n = ra->max_ra_blocks, i = ra->index + 1;
503464ece88SRyusuke Konishi n > 0 && i < ra->ncmax; n--, i++) {
504464ece88SRyusuke Konishi ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);
505464ece88SRyusuke Konishi
5062a222ca9SMike Christie ret = nilfs_btnode_submit_block(btnc, ptr2, 0,
507ed451259SBart Van Assche REQ_OP_READ | REQ_RAHEAD,
508464ece88SRyusuke Konishi &ra_bh, &submit_ptr);
509464ece88SRyusuke Konishi if (likely(!ret || ret == -EEXIST))
510464ece88SRyusuke Konishi brelse(ra_bh);
511464ece88SRyusuke Konishi else if (ret != -EBUSY)
512464ece88SRyusuke Konishi break;
513464ece88SRyusuke Konishi if (!buffer_locked(bh))
514464ece88SRyusuke Konishi goto out_no_wait;
515464ece88SRyusuke Konishi }
516464ece88SRyusuke Konishi }
517464ece88SRyusuke Konishi
518464ece88SRyusuke Konishi wait_on_buffer(bh);
519464ece88SRyusuke Konishi
520464ece88SRyusuke Konishi out_no_wait:
521464ece88SRyusuke Konishi if (!buffer_uptodate(bh)) {
522a1d0747aSJoe Perches nilfs_err(btree->b_inode->i_sb,
52339a9dccaSRyusuke Konishi "I/O error reading b-tree node block (ino=%lu, blocknr=%llu)",
52439a9dccaSRyusuke Konishi btree->b_inode->i_ino, (unsigned long long)ptr);
525464ece88SRyusuke Konishi brelse(bh);
526464ece88SRyusuke Konishi return -EIO;
527464ece88SRyusuke Konishi }
528464ece88SRyusuke Konishi
529464ece88SRyusuke Konishi out_check:
530464ece88SRyusuke Konishi if (nilfs_btree_broken_node_block(bh)) {
531464ece88SRyusuke Konishi clear_buffer_uptodate(bh);
532464ece88SRyusuke Konishi brelse(bh);
533464ece88SRyusuke Konishi return -EINVAL;
534464ece88SRyusuke Konishi }
535464ece88SRyusuke Konishi
536464ece88SRyusuke Konishi *bhp = bh;
537464ece88SRyusuke Konishi return 0;
538464ece88SRyusuke Konishi }
539464ece88SRyusuke Konishi
nilfs_btree_get_block(const struct nilfs_bmap * btree,__u64 ptr,struct buffer_head ** bhp)540464ece88SRyusuke Konishi static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
541464ece88SRyusuke Konishi struct buffer_head **bhp)
542464ece88SRyusuke Konishi {
543464ece88SRyusuke Konishi return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
544464ece88SRyusuke Konishi }
545464ece88SRyusuke Konishi
nilfs_btree_do_lookup(const struct nilfs_bmap * btree,struct nilfs_btree_path * path,__u64 key,__u64 * ptrp,int minlevel,int readahead)546e7c274f8SRyusuke Konishi static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
54717c76b01SKoji Sato struct nilfs_btree_path *path,
54803bdb5acSRyusuke Konishi __u64 key, __u64 *ptrp, int minlevel,
54903bdb5acSRyusuke Konishi int readahead)
55017c76b01SKoji Sato {
55117c76b01SKoji Sato struct nilfs_btree_node *node;
55203bdb5acSRyusuke Konishi struct nilfs_btree_readahead_info p, *ra;
55317c76b01SKoji Sato __u64 ptr;
554ea64ab87SRyusuke Konishi int level, index, found, ncmax, ret;
55517c76b01SKoji Sato
55617c76b01SKoji Sato node = nilfs_btree_get_root(btree);
5576d28f7eaSRyusuke Konishi level = nilfs_btree_node_get_level(node);
5586d28f7eaSRyusuke Konishi if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
55917c76b01SKoji Sato return -ENOENT;
56017c76b01SKoji Sato
5616d28f7eaSRyusuke Konishi found = nilfs_btree_node_lookup(node, key, &index);
5629b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(node, index,
5639b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
56417c76b01SKoji Sato path[level].bp_bh = NULL;
56517c76b01SKoji Sato path[level].bp_index = index;
56617c76b01SKoji Sato
5679b7b265cSRyusuke Konishi ncmax = nilfs_btree_nchildren_per_block(btree);
568ea64ab87SRyusuke Konishi
56903bdb5acSRyusuke Konishi while (--level >= minlevel) {
57003bdb5acSRyusuke Konishi ra = NULL;
57103bdb5acSRyusuke Konishi if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
57203bdb5acSRyusuke Konishi p.node = nilfs_btree_get_node(btree, path, level + 1,
57303bdb5acSRyusuke Konishi &p.ncmax);
57403bdb5acSRyusuke Konishi p.index = index;
57503bdb5acSRyusuke Konishi p.max_ra_blocks = 7;
57603bdb5acSRyusuke Konishi ra = &p;
57703bdb5acSRyusuke Konishi }
57803bdb5acSRyusuke Konishi ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
57903bdb5acSRyusuke Konishi ra);
58017c76b01SKoji Sato if (ret < 0)
58117c76b01SKoji Sato return ret;
58203bdb5acSRyusuke Konishi
5836d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
584feee880fSRyusuke Konishi if (nilfs_btree_bad_node(btree, node, level))
5859b945d53SRyusuke Konishi return -EINVAL;
58617c76b01SKoji Sato if (!found)
5876d28f7eaSRyusuke Konishi found = nilfs_btree_node_lookup(node, key, &index);
58817c76b01SKoji Sato else
58917c76b01SKoji Sato index = 0;
590ea64ab87SRyusuke Konishi if (index < ncmax) {
5919b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
592ea64ab87SRyusuke Konishi } else {
5931f5abe7eSRyusuke Konishi WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
59417c76b01SKoji Sato /* insert */
59517c76b01SKoji Sato ptr = NILFS_BMAP_INVALID_PTR;
59617c76b01SKoji Sato }
59717c76b01SKoji Sato path[level].bp_index = index;
59817c76b01SKoji Sato }
59917c76b01SKoji Sato if (!found)
60017c76b01SKoji Sato return -ENOENT;
60117c76b01SKoji Sato
60217c76b01SKoji Sato if (ptrp != NULL)
60317c76b01SKoji Sato *ptrp = ptr;
60417c76b01SKoji Sato
60517c76b01SKoji Sato return 0;
60617c76b01SKoji Sato }
60717c76b01SKoji Sato
nilfs_btree_do_lookup_last(const struct nilfs_bmap * btree,struct nilfs_btree_path * path,__u64 * keyp,__u64 * ptrp)608e7c274f8SRyusuke Konishi static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
60917c76b01SKoji Sato struct nilfs_btree_path *path,
61017c76b01SKoji Sato __u64 *keyp, __u64 *ptrp)
61117c76b01SKoji Sato {
61217c76b01SKoji Sato struct nilfs_btree_node *node;
61317c76b01SKoji Sato __u64 ptr;
6149b7b265cSRyusuke Konishi int index, level, ncmax, ret;
61517c76b01SKoji Sato
61617c76b01SKoji Sato node = nilfs_btree_get_root(btree);
6176d28f7eaSRyusuke Konishi index = nilfs_btree_node_get_nchildren(node) - 1;
61817c76b01SKoji Sato if (index < 0)
61917c76b01SKoji Sato return -ENOENT;
6206d28f7eaSRyusuke Konishi level = nilfs_btree_node_get_level(node);
6219b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(node, index,
6229b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
62317c76b01SKoji Sato path[level].bp_bh = NULL;
62417c76b01SKoji Sato path[level].bp_index = index;
6259b7b265cSRyusuke Konishi ncmax = nilfs_btree_nchildren_per_block(btree);
62617c76b01SKoji Sato
62717c76b01SKoji Sato for (level--; level > 0; level--) {
628f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
62917c76b01SKoji Sato if (ret < 0)
63017c76b01SKoji Sato return ret;
6316d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
632feee880fSRyusuke Konishi if (nilfs_btree_bad_node(btree, node, level))
6339b945d53SRyusuke Konishi return -EINVAL;
6346d28f7eaSRyusuke Konishi index = nilfs_btree_node_get_nchildren(node) - 1;
6359b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
63617c76b01SKoji Sato path[level].bp_index = index;
63717c76b01SKoji Sato }
63817c76b01SKoji Sato
63917c76b01SKoji Sato if (keyp != NULL)
6406d28f7eaSRyusuke Konishi *keyp = nilfs_btree_node_get_key(node, index);
64117c76b01SKoji Sato if (ptrp != NULL)
64217c76b01SKoji Sato *ptrp = ptr;
64317c76b01SKoji Sato
64417c76b01SKoji Sato return 0;
64517c76b01SKoji Sato }
64617c76b01SKoji Sato
6475b20384fSRyusuke Konishi /**
6485b20384fSRyusuke Konishi * nilfs_btree_get_next_key - get next valid key from btree path array
6495b20384fSRyusuke Konishi * @btree: bmap struct of btree
6505b20384fSRyusuke Konishi * @path: array of nilfs_btree_path struct
6515b20384fSRyusuke Konishi * @minlevel: start level
6525b20384fSRyusuke Konishi * @nextkey: place to store the next valid key
6535b20384fSRyusuke Konishi *
6545b20384fSRyusuke Konishi * Return Value: If a next key was found, 0 is returned. Otherwise,
6555b20384fSRyusuke Konishi * -ENOENT is returned.
6565b20384fSRyusuke Konishi */
nilfs_btree_get_next_key(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path,int minlevel,__u64 * nextkey)6575b20384fSRyusuke Konishi static int nilfs_btree_get_next_key(const struct nilfs_bmap *btree,
6585b20384fSRyusuke Konishi const struct nilfs_btree_path *path,
6595b20384fSRyusuke Konishi int minlevel, __u64 *nextkey)
6605b20384fSRyusuke Konishi {
6615b20384fSRyusuke Konishi struct nilfs_btree_node *node;
6625b20384fSRyusuke Konishi int maxlevel = nilfs_btree_height(btree) - 1;
6635b20384fSRyusuke Konishi int index, next_adj, level;
6645b20384fSRyusuke Konishi
6655b20384fSRyusuke Konishi /* Next index is already set to bp_index for leaf nodes. */
6665b20384fSRyusuke Konishi next_adj = 0;
6675b20384fSRyusuke Konishi for (level = minlevel; level <= maxlevel; level++) {
6685b20384fSRyusuke Konishi if (level == maxlevel)
6695b20384fSRyusuke Konishi node = nilfs_btree_get_root(btree);
6705b20384fSRyusuke Konishi else
6715b20384fSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
6725b20384fSRyusuke Konishi
6735b20384fSRyusuke Konishi index = path[level].bp_index + next_adj;
6745b20384fSRyusuke Konishi if (index < nilfs_btree_node_get_nchildren(node)) {
6755b20384fSRyusuke Konishi /* Next key is in this node */
6765b20384fSRyusuke Konishi *nextkey = nilfs_btree_node_get_key(node, index);
6775b20384fSRyusuke Konishi return 0;
6785b20384fSRyusuke Konishi }
6795b20384fSRyusuke Konishi /* For non-leaf nodes, next index is stored at bp_index + 1. */
6805b20384fSRyusuke Konishi next_adj = 1;
6815b20384fSRyusuke Konishi }
6825b20384fSRyusuke Konishi return -ENOENT;
6835b20384fSRyusuke Konishi }
6845b20384fSRyusuke Konishi
nilfs_btree_lookup(const struct nilfs_bmap * btree,__u64 key,int level,__u64 * ptrp)685e7c274f8SRyusuke Konishi static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
68617c76b01SKoji Sato __u64 key, int level, __u64 *ptrp)
68717c76b01SKoji Sato {
68817c76b01SKoji Sato struct nilfs_btree_path *path;
68917c76b01SKoji Sato int ret;
69017c76b01SKoji Sato
6916d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
69217c76b01SKoji Sato if (path == NULL)
69317c76b01SKoji Sato return -ENOMEM;
69417c76b01SKoji Sato
69503bdb5acSRyusuke Konishi ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
69617c76b01SKoji Sato
6976d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
69817c76b01SKoji Sato
69917c76b01SKoji Sato return ret;
70017c76b01SKoji Sato }
70117c76b01SKoji Sato
nilfs_btree_lookup_contig(const struct nilfs_bmap * btree,__u64 key,__u64 * ptrp,unsigned int maxblocks)702e7c274f8SRyusuke Konishi static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
7030c6c44cbSRyusuke Konishi __u64 key, __u64 *ptrp,
7040c6c44cbSRyusuke Konishi unsigned int maxblocks)
705c3a7abf0SRyusuke Konishi {
706c3a7abf0SRyusuke Konishi struct nilfs_btree_path *path;
707c3a7abf0SRyusuke Konishi struct nilfs_btree_node *node;
708c3a7abf0SRyusuke Konishi struct inode *dat = NULL;
709c3a7abf0SRyusuke Konishi __u64 ptr, ptr2;
710c3a7abf0SRyusuke Konishi sector_t blocknr;
711c3a7abf0SRyusuke Konishi int level = NILFS_BTREE_LEVEL_NODE_MIN;
7129b7b265cSRyusuke Konishi int ret, cnt, index, maxlevel, ncmax;
71303bdb5acSRyusuke Konishi struct nilfs_btree_readahead_info p;
714c3a7abf0SRyusuke Konishi
7156d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
716c3a7abf0SRyusuke Konishi if (path == NULL)
717c3a7abf0SRyusuke Konishi return -ENOMEM;
718f905440fSLi Hong
71903bdb5acSRyusuke Konishi ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
720c3a7abf0SRyusuke Konishi if (ret < 0)
721c3a7abf0SRyusuke Konishi goto out;
722c3a7abf0SRyusuke Konishi
723e7c274f8SRyusuke Konishi if (NILFS_BMAP_USE_VBN(btree)) {
724e7c274f8SRyusuke Konishi dat = nilfs_bmap_get_dat(btree);
725c3a7abf0SRyusuke Konishi ret = nilfs_dat_translate(dat, ptr, &blocknr);
726c3a7abf0SRyusuke Konishi if (ret < 0)
727f69e8139SRyusuke Konishi goto dat_error;
728c3a7abf0SRyusuke Konishi ptr = blocknr;
729c3a7abf0SRyusuke Konishi }
730c3a7abf0SRyusuke Konishi cnt = 1;
731c3a7abf0SRyusuke Konishi if (cnt == maxblocks)
732c3a7abf0SRyusuke Konishi goto end;
733c3a7abf0SRyusuke Konishi
734c3a7abf0SRyusuke Konishi maxlevel = nilfs_btree_height(btree) - 1;
7359b7b265cSRyusuke Konishi node = nilfs_btree_get_node(btree, path, level, &ncmax);
736c3a7abf0SRyusuke Konishi index = path[level].bp_index + 1;
737c3a7abf0SRyusuke Konishi for (;;) {
7386d28f7eaSRyusuke Konishi while (index < nilfs_btree_node_get_nchildren(node)) {
7396d28f7eaSRyusuke Konishi if (nilfs_btree_node_get_key(node, index) !=
740c3a7abf0SRyusuke Konishi key + cnt)
741c3a7abf0SRyusuke Konishi goto end;
7429b7b265cSRyusuke Konishi ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax);
743c3a7abf0SRyusuke Konishi if (dat) {
744c3a7abf0SRyusuke Konishi ret = nilfs_dat_translate(dat, ptr2, &blocknr);
745c3a7abf0SRyusuke Konishi if (ret < 0)
746f69e8139SRyusuke Konishi goto dat_error;
747c3a7abf0SRyusuke Konishi ptr2 = blocknr;
748c3a7abf0SRyusuke Konishi }
749c3a7abf0SRyusuke Konishi if (ptr2 != ptr + cnt || ++cnt == maxblocks)
750c3a7abf0SRyusuke Konishi goto end;
751c3a7abf0SRyusuke Konishi index++;
752c3a7abf0SRyusuke Konishi }
753c3a7abf0SRyusuke Konishi if (level == maxlevel)
754c3a7abf0SRyusuke Konishi break;
755c3a7abf0SRyusuke Konishi
756c3a7abf0SRyusuke Konishi /* look-up right sibling node */
75703bdb5acSRyusuke Konishi p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
75803bdb5acSRyusuke Konishi p.index = path[level + 1].bp_index + 1;
75903bdb5acSRyusuke Konishi p.max_ra_blocks = 7;
76003bdb5acSRyusuke Konishi if (p.index >= nilfs_btree_node_get_nchildren(p.node) ||
76103bdb5acSRyusuke Konishi nilfs_btree_node_get_key(p.node, p.index) != key + cnt)
762c3a7abf0SRyusuke Konishi break;
76303bdb5acSRyusuke Konishi ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax);
76403bdb5acSRyusuke Konishi path[level + 1].bp_index = p.index;
765c3a7abf0SRyusuke Konishi
766c3a7abf0SRyusuke Konishi brelse(path[level].bp_bh);
767c3a7abf0SRyusuke Konishi path[level].bp_bh = NULL;
76803bdb5acSRyusuke Konishi
76903bdb5acSRyusuke Konishi ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
77003bdb5acSRyusuke Konishi &p);
771c3a7abf0SRyusuke Konishi if (ret < 0)
772c3a7abf0SRyusuke Konishi goto out;
7736d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
7749b7b265cSRyusuke Konishi ncmax = nilfs_btree_nchildren_per_block(btree);
775c3a7abf0SRyusuke Konishi index = 0;
776c3a7abf0SRyusuke Konishi path[level].bp_index = index;
777c3a7abf0SRyusuke Konishi }
778c3a7abf0SRyusuke Konishi end:
779c3a7abf0SRyusuke Konishi *ptrp = ptr;
780c3a7abf0SRyusuke Konishi ret = cnt;
781c3a7abf0SRyusuke Konishi out:
7826d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
783c3a7abf0SRyusuke Konishi return ret;
784f69e8139SRyusuke Konishi
785f69e8139SRyusuke Konishi dat_error:
786f69e8139SRyusuke Konishi if (ret == -ENOENT)
787f69e8139SRyusuke Konishi ret = -EINVAL; /* Notify bmap layer of metadata corruption */
788f69e8139SRyusuke Konishi goto out;
789c3a7abf0SRyusuke Konishi }
790c3a7abf0SRyusuke Konishi
nilfs_btree_promote_key(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 key)791e7c274f8SRyusuke Konishi static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
79217c76b01SKoji Sato struct nilfs_btree_path *path,
79317c76b01SKoji Sato int level, __u64 key)
79417c76b01SKoji Sato {
79517c76b01SKoji Sato if (level < nilfs_btree_height(btree) - 1) {
79617c76b01SKoji Sato do {
79717c76b01SKoji Sato nilfs_btree_node_set_key(
7986d28f7eaSRyusuke Konishi nilfs_btree_get_nonroot_node(path, level),
79917c76b01SKoji Sato path[level].bp_index, key);
80017c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
8015fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
80217c76b01SKoji Sato } while ((path[level].bp_index == 0) &&
80317c76b01SKoji Sato (++level < nilfs_btree_height(btree) - 1));
80417c76b01SKoji Sato }
80517c76b01SKoji Sato
80617c76b01SKoji Sato /* root */
80717c76b01SKoji Sato if (level == nilfs_btree_height(btree) - 1) {
8086d28f7eaSRyusuke Konishi nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
80917c76b01SKoji Sato path[level].bp_index, key);
81017c76b01SKoji Sato }
81117c76b01SKoji Sato }
81217c76b01SKoji Sato
nilfs_btree_do_insert(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)813e7c274f8SRyusuke Konishi static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
81417c76b01SKoji Sato struct nilfs_btree_path *path,
81517c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
81617c76b01SKoji Sato {
81717c76b01SKoji Sato struct nilfs_btree_node *node;
8189b7b265cSRyusuke Konishi int ncblk;
81917c76b01SKoji Sato
82017c76b01SKoji Sato if (level < nilfs_btree_height(btree) - 1) {
8216d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
8229b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
8239b7b265cSRyusuke Konishi nilfs_btree_node_insert(node, path[level].bp_index,
8249b7b265cSRyusuke Konishi *keyp, *ptrp, ncblk);
82517c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
8265fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
82717c76b01SKoji Sato
82817c76b01SKoji Sato if (path[level].bp_index == 0)
82917c76b01SKoji Sato nilfs_btree_promote_key(btree, path, level + 1,
8306d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(node,
8316d28f7eaSRyusuke Konishi 0));
83217c76b01SKoji Sato } else {
83317c76b01SKoji Sato node = nilfs_btree_get_root(btree);
8349b7b265cSRyusuke Konishi nilfs_btree_node_insert(node, path[level].bp_index,
8359b7b265cSRyusuke Konishi *keyp, *ptrp,
8369b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
83717c76b01SKoji Sato }
83817c76b01SKoji Sato }
83917c76b01SKoji Sato
nilfs_btree_carry_left(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)840e7c274f8SRyusuke Konishi static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
84117c76b01SKoji Sato struct nilfs_btree_path *path,
84217c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
84317c76b01SKoji Sato {
84417c76b01SKoji Sato struct nilfs_btree_node *node, *left;
8459b7b265cSRyusuke Konishi int nchildren, lnchildren, n, move, ncblk;
84617c76b01SKoji Sato
8476d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
8486d28f7eaSRyusuke Konishi left = nilfs_btree_get_sib_node(path, level);
8496d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
8506d28f7eaSRyusuke Konishi lnchildren = nilfs_btree_node_get_nchildren(left);
8519b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
85217c76b01SKoji Sato move = 0;
85317c76b01SKoji Sato
85417c76b01SKoji Sato n = (nchildren + lnchildren + 1) / 2 - lnchildren;
85517c76b01SKoji Sato if (n > path[level].bp_index) {
85617c76b01SKoji Sato /* move insert point */
85717c76b01SKoji Sato n--;
85817c76b01SKoji Sato move = 1;
85917c76b01SKoji Sato }
86017c76b01SKoji Sato
8619b7b265cSRyusuke Konishi nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
86217c76b01SKoji Sato
86317c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
8645fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
86517c76b01SKoji Sato if (!buffer_dirty(path[level].bp_sib_bh))
8665fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_sib_bh);
86717c76b01SKoji Sato
86817c76b01SKoji Sato nilfs_btree_promote_key(btree, path, level + 1,
8696d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(node, 0));
87017c76b01SKoji Sato
87117c76b01SKoji Sato if (move) {
872087d01b4SRyusuke Konishi brelse(path[level].bp_bh);
87317c76b01SKoji Sato path[level].bp_bh = path[level].bp_sib_bh;
87417c76b01SKoji Sato path[level].bp_sib_bh = NULL;
87517c76b01SKoji Sato path[level].bp_index += lnchildren;
87617c76b01SKoji Sato path[level + 1].bp_index--;
87717c76b01SKoji Sato } else {
878087d01b4SRyusuke Konishi brelse(path[level].bp_sib_bh);
87917c76b01SKoji Sato path[level].bp_sib_bh = NULL;
88017c76b01SKoji Sato path[level].bp_index -= n;
88117c76b01SKoji Sato }
88217c76b01SKoji Sato
88317c76b01SKoji Sato nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
88417c76b01SKoji Sato }
88517c76b01SKoji Sato
nilfs_btree_carry_right(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)886e7c274f8SRyusuke Konishi static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
88717c76b01SKoji Sato struct nilfs_btree_path *path,
88817c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
88917c76b01SKoji Sato {
89017c76b01SKoji Sato struct nilfs_btree_node *node, *right;
8919b7b265cSRyusuke Konishi int nchildren, rnchildren, n, move, ncblk;
89217c76b01SKoji Sato
8936d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
8946d28f7eaSRyusuke Konishi right = nilfs_btree_get_sib_node(path, level);
8956d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
8966d28f7eaSRyusuke Konishi rnchildren = nilfs_btree_node_get_nchildren(right);
8979b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
89817c76b01SKoji Sato move = 0;
89917c76b01SKoji Sato
90017c76b01SKoji Sato n = (nchildren + rnchildren + 1) / 2 - rnchildren;
90117c76b01SKoji Sato if (n > nchildren - path[level].bp_index) {
90217c76b01SKoji Sato /* move insert point */
90317c76b01SKoji Sato n--;
90417c76b01SKoji Sato move = 1;
90517c76b01SKoji Sato }
90617c76b01SKoji Sato
9079b7b265cSRyusuke Konishi nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
90817c76b01SKoji Sato
90917c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
9105fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
91117c76b01SKoji Sato if (!buffer_dirty(path[level].bp_sib_bh))
9125fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_sib_bh);
91317c76b01SKoji Sato
91417c76b01SKoji Sato path[level + 1].bp_index++;
91517c76b01SKoji Sato nilfs_btree_promote_key(btree, path, level + 1,
9166d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(right, 0));
91717c76b01SKoji Sato path[level + 1].bp_index--;
91817c76b01SKoji Sato
91917c76b01SKoji Sato if (move) {
920087d01b4SRyusuke Konishi brelse(path[level].bp_bh);
92117c76b01SKoji Sato path[level].bp_bh = path[level].bp_sib_bh;
92217c76b01SKoji Sato path[level].bp_sib_bh = NULL;
9236d28f7eaSRyusuke Konishi path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
92417c76b01SKoji Sato path[level + 1].bp_index++;
92517c76b01SKoji Sato } else {
926087d01b4SRyusuke Konishi brelse(path[level].bp_sib_bh);
92717c76b01SKoji Sato path[level].bp_sib_bh = NULL;
92817c76b01SKoji Sato }
92917c76b01SKoji Sato
93017c76b01SKoji Sato nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
93117c76b01SKoji Sato }
93217c76b01SKoji Sato
nilfs_btree_split(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)933e7c274f8SRyusuke Konishi static void nilfs_btree_split(struct nilfs_bmap *btree,
93417c76b01SKoji Sato struct nilfs_btree_path *path,
93517c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
93617c76b01SKoji Sato {
93717c76b01SKoji Sato struct nilfs_btree_node *node, *right;
9389b7b265cSRyusuke Konishi int nchildren, n, move, ncblk;
93917c76b01SKoji Sato
9406d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
9416d28f7eaSRyusuke Konishi right = nilfs_btree_get_sib_node(path, level);
9426d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
9439b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
94417c76b01SKoji Sato move = 0;
94517c76b01SKoji Sato
94617c76b01SKoji Sato n = (nchildren + 1) / 2;
94717c76b01SKoji Sato if (n > nchildren - path[level].bp_index) {
94817c76b01SKoji Sato n--;
94917c76b01SKoji Sato move = 1;
95017c76b01SKoji Sato }
95117c76b01SKoji Sato
9529b7b265cSRyusuke Konishi nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
95317c76b01SKoji Sato
95417c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
9555fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
95617c76b01SKoji Sato if (!buffer_dirty(path[level].bp_sib_bh))
9575fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_sib_bh);
95817c76b01SKoji Sato
95917c76b01SKoji Sato if (move) {
9606d28f7eaSRyusuke Konishi path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
9619b7b265cSRyusuke Konishi nilfs_btree_node_insert(right, path[level].bp_index,
9629b7b265cSRyusuke Konishi *keyp, *ptrp, ncblk);
96317c76b01SKoji Sato
9646d28f7eaSRyusuke Konishi *keyp = nilfs_btree_node_get_key(right, 0);
96517c76b01SKoji Sato *ptrp = path[level].bp_newreq.bpr_ptr;
96617c76b01SKoji Sato
967087d01b4SRyusuke Konishi brelse(path[level].bp_bh);
96817c76b01SKoji Sato path[level].bp_bh = path[level].bp_sib_bh;
96917c76b01SKoji Sato path[level].bp_sib_bh = NULL;
97017c76b01SKoji Sato } else {
97117c76b01SKoji Sato nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
97217c76b01SKoji Sato
9736d28f7eaSRyusuke Konishi *keyp = nilfs_btree_node_get_key(right, 0);
97417c76b01SKoji Sato *ptrp = path[level].bp_newreq.bpr_ptr;
97517c76b01SKoji Sato
976087d01b4SRyusuke Konishi brelse(path[level].bp_sib_bh);
97717c76b01SKoji Sato path[level].bp_sib_bh = NULL;
97817c76b01SKoji Sato }
97917c76b01SKoji Sato
98017c76b01SKoji Sato path[level + 1].bp_index++;
98117c76b01SKoji Sato }
98217c76b01SKoji Sato
nilfs_btree_grow(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)983e7c274f8SRyusuke Konishi static void nilfs_btree_grow(struct nilfs_bmap *btree,
98417c76b01SKoji Sato struct nilfs_btree_path *path,
98517c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
98617c76b01SKoji Sato {
98717c76b01SKoji Sato struct nilfs_btree_node *root, *child;
9889b7b265cSRyusuke Konishi int n, ncblk;
98917c76b01SKoji Sato
99017c76b01SKoji Sato root = nilfs_btree_get_root(btree);
9916d28f7eaSRyusuke Konishi child = nilfs_btree_get_sib_node(path, level);
9929b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
99317c76b01SKoji Sato
9946d28f7eaSRyusuke Konishi n = nilfs_btree_node_get_nchildren(root);
99517c76b01SKoji Sato
9969b7b265cSRyusuke Konishi nilfs_btree_node_move_right(root, child, n,
9979b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
9986d28f7eaSRyusuke Konishi nilfs_btree_node_set_level(root, level + 1);
99917c76b01SKoji Sato
100017c76b01SKoji Sato if (!buffer_dirty(path[level].bp_sib_bh))
10015fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_sib_bh);
100217c76b01SKoji Sato
100317c76b01SKoji Sato path[level].bp_bh = path[level].bp_sib_bh;
100417c76b01SKoji Sato path[level].bp_sib_bh = NULL;
100517c76b01SKoji Sato
100617c76b01SKoji Sato nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
100717c76b01SKoji Sato
10086d28f7eaSRyusuke Konishi *keyp = nilfs_btree_node_get_key(child, 0);
100917c76b01SKoji Sato *ptrp = path[level].bp_newreq.bpr_ptr;
101017c76b01SKoji Sato }
101117c76b01SKoji Sato
nilfs_btree_find_near(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path)1012e7c274f8SRyusuke Konishi static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
101317c76b01SKoji Sato const struct nilfs_btree_path *path)
101417c76b01SKoji Sato {
101517c76b01SKoji Sato struct nilfs_btree_node *node;
10169b7b265cSRyusuke Konishi int level, ncmax;
101717c76b01SKoji Sato
101817c76b01SKoji Sato if (path == NULL)
101917c76b01SKoji Sato return NILFS_BMAP_INVALID_PTR;
102017c76b01SKoji Sato
102117c76b01SKoji Sato /* left sibling */
102217c76b01SKoji Sato level = NILFS_BTREE_LEVEL_NODE_MIN;
102317c76b01SKoji Sato if (path[level].bp_index > 0) {
10249b7b265cSRyusuke Konishi node = nilfs_btree_get_node(btree, path, level, &ncmax);
10259b7b265cSRyusuke Konishi return nilfs_btree_node_get_ptr(node,
10269b7b265cSRyusuke Konishi path[level].bp_index - 1,
10279b7b265cSRyusuke Konishi ncmax);
102817c76b01SKoji Sato }
102917c76b01SKoji Sato
103017c76b01SKoji Sato /* parent */
103117c76b01SKoji Sato level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
103217c76b01SKoji Sato if (level <= nilfs_btree_height(btree) - 1) {
10339b7b265cSRyusuke Konishi node = nilfs_btree_get_node(btree, path, level, &ncmax);
10349b7b265cSRyusuke Konishi return nilfs_btree_node_get_ptr(node, path[level].bp_index,
10359b7b265cSRyusuke Konishi ncmax);
103617c76b01SKoji Sato }
103717c76b01SKoji Sato
103817c76b01SKoji Sato return NILFS_BMAP_INVALID_PTR;
103917c76b01SKoji Sato }
104017c76b01SKoji Sato
nilfs_btree_find_target_v(const struct nilfs_bmap * btree,const struct nilfs_btree_path * path,__u64 key)1041e7c274f8SRyusuke Konishi static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
104217c76b01SKoji Sato const struct nilfs_btree_path *path,
104317c76b01SKoji Sato __u64 key)
104417c76b01SKoji Sato {
104517c76b01SKoji Sato __u64 ptr;
104617c76b01SKoji Sato
1047e7c274f8SRyusuke Konishi ptr = nilfs_bmap_find_target_seq(btree, key);
104817c76b01SKoji Sato if (ptr != NILFS_BMAP_INVALID_PTR)
104917c76b01SKoji Sato /* sequential access */
105017c76b01SKoji Sato return ptr;
10517f00184eSRyusuke Konishi
105217c76b01SKoji Sato ptr = nilfs_btree_find_near(btree, path);
105317c76b01SKoji Sato if (ptr != NILFS_BMAP_INVALID_PTR)
105417c76b01SKoji Sato /* near */
105517c76b01SKoji Sato return ptr;
10567f00184eSRyusuke Konishi
105717c76b01SKoji Sato /* block group */
1058e7c274f8SRyusuke Konishi return nilfs_bmap_find_target_in_group(btree);
105917c76b01SKoji Sato }
106017c76b01SKoji Sato
nilfs_btree_prepare_insert(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int * levelp,__u64 key,__u64 ptr,struct nilfs_bmap_stats * stats)1061e7c274f8SRyusuke Konishi static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
106217c76b01SKoji Sato struct nilfs_btree_path *path,
106317c76b01SKoji Sato int *levelp, __u64 key, __u64 ptr,
106417c76b01SKoji Sato struct nilfs_bmap_stats *stats)
106517c76b01SKoji Sato {
106617c76b01SKoji Sato struct buffer_head *bh;
106717c76b01SKoji Sato struct nilfs_btree_node *node, *parent, *sib;
106817c76b01SKoji Sato __u64 sibptr;
10699b7b265cSRyusuke Konishi int pindex, level, ncmax, ncblk, ret;
10702e0c2c73SRyusuke Konishi struct inode *dat = NULL;
107117c76b01SKoji Sato
107217c76b01SKoji Sato stats->bs_nblocks = 0;
107317c76b01SKoji Sato level = NILFS_BTREE_LEVEL_DATA;
107417c76b01SKoji Sato
107517c76b01SKoji Sato /* allocate a new ptr for data block */
1076e7c274f8SRyusuke Konishi if (NILFS_BMAP_USE_VBN(btree)) {
107717c76b01SKoji Sato path[level].bp_newreq.bpr_ptr =
10787cde31d7SRyusuke Konishi nilfs_btree_find_target_v(btree, path, key);
1079e7c274f8SRyusuke Konishi dat = nilfs_bmap_get_dat(btree);
10802e0c2c73SRyusuke Konishi }
108117c76b01SKoji Sato
1082e7c274f8SRyusuke Konishi ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
108317c76b01SKoji Sato if (ret < 0)
108417c76b01SKoji Sato goto err_out_data;
108517c76b01SKoji Sato
10869b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
1087ea64ab87SRyusuke Konishi
108817c76b01SKoji Sato for (level = NILFS_BTREE_LEVEL_NODE_MIN;
108917c76b01SKoji Sato level < nilfs_btree_height(btree) - 1;
109017c76b01SKoji Sato level++) {
10916d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
10929b7b265cSRyusuke Konishi if (nilfs_btree_node_get_nchildren(node) < ncblk) {
109317c76b01SKoji Sato path[level].bp_op = nilfs_btree_do_insert;
109417c76b01SKoji Sato stats->bs_nblocks++;
109517c76b01SKoji Sato goto out;
109617c76b01SKoji Sato }
109717c76b01SKoji Sato
10989b7b265cSRyusuke Konishi parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
109917c76b01SKoji Sato pindex = path[level + 1].bp_index;
110017c76b01SKoji Sato
110117c76b01SKoji Sato /* left sibling */
110217c76b01SKoji Sato if (pindex > 0) {
11039b7b265cSRyusuke Konishi sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
11049b7b265cSRyusuke Konishi ncmax);
1105f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, sibptr, &bh);
110617c76b01SKoji Sato if (ret < 0)
110717c76b01SKoji Sato goto err_out_child_node;
110817c76b01SKoji Sato sib = (struct nilfs_btree_node *)bh->b_data;
11099b7b265cSRyusuke Konishi if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
111017c76b01SKoji Sato path[level].bp_sib_bh = bh;
111117c76b01SKoji Sato path[level].bp_op = nilfs_btree_carry_left;
111217c76b01SKoji Sato stats->bs_nblocks++;
111317c76b01SKoji Sato goto out;
11149b7b265cSRyusuke Konishi } else {
1115087d01b4SRyusuke Konishi brelse(bh);
111617c76b01SKoji Sato }
11179b7b265cSRyusuke Konishi }
111817c76b01SKoji Sato
111917c76b01SKoji Sato /* right sibling */
11209b7b265cSRyusuke Konishi if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) {
11219b7b265cSRyusuke Konishi sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
11229b7b265cSRyusuke Konishi ncmax);
1123f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, sibptr, &bh);
112417c76b01SKoji Sato if (ret < 0)
112517c76b01SKoji Sato goto err_out_child_node;
112617c76b01SKoji Sato sib = (struct nilfs_btree_node *)bh->b_data;
11279b7b265cSRyusuke Konishi if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
112817c76b01SKoji Sato path[level].bp_sib_bh = bh;
112917c76b01SKoji Sato path[level].bp_op = nilfs_btree_carry_right;
113017c76b01SKoji Sato stats->bs_nblocks++;
113117c76b01SKoji Sato goto out;
11329b7b265cSRyusuke Konishi } else {
1133087d01b4SRyusuke Konishi brelse(bh);
113417c76b01SKoji Sato }
11359b7b265cSRyusuke Konishi }
113617c76b01SKoji Sato
113717c76b01SKoji Sato /* split */
113817c76b01SKoji Sato path[level].bp_newreq.bpr_ptr =
113917c76b01SKoji Sato path[level - 1].bp_newreq.bpr_ptr + 1;
1140e7c274f8SRyusuke Konishi ret = nilfs_bmap_prepare_alloc_ptr(btree,
11412e0c2c73SRyusuke Konishi &path[level].bp_newreq, dat);
114217c76b01SKoji Sato if (ret < 0)
114317c76b01SKoji Sato goto err_out_child_node;
1144f198dbb9SRyusuke Konishi ret = nilfs_btree_get_new_block(btree,
114517c76b01SKoji Sato path[level].bp_newreq.bpr_ptr,
114617c76b01SKoji Sato &bh);
114717c76b01SKoji Sato if (ret < 0)
114817c76b01SKoji Sato goto err_out_curr_node;
114917c76b01SKoji Sato
115017c76b01SKoji Sato stats->bs_nblocks++;
115117c76b01SKoji Sato
11529b7b265cSRyusuke Konishi sib = (struct nilfs_btree_node *)bh->b_data;
11539b7b265cSRyusuke Konishi nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);
115417c76b01SKoji Sato path[level].bp_sib_bh = bh;
115517c76b01SKoji Sato path[level].bp_op = nilfs_btree_split;
115617c76b01SKoji Sato }
115717c76b01SKoji Sato
115817c76b01SKoji Sato /* root */
115917c76b01SKoji Sato node = nilfs_btree_get_root(btree);
11606d28f7eaSRyusuke Konishi if (nilfs_btree_node_get_nchildren(node) <
1161ea64ab87SRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX) {
116217c76b01SKoji Sato path[level].bp_op = nilfs_btree_do_insert;
116317c76b01SKoji Sato stats->bs_nblocks++;
116417c76b01SKoji Sato goto out;
116517c76b01SKoji Sato }
116617c76b01SKoji Sato
116717c76b01SKoji Sato /* grow */
116817c76b01SKoji Sato path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
1169e7c274f8SRyusuke Konishi ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
117017c76b01SKoji Sato if (ret < 0)
117117c76b01SKoji Sato goto err_out_child_node;
1172f198dbb9SRyusuke Konishi ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1173f198dbb9SRyusuke Konishi &bh);
117417c76b01SKoji Sato if (ret < 0)
117517c76b01SKoji Sato goto err_out_curr_node;
117617c76b01SKoji Sato
11779b7b265cSRyusuke Konishi nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data,
11789b7b265cSRyusuke Konishi 0, level, 0, ncblk, NULL, NULL);
117917c76b01SKoji Sato path[level].bp_sib_bh = bh;
118017c76b01SKoji Sato path[level].bp_op = nilfs_btree_grow;
118117c76b01SKoji Sato
118217c76b01SKoji Sato level++;
118317c76b01SKoji Sato path[level].bp_op = nilfs_btree_do_insert;
118417c76b01SKoji Sato
118517c76b01SKoji Sato /* a newly-created node block and a data block are added */
118617c76b01SKoji Sato stats->bs_nblocks += 2;
118717c76b01SKoji Sato
118817c76b01SKoji Sato /* success */
118917c76b01SKoji Sato out:
119017c76b01SKoji Sato *levelp = level;
119117c76b01SKoji Sato return ret;
119217c76b01SKoji Sato
119317c76b01SKoji Sato /* error */
119417c76b01SKoji Sato err_out_curr_node:
1195e7c274f8SRyusuke Konishi nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
119617c76b01SKoji Sato err_out_child_node:
119717c76b01SKoji Sato for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
11989f098900SRyusuke Konishi nilfs_btnode_delete(path[level].bp_sib_bh);
1199e7c274f8SRyusuke Konishi nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
120017c76b01SKoji Sato
120117c76b01SKoji Sato }
120217c76b01SKoji Sato
1203e7c274f8SRyusuke Konishi nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
120417c76b01SKoji Sato err_out_data:
120517c76b01SKoji Sato *levelp = level;
120617c76b01SKoji Sato stats->bs_nblocks = 0;
120717c76b01SKoji Sato return ret;
120817c76b01SKoji Sato }
120917c76b01SKoji Sato
nilfs_btree_commit_insert(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int maxlevel,__u64 key,__u64 ptr)1210e7c274f8SRyusuke Konishi static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
121117c76b01SKoji Sato struct nilfs_btree_path *path,
121217c76b01SKoji Sato int maxlevel, __u64 key, __u64 ptr)
121317c76b01SKoji Sato {
12142e0c2c73SRyusuke Konishi struct inode *dat = NULL;
121517c76b01SKoji Sato int level;
121617c76b01SKoji Sato
121717c76b01SKoji Sato set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
121817c76b01SKoji Sato ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
1219e7c274f8SRyusuke Konishi if (NILFS_BMAP_USE_VBN(btree)) {
1220dc935be2SRyusuke Konishi nilfs_bmap_set_target_v(btree, key, ptr);
1221e7c274f8SRyusuke Konishi dat = nilfs_bmap_get_dat(btree);
12222e0c2c73SRyusuke Konishi }
122317c76b01SKoji Sato
122417c76b01SKoji Sato for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
1225e7c274f8SRyusuke Konishi nilfs_bmap_commit_alloc_ptr(btree,
12262e0c2c73SRyusuke Konishi &path[level - 1].bp_newreq, dat);
12278acfbf09SPekka Enberg path[level].bp_op(btree, path, level, &key, &ptr);
122817c76b01SKoji Sato }
122917c76b01SKoji Sato
1230e7c274f8SRyusuke Konishi if (!nilfs_bmap_dirty(btree))
1231e7c274f8SRyusuke Konishi nilfs_bmap_set_dirty(btree);
123217c76b01SKoji Sato }
123317c76b01SKoji Sato
nilfs_btree_insert(struct nilfs_bmap * btree,__u64 key,__u64 ptr)1234e7c274f8SRyusuke Konishi static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
123517c76b01SKoji Sato {
123617c76b01SKoji Sato struct nilfs_btree_path *path;
123717c76b01SKoji Sato struct nilfs_bmap_stats stats;
123817c76b01SKoji Sato int level, ret;
123917c76b01SKoji Sato
12406d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
124117c76b01SKoji Sato if (path == NULL)
124217c76b01SKoji Sato return -ENOMEM;
124317c76b01SKoji Sato
124417c76b01SKoji Sato ret = nilfs_btree_do_lookup(btree, path, key, NULL,
124503bdb5acSRyusuke Konishi NILFS_BTREE_LEVEL_NODE_MIN, 0);
124617c76b01SKoji Sato if (ret != -ENOENT) {
124717c76b01SKoji Sato if (ret == 0)
124817c76b01SKoji Sato ret = -EEXIST;
124917c76b01SKoji Sato goto out;
125017c76b01SKoji Sato }
125117c76b01SKoji Sato
125217c76b01SKoji Sato ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
125317c76b01SKoji Sato if (ret < 0)
125417c76b01SKoji Sato goto out;
125517c76b01SKoji Sato nilfs_btree_commit_insert(btree, path, level, key, ptr);
1256be667377SRyusuke Konishi nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
125717c76b01SKoji Sato
125817c76b01SKoji Sato out:
12596d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
126017c76b01SKoji Sato return ret;
126117c76b01SKoji Sato }
126217c76b01SKoji Sato
nilfs_btree_do_delete(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)1263e7c274f8SRyusuke Konishi static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
126417c76b01SKoji Sato struct nilfs_btree_path *path,
126517c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
126617c76b01SKoji Sato {
126717c76b01SKoji Sato struct nilfs_btree_node *node;
12689b7b265cSRyusuke Konishi int ncblk;
126917c76b01SKoji Sato
127017c76b01SKoji Sato if (level < nilfs_btree_height(btree) - 1) {
12716d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
12729b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
12739b7b265cSRyusuke Konishi nilfs_btree_node_delete(node, path[level].bp_index,
12749b7b265cSRyusuke Konishi keyp, ptrp, ncblk);
127517c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
12765fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
127717c76b01SKoji Sato if (path[level].bp_index == 0)
127817c76b01SKoji Sato nilfs_btree_promote_key(btree, path, level + 1,
12796d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(node, 0));
128017c76b01SKoji Sato } else {
128117c76b01SKoji Sato node = nilfs_btree_get_root(btree);
12829b7b265cSRyusuke Konishi nilfs_btree_node_delete(node, path[level].bp_index,
12839b7b265cSRyusuke Konishi keyp, ptrp,
12849b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
128517c76b01SKoji Sato }
128617c76b01SKoji Sato }
128717c76b01SKoji Sato
nilfs_btree_borrow_left(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)1288e7c274f8SRyusuke Konishi static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
128917c76b01SKoji Sato struct nilfs_btree_path *path,
129017c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
129117c76b01SKoji Sato {
129217c76b01SKoji Sato struct nilfs_btree_node *node, *left;
12939b7b265cSRyusuke Konishi int nchildren, lnchildren, n, ncblk;
129417c76b01SKoji Sato
129517c76b01SKoji Sato nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
129617c76b01SKoji Sato
12976d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
12986d28f7eaSRyusuke Konishi left = nilfs_btree_get_sib_node(path, level);
12996d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
13006d28f7eaSRyusuke Konishi lnchildren = nilfs_btree_node_get_nchildren(left);
13019b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
130217c76b01SKoji Sato
130317c76b01SKoji Sato n = (nchildren + lnchildren) / 2 - nchildren;
130417c76b01SKoji Sato
13059b7b265cSRyusuke Konishi nilfs_btree_node_move_right(left, node, n, ncblk, ncblk);
130617c76b01SKoji Sato
130717c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
13085fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
130917c76b01SKoji Sato if (!buffer_dirty(path[level].bp_sib_bh))
13105fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_sib_bh);
131117c76b01SKoji Sato
131217c76b01SKoji Sato nilfs_btree_promote_key(btree, path, level + 1,
13136d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(node, 0));
131417c76b01SKoji Sato
1315087d01b4SRyusuke Konishi brelse(path[level].bp_sib_bh);
131617c76b01SKoji Sato path[level].bp_sib_bh = NULL;
131717c76b01SKoji Sato path[level].bp_index += n;
131817c76b01SKoji Sato }
131917c76b01SKoji Sato
nilfs_btree_borrow_right(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)1320e7c274f8SRyusuke Konishi static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
132117c76b01SKoji Sato struct nilfs_btree_path *path,
132217c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
132317c76b01SKoji Sato {
132417c76b01SKoji Sato struct nilfs_btree_node *node, *right;
13259b7b265cSRyusuke Konishi int nchildren, rnchildren, n, ncblk;
132617c76b01SKoji Sato
132717c76b01SKoji Sato nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
132817c76b01SKoji Sato
13296d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
13306d28f7eaSRyusuke Konishi right = nilfs_btree_get_sib_node(path, level);
13316d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
13326d28f7eaSRyusuke Konishi rnchildren = nilfs_btree_node_get_nchildren(right);
13339b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
133417c76b01SKoji Sato
133517c76b01SKoji Sato n = (nchildren + rnchildren) / 2 - nchildren;
133617c76b01SKoji Sato
13379b7b265cSRyusuke Konishi nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
133817c76b01SKoji Sato
133917c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
13405fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
134117c76b01SKoji Sato if (!buffer_dirty(path[level].bp_sib_bh))
13425fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_sib_bh);
134317c76b01SKoji Sato
134417c76b01SKoji Sato path[level + 1].bp_index++;
134517c76b01SKoji Sato nilfs_btree_promote_key(btree, path, level + 1,
13466d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(right, 0));
134717c76b01SKoji Sato path[level + 1].bp_index--;
134817c76b01SKoji Sato
1349087d01b4SRyusuke Konishi brelse(path[level].bp_sib_bh);
135017c76b01SKoji Sato path[level].bp_sib_bh = NULL;
135117c76b01SKoji Sato }
135217c76b01SKoji Sato
nilfs_btree_concat_left(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)1353e7c274f8SRyusuke Konishi static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
135417c76b01SKoji Sato struct nilfs_btree_path *path,
135517c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
135617c76b01SKoji Sato {
135717c76b01SKoji Sato struct nilfs_btree_node *node, *left;
13589b7b265cSRyusuke Konishi int n, ncblk;
135917c76b01SKoji Sato
136017c76b01SKoji Sato nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
136117c76b01SKoji Sato
13626d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
13636d28f7eaSRyusuke Konishi left = nilfs_btree_get_sib_node(path, level);
13649b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
136517c76b01SKoji Sato
13666d28f7eaSRyusuke Konishi n = nilfs_btree_node_get_nchildren(node);
136717c76b01SKoji Sato
13689b7b265cSRyusuke Konishi nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
136917c76b01SKoji Sato
137017c76b01SKoji Sato if (!buffer_dirty(path[level].bp_sib_bh))
13715fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_sib_bh);
137217c76b01SKoji Sato
13739f098900SRyusuke Konishi nilfs_btnode_delete(path[level].bp_bh);
137417c76b01SKoji Sato path[level].bp_bh = path[level].bp_sib_bh;
137517c76b01SKoji Sato path[level].bp_sib_bh = NULL;
13766d28f7eaSRyusuke Konishi path[level].bp_index += nilfs_btree_node_get_nchildren(left);
137717c76b01SKoji Sato }
137817c76b01SKoji Sato
nilfs_btree_concat_right(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)1379e7c274f8SRyusuke Konishi static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
138017c76b01SKoji Sato struct nilfs_btree_path *path,
138117c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
138217c76b01SKoji Sato {
138317c76b01SKoji Sato struct nilfs_btree_node *node, *right;
13849b7b265cSRyusuke Konishi int n, ncblk;
138517c76b01SKoji Sato
138617c76b01SKoji Sato nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
138717c76b01SKoji Sato
13886d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
13896d28f7eaSRyusuke Konishi right = nilfs_btree_get_sib_node(path, level);
13909b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
139117c76b01SKoji Sato
13926d28f7eaSRyusuke Konishi n = nilfs_btree_node_get_nchildren(right);
139317c76b01SKoji Sato
13949b7b265cSRyusuke Konishi nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
139517c76b01SKoji Sato
139617c76b01SKoji Sato if (!buffer_dirty(path[level].bp_bh))
13975fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
139817c76b01SKoji Sato
13999f098900SRyusuke Konishi nilfs_btnode_delete(path[level].bp_sib_bh);
140017c76b01SKoji Sato path[level].bp_sib_bh = NULL;
140117c76b01SKoji Sato path[level + 1].bp_index++;
140217c76b01SKoji Sato }
140317c76b01SKoji Sato
nilfs_btree_shrink(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)1404e7c274f8SRyusuke Konishi static void nilfs_btree_shrink(struct nilfs_bmap *btree,
140517c76b01SKoji Sato struct nilfs_btree_path *path,
140617c76b01SKoji Sato int level, __u64 *keyp, __u64 *ptrp)
140717c76b01SKoji Sato {
140817c76b01SKoji Sato struct nilfs_btree_node *root, *child;
14099b7b265cSRyusuke Konishi int n, ncblk;
141017c76b01SKoji Sato
141117c76b01SKoji Sato nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
141217c76b01SKoji Sato
141317c76b01SKoji Sato root = nilfs_btree_get_root(btree);
14146d28f7eaSRyusuke Konishi child = nilfs_btree_get_nonroot_node(path, level);
14159b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
141617c76b01SKoji Sato
14179b7b265cSRyusuke Konishi nilfs_btree_node_delete(root, 0, NULL, NULL,
14189b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
14196d28f7eaSRyusuke Konishi nilfs_btree_node_set_level(root, level);
14206d28f7eaSRyusuke Konishi n = nilfs_btree_node_get_nchildren(child);
14219b7b265cSRyusuke Konishi nilfs_btree_node_move_left(root, child, n,
14229b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
142317c76b01SKoji Sato
14249f098900SRyusuke Konishi nilfs_btnode_delete(path[level].bp_bh);
142517c76b01SKoji Sato path[level].bp_bh = NULL;
142617c76b01SKoji Sato }
142717c76b01SKoji Sato
nilfs_btree_nop(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,__u64 * keyp,__u64 * ptrp)1428d4099053SRyusuke Konishi static void nilfs_btree_nop(struct nilfs_bmap *btree,
1429d4099053SRyusuke Konishi struct nilfs_btree_path *path,
1430d4099053SRyusuke Konishi int level, __u64 *keyp, __u64 *ptrp)
1431d4099053SRyusuke Konishi {
1432d4099053SRyusuke Konishi }
143317c76b01SKoji Sato
nilfs_btree_prepare_delete(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int * levelp,struct nilfs_bmap_stats * stats,struct inode * dat)1434e7c274f8SRyusuke Konishi static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
143517c76b01SKoji Sato struct nilfs_btree_path *path,
143617c76b01SKoji Sato int *levelp,
14372e0c2c73SRyusuke Konishi struct nilfs_bmap_stats *stats,
14382e0c2c73SRyusuke Konishi struct inode *dat)
143917c76b01SKoji Sato {
144017c76b01SKoji Sato struct buffer_head *bh;
144117c76b01SKoji Sato struct nilfs_btree_node *node, *parent, *sib;
144217c76b01SKoji Sato __u64 sibptr;
1443fe744fdbSRyusuke Konishi int pindex, dindex, level, ncmin, ncmax, ncblk, ret;
144417c76b01SKoji Sato
144517c76b01SKoji Sato ret = 0;
144617c76b01SKoji Sato stats->bs_nblocks = 0;
1447ea64ab87SRyusuke Konishi ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
14489b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
1449ea64ab87SRyusuke Konishi
1450fe744fdbSRyusuke Konishi for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;
145117c76b01SKoji Sato level < nilfs_btree_height(btree) - 1;
145217c76b01SKoji Sato level++) {
14536d28f7eaSRyusuke Konishi node = nilfs_btree_get_nonroot_node(path, level);
145417c76b01SKoji Sato path[level].bp_oldreq.bpr_ptr =
1455fe744fdbSRyusuke Konishi nilfs_btree_node_get_ptr(node, dindex, ncblk);
1456e7c274f8SRyusuke Konishi ret = nilfs_bmap_prepare_end_ptr(btree,
14572e0c2c73SRyusuke Konishi &path[level].bp_oldreq, dat);
145817c76b01SKoji Sato if (ret < 0)
145917c76b01SKoji Sato goto err_out_child_node;
146017c76b01SKoji Sato
1461ea64ab87SRyusuke Konishi if (nilfs_btree_node_get_nchildren(node) > ncmin) {
146217c76b01SKoji Sato path[level].bp_op = nilfs_btree_do_delete;
146317c76b01SKoji Sato stats->bs_nblocks++;
146417c76b01SKoji Sato goto out;
146517c76b01SKoji Sato }
146617c76b01SKoji Sato
14679b7b265cSRyusuke Konishi parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
146817c76b01SKoji Sato pindex = path[level + 1].bp_index;
1469fe744fdbSRyusuke Konishi dindex = pindex;
147017c76b01SKoji Sato
147117c76b01SKoji Sato if (pindex > 0) {
147217c76b01SKoji Sato /* left sibling */
14739b7b265cSRyusuke Konishi sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
14749b7b265cSRyusuke Konishi ncmax);
1475f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, sibptr, &bh);
147617c76b01SKoji Sato if (ret < 0)
147717c76b01SKoji Sato goto err_out_curr_node;
147817c76b01SKoji Sato sib = (struct nilfs_btree_node *)bh->b_data;
1479ea64ab87SRyusuke Konishi if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
148017c76b01SKoji Sato path[level].bp_sib_bh = bh;
148117c76b01SKoji Sato path[level].bp_op = nilfs_btree_borrow_left;
148217c76b01SKoji Sato stats->bs_nblocks++;
148317c76b01SKoji Sato goto out;
148417c76b01SKoji Sato } else {
148517c76b01SKoji Sato path[level].bp_sib_bh = bh;
148617c76b01SKoji Sato path[level].bp_op = nilfs_btree_concat_left;
148717c76b01SKoji Sato stats->bs_nblocks++;
148817c76b01SKoji Sato /* continue; */
148917c76b01SKoji Sato }
149017c76b01SKoji Sato } else if (pindex <
14916d28f7eaSRyusuke Konishi nilfs_btree_node_get_nchildren(parent) - 1) {
149217c76b01SKoji Sato /* right sibling */
14939b7b265cSRyusuke Konishi sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
14949b7b265cSRyusuke Konishi ncmax);
1495f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, sibptr, &bh);
149617c76b01SKoji Sato if (ret < 0)
149717c76b01SKoji Sato goto err_out_curr_node;
149817c76b01SKoji Sato sib = (struct nilfs_btree_node *)bh->b_data;
1499ea64ab87SRyusuke Konishi if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
150017c76b01SKoji Sato path[level].bp_sib_bh = bh;
150117c76b01SKoji Sato path[level].bp_op = nilfs_btree_borrow_right;
150217c76b01SKoji Sato stats->bs_nblocks++;
150317c76b01SKoji Sato goto out;
150417c76b01SKoji Sato } else {
150517c76b01SKoji Sato path[level].bp_sib_bh = bh;
150617c76b01SKoji Sato path[level].bp_op = nilfs_btree_concat_right;
150717c76b01SKoji Sato stats->bs_nblocks++;
1508fe744fdbSRyusuke Konishi /*
1509fe744fdbSRyusuke Konishi * When merging right sibling node
1510fe744fdbSRyusuke Konishi * into the current node, pointer to
1511fe744fdbSRyusuke Konishi * the right sibling node must be
1512fe744fdbSRyusuke Konishi * terminated instead. The adjustment
1513fe744fdbSRyusuke Konishi * below is required for that.
1514fe744fdbSRyusuke Konishi */
1515fe744fdbSRyusuke Konishi dindex = pindex + 1;
151617c76b01SKoji Sato /* continue; */
151717c76b01SKoji Sato }
151817c76b01SKoji Sato } else {
151917c76b01SKoji Sato /* no siblings */
152017c76b01SKoji Sato /* the only child of the root node */
15211f5abe7eSRyusuke Konishi WARN_ON(level != nilfs_btree_height(btree) - 2);
15226d28f7eaSRyusuke Konishi if (nilfs_btree_node_get_nchildren(node) - 1 <=
152317c76b01SKoji Sato NILFS_BTREE_ROOT_NCHILDREN_MAX) {
152417c76b01SKoji Sato path[level].bp_op = nilfs_btree_shrink;
152517c76b01SKoji Sato stats->bs_nblocks += 2;
1526d4099053SRyusuke Konishi level++;
1527d4099053SRyusuke Konishi path[level].bp_op = nilfs_btree_nop;
1528d4099053SRyusuke Konishi goto shrink_root_child;
152917c76b01SKoji Sato } else {
153017c76b01SKoji Sato path[level].bp_op = nilfs_btree_do_delete;
153117c76b01SKoji Sato stats->bs_nblocks++;
153217c76b01SKoji Sato goto out;
1533d4099053SRyusuke Konishi }
153417c76b01SKoji Sato }
153517c76b01SKoji Sato }
153617c76b01SKoji Sato
1537d4099053SRyusuke Konishi /* child of the root node is deleted */
1538d4099053SRyusuke Konishi path[level].bp_op = nilfs_btree_do_delete;
1539d4099053SRyusuke Konishi stats->bs_nblocks++;
1540d4099053SRyusuke Konishi
1541d4099053SRyusuke Konishi shrink_root_child:
154217c76b01SKoji Sato node = nilfs_btree_get_root(btree);
154317c76b01SKoji Sato path[level].bp_oldreq.bpr_ptr =
1544fe744fdbSRyusuke Konishi nilfs_btree_node_get_ptr(node, dindex,
15459b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
1546d4b96157SRyusuke Konishi
1547e7c274f8SRyusuke Konishi ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
154817c76b01SKoji Sato if (ret < 0)
154917c76b01SKoji Sato goto err_out_child_node;
1550d4b96157SRyusuke Konishi
155117c76b01SKoji Sato /* success */
155217c76b01SKoji Sato out:
155317c76b01SKoji Sato *levelp = level;
155417c76b01SKoji Sato return ret;
155517c76b01SKoji Sato
155617c76b01SKoji Sato /* error */
155717c76b01SKoji Sato err_out_curr_node:
1558e7c274f8SRyusuke Konishi nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
155917c76b01SKoji Sato err_out_child_node:
156017c76b01SKoji Sato for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {
1561087d01b4SRyusuke Konishi brelse(path[level].bp_sib_bh);
1562e7c274f8SRyusuke Konishi nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
156317c76b01SKoji Sato }
156417c76b01SKoji Sato *levelp = level;
156517c76b01SKoji Sato stats->bs_nblocks = 0;
156617c76b01SKoji Sato return ret;
156717c76b01SKoji Sato }
156817c76b01SKoji Sato
nilfs_btree_commit_delete(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int maxlevel,struct inode * dat)1569e7c274f8SRyusuke Konishi static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
157017c76b01SKoji Sato struct nilfs_btree_path *path,
15712e0c2c73SRyusuke Konishi int maxlevel, struct inode *dat)
157217c76b01SKoji Sato {
157317c76b01SKoji Sato int level;
157417c76b01SKoji Sato
157517c76b01SKoji Sato for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
1576e7c274f8SRyusuke Konishi nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
15778acfbf09SPekka Enberg path[level].bp_op(btree, path, level, NULL, NULL);
157817c76b01SKoji Sato }
157917c76b01SKoji Sato
1580e7c274f8SRyusuke Konishi if (!nilfs_bmap_dirty(btree))
1581e7c274f8SRyusuke Konishi nilfs_bmap_set_dirty(btree);
158217c76b01SKoji Sato }
158317c76b01SKoji Sato
nilfs_btree_delete(struct nilfs_bmap * btree,__u64 key)1584e7c274f8SRyusuke Konishi static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
158517c76b01SKoji Sato
158617c76b01SKoji Sato {
158717c76b01SKoji Sato struct nilfs_btree_path *path;
158817c76b01SKoji Sato struct nilfs_bmap_stats stats;
15892e0c2c73SRyusuke Konishi struct inode *dat;
159017c76b01SKoji Sato int level, ret;
159117c76b01SKoji Sato
15926d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
159317c76b01SKoji Sato if (path == NULL)
159417c76b01SKoji Sato return -ENOMEM;
1595f905440fSLi Hong
159617c76b01SKoji Sato ret = nilfs_btree_do_lookup(btree, path, key, NULL,
159703bdb5acSRyusuke Konishi NILFS_BTREE_LEVEL_NODE_MIN, 0);
159817c76b01SKoji Sato if (ret < 0)
159917c76b01SKoji Sato goto out;
160017c76b01SKoji Sato
16012e0c2c73SRyusuke Konishi
1602e7c274f8SRyusuke Konishi dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
16032e0c2c73SRyusuke Konishi
16042e0c2c73SRyusuke Konishi ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
160517c76b01SKoji Sato if (ret < 0)
160617c76b01SKoji Sato goto out;
16072e0c2c73SRyusuke Konishi nilfs_btree_commit_delete(btree, path, level, dat);
1608be667377SRyusuke Konishi nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);
160917c76b01SKoji Sato
161017c76b01SKoji Sato out:
16116d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
161217c76b01SKoji Sato return ret;
161317c76b01SKoji Sato }
161417c76b01SKoji Sato
nilfs_btree_seek_key(const struct nilfs_bmap * btree,__u64 start,__u64 * keyp)16155b20384fSRyusuke Konishi static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
16165b20384fSRyusuke Konishi __u64 *keyp)
16175b20384fSRyusuke Konishi {
16185b20384fSRyusuke Konishi struct nilfs_btree_path *path;
16195b20384fSRyusuke Konishi const int minlevel = NILFS_BTREE_LEVEL_NODE_MIN;
16205b20384fSRyusuke Konishi int ret;
16215b20384fSRyusuke Konishi
16225b20384fSRyusuke Konishi path = nilfs_btree_alloc_path();
16235b20384fSRyusuke Konishi if (!path)
16245b20384fSRyusuke Konishi return -ENOMEM;
16255b20384fSRyusuke Konishi
16265b20384fSRyusuke Konishi ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
16275b20384fSRyusuke Konishi if (!ret)
16285b20384fSRyusuke Konishi *keyp = start;
16295b20384fSRyusuke Konishi else if (ret == -ENOENT)
16305b20384fSRyusuke Konishi ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
16315b20384fSRyusuke Konishi
16325b20384fSRyusuke Konishi nilfs_btree_free_path(path);
16335b20384fSRyusuke Konishi return ret;
16345b20384fSRyusuke Konishi }
16355b20384fSRyusuke Konishi
nilfs_btree_last_key(const struct nilfs_bmap * btree,__u64 * keyp)1636e7c274f8SRyusuke Konishi static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
163717c76b01SKoji Sato {
163817c76b01SKoji Sato struct nilfs_btree_path *path;
163917c76b01SKoji Sato int ret;
164017c76b01SKoji Sato
16416d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
164217c76b01SKoji Sato if (path == NULL)
164317c76b01SKoji Sato return -ENOMEM;
164417c76b01SKoji Sato
164517c76b01SKoji Sato ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
164617c76b01SKoji Sato
16476d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
164817c76b01SKoji Sato
164917c76b01SKoji Sato return ret;
165017c76b01SKoji Sato }
165117c76b01SKoji Sato
nilfs_btree_check_delete(struct nilfs_bmap * btree,__u64 key)1652e7c274f8SRyusuke Konishi static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
165317c76b01SKoji Sato {
165417c76b01SKoji Sato struct buffer_head *bh;
165517c76b01SKoji Sato struct nilfs_btree_node *root, *node;
165617c76b01SKoji Sato __u64 maxkey, nextmaxkey;
165717c76b01SKoji Sato __u64 ptr;
165817c76b01SKoji Sato int nchildren, ret;
165917c76b01SKoji Sato
166017c76b01SKoji Sato root = nilfs_btree_get_root(btree);
166117c76b01SKoji Sato switch (nilfs_btree_height(btree)) {
166217c76b01SKoji Sato case 2:
166317c76b01SKoji Sato bh = NULL;
166417c76b01SKoji Sato node = root;
166517c76b01SKoji Sato break;
166617c76b01SKoji Sato case 3:
16676d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(root);
166817c76b01SKoji Sato if (nchildren > 1)
166917c76b01SKoji Sato return 0;
16709b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
16719b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
1672f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, ptr, &bh);
167317c76b01SKoji Sato if (ret < 0)
167417c76b01SKoji Sato return ret;
167517c76b01SKoji Sato node = (struct nilfs_btree_node *)bh->b_data;
167617c76b01SKoji Sato break;
167717c76b01SKoji Sato default:
167817c76b01SKoji Sato return 0;
167917c76b01SKoji Sato }
168017c76b01SKoji Sato
16816d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
16826d28f7eaSRyusuke Konishi maxkey = nilfs_btree_node_get_key(node, nchildren - 1);
168317c76b01SKoji Sato nextmaxkey = (nchildren > 1) ?
16846d28f7eaSRyusuke Konishi nilfs_btree_node_get_key(node, nchildren - 2) : 0;
1685087d01b4SRyusuke Konishi brelse(bh);
168617c76b01SKoji Sato
16873033342aSRyusuke Konishi return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
168817c76b01SKoji Sato }
168917c76b01SKoji Sato
nilfs_btree_gather_data(struct nilfs_bmap * btree,__u64 * keys,__u64 * ptrs,int nitems)1690e7c274f8SRyusuke Konishi static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
169117c76b01SKoji Sato __u64 *keys, __u64 *ptrs, int nitems)
169217c76b01SKoji Sato {
169317c76b01SKoji Sato struct buffer_head *bh;
169417c76b01SKoji Sato struct nilfs_btree_node *node, *root;
169517c76b01SKoji Sato __le64 *dkeys;
169617c76b01SKoji Sato __le64 *dptrs;
169717c76b01SKoji Sato __u64 ptr;
16989b7b265cSRyusuke Konishi int nchildren, ncmax, i, ret;
169917c76b01SKoji Sato
170017c76b01SKoji Sato root = nilfs_btree_get_root(btree);
170117c76b01SKoji Sato switch (nilfs_btree_height(btree)) {
170217c76b01SKoji Sato case 2:
170317c76b01SKoji Sato bh = NULL;
170417c76b01SKoji Sato node = root;
17059b7b265cSRyusuke Konishi ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX;
170617c76b01SKoji Sato break;
170717c76b01SKoji Sato case 3:
17086d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(root);
17091f5abe7eSRyusuke Konishi WARN_ON(nchildren > 1);
17109b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
17119b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
1712f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, ptr, &bh);
171317c76b01SKoji Sato if (ret < 0)
171417c76b01SKoji Sato return ret;
171517c76b01SKoji Sato node = (struct nilfs_btree_node *)bh->b_data;
17169b7b265cSRyusuke Konishi ncmax = nilfs_btree_nchildren_per_block(btree);
171717c76b01SKoji Sato break;
171817c76b01SKoji Sato default:
171917c76b01SKoji Sato node = NULL;
17201f5abe7eSRyusuke Konishi return -EINVAL;
172117c76b01SKoji Sato }
172217c76b01SKoji Sato
17236d28f7eaSRyusuke Konishi nchildren = nilfs_btree_node_get_nchildren(node);
172417c76b01SKoji Sato if (nchildren < nitems)
172517c76b01SKoji Sato nitems = nchildren;
17266d28f7eaSRyusuke Konishi dkeys = nilfs_btree_node_dkeys(node);
17279b7b265cSRyusuke Konishi dptrs = nilfs_btree_node_dptrs(node, ncmax);
172817c76b01SKoji Sato for (i = 0; i < nitems; i++) {
172925b8d7deSRyusuke Konishi keys[i] = le64_to_cpu(dkeys[i]);
173025b8d7deSRyusuke Konishi ptrs[i] = le64_to_cpu(dptrs[i]);
173117c76b01SKoji Sato }
173217c76b01SKoji Sato
1733087d01b4SRyusuke Konishi brelse(bh);
173417c76b01SKoji Sato
173517c76b01SKoji Sato return nitems;
173617c76b01SKoji Sato }
173717c76b01SKoji Sato
173817c76b01SKoji Sato static int
nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap * btree,__u64 key,union nilfs_bmap_ptr_req * dreq,union nilfs_bmap_ptr_req * nreq,struct buffer_head ** bhp,struct nilfs_bmap_stats * stats)1739e7c274f8SRyusuke Konishi nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
174017c76b01SKoji Sato union nilfs_bmap_ptr_req *dreq,
174117c76b01SKoji Sato union nilfs_bmap_ptr_req *nreq,
174217c76b01SKoji Sato struct buffer_head **bhp,
174317c76b01SKoji Sato struct nilfs_bmap_stats *stats)
174417c76b01SKoji Sato {
174517c76b01SKoji Sato struct buffer_head *bh;
17462e0c2c73SRyusuke Konishi struct inode *dat = NULL;
174717c76b01SKoji Sato int ret;
174817c76b01SKoji Sato
174917c76b01SKoji Sato stats->bs_nblocks = 0;
175017c76b01SKoji Sato
175117c76b01SKoji Sato /* for data */
175217c76b01SKoji Sato /* cannot find near ptr */
1753e7c274f8SRyusuke Konishi if (NILFS_BMAP_USE_VBN(btree)) {
17547cde31d7SRyusuke Konishi dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
1755e7c274f8SRyusuke Konishi dat = nilfs_bmap_get_dat(btree);
17562e0c2c73SRyusuke Konishi }
17577cde31d7SRyusuke Konishi
1758e897be17SRyusuke Konishi ret = nilfs_attach_btree_node_cache(&NILFS_BMAP_I(btree)->vfs_inode);
1759e897be17SRyusuke Konishi if (ret < 0)
1760e897be17SRyusuke Konishi return ret;
1761e897be17SRyusuke Konishi
1762e7c274f8SRyusuke Konishi ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
176317c76b01SKoji Sato if (ret < 0)
176417c76b01SKoji Sato return ret;
176517c76b01SKoji Sato
176617c76b01SKoji Sato *bhp = NULL;
176717c76b01SKoji Sato stats->bs_nblocks++;
176817c76b01SKoji Sato if (nreq != NULL) {
176917c76b01SKoji Sato nreq->bpr_ptr = dreq->bpr_ptr + 1;
1770e7c274f8SRyusuke Konishi ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
177117c76b01SKoji Sato if (ret < 0)
177217c76b01SKoji Sato goto err_out_dreq;
177317c76b01SKoji Sato
1774f198dbb9SRyusuke Konishi ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
177517c76b01SKoji Sato if (ret < 0)
177617c76b01SKoji Sato goto err_out_nreq;
177717c76b01SKoji Sato
177817c76b01SKoji Sato *bhp = bh;
177917c76b01SKoji Sato stats->bs_nblocks++;
178017c76b01SKoji Sato }
178117c76b01SKoji Sato
178217c76b01SKoji Sato /* success */
178317c76b01SKoji Sato return 0;
178417c76b01SKoji Sato
178517c76b01SKoji Sato /* error */
178617c76b01SKoji Sato err_out_nreq:
1787e7c274f8SRyusuke Konishi nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
178817c76b01SKoji Sato err_out_dreq:
1789e7c274f8SRyusuke Konishi nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
179017c76b01SKoji Sato stats->bs_nblocks = 0;
179117c76b01SKoji Sato return ret;
179217c76b01SKoji Sato
179317c76b01SKoji Sato }
179417c76b01SKoji Sato
179517c76b01SKoji Sato static void
nilfs_btree_commit_convert_and_insert(struct nilfs_bmap * btree,__u64 key,__u64 ptr,const __u64 * keys,const __u64 * ptrs,int n,union nilfs_bmap_ptr_req * dreq,union nilfs_bmap_ptr_req * nreq,struct buffer_head * bh)1796e7c274f8SRyusuke Konishi nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
179717c76b01SKoji Sato __u64 key, __u64 ptr,
179817c76b01SKoji Sato const __u64 *keys, const __u64 *ptrs,
17993033342aSRyusuke Konishi int n,
180017c76b01SKoji Sato union nilfs_bmap_ptr_req *dreq,
180117c76b01SKoji Sato union nilfs_bmap_ptr_req *nreq,
180217c76b01SKoji Sato struct buffer_head *bh)
180317c76b01SKoji Sato {
180417c76b01SKoji Sato struct nilfs_btree_node *node;
18052e0c2c73SRyusuke Konishi struct inode *dat;
180617c76b01SKoji Sato __u64 tmpptr;
18079b7b265cSRyusuke Konishi int ncblk;
180817c76b01SKoji Sato
180917c76b01SKoji Sato /* free resources */
1810e7c274f8SRyusuke Konishi if (btree->b_ops->bop_clear != NULL)
1811e7c274f8SRyusuke Konishi btree->b_ops->bop_clear(btree);
181217c76b01SKoji Sato
181317c76b01SKoji Sato /* ptr must be a pointer to a buffer head. */
181417c76b01SKoji Sato set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
181517c76b01SKoji Sato
181617c76b01SKoji Sato /* convert and insert */
1817e7c274f8SRyusuke Konishi dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1818957ed60bSRyusuke Konishi __nilfs_btree_init(btree);
181917c76b01SKoji Sato if (nreq != NULL) {
1820e7c274f8SRyusuke Konishi nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1821e7c274f8SRyusuke Konishi nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
182217c76b01SKoji Sato
182317c76b01SKoji Sato /* create child node at level 1 */
182417c76b01SKoji Sato node = (struct nilfs_btree_node *)bh->b_data;
18259b7b265cSRyusuke Konishi ncblk = nilfs_btree_nchildren_per_block(btree);
18269b7b265cSRyusuke Konishi nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs);
18279b7b265cSRyusuke Konishi nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk);
182817c76b01SKoji Sato if (!buffer_dirty(bh))
18295fc7b141SRyusuke Konishi mark_buffer_dirty(bh);
1830e7c274f8SRyusuke Konishi if (!nilfs_bmap_dirty(btree))
1831e7c274f8SRyusuke Konishi nilfs_bmap_set_dirty(btree);
183217c76b01SKoji Sato
1833087d01b4SRyusuke Konishi brelse(bh);
183417c76b01SKoji Sato
183517c76b01SKoji Sato /* create root node at level 2 */
183617c76b01SKoji Sato node = nilfs_btree_get_root(btree);
183717c76b01SKoji Sato tmpptr = nreq->bpr_ptr;
18389b7b265cSRyusuke Konishi nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1,
18399b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX,
18409b7b265cSRyusuke Konishi &keys[0], &tmpptr);
184117c76b01SKoji Sato } else {
1842e7c274f8SRyusuke Konishi nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
184317c76b01SKoji Sato
184417c76b01SKoji Sato /* create root node at level 1 */
184517c76b01SKoji Sato node = nilfs_btree_get_root(btree);
18469b7b265cSRyusuke Konishi nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n,
18479b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX,
18489b7b265cSRyusuke Konishi keys, ptrs);
18499b7b265cSRyusuke Konishi nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr,
18509b7b265cSRyusuke Konishi NILFS_BTREE_ROOT_NCHILDREN_MAX);
1851e7c274f8SRyusuke Konishi if (!nilfs_bmap_dirty(btree))
1852e7c274f8SRyusuke Konishi nilfs_bmap_set_dirty(btree);
185317c76b01SKoji Sato }
185417c76b01SKoji Sato
1855e7c274f8SRyusuke Konishi if (NILFS_BMAP_USE_VBN(btree))
1856dc935be2SRyusuke Konishi nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
185717c76b01SKoji Sato }
185817c76b01SKoji Sato
185917c76b01SKoji Sato /**
186017c76b01SKoji Sato * nilfs_btree_convert_and_insert -
186117c76b01SKoji Sato * @bmap:
186217c76b01SKoji Sato * @key:
186317c76b01SKoji Sato * @ptr:
186417c76b01SKoji Sato * @keys:
186517c76b01SKoji Sato * @ptrs:
186617c76b01SKoji Sato * @n:
186717c76b01SKoji Sato */
nilfs_btree_convert_and_insert(struct nilfs_bmap * btree,__u64 key,__u64 ptr,const __u64 * keys,const __u64 * ptrs,int n)1868e7c274f8SRyusuke Konishi int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
186917c76b01SKoji Sato __u64 key, __u64 ptr,
18703033342aSRyusuke Konishi const __u64 *keys, const __u64 *ptrs, int n)
187117c76b01SKoji Sato {
18724f05028fSRyusuke Konishi struct buffer_head *bh = NULL;
187317c76b01SKoji Sato union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
187417c76b01SKoji Sato struct nilfs_bmap_stats stats;
187517c76b01SKoji Sato int ret;
187617c76b01SKoji Sato
187717c76b01SKoji Sato if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
187817c76b01SKoji Sato di = &dreq;
187917c76b01SKoji Sato ni = NULL;
188017c76b01SKoji Sato } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
18811508ddc3SGeliang Tang nilfs_btree_node_size(btree))) {
188217c76b01SKoji Sato di = &dreq;
188317c76b01SKoji Sato ni = &nreq;
188417c76b01SKoji Sato } else {
188517c76b01SKoji Sato di = NULL;
188617c76b01SKoji Sato ni = NULL;
188717c76b01SKoji Sato BUG();
188817c76b01SKoji Sato }
188917c76b01SKoji Sato
1890e7c274f8SRyusuke Konishi ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
189117c76b01SKoji Sato &stats);
189217c76b01SKoji Sato if (ret < 0)
189317c76b01SKoji Sato return ret;
1894e7c274f8SRyusuke Konishi nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
18953033342aSRyusuke Konishi di, ni, bh);
1896be667377SRyusuke Konishi nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
189717c76b01SKoji Sato return 0;
189817c76b01SKoji Sato }
189917c76b01SKoji Sato
nilfs_btree_propagate_p(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct buffer_head * bh)1900e7c274f8SRyusuke Konishi static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
190117c76b01SKoji Sato struct nilfs_btree_path *path,
190217c76b01SKoji Sato int level,
190317c76b01SKoji Sato struct buffer_head *bh)
190417c76b01SKoji Sato {
190517c76b01SKoji Sato while ((++level < nilfs_btree_height(btree) - 1) &&
190617c76b01SKoji Sato !buffer_dirty(path[level].bp_bh))
19075fc7b141SRyusuke Konishi mark_buffer_dirty(path[level].bp_bh);
190817c76b01SKoji Sato
190917c76b01SKoji Sato return 0;
191017c76b01SKoji Sato }
191117c76b01SKoji Sato
nilfs_btree_prepare_update_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct inode * dat)1912e7c274f8SRyusuke Konishi static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
191317c76b01SKoji Sato struct nilfs_btree_path *path,
19142e0c2c73SRyusuke Konishi int level, struct inode *dat)
191517c76b01SKoji Sato {
191617c76b01SKoji Sato struct nilfs_btree_node *parent;
19179b7b265cSRyusuke Konishi int ncmax, ret;
191817c76b01SKoji Sato
19199b7b265cSRyusuke Konishi parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
192017c76b01SKoji Sato path[level].bp_oldreq.bpr_ptr =
19219b7b265cSRyusuke Konishi nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
19229b7b265cSRyusuke Konishi ncmax);
192317c76b01SKoji Sato path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
19242e0c2c73SRyusuke Konishi ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
19252e0c2c73SRyusuke Konishi &path[level].bp_newreq.bpr_req);
192617c76b01SKoji Sato if (ret < 0)
192717c76b01SKoji Sato return ret;
192817c76b01SKoji Sato
192917c76b01SKoji Sato if (buffer_nilfs_node(path[level].bp_bh)) {
193017c76b01SKoji Sato path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
193117c76b01SKoji Sato path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
193217c76b01SKoji Sato path[level].bp_ctxt.bh = path[level].bp_bh;
193317c76b01SKoji Sato ret = nilfs_btnode_prepare_change_key(
1934e897be17SRyusuke Konishi NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
193517c76b01SKoji Sato &path[level].bp_ctxt);
193617c76b01SKoji Sato if (ret < 0) {
19372e0c2c73SRyusuke Konishi nilfs_dat_abort_update(dat,
19382e0c2c73SRyusuke Konishi &path[level].bp_oldreq.bpr_req,
19392e0c2c73SRyusuke Konishi &path[level].bp_newreq.bpr_req);
194017c76b01SKoji Sato return ret;
194117c76b01SKoji Sato }
194217c76b01SKoji Sato }
194317c76b01SKoji Sato
194417c76b01SKoji Sato return 0;
194517c76b01SKoji Sato }
194617c76b01SKoji Sato
nilfs_btree_commit_update_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct inode * dat)1947e7c274f8SRyusuke Konishi static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
194817c76b01SKoji Sato struct nilfs_btree_path *path,
19492e0c2c73SRyusuke Konishi int level, struct inode *dat)
195017c76b01SKoji Sato {
195117c76b01SKoji Sato struct nilfs_btree_node *parent;
19529b7b265cSRyusuke Konishi int ncmax;
195317c76b01SKoji Sato
19542e0c2c73SRyusuke Konishi nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
19552e0c2c73SRyusuke Konishi &path[level].bp_newreq.bpr_req,
1956e7c274f8SRyusuke Konishi btree->b_ptr_type == NILFS_BMAP_PTR_VS);
195717c76b01SKoji Sato
195817c76b01SKoji Sato if (buffer_nilfs_node(path[level].bp_bh)) {
195917c76b01SKoji Sato nilfs_btnode_commit_change_key(
1960e897be17SRyusuke Konishi NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
196117c76b01SKoji Sato &path[level].bp_ctxt);
196217c76b01SKoji Sato path[level].bp_bh = path[level].bp_ctxt.bh;
196317c76b01SKoji Sato }
196417c76b01SKoji Sato set_buffer_nilfs_volatile(path[level].bp_bh);
196517c76b01SKoji Sato
19669b7b265cSRyusuke Konishi parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
19679b7b265cSRyusuke Konishi nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
19689b7b265cSRyusuke Konishi path[level].bp_newreq.bpr_ptr, ncmax);
196917c76b01SKoji Sato }
197017c76b01SKoji Sato
nilfs_btree_abort_update_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct inode * dat)1971e7c274f8SRyusuke Konishi static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
197217c76b01SKoji Sato struct nilfs_btree_path *path,
19732e0c2c73SRyusuke Konishi int level, struct inode *dat)
197417c76b01SKoji Sato {
19752e0c2c73SRyusuke Konishi nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
19762e0c2c73SRyusuke Konishi &path[level].bp_newreq.bpr_req);
197717c76b01SKoji Sato if (buffer_nilfs_node(path[level].bp_bh))
197817c76b01SKoji Sato nilfs_btnode_abort_change_key(
1979e897be17SRyusuke Konishi NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
198017c76b01SKoji Sato &path[level].bp_ctxt);
198117c76b01SKoji Sato }
198217c76b01SKoji Sato
nilfs_btree_prepare_propagate_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int minlevel,int * maxlevelp,struct inode * dat)1983e7c274f8SRyusuke Konishi static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
198417c76b01SKoji Sato struct nilfs_btree_path *path,
19852e0c2c73SRyusuke Konishi int minlevel, int *maxlevelp,
19862e0c2c73SRyusuke Konishi struct inode *dat)
198717c76b01SKoji Sato {
198817c76b01SKoji Sato int level, ret;
198917c76b01SKoji Sato
199017c76b01SKoji Sato level = minlevel;
199117c76b01SKoji Sato if (!buffer_nilfs_volatile(path[level].bp_bh)) {
19922e0c2c73SRyusuke Konishi ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
199317c76b01SKoji Sato if (ret < 0)
199417c76b01SKoji Sato return ret;
199517c76b01SKoji Sato }
199617c76b01SKoji Sato while ((++level < nilfs_btree_height(btree) - 1) &&
199717c76b01SKoji Sato !buffer_dirty(path[level].bp_bh)) {
199817c76b01SKoji Sato
19991f5abe7eSRyusuke Konishi WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
20002e0c2c73SRyusuke Konishi ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
200117c76b01SKoji Sato if (ret < 0)
200217c76b01SKoji Sato goto out;
200317c76b01SKoji Sato }
200417c76b01SKoji Sato
200517c76b01SKoji Sato /* success */
200617c76b01SKoji Sato *maxlevelp = level - 1;
200717c76b01SKoji Sato return 0;
200817c76b01SKoji Sato
200917c76b01SKoji Sato /* error */
201017c76b01SKoji Sato out:
201117c76b01SKoji Sato while (--level > minlevel)
20122e0c2c73SRyusuke Konishi nilfs_btree_abort_update_v(btree, path, level, dat);
201317c76b01SKoji Sato if (!buffer_nilfs_volatile(path[level].bp_bh))
20142e0c2c73SRyusuke Konishi nilfs_btree_abort_update_v(btree, path, level, dat);
201517c76b01SKoji Sato return ret;
201617c76b01SKoji Sato }
201717c76b01SKoji Sato
nilfs_btree_commit_propagate_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int minlevel,int maxlevel,struct buffer_head * bh,struct inode * dat)2018e7c274f8SRyusuke Konishi static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
201917c76b01SKoji Sato struct nilfs_btree_path *path,
20202e0c2c73SRyusuke Konishi int minlevel, int maxlevel,
20212e0c2c73SRyusuke Konishi struct buffer_head *bh,
20222e0c2c73SRyusuke Konishi struct inode *dat)
202317c76b01SKoji Sato {
202417c76b01SKoji Sato int level;
202517c76b01SKoji Sato
202617c76b01SKoji Sato if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
20272e0c2c73SRyusuke Konishi nilfs_btree_commit_update_v(btree, path, minlevel, dat);
202817c76b01SKoji Sato
202917c76b01SKoji Sato for (level = minlevel + 1; level <= maxlevel; level++)
20302e0c2c73SRyusuke Konishi nilfs_btree_commit_update_v(btree, path, level, dat);
203117c76b01SKoji Sato }
203217c76b01SKoji Sato
nilfs_btree_propagate_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct buffer_head * bh)2033e7c274f8SRyusuke Konishi static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
203417c76b01SKoji Sato struct nilfs_btree_path *path,
20352e0c2c73SRyusuke Konishi int level, struct buffer_head *bh)
203617c76b01SKoji Sato {
2037308f4419SLi Hong int maxlevel = 0, ret;
203817c76b01SKoji Sato struct nilfs_btree_node *parent;
2039e7c274f8SRyusuke Konishi struct inode *dat = nilfs_bmap_get_dat(btree);
204017c76b01SKoji Sato __u64 ptr;
20419b7b265cSRyusuke Konishi int ncmax;
204217c76b01SKoji Sato
204317c76b01SKoji Sato get_bh(bh);
204417c76b01SKoji Sato path[level].bp_bh = bh;
20452e0c2c73SRyusuke Konishi ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
20462e0c2c73SRyusuke Konishi dat);
204717c76b01SKoji Sato if (ret < 0)
204817c76b01SKoji Sato goto out;
204917c76b01SKoji Sato
205017c76b01SKoji Sato if (buffer_nilfs_volatile(path[level].bp_bh)) {
20519b7b265cSRyusuke Konishi parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
20529b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(parent,
20539b7b265cSRyusuke Konishi path[level + 1].bp_index,
20549b7b265cSRyusuke Konishi ncmax);
20552e0c2c73SRyusuke Konishi ret = nilfs_dat_mark_dirty(dat, ptr);
205617c76b01SKoji Sato if (ret < 0)
205717c76b01SKoji Sato goto out;
205817c76b01SKoji Sato }
205917c76b01SKoji Sato
20602e0c2c73SRyusuke Konishi nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
206117c76b01SKoji Sato
206217c76b01SKoji Sato out:
206317c76b01SKoji Sato brelse(path[level].bp_bh);
206417c76b01SKoji Sato path[level].bp_bh = NULL;
206517c76b01SKoji Sato return ret;
206617c76b01SKoji Sato }
206717c76b01SKoji Sato
nilfs_btree_propagate(struct nilfs_bmap * btree,struct buffer_head * bh)2068e7c274f8SRyusuke Konishi static int nilfs_btree_propagate(struct nilfs_bmap *btree,
206917c76b01SKoji Sato struct buffer_head *bh)
207017c76b01SKoji Sato {
207117c76b01SKoji Sato struct nilfs_btree_path *path;
207217c76b01SKoji Sato struct nilfs_btree_node *node;
207317c76b01SKoji Sato __u64 key;
207417c76b01SKoji Sato int level, ret;
207517c76b01SKoji Sato
20761f5abe7eSRyusuke Konishi WARN_ON(!buffer_dirty(bh));
207717c76b01SKoji Sato
20786d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
207917c76b01SKoji Sato if (path == NULL)
208017c76b01SKoji Sato return -ENOMEM;
208117c76b01SKoji Sato
208217c76b01SKoji Sato if (buffer_nilfs_node(bh)) {
208317c76b01SKoji Sato node = (struct nilfs_btree_node *)bh->b_data;
20846d28f7eaSRyusuke Konishi key = nilfs_btree_node_get_key(node, 0);
20856d28f7eaSRyusuke Konishi level = nilfs_btree_node_get_level(node);
208617c76b01SKoji Sato } else {
2087e7c274f8SRyusuke Konishi key = nilfs_bmap_data_get_key(btree, bh);
208817c76b01SKoji Sato level = NILFS_BTREE_LEVEL_DATA;
208917c76b01SKoji Sato }
209017c76b01SKoji Sato
209103bdb5acSRyusuke Konishi ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
209217c76b01SKoji Sato if (ret < 0) {
20931f5abe7eSRyusuke Konishi if (unlikely(ret == -ENOENT))
2094a1d0747aSJoe Perches nilfs_crit(btree->b_inode->i_sb,
2095feee880fSRyusuke Konishi "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d",
2096feee880fSRyusuke Konishi btree->b_inode->i_ino,
2097feee880fSRyusuke Konishi (unsigned long long)key, level);
209817c76b01SKoji Sato goto out;
209917c76b01SKoji Sato }
210017c76b01SKoji Sato
2101e7c274f8SRyusuke Konishi ret = NILFS_BMAP_USE_VBN(btree) ?
21027cde31d7SRyusuke Konishi nilfs_btree_propagate_v(btree, path, level, bh) :
21037cde31d7SRyusuke Konishi nilfs_btree_propagate_p(btree, path, level, bh);
210417c76b01SKoji Sato
210517c76b01SKoji Sato out:
21066d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
210717c76b01SKoji Sato
210817c76b01SKoji Sato return ret;
210917c76b01SKoji Sato }
211017c76b01SKoji Sato
nilfs_btree_propagate_gc(struct nilfs_bmap * btree,struct buffer_head * bh)2111e7c274f8SRyusuke Konishi static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
211217c76b01SKoji Sato struct buffer_head *bh)
211317c76b01SKoji Sato {
2114e7c274f8SRyusuke Konishi return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
211517c76b01SKoji Sato }
211617c76b01SKoji Sato
nilfs_btree_add_dirty_buffer(struct nilfs_bmap * btree,struct list_head * lists,struct buffer_head * bh)2117e7c274f8SRyusuke Konishi static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
211817c76b01SKoji Sato struct list_head *lists,
211917c76b01SKoji Sato struct buffer_head *bh)
212017c76b01SKoji Sato {
212117c76b01SKoji Sato struct list_head *head;
212217c76b01SKoji Sato struct buffer_head *cbh;
212317c76b01SKoji Sato struct nilfs_btree_node *node, *cnode;
212417c76b01SKoji Sato __u64 key, ckey;
212517c76b01SKoji Sato int level;
212617c76b01SKoji Sato
212717c76b01SKoji Sato get_bh(bh);
212817c76b01SKoji Sato node = (struct nilfs_btree_node *)bh->b_data;
21296d28f7eaSRyusuke Konishi key = nilfs_btree_node_get_key(node, 0);
21306d28f7eaSRyusuke Konishi level = nilfs_btree_node_get_level(node);
2131cfa913a5SRyusuke Konishi if (level < NILFS_BTREE_LEVEL_NODE_MIN ||
2132cfa913a5SRyusuke Konishi level >= NILFS_BTREE_LEVEL_MAX) {
2133cfa913a5SRyusuke Konishi dump_stack();
2134a1d0747aSJoe Perches nilfs_warn(btree->b_inode->i_sb,
2135feee880fSRyusuke Konishi "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",
2136feee880fSRyusuke Konishi level, (unsigned long long)key,
2137feee880fSRyusuke Konishi btree->b_inode->i_ino,
2138cfa913a5SRyusuke Konishi (unsigned long long)bh->b_blocknr);
2139cfa913a5SRyusuke Konishi return;
2140cfa913a5SRyusuke Konishi }
2141cfa913a5SRyusuke Konishi
214217c76b01SKoji Sato list_for_each(head, &lists[level]) {
214317c76b01SKoji Sato cbh = list_entry(head, struct buffer_head, b_assoc_buffers);
214417c76b01SKoji Sato cnode = (struct nilfs_btree_node *)cbh->b_data;
21456d28f7eaSRyusuke Konishi ckey = nilfs_btree_node_get_key(cnode, 0);
214617c76b01SKoji Sato if (key < ckey)
214717c76b01SKoji Sato break;
214817c76b01SKoji Sato }
214917c76b01SKoji Sato list_add_tail(&bh->b_assoc_buffers, head);
215017c76b01SKoji Sato }
215117c76b01SKoji Sato
nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap * btree,struct list_head * listp)2152e7c274f8SRyusuke Konishi static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
215317c76b01SKoji Sato struct list_head *listp)
215417c76b01SKoji Sato {
2155e897be17SRyusuke Konishi struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
2156e897be17SRyusuke Konishi struct address_space *btcache = btnc_inode->i_mapping;
215717c76b01SKoji Sato struct list_head lists[NILFS_BTREE_LEVEL_MAX];
215841f3f3b5SVishal Moola (Oracle) struct folio_batch fbatch;
215917c76b01SKoji Sato struct buffer_head *bh, *head;
216017c76b01SKoji Sato pgoff_t index = 0;
216117c76b01SKoji Sato int level, i;
216217c76b01SKoji Sato
216317c76b01SKoji Sato for (level = NILFS_BTREE_LEVEL_NODE_MIN;
216417c76b01SKoji Sato level < NILFS_BTREE_LEVEL_MAX;
216517c76b01SKoji Sato level++)
216617c76b01SKoji Sato INIT_LIST_HEAD(&lists[level]);
216717c76b01SKoji Sato
216841f3f3b5SVishal Moola (Oracle) folio_batch_init(&fbatch);
216917c76b01SKoji Sato
217041f3f3b5SVishal Moola (Oracle) while (filemap_get_folios_tag(btcache, &index, (pgoff_t)-1,
217141f3f3b5SVishal Moola (Oracle) PAGECACHE_TAG_DIRTY, &fbatch)) {
217241f3f3b5SVishal Moola (Oracle) for (i = 0; i < folio_batch_count(&fbatch); i++) {
217341f3f3b5SVishal Moola (Oracle) bh = head = folio_buffers(fbatch.folios[i]);
217417c76b01SKoji Sato do {
217517c76b01SKoji Sato if (buffer_dirty(bh))
217617c76b01SKoji Sato nilfs_btree_add_dirty_buffer(btree,
217717c76b01SKoji Sato lists, bh);
217817c76b01SKoji Sato } while ((bh = bh->b_this_page) != head);
217917c76b01SKoji Sato }
218041f3f3b5SVishal Moola (Oracle) folio_batch_release(&fbatch);
218117c76b01SKoji Sato cond_resched();
218217c76b01SKoji Sato }
218317c76b01SKoji Sato
218417c76b01SKoji Sato for (level = NILFS_BTREE_LEVEL_NODE_MIN;
218517c76b01SKoji Sato level < NILFS_BTREE_LEVEL_MAX;
218617c76b01SKoji Sato level++)
21870935db74SRyusuke Konishi list_splice_tail(&lists[level], listp);
218817c76b01SKoji Sato }
218917c76b01SKoji Sato
nilfs_btree_assign_p(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct buffer_head ** bh,sector_t blocknr,union nilfs_binfo * binfo)2190e7c274f8SRyusuke Konishi static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
219117c76b01SKoji Sato struct nilfs_btree_path *path,
219217c76b01SKoji Sato int level,
219317c76b01SKoji Sato struct buffer_head **bh,
219417c76b01SKoji Sato sector_t blocknr,
219517c76b01SKoji Sato union nilfs_binfo *binfo)
219617c76b01SKoji Sato {
219717c76b01SKoji Sato struct nilfs_btree_node *parent;
219817c76b01SKoji Sato __u64 key;
219917c76b01SKoji Sato __u64 ptr;
22009b7b265cSRyusuke Konishi int ncmax, ret;
220117c76b01SKoji Sato
22029b7b265cSRyusuke Konishi parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
22039b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
22049b7b265cSRyusuke Konishi ncmax);
220517c76b01SKoji Sato if (buffer_nilfs_node(*bh)) {
220617c76b01SKoji Sato path[level].bp_ctxt.oldkey = ptr;
220717c76b01SKoji Sato path[level].bp_ctxt.newkey = blocknr;
220817c76b01SKoji Sato path[level].bp_ctxt.bh = *bh;
220917c76b01SKoji Sato ret = nilfs_btnode_prepare_change_key(
2210e897be17SRyusuke Konishi NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
221117c76b01SKoji Sato &path[level].bp_ctxt);
221217c76b01SKoji Sato if (ret < 0)
221317c76b01SKoji Sato return ret;
221417c76b01SKoji Sato nilfs_btnode_commit_change_key(
2215e897be17SRyusuke Konishi NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
221617c76b01SKoji Sato &path[level].bp_ctxt);
221717c76b01SKoji Sato *bh = path[level].bp_ctxt.bh;
221817c76b01SKoji Sato }
221917c76b01SKoji Sato
22209b7b265cSRyusuke Konishi nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
22219b7b265cSRyusuke Konishi ncmax);
222217c76b01SKoji Sato
22236d28f7eaSRyusuke Konishi key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
222417c76b01SKoji Sato /* on-disk format */
222525b8d7deSRyusuke Konishi binfo->bi_dat.bi_blkoff = cpu_to_le64(key);
222617c76b01SKoji Sato binfo->bi_dat.bi_level = level;
222773970316STetsuo Handa memset(binfo->bi_dat.bi_pad, 0, sizeof(binfo->bi_dat.bi_pad));
222817c76b01SKoji Sato
222917c76b01SKoji Sato return 0;
223017c76b01SKoji Sato }
223117c76b01SKoji Sato
nilfs_btree_assign_v(struct nilfs_bmap * btree,struct nilfs_btree_path * path,int level,struct buffer_head ** bh,sector_t blocknr,union nilfs_binfo * binfo)2232e7c274f8SRyusuke Konishi static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
223317c76b01SKoji Sato struct nilfs_btree_path *path,
223417c76b01SKoji Sato int level,
223517c76b01SKoji Sato struct buffer_head **bh,
223617c76b01SKoji Sato sector_t blocknr,
223717c76b01SKoji Sato union nilfs_binfo *binfo)
223817c76b01SKoji Sato {
223917c76b01SKoji Sato struct nilfs_btree_node *parent;
2240e7c274f8SRyusuke Konishi struct inode *dat = nilfs_bmap_get_dat(btree);
224117c76b01SKoji Sato __u64 key;
224217c76b01SKoji Sato __u64 ptr;
224317c76b01SKoji Sato union nilfs_bmap_ptr_req req;
22449b7b265cSRyusuke Konishi int ncmax, ret;
224517c76b01SKoji Sato
22469b7b265cSRyusuke Konishi parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
22479b7b265cSRyusuke Konishi ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
22489b7b265cSRyusuke Konishi ncmax);
224917c76b01SKoji Sato req.bpr_ptr = ptr;
22502e0c2c73SRyusuke Konishi ret = nilfs_dat_prepare_start(dat, &req.bpr_req);
22512e0c2c73SRyusuke Konishi if (ret < 0)
225217c76b01SKoji Sato return ret;
22532e0c2c73SRyusuke Konishi nilfs_dat_commit_start(dat, &req.bpr_req, blocknr);
225417c76b01SKoji Sato
22556d28f7eaSRyusuke Konishi key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
225617c76b01SKoji Sato /* on-disk format */
225725b8d7deSRyusuke Konishi binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr);
225825b8d7deSRyusuke Konishi binfo->bi_v.bi_blkoff = cpu_to_le64(key);
225917c76b01SKoji Sato
226017c76b01SKoji Sato return 0;
226117c76b01SKoji Sato }
226217c76b01SKoji Sato
nilfs_btree_assign(struct nilfs_bmap * btree,struct buffer_head ** bh,sector_t blocknr,union nilfs_binfo * binfo)2263e7c274f8SRyusuke Konishi static int nilfs_btree_assign(struct nilfs_bmap *btree,
226417c76b01SKoji Sato struct buffer_head **bh,
226517c76b01SKoji Sato sector_t blocknr,
226617c76b01SKoji Sato union nilfs_binfo *binfo)
226717c76b01SKoji Sato {
226817c76b01SKoji Sato struct nilfs_btree_path *path;
226917c76b01SKoji Sato struct nilfs_btree_node *node;
227017c76b01SKoji Sato __u64 key;
227117c76b01SKoji Sato int level, ret;
227217c76b01SKoji Sato
22736d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
227417c76b01SKoji Sato if (path == NULL)
227517c76b01SKoji Sato return -ENOMEM;
227617c76b01SKoji Sato
227717c76b01SKoji Sato if (buffer_nilfs_node(*bh)) {
227817c76b01SKoji Sato node = (struct nilfs_btree_node *)(*bh)->b_data;
22796d28f7eaSRyusuke Konishi key = nilfs_btree_node_get_key(node, 0);
22806d28f7eaSRyusuke Konishi level = nilfs_btree_node_get_level(node);
228117c76b01SKoji Sato } else {
2282e7c274f8SRyusuke Konishi key = nilfs_bmap_data_get_key(btree, *bh);
228317c76b01SKoji Sato level = NILFS_BTREE_LEVEL_DATA;
228417c76b01SKoji Sato }
228517c76b01SKoji Sato
228603bdb5acSRyusuke Konishi ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
228717c76b01SKoji Sato if (ret < 0) {
22881f5abe7eSRyusuke Konishi WARN_ON(ret == -ENOENT);
228917c76b01SKoji Sato goto out;
229017c76b01SKoji Sato }
229117c76b01SKoji Sato
2292e7c274f8SRyusuke Konishi ret = NILFS_BMAP_USE_VBN(btree) ?
22937cde31d7SRyusuke Konishi nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
22947cde31d7SRyusuke Konishi nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
229517c76b01SKoji Sato
229617c76b01SKoji Sato out:
22976d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
229817c76b01SKoji Sato
229917c76b01SKoji Sato return ret;
230017c76b01SKoji Sato }
230117c76b01SKoji Sato
nilfs_btree_assign_gc(struct nilfs_bmap * btree,struct buffer_head ** bh,sector_t blocknr,union nilfs_binfo * binfo)2302e7c274f8SRyusuke Konishi static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
230317c76b01SKoji Sato struct buffer_head **bh,
230417c76b01SKoji Sato sector_t blocknr,
230517c76b01SKoji Sato union nilfs_binfo *binfo)
230617c76b01SKoji Sato {
230717c76b01SKoji Sato struct nilfs_btree_node *node;
230817c76b01SKoji Sato __u64 key;
230917c76b01SKoji Sato int ret;
231017c76b01SKoji Sato
2311e7c274f8SRyusuke Konishi ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
23122e0c2c73SRyusuke Konishi blocknr);
231317c76b01SKoji Sato if (ret < 0)
231417c76b01SKoji Sato return ret;
231517c76b01SKoji Sato
231617c76b01SKoji Sato if (buffer_nilfs_node(*bh)) {
231717c76b01SKoji Sato node = (struct nilfs_btree_node *)(*bh)->b_data;
23186d28f7eaSRyusuke Konishi key = nilfs_btree_node_get_key(node, 0);
231917c76b01SKoji Sato } else
2320e7c274f8SRyusuke Konishi key = nilfs_bmap_data_get_key(btree, *bh);
232117c76b01SKoji Sato
232217c76b01SKoji Sato /* on-disk format */
232317c76b01SKoji Sato binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr);
232425b8d7deSRyusuke Konishi binfo->bi_v.bi_blkoff = cpu_to_le64(key);
232517c76b01SKoji Sato
232617c76b01SKoji Sato return 0;
232717c76b01SKoji Sato }
232817c76b01SKoji Sato
nilfs_btree_mark(struct nilfs_bmap * btree,__u64 key,int level)2329e7c274f8SRyusuke Konishi static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
233017c76b01SKoji Sato {
233117c76b01SKoji Sato struct buffer_head *bh;
233217c76b01SKoji Sato struct nilfs_btree_path *path;
233317c76b01SKoji Sato __u64 ptr;
233417c76b01SKoji Sato int ret;
233517c76b01SKoji Sato
23366d28f7eaSRyusuke Konishi path = nilfs_btree_alloc_path();
233717c76b01SKoji Sato if (path == NULL)
233817c76b01SKoji Sato return -ENOMEM;
233917c76b01SKoji Sato
234003bdb5acSRyusuke Konishi ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
234117c76b01SKoji Sato if (ret < 0) {
23421f5abe7eSRyusuke Konishi WARN_ON(ret == -ENOENT);
234317c76b01SKoji Sato goto out;
234417c76b01SKoji Sato }
2345f198dbb9SRyusuke Konishi ret = nilfs_btree_get_block(btree, ptr, &bh);
234617c76b01SKoji Sato if (ret < 0) {
23471f5abe7eSRyusuke Konishi WARN_ON(ret == -ENOENT);
234817c76b01SKoji Sato goto out;
234917c76b01SKoji Sato }
235017c76b01SKoji Sato
235117c76b01SKoji Sato if (!buffer_dirty(bh))
23525fc7b141SRyusuke Konishi mark_buffer_dirty(bh);
2353087d01b4SRyusuke Konishi brelse(bh);
2354e7c274f8SRyusuke Konishi if (!nilfs_bmap_dirty(btree))
2355e7c274f8SRyusuke Konishi nilfs_bmap_set_dirty(btree);
235617c76b01SKoji Sato
235717c76b01SKoji Sato out:
23586d28f7eaSRyusuke Konishi nilfs_btree_free_path(path);
235917c76b01SKoji Sato return ret;
236017c76b01SKoji Sato }
236117c76b01SKoji Sato
236217c76b01SKoji Sato static const struct nilfs_bmap_operations nilfs_btree_ops = {
236317c76b01SKoji Sato .bop_lookup = nilfs_btree_lookup,
2364c3a7abf0SRyusuke Konishi .bop_lookup_contig = nilfs_btree_lookup_contig,
236517c76b01SKoji Sato .bop_insert = nilfs_btree_insert,
236617c76b01SKoji Sato .bop_delete = nilfs_btree_delete,
236717c76b01SKoji Sato .bop_clear = NULL,
236817c76b01SKoji Sato
236917c76b01SKoji Sato .bop_propagate = nilfs_btree_propagate,
237017c76b01SKoji Sato
237117c76b01SKoji Sato .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
237217c76b01SKoji Sato
237317c76b01SKoji Sato .bop_assign = nilfs_btree_assign,
237417c76b01SKoji Sato .bop_mark = nilfs_btree_mark,
237517c76b01SKoji Sato
23765b20384fSRyusuke Konishi .bop_seek_key = nilfs_btree_seek_key,
237717c76b01SKoji Sato .bop_last_key = nilfs_btree_last_key,
23785b20384fSRyusuke Konishi
237917c76b01SKoji Sato .bop_check_insert = NULL,
238017c76b01SKoji Sato .bop_check_delete = nilfs_btree_check_delete,
238117c76b01SKoji Sato .bop_gather_data = nilfs_btree_gather_data,
238217c76b01SKoji Sato };
238317c76b01SKoji Sato
238417c76b01SKoji Sato static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
238517c76b01SKoji Sato .bop_lookup = NULL,
2386c3a7abf0SRyusuke Konishi .bop_lookup_contig = NULL,
238717c76b01SKoji Sato .bop_insert = NULL,
238817c76b01SKoji Sato .bop_delete = NULL,
238917c76b01SKoji Sato .bop_clear = NULL,
239017c76b01SKoji Sato
239117c76b01SKoji Sato .bop_propagate = nilfs_btree_propagate_gc,
239217c76b01SKoji Sato
239317c76b01SKoji Sato .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
239417c76b01SKoji Sato
239517c76b01SKoji Sato .bop_assign = nilfs_btree_assign_gc,
239617c76b01SKoji Sato .bop_mark = NULL,
239717c76b01SKoji Sato
23985b20384fSRyusuke Konishi .bop_seek_key = NULL,
239917c76b01SKoji Sato .bop_last_key = NULL,
24005b20384fSRyusuke Konishi
240117c76b01SKoji Sato .bop_check_insert = NULL,
240217c76b01SKoji Sato .bop_check_delete = NULL,
240317c76b01SKoji Sato .bop_gather_data = NULL,
240417c76b01SKoji Sato };
240517c76b01SKoji Sato
__nilfs_btree_init(struct nilfs_bmap * bmap)2406957ed60bSRyusuke Konishi static void __nilfs_btree_init(struct nilfs_bmap *bmap)
240717c76b01SKoji Sato {
240817c76b01SKoji Sato bmap->b_ops = &nilfs_btree_ops;
24095ad2686eSRyusuke Konishi bmap->b_nchildren_per_block =
24105ad2686eSRyusuke Konishi NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
2411957ed60bSRyusuke Konishi }
2412957ed60bSRyusuke Konishi
nilfs_btree_init(struct nilfs_bmap * bmap)2413957ed60bSRyusuke Konishi int nilfs_btree_init(struct nilfs_bmap *bmap)
2414957ed60bSRyusuke Konishi {
2415957ed60bSRyusuke Konishi int ret = 0;
2416957ed60bSRyusuke Konishi
2417957ed60bSRyusuke Konishi __nilfs_btree_init(bmap);
2418957ed60bSRyusuke Konishi
2419feee880fSRyusuke Konishi if (nilfs_btree_root_broken(nilfs_btree_get_root(bmap), bmap->b_inode))
2420957ed60bSRyusuke Konishi ret = -EIO;
2421e897be17SRyusuke Konishi else
2422e897be17SRyusuke Konishi ret = nilfs_attach_btree_node_cache(
2423e897be17SRyusuke Konishi &NILFS_BMAP_I(bmap)->vfs_inode);
2424e897be17SRyusuke Konishi
2425957ed60bSRyusuke Konishi return ret;
242617c76b01SKoji Sato }
242717c76b01SKoji Sato
nilfs_btree_init_gc(struct nilfs_bmap * bmap)242817c76b01SKoji Sato void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
242917c76b01SKoji Sato {
243017c76b01SKoji Sato bmap->b_ops = &nilfs_btree_ops_gc;
24315ad2686eSRyusuke Konishi bmap->b_nchildren_per_block =
24325ad2686eSRyusuke Konishi NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
243317c76b01SKoji Sato }
2434