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 /* Append an element to the array. */ 49 static inline int xfarray_append(struct xfarray *array, const void *ptr) 50 { 51 return xfarray_store(array, array->nr, ptr); 52 } 53 54 uint64_t xfarray_length(struct xfarray *array); 55 int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec); 56 57 /* 58 * Iterate the non-null elements in a sparse xfarray. Callers should 59 * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it 60 * will be set to one more than the index of the record that was retrieved. 61 * Returns 1 if a record was retrieved, 0 if there weren't any more records, or 62 * a negative errno. 63 */ 64 static inline int 65 xfarray_iter( 66 struct xfarray *array, 67 xfarray_idx_t *idx, 68 void *rec) 69 { 70 int ret = xfarray_load_next(array, idx, rec); 71 72 if (ret == -ENODATA) 73 return 0; 74 if (ret == 0) 75 return 1; 76 return ret; 77 } 78 79 /* Declarations for xfile array sort functionality. */ 80 81 typedef cmp_func_t xfarray_cmp_fn; 82 83 /* Perform an in-memory heapsort for small subsets. */ 84 #define XFARRAY_ISORT_SHIFT (4) 85 #define XFARRAY_ISORT_NR (1U << XFARRAY_ISORT_SHIFT) 86 87 /* Evalulate this many points to find the qsort pivot. */ 88 #define XFARRAY_QSORT_PIVOT_NR (9) 89 90 struct xfarray_sortinfo { 91 struct xfarray *array; 92 93 /* Comparison function for the sort. */ 94 xfarray_cmp_fn cmp_fn; 95 96 /* Maximum height of the partition stack. */ 97 uint8_t max_stack_depth; 98 99 /* Current height of the partition stack. */ 100 int8_t stack_depth; 101 102 /* Maximum stack depth ever used. */ 103 uint8_t max_stack_used; 104 105 /* XFARRAY_SORT_* flags; see below. */ 106 unsigned int flags; 107 108 /* Cache a page here for faster access. */ 109 struct xfile_page xfpage; 110 void *page_kaddr; 111 112 #ifdef DEBUG 113 /* Performance statistics. */ 114 uint64_t loads; 115 uint64_t stores; 116 uint64_t compares; 117 uint64_t heapsorts; 118 #endif 119 /* 120 * Extra bytes are allocated beyond the end of the structure to store 121 * quicksort information. C does not permit multiple VLAs per struct, 122 * so we document all of this in a comment. 123 * 124 * Pretend that we have a typedef for array records: 125 * 126 * typedef char[array->obj_size] xfarray_rec_t; 127 * 128 * First comes the quicksort partition stack: 129 * 130 * xfarray_idx_t lo[max_stack_depth]; 131 * xfarray_idx_t hi[max_stack_depth]; 132 * 133 * union { 134 * 135 * If for a given subset we decide to use an in-memory sort, we use a 136 * block of scratchpad records here to compare items: 137 * 138 * xfarray_rec_t scratch[ISORT_NR]; 139 * 140 * Otherwise, we want to partition the records to partition the array. 141 * We store the chosen pivot record at the start of the scratchpad area 142 * and use the rest to sample some records to estimate the median. 143 * The format of the qsort_pivot array enables us to use the kernel 144 * heapsort function to place the median value in the middle. 145 * 146 * struct { 147 * xfarray_rec_t pivot; 148 * struct { 149 * xfarray_rec_t rec; (rounded up to 8 bytes) 150 * xfarray_idx_t idx; 151 * } qsort_pivot[QSORT_PIVOT_NR]; 152 * }; 153 * } 154 */ 155 }; 156 157 /* Sort can be interrupted by a fatal signal. */ 158 #define XFARRAY_SORT_KILLABLE (1U << 0) 159 160 int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn, 161 unsigned int flags); 162 163 #endif /* __XFS_SCRUB_XFARRAY_H__ */ 164