-
Notifications
You must be signed in to change notification settings - Fork 17
Memory Management
This article describes the high-level aspects of memory management in MLWorks. It doesn't go into detail about the garbage collector, which will be documented in one or more separate articles.
MLWorks has its own large-scale memory management. The arena is the
first part of the address space, 1 << ARENA_WIDTH
bytes. (ARENA_WIDTH is 32 on Solaris, 31 on SunOS, Irix, and
Linux, and 30 on Win32). It's divided into spaces of 1 <<
SPACE_WIDTH bytes each (SPACE_WIDTH is 24 on all platforms, so a
space is 16 MiB). Some spaces are used in their entirety, while some
("block spaces") are further subdivided into blocks of 1 <<
BLOCK_WIDTH bytes each (BLOCK_WIDTH is 16 on all platforms: a
block is 64 KiB and there are 256 per space).
On Unix-like systems, there is no way of discovering existing memory mappings, so it is tricky to be a "good citizen". We address this in different ways on different platforms.
On SunOS, address space is not reserved; spaces up to and including
sbrk(0) are marked as TYPE_RESERVED and all other spaces are
considered fair game.
On Solaris and Linux, we locate and reserve address space by mmap(,,
PROT_NONE, MAP_SHARED, /etc/passwd, 0). /etc/passwd was chosen
as a file which always exists and is readable. If reserving
SPACE_SIZE doesn't give us a space-aligned chunk, we release it
and reserve 2 * SPACE_SIZE, which we then trim down with
munmap() to a single space-aligned chunk. This sounds tedious but
our experience was that after doing this once we would generally get
space-aligned chunks subsequently. On Irix, we use the same technique
but with mmap(,, PROT_NONE, MAP_SHARED | MAP_AUTORESRV, /dev/zero,
0)
On all Unix-like platforms, we map actual memory with mmap(,,
PROT_READ | PROT_WRITE | PROT_EXEC, MAP_FIXED | MAP_PRIVATE,
/dev/zero, 0). On SunOS we release actual memory with munmap().
On other Unix-like platforms, we use mmap(,, PROT_NONE, MAP_FIXED |
MAP_SHARED, device, offset), with /dev/zero on Irix and
/etc/passwd on Solaris and Linux.
On Linux we have a hard-wired ARENA_LIMIT of 0x60000000
because experiment (in about 1994) showed us that "mmap()s past
0x60000000 will break Linux." I don't suppose that's been true for a
long time.
On Win32, we reserve address space in a broadly similar way, but using
VirtualAlloc(,, MEM_RESERVE, PAGE_NOACCESS) and release it with
VirtualFree(,, MEM_RELEASE). We map actual memory with
VirtualAlloc(,, MEM_COMMIT, PAGE_EXECUTE_READWRITE) and unmap it
with VirtualFree(,, MEM_DECOMMIT).
Blocks in a block space may be mapped and unmapped individually. Memory in a non-block space may be partly-used, in which case only the lower part of it is mapped.
Per-space information is looked up in arrays large enough to cover the whole address space, not just the arena. The following arrays exist:
| Name | Element Type | Description |
|---|---|---|
space_type |
byte |
Space type (see below) |
space_extent |
size_t |
The number of bytes mapped in this space (-1 for an unused space, -2 for the first block space, 0 ). |
space_info |
void * |
Meaning depends on space_type.
Also known as SPACE_MAP(s). |
space_gen |
struct ml_heap * |
Structures for the ML garbage collector. |
For block spaces, the space_info points to a "block map", an array
of byte which has the same semantics per-block as space_type
has per-space. This block map is statically allocated for the first
block space. Once that block space is created, a single block map for
all the other spaces is allocated within it, and the space_info
for any subsequent block map is simply a pointer into this large block
map.
The following space and block types are used:
| Type | Value | Meaning |
|---|---|---|
| TYPE_RESERVED | -2 | A space with address space not claimed by MLWorks, or a block which is used by the MLWorks allocator. |
| TYPE_BLOCKS | -1 | The type of a block space. |
| TYPE_FREE | 0 | Address space claimed by MLWorks (without mapped memory). |
| TYPE_ML_HEAP | 1 | (spaces) Used for the ML heap. |
| TYPE_FROM | 2 | (spaces) Used for the ML heap, and being copied from by an ongoing garbage collection. |
| TYPE_ML_STACK | 3 | (blocks) used for an ML stack |
| TYPE_C_HEAP | 4 | (blocks) C heap area |
| TYPE_ML_STATIC | 5 | (spaces) static (non-moving) ML objects. |
| TYPE_C_STACK | 6 | (blocks) used for the C stack |
MLWorks includes implementations of the standard C heap functions
malloc, free, and realloc. It is a simple address-ordered
first-fit allocator, based on blocks of type TYPE_C_HEAP. This
prevents the OS-provided library implementation (which on Unix-like
systems may well be based on sbrk()) from interfering with our
memory-mapping arena management.
Care is taken to cope with misbehaving clients who apply free() to
non-allocated pointers. Care is also taken to emulate the behaviour
on each operating system of the well-known corner cases malloc(0),
realloc(NULL, 0), and realloc(p, 0), because client code may
depend on it.
(We don't have documentation on the thread system yet).
MLWorks includes its own cooperative thread system. Each thread
(apart from the "top thread" — the main 'thread' of the process, in
which the process is started by the operating system — which is only
used for managing the thread scheduler) can run either ML or C, and
has separate stack areas for ML and for C (this simplifies scanning
the ML stack during garbage collection). Those stack areas are
allocated, with TYPE_ML_STACK and TYPE_C_STACK, using the
block allocator, when the thread is created.
Almost all objects on the ML heap are moved (copied) by the garbage
collector. However, there is support for "static objects" which do
not move. For these, there is a simple per-space-address-ordered
first fit allocator, using spaces of type TYPE_ML_STATIC. It
appears that this is only used for (a) objects too large to fit into
the "creation space" (nursery generation), and (b) "byte array"
objects which are explicitly allocated as static by a call from ML
into the runtime; these are used for the foreign function interface.
The per-space header objects to manage this ML static heap are found
via the space_info map.
Each space of TYPE_ML_HEAP is a single generation of the ML heap.
space_gen[SPACE(value)] is a struct ml_heap structure to
manage that generation. There is a chain of generations, leading from
the creation space creation to the oldest generation. Generations
are added on demand. Garbage collection collects a single generation
at a time (the 'condemned generation'), and surviving objects are
promoted to the 'survivors generation'. The survivors generation may
be an existing older generation, or may be newly-created (inserted
into the chain). After the collection, the condemned generation
(which is now empty) may be removed from the chain or may remain in
it. Thus the number, size, and relative 'age' of the generations is
determined dynamically by GC policy code.
Each static ML object belongs to a specific generation, and shares the policy decisions (collection, promotion, and so on) of that generation.