THE DESIGN OF THE GENERAL MPS TYPES
                            design.mps.type
                             incomplete doc
                           richard 1996-10-23

INTRODUCTION

.intro:

See impl.h.mpmtypes.


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.


CONCRETE TYPES


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 intel 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).


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.

ResOK: The operation succeeded.  Return parameters may only be updated if OK is 
returned, otherwise they must be left untouched.
ResFAIL: Something went wrong which doesn't fall into any of the other 
categories.  The exact meaning depends on the call.  See documentation.
ResRESOURCE: A needed resource could not be obtained.  Which resource depends 
on the call.  See also MEMORY, which is a special case of this.
ResMEMORY: Needed memory (committed memory, not address space) could not be 
obtained.
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.)
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.
ResIO: An I/O error occurred.  Exactly what depends on the function.
ResCOMMIT_LIMIT: The arena's commit limit would have been exceeded as a reult 
of allocation.
ResPARAM: An invalid parameter was passed.  Normally reserved for parameters 
passed from the client.

.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).  [This is documented elsewhere, I 
think -- richard].res.use.spec: The most specific code should be returned.


Fun

.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 without 
calling it in a polymorphic way.  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

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

.word.use: It 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.

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


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().


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.


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).  [ Should Count be used to count things that aren't represented 
by objects (e.g. a level)?  I would say yes.  gavinm 1998-07-21 ] [Only where 
it can be determined that the maximum count is less than the number of 
objects.  pekka 1998-07-21]


Accumulation

.accumulation: Accumulation is an arithmetic type which is large enough to hold 
accumulated totals of objects of bytes (e.g. total number of objects allocated, 
total number of bytes allocated).

.accumulation.type: Currently it is double, but reason for the interface is so 
that we can more easily change it if we want to (if we decide we need more 
accuracy for example).

.accumulation.use: Currently the only way to use an Accumulation is to reset it 
(AccumulatorReset) and accumulate (Accumulate) amounts into it.  There is no 
way to read it at the moment, but that's okay, because noone seems to want to.  
.accumulation.future: Probably we should have methods which return the 
accumulation into an unsigned long, and also a double; these functions should 
return bools to indicate whether the accumulation can fit in the requested 
type.  Possibly we could have functions which returned scaled accumulations 
(e.g. AccumulatorScale(a, d) would divide the Accumulation a by double d and 
return the double result if the result fitted into a double).


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 mps_lib_mem* functions in the plinth (impl.h.mpm) [and 
in fact, no other implementation exists at present, pekka 1998-09-07].

.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.


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 may not 
be true for all existing code.

.size.use: Size should be used whenever the code needs to deal with the size of 
managed memory or client objects.  Is 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: [Size operations?]

.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.


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.


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.

.shift.conv.c: Shift is converted to mps_shift_t in the MPS C Interface.


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.

[This isn't too clear -- richard]


RefSet

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


Rank

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

RankAMBIG (0): the reference is ambiguous, i.e. must be assumed to be a 
reference, and not update 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.

[Could Rank be a short?]

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


Epoch

.epoch: An Epoch is a count of the number of flips that the mutator have 
occurred.  [Is it more general than that?]  It is used in the implementation of 
location dependencies (LDs).

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


TraceId

.traceid: A TraceId is an unsigned integer which is less than TRACE_MAX.  Each 
running trace has a different TraceId which is used to index into tables and 
bitfields used to remember the state of that trace.


TraceSet

.traceset: A TraceSet is a bitset of TraceIds, represented in the obvious way, 
i.e.

  member(ti, ts) <=> (2^ti & ts) != 0

TraceSets are used to represent colour in the Tracer.  [Expand on this.]


AccessSet

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


Attr

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

  AttrFMT: the pool contains formatted objects;

  AttrSCAN: the pool contains references and must be scanned for GC;

  AttrPM_NO_READ: the pool may not be read protected;

  AttrPM_NO_WRITE: the pool may not be write protected;

  AttrALLOC: the pool supports the PoolAlloc interface;

  AttrFREE: the pool supports the PoolFree interface;

  AttrBUF: the pool supports the allocation buffer interface;

  AttrBUF_RESERVE: the pool suppors the reserve/commit protocol on allocation 
buffers;

  AttrBUF_ALLOC: the pool supports the alloc protocol on allocation buffers;

  AttrGC: the pool is garbage collecting, i.e. parts may be reclaimed;

  AttrINCR_RB: the pool is incremental requiring a read barrier;

  AttrINCR_WB: the pool is incremental requiring a write barrier.

There is an attribute field in the pool class (PoolClassStruct) which declares 
the attributes of that class.  These attributes are only used for consistency 
checking at the moment. [no longer true that they are only used for consistency 
checking -- drj 1998-05-07]


RootVar

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


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:

  space[3].pool[5].buffer[2]

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


Compare

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

CompareLESS: Indicates that a value compares less than another value. 
CompareEQUAL: Indicates that two value compares the same 
CompareGREATER: Indicates that a value compares greater than another value. 


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 [where?].

  Ring, Buffer, AP, Format, LD, Lock, Pool, Space, PoolClass, Trace,
  ScanState, Seg, Arena, VM, Root, Thread.


POINTERS

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