round_up integer underflow
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
Quoted 30 lines · Jörn Engel
Spencer spotted something nasty in the
round_upmacro. We were wondering whyround_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_upwill underflow onINT_MIN, ALIGN will overflow onINT_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)) #defineround_up(x, y)((((x)-1) |__round_mask(x, y))+1) #defineround_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; }
Quoted 6 lines
I don't have a good answer yet. We could make
round_upcheck 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
Quoted 31 lines · Jörn Engel
Quoted 30 lines · Jörn Engel
Spencer spotted something nasty in the
round_upmacro. We were wondering whyround_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_upwill underflow onINT_MIN, ALIGN will overflow onINT_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)) #defineround_up(x, y)((((x)-1) |__round_mask(x, y))+1) #defineround_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; }
Quoted 6 lines
Quoted 6 lines
I don't have a good answer yet. We could make
round_upcheck 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).
Quoted 1 line
#define
round_up(x, y)(__typeof__(x)(__round_up((unsigned __typeof__(x)(x)), (y))))
^^^^^^^^^^^^^^^^^^^
If only... :-(
Quoted 3 lines
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.