Because the Mes project is rather large, I have split this post into two parts, that will cover major components of the stack: stage0, which provides components for low-level system bootstrap, and mes/mescc, which intends to bootstrap Linux from a minimal Scheme and minimal C compiler. I begin with examining stage0.
The motivation behind stage0 is to allow bootstrapping of computer software from scratch, avoiding thompsonization attacks on GCC and other bootstrapped components.
The process begins with hand-cranked hex numbers manually typed into the memory of the machine. As a first root of trust, authors use a simulator of a very simple RISCy architecture1. There are two stated reasons for this decision: first, x86 CPUs are not trusted anyways, so in the future currently-emulated architecture can be implemented in FPGA, and eventually in TTL, to have a trusted environment; second, to avoid a situation where architecture-specific aspects creep into the design of the boostrapping process. Inside this VM environment, the actual x86/arm/whatever binaries can be produced. On the other hand, conceptually, the plan is to have several independent roots of trust on each architecture, so that independent cross-verification is possible - for instance, some components were also ported to AMD64, there is work in progress of ARMv7l. The bootstrap procedure for stage0 has the following structure:
(stage-0) hex0_monitor -> (stage-1) hex0 -> hex1 -> hex2 -> M0 -> (stage-2) cc_x86 -> (stage-3) M2-Planet/mescc-tools.2
Through the bootstrapping procedure, a set of increasingly more powerful hex assemblers are created, the last of which is then used to write a macro assembler and simple C compilers. There is also a document of why other decisions were rejected, which is not even terrible.
The bootstrap starts with hex_monitor: an application that reads a sequence of hex digits from the keyboard (stdin in case of emulator), and writes the copy of the input stream to first tape, and the hex code assembled from the user input to the second. The first tape is necessary to save the input to a source file while there is no text editor on the platform yet; the second tape contains actual assembled code. The functionality of this stage is equivalent to "tee -a tape_1| sed -e 's/[;#].*$//g' | xxd -r -p > tape_2". For testing bootstrapping on Linux, the root monitor is created using an assembler from the next stage, hex0, which for this purpose is provided as C, assembler, and hex0 code, and is compiled by GCC from the C source. In real bootstrap, the user will have to type in hex_monitor code manually/punch in the cards/etc.
48 c7 c7 00 00 00 00 # mov $0x0,%rdi 48 c7 c0 3c 00 00 00 # mov $0x3c,%rax 0f 05 # syscall
Figure 1. Hex0 assembly example.
Hex03 assumes better environment (there is a simple text editor source provided along hex0_monitor). Therefore, it reads input from a tape, and only assembles it - that is, does only sed -e 's/[;#].*$//g' < tape_1 | xxd -r -p > tape_2. It is used to implement hex1.
:c # :First_pass_0
# Check for %
483D 25000000 ; CMPI32_RAX %0x25
0F84 %e ; JE32 %First_pass_pointer
Figure 2. Hex1 assembly example.
Hex1 iteration on assembler: it supports creating and referencing single-character labels, that is, calculating and patching-in 16bit relative displacements. Otherwise, it's functionally equivalent to hex1 -- converts textual hex numbers to binary while stripping comments. It still does not support architecture instruction mnemonics. This assembler is used solely for implementing a more advanced assembler, hex2.
# ;; Set p->Next = p->Next->Next->Next 18020000 # LOAD32 R0 R2 0 ; Get Next->Next->Next 23010000 # STORE32 R0 R1 0 ; Set Next = Next->Next->Next :Identify_Macros_1 18010000 # LOAD32 R0 R1 0 ; Get node->next A0300000 # CMPSKIPI.NE R0 0 ; If node->next is NULL 3C00 @Identify_Macros_Done # JUMP @Identify_Macros_Done ; Be done # ;; Otherwise keep looping 3C00 @Identify_Macros_0 # JUMP @Identify_Macros_0 :Identify_Macros_Done # ;; Restore registers 0902803F # POPR R3 R15 0902802F # POPR R2 R15 0902801F # POPR R1 R15 0902800F # POPR R0 R15 0D01001F # RET R15 :Identify_Macros_string 444546494E450000 # "DEFINE"
Figure 3. Hex2 assembly example.
Hex2 is main workhorse of both stage0 and mes -- all other utilities provide output that is assembled and linked by hex2. It supports longer labels and more addressing modes: 16bit absolute, optionally 8bit relative, 32bit absolute and relative. This tool is architecture-specific to some extent - it must support generating all architecture-provided jump types that may be necessary during the bootstrapping.
:start
;; Check if we are going to hit outside the world
HAL_MEM ; Get total amount of Memory
LOADR R1 @MINIMAL_MEMORY ; Get our Minimal Value
CMPSKIP.GE R0 R1 ; Check if we have enough
JUMP @FAILED_INITIALIZATION ; If not fail gracefully
Figure 4. M0 macroassebly
M0 is implemented in hex2, and it is the first macro assembler that reduces the amount of hex code that one has to write, by adding support of integers4, textual macros5, raw strings, textual strings6. M0 expands all aliases, converts textual strings and integers to architecture-specific format, and outputs the results in the hex2 format.
Then, there is cc_x86, a compiler from a subset of C to x86 variant of M0 assembly, in ~4500 lines of M0 assembly. It produces code that is supposed to be processed by M0_x86 (not bootstrapped yet) and hex2_x86 (also not bootstrapped yet). x86 versions of M0 and hex2 are currently built by gcc, and their proper bootstrap is only planned yet. Variants of this compiler for other architectures are planned, but not started yet. Alongside with the C compiler, one can also find a forth and a lisp implementation(~3500 lines of M0 asm).
M0_arch, hex2_arch, cc_arch are in turn used for compiling mescc-tools and M2-Planet. M2-Planet is an extended version of cc_arch, improving C support, and supporting code generation for multiple architectures. mescc-tools contains utilities which are useful during system bootstrap (simple batch shell, chmod +x analogue, uname, M1 macroassembler, hex2 linker/assembler).
The next tools in bootstrapping sequence are mes/mescc, but there is no direct link between m2/mescc-tools and mes/mescc yet -- this is still work in progress. I will provide overview of mes/mescc in the next post.
Some notes:
- In general, I find the bootstrapping architecture sound, the author definitely knows what fit-in-head means.
- Before genesising anything, I would like do experiments with the mes/mescc itself. Also, vpatch releases should happen in FFA style, instead of taking heathen artifacts and polishing them.
- IMO it makes no sense adopting the VM, given that apparently mips.v7 will be the republican CPU architecture on ice40.
- This leads to the question of the genesising order: if we won't use the VM, does it have any sense to begin genesis from stage0, given that it's support for hardware architectures is immature at this point?
- This all made me thinking about bootstrapping GNAT, which was implemented in Ada from it's very first day. I guess a trip into the world of Ada-to-C translators will be necessary.
So far for the examination, I have prepared a tarball with all the artifacts mentioned in the post:
curl http://bvt-trace.net/src/stage0-mescc-tools.tgz > stage0-mescc-tools.tgz curl http://bvt-trace.net/src/stage0-mescc-tools.tgz.bvt.sig > stage0-mescc-tools.tgz.bvt.sig
- Input to simulator is provided via keyboard/stdin, output is written to tapes/files. The design document for the architecture is available here. [↩]
- This stage so far is emulated, and the code is compiled with GCC. [↩]
- Also bootstrapped on linux using GCC-compiled hex0. [↩]
- Due to endianness issues, M0 is also architecture-specific. There is also a macroassembler called M1 - it supports the functionality of all architecture-specific M0 implementations. [↩]
- Aliases for sequences of hex characters; all instruction mnenomics are implemented as aliases. [↩]
- Raw strings are like FFA quotes -- passed to hex2 verbatim. Textual strings are converted to hex at the M0 output, so that hex2 assembles the binary representation of the string. [↩]
- MIPS.V, not RISC-V. [↩]