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.
1972 	struct extent_buffer *leaf = path->nodes[0];  in search_leaf()  local
1979 	 * If we are doing an insertion, the leaf has enough free space and the  in search_leaf()
1982 	 * binary search on the leaf (with search_for_key_slot()), allowing other  in search_leaf()
1987 		 * Cache the leaf free space, since we will need it later and it  in search_leaf()
1990 		leaf_free_space = btrfs_leaf_free_space(leaf);  in search_leaf()
1993 		 * !path->locks[1] means we have a single node tree, the leaf is  in search_leaf()
1999 			ASSERT(btrfs_header_nritems(leaf) > 0);  in search_leaf()
2000 			btrfs_item_key(leaf, &first_key, 0);  in search_leaf()
2021 				 * leaf and there's no need to split the leaf.  in search_leaf()
2054 		ret = search_for_key_slot(leaf, search_low_slot, key,  in search_leaf()
2067 		 * accounts the size btrfs_item, deduct it here so leaf space  in search_leaf()
2115  * If @key is found, 0 is returned and you can find the item in the leaf level
2118  * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2469  * Search the tree again to find a leaf with smaller keys.
2506 	 * Previous key not found. Even if we were at slot 0 of the leaf we had  in btrfs_prev_leaf()
2510 	 * sibling leaf into the front of the leaf we had due to an insertion  in btrfs_prev_leaf()
2537 	 * item might have been pushed to the first slot (0) of the leaf we  in btrfs_prev_leaf()
2539 	 * previous key can exist as the only element of a leaf (big fat item).  in btrfs_prev_leaf()
2567 	struct extent_buffer *leaf;  in btrfs_search_slot_for_read()  local
2576 	 * but in case the previous item is the last in a leaf, path points  in btrfs_search_slot_for_read()
2577 	 * to the first free slot in the previous leaf, i.e. at an invalid  in btrfs_search_slot_for_read()
2580 	leaf = p->nodes[0];  in btrfs_search_slot_for_read()
2583 		if (p->slots[0] >= btrfs_header_nritems(leaf)) {  in btrfs_search_slot_for_read()
2604 				leaf = p->nodes[0];  in btrfs_search_slot_for_read()
2605 				if (p->slots[0] == btrfs_header_nritems(leaf))  in btrfs_search_slot_for_read()
2677  * fixing up pointers when a given leaf/node is not in slot 0 of the
2765  * Leaf @left			| Leaf @right
2769  * Key f6 in leaf @left itself is valid, but not valid when the next
2770  * key in leaf @right is 7.
3186  * how many bytes are required to store the items in a leaf.  start
3187  * and nr indicate which items in the leaf to check.  This totals up the
3206  * The space between the end of the leaf items and
3207  * the start of the leaf data.  IOW, how much room
3208  * the leaf has left for both items and data
3210 int btrfs_leaf_free_space(const struct extent_buffer *leaf)  in btrfs_leaf_free_space()  argument
3212 	struct btrfs_fs_info *fs_info = leaf->fs_info;  in btrfs_leaf_free_space()
3213 	int nritems = btrfs_header_nritems(leaf);  in btrfs_leaf_free_space()
3216 	ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);  in btrfs_leaf_free_space()
3219 			   "leaf free space ret %d, leaf data size %lu, used %d nritems %d",  in btrfs_leaf_free_space()
3222 			   leaf_space_used(leaf, 0, nritems), nritems);  in btrfs_leaf_free_space()
3338 	/* then fixup the leaf pointer in the path */  in __push_leaf_right()
3360  * push some data in the path leaf to the right, trying to free up at
3366  * this will push starting from min_slot to the end of the leaf.  It won't
3419 		/* Key greater than all keys in the leaf, right neighbor has  in push_leaf_right()
3420 		 * enough room for it and we're not emptying our leaf to delete  in push_leaf_right()
3422 		 * no need to touch/dirty our left leaf. */  in push_leaf_right()
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
3557 	/* then fixup the leaf pointer in the path */  in __push_leaf_left()
3578  * push some data in the path leaf to the left, trying to free up at
3581  * max_slot can put a limit on how far into the leaf we'll push items.  The
3644  * split the path's leaf in two, making sure there is at least data_size
3645  * available for the resulting leaf level of the path.
3708  * of a leaf.  A double split can leave us with 3 mostly empty leaves:
3709  * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3733 	 * right leaf  in push_for_double_split()
3744 	 * our goal is to get our slot at the start or end of a leaf.  If  in push_for_double_split()
3753 	/* try to push all the items before our slot into the next leaf */  in push_for_double_split()
3771  * split the path's leaf in two, making sure there is at least data_size
3772  * available for the resulting leaf level of the path.
3931 		 * We create a new leaf 'right' for the required ins_len and  in split_leaf()
3932 		 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying  in split_leaf()
3966 	struct extent_buffer *leaf;  in setup_leaf_for_split()  local
3972 	leaf = path->nodes[0];  in setup_leaf_for_split()
3973 	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);  in setup_leaf_for_split()
3978 	if (btrfs_leaf_free_space(leaf) >= ins_len)  in setup_leaf_for_split()
3981 	item_size = btrfs_item_size(leaf, path->slots[0]);  in setup_leaf_for_split()
3983 		fi = btrfs_item_ptr(leaf, path->slots[0],  in setup_leaf_for_split()
3985 		extent_len = btrfs_file_extent_num_bytes(leaf, fi);  in setup_leaf_for_split()
3999 	leaf = path->nodes[0];  in setup_leaf_for_split()
4001 	if (item_size != btrfs_item_size(leaf, path->slots[0]))  in setup_leaf_for_split()
4004 	/* the leaf has  changed, it now has room.  return now */  in setup_leaf_for_split()
4009 		fi = btrfs_item_ptr(leaf, path->slots[0],  in setup_leaf_for_split()
4011 		if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))  in setup_leaf_for_split()
4031 	struct extent_buffer *leaf;  in split_item()  local
4039 	leaf = path->nodes[0];  in split_item()
4042 	 * setup_leaf_for_split() to make room for the new item in the leaf.  in split_item()
4044 	if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)))  in split_item()
4048 	orig_offset = btrfs_item_offset(leaf, path->slots[0]);  in split_item()
4049 	item_size = btrfs_item_size(leaf, path->slots[0]);  in split_item()
4055 	read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,  in split_item()
4059 	nritems = btrfs_header_nritems(leaf);  in split_item()
4062 		memmove_leaf_items(leaf, slot + 1, slot, nritems - slot);  in split_item()
4066 	btrfs_set_item_key(leaf, &disk_key, slot);  in split_item()
4068 	btrfs_set_item_offset(leaf, slot, orig_offset);  in split_item()
4069 	btrfs_set_item_size(leaf, slot, item_size - split_offset);  in split_item()
4071 	btrfs_set_item_offset(leaf, orig_slot,  in split_item()
4073 	btrfs_set_item_size(leaf, orig_slot, split_offset);  in split_item()
4075 	btrfs_set_header_nritems(leaf, nritems + 1);  in split_item()
4078 	write_extent_buffer(leaf, buf,  in split_item()
4079 			    btrfs_item_ptr_offset(leaf, path->slots[0]),  in split_item()
4083 	write_extent_buffer(leaf, buf + split_offset,  in split_item()
4084 			    btrfs_item_ptr_offset(leaf, slot),  in split_item()
4086 	btrfs_mark_buffer_dirty(leaf);  in split_item()
4088 	BUG_ON(btrfs_leaf_free_space(leaf) < 0);  in split_item()
4106  * leaf the entire time.
4133 	struct extent_buffer *leaf;  in btrfs_truncate_item()  local
4142 	leaf = path->nodes[0];  in btrfs_truncate_item()
4145 	old_size = btrfs_item_size(leaf, slot);  in btrfs_truncate_item()
4149 	nritems = btrfs_header_nritems(leaf);  in btrfs_truncate_item()
4150 	data_end = leaf_data_end(leaf);  in btrfs_truncate_item()
4152 	old_data_start = btrfs_item_offset(leaf, slot);  in btrfs_truncate_item()
4163 	btrfs_init_map_token(&token, leaf);  in btrfs_truncate_item()
4173 		memmove_leaf_data(leaf, data_end + size_diff, data_end,  in btrfs_truncate_item()
4179 		btrfs_item_key(leaf, &disk_key, slot);  in btrfs_truncate_item()
4185 			fi = btrfs_item_ptr(leaf, slot,  in btrfs_truncate_item()
4190 			if (btrfs_file_extent_type(leaf, fi) ==  in btrfs_truncate_item()
4192 				ptr = btrfs_item_ptr_offset(leaf, slot);  in btrfs_truncate_item()
4193 				memmove_extent_buffer(leaf, ptr,  in btrfs_truncate_item()
4199 		memmove_leaf_data(leaf, data_end + size_diff, data_end,  in btrfs_truncate_item()
4204 		btrfs_set_item_key(leaf, &disk_key, slot);  in btrfs_truncate_item()
4209 	btrfs_set_item_size(leaf, slot, new_size);  in btrfs_truncate_item()
4210 	btrfs_mark_buffer_dirty(leaf);  in btrfs_truncate_item()
4212 	if (btrfs_leaf_free_space(leaf) < 0) {  in btrfs_truncate_item()
4213 		btrfs_print_leaf(leaf);  in btrfs_truncate_item()
4224 	struct extent_buffer *leaf;  in btrfs_extend_item()  local
4232 	leaf = path->nodes[0];  in btrfs_extend_item()
4234 	nritems = btrfs_header_nritems(leaf);  in btrfs_extend_item()
4235 	data_end = leaf_data_end(leaf);  in btrfs_extend_item()
4237 	if (btrfs_leaf_free_space(leaf) < data_size) {  in btrfs_extend_item()
4238 		btrfs_print_leaf(leaf);  in btrfs_extend_item()
4242 	old_data = btrfs_item_data_end(leaf, slot);  in btrfs_extend_item()
4246 		btrfs_print_leaf(leaf);  in btrfs_extend_item()
4247 		btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",  in btrfs_extend_item()
4256 	btrfs_init_map_token(&token, leaf);  in btrfs_extend_item()
4265 	memmove_leaf_data(leaf, data_end - data_size, data_end,  in btrfs_extend_item()
4269 	old_size = btrfs_item_size(leaf, slot);  in btrfs_extend_item()
4270 	btrfs_set_item_size(leaf, slot, old_size + data_size);  in btrfs_extend_item()
4271 	btrfs_mark_buffer_dirty(leaf);  in btrfs_extend_item()
4273 	if (btrfs_leaf_free_space(leaf) < 0) {  in btrfs_extend_item()
4274 		btrfs_print_leaf(leaf);  in btrfs_extend_item()
4283  * @path:	points to the leaf/slot where we are going to insert new items
4297 	struct extent_buffer *leaf;  in setup_items_for_insert()  local
4305 	 * can use them while we modify the leaf.  in setup_items_for_insert()
4313 	leaf = path->nodes[0];  in setup_items_for_insert()
4316 	nritems = btrfs_header_nritems(leaf);  in setup_items_for_insert()
4317 	data_end = leaf_data_end(leaf);  in setup_items_for_insert()
4320 	if (btrfs_leaf_free_space(leaf) < total_size) {  in setup_items_for_insert()
4321 		btrfs_print_leaf(leaf);  in setup_items_for_insert()
4323 			   total_size, btrfs_leaf_free_space(leaf));  in setup_items_for_insert()
4327 	btrfs_init_map_token(&token, leaf);  in setup_items_for_insert()
4329 		unsigned int old_data = btrfs_item_data_end(leaf, slot);  in setup_items_for_insert()
4332 			btrfs_print_leaf(leaf);  in setup_items_for_insert()
4334 		"item at slot %d with data offset %u beyond data end of leaf %u",  in setup_items_for_insert()
4350 		memmove_leaf_items(leaf, slot + batch->nr, slot, nritems - slot);  in setup_items_for_insert()
4353 		memmove_leaf_data(leaf, data_end - batch->total_data_size,  in setup_items_for_insert()
4361 		btrfs_set_item_key(leaf, &disk_key, slot + i);  in setup_items_for_insert()
4367 	btrfs_set_header_nritems(leaf, nritems + batch->nr);  in setup_items_for_insert()
4368 	btrfs_mark_buffer_dirty(leaf);  in setup_items_for_insert()
4370 	if (btrfs_leaf_free_space(leaf) < 0) {  in setup_items_for_insert()
4371 		btrfs_print_leaf(leaf);  in setup_items_for_insert()
4377  * Insert a new item into a leaf.
4380  * @path:      A path pointing to the target leaf and slot.
4436 	struct extent_buffer *leaf;  in btrfs_insert_item()  local
4444 		leaf = path->nodes[0];  in btrfs_insert_item()
4445 		ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);  in btrfs_insert_item()
4446 		write_extent_buffer(leaf, data, ptr, data_size);  in btrfs_insert_item()
4447 		btrfs_mark_buffer_dirty(leaf);  in btrfs_insert_item()
4455  * It guarantees both items live in the same tree leaf and the new item is
4458  * This allows us to split a file extent in place, keeping a lock on the leaf
4466 	struct extent_buffer *leaf;  in btrfs_duplicate_item()  local
4470 	leaf = path->nodes[0];  in btrfs_duplicate_item()
4471 	item_size = btrfs_item_size(leaf, path->slots[0]);  in btrfs_duplicate_item()
4479 	leaf = path->nodes[0];  in btrfs_duplicate_item()
4480 	memcpy_extent_buffer(leaf,  in btrfs_duplicate_item()
4481 			     btrfs_item_ptr_offset(leaf, path->slots[0]),  in btrfs_duplicate_item()
4482 			     btrfs_item_ptr_offset(leaf, path->slots[0] - 1),  in btrfs_duplicate_item()
4530 		/* just turn the root into a leaf and break */  in btrfs_del_ptr()
4543  * a helper function to delete the leaf pointed to by path->slots[1] and
4546  * This deletes the pointer in path->nodes[1] and frees the leaf
4549  * The path must have already been setup for deleting the leaf, including
4555 				   struct extent_buffer *leaf)  in btrfs_del_leaf()  argument
4559 	WARN_ON(btrfs_header_generation(leaf) != trans->transid);  in btrfs_del_leaf()
4570 	root_sub_used(root, leaf->len);  in btrfs_del_leaf()
4572 	atomic_inc(&leaf->refs);  in btrfs_del_leaf()
4573 	btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1);  in btrfs_del_leaf()
4574 	free_extent_buffer_stale(leaf);  in btrfs_del_leaf()
4578  * delete the item at the leaf level in path.  If that empties
4579  * the leaf, remove it from the tree
4585 	struct extent_buffer *leaf;  in btrfs_del_items()  local
4590 	leaf = path->nodes[0];  in btrfs_del_items()
4591 	nritems = btrfs_header_nritems(leaf);  in btrfs_del_items()
4594 		const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1);  in btrfs_del_items()
4595 		const int data_end = leaf_data_end(leaf);  in btrfs_del_items()
4601 			dsize += btrfs_item_size(leaf, slot + i);  in btrfs_del_items()
4603 		memmove_leaf_data(leaf, data_end + dsize, data_end,  in btrfs_del_items()
4606 		btrfs_init_map_token(&token, leaf);  in btrfs_del_items()
4614 		memmove_leaf_items(leaf, slot, slot + nr, nritems - slot - nr);  in btrfs_del_items()
4616 	btrfs_set_header_nritems(leaf, nritems - nr);  in btrfs_del_items()
4619 	/* delete the leaf if we've emptied it */  in btrfs_del_items()
4621 		if (leaf == root->node) {  in btrfs_del_items()
4622 			btrfs_set_header_level(leaf, 0);  in btrfs_del_items()
4624 			btrfs_clear_buffer_dirty(trans, leaf);  in btrfs_del_items()
4625 			ret = btrfs_del_leaf(trans, root, path, leaf);  in btrfs_del_items()
4630 		int used = leaf_space_used(leaf, 0, nritems);  in btrfs_del_items()
4634 			btrfs_item_key(leaf, &disk_key, 0);  in btrfs_del_items()
4639 		 * Try to delete the leaf if it is mostly empty. We do this by  in btrfs_del_items()
4642 		 * not ideal, but future insertions might fill the leaf with more  in btrfs_del_items()
4644 		 * leaf due to deletions on those leaves.  in btrfs_del_items()
4650 			 * make sure the path still points to our leaf  in btrfs_del_items()
4654 			atomic_inc(&leaf->refs);  in btrfs_del_items()
4657 			 * left neighbour leaf, and that's the first item.  in btrfs_del_items()
4660 				btrfs_item_size(leaf, 0);  in btrfs_del_items()
4666 			if (path->nodes[0] == leaf &&  in btrfs_del_items()
4667 			    btrfs_header_nritems(leaf)) {  in btrfs_del_items()
4670 				 * leaf to its left neighbour, then attempt to  in btrfs_del_items()
4674 				 * it's pointless to end up with a leaf having  in btrfs_del_items()
4678 				nritems = btrfs_header_nritems(leaf);  in btrfs_del_items()
4679 				min_push_space = leaf_space_used(leaf, 0, nritems);  in btrfs_del_items()
4686 			if (btrfs_header_nritems(leaf) == 0) {  in btrfs_del_items()
4688 				ret = btrfs_del_leaf(trans, root, path, leaf);  in btrfs_del_items()
4691 				free_extent_buffer(leaf);  in btrfs_del_items()
4699 				if (path->nodes[0] == leaf)  in btrfs_del_items()
4700 					btrfs_mark_buffer_dirty(leaf);  in btrfs_del_items()
4701 				free_extent_buffer(leaf);  in btrfs_del_items()
4704 			btrfs_mark_buffer_dirty(leaf);  in btrfs_del_items()
4983 	 * This one should be returned as well, or we can get leaf corruption  in btrfs_next_old_leaf()
5049 				 * itself waiting for the leaf we've currently  in btrfs_next_old_leaf()
5129 	struct extent_buffer *leaf;  in btrfs_previous_item()  local
5141 		leaf = path->nodes[0];  in btrfs_previous_item()
5142 		nritems = btrfs_header_nritems(leaf);  in btrfs_previous_item()
5148 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);  in btrfs_previous_item()
5170 	struct extent_buffer *leaf;  in btrfs_previous_extent_item()  local
5182 		leaf = path->nodes[0];  in btrfs_previous_extent_item()
5183 		nritems = btrfs_header_nritems(leaf);  in btrfs_previous_extent_item()
5189 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);  in btrfs_previous_extent_item()