linux/fs/xfs/libxfs/xfs_rmap.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2014 Red Hat, Inc.
 * All Rights Reserved.
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_log_format.h"
#include "xfs_trans_resv.h"
#include "xfs_bit.h"
#include "xfs_mount.h"
#include "xfs_sb.h"
#include "xfs_defer.h"
#include "xfs_btree.h"
#include "xfs_trans.h"
#include "xfs_alloc.h"
#include "xfs_rmap.h"
#include "xfs_rmap_btree.h"
#include "xfs_trace.h"
#include "xfs_errortag.h"
#include "xfs_error.h"
#include "xfs_inode.h"
#include "xfs_ag.h"
#include "xfs_health.h"
#include "xfs_rmap_item.h"

struct kmem_cache	*xfs_rmap_intent_cache;

/*
 * Lookup the first record less than or equal to [bno, len, owner, offset]
 * in the btree given by cur.
 */
int
xfs_rmap_lookup_le(
	struct xfs_btree_cur	*cur,
	xfs_agblock_t		bno,
	uint64_t		owner,
	uint64_t		offset,
	unsigned int		flags,
	struct xfs_rmap_irec	*irec,
	int			*stat)
{ … }

/*
 * Lookup the record exactly matching [bno, len, owner, offset]
 * in the btree given by cur.
 */
int
xfs_rmap_lookup_eq(
	struct xfs_btree_cur	*cur,
	xfs_agblock_t		bno,
	xfs_extlen_t		len,
	uint64_t		owner,
	uint64_t		offset,
	unsigned int		flags,
	int			*stat)
{ … }

/*
 * Update the record referred to by cur to the value given
 * by [bno, len, owner, offset].
 * This either works (return 0) or gets an EFSCORRUPTED error.
 */
STATIC int
xfs_rmap_update(
	struct xfs_btree_cur	*cur,
	struct xfs_rmap_irec	*irec)
{ … }

int
xfs_rmap_insert(
	struct xfs_btree_cur	*rcur,
	xfs_agblock_t		agbno,
	xfs_extlen_t		len,
	uint64_t		owner,
	uint64_t		offset,
	unsigned int		flags)
{ … }

STATIC int
xfs_rmap_delete(
	struct xfs_btree_cur	*rcur,
	xfs_agblock_t		agbno,
	xfs_extlen_t		len,
	uint64_t		owner,
	uint64_t		offset,
	unsigned int		flags)
{ … }

/* Convert an internal btree record to an rmap record. */
xfs_failaddr_t
xfs_rmap_btrec_to_irec(
	const union xfs_btree_rec	*rec,
	struct xfs_rmap_irec		*irec)
{ … }

/* Simple checks for rmap records. */
xfs_failaddr_t
xfs_rmap_check_irec(
	struct xfs_perag		*pag,
	const struct xfs_rmap_irec	*irec)
{ … }

static inline xfs_failaddr_t
xfs_rmap_check_btrec(
	struct xfs_btree_cur		*cur,
	const struct xfs_rmap_irec	*irec)
{ … }

static inline int
xfs_rmap_complain_bad_rec(
	struct xfs_btree_cur		*cur,
	xfs_failaddr_t			fa,
	const struct xfs_rmap_irec	*irec)
{ … }

/*
 * Get the data from the pointed-to record.
 */
int
xfs_rmap_get_rec(
	struct xfs_btree_cur	*cur,
	struct xfs_rmap_irec	*irec,
	int			*stat)
{ … }

struct xfs_find_left_neighbor_info { … };

/* For each rmap given, figure out if it matches the key we want. */
STATIC int
xfs_rmap_find_left_neighbor_helper(
	struct xfs_btree_cur		*cur,
	const struct xfs_rmap_irec	*rec,
	void				*priv)
{ … }

/*
 * Find the record to the left of the given extent, being careful only to
 * return a match with the same owner and adjacent physical and logical
 * block ranges.
 */
STATIC int
xfs_rmap_find_left_neighbor(
	struct xfs_btree_cur	*cur,
	xfs_agblock_t		bno,
	uint64_t		owner,
	uint64_t		offset,
	unsigned int		flags,
	struct xfs_rmap_irec	*irec,
	int			*stat)
{ … }

/* For each rmap given, figure out if it matches the key we want. */
STATIC int
xfs_rmap_lookup_le_range_helper(
	struct xfs_btree_cur		*cur,
	const struct xfs_rmap_irec	*rec,
	void				*priv)
{ … }

