Re: [PATCH 14/14] xfarray: warn against sorting arrays with identical elements

["Darrick J. Wong" <djwong@kernel.org>]

On Sun, Sep 20, 2026 at 11:18:38PM -0700, Darrick J. Wong wrote:
> From: Darrick J. Wong <djwong@kernel.org>
> 
> LOLLM complains about a potential underflow here if xfarray_qsort_push
> is called with lo==0.  However, this isn't possible in most cases
> because filesystem metadata records cannot be identical.
> 
> Signed-off-by: "Darrick J. Wong" <djwong@kernel.org>
> Assisted-by: LOLLM # finding obvious bugs
> ---
>  fs/xfs/scrub/xfarray.c |   12 ++++++++++++
>  1 file changed, 12 insertions(+)
> 
> 
> diff --git a/fs/xfs/scrub/xfarray.c b/fs/xfs/scrub/xfarray.c
> index 78274ad53097e1..ab15a73b7d3b10 100644
> --- a/fs/xfs/scrub/xfarray.c
> +++ b/fs/xfs/scrub/xfarray.c
> @@ -693,6 +693,18 @@ xfarray_qsort_push(
>  		return -EFSCORRUPTED;
>  	}
>  
> +	/*
> +	 * Avoid the integer underflow below in (lo - 1).  This shouldn't
> +	 * be possible because the pivot is the median of nine distinct
> +	 * filesystem metadata records, so at least four records will be less
> +	 * than the pivot, which means the pivot will not be in the low end of
> +	 * the range by the time we get here.
> +	 */
> +	if (lo == 0) {
> +		ASSERT(lo != 0);
> +		return -EFSCORRUPTED;
> +	}

Shashiko has a big long comment:

"Can this assertion be triggered if a corrupted filesystem actually contains
identical elements, causing a denial of service?
Looking at the partition loop in xfarray_sort(), it uses a >= 0 check:
fs/xfs/scrub/xfarray.c:xfarray_sort() {
    ...
			while (xfarray_sort_cmp(si, p, pivot) >= 0 && lo < hi) {
				hi--;
    ...
}
If the array contains duplicate elements, the comparison returns 0, and hi is
decremented down to lo. Then xfarray_qsort_push() is called with the
unmodified lo.
If lo is 0, won't this trigger the new assertion and crash the kernel?
Furthermore, if lo > 0, does this cause linear stack growth and another crash?
Because hi was decremented down to lo, the left partition size calculation
underflows:
fs/xfs/scrub/xfarray.c:xfarray_qsort_push() {
    ...
	si_hi[si->stack_depth++] = lo - 1;
	/*
	 * Always start with the smaller of the two partitions to keep the
	 * amount of recursion in check.
	 */
	if (si_hi[si->stack_depth]     - si_lo[si->stack_depth] >
	    si_hi[si->stack_depth - 1] - si_lo[si->stack_depth - 1]) {
    ...
}
The left partition size calculated via (lo - 1) - lo underflows to a very
large unsigned value, bypassing the size optimization.
Will the algorithm then process the N-1 right partition first, pushing empty
left partitions to the stack until it hits max_stack_depth and fails via
the stack overflow assertion?
fs/xfs/scrub/xfarray.c:xfarray_qsort_push() {
	/* Check for stack overflows */
	if (si->stack_depth >= si->max_stack_depth - 1) {
		ASSERT(si->stack_depth < si->max_stack_depth - 1);
		return -EFSCORRUPTED;
	}
}"

To which I say that xfs isn't supposed to store duplicate elements in a
metadata structure, so repair code should never create duplicate
elements in a staging array.  We're not going to exhaustively verify
that for every repair since most repair code is structured so that it
can't create duplicate elements, but we can at least bail out when we
detect the obvious signs of this.

--D

> +
>  	si->max_stack_used = max_t(uint8_t, si->max_stack_used,
>  					    si->stack_depth + 2);
>  
> 
>