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 */ 10typedef 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 19struct 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 39int xfarray_create(const char *descr, unsigned long long required_capacity, 40 size_t obj_size, struct xfarray **arrayp); 41void xfarray_destroy(struct xfarray *array); 42int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr); 43int xfarray_unset(struct xfarray *array, xfarray_idx_t idx); 44int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr); 45int xfarray_store_anywhere(struct xfarray *array, const void *ptr); 46bool 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 */ 52static inline int 53xfarray_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. */ 68static inline int xfarray_append(struct xfarray *array, const void *ptr) 69{ 70 return xfarray_store(array, array->nr, ptr); 71} 72 73uint64_t xfarray_length(struct xfarray *array); 74int 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 */ 83static inline int 84xfarray_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 100typedef 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 109struct 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 184int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn, 185 unsigned int flags); 186 187#endif /* __XFS_SCRUB_XFARRAY_H__ */ 188