/*
 * Find the record to the left of the given extent, being careful only to
 * return a match with the same owner and overlapping physical and logical
 * block ranges.  This is the overlapping-interval version of
 * xfs_rmap_lookup_le.
 */
int
xfs_rmap_lookup_le_range(
	struct xfs_btree_cur	*cur,
	xfs_agblock_t		bno,
	uint64_t		owner,
	uint64_t		offset,
	unsigned int		flags,
	struct xfs_rmap_irec	*irec,
	int			*stat)
{ … }

/*
 * Perform all the relevant owner checks for a removal op.  If we're doing an
 * unknown-owner removal then we have no owner information to check.
 */
static int
xfs_rmap_free_check_owner(
	struct xfs_btree_cur	*cur,
	uint64_t		ltoff,
	struct xfs_rmap_irec	*rec,
	xfs_filblks_t		len,
	uint64_t		owner,
	uint64_t		offset,
	unsigned int		flags)
{ … }

/*
 * Find the extent in the rmap btree and remove it.
 *
 * The record we find should always be an exact match for the extent that we're
 * looking for, since we insert them into the btree without modification.
 *
 * Special Case #1: when growing the filesystem, we "free" an extent when
 * growing the last AG. This extent is new space and so it is not tracked as
 * used space in the btree. The growfs code will pass in an owner of
 * XFS_RMAP_OWN_NULL to indicate that it expected that there is no owner of this
 * extent. We verify that - the extent lookup result in a record that does not
 * overlap.
 *
 * Special Case #2: EFIs do not record the owner of the extent, so when
 * recovering EFIs from the log we pass in XFS_RMAP_OWN_UNKNOWN to tell the rmap
 * btree to ignore the owner (i.e. wildcard match) so we don't trigger
 * corruption checks during log recovery.
 */
STATIC int
xfs_rmap_unmap(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	bool				unwritten,
	const struct xfs_owner_info	*oinfo)
{ … }

#ifdef CONFIG_XFS_LIVE_HOOKS
/*
 * Use a static key here to reduce the overhead of rmapbt live updates.  If
 * the compiler supports jump labels, the static branch will be replaced by a
 * nop sled when there are no hook users.  Online fsck is currently the only
 * caller, so this is a reasonable tradeoff.
 *
 * Note: Patching the kernel code requires taking the cpu hotplug lock.  Other
 * parts of the kernel allocate memory with that lock held, which means that
 * XFS callers cannot hold any locks that might be used by memory reclaim or
 * writeback when calling the static_branch_{inc,dec} functions.
 */
DEFINE_STATIC_XFS_HOOK_SWITCH(xfs_rmap_hooks_switch);

void
xfs_rmap_hook_disable(void)
{ … }

void
xfs_rmap_hook_enable(void)
{ … }

/* Call downstream hooks for a reverse mapping update. */
static inline void
xfs_rmap_update_hook(
	struct xfs_trans		*tp,
	struct xfs_perag		*pag,
	enum xfs_rmap_intent_type	op,
	xfs_agblock_t			startblock,
	xfs_extlen_t			blockcount,
	bool				unwritten,
	const struct xfs_owner_info	*oinfo)
{ … }

/* Call the specified function during a reverse mapping update. */
int
xfs_rmap_hook_add(
	struct xfs_perag	*pag,
	struct xfs_rmap_hook	*hook)
{ … }

/* Stop calling the specified function during a reverse mapping update. */
void
xfs_rmap_hook_del(
	struct xfs_perag	*pag,
	struct xfs_rmap_hook	*hook)
{ … }

/* Configure rmap update hook functions. */
void
xfs_rmap_hook_setup(
	struct xfs_rmap_hook	*hook,
	notifier_fn_t		mod_fn)
{ … }
#else
#define xfs_rmap_update_hook …
#endif /* CONFIG_XFS_LIVE_HOOKS */

/*
 * Remove a reference to an extent in the rmap btree.
 */
int
xfs_rmap_free(
	struct xfs_trans		*tp,
	struct xfs_buf			*agbp,
	struct xfs_perag		*pag,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	const struct xfs_owner_info	*oinfo)
{ … }

/*
 * A mergeable rmap must have the same owner and the same values for
 * the unwritten, attr_fork, and bmbt flags.  The startblock and
 * offset are checked separately.
 */
static bool
xfs_rmap_is_mergeable(
	struct xfs_rmap_irec	*irec,
	uint64_t		owner,
	unsigned int		flags)
{ … }

