6. Allocation

6.1. Manual allocation

Note

Not all pool classes support this interface: automatically managed pools typically support none of it, and even manually managed pools may not support the whole interface. Consult the pool class documentation for details. For example, the MVT (Manual Variable Temporal) pool class supports deallocation via mps_free() but allocation must use allocation points, as described below.

mps_res_t mps_alloc(mps_addr_t *p_o, mps_pool_t pool, size_t size)

Allocate a block of memory in a pool.

p_o points to a location that will hold the address of the allocated block.

pool the pool to allocate in.

size is the size of the block to allocate. If it is unaligned, it will be rounded up to the pool’s alignment (unless the pool documentation says otherwise).

void mps_free(mps_pool_t pool, mps_addr_t addr, size_t size)

Free a block of memory to a pool.

pool is the pool the block belongs to.

addr is the address of the block to be freed.

size is the size of the block to be freed. If it is unaligned, it will be rounded up to the pool’s alignment (unless the pool documentation says otherwise).

The freed block of memory becomes available for allocation by the pool, or the pool might decide to make it available to other pools, or it may be returned to the operating system.

Note

mps_free() takes a size parameter because it is most efficient to do so. In most programs, the type of an object is known at the point in the code that frees it, hence the size is trivially available. In such programs, storing the size on the MPS side would cost time and memory, and make it hard to get good virtual memory behaviour because of the need to touch the object in order to free it. As it is, the deallocation code doesn’t have to touch the dead object at all.

6.2. Allocation points

Allocation points provide fast, inline, nearly lock-free allocation. They allow code to allocate without calling an allocation function: this is vital for performance in languages or programs that allocate many small objects. They must be used according to the Allocation point protocol.

mps_ap_t

The type of allocation points. It is a transparent alias for a pointer to mps_ap_s.

mps_res_t mps_ap_create_k(mps_ap_t *ap_o, mps_pool_t pool, mps_arg_s args[])

Create an allocation point in a pool.

ap_o points to a location that will hold the address of the allocation point, if successful.

pool is the pool.

args are keyword arguments specific to the pool class to which pool belong. See the documentation for that pool class. (Most pool classes don’t take any keyword arguments; in those cases you can pass mps_args_none.)

Returns MPS_RES_OK if successful, or another result code if not.

Warning

An allocation point must not be used by more than one thread: each thread must create its own allocation point or points.

Note

There’s an alternative function mps_ap_create_v() that takes its extra arguments using the standard C va_list mechanism.

mps_res_t mps_ap_create(mps_ap_t *ap_o, mps_pool_t pool, ...)

Deprecated

starting with version 1.112.

Use mps_ap_create_k() instead: the keyword arguments interface is more reliable and produces better error messages.

An alternative to mps_ap_create_k() that takes its extra arguments using the standard C variable argument list mechanism.

mps_res_t mps_ap_create_v(mps_ap_t *ap_o, mps_pool_t pool, va_list args)

Deprecated

starting with version 1.112.

Use mps_ap_create_k() instead: the keyword arguments interface is more reliable and produces better error messages.

An alternative to mps_ap_create_k() that takes its extra arguments using the standard C va_list mechanism.

void mps_ap_destroy(mps_ap_t ap)

Destroy an allocation point.

ap is the allocation point to destroy.

Destroying an allocation point has no effect on blocks that were allocated from it, so long as they were successfully committed⁽²⁾ by mps_commit().

6.3. Allocation point protocol

This protocol is designed to work with incremental garbage collection and multiple threads, where between any two instructions in the client program, the MPS may run part of a garbage collection, move blocks in memory, rewrite pointers, and reclaim space. In order to reliably handle this, the allocation point protocol consists of (at least) two steps, a reserve followed by a commit.

Note

The description of the protocol assumes that you have declared your threads’ control stacks and registers to be ambiguous roots, by passing mps_stack_scan_ambig() to mps_root_create_reg(). This is the simplest way to write a client, but other scenarios are possible. Please contact us if your use case is not covered here (for example, if you need an exact collector).

When the client program is initializing a newly allocated object, you can think of it as being “in a race” with the MPS. Until the object is initialized, the MPS cannot manage it in the usual way: in particular, it cannot ensure that the new object remains correct if other objects move during its initialization. So if other objects do move, the MPS tells the client program that it has “lost the race”: the partially-initialized object may be invalid, and the client must initialize it again from scratch.

