Memory Allocation

Overview

ESP 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 (GC) 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 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, ESP uses the opposite approach. Memory that must be retained, must be actively managed to prevent garbage collection. This means that a managed reference must be held for all active memory.

In practice there are thus two kinds of memory:

• Managed memory — This is memory allocated via the MPR which is actively managed by the garbage collector. The user is responsible for marking the memory as being active via the mprMark API. The collector will automatically reclaim the memory when it is no longer marked as being actively used.
• Malloc memory — This is memory allocated directly or indirectly by malloc, and is not managed by the garbage collector. The user is responsible for explicitly calling free() when the memory is no longer required. You must not call mprMark() on such 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.

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 a configurable memory redline limit and a memory depletion policy handler. ESP 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. Typically, ESP will restart 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 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. ESP will ensure threads call mprYield when waiting for I/O or when a request is complete. Users only need to explicitly call mprYield when they are doing a long-blocking operation.

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 by mprMark() during a collection cycle by the parent block's manager function. Manager functions are defined when allocating blocks that will hold managed references. See below for more details.

Yielding

There are two kinds of yield:

• Short yields — used to yield to the GC once
• Long or sticky yields — used to put the thread into a semi-permanent yielded state

A short yield is achieved by calling mprYield(0) which will test if garbage collection is required and if so, will wait until the collection is complete. If no collection is required, the call returns immediately without blocking.

A long yield is achieved by calling mprYield(MPR_YIELD_STICKY). This will yield to the garbage collector and immediately return leaving the thread in a "yielded" state. This is used when the application must sleep or block waiting for some event. When the thread resumes, it must call mprResetYield() to resume normal operation.

For high-performance needs, the mprNeedYield() macro may be used to test if yielding is required before calling mprYield.

User code or handlers may yield at anytime provided they have secured all their temporary memory.

Yielding Functions

The following functions are the only functions in ESP that yield:

• httpFlushQueue(, HTTP_BLOCK)
• httpConnect used for client requests
• httpRead() used for client requests and to read responses
• httpReadBlock(, HTTP_BLOCK) used for client requests and to read responses
• httpSendBlock(, HTTP_BLOCK)
• httpWait() used for client requests
• httpWriteBlock(, HTTP_BLOCK)
• httpWriteUploadData client side
• mprDestroy
• mprGC
• mprSleep
• mprWaitForSingleIO
• mprWaitForIO
• mprWaitForEvent
• mprWaitTillIdle
• mprYield

When calling any of these routines, you must be prepared for the GC to run and so you must have secured all temporary allocations.

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 ESP 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 reference to a managed string and a reference to an un-managed malloc block.

typedef struct MyBlock
    char    *managedString;
    void    *privateMalloc;
} MyBlock;

MyBlock *blk = mprAllocObj(MyBlock, manageBlock);
blk->managedString = sclone("Hello World");
blk->privateMalloc = malloc(1024);

This will allocate a new structure and define manageBlock as the manager function for the structure. If you need to keep the allocated structure, you must ensure the blk reference will be marked during the garbage collector mark phase. To do this, you must ensure the reference is marked via mprMark during some other object's manager function. Alternatively, you can call mprAddRoot to specify that this reference is a top level root of a new memory tree. You should do this sparingly. It is more effective to mark the reference from another manager routine. If you have a single memory allocation that you need to retain, you can use mprHold to retain and mprRelease when you do not require the memory anymore.

If you only require the allocated structure temporarily, you do not need to retain a reference or call mprAddRoot. In this manner, the memory will be automatically collected during the next garbage collection sweep because there will not be a managed (marked) reference to the block.

The mprAllocMem may be used 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 and also during the Sweep phase if the block is actually being freed. When called, 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 during the sweep phase if the collector determines the block is to be freed.

void manageBlock(MyBlock *blk, int flags)
{
    if (flags & MPR_MANAGE_MARK) {
        mprMark(blk->managedString);
        /* Don't mark privateMalloc */
    } else if (flags & MPR_MANAGE_FREE) {
        /* Custom code when the block is freed */
    }
}

When the manager is invoked during the Mark phase, all MPR threads are stopped — so the system is effectively single threaded. You should NOT do anything other than call mprMark at this time.

When the manager is invoked during the sweep phase, other threads are resumed and running, i.e. the sweeper thread runs in parallel with the application. So you must take care not to call locking primitives or block at this time.

When sweeping, the block to be freed should have no remaining references and thus be fully isolated from the application — so there is typically little to do during the collection/free phase other than close and release external resources. Note that it is safe to call mprMark with NULL reference. This is a convenient pattern so you do not need to test if the element is null or not.

Order of Invocation

During the mark phase, managers are called recursively from parent calls to mprMark. Thus the blocks are visited top down. During the sweep phase, managers are called in any order, i.e. children may be visited before their parents. It is important to write manager free code to handle this. Note: the actual memory for the blocks to be freed will only be unpinned once all managers have been invoked. So whether the child or parent is visited last, the memory for both will be accessible until the end of the sweep phase when all freed blocks are released.

Convenient References

ESP defines two empty fields that can be used by request handlers to hold managed references. The HttpStream.data field is marked by the HttpStream manager. A handler can store a managed-memory reference in this field. The HttpStream manager will then call mprMark(conn->data) to mark the reference as active and required.

Similarly, HttpQueue.queueData field is marked by the HttpQueue manager. A queue stage (filter or handler) can store a managed-memory reference in this field. The HttpQueue manager will then call mprMark(q->queueData) to mark the reference as active and required.

ESP defines two fields that can be used to store un-managed memory references: HttpStream.staticData and HttpQueue.staticData. Use these to store references to memory allocated by malloc.

Another 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.

Simple Rules

Here are some simple rules for allocating memory with ESP and using the Garbage Collector.

Must Mark to Retain Managed Memory

Any memory allocated from the MPR must be marked to be retained past the next garbage collection cycle.

Don't Mix Memory

You must not mix MPR allocated memory and non-managed memory. This means don't mark un-managed memory that has been allocated via malloc(). And you must not call free() on managed memory allocated from the MPR.

Define a Manager

If you allocate a managed structure that has references to managed memory, you should define a manager function that invokes mprMark on the structure elements that are managed references.

Free External Resources

If you open files or allocate external resources, your manager should close or release these when invoked with MPR_MANAGE_FREE as the manager flags.

Yield in Long Loops

Insert calls to mprYield if your code allocates a lot of memory in a tight loop. You should not run for more than 1/10 second without yielding.

Don't Call from Foreign Threads

ESP uses many APIs that are not thread-safe. This is because ESP code runs on a serialized per-thread event dispatcher. If you call from a foreign non-MPR thread into ESP, you will corrupt critical ESP structures. Rather, use mprCreateEventOutside to schedule an event callback to run inside the MPR to run your code.