xfs/scrub/xfarray.c

19  * This memory array uses an xfile (which itself is a shmem file) to store
22  * because we don't have to pin so much memory.  However, array access is less
23  * direct than would be in a regular memory array.  Access to the array is
34  * buffer array items when we need space to store values temporarily.
36 static inline void *xfarray_scratch(struct xfarray *array)
38 	return (array + 1);
41 /* Compute array index given an xfile offset. */
44 	struct xfarray	*array,
47 	if (array->obj_size_log >= 0)
48 		return (xfarray_idx_t)pos >> array->obj_size_log;
50 	return div_u64((xfarray_idx_t)pos, array->obj_size);
53 /* Compute xfile offset of array element. */
54 static inline loff_t xfarray_pos(struct xfarray *array, xfarray_idx_t idx)
56 	if (array->obj_size_log >= 0)
57 		return idx << array->obj_size_log;
59 	return idx * array->obj_size;
63  * Initialize a big memory array.  Array records cannot be larger than a
64  * page, and the array cannot span more bytes than the page cache supports.
65  * If @required_capacity is nonzero, the maximum array size will be set to this
66  * quantity and the array creation will fail if the underlying storage cannot
76 	struct xfarray		*array;
87 	array = kzalloc(sizeof(struct xfarray) + obj_size, XCHK_GFP_FLAGS);
88 	if (!array)
91 	array->xfile = xfile;
92 	array->obj_size = obj_size;
95 		array->obj_size_log = ilog2(obj_size);
97 		array->obj_size_log = -1;
99 	array->max_nr = xfarray_idx(array, MAX_LFS_FILESIZE);
100 	trace_xfarray_create(array, required_capacity);
103 		if (array->max_nr < required_capacity) {
107 		array->max_nr = required_capacity;
110 	*arrayp = array;
114 	kfree(array);
120 /* Destroy the array. */
123 	struct xfarray	*array)
125 	xfile_destroy(array->xfile);
126 	kfree(array);
129 /* Load an element from the array. */
132 	struct xfarray	*array,
136 	if (idx >= array->nr)
139 	return xfile_load(array->xfile, ptr, array->obj_size,
140 			xfarray_pos(array, idx));
143 /* Is this array element potentially unset? */
146 	struct xfarray	*array,
149 	void		*temp = xfarray_scratch(array);
152 	if (array->unset_slots == 0)
155 	error = xfile_load(array->xfile, temp, array->obj_size, pos);
156 	if (!error && xfarray_element_is_null(array, temp))
163  * Unset an array element.  If @idx is the last element in the array, the
164  * array will be truncated.  Otherwise, the entry will be zeroed.
168 	struct xfarray	*array,
171 	void		*temp = xfarray_scratch(array);
172 	loff_t		pos = xfarray_pos(array, idx);
175 	if (idx >= array->nr)
178 	if (idx == array->nr - 1) {
179 		array->nr--;
183 	if (xfarray_is_unset(array, pos))
186 	memset(temp, 0, array->obj_size);
187 	error = xfile_store(array->xfile, temp, array->obj_size, pos);
191 	array->unset_slots++;
196  * Store an element in the array.  The element must not be completely zeroed,
201 	struct xfarray	*array,
207 	if (idx >= array->max_nr)
210 	ASSERT(!xfarray_element_is_null(array, ptr));
212 	ret = xfile_store(array->xfile, ptr, array->obj_size,
213 			xfarray_pos(array, idx));
217 	array->nr = max(array->nr, idx + 1);
221 /* Is this array element NULL? */
224 	struct xfarray	*array,
227 	return !memchr_inv(ptr, 0, array->obj_size);
231  * Store an element anywhere in the array that is unset.  If there are no
232  * unset slots, append the element to the array.
236 	struct xfarray	*array,
239 	void		*temp = xfarray_scratch(array);
240 	loff_t		endpos = xfarray_pos(array, array->nr);
246 	     pos < endpos && array->unset_slots > 0;
247 	     pos += array->obj_size) {
248 		error = xfile_load(array->xfile, temp, array->obj_size,
250 		if (error || !xfarray_element_is_null(array, temp))
253 		error = xfile_store(array->xfile, ptr, array->obj_size,
258 		array->unset_slots--;
263 	array->unset_slots = 0;
264 	return xfarray_append(array, ptr);
267 /* Return length of array. */
270 	struct xfarray	*array)
272 	return array->nr;
276  * Decide which array item we're going to read as part of an _iter_get.
277  * @cur is the array index, and @pos is the file offset of that array index in
281  * iterating a (possibly sparse) array we need to figure out if the cursor is
287 	struct xfarray	*array,
292 	loff_t		end_pos = *pos + array->obj_size - 1;
296 	 * If the current array record is not adjacent to a page boundary, we
299 	if (pgoff != 0 && pgoff + array->obj_size - 1 < PAGE_SIZE)
313 	new_pos = xfile_seek_data(array->xfile, end_pos);
323 	 * find more data.  Move the array index to the first record past the
326 	new_pos = roundup_64(new_pos, array->obj_size);
327 	*cur = xfarray_idx(array, new_pos);
328 	*pos = xfarray_pos(array, *cur);
333  * Starting at *idx, fetch the next non-null array entry and advance the index
335  * the array.  Callers must set @*idx to XFARRAY_CURSOR_INIT before the first
340 	struct xfarray	*array,
345 	loff_t		pos = xfarray_pos(array, cur);
349 		if (cur >= array->nr)
356 		error = xfarray_find_data(array, &cur, &pos);
359 		error = xfarray_load(array, cur, rec);
364 		pos += array->obj_size;
365 	} while (xfarray_element_is_null(array, rec));
385 /* Load an array element for sorting. */
393 	return xfarray_load(si->array, idx, ptr);
396 /* Store an array element for sorting. */
404 	return xfarray_store(si->array, idx, ptr);
407 /* Compare an array element for sorting. */
430 /* Size of each element in the quicksort pivot array. */
433 	struct xfarray		*array)
435 	return round_up(array->obj_size, 8) + sizeof(xfarray_idx_t);
441 	struct xfarray		*array,
448 	size_t			pivot_rec_sz = xfarray_pivot_rec_sz(array);
465 	max_stack_depth = ilog2(array->nr) + 1 - (XFARRAY_ISORT_SHIFT - 1);
475 			XFARRAY_ISORT_NR * array->obj_size);
481 	si->array = array;
488 	xfarray_sortinfo_hi(si)[0] = array->nr - 1;
525 	 * For array subsets that fit in the scratchpad, it's much faster to
538  * Sort a small number of array records using scratchpad memory.  The records
548 	loff_t			lo_pos = xfarray_pos(si->array, lo);
549 	loff_t			len = xfarray_pos(si->array, hi - lo + 1);
555 	error = xfile_load(si->array->xfile, scratch, len, lo_pos);
560 	sort(scratch, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
563 	return xfile_store(si->array->xfile, scratch, len, lo_pos);
579 	loff_t			lo_pos = xfarray_pos(si->array, lo);
580 	uint64_t		len = xfarray_pos(si->array, hi - lo + 1);
587 	folio = xfile_get_folio(si->array->xfile, lo_pos, len, XFILE_ALLOC);
597 	sort(startp, hi - lo + 1, si->array->obj_size, si->cmp_fn, NULL);
600 	xfile_put_folio(si->array->xfile, folio);
610 /* Return a pointer to the start of the pivot array. */
615 	return xfarray_sortinfo_pivot(si) + si->array->obj_size;
618 /* The xfarray record is stored at the start of each pivot array element. */
628 /* The xfarray index is stored at the end of each pivot array element. */
646  * quicksort behavior, since our array values are nearly always evenly sorted.
659 	size_t			pivot_rec_sz = xfarray_pivot_rec_sz(si->array);
667 	 * pivot array.
679 	/* Load the selected xfarray records into the pivot array. */
686 		/* No unset records; load directly into the array. */
687 		if (likely(si->array->unset_slots == 0)) {
696 		 * the xfarray_idx_t in the pivot array.
700 		error = xfarray_load_next(si->array, &idx, recp);
709 	 * We sorted the pivot array records (which includes the xfarray
711 	 * array contains the xfarray record that we will use as the pivot.
716 	memcpy(pivot, recp, si->array->obj_size);
725 	 * Find the cached copy of a[lo] in the pivot array so that we can swap
794 		xfile_put_folio(si->array->xfile, si->folio);
799  * Cache the folio backing the start of the given array element.  If the array
810 	loff_t			idx_pos = xfarray_pos(si->array, idx);
823 	/* Grab the first folio that backs this array element. */
827 		si->folio = xfile_get_folio(si->array->xfile, idx_pos,
828 				si->array->obj_size, XFILE_ALLOC);
832 		si->first_folio_idx = xfarray_idx(si->array,
833 				folio_pos(si->folio) + si->array->obj_size - 1);
836 		si->last_folio_idx = xfarray_idx(si->array, next_pos - 1);
837 		if (xfarray_pos(si->array, si->last_folio_idx + 1) > next_pos)
848 		void		*temp = xfarray_scratch(si->array);
850 		error = xfile_load(si->array->xfile, temp, si->array->obj_size,
859 	/* Otherwise return a pointer to the array element in the folio. */
865  * Sort the array elements via quicksort.  This implementation incorporates
868  * 1. Use an explicit stack of array indices to store the next array partition
903 	struct xfarray		*array,
910 	void			*scratch = xfarray_scratch(array);
914 	if (array->nr < 2)
916 	if (array->nr >= QSORT_MAX_RECS)
919 	error = xfarray_sortinfo_alloc(array, cmp_fn, flags, &si);
988 				memcpy(scratch, p, si->array->obj_size);
1014 				memcpy(scratch, p, si->array->obj_size);