// 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_inode.h"
#include "xfs_trans_resv.h"
#include "xfs_mount.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;