168 lines
6.2 KiB
Groff
168 lines
6.2 KiB
Groff
.TH
|
|
memory allocator
|
|
.SH
|
|
Introduction
|
|
.PP
|
|
Standard C libraries come equipped with a general purpose memory
|
|
allocator \- \fCmalloc\fP.
|
|
The programming interface is simple and powerful.
|
|
This paper describes a fresh \fCmalloc\fP library with some new
|
|
capabilities
|
|
capabilihich maintains this
|
|
interface, but presents a plethora of configuration options.
|
|
|
|
|
|
.SH
|
|
Background
|
|
.PP
|
|
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.
|
|
.SH
|
|
Implementation
|
|
.PP
|
|
This allocator uses a
|
|
can be reclaimed
|
|
|
|
The \fCmalloc\fP library is a good general purpose specification
|
|
for a memory allocator.
|
|
This implementation strives for a high degree of compatibility
|
|
with the \fCWATCOM\fP implementation, higher performance and
|
|
better memory utilization.
|
|
.PP
|
|
A traditional \fCmalloc\fP is based upon \fCsbrk\fP 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 \fCmmap\fP and \fCmunmap\fP can
|
|
allocate and release memory at any location in the data segment.
|
|
This allocator is based upon \fCmmap\fP and \fCmunmap\fP.
|
|
.PP
|
|
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.
|
|
.PP
|
|
|
|
|
|
|
|
of free
|
|
\fCSbrk\fP 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.
|
|
.PP
|
|
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().
|
|
.PP
|
|
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.
|
|
.PP
|
|
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
|
|
.SH
|
|
BAND ALLOCATOR
|
|
.PP
|
|
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.
|
|
.SH
|
|
BAND TUNING
|
|
.PP
|
|
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.
|
|
.SH
|
|
LIST ALLOCATOR
|
|
.PP
|
|
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.
|
|
.PP
|
|
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.
|
|
.SH
|
|
LARGE ALLOCATOR
|
|
.PP
|
|
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.
|
|
.SH
|
|
IMPLEMENTATION
|
|
.PP
|
|
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:
|
|
.nf
|
|
original new difference action
|
|
SMALL SMALL same band return original
|
|
MEDIUM MEDIUM MEDIUM list_resize().
|
|
LARGE LARGE <PSIZ return original
|
|
* * * alloc new and copy.
|
|
.fi
|
|
.sp
|
|
More work may be needed here.
|
|
|
|
.SH
|
|
CONFIGURATION
|
|
.PP
|
|
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.
|
|
.PP
|
|
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.
|