Date: Sun, 14 Feb 2016 03:56:20 +1100 (EST) From: Bruce Evans <brde@optusnet.com.au> To: Ed Schouten <ed@nuxi.nl> Cc: C Turt <cturt@hardenedbsd.org>, arch@freebsd.org Subject: Re: OpenBSD mallocarray Message-ID: <20160214025715.A918@besplex.bde.org> In-Reply-To: <CABh_MKmtC0OPPkNU0ho2UZsnVrbRO1w6vHjidYhKqgu123PVCg@mail.gmail.com> References: <CAB815ZafpqJoqr1oH8mDJM=0RxLptQJpoJLexw6P6zOi7oSXTQ@mail.gmail.com> <CABh_MKmtC0OPPkNU0ho2UZsnVrbRO1w6vHjidYhKqgu123PVCg@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, 13 Feb 2016, Ed Schouten wrote:
> 2016-02-01 20:57 GMT+01:00 C Turt <cturt@hardenedbsd.org>:
>> if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
>> nmemb > 0 && SIZE_MAX / nmemb < size) {
>
> In my opinion functions like these are good additions, as long as we
> make sure that we stop importing garbage expressions like the one
> above. It's already bad enough that we copy-pasted this gobbledygook
> into fread(), fwrite(), calloc(), reallocarray(), etc.
This is a normal well written C expression. It uses a possibly-
excessive micro-optimization to avoid a possibly-slow division. It
is less general then my macro:
#define MALLOC_ARRAY_CHECK(num, size, limit) \
((size) == 0 || limit / (size) >= (num))
My macro shouldn't have MALLOC in its name, since its only relation to
malloc() is that it may be used for bounds checking related to using
malloc().
> Both the latest versions of Clang and GCC support the following builtins:
>
> bool __builtin_add_overflow(type1 a, type2 b, type3 *res);
> bool __builtin_sub_overflow(type1 a, type2 b, type3 *res);
> bool __builtin_mul_overflow(type1 a, type2 b, type3 *res);
>
> These functions perform addition, subtraction and multiplication,
> returning whether overflow has occurred in the process. This is a lot
> more efficient (and readable) than the expression above, as it simply
> uses the CPU's mul instruction, followed by a jump-on-overflow.
Using these functions is gives undefined behaviour. They are in the
implementation namespace and are not documented in any installed
documentation for clang (maybe in info for gcc?). This is a slightly
less efficient and slightly less readable than the first expression
above if the implementation is as you describe. The micro-optimization
in the first expression does work and results in no division in most
cases. It usually takes 2 comparisons and 2 branches instead of 1
multiplication, 1 comparison and 1 branch. The extra comparison is
probably faster than the multiplication unless multiplication takes
only 1 cycle. The compiler might actually actually convert each version
to the other if the version with the multiplication is faster. Or
better, to the in-between version with 2 comparisons and the division
reduced to multiplications.
My macro is more general than this. It allows an arbitrary limit, but
the builtins only check for the overflow threshold. Checks for malloc()
in the kernel always need to use a limit much smaller than the overflow
threshold.
The version in fread.c actually has a further micro-optimizations which
you don't like and style bugs which I don't like:
X /*
X * Check for integer overflow. As an optimization, first check that
X * at least one of {count, size} is at least 2^16, since if both
X * values are less than that, their product can't possible overflow
X * (size_t is always at least 32 bits on FreeBSD).
X */
X if (((count | size) > 0xFFFF) &&
X (count > SIZE_MAX / size)) {
(size != 0 has already been checked for.)
This manually reduces the 2 comparisons and 2 branches to 1 OR, 1 comparison
and 1 branch. Well, I don't like this either. The compiler can do this
strength reduction much more easily than the mul/div ones if it (either
the optimization or the compiler) is any good. It micro-optimization gives
one of the style bugs (a verbose comment to explain it, and duplicating this
comment. The other style bugs are excessive parentheses and unnecessary
line splitting.
Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20160214025715.A918>