xfs_ialloc.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2002,2005 Silicon Graphics, 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_inode.h"
#include "xfs_btree.h"
#include "xfs_ialloc.h"
#include "xfs_ialloc_btree.h"
#include "xfs_alloc.h"
#include "xfs_errortag.h"
#include "xfs_error.h"
#include "xfs_bmap.h"
#include "xfs_trans.h"
#include "xfs_buf_item.h"
#include "xfs_icreate_item.h"
#include "xfs_icache.h"
#include "xfs_trace.h"
#include "xfs_log.h"
#include "xfs_rmap.h"
#include "xfs_ag.h"
#include "xfs_health.h"

/*
 * Lookup a record by ino in the btree given by cur.
 */
int					/* error */
xfs_inobt_lookup(
	struct xfs_btree_cur	*cur,	/* btree cursor */
	xfs_agino_t		ino,	/* starting inode of chunk */
	xfs_lookup_t		dir,	/* <=, >=, == */
	int			*stat)	/* success/failure */
{ … }

/*
 * Update the record referred to by cur to the value given.
 * This either works (return 0) or gets an EFSCORRUPTED error.
 */
STATIC int				/* error */
xfs_inobt_update(
	struct xfs_btree_cur	*cur,	/* btree cursor */
	xfs_inobt_rec_incore_t	*irec)	/* btree record */
{ … }

/* Convert on-disk btree record to incore inobt record. */
void
xfs_inobt_btrec_to_irec(
	struct xfs_mount		*mp,
	const union xfs_btree_rec	*rec,
	struct xfs_inobt_rec_incore	*irec)
{ … }

/* Compute the freecount of an incore inode record. */
uint8_t
xfs_inobt_rec_freecount(
	const struct xfs_inobt_rec_incore	*irec)
{ … }

/* Simple checks for inode records. */
xfs_failaddr_t
xfs_inobt_check_irec(
	struct xfs_perag			*pag,
	const struct xfs_inobt_rec_incore	*irec)
{ … }

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

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

/*
 * Insert a single inobt record. Cursor must already point to desired location.
 */
int
xfs_inobt_insert_rec(
	struct xfs_btree_cur	*cur,
	uint16_t		holemask,
	uint8_t			count,
	int32_t			freecount,
	xfs_inofree_t		free,
	int			*stat)
{ … }

/*
 * Insert records describing a newly allocated inode chunk into the inobt.
 */
STATIC int
xfs_inobt_insert(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	struct xfs_buf		*agbp,
	xfs_agino_t		newino,
	xfs_agino_t		newlen,
	bool			is_finobt)
{ … }

/*
 * Verify that the number of free inodes in the AGI is correct.
 */
#ifdef DEBUG
static int
xfs_check_agi_freecount(
	struct xfs_btree_cur	*cur)
{ … }
#else
#define xfs_check_agi_freecount …
#endif

/*
 * Initialise a new set of inodes. When called without a transaction context
 * (e.g. from recovery) we initiate a delayed write of the inode buffers rather
 * than logging them (which in a transaction context puts them into the AIL
 * for writeback rather than the xfsbufd queue).
 */
int
xfs_ialloc_inode_init(
	struct xfs_mount	*mp,
	struct xfs_trans	*tp,
	struct list_head	*buffer_list,
	int			icount,
	xfs_agnumber_t		agno,
	xfs_agblock_t		agbno,
	xfs_agblock_t		length,
	unsigned int		gen)
{ … }

/*
 * Align startino and allocmask for a recently allocated sparse chunk such that
 * they are fit for insertion (or merge) into the on-disk inode btrees.
 *
 * Background:
 *
 * When enabled, sparse inode support increases the inode alignment from cluster
 * size to inode chunk size. This means that the minimum range between two
 * non-adjacent inode records in the inobt is large enough for a full inode
 * record. This allows for cluster sized, cluster aligned block allocation
 * without need to worry about whether the resulting inode record overlaps with
 * another record in the tree. Without this basic rule, we would have to deal
 * with the consequences of overlap by potentially undoing recent allocations in
 * the inode allocation codepath.
 *
 * Because of this alignment rule (which is enforced on mount), there are two
 * inobt possibilities for newly allocated sparse chunks. One is that the
 * aligned inode record for the chunk covers a range of inodes not already
 * covered in the inobt (i.e., it is safe to insert a new sparse record). The
 * other is that a record already exists at the aligned startino that considers
 * the newly allocated range as sparse. In the latter case, record content is
 * merged in hope that sparse inode chunks fill to full chunks over time.
 */
