OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Mar 19, 2024 4:50 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Why is bztalloc not mentioned in the wiki?
PostPosted: Mon Jan 29, 2024 11:46 am 
Offline
Member
Member
User avatar

Joined: Sun Jul 21, 2019 7:34 am
Posts: 291
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?


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Mon Jan 29, 2024 12:59 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5069
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.


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Mon Jan 29, 2024 1:52 pm 
Offline
Member
Member

Joined: Tue Feb 18, 2020 3:29 pm
Posts: 1071
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


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Mon Jan 29, 2024 4:16 pm 
Offline
Member
Member
User avatar

Joined: Sun Jul 21, 2019 7:34 am
Posts: 291
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?


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Tue Jan 30, 2024 8:34 am 
Offline
Member
Member

Joined: Tue Feb 18, 2020 3:29 pm
Posts: 1071
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/blob/dev/source/nexke/mm/slab.c
https://github.com/nexos-dev/nexnix/blob/dev/source/nexke/mm/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


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Tue Jan 30, 2024 9:05 am 
Offline
Member
Member
User avatar

Joined: Sun Jul 21, 2019 7:34 am
Posts: 291
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/blob/dev/source/nexke/mm/slab.c
https://github.com/nexos-dev/nexnix/blob/dev/source/nexke/mm/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?


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Tue Jan 30, 2024 12:37 pm 
Offline
Member
Member

Joined: Tue Feb 18, 2020 3:29 pm
Posts: 1071
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


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Tue Jan 30, 2024 12:53 pm 
Offline
Member
Member
User avatar

Joined: Sun Jul 21, 2019 7:34 am
Posts: 291
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!


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Tue Jan 30, 2024 6:42 pm 
Offline
Member
Member

Joined: Tue Apr 03, 2018 2:44 am
Posts: 399
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.


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Tue Jan 30, 2024 7:20 pm 
Offline
Member
Member

Joined: Tue Feb 18, 2020 3:29 pm
Posts: 1071
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


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Wed Jan 31, 2024 11:28 am 
Offline
Member
Member
User avatar

Joined: Sun Jul 21, 2019 7:34 am
Posts: 291
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.


Top
 Profile  
 
 Post subject: Re: Why is bztalloc not mentioned in the wiki?
PostPosted: Wed Jan 31, 2024 2:13 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1590
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!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group