diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/hex0.md | 450 |
1 files changed, 450 insertions, 0 deletions
diff --git a/content/hex0.md b/content/hex0.md new file mode 100644 index 0000000..1930885 --- /dev/null +++ b/content/hex0.md @@ -0,0 +1,450 @@ +Title: RISC-V Adventures II: hex0 +Date: 2021-06-08 +Category: +Tags: +Slug: hex0 +Lang: en +Summary: + A love story about trust, machine code, hexadecimal notation and weird + instruction formats, with an epic unexpected solution coming back from the + afterlife. + +[Stage0](https://github.com/oriansj/stage0) is a crazy project that is pretty +well aligned with our vision of trust, bootstrappable software and whatnot. + +During the last two weeks we have been working on the port of Stage0 to +RISC-V, providing the very first step of the process, so we came here to talk +about it, including a fantastic software necromancy moment you are going to +enjoy. + +### The origin of the times + +Once upon a time, software was written in machine code. Directly expressing the +machine instructions by the hands of the *programmers*. That was long, long, +time ago. + +One day some programmer decided to write a translator that mapped that machine +code to something more human readable and created what we call *assembly +language* today. It gained popularity and programmers decided to add more and +more functionalities to the *assembly language* until the point that what they +created was not a one-to-one mapping with machine code anymore. + +That's how the first *programming languages* were born. + +Their power was so immense that programmers decided to rewrite all their tools +using the new *programming languages*, they even wrote newer *programming +languages* with them. + +But power corrupts the mind of the fool. Blinded by the power of *programming +languages*, most of the programmers forgot the origin of the times, and +forgetting the history is always a mistake. + +*Epic music starts...* + + +### The problem + +> Warning: I oversimplified during the beginning of the post, but now... Oh +> boy! I'm going to flatten this shit. + +Well, we need auditable software. I don't think anyone can deny that fact. + +But what does "auditable software" mean? Isn't free software enough? + +It is true that the best way to audit stuff is to read the code of the +programs. It's the classic way we had to know if a program is doing what we +want it to. But, how can you be really sure the code you are reading is the one +that is shipping with your program? + +You can't! In general it's impossible to know. There are many reasons, but I +will oversimplify and give you just some thoughts and let the people from +[bootstrappable](http://bootstrappable.org/) do the dirty job. + +1. The compilation process is not reproducible, so the same source can result + in different binaries. You can't just compare different binaries to make + sure your compiler is compiled correctly. + +2. We have no way to solve the chicken-egg problem. The recipe to build the + compiler version X is to get the sources of the compiler version X and + compile them with the compiler version X-1. But how do you get the compiler + version X-1? Rinse and repeat. + Also... Where's the first version of your compiler? Does it run in modern + machines with modern operating systems? + +3. As there's no real way to get your compilers compiled by yourself, there's + no real way to be sure that the compilers are emitting the code they are + supposed to. You have to [**trust + them**](https://www.cs.umass.edu/~emery/classes/cmpsci691st/readings/Sec/Reflections-on-Trusting-Trust.pdf), + and you can't audit what you need to trust. + +The first point is where projects like Nix and Guix have sense: they try to +create reproducible stuff. Not only for compilation processes but also for +scientific studies (that have to be reproduced by other people, because... +that's how science works, isn't it?) and other things. Being able to create +identical environments where you can ensure that their (compilation) output is +going to be identical is extremely important, but I'll leave that for now. + +The second and third point are two different problems but they result in the +same: software distributions ship huge binary blobs (hundreds of megabytes) as +an starting point (bash, gcc...) so the users have no chance to check if those +binaries are corrupt. + +[GNU Mes](https://www.gnu.org/software/mes/) is a Scheme interpreter and C +compiler that was designed to reduce the size of the binaries you need to ship +with your distro. Mes has successfully reduced the size of the binaries that +need to be shipped with distros like Guix, but the project is more ambitious +that that. + +### Full-source bootstrap + +[Stage-0](https://savannah.nongnu.org/projects/stage0/) is a project that is +tackling the same "trusting trust" problem but from the opposite perspective, +starting in the low-level, rather than the high-level approach that GNU Mes +uses. + +Both projects work together to provide a greater goal: the full-source +bootstrap. The whole bootstrap is started from source, with no binaries +involved, so the distros don't need to ship binaries anymore. + +But how is that? + +### Hex0 + +Stage0 starts in the low level, the lowest possible, and builds more complex +programs from there, step by step. + +The first step, Hex0, is a self-hosting "assembler". I quote the word assembler +there because I think it's a very strong word for this: it's an ELF file +written in hexadecimal, with extra comments. + +Hex0 is able to compile itself to a binary ELF file, converting the Hexadecimal +values to the binary values and stripping the comments. + +We still have to compile the first Hex0 with something but that's not as +difficult as compiling the first GCC because basically Hex0 can be compiled by +very simple programs or even by hand, because it contains literally what is +going to be written in the final ELF. + +The comments on the Hex0 files describe the instructions on each of the lines +of the ELF file so the resulting files can be audited, instruction by +instruction, with the manual of the ISA as a reference. + +This starting point is more than enough to build on top of. We just need to add +more functionalities to the next steps: labels, constants... Until we are able +to compile a simple C compiler, Mes or anything. + +It's a clever solution for a crazy problem. + +### Hex0 in RISC-V: my experience + +So this is my blog and I come here to talk about myself![^1] + +Some weeks ago I had the chance to make that first step, Hex0, for RISC-V (64 +bit). You can take a look to [the code here](https://github.com/oriansj/bootstrap-seeds/pull/2/files). + +There you can see I added three files: the assembly file, the hex0 file and the +binary of the compiled hex0. They are basically the same thing, but they are +included for readability. + +#### The assembly + +The first step for me was to write the assembly file. It's easy once you know +how to make system calls in POSIX. + +**POSIX system calls in RISC-V** are pretty easy: + +- Load the arguments for the call in registers `a0`, `a1`... +- Load the *syscall number* in `a7` +- Run `ecall` + +The result of the system call comes in `a0`. + +**Input arguments** are also important, because we need to be able to tell to +Hex0 which is the file we want to compile, and where to put its output. + +That's pretty easy, input arguments are inserted in the stack, so we can load +them by *pop*-ing them. As in any C program, the first element we get is the +amount of arguments and the rest of them are the arguments themselves. + +Putting all together, if you take a look to the first block of the program: + + ::asm + _start: + ld a0, 0(sp) # Get number of the args + ld a1, 8(sp) # Get program name + ld a2, 16(sp) # Input file name + + ... + + # Open input file and store FD in s2 + li a7, 56 # sys_openat + li a0, -100 # AT_FDCWD + mv a1, a2 # input file + li a2, 0 # read only + ecall + mv s2, a0 # Save fd in for later + +In the first chunk we are reading the stack, element by element, and in the +second we are opening the input file, using the filename we just obtained from +the stack. + +Simple. + +As a note, I'd like to remind you to finish your program, because if you don't +it will continue to execute the memory after it and it'll explode in your face: + + ::asm + terminate: + # Terminate program with 0 return code + li a7, 93 # sys_exit + li a0, 0 # Return code 0 + ecall + +This tells the OS to finish the execution. + +The internals of the assembly file are simple, I won't explain them in detail. +It basically iterates character by character, removing the comments and +converting the hex value couples to a byte. + +Read it and tell me if you need help understanding it![^contact] + +#### The conversion to the Hex0 + +Hex0, as I said, is an ELF file, written in hexadecimal, so we need to compile +our assembly file to binary and represent each of the instructions in +hexadecimal. And we need to resolve all the labels to final addresses. + +There's no easy way to do it. I started doing it by hand, reading the RISC-V +spec and converting the instructions one by one. But I tackled several +difficulties doing that. + +Pseudoinstructions are expanded to more than one instruction so we need to be +careful in the comments and explain that correctly. Also, we need to resolve +the addresses accordingly. For example: + + ::asm + la a1, buffer + +This is a pseudoinstruction, and we need to resolve it to: + + ::asm + auipc a1, 0 + addi a1, a1, $OFFSET + +Where `$OFFSET` is the offset from that instruction to the label `buffer`. + +These kind of expansions change our perception of the amount of instructions we +have and we have to be extremely careful. I didn't even mention the case where +the offset is very large! That's another story (thankfully we don't have to +deal with yet). + +Once the pseudoinstructions are expanded we need to convert them to the hex +value, and I swear it's the most boring task I ever made in my life. Basically +because the RISC-V instructions are not easy to map to their binary (for +reasons related with the hardware implementation). + +##### The eagles are coming! + +But I had a trick, a deus ex machina that would safe my life. During the last +months I've been randomly working on a Scheme compiler for RISC-V assembly and +that made me start making a [RISC-V assembly interpreter and compiler in +python](http://git.elenq.tech/pysc-v/). It's still an early WIP, and was +almost abandoned, but it has the basic machinery that lets me compile simple +instructions to hex. + +With this dirty glue code I was able to compile the instructions one by one: + + + ::python + from registers.RV32I import * + from InstructionSets.RV64I import * + + Regs = RegistersRV32I() + + def x(registerName): + return Regs.getPos(registerName) + + def compile(instruction): + hexrepr = hex(instruction.compile().value) + hexval = hexrepr[2:] + if len(hexval) < 8: + hexval = "0" * (8 - len(hexval)) + hexval + + final = "" + for i in range(0,8,2): + final += hexval[i:i+2] + " " + final = final.rstrip().upper() + return " ".join(reversed(final.split(" "))) + + +I just needed to open a python shell and write something like: + + ::python + compile( addi(x("a0"), x("a1"), 12) ) + +And that would compile that instruction for me, giving me the output in a +beautiful hexadecimal format. + + ::hex + 13 85 C5 00 + +Not the best UX but usable enough for a small file like this. + +##### The addresses + +The addresses are still something to solve. + +I'm an idiot so I counted the instructions by hand and then realized I had to +expand some pseudoinstructions I forgot, so all the branch instructions were +broken. *Yes, I'm like that*. + +Try to be smarter than I am. Use this trick: + +Leave all the instructions that use addresses set to a wrong address, like 0 or +something, until you converted the whole file. Once you have that, resolve the +addresses. That way you'll make sure every pseudoinstruction is expanded and +you'll be able to use tools that will help you to choose addresses correctly. + +The trick I used was to add the ELF header, compile the file and then inspect +the resulting binary. + +For the compilation there are two choices: we can use the assembly file we +wrote previously simply assembling it to a binary and use it as the hex0 +assembler; or we can use the high level C prototype that Stage0 provides. In +any case, they have to give the same result. + +I still don't know why `objdump` is unable to process the binaries of the hex0 +files but GDB is able to do it so... Launch a GDB as [I explained in the +previous post](https://ekaitz.elenq.tech/lightening.html) and disassemble the +whole file[^where]. + +It'll look like this: + + ::asm + 0x0000000000600078: ld a0,0(sp) + 0x000000000060007c: ld a1,8(sp) + 0x0000000000600080: ld a2,16(sp) + 0x0000000000600084: li s4,0 + 0x0000000000600088: li s5,0 + 0x000000000060008c: li a7,56 + 0x0000000000600090: li a0,-100 + 0x0000000000600094: mv a1,a2 + 0x0000000000600098: li a2,0 + 0x000000000060009c: ecall + ... + +With that dissasembled result, we can literally make some math with the +addresses and fix all the instructions. We just need to substract the target +address from the current address in the branches, so we get the offset. + +> NOTE: Be careful with the `la` pseudoinstruction (`auipc + addi`). The base +> address here is the one of the `auipc`, not the one of the `addi`. + +##### The ELF header + +If we don't know how to make the ELF header, we can't make the previous step, +so better if we mention something about it. + +Other files of the project are hex0 files too, so they also have a heavily +commented ELF header we can use as a reference. Also, [wikipedia has a great +explanation of it](https://en.wikipedia.org/wiki/Executable_and_Linkable_Format#File_header). + +The main point we need to change is the `e_machine` field. We need to set it to +`0xF3`, indicating RISC-V. Also we need to make sure the flag of 64 bit system +has to be set for RV64 and remember to check the endianness. + +> NOTE: Big Endian it's the most natural way to write the file by hand. If you +> want to go for Little Endian this might get weird to write. The python script +> above uses Little Endian, watch the `reversed` call on it. + + +##### Debugging + +Once you have everything ready you need to make sure it's doing what it's +supposed to. + +My first working program was failing to use an output file. Someone in the +`#bootstrappable` IRC channel (I'm sorry, I can't remember who was) told me to +`strace` the program to see what was going on, and with that and some debugging +with GDB's `layout asm`, I was able to figure out one instruction was using a +wrong register. + +These tools are important because the all the process is done by hand so there +are many chances to screw up somewhere. + +`strace` is extremely handy in this specific program because most of the +functionality it has is based on system calls. If you clean the output +correctly you can see everything the program does accurately. + +--- + +<div style=" + text-align: center; + font-size: smaller; + padding-left: 3em; + padding-right: 3em; + padding-top: 1em; + padding-bottom: 1em; + border-top: 1px solid var(--border-color); + border-bottom: 1px solid var(--border-color)"> +Remember you can hire <a href="https://elenq.tech">ElenQ +Technology</a> to help you with your research, development or training. <br/> +If you want to encourage my free software work you can support me on <a +href="https://buymeacoffee.com/ekaitz">Buy Me a Coffee</a> or on <a +href="https://liberapay.com/ekaitz">Liberapay</a>. +</div> + +--- + +### Final thoughts + +This contribution have been a lot of fun. It let me understand a little bit +more about the ecosystem around the full-source bootstrap, which is kinda +complex and includes some other stuff I didn't even mention. + +I learned a lot from this, now I have a deeper understanding of the instruction +formats on RISC-V and I learned some cool GDB tricks that are always useful. + +Stage0 has a really interesting approach for auditability that's worth thinking +about. They build everything from a commented binary file (that's basically +what hex0 is) that acts like a seed, so we can audit everything, including the +very first step. The solution of having the contents of the ELF file directly +written in hexadecimal is enough to ensure we can certify the contents are what +we expect, and having every instruction commented with its assembly counterpart +gives us the chance to go to the ISA and check if that's actually what it is +supposed to be. Perfectly auditable. + +Using this first step as a building block for anything else ensures that we +never need to rely on a binary file we can't know where does it come from. + +Really interesting stuff. + +Now we have this very first step ported to an open instruction set, what also +opens the door to the auditability from the hardware perspective. Now we can +start thinking about having an auditable software stack in a device we designed +ourselves, so we can audit it too. This is huge. + +Now, we need to keep pushing in this direction, porting all the rest of the +steps of Stage0, Mes and many other projects, if we want to reach a full RISC-V +support. This is just one small step in that direction. + +Hey! I almost forgot! And thanks to this I had the chance to work a little bit +more on my assembly interpreter, and recover it from the darkness. That's also +great. Isn't it? + +> Well, so we learned some things today, but the most important is that all the +> stupid things we do, all the random projects we work on, all the experiences +> we have in life are not just a *waste of time*. They may appear to be useful +> in the future, but you don't know when... +> What is sure here is if you don't stay creative and active, you'll never +> have any experience to learn from. + + +[^1]: Not really, in fact, I use my experience as a vehicle to introduce you to + great projects and interesting pieces of knowledge. But ssssh, don't tell + anyone. + +[^contact]: Contact me, seriously. I have my [contact info here](https://ekaitz.elenq.tech/pages/about.html) + +[^where]: If you want to know where to start to disassemble, you can just ask + `where` to GDB. |