/*
 * When we allocate a new block, the first thing we do is add a reference to
 * the extent in the rmap btree. This takes the form of a [agbno, length,
 * owner, offset] record.  Flags are encoded in the high bits of the offset
 * field.
 */
STATIC int
xfs_rmap_map(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	bool				unwritten,
	const struct xfs_owner_info	*oinfo)
{ … }

/*
 * Add a reference to an extent in the rmap btree.
 */
int
xfs_rmap_alloc(
	struct xfs_trans		*tp,
	struct xfs_buf			*agbp,
	struct xfs_perag		*pag,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	const struct xfs_owner_info	*oinfo)
{ … }

#define RMAP_LEFT_CONTIG …
#define RMAP_RIGHT_CONTIG …
#define RMAP_LEFT_FILLING …
#define RMAP_RIGHT_FILLING …
#define RMAP_LEFT_VALID …
#define RMAP_RIGHT_VALID …

#define LEFT …
#define RIGHT …
#define PREV …
#define NEW …

/*
 * Convert an unwritten extent to a real extent or vice versa.
 * Does not handle overlapping extents.
 */
STATIC int
xfs_rmap_convert(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	bool				unwritten,
	const struct xfs_owner_info	*oinfo)
{ … }

/*
 * Convert an unwritten extent to a real extent or vice versa.  If there is no
 * possibility of overlapping extents, delegate to the simpler convert
 * function.
 */
STATIC int
xfs_rmap_convert_shared(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	bool				unwritten,
	const struct xfs_owner_info	*oinfo)
{ … }

#undef	NEW
#undef	LEFT
#undef	RIGHT
#undef	PREV

/*
 * Find an extent in the rmap btree and unmap it.  For rmap extent types that
 * can overlap (data fork rmaps on reflink filesystems) we must be careful
 * that the prev/next records in the btree might belong to another owner.
 * Therefore we must use delete+insert to alter any of the key fields.
 *
 * For every other situation there can only be one owner for a given extent,
 * so we can call the regular _free function.
 */
STATIC int
xfs_rmap_unmap_shared(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	bool				unwritten,
	const struct xfs_owner_info	*oinfo)
{ … }

/*
 * Find an extent in the rmap btree and map it.  For rmap extent types that
 * can overlap (data fork rmaps on reflink filesystems) we must be careful
 * that the prev/next records in the btree might belong to another owner.
 * Therefore we must use delete+insert to alter any of the key fields.
 *
 * For every other situation there can only be one owner for a given extent,
 * so we can call the regular _alloc function.
 */
STATIC int
xfs_rmap_map_shared(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	bool				unwritten,
	const struct xfs_owner_info	*oinfo)
{ … }

/* Insert a raw rmap into the rmapbt. */
int
xfs_rmap_map_raw(
	struct xfs_btree_cur	*cur,
	struct xfs_rmap_irec	*rmap)
{ … }

struct xfs_rmap_query_range_info { … };

/* Format btree record and pass to our callback. */
STATIC int
xfs_rmap_query_range_helper(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_rec	*rec,
	void				*priv)
{ … }

/* Find all rmaps between two keys. */
int
xfs_rmap_query_range(
	struct xfs_btree_cur			*cur,
	const struct xfs_rmap_irec		*low_rec,
	const struct xfs_rmap_irec		*high_rec,
	xfs_rmap_query_range_fn			fn,
	void					*priv)
{ … }

/* Find all rmaps. */
int
xfs_rmap_query_all(
	struct xfs_btree_cur			*cur,
	xfs_rmap_query_range_fn			fn,
	void					*priv)
{ … }

/* Commit an rmap operation into the ondisk tree. */
int
__xfs_rmap_finish_intent(
	struct xfs_btree_cur		*rcur,
	enum xfs_rmap_intent_type	op,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	const struct xfs_owner_info	*oinfo,
	bool				unwritten)
{ … }

/*
 * Process one of the deferred rmap operations.  We pass back the
 * btree cursor to maintain our lock on the rmapbt between calls.
 * This saves time and eliminates a buffer deadlock between the
 * superblock and the AGF because we'll always grab them in the same
 * order.
 */
int
xfs_rmap_finish_one(
	struct xfs_trans		*tp,
	struct xfs_rmap_intent		*ri,
	struct xfs_btree_cur		**pcur)
{ … }

/*
 * Don't defer an rmap if we aren't an rmap filesystem.
 */
static bool
xfs_rmap_update_is_needed(
	struct xfs_mount	*mp,
	int			whichfork)
{ … }

/*
 * Record a rmap intent; the list is kept sorted first by AG and then by
 * increasing age.
 */
