search

rust-lang / wg-allocators

Home of the Allocators working group: Paving a path for a standard set of allocator traits to be used in collections!
http://bit.ly/hello-wg-allocators
209 stars 9 forks source link

Replace `MemoryBlock` with `NonNull<[u8]>` #61

Closed SimonSapin closed 4 years ago

SimonSapin commented 4 years ago

The return type some methods involves:

pub struct MemoryBlock {
    pub ptr: NonNull<u8>,
    pub size: usize,
}

A pointer and a size, that sounds familiar.

Perhaps a dedicated struct is not needed and this could be NonNull<[u8]> instead?

NonNull::cast can be used to cast to any thin pointer type, similar to accessing the MemoryBlock::ptr field. PR https://github.com/rust-lang/rust/pull/71940 proposes NonNull<[T]>::len for accessing the size, and NonNull<[T]>::slice_from_raw_parts for constructing a new value. (I feel that these would be good to have regardless of what happens to MemoryBlock, and I expect their existence be uncontroversial given the precedent of <*const [T]>::len and ptr::slice_from_raw_parts.)

Lokathor commented 4 years ago

This makes the struct less repr(C) friendly, so that's a major downside.

TimDiekmann commented 4 years ago

Why would MemoryBlock need repr(c)?

Lokathor commented 4 years ago

Much easier to interact with foreign code if our allocation system can actually have its primitives sent directly to said foreign code.

for plain data structs, repr(C) is a very sane and good default to follow. We don't need any fancy field reordering here.

TimDiekmann commented 4 years ago

I see the argument, why #[repr(C)] is good, but I also like NonNull<[u8]>, it just feels intuitive. Is there an option to make NonNull<[u8]> repr(C) somehow in the future? Was there any progression recently, which defines the layout of fat pointers?

Lokathor commented 4 years ago

I am not on T-Lang or the UCG-wg, but they're both having meetings on Thursday and they're open to the public. I'll try to ask about it if I get a chance, but I expect the answer is "no plans at this time".

glandium commented 4 years ago

NonNull<[u8]> is actually painful to get the length of.

glandium commented 4 years ago

Oh, I missed that there's <*const [T]>::len now.

TimDiekmann commented 4 years ago

What I really like on NonNull<[u8]> is, that we could far more methods to NonNull in generell inspired by *mut T. Sure, those could also be implemented on MemoryBlock, but this feels off. This also comes in handy when dealing with allocators in general as NonNull is widely used in the allocator API. Originally I introduced MemoryBlock to pass it back to the allocator (grow, shrink, dealloc), but now it's just a tiny wrapper around NonNull and usize, which is quite verbose to type every time. It also requires an additional struct to be in scope.

Much easier to interact with foreign code if our allocation system can actually have its primitives sent directly to said foreign code.

Couldn't you just implement an extension trait for NonNull<[u8]>, when you need to talk to ffi? I mean, we don't want to design the allocator API towards a specific C-API. Passing those pointers to/from ffi is pretty easy with https://github.com/rust-lang/rust/pull/71940.

@SimonSapin What you would pass back to the allocator? NonNull<u8> + Layout? NonNull<[u8]> + usize? Would the latter solve #3?

Lokathor commented 4 years ago

Couldn't you just implement an extension trait for NonNull<[u8]>, when you need to talk to ffi? I mean, we don't want to design the allocator API towards a specific C-API.

NonNull<[u8]> cannot currently be passed directly to C. And of course extension traits don't help you either, this is a layout issue.

I'd be totally fine with this proposal if there was a defined and stable layout for the type, but until then we should not change from a simple struct that's easy to have interact with C to a more "rusty" type that makes it harder to interact with C. Because it's not just C that we're talking about of course, this affects Rust being used in Python, and Ruby, and Erlang and all those other things.

TimDiekmann commented 4 years ago

NonNull<[u8]> cannot currently be passed directly to C

I didn't mean to pass it directly but use a wrapper struct (like MemoryBlock), which is #[repr(C)] and is used by the extension trait.

