I need to do an oob vector load. How?

[brson]

As an optimization during a buffer search, I need (very want) to load that buffer into a SIMD vector, even when the buffer doesn't fit into the vector. E.g. I might have a 31-byte buffer that can be efficiently searched with a 32-byte wide AVX2 vector.

From a machine perspective, I don't see this as a problem, as long as the load doesn't extend beyond the current page; from LLVM's perspective this seems like UB.

I'd really like to be able to write this code in Rust and not have to use assembly.

Here's an example of this pattern:

    #[inline(always)]
    unsafe fn do_tail_clever(needle: u8, p: *const u8, len: isize,
                             i: isize, q: __m256i) -> Option<usize> {
        let rem = len - i;
        debug_assert!(rem < 32);

        // Check if the 32-byte load is within the current page
        let page_alignment = 4096;
        let page_mask = !(page_alignment - 1);
        let current_p = p.offset(i) as usize;
        let avx_read_end = current_p + 32;
        let next_page = (current_p & page_mask) + page_alignment;

        if likely(avx_read_end <= next_page) {
            let x = _mm256_loadu_si256(p.offset(i) as *const __m256i);
            let r = _mm256_cmpeq_epi8(x, q);
            let z = _mm256_movemask_epi8(r);
            let garbage_mask = {
                let ones = u32::max_value();
                let mask = ones << rem;
                let mask = !mask;
                mask as i32
            };
            let z = z & garbage_mask;
            if z != 0 {
                return off(i, z);
            }

            return None;
        }

        // Slow path
        do_tail_simple(needle, p, len, i, q)
    }

It loads beyond the array, does vector operations on it, then disregards the oob bytes with a mask.

I'm hopeful that there is some mechanism to tell LLVM to 'forget' what it knows about this pointer, 'fooling' the optimizer into not messing with it.

From the LLVM aliasing rules, there is some language that makes me hopeful:

An integer constant other than zero or a pointer value returned from a function not defined within LLVM may be associated with address ranges allocated through mechanisms other than those provided by LLVM. Such ranges shall not overlap with any ranges of addresses allocated by mechanisms provided by LLVM.

