blob: c0266f7f0b268be5a717fd3f565cc371a79d8f23 [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
Li Hongf9054402010-04-02 17:36:34 +080034static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
Koji Sato17c76b02009-04-06 19:01:24 -070035{
Li Hongf9054402010-04-02 17:36:34 +080036 struct nilfs_btree_path *path;
37 int level = NILFS_BTREE_LEVEL_DATA;
Koji Sato17c76b02009-04-06 19:01:24 -070038
Li Hongf9054402010-04-02 17:36:34 +080039 path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
40 if (path == NULL)
41 goto out;
Koji Sato17c76b02009-04-06 19:01:24 -070042
Li Hongf9054402010-04-02 17:36:34 +080043 for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
Koji Sato17c76b02009-04-06 19:01:24 -070044 path[level].bp_bh = NULL;
45 path[level].bp_sib_bh = NULL;
46 path[level].bp_index = 0;
47 path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
48 path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
49 path[level].bp_op = NULL;
50 }
Li Hongf9054402010-04-02 17:36:34 +080051
52out:
53 return path;
54}
55
Li Hong73bb4882010-04-02 18:35:00 +080056static void nilfs_btree_free_path(struct nilfs_btree_path *path)
Li Hongf9054402010-04-02 17:36:34 +080057{
Li Hong73bb4882010-04-02 18:35:00 +080058 int level = NILFS_BTREE_LEVEL_DATA;
Koji Sato17c76b02009-04-06 19:01:24 -070059
Li Hong73bb4882010-04-02 18:35:00 +080060 for (; level < NILFS_BTREE_LEVEL_MAX; level++)
Ryusuke Konishi32189292009-08-15 01:54:59 +090061 brelse(path[level].bp_bh);
Li Hong73bb4882010-04-02 18:35:00 +080062
63 kmem_cache_free(nilfs_btree_path_cache, path);
Koji Sato17c76b02009-04-06 19:01:24 -070064}
65
Koji Sato17c76b02009-04-06 19:01:24 -070066/*
67 * B-tree node operations
68 */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +090069static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
Ryusuke Konishif198dbb2009-05-22 01:07:13 +090070 struct buffer_head **bhp)
71{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +090072 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +090073 struct buffer_head *bh;
Ryusuke Konishi1376e932009-11-13 16:49:09 +090074 int err;
75
76 err = nilfs_btnode_submit_block(btnc, ptr, 0, bhp);
77 if (err)
78 return err == -EEXIST ? 0 : err;
79
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +090080 bh = *bhp;
81 wait_on_buffer(bh);
82 if (!buffer_uptodate(bh)) {
83 brelse(bh);
Ryusuke Konishi1376e932009-11-13 16:49:09 +090084 return -EIO;
85 }
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +090086 if (nilfs_btree_broken_node_block(bh)) {
87 clear_buffer_uptodate(bh);
88 brelse(bh);
89 return -EINVAL;
90 }
Ryusuke Konishi1376e932009-11-13 16:49:09 +090091 return 0;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +090092}
93
Ryusuke Konishie7c274f2010-07-10 19:09:49 +090094static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
Ryusuke Konishif198dbb2009-05-22 01:07:13 +090095 __u64 ptr, struct buffer_head **bhp)
96{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +090097 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
Ryusuke Konishi45f49102009-11-13 16:25:19 +090098 struct buffer_head *bh;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +090099
Ryusuke Konishi45f49102009-11-13 16:25:19 +0900100 bh = nilfs_btnode_create_block(btnc, ptr);
101 if (!bh)
102 return -ENOMEM;
103
104 set_buffer_nilfs_volatile(bh);
105 *bhp = bh;
106 return 0;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +0900107}
Koji Sato17c76b02009-04-06 19:01:24 -0700108
109static inline int
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900110nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700111{
112 return node->bn_flags;
113}
114
115static inline void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900116nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
Koji Sato17c76b02009-04-06 19:01:24 -0700117{
118 node->bn_flags = flags;
119}
120
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900121static inline int nilfs_btree_node_root(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700122{
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900123 return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
Koji Sato17c76b02009-04-06 19:01:24 -0700124}
125
126static inline int
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900127nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700128{
129 return node->bn_level;
130}
131
132static inline void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900133nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
Koji Sato17c76b02009-04-06 19:01:24 -0700134{
135 node->bn_level = level;
136}
137
138static inline int
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900139nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700140{
141 return le16_to_cpu(node->bn_nchildren);
142}
143
144static inline void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900145nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
Koji Sato17c76b02009-04-06 19:01:24 -0700146{
147 node->bn_nchildren = cpu_to_le16(nchildren);
148}
149
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900150static inline int nilfs_btree_node_size(const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700151{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900152 return 1 << btree->b_inode->i_blkbits;
Koji Sato17c76b02009-04-06 19:01:24 -0700153}
154
155static inline int
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900156nilfs_btree_node_nchildren_min(const struct nilfs_btree_node *node,
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900157 const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700158{
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900159 return nilfs_btree_node_root(node) ?
Koji Sato17c76b02009-04-06 19:01:24 -0700160 NILFS_BTREE_ROOT_NCHILDREN_MIN :
161 NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
162}
163
164static inline int
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900165nilfs_btree_node_nchildren_max(const struct nilfs_btree_node *node,
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900166 const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700167{
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900168 return nilfs_btree_node_root(node) ?
Koji Sato17c76b02009-04-06 19:01:24 -0700169 NILFS_BTREE_ROOT_NCHILDREN_MAX :
170 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree));
171}
172
173static inline __le64 *
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900174nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
Koji Sato17c76b02009-04-06 19:01:24 -0700175{
176 return (__le64 *)((char *)(node + 1) +
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900177 (nilfs_btree_node_root(node) ?
Koji Sato17c76b02009-04-06 19:01:24 -0700178 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
179}
180
181static inline __le64 *
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900182nilfs_btree_node_dptrs(const struct nilfs_btree_node *node,
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900183 const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700184{
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900185 return (__le64 *)(nilfs_btree_node_dkeys(node) +
186 nilfs_btree_node_nchildren_max(node, btree));
Koji Sato17c76b02009-04-06 19:01:24 -0700187}
188
189static inline __u64
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900190nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
Koji Sato17c76b02009-04-06 19:01:24 -0700191{
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900192 return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
Koji Sato17c76b02009-04-06 19:01:24 -0700193}
194
195static inline void
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900196nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
Koji Sato17c76b02009-04-06 19:01:24 -0700197{
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900198 *(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -0700199}
200
201static inline __u64
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900202nilfs_btree_node_get_ptr(const struct nilfs_bmap *btree,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900203 const struct nilfs_btree_node *node, int index)
Koji Sato17c76b02009-04-06 19:01:24 -0700204{
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900205 return le64_to_cpu(*(nilfs_btree_node_dptrs(node, btree) + index));
Koji Sato17c76b02009-04-06 19:01:24 -0700206}
207
208static inline void
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900209nilfs_btree_node_set_ptr(struct nilfs_bmap *btree,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900210 struct nilfs_btree_node *node, int index, __u64 ptr)
Koji Sato17c76b02009-04-06 19:01:24 -0700211{
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900212 *(nilfs_btree_node_dptrs(node, btree) + index) = cpu_to_le64(ptr);
Koji Sato17c76b02009-04-06 19:01:24 -0700213}
214
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900215static void nilfs_btree_node_init(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700216 struct nilfs_btree_node *node,
217 int flags, int level, int nchildren,
218 const __u64 *keys, const __u64 *ptrs)
219{
220 __le64 *dkeys;
221 __le64 *dptrs;
222 int i;
223
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900224 nilfs_btree_node_set_flags(node, flags);
225 nilfs_btree_node_set_level(node, level);
226 nilfs_btree_node_set_nchildren(node, nchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700227
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900228 dkeys = nilfs_btree_node_dkeys(node);
229 dptrs = nilfs_btree_node_dptrs(node, btree);
Koji Sato17c76b02009-04-06 19:01:24 -0700230 for (i = 0; i < nchildren; i++) {
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900231 dkeys[i] = cpu_to_le64(keys[i]);
232 dptrs[i] = cpu_to_le64(ptrs[i]);
Koji Sato17c76b02009-04-06 19:01:24 -0700233 }
234}
235
236/* Assume the buffer heads corresponding to left and right are locked. */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900237static void nilfs_btree_node_move_left(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700238 struct nilfs_btree_node *left,
239 struct nilfs_btree_node *right,
240 int n)
241{
242 __le64 *ldkeys, *rdkeys;
243 __le64 *ldptrs, *rdptrs;
244 int lnchildren, rnchildren;
245
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900246 ldkeys = nilfs_btree_node_dkeys(left);
247 ldptrs = nilfs_btree_node_dptrs(left, btree);
248 lnchildren = nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -0700249
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900250 rdkeys = nilfs_btree_node_dkeys(right);
251 rdptrs = nilfs_btree_node_dptrs(right, btree);
252 rnchildren = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -0700253
254 memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
255 memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
256 memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
257 memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));
258
259 lnchildren += n;
260 rnchildren -= n;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900261 nilfs_btree_node_set_nchildren(left, lnchildren);
262 nilfs_btree_node_set_nchildren(right, rnchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700263}
264
265/* Assume that the buffer heads corresponding to left and right are locked. */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900266static void nilfs_btree_node_move_right(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700267 struct nilfs_btree_node *left,
268 struct nilfs_btree_node *right,
269 int n)
270{
271 __le64 *ldkeys, *rdkeys;
272 __le64 *ldptrs, *rdptrs;
273 int lnchildren, rnchildren;
274
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900275 ldkeys = nilfs_btree_node_dkeys(left);
276 ldptrs = nilfs_btree_node_dptrs(left, btree);
277 lnchildren = nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -0700278
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900279 rdkeys = nilfs_btree_node_dkeys(right);
280 rdptrs = nilfs_btree_node_dptrs(right, btree);
281 rnchildren = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -0700282
283 memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
284 memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
285 memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
286 memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));
287
288 lnchildren -= n;
289 rnchildren += n;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900290 nilfs_btree_node_set_nchildren(left, lnchildren);
291 nilfs_btree_node_set_nchildren(right, rnchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700292}
293
294/* Assume that the buffer head corresponding to node is locked. */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900295static void nilfs_btree_node_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700296 struct nilfs_btree_node *node,
297 __u64 key, __u64 ptr, int index)
298{
299 __le64 *dkeys;
300 __le64 *dptrs;
301 int nchildren;
302
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900303 dkeys = nilfs_btree_node_dkeys(node);
304 dptrs = nilfs_btree_node_dptrs(node, btree);
305 nchildren = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700306 if (index < nchildren) {
307 memmove(dkeys + index + 1, dkeys + index,
308 (nchildren - index) * sizeof(*dkeys));
309 memmove(dptrs + index + 1, dptrs + index,
310 (nchildren - index) * sizeof(*dptrs));
311 }
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900312 dkeys[index] = cpu_to_le64(key);
313 dptrs[index] = cpu_to_le64(ptr);
Koji Sato17c76b02009-04-06 19:01:24 -0700314 nchildren++;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900315 nilfs_btree_node_set_nchildren(node, nchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700316}
317
318/* Assume that the buffer head corresponding to node is locked. */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900319static void nilfs_btree_node_delete(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700320 struct nilfs_btree_node *node,
321 __u64 *keyp, __u64 *ptrp, int index)
322{
323 __u64 key;
324 __u64 ptr;
325 __le64 *dkeys;
326 __le64 *dptrs;
327 int nchildren;
328
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900329 dkeys = nilfs_btree_node_dkeys(node);
330 dptrs = nilfs_btree_node_dptrs(node, btree);
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +0900331 key = le64_to_cpu(dkeys[index]);
332 ptr = le64_to_cpu(dptrs[index]);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900333 nchildren = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700334 if (keyp != NULL)
335 *keyp = key;
336 if (ptrp != NULL)
337 *ptrp = ptr;
338
339 if (index < nchildren - 1) {
340 memmove(dkeys + index, dkeys + index + 1,
341 (nchildren - index - 1) * sizeof(*dkeys));
342 memmove(dptrs + index, dptrs + index + 1,
343 (nchildren - index - 1) * sizeof(*dptrs));
344 }
345 nchildren--;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900346 nilfs_btree_node_set_nchildren(node, nchildren);
Koji Sato17c76b02009-04-06 19:01:24 -0700347}
348
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900349static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
Koji Sato17c76b02009-04-06 19:01:24 -0700350 __u64 key, int *indexp)
351{
352 __u64 nkey;
353 int index, low, high, s;
354
355 /* binary search */
356 low = 0;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900357 high = nilfs_btree_node_get_nchildren(node) - 1;
Koji Sato17c76b02009-04-06 19:01:24 -0700358 index = 0;
359 s = 0;
360 while (low <= high) {
361 index = (low + high) / 2;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900362 nkey = nilfs_btree_node_get_key(node, index);
Koji Sato17c76b02009-04-06 19:01:24 -0700363 if (nkey == key) {
364 s = 0;
365 goto out;
366 } else if (nkey < key) {
367 low = index + 1;
368 s = -1;
369 } else {
370 high = index - 1;
371 s = 1;
372 }
373 }
374
375 /* adjust index */
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900376 if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
377 if (s > 0 && index > 0)
Koji Sato17c76b02009-04-06 19:01:24 -0700378 index--;
379 } else if (s < 0)
380 index++;
381
382 out:
Koji Sato17c76b02009-04-06 19:01:24 -0700383 *indexp = index;
384
385 return s == 0;
386}
387
Ryusuke Konishi1d5385b2010-07-16 23:52:40 +0900388/**
389 * nilfs_btree_node_broken - verify consistency of btree node
390 * @node: btree node block to be examined
391 * @size: node size (in bytes)
392 * @blocknr: block number
393 *
394 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
395 */
396static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
397 size_t size, sector_t blocknr)
398{
399 int level, flags, nchildren;
400 int ret = 0;
401
402 level = nilfs_btree_node_get_level(node);
403 flags = nilfs_btree_node_get_flags(node);
404 nchildren = nilfs_btree_node_get_nchildren(node);
405
406 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
407 level >= NILFS_BTREE_LEVEL_MAX ||
408 (flags & NILFS_BTREE_NODE_ROOT) ||
409 nchildren < 0 ||
410 nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
411 printk(KERN_CRIT "NILFS: bad btree node (blocknr=%llu): "
412 "level = %d, flags = 0x%x, nchildren = %d\n",
413 (unsigned long long)blocknr, level, flags, nchildren);
414 ret = 1;
415 }
416 return ret;
417}
418
419int nilfs_btree_broken_node_block(struct buffer_head *bh)
420{
421 return nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
422 bh->b_size, bh->b_blocknr);
423}
424
Koji Sato17c76b02009-04-06 19:01:24 -0700425static inline struct nilfs_btree_node *
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900426nilfs_btree_get_root(const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700427{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900428 return (struct nilfs_btree_node *)btree->b_u.u_data;
Koji Sato17c76b02009-04-06 19:01:24 -0700429}
430
431static inline struct nilfs_btree_node *
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900432nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
Koji Sato17c76b02009-04-06 19:01:24 -0700433{
434 return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
435}
436
437static inline struct nilfs_btree_node *
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900438nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
Koji Sato17c76b02009-04-06 19:01:24 -0700439{
440 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
441}
442
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900443static inline int nilfs_btree_height(const struct nilfs_bmap *btree)
Koji Sato17c76b02009-04-06 19:01:24 -0700444{
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900445 return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
Koji Sato17c76b02009-04-06 19:01:24 -0700446}
447
448static inline struct nilfs_btree_node *
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900449nilfs_btree_get_node(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700450 const struct nilfs_btree_path *path,
451 int level)
452{
453 return (level == nilfs_btree_height(btree) - 1) ?
454 nilfs_btree_get_root(btree) :
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900455 nilfs_btree_get_nonroot_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -0700456}
457
Ryusuke Konishi9b945d52009-10-10 22:58:10 +0900458static inline int
459nilfs_btree_bad_node(struct nilfs_btree_node *node, int level)
460{
461 if (unlikely(nilfs_btree_node_get_level(node) != level)) {
462 dump_stack();
463 printk(KERN_CRIT "NILFS: btree level mismatch: %d != %d\n",
464 nilfs_btree_node_get_level(node), level);
465 return 1;
466 }
467 return 0;
468}
469
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900470static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700471 struct nilfs_btree_path *path,
472 __u64 key, __u64 *ptrp, int minlevel)
473{
474 struct nilfs_btree_node *node;
475 __u64 ptr;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900476 int level, index, found, ncmax, ret;
Koji Sato17c76b02009-04-06 19:01:24 -0700477
Koji Sato17c76b02009-04-06 19:01:24 -0700478 node = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900479 level = nilfs_btree_node_get_level(node);
480 if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
Koji Sato17c76b02009-04-06 19:01:24 -0700481 return -ENOENT;
482
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900483 found = nilfs_btree_node_lookup(node, key, &index);
Koji Sato17c76b02009-04-06 19:01:24 -0700484 ptr = nilfs_btree_node_get_ptr(btree, node, index);
485 path[level].bp_bh = NULL;
486 path[level].bp_index = index;
487
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900488 ncmax = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree));
489
Koji Sato17c76b02009-04-06 19:01:24 -0700490 for (level--; level >= minlevel; level--) {
Ryusuke Konishif198dbb2009-05-22 01:07:13 +0900491 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700492 if (ret < 0)
493 return ret;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900494 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b945d52009-10-10 22:58:10 +0900495 if (nilfs_btree_bad_node(node, level))
496 return -EINVAL;
Koji Sato17c76b02009-04-06 19:01:24 -0700497 if (!found)
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900498 found = nilfs_btree_node_lookup(node, key, &index);
Koji Sato17c76b02009-04-06 19:01:24 -0700499 else
500 index = 0;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900501 if (index < ncmax) {
Koji Sato17c76b02009-04-06 19:01:24 -0700502 ptr = nilfs_btree_node_get_ptr(btree, node, index);
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900503 } else {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -0700504 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
Koji Sato17c76b02009-04-06 19:01:24 -0700505 /* insert */
506 ptr = NILFS_BMAP_INVALID_PTR;
507 }
508 path[level].bp_index = index;
509 }
510 if (!found)
511 return -ENOENT;
512
513 if (ptrp != NULL)
514 *ptrp = ptr;
515
516 return 0;
517}
518
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900519static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700520 struct nilfs_btree_path *path,
521 __u64 *keyp, __u64 *ptrp)
522{
523 struct nilfs_btree_node *node;
524 __u64 ptr;
525 int index, level, ret;
526
527 node = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900528 index = nilfs_btree_node_get_nchildren(node) - 1;
Koji Sato17c76b02009-04-06 19:01:24 -0700529 if (index < 0)
530 return -ENOENT;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900531 level = nilfs_btree_node_get_level(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700532 ptr = nilfs_btree_node_get_ptr(btree, node, index);
533 path[level].bp_bh = NULL;
534 path[level].bp_index = index;
535
536 for (level--; level > 0; level--) {
Ryusuke Konishif198dbb2009-05-22 01:07:13 +0900537 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700538 if (ret < 0)
539 return ret;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900540 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishi9b945d52009-10-10 22:58:10 +0900541 if (nilfs_btree_bad_node(node, level))
542 return -EINVAL;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900543 index = nilfs_btree_node_get_nchildren(node) - 1;
Koji Sato17c76b02009-04-06 19:01:24 -0700544 ptr = nilfs_btree_node_get_ptr(btree, node, index);
545 path[level].bp_index = index;
546 }
547
548 if (keyp != NULL)
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900549 *keyp = nilfs_btree_node_get_key(node, index);
Koji Sato17c76b02009-04-06 19:01:24 -0700550 if (ptrp != NULL)
551 *ptrp = ptr;
552
553 return 0;
554}
555
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900556static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700557 __u64 key, int level, __u64 *ptrp)
558{
Koji Sato17c76b02009-04-06 19:01:24 -0700559 struct nilfs_btree_path *path;
Koji Sato17c76b02009-04-06 19:01:24 -0700560 int ret;
561
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900562 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -0700563 if (path == NULL)
564 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -0700565
Ryusuke Konishi364ec2d2010-07-13 23:33:51 +0900566 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level);
Koji Sato17c76b02009-04-06 19:01:24 -0700567
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900568 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -0700569
570 return ret;
571}
572
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900573static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900574 __u64 key, __u64 *ptrp, unsigned maxblocks)
575{
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900576 struct nilfs_btree_path *path;
577 struct nilfs_btree_node *node;
578 struct inode *dat = NULL;
579 __u64 ptr, ptr2;
580 sector_t blocknr;
581 int level = NILFS_BTREE_LEVEL_NODE_MIN;
582 int ret, cnt, index, maxlevel;
583
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900584 path = nilfs_btree_alloc_path();
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900585 if (path == NULL)
586 return -ENOMEM;
Li Hongf9054402010-04-02 17:36:34 +0800587
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900588 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level);
589 if (ret < 0)
590 goto out;
591
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900592 if (NILFS_BMAP_USE_VBN(btree)) {
593 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900594 ret = nilfs_dat_translate(dat, ptr, &blocknr);
595 if (ret < 0)
596 goto out;
597 ptr = blocknr;
598 }
599 cnt = 1;
600 if (cnt == maxblocks)
601 goto end;
602
603 maxlevel = nilfs_btree_height(btree) - 1;
604 node = nilfs_btree_get_node(btree, path, level);
605 index = path[level].bp_index + 1;
606 for (;;) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900607 while (index < nilfs_btree_node_get_nchildren(node)) {
608 if (nilfs_btree_node_get_key(node, index) !=
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900609 key + cnt)
610 goto end;
611 ptr2 = nilfs_btree_node_get_ptr(btree, node, index);
612 if (dat) {
613 ret = nilfs_dat_translate(dat, ptr2, &blocknr);
614 if (ret < 0)
615 goto out;
616 ptr2 = blocknr;
617 }
618 if (ptr2 != ptr + cnt || ++cnt == maxblocks)
619 goto end;
620 index++;
621 continue;
622 }
623 if (level == maxlevel)
624 break;
625
626 /* look-up right sibling node */
627 node = nilfs_btree_get_node(btree, path, level + 1);
628 index = path[level + 1].bp_index + 1;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900629 if (index >= nilfs_btree_node_get_nchildren(node) ||
630 nilfs_btree_node_get_key(node, index) != key + cnt)
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900631 break;
632 ptr2 = nilfs_btree_node_get_ptr(btree, node, index);
633 path[level + 1].bp_index = index;
634
635 brelse(path[level].bp_bh);
636 path[level].bp_bh = NULL;
637 ret = nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh);
638 if (ret < 0)
639 goto out;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900640 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900641 index = 0;
642 path[level].bp_index = index;
643 }
644 end:
645 *ptrp = ptr;
646 ret = cnt;
647 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900648 nilfs_btree_free_path(path);
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +0900649 return ret;
650}
651
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900652static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700653 struct nilfs_btree_path *path,
654 int level, __u64 key)
655{
656 if (level < nilfs_btree_height(btree) - 1) {
657 do {
Koji Sato17c76b02009-04-06 19:01:24 -0700658 nilfs_btree_node_set_key(
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900659 nilfs_btree_get_nonroot_node(path, level),
Koji Sato17c76b02009-04-06 19:01:24 -0700660 path[level].bp_index, key);
661 if (!buffer_dirty(path[level].bp_bh))
662 nilfs_btnode_mark_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700663 } while ((path[level].bp_index == 0) &&
664 (++level < nilfs_btree_height(btree) - 1));
665 }
666
667 /* root */
668 if (level == nilfs_btree_height(btree) - 1) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900669 nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
Koji Sato17c76b02009-04-06 19:01:24 -0700670 path[level].bp_index, key);
671 }
672}
673
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900674static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700675 struct nilfs_btree_path *path,
676 int level, __u64 *keyp, __u64 *ptrp)
677{
678 struct nilfs_btree_node *node;
679
680 if (level < nilfs_btree_height(btree) - 1) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900681 node = nilfs_btree_get_nonroot_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -0700682 nilfs_btree_node_insert(btree, node, *keyp, *ptrp,
683 path[level].bp_index);
684 if (!buffer_dirty(path[level].bp_bh))
685 nilfs_btnode_mark_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700686
687 if (path[level].bp_index == 0)
688 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900689 nilfs_btree_node_get_key(node,
690 0));
Koji Sato17c76b02009-04-06 19:01:24 -0700691 } else {
692 node = nilfs_btree_get_root(btree);
693 nilfs_btree_node_insert(btree, node, *keyp, *ptrp,
694 path[level].bp_index);
695 }
696}
697
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900698static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700699 struct nilfs_btree_path *path,
700 int level, __u64 *keyp, __u64 *ptrp)
701{
702 struct nilfs_btree_node *node, *left;
703 int nchildren, lnchildren, n, move;
704
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900705 node = nilfs_btree_get_nonroot_node(path, level);
706 left = nilfs_btree_get_sib_node(path, level);
707 nchildren = nilfs_btree_node_get_nchildren(node);
708 lnchildren = nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -0700709 move = 0;
710
711 n = (nchildren + lnchildren + 1) / 2 - lnchildren;
712 if (n > path[level].bp_index) {
713 /* move insert point */
714 n--;
715 move = 1;
716 }
717
718 nilfs_btree_node_move_left(btree, left, node, n);
719
720 if (!buffer_dirty(path[level].bp_bh))
721 nilfs_btnode_mark_dirty(path[level].bp_bh);
722 if (!buffer_dirty(path[level].bp_sib_bh))
723 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
724
Koji Sato17c76b02009-04-06 19:01:24 -0700725 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900726 nilfs_btree_node_get_key(node, 0));
Koji Sato17c76b02009-04-06 19:01:24 -0700727
728 if (move) {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900729 brelse(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700730 path[level].bp_bh = path[level].bp_sib_bh;
731 path[level].bp_sib_bh = NULL;
732 path[level].bp_index += lnchildren;
733 path[level + 1].bp_index--;
734 } else {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900735 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700736 path[level].bp_sib_bh = NULL;
737 path[level].bp_index -= n;
738 }
739
740 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
741}
742
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900743static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700744 struct nilfs_btree_path *path,
745 int level, __u64 *keyp, __u64 *ptrp)
746{
747 struct nilfs_btree_node *node, *right;
748 int nchildren, rnchildren, n, move;
749
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900750 node = nilfs_btree_get_nonroot_node(path, level);
751 right = nilfs_btree_get_sib_node(path, level);
752 nchildren = nilfs_btree_node_get_nchildren(node);
753 rnchildren = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -0700754 move = 0;
755
756 n = (nchildren + rnchildren + 1) / 2 - rnchildren;
757 if (n > nchildren - path[level].bp_index) {
758 /* move insert point */
759 n--;
760 move = 1;
761 }
762
763 nilfs_btree_node_move_right(btree, node, right, n);
764
765 if (!buffer_dirty(path[level].bp_bh))
766 nilfs_btnode_mark_dirty(path[level].bp_bh);
767 if (!buffer_dirty(path[level].bp_sib_bh))
768 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
769
Koji Sato17c76b02009-04-06 19:01:24 -0700770 path[level + 1].bp_index++;
771 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900772 nilfs_btree_node_get_key(right, 0));
Koji Sato17c76b02009-04-06 19:01:24 -0700773 path[level + 1].bp_index--;
774
775 if (move) {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900776 brelse(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700777 path[level].bp_bh = path[level].bp_sib_bh;
778 path[level].bp_sib_bh = NULL;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900779 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700780 path[level + 1].bp_index++;
781 } else {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900782 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700783 path[level].bp_sib_bh = NULL;
784 }
785
786 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
787}
788
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900789static void nilfs_btree_split(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700790 struct nilfs_btree_path *path,
791 int level, __u64 *keyp, __u64 *ptrp)
792{
793 struct nilfs_btree_node *node, *right;
794 __u64 newkey;
795 __u64 newptr;
796 int nchildren, n, move;
797
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900798 node = nilfs_btree_get_nonroot_node(path, level);
799 right = nilfs_btree_get_sib_node(path, level);
800 nchildren = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700801 move = 0;
802
803 n = (nchildren + 1) / 2;
804 if (n > nchildren - path[level].bp_index) {
805 n--;
806 move = 1;
807 }
808
809 nilfs_btree_node_move_right(btree, node, right, n);
810
811 if (!buffer_dirty(path[level].bp_bh))
812 nilfs_btnode_mark_dirty(path[level].bp_bh);
813 if (!buffer_dirty(path[level].bp_sib_bh))
814 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
815
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900816 newkey = nilfs_btree_node_get_key(right, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700817 newptr = path[level].bp_newreq.bpr_ptr;
818
819 if (move) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900820 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -0700821 nilfs_btree_node_insert(btree, right, *keyp, *ptrp,
822 path[level].bp_index);
823
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900824 *keyp = nilfs_btree_node_get_key(right, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700825 *ptrp = path[level].bp_newreq.bpr_ptr;
826
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900827 brelse(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700828 path[level].bp_bh = path[level].bp_sib_bh;
829 path[level].bp_sib_bh = NULL;
830 } else {
831 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
832
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900833 *keyp = nilfs_btree_node_get_key(right, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700834 *ptrp = path[level].bp_newreq.bpr_ptr;
835
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900836 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700837 path[level].bp_sib_bh = NULL;
838 }
839
840 path[level + 1].bp_index++;
841}
842
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900843static void nilfs_btree_grow(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700844 struct nilfs_btree_path *path,
845 int level, __u64 *keyp, __u64 *ptrp)
846{
847 struct nilfs_btree_node *root, *child;
848 int n;
849
Koji Sato17c76b02009-04-06 19:01:24 -0700850 root = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900851 child = nilfs_btree_get_sib_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -0700852
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900853 n = nilfs_btree_node_get_nchildren(root);
Koji Sato17c76b02009-04-06 19:01:24 -0700854
855 nilfs_btree_node_move_right(btree, root, child, n);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900856 nilfs_btree_node_set_level(root, level + 1);
Koji Sato17c76b02009-04-06 19:01:24 -0700857
858 if (!buffer_dirty(path[level].bp_sib_bh))
859 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
860
Koji Sato17c76b02009-04-06 19:01:24 -0700861 path[level].bp_bh = path[level].bp_sib_bh;
862 path[level].bp_sib_bh = NULL;
863
864 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
865
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900866 *keyp = nilfs_btree_node_get_key(child, 0);
Koji Sato17c76b02009-04-06 19:01:24 -0700867 *ptrp = path[level].bp_newreq.bpr_ptr;
868}
869
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900870static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700871 const struct nilfs_btree_path *path)
872{
873 struct nilfs_btree_node *node;
874 int level;
875
876 if (path == NULL)
877 return NILFS_BMAP_INVALID_PTR;
878
879 /* left sibling */
880 level = NILFS_BTREE_LEVEL_NODE_MIN;
881 if (path[level].bp_index > 0) {
882 node = nilfs_btree_get_node(btree, path, level);
883 return nilfs_btree_node_get_ptr(btree, node,
884 path[level].bp_index - 1);
885 }
886
887 /* parent */
888 level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
889 if (level <= nilfs_btree_height(btree) - 1) {
890 node = nilfs_btree_get_node(btree, path, level);
891 return nilfs_btree_node_get_ptr(btree, node,
892 path[level].bp_index);
893 }
894
895 return NILFS_BMAP_INVALID_PTR;
896}
897
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900898static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700899 const struct nilfs_btree_path *path,
900 __u64 key)
901{
902 __u64 ptr;
903
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900904 ptr = nilfs_bmap_find_target_seq(btree, key);
Koji Sato17c76b02009-04-06 19:01:24 -0700905 if (ptr != NILFS_BMAP_INVALID_PTR)
906 /* sequential access */
907 return ptr;
908 else {
909 ptr = nilfs_btree_find_near(btree, path);
910 if (ptr != NILFS_BMAP_INVALID_PTR)
911 /* near */
912 return ptr;
913 }
914 /* block group */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900915 return nilfs_bmap_find_target_in_group(btree);
Koji Sato17c76b02009-04-06 19:01:24 -0700916}
917
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900918static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -0700919 struct nilfs_btree_path *path,
920 int *levelp, __u64 key, __u64 ptr,
921 struct nilfs_bmap_stats *stats)
922{
923 struct buffer_head *bh;
924 struct nilfs_btree_node *node, *parent, *sib;
925 __u64 sibptr;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900926 int pindex, level, ncmax, ret;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +0900927 struct inode *dat = NULL;
Koji Sato17c76b02009-04-06 19:01:24 -0700928
929 stats->bs_nblocks = 0;
930 level = NILFS_BTREE_LEVEL_DATA;
931
932 /* allocate a new ptr for data block */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900933 if (NILFS_BMAP_USE_VBN(btree)) {
Koji Sato17c76b02009-04-06 19:01:24 -0700934 path[level].bp_newreq.bpr_ptr =
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +0900935 nilfs_btree_find_target_v(btree, path, key);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900936 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +0900937 }
Koji Sato17c76b02009-04-06 19:01:24 -0700938
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900939 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -0700940 if (ret < 0)
941 goto err_out_data;
942
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900943 ncmax = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree));
944
Koji Sato17c76b02009-04-06 19:01:24 -0700945 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
946 level < nilfs_btree_height(btree) - 1;
947 level++) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900948 node = nilfs_btree_get_nonroot_node(path, level);
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900949 if (nilfs_btree_node_get_nchildren(node) < ncmax) {
Koji Sato17c76b02009-04-06 19:01:24 -0700950 path[level].bp_op = nilfs_btree_do_insert;
951 stats->bs_nblocks++;
952 goto out;
953 }
954
955 parent = nilfs_btree_get_node(btree, path, level + 1);
956 pindex = path[level + 1].bp_index;
957
958 /* left sibling */
959 if (pindex > 0) {
960 sibptr = nilfs_btree_node_get_ptr(btree, parent,
961 pindex - 1);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +0900962 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700963 if (ret < 0)
964 goto err_out_child_node;
965 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900966 if (nilfs_btree_node_get_nchildren(sib) < ncmax) {
Koji Sato17c76b02009-04-06 19:01:24 -0700967 path[level].bp_sib_bh = bh;
968 path[level].bp_op = nilfs_btree_carry_left;
969 stats->bs_nblocks++;
970 goto out;
971 } else
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900972 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700973 }
974
975 /* right sibling */
976 if (pindex <
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +0900977 nilfs_btree_node_get_nchildren(parent) - 1) {
Koji Sato17c76b02009-04-06 19:01:24 -0700978 sibptr = nilfs_btree_node_get_ptr(btree, parent,
979 pindex + 1);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +0900980 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700981 if (ret < 0)
982 goto err_out_child_node;
983 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +0900984 if (nilfs_btree_node_get_nchildren(sib) < ncmax) {
Koji Sato17c76b02009-04-06 19:01:24 -0700985 path[level].bp_sib_bh = bh;
986 path[level].bp_op = nilfs_btree_carry_right;
987 stats->bs_nblocks++;
988 goto out;
989 } else
Ryusuke Konishi087d01b2009-05-22 00:33:13 +0900990 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -0700991 }
992
993 /* split */
994 path[level].bp_newreq.bpr_ptr =
995 path[level - 1].bp_newreq.bpr_ptr + 1;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +0900996 ret = nilfs_bmap_prepare_alloc_ptr(btree,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +0900997 &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -0700998 if (ret < 0)
999 goto err_out_child_node;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001000 ret = nilfs_btree_get_new_block(btree,
1001 path[level].bp_newreq.bpr_ptr,
1002 &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001003 if (ret < 0)
1004 goto err_out_curr_node;
1005
1006 stats->bs_nblocks++;
1007
Koji Sato17c76b02009-04-06 19:01:24 -07001008 nilfs_btree_node_init(btree,
1009 (struct nilfs_btree_node *)bh->b_data,
1010 0, level, 0, NULL, NULL);
Koji Sato17c76b02009-04-06 19:01:24 -07001011 path[level].bp_sib_bh = bh;
1012 path[level].bp_op = nilfs_btree_split;
1013 }
1014
1015 /* root */
1016 node = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001017 if (nilfs_btree_node_get_nchildren(node) <
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001018 NILFS_BTREE_ROOT_NCHILDREN_MAX) {
Koji Sato17c76b02009-04-06 19:01:24 -07001019 path[level].bp_op = nilfs_btree_do_insert;
1020 stats->bs_nblocks++;
1021 goto out;
1022 }
1023
1024 /* grow */
1025 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001026 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001027 if (ret < 0)
1028 goto err_out_child_node;
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001029 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1030 &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001031 if (ret < 0)
1032 goto err_out_curr_node;
1033
Koji Sato17c76b02009-04-06 19:01:24 -07001034 nilfs_btree_node_init(btree, (struct nilfs_btree_node *)bh->b_data,
1035 0, level, 0, NULL, NULL);
Koji Sato17c76b02009-04-06 19:01:24 -07001036 path[level].bp_sib_bh = bh;
1037 path[level].bp_op = nilfs_btree_grow;
1038
1039 level++;
1040 path[level].bp_op = nilfs_btree_do_insert;
1041
1042 /* a newly-created node block and a data block are added */
1043 stats->bs_nblocks += 2;
1044
1045 /* success */
1046 out:
1047 *levelp = level;
1048 return ret;
1049
1050 /* error */
1051 err_out_curr_node:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001052 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001053 err_out_child_node:
1054 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001055 nilfs_btnode_delete(path[level].bp_sib_bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001056 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001057
1058 }
1059
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001060 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001061 err_out_data:
1062 *levelp = level;
1063 stats->bs_nblocks = 0;
1064 return ret;
1065}
1066
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001067static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001068 struct nilfs_btree_path *path,
1069 int maxlevel, __u64 key, __u64 ptr)
1070{
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001071 struct inode *dat = NULL;
Koji Sato17c76b02009-04-06 19:01:24 -07001072 int level;
1073
1074 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1075 ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001076 if (NILFS_BMAP_USE_VBN(btree)) {
Ryusuke Konishidc935be2010-07-10 22:21:54 +09001077 nilfs_bmap_set_target_v(btree, key, ptr);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001078 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001079 }
Koji Sato17c76b02009-04-06 19:01:24 -07001080
1081 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001082 nilfs_bmap_commit_alloc_ptr(btree,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001083 &path[level - 1].bp_newreq, dat);
Pekka Enberg8acfbf02009-04-06 19:01:49 -07001084 path[level].bp_op(btree, path, level, &key, &ptr);
Koji Sato17c76b02009-04-06 19:01:24 -07001085 }
1086
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001087 if (!nilfs_bmap_dirty(btree))
1088 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001089}
1090
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001091static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
Koji Sato17c76b02009-04-06 19:01:24 -07001092{
Koji Sato17c76b02009-04-06 19:01:24 -07001093 struct nilfs_btree_path *path;
1094 struct nilfs_bmap_stats stats;
1095 int level, ret;
1096
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001097 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07001098 if (path == NULL)
1099 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07001100
1101 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1102 NILFS_BTREE_LEVEL_NODE_MIN);
1103 if (ret != -ENOENT) {
1104 if (ret == 0)
1105 ret = -EEXIST;
1106 goto out;
1107 }
1108
1109 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1110 if (ret < 0)
1111 goto out;
1112 nilfs_btree_commit_insert(btree, path, level, key, ptr);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001113 nilfs_bmap_add_blocks(btree, stats.bs_nblocks);
Koji Sato17c76b02009-04-06 19:01:24 -07001114
1115 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001116 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07001117 return ret;
1118}
1119
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001120static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001121 struct nilfs_btree_path *path,
1122 int level, __u64 *keyp, __u64 *ptrp)
1123{
1124 struct nilfs_btree_node *node;
1125
1126 if (level < nilfs_btree_height(btree) - 1) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001127 node = nilfs_btree_get_nonroot_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -07001128 nilfs_btree_node_delete(btree, node, keyp, ptrp,
1129 path[level].bp_index);
1130 if (!buffer_dirty(path[level].bp_bh))
1131 nilfs_btnode_mark_dirty(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001132 if (path[level].bp_index == 0)
1133 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001134 nilfs_btree_node_get_key(node, 0));
Koji Sato17c76b02009-04-06 19:01:24 -07001135 } else {
1136 node = nilfs_btree_get_root(btree);
1137 nilfs_btree_node_delete(btree, node, keyp, ptrp,
1138 path[level].bp_index);
1139 }
1140}
1141
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001142static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001143 struct nilfs_btree_path *path,
1144 int level, __u64 *keyp, __u64 *ptrp)
1145{
1146 struct nilfs_btree_node *node, *left;
1147 int nchildren, lnchildren, n;
1148
1149 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1150
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001151 node = nilfs_btree_get_nonroot_node(path, level);
1152 left = nilfs_btree_get_sib_node(path, level);
1153 nchildren = nilfs_btree_node_get_nchildren(node);
1154 lnchildren = nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -07001155
1156 n = (nchildren + lnchildren) / 2 - nchildren;
1157
1158 nilfs_btree_node_move_right(btree, left, node, n);
1159
1160 if (!buffer_dirty(path[level].bp_bh))
1161 nilfs_btnode_mark_dirty(path[level].bp_bh);
1162 if (!buffer_dirty(path[level].bp_sib_bh))
1163 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
1164
Koji Sato17c76b02009-04-06 19:01:24 -07001165 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001166 nilfs_btree_node_get_key(node, 0));
Koji Sato17c76b02009-04-06 19:01:24 -07001167
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001168 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001169 path[level].bp_sib_bh = NULL;
1170 path[level].bp_index += n;
1171}
1172
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001173static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001174 struct nilfs_btree_path *path,
1175 int level, __u64 *keyp, __u64 *ptrp)
1176{
1177 struct nilfs_btree_node *node, *right;
1178 int nchildren, rnchildren, n;
1179
1180 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1181
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001182 node = nilfs_btree_get_nonroot_node(path, level);
1183 right = nilfs_btree_get_sib_node(path, level);
1184 nchildren = nilfs_btree_node_get_nchildren(node);
1185 rnchildren = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -07001186
1187 n = (nchildren + rnchildren) / 2 - nchildren;
1188
1189 nilfs_btree_node_move_left(btree, node, right, n);
1190
1191 if (!buffer_dirty(path[level].bp_bh))
1192 nilfs_btnode_mark_dirty(path[level].bp_bh);
1193 if (!buffer_dirty(path[level].bp_sib_bh))
1194 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
1195
Koji Sato17c76b02009-04-06 19:01:24 -07001196 path[level + 1].bp_index++;
1197 nilfs_btree_promote_key(btree, path, level + 1,
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001198 nilfs_btree_node_get_key(right, 0));
Koji Sato17c76b02009-04-06 19:01:24 -07001199 path[level + 1].bp_index--;
1200
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001201 brelse(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001202 path[level].bp_sib_bh = NULL;
1203}
1204
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001205static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001206 struct nilfs_btree_path *path,
1207 int level, __u64 *keyp, __u64 *ptrp)
1208{
1209 struct nilfs_btree_node *node, *left;
1210 int n;
1211
1212 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1213
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001214 node = nilfs_btree_get_nonroot_node(path, level);
1215 left = nilfs_btree_get_sib_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -07001216
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001217 n = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -07001218
1219 nilfs_btree_node_move_left(btree, left, node, n);
1220
1221 if (!buffer_dirty(path[level].bp_sib_bh))
1222 nilfs_btnode_mark_dirty(path[level].bp_sib_bh);
1223
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001224 nilfs_btnode_delete(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001225 path[level].bp_bh = path[level].bp_sib_bh;
1226 path[level].bp_sib_bh = NULL;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001227 path[level].bp_index += nilfs_btree_node_get_nchildren(left);
Koji Sato17c76b02009-04-06 19:01:24 -07001228}
1229
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001230static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001231 struct nilfs_btree_path *path,
1232 int level, __u64 *keyp, __u64 *ptrp)
1233{
1234 struct nilfs_btree_node *node, *right;
1235 int n;
1236
1237 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1238
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001239 node = nilfs_btree_get_nonroot_node(path, level);
1240 right = nilfs_btree_get_sib_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -07001241
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001242 n = nilfs_btree_node_get_nchildren(right);
Koji Sato17c76b02009-04-06 19:01:24 -07001243
1244 nilfs_btree_node_move_left(btree, node, right, n);
1245
1246 if (!buffer_dirty(path[level].bp_bh))
1247 nilfs_btnode_mark_dirty(path[level].bp_bh);
1248
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001249 nilfs_btnode_delete(path[level].bp_sib_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001250 path[level].bp_sib_bh = NULL;
1251 path[level + 1].bp_index++;
1252}
1253
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001254static void nilfs_btree_shrink(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001255 struct nilfs_btree_path *path,
1256 int level, __u64 *keyp, __u64 *ptrp)
1257{
1258 struct nilfs_btree_node *root, *child;
1259 int n;
1260
1261 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1262
Koji Sato17c76b02009-04-06 19:01:24 -07001263 root = nilfs_btree_get_root(btree);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001264 child = nilfs_btree_get_nonroot_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -07001265
1266 nilfs_btree_node_delete(btree, root, NULL, NULL, 0);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001267 nilfs_btree_node_set_level(root, level);
1268 n = nilfs_btree_node_get_nchildren(child);
Koji Sato17c76b02009-04-06 19:01:24 -07001269 nilfs_btree_node_move_left(btree, root, child, n);
Koji Sato17c76b02009-04-06 19:01:24 -07001270
Ryusuke Konishi9f098902009-05-22 00:38:56 +09001271 nilfs_btnode_delete(path[level].bp_bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001272 path[level].bp_bh = NULL;
1273}
1274
1275
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001276static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001277 struct nilfs_btree_path *path,
1278 int *levelp,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001279 struct nilfs_bmap_stats *stats,
1280 struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001281{
1282 struct buffer_head *bh;
1283 struct nilfs_btree_node *node, *parent, *sib;
1284 __u64 sibptr;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001285 int pindex, level, ncmin, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07001286
1287 ret = 0;
1288 stats->bs_nblocks = 0;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001289 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1290
Koji Sato17c76b02009-04-06 19:01:24 -07001291 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
1292 level < nilfs_btree_height(btree) - 1;
1293 level++) {
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001294 node = nilfs_btree_get_nonroot_node(path, level);
Koji Sato17c76b02009-04-06 19:01:24 -07001295 path[level].bp_oldreq.bpr_ptr =
1296 nilfs_btree_node_get_ptr(btree, node,
1297 path[level].bp_index);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001298 ret = nilfs_bmap_prepare_end_ptr(btree,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001299 &path[level].bp_oldreq, dat);
Ryusuke Konishid4b96152009-05-24 03:25:44 +09001300 if (ret < 0)
1301 goto err_out_child_node;
Koji Sato17c76b02009-04-06 19:01:24 -07001302
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001303 if (nilfs_btree_node_get_nchildren(node) > ncmin) {
Koji Sato17c76b02009-04-06 19:01:24 -07001304 path[level].bp_op = nilfs_btree_do_delete;
1305 stats->bs_nblocks++;
1306 goto out;
1307 }
1308
1309 parent = nilfs_btree_get_node(btree, path, level + 1);
1310 pindex = path[level + 1].bp_index;
1311
1312 if (pindex > 0) {
1313 /* left sibling */
1314 sibptr = nilfs_btree_node_get_ptr(btree, parent,
1315 pindex - 1);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001316 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001317 if (ret < 0)
1318 goto err_out_curr_node;
1319 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001320 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
Koji Sato17c76b02009-04-06 19:01:24 -07001321 path[level].bp_sib_bh = bh;
1322 path[level].bp_op = nilfs_btree_borrow_left;
1323 stats->bs_nblocks++;
1324 goto out;
1325 } else {
1326 path[level].bp_sib_bh = bh;
1327 path[level].bp_op = nilfs_btree_concat_left;
1328 stats->bs_nblocks++;
1329 /* continue; */
1330 }
1331 } else if (pindex <
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001332 nilfs_btree_node_get_nchildren(parent) - 1) {
Koji Sato17c76b02009-04-06 19:01:24 -07001333 /* right sibling */
1334 sibptr = nilfs_btree_node_get_ptr(btree, parent,
1335 pindex + 1);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001336 ret = nilfs_btree_get_block(btree, sibptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001337 if (ret < 0)
1338 goto err_out_curr_node;
1339 sib = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishiea64ab82010-07-13 23:33:52 +09001340 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
Koji Sato17c76b02009-04-06 19:01:24 -07001341 path[level].bp_sib_bh = bh;
1342 path[level].bp_op = nilfs_btree_borrow_right;
1343 stats->bs_nblocks++;
1344 goto out;
1345 } else {
1346 path[level].bp_sib_bh = bh;
1347 path[level].bp_op = nilfs_btree_concat_right;
1348 stats->bs_nblocks++;
1349 /* continue; */
1350 }
1351 } else {
1352 /* no siblings */
1353 /* the only child of the root node */
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001354 WARN_ON(level != nilfs_btree_height(btree) - 2);
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001355 if (nilfs_btree_node_get_nchildren(node) - 1 <=
Koji Sato17c76b02009-04-06 19:01:24 -07001356 NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1357 path[level].bp_op = nilfs_btree_shrink;
1358 stats->bs_nblocks += 2;
1359 } else {
1360 path[level].bp_op = nilfs_btree_do_delete;
1361 stats->bs_nblocks++;
1362 }
1363
1364 goto out;
1365
1366 }
1367 }
1368
1369 node = nilfs_btree_get_root(btree);
1370 path[level].bp_oldreq.bpr_ptr =
1371 nilfs_btree_node_get_ptr(btree, node, path[level].bp_index);
Ryusuke Konishid4b96152009-05-24 03:25:44 +09001372
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001373 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
Ryusuke Konishid4b96152009-05-24 03:25:44 +09001374 if (ret < 0)
1375 goto err_out_child_node;
1376
Koji Sato17c76b02009-04-06 19:01:24 -07001377 /* child of the root node is deleted */
1378 path[level].bp_op = nilfs_btree_do_delete;
1379 stats->bs_nblocks++;
1380
1381 /* success */
1382 out:
1383 *levelp = level;
1384 return ret;
1385
1386 /* error */
1387 err_out_curr_node:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001388 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001389 err_out_child_node:
1390 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001391 brelse(path[level].bp_sib_bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001392 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001393 }
1394 *levelp = level;
1395 stats->bs_nblocks = 0;
1396 return ret;
1397}
1398
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001399static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001400 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001401 int maxlevel, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001402{
1403 int level;
1404
1405 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001406 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
Pekka Enberg8acfbf02009-04-06 19:01:49 -07001407 path[level].bp_op(btree, path, level, NULL, NULL);
Koji Sato17c76b02009-04-06 19:01:24 -07001408 }
1409
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001410 if (!nilfs_bmap_dirty(btree))
1411 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001412}
1413
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001414static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
Koji Sato17c76b02009-04-06 19:01:24 -07001415
1416{
Koji Sato17c76b02009-04-06 19:01:24 -07001417 struct nilfs_btree_path *path;
1418 struct nilfs_bmap_stats stats;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001419 struct inode *dat;
Koji Sato17c76b02009-04-06 19:01:24 -07001420 int level, ret;
1421
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001422 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07001423 if (path == NULL)
1424 return -ENOMEM;
Li Hongf9054402010-04-02 17:36:34 +08001425
Koji Sato17c76b02009-04-06 19:01:24 -07001426 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1427 NILFS_BTREE_LEVEL_NODE_MIN);
1428 if (ret < 0)
1429 goto out;
1430
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001431
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001432 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001433
1434 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001435 if (ret < 0)
1436 goto out;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001437 nilfs_btree_commit_delete(btree, path, level, dat);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001438 nilfs_bmap_sub_blocks(btree, stats.bs_nblocks);
Koji Sato17c76b02009-04-06 19:01:24 -07001439
1440out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001441 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07001442 return ret;
1443}
1444
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001445static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
Koji Sato17c76b02009-04-06 19:01:24 -07001446{
Koji Sato17c76b02009-04-06 19:01:24 -07001447 struct nilfs_btree_path *path;
1448 int ret;
1449
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001450 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07001451 if (path == NULL)
1452 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07001453
1454 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1455
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001456 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07001457
1458 return ret;
1459}
1460
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001461static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
Koji Sato17c76b02009-04-06 19:01:24 -07001462{
1463 struct buffer_head *bh;
Koji Sato17c76b02009-04-06 19:01:24 -07001464 struct nilfs_btree_node *root, *node;
1465 __u64 maxkey, nextmaxkey;
1466 __u64 ptr;
1467 int nchildren, ret;
1468
Koji Sato17c76b02009-04-06 19:01:24 -07001469 root = nilfs_btree_get_root(btree);
1470 switch (nilfs_btree_height(btree)) {
1471 case 2:
1472 bh = NULL;
1473 node = root;
1474 break;
1475 case 3:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001476 nchildren = nilfs_btree_node_get_nchildren(root);
Koji Sato17c76b02009-04-06 19:01:24 -07001477 if (nchildren > 1)
1478 return 0;
1479 ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001480 ret = nilfs_btree_get_block(btree, ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001481 if (ret < 0)
1482 return ret;
1483 node = (struct nilfs_btree_node *)bh->b_data;
1484 break;
1485 default:
1486 return 0;
1487 }
1488
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001489 nchildren = nilfs_btree_node_get_nchildren(node);
1490 maxkey = nilfs_btree_node_get_key(node, nchildren - 1);
Koji Sato17c76b02009-04-06 19:01:24 -07001491 nextmaxkey = (nchildren > 1) ?
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001492 nilfs_btree_node_get_key(node, nchildren - 2) : 0;
Koji Sato17c76b02009-04-06 19:01:24 -07001493 if (bh != NULL)
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001494 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001495
Ryusuke Konishi30333422009-05-24 00:09:44 +09001496 return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
Koji Sato17c76b02009-04-06 19:01:24 -07001497}
1498
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001499static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001500 __u64 *keys, __u64 *ptrs, int nitems)
1501{
1502 struct buffer_head *bh;
Koji Sato17c76b02009-04-06 19:01:24 -07001503 struct nilfs_btree_node *node, *root;
1504 __le64 *dkeys;
1505 __le64 *dptrs;
1506 __u64 ptr;
1507 int nchildren, i, ret;
1508
Koji Sato17c76b02009-04-06 19:01:24 -07001509 root = nilfs_btree_get_root(btree);
1510 switch (nilfs_btree_height(btree)) {
1511 case 2:
1512 bh = NULL;
1513 node = root;
1514 break;
1515 case 3:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001516 nchildren = nilfs_btree_node_get_nchildren(root);
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001517 WARN_ON(nchildren > 1);
Koji Sato17c76b02009-04-06 19:01:24 -07001518 ptr = nilfs_btree_node_get_ptr(btree, root, nchildren - 1);
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001519 ret = nilfs_btree_get_block(btree, ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001520 if (ret < 0)
1521 return ret;
1522 node = (struct nilfs_btree_node *)bh->b_data;
1523 break;
1524 default:
1525 node = NULL;
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001526 return -EINVAL;
Koji Sato17c76b02009-04-06 19:01:24 -07001527 }
1528
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001529 nchildren = nilfs_btree_node_get_nchildren(node);
Koji Sato17c76b02009-04-06 19:01:24 -07001530 if (nchildren < nitems)
1531 nitems = nchildren;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001532 dkeys = nilfs_btree_node_dkeys(node);
1533 dptrs = nilfs_btree_node_dptrs(node, btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001534 for (i = 0; i < nitems; i++) {
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09001535 keys[i] = le64_to_cpu(dkeys[i]);
1536 ptrs[i] = le64_to_cpu(dptrs[i]);
Koji Sato17c76b02009-04-06 19:01:24 -07001537 }
1538
1539 if (bh != NULL)
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001540 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001541
1542 return nitems;
1543}
1544
1545static int
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001546nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
Koji Sato17c76b02009-04-06 19:01:24 -07001547 union nilfs_bmap_ptr_req *dreq,
1548 union nilfs_bmap_ptr_req *nreq,
1549 struct buffer_head **bhp,
1550 struct nilfs_bmap_stats *stats)
1551{
1552 struct buffer_head *bh;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001553 struct inode *dat = NULL;
Koji Sato17c76b02009-04-06 19:01:24 -07001554 int ret;
1555
Koji Sato17c76b02009-04-06 19:01:24 -07001556 stats->bs_nblocks = 0;
1557
1558 /* for data */
1559 /* cannot find near ptr */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001560 if (NILFS_BMAP_USE_VBN(btree)) {
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09001561 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001562 dat = nilfs_bmap_get_dat(btree);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001563 }
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09001564
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001565 ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001566 if (ret < 0)
1567 return ret;
1568
1569 *bhp = NULL;
1570 stats->bs_nblocks++;
1571 if (nreq != NULL) {
1572 nreq->bpr_ptr = dreq->bpr_ptr + 1;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001573 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001574 if (ret < 0)
1575 goto err_out_dreq;
1576
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09001577 ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001578 if (ret < 0)
1579 goto err_out_nreq;
1580
1581 *bhp = bh;
1582 stats->bs_nblocks++;
1583 }
1584
1585 /* success */
1586 return 0;
1587
1588 /* error */
1589 err_out_nreq:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001590 nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001591 err_out_dreq:
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001592 nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001593 stats->bs_nblocks = 0;
1594 return ret;
1595
1596}
1597
1598static void
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001599nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001600 __u64 key, __u64 ptr,
1601 const __u64 *keys, const __u64 *ptrs,
Ryusuke Konishi30333422009-05-24 00:09:44 +09001602 int n,
Koji Sato17c76b02009-04-06 19:01:24 -07001603 union nilfs_bmap_ptr_req *dreq,
1604 union nilfs_bmap_ptr_req *nreq,
1605 struct buffer_head *bh)
1606{
Koji Sato17c76b02009-04-06 19:01:24 -07001607 struct nilfs_btree_node *node;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001608 struct inode *dat;
Koji Sato17c76b02009-04-06 19:01:24 -07001609 __u64 tmpptr;
1610
1611 /* free resources */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001612 if (btree->b_ops->bop_clear != NULL)
1613 btree->b_ops->bop_clear(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001614
1615 /* ptr must be a pointer to a buffer head. */
1616 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1617
1618 /* convert and insert */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001619 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1620 nilfs_btree_init(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001621 if (nreq != NULL) {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001622 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1623 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001624
1625 /* create child node at level 1 */
Koji Sato17c76b02009-04-06 19:01:24 -07001626 node = (struct nilfs_btree_node *)bh->b_data;
1627 nilfs_btree_node_init(btree, node, 0, 1, n, keys, ptrs);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001628 nilfs_btree_node_insert(btree, node, key, dreq->bpr_ptr, n);
Koji Sato17c76b02009-04-06 19:01:24 -07001629 if (!buffer_dirty(bh))
1630 nilfs_btnode_mark_dirty(bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001631 if (!nilfs_bmap_dirty(btree))
1632 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001633
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09001634 brelse(bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001635
1636 /* create root node at level 2 */
1637 node = nilfs_btree_get_root(btree);
1638 tmpptr = nreq->bpr_ptr;
1639 nilfs_btree_node_init(btree, node, NILFS_BTREE_NODE_ROOT,
1640 2, 1, &keys[0], &tmpptr);
1641 } else {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001642 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001643
1644 /* create root node at level 1 */
1645 node = nilfs_btree_get_root(btree);
1646 nilfs_btree_node_init(btree, node, NILFS_BTREE_NODE_ROOT,
1647 1, n, keys, ptrs);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001648 nilfs_btree_node_insert(btree, node, key, dreq->bpr_ptr, n);
1649 if (!nilfs_bmap_dirty(btree))
1650 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001651 }
1652
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001653 if (NILFS_BMAP_USE_VBN(btree))
Ryusuke Konishidc935be2010-07-10 22:21:54 +09001654 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
Koji Sato17c76b02009-04-06 19:01:24 -07001655}
1656
1657/**
1658 * nilfs_btree_convert_and_insert -
1659 * @bmap:
1660 * @key:
1661 * @ptr:
1662 * @keys:
1663 * @ptrs:
1664 * @n:
Koji Sato17c76b02009-04-06 19:01:24 -07001665 */
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001666int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001667 __u64 key, __u64 ptr,
Ryusuke Konishi30333422009-05-24 00:09:44 +09001668 const __u64 *keys, const __u64 *ptrs, int n)
Koji Sato17c76b02009-04-06 19:01:24 -07001669{
1670 struct buffer_head *bh;
1671 union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
1672 struct nilfs_bmap_stats stats;
1673 int ret;
1674
1675 if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1676 di = &dreq;
1677 ni = NULL;
1678 } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001679 1 << btree->b_inode->i_blkbits)) {
Koji Sato17c76b02009-04-06 19:01:24 -07001680 di = &dreq;
1681 ni = &nreq;
1682 } else {
1683 di = NULL;
1684 ni = NULL;
1685 BUG();
1686 }
1687
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001688 ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
Koji Sato17c76b02009-04-06 19:01:24 -07001689 &stats);
1690 if (ret < 0)
1691 return ret;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001692 nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
Ryusuke Konishi30333422009-05-24 00:09:44 +09001693 di, ni, bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001694 nilfs_bmap_add_blocks(btree, stats.bs_nblocks);
Koji Sato17c76b02009-04-06 19:01:24 -07001695 return 0;
1696}
1697
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001698static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001699 struct nilfs_btree_path *path,
1700 int level,
1701 struct buffer_head *bh)
1702{
1703 while ((++level < nilfs_btree_height(btree) - 1) &&
1704 !buffer_dirty(path[level].bp_bh))
1705 nilfs_btnode_mark_dirty(path[level].bp_bh);
1706
1707 return 0;
1708}
1709
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001710static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001711 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001712 int level, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001713{
1714 struct nilfs_btree_node *parent;
1715 int ret;
1716
1717 parent = nilfs_btree_get_node(btree, path, level + 1);
1718 path[level].bp_oldreq.bpr_ptr =
1719 nilfs_btree_node_get_ptr(btree, parent,
1720 path[level + 1].bp_index);
1721 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001722 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
1723 &path[level].bp_newreq.bpr_req);
Koji Sato17c76b02009-04-06 19:01:24 -07001724 if (ret < 0)
1725 return ret;
1726
1727 if (buffer_nilfs_node(path[level].bp_bh)) {
1728 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
1729 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
1730 path[level].bp_ctxt.bh = path[level].bp_bh;
1731 ret = nilfs_btnode_prepare_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001732 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07001733 &path[level].bp_ctxt);
1734 if (ret < 0) {
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001735 nilfs_dat_abort_update(dat,
1736 &path[level].bp_oldreq.bpr_req,
1737 &path[level].bp_newreq.bpr_req);
Koji Sato17c76b02009-04-06 19:01:24 -07001738 return ret;
1739 }
1740 }
1741
1742 return 0;
1743}
1744
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001745static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001746 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001747 int level, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001748{
1749 struct nilfs_btree_node *parent;
1750
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001751 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
1752 &path[level].bp_newreq.bpr_req,
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001753 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
Koji Sato17c76b02009-04-06 19:01:24 -07001754
1755 if (buffer_nilfs_node(path[level].bp_bh)) {
1756 nilfs_btnode_commit_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001757 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07001758 &path[level].bp_ctxt);
1759 path[level].bp_bh = path[level].bp_ctxt.bh;
1760 }
1761 set_buffer_nilfs_volatile(path[level].bp_bh);
1762
1763 parent = nilfs_btree_get_node(btree, path, level + 1);
1764 nilfs_btree_node_set_ptr(btree, parent, path[level + 1].bp_index,
1765 path[level].bp_newreq.bpr_ptr);
1766}
1767
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001768static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001769 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001770 int level, struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001771{
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001772 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
1773 &path[level].bp_newreq.bpr_req);
Koji Sato17c76b02009-04-06 19:01:24 -07001774 if (buffer_nilfs_node(path[level].bp_bh))
1775 nilfs_btnode_abort_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001776 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07001777 &path[level].bp_ctxt);
1778}
1779
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001780static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001781 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001782 int minlevel, int *maxlevelp,
1783 struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001784{
1785 int level, ret;
1786
1787 level = minlevel;
1788 if (!buffer_nilfs_volatile(path[level].bp_bh)) {
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001789 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001790 if (ret < 0)
1791 return ret;
1792 }
1793 while ((++level < nilfs_btree_height(btree) - 1) &&
1794 !buffer_dirty(path[level].bp_bh)) {
1795
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001796 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001797 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001798 if (ret < 0)
1799 goto out;
1800 }
1801
1802 /* success */
Koji Sato17c76b02009-04-06 19:01:24 -07001803 *maxlevelp = level - 1;
1804 return 0;
1805
1806 /* error */
1807 out:
1808 while (--level > minlevel)
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001809 nilfs_btree_abort_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001810 if (!buffer_nilfs_volatile(path[level].bp_bh))
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001811 nilfs_btree_abort_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001812 return ret;
1813}
1814
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001815static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001816 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001817 int minlevel, int maxlevel,
1818 struct buffer_head *bh,
1819 struct inode *dat)
Koji Sato17c76b02009-04-06 19:01:24 -07001820{
1821 int level;
1822
1823 if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001824 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001825
1826 for (level = minlevel + 1; level <= maxlevel; level++)
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001827 nilfs_btree_commit_update_v(btree, path, level, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001828}
1829
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001830static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001831 struct nilfs_btree_path *path,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001832 int level, struct buffer_head *bh)
Koji Sato17c76b02009-04-06 19:01:24 -07001833{
Li Hong308f4412010-04-02 18:40:39 +08001834 int maxlevel = 0, ret;
Koji Sato17c76b02009-04-06 19:01:24 -07001835 struct nilfs_btree_node *parent;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001836 struct inode *dat = nilfs_bmap_get_dat(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07001837 __u64 ptr;
1838
1839 get_bh(bh);
1840 path[level].bp_bh = bh;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001841 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
1842 dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001843 if (ret < 0)
1844 goto out;
1845
1846 if (buffer_nilfs_volatile(path[level].bp_bh)) {
1847 parent = nilfs_btree_get_node(btree, path, level + 1);
1848 ptr = nilfs_btree_node_get_ptr(btree, parent,
1849 path[level + 1].bp_index);
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001850 ret = nilfs_dat_mark_dirty(dat, ptr);
Koji Sato17c76b02009-04-06 19:01:24 -07001851 if (ret < 0)
1852 goto out;
1853 }
1854
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09001855 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
Koji Sato17c76b02009-04-06 19:01:24 -07001856
1857 out:
1858 brelse(path[level].bp_bh);
1859 path[level].bp_bh = NULL;
1860 return ret;
1861}
1862
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001863static int nilfs_btree_propagate(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001864 struct buffer_head *bh)
1865{
Koji Sato17c76b02009-04-06 19:01:24 -07001866 struct nilfs_btree_path *path;
1867 struct nilfs_btree_node *node;
1868 __u64 key;
1869 int level, ret;
1870
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001871 WARN_ON(!buffer_dirty(bh));
Koji Sato17c76b02009-04-06 19:01:24 -07001872
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001873 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07001874 if (path == NULL)
1875 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07001876
1877 if (buffer_nilfs_node(bh)) {
1878 node = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001879 key = nilfs_btree_node_get_key(node, 0);
1880 level = nilfs_btree_node_get_level(node);
Koji Sato17c76b02009-04-06 19:01:24 -07001881 } else {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001882 key = nilfs_bmap_data_get_key(btree, bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001883 level = NILFS_BTREE_LEVEL_DATA;
1884 }
1885
1886 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1);
1887 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07001888 if (unlikely(ret == -ENOENT))
Koji Sato17c76b02009-04-06 19:01:24 -07001889 printk(KERN_CRIT "%s: key = %llu, level == %d\n",
1890 __func__, (unsigned long long)key, level);
Koji Sato17c76b02009-04-06 19:01:24 -07001891 goto out;
1892 }
1893
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001894 ret = NILFS_BMAP_USE_VBN(btree) ?
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09001895 nilfs_btree_propagate_v(btree, path, level, bh) :
1896 nilfs_btree_propagate_p(btree, path, level, bh);
Koji Sato17c76b02009-04-06 19:01:24 -07001897
1898 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001899 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07001900
1901 return ret;
1902}
1903
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001904static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001905 struct buffer_head *bh)
1906{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001907 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
Koji Sato17c76b02009-04-06 19:01:24 -07001908}
1909
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001910static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001911 struct list_head *lists,
1912 struct buffer_head *bh)
1913{
1914 struct list_head *head;
1915 struct buffer_head *cbh;
1916 struct nilfs_btree_node *node, *cnode;
1917 __u64 key, ckey;
1918 int level;
1919
1920 get_bh(bh);
1921 node = (struct nilfs_btree_node *)bh->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001922 key = nilfs_btree_node_get_key(node, 0);
1923 level = nilfs_btree_node_get_level(node);
Ryusuke Konishicfa913a2010-07-07 17:19:54 +09001924 if (level < NILFS_BTREE_LEVEL_NODE_MIN ||
1925 level >= NILFS_BTREE_LEVEL_MAX) {
1926 dump_stack();
1927 printk(KERN_WARNING
1928 "%s: invalid btree level: %d (key=%llu, ino=%lu, "
1929 "blocknr=%llu)\n",
1930 __func__, level, (unsigned long long)key,
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001931 NILFS_BMAP_I(btree)->vfs_inode.i_ino,
Ryusuke Konishicfa913a2010-07-07 17:19:54 +09001932 (unsigned long long)bh->b_blocknr);
1933 return;
1934 }
1935
Koji Sato17c76b02009-04-06 19:01:24 -07001936 list_for_each(head, &lists[level]) {
1937 cbh = list_entry(head, struct buffer_head, b_assoc_buffers);
1938 cnode = (struct nilfs_btree_node *)cbh->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09001939 ckey = nilfs_btree_node_get_key(cnode, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07001940 if (key < ckey)
1941 break;
1942 }
1943 list_add_tail(&bh->b_assoc_buffers, head);
1944}
1945
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001946static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001947 struct list_head *listp)
1948{
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001949 struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache;
Koji Sato17c76b02009-04-06 19:01:24 -07001950 struct list_head lists[NILFS_BTREE_LEVEL_MAX];
1951 struct pagevec pvec;
1952 struct buffer_head *bh, *head;
1953 pgoff_t index = 0;
1954 int level, i;
1955
1956 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
1957 level < NILFS_BTREE_LEVEL_MAX;
1958 level++)
1959 INIT_LIST_HEAD(&lists[level]);
1960
1961 pagevec_init(&pvec, 0);
1962
1963 while (pagevec_lookup_tag(&pvec, btcache, &index, PAGECACHE_TAG_DIRTY,
1964 PAGEVEC_SIZE)) {
1965 for (i = 0; i < pagevec_count(&pvec); i++) {
1966 bh = head = page_buffers(pvec.pages[i]);
1967 do {
1968 if (buffer_dirty(bh))
1969 nilfs_btree_add_dirty_buffer(btree,
1970 lists, bh);
1971 } while ((bh = bh->b_this_page) != head);
1972 }
1973 pagevec_release(&pvec);
1974 cond_resched();
1975 }
1976
1977 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
1978 level < NILFS_BTREE_LEVEL_MAX;
1979 level++)
Ryusuke Konishi0935db72009-11-29 02:39:11 +09001980 list_splice_tail(&lists[level], listp);
Koji Sato17c76b02009-04-06 19:01:24 -07001981}
1982
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09001983static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07001984 struct nilfs_btree_path *path,
1985 int level,
1986 struct buffer_head **bh,
1987 sector_t blocknr,
1988 union nilfs_binfo *binfo)
1989{
1990 struct nilfs_btree_node *parent;
1991 __u64 key;
1992 __u64 ptr;
1993 int ret;
1994
1995 parent = nilfs_btree_get_node(btree, path, level + 1);
1996 ptr = nilfs_btree_node_get_ptr(btree, parent,
1997 path[level + 1].bp_index);
1998 if (buffer_nilfs_node(*bh)) {
1999 path[level].bp_ctxt.oldkey = ptr;
2000 path[level].bp_ctxt.newkey = blocknr;
2001 path[level].bp_ctxt.bh = *bh;
2002 ret = nilfs_btnode_prepare_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002003 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07002004 &path[level].bp_ctxt);
2005 if (ret < 0)
2006 return ret;
2007 nilfs_btnode_commit_change_key(
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002008 &NILFS_BMAP_I(btree)->i_btnode_cache,
Koji Sato17c76b02009-04-06 19:01:24 -07002009 &path[level].bp_ctxt);
2010 *bh = path[level].bp_ctxt.bh;
2011 }
2012
2013 nilfs_btree_node_set_ptr(btree, parent,
2014 path[level + 1].bp_index, blocknr);
2015
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002016 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
Koji Sato17c76b02009-04-06 19:01:24 -07002017 /* on-disk format */
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09002018 binfo->bi_dat.bi_blkoff = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -07002019 binfo->bi_dat.bi_level = level;
2020
2021 return 0;
2022}
2023
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002024static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002025 struct nilfs_btree_path *path,
2026 int level,
2027 struct buffer_head **bh,
2028 sector_t blocknr,
2029 union nilfs_binfo *binfo)
2030{
2031 struct nilfs_btree_node *parent;
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002032 struct inode *dat = nilfs_bmap_get_dat(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07002033 __u64 key;
2034 __u64 ptr;
2035 union nilfs_bmap_ptr_req req;
2036 int ret;
2037
2038 parent = nilfs_btree_get_node(btree, path, level + 1);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002039 ptr = nilfs_btree_node_get_ptr(btree, parent, path[level + 1].bp_index);
Koji Sato17c76b02009-04-06 19:01:24 -07002040 req.bpr_ptr = ptr;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002041 ret = nilfs_dat_prepare_start(dat, &req.bpr_req);
2042 if (ret < 0)
Koji Sato17c76b02009-04-06 19:01:24 -07002043 return ret;
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002044 nilfs_dat_commit_start(dat, &req.bpr_req, blocknr);
Koji Sato17c76b02009-04-06 19:01:24 -07002045
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002046 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
Koji Sato17c76b02009-04-06 19:01:24 -07002047 /* on-disk format */
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09002048 binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr);
2049 binfo->bi_v.bi_blkoff = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -07002050
2051 return 0;
2052}
2053
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002054static int nilfs_btree_assign(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002055 struct buffer_head **bh,
2056 sector_t blocknr,
2057 union nilfs_binfo *binfo)
2058{
Koji Sato17c76b02009-04-06 19:01:24 -07002059 struct nilfs_btree_path *path;
2060 struct nilfs_btree_node *node;
2061 __u64 key;
2062 int level, ret;
2063
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002064 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07002065 if (path == NULL)
2066 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07002067
2068 if (buffer_nilfs_node(*bh)) {
2069 node = (struct nilfs_btree_node *)(*bh)->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002070 key = nilfs_btree_node_get_key(node, 0);
2071 level = nilfs_btree_node_get_level(node);
Koji Sato17c76b02009-04-06 19:01:24 -07002072 } else {
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002073 key = nilfs_bmap_data_get_key(btree, *bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002074 level = NILFS_BTREE_LEVEL_DATA;
2075 }
2076
2077 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1);
2078 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002079 WARN_ON(ret == -ENOENT);
Koji Sato17c76b02009-04-06 19:01:24 -07002080 goto out;
2081 }
2082
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002083 ret = NILFS_BMAP_USE_VBN(btree) ?
Ryusuke Konishi7cde31d2009-05-24 18:07:59 +09002084 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2085 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
Koji Sato17c76b02009-04-06 19:01:24 -07002086
2087 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002088 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07002089
2090 return ret;
2091}
2092
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002093static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
Koji Sato17c76b02009-04-06 19:01:24 -07002094 struct buffer_head **bh,
2095 sector_t blocknr,
2096 union nilfs_binfo *binfo)
2097{
Koji Sato17c76b02009-04-06 19:01:24 -07002098 struct nilfs_btree_node *node;
2099 __u64 key;
2100 int ret;
2101
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002102 ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
Ryusuke Konishi2e0c2c72009-08-15 15:34:33 +09002103 blocknr);
Koji Sato17c76b02009-04-06 19:01:24 -07002104 if (ret < 0)
2105 return ret;
2106
2107 if (buffer_nilfs_node(*bh)) {
2108 node = (struct nilfs_btree_node *)(*bh)->b_data;
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002109 key = nilfs_btree_node_get_key(node, 0);
Koji Sato17c76b02009-04-06 19:01:24 -07002110 } else
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002111 key = nilfs_bmap_data_get_key(btree, *bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002112
2113 /* on-disk format */
2114 binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr);
Ryusuke Konishi25b8d7d2010-07-10 16:50:41 +09002115 binfo->bi_v.bi_blkoff = cpu_to_le64(key);
Koji Sato17c76b02009-04-06 19:01:24 -07002116
2117 return 0;
2118}
2119
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002120static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
Koji Sato17c76b02009-04-06 19:01:24 -07002121{
2122 struct buffer_head *bh;
Koji Sato17c76b02009-04-06 19:01:24 -07002123 struct nilfs_btree_path *path;
2124 __u64 ptr;
2125 int ret;
2126
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002127 path = nilfs_btree_alloc_path();
Koji Sato17c76b02009-04-06 19:01:24 -07002128 if (path == NULL)
2129 return -ENOMEM;
Koji Sato17c76b02009-04-06 19:01:24 -07002130
2131 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1);
2132 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002133 WARN_ON(ret == -ENOENT);
Koji Sato17c76b02009-04-06 19:01:24 -07002134 goto out;
2135 }
Ryusuke Konishif198dbb2009-05-22 01:07:13 +09002136 ret = nilfs_btree_get_block(btree, ptr, &bh);
Koji Sato17c76b02009-04-06 19:01:24 -07002137 if (ret < 0) {
Ryusuke Konishi1f5abe72009-04-06 19:01:55 -07002138 WARN_ON(ret == -ENOENT);
Koji Sato17c76b02009-04-06 19:01:24 -07002139 goto out;
2140 }
2141
2142 if (!buffer_dirty(bh))
2143 nilfs_btnode_mark_dirty(bh);
Ryusuke Konishi087d01b2009-05-22 00:33:13 +09002144 brelse(bh);
Ryusuke Konishie7c274f2010-07-10 19:09:49 +09002145 if (!nilfs_bmap_dirty(btree))
2146 nilfs_bmap_set_dirty(btree);
Koji Sato17c76b02009-04-06 19:01:24 -07002147
2148 out:
Ryusuke Konishi6d28f7e2009-08-15 01:14:10 +09002149 nilfs_btree_free_path(path);
Koji Sato17c76b02009-04-06 19:01:24 -07002150 return ret;
2151}
2152
2153static const struct nilfs_bmap_operations nilfs_btree_ops = {
2154 .bop_lookup = nilfs_btree_lookup,
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +09002155 .bop_lookup_contig = nilfs_btree_lookup_contig,
Koji Sato17c76b02009-04-06 19:01:24 -07002156 .bop_insert = nilfs_btree_insert,
2157 .bop_delete = nilfs_btree_delete,
2158 .bop_clear = NULL,
2159
2160 .bop_propagate = nilfs_btree_propagate,
2161
2162 .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
2163
2164 .bop_assign = nilfs_btree_assign,
2165 .bop_mark = nilfs_btree_mark,
2166
2167 .bop_last_key = nilfs_btree_last_key,
2168 .bop_check_insert = NULL,
2169 .bop_check_delete = nilfs_btree_check_delete,
2170 .bop_gather_data = nilfs_btree_gather_data,
2171};
2172
2173static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
2174 .bop_lookup = NULL,
Ryusuke Konishic3a7abf2009-05-25 02:47:14 +09002175 .bop_lookup_contig = NULL,
Koji Sato17c76b02009-04-06 19:01:24 -07002176 .bop_insert = NULL,
2177 .bop_delete = NULL,
2178 .bop_clear = NULL,
2179
2180 .bop_propagate = nilfs_btree_propagate_gc,
2181
2182 .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
2183
2184 .bop_assign = nilfs_btree_assign_gc,
2185 .bop_mark = NULL,
2186
2187 .bop_last_key = NULL,
2188 .bop_check_insert = NULL,
2189 .bop_check_delete = NULL,
2190 .bop_gather_data = NULL,
2191};
2192
Ryusuke Konishi30333422009-05-24 00:09:44 +09002193int nilfs_btree_init(struct nilfs_bmap *bmap)
Koji Sato17c76b02009-04-06 19:01:24 -07002194{
Koji Sato17c76b02009-04-06 19:01:24 -07002195 bmap->b_ops = &nilfs_btree_ops;
Koji Sato17c76b02009-04-06 19:01:24 -07002196 return 0;
2197}
2198
2199void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
2200{
Koji Sato17c76b02009-04-06 19:01:24 -07002201 bmap->b_ops = &nilfs_btree_ops_gc;
2202}