linux/fs/btrfs/ctree.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2007,2008 Oracle.  All rights reserved.
 */

#include <linux/sched.h>
#include <linux/slab.h>
#include <linux/rbtree.h>
#include <linux/mm.h>
#include <linux/error-injection.h>
#include "messages.h"
#include "ctree.h"
#include "disk-io.h"
#include "transaction.h"
#include "print-tree.h"
#include "locking.h"
#include "volumes.h"
#include "qgroup.h"
#include "tree-mod-log.h"
#include "tree-checker.h"
#include "fs.h"
#include "accessors.h"
#include "extent-tree.h"
#include "relocation.h"
#include "file-item.h"

static struct kmem_cache *btrfs_path_cachep;

static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_path *path, int level);
static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		      const struct btrfs_key *ins_key, struct btrfs_path *path,
		      int data_size, int extend);
static int push_node_left(struct btrfs_trans_handle *trans,
			  struct extent_buffer *dst,
			  struct extent_buffer *src, int empty);
static int balance_node_right(struct btrfs_trans_handle *trans,
			      struct extent_buffer *dst_buf,
			      struct extent_buffer *src_buf);

static const struct btrfs_csums {} btrfs_csums[] =;

/*
 * The leaf data grows from end-to-front in the node.  this returns the address
 * of the start of the last item, which is the stop of the leaf data stack.
 */
static unsigned int leaf_data_end(const struct extent_buffer *leaf)
{}

/*
 * Move data in a @leaf (using memmove, safe for overlapping ranges).
 *
 * @leaf:	leaf that we're doing a memmove on
 * @dst_offset:	item data offset we're moving to
 * @src_offset:	item data offset were' moving from
 * @len:	length of the data we're moving
 *
 * Wrapper around memmove_extent_buffer() that takes into account the header on
 * the leaf.  The btrfs_item offset's start directly after the header, so we
 * have to adjust any offsets to account for the header in the leaf.  This
 * handles that math to simplify the callers.
 */
static inline void memmove_leaf_data(const struct extent_buffer *leaf,
				     unsigned long dst_offset,
				     unsigned long src_offset,
				     unsigned long len)
{}

/*
 * Copy item data from @src into @dst at the given @offset.
 *
 * @dst:	destination leaf that we're copying into
 * @src:	source leaf that we're copying from
 * @dst_offset:	item data offset we're copying to
 * @src_offset:	item data offset were' copying from
 * @len:	length of the data we're copying
 *
 * Wrapper around copy_extent_buffer() that takes into account the header on
 * the leaf.  The btrfs_item offset's start directly after the header, so we
 * have to adjust any offsets to account for the header in the leaf.  This
 * handles that math to simplify the callers.
 */
static inline void copy_leaf_data(const struct extent_buffer *dst,
				  const struct extent_buffer *src,
				  unsigned long dst_offset,
				  unsigned long src_offset, unsigned long len)
{}

/*
 * Move items in a @leaf (using memmove).
 *
 * @dst:	destination leaf for the items
 * @dst_item:	the item nr we're copying into
 * @src_item:	the item nr we're copying from
 * @nr_items:	the number of items to copy
 *
 * Wrapper around memmove_extent_buffer() that does the math to get the
 * appropriate offsets into the leaf from the item numbers.
 */
static inline void memmove_leaf_items(const struct extent_buffer *leaf,
				      int dst_item, int src_item, int nr_items)
{}

/*
 * Copy items from @src into @dst at the given @offset.
 *
 * @dst:	destination leaf for the items
 * @src:	source leaf for the items
 * @dst_item:	the item nr we're copying into
 * @src_item:	the item nr we're copying from
 * @nr_items:	the number of items to copy
 *
 * Wrapper around copy_extent_buffer() that does the math to get the
 * appropriate offsets into the leaf from the item numbers.
 */
static inline void copy_leaf_items(const struct extent_buffer *dst,
				   const struct extent_buffer *src,
				   int dst_item, int src_item, int nr_items)
{}

/* This exists for btrfs-progs usages. */
u16 btrfs_csum_type_size(u16 type)
{}

