Lines Matching refs: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);
786 static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
790 if (level < nilfs_btree_height(btree) - 1) {
798 (++level < nilfs_btree_height(btree) - 1));
802 if (level == nilfs_btree_height(btree) - 1) {
803 nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
808 static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
815 if (level < nilfs_btree_height(btree) - 1) {
817 ncblk = nilfs_btree_nchildren_per_block(btree);
824 nilfs_btree_promote_key(btree, path, level + 1,
828 node = nilfs_btree_get_root(btree);
835 static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
846 ncblk = nilfs_btree_nchildren_per_block(btree);
863 nilfs_btree_promote_key(btree, path, level + 1,
878 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
881 static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
892 ncblk = nilfs_btree_nchildren_per_block(btree);
910 nilfs_btree_promote_key(btree, path, level + 1,
925 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
928 static void nilfs_btree_split(struct nilfs_bmap *btree,
938 ncblk = nilfs_btree_nchildren_per_block(btree);
966 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
978 static void nilfs_btree_grow(struct nilfs_bmap *btree,
985 root = nilfs_btree_get_root(btree);
987 ncblk = nilfs_btree_nchildren_per_block(btree);
1001 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
1007 static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
1019 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1027 if (level <= nilfs_btree_height(btree) - 1) {
1028 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1036 static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
1042 ptr = nilfs_bmap_find_target_seq(btree, key);
1047 ptr = nilfs_btree_find_near(btree, path);
1053 return nilfs_bmap_find_target_in_group(btree);
1056 static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
1071 if (NILFS_BMAP_USE_VBN(btree)) {
1073 nilfs_btree_find_target_v(btree, path, key);
1074 dat = nilfs_bmap_get_dat(btree);
1077 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1081 ncblk = nilfs_btree_nchildren_per_block(btree);
1084 level < nilfs_btree_height(btree) - 1;
1093 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1100 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1118 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1135 ret = nilfs_bmap_prepare_alloc_ptr(btree,
1139 ret = nilfs_btree_get_new_block(btree,
1154 node = nilfs_btree_get_root(btree);
1164 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1167 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1190 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1194 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1198 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1205 static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
1214 if (NILFS_BMAP_USE_VBN(btree)) {
1215 nilfs_bmap_set_target_v(btree, key, ptr);
1216 dat = nilfs_bmap_get_dat(btree);
1220 nilfs_bmap_commit_alloc_ptr(btree,
1222 path[level].bp_op(btree, path, level, &key, &ptr);
1225 if (!nilfs_bmap_dirty(btree))
1226 nilfs_bmap_set_dirty(btree);
1229 static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
1239 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1247 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1250 nilfs_btree_commit_insert(btree, path, level, key, ptr);
1251 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1258 static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
1265 if (level < nilfs_btree_height(btree) - 1) {
1267 ncblk = nilfs_btree_nchildren_per_block(btree);
1273 nilfs_btree_promote_key(btree, path, level + 1,
1276 node = nilfs_btree_get_root(btree);
1283 static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
1290 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1296 ncblk = nilfs_btree_nchildren_per_block(btree);
1307 nilfs_btree_promote_key(btree, path, level + 1,
1315 static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
1322 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1328 ncblk = nilfs_btree_nchildren_per_block(btree);
1340 nilfs_btree_promote_key(btree, path, level + 1,
1348 static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
1355 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1359 ncblk = nilfs_btree_nchildren_per_block(btree);
1374 static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
1381 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1385 ncblk = nilfs_btree_nchildren_per_block(btree);
1399 static void nilfs_btree_shrink(struct nilfs_bmap *btree,
1406 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1408 root = nilfs_btree_get_root(btree);
1410 ncblk = nilfs_btree_nchildren_per_block(btree);
1423 static void nilfs_btree_nop(struct nilfs_bmap *btree,
1429 static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1442 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1443 ncblk = nilfs_btree_nchildren_per_block(btree);
1446 level < nilfs_btree_height(btree) - 1;
1451 ret = nilfs_bmap_prepare_end_ptr(btree,
1462 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1470 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1490 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1516 WARN_ON(level != nilfs_btree_height(btree) - 2);
1537 node = nilfs_btree_get_root(btree);
1542 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1553 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1557 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1564 static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
1571 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1572 path[level].bp_op(btree, path, level, NULL, NULL);
1575 if (!nilfs_bmap_dirty(btree))
1576 nilfs_bmap_set_dirty(btree);
1579 static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
1591 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1597 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1599 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1602 nilfs_btree_commit_delete(btree, path, level, dat);
1603 nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);
1610 static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
1621 ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
1625 ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
1631 static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
1640 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1647 static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
1655 root = nilfs_btree_get_root(btree);
1656 switch (nilfs_btree_height(btree)) {
1667 ret = nilfs_btree_get_block(btree, ptr, &bh);
1685 static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
1695 root = nilfs_btree_get_root(btree);
1696 switch (nilfs_btree_height(btree)) {
1707 ret = nilfs_btree_get_block(btree, ptr, &bh);
1711 ncmax = nilfs_btree_nchildren_per_block(btree);
1734 nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
1748 if (NILFS_BMAP_USE_VBN(btree)) {
1749 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
1750 dat = nilfs_bmap_get_dat(btree);
1753 ret = nilfs_attach_btree_node_cache(&NILFS_BMAP_I(btree)->vfs_inode);
1757 ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
1765 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
1769 ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
1782 nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
1784 nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
1791 nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
1805 if (btree->b_ops->bop_clear != NULL)
1806 btree->b_ops->bop_clear(btree);
1812 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1813 __nilfs_btree_init(btree);
1815 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1816 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
1820 ncblk = nilfs_btree_nchildren_per_block(btree);
1825 if (!nilfs_bmap_dirty(btree))
1826 nilfs_bmap_set_dirty(btree);
1831 node = nilfs_btree_get_root(btree);
1837 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1840 node = nilfs_btree_get_root(btree);
1846 if (!nilfs_bmap_dirty(btree))
1847 nilfs_bmap_set_dirty(btree);
1850 if (NILFS_BMAP_USE_VBN(btree))
1851 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
1863 int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
1876 nilfs_btree_node_size(btree))) {
1885 ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
1889 nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
1891 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1895 static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
1900 while ((++level < nilfs_btree_height(btree) - 1) &&
1907 static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
1914 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1929 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1942 static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
1951 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
1955 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1961 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1966 static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
1974 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1978 static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
1987 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1991 while ((++level < nilfs_btree_height(btree) - 1) &&
1995 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
2007 nilfs_btree_abort_update_v(btree, path, level, dat);
2009 nilfs_btree_abort_update_v(btree, path, level, dat);
2013 static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
2022 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
2025 nilfs_btree_commit_update_v(btree, path, level, dat);
2028 static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
2034 struct inode *dat = nilfs_bmap_get_dat(btree);
2040 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
2046 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2055 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
2063 static int nilfs_btree_propagate(struct nilfs_bmap *btree,
2082 key = nilfs_bmap_data_get_key(btree, bh);
2086 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2089 nilfs_crit(btree->b_inode->i_sb,
2091 btree->b_inode->i_ino,
2096 ret = NILFS_BMAP_USE_VBN(btree) ?
2097 nilfs_btree_propagate_v(btree, path, level, bh) :
2098 nilfs_btree_propagate_p(btree, path, level, bh);
2106 static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
2109 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
2112 static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
2129 nilfs_warn(btree->b_inode->i_sb,
2130 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",
2132 btree->b_inode->i_ino,
2147 static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
2150 struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
2171 nilfs_btree_add_dirty_buffer(btree,
2185 static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
2197 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2205 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2210 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2227 static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
2235 struct inode *dat = nilfs_bmap_get_dat(btree);
2241 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2258 static int nilfs_btree_assign(struct nilfs_bmap *btree,
2277 key = nilfs_bmap_data_get_key(btree, *bh);
2281 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2287 ret = NILFS_BMAP_USE_VBN(btree) ?
2288 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2289 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2297 static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
2306 ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
2315 key = nilfs_bmap_data_get_key(btree, *bh);
2324 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
2335 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2340 ret = nilfs_btree_get_block(btree, ptr, &bh);
2349 if (!nilfs_bmap_dirty(btree))
2350 nilfs_bmap_set_dirty(btree);