Blame view
fs/nilfs2/btree.c
60 KB
17c76b010
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
/* * btree.c - NILFS B-tree. * * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA * * Written by Koji Sato <koji@osrg.net>. */ #include <linux/slab.h> #include <linux/string.h> #include <linux/errno.h> #include <linux/pagevec.h> #include "nilfs.h" #include "page.h" #include "btnode.h" #include "btree.h" #include "alloc.h" |
c3a7abf06
|
32 |
#include "dat.h" |
17c76b010
|
33 |
|
f905440f5
|
34 |
static struct nilfs_btree_path *nilfs_btree_alloc_path(void) |
17c76b010
|
35 |
{ |
f905440f5
|
36 37 |
struct nilfs_btree_path *path; int level = NILFS_BTREE_LEVEL_DATA; |
17c76b010
|
38 |
|
f905440f5
|
39 40 41 |
path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS); if (path == NULL) goto out; |
17c76b010
|
42 |
|
f905440f5
|
43 |
for (; level < NILFS_BTREE_LEVEL_MAX; level++) { |
17c76b010
|
44 45 46 47 48 49 50 |
path[level].bp_bh = NULL; path[level].bp_sib_bh = NULL; path[level].bp_index = 0; path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; path[level].bp_op = NULL; } |
f905440f5
|
51 52 53 54 |
out: return path; } |
73bb48869
|
55 |
static void nilfs_btree_free_path(struct nilfs_btree_path *path) |
f905440f5
|
56 |
{ |
73bb48869
|
57 |
int level = NILFS_BTREE_LEVEL_DATA; |
17c76b010
|
58 |
|
73bb48869
|
59 |
for (; level < NILFS_BTREE_LEVEL_MAX; level++) |
3218929db
|
60 |
brelse(path[level].bp_bh); |
73bb48869
|
61 62 |
kmem_cache_free(nilfs_btree_path_cache, path); |
17c76b010
|
63 |
} |
17c76b010
|
64 65 66 |
/* * B-tree node operations */ |
e7c274f80
|
67 |
static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree, |
f198dbb9c
|
68 69 |
__u64 ptr, struct buffer_head **bhp) { |
e7c274f80
|
70 |
struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache; |
45f4910bc
|
71 |
struct buffer_head *bh; |
f198dbb9c
|
72 |
|
45f4910bc
|
73 74 75 76 77 78 79 |
bh = nilfs_btnode_create_block(btnc, ptr); if (!bh) return -ENOMEM; set_buffer_nilfs_volatile(bh); *bhp = bh; return 0; |
f198dbb9c
|
80 |
} |
17c76b010
|
81 |
|
7c397a81f
|
82 |
static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node) |
17c76b010
|
83 84 85 |
{ return node->bn_flags; } |
7c397a81f
|
86 |
static void |
6d28f7ea4
|
87 |
nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags) |
17c76b010
|
88 89 90 |
{ node->bn_flags = flags; } |
7c397a81f
|
91 |
static int nilfs_btree_node_root(const struct nilfs_btree_node *node) |
17c76b010
|
92 |
{ |
6d28f7ea4
|
93 |
return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT; |
17c76b010
|
94 |
} |
7c397a81f
|
95 |
static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node) |
17c76b010
|
96 97 98 |
{ return node->bn_level; } |
7c397a81f
|
99 |
static void |
6d28f7ea4
|
100 |
nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) |
17c76b010
|
101 102 103 |
{ node->bn_level = level; } |
7c397a81f
|
104 |
static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node) |
17c76b010
|
105 106 107 |
{ return le16_to_cpu(node->bn_nchildren); } |
7c397a81f
|
108 |
static void |
6d28f7ea4
|
109 |
nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren) |
17c76b010
|
110 111 112 |
{ node->bn_nchildren = cpu_to_le16(nchildren); } |
7c397a81f
|
113 |
static int nilfs_btree_node_size(const struct nilfs_bmap *btree) |
17c76b010
|
114 |
{ |
e7c274f80
|
115 |
return 1 << btree->b_inode->i_blkbits; |
17c76b010
|
116 |
} |
9b7b265c9
|
117 |
static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree) |
17c76b010
|
118 |
{ |
5ad2686e9
|
119 |
return btree->b_nchildren_per_block; |
17c76b010
|
120 |
} |
7c397a81f
|
121 |
static __le64 * |
6d28f7ea4
|
122 |
nilfs_btree_node_dkeys(const struct nilfs_btree_node *node) |
17c76b010
|
123 124 |
{ return (__le64 *)((char *)(node + 1) + |
6d28f7ea4
|
125 |
(nilfs_btree_node_root(node) ? |
17c76b010
|
126 127 |
0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE)); } |
7c397a81f
|
128 |
static __le64 * |
9b7b265c9
|
129 |
nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax) |
17c76b010
|
130 |
{ |
9b7b265c9
|
131 |
return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax); |
17c76b010
|
132 |
} |
7c397a81f
|
133 |
static __u64 |
6d28f7ea4
|
134 |
nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index) |
17c76b010
|
135 |
{ |
25b8d7ded
|
136 |
return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index)); |
17c76b010
|
137 |
} |
7c397a81f
|
138 |
static void |
6d28f7ea4
|
139 |
nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key) |
17c76b010
|
140 |
{ |
25b8d7ded
|
141 |
*(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key); |
17c76b010
|
142 |
} |
7c397a81f
|
143 |
static __u64 |
9b7b265c9
|
144 145 |
nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index, int ncmax) |
17c76b010
|
146 |
{ |
9b7b265c9
|
147 |
return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index)); |
17c76b010
|
148 |
} |
7c397a81f
|
149 |
static void |
9b7b265c9
|
150 151 |
nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr, int ncmax) |
17c76b010
|
152 |
{ |
9b7b265c9
|
153 |
*(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr); |
17c76b010
|
154 |
} |
9b7b265c9
|
155 156 |
static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags, int level, int nchildren, int ncmax, |
17c76b010
|
157 158 159 160 161 |
const __u64 *keys, const __u64 *ptrs) { __le64 *dkeys; __le64 *dptrs; int i; |
6d28f7ea4
|
162 163 164 |
nilfs_btree_node_set_flags(node, flags); nilfs_btree_node_set_level(node, level); nilfs_btree_node_set_nchildren(node, nchildren); |
17c76b010
|
165 |
|
6d28f7ea4
|
166 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9
|
167 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
17c76b010
|
168 |
for (i = 0; i < nchildren; i++) { |
25b8d7ded
|
169 170 |
dkeys[i] = cpu_to_le64(keys[i]); dptrs[i] = cpu_to_le64(ptrs[i]); |
17c76b010
|
171 172 173 174 |
} } /* Assume the buffer heads corresponding to left and right are locked. */ |
9b7b265c9
|
175 |
static void nilfs_btree_node_move_left(struct nilfs_btree_node *left, |
17c76b010
|
176 |
struct nilfs_btree_node *right, |
9b7b265c9
|
177 |
int n, int lncmax, int rncmax) |
17c76b010
|
178 179 180 181 |
{ __le64 *ldkeys, *rdkeys; __le64 *ldptrs, *rdptrs; int lnchildren, rnchildren; |
6d28f7ea4
|
182 |
ldkeys = nilfs_btree_node_dkeys(left); |
9b7b265c9
|
183 |
ldptrs = nilfs_btree_node_dptrs(left, lncmax); |
6d28f7ea4
|
184 |
lnchildren = nilfs_btree_node_get_nchildren(left); |
17c76b010
|
185 |
|
6d28f7ea4
|
186 |
rdkeys = nilfs_btree_node_dkeys(right); |
9b7b265c9
|
187 |
rdptrs = nilfs_btree_node_dptrs(right, rncmax); |
6d28f7ea4
|
188 |
rnchildren = nilfs_btree_node_get_nchildren(right); |
17c76b010
|
189 190 191 192 193 194 195 196 |
memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys)); memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs)); memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys)); memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs)); lnchildren += n; rnchildren -= n; |
6d28f7ea4
|
197 198 |
nilfs_btree_node_set_nchildren(left, lnchildren); nilfs_btree_node_set_nchildren(right, rnchildren); |
17c76b010
|
199 200 201 |
} /* Assume that the buffer heads corresponding to left and right are locked. */ |
9b7b265c9
|
202 |
static void nilfs_btree_node_move_right(struct nilfs_btree_node *left, |
17c76b010
|
203 |
struct nilfs_btree_node *right, |
9b7b265c9
|
204 |
int n, int lncmax, int rncmax) |
17c76b010
|
205 206 207 208 |
{ __le64 *ldkeys, *rdkeys; __le64 *ldptrs, *rdptrs; int lnchildren, rnchildren; |
6d28f7ea4
|
209 |
ldkeys = nilfs_btree_node_dkeys(left); |
9b7b265c9
|
210 |
ldptrs = nilfs_btree_node_dptrs(left, lncmax); |
6d28f7ea4
|
211 |
lnchildren = nilfs_btree_node_get_nchildren(left); |
17c76b010
|
212 |
|
6d28f7ea4
|
213 |
rdkeys = nilfs_btree_node_dkeys(right); |
9b7b265c9
|
214 |
rdptrs = nilfs_btree_node_dptrs(right, rncmax); |
6d28f7ea4
|
215 |
rnchildren = nilfs_btree_node_get_nchildren(right); |
17c76b010
|
216 217 218 219 220 221 222 223 |
memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys)); memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs)); memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys)); memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs)); lnchildren -= n; rnchildren += n; |
6d28f7ea4
|
224 225 |
nilfs_btree_node_set_nchildren(left, lnchildren); nilfs_btree_node_set_nchildren(right, rnchildren); |
17c76b010
|
226 227 228 |
} /* Assume that the buffer head corresponding to node is locked. */ |
9b7b265c9
|
229 230 |
static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index, __u64 key, __u64 ptr, int ncmax) |
17c76b010
|
231 232 233 234 |
{ __le64 *dkeys; __le64 *dptrs; int nchildren; |
6d28f7ea4
|
235 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9
|
236 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
6d28f7ea4
|
237 |
nchildren = nilfs_btree_node_get_nchildren(node); |
17c76b010
|
238 239 240 241 242 243 |
if (index < nchildren) { memmove(dkeys + index + 1, dkeys + index, (nchildren - index) * sizeof(*dkeys)); memmove(dptrs + index + 1, dptrs + index, (nchildren - index) * sizeof(*dptrs)); } |
25b8d7ded
|
244 245 |
dkeys[index] = cpu_to_le64(key); dptrs[index] = cpu_to_le64(ptr); |
17c76b010
|
246 |
nchildren++; |
6d28f7ea4
|
247 |
nilfs_btree_node_set_nchildren(node, nchildren); |
17c76b010
|
248 249 250 |
} /* Assume that the buffer head corresponding to node is locked. */ |
9b7b265c9
|
251 252 |
static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index, __u64 *keyp, __u64 *ptrp, int ncmax) |
17c76b010
|
253 254 255 256 257 258 |
{ __u64 key; __u64 ptr; __le64 *dkeys; __le64 *dptrs; int nchildren; |
6d28f7ea4
|
259 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9
|
260 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
25b8d7ded
|
261 262 |
key = le64_to_cpu(dkeys[index]); ptr = le64_to_cpu(dptrs[index]); |
6d28f7ea4
|
263 |
nchildren = nilfs_btree_node_get_nchildren(node); |
17c76b010
|
264 265 266 267 268 269 270 271 272 273 274 275 |
if (keyp != NULL) *keyp = key; if (ptrp != NULL) *ptrp = ptr; if (index < nchildren - 1) { memmove(dkeys + index, dkeys + index + 1, (nchildren - index - 1) * sizeof(*dkeys)); memmove(dptrs + index, dptrs + index + 1, (nchildren - index - 1) * sizeof(*dptrs)); } nchildren--; |
6d28f7ea4
|
276 |
nilfs_btree_node_set_nchildren(node, nchildren); |
17c76b010
|
277 |
} |
6d28f7ea4
|
278 |
static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node, |
17c76b010
|
279 280 281 282 283 284 285 |
__u64 key, int *indexp) { __u64 nkey; int index, low, high, s; /* binary search */ low = 0; |
6d28f7ea4
|
286 |
high = nilfs_btree_node_get_nchildren(node) - 1; |
17c76b010
|
287 288 289 290 |
index = 0; s = 0; while (low <= high) { index = (low + high) / 2; |
6d28f7ea4
|
291 |
nkey = nilfs_btree_node_get_key(node, index); |
17c76b010
|
292 293 294 295 296 297 298 299 300 301 302 303 304 |
if (nkey == key) { s = 0; goto out; } else if (nkey < key) { low = index + 1; s = -1; } else { high = index - 1; s = 1; } } /* adjust index */ |
6d28f7ea4
|
305 306 |
if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) { if (s > 0 && index > 0) |
17c76b010
|
307 308 309 310 311 |
index--; } else if (s < 0) index++; out: |
17c76b010
|
312 313 314 315 |
*indexp = index; return s == 0; } |
1d5385b9f
|
316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 |
/** * nilfs_btree_node_broken - verify consistency of btree node * @node: btree node block to be examined * @size: node size (in bytes) * @blocknr: block number * * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned. */ static int nilfs_btree_node_broken(const struct nilfs_btree_node *node, size_t size, sector_t blocknr) { int level, flags, nchildren; int ret = 0; level = nilfs_btree_node_get_level(node); flags = nilfs_btree_node_get_flags(node); nchildren = nilfs_btree_node_get_nchildren(node); if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || level >= NILFS_BTREE_LEVEL_MAX || (flags & NILFS_BTREE_NODE_ROOT) || nchildren < 0 || nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) { printk(KERN_CRIT "NILFS: bad btree node (blocknr=%llu): " "level = %d, flags = 0x%x, nchildren = %d ", (unsigned long long)blocknr, level, flags, nchildren); ret = 1; } return ret; } int nilfs_btree_broken_node_block(struct buffer_head *bh) { |
4e13e66be
|
350 351 352 353 354 355 |
int ret; if (buffer_nilfs_checked(bh)) return 0; ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data, |
1d5385b9f
|
356 |
bh->b_size, bh->b_blocknr); |
4e13e66be
|
357 358 359 |
if (likely(!ret)) set_buffer_nilfs_checked(bh); return ret; |
1d5385b9f
|
360 |
} |
7c397a81f
|
361 |
static struct nilfs_btree_node * |
e7c274f80
|
362 |
nilfs_btree_get_root(const struct nilfs_bmap *btree) |
17c76b010
|
363 |
{ |
e7c274f80
|
364 |
return (struct nilfs_btree_node *)btree->b_u.u_data; |
17c76b010
|
365 |
} |
7c397a81f
|
366 |
static struct nilfs_btree_node * |
6d28f7ea4
|
367 |
nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) |
17c76b010
|
368 369 370 |
{ return (struct nilfs_btree_node *)path[level].bp_bh->b_data; } |
7c397a81f
|
371 |
static struct nilfs_btree_node * |
6d28f7ea4
|
372 |
nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) |
17c76b010
|
373 374 375 |
{ return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; } |
7c397a81f
|
376 |
static int nilfs_btree_height(const struct nilfs_bmap *btree) |
17c76b010
|
377 |
{ |
6d28f7ea4
|
378 |
return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1; |
17c76b010
|
379 |
} |
9b7b265c9
|
380 |
static struct nilfs_btree_node * |
e7c274f80
|
381 |
nilfs_btree_get_node(const struct nilfs_bmap *btree, |
17c76b010
|
382 |
const struct nilfs_btree_path *path, |
9b7b265c9
|
383 |
int level, int *ncmaxp) |
17c76b010
|
384 |
{ |
9b7b265c9
|
385 386 387 388 389 390 391 392 393 394 |
struct nilfs_btree_node *node; if (level == nilfs_btree_height(btree) - 1) { node = nilfs_btree_get_root(btree); *ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX; } else { node = nilfs_btree_get_nonroot_node(path, level); *ncmaxp = nilfs_btree_nchildren_per_block(btree); } return node; |
17c76b010
|
395 |
} |
7c397a81f
|
396 |
static int |
9b945d537
|
397 398 399 400 401 402 403 404 405 406 407 |
nilfs_btree_bad_node(struct nilfs_btree_node *node, int level) { if (unlikely(nilfs_btree_node_get_level(node) != level)) { dump_stack(); printk(KERN_CRIT "NILFS: btree level mismatch: %d != %d ", nilfs_btree_node_get_level(node), level); return 1; } return 0; } |
464ece886
|
408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 |
struct nilfs_btree_readahead_info { struct nilfs_btree_node *node; /* parent node */ int max_ra_blocks; /* max nof blocks to read ahead */ int index; /* current index on the parent node */ int ncmax; /* nof children in the parent node */ }; static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr, struct buffer_head **bhp, const struct nilfs_btree_readahead_info *ra) { struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache; struct buffer_head *bh, *ra_bh; sector_t submit_ptr = 0; int ret; ret = nilfs_btnode_submit_block(btnc, ptr, 0, READ, &bh, &submit_ptr); if (ret) { if (ret != -EEXIST) return ret; goto out_check; } if (ra) { int i, n; __u64 ptr2; /* read ahead sibling nodes */ for (n = ra->max_ra_blocks, i = ra->index + 1; n > 0 && i < ra->ncmax; n--, i++) { ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax); ret = nilfs_btnode_submit_block(btnc, ptr2, 0, READA, &ra_bh, &submit_ptr); if (likely(!ret || ret == -EEXIST)) brelse(ra_bh); else if (ret != -EBUSY) break; if (!buffer_locked(bh)) goto out_no_wait; } } wait_on_buffer(bh); out_no_wait: if (!buffer_uptodate(bh)) { brelse(bh); return -EIO; } out_check: if (nilfs_btree_broken_node_block(bh)) { clear_buffer_uptodate(bh); brelse(bh); return -EINVAL; } *bhp = bh; return 0; } static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr, struct buffer_head **bhp) { return __nilfs_btree_get_block(btree, ptr, bhp, NULL); } |
e7c274f80
|
475 |
static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree, |
17c76b010
|
476 |
struct nilfs_btree_path *path, |
03bdb5ac5
|
477 478 |
__u64 key, __u64 *ptrp, int minlevel, int readahead) |
17c76b010
|
479 480 |
{ struct nilfs_btree_node *node; |
03bdb5ac5
|
481 |
struct nilfs_btree_readahead_info p, *ra; |
17c76b010
|
482 |
__u64 ptr; |
ea64ab87c
|
483 |
int level, index, found, ncmax, ret; |
17c76b010
|
484 |
|
17c76b010
|
485 |
node = nilfs_btree_get_root(btree); |
6d28f7ea4
|
486 487 |
level = nilfs_btree_node_get_level(node); if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) |
17c76b010
|
488 |
return -ENOENT; |
6d28f7ea4
|
489 |
found = nilfs_btree_node_lookup(node, key, &index); |
9b7b265c9
|
490 491 |
ptr = nilfs_btree_node_get_ptr(node, index, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010
|
492 493 |
path[level].bp_bh = NULL; path[level].bp_index = index; |
9b7b265c9
|
494 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
ea64ab87c
|
495 |
|
03bdb5ac5
|
496 497 498 499 500 501 502 503 504 505 506 |
while (--level >= minlevel) { ra = NULL; if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) { p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); p.index = index; p.max_ra_blocks = 7; ra = &p; } ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh, ra); |
17c76b010
|
507 508 |
if (ret < 0) return ret; |
03bdb5ac5
|
509 |
|
6d28f7ea4
|
510 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b945d537
|
511 512 |
if (nilfs_btree_bad_node(node, level)) return -EINVAL; |
17c76b010
|
513 |
if (!found) |
6d28f7ea4
|
514 |
found = nilfs_btree_node_lookup(node, key, &index); |
17c76b010
|
515 516 |
else index = 0; |
ea64ab87c
|
517 |
if (index < ncmax) { |
9b7b265c9
|
518 |
ptr = nilfs_btree_node_get_ptr(node, index, ncmax); |
ea64ab87c
|
519 |
} else { |
1f5abe7e7
|
520 |
WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); |
17c76b010
|
521 522 523 524 525 526 527 528 529 530 531 532 533 |
/* insert */ ptr = NILFS_BMAP_INVALID_PTR; } path[level].bp_index = index; } if (!found) return -ENOENT; if (ptrp != NULL) *ptrp = ptr; return 0; } |
e7c274f80
|
534 |
static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree, |
17c76b010
|
535 536 537 538 539 |
struct nilfs_btree_path *path, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node; __u64 ptr; |
9b7b265c9
|
540 |
int index, level, ncmax, ret; |
17c76b010
|
541 542 |
node = nilfs_btree_get_root(btree); |
6d28f7ea4
|
543 |
index = nilfs_btree_node_get_nchildren(node) - 1; |
17c76b010
|
544 545 |
if (index < 0) return -ENOENT; |
6d28f7ea4
|
546 |
level = nilfs_btree_node_get_level(node); |
9b7b265c9
|
547 548 |
ptr = nilfs_btree_node_get_ptr(node, index, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010
|
549 550 |
path[level].bp_bh = NULL; path[level].bp_index = index; |
9b7b265c9
|
551 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
552 553 |
for (level--; level > 0; level--) { |
f198dbb9c
|
554 |
ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); |
17c76b010
|
555 556 |
if (ret < 0) return ret; |
6d28f7ea4
|
557 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b945d537
|
558 559 |
if (nilfs_btree_bad_node(node, level)) return -EINVAL; |
6d28f7ea4
|
560 |
index = nilfs_btree_node_get_nchildren(node) - 1; |
9b7b265c9
|
561 |
ptr = nilfs_btree_node_get_ptr(node, index, ncmax); |
17c76b010
|
562 563 564 565 |
path[level].bp_index = index; } if (keyp != NULL) |
6d28f7ea4
|
566 |
*keyp = nilfs_btree_node_get_key(node, index); |
17c76b010
|
567 568 569 570 571 |
if (ptrp != NULL) *ptrp = ptr; return 0; } |
e7c274f80
|
572 |
static int nilfs_btree_lookup(const struct nilfs_bmap *btree, |
17c76b010
|
573 574 |
__u64 key, int level, __u64 *ptrp) { |
17c76b010
|
575 |
struct nilfs_btree_path *path; |
17c76b010
|
576 |
int ret; |
6d28f7ea4
|
577 |
path = nilfs_btree_alloc_path(); |
17c76b010
|
578 579 |
if (path == NULL) return -ENOMEM; |
17c76b010
|
580 |
|
03bdb5ac5
|
581 |
ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0); |
17c76b010
|
582 |
|
6d28f7ea4
|
583 |
nilfs_btree_free_path(path); |
17c76b010
|
584 585 586 |
return ret; } |
e7c274f80
|
587 |
static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree, |
c3a7abf06
|
588 589 |
__u64 key, __u64 *ptrp, unsigned maxblocks) { |
c3a7abf06
|
590 591 592 593 594 595 |
struct nilfs_btree_path *path; struct nilfs_btree_node *node; struct inode *dat = NULL; __u64 ptr, ptr2; sector_t blocknr; int level = NILFS_BTREE_LEVEL_NODE_MIN; |
9b7b265c9
|
596 |
int ret, cnt, index, maxlevel, ncmax; |
03bdb5ac5
|
597 |
struct nilfs_btree_readahead_info p; |
c3a7abf06
|
598 |
|
6d28f7ea4
|
599 |
path = nilfs_btree_alloc_path(); |
c3a7abf06
|
600 601 |
if (path == NULL) return -ENOMEM; |
f905440f5
|
602 |
|
03bdb5ac5
|
603 |
ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1); |
c3a7abf06
|
604 605 |
if (ret < 0) goto out; |
e7c274f80
|
606 607 |
if (NILFS_BMAP_USE_VBN(btree)) { dat = nilfs_bmap_get_dat(btree); |
c3a7abf06
|
608 609 610 611 612 613 614 615 616 617 |
ret = nilfs_dat_translate(dat, ptr, &blocknr); if (ret < 0) goto out; ptr = blocknr; } cnt = 1; if (cnt == maxblocks) goto end; maxlevel = nilfs_btree_height(btree) - 1; |
9b7b265c9
|
618 |
node = nilfs_btree_get_node(btree, path, level, &ncmax); |
c3a7abf06
|
619 620 |
index = path[level].bp_index + 1; for (;;) { |
6d28f7ea4
|
621 622 |
while (index < nilfs_btree_node_get_nchildren(node)) { if (nilfs_btree_node_get_key(node, index) != |
c3a7abf06
|
623 624 |
key + cnt) goto end; |
9b7b265c9
|
625 |
ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax); |
c3a7abf06
|
626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 |
if (dat) { ret = nilfs_dat_translate(dat, ptr2, &blocknr); if (ret < 0) goto out; ptr2 = blocknr; } if (ptr2 != ptr + cnt || ++cnt == maxblocks) goto end; index++; continue; } if (level == maxlevel) break; /* look-up right sibling node */ |
03bdb5ac5
|
641 642 643 644 645 |
p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); p.index = path[level + 1].bp_index + 1; p.max_ra_blocks = 7; if (p.index >= nilfs_btree_node_get_nchildren(p.node) || nilfs_btree_node_get_key(p.node, p.index) != key + cnt) |
c3a7abf06
|
646 |
break; |
03bdb5ac5
|
647 648 |
ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax); path[level + 1].bp_index = p.index; |
c3a7abf06
|
649 650 651 |
brelse(path[level].bp_bh); path[level].bp_bh = NULL; |
03bdb5ac5
|
652 653 654 |
ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh, &p); |
c3a7abf06
|
655 656 |
if (ret < 0) goto out; |
6d28f7ea4
|
657 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9
|
658 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
c3a7abf06
|
659 660 661 662 663 664 665 |
index = 0; path[level].bp_index = index; } end: *ptrp = ptr; ret = cnt; out: |
6d28f7ea4
|
666 |
nilfs_btree_free_path(path); |
c3a7abf06
|
667 668 |
return ret; } |
e7c274f80
|
669 |
static void nilfs_btree_promote_key(struct nilfs_bmap *btree, |
17c76b010
|
670 671 672 673 674 |
struct nilfs_btree_path *path, int level, __u64 key) { if (level < nilfs_btree_height(btree) - 1) { do { |
17c76b010
|
675 |
nilfs_btree_node_set_key( |
6d28f7ea4
|
676 |
nilfs_btree_get_nonroot_node(path, level), |
17c76b010
|
677 678 |
path[level].bp_index, key); if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
679 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
680 681 682 683 684 685 |
} while ((path[level].bp_index == 0) && (++level < nilfs_btree_height(btree) - 1)); } /* root */ if (level == nilfs_btree_height(btree) - 1) { |
6d28f7ea4
|
686 |
nilfs_btree_node_set_key(nilfs_btree_get_root(btree), |
17c76b010
|
687 688 689 |
path[level].bp_index, key); } } |
e7c274f80
|
690 |
static void nilfs_btree_do_insert(struct nilfs_bmap *btree, |
17c76b010
|
691 692 693 694 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node; |
9b7b265c9
|
695 |
int ncblk; |
17c76b010
|
696 697 |
if (level < nilfs_btree_height(btree) - 1) { |
6d28f7ea4
|
698 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9
|
699 700 701 |
ncblk = nilfs_btree_nchildren_per_block(btree); nilfs_btree_node_insert(node, path[level].bp_index, *keyp, *ptrp, ncblk); |
17c76b010
|
702 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
703 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
704 705 706 |
if (path[level].bp_index == 0) nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4
|
707 708 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010
|
709 710 |
} else { node = nilfs_btree_get_root(btree); |
9b7b265c9
|
711 712 713 |
nilfs_btree_node_insert(node, path[level].bp_index, *keyp, *ptrp, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010
|
714 715 |
} } |
e7c274f80
|
716 |
static void nilfs_btree_carry_left(struct nilfs_bmap *btree, |
17c76b010
|
717 718 719 720 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *left; |
9b7b265c9
|
721 |
int nchildren, lnchildren, n, move, ncblk; |
17c76b010
|
722 |
|
6d28f7ea4
|
723 724 725 726 |
node = nilfs_btree_get_nonroot_node(path, level); left = nilfs_btree_get_sib_node(path, level); nchildren = nilfs_btree_node_get_nchildren(node); lnchildren = nilfs_btree_node_get_nchildren(left); |
9b7b265c9
|
727 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
728 729 730 731 732 733 734 735 |
move = 0; n = (nchildren + lnchildren + 1) / 2 - lnchildren; if (n > path[level].bp_index) { /* move insert point */ n--; move = 1; } |
9b7b265c9
|
736 |
nilfs_btree_node_move_left(left, node, n, ncblk, ncblk); |
17c76b010
|
737 738 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
739 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
740 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417
|
741 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010
|
742 |
|
17c76b010
|
743 |
nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4
|
744 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010
|
745 746 |
if (move) { |
087d01b42
|
747 |
brelse(path[level].bp_bh); |
17c76b010
|
748 749 750 751 752 |
path[level].bp_bh = path[level].bp_sib_bh; path[level].bp_sib_bh = NULL; path[level].bp_index += lnchildren; path[level + 1].bp_index--; } else { |
087d01b42
|
753 |
brelse(path[level].bp_sib_bh); |
17c76b010
|
754 755 756 757 758 759 |
path[level].bp_sib_bh = NULL; path[level].bp_index -= n; } nilfs_btree_do_insert(btree, path, level, keyp, ptrp); } |
e7c274f80
|
760 |
static void nilfs_btree_carry_right(struct nilfs_bmap *btree, |
17c76b010
|
761 762 763 764 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *right; |
9b7b265c9
|
765 |
int nchildren, rnchildren, n, move, ncblk; |
17c76b010
|
766 |
|
6d28f7ea4
|
767 768 769 770 |
node = nilfs_btree_get_nonroot_node(path, level); right = nilfs_btree_get_sib_node(path, level); nchildren = nilfs_btree_node_get_nchildren(node); rnchildren = nilfs_btree_node_get_nchildren(right); |
9b7b265c9
|
771 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
772 773 774 775 776 777 778 779 |
move = 0; n = (nchildren + rnchildren + 1) / 2 - rnchildren; if (n > nchildren - path[level].bp_index) { /* move insert point */ n--; move = 1; } |
9b7b265c9
|
780 |
nilfs_btree_node_move_right(node, right, n, ncblk, ncblk); |
17c76b010
|
781 782 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
783 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
784 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417
|
785 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010
|
786 |
|
17c76b010
|
787 788 |
path[level + 1].bp_index++; nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4
|
789 |
nilfs_btree_node_get_key(right, 0)); |
17c76b010
|
790 791 792 |
path[level + 1].bp_index--; if (move) { |
087d01b42
|
793 |
brelse(path[level].bp_bh); |
17c76b010
|
794 795 |
path[level].bp_bh = path[level].bp_sib_bh; path[level].bp_sib_bh = NULL; |
6d28f7ea4
|
796 |
path[level].bp_index -= nilfs_btree_node_get_nchildren(node); |
17c76b010
|
797 798 |
path[level + 1].bp_index++; } else { |
087d01b42
|
799 |
brelse(path[level].bp_sib_bh); |
17c76b010
|
800 801 802 803 804 |
path[level].bp_sib_bh = NULL; } nilfs_btree_do_insert(btree, path, level, keyp, ptrp); } |
e7c274f80
|
805 |
static void nilfs_btree_split(struct nilfs_bmap *btree, |
17c76b010
|
806 807 808 809 810 811 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *right; __u64 newkey; __u64 newptr; |
9b7b265c9
|
812 |
int nchildren, n, move, ncblk; |
17c76b010
|
813 |
|
6d28f7ea4
|
814 815 816 |
node = nilfs_btree_get_nonroot_node(path, level); right = nilfs_btree_get_sib_node(path, level); nchildren = nilfs_btree_node_get_nchildren(node); |
9b7b265c9
|
817 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
818 819 820 821 822 823 824 |
move = 0; n = (nchildren + 1) / 2; if (n > nchildren - path[level].bp_index) { n--; move = 1; } |
9b7b265c9
|
825 |
nilfs_btree_node_move_right(node, right, n, ncblk, ncblk); |
17c76b010
|
826 827 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
828 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
829 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417
|
830 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010
|
831 |
|
6d28f7ea4
|
832 |
newkey = nilfs_btree_node_get_key(right, 0); |
17c76b010
|
833 834 835 |
newptr = path[level].bp_newreq.bpr_ptr; if (move) { |
6d28f7ea4
|
836 |
path[level].bp_index -= nilfs_btree_node_get_nchildren(node); |
9b7b265c9
|
837 838 |
nilfs_btree_node_insert(right, path[level].bp_index, *keyp, *ptrp, ncblk); |
17c76b010
|
839 |
|
6d28f7ea4
|
840 |
*keyp = nilfs_btree_node_get_key(right, 0); |
17c76b010
|
841 |
*ptrp = path[level].bp_newreq.bpr_ptr; |
087d01b42
|
842 |
brelse(path[level].bp_bh); |
17c76b010
|
843 844 845 846 |
path[level].bp_bh = path[level].bp_sib_bh; path[level].bp_sib_bh = NULL; } else { nilfs_btree_do_insert(btree, path, level, keyp, ptrp); |
6d28f7ea4
|
847 |
*keyp = nilfs_btree_node_get_key(right, 0); |
17c76b010
|
848 |
*ptrp = path[level].bp_newreq.bpr_ptr; |
087d01b42
|
849 |
brelse(path[level].bp_sib_bh); |
17c76b010
|
850 851 852 853 854 |
path[level].bp_sib_bh = NULL; } path[level + 1].bp_index++; } |
e7c274f80
|
855 |
static void nilfs_btree_grow(struct nilfs_bmap *btree, |
17c76b010
|
856 857 858 859 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *root, *child; |
9b7b265c9
|
860 |
int n, ncblk; |
17c76b010
|
861 |
|
17c76b010
|
862 |
root = nilfs_btree_get_root(btree); |
6d28f7ea4
|
863 |
child = nilfs_btree_get_sib_node(path, level); |
9b7b265c9
|
864 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
865 |
|
6d28f7ea4
|
866 |
n = nilfs_btree_node_get_nchildren(root); |
17c76b010
|
867 |
|
9b7b265c9
|
868 869 |
nilfs_btree_node_move_right(root, child, n, NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk); |
6d28f7ea4
|
870 |
nilfs_btree_node_set_level(root, level + 1); |
17c76b010
|
871 872 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417
|
873 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010
|
874 |
|
17c76b010
|
875 876 877 878 |
path[level].bp_bh = path[level].bp_sib_bh; path[level].bp_sib_bh = NULL; nilfs_btree_do_insert(btree, path, level, keyp, ptrp); |
6d28f7ea4
|
879 |
*keyp = nilfs_btree_node_get_key(child, 0); |
17c76b010
|
880 881 |
*ptrp = path[level].bp_newreq.bpr_ptr; } |
e7c274f80
|
882 |
static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree, |
17c76b010
|
883 884 885 |
const struct nilfs_btree_path *path) { struct nilfs_btree_node *node; |
9b7b265c9
|
886 |
int level, ncmax; |
17c76b010
|
887 888 889 890 891 892 893 |
if (path == NULL) return NILFS_BMAP_INVALID_PTR; /* left sibling */ level = NILFS_BTREE_LEVEL_NODE_MIN; if (path[level].bp_index > 0) { |
9b7b265c9
|
894 895 896 897 |
node = nilfs_btree_get_node(btree, path, level, &ncmax); return nilfs_btree_node_get_ptr(node, path[level].bp_index - 1, ncmax); |
17c76b010
|
898 899 900 901 902 |
} /* parent */ level = NILFS_BTREE_LEVEL_NODE_MIN + 1; if (level <= nilfs_btree_height(btree) - 1) { |
9b7b265c9
|
903 904 905 |
node = nilfs_btree_get_node(btree, path, level, &ncmax); return nilfs_btree_node_get_ptr(node, path[level].bp_index, ncmax); |
17c76b010
|
906 907 908 909 |
} return NILFS_BMAP_INVALID_PTR; } |
e7c274f80
|
910 |
static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree, |
17c76b010
|
911 912 913 914 |
const struct nilfs_btree_path *path, __u64 key) { __u64 ptr; |
e7c274f80
|
915 |
ptr = nilfs_bmap_find_target_seq(btree, key); |
17c76b010
|
916 917 918 919 920 921 922 923 924 925 |
if (ptr != NILFS_BMAP_INVALID_PTR) /* sequential access */ return ptr; else { ptr = nilfs_btree_find_near(btree, path); if (ptr != NILFS_BMAP_INVALID_PTR) /* near */ return ptr; } /* block group */ |
e7c274f80
|
926 |
return nilfs_bmap_find_target_in_group(btree); |
17c76b010
|
927 |
} |
e7c274f80
|
928 |
static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree, |
17c76b010
|
929 930 931 932 933 934 935 |
struct nilfs_btree_path *path, int *levelp, __u64 key, __u64 ptr, struct nilfs_bmap_stats *stats) { struct buffer_head *bh; struct nilfs_btree_node *node, *parent, *sib; __u64 sibptr; |
9b7b265c9
|
936 |
int pindex, level, ncmax, ncblk, ret; |
2e0c2c739
|
937 |
struct inode *dat = NULL; |
17c76b010
|
938 939 940 941 942 |
stats->bs_nblocks = 0; level = NILFS_BTREE_LEVEL_DATA; /* allocate a new ptr for data block */ |
e7c274f80
|
943 |
if (NILFS_BMAP_USE_VBN(btree)) { |
17c76b010
|
944 |
path[level].bp_newreq.bpr_ptr = |
7cde31d7d
|
945 |
nilfs_btree_find_target_v(btree, path, key); |
e7c274f80
|
946 |
dat = nilfs_bmap_get_dat(btree); |
2e0c2c739
|
947 |
} |
17c76b010
|
948 |
|
e7c274f80
|
949 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010
|
950 951 |
if (ret < 0) goto err_out_data; |
9b7b265c9
|
952 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
ea64ab87c
|
953 |
|
17c76b010
|
954 955 956 |
for (level = NILFS_BTREE_LEVEL_NODE_MIN; level < nilfs_btree_height(btree) - 1; level++) { |
6d28f7ea4
|
957 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9
|
958 |
if (nilfs_btree_node_get_nchildren(node) < ncblk) { |
17c76b010
|
959 960 961 962 |
path[level].bp_op = nilfs_btree_do_insert; stats->bs_nblocks++; goto out; } |
9b7b265c9
|
963 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); |
17c76b010
|
964 965 966 967 |
pindex = path[level + 1].bp_index; /* left sibling */ if (pindex > 0) { |
9b7b265c9
|
968 969 |
sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1, ncmax); |
f198dbb9c
|
970 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010
|
971 972 973 |
if (ret < 0) goto err_out_child_node; sib = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9
|
974 |
if (nilfs_btree_node_get_nchildren(sib) < ncblk) { |
17c76b010
|
975 976 977 978 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_carry_left; stats->bs_nblocks++; goto out; |
9b7b265c9
|
979 |
} else { |
087d01b42
|
980 |
brelse(bh); |
9b7b265c9
|
981 |
} |
17c76b010
|
982 983 984 |
} /* right sibling */ |
9b7b265c9
|
985 986 987 |
if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) { sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1, ncmax); |
f198dbb9c
|
988 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010
|
989 990 991 |
if (ret < 0) goto err_out_child_node; sib = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9
|
992 |
if (nilfs_btree_node_get_nchildren(sib) < ncblk) { |
17c76b010
|
993 994 995 996 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_carry_right; stats->bs_nblocks++; goto out; |
9b7b265c9
|
997 |
} else { |
087d01b42
|
998 |
brelse(bh); |
9b7b265c9
|
999 |
} |
17c76b010
|
1000 1001 1002 1003 1004 |
} /* split */ path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; |
e7c274f80
|
1005 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, |
2e0c2c739
|
1006 |
&path[level].bp_newreq, dat); |
17c76b010
|
1007 1008 |
if (ret < 0) goto err_out_child_node; |
f198dbb9c
|
1009 1010 1011 |
ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, &bh); |
17c76b010
|
1012 1013 1014 1015 |
if (ret < 0) goto err_out_curr_node; stats->bs_nblocks++; |
9b7b265c9
|
1016 1017 |
sib = (struct nilfs_btree_node *)bh->b_data; nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL); |
17c76b010
|
1018 1019 1020 1021 1022 1023 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_split; } /* root */ node = nilfs_btree_get_root(btree); |
6d28f7ea4
|
1024 |
if (nilfs_btree_node_get_nchildren(node) < |
ea64ab87c
|
1025 |
NILFS_BTREE_ROOT_NCHILDREN_MAX) { |
17c76b010
|
1026 1027 1028 1029 1030 1031 1032 |
path[level].bp_op = nilfs_btree_do_insert; stats->bs_nblocks++; goto out; } /* grow */ path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; |
e7c274f80
|
1033 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010
|
1034 1035 |
if (ret < 0) goto err_out_child_node; |
f198dbb9c
|
1036 1037 |
ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, &bh); |
17c76b010
|
1038 1039 |
if (ret < 0) goto err_out_curr_node; |
9b7b265c9
|
1040 1041 |
nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data, 0, level, 0, ncblk, NULL, NULL); |
17c76b010
|
1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_grow; level++; path[level].bp_op = nilfs_btree_do_insert; /* a newly-created node block and a data block are added */ stats->bs_nblocks += 2; /* success */ out: *levelp = level; return ret; /* error */ err_out_curr_node: |
e7c274f80
|
1058 |
nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010
|
1059 1060 |
err_out_child_node: for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { |
9f098900a
|
1061 |
nilfs_btnode_delete(path[level].bp_sib_bh); |
e7c274f80
|
1062 |
nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010
|
1063 1064 |
} |
e7c274f80
|
1065 |
nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010
|
1066 1067 1068 1069 1070 |
err_out_data: *levelp = level; stats->bs_nblocks = 0; return ret; } |
e7c274f80
|
1071 |
static void nilfs_btree_commit_insert(struct nilfs_bmap *btree, |
17c76b010
|
1072 1073 1074 |
struct nilfs_btree_path *path, int maxlevel, __u64 key, __u64 ptr) { |
2e0c2c739
|
1075 |
struct inode *dat = NULL; |
17c76b010
|
1076 1077 1078 1079 |
int level; set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr)); ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr; |
e7c274f80
|
1080 |
if (NILFS_BMAP_USE_VBN(btree)) { |
dc935be2a
|
1081 |
nilfs_bmap_set_target_v(btree, key, ptr); |
e7c274f80
|
1082 |
dat = nilfs_bmap_get_dat(btree); |
2e0c2c739
|
1083 |
} |
17c76b010
|
1084 1085 |
for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { |
e7c274f80
|
1086 |
nilfs_bmap_commit_alloc_ptr(btree, |
2e0c2c739
|
1087 |
&path[level - 1].bp_newreq, dat); |
8acfbf093
|
1088 |
path[level].bp_op(btree, path, level, &key, &ptr); |
17c76b010
|
1089 |
} |
e7c274f80
|
1090 1091 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010
|
1092 |
} |
e7c274f80
|
1093 |
static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr) |
17c76b010
|
1094 |
{ |
17c76b010
|
1095 1096 1097 |
struct nilfs_btree_path *path; struct nilfs_bmap_stats stats; int level, ret; |
6d28f7ea4
|
1098 |
path = nilfs_btree_alloc_path(); |
17c76b010
|
1099 1100 |
if (path == NULL) return -ENOMEM; |
17c76b010
|
1101 1102 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, |
03bdb5ac5
|
1103 |
NILFS_BTREE_LEVEL_NODE_MIN, 0); |
17c76b010
|
1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 |
if (ret != -ENOENT) { if (ret == 0) ret = -EEXIST; goto out; } ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats); if (ret < 0) goto out; nilfs_btree_commit_insert(btree, path, level, key, ptr); |
be667377a
|
1114 |
nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks); |
17c76b010
|
1115 1116 |
out: |
6d28f7ea4
|
1117 |
nilfs_btree_free_path(path); |
17c76b010
|
1118 1119 |
return ret; } |
e7c274f80
|
1120 |
static void nilfs_btree_do_delete(struct nilfs_bmap *btree, |
17c76b010
|
1121 1122 1123 1124 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node; |
9b7b265c9
|
1125 |
int ncblk; |
17c76b010
|
1126 1127 |
if (level < nilfs_btree_height(btree) - 1) { |
6d28f7ea4
|
1128 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9
|
1129 1130 1131 |
ncblk = nilfs_btree_nchildren_per_block(btree); nilfs_btree_node_delete(node, path[level].bp_index, keyp, ptrp, ncblk); |
17c76b010
|
1132 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
1133 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
1134 1135 |
if (path[level].bp_index == 0) nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4
|
1136 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010
|
1137 1138 |
} else { node = nilfs_btree_get_root(btree); |
9b7b265c9
|
1139 1140 1141 |
nilfs_btree_node_delete(node, path[level].bp_index, keyp, ptrp, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010
|
1142 1143 |
} } |
e7c274f80
|
1144 |
static void nilfs_btree_borrow_left(struct nilfs_bmap *btree, |
17c76b010
|
1145 1146 1147 1148 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *left; |
9b7b265c9
|
1149 |
int nchildren, lnchildren, n, ncblk; |
17c76b010
|
1150 1151 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4
|
1152 1153 1154 1155 |
node = nilfs_btree_get_nonroot_node(path, level); left = nilfs_btree_get_sib_node(path, level); nchildren = nilfs_btree_node_get_nchildren(node); lnchildren = nilfs_btree_node_get_nchildren(left); |
9b7b265c9
|
1156 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
1157 1158 |
n = (nchildren + lnchildren) / 2 - nchildren; |
9b7b265c9
|
1159 |
nilfs_btree_node_move_right(left, node, n, ncblk, ncblk); |
17c76b010
|
1160 1161 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
1162 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
1163 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417
|
1164 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010
|
1165 |
|
17c76b010
|
1166 |
nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4
|
1167 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010
|
1168 |
|
087d01b42
|
1169 |
brelse(path[level].bp_sib_bh); |
17c76b010
|
1170 1171 1172 |
path[level].bp_sib_bh = NULL; path[level].bp_index += n; } |
e7c274f80
|
1173 |
static void nilfs_btree_borrow_right(struct nilfs_bmap *btree, |
17c76b010
|
1174 1175 1176 1177 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *right; |
9b7b265c9
|
1178 |
int nchildren, rnchildren, n, ncblk; |
17c76b010
|
1179 1180 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4
|
1181 1182 1183 1184 |
node = nilfs_btree_get_nonroot_node(path, level); right = nilfs_btree_get_sib_node(path, level); nchildren = nilfs_btree_node_get_nchildren(node); rnchildren = nilfs_btree_node_get_nchildren(right); |
9b7b265c9
|
1185 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
1186 1187 |
n = (nchildren + rnchildren) / 2 - nchildren; |
9b7b265c9
|
1188 |
nilfs_btree_node_move_left(node, right, n, ncblk, ncblk); |
17c76b010
|
1189 1190 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
1191 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
1192 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417
|
1193 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010
|
1194 |
|
17c76b010
|
1195 1196 |
path[level + 1].bp_index++; nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4
|
1197 |
nilfs_btree_node_get_key(right, 0)); |
17c76b010
|
1198 |
path[level + 1].bp_index--; |
087d01b42
|
1199 |
brelse(path[level].bp_sib_bh); |
17c76b010
|
1200 1201 |
path[level].bp_sib_bh = NULL; } |
e7c274f80
|
1202 |
static void nilfs_btree_concat_left(struct nilfs_bmap *btree, |
17c76b010
|
1203 1204 1205 1206 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *left; |
9b7b265c9
|
1207 |
int n, ncblk; |
17c76b010
|
1208 1209 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4
|
1210 1211 |
node = nilfs_btree_get_nonroot_node(path, level); left = nilfs_btree_get_sib_node(path, level); |
9b7b265c9
|
1212 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
1213 |
|
6d28f7ea4
|
1214 |
n = nilfs_btree_node_get_nchildren(node); |
17c76b010
|
1215 |
|
9b7b265c9
|
1216 |
nilfs_btree_node_move_left(left, node, n, ncblk, ncblk); |
17c76b010
|
1217 1218 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417
|
1219 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010
|
1220 |
|
9f098900a
|
1221 |
nilfs_btnode_delete(path[level].bp_bh); |
17c76b010
|
1222 1223 |
path[level].bp_bh = path[level].bp_sib_bh; path[level].bp_sib_bh = NULL; |
6d28f7ea4
|
1224 |
path[level].bp_index += nilfs_btree_node_get_nchildren(left); |
17c76b010
|
1225 |
} |
e7c274f80
|
1226 |
static void nilfs_btree_concat_right(struct nilfs_bmap *btree, |
17c76b010
|
1227 1228 1229 1230 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *right; |
9b7b265c9
|
1231 |
int n, ncblk; |
17c76b010
|
1232 1233 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4
|
1234 1235 |
node = nilfs_btree_get_nonroot_node(path, level); right = nilfs_btree_get_sib_node(path, level); |
9b7b265c9
|
1236 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
1237 |
|
6d28f7ea4
|
1238 |
n = nilfs_btree_node_get_nchildren(right); |
17c76b010
|
1239 |
|
9b7b265c9
|
1240 |
nilfs_btree_node_move_left(node, right, n, ncblk, ncblk); |
17c76b010
|
1241 1242 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
1243 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
1244 |
|
9f098900a
|
1245 |
nilfs_btnode_delete(path[level].bp_sib_bh); |
17c76b010
|
1246 1247 1248 |
path[level].bp_sib_bh = NULL; path[level + 1].bp_index++; } |
e7c274f80
|
1249 |
static void nilfs_btree_shrink(struct nilfs_bmap *btree, |
17c76b010
|
1250 1251 1252 1253 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *root, *child; |
9b7b265c9
|
1254 |
int n, ncblk; |
17c76b010
|
1255 1256 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
17c76b010
|
1257 |
root = nilfs_btree_get_root(btree); |
6d28f7ea4
|
1258 |
child = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9
|
1259 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
1260 |
|
9b7b265c9
|
1261 1262 |
nilfs_btree_node_delete(root, 0, NULL, NULL, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
6d28f7ea4
|
1263 1264 |
nilfs_btree_node_set_level(root, level); n = nilfs_btree_node_get_nchildren(child); |
9b7b265c9
|
1265 1266 |
nilfs_btree_node_move_left(root, child, n, NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk); |
17c76b010
|
1267 |
|
9f098900a
|
1268 |
nilfs_btnode_delete(path[level].bp_bh); |
17c76b010
|
1269 1270 |
path[level].bp_bh = NULL; } |
d40990537
|
1271 1272 1273 1274 1275 |
static void nilfs_btree_nop(struct nilfs_bmap *btree, struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { } |
17c76b010
|
1276 |
|
e7c274f80
|
1277 |
static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree, |
17c76b010
|
1278 1279 |
struct nilfs_btree_path *path, int *levelp, |
2e0c2c739
|
1280 1281 |
struct nilfs_bmap_stats *stats, struct inode *dat) |
17c76b010
|
1282 1283 1284 1285 |
{ struct buffer_head *bh; struct nilfs_btree_node *node, *parent, *sib; __u64 sibptr; |
fe744fdb7
|
1286 |
int pindex, dindex, level, ncmin, ncmax, ncblk, ret; |
17c76b010
|
1287 1288 1289 |
ret = 0; stats->bs_nblocks = 0; |
ea64ab87c
|
1290 |
ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree)); |
9b7b265c9
|
1291 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
ea64ab87c
|
1292 |
|
fe744fdb7
|
1293 |
for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index; |
17c76b010
|
1294 1295 |
level < nilfs_btree_height(btree) - 1; level++) { |
6d28f7ea4
|
1296 |
node = nilfs_btree_get_nonroot_node(path, level); |
17c76b010
|
1297 |
path[level].bp_oldreq.bpr_ptr = |
fe744fdb7
|
1298 |
nilfs_btree_node_get_ptr(node, dindex, ncblk); |
e7c274f80
|
1299 |
ret = nilfs_bmap_prepare_end_ptr(btree, |
2e0c2c739
|
1300 |
&path[level].bp_oldreq, dat); |
d4b961576
|
1301 1302 |
if (ret < 0) goto err_out_child_node; |
17c76b010
|
1303 |
|
ea64ab87c
|
1304 |
if (nilfs_btree_node_get_nchildren(node) > ncmin) { |
17c76b010
|
1305 1306 1307 1308 |
path[level].bp_op = nilfs_btree_do_delete; stats->bs_nblocks++; goto out; } |
9b7b265c9
|
1309 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); |
17c76b010
|
1310 |
pindex = path[level + 1].bp_index; |
fe744fdb7
|
1311 |
dindex = pindex; |
17c76b010
|
1312 1313 1314 |
if (pindex > 0) { /* left sibling */ |
9b7b265c9
|
1315 1316 |
sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1, ncmax); |
f198dbb9c
|
1317 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010
|
1318 1319 1320 |
if (ret < 0) goto err_out_curr_node; sib = (struct nilfs_btree_node *)bh->b_data; |
ea64ab87c
|
1321 |
if (nilfs_btree_node_get_nchildren(sib) > ncmin) { |
17c76b010
|
1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_borrow_left; stats->bs_nblocks++; goto out; } else { path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_concat_left; stats->bs_nblocks++; /* continue; */ } } else if (pindex < |
6d28f7ea4
|
1333 |
nilfs_btree_node_get_nchildren(parent) - 1) { |
17c76b010
|
1334 |
/* right sibling */ |
9b7b265c9
|
1335 1336 |
sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1, ncmax); |
f198dbb9c
|
1337 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010
|
1338 1339 1340 |
if (ret < 0) goto err_out_curr_node; sib = (struct nilfs_btree_node *)bh->b_data; |
ea64ab87c
|
1341 |
if (nilfs_btree_node_get_nchildren(sib) > ncmin) { |
17c76b010
|
1342 1343 1344 1345 1346 1347 1348 1349 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_borrow_right; stats->bs_nblocks++; goto out; } else { path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_concat_right; stats->bs_nblocks++; |
fe744fdb7
|
1350 1351 1352 1353 1354 1355 1356 1357 |
/* * When merging right sibling node * into the current node, pointer to * the right sibling node must be * terminated instead. The adjustment * below is required for that. */ dindex = pindex + 1; |
17c76b010
|
1358 1359 1360 1361 1362 |
/* continue; */ } } else { /* no siblings */ /* the only child of the root node */ |
1f5abe7e7
|
1363 |
WARN_ON(level != nilfs_btree_height(btree) - 2); |
6d28f7ea4
|
1364 |
if (nilfs_btree_node_get_nchildren(node) - 1 <= |
17c76b010
|
1365 1366 1367 |
NILFS_BTREE_ROOT_NCHILDREN_MAX) { path[level].bp_op = nilfs_btree_shrink; stats->bs_nblocks += 2; |
d40990537
|
1368 1369 1370 |
level++; path[level].bp_op = nilfs_btree_nop; goto shrink_root_child; |
17c76b010
|
1371 1372 1373 |
} else { path[level].bp_op = nilfs_btree_do_delete; stats->bs_nblocks++; |
d40990537
|
1374 |
goto out; |
17c76b010
|
1375 |
} |
17c76b010
|
1376 1377 |
} } |
d40990537
|
1378 1379 1380 1381 1382 |
/* child of the root node is deleted */ path[level].bp_op = nilfs_btree_do_delete; stats->bs_nblocks++; shrink_root_child: |
17c76b010
|
1383 1384 |
node = nilfs_btree_get_root(btree); path[level].bp_oldreq.bpr_ptr = |
fe744fdb7
|
1385 |
nilfs_btree_node_get_ptr(node, dindex, |
9b7b265c9
|
1386 |
NILFS_BTREE_ROOT_NCHILDREN_MAX); |
d4b961576
|
1387 |
|
e7c274f80
|
1388 |
ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat); |
d4b961576
|
1389 1390 |
if (ret < 0) goto err_out_child_node; |
17c76b010
|
1391 1392 1393 1394 1395 1396 1397 |
/* success */ out: *levelp = level; return ret; /* error */ err_out_curr_node: |
e7c274f80
|
1398 |
nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); |
17c76b010
|
1399 1400 |
err_out_child_node: for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { |
087d01b42
|
1401 |
brelse(path[level].bp_sib_bh); |
e7c274f80
|
1402 |
nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); |
17c76b010
|
1403 1404 1405 1406 1407 |
} *levelp = level; stats->bs_nblocks = 0; return ret; } |
e7c274f80
|
1408 |
static void nilfs_btree_commit_delete(struct nilfs_bmap *btree, |
17c76b010
|
1409 |
struct nilfs_btree_path *path, |
2e0c2c739
|
1410 |
int maxlevel, struct inode *dat) |
17c76b010
|
1411 1412 1413 1414 |
{ int level; for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { |
e7c274f80
|
1415 |
nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat); |
8acfbf093
|
1416 |
path[level].bp_op(btree, path, level, NULL, NULL); |
17c76b010
|
1417 |
} |
e7c274f80
|
1418 1419 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010
|
1420 |
} |
e7c274f80
|
1421 |
static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key) |
17c76b010
|
1422 1423 |
{ |
17c76b010
|
1424 1425 |
struct nilfs_btree_path *path; struct nilfs_bmap_stats stats; |
2e0c2c739
|
1426 |
struct inode *dat; |
17c76b010
|
1427 |
int level, ret; |
6d28f7ea4
|
1428 |
path = nilfs_btree_alloc_path(); |
17c76b010
|
1429 1430 |
if (path == NULL) return -ENOMEM; |
f905440f5
|
1431 |
|
17c76b010
|
1432 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, |
03bdb5ac5
|
1433 |
NILFS_BTREE_LEVEL_NODE_MIN, 0); |
17c76b010
|
1434 1435 |
if (ret < 0) goto out; |
2e0c2c739
|
1436 |
|
e7c274f80
|
1437 |
dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL; |
2e0c2c739
|
1438 1439 |
ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); |
17c76b010
|
1440 1441 |
if (ret < 0) goto out; |
2e0c2c739
|
1442 |
nilfs_btree_commit_delete(btree, path, level, dat); |
be667377a
|
1443 |
nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks); |
17c76b010
|
1444 1445 |
out: |
6d28f7ea4
|
1446 |
nilfs_btree_free_path(path); |
17c76b010
|
1447 1448 |
return ret; } |
e7c274f80
|
1449 |
static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp) |
17c76b010
|
1450 |
{ |
17c76b010
|
1451 1452 |
struct nilfs_btree_path *path; int ret; |
6d28f7ea4
|
1453 |
path = nilfs_btree_alloc_path(); |
17c76b010
|
1454 1455 |
if (path == NULL) return -ENOMEM; |
17c76b010
|
1456 1457 |
ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL); |
6d28f7ea4
|
1458 |
nilfs_btree_free_path(path); |
17c76b010
|
1459 1460 1461 |
return ret; } |
e7c274f80
|
1462 |
static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key) |
17c76b010
|
1463 1464 |
{ struct buffer_head *bh; |
17c76b010
|
1465 1466 1467 1468 |
struct nilfs_btree_node *root, *node; __u64 maxkey, nextmaxkey; __u64 ptr; int nchildren, ret; |
17c76b010
|
1469 1470 1471 1472 1473 1474 1475 |
root = nilfs_btree_get_root(btree); switch (nilfs_btree_height(btree)) { case 2: bh = NULL; node = root; break; case 3: |
6d28f7ea4
|
1476 |
nchildren = nilfs_btree_node_get_nchildren(root); |
17c76b010
|
1477 1478 |
if (nchildren > 1) return 0; |
9b7b265c9
|
1479 1480 |
ptr = nilfs_btree_node_get_ptr(root, nchildren - 1, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
f198dbb9c
|
1481 |
ret = nilfs_btree_get_block(btree, ptr, &bh); |
17c76b010
|
1482 1483 1484 1485 1486 1487 1488 |
if (ret < 0) return ret; node = (struct nilfs_btree_node *)bh->b_data; break; default: return 0; } |
6d28f7ea4
|
1489 1490 |
nchildren = nilfs_btree_node_get_nchildren(node); maxkey = nilfs_btree_node_get_key(node, nchildren - 1); |
17c76b010
|
1491 |
nextmaxkey = (nchildren > 1) ? |
6d28f7ea4
|
1492 |
nilfs_btree_node_get_key(node, nchildren - 2) : 0; |
17c76b010
|
1493 |
if (bh != NULL) |
087d01b42
|
1494 |
brelse(bh); |
17c76b010
|
1495 |
|
3033342a0
|
1496 |
return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW); |
17c76b010
|
1497 |
} |
e7c274f80
|
1498 |
static int nilfs_btree_gather_data(struct nilfs_bmap *btree, |
17c76b010
|
1499 1500 1501 |
__u64 *keys, __u64 *ptrs, int nitems) { struct buffer_head *bh; |
17c76b010
|
1502 1503 1504 1505 |
struct nilfs_btree_node *node, *root; __le64 *dkeys; __le64 *dptrs; __u64 ptr; |
9b7b265c9
|
1506 |
int nchildren, ncmax, i, ret; |
17c76b010
|
1507 |
|
17c76b010
|
1508 1509 1510 1511 1512 |
root = nilfs_btree_get_root(btree); switch (nilfs_btree_height(btree)) { case 2: bh = NULL; node = root; |
9b7b265c9
|
1513 |
ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX; |
17c76b010
|
1514 1515 |
break; case 3: |
6d28f7ea4
|
1516 |
nchildren = nilfs_btree_node_get_nchildren(root); |
1f5abe7e7
|
1517 |
WARN_ON(nchildren > 1); |
9b7b265c9
|
1518 1519 |
ptr = nilfs_btree_node_get_ptr(root, nchildren - 1, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
f198dbb9c
|
1520 |
ret = nilfs_btree_get_block(btree, ptr, &bh); |
17c76b010
|
1521 1522 1523 |
if (ret < 0) return ret; node = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9
|
1524 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
17c76b010
|
1525 1526 1527 |
break; default: node = NULL; |
1f5abe7e7
|
1528 |
return -EINVAL; |
17c76b010
|
1529 |
} |
6d28f7ea4
|
1530 |
nchildren = nilfs_btree_node_get_nchildren(node); |
17c76b010
|
1531 1532 |
if (nchildren < nitems) nitems = nchildren; |
6d28f7ea4
|
1533 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9
|
1534 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
17c76b010
|
1535 |
for (i = 0; i < nitems; i++) { |
25b8d7ded
|
1536 1537 |
keys[i] = le64_to_cpu(dkeys[i]); ptrs[i] = le64_to_cpu(dptrs[i]); |
17c76b010
|
1538 1539 1540 |
} if (bh != NULL) |
087d01b42
|
1541 |
brelse(bh); |
17c76b010
|
1542 1543 1544 1545 1546 |
return nitems; } static int |
e7c274f80
|
1547 |
nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key, |
17c76b010
|
1548 1549 1550 1551 1552 1553 |
union nilfs_bmap_ptr_req *dreq, union nilfs_bmap_ptr_req *nreq, struct buffer_head **bhp, struct nilfs_bmap_stats *stats) { struct buffer_head *bh; |
2e0c2c739
|
1554 |
struct inode *dat = NULL; |
17c76b010
|
1555 |
int ret; |
17c76b010
|
1556 1557 1558 1559 |
stats->bs_nblocks = 0; /* for data */ /* cannot find near ptr */ |
e7c274f80
|
1560 |
if (NILFS_BMAP_USE_VBN(btree)) { |
7cde31d7d
|
1561 |
dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key); |
e7c274f80
|
1562 |
dat = nilfs_bmap_get_dat(btree); |
2e0c2c739
|
1563 |
} |
7cde31d7d
|
1564 |
|
e7c274f80
|
1565 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat); |
17c76b010
|
1566 1567 1568 1569 1570 1571 1572 |
if (ret < 0) return ret; *bhp = NULL; stats->bs_nblocks++; if (nreq != NULL) { nreq->bpr_ptr = dreq->bpr_ptr + 1; |
e7c274f80
|
1573 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat); |
17c76b010
|
1574 1575 |
if (ret < 0) goto err_out_dreq; |
f198dbb9c
|
1576 |
ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh); |
17c76b010
|
1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 |
if (ret < 0) goto err_out_nreq; *bhp = bh; stats->bs_nblocks++; } /* success */ return 0; /* error */ err_out_nreq: |
e7c274f80
|
1589 |
nilfs_bmap_abort_alloc_ptr(btree, nreq, dat); |
17c76b010
|
1590 |
err_out_dreq: |
e7c274f80
|
1591 |
nilfs_bmap_abort_alloc_ptr(btree, dreq, dat); |
17c76b010
|
1592 1593 1594 1595 1596 1597 |
stats->bs_nblocks = 0; return ret; } static void |
e7c274f80
|
1598 |
nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree, |
17c76b010
|
1599 1600 |
__u64 key, __u64 ptr, const __u64 *keys, const __u64 *ptrs, |
3033342a0
|
1601 |
int n, |
17c76b010
|
1602 1603 1604 1605 |
union nilfs_bmap_ptr_req *dreq, union nilfs_bmap_ptr_req *nreq, struct buffer_head *bh) { |
17c76b010
|
1606 |
struct nilfs_btree_node *node; |
2e0c2c739
|
1607 |
struct inode *dat; |
17c76b010
|
1608 |
__u64 tmpptr; |
9b7b265c9
|
1609 |
int ncblk; |
17c76b010
|
1610 1611 |
/* free resources */ |
e7c274f80
|
1612 1613 |
if (btree->b_ops->bop_clear != NULL) btree->b_ops->bop_clear(btree); |
17c76b010
|
1614 1615 1616 1617 1618 |
/* ptr must be a pointer to a buffer head. */ set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr)); /* convert and insert */ |
e7c274f80
|
1619 1620 |
dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL; nilfs_btree_init(btree); |
17c76b010
|
1621 |
if (nreq != NULL) { |
e7c274f80
|
1622 1623 |
nilfs_bmap_commit_alloc_ptr(btree, dreq, dat); nilfs_bmap_commit_alloc_ptr(btree, nreq, dat); |
17c76b010
|
1624 1625 |
/* create child node at level 1 */ |
17c76b010
|
1626 |
node = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9
|
1627 1628 1629 |
ncblk = nilfs_btree_nchildren_per_block(btree); nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs); nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk); |
17c76b010
|
1630 |
if (!buffer_dirty(bh)) |
5fc7b1417
|
1631 |
mark_buffer_dirty(bh); |
e7c274f80
|
1632 1633 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010
|
1634 |
|
087d01b42
|
1635 |
brelse(bh); |
17c76b010
|
1636 1637 1638 1639 |
/* create root node at level 2 */ node = nilfs_btree_get_root(btree); tmpptr = nreq->bpr_ptr; |
9b7b265c9
|
1640 1641 1642 |
nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1, NILFS_BTREE_ROOT_NCHILDREN_MAX, &keys[0], &tmpptr); |
17c76b010
|
1643 |
} else { |
e7c274f80
|
1644 |
nilfs_bmap_commit_alloc_ptr(btree, dreq, dat); |
17c76b010
|
1645 1646 1647 |
/* create root node at level 1 */ node = nilfs_btree_get_root(btree); |
9b7b265c9
|
1648 1649 1650 1651 1652 |
nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n, NILFS_BTREE_ROOT_NCHILDREN_MAX, keys, ptrs); nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
e7c274f80
|
1653 1654 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010
|
1655 |
} |
e7c274f80
|
1656 |
if (NILFS_BMAP_USE_VBN(btree)) |
dc935be2a
|
1657 |
nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr); |
17c76b010
|
1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 |
} /** * nilfs_btree_convert_and_insert - * @bmap: * @key: * @ptr: * @keys: * @ptrs: * @n: |
17c76b010
|
1668 |
*/ |
e7c274f80
|
1669 |
int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree, |
17c76b010
|
1670 |
__u64 key, __u64 ptr, |
3033342a0
|
1671 |
const __u64 *keys, const __u64 *ptrs, int n) |
17c76b010
|
1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 |
{ struct buffer_head *bh; union nilfs_bmap_ptr_req dreq, nreq, *di, *ni; struct nilfs_bmap_stats stats; int ret; if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) { di = &dreq; ni = NULL; } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX( |
e7c274f80
|
1682 |
1 << btree->b_inode->i_blkbits)) { |
17c76b010
|
1683 1684 1685 1686 1687 1688 1689 |
di = &dreq; ni = &nreq; } else { di = NULL; ni = NULL; BUG(); } |
e7c274f80
|
1690 |
ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh, |
17c76b010
|
1691 1692 1693 |
&stats); if (ret < 0) return ret; |
e7c274f80
|
1694 |
nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n, |
3033342a0
|
1695 |
di, ni, bh); |
be667377a
|
1696 |
nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks); |
17c76b010
|
1697 1698 |
return 0; } |
e7c274f80
|
1699 |
static int nilfs_btree_propagate_p(struct nilfs_bmap *btree, |
17c76b010
|
1700 1701 1702 1703 1704 1705 |
struct nilfs_btree_path *path, int level, struct buffer_head *bh) { while ((++level < nilfs_btree_height(btree) - 1) && !buffer_dirty(path[level].bp_bh)) |
5fc7b1417
|
1706 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010
|
1707 1708 1709 |
return 0; } |
e7c274f80
|
1710 |
static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree, |
17c76b010
|
1711 |
struct nilfs_btree_path *path, |
2e0c2c739
|
1712 |
int level, struct inode *dat) |
17c76b010
|
1713 1714 |
{ struct nilfs_btree_node *parent; |
9b7b265c9
|
1715 |
int ncmax, ret; |
17c76b010
|
1716 |
|
9b7b265c9
|
1717 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); |
17c76b010
|
1718 |
path[level].bp_oldreq.bpr_ptr = |
9b7b265c9
|
1719 1720 |
nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, ncmax); |
17c76b010
|
1721 |
path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; |
2e0c2c739
|
1722 1723 |
ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req); |
17c76b010
|
1724 1725 1726 1727 1728 1729 1730 1731 |
if (ret < 0) return ret; if (buffer_nilfs_node(path[level].bp_bh)) { path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr; path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr; path[level].bp_ctxt.bh = path[level].bp_bh; ret = nilfs_btnode_prepare_change_key( |
e7c274f80
|
1732 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010
|
1733 1734 |
&path[level].bp_ctxt); if (ret < 0) { |
2e0c2c739
|
1735 1736 1737 |
nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req); |
17c76b010
|
1738 1739 1740 1741 1742 1743 |
return ret; } } return 0; } |
e7c274f80
|
1744 |
static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree, |
17c76b010
|
1745 |
struct nilfs_btree_path *path, |
2e0c2c739
|
1746 |
int level, struct inode *dat) |
17c76b010
|
1747 1748 |
{ struct nilfs_btree_node *parent; |
9b7b265c9
|
1749 |
int ncmax; |
17c76b010
|
1750 |
|
2e0c2c739
|
1751 1752 |
nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req, |
e7c274f80
|
1753 |
btree->b_ptr_type == NILFS_BMAP_PTR_VS); |
17c76b010
|
1754 1755 1756 |
if (buffer_nilfs_node(path[level].bp_bh)) { nilfs_btnode_commit_change_key( |
e7c274f80
|
1757 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010
|
1758 1759 1760 1761 |
&path[level].bp_ctxt); path[level].bp_bh = path[level].bp_ctxt.bh; } set_buffer_nilfs_volatile(path[level].bp_bh); |
9b7b265c9
|
1762 1763 1764 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, path[level].bp_newreq.bpr_ptr, ncmax); |
17c76b010
|
1765 |
} |
e7c274f80
|
1766 |
static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree, |
17c76b010
|
1767 |
struct nilfs_btree_path *path, |
2e0c2c739
|
1768 |
int level, struct inode *dat) |
17c76b010
|
1769 |
{ |
2e0c2c739
|
1770 1771 |
nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req); |
17c76b010
|
1772 1773 |
if (buffer_nilfs_node(path[level].bp_bh)) nilfs_btnode_abort_change_key( |
e7c274f80
|
1774 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010
|
1775 1776 |
&path[level].bp_ctxt); } |
e7c274f80
|
1777 |
static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree, |
17c76b010
|
1778 |
struct nilfs_btree_path *path, |
2e0c2c739
|
1779 1780 |
int minlevel, int *maxlevelp, struct inode *dat) |
17c76b010
|
1781 1782 1783 1784 1785 |
{ int level, ret; level = minlevel; if (!buffer_nilfs_volatile(path[level].bp_bh)) { |
2e0c2c739
|
1786 |
ret = nilfs_btree_prepare_update_v(btree, path, level, dat); |
17c76b010
|
1787 1788 1789 1790 1791 |
if (ret < 0) return ret; } while ((++level < nilfs_btree_height(btree) - 1) && !buffer_dirty(path[level].bp_bh)) { |
1f5abe7e7
|
1792 |
WARN_ON(buffer_nilfs_volatile(path[level].bp_bh)); |
2e0c2c739
|
1793 |
ret = nilfs_btree_prepare_update_v(btree, path, level, dat); |
17c76b010
|
1794 1795 1796 1797 1798 |
if (ret < 0) goto out; } /* success */ |
17c76b010
|
1799 1800 1801 1802 1803 1804 |
*maxlevelp = level - 1; return 0; /* error */ out: while (--level > minlevel) |
2e0c2c739
|
1805 |
nilfs_btree_abort_update_v(btree, path, level, dat); |
17c76b010
|
1806 |
if (!buffer_nilfs_volatile(path[level].bp_bh)) |
2e0c2c739
|
1807 |
nilfs_btree_abort_update_v(btree, path, level, dat); |
17c76b010
|
1808 1809 |
return ret; } |
e7c274f80
|
1810 |
static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree, |
17c76b010
|
1811 |
struct nilfs_btree_path *path, |
2e0c2c739
|
1812 1813 1814 |
int minlevel, int maxlevel, struct buffer_head *bh, struct inode *dat) |
17c76b010
|
1815 1816 1817 1818 |
{ int level; if (!buffer_nilfs_volatile(path[minlevel].bp_bh)) |
2e0c2c739
|
1819 |
nilfs_btree_commit_update_v(btree, path, minlevel, dat); |
17c76b010
|
1820 1821 |
for (level = minlevel + 1; level <= maxlevel; level++) |
2e0c2c739
|
1822 |
nilfs_btree_commit_update_v(btree, path, level, dat); |
17c76b010
|
1823 |
} |
e7c274f80
|
1824 |
static int nilfs_btree_propagate_v(struct nilfs_bmap *btree, |
17c76b010
|
1825 |
struct nilfs_btree_path *path, |
2e0c2c739
|
1826 |
int level, struct buffer_head *bh) |
17c76b010
|
1827 |
{ |
308f44193
|
1828 |
int maxlevel = 0, ret; |
17c76b010
|
1829 |
struct nilfs_btree_node *parent; |
e7c274f80
|
1830 |
struct inode *dat = nilfs_bmap_get_dat(btree); |
17c76b010
|
1831 |
__u64 ptr; |
9b7b265c9
|
1832 |
int ncmax; |
17c76b010
|
1833 1834 1835 |
get_bh(bh); path[level].bp_bh = bh; |
2e0c2c739
|
1836 1837 |
ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel, dat); |
17c76b010
|
1838 1839 1840 1841 |
if (ret < 0) goto out; if (buffer_nilfs_volatile(path[level].bp_bh)) { |
9b7b265c9
|
1842 1843 1844 1845 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, ncmax); |
2e0c2c739
|
1846 |
ret = nilfs_dat_mark_dirty(dat, ptr); |
17c76b010
|
1847 1848 1849 |
if (ret < 0) goto out; } |
2e0c2c739
|
1850 |
nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat); |
17c76b010
|
1851 1852 1853 1854 1855 1856 |
out: brelse(path[level].bp_bh); path[level].bp_bh = NULL; return ret; } |
e7c274f80
|
1857 |
static int nilfs_btree_propagate(struct nilfs_bmap *btree, |
17c76b010
|
1858 1859 |
struct buffer_head *bh) { |
17c76b010
|
1860 1861 1862 1863 |
struct nilfs_btree_path *path; struct nilfs_btree_node *node; __u64 key; int level, ret; |
1f5abe7e7
|
1864 |
WARN_ON(!buffer_dirty(bh)); |
17c76b010
|
1865 |
|
6d28f7ea4
|
1866 |
path = nilfs_btree_alloc_path(); |
17c76b010
|
1867 1868 |
if (path == NULL) return -ENOMEM; |
17c76b010
|
1869 1870 1871 |
if (buffer_nilfs_node(bh)) { node = (struct nilfs_btree_node *)bh->b_data; |
6d28f7ea4
|
1872 1873 |
key = nilfs_btree_node_get_key(node, 0); level = nilfs_btree_node_get_level(node); |
17c76b010
|
1874 |
} else { |
e7c274f80
|
1875 |
key = nilfs_bmap_data_get_key(btree, bh); |
17c76b010
|
1876 1877 |
level = NILFS_BTREE_LEVEL_DATA; } |
03bdb5ac5
|
1878 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); |
17c76b010
|
1879 |
if (ret < 0) { |
1f5abe7e7
|
1880 |
if (unlikely(ret == -ENOENT)) |
17c76b010
|
1881 1882 1883 |
printk(KERN_CRIT "%s: key = %llu, level == %d ", __func__, (unsigned long long)key, level); |
17c76b010
|
1884 1885 |
goto out; } |
e7c274f80
|
1886 |
ret = NILFS_BMAP_USE_VBN(btree) ? |
7cde31d7d
|
1887 1888 |
nilfs_btree_propagate_v(btree, path, level, bh) : nilfs_btree_propagate_p(btree, path, level, bh); |
17c76b010
|
1889 1890 |
out: |
6d28f7ea4
|
1891 |
nilfs_btree_free_path(path); |
17c76b010
|
1892 1893 1894 |
return ret; } |
e7c274f80
|
1895 |
static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree, |
17c76b010
|
1896 1897 |
struct buffer_head *bh) { |
e7c274f80
|
1898 |
return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr); |
17c76b010
|
1899 |
} |
e7c274f80
|
1900 |
static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree, |
17c76b010
|
1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 |
struct list_head *lists, struct buffer_head *bh) { struct list_head *head; struct buffer_head *cbh; struct nilfs_btree_node *node, *cnode; __u64 key, ckey; int level; get_bh(bh); node = (struct nilfs_btree_node *)bh->b_data; |
6d28f7ea4
|
1912 1913 |
key = nilfs_btree_node_get_key(node, 0); level = nilfs_btree_node_get_level(node); |
cfa913a50
|
1914 1915 1916 1917 1918 1919 1920 1921 |
if (level < NILFS_BTREE_LEVEL_NODE_MIN || level >= NILFS_BTREE_LEVEL_MAX) { dump_stack(); printk(KERN_WARNING "%s: invalid btree level: %d (key=%llu, ino=%lu, " "blocknr=%llu) ", __func__, level, (unsigned long long)key, |
e7c274f80
|
1922 |
NILFS_BMAP_I(btree)->vfs_inode.i_ino, |
cfa913a50
|
1923 1924 1925 |
(unsigned long long)bh->b_blocknr); return; } |
17c76b010
|
1926 1927 1928 |
list_for_each(head, &lists[level]) { cbh = list_entry(head, struct buffer_head, b_assoc_buffers); cnode = (struct nilfs_btree_node *)cbh->b_data; |
6d28f7ea4
|
1929 |
ckey = nilfs_btree_node_get_key(cnode, 0); |
17c76b010
|
1930 1931 1932 1933 1934 |
if (key < ckey) break; } list_add_tail(&bh->b_assoc_buffers, head); } |
e7c274f80
|
1935 |
static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree, |
17c76b010
|
1936 1937 |
struct list_head *listp) { |
e7c274f80
|
1938 |
struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache; |
17c76b010
|
1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 |
struct list_head lists[NILFS_BTREE_LEVEL_MAX]; struct pagevec pvec; struct buffer_head *bh, *head; pgoff_t index = 0; int level, i; for (level = NILFS_BTREE_LEVEL_NODE_MIN; level < NILFS_BTREE_LEVEL_MAX; level++) INIT_LIST_HEAD(&lists[level]); pagevec_init(&pvec, 0); while (pagevec_lookup_tag(&pvec, btcache, &index, PAGECACHE_TAG_DIRTY, PAGEVEC_SIZE)) { for (i = 0; i < pagevec_count(&pvec); i++) { bh = head = page_buffers(pvec.pages[i]); do { if (buffer_dirty(bh)) nilfs_btree_add_dirty_buffer(btree, lists, bh); } while ((bh = bh->b_this_page) != head); } pagevec_release(&pvec); cond_resched(); } for (level = NILFS_BTREE_LEVEL_NODE_MIN; level < NILFS_BTREE_LEVEL_MAX; level++) |
0935db747
|
1969 |
list_splice_tail(&lists[level], listp); |
17c76b010
|
1970 |
} |
e7c274f80
|
1971 |
static int nilfs_btree_assign_p(struct nilfs_bmap *btree, |
17c76b010
|
1972 1973 1974 1975 1976 1977 1978 1979 1980 |
struct nilfs_btree_path *path, int level, struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) { struct nilfs_btree_node *parent; __u64 key; __u64 ptr; |
9b7b265c9
|
1981 |
int ncmax, ret; |
17c76b010
|
1982 |
|
9b7b265c9
|
1983 1984 1985 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, ncmax); |
17c76b010
|
1986 1987 1988 1989 1990 |
if (buffer_nilfs_node(*bh)) { path[level].bp_ctxt.oldkey = ptr; path[level].bp_ctxt.newkey = blocknr; path[level].bp_ctxt.bh = *bh; ret = nilfs_btnode_prepare_change_key( |
e7c274f80
|
1991 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010
|
1992 1993 1994 1995 |
&path[level].bp_ctxt); if (ret < 0) return ret; nilfs_btnode_commit_change_key( |
e7c274f80
|
1996 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010
|
1997 1998 1999 |
&path[level].bp_ctxt); *bh = path[level].bp_ctxt.bh; } |
9b7b265c9
|
2000 2001 |
nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr, ncmax); |
17c76b010
|
2002 |
|
6d28f7ea4
|
2003 |
key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); |
17c76b010
|
2004 |
/* on-disk format */ |
25b8d7ded
|
2005 |
binfo->bi_dat.bi_blkoff = cpu_to_le64(key); |
17c76b010
|
2006 2007 2008 2009 |
binfo->bi_dat.bi_level = level; return 0; } |
e7c274f80
|
2010 |
static int nilfs_btree_assign_v(struct nilfs_bmap *btree, |
17c76b010
|
2011 2012 2013 2014 2015 2016 2017 |
struct nilfs_btree_path *path, int level, struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) { struct nilfs_btree_node *parent; |
e7c274f80
|
2018 |
struct inode *dat = nilfs_bmap_get_dat(btree); |
17c76b010
|
2019 2020 2021 |
__u64 key; __u64 ptr; union nilfs_bmap_ptr_req req; |
9b7b265c9
|
2022 |
int ncmax, ret; |
17c76b010
|
2023 |
|
9b7b265c9
|
2024 2025 2026 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, ncmax); |
17c76b010
|
2027 |
req.bpr_ptr = ptr; |
2e0c2c739
|
2028 2029 |
ret = nilfs_dat_prepare_start(dat, &req.bpr_req); if (ret < 0) |
17c76b010
|
2030 |
return ret; |
2e0c2c739
|
2031 |
nilfs_dat_commit_start(dat, &req.bpr_req, blocknr); |
17c76b010
|
2032 |
|
6d28f7ea4
|
2033 |
key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); |
17c76b010
|
2034 |
/* on-disk format */ |
25b8d7ded
|
2035 2036 |
binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr); binfo->bi_v.bi_blkoff = cpu_to_le64(key); |
17c76b010
|
2037 2038 2039 |
return 0; } |
e7c274f80
|
2040 |
static int nilfs_btree_assign(struct nilfs_bmap *btree, |
17c76b010
|
2041 2042 2043 2044 |
struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) { |
17c76b010
|
2045 2046 2047 2048 |
struct nilfs_btree_path *path; struct nilfs_btree_node *node; __u64 key; int level, ret; |
6d28f7ea4
|
2049 |
path = nilfs_btree_alloc_path(); |
17c76b010
|
2050 2051 |
if (path == NULL) return -ENOMEM; |
17c76b010
|
2052 2053 2054 |
if (buffer_nilfs_node(*bh)) { node = (struct nilfs_btree_node *)(*bh)->b_data; |
6d28f7ea4
|
2055 2056 |
key = nilfs_btree_node_get_key(node, 0); level = nilfs_btree_node_get_level(node); |
17c76b010
|
2057 |
} else { |
e7c274f80
|
2058 |
key = nilfs_bmap_data_get_key(btree, *bh); |
17c76b010
|
2059 2060 |
level = NILFS_BTREE_LEVEL_DATA; } |
03bdb5ac5
|
2061 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); |
17c76b010
|
2062 |
if (ret < 0) { |
1f5abe7e7
|
2063 |
WARN_ON(ret == -ENOENT); |
17c76b010
|
2064 2065 |
goto out; } |
e7c274f80
|
2066 |
ret = NILFS_BMAP_USE_VBN(btree) ? |
7cde31d7d
|
2067 2068 |
nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); |
17c76b010
|
2069 2070 |
out: |
6d28f7ea4
|
2071 |
nilfs_btree_free_path(path); |
17c76b010
|
2072 2073 2074 |
return ret; } |
e7c274f80
|
2075 |
static int nilfs_btree_assign_gc(struct nilfs_bmap *btree, |
17c76b010
|
2076 2077 2078 2079 |
struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) { |
17c76b010
|
2080 2081 2082 |
struct nilfs_btree_node *node; __u64 key; int ret; |
e7c274f80
|
2083 |
ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr, |
2e0c2c739
|
2084 |
blocknr); |
17c76b010
|
2085 2086 2087 2088 2089 |
if (ret < 0) return ret; if (buffer_nilfs_node(*bh)) { node = (struct nilfs_btree_node *)(*bh)->b_data; |
6d28f7ea4
|
2090 |
key = nilfs_btree_node_get_key(node, 0); |
17c76b010
|
2091 |
} else |
e7c274f80
|
2092 |
key = nilfs_bmap_data_get_key(btree, *bh); |
17c76b010
|
2093 2094 2095 |
/* on-disk format */ binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr); |
25b8d7ded
|
2096 |
binfo->bi_v.bi_blkoff = cpu_to_le64(key); |
17c76b010
|
2097 2098 2099 |
return 0; } |
e7c274f80
|
2100 |
static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) |
17c76b010
|
2101 2102 |
{ struct buffer_head *bh; |
17c76b010
|
2103 2104 2105 |
struct nilfs_btree_path *path; __u64 ptr; int ret; |
6d28f7ea4
|
2106 |
path = nilfs_btree_alloc_path(); |
17c76b010
|
2107 2108 |
if (path == NULL) return -ENOMEM; |
17c76b010
|
2109 |
|
03bdb5ac5
|
2110 |
ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0); |
17c76b010
|
2111 |
if (ret < 0) { |
1f5abe7e7
|
2112 |
WARN_ON(ret == -ENOENT); |
17c76b010
|
2113 2114 |
goto out; } |
f198dbb9c
|
2115 |
ret = nilfs_btree_get_block(btree, ptr, &bh); |
17c76b010
|
2116 |
if (ret < 0) { |
1f5abe7e7
|
2117 |
WARN_ON(ret == -ENOENT); |
17c76b010
|
2118 2119 2120 2121 |
goto out; } if (!buffer_dirty(bh)) |
5fc7b1417
|
2122 |
mark_buffer_dirty(bh); |
087d01b42
|
2123 |
brelse(bh); |
e7c274f80
|
2124 2125 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010
|
2126 2127 |
out: |
6d28f7ea4
|
2128 |
nilfs_btree_free_path(path); |
17c76b010
|
2129 2130 2131 2132 2133 |
return ret; } static const struct nilfs_bmap_operations nilfs_btree_ops = { .bop_lookup = nilfs_btree_lookup, |
c3a7abf06
|
2134 |
.bop_lookup_contig = nilfs_btree_lookup_contig, |
17c76b010
|
2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 |
.bop_insert = nilfs_btree_insert, .bop_delete = nilfs_btree_delete, .bop_clear = NULL, .bop_propagate = nilfs_btree_propagate, .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers, .bop_assign = nilfs_btree_assign, .bop_mark = nilfs_btree_mark, .bop_last_key = nilfs_btree_last_key, .bop_check_insert = NULL, .bop_check_delete = nilfs_btree_check_delete, .bop_gather_data = nilfs_btree_gather_data, }; static const struct nilfs_bmap_operations nilfs_btree_ops_gc = { .bop_lookup = NULL, |
c3a7abf06
|
2154 |
.bop_lookup_contig = NULL, |
17c76b010
|
2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 |
.bop_insert = NULL, .bop_delete = NULL, .bop_clear = NULL, .bop_propagate = nilfs_btree_propagate_gc, .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers, .bop_assign = nilfs_btree_assign_gc, .bop_mark = NULL, .bop_last_key = NULL, .bop_check_insert = NULL, .bop_check_delete = NULL, .bop_gather_data = NULL, }; |
3033342a0
|
2171 |
int nilfs_btree_init(struct nilfs_bmap *bmap) |
17c76b010
|
2172 |
{ |
17c76b010
|
2173 |
bmap->b_ops = &nilfs_btree_ops; |
5ad2686e9
|
2174 2175 |
bmap->b_nchildren_per_block = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap)); |
17c76b010
|
2176 2177 2178 2179 2180 |
return 0; } void nilfs_btree_init_gc(struct nilfs_bmap *bmap) { |
17c76b010
|
2181 |
bmap->b_ops = &nilfs_btree_ops_gc; |
5ad2686e9
|
2182 2183 |
bmap->b_nchildren_per_block = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap)); |
17c76b010
|
2184 |
} |