Type aware allocators

[CasperN]

I don't know if the ship has sailed on the Allocator trait's API yet, but I think it is a good idea to have an allocate/deallocate variant that is parameterized by T. I'll just call them "Type aware allocators". There are a few security opportunities w.r.t. heap exploits and maybe performance ones too.

Implementations must be backwards compatible, which means if a pointer is allocated with T, deallocating with U where T and U have the same size and alignment must succeed, unless users opt into other behavior.

Benefits:

1. Allocations that contain secret material should be stored on separate pages. With ASLR and guard pages, its difficult for an attacker with a heap overflow to reliably find and exploit this material. Having T in the API lets libraries hint to a shared allocator to get this separate treatment. Currently, libraries containing secrets would have to manage their own allocator.

2. Similarly, an attacker with a heap overflow may want to exploit function pointers.

One mitigation employed by the Scudo hardened allocator involves "quarantining" free'd pointers and freeing them at a later point. This makes heap attacks less reliable too but kills memory locality: Imagine you're allocating and deallocating a string in a tight loop, tcmalloc and jemalloc will give you the same (hot) memory each time while quarantining forces you into something colder. So for performance reasons, this security feature is often disabled. In some sense, quarantining all pointers is overkill. Function pointers are more dangerous than, e.g., a vector of ints.

3. It might be a red flag if a program allocates a pointer and de-allocates it with a different type. This probably happens a lot already for existing code, but for new opt in types in completely safe code, this may point to malicious behavior and the allocator should terminate the program.

4. For performance reasons, it might be a good idea to put long lived shared data on different pages than hot, thread local data. This reason is a little iffy since a performance sensitive user should probably go with a locally scoped allocator to keep its memory nearby.

5. More performance reasons: Slab allocators

[CasperN]

Chrome's PartitionAlloc separates strings: https://blog.chromium.org/2021/04/efficient-and-safe-allocations-everywhere.html

https://chromium.googlesource.com/chromium/src/+/dcc13470a/third_party/WebKit/Source/wtf/PartitionAlloc.md#partitions-and-buckets

[CeleritasCelery]

I can certainly see the benefit of type of allocators for different types. But monomorphizing every allocation site seems quite expensive. With the allocator API you can pass different allocators to different allocatable functions, so there would be no need to make it generic, at least not that I can see.

[CasperN]

But monomorphizing every allocation site seems quite expensive

I agree that it seems to be a potentially expensive compile time cost, and should be kept in mind when exploring this direction.

My intuition is that a similar cost is already paid by Layout::new() which is generic over T and presumably also present at most/all allocation sites. I'd expect the additional cost to be comparable. Additionally, implementers can be recommended to keep allocate<T>optimizable to a single call to a more specific allocator function. Basically use T and const functions to decide on the more specific function, the const function and branching will be optimized away.

With the allocator API you can pass different allocators to different allocatable functions, so there would be no need to make it generic, at least not that I can see.

While its true that programmers can manage multiple allocators, I do not think that is the best way to solve the above class of problems. It is not possible to enforce for large groups of programmers over a long period of time. It is not easy to do backwards compatibly if there is a new security/performance technology.

There needs to be a mechanism for a type to choose allowable allocators for its containers or allocators need to be aware of the types it consumes. The latter is better because the cost is put on the allocator writer rather than the allocator user.

[CeleritasCelery]

Touché. Those are all good points. I am convinced so long as the generic overhead is not too high.

[scottmcm]

