High Level Memory Manager Question.

[astrocrep]

Ok,

So thanks to the help of some fellow os devers, my Virtual memory manager is working, along with my physical page allocator. I wrote a simple "hack" kmalloc that basically just allocated pointers at a given location (1gb) and would allocate every new request at the end of the first... obvious this is horrible, but it was just to proven my vmm, and mm were working.

So now I want to create a much better kmalloc and implement a kfree... (along with an eventual malloc/free). My confusion becomes connecting (k)malloc and (k)free to the kernel's memory manager. I understand that *malloc is something that should be in a library, and not a kernel function, furthermore, I know that *malloc calls either sbrk or mmap to get more space in the heap.

What I dont get is who maintains the information about mallocs??

So When some random program (or kernel) calls malloc, and malloc needs more pages, its calls either sbrk or mmap. I think in my case it will use mmap to add a new page to the end of the heap. I assume that mmap (or sbrk) _IS_ a kernel function, so I would guess the kernel would need to keep track of the all of the heaps. My confusion is how would the kernel know which heap to extend? Is there a general practice for that? Or is there some big concept I am missing?

Thanks,
Rich

[Brendan]

Hi,

So When some random program (or kernel) calls malloc, and malloc needs more pages, its calls either sbrk or mmap. I think in my case it will use mmap to add a new page to the end of the heap. I assume that mmap (or sbrk) _IS_ a kernel function, so I would guess the kernel would need to keep track of the all of the heaps. My confusion is how would the kernel know which heap to extend? Is there a general practice for that? Or is there some big concept I am missing?

The library would call brk() or sbrk() or mmap(), which are kernel functions, but the kernel doesn't know or care why they were called and doesn't know anything about malloc.

For brk() and sbrk() the kernel maintains a "top of RAM" variable. If someone uses brk() or sbrk() to increase the "top of virtual RAM" variable the kernel will allocate more pages between the old top of virtual RAM and the new top of virtual RAM. If someone uses brk() or sbrk() to decrease the variable the kernel will free any pages between the old top of virtual RAM and the new top of virtual RAM.

For mmap(), the kernel just looks for part of the address space that isn't being used (e.g. by scanning the page tables perhaps) and uses that. It's up to the caller to keep track of which areas it's using for what.

Programmers *should* be able to use brk()/sbrk() or mmap()/munmap() through something other than malloc/free (e.g. obstacks), or use them directly without a library (for e.g. to avoid malloc overheads for large allocations). Of course it's normal for brk()/sbrk() or mmap()/munmap() to work on pages, so they're fairly wastefull if you only want to allocate 20 bytes or something...


Cheers,

Brendan

[astrocrep]

Ohhhh...

I think I got it... excellent explaination!

Well Actually, How would you work freeing memory?

Thanks yet again!

-Rich

[jnc100]

If you want to learn about how malloc works, then (I believe) there's a sample implementation in the K+R book. If its just as a means to get to a more interesting (for you) part of your OS then I suggest you use the Doug Lea's malloc (just Google for dlmalloc) which is just one source file that can be dropped into your source tree with only a few defines (and an sbrk or mmap) to make it work. As I wasn't too interested in the implementation details I won't enlighten you with my rather limited understanding now, besides from the fact that it works quite well and is in the public domain.

As regards to freeing memory, then dlmalloc also implements a free function. If you mean releasing memory back to the kernel, it calls sbrk with a negative argument, which should just decrease the end of stack pointer, and optionally free some physical pages.

Regards,
John.

[Kevin McGuire]

You take a contiguous range of memory and give it a header. To allocate memory you split then range at the amount you need and give both parts a header. You continue this trend.

You use a (int size) field to represent a freed or allocated block. If the number is negative then the block is free and if positive then the block is allocated.

The implementation details are straight forward once you wrap your head around it one good time. Although there are numerous ways to do it they all do almost exactly the same thing.

You walk the heap by starting at offset zero and jumping the amount in each header (or plus the size of the header if it is not included in the size field), and stop when you find a free block (positive number). Then return the address for this block in memory and change the number to a positive one. And remember to return the address AFTER the header.

return block_address+sizeof(blockHeader);

When you free a block you do:
block_address-sizeof(blockHeader)

Do a sanity check and make sure it is a positive number and the heap is not corrupted or the program can done something awfully wrong. Then change the number to a negative one.