OSDev.org

Hi there,
I'm just trying to implement my kmalloc() in my memory manager.

I've got a workig page allocator which marks a page as used in a bitmap and I also have paging working.
At least for allocation.

Now I wanted to implement a first fit algorithm to start at an easy level.
I've currently got the following idea in my head floating around:

My kernel resides at (virtual) 0xC0000000 = 3GB and I currently assume that the kernel and the stack behind it has a size of 4MB.
After that the kernel heap starts, for now, at 0xC0400000 and can grow up to 0xFFBFFFFF. The last page is used for the identity paging.

Now if I want to allocate memory with my kmalloc() function for the first time, I allocate a page and map it into the heap-space.
Then I create a little structure for the metadata which contains the size of the allocated space, what type it is (free or used) and a pointer to the next structure which then resides after the just allocated memory with type "free" and the size of the rest of the space for the heap.
Before allocating space I always need to check wether a new page must be mapped into the space and do it if neccessary.
Freeing would also be easy: Just look at the neighbours if they are free and merge the entries in the linked list. But how can I find the predecessor of an entry? A double linked list would be much more prone to errors when messing around with all these pointers.

Would this be the right thing how to do it? Or should I store the metadata per allocated page in the heap?
Oh and some minor question about the stack: Should I locate the stack on some other place? So designate some own space for it?

Thanks for your suggestions,
Andreas

Hi Andreas,
I have recently written my own memory manager.I have followed the same line as u are thinking.Here is what u can do

First of all when u dynamically allocate space your malloc needs to maintain some metadata .You can have both Header and footer.

Struct header{
struct header * next;
unsigned int free;
unsigned int size;
}

and a footer

struct Footer {
struct Footer *prev;
unsigned int size;
}

For every allocation u will be having an overhead of 20 bytes but thats ok.
And another thing ,doubly link list do not cause any problem.Personally , i used the bin approach with doubly linked list.

I followed a three tier approach
1) malloc()
2) memory mappper
3) physical_bitmap_allocater()

memory_mapper asks lower functions to provide pages and maps these pages to the end of Heap.
One thing u should keep in mind that as soon as u enable PAging all addresses are treated as virtual but your page tables and dirs contains physical addresses and therefore you cannot modify them directly.

I would advice you to go through Tim Robinson Memory manager tutorial at
http://osdever.net/tutorials/memory1.php
They would answer most of you queries.

So you are treating the whole heap space as one continous block of memory and you are mapping your frames on demand into this space?

I've already got the two lowest layers implemented.
That are some functions to mark a physical frame as used and a function to map virtual addresses to physical ones. So having some abstraction over all this paging stuff.

I think I'll try my luck tomorrow with implementing it.

Typical steps would be like this:

initialization:
1. Map one page to the beginning of the heap and write a header into it
2. Determine the size of the complete heap minus the size of the header and set it into the header

after that memory is allocated like this:
1. Rush through the linked list and look for a free block with enough space
2. Get the starting address of the found block, add the size of the header and the requested size of memory and check if the resulting "end-address" has a frame assinged
3. if not, mark a frame as used and map it to the corresponding address
4. Split the found block (if neccessary) into 2 parts, the first one with the size of the header and the requested size of the memory
5. return the address

deallocating is a bit more sophisticated.
First, I will have to look at the neighbours to determine if there are some free blocks for merging
And after that I have to dtermine if there is any used block in the page I just free'd a block and unmap this page and free it in the physical memory manager if not.

Would this be the right thing how to do it? Or should I store the metadata per allocated page in the heap?

You should store metadata with each chunk of space allocated to user.So if user requests x byte of memory you are actually having something like this
(header + x + footer).Header and footer contains necessary bookkeeping information .I do not think there is any need to maintain metadata with mapped pages.Whenever u map a page simply increment the HEAP_PTR.

So you are treating the whole heap space as one continous block of memory and you are mapping your frames on demand into this space?

Yes u are right. My heap starts from 3gb marks and any physical frame is mapped to virtual address starting from HEAP_PTR which is then incremented by PAGE_SIZE.

First, I will have to look at the neighbours to determine if there are some free blocks for merging And after that I have to dtermine if there is any used block in the page I just free'd a block and unmap this page and free it in the physical memory manager if not.

When u free some memory chunk u shouldn't unmap that particular page.One reason being that maybe more than 1 process have been allocated space from this page and second being that process may call malloc again and then u would need to map again.Maybe u can schedule a process which runs once in a while and checks if large mapped areas in HEAP are unallocated and then unmaps them.

I would suggest u go through following links as they really helped me out
http://gee.cs.oswego.edu/dl/html/malloc.html
http://www.ibm.com/developerworks/library/l-memory/

Oh and some minor question about the stack: Should I locate the stack on some other place? So designate some own space for it?

I am currently having problem related to stack myself though after reading through some posts on this forum i gathered that it is not a good idea to move the stack.