Why is bztalloc not mentioned in the wiki?
-
- Member
- Posts: 5543
- Joined: Mon Mar 25, 2013 7:01 pm
Re: Why is bztalloc not mentioned in the wiki?
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.
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.
Re: Why is bztalloc not mentioned in the wiki?
I’ve looked at the code, it uses woefully inefficient algorithms. It seems pretty reliable though
Re: Why is bztalloc not mentioned in the wiki?
Do you think it's worth using it? Or is it better to stick to another allocator?nexos wrote:I’ve looked at the code, it uses woefully inefficient algorithms. It seems pretty reliable though
Re: Why is bztalloc not mentioned in the wiki?
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
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
Re: Why is bztalloc not mentioned in the wiki?
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?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
How much worse is using a general-purpose allocator for the entire kernel?
Re: Why is bztalloc not mentioned in the wiki?
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.
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.
Re: Why is bztalloc not mentioned in the wiki?
Well, thanks for the reply and the links!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.
-
- Member
- Posts: 425
- Joined: Tue Apr 03, 2018 2:44 am
Re: Why is bztalloc not mentioned in the wiki?
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.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 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.
Re: Why is bztalloc not mentioned in the wiki?
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).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.
Re: Why is bztalloc not mentioned in the wiki?
I try to follow this rule, favoring understanding over performance.thewrongchristian wrote:You're better off using something you understand and works.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.
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.
Re: Why is bztalloc not mentioned in the wiki?
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:I try to follow this rule, favoring understanding over performance.
At the same time, I wouldn't want to lose too much performance.
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.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.
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!