40. General MPS types

40.1. Introduction

.intro: See impl.h.mpmtypes.

40.2. Rationale

Some types are declared to resolve a point of design, such as the best type to use for array indexing.

Some types are declared so that the intention of code is clearer. For example, Byte is necessarily unsigned char, but it’s better to say Byte in your code if it’s what you mean.

40.3. Concrete types

unsigned AccessSet

.access-set: An AccessSet is a bitset of Access modes, which are AccessREAD and AccessWRITE. AccessSetEMPTY is the empty AccessSet.

struct AddrStruct *Addr

.addr: Addr is the type used for “managed addresses”, that is, addresses of objects managed by the MPS.

.addr.def: Addr is defined as struct AddrStruct *, but AddrStruct is never defined. This means that Addr is always an incomplete type, which prevents accidental dereferencing, arithmetic, or assignment to other pointer types.

.addr.use: Addr should be used whenever the code needs to deal with addresses. It should not be used for the addresses of memory manager data structures themselves, so that the memory manager remains amenable to working in a separate address space. Be careful not to confuse Addr with void *.

.addr.ops: Limited arithmetic is allowed on addresses using AddrAdd() and AddrOffset() (impl.c.mpm). Addresses may also be compared using the relational operators ==, !=, <, <=, >, and >=.

.addr.ops.mem: We need efficient operators similar to memset(), memcpy(), and memcmp() on Addr; these are called AddrSet(), AddrCopy(), and AddrComp(). When Addr is compatible with void *, these are implemented through the functions mps_lib_memset(), mps_lib_memcpy(), and mps_lib_memcmp() functions in the plinth (impl.h.mpm).

.addr.conv.c: Addr is converted to mps_addr_t in the MPS C Interface. mps_addr_t is defined to be the same as void *, so using the MPS C Interface confines the memory manager to the same address space as the client data.

.addr.readonly: For read-only addresses, see .readonlyaddr.

Word Align

.align: Align is an unsigned integral type which is used to represent the alignment of managed addresses. All alignments are positive powers of two. Align is large enough to hold the maximum possible alignment.

.align.use: Align should be used whenever the code needs to deal with the alignment of a managed address.

.align.conv.c: Align is converted to mps_align_t in the MPS C Interface.

unsigned Attr

.attr: Pool attributes. A bitset of pool class attributes, which are:

Attribute Description
AttrGC Is garbage collecting, that is, parts may be reclaimed. Used to decide which segments are condemned.
AttrMOVINGGC Is moving, that is, objects may move in memory. Used to update the set of zones that might have moved and so implement location dependency.

There is an attribute field in the pool class (PoolClassStruct) which declares the attributes of that class. See design.mps.pool.field.attr.

int Bool

.bool: The Bool type is mostly defined so that the intention of code is clearer. In C, Boolean expressions evaluate to int, so Bool is in fact an alias for int.

.bool.value: Bool has two values, TRUE and FALSE. These are defined to be 1 and 0 respectively, for compatibility with C Boolean expressions (so one may set a Bool to the result of a C Boolean expression).

.bool.use: Bool is a type which should be used when a Boolean value is intended, for example, as the result of a function. Using a Boolean type in C is a tricky thing. Non-zero values are “true” (when used as control conditions) but are not all equal to TRUE. Use with care.

.bool.check: BoolCheck() simply checks whether the argument is TRUE (1) or FALSE (0).

.bool.check.inline: The inline macro version of BoolCheck casts the int to unsigned and checks that it is <= 1. This is safe, well-defined, uses the argument exactly once, and generates reasonable code.

.bool.check.inline.smaller: In fact we can expect that the “inline” version of BoolCheck() to be smaller than the equivalent function call. On IA-32 for example, a function call will be 3 instructions (total 9 bytes), the inline code for BoolCheck() will be 1 instruction (total 3 bytes) (both sequences not including the test which is the same length in either case).

.bool.check.inline.why: As well as being smaller (see .bool.check.inline.smaller) it is faster. On 1998-11-16 drj compared w3i3mv\hi\amcss.exe running with and without the macro for BoolCheck on the PC Aaron. “With” ran in 97.7% of the time (averaged over 3 runs).

.bool.bitfield: When a Boolean needs to be stored in a bitfield, the type of the bitfield must be unsigned:1, not Bool:1. (That’s because the two values of the type Bool:1 are 0 and -1, which means that assigning TRUE would require a sign conversion.) To make it clear why this is done, misc.h provides the BOOLFIELD macro.

