aboutsummaryrefslogtreecommitdiffstats
path: root/functest/opnfv_tests/openstack/refstack_client/refstack_client.py
blob: c2a05379d08d6c1bb752a7fad677cda74d1e3675 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#!/usr/bin/env python
# Copyright (c) 2017 Huawei Technologies Co.,Ltd and others.
# matthew.lijun@huawei.com wangwulin@huawei.com
# All rights reserved. This program and the accompanying materials
# are made available under the terms of the Apache License, Version 2.0
# which accompanies this distribution, and is available at
# http://www.apache.org/licenses/LICENSE-2.0

from __future__ import division


import argparse
import logging
import os
import pkg_resources
import re
import sys
import subprocess
import time

from functest.core import testcase
from functest.opnfv_tests.openstack.tempest import conf_utils
from functest.utils.constants import CONST
import functest.utils.functest_utils as ft_utils
from tempest_conf import TempestConf

""" logging configuration """
logger = logging.getLogger(__name__)


class RefstackClient(testcase.OSGCTestCase):

    def __init__(self, **kwargs):
        if "case_name" not in kwargs:
            kwargs["case_name"] = "refstack_defcore"
        super(RefstackClient, self).__init__(**kwargs)
        self.CONF_PATH = pkg_resources.resource_filename(
            'functest',
            'opnfv_tests/openstack/refstack_client/refstack_tempest.conf')
        self.FUNCTEST_TEST = pkg_resources.resource_filename(
            'functest', 'opnfv_tests')
        self.DEFCORE_LIST = 'openstack/refstack_client/defcore.txt'
        self.confpath = os.path.join(self.FUNCTEST_TEST,
                                     self.CONF_PATH)
        self.defcorelist = pkg_resources.resource_filename(
            'functest', 'opnfv_tests/openstack/refstack_client/defcore.txt')
        self.insecure = ''
        if ('https' in CONST.__getattribute__('OS_AUTH_URL') and
                CONST.__getattribute__('OS_INSECURE').lower() == 'true'):
            self.insecure = '-k'

    def run_defcore(self, conf, testlist):
        cmd = ("refstack-client test {0} -c {1} -v --test-list {2}"
               .format(self.insecure, conf, testlist))
        logger.info("Starting Refstack_defcore test case: '%s'." % cmd)
        ft_utils.execute_command(cmd)

    def run_defcore_default(self):
        cmd = ("refstack-client test {0} -c {1} -v --test-list {2}"
               .format(self.insecure, self.confpath, self.defcorelist))
        logger.info("Starting Refstack_defcore test case: '%s'." % cmd)

        header = ("Refstack environment:\n"
                  "  SUT: %s\n  Scenario: %s\n  Node: %s\n  Date: %s\n" %
                  (CONST.__getattribute__('INSTALLER_TYPE'),
                   CONST.__getattribute__('DEPLOY_SCENARIO'),
                   CONST.__getattribute__('NODE_NAME'),
                   time.strftime("%a %b %d %H:%M:%S %Z %Y")))

        f_stdout = open(
            os.path.join(conf_utils.REFSTACK_RESULTS_DIR,
                         "refstack.log"), 'w+')
        f_env = open(os.path.join(conf_utils.REFSTACK_RESULTS_DIR,
                                  "environment.log"), 'w+')
        f_env.write(header)

        p = subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE,
                             stderr=subprocess.STDOUT, bufsize=1)

        with p.stdout:
            for line in iter(p.stdout.readline, b''):
                if 'Tests' in line:
                    break
                if re.search("\} tempest\.", line):
                    logger.info(line.replace('\n', ''))
                f_stdout.write(line)
        p.wait()

        f_stdout.close()
        f_env.close()

    def parse_refstack_result(self):
        try:
            with open(os.path.join(conf_utils.REFSTACK_RESULTS_DIR,
                                   "refstack.log"), 'r') as logfile:
                output = logfile.read()

            for match in re.findall("Ran: (\d+) tests in (\d+\.\d{4}) sec.",
                                    output):
                num_tests = match[0]
                logger.info("Ran: %s tests in %s sec." % (num_tests, match[1]))
            for match in re.findall("(- Passed: )(\d+)", output):
                num_success = match[1]
                logger.info("".join(match))
            for match in re.findall("(- Skipped: )(\d+)", output):
                num_skipped = match[1]
                logger.info("".join(match))
            for match in re.findall("(- Failed: )(\d+)", output):
                num_failures = match[1]
                logger.info("".join(match))
            success_testcases = ""
            for match in re.findall(r"\{0\}(.*?)[. ]*ok", output):
                success_testcases += match + ", "
            failed_testcases = ""
            for match in re.findall(r"\{0\}(.*?)[. ]*FAILED", output):
                failed_testcases += match + ", "
            skipped_testcases = ""
            for match in re.findall(r"\{0\}(.*?)[. ]*SKIPPED:", output):
                skipped_testcases += match + ", "

            num_executed = int(num_tests) - int(num_skipped)

            try:
                self.result = 100 * int(num_success) / int(num_executed)
            except ZeroDivisionError:
                logger.error("No test has been executed")

            self.details = {"tests": int(num_tests),
                            "failures": int(num_failures),
                            "success": success_testcases,
                            "errors": failed_testcases,
                            "skipped": skipped_testcases}
        except Exception:
            self.result = 0

        logger.info("Testcase %s success_rate is %s%%"
                    % (self.case_name, self.result))

    def run(self):
        '''used for functest command line,
           functest testcase run refstack_defcore'''
        self.start_time = time.time()

        if not os.path.exists(conf_utils.REFSTACK_RESULTS_DIR):
            os.makedirs(conf_utils.REFSTACK_RESULTS_DIR)

        try:
            tempestconf = TempestConf()
            tempestconf.generate_tempestconf()
            self.run_defcore_default()
            self.parse_refstack_result()
            res = testcase.TestCase.EX_OK
        except Exception as e:
            logger.error('Error with run: %s', e)
            res = testcase.TestCase.EX_RUN_ERROR

        self.stop_time = time.time()
        return res

    def _prep_test(self):
        '''Check that the config file exists.'''
        if not os.path.isfile(self.confpath):
            logger.error("Conf file not valid: %s" % self.confpath)
        if not os.path.isfile(self.testlist):
            logger.error("testlist file not valid: %s" % self.testlist)

    def main(self, **kwargs):
        '''used for manually running,
           python refstack_client.py -c <tempest_conf_path>
           --testlist <testlist_path>
           can generate a reference refstack_tempest.conf by
           python tempest_conf.py
        '''
        try:
            self.confpath = kwargs['config']
            self.testlist = kwargs['testlist']
        except KeyError as e:
            logger.error("Cannot run refstack client. Please check "
                         "%s", e)
            return self.EX_RUN_ERROR
        try:
            self._prep_test()
            self.run_defcore(self.confpath, self.testlist)
            res = testcase.TestCase.EX_OK
        except Exception as e:
            logger.error('Error with run: %s', e)
            res = testcase.TestCase.EX_RUN_ERROR

        return res


class RefstackClientParser(object):

    def __init__(self):
        self.FUNCTEST_TEST = pkg_resources.resource_filename(
            'functest', 'opnfv_tests')
        self.CONF_PATH = pkg_resources.resource_filename(
            'functest',
            'opnfv_tests/openstack/refstack_client/refstack_tempest.conf')
        self.DEFCORE_LIST = pkg_resources.resource_filename(
            'functest', 'opnfv_tests/openstack/refstack_client/defcore.txt')
        self.confpath = os.path.join(self.FUNCTEST_TEST,
                                     self.CONF_PATH)
        self.defcorelist = os.path.join(self.FUNCTEST_TEST,
                                        self.DEFCORE_LIST)
        self.parser = argparse.ArgumentParser()
        self.parser.add_argument(
            '-c', '--config',
            help='the file path of refstack_tempest.conf',
            default=self.confpath)
        self.parser.add_argument(
            '-t', '--testlist',
            help='Specify the file path or URL of a test list text file. '
                 'This test list will contain specific test cases that '
                 'should be tested.',
            default=self.defcorelist)

    def parse_args(self, argv=[]):
        return vars(self.parser.parse_args(argv))


def main():
    logging.basicConfig()
    refstackclient = RefstackClient()
    parser = RefstackClientParser()
    args = parser.parse_args(sys.argv[1:])
    try:
        result = refstackclient.main(**args)
        if result != testcase.TestCase.EX_OK:
            return result
    except Exception:
        return testcase.TestCase.EX_RUN_ERROR
2 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414
/*
 * btree.c - NILFS B-tree.
 *
 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Written by Koji Sato <koji@osrg.net>.
 */

#include <linux/slab.h>
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/pagevec.h>
#include "nilfs.h"
#include "page.h"
#include "btnode.h"
#include "btree.h"
#include "alloc.h"
#include "dat.h"