The allocation point protocol is as follows:

1. Call mps_reserve() to reserve a block of memory on an allocation point. The size of the block must be a multiple of the alignment of the pool in which the allocation point was created.

   If mps_reserve() returns MPS_RES_OK, go to step 2.

   Otherwise, the block cannot be reserved (this might happen if the MPS is out of memory).

2. Initialize the block. During this step the block must not be referenced by an exact reference, and references stored in it must not be followed.

   The block need not be initialized completely, but if the pool has an object format, then by the end of this step, the block must be capable of being passed to the format’s scan method and skip method.

3. Call mps_commit() to attempt to commit the object to the care of the MPS.

   If mps_commit() returns true, this means that the object is valid, and is now under the management of the MPS. The client program may rely on references stored in the object, and may store references to the new object in its other objects.

   If mps_commit() returns false, this means that the block is invalid. It is usual in this case to go back to step 1 and re-reserve and re-initialize it, but other courses of action are permitted.

   Note

   In this case, the reason the block is invalid because a flip took place after the call to mps_reserve() and before the call to mps_commit(). This means that references in the block may point to the old location of blocks that moved.

The usual implementation of the allocation point protocol in C is thus:

mps_addr_t p;
obj_t obj;
do {
    mps_res_t res = mps_reserve(&p, ap, size);
    if (res != MPS_RES_OK) /* handle the error */;
    /* p is now an ambiguous reference to the reserved block */
    obj = p;
    /* initialize obj */
} while (!mps_commit(ap, p, size));
/* obj is now valid and managed by the MPS */

It is not necessary to worry about going around this loop many times: mps_commit() can fail at most once per thread per flip.

mps_res_t mps_reserve(mps_addr_t *p_o, mps_ap_t ap, size_t size)

Reserve a block of memory on an allocation point.

p_o points to a location that will hold the address of the reserved block.

ap is the allocation point.

size is the size of the block to allocate. It must be a multiple of the alignment of the pool (or of the pool’s object format if it has one).

Returns MPS_RES_OK if the block was reserved successfully, or another result code if not.

The reserved block may be initialized but must not otherwise be used

Until it has been committed⁽²⁾ via a successful call to mps_commit(), the reserved block may be:

• initialized;
• referenced by an ambiguous reference;

but:

• it must not be referenced by an exact reference;
• references stored in it must not be followed;
• it is not scanned, moved, or protected (even if it belongs to a pool with these features).

Note

mps_reserve() must only be called according to the Allocation point protocol.

mps_reserve() is implemented as a macro for speed. It may evaluate its arguments multiple times.

There is an alternative, MPS_RESERVE_BLOCK(), which may generate faster code on some compilers.

MPS_RESERVE_BLOCK(mps_res_t res_v, mps_addr_t *p_v, mps_ap_t ap, size_t size)

An alternative to mps_reserve(). On compilers that do not perform common-subexpression elimination, it may generate faster code than mps_reserve() (but may not). It may only be used in statement context (not as an expression).

The second argument is an lvalue p_v, which is assigned the address of the reserved block. It takes an additional first argument, the lvalue res_v, which is assigned the result code.

mps_bool_t mps_commit(mps_ap_t ap, mps_addr_t p, size_t size)

Commit a reserved block on an allocation point.

ap is an allocation point.

p points to a block that was reserved by mps_reserve() but has not yet been committed.

size is the size of the block to allocate. It must be the same size that was passed to mps_reserve().

If mps_commit() returns true, the block was successfully committed, which means that the client program may use it, create references to it, and rely on references from it. It also means that the MPS may scan it, move it, protect it, or reclaim it (if ap was attached to a pool with those features).

If mps_commit() returns false, the block was not committed. This means that the client program must not create references to the block, rely on references from it, or otherwise use it. It is normal to attempt the reserve operation again when this happens.

It is very rare for mps_commit() to return false: this only happens if there was a flip between the call to mps_reserve() and the call to mps_commit(). Nonetheless, it can happen, so it is important not to perform operations with side effects (that you aren’t prepared to repeat) between calling mps_reserve() and mps_commit(). Also, the shorter the interval, the less likely mps_commit() is to return false.

Note

mps_commit() must only be called according to the Allocation point protocol.

mps_commit() is implemented as a macro for speed. It may evaluate its arguments multiple times.