int btrfs_super_csum_size(const struct btrfs_super_block *s)
{}

const char *btrfs_super_csum_name(u16 csum_type)
{}

/*
 * Return driver name if defined, otherwise the name that's also a valid driver
 * name
 */
const char *btrfs_super_csum_driver(u16 csum_type)
{}

size_t __attribute_const__ btrfs_get_num_csums(void)
{}

struct btrfs_path *btrfs_alloc_path(void)
{}

/* this also releases the path */
void btrfs_free_path(struct btrfs_path *p)
{}

/*
 * path release drops references on the extent buffers in the path
 * and it drops any locks held by this path
 *
 * It is safe to call this on paths that no locks or extent buffers held.
 */
noinline void btrfs_release_path(struct btrfs_path *p)
{}

/*
 * We want the transaction abort to print stack trace only for errors where the
 * cause could be a bug, eg. due to ENOSPC, and not for common errors that are
 * caused by external factors.
 */
bool __cold abort_should_print_stack(int error)
{}

/*
 * safely gets a reference on the root node of a tree.  A lock
 * is not taken, so a concurrent writer may put a different node
 * at the root of the tree.  See btrfs_lock_root_node for the
 * looping required.
 *
 * The extent buffer returned by this has a reference taken, so
 * it won't disappear.  It may stop being the root of the tree
 * at any time because there are no locks held.
 */
struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
{}

/*
 * Cowonly root (not-shareable trees, everything not subvolume or reloc roots),
 * just get put onto a simple dirty list.  Transaction walks this list to make
 * sure they get properly updated on disk.
 */
static void add_root_to_dirty_list(struct btrfs_root *root)
{}

/*
 * used by snapshot creation to make a copy of a root for a tree with
 * a given objectid.  The buffer with the new root node is returned in
 * cow_ret, and this func returns zero on success or a negative error code.
 */
int btrfs_copy_root(struct btrfs_trans_handle *trans,
		      struct btrfs_root *root,
		      struct extent_buffer *buf,
		      struct extent_buffer **cow_ret, u64 new_root_objectid)
{}

/*
 * check if the tree block can be shared by multiple trees
 */
bool btrfs_block_can_be_shared(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       struct extent_buffer *buf)
{}

static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
				       struct btrfs_root *root,
				       struct extent_buffer *buf,
				       struct extent_buffer *cow,
				       int *last_ref)
{}

/*
 * does the dirty work in cow of a single block.  The parent block (if
 * supplied) is updated to point to the new cow copy.  The new buffer is marked
 * dirty and returned locked.  If you modify the block it needs to be marked
 * dirty again.
 *
 * search_start -- an allocation hint for the new block
 *
 * empty_size -- a hint that you plan on doing more cow.  This is the size in
 * bytes the allocator should try to find free next to the block it returns.
 * This is just a hint and may be ignored by the allocator.
 */
int btrfs_force_cow_block(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root,
			  struct extent_buffer *buf,
			  struct extent_buffer *parent, int parent_slot,
			  struct extent_buffer **cow_ret,
			  u64 search_start, u64 empty_size,
			  enum btrfs_lock_nesting nest)
{}

static inline int should_cow_block(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct extent_buffer *buf)
{}

/*
 * COWs a single block, see btrfs_force_cow_block() for the real work.
 * This version of it has extra checks so that a block isn't COWed more than
 * once per transaction, as long as it hasn't been written yet
 */
int btrfs_cow_block(struct btrfs_trans_handle *trans,
		    struct btrfs_root *root, struct extent_buffer *buf,
		    struct extent_buffer *parent, int parent_slot,
		    struct extent_buffer **cow_ret,
		    enum btrfs_lock_nesting nest)
{}
ALLOW_ERROR_INJECTION();

/*
 * same as comp_keys only with two btrfs_key's
 */
int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
{}

