Allocator Designs

[utterances-bot]

This is a general purpose comment thread for the Allocator Designs post.

[senseiod]

Great!

[MikailBag]

Thanks for the post! As usual, it is very interesting!

Since the Heap type of the linked_list_allocator crate does not implement GlobalAlloc (as it's not possible without locking).

looks like typo

[engstad]

The align_up function could be improved by removing the if-test. Notice that if addr is already aligned, then (addr + align - 1) / align * align equals addr, whereas if it is not, then it equals (addr + align)/ align*align or addr/align*align + align or align_down(addr) + align.

fn align_up(addr: usize, align: usize) -> usize {
    (addr + align - 1) / align * align;
}

Or, if you use powers of two as argument instead:

fn align_up_pow2(addr: usize, align_pow2: usize) -> usize {
    (addr + align - 1) >> align_pow2 << align_pow2
}

[engstad]

I should mention that when using a BumpAllocator, that you could have extended the functionality a bit.

First, while you normally can't delete entries from the allocator, you can delete the last entry. In other words, if you know what you are doing, you can allow a reset() function that takes the address of an allocation resetting the allocation to that point. Highly dangerous if you don't know what is going on, but you can safeguard it somewhat if you know that it was the last allocation. This makes it a "stack" allocator.

Second, it is common practice to allocate from both the front and the back of the memory region. This is useful where some of the allocations are temporary. You put temporary allocations at the end, while longer-lasting allocation are put in the front.

Anyway, both these methods are quite dangerous, but in terms of raw speed, there's no comparison.

[phil-opp]

@engstad

Thanks for your comments!

The align_up function could be improved by removing the if-test.

Good point! I'll extend that section. The fastest variant I'm aware of is relying on the optimized align_offset implementation of Rust's standard library:

#[no_mangle]
fn align_up(addr: usize, align: usize) -> usize {
    let offset = (addr as *const u8).align_offset(align);
    addr + offset
}

First, while you normally can't delete entries from the allocator, you can delete the last entry. In other words, if you know what you are doing, you can allow a reset() function that takes the address of an allocation resetting the allocation to that point

One could also check in deallocate whether the end address of the freed allocation equals next. However, this way we could not recover inserted allocation bytes.

Second, it is common practice to allocate from both the front and the back of the memory region. This is useful where some of the allocations are temporary. You put temporary allocations at the end, while longer-lasting allocation are put in the front.

Good point! While this is difficult to implement for a global allocator, it definitely works for manual allocations.

I try to update the bump allocator discussion section with both your suggestions.

[phil-opp]

@engstad I prepared two updates for the post related to your comments. #721 adds more variants to implement align_up and shortly discusses their performance. #722 outlines the two bump allocator improvements you mentioned. What do you think about the changes?

[phil-opp]

@senseiod Thanks!

[phil-opp]

@MikailBag Thank you! Could you maybe clarify what the typo is? I don't see it right now…

[amosonn]

Nice comparison, thanks!

For more on bump allocation, see this post (in Rust, even):
https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html
To summarize, his rounding method is:
(size + align - 1) & !(align - 1)
(which relies on align being a power of 2 of course); and he comments that allocation arithmetic should be checked for overflows (which is the case for all allocators), and that then bumping from the end is more performant.

Also small typo in the beginning:
"This complexity is often undesired [...]"
(the "is" is missing).

[phil-opp]

@amosonn Thanks for you comment!

For more on bump allocation, see this post (in Rust, even):
https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html

I already link this post in the Dicussion section as "can be optimized to just a few assembly operations". I deliberatly decided against bumping from the end because the intention of the post is to explain a basic implementation, not to maximally optimize it. Regarding the alignment function: I think the align_offset function from the standard library should still be faster, given how optimized it is (see rust-lang/rust#50319).

allocation arithmetic should be checked for overflows (which is the case for all allocators)

Good point! I'll prepare a PR to fix this.

Also small typo in the beginning:

Thanks! Fixed in 4b8c902.

[phil-opp]

@amosonn

allocation arithmetic should be checked for overflows (which is the case for all allocators)

Good point! I'll prepare a PR to fix this.

I filed pull requests #726 and #727.

[amosonn]

Ah sorry, I missed the link :).

Regarding the various alignment implementations: align_offset does something stronger: it checks how many elements of an arbitrary size (mem::size_of::<T>()) should be added to align. In this case, you only need to compute this for stride 1, which devolves in that implementaion to something quite similar to the method above (but with a branch for already aligned pointers). Most of the complexity in that method is for computing for "stranger" sizes.

[phil-opp]

Thanks for investigating! I'll update #721 to use the (size + align - 1) & !(align - 1) method.

[Menschenkindlein]

In the code for LinkedListAllocator, self.inner.lock() => self.lock()

[phil-opp]

@Menschenkindlein Thanks! Fixed in 00fedc8 and 670ac60.

[diminishedprime]

First off, thanks for the excellent series, it's been extremely interesting to go through!

Just a small note, if you skip the implementation of the linked list allocator, you won't already have:

#![feature(const_fn)]

in your lib.rs. Just something I ran into.

[phil-opp]

@diminishedprime Thanks for reporting! I pushed 10d84fa to fix this issue.

[jiayihu]

As small note, list_index() should be FixedSizeBlockAllocator::list_index in the GlobalAlloc implementation of FixedSizeBlockAllocator

[phil-opp]

@jiayihu Sorry for the late reply!

As small note, list_index() should be FixedSizeBlockAllocator::list_index in the GlobalAlloc implementation of FixedSizeBlockAllocator

This depends on whether you declare the list_index function inside an impl FixedSizeBlockAllocator block or as a normal independent function. I implemented it as a independent function in this post, but putting it in the impl block is fine too of course.

See:

blog_os/src/allocator/fixed_size_block.rs

Lines 14 to 20 in ca3dfc7

	/// Choose an appropriate block size for the given layout.
	///
	/// Returns an index into the `BLOCK_SIZES` array.
	fn list_index(layout: &Layout) -> Option<usize> {
	let required_block_size = layout.size().max(layout.align());
	BLOCK_SIZES.iter().position(|&s| s >= required_block_size)
	}

[Sk3pz]

I found an issue with the allocators which was caused by using a mutable reference in a constant function (both in linked list allocator and in fixed size allocator), and removing that caused the issue calls in statics are limited to constant functions, tuple structs and tuple variants. The solution to this issue for anybody coming across this is to go to lib.rs and add #![feature(const_mut_refs)] to allow for mutable references in constant functions! (I am not sure this is the best way of doing it, but its what I did!)

[phil-opp]

@DeathBySpork Thanks for sharing your problem and solution.

Yes, adding #![feature(const_mut_refs)] is the recommend way of doing it, and also mentioned in the post:

In order to get it to compile, we need to add #![feature(const_mut_refs)] to the beginning of our lib.rs.

If you haven't done so already for the LinkedListAllocator implementation, you also need to add #![feature(const_mut_refs)] to the beginning of your lib.rs.

(See https://os.phil-opp.com/allocator-designs/#the-allocator-type and https://os.phil-opp.com/allocator-designs/#the-allocator-type-1)

[Sk3pz]

ah, I guess I didnt notice the change, I am sorry!

[phil-opp]

@DeathBySpork No worries, thanks for reporting your problems!

[Ananta98]

I still got error "calls in statics are limited to constant functions, tuple structs and tuple variants". I've add #![feature(const_in_array_repeat_expressions)] and #![feature(const_mut_refs)] in main.rs but still got error how to solve it ? My Code in https://github.com/Ananta98/PetraOS. Thank you.

[phil-opp]

@Ananta98 Looks like you forgot to make your Locked::new function a const fn:

diff --git a/src/mm/allocator.rs b/src/mm/allocator.rs
index 1ee24e3..8b911b1 100644
--- a/src/mm/allocator.rs
+++ b/src/mm/allocator.rs
@@ -15,7 +15,7 @@ pub struct Locked<A> {
 }
 
 impl<A> Locked<A> {
-    pub fn new(inner : A) -> Self {
+    pub const fn new(inner : A) -> Self {
         Locked {
             inner : Mutex::new(inner),
         }

After this change, it works for me.

[Ananta98]

Thank you @phil-opp it works now. sorry this is human fault.

[phil-opp]

Great to hear that! No worries, I'm happy to help.

[abesto]

Thank you so much for your work on this post series and the supporting crates! It's been extremely educational, following along.

I'm either confused, or this is input: the below asserts in the fixed block allocator

// verify that block has size and alignment required for storing node
assert!(mem::size_of::<ListNode>() <= BLOCK_SIZES[index]);
assert!(mem::align_of::<ListNode>() <= BLOCK_SIZES[index]);

seem like they'll never be useful.

• mem::align_of::<ListNode>() is constant
• mem::size_of::<ListNode>() is constant
• min(BLOCK_SIZES) is constant

If I'm right, then we run these assertions each time we deallocate memory, paying runtime cost for no value, I think?

There is a useful assertion to be made (once, maybe in init): that even the smallest block size has room for ListNode.

[seewishnew]

Agreed, the min BLOCK_SIZE should start at max(mem::align_of::<ListNode>(), mem::size_of::<ListNode>()), which should be 16 bytes in x86_64. I also believe it makes more sense to add alignment checks during dealloc for ptr so that we end up panicking at an assert as opposed to an internal ptr.write call.

[seewishnew]

Correction, the ListNode in fixed_size_block.rs should only need 8 bytes for both size and alignment. This goes in-hand with the current min size of BLOCK_SIZES.

However, it is interesting to note that we are only adding blocks to the list_heads during dealloc from blocks originally formed from the fallback allocator, and the linked_list_allocator crate has a minimum Hole size of 16 bytes, at least in x86-64.

So even though we currently have a BLOCK_SIZE[0] = 8, during dealloc for such small blocks, in reality we will be adding 16-byte blocks to list_heads[0] and use them only for 8 bytes or fewer, leading to over 50% wasted space for this bucket, on average. This seems to be an implicit price we might unconsciously have to pay--this could probably be mentioned as another point under discussions.

As a test, I found that trying to allocate some u64 on the heap gives us exactly this 50% efficiency:

// in tests/allocation_overhead.rs
#[test_case]
fn overhead_test_pass() {
    // Even though 8-byte blocks seem to be supported, the real
    // minimum is 16 bytes

    // We have 50% overhead, so this should pass
    let n = (HEAP_SIZE / size_of::<u64>()) as u64 / 2; // 6400 for 100 KiB HEAP_SIZE
    assert_eq!(6400, n);

    // whereas this should fail.
    // let n = (HEAP_SIZE / size_of::<u64>()) / 2 + 1; // 6401

    (0..n).for_each(|i| {
        Box::into_raw(Box::new(i));
    });
}

[UsQuake]

How can I translate the posts in Korean

[bjorn3]

#1092 is the tracking issue for Korean translations. I would suggest looking there for any posts that others are already translating and commenting with the post you picked to avoid duplicate work.

[jlkiri]

Amazing article, thank you.
I'm not sure I understand one of the caveats at end of the article: "We currently only create new blocks, but never free them again.". What does it mean? As far as I can see the blocks are freed in the dealloc implementation.