So there is a class of pointers that can operate on arbitrary memory (those that don't come from LLVM). That suggests to me that I could e.g. send my pointer through assembly or some other black-box function to 'clean it', maybe. On the other hand, calling into any function, or even into inline asm imposes extra instructions that more-or-less defeat the optimization (inline asm in LLVM seems to always spill registers). Though that sentence also says "such ranges shall not overlap with any ranges of addresses allocated by mechanisms provided by LLVM"

I'm not sure how much 'wiggle-room' there is. Is a malloc'd array "provided by LLVM"? What are the consequences of disobeying this "shall not"?

Even if there's no in-language solution and it is technically UB, I am hopeful that I can do this thing without LLVM messing with my codegen.

cc @nikomatsakis writing this here per your request.

[brson]

One thing I could do here is track the capacity of the original vector, and only do the oob load if there's enough capacity. That would definitely reduce how often this could hit the fast path, but not sure how much.

Edit: NVM, this routine never sees the Vec capacity - it operates only on slices.

[RalfJung]

A very related question has recently come up on stackoverflow. Someone has been suggesting to read a full u32 through a u8 pointer, making sure that never crosses page boundaries so there can't be a SEGFAULT.

As already discussed there, I think there are two related but distinct problems before we can even start taking Rust's own rules into account: You are potentially performing accesses outside of any allocation (as you already mentioned), and if not then you may be racing with other accesses to the bytes outside if your buffer.

For the out-of-bounds part, that is pretty much entirely in LLVM's hands. Rustc/MIR is not doing anything interesting there, but LLVM certainly does (for example, when you are accessing some pointer x + 3 and you have another pointer that LLVM knows points into an object of size <= 2, it will assume these accesses do not alias). You'd have to find a way to work around that, preferably something sanctioned by LLVM. That's probably something that would require discussion on the llvm-dev list. (I am sure the need for this comes up in C as well.)

For data races, Rust officially is using the C11 memory model. Read-write races are immediate UB under that model. So, if the extra byte you are accessing is actually allocated and currently accessed by some other thread, you would introduce UB. However, LLVM says that such read-write races yield undef/poison (effectively: uninitialized bytes) instead of raising UB. If Rust decided to switch from C11's model to LLVM's, that would enable your use-case if you carefully decorate everything with MaybeUninit to inform Rust that there may be uninitialized data around here.
The trouble is that C11's model is much better studied and much more clearly defined by now.

Only if we solve those two points, our own (Rust-level) aliasing rules even become relevant. I could imagine us following LLVM's lead and making "bad" loads return undef instead of raising UB.

[brson]

@RalfJung when you say "you may be racing with other accesses to the bytes outside if your buffer." What is the practical impact of that? In what concurrent/atomic scenario will my loads change the outcome for other thread? Eg making atomic values visible before they should be?

[RalfJung]

The practical impact is hard to determine. Compilers are allowed to and will perform optimizations that are only valid if non-atomic accesses never have a data race. Let me try to construct an example for how they might break when combining an otherwise correct unsafely implemented library with your code.

For example, in the following C code

int x = *x_ptr;
acquire_lock(l);
int y = *x_ptr;

gcc may and sometimes will replace the last line by int y = x;, which is correct because it knows there cannot be a concurrent write that could change the value behind x_ptr in the mean time. Now imagine a situation where a 32-byte (aligned) buffer (&mut [u8; 32]) is split into a 31-byte buffer (part1: &mut [u8; 31]) and a location (part2: &mut u8) that is put under the control of some unsafely implemented library lib. That library makes the location accessible from multiple threads and uses a lock stored somewhere else to synchronize (like a Mutex but with the data not stored in-band with the lock).

Now we have something like

let h = lib::put_under_library_control(part2);
something_that_uses_tail_clever(part1);
let val = h.get();

If everything gets inlined, this matches the C code above: tail_clever will read part2 but throw away the result, then h.get() will acquire a lock and read part2 again. The compiler may optimize this to use the result of the first read, assuming there are no data races -- and we got a miscompilation.

Now, this is clearly a very contrived example. But the point is, we cannot just ignore UB due to data races. The only thing we can do is pick different rules and make sure the compiler follows those rules -- LLVM will not perform the optimization outlined above precisely because under LLVM semantics, this read-write race is not UB.

---

Coming back to the higher level, I think this is an excellent example for why one may prefer the LLVM memory model over the C11 one. seqlocks are another example that causes trouble with the C11 memory model and AFAIK works fine with the LLVM model (though I have not seen an analysis of the latter).
There may be other arguments for the C11 model, e.g. I do not know the situation and DRF theorems (data-race-freedeom theorems) for the LLVM model. The C11 model has some pretty strong DRF theorems saying e.g. that a program that is race-free under sequential consistent semantics and only uses non-atomic and sequential consistent accesses, does not gain any additional behaviors when considering the full C11 semantics. These theorems ensure that programs not using the weaker access modes do not have to care. I haven't seen such theorems for the LLVM model, but that's just because I haven't seen that model studied very much at all.

[brson]

Thanks for the detail. I don't know if it helps anything but this particular code will never be inlined into any other code ("If everything gets inlined") because the caller is under my control and is inline (never).

…

On Sun, Jul 8, 2018, 12:49 PM Ralf Jung ***@***.***> wrote: The practical impact is hard to determine. Compilers are allowed to and will perform optimizations that are only valid if non-atomic accesses never have a data race. It is possible that none of these optimizations break your code, but that's the usual problem with undefined behavior -- just because the code isn't broken with one context now, doesn't mean it won't be broken with another context in the future. For example, in the following C code int x = *x_ptr;acquire_lock(l);int y = *x_ptr; gcc may and sometimes will replace the last line by int y = x;, which is correct because it knows there cannot be a concurrent write that could change the value behind x_ptr in the mean time. Now imagine a situation where a 32-byte (aligned) buffer (&mut [u8; 32]) is split into a 31-byte buffer (part1: &mut [u8; 31]) and a location (part2: &mut u8) that is put under the control of some unsafely implemented library lib. That library makes the location accessible from multiple threads and uses a lock stored somewhere else to synchronize (like a Mutex but with the data not stored in-band with the lock). Now we have something like let h = lib::put_under_library_control(part2);something_that_uses_tail_clever(part1);let val = h.get(); If everything gets inlined, this matches the C code above: tail_clever will read part2 but throw away the result, then h.get() will acquire a lock and read part2 again. The compiler may optimize this to use the result of the first read, assuming there are no data races -- and we got a miscompilation. Now, this is clearly a very contrived example. But the point is, we cannot just ignore UB due to data races. The only thing we can do is pick different rules and make sure the compiler follows those rules -- LLVM will not perform the optimization outlined above precises because under LLVM semantics, this read-write race is not UB. ------------------------------ Coming back to the higher level, I think this is an excellent example for why one may prefer the LLVM memory model over the C11 one. seqlocks <https://en.wikipedia.org/wiki/Seqlock> are another example that causes trouble with the C11 memory model <http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf> and AFAIK works fine with the LLVM model (though I have not seen an analysis of the latter). There may be other arguments for the C11 model, e.g. I do not know the situation and DRF theorems (data-race-freedeom theorems) for the LLVM model. The C11 model has some pretty strong DRF theorems saying e.g. that a program that is race-free under sequential consistent semantics and only uses non-atomic and sequential consistent accesses, does not gain any additional behaviors when considering the full C11 semantics. These theorems ensure that programs not using the weaker access modes do not have to care. I haven't seen such theorems for the LLVM model, but that's just because I haven't seen that model studied very much at all. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAI_DtJ4Cu8C7TnvpPgC91hcoosim_h1ks5uEmIugaJpZM4VEX04> .

[RalfJung]

Yeah, unfortunately these inlining hints don't actually change the program semantics -- they affect what the compiler will do, but not what it could do. From a correctness stand-point, I do not know of a way to make inlining hints "mean" anything.

[gnzlbg]

@Amanieu would like to be able to do oob atomic loads as well: rust-lang/rust#32976 (comment)

That's required for correctness, and is not an optimization AFAICT.

[Amanieu]

https://github.com/rust-lang-nursery/compiler-builtins/blob/master/src/arm_linux.rs#L58

[RalfJung]

@Amanieu what is that doing?

[Amanieu]

It is emulating 8/16/32 atomic operations on older ARM architectures (without atomic support) using a kernel-provided 32-bit cmpxchg function.

[RalfJung]

Does LLVM know that these are 32bit memory accesses? Code in other translation units, compiled from a different language with different UB (and linked on the assembly level, i.e., in a language where this is not UB), does not have to follow the same rules. Syscalls are an extreme case of "different translation unit".

Only LLVM IR itself is subject to LLVM IR's rules. (Of course there must be some amount of interop, and a shared memory model, but that seems plausible in this case.)

[gnzlbg]

Talking about doing SIMD loads OOBs:

if you carefully decorate everything with MaybeUninit to inform Rust that there may be uninitialized data around here.

@RalfJung that might be doable, but @brson would need to heavily re-write its code. Here:

let p: *const __m256i = /* ptr to allocation smaller than 32 bytes */;
let x: __m256i = _mm256_loadu_si256(p);

The problem is that core::arch::x86_64::_mm256_loadu_si256 returns an __m256i - not a MaybeUninit<__m256i> (which wouldn't help much), nor a Simd<[MaybeUninit<i64>; 4]>.

If packed_simd supported Simd<[MaybeUninit<i64>; 4]>, one could maybe write:

let p: *const Simd<[MaybeUninit<i64>; 4]> = /* ptr to allocation smaller than 32 bytes */;
let x: Simd<[MaybeUninit<i64>; 4]> = ptr.read_unaligned(p); 
// ^^ Is ptr::read_unaligned the right tool for reading memory OOB ?

where Simd<[MaybeUninit<i64>; 4]> would support the same API as Simd<[i64 ;4]> (comparisons, arithmetic, bit manipulation, reductions, etc.) but propagating undef.

---

Implementation wise, I don't really know how that would work. Adding the API to packed_simd is "trivial", but what LLVM-IR should it generate ? LLVM vectors are of type <N x T>, but I don't know whether we can put <4 x MaybeUninit_i64> there, and even if we could, whether LLVM could do something meaningful with it. Maybe an attribute <4 x maybe_undef i64> ?