I need to do an oob vector load. How?

@nikomatsakis

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.

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.

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.

@RalfJung

@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?

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.

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> .

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.

@Amanieu

@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.

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

@Amanieu

@Amanieu what is that doing?

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

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.)

@RalfJung

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> ?

@gnzlbg

@gnzlbg Notice that this only "solves" the data-race part. One alternative (not correct in theory but experimentally confirmed to work in practice) is to use volatile reads for the non-atomic maybe-racy reads. LLVM didn't sanction this, and maybe we should have a discussion with them about this. Another alternative might be to use LLVM monotone accesses, not sure if anybody experimented with them in Rust yet.

None of this helps with the fact that the accesses are OOB. There is no solution to that other than having explicit support for this from LLVM.

Briefly discussed in backlog bonanza: This is still open. Rust does not support it today, but it seems plausible to have in the language at some point

We actually now have an intrinsic that can do something like this: simd_maksed_load. However, you need to produce a mask that indicates which parts of the vector are in-bounds and which are not.

@nikic

This pattern also again came up here, and here.

@nikic as far as I can tell, this is currently blocked on finding some way for LLVM to generate the desired code. There's a very clear idea of what the assembly code is that we want, but apparently no good way to get LLVM to generate that code without UB. Do you have any thoughts on what a realistic way forward may look like here? Some sort of flag on load operations with the meaning of "make the OOB parts poison; it is UB only if they end up causing a trap"?

@RalfJung

@RalfJung I think a flag on load operations is unlikely -- it would have to be an actual flag, not metadata, and that will take significant effort to preserve through the compiler.

It should be pretty easy to provide an intrinsic for this though. I'd like to double check I understand the requirements here:

If the load actually traps, that's undefined behavior, we're not required to preserve the trap, right? So the loads may be DCEd.
The load is still provenance aware, right? That is, any bytes that are outside the underlying allocated object are undef. Two consecutive loads without changes in between may return different results for the out-of-bounds bytes. This means this is suitable for implementing a memcpy, but not a memcmp. (I think it would be very hard to support without this limitation -- the AA implications of a providing a pure physical load would be terrible.)
What kind of loads do we need? Just plain loads? Volatile loads? Atomic loads? If it's just plain (and volatile if necessary) that's okay, but atomic loads would be a substantial complication.

If the load actually traps, that's undefined behavior, we're not required to preserve the trap, right? So the loads may be DCEd.

Yes.

The load is still provenance aware, right? That is, any bytes that are outside the underlying allocated object are undef. Two consecutive loads without changes in between may return different results for the out-of-bounds bytes. This means this is suitable for implementing a memcpy, but not a memcmp. (I think it would be very hard to support without this limitation -- the AA implications of a providing a pure physical load would be terrible.)

Yes. This is actually tricky to define from an aliasing model perspective -- if we have two noalias pointers that are 4 bytes apart from each other, and we do such an OOB load of size 8 through one of them with the intent of only loading 4 bytes and ignoring the remaining bytes, we don't want this to be an aliasing conflict.

