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.
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;
