Heap Module Specification

Heap Module Specification

Document formatted by vherva at Fri Apr 24 11:23:42 1998 on the host schemestation. This document is produced by the SchemeStation project during the Tik-76.115 course.

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:

  • HEAP_TYPE_NULL,

  • HEAP_TYPE_BOOLEAN,

  • HEAP_TYPE_INTEGER,

  • HEAP_TYPE_FLOAT,

  • HEAP_TYPE_VECTOR,

  • HEAP_TYPE_VECTOR_TAGGED,

  • HEAP_TYPE_PAIR,

  • HEAP_TYPE_PAIR_TAGGED,

  • HEAP_TYPE_SHARED_BSTRING,

  • HEAP_TYPE_SHARED_BSTRING_TAGGED,

  • HEAP_TYPE_PRIVATE_BSTRING,

  • HEAP_TYPE_PRIVATE_BSTRING_TAGGED,

  • HEAP_TYPE_PROCEDURE

  • Tests for type domains are defined in heap_types.h:

  • IS_OF_VECTOR(type)

  • IS_OF_PAIR(type)

  • IS_OF_BIT_STRING(type)

The heap API implementation is described below.

4 The functions of module Heap
File heap.h

C-functions:

  • Status heap_copy_bit_string(INOUT Heap heap, OUT HeapTypedData *item, IN HeapTypedData *source)
    Description: Make copy of bit string source to dest.

  • Status heap_copy_pair(INOUT Heap heap, OUT HeapTypedData *dest, IN HeapTypedData *source)
    Description: Make copy of pair source to dest,

  • Status heap_copy_vector(INOUT Heap heap, OUT HeapTypedData *item, IN HeapTypedData *source)
    Description: Make copy of vector source to dest.

  • Status heap_delinearize(INOUT Heap heap, IN HeapTypedData *dest, IN LinearizedHeap source)
    Description: Produce subheap dest from linearization source. Similar to heap_linearize, but opposite operation. Related macros: HEAP_GC_ACTIVATE(h) HEAP_GC_DEACTIVATE(h) HEAP_DYNAMIC_ACTIVATE(h) HEAP_DYNAMIC_DEACTIVATE(h) HEAP_MSG_OPT_ACTIVATE(h) HEAP_MSG_OPT_DEACTIVATE(h) HEAP_MSG_CONST_EXPAND(h) HEAP_MSG_CONST_REFUSE(h)

  • Status heap_delinearize_assembled(INOUT Heap heap, IN LinearizedHeap linheap, OUT uchar **bytecode, OUT HeapInteger *blen)
    Description: XXX THIS SHOULD BE REMOVED - waiting for ssvm cleanup.

  • Status heap_free(IN Heap heap)
    Description: Free heap and all related resources.

  • Status heap_gc(INOUT Heap heap)
    Description: Coit heap garbage collection. Related macros: HEAP_GC_ACTIVATE(h) HEAP_GC_DEACTIVATE(h) HEAP_DYNAMIC_ACTIVATE(h) HEAP_DYNAMIC_DEACTIVATE(h) HEAP_MSG_OPT_ACTIVATE(h) HEAP_MSG_OPT_DEACTIVATE(h)

  • Status heap_get_bit_string(IN Heap heap, OUT uchar **item, IN HeapTypedData *source)
    Description: Get contents of bit string source to item.

  • Status heap_get_bit_string_len(IN Heap heap, OUT HeapInteger *num, IN HeapTypedData *source)
    Description: Get length of bit string source to item.

  • Status heap_get_bit_string_substring(INOUT Heap heap, OUT HeapTypedData *dst, IN HeapTypedData *source, IN HeapIndex pos, IN HeapSize len)
    Description: Get substring of bit string source starting from index with length size (both bits) to dst.

  • Status heap_get_boolean(IN Heap heap, OUT HeapBoolean *num, IN HeapTypedData *source)
    Description: Get numeric value of boolean number source to num.

  • Status heap_get_bytecode(IN Heap heap, OUT HeapInteger *num, IN HeapTypedData *source)
    Description: Get bytecode address value.

  • Status heap_get_constant_item(IN Heap heap, OUT HeapTypedData *dest, IN HeapInteger index)
    Description: Get constant from constant table.

  • Status heap_get_constants_table(IN Heap heap, OUT HeapTypedData *dest)
    Description: Get constant table pointer (to modify this, take a copy, modify, reset using heap_set_constants_table).

  • Status heap_get_float(IN Heap heap, OUT HeapFloat *num, IN HeapTypedData *source)
    Description: Get numeric value of floating point number source to num.

  • Status heap_get_integer(IN Heap heap, OUT HeapInteger *num, IN HeapTypedData *source)
    Description: Get numeric value of integer source to num.

  • Status heap_get_pair_car(IN Heap heap, OUT HeapTypedData *item, IN HeapTypedData *source)
    Description: Get contents of car of pair source to item.

  • Status heap_get_pair_cdr(IN Heap heap, OUT HeapTypedData *item, IN HeapTypedData *source)
    Description: Get contents of cdr of pair source to item.

  • Status heap_get_procedure_bytecode(IN Heap heap, OUT HeapTypedData *dest, IN HeapTypedData *src)
    Description: Get procedure bytecode address.

  • Status heap_get_procedure_env(IN Heap heap, OUT HeapTypedData *dest, IN HeapTypedData *src)
    Description: Get procedure environment.

  • Status heap_get_tag(IN Heap heap, OUT HeapTag *tag, IN HeapTypedData *source)
    Description: Get item tag. (Fail if not tagged)

  • Status heap_get_vector_item(IN Heap heap, OUT HeapTypedData *item, IN HeapTypedData *source, IN HeapIndex index)
    Description: Get contents of item index of vector source to item.

  • Status heap_get_vector_len(IN Heap heap, OUT HeapSize *size, IN HeapTypedData *source)
    Description: Get length of vector source to size.

  • Status heap_info(IN Heap heap, OUT HeapInfo *info)
    Description: Provide information of heap using info structure (unimplemented).

  • Status heap_init(OUT Heap *heap, IN HeapSize size)
    Description: Set up heap heap with start size size. Start size must be 2 or greater. This function creates garbage-collected, dynamic heap at *heap. The properties of the heap can be controlled with following macros: HEAP_GC_ACTIVATE(h) HEAP_GC_DEACTIVATE(h) HEAP_DYNAMIC_ACTIVATE(h) HEAP_DYNAMIC_DEACTIVATE(h) HEAP_MSG_OPT_ACTIVATE(h) HEAP_MSG_OPT_DEACTIVATE(h) HEAP_MSG_CONST_INCLUDE(h) HEAP_MSG_CONST_EXCLUDE(h) HEAP_MSG_CONST_EXPAND(h) HEAP_MSG_CONST_REFUSE(h)

  • Status heap_lin_get_bstr(OUT LinearizedHeap linheap, OUT uchar **content, OUT HeapInteger *length, OUT HeapTag *tag, IN HeapInteger index)
    Description: Get pointer to bit string number index start at the linearisation, length and tag of the bit string. This is useful for modifying bit string values at linearisations.

  • Status heap_lin_get_bstr_count(OUT LinearizedHeap source, OUT HeapInteger *num)
    Description: Get number of bit string items in linearisation.

  • Status heap_linearize(IN Heap heap, OUT LinearizedHeap *linheap, OUT HeapInteger *len, IN HeapTypedData *source)
    Description: Produce heap linearization linheap from subheap source, setting the linearization length (in bytes) to len. Performs task with a modified GC operation. Related macros: HEAP_GC_ACTIVATE(h) HEAP_GC_DEACTIVATE(h) HEAP_DYNAMIC_ACTIVATE(h) HEAP_DYNAMIC_DEACTIVATE(h) HEAP_MSG_OPT_ACTIVATE(h) HEAP_MSG_OPT_DEACTIVATE(h) HEAP_MSG_CONST_INCLUDE(h) HEAP_MSG_CONST_EXCLUDE(h)

  • Status heap_make_boolean(INOUT Heap heap, IN HeapBoolean num, OUT HeapTypedData *ptr)
    Description: Set contents of ptr to boolean number with value num.

  • Status heap_make_bytecode(INOUT Heap heap, IN HeapInteger num, INOUT HeapTypedData *ptr)
    Description: Make bytecode address pointing to address num.

  • Status heap_make_float(INOUT Heap heap, IN HeapFloat num, OUT HeapTypedData *ptr)
    Description: Set contents of ptr to floating point number with value num.

  • Status heap_make_integer(INOUT Heap heap, IN HeapInteger num, OUT HeapTypedData *ptr)
    Description: Set contents of ptr to integer with value num.

  • heap_make_pair(heap, item)
    Description:

  • Status heap_make_pair_tagged(INOUT Heap heap, OUT HeapTypedData *ptr, IN HeapTag tag)
    Description: Set contents of ptr to pair (consisting of two nulls), tagged with tag.

  • heap_make_private_bit_string(heap, item, size)
    Description:

  • Status heap_make_private_bit_string_tagged(INOUT Heap heap, OUT HeapTypedData *item, IN HeapSize size, IN HeapTag tag)
    Description: Set contents of ptr to private bit string item of lenght size (all bits zero), tagged with tag.

  • Status heap_make_procedure(INOUT Heap heap, OUT HeapTypedData *item, IN HeapTypedData *bytecode, IN HeapTypedData *env)
    Description: Make procedure from bytecode address and associated environment.

  • heap_make_shared_bit_string(heap, item, size)
    Description:

  • Status heap_make_shared_bit_string_tagged(INOUT Heap heap, OUT HeapTypedData *item, IN HeapSize size, IN HeapTag tag)
    Description: Set contents of ptr to shared bit string item of lenght size (all bits zero), tagged with tag.

  • Status heap_make_tag(INOUT Heap heap, IN HeapTag tag, OUT HeapTypedData *ptr)
    Description: Set contents of ptr to tag with value TAG

  • Status heap_make_vector(INOUT Heap heap, OUT HeapTypedData *ptr, HeapInteger length)
    Description: Set contents of ptr to length -length vector (consisting of nulls).

  • Status heap_make_vector_tagged(INOUT Heap heap, OUT HeapTypedData *ptr, IN HeapInteger length, IN HeapTag tag)
    Description: Set contents of ptr to lenght -lenght vector (consisting of nulls), tagged with tag.

  • Status heap_pop_gc_roots(IN Heap heap)
    Description: Pop all items in current root frame and return to previous root frame.

  • Status heap_push_gc_root(IN Heap heap, IN HeapTypedData *reg)
    Description: Push reg to heap GC root set.

  • heap_set_bit_string(heap, item, string)
    Description:

  • Status heap_set_bit_string_substring(INOUT Heap heap, INOUT HeapTypedData *dest, IN HeapTypedData *src, IN HeapIndex pos)
    Description: Set substring of bit string dest starting from pos (len bits) to source.

  • Status heap_set_constant_vector(IN Heap heap, IN HeapTypedData *source)
    Description: Set constant table (for testing only). this is obsolete, use heap_set_constants_table instead

  • Status heap_set_constants_table(IN Heap heap, IN HeapTypedData *src)
    Description: Set constant table vector.

  • Status heap_set_item(INOUT Heap heap, INOUT HeapTypedData *dest, OUT HeapTypedData *src)
    Description: Set dest to src value. *Must* be used on such moves.

  • heap_set_pair_car(heap, item, car)
    Description:

  • heap_set_pair_cdr(heap, item, cdr)
    Description:

  • Status heap_set_vector_item(INOUT Heap heap, INOUT HeapTypedData *dest, IN HeapTypedData *source, IN HeapIndex index)
    Description: Set item index of vector dest to source.

  • Status heap_start_root_frame(IN Heap heap)
    Description: Begin a root frame. Look at above example.

  • ss_int64_ntoh(*(int64 *)(heap))
    Description:

