Lines Matching full:leaf
1672 * If @key is found, 0 is returned and you can find the item in the leaf level
1675 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
1831 * accounts the size btrfs_item, deduct it here so leaf in btrfs_search_slot()
2045 struct extent_buffer *leaf; in btrfs_search_slot_for_read() local
2054 * but in case the previous item is the last in a leaf, path points in btrfs_search_slot_for_read()
2055 * to the first free slot in the previous leaf, i.e. at an invalid in btrfs_search_slot_for_read()
2058 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2061 if (p->slots[0] >= btrfs_header_nritems(leaf)) { in btrfs_search_slot_for_read()
2082 leaf = p->nodes[0]; in btrfs_search_slot_for_read()
2083 if (p->slots[0] == btrfs_header_nritems(leaf)) in btrfs_search_slot_for_read()
2129 * fixing up pointers when a given leaf/node is not in slot 0 of the
2217 * Leaf @left | Leaf @right
2221 * Key f6 in leaf @left itself is valid, but not valid when the next
2222 * key in leaf @right is 7.
2611 * how many bytes are required to store the items in a leaf. start
2612 * and nr indicate which items in the leaf to check. This totals up the
2636 * The space between the end of the leaf items and
2637 * the start of the leaf data. IOW, how much room
2638 * the leaf has left for both items and data
2640 noinline int btrfs_leaf_free_space(struct extent_buffer *leaf) in btrfs_leaf_free_space() argument
2642 struct btrfs_fs_info *fs_info = leaf->fs_info; in btrfs_leaf_free_space()
2643 int nritems = btrfs_header_nritems(leaf); in btrfs_leaf_free_space()
2646 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); in btrfs_leaf_free_space()
2649 "leaf free space ret %d, leaf data size %lu, used %d nritems %d", in btrfs_leaf_free_space()
2652 leaf_space_used(leaf, 0, nritems), nritems); in btrfs_leaf_free_space()
2778 /* then fixup the leaf pointer in the path */ in __push_leaf_right()
2800 * push some data in the path leaf to the right, trying to free up at
2806 * this will push starting from min_slot to the end of the leaf. It won't
2867 /* Key greater than all keys in the leaf, right neighbor has in push_leaf_right()
2868 * enough room for it and we're not emptying our leaf to delete in push_leaf_right()
2870 * no need to touch/dirty our left leaf. */ in push_leaf_right()
2888 * push some data in the path leaf to the left, trying to free up at
2891 * max_slot can put a limit on how far into the leaf we'll push items. The
3019 /* then fixup the leaf pointer in the path */ in __push_leaf_left()
3040 * push some data in the path leaf to the left, trying to free up at
3043 * max_slot can put a limit on how far into the leaf we'll push items. The
3117 * split the path's leaf in two, making sure there is at least data_size
3118 * available for the resulting leaf level of the path.
3181 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3182 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3206 * right leaf in push_for_double_split()
3217 * our goal is to get our slot at the start or end of a leaf. If in push_for_double_split()
3226 /* try to push all the items before our slot into the next leaf */ in push_for_double_split()
3244 * split the path's leaf in two, making sure there is at least data_size
3245 * available for the resulting leaf level of the path.
3394 * We create a new leaf 'right' for the required ins_len and in split_leaf()
3395 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying in split_leaf()
3424 struct extent_buffer *leaf; in setup_leaf_for_split() local
3430 leaf = path->nodes[0]; in setup_leaf_for_split()
3431 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in setup_leaf_for_split()
3436 if (btrfs_leaf_free_space(leaf) >= ins_len) in setup_leaf_for_split()
3439 item_size = btrfs_item_size_nr(leaf, path->slots[0]); in setup_leaf_for_split()
3441 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3443 extent_len = btrfs_file_extent_num_bytes(leaf, fi); in setup_leaf_for_split()
3457 leaf = path->nodes[0]; in setup_leaf_for_split()
3459 if (item_size != btrfs_item_size_nr(leaf, path->slots[0])) in setup_leaf_for_split()
3462 /* the leaf has changed, it now has room. return now */ in setup_leaf_for_split()
3467 fi = btrfs_item_ptr(leaf, path->slots[0], in setup_leaf_for_split()
3469 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) in setup_leaf_for_split()
3489 struct extent_buffer *leaf; in split_item() local
3499 leaf = path->nodes[0]; in split_item()
3500 BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)); in split_item()
3503 orig_offset = btrfs_item_offset(leaf, item); in split_item()
3504 item_size = btrfs_item_size(leaf, item); in split_item()
3510 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, in split_item()
3514 nritems = btrfs_header_nritems(leaf); in split_item()
3517 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), in split_item()
3523 btrfs_set_item_key(leaf, &disk_key, slot); in split_item()
3527 btrfs_set_item_offset(leaf, new_item, orig_offset); in split_item()
3528 btrfs_set_item_size(leaf, new_item, item_size - split_offset); in split_item()
3530 btrfs_set_item_offset(leaf, item, in split_item()
3532 btrfs_set_item_size(leaf, item, split_offset); in split_item()
3534 btrfs_set_header_nritems(leaf, nritems + 1); in split_item()
3537 write_extent_buffer(leaf, buf, in split_item()
3538 btrfs_item_ptr_offset(leaf, path->slots[0]), in split_item()
3542 write_extent_buffer(leaf, buf + split_offset, in split_item()
3543 btrfs_item_ptr_offset(leaf, slot), in split_item()
3545 btrfs_mark_buffer_dirty(leaf); in split_item()
3547 BUG_ON(btrfs_leaf_free_space(leaf) < 0); in split_item()
3565 * leaf the entire time.
3585 * It guarantees both items live in the same tree leaf and the new item
3589 * leaf the entire time.
3596 struct extent_buffer *leaf; in btrfs_duplicate_item() local
3600 leaf = path->nodes[0]; in btrfs_duplicate_item()
3601 item_size = btrfs_item_size_nr(leaf, path->slots[0]); in btrfs_duplicate_item()
3609 leaf = path->nodes[0]; in btrfs_duplicate_item()
3610 memcpy_extent_buffer(leaf, in btrfs_duplicate_item()
3611 btrfs_item_ptr_offset(leaf, path->slots[0]), in btrfs_duplicate_item()
3612 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), in btrfs_duplicate_item()
3626 struct extent_buffer *leaf; in btrfs_truncate_item() local
3636 leaf = path->nodes[0]; in btrfs_truncate_item()
3639 old_size = btrfs_item_size_nr(leaf, slot); in btrfs_truncate_item()
3643 nritems = btrfs_header_nritems(leaf); in btrfs_truncate_item()
3644 data_end = leaf_data_end(leaf); in btrfs_truncate_item()
3646 old_data_start = btrfs_item_offset_nr(leaf, slot); in btrfs_truncate_item()
3657 btrfs_init_map_token(&token, leaf); in btrfs_truncate_item()
3668 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_truncate_item()
3675 btrfs_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
3681 fi = btrfs_item_ptr(leaf, slot, in btrfs_truncate_item()
3686 if (btrfs_file_extent_type(leaf, fi) == in btrfs_truncate_item()
3688 ptr = btrfs_item_ptr_offset(leaf, slot); in btrfs_truncate_item()
3689 memmove_extent_buffer(leaf, ptr, in btrfs_truncate_item()
3695 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_truncate_item()
3701 btrfs_set_item_key(leaf, &disk_key, slot); in btrfs_truncate_item()
3707 btrfs_set_item_size(leaf, item, new_size); in btrfs_truncate_item()
3708 btrfs_mark_buffer_dirty(leaf); in btrfs_truncate_item()
3710 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_truncate_item()
3711 btrfs_print_leaf(leaf); in btrfs_truncate_item()
3722 struct extent_buffer *leaf; in btrfs_extend_item() local
3731 leaf = path->nodes[0]; in btrfs_extend_item()
3733 nritems = btrfs_header_nritems(leaf); in btrfs_extend_item()
3734 data_end = leaf_data_end(leaf); in btrfs_extend_item()
3736 if (btrfs_leaf_free_space(leaf) < data_size) { in btrfs_extend_item()
3737 btrfs_print_leaf(leaf); in btrfs_extend_item()
3741 old_data = btrfs_item_end_nr(leaf, slot); in btrfs_extend_item()
3745 btrfs_print_leaf(leaf); in btrfs_extend_item()
3746 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", in btrfs_extend_item()
3755 btrfs_init_map_token(&token, leaf); in btrfs_extend_item()
3765 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_extend_item()
3770 old_size = btrfs_item_size_nr(leaf, slot); in btrfs_extend_item()
3772 btrfs_set_item_size(leaf, item, old_size + data_size); in btrfs_extend_item()
3773 btrfs_mark_buffer_dirty(leaf); in btrfs_extend_item()
3775 if (btrfs_leaf_free_space(leaf) < 0) { in btrfs_extend_item()
3776 btrfs_print_leaf(leaf); in btrfs_extend_item()
3783 * to a leaf. Main purpose is to save stack depth by doing the bulk of the work
3787 * @path: points to the leaf/slot where we are going to insert new items
3802 struct extent_buffer *leaf; in setup_items_for_insert() local
3818 leaf = path->nodes[0]; in setup_items_for_insert()
3821 nritems = btrfs_header_nritems(leaf); in setup_items_for_insert()
3822 data_end = leaf_data_end(leaf); in setup_items_for_insert()
3824 if (btrfs_leaf_free_space(leaf) < total_size) { in setup_items_for_insert()
3825 btrfs_print_leaf(leaf); in setup_items_for_insert()
3827 total_size, btrfs_leaf_free_space(leaf)); in setup_items_for_insert()
3831 btrfs_init_map_token(&token, leaf); in setup_items_for_insert()
3833 unsigned int old_data = btrfs_item_end_nr(leaf, slot); in setup_items_for_insert()
3836 btrfs_print_leaf(leaf); in setup_items_for_insert()
3838 "item at slot %d with data offset %u beyond data end of leaf %u", in setup_items_for_insert()
3855 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), in setup_items_for_insert()
3860 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in setup_items_for_insert()
3869 btrfs_set_item_key(leaf, &disk_key, slot + i); in setup_items_for_insert()
3876 btrfs_set_header_nritems(leaf, nritems + nr); in setup_items_for_insert()
3877 btrfs_mark_buffer_dirty(leaf); in setup_items_for_insert()
3879 if (btrfs_leaf_free_space(leaf) < 0) { in setup_items_for_insert()
3880 btrfs_print_leaf(leaf); in setup_items_for_insert()
3928 struct extent_buffer *leaf; in btrfs_insert_item() local
3936 leaf = path->nodes[0]; in btrfs_insert_item()
3937 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in btrfs_insert_item()
3938 write_extent_buffer(leaf, data, ptr, data_size); in btrfs_insert_item()
3939 btrfs_mark_buffer_dirty(leaf); in btrfs_insert_item()
3980 /* just turn the root into a leaf and break */ in del_ptr()
3992 * a helper function to delete the leaf pointed to by path->slots[1] and
3995 * This deletes the pointer in path->nodes[1] and frees the leaf
3998 * The path must have already been setup for deleting the leaf, including
4004 struct extent_buffer *leaf) in btrfs_del_leaf() argument
4006 WARN_ON(btrfs_header_generation(leaf) != trans->transid); in btrfs_del_leaf()
4015 root_sub_used(root, leaf->len); in btrfs_del_leaf()
4017 atomic_inc(&leaf->refs); in btrfs_del_leaf()
4018 btrfs_free_tree_block(trans, root, leaf, 0, 1); in btrfs_del_leaf()
4019 free_extent_buffer_stale(leaf); in btrfs_del_leaf()
4022 * delete the item at the leaf level in path. If that empties
4023 * the leaf, remove it from the tree
4029 struct extent_buffer *leaf; in btrfs_del_items() local
4038 leaf = path->nodes[0]; in btrfs_del_items()
4039 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); in btrfs_del_items()
4042 dsize += btrfs_item_size_nr(leaf, slot + i); in btrfs_del_items()
4044 nritems = btrfs_header_nritems(leaf); in btrfs_del_items()
4047 int data_end = leaf_data_end(leaf); in btrfs_del_items()
4050 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + in btrfs_del_items()
4055 btrfs_init_map_token(&token, leaf); in btrfs_del_items()
4064 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), in btrfs_del_items()
4069 btrfs_set_header_nritems(leaf, nritems - nr); in btrfs_del_items()
4072 /* delete the leaf if we've emptied it */ in btrfs_del_items()
4074 if (leaf == root->node) { in btrfs_del_items()
4075 btrfs_set_header_level(leaf, 0); in btrfs_del_items()
4077 btrfs_clean_tree_block(leaf); in btrfs_del_items()
4078 btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4081 int used = leaf_space_used(leaf, 0, nritems); in btrfs_del_items()
4085 btrfs_item_key(leaf, &disk_key, 0); in btrfs_del_items()
4089 /* delete the leaf if it is mostly empty */ in btrfs_del_items()
4092 * make sure the path still points to our leaf in btrfs_del_items()
4096 atomic_inc(&leaf->refs); in btrfs_del_items()
4103 if (path->nodes[0] == leaf && in btrfs_del_items()
4104 btrfs_header_nritems(leaf)) { in btrfs_del_items()
4111 if (btrfs_header_nritems(leaf) == 0) { in btrfs_del_items()
4113 btrfs_del_leaf(trans, root, path, leaf); in btrfs_del_items()
4114 free_extent_buffer(leaf); in btrfs_del_items()
4122 if (path->nodes[0] == leaf) in btrfs_del_items()
4123 btrfs_mark_buffer_dirty(leaf); in btrfs_del_items()
4124 free_extent_buffer(leaf); in btrfs_del_items()
4127 btrfs_mark_buffer_dirty(leaf); in btrfs_del_items()
4134 * search the tree again to find a leaf with lesser keys
4171 * item might have been pushed to the first slot (0) of the leaf we in btrfs_prev_leaf()
4173 * previous key can exist as the only element of a leaf (big fat item). in btrfs_prev_leaf()
4433 * This one should be returned as well, or we can get leaf corruption in btrfs_next_old_leaf()
4495 * itself waiting for the leaf we've currently in btrfs_next_old_leaf()
4550 struct extent_buffer *leaf; in btrfs_previous_item() local
4562 leaf = path->nodes[0]; in btrfs_previous_item()
4563 nritems = btrfs_header_nritems(leaf); in btrfs_previous_item()
4569 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_item()
4591 struct extent_buffer *leaf; in btrfs_previous_extent_item() local
4603 leaf = path->nodes[0]; in btrfs_previous_extent_item()
4604 nritems = btrfs_header_nritems(leaf); in btrfs_previous_extent_item()
4610 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); in btrfs_previous_extent_item()