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_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 struct xfarray_sortinfo {
  66         struct xfarray          *array;
  67
  68         /* Comparison function for the sort. */
  69         xfarray_cmp_fn          cmp_fn;
  70
  71         /* Maximum height of the partition stack. */
  72         uint8_t                 max_stack_depth;
  73
  74         /* Current height of the partition stack. */
  75         int8_t                  stack_depth;
  76
  77         /* Maximum stack depth ever used. */
  78         uint8_t                 max_stack_used;
  79
  80         /* XFARRAY_SORT_* flags; see below. */
  81         unsigned int            flags;
  82
  83 #ifdef DEBUG
  84         /* Performance statistics. */
  85         uint64_t                loads;
  86         uint64_t                stores;
  87         uint64_t                compares;
  88         uint64_t                heapsorts;
  89 #endif
  90
  91         /*
  92          * Extra bytes are allocated beyond the end of the structure to store
  93          * quicksort information.  C does not permit multiple VLAs per struct,
  94          * so we document all of this in a comment.
  95          *
  96          * Pretend that we have a typedef for array records:
  97          *
  98          * typedef char[array->obj_size]        xfarray_rec_t;
  99          *
 100          * First comes the quicksort partition stack:
 101          *
 102          * xfarray_idx_t        lo[max_stack_depth];
 103          * xfarray_idx_t        hi[max_stack_depth];
 104          *
 105          * union {
 106          *
 107          * If for a given subset we decide to use an in-memory sort, we use a
 108          * block of scratchpad records here to compare items:
 109          *
 110          *      xfarray_rec_t   scratch[ISORT_NR];
 111          *
 112          * Otherwise, we want to partition the records to partition the array.
 113          * We store the chosen pivot record here and use the xfarray scratchpad
 114          * to rearrange the array around the pivot:
 115          *
 116          *      xfarray_rec_t   pivot;
 117          *
 118          * }
 119          */
 120 };
 121
 122 /* Sort can be interrupted by a fatal signal. */
 123 #define XFARRAY_SORT_KILLABLE   (1U << 0)
 124
 125 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,
 126                 unsigned int flags);
 127
 128 #endif /* __XFS_SCRUB_XFARRAY_H__ */