Stacked Borrows around GlobalAlloc

[niluxv]

One of my tests recently started to fail under Miri with a stacked borrows violation error. I've now kind of minimised the test case but I don't really understand why it is a stacked borrow violation. For the test to fail, a custom global allocator is necessary. All the allocator does is zeroize memory on drop, and forward calls to the System allocator.

#![deny(unsafe_op_in_unsafe_fn)]

use core::alloc::{GlobalAlloc, Layout};
use std::alloc::System;

/// # Safety
/// `ptr` must be valid for writes of `len` bytes
unsafe fn volatile_write_zeroize_mem(ptr: *mut u8, len: usize) {
    for i in 0..len {
        // ptr as usize + i can't overlow because `ptr` is valid for writes of `len`
        let ptr_new: *mut u8 = ((ptr as usize) + i) as *mut u8;
        // SAFETY: `ptr` is valid for writes of `len` bytes, so `ptr_new` is valid for a
        // byte write
        unsafe {
            core::ptr::write_volatile(ptr_new, 0u8);
        }
    }
}

pub struct ZeroizeAlloc;

unsafe impl GlobalAlloc for ZeroizeAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // SAFETY: uphold by caller
        unsafe { System.alloc(layout) }
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        // securely wipe the deallocated memory
        // SAFETY: `ptr` is valid for writes of `layout.size()` bytes since it was
        // previously successfully allocated (by the safety assumption on this function)
        // and not yet deallocated
        unsafe {
            volatile_write_zeroize_mem(ptr, layout.size());
        }
        // SAFETY: uphold by caller
        unsafe { System.dealloc(ptr, layout) }
    }

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
        // SAFETY: uphold by caller
        unsafe { System.alloc_zeroed(layout) }
    }
}

#[global_allocator]
static GLOBAL: ZeroizeAlloc = ZeroizeAlloc;

fn main() {
    let layout = Layout::new::<[u8; 16]>();
    let ptr = unsafe { std::alloc::alloc_zeroed(layout) };
    unsafe {
        std::alloc::dealloc(ptr, layout);
    }
}

Playground

Relevant fragment of the error:

error: Undefined Behavior: no item granting write access for deallocation to tag <3434> at alloc772 found in borrow stack
  --> /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:42:9
   |
42 |         libc::free(ptr as *mut libc::c_void)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access for deallocation to tag <3434> at alloc772 found in borrow stack
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
           
   = note: inside `std::sys::unix::alloc::<impl std::alloc::GlobalAlloc for std::alloc::System>::dealloc` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:42:9
note: inside `<ZeroizeAlloc as std::alloc::GlobalAlloc>::dealloc` at src/main.rs:37:18
  --> src/main.rs:37:18
   |
37 |         unsafe { System.dealloc(ptr, layout) }

Full error log with pointer and allocation tracking (click to expand)

note: tracking was triggered
  --> /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:14:13
   |
14 |             libc::malloc(layout.size()) as *mut u8
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^ created allocation with id 772
   |
   = note: inside `std::sys::unix::alloc::<impl std::alloc::GlobalAlloc for std::alloc::System>::alloc` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:14:13
note: inside `<ZeroizeAlloc as std::alloc::GlobalAlloc>::alloc` at src/main.rs:25:18
  --> src/main.rs:25:18
   |
