1068 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (c) 2017 Christoph Hellwig.4 */5 6#include "xfs.h"7#include "xfs_shared.h"8#include "xfs_format.h"9#include "xfs_bit.h"10#include "xfs_log_format.h"11#include "xfs_trans_resv.h"12#include "xfs_mount.h"13#include "xfs_inode.h"14#include "xfs_trace.h"15 16/*17 * In-core extent record layout:18 *19 * +-------+----------------------------+20 * | 00:53 | all 54 bits of startoff |21 * | 54:63 | low 10 bits of startblock |22 * +-------+----------------------------+23 * | 00:20 | all 21 bits of length |24 * | 21 | unwritten extent bit |25 * | 22:63 | high 42 bits of startblock |26 * +-------+----------------------------+27 */28#define XFS_IEXT_STARTOFF_MASK xfs_mask64lo(BMBT_STARTOFF_BITLEN)29#define XFS_IEXT_LENGTH_MASK xfs_mask64lo(BMBT_BLOCKCOUNT_BITLEN)30#define XFS_IEXT_STARTBLOCK_MASK xfs_mask64lo(BMBT_STARTBLOCK_BITLEN)31 32struct xfs_iext_rec {33 uint64_t lo;34 uint64_t hi;35};36 37/*38 * Given that the length can't be a zero, only an empty hi value indicates an39 * unused record.40 */41static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec)42{43 return rec->hi == 0;44}45 46static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec)47{48 rec->lo = 0;49 rec->hi = 0;50}51 52static void53xfs_iext_set(54 struct xfs_iext_rec *rec,55 struct xfs_bmbt_irec *irec)56{57 ASSERT((irec->br_startoff & ~XFS_IEXT_STARTOFF_MASK) == 0);58 ASSERT((irec->br_blockcount & ~XFS_IEXT_LENGTH_MASK) == 0);59 ASSERT((irec->br_startblock & ~XFS_IEXT_STARTBLOCK_MASK) == 0);60 61 rec->lo = irec->br_startoff & XFS_IEXT_STARTOFF_MASK;62 rec->hi = irec->br_blockcount & XFS_IEXT_LENGTH_MASK;63 64 rec->lo |= (irec->br_startblock << 54);65 rec->hi |= ((irec->br_startblock & ~xfs_mask64lo(10)) << (22 - 10));66 67 if (irec->br_state == XFS_EXT_UNWRITTEN)68 rec->hi |= (1 << 21);69}70 71static void72xfs_iext_get(73 struct xfs_bmbt_irec *irec,74 struct xfs_iext_rec *rec)75{76 irec->br_startoff = rec->lo & XFS_IEXT_STARTOFF_MASK;77 irec->br_blockcount = rec->hi & XFS_IEXT_LENGTH_MASK;78 79 irec->br_startblock = rec->lo >> 54;80 irec->br_startblock |= (rec->hi & xfs_mask64hi(42)) >> (22 - 10);81 82 if (rec->hi & (1 << 21))83 irec->br_state = XFS_EXT_UNWRITTEN;84 else85 irec->br_state = XFS_EXT_NORM;86}87 88enum {89 NODE_SIZE = 256,90 KEYS_PER_NODE = NODE_SIZE / (sizeof(uint64_t) + sizeof(void *)),91 RECS_PER_LEAF = (NODE_SIZE - (2 * sizeof(struct xfs_iext_leaf *))) /92 sizeof(struct xfs_iext_rec),93};94 95/*96 * In-core extent btree block layout:97 *98 * There are two types of blocks in the btree: leaf and inner (non-leaf) blocks.99 *100 * The leaf blocks are made up by %KEYS_PER_NODE extent records, which each101 * contain the startoffset, blockcount, startblock and unwritten extent flag.102 * See above for the exact format, followed by pointers to the previous and next103 * leaf blocks (if there are any).104 *105 * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed106 * by an equal number of pointers to the btree blocks at the next lower level.107 *108 * +-------+-------+-------+-------+-------+----------+----------+109 * Leaf: | rec 1 | rec 2 | rec 3 | rec 4 | rec N | prev-ptr | next-ptr |110 * +-------+-------+-------+-------+-------+----------+----------+111 *112 * +-------+-------+-------+-------+-------+-------+------+-------+113 * Inner: | key 1 | key 2 | key 3 | key N | ptr 1 | ptr 2 | ptr3 | ptr N |114 * +-------+-------+-------+-------+-------+-------+------+-------+115 */116struct xfs_iext_node {117 uint64_t keys[KEYS_PER_NODE];118#define XFS_IEXT_KEY_INVALID (1ULL << 63)119 void *ptrs[KEYS_PER_NODE];120};121 122struct xfs_iext_leaf {123 struct xfs_iext_rec recs[RECS_PER_LEAF];124 struct xfs_iext_leaf *prev;125 struct xfs_iext_leaf *next;126};127 128inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp)129{130 return ifp->if_bytes / sizeof(struct xfs_iext_rec);131}132 133static inline int xfs_iext_max_recs(struct xfs_ifork *ifp)134{135 if (ifp->if_height == 1)136 return xfs_iext_count(ifp);137 return RECS_PER_LEAF;138}139 140static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur)141{142 return &cur->leaf->recs[cur->pos];143}144 145static inline bool xfs_iext_valid(struct xfs_ifork *ifp,146 struct xfs_iext_cursor *cur)147{148 if (!cur->leaf)149 return false;150 if (cur->pos < 0 || cur->pos >= xfs_iext_max_recs(ifp))151 return false;152 if (xfs_iext_rec_is_empty(cur_rec(cur)))153 return false;154 return true;155}156 157static void *158xfs_iext_find_first_leaf(159 struct xfs_ifork *ifp)160{161 struct xfs_iext_node *node = ifp->if_data;162 int height;163 164 if (!ifp->if_height)165 return NULL;166 167 for (height = ifp->if_height; height > 1; height--) {168 node = node->ptrs[0];169 ASSERT(node);170 }171 172 return node;173}174 175static void *176xfs_iext_find_last_leaf(177 struct xfs_ifork *ifp)178{179 struct xfs_iext_node *node = ifp->if_data;180 int height, i;181 182 if (!ifp->if_height)183 return NULL;184 185 for (height = ifp->if_height; height > 1; height--) {186 for (i = 1; i < KEYS_PER_NODE; i++)187 if (!node->ptrs[i])188 break;189 node = node->ptrs[i - 1];190 ASSERT(node);191 }192 193 return node;194}195 196void197xfs_iext_first(198 struct xfs_ifork *ifp,199 struct xfs_iext_cursor *cur)200{201 cur->pos = 0;202 cur->leaf = xfs_iext_find_first_leaf(ifp);203}204 205void206xfs_iext_last(207 struct xfs_ifork *ifp,208 struct xfs_iext_cursor *cur)209{210 int i;211 212 cur->leaf = xfs_iext_find_last_leaf(ifp);213 if (!cur->leaf) {214 cur->pos = 0;215 return;216 }217 218 for (i = 1; i < xfs_iext_max_recs(ifp); i++) {219 if (xfs_iext_rec_is_empty(&cur->leaf->recs[i]))220 break;221 }222 cur->pos = i - 1;223}224 225void226xfs_iext_next(227 struct xfs_ifork *ifp,228 struct xfs_iext_cursor *cur)229{230 if (!cur->leaf) {231 ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);232 xfs_iext_first(ifp, cur);233 return;234 }235 236 ASSERT(cur->pos >= 0);237 ASSERT(cur->pos < xfs_iext_max_recs(ifp));238 239 cur->pos++;240 if (ifp->if_height > 1 && !xfs_iext_valid(ifp, cur) &&241 cur->leaf->next) {242 cur->leaf = cur->leaf->next;243 cur->pos = 0;244 }245}246 247void248xfs_iext_prev(249 struct xfs_ifork *ifp,250 struct xfs_iext_cursor *cur)251{252 if (!cur->leaf) {253 ASSERT(cur->pos <= 0 || cur->pos >= RECS_PER_LEAF);254 xfs_iext_last(ifp, cur);255 return;256 }257 258 ASSERT(cur->pos >= 0);259 ASSERT(cur->pos <= RECS_PER_LEAF);260 261recurse:262 do {263 cur->pos--;264 if (xfs_iext_valid(ifp, cur))265 return;266 } while (cur->pos > 0);267 268 if (ifp->if_height > 1 && cur->leaf->prev) {269 cur->leaf = cur->leaf->prev;270 cur->pos = RECS_PER_LEAF;271 goto recurse;272 }273}274 275static inline int276xfs_iext_key_cmp(277 struct xfs_iext_node *node,278 int n,279 xfs_fileoff_t offset)280{281 if (node->keys[n] > offset)282 return 1;283 if (node->keys[n] < offset)284 return -1;285 return 0;286}287 288static inline int289xfs_iext_rec_cmp(290 struct xfs_iext_rec *rec,291 xfs_fileoff_t offset)292{293 uint64_t rec_offset = rec->lo & XFS_IEXT_STARTOFF_MASK;294 uint32_t rec_len = rec->hi & XFS_IEXT_LENGTH_MASK;295 296 if (rec_offset > offset)297 return 1;298 if (rec_offset + rec_len <= offset)299 return -1;300 return 0;301}302 303static void *304xfs_iext_find_level(305 struct xfs_ifork *ifp,306 xfs_fileoff_t offset,307 int level)308{309 struct xfs_iext_node *node = ifp->if_data;310 int height, i;311 312 if (!ifp->if_height)313 return NULL;314 315 for (height = ifp->if_height; height > level; height--) {316 for (i = 1; i < KEYS_PER_NODE; i++)317 if (xfs_iext_key_cmp(node, i, offset) > 0)318 break;319 320 node = node->ptrs[i - 1];321 if (!node)322 break;323 }324 325 return node;326}327 328static int329xfs_iext_node_pos(330 struct xfs_iext_node *node,331 xfs_fileoff_t offset)332{333 int i;334 335 for (i = 1; i < KEYS_PER_NODE; i++) {336 if (xfs_iext_key_cmp(node, i, offset) > 0)337 break;338 }339 340 return i - 1;341}342 343static int344xfs_iext_node_insert_pos(345 struct xfs_iext_node *node,346 xfs_fileoff_t offset)347{348 int i;349 350 for (i = 0; i < KEYS_PER_NODE; i++) {351 if (xfs_iext_key_cmp(node, i, offset) > 0)352 return i;353 }354 355 return KEYS_PER_NODE;356}357 358static int359xfs_iext_node_nr_entries(360 struct xfs_iext_node *node,361 int start)362{363 int i;364 365 for (i = start; i < KEYS_PER_NODE; i++) {366 if (node->keys[i] == XFS_IEXT_KEY_INVALID)367 break;368 }369 370 return i;371}372 373static int374xfs_iext_leaf_nr_entries(375 struct xfs_ifork *ifp,376 struct xfs_iext_leaf *leaf,377 int start)378{379 int i;380 381 for (i = start; i < xfs_iext_max_recs(ifp); i++) {382 if (xfs_iext_rec_is_empty(&leaf->recs[i]))383 break;384 }385 386 return i;387}388 389static inline uint64_t390xfs_iext_leaf_key(391 struct xfs_iext_leaf *leaf,392 int n)393{394 return leaf->recs[n].lo & XFS_IEXT_STARTOFF_MASK;395}396 397static inline void *398xfs_iext_alloc_node(399 int size)400{401 return kzalloc(size, GFP_KERNEL | __GFP_NOLOCKDEP | __GFP_NOFAIL);402}403 404static void405xfs_iext_grow(406 struct xfs_ifork *ifp)407{408 struct xfs_iext_node *node = xfs_iext_alloc_node(NODE_SIZE);409 int i;410 411 if (ifp->if_height == 1) {412 struct xfs_iext_leaf *prev = ifp->if_data;413 414 node->keys[0] = xfs_iext_leaf_key(prev, 0);415 node->ptrs[0] = prev;416 } else {417 struct xfs_iext_node *prev = ifp->if_data;418 419 ASSERT(ifp->if_height > 1);420 421 node->keys[0] = prev->keys[0];422 node->ptrs[0] = prev;423 }424 425 for (i = 1; i < KEYS_PER_NODE; i++)426 node->keys[i] = XFS_IEXT_KEY_INVALID;427 428 ifp->if_data = node;429 ifp->if_height++;430}431 432static void433xfs_iext_update_node(434 struct xfs_ifork *ifp,435 xfs_fileoff_t old_offset,436 xfs_fileoff_t new_offset,437 int level,438 void *ptr)439{440 struct xfs_iext_node *node = ifp->if_data;441 int height, i;442 443 for (height = ifp->if_height; height > level; height--) {444 for (i = 0; i < KEYS_PER_NODE; i++) {445 if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0)446 break;447 if (node->keys[i] == old_offset)448 node->keys[i] = new_offset;449 }450 node = node->ptrs[i - 1];451 ASSERT(node);452 }453 454 ASSERT(node == ptr);455}456 457static struct xfs_iext_node *458xfs_iext_split_node(459 struct xfs_iext_node **nodep,460 int *pos,461 int *nr_entries)462{463 struct xfs_iext_node *node = *nodep;464 struct xfs_iext_node *new = xfs_iext_alloc_node(NODE_SIZE);465 const int nr_move = KEYS_PER_NODE / 2;466 int nr_keep = nr_move + (KEYS_PER_NODE & 1);467 int i = 0;468 469 /* for sequential append operations just spill over into the new node */470 if (*pos == KEYS_PER_NODE) {471 *nodep = new;472 *pos = 0;473 *nr_entries = 0;474 goto done;475 }476 477 478 for (i = 0; i < nr_move; i++) {479 new->keys[i] = node->keys[nr_keep + i];480 new->ptrs[i] = node->ptrs[nr_keep + i];481 482 node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID;483 node->ptrs[nr_keep + i] = NULL;484 }485 486 if (*pos >= nr_keep) {487 *nodep = new;488 *pos -= nr_keep;489 *nr_entries = nr_move;490 } else {491 *nr_entries = nr_keep;492 }493done:494 for (; i < KEYS_PER_NODE; i++)495 new->keys[i] = XFS_IEXT_KEY_INVALID;496 return new;497}498 499static void500xfs_iext_insert_node(501 struct xfs_ifork *ifp,502 uint64_t offset,503 void *ptr,504 int level)505{506 struct xfs_iext_node *node, *new;507 int i, pos, nr_entries;508 509again:510 if (ifp->if_height < level)511 xfs_iext_grow(ifp);512 513 new = NULL;514 node = xfs_iext_find_level(ifp, offset, level);515 pos = xfs_iext_node_insert_pos(node, offset);516 nr_entries = xfs_iext_node_nr_entries(node, pos);517 518 ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0);519 ASSERT(nr_entries <= KEYS_PER_NODE);520 521 if (nr_entries == KEYS_PER_NODE)522 new = xfs_iext_split_node(&node, &pos, &nr_entries);523 524 /*525 * Update the pointers in higher levels if the first entry changes526 * in an existing node.527 */528 if (node != new && pos == 0 && nr_entries > 0)529 xfs_iext_update_node(ifp, node->keys[0], offset, level, node);530 531 for (i = nr_entries; i > pos; i--) {532 node->keys[i] = node->keys[i - 1];533 node->ptrs[i] = node->ptrs[i - 1];534 }535 node->keys[pos] = offset;536 node->ptrs[pos] = ptr;537 538 if (new) {539 offset = new->keys[0];540 ptr = new;541 level++;542 goto again;543 }544}545 546static struct xfs_iext_leaf *547xfs_iext_split_leaf(548 struct xfs_iext_cursor *cur,549 int *nr_entries)550{551 struct xfs_iext_leaf *leaf = cur->leaf;552 struct xfs_iext_leaf *new = xfs_iext_alloc_node(NODE_SIZE);553 const int nr_move = RECS_PER_LEAF / 2;554 int nr_keep = nr_move + (RECS_PER_LEAF & 1);555 int i;556 557 /* for sequential append operations just spill over into the new node */558 if (cur->pos == RECS_PER_LEAF) {559 cur->leaf = new;560 cur->pos = 0;561 *nr_entries = 0;562 goto done;563 }564 565 for (i = 0; i < nr_move; i++) {566 new->recs[i] = leaf->recs[nr_keep + i];567 xfs_iext_rec_clear(&leaf->recs[nr_keep + i]);568 }569 570 if (cur->pos >= nr_keep) {571 cur->leaf = new;572 cur->pos -= nr_keep;573 *nr_entries = nr_move;574 } else {575 *nr_entries = nr_keep;576 }577done:578 if (leaf->next)579 leaf->next->prev = new;580 new->next = leaf->next;581 new->prev = leaf;582 leaf->next = new;583 return new;584}585 586static void587xfs_iext_alloc_root(588 struct xfs_ifork *ifp,589 struct xfs_iext_cursor *cur)590{591 ASSERT(ifp->if_bytes == 0);592 593 ifp->if_data = xfs_iext_alloc_node(sizeof(struct xfs_iext_rec));594 ifp->if_height = 1;595 596 /* now that we have a node step into it */597 cur->leaf = ifp->if_data;598 cur->pos = 0;599}600 601static void602xfs_iext_realloc_root(603 struct xfs_ifork *ifp,604 struct xfs_iext_cursor *cur)605{606 int64_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec);607 void *new;608 609 /* account for the prev/next pointers */610 if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF)611 new_size = NODE_SIZE;612 613 new = krealloc(ifp->if_data, new_size,614 GFP_KERNEL | __GFP_NOLOCKDEP | __GFP_NOFAIL);615 memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes);616 ifp->if_data = new;617 cur->leaf = new;618}619 620/*621 * Increment the sequence counter on extent tree changes. If we are on a COW622 * fork, this allows the writeback code to skip looking for a COW extent if the623 * COW fork hasn't changed. We use WRITE_ONCE here to ensure the update to the624 * sequence counter is seen before the modifications to the extent tree itself625 * take effect.626 */627static inline void xfs_iext_inc_seq(struct xfs_ifork *ifp)628{629 WRITE_ONCE(ifp->if_seq, READ_ONCE(ifp->if_seq) + 1);630}631 632void633xfs_iext_insert_raw(634 struct xfs_ifork *ifp,635 struct xfs_iext_cursor *cur,636 struct xfs_bmbt_irec *irec)637{638 xfs_fileoff_t offset = irec->br_startoff;639 struct xfs_iext_leaf *new = NULL;640 int nr_entries, i;641 642 xfs_iext_inc_seq(ifp);643 644 if (ifp->if_height == 0)645 xfs_iext_alloc_root(ifp, cur);646 else if (ifp->if_height == 1)647 xfs_iext_realloc_root(ifp, cur);648 649 nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos);650 ASSERT(nr_entries <= RECS_PER_LEAF);651 ASSERT(cur->pos >= nr_entries ||652 xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0);653 654 if (nr_entries == RECS_PER_LEAF)655 new = xfs_iext_split_leaf(cur, &nr_entries);656 657 /*658 * Update the pointers in higher levels if the first entry changes659 * in an existing node.660 */661 if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) {662 xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0),663 offset, 1, cur->leaf);664 }665 666 for (i = nr_entries; i > cur->pos; i--)667 cur->leaf->recs[i] = cur->leaf->recs[i - 1];668 xfs_iext_set(cur_rec(cur), irec);669 ifp->if_bytes += sizeof(struct xfs_iext_rec);670 671 if (new)672 xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2);673}674 675void676xfs_iext_insert(677 struct xfs_inode *ip,678 struct xfs_iext_cursor *cur,679 struct xfs_bmbt_irec *irec,680 int state)681{682 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);683 684 xfs_iext_insert_raw(ifp, cur, irec);685 trace_xfs_iext_insert(ip, cur, state, _RET_IP_);686}687 688static struct xfs_iext_node *689xfs_iext_rebalance_node(690 struct xfs_iext_node *parent,691 int *pos,692 struct xfs_iext_node *node,693 int nr_entries)694{695 /*696 * If the neighbouring nodes are completely full, or have different697 * parents, we might never be able to merge our node, and will only698 * delete it once the number of entries hits zero.699 */700 if (nr_entries == 0)701 return node;702 703 if (*pos > 0) {704 struct xfs_iext_node *prev = parent->ptrs[*pos - 1];705 int nr_prev = xfs_iext_node_nr_entries(prev, 0), i;706 707 if (nr_prev + nr_entries <= KEYS_PER_NODE) {708 for (i = 0; i < nr_entries; i++) {709 prev->keys[nr_prev + i] = node->keys[i];710 prev->ptrs[nr_prev + i] = node->ptrs[i];711 }712 return node;713 }714 }715 716 if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) {717 struct xfs_iext_node *next = parent->ptrs[*pos + 1];718 int nr_next = xfs_iext_node_nr_entries(next, 0), i;719 720 if (nr_entries + nr_next <= KEYS_PER_NODE) {721 /*722 * Merge the next node into this node so that we don't723 * have to do an additional update of the keys in the724 * higher levels.725 */726 for (i = 0; i < nr_next; i++) {727 node->keys[nr_entries + i] = next->keys[i];728 node->ptrs[nr_entries + i] = next->ptrs[i];729 }730 731 ++*pos;732 return next;733 }734 }735 736 return NULL;737}738 739static void740xfs_iext_remove_node(741 struct xfs_ifork *ifp,742 xfs_fileoff_t offset,743 void *victim)744{745 struct xfs_iext_node *node, *parent;746 int level = 2, pos, nr_entries, i;747 748 ASSERT(level <= ifp->if_height);749 node = xfs_iext_find_level(ifp, offset, level);750 pos = xfs_iext_node_pos(node, offset);751again:752 ASSERT(node->ptrs[pos]);753 ASSERT(node->ptrs[pos] == victim);754 kfree(victim);755 756 nr_entries = xfs_iext_node_nr_entries(node, pos) - 1;757 offset = node->keys[0];758 for (i = pos; i < nr_entries; i++) {759 node->keys[i] = node->keys[i + 1];760 node->ptrs[i] = node->ptrs[i + 1];761 }762 node->keys[nr_entries] = XFS_IEXT_KEY_INVALID;763 node->ptrs[nr_entries] = NULL;764 765 if (pos == 0 && nr_entries > 0) {766 xfs_iext_update_node(ifp, offset, node->keys[0], level, node);767 offset = node->keys[0];768 }769 770 if (nr_entries >= KEYS_PER_NODE / 2)771 return;772 773 if (level < ifp->if_height) {774 /*775 * If we aren't at the root yet try to find a neighbour node to776 * merge with (or delete the node if it is empty), and then777 * recurse up to the next level.778 */779 level++;780 parent = xfs_iext_find_level(ifp, offset, level);781 pos = xfs_iext_node_pos(parent, offset);782 783 ASSERT(pos != KEYS_PER_NODE);784 ASSERT(parent->ptrs[pos] == node);785 786 node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries);787 if (node) {788 victim = node;789 node = parent;790 goto again;791 }792 } else if (nr_entries == 1) {793 /*794 * If we are at the root and only one entry is left we can just795 * free this node and update the root pointer.796 */797 ASSERT(node == ifp->if_data);798 ifp->if_data = node->ptrs[0];799 ifp->if_height--;800 kfree(node);801 }802}803 804static void805xfs_iext_rebalance_leaf(806 struct xfs_ifork *ifp,807 struct xfs_iext_cursor *cur,808 struct xfs_iext_leaf *leaf,809 xfs_fileoff_t offset,810 int nr_entries)811{812 /*813 * If the neighbouring nodes are completely full we might never be able814 * to merge our node, and will only delete it once the number of815 * entries hits zero.816 */817 if (nr_entries == 0)818 goto remove_node;819 820 if (leaf->prev) {821 int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i;822 823 if (nr_prev + nr_entries <= RECS_PER_LEAF) {824 for (i = 0; i < nr_entries; i++)825 leaf->prev->recs[nr_prev + i] = leaf->recs[i];826 827 if (cur->leaf == leaf) {828 cur->leaf = leaf->prev;829 cur->pos += nr_prev;830 }831 goto remove_node;832 }833 }834 835 if (leaf->next) {836 int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i;837 838 if (nr_entries + nr_next <= RECS_PER_LEAF) {839 /*840 * Merge the next node into this node so that we don't841 * have to do an additional update of the keys in the842 * higher levels.843 */844 for (i = 0; i < nr_next; i++) {845 leaf->recs[nr_entries + i] =846 leaf->next->recs[i];847 }848 849 if (cur->leaf == leaf->next) {850 cur->leaf = leaf;851 cur->pos += nr_entries;852 }853 854 offset = xfs_iext_leaf_key(leaf->next, 0);855 leaf = leaf->next;856 goto remove_node;857 }858 }859 860 return;861remove_node:862 if (leaf->prev)863 leaf->prev->next = leaf->next;864 if (leaf->next)865 leaf->next->prev = leaf->prev;866 xfs_iext_remove_node(ifp, offset, leaf);867}868 869static void870xfs_iext_free_last_leaf(871 struct xfs_ifork *ifp)872{873 ifp->if_height--;874 kfree(ifp->if_data);875 ifp->if_data = NULL;876}877 878void879xfs_iext_remove(880 struct xfs_inode *ip,881 struct xfs_iext_cursor *cur,882 int state)883{884 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);885 struct xfs_iext_leaf *leaf = cur->leaf;886 xfs_fileoff_t offset = xfs_iext_leaf_key(leaf, 0);887 int i, nr_entries;888 889 trace_xfs_iext_remove(ip, cur, state, _RET_IP_);890 891 ASSERT(ifp->if_height > 0);892 ASSERT(ifp->if_data != NULL);893 ASSERT(xfs_iext_valid(ifp, cur));894 895 xfs_iext_inc_seq(ifp);896 897 nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1;898 for (i = cur->pos; i < nr_entries; i++)899 leaf->recs[i] = leaf->recs[i + 1];900 xfs_iext_rec_clear(&leaf->recs[nr_entries]);901 ifp->if_bytes -= sizeof(struct xfs_iext_rec);902 903 if (cur->pos == 0 && nr_entries > 0) {904 xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1,905 leaf);906 offset = xfs_iext_leaf_key(leaf, 0);907 } else if (cur->pos == nr_entries) {908 if (ifp->if_height > 1 && leaf->next)909 cur->leaf = leaf->next;910 else911 cur->leaf = NULL;912 cur->pos = 0;913 }914 915 if (nr_entries >= RECS_PER_LEAF / 2)916 return;917 918 if (ifp->if_height > 1)919 xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries);920 else if (nr_entries == 0)921 xfs_iext_free_last_leaf(ifp);922}923 924/*925 * Lookup the extent covering bno.926 *927 * If there is an extent covering bno return the extent index, and store the928 * expanded extent structure in *gotp, and the extent cursor in *cur.929 * If there is no extent covering bno, but there is an extent after it (e.g.930 * it lies in a hole) return that extent in *gotp and its cursor in *cur931 * instead.932 * If bno is beyond the last extent return false, and return an invalid933 * cursor value.934 */935bool936xfs_iext_lookup_extent(937 struct xfs_inode *ip,938 struct xfs_ifork *ifp,939 xfs_fileoff_t offset,940 struct xfs_iext_cursor *cur,941 struct xfs_bmbt_irec *gotp)942{943 XFS_STATS_INC(ip->i_mount, xs_look_exlist);944 945 cur->leaf = xfs_iext_find_level(ifp, offset, 1);946 if (!cur->leaf) {947 cur->pos = 0;948 return false;949 }950 951 for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) {952 struct xfs_iext_rec *rec = cur_rec(cur);953 954 if (xfs_iext_rec_is_empty(rec))955 break;956 if (xfs_iext_rec_cmp(rec, offset) >= 0)957 goto found;958 }959 960 /* Try looking in the next node for an entry > offset */961 if (ifp->if_height == 1 || !cur->leaf->next)962 return false;963 cur->leaf = cur->leaf->next;964 cur->pos = 0;965 if (!xfs_iext_valid(ifp, cur))966 return false;967found:968 xfs_iext_get(gotp, cur_rec(cur));969 return true;970}971 972/*973 * Returns the last extent before end, and if this extent doesn't cover974 * end, update end to the end of the extent.975 */976bool977xfs_iext_lookup_extent_before(978 struct xfs_inode *ip,979 struct xfs_ifork *ifp,980 xfs_fileoff_t *end,981 struct xfs_iext_cursor *cur,982 struct xfs_bmbt_irec *gotp)983{984 /* could be optimized to not even look up the next on a match.. */985 if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) &&986 gotp->br_startoff <= *end - 1)987 return true;988 if (!xfs_iext_prev_extent(ifp, cur, gotp))989 return false;990 *end = gotp->br_startoff + gotp->br_blockcount;991 return true;992}993 994void995xfs_iext_update_extent(996 struct xfs_inode *ip,997 int state,998 struct xfs_iext_cursor *cur,999 struct xfs_bmbt_irec *new)1000{1001 struct xfs_ifork *ifp = xfs_iext_state_to_fork(ip, state);1002 1003 xfs_iext_inc_seq(ifp);1004 1005 if (cur->pos == 0) {1006 struct xfs_bmbt_irec old;1007 1008 xfs_iext_get(&old, cur_rec(cur));1009 if (new->br_startoff != old.br_startoff) {1010 xfs_iext_update_node(ifp, old.br_startoff,1011 new->br_startoff, 1, cur->leaf);1012 }1013 }1014 1015 trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_);1016 xfs_iext_set(cur_rec(cur), new);1017 trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_);1018}1019 1020/*1021 * Return true if the cursor points at an extent and return the extent structure1022 * in gotp. Else return false.1023 */1024bool1025xfs_iext_get_extent(1026 struct xfs_ifork *ifp,1027 struct xfs_iext_cursor *cur,1028 struct xfs_bmbt_irec *gotp)1029{1030 if (!xfs_iext_valid(ifp, cur))1031 return false;1032 xfs_iext_get(gotp, cur_rec(cur));1033 return true;1034}1035 1036/*1037 * This is a recursive function, because of that we need to be extremely1038 * careful with stack usage.1039 */1040static void1041xfs_iext_destroy_node(1042 struct xfs_iext_node *node,1043 int level)1044{1045 int i;1046 1047 if (level > 1) {1048 for (i = 0; i < KEYS_PER_NODE; i++) {1049 if (node->keys[i] == XFS_IEXT_KEY_INVALID)1050 break;1051 xfs_iext_destroy_node(node->ptrs[i], level - 1);1052 }1053 }1054 1055 kfree(node);1056}1057 1058void1059xfs_iext_destroy(1060 struct xfs_ifork *ifp)1061{1062 xfs_iext_destroy_node(ifp->if_data, ifp->if_height);1063 1064 ifp->if_bytes = 0;1065 ifp->if_height = 0;1066 ifp->if_data = NULL;1067}1068