fs/xfs/libxfs/xfs_iext_tree.c

Source file repositories/reference/linux-study-clean/fs/xfs/libxfs/xfs_iext_tree.c

File Facts

System
Linux kernel
Corpus path
fs/xfs/libxfs/xfs_iext_tree.c
Extension
.c
Size
23886 bytes
Lines
1068
Domain
Core OS
Bucket
VFS And Filesystem Core
Inferred role
Core OS: implementation source
Status
source implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

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];
};

Annotation

Implementation Notes