10b61f8a4SDave Chinner // SPDX-License-Identifier: GPL-2.0
26bdcf26aSChristoph Hellwig /*
36bdcf26aSChristoph Hellwig * Copyright (c) 2017 Christoph Hellwig.
46bdcf26aSChristoph Hellwig */
56bdcf26aSChristoph Hellwig
66bdcf26aSChristoph Hellwig #include "xfs.h"
75467b34bSDarrick J. Wong #include "xfs_shared.h"
86bdcf26aSChristoph Hellwig #include "xfs_format.h"
96bdcf26aSChristoph Hellwig #include "xfs_bit.h"
106bdcf26aSChristoph Hellwig #include "xfs_log_format.h"
116bdcf26aSChristoph Hellwig #include "xfs_trans_resv.h"
126bdcf26aSChristoph Hellwig #include "xfs_mount.h"
13*383e32b0SDarrick J. Wong #include "xfs_inode.h"
146bdcf26aSChristoph Hellwig #include "xfs_trace.h"
156bdcf26aSChristoph Hellwig
166bdcf26aSChristoph Hellwig /*
176bdcf26aSChristoph Hellwig * In-core extent record layout:
186bdcf26aSChristoph Hellwig *
196bdcf26aSChristoph Hellwig * +-------+----------------------------+
206bdcf26aSChristoph Hellwig * | 00:53 | all 54 bits of startoff |
216bdcf26aSChristoph Hellwig * | 54:63 | low 10 bits of startblock |
226bdcf26aSChristoph Hellwig * +-------+----------------------------+
236bdcf26aSChristoph Hellwig * | 00:20 | all 21 bits of length |
246bdcf26aSChristoph Hellwig * | 21 | unwritten extent bit |
256bdcf26aSChristoph Hellwig * | 22:63 | high 42 bits of startblock |
266bdcf26aSChristoph Hellwig * +-------+----------------------------+
276bdcf26aSChristoph Hellwig */
286bdcf26aSChristoph Hellwig #define XFS_IEXT_STARTOFF_MASK xfs_mask64lo(BMBT_STARTOFF_BITLEN)
296bdcf26aSChristoph Hellwig #define XFS_IEXT_LENGTH_MASK xfs_mask64lo(BMBT_BLOCKCOUNT_BITLEN)
306bdcf26aSChristoph Hellwig #define XFS_IEXT_STARTBLOCK_MASK xfs_mask64lo(BMBT_STARTBLOCK_BITLEN)
316bdcf26aSChristoph Hellwig
326bdcf26aSChristoph Hellwig struct xfs_iext_rec {
336bdcf26aSChristoph Hellwig uint64_t lo;
346bdcf26aSChristoph Hellwig uint64_t hi;
356bdcf26aSChristoph Hellwig };
366bdcf26aSChristoph Hellwig
376bdcf26aSChristoph Hellwig /*
386bdcf26aSChristoph Hellwig * Given that the length can't be a zero, only an empty hi value indicates an
396bdcf26aSChristoph Hellwig * unused record.
406bdcf26aSChristoph Hellwig */
xfs_iext_rec_is_empty(struct xfs_iext_rec * rec)416bdcf26aSChristoph Hellwig static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec)
426bdcf26aSChristoph Hellwig {
436bdcf26aSChristoph Hellwig return rec->hi == 0;
446bdcf26aSChristoph Hellwig }
456bdcf26aSChristoph Hellwig
xfs_iext_rec_clear(struct xfs_iext_rec * rec)466bdcf26aSChristoph Hellwig static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec)
476bdcf26aSChristoph Hellwig {
486bdcf26aSChristoph Hellwig rec->lo = 0;
496bdcf26aSChristoph Hellwig rec->hi = 0;
506bdcf26aSChristoph Hellwig }
516bdcf26aSChristoph Hellwig
526bdcf26aSChristoph Hellwig static void
xfs_iext_set(struct xfs_iext_rec * rec,struct xfs_bmbt_irec * irec)536bdcf26aSChristoph Hellwig xfs_iext_set(
546bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec,
556bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *irec)
566bdcf26aSChristoph Hellwig {
576bdcf26aSChristoph Hellwig ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0);
586bdcf26aSChristoph Hellwig ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0);
596bdcf26aSChristoph Hellwig ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0);
606bdcf26aSChristoph Hellwig
616bdcf26aSChristoph Hellwig rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK;
626bdcf26aSChristoph Hellwig rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK;
636bdcf26aSChristoph Hellwig
646bdcf26aSChristoph Hellwig rec->lo |= (irec->br_startblock << 54);
656bdcf26aSChristoph Hellwig rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10));
666bdcf26aSChristoph Hellwig
676bdcf26aSChristoph Hellwig if (irec->br_state == XFS_EXT_UNWRITTEN)
686bdcf26aSChristoph Hellwig rec->hi |= (1 << 21);
696bdcf26aSChristoph Hellwig }
706bdcf26aSChristoph Hellwig
716bdcf26aSChristoph Hellwig static void
xfs_iext_get(struct xfs_bmbt_irec * irec,struct xfs_iext_rec * rec)726bdcf26aSChristoph Hellwig xfs_iext_get(
736bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *irec,
746bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec)
756bdcf26aSChristoph Hellwig {
766bdcf26aSChristoph Hellwig irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK;
776bdcf26aSChristoph Hellwig irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK;
786bdcf26aSChristoph Hellwig
796bdcf26aSChristoph Hellwig irec->br_startblock = rec->lo >> 54;
806bdcf26aSChristoph Hellwig irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10);
816bdcf26aSChristoph Hellwig
826bdcf26aSChristoph Hellwig if (rec->hi & (1 << 21))
836bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_UNWRITTEN;
846bdcf26aSChristoph Hellwig else
856bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_NORM;
866bdcf26aSChristoph Hellwig }
876bdcf26aSChristoph Hellwig
886bdcf26aSChristoph Hellwig enum {
896bdcf26aSChristoph Hellwig NODE_SIZE = 256,
906bdcf26aSChristoph Hellwig KEYS_PER_NODE = NODE_SIZE / (sizeof(uint64_t) + sizeof(void *)),
916bdcf26aSChristoph Hellwig RECS_PER_LEAF = (NODE_SIZE - (2 * sizeof(struct xfs_iext_leaf *))) /
926bdcf26aSChristoph Hellwig sizeof(struct xfs_iext_rec),
936bdcf26aSChristoph Hellwig };
946bdcf26aSChristoph Hellwig
956bdcf26aSChristoph Hellwig /*
966bdcf26aSChristoph Hellwig * In-core extent btree block layout:
976bdcf26aSChristoph Hellwig *
986bdcf26aSChristoph Hellwig * There are two types of blocks in the btree: leaf and inner (non-leaf) blocks.
996bdcf26aSChristoph Hellwig *
1006bdcf26aSChristoph Hellwig * The leaf blocks are made up by %KEYS_PER_NODE extent records, which each
1016bdcf26aSChristoph Hellwig * contain the startoffset, blockcount, startblock and unwritten extent flag.
1026bdcf26aSChristoph Hellwig * See above for the exact format, followed by pointers to the previous and next
1036bdcf26aSChristoph Hellwig * leaf blocks (if there are any).
1046bdcf26aSChristoph Hellwig *
1056bdcf26aSChristoph Hellwig * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed
1066bdcf26aSChristoph Hellwig * by an equal number of pointers to the btree blocks at the next lower level.
1076bdcf26aSChristoph Hellwig *
1086bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+----------+----------+
1096bdcf26aSChristoph Hellwig * Leaf: | rec 1 | rec 2 | rec 3 | rec 4 | rec N | prev-ptr | next-ptr |
1106bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+----------+----------+
1116bdcf26aSChristoph Hellwig *
1126bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+-------+------+-------+
1136bdcf26aSChristoph Hellwig * Inner: | key 1 | key 2 | key 3 | key N | ptr 1 | ptr 2 | ptr3 | ptr N |
1146bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+-------+------+-------+
1156bdcf26aSChristoph Hellwig */
1166bdcf26aSChristoph Hellwig struct xfs_iext_node {
1176bdcf26aSChristoph Hellwig uint64_t keys[KEYS_PER_NODE];
1186bdcf26aSChristoph Hellwig #define XFS_IEXT_KEY_INVALID (1ULL << 63)
1196bdcf26aSChristoph Hellwig void *ptrs[KEYS_PER_NODE];
1206bdcf26aSChristoph Hellwig };
1216bdcf26aSChristoph Hellwig
1226bdcf26aSChristoph Hellwig struct xfs_iext_leaf {
1236bdcf26aSChristoph Hellwig struct xfs_iext_rec recs[RECS_PER_LEAF];
1246bdcf26aSChristoph Hellwig struct xfs_iext_leaf *prev;
1256bdcf26aSChristoph Hellwig struct xfs_iext_leaf *next;
1266bdcf26aSChristoph Hellwig };
1276bdcf26aSChristoph Hellwig
xfs_iext_count(struct xfs_ifork * ifp)1286bdcf26aSChristoph Hellwig inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp)
1296bdcf26aSChristoph Hellwig {
1306bdcf26aSChristoph Hellwig return ifp->if_bytes / sizeof(struct xfs_iext_rec);
1316bdcf26aSChristoph Hellwig }
1326bdcf26aSChristoph Hellwig
xfs_iext_max_recs(struct xfs_ifork * ifp)1336bdcf26aSChristoph Hellwig static inline int xfs_iext_max_recs(struct xfs_ifork *ifp)
1346bdcf26aSChristoph Hellwig {
1356bdcf26aSChristoph Hellwig if (ifp->if_height == 1)
1366bdcf26aSChristoph Hellwig return xfs_iext_count(ifp);
1376bdcf26aSChristoph Hellwig return RECS_PER_LEAF;
1386bdcf26aSChristoph Hellwig }
1396bdcf26aSChristoph Hellwig
cur_rec(struct xfs_iext_cursor * cur)1406bdcf26aSChristoph Hellwig static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur)
1416bdcf26aSChristoph Hellwig {
1426bdcf26aSChristoph Hellwig return &cur->leaf->recs[cur->pos];
1436bdcf26aSChristoph Hellwig }
1446bdcf26aSChristoph Hellwig
xfs_iext_valid(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)1456bdcf26aSChristoph Hellwig static inline bool xfs_iext_valid(struct xfs_ifork *ifp,
1466bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur)
1476bdcf26aSChristoph Hellwig {
1486bdcf26aSChristoph Hellwig if (!cur->leaf)
1496bdcf26aSChristoph Hellwig return false;
1506bdcf26aSChristoph Hellwig if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp))
1516bdcf26aSChristoph Hellwig return false;
1526bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(cur_rec(cur)))
1536bdcf26aSChristoph Hellwig return false;
1546bdcf26aSChristoph Hellwig return true;
1556bdcf26aSChristoph Hellwig }
1566bdcf26aSChristoph Hellwig
1576bdcf26aSChristoph Hellwig static void *
xfs_iext_find_first_leaf(struct xfs_ifork * ifp)1586bdcf26aSChristoph Hellwig xfs_iext_find_first_leaf(
1596bdcf26aSChristoph Hellwig struct xfs_ifork *ifp)
1606bdcf26aSChristoph Hellwig {
1616bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root;
1626bdcf26aSChristoph Hellwig int height;
1636bdcf26aSChristoph Hellwig
1646bdcf26aSChristoph Hellwig if (!ifp->if_height)
1656bdcf26aSChristoph Hellwig return NULL;
1666bdcf26aSChristoph Hellwig
1676bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > 1; height--) {
1686bdcf26aSChristoph Hellwig node = node->ptrs[0];
1696bdcf26aSChristoph Hellwig ASSERT(node);
1706bdcf26aSChristoph Hellwig }
1716bdcf26aSChristoph Hellwig
1726bdcf26aSChristoph Hellwig return node;
1736bdcf26aSChristoph Hellwig }
1746bdcf26aSChristoph Hellwig
1756bdcf26aSChristoph Hellwig static void *
xfs_iext_find_last_leaf(struct xfs_ifork * ifp)1766bdcf26aSChristoph Hellwig xfs_iext_find_last_leaf(
1776bdcf26aSChristoph Hellwig struct xfs_ifork *ifp)
1786bdcf26aSChristoph Hellwig {
1796bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root;
1806bdcf26aSChristoph Hellwig int height, i;
1816bdcf26aSChristoph Hellwig
1826bdcf26aSChristoph Hellwig if (!ifp->if_height)
1836bdcf26aSChristoph Hellwig return NULL;
1846bdcf26aSChristoph Hellwig
1856bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > 1; height--) {
1866bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++)
1876bdcf26aSChristoph Hellwig if (!node->ptrs[i])
1886bdcf26aSChristoph Hellwig break;
1896bdcf26aSChristoph Hellwig node = node->ptrs[i - 1];
1906bdcf26aSChristoph Hellwig ASSERT(node);
1916bdcf26aSChristoph Hellwig }
1926bdcf26aSChristoph Hellwig
1936bdcf26aSChristoph Hellwig return node;
1946bdcf26aSChristoph Hellwig }
1956bdcf26aSChristoph Hellwig
1966bdcf26aSChristoph Hellwig void
xfs_iext_first(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)1976bdcf26aSChristoph Hellwig xfs_iext_first(
1986bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
1996bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur)
2006bdcf26aSChristoph Hellwig {
2016bdcf26aSChristoph Hellwig cur->pos = 0;
2026bdcf26aSChristoph Hellwig cur->leaf = xfs_iext_find_first_leaf(ifp);
2036bdcf26aSChristoph Hellwig }
2046bdcf26aSChristoph Hellwig
2056bdcf26aSChristoph Hellwig void
xfs_iext_last(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)2066bdcf26aSChristoph Hellwig xfs_iext_last(
2076bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
2086bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur)
2096bdcf26aSChristoph Hellwig {
2106bdcf26aSChristoph Hellwig int i;
2116bdcf26aSChristoph Hellwig
2126bdcf26aSChristoph Hellwig cur->leaf = xfs_iext_find_last_leaf(ifp);
2136bdcf26aSChristoph Hellwig if (!cur->leaf) {
2146bdcf26aSChristoph Hellwig cur->pos = 0;
2156bdcf26aSChristoph Hellwig return;
2166bdcf26aSChristoph Hellwig }
2176bdcf26aSChristoph Hellwig
2186bdcf26aSChristoph Hellwig for (i = 1; i < xfs_iext_max_recs(ifp); i++) {
2196bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(&cur->leaf->recs[i]))
2206bdcf26aSChristoph Hellwig break;
2216bdcf26aSChristoph Hellwig }
2226bdcf26aSChristoph Hellwig cur->pos = i - 1;
2236bdcf26aSChristoph Hellwig }
2246bdcf26aSChristoph Hellwig
2256bdcf26aSChristoph Hellwig void
xfs_iext_next(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)2266bdcf26aSChristoph Hellwig xfs_iext_next(
2276bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
2286bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur)
2296bdcf26aSChristoph Hellwig {
2306bdcf26aSChristoph Hellwig if (!cur->leaf) {
2316bdcf26aSChristoph Hellwig ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);
2326bdcf26aSChristoph Hellwig xfs_iext_first(ifp, cur);
2336bdcf26aSChristoph Hellwig return;
2346bdcf26aSChristoph Hellwig }
2356bdcf26aSChristoph Hellwig
2366bdcf26aSChristoph Hellwig ASSERT(cur->pos >= 0);
2376bdcf26aSChristoph Hellwig ASSERT(cur->pos < xfs_iext_max_recs(ifp));
2386bdcf26aSChristoph Hellwig
2396bdcf26aSChristoph Hellwig cur->pos++;
2406bdcf26aSChristoph Hellwig if (ifp->if_height > 1 && !xfs_iext_valid(ifp, cur) &&
2416bdcf26aSChristoph Hellwig cur->leaf->next) {
2426bdcf26aSChristoph Hellwig cur->leaf = cur->leaf->next;
2436bdcf26aSChristoph Hellwig cur->pos = 0;
2446bdcf26aSChristoph Hellwig }
2456bdcf26aSChristoph Hellwig }
2466bdcf26aSChristoph Hellwig
2476bdcf26aSChristoph Hellwig void
xfs_iext_prev(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)2486bdcf26aSChristoph Hellwig xfs_iext_prev(
2496bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
2506bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur)
2516bdcf26aSChristoph Hellwig {
2526bdcf26aSChristoph Hellwig if (!cur->leaf) {
2536bdcf26aSChristoph Hellwig ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);
2546bdcf26aSChristoph Hellwig xfs_iext_last(ifp, cur);
2556bdcf26aSChristoph Hellwig return;
2566bdcf26aSChristoph Hellwig }
2576bdcf26aSChristoph Hellwig
2586bdcf26aSChristoph Hellwig ASSERT(cur->pos >= 0);
2596bdcf26aSChristoph Hellwig ASSERT(cur->pos <= RECS_PER_LEAF);
2606bdcf26aSChristoph Hellwig
2616bdcf26aSChristoph Hellwig recurse:
2626bdcf26aSChristoph Hellwig do {
2636bdcf26aSChristoph Hellwig cur->pos--;
2646bdcf26aSChristoph Hellwig if (xfs_iext_valid(ifp, cur))
2656bdcf26aSChristoph Hellwig return;
2666bdcf26aSChristoph Hellwig } while (cur->pos > 0);
2676bdcf26aSChristoph Hellwig
2686bdcf26aSChristoph Hellwig if (ifp->if_height > 1 && cur->leaf->prev) {
2696bdcf26aSChristoph Hellwig cur->leaf = cur->leaf->prev;
2706bdcf26aSChristoph Hellwig cur->pos = RECS_PER_LEAF;
2716bdcf26aSChristoph Hellwig goto recurse;
2726bdcf26aSChristoph Hellwig }
2736bdcf26aSChristoph Hellwig }
2746bdcf26aSChristoph Hellwig
2756bdcf26aSChristoph Hellwig static inline int
xfs_iext_key_cmp(struct xfs_iext_node * node,int n,xfs_fileoff_t offset)2766bdcf26aSChristoph Hellwig xfs_iext_key_cmp(
2776bdcf26aSChristoph Hellwig struct xfs_iext_node *node,
2786bdcf26aSChristoph Hellwig int n,
2796bdcf26aSChristoph Hellwig xfs_fileoff_t offset)
2806bdcf26aSChristoph Hellwig {
2816bdcf26aSChristoph Hellwig if (node->keys[n] > offset)
2826bdcf26aSChristoph Hellwig return 1;
2836bdcf26aSChristoph Hellwig if (node->keys[n] < offset)
2846bdcf26aSChristoph Hellwig return -1;
2856bdcf26aSChristoph Hellwig return 0;
2866bdcf26aSChristoph Hellwig }
2876bdcf26aSChristoph Hellwig
2886bdcf26aSChristoph Hellwig static inline int
xfs_iext_rec_cmp(struct xfs_iext_rec * rec,xfs_fileoff_t offset)2896bdcf26aSChristoph Hellwig xfs_iext_rec_cmp(
2906bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec,
2916bdcf26aSChristoph Hellwig xfs_fileoff_t offset)
2926bdcf26aSChristoph Hellwig {
2936bdcf26aSChristoph Hellwig uint64_t rec_offset = rec->lo & XFS_IEXT_STARTOFF_MASK;
2942015a63dSDarrick J. Wong uint32_t rec_len = rec->hi & XFS_IEXT_LENGTH_MASK;
2956bdcf26aSChristoph Hellwig
2966bdcf26aSChristoph Hellwig if (rec_offset > offset)
2976bdcf26aSChristoph Hellwig return 1;
2986bdcf26aSChristoph Hellwig if (rec_offset + rec_len <= offset)
2996bdcf26aSChristoph Hellwig return -1;
3006bdcf26aSChristoph Hellwig return 0;
3016bdcf26aSChristoph Hellwig }
3026bdcf26aSChristoph Hellwig
3036bdcf26aSChristoph Hellwig static void *
xfs_iext_find_level(struct xfs_ifork * ifp,xfs_fileoff_t offset,int level)3046bdcf26aSChristoph Hellwig xfs_iext_find_level(
3056bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
3066bdcf26aSChristoph Hellwig xfs_fileoff_t offset,
3076bdcf26aSChristoph Hellwig int level)
3086bdcf26aSChristoph Hellwig {
3096bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root;
3106bdcf26aSChristoph Hellwig int height, i;
3116bdcf26aSChristoph Hellwig
3126bdcf26aSChristoph Hellwig if (!ifp->if_height)
3136bdcf26aSChristoph Hellwig return NULL;
3146bdcf26aSChristoph Hellwig
3156bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > level; height--) {
3166bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++)
3176bdcf26aSChristoph Hellwig if (xfs_iext_key_cmp(node, i, offset) > 0)
3186bdcf26aSChristoph Hellwig break;
3196bdcf26aSChristoph Hellwig
3206bdcf26aSChristoph Hellwig node = node->ptrs[i - 1];
3216bdcf26aSChristoph Hellwig if (!node)
3226bdcf26aSChristoph Hellwig break;
3236bdcf26aSChristoph Hellwig }
3246bdcf26aSChristoph Hellwig
3256bdcf26aSChristoph Hellwig return node;
3266bdcf26aSChristoph Hellwig }
3276bdcf26aSChristoph Hellwig
3286bdcf26aSChristoph Hellwig static int
xfs_iext_node_pos(struct xfs_iext_node * node,xfs_fileoff_t offset)3296bdcf26aSChristoph Hellwig xfs_iext_node_pos(
3306bdcf26aSChristoph Hellwig struct xfs_iext_node *node,
3316bdcf26aSChristoph Hellwig xfs_fileoff_t offset)
3326bdcf26aSChristoph Hellwig {
3336bdcf26aSChristoph Hellwig int i;
3346bdcf26aSChristoph Hellwig
3356bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++) {
3366bdcf26aSChristoph Hellwig if (xfs_iext_key_cmp(node, i, offset) > 0)
3376bdcf26aSChristoph Hellwig break;
3386bdcf26aSChristoph Hellwig }
3396bdcf26aSChristoph Hellwig
3406bdcf26aSChristoph Hellwig return i - 1;
3416bdcf26aSChristoph Hellwig }
3426bdcf26aSChristoph Hellwig
3436bdcf26aSChristoph Hellwig static int
xfs_iext_node_insert_pos(struct xfs_iext_node * node,xfs_fileoff_t offset)3446bdcf26aSChristoph Hellwig xfs_iext_node_insert_pos(
3456bdcf26aSChristoph Hellwig struct xfs_iext_node *node,
3466bdcf26aSChristoph Hellwig xfs_fileoff_t offset)
3476bdcf26aSChristoph Hellwig {
3486bdcf26aSChristoph Hellwig int i;
3496bdcf26aSChristoph Hellwig
3506bdcf26aSChristoph Hellwig for (i = 0; i < KEYS_PER_NODE; i++) {
3516bdcf26aSChristoph Hellwig if (xfs_iext_key_cmp(node, i, offset) > 0)
3526bdcf26aSChristoph Hellwig return i;
3536bdcf26aSChristoph Hellwig }
3546bdcf26aSChristoph Hellwig
3556bdcf26aSChristoph Hellwig return KEYS_PER_NODE;
3566bdcf26aSChristoph Hellwig }
3576bdcf26aSChristoph Hellwig
3586bdcf26aSChristoph Hellwig static int
xfs_iext_node_nr_entries(struct xfs_iext_node * node,int start)3596bdcf26aSChristoph Hellwig xfs_iext_node_nr_entries(
3606bdcf26aSChristoph Hellwig struct xfs_iext_node *node,
3616bdcf26aSChristoph Hellwig int start)
3626bdcf26aSChristoph Hellwig {
3636bdcf26aSChristoph Hellwig int i;
3646bdcf26aSChristoph Hellwig
3656bdcf26aSChristoph Hellwig for (i = start; i < KEYS_PER_NODE; i++) {
3666bdcf26aSChristoph Hellwig if (node->keys[i] == XFS_IEXT_KEY_INVALID)
3676bdcf26aSChristoph Hellwig break;
3686bdcf26aSChristoph Hellwig }
3696bdcf26aSChristoph Hellwig
3706bdcf26aSChristoph Hellwig return i;
3716bdcf26aSChristoph Hellwig }
3726bdcf26aSChristoph Hellwig
3736bdcf26aSChristoph Hellwig static int
xfs_iext_leaf_nr_entries(struct xfs_ifork * ifp,struct xfs_iext_leaf * leaf,int start)3746bdcf26aSChristoph Hellwig xfs_iext_leaf_nr_entries(
3756bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
3766bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf,
3776bdcf26aSChristoph Hellwig int start)
3786bdcf26aSChristoph Hellwig {
3796bdcf26aSChristoph Hellwig int i;
3806bdcf26aSChristoph Hellwig
3816bdcf26aSChristoph Hellwig for (i = start; i < xfs_iext_max_recs(ifp); i++) {
3826bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(&leaf->recs[i]))
3836bdcf26aSChristoph Hellwig break;
3846bdcf26aSChristoph Hellwig }
3856bdcf26aSChristoph Hellwig
3866bdcf26aSChristoph Hellwig return i;
3876bdcf26aSChristoph Hellwig }
3886bdcf26aSChristoph Hellwig
3896bdcf26aSChristoph Hellwig static inline uint64_t
xfs_iext_leaf_key(struct xfs_iext_leaf * leaf,int n)3906bdcf26aSChristoph Hellwig xfs_iext_leaf_key(
3916bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf,
3926bdcf26aSChristoph Hellwig int n)
3936bdcf26aSChristoph Hellwig {
3946bdcf26aSChristoph Hellwig return leaf->recs[n].lo & XFS_IEXT_STARTOFF_MASK;
3956bdcf26aSChristoph Hellwig }
3966bdcf26aSChristoph Hellwig
3976bdcf26aSChristoph Hellwig static void
xfs_iext_grow(struct xfs_ifork * ifp)3986bdcf26aSChristoph Hellwig xfs_iext_grow(
3996bdcf26aSChristoph Hellwig struct xfs_ifork *ifp)
4006bdcf26aSChristoph Hellwig {
4016bdcf26aSChristoph Hellwig struct xfs_iext_node *node = kmem_zalloc(NODE_SIZE, KM_NOFS);
4026bdcf26aSChristoph Hellwig int i;
4036bdcf26aSChristoph Hellwig
4046bdcf26aSChristoph Hellwig if (ifp->if_height == 1) {
4056bdcf26aSChristoph Hellwig struct xfs_iext_leaf *prev = ifp->if_u1.if_root;
4066bdcf26aSChristoph Hellwig
4076bdcf26aSChristoph Hellwig node->keys[0] = xfs_iext_leaf_key(prev, 0);
4086bdcf26aSChristoph Hellwig node->ptrs[0] = prev;
4096bdcf26aSChristoph Hellwig } else {
4106bdcf26aSChristoph Hellwig struct xfs_iext_node *prev = ifp->if_u1.if_root;
4116bdcf26aSChristoph Hellwig
4126bdcf26aSChristoph Hellwig ASSERT(ifp->if_height > 1);
4136bdcf26aSChristoph Hellwig
4146bdcf26aSChristoph Hellwig node->keys[0] = prev->keys[0];
4156bdcf26aSChristoph Hellwig node->ptrs[0] = prev;
4166bdcf26aSChristoph Hellwig }
4176bdcf26aSChristoph Hellwig
4186bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++)
4196bdcf26aSChristoph Hellwig node->keys[i] = XFS_IEXT_KEY_INVALID;
4206bdcf26aSChristoph Hellwig
4216bdcf26aSChristoph Hellwig ifp->if_u1.if_root = node;
4226bdcf26aSChristoph Hellwig ifp->if_height++;
4236bdcf26aSChristoph Hellwig }
4246bdcf26aSChristoph Hellwig
4256bdcf26aSChristoph Hellwig static void
xfs_iext_update_node(struct xfs_ifork * ifp,xfs_fileoff_t old_offset,xfs_fileoff_t new_offset,int level,void * ptr)4266bdcf26aSChristoph Hellwig xfs_iext_update_node(
4276bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
4286bdcf26aSChristoph Hellwig xfs_fileoff_t old_offset,
4296bdcf26aSChristoph Hellwig xfs_fileoff_t new_offset,
4306bdcf26aSChristoph Hellwig int level,
4316bdcf26aSChristoph Hellwig void *ptr)
4326bdcf26aSChristoph Hellwig {
4336bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root;
4346bdcf26aSChristoph Hellwig int height, i;
4356bdcf26aSChristoph Hellwig
4366bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > level; height--) {
4376bdcf26aSChristoph Hellwig for (i = 0; i < KEYS_PER_NODE; i++) {
4386bdcf26aSChristoph Hellwig if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0)
4396bdcf26aSChristoph Hellwig break;
4406bdcf26aSChristoph Hellwig if (node->keys[i] == old_offset)
4416bdcf26aSChristoph Hellwig node->keys[i] = new_offset;
4426bdcf26aSChristoph Hellwig }
4436bdcf26aSChristoph Hellwig node = node->ptrs[i - 1];
4446bdcf26aSChristoph Hellwig ASSERT(node);
4456bdcf26aSChristoph Hellwig }
4466bdcf26aSChristoph Hellwig
4476bdcf26aSChristoph Hellwig ASSERT(node == ptr);
4486bdcf26aSChristoph Hellwig }
4496bdcf26aSChristoph Hellwig
4506bdcf26aSChristoph Hellwig static struct xfs_iext_node *
xfs_iext_split_node(struct xfs_iext_node ** nodep,int * pos,int * nr_entries)4516bdcf26aSChristoph Hellwig xfs_iext_split_node(
4526bdcf26aSChristoph Hellwig struct xfs_iext_node **nodep,
4536bdcf26aSChristoph Hellwig int *pos,
4546bdcf26aSChristoph Hellwig int *nr_entries)
4556bdcf26aSChristoph Hellwig {
4566bdcf26aSChristoph Hellwig struct xfs_iext_node *node = *nodep;
4576bdcf26aSChristoph Hellwig struct xfs_iext_node *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
4586bdcf26aSChristoph Hellwig const int nr_move = KEYS_PER_NODE / 2;
4596bdcf26aSChristoph Hellwig int nr_keep = nr_move + (KEYS_PER_NODE & 1);
4606bdcf26aSChristoph Hellwig int i = 0;
4616bdcf26aSChristoph Hellwig
4626bdcf26aSChristoph Hellwig /* for sequential append operations just spill over into the new node */
4636bdcf26aSChristoph Hellwig if (*pos == KEYS_PER_NODE) {
4646bdcf26aSChristoph Hellwig *nodep = new;
4656bdcf26aSChristoph Hellwig *pos = 0;
4666bdcf26aSChristoph Hellwig *nr_entries = 0;
4676bdcf26aSChristoph Hellwig goto done;
4686bdcf26aSChristoph Hellwig }
4696bdcf26aSChristoph Hellwig
4706bdcf26aSChristoph Hellwig
4716bdcf26aSChristoph Hellwig for (i = 0; i < nr_move; i++) {
4726bdcf26aSChristoph Hellwig new->keys[i] = node->keys[nr_keep + i];
4736bdcf26aSChristoph Hellwig new->ptrs[i] = node->ptrs[nr_keep + i];
4746bdcf26aSChristoph Hellwig
4756bdcf26aSChristoph Hellwig node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID;
4766bdcf26aSChristoph Hellwig node->ptrs[nr_keep + i] = NULL;
4776bdcf26aSChristoph Hellwig }
4786bdcf26aSChristoph Hellwig
4796bdcf26aSChristoph Hellwig if (*pos >= nr_keep) {
4806bdcf26aSChristoph Hellwig *nodep = new;
4816bdcf26aSChristoph Hellwig *pos -= nr_keep;
4826bdcf26aSChristoph Hellwig *nr_entries = nr_move;
4836bdcf26aSChristoph Hellwig } else {
4846bdcf26aSChristoph Hellwig *nr_entries = nr_keep;
4856bdcf26aSChristoph Hellwig }
4866bdcf26aSChristoph Hellwig done:
4876bdcf26aSChristoph Hellwig for (; i < KEYS_PER_NODE; i++)
4886bdcf26aSChristoph Hellwig new->keys[i] = XFS_IEXT_KEY_INVALID;
4896bdcf26aSChristoph Hellwig return new;
4906bdcf26aSChristoph Hellwig }
4916bdcf26aSChristoph Hellwig
4926bdcf26aSChristoph Hellwig static void
xfs_iext_insert_node(struct xfs_ifork * ifp,uint64_t offset,void * ptr,int level)4936bdcf26aSChristoph Hellwig xfs_iext_insert_node(
4946bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
4956bdcf26aSChristoph Hellwig uint64_t offset,
4966bdcf26aSChristoph Hellwig void *ptr,
4976bdcf26aSChristoph Hellwig int level)
4986bdcf26aSChristoph Hellwig {
4996bdcf26aSChristoph Hellwig struct xfs_iext_node *node, *new;
5006bdcf26aSChristoph Hellwig int i, pos, nr_entries;
5016bdcf26aSChristoph Hellwig
5026bdcf26aSChristoph Hellwig again:
5036bdcf26aSChristoph Hellwig if (ifp->if_height < level)
5046bdcf26aSChristoph Hellwig xfs_iext_grow(ifp);
5056bdcf26aSChristoph Hellwig
5066bdcf26aSChristoph Hellwig new = NULL;
5076bdcf26aSChristoph Hellwig node = xfs_iext_find_level(ifp, offset, level);
5086bdcf26aSChristoph Hellwig pos = xfs_iext_node_insert_pos(node, offset);
5096bdcf26aSChristoph Hellwig nr_entries = xfs_iext_node_nr_entries(node, pos);
5106bdcf26aSChristoph Hellwig
5116bdcf26aSChristoph Hellwig ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0);
5126bdcf26aSChristoph Hellwig ASSERT(nr_entries <= KEYS_PER_NODE);
5136bdcf26aSChristoph Hellwig
5146bdcf26aSChristoph Hellwig if (nr_entries == KEYS_PER_NODE)
5156bdcf26aSChristoph Hellwig new = xfs_iext_split_node(&node, &pos, &nr_entries);
5166bdcf26aSChristoph Hellwig
517fc258f4bSChristoph Hellwig /*
518fc258f4bSChristoph Hellwig * Update the pointers in higher levels if the first entry changes
519fc258f4bSChristoph Hellwig * in an existing node.
520fc258f4bSChristoph Hellwig */
5216bdcf26aSChristoph Hellwig if (node != new && pos == 0 && nr_entries > 0)
5226bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, node->keys[0], offset, level, node);
5236bdcf26aSChristoph Hellwig
5246bdcf26aSChristoph Hellwig for (i = nr_entries; i > pos; i--) {
5256bdcf26aSChristoph Hellwig node->keys[i] = node->keys[i - 1];
5266bdcf26aSChristoph Hellwig node->ptrs[i] = node->ptrs[i - 1];
5276bdcf26aSChristoph Hellwig }
5286bdcf26aSChristoph Hellwig node->keys[pos] = offset;
5296bdcf26aSChristoph Hellwig node->ptrs[pos] = ptr;
5306bdcf26aSChristoph Hellwig
5316bdcf26aSChristoph Hellwig if (new) {
5326bdcf26aSChristoph Hellwig offset = new->keys[0];
5336bdcf26aSChristoph Hellwig ptr = new;
5346bdcf26aSChristoph Hellwig level++;
5356bdcf26aSChristoph Hellwig goto again;
5366bdcf26aSChristoph Hellwig }
5376bdcf26aSChristoph Hellwig }
5386bdcf26aSChristoph Hellwig
5396bdcf26aSChristoph Hellwig static struct xfs_iext_leaf *
xfs_iext_split_leaf(struct xfs_iext_cursor * cur,int * nr_entries)5406bdcf26aSChristoph Hellwig xfs_iext_split_leaf(
5416bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur,
5426bdcf26aSChristoph Hellwig int *nr_entries)
5436bdcf26aSChristoph Hellwig {
5446bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf = cur->leaf;
5456bdcf26aSChristoph Hellwig struct xfs_iext_leaf *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
5466bdcf26aSChristoph Hellwig const int nr_move = RECS_PER_LEAF / 2;
5476bdcf26aSChristoph Hellwig int nr_keep = nr_move + (RECS_PER_LEAF & 1);
5486bdcf26aSChristoph Hellwig int i;
5496bdcf26aSChristoph Hellwig
5506bdcf26aSChristoph Hellwig /* for sequential append operations just spill over into the new node */
55143d193aaSChristoph Hellwig if (cur->pos == RECS_PER_LEAF) {
5526bdcf26aSChristoph Hellwig cur->leaf = new;
5536bdcf26aSChristoph Hellwig cur->pos = 0;
5546bdcf26aSChristoph Hellwig *nr_entries = 0;
5556bdcf26aSChristoph Hellwig goto done;
5566bdcf26aSChristoph Hellwig }
5576bdcf26aSChristoph Hellwig
5586bdcf26aSChristoph Hellwig for (i = 0; i < nr_move; i++) {
5596bdcf26aSChristoph Hellwig new->recs[i] = leaf->recs[nr_keep + i];
5606bdcf26aSChristoph Hellwig xfs_iext_rec_clear(&leaf->recs[nr_keep + i]);
5616bdcf26aSChristoph Hellwig }
5626bdcf26aSChristoph Hellwig
5636bdcf26aSChristoph Hellwig if (cur->pos >= nr_keep) {
5646bdcf26aSChristoph Hellwig cur->leaf = new;
5656bdcf26aSChristoph Hellwig cur->pos -= nr_keep;
5666bdcf26aSChristoph Hellwig *nr_entries = nr_move;
5676bdcf26aSChristoph Hellwig } else {
5686bdcf26aSChristoph Hellwig *nr_entries = nr_keep;
5696bdcf26aSChristoph Hellwig }
5706bdcf26aSChristoph Hellwig done:
5716bdcf26aSChristoph Hellwig if (leaf->next)
5726bdcf26aSChristoph Hellwig leaf->next->prev = new;
5736bdcf26aSChristoph Hellwig new->next = leaf->next;
5746bdcf26aSChristoph Hellwig new->prev = leaf;
5756bdcf26aSChristoph Hellwig leaf->next = new;
5766bdcf26aSChristoph Hellwig return new;
5776bdcf26aSChristoph Hellwig }
5786bdcf26aSChristoph Hellwig
5796bdcf26aSChristoph Hellwig static void
xfs_iext_alloc_root(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)5806bdcf26aSChristoph Hellwig xfs_iext_alloc_root(
5816bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
5826bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur)
5836bdcf26aSChristoph Hellwig {
5846bdcf26aSChristoph Hellwig ASSERT(ifp->if_bytes == 0);
5856bdcf26aSChristoph Hellwig
5866bdcf26aSChristoph Hellwig ifp->if_u1.if_root = kmem_zalloc(sizeof(struct xfs_iext_rec), KM_NOFS);
5876bdcf26aSChristoph Hellwig ifp->if_height = 1;
5886bdcf26aSChristoph Hellwig
5896bdcf26aSChristoph Hellwig /* now that we have a node step into it */
5906bdcf26aSChristoph Hellwig cur->leaf = ifp->if_u1.if_root;
5916bdcf26aSChristoph Hellwig cur->pos = 0;
5926bdcf26aSChristoph Hellwig }
5936bdcf26aSChristoph Hellwig
5946bdcf26aSChristoph Hellwig static void
xfs_iext_realloc_root(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur)5956bdcf26aSChristoph Hellwig xfs_iext_realloc_root(
5966bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
5976bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur)
5986bdcf26aSChristoph Hellwig {
5993f8a4f1dSDave Chinner int64_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec);
6006bdcf26aSChristoph Hellwig void *new;
6016bdcf26aSChristoph Hellwig
6026bdcf26aSChristoph Hellwig /* account for the prev/next pointers */
6036bdcf26aSChristoph Hellwig if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF)
6046bdcf26aSChristoph Hellwig new_size = NODE_SIZE;
6056bdcf26aSChristoph Hellwig
606771915c4SCarlos Maiolino new = krealloc(ifp->if_u1.if_root, new_size, GFP_NOFS | __GFP_NOFAIL);
6076bdcf26aSChristoph Hellwig memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes);
6086bdcf26aSChristoph Hellwig ifp->if_u1.if_root = new;
6096bdcf26aSChristoph Hellwig cur->leaf = new;
6106bdcf26aSChristoph Hellwig }
6116bdcf26aSChristoph Hellwig
6122ba090d5SChristoph Hellwig /*
6139f9bc034SBrian Foster * Increment the sequence counter on extent tree changes. If we are on a COW
6149f9bc034SBrian Foster * fork, this allows the writeback code to skip looking for a COW extent if the
6159f9bc034SBrian Foster * COW fork hasn't changed. We use WRITE_ONCE here to ensure the update to the
6169f9bc034SBrian Foster * sequence counter is seen before the modifications to the extent tree itself
6179f9bc034SBrian Foster * take effect.
6182ba090d5SChristoph Hellwig */
xfs_iext_inc_seq(struct xfs_ifork * ifp)6192ca09177SDarrick J. Wong static inline void xfs_iext_inc_seq(struct xfs_ifork *ifp)
6202ba090d5SChristoph Hellwig {
6212ba090d5SChristoph Hellwig WRITE_ONCE(ifp->if_seq, READ_ONCE(ifp->if_seq) + 1);
6222ba090d5SChristoph Hellwig }
6232ba090d5SChristoph Hellwig
6240254c2f2SChristoph Hellwig void
xfs_iext_insert(struct xfs_inode * ip,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * irec,int state)6250254c2f2SChristoph Hellwig xfs_iext_insert(
6260254c2f2SChristoph Hellwig struct xfs_inode *ip,
6276bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur,
6280254c2f2SChristoph Hellwig struct xfs_bmbt_irec *irec,
6290254c2f2SChristoph Hellwig int state)
6306bdcf26aSChristoph Hellwig {
6310254c2f2SChristoph Hellwig struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
6326bdcf26aSChristoph Hellwig xfs_fileoff_t offset = irec->br_startoff;
6336bdcf26aSChristoph Hellwig struct xfs_iext_leaf *new = NULL;
6346bdcf26aSChristoph Hellwig int nr_entries, i;
6356bdcf26aSChristoph Hellwig
6362ca09177SDarrick J. Wong xfs_iext_inc_seq(ifp);
637745b3f76SChristoph Hellwig
6386bdcf26aSChristoph Hellwig if (ifp->if_height == 0)
6396bdcf26aSChristoph Hellwig xfs_iext_alloc_root(ifp, cur);
6406bdcf26aSChristoph Hellwig else if (ifp->if_height == 1)
6416bdcf26aSChristoph Hellwig xfs_iext_realloc_root(ifp, cur);
6426bdcf26aSChristoph Hellwig
6436bdcf26aSChristoph Hellwig nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos);
6446bdcf26aSChristoph Hellwig ASSERT(nr_entries <= RECS_PER_LEAF);
6456bdcf26aSChristoph Hellwig ASSERT(cur->pos >= nr_entries ||
6466bdcf26aSChristoph Hellwig xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0);
6476bdcf26aSChristoph Hellwig
6486bdcf26aSChristoph Hellwig if (nr_entries == RECS_PER_LEAF)
6496bdcf26aSChristoph Hellwig new = xfs_iext_split_leaf(cur, &nr_entries);
6506bdcf26aSChristoph Hellwig
651fc258f4bSChristoph Hellwig /*
652fc258f4bSChristoph Hellwig * Update the pointers in higher levels if the first entry changes
653fc258f4bSChristoph Hellwig * in an existing node.
654fc258f4bSChristoph Hellwig */
6556bdcf26aSChristoph Hellwig if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) {
6566bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0),
6576bdcf26aSChristoph Hellwig offset, 1, cur->leaf);
6586bdcf26aSChristoph Hellwig }
6596bdcf26aSChristoph Hellwig
6606bdcf26aSChristoph Hellwig for (i = nr_entries; i > cur->pos; i--)
6616bdcf26aSChristoph Hellwig cur->leaf->recs[i] = cur->leaf->recs[i - 1];
6626bdcf26aSChristoph Hellwig xfs_iext_set(cur_rec(cur), irec);
6636bdcf26aSChristoph Hellwig ifp->if_bytes += sizeof(struct xfs_iext_rec);
6646bdcf26aSChristoph Hellwig
665c54854a4SDarrick J. Wong trace_xfs_iext_insert(ip, cur, state, _RET_IP_);
666c54854a4SDarrick J. Wong
6676bdcf26aSChristoph Hellwig if (new)
6686bdcf26aSChristoph Hellwig xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2);
6696bdcf26aSChristoph Hellwig }
6706bdcf26aSChristoph Hellwig
6716bdcf26aSChristoph Hellwig static struct xfs_iext_node *
xfs_iext_rebalance_node(struct xfs_iext_node * parent,int * pos,struct xfs_iext_node * node,int nr_entries)6726bdcf26aSChristoph Hellwig xfs_iext_rebalance_node(
6736bdcf26aSChristoph Hellwig struct xfs_iext_node *parent,
6746bdcf26aSChristoph Hellwig int *pos,
6756bdcf26aSChristoph Hellwig struct xfs_iext_node *node,
6766bdcf26aSChristoph Hellwig int nr_entries)
6776bdcf26aSChristoph Hellwig {
6783e27c418SChristoph Hellwig /*
6793e27c418SChristoph Hellwig * If the neighbouring nodes are completely full, or have different
6803e27c418SChristoph Hellwig * parents, we might never be able to merge our node, and will only
6813e27c418SChristoph Hellwig * delete it once the number of entries hits zero.
6823e27c418SChristoph Hellwig */
6836bdcf26aSChristoph Hellwig if (nr_entries == 0)
6846bdcf26aSChristoph Hellwig return node;
6856bdcf26aSChristoph Hellwig
6866bdcf26aSChristoph Hellwig if (*pos > 0) {
6876bdcf26aSChristoph Hellwig struct xfs_iext_node *prev = parent->ptrs[*pos - 1];
6886bdcf26aSChristoph Hellwig int nr_prev = xfs_iext_node_nr_entries(prev, 0), i;
6896bdcf26aSChristoph Hellwig
6906bdcf26aSChristoph Hellwig if (nr_prev + nr_entries <= KEYS_PER_NODE) {
6916bdcf26aSChristoph Hellwig for (i = 0; i < nr_entries; i++) {
6926bdcf26aSChristoph Hellwig prev->keys[nr_prev + i] = node->keys[i];
6936bdcf26aSChristoph Hellwig prev->ptrs[nr_prev + i] = node->ptrs[i];
6946bdcf26aSChristoph Hellwig }
6956bdcf26aSChristoph Hellwig return node;
6966bdcf26aSChristoph Hellwig }
6976bdcf26aSChristoph Hellwig }
6986bdcf26aSChristoph Hellwig
6996bdcf26aSChristoph Hellwig if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) {
7006bdcf26aSChristoph Hellwig struct xfs_iext_node *next = parent->ptrs[*pos + 1];
7016bdcf26aSChristoph Hellwig int nr_next = xfs_iext_node_nr_entries(next, 0), i;
7026bdcf26aSChristoph Hellwig
7036bdcf26aSChristoph Hellwig if (nr_entries + nr_next <= KEYS_PER_NODE) {
7043e27c418SChristoph Hellwig /*
7053e27c418SChristoph Hellwig * Merge the next node into this node so that we don't
7063e27c418SChristoph Hellwig * have to do an additional update of the keys in the
7073e27c418SChristoph Hellwig * higher levels.
7083e27c418SChristoph Hellwig */
7096bdcf26aSChristoph Hellwig for (i = 0; i < nr_next; i++) {
7106bdcf26aSChristoph Hellwig node->keys[nr_entries + i] = next->keys[i];
7116bdcf26aSChristoph Hellwig node->ptrs[nr_entries + i] = next->ptrs[i];
7126bdcf26aSChristoph Hellwig }
7136bdcf26aSChristoph Hellwig
7146bdcf26aSChristoph Hellwig ++*pos;
7156bdcf26aSChristoph Hellwig return next;
7166bdcf26aSChristoph Hellwig }
7176bdcf26aSChristoph Hellwig }
7186bdcf26aSChristoph Hellwig
7196bdcf26aSChristoph Hellwig return NULL;
7206bdcf26aSChristoph Hellwig }
7216bdcf26aSChristoph Hellwig
7226bdcf26aSChristoph Hellwig static void
xfs_iext_remove_node(struct xfs_ifork * ifp,xfs_fileoff_t offset,void * victim)7236bdcf26aSChristoph Hellwig xfs_iext_remove_node(
7246bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
7256bdcf26aSChristoph Hellwig xfs_fileoff_t offset,
7266bdcf26aSChristoph Hellwig void *victim)
7276bdcf26aSChristoph Hellwig {
7286bdcf26aSChristoph Hellwig struct xfs_iext_node *node, *parent;
7296bdcf26aSChristoph Hellwig int level = 2, pos, nr_entries, i;
7306bdcf26aSChristoph Hellwig
7316bdcf26aSChristoph Hellwig ASSERT(level <= ifp->if_height);
7326bdcf26aSChristoph Hellwig node = xfs_iext_find_level(ifp, offset, level);
7336bdcf26aSChristoph Hellwig pos = xfs_iext_node_pos(node, offset);
7346bdcf26aSChristoph Hellwig again:
7356bdcf26aSChristoph Hellwig ASSERT(node->ptrs[pos]);
7366bdcf26aSChristoph Hellwig ASSERT(node->ptrs[pos] == victim);
7376bdcf26aSChristoph Hellwig kmem_free(victim);
7386bdcf26aSChristoph Hellwig
7396bdcf26aSChristoph Hellwig nr_entries = xfs_iext_node_nr_entries(node, pos) - 1;
7406bdcf26aSChristoph Hellwig offset = node->keys[0];
7416bdcf26aSChristoph Hellwig for (i = pos; i < nr_entries; i++) {
7426bdcf26aSChristoph Hellwig node->keys[i] = node->keys[i + 1];
7436bdcf26aSChristoph Hellwig node->ptrs[i] = node->ptrs[i + 1];
7446bdcf26aSChristoph Hellwig }
7456bdcf26aSChristoph Hellwig node->keys[nr_entries] = XFS_IEXT_KEY_INVALID;
7466bdcf26aSChristoph Hellwig node->ptrs[nr_entries] = NULL;
7476bdcf26aSChristoph Hellwig
7486bdcf26aSChristoph Hellwig if (pos == 0 && nr_entries > 0) {
749b9aee1d5SChristoph Hellwig xfs_iext_update_node(ifp, offset, node->keys[0], level, node);
7506bdcf26aSChristoph Hellwig offset = node->keys[0];
7516bdcf26aSChristoph Hellwig }
7526bdcf26aSChristoph Hellwig
7536bdcf26aSChristoph Hellwig if (nr_entries >= KEYS_PER_NODE / 2)
7546bdcf26aSChristoph Hellwig return;
7556bdcf26aSChristoph Hellwig
7566bdcf26aSChristoph Hellwig if (level < ifp->if_height) {
7573e27c418SChristoph Hellwig /*
7583e27c418SChristoph Hellwig * If we aren't at the root yet try to find a neighbour node to
7593e27c418SChristoph Hellwig * merge with (or delete the node if it is empty), and then
7603e27c418SChristoph Hellwig * recurse up to the next level.
7613e27c418SChristoph Hellwig */
7626bdcf26aSChristoph Hellwig level++;
7636bdcf26aSChristoph Hellwig parent = xfs_iext_find_level(ifp, offset, level);
7646bdcf26aSChristoph Hellwig pos = xfs_iext_node_pos(parent, offset);
7656bdcf26aSChristoph Hellwig
7666bdcf26aSChristoph Hellwig ASSERT(pos != KEYS_PER_NODE);
7676bdcf26aSChristoph Hellwig ASSERT(parent->ptrs[pos] == node);
7686bdcf26aSChristoph Hellwig
7696bdcf26aSChristoph Hellwig node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries);
7706bdcf26aSChristoph Hellwig if (node) {
7716bdcf26aSChristoph Hellwig victim = node;
7726bdcf26aSChristoph Hellwig node = parent;
7736bdcf26aSChristoph Hellwig goto again;
7746bdcf26aSChristoph Hellwig }
7756bdcf26aSChristoph Hellwig } else if (nr_entries == 1) {
7763e27c418SChristoph Hellwig /*
7773e27c418SChristoph Hellwig * If we are at the root and only one entry is left we can just
7783e27c418SChristoph Hellwig * free this node and update the root pointer.
7793e27c418SChristoph Hellwig */
7806bdcf26aSChristoph Hellwig ASSERT(node == ifp->if_u1.if_root);
7816bdcf26aSChristoph Hellwig ifp->if_u1.if_root = node->ptrs[0];
7826bdcf26aSChristoph Hellwig ifp->if_height--;
7836bdcf26aSChristoph Hellwig kmem_free(node);
7846bdcf26aSChristoph Hellwig }
7856bdcf26aSChristoph Hellwig }
7866bdcf26aSChristoph Hellwig
7876bdcf26aSChristoph Hellwig 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)7886bdcf26aSChristoph Hellwig xfs_iext_rebalance_leaf(
7896bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
7906bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur,
7916bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf,
7926bdcf26aSChristoph Hellwig xfs_fileoff_t offset,
793ae82968eSChristoph Hellwig int nr_entries)
7946bdcf26aSChristoph Hellwig {
795ae82968eSChristoph Hellwig /*
796ae82968eSChristoph Hellwig * If the neighbouring nodes are completely full we might never be able
797ae82968eSChristoph Hellwig * to merge our node, and will only delete it once the number of
798ae82968eSChristoph Hellwig * entries hits zero.
799ae82968eSChristoph Hellwig */
800ae82968eSChristoph Hellwig if (nr_entries == 0)
801ae82968eSChristoph Hellwig goto remove_node;
802ae82968eSChristoph Hellwig
8036bdcf26aSChristoph Hellwig if (leaf->prev) {
8046bdcf26aSChristoph Hellwig int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i;
8056bdcf26aSChristoph Hellwig
806ae82968eSChristoph Hellwig if (nr_prev + nr_entries <= RECS_PER_LEAF) {
807ae82968eSChristoph Hellwig for (i = 0; i < nr_entries; i++)
8086bdcf26aSChristoph Hellwig leaf->prev->recs[nr_prev + i] = leaf->recs[i];
8096bdcf26aSChristoph Hellwig
8106bdcf26aSChristoph Hellwig if (cur->leaf == leaf) {
8116bdcf26aSChristoph Hellwig cur->leaf = leaf->prev;
8126bdcf26aSChristoph Hellwig cur->pos += nr_prev;
8136bdcf26aSChristoph Hellwig }
8146bdcf26aSChristoph Hellwig goto remove_node;
8156bdcf26aSChristoph Hellwig }
8166bdcf26aSChristoph Hellwig }
8176bdcf26aSChristoph Hellwig
8186bdcf26aSChristoph Hellwig if (leaf->next) {
8196bdcf26aSChristoph Hellwig int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i;
8206bdcf26aSChristoph Hellwig
821ae82968eSChristoph Hellwig if (nr_entries + nr_next <= RECS_PER_LEAF) {
8223e27c418SChristoph Hellwig /*
8233e27c418SChristoph Hellwig * Merge the next node into this node so that we don't
8243e27c418SChristoph Hellwig * have to do an additional update of the keys in the
8253e27c418SChristoph Hellwig * higher levels.
8263e27c418SChristoph Hellwig */
827ae82968eSChristoph Hellwig for (i = 0; i < nr_next; i++) {
828ae82968eSChristoph Hellwig leaf->recs[nr_entries + i] =
829ae82968eSChristoph Hellwig leaf->next->recs[i];
830ae82968eSChristoph Hellwig }
8316bdcf26aSChristoph Hellwig
8326bdcf26aSChristoph Hellwig if (cur->leaf == leaf->next) {
8336bdcf26aSChristoph Hellwig cur->leaf = leaf;
834ae82968eSChristoph Hellwig cur->pos += nr_entries;
8356bdcf26aSChristoph Hellwig }
8366bdcf26aSChristoph Hellwig
8376bdcf26aSChristoph Hellwig offset = xfs_iext_leaf_key(leaf->next, 0);
8386bdcf26aSChristoph Hellwig leaf = leaf->next;
8396bdcf26aSChristoph Hellwig goto remove_node;
8406bdcf26aSChristoph Hellwig }
8416bdcf26aSChristoph Hellwig }
8426bdcf26aSChristoph Hellwig
8436bdcf26aSChristoph Hellwig return;
8446bdcf26aSChristoph Hellwig remove_node:
8456bdcf26aSChristoph Hellwig if (leaf->prev)
8466bdcf26aSChristoph Hellwig leaf->prev->next = leaf->next;
8476bdcf26aSChristoph Hellwig if (leaf->next)
8486bdcf26aSChristoph Hellwig leaf->next->prev = leaf->prev;
8496bdcf26aSChristoph Hellwig xfs_iext_remove_node(ifp, offset, leaf);
8506bdcf26aSChristoph Hellwig }
8516bdcf26aSChristoph Hellwig
8526bdcf26aSChristoph Hellwig static void
xfs_iext_free_last_leaf(struct xfs_ifork * ifp)8536bdcf26aSChristoph Hellwig xfs_iext_free_last_leaf(
8546bdcf26aSChristoph Hellwig struct xfs_ifork *ifp)
8556bdcf26aSChristoph Hellwig {
8566bdcf26aSChristoph Hellwig ifp->if_height--;
8576bdcf26aSChristoph Hellwig kmem_free(ifp->if_u1.if_root);
8586818caa4SShu Wang ifp->if_u1.if_root = NULL;
8596bdcf26aSChristoph Hellwig }
8606bdcf26aSChristoph Hellwig
861c38ccf59SChristoph Hellwig void
xfs_iext_remove(struct xfs_inode * ip,struct xfs_iext_cursor * cur,int state)862c38ccf59SChristoph Hellwig xfs_iext_remove(
863c38ccf59SChristoph Hellwig struct xfs_inode *ip,
864c38ccf59SChristoph Hellwig struct xfs_iext_cursor *cur,
865c38ccf59SChristoph Hellwig int state)
8666bdcf26aSChristoph Hellwig {
867c38ccf59SChristoph Hellwig struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
8686bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf = cur->leaf;
8696bdcf26aSChristoph Hellwig xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0);
8706bdcf26aSChristoph Hellwig int i, nr_entries;
8716bdcf26aSChristoph Hellwig
872c38ccf59SChristoph Hellwig trace_xfs_iext_remove(ip, cur, state, _RET_IP_);
873c38ccf59SChristoph Hellwig
8746bdcf26aSChristoph Hellwig ASSERT(ifp->if_height > 0);
8756bdcf26aSChristoph Hellwig ASSERT(ifp->if_u1.if_root != NULL);
8766bdcf26aSChristoph Hellwig ASSERT(xfs_iext_valid(ifp, cur));
8776bdcf26aSChristoph Hellwig
8782ca09177SDarrick J. Wong xfs_iext_inc_seq(ifp);
879745b3f76SChristoph Hellwig
8806bdcf26aSChristoph Hellwig nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1;
8816bdcf26aSChristoph Hellwig for (i = cur->pos; i < nr_entries; i++)
8826bdcf26aSChristoph Hellwig leaf->recs[i] = leaf->recs[i + 1];
8836bdcf26aSChristoph Hellwig xfs_iext_rec_clear(&leaf->recs[nr_entries]);
8846bdcf26aSChristoph Hellwig ifp->if_bytes -= sizeof(struct xfs_iext_rec);
8856bdcf26aSChristoph Hellwig
8866bdcf26aSChristoph Hellwig if (cur->pos == 0 && nr_entries > 0) {
8876bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1,
8886bdcf26aSChristoph Hellwig leaf);
8896bdcf26aSChristoph Hellwig offset = xfs_iext_leaf_key(leaf, 0);
8906bdcf26aSChristoph Hellwig } else if (cur->pos == nr_entries) {
8916bdcf26aSChristoph Hellwig if (ifp->if_height > 1 && leaf->next)
8926bdcf26aSChristoph Hellwig cur->leaf = leaf->next;
8936bdcf26aSChristoph Hellwig else
8946bdcf26aSChristoph Hellwig cur->leaf = NULL;
8956bdcf26aSChristoph Hellwig cur->pos = 0;
8966bdcf26aSChristoph Hellwig }
8976bdcf26aSChristoph Hellwig
8986bdcf26aSChristoph Hellwig if (nr_entries >= RECS_PER_LEAF / 2)
8996bdcf26aSChristoph Hellwig return;
9006bdcf26aSChristoph Hellwig
9016bdcf26aSChristoph Hellwig if (ifp->if_height > 1)
9026bdcf26aSChristoph Hellwig xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries);
9036bdcf26aSChristoph Hellwig else if (nr_entries == 0)
9046bdcf26aSChristoph Hellwig xfs_iext_free_last_leaf(ifp);
9056bdcf26aSChristoph Hellwig }
9066bdcf26aSChristoph Hellwig
9076bdcf26aSChristoph Hellwig /*
9086bdcf26aSChristoph Hellwig * Lookup the extent covering bno.
9096bdcf26aSChristoph Hellwig *
9106bdcf26aSChristoph Hellwig * If there is an extent covering bno return the extent index, and store the
9116bdcf26aSChristoph Hellwig * expanded extent structure in *gotp, and the extent cursor in *cur.
9126bdcf26aSChristoph Hellwig * If there is no extent covering bno, but there is an extent after it (e.g.
9136bdcf26aSChristoph Hellwig * it lies in a hole) return that extent in *gotp and its cursor in *cur
9146bdcf26aSChristoph Hellwig * instead.
9156bdcf26aSChristoph Hellwig * If bno is beyond the last extent return false, and return an invalid
9166bdcf26aSChristoph Hellwig * cursor value.
9176bdcf26aSChristoph Hellwig */
9186bdcf26aSChristoph Hellwig 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)9196bdcf26aSChristoph Hellwig xfs_iext_lookup_extent(
9206bdcf26aSChristoph Hellwig struct xfs_inode *ip,
9216bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
9226bdcf26aSChristoph Hellwig xfs_fileoff_t offset,
9236bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur,
9246bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *gotp)
9256bdcf26aSChristoph Hellwig {
9266bdcf26aSChristoph Hellwig XFS_STATS_INC(ip->i_mount, xs_look_exlist);
9276bdcf26aSChristoph Hellwig
9286bdcf26aSChristoph Hellwig cur->leaf = xfs_iext_find_level(ifp, offset, 1);
9296bdcf26aSChristoph Hellwig if (!cur->leaf) {
9306bdcf26aSChristoph Hellwig cur->pos = 0;
9316bdcf26aSChristoph Hellwig return false;
9326bdcf26aSChristoph Hellwig }
9336bdcf26aSChristoph Hellwig
9346bdcf26aSChristoph Hellwig for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) {
9356bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec = cur_rec(cur);
9366bdcf26aSChristoph Hellwig
9376bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(rec))
9386bdcf26aSChristoph Hellwig break;
9396bdcf26aSChristoph Hellwig if (xfs_iext_rec_cmp(rec, offset) >= 0)
9406bdcf26aSChristoph Hellwig goto found;
9416bdcf26aSChristoph Hellwig }
9426bdcf26aSChristoph Hellwig
9436bdcf26aSChristoph Hellwig /* Try looking in the next node for an entry > offset */
9446bdcf26aSChristoph Hellwig if (ifp->if_height == 1 || !cur->leaf->next)
9456bdcf26aSChristoph Hellwig return false;
9466bdcf26aSChristoph Hellwig cur->leaf = cur->leaf->next;
9476bdcf26aSChristoph Hellwig cur->pos = 0;
9486bdcf26aSChristoph Hellwig if (!xfs_iext_valid(ifp, cur))
9496bdcf26aSChristoph Hellwig return false;
9506bdcf26aSChristoph Hellwig found:
9516bdcf26aSChristoph Hellwig xfs_iext_get(gotp, cur_rec(cur));
9526bdcf26aSChristoph Hellwig return true;
9536bdcf26aSChristoph Hellwig }
9546bdcf26aSChristoph Hellwig
9556bdcf26aSChristoph Hellwig /*
9566bdcf26aSChristoph Hellwig * Returns the last extent before end, and if this extent doesn't cover
9576bdcf26aSChristoph Hellwig * end, update end to the end of the extent.
9586bdcf26aSChristoph Hellwig */
9596bdcf26aSChristoph Hellwig 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)9606bdcf26aSChristoph Hellwig xfs_iext_lookup_extent_before(
9616bdcf26aSChristoph Hellwig struct xfs_inode *ip,
9626bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
9636bdcf26aSChristoph Hellwig xfs_fileoff_t *end,
9646bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur,
9656bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *gotp)
9666bdcf26aSChristoph Hellwig {
9676bdcf26aSChristoph Hellwig /* could be optimized to not even look up the next on a match.. */
9686bdcf26aSChristoph Hellwig if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) &&
9696bdcf26aSChristoph Hellwig gotp->br_startoff <= *end - 1)
9706bdcf26aSChristoph Hellwig return true;
9716bdcf26aSChristoph Hellwig if (!xfs_iext_prev_extent(ifp, cur, gotp))
9726bdcf26aSChristoph Hellwig return false;
9736bdcf26aSChristoph Hellwig *end = gotp->br_startoff + gotp->br_blockcount;
9746bdcf26aSChristoph Hellwig return true;
9756bdcf26aSChristoph Hellwig }
9766bdcf26aSChristoph Hellwig
9776bdcf26aSChristoph Hellwig void
xfs_iext_update_extent(struct xfs_inode * ip,int state,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * new)9786bdcf26aSChristoph Hellwig xfs_iext_update_extent(
9796bdcf26aSChristoph Hellwig struct xfs_inode *ip,
9806bdcf26aSChristoph Hellwig int state,
9816bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur,
9826bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *new)
9836bdcf26aSChristoph Hellwig {
9846bdcf26aSChristoph Hellwig struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);
9856bdcf26aSChristoph Hellwig
9862ca09177SDarrick J. Wong xfs_iext_inc_seq(ifp);
987745b3f76SChristoph Hellwig
9886bdcf26aSChristoph Hellwig if (cur->pos == 0) {
9896bdcf26aSChristoph Hellwig struct xfs_bmbt_irec old;
9906bdcf26aSChristoph Hellwig
9916bdcf26aSChristoph Hellwig xfs_iext_get(&old, cur_rec(cur));
9926bdcf26aSChristoph Hellwig if (new->br_startoff != old.br_startoff) {
9936bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, old.br_startoff,
9946bdcf26aSChristoph Hellwig new->br_startoff, 1, cur->leaf);
9956bdcf26aSChristoph Hellwig }
9966bdcf26aSChristoph Hellwig }
9976bdcf26aSChristoph Hellwig
9986bdcf26aSChristoph Hellwig trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_);
9996bdcf26aSChristoph Hellwig xfs_iext_set(cur_rec(cur), new);
10006bdcf26aSChristoph Hellwig trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_);
10016bdcf26aSChristoph Hellwig }
10026bdcf26aSChristoph Hellwig
10036bdcf26aSChristoph Hellwig /*
10046bdcf26aSChristoph Hellwig * Return true if the cursor points at an extent and return the extent structure
10056bdcf26aSChristoph Hellwig * in gotp. Else return false.
10066bdcf26aSChristoph Hellwig */
10076bdcf26aSChristoph Hellwig bool
xfs_iext_get_extent(struct xfs_ifork * ifp,struct xfs_iext_cursor * cur,struct xfs_bmbt_irec * gotp)10086bdcf26aSChristoph Hellwig xfs_iext_get_extent(
10096bdcf26aSChristoph Hellwig struct xfs_ifork *ifp,
10106bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur,
10116bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *gotp)
10126bdcf26aSChristoph Hellwig {
10136bdcf26aSChristoph Hellwig if (!xfs_iext_valid(ifp, cur))
10146bdcf26aSChristoph Hellwig return false;
10156bdcf26aSChristoph Hellwig xfs_iext_get(gotp, cur_rec(cur));
10166bdcf26aSChristoph Hellwig return true;
10176bdcf26aSChristoph Hellwig }
10186bdcf26aSChristoph Hellwig
10196bdcf26aSChristoph Hellwig /*
10206bdcf26aSChristoph Hellwig * This is a recursive function, because of that we need to be extremely
10216bdcf26aSChristoph Hellwig * careful with stack usage.
10226bdcf26aSChristoph Hellwig */
10236bdcf26aSChristoph Hellwig static void
xfs_iext_destroy_node(struct xfs_iext_node * node,int level)10246bdcf26aSChristoph Hellwig xfs_iext_destroy_node(
10256bdcf26aSChristoph Hellwig struct xfs_iext_node *node,
10266bdcf26aSChristoph Hellwig int level)
10276bdcf26aSChristoph Hellwig {
10286bdcf26aSChristoph Hellwig int i;
10296bdcf26aSChristoph Hellwig
10306bdcf26aSChristoph Hellwig if (level > 1) {
10316bdcf26aSChristoph Hellwig for (i = 0; i < KEYS_PER_NODE; i++) {
10326bdcf26aSChristoph Hellwig if (node->keys[i] == XFS_IEXT_KEY_INVALID)
10336bdcf26aSChristoph Hellwig break;
10346bdcf26aSChristoph Hellwig xfs_iext_destroy_node(node->ptrs[i], level - 1);
10356bdcf26aSChristoph Hellwig }
10366bdcf26aSChristoph Hellwig }
10376bdcf26aSChristoph Hellwig
10386bdcf26aSChristoph Hellwig kmem_free(node);
10396bdcf26aSChristoph Hellwig }
10406bdcf26aSChristoph Hellwig
10416bdcf26aSChristoph Hellwig void
xfs_iext_destroy(struct xfs_ifork * ifp)10426bdcf26aSChristoph Hellwig xfs_iext_destroy(
10436bdcf26aSChristoph Hellwig struct xfs_ifork *ifp)
10446bdcf26aSChristoph Hellwig {
10456bdcf26aSChristoph Hellwig xfs_iext_destroy_node(ifp->if_u1.if_root, ifp->if_height);
10466bdcf26aSChristoph Hellwig
10476bdcf26aSChristoph Hellwig ifp->if_bytes = 0;
10486bdcf26aSChristoph Hellwig ifp->if_height = 0;
10496bdcf26aSChristoph Hellwig ifp->if_u1.if_root = NULL;
10506bdcf26aSChristoph Hellwig }
1051