static void __nilfs_btree_init(struct nilfs_bmap *bmap);

static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
{
	struct nilfs_btree_path *path;
	int level = NILFS_BTREE_LEVEL_DATA;

	path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
	if (path == NULL)
		goto out;

	for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
		path[level].bp_bh = NULL;
		path[level].bp_sib_bh = NULL;
		path[level].bp_index = 0;
		path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
		path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
		path[level].bp_op = NULL;
	}

out:
	return path;
}

static void nilfs_btree_free_path(struct nilfs_btree_path *path)
{
	int level = NILFS_BTREE_LEVEL_DATA;

	for (; level < NILFS_BTREE_LEVEL_MAX; level++)
		brelse(path[level].bp_bh);

	kmem_cache_free(nilfs_btree_path_cache, path);
}

/*
 * B-tree node operations
 */
static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
				     __u64 ptr, struct buffer_head **bhp)
{
	struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
	struct buffer_head *bh;

	bh = nilfs_btnode_create_block(btnc, ptr);
	if (!bh)
		return -ENOMEM;

	set_buffer_nilfs_volatile(bh);
	*bhp = bh;
	return 0;
}

static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
{
	return node->bn_flags;
}

static void
nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
{
	node->bn_flags = flags;
}

static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
{
	return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
}

static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
{
	return node->bn_level;
}

static void
nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
{
	node->bn_level = level;
}

static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
{
	return le16_to_cpu(node->bn_nchildren);
}

static void
nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
{
	node->bn_nchildren = cpu_to_le16(nchildren);
}

static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
{
	return 1 << btree->b_inode->i_blkbits;
}

static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
{
	return btree->b_nchildren_per_block;
}

static __le64 *
nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
{
	return (__le64 *)((char *)(node + 1) +
			  (nilfs_btree_node_root(node) ?
			   0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
}

static __le64 *
nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
{
	return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
}

static __u64
nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
{
	return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
}

static void
nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
{
	*(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
}

static __u64
nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
			 int ncmax)
{
	return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
}

static void
nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
			 int ncmax)
{
	*(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
}

static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
				  int level, int nchildren, int ncmax,
				  const __u64 *keys, const __u64 *ptrs)
{
	__le64 *dkeys;
	__le64 *dptrs;
	int i;

	nilfs_btree_node_set_flags(node, flags);
	nilfs_btree_node_set_level(node, level);
	nilfs_btree_node_set_nchildren(node, nchildren);

	dkeys = nilfs_btree_node_dkeys(node);
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
	for (i = 0; i < nchildren; i++) {
		dkeys[i] = cpu_to_le64(keys[i]);
		dptrs[i] = cpu_to_le64(ptrs[i]);
	}
}

/* Assume the buffer heads corresponding to left and right are locked. */
static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
				       struct nilfs_btree_node *right,
				       int n, int lncmax, int rncmax)
{
	__le64 *ldkeys, *rdkeys;
	__le64 *ldptrs, *rdptrs;
	int lnchildren, rnchildren;

	ldkeys = nilfs_btree_node_dkeys(left);
	ldptrs = nilfs_btree_node_dptrs(left, lncmax);
	lnchildren = nilfs_btree_node_get_nchildren(left);

	rdkeys = nilfs_btree_node_dkeys(right);
	rdptrs = nilfs_btree_node_dptrs(right, rncmax);
	rnchildren = nilfs_btree_node_get_nchildren(right);

	memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
	memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
	memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
	memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));

	lnchildren += n;
	rnchildren -= n;
	nilfs_btree_node_set_nchildren(left, lnchildren);
	nilfs_btree_node_set_nchildren(right, rnchildren);
}

/* Assume that the buffer heads corresponding to left and right are locked. */
static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
					struct nilfs_btree_node *right,
					int n, int lncmax, int rncmax)
{
	__le64 *ldkeys, *rdkeys;
	__le64 *ldptrs, *rdptrs;
	int lnchildren, rnchildren;

	ldkeys = nilfs_btree_node_dkeys(left);
	ldptrs = nilfs_btree_node_dptrs(left, lncmax);
	lnchildren = nilfs_btree_node_get_nchildren(left);

	rdkeys = nilfs_btree_node_dkeys(right);
	rdptrs = nilfs_btree_node_dptrs(right, rncmax);
	rnchildren = nilfs_btree_node_get_nchildren(right);

	memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
	memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
	memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
	memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));

	lnchildren -= n;
	rnchildren += n;
	nilfs_btree_node_set_nchildren(left, lnchildren);
	nilfs_btree_node_set_nchildren(right, rnchildren);
}

/* Assume that the buffer head corresponding to node is locked. */
static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
				    __u64 key, __u64 ptr, int ncmax)
{
	__le64 *dkeys;
	__le64 *dptrs;
	int nchildren;

	dkeys = nilfs_btree_node_dkeys(node);
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
	nchildren = nilfs_btree_node_get_nchildren(node);
	if (index < nchildren) {
		memmove(dkeys + index + 1, dkeys + index,
			(nchildren - index) * sizeof(*dkeys));
		memmove(dptrs + index + 1, dptrs + index,
			(nchildren - index) * sizeof(*dptrs));
	}
	dkeys[index] = cpu_to_le64(key);
	dptrs[index] = cpu_to_le64(ptr);
	nchildren++;
	nilfs_btree_node_set_nchildren(node, nchildren);
}

/* Assume that the buffer head corresponding to node is locked. */
static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
				    __u64 *keyp, __u64 *ptrp, int ncmax)
{
	__u64 key;
	__u64 ptr;
	__le64 *dkeys;
	__le64 *dptrs;
	int nchildren;

	dkeys = nilfs_btree_node_dkeys(node);
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
	key = le64_to_cpu(dkeys[index]);
	ptr = le64_to_cpu(dptrs[index]);
	nchildren = nilfs_btree_node_get_nchildren(node);
	if (keyp != NULL)
		*keyp = key;
	if (ptrp != NULL)
		*ptrp = ptr;

	if (index < nchildren - 1) {
		memmove(dkeys + index, dkeys + index + 1,
			(nchildren - index - 1) * sizeof(*dkeys));
		memmove(dptrs + index, dptrs + index + 1,
			(nchildren - index - 1) * sizeof(*dptrs));
	}
	nchildren--;
	nilfs_btree_node_set_nchildren(node, nchildren);
}

static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
				   __u64 key, int *indexp)
{
	__u64 nkey;
	int index, low, high, s;

	/* binary search */
	low = 0;
	high = nilfs_btree_node_get_nchildren(node) - 1;
	index = 0;
	s = 0;
	while (low <= high) {
		index = (low + high) / 2;
		nkey = nilfs_btree_node_get_key(node, index);
		if (nkey == key) {
			s = 0;
			goto out;
		} else if (nkey < key) {
			low = index + 1;
			s = -1;
		} else {
			high = index - 1;
			s = 1;
		}
	}

	/* adjust index */
	if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
		if (s > 0 && index > 0)
			index--;
	} else if (s < 0)
		index++;

 out:
	*indexp = index;

	return s == 0;
}

/**
 * nilfs_btree_node_broken - verify consistency of btree node
 * @node: btree node block to be examined
 * @size: node size (in bytes)
 * @blocknr: block number
 *
 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 */
static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
				   size_t size, sector_t blocknr)
{
	int level, flags, nchildren;
	int ret = 0;

	level = nilfs_btree_node_get_level(node);
	flags = nilfs_btree_node_get_flags(node);
	nchildren = nilfs_btree_node_get_nchildren(node);

	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
		     level >= NILFS_BTREE_LEVEL_MAX ||
		     (flags & NILFS_BTREE_NODE_ROOT) ||
		     nchildren < 0 ||
		     nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
		printk(KERN_CRIT "NILFS: bad btree node (blocknr=%llu): "
		       "level = %d, flags = 0x%x, nchildren = %d\n",
		       (unsigned long long)blocknr, level, flags, nchildren);
		ret = 1;
	}
	return ret;
}

/**
 * nilfs_btree_root_broken - verify consistency of btree root node
 * @node: btree root node to be examined
 * @ino: inode number
 *
 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 */
static int nilfs_btree_root_broken(const struct nilfs_btree_node *node,
				   unsigned long ino)
{
	int level, flags, nchildren;
	int ret = 0;

	level = nilfs_btree_node_get_level(node);
	flags = nilfs_btree_node_get_flags(node);
	nchildren = nilfs_btree_node_get_nchildren(node);

	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
		     level >= NILFS_BTREE_LEVEL_MAX ||
		     nchildren < 0 ||
		     nchildren > NILFS_BTREE_ROOT_NCHILDREN_MAX)) {
		pr_crit("NILFS: bad btree root (inode number=%lu): level = %d, flags = 0x%x, nchildren = %d\n",
			ino, level, flags, nchildren);
		ret = 1;
	}
	return ret;
}

