OSDev.org
https://forum.osdev.org/

What heap algorithm is Linux using?
https://forum.osdev.org/viewtopic.php?f=15&t=33622
Page 1 of 1

Author:  LIC [ Thu Apr 04, 2019 2:13 am ]
Post subject:  What heap algorithm is Linux using?

I have seen that there are several kernel heap algorithms with their pros and cons. What about Linux? What is the heap algorithm that the Linux Kernel is using?

Thanks for your answers

Author:  iansjack [ Thu Apr 04, 2019 3:03 am ]
Post subject:  Re: What heap algorithm is Linux using?

If only the source code wad available to answer this sort of question.

If only someone had written a book describing the workings of the Linux kernel.

Seriously - without wishing to appear rude - there is a wealth of information available on the web and in print about the Linux kernel. You will learn far more by doing your own research than by asking someone else to do it for you. Amongst other publications let me recommend: https://www.amazon.com/Professional-Ker ... 0470343435

Author:  bzt [ Thu Apr 04, 2019 4:01 am ]
Post subject:  Re: What heap algorithm is Linux using?

Hi
LIC wrote:
I have seen that there are several kernel heap algorithms with their pros and cons. What about Linux? What is the heap algorithm that the Linux Kernel is using?

Thanks for your answers
A quick google search reveals that Linux is using the buddy allocator for page allocation and slab allocator for heap, which algorithm originates from Solaris' allocator.

https://www.kernel.org/doc/gorman/html/understand/understand009.html
https://en.wikipedia.org/wiki/Buddy_memory_allocation
https://www.kernel.org/doc/gorman/html/understand/understand011.html
https://en.wikipedia.org/wiki/Slab_allocation

Cheers,
bzt

Author:  Solar [ Thu Apr 04, 2019 7:45 am ]
Post subject:  Re: What heap algorithm is Linux using?

iansjack wrote:
If only the source code wad available to answer this sort of question.


Source code tells you lots about the "how". Unless there are comments, figuring out the "what" can be somewhat of a stretch, especially in a code base of that magnitude. And even then you usually get the "what" on a rather too-fine-grained level. Usually we rely on documentation to tell us the high-level "what" and "why".

Author:  iansjack [ Thu Apr 04, 2019 8:48 am ]
Post subject:  Re: What heap algorithm is Linux using?

Solar wrote:
iansjack wrote:
If only the source code wad available to answer this sort of question.


Source code tells you lots about the "how". Unless there are comments, figuring out the "what" can be somewhat of a stretch, especially in a code base of that magnitude. And even then you usually get the "what" on a rather too-fine-grained level. Usually we rely on documentation to tell us the high-level "what" and "why".

Which - of course - is why I also recommended books.

A combination of the two is - IMO - better than relying upon inaccurate generalisations such as " it uses the buddy allocator".

Author:  LIC [ Thu Apr 04, 2019 2:39 pm ]
Post subject:  Re: What heap algorithm is Linux using?

Thank you for your replies, I tried to check the answer by myself with the Linux kernel code but with all the files, I could not find out a clue on where to look for this part of the kernel first.

Thank you for the links !

Page 1 of 1 All times are UTC - 6 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/