.bool.bitfield.assign: To avoid warnings about loss of data from GCC with the -Wconversion option, misc.h provides the BOOLOF macro for coercing a value to an unsigned single-bit field.

.bool.bitfield.check: A Boolean bitfield cannot have an incorrect value, and if you call BoolCheck() on such a bitfield then GCC 4.2 issues the warning “comparison is always true due to limited range of data type”. When avoiding such a warning, reference this tag.

unsigned BufferMode

.buffermode: BufferMode is a bitset of buffer attributes. See design.mps.buffer. It is a sum of the following:

Mode Description
BufferModeATTACHED Buffer is attached to a region of memory.
BufferModeFLIPPED Buffer has been flipped.
BufferModeLOGGED Buffer remains permanently trapped, so that all reserve and commit events can be logged.
BufferModeTRANSITION Buffer is in the process of being detached.
unsigned char Byte

.byte: Byte is an unsigned integral type corresponding to the unit in which most sizes are measured, and also the units of sizeof.

.byte.use: Byte should be used in preference to char or unsigned char wherever it is necessary to deal with bytes directly.

.byte.source: Byte is a just pedagogic version of unsigned char, since char is the unit of sizeof.

Word Clock

.clock: Clock is an unsigned integral type representing clock time since some epoch.

.clock.use: A Clock value is returned by the plinth function mps_clock. It is used to make collection scheduling decisions and to calibrate the time stamps on events in the telemetry stream.

.clock.units: The plinth function mps_clocks_per_sec defines the units of a Clock value.

.clock.conv.c: Clock is converted to mps_clock_t in the MPS C Interface.

unsigned Compare

.compare: Compare is the type of tri-state comparison values.

Value Description
CompareLESS A value compares less than another value.
CompareEQUAL Two values compare the same.
CompareGREATER A value compares greater than another value.
Word Count

.count: Count is an unsigned integral type which is large enough to hold the size of any collection of objects in the MPS.

.count.use: Count should be used for a number of objects (control or managed) where the maximum number of objects cannot be statically determined. If the maximum number can be statically determined then the smallest unsigned integer with a large enough range may be used instead (although Count may be preferable for clarity).

.count.use.other: Count may also be used to count things that aren’t represented by objects (for example, levels), but only where it can be determined that the maximum count is less than the number of objects.

Size Epoch

.epoch: An Epoch is a count of the number of flips that have occurred, in which objects may have moved. It is used in the implementation of location dependencies.

Epoch is converted to mps_word_t in the MPS C Interface, as a field of mps_ld_s.

unsigned FindDelete

.finddelete: FindDelete represents an instruction to one of the find methods of a Land as to what it should do if it finds a suitable block. See design.mps.land. It takes one of the following values:

Value Description
FindDeleteNONE Don’t delete after finding.
FindDeleteLOW Delete from low end of block.
FindDeleteHIGH Delete from high end of block.
FindDeleteENTIRE Delete entire block.
void (*Fun)(void)

.fun: Fun is the type of a pointer to a function about which nothing more is known.

.fun.use: Fun should be used where it’s necessary to handle a function in a polymorphic way without calling it. For example, if you need to write a function g which passes another function f through to a third function h, where h knows the real type of f but g doesn’t.

Word Index

.index: Index is an unsigned integral type which is large enough to hold any array index.

.index.use: Index should be used where the maximum size of the array cannot be statically determined. If the maximum size can be determined then the smallest unsigned integer with a large enough range may be used instead.

unsigned LocusPrefKind

.locusprefkind: The type LocusPrefKind expresses a preference for addresses within an address space. It takes one of the following values:

Kind Description
LocusPrefHIGH Prefer high addresses.
LocusPrefLOW Prefer low addresses.
LocusPrefZONESET Prefer addresses in specified zones.
unsigned MessageType

.messagetype: MessageType is the type of a message. See design.mps.message. It takes one of the following values:

Message type Description
MessageTypeFINALIZATION A block is finalizable.
MessageTypeGC A garbage collection finished.
MessageTypeGCSTART A garbage collection started.
unsigned Rank

.rank: Rank is an enumeration which represents the rank of a reference. The ranks are:

Rank Index Description
RankAMBIG 0 The reference is ambiguous. That is, it must be assumed to be a reference, but not updated in case it isn’t.
RankEXACT 1 The reference is exact, and refers to an object.
RankFINAL 2 The reference is exact and final, so special action is required if only final or weak references remain to the object.
RankWEAK 3 The reference is exact and weak, so should be deleted if only weak references remain to the object.

Rank is stored with segments and roots, and passed around.

Rank is converted to mps_rank_t in the MPS C Interface.

The ordering of the ranks is important. It is the order in which the references must be scanned in order to respect the properties of references of the ranks. Therefore they are declared explicitly with their integer values.

Note

Could Rank be an unsigned short or unsigned char?

Note

This documentation should be expanded and moved to its own document, then referenced from the implementation more thoroughly.

unsigned RankSet

.rankset: RankSet is a set of ranks, represented as a bitset.

const struct AddrStruct *ReadonlyAddr

.readonlyaddr: ReadonlyAddr is the type used for managed addresses that an interface promises it will only read through, never write. Otherwise it is identical to Addr.

Addr Ref

.ref: Ref is a reference to a managed object (as opposed to any old managed address). Ref should be used where a reference is intended.

Note

This isn’t too clear – richard

Word RefSet

.refset: RefSet is a conservative approximation to a set of references. See design.mps.collection.refsets.

int Res

.res: Res is the type of result codes. A result code indicates the success or failure of an operation, along with the reason for failure. Like Unix error codes, the meaning of the code depends on the call that returned it. These codes are just broad categories with mnemonic names for various sorts of problems.

Result code Description
ResOK The operation succeeded. Return parameters may only be updated if OK is returned, otherwise they must be left untouched.
ResCOMMIT_LIMIT The arena’s commit limit would have been exceeded as a result of allocation.
ResFAIL Something went wrong which doesn’t fall into any of the other categories. The exact meaning depends on the call. See documentation.
ResIO An I/O error occurred. Exactly what depends on the function.
ResLIMIT An internal limitation was reached. For example, the maximum number of somethings was reached. We should avoid returning this by not including static limitations in our code, as far as possible. (See rule.impl.constrain and rule.impl.limits.)
ResMEMORY Needed memory (committed memory, not address space) could not be obtained.
ResPARAM An invalid parameter was passed. Normally reserved for parameters passed from the client.
ResRESOURCE A needed resource could not be obtained. Which resource depends on the call. See also ResMEMORY, which is a special case of this.
ResUNIMPL The operation, or some vital part of it, is unimplemented. This might be returned by functions which are no longer supported, or by operations which are included for future expansion, but not yet supported.

.res.use: Res should be returned from any function which might fail. Any other results of the function should be passed back in “return” parameters (pointers to locations to fill in with the results).

Note

This is documented elsewhere, I think – richard

.res.use.spec: The most specific code should be returned.

unsigned RootMode

.rootmode: RootMode is an unsigned integral type which is used to represent an attribute of a root:

Root mode Description
RootModeCONSTANT Client program will not change the root after it is registered.
RootModePROTECTABLE Root is protectable: the MPS may place a barrier on any page containing any part of the root.
RootModePROTECTABLE_INNER Root is protectable: the MPS may place a barrier on any page completely covered by part of the root.

.rootmode.const.unused: RootModeCONSTANT has no effect. This mode 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.)

.rootmode.conv.c: RootMode is converted to mps_rm_t in the MPS C Interface.

unsigned RootVar

.rootvar: The type RootVar is the type of the discriminator for the union within RootStruct.

unsigned Serial

.serial: A Serial is a number which is assigned to a structure when it is initialized. The serial number is taken from a field in the parent structure, which is incremented. Thus, every instance of a structure has a unique “name” which is a path of structures from the global root. For example, “the third arena’s fifth pool’s second buffer”.

Why? Consistency checking, debugging, and logging. Not well thought out.

unsigned Shift

.shift: Shift is an unsigned integral type which can hold the amount by which a Word can be shifted. It is therefore large enough to hold the word width (in bits).

.shift.use: Shift should be used whenever a shift value (the right-hand operand of the << or >> operators) is intended, to make the code clear. It should also be used for structure fields which have this use.

Note

Could Shift be an unsigned short or unsigned char?

unsigned long Sig

.sig: Sig is the type of signatures, which are written into structures when they are created, and invalidated when they are destroyed. They provide a limited form of run-time type checking and dynamic scope checking. See design.mps.sig.