STATIC void
xfs_align_sparse_ino(
	struct xfs_mount		*mp,
	xfs_agino_t			*startino,
	uint16_t			*allocmask)
{ … }

/*
 * Determine whether the source inode record can merge into the target. Both
 * records must be sparse, the inode ranges must match and there must be no
 * allocation overlap between the records.
 */
STATIC bool
__xfs_inobt_can_merge(
	struct xfs_inobt_rec_incore	*trec,	/* tgt record */
	struct xfs_inobt_rec_incore	*srec)	/* src record */
{ … }

/*
 * Merge the source inode record into the target. The caller must call
 * __xfs_inobt_can_merge() to ensure the merge is valid.
 */
STATIC void
__xfs_inobt_rec_merge(
	struct xfs_inobt_rec_incore	*trec,	/* target */
	struct xfs_inobt_rec_incore	*srec)	/* src */
{ … }

/*
 * Insert a new sparse inode chunk into the associated inode allocation btree.
 * The inode record for the sparse chunk is pre-aligned to a startino that
 * should match any pre-existing sparse inode record in the tree. This allows
 * sparse chunks to fill over time.
 *
 * If no preexisting record exists, the provided record is inserted.
 * If there is a preexisting record, the provided record is merged with the
 * existing record and updated in place. The merged record is returned in nrec.
 *
 * It is considered corruption if a merge is requested and not possible. Given
 * the sparse inode alignment constraints, this should never happen.
 */
STATIC int
xfs_inobt_insert_sprec(
	struct xfs_perag		*pag,
	struct xfs_trans		*tp,
	struct xfs_buf			*agbp,
	struct xfs_inobt_rec_incore	*nrec)	/* in/out: new/merged rec. */
{ … }

/*
 * Insert a new sparse inode chunk into the free inode btree. The inode
 * record for the sparse chunk is pre-aligned to a startino that should match
 * any pre-existing sparse inode record in the tree. This allows sparse chunks
 * to fill over time.
 *
 * The new record is always inserted, overwriting a pre-existing record if
 * there is one.
 */
STATIC int
xfs_finobt_insert_sprec(
	struct xfs_perag		*pag,
	struct xfs_trans		*tp,
	struct xfs_buf			*agbp,
	struct xfs_inobt_rec_incore	*nrec)	/* in/out: new rec. */
{ … }


/*
 * Allocate new inodes in the allocation group specified by agbp.  Returns 0 if
 * inodes were allocated in this AG; -EAGAIN if there was no space in this AG so
 * the caller knows it can try another AG, a hard -ENOSPC when over the maximum
 * inode count threshold, or the usual negative error code for other errors.
 */
STATIC int
xfs_ialloc_ag_alloc(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	struct xfs_buf		*agbp)
{ … }

/*
 * Try to retrieve the next record to the left/right from the current one.
 */
STATIC int
xfs_ialloc_next_rec(
	struct xfs_btree_cur	*cur,
	xfs_inobt_rec_incore_t	*rec,
	int			*done,
	int			left)
{ … }

STATIC int
xfs_ialloc_get_rec(
	struct xfs_btree_cur	*cur,
	xfs_agino_t		agino,
	xfs_inobt_rec_incore_t	*rec,
	int			*done)
{ … }

/*
 * Return the offset of the first free inode in the record. If the inode chunk
 * is sparsely allocated, we convert the record holemask to inode granularity
 * and mask off the unallocated regions from the inode free mask.
 */
STATIC int
xfs_inobt_first_free_inode(
	struct xfs_inobt_rec_incore	*rec)
{ … }

/*
 * If this AG has corrupt inodes, check if allocating this inode would fail
 * with corruption errors.  Returns 0 if we're clear, or EAGAIN to try again
 * somewhere else.
 */
static int
xfs_dialloc_check_ino(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	xfs_ino_t		ino)
{ … }

/*
 * Allocate an inode using the inobt-only algorithm.
 */
STATIC int
xfs_dialloc_ag_inobt(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	struct xfs_buf		*agbp,
	xfs_ino_t		parent,
	xfs_ino_t		*inop)
{ … }

