blob: 919fd5bb14a842e94b80ae8d839cac1918bb1cc2 [file] [log] [blame]
Koji Sato17c76b02009-04-06 19:01:24 -07001/*
2 * btree.c - NILFS B-tree.
3 *
4 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 *
20 * Written by Koji Sato <koji@osrg.net>.
21 */
22
23#include <linux/slab.h>
24#include <linux/string.h>
25#include <linux/errno.h>
26#include <linux/pagevec.h>
27#include "nilfs.h"
28#include "page.h"
29#include "btnode.h"
30#include "btree.h"
31#include "alloc.h"
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +090032#include "dat.h"
Koji Sato17c76b02009-04-06 19:01:24 -070033
Ryusuke Konishi957ed602015-02-27 15:51:56 -080034static void __nilfs_btree_init(struct nilfs_bmap *bmap);
35
Li Hongf9054402010-04-02 17:36:34 +080036static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
Koji Sato17c76b02009-04-06 19:01:24 -070037{
Li Hongf9054402010-04-02 17:36:34 +080038 struct nilfs_btree_path *path;
39 int level = NILFS_BTREE_LEVEL_DATA;
Koji Sato17c76b02009-04-06 19:01:24 -070040
Li Hongf9054402010-04-02 17:36:34 +080041 path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
42 if (path == NULL)
43 goto out;
Koji Sato17c76b02009-04-06 19:01:24 -070044
Li Hongf9054402010-04-02 17:36:34 +080045 for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
Koji Sato17c76b02009-04-06 19:01:24 -070046 path[level].bp_bh = NULL;
47 path[level].bp_sib_bh = NULL;
48 path[level].bp_index = 0;
49 path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
50 path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
51 path[level].bp_op = NULL;
52 }
Li Hongf9054402010-04-02 17:36:34 +080053
54out:
55 return path;
56}
57
Li Hong73bb4882010-04-02 18:35:00 +080058static void nilfs_btree_free_path(struct nilfs_btree_path *path)
Li Hongf9054402010-04-02 17:36:34 +080059{
Li Hong73bb4882010-04-02 18:35:00 +080060 int level = NILFS_BTREE_LEVEL_DATA;
Koji Sato17c76b02009-04-06 19:01:24 -070061
Li Hong73bb4882010-04-02 18:35:00 +080062 for (; level < NILFS_BTREE_LEVEL_MAX; level++)
Ryusuke Konishi32189292009-08-15 01:54:59 +090063 brelse(path[level].bp_bh);
Li Hong73bb4882010-04-02 18:35:00 +080064
65 kmem_cache_free(nilfs_btree_path_cache, path);
Koji Sato17c76b02009-04-06 19:01:24 -070066}
67
Koji Sato17c76b02009-04-06 19:01:24 -070068/*
69 * B-tree node operations
70 */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +090071static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
Ryusuke Konishif198dbb2009-05-22 01:07:13 +090072 __u64 ptr, struct buffer_head **bhp)
73{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +090074 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
Ryusuke Konishi45f49102009-11-13 16:25:19 +090075 struct buffer_head *bh;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +090076
Ryusuke Konishi45f49102009-11-13 16:25:19 +090077 bh = nilfs_btnode_create_block(btnc, ptr);
78 if (!bh)
79 return -ENOMEM;
80
81 set_buffer_nilfs_volatile(bh);
82 *bhp = bh;
83 return 0;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +090084}
Koji Sato17c76b02009-04-06 19:01:24 -070085
Ryusuke Konishi7c397a82010-07-13 23:33:55 +090086static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -070087{
88 return node->bn_flags;
89}
90
Ryusuke Konishi7c397a82010-07-13 23:33:55 +090091static void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +090092nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
Koji Sato17c76b02009-04-06 19:01:24 -070093{
94 node->bn_flags = flags;
95}
96
Ryusuke Konishi7c397a82010-07-13 23:33:55 +090097static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -070098{
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +090099 return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
Koji Sato17c76b02009-04-06 19:01:24 -0700100}
101
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900102static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700103{
104 return node->bn_level;
105}
106
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900107static void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900108nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
Koji Sato17c76b02009-04-06 19:01:24 -0700109{
110 node->bn_level = level;
111}
112
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900113static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700114{
115 return le16_to_cpu(node->bn_nchildren);
116}
117
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900118static void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900119nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
Koji Sato17c76b02009-04-06 19:01:24 -0700120{
121 node->bn_nchildren = cpu_to_le16(nchildren);
122}
123
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900124static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700125{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900126 return 1 << btree->b_inode->i_blkbits;
Koji Sato17c76b02009-04-06 19:01:24 -0700127}
128
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900129static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700130{
Ryusuke Konishi5ad2686e92010-07-13 23:33:54 +0900131 return btree->b_nchildren_per_block;
Koji Sato17c76b02009-04-06 19:01:24 -0700132}
133
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900134static __le64 *
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900135nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700136{
137 return (__le64 *)((char *)(node + 1) +
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900138 (nilfs_btree_node_root(node) ?
Koji Sato17c76b02009-04-06 19:01:24 -0700139 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
140}
141
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900142static __le64 *
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900143nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
Koji Sato17c76b02009-04-06 19:01:24 -0700144{
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900145 return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -0700146}
147
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900148static __u64
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900149nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
Koji Sato17c76b02009-04-06 19:01:24 -0700150{
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900151 return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
Koji Sato17c76b02009-04-06 19:01:24 -0700152}
153
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900154static void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900155nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
Koji Sato17c76b02009-04-06 19:01:24 -0700156{
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900157 *(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -0700158}
159
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900160static __u64
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900161nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
162 int ncmax)
Koji Sato17c76b02009-04-06 19:01:24 -0700163{
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900164 return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
Koji Sato17c76b02009-04-06 19:01:24 -0700165}
166
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900167static void
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900168nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
169 int ncmax)
Koji Sato17c76b02009-04-06 19:01:24 -0700170{
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900171 *(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
Koji Sato17c76b02009-04-06 19:01:24 -0700172}
173
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900174static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
175 int level, int nchildren, int ncmax,
Koji Sato17c76b02009-04-06 19:01:24 -0700176 const __u64 *keys, const __u64 *ptrs)
177{
178 __le64 *dkeys;
179 __le64 *dptrs;
180 int i;
181
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900182 nilfs_btree_node_set_flags(node, flags);
183 nilfs_btree_node_set_level(node, level);
184 nilfs_btree_node_set_nchildren(node, nchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700185
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900186 dkeys = nilfs_btree_node_dkeys(node);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900187 dptrs = nilfs_btree_node_dptrs(node, ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -0700188 for (i = 0; i < nchildren; i++) {
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900189 dkeys[i] = cpu_to_le64(keys[i]);
190 dptrs[i] = cpu_to_le64(ptrs[i]);
Koji Sato17c76b02009-04-06 19:01:24 -0700191 }
192}
193
194/* Assume the buffer heads corresponding to left and right are locked. */
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900195static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
Koji Sato17c76b02009-04-06 19:01:24 -0700196 struct nilfs_btree_node *right,
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900197 int n, int lncmax, int rncmax)
Koji Sato17c76b02009-04-06 19:01:24 -0700198{
199 __le64 *ldkeys, *rdkeys;
200 __le64 *ldptrs, *rdptrs;
201 int lnchildren, rnchildren;
202
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900203 ldkeys = nilfs_btree_node_dkeys(left);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900204 ldptrs = nilfs_btree_node_dptrs(left, lncmax);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900205 lnchildren = nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -0700206
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900207 rdkeys = nilfs_btree_node_dkeys(right);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900208 rdptrs = nilfs_btree_node_dptrs(right, rncmax);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900209 rnchildren = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -0700210
211 memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
212 memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
213 memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
214 memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));
215
216 lnchildren += n;
217 rnchildren -= n;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900218 nilfs_btree_node_set_nchildren(left, lnchildren);
219 nilfs_btree_node_set_nchildren(right, rnchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700220}
221
222/* Assume that the buffer heads corresponding to left and right are locked. */
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900223static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
Koji Sato17c76b02009-04-06 19:01:24 -0700224 struct nilfs_btree_node *right,
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900225 int n, int lncmax, int rncmax)
Koji Sato17c76b02009-04-06 19:01:24 -0700226{
227 __le64 *ldkeys, *rdkeys;
228 __le64 *ldptrs, *rdptrs;
229 int lnchildren, rnchildren;
230
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900231 ldkeys = nilfs_btree_node_dkeys(left);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900232 ldptrs = nilfs_btree_node_dptrs(left, lncmax);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900233 lnchildren = nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -0700234
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900235 rdkeys = nilfs_btree_node_dkeys(right);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900236 rdptrs = nilfs_btree_node_dptrs(right, rncmax);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900237 rnchildren = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -0700238
239 memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
240 memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
241 memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
242 memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));
243
244 lnchildren -= n;
245 rnchildren += n;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900246 nilfs_btree_node_set_nchildren(left, lnchildren);
247 nilfs_btree_node_set_nchildren(right, rnchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700248}
249
250/* Assume that the buffer head corresponding to node is locked. */
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900251static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
252 __u64 key, __u64 ptr, int ncmax)
Koji Sato17c76b02009-04-06 19:01:24 -0700253{
254 __le64 *dkeys;
255 __le64 *dptrs;
256 int nchildren;
257
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900258 dkeys = nilfs_btree_node_dkeys(node);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900259 dptrs = nilfs_btree_node_dptrs(node, ncmax);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900260 nchildren = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700261 if (index < nchildren) {
262 memmove(dkeys + index + 1, dkeys + index,
263 (nchildren - index) * sizeof(*dkeys));
264 memmove(dptrs + index + 1, dptrs + index,
265 (nchildren - index) * sizeof(*dptrs));
266 }
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900267 dkeys[index] = cpu_to_le64(key);
268 dptrs[index] = cpu_to_le64(ptr);
Koji Sato17c76b02009-04-06 19:01:24 -0700269 nchildren++;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900270 nilfs_btree_node_set_nchildren(node, nchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700271}
272
273/* Assume that the buffer head corresponding to node is locked. */
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900274static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
275 __u64 *keyp, __u64 *ptrp, int ncmax)
Koji Sato17c76b02009-04-06 19:01:24 -0700276{
277 __u64 key;
278 __u64 ptr;
279 __le64 *dkeys;
280 __le64 *dptrs;
281 int nchildren;
282
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900283 dkeys = nilfs_btree_node_dkeys(node);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900284 dptrs = nilfs_btree_node_dptrs(node, ncmax);
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900285 key = le64_to_cpu(dkeys[index]);
286 ptr = le64_to_cpu(dptrs[index]);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900287 nchildren = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700288 if (keyp != NULL)
289 *keyp = key;
290 if (ptrp != NULL)
291 *ptrp = ptr;
292
293 if (index < nchildren - 1) {
294 memmove(dkeys + index, dkeys + index + 1,
295 (nchildren - index - 1) * sizeof(*dkeys));
296 memmove(dptrs + index, dptrs + index + 1,
297 (nchildren - index - 1) * sizeof(*dptrs));
298 }
299 nchildren--;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900300 nilfs_btree_node_set_nchildren(node, nchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700301}
302
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900303static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
Koji Sato17c76b02009-04-06 19:01:24 -0700304 __u64 key, int *indexp)
305{
306 __u64 nkey;
307 int index, low, high, s;
308
309 /* binary search */
310 low = 0;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900311 high = nilfs_btree_node_get_nchildren(node) - 1;
Koji Sato17c76b02009-04-06 19:01:24 -0700312 index = 0;
313 s = 0;
314 while (low <= high) {
315 index = (low + high) / 2;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900316 nkey = nilfs_btree_node_get_key(node, index);
Koji Sato17c76b02009-04-06 19:01:24 -0700317 if (nkey == key) {
318 s = 0;
319 goto out;
320 } else if (nkey < key) {
321 low = index + 1;
322 s = -1;
323 } else {
324 high = index - 1;
325 s = 1;
326 }
327 }
328
329 /* adjust index */
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900330 if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
331 if (s > 0 && index > 0)
Koji Sato17c76b02009-04-06 19:01:24 -0700332 index--;
333 } else if (s < 0)
334 index++;
335
336 out:
Koji Sato17c76b02009-04-06 19:01:24 -0700337 *indexp = index;
338
339 return s == 0;
340}
341
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +0900342/**
343 * nilfs_btree_node_broken - verify consistency of btree node
344 * @node: btree node block to be examined
345 * @size: node size (in bytes)
346 * @blocknr: block number
347 *
348 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
349 */
350static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
351 size_t size, sector_t blocknr)
352{
353 int level, flags, nchildren;
354 int ret = 0;
355
356 level = nilfs_btree_node_get_level(node);
357 flags = nilfs_btree_node_get_flags(node);
358 nchildren = nilfs_btree_node_get_nchildren(node);
359
360 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
361 level >= NILFS_BTREE_LEVEL_MAX ||
362 (flags & NILFS_BTREE_NODE_ROOT) ||
363 nchildren < 0 ||
364 nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
365 printk(KERN_CRIT "NILFS: bad btree node (blocknr=%llu): "
366 "level = %d, flags = 0x%x, nchildren = %d\n",
367 (unsigned long long)blocknr, level, flags, nchildren);
368 ret = 1;
369 }
370 return ret;
371}
372
Ryusuke Konishi957ed602015-02-27 15:51:56 -0800373/**
374 * nilfs_btree_root_broken - verify consistency of btree root node
375 * @node: btree root node to be examined
376 * @ino: inode number
377 *
378 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
379 */
380static int nilfs_btree_root_broken(const struct nilfs_btree_node *node,
381 unsigned long ino)
382{
383 int level, flags, nchildren;
384 int ret = 0;
385
386 level = nilfs_btree_node_get_level(node);
387 flags = nilfs_btree_node_get_flags(node);
388 nchildren = nilfs_btree_node_get_nchildren(node);
389
390 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
Ryusuke Konishid8fd1502015-05-05 16:24:00 -0700391 level >= NILFS_BTREE_LEVEL_MAX ||
Ryusuke Konishi957ed602015-02-27 15:51:56 -0800392 nchildren < 0 ||
393 nchildren > NILFS_BTREE_ROOT_NCHILDREN_MAX)) {
394 pr_crit("NILFS: bad btree root (inode number=%lu): level = %d, flags = 0x%x, nchildren = %d\n",
395 ino, level, flags, nchildren);
396 ret = 1;
397 }
398 return ret;
399}
400
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +0900401int nilfs_btree_broken_node_block(struct buffer_head *bh)
402{
Ryusuke Konishi4e13e662010-07-18 10:42:25 +0900403 int ret;
404
405 if (buffer_nilfs_checked(bh))
406 return 0;
407
408 ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +0900409 bh->b_size, bh->b_blocknr);
Ryusuke Konishi4e13e662010-07-18 10:42:25 +0900410 if (likely(!ret))
411 set_buffer_nilfs_checked(bh);
412 return ret;
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +0900413}
414
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900415static struct nilfs_btree_node *
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900416nilfs_btree_get_root(const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700417{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900418 return (struct nilfs_btree_node *)btree->b_u.u_data;
Koji Sato17c76b02009-04-06 19:01:24 -0700419}
420
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900421static struct nilfs_btree_node *
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900422nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
Koji Sato17c76b02009-04-06 19:01:24 -0700423{
424 return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
425}
426
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900427static struct nilfs_btree_node *
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900428nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
Koji Sato17c76b02009-04-06 19:01:24 -0700429{
430 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
431}
432
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900433static int nilfs_btree_height(const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700434{
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900435 return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
Koji Sato17c76b02009-04-06 19:01:24 -0700436}
437
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900438static struct nilfs_btree_node *
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900439nilfs_btree_get_node(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700440 const struct nilfs_btree_path *path,
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900441 int level, int *ncmaxp)
Koji Sato17c76b02009-04-06 19:01:24 -0700442{
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900443 struct nilfs_btree_node *node;
444
445 if (level == nilfs_btree_height(btree) - 1) {
446 node = nilfs_btree_get_root(btree);
447 *ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
448 } else {
449 node = nilfs_btree_get_nonroot_node(path, level);
450 *ncmaxp = nilfs_btree_nchildren_per_block(btree);
451 }
452 return node;
Koji Sato17c76b02009-04-06 19:01:24 -0700453}
454
Ryusuke Konishi7c397a82010-07-13 23:33:55 +0900455static int
Ryusuke Konishi9b945d52009-10-10 22:58:10 +0900456nilfs_btree_bad_node(struct nilfs_btree_node *node, int level)
457{
458 if (unlikely(nilfs_btree_node_get_level(node) != level)) {
459 dump_stack();
460 printk(KERN_CRIT "NILFS: btree level mismatch: %d != %d\n",
461 nilfs_btree_node_get_level(node), level);
462 return 1;
463 }
464 return 0;
465}
466
Ryusuke Konishi464ece82010-07-18 10:42:24 +0900467struct nilfs_btree_readahead_info {
468 struct nilfs_btree_node *node; /* parent node */
469 int max_ra_blocks; /* max nof blocks to read ahead */
470 int index; /* current index on the parent node */
471 int ncmax; /* nof children in the parent node */
472};
473
474static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
475 struct buffer_head **bhp,
476 const struct nilfs_btree_readahead_info *ra)
477{
478 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
479 struct buffer_head *bh, *ra_bh;
480 sector_t submit_ptr = 0;
481 int ret;
482
483 ret = nilfs_btnode_submit_block(btnc, ptr, 0, READ, &bh, &submit_ptr);
484 if (ret) {
485 if (ret != -EEXIST)
486 return ret;
487 goto out_check;
488 }
489
490 if (ra) {
491 int i, n;
492 __u64 ptr2;
493
494 /* read ahead sibling nodes */
495 for (n = ra->max_ra_blocks, i = ra->index + 1;
496 n > 0 && i < ra->ncmax; n--, i++) {
497 ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);
498
499 ret = nilfs_btnode_submit_block(btnc, ptr2, 0, READA,
500 &ra_bh, &submit_ptr);
501 if (likely(!ret || ret == -EEXIST))
502 brelse(ra_bh);
503 else if (ret != -EBUSY)
504 break;
505 if (!buffer_locked(bh))
506 goto out_no_wait;
507 }
508 }
509
510 wait_on_buffer(bh);
511
512 out_no_wait:
513 if (!buffer_uptodate(bh)) {
514 brelse(bh);
515 return -EIO;
516 }
517
518 out_check:
519 if (nilfs_btree_broken_node_block(bh)) {
520 clear_buffer_uptodate(bh);
521 brelse(bh);
522 return -EINVAL;
523 }
524
525 *bhp = bh;
526 return 0;
527}
528
529static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
530 struct buffer_head **bhp)
531{
532 return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
533}
534
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900535static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700536 struct nilfs_btree_path *path,
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900537 __u64 key, __u64 *ptrp, int minlevel,
538 int readahead)
Koji Sato17c76b02009-04-06 19:01:24 -0700539{
540 struct nilfs_btree_node *node;
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900541 struct nilfs_btree_readahead_info p, *ra;
Koji Sato17c76b02009-04-06 19:01:24 -0700542 __u64 ptr;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900543 int level, index, found, ncmax, ret;
Koji Sato17c76b02009-04-06 19:01:24 -0700544
Koji Sato17c76b02009-04-06 19:01:24 -0700545 node = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900546 level = nilfs_btree_node_get_level(node);
547 if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
Koji Sato17c76b02009-04-06 19:01:24 -0700548 return -ENOENT;
549
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900550 found = nilfs_btree_node_lookup(node, key, &index);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900551 ptr = nilfs_btree_node_get_ptr(node, index,
552 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Koji Sato17c76b02009-04-06 19:01:24 -0700553 path[level].bp_bh = NULL;
554 path[level].bp_index = index;
555
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900556 ncmax = nilfs_btree_nchildren_per_block(btree);
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900557
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900558 while (--level >= minlevel) {
559 ra = NULL;
560 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
561 p.node = nilfs_btree_get_node(btree, path, level + 1,
562 &p.ncmax);
563 p.index = index;
564 p.max_ra_blocks = 7;
565 ra = &p;
566 }
567 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
568 ra);
Koji Sato17c76b02009-04-06 19:01:24 -0700569 if (ret < 0)
570 return ret;
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900571
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900572 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b945d52009-10-10 22:58:10 +0900573 if (nilfs_btree_bad_node(node, level))
574 return -EINVAL;
Koji Sato17c76b02009-04-06 19:01:24 -0700575 if (!found)
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900576 found = nilfs_btree_node_lookup(node, key, &index);
Koji Sato17c76b02009-04-06 19:01:24 -0700577 else
578 index = 0;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900579 if (index < ncmax) {
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900580 ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900581 } else {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -0700582 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
Koji Sato17c76b02009-04-06 19:01:24 -0700583 /* insert */
584 ptr = NILFS_BMAP_INVALID_PTR;
585 }
586 path[level].bp_index = index;
587 }
588 if (!found)
589 return -ENOENT;
590
591 if (ptrp != NULL)
592 *ptrp = ptr;
593
594 return 0;
595}
596
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900597static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700598 struct nilfs_btree_path *path,
599 __u64 *keyp, __u64 *ptrp)
600{
601 struct nilfs_btree_node *node;
602 __u64 ptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900603 int index, level, ncmax, ret;
Koji Sato17c76b02009-04-06 19:01:24 -0700604
605 node = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900606 index = nilfs_btree_node_get_nchildren(node) - 1;
Koji Sato17c76b02009-04-06 19:01:24 -0700607 if (index < 0)
608 return -ENOENT;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900609 level = nilfs_btree_node_get_level(node);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900610 ptr = nilfs_btree_node_get_ptr(node, index,
611 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Koji Sato17c76b02009-04-06 19:01:24 -0700612 path[level].bp_bh = NULL;
613 path[level].bp_index = index;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900614 ncmax = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -0700615
616 for (level--; level > 0; level--) {
Ryusuke Konishif198dbb2009-05-22 01:07:13 +0900617 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700618 if (ret < 0)
619 return ret;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900620 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b945d52009-10-10 22:58:10 +0900621 if (nilfs_btree_bad_node(node, level))
622 return -EINVAL;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900623 index = nilfs_btree_node_get_nchildren(node) - 1;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900624 ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -0700625 path[level].bp_index = index;
626 }
627
628 if (keyp != NULL)
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900629 *keyp = nilfs_btree_node_get_key(node, index);
Koji Sato17c76b02009-04-06 19:01:24 -0700630 if (ptrp != NULL)
631 *ptrp = ptr;
632
633 return 0;
634}
635
Ryusuke Konishi5b203842015-04-16 12:46:36 -0700636/**
637 * nilfs_btree_get_next_key - get next valid key from btree path array
638 * @btree: bmap struct of btree
639 * @path: array of nilfs_btree_path struct
640 * @minlevel: start level
641 * @nextkey: place to store the next valid key
642 *
643 * Return Value: If a next key was found, 0 is returned. Otherwise,
644 * -ENOENT is returned.
645 */
646static int nilfs_btree_get_next_key(const struct nilfs_bmap *btree,
647 const struct nilfs_btree_path *path,
648 int minlevel, __u64 *nextkey)
649{
650 struct nilfs_btree_node *node;
651 int maxlevel = nilfs_btree_height(btree) - 1;
652 int index, next_adj, level;
653
654 /* Next index is already set to bp_index for leaf nodes. */
655 next_adj = 0;
656 for (level = minlevel; level <= maxlevel; level++) {
657 if (level == maxlevel)
658 node = nilfs_btree_get_root(btree);
659 else
660 node = nilfs_btree_get_nonroot_node(path, level);
661
662 index = path[level].bp_index + next_adj;
663 if (index < nilfs_btree_node_get_nchildren(node)) {
664 /* Next key is in this node */
665 *nextkey = nilfs_btree_node_get_key(node, index);
666 return 0;
667 }
668 /* For non-leaf nodes, next index is stored at bp_index + 1. */
669 next_adj = 1;
670 }
671 return -ENOENT;
672}
673
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900674static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700675 __u64 key, int level, __u64 *ptrp)
676{
Koji Sato17c76b02009-04-06 19:01:24 -0700677 struct nilfs_btree_path *path;
Koji Sato17c76b02009-04-06 19:01:24 -0700678 int ret;
679
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900680 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -0700681 if (path == NULL)
682 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -0700683
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900684 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700685
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900686 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -0700687
688 return ret;
689}
690
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900691static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900692 __u64 key, __u64 *ptrp, unsigned maxblocks)
693{
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900694 struct nilfs_btree_path *path;
695 struct nilfs_btree_node *node;
696 struct inode *dat = NULL;
697 __u64 ptr, ptr2;
698 sector_t blocknr;
699 int level = NILFS_BTREE_LEVEL_NODE_MIN;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900700 int ret, cnt, index, maxlevel, ncmax;
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900701 struct nilfs_btree_readahead_info p;
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900702
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900703 path = nilfs_btree_alloc_path();
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900704 if (path == NULL)
705 return -ENOMEM;
Li Hongf9054402010-04-02 17:36:34 +0800706
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900707 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900708 if (ret < 0)
709 goto out;
710
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900711 if (NILFS_BMAP_USE_VBN(btree)) {
712 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900713 ret = nilfs_dat_translate(dat, ptr, &blocknr);
714 if (ret < 0)
715 goto out;
716 ptr = blocknr;
717 }
718 cnt = 1;
719 if (cnt == maxblocks)
720 goto end;
721
722 maxlevel = nilfs_btree_height(btree) - 1;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900723 node = nilfs_btree_get_node(btree, path, level, &ncmax);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900724 index = path[level].bp_index + 1;
725 for (;;) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900726 while (index < nilfs_btree_node_get_nchildren(node)) {
727 if (nilfs_btree_node_get_key(node, index) !=
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900728 key + cnt)
729 goto end;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900730 ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900731 if (dat) {
732 ret = nilfs_dat_translate(dat, ptr2, &blocknr);
733 if (ret < 0)
734 goto out;
735 ptr2 = blocknr;
736 }
737 if (ptr2 != ptr + cnt || ++cnt == maxblocks)
738 goto end;
739 index++;
740 continue;
741 }
742 if (level == maxlevel)
743 break;
744
745 /* look-up right sibling node */
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900746 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
747 p.index = path[level + 1].bp_index + 1;
748 p.max_ra_blocks = 7;
749 if (p.index >= nilfs_btree_node_get_nchildren(p.node) ||
750 nilfs_btree_node_get_key(p.node, p.index) != key + cnt)
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900751 break;
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900752 ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax);
753 path[level + 1].bp_index = p.index;
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900754
755 brelse(path[level].bp_bh);
756 path[level].bp_bh = NULL;
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +0900757
758 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
759 &p);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900760 if (ret < 0)
761 goto out;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900762 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900763 ncmax = nilfs_btree_nchildren_per_block(btree);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900764 index = 0;
765 path[level].bp_index = index;
766 }
767 end:
768 *ptrp = ptr;
769 ret = cnt;
770 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900771 nilfs_btree_free_path(path);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900772 return ret;
773}
774
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900775static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700776 struct nilfs_btree_path *path,
777 int level, __u64 key)
778{
779 if (level < nilfs_btree_height(btree) - 1) {
780 do {
Koji Sato17c76b02009-04-06 19:01:24 -0700781 nilfs_btree_node_set_key(
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900782 nilfs_btree_get_nonroot_node(path, level),
Koji Sato17c76b02009-04-06 19:01:24 -0700783 path[level].bp_index, key);
784 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900785 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700786 } while ((path[level].bp_index == 0) &&
787 (++level < nilfs_btree_height(btree) - 1));
788 }
789
790 /* root */
791 if (level == nilfs_btree_height(btree) - 1) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900792 nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
Koji Sato17c76b02009-04-06 19:01:24 -0700793 path[level].bp_index, key);
794 }
795}
796
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900797static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700798 struct nilfs_btree_path *path,
799 int level, __u64 *keyp, __u64 *ptrp)
800{
801 struct nilfs_btree_node *node;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900802 int ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -0700803
804 if (level < nilfs_btree_height(btree) - 1) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900805 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900806 ncblk = nilfs_btree_nchildren_per_block(btree);
807 nilfs_btree_node_insert(node, path[level].bp_index,
808 *keyp, *ptrp, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -0700809 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900810 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700811
812 if (path[level].bp_index == 0)
813 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900814 nilfs_btree_node_get_key(node,
815 0));
Koji Sato17c76b02009-04-06 19:01:24 -0700816 } else {
817 node = nilfs_btree_get_root(btree);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900818 nilfs_btree_node_insert(node, path[level].bp_index,
819 *keyp, *ptrp,
820 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Koji Sato17c76b02009-04-06 19:01:24 -0700821 }
822}
823
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900824static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700825 struct nilfs_btree_path *path,
826 int level, __u64 *keyp, __u64 *ptrp)
827{
828 struct nilfs_btree_node *node, *left;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900829 int nchildren, lnchildren, n, move, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -0700830
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900831 node = nilfs_btree_get_nonroot_node(path, level);
832 left = nilfs_btree_get_sib_node(path, level);
833 nchildren = nilfs_btree_node_get_nchildren(node);
834 lnchildren = nilfs_btree_node_get_nchildren(left);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900835 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -0700836 move = 0;
837
838 n = (nchildren + lnchildren + 1) / 2 - lnchildren;
839 if (n > path[level].bp_index) {
840 /* move insert point */
841 n--;
842 move = 1;
843 }
844
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900845 nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -0700846
847 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900848 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700849 if (!buffer_dirty(path[level].bp_sib_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900850 mark_buffer_dirty(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700851
Koji Sato17c76b02009-04-06 19:01:24 -0700852 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900853 nilfs_btree_node_get_key(node, 0));
Koji Sato17c76b02009-04-06 19:01:24 -0700854
855 if (move) {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900856 brelse(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700857 path[level].bp_bh = path[level].bp_sib_bh;
858 path[level].bp_sib_bh = NULL;
859 path[level].bp_index += lnchildren;
860 path[level + 1].bp_index--;
861 } else {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900862 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700863 path[level].bp_sib_bh = NULL;
864 path[level].bp_index -= n;
865 }
866
867 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
868}
869
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900870static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700871 struct nilfs_btree_path *path,
872 int level, __u64 *keyp, __u64 *ptrp)
873{
874 struct nilfs_btree_node *node, *right;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900875 int nchildren, rnchildren, n, move, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -0700876
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900877 node = nilfs_btree_get_nonroot_node(path, level);
878 right = nilfs_btree_get_sib_node(path, level);
879 nchildren = nilfs_btree_node_get_nchildren(node);
880 rnchildren = nilfs_btree_node_get_nchildren(right);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900881 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -0700882 move = 0;
883
884 n = (nchildren + rnchildren + 1) / 2 - rnchildren;
885 if (n > nchildren - path[level].bp_index) {
886 /* move insert point */
887 n--;
888 move = 1;
889 }
890
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900891 nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -0700892
893 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900894 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700895 if (!buffer_dirty(path[level].bp_sib_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900896 mark_buffer_dirty(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700897
Koji Sato17c76b02009-04-06 19:01:24 -0700898 path[level + 1].bp_index++;
899 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900900 nilfs_btree_node_get_key(right, 0));
Koji Sato17c76b02009-04-06 19:01:24 -0700901 path[level + 1].bp_index--;
902
903 if (move) {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900904 brelse(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700905 path[level].bp_bh = path[level].bp_sib_bh;
906 path[level].bp_sib_bh = NULL;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900907 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700908 path[level + 1].bp_index++;
909 } else {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900910 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700911 path[level].bp_sib_bh = NULL;
912 }
913
914 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
915}
916
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900917static void nilfs_btree_split(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700918 struct nilfs_btree_path *path,
919 int level, __u64 *keyp, __u64 *ptrp)
920{
921 struct nilfs_btree_node *node, *right;
922 __u64 newkey;
923 __u64 newptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900924 int nchildren, n, move, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -0700925
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900926 node = nilfs_btree_get_nonroot_node(path, level);
927 right = nilfs_btree_get_sib_node(path, level);
928 nchildren = nilfs_btree_node_get_nchildren(node);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900929 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -0700930 move = 0;
931
932 n = (nchildren + 1) / 2;
933 if (n > nchildren - path[level].bp_index) {
934 n--;
935 move = 1;
936 }
937
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900938 nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -0700939
940 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900941 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700942 if (!buffer_dirty(path[level].bp_sib_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900943 mark_buffer_dirty(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700944
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900945 newkey = nilfs_btree_node_get_key(right, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700946 newptr = path[level].bp_newreq.bpr_ptr;
947
948 if (move) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900949 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900950 nilfs_btree_node_insert(right, path[level].bp_index,
951 *keyp, *ptrp, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -0700952
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900953 *keyp = nilfs_btree_node_get_key(right, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700954 *ptrp = path[level].bp_newreq.bpr_ptr;
955
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900956 brelse(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700957 path[level].bp_bh = path[level].bp_sib_bh;
958 path[level].bp_sib_bh = NULL;
959 } else {
960 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
961
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900962 *keyp = nilfs_btree_node_get_key(right, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700963 *ptrp = path[level].bp_newreq.bpr_ptr;
964
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900965 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700966 path[level].bp_sib_bh = NULL;
967 }
968
969 path[level + 1].bp_index++;
970}
971
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900972static void nilfs_btree_grow(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700973 struct nilfs_btree_path *path,
974 int level, __u64 *keyp, __u64 *ptrp)
975{
976 struct nilfs_btree_node *root, *child;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900977 int n, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -0700978
Koji Sato17c76b02009-04-06 19:01:24 -0700979 root = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900980 child = nilfs_btree_get_sib_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900981 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -0700982
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900983 n = nilfs_btree_node_get_nchildren(root);
Koji Sato17c76b02009-04-06 19:01:24 -0700984
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +0900985 nilfs_btree_node_move_right(root, child, n,
986 NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900987 nilfs_btree_node_set_level(root, level + 1);
Koji Sato17c76b02009-04-06 19:01:24 -0700988
989 if (!buffer_dirty(path[level].bp_sib_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900990 mark_buffer_dirty(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700991
Koji Sato17c76b02009-04-06 19:01:24 -0700992 path[level].bp_bh = path[level].bp_sib_bh;
993 path[level].bp_sib_bh = NULL;
994
995 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
996
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900997 *keyp = nilfs_btree_node_get_key(child, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700998 *ptrp = path[level].bp_newreq.bpr_ptr;
999}
1000
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001001static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001002 const struct nilfs_btree_path *path)
1003{
1004 struct nilfs_btree_node *node;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001005 int level, ncmax;
Koji Sato17c76b02009-04-06 19:01:24 -07001006
1007 if (path == NULL)
1008 return NILFS_BMAP_INVALID_PTR;
1009
1010 /* left sibling */
1011 level = NILFS_BTREE_LEVEL_NODE_MIN;
1012 if (path[level].bp_index > 0) {
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001013 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1014 return nilfs_btree_node_get_ptr(node,
1015 path[level].bp_index - 1,
1016 ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001017 }
1018
1019 /* parent */
1020 level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
1021 if (level <= nilfs_btree_height(btree) - 1) {
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001022 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1023 return nilfs_btree_node_get_ptr(node, path[level].bp_index,
1024 ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001025 }
1026
1027 return NILFS_BMAP_INVALID_PTR;
1028}
1029
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001030static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001031 const struct nilfs_btree_path *path,
1032 __u64 key)
1033{
1034 __u64 ptr;
1035
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001036 ptr = nilfs_bmap_find_target_seq(btree, key);
Koji Sato17c76b02009-04-06 19:01:24 -07001037 if (ptr != NILFS_BMAP_INVALID_PTR)
1038 /* sequential access */
1039 return ptr;
1040 else {
1041 ptr = nilfs_btree_find_near(btree, path);
1042 if (ptr != NILFS_BMAP_INVALID_PTR)
1043 /* near */
1044 return ptr;
1045 }
1046 /* block group */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001047 return nilfs_bmap_find_target_in_group(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001048}
1049
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001050static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001051 struct nilfs_btree_path *path,
1052 int *levelp, __u64 key, __u64 ptr,
1053 struct nilfs_bmap_stats *stats)
1054{
1055 struct buffer_head *bh;
1056 struct nilfs_btree_node *node, *parent, *sib;
1057 __u64 sibptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001058 int pindex, level, ncmax, ncblk, ret;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001059 struct inode *dat = NULL;
Koji Sato17c76b02009-04-06 19:01:24 -07001060
1061 stats->bs_nblocks = 0;
1062 level = NILFS_BTREE_LEVEL_DATA;
1063
1064 /* allocate a new ptr for data block */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001065 if (NILFS_BMAP_USE_VBN(btree)) {
Koji Sato17c76b02009-04-06 19:01:24 -07001066 path[level].bp_newreq.bpr_ptr =
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09001067 nilfs_btree_find_target_v(btree, path, key);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001068 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001069 }
Koji Sato17c76b02009-04-06 19:01:24 -07001070
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001071 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001072 if (ret < 0)
1073 goto err_out_data;
1074
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001075 ncblk = nilfs_btree_nchildren_per_block(btree);
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001076
Koji Sato17c76b02009-04-06 19:01:24 -07001077 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
1078 level < nilfs_btree_height(btree) - 1;
1079 level++) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001080 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001081 if (nilfs_btree_node_get_nchildren(node) < ncblk) {
Koji Sato17c76b02009-04-06 19:01:24 -07001082 path[level].bp_op = nilfs_btree_do_insert;
1083 stats->bs_nblocks++;
1084 goto out;
1085 }
1086
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001087 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001088 pindex = path[level + 1].bp_index;
1089
1090 /* left sibling */
1091 if (pindex > 0) {
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001092 sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
1093 ncmax);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001094 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001095 if (ret < 0)
1096 goto err_out_child_node;
1097 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001098 if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
Koji Sato17c76b02009-04-06 19:01:24 -07001099 path[level].bp_sib_bh = bh;
1100 path[level].bp_op = nilfs_btree_carry_left;
1101 stats->bs_nblocks++;
1102 goto out;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001103 } else {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001104 brelse(bh);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001105 }
Koji Sato17c76b02009-04-06 19:01:24 -07001106 }
1107
1108 /* right sibling */
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001109 if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) {
1110 sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
1111 ncmax);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001112 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001113 if (ret < 0)
1114 goto err_out_child_node;
1115 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001116 if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
Koji Sato17c76b02009-04-06 19:01:24 -07001117 path[level].bp_sib_bh = bh;
1118 path[level].bp_op = nilfs_btree_carry_right;
1119 stats->bs_nblocks++;
1120 goto out;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001121 } else {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001122 brelse(bh);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001123 }
Koji Sato17c76b02009-04-06 19:01:24 -07001124 }
1125
1126 /* split */
1127 path[level].bp_newreq.bpr_ptr =
1128 path[level - 1].bp_newreq.bpr_ptr + 1;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001129 ret = nilfs_bmap_prepare_alloc_ptr(btree,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001130 &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001131 if (ret < 0)
1132 goto err_out_child_node;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001133 ret = nilfs_btree_get_new_block(btree,
1134 path[level].bp_newreq.bpr_ptr,
1135 &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001136 if (ret < 0)
1137 goto err_out_curr_node;
1138
1139 stats->bs_nblocks++;
1140
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001141 sib = (struct nilfs_btree_node *)bh->b_data;
1142 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);
Koji Sato17c76b02009-04-06 19:01:24 -07001143 path[level].bp_sib_bh = bh;
1144 path[level].bp_op = nilfs_btree_split;
1145 }
1146
1147 /* root */
1148 node = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001149 if (nilfs_btree_node_get_nchildren(node) <
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001150 NILFS_BTREE_ROOT_NCHILDREN_MAX) {
Koji Sato17c76b02009-04-06 19:01:24 -07001151 path[level].bp_op = nilfs_btree_do_insert;
1152 stats->bs_nblocks++;
1153 goto out;
1154 }
1155
1156 /* grow */
1157 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001158 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001159 if (ret < 0)
1160 goto err_out_child_node;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001161 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1162 &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001163 if (ret < 0)
1164 goto err_out_curr_node;
1165
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001166 nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data,
1167 0, level, 0, ncblk, NULL, NULL);
Koji Sato17c76b02009-04-06 19:01:24 -07001168 path[level].bp_sib_bh = bh;
1169 path[level].bp_op = nilfs_btree_grow;
1170
1171 level++;
1172 path[level].bp_op = nilfs_btree_do_insert;
1173
1174 /* a newly-created node block and a data block are added */
1175 stats->bs_nblocks += 2;
1176
1177 /* success */
1178 out:
1179 *levelp = level;
1180 return ret;
1181
1182 /* error */
1183 err_out_curr_node:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001184 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001185 err_out_child_node:
1186 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001187 nilfs_btnode_delete(path[level].bp_sib_bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001188 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001189
1190 }
1191
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001192 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001193 err_out_data:
1194 *levelp = level;
1195 stats->bs_nblocks = 0;
1196 return ret;
1197}
1198
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001199static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001200 struct nilfs_btree_path *path,
1201 int maxlevel, __u64 key, __u64 ptr)
1202{
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001203 struct inode *dat = NULL;
Koji Sato17c76b02009-04-06 19:01:24 -07001204 int level;
1205
1206 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1207 ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001208 if (NILFS_BMAP_USE_VBN(btree)) {
Ryusuke Konishidc935be2010-07-10 22:21:54 +09001209 nilfs_bmap_set_target_v(btree, key, ptr);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001210 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001211 }
Koji Sato17c76b02009-04-06 19:01:24 -07001212
1213 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001214 nilfs_bmap_commit_alloc_ptr(btree,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001215 &path[level - 1].bp_newreq, dat);
Pekka Enberg8acfbf02009-04-06 19:01:49 -07001216 path[level].bp_op(btree, path, level, &key, &ptr);
Koji Sato17c76b02009-04-06 19:01:24 -07001217 }
1218
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001219 if (!nilfs_bmap_dirty(btree))
1220 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001221}
1222
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001223static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
Koji Sato17c76b02009-04-06 19:01:24 -07001224{
Koji Sato17c76b02009-04-06 19:01:24 -07001225 struct nilfs_btree_path *path;
1226 struct nilfs_bmap_stats stats;
1227 int level, ret;
1228
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001229 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07001230 if (path == NULL)
1231 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07001232
1233 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +09001234 NILFS_BTREE_LEVEL_NODE_MIN, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07001235 if (ret != -ENOENT) {
1236 if (ret == 0)
1237 ret = -EEXIST;
1238 goto out;
1239 }
1240
1241 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1242 if (ret < 0)
1243 goto out;
1244 nilfs_btree_commit_insert(btree, path, level, key, ptr);
Ryusuke Konishibe667372011-03-05 00:19:32 +09001245 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
Koji Sato17c76b02009-04-06 19:01:24 -07001246
1247 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001248 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07001249 return ret;
1250}
1251
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001252static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001253 struct nilfs_btree_path *path,
1254 int level, __u64 *keyp, __u64 *ptrp)
1255{
1256 struct nilfs_btree_node *node;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001257 int ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -07001258
1259 if (level < nilfs_btree_height(btree) - 1) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001260 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001261 ncblk = nilfs_btree_nchildren_per_block(btree);
1262 nilfs_btree_node_delete(node, path[level].bp_index,
1263 keyp, ptrp, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -07001264 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001265 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001266 if (path[level].bp_index == 0)
1267 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001268 nilfs_btree_node_get_key(node, 0));
Koji Sato17c76b02009-04-06 19:01:24 -07001269 } else {
1270 node = nilfs_btree_get_root(btree);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001271 nilfs_btree_node_delete(node, path[level].bp_index,
1272 keyp, ptrp,
1273 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Koji Sato17c76b02009-04-06 19:01:24 -07001274 }
1275}
1276
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001277static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001278 struct nilfs_btree_path *path,
1279 int level, __u64 *keyp, __u64 *ptrp)
1280{
1281 struct nilfs_btree_node *node, *left;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001282 int nchildren, lnchildren, n, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -07001283
1284 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1285
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001286 node = nilfs_btree_get_nonroot_node(path, level);
1287 left = nilfs_btree_get_sib_node(path, level);
1288 nchildren = nilfs_btree_node_get_nchildren(node);
1289 lnchildren = nilfs_btree_node_get_nchildren(left);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001290 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001291
1292 n = (nchildren + lnchildren) / 2 - nchildren;
1293
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001294 nilfs_btree_node_move_right(left, node, n, ncblk, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -07001295
1296 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001297 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001298 if (!buffer_dirty(path[level].bp_sib_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001299 mark_buffer_dirty(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001300
Koji Sato17c76b02009-04-06 19:01:24 -07001301 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001302 nilfs_btree_node_get_key(node, 0));
Koji Sato17c76b02009-04-06 19:01:24 -07001303
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001304 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001305 path[level].bp_sib_bh = NULL;
1306 path[level].bp_index += n;
1307}
1308
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001309static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001310 struct nilfs_btree_path *path,
1311 int level, __u64 *keyp, __u64 *ptrp)
1312{
1313 struct nilfs_btree_node *node, *right;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001314 int nchildren, rnchildren, n, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -07001315
1316 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1317
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001318 node = nilfs_btree_get_nonroot_node(path, level);
1319 right = nilfs_btree_get_sib_node(path, level);
1320 nchildren = nilfs_btree_node_get_nchildren(node);
1321 rnchildren = nilfs_btree_node_get_nchildren(right);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001322 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001323
1324 n = (nchildren + rnchildren) / 2 - nchildren;
1325
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001326 nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -07001327
1328 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001329 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001330 if (!buffer_dirty(path[level].bp_sib_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001331 mark_buffer_dirty(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001332
Koji Sato17c76b02009-04-06 19:01:24 -07001333 path[level + 1].bp_index++;
1334 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001335 nilfs_btree_node_get_key(right, 0));
Koji Sato17c76b02009-04-06 19:01:24 -07001336 path[level + 1].bp_index--;
1337
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001338 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001339 path[level].bp_sib_bh = NULL;
1340}
1341
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001342static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001343 struct nilfs_btree_path *path,
1344 int level, __u64 *keyp, __u64 *ptrp)
1345{
1346 struct nilfs_btree_node *node, *left;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001347 int n, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -07001348
1349 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1350
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001351 node = nilfs_btree_get_nonroot_node(path, level);
1352 left = nilfs_btree_get_sib_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001353 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001354
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001355 n = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -07001356
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001357 nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -07001358
1359 if (!buffer_dirty(path[level].bp_sib_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001360 mark_buffer_dirty(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001361
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001362 nilfs_btnode_delete(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001363 path[level].bp_bh = path[level].bp_sib_bh;
1364 path[level].bp_sib_bh = NULL;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001365 path[level].bp_index += nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -07001366}
1367
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001368static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001369 struct nilfs_btree_path *path,
1370 int level, __u64 *keyp, __u64 *ptrp)
1371{
1372 struct nilfs_btree_node *node, *right;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001373 int n, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -07001374
1375 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1376
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001377 node = nilfs_btree_get_nonroot_node(path, level);
1378 right = nilfs_btree_get_sib_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001379 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001380
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001381 n = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -07001382
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001383 nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -07001384
1385 if (!buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001386 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001387
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001388 nilfs_btnode_delete(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001389 path[level].bp_sib_bh = NULL;
1390 path[level + 1].bp_index++;
1391}
1392
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001393static void nilfs_btree_shrink(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001394 struct nilfs_btree_path *path,
1395 int level, __u64 *keyp, __u64 *ptrp)
1396{
1397 struct nilfs_btree_node *root, *child;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001398 int n, ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -07001399
1400 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1401
Koji Sato17c76b02009-04-06 19:01:24 -07001402 root = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001403 child = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001404 ncblk = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001405
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001406 nilfs_btree_node_delete(root, 0, NULL, NULL,
1407 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001408 nilfs_btree_node_set_level(root, level);
1409 n = nilfs_btree_node_get_nchildren(child);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001410 nilfs_btree_node_move_left(root, child, n,
1411 NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -07001412
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001413 nilfs_btnode_delete(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001414 path[level].bp_bh = NULL;
1415}
1416
Ryusuke Konishid4099052011-05-25 23:00:27 +09001417static void nilfs_btree_nop(struct nilfs_bmap *btree,
1418 struct nilfs_btree_path *path,
1419 int level, __u64 *keyp, __u64 *ptrp)
1420{
1421}
Koji Sato17c76b02009-04-06 19:01:24 -07001422
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001423static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001424 struct nilfs_btree_path *path,
1425 int *levelp,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001426 struct nilfs_bmap_stats *stats,
1427 struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001428{
1429 struct buffer_head *bh;
1430 struct nilfs_btree_node *node, *parent, *sib;
1431 __u64 sibptr;
Ryusuke Konishife744fd2011-05-25 23:00:27 +09001432 int pindex, dindex, level, ncmin, ncmax, ncblk, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07001433
1434 ret = 0;
1435 stats->bs_nblocks = 0;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001436 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001437 ncblk = nilfs_btree_nchildren_per_block(btree);
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001438
Ryusuke Konishife744fd2011-05-25 23:00:27 +09001439 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;
Koji Sato17c76b02009-04-06 19:01:24 -07001440 level < nilfs_btree_height(btree) - 1;
1441 level++) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001442 node = nilfs_btree_get_nonroot_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -07001443 path[level].bp_oldreq.bpr_ptr =
Ryusuke Konishife744fd2011-05-25 23:00:27 +09001444 nilfs_btree_node_get_ptr(node, dindex, ncblk);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001445 ret = nilfs_bmap_prepare_end_ptr(btree,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001446 &path[level].bp_oldreq, dat);
Ryusuke Konishid4b96152009-05-24 03:25:44 +09001447 if (ret < 0)
1448 goto err_out_child_node;
Koji Sato17c76b02009-04-06 19:01:24 -07001449
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001450 if (nilfs_btree_node_get_nchildren(node) > ncmin) {
Koji Sato17c76b02009-04-06 19:01:24 -07001451 path[level].bp_op = nilfs_btree_do_delete;
1452 stats->bs_nblocks++;
1453 goto out;
1454 }
1455
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001456 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001457 pindex = path[level + 1].bp_index;
Ryusuke Konishife744fd2011-05-25 23:00:27 +09001458 dindex = pindex;
Koji Sato17c76b02009-04-06 19:01:24 -07001459
1460 if (pindex > 0) {
1461 /* left sibling */
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001462 sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
1463 ncmax);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001464 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001465 if (ret < 0)
1466 goto err_out_curr_node;
1467 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001468 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
Koji Sato17c76b02009-04-06 19:01:24 -07001469 path[level].bp_sib_bh = bh;
1470 path[level].bp_op = nilfs_btree_borrow_left;
1471 stats->bs_nblocks++;
1472 goto out;
1473 } else {
1474 path[level].bp_sib_bh = bh;
1475 path[level].bp_op = nilfs_btree_concat_left;
1476 stats->bs_nblocks++;
1477 /* continue; */
1478 }
1479 } else if (pindex <
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001480 nilfs_btree_node_get_nchildren(parent) - 1) {
Koji Sato17c76b02009-04-06 19:01:24 -07001481 /* right sibling */
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001482 sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
1483 ncmax);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001484 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001485 if (ret < 0)
1486 goto err_out_curr_node;
1487 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001488 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
Koji Sato17c76b02009-04-06 19:01:24 -07001489 path[level].bp_sib_bh = bh;
1490 path[level].bp_op = nilfs_btree_borrow_right;
1491 stats->bs_nblocks++;
1492 goto out;
1493 } else {
1494 path[level].bp_sib_bh = bh;
1495 path[level].bp_op = nilfs_btree_concat_right;
1496 stats->bs_nblocks++;
Ryusuke Konishife744fd2011-05-25 23:00:27 +09001497 /*
1498 * When merging right sibling node
1499 * into the current node, pointer to
1500 * the right sibling node must be
1501 * terminated instead. The adjustment
1502 * below is required for that.
1503 */
1504 dindex = pindex + 1;
Koji Sato17c76b02009-04-06 19:01:24 -07001505 /* continue; */
1506 }
1507 } else {
1508 /* no siblings */
1509 /* the only child of the root node */
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001510 WARN_ON(level != nilfs_btree_height(btree) - 2);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001511 if (nilfs_btree_node_get_nchildren(node) - 1 <=
Koji Sato17c76b02009-04-06 19:01:24 -07001512 NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1513 path[level].bp_op = nilfs_btree_shrink;
1514 stats->bs_nblocks += 2;
Ryusuke Konishid4099052011-05-25 23:00:27 +09001515 level++;
1516 path[level].bp_op = nilfs_btree_nop;
1517 goto shrink_root_child;
Koji Sato17c76b02009-04-06 19:01:24 -07001518 } else {
1519 path[level].bp_op = nilfs_btree_do_delete;
1520 stats->bs_nblocks++;
Ryusuke Konishid4099052011-05-25 23:00:27 +09001521 goto out;
Koji Sato17c76b02009-04-06 19:01:24 -07001522 }
Koji Sato17c76b02009-04-06 19:01:24 -07001523 }
1524 }
1525
Ryusuke Konishid4099052011-05-25 23:00:27 +09001526 /* child of the root node is deleted */
1527 path[level].bp_op = nilfs_btree_do_delete;
1528 stats->bs_nblocks++;
1529
1530shrink_root_child:
Koji Sato17c76b02009-04-06 19:01:24 -07001531 node = nilfs_btree_get_root(btree);
1532 path[level].bp_oldreq.bpr_ptr =
Ryusuke Konishife744fd2011-05-25 23:00:27 +09001533 nilfs_btree_node_get_ptr(node, dindex,
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001534 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Ryusuke Konishid4b96152009-05-24 03:25:44 +09001535
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001536 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
Ryusuke Konishid4b96152009-05-24 03:25:44 +09001537 if (ret < 0)
1538 goto err_out_child_node;
1539
Koji Sato17c76b02009-04-06 19:01:24 -07001540 /* success */
1541 out:
1542 *levelp = level;
1543 return ret;
1544
1545 /* error */
1546 err_out_curr_node:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001547 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001548 err_out_child_node:
1549 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001550 brelse(path[level].bp_sib_bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001551 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001552 }
1553 *levelp = level;
1554 stats->bs_nblocks = 0;
1555 return ret;
1556}
1557
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001558static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001559 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001560 int maxlevel, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001561{
1562 int level;
1563
1564 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001565 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
Pekka Enberg8acfbf02009-04-06 19:01:49 -07001566 path[level].bp_op(btree, path, level, NULL, NULL);
Koji Sato17c76b02009-04-06 19:01:24 -07001567 }
1568
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001569 if (!nilfs_bmap_dirty(btree))
1570 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001571}
1572
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001573static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
Koji Sato17c76b02009-04-06 19:01:24 -07001574
1575{
Koji Sato17c76b02009-04-06 19:01:24 -07001576 struct nilfs_btree_path *path;
1577 struct nilfs_bmap_stats stats;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001578 struct inode *dat;
Koji Sato17c76b02009-04-06 19:01:24 -07001579 int level, ret;
1580
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001581 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07001582 if (path == NULL)
1583 return -ENOMEM;
Li Hongf9054402010-04-02 17:36:34 +08001584
Koji Sato17c76b02009-04-06 19:01:24 -07001585 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +09001586 NILFS_BTREE_LEVEL_NODE_MIN, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07001587 if (ret < 0)
1588 goto out;
1589
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001590
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001591 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001592
1593 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001594 if (ret < 0)
1595 goto out;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001596 nilfs_btree_commit_delete(btree, path, level, dat);
Ryusuke Konishibe667372011-03-05 00:19:32 +09001597 nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);
Koji Sato17c76b02009-04-06 19:01:24 -07001598
1599out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001600 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07001601 return ret;
1602}
1603
Ryusuke Konishi5b203842015-04-16 12:46:36 -07001604static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
1605 __u64 *keyp)
1606{
1607 struct nilfs_btree_path *path;
1608 const int minlevel = NILFS_BTREE_LEVEL_NODE_MIN;
1609 int ret;
1610
1611 path = nilfs_btree_alloc_path();
1612 if (!path)
1613 return -ENOMEM;
1614
1615 ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
1616 if (!ret)
1617 *keyp = start;
1618 else if (ret == -ENOENT)
1619 ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
1620
1621 nilfs_btree_free_path(path);
1622 return ret;
1623}
1624
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001625static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
Koji Sato17c76b02009-04-06 19:01:24 -07001626{
Koji Sato17c76b02009-04-06 19:01:24 -07001627 struct nilfs_btree_path *path;
1628 int ret;
1629
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001630 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07001631 if (path == NULL)
1632 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07001633
1634 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1635
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001636 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07001637
1638 return ret;
1639}
1640
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001641static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
Koji Sato17c76b02009-04-06 19:01:24 -07001642{
1643 struct buffer_head *bh;
Koji Sato17c76b02009-04-06 19:01:24 -07001644 struct nilfs_btree_node *root, *node;
1645 __u64 maxkey, nextmaxkey;
1646 __u64 ptr;
1647 int nchildren, ret;
1648
Koji Sato17c76b02009-04-06 19:01:24 -07001649 root = nilfs_btree_get_root(btree);
1650 switch (nilfs_btree_height(btree)) {
1651 case 2:
1652 bh = NULL;
1653 node = root;
1654 break;
1655 case 3:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001656 nchildren = nilfs_btree_node_get_nchildren(root);
Koji Sato17c76b02009-04-06 19:01:24 -07001657 if (nchildren > 1)
1658 return 0;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001659 ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
1660 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001661 ret = nilfs_btree_get_block(btree, ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001662 if (ret < 0)
1663 return ret;
1664 node = (struct nilfs_btree_node *)bh->b_data;
1665 break;
1666 default:
1667 return 0;
1668 }
1669
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001670 nchildren = nilfs_btree_node_get_nchildren(node);
1671 maxkey = nilfs_btree_node_get_key(node, nchildren - 1);
Koji Sato17c76b02009-04-06 19:01:24 -07001672 nextmaxkey = (nchildren > 1) ?
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001673 nilfs_btree_node_get_key(node, nchildren - 2) : 0;
Koji Sato17c76b02009-04-06 19:01:24 -07001674 if (bh != NULL)
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001675 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001676
Ryusuke Konishi30333422009-05-24 00:09:44 +09001677 return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
Koji Sato17c76b02009-04-06 19:01:24 -07001678}
1679
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001680static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001681 __u64 *keys, __u64 *ptrs, int nitems)
1682{
1683 struct buffer_head *bh;
Koji Sato17c76b02009-04-06 19:01:24 -07001684 struct nilfs_btree_node *node, *root;
1685 __le64 *dkeys;
1686 __le64 *dptrs;
1687 __u64 ptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001688 int nchildren, ncmax, i, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07001689
Koji Sato17c76b02009-04-06 19:01:24 -07001690 root = nilfs_btree_get_root(btree);
1691 switch (nilfs_btree_height(btree)) {
1692 case 2:
1693 bh = NULL;
1694 node = root;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001695 ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX;
Koji Sato17c76b02009-04-06 19:01:24 -07001696 break;
1697 case 3:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001698 nchildren = nilfs_btree_node_get_nchildren(root);
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001699 WARN_ON(nchildren > 1);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001700 ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
1701 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001702 ret = nilfs_btree_get_block(btree, ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001703 if (ret < 0)
1704 return ret;
1705 node = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001706 ncmax = nilfs_btree_nchildren_per_block(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001707 break;
1708 default:
1709 node = NULL;
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001710 return -EINVAL;
Koji Sato17c76b02009-04-06 19:01:24 -07001711 }
1712
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001713 nchildren = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -07001714 if (nchildren < nitems)
1715 nitems = nchildren;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001716 dkeys = nilfs_btree_node_dkeys(node);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001717 dptrs = nilfs_btree_node_dptrs(node, ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001718 for (i = 0; i < nitems; i++) {
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09001719 keys[i] = le64_to_cpu(dkeys[i]);
1720 ptrs[i] = le64_to_cpu(dptrs[i]);
Koji Sato17c76b02009-04-06 19:01:24 -07001721 }
1722
1723 if (bh != NULL)
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001724 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001725
1726 return nitems;
1727}
1728
1729static int
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001730nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
Koji Sato17c76b02009-04-06 19:01:24 -07001731 union nilfs_bmap_ptr_req *dreq,
1732 union nilfs_bmap_ptr_req *nreq,
1733 struct buffer_head **bhp,
1734 struct nilfs_bmap_stats *stats)
1735{
1736 struct buffer_head *bh;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001737 struct inode *dat = NULL;
Koji Sato17c76b02009-04-06 19:01:24 -07001738 int ret;
1739
Koji Sato17c76b02009-04-06 19:01:24 -07001740 stats->bs_nblocks = 0;
1741
1742 /* for data */
1743 /* cannot find near ptr */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001744 if (NILFS_BMAP_USE_VBN(btree)) {
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09001745 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001746 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001747 }
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09001748
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001749 ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001750 if (ret < 0)
1751 return ret;
1752
1753 *bhp = NULL;
1754 stats->bs_nblocks++;
1755 if (nreq != NULL) {
1756 nreq->bpr_ptr = dreq->bpr_ptr + 1;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001757 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001758 if (ret < 0)
1759 goto err_out_dreq;
1760
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001761 ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001762 if (ret < 0)
1763 goto err_out_nreq;
1764
1765 *bhp = bh;
1766 stats->bs_nblocks++;
1767 }
1768
1769 /* success */
1770 return 0;
1771
1772 /* error */
1773 err_out_nreq:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001774 nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001775 err_out_dreq:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001776 nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001777 stats->bs_nblocks = 0;
1778 return ret;
1779
1780}
1781
1782static void
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001783nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001784 __u64 key, __u64 ptr,
1785 const __u64 *keys, const __u64 *ptrs,
Ryusuke Konishi30333422009-05-24 00:09:44 +09001786 int n,
Koji Sato17c76b02009-04-06 19:01:24 -07001787 union nilfs_bmap_ptr_req *dreq,
1788 union nilfs_bmap_ptr_req *nreq,
1789 struct buffer_head *bh)
1790{
Koji Sato17c76b02009-04-06 19:01:24 -07001791 struct nilfs_btree_node *node;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001792 struct inode *dat;
Koji Sato17c76b02009-04-06 19:01:24 -07001793 __u64 tmpptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001794 int ncblk;
Koji Sato17c76b02009-04-06 19:01:24 -07001795
1796 /* free resources */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001797 if (btree->b_ops->bop_clear != NULL)
1798 btree->b_ops->bop_clear(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001799
1800 /* ptr must be a pointer to a buffer head. */
1801 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1802
1803 /* convert and insert */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001804 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
Ryusuke Konishi957ed602015-02-27 15:51:56 -08001805 __nilfs_btree_init(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001806 if (nreq != NULL) {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001807 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1808 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001809
1810 /* create child node at level 1 */
Koji Sato17c76b02009-04-06 19:01:24 -07001811 node = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001812 ncblk = nilfs_btree_nchildren_per_block(btree);
1813 nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs);
1814 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk);
Koji Sato17c76b02009-04-06 19:01:24 -07001815 if (!buffer_dirty(bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001816 mark_buffer_dirty(bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001817 if (!nilfs_bmap_dirty(btree))
1818 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001819
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001820 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001821
1822 /* create root node at level 2 */
1823 node = nilfs_btree_get_root(btree);
1824 tmpptr = nreq->bpr_ptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001825 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1,
1826 NILFS_BTREE_ROOT_NCHILDREN_MAX,
1827 &keys[0], &tmpptr);
Koji Sato17c76b02009-04-06 19:01:24 -07001828 } else {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001829 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001830
1831 /* create root node at level 1 */
1832 node = nilfs_btree_get_root(btree);
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001833 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n,
1834 NILFS_BTREE_ROOT_NCHILDREN_MAX,
1835 keys, ptrs);
1836 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr,
1837 NILFS_BTREE_ROOT_NCHILDREN_MAX);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001838 if (!nilfs_bmap_dirty(btree))
1839 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001840 }
1841
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001842 if (NILFS_BMAP_USE_VBN(btree))
Ryusuke Konishidc935be2010-07-10 22:21:54 +09001843 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
Koji Sato17c76b02009-04-06 19:01:24 -07001844}
1845
1846/**
1847 * nilfs_btree_convert_and_insert -
1848 * @bmap:
1849 * @key:
1850 * @ptr:
1851 * @keys:
1852 * @ptrs:
1853 * @n:
Koji Sato17c76b02009-04-06 19:01:24 -07001854 */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001855int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001856 __u64 key, __u64 ptr,
Ryusuke Konishi30333422009-05-24 00:09:44 +09001857 const __u64 *keys, const __u64 *ptrs, int n)
Koji Sato17c76b02009-04-06 19:01:24 -07001858{
1859 struct buffer_head *bh;
1860 union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
1861 struct nilfs_bmap_stats stats;
1862 int ret;
1863
1864 if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1865 di = &dreq;
1866 ni = NULL;
1867 } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001868 1 << btree->b_inode->i_blkbits)) {
Koji Sato17c76b02009-04-06 19:01:24 -07001869 di = &dreq;
1870 ni = &nreq;
1871 } else {
1872 di = NULL;
1873 ni = NULL;
1874 BUG();
1875 }
1876
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001877 ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
Koji Sato17c76b02009-04-06 19:01:24 -07001878 &stats);
1879 if (ret < 0)
1880 return ret;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001881 nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
Ryusuke Konishi30333422009-05-24 00:09:44 +09001882 di, ni, bh);
Ryusuke Konishibe667372011-03-05 00:19:32 +09001883 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
Koji Sato17c76b02009-04-06 19:01:24 -07001884 return 0;
1885}
1886
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001887static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001888 struct nilfs_btree_path *path,
1889 int level,
1890 struct buffer_head *bh)
1891{
1892 while ((++level < nilfs_btree_height(btree) - 1) &&
1893 !buffer_dirty(path[level].bp_bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09001894 mark_buffer_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001895
1896 return 0;
1897}
1898
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001899static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001900 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001901 int level, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001902{
1903 struct nilfs_btree_node *parent;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001904 int ncmax, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07001905
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001906 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001907 path[level].bp_oldreq.bpr_ptr =
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001908 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
1909 ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001910 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001911 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
1912 &path[level].bp_newreq.bpr_req);
Koji Sato17c76b02009-04-06 19:01:24 -07001913 if (ret < 0)
1914 return ret;
1915
1916 if (buffer_nilfs_node(path[level].bp_bh)) {
1917 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
1918 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
1919 path[level].bp_ctxt.bh = path[level].bp_bh;
1920 ret = nilfs_btnode_prepare_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001921 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07001922 &path[level].bp_ctxt);
1923 if (ret < 0) {
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001924 nilfs_dat_abort_update(dat,
1925 &path[level].bp_oldreq.bpr_req,
1926 &path[level].bp_newreq.bpr_req);
Koji Sato17c76b02009-04-06 19:01:24 -07001927 return ret;
1928 }
1929 }
1930
1931 return 0;
1932}
1933
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001934static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001935 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001936 int level, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001937{
1938 struct nilfs_btree_node *parent;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001939 int ncmax;
Koji Sato17c76b02009-04-06 19:01:24 -07001940
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001941 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
1942 &path[level].bp_newreq.bpr_req,
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001943 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
Koji Sato17c76b02009-04-06 19:01:24 -07001944
1945 if (buffer_nilfs_node(path[level].bp_bh)) {
1946 nilfs_btnode_commit_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001947 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07001948 &path[level].bp_ctxt);
1949 path[level].bp_bh = path[level].bp_ctxt.bh;
1950 }
1951 set_buffer_nilfs_volatile(path[level].bp_bh);
1952
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09001953 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1954 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
1955 path[level].bp_newreq.bpr_ptr, ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07001956}
1957
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001958static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001959 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001960 int level, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001961{
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001962 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
1963 &path[level].bp_newreq.bpr_req);
Koji Sato17c76b02009-04-06 19:01:24 -07001964 if (buffer_nilfs_node(path[level].bp_bh))
1965 nilfs_btnode_abort_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001966 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07001967 &path[level].bp_ctxt);
1968}
1969
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001970static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001971 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001972 int minlevel, int *maxlevelp,
1973 struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001974{
1975 int level, ret;
1976
1977 level = minlevel;
1978 if (!buffer_nilfs_volatile(path[level].bp_bh)) {
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001979 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001980 if (ret < 0)
1981 return ret;
1982 }
1983 while ((++level < nilfs_btree_height(btree) - 1) &&
1984 !buffer_dirty(path[level].bp_bh)) {
1985
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001986 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001987 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001988 if (ret < 0)
1989 goto out;
1990 }
1991
1992 /* success */
Koji Sato17c76b02009-04-06 19:01:24 -07001993 *maxlevelp = level - 1;
1994 return 0;
1995
1996 /* error */
1997 out:
1998 while (--level > minlevel)
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001999 nilfs_btree_abort_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07002000 if (!buffer_nilfs_volatile(path[level].bp_bh))
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002001 nilfs_btree_abort_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07002002 return ret;
2003}
2004
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002005static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002006 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002007 int minlevel, int maxlevel,
2008 struct buffer_head *bh,
2009 struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07002010{
2011 int level;
2012
2013 if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002014 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07002015
2016 for (level = minlevel + 1; level <= maxlevel; level++)
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002017 nilfs_btree_commit_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07002018}
2019
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002020static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002021 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002022 int level, struct buffer_head *bh)
Koji Sato17c76b02009-04-06 19:01:24 -07002023{
Li Hong308f4412010-04-02 18:40:39 +08002024 int maxlevel = 0, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07002025 struct nilfs_btree_node *parent;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002026 struct inode *dat = nilfs_bmap_get_dat(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07002027 __u64 ptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09002028 int ncmax;
Koji Sato17c76b02009-04-06 19:01:24 -07002029
2030 get_bh(bh);
2031 path[level].bp_bh = bh;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002032 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
2033 dat);
Koji Sato17c76b02009-04-06 19:01:24 -07002034 if (ret < 0)
2035 goto out;
2036
2037 if (buffer_nilfs_volatile(path[level].bp_bh)) {
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09002038 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2039 ptr = nilfs_btree_node_get_ptr(parent,
2040 path[level + 1].bp_index,
2041 ncmax);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002042 ret = nilfs_dat_mark_dirty(dat, ptr);
Koji Sato17c76b02009-04-06 19:01:24 -07002043 if (ret < 0)
2044 goto out;
2045 }
2046
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002047 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07002048
2049 out:
2050 brelse(path[level].bp_bh);
2051 path[level].bp_bh = NULL;
2052 return ret;
2053}
2054
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002055static int nilfs_btree_propagate(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002056 struct buffer_head *bh)
2057{
Koji Sato17c76b02009-04-06 19:01:24 -07002058 struct nilfs_btree_path *path;
2059 struct nilfs_btree_node *node;
2060 __u64 key;
2061 int level, ret;
2062
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002063 WARN_ON(!buffer_dirty(bh));
Koji Sato17c76b02009-04-06 19:01:24 -07002064
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002065 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07002066 if (path == NULL)
2067 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07002068
2069 if (buffer_nilfs_node(bh)) {
2070 node = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002071 key = nilfs_btree_node_get_key(node, 0);
2072 level = nilfs_btree_node_get_level(node);
Koji Sato17c76b02009-04-06 19:01:24 -07002073 } else {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002074 key = nilfs_bmap_data_get_key(btree, bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002075 level = NILFS_BTREE_LEVEL_DATA;
2076 }
2077
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +09002078 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07002079 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002080 if (unlikely(ret == -ENOENT))
Koji Sato17c76b02009-04-06 19:01:24 -07002081 printk(KERN_CRIT "%s: key = %llu, level == %d\n",
2082 __func__, (unsigned long long)key, level);
Koji Sato17c76b02009-04-06 19:01:24 -07002083 goto out;
2084 }
2085
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002086 ret = NILFS_BMAP_USE_VBN(btree) ?
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09002087 nilfs_btree_propagate_v(btree, path, level, bh) :
2088 nilfs_btree_propagate_p(btree, path, level, bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002089
2090 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002091 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07002092
2093 return ret;
2094}
2095
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002096static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002097 struct buffer_head *bh)
2098{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002099 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
Koji Sato17c76b02009-04-06 19:01:24 -07002100}
2101
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002102static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002103 struct list_head *lists,
2104 struct buffer_head *bh)
2105{
2106 struct list_head *head;
2107 struct buffer_head *cbh;
2108 struct nilfs_btree_node *node, *cnode;
2109 __u64 key, ckey;
2110 int level;
2111
2112 get_bh(bh);
2113 node = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002114 key = nilfs_btree_node_get_key(node, 0);
2115 level = nilfs_btree_node_get_level(node);
Ryusuke Konishicfa913a2010-07-07 17:19:54 +09002116 if (level < NILFS_BTREE_LEVEL_NODE_MIN ||
2117 level >= NILFS_BTREE_LEVEL_MAX) {
2118 dump_stack();
2119 printk(KERN_WARNING
2120 "%s: invalid btree level: %d (key=%llu, ino=%lu, "
2121 "blocknr=%llu)\n",
2122 __func__, level, (unsigned long long)key,
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002123 NILFS_BMAP_I(btree)->vfs_inode.i_ino,
Ryusuke Konishicfa913a2010-07-07 17:19:54 +09002124 (unsigned long long)bh->b_blocknr);
2125 return;
2126 }
2127
Koji Sato17c76b02009-04-06 19:01:24 -07002128 list_for_each(head, &lists[level]) {
2129 cbh = list_entry(head, struct buffer_head, b_assoc_buffers);
2130 cnode = (struct nilfs_btree_node *)cbh->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002131 ckey = nilfs_btree_node_get_key(cnode, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07002132 if (key < ckey)
2133 break;
2134 }
2135 list_add_tail(&bh->b_assoc_buffers, head);
2136}
2137
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002138static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002139 struct list_head *listp)
2140{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002141 struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache;
Koji Sato17c76b02009-04-06 19:01:24 -07002142 struct list_head lists[NILFS_BTREE_LEVEL_MAX];
2143 struct pagevec pvec;
2144 struct buffer_head *bh, *head;
2145 pgoff_t index = 0;
2146 int level, i;
2147
2148 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
2149 level < NILFS_BTREE_LEVEL_MAX;
2150 level++)
2151 INIT_LIST_HEAD(&lists[level]);
2152
2153 pagevec_init(&pvec, 0);
2154
2155 while (pagevec_lookup_tag(&pvec, btcache, &index, PAGECACHE_TAG_DIRTY,
2156 PAGEVEC_SIZE)) {
2157 for (i = 0; i < pagevec_count(&pvec); i++) {
2158 bh = head = page_buffers(pvec.pages[i]);
2159 do {
2160 if (buffer_dirty(bh))
2161 nilfs_btree_add_dirty_buffer(btree,
2162 lists, bh);
2163 } while ((bh = bh->b_this_page) != head);
2164 }
2165 pagevec_release(&pvec);
2166 cond_resched();
2167 }
2168
2169 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
2170 level < NILFS_BTREE_LEVEL_MAX;
2171 level++)
Ryusuke Konishi0935db72009-11-29 02:39:11 +09002172 list_splice_tail(&lists[level], listp);
Koji Sato17c76b02009-04-06 19:01:24 -07002173}
2174
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002175static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002176 struct nilfs_btree_path *path,
2177 int level,
2178 struct buffer_head **bh,
2179 sector_t blocknr,
2180 union nilfs_binfo *binfo)
2181{
2182 struct nilfs_btree_node *parent;
2183 __u64 key;
2184 __u64 ptr;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09002185 int ncmax, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07002186
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09002187 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2188 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2189 ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07002190 if (buffer_nilfs_node(*bh)) {
2191 path[level].bp_ctxt.oldkey = ptr;
2192 path[level].bp_ctxt.newkey = blocknr;
2193 path[level].bp_ctxt.bh = *bh;
2194 ret = nilfs_btnode_prepare_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002195 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07002196 &path[level].bp_ctxt);
2197 if (ret < 0)
2198 return ret;
2199 nilfs_btnode_commit_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002200 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07002201 &path[level].bp_ctxt);
2202 *bh = path[level].bp_ctxt.bh;
2203 }
2204
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09002205 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
2206 ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07002207
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002208 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
Koji Sato17c76b02009-04-06 19:01:24 -07002209 /* on-disk format */
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09002210 binfo->bi_dat.bi_blkoff = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -07002211 binfo->bi_dat.bi_level = level;
2212
2213 return 0;
2214}
2215
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002216static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002217 struct nilfs_btree_path *path,
2218 int level,
2219 struct buffer_head **bh,
2220 sector_t blocknr,
2221 union nilfs_binfo *binfo)
2222{
2223 struct nilfs_btree_node *parent;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002224 struct inode *dat = nilfs_bmap_get_dat(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07002225 __u64 key;
2226 __u64 ptr;
2227 union nilfs_bmap_ptr_req req;
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09002228 int ncmax, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07002229
Ryusuke Konishi9b7b2652010-07-13 23:33:53 +09002230 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2231 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2232 ncmax);
Koji Sato17c76b02009-04-06 19:01:24 -07002233 req.bpr_ptr = ptr;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002234 ret = nilfs_dat_prepare_start(dat, &req.bpr_req);
2235 if (ret < 0)
Koji Sato17c76b02009-04-06 19:01:24 -07002236 return ret;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002237 nilfs_dat_commit_start(dat, &req.bpr_req, blocknr);
Koji Sato17c76b02009-04-06 19:01:24 -07002238
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002239 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
Koji Sato17c76b02009-04-06 19:01:24 -07002240 /* on-disk format */
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09002241 binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr);
2242 binfo->bi_v.bi_blkoff = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -07002243
2244 return 0;
2245}
2246
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002247static int nilfs_btree_assign(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002248 struct buffer_head **bh,
2249 sector_t blocknr,
2250 union nilfs_binfo *binfo)
2251{
Koji Sato17c76b02009-04-06 19:01:24 -07002252 struct nilfs_btree_path *path;
2253 struct nilfs_btree_node *node;
2254 __u64 key;
2255 int level, ret;
2256
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002257 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07002258 if (path == NULL)
2259 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07002260
2261 if (buffer_nilfs_node(*bh)) {
2262 node = (struct nilfs_btree_node *)(*bh)->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002263 key = nilfs_btree_node_get_key(node, 0);
2264 level = nilfs_btree_node_get_level(node);
Koji Sato17c76b02009-04-06 19:01:24 -07002265 } else {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002266 key = nilfs_bmap_data_get_key(btree, *bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002267 level = NILFS_BTREE_LEVEL_DATA;
2268 }
2269
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +09002270 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07002271 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002272 WARN_ON(ret == -ENOENT);
Koji Sato17c76b02009-04-06 19:01:24 -07002273 goto out;
2274 }
2275
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002276 ret = NILFS_BMAP_USE_VBN(btree) ?
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09002277 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2278 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
Koji Sato17c76b02009-04-06 19:01:24 -07002279
2280 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002281 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07002282
2283 return ret;
2284}
2285
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002286static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002287 struct buffer_head **bh,
2288 sector_t blocknr,
2289 union nilfs_binfo *binfo)
2290{
Koji Sato17c76b02009-04-06 19:01:24 -07002291 struct nilfs_btree_node *node;
2292 __u64 key;
2293 int ret;
2294
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002295 ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002296 blocknr);
Koji Sato17c76b02009-04-06 19:01:24 -07002297 if (ret < 0)
2298 return ret;
2299
2300 if (buffer_nilfs_node(*bh)) {
2301 node = (struct nilfs_btree_node *)(*bh)->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002302 key = nilfs_btree_node_get_key(node, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07002303 } else
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002304 key = nilfs_bmap_data_get_key(btree, *bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002305
2306 /* on-disk format */
2307 binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr);
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09002308 binfo->bi_v.bi_blkoff = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -07002309
2310 return 0;
2311}
2312
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002313static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
Koji Sato17c76b02009-04-06 19:01:24 -07002314{
2315 struct buffer_head *bh;
Koji Sato17c76b02009-04-06 19:01:24 -07002316 struct nilfs_btree_path *path;
2317 __u64 ptr;
2318 int ret;
2319
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002320 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07002321 if (path == NULL)
2322 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07002323
Ryusuke Konishi03bdb5a2010-07-18 10:42:26 +09002324 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07002325 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002326 WARN_ON(ret == -ENOENT);
Koji Sato17c76b02009-04-06 19:01:24 -07002327 goto out;
2328 }
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09002329 ret = nilfs_btree_get_block(btree, ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002330 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002331 WARN_ON(ret == -ENOENT);
Koji Sato17c76b02009-04-06 19:01:24 -07002332 goto out;
2333 }
2334
2335 if (!buffer_dirty(bh))
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +09002336 mark_buffer_dirty(bh);
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09002337 brelse(bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002338 if (!nilfs_bmap_dirty(btree))
2339 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07002340
2341 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002342 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07002343 return ret;
2344}
2345
2346static const struct nilfs_bmap_operations nilfs_btree_ops = {
2347 .bop_lookup = nilfs_btree_lookup,
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +09002348 .bop_lookup_contig = nilfs_btree_lookup_contig,
Koji Sato17c76b02009-04-06 19:01:24 -07002349 .bop_insert = nilfs_btree_insert,
2350 .bop_delete = nilfs_btree_delete,
2351 .bop_clear = NULL,
2352
2353 .bop_propagate = nilfs_btree_propagate,
2354
2355 .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
2356
2357 .bop_assign = nilfs_btree_assign,
2358 .bop_mark = nilfs_btree_mark,
2359
Ryusuke Konishi5b203842015-04-16 12:46:36 -07002360 .bop_seek_key = nilfs_btree_seek_key,
Koji Sato17c76b02009-04-06 19:01:24 -07002361 .bop_last_key = nilfs_btree_last_key,
Ryusuke Konishi5b203842015-04-16 12:46:36 -07002362
Koji Sato17c76b02009-04-06 19:01:24 -07002363 .bop_check_insert = NULL,
2364 .bop_check_delete = nilfs_btree_check_delete,
2365 .bop_gather_data = nilfs_btree_gather_data,
2366};
2367
2368static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
2369 .bop_lookup = NULL,
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +09002370 .bop_lookup_contig = NULL,
Koji Sato17c76b02009-04-06 19:01:24 -07002371 .bop_insert = NULL,
2372 .bop_delete = NULL,
2373 .bop_clear = NULL,
2374
2375 .bop_propagate = nilfs_btree_propagate_gc,
2376
2377 .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
2378
2379 .bop_assign = nilfs_btree_assign_gc,
2380 .bop_mark = NULL,
2381
Ryusuke Konishi5b203842015-04-16 12:46:36 -07002382 .bop_seek_key = NULL,
Koji Sato17c76b02009-04-06 19:01:24 -07002383 .bop_last_key = NULL,
Ryusuke Konishi5b203842015-04-16 12:46:36 -07002384
Koji Sato17c76b02009-04-06 19:01:24 -07002385 .bop_check_insert = NULL,
2386 .bop_check_delete = NULL,
2387 .bop_gather_data = NULL,
2388};
2389
Ryusuke Konishi957ed602015-02-27 15:51:56 -08002390static void __nilfs_btree_init(struct nilfs_bmap *bmap)
Koji Sato17c76b02009-04-06 19:01:24 -07002391{
Koji Sato17c76b02009-04-06 19:01:24 -07002392 bmap->b_ops = &nilfs_btree_ops;
Ryusuke Konishi5ad2686e92010-07-13 23:33:54 +09002393 bmap->b_nchildren_per_block =
2394 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
Ryusuke Konishi957ed602015-02-27 15:51:56 -08002395}
2396
2397int nilfs_btree_init(struct nilfs_bmap *bmap)
2398{
2399 int ret = 0;
2400
2401 __nilfs_btree_init(bmap);
2402
2403 if (nilfs_btree_root_broken(nilfs_btree_get_root(bmap),
2404 bmap->b_inode->i_ino))
2405 ret = -EIO;
2406 return ret;
Koji Sato17c76b02009-04-06 19:01:24 -07002407}
2408
2409void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
2410{
Koji Sato17c76b02009-04-06 19:01:24 -07002411 bmap->b_ops = &nilfs_btree_ops_gc;
Ryusuke Konishi5ad2686e92010-07-13 23:33:54 +09002412 bmap->b_nchildren_per_block =
2413 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
Koji Sato17c76b02009-04-06 19:01:24 -07002414}