bug in roundup(3) from <sys/param.h>

bug in roundup(3) from <sys/param.h>

[Alejandro Colomar]

[-- Attachment #1.1: Type: text/plain, Size: 4194 bytes --]

Hi!

I was trying to understand what roundup() is (defined in <sys/param,h>).

It seems to be kind of:

SYNOPSIS
        #include <sys/param.h>

        roundup(x, step);

DESCRIPTION
        This  macro  rounds  x to the nearest multiple of step that is not less
        than x.

I found that it doesn't work for negative numbers; but that's expected, and it 
could be documented as such.  However, it doesn't work nicely with unsigned 
integers either: for values close to zero, where wrap around happens, the result 
is also bogus.  See my experiments below.



$ sed -n 92,98p /usr/include/x86_64-linux-gnu/sys/param.h
#ifdef __GNUC__
# define roundup(x, y)  (__builtin_constant_p (y) && powerof2 (y)             \
                          ? (((x) + (y) - 1) & ~((y) - 1))                     \
                          : ((((x) + ((y) - 1)) / (y)) * (y)))
#else
# define roundup(x, y)  ((((x) + ((y) - 1)) / (y)) * (y))
#endif


$ cat roundup.c
#include <stdint.h>
#include <stdio.h>
#include <sys/param.h>

int
main(void)
{
	/* signed */
	{
		int32_t n, m;

		m = 3;
		n = 10;

		puts("signed:");
		for (int32_t x = -n; x < 0; x++)
			printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));

		puts("");
		for (int32_t x = 0; x < n; x++)
			printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));

		puts("");

		for (int32_t x = INT32_MIN; x < INT_MIN + n; x++)
			printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));

		puts("");
		for (int32_t x = INT32_MAX; x > INT32_MAX - n; x--)
			printf("roundup(%d, %d) == %d\n", x, m, roundup(x, m));
	}

	/* unsigned */
	{
		uint32_t n, m;

		m = 3;
		n = 10;

		puts("\nunsigned:");
		for (uint32_t x = 1; x < n; x++)
			printf("roundup(%u, %u) == %u\n", -x, m, roundup(-x, m));

		puts("");
		for (uint32_t x = 0; x < n; x++)
			printf("roundup(%u, %u) == %u\n", x, m, roundup(x, m));
	}
}

$ cc -Wall -Wextra -Werror roundup.c
$ ./a.out
signed:
roundup(-10, 3) == -6
roundup(-9, 3) == -6
roundup(-8, 3) == -6
roundup(-7, 3) == -3
roundup(-6, 3) == -3
roundup(-5, 3) == -3
roundup(-4, 3) == 0
roundup(-3, 3) == 0
roundup(-2, 3) == 0
roundup(-1, 3) == 0
/* These values are nonsense, but OK, let's ignore the negative */

roundup(0, 3) == 0
roundup(1, 3) == 3
roundup(2, 3) == 3
roundup(3, 3) == 3
roundup(4, 3) == 6
roundup(5, 3) == 6
roundup(6, 3) == 6
roundup(7, 3) == 9
roundup(8, 3) == 9
roundup(9, 3) == 9
/* These make sense */

roundup(-2147483648, 3) == -2147483646
roundup(-2147483647, 3) == -2147483643
roundup(-2147483646, 3) == -2147483643
roundup(-2147483645, 3) == -2147483643
roundup(-2147483644, 3) == -2147483640
roundup(-2147483643, 3) == -2147483640
roundup(-2147483642, 3) == -2147483640
roundup(-2147483641, 3) == -2147483637
roundup(-2147483640, 3) == -2147483637
roundup(-2147483639, 3) == -2147483637
/* Nonsense; ignore the negative */

roundup(2147483647, 3) == -2147483646  // UB; ignore
roundup(2147483646, 3) == -2147483646  // UB; ignore
roundup(2147483645, 3) == 2147483646
roundup(2147483644, 3) == 2147483646
roundup(2147483643, 3) == 2147483643
roundup(2147483642, 3) == 2147483643
roundup(2147483641, 3) == 2147483643
roundup(2147483640, 3) == 2147483640
roundup(2147483639, 3) == 2147483640
roundup(2147483638, 3) == 2147483640
/* These make sense */

