PIOS Virtual Machine and Code

[Mike Prince]

Introduction
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
This is our first big test; agreeing on the virtual machine=20
architecture.  I have been piecing this virtual machine=20
together for a while now, and every part interplay=92s with=20
every other part.  Unfortunately the justification for this=20
model exists on millions of scraps of papers and in my head. =20
This text file was put together in only a few hours and lacks=20
most of my justification for this model, so please give do not=20
be too harsh for the glaring omissions.  In time, through=20
discussion, they will all be resolved.

As I have said before, nothing is cast in stone, and I am very=20
versatile.  Please critique any and every part of this=20
proposal.  I would be happy to be proved completely wrong if=20
we end up finding a better way to do this.  We can not=20
compromise the project due to individual pride.  I am looking=20
forward to you opinions.

My date for beginning to discuss the virtual machine/language=20
issue was the first of November, so we are running a little=20
ahead of schedule.  You can still look forward to a more=20
detailed agenda of November on the 1st though.

Now on to the work...


For this project we will need to define at least two=20
languages.

First we must define a basic model for our computing world. =20
That model will be represented by a virtual machine.  Our=20
tools will be distributed in the programming language of this=20
virtual machine.  For now we will call this language vmcode.

We could program all our tools in this low level vmcode.  But=20
there are two immediate disadvantages.  First, we may decide=20
to change the vmcode.  If we did, all prior coding would have=20
to be re-written.  Secondly, there are many good programming=20
languages already out there that we could choose from.  We=20
might even decide to create a hybrid language of our own=20
better suited to programming our virtual machine.

I would like to model vmcode and the machine loosely on Forth.

Virtual Machine
---------------
The largest object is the tool box.  A tool box contains=20
tools, stacks, and agents.

Tools are executable code and are accessible to all agents=20
within the tool box. The tool box stacks are data global to=20
the tool box.

Agents are the execution primitives.  Agents have their own=20
stacks which are only accessible to the agent to which they=20
belong.  Agents reside in one tool box at a time.  Agents can=20
move between tools and tool boxes at the tools discretion. =20
Agents carry their own stacks with them as they move between=20
tools or tool boxes.

An agent has two active stacks at any time A and P.  A is the=20
stack used for generic operations.  P is the path stack and is=20
used as a return stack for program flow control.  Each stack=20
also has a stack pointer.  Neither A nor P may be a tool box=20
stack (global) when an agent transfers control to another tool=20
box.

NOTE: Should we have more active stacks?  A floating point=20
stack, secondary stack, loop counter stack, etc?=20

Agents are synchronized through the use of blocking=20
semaphores.  All semaphores are stored in tool box stack 2. =20
Semaphores are 32 bits and are referenced as an array.  Vmcode=20
has up, down, and setsemaphore primitives.  Up increases the=20
value of the semaphore by one. If an agent is blocked on that=20
semaphore, then only one agent will be unblocked and the=20
semaphore will automatically be reduced by one again.  A down=20
attempts to reduce the semaphore by one.  If the count is=20
already zero the agent blocks until the count can be reduced. =20
A set forces to semaphore to a particular value.

Our virtual machine is broken up into domains.  Domains are=20
further broken up into work spaces.  Each work space can=20
contain one or more tool boxes.  A work space may or may not=20
be accessible at any given time (i.e. has been disconnected=20
from the net, turned off, etc).  Domains are used to=20
encapsulate groups of work spaces to ensure security or the=20
containment of computational resources.

Each tool box provides a name for itself up to 2^7 bytes long. =20
Each tool box has up to 2^15 tools and/or stacks.  Each agent=20
can have up to 2^15 private stacks.  Each stack is up to 2^31=20
bytes long.

NOTE: All the numbers above has lost one bit.  In the case of=20
the stacks, agents use positive numbers to reference their=20
stacks, and negative numbers to reference global stacks,=20
resulting in a full 2^16 worth of stacks.

Each stacks data is accessible randomly or like a traditional=20
stack. All numbers are stored little endian.  Stacks grow=20
upwards.  The stack pointer points to the first free byte. =20
Data is not necessarily aligned on word boundaries.  Data=20
types are consistently represented on all machines.

Stacks are referenced by their number.  All positive numbered=20
stacks belong to the current agent.  All negative numbered=20
stacks are global and belong to the tool box the agent is=20
currently in.

