Lines Matching full:level
26 int level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_alloc_path() local
32 for (; level < NILFS_BTREE_LEVEL_MAX; level++) { in nilfs_btree_alloc_path()
33 path[level].bp_bh = NULL; in nilfs_btree_alloc_path()
34 path[level].bp_sib_bh = NULL; in nilfs_btree_alloc_path()
35 path[level].bp_index = 0; in nilfs_btree_alloc_path()
36 path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; in nilfs_btree_alloc_path()
37 path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; in nilfs_btree_alloc_path()
38 path[level].bp_op = NULL; in nilfs_btree_alloc_path()
47 int level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_free_path() local
49 for (; level < NILFS_BTREE_LEVEL_MAX; level++) in nilfs_btree_free_path()
50 brelse(path[level].bp_bh); in nilfs_btree_free_path()
96 nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) in nilfs_btree_node_set_level() argument
98 node->bn_level = level; in nilfs_btree_node_set_level()
163 int level, int nchildren, int ncmax, in nilfs_btree_node_init() argument
171 nilfs_btree_node_set_level(node, level); in nilfs_btree_node_init()
343 int level, flags, nchildren; in nilfs_btree_node_broken() local
346 level = nilfs_btree_node_get_level(node); in nilfs_btree_node_broken()
350 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_node_broken()
351 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_node_broken()
356 "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d", in nilfs_btree_node_broken()
357 inode->i_ino, (unsigned long long)blocknr, level, in nilfs_btree_node_broken()
374 int level, flags, nchildren; in nilfs_btree_root_broken() local
377 level = nilfs_btree_node_get_level(node); in nilfs_btree_root_broken()
381 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_root_broken()
382 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_root_broken()
386 "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d", in nilfs_btree_root_broken()
387 inode->i_ino, level, flags, nchildren); in nilfs_btree_root_broken()
416 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_nonroot_node() argument
418 return (struct nilfs_btree_node *)path[level].bp_bh->b_data; in nilfs_btree_get_nonroot_node()
422 nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_sib_node() argument
424 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; in nilfs_btree_get_sib_node()
435 int level, int *ncmaxp) in nilfs_btree_get_node() argument
439 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_get_node()
443 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_node()
450 struct nilfs_btree_node *node, int level) in nilfs_btree_bad_node() argument
452 if (unlikely(nilfs_btree_node_get_level(node) != level)) { in nilfs_btree_bad_node()
455 "btree level mismatch (ino=%lu): %d != %d", in nilfs_btree_bad_node()
457 nilfs_btree_node_get_level(node), level); in nilfs_btree_bad_node()
554 int level, index, found, ncmax, ret; in nilfs_btree_do_lookup() local
557 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup()
558 if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) in nilfs_btree_do_lookup()
564 path[level].bp_bh = NULL; in nilfs_btree_do_lookup()
565 path[level].bp_index = index; in nilfs_btree_do_lookup()
569 while (--level >= minlevel) { in nilfs_btree_do_lookup()
571 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) { in nilfs_btree_do_lookup()
572 p.node = nilfs_btree_get_node(btree, path, level + 1, in nilfs_btree_do_lookup()
578 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh, in nilfs_btree_do_lookup()
583 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup()
584 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup()
593 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); in nilfs_btree_do_lookup()
597 path[level].bp_index = index; in nilfs_btree_do_lookup()
614 int index, level, ncmax, ret; in nilfs_btree_do_lookup_last() local
620 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup_last()
623 path[level].bp_bh = NULL; in nilfs_btree_do_lookup_last()
624 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
627 for (level--; level > 0; level--) { in nilfs_btree_do_lookup_last()
628 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); in nilfs_btree_do_lookup_last()
631 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup_last()
632 if (nilfs_btree_bad_node(btree, node, level)) in nilfs_btree_do_lookup_last()
636 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
651 * @minlevel: start level
663 int index, next_adj, level; in nilfs_btree_get_next_key() local
667 for (level = minlevel; level <= maxlevel; level++) { in nilfs_btree_get_next_key()
668 if (level == maxlevel) in nilfs_btree_get_next_key()
671 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_next_key()
673 index = path[level].bp_index + next_adj; in nilfs_btree_get_next_key()
686 __u64 key, int level, __u64 *ptrp) in nilfs_btree_lookup() argument
695 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0); in nilfs_btree_lookup()
711 int level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_contig() local
719 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1); in nilfs_btree_lookup_contig()
735 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_lookup_contig()
736 index = path[level].bp_index + 1; in nilfs_btree_lookup_contig()
753 if (level == maxlevel) in nilfs_btree_lookup_contig()
757 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); in nilfs_btree_lookup_contig()
758 p.index = path[level + 1].bp_index + 1; in nilfs_btree_lookup_contig()
764 path[level + 1].bp_index = p.index; in nilfs_btree_lookup_contig()
766 brelse(path[level].bp_bh); in nilfs_btree_lookup_contig()
767 path[level].bp_bh = NULL; in nilfs_btree_lookup_contig()
769 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh, in nilfs_btree_lookup_contig()
773 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_lookup_contig()
776 path[level].bp_index = index; in nilfs_btree_lookup_contig()
788 int level, __u64 key) in nilfs_btree_promote_key() argument
790 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
793 nilfs_btree_get_nonroot_node(path, level), in nilfs_btree_promote_key()
794 path[level].bp_index, key); in nilfs_btree_promote_key()
795 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_promote_key()
796 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_promote_key()
797 } while ((path[level].bp_index == 0) && in nilfs_btree_promote_key()
798 (++level < nilfs_btree_height(btree) - 1)); in nilfs_btree_promote_key()
802 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
804 path[level].bp_index, key); in nilfs_btree_promote_key()
810 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_insert() argument
815 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_insert()
816 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_insert()
818 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
820 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_insert()
821 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_insert()
823 if (path[level].bp_index == 0) in nilfs_btree_do_insert()
824 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_insert()
829 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
837 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_left() argument
842 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_left()
843 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_left()
850 if (n > path[level].bp_index) { in nilfs_btree_carry_left()
858 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_left()
859 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_left()
860 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_left()
861 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_left()
863 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_left()
867 brelse(path[level].bp_bh); in nilfs_btree_carry_left()
868 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_left()
869 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
870 path[level].bp_index += lnchildren; in nilfs_btree_carry_left()
871 path[level + 1].bp_index--; in nilfs_btree_carry_left()
873 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_left()
874 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
875 path[level].bp_index -= n; in nilfs_btree_carry_left()
878 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_left()
883 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_right() argument
888 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_right()
889 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_right()
896 if (n > nchildren - path[level].bp_index) { in nilfs_btree_carry_right()
904 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_right()
905 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_right()
906 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_right()
907 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_right()
909 path[level + 1].bp_index++; in nilfs_btree_carry_right()
910 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_right()
912 path[level + 1].bp_index--; in nilfs_btree_carry_right()
915 brelse(path[level].bp_bh); in nilfs_btree_carry_right()
916 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_right()
917 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
918 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_right()
919 path[level + 1].bp_index++; in nilfs_btree_carry_right()
921 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_right()
922 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
925 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_right()
930 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_split() argument
935 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_split()
936 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_split()
942 if (n > nchildren - path[level].bp_index) { in nilfs_btree_split()
949 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_split()
950 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_split()
951 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_split()
952 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_split()
955 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_split()
956 nilfs_btree_node_insert(right, path[level].bp_index, in nilfs_btree_split()
960 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
962 brelse(path[level].bp_bh); in nilfs_btree_split()
963 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_split()
964 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
966 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_split()
969 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
971 brelse(path[level].bp_sib_bh); in nilfs_btree_split()
972 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
975 path[level + 1].bp_index++; in nilfs_btree_split()
980 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_grow() argument
986 child = nilfs_btree_get_sib_node(path, level); in nilfs_btree_grow()
993 nilfs_btree_node_set_level(root, level + 1); in nilfs_btree_grow()
995 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_grow()
996 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_grow()
998 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_grow()
999 path[level].bp_sib_bh = NULL; in nilfs_btree_grow()
1001 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_grow()
1004 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_grow()
1011 int level, ncmax; in nilfs_btree_find_near() local
1017 level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_find_near()
1018 if (path[level].bp_index > 0) { in nilfs_btree_find_near()
1019 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1021 path[level].bp_index - 1, in nilfs_btree_find_near()
1026 level = NILFS_BTREE_LEVEL_NODE_MIN + 1; in nilfs_btree_find_near()
1027 if (level <= nilfs_btree_height(btree) - 1) { in nilfs_btree_find_near()
1028 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1029 return nilfs_btree_node_get_ptr(node, path[level].bp_index, in nilfs_btree_find_near()
1064 int pindex, level, ncmax, ncblk, ret; in nilfs_btree_prepare_insert() local
1068 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_prepare_insert()
1072 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1077 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1083 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_prepare_insert()
1084 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_insert()
1085 level++) { in nilfs_btree_prepare_insert()
1086 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_insert()
1088 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1093 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_insert()
1094 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_insert()
1105 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1106 path[level].bp_op = nilfs_btree_carry_left; in nilfs_btree_prepare_insert()
1123 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1124 path[level].bp_op = nilfs_btree_carry_right; in nilfs_btree_prepare_insert()
1133 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1134 path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1136 &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1140 path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1148 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1149 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1150 path[level].bp_op = nilfs_btree_split; in nilfs_btree_prepare_insert()
1157 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1163 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1164 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1167 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1173 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1174 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1175 path[level].bp_op = nilfs_btree_grow; in nilfs_btree_prepare_insert()
1177 level++; in nilfs_btree_prepare_insert()
1178 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1185 *levelp = level; in nilfs_btree_prepare_insert()
1190 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1192 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { in nilfs_btree_prepare_insert()
1193 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_prepare_insert()
1194 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1198 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1200 *levelp = level; in nilfs_btree_prepare_insert()
1210 int level; in nilfs_btree_commit_insert() local
1219 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_insert()
1221 &path[level - 1].bp_newreq, dat); in nilfs_btree_commit_insert()
1222 path[level].bp_op(btree, path, level, &key, &ptr); in nilfs_btree_commit_insert()
1233 int level, ret; in nilfs_btree_insert() local
1247 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats); in nilfs_btree_insert()
1250 nilfs_btree_commit_insert(btree, path, level, key, ptr); in nilfs_btree_insert()
1260 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_delete() argument
1265 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_delete()
1266 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_delete()
1268 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1270 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_delete()
1271 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_delete()
1272 if (path[level].bp_index == 0) in nilfs_btree_do_delete()
1273 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_delete()
1277 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1285 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_left() argument
1290 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_left()
1292 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_left()
1293 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_left()
1302 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_left()
1303 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_left()
1304 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_left()
1305 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1307 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_left()
1310 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1311 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_left()
1312 path[level].bp_index += n; in nilfs_btree_borrow_left()
1317 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_right() argument
1322 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_right()
1324 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_right()
1325 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_right()
1334 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_right()
1335 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_right()
1336 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_right()
1337 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1339 path[level + 1].bp_index++; in nilfs_btree_borrow_right()
1340 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_right()
1342 path[level + 1].bp_index--; in nilfs_btree_borrow_right()
1344 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1345 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_right()
1350 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_left() argument
1355 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_left()
1357 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_left()
1358 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_left()
1365 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_concat_left()
1366 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_concat_left()
1368 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_concat_left()
1369 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_concat_left()
1370 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_left()
1371 path[level].bp_index += nilfs_btree_node_get_nchildren(left); in nilfs_btree_concat_left()
1376 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_right() argument
1381 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_right()
1383 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_right()
1384 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_right()
1391 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_concat_right()
1392 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_concat_right()
1394 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_concat_right()
1395 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_right()
1396 path[level + 1].bp_index++; in nilfs_btree_concat_right()
1401 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_shrink() argument
1406 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_shrink()
1409 child = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_shrink()
1414 nilfs_btree_node_set_level(root, level); in nilfs_btree_shrink()
1419 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_shrink()
1420 path[level].bp_bh = NULL; in nilfs_btree_shrink()
1425 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_nop() argument
1438 int pindex, dindex, level, ncmin, ncmax, ncblk, ret; in nilfs_btree_prepare_delete() local
1445 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index; in nilfs_btree_prepare_delete()
1446 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_delete()
1447 level++) { in nilfs_btree_prepare_delete()
1448 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_delete()
1449 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1452 &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1457 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1462 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_delete()
1463 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_delete()
1475 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1476 path[level].bp_op = nilfs_btree_borrow_left; in nilfs_btree_prepare_delete()
1480 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1481 path[level].bp_op = nilfs_btree_concat_left; in nilfs_btree_prepare_delete()
1495 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1496 path[level].bp_op = nilfs_btree_borrow_right; in nilfs_btree_prepare_delete()
1500 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1501 path[level].bp_op = nilfs_btree_concat_right; in nilfs_btree_prepare_delete()
1516 WARN_ON(level != nilfs_btree_height(btree) - 2); in nilfs_btree_prepare_delete()
1519 path[level].bp_op = nilfs_btree_shrink; in nilfs_btree_prepare_delete()
1521 level++; in nilfs_btree_prepare_delete()
1522 path[level].bp_op = nilfs_btree_nop; in nilfs_btree_prepare_delete()
1525 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1533 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1538 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1542 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1548 *levelp = level; in nilfs_btree_prepare_delete()
1553 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1555 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { in nilfs_btree_prepare_delete()
1556 brelse(path[level].bp_sib_bh); in nilfs_btree_prepare_delete()
1557 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1559 *levelp = level; in nilfs_btree_prepare_delete()
1568 int level; in nilfs_btree_commit_delete() local
1570 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_delete()
1571 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_commit_delete()
1572 path[level].bp_op(btree, path, level, NULL, NULL); in nilfs_btree_commit_delete()
1585 int level, ret; in nilfs_btree_delete() local
1599 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); in nilfs_btree_delete()
1602 nilfs_btree_commit_delete(btree, path, level, dat); in nilfs_btree_delete()
1818 /* create child node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1830 /* create root node at level 2 */ in nilfs_btree_commit_convert_and_insert()
1839 /* create root node at level 1 */ in nilfs_btree_commit_convert_and_insert()
1897 int level, in nilfs_btree_propagate_p() argument
1900 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_propagate_p()
1901 !buffer_dirty(path[level].bp_bh)) in nilfs_btree_propagate_p()
1902 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_propagate_p()
1909 int level, struct inode *dat) in nilfs_btree_prepare_update_v() argument
1914 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_update_v()
1915 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_update_v()
1916 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_prepare_update_v()
1918 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; in nilfs_btree_prepare_update_v()
1919 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1920 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1924 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_prepare_update_v()
1925 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1926 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1927 path[level].bp_ctxt.bh = path[level].bp_bh; in nilfs_btree_prepare_update_v()
1930 &path[level].bp_ctxt); in nilfs_btree_prepare_update_v()
1933 &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1934 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1944 int level, struct inode *dat) in nilfs_btree_commit_update_v() argument
1949 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_commit_update_v()
1950 &path[level].bp_newreq.bpr_req, in nilfs_btree_commit_update_v()
1953 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_commit_update_v()
1956 &path[level].bp_ctxt); in nilfs_btree_commit_update_v()
1957 path[level].bp_bh = path[level].bp_ctxt.bh; in nilfs_btree_commit_update_v()
1959 set_buffer_nilfs_volatile(path[level].bp_bh); in nilfs_btree_commit_update_v()
1961 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_commit_update_v()
1962 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, in nilfs_btree_commit_update_v()
1963 path[level].bp_newreq.bpr_ptr, ncmax); in nilfs_btree_commit_update_v()
1968 int level, struct inode *dat) in nilfs_btree_abort_update_v() argument
1970 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_abort_update_v()
1971 &path[level].bp_newreq.bpr_req); in nilfs_btree_abort_update_v()
1972 if (buffer_nilfs_node(path[level].bp_bh)) in nilfs_btree_abort_update_v()
1975 &path[level].bp_ctxt); in nilfs_btree_abort_update_v()
1983 int level, ret; in nilfs_btree_prepare_propagate_v() local
1985 level = minlevel; in nilfs_btree_prepare_propagate_v()
1986 if (!buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1987 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1991 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_prepare_propagate_v()
1992 !buffer_dirty(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1994 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh)); in nilfs_btree_prepare_propagate_v()
1995 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2001 *maxlevelp = level - 1; in nilfs_btree_prepare_propagate_v()
2006 while (--level > minlevel) in nilfs_btree_prepare_propagate_v()
2007 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2008 if (!buffer_nilfs_volatile(path[level].bp_bh)) in nilfs_btree_prepare_propagate_v()
2009 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2019 int level; in nilfs_btree_commit_propagate_v() local
2024 for (level = minlevel + 1; level <= maxlevel; level++) in nilfs_btree_commit_propagate_v()
2025 nilfs_btree_commit_update_v(btree, path, level, dat); in nilfs_btree_commit_propagate_v()
2030 int level, struct buffer_head *bh) in nilfs_btree_propagate_v() argument
2039 path[level].bp_bh = bh; in nilfs_btree_propagate_v()
2040 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel, in nilfs_btree_propagate_v()
2045 if (buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_propagate_v()
2046 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_propagate_v()
2048 path[level + 1].bp_index, in nilfs_btree_propagate_v()
2055 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat); in nilfs_btree_propagate_v()
2058 brelse(path[level].bp_bh); in nilfs_btree_propagate_v()
2059 path[level].bp_bh = NULL; in nilfs_btree_propagate_v()
2069 int level, ret; in nilfs_btree_propagate() local
2080 level = nilfs_btree_node_get_level(node); in nilfs_btree_propagate()
2083 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_propagate()
2086 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_propagate()
2090 "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d", in nilfs_btree_propagate()
2092 (unsigned long long)key, level); in nilfs_btree_propagate()
2097 nilfs_btree_propagate_v(btree, path, level, bh) : in nilfs_btree_propagate()
2098 nilfs_btree_propagate_p(btree, path, level, bh); in nilfs_btree_propagate()
2120 int level; in nilfs_btree_add_dirty_buffer() local
2125 level = nilfs_btree_node_get_level(node); in nilfs_btree_add_dirty_buffer()
2126 if (level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_add_dirty_buffer()
2127 level >= NILFS_BTREE_LEVEL_MAX) { in nilfs_btree_add_dirty_buffer()
2130 "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)", in nilfs_btree_add_dirty_buffer()
2131 level, (unsigned long long)key, in nilfs_btree_add_dirty_buffer()
2137 list_for_each(head, &lists[level]) { in nilfs_btree_add_dirty_buffer()
2156 int level, i; in nilfs_btree_lookup_dirty_buffers() local
2158 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2159 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2160 level++) in nilfs_btree_lookup_dirty_buffers()
2161 INIT_LIST_HEAD(&lists[level]); in nilfs_btree_lookup_dirty_buffers()
2179 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2180 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2181 level++) in nilfs_btree_lookup_dirty_buffers()
2182 list_splice_tail(&lists[level], listp); in nilfs_btree_lookup_dirty_buffers()
2187 int level, in nilfs_btree_assign_p() argument
2197 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_p()
2198 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_p()
2201 path[level].bp_ctxt.oldkey = ptr; in nilfs_btree_assign_p()
2202 path[level].bp_ctxt.newkey = blocknr; in nilfs_btree_assign_p()
2203 path[level].bp_ctxt.bh = *bh; in nilfs_btree_assign_p()
2206 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2211 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2212 *bh = path[level].bp_ctxt.bh; in nilfs_btree_assign_p()
2215 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr, in nilfs_btree_assign_p()
2218 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_p()
2221 binfo->bi_dat.bi_level = level; in nilfs_btree_assign_p()
2229 int level, in nilfs_btree_assign_v() argument
2241 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_v()
2242 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_v()
2250 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_v()
2266 int level, ret; in nilfs_btree_assign() local
2275 level = nilfs_btree_node_get_level(node); in nilfs_btree_assign()
2278 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_assign()
2281 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_assign()
2288 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : in nilfs_btree_assign()
2289 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); in nilfs_btree_assign()
2324 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) in nilfs_btree_mark() argument
2335 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0); in nilfs_btree_mark()