Small Nerves Logo
Full Amoeba Spec, August 1995

Nerve Band
Overall Goals of the Design

Locality

The design is built to try to localize operations as much as possible. Thus, most information needed to make a decision is contained in the stream, and will not require indirection to another datastructure. This property is included to satisfy the overall requirement for high performance (number of messages moved in a given time frame).

Compactness

The design is meant to take a minimum of memory on its own and require a minimum of associated memory during execution.

Addressability

Components of the design are intended to be easily and universally addressed. For example, to address a certain pool: design_name.instance_id.design_sub_element_name.pool_name would allow the direct addressing of the contents of pool pool_name within a given instance instance_id of the design design_name It is for this reason that all textual names from the source compilation will be saved in the binary executable image.

This facility will allow network based addressing of the smallest components of an executing or non-executing design. Thus, a message could be transmitted to be inserted in a specific pool of a specific instance (or all instances) or a message of a specific named type having specific contents (or all messages of a specific type) could be retrieved from a given pool (or all pools). A remote retrieval or purge of all messages from all pools of all object instances could be executed under this model. In addtion, sections of the actual design encoding could be added, removed or updated remotely.

Nerve Band
Efficiency Features and Numerical Limits

Syntax and Structure for Spaces produced by compilation and execution. The following records make up a single executable binary file which can be loaded, saved and paged rapidly and directly executed as an instruction set.

  • WorldSpace
  • DesignSpace
  • InstanceSpace
  • WorkSpace

  • Source and Binary Formats
  • Rapid Storage and Loading
  • Single File for design and instances
  • Executability of Image

Number of pools allowed: 65536
Number of links out of a given pool allowed: up to 65536 if no filters are
defined and a reduced number of links for filters. No practical limit.
Number of filters allowed on a given link: 255
Number of message types permitted: 65536

Nerve Band
Engine Internals High Level Overview

All Structures are Represented as a Chain of Records

[Escapement][Record][Escapement][Record]..

b) Major Blocks of Records

WorldSpace

[World Encoding]

DesignSpace:

[Design Encoding][Pool Registry][Message Registry][Function Registry]

InstanceSpace:

[Instance Registry][Instance Message Streams][Instance Message Content Stores]

I. WorldSpace

A Worldspace is a collection of zero or more designs and their instances. A worldspace could have no instances, or no designs and instances (it would be an empty world)

A. The World Encoding

[Escapement][Name][Long Description][Author]
[Version/Revision][Creation Date][Update Log]
[Security Access][Privileges][Operational Libraries Registry]
[Number of DesignSpaces][Offsets to DesignSpaces][Lengths of DesignSpaces]
[Number of InstanceSpaces][Offsets to InstanceSpaces][Lengths of InstanceSpaces]

B. General Structures in WorldSpace

Escapement

This is a symbol in the WorldSPpace stream which indicates the type of Structure to follow. The Escapement has the following structure:

[Escapement Code][Structure ID]

Escapement Code: 1 byte
This code is a single byte, containing hex 'FF' which indicate a new record structure to follow.

Structure ID: 2 bytes
The Structure ID uniquely identifies a structure type to follow.

Note that the recording of the length of the structures to follow the escapement will be handled differently for each structure, as lengths vary from understood fixed values to widely variable values.

It is hoped that the use of an Escapement will aid in both implementation and debugging of Worlds and assist in possible future hardware implementations.

Registry of Structure IDs:

0: Reserved

For the WorldSpace

1: World Encoding Record
2-99: Reserved for additional structures or new versions of structures

For the DesignSpace

100: Design Record
101-199: Reserved for additional Design Record structures or new versions of structures
200: InLink Record
201-299: Reserved for additional InLink Record structures or new versions of structures
300: OutLink Record
301-399: Reserved for additional OutLink Record structures or new versions of structures
400: Pool Record with Links
401-499: Reserved for additional Pool Record structures or new versions of structures
500: Pool Registry
501-599: Reserved for additional Pool Registry structures or new versions of structures
600: Message Registry
601-699: Reserved for additional Message Registry structures or new versions of structures
700: Function Registry
701-799: Reserved for additional Function Registry structures or new versions of structures
800-999: Reserved for additional DesignSpace structures

For the InstanceSpace

1000: Instance Registry
1001-1099: Reserved for additional Instance Registry structures or new versions of structures
1100: Instance Message Streams
1101-1199: Reserved for additional Instance Message Stream structures or new versions of structures
1200: Instance Message Content Stores
1201-1299: Reserved for additional Instance Message Content Store structures or new versions of structures For the WorkSpace