int nilfs_btree_broken_node_block(struct buffer_head *bh)
{
	int ret;

	if (buffer_nilfs_checked(bh))
		return 0;

	ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
				       bh->b_size, bh->b_blocknr);
	if (likely(!ret))
		set_buffer_nilfs_checked(bh);
	return ret;
}

static struct nilfs_btree_node *
nilfs_btree_get_root(const struct nilfs_bmap *btree)
{
	return (struct nilfs_btree_node *)btree->b_u.u_data;
}

static struct nilfs_btree_node *
nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
{
	return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
}

static struct nilfs_btree_node *
nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
{
	return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
}

static int nilfs_btree_height(const struct nilfs_bmap *btree)
{
	return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
}

static struct nilfs_btree_node *
nilfs_btree_get_node(const struct nilfs_bmap *btree,
		     const struct nilfs_btree_path *path,
		     int level, int *ncmaxp)
{
	struct nilfs_btree_node *node;

	if (level == nilfs_btree_height(btree) - 1) {
		node = nilfs_btree_get_root(btree);
		*ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
	} else {
		node = nilfs_btree_get_nonroot_node(path, level);
		*ncmaxp = nilfs_btree_nchildren_per_block(btree);
	}
	return node;
}

static int
nilfs_btree_bad_node(struct nilfs_btree_node *node, int level)
{
	if (unlikely(nilfs_btree_node_get_level(node) != level)) {
		dump_stack();
		printk(KERN_CRIT "NILFS: btree level mismatch: %d != %d\n",
		       nilfs_btree_node_get_level(node), level);
		return 1;
	}
	return 0;
}

struct nilfs_btree_readahead_info {
	struct nilfs_btree_node *node;	/* parent node */
	int max_ra_blocks;		/* max nof blocks to read ahead */
	int index;			/* current index on the parent node */
	int ncmax;			/* nof children in the parent node */
};

static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
				   struct buffer_head **bhp,
				   const struct nilfs_btree_readahead_info *ra)
{
	struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
	struct buffer_head *bh, *ra_bh;
	sector_t submit_ptr = 0;
	int ret;

	ret = nilfs_btnode_submit_block(btnc, ptr, 0, READ, &bh, &submit_ptr);
	if (ret) {
		if (ret != -EEXIST)
			return ret;
		goto out_check;
	}

	if (ra) {
		int i, n;
		__u64 ptr2;

		/* read ahead sibling nodes */
		for (n = ra->max_ra_blocks, i = ra->index + 1;
		     n > 0 && i < ra->ncmax; n--, i++) {
			ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);

			ret = nilfs_btnode_submit_block(btnc, ptr2, 0, READA,
							&ra_bh, &submit_ptr);
			if (likely(!ret || ret == -EEXIST))
				brelse(ra_bh);
			else if (ret != -EBUSY)
				break;
			if (!buffer_locked(bh))
				goto out_no_wait;
		}
	}

	wait_on_buffer(bh);

 out_no_wait:
	if (!buffer_uptodate(bh)) {
		brelse(bh);
		return -EIO;
	}

 out_check:
	if (nilfs_btree_broken_node_block(bh)) {
		clear_buffer_uptodate(bh);
		brelse(bh);
		return -EINVAL;
	}

	*bhp = bh;
	return 0;
}

static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
				   struct buffer_head **bhp)
{
	return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
}

static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
				 struct nilfs_btree_path *path,
				 __u64 key, __u64 *ptrp, int minlevel,
				 int readahead)
{
	struct nilfs_btree_node *node;
	struct nilfs_btree_readahead_info p, *ra;
	__u64 ptr;
	int level, index, found, ncmax, ret;

	node = nilfs_btree_get_root(btree);
	level = nilfs_btree_node_get_level(node);
	if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
		return -ENOENT;

	found = nilfs_btree_node_lookup(node, key, &index);
	ptr = nilfs_btree_node_get_ptr(node, index,
				       NILFS_BTREE_ROOT_NCHILDREN_MAX);
	path[level].bp_bh = NULL;
	path[level].bp_index = index;

	ncmax = nilfs_btree_nchildren_per_block(btree);

	while (--level >= minlevel) {
		ra = NULL;
		if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
			p.node = nilfs_btree_get_node(btree, path, level + 1,
						      &p.ncmax);
			p.index = index;
			p.max_ra_blocks = 7;
			ra = &p;
		}
		ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
					      ra);
		if (ret < 0)
			return ret;

		node = nilfs_btree_get_nonroot_node(path, level);
		if (nilfs_btree_bad_node(node, level))
			return -EINVAL;
		if (!found)
			found = nilfs_btree_node_lookup(node, key, &index);
		else
			index = 0;
		if (index < ncmax) {
			ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
		} else {
			WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
			/* insert */
			ptr = NILFS_BMAP_INVALID_PTR;
		}
		path[level].bp_index = index;
	}
	if (!found)
		return -ENOENT;

	if (ptrp != NULL)
		*ptrp = ptr;

	return 0;
}

static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
				      struct nilfs_btree_path *path,
				      __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node;
	__u64 ptr;
	int index, level, ncmax, ret;

	node = nilfs_btree_get_root(btree);
	index = nilfs_btree_node_get_nchildren(node) - 1;
	if (index < 0)
		return -ENOENT;
	level = nilfs_btree_node_get_level(node);
	ptr = nilfs_btree_node_get_ptr(node, index,
				       NILFS_BTREE_ROOT_NCHILDREN_MAX);
	path[level].bp_bh = NULL;
	path[level].bp_index = index;
	ncmax = nilfs_btree_nchildren_per_block(btree);

	for (level--; level > 0; level--) {
		ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
		if (ret < 0)
			return ret;
		node = nilfs_btree_get_nonroot_node(path, level);
		if (nilfs_btree_bad_node(node, level))
			return -EINVAL;
		index = nilfs_btree_node_get_nchildren(node) - 1;
		ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
		path[level].bp_index = index;
	}

	if (keyp != NULL)
		*keyp = nilfs_btree_node_get_key(node, index);
	if (ptrp != NULL)
		*ptrp = ptr;

	return 0;
}

/**
 * nilfs_btree_get_next_key - get next valid key from btree path array
 * @btree: bmap struct of btree
 * @path: array of nilfs_btree_path struct
 * @minlevel: start level
 * @nextkey: place to store the next valid key
 *
 * Return Value: If a next key was found, 0 is returned. Otherwise,
 * -ENOENT is returned.
 */
static int nilfs_btree_get_next_key(const struct nilfs_bmap *btree,
				    const struct nilfs_btree_path *path,
				    int minlevel, __u64 *nextkey)
{
	struct nilfs_btree_node *node;
	int maxlevel = nilfs_btree_height(btree) - 1;
	int index, next_adj, level;

	/* Next index is already set to bp_index for leaf nodes. */
	next_adj = 0;
	for (level = minlevel; level <= maxlevel; level++) {
		if (level == maxlevel)
			node = nilfs_btree_get_root(btree);
		else
			node = nilfs_btree_get_nonroot_node(path, level);

		index = path[level].bp_index + next_adj;
		if (index < nilfs_btree_node_get_nchildren(node)) {
			/* Next key is in this node */
			*nextkey = nilfs_btree_node_get_key(node, index);
			return 0;
		}
		/* For non-leaf nodes, next index is stored at bp_index + 1. */
		next_adj = 1;
	}
	return -ENOENT;
}

static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
			      __u64 key, int level, __u64 *ptrp)
{
	struct nilfs_btree_path *path;
	int ret;

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);

	nilfs_btree_free_path(path);

	return ret;
}

static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
				     __u64 key, __u64 *ptrp, unsigned maxblocks)
{
	struct nilfs_btree_path *path;
	struct nilfs_btree_node *node;
	struct inode *dat = NULL;
	__u64 ptr, ptr2;
	sector_t blocknr;
	int level = NILFS_BTREE_LEVEL_NODE_MIN;
	int ret, cnt, index, maxlevel, ncmax;
	struct nilfs_btree_readahead_info p;

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
	if (ret < 0)
		goto out;

	if (NILFS_BMAP_USE_VBN(btree)) {
		dat = nilfs_bmap_get_dat(btree);
		ret = nilfs_dat_translate(dat, ptr, &blocknr);
		if (ret < 0)
			goto out;
		ptr = blocknr;
	}
	cnt = 1;
	if (cnt == maxblocks)
		goto end;

	maxlevel = nilfs_btree_height(btree) - 1;
	node = nilfs_btree_get_node(btree, path, level, &ncmax);
	index = path[level].bp_index + 1;
	for (;;) {
		while (index < nilfs_btree_node_get_nchildren(node)) {
			if (nilfs_btree_node_get_key(node, index) !=
			    key + cnt)
				goto end;
			ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax);
			if (dat) {
				ret = nilfs_dat_translate(dat, ptr2, &blocknr);
				if (ret < 0)
					goto out;
				ptr2 = blocknr;
			}
			if (ptr2 != ptr + cnt || ++cnt == maxblocks)
				goto end;
			index++;
			continue;
		}
		if (level == maxlevel)
			break;

		/* look-up right sibling node */
		p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
		p.index = path[level + 1].bp_index + 1;
		p.max_ra_blocks = 7;
		if (p.index >= nilfs_btree_node_get_nchildren(p.node) ||
		    nilfs_btree_node_get_key(p.node, p.index) != key + cnt)
			break;
		ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax);
		path[level + 1].bp_index = p.index;

		brelse(path[level].bp_bh);
		path[level].bp_bh = NULL;

		ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
					      &p);
		if (ret < 0)
			goto out;
		node = nilfs_btree_get_nonroot_node(path, level);
		ncmax = nilfs_btree_nchildren_per_block(btree);
		index = 0;
		path[level].bp_index = index;
	}
 end:
	*ptrp = ptr;
	ret = cnt;
 out:
	nilfs_btree_free_path(path);
	return ret;
}

