Lines Matching full:leaf
41 * The leaf data grows from end-to-front in the node. this returns the address
42 * of the start of the last item, which is the stop of the leaf data stack.
44 static unsigned int leaf_data_end(const struct extent_buffer *leaf) in leaf_data_end() argument
46 u32 nr = btrfs_header_nritems(leaf); in leaf_data_end()
49 return BTRFS_LEAF_DATA_SIZE(leaf->fs_info); in leaf_data_end()
50 return btrfs_item_offset(leaf, nr - 1); in leaf_data_end()
54 * Move data in a @leaf (using memmove, safe for overlapping ranges).
56 * @leaf: leaf that we're doing a memmove on
62 * the leaf. The btrfs_item offset's start directly after the header, so we
63 * have to adjust any offsets to account for the header in the leaf. This
66 static inline void memmove_leaf_data(const struct extent_buffer *leaf, in memmove_leaf_data() argument
71 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, 0) + dst_offset, in memmove_leaf_data()
72 btrfs_item_nr_offset(leaf, 0) + src_offset, len); in memmove_leaf_data()
78 * @dst: destination leaf that we're copying into
79 * @src: source leaf that we're copying from
85 * the leaf. The btrfs_item offset's start directly after the header, so we
86 * have to adjust any offsets to account for the header in the leaf. This
99 * Move items in a @leaf (using memmove).
101 * @dst: destination leaf for the items
107 * appropriate offsets into the leaf from the item numbers.
109 static inline void memmove_leaf_items(const struct extent_buffer *leaf, in memmove_leaf_items() argument
112 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, dst_item), in memmove_leaf_items()
113 btrfs_item_nr_offset(leaf, src_item), in memmove_leaf_items()
120 * @dst: destination leaf for the items
121 * @src: source leaf for the items
127 * appropriate offsets into the leaf from the item numbers.
1825 struct extent_buffer *leaf = path->nodes[0]; in search_leaf() local
1832 * If we are doing an insertion, the leaf has enough free space and the in search_leaf()
1835 * binary search on the leaf (with search_for_key_slot()), allowing other in search_leaf()
1840 * Cache the leaf free space, since we will need it later and it in search_leaf()
1843 leaf_free_space = btrfs_leaf_free_space(leaf); in search_leaf()
1846 * !path->locks[1] means we have a single node tree, the leaf is in search_leaf()
1852 ASSERT(btrfs_header_nritems(leaf) > 0); in search_leaf()
1853 btrfs_item_key(leaf, &first_key, 0); in search_leaf()
1874 * leaf and there's no need to split the leaf. in search_leaf()
1907 ret = search_for_key_slot(leaf, search_low_slot, key, in search_leaf()
1920 * accounts the size btrfs_item, deduct it here so leaf space in search_leaf()
1968 * If @key is found, 0 is returned and you can find the item in the leaf level
1971 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2326 * Search the tree again to find a leaf with smaller keys.
2363 * Previous key not found. Even if we were at slot 0 of the leaf we had in btrfs_prev_leaf()
2367 * sibling leaf into the front of the leaf we had due to an insertion in btrfs_prev_leaf()
2394 * item might have been pushed to the first slot (0) of the leaf we in btrfs_prev_leaf()
2396 * previous key can exist as the only element of a leaf (big fat item). in btrfs_prev_leaf()
2424 struct extent_buffer *leaf; in btrfs_search_slot_for_read() local
2433 * but in case the previous item is the last in a leaf, path points in btrfs_search_slot_for_read()
2434 * to the first free slot in the previous leaf, i.e. at an invalid in btrfs_search_slot_for_read()
2437 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2440 if (p->slots[0] >= btrfs_header_nritems(leaf)) { in btrfs_search_slot_for_read()
2461 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2462 if (p->slots[0] == btrfs_header_nritems(leaf)) in btrfs_search_slot_for_read()
2534 * fixing up pointers when a given leaf/node is not in slot 0 of the
2624 * Leaf @left | Leaf @right
2628 * Key f6 in leaf @left itself is valid, but not valid when the next
2629 * key in leaf @right is 7.
3048 * how many bytes are required to store the items in a leaf. start
3049 * and nr indicate which items in the leaf to check. This totals up the
3068 * The space between the end of the leaf items and
3069 * the start of the leaf data. IOW, how much room
3070 * the leaf has left for both items and data
3072 int btrfs_leaf_free_space(const struct extent_buffer *leaf) in btrfs_leaf_free_space() argument
3074 struct btrfs_fs_info *fs_info = leaf->fs_info; in btrfs_leaf_free_space()
3075 int nritems = btrfs_header_nritems(leaf); in btrfs_leaf_free_space()
3078 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); in btrfs_leaf_free_space()
3081 "leaf free space ret %d, leaf data size %lu, used %d nritems %d", in btrfs_leaf_free_space()
3084 leaf_space_used(leaf, 0, nritems), nritems); in btrfs_leaf_free_space()
3200 /* then fixup the leaf pointer in the path */ in __push_leaf_right()
3222 * push some data in the path leaf to the right, trying to free up at
3228 * this will push starting from min_slot to the end of the leaf. It won't
3281 /* Key greater than all keys in the leaf, right neighbor has in push_leaf_right()
3282 * enough room for it and we're not emptying our leaf to delete in push_leaf_right()
3284 * no need to touch/dirty our left leaf. */ in push_leaf_right()
3302 * push some data in the path leaf to the left, trying to free up at
3305 * max_slot can put a limit on how far into the leaf we'll push items. The
3419 /* then fixup the leaf pointer in the path */ in __push_leaf_left()
3440 * push some data in the path leaf to the left, trying to free up at
3443 * max_slot can put a limit on how far into the leaf we'll push items. The
3506 * split the path's leaf in two, making sure there is at least data_size
3507 * available for the resulting leaf level of the path.
3570 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3571 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3595 * right leaf in push_for_double_split()
3606 * our goal is to get our slot at the start or end of a leaf. If in push_for_double_split()
3615 /* try to push all the items before our slot into the next leaf */ in push_for_double_split()
3633 * split the path's leaf in two, making sure there is at least data_size
3634 * available for the resulting leaf level of the path.
3793 * We create a new leaf 'right' for the required ins_len and in split_leaf()
3794 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying in split_leaf()
3828 struct extent_buffer *leaf; in setup_leaf_for_split() local
3834 leaf = path->nodes[0]; in setup_leaf_for_split()
3835 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in setup_leaf_for_split()
3841 if (btrfs_leaf_free_space(leaf) >= ins_len) in setup_leaf_for_split()
3844 item_size = btrfs_item_size(leaf, path->slots[0]); in setup_leaf_for_split()
3846 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3848 extent_len = btrfs_file_extent_num_bytes(leaf, fi); in setup_leaf_for_split()
3862 leaf = path->nodes[0]; in setup_leaf_for_split()
3864 if (item_size != btrfs_item_size(leaf, path->slots[0])) in setup_leaf_for_split()
3867 /* the leaf has changed, it now has room. return now */ in setup_leaf_for_split()
3872 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3874 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) in setup_leaf_for_split()
3895 struct extent_buffer *leaf; in split_item() local
3903 leaf = path->nodes[0]; in split_item()
3906 * setup_leaf_for_split() to make room for the new item in the leaf. in split_item()
3908 if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item))) in split_item()
3912 orig_offset = btrfs_item_offset(leaf, path->slots[0]); in split_item()
3913 item_size = btrfs_item_size(leaf, path->slots[0]); in split_item()
3919 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, in split_item()
3923 nritems = btrfs_header_nritems(leaf); in split_item()
3926 memmove_leaf_items(leaf, slot + 1, slot, nritems - slot); in split_item()
3930 btrfs_set_item_key(leaf, &disk_key, slot); in split_item()
3932 btrfs_set_item_offset(leaf, slot, orig_offset); in split_item()
3933 btrfs_set_item_size(leaf, slot, item_size - split_offset); in split_item()
3935 btrfs_set_item_offset(leaf, orig_slot, in split_item()
3937 btrfs_set_item_size(leaf, orig_slot, split_offset); in split_item()
3939 btrfs_set_header_nritems(leaf, nritems + 1); in split_item()
3942 write_extent_buffer(leaf, buf, in split_item()
3943 btrfs_item_ptr_offset(leaf, path->slots[0]), in split_item()
3947 write_extent_buffer(leaf, buf + split_offset, in split_item()
3948 btrfs_item_ptr_offset(leaf, slot), in split_item()
3950 btrfs_mark_buffer_dirty(trans, leaf); in split_item()
3952 BUG_ON(btrfs_leaf_free_space(leaf) < 0); in split_item()
3970 * leaf the entire time.
3998 struct extent_buffer *leaf; in btrfs_truncate_item() local
4007 leaf = path->nodes[0]; in btrfs_truncate_item()
4010 old_size = btrfs_item_size(leaf, slot); in btrfs_truncate_item()
4014 nritems = btrfs_header_nritems(leaf); in btrfs_truncate_item()
4015 data_end = leaf_data_end(leaf); in btrfs_truncate_item()
4017 old_data_start = btrfs_item_offset(leaf, slot); in btrfs_truncate_item()
4028 btrfs_init_map_token(&token, leaf); in btrfs_truncate_item()
4038 memmove_leaf_data(leaf, data_end + size_diff, data_end, in btrfs_truncate_item()
4044 btrfs_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
4050 fi = btrfs_item_ptr(leaf, slot, in btrfs_truncate_item()
4055 if (btrfs_file_extent_type(leaf, fi) == in btrfs_truncate_item()
4057 ptr = btrfs_item_ptr_offset(leaf, slot); in btrfs_truncate_item()
4058 memmove_extent_buffer(leaf, ptr, in btrfs_truncate_item()
4064 memmove_leaf_data(leaf, data_end + size_diff, data_end, in btrfs_truncate_item()
4069 btrfs_set_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
4074 btrfs_set_item_size(leaf, slot, new_size); in btrfs_truncate_item()
4075 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_truncate_item()
4077 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_truncate_item()
4078 btrfs_print_leaf(leaf); in btrfs_truncate_item()
4090 struct extent_buffer *leaf; in btrfs_extend_item() local
4098 leaf = path->nodes[0]; in btrfs_extend_item()
4100 nritems = btrfs_header_nritems(leaf); in btrfs_extend_item()
4101 data_end = leaf_data_end(leaf); in btrfs_extend_item()
4103 if (btrfs_leaf_free_space(leaf) < data_size) { in btrfs_extend_item()
4104 btrfs_print_leaf(leaf); in btrfs_extend_item()
4108 old_data = btrfs_item_data_end(leaf, slot); in btrfs_extend_item()
4112 btrfs_print_leaf(leaf); in btrfs_extend_item()
4113 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", in btrfs_extend_item()
4122 btrfs_init_map_token(&token, leaf); in btrfs_extend_item()
4131 memmove_leaf_data(leaf, data_end - data_size, data_end, in btrfs_extend_item()
4135 old_size = btrfs_item_size(leaf, slot); in btrfs_extend_item()
4136 btrfs_set_item_size(leaf, slot, old_size + data_size); in btrfs_extend_item()
4137 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_extend_item()
4139 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_extend_item()
4140 btrfs_print_leaf(leaf); in btrfs_extend_item()
4150 * @path: points to the leaf/slot where we are going to insert new items
4165 struct extent_buffer *leaf; in setup_items_for_insert() local
4173 * can use them while we modify the leaf. in setup_items_for_insert()
4181 leaf = path->nodes[0]; in setup_items_for_insert()
4184 nritems = btrfs_header_nritems(leaf); in setup_items_for_insert()
4185 data_end = leaf_data_end(leaf); in setup_items_for_insert()
4188 if (btrfs_leaf_free_space(leaf) < total_size) { in setup_items_for_insert()
4189 btrfs_print_leaf(leaf); in setup_items_for_insert()
4191 total_size, btrfs_leaf_free_space(leaf)); in setup_items_for_insert()
4195 btrfs_init_map_token(&token, leaf); in setup_items_for_insert()
4197 unsigned int old_data = btrfs_item_data_end(leaf, slot); in setup_items_for_insert()
4200 btrfs_print_leaf(leaf); in setup_items_for_insert()
4202 "item at slot %d with data offset %u beyond data end of leaf %u", in setup_items_for_insert()
4218 memmove_leaf_items(leaf, slot + batch->nr, slot, nritems - slot); in setup_items_for_insert()
4221 memmove_leaf_data(leaf, data_end - batch->total_data_size, in setup_items_for_insert()
4229 btrfs_set_item_key(leaf, &disk_key, slot + i); in setup_items_for_insert()
4235 btrfs_set_header_nritems(leaf, nritems + batch->nr); in setup_items_for_insert()
4236 btrfs_mark_buffer_dirty(trans, leaf); in setup_items_for_insert()
4238 if (btrfs_leaf_free_space(leaf) < 0) { in setup_items_for_insert()
4239 btrfs_print_leaf(leaf); in setup_items_for_insert()
4245 * Insert a new item into a leaf.
4249 * @path: A path pointing to the target leaf and slot.
4310 struct extent_buffer *leaf; in btrfs_insert_item() local
4318 leaf = path->nodes[0]; in btrfs_insert_item()
4319 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in btrfs_insert_item()
4320 write_extent_buffer(leaf, data, ptr, data_size); in btrfs_insert_item()
4321 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_insert_item()
4329 * It guarantees both items live in the same tree leaf and the new item is
4332 * This allows us to split a file extent in place, keeping a lock on the leaf
4340 struct extent_buffer *leaf; in btrfs_duplicate_item() local
4344 leaf = path->nodes[0]; in btrfs_duplicate_item()
4345 item_size = btrfs_item_size(leaf, path->slots[0]); in btrfs_duplicate_item()
4353 leaf = path->nodes[0]; in btrfs_duplicate_item()
4354 memcpy_extent_buffer(leaf, in btrfs_duplicate_item()
4355 btrfs_item_ptr_offset(leaf, path->slots[0]), in btrfs_duplicate_item()
4356 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), in btrfs_duplicate_item()
4404 /* just turn the root into a leaf and break */ in btrfs_del_ptr()
4417 * a helper function to delete the leaf pointed to by path->slots[1] and
4420 * This deletes the pointer in path->nodes[1] and frees the leaf
4423 * The path must have already been setup for deleting the leaf, including
4429 struct extent_buffer *leaf) in btrfs_del_leaf() argument
4433 WARN_ON(btrfs_header_generation(leaf) != trans->transid); in btrfs_del_leaf()
4446 atomic_inc(&leaf->refs); in btrfs_del_leaf()
4447 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1); in btrfs_del_leaf()
4448 free_extent_buffer_stale(leaf); in btrfs_del_leaf()
4455 * delete the item at the leaf level in path. If that empties
4456 * the leaf, remove it from the tree
4462 struct extent_buffer *leaf; in btrfs_del_items() local
4467 leaf = path->nodes[0]; in btrfs_del_items()
4468 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4471 const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1); in btrfs_del_items()
4472 const int data_end = leaf_data_end(leaf); in btrfs_del_items()
4478 dsize += btrfs_item_size(leaf, slot + i); in btrfs_del_items()
4480 memmove_leaf_data(leaf, data_end + dsize, data_end, in btrfs_del_items()
4483 btrfs_init_map_token(&token, leaf); in btrfs_del_items()
4491 memmove_leaf_items(leaf, slot, slot + nr, nritems - slot - nr); in btrfs_del_items()
4493 btrfs_set_header_nritems(leaf, nritems - nr); in btrfs_del_items()
4496 /* delete the leaf if we've emptied it */ in btrfs_del_items()
4498 if (leaf == root->node) { in btrfs_del_items()
4499 btrfs_set_header_level(leaf, 0); in btrfs_del_items()
4501 btrfs_clear_buffer_dirty(trans, leaf); in btrfs_del_items()
4502 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4507 int used = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4511 btrfs_item_key(leaf, &disk_key, 0); in btrfs_del_items()
4516 * Try to delete the leaf if it is mostly empty. We do this by in btrfs_del_items()
4519 * not ideal, but future insertions might fill the leaf with more in btrfs_del_items()
4521 * leaf due to deletions on those leaves. in btrfs_del_items()
4527 * make sure the path still points to our leaf in btrfs_del_items()
4531 atomic_inc(&leaf->refs); in btrfs_del_items()
4534 * left neighbour leaf, and that's the first item. in btrfs_del_items()
4537 btrfs_item_size(leaf, 0); in btrfs_del_items()
4543 if (path->nodes[0] == leaf && in btrfs_del_items()
4544 btrfs_header_nritems(leaf)) { in btrfs_del_items()
4547 * leaf to its left neighbour, then attempt to in btrfs_del_items()
4551 * it's pointless to end up with a leaf having in btrfs_del_items()
4555 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4556 min_push_space = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4563 if (btrfs_header_nritems(leaf) == 0) { in btrfs_del_items()
4565 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4568 free_extent_buffer(leaf); in btrfs_del_items()
4576 if (path->nodes[0] == leaf) in btrfs_del_items()
4577 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_del_items()
4578 free_extent_buffer(leaf); in btrfs_del_items()
4581 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_del_items()
4860 * This one should be returned as well, or we can get leaf corruption in btrfs_next_old_leaf()
4925 * itself waiting for the leaf we've currently in btrfs_next_old_leaf()
5004 struct extent_buffer *leaf; in btrfs_previous_item() local
5016 leaf = path->nodes[0]; in btrfs_previous_item()
5017 nritems = btrfs_header_nritems(leaf); in btrfs_previous_item()
5023 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_item()
5045 struct extent_buffer *leaf; in btrfs_previous_extent_item() local
5057 leaf = path->nodes[0]; in btrfs_previous_extent_item()
5058 nritems = btrfs_header_nritems(leaf); in btrfs_previous_extent_item()
5064 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_extent_item()