extent_map.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0

#include <linux/err.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include "messages.h"
#include "ctree.h"
#include "extent_map.h"
#include "compression.h"
#include "btrfs_inode.h"
#include "disk-io.h"


static struct kmem_cache *extent_map_cache;

int __init extent_map_init(void)
{ … }

void __cold extent_map_exit(void)
{ … }

/*
 * Initialize the extent tree @tree.  Should be called for each new inode or
 * other user of the extent_map interface.
 */
void extent_map_tree_init(struct extent_map_tree *tree)
{ … }

/*
 * Allocate a new extent_map structure.  The new structure is returned with a
 * reference count of one and needs to be freed using free_extent_map()
 */
struct extent_map *alloc_extent_map(void)
{ … }

/*
 * Drop the reference out on @em by one and free the structure if the reference
 * count hits zero.
 */
void free_extent_map(struct extent_map *em)
{ … }

/* Do the math around the end of an extent, handling wrapping. */
static u64 range_end(u64 start, u64 len)
{ … }

static void dec_evictable_extent_maps(struct btrfs_inode *inode)
{ … }

static int tree_insert(struct rb_root *root, struct extent_map *em)
{ … }

/*
 * Search through the tree for an extent_map with a given offset.  If it can't
 * be found, try to find some neighboring extents
 */
static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
				     struct rb_node **prev_or_next_ret)
{ … }

static inline u64 extent_map_block_len(const struct extent_map *em)
{ … }

static inline u64 extent_map_block_end(const struct extent_map *em)
{ … }

static bool can_merge_extent_map(const struct extent_map *em)
{ … }

/* Check to see if two extent_map structs are adjacent and safe to merge. */
static bool mergeable_maps(const struct extent_map *prev, const struct extent_map *next)
{ … }

/*
 * Handle the on-disk data extents merge for @prev and @next.
 *
 * Only touches disk_bytenr/disk_num_bytes/offset/ram_bytes.
 * For now only uncompressed regular extent can be merged.
 *
 * @prev and @next will be both updated to point to the new merged range.
 * Thus one of them should be removed by the caller.
 */
static void merge_ondisk_extents(struct extent_map *prev, struct extent_map *next)
{ … }

static void dump_extent_map(struct btrfs_fs_info *fs_info, const char *prefix,
			    struct extent_map *em)
{ … }

/* Internal sanity checks for btrfs debug builds. */
static void validate_extent_map(struct btrfs_fs_info *fs_info, struct extent_map *em)
{ … }

static void try_merge_map(struct btrfs_inode *inode, struct extent_map *em)
{ … }

/*
 * Unpin an extent from the cache.
 *
 * @inode:	the inode from which we are unpinning an extent range
 * @start:	logical offset in the file
 * @len:	length of the extent
 * @gen:	generation that this extent has been modified in
 *
 * Called after an extent has been written to disk properly.  Set the generation
 * to the generation that actually added the file item to the inode so we know
 * we need to sync this extent when we call fsync().
 *
 * Returns: 0	     on success
 * 	    -ENOENT  when the extent is not found in the tree
 * 	    -EUCLEAN if the found extent does not match the expected start
 */
int unpin_extent_cache(struct btrfs_inode *inode, u64 start, u64 len, u64 gen)
{ … }

void clear_em_logging(struct btrfs_inode *inode, struct extent_map *em)
{ … }

static inline void setup_extent_mapping(struct btrfs_inode *inode,
					struct extent_map *em,
					int modified)
{ … }

/*
 * Add a new extent map to an inode's extent map tree.
 *
 * @inode:	the target inode
 * @em:		map to insert
 * @modified:	indicate whether the given @em should be added to the
 *	        modified list, which indicates the extent needs to be logged
 *
 * Insert @em into the @inode's extent map tree or perform a simple
 * forward/backward merge with existing mappings.  The extent_map struct passed
 * in will be inserted into the tree directly, with an additional reference
 * taken, or a reference dropped if the merge attempt was successful.
 */
static int add_extent_mapping(struct btrfs_inode *inode,
			      struct extent_map *em, int modified)
{ … }

static struct extent_map *
__lookup_extent_mapping(struct extent_map_tree *tree,
			u64 start, u64 len, int strict)
{ … }

/*
 * Lookup extent_map that intersects @start + @len range.
 *
 * @tree:	tree to lookup in
 * @start:	byte offset to start the search
 * @len:	length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.  There may be additional objects in the tree that
 * intersect, so check the object returned carefully to make sure that no
 * additional lookups are needed.
 */
struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{ … }

