1

I'm curious about one aspect of heap management in linux, and particularly in ubuntu's build of glibc 2.17.

I understand that the last chunk in each heap, the top or wilderness chunk, tends to be free, and gets bits carved out of it and added to it and has its size changed with sbrk() when needed (if it's the first heap?).

However, what I can't find is this: is it possible that the wilderness chunk might ever be allocated, meaning that the highest chunk in the heap is busy?

The difference may seem of theoretical interest only, but it has some implications related to whether or not it is possible to analyze a heap in memory without external metadata.

1 Answer 1

1

I don't know the glibc implementation, but in Doug Lea's malloc the answer is "no". Quote from the link:

treat the wilderness chunk as ``bigger'' than all others, since it can be made so (up to system limitations) and use it as such in a best-first scan. This results in the wilderness chunk always being used only if no other chunk exists, further avoiding preventable fragmentation.

I guess there is one case in which the invariant could be technically violated: if the user allocated a chunk that was exactly the size of all remaining system memory.

There is a somewhat more in-depth discussion of how the wilderness should be managed in Wilson; Johnstone; Neely; Boles: "Dynamic Storage Allocation: A Survey and Critical Review", Int'l Wkshp on Mem Mgt, 1995.

1
  • This is a highly irritating edge case. Of course it won't be allocated except if a request for exactly the amount of memory remaining in the heap is made... I was honestly hoping to avoid writing a test program for that, but I guess I have to. Jul 7, 2013 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .