| /* SPDX-License-Identifier: GPL-2.0-or-later */ |
| /* |
| * Copyright (C) 2021-2023 Oracle. All Rights Reserved. |
| * Author: Darrick J. Wong <djwong@kernel.org> |
| */ |
| #ifndef __XFS_SCRUB_XFARRAY_H__ |
| #define __XFS_SCRUB_XFARRAY_H__ |
| |
| /* xfile array index type, along with cursor initialization */ |
| typedef uint64_t xfarray_idx_t; |
| #define XFARRAY_CURSOR_INIT ((__force xfarray_idx_t)0) |
| |
| /* Iterate each index of an xfile array. */ |
| #define foreach_xfarray_idx(array, idx) \ |
| for ((idx) = XFARRAY_CURSOR_INIT; \ |
| (idx) < xfarray_length(array); \ |
| (idx)++) |
| |
| struct xfarray { |
| /* Underlying file that backs the array. */ |
| struct xfile *xfile; |
| |
| /* Number of array elements. */ |
| xfarray_idx_t nr; |
| |
| /* Maximum possible array size. */ |
| xfarray_idx_t max_nr; |
| |
| /* Number of unset slots in the array below @nr. */ |
| uint64_t unset_slots; |
| |
| /* Size of an array element. */ |
| size_t obj_size; |
| |
| /* log2 of array element size, if possible. */ |
| int obj_size_log; |
| }; |
| |
| int xfarray_create(const char *descr, unsigned long long required_capacity, |
| size_t obj_size, struct xfarray **arrayp); |
| void xfarray_destroy(struct xfarray *array); |
| int xfarray_load(struct xfarray *array, xfarray_idx_t idx, void *ptr); |
| int xfarray_unset(struct xfarray *array, xfarray_idx_t idx); |
| int xfarray_store(struct xfarray *array, xfarray_idx_t idx, const void *ptr); |
| int xfarray_store_anywhere(struct xfarray *array, const void *ptr); |
| bool xfarray_element_is_null(struct xfarray *array, const void *ptr); |
| |
| /* |
| * Load an array element, but zero the buffer if there's no data because we |
| * haven't stored to that array element yet. |
| */ |
| static inline int |
| xfarray_load_sparse( |
| struct xfarray *array, |
| uint64_t idx, |
| void *rec) |
| { |
| int error = xfarray_load(array, idx, rec); |
| |
| if (error == -ENODATA) { |
| memset(rec, 0, array->obj_size); |
| return 0; |
| } |
| return error; |
| } |
| |
| /* Append an element to the array. */ |
| static inline int xfarray_append(struct xfarray *array, const void *ptr) |
| { |
| return xfarray_store(array, array->nr, ptr); |
| } |
| |
| uint64_t xfarray_length(struct xfarray *array); |
| int xfarray_load_next(struct xfarray *array, xfarray_idx_t *idx, void *rec); |
| |
| /* |
| * Iterate the non-null elements in a sparse xfarray. Callers should |
| * initialize *idx to XFARRAY_CURSOR_INIT before the first call; on return, it |
| * will be set to one more than the index of the record that was retrieved. |
| * Returns 1 if a record was retrieved, 0 if there weren't any more records, or |
| * a negative errno. |
| */ |
| static inline int |
| xfarray_iter( |
| struct xfarray *array, |
| xfarray_idx_t *idx, |
| void *rec) |
| { |
| int ret = xfarray_load_next(array, idx, rec); |
| |
| if (ret == -ENODATA) |
| return 0; |
| if (ret == 0) |
| return 1; |
| return ret; |
| } |
| |
| /* Declarations for xfile array sort functionality. */ |
| |
| typedef cmp_func_t xfarray_cmp_fn; |
| |
| /* Perform an in-memory heapsort for small subsets. */ |
| #define XFARRAY_ISORT_SHIFT (4) |
| #define XFARRAY_ISORT_NR (1U << XFARRAY_ISORT_SHIFT) |
| |
| /* Evalulate this many points to find the qsort pivot. */ |
| #define XFARRAY_QSORT_PIVOT_NR (9) |
| |
| struct xfarray_sortinfo { |
| struct xfarray *array; |
| |
| /* Comparison function for the sort. */ |
| xfarray_cmp_fn cmp_fn; |
| |
| /* Maximum height of the partition stack. */ |
| uint8_t max_stack_depth; |
| |
| /* Current height of the partition stack. */ |
| int8_t stack_depth; |
| |
| /* Maximum stack depth ever used. */ |
| uint8_t max_stack_used; |
| |
| /* XFARRAY_SORT_* flags; see below. */ |
| unsigned int flags; |
| |
| /* Cache a folio here for faster scanning for pivots */ |
| struct folio *folio; |
| |
| /* First array index in folio that is completely readable */ |
| xfarray_idx_t first_folio_idx; |
| |
| /* Last array index in folio that is completely readable */ |
| xfarray_idx_t last_folio_idx; |
| |
| #ifdef DEBUG |
| /* Performance statistics. */ |
| uint64_t loads; |
| uint64_t stores; |
| uint64_t compares; |
| uint64_t heapsorts; |
| #endif |
| /* |
| * Extra bytes are allocated beyond the end of the structure to store |
| * quicksort information. C does not permit multiple VLAs per struct, |
| * so we document all of this in a comment. |
| * |
| * Pretend that we have a typedef for array records: |
| * |
| * typedef char[array->obj_size] xfarray_rec_t; |
| * |
| * First comes the quicksort partition stack: |
| * |
| * xfarray_idx_t lo[max_stack_depth]; |
| * xfarray_idx_t hi[max_stack_depth]; |
| * |
| * union { |
| * |
| * If for a given subset we decide to use an in-memory sort, we use a |
| * block of scratchpad records here to compare items: |
| * |
| * xfarray_rec_t scratch[ISORT_NR]; |
| * |
| * Otherwise, we want to partition the records to partition the array. |
| * We store the chosen pivot record at the start of the scratchpad area |
| * and use the rest to sample some records to estimate the median. |
| * The format of the qsort_pivot array enables us to use the kernel |
| * heapsort function to place the median value in the middle. |
| * |
| * struct { |
| * xfarray_rec_t pivot; |
| * struct { |
| * xfarray_rec_t rec; (rounded up to 8 bytes) |
| * xfarray_idx_t idx; |
| * } qsort_pivot[QSORT_PIVOT_NR]; |
| * }; |
| * } |
| */ |
| }; |
| |
| /* Sort can be interrupted by a fatal signal. */ |
| #define XFARRAY_SORT_KILLABLE (1U << 0) |
| |
| int xfarray_sort(struct xfarray *array, xfarray_cmp_fn cmp_fn, |
| unsigned int flags); |
| |
| #endif /* __XFS_SCRUB_XFARRAY_H__ */ |