Lines Matching full: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) in leaf_data_end() argument
59 u32 nr = btrfs_header_nritems(leaf); in leaf_data_end()
62 return BTRFS_LEAF_DATA_SIZE(leaf->fs_info); in leaf_data_end()
63 return btrfs_item_offset(leaf, nr - 1); in leaf_data_end()
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, in memmove_leaf_data() argument
84 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, 0) + dst_offset, in memmove_leaf_data()
85 btrfs_item_nr_offset(leaf, 0) + src_offset, len); in memmove_leaf_data()
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, in memmove_leaf_items() argument
125 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, dst_item), in memmove_leaf_items()
126 btrfs_item_nr_offset(leaf, src_item), in memmove_leaf_items()
133 * @dst: destination leaf for the items
134 * @src: source leaf for the items
140 * appropriate offsets into the leaf from the item numbers.
2001 struct extent_buffer *leaf = path->nodes[0]; in search_leaf() local
2008 * If we are doing an insertion, the leaf has enough free space and the in search_leaf()
2011 * binary search on the leaf (with search_for_key_slot()), allowing other in search_leaf()
2016 * Cache the leaf free space, since we will need it later and it in search_leaf()
2019 leaf_free_space = btrfs_leaf_free_space(leaf); in search_leaf()
2022 * !path->locks[1] means we have a single node tree, the leaf is in search_leaf()
2028 ASSERT(btrfs_header_nritems(leaf) > 0); in search_leaf()
2029 btrfs_item_key(leaf, &first_key, 0); in search_leaf()
2050 * leaf and there's no need to split the leaf. in search_leaf()
2083 ret = search_for_key_slot(leaf, search_low_slot, key, in search_leaf()
2096 * accounts the size btrfs_item, deduct it here so leaf space in search_leaf()
2144 * If @key is found, 0 is returned and you can find the item in the leaf level
2147 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2502 * Search the tree again to find a leaf with smaller keys.
2539 * Previous key not found. Even if we were at slot 0 of the leaf we had in btrfs_prev_leaf()
2543 * sibling leaf into the front of the leaf we had due to an insertion in btrfs_prev_leaf()
2570 * item might have been pushed to the first slot (0) of the leaf we in btrfs_prev_leaf()
2572 * previous key can exist as the only element of a leaf (big fat item). in btrfs_prev_leaf()
2600 struct extent_buffer *leaf; in btrfs_search_slot_for_read() local
2609 * but in case the previous item is the last in a leaf, path points in btrfs_search_slot_for_read()
2610 * to the first free slot in the previous leaf, i.e. at an invalid in btrfs_search_slot_for_read()
2613 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2616 if (p->slots[0] >= btrfs_header_nritems(leaf)) { in btrfs_search_slot_for_read()
2637 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2638 if (p->slots[0] == btrfs_header_nritems(leaf)) in btrfs_search_slot_for_read()
2710 * fixing up pointers when a given leaf/node is not in slot 0 of the
2800 * Leaf @left | Leaf @right
2804 * Key f6 in leaf @left itself is valid, but not valid when the next
2805 * key in leaf @right is 7.
3225 * how many bytes are required to store the items in a leaf. start
3226 * and nr indicate which items in the leaf to check. This totals up the
3245 * The space between the end of the leaf items and
3246 * the start of the leaf data. IOW, how much room
3247 * the leaf has left for both items and data
3249 int btrfs_leaf_free_space(const struct extent_buffer *leaf) in btrfs_leaf_free_space() argument
3251 struct btrfs_fs_info *fs_info = leaf->fs_info; in btrfs_leaf_free_space()
3252 int nritems = btrfs_header_nritems(leaf); in btrfs_leaf_free_space()
3255 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); in btrfs_leaf_free_space()
3258 "leaf free space ret %d, leaf data size %lu, used %d nritems %d", in btrfs_leaf_free_space()
3261 leaf_space_used(leaf, 0, nritems), nritems); in btrfs_leaf_free_space()
3377 /* then fixup the leaf pointer in the path */ in __push_leaf_right()
3399 * push some data in the path leaf to the right, trying to free up at
3405 * this will push starting from min_slot to the end of the leaf. It won't
3458 /* Key greater than all keys in the leaf, right neighbor has in push_leaf_right()
3459 * enough room for it and we're not emptying our leaf to delete in push_leaf_right()
3461 * no need to touch/dirty our left leaf. */ in push_leaf_right()
3479 * push some data in the path leaf to the left, trying to free up at
3482 * max_slot can put a limit on how far into the leaf we'll push items. The
3596 /* then fixup the leaf pointer in the path */ in __push_leaf_left()
3617 * push some data in the path leaf to the left, trying to free up at
3620 * max_slot can put a limit on how far into the leaf we'll push items. The
3683 * split the path's leaf in two, making sure there is at least data_size
3684 * available for the resulting leaf level of the path.
3747 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3748 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3772 * right leaf in push_for_double_split()
3783 * our goal is to get our slot at the start or end of a leaf. If in push_for_double_split()
3792 /* try to push all the items before our slot into the next leaf */ in push_for_double_split()
3810 * split the path's leaf in two, making sure there is at least data_size
3811 * available for the resulting leaf level of the path.
3970 * We create a new leaf 'right' for the required ins_len and in split_leaf()
3971 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying in split_leaf()
4005 struct extent_buffer *leaf; in setup_leaf_for_split() local
4011 leaf = path->nodes[0]; in setup_leaf_for_split()
4012 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in setup_leaf_for_split()
4017 if (btrfs_leaf_free_space(leaf) >= ins_len) in setup_leaf_for_split()
4020 item_size = btrfs_item_size(leaf, path->slots[0]); in setup_leaf_for_split()
4022 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
4024 extent_len = btrfs_file_extent_num_bytes(leaf, fi); in setup_leaf_for_split()
4038 leaf = path->nodes[0]; in setup_leaf_for_split()
4040 if (item_size != btrfs_item_size(leaf, path->slots[0])) in setup_leaf_for_split()
4043 /* the leaf has changed, it now has room. return now */ in setup_leaf_for_split()
4048 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
4050 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) in setup_leaf_for_split()
4071 struct extent_buffer *leaf; in split_item() local
4079 leaf = path->nodes[0]; in split_item()
4082 * setup_leaf_for_split() to make room for the new item in the leaf. in split_item()
4084 if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item))) in split_item()
4088 orig_offset = btrfs_item_offset(leaf, path->slots[0]); in split_item()
4089 item_size = btrfs_item_size(leaf, path->slots[0]); in split_item()
4095 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, in split_item()
4099 nritems = btrfs_header_nritems(leaf); in split_item()
4102 memmove_leaf_items(leaf, slot + 1, slot, nritems - slot); in split_item()
4106 btrfs_set_item_key(leaf, &disk_key, slot); in split_item()
4108 btrfs_set_item_offset(leaf, slot, orig_offset); in split_item()
4109 btrfs_set_item_size(leaf, slot, item_size - split_offset); in split_item()
4111 btrfs_set_item_offset(leaf, orig_slot, in split_item()
4113 btrfs_set_item_size(leaf, orig_slot, split_offset); in split_item()
4115 btrfs_set_header_nritems(leaf, nritems + 1); in split_item()
4118 write_extent_buffer(leaf, buf, in split_item()
4119 btrfs_item_ptr_offset(leaf, path->slots[0]), in split_item()
4123 write_extent_buffer(leaf, buf + split_offset, in split_item()
4124 btrfs_item_ptr_offset(leaf, slot), in split_item()
4126 btrfs_mark_buffer_dirty(trans, leaf); in split_item()
4128 BUG_ON(btrfs_leaf_free_space(leaf) < 0); in split_item()
4146 * leaf the entire time.
4174 struct extent_buffer *leaf; in btrfs_truncate_item() local
4183 leaf = path->nodes[0]; in btrfs_truncate_item()
4186 old_size = btrfs_item_size(leaf, slot); in btrfs_truncate_item()
4190 nritems = btrfs_header_nritems(leaf); in btrfs_truncate_item()
4191 data_end = leaf_data_end(leaf); in btrfs_truncate_item()
4193 old_data_start = btrfs_item_offset(leaf, slot); in btrfs_truncate_item()
4204 btrfs_init_map_token(&token, leaf); in btrfs_truncate_item()
4214 memmove_leaf_data(leaf, data_end + size_diff, data_end, in btrfs_truncate_item()
4220 btrfs_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
4226 fi = btrfs_item_ptr(leaf, slot, in btrfs_truncate_item()
4231 if (btrfs_file_extent_type(leaf, fi) == in btrfs_truncate_item()
4233 ptr = btrfs_item_ptr_offset(leaf, slot); in btrfs_truncate_item()
4234 memmove_extent_buffer(leaf, ptr, in btrfs_truncate_item()
4240 memmove_leaf_data(leaf, data_end + size_diff, data_end, in btrfs_truncate_item()
4245 btrfs_set_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
4250 btrfs_set_item_size(leaf, slot, new_size); in btrfs_truncate_item()
4251 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_truncate_item()
4253 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_truncate_item()
4254 btrfs_print_leaf(leaf); in btrfs_truncate_item()
4266 struct extent_buffer *leaf; in btrfs_extend_item() local
4274 leaf = path->nodes[0]; in btrfs_extend_item()
4276 nritems = btrfs_header_nritems(leaf); in btrfs_extend_item()
4277 data_end = leaf_data_end(leaf); in btrfs_extend_item()
4279 if (btrfs_leaf_free_space(leaf) < data_size) { in btrfs_extend_item()
4280 btrfs_print_leaf(leaf); in btrfs_extend_item()
4284 old_data = btrfs_item_data_end(leaf, slot); in btrfs_extend_item()
4288 btrfs_print_leaf(leaf); in btrfs_extend_item()
4289 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", in btrfs_extend_item()
4298 btrfs_init_map_token(&token, leaf); in btrfs_extend_item()
4307 memmove_leaf_data(leaf, data_end - data_size, data_end, in btrfs_extend_item()
4311 old_size = btrfs_item_size(leaf, slot); in btrfs_extend_item()
4312 btrfs_set_item_size(leaf, slot, old_size + data_size); in btrfs_extend_item()
4313 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_extend_item()
4315 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_extend_item()
4316 btrfs_print_leaf(leaf); in btrfs_extend_item()
4326 * @path: points to the leaf/slot where we are going to insert new items
4341 struct extent_buffer *leaf; in setup_items_for_insert() local
4349 * can use them while we modify the leaf. in setup_items_for_insert()
4357 leaf = path->nodes[0]; in setup_items_for_insert()
4360 nritems = btrfs_header_nritems(leaf); in setup_items_for_insert()
4361 data_end = leaf_data_end(leaf); in setup_items_for_insert()
4364 if (btrfs_leaf_free_space(leaf) < total_size) { in setup_items_for_insert()
4365 btrfs_print_leaf(leaf); in setup_items_for_insert()
4367 total_size, btrfs_leaf_free_space(leaf)); in setup_items_for_insert()
4371 btrfs_init_map_token(&token, leaf); in setup_items_for_insert()
4373 unsigned int old_data = btrfs_item_data_end(leaf, slot); in setup_items_for_insert()
4376 btrfs_print_leaf(leaf); in setup_items_for_insert()
4378 "item at slot %d with data offset %u beyond data end of leaf %u", in setup_items_for_insert()
4394 memmove_leaf_items(leaf, slot + batch->nr, slot, nritems - slot); in setup_items_for_insert()
4397 memmove_leaf_data(leaf, data_end - batch->total_data_size, in setup_items_for_insert()
4405 btrfs_set_item_key(leaf, &disk_key, slot + i); in setup_items_for_insert()
4411 btrfs_set_header_nritems(leaf, nritems + batch->nr); in setup_items_for_insert()
4412 btrfs_mark_buffer_dirty(trans, leaf); in setup_items_for_insert()
4414 if (btrfs_leaf_free_space(leaf) < 0) { in setup_items_for_insert()
4415 btrfs_print_leaf(leaf); in setup_items_for_insert()
4421 * Insert a new item into a leaf.
4425 * @path: A path pointing to the target leaf and slot.
4482 struct extent_buffer *leaf; in btrfs_insert_item() local
4490 leaf = path->nodes[0]; in btrfs_insert_item()
4491 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in btrfs_insert_item()
4492 write_extent_buffer(leaf, data, ptr, data_size); in btrfs_insert_item()
4493 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_insert_item()
4501 * It guarantees both items live in the same tree leaf and the new item is
4504 * This allows us to split a file extent in place, keeping a lock on the leaf
4512 struct extent_buffer *leaf; in btrfs_duplicate_item() local
4516 leaf = path->nodes[0]; in btrfs_duplicate_item()
4517 item_size = btrfs_item_size(leaf, path->slots[0]); in btrfs_duplicate_item()
4525 leaf = path->nodes[0]; in btrfs_duplicate_item()
4526 memcpy_extent_buffer(leaf, in btrfs_duplicate_item()
4527 btrfs_item_ptr_offset(leaf, path->slots[0]), in btrfs_duplicate_item()
4528 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), in btrfs_duplicate_item()
4576 /* just turn the root into a leaf and break */ in btrfs_del_ptr()
4589 * a helper function to delete the leaf pointed to by path->slots[1] and
4592 * This deletes the pointer in path->nodes[1] and frees the leaf
4595 * The path must have already been setup for deleting the leaf, including
4601 struct extent_buffer *leaf) in btrfs_del_leaf() argument
4605 WARN_ON(btrfs_header_generation(leaf) != trans->transid); in btrfs_del_leaf()
4616 root_sub_used(root, leaf->len); in btrfs_del_leaf()
4618 atomic_inc(&leaf->refs); in btrfs_del_leaf()
4619 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1); in btrfs_del_leaf()
4620 free_extent_buffer_stale(leaf); in btrfs_del_leaf()
4627 * delete the item at the leaf level in path. If that empties
4628 * the leaf, remove it from the tree
4634 struct extent_buffer *leaf; in btrfs_del_items() local
4639 leaf = path->nodes[0]; in btrfs_del_items()
4640 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4643 const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1); in btrfs_del_items()
4644 const int data_end = leaf_data_end(leaf); in btrfs_del_items()
4650 dsize += btrfs_item_size(leaf, slot + i); in btrfs_del_items()
4652 memmove_leaf_data(leaf, data_end + dsize, data_end, in btrfs_del_items()
4655 btrfs_init_map_token(&token, leaf); in btrfs_del_items()
4663 memmove_leaf_items(leaf, slot, slot + nr, nritems - slot - nr); in btrfs_del_items()
4665 btrfs_set_header_nritems(leaf, nritems - nr); in btrfs_del_items()
4668 /* delete the leaf if we've emptied it */ in btrfs_del_items()
4670 if (leaf == root->node) { in btrfs_del_items()
4671 btrfs_set_header_level(leaf, 0); in btrfs_del_items()
4673 btrfs_clear_buffer_dirty(trans, leaf); in btrfs_del_items()
4674 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4679 int used = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4683 btrfs_item_key(leaf, &disk_key, 0); in btrfs_del_items()
4688 * Try to delete the leaf if it is mostly empty. We do this by in btrfs_del_items()
4691 * not ideal, but future insertions might fill the leaf with more in btrfs_del_items()
4693 * leaf due to deletions on those leaves. in btrfs_del_items()
4699 * make sure the path still points to our leaf in btrfs_del_items()
4703 atomic_inc(&leaf->refs); in btrfs_del_items()
4706 * left neighbour leaf, and that's the first item. in btrfs_del_items()
4709 btrfs_item_size(leaf, 0); in btrfs_del_items()
4715 if (path->nodes[0] == leaf && in btrfs_del_items()
4716 btrfs_header_nritems(leaf)) { in btrfs_del_items()
4719 * leaf to its left neighbour, then attempt to in btrfs_del_items()
4723 * it's pointless to end up with a leaf having in btrfs_del_items()
4727 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4728 min_push_space = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4735 if (btrfs_header_nritems(leaf) == 0) { in btrfs_del_items()
4737 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4740 free_extent_buffer(leaf); in btrfs_del_items()
4748 if (path->nodes[0] == leaf) in btrfs_del_items()
4749 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_del_items()
4750 free_extent_buffer(leaf); in btrfs_del_items()
4753 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_del_items()
5032 * This one should be returned as well, or we can get leaf corruption in btrfs_next_old_leaf()
5098 * itself waiting for the leaf we've currently in btrfs_next_old_leaf()
5178 struct extent_buffer *leaf; in btrfs_previous_item() local
5190 leaf = path->nodes[0]; in btrfs_previous_item()
5191 nritems = btrfs_header_nritems(leaf); in btrfs_previous_item()
5197 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_item()
5219 struct extent_buffer *leaf; in btrfs_previous_extent_item() local
5231 leaf = path->nodes[0]; in btrfs_previous_extent_item()
5232 nritems = btrfs_header_nritems(leaf); in btrfs_previous_extent_item()
5238 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_extent_item()