Clarification on how kmalloc works

[Sanchezman]

I'm ready to begin more memory management for my OS. I have a physical memory manager set up, and paging enabled. Now I want to work on kmalloc, but I wanted to be sure I understood the process. Here's the way I see it, and I'd love to get more information about how the kmalloc process usually works:

1: Find the first amount of contiguous memory big enough to hold what is requested. I plan to use a doubly-linked list to map out memory, with pointers to the next and previous spaces, as well as information about the size and availabilty (free/allocated) of each section of memory.
2: If the current amount of memory we're using is not big enough, request from the physical memory manager to free a new block(s) for use. We'll have the end of our previous block point to this new one, and the beginning of our new one will point back to the old one.
3: If we had to request a new block(s), give it a page table entry that registers it as both present and belonging to the kernel
4: Now we can divy up the block(s) into the amount of memory requested. Mark the section as allocated.
5: Return the pointer to our section
6: Freeing works by checking neighboring blocks for contiguous free space and consolidating. If an entire block is free, we free it in the physical memory manager and set its page table entry to 'Not present'

Is this a viable process for a memory manager? Am I forgetting anything important?

[bluemoon]

There are many ways to implement kmalloc, depends on your requirement.

For me, I have the following layers:
1. PMM - alloc/free page
2. LMM - handle address space
3. Heap - a linearly expandable memory
4. kmalloc - handle the book-keeping and recycling of memory.

So, I have a kernel heap, which starts and expands at a specific address.

When you ask for memory with kmalloc, it checks its repo to see if any "previously free'd" block, for the first time it's no. It then ask the heap to expand. and return such piece of memory.

When you kfree a memory, the block it put into malloc's repo for recycling later.

Now for a bit more optimisations - I classify the allocation by size, such that there are multiple "recycling list" (and locks). I also add a prefix block to store meta info in front of the returned memory, so that kfree can know the size and put back into correct list.

PS. I have intention to not abuse kernel heap, so I did not care to shrink or swap the kernel heap, but you may think about it.

[FallenAvatar]

...

Good job advertising your way of doing things and not answering the OP's question.

...

The only thing I think you might be forgetting is virtual memory. You might need a layer to handle that (even kernels use paging/virtual memory.) For more info on that, take a super quick glance at bluemoon's post, then hop to the wiki linked at the top.

- Monk

[eryjus]

Am I forgetting anything important?

Here are some details to consider (food for thought only):

1: Find the first amount of contiguous memory big enough to hold what is requested. I plan to use a doubly-linked list to map out memory, with pointers to the next and previous spaces, as well as information about the size and availabilty (free/allocated) of each section of memory.

• Are you going to sort this list in order to find a better fit?
• Consider what happens to your alignment when you request kmalloc(1).
• How will you handle kmalloc(0)?
• Is there a size limit to what you can request?

2: If the current amount of memory we're using is not big enough, request from the physical memory manager to free a new block(s) for use. We'll have the end of our previous block point to this new one, and the beginning of our new one will point back to the old one.

• When you have to go to the PMM, you might consider how much you ask for.

4: Now we can divvy up the block(s) into the amount of memory requested. Mark the section as allocated.

• What do you do when a leftover block is too small?

6: Freeing works by checking neighboring blocks for contiguous free space and consolidating. If an entire block is free, we free it in the physical memory manager and set its page table entry to 'Not present'

• It would be a shame to return a block to the PMM as soon as it was all free just to turn around to ask for it back with the next allocation...

Is this a viable process for a memory manager?

I think you have a good start. You will find improvements to make as you continue on, I'm sure.