/*
 * Search for a key in the given extent_buffer.
 *
 * The lower boundary for the search is specified by the slot number @first_slot.
 * Use a value of 0 to search over the whole extent buffer. Works for both
 * leaves and nodes.
 *
 * The slot in the extent buffer is returned via @slot. If the key exists in the
 * extent buffer, then @slot will point to the slot where the key is, otherwise
 * it points to the slot where you would insert the key.
 *
 * Slot may point to the total number of items (i.e. one position beyond the last
 * key) if the key is bigger than the last key in the extent buffer.
 */
int btrfs_bin_search(struct extent_buffer *eb, int first_slot,
		     const struct btrfs_key *key, int *slot)
{}

static void root_add_used_bytes(struct btrfs_root *root)
{}

static void root_sub_used_bytes(struct btrfs_root *root)
{}

/* given a node and slot number, this reads the blocks it points to.  The
 * extent buffer is returned with a reference taken (but unlocked).
 */
struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
					   int slot)
{}

/*
 * node level balancing, used to make sure nodes are in proper order for
 * item deletion.  We balance from the top down, so we have to make sure
 * that a deletion won't leave an node completely empty later on.
 */
static noinline int balance_level(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root,
			 struct btrfs_path *path, int level)
{}

/* Node balancing for insertion.  Here we only split or push nodes around
 * when they are completely full.  This is also done top down, so we
 * have to be pessimistic.
 */
static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
					  struct btrfs_root *root,
					  struct btrfs_path *path, int level)
{}

/*
 * readahead one full node of leaves, finding things that are close
 * to the block in 'slot', and triggering ra on them.
 */
static void reada_for_search(struct btrfs_fs_info *fs_info,
			     struct btrfs_path *path,
			     int level, int slot, u64 objectid)
{}

static noinline void reada_for_balance(struct btrfs_path *path, int level)
{}


/*
 * when we walk down the tree, it is usually safe to unlock the higher layers
 * in the tree.  The exceptions are when our path goes through slot 0, because
 * operations on the tree might require changing key pointers higher up in the
 * tree.
 *
 * callers might also have set path->keep_locks, which tells this code to keep
 * the lock if the path points to the last slot in the block.  This is part of
 * walking through the tree, and selecting the next slot in the higher block.
 *
 * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
 * if lowest_unlock is 1, level 0 won't be unlocked
 */
static noinline void unlock_up(struct btrfs_path *path, int level,
			       int lowest_unlock, int min_write_lock_level,
			       int *write_lock_level)
{}

/*
 * Helper function for btrfs_search_slot() and other functions that do a search
 * on a btree. The goal is to find a tree block in the cache (the radix tree at
 * fs_info->buffer_radix), but if we can't find it, or it's not up to date, read
 * its pages from disk.
 *
 * Returns -EAGAIN, with the path unlocked, if the caller needs to repeat the
 * whole btree search, starting again from the current root node.
 */
static int
read_block_for_search(struct btrfs_root *root, struct btrfs_path *p,
		      struct extent_buffer **eb_ret, int level, int slot,
		      const struct btrfs_key *key)
{}

/*
 * helper function for btrfs_search_slot.  This does all of the checks
 * for node-level blocks and does any balancing required based on
 * the ins_len.
 *
 * If no extra work was required, zero is returned.  If we had to
 * drop the path, -EAGAIN is returned and btrfs_search_slot must
 * start over
 */
static int
setup_nodes_for_search(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root, struct btrfs_path *p,
		       struct extent_buffer *b, int level, int ins_len,
		       int *write_lock_level)
{}

int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
		u64 iobjectid, u64 ioff, u8 key_type,
		struct btrfs_key *found_key)
{}

static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root,
							struct btrfs_path *p,
							int write_lock_level)
{}

/*
 * Replace the extent buffer at the lowest level of the path with a cloned
 * version. The purpose is to be able to use it safely, after releasing the
 * commit root semaphore, even if relocation is happening in parallel, the
 * transaction used for relocation is committed and the extent buffer is
 * reallocated in the next transaction.
 *
 * This is used in a context where the caller does not prevent transaction
 * commits from happening, either by holding a transaction handle or holding
 * some lock, while it's doing searches through a commit root.
 * At the moment it's only used for send operations.
 */
static int finish_need_commit_sem_search(struct btrfs_path *path)
{}

