7. Object formats

The need for some means of describing objects in the client program comes from tracing and moving. During tracing, when an object is scanned, all the references in the object must be identified so that the objects they point to can be scanned in their turn. When an object has moved, references to that object must be identified so that they can be updated to point to the new location of the object.

In general, only the client program can say which fields in an object are references, and only the client program knows how references are represented (for example, are they tagged?). Object formats provide the means by which the client program communicates this information to the MPS.

An object format is a collection of format methods and other (usually scalar) values which together describe programatically the layout of objects belonging to the format. Format methods include the skip method (which calculates an object’s size), the scan method (which fixes references in the object), and the forward method (which replaces an object that has moved with a forwarding object).

Not every pool class supports formatted objects.

mps_fmt_t

The type of an object format.

7.1. Creating an object format

Different pool classes use different sets of format methods and values (for example, a non-moving pool does not need forwarding objects, so its object formats do not need to contain a forward method). To accommodate this variance, it is possible to construct object formats from different collections of format methods and values. Such a collection is called a format variant.

There are three supported format variants. All are suitable for copying and moving pools.

• Variant A (mps_fmt_A_s): for objects without headers.
• Variant B (mps_fmt_B_s): as variant A, but with the addition of a class method.
• Variant auto-header (mps_fmt_auto_header_s): for objects with headers.

The client program creates an object format by construct a format variant structure and then calling the appropriate mps_fmt_create_ function for the variant. The variant structure can then be disposed of.

For example:

struct mps_fmt_A_s obj_fmt_s = {
    ALIGNMENT,
    obj_scan,
    obj_skip,
    NULL,                         /* Obsolete copy method */
    obj_fwd,
    obj_isfwd,
    obj_pad
};

mps_pool_t obj_pool;
mps_fmt_t obj_fmt;
mps_res_t res;

res = mps_fmt_create_A(&obj_fmt, arena, &obj_fmt_s);
if (res != MPS_RES_OK) error("Couldn't create obj format");
/* obj_fmt created successfully */

MPS_ARGS_BEGIN(args) {
    MPS_ARGS_ADD(args, MPS_KEY_FORMAT, obj_fmt);
    MPS_ARGS_DONE(args);
    res = mps_pool_create_k(&obj_pool, arena, pool_class, args);
} MPS_ARGS_END(args);
if (res != MPS_RES_OK) error("Couldn't create obj pool");

mps_fmt_A_s

The type of the structure used to create an object format of variant A.

typedef struct mps_fmt_A_s {
    mps_align_t     align;
    mps_fmt_scan_t  scan;
    mps_fmt_skip_t  skip;
    mps_fmt_copy_t  copy;
    mps_fmt_fwd_t   fwd;
    mps_fmt_isfwd_t isfwd;
    mps_fmt_pad_t   pad;
} mps_fmt_A_s;

Broadly speaking, object formats of variant A are suitable for use in copying or moving pools.

align is an integer value specifying the alignment of objects allocated with this format. It should be large enough to satisfy the alignment requirements of any field in the objects, and it must not be larger than the pool alignment.

scan is a scan method that identifies references within objects belonging to this format. See mps_fmt_scan_t.

skip is a skip method that skips over objects belonging to this format. See mps_fmt_skip_t.

copy is not used. (In older versions of the MPS it was a copy method that copied objects belonging to this format.)

fwd is a forward method that stores relocation information for an object belonging to this format that has moved. See mps_fmt_fwd_t.

isfwd is a is-forwarded method that determines if an object belonging to this format has been moved. See mps_fmt_isfwd_t.

pad is a padding method that creates padding objects belonging to this format. See mps_fmt_pad_t.

mps_res_t mps_fmt_create_A(mps_fmt_t *fmt_o, mps_arena_t arena, mps_fmt_A_s *fmt_A)

Create an object format of variant A.

fmt_o points to a location that will hold the address of the new object format.

arena is the arena in which to create the format.

fmt_A points to a description of an object format of variant A.

Returns MPS_RES_OK if successful. The MPS may exhaust some resource in the course of mps_fmt_create_A() and will return an appropriate result code if so.

After this function returns, the object format description pointed to be fmt_A is no longer needed and may be discarded. The object format pointed to by fmt_o persists until it is destroyed by calling mps_fmt_destroy().

mps_fmt_B_s

The type of the structure used to create an object format of variant B.

typedef struct mps_fmt_B_s {
    mps_align_t     align;
    mps_fmt_scan_t  scan;
    mps_fmt_skip_t  skip;
    mps_fmt_copy_t  copy;
    mps_fmt_fwd_t   fwd;
    mps_fmt_isfwd_t isfwd;
    mps_fmt_pad_t   pad;
    mps_fmt_class_t mps_class;
} mps_fmt_B_s;

Variant B is the same as variant A except for the addition of the mps_class method. See mps_fmt_A_s.

