Revision acbbe6fbb240a927ee1f5994f04d31267d422215 authored by Rasmus Villemoes on 09 September 2014, 21:51:01 UTC, committed by Linus Torvalds on 10 September 2014, 22:42:12 UTC
The C operator <= defines a perfectly fine total ordering on the set of values representable in a long. However, unlike its namesake in the integers, it is not translation invariant, meaning that we do not have "b <= c" iff "a+b <= a+c" for all a,b,c. This means that it is always wrong to try to boil down the relationship between two longs to a question about the sign of their difference, because the resulting relation [a LEQ b iff a-b <= 0] is neither anti-symmetric or transitive. The former is due to -LONG_MIN==LONG_MIN (take any two a,b with a-b = LONG_MIN; then a LEQ b and b LEQ a, but a != b). The latter can either be seen observing that x LEQ x+1 for all x, implying x LEQ x+1 LEQ x+2 ... LEQ x-1 LEQ x; or more directly with the simple example a=LONG_MIN, b=0, c=1, for which a-b < 0, b-c < 0, but a-c > 0. Note that it makes absolutely no difference that a transmogrying bijection has been applied before the comparison is done. In fact, had the obfuscation not been done, one could probably not observe the bug (assuming all values being compared always lie in one half of the address space, the mathematical value of a-b is always representable in a long). As it stands, one can easily obtain three file descriptors exhibiting the non-transitivity of kcmp(). Side note 1: I can't see that ensuring the MSB of the multiplier is set serves any purpose other than obfuscating the obfuscating code. Side note 2: #include <stdio.h> #include <stdlib.h> #include <string.h> #include <fcntl.h> #include <unistd.h> #include <assert.h> #include <sys/syscall.h> enum kcmp_type { KCMP_FILE, KCMP_VM, KCMP_FILES, KCMP_FS, KCMP_SIGHAND, KCMP_IO, KCMP_SYSVSEM, KCMP_TYPES, }; pid_t pid; int kcmp(pid_t pid1, pid_t pid2, int type, unsigned long idx1, unsigned long idx2) { return syscall(SYS_kcmp, pid1, pid2, type, idx1, idx2); } int cmp_fd(int fd1, int fd2) { int c = kcmp(pid, pid, KCMP_FILE, fd1, fd2); if (c < 0) { perror("kcmp"); exit(1); } assert(0 <= c && c < 3); return c; } int cmp_fdp(const void *a, const void *b) { static const int normalize[] = {0, -1, 1}; return normalize[cmp_fd(*(int*)a, *(int*)b)]; } #define MAX 100 /* This is plenty; I've seen it trigger for MAX==3 */ int main(int argc, char *argv[]) { int r, s, count = 0; int REL[3] = {0,0,0}; int fd[MAX]; pid = getpid(); while (count < MAX) { r = open("/dev/null", O_RDONLY); if (r < 0) break; fd[count++] = r; } printf("opened %d file descriptors\n", count); for (r = 0; r < count; ++r) { for (s = r+1; s < count; ++s) { REL[cmp_fd(fd[r], fd[s])]++; } } printf("== %d\t< %d\t> %d\n", REL[0], REL[1], REL[2]); qsort(fd, count, sizeof(fd[0]), cmp_fdp); memset(REL, 0, sizeof(REL)); for (r = 0; r < count; ++r) { for (s = r+1; s < count; ++s) { REL[cmp_fd(fd[r], fd[s])]++; } } printf("== %d\t< %d\t> %d\n", REL[0], REL[1], REL[2]); return (REL[0] + REL[2] != 0); } Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Reviewed-by: Cyrill Gorcunov <gorcunov@openvz.org> "Eric W. Biederman" <ebiederm@xmission.com> Cc: <stable@vger.kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
1 parent 8542bdf
Kconfig.kgdb
config HAVE_ARCH_KGDB
bool
menuconfig KGDB
bool "KGDB: kernel debugger"
depends on HAVE_ARCH_KGDB
depends on DEBUG_KERNEL
help
If you say Y here, it will be possible to remotely debug the
kernel using gdb. It is recommended but not required, that
you also turn on the kernel config option
CONFIG_FRAME_POINTER to aid in producing more reliable stack
backtraces in the external debugger. Documentation of
kernel debugger is available at http://kgdb.sourceforge.net
as well as in DocBook form in Documentation/DocBook/. If
unsure, say N.
if KGDB
config KGDB_SERIAL_CONSOLE
tristate "KGDB: use kgdb over the serial console"
select CONSOLE_POLL
select MAGIC_SYSRQ
depends on TTY
default y
help
Share a serial console with kgdb. Sysrq-g must be used
to break in initially.
config KGDB_TESTS
bool "KGDB: internal test suite"
default n
help
This is a kgdb I/O module specifically designed to test
kgdb's internal functions. This kgdb I/O module is
intended to for the development of new kgdb stubs
as well as regression testing the kgdb internals.
See the drivers/misc/kgdbts.c for the details about
the tests. The most basic of this I/O module is to boot
a kernel boot arguments "kgdbwait kgdbts=V1F100"
config KGDB_TESTS_ON_BOOT
bool "KGDB: Run tests on boot"
depends on KGDB_TESTS
default n
help
Run the kgdb tests on boot up automatically without the need
to pass in a kernel parameter
config KGDB_TESTS_BOOT_STRING
string "KGDB: which internal kgdb tests to run"
depends on KGDB_TESTS_ON_BOOT
default "V1F100"
help
This is the command string to send the kgdb test suite on
boot. See the drivers/misc/kgdbts.c for detailed
information about other strings you could use beyond the
default of V1F100.
config KGDB_LOW_LEVEL_TRAP
bool "KGDB: Allow debugging with traps in notifiers"
depends on X86 || MIPS
default n
help
This will add an extra call back to kgdb for the breakpoint
exception handler which will allow kgdb to step through a
notify handler.
config KGDB_KDB
bool "KGDB_KDB: include kdb frontend for kgdb"
default n
help
KDB frontend for kernel
config KDB_KEYBOARD
bool "KGDB_KDB: keyboard as input device"
depends on VT && KGDB_KDB
default n
help
KDB can use a PS/2 type keyboard for an input device
config KDB_CONTINUE_CATASTROPHIC
int "KDB: continue after catastrophic errors"
depends on KGDB_KDB
default "0"
help
This integer controls the behaviour of kdb when the kernel gets a
catastrophic error, i.e. for a panic or oops.
When KDB is active and a catastrophic error occurs, nothing extra
will happen until you type 'go'.
CONFIG_KDB_CONTINUE_CATASTROPHIC == 0 (default). The first time
you type 'go', you will be warned by kdb. The secend time you type
'go', KDB tries to continue. No guarantees that the
kernel is still usable in this situation.
CONFIG_KDB_CONTINUE_CATASTROPHIC == 1. KDB tries to continue.
No guarantees that the kernel is still usable in this situation.
CONFIG_KDB_CONTINUE_CATASTROPHIC == 2. KDB forces a reboot.
If you are not sure, say 0.
endif # KGDB
Computing file changes ...