11. Garbage collection

The arena contains a garbage collector that coordinates the collection of garbage in all of its automatically managed pools. The collector efficiently traces references between roots and pools, and between objects in different pools. It is capable of collecting many automatically managed pools simultaneously.

11.1. Generation chains

A generation chain describes a sequence of generations used by a set of automatically managed pools.

A generation is a set of blocks that are managed together by the garbage collector: they are condemned together, and in moving pools they are moved together. If two pools allocate blocks that are expected to live and die together, then it is efficient for them to share a chain.

Typically blocks are allocated in the first generation in the chain, the nursery generation (though you can change this using the MPS_KEY_GEN keyword argument to mps_pool_create_k()), and each time a block survives one collection then it is promoted to the next generation. Thus a generation contains a set of blocks of similar ages.

By default, all pools in an arena share the same generation chain (“the arena’s default generation chain”), but if this doesn’t meet your requirements, then when creating an automatically managed pool, you can choose which chain it should use by passing the MPS_KEY_CHAIN keyword argument to mps_pool_create_k().

Create a generation chain by preparing an array of mps_gen_param_s structures giving the capacity (in kilobytes) and predicted mortality (between 0 and 1) of each generation, and passing them to mps_chain_create().

When the new size of a generation exceeds its capacity, the MPS will be prepared to start collecting the chain to which the generation belongs. See Scheduling of collections below.

For example:

mps_gen_param_s gen_params[] = {
    { 1024, 0.8 },
    { 2048, 0.4 },
};

mps_chain_t chain;
mps_res_t res;
res = mps_chain_create(&chain, arena,
                       sizeof(gen_params) / sizeof(gen_params[0]),
                       gen_params);
if (res != MPS_RES_OK) error("Couldn't create chain");
mps_chain_t

The type of generation chains. A generation chain describes the structure of generations in a set of pools.

mps_gen_param_s

The type of the structure used to specify a generation in a generation chain.

typedef struct mps_gen_param_s {
    size_t mps_capacity;
    double mps_mortality;
} mps_gen_param_s;

mps_capacity is the capacity of the generation, in kilobytes. When the size of the generation exceeds this, the MPS will be prepared to start collecting it.

mps_mortality is the predicted mortality of the generation: the proportion (between 0 and 1) of blocks in the generation that are expected to be dead when the generation is collected.

These numbers are hints to the MPS that it may use to make decisions about when and what to collect: nothing will go wrong (other than suboptimal performance) if you make poor choices. See Scheduling of collections.

mps_res_t mps_chain_create(mps_chain_t *chain_o, mps_arena_t arena, size_t gen_count, mps_gen_param_s *gen_params)

Create a generation chain.

chain_o points to a location that will hold a pointer to the new generation chain.

arena is the arena to which the generation chain will belong.

gen_count is the number of generations in the chain.

gen_params points to an array describing the generations.

Returns MPS_RES_OK if the generation chain is created successfully, or another result code if it fails.

The generation chain persists until it is destroyed by calling mps_chain_destroy().

void mps_chain_destroy(mps_chain_t chain)

Destroy a generation chain.

chain is the generation chain.

It is an error to destroy a generation chain if there is a garbage collection in progress on the chain, or if there are any pools using the chain. Before calling this function, the arena should be parked (by calling mps_arena_park()) to ensure that there are no collections in progress, and pools using the chain must be destroyed.

11.2. Scheduling of collections

Note

It’s likely that the algorithm the MPS uses to schedule its collections will change in future releases. There’s a lot of room for improvement here.

The new size of a generation is the total size of the newly allocated (in generation 0) or newly promoted (in other generations) blocks in that generation. These are the blocks that have not been condemned since they were allocated or promoted into this generation. In pools like AMC (Automatic Mostly-Copying) where the survivors get promoted to the next generation in the chain, the new size of each generation (other than the topmost) is the same as its total size, but in pools like AMS (Automatic Mark and Sweep) where survivors do not get promoted, the two sizes can be different.

When a generation’s new size exceeds its capacity, the MPS considers collecting the chain to which the generation belongs. (How long it takes to get around to it depends on which other collections are in progress.)

Note

You can affect the decision as to when to collect the chain by using the ramp allocation pattern.

If the MPS decides to collect a chain, all generations are collected up to, and including, the highest generation whose new size exceeds its capacity.

In pools such as AMC (Automatic Mostly-Copying), blocks in generation g that survive collection get promoted to generation g+1. If the last generation in the chain is collected, the survivors are promoted into an arena-wide “top” generation.

The predicted mortality is used to estimate how long the collection will take, and this is used in turn to decide how much work the collector will do each time it has an opportunity to do some work. The constraints here are:

  1. The client program might have specified a limit on the acceptable length of the pause if the work is being done inside mps_arena_step().

  2. The collector needs to keep up with the client program: that is, it has to collect garbage at least as fast as the client is producing it, otherwise the amount of garbage will grow without bound.

With perfect prediction, the collector’s work should be smoothly distributed, with a small maximum pause time. Getting the predicted mortality wrong leads to “lumpy” distribution of collection work with a longer maximum pause time. If the predicted mortality is too high, the collector will start out by taking small time slices and then find that it has to catch up later by taking larger time slices. If the predicted mortality is too low, the collector will take larger time slices up front and then find that it is idle later on.

11.3. Garbage collection start messages

mps_message_type_t mps_message_type_gc_start(void)

Return the message type of garbage collection start messages.

Garbage collection start messages contain information about why the garbage collection started.

The access method specific to a message of this message type is:

See also

Messages.

const char *mps_message_gc_start_why(mps_arena_t arena, mps_message_t message)

Return a string that describes why the garbage collection that posted a message started.

arena is the arena which posted the message.

message is a message retrieved by mps_message_get() and not yet discarded. It must be a garbage collection message: see mps_message_type_gc().

Returns a pointer to a string that is describes (in English) why this collection started. The contents of the string must not be modified by the client. The string and the pointer are valid until the message is discarded with mps_message_discard().

See also

Messages.

11.4. Garbage collection messages

mps_message_type_t mps_message_type_gc(void)

Return the message type of garbage collection statistic messages.

Garbage collection statistic messages are used by the MPS to give the client program information about a garbage collection that has taken place. Such information may be useful in analysing the client program’s memory usage over time.

The access methods specific to a message of this type are:

See also

Messages.

size_t mps_message_gc_condemned_size(mps_arena_t arena, mps_message_t message)

Return the “condemned size” property of a message.

arena is the arena which posted the message.

message is a message retrieved by mps_message_get() and not yet discarded. It must be a garbage collection message: see mps_message_type_gc().

The “condemned size” property is the approximate size of the condemned set in the garbage collection that generated the message.

See also

Messages.

size_t mps_message_gc_live_size(mps_arena_t arena, mps_message_t message)

Return the “live size” property of a message.

arena is the arena which posted the message.

message is a message retrieved by mps_message_get() and not yet discarded. It must be a garbage collection message: see mps_message_type_gc().

The “live size” property is the total size of the set of blocks that survived the garbage collection that generated the message.

See also

Messages.

size_t mps_message_gc_not_condemned_size(mps_arena_t arena, mps_message_t message)

Return the “not condemned size” property of a message.

arena is the arena which posted the message.

message is a message retrieved by mps_message_get() and not yet discarded. It must be a garbage collection message: see mps_message_type_gc().

The “not condemned size” property is the approximate size of the set of blocks that were in collected pools, but were not in the condemned set in the garbage collection that generated the message.

See also

Messages.