When a stack underflow occurs, error information is pushed=20
onto the agents stack, and a call is issued to mark 0 of the=20
current tool; the error handling routine.  That routine may=20
elect to kill the agent, continue on as if nothing happened,=20
or take corrective action.

When a stack overflow occurs, the kernel attempts to adjust=20
the size of the stack to accommodate the new data.  If the=20
stack cannot be made larger then the tool box is moved to a=20
workspace that can handle a larger stack.

There are seven basic data types; 8 , 16, 32, and 64 bit=20
signed numbers, 80 bit floating point numbers(?), strings and=20
blocks.  Strings are length delimited arrays of bytes up to=20
2^7 bytes long.  Blocks are length delimited arrays of bytes=20
2^31 bytes long.

Abbreviations
-------------
8bit,16bit,32bit,64bit: all represent signed numbers
F: is an 80 bit floating point number
S: is a string of 8bit length plus n bytes of data.
B: is a block of 32bit length plus n bytes of data
#: is a number of expected type
$: stands for any one of 8, 16, 32, 64 (bit=20
numbers), F, S, or B.
xx: stands for the byte code for the operation.
op: stands for one of the previously mentioned=20
operations.
(): surround equations which are resolved by the=20
instruction.
[]: surrounds optional arguments
stack: a 16bit stack number, positive for agent,=20
negative for group.
size: a 32bit number.
flag: a 16bit number, non-zero if true.

Format of Instruction Descriptions
----------------------------------
The first line is what the vmcode assembler would expect, or=20
what a disassembler would generate.  The second line is the=20
resultant vmcode. The third line is the affect of the=20
instruction on the stack, to the left of the =3D> is before the=20
operation, to the right is after the operation. The rightmost=20
item on either side of the =3D> is the topmost item on the=20
stack.  Items on either side of the =3D> are assumed to be on=20
the agents current stack.  The last line is a description of=20
the operation.

Instructions
------------
#[.$]=20
xx #
-- =3D> #
Pushes the number onto the stack.  If a type is not defined=20
then 16bit is assumed.

=93text=94
xx 8bit data
-- =3D> data 8bit
Pushes the string plus the string length onto the stack.

{ ... }
xx 8bit data
-- =3D> data 8bit
Creates a string containing all data between the braces and=20
places it on the stack along with the resultant length.

[ ... ]
xx 32bit data
-- =3D> data 32bit
Creates a block containing all data between the braces and=20
places it on the stack along with the resultant length.

Pop.$
xx
# =3D> --
Pops the number, string, or block off the stack.
NOTE: Should this be replaced by a simple #of bytes GetSP -=20
SetSP macro?

add.$ sub.$ mul.$ div.$
xx
a b =3D> (a op b)
Takes the two top numbers off of the stack, and applies the=20
operation leaving the result on the stack.

$.to.$
xx
a =3D> b
Converts types.  Does not apply to strings or blocks.

NameToolBox
xx
S =3D> --
Notifies kernel tool box has been renamed.

Anchor
xx
-- =3D> --
Notifies kernel that tool box cannot be migrated from this=20
workspace.

UnAnchor
xx
-- =3D> --
Notifies kernel that tool box can be migrated to different=20
workspaces.

Unique
xx
-- =3D> --
Notifies kernel that this tool box may not be duplicated.

NotUnique
xx
-- =3D> --
Notifies kernel that this tool box may be duplicated.

Codify
xx
stack =3D> flag
Creates a code segment from a data segment.  The code segment=20
is expected to be intermediate byte code.  The segment is=20
scanned for validity, and compiled to binary if deemed=20
necessary.

SetA
xx
a =3D> --
Sets the primary stack to use stack a.

SetP
xx
a =3D> --
Sets the path stack to use stack a.  Stack a must be an agent=20
stack.

ReadA
xx
-- =3D> a
Gives the current primary stack number.

ReadP
xx
-- =3D> a
Gives the current path stack number.

SetA.SP
xx
a =3D> --
Sets the stack pointer for the primary stack.

ReadA.SP
xx
-- =3D> a=20
Returns the value of the stack pointer for the primary stack=20
before the instruction.

SetP.SP
xx
a =3D> --
Sets the stack pointer for the path stack.

