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
File | Mode | Size |
---|---|---|
fonts | ||
lz4 | ||
lzo | ||
mpi | ||
raid6 | ||
reed_solomon | ||
xz | ||
zlib_deflate | ||
zlib_inflate | ||
.gitignore | -rw-r--r-- | 70 bytes |
Kconfig | -rw-r--r-- | 11.6 KB |
Kconfig.debug | -rw-r--r-- | 57.3 KB |
Kconfig.kgdb | -rw-r--r-- | 3.1 KB |
Kconfig.kmemcheck | -rw-r--r-- | 2.9 KB |
Makefile | -rw-r--r-- | 6.0 KB |
argv_split.c | -rw-r--r-- | 2.1 KB |
asn1_decoder.c | -rw-r--r-- | 12.4 KB |
assoc_array.c | -rw-r--r-- | 52.5 KB |
atomic64.c | -rw-r--r-- | 4.2 KB |
atomic64_test.c | -rw-r--r-- | 3.4 KB |
audit.c | -rw-r--r-- | 1.7 KB |
average.c | -rw-r--r-- | 1.9 KB |
bcd.c | -rw-r--r-- | 261 bytes |
bch.c | -rw-r--r-- | 35.6 KB |
bitmap.c | -rw-r--r-- | 35.1 KB |
bitrev.c | -rw-r--r-- | 2.1 KB |
bsearch.c | -rw-r--r-- | 1.6 KB |
btree.c | -rw-r--r-- | 19.3 KB |
bug.c | -rw-r--r-- | 4.7 KB |
build_OID_registry | -rwxr-xr-x | 4.7 KB |
bust_spinlocks.c | -rw-r--r-- | 660 bytes |
check_signature.c | -rw-r--r-- | 599 bytes |
checksum.c | -rw-r--r-- | 4.9 KB |
clz_ctz.c | -rw-r--r-- | 1.3 KB |
clz_tab.c | -rw-r--r-- | 855 bytes |
cmdline.c | -rw-r--r-- | 3.5 KB |
compat_audit.c | -rw-r--r-- | 796 bytes |
cordic.c | -rw-r--r-- | 2.5 KB |
cpu-notifier-error-inject.c | -rw-r--r-- | 1.2 KB |
cpu_rmap.c | -rw-r--r-- | 7.8 KB |
cpumask.c | -rw-r--r-- | 5.8 KB |
crc-ccitt.c | -rw-r--r-- | 3.0 KB |
crc-itu-t.c | -rw-r--r-- | 2.8 KB |
crc-t10dif.c | -rw-r--r-- | 1.5 KB |
crc16.c | -rw-r--r-- | 2.8 KB |
crc32.c | -rw-r--r-- | 45.4 KB |
crc32defs.h | -rw-r--r-- | 2.0 KB |
crc7.c | -rw-r--r-- | 2.6 KB |
crc8.c | -rw-r--r-- | 2.4 KB |
ctype.c | -rw-r--r-- | 1.4 KB |
debug_locks.c | -rw-r--r-- | 1.2 KB |
debugobjects.c | -rw-r--r-- | 26.1 KB |
dec_and_lock.c | -rw-r--r-- | 784 bytes |
decompress.c | -rw-r--r-- | 1.6 KB |
decompress_bunzip2.c | -rw-r--r-- | 23.4 KB |
decompress_inflate.c | -rw-r--r-- | 3.8 KB |
decompress_unlz4.c | -rw-r--r-- | 4.1 KB |
decompress_unlzma.c | -rw-r--r-- | 15.8 KB |
decompress_unlzo.c | -rw-r--r-- | 6.8 KB |
decompress_unxz.c | -rw-r--r-- | 10.6 KB |
devres.c | -rw-r--r-- | 9.4 KB |
digsig.c | -rw-r--r-- | 5.5 KB |
div64.c | -rw-r--r-- | 4.0 KB |
dma-debug.c | -rw-r--r-- | 41.4 KB |
dump_stack.c | -rw-r--r-- | 1.1 KB |
dynamic_debug.c | -rw-r--r-- | 25.5 KB |
dynamic_queue_limits.c | -rw-r--r-- | 4.3 KB |
earlycpio.c | -rw-r--r-- | 3.9 KB |
extable.c | -rw-r--r-- | 2.4 KB |
fault-inject.c | -rw-r--r-- | 5.5 KB |
fdt.c | -rw-r--r-- | 69 bytes |
fdt_empty_tree.c | -rw-r--r-- | 80 bytes |
fdt_ro.c | -rw-r--r-- | 72 bytes |
fdt_rw.c | -rw-r--r-- | 72 bytes |
fdt_strerror.c | -rw-r--r-- | 78 bytes |
fdt_sw.c | -rw-r--r-- | 72 bytes |
fdt_wip.c | -rw-r--r-- | 73 bytes |
find_last_bit.c | -rw-r--r-- | 1.1 KB |
find_next_bit.c | -rw-r--r-- | 6.4 KB |
flex_array.c | -rw-r--r-- | 11.0 KB |
flex_proportions.c | -rw-r--r-- | 6.8 KB |
gcd.c | -rw-r--r-- | 313 bytes |
gen_crc32table.c | -rw-r--r-- | 3.2 KB |
genalloc.c | -rw-r--r-- | 16.3 KB |
glob.c | -rw-r--r-- | 7.7 KB |
halfmd4.c | -rw-r--r-- | 2.0 KB |
hash.c | -rw-r--r-- | 1.0 KB |
hexdump.c | -rw-r--r-- | 7.2 KB |
hweight.c | -rw-r--r-- | 1.9 KB |
idr.c | -rw-r--r-- | 28.0 KB |
inflate.c | -rw-r--r-- | 38.6 KB |
int_sqrt.c | -rw-r--r-- | 652 bytes |
interval_tree.c | -rw-r--r-- | 495 bytes |
interval_tree_test.c | -rw-r--r-- | 2.3 KB |
iomap.c | -rw-r--r-- | 6.5 KB |
iomap_copy.c | -rw-r--r-- | 2.1 KB |
iommu-helper.c | -rw-r--r-- | 1.0 KB |
ioremap.c | -rw-r--r-- | 2.1 KB |
iovec.c | -rw-r--r-- | 2.2 KB |
irq_regs.c | -rw-r--r-- | 604 bytes |
is_single_threaded.c | -rw-r--r-- | 1.3 KB |
jedec_ddr_data.c | -rw-r--r-- | 3.0 KB |
kasprintf.c | -rw-r--r-- | 717 bytes |
kfifo.c | -rw-r--r-- | 12.7 KB |
klist.c | -rw-r--r-- | 9.3 KB |
kobject.c | -rw-r--r-- | 25.5 KB |
kobject_uevent.c | -rw-r--r-- | 11.4 KB |
kstrtox.c | -rw-r--r-- | 9.4 KB |
kstrtox.h | -rw-r--r-- | 254 bytes |
lcm.c | -rw-r--r-- | 288 bytes |
libcrc32c.c | -rw-r--r-- | 2.1 KB |
list_debug.c | -rw-r--r-- | 2.6 KB |
list_sort.c | -rw-r--r-- | 6.7 KB |
llist.c | -rw-r--r-- | 3.1 KB |
locking-selftest-hardirq.h | -rw-r--r-- | 207 bytes |
locking-selftest-mutex.h | -rw-r--r-- | 120 bytes |
locking-selftest-rlock-hardirq.h | -rw-r--r-- | 74 bytes |
locking-selftest-rlock-softirq.h | -rw-r--r-- | 74 bytes |
locking-selftest-rlock.h | -rw-r--r-- | 158 bytes |
locking-selftest-rsem.h | -rw-r--r-- | 163 bytes |
locking-selftest-softirq.h | -rw-r--r-- | 207 bytes |
locking-selftest-spin-hardirq.h | -rw-r--r-- | 73 bytes |
locking-selftest-spin-softirq.h | -rw-r--r-- | 73 bytes |
locking-selftest-spin.h | -rw-r--r-- | 118 bytes |
locking-selftest-wlock-hardirq.h | -rw-r--r-- | 74 bytes |
locking-selftest-wlock-softirq.h | -rw-r--r-- | 74 bytes |
locking-selftest-wlock.h | -rw-r--r-- | 158 bytes |
locking-selftest-wsem.h | -rw-r--r-- | 163 bytes |
locking-selftest.c | -rw-r--r-- | 40.1 KB |
lockref.c | -rw-r--r-- | 3.6 KB |
lru_cache.c | -rw-r--r-- | 19.4 KB |
md5.c | -rw-r--r-- | 3.7 KB |
memory-notifier-error-inject.c | -rw-r--r-- | 1.1 KB |
memweight.c | -rw-r--r-- | 999 bytes |
net_utils.c | -rw-r--r-- | 604 bytes |
nlattr.c | -rw-r--r-- | 12.5 KB |
notifier-error-inject.c | -rw-r--r-- | 2.7 KB |
notifier-error-inject.h | -rw-r--r-- | 614 bytes |
of-reconfig-notifier-error-inject.c | -rw-r--r-- | 1.3 KB |
oid_registry.c | -rw-r--r-- | 3.8 KB |
parser.c | -rw-r--r-- | 7.1 KB |
pci_iomap.c | -rw-r--r-- | 1.4 KB |
percpu-refcount.c | -rw-r--r-- | 6.3 KB |
percpu_counter.c | -rw-r--r-- | 5.3 KB |
percpu_ida.c | -rw-r--r-- | 9.6 KB |
percpu_test.c | -rw-r--r-- | 3.2 KB |
plist.c | -rw-r--r-- | 5.9 KB |
pm-notifier-error-inject.c | -rw-r--r-- | 1.1 KB |
prio_heap.c | -rw-r--r-- | 1.4 KB |
proportions.c | -rw-r--r-- | 9.3 KB |
radix-tree.c | -rw-r--r-- | 39.3 KB |
random32.c | -rw-r--r-- | 12.6 KB |
ratelimit.c | -rw-r--r-- | 1.5 KB |
rational.c | -rw-r--r-- | 1.5 KB |
rbtree.c | -rw-r--r-- | 15.0 KB |
rbtree_test.c | -rw-r--r-- | 5.5 KB |
reciprocal_div.c | -rw-r--r-- | 492 bytes |
rhashtable.c | -rw-r--r-- | 20.1 KB |
scatterlist.c | -rw-r--r-- | 18.2 KB |
sha1.c | -rw-r--r-- | 6.1 KB |
show_mem.c | -rw-r--r-- | 1.2 KB |
smp_processor_id.c | -rw-r--r-- | 1.3 KB |
sort.c | -rw-r--r-- | 2.5 KB |
stmp_device.c | -rw-r--r-- | 2.1 KB |
string.c | -rw-r--r-- | 16.6 KB |
string_helpers.c | -rw-r--r-- | 3.6 KB |
strncpy_from_user.c | -rw-r--r-- | 2.9 KB |
strnlen_user.c | -rw-r--r-- | 3.6 KB |
swiotlb.c | -rw-r--r-- | 27.1 KB |
syscall.c | -rw-r--r-- | 2.4 KB |
test-kstrtox.c | -rw-r--r-- | 17.4 KB |
test-string_helpers.c | -rw-r--r-- | 2.5 KB |
test_bpf.c | -rw-r--r-- | 53.9 KB |
test_firmware.c | -rw-r--r-- | 2.8 KB |
test_module.c | -rw-r--r-- | 753 bytes |
test_user_copy.c | -rw-r--r-- | 3.1 KB |
textsearch.c | -rw-r--r-- | 9.6 KB |
timerqueue.c | -rw-r--r-- | 3.1 KB |
ts_bm.c | -rw-r--r-- | 5.3 KB |
ts_fsm.c | -rw-r--r-- | 10.6 KB |
ts_kmp.c | -rw-r--r-- | 4.3 KB |
ucs2_string.c | -rw-r--r-- | 1.2 KB |
usercopy.c | -rw-r--r-- | 197 bytes |
uuid.c | -rw-r--r-- | 1.3 KB |
vsprintf.c | -rw-r--r-- | 58.4 KB |
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...