static inline int search_for_key_slot(struct extent_buffer *eb,
				      int search_low_slot,
				      const struct btrfs_key *key,
				      int prev_cmp,
				      int *slot)
{}

static int search_leaf(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root,
		       const struct btrfs_key *key,
		       struct btrfs_path *path,
		       int ins_len,
		       int prev_cmp)
{}

/*
 * Look for a key in a tree and perform necessary modifications to preserve
 * tree invariants.
 *
 * @trans:	Handle of transaction, used when modifying the tree
 * @p:		Holds all btree nodes along the search path
 * @root:	The root node of the tree
 * @key:	The key we are looking for
 * @ins_len:	Indicates purpose of search:
 *              >0  for inserts it's size of item inserted (*)
 *              <0  for deletions
 *               0  for plain searches, not modifying the tree
 *
 *              (*) If size of item inserted doesn't include
 *              sizeof(struct btrfs_item), then p->search_for_extension must
 *              be set.
 * @cow:	boolean should CoW operations be performed. Must always be 1
 *		when modifying the tree.
 *
 * If @ins_len > 0, nodes and leaves will be split as we walk down the tree.
 * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible)
 *
 * If @key is found, 0 is returned and you can find the item in the leaf level
 * of the path (level 0)
 *
 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
 * points to the slot where it should be inserted
 *
 * If an error is encountered while searching the tree a negative error number
 * is returned
 */
int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		      const struct btrfs_key *key, struct btrfs_path *p,
		      int ins_len, int cow)
{}
ALLOW_ERROR_INJECTION();

/*
 * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
 * current state of the tree together with the operations recorded in the tree
 * modification log to search for the key in a previous version of this tree, as
 * denoted by the time_seq parameter.
 *
 * Naturally, there is no support for insert, delete or cow operations.
 *
 * The resulting path and return value will be set up as if we called
 * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
 */
int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
			  struct btrfs_path *p, u64 time_seq)
{}

/*
 * Search the tree again to find a leaf with smaller keys.
 * Returns 0 if it found something.
 * Returns 1 if there are no smaller keys.
 * Returns < 0 on error.
 *
 * This may release the path, and so you may lose any locks held at the
 * time you call it.
 */
static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
{}

/*
 * helper to use instead of search slot if no exact match is needed but
 * instead the next or previous item should be returned.
 * When find_higher is true, the next higher item is returned, the next lower
 * otherwise.
 * When return_any and find_higher are both true, and no higher item is found,
 * return the next lower instead.
 * When return_any is true and find_higher is false, and no lower item is found,
 * return the next higher instead.
 * It returns 0 if any item is found, 1 if none is found (tree empty), and
 * < 0 on error
 */
int btrfs_search_slot_for_read(struct btrfs_root *root,
			       const struct btrfs_key *key,
			       struct btrfs_path *p, int find_higher,
			       int return_any)
{}

/*
 * Execute search and call btrfs_previous_item to traverse backwards if the item
 * was not found.
 *
 * Return 0 if found, 1 if not found and < 0 if error.
 */
int btrfs_search_backwards(struct btrfs_root *root, struct btrfs_key *key,
			   struct btrfs_path *path)
{}

/*
 * Search for a valid slot for the given path.
 *
 * @root:	The root node of the tree.
 * @key:	Will contain a valid item if found.
 * @path:	The starting point to validate the slot.
 *
 * Return: 0  if the item is valid
 *         1  if not found
 *         <0 if error.
 */
int btrfs_get_next_valid_item(struct btrfs_root *root, struct btrfs_key *key,
			      struct btrfs_path *path)
{}

/*
 * adjust the pointers going up the tree, starting at level
 * making sure the right key of each node is points to 'key'.
 * This is used after shifting pointers to the left, so it stops
 * fixing up pointers when a given leaf/node is not in slot 0 of the
 * higher levels
 *
 */
static void fixup_low_keys(struct btrfs_trans_handle *trans,
			   struct btrfs_path *path,
			   struct btrfs_disk_key *key, int level)
{}

/*
 * update item key.
 *
 * This function isn't completely safe. It's the caller's responsibility
 * that the new key won't break the order
 */
void btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
			     struct btrfs_path *path,
			     const struct btrfs_key *new_key)
{}

/*
 * Check key order of two sibling extent buffers.
 *
 * Return true if something is wrong.
 * Return false if everything is fine.
 *
 * Tree-checker only works inside one tree block, thus the following
 * corruption can not be detected by tree-checker:
 *
 * Leaf @left			| Leaf @right
 * --------------------------------------------------------------
 * | 1 | 2 | 3 | 4 | 5 | f6 |   | 7 | 8 |
 *
 * Key f6 in leaf @left itself is valid, but not valid when the next
 * key in leaf @right is 7.
 * This can only be checked at tree block merge time.
 * And since tree checker has ensured all key order in each tree block
 * is correct, we only need to bother the last key of @left and the first
 * key of @right.
 */
static bool check_sibling_keys(struct extent_buffer *left,
			       struct extent_buffer *right)
{}

/*
 * try to push data from one node into the next node left in the
 * tree.
 *
 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
 * error, and > 0 if there was no room in the left hand block.
 */
static int push_node_left(struct btrfs_trans_handle *trans,
			  struct extent_buffer *dst,
			  struct extent_buffer *src, int empty)
{}

/*
 * try to push data from one node into the next node right in the
 * tree.
 *
 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
 * error, and > 0 if there was no room in the right hand block.
 *
 * this will  only push up to 1/2 the contents of the left node over
 */
static int balance_node_right(struct btrfs_trans_handle *trans,
			      struct extent_buffer *dst,
			      struct extent_buffer *src)
{}

/*
 * helper function to insert a new root level in the tree.
 * A new node is allocated, and a single item is inserted to
 * point to the existing root
 *
 * returns zero on success or < 0 on failure.
 */
static noinline int insert_new_root(struct btrfs_trans_handle *trans,
			   struct btrfs_root *root,
			   struct btrfs_path *path, int level)
{}

/*
 * worker function to insert a single pointer in a node.
 * the node should have enough room for the pointer already
 *
 * slot and level indicate where you want the key to go, and
 * blocknr is the block the key points to.
 */
static int insert_ptr(struct btrfs_trans_handle *trans,
		      struct btrfs_path *path,
		      struct btrfs_disk_key *key, u64 bytenr,
		      int slot, int level)
{}

/*
 * split the node at the specified level in path in two.
 * The path is corrected to point to the appropriate node after the split
 *
 * Before splitting this tries to make some room in the node by pushing
 * left and right, if either one works, it returns right away.
 *
 * returns 0 on success and < 0 on failure
 */
static noinline int split_node(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       struct btrfs_path *path, int level)
{}

/*
 * how many bytes are required to store the items in a leaf.  start
 * and nr indicate which items in the leaf to check.  This totals up the
 * space used both by the item structs and the item data
 */
static int leaf_space_used(const struct extent_buffer *l, int start, int nr)
{}

/*
 * The space between the end of the leaf items and
 * the start of the leaf data.  IOW, how much room
 * the leaf has left for both items and data
 */
int btrfs_leaf_free_space(const struct extent_buffer *leaf)
{}

/*
 * min slot controls the lowest index we're willing to push to the
 * right.  We'll push up to and including min_slot, but no lower
 */
static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
				      struct btrfs_path *path,
				      int data_size, int empty,
				      struct extent_buffer *right,
				      int free_space, u32 left_nritems,
				      u32 min_slot)
{}

/*
 * push some data in the path leaf to the right, trying to free up at
 * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 *
 * returns 1 if the push failed because the other node didn't have enough
 * room, 0 if everything worked out and < 0 if there were major errors.
 *
 * this will push starting from min_slot to the end of the leaf.  It won't
 * push any slot lower than min_slot
 */
static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
			   *root, struct btrfs_path *path,
			   int min_data_size, int data_size,
			   int empty, u32 min_slot)
{}

/*
 * push some data in the path leaf to the left, trying to free up at
 * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 *
 * max_slot can put a limit on how far into the leaf we'll push items.  The
 * item at 'max_slot' won't be touched.  Use (u32)-1 to make us do all the
 * items
 */
