Why is bztalloc not mentioned in the wiki?

All about the OSDev Wiki. Discussions about the organization and general structure of articles and how to use the wiki. Request changes here if you don't know how to use the wiki.
Post Reply
User avatar
mrjbom
Member
Member
Posts: 309
Joined: Sun Jul 21, 2019 7:34 am

Why is bztalloc not mentioned in the wiki?

Post by 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
Member
Member
Posts: 5543
Joined: Mon Mar 25, 2013 7:01 pm

Re: Why is bztalloc not mentioned in the wiki?

Post by 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
Member
Member
Posts: 1081
Joined: Tue Feb 18, 2020 3:29 pm
Libera.chat IRC: nexos

Re: Why is bztalloc not mentioned in the wiki?

Post by nexos »

I’ve looked at the code, it uses woefully inefficient algorithms. It seems pretty reliable though
"How did you do this?"
"It's very simple — you read the protocol and write the code." - Bill Joy
Projects: NexNix | libnex | nnpkg
User avatar
mrjbom
Member
Member
Posts: 309
Joined: Sun Jul 21, 2019 7:34 am

Re: Why is bztalloc not mentioned in the wiki?

Post by mrjbom »

nexos wrote: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
Member
Member
Posts: 1081
Joined: Tue Feb 18, 2020 3:29 pm
Libera.chat IRC: nexos

Re: Why is bztalloc not mentioned in the wiki?

Post by 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
"How did you do this?"
"It's very simple — you read the protocol and write the code." - Bill Joy
Projects: NexNix | libnex | nnpkg
User avatar
mrjbom
Member
Member
Posts: 309
Joined: Sun Jul 21, 2019 7:34 am

Re: Why is bztalloc not mentioned in the wiki?

Post by mrjbom »

nexos wrote: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
Member
Member
Posts: 1081
Joined: Tue Feb 18, 2020 3:29 pm
Libera.chat IRC: nexos

Re: Why is bztalloc not mentioned in the wiki?

Post by 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.
"How did you do this?"
"It's very simple — you read the protocol and write the code." - Bill Joy
Projects: NexNix | libnex | nnpkg
User avatar
mrjbom
Member
Member
Posts: 309
Joined: Sun Jul 21, 2019 7:34 am

Re: Why is bztalloc not mentioned in the wiki?

Post by mrjbom »

nexos wrote: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
Member
Member
Posts: 425
Joined: Tue Apr 03, 2018 2:44 am

Re: Why is bztalloc not mentioned in the wiki?

Post by thewrongchristian »

nexos wrote: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
Member
Member
Posts: 1081
Joined: Tue Feb 18, 2020 3:29 pm
Libera.chat IRC: nexos

Re: Why is bztalloc not mentioned in the wiki?

Post by nexos »

thewrongchristian wrote: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).
"How did you do this?"
"It's very simple — you read the protocol and write the code." - Bill Joy
Projects: NexNix | libnex | nnpkg
User avatar
mrjbom
Member
Member
Posts: 309
Joined: Sun Jul 21, 2019 7:34 am

Re: Why is bztalloc not mentioned in the wiki?

Post by mrjbom »

thewrongchristian wrote:
nexos wrote: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
Member
Member
Posts: 1779
Joined: Wed Aug 30, 2017 8:24 am

Re: Why is bztalloc not mentioned in the wiki?

Post by nullplan »

mrjbom wrote: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.
mrjbom wrote: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.
Carpe diem!
Post Reply