unsigned:
roundup(4294967295, 3) == 0  // Wrong; should be: 4294967295
roundup(4294967294, 3) == 0  // Wrong; should be: 4294967295
roundup(4294967293, 3) == 4294967295
roundup(4294967292, 3) == 4294967292
roundup(4294967291, 3) == 4294967292
roundup(4294967290, 3) == 4294967292
roundup(4294967289, 3) == 4294967289
roundup(4294967288, 3) == 4294967289
roundup(4294967287, 3) == 4294967289

roundup(0, 3) == 0
roundup(1, 3) == 3
roundup(2, 3) == 3
roundup(3, 3) == 3
roundup(4, 3) == 6
roundup(5, 3) == 6
roundup(6, 3) == 6
roundup(7, 3) == 9
roundup(8, 3) == 9
roundup(9, 3) == 9


Do you think this is something to be fixed without important performance 
penalties, or should we just document the bug and live with it?


Cheers,

Alex



-- 
<http://www.alejandro-colomar.es/>

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: bug in roundup(3) from <sys/param.h>

[Alejandro Colomar]

[-- Attachment #1.1: Type: text/plain, Size: 3521 bytes --]

On 1/16/23 21:46, Alejandro Colomar wrote:
> Hi!
> 
> I was trying to understand what roundup() is (defined in <sys/param,h>).
> 
> It seems to be kind of:
> 
> SYNOPSIS
>         #include <sys/param.h>
> 
>         roundup(x, step);
> 
> DESCRIPTION
>         This  macro  rounds  x to the nearest multiple of step that is not less
>         than x.
> 
> I found that it doesn't work for negative numbers; but that's expected, and it 
> could be documented as such.  However, it doesn't work nicely with unsigned 
> integers either: for values close to zero, where wrap around happens, the result 
> is also bogus.  See my experiments below.
> 
> 
> 
> $ sed -n 92,98p /usr/include/x86_64-linux-gnu/sys/param.h
> #ifdef __GNUC__
> # define roundup(x, y)  (__builtin_constant_p (y) && powerof2 (y)             \
>                           ? (((x) + (y) - 1) & ~((y) - 1))                     \
>                           : ((((x) + ((y) - 1)) / (y)) * (y)))
> #else
> # define roundup(x, y)  ((((x) + ((y) - 1)) / (y)) * (y))
> #endif
> 

I came up with this implementation, which increases complexity quite a lot 
(compared to the one liner), but makes the macro work correctly for all input 
(or that's what my tests showed).  It only has UB for signed input when the 
output would overflow <TYPE>_MAX (but of course, there's no way to avoid that).

Apart from working will all input, signed or unsigned, until the end of the 
range, it also has no problems about double evaluation.

If using GCC extensions is a problem, this could be rewritten a bit less safely 
and more standardese.


#define alx_widthof(t)    (sizeof(t) * CHAR_BIT)

#define alx_is_signed(x)  (((typeof(x)) -1) < 0)

#define alx_stype_max(t)  (((((t) 1 << (alx_widthof(t) - 2)) - 1) << 1) + 1)

#define alx_roundup(x, step)                                                  \
({                                                                            \
	__auto_type  x_    = (x);                                             \
	__auto_type  step_ = (step);                                          \
                                                                               \
	if (alx_is_signed(x_)) {                                              \
		if (x_ < 0) {                                                 \
			x_ = x_ / step_ * step_;                              \
		} else if (x_ - 1 > alx_stype_max(typeof(x_)) - step_) {      \
			x_ = ((x_ - 1) / step_ + 1) * step_;                  \
		} else {                                                      \
			x_ = ((x_ - 1 + step_) / step_) * step_;              \
		}                                                             \
	} else {                                                              \
		if (x_ + step_ < step_) {                                     \
			x_ = ((x_ - 1) / step_ + 1) * step_;                  \
		} else {                                                      \
			x_ = ((x_ - 1 + step_) / step_) * step_;              \
		}                                                             \
	}                                                                     \
                                                                               \
	x_;                                                                   \
})


-- 
<http://www.alejandro-colomar.es/>

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: bug in roundup(3) from <sys/param.h>

[Adhemerval Zanella Netto]

On 16/01/23 17:46, Alejandro Colomar via Libc-alpha wrote:
> Hi!

> 
> Do you think this is something to be fixed without important performance penalties, or should we just document the bug and live with it?

That's the problem with ill-defined interfaces, each implementation might 
eventually differs.  It seems that BSD, AIX, and Solaris follows glibc 
implementation by wrapping around (Solaris also provides it through 
sysmacros.h instead of param.h).  The exception is macOS that saturates 
the value.

I really won't bother with this interface, since potentially changing it
might generate more potentially breakage than improvements.

bug in roundup(3) from <sys/param.h>

[Wilco Dijkstra]

Hi,

> I really won't bother with this interface, since potentially changing it
> might generate more potentially breakage than improvements.

The typical use-case is rounding up a pointer to align it or increasing a buffer
to be allocated. There is no chance of overflow in these cases since you will
never have pointers that close to SIZE_MAX or get buffers close to the maximum
memory size. And adding saturation would mean we didn't do what was requested
either...

So it seems best to state it only works on unsigned values (with y > 0 since division
by zero is undefined behaviour of course) and it's implementation defined whether
overflow wraps or saturates.

Cheers,
Wilco

Re: bug in roundup(3) from <sys/param.h>

[Alejandro Colomar]

[-- Attachment #1.1: Type: text/plain, Size: 935 bytes --]

Hi Wilco and Adhemerval!

On 1/17/23 20:16, Wilco Dijkstra wrote:
> Hi,
> 
>> I really won't bother with this interface, since potentially changing it
>> might generate more potentially breakage than improvements.
> 
> The typical use-case is rounding up a pointer to align it or increasing a buffer
> to be allocated. There is no chance of overflow in these cases since you will
> never have pointers that close to SIZE_MAX or get buffers close to the maximum
> memory size. And adding saturation would mean we didn't do what was requested
> either...
> 
> So it seems best to state it only works on unsigned values (with y > 0 since division
> by zero is undefined behaviour of course) and it's implementation defined whether
> overflow wraps or saturates.
> 

Thanks! That clarifies what this macro is for.  I'll document that.

Cheers,

Alex

> Cheers,
> Wilco

-- 
<http://www.alejandro-colomar.es/>

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: bug in roundup(3) from <sys/param.h>

[Paul Eggert]

On 1/17/23 11:16, Wilco Dijkstra via Libc-alpha wrote:
> So it seems best to state it only works on unsigned values (with y > 0 since division
> by zero is undefined behaviour of course) and it's implementation defined whether
> overflow wraps or saturates.

roundup works just fine on signed integers. Although x should be 
nonnegative and y should be positive, there's no requirement that either 
x or y must be unsigned.

This sort of thing matters in the C style I prefer nowadays, which is to 
use types like ptrdiff_t and idx_t instead of size_t, so that I can 
optionally enable runtime overflow checking that works.

Re: bug in roundup(3) from <sys/param.h>

[Alejandro Colomar]

[-- Attachment #1.1: Type: text/plain, Size: 961 bytes --]

Hi Paul!

On 1/17/23 21:11, Paul Eggert wrote:
> On 1/17/23 11:16, Wilco Dijkstra via Libc-alpha wrote:
>> So it seems best to state it only works on unsigned values (with y > 0 since 
>> division
>> by zero is undefined behaviour of course) and it's implementation defined whether
>> overflow wraps or saturates.
> 
> roundup works just fine on signed integers. Although x should be nonnegative and 
> y should be positive, there's no requirement that either x or y must be unsigned.
> 
> This sort of thing matters in the C style I prefer nowadays, which is to use 
> types like ptrdiff_t and idx_t instead of size_t, so that I can optionally 
> enable runtime overflow checking that works.

That's fair; I'll clarify, and anyway, will post the manual page for review 
before pushing.

If you happen to know od any other use cases for this function, it might be 
interesting.

Cheers,

Alex

-- 
<http://www.alejandro-colomar.es/>

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]