File heap_internal.h

C-functions:

File heap_types.h

C-functions:

File heapconv.h

C-functions:

  • Status get_list_from_lheap(IN LinearizedHeap lheap, IN char *format, OUT ...)
    Description: These functions are used to extract data from linearized heaps that represent lists and to build such linearized heaps from C values. FORMAT is a string denoting the types of values that should be found from a list / put to a list. get_list_from_heap returns STATUS_FAILED if the types in the linearized heap do not match the types specified in FORMAT. make_lheap_from_list return STATUS_FAILED if the heap cannot be built for some reason. Format specifiers corresponding type d = integer int * (get_list), int (make_lheap) a = ActorSpecifier, uchar * (both) s = null-terminated string char ** (get_list), char * (make_lheap) b = bit string char ** , int ** (get_list), char *, int (make_lheap) [for bit strings, the second integer argument is the length of the bit string in bytes, i.e. the number of bits divided by eight] ActorSpecifiers are written to memory starting from the given pointer, which must denote at least 256 bits of free space. Because the length of a null-terminated string cannot be known, it is dynamically allocated. The pointer to a dynamically allocated NULL-terminated string will be written to the supplied char ** pointer.

  • Status hconv_heap_end_incr(OUT LinearizedHeap *lheap)
    Description:

  • Status hconv_heap_end_walk(void)
    Description:

  • Status hconv_heap_make_incr(char format, ...)
    Description:

  • Status hconv_heap_start_incr(void)
    Description: These are counterparts of walks.

  • Status hconv_heap_start_walk(IN LinearizedHeap lheap)
    Description: These are as get_list_from_lheap but can be used to traverse the list found from the heap one item at a time. If the types of the later element in a list depend on the previous ones using these is more effective than calling get_list_from_lheap multiple times, because every call to get_list_from_lheap performs the delinearization [again]. Notice that FORMAT is _one_ character, not a string, and gets only one parameter with types as for get_list_from_lheap.

  • Status hconv_heap_walk(char format, ...)
    Description:

  • Status make_lheap_from_list(OUT LinearizedHeap *lheap, IN char *format, IN ...)
    Description:

  • Status make_lheap_from_list_va(OUT LinearizedHeap *lheap, char *format, IN va_list args)
    Description:

© SchemeStation project 1997-1998 [Back to the document index]