10. Roots

Roots tell the garbage collector where to start tracing. The garbage collector determines which blocks are reachable from the roots, and (in automatically managed pools) reclaims the unreachable blocks. This is quite efficient and can be a very good approximation to liveness.

It is therefore important that all references that the client program can directly access are registered as roots, otherwise the garbage collector might recycle an object that would be used in the future. Some collectors, for example Boehm’s, assume that all references stored in static data are roots; the Memory Pool System is more flexible, but requires the client program to declare which references are roots.

10.1. Registering roots

You can register a root at any time by calling one of the mps_root_create functions. Roots may not be registered twice, and no two roots may overlap (that is, each reference is fixed by at most one root). Roots may be:

  1. in registers;

  2. on the program’s control stack;

  3. in the program’s static data;

  4. in heap not managed by the MPS (provided that you destroy the root before freeing it; see the Scheme interpreter’s global symbol table for an example);

  5. in manually managed pools (provided that you remove the root before freeing it).

Roots must not be in memory that is subject to garbage collection (and so roots must not be in automatically managed pools).

When you register a root you describe to the MPS how to scan it for references, providing your own scanning function in the cases of mps_root_create() and mps_root_create_fmt(). Such a root scanning function must follow the Scanning protocol.

All the references in a root are of the same rank (just as in a formatted object). So they are all exact, ambiguous or weak.

Note

If the rank of the root is exact, or weak, the references in the root must always be valid while the root is registered: that is, they must be references to actual objects or null pointers. This could be immediately after the root is registered, so the root must be valid before it is registered.

Note

As with scanning in general, it’s safe to fix references that point to memory not managed by the MPS. These will be ignored.

Roots can be deregistered at any time by calling mps_root_destroy(). All roots registered in an arena must be deregistered before the arena is destroyed.

There are four ways to register a root, depending on how you need to scan it for references:

  1. mps_root_create() if you need a custom root scanning function (of type mps_root_scan_t);

  2. mps_root_create_fmt() if the root consists of a block of objects belonging to an object format, which can be scanned by the format’s scan method (of type mps_fmt_scan_t);

  3. mps_root_create_area() if the root consists of an area of memory;

  4. mps_root_create_thread() if the root consists of the registers and control stack of a thread. See Thread roots below.

Several of these categories of roots have variants for dealing with tagged references. See Tagged references.

10.2. Cautions

Creating a root and then registering is similar to reserving a block and then committing it (in the Allocation point protocol), and similar cautions apply. Before registering a root:

  1. The root must be valid (that is, the appropriate root scanning function can scan it).

  2. All exact references in the root (references that are fixed by the root scanning function) must contain valid references or null pointers.

  3. You must not store a reference in the root to a block in an automatically managed pool (such a reference is hidden from the MPS until you register the root, and may become invalid).

So the typical sequence of operations when creating a root is:

  1. Initialize references in the root with null pointers or other safe values.

  2. Register the root.

  3. Fill in the references in the root.

10.3. Thread roots

Every thread’s registers and control stack potentially contain references to allocated objects, so should be registered as a root by calling mps_root_create_thread().

The MPS’s stack scanner needs to know how to find the cold end of the part of the stack to scan. The cold end of the relevant part of the stack can be found by taking the address of a local variable in the function that calls the main work function of your thread. You should take care to ensure that the work function is not inlined so that the address is definitely in the stack frame below any potential roots.

For example, here’s the code from the toy Scheme interpreter that registers a thread root and then calls the program:

mps_thr_t thread;
mps_root_t stack_root;
int exit_code;
void *cold = &cold;

res = mps_thread_reg(&thread, arena);
if (res != MPS_RES_OK) error("Couldn't register thread");

res = mps_root_create_thread(&stack_root, arena, thread, cold);
if (res != MPS_RES_OK) error("Couldn't create root");

exit_code = start(argc, argv);

mps_root_destroy(stack_root);
mps_thread_dereg(thread);

10.4. Ranks

mps_rank_t

The type of ranks. It is a transparent alias for unsigned int, provided for convenience and clarity.

mps_rank_t mps_rank_ambig(void)

Return the rank of ambiguous roots.

mps_rank_t mps_rank_exact(void)

Return the rank of exact roots.

mps_rank_t mps_rank_weak(void)

Return the rank of weak roots.

10.5. Root modes

