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