Stream: t-lang/wg-unsafe-code-guidelines

Topic: no item granting read acces to tag


Yogurt (Mar 02 2020 at 19:11, on Zulip):

Hey All,

I'm writing some code which requires the use of unsafe and I'm trying to wrap my head around the miri error no item granting read access to tag What I'm doing is creating an array of 32bit ints and then getting a u8 pointer to that same array. The issue I'm hitting is that I create the array and pointer as

    let mut state: [u32; 12] = [0; 12];
    let state_8 = unsafe {
        std::slice::from_raw_parts_mut(
            state.as_mut_ptr() as *mut u8,
            48)
    };

Then go into a loop of the form

while input_byte_len > 0 {
        block_size = min(input_byte_len, 16);
        for i in 0..block_size {
            let b = input.next().unwrap().expect("Read error on input");
            state_8[i as usize] ^= b;
        }
        ...
    }

The line that gets flagged is state_8[i as usize] ^= b;. I've tried to make a minimal example of this which can be seen here
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=589490937b36480799043d790f5d0d4e
but it passes cargo miri test without issue. Also, I've tried moving the pointer creation into the loop and that seems to resolve the issue.
ex.

while input_byte_len > 0 {
        block_size = min(input_byte_len, 16);
        for i in 0..block_size {
        let state_8 = unsafe {std::slice::from_raw_parts_mut(state.as_mut_ptr() as *mut u8,48)};
            let b = input.next().unwrap().expect("Read error on input");
            state_8[i as usize] ^= b;
        }
        ...
    }

I'm not really sure where to go from here and could really use some guidance. For context my full set of code with branch adding a miri CI check can be found here
https://github.com/darakian/gimli/tree/add-miri-ci

The full cli output of the miri error is

error[E0080]: Miri evaluation error: no item granting read access to tag <87365> found in borrow stack
   --> src/lib.rs:70:13
    |
70  |             state_8[i as usize] ^= b;
    |             ^^^^^^^^^^^^^^^^^^^^^^^^ Miri evaluation error: no item granting read access to tag <87365> found in borrow stack
    |
Jake Goulding (Mar 02 2020 at 19:55, on Zulip):

Are you sure your version of Miri matches the one in the playground?

Jake Goulding (Mar 02 2020 at 19:56, on Zulip):

And have you seen https://doc.rust-lang.org/std/primitive.slice.html#method.align_to_mut ?

Jake Goulding (Mar 02 2020 at 20:01, on Zulip):

Your playground has

let mut block_size: usize = 0;

for i in 0..block_size { /* ... */ }

The loop will never run.

Jake Goulding (Mar 02 2020 at 20:03, on Zulip):

Oh, that's being strangely mutable, I see.

Yogurt (Mar 02 2020 at 20:41, on Zulip):

No, I'm not sure the versions of miri match. I have miri 0.1.0 (07ac1027 2019-09-29) locally. It seems like the playground is using 0.1.0 (2020-02-23 3c444bf). On the blocksize, ya that number should be 16 for each loop until the input iterator has fewer than 16 bytes in it. The playground initially had block_size = min(input_byte_len, 64); which was a type. I've updated it to block_size = min(input_byte_len, 16);.

Yogurt (Mar 02 2020 at 20:53, on Zulip):

Actually. Is it possible that a scope could be taking ownership of the pointer at the MIR level?

Lokathor (Mar 02 2020 at 20:55, on Zulip):

What happens if you replace it with the bytemuck crate and use the cast_slice function to do the conversion?

Yogurt (Mar 02 2020 at 21:07, on Zulip):

Replacing

    let state_8 = unsafe {
        std::slice::from_raw_parts_mut(
            state.as_mut_ptr() as *mut u8,
            48)
    };

with let state_8 = cast_slice_mut(&mut state); which I'm not sure is the correct syntax. My code no longer compiles due to multiple mutable borrows. Using cast_slice I have similar errors but around the state_8 variable not being mutable. However, I've never used the bytemuck crate before and I'm not sure if this is correct usage. Their docs leave a lot to be desired.

Lokathor (Mar 02 2020 at 21:39, on Zulip):

Well, if I understand the rest of your situation correctly then that usage is accurate and your code's borrow errors are the source of the miri failures.

Lokathor (Mar 02 2020 at 21:40, on Zulip):

However, I apologise for the docs situation! If you have ideas on how to improve them please send in an issue. Or even just send in an issue about the problem without a solution and I'll do my best to fix it up.

Yogurt (Mar 02 2020 at 22:06, on Zulip):

A simple example would be nice for the docs. My confusion at the moment around the cast_slice(_mut) functions are how U and T are derived. For instance it's unclear to me if let state_8 = cast_slice_mut(&mut state); will return a &[u8] in my case. I'm not sure if that information can be inferred or not.

