Heap Module Specification

Heap Module Specification
SchemeStation documentation

1 Introduction

SCHEMESTATION heap module implements the structured memory system used by the virtual machine. The heap is implemented as list-organised, typed, garbage-collected system to support the ease-of-use targets of the Schemestation project. Heap can be linearised and linearisations can be returned to native heap form. This eases message-passing implementation at other modules.

2 The Heap Structure

The heap is typed; type of each object can be found out at run time. Instances of each object type can be created, manipulated and read using legal operations of their type domain.

The heap is garbage-collected; data unreachable from the root set (and, thus unreachable from any client reference) is automatically removed from time to time. The heap size is dynamic; only actual system memory exhaustion can cause failed memory allocation.

2.1 Types

2.1.1 Integer

This type implements 64-bit signed integer numbers. Integer items can be created and read.

2.1.2 Float

This type implements 64-bit double-precision IEEE floating point numbers. Float items can be created and read.

2.1.3 Boolean

This type implements boolean truth value. Possible values are 0 (false) and 1 (true). All non-zero values are treated as true values at creation. Boolean items can be created and read.

2.1.4 Pair

Pair implements a pair of items. First item of pair is referred as "car", and the second as "cdr". Pairs can be created, and their car and cdr values can be read, set (to any heap object) and copied.

2.1.5 Vector

Vector implements a list of items with constant item operation complexity. Vectors contain one or more heap items. Vectors can be created, and their (numerically indexed) items can be set, read and copied similar way to pair. The length of vector is fixed at creation time, and it can be read after creation.

2.1.6 Shared Bit String

Shared bit string implements string of bits. The string is shared; all modifications of the string will be seen through other references to the object in the heap. Shared bit strings can be created, set, read and copied. Partial modification and substring expansion of strings is also possible. The length of shared bit string is fixed at creation time, and it can be read after creation.

2.1.7 Private Bit String

Private bit string implements string of bits. The string is private; all modifications of the string will affect only the referenced copy. Private bit strings can be created, set, read and copied. Partial modification and substring expansion of strings is also possible. The length of shared bit string is fixed at creation time, and it can be read after creation.

2.1.8 Procedure

Procedure implements procedure definition containing bytecode address and procedure environment. Procedures can be read and their pair elements can be read.

2.1.9 Null

Null implements "empty set" object. Object value can be set to null, and objects can be identified to be null (reading type field).

2.2 Tags

Pairs, vectors and bit stirngs can be "tagged" at creation time. The "tag" is 64-bit integer similar to integer type. Tags can't be modified after creation, but they can be read.

2.3 Garbage collection

Current GC implementation is non-generational stop-and-copy. Garbage collection is transparent process; only thing heap client must care of is the root set.

The root set the set that must contain all heap objects used by client to make garbage collection work properly. Root items are organised as "root frames", set of root items at run time. Root frames can be created and finalised; root items can be pushed to the root set between frame creation and finalisation.

2.4 Linearisation

Partial and whole linearisations of heap can be made and expanded back to structured form. Partial linearisations include all data reachable from the linearisation root item. Whole linearisations include also the root set state, constant item table and bytecode as bit string. Constant table vector can be manipulated using special operations and its inclusion to the linearisation can be controlled using macros defined at heap_types.h. Writing directly to active constant table is an illegal operation. The linearisations are platform-independent like all other operations of the heap; linearisations can be used as generic message payload at the SCHEMESTATION system. Transparent modifications of host-specific data (agent addresses) are performed in co-operation by the heap and addressing subsystems.

2.5 Initial Values

Due to heap implementation details, all values must be initialised to heap object default value before use. Lists and vectors have all their entries set up to default value at creation time. Bit string values are undefined at the creation time. The default value is HEAP_DEFVAL.

2.6 Illegal Operations

Operations performed with invalid parameter types fail. Out-of-bounds accesses cause failure.

3 Heap implementation

The stuctures required to use the heap implementation are on heap.h and heap_types.h, HeapTypedData, the basic type for heap operations is defined: 

typedef struct 
{
  HeapData data;  
  HeapType type;  
} HeapTypedData;

When used, it MUST be initialized with HEAP_DEFVAL. Reading of both the type and data field directly is acceptable (actually this is the way to check the type), but no reads must be performed to these fields outside heap library.

The supported (and obviously named) types are:

The heap API implementation is described below.

4.4.9 The functions of module Heap

File heap.h

C-functions:

File heap_internal.h

C-functions:

File heap_types.h

C-functions:

File heapconv.h

C-functions: