memtree.c

地球模拟器

/* memtree.c   9-9-92 memory allocation routines for the Tierra Simulator */
/* Tierra Simulator V4.0: Copyright (c) 1992 C. J. Stephenson & Virtual Life*/

#ifndef lint
static char     memtreec_sccsid[] = "@(#)memtree.c	1.2     7/21/92";
#endif

#include <sys/types.h>
#include "license.h"
#include "tierra.h"
#include "extern.h"

#ifdef ALCOMM
#include "tmonitor.h"
#include "trequest.h"
#include <mlayer.h>
#endif


#ifdef MEM_CHK
#include <memcheck.h>
#endif

/* This is the file memtree.c 

   This file contains the code for:

       MemInit()    --  Initialize soup allocator
       IsFree()     --  Enquire status of soup addr
       MemAlloc()   --  Allocate an area of the soup
       MemDealloc() --  Deallocate an area of soup   */


/*  _________________________________________________
   |                                                 | 
   |        NEW  SOUP  ALLOCATOR  FOR  TIERRA        |
   |_________________________________________________|


   Program and program notes by C.J.Stephenson, Santa
   Fe, July 1992.

                        *    *    *

   This soup allocator allows the program requesting 
   space to supply a preferred address for allocation,
   and also a tolerance. This permits a dividing creat-
   ure to place its offspring near itself (which may be 
   desirable for self-contained creatures), or scatter-
   ed far and wide (which may make sense for seeds and
   parasites).

      This allocator is also expected to perform better 
   than the previous version.

                        *    *    *

   The `soup' begins at zero and has a size of SoupSize
   (global var). The soup size is constant during a run.

      The soup allocator possesses two main entry points,
   MemAlloc() and MemDealloc().  

      When MemAlloc() is called, it doles out some soup
   by finding an unoccupied area of adequate size.  When 
   MemDealloc() is called, it records that the specified 
   area of soup is no longer occupied (and is therefore
   available for reallocation).

      This soup allocator maintains a record of the unoc-
   cupied areas in a `cartesian' tree.  A cartesian tree
   is a binary search tree in which one property is ord-
   ered horizontally (in this case the soup addr), and
   some other property is ordered vertically (in this
   case the size of the unoccupied area), such that no
   son is `heavier' than its father. Therefore the root
   of the tree always describes the biggest unoccupied
   area.  Here is a picture of such a tree:

                       _________
                      |         |
                      | 300,500 |
                      |_________|
                      /    \
                     /      \
                    /        \
                   /          \
                  /            \
                 /              \
              __/______          \__________
             |         |         |          |
             | 100,100 |         | 1000,200 |
             |_________|         |__________|
             /                   /    \
            /                   /      \
           /                   /        \
        __/___            ____/___       \__________
       |      |          |        |      |          |
       | 0,50 |          | 900,50 |      | 1400,200 |
       |______|          |________|      |__________|
                              \
                               \
                                \
                                 \________
                                 |        |
                                 | 960,10 |
                                 |________|


   A cartesian tree can be maintained by the technique 
   called `root insertion'.  It possesses several nice
   properties:

   (1)  The method offers better performance than list
        methods (and does not impose course granularity
        or possess the other restrictions of the `buddy'
        methods).  When allocating, an area of adequate
        size can be found by descending from the root 
        and examining only the areas of adequate size,
        without needing to inspect the numerous scraps
        of inadequate size (which are relegated to the 
        lower branches and the leaves).  And when deal-
        locating, the area being returned can be placed 
        correctly in the tree, and combined with its 
        neighbour(s) if any, by performing a binary 
        search, which usually requires far less work
        than searching a list.

        (Note however that the tree is not balanced, and
        cannot in general be balanced, so the worst-case
        performance is still bad, though rarely encount-
        ered in practice.  Techniques exist for alleviat-
        ing the worst case, but they are not used in this
        program.)

   (2)  The method allows several interesting allocation
        policies to be offered cheaply:

        (a) `Friendly Fit'.  The caller of MemAlloc() 
        can supply a preferred addr for allocation, and
        an acceptable tolerance. The allocator can find 
        the nearest unoccupied area (of adequate size) 
        by performing a binary search for the prefer-
        red address. If the nearest area is near enough
        (i.e. within the given tolerance), the allocator
        supplies some soup from this area; otherwise it 
        reports that there is no suitably placed soup
        available.

        First fit (or `Leftmost Fit' from the tree) can 
        be realized simply by supplying a preferred addr
        of zero and the most generous tolerance.

        (b) `Better Fit'. Alternatively the caller can
        indicate the absence of a preference, in which
        case the allocator employs a policy that tends
        to minimize fragmentation of the soup.

      Control over placement is the issue that motivated
   this new allocator.  In Tierra, proximity in the soup
   has semantic significance, since it affects the inter-
   actions between creatures.  It therefore seems desir-
   able to give Mama some control over the position of
   her offspring.

      For a description of root insertion, see:

      [1]  C.J.Stephenson, A method for constructing
           binary search trees by making insertions
           at the root, Int J Comp and Inf Sci, Vol
           9 (1980).

      For the original description of cartesian trees,
      see:

      [2]  J.Vuillemin, A unifying look at data
           structures, CACM Vol 23 (1980).

      For the application of cartesian trees to memory
      allocation, see:

      [3]  C.J.Stephenson, Fast Fits: New methods for
           dynamic storage allocation, Operating Sys
           Review (extended abstract), Vol 17 (1983).

      Note that ref [3] describes a method of memory
      allocation in which the tree is constructed in
      the unoccupied pieces themselves, i.e. in the
      same space that is being managed. In the pre-
      sent application, the tree is constructed in
      separate memory (see below), and not within
      the soup.


   THE NODE ARRAY

      The nodes for the tree are `allocated' from an
   array of nodes, and the tree `ptrs' are represented
   by the indices of the nodes in the array. This per-
   mits the entire tree to be preserved in a file (or
   restored from file) simply be writing (or reading)
   the array.  (A similar scheme was employed in the
   previous soup allocator, and carried over to this
   one.) 

      The structure that describes an indiividual node
   is named MemFr (for `Memory Frame').  It contains 4
   signed fullword integers, laid out thus:

               ___________________________ 
              |             |             |
       MemFr  | l=left ptr  | r=right ptr | 
              |_____________|_____________|
              |             |             |
              | p=soup addr |   s = size  |
              |_____________|_____________|


   where:  l,r  =  `ptrs' to (i.e. indices of) the
                   left and right sons, or zero if
                   corresponding son does not exist

           p,s  =  addr and size of unoccupied area
                   of the soup (0 <= addr < SoupSize,
                   0 < s <= SoupSize)

   The addr of the array is maintained in FreeMem (glob-
   al var) -- and the number of nodes in the array is in 
   MaxFreeBlocks (another global var).  An initial modest
   array is allocated when the program begins, and is en-
   larged as necessary during the course of the run (with
   FreeMem and MaxFreeBocks being adjusted accordingly).
   Here is a picture of the array:

                     ___________
                    |           |            
        FreeMem[0]  |   MemFr   |  Node 0 is special (see below)
                    |___________|
                    |           |            
        FreeMem[1]  |   MemFr   |  Some nodes are used for the tree
                    |___________|  
                    |           |            
        FreeMem[2]  |   MemFr   | 
                    |___________|
                    |           |            
        FreeMem[3]  |   MemFr   |  Some nodes are typically unused
                    |___________|
                    :           :
                    :           :
                    :           :
                    :___________:
                    |           |            
    FreeMem[MFB-1]  |   MemFr   |  (MFB is short for MaxFreeBlocks)
                    |___________|


   The zeroth node in the array acts as an `anchor' for
   the tree -- and also for the unused nodes. It is laid
   out thus:

                  ___________________________ 
                 |             |             |
     FreeMem[0]  | l=`liberty' |  r = `root' |  The anchor
                 |_____________|_____________|
                 |             |             |
                 |    p = 0    |    s = 0    |
                 |_____________|_____________|


   where:  l = `liberty ptr' = anchor for unused nodes
                               (see below), or zero if
                               no unused nodes exist
           
           r =  `root ptr'   = index of the tree root
                               (1 <= r < MFB), or zero
                               if the tree is empty


   UNUSED NODES

      There are two flavours of unused nodes, untouched
   and recycled.

      Untouched nodes are nodes that have never been used
   in the tree.  Their contents are undefined.  They form
   a contiguous group (which may be empty) at the end of
   the array.  The position of the first is identified by 
   a negative `liberty ptr' having a value of u-MFB, where
   u = index of first untouched node; note that this nat-
   urally acquires a value of zero when the last untouch-
   ed node is pressed into service.

      Recycled nodes are nodes that have been used in the
   tree, but are not currently used. They may be sprinkled
   among the nodes that are in use.  They are chained to-   
   gether, via their `l' ptrs, into a free list. 

      The liberty ptr in the anchor identifies the first
   recycled node if any (positive ptr), or the first un-
   touched node otherwise (negative ptr), or it is zero 
   if the array is `full'  If recycled nodes exist, the 
   last one identifies the first untouched node, or con-
   tains a zero ptr if there are no untouched nodes. 

      Fortunately this scheme is easier to implement
   than to describe, and has the nice property that the
   tail of the array is not touched until it is needed
   (or is never touched if never needed), which is good
   for the working set.  [Actually, at the time of writ-
   ing (1992/07), the array is allocated and reallocated  
   with calloc(), which clears the entire thing to zero  
   -- so in truth there is little benefit in postponing 
   contact with the tail.  This soup allocator does not 
   however require the array to be cleared, and malloc()
   could be used instead of calloc(), which would result 
   in slightly better performance.]


   NULL POINTERS IN THE TREE

      In the tree, a left or right ptr of zero indic-
   ates the absence of a left or right son. When examin-
   ing or manipulating the tree, it is usually necessary
   to check for such `null ptrs' explicitly, in order to 
   avoid unwittingly falling out of the tree.  In some 
   contexts, however, it is possible to omit the check, 
   and cunningly plough on regardless (without risking
   a broken arm).

      Consider for example a search for the deepest node
   of adequate size on some particular path through the
   tree.  (For the present purpose, the actual path is
   immaterial.)  If we treat a null left or right ptr as
   a valid tree ptr, we will find ourselves examining node
   0 (the anchor), where the `size' field is permanently
   set to zero. So we will conclude (correctly) that the
   node possessing the null ptr does not possess a son of
   adequate size, without needing to distinguish between
   the case of a small son and the case of a missing one.

                       *    *    *

   My thanks to Tom Ray, for creating Tierra; to Tom and
   his colleague Dan Pirone for encouraging this little
   project (and for answering numerous questions); and
   to the Santa Fe Institute and IBM for providing the
   facilities and the time for the work.

   CJS, Santa Fe, July 1992.                         */




/* Declare private internal functions */

static void delete  P_((I32s Hp pa, Pmf victim));
static void demote  P_((I32s Hp pa, Pmf victim));
static void promote P_((I32s Hp pa, Pmf riser));
static I32s memnode P_((void));


/*  _________________________________________________
   |                                                 | 
   |  Function MemInit -- Initialize soup allocator  |
   |_________________________________________________|

   Call is:  MemInit ()

   On entry: FreeMem  = addr of initial memory node array 
             MaxFreeBlocks = the size of this array (>=2)
             SoupSize = size of soup in instr slots (>0)

   Effect is to initialize memory node 0 (anchor) and 1
   (initial root), thus:

               _________________________ 
              |            |            |
   FreeMem[0] | l=-(MFB-2) |     r=1    | Anchor for tree
              |____________|____________|
              |            |            |
              |    p=0     |     s=0    |
              |____________|____________|
              |            |            |
   FreeMem[1] |    l=0     |     r=0    | The initial root
              |____________|____________|
              |            |            |
              |    p=0     | s=SoupSize |
              |____________|____________|
              |            |            |
              :            :            :
 
   where `MFB' is short for MaxFreeBlocks (array size).

   Notes:

   1.   This version of MemInit is for the new 
        soup allocator (CJS, Santa Fe, July 1992).

   2.   This routine does not bother to initialize
        fields that require an initial value of zero,
        since the memory for the node array is obtain-
        ed with calloc(), which clears the whole thing.