Anyway, yes my borrow errors most certainly are coming from having two mutable pointers to the same data structure. These two pointers are a requirement at least for now and hence the unsafe usage :)
I suppose this may just be an anti-pattern that miri doesn't deal with, but I was hoping that this would be a case which was covered.

Lokathor (Mar 02 2020 at 22:31, on Zulip):

Often the output type of a cast cannot be inferred because rust has kinda weak inference and there's so many possible outputs. It is a mild weakness of the library

Lokathor (Mar 02 2020 at 22:34, on Zulip):

as to the aliasing issue: raw pointers actually can alias, but unique references cannot

Lokathor (Mar 02 2020 at 22:35, on Zulip):

so you could maybe to what you want if you never make a &mut T pointing at the stuff

Lokathor (Mar 02 2020 at 22:35, on Zulip):

but that means a lot of rust can't be used, sadly

Yogurt (Mar 02 2020 at 22:39, on Zulip):

Sadly the algorithm I'm porting requires two mutable views of the same array. I believe this requires two mutable pointers, but I would be happy to be wrong there.

Lokathor (Mar 02 2020 at 23:14, on Zulip):

could maybe go by index instead of by pointer

Yogurt (Mar 02 2020 at 23:38, on Zulip):

Perhaps, I'll have to investigate it. Thanks for the help and for letting me think out loud a bit :)

RalfJ (Mar 03 2020 at 18:01, on Zulip):

Yogurt said:

Sadly the algorithm I'm porting requires two mutable views of the same array. I believe this requires two mutable pointers, but I would be happy to be wrong there.

given that the entire point of mutable referneces is not to alias, this sadly will mean that you have to use raw pointers (or indices) throughout

RalfJ (Mar 03 2020 at 18:02, on Zulip):

(the code is still a bit long for me to understand the issue at a glance, and it seems y'all got some idea about where the problem is, so I take it its not worth for me to dig into it right now)

Jake Goulding (Mar 03 2020 at 18:20, on Zulip):

Also without fully grokking the code, I feel like many algorithms can be restated in a way that doesn't require double mutable references.

Yogurt (Mar 03 2020 at 18:55, on Zulip):

To @Jake Goulding point; I think I can rewrite the algorithm to avoid the usage of two pointers. This is on my radar, but that's an exploration down the road. @RalfJ Here's an even more minimal example of the issue with a fake function.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=11f0edd22e7950f23155c6f8e6a2364e

The crux seems to be that in the loop

while input_len > 0 {
...
}

the call to the gimli function seems to take ownership or otherwise makes referencing state_8[i] invalid. I would love to know the rational there because as I understand it I am simply borrowing the pointer (rather than taking ownership) with the gimli function. Moving the gimli call out of the while loop allows miri to pass without complaint. Similarly if the input vector is under 16 elements long miri passes, so I can only assume that the access error occurs only after the first call to gimli.
ex.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=34c4abd62f3043495aa421026ce65219

Jake Goulding (Mar 03 2020 at 19:04, on Zulip):

state and state8 alias each other, don't they?

Jake Goulding (Mar 03 2020 at 19:05, on Zulip):

So when you call gimli passing in state, state8 needs to be invalidated

Jake Goulding (Mar 03 2020 at 19:07, on Zulip):

e.g. I think this is the same:

fn main() {
    let mut state: [u32; 12] = [0; 12];
    let state_8 = unsafe { std::slice::from_raw_parts_mut(state.as_mut_ptr() as *mut u8, 48) };

    for _i in 0..2 {
        state_8[0];
        &mut state;
    }
}
Jake Goulding (Mar 03 2020 at 19:08, on Zulip):

Which is why putting the call to from_raw_parts inside the loop fixes it — you are retaking the single mutable reference

Yogurt (Mar 03 2020 at 19:12, on Zulip):

Yes that's my understanding as well.

Jake Goulding (Mar 03 2020 at 19:14, on Zulip):

Or simpler

fn main() {
    let mut v: i32 = 0;
    let a: &mut i32 = &mut v;
    let b: &mut i32 = unsafe { &mut *(a as *mut _) };

    let _x = *b;
    let _y = *a;
    // let _z = *b; // Causes Miri failure
}
RalfJ (Mar 03 2020 at 19:23, on Zulip):

Yogurt said:

Yes that's my understanding as well, but I suppose I don't understand why. If the state8 pointer needs to be invalidated doesn't that somewhat defeat the point of having two mutable references?

well you are not supposed to have two mutable references, that is the entire point. mutable references must be unique, only one can point to any memory at any given point in time (and be currently "usable").

RalfJ (Mar 03 2020 at 19:24, on Zulip):

IOW, "you can have aliasing or mutation, but never both at the same time" -- the fundamental principle of ownership and borrowing in Rust

Yogurt (Mar 03 2020 at 19:54, on Zulip):

RalfJ said:

IOW, "you can have aliasing or mutation, but never both at the same time" -- the fundamental principle of ownership and borrowing in Rust

I thought this is a fundamental principle of safe rust though. I understand that I am breaking that principle with my use of unsafe and as such I'm trying to add Miri to my workflow so that I can have a better assurance of my usage of unsafe. If that's not a use case for miri then I'm simply out of luck until I can refactor my pointer usage. Thanks again for the help :)

Jake Goulding (Mar 03 2020 at 19:59, on Zulip):

@RalfJ another way of approaching this problem is "I want to interleave treating state as &mut [u32] and &mut [u8], but never both at the same time".

Is there some way of doing some kind of union or reborrowing here?

RalfJ (Mar 03 2020 at 20:04, on Zulip):

this is a fundamental principle of all of Rust, not just safe Rust. I recently gave a talk explaining why. :)
only raw pointers are allowed to get around this, and alias each other during mutation. So indeed you need unsafe code to get around this, but just adding unsafe is not enough -- the reason you need unsafe is that you need raw pointers to get around the principle, and raw pointers only work in unsafe code.