6.4. Example: allocating a symbol

typedef struct symbol_s {
    type_t type;                  /* TYPE_SYMBOL */
    size_t length;                /* length of symbol string (excl. NUL) */
    char string[1];               /* symbol string, NUL terminated */
} symbol_s, *symbol_t;

symbol_t make_symbol(size_t length, char string[])
{
    symbol_t symbol;
    mps_addr_t addr;
    size_t size = ALIGN(offsetof(symbol_s, string) + length+1);
    do {
        mps_res_t res = mps_reserve(&addr, ap, size);
        if (res != MPS_RES_OK) error("out of memory in make_symbol");
        symbol = addr;
        symbol->type = TYPE_SYMBOL;
        symbol->length = length;
        memcpy(symbol->string, string, length+1);
    } while (!mps_commit(ap, addr, size));
    return symbol;
}

6.5. Cautions

While a block is reserved but not yet committed:

1. The client program must not create an exact reference to the reserved block (for example, by referring to the reserved block from a formatted object). All references to it must be ambiguous (for example, local variables).
2. Similar restrictions apply to a reference that has been stored in the reserved block. Such a reference might be invalid, and must not be copied to an exact reference or dereferenced. It is safe to copy such a reference if it remains ambiguous (for example, copying to a local variable or to another part of the new block).

Before calling mps_commit():

1. The new block must be validly formatted. If it belongs to an object format, then it must be correctly recognized by the format methods (the skip method must return the object’s correct size; the scan method must scan it; the is-forwarded method must report that it is not a forwarding object, and so on).
2. All exact references in the new block (references that are fixed by scanning functions) must contain valid references or null pointers.
3. The new object must be ambiguously reachable.

You do not have to initialize the whole block so long as you satisfy these conditions. For example, it is permissible to defer initialization completely (for example, by writing TYPE_UNINITIALIZED into a tag field), so long as you handle this correctly in the format methods.

However, if you do not initialize the whole block then you should beware: the uninitialized contents of the block is likely to consist of dead objects. If, due to a bug, you created an exact reference into the middle of the uninitialized block, this might by bad luck point to a dead object, which would be resurrected (and it might well contain further exact references to other dead objects). To ensure detection of such a bug promptly you should consider filling the uninitialized object with dummy values that cannot be mistaken for part of a valid formatted object (at least in the debugging version of your program).

Note

Some pool classes have debugging counterparts that automatically overwrite free space with a pattern of bytes of your choosing. See Debugging pools.

6.6. Example: inserting into a doubly linked list

This example contains several mistakes. See the highlighted lines:

typedef struct link_s {
    type_t type;                       /* TYPE_LINK */
    /* all three of these pointers are fixed: */
    struct link_s *prev;
    struct link_s *next;
    obj_t obj;
} link_s, *link_t;

/* insert 'obj' into the doubly-linked list after 'head' */
link_t insert_link(link_t head, obj_t obj)
{
    mps_addr_t p;
    link_t link;
    size_t size = ALIGN(sizeof(link_s));
    do {
        mps_res_t res = mps_reserve(&p, ap, size);
        if (res != MPS_RES_OK) error("out of memory");
        link = p;
        link->type = TYPE_LINK;
        link->prev = head;
        link->next = link->prev->next; /* (1) */
        head->next = link;             /* (2) */
        link->next->prev = link;       /* (3) */
    } while (!mps_commit(ap, p, size));
    link->obj = obj;                   /* (4) */
    return link;
}

The mistakes are:

1. Dereferencing a reference (here, link->prev) that was stored in the reserved block.
2. Making an exact reference to the reserved block (here, head->next becomes an exact reference to link). This must be deferred until after a successful commit.
3. This line makes both mistakes made by lines (1) and (2).
4. The obj slot contains an exact reference that gets fixed by the scan method, so it must be initialized before the call to commit.

A correct version of insert_link looks like this:

link_t insert_link(link_t head, obj_t obj)
{
    mps_addr_t p;
    link_t link;
    size_t size = ALIGN(sizeof(link_s));
    do {
        mps_res_t res = mps_reserve(&p, ap, size);
        if (res != MPS_RES_OK) error("out of memory");
        link = p;
        link->type = TYPE_LINK;
        link->prev = head;
        link->next = head->next;
        link->obj = obj;
    } while (!mps_commit(ap, p, size));
    head->next->prev = link;
    head->next = link;
    return link;
}

