OSDev.org

So, I am currently writing a memory allocater instead of using one I found online. I originally wanted to write a buddy allocator, but as far as I know there are
different systems. So, which one should I use? Are some of them more secure, etc. or do they differ in speed.

thanks in advance.

Ahh, memory management my favorite

Basically, a memory manager has many layers. It appears you are talking about the physical layer. This layer allocates blocks of physical memory which in turn are used by the virtual memory manager. If you are going without paging, this is the only layer you have to worry about. Also, physical memory is managed in blocks for efficiency's sake. On x86, the block size normally would be 4K (although there isn't anything requiring this, it is just more convenient when you implement paging) As far as algorithms go, there are 4 main algorithms that are used for PMMs

Bitmap - this one is easy to understand. You have a big array, where each bit represents a particular block. Bit 0 represents block 0, bit represents block 1, and so on. Allocation involves doing a linear search for this first bit set to 0 and then setting it to 1. Deallocation sets a given bit to 0.
Advantages
- Easy to understand
- Allows for contiguous memory blocks (which would be a necessity without paging)
- Many tutorials on it
- Takes up little memory
Disadvantages
- The slowest algorithm used. To improve performance, normally bits are compared in uint32_ts instead of smaller units. Also, caching the most recent allocated block as a hint could somewhat help as well
- Has a high overhead to implement

Free list - basically, you just have a linked list. At startup, you loop through every page that is free, and you add a pointer to the next free page at the first uintptr_t in that page. The head of the list is stored. Allocation involves grabbing the page at the head of the list, freeing involves placing a page at the head of the list
Advantages
- Very fast, O(1) in fact
- Takes up no extra memory, as free info data is stored in the actual free blocks
- Easy to implement allocation and freeing, not so easy to initialize
Disadvantages
- Impractical on 32 bit system where paging is used, as the physical memory needs to be mapped somewhere
- Would be very slow to allocate contingious blocks

Free stack - Basically, you allocate a big array to store all addresses of all free physical addresses. You loop through every free page, and add its address to the list. This creates a stack like data structure, where the highest address of the array is the stack top. Allocation involves popping a page of off the stack top. Freeing involves pushing a page on the stack top.
Advantages
- Very fast, O(1)
- Easy to implement
Disadvantages
- Takes up lots of extra memory
- Would be very slow to allocate contingious blocks

Finally, we have the buddy allocator. This one is more complex to explain, so I will point you to the wiki. Basically, it combines a free list / stack and a bitmap to allow fast allocation of larger contiguous blocks. I will implement this one in my OS.
In reality, a buddy system is good as it gives you better cache performance for contiguous blocks, but has a high overhead. Note that Linux also has multiple buddies, one for ISA DMA (which must be 64K aligned), one for normal pages, and I believe one for large pages.
For a hobby OS, a free stack will be good enough. This is fast, simple, and works great. If you want a more sense of professional-ism, then go with a buddy system. I would recommend googling about Lazy Buddy as well, as it has some performance advantages over normal buddy.
I hope I didn't bore you with loads of theory
nexos

You forgot the slab allocator, which would be my choice.

iansjack wrote:You forgot the slab allocator, which would be my choice.

I was focusing on physical memory allocators The slab would be my choice for heap type allocators. I personally haven't heard of slab PMMs, but if there are those, please, correct me

Thanks a lot! So then I will probably try to implement the buddy allocator. Just one more question: If I am writing a microkernel, should I wait for memory allocation until I implement a malloc server?

nexos wrote: I hope I didn't bore you with loads of theory
nexos

No, this was a quite interesting overview of systems and their advantages.

acccidiccc wrote:Thanks a lot! So then I will probably try to implement the buddy allocator. Just one more question: If I am writing a microkernel, should I wait for memory allocation until I implement a malloc server?

I would implement as much of the MM in kernel as possible

To advantages / disadvantages I would add possibility to create a lock-free implementation. I think only bitmap allows this. Having a lock free implementation is good when you use lazy evaluation of page frames and allocate memory for them in the pagefault handler.

The bitmap allocator also can be combined with having a "header" per 4kB bitmap entries that has free count and a current pointer. This makes normal allocation very fast as long as you have a lot of free memory.