RalfJ (Mar 03 2020 at 20:07, on Zulip):

@Jake Goulding you cannot interleave the use of two different mutable refs, no exceptions. That is the entire point of Stacked Borrows.^^
What you could be able to do is construct &[Cell<u32>] and &[Cell<u8>] appropriately and interleave those (from_mut is useful here).

Jake Goulding (Mar 03 2020 at 20:08, on Zulip):

You can make the sugar sweeter and do the transforms more transparently, but still Miri-clean: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4790f42b00be9e979cc9bd394eaa3d3b

Jake Goulding (Mar 03 2020 at 20:09, on Zulip):

I wonder how well from_parts optimizes away.

Jake Goulding (Mar 03 2020 at 20:09, on Zulip):

@RalfJ well, it's a stack, right? Just add a method that does stack::swap_top(N) :wink:

RalfJ (Mar 03 2020 at 20:09, on Zulip):

I mean sure if you re-cosntruct a new slice from the origin reference each time, of course that also works

Jake Goulding (Mar 03 2020 at 20:10, on Zulip):

yes, I'm just showing a way to reconstruct it each time so that that doesn't get in the way of the algorithm. Also why I muse about the optimizer.

RalfJ (Mar 03 2020 at 20:11, on Zulip):

Jake Goulding said:

RalfJ well, it's a stack, right? Just add a method that does stack::swap_top(N) :wink:

sure we could do that, and then we'll just not be able to do any of the optimizations that motivate SB in the first place ;)

Jake Goulding (Mar 03 2020 at 20:11, on Zulip):

stack::shuffle

Yogurt (Mar 03 2020 at 20:11, on Zulip):

For my case I certainly can reconstruct the reference each time. It's a bit ugly and my C friends will probably cock their eyebrows at me, but :shrug:

RalfJ (Mar 03 2020 at 20:12, on Zulip):

the alternative if you want to use references "on the inside" is to work with interior mutabulity -- i.e, Cell. those types "know" that there can be aliasing so optimziations are suspended around them.

Yogurt (Mar 03 2020 at 20:13, on Zulip):

well the end goal is to get away from aliasing so.... I'll avoid that, but thanks :)

RalfJ (Mar 03 2020 at 20:13, on Zulip):

your original code had aliasing though, that is the entire problem ;) and the C version of this has aliasing, too.

RalfJ (Mar 03 2020 at 20:13, on Zulip):

one way or another, you need to tell the compiler about the aliasing. I'm afraid that is the price we have to pay if we want the compiler to optimize our code based on aliasing assumptions.

Jake Goulding (Mar 03 2020 at 20:13, on Zulip):

@Yogurt that is why I showed the prettier way of reconstructing it

RalfJ (Mar 03 2020 at 20:14, on Zulip):

yeah, @Jake Goulding 's approach is the one that avoids aliasing

Jake Goulding (Mar 03 2020 at 20:14, on Zulip):

Also, if you change gimli to take in &[u8] then you'd also succeed, I think

RalfJ (Mar 03 2020 at 20:14, on Zulip):

@Jake Goulding wow you didn't even hard-code the factor of 4 for the size like I would have^^

Jake Goulding (Mar 03 2020 at 20:15, on Zulip):

I do not believe in my ability to do basic math like that always

RalfJ (Mar 03 2020 at 20:15, on Zulip):

ah but I think there's a mistake... you are using the slice self.0 after creating the raw ptr

Yogurt (Mar 03 2020 at 20:15, on Zulip):

