path: root/fs/xfs/libxfs/xfs_iext_tree.c

// 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		xfs_mask64lo(BMBT_STARTOFF_BITLEN)
#define XFS_IEXT_LENGTH_MASK		xfs_mask64lo(BMBT_BLOCKCOUNT_BITLEN)
#define XFS_IEXT_STARTBLOCK_MASK	xfs_mask64lo(BMBT_STARTBLOCK_BITLEN)

struct xfs_iext_rec {
	uint64_t			lo;
	uint64_t			hi;
};

/*
 * 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)
{
	return rec->hi == 0;
}

static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec)
{
	rec->lo = 0;
	rec->hi = 0;
}

static void
xfs_iext_set(
	struct xfs_iext_rec	*rec,
	struct xfs_bmbt_irec	*irec)
{
	ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0);
	ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0);
	ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0);

	rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK;
	rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK;

	rec->lo |= (irec->br_startblock << 54);
	rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10));

	if (irec->br_state == XFS_EXT_UNWRITTEN)
		rec->hi |= (1 << 21);
}

static void
xfs_iext_get(
	struct xfs_bmbt_irec	*irec,
	struct xfs_iext_rec	*rec)
{
	irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK;
	irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK;

	irec->br_startblock = rec->lo >> 54;
	irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10);

	if (rec->hi & (1 << 21))
		irec->br_state = XFS_EXT_UNWRITTEN;
	else
		irec->br_state = XFS_EXT_NORM;
}

enum {
	NODE_SIZE	= 256,
	KEYS_PER_NODE	= NODE_SIZE / (sizeof(uint64_t) + sizeof(void *)),
	RECS_PER_LEAF	= (NODE_SIZE - (2 * sizeof(struct xfs_iext_leaf *))) /
				sizeof(struct xfs_iext_rec),
};

/*
 * 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 {
	uint64_t		keys[KEYS_PER_NODE];
#define XFS_IEXT_KEY_INVALID	(1ULL << 63)
	void			*ptrs[KEYS_PER_NODE];
};

struct xfs_iext_leaf {
	struct xfs_iext_rec	recs[RECS_PER_LEAF];
	struct xfs_iext_leaf	*prev;
	struct xfs_iext_leaf	*next;
};

inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp)
{
	return ifp->if_bytes / sizeof(struct xfs_iext_rec);
}

static inline int xfs_iext_max_recs(struct xfs_ifork *ifp)
{
	if (ifp->if_height == 1)
		return xfs_iext_count(ifp);
	return RECS_PER_LEAF;
}

static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur)
{
	return &cur->leaf->recs[cur->pos];
}

static inline bool xfs_iext_valid(struct xfs_ifork *ifp,
		struct xfs_iext_cursor *cur)
{
	if (!cur->leaf)
		return false;
	if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp))
		return false;
	if (xfs_iext_rec_is_empty(cur_rec(cur)))
		return false;
	return true;
}

static void *
xfs_iext_find_first_leaf(
	struct xfs_ifork	*ifp)
{
	struct xfs_iext_node	*node = ifp->if_data;
	int			height;

	if (!ifp->if_height)
		return NULL;

	for (height = ifp->if_height; height > 1; height--) {
		node = node->ptrs[0];
		ASSERT(node);
	}

	return node;
}

static void *
xfs_iext_find_last_leaf(
	struct xfs_ifork	*ifp)
{
	struct xfs_iext_node	*node = ifp->if_data;
	int			height, i;

	if (!ifp->if_height)
		return NULL;

	for (height = ifp->if_height; height > 1; height--