Date: Thu, 23 Jul 2015 11:10:30 -0700
From: =?iso-8859-1?Q?J=F6rn?= Engel <joern@purestorage.com>
To: linux-kernel@vger.kernel.org, Yinghai Lu <yinghai@kernel.org>,
        Alexey Dobriyan <adobriyan@gmail.com>
Cc: Spencer Baugh <spencer.baugh@purestorage.com>
Subject: Re: round_up integer underflow
Message-ID: <20150723181030.GC24876@Sligo.logfs.org>
References: <20150723180255.GA24876@Sligo.logfs.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <20150723180255.GA24876@Sligo.logfs.org>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2248
Lines: 61

On Thu, Jul 23, 2015 at 11:02:55AM -0700, J?rn Engel wrote:
> Spencer spotted something nasty in the round_up macro.  We were
> wondering why round_up() worked differently from ALIGN.  The only real
> difference between the two patterns is overflow behaviour.  And both
> version are buggy when used for signed integer types, round_up will
> underflow on INT_MIN, ALIGN will overflow on INT_MAX.  Since signed
> integer under/overflows are undefined, we might have subtle bugs lurking
> in the kernel.
> 
> This example program produces a warning when compiling with gcc -O2 or
> higher.  Clang doesn't warn.  Compiled code behaves correctly with both
> compilers, but that is largely luck and the same compilers may create
> wrong behaviour if the surrounding code changes.
> 
> #include <limits.h>
> #include <stdio.h>
> 
> #define __round_mask(x, y) ((__typeof__(x))((y)-1))
> #define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
> #define round_down(x, y) ((x) & ~__round_mask(x, y))
> 
> int main(void)
> {
> 	int i, r = 8;
> 
> 	for (i = INT_MIN; i; i++) {
> 		printf("%2x: %2x %2x\n", i, round_down(i, r), round_up(i, r));
> 	}
> 	return 0;
> }
> 
> I don't have a good answer yet.  We could make round_up check for
> negative numbers, but I would prefer unconditional code that optimizes
> down to nothing.  We could rewrite it in assembly, once for each
> architecture.
> 
> Does anyone have better ideas?

Btw, it would be awesome if something like the following would work in
gcc:
#define __round_mask(x, y) ((__typeof__(x))((y)-1))
#define __round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
#define round_down(x, y) ((x) & ~__round_mask(x, y))
#define round_up(x, y) (__typeof__(x)(__round_up((unsigned __typeof__(x)(x)), (y))))

I.e. cast x to the matching unsigned type where overflows are
well-defined, do the rounding, then cast the result back to the original
type.

J?rn

--
Rules of Optimization:
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet.
-- M.A. Jackson
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/