Lines Matching refs:path
30 *root, struct btrfs_path *path, int level);
32 const struct btrfs_key *ins_key, struct btrfs_path *path,
196 /* this also releases the path */
206 * path release drops references on the extent buffers in the path
207 * and it drops any locks held by this path
1043 struct btrfs_path *path, int level)
1053 int orig_slot = path->slots[level];
1058 mid = path->nodes[level];
1060 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK);
1066 parent = path->nodes[level + 1];
1067 pslot = path->slots[level + 1];
1108 path->locks[level] = 0;
1109 path->nodes[level] = NULL;
1112 /* once for the path */
1179 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot + 1);
1237 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot);
1261 /* update the path */
1266 path->nodes[level] = left;
1267 path->slots[level + 1] -= 1;
1268 path->slots[level] = orig_slot;
1275 path->slots[level] = orig_slot;
1280 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1288 if (path->nodes[level] != left)
1301 struct btrfs_path *path, int level)
1311 int orig_slot = path->slots[level];
1316 mid = path->nodes[level];
1320 parent = path->nodes[level + 1];
1321 pslot = path->slots[level + 1];
1367 path->nodes[level] = left;
1368 path->slots[level + 1] -= 1;
1369 path->slots[level] = orig_slot;
1375 path->slots[level] = orig_slot;
1428 path->nodes[level] = right;
1429 path->slots[level + 1] += 1;
1430 path->slots[level] = orig_slot -
1451 struct btrfs_path *path,
1465 if (level != 1 && path->reada != READA_FORWARD_ALWAYS)
1468 if (!path->nodes[level])
1471 node = path->nodes[level];
1478 if (path->reada == READA_FORWARD_ALWAYS) {
1489 if (path->reada != READA_FORWARD_ALWAYS) {
1505 if (path->reada == READA_BACK) {
1509 } else if (path->reada == READA_FORWARD ||
1510 path->reada == READA_FORWARD_ALWAYS) {
1515 if (path->reada == READA_BACK && objectid) {
1521 if (path->reada == READA_FORWARD_ALWAYS ||
1533 static noinline void reada_for_balance(struct btrfs_path *path, int level)
1539 parent = path->nodes[level + 1];
1544 slot = path->slots[level + 1];
1555 * in the tree. The exceptions are when our path goes through slot 0, because
1559 * callers might also have set path->keep_locks, which tells this code to keep
1560 * the lock if the path points to the last slot in the block. This is part of
1566 static noinline void unlock_up(struct btrfs_path *path, int level,
1575 if (!path->nodes[i])
1577 if (!path->locks[i])
1581 if (path->slots[i] == 0) {
1586 if (path->keep_locks) {
1589 nritems = btrfs_header_nritems(path->nodes[i]);
1590 if (nritems < 1 || path->slots[i] >= nritems - 1) {
1599 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);
1600 path->locks[i] = 0;
1616 * Returns -EAGAIN, with the path unlocked, if the caller needs to repeat the
1741 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1790 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
1798 ASSERT(path);
1805 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
1809 eb = path->nodes[0];
1810 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
1811 ret = btrfs_next_leaf(fs_root, path);
1814 eb = path->nodes[0];
1817 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
1908 * Replace the extent buffer at the lowest level of the path with a cloned
1919 static int finish_need_commit_sem_search(struct btrfs_path *path)
1921 const int i = path->lowest_level;
1922 const int slot = path->slots[i];
1923 struct extent_buffer *lowest = path->nodes[i];
1926 ASSERT(path->need_commit_sem);
1937 btrfs_release_path(path);
1938 path->nodes[i] = clone;
1939 path->slots[i] = slot;
1968 struct btrfs_path *path,
1972 struct extent_buffer *leaf = path->nodes[0];
1993 * !path->locks[1] means we have a single node tree, the leaf is
1996 if (path->locks[1] && leaf_free_space >= ins_len) {
2023 btrfs_unlock_up_safe(path, 1);
2041 btrfs_unlock_up_safe(path, 1);
2048 path->slots[0] = 0;
2055 prev_cmp, &path->slots[0]);
2070 if (ret == 0 && !path->search_for_extension) {
2080 err = split_leaf(trans, root, key, path, ins_len,
2098 * @p: Holds all btree nodes along the search path
2116 * of the path (level 0)
2118 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2207 * then we don't want to set the path blocking,
2372 * The resulting path and return value will be set up as if we called
2474 * This may release the path, and so you may lose any locks held at the
2477 static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2484 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
2500 btrfs_release_path(path);
2501 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2507 * before releasing the path and calling btrfs_search_slot(), we now may
2509 * after we released the path, one of more items were moved from a
2516 if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
2517 btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
2520 if (path->slots[0] > 0) {
2521 path->slots[0]--;
2532 btrfs_item_key(path->nodes[0], &found_key, 0);
2536 * before we released our path. And after we released our path, that
2574 * a return value of 1 means the path is at the position where the
2576 * but in case the previous item is the last in a leaf, path points
2633 struct btrfs_path *path)
2637 ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
2639 ret = btrfs_previous_item(root, path, key->objectid, key->type);
2642 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]);
2648 * Search for a valid slot for the given path.
2652 * @path: The starting point to validate the slot.
2659 struct btrfs_path *path)
2661 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
2664 ret = btrfs_next_leaf(root, path);
2669 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]);
2682 struct btrfs_path *path,
2690 int tslot = path->slots[i];
2692 if (!path->nodes[i])
2694 t = path->nodes[i];
2699 btrfs_mark_buffer_dirty(trans, path->nodes[i]);
2712 struct btrfs_path *path,
2720 eb = path->nodes[0];
2721 slot = path->slots[0];
2755 fixup_low_keys(trans, path, &disk_key, 1);
2977 struct btrfs_path *path, int level)
2987 BUG_ON(path->nodes[level]);
2988 BUG_ON(path->nodes[level-1] != root->node);
2990 lower = path->nodes[level-1];
3029 path->nodes[level] = c;
3030 path->locks[level] = BTRFS_WRITE_LOCK;
3031 path->slots[level] = 0;
3043 struct btrfs_path *path,
3051 BUG_ON(!path->nodes[level]);
3052 btrfs_assert_tree_write_locked(path->nodes[level]);
3053 lower = path->nodes[level];
3090 * split the node at the specified level in path in two.
3091 * The path is corrected to point to the appropriate node after the split
3100 struct btrfs_path *path, int level)
3110 c = path->nodes[level];
3123 ret = insert_new_root(trans, root, path, level + 1);
3127 ret = push_nodes_for_insert(trans, root, path, level);
3128 c = path->nodes[level];
3166 ret = insert_ptr(trans, path, &disk_key, split->start,
3167 path->slots[level + 1] + 1, level + 1);
3174 if (path->slots[level] >= mid) {
3175 path->slots[level] -= mid;
3178 path->nodes[level] = split;
3179 path->slots[level + 1] += 1;
3234 struct btrfs_path *path,
3241 struct extent_buffer *left = path->nodes[0];
3242 struct extent_buffer *upper = path->nodes[1];
3259 if (path->slots[0] >= left_nritems)
3262 slot = path->slots[1];
3266 if (path->slots[0] > i)
3268 if (path->slots[0] == i) {
3276 if (path->slots[0] == i)
3340 /* then fixup the leaf pointer in the path */
3341 if (path->slots[0] >= left_nritems) {
3342 path->slots[0] -= left_nritems;
3343 if (btrfs_header_nritems(path->nodes[0]) == 0)
3344 btrfs_clear_buffer_dirty(trans, path->nodes[0]);
3345 btrfs_tree_unlock(path->nodes[0]);
3346 free_extent_buffer(path->nodes[0]);
3347 path->nodes[0] = right;
3348 path->slots[1] += 1;
3362 * push some data in the path leaf to the right, trying to free up at
3372 *root, struct btrfs_path *path,
3376 struct extent_buffer *left = path->nodes[0];
3384 if (!path->nodes[1])
3387 slot = path->slots[1];
3388 upper = path->nodes[1];
3392 btrfs_assert_tree_write_locked(path->nodes[1]);
3420 if (path->slots[0] == left_nritems && !empty) {
3427 path->nodes[0] = right;
3428 path->slots[0] = 0;
3429 path->slots[1]++;
3433 return __push_leaf_right(trans, path, min_data_size, empty, right,
3442 * push some data in the path leaf to the left, trying to free up at
3450 struct btrfs_path *path, int data_size,
3457 struct extent_buffer *right = path->nodes[0];
3475 if (path->slots[0] < i)
3477 if (path->slots[0] == i) {
3485 if (path->slots[0] == i)
3557 fixup_low_keys(trans, path, &disk_key, 1);
3559 /* then fixup the leaf pointer in the path */
3560 if (path->slots[0] < push_items) {
3561 path->slots[0] += old_left_nritems;
3562 btrfs_tree_unlock(path->nodes[0]);
3563 free_extent_buffer(path->nodes[0]);
3564 path->nodes[0] = left;
3565 path->slots[1] -= 1;
3569 path->slots[0] -= push_items;
3571 BUG_ON(path->slots[0] < 0);
3580 * push some data in the path leaf to the left, trying to free up at
3588 *root, struct btrfs_path *path, int min_data_size,
3591 struct extent_buffer *right = path->nodes[0];
3598 slot = path->slots[1];
3601 if (!path->nodes[1])
3608 btrfs_assert_tree_write_locked(path->nodes[1]);
3610 left = btrfs_read_node_slot(path->nodes[1], slot - 1);
3623 path->nodes[1], slot - 1, &left,
3637 return __push_leaf_left(trans, path, min_data_size, empty, left,
3646 * split the path's leaf in two, making sure there is at least data_size
3647 * available for the resulting leaf level of the path.
3650 struct btrfs_path *path,
3684 ret = insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
3690 BUG_ON(path->slots[0] != slot);
3693 btrfs_tree_unlock(path->nodes[0]);
3694 free_extent_buffer(path->nodes[0]);
3695 path->nodes[0] = right;
3696 path->slots[0] -= mid;
3697 path->slots[1] += 1;
3703 BUG_ON(path->slots[0] < 0);
3720 struct btrfs_path *path,
3729 slot = path->slots[0];
3730 if (slot < btrfs_header_nritems(path->nodes[0]))
3731 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
3737 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
3744 nritems = btrfs_header_nritems(path->nodes[0]);
3749 if (path->slots[0] == 0 || path->slots[0] == nritems)
3752 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
3756 slot = path->slots[0];
3759 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
3760 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
3773 * split the path's leaf in two, making sure there is at least data_size
3774 * available for the resulting leaf level of the path.
3781 struct btrfs_path *path, int data_size,
3797 l = path->nodes[0];
3798 slot = path->slots[0];
3804 if (data_size && path->nodes[1]) {
3810 wret = push_leaf_right(trans, root, path, space_needed,
3818 wret = push_leaf_left(trans, root, path, space_needed,
3823 l = path->nodes[0];
3830 if (!path->nodes[1]) {
3831 ret = insert_new_root(trans, root, path, 1);
3837 l = path->nodes[0];
3838 slot = path->slots[0];
3904 ret = insert_ptr(trans, path, &disk_key,
3905 right->start, path->slots[1] + 1, 1);
3911 btrfs_tree_unlock(path->nodes[0]);
3912 free_extent_buffer(path->nodes[0]);
3913 path->nodes[0] = right;
3914 path->slots[0] = 0;
3915 path->slots[1] += 1;
3918 ret = insert_ptr(trans, path, &disk_key,
3919 right->start, path->slots[1], 1);
3925 btrfs_tree_unlock(path->nodes[0]);
3926 free_extent_buffer(path->nodes[0]);
3927 path->nodes[0] = right;
3928 path->slots[0] = 0;
3929 if (path->slots[1] == 0)
3930 fixup_low_keys(trans, path, &disk_key, 1);
3940 ret = copy_for_split(trans, path, l, right, slot, mid, nritems);
3956 push_for_double_split(trans, root, path, data_size);
3958 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
3965 struct btrfs_path *path, int ins_len)
3974 leaf = path->nodes[0];
3975 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3983 item_size = btrfs_item_size(leaf, path->slots[0]);
3985 fi = btrfs_item_ptr(leaf, path->slots[0],
3989 btrfs_release_path(path);
3991 path->keep_locks = 1;
3992 path->search_for_split = 1;
3993 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3994 path->search_for_split = 0;
4001 leaf = path->nodes[0];
4003 if (item_size != btrfs_item_size(leaf, path->slots[0]))
4007 if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len)
4011 fi = btrfs_item_ptr(leaf, path->slots[0],
4017 ret = split_leaf(trans, root, &key, path, ins_len, 1);
4021 path->keep_locks = 0;
4022 btrfs_unlock_up_safe(path, 1);
4025 path->keep_locks = 0;
4030 struct btrfs_path *path,
4042 leaf = path->nodes[0];
4050 orig_slot = path->slots[0];
4051 orig_offset = btrfs_item_offset(leaf, path->slots[0]);
4052 item_size = btrfs_item_size(leaf, path->slots[0]);
4059 path->slots[0]), item_size);
4061 slot = path->slots[0] + 1;
4082 btrfs_item_ptr_offset(leaf, path->slots[0]),
4101 * The path may be released by this operation. After
4102 * the split, the path is pointing to the old item. The
4113 struct btrfs_path *path,
4118 ret = setup_leaf_for_split(trans, root, path,
4123 ret = split_item(trans, path, new_key, split_offset);
4128 * make the item pointed to by the path smaller. new_size indicates
4134 struct btrfs_path *path, u32 new_size, int from_end)
4146 leaf = path->nodes[0];
4147 slot = path->slots[0];
4210 fixup_low_keys(trans, path, &disk_key, 1);
4223 * make the item pointed to by the path bigger, data_size is the added size.
4226 struct btrfs_path *path, u32 data_size)
4237 leaf = path->nodes[0];
4246 slot = path->slots[0];
4289 * @path: points to the leaf/slot where we are going to insert new items
4296 struct btrfs_root *root, struct btrfs_path *path,
4314 if (path->slots[0] == 0) {
4316 fixup_low_keys(trans, path, &disk_key, 1);
4318 btrfs_unlock_up_safe(path, 1);
4320 leaf = path->nodes[0];
4321 slot = path->slots[0];
4388 * @path: A path pointing to the target leaf and slot.
4394 struct btrfs_path *path,
4405 setup_items_for_insert(trans, root, path, &batch);
4410 * This does all the path init required, making room in the tree if needed.
4414 struct btrfs_path *path,
4422 ret = btrfs_search_slot(trans, root, &batch->keys[0], path, total_size, 1);
4428 slot = path->slots[0];
4431 setup_items_for_insert(trans, root, path, batch);
4437 * This does all the path init required, making room in the tree if needed.
4444 struct btrfs_path *path;
4448 path = btrfs_alloc_path();
4449 if (!path)
4451 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
4453 leaf = path->nodes[0];
4454 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4458 btrfs_free_path(path);
4472 struct btrfs_path *path,
4479 leaf = path->nodes[0];
4480 item_size = btrfs_item_size(leaf, path->slots[0]);
4481 ret = setup_leaf_for_split(trans, root, path,
4486 path->slots[0]++;
4487 btrfs_setup_item_for_insert(trans, root, path, new_key, item_size);
4488 leaf = path->nodes[0];
4490 btrfs_item_ptr_offset(leaf, path->slots[0]),
4491 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4505 struct btrfs_path *path, int level, int slot)
4507 struct extent_buffer *parent = path->nodes[level];
4545 fixup_low_keys(trans, path, &disk_key, level + 1);
4552 * a helper function to delete the leaf pointed to by path->slots[1] and
4553 * path->nodes[1].
4555 * This deletes the pointer in path->nodes[1] and frees the leaf
4558 * The path must have already been setup for deleting the leaf, including
4559 * all the proper balancing. path->nodes[1] must be locked.
4563 struct btrfs_path *path,
4569 ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]);
4577 btrfs_unlock_up_safe(path, 0);
4587 * delete the item at the leaf level in path. If that empties
4591 struct btrfs_path *path, int slot, int nr)
4599 leaf = path->nodes[0];
4634 ret = btrfs_del_leaf(trans, root, path, leaf);
4644 fixup_low_keys(trans, path, &disk_key, 1);
4658 /* push_leaf_left fixes the path.
4659 * make sure the path still points to our leaf
4662 slot = path->slots[1];
4670 wret = push_leaf_left(trans, root, path, 0,
4675 if (path->nodes[0] == leaf &&
4689 wret = push_leaf_right(trans, root, path, 0,
4696 path->slots[1] = slot;
4697 ret = btrfs_del_leaf(trans, root, path, leaf);
4703 /* if we're still in the path, make sure
4708 if (path->nodes[0] == leaf)
4726 * key and get a writable path.
4728 * This honors path->lowest_level to prevent descent past a given level
4739 struct btrfs_path *path,
4749 int keep_locks = path->keep_locks;
4751 ASSERT(!path->nowait);
4752 path->keep_locks = 1;
4756 WARN_ON(path->nodes[level]);
4757 path->nodes[level] = cur;
4758 path->locks[level] = BTRFS_READ_LOCK;
4773 /* at the lowest level, we're done, setup the path and exit */
4774 if (level == path->lowest_level) {
4778 path->slots[level] = slot;
4804 path->slots[level] = slot;
4805 sret = btrfs_find_next_key(root, path, min_key, level,
4808 btrfs_release_path(path);
4816 path->slots[level] = slot;
4817 if (level == path->lowest_level) {
4829 path->locks[level - 1] = BTRFS_READ_LOCK;
4830 path->nodes[level - 1] = cur;
4831 unlock_up(path, level, 1, 0, NULL);
4834 path->keep_locks = keep_locks;
4836 btrfs_unlock_up_safe(path, path->lowest_level + 1);
4844 * and fixup the path. It looks for and returns the next key in the
4845 * tree based on the current path and the min_trans parameters.
4850 * path->keep_locks should be set to 1 on the search made before
4853 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
4859 WARN_ON(!path->keep_locks && !path->skip_locking);
4861 if (!path->nodes[level])
4864 slot = path->slots[level] + 1;
4865 c = path->nodes[level];
4872 !path->nodes[level + 1])
4875 if (path->locks[level + 1] || path->skip_locking) {
4886 orig_lowest = path->lowest_level;
4887 btrfs_release_path(path);
4888 path->lowest_level = level;
4889 ret = btrfs_search_slot(NULL, root, &cur_key, path,
4891 path->lowest_level = orig_lowest;
4895 c = path->nodes[level];
4896 slot = path->slots[level];
4918 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
4937 ASSERT(!path->nowait);
4939 nritems = btrfs_header_nritems(path->nodes[0]);
4943 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4947 btrfs_release_path(path);
4949 path->keep_locks = 1;
4952 ret = btrfs_search_old_slot(root, &key, path, time_seq);
4954 if (path->need_commit_sem) {
4955 path->need_commit_sem = 0;
4957 if (path->nowait) {
4966 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4968 path->keep_locks = 0;
4973 nritems = btrfs_header_nritems(path->nodes[0]);
4975 * by releasing the path above we dropped all our locks. A balance
4978 * advance the path if there are now more items available.
4980 if (nritems > 0 && path->slots[0] < nritems - 1) {
4982 path->slots[0]++;
4988 * - after releasing the path above, someone has removed the item that
4996 * with ret > 0, the key isn't found, the path points to the slot
4997 * where it should be inserted, so the path->slots[0] item must be the
5000 if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) {
5006 if (!path->nodes[level]) {
5011 slot = path->slots[level] + 1;
5012 c = path->nodes[level];
5029 if (path->locks[level]) {
5030 btrfs_tree_read_unlock(path->nodes[i]);
5031 path->locks[i] = 0;
5033 free_extent_buffer(path->nodes[i]);
5034 path->nodes[i] = NULL;
5038 ret = read_block_for_search(root, path, &next, level,
5040 if (ret == -EAGAIN && !path->nowait)
5044 btrfs_release_path(path);
5048 if (!path->skip_locking) {
5050 if (!ret && path->nowait) {
5063 btrfs_release_path(path);
5072 path->slots[level] = slot;
5075 path->nodes[level] = next;
5076 path->slots[level] = 0;
5077 if (!path->skip_locking)
5078 path->locks[level] = BTRFS_READ_LOCK;
5082 ret = read_block_for_search(root, path, &next, level,
5084 if (ret == -EAGAIN && !path->nowait)
5088 btrfs_release_path(path);
5092 if (!path->skip_locking) {
5093 if (path->nowait) {
5105 unlock_up(path, 0, 1, 0, NULL);
5109 path->need_commit_sem = 1;
5110 ret2 = finish_need_commit_sem_search(path);
5119 int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq)
5121 path->slots[0]++;
5122 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0]))
5123 return btrfs_next_old_leaf(root, path, time_seq);
5134 struct btrfs_path *path, u64 min_objectid,
5143 if (path->slots[0] == 0) {
5144 ret = btrfs_prev_leaf(root, path);
5148 path->slots[0]--;
5150 leaf = path->nodes[0];
5154 if (path->slots[0] == nritems)
5155 path->slots[0]--;
5157 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5176 struct btrfs_path *path, u64 min_objectid)
5184 if (path->slots[0] == 0) {
5185 ret = btrfs_prev_leaf(root, path);
5189 path->slots[0]--;
5191 leaf = path->nodes[0];
5195 if (path->slots[0] == nritems)
5196 path->slots[0]--;
5198 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);