Lines Matching full:path
31 *root, struct btrfs_path *path, int level);
33 const struct btrfs_key *ins_key, struct btrfs_path *path,
146 /* this also releases the path */
156 * path release drops references on the extent buffers in the path
157 * and it drops any locks held by this path
847 * @path: Path holding nodes and locks
853 * that child to become the new root and freeing the old root node. The path
860 struct btrfs_root *root, struct btrfs_path *path, in promote_child_to_root() argument
892 path->locks[level] = 0; in promote_child_to_root()
893 path->nodes[level] = NULL; in promote_child_to_root()
896 /* Once for the path. */ in promote_child_to_root()
918 struct btrfs_path *path, int level) in balance_level() argument
928 int orig_slot = path->slots[level]; in balance_level()
933 mid = path->nodes[level]; in balance_level()
935 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK); in balance_level()
941 parent = path->nodes[level + 1]; in balance_level()
942 pslot = path->slots[level + 1]; in balance_level()
953 return promote_child_to_root(trans, root, path, level, mid); in balance_level()
1013 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot + 1); in balance_level()
1075 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot); in balance_level()
1103 /* update the path */ in balance_level()
1107 path->nodes[level] = left; in balance_level()
1108 path->slots[level + 1] -= 1; in balance_level()
1109 path->slots[level] = orig_slot; in balance_level()
1110 /* Left is now owned by path. */ in balance_level()
1118 path->slots[level] = orig_slot; in balance_level()
1123 btrfs_node_blockptr(path->nodes[level], path->slots[level])) in balance_level()
1143 struct btrfs_path *path, int level) in push_nodes_for_insert() argument
1153 int orig_slot = path->slots[level]; in push_nodes_for_insert()
1158 mid = path->nodes[level]; in push_nodes_for_insert()
1162 parent = path->nodes[level + 1]; in push_nodes_for_insert()
1163 pslot = path->slots[level + 1]; in push_nodes_for_insert()
1209 path->nodes[level] = left; in push_nodes_for_insert()
1210 path->slots[level + 1] -= 1; in push_nodes_for_insert()
1211 path->slots[level] = orig_slot; in push_nodes_for_insert()
1217 path->slots[level] = orig_slot; in push_nodes_for_insert()
1270 path->nodes[level] = right; in push_nodes_for_insert()
1271 path->slots[level + 1] += 1; in push_nodes_for_insert()
1272 path->slots[level] = orig_slot - in push_nodes_for_insert()
1293 const struct btrfs_path *path, in reada_for_search() argument
1307 if (level != 1 && path->reada != READA_FORWARD_ALWAYS) in reada_for_search()
1310 if (!path->nodes[level]) in reada_for_search()
1313 node = path->nodes[level]; in reada_for_search()
1320 if (path->reada == READA_FORWARD_ALWAYS) { in reada_for_search()
1331 if (path->reada != READA_FORWARD_ALWAYS) { in reada_for_search()
1347 if (path->reada == READA_BACK) { in reada_for_search()
1351 } else if (path->reada == READA_FORWARD || in reada_for_search()
1352 path->reada == READA_FORWARD_ALWAYS) { in reada_for_search()
1357 if (path->reada == READA_BACK && objectid) { in reada_for_search()
1363 if (path->reada == READA_FORWARD_ALWAYS || in reada_for_search()
1375 static noinline void reada_for_balance(const struct btrfs_path *path, int level) in reada_for_balance() argument
1381 parent = path->nodes[level + 1]; in reada_for_balance()
1386 slot = path->slots[level + 1]; in reada_for_balance()
1397 * in the tree. The exceptions are when our path goes through slot 0, because
1401 * callers might also have set path->keep_locks, which tells this code to keep
1402 * the lock if the path points to the last slot in the block. This is part of
1408 static noinline void unlock_up(struct btrfs_path *path, int level, in unlock_up() argument
1417 if (!path->nodes[i]) in unlock_up()
1419 if (!path->locks[i]) in unlock_up()
1423 if (path->slots[i] == 0) { in unlock_up()
1428 if (path->keep_locks) { in unlock_up()
1431 nritems = btrfs_header_nritems(path->nodes[i]); in unlock_up()
1432 if (nritems < 1 || path->slots[i] >= nritems - 1) { in unlock_up()
1440 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]); in unlock_up()
1442 path->locks[i] = 0; in unlock_up()
1458 * Returns -EAGAIN, with the path unlocked, if the caller needs to repeat the
1612 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1661 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path, in btrfs_find_item() argument
1669 ASSERT(path); in btrfs_find_item()
1676 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); in btrfs_find_item()
1680 eb = path->nodes[0]; in btrfs_find_item()
1681 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { in btrfs_find_item()
1682 ret = btrfs_next_leaf(fs_root, path); in btrfs_find_item()
1685 eb = path->nodes[0]; in btrfs_find_item()
1688 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); in btrfs_find_item()
1779 * Replace the extent buffer at the lowest level of the path with a cloned
1790 static int finish_need_commit_sem_search(struct btrfs_path *path) in finish_need_commit_sem_search() argument
1792 const int i = path->lowest_level; in finish_need_commit_sem_search()
1793 const int slot = path->slots[i]; in finish_need_commit_sem_search()
1794 struct extent_buffer *lowest = path->nodes[i]; in finish_need_commit_sem_search()
1797 ASSERT(path->need_commit_sem); in finish_need_commit_sem_search()
1808 btrfs_release_path(path); in finish_need_commit_sem_search()
1809 path->nodes[i] = clone; in finish_need_commit_sem_search()
1810 path->slots[i] = slot; in finish_need_commit_sem_search()
1839 struct btrfs_path *path, in search_leaf() argument
1843 struct extent_buffer *leaf = path->nodes[0]; in search_leaf()
1864 * !path->locks[1] means we have a single node tree, the leaf is in search_leaf()
1867 if (path->locks[1] && leaf_free_space >= ins_len) { in search_leaf()
1894 btrfs_unlock_up_safe(path, 1); in search_leaf()
1912 btrfs_unlock_up_safe(path, 1); in search_leaf()
1919 path->slots[0] = 0; in search_leaf()
1926 prev_cmp, &path->slots[0]); in search_leaf()
1941 if (ret == 0 && !path->search_for_extension) { in search_leaf()
1951 ret2 = split_leaf(trans, root, key, path, ins_len, (ret == 0)); in search_leaf()
1968 * @p: Holds all btree nodes along the search path
1986 * of the path (level 0)
1988 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2087 * then we don't want to set the path blocking, in btrfs_search_slot()
2259 * The resulting path and return value will be set up as if we called
2369 * This may release the path, and so you may lose any locks held at the
2372 static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) in btrfs_prev_leaf() argument
2379 btrfs_item_key_to_cpu(path->nodes[0], &key, 0); in btrfs_prev_leaf()
2395 btrfs_release_path(path); in btrfs_prev_leaf()
2396 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); in btrfs_prev_leaf()
2402 * before releasing the path and calling btrfs_search_slot(), we now may in btrfs_prev_leaf()
2404 * after we released the path, one of more items were moved from a in btrfs_prev_leaf()
2411 if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) { in btrfs_prev_leaf()
2412 btrfs_item_key(path->nodes[0], &found_key, path->slots[0]); in btrfs_prev_leaf()
2415 if (path->slots[0] > 0) { in btrfs_prev_leaf()
2416 path->slots[0]--; in btrfs_prev_leaf()
2427 btrfs_item_key(path->nodes[0], &found_key, 0); in btrfs_prev_leaf()
2431 * before we released our path. And after we released our path, that in btrfs_prev_leaf()
2469 * a return value of 1 means the path is at the position where the in btrfs_search_slot_for_read()
2471 * but in case the previous item is the last in a leaf, path points in btrfs_search_slot_for_read()
2528 struct btrfs_path *path) in btrfs_search_backwards() argument
2532 ret = btrfs_search_slot(NULL, root, key, path, 0, 0); in btrfs_search_backwards()
2534 ret = btrfs_previous_item(root, path, key->objectid, key->type); in btrfs_search_backwards()
2537 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]); in btrfs_search_backwards()
2543 * Search for a valid slot for the given path.
2547 * @path: The starting point to validate the slot.
2554 struct btrfs_path *path) in btrfs_get_next_valid_item() argument
2556 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { in btrfs_get_next_valid_item()
2559 ret = btrfs_next_leaf(root, path); in btrfs_get_next_valid_item()
2564 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]); in btrfs_get_next_valid_item()
2577 const struct btrfs_path *path, in fixup_low_keys() argument
2585 int tslot = path->slots[i]; in fixup_low_keys()
2587 if (!path->nodes[i]) in fixup_low_keys()
2589 t = path->nodes[i]; in fixup_low_keys()
2594 btrfs_mark_buffer_dirty(trans, path->nodes[i]); in fixup_low_keys()
2607 const struct btrfs_path *path, in btrfs_set_item_key_safe() argument
2615 eb = path->nodes[0]; in btrfs_set_item_key_safe()
2616 slot = path->slots[0]; in btrfs_set_item_key_safe()
2648 fixup_low_keys(trans, path, &disk_key, 1); in btrfs_set_item_key_safe()
2869 struct btrfs_path *path, int level) in insert_new_root() argument
2878 BUG_ON(path->nodes[level]); in insert_new_root()
2879 BUG_ON(path->nodes[level-1] != root->node); in insert_new_root()
2881 lower = path->nodes[level-1]; in insert_new_root()
2925 path->nodes[level] = c; in insert_new_root()
2926 path->locks[level] = BTRFS_WRITE_LOCK; in insert_new_root()
2927 path->slots[level] = 0; in insert_new_root()
2939 const struct btrfs_path *path, in insert_ptr() argument
2947 BUG_ON(!path->nodes[level]); in insert_ptr()
2948 btrfs_assert_tree_write_locked(path->nodes[level]); in insert_ptr()
2949 lower = path->nodes[level]; in insert_ptr()
2986 * split the node at the specified level in path in two.
2987 * The path is corrected to point to the appropriate node after the split
2996 struct btrfs_path *path, int level) in split_node() argument
3006 c = path->nodes[level]; in split_node()
3019 ret = insert_new_root(trans, root, path, level + 1); in split_node()
3023 ret = push_nodes_for_insert(trans, root, path, level); in split_node()
3024 c = path->nodes[level]; in split_node()
3062 ret = insert_ptr(trans, path, &disk_key, split->start, in split_node()
3063 path->slots[level + 1] + 1, level + 1); in split_node()
3070 if (path->slots[level] >= mid) { in split_node()
3071 path->slots[level] -= mid; in split_node()
3074 path->nodes[level] = split; in split_node()
3075 path->slots[level + 1] += 1; in split_node()
3130 struct btrfs_path *path, in __push_leaf_right() argument
3137 struct extent_buffer *left = path->nodes[0]; in __push_leaf_right()
3138 struct extent_buffer *upper = path->nodes[1]; in __push_leaf_right()
3154 if (path->slots[0] >= left_nritems) in __push_leaf_right()
3157 slot = path->slots[1]; in __push_leaf_right()
3161 if (path->slots[0] > i) in __push_leaf_right()
3163 if (path->slots[0] == i) { in __push_leaf_right()
3171 if (path->slots[0] == i) in __push_leaf_right()
3234 /* then fixup the leaf pointer in the path */ in __push_leaf_right()
3235 if (path->slots[0] >= left_nritems) { in __push_leaf_right()
3236 path->slots[0] -= left_nritems; in __push_leaf_right()
3239 path->nodes[0] = right; in __push_leaf_right()
3240 path->slots[1] += 1; in __push_leaf_right()
3254 * push some data in the path leaf to the right, trying to free up at
3264 *root, struct btrfs_path *path, in push_leaf_right() argument
3268 struct extent_buffer *left = path->nodes[0]; in push_leaf_right()
3276 if (!path->nodes[1]) in push_leaf_right()
3279 slot = path->slots[1]; in push_leaf_right()
3280 upper = path->nodes[1]; in push_leaf_right()
3284 btrfs_assert_tree_write_locked(path->nodes[1]); in push_leaf_right()
3312 if (path->slots[0] == left_nritems && !empty) { in push_leaf_right()
3319 path->nodes[0] = right; in push_leaf_right()
3320 path->slots[0] = 0; in push_leaf_right()
3321 path->slots[1]++; in push_leaf_right()
3325 return __push_leaf_right(trans, path, min_data_size, empty, right, in push_leaf_right()
3334 * push some data in the path leaf to the left, trying to free up at
3342 struct btrfs_path *path, int data_size, in __push_leaf_left() argument
3349 struct extent_buffer *right = path->nodes[0]; in __push_leaf_left()
3366 if (path->slots[0] < i) in __push_leaf_left()
3368 if (path->slots[0] == i) { in __push_leaf_left()
3376 if (path->slots[0] == i) in __push_leaf_left()
3450 fixup_low_keys(trans, path, &disk_key, 1); in __push_leaf_left()
3452 /* then fixup the leaf pointer in the path */ in __push_leaf_left()
3453 if (path->slots[0] < push_items) { in __push_leaf_left()
3454 path->slots[0] += old_left_nritems; in __push_leaf_left()
3457 path->nodes[0] = left; in __push_leaf_left()
3458 path->slots[1] -= 1; in __push_leaf_left()
3462 path->slots[0] -= push_items; in __push_leaf_left()
3464 BUG_ON(path->slots[0] < 0); in __push_leaf_left()
3473 * push some data in the path leaf to the left, trying to free up at
3481 *root, struct btrfs_path *path, int min_data_size, in push_leaf_left() argument
3484 struct extent_buffer *right = path->nodes[0]; in push_leaf_left()
3491 slot = path->slots[1]; in push_leaf_left()
3494 if (!path->nodes[1]) in push_leaf_left()
3501 btrfs_assert_tree_write_locked(path->nodes[1]); in push_leaf_left()
3503 left = btrfs_read_node_slot(path->nodes[1], slot - 1); in push_leaf_left()
3516 path->nodes[1], slot - 1, &left, in push_leaf_left()
3530 return __push_leaf_left(trans, path, min_data_size, empty, left, in push_leaf_left()
3539 * split the path's leaf in two, making sure there is at least data_size
3540 * available for the resulting leaf level of the path.
3543 struct btrfs_path *path, in copy_for_split() argument
3575 ret = insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1); in copy_for_split()
3581 BUG_ON(path->slots[0] != slot); in copy_for_split()
3584 btrfs_tree_unlock(path->nodes[0]); in copy_for_split()
3585 free_extent_buffer(path->nodes[0]); in copy_for_split()
3586 path->nodes[0] = right; in copy_for_split()
3587 path->slots[0] -= mid; in copy_for_split()
3588 path->slots[1] += 1; in copy_for_split()
3594 BUG_ON(path->slots[0] < 0); in copy_for_split()
3611 struct btrfs_path *path, in push_for_double_split() argument
3620 slot = path->slots[0]; in push_for_double_split()
3621 if (slot < btrfs_header_nritems(path->nodes[0])) in push_for_double_split()
3622 space_needed -= btrfs_leaf_free_space(path->nodes[0]); in push_for_double_split()
3628 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot); in push_for_double_split()
3635 nritems = btrfs_header_nritems(path->nodes[0]); in push_for_double_split()
3640 if (path->slots[0] == 0 || path->slots[0] == nritems) in push_for_double_split()
3643 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) in push_for_double_split()
3647 slot = path->slots[0]; in push_for_double_split()
3650 space_needed -= btrfs_leaf_free_space(path->nodes[0]); in push_for_double_split()
3651 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot); in push_for_double_split()
3664 * split the path's leaf in two, making sure there is at least data_size
3665 * available for the resulting leaf level of the path.
3672 struct btrfs_path *path, int data_size, in split_leaf() argument
3688 l = path->nodes[0]; in split_leaf()
3689 slot = path->slots[0]; in split_leaf()
3695 if (data_size && path->nodes[1]) { in split_leaf()
3701 wret = push_leaf_right(trans, root, path, space_needed, in split_leaf()
3709 wret = push_leaf_left(trans, root, path, space_needed, in split_leaf()
3714 l = path->nodes[0]; in split_leaf()
3721 if (!path->nodes[1]) { in split_leaf()
3722 ret = insert_new_root(trans, root, path, 1); in split_leaf()
3728 l = path->nodes[0]; in split_leaf()
3729 slot = path->slots[0]; in split_leaf()
3795 ret = insert_ptr(trans, path, &disk_key, in split_leaf()
3796 right->start, path->slots[1] + 1, 1); in split_leaf()
3802 btrfs_tree_unlock(path->nodes[0]); in split_leaf()
3803 free_extent_buffer(path->nodes[0]); in split_leaf()
3804 path->nodes[0] = right; in split_leaf()
3805 path->slots[0] = 0; in split_leaf()
3806 path->slots[1] += 1; in split_leaf()
3809 ret = insert_ptr(trans, path, &disk_key, in split_leaf()
3810 right->start, path->slots[1], 1); in split_leaf()
3816 btrfs_tree_unlock(path->nodes[0]); in split_leaf()
3817 free_extent_buffer(path->nodes[0]); in split_leaf()
3818 path->nodes[0] = right; in split_leaf()
3819 path->slots[0] = 0; in split_leaf()
3820 if (path->slots[1] == 0) in split_leaf()
3821 fixup_low_keys(trans, path, &disk_key, 1); in split_leaf()
3831 ret = copy_for_split(trans, path, l, right, slot, mid, nritems); in split_leaf()
3847 push_for_double_split(trans, root, path, data_size); in split_leaf()
3849 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) in split_leaf()
3856 struct btrfs_path *path, int ins_len) in setup_leaf_for_split() argument
3865 leaf = path->nodes[0]; in setup_leaf_for_split()
3866 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in setup_leaf_for_split()
3875 item_size = btrfs_item_size(leaf, path->slots[0]); in setup_leaf_for_split()
3877 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3881 btrfs_release_path(path); in setup_leaf_for_split()
3883 path->keep_locks = true; in setup_leaf_for_split()
3884 path->search_for_split = true; in setup_leaf_for_split()
3885 ret = btrfs_search_slot(trans, root, &key, path, 0, 1); in setup_leaf_for_split()
3886 path->search_for_split = false; in setup_leaf_for_split()
3893 leaf = path->nodes[0]; in setup_leaf_for_split()
3895 if (item_size != btrfs_item_size(leaf, path->slots[0])) in setup_leaf_for_split()
3899 if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len) in setup_leaf_for_split()
3903 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3909 ret = split_leaf(trans, root, &key, path, ins_len, true); in setup_leaf_for_split()
3913 path->keep_locks = false; in setup_leaf_for_split()
3914 btrfs_unlock_up_safe(path, 1); in setup_leaf_for_split()
3917 path->keep_locks = false; in setup_leaf_for_split()
3922 struct btrfs_path *path, in split_item() argument
3934 leaf = path->nodes[0]; in split_item()
3942 orig_slot = path->slots[0]; in split_item()
3943 orig_offset = btrfs_item_offset(leaf, path->slots[0]); in split_item()
3944 item_size = btrfs_item_size(leaf, path->slots[0]); in split_item()
3951 path->slots[0]), item_size); in split_item()
3953 slot = path->slots[0] + 1; in split_item()
3974 btrfs_item_ptr_offset(leaf, path->slots[0]), in split_item()
3993 * The path may be released by this operation. After
3994 * the split, the path is pointing to the old item. The
4005 struct btrfs_path *path, in btrfs_split_item() argument
4010 ret = setup_leaf_for_split(trans, root, path, in btrfs_split_item()
4015 return split_item(trans, path, new_key, split_offset); in btrfs_split_item()
4019 * make the item pointed to by the path smaller. new_size indicates
4025 const struct btrfs_path *path, u32 new_size, int from_end) in btrfs_truncate_item() argument
4036 leaf = path->nodes[0]; in btrfs_truncate_item()
4037 slot = path->slots[0]; in btrfs_truncate_item()
4099 fixup_low_keys(trans, path, &disk_key, 1); in btrfs_truncate_item()
4112 * make the item pointed to by the path bigger, data_size is the added size.
4115 const struct btrfs_path *path, u32 data_size) in btrfs_extend_item() argument
4125 leaf = path->nodes[0]; in btrfs_extend_item()
4134 slot = path->slots[0]; in btrfs_extend_item()
4175 * @path: points to the leaf/slot where we are going to insert new items
4182 struct btrfs_root *root, struct btrfs_path *path, in setup_items_for_insert() argument
4199 if (path->slots[0] == 0) { in setup_items_for_insert()
4201 fixup_low_keys(trans, path, &disk_key, 1); in setup_items_for_insert()
4203 btrfs_unlock_up_safe(path, 1); in setup_items_for_insert()
4205 leaf = path->nodes[0]; in setup_items_for_insert()
4206 slot = path->slots[0]; in setup_items_for_insert()
4272 * @path: A path pointing to the target leaf and slot.
4278 struct btrfs_path *path, in btrfs_setup_item_for_insert() argument
4289 setup_items_for_insert(trans, root, path, &batch); in btrfs_setup_item_for_insert()
4294 * This does all the path init required, making room in the tree if needed.
4302 struct btrfs_path *path, in btrfs_insert_empty_items() argument
4310 ret = btrfs_search_slot(trans, root, &batch->keys[0], path, total_size, 1); in btrfs_insert_empty_items()
4316 slot = path->slots[0]; in btrfs_insert_empty_items()
4319 setup_items_for_insert(trans, root, path, batch); in btrfs_insert_empty_items()
4325 * This does all the path init required, making room in the tree if needed.
4332 BTRFS_PATH_AUTO_FREE(path); in btrfs_insert_item()
4336 path = btrfs_alloc_path(); in btrfs_insert_item()
4337 if (!path) in btrfs_insert_item()
4339 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); in btrfs_insert_item()
4341 leaf = path->nodes[0]; in btrfs_insert_item()
4342 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in btrfs_insert_item()
4359 struct btrfs_path *path, in btrfs_duplicate_item() argument
4366 leaf = path->nodes[0]; in btrfs_duplicate_item()
4367 item_size = btrfs_item_size(leaf, path->slots[0]); in btrfs_duplicate_item()
4368 ret = setup_leaf_for_split(trans, root, path, in btrfs_duplicate_item()
4373 path->slots[0]++; in btrfs_duplicate_item()
4374 btrfs_setup_item_for_insert(trans, root, path, new_key, item_size); in btrfs_duplicate_item()
4375 leaf = path->nodes[0]; in btrfs_duplicate_item()
4377 btrfs_item_ptr_offset(leaf, path->slots[0]), in btrfs_duplicate_item()
4378 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), in btrfs_duplicate_item()
4392 struct btrfs_path *path, int level, int slot) in btrfs_del_ptr() argument
4394 struct extent_buffer *parent = path->nodes[level]; in btrfs_del_ptr()
4432 fixup_low_keys(trans, path, &disk_key, level + 1); in btrfs_del_ptr()
4439 * a helper function to delete the leaf pointed to by path->slots[1] and
4440 * path->nodes[1].
4442 * This deletes the pointer in path->nodes[1] and frees the leaf
4445 * The path must have already been setup for deleting the leaf, including
4446 * all the proper balancing. path->nodes[1] must be locked.
4450 struct btrfs_path *path, in btrfs_del_leaf() argument
4456 ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]); in btrfs_del_leaf()
4464 btrfs_unlock_up_safe(path, 0); in btrfs_del_leaf()
4477 * delete the item at the leaf level in path. If that empties
4481 struct btrfs_path *path, int slot, int nr) in btrfs_del_items() argument
4489 leaf = path->nodes[0]; in btrfs_del_items()
4520 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4530 fixup_low_keys(trans, path, &disk_key, 1); in btrfs_del_items()
4544 /* push_leaf_left fixes the path. in btrfs_del_items()
4545 * make sure the path still points to our leaf in btrfs_del_items()
4548 slot = path->slots[1]; in btrfs_del_items()
4556 wret = push_leaf_left(trans, root, path, 0, in btrfs_del_items()
4561 if (path->nodes[0] == leaf && in btrfs_del_items()
4575 wret = push_leaf_right(trans, root, path, 0, in btrfs_del_items()
4582 path->slots[1] = slot; in btrfs_del_items()
4583 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4588 /* if we're still in the path, make sure in btrfs_del_items()
4593 if (path->nodes[0] == leaf) in btrfs_del_items()
4611 * key and get a writable path.
4621 struct btrfs_path *path, in btrfs_search_forward() argument
4630 const bool keep_locks = path->keep_locks; in btrfs_search_forward()
4632 ASSERT(!path->nowait); in btrfs_search_forward()
4633 ASSERT(path->lowest_level == 0); in btrfs_search_forward()
4634 path->keep_locks = true; in btrfs_search_forward()
4638 WARN_ON(path->nodes[level]); in btrfs_search_forward()
4639 path->nodes[level] = cur; in btrfs_search_forward()
4640 path->locks[level] = BTRFS_READ_LOCK; in btrfs_search_forward()
4655 /* At level 0 we're done, setup the path and exit. */ in btrfs_search_forward()
4660 path->slots[level] = slot; in btrfs_search_forward()
4686 path->slots[level] = slot; in btrfs_search_forward()
4688 sret = btrfs_find_next_key(root, path, min_key, level, in btrfs_search_forward()
4691 btrfs_release_path(path); in btrfs_search_forward()
4705 path->locks[level - 1] = BTRFS_READ_LOCK; in btrfs_search_forward()
4706 path->nodes[level - 1] = cur; in btrfs_search_forward()
4707 unlock_up(path, level, 1, 0, NULL); in btrfs_search_forward()
4710 path->keep_locks = keep_locks; in btrfs_search_forward()
4712 btrfs_unlock_up_safe(path, 1); in btrfs_search_forward()
4718 * and fixup the path. It looks for and returns the next key in the
4719 * tree based on the current path and the min_trans parameters.
4724 * path->keep_locks should be set to true on the search made before
4727 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, in btrfs_find_next_key() argument
4733 WARN_ON(!path->keep_locks && !path->skip_locking); in btrfs_find_next_key()
4735 if (!path->nodes[level]) in btrfs_find_next_key()
4738 slot = path->slots[level] + 1; in btrfs_find_next_key()
4739 c = path->nodes[level]; in btrfs_find_next_key()
4746 !path->nodes[level + 1]) in btrfs_find_next_key()
4749 if (path->locks[level + 1] || path->skip_locking) { in btrfs_find_next_key()
4760 orig_lowest = path->lowest_level; in btrfs_find_next_key()
4761 btrfs_release_path(path); in btrfs_find_next_key()
4762 path->lowest_level = level; in btrfs_find_next_key()
4763 ret = btrfs_search_slot(NULL, root, &cur_key, path, in btrfs_find_next_key()
4765 path->lowest_level = orig_lowest; in btrfs_find_next_key()
4769 c = path->nodes[level]; in btrfs_find_next_key()
4770 slot = path->slots[level]; in btrfs_find_next_key()
4792 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path, in btrfs_next_old_leaf() argument
4812 ASSERT(!path->nowait); in btrfs_next_old_leaf()
4814 nritems = btrfs_header_nritems(path->nodes[0]); in btrfs_next_old_leaf()
4818 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); in btrfs_next_old_leaf()
4827 btrfs_release_path(path); in btrfs_next_old_leaf()
4829 path->keep_locks = true; in btrfs_next_old_leaf()
4832 ret = btrfs_search_old_slot(root, &key, path, time_seq); in btrfs_next_old_leaf()
4834 if (path->need_commit_sem) { in btrfs_next_old_leaf()
4835 path->need_commit_sem = false; in btrfs_next_old_leaf()
4837 if (path->nowait) { in btrfs_next_old_leaf()
4846 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); in btrfs_next_old_leaf()
4848 path->keep_locks = false; in btrfs_next_old_leaf()
4853 nritems = btrfs_header_nritems(path->nodes[0]); in btrfs_next_old_leaf()
4855 * By releasing the path above we dropped all our locks. A balance in btrfs_next_old_leaf()
4861 * So, check again here and advance the path if there are now more in btrfs_next_old_leaf()
4864 if (nritems > 0 && path->slots[0] <= nritems - 1) { in btrfs_next_old_leaf()
4865 if (ret == 0 && path->slots[0] != nritems - 1) { in btrfs_next_old_leaf()
4866 path->slots[0]++; in btrfs_next_old_leaf()
4875 if (!path->nodes[level]) { in btrfs_next_old_leaf()
4880 slot = path->slots[level] + 1; in btrfs_next_old_leaf()
4881 c = path->nodes[level]; in btrfs_next_old_leaf()
4898 if (path->locks[level]) { in btrfs_next_old_leaf()
4899 btrfs_tree_read_unlock(path->nodes[i]); in btrfs_next_old_leaf()
4900 path->locks[i] = 0; in btrfs_next_old_leaf()
4902 free_extent_buffer(path->nodes[i]); in btrfs_next_old_leaf()
4903 path->nodes[i] = NULL; in btrfs_next_old_leaf()
4907 ret = read_block_for_search(root, path, &pa, &next, slot, &key); in btrfs_next_old_leaf()
4908 if (ret == -EAGAIN && !path->nowait) in btrfs_next_old_leaf()
4912 btrfs_release_path(path); in btrfs_next_old_leaf()
4916 if (!path->skip_locking) { in btrfs_next_old_leaf()
4918 if (!ret && path->nowait) { in btrfs_next_old_leaf()
4931 btrfs_release_path(path); in btrfs_next_old_leaf()
4940 path->slots[level] = slot; in btrfs_next_old_leaf()
4943 path->nodes[level] = next; in btrfs_next_old_leaf()
4944 path->slots[level] = 0; in btrfs_next_old_leaf()
4945 if (!path->skip_locking) in btrfs_next_old_leaf()
4946 path->locks[level] = BTRFS_READ_LOCK; in btrfs_next_old_leaf()
4950 ret = read_block_for_search(root, path, &pa, &next, 0, &key); in btrfs_next_old_leaf()
4951 if (ret == -EAGAIN && !path->nowait) in btrfs_next_old_leaf()
4955 btrfs_release_path(path); in btrfs_next_old_leaf()
4959 if (!path->skip_locking) { in btrfs_next_old_leaf()
4960 if (path->nowait) { in btrfs_next_old_leaf()
4972 unlock_up(path, 0, 1, 0, NULL); in btrfs_next_old_leaf()
4976 path->need_commit_sem = true; in btrfs_next_old_leaf()
4977 ret2 = finish_need_commit_sem_search(path); in btrfs_next_old_leaf()
4988 int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq) in btrfs_next_old_item() argument
4990 path->slots[0]++; in btrfs_next_old_item()
4991 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) in btrfs_next_old_item()
4992 return btrfs_next_old_leaf(root, path, time_seq); in btrfs_next_old_item()
5003 struct btrfs_path *path, u64 min_objectid, in btrfs_previous_item() argument
5012 if (path->slots[0] == 0) { in btrfs_previous_item()
5013 ret = btrfs_prev_leaf(root, path); in btrfs_previous_item()
5017 path->slots[0]--; in btrfs_previous_item()
5019 leaf = path->nodes[0]; in btrfs_previous_item()
5023 if (path->slots[0] == nritems) in btrfs_previous_item()
5024 path->slots[0]--; in btrfs_previous_item()
5026 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_item()
5045 struct btrfs_path *path, u64 min_objectid) in btrfs_previous_extent_item() argument
5053 if (path->slots[0] == 0) { in btrfs_previous_extent_item()
5054 ret = btrfs_prev_leaf(root, path); in btrfs_previous_extent_item()
5058 path->slots[0]--; in btrfs_previous_extent_item()
5060 leaf = path->nodes[0]; in btrfs_previous_extent_item()
5064 if (path->slots[0] == nritems) in btrfs_previous_extent_item()
5065 path->slots[0]--; in btrfs_previous_extent_item()
5067 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_extent_item()