Received-SPF: pass (google.com: domain of linux-kernel+bounces-182773-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99;
Date: Sat, 18 May 2024 06:11:26 +0100
From: Matthew Wilcox <willy@infradead.org>
To: Kees Cook <keescook@chromium.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>,
	Justin Stitt <justinstitt@google.com>,
	Peter Zijlstra <peterz@infradead.org>,
	Mark Rutland <mark.rutland@arm.com>,
	linux-hardening@vger.kernel.org, linux-kernel@vger.kernel.org,
	llvm@lists.linux.dev
Subject: Re: [RFC] Mitigating unexpected arithmetic overflow
Message-ID: <Zkg4fl1t6sKGPSb6@casper.infradead.org>
References: <202404291502.612E0A10@keescook>
 <CAHk-=wi5YPwWA8f5RAf_Hi8iL0NhGJeL6MN6UFWwRMY8L6UDvQ@mail.gmail.com>
 <202405081144.D5FCC44A@keescook>
 <CAHk-=wjeiGb1UxCy6Q8aif50C=wWDX9Pgp+WbZYrO72+B1f_QA@mail.gmail.com>
 <202405081354.B0A8194B3C@keescook>
 <CAHk-=wgoE5EkH+sQwi4KhRhCZizUxwZAnC=+9RbZcw7g6016LQ@mail.gmail.com>
 <202405081949.0565810E46@keescook>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <202405081949.0565810E46@keescook>

On Wed, May 08, 2024 at 11:11:35PM -0700, Kees Cook wrote:
> 	Or even just simple math between u8s:
> 
> 	while (xas->xa_offset == 255) {
> 		xas->xa_offset = xas->xa_node->offset - 1;
> 
> 	Is it expecting to wrap (truncate)? How is it distinguished from
> 	the "num_elems++" case?

Hi ;-)

This looks to me like it's walking up the tree, looking to go to the
'prev' element.  So yes, the wrapping from 0 to 255 is intentional,
because once we find an offset that's not 0, we've set offset to the
right one.  Just to give more context, here's the few lines around it:

        if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
                xas->xa_offset--;

        while (xas->xa_offset == 255) {
                xas->xa_offset = xas->xa_node->offset - 1;
                xas->xa_node = xa_parent(xas->xa, xas->xa_node);
                if (!xas->xa_node)
                        return set_bounds(xas);
        }

So it's kind of nasty.  I don't want to write it as:

	while (xas->xa_offset == 0) {
		xas->xa_offset = xas->xa_node->offset;
		xas->xa_node = xa_parent(xas->xa, xas->xa_node);
	}
	xas->xa_offset--;

because there's that conditional subtraction before the loop starts.
The xarray test-suite is pretty good if anyone thinks they have a clearer
way to write this loop ...