Lines Matching refs:path
19 *root, struct btrfs_path *path, int level);
21 const struct btrfs_key *ins_key, struct btrfs_path *path,
29 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
81 /* this also releases the path */
91 * path release drops references on the extent buffers in the path
92 * and it drops any locks held by this path
1268 tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
1284 btrfs_set_path_blocking(path);
1846 struct btrfs_path *path, int level)
1856 int orig_slot = path->slots[level];
1861 mid = path->nodes[level];
1863 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK &&
1864 path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING);
1870 parent = path->nodes[level + 1];
1871 pslot = path->slots[level + 1];
1909 path->locks[level] = 0;
1910 path->nodes[level] = NULL;
1913 /* once for the path */
1976 del_ptr(root, path, level + 1, pslot + 1);
2021 del_ptr(root, path, level + 1, pslot);
2037 /* update the path */
2042 path->nodes[level] = left;
2043 path->slots[level + 1] -= 1;
2044 path->slots[level] = orig_slot;
2051 path->slots[level] = orig_slot;
2056 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
2064 if (path->nodes[level] != left)
2077 struct btrfs_path *path, int level)
2087 int orig_slot = path->slots[level];
2092 mid = path->nodes[level];
2096 parent = path->nodes[level + 1];
2097 pslot = path->slots[level + 1];
2139 path->nodes[level] = left;
2140 path->slots[level + 1] -= 1;
2141 path->slots[level] = orig_slot;
2147 path->slots[level] = orig_slot;
2195 path->nodes[level] = right;
2196 path->slots[level + 1] += 1;
2197 path->slots[level] = orig_slot -
2218 struct btrfs_path *path,
2235 if (!path->nodes[level])
2238 node = path->nodes[level];
2254 if (path->reada == READA_BACK) {
2258 } else if (path->reada == READA_FORWARD) {
2263 if (path->reada == READA_BACK && objectid) {
2281 struct btrfs_path *path, int level)
2291 parent = path->nodes[level + 1];
2296 slot = path->slots[level + 1];
2329 * in the tree. The exceptions are when our path goes through slot 0, because
2333 * callers might also have set path->keep_locks, which tells this code to keep
2334 * the lock if the path points to the last slot in the block. This is part of
2340 static noinline void unlock_up(struct btrfs_path *path, int level,
2350 if (!path->nodes[i])
2352 if (!path->locks[i])
2354 if (!no_skips && path->slots[i] == 0) {
2358 if (!no_skips && path->keep_locks) {
2360 t = path->nodes[i];
2362 if (nritems < 1 || path->slots[i] >= nritems - 1) {
2370 t = path->nodes[i];
2372 btrfs_tree_unlock_rw(t, path->locks[i]);
2373 path->locks[i] = 0;
2385 * in cache without setting the path to blocking. If we find the block
2386 * we return zero and the path is unchanged.
2388 * If we can't find the block, we set the path blocking and do some
2486 * drop the path, -EAGAIN is returned and btrfs_search_slot must
2551 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
2559 ASSERT(path);
2566 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
2570 eb = path->nodes[0];
2571 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
2572 ret = btrfs_next_leaf(fs_root, path);
2575 eb = path->nodes[0];
2578 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
2687 * @p: Holds all btree nodes along the search path
2699 * of the path (level 0)
2701 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2770 * then we don't want to set the path blocking,
2809 * Leave path with blocking locks to avoid massive
2942 * we don't really know what they plan on doing with the path
2960 * The resulting path and return value will be set up as if we called
3085 * a return value of 1 means the path is at the position where the
3087 * but in case the previous item is the last in a leaf, path points
3145 static void fixup_low_keys(struct btrfs_path *path,
3153 int tslot = path->slots[i];
3155 if (!path->nodes[i])
3157 t = path->nodes[i];
3162 btrfs_mark_buffer_dirty(path->nodes[i]);
3175 struct btrfs_path *path,
3182 eb = path->nodes[0];
3183 slot = path->slots[0];
3217 fixup_low_keys(path, &disk_key, 1);
3432 struct btrfs_path *path, int level)
3442 BUG_ON(path->nodes[level]);
3443 BUG_ON(path->nodes[level-1] != root->node);
3445 lower = path->nodes[level-1];
3479 path->nodes[level] = c;
3480 path->locks[level] = BTRFS_WRITE_LOCK_BLOCKING;
3481 path->slots[level] = 0;
3493 struct btrfs_path *path,
3501 BUG_ON(!path->nodes[level]);
3502 btrfs_assert_tree_locked(path->nodes[level]);
3503 lower = path->nodes[level];
3532 * split the node at the specified level in path in two.
3533 * The path is corrected to point to the appropriate node after the split
3542 struct btrfs_path *path, int level)
3552 c = path->nodes[level];
3565 ret = insert_new_root(trans, root, path, level + 1);
3569 ret = push_nodes_for_insert(trans, root, path, level);
3570 c = path->nodes[level];
3608 insert_ptr(trans, path, &disk_key, split->start,
3609 path->slots[level + 1] + 1, level + 1);
3611 if (path->slots[level] >= mid) {
3612 path->slots[level] -= mid;
3615 path->nodes[level] = split;
3616 path->slots[level + 1] += 1;
3675 static noinline int __push_leaf_right(struct btrfs_path *path,
3682 struct extent_buffer *left = path->nodes[0];
3683 struct extent_buffer *upper = path->nodes[1];
3701 if (path->slots[0] >= left_nritems)
3704 slot = path->slots[1];
3710 if (path->slots[0] > i)
3712 if (path->slots[0] == i) {
3720 if (path->slots[0] == i)
3792 /* then fixup the leaf pointer in the path */
3793 if (path->slots[0] >= left_nritems) {
3794 path->slots[0] -= left_nritems;
3795 if (btrfs_header_nritems(path->nodes[0]) == 0)
3796 btrfs_clean_tree_block(path->nodes[0]);
3797 btrfs_tree_unlock(path->nodes[0]);
3798 free_extent_buffer(path->nodes[0]);
3799 path->nodes[0] = right;
3800 path->slots[1] += 1;
3814 * push some data in the path leaf to the right, trying to free up at
3824 *root, struct btrfs_path *path,
3828 struct extent_buffer *left = path->nodes[0];
3836 if (!path->nodes[1])
3839 slot = path->slots[1];
3840 upper = path->nodes[1];
3844 btrfs_assert_tree_locked(path->nodes[1]);
3882 if (path->slots[0] == left_nritems && !empty) {
3889 path->nodes[0] = right;
3890 path->slots[0] = 0;
3891 path->slots[1]++;
3895 return __push_leaf_right(path, min_data_size, empty,
3904 * push some data in the path leaf to the left, trying to free up at
3911 static noinline int __push_leaf_left(struct btrfs_path *path, int data_size,
3918 struct extent_buffer *right = path->nodes[0];
3939 if (path->slots[0] < i)
3941 if (path->slots[0] == i) {
3949 if (path->slots[0] == i)
4033 fixup_low_keys(path, &disk_key, 1);
4035 /* then fixup the leaf pointer in the path */
4036 if (path->slots[0] < push_items) {
4037 path->slots[0] += old_left_nritems;
4038 btrfs_tree_unlock(path->nodes[0]);
4039 free_extent_buffer(path->nodes[0]);
4040 path->nodes[0] = left;
4041 path->slots[1] -= 1;
4045 path->slots[0] -= push_items;
4047 BUG_ON(path->slots[0] < 0);
4056 * push some data in the path leaf to the left, trying to free up at
4064 *root, struct btrfs_path *path, int min_data_size,
4067 struct extent_buffer *right = path->nodes[0];
4074 slot = path->slots[1];
4077 if (!path->nodes[1])
4084 btrfs_assert_tree_locked(path->nodes[1]);
4086 left = btrfs_read_node_slot(path->nodes[1], slot - 1);
4105 path->nodes[1], slot - 1, &left,
4125 return __push_leaf_left(path, min_data_size,
4135 * split the path's leaf in two, making sure there is at least data_size
4136 * available for the resulting leaf level of the path.
4139 struct btrfs_path *path,
4177 insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
4181 BUG_ON(path->slots[0] != slot);
4184 btrfs_tree_unlock(path->nodes[0]);
4185 free_extent_buffer(path->nodes[0]);
4186 path->nodes[0] = right;
4187 path->slots[0] -= mid;
4188 path->slots[1] += 1;
4194 BUG_ON(path->slots[0] < 0);
4209 struct btrfs_path *path,
4218 slot = path->slots[0];
4219 if (slot < btrfs_header_nritems(path->nodes[0]))
4220 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
4226 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
4233 nritems = btrfs_header_nritems(path->nodes[0]);
4238 if (path->slots[0] == 0 || path->slots[0] == nritems)
4241 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
4245 slot = path->slots[0];
4248 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
4249 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
4262 * split the path's leaf in two, making sure there is at least data_size
4263 * available for the resulting leaf level of the path.
4270 struct btrfs_path *path, int data_size,
4286 l = path->nodes[0];
4287 slot = path->slots[0];
4293 if (data_size && path->nodes[1]) {
4299 wret = push_leaf_right(trans, root, path, space_needed,
4307 wret = push_leaf_left(trans, root, path, space_needed,
4312 l = path->nodes[0];
4319 if (!path->nodes[1]) {
4320 ret = insert_new_root(trans, root, path, 1);
4326 l = path->nodes[0];
4327 slot = path->slots[0];
4393 insert_ptr(trans, path, &disk_key,
4394 right->start, path->slots[1] + 1, 1);
4395 btrfs_tree_unlock(path->nodes[0]);
4396 free_extent_buffer(path->nodes[0]);
4397 path->nodes[0] = right;
4398 path->slots[0] = 0;
4399 path->slots[1] += 1;
4402 insert_ptr(trans, path, &disk_key,
4403 right->start, path->slots[1], 1);
4404 btrfs_tree_unlock(path->nodes[0]);
4405 free_extent_buffer(path->nodes[0]);
4406 path->nodes[0] = right;
4407 path->slots[0] = 0;
4408 if (path->slots[1] == 0)
4409 fixup_low_keys(path, &disk_key, 1);
4419 copy_for_split(trans, path, l, right, slot, mid, nritems);
4430 push_for_double_split(trans, root, path, data_size);
4432 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
4439 struct btrfs_path *path, int ins_len)
4448 leaf = path->nodes[0];
4449 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4457 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4459 fi = btrfs_item_ptr(leaf, path->slots[0],
4463 btrfs_release_path(path);
4465 path->keep_locks = 1;
4466 path->search_for_split = 1;
4467 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
4468 path->search_for_split = 0;
4475 leaf = path->nodes[0];
4477 if (item_size != btrfs_item_size_nr(leaf, path->slots[0]))
4481 if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len)
4485 fi = btrfs_item_ptr(leaf, path->slots[0],
4491 btrfs_set_path_blocking(path);
4492 ret = split_leaf(trans, root, &key, path, ins_len, 1);
4496 path->keep_locks = 0;
4497 btrfs_unlock_up_safe(path, 1);
4500 path->keep_locks = 0;
4504 static noinline int split_item(struct btrfs_path *path,
4518 leaf = path->nodes[0];
4521 btrfs_set_path_blocking(path);
4523 item = btrfs_item_nr(path->slots[0]);
4532 path->slots[0]), item_size);
4534 slot = path->slots[0] + 1;
4559 btrfs_item_ptr_offset(leaf, path->slots[0]),
4578 * The path may be released by this operation. After
4579 * the split, the path is pointing to the old item. The
4590 struct btrfs_path *path,
4595 ret = setup_leaf_for_split(trans, root, path,
4600 ret = split_item(path, new_key, split_offset);
4614 struct btrfs_path *path,
4621 leaf = path->nodes[0];
4622 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4623 ret = setup_leaf_for_split(trans, root, path,
4628 path->slots[0]++;
4629 setup_items_for_insert(root, path, new_key, &item_size, 1);
4630 leaf = path->nodes[0];
4632 btrfs_item_ptr_offset(leaf, path->slots[0]),
4633 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4639 * make the item pointed to by the path smaller. new_size indicates
4644 void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end)
4657 leaf = path->nodes[0];
4658 slot = path->slots[0];
4724 fixup_low_keys(path, &disk_key, 1);
4738 * make the item pointed to by the path bigger, data_size is the added size.
4740 void btrfs_extend_item(struct btrfs_path *path, u32 data_size)
4752 leaf = path->nodes[0];
4761 slot = path->slots[0];
4808 * @path: points to the leaf/slot where we are going to insert new items
4813 void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path,
4833 if (path->slots[0] == 0) {
4835 fixup_low_keys(path, &disk_key, 1);
4837 btrfs_unlock_up_safe(path, 1);
4839 leaf = path->nodes[0];
4840 slot = path->slots[0];
4908 * This does all the path init required, making room in the tree if needed.
4912 struct btrfs_path *path,
4926 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
4932 slot = path->slots[0];
4935 setup_items_for_insert(root, path, cpu_key, data_size, nr);
4941 * This does all the path init required, making room in the tree if needed.
4948 struct btrfs_path *path;
4952 path = btrfs_alloc_path();
4953 if (!path)
4955 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
4957 leaf = path->nodes[0];
4958 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4962 btrfs_free_path(path);
4972 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
4975 struct extent_buffer *parent = path->nodes[level];
5007 fixup_low_keys(path, &disk_key, level + 1);
5013 * a helper function to delete the leaf pointed to by path->slots[1] and
5014 * path->nodes[1].
5016 * This deletes the pointer in path->nodes[1] and frees the leaf
5019 * The path must have already been setup for deleting the leaf, including
5020 * all the proper balancing. path->nodes[1] must be locked.
5024 struct btrfs_path *path,
5028 del_ptr(root, path, 1, path->slots[1]);
5034 btrfs_unlock_up_safe(path, 0);
5043 * delete the item at the leaf level in path. If that empties
5047 struct btrfs_path *path, int slot, int nr)
5059 leaf = path->nodes[0];
5098 btrfs_set_path_blocking(path);
5100 btrfs_del_leaf(trans, root, path, leaf);
5108 fixup_low_keys(path, &disk_key, 1);
5113 /* push_leaf_left fixes the path.
5114 * make sure the path still points to our leaf
5117 slot = path->slots[1];
5120 btrfs_set_path_blocking(path);
5121 wret = push_leaf_left(trans, root, path, 1, 1,
5126 if (path->nodes[0] == leaf &&
5128 wret = push_leaf_right(trans, root, path, 1,
5135 path->slots[1] = slot;
5136 btrfs_del_leaf(trans, root, path, leaf);
5140 /* if we're still in the path, make sure
5145 if (path->nodes[0] == leaf)
5161 * This may release the path, and so you may lose any locks held at the
5164 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
5171 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
5187 btrfs_release_path(path);
5188 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5194 * before releasing the path and calling btrfs_search_slot(), we now may
5196 * after we released the path, one of more items were moved from a
5203 if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
5204 btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
5207 if (path->slots[0] > 0) {
5208 path->slots[0]--;
5219 btrfs_item_key(path->nodes[0], &found_key, 0);
5223 * before we released our path. And after we released our path, that
5243 * key and get a writable path.
5245 * This honors path->lowest_level to prevent descent past a given level
5256 struct btrfs_path *path,
5266 int keep_locks = path->keep_locks;
5268 path->keep_locks = 1;
5272 WARN_ON(path->nodes[level]);
5273 path->nodes[level] = cur;
5274 path->locks[level] = BTRFS_READ_LOCK;
5289 /* at the lowest level, we're done, setup the path and exit */
5290 if (level == path->lowest_level) {
5294 path->slots[level] = slot;
5320 path->slots[level] = slot;
5321 btrfs_set_path_blocking(path);
5322 sret = btrfs_find_next_key(root, path, min_key, level,
5325 btrfs_release_path(path);
5333 path->slots[level] = slot;
5334 if (level == path->lowest_level) {
5338 btrfs_set_path_blocking(path);
5347 path->locks[level - 1] = BTRFS_READ_LOCK;
5348 path->nodes[level - 1] = cur;
5349 unlock_up(path, level, 1, 0, NULL);
5352 path->keep_locks = keep_locks;
5354 btrfs_unlock_up_safe(path, path->lowest_level + 1);
5355 btrfs_set_path_blocking(path);
5363 * and fixup the path. It looks for and returns the next key in the
5364 * tree based on the current path and the min_trans parameters.
5369 * path->keep_locks should be set to 1 on the search made before
5372 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
5378 WARN_ON(!path->keep_locks && !path->skip_locking);
5380 if (!path->nodes[level])
5383 slot = path->slots[level] + 1;
5384 c = path->nodes[level];
5391 !path->nodes[level + 1])
5394 if (path->locks[level + 1] || path->skip_locking) {
5405 orig_lowest = path->lowest_level;
5406 btrfs_release_path(path);
5407 path->lowest_level = level;
5408 ret = btrfs_search_slot(NULL, root, &cur_key, path,
5410 path->lowest_level = orig_lowest;
5414 c = path->nodes[level];
5415 slot = path->slots[level];
5442 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
5444 return btrfs_next_old_leaf(root, path, 0);
5447 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
5457 int old_spinning = path->leave_spinning;
5460 nritems = btrfs_header_nritems(path->nodes[0]);
5464 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
5469 btrfs_release_path(path);
5471 path->keep_locks = 1;
5472 path->leave_spinning = 1;
5475 ret = btrfs_search_old_slot(root, &key, path, time_seq);
5477 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5478 path->keep_locks = 0;
5483 nritems = btrfs_header_nritems(path->nodes[0]);
5485 * by releasing the path above we dropped all our locks. A balance
5488 * advance the path if there are now more items available.
5490 if (nritems > 0 && path->slots[0] < nritems - 1) {
5492 path->slots[0]++;
5498 * - after releasing the path above, someone has removed the item that
5506 * with ret > 0, the key isn't found, the path points to the slot
5507 * where it should be inserted, so the path->slots[0] item must be the
5510 if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) {
5516 if (!path->nodes[level]) {
5521 slot = path->slots[level] + 1;
5522 c = path->nodes[level];
5538 next_rw_lock = path->locks[level];
5539 ret = read_block_for_search(root, path, &next, level,
5545 btrfs_release_path(path);
5549 if (!path->skip_locking) {
5560 btrfs_release_path(path);
5565 btrfs_set_path_blocking(path);
5568 path->recurse);
5574 path->slots[level] = slot;
5577 c = path->nodes[level];
5578 if (path->locks[level])
5579 btrfs_tree_unlock_rw(c, path->locks[level]);
5582 path->nodes[level] = next;
5583 path->slots[level] = 0;
5584 if (!path->skip_locking)
5585 path->locks[level] = next_rw_lock;
5589 ret = read_block_for_search(root, path, &next, level,
5595 btrfs_release_path(path);
5599 if (!path->skip_locking) {
5602 btrfs_set_path_blocking(path);
5605 path->recurse);
5612 unlock_up(path, 0, 1, 0, NULL);
5613 path->leave_spinning = old_spinning;
5615 btrfs_set_path_blocking(path);
5627 struct btrfs_path *path, u64 min_objectid,
5636 if (path->slots[0] == 0) {
5637 btrfs_set_path_blocking(path);
5638 ret = btrfs_prev_leaf(root, path);
5642 path->slots[0]--;
5644 leaf = path->nodes[0];
5648 if (path->slots[0] == nritems)
5649 path->slots[0]--;
5651 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5670 struct btrfs_path *path, u64 min_objectid)
5678 if (path->slots[0] == 0) {
5679 btrfs_set_path_blocking(path);
5680 ret = btrfs_prev_leaf(root, path);
5684 path->slots[0]--;
5686 leaf = path->nodes[0];
5690 if (path->slots[0] == nritems)
5691 path->slots[0]--;
5693 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);