static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
				    struct nilfs_btree_path *path,
				    int level, __u64 key)
{
	if (level < nilfs_btree_height(btree) - 1) {
		do {
			nilfs_btree_node_set_key(
				nilfs_btree_get_nonroot_node(path, level),
				path[level].bp_index, key);
			if (!buffer_dirty(path[level].bp_bh))
				mark_buffer_dirty(path[level].bp_bh);
		} while ((path[level].bp_index == 0) &&
			 (++level < nilfs_btree_height(btree) - 1));
	}

	/* root */
	if (level == nilfs_btree_height(btree) - 1) {
		nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
					 path[level].bp_index, key);
	}
}

static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
				  struct nilfs_btree_path *path,
				  int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node;
	int ncblk;

	if (level < nilfs_btree_height(btree) - 1) {
		node = nilfs_btree_get_nonroot_node(path, level);
		ncblk = nilfs_btree_nchildren_per_block(btree);
		nilfs_btree_node_insert(node, path[level].bp_index,
					*keyp, *ptrp, ncblk);
		if (!buffer_dirty(path[level].bp_bh))
			mark_buffer_dirty(path[level].bp_bh);

		if (path[level].bp_index == 0)
			nilfs_btree_promote_key(btree, path, level + 1,
						nilfs_btree_node_get_key(node,
									 0));
	} else {
		node = nilfs_btree_get_root(btree);
		nilfs_btree_node_insert(node, path[level].bp_index,
					*keyp, *ptrp,
					NILFS_BTREE_ROOT_NCHILDREN_MAX);
	}
}

static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
				   struct nilfs_btree_path *path,
				   int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *left;
	int nchildren, lnchildren, n, move, ncblk;

	node = nilfs_btree_get_nonroot_node(path, level);
	left = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	lnchildren = nilfs_btree_node_get_nchildren(left);
	ncblk = nilfs_btree_nchildren_per_block(btree);
	move = 0;

	n = (nchildren + lnchildren + 1) / 2 - lnchildren;
	if (n > path[level].bp_index) {
		/* move insert point */
		n--;
		move = 1;
	}

	nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);

	if (!buffer_dirty(path[level].bp_bh))
		mark_buffer_dirty(path[level].bp_bh);
	if (!buffer_dirty(path[level].bp_sib_bh))
		mark_buffer_dirty(path[level].bp_sib_bh);

	nilfs_btree_promote_key(btree, path, level + 1,
				nilfs_btree_node_get_key(node, 0));

	if (move) {
		brelse(path[level].bp_bh);
		path[level].bp_bh = path[level].bp_sib_bh;
		path[level].bp_sib_bh = NULL;
		path[level].bp_index += lnchildren;
		path[level + 1].bp_index--;
	} else {
		brelse(path[level].bp_sib_bh);
		path[level].bp_sib_bh = NULL;
		path[level].bp_index -= n;
	}

	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
}

static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
				    struct nilfs_btree_path *path,
				    int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *right;
	int nchildren, rnchildren, n, move, ncblk;

	node = nilfs_btree_get_nonroot_node(path, level);
	right = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	rnchildren = nilfs_btree_node_get_nchildren(right);
	ncblk = nilfs_btree_nchildren_per_block(btree);
	move = 0;

	n = (nchildren + rnchildren + 1) / 2 - rnchildren;
	if (n > nchildren - path[level].bp_index) {
		/* move insert point */
		n--;
		move = 1;
	}

	nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);

	if (!buffer_dirty(path[level].bp_bh))
		mark_buffer_dirty(path[level].bp_bh);
	if (!buffer_dirty(path[level].bp_sib_bh))
		mark_buffer_dirty(path[level].bp_sib_bh);

	path[level + 1].bp_index++;
	nilfs_btree_promote_key(btree, path, level + 1,
				nilfs_btree_node_get_key(right, 0));
	path[level + 1].bp_index--;

	if (move) {
		brelse(path[level].bp_bh);
		path[level].bp_bh = path[level].bp_sib_bh;
		path[level].bp_sib_bh = NULL;
		path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
		path[level + 1].bp_index++;
	} else {
		brelse(path[level].bp_sib_bh);
		path[level].bp_sib_bh = NULL;
	}

	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
}

static void nilfs_btree_split(struct nilfs_bmap *btree,
			      struct nilfs_btree_path *path,
			      int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *right;
	__u64 newkey;
	__u64 newptr;
	int nchildren, n, move, ncblk;

	node = nilfs_btree_get_nonroot_node(path, level);
	right = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	ncblk = nilfs_btree_nchildren_per_block(btree);
	move = 0;

	n = (nchildren + 1) / 2;
	if (n > nchildren - path[level].bp_index) {
		n--;
		move = 1;
	}

	nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);

	if (!buffer_dirty(path[level].bp_bh))
		mark_buffer_dirty(path[level].bp_bh);
	if (!buffer_dirty(path[level].bp_sib_bh))
		mark_buffer_dirty(path[level].bp_sib_bh);

	newkey = nilfs_btree_node_get_key(right, 0);
	newptr = path[level].bp_newreq.bpr_ptr;

	if (move) {
		path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
		nilfs_btree_node_insert(right, path[level].bp_index,
					*keyp, *ptrp, ncblk);

		*keyp = nilfs_btree_node_get_key(right, 0);
		*ptrp = path[level].bp_newreq.bpr_ptr;

		brelse(path[level].bp_bh);
		path[level].bp_bh = path[level].bp_sib_bh;
		path[level].bp_sib_bh = NULL;
	} else {
		nilfs_btree_do_insert(btree, path, level, keyp, ptrp);

		*keyp = nilfs_btree_node_get_key(right, 0);
		*ptrp = path[level].bp_newreq.bpr_ptr;

		brelse(path[level].bp_sib_bh);
		path[level].bp_sib_bh = NULL;
	}

	path[level + 1].bp_index++;
}

static void nilfs_btree_grow(struct nilfs_bmap *btree,
			     struct nilfs_btree_path *path,
			     int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *root, *child;
	int n, ncblk;

	root = nilfs_btree_get_root(btree);
	child = nilfs_btree_get_sib_node(path, level);
	ncblk = nilfs_btree_nchildren_per_block(btree);

	n = nilfs_btree_node_get_nchildren(root);

	nilfs_btree_node_move_right(root, child, n,
				    NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
	nilfs_btree_node_set_level(root, level + 1);

	if (!buffer_dirty(path[level].bp_sib_bh))
		mark_buffer_dirty(path[level].bp_sib_bh);

	path[level].bp_bh = path[level].bp_sib_bh;
	path[level].bp_sib_bh = NULL;

	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);

	*keyp = nilfs_btree_node_get_key(child, 0);
	*ptrp = path[level].bp_newreq.bpr_ptr;
}

static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
				   const struct nilfs_btree_path *path)
{
	struct nilfs_btree_node *node;
	int level, ncmax;

	if (path == NULL)
		return NILFS_BMAP_INVALID_PTR;

	/* left sibling */
	level = NILFS_BTREE_LEVEL_NODE_MIN;
	if (path[level].bp_index > 0) {
		node = nilfs_btree_get_node(btree, path, level, &ncmax);
		return nilfs_btree_node_get_ptr(node,
						path[level].bp_index - 1,
						ncmax);
	}

	/* parent */
	level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
	if (level <= nilfs_btree_height(btree) - 1) {
		node = nilfs_btree_get_node(btree, path, level, &ncmax);
		return nilfs_btree_node_get_ptr(node, path[level].bp_index,
						ncmax);
	}

	return NILFS_BMAP_INVALID_PTR;
}

static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
				       const struct nilfs_btree_path *path,
				       __u64 key)
{
	__u64 ptr;

	ptr = nilfs_bmap_find_target_seq(btree, key);
	if (ptr != NILFS_BMAP_INVALID_PTR)
		/* sequential access */
		return ptr;
	else {
		ptr = nilfs_btree_find_near(btree, path);
		if (ptr != NILFS_BMAP_INVALID_PTR)
			/* near */
			return ptr;
	}
	/* block group */
	return nilfs_bmap_find_target_in_group(btree);
}

