Hiya
Octacone wrote:
Hello everybody!
I have a conceptual dilemma on how to implement this thing. I don't know where to start, what to look for. I already searched quite a few online pages, but they don't talk about the implementation itself.
How to implement it? To use a double linked list? I know for sure that I do not and will not want port an existing allocator, just don't try to convince me. Do I need to look at other OS specific implementations and try to kind of
"clone" them or should I come up with my own idea? The problem is that I don't even know how it technically works and what it does underneath.
I have quite a few tabs open with different source files to look at, but the problem is that they mostly rely on James Molloy's implementation. Is that implementation even worth taking a look at?
I know this is one really big question, I really need help. I can't continue working on my OS until I have something as important as this working perfectly.
Also I've read about best fist, first fit algorithms. I for sure don't want to waste any memory to fragmentation.
So I would have to find the hole that satisfies the request, take requested + overhead and then split that hole leaving the extra for future allocation.
My primary goal right now is the be able to understand every little detail on how it works and how to implement it. Thanks for understanding!
What exactly are you trying to implement at the moment? There are a lot of levels to memory management in a kernel, including, but not necessarily limited to, physical memory allocation, address space allocation/vmm, and then specific heap allocators. There are also a lot of different methods for each of these, with their own common and uncommon methods of implementation. It seems to me like you're trying to implement both a virtual memory manager, and a malloc/free style discrete allocator (for your kernel space?).
Algorithms like the ones used in tlsf, and other discrete heap allocators are rather complex, and usually involve some kind of mix between free lists, binning, trees, and doubly linked lists so as to either minimize time, memory waste, or both. You can work for as long as you want at writing an allocator, and still never have a perfect (or necessarily even good) implementation of one. I suggest that if you want to learn how to build a discrete heap allocator, you do so in user space, rather than trying to do it along side the rest of a kernel.
AVL trees, RB trees, and siblings of them, on the other hand, are a typical way of managing address spaces. (As has been mentioned before, linux uses RB trees for it's virtual memory manager, and if i'm not mistaken, also for the physical memory manager. These binary trees represent contiguous memory by existing in a sorted state, where each nth node from the left represents the next region of memory. That way, if you traverse the (sorted) tree in left-to-right order, you will cover the memory region you're managing completely and sequentially. The specific advantage of balanced binary trees is, of course, their worst case O(log n) for search, addition, and removal. In practice, this is usually pretty efficient in a VMM or PMM situation. That is what I personally use in my PMM and VMM, along with a set of size-binned doubly linked list for free zones. If you'd like to see that implementation, it's
here and
here, but it is rather complex. I suggest that if you want to learn about AVL trees, again, do it in user space first.
That's how I did it.
As for fragmentation, It's important to understand the problem before you try and find a solution. Basically, the problem with fragmentation is that a program might allocate two sequential chunks of memory and free the first, but not the second. That means that your first free block is stuck at the size of the first allocation until the program frees the second block. This will happen no matter what allocation algorithm you use. What makes an allocator good at circumventing fragmentation is the ability to recognize and combine two adjacent free blocks of memory. balanced/sorted binary trees are nice for this because you can very quickly find the next sequential chunk of memory on the free list, and if it's sequential to another free chunk, combine it and rebalance the tree. This means that fragmentation is kept to a minimum, because you don't allow two adjacent free blocks to be disjointed.
I recommend figuring out which part of your kernel you're trying to implement, and then trying to solve the problem in user space first. It's a lot easier to debug an allocator in userland than in a custom kernel, especially if you haven't set up proper kernel debugging yet.