Lines Matching defs:btree
17 #include "btree.h"
58 static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
61 struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
112 static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
114 return i_blocksize(btree->b_inode);
117 static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
119 return btree->b_nchildren_per_block;
331 * nilfs_btree_node_broken - verify consistency of btree node
332 * @node: btree node block to be examined
334 * @inode: host inode of btree
356 "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d",
365 * nilfs_btree_root_broken - verify consistency of btree root node
366 * @node: btree root node to be examined
367 * @inode: host inode of btree
386 "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d",
410 nilfs_btree_get_root(const struct nilfs_bmap *btree)
412 return (struct nilfs_btree_node *)btree->b_u.u_data;
427 static int nilfs_btree_height(const struct nilfs_bmap *btree)
429 return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
433 nilfs_btree_get_node(const struct nilfs_bmap *btree,
439 if (level == nilfs_btree_height(btree) - 1) {
440 node = nilfs_btree_get_root(btree);
444 *ncmaxp = nilfs_btree_nchildren_per_block(btree);
449 static int nilfs_btree_bad_node(const struct nilfs_bmap *btree,
454 nilfs_crit(btree->b_inode->i_sb,
455 "btree level mismatch (ino=%lu): %d != %d",
456 btree->b_inode->i_ino,
470 static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
474 struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
522 nilfs_err(btree->b_inode->i_sb,
524 btree->b_inode->i_ino, (unsigned long long)ptr);
540 static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
543 return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
546 static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
556 node = nilfs_btree_get_root(btree);
567 ncmax = nilfs_btree_nchildren_per_block(btree);
572 p.node = nilfs_btree_get_node(btree, path, level + 1,
578 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
584 if (nilfs_btree_bad_node(btree, node, level))
608 static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
616 node = nilfs_btree_get_root(btree);
625 ncmax = nilfs_btree_nchildren_per_block(btree);
628 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
632 if (nilfs_btree_bad_node(btree, node, level))
648 * nilfs_btree_get_next_key - get next valid key from btree path array
649 * @btree: bmap struct of btree
657 static int nilfs_btree_get_next_key(const struct nilfs_bmap *btree,
662 int maxlevel = nilfs_btree_height(btree) - 1;
669 node = nilfs_btree_get_root(btree);
685 static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
695 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
702 static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
719 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
723 if (NILFS_BMAP_USE_VBN(btree)) {
724 dat = nilfs_bmap_get_dat(btree);
734 maxlevel = nilfs_btree_height(btree) - 1;
735 node = nilfs_btree_get_node(btree, path, level, &ncmax);
757 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
769 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
774 ncmax = nilfs_btree_nchildren_per_block(btree);
791 static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
795 if (level < nilfs_btree_height(btree) - 1) {
803 (++level < nilfs_btree_height(btree) - 1));
807 if (level == nilfs_btree_height(btree) - 1) {
808 nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
813 static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
820 if (level < nilfs_btree_height(btree) - 1) {
822 ncblk = nilfs_btree_nchildren_per_block(btree);
829 nilfs_btree_promote_key(btree, path, level + 1,
833 node = nilfs_btree_get_root(btree);
840 static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
851 ncblk = nilfs_btree_nchildren_per_block(btree);
868 nilfs_btree_promote_key(btree, path, level + 1,
883 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
886 static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
897 ncblk = nilfs_btree_nchildren_per_block(btree);
915 nilfs_btree_promote_key(btree, path, level + 1,
930 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
933 static void nilfs_btree_split(struct nilfs_bmap *btree,
943 ncblk = nilfs_btree_nchildren_per_block(btree);
971 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
983 static void nilfs_btree_grow(struct nilfs_bmap *btree,
990 root = nilfs_btree_get_root(btree);
992 ncblk = nilfs_btree_nchildren_per_block(btree);
1006 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
1012 static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
1024 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1032 if (level <= nilfs_btree_height(btree) - 1) {
1033 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1041 static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
1047 ptr = nilfs_bmap_find_target_seq(btree, key);
1052 ptr = nilfs_btree_find_near(btree, path);
1058 return nilfs_bmap_find_target_in_group(btree);
1061 static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
1076 if (NILFS_BMAP_USE_VBN(btree)) {
1078 nilfs_btree_find_target_v(btree, path, key);
1079 dat = nilfs_bmap_get_dat(btree);
1082 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1086 ncblk = nilfs_btree_nchildren_per_block(btree);
1089 level < nilfs_btree_height(btree) - 1;
1098 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1105 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1123 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1140 ret = nilfs_bmap_prepare_alloc_ptr(btree,
1144 ret = nilfs_btree_get_new_block(btree,
1159 node = nilfs_btree_get_root(btree);
1169 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1172 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1195 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1199 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1203 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1210 static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
1219 if (NILFS_BMAP_USE_VBN(btree)) {
1220 nilfs_bmap_set_target_v(btree, key, ptr);
1221 dat = nilfs_bmap_get_dat(btree);
1225 nilfs_bmap_commit_alloc_ptr(btree,
1227 path[level].bp_op(btree, path, level, &key, &ptr);
1230 if (!nilfs_bmap_dirty(btree))
1231 nilfs_bmap_set_dirty(btree);
1234 static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
1244 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1252 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1255 nilfs_btree_commit_insert(btree, path, level, key, ptr);
1256 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1263 static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
1270 if (level < nilfs_btree_height(btree) - 1) {
1272 ncblk = nilfs_btree_nchildren_per_block(btree);
1278 nilfs_btree_promote_key(btree, path, level + 1,
1281 node = nilfs_btree_get_root(btree);
1288 static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
1295 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1301 ncblk = nilfs_btree_nchildren_per_block(btree);
1312 nilfs_btree_promote_key(btree, path, level + 1,
1320 static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
1327 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1333 ncblk = nilfs_btree_nchildren_per_block(btree);
1345 nilfs_btree_promote_key(btree, path, level + 1,
1353 static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
1360 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1364 ncblk = nilfs_btree_nchildren_per_block(btree);
1379 static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
1386 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1390 ncblk = nilfs_btree_nchildren_per_block(btree);
1404 static void nilfs_btree_shrink(struct nilfs_bmap *btree,
1411 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1413 root = nilfs_btree_get_root(btree);
1415 ncblk = nilfs_btree_nchildren_per_block(btree);
1428 static void nilfs_btree_nop(struct nilfs_bmap *btree,
1434 static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1447 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1448 ncblk = nilfs_btree_nchildren_per_block(btree);
1451 level < nilfs_btree_height(btree) - 1;
1456 ret = nilfs_bmap_prepare_end_ptr(btree,
1467 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1475 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1495 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1521 WARN_ON(level != nilfs_btree_height(btree) - 2);
1542 node = nilfs_btree_get_root(btree);
1547 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1558 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1562 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1569 static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
1576 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1577 path[level].bp_op(btree, path, level, NULL, NULL);
1580 if (!nilfs_bmap_dirty(btree))
1581 nilfs_bmap_set_dirty(btree);
1584 static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
1596 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1602 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1604 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1607 nilfs_btree_commit_delete(btree, path, level, dat);
1608 nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);
1615 static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
1626 ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
1630 ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
1636 static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
1645 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1652 static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
1660 root = nilfs_btree_get_root(btree);
1661 switch (nilfs_btree_height(btree)) {
1672 ret = nilfs_btree_get_block(btree, ptr, &bh);
1690 static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
1700 root = nilfs_btree_get_root(btree);
1701 switch (nilfs_btree_height(btree)) {
1712 ret = nilfs_btree_get_block(btree, ptr, &bh);
1716 ncmax = nilfs_btree_nchildren_per_block(btree);
1739 nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
1753 if (NILFS_BMAP_USE_VBN(btree)) {
1754 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
1755 dat = nilfs_bmap_get_dat(btree);
1758 ret = nilfs_attach_btree_node_cache(&NILFS_BMAP_I(btree)->vfs_inode);
1762 ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
1770 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
1774 ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
1787 nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
1789 nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
1796 nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
1810 if (btree->b_ops->bop_clear != NULL)
1811 btree->b_ops->bop_clear(btree);
1817 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1818 __nilfs_btree_init(btree);
1820 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1821 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
1825 ncblk = nilfs_btree_nchildren_per_block(btree);
1830 if (!nilfs_bmap_dirty(btree))
1831 nilfs_bmap_set_dirty(btree);
1836 node = nilfs_btree_get_root(btree);
1842 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1845 node = nilfs_btree_get_root(btree);
1851 if (!nilfs_bmap_dirty(btree))
1852 nilfs_bmap_set_dirty(btree);
1855 if (NILFS_BMAP_USE_VBN(btree))
1856 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
1868 int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
1881 nilfs_btree_node_size(btree))) {
1890 ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
1894 nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
1896 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1900 static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
1905 while ((++level < nilfs_btree_height(btree) - 1) &&
1912 static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
1919 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1934 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1947 static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
1956 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
1960 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1966 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1971 static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
1979 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1983 static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
1992 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1996 while ((++level < nilfs_btree_height(btree) - 1) &&
2000 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
2012 nilfs_btree_abort_update_v(btree, path, level, dat);
2014 nilfs_btree_abort_update_v(btree, path, level, dat);
2018 static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
2027 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
2030 nilfs_btree_commit_update_v(btree, path, level, dat);
2033 static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
2039 struct inode *dat = nilfs_bmap_get_dat(btree);
2045 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
2051 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2060 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
2068 static int nilfs_btree_propagate(struct nilfs_bmap *btree,
2087 key = nilfs_bmap_data_get_key(btree, bh);
2091 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2094 nilfs_crit(btree->b_inode->i_sb,
2096 btree->b_inode->i_ino,
2101 ret = NILFS_BMAP_USE_VBN(btree) ?
2102 nilfs_btree_propagate_v(btree, path, level, bh) :
2103 nilfs_btree_propagate_p(btree, path, level, bh);
2111 static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
2114 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
2117 static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
2134 nilfs_warn(btree->b_inode->i_sb,
2135 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",
2137 btree->b_inode->i_ino,
2152 static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
2155 struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
2176 nilfs_btree_add_dirty_buffer(btree,
2190 static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
2202 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2210 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2215 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2232 static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
2240 struct inode *dat = nilfs_bmap_get_dat(btree);
2246 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2263 static int nilfs_btree_assign(struct nilfs_bmap *btree,
2282 key = nilfs_bmap_data_get_key(btree, *bh);
2286 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2292 ret = NILFS_BMAP_USE_VBN(btree) ?
2293 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2294 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2302 static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
2311 ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
2320 key = nilfs_bmap_data_get_key(btree, *bh);
2329 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
2340 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2345 ret = nilfs_btree_get_block(btree, ptr, &bh);
2354 if (!nilfs_bmap_dirty(btree))
2355 nilfs_bmap_set_dirty(btree);