16bdcf26aSChristoph Hellwig /* 26bdcf26aSChristoph Hellwig * Copyright (c) 2017 Christoph Hellwig. 36bdcf26aSChristoph Hellwig * 46bdcf26aSChristoph Hellwig * This program is free software; you can redistribute it and/or modify it 56bdcf26aSChristoph Hellwig * under the terms and conditions of the GNU General Public License, 66bdcf26aSChristoph Hellwig * version 2, as published by the Free Software Foundation. 76bdcf26aSChristoph Hellwig * 86bdcf26aSChristoph Hellwig * This program is distributed in the hope it will be useful, but WITHOUT 96bdcf26aSChristoph Hellwig * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 106bdcf26aSChristoph Hellwig * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 116bdcf26aSChristoph Hellwig * more details. 126bdcf26aSChristoph Hellwig */ 136bdcf26aSChristoph Hellwig 146bdcf26aSChristoph Hellwig #include <linux/cache.h> 156bdcf26aSChristoph Hellwig #include <linux/kernel.h> 166bdcf26aSChristoph Hellwig #include <linux/slab.h> 176bdcf26aSChristoph Hellwig #include "xfs.h" 186bdcf26aSChristoph Hellwig #include "xfs_format.h" 196bdcf26aSChristoph Hellwig #include "xfs_bit.h" 206bdcf26aSChristoph Hellwig #include "xfs_log_format.h" 216bdcf26aSChristoph Hellwig #include "xfs_inode.h" 226bdcf26aSChristoph Hellwig #include "xfs_inode_fork.h" 236bdcf26aSChristoph Hellwig #include "xfs_trans_resv.h" 246bdcf26aSChristoph Hellwig #include "xfs_mount.h" 256bdcf26aSChristoph Hellwig #include "xfs_trace.h" 266bdcf26aSChristoph Hellwig 276bdcf26aSChristoph Hellwig /* 286bdcf26aSChristoph Hellwig * In-core extent record layout: 296bdcf26aSChristoph Hellwig * 306bdcf26aSChristoph Hellwig * +-------+----------------------------+ 316bdcf26aSChristoph Hellwig * | 00:53 | all 54 bits of startoff | 326bdcf26aSChristoph Hellwig * | 54:63 | low 10 bits of startblock | 336bdcf26aSChristoph Hellwig * +-------+----------------------------+ 346bdcf26aSChristoph Hellwig * | 00:20 | all 21 bits of length | 356bdcf26aSChristoph Hellwig * | 21 | unwritten extent bit | 366bdcf26aSChristoph Hellwig * | 22:63 | high 42 bits of startblock | 376bdcf26aSChristoph Hellwig * +-------+----------------------------+ 386bdcf26aSChristoph Hellwig */ 396bdcf26aSChristoph Hellwig #define XFS_IEXT_STARTOFF_MASK xfs_mask64lo(BMBT_STARTOFF_BITLEN) 406bdcf26aSChristoph Hellwig #define XFS_IEXT_LENGTH_MASK xfs_mask64lo(BMBT_BLOCKCOUNT_BITLEN) 416bdcf26aSChristoph Hellwig #define XFS_IEXT_STARTBLOCK_MASK xfs_mask64lo(BMBT_STARTBLOCK_BITLEN) 426bdcf26aSChristoph Hellwig 436bdcf26aSChristoph Hellwig struct xfs_iext_rec { 446bdcf26aSChristoph Hellwig uint64_t lo; 456bdcf26aSChristoph Hellwig uint64_t hi; 466bdcf26aSChristoph Hellwig }; 476bdcf26aSChristoph Hellwig 486bdcf26aSChristoph Hellwig /* 496bdcf26aSChristoph Hellwig * Given that the length can't be a zero, only an empty hi value indicates an 506bdcf26aSChristoph Hellwig * unused record. 516bdcf26aSChristoph Hellwig */ 526bdcf26aSChristoph Hellwig static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec) 536bdcf26aSChristoph Hellwig { 546bdcf26aSChristoph Hellwig return rec->hi == 0; 556bdcf26aSChristoph Hellwig } 566bdcf26aSChristoph Hellwig 576bdcf26aSChristoph Hellwig static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec) 586bdcf26aSChristoph Hellwig { 596bdcf26aSChristoph Hellwig rec->lo = 0; 606bdcf26aSChristoph Hellwig rec->hi = 0; 616bdcf26aSChristoph Hellwig } 626bdcf26aSChristoph Hellwig 636bdcf26aSChristoph Hellwig static void 646bdcf26aSChristoph Hellwig xfs_iext_set( 656bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec, 666bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *irec) 676bdcf26aSChristoph Hellwig { 686bdcf26aSChristoph Hellwig ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0); 696bdcf26aSChristoph Hellwig ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0); 706bdcf26aSChristoph Hellwig ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0); 716bdcf26aSChristoph Hellwig 726bdcf26aSChristoph Hellwig rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK; 736bdcf26aSChristoph Hellwig rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK; 746bdcf26aSChristoph Hellwig 756bdcf26aSChristoph Hellwig rec->lo |= (irec->br_startblock << 54); 766bdcf26aSChristoph Hellwig rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10)); 776bdcf26aSChristoph Hellwig 786bdcf26aSChristoph Hellwig if (irec->br_state == XFS_EXT_UNWRITTEN) 796bdcf26aSChristoph Hellwig rec->hi |= (1 << 21); 806bdcf26aSChristoph Hellwig } 816bdcf26aSChristoph Hellwig 826bdcf26aSChristoph Hellwig static void 836bdcf26aSChristoph Hellwig xfs_iext_get( 846bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *irec, 856bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec) 866bdcf26aSChristoph Hellwig { 876bdcf26aSChristoph Hellwig irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK; 886bdcf26aSChristoph Hellwig irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK; 896bdcf26aSChristoph Hellwig 906bdcf26aSChristoph Hellwig irec->br_startblock = rec->lo >> 54; 916bdcf26aSChristoph Hellwig irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10); 926bdcf26aSChristoph Hellwig 936bdcf26aSChristoph Hellwig if (rec->hi & (1 << 21)) 946bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_UNWRITTEN; 956bdcf26aSChristoph Hellwig else 966bdcf26aSChristoph Hellwig irec->br_state = XFS_EXT_NORM; 976bdcf26aSChristoph Hellwig } 986bdcf26aSChristoph Hellwig 996bdcf26aSChristoph Hellwig enum { 1006bdcf26aSChristoph Hellwig NODE_SIZE = 256, 1016bdcf26aSChristoph Hellwig KEYS_PER_NODE = NODE_SIZE / (sizeof(uint64_t) + sizeof(void *)), 1026bdcf26aSChristoph Hellwig RECS_PER_LEAF = (NODE_SIZE - (2 * sizeof(struct xfs_iext_leaf *))) / 1036bdcf26aSChristoph Hellwig sizeof(struct xfs_iext_rec), 1046bdcf26aSChristoph Hellwig }; 1056bdcf26aSChristoph Hellwig 1066bdcf26aSChristoph Hellwig /* 1076bdcf26aSChristoph Hellwig * In-core extent btree block layout: 1086bdcf26aSChristoph Hellwig * 1096bdcf26aSChristoph Hellwig * There are two types of blocks in the btree: leaf and inner (non-leaf) blocks. 1106bdcf26aSChristoph Hellwig * 1116bdcf26aSChristoph Hellwig * The leaf blocks are made up by %KEYS_PER_NODE extent records, which each 1126bdcf26aSChristoph Hellwig * contain the startoffset, blockcount, startblock and unwritten extent flag. 1136bdcf26aSChristoph Hellwig * See above for the exact format, followed by pointers to the previous and next 1146bdcf26aSChristoph Hellwig * leaf blocks (if there are any). 1156bdcf26aSChristoph Hellwig * 1166bdcf26aSChristoph Hellwig * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed 1176bdcf26aSChristoph Hellwig * by an equal number of pointers to the btree blocks at the next lower level. 1186bdcf26aSChristoph Hellwig * 1196bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+----------+----------+ 1206bdcf26aSChristoph Hellwig * Leaf: | rec 1 | rec 2 | rec 3 | rec 4 | rec N | prev-ptr | next-ptr | 1216bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+----------+----------+ 1226bdcf26aSChristoph Hellwig * 1236bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+-------+------+-------+ 1246bdcf26aSChristoph Hellwig * Inner: | key 1 | key 2 | key 3 | key N | ptr 1 | ptr 2 | ptr3 | ptr N | 1256bdcf26aSChristoph Hellwig * +-------+-------+-------+-------+-------+-------+------+-------+ 1266bdcf26aSChristoph Hellwig */ 1276bdcf26aSChristoph Hellwig struct xfs_iext_node { 1286bdcf26aSChristoph Hellwig uint64_t keys[KEYS_PER_NODE]; 1296bdcf26aSChristoph Hellwig #define XFS_IEXT_KEY_INVALID (1ULL << 63) 1306bdcf26aSChristoph Hellwig void *ptrs[KEYS_PER_NODE]; 1316bdcf26aSChristoph Hellwig }; 1326bdcf26aSChristoph Hellwig 1336bdcf26aSChristoph Hellwig struct xfs_iext_leaf { 1346bdcf26aSChristoph Hellwig struct xfs_iext_rec recs[RECS_PER_LEAF]; 1356bdcf26aSChristoph Hellwig struct xfs_iext_leaf *prev; 1366bdcf26aSChristoph Hellwig struct xfs_iext_leaf *next; 1376bdcf26aSChristoph Hellwig }; 1386bdcf26aSChristoph Hellwig 1396bdcf26aSChristoph Hellwig inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp) 1406bdcf26aSChristoph Hellwig { 1416bdcf26aSChristoph Hellwig return ifp->if_bytes / sizeof(struct xfs_iext_rec); 1426bdcf26aSChristoph Hellwig } 1436bdcf26aSChristoph Hellwig 1446bdcf26aSChristoph Hellwig static inline int xfs_iext_max_recs(struct xfs_ifork *ifp) 1456bdcf26aSChristoph Hellwig { 1466bdcf26aSChristoph Hellwig if (ifp->if_height == 1) 1476bdcf26aSChristoph Hellwig return xfs_iext_count(ifp); 1486bdcf26aSChristoph Hellwig return RECS_PER_LEAF; 1496bdcf26aSChristoph Hellwig } 1506bdcf26aSChristoph Hellwig 1516bdcf26aSChristoph Hellwig static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur) 1526bdcf26aSChristoph Hellwig { 1536bdcf26aSChristoph Hellwig return &cur->leaf->recs[cur->pos]; 1546bdcf26aSChristoph Hellwig } 1556bdcf26aSChristoph Hellwig 1566bdcf26aSChristoph Hellwig static inline bool xfs_iext_valid(struct xfs_ifork *ifp, 1576bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur) 1586bdcf26aSChristoph Hellwig { 1596bdcf26aSChristoph Hellwig if (!cur->leaf) 1606bdcf26aSChristoph Hellwig return false; 1616bdcf26aSChristoph Hellwig if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp)) 1626bdcf26aSChristoph Hellwig return false; 1636bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(cur_rec(cur))) 1646bdcf26aSChristoph Hellwig return false; 1656bdcf26aSChristoph Hellwig return true; 1666bdcf26aSChristoph Hellwig } 1676bdcf26aSChristoph Hellwig 1686bdcf26aSChristoph Hellwig static void * 1696bdcf26aSChristoph Hellwig xfs_iext_find_first_leaf( 1706bdcf26aSChristoph Hellwig struct xfs_ifork *ifp) 1716bdcf26aSChristoph Hellwig { 1726bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root; 1736bdcf26aSChristoph Hellwig int height; 1746bdcf26aSChristoph Hellwig 1756bdcf26aSChristoph Hellwig if (!ifp->if_height) 1766bdcf26aSChristoph Hellwig return NULL; 1776bdcf26aSChristoph Hellwig 1786bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > 1; height--) { 1796bdcf26aSChristoph Hellwig node = node->ptrs[0]; 1806bdcf26aSChristoph Hellwig ASSERT(node); 1816bdcf26aSChristoph Hellwig } 1826bdcf26aSChristoph Hellwig 1836bdcf26aSChristoph Hellwig return node; 1846bdcf26aSChristoph Hellwig } 1856bdcf26aSChristoph Hellwig 1866bdcf26aSChristoph Hellwig static void * 1876bdcf26aSChristoph Hellwig xfs_iext_find_last_leaf( 1886bdcf26aSChristoph Hellwig struct xfs_ifork *ifp) 1896bdcf26aSChristoph Hellwig { 1906bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root; 1916bdcf26aSChristoph Hellwig int height, i; 1926bdcf26aSChristoph Hellwig 1936bdcf26aSChristoph Hellwig if (!ifp->if_height) 1946bdcf26aSChristoph Hellwig return NULL; 1956bdcf26aSChristoph Hellwig 1966bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > 1; height--) { 1976bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++) 1986bdcf26aSChristoph Hellwig if (!node->ptrs[i]) 1996bdcf26aSChristoph Hellwig break; 2006bdcf26aSChristoph Hellwig node = node->ptrs[i - 1]; 2016bdcf26aSChristoph Hellwig ASSERT(node); 2026bdcf26aSChristoph Hellwig } 2036bdcf26aSChristoph Hellwig 2046bdcf26aSChristoph Hellwig return node; 2056bdcf26aSChristoph Hellwig } 2066bdcf26aSChristoph Hellwig 2076bdcf26aSChristoph Hellwig void 2086bdcf26aSChristoph Hellwig xfs_iext_first( 2096bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 2106bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur) 2116bdcf26aSChristoph Hellwig { 2126bdcf26aSChristoph Hellwig cur->pos = 0; 2136bdcf26aSChristoph Hellwig cur->leaf = xfs_iext_find_first_leaf(ifp); 2146bdcf26aSChristoph Hellwig } 2156bdcf26aSChristoph Hellwig 2166bdcf26aSChristoph Hellwig void 2176bdcf26aSChristoph Hellwig xfs_iext_last( 2186bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 2196bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur) 2206bdcf26aSChristoph Hellwig { 2216bdcf26aSChristoph Hellwig int i; 2226bdcf26aSChristoph Hellwig 2236bdcf26aSChristoph Hellwig cur->leaf = xfs_iext_find_last_leaf(ifp); 2246bdcf26aSChristoph Hellwig if (!cur->leaf) { 2256bdcf26aSChristoph Hellwig cur->pos = 0; 2266bdcf26aSChristoph Hellwig return; 2276bdcf26aSChristoph Hellwig } 2286bdcf26aSChristoph Hellwig 2296bdcf26aSChristoph Hellwig for (i = 1; i < xfs_iext_max_recs(ifp); i++) { 2306bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(&cur->leaf->recs[i])) 2316bdcf26aSChristoph Hellwig break; 2326bdcf26aSChristoph Hellwig } 2336bdcf26aSChristoph Hellwig cur->pos = i - 1; 2346bdcf26aSChristoph Hellwig } 2356bdcf26aSChristoph Hellwig 2366bdcf26aSChristoph Hellwig void 2376bdcf26aSChristoph Hellwig xfs_iext_next( 2386bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 2396bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur) 2406bdcf26aSChristoph Hellwig { 2416bdcf26aSChristoph Hellwig if (!cur->leaf) { 2426bdcf26aSChristoph Hellwig ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF); 2436bdcf26aSChristoph Hellwig xfs_iext_first(ifp, cur); 2446bdcf26aSChristoph Hellwig return; 2456bdcf26aSChristoph Hellwig } 2466bdcf26aSChristoph Hellwig 2476bdcf26aSChristoph Hellwig ASSERT(cur->pos >= 0); 2486bdcf26aSChristoph Hellwig ASSERT(cur->pos < xfs_iext_max_recs(ifp)); 2496bdcf26aSChristoph Hellwig 2506bdcf26aSChristoph Hellwig cur->pos++; 2516bdcf26aSChristoph Hellwig if (ifp->if_height > 1 && !xfs_iext_valid(ifp, cur) && 2526bdcf26aSChristoph Hellwig cur->leaf->next) { 2536bdcf26aSChristoph Hellwig cur->leaf = cur->leaf->next; 2546bdcf26aSChristoph Hellwig cur->pos = 0; 2556bdcf26aSChristoph Hellwig } 2566bdcf26aSChristoph Hellwig } 2576bdcf26aSChristoph Hellwig 2586bdcf26aSChristoph Hellwig void 2596bdcf26aSChristoph Hellwig xfs_iext_prev( 2606bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 2616bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur) 2626bdcf26aSChristoph Hellwig { 2636bdcf26aSChristoph Hellwig if (!cur->leaf) { 2646bdcf26aSChristoph Hellwig ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF); 2656bdcf26aSChristoph Hellwig xfs_iext_last(ifp, cur); 2666bdcf26aSChristoph Hellwig return; 2676bdcf26aSChristoph Hellwig } 2686bdcf26aSChristoph Hellwig 2696bdcf26aSChristoph Hellwig ASSERT(cur->pos >= 0); 2706bdcf26aSChristoph Hellwig ASSERT(cur->pos <= RECS_PER_LEAF); 2716bdcf26aSChristoph Hellwig 2726bdcf26aSChristoph Hellwig recurse: 2736bdcf26aSChristoph Hellwig do { 2746bdcf26aSChristoph Hellwig cur->pos--; 2756bdcf26aSChristoph Hellwig if (xfs_iext_valid(ifp, cur)) 2766bdcf26aSChristoph Hellwig return; 2776bdcf26aSChristoph Hellwig } while (cur->pos > 0); 2786bdcf26aSChristoph Hellwig 2796bdcf26aSChristoph Hellwig if (ifp->if_height > 1 && cur->leaf->prev) { 2806bdcf26aSChristoph Hellwig cur->leaf = cur->leaf->prev; 2816bdcf26aSChristoph Hellwig cur->pos = RECS_PER_LEAF; 2826bdcf26aSChristoph Hellwig goto recurse; 2836bdcf26aSChristoph Hellwig } 2846bdcf26aSChristoph Hellwig } 2856bdcf26aSChristoph Hellwig 2866bdcf26aSChristoph Hellwig static inline int 2876bdcf26aSChristoph Hellwig xfs_iext_key_cmp( 2886bdcf26aSChristoph Hellwig struct xfs_iext_node *node, 2896bdcf26aSChristoph Hellwig int n, 2906bdcf26aSChristoph Hellwig xfs_fileoff_t offset) 2916bdcf26aSChristoph Hellwig { 2926bdcf26aSChristoph Hellwig if (node->keys[n] > offset) 2936bdcf26aSChristoph Hellwig return 1; 2946bdcf26aSChristoph Hellwig if (node->keys[n] < offset) 2956bdcf26aSChristoph Hellwig return -1; 2966bdcf26aSChristoph Hellwig return 0; 2976bdcf26aSChristoph Hellwig } 2986bdcf26aSChristoph Hellwig 2996bdcf26aSChristoph Hellwig static inline int 3006bdcf26aSChristoph Hellwig xfs_iext_rec_cmp( 3016bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec, 3026bdcf26aSChristoph Hellwig xfs_fileoff_t offset) 3036bdcf26aSChristoph Hellwig { 3046bdcf26aSChristoph Hellwig uint64_t rec_offset = rec->lo & XFS_IEXT_STARTOFF_MASK; 3056bdcf26aSChristoph Hellwig u32 rec_len = rec->hi & XFS_IEXT_LENGTH_MASK; 3066bdcf26aSChristoph Hellwig 3076bdcf26aSChristoph Hellwig if (rec_offset > offset) 3086bdcf26aSChristoph Hellwig return 1; 3096bdcf26aSChristoph Hellwig if (rec_offset + rec_len <= offset) 3106bdcf26aSChristoph Hellwig return -1; 3116bdcf26aSChristoph Hellwig return 0; 3126bdcf26aSChristoph Hellwig } 3136bdcf26aSChristoph Hellwig 3146bdcf26aSChristoph Hellwig static void * 3156bdcf26aSChristoph Hellwig xfs_iext_find_level( 3166bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 3176bdcf26aSChristoph Hellwig xfs_fileoff_t offset, 3186bdcf26aSChristoph Hellwig int level) 3196bdcf26aSChristoph Hellwig { 3206bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root; 3216bdcf26aSChristoph Hellwig int height, i; 3226bdcf26aSChristoph Hellwig 3236bdcf26aSChristoph Hellwig if (!ifp->if_height) 3246bdcf26aSChristoph Hellwig return NULL; 3256bdcf26aSChristoph Hellwig 3266bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > level; height--) { 3276bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++) 3286bdcf26aSChristoph Hellwig if (xfs_iext_key_cmp(node, i, offset) > 0) 3296bdcf26aSChristoph Hellwig break; 3306bdcf26aSChristoph Hellwig 3316bdcf26aSChristoph Hellwig node = node->ptrs[i - 1]; 3326bdcf26aSChristoph Hellwig if (!node) 3336bdcf26aSChristoph Hellwig break; 3346bdcf26aSChristoph Hellwig } 3356bdcf26aSChristoph Hellwig 3366bdcf26aSChristoph Hellwig return node; 3376bdcf26aSChristoph Hellwig } 3386bdcf26aSChristoph Hellwig 3396bdcf26aSChristoph Hellwig static int 3406bdcf26aSChristoph Hellwig xfs_iext_node_pos( 3416bdcf26aSChristoph Hellwig struct xfs_iext_node *node, 3426bdcf26aSChristoph Hellwig xfs_fileoff_t offset) 3436bdcf26aSChristoph Hellwig { 3446bdcf26aSChristoph Hellwig int i; 3456bdcf26aSChristoph Hellwig 3466bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++) { 3476bdcf26aSChristoph Hellwig if (xfs_iext_key_cmp(node, i, offset) > 0) 3486bdcf26aSChristoph Hellwig break; 3496bdcf26aSChristoph Hellwig } 3506bdcf26aSChristoph Hellwig 3516bdcf26aSChristoph Hellwig return i - 1; 3526bdcf26aSChristoph Hellwig } 3536bdcf26aSChristoph Hellwig 3546bdcf26aSChristoph Hellwig static int 3556bdcf26aSChristoph Hellwig xfs_iext_node_insert_pos( 3566bdcf26aSChristoph Hellwig struct xfs_iext_node *node, 3576bdcf26aSChristoph Hellwig xfs_fileoff_t offset) 3586bdcf26aSChristoph Hellwig { 3596bdcf26aSChristoph Hellwig int i; 3606bdcf26aSChristoph Hellwig 3616bdcf26aSChristoph Hellwig for (i = 0; i < KEYS_PER_NODE; i++) { 3626bdcf26aSChristoph Hellwig if (xfs_iext_key_cmp(node, i, offset) > 0) 3636bdcf26aSChristoph Hellwig return i; 3646bdcf26aSChristoph Hellwig } 3656bdcf26aSChristoph Hellwig 3666bdcf26aSChristoph Hellwig return KEYS_PER_NODE; 3676bdcf26aSChristoph Hellwig } 3686bdcf26aSChristoph Hellwig 3696bdcf26aSChristoph Hellwig static int 3706bdcf26aSChristoph Hellwig xfs_iext_node_nr_entries( 3716bdcf26aSChristoph Hellwig struct xfs_iext_node *node, 3726bdcf26aSChristoph Hellwig int start) 3736bdcf26aSChristoph Hellwig { 3746bdcf26aSChristoph Hellwig int i; 3756bdcf26aSChristoph Hellwig 3766bdcf26aSChristoph Hellwig for (i = start; i < KEYS_PER_NODE; i++) { 3776bdcf26aSChristoph Hellwig if (node->keys[i] == XFS_IEXT_KEY_INVALID) 3786bdcf26aSChristoph Hellwig break; 3796bdcf26aSChristoph Hellwig } 3806bdcf26aSChristoph Hellwig 3816bdcf26aSChristoph Hellwig return i; 3826bdcf26aSChristoph Hellwig } 3836bdcf26aSChristoph Hellwig 3846bdcf26aSChristoph Hellwig static int 3856bdcf26aSChristoph Hellwig xfs_iext_leaf_nr_entries( 3866bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 3876bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf, 3886bdcf26aSChristoph Hellwig int start) 3896bdcf26aSChristoph Hellwig { 3906bdcf26aSChristoph Hellwig int i; 3916bdcf26aSChristoph Hellwig 3926bdcf26aSChristoph Hellwig for (i = start; i < xfs_iext_max_recs(ifp); i++) { 3936bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(&leaf->recs[i])) 3946bdcf26aSChristoph Hellwig break; 3956bdcf26aSChristoph Hellwig } 3966bdcf26aSChristoph Hellwig 3976bdcf26aSChristoph Hellwig return i; 3986bdcf26aSChristoph Hellwig } 3996bdcf26aSChristoph Hellwig 4006bdcf26aSChristoph Hellwig static inline uint64_t 4016bdcf26aSChristoph Hellwig xfs_iext_leaf_key( 4026bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf, 4036bdcf26aSChristoph Hellwig int n) 4046bdcf26aSChristoph Hellwig { 4056bdcf26aSChristoph Hellwig return leaf->recs[n].lo & XFS_IEXT_STARTOFF_MASK; 4066bdcf26aSChristoph Hellwig } 4076bdcf26aSChristoph Hellwig 4086bdcf26aSChristoph Hellwig static void 4096bdcf26aSChristoph Hellwig xfs_iext_grow( 4106bdcf26aSChristoph Hellwig struct xfs_ifork *ifp) 4116bdcf26aSChristoph Hellwig { 4126bdcf26aSChristoph Hellwig struct xfs_iext_node *node = kmem_zalloc(NODE_SIZE, KM_NOFS); 4136bdcf26aSChristoph Hellwig int i; 4146bdcf26aSChristoph Hellwig 4156bdcf26aSChristoph Hellwig if (ifp->if_height == 1) { 4166bdcf26aSChristoph Hellwig struct xfs_iext_leaf *prev = ifp->if_u1.if_root; 4176bdcf26aSChristoph Hellwig 4186bdcf26aSChristoph Hellwig node->keys[0] = xfs_iext_leaf_key(prev, 0); 4196bdcf26aSChristoph Hellwig node->ptrs[0] = prev; 4206bdcf26aSChristoph Hellwig } else { 4216bdcf26aSChristoph Hellwig struct xfs_iext_node *prev = ifp->if_u1.if_root; 4226bdcf26aSChristoph Hellwig 4236bdcf26aSChristoph Hellwig ASSERT(ifp->if_height > 1); 4246bdcf26aSChristoph Hellwig 4256bdcf26aSChristoph Hellwig node->keys[0] = prev->keys[0]; 4266bdcf26aSChristoph Hellwig node->ptrs[0] = prev; 4276bdcf26aSChristoph Hellwig } 4286bdcf26aSChristoph Hellwig 4296bdcf26aSChristoph Hellwig for (i = 1; i < KEYS_PER_NODE; i++) 4306bdcf26aSChristoph Hellwig node->keys[i] = XFS_IEXT_KEY_INVALID; 4316bdcf26aSChristoph Hellwig 4326bdcf26aSChristoph Hellwig ifp->if_u1.if_root = node; 4336bdcf26aSChristoph Hellwig ifp->if_height++; 4346bdcf26aSChristoph Hellwig } 4356bdcf26aSChristoph Hellwig 4366bdcf26aSChristoph Hellwig static void 4376bdcf26aSChristoph Hellwig xfs_iext_update_node( 4386bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 4396bdcf26aSChristoph Hellwig xfs_fileoff_t old_offset, 4406bdcf26aSChristoph Hellwig xfs_fileoff_t new_offset, 4416bdcf26aSChristoph Hellwig int level, 4426bdcf26aSChristoph Hellwig void *ptr) 4436bdcf26aSChristoph Hellwig { 4446bdcf26aSChristoph Hellwig struct xfs_iext_node *node = ifp->if_u1.if_root; 4456bdcf26aSChristoph Hellwig int height, i; 4466bdcf26aSChristoph Hellwig 4476bdcf26aSChristoph Hellwig for (height = ifp->if_height; height > level; height--) { 4486bdcf26aSChristoph Hellwig for (i = 0; i < KEYS_PER_NODE; i++) { 4496bdcf26aSChristoph Hellwig if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0) 4506bdcf26aSChristoph Hellwig break; 4516bdcf26aSChristoph Hellwig if (node->keys[i] == old_offset) 4526bdcf26aSChristoph Hellwig node->keys[i] = new_offset; 4536bdcf26aSChristoph Hellwig } 4546bdcf26aSChristoph Hellwig node = node->ptrs[i - 1]; 4556bdcf26aSChristoph Hellwig ASSERT(node); 4566bdcf26aSChristoph Hellwig } 4576bdcf26aSChristoph Hellwig 4586bdcf26aSChristoph Hellwig ASSERT(node == ptr); 4596bdcf26aSChristoph Hellwig } 4606bdcf26aSChristoph Hellwig 4616bdcf26aSChristoph Hellwig static struct xfs_iext_node * 4626bdcf26aSChristoph Hellwig xfs_iext_split_node( 4636bdcf26aSChristoph Hellwig struct xfs_iext_node **nodep, 4646bdcf26aSChristoph Hellwig int *pos, 4656bdcf26aSChristoph Hellwig int *nr_entries) 4666bdcf26aSChristoph Hellwig { 4676bdcf26aSChristoph Hellwig struct xfs_iext_node *node = *nodep; 4686bdcf26aSChristoph Hellwig struct xfs_iext_node *new = kmem_zalloc(NODE_SIZE, KM_NOFS); 4696bdcf26aSChristoph Hellwig const int nr_move = KEYS_PER_NODE / 2; 4706bdcf26aSChristoph Hellwig int nr_keep = nr_move + (KEYS_PER_NODE & 1); 4716bdcf26aSChristoph Hellwig int i = 0; 4726bdcf26aSChristoph Hellwig 4736bdcf26aSChristoph Hellwig /* for sequential append operations just spill over into the new node */ 4746bdcf26aSChristoph Hellwig if (*pos == KEYS_PER_NODE) { 4756bdcf26aSChristoph Hellwig *nodep = new; 4766bdcf26aSChristoph Hellwig *pos = 0; 4776bdcf26aSChristoph Hellwig *nr_entries = 0; 4786bdcf26aSChristoph Hellwig goto done; 4796bdcf26aSChristoph Hellwig } 4806bdcf26aSChristoph Hellwig 4816bdcf26aSChristoph Hellwig 4826bdcf26aSChristoph Hellwig for (i = 0; i < nr_move; i++) { 4836bdcf26aSChristoph Hellwig new->keys[i] = node->keys[nr_keep + i]; 4846bdcf26aSChristoph Hellwig new->ptrs[i] = node->ptrs[nr_keep + i]; 4856bdcf26aSChristoph Hellwig 4866bdcf26aSChristoph Hellwig node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID; 4876bdcf26aSChristoph Hellwig node->ptrs[nr_keep + i] = NULL; 4886bdcf26aSChristoph Hellwig } 4896bdcf26aSChristoph Hellwig 4906bdcf26aSChristoph Hellwig if (*pos >= nr_keep) { 4916bdcf26aSChristoph Hellwig *nodep = new; 4926bdcf26aSChristoph Hellwig *pos -= nr_keep; 4936bdcf26aSChristoph Hellwig *nr_entries = nr_move; 4946bdcf26aSChristoph Hellwig } else { 4956bdcf26aSChristoph Hellwig *nr_entries = nr_keep; 4966bdcf26aSChristoph Hellwig } 4976bdcf26aSChristoph Hellwig done: 4986bdcf26aSChristoph Hellwig for (; i < KEYS_PER_NODE; i++) 4996bdcf26aSChristoph Hellwig new->keys[i] = XFS_IEXT_KEY_INVALID; 5006bdcf26aSChristoph Hellwig return new; 5016bdcf26aSChristoph Hellwig } 5026bdcf26aSChristoph Hellwig 5036bdcf26aSChristoph Hellwig static void 5046bdcf26aSChristoph Hellwig xfs_iext_insert_node( 5056bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 5066bdcf26aSChristoph Hellwig uint64_t offset, 5076bdcf26aSChristoph Hellwig void *ptr, 5086bdcf26aSChristoph Hellwig int level) 5096bdcf26aSChristoph Hellwig { 5106bdcf26aSChristoph Hellwig struct xfs_iext_node *node, *new; 5116bdcf26aSChristoph Hellwig int i, pos, nr_entries; 5126bdcf26aSChristoph Hellwig 5136bdcf26aSChristoph Hellwig again: 5146bdcf26aSChristoph Hellwig if (ifp->if_height < level) 5156bdcf26aSChristoph Hellwig xfs_iext_grow(ifp); 5166bdcf26aSChristoph Hellwig 5176bdcf26aSChristoph Hellwig new = NULL; 5186bdcf26aSChristoph Hellwig node = xfs_iext_find_level(ifp, offset, level); 5196bdcf26aSChristoph Hellwig pos = xfs_iext_node_insert_pos(node, offset); 5206bdcf26aSChristoph Hellwig nr_entries = xfs_iext_node_nr_entries(node, pos); 5216bdcf26aSChristoph Hellwig 5226bdcf26aSChristoph Hellwig ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0); 5236bdcf26aSChristoph Hellwig ASSERT(nr_entries <= KEYS_PER_NODE); 5246bdcf26aSChristoph Hellwig 5256bdcf26aSChristoph Hellwig if (nr_entries == KEYS_PER_NODE) 5266bdcf26aSChristoph Hellwig new = xfs_iext_split_node(&node, &pos, &nr_entries); 5276bdcf26aSChristoph Hellwig 5286bdcf26aSChristoph Hellwig if (node != new && pos == 0 && nr_entries > 0) 5296bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, node->keys[0], offset, level, node); 5306bdcf26aSChristoph Hellwig 5316bdcf26aSChristoph Hellwig for (i = nr_entries; i > pos; i--) { 5326bdcf26aSChristoph Hellwig node->keys[i] = node->keys[i - 1]; 5336bdcf26aSChristoph Hellwig node->ptrs[i] = node->ptrs[i - 1]; 5346bdcf26aSChristoph Hellwig } 5356bdcf26aSChristoph Hellwig node->keys[pos] = offset; 5366bdcf26aSChristoph Hellwig node->ptrs[pos] = ptr; 5376bdcf26aSChristoph Hellwig 5386bdcf26aSChristoph Hellwig if (new) { 5396bdcf26aSChristoph Hellwig offset = new->keys[0]; 5406bdcf26aSChristoph Hellwig ptr = new; 5416bdcf26aSChristoph Hellwig level++; 5426bdcf26aSChristoph Hellwig goto again; 5436bdcf26aSChristoph Hellwig } 5446bdcf26aSChristoph Hellwig } 5456bdcf26aSChristoph Hellwig 5466bdcf26aSChristoph Hellwig static struct xfs_iext_leaf * 5476bdcf26aSChristoph Hellwig xfs_iext_split_leaf( 5486bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur, 5496bdcf26aSChristoph Hellwig int *nr_entries) 5506bdcf26aSChristoph Hellwig { 5516bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf = cur->leaf; 5526bdcf26aSChristoph Hellwig struct xfs_iext_leaf *new = kmem_zalloc(NODE_SIZE, KM_NOFS); 5536bdcf26aSChristoph Hellwig const int nr_move = RECS_PER_LEAF / 2; 5546bdcf26aSChristoph Hellwig int nr_keep = nr_move + (RECS_PER_LEAF & 1); 5556bdcf26aSChristoph Hellwig int i; 5566bdcf26aSChristoph Hellwig 5576bdcf26aSChristoph Hellwig /* for sequential append operations just spill over into the new node */ 55843d193aaSChristoph Hellwig if (cur->pos == RECS_PER_LEAF) { 5596bdcf26aSChristoph Hellwig cur->leaf = new; 5606bdcf26aSChristoph Hellwig cur->pos = 0; 5616bdcf26aSChristoph Hellwig *nr_entries = 0; 5626bdcf26aSChristoph Hellwig goto done; 5636bdcf26aSChristoph Hellwig } 5646bdcf26aSChristoph Hellwig 5656bdcf26aSChristoph Hellwig for (i = 0; i < nr_move; i++) { 5666bdcf26aSChristoph Hellwig new->recs[i] = leaf->recs[nr_keep + i]; 5676bdcf26aSChristoph Hellwig xfs_iext_rec_clear(&leaf->recs[nr_keep + i]); 5686bdcf26aSChristoph Hellwig } 5696bdcf26aSChristoph Hellwig 5706bdcf26aSChristoph Hellwig if (cur->pos >= nr_keep) { 5716bdcf26aSChristoph Hellwig cur->leaf = new; 5726bdcf26aSChristoph Hellwig cur->pos -= nr_keep; 5736bdcf26aSChristoph Hellwig *nr_entries = nr_move; 5746bdcf26aSChristoph Hellwig } else { 5756bdcf26aSChristoph Hellwig *nr_entries = nr_keep; 5766bdcf26aSChristoph Hellwig } 5776bdcf26aSChristoph Hellwig done: 5786bdcf26aSChristoph Hellwig if (leaf->next) 5796bdcf26aSChristoph Hellwig leaf->next->prev = new; 5806bdcf26aSChristoph Hellwig new->next = leaf->next; 5816bdcf26aSChristoph Hellwig new->prev = leaf; 5826bdcf26aSChristoph Hellwig leaf->next = new; 5836bdcf26aSChristoph Hellwig return new; 5846bdcf26aSChristoph Hellwig } 5856bdcf26aSChristoph Hellwig 5866bdcf26aSChristoph Hellwig static void 5876bdcf26aSChristoph Hellwig xfs_iext_alloc_root( 5886bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 5896bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur) 5906bdcf26aSChristoph Hellwig { 5916bdcf26aSChristoph Hellwig ASSERT(ifp->if_bytes == 0); 5926bdcf26aSChristoph Hellwig 5936bdcf26aSChristoph Hellwig ifp->if_u1.if_root = kmem_zalloc(sizeof(struct xfs_iext_rec), KM_NOFS); 5946bdcf26aSChristoph Hellwig ifp->if_height = 1; 5956bdcf26aSChristoph Hellwig 5966bdcf26aSChristoph Hellwig /* now that we have a node step into it */ 5976bdcf26aSChristoph Hellwig cur->leaf = ifp->if_u1.if_root; 5986bdcf26aSChristoph Hellwig cur->pos = 0; 5996bdcf26aSChristoph Hellwig } 6006bdcf26aSChristoph Hellwig 6016bdcf26aSChristoph Hellwig static void 6026bdcf26aSChristoph Hellwig xfs_iext_realloc_root( 6036bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 6046bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur) 6056bdcf26aSChristoph Hellwig { 6066bdcf26aSChristoph Hellwig size_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec); 6076bdcf26aSChristoph Hellwig void *new; 6086bdcf26aSChristoph Hellwig 6096bdcf26aSChristoph Hellwig /* account for the prev/next pointers */ 6106bdcf26aSChristoph Hellwig if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF) 6116bdcf26aSChristoph Hellwig new_size = NODE_SIZE; 6126bdcf26aSChristoph Hellwig 6136bdcf26aSChristoph Hellwig new = kmem_realloc(ifp->if_u1.if_root, new_size, KM_NOFS); 6146bdcf26aSChristoph Hellwig memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes); 6156bdcf26aSChristoph Hellwig ifp->if_u1.if_root = new; 6166bdcf26aSChristoph Hellwig cur->leaf = new; 6176bdcf26aSChristoph Hellwig } 6186bdcf26aSChristoph Hellwig 6190254c2f2SChristoph Hellwig void 6200254c2f2SChristoph Hellwig xfs_iext_insert( 6210254c2f2SChristoph Hellwig struct xfs_inode *ip, 6226bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur, 6230254c2f2SChristoph Hellwig struct xfs_bmbt_irec *irec, 6240254c2f2SChristoph Hellwig int state) 6256bdcf26aSChristoph Hellwig { 6260254c2f2SChristoph Hellwig struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); 6276bdcf26aSChristoph Hellwig xfs_fileoff_t offset = irec->br_startoff; 6286bdcf26aSChristoph Hellwig struct xfs_iext_leaf *new = NULL; 6296bdcf26aSChristoph Hellwig int nr_entries, i; 6306bdcf26aSChristoph Hellwig 6310254c2f2SChristoph Hellwig trace_xfs_iext_insert(ip, cur, state, _RET_IP_); 6320254c2f2SChristoph Hellwig 6336bdcf26aSChristoph Hellwig if (ifp->if_height == 0) 6346bdcf26aSChristoph Hellwig xfs_iext_alloc_root(ifp, cur); 6356bdcf26aSChristoph Hellwig else if (ifp->if_height == 1) 6366bdcf26aSChristoph Hellwig xfs_iext_realloc_root(ifp, cur); 6376bdcf26aSChristoph Hellwig 6386bdcf26aSChristoph Hellwig nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos); 6396bdcf26aSChristoph Hellwig ASSERT(nr_entries <= RECS_PER_LEAF); 6406bdcf26aSChristoph Hellwig ASSERT(cur->pos >= nr_entries || 6416bdcf26aSChristoph Hellwig xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0); 6426bdcf26aSChristoph Hellwig 6436bdcf26aSChristoph Hellwig if (nr_entries == RECS_PER_LEAF) 6446bdcf26aSChristoph Hellwig new = xfs_iext_split_leaf(cur, &nr_entries); 6456bdcf26aSChristoph Hellwig 6466bdcf26aSChristoph Hellwig if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) { 6476bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0), 6486bdcf26aSChristoph Hellwig offset, 1, cur->leaf); 6496bdcf26aSChristoph Hellwig } 6506bdcf26aSChristoph Hellwig 6516bdcf26aSChristoph Hellwig for (i = nr_entries; i > cur->pos; i--) 6526bdcf26aSChristoph Hellwig cur->leaf->recs[i] = cur->leaf->recs[i - 1]; 6536bdcf26aSChristoph Hellwig xfs_iext_set(cur_rec(cur), irec); 6546bdcf26aSChristoph Hellwig ifp->if_bytes += sizeof(struct xfs_iext_rec); 6556bdcf26aSChristoph Hellwig 6566bdcf26aSChristoph Hellwig if (new) 6576bdcf26aSChristoph Hellwig xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2); 6586bdcf26aSChristoph Hellwig } 6596bdcf26aSChristoph Hellwig 6606bdcf26aSChristoph Hellwig static struct xfs_iext_node * 6616bdcf26aSChristoph Hellwig xfs_iext_rebalance_node( 6626bdcf26aSChristoph Hellwig struct xfs_iext_node *parent, 6636bdcf26aSChristoph Hellwig int *pos, 6646bdcf26aSChristoph Hellwig struct xfs_iext_node *node, 6656bdcf26aSChristoph Hellwig int nr_entries) 6666bdcf26aSChristoph Hellwig { 6676bdcf26aSChristoph Hellwig if (nr_entries == 0) 6686bdcf26aSChristoph Hellwig return node; 6696bdcf26aSChristoph Hellwig 6706bdcf26aSChristoph Hellwig if (*pos > 0) { 6716bdcf26aSChristoph Hellwig struct xfs_iext_node *prev = parent->ptrs[*pos - 1]; 6726bdcf26aSChristoph Hellwig int nr_prev = xfs_iext_node_nr_entries(prev, 0), i; 6736bdcf26aSChristoph Hellwig 6746bdcf26aSChristoph Hellwig if (nr_prev + nr_entries <= KEYS_PER_NODE) { 6756bdcf26aSChristoph Hellwig for (i = 0; i < nr_entries; i++) { 6766bdcf26aSChristoph Hellwig prev->keys[nr_prev + i] = node->keys[i]; 6776bdcf26aSChristoph Hellwig prev->ptrs[nr_prev + i] = node->ptrs[i]; 6786bdcf26aSChristoph Hellwig } 6796bdcf26aSChristoph Hellwig return node; 6806bdcf26aSChristoph Hellwig } 6816bdcf26aSChristoph Hellwig } 6826bdcf26aSChristoph Hellwig 6836bdcf26aSChristoph Hellwig if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) { 6846bdcf26aSChristoph Hellwig struct xfs_iext_node *next = parent->ptrs[*pos + 1]; 6856bdcf26aSChristoph Hellwig int nr_next = xfs_iext_node_nr_entries(next, 0), i; 6866bdcf26aSChristoph Hellwig 6876bdcf26aSChristoph Hellwig if (nr_entries + nr_next <= KEYS_PER_NODE) { 6886bdcf26aSChristoph Hellwig for (i = 0; i < nr_next; i++) { 6896bdcf26aSChristoph Hellwig node->keys[nr_entries + i] = next->keys[i]; 6906bdcf26aSChristoph Hellwig node->ptrs[nr_entries + i] = next->ptrs[i]; 6916bdcf26aSChristoph Hellwig } 6926bdcf26aSChristoph Hellwig 6936bdcf26aSChristoph Hellwig ++*pos; 6946bdcf26aSChristoph Hellwig return next; 6956bdcf26aSChristoph Hellwig } 6966bdcf26aSChristoph Hellwig } 6976bdcf26aSChristoph Hellwig 6986bdcf26aSChristoph Hellwig return NULL; 6996bdcf26aSChristoph Hellwig } 7006bdcf26aSChristoph Hellwig 7016bdcf26aSChristoph Hellwig static void 7026bdcf26aSChristoph Hellwig xfs_iext_remove_node( 7036bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 7046bdcf26aSChristoph Hellwig xfs_fileoff_t offset, 7056bdcf26aSChristoph Hellwig void *victim) 7066bdcf26aSChristoph Hellwig { 7076bdcf26aSChristoph Hellwig struct xfs_iext_node *node, *parent; 7086bdcf26aSChristoph Hellwig int level = 2, pos, nr_entries, i; 7096bdcf26aSChristoph Hellwig 7106bdcf26aSChristoph Hellwig ASSERT(level <= ifp->if_height); 7116bdcf26aSChristoph Hellwig node = xfs_iext_find_level(ifp, offset, level); 7126bdcf26aSChristoph Hellwig pos = xfs_iext_node_pos(node, offset); 7136bdcf26aSChristoph Hellwig again: 7146bdcf26aSChristoph Hellwig ASSERT(node->ptrs[pos]); 7156bdcf26aSChristoph Hellwig ASSERT(node->ptrs[pos] == victim); 7166bdcf26aSChristoph Hellwig kmem_free(victim); 7176bdcf26aSChristoph Hellwig 7186bdcf26aSChristoph Hellwig nr_entries = xfs_iext_node_nr_entries(node, pos) - 1; 7196bdcf26aSChristoph Hellwig offset = node->keys[0]; 7206bdcf26aSChristoph Hellwig for (i = pos; i < nr_entries; i++) { 7216bdcf26aSChristoph Hellwig node->keys[i] = node->keys[i + 1]; 7226bdcf26aSChristoph Hellwig node->ptrs[i] = node->ptrs[i + 1]; 7236bdcf26aSChristoph Hellwig } 7246bdcf26aSChristoph Hellwig node->keys[nr_entries] = XFS_IEXT_KEY_INVALID; 7256bdcf26aSChristoph Hellwig node->ptrs[nr_entries] = NULL; 7266bdcf26aSChristoph Hellwig 7276bdcf26aSChristoph Hellwig if (pos == 0 && nr_entries > 0) { 7286bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, offset, node->keys[0], level, 7296bdcf26aSChristoph Hellwig node); 7306bdcf26aSChristoph Hellwig offset = node->keys[0]; 7316bdcf26aSChristoph Hellwig } 7326bdcf26aSChristoph Hellwig 7336bdcf26aSChristoph Hellwig if (nr_entries >= KEYS_PER_NODE / 2) 7346bdcf26aSChristoph Hellwig return; 7356bdcf26aSChristoph Hellwig 7366bdcf26aSChristoph Hellwig if (level < ifp->if_height) { 7376bdcf26aSChristoph Hellwig level++; 7386bdcf26aSChristoph Hellwig parent = xfs_iext_find_level(ifp, offset, level); 7396bdcf26aSChristoph Hellwig pos = xfs_iext_node_pos(parent, offset); 7406bdcf26aSChristoph Hellwig 7416bdcf26aSChristoph Hellwig ASSERT(pos != KEYS_PER_NODE); 7426bdcf26aSChristoph Hellwig ASSERT(parent->ptrs[pos] == node); 7436bdcf26aSChristoph Hellwig 7446bdcf26aSChristoph Hellwig node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries); 7456bdcf26aSChristoph Hellwig if (node) { 7466bdcf26aSChristoph Hellwig offset = node->keys[0]; 7476bdcf26aSChristoph Hellwig victim = node; 7486bdcf26aSChristoph Hellwig node = parent; 7496bdcf26aSChristoph Hellwig goto again; 7506bdcf26aSChristoph Hellwig } 7516bdcf26aSChristoph Hellwig } else if (nr_entries == 1) { 7526bdcf26aSChristoph Hellwig ASSERT(node == ifp->if_u1.if_root); 7536bdcf26aSChristoph Hellwig ifp->if_u1.if_root = node->ptrs[0]; 7546bdcf26aSChristoph Hellwig ifp->if_height--; 7556bdcf26aSChristoph Hellwig kmem_free(node); 7566bdcf26aSChristoph Hellwig } 7576bdcf26aSChristoph Hellwig } 7586bdcf26aSChristoph Hellwig 7596bdcf26aSChristoph Hellwig static void 7606bdcf26aSChristoph Hellwig xfs_iext_rebalance_leaf( 7616bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 7626bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur, 7636bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf, 7646bdcf26aSChristoph Hellwig xfs_fileoff_t offset, 7656bdcf26aSChristoph Hellwig int fill) 7666bdcf26aSChristoph Hellwig { 7676bdcf26aSChristoph Hellwig if (leaf->prev) { 7686bdcf26aSChristoph Hellwig int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i; 7696bdcf26aSChristoph Hellwig 7706bdcf26aSChristoph Hellwig if (nr_prev + fill <= RECS_PER_LEAF) { 7716bdcf26aSChristoph Hellwig for (i = 0; i < fill; i++) 7726bdcf26aSChristoph Hellwig leaf->prev->recs[nr_prev + i] = leaf->recs[i]; 7736bdcf26aSChristoph Hellwig 7746bdcf26aSChristoph Hellwig if (cur->leaf == leaf) { 7756bdcf26aSChristoph Hellwig cur->leaf = leaf->prev; 7766bdcf26aSChristoph Hellwig cur->pos += nr_prev; 7776bdcf26aSChristoph Hellwig } 7786bdcf26aSChristoph Hellwig goto remove_node; 7796bdcf26aSChristoph Hellwig } 7806bdcf26aSChristoph Hellwig } 7816bdcf26aSChristoph Hellwig 7826bdcf26aSChristoph Hellwig if (leaf->next) { 7836bdcf26aSChristoph Hellwig int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i; 7846bdcf26aSChristoph Hellwig 7856bdcf26aSChristoph Hellwig if (fill + nr_next <= RECS_PER_LEAF) { 7866bdcf26aSChristoph Hellwig for (i = 0; i < nr_next; i++) 7876bdcf26aSChristoph Hellwig leaf->recs[fill + i] = leaf->next->recs[i]; 7886bdcf26aSChristoph Hellwig 7896bdcf26aSChristoph Hellwig if (cur->leaf == leaf->next) { 7906bdcf26aSChristoph Hellwig cur->leaf = leaf; 7916bdcf26aSChristoph Hellwig cur->pos += fill; 7926bdcf26aSChristoph Hellwig } 7936bdcf26aSChristoph Hellwig 7946bdcf26aSChristoph Hellwig offset = xfs_iext_leaf_key(leaf->next, 0); 7956bdcf26aSChristoph Hellwig leaf = leaf->next; 7966bdcf26aSChristoph Hellwig goto remove_node; 7976bdcf26aSChristoph Hellwig } 7986bdcf26aSChristoph Hellwig } 7996bdcf26aSChristoph Hellwig 8006bdcf26aSChristoph Hellwig return; 8016bdcf26aSChristoph Hellwig remove_node: 8026bdcf26aSChristoph Hellwig if (leaf->prev) 8036bdcf26aSChristoph Hellwig leaf->prev->next = leaf->next; 8046bdcf26aSChristoph Hellwig if (leaf->next) 8056bdcf26aSChristoph Hellwig leaf->next->prev = leaf->prev; 8066bdcf26aSChristoph Hellwig xfs_iext_remove_node(ifp, offset, leaf); 8076bdcf26aSChristoph Hellwig } 8086bdcf26aSChristoph Hellwig 8096bdcf26aSChristoph Hellwig static void 8106bdcf26aSChristoph Hellwig xfs_iext_free_last_leaf( 8116bdcf26aSChristoph Hellwig struct xfs_ifork *ifp) 8126bdcf26aSChristoph Hellwig { 8136bdcf26aSChristoph Hellwig ifp->if_u1.if_root = NULL; 8146bdcf26aSChristoph Hellwig ifp->if_height--; 8156bdcf26aSChristoph Hellwig kmem_free(ifp->if_u1.if_root); 8166bdcf26aSChristoph Hellwig } 8176bdcf26aSChristoph Hellwig 818c38ccf59SChristoph Hellwig void 819c38ccf59SChristoph Hellwig xfs_iext_remove( 820c38ccf59SChristoph Hellwig struct xfs_inode *ip, 821c38ccf59SChristoph Hellwig struct xfs_iext_cursor *cur, 822c38ccf59SChristoph Hellwig int state) 8236bdcf26aSChristoph Hellwig { 824c38ccf59SChristoph Hellwig struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); 8256bdcf26aSChristoph Hellwig struct xfs_iext_leaf *leaf = cur->leaf; 8266bdcf26aSChristoph Hellwig xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0); 8276bdcf26aSChristoph Hellwig int i, nr_entries; 8286bdcf26aSChristoph Hellwig 829c38ccf59SChristoph Hellwig trace_xfs_iext_remove(ip, cur, state, _RET_IP_); 830c38ccf59SChristoph Hellwig 8316bdcf26aSChristoph Hellwig ASSERT(ifp->if_height > 0); 8326bdcf26aSChristoph Hellwig ASSERT(ifp->if_u1.if_root != NULL); 8336bdcf26aSChristoph Hellwig ASSERT(xfs_iext_valid(ifp, cur)); 8346bdcf26aSChristoph Hellwig 8356bdcf26aSChristoph Hellwig nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1; 8366bdcf26aSChristoph Hellwig for (i = cur->pos; i < nr_entries; i++) 8376bdcf26aSChristoph Hellwig leaf->recs[i] = leaf->recs[i + 1]; 8386bdcf26aSChristoph Hellwig xfs_iext_rec_clear(&leaf->recs[nr_entries]); 8396bdcf26aSChristoph Hellwig ifp->if_bytes -= sizeof(struct xfs_iext_rec); 8406bdcf26aSChristoph Hellwig 8416bdcf26aSChristoph Hellwig if (cur->pos == 0 && nr_entries > 0) { 8426bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1, 8436bdcf26aSChristoph Hellwig leaf); 8446bdcf26aSChristoph Hellwig offset = xfs_iext_leaf_key(leaf, 0); 8456bdcf26aSChristoph Hellwig } else if (cur->pos == nr_entries) { 8466bdcf26aSChristoph Hellwig if (ifp->if_height > 1 && leaf->next) 8476bdcf26aSChristoph Hellwig cur->leaf = leaf->next; 8486bdcf26aSChristoph Hellwig else 8496bdcf26aSChristoph Hellwig cur->leaf = NULL; 8506bdcf26aSChristoph Hellwig cur->pos = 0; 8516bdcf26aSChristoph Hellwig } 8526bdcf26aSChristoph Hellwig 8536bdcf26aSChristoph Hellwig if (nr_entries >= RECS_PER_LEAF / 2) 8546bdcf26aSChristoph Hellwig return; 8556bdcf26aSChristoph Hellwig 8566bdcf26aSChristoph Hellwig if (ifp->if_height > 1) 8576bdcf26aSChristoph Hellwig xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries); 8586bdcf26aSChristoph Hellwig else if (nr_entries == 0) 8596bdcf26aSChristoph Hellwig xfs_iext_free_last_leaf(ifp); 8606bdcf26aSChristoph Hellwig } 8616bdcf26aSChristoph Hellwig 8626bdcf26aSChristoph Hellwig /* 8636bdcf26aSChristoph Hellwig * Lookup the extent covering bno. 8646bdcf26aSChristoph Hellwig * 8656bdcf26aSChristoph Hellwig * If there is an extent covering bno return the extent index, and store the 8666bdcf26aSChristoph Hellwig * expanded extent structure in *gotp, and the extent cursor in *cur. 8676bdcf26aSChristoph Hellwig * If there is no extent covering bno, but there is an extent after it (e.g. 8686bdcf26aSChristoph Hellwig * it lies in a hole) return that extent in *gotp and its cursor in *cur 8696bdcf26aSChristoph Hellwig * instead. 8706bdcf26aSChristoph Hellwig * If bno is beyond the last extent return false, and return an invalid 8716bdcf26aSChristoph Hellwig * cursor value. 8726bdcf26aSChristoph Hellwig */ 8736bdcf26aSChristoph Hellwig bool 8746bdcf26aSChristoph Hellwig xfs_iext_lookup_extent( 8756bdcf26aSChristoph Hellwig struct xfs_inode *ip, 8766bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 8776bdcf26aSChristoph Hellwig xfs_fileoff_t offset, 8786bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur, 8796bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *gotp) 8806bdcf26aSChristoph Hellwig { 8816bdcf26aSChristoph Hellwig XFS_STATS_INC(ip->i_mount, xs_look_exlist); 8826bdcf26aSChristoph Hellwig 8836bdcf26aSChristoph Hellwig cur->leaf = xfs_iext_find_level(ifp, offset, 1); 8846bdcf26aSChristoph Hellwig if (!cur->leaf) { 8856bdcf26aSChristoph Hellwig cur->pos = 0; 8866bdcf26aSChristoph Hellwig return false; 8876bdcf26aSChristoph Hellwig } 8886bdcf26aSChristoph Hellwig 8896bdcf26aSChristoph Hellwig for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) { 8906bdcf26aSChristoph Hellwig struct xfs_iext_rec *rec = cur_rec(cur); 8916bdcf26aSChristoph Hellwig 8926bdcf26aSChristoph Hellwig if (xfs_iext_rec_is_empty(rec)) 8936bdcf26aSChristoph Hellwig break; 8946bdcf26aSChristoph Hellwig if (xfs_iext_rec_cmp(rec, offset) >= 0) 8956bdcf26aSChristoph Hellwig goto found; 8966bdcf26aSChristoph Hellwig } 8976bdcf26aSChristoph Hellwig 8986bdcf26aSChristoph Hellwig /* Try looking in the next node for an entry > offset */ 8996bdcf26aSChristoph Hellwig if (ifp->if_height == 1 || !cur->leaf->next) 9006bdcf26aSChristoph Hellwig return false; 9016bdcf26aSChristoph Hellwig cur->leaf = cur->leaf->next; 9026bdcf26aSChristoph Hellwig cur->pos = 0; 9036bdcf26aSChristoph Hellwig if (!xfs_iext_valid(ifp, cur)) 9046bdcf26aSChristoph Hellwig return false; 9056bdcf26aSChristoph Hellwig found: 9066bdcf26aSChristoph Hellwig xfs_iext_get(gotp, cur_rec(cur)); 9076bdcf26aSChristoph Hellwig return true; 9086bdcf26aSChristoph Hellwig } 9096bdcf26aSChristoph Hellwig 9106bdcf26aSChristoph Hellwig /* 9116bdcf26aSChristoph Hellwig * Returns the last extent before end, and if this extent doesn't cover 9126bdcf26aSChristoph Hellwig * end, update end to the end of the extent. 9136bdcf26aSChristoph Hellwig */ 9146bdcf26aSChristoph Hellwig bool 9156bdcf26aSChristoph Hellwig xfs_iext_lookup_extent_before( 9166bdcf26aSChristoph Hellwig struct xfs_inode *ip, 9176bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 9186bdcf26aSChristoph Hellwig xfs_fileoff_t *end, 9196bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur, 9206bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *gotp) 9216bdcf26aSChristoph Hellwig { 9226bdcf26aSChristoph Hellwig /* could be optimized to not even look up the next on a match.. */ 9236bdcf26aSChristoph Hellwig if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) && 9246bdcf26aSChristoph Hellwig gotp->br_startoff <= *end - 1) 9256bdcf26aSChristoph Hellwig return true; 9266bdcf26aSChristoph Hellwig if (!xfs_iext_prev_extent(ifp, cur, gotp)) 9276bdcf26aSChristoph Hellwig return false; 9286bdcf26aSChristoph Hellwig *end = gotp->br_startoff + gotp->br_blockcount; 9296bdcf26aSChristoph Hellwig return true; 9306bdcf26aSChristoph Hellwig } 9316bdcf26aSChristoph Hellwig 9326bdcf26aSChristoph Hellwig void 9336bdcf26aSChristoph Hellwig xfs_iext_update_extent( 9346bdcf26aSChristoph Hellwig struct xfs_inode *ip, 9356bdcf26aSChristoph Hellwig int state, 9366bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur, 9376bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *new) 9386bdcf26aSChristoph Hellwig { 9396bdcf26aSChristoph Hellwig struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); 9406bdcf26aSChristoph Hellwig 9416bdcf26aSChristoph Hellwig if (cur->pos == 0) { 9426bdcf26aSChristoph Hellwig struct xfs_bmbt_irec old; 9436bdcf26aSChristoph Hellwig 9446bdcf26aSChristoph Hellwig xfs_iext_get(&old, cur_rec(cur)); 9456bdcf26aSChristoph Hellwig if (new->br_startoff != old.br_startoff) { 9466bdcf26aSChristoph Hellwig xfs_iext_update_node(ifp, old.br_startoff, 9476bdcf26aSChristoph Hellwig new->br_startoff, 1, cur->leaf); 9486bdcf26aSChristoph Hellwig } 9496bdcf26aSChristoph Hellwig } 9506bdcf26aSChristoph Hellwig 9516bdcf26aSChristoph Hellwig trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_); 9526bdcf26aSChristoph Hellwig xfs_iext_set(cur_rec(cur), new); 9536bdcf26aSChristoph Hellwig trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_); 9546bdcf26aSChristoph Hellwig } 9556bdcf26aSChristoph Hellwig 9566bdcf26aSChristoph Hellwig /* 9576bdcf26aSChristoph Hellwig * Return true if the cursor points at an extent and return the extent structure 9586bdcf26aSChristoph Hellwig * in gotp. Else return false. 9596bdcf26aSChristoph Hellwig */ 9606bdcf26aSChristoph Hellwig bool 9616bdcf26aSChristoph Hellwig xfs_iext_get_extent( 9626bdcf26aSChristoph Hellwig struct xfs_ifork *ifp, 9636bdcf26aSChristoph Hellwig struct xfs_iext_cursor *cur, 9646bdcf26aSChristoph Hellwig struct xfs_bmbt_irec *gotp) 9656bdcf26aSChristoph Hellwig { 9666bdcf26aSChristoph Hellwig if (!xfs_iext_valid(ifp, cur)) 9676bdcf26aSChristoph Hellwig return false; 9686bdcf26aSChristoph Hellwig xfs_iext_get(gotp, cur_rec(cur)); 9696bdcf26aSChristoph Hellwig return true; 9706bdcf26aSChristoph Hellwig } 9716bdcf26aSChristoph Hellwig 9726bdcf26aSChristoph Hellwig /* 9736bdcf26aSChristoph Hellwig * This is a recursive function, because of that we need to be extremely 9746bdcf26aSChristoph Hellwig * careful with stack usage. 9756bdcf26aSChristoph Hellwig */ 9766bdcf26aSChristoph Hellwig static void 9776bdcf26aSChristoph Hellwig xfs_iext_destroy_node( 9786bdcf26aSChristoph Hellwig struct xfs_iext_node *node, 9796bdcf26aSChristoph Hellwig int level) 9806bdcf26aSChristoph Hellwig { 9816bdcf26aSChristoph Hellwig int i; 9826bdcf26aSChristoph Hellwig 9836bdcf26aSChristoph Hellwig if (level > 1) { 9846bdcf26aSChristoph Hellwig for (i = 0; i < KEYS_PER_NODE; i++) { 9856bdcf26aSChristoph Hellwig if (node->keys[i] == XFS_IEXT_KEY_INVALID) 9866bdcf26aSChristoph Hellwig break; 9876bdcf26aSChristoph Hellwig xfs_iext_destroy_node(node->ptrs[i], level - 1); 9886bdcf26aSChristoph Hellwig } 9896bdcf26aSChristoph Hellwig } 9906bdcf26aSChristoph Hellwig 9916bdcf26aSChristoph Hellwig kmem_free(node); 9926bdcf26aSChristoph Hellwig } 9936bdcf26aSChristoph Hellwig 9946bdcf26aSChristoph Hellwig void 9956bdcf26aSChristoph Hellwig xfs_iext_destroy( 9966bdcf26aSChristoph Hellwig struct xfs_ifork *ifp) 9976bdcf26aSChristoph Hellwig { 9986bdcf26aSChristoph Hellwig xfs_iext_destroy_node(ifp->if_u1.if_root, ifp->if_height); 9996bdcf26aSChristoph Hellwig 10006bdcf26aSChristoph Hellwig ifp->if_bytes = 0; 10016bdcf26aSChristoph Hellwig ifp->if_height = 0; 10026bdcf26aSChristoph Hellwig ifp->if_u1.if_root = NULL; 10036bdcf26aSChristoph Hellwig } 1004