memory allocator

Introduction

Standard C libraries come equipped with a general purpose memory allocator - malloc. The programming interface is simple and powerful. This paper describes a fresh malloc library with some new capabilities capabilihich maintains this interface, but presents a plethora of configuration options.

Background

Traditional malloc implementations are a first-fit allocator [KNUTH] using the service sbrk to change the size of the data segment. The first fit model is balances performance and fragmentation of memory. The sbrk model is not so good, as memory can only be released to the system when the 'end' of the data segment is not in use.

Implementation

This allocator uses a can be reclaimed The malloc library is a good general purpose specification for a memory allocator. This implementation strives for a high degree of compatibility with the WATCOM implementation, higher performance and better memory utilization.

A traditional malloc is based upon sbrk to change the boundary of the data segment. A failing of this is that memory can only be released to the Operating System if it is at the very end of the data segment. More modern services, such as mmap and munmap can allocate and release memory at any location in the data segment. This allocator is based upon mmap and munmap.

Memory allocation is typically performed by maintaining a list of available memory fragments; if a request cannot be fulfilled from a fragment, it asks the system for more memory. Releasing memory puts a corresponding node into this list. This mechanism is quite proficient at keeping memory in as large a segment as possible, to minimize the number of requests to the system, however the list must be scanned for each alloc and release.

of free Sbrk alters the boundary of the data segment of a program This malloc library uses different allocation strategies for different sized objects in an attempt to obtain high performance and low waste.

The standard malloc library is based upon an sbrk() model; attempts to physically reduce the data size of the program can only be made when the top of the heap is unused. QNX also thwarts this by refusing to shrink the data segment in brk() to avoid interference with mmap().

The system interface in this allocator relies upon two functions: morecore(n); and donecore(n,s). Morecore aquires a quantity of memory; donecore indicates the allocator no longer needs this space. This implementation uses mmap() in morecore() to acquire memory and munmap() in donecore() to release it.

The allocator divides sizes into three broad categories: small, medium and large. The boundaries for these sizes is configurable with some constraints. Small objects are managed by band.c, medium objects by list.c, and large objects by large.c

BAND ALLOCATOR

Band.c is a fixed-size allocator. A set of objects are allocated to form a block, and within the block managed by a single list. When a block becomes unused (all objects in the block are on it's free list), the block is returned to another allocator. When all blocks are fully used, a new block is allocated. Allocation from and return to a block are constant time operations. The allocator maintains a 'hint' which, if valid, points at the lowest address block with available entries. Blocks are stored on a sorted list, and the allocator rejects attempts to return an object to the wrong block, eliminating at least one type of user error.

BAND TUNING

The bands are defined by an Band structure, which can be tuned for the size of object and number of objects in a block. Furthur tuning may be available by changing the hint mechanism. It is currently attempts to empty blocks near the beginning of the list first, however some applications may find that maintaining it at the last block allocated from will enhance performance.

LIST ALLOCATOR

To minimize fragmentation, medium sized objects are kept on a classic first fit allocator. Available segments are released to donecore() when they exceed certain size and alignment constraints. The allocator is bound to a somewhat larger block size than is typical; this is to minimize the co-allescing operations on release of memory.

The allocator keeps a signature as well as length at the beginning of the object. Attempts to release memory lacking this signature are rejected, eliminating a source of user error.

LARGE ALLOCATOR

The large allocator maintains no free list. Objects have a small header and are allocated in sets of pages from morecore(). When an object is released, it is immediately returned to donecore(). Unfortunately, the small header means that user requests are never page-aligned, and allocating an exact multiple of pagesize will waste almost a page. This could be fixed with an unseemly familiarity with the other allocators.

IMPLEMENTATION

In all allocators, the work immediately preceding the object contains the size, in bytes, of the object. This allows the traditional malloc() interface to be built readily: an allocation request is diverted to one of the above allocators based upon the request size. A free() request examines the size and passes the object on to the appropriate allocator. Realloc() causes a bit of a concern, however. Growing or shrinking an object may cause it to move from one allocators domain to another. The rules currently enforced are:
original	new	difference	action
SMALL          SMALL    same band      return original
MEDIUM         MEDIUM   MEDIUM          list_resize().
LARGE          LARGE    <PSIZ           return original
*               *         *             alloc new and copy.

More work may be needed here.

CONFIGURATION

The principal configuration requirement is deciding where to split the allocation domains. Once the domains are configured, selecting the band's is of next importance. Balancing the number of bands, block size and factoring are of import.

To augment this operation, the library routines have a configuration option to keep detailed statistics upon use. The tables generated by these statistics may be used to configure the allocator for particular applications; this configuration may be automated.