/*
 * Use the free inode btree to allocate an inode based on distance from the
 * parent. Note that the provided cursor may be deleted and replaced.
 */
STATIC int
xfs_dialloc_ag_finobt_near(
	xfs_agino_t			pagino,
	struct xfs_btree_cur		**ocur,
	struct xfs_inobt_rec_incore	*rec)
{ … }

/*
 * Use the free inode btree to find a free inode based on a newino hint. If
 * the hint is NULL, find the first free inode in the AG.
 */
STATIC int
xfs_dialloc_ag_finobt_newino(
	struct xfs_agi			*agi,
	struct xfs_btree_cur		*cur,
	struct xfs_inobt_rec_incore	*rec)
{ … }

/*
 * Update the inobt based on a modification made to the finobt. Also ensure that
 * the records from both trees are equivalent post-modification.
 */
STATIC int
xfs_dialloc_ag_update_inobt(
	struct xfs_btree_cur		*cur,	/* inobt cursor */
	struct xfs_inobt_rec_incore	*frec,	/* finobt record */
	int				offset) /* inode offset */
{ … }

/*
 * Allocate an inode using the free inode btree, if available. Otherwise, fall
 * back to the inobt search algorithm.
 *
 * The caller selected an AG for us, and made sure that free inodes are
 * available.
 */
static int
xfs_dialloc_ag(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	struct xfs_buf		*agbp,
	xfs_ino_t		parent,
	xfs_ino_t		*inop)
{ … }

static int
xfs_dialloc_roll(
	struct xfs_trans	**tpp,
	struct xfs_buf		*agibp)
{ … }

static bool
xfs_dialloc_good_ag(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	umode_t			mode,
	int			flags,
	bool			ok_alloc)
{ … }

static int
xfs_dialloc_try_ag(
	struct xfs_perag	*pag,
	struct xfs_trans	**tpp,
	xfs_ino_t		parent,
	xfs_ino_t		*new_ino,
	bool			ok_alloc)
{ … }

/*
 * Allocate an on-disk inode.
 *
 * Mode is used to tell whether the new inode is a directory and hence where to
 * locate it. The on-disk inode that is allocated will be returned in @new_ino
 * on success, otherwise an error will be set to indicate the failure (e.g.
 * -ENOSPC).
 */
int
xfs_dialloc(
	struct xfs_trans	**tpp,
	xfs_ino_t		parent,
	umode_t			mode,
	xfs_ino_t		*new_ino)
{ … }

/*
 * Free the blocks of an inode chunk. We must consider that the inode chunk
 * might be sparse and only free the regions that are allocated as part of the
 * chunk.
 */
static int
xfs_difree_inode_chunk(
	struct xfs_trans		*tp,
	xfs_agnumber_t			agno,
	struct xfs_inobt_rec_incore	*rec)
{ … }

STATIC int
xfs_difree_inobt(
	struct xfs_perag		*pag,
	struct xfs_trans		*tp,
	struct xfs_buf			*agbp,
	xfs_agino_t			agino,
	struct xfs_icluster		*xic,
	struct xfs_inobt_rec_incore	*orec)
{ … }

/*
 * Free an inode in the free inode btree.
 */
STATIC int
xfs_difree_finobt(
	struct xfs_perag		*pag,
	struct xfs_trans		*tp,
	struct xfs_buf			*agbp,
	xfs_agino_t			agino,
	struct xfs_inobt_rec_incore	*ibtrec) /* inobt record */
{ … }

/*
 * Free disk inode.  Carefully avoids touching the incore inode, all
 * manipulations incore are the caller's responsibility.
 * The on-disk inode is not changed by this operation, only the
 * btree (free inode mask) is changed.
 */
int
xfs_difree(
	struct xfs_trans	*tp,
	struct xfs_perag	*pag,
	xfs_ino_t		inode,
	struct xfs_icluster	*xic)
{ … }

STATIC int
xfs_imap_lookup(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	xfs_agino_t		agino,
	xfs_agblock_t		agbno,
	xfs_agblock_t		*chunk_agbno,
	xfs_agblock_t		*offset_agbno,
	int			flags)
{ … }

/*
 * Return the location of the inode in imap, for mapping it into a buffer.
 */