static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
				     struct btrfs_path *path, int data_size,
				     int empty, struct extent_buffer *left,
				     int free_space, u32 right_nritems,
				     u32 max_slot)
{}

/*
 * push some data in the path leaf to the left, trying to free up at
 * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 *
 * max_slot can put a limit on how far into the leaf we'll push items.  The
 * item at 'max_slot' won't be touched.  Use (u32)-1 to make us push all the
 * items
 */
static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
			  *root, struct btrfs_path *path, int min_data_size,
			  int data_size, int empty, u32 max_slot)
{}

/*
 * split the path's leaf in two, making sure there is at least data_size
 * available for the resulting leaf level of the path.
 */
static noinline int copy_for_split(struct btrfs_trans_handle *trans,
				   struct btrfs_path *path,
				   struct extent_buffer *l,
				   struct extent_buffer *right,
				   int slot, int mid, int nritems)
{}

/*
 * double splits happen when we need to insert a big item in the middle
 * of a leaf.  A double split can leave us with 3 mostly empty leaves:
 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
 *          A                 B                 C
 *
 * We avoid this by trying to push the items on either side of our target
 * into the adjacent leaves.  If all goes well we can avoid the double split
 * completely.
 */
static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
					  struct btrfs_root *root,
					  struct btrfs_path *path,
					  int data_size)
{}

/*
 * split the path's leaf in two, making sure there is at least data_size
 * available for the resulting leaf level of the path.
 *
 * returns 0 if all went well and < 0 on failure.
 */
static noinline int split_leaf(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       const struct btrfs_key *ins_key,
			       struct btrfs_path *path, int data_size,
			       int extend)
{}

static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
					 struct btrfs_root *root,
					 struct btrfs_path *path, int ins_len)
{}

static noinline int split_item(struct btrfs_trans_handle *trans,
			       struct btrfs_path *path,
			       const struct btrfs_key *new_key,
			       unsigned long split_offset)
{}

/*
 * This function splits a single item into two items,
 * giving 'new_key' to the new item and splitting the
 * old one at split_offset (from the start of the item).
 *
 * The path may be released by this operation.  After
 * the split, the path is pointing to the old item.  The
 * new item is going to be in the same node as the old one.
 *
 * Note, the item being split must be smaller enough to live alone on
 * a tree block with room for one extra struct btrfs_item
 *
 * This allows us to split the item in place, keeping a lock on the
 * leaf the entire time.
 */
int btrfs_split_item(struct btrfs_trans_handle *trans,
		     struct btrfs_root *root,
		     struct btrfs_path *path,
		     const struct btrfs_key *new_key,
		     unsigned long split_offset)
{}

/*
 * make the item pointed to by the path smaller.  new_size indicates
 * how small to make it, and from_end tells us if we just chop bytes
 * off the end of the item or if we shift the item to chop bytes off
 * the front.
 */
void btrfs_truncate_item(struct btrfs_trans_handle *trans,
			 struct btrfs_path *path, u32 new_size, int from_end)
{}

/*
 * make the item pointed to by the path bigger, data_size is the added size.
 */
void btrfs_extend_item(struct btrfs_trans_handle *trans,
		       struct btrfs_path *path, u32 data_size)
{}

/*
 * Make space in the node before inserting one or more items.
 *
 * @trans:	transaction handle
 * @root:	root we are inserting items to
 * @path:	points to the leaf/slot where we are going to insert new items
 * @batch:      information about the batch of items to insert
 *
 * Main purpose is to save stack depth by doing the bulk of the work in a
 * function that doesn't call btrfs_search_slot
 */
static void setup_items_for_insert(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root, struct btrfs_path *path,
				   const struct btrfs_item_batch *batch)
{}

/*
 * Insert a new item into a leaf.
 *
 * @trans:     Transaction handle.
 * @root:      The root of the btree.
 * @path:      A path pointing to the target leaf and slot.
 * @key:       The key of the new item.
 * @data_size: The size of the data associated with the new key.
 */
