proj-oot-ootOvmNotes1

see also ootVm.txt; that file is older and needs to be integrated into the list in the following section

---

so i think some stuff that OVM should implement is:

todo should also read more about the OOP parts of JVM and CIL. todo should also read about Cmm/C-- runtime support todo update Oot todos

as you can see, the purpose of OVM is coming into focus:

but everything should be not very dynamic/metaprogrammable/dynamically typed (remember the lesson from PyPy?), so this is different from Oot Core.

---

Instruction format (128-bit):

1 x 16-bit opcode 3 x (16-bit operand + 8-bit addr mode) 1 x (32-bit operand + 8-bit addr mode)

16 bytes

Note that there is no space for encoding length format bits here -- UNLESS you reduced the opcode by 5 bits to 11 bits. Which isn't crazy. So maybe:

5 encoding length format bits 1 x 11-bit opcode 3 x (16-bit operand + 8-bit addr mode) 1 x (32-bit operand + 8-bit addr mode)

16 bytes

We could also have a 64-bit encoding format:

4 encoding length format bits + 2 RESERVED bits + 10-bit opcode + 4 x (8-bit operand + 4-bit addr mode)

---

i dunno man, this seems like a lot of work to implement in assembly language.

also, what about the idea of incremental implementation? how is the porter going to be able to just implement the bare VM and use existing implementations of most of the opcodes?

i guess some of these things could be compile-time macros (eg hash tables).

but i feel like we really have a couple of levels here.

maybe some/many of these things would be 'standard library functions' at the OVM level (eg hash tables).

hmm, that makes a lot more sense to me. So we would specify a smaller core VM, which has to actually be implemented, and then a large standard library. And then porters would have to implement the VM, and then for better interoperability and efficiency on a given platform they could go ahead and incrementally override parts of the standard library with platform-specific stuff.

another issue is static typing. There's a tension here:

I think the solution is: (a) some of the dynamic stuff will be in the layer above (in the implementation of Oot Core on top of OVM) (b) there is some dynamic stuff at this level but it is easy to tell from looking at each instruction if it has any dynamicity. For example, if we use my idea for 'polymorphic assembly' by way of a type operand, then instructions whose type operands are constant mode are statically typed. This means that OVM code that is composed only of non-dynamic instructions can be efficiently compiled. And the language implementation itself will be like that.

Still, this suggests that maybe we are trying to do too many things at once.

Should we have one layer for a 'language implementing language', and then OVM is a 'runtime VM' implemented in that language? The problem with that may be that the 'runtime VM' has to support funky control flow like delimited continuations, so we don't want the language implementing language to impose and abstract away something like a restrictive call chain/stack abstraction, because then it seems like we have another interpreter-on-top-of-an-interpreter layer. But i'm not sure i fully understand that part, so that objection could be invalid. todo/hmmm.

My immediate thoughts are that Oot itself may be the 'language implementing language' that the reference implementation is ultimately written in. So when i say 'it's a lot of work to write this in assembly' that's not relevant, because the Oot implementation will be compiled to Boot, we don't have to write it in Boot directly (except maybe once to bootstrap). But is this really true? I don't expect our compiler to be smart enough to write efficient Boot code for things like context switches in the scheduler.

And, in any case we actually want the runtime VM to have the property that it supports dynamic typing yet you can easily identify code with static typing, because this will help JIT'ing, compilers, etc. This is certainly helpful for efficient compilation of a self-hosting implementation of Oot itself, but it'll be helpful for user code as well, because users will be able to write statically typed Oot code, we can use the ordinary toolchain to compile that to OVM, and then the toolchain will be able to recognize that the OVM code is statically typed and compile it down further rather than interpreting it.

---

so here's the design i'm coming up with. It seems odd to me, in that i don't think i've heard of it being done this way before, but it seems to satisfy the considerations noted in the previous section:

OVM is a VM with opcodes.

Some of the opcodes are primitive. A porter has to implement these. For example, BEQ.

