Appweb / MPR Memory Allocator

Appweb provides an application-specific, high performance memory allocator. 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, Appweb 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.

The Appweb 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.

In practice there are thus two kinds of memory:

• Managed memory — This is memory allocated via Appweb/MPR which is actively managed by the garbage collector. The user is responsible for marking the memory as being active by calling the mprMark API from a memory manager callback. 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 or pass it to Appweb APIs that expect managed memory.

You can use both MPR managed memory and malloc allocated memory in your application. However, Appweb APIs expect to receive appweb allocated memory in most cases, so you should not pass malloc memory into Appweb APIs unless explicitly permitted in the documentation. The Appweb garbage collector will not interfere with malloc memory and you can safely use it in your application for other purposes.

Garbage Collection

The 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 and every Appweb thread must yield to the collector before memory can be reclaimed. Appweb threads yield to the collector by calling the mprYield API. This strategy permits Appweb threads to allocate temporary memory without fear. The memory will not be prematurely collected until the worker thread explicitly acknowledges and yields to the collector by calling mprYield. Appweb 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 calling mprMark() from a manager callback function which will be invoked by the garbage collector during a collection cycle. Manager functions are defined when allocating memory via the mprAllocMem API. 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 only when the application must sleep or block waiting for some event. You should never call mprYield(MPR_YIELD_STICKY) and then continue normal processing as the garbage collector may run at anytime after calling mprYield. After sleeping, the thread must immediately call mprResetYield() to unyield and resume normal operation.

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

Yielding Functions

The following Appweb functions will yield. When calling these functions, you must have retained all local memory as the garbage collector may run while calling these APIs.

• 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

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 Appweb HTTP processing engine. You normally do not need to worry about this.

The Mark phase traverses memory and marks all blocks that are currently being used. When complete, user threads are resumed and the Sweep phase runs in parallel to reclaim all blocks that are not marked in-use.

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);

mprAddRoot(blk);

This will allocate a new structure and define "manageBlock" as the manager function for the structure.

Managers

A manager function is invoked by the collector during the Mark phase 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 callback function 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 in your manager callback at this time. 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.

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.

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.

Retaining Memory

To retain memory blocks, you must ensure the block 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. This is normally not onerous as any valuable structure will typically be stored or referenced by some other object.

Alternatively, if you have no such reference, 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 block's manager routine.

If you only require an allocated block temporarily, and do not want to keep the memory across a yield point, you do not need to retain a reference or call mprAddRoot. When the garbage collector next runs, the memory will be automatically collected because there will not be a managed (marked) reference to the block.

If you have a single temporary memory allocation that you need to retain over a yield point, you can use mprHold to retain and mprRelease when you do not require the memory anymore. Note that you must never access the memory after calling mprRelease as the garbage collector may have already collected the memory. It is not safe to use the mprAlloc with a separate mprHold call from foreign (non-Appweb) threads, as these operations will not be atomic. Instead use the MPR_ALLOC_HOLD flag with mprAllocMem from foreign threads. You can also use the convenience routine palloc which wraps the call to mprAllocMem(MPR_ALLOC_HOLD) and returns permanently retained memory. Use pfree to release memory allocated with palloc. In this manner palloc/pfree operate like malloc/free but use the Appweb allocator instead of the standard malloc allocator.

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. The mprAllocMem function may be used from foreign non-Appweb threads if used with the MPR_ALLOC_HOLD flag which will atomically allocate the memory and hold it until mprRelease is called.

Convenient References

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

Appweb 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 Appweb and using the Garbage Collector.

Must Mark to Retain Managed Memory

Any managed memory must be marked to be retained past the next garbage collection cycle.

Don't Mix Memory

You must not mix managed 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

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

Error Handling

It is difficult and error-prone for programmers to always check the result of every API call that can possibly 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 Appweb allocator handles memory allocation errors globally. It has a configurable memory redline limit and a memory depletion policy handler. Appweb 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, Appweb will restart in such circumstances.