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