This wiki article contains incomplete and informal notes about the MPS, the precursor to more formal documentation. Not confidential. Readership: MPS users and developers.
We would like a 'map' from a client's requirements to the recommended pool class:
Do you need garbage collection? Do you have objects with no references in them? Do you need to pass buffers to system calls? etc etc You need mps_class_lo.
General-purpose automatic (collecting) pool class. This is the most 'advanced' pool class in the MPS, intended for most client objects.
AMC is "Automatic, Mostly Copying": it uses copying collection except when prevented by ambiguous references. It is generational.
Chain: specify capacity and mortality of generations 0..N-1. Survivors from N-1 get promoted into an arena-wide topGen (often anachronistically called the "dynamic" generation).
General-purpose leaf-only pool class (for objects that contain no references). A variant of AMC (the Z means "Zero rank", ie. containing no references).
Non-moving automatic (collecting) pool class.
AMS is "Automatic Mark & Sweep". Not generational.
Chain: specify capacity and mortality of 'generation' 0. [Why? Perhaps to trigger nursery-like collections? New 2001-03-02. RHSK 2006-11-27]
Non-moving, non-protecting, automatic (collecting), Leaf Only pool class (for objects that contain no references). Unit test: locv.c. RefMan: -undocumented-.
This pool class should really be called "flat data that needs to be accessed by foreign code" -- it's ideal for allocating a buffer to pass to an operating system I/O call. It is not very fast. [Conversation with DRJ, 2006-07].
(For a general-purpose leaf-only pool see AMCZ).
[Internal note: has a dummy chain: 1MiB 20%]
Automatic Weak Linked
For weak references, linked to normal references. The purpose of this pool class is to allow the client to implement hash tables (or, conceivably some similar datastructures) that are partly or wholly weak. A client might want a weak-key strong-value table, or a strong-key weak-value table (or in fact weak-key weak-value). For example, Java's java.util.WeakHashMap class.
The principle idea behind a weak-key strong-value hash table is that the keys are weakly referenced, so their presence in the table will not prevent the key object from being garbage collected. Once the key is no longer reachable, weak references to it may get splatted. Obviously once that has happened you can't get at the value corresponding to the key anymore, so the implementation is free to splat the value slot as well.
Pool Class AWL allows the implementation to splat the value slot at the same time that the (weak) key slot is splatted. (Or the other way around if you have strong-key weak-value tables).
Exactly how you do this is not yet well documented (but see below for more hints).
AWL has another special power: it enables better handing of barrier hits on weak objects. To explain the benefit we need to describe a problem first. The MPS uses a read-barrier to perform incremental garbage collection [@@ link to canned-for-client explanation of how a garbage collector works in broad terms]. When the client tries to read an object containing weak references the MPS may have protected it so that the MPS can process the object before the client gets to see it. The problem for weak objects is that the client may try and access the object at a point in the collection cycle when the MPS cannot yet determine the status of the objects that the weak object refers to. What the MPS does in this situation is assume that all the referenced objects are going to live. This assumption is correct but conservative; it may result in objects that are weakly referenced staying alive for longer than they need to. In the worst case this can result in a very large amount of memory being used by objects that are no longer needed.
In order to combat this problem the MPS sometimes does the following: Instead of processing the entire weak object and unprotecting it so that the client can access the object the MPS may emulate the processor instruction. When this happens the MPS doesn't process the entire weak object, it only processes the exact location that was being accessed (typically a single word), it emulates the processor instruction, and it keeps the object protected. This happens invisibly from the client's perspective, it's exactly as if the instruction executed as normal. The MPS instead of processing the entire object processes just a single word.
Naturally this emulation business is delicate and hairy and involves staring at the most badly written parts of low-level processor architecture manuals for days.
Emulation of accesses to protected objects happens when:
Because of this emulation, AWL places a restriction on the format of objects allocated in it:
All slots in an object must either be a valid word-aligned reference, or the bottom bits of the word must be non-zero so that it does not look like an aligned pointer. "Aligned pointer" means a word whose numeric value (that is, treated as an unsigned integer) is a multiple of the architecture's natural word size (in bytes). In the very likely event that you're using a 32-bit machine that means that an aligned poiner is a multiple of 4 and its bottom 2 bits are both 0. Bottom line: pointers must be untagged and aligned, ints must be tagged with a non-zero tag.
AWL is one of the few pools that can allocate objects that contain
non-exact references. The mps_ap_create method when
used with an AWL pool accepts an extra argument, which is a
rank of type mps_rank_t. The rank is either
MPS_RANK_EXACT (to allocate ordinary objects contained
exact references), or MPS_RANK_WEAK (to allocate
objects that contain weak references). Example:
if(MPS_RES_OK != mps_ap_create(&weakap, tablepool, MPS_RANK_WEAK) {
/* Error. */
...
}
...
[Internal note: has a dummy chain: 2^32KiB 50%]
(This pool is not for MPS clients to use; it is for MPS developers).
PoolClassN is the "null pool class" -- it is an example, an empty template. It has trivial implementations of all the necessary pool class methods. It is intended as good starting point when implementing a new pool class.
(Additonal historical material, not publically available: a survey from 1998 that still contains confidential material: guide.mps.pool-classes by RIT ∅).
You need to pass a FindDependentMethod to
mps_pool_create.
Here are some notes:
...
The "dependent object" is an object which
the scan method is permitted to update. The awlScanObject function
Exposes that object before the scan and Covers it afterwards, to allow
the update to take place. It also discards the MPS "summary" for that
object's segment (the "summary" of a segment is a conservative
approximation of the objects pointed to by objects in that segment;
since the scan method is now allowed to update the segment to point to
anything else, the summary has to be discarded).
If the keys and values of hash tables are stored in separate linear
tables (a key table and a value table), then for a weak-key table the
scan method for the key table may need to update the value table (to
null out the corresponding value if a key goes away on fix). So the
dependent object for the key table is the value table. For weak-value
tables, the relationship is the other way around.
The dylan format works like that, and here's the relevant code from my
auto-header variant of that. First dylan_weak_dependent, which is the
dependent-object method. Then dylan_scan_contig_weak, which is the
innermost part of the scan method for those weak tables. The comment
"delete corresponding entry" is where the scan method updates the
value table.
/* dylan_weak_dependent -- returns the linked object, if any.
*/
extern mps_addr_t dylan_weak_dependent(mps_addr_t parent)
{
mps_word_t *object;
mps_word_t *wrapper;
mps_word_t fword;
mps_word_t fl;
mps_word_t ff;
assert(parent != NULL);
object = (mps_word_t *)parent;
wrapper = (mps_word_t *)object[0];
assert(dylan_wrapper_check(wrapper));
fword = wrapper[3];
ff = fword & 3;
/* traceable fixed part */
assert(ff == 1);
fl = fword & ~3uL;
/* at least one fixed field */
assert(fl >= 1);
return (mps_addr_t) object[1];
}
/* Scan weakly a contiguous array of references in [base, limit). */
/* Only required to scan vectors for Dylan Weak Tables. */
/* Depends on the vector length field being scannable (ie a tagged */
/* integer). */
/* When a reference that has been fixed to NULL is detected the */
/* corresponding reference in the associated table (pointed to be the */
/* assoc variable) will be deleted. */
static mps_res_t
dylan_scan_contig_weak(mps_ss_t mps_ss,
mps_addr_t *base, mps_addr_t *limit,
mps_addr_t *objectBase, mps_addr_t *assoc)
{
mps_addr_t *p;
mps_res_t res;
mps_addr_t r;
MPS_SCAN_BEGIN(mps_ss) {
p = base;
goto skip_inc;
loop:
++p;
skip_inc:
if(p >= limit)
goto out;
r = *p;
if(((mps_word_t)r & 3) != 0) /* non-pointer */
goto loop;
if(!MPS_FIX1(mps_ss, r))
goto loop;
res = MPS_FIX2(mps_ss, p);
if(res == MPS_RES_OK) {
if(*p == 0 && r != 0) {
if(assoc != NULL) {
assoc[p-objectBase] = 0; /* delete corresponding entry */
}
}
goto loop;
}
return res;
out:
assert(p == limit);
} MPS_SCAN_END(mps_ss);
return MPS_RES_OK;
}
If your scan method won't need to update any other object while
scanning a weak object, the dependent-object method should return
NULL.
Source: //info.ravenbrook.com/mail/2002/04/12/15-52-29/0.txt ∅ //info.ravenbrook.com/mail/2002/04/12/15-56-15/0.txt ∅ .
2006-06-02 RHSK Created.
2006-06-23 RHSK Link to RIT's 1998 guide.mps.pool-classes.
2006-06-28 RHSK Notes on AWL dependent object and scan method.
2006-08-02 RHSK LO is for foreign code; for leaf-only use AMCZ.
How to choose the right pool class.
2006-08-07 RHSK AMC.
2006-11-27 RHSK Chains.
2009-09-17 RHSK PoolClassN.
This document is copyright © 2006,2009 Ravenbrook Limited. All rights reserved. This is an open source license. Contact Ravenbrook for commercial licensing options.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
This software is provided by the copyright holders and contributors "as is" and any express or implied warranties, including, but not limited to, the implied warranties of merchantability, fitness for a particular purpose, or non-infringement, are disclaimed. In no event shall the copyright holders and contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.