Memory Allocator

Overview

Ejscript provides an application-specific memory allocator to use instead of malloc. This allocator is part of the Multithreaded Portable Runtime (MPR) and is tailored to the needs of embedded applications. It is faster than most general purpose malloc allocators for these workloads. It is deterministic and allocates and frees memory in constant time O(1). It exhibits very low fragmentation and accurate coalescing.

The allocator uses a garbage collector for locating unused memory. The collector is a generational, cooperative and non-compacting collector. The use of a garbage collector is somewhat unusual in a C program. However, garbage collection it is especially well suited for long running applications like a web server, as it eliminates most memory leaks. Unlike traditional memory allocation where free must be called to release memory, Ejscript uses the opposite approach where memory that must be retained, needs to be actively managed to prevent garbage collection. This means that a managed reference must be held for all active memory.

Allocator

The allocator is optimized for frequent allocations of small blocks (< 4K). It uses a scheme of free queues for fast allocation. Memory allocations are aligned on 16 byte boundaries on 64-bit systems and otherwise on 8 byte boundaries. It will return chunks of unused memory back to the O/S.

Ejscript Allocator

Ejscript 1.0 used memory contexts for all memory allocations. This required many APIs to have a memory context as the first parameter. Ejscript 2 does not require this and these APIs have removed the memory context parameter.

Error Handling

It is difficult for programmers to consistently check the result of every API call that can fail due to memory allocation errors. Calls such as strdup and asprintf are often assumed to succeed, but they can, and do fail when memory is depleted.

A better approach is to proactively detect and handle memory allocation errors in one place. The MPR allocator handles memory allocation errors globally. It has has a configurable memory redline limit and memory depletion policy handler. Ejscript configures this memory limit so that memory depletion can be proactively detected and handled before memory allocations actually fail. When memory usage exceeds a pre-configured redline value, the depletion handler is invoked. The application can then determine what action to take. Ejscript will restart automatically in such circumstances.

Garbage Collection

The MPR garbage collector will run periodically to reclaim unused memory and potentially return that memory to the Operating System. The collector runs in its own thread, but is cooperative, in that each other thread must yield to the collector before memory can be reclaimed. Worker threads yield to the collector by calling the mprYield API. This strategy permits worker threads to allocate temporary memory without fear. The memory will not be prematurely collected until the worker explicitly acknowledges and yields to the collector by calling mprYield.

To prevent collection of a memory block and retain the block over a yield point, the application must hold a managed reference for the block. A managed reference, is a reference to an allocated block that will be marked as active during a collection cycle by the Owning Blocks manager function. Manager functions are defined when allocating blocks that will hold managed references.

Collection Phases

The collector reclaims memory in three phases: Wait, Mark and Sweep. The Wait phase waits for all threads to yield. This quiesces the system for reliable collection. NOTE: this does not mean that all request activity must cease. Rather, pre-determined rendezvous yield points are inserted in key locations in the Ejscript HTTP processing engine.

The Mark phase traverses memory and marks all blocks that are currently being used. The Sweep phase finally reclaims all blocks that are not marked.

Marking Blocks

The Mark phase beings with a set of known root memory blocks. The ultimate root is the Mpr object returned from the mprCreate API. However, other roots can be added at any time via mprAddRoot. For each root, the collector invokes the manager function defined when the block was allocated. It is the responsibility of that manager function to call mprMark on every managed reference owned by the block. The mprMark function will then invoke the manager for these managed references and so on. In this manner, managed memory forms a tree from the roots to the leaves and the mark phase visits every managed block currently in use.

Allocating Memory

Managers are defined when allocating a block of memory. For example, this code will allocate a block that will contain a managed reference to an allocated string:

char **block = mprAllocObj(char*, manageBlock);
*block = sclone("Hello World");

This will allocate a block sufficient to store one character pointer and will define the manageBlock function as the manager for managed references in that block. The sclone function allocates a string block and copies the string argument. The mprAllocObj function is used to allocate structures with managers. Use mprAllocMem to allocate a block of memory and reserve room for a manager function. Then use mprSetManager to define a manager function.

Managers

A manager function is invoked by the collector during each collector Mark phase of the collection cycle. The manager is passed a reference to the block and a flags word. The flags are set to either MPR_MANAGE_MARK during the Mark phase and to MPR_MANAGE_FREE if the collector determines the block is to be freed.

void manageBlock(char *ptr, int flags) 
{
    if (flags & MPR_MANAGE_MARK) {
        mprMark(*ptr);
    } else if (flags & MPR_MANAGE_FREE) {
        /* Custom code when the block is freed */
    }
}

A common technique it to define a top level application structure which will be the root memory block for the entire application. Store top level managed references in this block and call mprAddRoot to define it as a root block.