nx_chain_selfref_adversary.nx source
↩ module page · 62 lines · 2465 B
1// nx_chain_selfref_adversary.nx -- T10 class: the SELF-REFERENTIAL chain-fusion
2// miscompile. A loop-carried alloca updated by `z = z OP (z OP' c)` (BOTH
3// operands read z) was chain-fused IN PLACE: the inner (z OP' c) mutated z's
4// home register, so the outer OP read the destroyed z. Symptom: `z = z & (z-1)`
5// (Brian Kernighan bit-clear) degraded to `z = z - 1` (decrement) -> popcount of
6// 0xFF returned 255 not 8 -> nx_hw_cpu_count popcounted a 16-bit CPU mask to 510
7// -> every auto-sized thread pool spawned 510 workers (32x oversubscription).
8// Fixed by the chain-scan guard: a chain step's src must not read the chained
9// alloca. This adversary is the regression witness; exit 0 == all correct.
10// license_tier: ORIGINAL No hw writes (Rule 26).
11import "nx_syscalls_x86_64.nx"
12const K_MAGIC_65535: i64 = 65535
13const K_MAGIC_1024: i64 = 1024
14
15// Brian Kernighan popcount -- the canonical x & (x-1) loop.
16func popcount(x: i64) -> i64 {
17 var z: i64 = x
18 var c: i64 = 0
19 while z != 0 { z = z & (z - 1); c = c + 1 }
20 return c
21}
22// operand-swapped form: (z-1) & z must be identical.
23func popcount_swapped(x: i64) -> i64 {
24 var z: i64 = x
25 var c: i64 = 0
26 while z != 0 { z = (z - 1) & z; c = c + 1 }
27 return c
28}
29// x ^ (x-1) isolates the lowest set bit + all below it; loop clears low run.
30// Here just verify ONE step is not degraded to a decrement.
31func xor_lowmask(x: i64) -> i64 {
32 var z: i64 = x
33 z = z ^ (z - 1)
34 return z
35}
36// z & (z+1): clears the trailing run of 1-bits. One step.
37func and_plus1(x: i64) -> i64 {
38 var z: i64 = x
39 z = z & (z + 1)
40 return z
41}
42
43func main() -> i64 {
44 // 0xFF has 8 bits -> Kernighan must iterate exactly 8 times.
45 if popcount(255) != 8 { return 1 }
46 if popcount_swapped(255) != 8 { return 2 }
47 // 0xFFFF (16 bits, the CPU-mask case that returned 510).
48 if popcount(K_MAGIC_65535) != 16 { return 3 }
49 if popcount_swapped(K_MAGIC_65535) != 16 { return 4 }
50 // 0 and 1 edge cases.
51 if popcount(0) != 0 { return 5 }
52 if popcount(1) != 1 { return 6 }
53 // power of two -> exactly 1 bit.
54 if popcount(K_MAGIC_1024) != 1 { return 7 }
55 // x ^ (x-1) for 0b1100 (12) = 12 ^ 11 = 0b0111 = 7 (NOT 12-1=11).
56 if xor_lowmask(12) != 7 { return 8 }
57 // x & (x+1) for 0b0111 (7) = 7 & 8 = 0 (NOT 7).
58 if and_plus1(7) != 0 { return 9 }
59 // x & (x+1) for 0b1011 (11) = 11 & 12 = 8 (NOT 11).
60 if and_plus1(11) != 8 { return 10 }
61 return 0
62}