Blame view
fs/nilfs2/btree.c
60 KB
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: support c... |
32 |
#include "dat.h" |
17c76b010 nilfs2: B-tree ba... |
33 |
|
f905440f5 nilfs2: Combine n... |
34 |
static struct nilfs_btree_path *nilfs_btree_alloc_path(void) |
17c76b010 nilfs2: B-tree ba... |
35 |
{ |
f905440f5 nilfs2: Combine n... |
36 37 |
struct nilfs_btree_path *path; int level = NILFS_BTREE_LEVEL_DATA; |
17c76b010 nilfs2: B-tree ba... |
38 |
|
f905440f5 nilfs2: Combine n... |
39 40 41 |
path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS); if (path == NULL) goto out; |
17c76b010 nilfs2: B-tree ba... |
42 |
|
f905440f5 nilfs2: Combine n... |
43 |
for (; level < NILFS_BTREE_LEVEL_MAX; level++) { |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: Combine n... |
51 52 53 54 |
out: return path; } |
73bb48869 nilfs2: Combine n... |
55 |
static void nilfs_btree_free_path(struct nilfs_btree_path *path) |
f905440f5 nilfs2: Combine n... |
56 |
{ |
73bb48869 nilfs2: Combine n... |
57 |
int level = NILFS_BTREE_LEVEL_DATA; |
17c76b010 nilfs2: B-tree ba... |
58 |
|
73bb48869 nilfs2: Combine n... |
59 |
for (; level < NILFS_BTREE_LEVEL_MAX; level++) |
3218929db nilfs2: stop zero... |
60 |
brelse(path[level].bp_bh); |
73bb48869 nilfs2: Combine n... |
61 62 |
kmem_cache_free(nilfs_btree_path_cache, path); |
17c76b010 nilfs2: B-tree ba... |
63 |
} |
17c76b010 nilfs2: B-tree ba... |
64 65 66 |
/* * B-tree node operations */ |
e7c274f80 nilfs2: get rid o... |
67 |
static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree, |
f198dbb9c nilfs2: move get ... |
68 69 |
__u64 ptr, struct buffer_head **bhp) { |
e7c274f80 nilfs2: get rid o... |
70 |
struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache; |
45f4910bc nilfs2: use nilfs... |
71 |
struct buffer_head *bh; |
f198dbb9c nilfs2: move get ... |
72 |
|
45f4910bc nilfs2: use nilfs... |
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 nilfs2: move get ... |
80 |
} |
17c76b010 nilfs2: B-tree ba... |
81 |
|
7c397a81f nilfs2: eliminate... |
82 |
static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node) |
17c76b010 nilfs2: B-tree ba... |
83 84 85 |
{ return node->bn_flags; } |
7c397a81f nilfs2: eliminate... |
86 |
static void |
6d28f7ea4 nilfs2: remove un... |
87 |
nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags) |
17c76b010 nilfs2: B-tree ba... |
88 89 90 |
{ node->bn_flags = flags; } |
7c397a81f nilfs2: eliminate... |
91 |
static int nilfs_btree_node_root(const struct nilfs_btree_node *node) |
17c76b010 nilfs2: B-tree ba... |
92 |
{ |
6d28f7ea4 nilfs2: remove un... |
93 |
return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT; |
17c76b010 nilfs2: B-tree ba... |
94 |
} |
7c397a81f nilfs2: eliminate... |
95 |
static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node) |
17c76b010 nilfs2: B-tree ba... |
96 97 98 |
{ return node->bn_level; } |
7c397a81f nilfs2: eliminate... |
99 |
static void |
6d28f7ea4 nilfs2: remove un... |
100 |
nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) |
17c76b010 nilfs2: B-tree ba... |
101 102 103 |
{ node->bn_level = level; } |
7c397a81f nilfs2: eliminate... |
104 |
static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node) |
17c76b010 nilfs2: B-tree ba... |
105 106 107 |
{ return le16_to_cpu(node->bn_nchildren); } |
7c397a81f nilfs2: eliminate... |
108 |
static void |
6d28f7ea4 nilfs2: remove un... |
109 |
nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren) |
17c76b010 nilfs2: B-tree ba... |
110 111 112 |
{ node->bn_nchildren = cpu_to_le16(nchildren); } |
7c397a81f nilfs2: eliminate... |
113 |
static int nilfs_btree_node_size(const struct nilfs_bmap *btree) |
17c76b010 nilfs2: B-tree ba... |
114 |
{ |
e7c274f80 nilfs2: get rid o... |
115 |
return 1 << btree->b_inode->i_blkbits; |
17c76b010 nilfs2: B-tree ba... |
116 |
} |
9b7b265c9 nilfs2: reduce re... |
117 |
static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree) |
17c76b010 nilfs2: B-tree ba... |
118 |
{ |
5ad2686e9 nilfs2: get maxim... |
119 |
return btree->b_nchildren_per_block; |
17c76b010 nilfs2: B-tree ba... |
120 |
} |
7c397a81f nilfs2: eliminate... |
121 |
static __le64 * |
6d28f7ea4 nilfs2: remove un... |
122 |
nilfs_btree_node_dkeys(const struct nilfs_btree_node *node) |
17c76b010 nilfs2: B-tree ba... |
123 124 |
{ return (__le64 *)((char *)(node + 1) + |
6d28f7ea4 nilfs2: remove un... |
125 |
(nilfs_btree_node_root(node) ? |
17c76b010 nilfs2: B-tree ba... |
126 127 |
0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE)); } |
7c397a81f nilfs2: eliminate... |
128 |
static __le64 * |
9b7b265c9 nilfs2: reduce re... |
129 |
nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax) |
17c76b010 nilfs2: B-tree ba... |
130 |
{ |
9b7b265c9 nilfs2: reduce re... |
131 |
return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax); |
17c76b010 nilfs2: B-tree ba... |
132 |
} |
7c397a81f nilfs2: eliminate... |
133 |
static __u64 |
6d28f7ea4 nilfs2: remove un... |
134 |
nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index) |
17c76b010 nilfs2: B-tree ba... |
135 |
{ |
25b8d7ded nilfs2: get rid o... |
136 |
return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index)); |
17c76b010 nilfs2: B-tree ba... |
137 |
} |
7c397a81f nilfs2: eliminate... |
138 |
static void |
6d28f7ea4 nilfs2: remove un... |
139 |
nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key) |
17c76b010 nilfs2: B-tree ba... |
140 |
{ |
25b8d7ded nilfs2: get rid o... |
141 |
*(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key); |
17c76b010 nilfs2: B-tree ba... |
142 |
} |
7c397a81f nilfs2: eliminate... |
143 |
static __u64 |
9b7b265c9 nilfs2: reduce re... |
144 145 |
nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index, int ncmax) |
17c76b010 nilfs2: B-tree ba... |
146 |
{ |
9b7b265c9 nilfs2: reduce re... |
147 |
return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index)); |
17c76b010 nilfs2: B-tree ba... |
148 |
} |
7c397a81f nilfs2: eliminate... |
149 |
static void |
9b7b265c9 nilfs2: reduce re... |
150 151 |
nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr, int ncmax) |
17c76b010 nilfs2: B-tree ba... |
152 |
{ |
9b7b265c9 nilfs2: reduce re... |
153 |
*(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr); |
17c76b010 nilfs2: B-tree ba... |
154 |
} |
9b7b265c9 nilfs2: reduce re... |
155 156 |
static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags, int level, int nchildren, int ncmax, |
17c76b010 nilfs2: B-tree ba... |
157 158 159 160 161 |
const __u64 *keys, const __u64 *ptrs) { __le64 *dkeys; __le64 *dptrs; int i; |
6d28f7ea4 nilfs2: remove un... |
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 nilfs2: B-tree ba... |
165 |
|
6d28f7ea4 nilfs2: remove un... |
166 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9 nilfs2: reduce re... |
167 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
17c76b010 nilfs2: B-tree ba... |
168 |
for (i = 0; i < nchildren; i++) { |
25b8d7ded nilfs2: get rid o... |
169 170 |
dkeys[i] = cpu_to_le64(keys[i]); dptrs[i] = cpu_to_le64(ptrs[i]); |
17c76b010 nilfs2: B-tree ba... |
171 172 173 174 |
} } /* Assume the buffer heads corresponding to left and right are locked. */ |
9b7b265c9 nilfs2: reduce re... |
175 |
static void nilfs_btree_node_move_left(struct nilfs_btree_node *left, |
17c76b010 nilfs2: B-tree ba... |
176 |
struct nilfs_btree_node *right, |
9b7b265c9 nilfs2: reduce re... |
177 |
int n, int lncmax, int rncmax) |
17c76b010 nilfs2: B-tree ba... |
178 179 180 181 |
{ __le64 *ldkeys, *rdkeys; __le64 *ldptrs, *rdptrs; int lnchildren, rnchildren; |
6d28f7ea4 nilfs2: remove un... |
182 |
ldkeys = nilfs_btree_node_dkeys(left); |
9b7b265c9 nilfs2: reduce re... |
183 |
ldptrs = nilfs_btree_node_dptrs(left, lncmax); |
6d28f7ea4 nilfs2: remove un... |
184 |
lnchildren = nilfs_btree_node_get_nchildren(left); |
17c76b010 nilfs2: B-tree ba... |
185 |
|
6d28f7ea4 nilfs2: remove un... |
186 |
rdkeys = nilfs_btree_node_dkeys(right); |
9b7b265c9 nilfs2: reduce re... |
187 |
rdptrs = nilfs_btree_node_dptrs(right, rncmax); |
6d28f7ea4 nilfs2: remove un... |
188 |
rnchildren = nilfs_btree_node_get_nchildren(right); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
197 198 |
nilfs_btree_node_set_nchildren(left, lnchildren); nilfs_btree_node_set_nchildren(right, rnchildren); |
17c76b010 nilfs2: B-tree ba... |
199 200 201 |
} /* Assume that the buffer heads corresponding to left and right are locked. */ |
9b7b265c9 nilfs2: reduce re... |
202 |
static void nilfs_btree_node_move_right(struct nilfs_btree_node *left, |
17c76b010 nilfs2: B-tree ba... |
203 |
struct nilfs_btree_node *right, |
9b7b265c9 nilfs2: reduce re... |
204 |
int n, int lncmax, int rncmax) |
17c76b010 nilfs2: B-tree ba... |
205 206 207 208 |
{ __le64 *ldkeys, *rdkeys; __le64 *ldptrs, *rdptrs; int lnchildren, rnchildren; |
6d28f7ea4 nilfs2: remove un... |
209 |
ldkeys = nilfs_btree_node_dkeys(left); |
9b7b265c9 nilfs2: reduce re... |
210 |
ldptrs = nilfs_btree_node_dptrs(left, lncmax); |
6d28f7ea4 nilfs2: remove un... |
211 |
lnchildren = nilfs_btree_node_get_nchildren(left); |
17c76b010 nilfs2: B-tree ba... |
212 |
|
6d28f7ea4 nilfs2: remove un... |
213 |
rdkeys = nilfs_btree_node_dkeys(right); |
9b7b265c9 nilfs2: reduce re... |
214 |
rdptrs = nilfs_btree_node_dptrs(right, rncmax); |
6d28f7ea4 nilfs2: remove un... |
215 |
rnchildren = nilfs_btree_node_get_nchildren(right); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
224 225 |
nilfs_btree_node_set_nchildren(left, lnchildren); nilfs_btree_node_set_nchildren(right, rnchildren); |
17c76b010 nilfs2: B-tree ba... |
226 227 228 |
} /* Assume that the buffer head corresponding to node is locked. */ |
9b7b265c9 nilfs2: reduce re... |
229 230 |
static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index, __u64 key, __u64 ptr, int ncmax) |
17c76b010 nilfs2: B-tree ba... |
231 232 233 234 |
{ __le64 *dkeys; __le64 *dptrs; int nchildren; |
6d28f7ea4 nilfs2: remove un... |
235 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9 nilfs2: reduce re... |
236 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
6d28f7ea4 nilfs2: remove un... |
237 |
nchildren = nilfs_btree_node_get_nchildren(node); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
244 245 |
dkeys[index] = cpu_to_le64(key); dptrs[index] = cpu_to_le64(ptr); |
17c76b010 nilfs2: B-tree ba... |
246 |
nchildren++; |
6d28f7ea4 nilfs2: remove un... |
247 |
nilfs_btree_node_set_nchildren(node, nchildren); |
17c76b010 nilfs2: B-tree ba... |
248 249 250 |
} /* Assume that the buffer head corresponding to node is locked. */ |
9b7b265c9 nilfs2: reduce re... |
251 252 |
static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index, __u64 *keyp, __u64 *ptrp, int ncmax) |
17c76b010 nilfs2: B-tree ba... |
253 254 255 256 257 258 |
{ __u64 key; __u64 ptr; __le64 *dkeys; __le64 *dptrs; int nchildren; |
6d28f7ea4 nilfs2: remove un... |
259 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9 nilfs2: reduce re... |
260 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
25b8d7ded nilfs2: get rid o... |
261 262 |
key = le64_to_cpu(dkeys[index]); ptr = le64_to_cpu(dptrs[index]); |
6d28f7ea4 nilfs2: remove un... |
263 |
nchildren = nilfs_btree_node_get_nchildren(node); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
276 |
nilfs_btree_node_set_nchildren(node, nchildren); |
17c76b010 nilfs2: B-tree ba... |
277 |
} |
6d28f7ea4 nilfs2: remove un... |
278 |
static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node, |
17c76b010 nilfs2: B-tree ba... |
279 280 281 282 283 284 285 |
__u64 key, int *indexp) { __u64 nkey; int index, low, high, s; /* binary search */ low = 0; |
6d28f7ea4 nilfs2: remove un... |
286 |
high = nilfs_btree_node_get_nchildren(node) - 1; |
17c76b010 nilfs2: B-tree ba... |
287 288 289 290 |
index = 0; s = 0; while (low <= high) { index = (low + high) / 2; |
6d28f7ea4 nilfs2: remove un... |
291 |
nkey = nilfs_btree_node_get_key(node, index); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
305 306 |
if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) { if (s > 0 && index > 0) |
17c76b010 nilfs2: B-tree ba... |
307 308 309 310 311 |
index--; } else if (s < 0) index++; out: |
17c76b010 nilfs2: B-tree ba... |
312 313 314 315 |
*indexp = index; return s == 0; } |
1d5385b9f nilfs2: verify bt... |
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 nilfs2: introduce... |
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 nilfs2: verify bt... |
356 |
bh->b_size, bh->b_blocknr); |
4e13e66be nilfs2: introduce... |
357 358 359 |
if (likely(!ret)) set_buffer_nilfs_checked(bh); return ret; |
1d5385b9f nilfs2: verify bt... |
360 |
} |
7c397a81f nilfs2: eliminate... |
361 |
static struct nilfs_btree_node * |
e7c274f80 nilfs2: get rid o... |
362 |
nilfs_btree_get_root(const struct nilfs_bmap *btree) |
17c76b010 nilfs2: B-tree ba... |
363 |
{ |
e7c274f80 nilfs2: get rid o... |
364 |
return (struct nilfs_btree_node *)btree->b_u.u_data; |
17c76b010 nilfs2: B-tree ba... |
365 |
} |
7c397a81f nilfs2: eliminate... |
366 |
static struct nilfs_btree_node * |
6d28f7ea4 nilfs2: remove un... |
367 |
nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) |
17c76b010 nilfs2: B-tree ba... |
368 369 370 |
{ return (struct nilfs_btree_node *)path[level].bp_bh->b_data; } |
7c397a81f nilfs2: eliminate... |
371 |
static struct nilfs_btree_node * |
6d28f7ea4 nilfs2: remove un... |
372 |
nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) |
17c76b010 nilfs2: B-tree ba... |
373 374 375 |
{ return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; } |
7c397a81f nilfs2: eliminate... |
376 |
static int nilfs_btree_height(const struct nilfs_bmap *btree) |
17c76b010 nilfs2: B-tree ba... |
377 |
{ |
6d28f7ea4 nilfs2: remove un... |
378 |
return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1; |
17c76b010 nilfs2: B-tree ba... |
379 |
} |
9b7b265c9 nilfs2: reduce re... |
380 |
static struct nilfs_btree_node * |
e7c274f80 nilfs2: get rid o... |
381 |
nilfs_btree_get_node(const struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
382 |
const struct nilfs_btree_path *path, |
9b7b265c9 nilfs2: reduce re... |
383 |
int level, int *ncmaxp) |
17c76b010 nilfs2: B-tree ba... |
384 |
{ |
9b7b265c9 nilfs2: reduce re... |
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 nilfs2: B-tree ba... |
395 |
} |
7c397a81f nilfs2: eliminate... |
396 |
static int |
9b945d537 nilfs2: get rid o... |
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 nilfs2: add btree... |
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 nilfs2: get rid o... |
475 |
static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
476 |
struct nilfs_btree_path *path, |
03bdb5ac5 nilfs2: apply rea... |
477 478 |
__u64 key, __u64 *ptrp, int minlevel, int readahead) |
17c76b010 nilfs2: B-tree ba... |
479 480 |
{ struct nilfs_btree_node *node; |
03bdb5ac5 nilfs2: apply rea... |
481 |
struct nilfs_btree_readahead_info p, *ra; |
17c76b010 nilfs2: B-tree ba... |
482 |
__u64 ptr; |
ea64ab87c nilfs2: optimize ... |
483 |
int level, index, found, ncmax, ret; |
17c76b010 nilfs2: B-tree ba... |
484 |
|
17c76b010 nilfs2: B-tree ba... |
485 |
node = nilfs_btree_get_root(btree); |
6d28f7ea4 nilfs2: remove un... |
486 487 |
level = nilfs_btree_node_get_level(node); if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) |
17c76b010 nilfs2: B-tree ba... |
488 |
return -ENOENT; |
6d28f7ea4 nilfs2: remove un... |
489 |
found = nilfs_btree_node_lookup(node, key, &index); |
9b7b265c9 nilfs2: reduce re... |
490 491 |
ptr = nilfs_btree_node_get_ptr(node, index, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010 nilfs2: B-tree ba... |
492 493 |
path[level].bp_bh = NULL; path[level].bp_index = index; |
9b7b265c9 nilfs2: reduce re... |
494 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
ea64ab87c nilfs2: optimize ... |
495 |
|
03bdb5ac5 nilfs2: apply rea... |
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 nilfs2: B-tree ba... |
507 508 |
if (ret < 0) return ret; |
03bdb5ac5 nilfs2: apply rea... |
509 |
|
6d28f7ea4 nilfs2: remove un... |
510 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b945d537 nilfs2: get rid o... |
511 512 |
if (nilfs_btree_bad_node(node, level)) return -EINVAL; |
17c76b010 nilfs2: B-tree ba... |
513 |
if (!found) |
6d28f7ea4 nilfs2: remove un... |
514 |
found = nilfs_btree_node_lookup(node, key, &index); |
17c76b010 nilfs2: B-tree ba... |
515 516 |
else index = 0; |
ea64ab87c nilfs2: optimize ... |
517 |
if (index < ncmax) { |
9b7b265c9 nilfs2: reduce re... |
518 |
ptr = nilfs_btree_node_get_ptr(node, index, ncmax); |
ea64ab87c nilfs2: optimize ... |
519 |
} else { |
1f5abe7e7 nilfs2: replace B... |
520 |
WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
534 |
static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
535 536 537 538 539 |
struct nilfs_btree_path *path, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node; __u64 ptr; |
9b7b265c9 nilfs2: reduce re... |
540 |
int index, level, ncmax, ret; |
17c76b010 nilfs2: B-tree ba... |
541 542 |
node = nilfs_btree_get_root(btree); |
6d28f7ea4 nilfs2: remove un... |
543 |
index = nilfs_btree_node_get_nchildren(node) - 1; |
17c76b010 nilfs2: B-tree ba... |
544 545 |
if (index < 0) return -ENOENT; |
6d28f7ea4 nilfs2: remove un... |
546 |
level = nilfs_btree_node_get_level(node); |
9b7b265c9 nilfs2: reduce re... |
547 548 |
ptr = nilfs_btree_node_get_ptr(node, index, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010 nilfs2: B-tree ba... |
549 550 |
path[level].bp_bh = NULL; path[level].bp_index = index; |
9b7b265c9 nilfs2: reduce re... |
551 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
552 553 |
for (level--; level > 0; level--) { |
f198dbb9c nilfs2: move get ... |
554 |
ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
555 556 |
if (ret < 0) return ret; |
6d28f7ea4 nilfs2: remove un... |
557 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b945d537 nilfs2: get rid o... |
558 559 |
if (nilfs_btree_bad_node(node, level)) return -EINVAL; |
6d28f7ea4 nilfs2: remove un... |
560 |
index = nilfs_btree_node_get_nchildren(node) - 1; |
9b7b265c9 nilfs2: reduce re... |
561 |
ptr = nilfs_btree_node_get_ptr(node, index, ncmax); |
17c76b010 nilfs2: B-tree ba... |
562 563 564 565 |
path[level].bp_index = index; } if (keyp != NULL) |
6d28f7ea4 nilfs2: remove un... |
566 |
*keyp = nilfs_btree_node_get_key(node, index); |
17c76b010 nilfs2: B-tree ba... |
567 568 569 570 571 |
if (ptrp != NULL) *ptrp = ptr; return 0; } |
e7c274f80 nilfs2: get rid o... |
572 |
static int nilfs_btree_lookup(const struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
573 574 |
__u64 key, int level, __u64 *ptrp) { |
17c76b010 nilfs2: B-tree ba... |
575 |
struct nilfs_btree_path *path; |
17c76b010 nilfs2: B-tree ba... |
576 |
int ret; |
6d28f7ea4 nilfs2: remove un... |
577 |
path = nilfs_btree_alloc_path(); |
17c76b010 nilfs2: B-tree ba... |
578 579 |
if (path == NULL) return -ENOMEM; |
17c76b010 nilfs2: B-tree ba... |
580 |
|
03bdb5ac5 nilfs2: apply rea... |
581 |
ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0); |
17c76b010 nilfs2: B-tree ba... |
582 |
|
6d28f7ea4 nilfs2: remove un... |
583 |
nilfs_btree_free_path(path); |
17c76b010 nilfs2: B-tree ba... |
584 585 586 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
587 |
static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree, |
c3a7abf06 nilfs2: support c... |
588 589 |
__u64 key, __u64 *ptrp, unsigned maxblocks) { |
c3a7abf06 nilfs2: support c... |
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 nilfs2: reduce re... |
596 |
int ret, cnt, index, maxlevel, ncmax; |
03bdb5ac5 nilfs2: apply rea... |
597 |
struct nilfs_btree_readahead_info p; |
c3a7abf06 nilfs2: support c... |
598 |
|
6d28f7ea4 nilfs2: remove un... |
599 |
path = nilfs_btree_alloc_path(); |
c3a7abf06 nilfs2: support c... |
600 601 |
if (path == NULL) return -ENOMEM; |
f905440f5 nilfs2: Combine n... |
602 |
|
03bdb5ac5 nilfs2: apply rea... |
603 |
ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1); |
c3a7abf06 nilfs2: support c... |
604 605 |
if (ret < 0) goto out; |
e7c274f80 nilfs2: get rid o... |
606 607 |
if (NILFS_BMAP_USE_VBN(btree)) { dat = nilfs_bmap_get_dat(btree); |
c3a7abf06 nilfs2: support c... |
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 nilfs2: reduce re... |
618 |
node = nilfs_btree_get_node(btree, path, level, &ncmax); |
c3a7abf06 nilfs2: support c... |
619 620 |
index = path[level].bp_index + 1; for (;;) { |
6d28f7ea4 nilfs2: remove un... |
621 622 |
while (index < nilfs_btree_node_get_nchildren(node)) { if (nilfs_btree_node_get_key(node, index) != |
c3a7abf06 nilfs2: support c... |
623 624 |
key + cnt) goto end; |
9b7b265c9 nilfs2: reduce re... |
625 |
ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax); |
c3a7abf06 nilfs2: support c... |
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 nilfs2: apply rea... |
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 nilfs2: support c... |
646 |
break; |
03bdb5ac5 nilfs2: apply rea... |
647 648 |
ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax); path[level + 1].bp_index = p.index; |
c3a7abf06 nilfs2: support c... |
649 650 651 |
brelse(path[level].bp_bh); path[level].bp_bh = NULL; |
03bdb5ac5 nilfs2: apply rea... |
652 653 654 |
ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh, &p); |
c3a7abf06 nilfs2: support c... |
655 656 |
if (ret < 0) goto out; |
6d28f7ea4 nilfs2: remove un... |
657 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
658 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
c3a7abf06 nilfs2: support c... |
659 660 661 662 663 664 665 |
index = 0; path[level].bp_index = index; } end: *ptrp = ptr; ret = cnt; out: |
6d28f7ea4 nilfs2: remove un... |
666 |
nilfs_btree_free_path(path); |
c3a7abf06 nilfs2: support c... |
667 668 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
669 |
static void nilfs_btree_promote_key(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
670 671 672 673 674 |
struct nilfs_btree_path *path, int level, __u64 key) { if (level < nilfs_btree_height(btree) - 1) { do { |
17c76b010 nilfs2: B-tree ba... |
675 |
nilfs_btree_node_set_key( |
6d28f7ea4 nilfs2: remove un... |
676 |
nilfs_btree_get_nonroot_node(path, level), |
17c76b010 nilfs2: B-tree ba... |
677 678 |
path[level].bp_index, key); if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
679 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
686 |
nilfs_btree_node_set_key(nilfs_btree_get_root(btree), |
17c76b010 nilfs2: B-tree ba... |
687 688 689 |
path[level].bp_index, key); } } |
e7c274f80 nilfs2: get rid o... |
690 |
static void nilfs_btree_do_insert(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
691 692 693 694 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node; |
9b7b265c9 nilfs2: reduce re... |
695 |
int ncblk; |
17c76b010 nilfs2: B-tree ba... |
696 697 |
if (level < nilfs_btree_height(btree) - 1) { |
6d28f7ea4 nilfs2: remove un... |
698 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
699 700 701 |
ncblk = nilfs_btree_nchildren_per_block(btree); nilfs_btree_node_insert(node, path[level].bp_index, *keyp, *ptrp, ncblk); |
17c76b010 nilfs2: B-tree ba... |
702 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
703 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
704 705 706 |
if (path[level].bp_index == 0) nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4 nilfs2: remove un... |
707 708 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010 nilfs2: B-tree ba... |
709 710 |
} else { node = nilfs_btree_get_root(btree); |
9b7b265c9 nilfs2: reduce re... |
711 712 713 |
nilfs_btree_node_insert(node, path[level].bp_index, *keyp, *ptrp, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010 nilfs2: B-tree ba... |
714 715 |
} } |
e7c274f80 nilfs2: get rid o... |
716 |
static void nilfs_btree_carry_left(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
717 718 719 720 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *left; |
9b7b265c9 nilfs2: reduce re... |
721 |
int nchildren, lnchildren, n, move, ncblk; |
17c76b010 nilfs2: B-tree ba... |
722 |
|
6d28f7ea4 nilfs2: remove un... |
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 nilfs2: reduce re... |
727 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: reduce re... |
736 |
nilfs_btree_node_move_left(left, node, n, ncblk, ncblk); |
17c76b010 nilfs2: B-tree ba... |
737 738 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
739 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
740 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417 nilfs2: use mark_... |
741 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
742 |
|
17c76b010 nilfs2: B-tree ba... |
743 |
nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4 nilfs2: remove un... |
744 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010 nilfs2: B-tree ba... |
745 746 |
if (move) { |
087d01b42 nilfs2: remove ni... |
747 |
brelse(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove ni... |
753 |
brelse(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
760 |
static void nilfs_btree_carry_right(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
761 762 763 764 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *right; |
9b7b265c9 nilfs2: reduce re... |
765 |
int nchildren, rnchildren, n, move, ncblk; |
17c76b010 nilfs2: B-tree ba... |
766 |
|
6d28f7ea4 nilfs2: remove un... |
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 nilfs2: reduce re... |
771 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: reduce re... |
780 |
nilfs_btree_node_move_right(node, right, n, ncblk, ncblk); |
17c76b010 nilfs2: B-tree ba... |
781 782 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
783 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
784 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417 nilfs2: use mark_... |
785 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
786 |
|
17c76b010 nilfs2: B-tree ba... |
787 788 |
path[level + 1].bp_index++; nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4 nilfs2: remove un... |
789 |
nilfs_btree_node_get_key(right, 0)); |
17c76b010 nilfs2: B-tree ba... |
790 791 792 |
path[level + 1].bp_index--; if (move) { |
087d01b42 nilfs2: remove ni... |
793 |
brelse(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
794 795 |
path[level].bp_bh = path[level].bp_sib_bh; path[level].bp_sib_bh = NULL; |
6d28f7ea4 nilfs2: remove un... |
796 |
path[level].bp_index -= nilfs_btree_node_get_nchildren(node); |
17c76b010 nilfs2: B-tree ba... |
797 798 |
path[level + 1].bp_index++; } else { |
087d01b42 nilfs2: remove ni... |
799 |
brelse(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
800 801 802 803 804 |
path[level].bp_sib_bh = NULL; } nilfs_btree_do_insert(btree, path, level, keyp, ptrp); } |
e7c274f80 nilfs2: get rid o... |
805 |
static void nilfs_btree_split(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: reduce re... |
812 |
int nchildren, n, move, ncblk; |
17c76b010 nilfs2: B-tree ba... |
813 |
|
6d28f7ea4 nilfs2: remove un... |
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 nilfs2: reduce re... |
817 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
818 819 820 821 822 823 824 |
move = 0; n = (nchildren + 1) / 2; if (n > nchildren - path[level].bp_index) { n--; move = 1; } |
9b7b265c9 nilfs2: reduce re... |
825 |
nilfs_btree_node_move_right(node, right, n, ncblk, ncblk); |
17c76b010 nilfs2: B-tree ba... |
826 827 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
828 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
829 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417 nilfs2: use mark_... |
830 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
831 |
|
6d28f7ea4 nilfs2: remove un... |
832 |
newkey = nilfs_btree_node_get_key(right, 0); |
17c76b010 nilfs2: B-tree ba... |
833 834 835 |
newptr = path[level].bp_newreq.bpr_ptr; if (move) { |
6d28f7ea4 nilfs2: remove un... |
836 |
path[level].bp_index -= nilfs_btree_node_get_nchildren(node); |
9b7b265c9 nilfs2: reduce re... |
837 838 |
nilfs_btree_node_insert(right, path[level].bp_index, *keyp, *ptrp, ncblk); |
17c76b010 nilfs2: B-tree ba... |
839 |
|
6d28f7ea4 nilfs2: remove un... |
840 |
*keyp = nilfs_btree_node_get_key(right, 0); |
17c76b010 nilfs2: B-tree ba... |
841 |
*ptrp = path[level].bp_newreq.bpr_ptr; |
087d01b42 nilfs2: remove ni... |
842 |
brelse(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
847 |
*keyp = nilfs_btree_node_get_key(right, 0); |
17c76b010 nilfs2: B-tree ba... |
848 |
*ptrp = path[level].bp_newreq.bpr_ptr; |
087d01b42 nilfs2: remove ni... |
849 |
brelse(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
850 851 852 853 854 |
path[level].bp_sib_bh = NULL; } path[level + 1].bp_index++; } |
e7c274f80 nilfs2: get rid o... |
855 |
static void nilfs_btree_grow(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
856 857 858 859 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *root, *child; |
9b7b265c9 nilfs2: reduce re... |
860 |
int n, ncblk; |
17c76b010 nilfs2: B-tree ba... |
861 |
|
17c76b010 nilfs2: B-tree ba... |
862 |
root = nilfs_btree_get_root(btree); |
6d28f7ea4 nilfs2: remove un... |
863 |
child = nilfs_btree_get_sib_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
864 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
865 |
|
6d28f7ea4 nilfs2: remove un... |
866 |
n = nilfs_btree_node_get_nchildren(root); |
17c76b010 nilfs2: B-tree ba... |
867 |
|
9b7b265c9 nilfs2: reduce re... |
868 869 |
nilfs_btree_node_move_right(root, child, n, NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk); |
6d28f7ea4 nilfs2: remove un... |
870 |
nilfs_btree_node_set_level(root, level + 1); |
17c76b010 nilfs2: B-tree ba... |
871 872 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417 nilfs2: use mark_... |
873 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
874 |
|
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
879 |
*keyp = nilfs_btree_node_get_key(child, 0); |
17c76b010 nilfs2: B-tree ba... |
880 881 |
*ptrp = path[level].bp_newreq.bpr_ptr; } |
e7c274f80 nilfs2: get rid o... |
882 |
static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
883 884 885 |
const struct nilfs_btree_path *path) { struct nilfs_btree_node *node; |
9b7b265c9 nilfs2: reduce re... |
886 |
int level, ncmax; |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: reduce re... |
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 nilfs2: B-tree ba... |
898 899 900 901 902 |
} /* parent */ level = NILFS_BTREE_LEVEL_NODE_MIN + 1; if (level <= nilfs_btree_height(btree) - 1) { |
9b7b265c9 nilfs2: reduce re... |
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 nilfs2: B-tree ba... |
906 907 908 909 |
} return NILFS_BMAP_INVALID_PTR; } |
e7c274f80 nilfs2: get rid o... |
910 |
static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
911 912 913 914 |
const struct nilfs_btree_path *path, __u64 key) { __u64 ptr; |
e7c274f80 nilfs2: get rid o... |
915 |
ptr = nilfs_bmap_find_target_seq(btree, key); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
926 |
return nilfs_bmap_find_target_in_group(btree); |
17c76b010 nilfs2: B-tree ba... |
927 |
} |
e7c274f80 nilfs2: get rid o... |
928 |
static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: reduce re... |
936 |
int pindex, level, ncmax, ncblk, ret; |
2e0c2c739 nilfs2: allow btr... |
937 |
struct inode *dat = NULL; |
17c76b010 nilfs2: B-tree ba... |
938 939 940 941 942 |
stats->bs_nblocks = 0; level = NILFS_BTREE_LEVEL_DATA; /* allocate a new ptr for data block */ |
e7c274f80 nilfs2: get rid o... |
943 |
if (NILFS_BMAP_USE_VBN(btree)) { |
17c76b010 nilfs2: B-tree ba... |
944 |
path[level].bp_newreq.bpr_ptr = |
7cde31d7d nilfs2: remove ni... |
945 |
nilfs_btree_find_target_v(btree, path, key); |
e7c274f80 nilfs2: get rid o... |
946 |
dat = nilfs_bmap_get_dat(btree); |
2e0c2c739 nilfs2: allow btr... |
947 |
} |
17c76b010 nilfs2: B-tree ba... |
948 |
|
e7c274f80 nilfs2: get rid o... |
949 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010 nilfs2: B-tree ba... |
950 951 |
if (ret < 0) goto err_out_data; |
9b7b265c9 nilfs2: reduce re... |
952 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
ea64ab87c nilfs2: optimize ... |
953 |
|
17c76b010 nilfs2: B-tree ba... |
954 955 956 |
for (level = NILFS_BTREE_LEVEL_NODE_MIN; level < nilfs_btree_height(btree) - 1; level++) { |
6d28f7ea4 nilfs2: remove un... |
957 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
958 |
if (nilfs_btree_node_get_nchildren(node) < ncblk) { |
17c76b010 nilfs2: B-tree ba... |
959 960 961 962 |
path[level].bp_op = nilfs_btree_do_insert; stats->bs_nblocks++; goto out; } |
9b7b265c9 nilfs2: reduce re... |
963 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); |
17c76b010 nilfs2: B-tree ba... |
964 965 966 967 |
pindex = path[level + 1].bp_index; /* left sibling */ if (pindex > 0) { |
9b7b265c9 nilfs2: reduce re... |
968 969 |
sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1, ncmax); |
f198dbb9c nilfs2: move get ... |
970 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
971 972 973 |
if (ret < 0) goto err_out_child_node; sib = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9 nilfs2: reduce re... |
974 |
if (nilfs_btree_node_get_nchildren(sib) < ncblk) { |
17c76b010 nilfs2: B-tree ba... |
975 976 977 978 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_carry_left; stats->bs_nblocks++; goto out; |
9b7b265c9 nilfs2: reduce re... |
979 |
} else { |
087d01b42 nilfs2: remove ni... |
980 |
brelse(bh); |
9b7b265c9 nilfs2: reduce re... |
981 |
} |
17c76b010 nilfs2: B-tree ba... |
982 983 984 |
} /* right sibling */ |
9b7b265c9 nilfs2: reduce re... |
985 986 987 |
if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) { sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1, ncmax); |
f198dbb9c nilfs2: move get ... |
988 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
989 990 991 |
if (ret < 0) goto err_out_child_node; sib = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9 nilfs2: reduce re... |
992 |
if (nilfs_btree_node_get_nchildren(sib) < ncblk) { |
17c76b010 nilfs2: B-tree ba... |
993 994 995 996 |
path[level].bp_sib_bh = bh; path[level].bp_op = nilfs_btree_carry_right; stats->bs_nblocks++; goto out; |
9b7b265c9 nilfs2: reduce re... |
997 |
} else { |
087d01b42 nilfs2: remove ni... |
998 |
brelse(bh); |
9b7b265c9 nilfs2: reduce re... |
999 |
} |
17c76b010 nilfs2: B-tree ba... |
1000 1001 1002 1003 1004 |
} /* split */ path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; |
e7c274f80 nilfs2: get rid o... |
1005 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, |
2e0c2c739 nilfs2: allow btr... |
1006 |
&path[level].bp_newreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1007 1008 |
if (ret < 0) goto err_out_child_node; |
f198dbb9c nilfs2: move get ... |
1009 1010 1011 |
ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
1012 1013 1014 1015 |
if (ret < 0) goto err_out_curr_node; stats->bs_nblocks++; |
9b7b265c9 nilfs2: reduce re... |
1016 1017 |
sib = (struct nilfs_btree_node *)bh->b_data; nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
1024 |
if (nilfs_btree_node_get_nchildren(node) < |
ea64ab87c nilfs2: optimize ... |
1025 |
NILFS_BTREE_ROOT_NCHILDREN_MAX) { |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1033 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1034 1035 |
if (ret < 0) goto err_out_child_node; |
f198dbb9c nilfs2: move get ... |
1036 1037 |
ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
1038 1039 |
if (ret < 0) goto err_out_curr_node; |
9b7b265c9 nilfs2: reduce re... |
1040 1041 |
nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data, 0, level, 0, ncblk, NULL, NULL); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1058 |
nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1059 1060 |
err_out_child_node: for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { |
9f098900a nilfs2: remove ni... |
1061 |
nilfs_btnode_delete(path[level].bp_sib_bh); |
e7c274f80 nilfs2: get rid o... |
1062 |
nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1063 1064 |
} |
e7c274f80 nilfs2: get rid o... |
1065 |
nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1066 1067 1068 1069 1070 |
err_out_data: *levelp = level; stats->bs_nblocks = 0; return ret; } |
e7c274f80 nilfs2: get rid o... |
1071 |
static void nilfs_btree_commit_insert(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1072 1073 1074 |
struct nilfs_btree_path *path, int maxlevel, __u64 key, __u64 ptr) { |
2e0c2c739 nilfs2: allow btr... |
1075 |
struct inode *dat = NULL; |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1080 |
if (NILFS_BMAP_USE_VBN(btree)) { |
dc935be2a nilfs2: unify bma... |
1081 |
nilfs_bmap_set_target_v(btree, key, ptr); |
e7c274f80 nilfs2: get rid o... |
1082 |
dat = nilfs_bmap_get_dat(btree); |
2e0c2c739 nilfs2: allow btr... |
1083 |
} |
17c76b010 nilfs2: B-tree ba... |
1084 1085 |
for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { |
e7c274f80 nilfs2: get rid o... |
1086 |
nilfs_bmap_commit_alloc_ptr(btree, |
2e0c2c739 nilfs2: allow btr... |
1087 |
&path[level - 1].bp_newreq, dat); |
8acfbf093 nilfs2: clean up ... |
1088 |
path[level].bp_op(btree, path, level, &key, &ptr); |
17c76b010 nilfs2: B-tree ba... |
1089 |
} |
e7c274f80 nilfs2: get rid o... |
1090 1091 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010 nilfs2: B-tree ba... |
1092 |
} |
e7c274f80 nilfs2: get rid o... |
1093 |
static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr) |
17c76b010 nilfs2: B-tree ba... |
1094 |
{ |
17c76b010 nilfs2: B-tree ba... |
1095 1096 1097 |
struct nilfs_btree_path *path; struct nilfs_bmap_stats stats; int level, ret; |
6d28f7ea4 nilfs2: remove un... |
1098 |
path = nilfs_btree_alloc_path(); |
17c76b010 nilfs2: B-tree ba... |
1099 1100 |
if (path == NULL) return -ENOMEM; |
17c76b010 nilfs2: B-tree ba... |
1101 1102 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, |
03bdb5ac5 nilfs2: apply rea... |
1103 |
NILFS_BTREE_LEVEL_NODE_MIN, 0); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: record us... |
1114 |
nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks); |
17c76b010 nilfs2: B-tree ba... |
1115 1116 |
out: |
6d28f7ea4 nilfs2: remove un... |
1117 |
nilfs_btree_free_path(path); |
17c76b010 nilfs2: B-tree ba... |
1118 1119 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
1120 |
static void nilfs_btree_do_delete(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1121 1122 1123 1124 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node; |
9b7b265c9 nilfs2: reduce re... |
1125 |
int ncblk; |
17c76b010 nilfs2: B-tree ba... |
1126 1127 |
if (level < nilfs_btree_height(btree) - 1) { |
6d28f7ea4 nilfs2: remove un... |
1128 |
node = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
1129 1130 1131 |
ncblk = nilfs_btree_nchildren_per_block(btree); nilfs_btree_node_delete(node, path[level].bp_index, keyp, ptrp, ncblk); |
17c76b010 nilfs2: B-tree ba... |
1132 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
1133 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
1134 1135 |
if (path[level].bp_index == 0) nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4 nilfs2: remove un... |
1136 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010 nilfs2: B-tree ba... |
1137 1138 |
} else { node = nilfs_btree_get_root(btree); |
9b7b265c9 nilfs2: reduce re... |
1139 1140 1141 |
nilfs_btree_node_delete(node, path[level].bp_index, keyp, ptrp, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
17c76b010 nilfs2: B-tree ba... |
1142 1143 |
} } |
e7c274f80 nilfs2: get rid o... |
1144 |
static void nilfs_btree_borrow_left(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1145 1146 1147 1148 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *left; |
9b7b265c9 nilfs2: reduce re... |
1149 |
int nchildren, lnchildren, n, ncblk; |
17c76b010 nilfs2: B-tree ba... |
1150 1151 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4 nilfs2: remove un... |
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 nilfs2: reduce re... |
1156 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
1157 1158 |
n = (nchildren + lnchildren) / 2 - nchildren; |
9b7b265c9 nilfs2: reduce re... |
1159 |
nilfs_btree_node_move_right(left, node, n, ncblk, ncblk); |
17c76b010 nilfs2: B-tree ba... |
1160 1161 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
1162 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
1163 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417 nilfs2: use mark_... |
1164 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
1165 |
|
17c76b010 nilfs2: B-tree ba... |
1166 |
nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4 nilfs2: remove un... |
1167 |
nilfs_btree_node_get_key(node, 0)); |
17c76b010 nilfs2: B-tree ba... |
1168 |
|
087d01b42 nilfs2: remove ni... |
1169 |
brelse(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
1170 1171 1172 |
path[level].bp_sib_bh = NULL; path[level].bp_index += n; } |
e7c274f80 nilfs2: get rid o... |
1173 |
static void nilfs_btree_borrow_right(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1174 1175 1176 1177 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *right; |
9b7b265c9 nilfs2: reduce re... |
1178 |
int nchildren, rnchildren, n, ncblk; |
17c76b010 nilfs2: B-tree ba... |
1179 1180 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4 nilfs2: remove un... |
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 nilfs2: reduce re... |
1185 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
1186 1187 |
n = (nchildren + rnchildren) / 2 - nchildren; |
9b7b265c9 nilfs2: reduce re... |
1188 |
nilfs_btree_node_move_left(node, right, n, ncblk, ncblk); |
17c76b010 nilfs2: B-tree ba... |
1189 1190 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
1191 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
1192 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417 nilfs2: use mark_... |
1193 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
1194 |
|
17c76b010 nilfs2: B-tree ba... |
1195 1196 |
path[level + 1].bp_index++; nilfs_btree_promote_key(btree, path, level + 1, |
6d28f7ea4 nilfs2: remove un... |
1197 |
nilfs_btree_node_get_key(right, 0)); |
17c76b010 nilfs2: B-tree ba... |
1198 |
path[level + 1].bp_index--; |
087d01b42 nilfs2: remove ni... |
1199 |
brelse(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
1200 1201 |
path[level].bp_sib_bh = NULL; } |
e7c274f80 nilfs2: get rid o... |
1202 |
static void nilfs_btree_concat_left(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1203 1204 1205 1206 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *left; |
9b7b265c9 nilfs2: reduce re... |
1207 |
int n, ncblk; |
17c76b010 nilfs2: B-tree ba... |
1208 1209 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4 nilfs2: remove un... |
1210 1211 |
node = nilfs_btree_get_nonroot_node(path, level); left = nilfs_btree_get_sib_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
1212 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
1213 |
|
6d28f7ea4 nilfs2: remove un... |
1214 |
n = nilfs_btree_node_get_nchildren(node); |
17c76b010 nilfs2: B-tree ba... |
1215 |
|
9b7b265c9 nilfs2: reduce re... |
1216 |
nilfs_btree_node_move_left(left, node, n, ncblk, ncblk); |
17c76b010 nilfs2: B-tree ba... |
1217 1218 |
if (!buffer_dirty(path[level].bp_sib_bh)) |
5fc7b1417 nilfs2: use mark_... |
1219 |
mark_buffer_dirty(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
1220 |
|
9f098900a nilfs2: remove ni... |
1221 |
nilfs_btnode_delete(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
1222 1223 |
path[level].bp_bh = path[level].bp_sib_bh; path[level].bp_sib_bh = NULL; |
6d28f7ea4 nilfs2: remove un... |
1224 |
path[level].bp_index += nilfs_btree_node_get_nchildren(left); |
17c76b010 nilfs2: B-tree ba... |
1225 |
} |
e7c274f80 nilfs2: get rid o... |
1226 |
static void nilfs_btree_concat_right(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1227 1228 1229 1230 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *node, *right; |
9b7b265c9 nilfs2: reduce re... |
1231 |
int n, ncblk; |
17c76b010 nilfs2: B-tree ba... |
1232 1233 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
6d28f7ea4 nilfs2: remove un... |
1234 1235 |
node = nilfs_btree_get_nonroot_node(path, level); right = nilfs_btree_get_sib_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
1236 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
1237 |
|
6d28f7ea4 nilfs2: remove un... |
1238 |
n = nilfs_btree_node_get_nchildren(right); |
17c76b010 nilfs2: B-tree ba... |
1239 |
|
9b7b265c9 nilfs2: reduce re... |
1240 |
nilfs_btree_node_move_left(node, right, n, ncblk, ncblk); |
17c76b010 nilfs2: B-tree ba... |
1241 1242 |
if (!buffer_dirty(path[level].bp_bh)) |
5fc7b1417 nilfs2: use mark_... |
1243 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
1244 |
|
9f098900a nilfs2: remove ni... |
1245 |
nilfs_btnode_delete(path[level].bp_sib_bh); |
17c76b010 nilfs2: B-tree ba... |
1246 1247 1248 |
path[level].bp_sib_bh = NULL; path[level + 1].bp_index++; } |
e7c274f80 nilfs2: get rid o... |
1249 |
static void nilfs_btree_shrink(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1250 1251 1252 1253 |
struct nilfs_btree_path *path, int level, __u64 *keyp, __u64 *ptrp) { struct nilfs_btree_node *root, *child; |
9b7b265c9 nilfs2: reduce re... |
1254 |
int n, ncblk; |
17c76b010 nilfs2: B-tree ba... |
1255 1256 |
nilfs_btree_do_delete(btree, path, level, keyp, ptrp); |
17c76b010 nilfs2: B-tree ba... |
1257 |
root = nilfs_btree_get_root(btree); |
6d28f7ea4 nilfs2: remove un... |
1258 |
child = nilfs_btree_get_nonroot_node(path, level); |
9b7b265c9 nilfs2: reduce re... |
1259 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
1260 |
|
9b7b265c9 nilfs2: reduce re... |
1261 1262 |
nilfs_btree_node_delete(root, 0, NULL, NULL, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
6d28f7ea4 nilfs2: remove un... |
1263 1264 |
nilfs_btree_node_set_level(root, level); n = nilfs_btree_node_get_nchildren(child); |
9b7b265c9 nilfs2: reduce re... |
1265 1266 |
nilfs_btree_node_move_left(root, child, n, NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk); |
17c76b010 nilfs2: B-tree ba... |
1267 |
|
9f098900a nilfs2: remove ni... |
1268 |
nilfs_btnode_delete(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
1269 1270 |
path[level].bp_bh = NULL; } |
d40990537 nilfs2: fix missi... |
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 nilfs2: B-tree ba... |
1276 |
|
e7c274f80 nilfs2: get rid o... |
1277 |
static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1278 1279 |
struct nilfs_btree_path *path, int *levelp, |
2e0c2c739 nilfs2: allow btr... |
1280 1281 |
struct nilfs_bmap_stats *stats, struct inode *dat) |
17c76b010 nilfs2: B-tree ba... |
1282 1283 1284 1285 |
{ struct buffer_head *bh; struct nilfs_btree_node *node, *parent, *sib; __u64 sibptr; |
fe744fdb7 nilfs2: fix incor... |
1286 |
int pindex, dindex, level, ncmin, ncmax, ncblk, ret; |
17c76b010 nilfs2: B-tree ba... |
1287 1288 1289 |
ret = 0; stats->bs_nblocks = 0; |
ea64ab87c nilfs2: optimize ... |
1290 |
ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree)); |
9b7b265c9 nilfs2: reduce re... |
1291 |
ncblk = nilfs_btree_nchildren_per_block(btree); |
ea64ab87c nilfs2: optimize ... |
1292 |
|
fe744fdb7 nilfs2: fix incor... |
1293 |
for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index; |
17c76b010 nilfs2: B-tree ba... |
1294 1295 |
level < nilfs_btree_height(btree) - 1; level++) { |
6d28f7ea4 nilfs2: remove un... |
1296 |
node = nilfs_btree_get_nonroot_node(path, level); |
17c76b010 nilfs2: B-tree ba... |
1297 |
path[level].bp_oldreq.bpr_ptr = |
fe744fdb7 nilfs2: fix incor... |
1298 |
nilfs_btree_node_get_ptr(node, dindex, ncblk); |
e7c274f80 nilfs2: get rid o... |
1299 |
ret = nilfs_bmap_prepare_end_ptr(btree, |
2e0c2c739 nilfs2: allow btr... |
1300 |
&path[level].bp_oldreq, dat); |
d4b961576 nilfs2: remove bm... |
1301 1302 |
if (ret < 0) goto err_out_child_node; |
17c76b010 nilfs2: B-tree ba... |
1303 |
|
ea64ab87c nilfs2: optimize ... |
1304 |
if (nilfs_btree_node_get_nchildren(node) > ncmin) { |
17c76b010 nilfs2: B-tree ba... |
1305 1306 1307 1308 |
path[level].bp_op = nilfs_btree_do_delete; stats->bs_nblocks++; goto out; } |
9b7b265c9 nilfs2: reduce re... |
1309 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); |
17c76b010 nilfs2: B-tree ba... |
1310 |
pindex = path[level + 1].bp_index; |
fe744fdb7 nilfs2: fix incor... |
1311 |
dindex = pindex; |
17c76b010 nilfs2: B-tree ba... |
1312 1313 1314 |
if (pindex > 0) { /* left sibling */ |
9b7b265c9 nilfs2: reduce re... |
1315 1316 |
sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1, ncmax); |
f198dbb9c nilfs2: move get ... |
1317 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
1318 1319 1320 |
if (ret < 0) goto err_out_curr_node; sib = (struct nilfs_btree_node *)bh->b_data; |
ea64ab87c nilfs2: optimize ... |
1321 |
if (nilfs_btree_node_get_nchildren(sib) > ncmin) { |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
1333 |
nilfs_btree_node_get_nchildren(parent) - 1) { |
17c76b010 nilfs2: B-tree ba... |
1334 |
/* right sibling */ |
9b7b265c9 nilfs2: reduce re... |
1335 1336 |
sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1, ncmax); |
f198dbb9c nilfs2: move get ... |
1337 |
ret = nilfs_btree_get_block(btree, sibptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
1338 1339 1340 |
if (ret < 0) goto err_out_curr_node; sib = (struct nilfs_btree_node *)bh->b_data; |
ea64ab87c nilfs2: optimize ... |
1341 |
if (nilfs_btree_node_get_nchildren(sib) > ncmin) { |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: fix incor... |
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 nilfs2: B-tree ba... |
1358 1359 1360 1361 1362 |
/* continue; */ } } else { /* no siblings */ /* the only child of the root node */ |
1f5abe7e7 nilfs2: replace B... |
1363 |
WARN_ON(level != nilfs_btree_height(btree) - 2); |
6d28f7ea4 nilfs2: remove un... |
1364 |
if (nilfs_btree_node_get_nchildren(node) - 1 <= |
17c76b010 nilfs2: B-tree ba... |
1365 1366 1367 |
NILFS_BTREE_ROOT_NCHILDREN_MAX) { path[level].bp_op = nilfs_btree_shrink; stats->bs_nblocks += 2; |
d40990537 nilfs2: fix missi... |
1368 1369 1370 |
level++; path[level].bp_op = nilfs_btree_nop; goto shrink_root_child; |
17c76b010 nilfs2: B-tree ba... |
1371 1372 1373 |
} else { path[level].bp_op = nilfs_btree_do_delete; stats->bs_nblocks++; |
d40990537 nilfs2: fix missi... |
1374 |
goto out; |
17c76b010 nilfs2: B-tree ba... |
1375 |
} |
17c76b010 nilfs2: B-tree ba... |
1376 1377 |
} } |
d40990537 nilfs2: fix missi... |
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 nilfs2: B-tree ba... |
1383 1384 |
node = nilfs_btree_get_root(btree); path[level].bp_oldreq.bpr_ptr = |
fe744fdb7 nilfs2: fix incor... |
1385 |
nilfs_btree_node_get_ptr(node, dindex, |
9b7b265c9 nilfs2: reduce re... |
1386 |
NILFS_BTREE_ROOT_NCHILDREN_MAX); |
d4b961576 nilfs2: remove bm... |
1387 |
|
e7c274f80 nilfs2: get rid o... |
1388 |
ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat); |
d4b961576 nilfs2: remove bm... |
1389 1390 |
if (ret < 0) goto err_out_child_node; |
17c76b010 nilfs2: B-tree ba... |
1391 1392 1393 1394 1395 1396 1397 |
/* success */ out: *levelp = level; return ret; /* error */ err_out_curr_node: |
e7c274f80 nilfs2: get rid o... |
1398 |
nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1399 1400 |
err_out_child_node: for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { |
087d01b42 nilfs2: remove ni... |
1401 |
brelse(path[level].bp_sib_bh); |
e7c274f80 nilfs2: get rid o... |
1402 |
nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1403 1404 1405 1406 1407 |
} *levelp = level; stats->bs_nblocks = 0; return ret; } |
e7c274f80 nilfs2: get rid o... |
1408 |
static void nilfs_btree_commit_delete(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1409 |
struct nilfs_btree_path *path, |
2e0c2c739 nilfs2: allow btr... |
1410 |
int maxlevel, struct inode *dat) |
17c76b010 nilfs2: B-tree ba... |
1411 1412 1413 1414 |
{ int level; for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { |
e7c274f80 nilfs2: get rid o... |
1415 |
nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat); |
8acfbf093 nilfs2: clean up ... |
1416 |
path[level].bp_op(btree, path, level, NULL, NULL); |
17c76b010 nilfs2: B-tree ba... |
1417 |
} |
e7c274f80 nilfs2: get rid o... |
1418 1419 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010 nilfs2: B-tree ba... |
1420 |
} |
e7c274f80 nilfs2: get rid o... |
1421 |
static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key) |
17c76b010 nilfs2: B-tree ba... |
1422 1423 |
{ |
17c76b010 nilfs2: B-tree ba... |
1424 1425 |
struct nilfs_btree_path *path; struct nilfs_bmap_stats stats; |
2e0c2c739 nilfs2: allow btr... |
1426 |
struct inode *dat; |
17c76b010 nilfs2: B-tree ba... |
1427 |
int level, ret; |
6d28f7ea4 nilfs2: remove un... |
1428 |
path = nilfs_btree_alloc_path(); |
17c76b010 nilfs2: B-tree ba... |
1429 1430 |
if (path == NULL) return -ENOMEM; |
f905440f5 nilfs2: Combine n... |
1431 |
|
17c76b010 nilfs2: B-tree ba... |
1432 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, |
03bdb5ac5 nilfs2: apply rea... |
1433 |
NILFS_BTREE_LEVEL_NODE_MIN, 0); |
17c76b010 nilfs2: B-tree ba... |
1434 1435 |
if (ret < 0) goto out; |
2e0c2c739 nilfs2: allow btr... |
1436 |
|
e7c274f80 nilfs2: get rid o... |
1437 |
dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL; |
2e0c2c739 nilfs2: allow btr... |
1438 1439 |
ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); |
17c76b010 nilfs2: B-tree ba... |
1440 1441 |
if (ret < 0) goto out; |
2e0c2c739 nilfs2: allow btr... |
1442 |
nilfs_btree_commit_delete(btree, path, level, dat); |
be667377a nilfs2: record us... |
1443 |
nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks); |
17c76b010 nilfs2: B-tree ba... |
1444 1445 |
out: |
6d28f7ea4 nilfs2: remove un... |
1446 |
nilfs_btree_free_path(path); |
17c76b010 nilfs2: B-tree ba... |
1447 1448 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
1449 |
static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp) |
17c76b010 nilfs2: B-tree ba... |
1450 |
{ |
17c76b010 nilfs2: B-tree ba... |
1451 1452 |
struct nilfs_btree_path *path; int ret; |
6d28f7ea4 nilfs2: remove un... |
1453 |
path = nilfs_btree_alloc_path(); |
17c76b010 nilfs2: B-tree ba... |
1454 1455 |
if (path == NULL) return -ENOMEM; |
17c76b010 nilfs2: B-tree ba... |
1456 1457 |
ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL); |
6d28f7ea4 nilfs2: remove un... |
1458 |
nilfs_btree_free_path(path); |
17c76b010 nilfs2: B-tree ba... |
1459 1460 1461 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
1462 |
static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key) |
17c76b010 nilfs2: B-tree ba... |
1463 1464 |
{ struct buffer_head *bh; |
17c76b010 nilfs2: B-tree ba... |
1465 1466 1467 1468 |
struct nilfs_btree_node *root, *node; __u64 maxkey, nextmaxkey; __u64 ptr; int nchildren, ret; |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
1476 |
nchildren = nilfs_btree_node_get_nchildren(root); |
17c76b010 nilfs2: B-tree ba... |
1477 1478 |
if (nchildren > 1) return 0; |
9b7b265c9 nilfs2: reduce re... |
1479 1480 |
ptr = nilfs_btree_node_get_ptr(root, nchildren - 1, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
f198dbb9c nilfs2: move get ... |
1481 |
ret = nilfs_btree_get_block(btree, ptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
1489 1490 |
nchildren = nilfs_btree_node_get_nchildren(node); maxkey = nilfs_btree_node_get_key(node, nchildren - 1); |
17c76b010 nilfs2: B-tree ba... |
1491 |
nextmaxkey = (nchildren > 1) ? |
6d28f7ea4 nilfs2: remove un... |
1492 |
nilfs_btree_node_get_key(node, nchildren - 2) : 0; |
17c76b010 nilfs2: B-tree ba... |
1493 |
if (bh != NULL) |
087d01b42 nilfs2: remove ni... |
1494 |
brelse(bh); |
17c76b010 nilfs2: B-tree ba... |
1495 |
|
3033342a0 nilfs2: remove us... |
1496 |
return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW); |
17c76b010 nilfs2: B-tree ba... |
1497 |
} |
e7c274f80 nilfs2: get rid o... |
1498 |
static int nilfs_btree_gather_data(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1499 1500 1501 |
__u64 *keys, __u64 *ptrs, int nitems) { struct buffer_head *bh; |
17c76b010 nilfs2: B-tree ba... |
1502 1503 1504 1505 |
struct nilfs_btree_node *node, *root; __le64 *dkeys; __le64 *dptrs; __u64 ptr; |
9b7b265c9 nilfs2: reduce re... |
1506 |
int nchildren, ncmax, i, ret; |
17c76b010 nilfs2: B-tree ba... |
1507 |
|
17c76b010 nilfs2: B-tree ba... |
1508 1509 1510 1511 1512 |
root = nilfs_btree_get_root(btree); switch (nilfs_btree_height(btree)) { case 2: bh = NULL; node = root; |
9b7b265c9 nilfs2: reduce re... |
1513 |
ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX; |
17c76b010 nilfs2: B-tree ba... |
1514 1515 |
break; case 3: |
6d28f7ea4 nilfs2: remove un... |
1516 |
nchildren = nilfs_btree_node_get_nchildren(root); |
1f5abe7e7 nilfs2: replace B... |
1517 |
WARN_ON(nchildren > 1); |
9b7b265c9 nilfs2: reduce re... |
1518 1519 |
ptr = nilfs_btree_node_get_ptr(root, nchildren - 1, NILFS_BTREE_ROOT_NCHILDREN_MAX); |
f198dbb9c nilfs2: move get ... |
1520 |
ret = nilfs_btree_get_block(btree, ptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
1521 1522 1523 |
if (ret < 0) return ret; node = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9 nilfs2: reduce re... |
1524 |
ncmax = nilfs_btree_nchildren_per_block(btree); |
17c76b010 nilfs2: B-tree ba... |
1525 1526 1527 |
break; default: node = NULL; |
1f5abe7e7 nilfs2: replace B... |
1528 |
return -EINVAL; |
17c76b010 nilfs2: B-tree ba... |
1529 |
} |
6d28f7ea4 nilfs2: remove un... |
1530 |
nchildren = nilfs_btree_node_get_nchildren(node); |
17c76b010 nilfs2: B-tree ba... |
1531 1532 |
if (nchildren < nitems) nitems = nchildren; |
6d28f7ea4 nilfs2: remove un... |
1533 |
dkeys = nilfs_btree_node_dkeys(node); |
9b7b265c9 nilfs2: reduce re... |
1534 |
dptrs = nilfs_btree_node_dptrs(node, ncmax); |
17c76b010 nilfs2: B-tree ba... |
1535 |
for (i = 0; i < nitems; i++) { |
25b8d7ded nilfs2: get rid o... |
1536 1537 |
keys[i] = le64_to_cpu(dkeys[i]); ptrs[i] = le64_to_cpu(dptrs[i]); |
17c76b010 nilfs2: B-tree ba... |
1538 1539 1540 |
} if (bh != NULL) |
087d01b42 nilfs2: remove ni... |
1541 |
brelse(bh); |
17c76b010 nilfs2: B-tree ba... |
1542 1543 1544 1545 1546 |
return nitems; } static int |
e7c274f80 nilfs2: get rid o... |
1547 |
nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: allow btr... |
1554 |
struct inode *dat = NULL; |
17c76b010 nilfs2: B-tree ba... |
1555 |
int ret; |
17c76b010 nilfs2: B-tree ba... |
1556 1557 1558 1559 |
stats->bs_nblocks = 0; /* for data */ /* cannot find near ptr */ |
e7c274f80 nilfs2: get rid o... |
1560 |
if (NILFS_BMAP_USE_VBN(btree)) { |
7cde31d7d nilfs2: remove ni... |
1561 |
dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key); |
e7c274f80 nilfs2: get rid o... |
1562 |
dat = nilfs_bmap_get_dat(btree); |
2e0c2c739 nilfs2: allow btr... |
1563 |
} |
7cde31d7d nilfs2: remove ni... |
1564 |
|
e7c274f80 nilfs2: get rid o... |
1565 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1573 |
ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1574 1575 |
if (ret < 0) goto err_out_dreq; |
f198dbb9c nilfs2: move get ... |
1576 |
ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1589 |
nilfs_bmap_abort_alloc_ptr(btree, nreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1590 |
err_out_dreq: |
e7c274f80 nilfs2: get rid o... |
1591 |
nilfs_bmap_abort_alloc_ptr(btree, dreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1592 1593 1594 1595 1596 1597 |
stats->bs_nblocks = 0; return ret; } static void |
e7c274f80 nilfs2: get rid o... |
1598 |
nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1599 1600 |
__u64 key, __u64 ptr, const __u64 *keys, const __u64 *ptrs, |
3033342a0 nilfs2: remove us... |
1601 |
int n, |
17c76b010 nilfs2: B-tree ba... |
1602 1603 1604 1605 |
union nilfs_bmap_ptr_req *dreq, union nilfs_bmap_ptr_req *nreq, struct buffer_head *bh) { |
17c76b010 nilfs2: B-tree ba... |
1606 |
struct nilfs_btree_node *node; |
2e0c2c739 nilfs2: allow btr... |
1607 |
struct inode *dat; |
17c76b010 nilfs2: B-tree ba... |
1608 |
__u64 tmpptr; |
9b7b265c9 nilfs2: reduce re... |
1609 |
int ncblk; |
17c76b010 nilfs2: B-tree ba... |
1610 1611 |
/* free resources */ |
e7c274f80 nilfs2: get rid o... |
1612 1613 |
if (btree->b_ops->bop_clear != NULL) btree->b_ops->bop_clear(btree); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1619 1620 |
dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL; nilfs_btree_init(btree); |
17c76b010 nilfs2: B-tree ba... |
1621 |
if (nreq != NULL) { |
e7c274f80 nilfs2: get rid o... |
1622 1623 |
nilfs_bmap_commit_alloc_ptr(btree, dreq, dat); nilfs_bmap_commit_alloc_ptr(btree, nreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1624 1625 |
/* create child node at level 1 */ |
17c76b010 nilfs2: B-tree ba... |
1626 |
node = (struct nilfs_btree_node *)bh->b_data; |
9b7b265c9 nilfs2: reduce re... |
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 nilfs2: B-tree ba... |
1630 |
if (!buffer_dirty(bh)) |
5fc7b1417 nilfs2: use mark_... |
1631 |
mark_buffer_dirty(bh); |
e7c274f80 nilfs2: get rid o... |
1632 1633 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010 nilfs2: B-tree ba... |
1634 |
|
087d01b42 nilfs2: remove ni... |
1635 |
brelse(bh); |
17c76b010 nilfs2: B-tree ba... |
1636 1637 1638 1639 |
/* create root node at level 2 */ node = nilfs_btree_get_root(btree); tmpptr = nreq->bpr_ptr; |
9b7b265c9 nilfs2: reduce re... |
1640 1641 1642 |
nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1, NILFS_BTREE_ROOT_NCHILDREN_MAX, &keys[0], &tmpptr); |
17c76b010 nilfs2: B-tree ba... |
1643 |
} else { |
e7c274f80 nilfs2: get rid o... |
1644 |
nilfs_bmap_commit_alloc_ptr(btree, dreq, dat); |
17c76b010 nilfs2: B-tree ba... |
1645 1646 1647 |
/* create root node at level 1 */ node = nilfs_btree_get_root(btree); |
9b7b265c9 nilfs2: reduce re... |
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 nilfs2: get rid o... |
1653 1654 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010 nilfs2: B-tree ba... |
1655 |
} |
e7c274f80 nilfs2: get rid o... |
1656 |
if (NILFS_BMAP_USE_VBN(btree)) |
dc935be2a nilfs2: unify bma... |
1657 |
nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr); |
17c76b010 nilfs2: B-tree ba... |
1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 |
} /** * nilfs_btree_convert_and_insert - * @bmap: * @key: * @ptr: * @keys: * @ptrs: * @n: |
17c76b010 nilfs2: B-tree ba... |
1668 |
*/ |
e7c274f80 nilfs2: get rid o... |
1669 |
int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1670 |
__u64 key, __u64 ptr, |
3033342a0 nilfs2: remove us... |
1671 |
const __u64 *keys, const __u64 *ptrs, int n) |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1682 |
1 << btree->b_inode->i_blkbits)) { |
17c76b010 nilfs2: B-tree ba... |
1683 1684 1685 1686 1687 1688 1689 |
di = &dreq; ni = &nreq; } else { di = NULL; ni = NULL; BUG(); } |
e7c274f80 nilfs2: get rid o... |
1690 |
ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh, |
17c76b010 nilfs2: B-tree ba... |
1691 1692 1693 |
&stats); if (ret < 0) return ret; |
e7c274f80 nilfs2: get rid o... |
1694 |
nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n, |
3033342a0 nilfs2: remove us... |
1695 |
di, ni, bh); |
be667377a nilfs2: record us... |
1696 |
nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks); |
17c76b010 nilfs2: B-tree ba... |
1697 1698 |
return 0; } |
e7c274f80 nilfs2: get rid o... |
1699 |
static int nilfs_btree_propagate_p(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: use mark_... |
1706 |
mark_buffer_dirty(path[level].bp_bh); |
17c76b010 nilfs2: B-tree ba... |
1707 1708 1709 |
return 0; } |
e7c274f80 nilfs2: get rid o... |
1710 |
static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1711 |
struct nilfs_btree_path *path, |
2e0c2c739 nilfs2: allow btr... |
1712 |
int level, struct inode *dat) |
17c76b010 nilfs2: B-tree ba... |
1713 1714 |
{ struct nilfs_btree_node *parent; |
9b7b265c9 nilfs2: reduce re... |
1715 |
int ncmax, ret; |
17c76b010 nilfs2: B-tree ba... |
1716 |
|
9b7b265c9 nilfs2: reduce re... |
1717 |
parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); |
17c76b010 nilfs2: B-tree ba... |
1718 |
path[level].bp_oldreq.bpr_ptr = |
9b7b265c9 nilfs2: reduce re... |
1719 1720 |
nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, ncmax); |
17c76b010 nilfs2: B-tree ba... |
1721 |
path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; |
2e0c2c739 nilfs2: allow btr... |
1722 1723 |
ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req); |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1732 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010 nilfs2: B-tree ba... |
1733 1734 |
&path[level].bp_ctxt); if (ret < 0) { |
2e0c2c739 nilfs2: allow btr... |
1735 1736 1737 |
nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req); |
17c76b010 nilfs2: B-tree ba... |
1738 1739 1740 1741 1742 1743 |
return ret; } } return 0; } |
e7c274f80 nilfs2: get rid o... |
1744 |
static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1745 |
struct nilfs_btree_path *path, |
2e0c2c739 nilfs2: allow btr... |
1746 |
int level, struct inode *dat) |
17c76b010 nilfs2: B-tree ba... |
1747 1748 |
{ struct nilfs_btree_node *parent; |
9b7b265c9 nilfs2: reduce re... |
1749 |
int ncmax; |
17c76b010 nilfs2: B-tree ba... |
1750 |
|
2e0c2c739 nilfs2: allow btr... |
1751 1752 |
nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req, |
e7c274f80 nilfs2: get rid o... |
1753 |
btree->b_ptr_type == NILFS_BMAP_PTR_VS); |
17c76b010 nilfs2: B-tree ba... |
1754 1755 1756 |
if (buffer_nilfs_node(path[level].bp_bh)) { nilfs_btnode_commit_change_key( |
e7c274f80 nilfs2: get rid o... |
1757 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: reduce re... |
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 nilfs2: B-tree ba... |
1765 |
} |
e7c274f80 nilfs2: get rid o... |
1766 |
static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1767 |
struct nilfs_btree_path *path, |
2e0c2c739 nilfs2: allow btr... |
1768 |
int level, struct inode *dat) |
17c76b010 nilfs2: B-tree ba... |
1769 |
{ |
2e0c2c739 nilfs2: allow btr... |
1770 1771 |
nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, &path[level].bp_newreq.bpr_req); |
17c76b010 nilfs2: B-tree ba... |
1772 1773 |
if (buffer_nilfs_node(path[level].bp_bh)) nilfs_btnode_abort_change_key( |
e7c274f80 nilfs2: get rid o... |
1774 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010 nilfs2: B-tree ba... |
1775 1776 |
&path[level].bp_ctxt); } |
e7c274f80 nilfs2: get rid o... |
1777 |
static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1778 |
struct nilfs_btree_path *path, |
2e0c2c739 nilfs2: allow btr... |
1779 1780 |
int minlevel, int *maxlevelp, struct inode *dat) |
17c76b010 nilfs2: B-tree ba... |
1781 1782 1783 1784 1785 |
{ int level, ret; level = minlevel; if (!buffer_nilfs_volatile(path[level].bp_bh)) { |
2e0c2c739 nilfs2: allow btr... |
1786 |
ret = nilfs_btree_prepare_update_v(btree, path, level, dat); |
17c76b010 nilfs2: B-tree ba... |
1787 1788 1789 1790 1791 |
if (ret < 0) return ret; } while ((++level < nilfs_btree_height(btree) - 1) && !buffer_dirty(path[level].bp_bh)) { |
1f5abe7e7 nilfs2: replace B... |
1792 |
WARN_ON(buffer_nilfs_volatile(path[level].bp_bh)); |
2e0c2c739 nilfs2: allow btr... |
1793 |
ret = nilfs_btree_prepare_update_v(btree, path, level, dat); |
17c76b010 nilfs2: B-tree ba... |
1794 1795 1796 1797 1798 |
if (ret < 0) goto out; } /* success */ |
17c76b010 nilfs2: B-tree ba... |
1799 1800 1801 1802 1803 1804 |
*maxlevelp = level - 1; return 0; /* error */ out: while (--level > minlevel) |
2e0c2c739 nilfs2: allow btr... |
1805 |
nilfs_btree_abort_update_v(btree, path, level, dat); |
17c76b010 nilfs2: B-tree ba... |
1806 |
if (!buffer_nilfs_volatile(path[level].bp_bh)) |
2e0c2c739 nilfs2: allow btr... |
1807 |
nilfs_btree_abort_update_v(btree, path, level, dat); |
17c76b010 nilfs2: B-tree ba... |
1808 1809 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
1810 |
static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1811 |
struct nilfs_btree_path *path, |
2e0c2c739 nilfs2: allow btr... |
1812 1813 1814 |
int minlevel, int maxlevel, struct buffer_head *bh, struct inode *dat) |
17c76b010 nilfs2: B-tree ba... |
1815 1816 1817 1818 |
{ int level; if (!buffer_nilfs_volatile(path[minlevel].bp_bh)) |
2e0c2c739 nilfs2: allow btr... |
1819 |
nilfs_btree_commit_update_v(btree, path, minlevel, dat); |
17c76b010 nilfs2: B-tree ba... |
1820 1821 |
for (level = minlevel + 1; level <= maxlevel; level++) |
2e0c2c739 nilfs2: allow btr... |
1822 |
nilfs_btree_commit_update_v(btree, path, level, dat); |
17c76b010 nilfs2: B-tree ba... |
1823 |
} |
e7c274f80 nilfs2: get rid o... |
1824 |
static int nilfs_btree_propagate_v(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1825 |
struct nilfs_btree_path *path, |
2e0c2c739 nilfs2: allow btr... |
1826 |
int level, struct buffer_head *bh) |
17c76b010 nilfs2: B-tree ba... |
1827 |
{ |
308f44193 nilfs2: Remove an... |
1828 |
int maxlevel = 0, ret; |
17c76b010 nilfs2: B-tree ba... |
1829 |
struct nilfs_btree_node *parent; |
e7c274f80 nilfs2: get rid o... |
1830 |
struct inode *dat = nilfs_bmap_get_dat(btree); |
17c76b010 nilfs2: B-tree ba... |
1831 |
__u64 ptr; |
9b7b265c9 nilfs2: reduce re... |
1832 |
int ncmax; |
17c76b010 nilfs2: B-tree ba... |
1833 1834 1835 |
get_bh(bh); path[level].bp_bh = bh; |
2e0c2c739 nilfs2: allow btr... |
1836 1837 |
ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel, dat); |
17c76b010 nilfs2: B-tree ba... |
1838 1839 1840 1841 |
if (ret < 0) goto out; if (buffer_nilfs_volatile(path[level].bp_bh)) { |
9b7b265c9 nilfs2: reduce re... |
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 nilfs2: allow btr... |
1846 |
ret = nilfs_dat_mark_dirty(dat, ptr); |
17c76b010 nilfs2: B-tree ba... |
1847 1848 1849 |
if (ret < 0) goto out; } |
2e0c2c739 nilfs2: allow btr... |
1850 |
nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat); |
17c76b010 nilfs2: B-tree ba... |
1851 1852 1853 1854 1855 1856 |
out: brelse(path[level].bp_bh); path[level].bp_bh = NULL; return ret; } |
e7c274f80 nilfs2: get rid o... |
1857 |
static int nilfs_btree_propagate(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1858 1859 |
struct buffer_head *bh) { |
17c76b010 nilfs2: B-tree ba... |
1860 1861 1862 1863 |
struct nilfs_btree_path *path; struct nilfs_btree_node *node; __u64 key; int level, ret; |
1f5abe7e7 nilfs2: replace B... |
1864 |
WARN_ON(!buffer_dirty(bh)); |
17c76b010 nilfs2: B-tree ba... |
1865 |
|
6d28f7ea4 nilfs2: remove un... |
1866 |
path = nilfs_btree_alloc_path(); |
17c76b010 nilfs2: B-tree ba... |
1867 1868 |
if (path == NULL) return -ENOMEM; |
17c76b010 nilfs2: B-tree ba... |
1869 1870 1871 |
if (buffer_nilfs_node(bh)) { node = (struct nilfs_btree_node *)bh->b_data; |
6d28f7ea4 nilfs2: remove un... |
1872 1873 |
key = nilfs_btree_node_get_key(node, 0); level = nilfs_btree_node_get_level(node); |
17c76b010 nilfs2: B-tree ba... |
1874 |
} else { |
e7c274f80 nilfs2: get rid o... |
1875 |
key = nilfs_bmap_data_get_key(btree, bh); |
17c76b010 nilfs2: B-tree ba... |
1876 1877 |
level = NILFS_BTREE_LEVEL_DATA; } |
03bdb5ac5 nilfs2: apply rea... |
1878 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); |
17c76b010 nilfs2: B-tree ba... |
1879 |
if (ret < 0) { |
1f5abe7e7 nilfs2: replace B... |
1880 |
if (unlikely(ret == -ENOENT)) |
17c76b010 nilfs2: B-tree ba... |
1881 1882 1883 |
printk(KERN_CRIT "%s: key = %llu, level == %d ", __func__, (unsigned long long)key, level); |
17c76b010 nilfs2: B-tree ba... |
1884 1885 |
goto out; } |
e7c274f80 nilfs2: get rid o... |
1886 |
ret = NILFS_BMAP_USE_VBN(btree) ? |
7cde31d7d nilfs2: remove ni... |
1887 1888 |
nilfs_btree_propagate_v(btree, path, level, bh) : nilfs_btree_propagate_p(btree, path, level, bh); |
17c76b010 nilfs2: B-tree ba... |
1889 1890 |
out: |
6d28f7ea4 nilfs2: remove un... |
1891 |
nilfs_btree_free_path(path); |
17c76b010 nilfs2: B-tree ba... |
1892 1893 1894 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
1895 |
static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1896 1897 |
struct buffer_head *bh) { |
e7c274f80 nilfs2: get rid o... |
1898 |
return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr); |
17c76b010 nilfs2: B-tree ba... |
1899 |
} |
e7c274f80 nilfs2: get rid o... |
1900 |
static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
1912 1913 |
key = nilfs_btree_node_get_key(node, 0); level = nilfs_btree_node_get_level(node); |
cfa913a50 nilfs2: add sanit... |
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 nilfs2: get rid o... |
1922 |
NILFS_BMAP_I(btree)->vfs_inode.i_ino, |
cfa913a50 nilfs2: add sanit... |
1923 1924 1925 |
(unsigned long long)bh->b_blocknr); return; } |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove un... |
1929 |
ckey = nilfs_btree_node_get_key(cnode, 0); |
17c76b010 nilfs2: B-tree ba... |
1930 1931 1932 1933 1934 |
if (key < ckey) break; } list_add_tail(&bh->b_assoc_buffers, head); } |
e7c274f80 nilfs2: get rid o... |
1935 |
static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
1936 1937 |
struct list_head *listp) { |
e7c274f80 nilfs2: get rid o... |
1938 |
struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache; |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: use list_... |
1969 |
list_splice_tail(&lists[level], listp); |
17c76b010 nilfs2: B-tree ba... |
1970 |
} |
e7c274f80 nilfs2: get rid o... |
1971 |
static int nilfs_btree_assign_p(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: reduce re... |
1981 |
int ncmax, ret; |
17c76b010 nilfs2: B-tree ba... |
1982 |
|
9b7b265c9 nilfs2: reduce re... |
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 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
1991 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010 nilfs2: B-tree ba... |
1992 1993 1994 1995 |
&path[level].bp_ctxt); if (ret < 0) return ret; nilfs_btnode_commit_change_key( |
e7c274f80 nilfs2: get rid o... |
1996 |
&NILFS_BMAP_I(btree)->i_btnode_cache, |
17c76b010 nilfs2: B-tree ba... |
1997 1998 1999 |
&path[level].bp_ctxt); *bh = path[level].bp_ctxt.bh; } |
9b7b265c9 nilfs2: reduce re... |
2000 2001 |
nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr, ncmax); |
17c76b010 nilfs2: B-tree ba... |
2002 |
|
6d28f7ea4 nilfs2: remove un... |
2003 |
key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); |
17c76b010 nilfs2: B-tree ba... |
2004 |
/* on-disk format */ |
25b8d7ded nilfs2: get rid o... |
2005 |
binfo->bi_dat.bi_blkoff = cpu_to_le64(key); |
17c76b010 nilfs2: B-tree ba... |
2006 2007 2008 2009 |
binfo->bi_dat.bi_level = level; return 0; } |
e7c274f80 nilfs2: get rid o... |
2010 |
static int nilfs_btree_assign_v(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: get rid o... |
2018 |
struct inode *dat = nilfs_bmap_get_dat(btree); |
17c76b010 nilfs2: B-tree ba... |
2019 2020 2021 |
__u64 key; __u64 ptr; union nilfs_bmap_ptr_req req; |
9b7b265c9 nilfs2: reduce re... |
2022 |
int ncmax, ret; |
17c76b010 nilfs2: B-tree ba... |
2023 |
|
9b7b265c9 nilfs2: reduce re... |
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 nilfs2: B-tree ba... |
2027 |
req.bpr_ptr = ptr; |
2e0c2c739 nilfs2: allow btr... |
2028 2029 |
ret = nilfs_dat_prepare_start(dat, &req.bpr_req); if (ret < 0) |
17c76b010 nilfs2: B-tree ba... |
2030 |
return ret; |
2e0c2c739 nilfs2: allow btr... |
2031 |
nilfs_dat_commit_start(dat, &req.bpr_req, blocknr); |
17c76b010 nilfs2: B-tree ba... |
2032 |
|
6d28f7ea4 nilfs2: remove un... |
2033 |
key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); |
17c76b010 nilfs2: B-tree ba... |
2034 |
/* on-disk format */ |
25b8d7ded nilfs2: get rid o... |
2035 2036 |
binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr); binfo->bi_v.bi_blkoff = cpu_to_le64(key); |
17c76b010 nilfs2: B-tree ba... |
2037 2038 2039 |
return 0; } |
e7c274f80 nilfs2: get rid o... |
2040 |
static int nilfs_btree_assign(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
2041 2042 2043 2044 |
struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) { |
17c76b010 nilfs2: B-tree ba... |
2045 2046 2047 2048 |
struct nilfs_btree_path *path; struct nilfs_btree_node *node; __u64 key; int level, ret; |
6d28f7ea4 nilfs2: remove un... |
2049 |
path = nilfs_btree_alloc_path(); |
17c76b010 nilfs2: B-tree ba... |
2050 2051 |
if (path == NULL) return -ENOMEM; |
17c76b010 nilfs2: B-tree ba... |
2052 2053 2054 |
if (buffer_nilfs_node(*bh)) { node = (struct nilfs_btree_node *)(*bh)->b_data; |
6d28f7ea4 nilfs2: remove un... |
2055 2056 |
key = nilfs_btree_node_get_key(node, 0); level = nilfs_btree_node_get_level(node); |
17c76b010 nilfs2: B-tree ba... |
2057 |
} else { |
e7c274f80 nilfs2: get rid o... |
2058 |
key = nilfs_bmap_data_get_key(btree, *bh); |
17c76b010 nilfs2: B-tree ba... |
2059 2060 |
level = NILFS_BTREE_LEVEL_DATA; } |
03bdb5ac5 nilfs2: apply rea... |
2061 |
ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); |
17c76b010 nilfs2: B-tree ba... |
2062 |
if (ret < 0) { |
1f5abe7e7 nilfs2: replace B... |
2063 |
WARN_ON(ret == -ENOENT); |
17c76b010 nilfs2: B-tree ba... |
2064 2065 |
goto out; } |
e7c274f80 nilfs2: get rid o... |
2066 |
ret = NILFS_BMAP_USE_VBN(btree) ? |
7cde31d7d nilfs2: remove ni... |
2067 2068 |
nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); |
17c76b010 nilfs2: B-tree ba... |
2069 2070 |
out: |
6d28f7ea4 nilfs2: remove un... |
2071 |
nilfs_btree_free_path(path); |
17c76b010 nilfs2: B-tree ba... |
2072 2073 2074 |
return ret; } |
e7c274f80 nilfs2: get rid o... |
2075 |
static int nilfs_btree_assign_gc(struct nilfs_bmap *btree, |
17c76b010 nilfs2: B-tree ba... |
2076 2077 2078 2079 |
struct buffer_head **bh, sector_t blocknr, union nilfs_binfo *binfo) { |
17c76b010 nilfs2: B-tree ba... |
2080 2081 2082 |
struct nilfs_btree_node *node; __u64 key; int ret; |
e7c274f80 nilfs2: get rid o... |
2083 |
ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr, |
2e0c2c739 nilfs2: allow btr... |
2084 |
blocknr); |
17c76b010 nilfs2: B-tree ba... |
2085 2086 2087 2088 2089 |
if (ret < 0) return ret; if (buffer_nilfs_node(*bh)) { node = (struct nilfs_btree_node *)(*bh)->b_data; |
6d28f7ea4 nilfs2: remove un... |
2090 |
key = nilfs_btree_node_get_key(node, 0); |
17c76b010 nilfs2: B-tree ba... |
2091 |
} else |
e7c274f80 nilfs2: get rid o... |
2092 |
key = nilfs_bmap_data_get_key(btree, *bh); |
17c76b010 nilfs2: B-tree ba... |
2093 2094 2095 |
/* on-disk format */ binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr); |
25b8d7ded nilfs2: get rid o... |
2096 |
binfo->bi_v.bi_blkoff = cpu_to_le64(key); |
17c76b010 nilfs2: B-tree ba... |
2097 2098 2099 |
return 0; } |
e7c274f80 nilfs2: get rid o... |
2100 |
static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) |
17c76b010 nilfs2: B-tree ba... |
2101 2102 |
{ struct buffer_head *bh; |
17c76b010 nilfs2: B-tree ba... |
2103 2104 2105 |
struct nilfs_btree_path *path; __u64 ptr; int ret; |
6d28f7ea4 nilfs2: remove un... |
2106 |
path = nilfs_btree_alloc_path(); |
17c76b010 nilfs2: B-tree ba... |
2107 2108 |
if (path == NULL) return -ENOMEM; |
17c76b010 nilfs2: B-tree ba... |
2109 |
|
03bdb5ac5 nilfs2: apply rea... |
2110 |
ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0); |
17c76b010 nilfs2: B-tree ba... |
2111 |
if (ret < 0) { |
1f5abe7e7 nilfs2: replace B... |
2112 |
WARN_ON(ret == -ENOENT); |
17c76b010 nilfs2: B-tree ba... |
2113 2114 |
goto out; } |
f198dbb9c nilfs2: move get ... |
2115 |
ret = nilfs_btree_get_block(btree, ptr, &bh); |
17c76b010 nilfs2: B-tree ba... |
2116 |
if (ret < 0) { |
1f5abe7e7 nilfs2: replace B... |
2117 |
WARN_ON(ret == -ENOENT); |
17c76b010 nilfs2: B-tree ba... |
2118 2119 2120 2121 |
goto out; } if (!buffer_dirty(bh)) |
5fc7b1417 nilfs2: use mark_... |
2122 |
mark_buffer_dirty(bh); |
087d01b42 nilfs2: remove ni... |
2123 |
brelse(bh); |
e7c274f80 nilfs2: get rid o... |
2124 2125 |
if (!nilfs_bmap_dirty(btree)) nilfs_bmap_set_dirty(btree); |
17c76b010 nilfs2: B-tree ba... |
2126 2127 |
out: |
6d28f7ea4 nilfs2: remove un... |
2128 |
nilfs_btree_free_path(path); |
17c76b010 nilfs2: B-tree ba... |
2129 2130 2131 2132 2133 |
return ret; } static const struct nilfs_bmap_operations nilfs_btree_ops = { .bop_lookup = nilfs_btree_lookup, |
c3a7abf06 nilfs2: support c... |
2134 |
.bop_lookup_contig = nilfs_btree_lookup_contig, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: support c... |
2154 |
.bop_lookup_contig = NULL, |
17c76b010 nilfs2: B-tree ba... |
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 nilfs2: remove us... |
2171 |
int nilfs_btree_init(struct nilfs_bmap *bmap) |
17c76b010 nilfs2: B-tree ba... |
2172 |
{ |
17c76b010 nilfs2: B-tree ba... |
2173 |
bmap->b_ops = &nilfs_btree_ops; |
5ad2686e9 nilfs2: get maxim... |
2174 2175 |
bmap->b_nchildren_per_block = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap)); |
17c76b010 nilfs2: B-tree ba... |
2176 2177 2178 2179 2180 |
return 0; } void nilfs_btree_init_gc(struct nilfs_bmap *bmap) { |
17c76b010 nilfs2: B-tree ba... |
2181 |
bmap->b_ops = &nilfs_btree_ops_gc; |
5ad2686e9 nilfs2: get maxim... |
2182 2183 |
bmap->b_nchildren_per_block = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap)); |
17c76b010 nilfs2: B-tree ba... |
2184 |
} |