path: root/fs/xfs/scrub/xfarray.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Copyright (C) 2021-2023 Oracle.  All Rights Reserved.
 * Author: Darrick J. Wong <djwong@kernel.org>
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "scrub/xfile.h"
#include "scrub/xfarray.h"
#include "scrub/scrub.h"
#include "scrub/trace.h"

/*
 * Large Arrays of Fixed-Size Records
 * ==================================
 *
 * This memory array uses an xfile (which itself is a memfd "file") to store
 * large numbers of fixed-size records in memory that can be paged out.  This
 * puts less stress on the memory reclaim algorithms during an online repair
 * because we don't have to pin so much memory.  However, array access is less
 * direct than would be in a regular memory array.  Access to the array is
 * performed via indexed load and store methods, and an append method is
 * provided for convenience.  Array elements can be unset, which sets them to
 * all zeroes.  Unset entries are skipped during iteration, though direct loads
 * will return a zeroed buffer.  Callers are responsible for concurrency
 * control.
 */

/*
 * Pointer to scratch space.  Because we can't access the xfile data directly,
 * we allocate a small amount of memory on the end of the xfarray structure to
 * buffer array items when we need space to store values temporarily.
 */
static inline void *xfarray_scratch(struct xfarray *array)
{
	return (array + 1);
}

/* Compute array index given an xfile offset. */
static xfarray_idx_t
xfarray_idx(
	struct xfarray	*array,
	loff_t		pos)
{
	if (array->obj_size_log >= 0)
		return (xfarray_idx_t)pos >> array->obj_size_log;

	return div_u64((xfarray_idx_t)pos, array->obj_size);
}

/* Compute xfile offset of array element. */
static inline loff_t xfarray_pos(struct xfarray *array, xfarray_idx_t idx)
{
	if (array->obj_size_log >= 0)
		return idx << array->obj_size_log;

	return idx * array->obj_size;
}

/*
 * Initialize a big memory array.  Array records cannot be larger than a
 * page, and the array cannot span more bytes than the page cache supports.
 * If @required_capacity is nonzero, the maximum array size will be set to this
 * quantity and the array creation will fail if the underlying storage cannot
 * support that many records.
 */
int
xfarray_create(
	const char		*description,
	unsigned long long	required_capacity,
	size_t			obj_size,
	struct xfarray		**arrayp)
{
	struct xfarray		*array;
	struct xfile		*xfile;
	int			error;

	ASSERT(obj_size < PAGE_SIZE);

	error = xfile_create(description, 0, &xfile);
	if (error)
		return error;

	error = -ENOMEM;
	array = kzalloc(sizeof(struct xfarray) + obj_size, XCHK_GFP_FLAGS);
	if (!array)
		goto out_xfile;

	array->xfile = xfile;
	array->obj_size = obj_size;

	if (is_power_of_2(obj_size))
		array->obj_size_log = ilog2(obj_size);
	else
		array->obj_size_log = -1;

	array->max_nr = xfarray_idx(array, MAX_LFS_FILESIZE);
	trace_xfarray_create(array, required_capacity);

	if (required_capacity > 0) {
		if (array->max_nr < required_capacity) {
			error = -ENOMEM;
			goto out_xfarray;
		}
		array->max_nr = required_capacity;
	}

	*arrayp = array;
	return 0;

out_xfarray:
	kfree(array);
out_xfile:
	xfile_destroy(xfile);
	return error;
}

/* Destroy the array. */
void
xfarray_destroy(
	struct xfarray	*array)
{
	xfile_destroy(array->xfile);
	kfree(array);
}

/* Load an element from the array. */
int
xfarray_load(
	struct xfarray	*array,
	xfarray_idx_t	idx,
	void		*ptr)
{
	if (idx >= array->nr)
		return -ENODATA;

	return xfile_obj_load(array->xfile, ptr, array->obj_size,
			xfarray_pos(array, idx));
}

/* Is this array element potentially unset? */
static inline bool
xfarray_is_unset(
	struct xfarray	*array,
	loff_t		pos)
{
	void		*temp = xfarray_scratch(array);
	int		error;

	if (array->unset_slots == 0)
		return false;

	error = xfile_obj_load(array->xfile, temp, array->obj_size, pos);
	if (!error && xfarray_element_is_null(array, temp))
		return true;

	return false;
}

/*
 * Unset an array element.  If @idx is the last element in the array, the
 * array will be truncated.  Otherwise, the entry will be zeroed.
 */
int
xfarray_unset(
	struct xfarray	*array,
	xfarray_idx_t	idx)
{
	void		*temp = xfarray_scratch(array);
	loff_t		pos = xfarray_pos(array, idx);
	int		error;

	if (idx >= array->nr)
		return -ENODATA;

	if (idx == array->nr - 1) {
		array->nr--;
		return 0;
	}

	if (xfarray_is_unset(array, pos))
		return 0;

	memset(temp, 0, array->obj_size);
	error = xfile_obj_store(array->xfile, temp, array->obj_size, pos);
	if (error)
		return error;

	array->unset_slots++;
	return 0;
}

/*
 * Store an element in the array.  The element must not be completely zeroed,
 * because those are considered unset sparse elements.
 */
int
xfarray_store(
	struct xfarray	*array,
	xfarray_idx_t	idx,
	const void	*ptr)