The contents of boot_reference as of 2017/03/27, just before a cleanup/removal of old-now-incorrect stuff/decision to remove 'optional' instructions:

Title

:hardbreaks:

Version: unreleased/in-progress/under development. Working towards development version 0.0.0-0.

todo: i said this was RISC-y, but: + +

Cheatsheet

Instruction encoding: 16 bits, little endian, from LSB to MSB, for fields each 4 bits long: opcode, operands 0, 1, 2. Instructions are packed into 64-bit aligned quads. The least-significant-bit of each quad must be 0. + + Datatypes: u16 (unsigned 16-bit integer), ptr (pointer). + + Registers: 16 registers. First 8 are special: + + (todo see below this is out of date)

0. 0 register 1. PC 2. ERR 3. SCRATCH 4. HIDDENSTACK 5. DATASTACK 6. CALLSTACK 7. reserved for future use + + Instructions: todo: this is slightly out of date, copy updated version from below:

0. annotate (also nop, when operands are zero) 1. loadi (load immediate) 2. load (load from memory to register) 3. store (store from register to memory) 4. cpy (copy from register to register (in other architectures this is usually called "MOV")) 5. skipz (skip if zero) 6. skipnz (skip if non-zero) 7. calli (call indirect) 8. pop 9. push 10. add-u16 (addition of u16s) 11. sub-u16 (subtraction of u16s) 12. leq-u16 (less-than-or-equal of u16s) 13. add-ptr (add a u16 to a pointer) 14. sub-ptr (subtract a u16 from a pointer) 15. vmcall (other vm functionality)

Instruction encoding

The instruction encoding is fixed-length 16-bits, and instructions are grouped into 64-bit 'quads'. + Encodings are little-endian, and bits are given from LSB to MSB. + + The encoding of each instruction is:

• 4 bits: opcode
• 4 bits: operand 0
• 4 bits: operand 1
• 4 bits: operand 2 + + Four instructions are grouped into a 'quad'. The quads must be 64-bit aligned in memory. The least significant bit of each quad must always be 0. This implies that every fourth instruction only has half of the opcodes available to it. The motivation for that is so that implementations may extend Boot by defining additional syntax and semantics for 64-bit chunks whose least significant bit is 1. + +

Data types

There are five defined data types:

