Lines Matching refs:level
39 int level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_alloc_path() local
45 for (; level < NILFS_BTREE_LEVEL_MAX; level++) { in nilfs_btree_alloc_path()
46 path[level].bp_bh = NULL; in nilfs_btree_alloc_path()
47 path[level].bp_sib_bh = NULL; in nilfs_btree_alloc_path()
48 path[level].bp_index = 0; in nilfs_btree_alloc_path()
49 path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; in nilfs_btree_alloc_path()
50 path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR; in nilfs_btree_alloc_path()
51 path[level].bp_op = NULL; in nilfs_btree_alloc_path()
60 int level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_free_path() local
62 for (; level < NILFS_BTREE_LEVEL_MAX; level++) in nilfs_btree_free_path()
63 brelse(path[level].bp_bh); in nilfs_btree_free_path()
108 nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level) in nilfs_btree_node_set_level() argument
110 node->bn_level = level; in nilfs_btree_node_set_level()
175 int level, int nchildren, int ncmax, in nilfs_btree_node_init() argument
183 nilfs_btree_node_set_level(node, level); in nilfs_btree_node_init()
353 int level, flags, nchildren; in nilfs_btree_node_broken() local
356 level = nilfs_btree_node_get_level(node); in nilfs_btree_node_broken()
360 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_node_broken()
361 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_node_broken()
367 (unsigned long long)blocknr, level, flags, nchildren); in nilfs_btree_node_broken()
383 int level, flags, nchildren; in nilfs_btree_root_broken() local
386 level = nilfs_btree_node_get_level(node); in nilfs_btree_root_broken()
390 if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_root_broken()
391 level >= NILFS_BTREE_LEVEL_MAX || in nilfs_btree_root_broken()
395 ino, level, flags, nchildren); in nilfs_btree_root_broken()
422 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_nonroot_node() argument
424 return (struct nilfs_btree_node *)path[level].bp_bh->b_data; in nilfs_btree_get_nonroot_node()
428 nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level) in nilfs_btree_get_sib_node() argument
430 return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data; in nilfs_btree_get_sib_node()
441 int level, int *ncmaxp) in nilfs_btree_get_node() argument
445 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_get_node()
449 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_node()
456 nilfs_btree_bad_node(struct nilfs_btree_node *node, int level) in nilfs_btree_bad_node() argument
458 if (unlikely(nilfs_btree_node_get_level(node) != level)) { in nilfs_btree_bad_node()
461 nilfs_btree_node_get_level(node), level); in nilfs_btree_bad_node()
543 int level, index, found, ncmax, ret; in nilfs_btree_do_lookup() local
546 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup()
547 if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0) in nilfs_btree_do_lookup()
553 path[level].bp_bh = NULL; in nilfs_btree_do_lookup()
554 path[level].bp_index = index; in nilfs_btree_do_lookup()
558 while (--level >= minlevel) { in nilfs_btree_do_lookup()
560 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) { in nilfs_btree_do_lookup()
561 p.node = nilfs_btree_get_node(btree, path, level + 1, in nilfs_btree_do_lookup()
567 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh, in nilfs_btree_do_lookup()
572 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup()
573 if (nilfs_btree_bad_node(node, level)) in nilfs_btree_do_lookup()
582 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); in nilfs_btree_do_lookup()
586 path[level].bp_index = index; in nilfs_btree_do_lookup()
603 int index, level, ncmax, ret; in nilfs_btree_do_lookup_last() local
609 level = nilfs_btree_node_get_level(node); in nilfs_btree_do_lookup_last()
612 path[level].bp_bh = NULL; in nilfs_btree_do_lookup_last()
613 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
616 for (level--; level > 0; level--) { in nilfs_btree_do_lookup_last()
617 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); in nilfs_btree_do_lookup_last()
620 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_lookup_last()
621 if (nilfs_btree_bad_node(node, level)) in nilfs_btree_do_lookup_last()
625 path[level].bp_index = index; in nilfs_btree_do_lookup_last()
652 int index, next_adj, level; in nilfs_btree_get_next_key() local
656 for (level = minlevel; level <= maxlevel; level++) { in nilfs_btree_get_next_key()
657 if (level == maxlevel) in nilfs_btree_get_next_key()
660 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_get_next_key()
662 index = path[level].bp_index + next_adj; in nilfs_btree_get_next_key()
675 __u64 key, int level, __u64 *ptrp) in nilfs_btree_lookup() argument
684 ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0); in nilfs_btree_lookup()
699 int level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_contig() local
707 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1); in nilfs_btree_lookup_contig()
723 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_lookup_contig()
724 index = path[level].bp_index + 1; in nilfs_btree_lookup_contig()
742 if (level == maxlevel) in nilfs_btree_lookup_contig()
746 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax); in nilfs_btree_lookup_contig()
747 p.index = path[level + 1].bp_index + 1; in nilfs_btree_lookup_contig()
753 path[level + 1].bp_index = p.index; in nilfs_btree_lookup_contig()
755 brelse(path[level].bp_bh); in nilfs_btree_lookup_contig()
756 path[level].bp_bh = NULL; in nilfs_btree_lookup_contig()
758 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh, in nilfs_btree_lookup_contig()
762 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_lookup_contig()
765 path[level].bp_index = index; in nilfs_btree_lookup_contig()
777 int level, __u64 key) in nilfs_btree_promote_key() argument
779 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
782 nilfs_btree_get_nonroot_node(path, level), in nilfs_btree_promote_key()
783 path[level].bp_index, key); in nilfs_btree_promote_key()
784 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_promote_key()
785 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_promote_key()
786 } while ((path[level].bp_index == 0) && in nilfs_btree_promote_key()
787 (++level < nilfs_btree_height(btree) - 1)); in nilfs_btree_promote_key()
791 if (level == nilfs_btree_height(btree) - 1) { in nilfs_btree_promote_key()
793 path[level].bp_index, key); in nilfs_btree_promote_key()
799 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_insert() argument
804 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_insert()
805 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_insert()
807 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
809 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_insert()
810 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_insert()
812 if (path[level].bp_index == 0) in nilfs_btree_do_insert()
813 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_insert()
818 nilfs_btree_node_insert(node, path[level].bp_index, in nilfs_btree_do_insert()
826 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_left() argument
831 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_left()
832 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_left()
839 if (n > path[level].bp_index) { in nilfs_btree_carry_left()
847 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_left()
848 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_left()
849 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_left()
850 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_left()
852 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_left()
856 brelse(path[level].bp_bh); in nilfs_btree_carry_left()
857 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_left()
858 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
859 path[level].bp_index += lnchildren; in nilfs_btree_carry_left()
860 path[level + 1].bp_index--; in nilfs_btree_carry_left()
862 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_left()
863 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_left()
864 path[level].bp_index -= n; in nilfs_btree_carry_left()
867 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_left()
872 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_carry_right() argument
877 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_carry_right()
878 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_carry_right()
885 if (n > nchildren - path[level].bp_index) { in nilfs_btree_carry_right()
893 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_carry_right()
894 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_carry_right()
895 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_carry_right()
896 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_carry_right()
898 path[level + 1].bp_index++; in nilfs_btree_carry_right()
899 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_carry_right()
901 path[level + 1].bp_index--; in nilfs_btree_carry_right()
904 brelse(path[level].bp_bh); in nilfs_btree_carry_right()
905 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_carry_right()
906 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
907 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_carry_right()
908 path[level + 1].bp_index++; in nilfs_btree_carry_right()
910 brelse(path[level].bp_sib_bh); in nilfs_btree_carry_right()
911 path[level].bp_sib_bh = NULL; in nilfs_btree_carry_right()
914 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_carry_right()
919 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_split() argument
926 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_split()
927 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_split()
933 if (n > nchildren - path[level].bp_index) { in nilfs_btree_split()
940 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_split()
941 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_split()
942 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_split()
943 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_split()
946 newptr = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
949 path[level].bp_index -= nilfs_btree_node_get_nchildren(node); in nilfs_btree_split()
950 nilfs_btree_node_insert(right, path[level].bp_index, in nilfs_btree_split()
954 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
956 brelse(path[level].bp_bh); in nilfs_btree_split()
957 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_split()
958 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
960 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_split()
963 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_split()
965 brelse(path[level].bp_sib_bh); in nilfs_btree_split()
966 path[level].bp_sib_bh = NULL; in nilfs_btree_split()
969 path[level + 1].bp_index++; in nilfs_btree_split()
974 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_grow() argument
980 child = nilfs_btree_get_sib_node(path, level); in nilfs_btree_grow()
987 nilfs_btree_node_set_level(root, level + 1); in nilfs_btree_grow()
989 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_grow()
990 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_grow()
992 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_grow()
993 path[level].bp_sib_bh = NULL; in nilfs_btree_grow()
995 nilfs_btree_do_insert(btree, path, level, keyp, ptrp); in nilfs_btree_grow()
998 *ptrp = path[level].bp_newreq.bpr_ptr; in nilfs_btree_grow()
1005 int level, ncmax; in nilfs_btree_find_near() local
1011 level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_find_near()
1012 if (path[level].bp_index > 0) { in nilfs_btree_find_near()
1013 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1015 path[level].bp_index - 1, in nilfs_btree_find_near()
1020 level = NILFS_BTREE_LEVEL_NODE_MIN + 1; in nilfs_btree_find_near()
1021 if (level <= nilfs_btree_height(btree) - 1) { in nilfs_btree_find_near()
1022 node = nilfs_btree_get_node(btree, path, level, &ncmax); in nilfs_btree_find_near()
1023 return nilfs_btree_node_get_ptr(node, path[level].bp_index, in nilfs_btree_find_near()
1058 int pindex, level, ncmax, ncblk, ret; in nilfs_btree_prepare_insert() local
1062 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_prepare_insert()
1066 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1071 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1077 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_prepare_insert()
1078 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_insert()
1079 level++) { in nilfs_btree_prepare_insert()
1080 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_insert()
1082 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1087 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_insert()
1088 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_insert()
1099 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1100 path[level].bp_op = nilfs_btree_carry_left; in nilfs_btree_prepare_insert()
1117 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1118 path[level].bp_op = nilfs_btree_carry_right; in nilfs_btree_prepare_insert()
1127 path[level].bp_newreq.bpr_ptr = in nilfs_btree_prepare_insert()
1128 path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1130 &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1134 path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1142 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1143 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1144 path[level].bp_op = nilfs_btree_split; in nilfs_btree_prepare_insert()
1151 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1157 path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1; in nilfs_btree_prepare_insert()
1158 ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1161 ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr, in nilfs_btree_prepare_insert()
1167 0, level, 0, ncblk, NULL, NULL); in nilfs_btree_prepare_insert()
1168 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_insert()
1169 path[level].bp_op = nilfs_btree_grow; in nilfs_btree_prepare_insert()
1171 level++; in nilfs_btree_prepare_insert()
1172 path[level].bp_op = nilfs_btree_do_insert; in nilfs_btree_prepare_insert()
1179 *levelp = level; in nilfs_btree_prepare_insert()
1184 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1186 for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) { in nilfs_btree_prepare_insert()
1187 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_prepare_insert()
1188 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1192 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat); in nilfs_btree_prepare_insert()
1194 *levelp = level; in nilfs_btree_prepare_insert()
1204 int level; in nilfs_btree_commit_insert() local
1213 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_insert()
1215 &path[level - 1].bp_newreq, dat); in nilfs_btree_commit_insert()
1216 path[level].bp_op(btree, path, level, &key, &ptr); in nilfs_btree_commit_insert()
1227 int level, ret; in nilfs_btree_insert() local
1241 ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats); in nilfs_btree_insert()
1244 nilfs_btree_commit_insert(btree, path, level, key, ptr); in nilfs_btree_insert()
1254 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_do_delete() argument
1259 if (level < nilfs_btree_height(btree) - 1) { in nilfs_btree_do_delete()
1260 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_do_delete()
1262 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1264 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_do_delete()
1265 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_do_delete()
1266 if (path[level].bp_index == 0) in nilfs_btree_do_delete()
1267 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_do_delete()
1271 nilfs_btree_node_delete(node, path[level].bp_index, in nilfs_btree_do_delete()
1279 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_left() argument
1284 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_left()
1286 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_left()
1287 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_left()
1296 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_left()
1297 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_left()
1298 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_left()
1299 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1301 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_left()
1304 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_left()
1305 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_left()
1306 path[level].bp_index += n; in nilfs_btree_borrow_left()
1311 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_borrow_right() argument
1316 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_borrow_right()
1318 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_borrow_right()
1319 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_borrow_right()
1328 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_borrow_right()
1329 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_borrow_right()
1330 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_borrow_right()
1331 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1333 path[level + 1].bp_index++; in nilfs_btree_borrow_right()
1334 nilfs_btree_promote_key(btree, path, level + 1, in nilfs_btree_borrow_right()
1336 path[level + 1].bp_index--; in nilfs_btree_borrow_right()
1338 brelse(path[level].bp_sib_bh); in nilfs_btree_borrow_right()
1339 path[level].bp_sib_bh = NULL; in nilfs_btree_borrow_right()
1344 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_left() argument
1349 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_left()
1351 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_left()
1352 left = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_left()
1359 if (!buffer_dirty(path[level].bp_sib_bh)) in nilfs_btree_concat_left()
1360 mark_buffer_dirty(path[level].bp_sib_bh); in nilfs_btree_concat_left()
1362 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_concat_left()
1363 path[level].bp_bh = path[level].bp_sib_bh; in nilfs_btree_concat_left()
1364 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_left()
1365 path[level].bp_index += nilfs_btree_node_get_nchildren(left); in nilfs_btree_concat_left()
1370 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_concat_right() argument
1375 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_concat_right()
1377 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_concat_right()
1378 right = nilfs_btree_get_sib_node(path, level); in nilfs_btree_concat_right()
1385 if (!buffer_dirty(path[level].bp_bh)) in nilfs_btree_concat_right()
1386 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_concat_right()
1388 nilfs_btnode_delete(path[level].bp_sib_bh); in nilfs_btree_concat_right()
1389 path[level].bp_sib_bh = NULL; in nilfs_btree_concat_right()
1390 path[level + 1].bp_index++; in nilfs_btree_concat_right()
1395 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_shrink() argument
1400 nilfs_btree_do_delete(btree, path, level, keyp, ptrp); in nilfs_btree_shrink()
1403 child = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_shrink()
1408 nilfs_btree_node_set_level(root, level); in nilfs_btree_shrink()
1413 nilfs_btnode_delete(path[level].bp_bh); in nilfs_btree_shrink()
1414 path[level].bp_bh = NULL; in nilfs_btree_shrink()
1419 int level, __u64 *keyp, __u64 *ptrp) in nilfs_btree_nop() argument
1432 int pindex, dindex, level, ncmin, ncmax, ncblk, ret; in nilfs_btree_prepare_delete() local
1439 for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index; in nilfs_btree_prepare_delete()
1440 level < nilfs_btree_height(btree) - 1; in nilfs_btree_prepare_delete()
1441 level++) { in nilfs_btree_prepare_delete()
1442 node = nilfs_btree_get_nonroot_node(path, level); in nilfs_btree_prepare_delete()
1443 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1446 &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1451 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1456 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_delete()
1457 pindex = path[level + 1].bp_index; in nilfs_btree_prepare_delete()
1469 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1470 path[level].bp_op = nilfs_btree_borrow_left; in nilfs_btree_prepare_delete()
1474 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1475 path[level].bp_op = nilfs_btree_concat_left; in nilfs_btree_prepare_delete()
1489 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1490 path[level].bp_op = nilfs_btree_borrow_right; in nilfs_btree_prepare_delete()
1494 path[level].bp_sib_bh = bh; in nilfs_btree_prepare_delete()
1495 path[level].bp_op = nilfs_btree_concat_right; in nilfs_btree_prepare_delete()
1510 WARN_ON(level != nilfs_btree_height(btree) - 2); in nilfs_btree_prepare_delete()
1513 path[level].bp_op = nilfs_btree_shrink; in nilfs_btree_prepare_delete()
1515 level++; in nilfs_btree_prepare_delete()
1516 path[level].bp_op = nilfs_btree_nop; in nilfs_btree_prepare_delete()
1519 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1527 path[level].bp_op = nilfs_btree_do_delete; in nilfs_btree_prepare_delete()
1532 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_delete()
1536 ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1542 *levelp = level; in nilfs_btree_prepare_delete()
1547 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1549 for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) { in nilfs_btree_prepare_delete()
1550 brelse(path[level].bp_sib_bh); in nilfs_btree_prepare_delete()
1551 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_prepare_delete()
1553 *levelp = level; in nilfs_btree_prepare_delete()
1562 int level; in nilfs_btree_commit_delete() local
1564 for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) { in nilfs_btree_commit_delete()
1565 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat); in nilfs_btree_commit_delete()
1566 path[level].bp_op(btree, path, level, NULL, NULL); in nilfs_btree_commit_delete()
1579 int level, ret; in nilfs_btree_delete() local
1593 ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat); in nilfs_btree_delete()
1596 nilfs_btree_commit_delete(btree, path, level, dat); in nilfs_btree_delete()
1889 int level, in nilfs_btree_propagate_p() argument
1892 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_propagate_p()
1893 !buffer_dirty(path[level].bp_bh)) in nilfs_btree_propagate_p()
1894 mark_buffer_dirty(path[level].bp_bh); in nilfs_btree_propagate_p()
1901 int level, struct inode *dat) in nilfs_btree_prepare_update_v() argument
1906 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_prepare_update_v()
1907 path[level].bp_oldreq.bpr_ptr = in nilfs_btree_prepare_update_v()
1908 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_prepare_update_v()
1910 path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1; in nilfs_btree_prepare_update_v()
1911 ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1912 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1916 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_prepare_update_v()
1917 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1918 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr; in nilfs_btree_prepare_update_v()
1919 path[level].bp_ctxt.bh = path[level].bp_bh; in nilfs_btree_prepare_update_v()
1922 &path[level].bp_ctxt); in nilfs_btree_prepare_update_v()
1925 &path[level].bp_oldreq.bpr_req, in nilfs_btree_prepare_update_v()
1926 &path[level].bp_newreq.bpr_req); in nilfs_btree_prepare_update_v()
1936 int level, struct inode *dat) in nilfs_btree_commit_update_v() argument
1941 nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_commit_update_v()
1942 &path[level].bp_newreq.bpr_req, in nilfs_btree_commit_update_v()
1945 if (buffer_nilfs_node(path[level].bp_bh)) { in nilfs_btree_commit_update_v()
1948 &path[level].bp_ctxt); in nilfs_btree_commit_update_v()
1949 path[level].bp_bh = path[level].bp_ctxt.bh; in nilfs_btree_commit_update_v()
1951 set_buffer_nilfs_volatile(path[level].bp_bh); in nilfs_btree_commit_update_v()
1953 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_commit_update_v()
1954 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, in nilfs_btree_commit_update_v()
1955 path[level].bp_newreq.bpr_ptr, ncmax); in nilfs_btree_commit_update_v()
1960 int level, struct inode *dat) in nilfs_btree_abort_update_v() argument
1962 nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req, in nilfs_btree_abort_update_v()
1963 &path[level].bp_newreq.bpr_req); in nilfs_btree_abort_update_v()
1964 if (buffer_nilfs_node(path[level].bp_bh)) in nilfs_btree_abort_update_v()
1967 &path[level].bp_ctxt); in nilfs_btree_abort_update_v()
1975 int level, ret; in nilfs_btree_prepare_propagate_v() local
1977 level = minlevel; in nilfs_btree_prepare_propagate_v()
1978 if (!buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1979 ret = nilfs_btree_prepare_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
1983 while ((++level < nilfs_btree_height(btree) - 1) && in nilfs_btree_prepare_propagate_v()
1984 !buffer_dirty(path[level].bp_bh)) { in nilfs_btree_prepare_propagate_v()
1986 WARN_ON(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()
1993 *maxlevelp = level - 1; in nilfs_btree_prepare_propagate_v()
1998 while (--level > minlevel) in nilfs_btree_prepare_propagate_v()
1999 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2000 if (!buffer_nilfs_volatile(path[level].bp_bh)) in nilfs_btree_prepare_propagate_v()
2001 nilfs_btree_abort_update_v(btree, path, level, dat); in nilfs_btree_prepare_propagate_v()
2011 int level; in nilfs_btree_commit_propagate_v() local
2016 for (level = minlevel + 1; level <= maxlevel; level++) in nilfs_btree_commit_propagate_v()
2017 nilfs_btree_commit_update_v(btree, path, level, dat); in nilfs_btree_commit_propagate_v()
2022 int level, struct buffer_head *bh) in nilfs_btree_propagate_v() argument
2031 path[level].bp_bh = bh; in nilfs_btree_propagate_v()
2032 ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel, in nilfs_btree_propagate_v()
2037 if (buffer_nilfs_volatile(path[level].bp_bh)) { in nilfs_btree_propagate_v()
2038 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_propagate_v()
2040 path[level + 1].bp_index, in nilfs_btree_propagate_v()
2047 nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat); in nilfs_btree_propagate_v()
2050 brelse(path[level].bp_bh); in nilfs_btree_propagate_v()
2051 path[level].bp_bh = NULL; in nilfs_btree_propagate_v()
2061 int level, ret; in nilfs_btree_propagate() local
2072 level = nilfs_btree_node_get_level(node); in nilfs_btree_propagate()
2075 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_propagate()
2078 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_propagate()
2082 __func__, (unsigned long long)key, level); in nilfs_btree_propagate()
2087 nilfs_btree_propagate_v(btree, path, level, bh) : in nilfs_btree_propagate()
2088 nilfs_btree_propagate_p(btree, path, level, bh); in nilfs_btree_propagate()
2110 int level; in nilfs_btree_add_dirty_buffer() local
2115 level = nilfs_btree_node_get_level(node); in nilfs_btree_add_dirty_buffer()
2116 if (level < NILFS_BTREE_LEVEL_NODE_MIN || in nilfs_btree_add_dirty_buffer()
2117 level >= NILFS_BTREE_LEVEL_MAX) { in nilfs_btree_add_dirty_buffer()
2122 __func__, level, (unsigned long long)key, in nilfs_btree_add_dirty_buffer()
2128 list_for_each(head, &lists[level]) { in nilfs_btree_add_dirty_buffer()
2146 int level, i; in nilfs_btree_lookup_dirty_buffers() local
2148 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2149 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2150 level++) in nilfs_btree_lookup_dirty_buffers()
2151 INIT_LIST_HEAD(&lists[level]); in nilfs_btree_lookup_dirty_buffers()
2169 for (level = NILFS_BTREE_LEVEL_NODE_MIN; in nilfs_btree_lookup_dirty_buffers()
2170 level < NILFS_BTREE_LEVEL_MAX; in nilfs_btree_lookup_dirty_buffers()
2171 level++) in nilfs_btree_lookup_dirty_buffers()
2172 list_splice_tail(&lists[level], listp); in nilfs_btree_lookup_dirty_buffers()
2177 int level, in nilfs_btree_assign_p() argument
2187 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_p()
2188 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_p()
2191 path[level].bp_ctxt.oldkey = ptr; in nilfs_btree_assign_p()
2192 path[level].bp_ctxt.newkey = blocknr; in nilfs_btree_assign_p()
2193 path[level].bp_ctxt.bh = *bh; in nilfs_btree_assign_p()
2196 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2201 &path[level].bp_ctxt); in nilfs_btree_assign_p()
2202 *bh = path[level].bp_ctxt.bh; in nilfs_btree_assign_p()
2205 nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr, in nilfs_btree_assign_p()
2208 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_p()
2211 binfo->bi_dat.bi_level = level; in nilfs_btree_assign_p()
2218 int level, in nilfs_btree_assign_v() argument
2230 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax); in nilfs_btree_assign_v()
2231 ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index, in nilfs_btree_assign_v()
2239 key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index); in nilfs_btree_assign_v()
2255 int level, ret; in nilfs_btree_assign() local
2264 level = nilfs_btree_node_get_level(node); in nilfs_btree_assign()
2267 level = NILFS_BTREE_LEVEL_DATA; in nilfs_btree_assign()
2270 ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0); in nilfs_btree_assign()
2277 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) : in nilfs_btree_assign()
2278 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo); in nilfs_btree_assign()
2313 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level) in nilfs_btree_mark() argument
2324 ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0); in nilfs_btree_mark()