xfs_iext_tree.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2017 Christoph Hellwig.
 */

#include "xfs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_bit.h"
#include "xfs_log_format.h"
#include "xfs_trans_resv.h"
#include "xfs_mount.h"
#include "xfs_inode.h"
#include "xfs_trace.h"

/*
 * In-core extent record layout:
 *
 * +-------+----------------------------+
 * | 00:53 | all 54 bits of startoff    |
 * | 54:63 | low 10 bits of startblock  |
 * +-------+----------------------------+
 * | 00:20 | all 21 bits of length      |
 * |    21 | unwritten extent bit       |
 * | 22:63 | high 42 bits of startblock |
 * +-------+----------------------------+
 */
#define XFS_IEXT_STARTOFF_MASK …
#define XFS_IEXT_LENGTH_MASK …
#define XFS_IEXT_STARTBLOCK_MASK …

struct xfs_iext_rec { … };

/*
 * Given that the length can't be a zero, only an empty hi value indicates an
 * unused record.
 */
static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec)
{ … }

static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec)
{ … }

static void
xfs_iext_set(
	struct xfs_iext_rec	*rec,
	struct xfs_bmbt_irec	*irec)
{ … }

static void
xfs_iext_get(
	struct xfs_bmbt_irec	*irec,
	struct xfs_iext_rec	*rec)
{ … }

enum { … };

/*
 * In-core extent btree block layout:
 *
 * There are two types of blocks in the btree: leaf and inner (non-leaf) blocks.
 *
 * The leaf blocks are made up by %KEYS_PER_NODE extent records, which each
 * contain the startoffset, blockcount, startblock and unwritten extent flag.
 * See above for the exact format, followed by pointers to the previous and next
 * leaf blocks (if there are any).
 *
 * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed
 * by an equal number of pointers to the btree blocks at the next lower level.
 *
 *		+-------+-------+-------+-------+-------+----------+----------+
 * Leaf:	| rec 1 | rec 2 | rec 3 | rec 4 | rec N | prev-ptr | next-ptr |
 *		+-------+-------+-------+-------+-------+----------+----------+
 *
 *		+-------+-------+-------+-------+-------+-------+------+-------+
 * Inner:	| key 1 | key 2 | key 3 | key N | ptr 1 | ptr 2 | ptr3 | ptr N |
 *		+-------+-------+-------+-------+-------+-------+------+-------+
 */
struct xfs_iext_node { … };

struct xfs_iext_leaf { … };

inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp)
{ … }

static inline int xfs_iext_max_recs(struct xfs_ifork *ifp)
{ … }

static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur)
{ … }

static inline bool xfs_iext_valid(struct xfs_ifork *ifp,
		struct xfs_iext_cursor *cur)
{ … }

static void *
xfs_iext_find_first_leaf(
	struct xfs_ifork	*ifp)
{ … }

static void *
xfs_iext_find_last_leaf(
	struct xfs_ifork	*ifp)
{ … }

void
xfs_iext_first(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur)
{ … }

void
xfs_iext_last(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur)
{ … }

void
xfs_iext_next(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur)
{ … }

void
xfs_iext_prev(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur)
{ … }

static inline int
xfs_iext_key_cmp(
	struct xfs_iext_node	*node,
	int			n,
	xfs_fileoff_t		offset)
{ … }

static inline int
xfs_iext_rec_cmp(
	struct xfs_iext_rec	*rec,
	xfs_fileoff_t		offset)
{ … }

static void *
xfs_iext_find_level(
	struct xfs_ifork	*ifp,
	xfs_fileoff_t		offset,
	int			level)
{ … }

static int
xfs_iext_node_pos(
	struct xfs_iext_node	*node,
	xfs_fileoff_t		offset)
{ … }

static int
xfs_iext_node_insert_pos(
	struct xfs_iext_node	*node,
	xfs_fileoff_t		offset)
{ … }

static int
xfs_iext_node_nr_entries(
	struct xfs_iext_node	*node,
	int			start)
{ … }

static int
xfs_iext_leaf_nr_entries(
	struct xfs_ifork	*ifp,
	struct xfs_iext_leaf	*leaf,
	int			start)
{ … }

static inline uint64_t
xfs_iext_leaf_key(
	struct xfs_iext_leaf	*leaf,
	int			n)
{ … }

static inline void *
xfs_iext_alloc_node(
	int	size)
{ … }