• U16 (unsigned 16-bit integer)
• PTR (pointer)
• CODEPTR (pointer to executable code)
• OTHER (opaque implementation-dependent type)
• UNDEFINED (the result of an invalid operation) + + Pointers (PTRs) are semi-opaque; although there are instructions to add integers to pointers, pointers are not themselves integers. Pointers cannot be added or compared to other pointers. The underlying representation of pointers is unspecified; pointers may be, for example, 64-bit native pointers, or they may be 16-bit integers. + + Each register, stack, and memory location must be able to contain at least one "word" which can be either of a 16-bit integer, or a pointer, or a codepointer. Registers, stack, and memory locations may or may not be capable of containing other opaque values that are neither U16s nor PTRs nor CODEPTRs ('OTHER'). + + Codepointers (CODEPTRs) are opaque; platforms may fail to support arithmetic on them or dereferencing them (for writing or even for reading). Similarly, no standard Boot instructions support operating on OTHER types; these may only be moved from place to place (if an implementation uses OTHER values, it is anticipated that implementation would provide library functions or other implementation-dependent extensions that can produce, manipulate, and consume them). + + Platforms are not required to detect attempts to apply unsupported operations on data. + + If an attempt is made to dereference and write to the location 'pointed to' by a non-PTR, or if a dynamic jump is made to a non-CODEPTR, then the result is undefined behavior. Similarly, an attempt to dereference and read from the location 'pointed to' by a non-PTR should result in a crash or in an UNDEFINED value (however, implementations are permitted to behave in an undefined manner for invalid pointer reads, although this is discouraged; this is only allowed because in some cases the platform that the implementation is running on may already do something weird when certain memory locations are read, and we don't want to make the implementation check each memory access to avoid those locations). Otherwise, application of unsupported/incorrectly typed operations result either in a crash (ideally with an INVALID_TYPE error code, but this is not required), or continued program execution with the result of the operation being a value of type UNDEFINED (but undefined BEHAVIOR, that is, a behavior other than these two alternatives, is not allowed, however). For example, application of an ADD-U16 instruction to a PTR may result in a crash, or an UNDEFINED value that behaves like some arbitrary PTR, or an UNDEFINED value that behaves like some other type, but will not result in arbitrary memory corruption. + + Since we don't define the semantics of either OTHER or UNDEFINED, these would seem to be redundant. The intent is that OTHERs may be created by correctly-behaving libraries and implementation extensions, whereas UNDEFINEDs are only created by erroneous programs. + +

Registers

There are 16 registers. The first 8 registers are special.

0. 0 register 1. PC 2. ERR (or STATUS?) 3. TOS (alias to top of datastack) 4. CAP (or MODE?) 5. HIDDENSTACK 6. DATASTACK 7. CALLSTACK + + There are three stacks (hiddenstack, datastack, callstack). The stack pointers are in scare quotes because Boot programs are not allowed to directly manipulate these; all stack manipulation must be accomplished via the PUSH and POP and LOAD and STORE instructions. The stacks may or may not be stored in ordinary memory, and the "pointers" may or may not be ordinary pointers. + + In more detail: + +

0. 0 register

Reading from the zero register always returns 0. Writing to the zero register has no effect. + +

1. PC

The program counter. This is a pointer to the next instruction to be executed. It is read-only. A Boot program is not allowed to directly read or write program memory, or dereference pointers into program memory. Program memory may or may not be stored in ordinary memory.

2. ERR

This is used to return error codes. An error code of "0" means no error (success).

It is also used to return carry and overflow results from addition and subtraction.

1. # 3. CAP This stores a stack "pointer" to the capability stack.
   1. 4. HIDDENSTACK

A stack "pointer".

The capacity of the hiddenstack is 15 items.

The compiler must be able to resolve at compile time the stack offset of each access of the hidden stack, relative to the hiddenstack pointer at the beginning of function/code segment.

1. # 5. DATASTACK

A stack "pointer".

1. # 6. CALLSTACK

A stack "pointer".

1. # 7. TOS Alias to the top item on DATASTACK.

Instructions

The 16 three-operand instruction opcodes and mnemonics and operand signatures are: 0. annotate: ? ? ? (this instruction is called BAD when all operands are zeros) 1. loadi: oi k k (load 8-bit u16 immediate) 2. loadlo: oi k k (load 8-bit immediate with multiply; multiply the destination register by 256 and then add the 8-bit immediate value. NOTE: this instruction is illegal except immediately following either a LOADI to the same destination register, or another LOADIM to the same destination register. NOTE: these allow you to load constant greater than 8 bits. The maximum constant size is platform-specific; a sequence of LOADI/LOADIM instructions that would create a larger constant than the platform supports is unsupported on that platform) 3. load: o k si (load from memory (plus constant offset) to register; atomic/tear-free) 4. store: so k i (store from register to memory (plus constant offset); atomic/tear-free) 5. TWO: ? ? k (two-operand instructions)) 6. jrel: 0 0 k (relative jump) 7. skipz: 0 0 ii (skip if zero) 8. skipnz: 0 0 ii (skip if non-zero) 9. add-u16: oi ii ii (addition of u16s) 10. addi-u16: oi ii k (add a constant to a u16) 11. sub-u16: oi ii ii (subtraction of u16s) 12. leq-u16: o ii ii (less-than-or-equal of u16s) 13. add-ptr: op ip ii (add a u16 to a pointer) 14. addi-ptr: op ip k (add a constant to a pointer) 15. cas-atomic: pio i i (compare-and-swap)

The 16 two-operand instruction opcodes and mnemonics and operand signatures are: 0. cpy: o i (copy from register to register (in other architectures this is usually called "MOV")) 1. or-u16: io i (bitwise OR: op0 = op0 OR op1) 2. and-u16: io i (bitwise AND: op0 = op0 AND op1) 3. xor-u16: io i (bitwise XOR: op0 = op0 XOR op1) 4. add-atomic-u16 pio i (value at memory location is atomically replaced with the sum of its previous value and a register) 5. add-atomic-ptr pio i 6. mul-u16: io i (multiplication: op0 = op0 MUL op1) 7. xchng-atomic: pio io (value at memory location is atomically exchanged with value of register) 8. picki: sm k (push a copy of the n-th item in a stack (zero-indexed) onto the top of the stack) (note: this can also do dup (with r0), over) 9. rolli: sm k (rotate the top n+2 elements on a stack) (note: this can also do swap (with k=0), rot) 10. slli-u16: io k (op0 = logical_shift_left(op0 by k bits)) 11. srli-u16: io k (op0 = logical_shift_right(op0 by k bits)) 12. library: k k (call to platform-specific library function identified by 8-bit constant (remember, each operand is only 4 bits); calling conventions are as with syscalls) 13. pop: o sim 14. push: som i 15. ONE: ? k (one-operand instructions)

The 16 one-operand instruction opcodes and mnemonics and operand signatures are: 0. jd: pc (dynamic jump) 1. stackload: sm (pop saved stack from DATASTACK, and load it) 2. stacksave: si (save stack, and push it to DATASTACK) 3. fence-acquire: p (the memory location p is ordered by an acquire memory barrier) 4. fence-release: p (the memory location p is ordered by a release memory barrier) 5. loadmulti-atomic: k (pop pointer (pi) from DATASTACK, atomically load k items onto DATASTACK) 6. storemulti-atomic: k (pop pointer (pi) from DATASTACK, atomically store k items from DATASTACK) 8. not-u16: io (bitwise NOT: op0 = NOT op0) 8. addstk-u16: sm (stack version of add-u16) 9. substk-u16 10. leqstk-u16 11. addstk-ptr: sm (stack version of add-ptr) 12. fence-seq: p (the memory location p is ordered by a sequential consistency memory barrier) 13. stackif: sm (pop top three items in stack, if top item was 0, push second item, otherwise push third item; C's ternary conditional operator) 14. ZERO: k (zero-operand misc operations) 15. syscall: k (zero-operand I/O and IPC)

The 16 zero-operand misc operations are: 1. 2. casstk: (stack version of CAS, on DATASTACK) 3. log: (log a message; loglevel k and then pointer to message is on top of DATASTACK) 4. mdealloc (deallocate memory (like C's free); ptr is on TOS) 5. 6. 7. 8. sra1stk-u16: (TOS = arithmetic_shift_right(TOS by 1 bit)) 9. modeset: (change the processor state in some way (eg set error handler); 2 arguments passed on stack) 10. malloc-shared: (allocate shared memory supporting atomic operations; amount of memory requested is popped from DATASTACK, result is pushed to DATASTACK) 11. mrealloc: (resize memory allocation (like C's realloc); pointer and new size is popped from top of DATASTACK) 12. malloc-local: (allocate local memory; amount of memory requested is popped from DATASTACK, result is pushed to DATASTACK) 13. regload: (pop k from datastack?, pop saved k registers from CALLSTACK and restore k registers starting with 8) 14. regsave: (pop k from datastack?, save registers greater than 7 and less than 7+k, and push to CALLSTACK; stored register format is opaque (but is it one or many entries on CALLSTACK?!? b/c we want to be able to manually manipulate CALLSTACK and even move saved registers elsewhere in memory, right?)) 15. break

The 16 zero-operand syscalls are:

0. sysinfo (does this take a 16-bit query argument on the stack, or just return all of the system info every time? probably the former) 1. delete 2. walk (like plan9's 9p's walk; todo is this actually different from ls/query, i forgot) 3. rand 4. sync/flush 5. seek 6. fork 7. forkdone (fork's join/wait) (todo can't we do this some other way, using channels, without burning an opcode?) 8. open 9. close 10. read 11. write 12. poll (todo: how exactly poll works) 13. time (takes a clock_spec on the stack, and returns one or more words on the stack according to the clock_spec; returns 0(s) and sets ERR condition if requested clock is not supported) 14. 15. halt (pop DATASTACK and terminate program execution, returning the popped value)

Many of the zero-operand instructions (esp. the syscall-y ones) also use DATASTACK to pass/return parameters.

todo:

• mb we do want loadd and stored in the three-operand instructions: b/c the reason for leaving them out is that you could just do pointer arithmetic to get the same thing in two instructions, but can you do pointer arithmetic on stack "pointers"? If not, then this doesn't work.
• is it better to have in-place and/or, or accumulator (ie outputs to scratch) and/or?
• does MUL deserve to be in the 3-operand instructions?
• REGSAVE and REGLOAD could just always push/pop from CODESTACK, in which case they could both be one-operand and could take a k argument for number of registers)
• could have some zero-operand instructions (syscalls, i guess?)
• yknow, we don't really want mlen to return u16, and we dont want to limit malloc to accept a u16. So mb replace u16 with a 'native' 'number' type that is guaranteed to be at least u16, but not guaranteed to be u16, so eg if you add 1 to 65535 it may or may not overflow or wrap to 0
• can opaque values be in constant table, or are they limited to u16s? if u16s, then limited to 64k words of code because that's the biggest jump constant you can encode. That seems too limiting...
• if limited to u16, should we even have a constant table? without a constant table, you could still have a jump table, but it would limit code size to 4k words, and also would be less space-efficient to store

