[linux-block.git] / fs / xfs / scrub / xfarray.h

/* 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__ */
Commit	Line	Data
3934e8eb DW	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
5a3ab584 DW	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
3934e8eb DW	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
4bdfd7d1 DW	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
232ea052 DW	98	/* Declarations for xfile array sort functionality. */
	99
	100	typedef cmp_func_t xfarray_cmp_fn;
	101
c390c645 DW	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
764018ca DW	106	/* Evalulate this many points to find the qsort pivot. */
	107	#define XFARRAY_QSORT_PIVOT_NR (9)
	108
232ea052 DW	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
ee13fc67 DW	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;
e5b46c75	135
232ea052 DW	136	#ifdef DEBUG
	137	/* Performance statistics. */
	138	uint64_t loads;
	139	uint64_t stores;
	140	uint64_t compares;
c390c645	141	uint64_t heapsorts;
232ea052	142	#endif
232ea052 DW	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	*
c390c645 DW	159	* If for a given subset we decide to use an in-memory sort, we use a
c390c645 DW	160	* block of scratchpad records here to compare items:
232ea052	161	*
c390c645	162	* xfarray_rec_t scratch[ISORT_NR];
232ea052 DW	163	*
232ea052 DW	164	* Otherwise, we want to partition the records to partition the array.
764018ca DW	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.
232ea052	169	*
764018ca DW	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	* };
232ea052 DW	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
3934e8eb	187	#endif /* __XFS_SCRUB_XFARRAY_H__ */