I think this would prevent Vec::from_raw_parts conversions that are legal today, right? (Or, at least it would if the global allocator could do this. I suppose that we could make Vec::from_raw_parts_in also require that the type is an exact match, since it's not stable yet, but I don't think that's desirable.)

The C++ part of my brain says that the way to meet the desire here (assuming for now it's worth doing) is to specialize the choice of allocator, not specialize the allocator. So, for example, it could be Vec<T, A = <T as PickDefaultAllocator>::Type> instead of Vec<T, A = GlobalAllocator>. That way allocators still don't need to know what type they're allocating and once you're using a specific allocator the rebuild-for-different-but-layout-compatible-type still works.

[Ericson2314]

There has been work with single type "slab allocators" of this sort before. CC @joshlf

[CasperN]

I think this would prevent Vec::from_raw_parts conversions that are legal today, right?

@scottmcm

We must still keep the contract of "allocate and deallocate with the same size and alignment" for backwards compatibility, so no. Idea 3 above should not be enforced on existing types. I think a fast deallocate path may assume that allocate used the same type but it should always fail back to a slower path if that is not true, except if a programmer opted into specific behavior. E.g. Foo: DeallocatedTypeMatchesAllocatedTypeOrAbort

The C++ part of my brain says that the way to meet the desire here (assuming for now it's worth doing) is to specialize the choice of allocator, not specialize the allocator. So, for example, it could be Vec<T, A = ::Type> instead of Vec<T, A = GlobalAllocator>. That way allocators still don't need to know what type they're allocating and once you're using a specific allocator the rebuild-for-different-but-layout-compatible-type still works.

I'm not sure if this will survive a transformation into/from raw parts unless the programmer carries <T as PickDefaultAllocator>::Type themself, or if they transmute T into U where <T as PickDefaultAllocator>::Type == <U as PickDefaultAllocator>::Type. So I don't think that this is backwards compatible either.

There has been work with single type "slab allocators" of this sort before. CC @joshlf

@Ericson2314 thanks that's a way better performance reason than the one I came up with. I added that as the fifth on the list above.

Looks like the prior art APIs include kmalloc and kmem_cache_alloc which both provide more data than simply layout. Attaching static data to T via traits would work. However, I'm not familiar with kernel allocation patterns. I doubt that dynamic allocation metadata would be generalizable.

[CasperN]

I found this earlier issue that discussed a variant of this idea: #27

@Avi-D-coder and @gnzlbg seemed like they gave it some thought.

@gnzlbg, I'm curious what do you think of the use cases laid out here?

[CasperN]

Actually parameterizing with T will break is the Allocator trait being object safe which was asked for in #83. Assuming that's a bigger priority, this effort needs a different mechanism for passing metadata, i.e. add more fields to Layout. Layout::new is parameterized by T so type specific data can be added unobtrusively. The simplest mechanism is to add TypeId.

[cmazakas]

C++ has typed Allocators and historically, they were a mistake.

They bring more complexity than they save in terms of safety.

Rust's decision to just take a Layout and return a NonNull<[u8]> is the correct one.

[CasperN]

C++ has typed Allocators and historically, they were a mistake. They bring more complexity than they save in terms of safety.

@LeonineKing1199 Can you elaborate on what you think these mistakes and complexities are?

[Lokathor]

well it would probably break the bytemuck try_cast_vec function, for one.

[CasperN]

@Lokathor, backwards compatibility is required so of course the contract should be, 'deallocation with a different type than allocated must not fail if the size and alignment match'. I think I alluded to this in point 3 originally and also in response to @scottmcm. I edited the top comment to reiterate the point explicitly and at the top. Let me know if that is clearer.

[petertodd]

Is there an example of a type aware allocator where something other than size and alignment would be relevant for deallocation? On October 24, 2021 6:02:33 PM EDT, Casper ***@***.***> wrote: ***@***.***, backwards compatibility is required so of course the contract should be, 'deallocation with a different type than allocated must not fail if the size and alignment match'. I think I alluded to this in point 3 originally and also in response to @scottmcm. I edited the top comment to reiterate the point explicitly and at the top. Let me know if that is clearer.

…

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: #91 (comment)

[thomcc]

One that uses the typeid as a key to figure out an allocation pool.

[petertodd]

Thanks for the example!

…

On October 24, 2021 6:21:06 PM EDT, Thom Chiovoloni ***@***.***> wrote: One that uses the typeid as a key to figure out an allocation pool. -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #91 (comment)

[cmazakas]

@LeonineKing1199 Can you elaborate on what you think these mistakes and complexities are?

C++ has "type-aware Allocators".

In general, this is a mistake because it introduces the need for a rebind mechanism. For example, you as a user may have an Allocator<i32> but when you pass this to a linked list implementation, the list must allocate nodes that contain pointers, ints, etc.

To do this, the Allocator must be "rebind-able" from i32 to Node<i32>.

In general, a rebinding mechanism only adds extra complexity when in Rust, there's already a simple API for creating the correct layouts, i.e. std::alloc::Layout::new::<i32>().

C++ had to support type-aware Allocators because stdlib containers would default construct elements so even element construction became a part of the Allocator API. Rust's stdlib seems to deliberately avoid this issue.

From my experience, an Allocator that simply returns a pointer to an array of bytes and deallocates an array of bytes using user-provided layouts is the most simple and straight-forward implementation from which higher-level constructs can be built upon.

The brutal simplicity of Rust's Allocators is what makes them so attractive to me.

[CasperN]

@LeonineKing1199 so I think the rebind challenge does not apply since I'm not proposing that allocators should be limited to producing allocations of a single type. I am proposing that allocators get extra information about types being (de)allocated. The allocators are still general purpose and are able to both allocate i32 and Node<i32> without needing to rebind.

[cmazakas]

Can I see some pseudocode?

[CasperN]

impl Layout {
  fn new<T>() -> Self {
    Self {
      size: mem::sizeof::<T>(),
      align: mem::alignof::<T>(),
      typeid: any::typeid::<T>()  // Really this just has to be extensible metadata, not necessarily TypeId
    }
  }
}
impl Allocate for MyAllocator {
  fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
    // Choose suballocator based on type information.
    match self.choose_suballocator(layout.typeid()) {
      SlabAllocator => self.slab_allocator.allocate(layout),
      LikesToRealloc => self.realloc_optimized_allocator.allocate(layout),
      ExtraSecret => self.secret_allocator.allocate(layout),
      Normal => self.default_allocator.allocate(layout),
    }
  }
  fn deallocate(&self, ptr: *mut u8, layout: Layout) {
    match self.choose_suballocator(layout.typeid) {
      // Fast path: Try to deallocate with the same suballocator as you would allocate with given the type hint.
    }
    // If that does not work try deallocating with every suballocator
    // if ptr is in not allocated anywhere...
    abort!()
  }
}

[cmazakas]

Ah, this looks you're after a more generic way of attaching metadata to a layout kind of struct.

That's an interesting idea.

I feel like it should theoretically live at a higher abstraction level, no?

As it is now, Allocators could be a low-level trait that really just handle allocate and deallocate calls with something higher up the abstraction stack deciding which allocator should be used based on pertinent metadata.

[Lokathor]

@CasperN big and bold at the top helps, yes :3

[CasperN]

I feel like it should theoretically live at a higher abstraction level, no?

Potentially: The reason I think its a good idea to focus on Layout, Allocator, or GlobalAlloc, is to enable allocator development in an existing codebase without having to touch every allocation site. This is, imo, a critical requirement. Any API in the allocation path underneath Vec, Box, and std::collections could work. However, I am not aware of another suitable abstraction layer.

[scottmcm]

impl Allocate for MyAllocator {
  fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
    // Choose suballocator based on type information.
    match self.choose_suballocator(layout.typeid()) {

This is, basically, wanna-be specialization.

That's why I mentioned specialization in the default type parameter as a way to address

without having to touch every allocation site

TBH, I also think that the allocator itself needing to know about your business logic classes is really weird from a layering perspective. Whereas a struct adding a specialization for "hey, I suggest using this allocator with me" seems more reasonable. Though it may cause a bunch of semver hazards from adding them.

(Although I'm still skeptical of somehow specializing an allocator for something like u8 to make SecureString work. struct SecureString(String<SecureAlloc>); feels far more likely to me.)

[CasperN]

TBH, I also think that the allocator itself needing to know about your business logic classes is really weird from a layering perspective. Whereas a struct adding a specialization for "hey, I suggest using this allocator with me" seems more reasonable.

Yeah, this is an interesting design question and I think the decision ultimately comes down to scale.

In a small codebase/team I agree its reasonable and better to have types choose their allocator everywhere. Especially for readability - this strategy does not have the same spooky action at a distance.

For what its worth, this type-aware-allocators proposal does not rule out the types-choose-allocators approach. It just enables more options.

In a large codebase/team I think types-choose-allocators does not scale too well. PartitionAlloc isolates strings and some other types because they're prone to exploitation. You'd need tooling and training to ban the native type in favor of SecureString. Maybe that's acceptable for a handful of types but the list will grow as the codebase develops. The number of structs/enums/fns to update will obviously grow too so keeping up with allocator advancements is in some sense quadratically hard.

I also think that the allocator itself needing to know about your business logic classes is really weird from a layering perspective.

I agree but I don't think security and performance features are "business logic" per se. Ideally business logic can be separated and this is actually easier if the business logic types don't mention the allocator. Granted, the allocator does become business logic for some teams when the performance requirements get steep enough. Those teams should engineer their allocation patterns carefully. However, many (most?) teams don't reach that point and will use default types and allocators (or even slow languages) because developer velocity matters more. But one allocator team might care that hundreds of teams could be using their allocator better. Their work will be easier and less intrusive with type-aware-allocators.

So yea, @scottmcm, I think I see your point and agree types-choosing-allocators is clearer for small projects however I think type-aware-allocators is more manageable at scale.

[scottmcm]

PartitionAlloc isolates strings and some other types because they're prone to exploitation.

I'm still puzzled by this one. String is just a wrapper on Vec<u8, A>, which is itself a wrapper on RawVec<u8, A>, which allocates via match Layout::array::<u8>(capacity). So I don't see how a type-aware allocator would even be able to detect it's a String at the outside -- as far as the allocator can tell, it might just be a BufWriter.

[CasperN]

Okay so I went and read their source: https://chromium.googlesource.com/chromium/blink/+/refs/heads/main/Source/wtf

The TL; DR is that they define their own data-structures like vector, string and hashmap in terms of their own allocator. So instead of using std::vector you'd use wtf::vector which is, erm, not super satisfying.

So I don't see how a type-aware allocator would even be able to detect it's a String at the outside -- as far as the allocator can tell, it might just be a BufWriter.

Yeah, I agree that would be the case so type-ids won't provide that fine grained metadata in these cases. That is sufficient if you want to achieve something like PartitionAlloc's BufferPartition since they isolate vectors and maps with strings... but its not ideal.

[thomcc]

For these sorts of things I suspect you want to customize the allocator based on the type doing the allocation rather than the type being allocated, e.g. the allocator should know that it's allocating from a String/Vec<T>/HashMap<K,V>/... rather than the type of the underlying allocation.

There are reasons this is a pain, though, and I don't know exactly what trying to express this in a Rust API looks like.

My hunch is solving this problem perfectly might break object safety, or at least, the ability to use runtime polymorphism with the allocator trait. (Admittedly this is fairly poorly supported now¹, so maybe it's not worth worrying about here)

The TL; DR is that they define their own data-structures like vector, string and hashmap in terms of their own allocator

I think this might be neither here nor there — it would probably happen regardless even if C++'s std::allocator were much better. (That's not to say the type awareness is a bad idea, I don't know).

Footnotes

1. You end up with problems like "what allocator should something like Rc<dyn Allocator, ???> use", as just the tip of the iceberg... ↩