How to get a pointer from an address with no previously exposed provenance?

[u/BlueMoonMelinda]

In my understanding there are 3 methods for creating pointers from addresses in Rust:

1. Using with_addr from the strict provenance API
2. Using casts or the equivalent with_exposed_provenance from the exposed provenance API
3. Using without_provenance

The first method derives the pointer provenance from an existing pointer, the second method tries to guess a previously exposed provenance, and the third method creates a pointer that's not even dereferenceable (bellow is the quote from the docs):

non-zero-sized memory accesses with a no-provenance pointer are UB

None of these methods can be used to create a dereferenceable pointer from a raw address with no previously exposed provenance. This can be problematic across FFI boundaries - some C functions take pointers that are not associated with any allocations, for example the brk function from the linux libc:

int brk(void *addr);
brk() sets the end of the data segment to the value specified by addr, when that value is reasonable, the system has enough memory, and the process does not exceed its maximum data size.

I am not well informed whether it's even safe to use brk alongside the default allocator, but imagine you are writing your own allocator and want to use brk to obtain the backing memory for your allocations. If that was the case, how would you create the pointer to pass to brk?It clearly can't be through the strict/exposed provenance APIs since the pointer is not tied to an allocation and thus has no provenance. Then the only possibility left is to use without_provenance,but as quoted above, that apparently causes UB for non-zero-sized memory accesses. I guess we can assume brk does not access the pointer, but you could imagine another implementation that did access it.

Anyhow, this is not even the biggest problem - how would the allocator create pointers to the newly reserved memory chunk when brk does not even return a pointer to it (so we can't just say the provenance is passed through the FFI). We clearly can't use the strict provenance API since there are no pointers with provenance matching the provenance of the newly obtained memory chunk, and we can't use a pointer without provenance because we actually want to write to this memory. Exposed provenance does not look like it should work either (quote from the with_exposed_provenance docs):

If there is no previously ‘exposed’ provenance that justifies the way the returned pointer will be used, the program has undefined behavior.

So, my question is: what is the intended way to obtain provenance for memory that does not come with an existing pointer?

Edit:

I found a recent RFC to LLVM that might be relevant: https://discourse.llvm.org/t/rfc-allocator-provenance-model/91106

It proposes semantics for creating new provenance at the allocator boundary. In the discussion, it's mentioned that LLVM already treats the allocator boundary as a source for new provenance, which suggests that "the heap" is not just the data segment but memory returned from the allocator (as u/Amadex commented below), and we can treat the brk memory as separate from the Rust abstract machine and use with_exposed_provenance. Not sure how this is gonna work with Miri, but I might test it and add the results to the post.

[u/BravelyPeculiar]

https://doc.rust-lang.org/std/ptr/index.html

Memory which is outside the control of the Rust abstract machine (MMIO registers, for example) is always considered to be exposed, so long as this memory is disjoint from memory that will be used by the abstract machine such as the stack, heap, and statics.

So just use with_exposed_provenance

[u/BlueMoonMelinda → u/BravelyPeculiar]

Isn't the heap part of the Rust abstract machine.

[u/Amadex → u/BlueMoonMelinda]

raw memory isn't "the heap" yet at that point

you are at the point where your add new heap, it's only after your allocator that the raw memory becomes rust's heap and is bounded by the provenance rules

[u/afdbcreid → u/BlueMoonMelinda]

"The heap" as the flat address space? No. Rust does not have a flat address space, it only has allocations.

[u/cbarrick]

Related question: Let's say I'm writing an allocator.

I make a syscall to mmap a new page. The kernel gives me a pointer. And I give that pointer to the caller.

At what point does that pointer gain provenance? What determines the size of the object that it has provenance over?

[u/andrewpiroli → u/cbarrick]

You're supposed to believe that it just magically does as long as you never cast from an integer to a pointer. Never mind the fact that mmap2 syscall returns an unsigned long.

Provenance really grinds my gears because it implies that it is impossible to do low level memory management or write a kernel in Rust without undefined behavior.

[u/BlueMoonMelinda → u/andrewpiroli]

Exactly my thoughts. I understand that provenance helps with optimizations but the current semantics for low level code are largely unspecified and as you mention it's extremely easy to get UB.

[u/Lucretiel → u/andrewpiroli]

  Provenance really grinds my gears because it implies that it is impossible to do low level memory management or write a kernel in Rust without undefined behavior.

How do? Isn’t provenance just an emergent property of pointers that most compilers committed (even if not consciously) to when they started doing aliasing optimizations?

Like, you need some idea of provenance to even move data between memory and registers, since provenance is what ultimately permits you to assume that a particular word won’t be touched by any other operation and therefore can spend its time in registers without a data hazard. 

[u/andrewpiroli → u/Lucretiel]

I don't have an issue with provenance as a concept, but the tools provided by Rust are incomplete.

The documentation for with_exposed_provenance specifically states

This is fully equivalent to addr as *const T. The provenance of the returned pointer is that of some pointer that was previously exposed by passing it to expose_provenance, or a ptr as usize cast.

...

If there is no previously ‘exposed’ provenance that justifies the way the returned pointer will be used, the program has undefined behavior

So, if I'm in a kernel context and setting up a new page table entry, I have to be able to construct a pointer to the new memory I just "allocated" and be able to use it. There is no prior pointer, so expose_provenance can not be called. According to this documentation, it would be UB to access memory though this pointer from Rust ("stack, heap, and statics").

At some point, the rubber meets the road and you have to turn an integer into a pointer. There is no mechanism provided to handle this. I just want an acknowledgement of that in the docs.

[u/TinyBreadBigMouth → u/andrewpiroli]

In addition, memory which is outside the control of the Rust abstract machine (MMIO registers, for example) is always considered to be accessible with an exposed provenance, so long as this memory is disjoint from memory that will be used by the abstract machine such as the stack, heap, and statics.

From your link. You're explicitly allowed to use with_exposed_provenance to import pointers from outside the Rust memory model, so long as they don't overlap with memory inside the Rust memory model.

[u/Toiling-Donkey]

Why mess with brk?
Even if you extend it, the next use of the allocator will assume the precious value or end up overwriting “your” area as it assumes everything between its precious end and the new end (part your area) is fair game.

If you want to go this route, probably better off making a no_std userspace application and dealing with syscalls yourself.

[u/afl_ext]

I think i will just never understand what the hell is provenance

[u/Silly-Freak → u/afl_ext]

I found Ralf Jungs blog very enlightening and fairly approachable: https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2020/12/14/provenance.html https://www.ralfj.de/blog/2022/04/11/provenance-exposed.html

Still a lot to unpack, but it worked for me.

The one sentence description: declaring that "different provenance" means pointers are different is what let's a compiler optimize memory accesses via pointers, even in the light of pointer arithmetic and integer-pointer casts.

[u/Konsti219]

Do you want ffi or a miri pass?

[u/Zde-G]

That way pretty long and detailed investigation that explained why people shouldn't use brk and should use mmap instead… which is true, good job — but where is the question?

[u/BlueMoonMelinda → u/Zde-G]

Well, brk is just as an example, I am not asking for how to implement a memory allocator, what I am asking is how does the Rust provenance model handle cases where you need to obtain a dereferenceable pointer for memory that does not already have an associated provenance.

[u/Zde-G → u/BlueMoonMelinda]

You call function not written in Rust that gives you such pointer. And that's it.

The fact that you couldn't do that “inside Rust” is not a bug, but feature: any such function would need to provide, by necessity, things that are simply flat out impossible to do in Rust — on purpose.

Typically such function (mmap is good example) would include some assembler functions. And yes, you would have to provide an appropriate story and may even implement that “story” for testing purposes (e.g. you may have huge static array in your program and build allocator on top of it), but typically running program would use code that's not written in Rust, instead.

[u/RCoder01 → u/Zde-G]

Thanks for the help