diff options
Diffstat (limited to 'fs/xfs/libxfs/xfs_iext_tree.c')
| -rw-r--r-- | fs/xfs/libxfs/xfs_iext_tree.c | 1043 |
1 files changed, 1043 insertions, 0 deletions
diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c new file mode 100644 index 000000000000..19e546a41251 --- /dev/null +++ b/fs/xfs/libxfs/xfs_iext_tree.c @@ -0,0 +1,1043 @@ +/* + * Copyright (c) 2017 Christoph Hellwig. + * + * This program is free software; you can redistribute it and/or modify it + * under the terms and conditions of the GNU General Public License, + * version 2, as published by the Free Software Foundation. + * + * This program is distributed in the hope it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + */ + +#include <linux/cache.h> +#include <linux/kernel.h> +#include <linux/slab.h> +#include "xfs.h" +#include "xfs_format.h" +#include "xfs_bit.h" +#include "xfs_log_format.h" +#include "xfs_inode.h" +#include "xfs_inode_fork.h" +#include "xfs_trans_resv.h" +#include "xfs_mount.h" +#include "xfs_trace.h" + +/* + * In-core extent record layout: + * + * +-------+----------------------------+ + * | 00:53 | all 54 bits of startoff | + * | 54:63 | low 10 bits of startblock | + * +-------+----------------------------+ + * | 00:20 | all 21 bits of length | + * | 21 | unwritten extent bit | + * | 22:63 | high 42 bits of startblock | + * +-------+----------------------------+ + */ +#define XFS_IEXT_STARTOFF_MASK xfs_mask64lo(BMBT_STARTOFF_BITLEN) +#define XFS_IEXT_LENGTH_MASK xfs_mask64lo(BMBT_BLOCKCOUNT_BITLEN) +#define XFS_IEXT_STARTBLOCK_MASK xfs_mask64lo(BMBT_STARTBLOCK_BITLEN) + +struct xfs_iext_rec { + uint64_t lo; + uint64_t hi; +}; + +/* + * Given that the length can't be a zero, only an empty hi value indicates an + * unused record. + */ +static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec) +{ + return rec->hi == 0; +} + +static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec) +{ + rec->lo = 0; + rec->hi = 0; +} + +static void +xfs_iext_set( + struct xfs_iext_rec *rec, + struct xfs_bmbt_irec *irec) +{ + ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0); + ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0); + ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0); + + rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK; + rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK; + + rec->lo |= (irec->br_startblock << 54); + rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10)); + + if (irec->br_state == XFS_EXT_UNWRITTEN) + rec->hi |= (1 << 21); +} + +static void +xfs_iext_get( + struct xfs_bmbt_irec *irec, + struct xfs_iext_rec *rec) +{ + irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK; + irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK; + + irec->br_startblock = rec->lo >> 54; + irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10); + + if (rec->hi & (1 << 21)) + irec->br_state = XFS_EXT_UNWRITTEN; + else + irec->br_state = XFS_EXT_NORM; +} + +enum { + NODE_SIZE = 256, + KEYS_PER_NODE = NODE_SIZE / (sizeof(uint64_t) + sizeof(void *)), + RECS_PER_LEAF = (NODE_SIZE - (2 * sizeof(struct xfs_iext_leaf *))) / + sizeof(struct xfs_iext_rec), +}; + +/* + * In-core extent btree block layout: + * + * There are two types of blocks in the btree: leaf and inner (non-leaf) blocks. + * + * The leaf blocks are made up by %KEYS_PER_NODE extent records, which each + * contain the startoffset, blockcount, startblock and unwritten extent flag. + * See above for the exact format, followed by pointers to the previous and next + * leaf blocks (if there are any). + * + * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed + * by an equal number of pointers to the btree blocks at the next lower level. + * + * +-------+-------+-------+-------+-------+----------+----------+ + * Leaf: | rec 1 | rec 2 | rec 3 | rec 4 | rec N | prev-ptr | next-ptr | + * +-------+-------+-------+-------+-------+----------+----------+ + * + * +-------+-------+-------+-------+-------+-------+------+-------+ + * Inner: | key 1 | key 2 | key 3 | key N | ptr 1 | ptr 2 | ptr3 | ptr N | + * +-------+-------+-------+-------+-------+-------+------+-------+ + */ +struct xfs_iext_node { + uint64_t keys[KEYS_PER_NODE]; +#define XFS_IEXT_KEY_INVALID (1ULL << 63) + void *ptrs[KEYS_PER_NODE]; +}; + +struct xfs_iext_leaf { + struct xfs_iext_rec recs[RECS_PER_LEAF]; + struct xfs_iext_leaf *prev; + struct xfs_iext_leaf *next; +}; + +inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp) +{ + return ifp->if_bytes / sizeof(struct xfs_iext_rec); +} + +static inline int xfs_iext_max_recs(struct xfs_ifork *ifp) +{ + if (ifp->if_height == 1) + return xfs_iext_count(ifp); + return RECS_PER_LEAF; +} + +static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur) +{ + return &cur->leaf->recs[cur->pos]; +} + +static inline bool xfs_iext_valid(struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur) +{ + if (!cur->leaf) + return false; + if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp)) + return false; + if (xfs_iext_rec_is_empty(cur_rec(cur))) + return false; + return true; +} + +static void * +xfs_iext_find_first_leaf( + struct xfs_ifork *ifp) +{ + struct xfs_iext_node *node = ifp->if_u1.if_root; + int height; + + if (!ifp->if_height) + return NULL; + + for (height = ifp->if_height; height > 1; height--) { + node = node->ptrs[0]; + ASSERT(node); + } + + return node; +} + +static void * +xfs_iext_find_last_leaf( + struct xfs_ifork *ifp) +{ + struct xfs_iext_node *node = ifp->if_u1.if_root; + int height, i; + + if (!ifp->if_height) + return NULL; + + for (height = ifp->if_height; height > 1; height--) { + for (i = 1; i < KEYS_PER_NODE; i++) + if (!node->ptrs[i]) + break; + node = node->ptrs[i - 1]; + ASSERT(node); + } + + return node; +} + +void +xfs_iext_first( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur) +{ + cur->pos = 0; + cur->leaf = xfs_iext_find_first_leaf(ifp); +} + +void +xfs_iext_last( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur) +{ + int i; + + cur->leaf = xfs_iext_find_last_leaf(ifp); + if (!cur->leaf) { + cur->pos = 0; + return; + } + + for (i = 1; i < xfs_iext_max_recs(ifp); i++) { + if (xfs_iext_rec_is_empty(&cur->leaf->recs[i])) + break; + } + cur->pos = i - 1; +} + +void +xfs_iext_next( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur) +{ + if (!cur->leaf) { + ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF); + xfs_iext_first(ifp, cur); + return; + } + + ASSERT(cur->pos >= 0); + ASSERT(cur->pos < xfs_iext_max_recs(ifp)); + + cur->pos++; + if (ifp->if_height > 1 && !xfs_iext_valid(ifp, cur) && + cur->leaf->next) { + cur->leaf = cur->leaf->next; + cur->pos = 0; + } +} + +void +xfs_iext_prev( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur) +{ + if (!cur->leaf) { + ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF); + xfs_iext_last(ifp, cur); + return; + } + + ASSERT(cur->pos >= 0); + ASSERT(cur->pos <= RECS_PER_LEAF); + +recurse: + do { + cur->pos--; + if (xfs_iext_valid(ifp, cur)) + return; + } while (cur->pos > 0); + + if (ifp->if_height > 1 && cur->leaf->prev) { + cur->leaf = cur->leaf->prev; + cur->pos = RECS_PER_LEAF; + goto recurse; + } +} + +static inline int +xfs_iext_key_cmp( + struct xfs_iext_node *node, + int n, + xfs_fileoff_t offset) +{ + if (node->keys[n] > offset) + return 1; + if (node->keys[n] < offset) + return -1; + return 0; +} + +static inline int +xfs_iext_rec_cmp( + struct xfs_iext_rec *rec, + xfs_fileoff_t offset) +{ + uint64_t rec_offset = rec->lo & XFS_IEXT_STARTOFF_MASK; + uint32_t rec_len = rec->hi & XFS_IEXT_LENGTH_MASK; + + if (rec_offset > offset) + return 1; + if (rec_offset + rec_len <= offset) + return -1; + return 0; +} + +static void * +xfs_iext_find_level( + struct xfs_ifork *ifp, + xfs_fileoff_t offset, + int level) +{ + struct xfs_iext_node *node = ifp->if_u1.if_root; + int height, i; + + if (!ifp->if_height) + return NULL; + + for (height = ifp->if_height; height > level; height--) { + for (i = 1; i < KEYS_PER_NODE; i++) + if (xfs_iext_key_cmp(node, i, offset) > 0) + break; + + node = node->ptrs[i - 1]; + if (!node) + break; + } + + return node; +} + +static int +xfs_iext_node_pos( + struct xfs_iext_node *node, + xfs_fileoff_t offset) +{ + int i; + + for (i = 1; i < KEYS_PER_NODE; i++) { + if (xfs_iext_key_cmp(node, i, offset) > 0) + break; + } + + return i - 1; +} + +static int +xfs_iext_node_insert_pos( + struct xfs_iext_node *node, + xfs_fileoff_t offset) +{ + int i; + + for (i = 0; i < KEYS_PER_NODE; i++) { + if (xfs_iext_key_cmp(node, i, offset) > 0) + return i; + } + + return KEYS_PER_NODE; +} + +static int +xfs_iext_node_nr_entries( + struct xfs_iext_node *node, + int start) +{ + int i; + + for (i = start; i < KEYS_PER_NODE; i++) { + if (node->keys[i] == XFS_IEXT_KEY_INVALID) + break; + } + + return i; +} + +static int +xfs_iext_leaf_nr_entries( + struct xfs_ifork *ifp, + struct xfs_iext_leaf *leaf, + int start) +{ + int i; + + for (i = start; i < xfs_iext_max_recs(ifp); i++) { + if (xfs_iext_rec_is_empty(&leaf->recs[i])) + break; + } + + return i; +} + +static inline uint64_t +xfs_iext_leaf_key( + struct xfs_iext_leaf *leaf, + int n) +{ + return leaf->recs[n].lo & XFS_IEXT_STARTOFF_MASK; +} + +static void +xfs_iext_grow( + struct xfs_ifork *ifp) +{ + struct xfs_iext_node *node = kmem_zalloc(NODE_SIZE, KM_NOFS); + int i; + + if (ifp->if_height == 1) { + struct xfs_iext_leaf *prev = ifp->if_u1.if_root; + + node->keys[0] = xfs_iext_leaf_key(prev, 0); + node->ptrs[0] = prev; + } else { + struct xfs_iext_node *prev = ifp->if_u1.if_root; + + ASSERT(ifp->if_height > 1); + + node->keys[0] = prev->keys[0]; + node->ptrs[0] = prev; + } + + for (i = 1; i < KEYS_PER_NODE; i++) + node->keys[i] = XFS_IEXT_KEY_INVALID; + + ifp->if_u1.if_root = node; + ifp->if_height++; +} + +static void +xfs_iext_update_node( + struct xfs_ifork *ifp, + xfs_fileoff_t old_offset, + xfs_fileoff_t new_offset, + int level, + void *ptr) +{ + struct xfs_iext_node *node = ifp->if_u1.if_root; + int height, i; + + for (height = ifp->if_height; height > level; height--) { + for (i = 0; i < KEYS_PER_NODE; i++) { + if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0) + break; + if (node->keys[i] == old_offset) + node->keys[i] = new_offset; + } + node = node->ptrs[i - 1]; + ASSERT(node); + } + + ASSERT(node == ptr); +} + +static struct xfs_iext_node * +xfs_iext_split_node( + struct xfs_iext_node **nodep, + int *pos, + int *nr_entries) +{ + struct xfs_iext_node *node = *nodep; + struct xfs_iext_node *new = kmem_zalloc(NODE_SIZE, KM_NOFS); + const int nr_move = KEYS_PER_NODE / 2; + int nr_keep = nr_move + (KEYS_PER_NODE & 1); + int i = 0; + + /* for sequential append operations just spill over into the new node */ + if (*pos == KEYS_PER_NODE) { + *nodep = new; + *pos = 0; + *nr_entries = 0; + goto done; + } + + + for (i = 0; i < nr_move; i++) { + new->keys[i] = node->keys[nr_keep + i]; + new->ptrs[i] = node->ptrs[nr_keep + i]; + + node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID; + node->ptrs[nr_keep + i] = NULL; + } + + if (*pos >= nr_keep) { + *nodep = new; + *pos -= nr_keep; + *nr_entries = nr_move; + } else { + *nr_entries = nr_keep; + } +done: + for (; i < KEYS_PER_NODE; i++) + new->keys[i] = XFS_IEXT_KEY_INVALID; + return new; +} + +static void +xfs_iext_insert_node( + struct xfs_ifork *ifp, + uint64_t offset, + void *ptr, + int level) +{ + struct xfs_iext_node *node, *new; + int i, pos, nr_entries; + +again: + if (ifp->if_height < level) + xfs_iext_grow(ifp); + + new = NULL; + node = xfs_iext_find_level(ifp, offset, level); + pos = xfs_iext_node_insert_pos(node, offset); + nr_entries = xfs_iext_node_nr_entries(node, pos); + + ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0); + ASSERT(nr_entries <= KEYS_PER_NODE); + + if (nr_entries == KEYS_PER_NODE) + new = xfs_iext_split_node(&node, &pos, &nr_entries); + + /* + * Update the pointers in higher levels if the first entry changes + * in an existing node. + */ + if (node != new && pos == 0 && nr_entries > 0) + xfs_iext_update_node(ifp, node->keys[0], offset, level, node); + + for (i = nr_entries; i > pos; i--) { + node->keys[i] = node->keys[i - 1]; + node->ptrs[i] = node->ptrs[i - 1]; + } + node->keys[pos] = offset; + node->ptrs[pos] = ptr; + + if (new) { + offset = new->keys[0]; + ptr = new; + level++; + goto again; + } +} + +static struct xfs_iext_leaf * +xfs_iext_split_leaf( + struct xfs_iext_cursor *cur, + int *nr_entries) +{ + struct xfs_iext_leaf *leaf = cur->leaf; + struct xfs_iext_leaf *new = kmem_zalloc(NODE_SIZE, KM_NOFS); + const int nr_move = RECS_PER_LEAF / 2; + int nr_keep = nr_move + (RECS_PER_LEAF & 1); + int i; + + /* for sequential append operations just spill over into the new node */ + if (cur->pos == RECS_PER_LEAF) { + cur->leaf = new; + cur->pos = 0; + *nr_entries = 0; + goto done; + } + + for (i = 0; i < nr_move; i++) { + new->recs[i] = leaf->recs[nr_keep + i]; + xfs_iext_rec_clear(&leaf->recs[nr_keep + i]); + } + + if (cur->pos >= nr_keep) { + cur->leaf = new; + cur->pos -= nr_keep; + *nr_entries = nr_move; + } else { + *nr_entries = nr_keep; + } +done: + if (leaf->next) + leaf->next->prev = new; + new->next = leaf->next; + new->prev = leaf; + leaf->next = new; + return new; +} + +static void +xfs_iext_alloc_root( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur) +{ + ASSERT(ifp->if_bytes == 0); + + ifp->if_u1.if_root = kmem_zalloc(sizeof(struct xfs_iext_rec), KM_NOFS); + ifp->if_height = 1; + + /* now that we have a node step into it */ + cur->leaf = ifp->if_u1.if_root; + cur->pos = 0; +} + +static void +xfs_iext_realloc_root( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur) +{ + size_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec); + void *new; + + /* account for the prev/next pointers */ + if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF) + new_size = NODE_SIZE; + + new = kmem_realloc(ifp->if_u1.if_root, new_size, KM_NOFS); + memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes); + ifp->if_u1.if_root = new; + cur->leaf = new; +} + +void +xfs_iext_insert( + struct xfs_inode *ip, + struct xfs_iext_cursor *cur, + struct xfs_bmbt_irec *irec, + int state) +{ + struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); + xfs_fileoff_t offset = irec->br_startoff; + struct xfs_iext_leaf *new = NULL; + int nr_entries, i; + + trace_xfs_iext_insert(ip, cur, state, _RET_IP_); + + if (ifp->if_height == 0) + xfs_iext_alloc_root(ifp, cur); + else if (ifp->if_height == 1) + xfs_iext_realloc_root(ifp, cur); + + nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos); + ASSERT(nr_entries <= RECS_PER_LEAF); + ASSERT(cur->pos >= nr_entries || + xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0); + + if (nr_entries == RECS_PER_LEAF) + new = xfs_iext_split_leaf(cur, &nr_entries); + + /* + * Update the pointers in higher levels if the first entry changes + * in an existing node. + */ + if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) { + xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0), + offset, 1, cur->leaf); + } + + for (i = nr_entries; i > cur->pos; i--) + cur->leaf->recs[i] = cur->leaf->recs[i - 1]; + xfs_iext_set(cur_rec(cur), irec); + ifp->if_bytes += sizeof(struct xfs_iext_rec); + + if (new) + xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2); +} + +static struct xfs_iext_node * +xfs_iext_rebalance_node( + struct xfs_iext_node *parent, + int *pos, + struct xfs_iext_node *node, + int nr_entries) +{ + /* + * If the neighbouring nodes are completely full, or have different + * parents, we might never be able to merge our node, and will only + * delete it once the number of entries hits zero. + */ + if (nr_entries == 0) + return node; + + if (*pos > 0) { + struct xfs_iext_node *prev = parent->ptrs[*pos - 1]; + int nr_prev = xfs_iext_node_nr_entries(prev, 0), i; + + if (nr_prev + nr_entries <= KEYS_PER_NODE) { + for (i = 0; i < nr_entries; i++) { + prev->keys[nr_prev + i] = node->keys[i]; + prev->ptrs[nr_prev + i] = node->ptrs[i]; + } + return node; + } + } + + if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) { + struct xfs_iext_node *next = parent->ptrs[*pos + 1]; + int nr_next = xfs_iext_node_nr_entries(next, 0), i; + + if (nr_entries + nr_next <= KEYS_PER_NODE) { + /* + * Merge the next node into this node so that we don't + * have to do an additional update of the keys in the + * higher levels. + */ + for (i = 0; i < nr_next; i++) { + node->keys[nr_entries + i] = next->keys[i]; + node->ptrs[nr_entries + i] = next->ptrs[i]; + } + + ++*pos; + return next; + } + } + + return NULL; +} + +static void +xfs_iext_remove_node( + struct xfs_ifork *ifp, + xfs_fileoff_t offset, + void *victim) +{ + struct xfs_iext_node *node, *parent; + int level = 2, pos, nr_entries, i; + + ASSERT(level <= ifp->if_height); + node = xfs_iext_find_level(ifp, offset, level); + pos = xfs_iext_node_pos(node, offset); +again: + ASSERT(node->ptrs[pos]); + ASSERT(node->ptrs[pos] == victim); + kmem_free(victim); + + nr_entries = xfs_iext_node_nr_entries(node, pos) - 1; + offset = node->keys[0]; + for (i = pos; i < nr_entries; i++) { + node->keys[i] = node->keys[i + 1]; + node->ptrs[i] = node->ptrs[i + 1]; + } + node->keys[nr_entries] = XFS_IEXT_KEY_INVALID; + node->ptrs[nr_entries] = NULL; + + if (pos == 0 && nr_entries > 0) { + xfs_iext_update_node(ifp, offset, node->keys[0], level, node); + offset = node->keys[0]; + } + + if (nr_entries >= KEYS_PER_NODE / 2) + return; + + if (level < ifp->if_height) { + /* + * If we aren't at the root yet try to find a neighbour node to + * merge with (or delete the node if it is empty), and then + * recurse up to the next level. + */ + level++; + parent = xfs_iext_find_level(ifp, offset, level); + pos = xfs_iext_node_pos(parent, offset); + + ASSERT(pos != KEYS_PER_NODE); + ASSERT(parent->ptrs[pos] == node); + + node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries); + if (node) { + victim = node; + node = parent; + goto again; + } + } else if (nr_entries == 1) { + /* + * If we are at the root and only one entry is left we can just + * free this node and update the root pointer. + */ + ASSERT(node == ifp->if_u1.if_root); + ifp->if_u1.if_root = node->ptrs[0]; + ifp->if_height--; + kmem_free(node); + } +} + +static void +xfs_iext_rebalance_leaf( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur, + struct xfs_iext_leaf *leaf, + xfs_fileoff_t offset, + int nr_entries) +{ + /* + * If the neighbouring nodes are completely full we might never be able + * to merge our node, and will only delete it once the number of + * entries hits zero. + */ + if (nr_entries == 0) + goto remove_node; + + if (leaf->prev) { + int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i; + + if (nr_prev + nr_entries <= RECS_PER_LEAF) { + for (i = 0; i < nr_entries; i++) + leaf->prev->recs[nr_prev + i] = leaf->recs[i]; + + if (cur->leaf == leaf) { + cur->leaf = leaf->prev; + cur->pos += nr_prev; + } + goto remove_node; + } + } + + if (leaf->next) { + int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i; + + if (nr_entries + nr_next <= RECS_PER_LEAF) { + /* + * Merge the next node into this node so that we don't + * have to do an additional update of the keys in the + * higher levels. + */ + for (i = 0; i < nr_next; i++) { + leaf->recs[nr_entries + i] = + leaf->next->recs[i]; + } + + if (cur->leaf == leaf->next) { + cur->leaf = leaf; + cur->pos += nr_entries; + } + + offset = xfs_iext_leaf_key(leaf->next, 0); + leaf = leaf->next; + goto remove_node; + } + } + + return; +remove_node: + if (leaf->prev) + leaf->prev->next = leaf->next; + if (leaf->next) + leaf->next->prev = leaf->prev; + xfs_iext_remove_node(ifp, offset, leaf); +} + +static void +xfs_iext_free_last_leaf( + struct xfs_ifork *ifp) +{ + ifp->if_u1.if_root = NULL; + ifp->if_height--; + kmem_free(ifp->if_u1.if_root); +} + +void +xfs_iext_remove( + struct xfs_inode *ip, + struct xfs_iext_cursor *cur, + int state) +{ + struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); + struct xfs_iext_leaf *leaf = cur->leaf; + xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0); + int i, nr_entries; + + trace_xfs_iext_remove(ip, cur, state, _RET_IP_); + + ASSERT(ifp->if_height > 0); + ASSERT(ifp->if_u1.if_root != NULL); + ASSERT(xfs_iext_valid(ifp, cur)); + + nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1; + for (i = cur->pos; i < nr_entries; i++) + leaf->recs[i] = leaf->recs[i + 1]; + xfs_iext_rec_clear(&leaf->recs[nr_entries]); + ifp->if_bytes -= sizeof(struct xfs_iext_rec); + + if (cur->pos == 0 && nr_entries > 0) { + xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1, + leaf); + offset = xfs_iext_leaf_key(leaf, 0); + } else if (cur->pos == nr_entries) { + if (ifp->if_height > 1 && leaf->next) + cur->leaf = leaf->next; + else + cur->leaf = NULL; + cur->pos = 0; + } + + if (nr_entries >= RECS_PER_LEAF / 2) + return; + + if (ifp->if_height > 1) + xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries); + else if (nr_entries == 0) + xfs_iext_free_last_leaf(ifp); +} + +/* + * Lookup the extent covering bno. + * + * If there is an extent covering bno return the extent index, and store the + * expanded extent structure in *gotp, and the extent cursor in *cur. + * If there is no extent covering bno, but there is an extent after it (e.g. + * it lies in a hole) return that extent in *gotp and its cursor in *cur + * instead. + * If bno is beyond the last extent return false, and return an invalid + * cursor value. + */ +bool +xfs_iext_lookup_extent( + struct xfs_inode *ip, + struct xfs_ifork *ifp, + xfs_fileoff_t offset, + struct xfs_iext_cursor *cur, + struct xfs_bmbt_irec *gotp) +{ + XFS_STATS_INC(ip->i_mount, xs_look_exlist); + + cur->leaf = xfs_iext_find_level(ifp, offset, 1); + if (!cur->leaf) { + cur->pos = 0; + return false; + } + + for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) { + struct xfs_iext_rec *rec = cur_rec(cur); + + if (xfs_iext_rec_is_empty(rec)) + break; + if (xfs_iext_rec_cmp(rec, offset) >= 0) + goto found; + } + + /* Try looking in the next node for an entry > offset */ + if (ifp->if_height == 1 || !cur->leaf->next) + return false; + cur->leaf = cur->leaf->next; + cur->pos = 0; + if (!xfs_iext_valid(ifp, cur)) + return false; +found: + xfs_iext_get(gotp, cur_rec(cur)); + return true; +} + +/* + * Returns the last extent before end, and if this extent doesn't cover + * end, update end to the end of the extent. + */ +bool +xfs_iext_lookup_extent_before( + struct xfs_inode *ip, + struct xfs_ifork *ifp, + xfs_fileoff_t *end, + struct xfs_iext_cursor *cur, + struct xfs_bmbt_irec *gotp) +{ + /* could be optimized to not even look up the next on a match.. */ + if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) && + gotp->br_startoff <= *end - 1) + return true; + if (!xfs_iext_prev_extent(ifp, cur, gotp)) + return false; + *end = gotp->br_startoff + gotp->br_blockcount; + return true; +} + +void +xfs_iext_update_extent( + struct xfs_inode *ip, + int state, + struct xfs_iext_cursor *cur, + struct xfs_bmbt_irec *new) +{ + struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state); + + if (cur->pos == 0) { + struct xfs_bmbt_irec old; + + xfs_iext_get(&old, cur_rec(cur)); + if (new->br_startoff != old.br_startoff) { + xfs_iext_update_node(ifp, old.br_startoff, + new->br_startoff, 1, cur->leaf); + } + } + + trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_); + xfs_iext_set(cur_rec(cur), new); + trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_); +} + +/* + * Return true if the cursor points at an extent and return the extent structure + * in gotp. Else return false. + */ +bool +xfs_iext_get_extent( + struct xfs_ifork *ifp, + struct xfs_iext_cursor *cur, + struct xfs_bmbt_irec *gotp) +{ + if (!xfs_iext_valid(ifp, cur)) + return false; + xfs_iext_get(gotp, cur_rec(cur)); + return true; +} + +/* + * This is a recursive function, because of that we need to be extremely + * careful with stack usage. + */ +static void +xfs_iext_destroy_node( + struct xfs_iext_node *node, + int level) +{ + int i; + + if (level > 1) { + for (i = 0; i < KEYS_PER_NODE; i++) { + if (node->keys[i] == XFS_IEXT_KEY_INVALID) + break; + xfs_iext_destroy_node(node->ptrs[i], level - 1); + } + } + + kmem_free(node); +} + +void +xfs_iext_destroy( + struct xfs_ifork *ifp) +{ + xfs_iext_destroy_node(ifp->if_u1.if_root, ifp->if_height); + + ifp->if_bytes = 0; + ifp->if_height = 0; + ifp->if_u1.if_root = NULL; +} |