The root mode provides a way for the client to declare various facts about a root that allow the MPS to make optimizations. Roots that are declared to be constant need not be re-scanned, and roots that are declared to be protectable may have barriers placed on them, allowing the MPS to detect whether they have changed.

Note

The MPS does not currently perform either of these optimizations, so root modes have no effect. These features may be added in a future release.

mps_rm_t

The type of root modes.

It should be zero (meaning neither constant or protectable), or the sum of some of MPS_RM_CONST, MPS_RM_PROT, and MPS_RM_PROT_INNER.

MPS_RM_CONST

Deprecated

starting with version 1.111.

This was introduced in the hope of being able to maintain a remembered set for the root without needing a write barrier, but it can’t work as described, since you can’t reliably create a valid registered constant root that contains any references. (If you add the references before registering the root, they may have become invalid; but you can’t add them afterwards because the root is supposed to be constant.)

The root mode for constant roots. This tells the MPS that the client program will not change the root after it is registered: that is, scanning the root will produce the same set of references every time. Furthermore, for roots registered by mps_root_create_fmt() and mps_root_create_area(), the client program will not write to the root at all.

MPS_RM_PROT

The root mode for protectable roots. This tells the MPS that it may place a barrier (1) on any page containing any part of the root. No format method or scan method (except for the one for this root) may write data in this root. They may read it.

Note

You must not specify MPS_RM_PROT on a root allocated by the MPS.

No page may contain parts of two or more protectable roots. You mustn’t specify MPS_RM_PROT if the client program or anything other than (this instance of) the MPS is going to protect or unprotect the relevant pages.

This mode may not be suitable if the client program wants the operating system to be able to access the root. Many operating systems can’t cope with writing to protected pages.

MPS_RM_PROT_INNER

The root mode for protectable roots whose inner pages (only) may be protected. This mode must not be specified unless MPS_RM_PROT is also specified. It tells the MPS that it may not place a barrier (1) on a page that’s partly (but not wholly) covered by the root.

10.6. Root interface

mps_root_t

The type of root descriptions.

The arena uses root descriptions to find references within the client program’s roots.

mps_res_t mps_root_create(mps_root_t *root_o, mps_arena_t arena, mps_rank_t rank, mps_rm_t rm, mps_root_scan_t root_scan, void *p, size_t s)

Register a root that consists of the references fixed by a scanning function.

root_o points to a location that will hold the address of the new root description.

arena is the arena.

rank is the rank of references in the root.

rm is the root mode.

root_scan is the root scanning function. See mps_root_scan_t.

p and s are arguments that will be passed to root_scan each time it is called. This is intended to make it easy to pass, for example, an array and its size as parameters.

Returns MPS_RES_OK if the root was registered successfully, MPS_RES_MEMORY if the new root description could not be allocated, or another result code if there was another error.

The registered root description persists until it is destroyed by calling mps_root_destroy().

This is the most general kind of root, but gives the MPS the least information to use for optimisation. Use a more specialized kind of root whenever possible.

mps_res_t (*mps_root_scan_t)(mps_ss_t ss, void *p, size_t s)

The type of root scanning functions for mps_root_create().

ss is the scan state. It must be passed to MPS_SCAN_BEGIN() and MPS_SCAN_END() to delimit a sequence of fix operations, and to the functions MPS_FIX1() and MPS_FIX2() when fixing a reference.

p and s are the corresponding values that were passed to mps_root_create().

Returns a result code. If a fix function returns a value other than MPS_RES_OK, the scan method must return that value, and may return without fixing any further references. Generally, it is better if it returns as soon as possible. If the scanning is completed successfully, the function should return MPS_RES_OK.

mps_res_t mps_root_create_fmt(mps_root_t *root_o, mps_arena_t arena, mps_rank_t rank, mps_rm_t rm, mps_fmt_scan_t fmt_scan, mps_addr_t base, mps_addr_t limit)

Register a root that consists of the references fixed by a scanning function in a block of formatted objects.

root_o points to a location that will hold the address of the new root description.

arena is the arena.

rank is the rank of references in the root.

rm is the root mode.

fmt_scan is a scanning function. See mps_fmt_scan_t.

base is the address of the base of the block of formatted objects.

limit is the address just beyond the end of the block of formatted objects.

Returns MPS_RES_OK if the root was registered successfully, MPS_RES_MEMORY if the new root description could not be allocated, or another result code if there was another error.