The opcodes which are not primitive are 'standard library functions'. These have implementations provided in the language of OVM, in terms of primitive functions (or other library functions; but there are no circular dependencies between library functions, except for self-referencing recursion (a function can call itself)). For example, hashtable_get(table, key). A porter can start out not implementing these and then implement them incrementally later on to improve interoperation and efficiency.

Some of the opcodes, including some (but probably not all) of the primitive ones, and including some but not all of the standard library ones, are (what's the word for this? secured? protected? guarded? fenced? barricaded? shielded? defended? prohibited? restricted? controlled? secured? access-controlled? restrictedaccess? unsafe? let's say 'unsafe'), in a protection-ring-security-model sense. If we are given some untrusted user code to run, we had better scan through it and make sure it doesn't contain any of these opcodes (alternately, the OVM could have a special mode where it faults on privileged instructions). For example, array_get_noboundscheck(array, location).

Standard library opcode implementations can call unsafe opcodes.

Some of the opcodes can sometimes or always be 'dynamic' (the others are called 'static'). This may make them difficult to statically and efficiently compile to some targets. It is possible to determine whether each instruction instance is static or dynamic just by syntactically inspecting it. For example, 'ADD' (polymorphic addition) is dynamic when its type operand is not a constant.

The Oot implementation is written in terms of only static instructions, and can freely use unsafe opcodes.

User code that contains only static opcodes can be most efficiently compiled.

User code that is untrusted cannot contain unsafe opcodes. However, it can contain safe standard library opcodes which are themselves implemented using unsafe opcodes.

This design should:

Should we partition the opcode address space to make it easy to recognize unsafe and primitive and static opcodes? Yeah, why not, we have 16 bits.

I'm thinking that memory management would work like this: there are primitive operations that do stuff (like loading, storing, copying) without managing memory, and primitive operations that do things like incrementing/decrementing reference counts, and reading/writing through read/write barriers. Some or all of loading/storing/copying directly without memory management is unsafe, and messing with reference counts is unsafe. Then memory-aware variants of stuff like loading, storing, copying is provided, and untrusted code (or portable user code) uses that.

---

i guess OVM should have some optional instructions that some platforms and not others implement, and that are not provided by macros/stdlib unless implemented.

For example, unicode stuff: embedded platforms usually won't support this because it requires a lot of data, but desktop platforms usually will. We want the HLL to be able to use the platform unicode stuff if it is there because interop, but otherwise the HLL must do without.

---

some notes from RPython [1]:

"Note that there are tons of special cased restrictions that you’ll encounter as you go. The exact definition is “RPython is everything that our translation toolchain can accept” :)"

ok that's crazy

---

my conclusions from the previous section:

we should do:

---

if you don't want to allow pointers into the middle of structures, then you probably want to deal with pairs (base_pointer, offset).

---

---

i guess all we really need to keep track of is where the pointers are. If we know where the pointers are on the stacks and in registers, and we know where the pointers are in memory, then we can prevent sandboxed code from manufacturing its own pointers. (is that how CLR prevents sandboxed code from manufacturing its own pointers by reading integers from memory in as pointers?)

in order to know where pointers are in memory we probably have to have data structure declarations, and force all allocated memory to be one of these data structures (although 'array of bytes' is a valid structure, provided that bytes can never be loaded as pointers).

data structure primitives include i32, ptr, probably also i64, fixed-length arrays, variable-length arrays.

i guess for these purposes we don't really need to know if e.g. such-and-such field within a data structure is a u32 or an i32, we just need its size. So we don't really need typed everything (although that may be useful at the OVM level for other reasons anyhow). And we don't really need 'objects' with encapsulated methods, we just need something more like C structs.

---

for another perspective, consider the runtimeless restricted variant of D, "BetterC?":

[3]

" Retained Features

