fs/xfs/scrub/xfarray.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Copyright (C) 2021-2023 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <[email protected]>
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_format.h"
  10 #include "scrub/scrub.h"
  11 #include "scrub/xfile.h"
  12 #include "scrub/xfarray.h"
  13 #include "scrub/trace.h"
  14
  15 /*
  16  * Large Arrays of Fixed-Size Records
  17  * ==================================
  18  *
  19  * This memory array uses an xfile (which itself is a shmem file) to store
  20  * large numbers of fixed-size records in memory that can be paged out.  This
  21  * puts less stress on the memory reclaim algorithms during an online repair
  22  * because we don't have to pin so much memory.  However, array access is less
  23  * direct than would be in a regular memory array.  Access to the array is
  24  * performed via indexed load and store methods, and an append method is
  25  * provided for convenience.  Array elements can be unset, which sets them to
  26  * all zeroes.  Unset entries are skipped during iteration, though direct loads
  27  * will return a zeroed buffer.  Callers are responsible for concurrency
  28  * control.
  29  */
  30
  31 /*
  32  * Pointer to scratch space.  Because we can't access the xfile data directly,
  33  * we allocate a small amount of memory on the end of the xfarray structure to
  34  * buffer array items when we need space to store values temporarily.
  35  */
  36 static inline void *xfarray_scratch(struct xfarray *array)
  37 {
  38         return (array + 1);
  39 }
  40
  41 /* Compute array index given an xfile offset. */
  42 static xfarray_idx_t
  43 xfarray_idx(
  44         struct xfarray  *array,
  45         loff_t          pos)
  46 {
  47         if (array->obj_size_log >= 0)
  48                 return (xfarray_idx_t)pos >> array->obj_size_log;
  49
  50         return div_u64((xfarray_idx_t)pos, array->obj_size);
  51 }
  52
  53 /* Compute xfile offset of array element. */
  54 static inline loff_t xfarray_pos(struct xfarray *array, xfarray_idx_t idx)
  55 {
  56         if (array->obj_size_log >= 0)
  57                 return idx << array->obj_size_log;
  58
  59         return idx * array->obj_size;
  60 }
  61
  62 /*
  63  * Initialize a big memory array.  Array records cannot be larger than a
  64  * page, and the array cannot span more bytes than the page cache supports.
  65  * If @required_capacity is nonzero, the maximum array size will be set to this
  66  * quantity and the array creation will fail if the underlying storage cannot
  67  * support that many records.
  68  */
  69 int
  70 xfarray_create(
  71         const char              *description,
  72         unsigned long long      required_capacity,
  73         size_t                  obj_size,
  74         struct xfarray          **arrayp)
  75 {
  76         struct xfarray          *array;
  77         struct xfile            *xfile;
  78         int                     error;
  79
  80         ASSERT(obj_size < PAGE_SIZE);
  81
  82         error = xfile_create(description, 0, &xfile);
  83         if (error)
  84                 return error;
  85
  86         error = -ENOMEM;
  87         array = kzalloc(sizeof(struct xfarray) + obj_size, XCHK_GFP_FLAGS);
  88         if (!array)
  89                 goto out_xfile;
  90
  91         array->xfile = xfile;
  92         array->obj_size = obj_size;
  93
  94         if (is_power_of_2(obj_size))
  95                 array->obj_size_log = ilog2(obj_size);
  96         else
  97                 array->obj_size_log = -1;
  98
  99         array->max_nr = xfarray_idx(array, MAX_LFS_FILESIZE);
 100         trace_xfarray_create(array, required_capacity);
 101
 102         if (required_capacity > 0) {
 103                 if (array->max_nr < required_capacity) {
 104                         error = -ENOMEM;
 105                         goto out_xfarray;
 106                 }
 107                 array->max_nr = required_capacity;
 108         }
 109
 110         *arrayp = array;
 111         return 0;
 112
 113 out_xfarray:
 114         kfree(array);
 115 out_xfile:
 116         xfile_destroy(xfile);
 117         return error;
 118 }
 119
 120 /* Destroy the array. */
 121 void
 122 xfarray_destroy(
 123         struct xfarray  *array)
 124 {
 125         xfile_destroy(array->xfile);
 126         kfree(array);
 127 }
 128
 129 /* Load an element from the array. */
 130 int
 131 xfarray_load(
 132         struct xfarray  *array,
 133         xfarray_idx_t   idx,
 134         void            *ptr)
 135 {
 136         if (idx >= array->nr)
 137                 return -ENODATA;
 138
 139         return xfile_load(array->xfile, ptr, array->obj_size,
 140                         xfarray_pos(array, idx));
 141 }
 142
 143 /* Is this array element potentially unset? */
 144 static inline bool
 145 xfarray_is_unset(
 146         struct xfarray  *array,
 147         loff_t          pos)
 148 {
 149         void            *temp = xfarray_scratch(array);
 150         int             error;
 151
 152         if (array->unset_slots == 0)
 153                 return false;
 154
 155         error = xfile_load(array->xfile, temp, array->obj_size, pos);
 156         if (!error && xfarray_element_is_null(array, temp))
 157                 return true;
 158
 159         return false;
 160 }
 161
 162 /*
 163  * Unset an array element.  If @idx is the last element in the array, the
 164  * array will be truncated.  Otherwise, the entry will be zeroed.
 165  */
 166 int
 167 xfarray_unset(
 168         struct xfarray  *array,
 169         xfarray_idx_t   idx)
 170 {
 171         void            *temp = xfarray_scratch(array);
 172         loff_t          pos = xfarray_pos(array, idx);
 173         int             error;
 174
 175         if (idx >= array->nr)
 176                 return -ENODATA;
 177
 178         if (idx == array->nr - 1) {
 179                 array->nr--;
 180                 return 0;
 181         }
 182
 183         if (xfarray_is_unset(array, pos))
 184                 return 0;
 185
 186         memset(temp, 0, array->obj_size);
 187         error = xfile_store(array->xfile, temp, array->obj_size, pos);
 188         if (error)
 189                 return error;
 190
 191         array->unset_slots++;
 192         return 0;
 193 }
 194
 195 /*
 196  * Store an element in the array.  The element must not be completely zeroed,
 197  * because those are considered unset sparse elements.
 198  */
 199 int
 200 xfarray_store(
 201         struct xfarray  *array,
 202         xfarray_idx_t   idx,
 203         const void      *ptr)
 204 {
 205         int             ret;
 206
 207         if (idx >= array->max_nr)
 208                 return -EFBIG;
 209
 210         ASSERT(!xfarray_element_is_null(array, ptr));
 211
 212         ret = xfile_store(array->xfile, ptr, array->obj_size,
 213                         xfarray_pos(array, idx));
 214         if (ret)
 215                 return ret;
 216
 217         array->nr = max(array->nr, idx + 1);
 218         return 0;
 219 }
 220
 221 /* Is this array element NULL? */
 222 bool
 223 xfarray_element_is_null(
 224         struct xfarray  *array,
 225         const void      *ptr)
 226 {
 227         return !memchr_inv(ptr, 0, array->obj_size);
 228 }
 229
 230 /*
 231  * Store an element anywhere in the array that is unset.  If there are no
 232  * unset slots, append the element to the array.
 233  */
 234 int
 235 xfarray_store_anywhere(
 236         struct xfarray  *array,
 237         const void      *ptr)
 238 {
 239         void            *temp = xfarray_scratch(array);
 240         loff_t          endpos = xfarray_pos(array, array->nr);
 241         loff_t          pos;
 242         int             error;
 243
 244         /* Find an unset slot to put it in. */
 245         for (pos = 0;
 246              pos < endpos && array->unset_slots > 0;
 247              pos += array->obj_size) {
 248                 error = xfile_load(array->xfile, temp, array->obj_size,
 249                                 pos);
 250                 if (error || !xfarray_element_is_null(array, temp))
 251                         continue;
 252
 253                 error = xfile_store(array->xfile, ptr, array->obj_size,
 254                                 pos);
 255                 if (error)
 256                         return error;
 257
 258                 array->unset_slots--;
 259                 return 0;
 260         }
 261
 262         /* No unset slots found; attach it on the end. */
 263         array->unset_slots = 0;
 264         return xfarray_append(array, ptr);
 265 }
 266
 267 /* Return length of array. */
 268 uint64_t
 269 xfarray_length(
 270         struct xfarray  *array)
 271 {
 272         return array->nr;
 273 }
 274
 275 /*
 276  * Decide which array item we're going to read as part of an _iter_get.
 277  * @cur is the array index, and @pos is the file offset of that array index in
 278  * the backing xfile.  Returns ENODATA if we reach the end of the records.
 279  *
 280  * Reading from a hole in a sparse xfile causes page instantiation, so for
 281  * iterating a (possibly sparse) array we need to figure out if the cursor is
 282  * pointing at a totally uninitialized hole and move the cursor up if
 283  * necessary.
 284  */
 285 static inline int
 286 xfarray_find_data(
 287         struct xfarray  *array,
 288         xfarray_idx_t   *cur,
 289         loff_t          *pos)
 290 {
 291         unsigned int    pgoff = offset_in_page(*pos);
 292         loff_t          end_pos = *pos + array->obj_size - 1;
 293         loff_t          new_pos;
 294
 295         /*
 296          * If the current array record is not adjacent to a page boundary, we
 297          * are in the middle of the page.  We do not need to move the cursor.
 298          */
 299         if (pgoff != 0 && pgoff + array->obj_size - 1 < PAGE_SIZE)
 300                 return 0;
 301
 302         /*
 303          * Call SEEK_DATA on the last byte in the record we're about to read.
 304          * If the record ends at (or crosses) the end of a page then we know
 305          * that the first byte of the record is backed by pages and don't need
 306          * to query it.  If instead the record begins at the start of the page
 307          * then we know that querying the last byte is just as good as querying
 308          * the first byte, since records cannot be larger than a page.
 309          *
 310          * If the call returns the same file offset, we know this record is
 311          * backed by real pages.  We do not need to move the cursor.
 312          */
 313         new_pos = xfile_seek_data(array->xfile, end_pos);
 314         if (new_pos == -ENXIO)
 315                 return -ENODATA;
 316         if (new_pos < 0)
 317                 return new_pos;
 318         if (new_pos == end_pos)
 319                 return 0;
 320
 321         /*
 322          * Otherwise, SEEK_DATA told us how far up to move the file pointer to
 323          * find more data.  Move the array index to the first record past the
 324          * byte offset we were given.
 325          */
 326         new_pos = roundup_64(new_pos, array->obj_size);
 327         *cur = xfarray_idx(array, new_pos);
 328         *pos = xfarray_pos(array, *cur);
 329         return 0;
 330 }
 331
 332 /*
 333  * Starting at *idx, fetch the next non-null array entry and advance the index
 334  * to set up the next _load_next call.  Returns ENODATA if we reach the end of
 335  * the array.  Callers must set @*idx to XFARRAY_CURSOR_INIT before the first
 336  * call to this function.
 337  */
 338 int
 339 xfarray_load_next(
 340         struct xfarray  *array,
 341         xfarray_idx_t   *idx,
 342         void            *rec)
 343 {
 344         xfarray_idx_t   cur = *idx;
 345         loff_t          pos = xfarray_pos(array, cur);
 346         int             error;
 347
 348         do {
 349                 if (cur >= array->nr)
 350                         return -ENODATA;
 351
 352                 /*
 353                  * Ask the backing store for the location of next possible
 354                  * written record, then retrieve that record.
 355                  */
 356                 error = xfarray_find_data(array, &cur, &pos);
 357                 if (error)
 358                         return error;
 359                 error = xfarray_load(array, cur, rec);
 360                 if (error)
 361                         return error;
 362
 363                 cur++;
 364                 pos += array->obj_size;
 365         } while (xfarray_element_is_null(array, rec));
 366
 367         *idx = cur;
 368         return 0;
 369 }
 370
 371 /* Sorting functions */
 372
 373 #ifdef DEBUG
 374 # define xfarray_sort_bump_loads(si)    do { (si)->loads++; } while (0)
 375 # define xfarray_sort_bump_stores(si)   do { (si)->stores++; } while (0)
 376 # define xfarray_sort_bump_compares(si) do { (si)->compares++; } while (0)
 377 # define xfarray_sort_bump_heapsorts(si) do { (si)->heapsorts++; } while (0)
 378 #else
 379 # define xfarray_sort_bump_loads(si)
 380 # define xfarray_sort_bump_stores(si)
 381 # define xfarray_sort_bump_compares(si)
 382 # define xfarray_sort_bump_heapsorts(si)
 383 #endif /* DEBUG */
 384
 385 /* Load an array element for sorting. */
 386 static inline int
 387 xfarray_sort_load(
 388         struct xfarray_sortinfo *si,
 389         xfarray_idx_t           idx,
 390         void                    *ptr)
 391 {
 392         xfarray_sort_bump_loads(si);
 393         return xfarray_load(si->array, idx, ptr);
 394 }
 395
 396 /* Store an array element for sorting. */
 397 static inline int
 398 xfarray_sort_store(
 399         struct xfarray_sortinfo *si,
 400         xfarray_idx_t           idx,
 401         void                    *ptr)
 402 {
 403         xfarray_sort_bump_stores(si);
 404         return xfarray_store(si->array, idx, ptr);
 405 }
 406
 407 /* Compare an array element for sorting. */
 408 static inline int
 409 xfarray_sort_cmp(
 410         struct xfarray_sortinfo *si,
 411         const void              *a,
 412         const void              *b)
 413 {
 414         xfarray_sort_bump_compares(si);
 415         return si->cmp_fn(a, b);
 416 }
 417
 418 /* Return a pointer to the low index stack for quicksort partitioning. */
 419 static inline xfarray_idx_t *xfarray_sortinfo_lo(struct xfarray_sortinfo *si)
 420 {
 421         return (xfarray_idx_t *)(si + 1);
 422 }
 423
 424 /* Return a pointer to the high index stack for quicksort partitioning. */
 425 static inline xfarray_idx_t *xfarray_sortinfo_hi(struct xfarray_sortinfo *si)
 426 {
 427         return xfarray_sortinfo_lo(si) + si->max_stack_depth;
 428 }
 429
 430 /* Size of each element in the quicksort pivot array. */
 431 static inline size_t
 432 xfarray_pivot_rec_sz(
 433         struct xfarray          *array)
 434 {
 435         return round_up(array->obj_size, 8) + sizeof(xfarray_idx_t);
 436 }
 437
 438 /* Allocate memory to handle the sort. */
 439 static inline int
 440 xfarray_sortinfo_alloc(
 441         struct xfarray          *array,
 442         xfarray_cmp_fn          cmp_fn,
 443         unsigned int            flags,
 444         struct xfarray_sortinfo **infop)
 445 {
 446         struct xfarray_sortinfo *si;
 447         size_t                  nr_bytes = sizeof(struct xfarray_sortinfo);
 448         size_t                  pivot_rec_sz = xfarray_pivot_rec_sz(array);
 449         int                     max_stack_depth;
 450
 451         /*
 452          * The median-of-nine pivot algorithm doesn't work if a subset has
 453          * fewer than 9 items.  Make sure the in-memory sort will always take
 454          * over for subsets where this wouldn't be the case.
 455          */
 456         BUILD_BUG_ON(XFARRAY_QSORT_PIVOT_NR >= XFARRAY_ISORT_NR);
 457
 458         /*
 459          * Tail-call recursion during the partitioning phase means that
 460          * quicksort will never recurse more than log2(nr) times.  We need one
 461          * extra level of stack to hold the initial parameters.  In-memory
 462          * sort will always take care of the last few levels of recursion for
 463          * us, so we can reduce the stack depth by that much.
 464          */
 465         max_stack_depth = ilog2(array->nr) + 1 - (XFARRAY_ISORT_SHIFT - 1);
 466         if (max_stack_depth < 1)
 467                 max_stack_depth = 1;
 468
 469         /* Each level of quicksort uses a lo and a hi index */
 470         nr_bytes += max_stack_depth * sizeof(xfarray_idx_t) * 2;
 471
 472         /* Scratchpad for in-memory sort, or finding the pivot */
 473         nr_bytes += max_t(size_t,
 474                         (XFARRAY_QSORT_PIVOT_NR + 1) * pivot_rec_sz,
 475                         XFARRAY_ISORT_NR * array->obj_size);
 476
 477         si = kvzalloc(nr_bytes, XCHK_GFP_FLAGS);
 478         if (!si)
 479                 return -ENOMEM;
 480
 481         si->array = array;
 482         si->cmp_fn = cmp_fn;
 483         si->flags = flags;
 484         si->max_stack_depth = max_stack_depth;
 485         si->max_stack_used = 1;
 486
 487         xfarray_sortinfo_lo(si)[0] = 0;
 488         xfarray_sortinfo_hi(si)[0] = array->nr - 1;
 489         si->relax = INIT_XCHK_RELAX;
 490         if (flags & XFARRAY_SORT_KILLABLE)
 491                 si->relax.interruptible = false;
 492
 493         trace_xfarray_sort(si, nr_bytes);
 494         *infop = si;
 495         return 0;
 496 }
 497
 498 /* Should this sort be terminated by a fatal signal? */
 499 static inline bool
 500 xfarray_sort_terminated(
 501         struct xfarray_sortinfo *si,
 502         int                     *error)
 503 {
 504         /*
 505          * If preemption is disabled, we need to yield to the scheduler every
 506          * few seconds so that we don't run afoul of the soft lockup watchdog
 507          * or RCU stall detector.
 508          */
 509         if (xchk_maybe_relax(&si->relax)) {
 510                 if (*error == 0)
 511                         *error = -EINTR;
 512                 return true;
 513         }
 514         return false;
 515 }
 516
 517 /* Do we want an in-memory sort? */
 518 static inline bool
 519 xfarray_want_isort(
 520         struct xfarray_sortinfo *si,
 521         xfarray_idx_t           start,
 522         xfarray_idx_t           end)
 523 {
 524         /*
 525          * For array subsets that fit in the scratchpad, it's much faster to
 526          * use the kernel's heapsort than quicksort's stack machine.
 527          */
 528         return (end - start) < XFARRAY_ISORT_NR;
 529 }
 530
 531 /* Return the scratch space within the sortinfo structure. */
 532 static inline void *xfarray_sortinfo_isort_scratch(struct xfarray_sortinfo *si)
 533 {
 534         return xfarray_sortinfo_hi(si) + si->max_stack_depth;
 535 }
 536
 537 /*
 538  * Sort a small number of array records using scratchpad memory.  The records
 539  * need not be contiguous in the xfile's memory pages.
 540  */
 541 STATIC int
 542 xfarray_isort(
 543         struct xfarray_sortinfo *si,
 544         xfarray_idx_t           lo,
 545         xfarray_idx_t           hi)
 546 {
 547         void                    *scratch = xfarray_sortinfo_isort_scratch(si);
 548         loff_t                  lo_pos = xfarray_pos(si->array, lo);
 549         loff_t                  len = xfarray_pos(si->array, hi - lo + 1);
 550         int                     error;
 551
 552         trace_xfarray_isort(si, lo, hi);
 553
 554         xfarray_sort_bump_loads(si);
 555         error = xfile_load(si->array->xfile, scratch, len, lo_pos);
 556         if (error)
 557                 return error;
 558
 559         xfarray_sort_bump_heapsorts(si);
 560         sort(scratch, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
 561
 562         xfarray_sort_bump_stores(si);
 563         return xfile_store(si->array->xfile, scratch, len, lo_pos);
 564 }
 565
 566 /*
 567  * Sort the records from lo to hi (inclusive) if they are all backed by the
 568  * same memory folio.  Returns 1 if it sorted, 0 if it did not, or a negative
 569  * errno.
 570  */
 571 STATIC int
 572 xfarray_foliosort(
 573         struct xfarray_sortinfo *si,
 574         xfarray_idx_t           lo,
 575         xfarray_idx_t           hi)
 576 {
 577         struct folio            *folio;
 578         void                    *startp;
 579         loff_t                  lo_pos = xfarray_pos(si->array, lo);
 580         uint64_t                len = xfarray_pos(si->array, hi - lo + 1);
 581
 582         /* No single folio could back this many records. */
 583         if (len > XFILE_MAX_FOLIO_SIZE)
 584                 return 0;
 585
 586         xfarray_sort_bump_loads(si);
 587         folio = xfile_get_folio(si->array->xfile, lo_pos, len, XFILE_ALLOC);
 588         if (IS_ERR(folio))
 589                 return PTR_ERR(folio);
 590         if (!folio)
 591                 return 0;
 592
 593         trace_xfarray_foliosort(si, lo, hi);
 594
 595         xfarray_sort_bump_heapsorts(si);
 596         startp = folio_address(folio) + offset_in_folio(folio, lo_pos);
 597         sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
 598
 599         xfarray_sort_bump_stores(si);
 600         xfile_put_folio(si->array->xfile, folio);
 601         return 1;
 602 }
 603
 604 /* Return a pointer to the xfarray pivot record within the sortinfo struct. */
 605 static inline void *xfarray_sortinfo_pivot(struct xfarray_sortinfo *si)
 606 {
 607         return xfarray_sortinfo_hi(si) + si->max_stack_depth;
 608 }
 609
 610 /* Return a pointer to the start of the pivot array. */
 611 static inline void *
 612 xfarray_sortinfo_pivot_array(
 613         struct xfarray_sortinfo *si)
 614 {
 615         return xfarray_sortinfo_pivot(si) + si->array->obj_size;
 616 }
 617
 618 /* The xfarray record is stored at the start of each pivot array element. */
 619 static inline void *
 620 xfarray_pivot_array_rec(
 621         void                    *pa,
 622         size_t                  pa_recsz,
 623         unsigned int            pa_idx)
 624 {
 625         return pa + (pa_recsz * pa_idx);
 626 }
 627
 628 /* The xfarray index is stored at the end of each pivot array element. */
 629 static inline xfarray_idx_t *
 630 xfarray_pivot_array_idx(
 631         void                    *pa,
 632         size_t                  pa_recsz,
 633         unsigned int            pa_idx)
 634 {
 635         return xfarray_pivot_array_rec(pa, pa_recsz, pa_idx + 1) -
 636                         sizeof(xfarray_idx_t);
 637 }
 638
 639 /*
 640  * Find a pivot value for quicksort partitioning, swap it with a[lo], and save
 641  * the cached pivot record for the next step.
 642  *
 643  * Load evenly-spaced records within the given range into memory, sort them,
 644  * and choose the pivot from the median record.  Using multiple points will
 645  * improve the quality of the pivot selection, and hopefully avoid the worst
 646  * quicksort behavior, since our array values are nearly always evenly sorted.
 647  */
 648 STATIC int
 649 xfarray_qsort_pivot(
 650         struct xfarray_sortinfo *si,
 651         xfarray_idx_t           lo,
 652         xfarray_idx_t           hi)
 653 {
 654         void                    *pivot = xfarray_sortinfo_pivot(si);
 655         void                    *parray = xfarray_sortinfo_pivot_array(si);
 656         void                    *recp;
 657         xfarray_idx_t           *idxp;
 658         xfarray_idx_t           step = (hi - lo) / (XFARRAY_QSORT_PIVOT_NR - 1);
 659         size_t                  pivot_rec_sz = xfarray_pivot_rec_sz(si->array);
 660         int                     i, j;
 661         int                     error;
 662
 663         ASSERT(step > 0);
 664
 665         /*
 666          * Load the xfarray indexes of the records we intend to sample into the
 667          * pivot array.
 668          */
 669         idxp = xfarray_pivot_array_idx(parray, pivot_rec_sz, 0);
 670         *idxp = lo;
 671         for (i = 1; i < XFARRAY_QSORT_PIVOT_NR - 1; i++) {
 672                 idxp = xfarray_pivot_array_idx(parray, pivot_rec_sz, i);
 673                 *idxp = lo + (i * step);
 674         }
 675         idxp = xfarray_pivot_array_idx(parray, pivot_rec_sz,
 676                         XFARRAY_QSORT_PIVOT_NR - 1);
 677         *idxp = hi;
 678
 679         /* Load the selected xfarray records into the pivot array. */
 680         for (i = 0; i < XFARRAY_QSORT_PIVOT_NR; i++) {
 681                 xfarray_idx_t   idx;
 682
 683                 recp = xfarray_pivot_array_rec(parray, pivot_rec_sz, i);
 684                 idxp = xfarray_pivot_array_idx(parray, pivot_rec_sz, i);
 685
 686                 /* No unset records; load directly into the array. */
 687                 if (likely(si->array->unset_slots == 0)) {
 688                         error = xfarray_sort_load(si, *idxp, recp);
 689                         if (error)
 690                                 return error;
 691                         continue;
 692                 }
 693
 694                 /*
 695                  * Load non-null records into the scratchpad without changing
 696                  * the xfarray_idx_t in the pivot array.
 697                  */
 698                 idx = *idxp;
 699                 xfarray_sort_bump_loads(si);
 700                 error = xfarray_load_next(si->array, &idx, recp);
 701                 if (error)
 702                         return error;
 703         }
 704
 705         xfarray_sort_bump_heapsorts(si);
 706         sort(parray, XFARRAY_QSORT_PIVOT_NR, pivot_rec_sz, si->cmp_fn, NULL);
 707
 708         /*
 709          * We sorted the pivot array records (which includes the xfarray
 710          * indices) in xfarray record order.  The median element of the pivot
 711          * array contains the xfarray record that we will use as the pivot.
 712          * Copy that xfarray record to the designated space.
 713          */
 714         recp = xfarray_pivot_array_rec(parray, pivot_rec_sz,
 715                         XFARRAY_QSORT_PIVOT_NR / 2);
 716         memcpy(pivot, recp, si->array->obj_size);
 717
 718         /* If the pivot record we chose was already in a[lo] then we're done. */
 719         idxp = xfarray_pivot_array_idx(parray, pivot_rec_sz,
 720                         XFARRAY_QSORT_PIVOT_NR / 2);
 721         if (*idxp == lo)
 722                 return 0;
 723
 724         /*
 725          * Find the cached copy of a[lo] in the pivot array so that we can swap
 726          * a[lo] and a[pivot].
 727          */
 728         for (i = 0, j = -1; i < XFARRAY_QSORT_PIVOT_NR; i++) {
 729                 idxp = xfarray_pivot_array_idx(parray, pivot_rec_sz, i);
 730                 if (*idxp == lo)
 731                         j = i;
 732         }
 733         if (j < 0) {
 734                 ASSERT(j >= 0);
 735                 return -EFSCORRUPTED;
 736         }
 737
 738         /* Swap a[lo] and a[pivot]. */
 739         error = xfarray_sort_store(si, lo, pivot);
 740         if (error)
 741                 return error;
 742
 743         recp = xfarray_pivot_array_rec(parray, pivot_rec_sz, j);
 744         idxp = xfarray_pivot_array_idx(parray, pivot_rec_sz,
 745                         XFARRAY_QSORT_PIVOT_NR / 2);
 746         return xfarray_sort_store(si, *idxp, recp);
 747 }
 748
 749 /*
 750  * Set up the pointers for the next iteration.  We push onto the stack all of
 751  * the unsorted values between a[lo + 1] and a[end[i]], and we tweak the
 752  * current stack frame to point to the unsorted values between a[beg[i]] and
 753  * a[lo] so that those values will be sorted when we pop the stack.
 754  */
 755 static inline int
 756 xfarray_qsort_push(
 757         struct xfarray_sortinfo *si,
 758         xfarray_idx_t           *si_lo,
 759         xfarray_idx_t           *si_hi,
 760         xfarray_idx_t           lo,
 761         xfarray_idx_t           hi)
 762 {
 763         /* Check for stack overflows */
 764         if (si->stack_depth >= si->max_stack_depth - 1) {
 765                 ASSERT(si->stack_depth < si->max_stack_depth - 1);
 766                 return -EFSCORRUPTED;
 767         }
 768
 769         si->max_stack_used = max_t(uint8_t, si->max_stack_used,
 770                                             si->stack_depth + 2);
 771
 772         si_lo[si->stack_depth + 1] = lo + 1;
 773         si_hi[si->stack_depth + 1] = si_hi[si->stack_depth];
 774         si_hi[si->stack_depth++] = lo - 1;
 775
 776         /*
 777          * Always start with the smaller of the two partitions to keep the
 778          * amount of recursion in check.
 779          */
 780         if (si_hi[si->stack_depth]     - si_lo[si->stack_depth] >
 781             si_hi[si->stack_depth - 1] - si_lo[si->stack_depth - 1]) {
 782                 swap(si_lo[si->stack_depth], si_lo[si->stack_depth - 1]);
 783                 swap(si_hi[si->stack_depth], si_hi[si->stack_depth - 1]);
 784         }
 785
 786         return 0;
 787 }
 788
 789 static inline void
 790 xfarray_sort_scan_done(
 791         struct xfarray_sortinfo *si)
 792 {
 793         if (si->folio)
 794                 xfile_put_folio(si->array->xfile, si->folio);
 795         si->folio = NULL;
 796 }
 797
 798 /*
 799  * Cache the folio backing the start of the given array element.  If the array
 800  * element is contained entirely within the folio, return a pointer to the
 801  * cached folio.  Otherwise, load the element into the scratchpad and return a
 802  * pointer to the scratchpad.
 803  */
 804 static inline int
 805 xfarray_sort_scan(
 806         struct xfarray_sortinfo *si,
 807         xfarray_idx_t           idx,
 808         void                    **ptrp)
 809 {
 810         loff_t                  idx_pos = xfarray_pos(si->array, idx);
 811         int                     error = 0;
 812
 813         if (xfarray_sort_terminated(si, &error))
 814                 return error;
 815
 816         trace_xfarray_sort_scan(si, idx);
 817
 818         /* If the cached folio doesn't cover this index, release it. */
 819         if (si->folio &&
 820             (idx < si->first_folio_idx || idx > si->last_folio_idx))
 821                 xfarray_sort_scan_done(si);
 822
 823         /* Grab the first folio that backs this array element. */
 824         if (!si->folio) {
 825                 struct folio    *folio;
 826                 loff_t          next_pos;
 827
 828                 folio = xfile_get_folio(si->array->xfile, idx_pos,
 829                                 si->array->obj_size, XFILE_ALLOC);
 830                 if (IS_ERR(folio))
 831                         return PTR_ERR(folio);
 832                 si->folio = folio;
 833
 834                 si->first_folio_idx = xfarray_idx(si->array,
 835                                 folio_pos(si->folio) + si->array->obj_size - 1);
 836
 837                 next_pos = folio_pos(si->folio) + folio_size(si->folio);
 838                 si->last_folio_idx = xfarray_idx(si->array, next_pos - 1);
 839                 if (xfarray_pos(si->array, si->last_folio_idx + 1) > next_pos)
 840                         si->last_folio_idx--;
 841
 842                 trace_xfarray_sort_scan(si, idx);
 843         }
 844
 845         /*
 846          * If this folio still doesn't cover the desired element, it must cross
 847          * a folio boundary.  Read into the scratchpad and we're done.
 848          */
 849         if (idx < si->first_folio_idx || idx > si->last_folio_idx) {
 850                 void            *temp = xfarray_scratch(si->array);
 851
 852                 error = xfile_load(si->array->xfile, temp, si->array->obj_size,
 853                                 idx_pos);
 854                 if (error)
 855                         return error;
 856
 857                 *ptrp = temp;
 858                 return 0;
 859         }
 860
 861         /* Otherwise return a pointer to the array element in the folio. */
 862         *ptrp = folio_address(si->folio) + offset_in_folio(si->folio, idx_pos);
 863         return 0;
 864 }
 865
 866 /*
 867  * Sort the array elements via quicksort.  This implementation incorporates
 868  * four optimizations discussed in Sedgewick:
 869  *
 870  * 1. Use an explicit stack of array indices to store the next array partition
 871  *    to sort.  This helps us to avoid recursion in the call stack, which is
 872  *    particularly expensive in the kernel.
 873  *
 874  * 2. For arrays with records in arbitrary or user-controlled order, choose the
 875  *    pivot element using a median-of-nine decision tree.  This reduces the
 876  *    probability of selecting a bad pivot value which causes worst case
 877  *    behavior (i.e. partition sizes of 1).
 878  *
 879  * 3. The smaller of the two sub-partitions is pushed onto the stack to start
 880  *    the next level of recursion, and the larger sub-partition replaces the
 881  *    current stack frame.  This guarantees that we won't need more than
 882  *    log2(nr) stack space.
 883  *
 884  * 4. For small sets, load the records into the scratchpad and run heapsort on
 885  *    them because that is very fast.  In the author's experience, this yields
 886  *    a ~10% reduction in runtime.
 887  *
 888  *    If a small set is contained entirely within a single xfile memory page,
 889  *    map the page directly and run heap sort directly on the xfile page
 890  *    instead of using the load/store interface.  This halves the runtime.
 891  *
 892  * 5. This optimization is specific to the implementation.  When converging lo
 893  *    and hi after selecting a pivot, we will try to retain the xfile memory
 894  *    page between load calls, which reduces run time by 50%.
 895  */
 896
 897 /*
 898  * Due to the use of signed indices, we can only support up to 2^63 records.
 899  * Files can only grow to 2^63 bytes, so this is not much of a limitation.
 900  */
 901 #define QSORT_MAX_RECS          (1ULL << 63)
 902
 903 int
 904 xfarray_sort(
 905         struct xfarray          *array,
 906         xfarray_cmp_fn          cmp_fn,
 907         unsigned int            flags)
 908 {
 909         struct xfarray_sortinfo *si;
 910         xfarray_idx_t           *si_lo, *si_hi;
 911         void                    *pivot;
 912         void                    *scratch = xfarray_scratch(array);
 913         xfarray_idx_t           lo, hi;
 914         int                     error = 0;
 915
 916         if (array->nr < 2)
 917                 return 0;
 918         if (array->nr >= QSORT_MAX_RECS)
 919                 return -E2BIG;
 920
 921         error = xfarray_sortinfo_alloc(array, cmp_fn, flags, &si);
 922         if (error)
 923                 return error;
 924         si_lo = xfarray_sortinfo_lo(si);
 925         si_hi = xfarray_sortinfo_hi(si);
 926         pivot = xfarray_sortinfo_pivot(si);
 927
 928         while (si->stack_depth >= 0) {
 929                 int             ret;
 930
 931                 lo = si_lo[si->stack_depth];
 932                 hi = si_hi[si->stack_depth];
 933
 934                 trace_xfarray_qsort(si, lo, hi);
 935
 936                 /* Nothing left in this partition to sort; pop stack. */
 937                 if (lo >= hi) {
 938                         si->stack_depth--;
 939                         continue;
 940                 }
 941
 942                 /*
 943                  * If directly mapping the folio and sorting can solve our
 944                  * problems, we're done.
 945                  */
 946                 ret = xfarray_foliosort(si, lo, hi);
 947                 if (ret < 0)
 948                         goto out_free;
 949                 if (ret == 1) {
 950                         si->stack_depth--;
 951                         continue;
 952                 }
 953
 954                 /* If insertion sort can solve our problems, we're done. */
 955                 if (xfarray_want_isort(si, lo, hi)) {
 956                         error = xfarray_isort(si, lo, hi);
 957                         if (error)
 958                                 goto out_free;
 959                         si->stack_depth--;
 960                         continue;
 961                 }
 962
 963                 /* Pick a pivot, move it to a[lo] and stash it. */
 964                 error = xfarray_qsort_pivot(si, lo, hi);
 965                 if (error)
 966                         goto out_free;
 967
 968                 /*
 969                  * Rearrange a[lo..hi] such that everything smaller than the
 970                  * pivot is on the left side of the range and everything larger
 971                  * than the pivot is on the right side of the range.
 972                  */
 973                 while (lo < hi) {
 974                         void    *p;
 975
 976                         /*
 977                          * Decrement hi until it finds an a[hi] less than the
 978                          * pivot value.
 979                          */
 980                         error = xfarray_sort_scan(si, hi, &p);
 981                         if (error)
 982                                 goto out_free;
 983                         while (xfarray_sort_cmp(si, p, pivot) >= 0 && lo < hi) {
 984                                 hi--;
 985                                 error = xfarray_sort_scan(si, hi, &p);
 986                                 if (error)
 987                                         goto out_free;
 988                         }
 989                         if (p != scratch)
 990                                 memcpy(scratch, p, si->array->obj_size);
 991                         xfarray_sort_scan_done(si);
 992                         if (xfarray_sort_terminated(si, &error))
 993                                 goto out_free;
 994
 995                         /* Copy that item (a[hi]) to a[lo]. */
 996                         if (lo < hi) {
 997                                 error = xfarray_sort_store(si, lo++, scratch);
 998                                 if (error)
 999                                         goto out_free;
1000                         }
1001
1002                         /*
1003                          * Increment lo until it finds an a[lo] greater than
1004                          * the pivot value.
1005                          */
1006                         error = xfarray_sort_scan(si, lo, &p);
1007                         if (error)
1008                                 goto out_free;
1009                         while (xfarray_sort_cmp(si, p, pivot) <= 0 && lo < hi) {
1010                                 lo++;
1011                                 error = xfarray_sort_scan(si, lo, &p);
1012                                 if (error)
1013                                         goto out_free;
1014                         }
1015                         if (p != scratch)
1016                                 memcpy(scratch, p, si->array->obj_size);
1017                         xfarray_sort_scan_done(si);
1018                         if (xfarray_sort_terminated(si, &error))
1019                                 goto out_free;
1020
1021                         /* Copy that item (a[lo]) to a[hi]. */
1022                         if (lo < hi) {
1023                                 error = xfarray_sort_store(si, hi--, scratch);
1024                                 if (error)
1025                                         goto out_free;
1026                         }
1027
1028                         if (xfarray_sort_terminated(si, &error))
1029                                 goto out_free;
1030                 }
1031
1032                 /*
1033                  * Put our pivot value in the correct place at a[lo].  All
1034                  * values between a[beg[i]] and a[lo - 1] should be less than
1035                  * the pivot; and all values between a[lo + 1] and a[end[i]-1]
1036                  * should be greater than the pivot.
1037                  */
1038                 error = xfarray_sort_store(si, lo, pivot);
1039                 if (error)
1040                         goto out_free;
1041
1042                 /* Set up the stack frame to process the two partitions. */
1043                 error = xfarray_qsort_push(si, si_lo, si_hi, lo, hi);
1044                 if (error)
1045                         goto out_free;
1046
1047                 if (xfarray_sort_terminated(si, &error))
1048                         goto out_free;
1049         }
1050
1051 out_free:
1052         trace_xfarray_sort_stats(si, error);
1053         xfarray_sort_scan_done(si);
1054         kvfree(si);
1055         return error;
1056 }
1057
1058 /* How many bytes is this array consuming? */
1059 unsigned long long
1060 xfarray_bytes(
1061         struct xfarray          *array)
1062 {
1063         return xfile_bytes(array->xfile);
1064 }
1065
1066 /* Empty the entire array. */
1067 void
1068 xfarray_truncate(
1069         struct xfarray  *array)
1070 {
1071         xfile_discard(array->xfile, 0, MAX_LFS_FILESIZE);
1072         array->nr = 0;
1073 }