2000: WorkSpace Record
2100: Working Area Records
2200: Log Records

II. DesignSpace

A. The Design Encoding

The sequencing of records in the Design Encoding
[Design Record][InLink Record][OutLink Record][Pool Records with Links]

1. The Design Record

[Escapement][Structure Length][Name][Long Description][Author]
[Version/Revision][Creation Date][Update Log]
[Security Access][Privileges][Operational Libraries Registry]
[Offset to Start of Design][[Length of Design]
[Offset to Pool Registry][Length of Pool Registry]
[Offset to Message Registry][Length of Message Registry]
[Offset to Function Registry][Length of Function Registry]

2. The Entry Ports: the InLink Record

Format:
[Escapement][Structure Length]([InLink]([Link Filter]..)..[Pool Index])

3. The Exit Ports: the OutLink Record

Format:
[Escapement][Structure Length]([OutLink]([Link Filter]..)..[Pool Index])

4. The Pool Record with Links

Format:
[Escapement][Pool Index][Structure Length]([Link]([Link Filter]..)..
[Link Destination Type][Link Destination Index])

[Pool Index]: 2 bytes
This is the numbered index uniquely identifying the pool. This is also an index directly into the table built at compile time which contains the textual name of the pool. This name table is stored after compilation of the encoding for use in tracking message flow and debugging.
Values:
Address 0 to 65535

[Structure Length]: 2 bytes
This value denotes the length of the data portion of the structure, which in the case of a pool definition, includes the Linkout records and Destination records. If this value is zero, then the pool has no links out and is an end node. Note that all pools can be 'drained' so that there never is truly a pool with no exit. There is no counter here to denote the number of linkout records, requiring a parsing of the data and extraction of the linkout records.

[Link]: 1 byte
This is a record denoting a link path from a pool. Links may have filters applying to messages attempting to exit the pool through this path. There can be an arbitrary number of filters. The value of Link denotes the number of filters which will follow. If the value of Linkout is zero, then the link is a simple exit from the pool which will carry all messages. There is a limit of 255 Linkout Filters which can be applied to any Linkout path.
Values:
0: no filters, just a simple link path to carry all messages
1-255: the number of Linkout Filters to follow.

[Link Filter]:3 bytes
This record defines a Link's Filter. This is a test applied against messages attempting to take this path out of a pool. The components of this record are:
[Filter Test]: 1 byte
[Message ID]: 2 bytes

The Filter Test determines what type of test to apply against the messages. The types of tests are as follows:
Filter Test: 0 apply a positive filter, eg: pass the message along this path if it is the same type of message as specified by Message ID.

Filter Test: 1 apply a negative filter, eg: pass all messages along this path if they are not the same type of message as specified by Message ID. The remaining bits in the Filter Test are unused and reserved for future purposes. The value of the message ID is identical to numerical values of the message identifiers assigned to messages flowing through the encoding. Some of these messages will be operating system messages and some will be locally defined messages (unique from the operating system messages)

The Message ID is also used for lookup of the textual name of the message. These names are stored in the table built at compile time. The message name table is kept for use in tracking, addressing and debugging.

B. Pool Registry

Format:
[Escapement][Structure Length][Number of Records in Registry]
Format of each record in Registry:
[Pool Name][Long Description]

C. Message Registry

Format:
[Escapement][Structure Length][Number of Records in Registry]

Format of each record in Registry:
[Message ID][Local Design Name][Operating System Name][Long Description]

D. Function Registry

Format:
[Escapement][Structure Length][Number of Records in Registry]

Format:
[Local Design Name][Function or Operating System Linkage][Long Description]

III. InstanceSpace

A. Instance Registry

Format:
[Escapement][Structure Length][Number of Records in Registry]

Format of each record in Registry:
[Instance ID][Pointer to Start of Instance Message Stream]
[Pointer to start of Instance Message Store]

B. Instance Message Streams

Format:
[Escapement][Structure Length][Number of Messages in Stream]

Format of each record in Stream:
[Offset to Pool in Design Encoding]
[Number of Messages]([Message Index][Offset into Message Store]..)

C. Instance Message Content Stores

Format:
[Escapement][Structure Length][Number of Messages Storage Areas][Storage Areas]

Format of each storage area:
The format of each message storage area is not determined by this design but varies for each message. This maintains the independence of the design from operating system or application message formats. This will allow these messages to be 'passed through'.

IV. WorkSpace

The Workspace provides temporary work areas and non-design, non-instance related information capture, including logs. Also, docking areas for external messages or design fragments could be housed here.

Format of WorkSpace Record:
[Escapement][WorkSpace Record]
[Pointer to start of Working Area Records][Length of Working Area]
[Pointer to start of Log Records][Length of Log Records]

A. Working Area Records

Working areas could include such things as stores for 'dead' messages in instances.

Format:
[Escapement][Structure Length][Working Data].. to be defined.

Format of each record in Registry:
[Instance ID][Pointer to Start of Instance Message Stream]
[Pointer to start of Instance Message Store]

B. Log Records

Items to be logged from the execution of the instances against designs may include events or errors or presumed errors.

Format:
[Escapement][Structure Length][Number of Log Records]

Format of each record in Log:
[Type of Log Record][Log Record Contents]

Nerve Band
Operation of the Design

Initially, from a text source

  1. A World is constructed
  2. One or more designs is assigned to the world
  3. One or more Instances with initial message streams are assigned to the designs
  4. The WorldSpace is compiled, including DesignSpaces, InstanceSpaces and WorkSpaces

Execution

  1. The Instancespace is processed once through
    • Each Instance Message Stream is processed through
      • For Each Instance Message Stream, the messages in each pool are processed. For each message in the Pool, messages pass through links which filter for them and all other messages pass through remaining open links (if any).
    • The Message Stream is rewritten as a new stream as the message stream is processed
    • A separate set of Function invokations is queued up, one queue for each available Functional Object
  2. Accumulated DisplayRender requests are processed
  3. Pending Function Operations are processed
  4. The InLinks are processed, passing new messages into the world
    • A new Instance Message Stream is constructed.
    • For each Pool referenced in the Inlink, a Pool Record
  5. Repeat from Step 1.

The device context is yielded

Nerve Band
Initial version of design
Developed: August 17-19, 1995

The following is an initial prototype design.
Features: does not compile the textual design encoding to binary but instead runs by on-the-fly parsing of this design given that links have been established.

The design consists of the following data structures and relationships:

0. Design Encoding stored entirely in memory in source format.

1. Message Registry

Structure:
[Internal name of Message][External Operating System Name of Message][Value of Message ID]

2. Function Registry

Structure:
[Internal Name of Function][Long name of Function][Type of Function][Link to Function]

3. Pool Registry

Structure, an array of records:
[Pool Name][Ptr to first record in Pool Occurence Registry][Ptr to design encoding]

3.1 Pool Occurence Registry

Structure, and array of records:
[Ptr to next record in Pool Occurence Registry][Ptr to design encoding]

where:
For every pool of the same name encountered in the encoding, a chain of records are recorded in the registry. This is done by recording the name of the pool from the first occurence in the Pool Registry and then creating an entry in the Pool Occurence Registry. All subsequent occurences of that pool in the design encoding are recorded as additional records in the Pool Occurence Registry. A pointer from the Pool Registry to the Pool Occurence Registry links the Registries together. Pointers from one record to the next in the Occurence Registry links these records within that registry.

In addition, each Pool Occurence Record points to the first byte beyond the end of its position in the design encoding. Thus, by tracing down the chain of pool occurence records and following the pointers to the design space, all links out of a given pool can be found and used.

4. InstanceSpace // Modified below in 4.a

InstanceSpace is made up of records and local caches of a constant length. Cache length is a World setting and must be between a value of 2 (to hold a minimum of two messages or two overflow cache pointers, one for each cache) and 255. Each message is 6 bytes long. Local cache default size can be modified by use of temporary and permanent overflow conditions. Default local cache size must be selected carefully to trade off performance with memory requirements. A Default local cache size of 2 would allow only one message to be currently in or added to any pool in the design encoding. Overflow conditions might occur frequently in this scenario or not at all depending on the requirements and expected message flow through the design.

The choice of the size of overflow caches is set by World defaults or could be dynamically determined. If a permanent overflow condition is in force (size of caches was increased and is to be kept larger) then a large enough buffer would have been selected. If messages exceed the overflow caches, these caches can be expanded and messages copied into them. Alternately, if the overflow caches are consistently underutilized, they can be reduced in size.

The use of a two level cache is designed to optimize both the performance of message flow through the design and the use of memory by the Instance Space of the design. The parts of the InstanceSpace records are described in detail below:
Structure, an array of records:
[Flags][Cache Boundary][Message Stream Cache for Pool]
where:
[Flags] are
Bit Indicators of the current state of the cache:
Bit 0: 0=use standard cache size
: 1=use modified cache size, stored in cache using permanent overflow conditions for either or both caches.
Bit 1: 0=current messages are in cache 1, new messages in cache 2
: 1=current messages are in cache 2, new messages in cache 1
Bit 2: 0=no overflow conditions on cache 1
: 1=overflow conditions on cache 1, length and pointer to overflow buffer in first six bytes of cache 1
Bit 3: 0=no overflow conditions on cache 2
: 1=overflow conditions on cache 2, length and pointer to overflow buffer in first six bytes of cache 2

[Cache Boundary] is a one byte value specifying the current boundary between cache 1 and cache 2. This is a floating boundary design to optimize use of the local cache during the pool draining and filling process. Cache 1 and 2 are alternately assigned to current or to new messages preventing the need to move most messages after the pool has been processed and all incoming messages posted here. Bit 1 of Flags determines this message assignment.

[Message Stream Cache for Pool] is
The section of cache (caches 1 and 2) reserved for messages currently in or just being newly added to the given pool. This cache space is by default a constant size and is allocated in units of 6 bytes. Messages stored here are in the format: [Message ID]: a two byte numerical index corresponding to the message ID [Ptr to Message Store]: a four byte pointer pointing to the message store which has any contents for the message (or zero if there are no contents)

Note: Variable sized message stream caches not to be implemented until later: The overall cache size is fixed unless Bit 0 of Flags is set in which case the cache size (larger or smaller) is stored in the first two bytes of the cache. This variable cache size allows local optimizations to occur as a given pool experiences fewer or more than the average number of messages. If the cache is to be larger and not smaller, then the overflow condition (described below) is to be in force permanently for both caches, and with the size of overflow areas to be determined from the individual cache overflow area lengths.

In the case that the number of current or new messages exceed the local cache capacity (caches 1 and 2 on either side of the cache boundary), then a cache overfolow condition exists. In this case, for either or both caches 1 and 2, the first six bytes of cache 1 and/or the last six bytes of cache 2 give the length and the address of separate overflow areas for each cache, accordingly. Messages which overflowed either cache are stored in these overflow areas. Cache overflow conditions are indicated by the settings of Flags 2 and 3.

4.a Modified Instancespace

A much simplified Instancespace consists only of a single data structure containing lengths of InstanceSpace Pool Caches. The only records in this structure would be fixed 7 byte length tokens, consisting of the following three record fields:
1 [token flags] a one bye flag bitfield as defined:
bit 0=0: the token area is unused
bit 0=1: the token defines an object
bit 1=0: the token denotes an actual simple message or message set:
bit 2=0: the message or message set is defined as being in local cache 0
bit 2=1: the message or message set is defined as being in local cache 1
bit 3=0: the message is entirely defined by this token
bit 4=0: the message params are packed into record field 3.
bit 4=1: record field 3 points to where the message contents are stored
bits 5-7: unused, set to zero.
bit 3=1: this token defines a pointer to another set of messages, the pointer is found in record field 3, the count of messages in that contiguous memory space is stored in record field 2
This is a set of messages entirely assigned to local cache 0 or 1, depending on the setting of bit 2 above.
bits 4-7: unused, set to zero.

bit 1=1: the token denotes another type of more sophisticated message object:
bit 2=0: the token defines a functional object capable of moving through the design and operating within pool caches. Unlike other functional objects, which are anchored on pool caches by links, this functional object will ingest messages directly from the pool based on the binary design encoding fragment link record pointed to by record field 3. This 'floating function' is given the mesage ID defined in record field 2 and may therefore be tested for and passed over links as other messages.
bit 2=1: the token defines a fragment of design encoding capable of moving through the design links and pools. As with the floating function, this 'floating fragment' is identified by a message ID stored in record field 2. The fragment may flow through a design just as any other type of message. A pointer stored in record field 3 points to a fragment of binary design encoding defining the floating fragment. A floating fragment may absorb messages along links defined by the encoding fragment pointed to. The first part of any fragment will be a set of links with filters. A floating fragment will place messages back into the pool from whence they came or will dispatch them to another pool in another InstanceSpace. Each floating fragment will also have an assigned InstanceSpace, as determined at the pointer location.
bits 3-7: unused, set to zero.
2 [message id or other functional record] a two byte integer the ID of the message, which could be the OS message ID or an internally defined ID.
3 [pointer to message store or other parameters] a four byte pointer or other value.

InstanceSpace Pool Caches are a constant length, optimized against memory availability and processing speed requirements. Effort should be made to match the typical cache load to minimize the number of indirections to message sets. Message sets can always be generated if the cache is full. Message sets can be chained together, given each cache an essentially unlimited capacity. There would only be a maximum of two message set objects in each cache, one for cache 0 and one for cache 1. Maintaining a fixed number of tokens in each cache in the InstanceSpace (excluding sets) allows easy correlation with the pools in the designspace encoding which the caches are tied to.

Processing of the 'current' messages and the creation of 'new' messages alternate in their use of cache 0 or cache 1. Which cache is in use for which type of messages depends on the settings of the InstanceSpace controls.

4.b InstanceSpace Controls

[instancespace cache size]
[current instancespace cache assignment]
[instancespace cache pool index]
[instancespace pointer]

5. InLink Registry

This set of records defines the entry point of messages into the "World" from outside (the operating environment).

Structure, array of records:
[Ptr to Pool Registry][Ptr to design encoding]

This registry is sorted such that the links having active filters are processed first and the links which are without filters are listed last and will be taken last. where
[Ptr to Pool Registry] is
A Pointer to the Pool Registry record (first one) for the destination pool which will be accepting the messages.
[Ptr to design encoding] is
A Pointer to the design encoding location containing the link into that pool, with its filters defined.

The links between the Pool Registry and InstanceSpace

The Pool Registry stores one pool per record (all occurences are stored in an overflow area, the Pool Occurence Registry). The InstanceSpace structure is a fixed length datastructure with entries that exactly correspond to the record entries in the Pool Registry. Therefore, the addressing between the InstanceSpace and the Pool Registry (and therefore the DesignSpace Encoding) is implied and requires no pointers.

The Processing of Messages into and through the design

Thus, to process messages into the design from the "outside" (operating environment):
Messages are accumulated. The Inlink Registry is processed and the links parsed out of the design encoding, complete with their filters, one by one. Any link which directly tests for this message is selected. If no link which filters for this message is found, a link which will take this message is searched for. If any such link is found then the message is assigned to the pool pointed to by the pointer to the registry. The entry in the Pool Registry is corresponded to the same record in the InstanceSpace. The message is then added into the cache for new messages.

Processing messages already within the InstanceSpace

The InstanceSpace structure is processed, top to bottom (or in any other order so later determined for more optimal design). Messages stored in the "current" cache for each pool message stream cache are processed. For each message of a given ID. The record from the Pool Registry is identified (directly corresponding to the given InstanceSpace record). From this record and all additional records stored in the Pool Occurence Registry, pointers to the designspace encoding are followed and the links to which they point (if any) are identified. These links are tested against each message in the "current" pool cache. If a message successfully traverses a link, its destination function (which is queued for invokation) or pool is identified from the encoding. If the destination is another pool then it is searched for in the Pool Registry. Having found the destination pool, the message is inserted in the "new" cache of the corresponding InstanceSpace record. Overflow conditions and caches are generated as needed.

Each record in the InstanceSpace structure is processed. Upon completion, the structure is parsed through again and all "new" caches are assigned as "current" and messages packed into the local cache and overflow conditions and caches retracted as necessary. In addition, all "current" messages still in the cache are assigned back to the "current" side of the cache. The Cache Boundary is shifted as needed.

Note that this adjustment could occur as each pool is processed rather than requiring a second pass. In addition, the flags indicating the cache assignment switch could be presumed and set globally.

Nerve Band
Restrictions on Encoding language design
Ammended: September 3, 1995

Not allowed

POOL;
POOL-func-NEXTPOOL;
POOL-func-func;

Allowed but not supported

-POOL;
POOL-;

Complex, planned to be supported in future:

=POOL;
POOL=;

Allowed variance in syntax

POOL-message,message-<destination>
POOL-message-message-<destination>

Illegal but not tested for: cannot have two 'unfiltered move' links out of the same pool

POOL-NEXTPOOL/func
POOL-NEXTPOOL/func

Not yet supported: move all messages except 'message'

POOL-!message-NEXTPOOL/func

Allowed

line of encoding %comment after line

Not supported

POOL=NEXTPOOL;

Will cause error

POOL- m1-NEXTPOOL;

Nerve Band

DigitalSpace Navigator Bar - please see below for links
| Frontiers | Home | Search | About Us | Feedback | At Work |