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