So I think we need the intrinsic to take the "size of the logical read" as a parameter, on top of the size of the physical read. In the AM, the load acts like a normal load on the logical size, with the full consequences for provenance and aliasing model. The part between the logical and physical size will always be uninit/undef/poison, the AM entirely ignores it except that it is UB if this part traps. (In Miri we'll have to figure out some fun way to define whether there can be a trap here.)

What kind of loads do we need? Just plain loads? Volatile loads? Atomic loads? If it's just plain (and volatile if necessary) that's okay, but atomic loads would be a substantial complication.

For now this has only come up with plain loads, but it definitely seems possible that this would come up with atomic loads.

Volatile loads arguably already allow this since they are basically inline assembly.

For atomic loads can the load be split into two operations with respect to the opsem? One half for what Ralf calls the "logical read". This half follows the regular memory ordering rules for the specified ordering of the atomic load. And one half for the rest of the load which acts effectively as a regular load and thus returns uninit/undef/poison in case of a race with a write on this half. And afterwards both halves are combined into a single return value for the atomic load as a whole.

Draft RFC for LLVM: https://hackmd.io/@nikic/S1O4QWYZkx Let me know if this makes sense. Also, does anyone has a good idea for the intrinsic name?

@nikic

@nikic Could this be generalized to handle OOB bytes at the start of a slice? This would be useful for memcpy implementations like the one in compiler-builtins.

Thanks for writing this up!

Making the remaining bytes undef means Rust will have to immediately generate a mask, since our integers cannot be undef... but I guess that's not too bad.

What is the reason why doing this for atomics is tricky? Is it just "there are so many variants of them", or something deeper?

Making the remaining bytes undef means Rust will have to immediately generate a mask, since our integers cannot be undef... but I guess that's not too bad.

Would it work if I said they're freeze poison instead? (In the sense that the bytes are fixed once loaded, but can differ on each load.)

What is the reason why doing this for atomics is tricky? Is it just "there are so many variants of them", or something deeper?

The former.

Could this be generalized to handle OOB bytes at the start of a slice? This would be useful for memcpy implementations like the one in compiler-builtins.

We could replace %defined_size with %defined_offset plus %defined_size, making this intrinsic even uglier :(

I'm really unhappy about this parameter. It is a spec-only construct that gets completely ignored by the implementation.

Would it work if I said they're freeze poison instead? (In the sense that the bytes are fixed once loaded, but can differ on each load.)

If LLVM can guarantee that, sure. But Rust might still want to apply a mask until we have officially decided that exposing the contents of uninit memory to sound programs is something we want to do.

I'm really unhappy about this parameter. It is a spec-only construct that gets completely ignored by the implementation.

Well, in a sense so is freeze...

Wouldn't alias analysis look at this parameter to determine whether such an access aliases with something else?

Well, in a sense so is freeze...

Not really. Freeze doesn't generate code, but it does affect analysis and transforms a lot. Here we'd have a parameter that is completely ignored, at all levels.

Wouldn't alias analysis look at this parameter to determine whether such an access aliases with something else?

It could use it if defined_size is a constant, but if it were a constant you wouldn't be using this intrinsic in the first place. For AA purposes, we'd just model this as "accesses at most sizeof(T) bytes" (LocationSize::upperBound).

If LLVM can deduce information about defined_size, AA could use that. Not sure how realistic that is, but a lot can happen after inlining.

Another place where the defined_size parameter would actually be used is by optimizations that replace such a load with a constant, if they can pair it up with a preceding store.

Would it be worth filing an LLVM issue to track this on their side as well?

Navigation Menu

Repository navigation

I need to do an oob vector load. How? #2

43 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

I need to do an oob vector load. How? #2

Description

Activity

brson commented on Jul 5, 2018

RalfJung commented on Jul 8, 2018

brson commented on Jul 8, 2018

RalfJung commented on Jul 8, 2018

brson commented on Jul 8, 2018

RalfJung commented on Jul 9, 2018

gnzlbg commented on Nov 27, 2018

Amanieu commented on Nov 27, 2018

RalfJung commented on Nov 27, 2018

Amanieu commented on Nov 27, 2018

RalfJung commented on Nov 27, 2018

gnzlbg commented on Dec 13, 2018

RalfJung commented on Dec 13, 2018

43 remaining items

JakobDegen commented on May 23, 2023

RalfJung commented on Apr 5, 2024

RalfJung commented on Nov 6, 2024

nikic commented on Nov 6, 2024

RalfJung commented on Nov 6, 2024

bjorn3 commented on Nov 6, 2024

nikic commented on Nov 6, 2024

Amanieu commented on Nov 6, 2024

RalfJung commented on Nov 7, 2024

nikic commented on Nov 10, 2024

RalfJung commented on Nov 10, 2024

nikic commented on Nov 10, 2024

RalfJung commented on Nov 10, 2024

RalfJung commented on Mar 19, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions