Thursday, May 20, 2004
Mixed Memory Allocator
A hybrid approach to glibc malloc()
As we all know, modern computer systems use hundreds of megabytes of system memory to support their operation. On a shell, you can almost always stay under a hundred if you don't run any servers; but in GUI, you may reach 200, 300, 500MiB easily. Some applications use 20MiB, 40MiB, some start at 30 and grow to 80 or 100MiB, and stay there.
Most programs use a class of function calls in glibc known as the malloc() function calls. These include malloc(), calloc(), resize(), and free(). C++ programs use new and delete, which are usually rooted in these functions, but not necessarily.
Because of the way the allocator works, it may be theoretically possible to increase its efficiency by anywhere from a minor, barely noticable amount to entire orders of magnitude. This would be done by attempting to balance the two methods used for allocation into a single, more effective method which neither wastes excess memory inherantly nor is forced to hold massive amounts of unused memory from the system.
Please note that the scope of this document is Linux only, and systems not supporting mmap() or equivalent calls will not be able to benefit from the new allocator scheme detailed within.
The Current Method
The malloc() class of functions has two current modes of operation, both flawed in different ways. The major method, used in most allocators on most platforms, uses the heap; while the othe method, available on Linux and other Unixes, uses the mmap() class of system calls.
Most calls to glibc malloc() functions for allocation use the heap. The simplest explaination of this method is that the heap shrinks and grows as needed. If there is not a segment of ram larger than or equal to the requested allocation, the heap is expanded via brk() to create space for the new segment. If there is free space on the end of the heap, brk() is used to shrink it, freeing the memory to the system.
The problem with the heap is that it may only exist as one large chunk. Its base (beginning) never changes, and its endpoint always must be no less than the last used piece of memory. This means that any holes in the heap are allocated, and unavailable to the system. They take up memory; and unused pages get swapped out while they're not in use, meaning that rather than just freeing and reallocating ram, a meaningless disk access must be done to give the ram back to the system and to reallocate it from the system.
One problem with the heap is that long-running applications can build up much intermittent fragmentation, and sometimes even spike for ram usage and leave junk at the top. Thus, a view of the heap may look as such for most of the application's running time:
With extremely large calls, by default those >128KiB, malloc() will become a wrapper for mmap(). mmap() maps a set of physical pages to a set of virtual pages; but it always maps whole pages. The problem with mmap() is much clearer: If you map a byte, you use 4k. 10 1 byte allocations may look like this:
The advantage of mmap() is that any one of these can be freed as soon as it is no longer in use. Unfortunately, it still bloats the ramspace.
A Hybrid Solution
On systems supporting mmap(), a hybrid solution would most likely increase the efficiency of memory allocation. Instead of using the heap or mmap(), we could use mmap()ed segments that act as heaps; that is, create a bunch of "mini-heaps" by mmap()ing contiguous memory as needed. This still leaves us vulnerable to fragmentation within pages; but entire empty pages can be immediately freed back to the system. Also, complex mappings can alleiviate situations where a new page cannot be mapped "between" two old pages.
Instead of using the heap, malloc() could use mmap() to map private, read/write, anonymous pages with the MAP_FIXED flag. This will fail if the page cannot be mapped to the exact address specified. This would allow malloc() to react by mapping somewhere else.
The basic function would be augmented by mapping the same physical pages around in other areas. Consider the case:
[**--] ____ [-***]
Where we need 7 segments to scale on here. We could satisfy this easily:
Map another page between the original two. If this mapping fails, however, we need to do one of two things: Map 2 new pages somewhere; or, my preferred method, map the other 2 pages somewhere else where we CAN map a third inbetween:
[**--] ____ [-***]
This wouldn't map extra system memory, and so we'd save a page (3 available units, plus the 1 left in the page we didn't alloc, would be 4 units, one page in our example); however, you would have to track your mapped pages and note which are which, because the multiple mapping will make allocations to one area of virtal memory space affect another. Because the above and below first and third page are the same physical memory, we must treat them as a single area of ram in our allocator.
Handling and tracking these types of allocations would be complex, but the trade-off would be good. Consider:
This is our original heap from the first example. This time, however, we can free some ram back to the system.
[****] ____ ____ ____ [---*] ____ ____ ____ [*--*]
Now, instead of using 9 pages, we use 3.
This hybrid allocator should fall back on the heap allocator if the system returns ENOMEM. ENOMEM indicates that either the system is out of memory, or that the process may not make any more memory mappings due to resource restrictions. Although running out of memory isn't recoverable, running out of your allotted memory mappings can and should be recovered from by using the heap as a fallback.
It would be very interesting to see a hybrid allocator included in glibc. It would take much coding, but the benefits could be very substantial if handled properly.