Lines Matching full:leaf
1768 struct extent_buffer *leaf = path->nodes[0]; in search_leaf() local
1775 * If we are doing an insertion, the leaf has enough free space and the in search_leaf()
1778 * binary search on the leaf (with search_for_key_slot()), allowing other in search_leaf()
1783 * Cache the leaf free space, since we will need it later and it in search_leaf()
1786 leaf_free_space = btrfs_leaf_free_space(leaf); in search_leaf()
1789 * !path->locks[1] means we have a single node tree, the leaf is in search_leaf()
1795 ASSERT(btrfs_header_nritems(leaf) > 0); in search_leaf()
1796 btrfs_item_key(leaf, &first_key, 0); in search_leaf()
1817 * leaf and there's no need to split the leaf. in search_leaf()
1850 ret = search_for_key_slot(leaf, search_low_slot, key, in search_leaf()
1863 * accounts the size btrfs_item, deduct it here so leaf space in search_leaf()
1911 * If @key is found, 0 is returned and you can find the item in the leaf level
1914 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2280 struct extent_buffer *leaf; in btrfs_search_slot_for_read() local
2289 * but in case the previous item is the last in a leaf, path points in btrfs_search_slot_for_read()
2290 * to the first free slot in the previous leaf, i.e. at an invalid in btrfs_search_slot_for_read()
2293 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2296 if (p->slots[0] >= btrfs_header_nritems(leaf)) { in btrfs_search_slot_for_read()
2317 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2318 if (p->slots[0] == btrfs_header_nritems(leaf)) in btrfs_search_slot_for_read()
2377 const struct extent_buffer *leaf = path->nodes[0]; in btrfs_get_next_valid_item() local
2380 if (slot >= btrfs_header_nritems(leaf)) { in btrfs_get_next_valid_item()
2382 * If we've reached the last slot in this leaf we need in btrfs_get_next_valid_item()
2383 * to go to the next leaf and reset the path. in btrfs_get_next_valid_item()
2391 btrfs_item_key_to_cpu(leaf, key, slot); in btrfs_get_next_valid_item()
2401 * fixing up pointers when a given leaf/node is not in slot 0 of the
2489 * Leaf @left | Leaf @right
2493 * Key f6 in leaf @left itself is valid, but not valid when the next
2494 * key in leaf @right is 7.
2883 * how many bytes are required to store the items in a leaf. start
2884 * and nr indicate which items in the leaf to check. This totals up the
2903 * The space between the end of the leaf items and
2904 * the start of the leaf data. IOW, how much room
2905 * the leaf has left for both items and data
2907 noinline int btrfs_leaf_free_space(struct extent_buffer *leaf) in btrfs_leaf_free_space() argument
2909 struct btrfs_fs_info *fs_info = leaf->fs_info; in btrfs_leaf_free_space()
2910 int nritems = btrfs_header_nritems(leaf); in btrfs_leaf_free_space()
2913 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); in btrfs_leaf_free_space()
2916 "leaf free space ret %d, leaf data size %lu, used %d nritems %d", in btrfs_leaf_free_space()
2919 leaf_space_used(leaf, 0, nritems), nritems); in btrfs_leaf_free_space()
3042 /* then fixup the leaf pointer in the path */ in __push_leaf_right()
3064 * push some data in the path leaf to the right, trying to free up at
3070 * this will push starting from min_slot to the end of the leaf. It won't
3126 /* Key greater than all keys in the leaf, right neighbor has in push_leaf_right()
3127 * enough room for it and we're not emptying our leaf to delete in push_leaf_right()
3129 * no need to touch/dirty our left leaf. */ in push_leaf_right()
3147 * push some data in the path leaf to the left, trying to free up at
3150 * max_slot can put a limit on how far into the leaf we'll push items. The
3272 /* then fixup the leaf pointer in the path */ in __push_leaf_left()
3293 * push some data in the path leaf to the left, trying to free up at
3296 * max_slot can put a limit on how far into the leaf we'll push items. The
3363 * split the path's leaf in two, making sure there is at least data_size
3364 * available for the resulting leaf level of the path.
3426 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3427 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3451 * right leaf in push_for_double_split()
3462 * our goal is to get our slot at the start or end of a leaf. If in push_for_double_split()
3471 /* try to push all the items before our slot into the next leaf */ in push_for_double_split()
3489 * split the path's leaf in two, making sure there is at least data_size
3490 * available for the resulting leaf level of the path.
3639 * We create a new leaf 'right' for the required ins_len and in split_leaf()
3640 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying in split_leaf()
3669 struct extent_buffer *leaf; in setup_leaf_for_split() local
3675 leaf = path->nodes[0]; in setup_leaf_for_split()
3676 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in setup_leaf_for_split()
3681 if (btrfs_leaf_free_space(leaf) >= ins_len) in setup_leaf_for_split()
3684 item_size = btrfs_item_size(leaf, path->slots[0]); in setup_leaf_for_split()
3686 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3688 extent_len = btrfs_file_extent_num_bytes(leaf, fi); in setup_leaf_for_split()
3702 leaf = path->nodes[0]; in setup_leaf_for_split()
3704 if (item_size != btrfs_item_size(leaf, path->slots[0])) in setup_leaf_for_split()
3707 /* the leaf has changed, it now has room. return now */ in setup_leaf_for_split()
3712 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3714 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) in setup_leaf_for_split()
3734 struct extent_buffer *leaf; in split_item() local
3742 leaf = path->nodes[0]; in split_item()
3743 BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)); in split_item()
3746 orig_offset = btrfs_item_offset(leaf, path->slots[0]); in split_item()
3747 item_size = btrfs_item_size(leaf, path->slots[0]); in split_item()
3753 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, in split_item()
3757 nritems = btrfs_header_nritems(leaf); in split_item()
3760 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), in split_item()
3766 btrfs_set_item_key(leaf, &disk_key, slot); in split_item()
3768 btrfs_set_item_offset(leaf, slot, orig_offset); in split_item()
3769 btrfs_set_item_size(leaf, slot, item_size - split_offset); in split_item()
3771 btrfs_set_item_offset(leaf, orig_slot, in split_item()
3773 btrfs_set_item_size(leaf, orig_slot, split_offset); in split_item()
3775 btrfs_set_header_nritems(leaf, nritems + 1); in split_item()
3778 write_extent_buffer(leaf, buf, in split_item()
3779 btrfs_item_ptr_offset(leaf, path->slots[0]), in split_item()
3783 write_extent_buffer(leaf, buf + split_offset, in split_item()
3784 btrfs_item_ptr_offset(leaf, slot), in split_item()
3786 btrfs_mark_buffer_dirty(leaf); in split_item()
3788 BUG_ON(btrfs_leaf_free_space(leaf) < 0); in split_item()
3806 * leaf the entire time.
3833 struct extent_buffer *leaf; in btrfs_truncate_item() local
3842 leaf = path->nodes[0]; in btrfs_truncate_item()
3845 old_size = btrfs_item_size(leaf, slot); in btrfs_truncate_item()
3849 nritems = btrfs_header_nritems(leaf); in btrfs_truncate_item()
3850 data_end = leaf_data_end(leaf); in btrfs_truncate_item()
3852 old_data_start = btrfs_item_offset(leaf, slot); in btrfs_truncate_item()
3863 btrfs_init_map_token(&token, leaf); in btrfs_truncate_item()
3873 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_truncate_item()
3880 btrfs_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
3886 fi = btrfs_item_ptr(leaf, slot, in btrfs_truncate_item()
3891 if (btrfs_file_extent_type(leaf, fi) == in btrfs_truncate_item()
3893 ptr = btrfs_item_ptr_offset(leaf, slot); in btrfs_truncate_item()
3894 memmove_extent_buffer(leaf, ptr, in btrfs_truncate_item()
3900 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_truncate_item()
3906 btrfs_set_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
3911 btrfs_set_item_size(leaf, slot, new_size); in btrfs_truncate_item()
3912 btrfs_mark_buffer_dirty(leaf); in btrfs_truncate_item()
3914 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_truncate_item()
3915 btrfs_print_leaf(leaf); in btrfs_truncate_item()
3926 struct extent_buffer *leaf; in btrfs_extend_item() local
3934 leaf = path->nodes[0]; in btrfs_extend_item()
3936 nritems = btrfs_header_nritems(leaf); in btrfs_extend_item()
3937 data_end = leaf_data_end(leaf); in btrfs_extend_item()
3939 if (btrfs_leaf_free_space(leaf) < data_size) { in btrfs_extend_item()
3940 btrfs_print_leaf(leaf); in btrfs_extend_item()
3944 old_data = btrfs_item_data_end(leaf, slot); in btrfs_extend_item()
3948 btrfs_print_leaf(leaf); in btrfs_extend_item()
3949 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", in btrfs_extend_item()
3958 btrfs_init_map_token(&token, leaf); in btrfs_extend_item()
3967 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_extend_item()
3972 old_size = btrfs_item_size(leaf, slot); in btrfs_extend_item()
3973 btrfs_set_item_size(leaf, slot, old_size + data_size); in btrfs_extend_item()
3974 btrfs_mark_buffer_dirty(leaf); in btrfs_extend_item()
3976 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_extend_item()
3977 btrfs_print_leaf(leaf); in btrfs_extend_item()
3984 * to a leaf. Main purpose is to save stack depth by doing the bulk of the work
3988 * @path: points to the leaf/slot where we are going to insert new items
3999 struct extent_buffer *leaf; in setup_items_for_insert() local
4007 * can use them while we modify the leaf. in setup_items_for_insert()
4015 leaf = path->nodes[0]; in setup_items_for_insert()
4018 nritems = btrfs_header_nritems(leaf); in setup_items_for_insert()
4019 data_end = leaf_data_end(leaf); in setup_items_for_insert()
4022 if (btrfs_leaf_free_space(leaf) < total_size) { in setup_items_for_insert()
4023 btrfs_print_leaf(leaf); in setup_items_for_insert()
4025 total_size, btrfs_leaf_free_space(leaf)); in setup_items_for_insert()
4029 btrfs_init_map_token(&token, leaf); in setup_items_for_insert()
4031 unsigned int old_data = btrfs_item_data_end(leaf, slot); in setup_items_for_insert()
4034 btrfs_print_leaf(leaf); in setup_items_for_insert()
4036 "item at slot %d with data offset %u beyond data end of leaf %u", in setup_items_for_insert()
4052 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + batch->nr), in setup_items_for_insert()
4057 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in setup_items_for_insert()
4067 btrfs_set_item_key(leaf, &disk_key, slot + i); in setup_items_for_insert()
4073 btrfs_set_header_nritems(leaf, nritems + batch->nr); in setup_items_for_insert()
4074 btrfs_mark_buffer_dirty(leaf); in setup_items_for_insert()
4076 if (btrfs_leaf_free_space(leaf) < 0) { in setup_items_for_insert()
4077 btrfs_print_leaf(leaf); in setup_items_for_insert()
4083 * Insert a new item into a leaf.
4086 * @path: A path pointing to the target leaf and slot.
4142 struct extent_buffer *leaf; in btrfs_insert_item() local
4150 leaf = path->nodes[0]; in btrfs_insert_item()
4151 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in btrfs_insert_item()
4152 write_extent_buffer(leaf, data, ptr, data_size); in btrfs_insert_item()
4153 btrfs_mark_buffer_dirty(leaf); in btrfs_insert_item()
4161 * It guarantees both items live in the same tree leaf and the new item is
4164 * This allows us to split a file extent in place, keeping a lock on the leaf
4172 struct extent_buffer *leaf; in btrfs_duplicate_item() local
4176 leaf = path->nodes[0]; in btrfs_duplicate_item()
4177 item_size = btrfs_item_size(leaf, path->slots[0]); in btrfs_duplicate_item()
4185 leaf = path->nodes[0]; in btrfs_duplicate_item()
4186 memcpy_extent_buffer(leaf, in btrfs_duplicate_item()
4187 btrfs_item_ptr_offset(leaf, path->slots[0]), in btrfs_duplicate_item()
4188 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), in btrfs_duplicate_item()
4228 /* just turn the root into a leaf and break */ in del_ptr()
4240 * a helper function to delete the leaf pointed to by path->slots[1] and
4243 * This deletes the pointer in path->nodes[1] and frees the leaf
4246 * The path must have already been setup for deleting the leaf, including
4252 struct extent_buffer *leaf) in btrfs_del_leaf() argument
4254 WARN_ON(btrfs_header_generation(leaf) != trans->transid); in btrfs_del_leaf()
4263 root_sub_used(root, leaf->len); in btrfs_del_leaf()
4265 atomic_inc(&leaf->refs); in btrfs_del_leaf()
4266 btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1); in btrfs_del_leaf()
4267 free_extent_buffer_stale(leaf); in btrfs_del_leaf()
4270 * delete the item at the leaf level in path. If that empties
4271 * the leaf, remove it from the tree
4277 struct extent_buffer *leaf; in btrfs_del_items() local
4282 leaf = path->nodes[0]; in btrfs_del_items()
4283 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4286 const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1); in btrfs_del_items()
4287 const int data_end = leaf_data_end(leaf); in btrfs_del_items()
4293 dsize += btrfs_item_size(leaf, slot + i); in btrfs_del_items()
4295 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_del_items()
4300 btrfs_init_map_token(&token, leaf); in btrfs_del_items()
4308 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), in btrfs_del_items()
4313 btrfs_set_header_nritems(leaf, nritems - nr); in btrfs_del_items()
4316 /* delete the leaf if we've emptied it */ in btrfs_del_items()
4318 if (leaf == root->node) { in btrfs_del_items()
4319 btrfs_set_header_level(leaf, 0); in btrfs_del_items()
4321 btrfs_clean_tree_block(leaf); in btrfs_del_items()
4322 btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4325 int used = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4329 btrfs_item_key(leaf, &disk_key, 0); in btrfs_del_items()
4334 * Try to delete the leaf if it is mostly empty. We do this by in btrfs_del_items()
4337 * not ideal, but future insertions might fill the leaf with more in btrfs_del_items()
4339 * leaf due to deletions on those leaves. in btrfs_del_items()
4345 * make sure the path still points to our leaf in btrfs_del_items()
4349 atomic_inc(&leaf->refs); in btrfs_del_items()
4352 * left neighbour leaf, and that's the first item. in btrfs_del_items()
4355 btrfs_item_size(leaf, 0); in btrfs_del_items()
4361 if (path->nodes[0] == leaf && in btrfs_del_items()
4362 btrfs_header_nritems(leaf)) { in btrfs_del_items()
4365 * leaf to its left neighbour, then attempt to in btrfs_del_items()
4369 * it's pointless to end up with a leaf having in btrfs_del_items()
4373 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4374 min_push_space = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4381 if (btrfs_header_nritems(leaf) == 0) { in btrfs_del_items()
4383 btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4384 free_extent_buffer(leaf); in btrfs_del_items()
4392 if (path->nodes[0] == leaf) in btrfs_del_items()
4393 btrfs_mark_buffer_dirty(leaf); in btrfs_del_items()
4394 free_extent_buffer(leaf); in btrfs_del_items()
4397 btrfs_mark_buffer_dirty(leaf); in btrfs_del_items()
4404 * search the tree again to find a leaf with lesser keys
4441 * item might have been pushed to the first slot (0) of the leaf we in btrfs_prev_leaf()
4443 * previous key can exist as the only element of a leaf (big fat item). in btrfs_prev_leaf()
4726 * This one should be returned as well, or we can get leaf corruption in btrfs_next_old_leaf()
4792 * itself waiting for the leaf we've currently in btrfs_next_old_leaf()
4864 struct extent_buffer *leaf; in btrfs_previous_item() local
4876 leaf = path->nodes[0]; in btrfs_previous_item()
4877 nritems = btrfs_header_nritems(leaf); in btrfs_previous_item()
4883 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_item()
4905 struct extent_buffer *leaf; in btrfs_previous_extent_item() local
4917 leaf = path->nodes[0]; in btrfs_previous_extent_item()
4918 nritems = btrfs_header_nritems(leaf); in btrfs_previous_extent_item()
4924 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_extent_item()