The registered root description persists until it is destroyed by calling mps_root_destroy().

mps_res_t mps_root_create_thread(mps_root_t *root_o, mps_arena_t arena, mps_thr_t thr, void *cold)

Register a root that consists of the references in a thread’s registers and stack that are word aligned. This is the most common kind of thread root.

This function is equivalent to calling:

mps_root_create_thread_tagged(root_o,
                              arena,
                              mps_rank_ambig(),
                              (mps_rm_t)0,
                              thr,
                              mps_scan_area_tagged,
                              sizeof(mps_word_t) - 1,
                              0,
                              cold);
mps_res_t mps_root_create_thread_tagged(mps_root_t *root_o, mps_arena_t arena, mps_rank_t rank, mps_rm_t rm, mps_thr_t thr, mps_area_scan_t scan_area, mps_word_t mask, mps_word_t pattern, void *cold)

Register a root that consists of the references in a thread’s registers and stack that match a binary pattern, for instance tagged as pointers.

root_o points to a location that will hold the address of the new root description.

arena is the arena.

rank is the rank of references in the root.

rm is the root mode.

thr is the thread.

scan_area is an tagged area scanning function that will be used to scan the threads registers and stack, for example mps_scan_area_tagged() or mps_scan_area_tagged_or_zero(). See Area scanners.

mask is a bitmask that is passed to scan_area to be applied to the thread’s registers and stack to locate the tag.

pattern is passed to scan_area to determine whether to consider a word as a reference. For example, mps_scan_area_tagged() will not consider any word that is unequal to this (after masking with mask) to be a reference.

cold is a pointer to the cold end of stack to be scanned. On platforms where the stack grows downwards (currently, all supported platforms), locations below this address will be scanned.

Returns MPS_RES_OK if the root was registered successfully, MPS_RES_MEMORY if the new root description could not be allocated, or another result code if there was another error.

The registered root description persists until it is destroyed by calling mps_root_destroy().

Warning

A risk of using tagged pointers in registers and on the stack is that in some circumstances, an optimizing compiler might optimize away the tagged pointer, keeping only the untagged version of the pointer. In this situation the pointer would be ignored and if it was the last reference to the object the MPS might incorrectly determine that it was dead.

You can avoid this risk in several ways:

  1. Choose to tag pointers with zero, setting scan_area to mps_scan_area_tagged() and setting pattern to zero.

  2. Set scan_area to mps_scan_area_tagged_or_zero() so that untagged pointers are scanned. This may lead to some additional scanning and retention.

  3. Use mps_root_create_thread_scanned() and set scan_area to mps_scan_area(): in this case all words in registers and on the stack are scanned, leading to possible additional scanning and retention.

  4. Write your own compiler with complete control over register contents and stack format, use mps_root_create_thread_scanned() and set scan_area to your own custom scanner, derived from the source code of mps_scan_area(), that knows the format.

Note

An optimization that may be worth considering is setting some of the top bits in mask and pattern so that addresses that cannot be allocated by the MPS are rejected quickly. This requires expertise with the platform’s virtual memory interface.

mps_res_t mps_root_create_thread_scanned(mps_root_t *root_o, mps_arena_t arena, mps_rank_t rank, mps_rm_t rm, mps_thr_t thread, mps_area_scan_t scan_area, void *closure, void *cold)

Register a root that consists of the references in a thread’s registers and stack, scanned by an arbitrary area scanning function.

root_o points to a location that will hold the address of the new root description.

arena is the arena.

rank is the rank of references in the root.

rm is the root mode.

thr is the thread.

scan_area is an area scanning function that will be used to scan the threads registers and stack, for example mps_scan_area(), or a similar user-defined function. See Area scanners.

closure is an arbitrary pointer that will be passed to scan_area and is intended to point to any parameters it needs. Ensure anything it points to exists as long as the root exists.

cold is a pointer to the cold end of stack to be scanned. On platforms where the stack grows downwards (currently, all supported platforms), locations below this address will be scanned.

Returns MPS_RES_OK if the root was registered successfully, MPS_RES_MEMORY if the new root description could not be allocated, or another result code if there was another error.

The registered root description persists until it is destroyed by calling mps_root_destroy().

mps_res_t mps_root_create_area(mps_root_t *root_o, mps_arena_t arena, mps_rank_t rank, mps_rm_t rm, void *base, void *limit, mps_area_scan_t scan_area, void *closure)

