Why is bztalloc not mentioned in the wiki?

[mrjbom]

The wiki page about memory management mentions many allocators in the list of malloc implementations, but no bztalloc. Judging by the description of bztalloc it is superior to many of those mentioned in the article, why is it not listed among them?

[Octocontrabass]

The wiki isn't trying to list every allocator out there, but you're welcome to make any additions you think are worthwhile.

Are you judging it only by the description, though? It's important to make sure the code actually works and doesn't have any bugs or undefined behavior before recommending it to others.

[nexos]

I’ve looked at the code, it uses woefully inefficient algorithms. It seems pretty reliable though

[mrjbom]

I’ve looked at the code, it uses woefully inefficient algorithms. It seems pretty reliable though

Do you think it's worth using it? Or is it better to stick to another allocator?

[nexos]

It depends on your use case. If you need reliability, bztalloc is actually good as it keeps allocator and user data separate. The main problem with it is that is not very scalable IMO. Personally, I would recommend for a kernel implementing a slab allocator, as documented here. They have excellent performance. Note that slab allocators don't work great for general sized allocations. They are designed for caching objects such as a thread structure, process structure, vnode, etc. For general allocations you can use power of two free lists, which may not be ideal, but you'll find yourself not needing to use it much.

Here is my kernel's slab allocator (which isn't quite complete yet) and malloc functions:
https://github.com/nexos-dev/nexnix/blo ... /mm/slab.c
https://github.com/nexos-dev/nexnix/blo ... m/malloc.c

[mrjbom]

It depends on your use case. If you need reliability, bztalloc is actually good as it keeps allocator and user data separate. The main problem with it is that is not very scalable IMO. Personally, I would recommend for a kernel implementing a slab allocator, as documented here. They have excellent performance. Note that slab allocators don't work great for general sized allocations. They are designed for caching objects such as a thread structure, process structure, vnode, etc. For general allocations you can use power of two free lists, which may not be ideal, but you'll find yourself not needing to use it much.

Here is my kernel's slab allocator (which isn't quite complete yet) and malloc functions:
https://github.com/nexos-dev/nexnix/blo ... /mm/slab.c
https://github.com/nexos-dev/nexnix/blo ... m/malloc.c

In general, instead of implementing a general-purpose allocator in the kernel and using kmalloc for everything in the kernel, it would be correct to implement a slab allocator for all major kernel structures and in rare cases use the power of two free allocation lists, right?

How much worse is using a general-purpose allocator for the entire kernel?

[nexos]

It would be preferable to use a slab allocator most of the time. It's not bad to use a general purpose malloc everywhere, it's just that an efficient malloc is fairly tricky to implement, whereas a slab allocator naturally has a certain level of efficiency.

If you want to go the simple route and use a standard malloc, I would recommend liballoc. Liballoc is fairly efficient, and works well in my experience.

[mrjbom]

It would be preferable to use a slab allocator most of the time. It's not bad to use a general purpose malloc everywhere, it's just that an efficient malloc is fairly tricky to implement, whereas a slab allocator naturally has a certain level of efficiency.

If you want to go the simple route and use a standard malloc, I would recommend liballoc. Liballoc is fairly efficient, and works well in my experience.

Well, thanks for the reply and the links!

[thewrongchristian]

It depends on your use case. If you need reliability, bztalloc is actually good as it keeps allocator and user data separate. The main problem with it is that is not very scalable IMO.

Be careful about making such opinions. Scalability can be deceptive. A linear search of a dense array can be faster than a similarly sized binary search tree, once cache effects are taken into account.

You need to make measurements before you can make a qualified opinion on scalability, else it's just a guess.

Which begs the question, what sort of metric do people look at for allocator scalability? And for the typical hobby OS, and especially given the plug-and-play nature of the malloc/free interface, does it even matter?

You're better off using something you understand and works. As soon as you outgrow whatever malloc implementation you use, chances are you'll be in a good position to choose something better, and know why it's better.

[nexos]

Be careful about making such opinions. Scalability can be deceptive. A linear search of a dense array can be faster than a similarly sized binary search tree, once cache effects are taken into account.

Yeah, that can be true. I mainly said that because freeing in bztalloc is O(n), whereas on most common allocators I know of, they have a faster approach for freeing (like storing the block header right beneath the free'd address).

[mrjbom]

It depends on your use case. If you need reliability, bztalloc is actually good as it keeps allocator and user data separate. The main problem with it is that is not very scalable IMO.

You're better off using something you understand and works.

I try to follow this rule, favoring understanding over performance.
At the same time, I wouldn't want to lose too much performance.
So, I would probably prefer to use malloc for all things in the kernel since it's easier, however I don't know how much worse it is compared to general purpose malloc.

[nullplan]

I try to follow this rule, favoring understanding over performance.
At the same time, I wouldn't want to lose too much performance.

Write the simple algorithm you understand. Then see if the performance is OK. If not, then measure where the slowdowns are. If experience has taught me anything here, it is that developers are incapable of gauging performance bottlenecks. They are never where you think they are. So measure twice, that way at least you have some way to know.

So, I would probably prefer to use malloc for all things in the kernel since it's easier, however I don't know how much worse it is compared to general purpose malloc.

The kernel has special needs compared to an application. Quite a few allocations require specific regions of physical memory. And the kernel often operates on objects that are quite costly to construct and destroy, and much cheaper to be left lying around and reused later. But only until memory gets scarce, of course. So while a normal malloc implementation is likely fine, you will need to build things on top of it, or maybe build some memory management directly on top of the physical and virtual allocators.

Speaking of malloc, all of the implementations I know depend on something to get more memory, so you will have to implement some way to do that as well.