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_inode.h" 126bdcf26aSChristoph Hellwig #include "xfs_trans_resv.h" 136bdcf26aSChristoph Hellwig #include "xfs_mount.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 */ 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 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 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 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 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 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 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 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 * 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 * 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 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 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 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 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 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 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 * 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 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 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 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 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 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 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 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 * 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 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 * 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 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 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 */ 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 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 * 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 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 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 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 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 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 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 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 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 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 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