Global allocator API changed

[phil-opp]

See rust-lang/rfcs#1974

Update: Build was fixed in #348. However, we still need to do some things:

• adjust the blog post (done in Update the “Kernel Heap” post to use new allocator API #367)
• backport the changes to all git tags
• maybe get rid of the hole_list_allocator and use LockedHeap directly (also in Update the “Kernel Heap” post to use new allocator API #367)

[rspencer01]

For blog post purposes, it might also be an idea to change the BumpAllocator.

[johanmon]

In this restructuring I was wondering if one should not rename the allocator. Instead of a naming it after the algorithm it should be named for what is it - the kernel allocator. One would then start by implementing the kernel_allocator as the bump_allocator. Then the kernel_allocator would be refined and using the linked_list_allocator but it would still be the kernel_allocator.

[toor]

I think it's necessary to distinguish between the libraries for learning purposes. @johanmon

[johanmon]

Agree that one should start to build a bump_allocator and to see that it is actually working. But instead of then start on another allocator one could instead refine the one that was built.

[johanmon]

Another thing - does not the HEAP_START and HEAP_SIZE belong in the kernel lib.rs rather than in the library allocator? Does it not make more sense that the kernel decides, where the heap should be allocated.

[phil-opp]

The heap start and end constants are a bit hacky and unsafe. They make it very easy to accidentally overlap the heap memory with other memory areas (e.g. if the kernel grows larger so that its content reach HEAP_START). It might be better to define them in the linker script or to dynamically choose a free memory area using the memory map.

[phil-opp]

But instead of then start on another allocator one could instead refine the one that was built.

The problem is that the linked_list_allocator has a lot of complexity around the edges, so explaining it in detail in the post is not possible. But we could try to find some middle ground. Some ideas:

• A linked list allocator that does not merge blocks. This will lead to much fragmentation eventually, but it's certainly better that not freeing memory at all.
• An allocator that uses discrete size classes, i.e. rounds the allocation size up to the next size class. This makes it easier to find a free block (it's the first block in the list corresponding to the size class).
  • We could extend this approach further by refilling the lists when they become empty. So if no free block is left for size class n, we allocate and split a larger block.
• A buddy allocator

[johanmon]

I agree that one should keep it simple; going in to all the different allocators pros and cons is not the target of the blog. The magic is getting things to work, not tuning memory usage. A linked list allocator that does not merge blocks should be simpler to build and could be described in detail in the blog. If one has this up and running it opens up the possibility to experiment with other algorithms.

[le-jzr]

Another possibility is a simple bitmap allocator. It's inefficient, but dead simple. Just scanning an array for long enough bit runs.

[le-jzr]

As an educational bonus, a bitmap allocator is excellent at demonstrating differences between first-fit/best-fit/next-fit strategies.

[johanmon]

@phil-opp Should I give rewriting the blog entry on the bump_allocator a try or would you rather take that yourself?

[phil-opp]

I think it's better if I do it myself, to keep the writing style consistent across the post. But thanks for the offer!

[johanmon]

perfectly understand

[phil-opp]

So I finally had some time to work on the blog post update. I plan to finish it over the weekend. Sorry for the long delay!

I decided to change it quite a bit. For example, there is no longer need for sub-crates in libs, since global allocators can be defined in the same crate now. Also, I made the bump allocator lock free instead of using a Mutex, which is not really necessary, but cool :). It shows that there are other ways to achieve thread safety apart of wrapping everything in a mutex.

@johanmon I hope that it's not too late to integrate these changes into your OS course, somehow they took me longer than expected.