home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD2.bin / bbs / dev / oberon-a-1.4ß.lha / Oberon-A / texts / Memory.txt < prev    next >
Text File  |  1994-05-28  |  13KB  |  274 lines
  1.      $RCSfile: Memory.txt $
  2.   Description: Description of the Oberon-A memory management system
  3.  
  4.    Created by: fjc (Frank Copeland)
  5.     $Revision: 1.2 $
  6.       $Author: fjc $
  7.         $Date: 1994/05/13 19:28:33 $
  8.  
  9.   Copyright © 1994, Frank Copeland.
  10.   This file is part of Oberon-A.
  11.   See Oberon-A.doc for conditions of use and distribution.
  12.   ________________________________________________________________________
  13.  
  14.  
  15.   Introduction
  16.   ------------
  17.  
  18.   This document describes the design and implementation of Oberon-A's
  19.   memory management.  This covers the allocator (NEW and SYSTEM.NEW),
  20.   deallocator (SYSTEM.DISPOSE) and garbage collector (SYSTEM.GC).  The
  21.   design used for Oberon-A is based closely on the designs discussed in
  22.   the Oberon Technical Notes 2 and 5, (see TechNotes.doc).
  23.  
  24.   Memory blocks
  25.   -------------
  26.  
  27.   Memory allocation in Oberon must take into account a number of factors
  28.   that require more than just requesting a block of memory from the
  29.   operating system.  Oberon's run-time type checking requires that every
  30.   record variable that is dynamically allocated have an hidden type tag
  31.   preceding it.  The garbage collector must be able to distinguish between
  32.   memory allocated for records, arrays and untyped blocks (created by
  33.   SYSTEM.NEW).  CPointers and BPointers must be treated differently to
  34.   normal Oberon pointers.
  35.  
  36.   Three types of memory block are recognised:
  37.  
  38.     RecordBlk : memory allocated to a POINTER TO <record type> variable.
  39.     ArrayBlk  : memory allocated to a POINTER TO <array type> variable.
  40.     SysBlk    : memory allocated to a CPointer or BPointer variable, or
  41.                 allocated with SYSTEM.NEW.
  42.  
  43.   A RecordBlk looks like this, where v is a variable of type POINTER TO T,
  44.   T is a record type:
  45.  
  46.       RecordBlk = RECORD
  47.         link : ADDRESS; (* next element in list of blocks *)
  48.         tag  : ADDRESS; (* type descriptor of type T *)
  49.   v --> data : ARRAY SIZE(T) OF BYTE
  50.       END
  51.  
  52.   An ArrayBlk looks like this, where v is a variable of type POINTER TO
  53.   ARRAY n1, n2 ... ni-1 OF T:
  54.  
  55.       ArrayBlk = RECORD
  56.         arrpos   : LONGINT; (* used by the garbage collector *)
  57.         elemSize : LONGINT; (* SIZE (T), for the convenience of the
  58.                                garbage collector *)
  59.         size     : LONGINT; (* n1 * n2 ... * ni-1 * SIZE(T) *)
  60.         link     : ADDRESS; (* next element in list of blocks *)
  61.         tag      : ADDRESS; (* type descriptor of type T *)
  62.   v --> data     : ARRAY size OF BYTE
  63.       END
  64.  
  65.   A SysBlk looks like this, where v is any pointer variable:
  66.  
  67.       SysBlk = RECORD
  68.         link : ADDRESS; (* next element in list of blocks *)
  69.         size : LONGINT; (* size of block *)
  70.   v --> data : ARRAY size OF BYTE
  71.       END
  72.  
  73.   The type of the block is determined by bits encoded in the tag or size
  74.   field at address: v - 4.  Bits 0 and 1 are used for this encoding: they
  75.   are available to be used because the type descriptors are guaranteed to
  76.   be longword-aligned and the allocator ensures that block sizes are
  77.   multiples of 4 bytes.  Bit 0 is set to indicate that the block is a
  78.   SysBlk.  Bit 1 is set to indicate that the block is an ArrayBlk.  If bit
  79.   1 is clear, the block is a RecordBlk.  This encoding ensures that the
  80.   type tag of a RecordBlk is a valid pointer to a type descriptor, which
  81.   is necessary for fast run-time type checks and guards.  For the other
  82.   block types, the encoded bits must be masked out before the tag or size
  83.   field can be used.
  84.  
  85.   The link field (at address: v - 8) in each type of block is used to
  86.   implement a singly-linked list of allocated blocks.  It is either NIL,
  87.   or points to the link field in the next block in the list.  Blocks are
  88.   added to the list by the allocator and removed by the deallocator and
  89.   garbage collector.  All allocated blocks are freed when the program
  90.   terminates.  Two seperate lists are maintained: one of traced blocks
  91.   known to the garbage collector and one of untraced blocks.
  92.  
  93.   The size, elemSize and arrpos fields in an ArrayBlk block are required
  94.   by the garbage collector (see Garbage collection).
  95.  
  96.   Allocating memory
  97.   -----------------
  98.  
  99.   The allocator is implemented in two procedures in the run-time support
  100.   library: OberonSys_NEW and OberonSys_SYSNEW.  OberonSys_NEW is used to
  101.   allocate RecordBlk and ArrayBlk blocks and OberonSys_SYSNEW is used to
  102.   allocate SysBlk blocks.  The standard procedure SYSTEM.NEW always
  103.   translates into a call to OberonSys_SYSNEW while the standard procedure
  104.   NEW can translate into a call to either, depending on the type of
  105.   variable.
  106.  
  107.   Oberon_NEW requires two parameters:
  108.  
  109.     size (passed D0): this is only required for an ArrayBlk and is the
  110.       size of the block to be allocated.
  111.  
  112.     tag (passed in D1): a pointer to a type descriptor. Bit 1 is set if an
  113.       ArrayBlk is required.
  114.  
  115.   For a RecordBlk block, OberonSys_NEW calculates the size of the block by
  116.   adding 8 to the size of the record found in the type descriptor.  For an
  117.   ArrayBlk block, it adds 20 to the size parameter.  The result is rounded
  118.   up to the next multiple of 4 bytes.  It then asks Exec for a block of
  119.   memory of the required size, using AllocMem (size, {memClear}) so that
  120.   the block is zeroed.  If successful, it initialises the block's hidden
  121.   fields, links it into the relevant list and returns the address of the
  122.   data field in D0.  By default, the allocated block is placed in the
  123.   list of blocks known to the garbage collector.  If the allocation fails,
  124.   NIL is returned in D0.
  125.  
  126.   OberonSys_SYSNEW requires two parameters:
  127.  
  128.     size (passed in D0): the number of bytes to be allocated.
  129.     traced (passed in D1.B): a flag indicating if the variable is traced.
  130.  
  131.   OberonSys_SYSNEW adds 8 to the size parameter and rounds the result up
  132.   to the next multiple of 4 bytes.  It then asks Exec for a block of
  133.   memory of the required size, using AllocMem (size, {memClear}) so that
  134.   the block is zeroed.  If successful, it initialises the block's hidden
  135.   fields, links it into the relevant list and returns the address of the
  136.   data field in D0.  If traced is TRUE, the allocated block is placed in
  137.   the list of blocks known to the garbage collector, otherwise it is
  138.   placed in an alternate list and will not be garbage collected.  If the
  139.   allocation fails, NIL is returned in D0.
  140.  
  141.   Type tags and descriptors
  142.   -------------------------
  143.  
  144.   RecordBlk and ArrayBlk blocks both contain a type tag, which is a
  145.   pointer to a type descriptor.  A type descriptor is always associated
  146.   with a record type.  Information in the type descriptor is used by the
  147.   allocator and the garbage collector.  The structure of a type descriptor
  148.   is:
  149.  
  150.     TypeTag = POINTER TO TypeDesc;
  151.     TypeDesc = RECORD
  152.       size    : LONGINT;
  153.       ttable  : ARRAY 8 OF TypeTag;
  154.       offsets : ARRAY N+1 OF LONGINT
  155.     END
  156.  
  157.   size holds the size in bytes of an object of that type.  This is used
  158.   by the allocator to determine the size of a RecordBlk.  ttable holds a
  159.   table of pointers to the descriptors of the base types of the
  160.   descriptor's type. This is used in type tests and guards.  The size is
  161.   fixed so that the garbage collector can always locate the offsets field
  162.   at a fixed offset from the base of the type descriptor.  This limits the
  163.   depth to which types can be extended.  The depth chosen (8) is the same
  164.   as that used in the Oberon System and should be adequate for most
  165.   purposes. The offsets field is an array holding the offsets of the
  166.   pointer fields in the type; N is the number of such fields.  This is
  167.   used in the garbage collector's mark phase (see Garbage collection).
  168.  
  169.   Deallocating memory
  170.   -------------------
  171.  
  172.   Memory is explicitly deallocated with the standard procedure
  173.   SYSTEM.DISPOSE.  This is implemented in the run-time support procedure
  174.   OberonSys_DISPOSE.
  175.  
  176.   OberonSys_DISPOSE has one parameter:
  177.  
  178.     block (passed in D0): the address of the block to be freed.
  179.  
  180.   OberonSys_DISPOSE scans the lists of allocated blocks looking for block;
  181.   the untraced list is scanned first.  If it does not find block, it halts
  182.   the program.  Otherwise, block is removed from the list and the memory
  183.   is returned to the operating sys