6.7. Allocation point implementation

An allocation point consists of a structure of type mps_ap_s and an associated buffer.

Allocation point and its associated buffer.

The buffer is structured as shown in the figure, with free space at the end of the buffer, committed blocks at the beginning, and (possibly) one reserved block in the middle. The mps_ap_s structure contains three addresses into the associated buffer: limit points to the end of the buffer, alloc points to the beginning of the free space, and init points to the end of the initialized blocks.

Allocation points are fast and nearly lock-free because in order to reserve space for a new block, the client program first checks that ap->alloc + size <= ap->limit and in the common case that it is, it takes a copy of ap->init (which now points to the reserved block) and sets ap->alloc += size.

What happens when ap->alloc + size > ap->limit, that is, when the new block won’t fit in the buffer? Then the buffer needs to be refilled by calling mps_ap_fill(), with typical results shown in the diagram below.

Allocation point after refilling.

Refilling is why allocation points are only nearly lock-free: mps_ap_fill() has to take locks on internal MPS data structures.

Note that mps_ap_fill() reserves the requested block as well as refilling the buffer.

The reserve operation thus looks like this:

if (ap->alloc + size <= ap->limit) {
    ap->alloc += ap->size;
    p = ap->init;
} else {
    res = mps_ap_fill(&p, ap, size);
    if (res != MPS_RES_OK) {
        /* handle error */;
    }
}

The critical path consists of an add, a store, and a branch (and branch prediction should work well since the test usually succeeds).

Note

Normally the client program would use the macro mps_reserve() to perform this operation, as described above, rather than directly accessing the fields of the allocation point structure. But there are use cases where direct access is needed to generate the fastest code (for example, in the case of a compiler generating machine code that needs to interface with the MPS), and it is for these use cases that the details of mps_ap_s are made public and supported.

When the new block has been initialized it must be committed⁽²⁾. To do this, set ap->init = ap->alloc and then check to see if the allocation point has been trapped: that is, if the garbage collector might have moved some objects since the new block was reserved. The garbage collector traps an allocation point by setting ap->limit = 0, so if this case is found, then the reserved block may have been invalidated, and must be discarded and re-reserved, and the buffer must be refilled. The function mps_ap_trip() determines whether or not this case applies, returning true if the block is valid, false if not.

The commit operation thus looks like this:

ap->init = ap->alloc;
if (ap->limit == 0 && !mps_ap_trip(ap, p, size)) {
    /* p is invalid */
} else {
    /* p is valid */
}

The critical path here consists of a store and a branch (and again, branch prediction should work well since the test almost never fails).

Note

Normally the client program would use mps_commit() to perform this operation, as described above, rather than directly accessing the fields of the allocation point structure. But direct access is supported by the MPS.

Note

The commit operation relies on atomic ordered access to words in memory to detect a flip that occurs between the assignment ap->init = ap->alloc and the test ap->limit == 0. A compiler or processor that reordered these two instructions would break the protocol. On some processor architectures and some compilers, it may be necessary to insert a memory barrier instruction at this point.

mps_ap_s

The type of the structure used to represent allocation points:

typedef struct mps_ap_s {
    mps_addr_t init;
    mps_addr_t alloc;
    mps_addr_t limit;
    /* ... private fields ... */
} mps_ap_s;

init is the limit of initialized memory.

alloc is the limit of allocated memory.

limit is the limit of available memory.

An allocation point is an interface to a pool which provides very fast allocation, and defers the need for synchronization in a multi-threaded environment.

Create an allocation point for a pool by calling mps_ap_create_k(), and allocate memory via one by calling mps_reserve() and mps_commit().

mps_res_t mps_ap_fill(mps_addr_t *p_o, mps_ap_t ap, size_t size)

Reserve a block of memory on an allocation point when the allocation point has insufficient space.

mps_ap_fill() has same interface as mps_reserve().

Note

mps_ap_fill() must only be called according to the Allocation point protocol.

mps_bool_t mps_ap_trip(mps_ap_t ap, mps_addr_t p, size_t size)

Test whether a reserved block was successfully committed⁽²⁾ when an allocation point was trapped.

mps_ap_trip() has the same interface as mps_commit().

Note

mps_ap_trip() must only be called according to the Allocation point protocol.