Valgrind gives false positives for valid SIMD Zig code; language specification implications

[andrewrk]

Extracted from #17209.

I don't really know how to solve this problem, but at least here is a tracking issue for it.

const std = @import("std");

pub fn main() !void {
    var buf: [100]u8 = undefined;
    buf[0..6].* = "hello\x00".*;
    const slice = std.mem.sliceTo(&buf, 0);
    _ = slice;
}

$ stage3/bin/zig build-exe test.zig  
$ valgrind ./test
==86463== Memcheck, a memory error detector
==86463== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==86463== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info
==86463== Command: ./test
==86463== 
==86463== Conditional jump or move depends on uninitialised value(s)
==86463==    at 0x24647E: mem.indexOfScalarPos__anon_7038 (mem.zig:1145)
==86463==    by 0x22173F: mem.indexOfScalar__anon_4185 (mem.zig:1104)
==86463==    by 0x21FD9E: mem.lenSliceTo__anon_3509 (mem.zig:868)
==86463==    by 0x21D9A4: mem.sliceTo__anon_3331 (mem.zig:807)
==86463==    by 0x21D977: test.main (test.zig:7)
==86463==    by 0x21D8B7: callMain (start.zig:583)
==86463==    by 0x21D8B7: initEventLoopAndCallMain (start.zig:517)
==86463==    by 0x21D8B7: callMainWithArgs (start.zig:467)
==86463==    by 0x21D8B7: start.posixCallMainAndExit (start.zig:423)
==86463==    by 0x21D3E1: (below main) (start.zig:251)
==86463== 
==86463== Conditional jump or move depends on uninitialised value(s)
==86463==    at 0x21D9C5: mem.sliceTo__anon_3331 (mem.zig:813)
==86463==    by 0x21D977: test.main (test.zig:7)
==86463==    by 0x21D8B7: callMain (start.zig:583)
==86463==    by 0x21D8B7: initEventLoopAndCallMain (start.zig:517)
==86463==    by 0x21D8B7: callMainWithArgs (start.zig:467)
==86463==    by 0x21D8B7: start.posixCallMainAndExit (start.zig:423)
==86463==    by 0x21D3E1: (below main) (start.zig:251)
==86463== 
==86463== Conditional jump or move depends on uninitialised value(s)
==86463==    at 0x21D9D1: mem.sliceTo__anon_3331 (mem.zig:813)
==86463==    by 0x21D977: test.main (test.zig:7)
==86463==    by 0x21D8B7: callMain (start.zig:583)
==86463==    by 0x21D8B7: initEventLoopAndCallMain (start.zig:517)
==86463==    by 0x21D8B7: callMainWithArgs (start.zig:467)
==86463==    by 0x21D8B7: start.posixCallMainAndExit (start.zig:423)
==86463==    by 0x21D3E1: (below main) (start.zig:251)
==86463== 
==86463== Conditional jump or move depends on uninitialised value(s)
==86463==    at 0x21D9ED: mem.sliceTo__anon_3331 (mem.zig:813)
==86463==    by 0x21D977: test.main (test.zig:7)
==86463==    by 0x21D8B7: callMain (start.zig:583)
==86463==    by 0x21D8B7: initEventLoopAndCallMain (start.zig:517)
==86463==    by 0x21D8B7: callMainWithArgs (start.zig:467)
==86463==    by 0x21D8B7: start.posixCallMainAndExit (start.zig:423)
==86463==    by 0x21D3E1: (below main) (start.zig:251)
==86463== 
==86463== 
==86463== HEAP SUMMARY:
==86463==     in use at exit: 0 bytes in 0 blocks
==86463==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==86463== 
==86463== All heap blocks were freed -- no leaks are possible
==86463== 
==86463== Use --track-origins=yes to see where uninitialised values come from
==86463== For lists of detected and suppressed errors, rerun with: -s
==86463== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)

The problem is that, while the first 6 bytes of the buffer are well-defined, including the null byte, the bytes after it are undefined.

For a naive loop, no loads of undefined bytes will occur:

    for (slice[i..], i..) |c, j| {
        if (c == value) return j;
    }

However, the Zig standard library is now taking advantage of SIMD:

https://github.com/ziglang/zig/blob/cc394431ae6eb69e7abd677c268a8ab7299f8aeb/lib/std/mem.zig#L1144-L1145

Technically this is indeed doing a memory load of some undefined bytes. However, since it's returning the index of the first null byte, it has no dependency on the undefined memory.

Maybe we can work with the Valgrind project to resolve this? Maybe there is already some client request mechanism so that we could communicate this pattern to Valgrind?

This also impacts the Zig language specification. It needs to be well-defined to do a SIMD operation on an undefined value as long as a conditional branch has no dependency on the undefined value.

For example, @reduce(.Or, v)) should produce a well-defined value if any of the elements of the vector are true.

However, making firstTrue sound is slightly more tricky:

https://github.com/ziglang/zig/blob/cc394431ae6eb69e7abd677c268a8ab7299f8aeb/lib/std/simd.zig#L291-L301

In theory, it should be fine, since the result does not actually depend on any elements past the first true element. Whether subsequent undefined elements are treated as true or false does not matter, since a well-defined true value will be the smallest index.

However, that only works if @select(T, v, a, b) produces a well-defined value for every element of its result. For scalar operations in Zig, this is not the case - an operation with undefined operators propagates undefined to the result. However, in this case, it could result in the following scenario:

1. vec contains .{false, true, undefined}.
2. @select() produces .{maxint, 1, undefined}
3. @reduce() receives 0 as the value for the undefined element, causing it to result in 0 instead of the correct result which is 1.

Perhaps @select could be defined to treat any undefined elements in the predicate as resulting in either the corresponding a element, or the corresponding b element, rather than undefined.

This maps to the concept of freeze in LLVM IR.

[ghost]

In theory, it should be fine, since the result does not actually depend on any elements past the first true element. Whether subsequent undefined elements are treated as true or false does not matter, since a well-defined true value will be the smallest index.

Excuse me if I'm missing something, but could it cause an exception if the well defined bytes are at the end of the memory page but the "undefined" bytes accessed by SIMD instruction are out of the page? If that are the scenarios which are detected by Valgrind, then that's why that detection exists? The question is maybe how then to cover the cases "we're sure the access is safe even with undefined content"?

[drfuchs]

With regard to ghost's point that the undefined bytes might be in a separate memory page: That page may not exist, and thus the SIMD instruction will cause a SIGSEGV or whatever. For instance, in NeXTSTEP, if the defined bytes are from the default allocator, the subsequent bytes may well be at an address that isn't mapped in at all. (Learned this the hard way, with a read-immediately-after-free bug that SEGV'd when NeXTSTEP unmapped the page that had just become completely free.)

[andrewrk]

Note that the std.mem code in question does not cross a page boundary.