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 /* 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 */ 52 static inline int 53 xfarray_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. */ 68 static inline int xfarray_append(struct xfarray *array, const void *ptr) 69 { 70 return xfarray_store(array, array->nr, ptr); 71 } 72 73 uint64_t xfarray_length(struct xfarray *array); 74 int 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 */ 83 static inline int 84 xfarray_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 100 typedef 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 109 struct 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 184 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn, 185 unsigned int flags); 186 187 #endif /* __XFS_SCRUB_XFARRAY_H__ */ 188