Can black_box/inline assembly be used for constant time initialization?

help
1

It's my understanding that in Rust, data must be written to to be initialized. Since writing to a large slice is in linear time with respect to the length of the slice, so is the initialization.

It is my understanding that memory can be initialized by passing a raw pointer of the memory to an extern function that will write the memory. Since extern functions may be opaque to the compiler, I'd guess that they could slack off with out anyone ever knowing, as long as arbitrary bytes make sense as an output.

That may seem far fetched, but any function that is opaque to the compiler would be runtime only and target-specific. While write-less initialization may be undefined in general, a specific executable in a specific context could still do it in a predictable way. An article by Ralf Jung on the topic emphasizes a distinction between the Rust virtual machine's memory and the actual state of the RAM of the target machine.

This leads me to suspect that something similar to the black_box() function could work:

use std::{hint::black_box, mem::MaybeUninit, slice};

pub unsafe fn initialize_with_anything(dst: *mut u8, len: usize) {
    black_box((dst, len));
}

pub fn init_slice<'a>(data: &'a mut [MaybeUninit<u8>]) -> &'a mut [u8] {
    let init_ptr = data.as_mut_ptr().cast();
    unsafe {
        initialize_with_anything(init_ptr, data.len());
        slice::from_raw_parts_mut(init_ptr, data.len())
    }
}

I am aware of the disclaimer on the docs for black_box(). A more serious implementation would be a pollyfill that defaults to zeroing the memory but uses inline assembly on platforms where constant-time initialization is possible.

How far off am I?

2

Your example code looks like transmute.

There is some ambiguity in your question, since a copy by definition cannot be constant time. Perhaps you can elaborate on what you are actually trying to accomplish, if not eliminate linear time operations like memory copies.

For instance, if you pre-compute the structure in a build script as a static allocation, the only copy that needs to happen is loading the executable from disk. For all intents and purposes, it will be initialized before the program starts, thus constant time.

But my interpretation of your question is probably wrong. An elaboration would be helpful.

3

I think the question essentially is "if we black_box a pointer to some memory, will this work as LLVM's freeze, i.e. will the pointed-to memory be converted from undef to some arbitrary defined value?"

1 Like
4

That's still UB. Initialization is a semantic property of code execution. While your hack can possibly thwart some optimizations, there are still plenty of ways for it to break.

First, black_box is a best effort function. It doesn't guarantee that the compiler doesn't know about your tricks, since at the low level it's impossible to do. If you conpile code with LTO (link-time optimizations) enabled, black_box is not preserved. By the time LTO happens, it's just an identity function. If you compile to a target with JIT optimizations (e.g. WASM), it can also trivially see through your tricks and knows that the memory is uninitialized.

Second, the OS and hardware can still behave erratically when reading memory which wasn't written to. OS can make reads happen from arbitrary dirty or zeroed memory pages which will vary over time. Since you don't do writes, it doesn't know that it needs to preserve the values, and the compiler can't insert the necessary freezes either. You lie to it, while it expects that your initialize_with_anything actually does proper initialization.

At even lower level, processor can have different cores read different stale values from the cache. You don't do writes, so it doesn't know that it must synchronize caches for those pages. And memory controllers may also return garbage from reading uninitialized data, because preserving values in memory requires certain effort on the part of the hardware.

8 Likes
5

I mean make the copy/write operation constant time by skipping the copy/write operation entirely. I don't actually want to copy/write to the memory, I just want to be able to make a &mut [u8] that I can write to later.

Your example code looks like transmute.

Yes, I am effectively transmuting MaybeUninit<u8> to u8. I am not aware of any way to use the transmute function on a slice without some verbose iterating logic, but ptr casting is the equivalent of transmute for slices.

6

That is exactly right, thanks for pointing that out.

I saw the freeze function in the docs before I was aware of this problem, and I didn't understand what it did. Then I read the 2019 article previously linked to which said freeze was something still being worked on. I never put two and two together until I read your comment.

freeze takes the input by value, not by reference, while my example snippet takes the input by reference. I do know that llvm values can be very big though, so it would be interesting to see if I can transmute to different size value to freeze a slice in logarithmic time.

7

Any sound freeze operation will have to read the whole slice, so you can't do this in logarithmic time.

2 Likes
8

The point is that you have to put something there. Either statically allocated or copied at runtime. And only the former can be considered constant time.

1 Like
9

Thanks for that great response. You gave me a lot to look into.

In the case of WASM in particular though, I'm pretty sure memory is initialized when it is allocated. So I think a black box would still work in that case.

10

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.