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 <djwong@kernel.org>
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_format.h"
  10 #include "scrub/xfile.h"
  11 #include "scrub/xfarray.h"
  12 #include "scrub/scrub.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 memfd "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_obj_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_obj_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_obj_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_obj_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_obj_load(array->xfile, temp, array->obj_size,
 249                                 pos);
 250                 if (error || !xfarray_element_is_null(array, temp))
 251                         continue;
 252
 253                 error = xfile_obj_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 #else
 378 # define xfarray_sort_bump_loads(si)
 379 # define xfarray_sort_bump_stores(si)
 380 # define xfarray_sort_bump_compares(si)
 381 #endif /* DEBUG */
 382
 383 /* Load an array element for sorting. */
 384 static inline int
 385 xfarray_sort_load(
 386         struct xfarray_sortinfo *si,
 387         xfarray_idx_t           idx,
 388         void                    *ptr)
 389 {
 390         xfarray_sort_bump_loads(si);
 391         return xfarray_load(si->array, idx, ptr);
 392 }
 393
 394 /* Store an array element for sorting. */
 395 static inline int
 396 xfarray_sort_store(
 397         struct xfarray_sortinfo *si,
 398         xfarray_idx_t           idx,
 399         void                    *ptr)
 400 {
 401         xfarray_sort_bump_stores(si);
 402         return xfarray_store(si->array, idx, ptr);
 403 }
 404
 405 /* Compare an array element for sorting. */
 406 static inline int
 407 xfarray_sort_cmp(
 408         struct xfarray_sortinfo *si,
 409         const void              *a,
 410         const void              *b)
 411 {
 412         xfarray_sort_bump_compares(si);
 413         return si->cmp_fn(a, b);
 414 }
 415
 416 /* Return a pointer to the low index stack for quicksort partitioning. */
 417 static inline xfarray_idx_t *xfarray_sortinfo_lo(struct xfarray_sortinfo *si)
 418 {
 419         return (xfarray_idx_t *)(si + 1);
 420 }
 421
 422 /* Return a pointer to the high index stack for quicksort partitioning. */
 423 static inline xfarray_idx_t *xfarray_sortinfo_hi(struct xfarray_sortinfo *si)
 424 {
 425         return xfarray_sortinfo_lo(si) + si->max_stack_depth;
 426 }
 427
 428 /* Allocate memory to handle the sort. */
 429 static inline int
 430 xfarray_sortinfo_alloc(
 431         struct xfarray          *array,
 432         xfarray_cmp_fn          cmp_fn,
 433         unsigned int            flags,
 434         struct xfarray_sortinfo **infop)
 435 {
 436         struct xfarray_sortinfo *si;
 437         size_t                  nr_bytes = sizeof(struct xfarray_sortinfo);
 438         int                     max_stack_depth;
 439
 440         /*
 441          * Tail-call recursion during the partitioning phase means that
 442          * quicksort will never recurse more than log2(nr) times.  We need one
 443          * extra level of stack to hold the initial parameters.
 444          */
 445         max_stack_depth = ilog2(array->nr) + 1;
 446
 447         /* Each level of quicksort uses a lo and a hi index */
 448         nr_bytes += max_stack_depth * sizeof(xfarray_idx_t) * 2;
 449
 450         /* One record for the pivot */
 451         nr_bytes += array->obj_size;
 452
 453         si = kvzalloc(nr_bytes, XCHK_GFP_FLAGS);
 454         if (!si)
 455                 return -ENOMEM;
 456
 457         si->array = array;
 458         si->cmp_fn = cmp_fn;
 459         si->flags = flags;
 460         si->max_stack_depth = max_stack_depth;
 461         si->max_stack_used = 1;
 462
 463         xfarray_sortinfo_lo(si)[0] = 0;
 464         xfarray_sortinfo_hi(si)[0] = array->nr - 1;
 465
 466         trace_xfarray_sort(si, nr_bytes);
 467         *infop = si;
 468         return 0;
 469 }
 470
 471 /* Should this sort be terminated by a fatal signal? */
 472 static inline bool
 473 xfarray_sort_terminated(
 474         struct xfarray_sortinfo *si,
 475         int                     *error)
 476 {
 477         /*
 478          * If preemption is disabled, we need to yield to the scheduler every
 479          * few seconds so that we don't run afoul of the soft lockup watchdog
 480          * or RCU stall detector.
 481          */
 482         cond_resched();
 483
 484         if ((si->flags & XFARRAY_SORT_KILLABLE) &&
 485             fatal_signal_pending(current)) {
 486                 if (*error == 0)
 487                         *error = -EINTR;
 488                 return true;
 489         }
 490         return false;
 491 }
 492
 493 /* Do we want an insertion sort? */
 494 static inline bool
 495 xfarray_want_isort(
 496         struct xfarray_sortinfo *si,
 497         xfarray_idx_t           start,
 498         xfarray_idx_t           end)
 499 {
 500         /*
 501          * For array subsets smaller than 8 elements, it's slightly faster to
 502          * use insertion sort than quicksort's stack machine.
 503          */
 504         return (end - start) < 8;
 505 }
 506
 507 /* Return the scratch space within the sortinfo structure. */
 508 static inline void *xfarray_sortinfo_isort_scratch(struct xfarray_sortinfo *si)
 509 {
 510         return xfarray_sortinfo_hi(si) + si->max_stack_depth;
 511 }
 512
 513 /*
 514  * Perform an insertion sort on a subset of the array.
 515  * Though insertion sort is an O(n^2) algorithm, for small set sizes it's
 516  * faster than quicksort's stack machine, so we let it take over for that.
 517  * This ought to be replaced with something more efficient.
 518  */
 519 STATIC int
 520 xfarray_isort(
 521         struct xfarray_sortinfo *si,
 522         xfarray_idx_t           lo,
 523         xfarray_idx_t           hi)
 524 {
 525         void                    *a = xfarray_sortinfo_isort_scratch(si);
 526         void                    *b = xfarray_scratch(si->array);
 527         xfarray_idx_t           tmp;
 528         xfarray_idx_t           i;
 529         xfarray_idx_t           run;
 530         int                     error;
 531
 532         trace_xfarray_isort(si, lo, hi);
 533
 534         /*
 535          * Move the smallest element in a[lo..hi] to a[lo].  This
 536          * simplifies the loop control logic below.
 537          */
 538         tmp = lo;
 539         error = xfarray_sort_load(si, tmp, b);
 540         if (error)
 541                 return error;
 542         for (run = lo + 1; run <= hi; run++) {
 543                 /* if a[run] < a[tmp], tmp = run */
 544                 error = xfarray_sort_load(si, run, a);
 545                 if (error)
 546                         return error;
 547                 if (xfarray_sort_cmp(si, a, b) < 0) {
 548                         tmp = run;
 549                         memcpy(b, a, si->array->obj_size);
 550                 }
 551
 552                 if (xfarray_sort_terminated(si, &error))
 553                         return error;
 554         }
 555
 556         /*
 557          * The smallest element is a[tmp]; swap with a[lo] if tmp != lo.
 558          * Recall that a[tmp] is already in *b.
 559          */
 560         if (tmp != lo) {
 561                 error = xfarray_sort_load(si, lo, a);
 562                 if (error)
 563                         return error;
 564                 error = xfarray_sort_store(si, tmp, a);
 565                 if (error)
 566                         return error;
 567                 error = xfarray_sort_store(si, lo, b);
 568                 if (error)
 569                         return error;
 570         }
 571
 572         /*
 573          * Perform an insertion sort on a[lo+1..hi].  We already made sure
 574          * that the smallest value in the original range is now in a[lo],
 575          * so the inner loop should never underflow.
 576          *
 577          * For each a[lo+2..hi], make sure it's in the correct position
 578          * with respect to the elements that came before it.
 579          */
 580         for (run = lo + 2; run <= hi; run++) {
 581                 error = xfarray_sort_load(si, run, a);
 582                 if (error)
 583                         return error;
 584
 585                 /*
 586                  * Find the correct place for a[run] by walking leftwards
 587                  * towards the start of the range until a[tmp] is no longer
 588                  * greater than a[run].
 589                  */
 590                 tmp = run - 1;
 591                 error = xfarray_sort_load(si, tmp, b);
 592                 if (error)
 593                         return error;
 594                 while (xfarray_sort_cmp(si, a, b) < 0) {
 595                         tmp--;
 596                         error = xfarray_sort_load(si, tmp, b);
 597                         if (error)
 598                                 return error;
 599
 600                         if (xfarray_sort_terminated(si, &error))
 601                                 return error;
 602                 }
 603                 tmp++;
 604
 605                 /*
 606                  * If tmp != run, then a[tmp..run-1] are all less than a[run],
 607                  * so right barrel roll a[tmp..run] to get this range in
 608                  * sorted order.
 609                  */
 610                 if (tmp == run)
 611                         continue;
 612
 613                 for (i = run; i >= tmp; i--) {
 614                         error = xfarray_sort_load(si, i - 1, b);
 615                         if (error)
 616                                 return error;
 617                         error = xfarray_sort_store(si, i, b);
 618                         if (error)
 619                                 return error;
 620
 621                         if (xfarray_sort_terminated(si, &error))
 622                                 return error;
 623                 }
 624                 error = xfarray_sort_store(si, tmp, a);
 625                 if (error)
 626                         return error;
 627
 628                 if (xfarray_sort_terminated(si, &error))
 629                         return error;
 630         }
 631
 632         return 0;
 633 }
 634
 635 /* Return a pointer to the xfarray pivot record within the sortinfo struct. */
 636 static inline void *xfarray_sortinfo_pivot(struct xfarray_sortinfo *si)
 637 {
 638         return xfarray_sortinfo_hi(si) + si->max_stack_depth;
 639 }
 640
 641 /*
 642  * Find a pivot value for quicksort partitioning, swap it with a[lo], and save
 643  * the cached pivot record for the next step.
 644  *
 645  * Select the median value from a[lo], a[mid], and a[hi].  Put the median in
 646  * a[lo], the lowest in a[mid], and the highest in a[hi].  Using the median of
 647  * the three reduces the chances that we pick the worst case pivot value, since
 648  * it's likely that our array values are nearly sorted.
 649  */
 650 STATIC int
 651 xfarray_qsort_pivot(
 652         struct xfarray_sortinfo *si,
 653         xfarray_idx_t           lo,
 654         xfarray_idx_t           hi)
 655 {
 656         void                    *a = xfarray_sortinfo_pivot(si);
 657         void                    *b = xfarray_scratch(si->array);
 658         xfarray_idx_t           mid = lo + ((hi - lo) / 2);
 659         int                     error;
 660
 661         /* if a[mid] < a[lo], swap a[mid] and a[lo]. */
 662         error = xfarray_sort_load(si, mid, a);
 663         if (error)
 664                 return error;
 665         error = xfarray_sort_load(si, lo, b);
 666         if (error)
 667                 return error;
 668         if (xfarray_sort_cmp(si, a, b) < 0) {
 669                 error = xfarray_sort_store(si, lo, a);
 670                 if (error)
 671                         return error;
 672                 error = xfarray_sort_store(si, mid, b);
 673                 if (error)
 674                         return error;
 675         }
 676
 677         /* if a[hi] < a[mid], swap a[mid] and a[hi]. */
 678         error = xfarray_sort_load(si, hi, a);
 679         if (error)
 680                 return error;
 681         error = xfarray_sort_load(si, mid, b);
 682         if (error)
 683                 return error;
 684         if (xfarray_sort_cmp(si, a, b) < 0) {
 685                 error = xfarray_sort_store(si, mid, a);
 686                 if (error)
 687                         return error;
 688                 error = xfarray_sort_store(si, hi, b);
 689                 if (error)
 690                         return error;
 691         } else {
 692                 goto move_front;
 693         }
 694
 695         /* if a[mid] < a[lo], swap a[mid] and a[lo]. */
 696         error = xfarray_sort_load(si, mid, a);
 697         if (error)
 698                 return error;
 699         error = xfarray_sort_load(si, lo, b);
 700         if (error)
 701                 return error;
 702         if (xfarray_sort_cmp(si, a, b) < 0) {
 703                 error = xfarray_sort_store(si, lo, a);
 704                 if (error)
 705                         return error;
 706                 error = xfarray_sort_store(si, mid, b);
 707                 if (error)
 708                         return error;
 709         }
 710
 711 move_front:
 712         /*
 713          * Move our selected pivot to a[lo].  Recall that a == si->pivot, so
 714          * this leaves us with the pivot cached in the sortinfo structure.
 715          */
 716         error = xfarray_sort_load(si, lo, b);
 717         if (error)
 718                 return error;
 719         error = xfarray_sort_load(si, mid, a);
 720         if (error)
 721                 return error;
 722         error = xfarray_sort_store(si, mid, b);
 723         if (error)
 724                 return error;
 725         return xfarray_sort_store(si, lo, a);
 726 }
 727
 728 /*
 729  * Set up the pointers for the next iteration.  We push onto the stack all of
 730  * the unsorted values between a[lo + 1] and a[end[i]], and we tweak the
 731  * current stack frame to point to the unsorted values between a[beg[i]] and
 732  * a[lo] so that those values will be sorted when we pop the stack.
 733  */
 734 static inline int
 735 xfarray_qsort_push(
 736         struct xfarray_sortinfo *si,
 737         xfarray_idx_t           *si_lo,
 738         xfarray_idx_t           *si_hi,
 739         xfarray_idx_t           lo,
 740         xfarray_idx_t           hi)
 741 {
 742         /* Check for stack overflows */
 743         if (si->stack_depth >= si->max_stack_depth - 1) {
 744                 ASSERT(si->stack_depth < si->max_stack_depth - 1);
 745                 return -EFSCORRUPTED;
 746         }
 747
 748         si->max_stack_used = max_t(uint8_t, si->max_stack_used,
 749                                             si->stack_depth + 2);
 750
 751         si_lo[si->stack_depth + 1] = lo + 1;
 752         si_hi[si->stack_depth + 1] = si_hi[si->stack_depth];
 753         si_hi[si->stack_depth++] = lo - 1;
 754
 755         /*
 756          * Always start with the smaller of the two partitions to keep the
 757          * amount of recursion in check.
 758          */
 759         if (si_hi[si->stack_depth]     - si_lo[si->stack_depth] >
 760             si_hi[si->stack_depth - 1] - si_lo[si->stack_depth - 1]) {
 761                 swap(si_lo[si->stack_depth], si_lo[si->stack_depth - 1]);
 762                 swap(si_hi[si->stack_depth], si_hi[si->stack_depth - 1]);
 763         }
 764
 765         return 0;
 766 }
 767
 768 /*
 769  * Sort the array elements via quicksort.  This implementation incorporates
 770  * four optimizations discussed in Sedgewick:
 771  *
 772  * 1. Use an explicit stack of array indices to store the next array partition
 773  *    to sort.  This helps us to avoid recursion in the call stack, which is
 774  *    particularly expensive in the kernel.
 775  *
 776  * 2. For arrays with records in arbitrary or user-controlled order, choose the
 777  *    pivot element using a median-of-three decision tree.  This reduces the
 778  *    probability of selecting a bad pivot value which causes worst case
 779  *    behavior (i.e. partition sizes of 1).
 780  *
 781  * 3. The smaller of the two sub-partitions is pushed onto the stack to start
 782  *    the next level of recursion, and the larger sub-partition replaces the
 783  *    current stack frame.  This guarantees that we won't need more than
 784  *    log2(nr) stack space.
 785  *
 786  * 4. Use insertion sort for small sets since since insertion sort is faster
 787  *    for small, mostly sorted array segments.  In the author's experience,
 788  *    substituting insertion sort for arrays smaller than 8 elements yields
 789  *    a ~10% reduction in runtime.
 790  */
 791
 792 /*
 793  * Due to the use of signed indices, we can only support up to 2^63 records.
 794  * Files can only grow to 2^63 bytes, so this is not much of a limitation.
 795  */
 796 #define QSORT_MAX_RECS          (1ULL << 63)
 797
 798 int
 799 xfarray_sort(
 800         struct xfarray          *array,
 801         xfarray_cmp_fn          cmp_fn,
 802         unsigned int            flags)
 803 {
 804         struct xfarray_sortinfo *si;
 805         xfarray_idx_t           *si_lo, *si_hi;
 806         void                    *pivot;
 807         void                    *scratch = xfarray_scratch(array);
 808         xfarray_idx_t           lo, hi;
 809         int                     error = 0;
 810
 811         if (array->nr < 2)
 812                 return 0;
 813         if (array->nr >= QSORT_MAX_RECS)
 814                 return -E2BIG;
 815
 816         error = xfarray_sortinfo_alloc(array, cmp_fn, flags, &si);
 817         if (error)
 818                 return error;
 819         si_lo = xfarray_sortinfo_lo(si);
 820         si_hi = xfarray_sortinfo_hi(si);
 821         pivot = xfarray_sortinfo_pivot(si);
 822
 823         while (si->stack_depth >= 0) {
 824                 lo = si_lo[si->stack_depth];
 825                 hi = si_hi[si->stack_depth];
 826
 827                 trace_xfarray_qsort(si, lo, hi);
 828
 829                 /* Nothing left in this partition to sort; pop stack. */
 830                 if (lo >= hi) {
 831                         si->stack_depth--;
 832                         continue;
 833                 }
 834
 835                 /* If insertion sort can solve our problems, we're done. */
 836                 if (xfarray_want_isort(si, lo, hi)) {
 837                         error = xfarray_isort(si, lo, hi);
 838                         if (error)
 839                                 goto out_free;
 840                         si->stack_depth--;
 841                         continue;
 842                 }
 843
 844                 /* Pick a pivot, move it to a[lo] and stash it. */
 845                 error = xfarray_qsort_pivot(si, lo, hi);
 846                 if (error)
 847                         goto out_free;
 848
 849                 /*
 850                  * Rearrange a[lo..hi] such that everything smaller than the
 851                  * pivot is on the left side of the range and everything larger
 852                  * than the pivot is on the right side of the range.
 853                  */
 854                 while (lo < hi) {
 855                         /*
 856                          * Decrement hi until it finds an a[hi] less than the
 857                          * pivot value.
 858                          */
 859                         error = xfarray_sort_load(si, hi, scratch);
 860                         if (error)
 861                                 goto out_free;
 862                         while (xfarray_sort_cmp(si, scratch, pivot) >= 0 &&
 863                                                                 lo < hi) {
 864                                 if (xfarray_sort_terminated(si, &error))
 865                                         goto out_free;
 866
 867                                 hi--;
 868                                 error = xfarray_sort_load(si, hi, scratch);
 869                                 if (error)
 870                                         goto out_free;
 871                         }
 872
 873                         if (xfarray_sort_terminated(si, &error))
 874                                 goto out_free;
 875
 876                         /* Copy that item (a[hi]) to a[lo]. */
 877                         if (lo < hi) {
 878                                 error = xfarray_sort_store(si, lo++, scratch);
 879                                 if (error)
 880                                         goto out_free;
 881                         }
 882
 883                         /*
 884                          * Increment lo until it finds an a[lo] greater than
 885                          * the pivot value.
 886                          */
 887                         error = xfarray_sort_load(si, lo, scratch);
 888                         if (error)
 889                                 goto out_free;
 890                         while (xfarray_sort_cmp(si, scratch, pivot) <= 0 &&
 891                                                                 lo < hi) {
 892                                 if (xfarray_sort_terminated(si, &error))
 893                                         goto out_free;
 894
 895                                 lo++;
 896                                 error = xfarray_sort_load(si, lo, scratch);
 897                                 if (error)
 898                                         goto out_free;
 899                         }
 900
 901                         if (xfarray_sort_terminated(si, &error))
 902                                 goto out_free;
 903
 904                         /* Copy that item (a[lo]) to a[hi]. */
 905                         if (lo < hi) {
 906                                 error = xfarray_sort_store(si, hi--, scratch);
 907                                 if (error)
 908                                         goto out_free;
 909                         }
 910
 911                         if (xfarray_sort_terminated(si, &error))
 912                                 goto out_free;
 913                 }
 914
 915                 /*
 916                  * Put our pivot value in the correct place at a[lo].  All
 917                  * values between a[beg[i]] and a[lo - 1] should be less than
 918                  * the pivot; and all values between a[lo + 1] and a[end[i]-1]
 919                  * should be greater than the pivot.
 920                  */
 921                 error = xfarray_sort_store(si, lo, pivot);
 922                 if (error)
 923                         goto out_free;
 924
 925                 /* Set up the stack frame to process the two partitions. */
 926                 error = xfarray_qsort_push(si, si_lo, si_hi, lo, hi);
 927                 if (error)
 928                         goto out_free;
 929
 930                 if (xfarray_sort_terminated(si, &error))
 931                         goto out_free;
 932         }
 933
 934 out_free:
 935         trace_xfarray_sort_stats(si, error);
 936         kvfree(si);
 937         return error;
 938 }