Nearly the full language remains available. Highlights include:

    Unrestricted use of compile-time features
    Full metaprogramming facilities
    Nested functions, nested structs, delegates and lambdas
    Member functions, constructors, destructors, operating overloading, etc.
    The full module system
    Array slicing, and array bounds checking
    RAII (yes, it can work without exceptions)
    scope(exit)
    Memory safety protections
    Interfacing with C++
    COM classes and C++ classes
    assert failures are directed to the C runtime library
    switch with strings
    final switch
    unittest

...

Unavailable Features

D features not available with BetterC?:

    Garbage Collection
    TypeInfo and ModuleInfo
    Classes
    Built-in threading (e.g. core.thread)
    Dynamic arrays (though slices of static arrays work) and associative arrays
    Exceptions
    synchronized and core.sync
    Static module constructors or destructors

"

(i don't know why dynamic arrays don't work, i think i read that it has something to do with GC)

this suggests a different path that i mentioned once before, where there would be yet another language in between BootX? and OVM. This other language would be a C-like runtimeless language.

In this case the other language would have the interop stuff and would only run trusted code, and the OVM would run untrusted code (and would do things like bounds-checking and convert cooperative multitasking to preemptive).

I'm not sure that there's really much benefit to not just doing as i said above, though, and have a subset of the OVM instructions be 'unsafe', and have many of the OVM instructions be macroinstructions. One issue with that is that multitasking remains cooperative, not fully pre-emptive; we can fix that by having a facility in the VM to designate an instruction to execute every N instructions, however. As for forcing read and write barriers upon access to various memory lcations, the safe instructions can do that.

---

Two alternatives for how unsafe instructions could be encoded in OVM:

1) BootX? instructions (8-, 16-, 32-bit) are always interpreted as unsafe instructions that do the same thing as in BootX?. The "safe variants" of these (e.g. safe ADD) are different opcodes and/or are in a 64- or 128-bit encoding. The allows the compiler to macrocompile some 'safe' instructions into a series of 'unsafe' instructions while leaving other 'safe' instructions as single (128-bit) instructions. Before beginning execution of untrusted code, OVM must scan it and check that no unsafe instructions are in there (which is easy because the unsafe ones are those less than 128-bit encoding, or mb less than 64-bit). Then during execution any unsafe instructions which are encountered are assumed to be trusted, and executed immediately.

2) BootX? instructions are interpreted as the 'safe variant' of themselves, e.g. LOAD does bounds-checking and reference-counting, etc. This allows the OVM program to be expressed with mostly short (8, 16, 32-bit) instructions. However to express unsafe instructions you would either (a) reuse the same opcodes but they are interpreted differently when the VM is in 'ring 0' protection ring/domain state, or (b) have variants of all of the BootX?-analog opcodes that are 'unsafe', and those can only be executed in the 'ring 0' state.

The advantage of (1) is that the compiler can intersperse unsafe instructions (such as those to update reference counts) with 'user code' without jumping to special unsafe subroutines and without also interspersing 'switch protection ring/domain' instructions. The advantage of (2) is that most user code can be more compact.

I guess it's likely that unsafe instructions may exceed user code in compiled code, because for every primitive actual operation like 'LOAD', this will usually be surrounded with a few unsafe instructions (bounds check, update reference counts). Of course the toolchain might not work like that at all (it may get compile all user code to unsafe instructions if it compiles any of it), but i bet if we're optimizing, it's better to optimize for the use case where safe and unsafe code is interspersed than for pure user code size.

So i'm leaning towards (1). This is also useful for expressing the definition of macroinstructions in terms of primitives and other previously defined macroinstructions.

We could also do both; have one 'ring' state that means 'treat BootX?-encoded instructions as unsafe BootX? instructions' and a different 'ring' state that means 'treat BootX?-encoded instructions as safe user code'. That would also allow us to immediately begin executing untrusted code without scanning it first (and then maybe switch to the other mode later after it's been scanned and/or partially compiled). Heck, why not?

So i'm leaning towards 'both'.

---

Also there are a few alternatives for defining the semantics of the safe variants of BootX?