static void
__xfs_rmap_add(
	struct xfs_trans		*tp,
	enum xfs_rmap_intent_type	type,
	uint64_t			owner,
	int				whichfork,
	struct xfs_bmbt_irec		*bmap)
{ … }

/* Map an extent into a file. */
void
xfs_rmap_map_extent(
	struct xfs_trans	*tp,
	struct xfs_inode	*ip,
	int			whichfork,
	struct xfs_bmbt_irec	*PREV)
{ … }

/* Unmap an extent out of a file. */
void
xfs_rmap_unmap_extent(
	struct xfs_trans	*tp,
	struct xfs_inode	*ip,
	int			whichfork,
	struct xfs_bmbt_irec	*PREV)
{ … }

/*
 * Convert a data fork extent from unwritten to real or vice versa.
 *
 * Note that tp can be NULL here as no transaction is used for COW fork
 * unwritten conversion.
 */
void
xfs_rmap_convert_extent(
	struct xfs_mount	*mp,
	struct xfs_trans	*tp,
	struct xfs_inode	*ip,
	int			whichfork,
	struct xfs_bmbt_irec	*PREV)
{ … }

/* Schedule the creation of an rmap for non-file data. */
void
xfs_rmap_alloc_extent(
	struct xfs_trans	*tp,
	xfs_agnumber_t		agno,
	xfs_agblock_t		bno,
	xfs_extlen_t		len,
	uint64_t		owner)
{ … }

/* Schedule the deletion of an rmap for non-file data. */
void
xfs_rmap_free_extent(
	struct xfs_trans	*tp,
	xfs_agnumber_t		agno,
	xfs_agblock_t		bno,
	xfs_extlen_t		len,
	uint64_t		owner)
{ … }

/* Compare rmap records.  Returns -1 if a < b, 1 if a > b, and 0 if equal. */
int
xfs_rmap_compare(
	const struct xfs_rmap_irec	*a,
	const struct xfs_rmap_irec	*b)
{ … }

/*
 * Scan the physical storage part of the keyspace of the reverse mapping index
 * and tell us if the area has no records, is fully mapped by records, or is
 * partially filled.
 */
int
xfs_rmap_has_records(
	struct xfs_btree_cur	*cur,
	xfs_agblock_t		bno,
	xfs_extlen_t		len,
	enum xbtree_recpacking	*outcome)
{ … }

struct xfs_rmap_ownercount { … };

/* Does this rmap represent space that can have multiple owners? */
static inline bool
xfs_rmap_shareable(
	struct xfs_mount		*mp,
	const struct xfs_rmap_irec	*rmap)
{ … }

static inline void
xfs_rmap_ownercount_init(
	struct xfs_rmap_ownercount	*roc,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	const struct xfs_owner_info	*oinfo,
	struct xfs_rmap_matches		*results)
{ … }

/* Figure out if this is a match for the owner. */
STATIC int
xfs_rmap_count_owners_helper(
	struct xfs_btree_cur		*cur,
	const struct xfs_rmap_irec	*rec,
	void				*priv)
{ … }

/* Count the number of owners and non-owners of this range of blocks. */
int
xfs_rmap_count_owners(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	const struct xfs_owner_info	*oinfo,
	struct xfs_rmap_matches		*results)
{ … }

/*
 * Given an extent and some owner info, can we find records overlapping
 * the extent whose owner info does not match the given owner?
 */
int
xfs_rmap_has_other_keys(
	struct xfs_btree_cur		*cur,
	xfs_agblock_t			bno,
	xfs_extlen_t			len,
	const struct xfs_owner_info	*oinfo,
	bool				*has_other)
{ … }

const struct xfs_owner_info XFS_RMAP_OINFO_SKIP_UPDATE = …;
const struct xfs_owner_info XFS_RMAP_OINFO_ANY_OWNER = …;
const struct xfs_owner_info XFS_RMAP_OINFO_FS = …;
const struct xfs_owner_info XFS_RMAP_OINFO_LOG = …;
const struct xfs_owner_info XFS_RMAP_OINFO_AG = …;
const struct xfs_owner_info XFS_RMAP_OINFO_INOBT = …;
const struct xfs_owner_info XFS_RMAP_OINFO_INODES = …;
const struct xfs_owner_info XFS_RMAP_OINFO_REFC = …;
const struct xfs_owner_info XFS_RMAP_OINFO_COW = …;

int __init
xfs_rmap_intent_init_cache(void)
{ … }

void
xfs_rmap_intent_destroy_cache(void)
{ … }