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?
J?rn
--
People really ought to be forced to read their code aloud over the phone.
That would rapidly improve the choice of identifiers.
-- Al Viro
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
On Thu, Jul 23, 2015 at 11:10:30AM -0700, J?rn Engel wrote:
> 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?
You can fix overflow issues but the ALIGN(INT_MAX, a) creating much
smaller value is probably a bug anyway. It should BUG_ON or something
(yes, I'm aware of recent memo).
> #define round_up(x, y) (__typeof__(x)(__round_up((unsigned __typeof__(x)(x)), (y))))
^^^^^^^^^^^^^^^^^^^
If only... :-(
> 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.