Lines Matching defs:leaf
357 * node/leaf start address -> sequence
971 * If we are COWing a node/leaf from the extent, chunk, device or free
982 * groups when splitting a leaf or node, from one of those trees, since
2698 * If @key is found, 0 is returned and you can find the item in the leaf level
2701 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
3078 struct extent_buffer *leaf;
3087 * but in case the previous item is the last in a leaf, path points
3088 * to the first free slot in the previous leaf, i.e. at an invalid
3091 leaf = p->nodes[0];
3094 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
3115 leaf = p->nodes[0];
3116 if (p->slots[0] == btrfs_header_nritems(leaf))
3141 * fixing up pointers when a given leaf/node is not in slot 0 of the
3233 * Key f6 in leaf @left itself is valid, but not valid when the next
3234 * key in leaf @right is 7.
3625 * how many bytes are required to store the items in a leaf. start
3626 * and nr indicate which items in the leaf to check. This totals up the
3650 * The space between the end of the leaf items and
3651 * the start of the leaf data. IOW, how much room
3652 * the leaf has left for both items and data
3654 noinline int btrfs_leaf_free_space(struct extent_buffer *leaf)
3656 struct btrfs_fs_info *fs_info = leaf->fs_info;
3657 int nritems = btrfs_header_nritems(leaf);
3660 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
3663 "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
3666 leaf_space_used(leaf, 0, nritems), nritems);
3792 /* then fixup the leaf pointer in the path */
3814 * push some data in the path leaf to the right, trying to free up at
3820 * this will push starting from min_slot to the end of the leaf. It won't
3883 /* Key greater than all keys in the leaf, right neighbor has
3884 * enough room for it and we're not emptying our leaf to delete
3886 * no need to touch/dirty our left leaf. */
3904 * push some data in the path leaf to the left, trying to free up at
3907 * max_slot can put a limit on how far into the leaf we'll push items. The
4035 /* then fixup the leaf pointer in the path */
4056 * push some data in the path leaf to the left, trying to free up at
4059 * max_slot can put a limit on how far into the leaf we'll push items. The
4135 * split the path's leaf in two, making sure there is at least data_size
4136 * available for the resulting leaf level of the path.
4199 * of a leaf. A double split can leave us with 3 mostly empty leaves:
4200 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
4224 * right leaf
4235 * our goal is to get our slot at the start or end of a leaf. If
4244 /* try to push all the items before our slot into the next leaf */
4262 * split the path's leaf in two, making sure there is at least data_size
4263 * available for the resulting leaf level of the path.
4412 * We create a new leaf 'right' for the required ins_len and
4413 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
4442 struct extent_buffer *leaf;
4448 leaf = path->nodes[0];
4449 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4454 if (btrfs_leaf_free_space(leaf) >= ins_len)
4457 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4459 fi = btrfs_item_ptr(leaf, path->slots[0],
4461 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
4475 leaf = path->nodes[0];
4477 if (item_size != btrfs_item_size_nr(leaf, path->slots[0]))
4480 /* the leaf has changed, it now has room. return now */
4485 fi = btrfs_item_ptr(leaf, path->slots[0],
4487 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
4508 struct extent_buffer *leaf;
4518 leaf = path->nodes[0];
4519 BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item));
4524 orig_offset = btrfs_item_offset(leaf, item);
4525 item_size = btrfs_item_size(leaf, item);
4531 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
4535 nritems = btrfs_header_nritems(leaf);
4538 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
4544 btrfs_set_item_key(leaf, &disk_key, slot);
4548 btrfs_set_item_offset(leaf, new_item, orig_offset);
4549 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
4551 btrfs_set_item_offset(leaf, item,
4553 btrfs_set_item_size(leaf, item, split_offset);
4555 btrfs_set_header_nritems(leaf, nritems + 1);
4558 write_extent_buffer(leaf, buf,
4559 btrfs_item_ptr_offset(leaf, path->slots[0]),
4563 write_extent_buffer(leaf, buf + split_offset,
4564 btrfs_item_ptr_offset(leaf, slot),
4566 btrfs_mark_buffer_dirty(leaf);
4568 BUG_ON(btrfs_leaf_free_space(leaf) < 0);
4586 * leaf the entire time.
4606 * It guarantees both items live in the same tree leaf and the new item
4610 * leaf the entire time.
4617 struct extent_buffer *leaf;
4621 leaf = path->nodes[0];
4622 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4630 leaf = path->nodes[0];
4631 memcpy_extent_buffer(leaf,
4632 btrfs_item_ptr_offset(leaf, path->slots[0]),
4633 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4647 struct extent_buffer *leaf;
4657 leaf = path->nodes[0];
4660 old_size = btrfs_item_size_nr(leaf, slot);
4664 nritems = btrfs_header_nritems(leaf);
4665 data_end = leaf_data_end(leaf);
4667 old_data_start = btrfs_item_offset_nr(leaf, slot);
4678 btrfs_init_map_token(&token, leaf);
4689 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4696 btrfs_item_key(leaf, &disk_key, slot);
4702 fi = btrfs_item_ptr(leaf, slot,
4707 if (btrfs_file_extent_type(leaf, fi) ==
4709 ptr = btrfs_item_ptr_offset(leaf, slot);
4710 memmove_extent_buffer(leaf, ptr,
4716 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4722 btrfs_set_item_key(leaf, &disk_key, slot);
4728 btrfs_set_item_size(leaf, item, new_size);
4729 btrfs_mark_buffer_dirty(leaf);
4731 if (btrfs_leaf_free_space(leaf) < 0) {
4732 btrfs_print_leaf(leaf);
4743 struct extent_buffer *leaf;
4752 leaf = path->nodes[0];
4754 nritems = btrfs_header_nritems(leaf);
4755 data_end = leaf_data_end(leaf);
4757 if (btrfs_leaf_free_space(leaf) < data_size) {
4758 btrfs_print_leaf(leaf);
4762 old_data = btrfs_item_end_nr(leaf, slot);
4766 btrfs_print_leaf(leaf);
4767 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",
4776 btrfs_init_map_token(&token, leaf);
4786 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4791 old_size = btrfs_item_size_nr(leaf, slot);
4793 btrfs_set_item_size(leaf, item, old_size + data_size);
4794 btrfs_mark_buffer_dirty(leaf);
4796 if (btrfs_leaf_free_space(leaf) < 0) {
4797 btrfs_print_leaf(leaf);
4804 * to a leaf. Main purpose is to save stack depth by doing the bulk of the work
4808 * @path: points to the leaf/slot where we are going to insert new items
4823 struct extent_buffer *leaf;
4839 leaf = path->nodes[0];
4842 nritems = btrfs_header_nritems(leaf);
4843 data_end = leaf_data_end(leaf);
4845 if (btrfs_leaf_free_space(leaf) < total_size) {
4846 btrfs_print_leaf(leaf);
4848 total_size, btrfs_leaf_free_space(leaf));
4852 btrfs_init_map_token(&token, leaf);
4854 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
4857 btrfs_print_leaf(leaf);
4859 "item at slot %d with data offset %u beyond data end of leaf %u",
4876 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
4881 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4890 btrfs_set_item_key(leaf, &disk_key, slot + i);
4897 btrfs_set_header_nritems(leaf, nritems + nr);
4898 btrfs_mark_buffer_dirty(leaf);
4900 if (btrfs_leaf_free_space(leaf) < 0) {
4901 btrfs_print_leaf(leaf);
4949 struct extent_buffer *leaf;
4957 leaf = path->nodes[0];
4958 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4959 write_extent_buffer(leaf, data, ptr, data_size);
4960 btrfs_mark_buffer_dirty(leaf);
5001 /* just turn the root into a leaf and break */
5013 * a helper function to delete the leaf pointed to by path->slots[1] and
5016 * This deletes the pointer in path->nodes[1] and frees the leaf
5019 * The path must have already been setup for deleting the leaf, including
5025 struct extent_buffer *leaf)
5027 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
5036 root_sub_used(root, leaf->len);
5038 atomic_inc(&leaf->refs);
5039 btrfs_free_tree_block(trans, root, leaf, 0, 1);
5040 free_extent_buffer_stale(leaf);
5043 * delete the item at the leaf level in path. If that empties
5044 * the leaf, remove it from the tree
5050 struct extent_buffer *leaf;
5059 leaf = path->nodes[0];
5060 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
5063 dsize += btrfs_item_size_nr(leaf, slot + i);
5065 nritems = btrfs_header_nritems(leaf);
5068 int data_end = leaf_data_end(leaf);
5071 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
5076 btrfs_init_map_token(&token, leaf);
5085 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
5090 btrfs_set_header_nritems(leaf, nritems - nr);
5093 /* delete the leaf if we've emptied it */
5095 if (leaf == root->node) {
5096 btrfs_set_header_level(leaf, 0);
5099 btrfs_clean_tree_block(leaf);
5100 btrfs_del_leaf(trans, root, path, leaf);
5103 int used = leaf_space_used(leaf, 0, nritems);
5107 btrfs_item_key(leaf, &disk_key, 0);
5111 /* delete the leaf if it is mostly empty */
5114 * make sure the path still points to our leaf
5118 atomic_inc(&leaf->refs);
5126 if (path->nodes[0] == leaf &&
5127 btrfs_header_nritems(leaf)) {
5134 if (btrfs_header_nritems(leaf) == 0) {
5136 btrfs_del_leaf(trans, root, path, leaf);
5137 free_extent_buffer(leaf);
5145 if (path->nodes[0] == leaf)
5146 btrfs_mark_buffer_dirty(leaf);
5147 free_extent_buffer(leaf);
5150 btrfs_mark_buffer_dirty(leaf);
5157 * search the tree again to find a leaf with lesser keys
5193 * Previous key not found. Even if we were at slot 0 of the leaf we had
5197 * sibling leaf into the front of the leaf we had due to an insertion
5224 * item might have been pushed to the first slot (0) of the leaf we
5226 * previous key can exist as the only element of a leaf (big fat item).
5438 * search the tree again to find a leaf with greater keys
5502 * This one should be returned as well, or we can get leaf corruption
5555 * itself waiting for the leaf we've currently
5631 struct extent_buffer *leaf;
5644 leaf = path->nodes[0];
5645 nritems = btrfs_header_nritems(leaf);
5651 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5673 struct extent_buffer *leaf;
5686 leaf = path->nodes[0];
5687 nritems = btrfs_header_nritems(leaf);
5693 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);