void btrfs_setup_item_for_insert(struct btrfs_trans_handle *trans,
				 struct btrfs_root *root,
				 struct btrfs_path *path,
				 const struct btrfs_key *key,
				 u32 data_size)
{}

/*
 * Given a key and some data, insert items into the tree.
 * This does all the path init required, making room in the tree if needed.
 *
 * Returns: 0        on success
 *          -EEXIST  if the first key already exists
 *          < 0      on other errors
 */
int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root,
			    struct btrfs_path *path,
			    const struct btrfs_item_batch *batch)
{}

/*
 * Given a key and some data, insert an item into the tree.
 * This does all the path init required, making room in the tree if needed.
 */
int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		      const struct btrfs_key *cpu_key, void *data,
		      u32 data_size)
{}

/*
 * This function duplicates an item, giving 'new_key' to the new item.
 * It guarantees both items live in the same tree leaf and the new item is
 * contiguous with the original item.
 *
 * This allows us to split a file extent in place, keeping a lock on the leaf
 * the entire time.
 */
int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root,
			 struct btrfs_path *path,
			 const struct btrfs_key *new_key)
{}

/*
 * delete the pointer from a given node.
 *
 * the tree should have been previously balanced so the deletion does not
 * empty a node.
 *
 * This is exported for use inside btrfs-progs, don't un-export it.
 */
int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		  struct btrfs_path *path, int level, int slot)
{}

/*
 * a helper function to delete the leaf pointed to by path->slots[1] and
 * path->nodes[1].
 *
 * This deletes the pointer in path->nodes[1] and frees the leaf
 * block extent.  zero is returned if it all worked out, < 0 otherwise.
 *
 * The path must have already been setup for deleting the leaf, including
 * all the proper balancing.  path->nodes[1] must be locked.
 */
static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct btrfs_path *path,
				   struct extent_buffer *leaf)
{}
/*
 * delete the item at the leaf level in path.  If that empties
 * the leaf, remove it from the tree
 */
int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		    struct btrfs_path *path, int slot, int nr)
{}

/*
 * A helper function to walk down the tree starting at min_key, and looking
 * for nodes or leaves that are have a minimum transaction id.
 * This is used by the btree defrag code, and tree logging
 *
 * This does not cow, but it does stuff the starting key it finds back
 * into min_key, so you can call btrfs_search_slot with cow=1 on the
 * key and get a writable path.
 *
 * This honors path->lowest_level to prevent descent past a given level
 * of the tree.
 *
 * min_trans indicates the oldest transaction that you are interested
 * in walking through.  Any nodes or leaves older than min_trans are
 * skipped over (without reading them).
 *
 * returns zero if something useful was found, < 0 on error and 1 if there
 * was nothing in the tree that matched the search criteria.
 */
int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
			 struct btrfs_path *path,
			 u64 min_trans)
{}

/*
 * this is similar to btrfs_next_leaf, but does not try to preserve
 * and fixup the path.  It looks for and returns the next key in the
 * tree based on the current path and the min_trans parameters.
 *
 * 0 is returned if another key is found, < 0 if there are any errors
 * and 1 is returned if there are no higher keys in the tree
 *
 * path->keep_locks should be set to 1 on the search made before
 * calling this function.
 */
int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
			struct btrfs_key *key, int level, u64 min_trans)
{}

int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
			u64 time_seq)
{}

int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq)
{}

/*
 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
 * searching until it gets past min_objectid or finds an item of 'type'
 *
 * returns 0 if something is found, 1 if nothing was found and < 0 on error
 */
int btrfs_previous_item(struct btrfs_root *root,
			struct btrfs_path *path, u64 min_objectid,
			int type)
{}

/*
 * search in extent tree to find a previous Metadata/Data extent item with
 * min objecitd.
 *
 * returns 0 if something is found, 1 if nothing was found and < 0 on error
 */
int btrfs_previous_extent_item(struct btrfs_root *root,
			struct btrfs_path *path, u64 min_objectid)
{}

int __init btrfs_ctree_init(void)
{}

void __cold btrfs_ctree_exit(void)
{}