Lokathor commented 4 years ago

I suppose, still feels kinda clunky, but sure.

cormacrelf commented 4 years ago

A bit off topic, but is the size field designed such that the computation to compute it can be optimised out if it's never read? The only way to return the full usable size from AllocRef::alloc is to always compute and include it. That is, if I'm implementing it, should I decide to always return usable sizes and let the optimiser figure out if it was needed, or decide that it's never worth it? If relying on the optimiser, does that tend to work in practice?

This is more a question for wrapping jemalloc etc, which have an extra function call associated with that. I don't think those wrappers will be able to optimise out an extern "C" call (although static jemalloc with LTO?). For pure Rust allocators you can always just structure your code not to forget the usable size.

(Edit: it's also my understanding that eventually, the list of __rg_alloc > GlobalAlloc::alloc (etc) calls is not the spot you should assume AllocRef will be inlined... I don't know how opaque those __rg functions are. But from now, it's more each specific Box<T, MyAllocator> instance, right?)

SimonSapin commented 4 years ago

@cormacrelf This issue is about what type to use in order to represent a pointer and size together. It’s independent of whether and when to do that in the first place, as opposed to only returning a pointer.

Always returning the usable size was proposed in https://github.com/rust-lang/wg-allocators/issues/17#issuecomment-585241852. I think how optimization interacts with the global allocator indirection is interesting, please consider filing a new issue.

I don't know how opaque those __rg functions are.

I don’t remember the exact scenario I tried, but quite some time ago I observed that __rg_alloc could be inlined with LTO (thin or not) but not without. This is unsurprising as it is just before linking (after compiling each crate) that the compiler decides what allocator to use (depending on which if any crate defines a #[global_allocator]) and synthesizes __rust_alloc and other trampoline functions.

Wodann commented 4 years ago

I've given this a little more thought and actually feel like NonNull<u8> seems deceptively intuitive, but actually leads to misconceptions of what we have (please correct me if I am wrong).

A NonNull<T> is a *mut T. A MemoryBlock transitively is a *mut u8 plus a usize length.

This is indeed a familiar pattern. Rust came up with slices for this case: [u8]. This is not the same as NonNull<[u8]>, however, as this would be a *mut [u8] (a mutable pointer to a slice).

I recognise that we can use the internal implementation of slices as a fat pointer to benefit from the apparent equality between MemoryBlock and NonNull<[u8]>, but semantically they are not the same.

If we are to follow this path, we should imo hide the implementation (potentially behind a AllocSlice type), similar to how the slice primitive hides the implementation. We also need to be aware that potential changes to the implementation of slice can have undesired consequences for our novel MemoryBlock.

W.r.t. C ABI compatibility, I don't think this is an issue. A big shortcoming of C is the inability to specify the length alongside a pointer. That's why you often pass in a size_t along with a pointer. A C API for the Rust AllocRef traits would have to anyway do this, to provide a "safe" C API.

petertodd commented 4 years ago

A problem with MemoryBlock or any other type with more semantics than "here is the memory address of the allocation you requested" is redundancy: if I ask for 100 bytes from alloc, and receive a slice, am I supposed to check if the slice length is what I asked for?

While normally more types to encode semantics are a good thing. In this case because low-level memory allocation is via opaque, type-erased, API's I think it could make more sense to just accept that and make it clear that the callee should just trust the allocator to implement the API correctly. Notably, AllocRef is an unsafe trait.

Thus I'd suggest we instead return NonNull<!> or NonNull<()> or make it 100% clear that API is opaque and trusted, and the callee should immediately cast the returned pointer to the correct type.

EDIT: wait, sorry, I somehow totally forgot that alloc() and similar may return a block of memory that's larger than requested. So MemoryBlock or NonNull<[u8]> is fine by me and communicates non-redundant information.

SimonSapin commented 4 years ago

@Wodann Sorry, I don’t understand what your point is.

the apparent equality between MemoryBlock and NonNull<[u8]>, but semantically they are not the same

How they semantically not the same? They both describe a region of memory by its starting address and size/length.

we should imo hide the implementation (potentially behind a AllocSlice type)

That’s mostly just another name for MemoryBlock. The point of this proposal is that we wouldn’t need to introduce a new type.

@petertodd The problem with returning a pointer to something that has size_of() == 0 like ! or () is that calling .offset(…) silently gives you the same pointer back.

As to returning a size, yes as your edit says it’s to allow the allocator to return more than requested. If I ask for 100 bytes, jemalloc will usually return 128 bytes.

As to whether returning a size should be part of the "default" APIs, that was proposed in https://github.com/rust-lang/wg-allocators/issues/17#issuecomment-585241852 and off-topic for this thread. This thread discusses how to represent a size together with a pointer, assuming we want to include it.

Wodann commented 4 years ago

@SimonSapin As I mentioned in my post

How they semantically not the same? They both describe a region of memory by its starting address and size/length.

As I mentioned in my post:

A NonNull<T> is a *mut T. The result of an allocation (or a MemoryBlock transitively) is a *mut u8 plus a usize length. The proposed NonNull<[u8]> is a *mut [u8].

Even though it encodes the same information, this communicates something completely different to the end user. Namely:

"You are returned a slice (aka a pointer to memory plus a size)" vs "You are returned a mutable pointer to a slice"

Why this is an issue? Intuitively that would make me believe that I still need to follow a pointer to get the actual address of the memory block.

SimonSapin commented 4 years ago

Ok I think there is some confusion here due to our collective inconsistent use of the word "slice" to mean sometimes [u8] and sometimes &[u8]. If we try to be consistent we can come of with some definitions:

All kinds of references and pointers to a given type T have the same representation: the memory address of the T value together with optional metadata, and the same size_of:

All of these can be combined in almost any way:

Once upon a time (before Rust 1.0 I think?) dynamically-sized types did not exist in the language. [U] was not a valid type on its own. Instead, &[U] and &mut [U] were special cases, two of the basic types in the language. At the time it made sense to call them a slice and a mutable slice respectively, because they were the only two ways to have any kind of slice. *mut [U] was not a valid type.

Today still we tend to casually refer for example to &[u8] as a slice of bytes. This is in part for this historical reason, in part because repeating "reference to slice" all the time gets annoying. So the term by itself is ambiguous, and we should try to make the number of levels of indirection clear based on context.

this communicates something completely different to the end user. Namely:

"You are returned a slice (aka a pointer to memory plus a size)" vs "You are returned a mutable pointer to a slice"

Honestly I’m not sure which of these two is MemoryBlock and which is NonNull<[u8]>.

If we assume my definitions above, your description "a pointer to memory plus a size" makes it clear that you mean "casual" use of the word slice, with one level of indirection rather than zero. (Zero levels would be a [u8] DST which cannot be a return type.)

And "a mutable pointer to a slice" fits *mut [U], again with one level of indirection. So to me, your two descriptions are roughly the same.

Intuitively that would make me believe that I still need to follow a pointer to get the actual address of the memory block.

That would be two levels of indirection like &&[u8] or NonNull<*mut [u8]>, but that’s not the case here.

To some extent I think we can help clear this confusion with more docs and teaching, but it’s a fair point that raw (pointers to) slices *mut [U] and NonNull<[U]> are somewhat uncommon in Rust and so people may not be familiar with them. This is a downside compared to MemoryBlock that you can click on in rustdoc and see the struct definition with two fields.

Lokathor commented 4 years ago

Perhaps a compromise might be a MemoryBlock type with:

RustyYato commented 4 years ago

Another option is a typedef

type MemoryBlock = NonNull<[u8]>;
Lokathor commented 4 years ago

I would still much favor a dedicated struct that can be repr(C).

SimonSapin commented 4 years ago

The premise of this proposal is that adding a new struct adds API surface and therefore complexity. In this case this may not be necessary since the language already has an equivalent type. Adding conversion impls does not really help there.

A typedef adds less API surface than a struct, but I’m not sure what is the point of it existing.

The repr(C) argument is valid but it feels weak in my opinion:

Lokathor commented 4 years ago

Well, the point of all of this is to unify the ecosystem. Nothing here is in any way enabling people to write programs they can't write today. We're just picking conventions for the ecosystem to follow.

So starting my logic from there, I think that it would be a better situation for Rust to pick a convention that is more friendly by default to being called from other hosted languages that might want to call into a native language, such as Python, Erlang/Elixir, etc. Rust already has some success stories with being the native lang of choice for hosted languages and we should try to continue the trend. Being able to return an allocator's output directly to foreign code, instead of each allocator or foreign framework having its own idea of what a rust allocation translates to, would help maintain ecosystem unity in this area.

But I guess if allocators have to use Result then we're already well past being able to easily have a pub "C" fn that calls the allocator, so that goal already doesn't work so well. However, I don't think there's much error reporting to do under a normal allocation failure so I don't think Result should even be used. I'd prefer either MemoryBlock (with size 0 for errors) or Option<NonNull<[u8]>> (with None for errors). If that can't be done, I guess oh well then.

Wodann commented 4 years ago

@SimonSapin thanks for the elaborate explanation, and apologies if my point wasn't clear.

I'll try to clarify my previous argument. A NonNull<T> is implemented as:

pub struct NonNull<T: ?Sized> {
    pointer: *const T,
}

impl<T: ?Sized> NonNull<T> {
    /// Creates a new `NonNull` if `ptr` is non-null.
    #[stable(feature = "nonnull", since = "1.25.0")]
    #[inline]
    pub fn new(ptr: *mut T) -> Option<Self> {
        if !ptr.is_null() { Some(unsafe { Self::new_unchecked(ptr) }) } else { None }
    }

    /// Acquires the underlying `*mut` pointer.
    #[stable(feature = "nonnull", since = "1.25.0")]
    #[rustc_const_stable(feature = "const_nonnull_as_ptr", since = "1.32.0")]
    #[inline]
    pub const fn as_ptr(self) -> *mut T {
        self.pointer as *mut T
    }

    ...
}

In your case (NonNull<[u8]>), that is a *const [u8] internally and a *mut [u8] upon creation and decomposition.

As you pointed out

For T = [U] in particular, the metadata is the number of elements in the slice. size_of for &[U] is 16 on x86-64. The two component (data address and metadata) are apparent in the signature of std::slice::from_raw_parts.

This means that NonNull<[u8]> contains a pointer to the slice (implemented as a fat pointer since it is dynamically sized). Any user following the NonNull and slice APIs would now know to access fields using non_null.as_ref().as_ptr(), hence two levels of indirection. Comparatively, someone using MemoryBlock would only have one layer of indirection when accessing ptr (as the MemoryBlock instance will be in memory).

You already proposed

NonNull::cast can be used to cast to any thin pointer type, similar to accessing the MemoryBlock::ptr field. PR rust-lang/rust#71940 proposes NonNull<[T]>::len for accessing the size to alleviate this problem. By using knowledge about the layout of a fat pointer you can cast NonNull<[u8]>'s pointer to any type and directly access the fat pointer's data pointer. This works as a result of the implementation of fat pointer and - I think - would confuse a lot of end users who are unfamiliar with this implementation detail. As you said this could however potentially be resolved by adding documentation.

The same fix won't work for obtaining the sized of the memory block, as evident from the NonNull::len implementation:

pub const fn len(self) -> usize {
    self.as_ptr().len()
}

It still requires an additional layer of indirection for accessing the size of a memory block.

Please tell me if it's still not clear what I am trying to explain, or if I am overlooking some implementation detail that would not make it two memory accesses.

Amanieu commented 4 years ago

len does not perform any indirection. A NonNull<[u8]> is effectively just a (*mut u8, usize) and len returns the second element of the pair.

Amanieu commented 4 years ago

In particular, NonNull<[u8]> is a fat pointer. It is not a pointer to a fat pointer.

RustyYato commented 4 years ago

Also note that NonNull::as_ptr is a no-op that just does a type conversion, so we really are just reading the length off the the pointer directly.

TimDiekmann commented 4 years ago

But I guess if allocators have to use Result then we're already well past being able to easily have a pub "C" fn that calls the allocator, so that goal already doesn't work so well. However, I don't think there's much error reporting to do under a normal allocation failure so I don't think Result should even be used. I'd prefer either MemoryBlock (with size 0 for errors) or Option<NonNull<[u8]>> (with None for errors). If that can't be done, I guess oh well then.

They don't have to use Result, but it's the only viable option in Rust IMO. I don't see any reason, not to use Result, and only use MemoryBlock with a size 0 for errors is a step back to C-like code. Rust as an established error handling strategy returning Result if an error can happen, which is the case here. Returning a zeroed size would complicate this and is very likely to be forgotten. If unwrapping is the bottleneck in a use-case, it's a micro-optimization, which can be bypassed with unreachable_unchecked so I don't think omitting Result is an option.

As @SimonSapin mentioned, you have to handle the return value anyway. Any FFI-API differs in it's required parameters and return values, so there is no variant to rule them all. When I'd have to use the allocator-api in an FFI-environment, I'd simply use an extension trait, which implements on every T where T: AllocRef and provides the needed (de/re-)allocation methods, but with the parameters/return types, which the FFI requires. We should not pollute the stdlib with those things.

TimDiekmann commented 4 years ago

@petertodd

[...] make it clear that the callee should just trust the allocator to implement the API correctly. Notably, AllocRef is an unsafe trait.

I think this holds for every trait, not only for unsafe traits :wink:

Lokathor commented 4 years ago

No no, the general contract of Rust as a whole is that unsafe code in a generic context can only trust a trait impl of an unsafe trait to work correctly. Any safe trait is "allowed" to give pathological outputs and if that makes something go wrong the "fault" of the situation is with the unsafe code (for trusting safe code) and not with the impl of the safe trait.

SimonSapin commented 4 years ago

Any user following the NonNull and slice APIs would now know to access fields using non_null.as_ref().as_ptr(), hence two levels of indirection. Comparatively, someone using MemoryBlock would only have one layer of indirection when accessing ptr (as the MemoryBlock instance will be in memory).

You’re using "levels of indirection" to count the number of method calls in a Rust expression, whereas my earlier comment used it to to count the number of pointer that can be followed in a "chain" (u8 has zero, NonNull<[u8]> has one like &[u8], and &mut &[u8] has two, etc.) These are completely different concepts.

As others have mentioned, some of these methods do type conversion but effectively do nothing at run-time. In the compiled assembly, &[u8] and *mut [u8] and NonNull<[u8]> are all indistinguishable from each other.

Wodann commented 4 years ago

If I understand correctly from @Amanieu (thanks!), the compiler does an optimisation that turns NonNull into a fat pointer.

In particular, NonNull<[u8]> is a fat pointer. It is not a pointer to a fat pointer.

len does not perform any indirection. A NonNull<[u8]> is effectively just a (*mut u8, usize) and len returns the second element of the pair.

In that case I see how there would be only one layer or indirection. For clarity, my understanding was as follows:

NonNull<u8>:

struct AllocatedMemorySlice {
   memory: *mut u8
   length: usize,
}

struct AllocatedMemoryWithNonNull {
  ptr: *const AllocatedMemorySlice
}

vs

MemoryBlock

struct AllocatedMemory {
   ptr: *mut u8
   length: usize,
}

Just to clear up the last misunderstanding, I was also referring to chasing pointers since as_ref().as_ptr() results in following two pointers in the case of AllocatedMemoryWithNonNull: self.ptr.memory. Hence why I understood there to be two layers of indirection.

If the function explanation contained information about NonNull<[u8]> actually being directly represented as a fat pointer for which you can access its memory address and memory size without additional redirection, I am okay with swapping out MemoryBlock for NonNull<u8> as an implementation detail.

If anything, I feel like the discussion and misunderstanding we've had about implementation details of NonNull's usage of fat pointers showcase the potential confusion we might cause. That is in part due to my laziness in my original comments, where I assumed that my point would get across - thinking we share the same understanding of the problem space. It turns out that I had wrong prior knowledge. Yet, this is likely to happen with others if we don't document this carefully.

I think it will be easier to document if we have a dedicated type (alias), as it centralises this critical documentation. If not, I am afraid that docs will blow up + make maintainance harder - if we need to copy the same docs to all functions that return NonNull<[u8]>.

P.s. for the record, my prior concern that

We also need to be aware that potential changes to the implementation of slice can have undesired consequences for [NonNull<[u8]>].

is probably a non-concern as fat pointers and their optimisations are seemingly well established.

SimonSapin commented 4 years ago

I took time at https://github.com/rust-lang/wg-allocators/issues/61#issuecomment-636997729 to make a detailed explanation of the exact same facts and reasoning, arriving at the same conclusion. It seems I failed to get something across :/

Wodann commented 4 years ago

For me, the missing part was:

In particular, NonNull<[u8]> is a fat pointer. It is not a pointer to a fat pointer.

I didn't realise that rustc optimised that.

SimonSapin commented 4 years ago

It’s not an optimization. There isn’t an extra level of pointer indirection that was magically removed. It’s just what it means to have T= [u8] (note: not T = &[u8]) in NonNull<T> or *mut T or *const T or &T.

Wodann commented 4 years ago

Okay, I see now. Your linked slice_from_raw_parts illustrates this well:

pub const fn slice_from_raw_parts<T>(data: *const T, len: usize) -> *const [T] {
    unsafe { Repr { raw: FatPtr { data, len } }.rust }
}

The data is encoded directly in a *const [T]. This is then directly stored in a NonNull<[u8]>.

Thanks for bearing with me 😅

SimonSapin commented 4 years ago

(Note that using a union like slice_from_raw_parts does is equivalent to using transmute, but is more compatible with const fn.)

TimDiekmann commented 4 years ago

As we are on nightly and there will be another breaking change to the allocator api anyway (#58), I'd like to try NonNull<[u8]> in favor of MemoryBlock and make an upstream PR next week. To summarize the advantages:

The only thing we lose is #[repr(C)] as NonNull<T> is not repr(C). This may change in the future, but for now it's undecided if and how. Result is not repr(C) either, so one need some Rust code around it anyway to retrieve the result. I don't expect that we remove Result from the API. Also accessing len and ptr of NonNull<[T]> is a noop, which makes this argument negligible IMO.

SimonSapin commented 4 years ago

(NonNull is repr(transparent) so this is rather about the layout of wide pointers being unspecified. But I agree with the rest of the argument.)

Lokathor commented 4 years ago

reminder for the record: returning Option<NonNull<u8>> would be directly C compatible.

SimonSapin commented 4 years ago

That would be an option for APIs where no size is part of the return value, but https://github.com/rust-lang/wg-allocators/issues/17#issuecomment-585241852 decided to always return the usable size.

TimDiekmann commented 4 years ago

Also: (Allocation) Failure is not an Option :wink:

zakarumych commented 4 years ago

I wonder if &mut [MaybeUninit<u8>] was considered at some point as return type from allocation function. The main difference here is that NonNull<[u8]> can be dangling. While allocator cannot return dangling pointer.

SimonSapin commented 4 years ago

@zakarumych Closed issues are generally not a great place to ask a question since they’re considered resolved and not in need of attention anymore.

&mut [MaybeUninit<u8>] was discussed in https://github.com/rust-lang/wg-allocators/issues/65. It’s really two proposals: &mut instead of NonNull, and MaybeUninit<u8> instead of u8. The former has the problem that we’d need to pick a lifetime for that reference, and none is accurate since the actual life time of a heap allocation is dynamic and cannot be encoded statically in the borrow checked. MaybeUninit is being discussed in https://github.com/rust-lang/wg-allocators/issues/66.

zakarumych commented 4 years ago

@SimonSapin thanks for clarification. Sorry for disturbance.