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