free()ing memory

[Solar]

I could look up previous art, but perhaps someone can enlighten me without me having to dig deep into foreign code:

The subject is malloc() / free(). Maintaining a list of free memory chunks is easy enough. Extending heap with system calls (brk, sbrk) is easy, too.

But how do I return heap to the system when free() is called? Especially if the last (highest-address) chunk is still allocated? I'm absolutely stumped on this one. PDCLib v0.4 will have a free() that returns the chunk to the free list, but not to the system - how would that be done?

(Please no pointers to BGET or dlmalloc etc. - I would like to keep this theoretical, to keep my mind open for ideas of my own.)

[zloba]

perhaps there is a syscall to indicate that a chunk of memory is not actually in use? so the system can unmap the pages..

[durand]

Ok. You could also ask why you need to return the memory to the system when it's been requested specifically to be handled locally? Here's an idea or two.


1. You could minimize the impact of such scenarios by reducing the size of the slab requested. So, in worst case, 16 KB is lost in a partially used memory region.

2. You could modify your kernel to support partial free'ing of memory.


I know it's been done somewhere, but there's a proof that shows that you can't predict/determine the efficiency of a memory allocator with regards to fragmentation. You can just show that it works OK.. I suppose this is a kind of fragmentation, in it's way.

If you're going to write a memory allocator, I still highly recommend: http://www.usenix.org/event/usenix01/bonwick.html

[distantvoices]

If the free chunk is between two allocated places - and even if you think it might be nifty to return it to the system - don't do it, for it would cause too much hassles around the edges.

Shrink the heap where you let it grow: at the end.

If you collect enough space at the end of the heap to get in total a few pages to return, adjust the pointers and alloc counters and return that memory to the system. have it adjust the vmm entry/entries accordingly. Me f. ex. only extends the vmm entry for the heap by pages. This thing can grow/shrink at needs.

So, the free would have just an additional task: check if by any chances by merging adjacent chunks at the end of the heap pages can be freed.

just my two cent.

stay safe.

[Pype.Clicker]

But how do I return heap to the system when free() is called? Especially if the last (highest-address) chunk is still allocated?

afaik, all you can do is using brk with a value lower than the current end-of-heap-address ... that will make your room shrink.

There doesn't seem to have a function to return areas located within the data segment to the system, much like you cannot release something in the middle of the stack. Now indeed, "dismissing" pages (e.g. telling the system it's pointless to swap them out because they actually contain nothing but garbage) would indeed be a nice optimization, but i don't think there's a POSIX interface for that. maybe you can indeed imagine a special "dismiss_page_range(void* base_address, void* limit_address);" system call that would just noop in the case of a host system that just has BRK().

[Solar]

Hmmm... there is mmap(), of course... well, when the time has come I'll look into previous art anyways. I just thought someone here had any bright ideas that just didn't occur to me.

Thanks for the input, in any case.