acccidiccc wrote:Thanks a lot! So then I will probably try to implement the buddy allocator. Just one more question: If I am writing a microkernel, should I wait for memory allocation until I implement a malloc server?

Memory management is by necessity one of the things you need to have in the main kernel. Just to avoid the chicken-and-egg scenario when loading the malloc server (I want to load the server, but for that I have to allocate memory for the server to live in...) Also, management of page tables is necessarily a part of the main kernel, since it is part of context switching, and context switching must be implemented in the main kernel (or else, how would you switch contexts to the context switcher?)

Therefore you have to manage physical memory and virtual memory in the main kernel. That does not mean you need malloc() in the kernel, but it will probably help.

rdos wrote:To advantages / disadvantages I would add possibility to create a lock-free implementation. I think only bitmap allows this. Having a lock free implementation is good when you use lazy evaluation of page frames and allocate memory for them in the pagefault handler.

How so? Pagefault from user space is by definition the highest layer in the kernel stack, so no spinlock can be taken on that core. And page fault from kernel space that requires the use of the physical allocator should only happen in case of user space access, which should also only happen if no spinlock is taken. In both cases, taking a spinlock for the PMM is safe.

nullplan wrote:

rdos wrote:To advantages / disadvantages I would add possibility to create a lock-free implementation. I think only bitmap allows this. Having a lock free implementation is good when you use lazy evaluation of page frames and allocate memory for them in the pagefault handler.

How so? Pagefault from user space is by definition the highest layer in the kernel stack, so no spinlock can be taken on that core. And page fault from kernel space that requires the use of the physical allocator should only happen in case of user space access, which should also only happen if no spinlock is taken. In both cases, taking a spinlock for the PMM is safe.

I have no PMM. I also use lazy evaluation of page directory entries and let the pagefault handler allocate & initialize those when the memory is first referenced. Additionally, many kernel linear areas are populated with physical memory in pagefault handler when referenced. This is often in kernel space, and there is no guarantee that this will happen in userspace or linked to userspace, and it can actually happen in scheduler, spinlocks, or IRQs, even if it is rare. However, I want these rare things to work properly without checking overhead elsewhere and so I have a lock-free physical memory handler that works when called from within scheduler, IRQs, and spinlocks.

rdos wrote:I have no PMM. [...] I have a lock-free physical memory handler

Your "lock-free physical memory handler" is your PMM.

nullplan wrote:In both cases, taking a spinlock for the PMM is safe.

So, you want to use a spinlock to protect the PMM? Spinlocks should usually be fast and only kept for a small period of time, which is fine when allocating & freeing single pages in a list or stack, but not when allocating multiple (continuous) physical pages which require extensive operations. I would say that if you use the bitmap method or support allocating more than one page at a time, then you shouldn't use a spinlock to synchronize the PMM, rather you must use a semaphore or similar. Of course, a lock-free bitmap allocator doesn't need a spinlock and so won't keep spinlocks for extended periods of time.

You could just use a mutex to do this. I hear you saying, "but don't you need the PMM before the scheduler?" And yes, that is true, but you could have a flag to determine whether locks are needed or not.

Octocontrabass wrote:

rdos wrote:I have no PMM. [...] I have a lock-free physical memory handler

Your "lock-free physical memory handler" is your PMM.

I don't know. It seems like people attribute PMM to handle user memory mappings. My lock-free physical memory handler only has functions to allocate one or more physical page frames or to free them. It doesn't deal with mapping them into linear address space at all, nor does it care about reference counts. The allocator will return a physical base address and free will take a physical address as the parameter.

Also, I think the ability to detect double frees (or freeing non-allocated pages) should be added as an advantage of the bitmap allocator and a drawback of the other methods. Typically, a list allocator will become corrupt if you double free a page.

nexos wrote:You could just use a mutex to do this. I hear you saying, "but don't you need the PMM before the scheduler?" And yes, that is true, but you could have a flag to determine whether locks are needed or not.

It's even more complex than that since you might need the PMM before you actually have set up all the free pages in the PMM. The bitmap allocator will need physical pages to create the bitmaps, which creates a nasty recursive situation. Something that actually is easier to handle with lists where you only need to link them.