Skip to contentSkip to conversation

round_up integer underflow

DISCUSSION Jörn Engel 2 participants 3 messages Jul 23, 2015

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
Quoted 30 lines · Jörn Engel

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;
}
Quoted 6 lines

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

#2 lore raw
Quoted 31 lines · Jörn Engel
Quoted 30 lines · Jörn Engel

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;
}
Quoted 6 lines
Quoted 6 lines

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).

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.