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