Allocator Designs | Hacker News Reader

Allocator Designs

os.phil-opp.com

141 pointszbentley9 comments

> To prevent integer overflow on large allocations, we use the checked_add method. If the resulting end address of the allocation is larger than the end address of the heap, we return a null pointer to signal an out-of-memory situation.

The overflow scenario should be treated the same as the out-of-memory scenario and also return null. The hypothetical result of the addition would always be larger than `heap_end`.

Suppose you allocate heap at the far end of the address space, then all out-of-memory events suddenly become overflows.

> The main limitation of a bump allocator is that it can only reuse deallocated memory after all allocations have been freed.

It can do better, in `dealloc` you can use `ptr` and `layout` to check if the allocation is at the end of the allocated region. If it is, `bump.next` can be reduced by `layout.size()`. This is optimal for lifo/stack style allocation patterns.

Alignment complicates implementation since precise information on the previous value of `bump.next` is lost. There are way to solve this, for example by always padding to some maximum alignment, or writing the padding size in the padding.

> The overflow scenario should be treated the same as the out-of-memory scenario and also return null.

Good point! I'll prepare an update to fix this.

> It can do better, in `dealloc` you can use `ptr` and `layout` to check if the allocation is at the end of the allocated region. If it is, `bump.next` can be reduced by `layout.size()`. This is optimal for lifo/stack style allocation patterns.

You're right. I already created a PR [1] for this shortly after publishing the article, but it seems like I forgot to merge it. There should be now an additional "Fixing the Test?" section that talks about freeing the last allocation.

[1]: https://github.com/phil-opp/blog_os/pull/722

> I'll prepare an update to fix this.

Update in https://github.com/phil-opp/blog_os/pull/738 and https://github.com/phil-opp/blog_os/pull/739

Would the author mind commenting on how the diagrams were generated? They were very clear and useful.

Thanks! I created them using draw.io (https://about.draw.io/).

Almost half of the article is dedicated to fighting Rust. Rust compiler doesn't permit this, doesn't permit that... May the authors of Rust excuse me, but that language is as much not fun to program in as it is thought-out and well-designed!

On the other hand, these strict requirements make sure that the global allocator is thread-safe. Also, I only count two compiler errors mentioned in this post and both have a valid reason (you can't modify values behind an immutable reference; you can't implement traits for types of other crates).

Both of them are invalid. What if you want a single-threaded allocator without the mutex overhead? And forbidding implementing traits for some types is just arbitrary stupidity. Developers don't need a nanny compiler to tell them which types they can or can't extend. Orphan instances are the solution in some cases.

For single threaded programs you can e.g. use a Mutex implementation that only disables interrupts for the critical section (https://docs.rust-embedded.org/book/concurrency/#mutexes). Rust does not forbid you from doing these potentially memory unsafe things, it just requires you to use an `unsafe` block for this.

The reason for forbidding these trait implementations is compatibility. For example, the dependency might add an implementation for the trait at some point, so that there would suddenly be conflicting implementations after a semver-compatible update. You can still implement the trait by creating a wrapper type.

Reply on news.ycombinator.com