ReadP.SP
xx
-- =3D> a
Returns the value of the stack pointer for the path stack.

NewStack
xx
stack size =3D> flag
Creates a new stack of size, returns true if successful.

DeleteStack
xx
stack =3D> flag
Deletes stack and returns true if successful.

SizeStack
xx
size =3D> flag
Resizes stack and returns true if successful.

NewAgent (Fork?)
xx
size =3D> flag
Creates a new agent in current tool box.  Returns false if=20
cannot complete.  Size bytes are pulled off the primary stack=20
of the creating agent and placed in agents primary stack. =20
Execution for both continues at the next instruction.

End
xx
-- =3D> --
Terminates execution of current agent.  Cleans up stacks.

>[.$] <[.$] =3D[.$] >=3D[.$] <=3D[.$]=20
xx
# # =3D> flag
Compares two values leaving a flag of 0 if false, non-zero if=20
true.

LockUp
xx
-- =3D> --
Locks kernel from compiling any more machine dependent code.

PortIn.$
xx
32bit =3D> #
Has the CPU do an In from the port.  Can only be compiled=20
before a LockUp command is executed.  Code in which PortIn are=20
automatically restricted from migrating from their workspace.

PortOut.$
xx
32bit xx =3D> --
Has the CPU do an Out to the indicated port. Can only be=20
compiled before a LockUp command is executed.  Code in which=20
PortIn are automatically restricted from migrating from their=20
workspace.

Up
xx
a =3D> --
Does an up on semaphore indexed by a.  If agents are blocked=20
on that semaphore then one will be unblocked.  All semaphores=20
are in stack -2.

Down
xx
a =3D> --
Does a down on a semaphore.  If the semaphore is smaller than=20
1 then the agent will block until another agent does an up. =20
All semaphores are in stack -2.

SetSemaphore
xx
32bit a =3D> --
Initializes a semaphore.

Return
xx
-- =3D> --
Parses path stack for a path to vector execution to.

Mark
xx
-- =3D> --
Indicates to compiler or interpreter a tool entry point.

Goto
xx
{complex} =3D> --
Parses primary stack for path to vector execution to.

IfGoto
xx
S flag =3D> --
If flag is true vector execution to path in string S.

Call
xx
{complex} =3D> --
Parses primary stack to path to vector execution to.  Saves=20
return path in path stack.

Peek
xx
size offset source_stack =3D> data
Copies size data starting from offset in source_stack onto top=20
of current stack.

Poke
xx
data size offset dest_stack =3D> --
Moves size bytes off current stack into dest_stack staring at=20
offset.

Dup.$
xx
# =3D> # #
Duplicates top item on stack, including strings and blocks.

Rot, Pick?
How to implement these, do we need these?