mps_res_t mps_fmt_create_B(mps_fmt_t *fmt_o, mps_arena_t arena, mps_fmt_B_s *fmt_B)

Create an object format of variant B.

fmt_o points to a location that will hold the address of the new object format.

arena is the arena in which to create the format.

fmt_B points to a description of an object format of variant B.

Returns MPS_RES_OK if successful. The MPS may exhaust some resource in the course of mps_fmt_create_B() and will return an appropriate result code if so.

mps_fmt_auto_header_s

The type of the structure used to create an object format of variant auto-header.

typedef struct mps_fmt_auto_header_s {
    mps_align_t     align;
    mps_fmt_scan_t  scan;
    mps_fmt_skip_t  skip;
    mps_fmt_fwd_t   fwd;
    mps_fmt_isfwd_t isfwd;
    mps_fmt_pad_t   pad;
    size_t          mps_headerSize;
} mps_fmt_auto_header_s;

Variant auto-header is the same as variant A except for the removal of the unused copy method, and the addition of the mps_headerSize field. See mps_fmt_A_s.

Broadly speaking, the object formats of this variant are suitable for use in automatic memory management for objects with headers (hence the name). More precisely, this variant is intended for formats where the client program’s pointers point some distance into the memory block containing the object. This typically happens when the objects have a common header used for memory management or class system purposes, but this situation also arises when the low bits of a pointer are used for a tag. The MPS does not care what the reason is, only about the offset of the pointer in relation to the memory block.

mps_headerSize is the size of the header, that is, the offset of a client pointer from the base of the memory block.

Note

Format methods (other than the padding method) for formats of this variant will receive client pointers (that is, pointers past the header) but all other MPS functions expect to receive and return base pointers (that is, pointers to the base of the block where the header is stored).

In particular, mps_reserve() and mps_alloc() always hand out base pointers, and mps_free() expects to receive one.

Note

For technical reasons, formatted objects must be longer than the header. In other words, objects consisting of only a header are not supported.

Note

Even if the header size is larger than or equal to alignment, the padding method must still be able to create padding objects down to the alignment size.

mps_res_t mps_fmt_create_auto_header(mps_fmt_t *fmt_o, mps_arena_t arena, mps_fmt_auto_header_s *fmt_ah)

Create an object format of variant auto-header.

fmt_o points to a location that will hold the address of the new object format.

arena is the arena in which to create the format.

fmt_ah points to a description of an object format of variant auto-header.

Returns MPS_RES_OK if successful. The MPS may exhaust some resource in the course of mps_fmt_create_auto_header() and will return an appropriate result code if so.

void mps_fmt_destroy(mps_fmt_t fmt)

Destroy an object format.

fmt is the object format to destroy.

It is an error to destroy an object format if there exists a pool using the format. The pool must be destroyed first.

7.2. Cautions

1. The MPS guarantees that format methods have exclusive access to the object for the duration of the call. This guarantee may entail suspending arbitrary threads. The methods that manipulate the object must not perform any sort of inter-thread locking or communication.

2. The MPS may call format methods in the context of an exception handler or a signal handler. For example, the following sequence of events is common:

   1. the MPS places a read barrier on a block of memory;
   2. the client program attempts to read from this block;
   3. the hardware raises a protection fault;
   4. the MPS signal handler is called;
   5. the MPS ensures that the contents of the block are correct and consistent: this may involve inspection of formatted objects in the block (or indeed, elsewhere), and so
   6. the MPS calls format methods.

   Therefore, the format methods must be able to be run at any time, including asynchronously or in parallel with the rest of the program.

3. Format methods must be re-entrant.

4. Format methods must not:

   1. call library code;
   2. perform a non-local exit (for example, by calling longjmp);
   3. call any functions in the MPS other than the fix functions (mps_fix(), MPS_FIX1(), MPS_FIX12(), and MPS_FIX2()).

   It’s permissible to call other functions in the client program, but see MPS_FIX_CALL() for a restriction on passing the scan state.

5. Subject to the above constraints, format methods can freely access:

   1. memory inside the object or block that they have been asked to look at;
   2. memory managed by the MPS that is in pools that do not protect their contents;
   3. memory not managed by the MPS;

   They must not access other memory managed by the MPS.

7.3. Format methods

mps_addr_t (*mps_fmt_class_t)(mps_addr_t addr)

The type of the class method of an object format.

addr is the address of the object whose class is of interest.

Returns an address that is related to the class or type of the object, or a null pointer if this is not possible.

It is recommended that a null pointer be returned for padding objects and forwarding objects.

void (*mps_fmt_fwd_t)(mps_addr_t old, mps_addr_t new)

The type of the forward method of an object format.

old is the address of an object.

new is the address to where the object has been moved.

The MPS calls the forward method for an object format when it has relocated an object belonging to that format. The forward method must replace the object at old with a forwarding marker that points to the address ‘new’. The forwarding marker must meet the following requirements:

1. It must be possible for the MPS to call other methods in the object format (the scan method, the skip method and so on) with the address of a forwarding marker as the argument.
2. The forwarding marker must not be bigger than the original object.
3. It must be possible for the is-forwarded method of the object format to distinguish the forwarding marker from ordinary objects, and the is-forwarded method method must return the address new. See mps_fmt_isfwd_t.

Note

This method is never invoked by the garbage collector on an object in a non-moving pool.

mps_addr_t (*mps_fmt_isfwd_t)(mps_addr_t addr)

The type of the is-forwarded method of an object format.

addr is the address of a candidate object.

If the addr is the address of a forwarding object, return the address where the object was moved to. This must be the value of the new argument supplied to the forward method when the object was moved. If not, return a null pointer.

Note

This method is never invoked by the garbage collector on an object in a non-moving pool.

void (*mps_fmt_pad_t)(mps_addr_t addr, size_t size)

The type of the padding method of an object format.

addr is the address at which to create a padding object.

size is the size of the padding object to be created.

The MPS calls a padding method when it wants to create a padding object. Typically the MPS creates padding objects to fill in otherwise unused gaps in memory; they allow the MPS to pack objects into fixed-size units (such as operating system pages).

The padding method must create a padding object of the specified size at the specified address. The size can be any aligned (to the format alignment) size. A padding object must be acceptable to other methods in the format (the scan method, the skip method, and so on).

Note

The padding method always receives a base pointer, even if the object format belongs to variant auto-header.

mps_res_t (*mps_fmt_scan_t)(mps_ss_t ss, mps_addr_t base, mps_addr_t limit)

The type of the scan method of an object format.

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.

base points to the first formatted object in the block of memory to be scanned.

limit points to the location just beyond the end of the block to be scanned. Note that there might not be any object at this location.

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.

The scan method for an object format is called when the MPS needs to scan objects in a block of memory containing objects belonging to that format. The scan method is called with a scan state and the base and limit of the block of objects to scan. It must then indicate references within the objects by calling MPS_FIX1() and MPS_FIX2().

See also

Scanning.

mps_addr_t (*mps_fmt_skip_t)(mps_addr_t addr)

The type of the skip method of an object format.

addr is the address of the object to be skipped.

Returns the address of the “next object”. In an object format without headers (for example, a format of variant A), this is the address just past the end of this object. In an object format with headers (for example, a format of variant auto-header), it’s the address just past where the header of next object would be, if there were one.

Note

In either case, the result is the sum of addr and the size of the block containing the object.

A skip method is not allowed to fail.

Note

The MPS uses this method to determine the size of objects (by subtracting addr from the result) as well as skipping over them.

7.4. Object format introspection

mps_bool_t mps_addr_fmt(mps_fmt_t *fmt_o, mps_arena_t arena, mps_addr_t addr)

Determine the object format to which an address belongs.

fmt_o points to a location that will hold the address of the object format, if one is found.

arena is the arena whose object formats will be considered.

addr is the address.

If addr is the address of a location inside a block allocated from a pool in arena, and that pool has an object format, then update the location pointed to by fmt_o with the address of the object format, and return true.

If addr is the address of a location inside a block allocated from a pool in arena, but that pool has no object format, return false.

If addr points to a location that is not managed by arena, return false.

If none of the above conditions is satisfied, mps_addr_fmt() may return either true or false.

Note

This function might return a false positive by returning true if you ask about an address that happens to be inside memory managed by a pool with an object format, but which is not inside a block allocated by that pool. It never returns a false negative.

void mps_arena_formatted_objects_walk(mps_arena_t arena, mps_formatted_objects_stepper_t f, void *p, size_t s)

Visit all formatted objects in an arena.

arena is the arena whose formatted objects you want to visit.

f is a formatted objects stepper function. It will be called for each formatted object in the arena. See mps_formatted_objects_stepper_t.

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.

Each pool class determines for which objects the stepper function is called. Typically, all validly formatted objects are visited. During a trace this will in general be only the black objects, though the LO (Leaf Object) pool, for example, will walk all objects since they are validly formatted whether they are black or white. Padding objects may be visited at the pool class’s discretion: the client program should handle this case.

See also

Arenas.

Note

This function is intended for heap analysis, tuning, and debugging, not for frequent use in production.

void (*mps_formatted_objects_stepper_t)(mps_addr_t addr, mps_fmt_t fmt, mps_pool_t pool, void *p, size_t s)

The type of a formatted objects stepper function.

A function of this type can be passed to mps_arena_formatted_objects_walk(), in which case it will be called for each formatted object in an arena. It receives five arguments:

addr is the address of the object.

fmt is the object format for that object.

pool is the pool to which the object belongs.

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

The function may not call any function in the MPS. It may access:

1. memory inside the object or block pointed to by addr;
2. memory managed by the MPS that is in pools that do not protect their contents;
3. memory not managed by the MPS;

It must not access other memory managed by the MPS.

See also

Arenas.