25 |         unsafe { System.alloc(layout) }
   |                  ^^^^^^^^^^^^^^^^^^^^
   = note: inside `alloc::alloc::__rust_alloc` at src/main.rs:47:1
   = note: inside `std::alloc::alloc` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:87:14
   = note: inside `std::alloc::Global::alloc_impl` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:169:73
   = note: inside `<std::alloc::Global as std::alloc::Allocator>::allocate` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:229:9
   = note: inside `alloc::alloc::exchange_malloc` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:318:11
   = note: inside `std::sys_common::thread_local_dtor::register_dtor_fallback` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/thread_local_dtor.rs:33:28
   = note: inside `std::sys::unix::thread_local_dtor::register_dtor` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/thread_local_dtor.rs:43:5
   = note: inside `std::thread::__FastLocalKeyInner::<std::cell::RefCell<std::option::Option<std::sys_common::thread_info::ThreadInfo>>>::register_dtor` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/thread/local.rs:577:17
   = note: inside `std::sys_common::thread_info::THREAD_INFO::__getit` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/thread/local.rs:220:29
   = note: inside `std::thread::LocalKey::<std::cell::RefCell<std::option::Option<std::sys_common::thread_info::ThreadInfo>>>::try_with::<[closure@std::sys_common::thread_info::set::{closure#0}], ()>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/thread/local.rs:398:32
   = note: inside `std::thread::LocalKey::<std::cell::RefCell<std::option::Option<std::sys_common::thread_info::ThreadInfo>>>::with::<[closure@std::sys_common::thread_info::set::{closure#0}], ()>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/thread/local.rs:375:9
   = note: inside `std::sys_common::thread_info::set` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/thread_info.rs:42:5
   = note: inside `std::rt::init` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:86:9
   = note: inside closure at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:127:42
   = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#1}], ()>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:406:40
   = note: inside `std::panicking::r#try::<(), [closure@std::rt::lang_start_internal::{closure#1}]>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:370:19
   = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#1}], ()>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:133:14
   = note: inside `std::rt::lang_start_internal` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:127:5
   = note: inside `std::rt::lang_start::<()>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:144:17

note: tracking was triggered
  --> /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/thread_local_dtor.rs:41:35
   |
41 |             let list: Box<List> = Box::from_raw(ptr as *mut List);
   |                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ created tag 3434
   |
   = note: inside `std::sys_common::thread_local_dtor::register_dtor_fallback::run_dtors` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/thread_local_dtor.rs:41:35

note: tracking was triggered
    --> /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1128:9
     |
1128 |         intrinsics::volatile_store(dst, src);
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ popped tracked tag for item [Unique for <3434>]
     |
     = note: inside `std::ptr::write_volatile::<u8>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1128:9
note: inside `volatile_write_zeroize_mem` at src/main.rs:15:13
    --> src/main.rs:15:13
     |
15   |             core::ptr::write_volatile(ptr_new, 0u8);
     |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `<ZeroizeAlloc as std::alloc::GlobalAlloc>::dealloc` at src/main.rs:34:13
    --> src/main.rs:34:13
     |
34   |             volatile_write_zeroize_mem(ptr, layout.size());
     |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: inside `alloc::alloc::__rust_dealloc` at src/main.rs:47:1
     = note: inside `std::alloc::dealloc` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:105:14
     = note: inside `<std::alloc::Global as std::alloc::Allocator>::deallocate` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:242:22
     = note: inside `alloc::alloc::box_free::<std::vec::Vec<(*mut u8, unsafe extern "C" fn(*mut u8))>, std::alloc::Global>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:336:9
     = note: inside `std::sys_common::thread_local_dtor::register_dtor_fallback::run_dtors` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/thread_local_dtor.rs:47:9

error: Undefined Behavior: no item granting write access for deallocation to tag <3434> at alloc772 found in borrow stack
  --> /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:42:9
   |
42 |         libc::free(ptr as *mut libc::c_void)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access for deallocation to tag <3434> at alloc772 found in borrow stack
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
           
   = note: inside `std::sys::unix::alloc::<impl std::alloc::GlobalAlloc for std::alloc::System>::dealloc` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:42:9
note: inside `<ZeroizeAlloc as std::alloc::GlobalAlloc>::dealloc` at src/main.rs:37:18
  --> src/main.rs:37:18
   |
37 |         unsafe { System.dealloc(ptr, layout) }
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: inside `alloc::alloc::__rust_dealloc` at src/main.rs:47:1
   = note: inside `std::alloc::dealloc` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:105:14
   = note: inside `<std::alloc::Global as std::alloc::Allocator>::deallocate` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:242:22
   = note: inside `alloc::alloc::box_free::<std::vec::Vec<(*mut u8, unsafe extern "C" fn(*mut u8))>, std::alloc::Global>` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:336:9
   = note: inside `std::sys_common::thread_local_dtor::register_dtor_fallback::run_dtors` at /home/niels/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/thread_local_dtor.rs:47:9

error: aborting due to previous error

The strange thing is, when the volatile_write_zeroize_mem call is moved from the dealloc into main (directly before the dealloc) the example runs just fine.
Playground

[niluxv]

Probably related to PR #1885.

[niluxv]

Slightly smaller playground.

Interestingly, the casts in zero_one_byte (previously volatile_write_zeroize_mem) are necessary.

[RalfJung]

Interesting. Box is special magic when it comes to alias tracking in Stacked Borrows, and integer-pointer casts are a never-ending source of pain and ambiguity, so I suspect the combination of those two is what explodes here.

FWIW your example errors even with an empty main -- the problem is some allocation that happens inside the standard library.

[RalfJung]

Your volatile_write_zeroize_mem could be implemented without invoking the hell that is int-to-ptr casts by using offset instead. The pointer has to be in-bounds anyway so this cannot add any more UB.

[RalfJung]

Ah, I think what happens is something like

• when the Box gets created, it calls into your allocator which returns an untagged pointer
• the ptr is basically transmuted to type Box, which causes a tag to be generated with unique permission and pushed to the borrow stack
• that same pointer ends up in your dealloc. The ptr-int-ptr roundtrip causes the tag to be lost, so it 'reverts' to the untagged pointer, which makes the unique Box pointer invalid.
• next your code uses the unique pointer for deallocation, but now this is an invalid pointer so this is a Stacked Borrows violation.

Allocators are tricky in that they "generate unique pointers" but then during deallocation (if this is implemented in userspace, not as a language primitive) somehow we have to 'forget' that these pointers are unique and treat them again as the shared raw pointers that they were before the magic act of allocation "blessed" them. I have not yet seen a proposal for how to solve this.

Though in this case one could argue the real culprit is the combination of a tagged raw pointer and integer-pointer-roundtrips -- the same problem that makes -Zmiri-track-raw-pointers not support integer-pointer-casts.

[bjorn3]

Can you push a special Allocated element onto the stack that can only be popped by going through dealloc and always gets popped at dealloc?

[niluxv]

Your volatile_write_zeroize_mem could be implemented without invoking the hell that is int-to-ptr casts by using offset instead. The pointer has to be in-bounds anyway so this cannot add any more UB.

Well, then to be safe len has to fit an isize, so it requires a check for this in alloc (only on < 64 bit systems fortunately). That is in fact the main reason I'm doing int-ptr-roundtrips here right now. I could also do wrapping_offset (without the isize requirement; but the addition never wraps...).

Edit: I can just repeatedly offset with 1 and it will always be sound, and even gives slightly better asm.

[RalfJung]

@niluxv LLVM/Rust do not support allocations that do not fit into an isize. There is no situation where the integer roundtrip can help here.

@bjorn3 the trouble is that dealloc would have to "undo" the tagging of its pointer that happened when it got turned into a Box. Basically it would have to store the old tag somewhere and then restore it inside dealloc.

[niluxv]

The documentation of the standard library tells otherwise (emph mine):

Most platforms fundamentally can’t even construct such an allocation. For instance, no known 64-bit platform can ever serve a request for 2^63 bytes due to page-table limitations or splitting the address space. However, some 32-bit and 16-bit platforms may successfully serve a request for more than isize::MAX bytes with things like Physical Address Extension. As such, memory acquired directly from allocators or memory mapped files may be too large to handle with this function.

(Note that ZeroizeAlloc in reallity needs to be able to wrap arbitrary GlobalAllocs, not just System.)

[RalfJung]

Weird... that is somewhat dubious at best, since LLVM to my knowledge will make the assumption that no allocation is larger than half the address space, and that offsets by more than isize::MAX (even when done in multiple steps) will always leave the allocation. But I am not an expert on all the details here of what this would mean in practice.

[RalfJung]

FWIW, this code is accepted now that Miri has better support for int-to-ptr casts. We should probably add it as a test.