Lines Matching defs:leaf
54 * The leaf data grows from end-to-front in the node. this returns the address
55 * of the start of the last item, which is the stop of the leaf data stack.
57 static unsigned int leaf_data_end(const struct extent_buffer *leaf)
59 u32 nr = btrfs_header_nritems(leaf);
62 return BTRFS_LEAF_DATA_SIZE(leaf->fs_info);
63 return btrfs_item_offset(leaf, nr - 1);
67 * Move data in a @leaf (using memmove, safe for overlapping ranges).
69 * @leaf: leaf that we're doing a memmove on
75 * the leaf. The btrfs_item offset's start directly after the header, so we
76 * have to adjust any offsets to account for the header in the leaf. This
79 static inline void memmove_leaf_data(const struct extent_buffer *leaf,
84 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, 0) + dst_offset,
85 btrfs_item_nr_offset(leaf, 0) + src_offset, len);
91 * @dst: destination leaf that we're copying into
92 * @src: source leaf that we're copying from
98 * the leaf. The btrfs_item offset's start directly after the header, so we
99 * have to adjust any offsets to account for the header in the leaf. This
112 * Move items in a @leaf (using memmove).
114 * @dst: destination leaf for the items
120 * appropriate offsets into the leaf from the item numbers.
122 static inline void memmove_leaf_items(const struct extent_buffer *leaf,
125 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, dst_item),
126 btrfs_item_nr_offset(leaf, src_item),
133 * @dst: destination leaf for the items
134 * @src: source leaf for the items
140 * appropriate offsets into the leaf from the item numbers.
1972 struct extent_buffer *leaf = path->nodes[0];
1979 * If we are doing an insertion, the leaf has enough free space and the
1982 * binary search on the leaf (with search_for_key_slot()), allowing other
1987 * Cache the leaf free space, since we will need it later and it
1990 leaf_free_space = btrfs_leaf_free_space(leaf);
1993 * !path->locks[1] means we have a single node tree, the leaf is
1999 ASSERT(btrfs_header_nritems(leaf) > 0);
2000 btrfs_item_key(leaf, &first_key, 0);
2021 * leaf and there's no need to split the leaf.
2054 ret = search_for_key_slot(leaf, search_low_slot, key,
2067 * accounts the size btrfs_item, deduct it here so leaf space
2115 * If @key is found, 0 is returned and you can find the item in the leaf level
2118 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2469 * Search the tree again to find a leaf with smaller keys.
2506 * Previous key not found. Even if we were at slot 0 of the leaf we had
2510 * sibling leaf into the front of the leaf we had due to an insertion
2537 * item might have been pushed to the first slot (0) of the leaf we
2539 * previous key can exist as the only element of a leaf (big fat item).
2567 struct extent_buffer *leaf;
2576 * but in case the previous item is the last in a leaf, path points
2577 * to the first free slot in the previous leaf, i.e. at an invalid
2580 leaf = p->nodes[0];
2583 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
2604 leaf = p->nodes[0];
2605 if (p->slots[0] == btrfs_header_nritems(leaf))
2677 * fixing up pointers when a given leaf/node is not in slot 0 of the
2771 * Key f6 in leaf @left itself is valid, but not valid when the next
2772 * key in leaf @right is 7.
3188 * how many bytes are required to store the items in a leaf. start
3189 * and nr indicate which items in the leaf to check. This totals up the
3208 * The space between the end of the leaf items and
3209 * the start of the leaf data. IOW, how much room
3210 * the leaf has left for both items and data
3212 int btrfs_leaf_free_space(const struct extent_buffer *leaf)
3214 struct btrfs_fs_info *fs_info = leaf->fs_info;
3215 int nritems = btrfs_header_nritems(leaf);
3218 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
3221 "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
3224 leaf_space_used(leaf, 0, nritems), nritems);
3340 /* then fixup the leaf pointer in the path */
3362 * push some data in the path leaf to the right, trying to free up at
3368 * this will push starting from min_slot to the end of the leaf. It won't
3421 /* Key greater than all keys in the leaf, right neighbor has
3422 * enough room for it and we're not emptying our leaf to delete
3424 * no need to touch/dirty our left leaf. */
3442 * push some data in the path leaf to the left, trying to free up at
3445 * max_slot can put a limit on how far into the leaf we'll push items. The
3559 /* then fixup the leaf pointer in the path */
3580 * push some data in the path leaf to the left, trying to free up at
3583 * max_slot can put a limit on how far into the leaf we'll push items. The
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.
3710 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3711 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3735 * right leaf
3746 * our goal is to get our slot at the start or end of a leaf. If
3755 /* try to push all the items before our slot into the next leaf */
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.
3933 * We create a new leaf 'right' for the required ins_len and
3934 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
3968 struct extent_buffer *leaf;
3974 leaf = path->nodes[0];
3975 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3980 if (btrfs_leaf_free_space(leaf) >= ins_len)
3983 item_size = btrfs_item_size(leaf, path->slots[0]);
3985 fi = btrfs_item_ptr(leaf, path->slots[0],
3987 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
4001 leaf = path->nodes[0];
4003 if (item_size != btrfs_item_size(leaf, path->slots[0]))
4006 /* the leaf has changed, it now has room. return now */
4011 fi = btrfs_item_ptr(leaf, path->slots[0],
4013 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
4034 struct extent_buffer *leaf;
4042 leaf = path->nodes[0];
4045 * setup_leaf_for_split() to make room for the new item in the leaf.
4047 if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)))
4051 orig_offset = btrfs_item_offset(leaf, path->slots[0]);
4052 item_size = btrfs_item_size(leaf, path->slots[0]);
4058 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
4062 nritems = btrfs_header_nritems(leaf);
4065 memmove_leaf_items(leaf, slot + 1, slot, nritems - slot);
4069 btrfs_set_item_key(leaf, &disk_key, slot);
4071 btrfs_set_item_offset(leaf, slot, orig_offset);
4072 btrfs_set_item_size(leaf, slot, item_size - split_offset);
4074 btrfs_set_item_offset(leaf, orig_slot,
4076 btrfs_set_item_size(leaf, orig_slot, split_offset);
4078 btrfs_set_header_nritems(leaf, nritems + 1);
4081 write_extent_buffer(leaf, buf,
4082 btrfs_item_ptr_offset(leaf, path->slots[0]),
4086 write_extent_buffer(leaf, buf + split_offset,
4087 btrfs_item_ptr_offset(leaf, slot),
4089 btrfs_mark_buffer_dirty(trans, leaf);
4091 BUG_ON(btrfs_leaf_free_space(leaf) < 0);
4109 * leaf the entire time.
4137 struct extent_buffer *leaf;
4146 leaf = path->nodes[0];
4149 old_size = btrfs_item_size(leaf, slot);
4153 nritems = btrfs_header_nritems(leaf);
4154 data_end = leaf_data_end(leaf);
4156 old_data_start = btrfs_item_offset(leaf, slot);
4167 btrfs_init_map_token(&token, leaf);
4177 memmove_leaf_data(leaf, data_end + size_diff, data_end,
4183 btrfs_item_key(leaf, &disk_key, slot);
4189 fi = btrfs_item_ptr(leaf, slot,
4194 if (btrfs_file_extent_type(leaf, fi) ==
4196 ptr = btrfs_item_ptr_offset(leaf, slot);
4197 memmove_extent_buffer(leaf, ptr,
4203 memmove_leaf_data(leaf, data_end + size_diff, data_end,
4208 btrfs_set_item_key(leaf, &disk_key, slot);
4213 btrfs_set_item_size(leaf, slot, new_size);
4214 btrfs_mark_buffer_dirty(trans, leaf);
4216 if (btrfs_leaf_free_space(leaf) < 0) {
4217 btrfs_print_leaf(leaf);
4229 struct extent_buffer *leaf;
4237 leaf = path->nodes[0];
4239 nritems = btrfs_header_nritems(leaf);
4240 data_end = leaf_data_end(leaf);
4242 if (btrfs_leaf_free_space(leaf) < data_size) {
4243 btrfs_print_leaf(leaf);
4247 old_data = btrfs_item_data_end(leaf, slot);
4251 btrfs_print_leaf(leaf);
4252 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",
4261 btrfs_init_map_token(&token, leaf);
4270 memmove_leaf_data(leaf, data_end - data_size, data_end,
4274 old_size = btrfs_item_size(leaf, slot);
4275 btrfs_set_item_size(leaf, slot, old_size + data_size);
4276 btrfs_mark_buffer_dirty(trans, leaf);
4278 if (btrfs_leaf_free_space(leaf) < 0) {
4279 btrfs_print_leaf(leaf);
4289 * @path: points to the leaf/slot where we are going to insert new items
4304 struct extent_buffer *leaf;
4312 * can use them while we modify the leaf.
4320 leaf = path->nodes[0];
4323 nritems = btrfs_header_nritems(leaf);
4324 data_end = leaf_data_end(leaf);
4327 if (btrfs_leaf_free_space(leaf) < total_size) {
4328 btrfs_print_leaf(leaf);
4330 total_size, btrfs_leaf_free_space(leaf));
4334 btrfs_init_map_token(&token, leaf);
4336 unsigned int old_data = btrfs_item_data_end(leaf, slot);
4339 btrfs_print_leaf(leaf);
4341 "item at slot %d with data offset %u beyond data end of leaf %u",
4357 memmove_leaf_items(leaf, slot + batch->nr, slot, nritems - slot);
4360 memmove_leaf_data(leaf, data_end - batch->total_data_size,
4368 btrfs_set_item_key(leaf, &disk_key, slot + i);
4374 btrfs_set_header_nritems(leaf, nritems + batch->nr);
4375 btrfs_mark_buffer_dirty(trans, leaf);
4377 if (btrfs_leaf_free_space(leaf) < 0) {
4378 btrfs_print_leaf(leaf);
4384 * Insert a new item into a leaf.
4388 * @path: A path pointing to the target leaf and slot.
4445 struct extent_buffer *leaf;
4453 leaf = path->nodes[0];
4454 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4455 write_extent_buffer(leaf, data, ptr, data_size);
4456 btrfs_mark_buffer_dirty(trans, leaf);
4464 * It guarantees both items live in the same tree leaf and the new item is
4467 * This allows us to split a file extent in place, keeping a lock on the leaf
4475 struct extent_buffer *leaf;
4479 leaf = path->nodes[0];
4480 item_size = btrfs_item_size(leaf, path->slots[0]);
4488 leaf = path->nodes[0];
4489 memcpy_extent_buffer(leaf,
4490 btrfs_item_ptr_offset(leaf, path->slots[0]),
4491 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4539 /* just turn the root into a leaf and break */
4552 * a helper function to delete the leaf pointed to by path->slots[1] and
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
4564 struct extent_buffer *leaf)
4568 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
4579 root_sub_used(root, leaf->len);
4581 atomic_inc(&leaf->refs);
4582 btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1);
4583 free_extent_buffer_stale(leaf);
4587 * delete the item at the leaf level in path. If that empties
4588 * the leaf, remove it from the tree
4594 struct extent_buffer *leaf;
4599 leaf = path->nodes[0];
4600 nritems = btrfs_header_nritems(leaf);
4603 const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1);
4604 const int data_end = leaf_data_end(leaf);
4610 dsize += btrfs_item_size(leaf, slot + i);
4612 memmove_leaf_data(leaf, data_end + dsize, data_end,
4615 btrfs_init_map_token(&token, leaf);
4623 memmove_leaf_items(leaf, slot, slot + nr, nritems - slot - nr);
4625 btrfs_set_header_nritems(leaf, nritems - nr);
4628 /* delete the leaf if we've emptied it */
4630 if (leaf == root->node) {
4631 btrfs_set_header_level(leaf, 0);
4633 btrfs_clear_buffer_dirty(trans, leaf);
4634 ret = btrfs_del_leaf(trans, root, path, leaf);
4639 int used = leaf_space_used(leaf, 0, nritems);
4643 btrfs_item_key(leaf, &disk_key, 0);
4648 * Try to delete the leaf if it is mostly empty. We do this by
4651 * not ideal, but future insertions might fill the leaf with more
4653 * leaf due to deletions on those leaves.
4659 * make sure the path still points to our leaf
4663 atomic_inc(&leaf->refs);
4666 * left neighbour leaf, and that's the first item.
4669 btrfs_item_size(leaf, 0);
4675 if (path->nodes[0] == leaf &&
4676 btrfs_header_nritems(leaf)) {
4679 * leaf to its left neighbour, then attempt to
4683 * it's pointless to end up with a leaf having
4687 nritems = btrfs_header_nritems(leaf);
4688 min_push_space = leaf_space_used(leaf, 0, nritems);
4695 if (btrfs_header_nritems(leaf) == 0) {
4697 ret = btrfs_del_leaf(trans, root, path, leaf);
4700 free_extent_buffer(leaf);
4708 if (path->nodes[0] == leaf)
4709 btrfs_mark_buffer_dirty(trans, leaf);
4710 free_extent_buffer(leaf);
4713 btrfs_mark_buffer_dirty(trans, leaf);
4992 * This one should be returned as well, or we can get leaf corruption
5058 * itself waiting for the leaf we've currently
5138 struct extent_buffer *leaf;
5150 leaf = path->nodes[0];
5151 nritems = btrfs_header_nritems(leaf);
5157 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5179 struct extent_buffer *leaf;
5191 leaf = path->nodes[0];
5192 nritems = btrfs_header_nritems(leaf);
5198 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);