Lines Matching refs:btree
3 * btree.c - NILFS B-tree.
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);
758 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
770 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
775 ncmax = nilfs_btree_nchildren_per_block(btree);
787 static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
791 if (level < nilfs_btree_height(btree) - 1) {
799 (++level < nilfs_btree_height(btree) - 1));
803 if (level == nilfs_btree_height(btree) - 1) {
804 nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
809 static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
816 if (level < nilfs_btree_height(btree) - 1) {
818 ncblk = nilfs_btree_nchildren_per_block(btree);
825 nilfs_btree_promote_key(btree, path, level + 1,
829 node = nilfs_btree_get_root(btree);
836 static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
847 ncblk = nilfs_btree_nchildren_per_block(btree);
864 nilfs_btree_promote_key(btree, path, level + 1,
879 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
882 static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
893 ncblk = nilfs_btree_nchildren_per_block(btree);
911 nilfs_btree_promote_key(btree, path, level + 1,
926 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
929 static void nilfs_btree_split(struct nilfs_bmap *btree,
939 ncblk = nilfs_btree_nchildren_per_block(btree);
967 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
979 static void nilfs_btree_grow(struct nilfs_bmap *btree,
986 root = nilfs_btree_get_root(btree);
988 ncblk = nilfs_btree_nchildren_per_block(btree);
1002 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
1008 static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
1020 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1028 if (level <= nilfs_btree_height(btree) - 1) {
1029 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1037 static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
1043 ptr = nilfs_bmap_find_target_seq(btree, key);
1048 ptr = nilfs_btree_find_near(btree, path);
1054 return nilfs_bmap_find_target_in_group(btree);
1057 static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
1072 if (NILFS_BMAP_USE_VBN(btree)) {
1074 nilfs_btree_find_target_v(btree, path, key);
1075 dat = nilfs_bmap_get_dat(btree);
1078 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1082 ncblk = nilfs_btree_nchildren_per_block(btree);
1085 level < nilfs_btree_height(btree) - 1;
1094 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1101 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1119 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1136 ret = nilfs_bmap_prepare_alloc_ptr(btree,
1140 ret = nilfs_btree_get_new_block(btree,
1155 node = nilfs_btree_get_root(btree);
1165 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1168 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1191 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1195 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1199 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1206 static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
1215 if (NILFS_BMAP_USE_VBN(btree)) {
1216 nilfs_bmap_set_target_v(btree, key, ptr);
1217 dat = nilfs_bmap_get_dat(btree);
1221 nilfs_bmap_commit_alloc_ptr(btree,
1223 path[level].bp_op(btree, path, level, &key, &ptr);
1226 if (!nilfs_bmap_dirty(btree))
1227 nilfs_bmap_set_dirty(btree);
1230 static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
1240 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1248 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1251 nilfs_btree_commit_insert(btree, path, level, key, ptr);
1252 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1259 static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
1266 if (level < nilfs_btree_height(btree) - 1) {
1268 ncblk = nilfs_btree_nchildren_per_block(btree);
1274 nilfs_btree_promote_key(btree, path, level + 1,
1277 node = nilfs_btree_get_root(btree);
1284 static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
1291 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1297 ncblk = nilfs_btree_nchildren_per_block(btree);
1308 nilfs_btree_promote_key(btree, path, level + 1,
1316 static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
1323 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1329 ncblk = nilfs_btree_nchildren_per_block(btree);
1341 nilfs_btree_promote_key(btree, path, level + 1,
1349 static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
1356 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1360 ncblk = nilfs_btree_nchildren_per_block(btree);
1375 static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
1382 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1386 ncblk = nilfs_btree_nchildren_per_block(btree);
1400 static void nilfs_btree_shrink(struct nilfs_bmap *btree,
1407 nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1409 root = nilfs_btree_get_root(btree);
1411 ncblk = nilfs_btree_nchildren_per_block(btree);
1424 static void nilfs_btree_nop(struct nilfs_bmap *btree,
1430 static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1443 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1444 ncblk = nilfs_btree_nchildren_per_block(btree);
1447 level < nilfs_btree_height(btree) - 1;
1452 ret = nilfs_bmap_prepare_end_ptr(btree,
1463 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1471 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1491 ret = nilfs_btree_get_block(btree, sibptr, &bh);
1517 WARN_ON(level != nilfs_btree_height(btree) - 2);
1538 node = nilfs_btree_get_root(btree);
1543 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1554 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1558 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1565 static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
1572 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1573 path[level].bp_op(btree, path, level, NULL, NULL);
1576 if (!nilfs_bmap_dirty(btree))
1577 nilfs_bmap_set_dirty(btree);
1580 static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
1592 ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1598 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1600 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1603 nilfs_btree_commit_delete(btree, path, level, dat);
1604 nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);
1611 static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
1622 ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
1626 ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
1632 static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
1641 ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1648 static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
1656 root = nilfs_btree_get_root(btree);
1657 switch (nilfs_btree_height(btree)) {
1668 ret = nilfs_btree_get_block(btree, ptr, &bh);
1687 static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
1697 root = nilfs_btree_get_root(btree);
1698 switch (nilfs_btree_height(btree)) {
1709 ret = nilfs_btree_get_block(btree, ptr, &bh);
1713 ncmax = nilfs_btree_nchildren_per_block(btree);
1737 nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
1751 if (NILFS_BMAP_USE_VBN(btree)) {
1752 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
1753 dat = nilfs_bmap_get_dat(btree);
1756 ret = nilfs_attach_btree_node_cache(&NILFS_BMAP_I(btree)->vfs_inode);
1760 ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
1768 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
1772 ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
1785 nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
1787 nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
1794 nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
1808 if (btree->b_ops->bop_clear != NULL)
1809 btree->b_ops->bop_clear(btree);
1815 dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1816 __nilfs_btree_init(btree);
1818 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1819 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
1823 ncblk = nilfs_btree_nchildren_per_block(btree);
1828 if (!nilfs_bmap_dirty(btree))
1829 nilfs_bmap_set_dirty(btree);
1834 node = nilfs_btree_get_root(btree);
1840 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1843 node = nilfs_btree_get_root(btree);
1849 if (!nilfs_bmap_dirty(btree))
1850 nilfs_bmap_set_dirty(btree);
1853 if (NILFS_BMAP_USE_VBN(btree))
1854 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
1866 int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
1879 nilfs_btree_node_size(btree))) {
1888 ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
1892 nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
1894 nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1898 static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
1903 while ((++level < nilfs_btree_height(btree) - 1) &&
1910 static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
1917 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1932 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1945 static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
1954 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
1958 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1964 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1969 static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
1977 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1981 static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
1990 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1994 while ((++level < nilfs_btree_height(btree) - 1) &&
1998 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
2010 nilfs_btree_abort_update_v(btree, path, level, dat);
2012 nilfs_btree_abort_update_v(btree, path, level, dat);
2016 static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
2025 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
2028 nilfs_btree_commit_update_v(btree, path, level, dat);
2031 static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
2037 struct inode *dat = nilfs_bmap_get_dat(btree);
2043 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
2049 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2058 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
2066 static int nilfs_btree_propagate(struct nilfs_bmap *btree,
2085 key = nilfs_bmap_data_get_key(btree, bh);
2089 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2092 nilfs_crit(btree->b_inode->i_sb,
2094 btree->b_inode->i_ino,
2099 ret = NILFS_BMAP_USE_VBN(btree) ?
2100 nilfs_btree_propagate_v(btree, path, level, bh) :
2101 nilfs_btree_propagate_p(btree, path, level, bh);
2109 static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
2112 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
2115 static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
2132 nilfs_warn(btree->b_inode->i_sb,
2133 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",
2135 btree->b_inode->i_ino,
2150 static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
2153 struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
2174 nilfs_btree_add_dirty_buffer(btree,
2188 static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
2200 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2208 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2213 NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2229 static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
2237 struct inode *dat = nilfs_bmap_get_dat(btree);
2243 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2260 static int nilfs_btree_assign(struct nilfs_bmap *btree,
2279 key = nilfs_bmap_data_get_key(btree, *bh);
2283 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2289 ret = NILFS_BMAP_USE_VBN(btree) ?
2290 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2291 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2299 static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
2308 ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
2317 key = nilfs_bmap_data_get_key(btree, *bh);
2326 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
2337 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2342 ret = nilfs_btree_get_block(btree, ptr, &bh);
2351 if (!nilfs_bmap_dirty(btree))
2352 nilfs_bmap_set_dirty(btree);