From owner-freebsd-arch@freebsd.org Sat Feb 13 16:56:31 2016 Return-Path: Delivered-To: freebsd-arch@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 5C7E6AA676E for ; Sat, 13 Feb 2016 16:56:31 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mailman.ysv.freebsd.org (mailman.ysv.freebsd.org [IPv6:2001:1900:2254:206a::50:5]) by mx1.freebsd.org (Postfix) with ESMTP id 4254D109F for ; Sat, 13 Feb 2016 16:56:31 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: by mailman.ysv.freebsd.org (Postfix) id 40163AA676D; Sat, 13 Feb 2016 16:56:31 +0000 (UTC) Delivered-To: arch@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 24ECCAA676C for ; Sat, 13 Feb 2016 16:56:31 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail104.syd.optusnet.com.au (mail104.syd.optusnet.com.au [211.29.132.246]) by mx1.freebsd.org (Postfix) with ESMTP id A7282109D for ; Sat, 13 Feb 2016 16:56:30 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from c110-21-41-193.carlnfd1.nsw.optusnet.com.au (c110-21-41-193.carlnfd1.nsw.optusnet.com.au [110.21.41.193]) by mail104.syd.optusnet.com.au (Postfix) with ESMTPS id 8A348426EB7; Sun, 14 Feb 2016 03:56:21 +1100 (AEDT) Date: Sun, 14 Feb 2016 03:56:20 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Ed Schouten cc: C Turt , arch@freebsd.org Subject: Re: OpenBSD mallocarray In-Reply-To: Message-ID: <20160214025715.A918@besplex.bde.org> References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Optus-CM-Score: 0 X-Optus-CM-Analysis: v=2.1 cv=cK4dyQqN c=1 sm=1 tr=0 a=73JWPhLeruqQCjN69UNZtQ==:117 a=L9H7d07YOLsA:10 a=9cW_t1CCXrUA:10 a=s5jvgZ67dGcA:10 a=kj9zAlcOel0A:10 a=ypVJL4-jAAAA:8 a=8YkvNc5hkbnPY-hunSYA:9 a=U5Y3M-fodkWOT-C-:21 a=05EgSaJtlaSRRacC:21 a=CjuIK1q_8ugA:10 X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 13 Feb 2016 16:56:31 -0000 On Sat, 13 Feb 2016, Ed Schouten wrote: > 2016-02-01 20:57 GMT+01:00 C Turt : >> 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