Lines Matching defs:btree
2 * btree.c - NILFS B-tree.
30 #include "btree.h"
69 static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
72 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
122 static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
124 return 1 << btree->b_inode->i_blkbits;
127 static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
129 return btree->b_nchildren_per_block;
341 * nilfs_btree_node_broken - verify consistency of btree node
342 * @node: btree node block to be examined
363 printk(KERN_CRIT "NILFS: bad btree node (blocknr=%llu): "
386 nilfs_btree_get_root(const struct nilfs_bmap *btree)
388 return (struct nilfs_btree_node *)btree->b_u.u_data;
403 static int nilfs_btree_height(const struct nilfs_bmap *btree)
405 return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
409 nilfs_btree_get_node(const struct nilfs_bmap *btree,
415 if (level == nilfs_btree_height(btree) - 1) {
416 node = nilfs_btree_get_root(btree);
420 *ncmaxp = nilfs_btree_nchildren_per_block(btree);
430 printk(KERN_CRIT "NILFS: btree level mismatch: %d != %d\n",
444 static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
448 struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
499 static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
502 return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
505 static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
515 node = nilfs_btree_get_root(btree);
526 ncmax = nilfs_btree_nchildren_per_block(btree);
531 p.node = nilfs_btree_get_node(btree, path, level + 1,
537 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
567 static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
575 node = nilfs_btree_get_root(btree);
584 ncmax = nilfs_btree_nchildren_per_block(btree);
587 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
606 static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
616 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
623 static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
639 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
643 if (NILFS_BMAP_USE_VBN(btree)) {
644 dat = nilfs_bmap_get_dat(btree);
654 maxlevel = nilfs_btree_height(btree) - 1;
655 node = nilfs_btree_get_node(btree, path, level, &ncmax);
678 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
690 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
695 ncmax = nilfs_btree_nchildren_per_block(btree);
707 static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
711 if (level < nilfs_btree_height(btree) - 1) {
719 (++level < nilfs_btree_height(btree) - 1));
723 if (level == nilfs_btree_height(btree) - 1) {
724 nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
729 static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
736 if (level < nilfs_btree_height(btree) - 1) {
738 ncblk = nilfs_btree_nchildren_per_block(btree);
745 nilfs_btree_promote_key(btree, path, level + 1,
749 node = nilfs_btree_get_root(btree);
756 static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
767 ncblk = nilfs_btree_nchildren_per_block(btree);
784 nilfs_btree_promote_key(btree, path, level + 1,
799 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
802 static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
813 ncblk = nilfs_btree_nchildren_per_block(btree);
831 nilfs_btree_promote_key(btree, path, level + 1,
846 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
849 static void nilfs_btree_split(struct nilfs_bmap *btree,
861 ncblk = nilfs_btree_nchildren_per_block(btree);
892 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
904 static void nilfs_btree_grow(struct nilfs_bmap *btree,
911 root = nilfs_btree_get_root(btree);
913 ncblk = nilfs_btree_nchildren_per_block(btree);
927 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
933 static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
945 node = nilfs_btree_get_node(btree, path, level, &ncmax);
953 if (level <= nilfs_btree_height(btree) - 1) {
954 node = nilfs_btree_get_node(btree, path, level, &ncmax);
962 static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
968 ptr = nilfs_bmap_find_target_seq(btree, key);
973 ptr = nilfs_btree_find_near(btree, path);
979 return nilfs_bmap_find_target_in_group(btree);
982 static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
997 if (NILFS_BMAP_USE_VBN(btree)) {
999 nilfs_btree_find_target_v(btree, path, key);
1000 dat = nilfs_bmap_get_dat(btree);
1003 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1007 ncblk = nilfs_btree_nchildren_per_block(btree);
1010 level < nilfs_btree_height(btree) - 1;
1019 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1026 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1044 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1061 ret = nilfs_bmap_prepare_alloc_ptr(btree,
1065 ret = nilfs_btree_get_new_block(btree,
1080 node = nilfs_btree_get_root(btree);
1090 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1093 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1116 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1120 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1124 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1131 static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
1140 if (NILFS_BMAP_USE_VBN(btree)) {
1141 nilfs_bmap_set_target_v(btree, key, ptr);
1142 dat = nilfs_bmap_get_dat(btree);
1146 nilfs_bmap_commit_alloc_ptr(btree,
1148 path[level].bp_op(btree, path, level, &key, &ptr);
1151 if (!nilfs_bmap_dirty(btree))
1152 nilfs_bmap_set_dirty(btree);
1155 static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
1165 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1173 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1176 nilfs_btree_commit_insert(btree, path, level, key, ptr);
1177 nilfs_bmap_add_blocks(btree, stats.bs_nblocks);
1184 static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
1191 if (level < nilfs_btree_height(btree) - 1) {
1193 ncblk = nilfs_btree_nchildren_per_block(btree);
1199 nilfs_btree_promote_key(btree, path, level + 1,
1202 node = nilfs_btree_get_root(btree);
1209 static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
1216 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1222 ncblk = nilfs_btree_nchildren_per_block(btree);
1233 nilfs_btree_promote_key(btree, path, level + 1,
1241 static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
1248 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1254 ncblk = nilfs_btree_nchildren_per_block(btree);
1266 nilfs_btree_promote_key(btree, path, level + 1,
1274 static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
1281 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1285 ncblk = nilfs_btree_nchildren_per_block(btree);
1300 static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
1307 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1311 ncblk = nilfs_btree_nchildren_per_block(btree);
1325 static void nilfs_btree_shrink(struct nilfs_bmap *btree,
1332 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1334 root = nilfs_btree_get_root(btree);
1336 ncblk = nilfs_btree_nchildren_per_block(btree);
1350 static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1363 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1364 ncblk = nilfs_btree_nchildren_per_block(btree);
1367 level < nilfs_btree_height(btree) - 1;
1373 ret = nilfs_bmap_prepare_end_ptr(btree,
1384 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1391 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1411 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1429 WARN_ON(level != nilfs_btree_height(btree) - 2);
1444 node = nilfs_btree_get_root(btree);
1449 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1464 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1468 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1475 static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
1482 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1483 path[level].bp_op(btree, path, level, NULL, NULL);
1486 if (!nilfs_bmap_dirty(btree))
1487 nilfs_bmap_set_dirty(btree);
1490 static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
1502 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1508 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1510 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1513 nilfs_btree_commit_delete(btree, path, level, dat);
1514 nilfs_bmap_sub_blocks(btree, stats.bs_nblocks);
1521 static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
1530 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1537 static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
1545 root = nilfs_btree_get_root(btree);
1546 switch (nilfs_btree_height(btree)) {
1557 ret = nilfs_btree_get_block(btree, ptr, &bh);
1576 static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
1586 root = nilfs_btree_get_root(btree);
1587 switch (nilfs_btree_height(btree)) {
1598 ret = nilfs_btree_get_block(btree, ptr, &bh);
1602 ncmax = nilfs_btree_nchildren_per_block(btree);
1626 nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
1640 if (NILFS_BMAP_USE_VBN(btree)) {
1641 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
1642 dat = nilfs_bmap_get_dat(btree);
1645 ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
1653 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
1657 ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
1670 nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
1672 nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
1679 nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
1693 if (btree->b_ops->bop_clear != NULL)
1694 btree->b_ops->bop_clear(btree);
1700 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1701 nilfs_btree_init(btree);
1703 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1704 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
1708 ncblk = nilfs_btree_nchildren_per_block(btree);
1713 if (!nilfs_bmap_dirty(btree))
1714 nilfs_bmap_set_dirty(btree);
1719 node = nilfs_btree_get_root(btree);
1725 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1728 node = nilfs_btree_get_root(btree);
1734 if (!nilfs_bmap_dirty(btree))
1735 nilfs_bmap_set_dirty(btree);
1738 if (NILFS_BMAP_USE_VBN(btree))
1739 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
1751 int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
1764 1 << btree->b_inode->i_blkbits)) {
1773 ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
1777 nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
1779 nilfs_bmap_add_blocks(btree, stats.bs_nblocks);
1783 static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
1788 while ((++level < nilfs_btree_height(btree) - 1) &&
1795 static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
1802 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1817 &NILFS_BMAP_I(btree)->i_btnode_cache,
1830 static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
1839 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
1843 &NILFS_BMAP_I(btree)->i_btnode_cache,
1849 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1854 static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
1862 &NILFS_BMAP_I(btree)->i_btnode_cache,
1866 static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
1875 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1879 while ((++level < nilfs_btree_height(btree) - 1) &&
1883 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1895 nilfs_btree_abort_update_v(btree, path, level, dat);
1897 nilfs_btree_abort_update_v(btree, path, level, dat);
1901 static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
1910 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
1913 nilfs_btree_commit_update_v(btree, path, level, dat);
1916 static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
1922 struct inode *dat = nilfs_bmap_get_dat(btree);
1928 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
1934 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1943 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
1951 static int nilfs_btree_propagate(struct nilfs_bmap *btree,
1970 key = nilfs_bmap_data_get_key(btree, bh);
1974 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
1982 ret = NILFS_BMAP_USE_VBN(btree) ?
1983 nilfs_btree_propagate_v(btree, path, level, bh) :
1984 nilfs_btree_propagate_p(btree, path, level, bh);
1992 static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
1995 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
1998 static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
2016 "%s: invalid btree level: %d (key=%llu, ino=%lu, "
2019 NILFS_BMAP_I(btree)->vfs_inode.i_ino,
2034 static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
2037 struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache;
2057 nilfs_btree_add_dirty_buffer(btree,
2071 static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
2083 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2091 &NILFS_BMAP_I(btree)->i_btnode_cache,
2096 &NILFS_BMAP_I(btree)->i_btnode_cache,
2112 static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
2120 struct inode *dat = nilfs_bmap_get_dat(btree);
2126 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2143 static int nilfs_btree_assign(struct nilfs_bmap *btree,
2162 key = nilfs_bmap_data_get_key(btree, *bh);
2166 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2172 ret = NILFS_BMAP_USE_VBN(btree) ?
2173 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2174 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2182 static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
2191 ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
2200 key = nilfs_bmap_data_get_key(btree, *bh);
2209 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
2220 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2225 ret = nilfs_btree_get_block(btree, ptr, &bh);
2234 if (!nilfs_bmap_dirty(btree))
2235 nilfs_bmap_set_dirty(btree);