int
xfs_imap(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	xfs_ino_t		ino,	/* inode to locate */
	struct xfs_imap		*imap,	/* location map structure */
	uint			flags)	/* flags for inode btree lookup */
{ … }

/*
 * Log specified fields for the ag hdr (inode section). The growth of the agi
 * structure over time requires that we interpret the buffer as two logical
 * regions delineated by the end of the unlinked list. This is due to the size
 * of the hash table and its location in the middle of the agi.
 *
 * For example, a request to log a field before agi_unlinked and a field after
 * agi_unlinked could cause us to log the entire hash table and use an excessive
 * amount of log space. To avoid this behavior, log the region up through
 * agi_unlinked in one call and the region after agi_unlinked through the end of
 * the structure in another.
 */
void
xfs_ialloc_log_agi(
	struct xfs_trans	*tp,
	struct xfs_buf		*bp,
	uint32_t		fields)
{ … }

static xfs_failaddr_t
xfs_agi_verify(
	struct xfs_buf		*bp)
{ … }

static void
xfs_agi_read_verify(
	struct xfs_buf	*bp)
{ … }

static void
xfs_agi_write_verify(
	struct xfs_buf	*bp)
{ … }

const struct xfs_buf_ops xfs_agi_buf_ops = …;

/*
 * Read in the allocation group header (inode allocation section)
 */
int
xfs_read_agi(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	xfs_buf_flags_t		flags,
	struct xfs_buf		**agibpp)
{ … }

/*
 * Read in the agi and initialise the per-ag data. If the caller supplies a
 * @agibpp, return the locked AGI buffer to them, otherwise release it.
 */
int
xfs_ialloc_read_agi(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	int			flags,
	struct xfs_buf		**agibpp)
{ … }

/* How many inodes are backed by inode clusters ondisk? */
STATIC int
xfs_ialloc_count_ondisk(
	struct xfs_btree_cur		*cur,
	xfs_agino_t			low,
	xfs_agino_t			high,
	unsigned int			*allocated)
{ … }

/* Is there an inode record covering a given extent? */
int
xfs_ialloc_has_inodes_at_extent(
	struct xfs_btree_cur	*cur,
	xfs_agblock_t		bno,
	xfs_extlen_t		len,
	enum xbtree_recpacking	*outcome)
{ … }

struct xfs_ialloc_count_inodes { … };

/* Record inode counts across all inobt records. */
STATIC int
xfs_ialloc_count_inodes_rec(
	struct xfs_btree_cur		*cur,
	const union xfs_btree_rec	*rec,
	void				*priv)
{ … }

/* Count allocated and free inodes under an inobt. */
int
xfs_ialloc_count_inodes(
	struct xfs_btree_cur		*cur,
	xfs_agino_t			*count,
	xfs_agino_t			*freecount)
{ … }

/*
 * Initialize inode-related geometry information.
 *
 * Compute the inode btree min and max levels and set maxicount.
 *
 * Set the inode cluster size.  This may still be overridden by the file
 * system block size if it is larger than the chosen cluster size.
 *
 * For v5 filesystems, scale the cluster size with the inode size to keep a
 * constant ratio of inode per cluster buffer, but only if mkfs has set the
 * inode alignment value appropriately for larger cluster sizes.
 *
 * Then compute the inode cluster alignment information.
 */
void
xfs_ialloc_setup_geometry(
	struct xfs_mount	*mp)
{ … }

/* Compute the location of the root directory inode that is laid out by mkfs. */
xfs_ino_t
xfs_ialloc_calc_rootino(
	struct xfs_mount	*mp,
	int			sunit)
{ … }

/*
 * Ensure there are not sparse inode clusters that cross the new EOAG.
 *
 * This is a no-op for non-spinode filesystems since clusters are always fully
 * allocated and checking the bnobt suffices.  However, a spinode filesystem
 * could have a record where the upper inodes are free blocks.  If those blocks
 * were removed from the filesystem, the inode record would extend beyond EOAG,
 * which will be flagged as corruption.
 */
int
xfs_ialloc_check_shrink(
	struct xfs_perag	*pag,
	struct xfs_trans	*tp,
	struct xfs_buf		*agibp,
	xfs_agblock_t		new_length)
{ … }
linux/fs/xfs/libxfs/xfs_ialloc.c