@RalfJ Yes, but the 8bit pointer is a convenience. The same math can be done with 32bit pointers and masks

@Jake Goulding This code block?

fn main() {
    let mut v: i32 = 0;
    let a: &mut i32 = &mut v;
    let b: &mut i32 = unsafe { &mut *(a as *mut _) };

    let _x = *b;
    let _y = *a;
    // let _z = *b; // Causes Miri failure
}

Isn't that still aliased?

RalfJ (Mar 03 2020 at 20:16, on Zulip):
        unsafe {
            let p = self.0.as_mut_ptr();
            let u8_len = self.0.len() / mem::size_of::<u8>() * mem::size_of::<u32>();
            slice::from_raw_parts_mut(p as *mut u8, u8_len)
        }

this is exactly like the mistake I recently fixed in align_to_mut

Jake Goulding (Mar 03 2020 at 20:16, on Zulip):

@RalfJ you should take that up with the maintainers of Miri — it says it's alllllll good

RalfJ (Mar 03 2020 at 20:17, on Zulip):

Jake Goulding said:

RalfJ you should take that up with the maintainers of Miri — it says it's alllllll good

yeah I am wondering why that is

Jake Goulding (Mar 03 2020 at 20:17, on Zulip):

@RalfJ After creating the raw pointer, but before creating the second reference — now just having the raw pointer is an issue?

RalfJ (Mar 03 2020 at 20:18, on Zulip):

@Yogurt your code block without _z can be written in safe code. this is the kind of "well-nested" aliasing that rust permits -- only one reference being "active" at any point in time

RalfJ (Mar 03 2020 at 20:18, on Zulip):

Jake Goulding said:

RalfJ After creating the raw pointer, but before creating the second reference — now just having the raw pointer is an issue?

no the issue is that self.0.len() is slice::len(&*self.0). you are creating a new shared ref.

Jake Goulding (Mar 03 2020 at 20:18, on Zulip):

@Yogurt this one specifically - https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4790f42b00be9e979cc9bd394eaa3d3b

RalfJ (Mar 03 2020 at 20:19, on Zulip):

ah but unlike in the align_to_mut case you didnt create a mutable ref before that

RalfJ (Mar 03 2020 at 20:19, on Zulip):

so you are fine actually, Miri was right^^

Jake Goulding (Mar 03 2020 at 20:19, on Zulip):

right. The ref is the last thing. I'm surprised the align_to_mut wasnt

RalfJ (Mar 03 2020 at 20:19, on Zulip):

calling self.0.len() invalidates any mutable refs you might have created since self.0.as_mut_ptr(). which I hope makes sense?

RalfJ (Mar 03 2020 at 20:20, on Zulip):

you are creating a shared ref, that invalidates mutable refs derived before as they dont allow aliasing

Jake Goulding (Mar 03 2020 at 20:20, on Zulip):

Oh, because it created the middle / aligned reference first

RalfJ (Mar 03 2020 at 20:20, on Zulip):

exactly

Jake Goulding (Mar 03 2020 at 20:21, on Zulip):

The creation was still in (semi-)tail-position, which is where it belongs, just that it was in that tuple.

RalfJ (Mar 03 2020 at 20:21, on Zulip):

yeah it was created late but not quite late enough

Jake Goulding (Mar 03 2020 at 20:28, on Zulip):

I kinda wanna see what happens with

union X {
    A([u8]),
    B([u32]),
}

//convert &mut[u32] -> &mut X

but I'm lazy.

RalfJ (Mar 03 2020 at 20:50, on Zulip):

well that certainly wont help avoid unsafe code^^

Yogurt (Mar 04 2020 at 19:18, on Zulip):

One more question on this thread. When aliasing a piece of data why is it that calling a helper function invalidates the aliased pointer?
ex.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=55371cda2bcd02fc79e7aa25ff385f79

Lokathor (Mar 04 2020 at 21:03, on Zulip):

Just as an approximation, anything that would cause a borrow check error with only references will probably invalidate a pointer when you mix references and pointers. Usually once you start using pointers you should stay with only pointers until you're done with all pointer work, and then go back to using references.

This is part of why bytemuck is useful, because since it's a dedicated function it has lifetime annotations on how the inputs and outputs are linked, so the compiler realizes what's going on.

RalfJ (Mar 06 2020 at 18:21, on Zulip):

Yogurt said:

One more question on this thread. When aliasing a piece of data why is it that calling a helper function invalidates the aliased pointer?
ex.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=55371cda2bcd02fc79e7aa25ff385f79

to get the optimizations we want, calling that helper function (even though it does nothing) basically has the same effect as actually writing to that memory using the reference passed to the function

Last update: Jun 05 2020 at 22:40UTC