maybe:

• stack size and stack capacity queries?
• REST-like CRUD and collection operations?
• capability security
• cpuid
• reset
• mark register as unused
• sync/flush
• kill
• array, string, map creation?
• CSWAP (fredkin) and CCNOT (Toffoli)? Note that CCNOT can do AND in two instructions (load 0 into a register x, then do CCNOT(A,B,x), where x is the output), and, given a zero register, if you make 0 swap instead of 1, CSWAP generalizes SWAP, and also can do OR in two instructions (LOADI 1 into a register x then do CSWAP(A, B, x), where x is the output). Of course, CSWAP and CCNOT can also be defined by and+or in a similar fashion
• getinfo/mode, setinfo/mode? mb to set error handing strategy, eg when we encounter an err, do we put the err code into ERR or do we jump to an error handler?
• stack addition/subtract/mul?
• a way to check capability access beforehand without causing an ACCESS DENIED error?

maybe (copied from ootLibrariesNotes6):

• readinfo remove
• writeinfo remove dup mount
• exec wait
• getpid(getmypid) kill
• pipe signal stuff_to_setup_signal_handlers
• cpuid/uname/myinfo/version
• mv mkdir 12. info: pi (finfo/stat) 13. query: pi (ls/query) 6. mcalloc: po i (allocate memory and zero it (like C's calloc))
• don't need 'sleep' b/c we have 'poll' which has a timeout
• done?: create new code segment, and/or transform data memory to code memory, and/or transform code memory to data memory (and possibly, create new code segment with constant table)
• done?: loadk, loadj (load from constant table/jump table; if we have these, we need to have a way to set these tables, right? b/c we don't have a LOADMODULE in Boot)
• calli: o i pc (call indirect) (should calli's arguments be numbers of parameters and return values passed on the stack, instead of actually being parameters and return argument values?) mkcode pi ?or mb more generally, ?chmod_pointer? for capability stuff? but mb we need mkcode so that we have a way to specify the constant table with the code? rroll: sm i (rotate the top n elements on a stack in the other direction) cnot: io io (CNOT gate; flip the contents of register op0 iff the contents of register op1 is 1) not: oi ii (logical not) (we don't need: just do SUB 1 - x) (do we need NEG? no, just do SUB 0 - x) loadd: o i si (load from memory to register, dynamic offset) (this would probably be frequently used, but is not essential, as you could just do an ADD-PTR followed by a LOAD) stored: so i i (store from register to memory, dynamic offset) mlen: si (current depth of stack or length of allocated memory (should those be combined?)) atomic add, and, or, xor, max, min exec addstk-u16 sm substk-u16 sm leqstk-u16 sm addstk-ptr sm stackisempty: o (is the stack empty? should probably be 0-operand. Useful if we want to enumerate the stack for debugging without doing a stacksave. Not sure if we should keep this one; b/c it will be rare and you can always just do a stacksave, if we make the stacksave format non-opaque) loadk: k k k (load from 12-bit-indexed constant table, and push onto DATASTACK) switch (jrel with a register input) swap: io io (swap the contents of two registers) (note: 'roll STACK 0' can be used to swap the top 2 elements in a stack) andi-u16: io k (bitwise AND: op0 = op0 AND constant) (note: is this worth it? remember that constant can only be 0-15. would stackandi-u16 k k be better?) 5. capunpack: (from the capability on top of CAP, generate a struct describing it. there is no 'cappack' because you can't edit capabilities) 6. capalloc: (allocate new capability stack (input on TOS: size to allocate); returns the new stack pointer on data stack. Deallocate with ordinary mdealloc)

note: over and dup can be done with 'pick 1' and 'pick 0'

TODO see also those other lists of popular linux syscalls that i made, and my ideas regarding instructions for epoll, completion ports, etc

note: the reason for (malloc, mdealloc, open, close, read, write), is that they are fundamental and common. (walk) because it is fundamental. (poll sleep) because they are called a lot in tight loops and so you want them to be efficient.

Where the signature characters mean:

• k: compile-time constant (integer from 0-15, inclusive)
• i: input register (input is any type except for stack "pointers") (register direct)
• o: output register (output is any type except for stack "pointers") (register direct)
• io: input and output register (any type except for stack "pointers") (register direct)
• ii: input register (input is integer type) (register direct)
• oi: output register (output is integer type) (register direct)
• ip: input register (input is pointer type)
• op: output register (input is pointer type)
• pi: input pointer (register indirect) (stack "pointers" not allowed)
• po: output pointer (register indirect) (stack "pointers" not allowed)
• pm: pointer which may be read and/or written and/or mutated (stack "pointers" not allowed)
• si: input pointer (register indirect) (both ordinary pointers and stack "pointers" are allowed)
• so: output pointer (register indirect) (both ordinary pointers and stack "pointers" are allowed)
• sm: pointer which will be mutated (both ordinary pointers and stack "pointers" are allowed)
• sim: input pointer which will be mutated (both ordinary pointers and stack "pointers" are allowed)
• som: output pointer which will be mutated (both ordinary pointers and stack "pointers" are allowed)
• pc: input code pointer
• ?: variant, or reserved for future use
• 0: must be 0

In addition, the mnemonic 'nop' refers to 'annotate' with all zero operands.

In the following, op0, op1, op2 are short for operand 0, operand 1, operand 2.

Three-operand instructions:

1. ## 0. annotate: ? ? ? If all bits are zero, this is not ANNOTATE but rather BAD, an illegal instruction. This is to help halt execution if memory is accidentally executed, since some memory may contain zeros.

Used to embed metadata into code. Has no effect on execution; can be skipped by an interpreter or compiler.

1. ## 1. LOADI (load immediate): oi k k

A number is formed by bitwise concatenating op1 and op2, with op1 being MSB (that is, by multiplying the value of op1 by 16, and then adding this to op2). This number is then treated as a u16 and stored in the register indicated by op0.

1. ## 2. LOAD (load from memory to register): o k si

The contents of the register indicated by op2 is taken to be a pointer. The memory location indicated by this pointer, plus op1, is looked at, and the value found there is stored in the register indicated by op0.

Note: by giving a stack pointer in op2, LOAD can be used to peek at stack items at indices from 0 to 15 without POPing. Stack "pointers" are allowed in op2.

1. ## 3. STORE (store from register to memory): so k i

The value in the register indicated by op2 is stored in (the memory location indicated by the contents of the register indicated by op0, plus op1).

Note: by giving a stack pointer in op2, LOAD can be used to overwrite stack items at indices from 0 to 15 without PUSHing. Stack "pointers" are allowed in op2.

1. ## 4. SKIPZ (skip if zero): 0 0 ii

If the value in the register indicated by op1 is zero, then the PC is incremented by 1.

Operands 0 and 1 must be zero; skipz instructions with non-zero operands 0 or 1 are reserved for the internal use of the implementation, and are syntax errors if found in Boot program code.

1. ## 5. SKIPNZ (skip if non-zero): 0 0 ii

If the value in the register indicated by op1 is not zero, then the PC is incremented by 1.

Operands 0 and 1 must be zero; skipnz instructions with non-zero operands 0 or 1 are reserved for the internal use of the implementation, and are syntax errors if found in Boot program code.

1. ## 6. JREL (relative jump): 0 0 k

If k > 7, increment the PC by k-7. Otherwise, increment the PC by k - 9.

1. ## 7. two (two-operand instructions): ? ? k

The two-operand instruction identified by op2 is called with operands op0 and op1. See section below for a list of two-operand instructions.

1. ## 8. POP: o k sim

The n-th item on the stack specified by op2 is popped (reading the value, then reducing the stack size by 1 and moving each item above the n-th down by 1), where n is op1. The value that was popped is placed into the register specified by op0.

1. ## 9. PUSH: som k i

The value in the register specified by op2 is pushed into the stack at the n-th index, where n is given by op1 (increasing the stack size by 1 and moving each item above the n-th up by 1, then writing the value).

1. ## 10. ADD-U16 (addition of u16s): oi ii ii op0 := op1 + op2 + ERR, where ERR is either 0 or 1

if the result is larger than op0 can hold, op0 will be set to the result mod its op0's maximum value, and ERR will be set to 1; otherwise ERR will be set to 0

1. ## 11. SUB-U16 (subtraction of u16s): oi ii ii op0 := op1 - op2
   1. 12. LEQ-U16 (less-than-or-equal of u16s): oi ii ii op0 := 1 if op1 <= op2; otherwise op0 := 0
   2. 13. ADD-PTR (add a u16 to a pointer): op ip ii op0 := op1 + op2
   3. 14. SUB-PTR (subtract a u16 from a pointer): op ip ii op0 := op1 - op2
   4. 15. CALL (call indirect): o i pc

todo: this instruction was deleted, i think

The current PC is PUSHed onto CALLSTACK. The contents of the register specified by op1 is PUSHed onto DATASTACK. The PC is set to the contents of the register specified by op2, and execution continues until a RET is encountered when the TOS of CALLSTACK is equal to the next instruction. At that time, the register specified by op0 will be set to the return value of the RET, and execution resumes.

See also RET.

Two-operand instructions:

todo: some of the numbers below are wrong

1. ## 0. CPY (copy from register to register (in other architectures this is usually called "MOV")): o i

The value in the register indicated by op2 is copied into in the register indicated by op0.

1. ## 1. NOT (logical not): o i
   1. 2. SWAP (swap the contents of two registers): io io

The values in the registers specified by op0 and op1 are swapped.

1. ## 3. MALLOC (allocate memory): po i

Memory whose size is the value in the register indicated by op1 is allocated. Note: each location in memory must be able to hold at least a 16-bit word (but could hold more, depending on the implementation). So the units of the amount of memory requested is not bytes. If the allocation is successful, a pointer to the new memory is placed into the register indicated by op0. If the requested amount of memory is not available, ERR will be set to the code for OOM (out-of-memory) and the value in the register specified by op0 is undefined.

See also MDEALLOC.

1. ## 14. syscall (platform-specific instructions): k

The k-th platform-specific subroutine is called. See section 'calling convention'.

1. ## 15. ONE (one-operand instructions): ? k

The one-operand instruction identified by op1 is called with operand op0. See section below for a list of one-operand instructions.

One-operand instructions:

1. ## 0. RET (return from call): o

CALLSTACK is POPped and the PC is set the value popped, and the value in the register indicated by op0 is returned.

See also CALLI.

1. ## 1. MDEALLOC (free memory): pi The memory region found at the pointer in the register specified by op0 is deallocated.

If this pointer was not returned by a previous MALLOC, or if this memory region has already been deallocated (and has not been subsequently returned by another MALLOC), the result is undefined.

See also MALLOC.

1. ## 15. HALT (terminate program execution): i

Program execution is terminated, and the value in the register indicated by op0 is returned.

1. ## ?. CAS (compare-and-swap): pio i i Atomically, if the value of the memory location in the register op0 is equal to the contents of register op1, then set that memory location to the contents of register op2, and set register op1 to op2.
   1. ?. SYSINFO (query system information): one input, one output on stack The input determines which information is being queried. Currently defined:

0. Boot SYSINFO version. Returns 0. Note: this version number is distinct from the Boot specification version identifier (SdVer?