static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
				      struct nilfs_btree_path *path,
				      int *levelp, __u64 key, __u64 ptr,
				      struct nilfs_bmap_stats *stats)
{
	struct buffer_head *bh;
	struct nilfs_btree_node *node, *parent, *sib;
	__u64 sibptr;
	int pindex, level, ncmax, ncblk, ret;
	struct inode *dat = NULL;

	stats->bs_nblocks = 0;
	level = NILFS_BTREE_LEVEL_DATA;

	/* allocate a new ptr for data block */
	if (NILFS_BMAP_USE_VBN(btree)) {
		path[level].bp_newreq.bpr_ptr =
			nilfs_btree_find_target_v(btree, path, key);
		dat = nilfs_bmap_get_dat(btree);
	}

	ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
	if (ret < 0)
		goto err_out_data;

	ncblk = nilfs_btree_nchildren_per_block(btree);

	for (level = NILFS_BTREE_LEVEL_NODE_MIN;
	     level < nilfs_btree_height(btree) - 1;
	     level++) {
		node = nilfs_btree_get_nonroot_node(path, level);
		if (nilfs_btree_node_get_nchildren(node) < ncblk) {
			path[level].bp_op = nilfs_btree_do_insert;
			stats->bs_nblocks++;
			goto out;
		}

		parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
		pindex = path[level + 1].bp_index;

		/* left sibling */
		if (pindex > 0) {
			sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
							  ncmax);
			ret = nilfs_btree_get_block(btree, sibptr, &bh);
			if (ret < 0)
				goto err_out_child_node;
			sib = (struct nilfs_btree_node *)bh->b_data;
			if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_carry_left;
				stats->bs_nblocks++;
				goto out;
			} else {
				brelse(bh);
			}
		}

		/* right sibling */
		if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) {
			sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
							  ncmax);
			ret = nilfs_btree_get_block(btree, sibptr, &bh);
			if (ret < 0)
				goto err_out_child_node;
			sib = (struct nilfs_btree_node *)bh->b_data;
			if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_carry_right;
				stats->bs_nblocks++;
				goto out;
			} else {
				brelse(bh);
			}
		}

		/* split */
		path[level].bp_newreq.bpr_ptr =
			path[level - 1].bp_newreq.bpr_ptr + 1;
		ret = nilfs_bmap_prepare_alloc_ptr(btree,
						   &path[level].bp_newreq, dat);
		if (ret < 0)
			goto err_out_child_node;
		ret = nilfs_btree_get_new_block(btree,
						path[level].bp_newreq.bpr_ptr,
						&bh);
		if (ret < 0)
			goto err_out_curr_node;

		stats->bs_nblocks++;

		sib = (struct nilfs_btree_node *)bh->b_data;
		nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);
		path[level].bp_sib_bh = bh;
		path[level].bp_op = nilfs_btree_split;
	}

	/* root */
	node = nilfs_btree_get_root(btree);
	if (nilfs_btree_node_get_nchildren(node) <
	    NILFS_BTREE_ROOT_NCHILDREN_MAX) {
		path[level].bp_op = nilfs_btree_do_insert;
		stats->bs_nblocks++;
		goto out;
	}

	/* grow */
	path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
	ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
	if (ret < 0)
		goto err_out_child_node;
	ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
					&bh);
	if (ret < 0)
		goto err_out_curr_node;

	nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data,
			      0, level, 0, ncblk, NULL, NULL);
	path[level].bp_sib_bh = bh;
	path[level].bp_op = nilfs_btree_grow;

	level++;
	path[level].bp_op = nilfs_btree_do_insert;

	/* a newly-created node block and a data block are added */
	stats->bs_nblocks += 2;

	/* success */
 out:
	*levelp = level;
	return ret;

	/* error */
 err_out_curr_node:
	nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
 err_out_child_node:
	for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
		nilfs_btnode_delete(path[level].bp_sib_bh);
		nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);

	}

	nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
 err_out_data:
	*levelp = level;
	stats->bs_nblocks = 0;
	return ret;
}

static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
				      struct nilfs_btree_path *path,
				      int maxlevel, __u64 key, __u64 ptr)
{
	struct inode *dat = NULL;
	int level;

	set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
	ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
	if (NILFS_BMAP_USE_VBN(btree)) {
		nilfs_bmap_set_target_v(btree, key, ptr);
		dat = nilfs_bmap_get_dat(btree);
	}

	for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
		nilfs_bmap_commit_alloc_ptr(btree,
					    &path[level - 1].bp_newreq, dat);
		path[level].bp_op(btree, path, level, &key, &ptr);
	}

	if (!nilfs_bmap_dirty(btree))
		nilfs_bmap_set_dirty(btree);
}

static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
{
	struct nilfs_btree_path *path;
	struct nilfs_bmap_stats stats;
	int level, ret;

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup(btree, path, key, NULL,
				    NILFS_BTREE_LEVEL_NODE_MIN, 0);
	if (ret != -ENOENT) {
		if (ret == 0)
			ret = -EEXIST;
		goto out;
	}

	ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
	if (ret < 0)
		goto out;
	nilfs_btree_commit_insert(btree, path, level, key, ptr);
	nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);

 out:
	nilfs_btree_free_path(path);
	return ret;
}

static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
				  struct nilfs_btree_path *path,
				  int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node;
	int ncblk;

	if (level < nilfs_btree_height(btree) - 1) {
		node = nilfs_btree_get_nonroot_node(path, level);
		ncblk = nilfs_btree_nchildren_per_block(btree);
		nilfs_btree_node_delete(node, path[level].bp_index,
					keyp, ptrp, ncblk);
		if (!buffer_dirty(path[level].bp_bh))
			mark_buffer_dirty(path[level].bp_bh);
		if (path[level].bp_index == 0)
			nilfs_btree_promote_key(btree, path, level + 1,
				nilfs_btree_node_get_key(node, 0));
	} else {
		node = nilfs_btree_get_root(btree);
		nilfs_btree_node_delete(node, path[level].bp_index,
					keyp, ptrp,
					NILFS_BTREE_ROOT_NCHILDREN_MAX);
	}
}

static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
				    struct nilfs_btree_path *path,
				    int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *left;
	int nchildren, lnchildren, n, ncblk;

	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);

	node = nilfs_btree_get_nonroot_node(path, level);
	left = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	lnchildren = nilfs_btree_node_get_nchildren(left);
	ncblk = nilfs_btree_nchildren_per_block(btree);

	n = (nchildren + lnchildren) / 2 - nchildren;

	nilfs_btree_node_move_right(left, node, n, ncblk, ncblk);

	if (!buffer_dirty(path[level].bp_bh))
		mark_buffer_dirty(path[level].bp_bh);
	if (!buffer_dirty(path[level].bp_sib_bh))
		mark_buffer_dirty(path[level].bp_sib_bh);

	nilfs_btree_promote_key(btree, path, level + 1,
				nilfs_btree_node_get_key(node, 0));

	brelse(path[level].bp_sib_bh);
	path[level].bp_sib_bh = NULL;
	path[level].bp_index += n;
}

static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
				     struct nilfs_btree_path *path,
				     int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *right;
	int nchildren, rnchildren, n, ncblk;

	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);

	node = nilfs_btree_get_nonroot_node(path, level);
	right = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	rnchildren = nilfs_btree_node_get_nchildren(right);
	ncblk = nilfs_btree_nchildren_per_block(btree);

	n = (nchildren + rnchildren) / 2 - nchildren;

	nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);

	if (!buffer_dirty(path[level].bp_bh))
		mark_buffer_dirty(path[level].bp_bh);
	if (!buffer_dirty(path[level].bp_sib_bh))
		mark_buffer_dirty(path[level].bp_sib_bh);

	path[level + 1].bp_index++;
	nilfs_btree_promote_key(btree, path, level + 1,
				nilfs_btree_node_get_key(right, 0));
	path[level + 1].bp_index--;

	brelse(path[level].bp_sib_bh);
	path[level].bp_sib_bh = NULL;
}

static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
				    struct nilfs_btree_path *path,
				    int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *left;
	int n, ncblk;

	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);

	node = nilfs_btree_get_nonroot_node(path, level);
	left = nilfs_btree_get_sib_node(path, level);
	ncblk = nilfs_btree_nchildren_per_block(btree);

	n = nilfs_btree_node_get_nchildren(node);

	nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);

	if (!buffer_dirty(path[level].bp_sib_bh))
		mark_buffer_dirty(path[level].bp_sib_bh);

	nilfs_btnode_delete(path[level].bp_bh);
	path[level].bp_bh = path[level].bp_sib_bh;
	path[level].bp_sib_bh = NULL;
	path[level].bp_index += nilfs_btree_node_get_nchildren(left);
}

