194 lines · c
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 */10typedef 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 20struct 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 40int xfarray_create(const char *descr, unsigned long long required_capacity,41 size_t obj_size, struct xfarray **arrayp);42void xfarray_destroy(struct xfarray *array);43int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr);44int xfarray_unset(struct xfarray *array, xfarray_idx_t idx);45int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr);46int xfarray_store_anywhere(struct xfarray *array, const void *ptr);47bool xfarray_element_is_null(struct xfarray *array, const void *ptr);48void xfarray_truncate(struct xfarray *array);49unsigned long long xfarray_bytes(struct xfarray *array);50 51/*52 * Load an array element, but zero the buffer if there's no data because we53 * haven't stored to that array element yet.54 */55static inline int56xfarray_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. */71static inline int xfarray_append(struct xfarray *array, const void *ptr)72{73 return xfarray_store(array, array->nr, ptr);74}75 76uint64_t xfarray_length(struct xfarray *array);77int 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 should81 * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it82 * 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, or84 * a negative errno.85 */86static inline int87xfarray_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 103typedef 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 112struct 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 DEBUG143 /* Performance statistics. */144 uint64_t loads;145 uint64_t stores;146 uint64_t compares;147 uint64_t heapsorts;148#endif149 /*150 * Extra bytes are allocated beyond the end of the structure to store151 * 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 a166 * 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 area172 * 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 kernel174 * 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 190int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn,191 unsigned int flags);192 193#endif /* __XFS_SCRUB_XFARRAY_H__ */194