fs/xfs/scrub/xfarray.h

   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 #ifndef __XFS_SCRUB_XFARRAY_H__
   7 #define __XFS_SCRUB_XFARRAY_H__
   8
   9 /* xfile array index type, along with cursor initialization */
  10 typedef uint64_t                xfarray_idx_t;
  11 #define XFARRAY_CURSOR_INIT     ((__force xfarray_idx_t)0)
  12
  13 /* Iterate each index of an xfile array. */
  14 #define foreach_xfarray_idx(array, idx) \
  15         for ((idx) = XFARRAY_CURSOR_INIT; \
  16              (idx) < xfarray_length(array); \
  17              (idx)++)
  18
  19 struct xfarray {
  20         /* Underlying file that backs the array. */
  21         struct xfile    *xfile;
  22
  23         /* Number of array elements. */
  24         xfarray_idx_t   nr;
  25
  26         /* Maximum possible array size. */
  27         xfarray_idx_t   max_nr;
  28
  29         /* Number of unset slots in the array below @nr. */
  30         uint64_t        unset_slots;
  31
  32         /* Size of an array element. */
  33         size_t          obj_size;
  34
  35         /* log2 of array element size, if possible. */
  36         int             obj_size_log;
  37 };
  38
  39 int xfarray_create(const char *descr, unsigned long long required_capacity,
  40                 size_t obj_size, struct xfarray **arrayp);
  41 void xfarray_destroy(struct xfarray *array);
  42 int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr);
  43 int xfarray_unset(struct xfarray *array, xfarray_idx_t idx);
  44 int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr);
  45 int xfarray_store_anywhere(struct xfarray *array, const void *ptr);
  46 bool xfarray_element_is_null(struct xfarray *array, const void *ptr);
  47
  48 /* Append an element to the array. */
  49 static inline int xfarray_append(struct xfarray *array, const void *ptr)
  50 {
  51         return xfarray_store(array, array->nr, ptr);
  52 }
  53
  54 uint64_t xfarray_length(struct xfarray *array);
  55 int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec);
  56
  57 /* Declarations for xfile array sort functionality. */
  58
  59 typedef cmp_func_t xfarray_cmp_fn;
  60
  61 /* Perform an in-memory heapsort for small subsets. */
  62 #define XFARRAY_ISORT_SHIFT             (4)
  63 #define XFARRAY_ISORT_NR                (1U << XFARRAY_ISORT_SHIFT)
  64
  65 /* Evalulate this many points to find the qsort pivot. */
  66 #define XFARRAY_QSORT_PIVOT_NR          (9)
  67
  68 struct xfarray_sortinfo {
  69         struct xfarray          *array;
  70
  71         /* Comparison function for the sort. */
  72         xfarray_cmp_fn          cmp_fn;
  73
  74         /* Maximum height of the partition stack. */
  75         uint8_t                 max_stack_depth;
  76
  77         /* Current height of the partition stack. */
  78         int8_t                  stack_depth;
  79
  80         /* Maximum stack depth ever used. */
  81         uint8_t                 max_stack_used;
  82
  83         /* XFARRAY_SORT_* flags; see below. */
  84         unsigned int            flags;
  85
  86         /* Cache a page here for faster access. */
  87         struct xfile_page       xfpage;
  88         void                    *page_kaddr;
  89
  90 #ifdef DEBUG
  91         /* Performance statistics. */
  92         uint64_t                loads;
  93         uint64_t                stores;
  94         uint64_t                compares;
  95         uint64_t                heapsorts;
  96 #endif
  97         /*
  98          * Extra bytes are allocated beyond the end of the structure to store
  99          * quicksort information.  C does not permit multiple VLAs per struct,
 100          * so we document all of this in a comment.
 101          *
 102          * Pretend that we have a typedef for array records:
 103          *
 104          * typedef char[array->obj_size]        xfarray_rec_t;
 105          *
 106          * First comes the quicksort partition stack:
 107          *
 108          * xfarray_idx_t        lo[max_stack_depth];
 109          * xfarray_idx_t        hi[max_stack_depth];
 110          *
 111          * union {
 112          *
 113          * If for a given subset we decide to use an in-memory sort, we use a
 114          * block of scratchpad records here to compare items:
 115          *
 116          *      xfarray_rec_t   scratch[ISORT_NR];
 117          *
 118          * Otherwise, we want to partition the records to partition the array.
 119          * We store the chosen pivot record at the start of the scratchpad area
 120          * and use the rest to sample some records to estimate the median.
 121          * The format of the qsort_pivot array enables us to use the kernel
 122          * heapsort function to place the median value in the middle.
 123          *
 124          *      struct {
 125          *              xfarray_rec_t   pivot;
 126          *              struct {
 127          *                      xfarray_rec_t   rec;  (rounded up to 8 bytes)
 128          *                      xfarray_idx_t   idx;
 129          *              } qsort_pivot[QSORT_PIVOT_NR];
 130          *      };
 131          * }
 132          */
 133 };
 134
 135 /* Sort can be interrupted by a fatal signal. */
 136 #define XFARRAY_SORT_KILLABLE   (1U << 0)
 137
 138 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
 139                 unsigned int flags);
 140
 141 #endif /* __XFS_SCRUB_XFARRAY_H__ */