static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
				     struct nilfs_btree_path *path,
				     int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *right;
	int n, ncblk;

	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);

	node = nilfs_btree_get_nonroot_node(path, level);
	right = nilfs_btree_get_sib_node(path, level);
	ncblk = nilfs_btree_nchildren_per_block(btree);

	n = nilfs_btree_node_get_nchildren(right);

	nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);

	if (!buffer_dirty(path[level].bp_bh))
		mark_buffer_dirty(path[level].bp_bh);

	nilfs_btnode_delete(path[level].bp_sib_bh);
	path[level].bp_sib_bh = NULL;
	path[level + 1].bp_index++;
}

static void nilfs_btree_shrink(struct nilfs_bmap *btree,
			       struct nilfs_btree_path *path,
			       int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *root, *child;
	int n, ncblk;

	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);

	root = nilfs_btree_get_root(btree);
	child = nilfs_btree_get_nonroot_node(path, level);
	ncblk = nilfs_btree_nchildren_per_block(btree);

	nilfs_btree_node_delete(root, 0, NULL, NULL,
				NILFS_BTREE_ROOT_NCHILDREN_MAX);
	nilfs_btree_node_set_level(root, level);
	n = nilfs_btree_node_get_nchildren(child);
	nilfs_btree_node_move_left(root, child, n,
				   NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);

	nilfs_btnode_delete(path[level].bp_bh);
	path[level].bp_bh = NULL;
}

static void nilfs_btree_nop(struct nilfs_bmap *btree,
			    struct nilfs_btree_path *path,
			    int level, __u64 *keyp, __u64 *ptrp)
{
}

static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
				      struct nilfs_btree_path *path,
				      int *levelp,
				      struct nilfs_bmap_stats *stats,
				      struct inode *dat)
{
	struct buffer_head *bh;
	struct nilfs_btree_node *node, *parent, *sib;
	__u64 sibptr;
	int pindex, dindex, level, ncmin, ncmax, ncblk, ret;

	ret = 0;
	stats->bs_nblocks = 0;
	ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
	ncblk = nilfs_btree_nchildren_per_block(btree);

	for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;
	     level < nilfs_btree_height(btree) - 1;
	     level++) {
		node = nilfs_btree_get_nonroot_node(path, level);
		path[level].bp_oldreq.bpr_ptr =
			nilfs_btree_node_get_ptr(node, dindex, ncblk);
		ret = nilfs_bmap_prepare_end_ptr(btree,
						 &path[level].bp_oldreq, dat);
		if (ret < 0)
			goto err_out_child_node;

		if (nilfs_btree_node_get_nchildren(node) > ncmin) {
			path[level].bp_op = nilfs_btree_do_delete;
			stats->bs_nblocks++;
			goto out;
		}

		parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
		pindex = path[level + 1].bp_index;
		dindex = pindex;

		if (pindex > 0) {
			/* left sibling */
			sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
							  ncmax);
			ret = nilfs_btree_get_block(btree, sibptr, &bh);
			if (ret < 0)
				goto err_out_curr_node;
			sib = (struct nilfs_btree_node *)bh->b_data;
			if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_borrow_left;
				stats->bs_nblocks++;
				goto out;
			} else {
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_concat_left;
				stats->bs_nblocks++;
				/* continue; */
			}
		} else if (pindex <
			   nilfs_btree_node_get_nchildren(parent) - 1) {
			/* right sibling */
			sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
							  ncmax);
			ret = nilfs_btree_get_block(btree, sibptr, &bh);
			if (ret < 0)
				goto err_out_curr_node;
			sib = (struct nilfs_btree_node *)bh->b_data;
			if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_borrow_right;
				stats->bs_nblocks++;
				goto out;
			} else {
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_concat_right;
				stats->bs_nblocks++;
				/*
				 * When merging right sibling node
				 * into the current node, pointer to
				 * the right sibling node must be
				 * terminated instead.  The adjustment
				 * below is required for that.
				 */
				dindex = pindex + 1;
				/* continue; */
			}
		} else {
			/* no siblings */
			/* the only child of the root node */
			WARN_ON(level != nilfs_btree_height(btree) - 2);
			if (nilfs_btree_node_get_nchildren(node) - 1 <=
			    NILFS_BTREE_ROOT_NCHILDREN_MAX) {
				path[level].bp_op = nilfs_btree_shrink;
				stats->bs_nblocks += 2;
				level++;
				path[level].bp_op = nilfs_btree_nop;
				goto shrink_root_child;
			} else {
				path[level].bp_op = nilfs_btree_do_delete;
				stats->bs_nblocks++;
				goto out;
			}
		}
	}

	/* child of the root node is deleted */
	path[level].bp_op = nilfs_btree_do_delete;
	stats->bs_nblocks++;

shrink_root_child:
	node = nilfs_btree_get_root(btree);
	path[level].bp_oldreq.bpr_ptr =
		nilfs_btree_node_get_ptr(node, dindex,
					 NILFS_BTREE_ROOT_NCHILDREN_MAX);

	ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
	if (ret < 0)
		goto err_out_child_node;

	/* success */
 out:
	*levelp = level;
	return ret;

	/* error */
 err_out_curr_node:
	nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
 err_out_child_node:
	for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {
		brelse(path[level].bp_sib_bh);
		nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
	}
	*levelp = level;
	stats->bs_nblocks = 0;
	return ret;
}

static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
				      struct nilfs_btree_path *path,
				      int maxlevel, struct inode *dat)
{
	int level;

	for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
		nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
		path[level].bp_op(btree, path, level, NULL, NULL);
	}

	if (!nilfs_bmap_dirty(btree))
		nilfs_bmap_set_dirty(btree);
}

static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)

{
	struct nilfs_btree_path *path;
	struct nilfs_bmap_stats stats;
	struct inode *dat;
	int level, ret;

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup(btree, path, key, NULL,
				    NILFS_BTREE_LEVEL_NODE_MIN, 0);
	if (ret < 0)
		goto out;


	dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;

	ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
	if (ret < 0)
		goto out;
	nilfs_btree_commit_delete(btree, path, level, dat);
	nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);

out:
	nilfs_btree_free_path(path);
	return ret;
}

static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
				__u64 *keyp)
{
	struct nilfs_btree_path *path;
	const int minlevel = NILFS_BTREE_LEVEL_NODE_MIN;
	int ret;

	path = nilfs_btree_alloc_path();
	if (!path)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
	if (!ret)
		*keyp = start;
	else if (ret == -ENOENT)
		ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);

	nilfs_btree_free_path(path);
	return ret;
}

static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
{
	struct nilfs_btree_path *path;
	int ret;

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);

	nilfs_btree_free_path(path);

	return ret;
}

static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
{
	struct buffer_head *bh;
	struct nilfs_btree_node *root, *node;
	__u64 maxkey, nextmaxkey;
	__u64 ptr;
	int nchildren, ret;

	root = nilfs_btree_get_root(btree);
	switch (nilfs_btree_height(btree)) {
	case 2:
		bh = NULL;
		node = root;
		break;
	case 3:
		nchildren = nilfs_btree_node_get_nchildren(root);
		if (nchildren > 1)
			return 0;
		ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
					       NILFS_BTREE_ROOT_NCHILDREN_MAX);
		ret = nilfs_btree_get_block(btree, ptr, &bh);
		if (ret < 0)
			return ret;
		node = (struct nilfs_btree_node *)bh->b_data;
		break;
	default:
		return 0;
	}

	nchildren = nilfs_btree_node_get_nchildren(node);
	maxkey = nilfs_btree_node_get_key(node, nchildren - 1);
	nextmaxkey = (nchildren > 1) ?
		nilfs_btree_node_get_key(node, nchildren - 2) : 0;
	if (bh != NULL)
		brelse(bh);

	return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
}

