Tiered allocators

[hawkw]

As I rewrite the kernel memory allocator, I should think about incorporating some notion of tiering. We could start with a simple bump pointer allocator early in the init process, and use that for allocating heap objects that live as long as the kernel does (and will never need to be deallocated), and wait to set up the buddy-block allocator until after we've remapped the kernel into the higher address space (since the buddy allocator seems to break occasionally when our paging setup is incomplete).

There's precedent for this sort of tiered allocation scheme; the Linux kernel starts out with a bump pointer allocator at boot time.

We could use an enum to encode one-way allocator state transitions in the type system, so that once the system allocator has been upgraded to the buddy-block allocator, there's no way for it to "go back".

In addition to tiering the system allocator for Rust collections, we should be able to compose slab allocators on top of the main allocator, for constructing specific object types. We should use these slab allocators for kernel objects that we need to allocate a large number of.

[hawkw]

Alternative: placement expressions

Another option is to look into using the placement expressions feature (rust-lang/rust#27779) to control where objects are allocated. Rather than making the bump pointer allocator a system allocator that links with the allocator lang items, we could explicitly use it to allocate objects using placement expressions.

Pros & Cons

• Makes where objects are allocated explicit at the call site (:thumbsup:)
  • rather than just using heap-allocated objects and assuming that the allocator crate will put them in the right place, using placement expressions makes allocations explicit in the code that does the allocating. this would help make our code easier to read and conveys more intent.
• Getting to use a cool new language feature (:thumbsup:)
• Having to deal with an unstable new API (:thumbsdown:)
  • This is the flip side of the previous point
• Wouldn't have to mutate a global static as much (:thumbsup:)

Even if we do still use tiered allocators for the system allocator, we might still want to look into using placement expressions for the kernel slab allocators...

More information

• https://www.reddit.com/r/rust/comments/3r8vqq/how_to_do_placement_allocation/
• RFC for placement-in syntax, e.g. in PLACE { BLOCK } vs PLACE <- EXPR. (See Place left arrow syntax (place <- expr) rust-lang/rfcs#1228 )
• RFC for protocol interface, e.g. passing &mut self vs self for the Placer::make_place (Placement protocol should not consume Placer rust-lang/rfcs#1286).