linux-kernel - round_up integer underflow

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <20150723180255.GA24876@Sligo.logfs.org>
Date:	Thu, 23 Jul 2015 11:02:55 -0700
From:	Jörn Engel <joern@...estorage.com>
To:	linux-kernel@...r.kernel.org, Yinghai Lu <yinghai@...nel.org>,
	Alexey Dobriyan <adobriyan@...il.com>
Cc:	Spencer Baugh <spencer.baugh@...estorage.com>
Subject: 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/