-
Notifications
You must be signed in to change notification settings - Fork 9
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Pre-proposal: Type-based allocator selection #81
Comments
I think this proposal (#79) will solve your issues. Basically it replaces the |
The basic problem this proposal aims to solve is relieving the programmer of the need to explicitly opt in to an alternative allocator at every allocation site for some set of types. I could be missing something, but I'm not sure how #79 would do that. Afaict #79 would add a generic backing store field to containers, but still requires the use of |
@rinon how would this interact with generic code? Because it seems to mean that anyone who assumes that edit: if you really needed a easy way to sugar over |
Yes, implementing Ideally I'd like the default allocator type of struct Box<T: TypeAllocated, A: AllocRef = <T as TypeAllocated>::TypeAllocator>;
// requires specialization to allow users to override this
impl<T> TypeAllocated for T {
type TypeAllocator = Global;
}
Yeah, considered that. Two major issues, from my perspective:
|
I don't think this will work. Assuming we have specialization for overwriting |
Yes, that would be the idea, that the crate that owns T should know where it needs to be allocated. Do you think that's too much of a limitation? For the use cases I'm looking at, I think it would be ok. The allocation behavior is determined by the type, rather than the code location where that type is being allocated. Of course, this won't always be the case, so in cases where the allocation site needs to control the allocator we always have the current allocator API. |
To be honest, I think it is. Since these structs are defined in the standard library, I don't feel such a limitation should exist. Especially since this is only a specific use case. I still believe that #79 can solve this problem more elegantly. I guess it will not be possible to change |
If security is your biggest concern, then I would create a newtype wrapper around Second, I don't think we can add a specialization based default allocator, because that can't be retrofitted on, But in any case, |
Fair, but I think the restriction makes sense. The "owner" of a type (its crate) could declare that it should be allocated with a certain allocator by default, probably guarded by a feature flag. This would push consumers of that type to use the allocator that was selected, rather than a generic other allocator. If you want to do this for a foreign type, just make a local newtype.
I'm fairly certain it is possible to change
That sort of works (as long as you duplicate the entire
Why not? I added the
I'm not proposing that at all. The layout of |
Given that custom allocators are still on nightly, I don't think many crates actually support it well (if at all). So... I don't think that's a great argument. You can still add some API for accessing external crates onto your newtype, and that would ease the boilerplate. The only thing big downside I see is adding the various traits that are on
Ok, I think I just missed that, my bad.
Adding an allocator that is non-zero sized or has an alignment larger than struct Box<T: ?Sized, A: Allocator> {
ptr: NonNull<T>,
allocator: A,
} (ignoring minor details that don't alter the layout) |
What I was hoping for was to be able to change allocation behavior in external crates as long as they assumed the default allocator. It's looking like that's tricky due to the layout issues you point out.
Sorry I've been misunderstanding, my bad! I somehow missed that we're actually adding the allocator to the Box structure rather than just tracking the type of the allocator in the type system. Yeah, what I'm proposing would only work for zero-sized allocators then. I don't think we have a good way to constrain that, is there? |
No, there isn't a way to constrain it to only zero sized types, until we get const generics |
TL;DR: Proposing the addition of a trait that indicates the default allocator for a type to the compiler for use in
Box
, etc. This would allow programmers to use different allocators on a per-type basis, rather than requiring the use ofBox::new_in()
at every allocation site.On a personal note, I've been following the alloc-wg work with great interest, and I'd love to help out if I can.
Background
Currently, the interface to allocate using a custom allocator looks like:
This API allows the programmer to specify a particular allocator for a heap allocation at the allocation site. The allocator itself does not know what type it is allocating, only the type’s size and alignment, so it cannot make allocation decisions based on types. There was a previous pre-proposal to add type information to AllocRef, but it did not get very far, partially due to inherent limitations in the Rust TypeId system.
Issues with Segmented Heaps
For our use case, we want to use multiple allocators and constrain some types to be only allocatable using a specific allocator. This problem consists of two parts: 1) allocating instances of a type in a specific allocator, and 2) preventing allocation of that type with any other allocator.
The first constraint, allocating instances of a type in a specific allocator, is viable although verbose, given the current API. For example, we can create a newtype wrapper around
Box
that only accepts types that implement aCustomAllocated
trait which will be allocated using the custom allocator:Unfortunately, we don’t know of a way to prevent a type from being allocated using a different allocator from the specific one we want. If allocators had access to type information, we could dispatch to the correct heap segment based on type inside a single allocator. However, as discussed above, there doesn’t seem to be a good way to get type information passed to the allocator. Even if we can’t prevent allocation to the “wrong” allocator, we would at least like to be able to control the default allocator for a type, as this will minimize the possibility of allocating using the wrong allocator.
Use Cases
We know of the following use cases that would benefit from the ability to select allocators based on type information:
Allocation into different sets of physical memory. The memory attached to the CPU has different characteristics (bandwidth, latency, etc) from memory on an accelerator such as a graphics card. Type-based allocation would let the programmer specify that texture objects, for instance, should be allocated in graphics memory, without requiring the programmer to specify the graphics allocator at each allocation site.
Larger multiprocessor systems have non-uniform memory access times (NUMA) meaning that the time to access a given memory location depends on the distance between the processor and the memory module. In this case, type-based allocation let’s programmers express NUMA-aware optimizations via the type system (See #29). The same goes for systems that can access remote memory (i.e., another host) via remote DMA.
Allocation into segmented memory domains. Currently, memory is generally segmented into kernel memory and per-process memory, subject to memory protection so that each domain cannot access others. These memory access permissions are enforced via the primary and secondary address translation mechanisms in processors with memory management units. However, modern processors support fast switching of access permissions inside a single process via features such as memory protection keys (Intel) and memory domains (ARM). We are using these primitives to put memory belonging to each library in a separate memory domain and use types to express which memory objects may be shared across domains. This has security and reliability benefits when a process contains a mix of safe (Rust) and unsafe (C/C++) code. This use case is our strongest motivator since inadvertent allocation into the wrong domain is far less likely, in our experience, when types can be used to constrain the allocation domain instead of correctly using
Box::new_in
at each allocation site.For a concrete example, the RedLeaf research operating system uses memory domains to separate memory allocations belonging to different components (such as device drivers and OS services) for fault tolerance. This design already includes a concept of exchangeable memory which are types that may be moved across memory domains – a concept which can be implemented more cleanly with support for type-based allocation according to the authors of the RedLeaf papers. See https://www.usenix.org/system/files/osdi20-narayanan_vikram.pdf.
Performance optimization. Being able to distinguish allocated and deallocated regions of memory by type allows for increased performance gains, orthogonal to other performance-enhancing allocation techniques such as pooling (this was also noted in the literature). Type-based allocation further aids the construction of object caches, which can significantly reduce allocation overhead in heavy workload scenarios (e.g., in web browsers) and garbage collectors (see the aforementioned pre-proposal).
While region allocation can be approximated by simply using allocation sizes, this is less efficient as different but identically sized structures may have different access patterns. In addition, mixing types of the same size in the same region is less secure against memory corruption resulting in type confusion.
Proposed Solution
We propose defining a new trait, e.g.,
TypeAllocated
, that the compiler will use to select a default allocator for certain types. When a type implements this trait, the compiler will use the associated allocator to allocate boxed objects of this type instead of the default global allocator. By itself, this change will not prevent the type from being allocated via a custom allocator if it is allocated using, e.g.,Box::new_in()
. However, selecting a default allocator for a type handles the majority of common cases and allows a type’s allocator to be changed in one place without having to change it at every allocation site.Example:
In order to use an allocator in this way, the compiler needs to be able to create an instance of the default allocator when constructing a box. This is handled by requiring
Default
on the type bound ofTypeAllocator
inTypeAllocated
. The compiler can use<T as TypeAllocated>::TypeAllocator::default()
to construct an instance of the allocatorPotential Issues
The type of Box is currently
Box<T, A: Allocator>
. Thus, changing the implementation ofTypeAllocated
for a type would change the type signature ofBox::new()
for that type. That may not be an issue, but changing an impl in one place and breaking types may not be ideal. Unfortunately, that’s also the benefit of this approach, so that will need to be evaluated.[edit] We can possibly deal with this issue by changing the definition of
Box
to default to theTypeAllocator
allocator and use a blanket implementation ofTypeAllocated
to remain backwards compatible:Implementing
TypeAllocated
doesn’t prevent a type from being allocated with a non-default allocator. This could be desirable in order to prevent bugs where types are allocated using an unexpected allocator. One option would be to disableBox::new_in
if type-based allocation is requested for the object type.Alternatives
It would be possible to implement this via a macro at call sites and dispatch to the correct
Box::new_in()
variant. However, this still requires the programmer to opt in to the special allocation at every allocation site, something which we want to avoid. In addition, an allocation-site macro would not allow a crate to control the allocator for its own types in a foreign crate, although this is unlikely to work unless the default allocator in the signature ofBox::new()
is controlled byTypeAllocated
.I've prototyped a simpler version of this proposal in the compiler, which passes an additional parameter to the global allocator indicating the memory domain for the allocation based on a trait implementation for the type being allocated. This is somewhat similar to #27, but passing a memory domain id instead of the type, thus avoiding some of the issues around TypeId. However, this approach seems strictly less flexible than the approach proposed above, so I don't think it's a great solution.
The text was updated successfully, but these errors were encountered: