fs/xfs/xfs_extent_busy.c

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