/*
 * Find a nearby extent map intersecting @start + @len (not an exact search).
 *
 * @tree:	tree to lookup in
 * @start:	byte offset to start the search
 * @len:	length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.
 *
 * If one can't be found, any nearby extent may be returned
 */
struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{ … }

/*
 * Remove an extent_map from its inode's extent tree.
 *
 * @inode:	the inode the extent map belongs to
 * @em:		extent map being removed
 *
 * Remove @em from the extent tree of @inode.  No reference counts are dropped,
 * and no checks are done to see if the range is in use.
 */
void remove_extent_mapping(struct btrfs_inode *inode, struct extent_map *em)
{ … }

static void replace_extent_mapping(struct btrfs_inode *inode,
				   struct extent_map *cur,
				   struct extent_map *new,
				   int modified)
{ … }

static struct extent_map *next_extent_map(const struct extent_map *em)
{ … }

static struct extent_map *prev_extent_map(struct extent_map *em)
{ … }

/*
 * Helper for btrfs_get_extent.  Given an existing extent in the tree,
 * the existing extent is the nearest extent to map_start,
 * and an extent that you want to insert, deal with overlap and insert
 * the best fitted new extent into the tree.
 */
static noinline int merge_extent_mapping(struct btrfs_inode *inode,
					 struct extent_map *existing,
					 struct extent_map *em,
					 u64 map_start)
{ … }

/*
 * Add extent mapping into an inode's extent map tree.
 *
 * @inode:    target inode
 * @em_in:    extent we are inserting
 * @start:    start of the logical range btrfs_get_extent() is requesting
 * @len:      length of the logical range btrfs_get_extent() is requesting
 *
 * Note that @em_in's range may be different from [start, start+len),
 * but they must be overlapped.
 *
 * Insert @em_in into the inode's extent map tree. In case there is an
 * overlapping range, handle the -EEXIST by either:
 * a) Returning the existing extent in @em_in if @start is within the
 *    existing em.
 * b) Merge the existing extent with @em_in passed in.
 *
 * Return 0 on success, otherwise -EEXIST.
 *
 */
int btrfs_add_extent_mapping(struct btrfs_inode *inode,
			     struct extent_map **em_in, u64 start, u64 len)
{ … }

/*
 * Drop all extent maps from a tree in the fastest possible way, rescheduling
 * if needed. This avoids searching the tree, from the root down to the first
 * extent map, before each deletion.
 */
static void drop_all_extent_maps_fast(struct btrfs_inode *inode)
{ … }

/*
 * Drop all extent maps in a given range.
 *
 * @inode:       The target inode.
 * @start:       Start offset of the range.
 * @end:         End offset of the range (inclusive value).
 * @skip_pinned: Indicate if pinned extent maps should be ignored or not.
 *
 * This drops all the extent maps that intersect the given range [@start, @end].
 * Extent maps that partially overlap the range and extend behind or beyond it,
 * are split.
 * The caller should have locked an appropriate file range in the inode's io
 * tree before calling this function.
 */
void btrfs_drop_extent_map_range(struct btrfs_inode *inode, u64 start, u64 end,
				 bool skip_pinned)
{ … }

/*
 * Replace a range in the inode's extent map tree with a new extent map.
 *
 * @inode:      The target inode.
 * @new_em:     The new extent map to add to the inode's extent map tree.
 * @modified:   Indicate if the new extent map should be added to the list of
 *              modified extents (for fast fsync tracking).
 *
 * Drops all the extent maps in the inode's extent map tree that intersect the
 * range of the new extent map and adds the new extent map to the tree.
 * The caller should have locked an appropriate file range in the inode's io
 * tree before calling this function.
 */
int btrfs_replace_extent_map_range(struct btrfs_inode *inode,
				   struct extent_map *new_em,
				   bool modified)
{ … }

/*
 * Split off the first pre bytes from the extent_map at [start, start + len],
 * and set the block_start for it to new_logical.
 *
 * This function is used when an ordered_extent needs to be split.
 */
int split_extent_map(struct btrfs_inode *inode, u64 start, u64 len, u64 pre,
		     u64 new_logical)
{ … }

struct btrfs_em_shrink_ctx { … };

static long btrfs_scan_inode(struct btrfs_inode *inode, struct btrfs_em_shrink_ctx *ctx)
{ … }

static long btrfs_scan_root(struct btrfs_root *root, struct btrfs_em_shrink_ctx *ctx)
{ … }

long btrfs_free_extent_maps(struct btrfs_fs_info *fs_info, long nr_to_scan)
{ … }
linux/fs/btrfs/extent_map.c
