fs/xfs/xfs_extent_busy.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   4  * Copyright (c) 2010 David Chinner.
   5  * Copyright (c) 2011 Christoph Hellwig.
   6  * All Rights Reserved.
   7  */
   8 #include "xfs.h"
   9 #include "xfs_fs.h"
  10 #include "xfs_format.h"
  11 #include "xfs_log_format.h"
  12 #include "xfs_shared.h"
  13 #include "xfs_trans_resv.h"
  14 #include "xfs_mount.h"
  15 #include "xfs_alloc.h"
  16 #include "xfs_extent_busy.h"
  17 #include "xfs_trace.h"
  18 #include "xfs_trans.h"
  19 #include "xfs_log.h"
  20 #include "xfs_ag.h"
  21
  22 static void
  23 xfs_extent_busy_insert_list(
  24         struct xfs_perag        *pag,
  25         xfs_agblock_t           bno,
  26         xfs_extlen_t            len,
  27         unsigned int            flags,
  28         struct list_head        *busy_list)
  29 {
  30         struct xfs_extent_busy  *new;
  31         struct xfs_extent_busy  *busyp;
  32         struct rb_node          **rbp;
  33         struct rb_node          *parent = NULL;
  34
  35         new = kmem_zalloc(sizeof(struct xfs_extent_busy), 0);
  36         new->agno = pag->pag_agno;
  37         new->bno = bno;
  38         new->length = len;
  39         INIT_LIST_HEAD(&new->list);
  40         new->flags = flags;
  41
  42         /* trace before insert to be able to see failed inserts */
  43         trace_xfs_extent_busy(pag->pag_mount, pag->pag_agno, bno, len);
  44
  45         spin_lock(&pag->pagb_lock);
  46         rbp = &pag->pagb_tree.rb_node;
  47         while (*rbp) {
  48                 parent = *rbp;
  49                 busyp = rb_entry(parent, struct xfs_extent_busy, rb_node);
  50
  51                 if (new->bno < busyp->bno) {
  52                         rbp = &(*rbp)->rb_left;
  53                         ASSERT(new->bno + new->length <= busyp->bno);
  54                 } else if (new->bno > busyp->bno) {
  55                         rbp = &(*rbp)->rb_right;
  56                         ASSERT(bno >= busyp->bno + busyp->length);
  57                 } else {
  58                         ASSERT(0);
  59                 }
  60         }
  61
  62         rb_link_node(&new->rb_node, parent, rbp);
  63         rb_insert_color(&new->rb_node, &pag->pagb_tree);
  64
  65         /* always process discard lists in fifo order */
  66         list_add_tail(&new->list, busy_list);
  67         spin_unlock(&pag->pagb_lock);
  68 }
  69
  70 void
  71 xfs_extent_busy_insert(
  72         struct xfs_trans        *tp,
  73         struct xfs_perag        *pag,
  74         xfs_agblock_t           bno,
  75         xfs_extlen_t            len,
  76         unsigned int            flags)
  77 {
  78         xfs_extent_busy_insert_list(pag, bno, len, flags, &tp->t_busy);
  79 }
  80
  81 void
  82 xfs_extent_busy_insert_discard(
  83         struct xfs_perag        *pag,
  84         xfs_agblock_t           bno,
  85         xfs_extlen_t            len,
  86         struct list_head        *busy_list)
  87 {
  88         xfs_extent_busy_insert_list(pag, bno, len, XFS_EXTENT_BUSY_DISCARDED,
  89                         busy_list);
  90 }
  91
  92 /*
  93  * Search for a busy extent within the range of the extent we are about to
  94  * allocate.  You need to be holding the busy extent tree lock when calling
  95  * xfs_extent_busy_search(). This function returns 0 for no overlapping busy
  96  * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
  97  * match. This is done so that a non-zero return indicates an overlap that
  98  * will require a synchronous transaction, but it can still be
  99  * used to distinguish between a partial or exact match.
 100  */
 101 int
 102 xfs_extent_busy_search(
 103         struct xfs_mount        *mp,
 104         struct xfs_perag        *pag,
 105         xfs_agblock_t           bno,
 106         xfs_extlen_t            len)
 107 {
 108         struct rb_node          *rbp;
 109         struct xfs_extent_busy  *busyp;
 110         int                     match = 0;
 111
 112         /* find closest start bno overlap */
 113         spin_lock(&pag->pagb_lock);
 114         rbp = pag->pagb_tree.rb_node;
 115         while (rbp) {
 116                 busyp = rb_entry(rbp, struct xfs_extent_busy, rb_node);
 117                 if (bno < busyp->bno) {
 118                         /* may overlap, but exact start block is lower */
 119                         if (bno + len > busyp->bno)
 120                                 match = -1;
 121                         rbp = rbp->rb_left;
 122                 } else if (bno > busyp->bno) {
 123                         /* may overlap, but exact start block is higher */
 124                         if (bno < busyp->bno + busyp->length)
 125                                 match = -1;
 126                         rbp = rbp->rb_right;
 127                 } else {
 128                         /* bno matches busyp, length determines exact match */
 129                         match = (busyp->length == len) ? 1 : -1;
 130                         break;
 131                 }
 132         }
 133         spin_unlock(&pag->pagb_lock);
 134         return match;
 135 }
 136
 137 /*
 138  * The found free extent [fbno, fend] overlaps part or all of the given busy
 139  * extent.  If the overlap covers the beginning, the end, or all of the busy
 140  * extent, the overlapping portion can be made unbusy and used for the
 141  * allocation.  We can't split a busy extent because we can't modify a
 142  * transaction/CIL context busy list, but we can update an entry's block
 143  * number or length.
 144  *
 145  * Returns true if the extent can safely be reused, or false if the search
 146  * needs to be restarted.
 147  */
 148 STATIC bool
 149 xfs_extent_busy_update_extent(
 150         struct xfs_mount        *mp,
 151         struct xfs_perag        *pag,
 152         struct xfs_extent_busy  *busyp,
 153         xfs_agblock_t           fbno,
 154         xfs_extlen_t            flen,
 155         bool                    userdata) __releases(&pag->pagb_lock)
 156                                           __acquires(&pag->pagb_lock)
 157 {
 158         xfs_agblock_t           fend = fbno + flen;
 159         xfs_agblock_t           bbno = busyp->bno;
 160         xfs_agblock_t           bend = bbno + busyp->length;
 161
 162         /*
 163          * This extent is currently being discarded.  Give the thread
 164          * performing the discard a chance to mark the extent unbusy
 165          * and retry.
 166          */
 167         if (busyp->flags & XFS_EXTENT_BUSY_DISCARDED) {
 168                 spin_unlock(&pag->pagb_lock);
 169                 delay(1);
 170                 spin_lock(&pag->pagb_lock);
 171                 return false;
 172         }
 173
 174         /*
 175          * If there is a busy extent overlapping a user allocation, we have
 176          * no choice but to force the log and retry the search.
 177          *
 178          * Fortunately this does not happen during normal operation, but
 179          * only if the filesystem is very low on space and has to dip into
 180          * the AGFL for normal allocations.
 181          */
 182         if (userdata)
 183                 goto out_force_log;
 184
 185         if (bbno < fbno && bend > fend) {
 186                 /*
 187                  * Case 1:
 188                  *    bbno           bend
 189                  *    +BBBBBBBBBBBBBBBBB+
 190                  *        +---------+
 191                  *        fbno   fend
 192                  */
 193
 194                 /*
 195                  * We would have to split the busy extent to be able to track
 196                  * it correct, which we cannot do because we would have to
 197                  * modify the list of busy extents attached to the transaction
 198                  * or CIL context, which is immutable.
 199                  *
 200                  * Force out the log to clear the busy extent and retry the
 201                  * search.
 202                  */
 203                 goto out_force_log;
 204         } else if (bbno >= fbno && bend <= fend) {
 205                 /*
 206                  * Case 2:
 207                  *    bbno           bend
 208                  *    +BBBBBBBBBBBBBBBBB+
 209                  *    +-----------------+
 210                  *    fbno           fend
 211                  *
 212                  * Case 3:
 213                  *    bbno           bend
 214                  *    +BBBBBBBBBBBBBBBBB+
 215                  *    +--------------------------+
 216                  *    fbno                    fend
 217                  *
 218                  * Case 4:
 219                  *             bbno           bend
 220                  *             +BBBBBBBBBBBBBBBBB+
 221                  *    +--------------------------+
 222                  *    fbno                    fend
 223                  *
 224                  * Case 5:
 225                  *             bbno           bend
 226                  *             +BBBBBBBBBBBBBBBBB+
 227                  *    +-----------------------------------+
 228                  *    fbno                             fend
 229                  *
 230                  */
 231
 232                 /*
 233                  * The busy extent is fully covered by the extent we are
 234                  * allocating, and can simply be removed from the rbtree.
 235                  * However we cannot remove it from the immutable list
 236                  * tracking busy extents in the transaction or CIL context,
 237                  * so set the length to zero to mark it invalid.
 238                  *
 239                  * We also need to restart the busy extent search from the
 240                  * tree root, because erasing the node can rearrange the
 241                  * tree topology.
 242                  */
 243                 rb_erase(&busyp->rb_node, &pag->pagb_tree);
 244                 busyp->length = 0;
 245                 return false;
 246         } else if (fend < bend) {
 247                 /*
 248                  * Case 6:
 249                  *              bbno           bend
 250                  *             +BBBBBBBBBBBBBBBBB+
 251                  *             +---------+
 252                  *             fbno   fend
 253                  *
 254                  * Case 7:
 255                  *             bbno           bend
 256                  *             +BBBBBBBBBBBBBBBBB+
 257                  *    +------------------+
 258                  *    fbno            fend
 259                  *
 260                  */
 261                 busyp->bno = fend;
 262                 busyp->length = bend - fend;
 263         } else if (bbno < fbno) {
 264                 /*
 265                  * Case 8:
 266                  *    bbno           bend
 267                  *    +BBBBBBBBBBBBBBBBB+
 268                  *        +-------------+
 269                  *        fbno       fend
 270                  *
 271                  * Case 9:
 272                  *    bbno           bend
 273                  *    +BBBBBBBBBBBBBBBBB+
 274                  *        +----------------------+
 275                  *        fbno                fend
 276                  */
 277                 busyp->length = fbno - busyp->bno;
 278         } else {
 279                 ASSERT(0);
 280         }
 281
 282         trace_xfs_extent_busy_reuse(mp, pag->pag_agno, fbno, flen);
 283         return true;
 284
 285 out_force_log:
 286         spin_unlock(&pag->pagb_lock);
 287         xfs_log_force(mp, XFS_LOG_SYNC);
 288         trace_xfs_extent_busy_force(mp, pag->pag_agno, fbno, flen);
 289         spin_lock(&pag->pagb_lock);
 290         return false;
 291 }
 292
 293
 294 /*
 295  * For a given extent [fbno, flen], make sure we can reuse it safely.
 296  */
 297 void
 298 xfs_extent_busy_reuse(
 299         struct xfs_mount        *mp,
 300         struct xfs_perag        *pag,
 301         xfs_agblock_t           fbno,
 302         xfs_extlen_t            flen,
 303         bool                    userdata)
 304 {
 305         struct rb_node          *rbp;
 306
 307         ASSERT(flen > 0);
 308         spin_lock(&pag->pagb_lock);
 309 restart:
 310         rbp = pag->pagb_tree.rb_node;
 311         while (rbp) {
 312                 struct xfs_extent_busy *busyp =
 313                         rb_entry(rbp, struct xfs_extent_busy, rb_node);
 314                 xfs_agblock_t   bbno = busyp->bno;
 315                 xfs_agblock_t   bend = bbno + busyp->length;
 316
 317                 if (fbno + flen <= bbno) {
 318                         rbp = rbp->rb_left;
 319                         continue;
 320                 } else if (fbno >= bend) {
 321                         rbp = rbp->rb_right;
 322                         continue;
 323                 }
 324
 325                 if (!xfs_extent_busy_update_extent(mp, pag, busyp, fbno, flen,
 326                                                   userdata))
 327                         goto restart;
 328         }
 329         spin_unlock(&pag->pagb_lock);
 330 }
 331
 332 /*
 333  * For a given extent [fbno, flen], search the busy extent list to find a
 334  * subset of the extent that is not busy.  If *rlen is smaller than
 335  * args->minlen no suitable extent could be found, and the higher level
 336  * code needs to force out the log and retry the allocation.
 337  *
 338  * Return the current busy generation for the AG if the extent is busy. This
 339  * value can be used to wait for at least one of the currently busy extents
 340  * to be cleared. Note that the busy list is not guaranteed to be empty after
 341  * the gen is woken. The state of a specific extent must always be confirmed
 342  * with another call to xfs_extent_busy_trim() before it can be used.
 343  */
 344 bool
 345 xfs_extent_busy_trim(
 346         struct xfs_alloc_arg    *args,
 347         xfs_agblock_t           *bno,
 348         xfs_extlen_t            *len,
 349         unsigned                *busy_gen)
 350 {
 351         xfs_agblock_t           fbno;
 352         xfs_extlen_t            flen;
 353         struct rb_node          *rbp;
 354         bool                    ret = false;
 355
 356         ASSERT(*len > 0);
 357
 358         spin_lock(&args->pag->pagb_lock);
 359         fbno = *bno;
 360         flen = *len;
 361         rbp = args->pag->pagb_tree.rb_node;
 362         while (rbp && flen >= args->minlen) {
 363                 struct xfs_extent_busy *busyp =
 364                         rb_entry(rbp, struct xfs_extent_busy, rb_node);
 365                 xfs_agblock_t   fend = fbno + flen;
 366                 xfs_agblock_t   bbno = busyp->bno;
 367                 xfs_agblock_t   bend = bbno + busyp->length;
 368
 369                 if (fend <= bbno) {
 370                         rbp = rbp->rb_left;
 371                         continue;
 372                 } else if (fbno >= bend) {
 373                         rbp = rbp->rb_right;
 374                         continue;
 375                 }
 376
 377                 if (bbno <= fbno) {
 378                         /* start overlap */
 379
 380                         /*
 381                          * Case 1:
 382                          *    bbno           bend
 383                          *    +BBBBBBBBBBBBBBBBB+
 384                          *        +---------+
 385                          *        fbno   fend
 386                          *
 387                          * Case 2:
 388                          *    bbno           bend
 389                          *    +BBBBBBBBBBBBBBBBB+
 390                          *    +-------------+
 391                          *    fbno       fend
 392                          *
 393                          * Case 3:
 394                          *    bbno           bend
 395                          *    +BBBBBBBBBBBBBBBBB+
 396                          *        +-------------+
 397                          *        fbno       fend
 398                          *
 399                          * Case 4:
 400                          *    bbno           bend
 401                          *    +BBBBBBBBBBBBBBBBB+
 402                          *    +-----------------+
 403                          *    fbno           fend
 404                          *
 405                          * No unbusy region in extent, return failure.
 406                          */
 407                         if (fend <= bend)
 408                                 goto fail;
 409
 410                         /*
 411                          * Case 5:
 412                          *    bbno           bend
 413                          *    +BBBBBBBBBBBBBBBBB+
 414                          *        +----------------------+
 415                          *        fbno                fend
 416                          *
 417                          * Case 6:
 418                          *    bbno           bend
 419                          *    +BBBBBBBBBBBBBBBBB+
 420                          *    +--------------------------+
 421                          *    fbno                    fend
 422                          *
 423                          * Needs to be trimmed to:
 424                          *                       +-------+
 425                          *                       fbno fend
 426                          */
 427                         fbno = bend;
 428                 } else if (bend >= fend) {
 429                         /* end overlap */
 430
 431                         /*
 432                          * Case 7:
 433                          *             bbno           bend
 434                          *             +BBBBBBBBBBBBBBBBB+
 435                          *    +------------------+
 436                          *    fbno            fend
 437                          *
 438                          * Case 8:
 439                          *             bbno           bend
 440                          *             +BBBBBBBBBBBBBBBBB+
 441                          *    +--------------------------+
 442                          *    fbno                    fend
 443                          *
 444                          * Needs to be trimmed to:
 445                          *    +-------+
 446                          *    fbno fend
 447                          */
 448                         fend = bbno;
 449                 } else {
 450                         /* middle overlap */
 451
 452                         /*
 453                          * Case 9:
 454                          *             bbno           bend
 455                          *             +BBBBBBBBBBBBBBBBB+
 456                          *    +-----------------------------------+
 457                          *    fbno                             fend
 458                          *
 459                          * Can be trimmed to:
 460                          *    +-------+        OR         +-------+
 461                          *    fbno fend                   fbno fend
 462                          *
 463                          * Backward allocation leads to significant
 464                          * fragmentation of directories, which degrades
 465                          * directory performance, therefore we always want to
 466                          * choose the option that produces forward allocation
 467                          * patterns.
 468                          * Preferring the lower bno extent will make the next
 469                          * request use "fend" as the start of the next
 470                          * allocation;  if the segment is no longer busy at
 471                          * that point, we'll get a contiguous allocation, but
 472                          * even if it is still busy, we will get a forward
 473                          * allocation.
 474                          * We try to avoid choosing the segment at "bend",
 475                          * because that can lead to the next allocation
 476                          * taking the segment at "fbno", which would be a
 477                          * backward allocation.  We only use the segment at
 478                          * "fbno" if it is much larger than the current
 479                          * requested size, because in that case there's a
 480                          * good chance subsequent allocations will be
 481                          * contiguous.
 482                          */
 483                         if (bbno - fbno >= args->maxlen) {
 484                                 /* left candidate fits perfect */
 485                                 fend = bbno;
 486                         } else if (fend - bend >= args->maxlen * 4) {
 487                                 /* right candidate has enough free space */
 488                                 fbno = bend;
 489                         } else if (bbno - fbno >= args->minlen) {
 490                                 /* left candidate fits minimum requirement */
 491                                 fend = bbno;
 492                         } else {
 493                                 goto fail;
 494                         }
 495                 }
 496
 497                 flen = fend - fbno;
 498         }
 499 out:
 500
 501         if (fbno != *bno || flen != *len) {
 502                 trace_xfs_extent_busy_trim(args->mp, args->agno, *bno, *len,
 503                                           fbno, flen);
 504                 *bno = fbno;
 505                 *len = flen;
 506                 *busy_gen = args->pag->pagb_gen;
 507                 ret = true;
 508         }
 509         spin_unlock(&args->pag->pagb_lock);
 510         return ret;
 511 fail:
 512         /*
 513          * Return a zero extent length as failure indications.  All callers
 514          * re-check if the trimmed extent satisfies the minlen requirement.
 515          */
 516         flen = 0;
 517         goto out;
 518 }
 519
 520 STATIC void
 521 xfs_extent_busy_clear_one(
 522         struct xfs_mount        *mp,
 523         struct xfs_perag        *pag,
 524         struct xfs_extent_busy  *busyp)
 525 {
 526         if (busyp->length) {
 527                 trace_xfs_extent_busy_clear(mp, busyp->agno, busyp->bno,
 528                                                 busyp->length);
 529                 rb_erase(&busyp->rb_node, &pag->pagb_tree);
 530         }
 531
 532         list_del_init(&busyp->list);
 533         kmem_free(busyp);
 534 }
 535
 536 static void
 537 xfs_extent_busy_put_pag(
 538         struct xfs_perag        *pag,
 539         bool                    wakeup)
 540                 __releases(pag->pagb_lock)
 541 {
 542         if (wakeup) {
 543                 pag->pagb_gen++;
 544                 wake_up_all(&pag->pagb_wait);
 545         }
 546
 547         spin_unlock(&pag->pagb_lock);
 548         xfs_perag_put(pag);
 549 }
 550
 551 /*
 552  * Remove all extents on the passed in list from the busy extents tree.
 553  * If do_discard is set skip extents that need to be discarded, and mark
 554  * these as undergoing a discard operation instead.
 555  */
 556 void
 557 xfs_extent_busy_clear(
 558         struct xfs_mount        *mp,
 559         struct list_head        *list,
 560         bool                    do_discard)
 561 {
 562         struct xfs_extent_busy  *busyp, *n;
 563         struct xfs_perag        *pag = NULL;
 564         xfs_agnumber_t          agno = NULLAGNUMBER;
 565         bool                    wakeup = false;
 566
 567         list_for_each_entry_safe(busyp, n, list, list) {
 568                 if (busyp->agno != agno) {
 569                         if (pag)
 570                                 xfs_extent_busy_put_pag(pag, wakeup);
 571                         agno = busyp->agno;
 572                         pag = xfs_perag_get(mp, agno);
 573                         spin_lock(&pag->pagb_lock);
 574                         wakeup = false;
 575                 }
 576
 577                 if (do_discard && busyp->length &&
 578                     !(busyp->flags & XFS_EXTENT_BUSY_SKIP_DISCARD)) {
 579                         busyp->flags = XFS_EXTENT_BUSY_DISCARDED;
 580                 } else {
 581                         xfs_extent_busy_clear_one(mp, pag, busyp);
 582                         wakeup = true;
 583                 }
 584         }
 585
 586         if (pag)
 587                 xfs_extent_busy_put_pag(pag, wakeup);
 588 }
 589
 590 /*
 591  * Flush out all busy extents for this AG.
 592  *
 593  * If the current transaction is holding busy extents, the caller may not want
 594  * to wait for committed busy extents to resolve. If we are being told just to
 595  * try a flush or progress has been made since we last skipped a busy extent,
 596  * return immediately to allow the caller to try again.
 597  *
 598  * If we are freeing extents, we might actually be holding the only free extents
 599  * in the transaction busy list and the log force won't resolve that situation.
 600  * In this case, we must return -EAGAIN to avoid a deadlock by informing the
 601  * caller it needs to commit the busy extents it holds before retrying the
 602  * extent free operation.
 603  */
 604 int
 605 xfs_extent_busy_flush(
 606         struct xfs_trans        *tp,
 607         struct xfs_perag        *pag,
 608         unsigned                busy_gen,
 609         uint32_t                alloc_flags)
 610 {
 611         DEFINE_WAIT             (wait);
 612         int                     error;
 613
 614         error = xfs_log_force(tp->t_mountp, XFS_LOG_SYNC);
 615         if (error)
 616                 return error;
 617
 618         /* Avoid deadlocks on uncommitted busy extents. */
 619         if (!list_empty(&tp->t_busy)) {
 620                 if (alloc_flags & XFS_ALLOC_FLAG_TRYFLUSH)
 621                         return 0;
 622
 623                 if (busy_gen != READ_ONCE(pag->pagb_gen))
 624                         return 0;
 625
 626                 if (alloc_flags & XFS_ALLOC_FLAG_FREEING)
 627                         return -EAGAIN;
 628         }
 629
 630         /* Wait for committed busy extents to resolve. */
 631         do {
 632                 prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE);
 633                 if  (busy_gen != READ_ONCE(pag->pagb_gen))
 634                         break;
 635                 schedule();
 636         } while (1);
 637
 638         finish_wait(&pag->pagb_wait, &wait);
 639         return 0;
 640 }
 641
 642 void
 643 xfs_extent_busy_wait_all(
 644         struct xfs_mount        *mp)
 645 {
 646         struct xfs_perag        *pag;
 647         DEFINE_WAIT             (wait);
 648         xfs_agnumber_t          agno;
 649
 650         for_each_perag(mp, agno, pag) {
 651                 do {
 652                         prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE);
 653                         if  (RB_EMPTY_ROOT(&pag->pagb_tree))
 654                                 break;
 655                         schedule();
 656                 } while (1);
 657                 finish_wait(&pag->pagb_wait, &wait);
 658         }
 659 }
 660
 661 /*
 662  * Callback for list_sort to sort busy extents by the AG they reside in.
 663  */
 664 int
 665 xfs_extent_busy_ag_cmp(
 666         void                    *priv,
 667         const struct list_head  *l1,
 668         const struct list_head  *l2)
 669 {
 670         struct xfs_extent_busy  *b1 =
 671                 container_of(l1, struct xfs_extent_busy, list);
 672         struct xfs_extent_busy  *b2 =
 673                 container_of(l2, struct xfs_extent_busy, list);
 674         s32 diff;
 675
 676         diff = b1->agno - b2->agno;
 677         if (!diff)
 678                 diff = b1->bno - b2->bno;
 679         return diff;
 680 }