Valgrind gives tons of errors
thomwiggers opened this issue · 3 comments
I'm running Valgrind on the latest version of the codebase (AVX2 version), and getting tons of errors like the following:
==22435== Conditional jump or move depends on uninitialised value(s)
==22435== at 0x109BA0: pqcrystals_kyber512_avx2_gen_matrix (indcpa.c:253)
==22435== by 0x109EC3: pqcrystals_kyber512_avx2_indcpa_enc (indcpa.c:581)
==22435== by 0x10930E: pqcrystals_kyber512_avx2_enc (kem.c:69)
==22435== by 0x1D9602: test_keys (test_kyber.c:23)
==22435== by 0x1D98A1: main (test_kyber.c:98)
==22435== Uninitialised value was created by a stack allocation
==22435== at 0x10976C: pqcrystals_kyber512_avx2_gen_matrix (indcpa.c:210)
...
==23591== Use of uninitialised value of size 8
==23591== at 0x110093: _mm_storeu_si128 (emmintrin.h:727)
==23591== by 0x110093: pqcrystals_kyber512_avx2_rej_uniform_avx (rejsample.c:351)
==23591== by 0x109A3A: pqcrystals_kyber512_avx2_gen_matrix (indcpa.c:251)
==23591== by 0x109CC0: pqcrystals_kyber512_avx2_indcpa_keypair (indcpa.c:497)
==23591== by 0x1091D9: pqcrystals_kyber512_avx2_keypair (kem.c:26)
==23591== by 0x1D95E5: test_keys (test_kyber.c:20)
==23591== by 0x1D98A1: main (test_kyber.c:98)
==23591==
All errors go away by exchanging _mm256_xor_si256(s,s) by _mm256_setzero_si256() in fips202x4.c, see commit 8440574. I'm surprised valgrind doesn't understand this standard pattern.
Interesting. That should be reported upstream.
Hrm, I'm having a ton of trouble reproducing this in smaller examples. I wonder if there's some undefined behavior showing up again, as, of course, it's still technically reading an uninitialized value.
e.g. https://godbolt.org/z/463sPc reduces all of these to vpxor xmm0, xmm0 xmm0
The disassembly of keccak_absorb
(objdump) shows:
...
aca6: 48 c7 44 24 40 00 00 movq $0x0,0x40(%rsp)
acad: 00 00
acaf: eb 76 jmp ad27 <keccakx4_absorb+0xbd>
acb1: 48 8b 44 24 40 mov 0x40(%rsp),%rax
acb6: 48 c1 e0 05 shl $0x5,%rax
acba: 48 89 c2 mov %rax,%rdx
acbd: 48 8b 44 24 38 mov 0x38(%rsp),%rax
acc2: 48 01 d0 add %rdx,%rax
acc5: c5 fd 6f 00 vmovdqa (%rax),%ymm0
acc9: 48 8b 44 24 40 mov 0x40(%rsp),%rax
acce: 48 c1 e0 05 shl $0x5,%rax
acd2: 48 89 c2 mov %rax,%rdx
acd5: 48 8b 44 24 38 mov 0x38(%rsp),%rax
acda: 48 01 d0 add %rdx,%rax
acdd: c5 fd 6f 08 vmovdqa (%rax),%ymm1
ace1: 48 8b 44 24 40 mov 0x40(%rsp),%rax
ace6: 48 c1 e0 05 shl $0x5,%rax
acea: 48 89 c2 mov %rax,%rdx
aced: 48 8b 44 24 38 mov 0x38(%rsp),%rax
acf2: 48 01 d0 add %rdx,%rax
acf5: c5 fd 7f 8c 24 e0 00 vmovdqa %ymm1,0xe0(%rsp)
acfc: 00 00
acfe: c5 fd 7f 84 24 00 01 vmovdqa %ymm0,0x100(%rsp)
ad05: 00 00
ad07: c5 fd 6f 8c 24 e0 00 vmovdqa 0xe0(%rsp),%ymm1
ad0e: 00 00
ad10: c5 fd 6f 84 24 00 01 vmovdqa 0x100(%rsp),%ymm0
ad17: 00 00
ad19: c5 f5 ef c0 vpxor %ymm0,%ymm1,%ymm0
ad1d: 90 nop
ad1e: c5 fd 7f 00 vmovdqa %ymm0,(%rax)
ad22: 48 ff 44 24 40 incq 0x40(%rsp)
ad27: 48 83 7c 24 40 18 cmpq $0x18,0x40(%rsp)
ad2d: 76 82 jbe acb1 <keccakx4_absorb+0x47>
...
which does look like a whole bunch of loads and stores are happening that are not strictly necessary and maybe coming from werid places. Switching compiler flags from -O0
(included in your fix for #21) to -O2
also patches this problem: the loop gets unrolled to vpxor %xmm0, %xmm0, %xmm0
and a bunch of stores.
Perhaps valgrind is just setting more memory as "uninitialised", and as it compiles the xor
using two separate registers (ymm1
and ymm0
) it doesn't keep track anymore that the values located there are the same.
The loop looks like this with __m256_setzero_si256()
:
...
acb1: 48 8b 44 24 40 mov 0x40(%rsp),%rax
acb6: 48 c1 e0 05 shl $0x5,%rax
acba: 48 89 c2 mov %rax,%rdx
acbd: 48 8b 44 24 38 mov 0x38(%rsp),%rax
acc2: 48 01 d0 add %rdx,%rax
acc5: c5 f9 ef c0 vpxor %xmm0,%xmm0,%xmm0
acc9: c5 fd 7f 00 vmovdqa %ymm0,(%rax)
accd: 48 ff 44 24 40 incq 0x40(%rsp)
acd2: 48 83 7c 24 40 18 cmpq $0x18,0x40(%rsp)
acd8: 76 d7 jbe acb1 <keccakx4_absorb+0x47>
...
Not sure if it's worth reporting this to Valgrind; semantically, setzero
is more clear anyway.