static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
				   __u64 *keys, __u64 *ptrs, int nitems)
{
	struct buffer_head *bh;
	struct nilfs_btree_node *node, *root;
	__le64 *dkeys;
	__le64 *dptrs;
	__u64 ptr;
	int nchildren, ncmax, i, ret;

	root = nilfs_btree_get_root(btree);
	switch (nilfs_btree_height(btree)) {
	case 2:
		bh = NULL;
		node = root;
		ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX;
		break;
	case 3:
		nchildren = nilfs_btree_node_get_nchildren(root);
		WARN_ON(nchildren > 1);
		ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
					       NILFS_BTREE_ROOT_NCHILDREN_MAX);
		ret = nilfs_btree_get_block(btree, ptr, &bh);
		if (ret < 0)
			return ret;
		node = (struct nilfs_btree_node *)bh->b_data;
		ncmax = nilfs_btree_nchildren_per_block(btree);
		break;
	default:
		node = NULL;
		return -EINVAL;
	}

	nchildren = nilfs_btree_node_get_nchildren(node);
	if (nchildren < nitems)
		nitems = nchildren;
	dkeys = nilfs_btree_node_dkeys(node);
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
	for (i = 0; i < nitems; i++) {
		keys[i] = le64_to_cpu(dkeys[i]);
		ptrs[i] = le64_to_cpu(dptrs[i]);
	}

	if (bh != NULL)
		brelse(bh);

	return nitems;
}

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)
{
	struct buffer_head *bh;
	struct inode *dat = NULL;
	int ret;

	stats->bs_nblocks = 0;

	/* for data */
	/* cannot find near ptr */
	if (NILFS_BMAP_USE_VBN(btree)) {
		dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
		dat = nilfs_bmap_get_dat(btree);
	}

	ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
	if (ret < 0)
		return ret;

	*bhp = NULL;
	stats->bs_nblocks++;
	if (nreq != NULL) {
		nreq->bpr_ptr = dreq->bpr_ptr + 1;
		ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
		if (ret < 0)
			goto err_out_dreq;

		ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
		if (ret < 0)
			goto err_out_nreq;

		*bhp = bh;
		stats->bs_nblocks++;
	}

	/* success */
	return 0;

	/* error */
 err_out_nreq:
	nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
 err_out_dreq:
	nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
	stats->bs_nblocks = 0;
	return ret;

}

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)
{
	struct nilfs_btree_node *node;
	struct inode *dat;
	__u64 tmpptr;
	int ncblk;

	/* free resources */
	if (btree->b_ops->bop_clear != NULL)
		btree->b_ops->bop_clear(btree);

	/* ptr must be a pointer to a buffer head. */
	set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));

	/* convert and insert */
	dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
	__nilfs_btree_init(btree);
	if (nreq != NULL) {
		nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
		nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);

		/* create child node at level 1 */
		node = (struct nilfs_btree_node *)bh->b_data;
		ncblk = nilfs_btree_nchildren_per_block(btree);
		nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs);
		nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk);
		if (!buffer_dirty(bh))
			mark_buffer_dirty(bh);
		if (!nilfs_bmap_dirty(btree))
			nilfs_bmap_set_dirty(btree);

		brelse(bh);

		/* create root node at level 2 */
		node = nilfs_btree_get_root(btree);
		tmpptr = nreq->bpr_ptr;
		nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1,
				      NILFS_BTREE_ROOT_NCHILDREN_MAX,
				      &keys[0], &tmpptr);
	} else {
		nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);

		/* create root node at level 1 */
		node = nilfs_btree_get_root(btree);
		nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n,
				      NILFS_BTREE_ROOT_NCHILDREN_MAX,
				      keys, ptrs);
		nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr,
					NILFS_BTREE_ROOT_NCHILDREN_MAX);
		if (!nilfs_bmap_dirty(btree))
			nilfs_bmap_set_dirty(btree);
	}

	if (NILFS_BMAP_USE_VBN(btree))
		nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
}

/**
 * nilfs_btree_convert_and_insert -
 * @bmap:
 * @key:
 * @ptr:
 * @keys:
 * @ptrs:
 * @n:
 */
int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
				   __u64 key, __u64 ptr,
				   const __u64 *keys, const __u64 *ptrs, int n)
{
	struct buffer_head *bh;
	union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
	struct nilfs_bmap_stats stats;
	int ret;

	if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
		di = &dreq;
		ni = NULL;
	} else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
			   1 << btree->b_inode->i_blkbits)) {
		di = &dreq;
		ni = &nreq;
	} else {
		di = NULL;
		ni = NULL;
		BUG();
	}

	ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
						     &stats);
	if (ret < 0)
		return ret;
	nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
					      di, ni, bh);
	nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
	return 0;
}

static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
				   struct nilfs_btree_path *path,
				   int level,
				   struct buffer_head *bh)
{
	while ((++level < nilfs_btree_height(btree) - 1) &&
	       !buffer_dirty(path[level].bp_bh))
		mark_buffer_dirty(path[level].bp_bh);

	return 0;
}

static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
					struct nilfs_btree_path *path,
					int level, struct inode *dat)
{
	struct nilfs_btree_node *parent;
	int ncmax, ret;

	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
	path[level].bp_oldreq.bpr_ptr =
		nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
					 ncmax);
	path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
	ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
				       &path[level].bp_newreq.bpr_req);
	if (ret < 0)
		return ret;

	if (buffer_nilfs_node(path[level].bp_bh)) {
		path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
		path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
		path[level].bp_ctxt.bh = path[level].bp_bh;
		ret = nilfs_btnode_prepare_change_key(
			&NILFS_BMAP_I(btree)->i_btnode_cache,
			&path[level].bp_ctxt);
		if (ret < 0) {
			nilfs_dat_abort_update(dat,
					       &path[level].bp_oldreq.bpr_req,
					       &path[level].bp_newreq.bpr_req);
			return ret;
		}
	}

	return 0;
}

static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
					struct nilfs_btree_path *path,
					int level, struct inode *dat)
{
	struct nilfs_btree_node *parent;
	int ncmax;

	nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
				&path[level].bp_newreq.bpr_req,
				btree->b_ptr_type == NILFS_BMAP_PTR_VS);

	if (buffer_nilfs_node(path[level].bp_bh)) {
		nilfs_btnode_commit_change_key(
			&NILFS_BMAP_I(btree)->i_btnode_cache,
			&path[level].bp_ctxt);
		path[level].bp_bh = path[level].bp_ctxt.bh;
	}
	set_buffer_nilfs_volatile(path[level].bp_bh);

	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
	nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
				 path[level].bp_newreq.bpr_ptr, ncmax);
}

static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
				       struct nilfs_btree_path *path,
				       int level, struct inode *dat)
{
	nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
			       &path[level].bp_newreq.bpr_req);
	if (buffer_nilfs_node(path[level].bp_bh))
		nilfs_btnode_abort_change_key(
			&NILFS_BMAP_I(btree)->i_btnode_cache,
			&path[level].bp_ctxt);
}

static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
					   struct nilfs_btree_path *path,
					   int minlevel, int *maxlevelp,
					   struct inode *dat)
{
	int level, ret;

	level = minlevel;
	if (!buffer_nilfs_volatile(path[level].bp_bh)) {
		ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
		if (ret < 0)
			return ret;
	}
	while ((++level < nilfs_btree_height(btree) - 1) &&
	       !buffer_dirty(path[level].bp_bh)) {

		WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
		ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
		if (ret < 0)
			goto out;
	}

	/* success */
	*maxlevelp = level - 1;
	return 0;

	/* error */
 out:
	while (--level > minlevel)
		nilfs_btree_abort_update_v(btree, path, level, dat);
	if (!buffer_nilfs_volatile(path[level].bp_bh))
		nilfs_btree_abort_update_v(btree, path, level, dat);
	return ret;
}

static void 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)
{
	int level;

	if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
		nilfs_btree_commit_update_v(btree, path, minlevel, dat);

	for (level = minlevel + 1; level <= maxlevel; level++)
		nilfs_btree_commit_update_v(btree, path, level, dat);
}

static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
				   struct nilfs_btree_path *path,
				   int level, struct buffer_head *bh)
{
	int maxlevel = 0, ret;
	struct nilfs_btree_node *parent;
	struct inode *dat = nilfs_bmap_get_dat(btree);
	__u64 ptr;
	int ncmax;

	get_bh(bh);
	path[level].bp_bh = bh;
	ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
					      dat);
	if (ret < 0)
		goto out;

	if (buffer_nilfs_volatile(path[level].bp_bh)) {
		parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
		ptr = nilfs_btree_node_get_ptr(parent,
					       path[level + 1].bp_index,
					       ncmax);
		ret = nilfs_dat_mark_dirty(dat, ptr);
		if (ret < 0)
			goto out;
	}

	nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);

 out:
	brelse(path[level].bp_bh);
	path[level].bp_bh = NULL;
	return ret;
}

static int nilfs_btree_propagate(struct nilfs_bmap *btree,
				 struct buffer_head *bh)
{
	struct nilfs_btree_path *path;
	struct nilfs_btree_node *node;
	__u64 key;
	int level, ret;

	WARN_ON(!buffer_dirty(bh));

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	if (buffer_nilfs_node(bh)) {
		node = (struct nilfs_btree_node *)bh->b_data;
		key = nilfs_btree_node_get_key(node, 0);
		level = nilfs_btree_node_get_level(node);
	} else {
		key = nilfs_bmap_data_get_key(btree, bh);
		level = NILFS_BTREE_LEVEL_DATA;
	}

	ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
	if (ret < 0) {
		if (unlikely(ret == -ENOENT))
			printk(KERN_CRIT "%s: key = %llu, level == %d\n",
			       __func__, (unsigned long long)key, level);
		goto out;
	}

	ret = NILFS_BMAP_USE_VBN(btree) ?
		nilfs_btree_propagate_v(btree, path, level, bh) :
		nilfs_btree_propagate_p(btree, path, level, bh);

