// SPDX-License-Identifier: GPL-2.0 #include <linux/slab.h> #include <trace/events/btrfs.h> #include "messages.h" #include "ctree.h" #include "extent_io.h" #include "extent-io-tree.h" #include "btrfs_inode.h" static struct kmem_cache *extent_state_cache; static inline bool extent_state_in_tree(const struct extent_state *state) { … } #ifdef CONFIG_BTRFS_DEBUG static LIST_HEAD(states); static DEFINE_SPINLOCK(leak_lock); static inline void btrfs_leak_debug_add_state(struct extent_state *state) { … } static inline void btrfs_leak_debug_del_state(struct extent_state *state) { … } static inline void btrfs_extent_state_leak_debug_check(void) { … } #define btrfs_debug_check_extent_io_range(tree, start, end) … static inline void __btrfs_debug_check_extent_io_range(const char *caller, struct extent_io_tree *tree, u64 start, u64 end) { … } #else #define btrfs_leak_debug_add_state … #define btrfs_leak_debug_del_state … #define btrfs_extent_state_leak_debug_check … #define btrfs_debug_check_extent_io_range … #endif /* * The only tree allowed to set the inode is IO_TREE_INODE_IO. */ static bool is_inode_io_tree(const struct extent_io_tree *tree) { … } /* Return the inode if it's valid for the given tree, otherwise NULL. */ struct btrfs_inode *extent_io_tree_to_inode(struct extent_io_tree *tree) { … } /* Read-only access to the inode. */ const struct btrfs_inode *extent_io_tree_to_inode_const(const struct extent_io_tree *tree) { … } /* For read-only access to fs_info. */ const struct btrfs_fs_info *extent_io_tree_to_fs_info(const struct extent_io_tree *tree) { … } void extent_io_tree_init(struct btrfs_fs_info *fs_info, struct extent_io_tree *tree, unsigned int owner) { … } /* * Empty an io tree, removing and freeing every extent state record from the * tree. This should be called once we are sure no other task can access the * tree anymore, so no tree updates happen after we empty the tree and there * aren't any waiters on any extent state record (EXTENT_LOCKED bit is never * set on any extent state when calling this function). */ void extent_io_tree_release(struct extent_io_tree *tree) { … } static struct extent_state *alloc_extent_state(gfp_t mask) { … } static struct extent_state *alloc_extent_state_atomic(struct extent_state *prealloc) { … } void free_extent_state(struct extent_state *state) { … } static int add_extent_changeset(struct extent_state *state, u32 bits, struct extent_changeset *changeset, int set) { … } static inline struct extent_state *next_state(struct extent_state *state) { … } static inline struct extent_state *prev_state(struct extent_state *state) { … } /* * Search @tree for an entry that contains @offset. Such entry would have * entry->start <= offset && entry->end >= offset. * * @tree: the tree to search * @offset: offset that should fall within an entry in @tree * @node_ret: pointer where new node should be anchored (used when inserting an * entry in the tree) * @parent_ret: points to entry which would have been the parent of the entry, * containing @offset * * Return a pointer to the entry that contains @offset byte address and don't change * @node_ret and @parent_ret. * * If no such entry exists, return pointer to entry that ends before @offset * and fill parameters @node_ret and @parent_ret, ie. does not return NULL. */ static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree, u64 offset, struct rb_node ***node_ret, struct rb_node **parent_ret) { … } /* * Search offset in the tree or fill neighbor rbtree node pointers. * * @tree: the tree to search * @offset: offset that should fall within an entry in @tree * @next_ret: pointer to the first entry whose range ends after @offset * @prev_ret: pointer to the first entry whose range begins before @offset * * Return a pointer to the entry that contains @offset byte address. If no * such entry exists, then return NULL and fill @prev_ret and @next_ret. * Otherwise return the found entry and other pointers are left untouched. */ static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree, u64 offset, struct extent_state **prev_ret, struct extent_state **next_ret) { … } /* * Inexact rb-tree search, return the next entry if @offset is not found */ static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset) { … } static void extent_io_tree_panic(const struct extent_io_tree *tree, const struct extent_state *state, const char *opname, int err) { … } static void merge_prev_state(struct extent_io_tree *tree, struct extent_state *state) { … } static void merge_next_state(struct extent_io_tree *tree, struct extent_state *state) { … } /* * Utility function to look for merge candidates inside a given range. Any * extents with matching state are merged together into a single extent in the * tree. Extents with EXTENT_IO in their state field are not merged because * the end_io handlers need to be able to do operations on them without * sleeping (or doing allocations/splits). * * This should be called with the tree lock held. */ static void merge_state(struct extent_io_tree *tree, struct extent_state *state) { … } static void set_state_bits(struct extent_io_tree *tree, struct extent_state *state, u32 bits, struct extent_changeset *changeset) { … } /* * Insert an extent_state struct into the tree. 'bits' are set on the * struct before it is inserted. * * Returns a pointer to the struct extent_state record containing the range * requested for insertion, which may be the same as the given struct or it * may be an existing record in the tree that was expanded to accommodate the * requested range. In case of an extent_state different from the one that was * given, the later can be freed or reused by the caller. * * On error it returns an error pointer. * * The tree lock is not taken internally. This is a utility function and * probably isn't what you want to call (see set/clear_extent_bit). */ static struct extent_state *insert_state(struct extent_io_tree *tree, struct extent_state *state, u32 bits, struct extent_changeset *changeset) { … } /* * Insert state to @tree to the location given by @node and @parent. */ static void insert_state_fast(struct extent_io_tree *tree, struct extent_state *state, struct rb_node **node, struct rb_node *parent, unsigned bits, struct extent_changeset *changeset) { … } /* * Split a given extent state struct in two, inserting the preallocated * struct 'prealloc' as the newly created second half. 'split' indicates an * offset inside 'orig' where it should be split. * * Before calling, * the tree has 'orig' at [orig->start, orig->end]. After calling, there * are two extent state structs in the tree: * prealloc: [orig->start, split - 1] * orig: [ split, orig->end ] * * The tree locks are not taken by this function. They need to be held * by the caller. */ static int split_state(struct extent_io_tree *tree, struct extent_state *orig, struct extent_state *prealloc, u64 split) { … } /* * Utility function to clear some bits in an extent state struct. It will * optionally wake up anyone waiting on this state (wake == 1). * * If no bits are set on the state struct after clearing things, the * struct is freed and removed from the tree */ static struct extent_state *clear_state_bit(struct extent_io_tree *tree, struct extent_state *state, u32 bits, int wake, struct extent_changeset *changeset) { … } /* * Detect if extent bits request NOWAIT semantics and set the gfp mask accordingly, * unset the EXTENT_NOWAIT bit. */ static void set_gfp_mask_from_bits(u32 *bits, gfp_t *mask) { … } /* * Clear some bits on a range in the tree. This may require splitting or * inserting elements in the tree, so the gfp mask is used to indicate which * allocations or sleeping are allowed. * * Pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove the given * range from the tree regardless of state (ie for truncate). * * The range [start, end] is inclusive. * * This takes the tree lock, and returns 0 on success and < 0 on error. */ int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, struct extent_state **cached_state, struct extent_changeset *changeset) { … } /* * Wait for one or more bits to clear on a range in the state tree. * The range [start, end] is inclusive. * The tree lock is taken by this function */ static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, struct extent_state **cached_state) { … } static void cache_state_if_flags(struct extent_state *state, struct extent_state **cached_ptr, unsigned flags) { … } static void cache_state(struct extent_state *state, struct extent_state **cached_ptr) { … } /* * Find the first state struct with 'bits' set after 'start', and return it. * tree->lock must be held. NULL will returned if nothing was found after * 'start'. */ static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree, u64 start, u32 bits) { … } /* * Find the first offset in the io tree with one or more @bits set. * * Note: If there are multiple bits set in @bits, any of them will match. * * Return true if we find something, and update @start_ret and @end_ret. * Return false if we found nothing. */ bool find_first_extent_bit(struct extent_io_tree *tree, u64 start, u64 *start_ret, u64 *end_ret, u32 bits, struct extent_state **cached_state) { … } /* * Find a contiguous area of bits * * @tree: io tree to check * @start: offset to start the search from * @start_ret: the first offset we found with the bits set * @end_ret: the final contiguous range of the bits that were set * @bits: bits to look for * * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges * to set bits appropriately, and then merge them again. During this time it * will drop the tree->lock, so use this helper if you want to find the actual * contiguous area for given bits. We will search to the first bit we find, and * then walk down the tree until we find a non-contiguous area. The area * returned will be the full contiguous area with the bits set. */ int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start, u64 *start_ret, u64 *end_ret, u32 bits) { … } /* * Find a contiguous range of bytes in the file marked as delalloc, not more * than 'max_bytes'. start and end are used to return the range, * * True is returned if we find something, false if nothing was in the tree. */ bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start, u64 *end, u64 max_bytes, struct extent_state **cached_state) { … } /* * Set some bits on a range in the tree. This may require allocations or * sleeping. By default all allocations use GFP_NOFS, use EXTENT_NOWAIT for * GFP_NOWAIT. * * If any of the exclusive bits are set, this will fail with -EEXIST if some * part of the range already has the desired bits set. The extent_state of the * existing range is returned in failed_state in this case, and the start of the * existing range is returned in failed_start. failed_state is used as an * optimization for wait_extent_bit, failed_start must be used as the source of * truth as failed_state may have changed since we returned. * * [start, end] is inclusive This takes the tree lock. */ static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, u64 *failed_start, struct extent_state **failed_state, struct extent_state **cached_state, struct extent_changeset *changeset) { … } int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, struct extent_state **cached_state) { … } /* * Convert all bits in a given range from one bit to another * * @tree: the io tree to search * @start: the start offset in bytes * @end: the end offset in bytes (inclusive) * @bits: the bits to set in this range * @clear_bits: the bits to clear in this range * @cached_state: state that we're going to cache * * This will go through and set bits for the given range. If any states exist * already in this range they are set with the given bit and cleared of the * clear_bits. This is only meant to be used by things that are mergeable, ie. * converting from say DELALLOC to DIRTY. This is not meant to be used with * boundary bits like LOCK. * * All allocations are done with GFP_NOFS. */ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, u32 clear_bits, struct extent_state **cached_state) { … } /* * Find the first range that has @bits not set. This range could start before * @start. * * @tree: the tree to search * @start: offset at/after which the found extent should start * @start_ret: records the beginning of the range * @end_ret: records the end of the range (inclusive) * @bits: the set of bits which must be unset * * Since unallocated range is also considered one which doesn't have the bits * set it's possible that @end_ret contains -1, this happens in case the range * spans (last_range_end, end of device]. In this case it's up to the caller to * trim @end_ret to the appropriate size. */ void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 *start_ret, u64 *end_ret, u32 bits) { … } /* * Count the number of bytes in the tree that have a given bit(s) set for a * given range. * * @tree: The io tree to search. * @start: The start offset of the range. This value is updated to the * offset of the first byte found with the given bit(s), so it * can end up being bigger than the initial value. * @search_end: The end offset (inclusive value) of the search range. * @max_bytes: The maximum byte count we are interested. The search stops * once it reaches this count. * @bits: The bits the range must have in order to be accounted for. * If multiple bits are set, then only subranges that have all * the bits set are accounted for. * @contig: Indicate if we should ignore holes in the range or not. If * this is true, then stop once we find a hole. * @cached_state: A cached state to be used across multiple calls to this * function in order to speedup searches. Use NULL if this is * called only once or if each call does not start where the * previous one ended. * * Returns the total number of bytes found within the given range that have * all given bits set. If the returned number of bytes is greater than zero * then @start is updated with the offset of the first byte with the bits set. */ u64 count_range_bits(struct extent_io_tree *tree, u64 *start, u64 search_end, u64 max_bytes, u32 bits, int contig, struct extent_state **cached_state) { … } /* * Check if the single @bit exists in the given range. */ bool test_range_bit_exists(struct extent_io_tree *tree, u64 start, u64 end, u32 bit) { … } /* * Check if the whole range [@start,@end) contains the single @bit set. */ bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit, struct extent_state *cached) { … } /* Wrappers around set/clear extent bit */ int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, struct extent_changeset *changeset) { … } int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, struct extent_changeset *changeset) { … } int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end, struct extent_state **cached) { … } /* * Either insert or lock state struct between start and end use mask to tell * us if waiting is desired. */ int lock_extent(struct extent_io_tree *tree, u64 start, u64 end, struct extent_state **cached_state) { … } void __cold extent_state_free_cachep(void) { … } int __init extent_state_init_cachep(void) { … }
Codebase Browser
linux