Register a root that consists of an area of memory scanned by an area scanning function.

root_o points to a location that will hold the address of the new root description.

arena is the arena.

rank is the rank of references in the root.

rm is the root mode.

base points to the first word to be scanned.

limit points to the location just beyond the end of the area to be scanned.

scan_area is an area scanning function, for example mps_scan_area(), or a similar user-defined function. See Area scanners.

closure is an arbitrary pointer that will be passed to scan_area and intended to point to any parameters it needs. Ensure anything it points to exists as long as the root exists.

Returns MPS_RES_OK if the root was registered successfully, MPS_RES_MEMORY if the new root description could not be allocated, or another result code if there was another error.

The registered root description persists until it is destroyed by calling mps_root_destroy().

mps_res_t mps_root_create_area_tagged(mps_root_t *root_o, mps_arena_t arena, mps_rank_t rank, mps_rm_t rm, void *base, void *limit, mps_area_scan_t scan_area, mps_word_t mask, mps_word_t pattern)

Register a root that consists of an area of memory scanned by a tagged area scanning function.

root_o points to a location that will hold the address of the new root description.

arena is the arena.

rank is the rank of references in the root.

rm is the root mode.

base points to a vector of tagged references.

count is the number of tagged references in the vector.

scan_area is an tagged area scanning function that will be used to scan the area, for example mps_scan_area_tagged() or mps_scan_area_tagged_or_zero(). The closure argument to scan_area is a mps_scan_tag_t cast to void * See Area scanners.

mask is a bitmask that is passed to scan_area to be applied to the words in the vector to locate the tag.

pattern is passed to scan_area to determine whether to consider a word as a reference. For example, mps_scan_area_tagged() will not consider any word that is unequal to this (after masking with mask) to be a reference.

Returns MPS_RES_OK if the root was registered successfully, MPS_RES_MEMORY if the new root description could not be allocated, or another result code if there was another error.

The registered root description persists until it is destroyed by calling mps_root_destroy().

For example:

#define TAG_MASK 0x3            /* bottom two bits */
#define TAG_PATTERN 0x1         /* bottom bit set for references */

/* Global symbol table. */
size_t symtab_size;
struct {
    obj_t symbol;
    obj_t value;
} *symtab;

mps_res_t res;
mps_root_t root;
res = mps_root_create_area_tagged(&root, arena,
                                  mps_rank_exact(),
                                  0,
                                  symtab, symtab + symtab_size,
                                  mps_scan_area_tagged,
                                  TAG_MASK, TAG_PATTERN);
if (res != MPS_RES_OK) error("can't create symtab root");
void mps_root_destroy(mps_root_t root)

Deregister a root and destroy its description.

root is the root.

10.7. Root introspection

void mps_arena_roots_walk(mps_arena_t arena, mps_roots_stepper_t f, void *p, size_t s)

Deprecated

starting with version 1.111.

If you think you need this, there’s probably a better way to achieve what you’re trying to do. Contact us.

Visit references in registered roots in an arena.

arena is the arena whose roots you want to visit.

f is a function that will be called for each reference to an object in an automatically managed pool class that was found in a registered root belonging to the arena. It takes four arguments: ref is the address of a reference to an object in the arena, root is the root in which ref was found, and p and s are the corresponding arguments that were passed to mps_arena_roots_walk().

p and s are arguments that will be passed to f each time it is called. This is intended to make it easy to pass, for example, an array and its size as parameters.

This function may only be called when the arena is in the parked state.

See also

Arenas.

Note

If a root is ambiguous then the reference might not be to the start of an object; the client program should handle this case. There is no guarantee that the reference corresponds to the actual location that holds the pointer to the object (since this might be a register, for example), but the actual location will be passed if possible. This may aid analysis of roots via a debugger.

void (*mps_roots_stepper_t)(mps_addr_t *ref, mps_root_t root, void *p, size_t s)

The type of a root stepper function.

A function of this type can be passed to mps_arena_roots_walk(), in which case it will be called for each reference into the arena from a root registered with the arena. It receives four arguments:

ref points to a reference in a root. The reference points to something in the arena. If the root is exact then the reference points to the start of an allocated block, but if the root is ambiguous it might point to somewhere in the middle of an allocated block.

root is the description of the root which contains ref.

p and s are the corresponding values that were passed to mps_arena_roots_walk().