Word Size

.size: Size is an unsigned integral type large enough to hold the size of any object which the MPS might manage.

.size.byte: Size should hold a size calculated in bytes.

Warning

This is violated by GenParams.capacity (which is measured in kilobytes).

.size.use: Size should be used whenever the code needs to deal with the size of managed memory or client objects. It should not be used for the sizes of the memory manager’s own data structures, so that the memory manager is amenable to working in a separate address space. Be careful not to confuse it with size_t.

.size.ops: SizeIsAligned(), SizeAlignUp(), SizeAlignDown() and SizeRoundUp().

.size.conv.c: Size is converted to size_t in the MPS C Interface. This constrains the memory manager to the same address space as the client data.

unsigned TraceId

.traceid: A TraceId is an unsigned integer which is less than TraceLIMIT. Each running trace has a different TraceId which is used to index into the tables and bitfields that record the state of that trace. See design.mps.trace.instance.limit.

unsigned TraceSet

.traceset: A TraceSet is a bitset of TraceId, represented in the obvious way:

member(ti, ts) ⇔ ((1<<ti) & ts) != 0

In the multiple-traces design, each region of memory may be a different colour for each trace. Thus the set of traces for which a segment is grey (say) is represented by a TraceSet. See design.mps.trace.

unsigned TraceStartWhy

.tracestartwhy: TraceStartWhy represents the reason that a trace was started. It takes one of the following values:

Reason Description
TraceStartWhyCHAIN_GEN0CAP Generation zero of a chain reached capacity.
TraceStartWhyDYNAMICCRITERION Need to start full collection now, or there won’t be enough memory to complete it.
TraceStartWhyOPPORTUNISM Client had idle time available.
TraceStartWhyCLIENTFULL_INCREMENTAL Client requested incremental collection.
TraceStartWhyCLIENTFULL_BLOCK Client requested full collection.
TraceStartWhyWALK Walking references.
TraceStartWhyEXTENSION Request by MPS extension.
unsigned TraceState

.tracestate: TraceState represents the current state in a trace’s lifecycle. See design.mps.trace. It takes one of the following values:

State Description
TraceINIT Nothing happened yet.
TraceUNFLIPPED Segments condemned (made white); initial grey set created; scanning rate calculated.
TraceFLIPPED Buffers flipped; roots scanned; location dependencies made stale; grey segments protected.
TraceRECLAIM There are no outstanding grey segments.
TraceFINISHED All segments reclaimed.
MPS_T_ULONGEST ULongest

.ulongest: ULongest is the longest unsigned integer on the platform. (We used to use unsigned long but this assumption is violated by 64-bit Windows.) This type should be used for calculations where any integer might be passed. Notably, it is used in WriteF() to print any integer.

MPS_T_WORD Word

.word: Word is an unsigned integral type which matches the size of the machine word, that is, the natural size of the machine registers and addresses.

.word.use: Word should be used where an unsigned integer is required that might range as large as the machine word.

.word.source: Word is derived from the macro MPS_T_WORD which is declared in impl.h.mpstd according to the target platform (design.mps.config.pf.word).

.word.conv.c: Word is converted to mps_word_t in the MPS C Interface.

.word.ops: WordIsAligned(), WordAlignUp(), WordAlignDown() and WordRoundUp().

MPS_T_WORD Work

.work: Work is an unsigned integral type representing accumulated work done by the collector.

.work.impl: Work is implemented as a count of the bytes scanned by the collector in segments and roots. This is a very crude measure, because it depends on the scanning functions supplied by the mutator, which we know very little about.

Word ZoneSet

.zoneset: ZoneSet is a conservative approximation to a set of zones. See design.mps.collection.refsets.

40.4. Abstract types

.adts: The following types are abstract data types, implemented as pointers to structures. For example, Ring is a pointer to a RingStruct. They are described elsewhere.

AllocFrame, AllocPattern, AP, Arena, BootBlock, Buffer, Chain, Chunk, Format, Globals, Land, LD, Lock, LocusPref, MutatorContext, PoolClass, Page, Pool, PoolDebugMixin, Range, Ring, Root, ScanState, Seg, SegBuf, StackContext, Thread, Trace, VM.

void *Pointer

.pointer: The type Pointer is the same as void *, and exists to sanctify functions such as PointerAdd().