LEAF OBJECT POOL CLASS
                           design.mps.poollo
                             incomplete doc
                             drj 1997-03-07

INTRODUCTION

.readership: Any MPS developer.

.intro: The Leaf Object Pool Class (LO for short) is a pool class developed for 
DylanWorks.  It is designed to manage objects that have no references (leaf 
objects) such as strings, bit tables, etc.  It is a garbage collected pool (in 
that objects allocated in the pool are automatically reclaimed when they are 
discovered to be unreachable.

[Need to sort out issue of alignment.  Currently lo grabs alignment from 
format, almost certainly "ought" to use the greater of the format alignment and 
the MPS_ALIGN value -- @@ drj 1997-07-02]

DEFINITIONS

.def.leaf: A "leaf" object is an object that contains no references, or an 
object all of whose references refer to roots.  That is, any references that 
the object has must refer to a priori alive objects that are guaranteed not to 
move, hence the references do not need fixing.

.def.grain: A grain (of some alignment) is a contiguous aligned area of memory 
of the smallest size possible (which is the same size as the alignment).


REQUIREMENTS

.req.source: See req.dylan.fun.obj.alloc and req.dylan.prot.ffi.access.

.req.leaf: The pool must manage formatted leaf objects (see .def.leaf above for 
a defintion).  This is intended to encompass Dylan and C leaf objects.  Dylan 
leaf objects have a reference to their wrapper, but are still leaf objects (in 
the sense of .def.leaf) because the wrapper will be a root.

.req.nofault: The memory caontaining objects managed by the pool must not be 
protected.  The client must be allowed to access these objects without using 
the MPS trampoline (the exception mechanism, q.v.).


OVERVIEW

.overview:
.overview.ms: The LO Pool is a non-moving mark-and-sweep collector.  
.overview.ms.justify: mark-and-sweep pools are simpler than moving pools.  
.overview.alloc: Objects are allocated in the pool using the reserve commit 
protocol on allocation points.  .overview.format: The pool is formatted.  The 
format of the objects in the pool is specified at instantiation time, using an 
format object derived from a format A variant (using variant A is overkill, see 
.if.init below) (see design.mps.format for excuse about calling the variant 
'variant A').


INTERFACE

.if.init:
.if.init.args: The init method for this class takes one extra parameter in the 
vararg parameter list.  .if.init.format: The extra parameter should be an 
object of type Format and should describe the format of the objects that are to 
be allocated in the pool.  .if.init.format.use: The pool uses the skip and 
alignment slots of the format.  The skip method is used to determine the length 
of objects (during reclaim).  The alignment field is used to determine the 
granularity at which memory should be managed.  .if.init.format.a: Currently 
only format variant A is supported though clearley that is overkill as only 
skip and alignment are used.


DATASTRUCTURES

.sig:  The signature for the LO Pool Class is 0x51970b07 (SIGLOPOoL).

.poolstruct: The class specific pool structure is:
typedef struct LOStruct {
  PoolStruct poolStruct;        /* generic pool structure */
  Format format;                /* format for allocated objects */
  Shift alignShift;
  Sig sig;                      /* impl.h.misc.sig */
} LOStruct;

.poolstruct.format: This is the format of the objects that are allocated in the 
pool.

.poolstruct.alignShift: This is shift used in alignment computations.  It is 
SizeLog2(pool->alignment).  It can be used on the right of a shift operator (<< 
or >>) to convert between a number of bytes and a number of grains.

.loseg: Every segment is an instance of segment class LOSegClass, a subclass of 
GCSegClass, and is an object of type LOSegStruct.  

.loseg.purpose: The purpose of the LOSeg structure is to associate the bit 
tables used for recording allocation and mark information with the segment.

.loseg.decl:  The declaration of the structure is as follows:

typedef struct LOSegStruct {
  GCSegStruct gcSegStruct;  /* superclass fields must come first */
  LO lo;                    /* owning LO */
  BT mark;                  /* mark bit table */
  BT alloc;                 /* alloc bit table */
  Count free;               /* number of free grains */
  Sig sig;                  /* impl.h.misc.sig */
} LOSegStruct;

.loseg.sig: The signature for a loseg is 0x519705E9 (SIGLOSEG).

.loseg.lo: The lo field points to the LO structure that owns this segment.

.loseg.bit:  Bit Tables (see design.mps.bt) are used to record allocation and 
mark information.  This is relatively straightforward, but might be inefficient 
in terms of space in some circumstances.

.loseg.mark: This is a Bit Table that is used to mark objects during a trace.  
Each grain in the segment is associated with 1 bit in this table.  When LOFix 
(see .fun.fix below) is called the address is converted to a grain within the 
segment and the corresponding bit in this table is set.

.loseg.alloc: This is a Bit Table that is used to record which addresses are 
allocated.  Addresses that are allocated and are not buffered have their 
corresponding bit in this table set.  If a bit in this table is reset then 
either the address is free or is being buffered.

.loseg.diagram: The following diagram is now obsolete. It's also not very 
interesting - but I've left the sources in case anyone ever gets around to 
updating it. tony 1999-12-16




FUNCTIONS


External

.fun.init:

.fun.destroy:

.fun.buffer-fill:

[explain way in which buffers interact with the alloc table and how it could be 
improved]

.fun.buffer-empty:

.fun.condemn:

.fun.fix:

static Res LOFix(Pool pool, ScanState ss, Seg seg, Ref *refIO)

[sketch]
Fix treats references of most ranks much the same.  There is one mark table 
that records all marks.  A reference of rank RankAMBIG is first checked to see 
if it is aligned to the pool alignment and discarded if not.  The reference is 
converted to a grain number within the segment (by subtracting the segments' 
base from the refrence and then dividing by the grain size).  The bit (the one 
corresponding to the grain number) is set in the mark table.  Exception, for a 
weak reference (rank is RankWEAK) the mark table is checked and the reference 
is fixed to 0 if this address has not been marked otherwise nothing happens.  
Note that there is no check that the reference refers to a valid object 
boundary (which wouldn't be a valid check in the case of ambiguous references 
anyway).

.fun.reclaim:

static void LOReclaim(Pool pool, Trace trace, Seg seg)

LOReclaim derives the loseg from the seg, and calls loSegReclaim (see 
.fun.segreclaim below).


Internal

.fun.segreclaim:

static void loSegReclaim(LOSeg loseg, Trace trace)

[sketch]
for all the contiguous allocated regions in the segment it locates the 
boundaries of all the objects in that region by repeatedly skipping (calling 
format->skip) from the beginning of the region (the beginning of the region is 
guaranteed to coincide with the beginning of an object).  For each object it 
examines the bit in the mark bit table that corresponds to the beginning of the 
object.  If that bit is set then the object has been marked as a result of a 
previous call to LOFix, the object is preserved by doing nothing.  If that bit 
is not set then the object has not been marked and should be reclaimed; the 
object is reclaimed by resetting the appropriate range of bits in the segment's 
free bit table.

[special things happen for buffered segments]

[explain how the marked variable is used to free segments]

ATTACHMENT
   "LOGROUP.CWK"

A. References

B. Document History

C. Copyright and License

This document is copyright © 1995-2002 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:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Redistributions in any form must be accompanied by information on how to obtain complete source code for the this software and any accompanying software that uses this software. The source code must either be included in the distribution or be available for no more than the cost of distribution plus a nominal fee, and must be freely redistributable under reasonable conditions. For an executable file, complete source code means the source code for all modules it contains. It does not include source code for modules or files that typically accompany the major components of the operating system on which the executable file runs.

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.