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