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 <djwong@kernel.org>
   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_NULLIDX         ((__force xfarray_idx_t)-1ULL)
  12 #define XFARRAY_CURSOR_INIT     ((__force xfarray_idx_t)0)
  13
  14 /* Iterate each index of an xfile array. */
  15 #define foreach_xfarray_idx(array, idx) \
  16         for ((idx) = XFARRAY_CURSOR_INIT; \
  17              (idx) < xfarray_length(array); \
  18              (idx)++)
  19
  20 struct xfarray {
  21         /* Underlying file that backs the array. */
  22         struct xfile    *xfile;
  23
  24         /* Number of array elements. */
  25         xfarray_idx_t   nr;
  26
  27         /* Maximum possible array size. */
  28         xfarray_idx_t   max_nr;
  29
  30         /* Number of unset slots in the array below @nr. */
  31         uint64_t        unset_slots;
  32
  33         /* Size of an array element. */
  34         size_t          obj_size;
  35
  36         /* log2 of array element size, if possible. */
  37         int             obj_size_log;
  38 };
  39
  40 int xfarray_create(const char *descr, unsigned long long required_capacity,
  41                 size_t obj_size, struct xfarray **arrayp);
  42 void xfarray_destroy(struct xfarray *array);
  43 int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr);
  44 int xfarray_unset(struct xfarray *array, xfarray_idx_t idx);
  45 int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr);
  46 int xfarray_store_anywhere(struct xfarray *array, const void *ptr);
  47 bool xfarray_element_is_null(struct xfarray *array, const void *ptr);
  48 void xfarray_truncate(struct xfarray *array);
  49 unsigned long long xfarray_bytes(struct xfarray *array);
  50
  51 /*
  52  * Load an array element, but zero the buffer if there's no data because we
  53  * haven't stored to that array element yet.
  54  */
  55 static inline int
  56 xfarray_load_sparse(
  57         struct xfarray  *array,
  58         uint64_t        idx,
  59         void            *rec)
  60 {
  61         int             error = xfarray_load(array, idx, rec);
  62
  63         if (error == -ENODATA) {
  64                 memset(rec, 0, array->obj_size);
  65                 return 0;
  66         }
  67         return error;
  68 }
  69
  70 /* Append an element to the array. */
  71 static inline int xfarray_append(struct xfarray *array, const void *ptr)
  72 {
  73         return xfarray_store(array, array->nr, ptr);
  74 }
  75
  76 uint64_t xfarray_length(struct xfarray *array);
  77 int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec);
  78
  79 /*
  80  * Iterate the non-null elements in a sparse xfarray.  Callers should
  81  * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it
  82  * will be set to one more than the index of the record that was retrieved.
  83  * Returns 1 if a record was retrieved, 0 if there weren't any more records, or
  84  * a negative errno.
  85  */
  86 static inline int
  87 xfarray_iter(
  88         struct xfarray  *array,
  89         xfarray_idx_t   *idx,
  90         void            *rec)
  91 {
  92         int ret = xfarray_load_next(array, idx, rec);
  93
  94         if (ret == -ENODATA)
  95                 return 0;
  96         if (ret == 0)
  97                 return 1;
  98         return ret;
  99 }
 100
 101 /* Declarations for xfile array sort functionality. */
 102
 103 typedef cmp_func_t xfarray_cmp_fn;
 104
 105 /* Perform an in-memory heapsort for small subsets. */
 106 #define XFARRAY_ISORT_SHIFT             (4)
 107 #define XFARRAY_ISORT_NR                (1U << XFARRAY_ISORT_SHIFT)
 108
 109 /* Evalulate this many points to find the qsort pivot. */
 110 #define XFARRAY_QSORT_PIVOT_NR          (9)
 111
 112 struct xfarray_sortinfo {
 113         struct xfarray          *array;
 114
 115         /* Comparison function for the sort. */
 116         xfarray_cmp_fn          cmp_fn;
 117
 118         /* Maximum height of the partition stack. */
 119         uint8_t                 max_stack_depth;
 120
 121         /* Current height of the partition stack. */
 122         int8_t                  stack_depth;
 123
 124         /* Maximum stack depth ever used. */
 125         uint8_t                 max_stack_used;
 126
 127         /* XFARRAY_SORT_* flags; see below. */
 128         unsigned int            flags;
 129
 130         /* next time we want to cond_resched() */
 131         struct xchk_relax       relax;
 132
 133         /* Cache a folio here for faster scanning for pivots */
 134         struct folio            *folio;
 135
 136         /* First array index in folio that is completely readable */
 137         xfarray_idx_t           first_folio_idx;
 138
 139         /* Last array index in folio that is completely readable */
 140         xfarray_idx_t           last_folio_idx;
 141
 142 #ifdef DEBUG
 143         /* Performance statistics. */
 144         uint64_t                loads;
 145         uint64_t                stores;
 146         uint64_t                compares;
 147         uint64_t                heapsorts;
 148 #endif
 149         /*
 150          * Extra bytes are allocated beyond the end of the structure to store
 151          * quicksort information.  C does not permit multiple VLAs per struct,
 152          * so we document all of this in a comment.
 153          *
 154          * Pretend that we have a typedef for array records:
 155          *
 156          * typedef char[array->obj_size]        xfarray_rec_t;
 157          *
 158          * First comes the quicksort partition stack:
 159          *
 160          * xfarray_idx_t        lo[max_stack_depth];
 161          * xfarray_idx_t        hi[max_stack_depth];
 162          *
 163          * union {
 164          *
 165          * If for a given subset we decide to use an in-memory sort, we use a
 166          * block of scratchpad records here to compare items:
 167          *
 168          *      xfarray_rec_t   scratch[ISORT_NR];
 169          *
 170          * Otherwise, we want to partition the records to partition the array.
 171          * We store the chosen pivot record at the start of the scratchpad area
 172          * and use the rest to sample some records to estimate the median.
 173          * The format of the qsort_pivot array enables us to use the kernel
 174          * heapsort function to place the median value in the middle.
 175          *
 176          *      struct {
 177          *              xfarray_rec_t   pivot;
 178          *              struct {
 179          *                      xfarray_rec_t   rec;  (rounded up to 8 bytes)
 180          *                      xfarray_idx_t   idx;
 181          *              } qsort_pivot[QSORT_PIVOT_NR];
 182          *      };
 183          * }
 184          */
 185 };
 186
 187 /* Sort can be interrupted by a fatal signal. */
 188 #define XFARRAY_SORT_KILLABLE   (1U << 0)
 189
 190 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
 191                 unsigned int flags);
 192
 193 #endif /* __XFS_SCRUB_XFARRAY_H__ */