I know I=92m missing instructions, the previous ones should give=20
you a flavor for the kind of virtual machine and instruction=20
set I would like.  Please let me know how big the instruction=20
set should get (# of instructions), what instructions should=20
be added, what we can reduce/get rid of, etc.

Program Flow Control
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
Herein lays a major obstacle to migrating agents.  Because all=20
the stacks have consistent representation between machines,=20
stacks can simply be bundled up and sent.  Because our return=20
path is a stack, and exhibits this same behavior, it to can be=20
sent.

Security is our first issue.  How can we maintain secure=20
communication between tool boxes.  First off, we can limit=20
migration of tool boxes to certain domains to minimize their=20
exposure.  Secondly, we allow tool boxes to control the gates=20
for agents entering and exiting.

All agents entering a tool box must first execute tool 1, mark=20
0.  This tool is the incoming gatekeeper code.  All agents=20
leaving a tool box are vectored likewise through tool 1, mark=20
2.  If no security is desired the code here can simply pass=20
the agent along.  However at this point code can encrypt all=20
outgoing agents and their data, and verify all incoming agents=20
validity.  The level of security implemented is up to the=20
tool.

Return information is stored on the path stack in the=20
following format.  Tool box names are stored as strings; data,=20
8 bit length, and the vmcode byte code for push string.  Tool=20
numbers are stored as 32 bit tool numbers and the byte code=20
for push 32 bit.  Mark numbers are stored as 16 bit numbers=20
and the byte code for push 16 bit.

When a return is executed, the path is parsed to determine how=20
to vector the agent.

When a call is executed the active stack is parsed to=20
determine how to vector the agent.  Immediately the return=20
mark is placed on the path stack.  If an agent moves between=20
tools, then the calling tool number is also placed in the=20
path.  If the agent moves between tool boxes then the agent is=20
first directed to the gate for the tool box.  The gate will=20
then issue a goto to vector the agent to the remote tool box. =20
Before the agent is relocated the tool box name is placed in=20
the path.

When a goto is issued that causes the agent to move between=20
tools, the path is evaluated to determine if the top entry on=20
path is tool number or tool box name.  If not then the sending=20
tool number is saved in the path.

When a goto is issued that causes the agent to move between=20
tool boxes, the path is evaluated to determine if the top=20
entry is a tool box name.  If not then the sending tool box=20
name is saved in the path.

This is only a partial explanation.  Because I would like to=20
encourage more discussion early on I am sending this out=20
incomplete.  By next week the full text should be ready.

Here are some of my questions
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D
How many tools/stacks per tool box should we have as a limit?=20
2^15 or 2^31?  The smaller lines up nicely with current=20
segmentation schemes of the 486.  The larger allows us to=20
manage much larger numbers of objects per tool box.

How many more/what kind access instructions should we have for=20
moving data to/from stacks?

Should we have more fundamental types of stacks (a floating=20
point one, a loop counter one, alternate one, etc).

Should the stack pointer be global or local?  If it=92s local=20
then everyone has to have their own copy of SP=92s to every=20
global stack.  In addition if we implement automatic stack=20
contraction/expansion then we would have to reconcile the=20
differences between all the agents global SP=92s.  If it=92s=20
global than how do we handle the case of two agents accessing=20
the same stack simultaneously (i.e. a two CPU system with=20
shared memory).  How do we manipulate the SP then?

How do we limit access to global stacks?  Should we make the=20
tools manage that themselves using semaphores, or provide=20
primitives for locking the stacks themselves?  Any other=20
ideas?

How do we represent the agents vmcode IP when moving between=20
workspaces?  The crude get it done way is to count the number=20
of vmcode instructions up till the point execution was=20
stopped.  Is there a faster way to determine this?  A better=20
way, maybe using predefined stall points indicated by marks? =20
Ideas?

In what order should we push arrays onto the stack?

What language should we program the kernel in?

What language should we select for our high level language? =20
Or should we create our own?

It is a big leap of faith to jump from a simple RISC virtual=20
machine (TAOS) to a Forth like machine.  What are arguments=20
for and against this?

What should the format of floating point numbers be, 32, 64,=20
80 bit?

Longer Term Plans
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=20
Here is a little glimpse into how I would like for things to=20
turn out.  One camp of developers will have full blown=20
development systems to write code in.  If our system becomes=20
accepted these will be developed in time, at great expense. =20
For now though, we do not have the time or money.

The other camp will write interactively like Forth.  This is=20
the one that can be implemented relatively easily and quickly. =20
This also is closer to my idea of organic computing.

I would like for the programmer to =93exist=94 within a tool box. =20
The programmer would build from the inside out, testing code=20
as he/she went along.  While the programmer was writing code=20
agents could enter into the tool box and exit, or resident=20
agents could continue executing the code they were working on. =20

I believe we could write a simple debug tool that would sit=20
inside the tool box and facilitate this; keeping track of tool=20
names and mark names, sending and receiving information to an=20
assembler, interacting with the programmers interface be it a=20
GUI or simple command line, etc.

How about a simple tool that sits in your tool box while you=20
are developing it that just provides a command line interface. =20
The tool could be called the basement, because it lets you=20
work in the lowest part of the OS, giving you an unadulterated=20
view and control of virtual machine.

A little further down the line I hope to alleviate device=20
drivers.  Each device would come with it=92s open tool box, that=20
would be found by the kernel when starting up and executed. =20
This is very similar to work being done with Open Boot (is=20
that the right name?) that embeds Forth like code that=20
initializes and provides an interface to devices that plug=20
into the computer.

Just a few ideas for now.

Conclusion
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
I wrote this to get the ball rolling.  I expect for there to=20
be MANY changes to what I have just proposed.  Please voice=20
any and all questions and comments.  An open dialog is what we=20
need to hash out these ideas.

Hope to hear from you soon,

Mike