 out:
	nilfs_btree_free_path(path);

	return ret;
}

static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
				    struct buffer_head *bh)
{
	return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
}

static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
					 struct list_head *lists,
					 struct buffer_head *bh)
{
	struct list_head *head;
	struct buffer_head *cbh;
	struct nilfs_btree_node *node, *cnode;
	__u64 key, ckey;
	int level;

	get_bh(bh);
	node = (struct nilfs_btree_node *)bh->b_data;
	key = nilfs_btree_node_get_key(node, 0);
	level = nilfs_btree_node_get_level(node);
	if (level < NILFS_BTREE_LEVEL_NODE_MIN ||
	    level >= NILFS_BTREE_LEVEL_MAX) {
		dump_stack();
		printk(KERN_WARNING
		       "%s: invalid btree level: %d (key=%llu, ino=%lu, "
		       "blocknr=%llu)\n",
		       __func__, level, (unsigned long long)key,
		       NILFS_BMAP_I(btree)->vfs_inode.i_ino,
		       (unsigned long long)bh->b_blocknr);
		return;
	}

	list_for_each(head, &lists[level]) {
		cbh = list_entry(head, struct buffer_head, b_assoc_buffers);
		cnode = (struct nilfs_btree_node *)cbh->b_data;
		ckey = nilfs_btree_node_get_key(cnode, 0);
		if (key < ckey)
			break;
	}
	list_add_tail(&bh->b_assoc_buffers, head);
}

static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
					     struct list_head *listp)
{
	struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache;
	struct list_head lists[NILFS_BTREE_LEVEL_MAX];
	struct pagevec pvec;
	struct buffer_head *bh, *head;
	pgoff_t index = 0;
	int level, i;

	for (level = NILFS_BTREE_LEVEL_NODE_MIN;
	     level < NILFS_BTREE_LEVEL_MAX;
	     level++)
		INIT_LIST_HEAD(&lists[level]);

	pagevec_init(&pvec, 0);

	while (pagevec_lookup_tag(&pvec, btcache, &index, PAGECACHE_TAG_DIRTY,
				  PAGEVEC_SIZE)) {
		for (i = 0; i < pagevec_count(&pvec); i++) {
			bh = head = page_buffers(pvec.pages[i]);
			do {
				if (buffer_dirty(bh))
					nilfs_btree_add_dirty_buffer(btree,
								     lists, bh);
			} while ((bh = bh->b_this_page) != head);
		}
		pagevec_release(&pvec);
		cond_resched();
	}

	for (level = NILFS_BTREE_LEVEL_NODE_MIN;
	     level < NILFS_BTREE_LEVEL_MAX;
	     level++)
		list_splice_tail(&lists[level], listp);
}

static int 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)
{
	struct nilfs_btree_node *parent;
	__u64 key;
	__u64 ptr;
	int ncmax, ret;

	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
	ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
				       ncmax);
	if (buffer_nilfs_node(*bh)) {
		path[level].bp_ctxt.oldkey = ptr;
		path[level].bp_ctxt.newkey = blocknr;
		path[level].bp_ctxt.bh = *bh;
		ret = nilfs_btnode_prepare_change_key(
			&NILFS_BMAP_I(btree)->i_btnode_cache,
			&path[level].bp_ctxt);
		if (ret < 0)
			return ret;
		nilfs_btnode_commit_change_key(
			&NILFS_BMAP_I(btree)->i_btnode_cache,
			&path[level].bp_ctxt);
		*bh = path[level].bp_ctxt.bh;
	}

	nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
				 ncmax);

	key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
	/* on-disk format */
	binfo->bi_dat.bi_blkoff = cpu_to_le64(key);
	binfo->bi_dat.bi_level = level;

	return 0;
}

static int 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)
{
	struct nilfs_btree_node *parent;
	struct inode *dat = nilfs_bmap_get_dat(btree);
	__u64 key;
	__u64 ptr;
	union nilfs_bmap_ptr_req req;
	int ncmax, ret;

	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
	ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
				       ncmax);
	req.bpr_ptr = ptr;
	ret = nilfs_dat_prepare_start(dat, &req.bpr_req);
	if (ret < 0)
		return ret;
	nilfs_dat_commit_start(dat, &req.bpr_req, blocknr);

	key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
	/* on-disk format */
	binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr);
	binfo->bi_v.bi_blkoff = cpu_to_le64(key);

	return 0;
}

static int nilfs_btree_assign(struct nilfs_bmap *btree,
			      struct buffer_head **bh,
			      sector_t blocknr,
			      union nilfs_binfo *binfo)
{
	struct nilfs_btree_path *path;
	struct nilfs_btree_node *node;
	__u64 key;
	int level, ret;

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	if (buffer_nilfs_node(*bh)) {
		node = (struct nilfs_btree_node *)(*bh)->b_data;
		key = nilfs_btree_node_get_key(node, 0);
		level = nilfs_btree_node_get_level(node);
	} else {
		key = nilfs_bmap_data_get_key(btree, *bh);
		level = NILFS_BTREE_LEVEL_DATA;
	}

	ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
	if (ret < 0) {
		WARN_ON(ret == -ENOENT);
		goto out;
	}

	ret = NILFS_BMAP_USE_VBN(btree) ?
		nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
		nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);

 out:
	nilfs_btree_free_path(path);

	return ret;
}

static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
				 struct buffer_head **bh,
				 sector_t blocknr,
				 union nilfs_binfo *binfo)
{
	struct nilfs_btree_node *node;
	__u64 key;
	int ret;

	ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
			     blocknr);
	if (ret < 0)
		return ret;

	if (buffer_nilfs_node(*bh)) {
		node = (struct nilfs_btree_node *)(*bh)->b_data;
		key = nilfs_btree_node_get_key(node, 0);
	} else
		key = nilfs_bmap_data_get_key(btree, *bh);

	/* on-disk format */
	binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr);
	binfo->bi_v.bi_blkoff = cpu_to_le64(key);

	return 0;
}

static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
{
	struct buffer_head *bh;
	struct nilfs_btree_path *path;
	__u64 ptr;
	int ret;

	path = nilfs_btree_alloc_path();
	if (path == NULL)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
	if (ret < 0) {
		WARN_ON(ret == -ENOENT);
		goto out;
	}
	ret = nilfs_btree_get_block(btree, ptr, &bh);
	if (ret < 0) {
		WARN_ON(ret == -ENOENT);
		goto out;
	}

	if (!buffer_dirty(bh))
		mark_buffer_dirty(bh);
	brelse(bh);
	if (!nilfs_bmap_dirty(btree))
		nilfs_bmap_set_dirty(btree);

 out:
	nilfs_btree_free_path(path);
	return ret;
}

static const struct nilfs_bmap_operations nilfs_btree_ops = {
	.bop_lookup		=	nilfs_btree_lookup,
	.bop_lookup_contig	=	nilfs_btree_lookup_contig,
	.bop_insert		=	nilfs_btree_insert,
	.bop_delete		=	nilfs_btree_delete,
	.bop_clear		=	NULL,

	.bop_propagate		=	nilfs_btree_propagate,

	.bop_lookup_dirty_buffers =	nilfs_btree_lookup_dirty_buffers,

	.bop_assign		=	nilfs_btree_assign,
	.bop_mark		=	nilfs_btree_mark,

	.bop_seek_key		=	nilfs_btree_seek_key,
	.bop_last_key		=	nilfs_btree_last_key,

	.bop_check_insert	=	NULL,
	.bop_check_delete	=	nilfs_btree_check_delete,
	.bop_gather_data	=	nilfs_btree_gather_data,
};

static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
	.bop_lookup		=	NULL,
	.bop_lookup_contig	=	NULL,
	.bop_insert		=	NULL,
	.bop_delete		=	NULL,
	.bop_clear		=	NULL,

	.bop_propagate		=	nilfs_btree_propagate_gc,

	.bop_lookup_dirty_buffers =	nilfs_btree_lookup_dirty_buffers,

	.bop_assign		=	nilfs_btree_assign_gc,
	.bop_mark		=	NULL,

	.bop_seek_key		=	NULL,
	.bop_last_key		=	NULL,

	.bop_check_insert	=	NULL,
	.bop_check_delete	=	NULL,
	.bop_gather_data	=	NULL,
};

static void __nilfs_btree_init(struct nilfs_bmap *bmap)
{
	bmap->b_ops = &nilfs_btree_ops;
	bmap->b_nchildren_per_block =
		NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
}

int nilfs_btree_init(struct nilfs_bmap *bmap)
{
	int ret = 0;

	__nilfs_btree_init(bmap);

	if (nilfs_btree_root_broken(nilfs_btree_get_root(bmap),
				    bmap->b_inode->i_ino))
		ret = -EIO;
	return ret;
}

void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
{
	bmap->b_ops = &nilfs_btree_ops_gc;
	bmap->b_nchildren_per_block =
		NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
}