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.
1857 struct extent_buffer *leaf = path->nodes[0]; in search_leaf() local
1864 * If we are doing an insertion, the leaf has enough free space and the in search_leaf()
1867 * binary search on the leaf (with search_for_key_slot()), allowing other in search_leaf()
1872 * Cache the leaf free space, since we will need it later and it in search_leaf()
1875 leaf_free_space = btrfs_leaf_free_space(leaf); in search_leaf()
1878 * !path->locks[1] means we have a single node tree, the leaf is in search_leaf()
1884 ASSERT(btrfs_header_nritems(leaf) > 0); in search_leaf()
1885 btrfs_item_key(leaf, &first_key, 0); in search_leaf()
1906 * leaf and there's no need to split the leaf. in search_leaf()
1939 ret = search_for_key_slot(leaf, search_low_slot, key, in search_leaf()
1952 * accounts the size btrfs_item, deduct it here so leaf space in search_leaf()
2000 * If @key is found, 0 is returned and you can find the item in the leaf level
2003 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2354 * Search the tree again to find a leaf with smaller keys.
2391 * Previous key not found. Even if we were at slot 0 of the leaf we had in btrfs_prev_leaf()
2395 * sibling leaf into the front of the leaf we had due to an insertion in btrfs_prev_leaf()
2422 * item might have been pushed to the first slot (0) of the leaf we in btrfs_prev_leaf()
2424 * previous key can exist as the only element of a leaf (big fat item). in btrfs_prev_leaf()
2452 struct extent_buffer *leaf; in btrfs_search_slot_for_read() local
2461 * but in case the previous item is the last in a leaf, path points in btrfs_search_slot_for_read()
2462 * to the first free slot in the previous leaf, i.e. at an invalid in btrfs_search_slot_for_read()
2465 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2468 if (p->slots[0] >= btrfs_header_nritems(leaf)) { in btrfs_search_slot_for_read()
2489 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2490 if (p->slots[0] == btrfs_header_nritems(leaf)) in btrfs_search_slot_for_read()
2562 * fixing up pointers when a given leaf/node is not in slot 0 of the
2652 * Leaf @left | Leaf @right
2656 * Key f6 in leaf @left itself is valid, but not valid when the next
2657 * key in leaf @right is 7.
3076 * how many bytes are required to store the items in a leaf. start
3077 * and nr indicate which items in the leaf to check. This totals up the
3096 * The space between the end of the leaf items and
3097 * the start of the leaf data. IOW, how much room
3098 * the leaf has left for both items and data
3100 int btrfs_leaf_free_space(const struct extent_buffer *leaf) in btrfs_leaf_free_space() argument
3102 struct btrfs_fs_info *fs_info = leaf->fs_info; in btrfs_leaf_free_space()
3103 int nritems = btrfs_header_nritems(leaf); in btrfs_leaf_free_space()
3106 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); in btrfs_leaf_free_space()
3109 "leaf free space ret %d, leaf data size %lu, used %d nritems %d", in btrfs_leaf_free_space()
3112 leaf_space_used(leaf, 0, nritems), nritems); in btrfs_leaf_free_space()
3228 /* then fixup the leaf pointer in the path */ in __push_leaf_right()
3250 * push some data in the path leaf to the right, trying to free up at
3256 * this will push starting from min_slot to the end of the leaf. It won't
3309 /* Key greater than all keys in the leaf, right neighbor has in push_leaf_right()
3310 * enough room for it and we're not emptying our leaf to delete in push_leaf_right()
3312 * no need to touch/dirty our left leaf. */ in push_leaf_right()
3330 * push some data in the path leaf to the left, trying to free up at
3333 * max_slot can put a limit on how far into the leaf we'll push items. The
3447 /* then fixup the leaf pointer in the path */ in __push_leaf_left()
3468 * push some data in the path leaf to the left, trying to free up at
3471 * max_slot can put a limit on how far into the leaf we'll push items. The
3534 * split the path's leaf in two, making sure there is at least data_size
3535 * available for the resulting leaf level of the path.
3598 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3599 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3623 * right leaf in push_for_double_split()
3634 * our goal is to get our slot at the start or end of a leaf. If in push_for_double_split()
3643 /* try to push all the items before our slot into the next leaf */ in push_for_double_split()
3661 * split the path's leaf in two, making sure there is at least data_size
3662 * available for the resulting leaf level of the path.
3821 * We create a new leaf 'right' for the required ins_len and in split_leaf()
3822 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying in split_leaf()
3856 struct extent_buffer *leaf; in setup_leaf_for_split() local
3862 leaf = path->nodes[0]; in setup_leaf_for_split()
3863 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in setup_leaf_for_split()
3868 if (btrfs_leaf_free_space(leaf) >= ins_len) in setup_leaf_for_split()
3871 item_size = btrfs_item_size(leaf, path->slots[0]); in setup_leaf_for_split()
3873 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3875 extent_len = btrfs_file_extent_num_bytes(leaf, fi); in setup_leaf_for_split()
3889 leaf = path->nodes[0]; in setup_leaf_for_split()
3891 if (item_size != btrfs_item_size(leaf, path->slots[0])) in setup_leaf_for_split()
3894 /* the leaf has changed, it now has room. return now */ in setup_leaf_for_split()
3899 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3901 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) in setup_leaf_for_split()
3922 struct extent_buffer *leaf; in split_item() local
3930 leaf = path->nodes[0]; in split_item()
3933 * setup_leaf_for_split() to make room for the new item in the leaf. in split_item()
3935 if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item))) in split_item()
3939 orig_offset = btrfs_item_offset(leaf, path->slots[0]); in split_item()
3940 item_size = btrfs_item_size(leaf, path->slots[0]); in split_item()
3946 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, in split_item()
3950 nritems = btrfs_header_nritems(leaf); in split_item()
3953 memmove_leaf_items(leaf, slot + 1, slot, nritems - slot); in split_item()
3957 btrfs_set_item_key(leaf, &disk_key, slot); in split_item()
3959 btrfs_set_item_offset(leaf, slot, orig_offset); in split_item()
3960 btrfs_set_item_size(leaf, slot, item_size - split_offset); in split_item()
3962 btrfs_set_item_offset(leaf, orig_slot, in split_item()
3964 btrfs_set_item_size(leaf, orig_slot, split_offset); in split_item()
3966 btrfs_set_header_nritems(leaf, nritems + 1); in split_item()
3969 write_extent_buffer(leaf, buf, in split_item()
3970 btrfs_item_ptr_offset(leaf, path->slots[0]), in split_item()
3974 write_extent_buffer(leaf, buf + split_offset, in split_item()
3975 btrfs_item_ptr_offset(leaf, slot), in split_item()
3977 btrfs_mark_buffer_dirty(trans, leaf); in split_item()
3979 BUG_ON(btrfs_leaf_free_space(leaf) < 0); in split_item()
3997 * leaf the entire time.
4025 struct extent_buffer *leaf; in btrfs_truncate_item() local
4034 leaf = path->nodes[0]; in btrfs_truncate_item()
4037 old_size = btrfs_item_size(leaf, slot); in btrfs_truncate_item()
4041 nritems = btrfs_header_nritems(leaf); in btrfs_truncate_item()
4042 data_end = leaf_data_end(leaf); in btrfs_truncate_item()
4044 old_data_start = btrfs_item_offset(leaf, slot); in btrfs_truncate_item()
4055 btrfs_init_map_token(&token, leaf); in btrfs_truncate_item()
4065 memmove_leaf_data(leaf, data_end + size_diff, data_end, in btrfs_truncate_item()
4071 btrfs_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
4077 fi = btrfs_item_ptr(leaf, slot, in btrfs_truncate_item()
4082 if (btrfs_file_extent_type(leaf, fi) == in btrfs_truncate_item()
4084 ptr = btrfs_item_ptr_offset(leaf, slot); in btrfs_truncate_item()
4085 memmove_extent_buffer(leaf, ptr, in btrfs_truncate_item()
4091 memmove_leaf_data(leaf, data_end + size_diff, data_end, in btrfs_truncate_item()
4096 btrfs_set_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
4101 btrfs_set_item_size(leaf, slot, new_size); in btrfs_truncate_item()
4102 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_truncate_item()
4104 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_truncate_item()
4105 btrfs_print_leaf(leaf); in btrfs_truncate_item()
4117 struct extent_buffer *leaf; in btrfs_extend_item() local
4125 leaf = path->nodes[0]; in btrfs_extend_item()
4127 nritems = btrfs_header_nritems(leaf); in btrfs_extend_item()
4128 data_end = leaf_data_end(leaf); in btrfs_extend_item()
4130 if (btrfs_leaf_free_space(leaf) < data_size) { in btrfs_extend_item()
4131 btrfs_print_leaf(leaf); in btrfs_extend_item()
4135 old_data = btrfs_item_data_end(leaf, slot); in btrfs_extend_item()
4139 btrfs_print_leaf(leaf); in btrfs_extend_item()
4140 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", in btrfs_extend_item()
4149 btrfs_init_map_token(&token, leaf); in btrfs_extend_item()
4158 memmove_leaf_data(leaf, data_end - data_size, data_end, in btrfs_extend_item()
4162 old_size = btrfs_item_size(leaf, slot); in btrfs_extend_item()
4163 btrfs_set_item_size(leaf, slot, old_size + data_size); in btrfs_extend_item()
4164 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_extend_item()
4166 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_extend_item()
4167 btrfs_print_leaf(leaf); in btrfs_extend_item()
4177 * @path: points to the leaf/slot where we are going to insert new items
4192 struct extent_buffer *leaf; in setup_items_for_insert() local
4200 * can use them while we modify the leaf. in setup_items_for_insert()
4208 leaf = path->nodes[0]; in setup_items_for_insert()
4211 nritems = btrfs_header_nritems(leaf); in setup_items_for_insert()
4212 data_end = leaf_data_end(leaf); in setup_items_for_insert()
4215 if (btrfs_leaf_free_space(leaf) < total_size) { in setup_items_for_insert()
4216 btrfs_print_leaf(leaf); in setup_items_for_insert()
4218 total_size, btrfs_leaf_free_space(leaf)); in setup_items_for_insert()
4222 btrfs_init_map_token(&token, leaf); in setup_items_for_insert()
4224 unsigned int old_data = btrfs_item_data_end(leaf, slot); in setup_items_for_insert()
4227 btrfs_print_leaf(leaf); in setup_items_for_insert()
4229 "item at slot %d with data offset %u beyond data end of leaf %u", in setup_items_for_insert()
4245 memmove_leaf_items(leaf, slot + batch->nr, slot, nritems - slot); in setup_items_for_insert()
4248 memmove_leaf_data(leaf, data_end - batch->total_data_size, in setup_items_for_insert()
4256 btrfs_set_item_key(leaf, &disk_key, slot + i); in setup_items_for_insert()
4262 btrfs_set_header_nritems(leaf, nritems + batch->nr); in setup_items_for_insert()
4263 btrfs_mark_buffer_dirty(trans, leaf); in setup_items_for_insert()
4265 if (btrfs_leaf_free_space(leaf) < 0) { in setup_items_for_insert()
4266 btrfs_print_leaf(leaf); in setup_items_for_insert()
4272 * Insert a new item into a leaf.
4276 * @path: A path pointing to the target leaf and slot.
4337 struct extent_buffer *leaf; in btrfs_insert_item() local
4345 leaf = path->nodes[0]; in btrfs_insert_item()
4346 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in btrfs_insert_item()
4347 write_extent_buffer(leaf, data, ptr, data_size); in btrfs_insert_item()
4348 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_insert_item()
4356 * It guarantees both items live in the same tree leaf and the new item is
4359 * This allows us to split a file extent in place, keeping a lock on the leaf
4367 struct extent_buffer *leaf; in btrfs_duplicate_item() local
4371 leaf = path->nodes[0]; in btrfs_duplicate_item()
4372 item_size = btrfs_item_size(leaf, path->slots[0]); in btrfs_duplicate_item()
4380 leaf = path->nodes[0]; in btrfs_duplicate_item()
4381 memcpy_extent_buffer(leaf, in btrfs_duplicate_item()
4382 btrfs_item_ptr_offset(leaf, path->slots[0]), in btrfs_duplicate_item()
4383 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), in btrfs_duplicate_item()
4431 /* just turn the root into a leaf and break */ in btrfs_del_ptr()
4444 * a helper function to delete the leaf pointed to by path->slots[1] and
4447 * This deletes the pointer in path->nodes[1] and frees the leaf
4450 * The path must have already been setup for deleting the leaf, including
4456 struct extent_buffer *leaf) in btrfs_del_leaf() argument
4460 WARN_ON(btrfs_header_generation(leaf) != trans->transid); in btrfs_del_leaf()
4473 atomic_inc(&leaf->refs); in btrfs_del_leaf()
4474 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1); in btrfs_del_leaf()
4475 free_extent_buffer_stale(leaf); in btrfs_del_leaf()
4482 * delete the item at the leaf level in path. If that empties
4483 * the leaf, remove it from the tree
4489 struct extent_buffer *leaf; in btrfs_del_items() local
4494 leaf = path->nodes[0]; in btrfs_del_items()
4495 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4498 const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1); in btrfs_del_items()
4499 const int data_end = leaf_data_end(leaf); in btrfs_del_items()
4505 dsize += btrfs_item_size(leaf, slot + i); in btrfs_del_items()
4507 memmove_leaf_data(leaf, data_end + dsize, data_end, in btrfs_del_items()
4510 btrfs_init_map_token(&token, leaf); in btrfs_del_items()
4518 memmove_leaf_items(leaf, slot, slot + nr, nritems - slot - nr); in btrfs_del_items()
4520 btrfs_set_header_nritems(leaf, nritems - nr); in btrfs_del_items()
4523 /* delete the leaf if we've emptied it */ in btrfs_del_items()
4525 if (leaf == root->node) { in btrfs_del_items()
4526 btrfs_set_header_level(leaf, 0); in btrfs_del_items()
4528 btrfs_clear_buffer_dirty(trans, leaf); in btrfs_del_items()
4529 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4534 int used = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4538 btrfs_item_key(leaf, &disk_key, 0); in btrfs_del_items()
4543 * Try to delete the leaf if it is mostly empty. We do this by in btrfs_del_items()
4546 * not ideal, but future insertions might fill the leaf with more in btrfs_del_items()
4548 * leaf due to deletions on those leaves. in btrfs_del_items()
4554 * make sure the path still points to our leaf in btrfs_del_items()
4558 atomic_inc(&leaf->refs); in btrfs_del_items()
4561 * left neighbour leaf, and that's the first item. in btrfs_del_items()
4564 btrfs_item_size(leaf, 0); in btrfs_del_items()
4570 if (path->nodes[0] == leaf && in btrfs_del_items()
4571 btrfs_header_nritems(leaf)) { in btrfs_del_items()
4574 * leaf to its left neighbour, then attempt to in btrfs_del_items()
4578 * it's pointless to end up with a leaf having in btrfs_del_items()
4582 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4583 min_push_space = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4590 if (btrfs_header_nritems(leaf) == 0) { in btrfs_del_items()
4592 ret = btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4595 free_extent_buffer(leaf); in btrfs_del_items()
4603 if (path->nodes[0] == leaf) in btrfs_del_items()
4604 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_del_items()
4605 free_extent_buffer(leaf); in btrfs_del_items()
4608 btrfs_mark_buffer_dirty(trans, leaf); in btrfs_del_items()
4887 * This one should be returned as well, or we can get leaf corruption in btrfs_next_old_leaf()
4953 * itself waiting for the leaf we've currently in btrfs_next_old_leaf()
5033 struct extent_buffer *leaf; in btrfs_previous_item() local
5045 leaf = path->nodes[0]; in btrfs_previous_item()
5046 nritems = btrfs_header_nritems(leaf); in btrfs_previous_item()
5052 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_item()
5074 struct extent_buffer *leaf; in btrfs_previous_extent_item() local
5086 leaf = path->nodes[0]; in btrfs_previous_extent_item()
5087 nritems = btrfs_header_nritems(leaf); in btrfs_previous_extent_item()
5093 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_extent_item()