static void
xfs_iext_grow(
	struct xfs_ifork	*ifp)
{ … }

static void
xfs_iext_update_node(
	struct xfs_ifork	*ifp,
	xfs_fileoff_t		old_offset,
	xfs_fileoff_t		new_offset,
	int			level,
	void			*ptr)
{ … }

static struct xfs_iext_node *
xfs_iext_split_node(
	struct xfs_iext_node	**nodep,
	int			*pos,
	int			*nr_entries)
{ … }

static void
xfs_iext_insert_node(
	struct xfs_ifork	*ifp,
	uint64_t		offset,
	void			*ptr,
	int			level)
{ … }

static struct xfs_iext_leaf *
xfs_iext_split_leaf(
	struct xfs_iext_cursor	*cur,
	int			*nr_entries)
{ … }

static void
xfs_iext_alloc_root(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur)
{ … }

static void
xfs_iext_realloc_root(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur)
{ … }

/*
 * Increment the sequence counter on extent tree changes. If we are on a COW
 * fork, this allows the writeback code to skip looking for a COW extent if the
 * COW fork hasn't changed. We use WRITE_ONCE here to ensure the update to the
 * sequence counter is seen before the modifications to the extent tree itself
 * take effect.
 */
static inline void xfs_iext_inc_seq(struct xfs_ifork *ifp)
{ … }

void
xfs_iext_insert_raw(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur,
	struct xfs_bmbt_irec	*irec)
{ … }

void
xfs_iext_insert(
	struct xfs_inode	*ip,
	struct xfs_iext_cursor	*cur,
	struct xfs_bmbt_irec	*irec,
	int			state)
{ … }

static struct xfs_iext_node *
xfs_iext_rebalance_node(
	struct xfs_iext_node	*parent,
	int			*pos,
	struct xfs_iext_node	*node,
	int			nr_entries)
{ … }

static void
xfs_iext_remove_node(
	struct xfs_ifork	*ifp,
	xfs_fileoff_t		offset,
	void			*victim)
{ … }

static void
xfs_iext_rebalance_leaf(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur,
	struct xfs_iext_leaf	*leaf,
	xfs_fileoff_t		offset,
	int			nr_entries)
{ … }

static void
xfs_iext_free_last_leaf(
	struct xfs_ifork	*ifp)
{ … }

void
xfs_iext_remove(
	struct xfs_inode	*ip,
	struct xfs_iext_cursor	*cur,
	int			state)
{ … }

/*
 * Lookup the extent covering bno.
 *
 * If there is an extent covering bno return the extent index, and store the
 * expanded extent structure in *gotp, and the extent cursor in *cur.
 * If there is no extent covering bno, but there is an extent after it (e.g.
 * it lies in a hole) return that extent in *gotp and its cursor in *cur
 * instead.
 * If bno is beyond the last extent return false, and return an invalid
 * cursor value.
 */
bool
xfs_iext_lookup_extent(
	struct xfs_inode	*ip,
	struct xfs_ifork	*ifp,
	xfs_fileoff_t		offset,
	struct xfs_iext_cursor	*cur,
	struct xfs_bmbt_irec	*gotp)
{ … }

/*
 * Returns the last extent before end, and if this extent doesn't cover
 * end, update end to the end of the extent.
 */
bool
xfs_iext_lookup_extent_before(
	struct xfs_inode	*ip,
	struct xfs_ifork	*ifp,
	xfs_fileoff_t		*end,
	struct xfs_iext_cursor	*cur,
	struct xfs_bmbt_irec	*gotp)
{ … }

void
xfs_iext_update_extent(
	struct xfs_inode	*ip,
	int			state,
	struct xfs_iext_cursor	*cur,
	struct xfs_bmbt_irec	*new)
{ … }

/*
 * Return true if the cursor points at an extent and return the extent structure
 * in gotp.  Else return false.
 */
bool
xfs_iext_get_extent(
	struct xfs_ifork	*ifp,
	struct xfs_iext_cursor	*cur,
	struct xfs_bmbt_irec	*gotp)
{ … }

/*
 * This is a recursive function, because of that we need to be extremely
 * careful with stack usage.
 */
static void
xfs_iext_destroy_node(
	struct xfs_iext_node	*node,
	int			level)
{ … }

void
xfs_iext_destroy(
	struct xfs_ifork	*ifp)
{ … }
linux/fs/xfs/libxfs/xfs_iext_tree.c
