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 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 /* Cache a folio here for faster scanning for pivots */ 130 struct folio *folio; 131 132 /* First array index in folio that is completely readable */ 133 xfarray_idx_t first_folio_idx; 134 135 /* Last array index in folio that is completely readable */ 136 xfarray_idx_t last_folio_idx; 137 138 #ifdef DEBUG 139 /* Performance statistics. */ 140 uint64_t loads; 141 uint64_t stores; 142 uint64_t compares; 143 uint64_t heapsorts; 144 #endif 145 /* 146 * Extra bytes are allocated beyond the end of the structure to store 147 * quicksort information. C does not permit multiple VLAs per struct, 148 * so we document all of this in a comment. 149 * 150 * Pretend that we have a typedef for array records: 151 * 152 * typedef char[array->obj_size] xfarray_rec_t; 153 * 154 * First comes the quicksort partition stack: 155 * 156 * xfarray_idx_t lo[max_stack_depth]; 157 * xfarray_idx_t hi[max_stack_depth]; 158 * 159 * union { 160 * 161 * If for a given subset we decide to use an in-memory sort, we use a 162 * block of scratchpad records here to compare items: 163 * 164 * xfarray_rec_t scratch[ISORT_NR]; 165 * 166 * Otherwise, we want to partition the records to partition the array. 167 * We store the chosen pivot record at the start of the scratchpad area 168 * and use the rest to sample some records to estimate the median. 169 * The format of the qsort_pivot array enables us to use the kernel 170 * heapsort function to place the median value in the middle. 171 * 172 * struct { 173 * xfarray_rec_t pivot; 174 * struct { 175 * xfarray_rec_t rec; (rounded up to 8 bytes) 176 * xfarray_idx_t idx; 177 * } qsort_pivot[QSORT_PIVOT_NR]; 178 * }; 179 * } 180 */ 181 }; 182 183 /* Sort can be interrupted by a fatal signal. */ 184 #define XFARRAY_SORT_KILLABLE (1U << 0) 185 186 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn, 187 unsigned int flags); 188 189 #endif /* __XFS_SCRUB_XFARRAY_H__ */ 190