fs/xfs/libxfs/xfs_iext_tree.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   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
  32 struct 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 an
  39  * unused record.
  40  */
  41 static bool xfs_iext_rec_is_empty(struct xfs_iext_rec *rec)
  42 {
  43         return rec->hi == 0;
  44 }
  45
  46 static inline void xfs_iext_rec_clear(struct xfs_iext_rec *rec)
  47 {
  48         rec->lo = 0;
  49         rec->hi = 0;
  50 }
  51
  52 static void
  53 xfs_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
  71 static void
  72 xfs_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         else
  85                 irec->br_state = XFS_EXT_NORM;
  86 }
  87
  88 enum {
  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 each
 101  * contain the startoffset, blockcount, startblock and unwritten extent flag.
 102  * See above for the exact format, followed by pointers to the previous and next
 103  * leaf blocks (if there are any).
 104  *
 105  * The inner (non-leaf) blocks first contain KEYS_PER_NODE lookup keys, followed
 106  * 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  */
 116 struct 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
 122 struct 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
 128 inline xfs_extnum_t xfs_iext_count(struct xfs_ifork *ifp)
 129 {
 130         return ifp->if_bytes / sizeof(struct xfs_iext_rec);
 131 }
 132
 133 static 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
 140 static inline struct xfs_iext_rec *cur_rec(struct xfs_iext_cursor *cur)
 141 {
 142         return &cur->leaf->recs[cur->pos];
 143 }
 144
 145 static 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
 157 static void *
 158 xfs_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
 175 static void *
 176 xfs_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
 196 void
 197 xfs_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
 205 void
 206 xfs_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
 225 void
 226 xfs_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
 247 void
 248 xfs_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
 261 recurse:
 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
 275 static inline int
 276 xfs_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
 288 static inline int
 289 xfs_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
 303 static void *
 304 xfs_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
 328 static int
 329 xfs_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
 343 static int
 344 xfs_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
 358 static int
 359 xfs_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
 373 static int
 374 xfs_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
 389 static inline uint64_t
 390 xfs_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
 397 static void
 398 xfs_iext_grow(
 399         struct xfs_ifork        *ifp)
 400 {
 401         struct xfs_iext_node    *node = kmem_zalloc(NODE_SIZE, KM_NOFS);
 402         int                     i;
 403
 404         if (ifp->if_height == 1) {
 405                 struct xfs_iext_leaf *prev = ifp->if_data;
 406
 407                 node->keys[0] = xfs_iext_leaf_key(prev, 0);
 408                 node->ptrs[0] = prev;
 409         } else  {
 410                 struct xfs_iext_node *prev = ifp->if_data;
 411
 412                 ASSERT(ifp->if_height > 1);
 413
 414                 node->keys[0] = prev->keys[0];
 415                 node->ptrs[0] = prev;
 416         }
 417
 418         for (i = 1; i < KEYS_PER_NODE; i++)
 419                 node->keys[i] = XFS_IEXT_KEY_INVALID;
 420
 421         ifp->if_data = node;
 422         ifp->if_height++;
 423 }
 424
 425 static void
 426 xfs_iext_update_node(
 427         struct xfs_ifork        *ifp,
 428         xfs_fileoff_t           old_offset,
 429         xfs_fileoff_t           new_offset,
 430         int                     level,
 431         void                    *ptr)
 432 {
 433         struct xfs_iext_node    *node = ifp->if_data;
 434         int                     height, i;
 435
 436         for (height = ifp->if_height; height > level; height--) {
 437                 for (i = 0; i < KEYS_PER_NODE; i++) {
 438                         if (i > 0 && xfs_iext_key_cmp(node, i, old_offset) > 0)
 439                                 break;
 440                         if (node->keys[i] == old_offset)
 441                                 node->keys[i] = new_offset;
 442                 }
 443                 node = node->ptrs[i - 1];
 444                 ASSERT(node);
 445         }
 446
 447         ASSERT(node == ptr);
 448 }
 449
 450 static struct xfs_iext_node *
 451 xfs_iext_split_node(
 452         struct xfs_iext_node    **nodep,
 453         int                     *pos,
 454         int                     *nr_entries)
 455 {
 456         struct xfs_iext_node    *node = *nodep;
 457         struct xfs_iext_node    *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
 458         const int               nr_move = KEYS_PER_NODE / 2;
 459         int                     nr_keep = nr_move + (KEYS_PER_NODE & 1);
 460         int                     i = 0;
 461
 462         /* for sequential append operations just spill over into the new node */
 463         if (*pos == KEYS_PER_NODE) {
 464                 *nodep = new;
 465                 *pos = 0;
 466                 *nr_entries = 0;
 467                 goto done;
 468         }
 469
 470
 471         for (i = 0; i < nr_move; i++) {
 472                 new->keys[i] = node->keys[nr_keep + i];
 473                 new->ptrs[i] = node->ptrs[nr_keep + i];
 474
 475                 node->keys[nr_keep + i] = XFS_IEXT_KEY_INVALID;
 476                 node->ptrs[nr_keep + i] = NULL;
 477         }
 478
 479         if (*pos >= nr_keep) {
 480                 *nodep = new;
 481                 *pos -= nr_keep;
 482                 *nr_entries = nr_move;
 483         } else {
 484                 *nr_entries = nr_keep;
 485         }
 486 done:
 487         for (; i < KEYS_PER_NODE; i++)
 488                 new->keys[i] = XFS_IEXT_KEY_INVALID;
 489         return new;
 490 }
 491
 492 static void
 493 xfs_iext_insert_node(
 494         struct xfs_ifork        *ifp,
 495         uint64_t                offset,
 496         void                    *ptr,
 497         int                     level)
 498 {
 499         struct xfs_iext_node    *node, *new;
 500         int                     i, pos, nr_entries;
 501
 502 again:
 503         if (ifp->if_height < level)
 504                 xfs_iext_grow(ifp);
 505
 506         new = NULL;
 507         node = xfs_iext_find_level(ifp, offset, level);
 508         pos = xfs_iext_node_insert_pos(node, offset);
 509         nr_entries = xfs_iext_node_nr_entries(node, pos);
 510
 511         ASSERT(pos >= nr_entries || xfs_iext_key_cmp(node, pos, offset) != 0);
 512         ASSERT(nr_entries <= KEYS_PER_NODE);
 513
 514         if (nr_entries == KEYS_PER_NODE)
 515                 new = xfs_iext_split_node(&node, &pos, &nr_entries);
 516
 517         /*
 518          * Update the pointers in higher levels if the first entry changes
 519          * in an existing node.
 520          */
 521         if (node != new && pos == 0 && nr_entries > 0)
 522                 xfs_iext_update_node(ifp, node->keys[0], offset, level, node);
 523
 524         for (i = nr_entries; i > pos; i--) {
 525                 node->keys[i] = node->keys[i - 1];
 526                 node->ptrs[i] = node->ptrs[i - 1];
 527         }
 528         node->keys[pos] = offset;
 529         node->ptrs[pos] = ptr;
 530
 531         if (new) {
 532                 offset = new->keys[0];
 533                 ptr = new;
 534                 level++;
 535                 goto again;
 536         }
 537 }
 538
 539 static struct xfs_iext_leaf *
 540 xfs_iext_split_leaf(
 541         struct xfs_iext_cursor  *cur,
 542         int                     *nr_entries)
 543 {
 544         struct xfs_iext_leaf    *leaf = cur->leaf;
 545         struct xfs_iext_leaf    *new = kmem_zalloc(NODE_SIZE, KM_NOFS);
 546         const int               nr_move = RECS_PER_LEAF / 2;
 547         int                     nr_keep = nr_move + (RECS_PER_LEAF & 1);
 548         int                     i;
 549
 550         /* for sequential append operations just spill over into the new node */
 551         if (cur->pos == RECS_PER_LEAF) {
 552                 cur->leaf = new;
 553                 cur->pos = 0;
 554                 *nr_entries = 0;
 555                 goto done;
 556         }
 557
 558         for (i = 0; i < nr_move; i++) {
 559                 new->recs[i] = leaf->recs[nr_keep + i];
 560                 xfs_iext_rec_clear(&leaf->recs[nr_keep + i]);
 561         }
 562
 563         if (cur->pos >= nr_keep) {
 564                 cur->leaf = new;
 565                 cur->pos -= nr_keep;
 566                 *nr_entries = nr_move;
 567         } else {
 568                 *nr_entries = nr_keep;
 569         }
 570 done:
 571         if (leaf->next)
 572                 leaf->next->prev = new;
 573         new->next = leaf->next;
 574         new->prev = leaf;
 575         leaf->next = new;
 576         return new;
 577 }
 578
 579 static void
 580 xfs_iext_alloc_root(
 581         struct xfs_ifork        *ifp,
 582         struct xfs_iext_cursor  *cur)
 583 {
 584         ASSERT(ifp->if_bytes == 0);
 585
 586         ifp->if_data = kmem_zalloc(sizeof(struct xfs_iext_rec), KM_NOFS);
 587         ifp->if_height = 1;
 588
 589         /* now that we have a node step into it */
 590         cur->leaf = ifp->if_data;
 591         cur->pos = 0;
 592 }
 593
 594 static void
 595 xfs_iext_realloc_root(
 596         struct xfs_ifork        *ifp,
 597         struct xfs_iext_cursor  *cur)
 598 {
 599         int64_t new_size = ifp->if_bytes + sizeof(struct xfs_iext_rec);
 600         void *new;
 601
 602         /* account for the prev/next pointers */
 603         if (new_size / sizeof(struct xfs_iext_rec) == RECS_PER_LEAF)
 604                 new_size = NODE_SIZE;
 605
 606         new = krealloc(ifp->if_data, new_size, GFP_NOFS | __GFP_NOFAIL);
 607         memset(new + ifp->if_bytes, 0, new_size - ifp->if_bytes);
 608         ifp->if_data = new;
 609         cur->leaf = new;
 610 }
 611
 612 /*
 613  * Increment the sequence counter on extent tree changes. If we are on a COW
 614  * fork, this allows the writeback code to skip looking for a COW extent if the
 615  * COW fork hasn't changed. We use WRITE_ONCE here to ensure the update to the
 616  * sequence counter is seen before the modifications to the extent tree itself
 617  * take effect.
 618  */
 619 static inline void xfs_iext_inc_seq(struct xfs_ifork *ifp)
 620 {
 621         WRITE_ONCE(ifp->if_seq, READ_ONCE(ifp->if_seq) + 1);
 622 }
 623
 624 void
 625 xfs_iext_insert_raw(
 626         struct xfs_ifork        *ifp,
 627         struct xfs_iext_cursor  *cur,
 628         struct xfs_bmbt_irec    *irec)
 629 {
 630         xfs_fileoff_t           offset = irec->br_startoff;
 631         struct xfs_iext_leaf    *new = NULL;
 632         int                     nr_entries, i;
 633
 634         xfs_iext_inc_seq(ifp);
 635
 636         if (ifp->if_height == 0)
 637                 xfs_iext_alloc_root(ifp, cur);
 638         else if (ifp->if_height == 1)
 639                 xfs_iext_realloc_root(ifp, cur);
 640
 641         nr_entries = xfs_iext_leaf_nr_entries(ifp, cur->leaf, cur->pos);
 642         ASSERT(nr_entries <= RECS_PER_LEAF);
 643         ASSERT(cur->pos >= nr_entries ||
 644                xfs_iext_rec_cmp(cur_rec(cur), irec->br_startoff) != 0);
 645
 646         if (nr_entries == RECS_PER_LEAF)
 647                 new = xfs_iext_split_leaf(cur, &nr_entries);
 648
 649         /*
 650          * Update the pointers in higher levels if the first entry changes
 651          * in an existing node.
 652          */
 653         if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) {
 654                 xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0),
 655                                 offset, 1, cur->leaf);
 656         }
 657
 658         for (i = nr_entries; i > cur->pos; i--)
 659                 cur->leaf->recs[i] = cur->leaf->recs[i - 1];
 660         xfs_iext_set(cur_rec(cur), irec);
 661         ifp->if_bytes += sizeof(struct xfs_iext_rec);
 662
 663         if (new)
 664                 xfs_iext_insert_node(ifp, xfs_iext_leaf_key(new, 0), new, 2);
 665 }
 666
 667 void
 668 xfs_iext_insert(
 669         struct xfs_inode        *ip,
 670         struct xfs_iext_cursor  *cur,
 671         struct xfs_bmbt_irec    *irec,
 672         int                     state)
 673 {
 674         struct xfs_ifork        *ifp = xfs_iext_state_to_fork(ip, state);
 675
 676         xfs_iext_insert_raw(ifp, cur, irec);
 677         trace_xfs_iext_insert(ip, cur, state, _RET_IP_);
 678 }
 679
 680 static struct xfs_iext_node *
 681 xfs_iext_rebalance_node(
 682         struct xfs_iext_node    *parent,
 683         int                     *pos,
 684         struct xfs_iext_node    *node,
 685         int                     nr_entries)
 686 {
 687         /*
 688          * If the neighbouring nodes are completely full, or have different
 689          * parents, we might never be able to merge our node, and will only
 690          * delete it once the number of entries hits zero.
 691          */
 692         if (nr_entries == 0)
 693                 return node;
 694
 695         if (*pos > 0) {
 696                 struct xfs_iext_node *prev = parent->ptrs[*pos - 1];
 697                 int nr_prev = xfs_iext_node_nr_entries(prev, 0), i;
 698
 699                 if (nr_prev + nr_entries <= KEYS_PER_NODE) {
 700                         for (i = 0; i < nr_entries; i++) {
 701                                 prev->keys[nr_prev + i] = node->keys[i];
 702                                 prev->ptrs[nr_prev + i] = node->ptrs[i];
 703                         }
 704                         return node;
 705                 }
 706         }
 707
 708         if (*pos + 1 < xfs_iext_node_nr_entries(parent, *pos)) {
 709                 struct xfs_iext_node *next = parent->ptrs[*pos + 1];
 710                 int nr_next = xfs_iext_node_nr_entries(next, 0), i;
 711
 712                 if (nr_entries + nr_next <= KEYS_PER_NODE) {
 713                         /*
 714                          * Merge the next node into this node so that we don't
 715                          * have to do an additional update of the keys in the
 716                          * higher levels.
 717                          */
 718                         for (i = 0; i < nr_next; i++) {
 719                                 node->keys[nr_entries + i] = next->keys[i];
 720                                 node->ptrs[nr_entries + i] = next->ptrs[i];
 721                         }
 722
 723                         ++*pos;
 724                         return next;
 725                 }
 726         }
 727
 728         return NULL;
 729 }
 730
 731 static void
 732 xfs_iext_remove_node(
 733         struct xfs_ifork        *ifp,
 734         xfs_fileoff_t           offset,
 735         void                    *victim)
 736 {
 737         struct xfs_iext_node    *node, *parent;
 738         int                     level = 2, pos, nr_entries, i;
 739
 740         ASSERT(level <= ifp->if_height);
 741         node = xfs_iext_find_level(ifp, offset, level);
 742         pos = xfs_iext_node_pos(node, offset);
 743 again:
 744         ASSERT(node->ptrs[pos]);
 745         ASSERT(node->ptrs[pos] == victim);
 746         kmem_free(victim);
 747
 748         nr_entries = xfs_iext_node_nr_entries(node, pos) - 1;
 749         offset = node->keys[0];
 750         for (i = pos; i < nr_entries; i++) {
 751                 node->keys[i] = node->keys[i + 1];
 752                 node->ptrs[i] = node->ptrs[i + 1];
 753         }
 754         node->keys[nr_entries] = XFS_IEXT_KEY_INVALID;
 755         node->ptrs[nr_entries] = NULL;
 756
 757         if (pos == 0 && nr_entries > 0) {
 758                 xfs_iext_update_node(ifp, offset, node->keys[0], level, node);
 759                 offset = node->keys[0];
 760         }
 761
 762         if (nr_entries >= KEYS_PER_NODE / 2)
 763                 return;
 764
 765         if (level < ifp->if_height) {
 766                 /*
 767                  * If we aren't at the root yet try to find a neighbour node to
 768                  * merge with (or delete the node if it is empty), and then
 769                  * recurse up to the next level.
 770                  */
 771                 level++;
 772                 parent = xfs_iext_find_level(ifp, offset, level);
 773                 pos = xfs_iext_node_pos(parent, offset);
 774
 775                 ASSERT(pos != KEYS_PER_NODE);
 776                 ASSERT(parent->ptrs[pos] == node);
 777
 778                 node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries);
 779                 if (node) {
 780                         victim = node;
 781                         node = parent;
 782                         goto again;
 783                 }
 784         } else if (nr_entries == 1) {
 785                 /*
 786                  * If we are at the root and only one entry is left we can just
 787                  * free this node and update the root pointer.
 788                  */
 789                 ASSERT(node == ifp->if_data);
 790                 ifp->if_data = node->ptrs[0];
 791                 ifp->if_height--;
 792                 kmem_free(node);
 793         }
 794 }
 795
 796 static void
 797 xfs_iext_rebalance_leaf(
 798         struct xfs_ifork        *ifp,
 799         struct xfs_iext_cursor  *cur,
 800         struct xfs_iext_leaf    *leaf,
 801         xfs_fileoff_t           offset,
 802         int                     nr_entries)
 803 {
 804         /*
 805          * If the neighbouring nodes are completely full we might never be able
 806          * to merge our node, and will only delete it once the number of
 807          * entries hits zero.
 808          */
 809         if (nr_entries == 0)
 810                 goto remove_node;
 811
 812         if (leaf->prev) {
 813                 int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i;
 814
 815                 if (nr_prev + nr_entries <= RECS_PER_LEAF) {
 816                         for (i = 0; i < nr_entries; i++)
 817                                 leaf->prev->recs[nr_prev + i] = leaf->recs[i];
 818
 819                         if (cur->leaf == leaf) {
 820                                 cur->leaf = leaf->prev;
 821                                 cur->pos += nr_prev;
 822                         }
 823                         goto remove_node;
 824                 }
 825         }
 826
 827         if (leaf->next) {
 828                 int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i;
 829
 830                 if (nr_entries + nr_next <= RECS_PER_LEAF) {
 831                         /*
 832                          * Merge the next node into this node so that we don't
 833                          * have to do an additional update of the keys in the
 834                          * higher levels.
 835                          */
 836                         for (i = 0; i < nr_next; i++) {
 837                                 leaf->recs[nr_entries + i] =
 838                                         leaf->next->recs[i];
 839                         }
 840
 841                         if (cur->leaf == leaf->next) {
 842                                 cur->leaf = leaf;
 843                                 cur->pos += nr_entries;
 844                         }
 845
 846                         offset = xfs_iext_leaf_key(leaf->next, 0);
 847                         leaf = leaf->next;
 848                         goto remove_node;
 849                 }
 850         }
 851
 852         return;
 853 remove_node:
 854         if (leaf->prev)
 855                 leaf->prev->next = leaf->next;
 856         if (leaf->next)
 857                 leaf->next->prev = leaf->prev;
 858         xfs_iext_remove_node(ifp, offset, leaf);
 859 }
 860
 861 static void
 862 xfs_iext_free_last_leaf(
 863         struct xfs_ifork        *ifp)
 864 {
 865         ifp->if_height--;
 866         kmem_free(ifp->if_data);
 867         ifp->if_data = NULL;
 868 }
 869
 870 void
 871 xfs_iext_remove(
 872         struct xfs_inode        *ip,
 873         struct xfs_iext_cursor  *cur,
 874         int                     state)
 875 {
 876         struct xfs_ifork        *ifp = xfs_iext_state_to_fork(ip, state);
 877         struct xfs_iext_leaf    *leaf = cur->leaf;
 878         xfs_fileoff_t           offset = xfs_iext_leaf_key(leaf, 0);
 879         int                     i, nr_entries;
 880
 881         trace_xfs_iext_remove(ip, cur, state, _RET_IP_);
 882
 883         ASSERT(ifp->if_height > 0);
 884         ASSERT(ifp->if_data != NULL);
 885         ASSERT(xfs_iext_valid(ifp, cur));
 886
 887         xfs_iext_inc_seq(ifp);
 888
 889         nr_entries = xfs_iext_leaf_nr_entries(ifp, leaf, cur->pos) - 1;
 890         for (i = cur->pos; i < nr_entries; i++)
 891                 leaf->recs[i] = leaf->recs[i + 1];
 892         xfs_iext_rec_clear(&leaf->recs[nr_entries]);
 893         ifp->if_bytes -= sizeof(struct xfs_iext_rec);
 894
 895         if (cur->pos == 0 && nr_entries > 0) {
 896                 xfs_iext_update_node(ifp, offset, xfs_iext_leaf_key(leaf, 0), 1,
 897                                 leaf);
 898                 offset = xfs_iext_leaf_key(leaf, 0);
 899         } else if (cur->pos == nr_entries) {
 900                 if (ifp->if_height > 1 && leaf->next)
 901                         cur->leaf = leaf->next;
 902                 else
 903                         cur->leaf = NULL;
 904                 cur->pos = 0;
 905         }
 906
 907         if (nr_entries >= RECS_PER_LEAF / 2)
 908                 return;
 909
 910         if (ifp->if_height > 1)
 911                 xfs_iext_rebalance_leaf(ifp, cur, leaf, offset, nr_entries);
 912         else if (nr_entries == 0)
 913                 xfs_iext_free_last_leaf(ifp);
 914 }
 915
 916 /*
 917  * Lookup the extent covering bno.
 918  *
 919  * If there is an extent covering bno return the extent index, and store the
 920  * expanded extent structure in *gotp, and the extent cursor in *cur.
 921  * If there is no extent covering bno, but there is an extent after it (e.g.
 922  * it lies in a hole) return that extent in *gotp and its cursor in *cur
 923  * instead.
 924  * If bno is beyond the last extent return false, and return an invalid
 925  * cursor value.
 926  */
 927 bool
 928 xfs_iext_lookup_extent(
 929         struct xfs_inode        *ip,
 930         struct xfs_ifork        *ifp,
 931         xfs_fileoff_t           offset,
 932         struct xfs_iext_cursor  *cur,
 933         struct xfs_bmbt_irec    *gotp)
 934 {
 935         XFS_STATS_INC(ip->i_mount, xs_look_exlist);
 936
 937         cur->leaf = xfs_iext_find_level(ifp, offset, 1);
 938         if (!cur->leaf) {
 939                 cur->pos = 0;
 940                 return false;
 941         }
 942
 943         for (cur->pos = 0; cur->pos < xfs_iext_max_recs(ifp); cur->pos++) {
 944                 struct xfs_iext_rec *rec = cur_rec(cur);
 945
 946                 if (xfs_iext_rec_is_empty(rec))
 947                         break;
 948                 if (xfs_iext_rec_cmp(rec, offset) >= 0)
 949                         goto found;
 950         }
 951
 952         /* Try looking in the next node for an entry > offset */
 953         if (ifp->if_height == 1 || !cur->leaf->next)
 954                 return false;
 955         cur->leaf = cur->leaf->next;
 956         cur->pos = 0;
 957         if (!xfs_iext_valid(ifp, cur))
 958                 return false;
 959 found:
 960         xfs_iext_get(gotp, cur_rec(cur));
 961         return true;
 962 }
 963
 964 /*
 965  * Returns the last extent before end, and if this extent doesn't cover
 966  * end, update end to the end of the extent.
 967  */
 968 bool
 969 xfs_iext_lookup_extent_before(
 970         struct xfs_inode        *ip,
 971         struct xfs_ifork        *ifp,
 972         xfs_fileoff_t           *end,
 973         struct xfs_iext_cursor  *cur,
 974         struct xfs_bmbt_irec    *gotp)
 975 {
 976         /* could be optimized to not even look up the next on a match.. */
 977         if (xfs_iext_lookup_extent(ip, ifp, *end - 1, cur, gotp) &&
 978             gotp->br_startoff <= *end - 1)
 979                 return true;
 980         if (!xfs_iext_prev_extent(ifp, cur, gotp))
 981                 return false;
 982         *end = gotp->br_startoff + gotp->br_blockcount;
 983         return true;
 984 }
 985
 986 void
 987 xfs_iext_update_extent(
 988         struct xfs_inode        *ip,
 989         int                     state,
 990         struct xfs_iext_cursor  *cur,
 991         struct xfs_bmbt_irec    *new)
 992 {
 993         struct xfs_ifork        *ifp = xfs_iext_state_to_fork(ip, state);
 994
 995         xfs_iext_inc_seq(ifp);
 996
 997         if (cur->pos == 0) {
 998                 struct xfs_bmbt_irec    old;
 999
1000                 xfs_iext_get(&old, cur_rec(cur));
1001                 if (new->br_startoff != old.br_startoff) {
1002                         xfs_iext_update_node(ifp, old.br_startoff,
1003                                         new->br_startoff, 1, cur->leaf);
1004                 }
1005         }
1006
1007         trace_xfs_bmap_pre_update(ip, cur, state, _RET_IP_);
1008         xfs_iext_set(cur_rec(cur), new);
1009         trace_xfs_bmap_post_update(ip, cur, state, _RET_IP_);
1010 }
1011
1012 /*
1013  * Return true if the cursor points at an extent and return the extent structure
1014  * in gotp.  Else return false.
1015  */
1016 bool
1017 xfs_iext_get_extent(
1018         struct xfs_ifork        *ifp,
1019         struct xfs_iext_cursor  *cur,
1020         struct xfs_bmbt_irec    *gotp)
1021 {
1022         if (!xfs_iext_valid(ifp, cur))
1023                 return false;
1024         xfs_iext_get(gotp, cur_rec(cur));
1025         return true;
1026 }
1027
1028 /*
1029  * This is a recursive function, because of that we need to be extremely
1030  * careful with stack usage.
1031  */
1032 static void
1033 xfs_iext_destroy_node(
1034         struct xfs_iext_node    *node,
1035         int                     level)
1036 {
1037         int                     i;
1038
1039         if (level > 1) {
1040                 for (i = 0; i < KEYS_PER_NODE; i++) {
1041                         if (node->keys[i] == XFS_IEXT_KEY_INVALID)
1042                                 break;
1043                         xfs_iext_destroy_node(node->ptrs[i], level - 1);
1044                 }
1045         }
1046
1047         kmem_free(node);
1048 }
1049
1050 void
1051 xfs_iext_destroy(
1052         struct xfs_ifork        *ifp)
1053 {
1054         xfs_iext_destroy_node(ifp->if_data, ifp->if_height);
1055
1056         ifp->if_bytes = 0;
1057         ifp->if_height = 0;
1058         ifp->if_data = NULL;
1059 }