Compiling Brainfuck code - Part 4: A Static Compiler
This is the fourth post of a blog post series where I reproduce Eli Bendersky’s Adventures In JIT Compilation series, but this time using the Rust programming language.
- Part 1: An Optimized Interpreter
- Part 2: A Singlepass JIT Compiler
- Part 3: A Cranelift JIT Compiler
- Part 4: A Static Compiler
In this final part we will use the compiled code that we generated in the previous parts, and learn how to put them in an executable file, achieving a static compiler.
Executable files and Object Files §
To build a static compiler, we need to be able to save our generated assembly in a file, in a way that the operating system can execute.
Each OS have its own executable file format. On Windows, executable files are in the PE file format, on macOS in the Mach-O. On Linux, executable files are in the ELF file format, which we will be exploring a little more in deep here.
Another important piece of the compilation process are the object files, and the
process of linking. Object files contain compiled code, but only part of the
code that forms a program. They are used by compilers to split the source code
compilation (C compilers can compile each .c file to a separated object file),
or for distributing precompiled libraries, for example. Again, each OS has its
own object file format, which commonly uses the same format as executables, or
executables use an extended version of them. On Linux, objects are also ELF files.
To link all these object files into a complete and executable program, you use a linker. Each object file has a list of symbols, that, among other things, are used to indicate what function the file define, and which ones they are using (that may be defined in another file). It also has a list of relocations, that are used to indicate which points in the memory need to be modified, and how, to connect the object files. The linker is the program that read these files and does all these modifications, and outputs an executable.
We will see more practical examples of this further down.
Exploring ELF files §
As always, we will start by making a compiler for the simplest program that we
can achieve. In the previous parts we were using the add1 function as example,
but that don’t make into an interesting enough program. So let’s make a good old
“hello world” program.
On Linux x86-64 assembly, it would be:
section .data
hello: db 'Hello world!',10
helloLen: equ $-hello
section .text
global _start
_start:
mov rax, 1 ; 'write' system call = 1
mov rdi, 1 ; file descriptor 1 = STDOUT
mov rsi, hello ; string to write
mov rdx, helloLen ; length of string to write
syscall ; call the kernel
; Terminate program
mov rax, 60 ; 'exit' system call = 60
mov rdi, 0 ; exit with error code 0
syscall ; call the kernel
In the code above we have two sections. Each section holds a chunk of arbitrary
data. The sections can have any name, but the linker will map the section with
the name .data to a segment that will have read and write permissions when
executed, and the .text to a segment with read and execute permissions.
In the section .data we declared the string 'Hello World!\n' (the 10 there
is the ASCII code for line-break) with the label hello, and a constant for the
string length (compute by taking the current address ($) minus the hello
address).
And in the section .text we declare that the label _start is global (meaning
that other objects can see it), and declaring it preceding the code for printing
the string (using the ‘write’ syscall) and exiting (with the ‘exit’ syscall).
Every label above will map to a symbol in the object file, that later will be
used for applying relocations, debug purposes, etcetera. The _start symbol in
specific will be used by the linker to tell where is the entry point of our
executable (and that is why it must be global).
To assemble and link the program, we can use the assembler NASM and the linker ld:
$ nasm hello.as -f elf64 -o hello.o
$ ld hello.o -o hello
And running it:
$ ./hello
Hello World!
It works!
Now, let’s take a close look in the object file and the executable file. For
this, we can use the readelf utility. You can use the -a flag to show in one
go all the information that I will be explaining, but I will go in parts here.
First, lake take a look at the hello.o object file:
$ readelf hello.o -h
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: REL (Relocatable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x0
Start of program headers: 0 (bytes into file)
Start of section headers: 64 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 0 (bytes)
Number of program headers: 0
Size of section headers: 64 (bytes)
Number of section headers: 7
Section header string table index: 3
First we have the ELF header, with basic information like version, ABI, etc. It also contains the location in the file of the program headers (only relevant for executable files) and the section headers.
You may want to take a look on the man page for the ELF format to see in more detail what each field in the header means, and also for the parts below.
$ readelf hello.o -S
There are 7 section headers, starting at offset 0x40:
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .data PROGBITS 0000000000000000 00000200
000000000000000d 0000000000000000 WA 0 0 4
[ 2] .text PROGBITS 0000000000000000 00000210
0000000000000027 0000000000000000 AX 0 0 16
[ 3] .shstrtab STRTAB 0000000000000000 00000240
0000000000000032 0000000000000000 0 0 1
[ 4] .symtab SYMTAB 0000000000000000 00000280
00000000000000a8 0000000000000018 5 6 8
[ 5] .strtab STRTAB 0000000000000000 00000330
0000000000000020 0000000000000000 0 0 1
[ 6] .rela.text RELA 0000000000000000 00000350
0000000000000018 0000000000000018 4 2 8
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
l (large), p (processor specific)
Following it, we have the section headers. The first header is always a null
one. Here we can see that we have the headers for the .data and .text
sections that we have written in our assembly code. But we also have some other
sections that hold, respectively, the strings for the name of the sections
headers, the symbols, the string for the symbol names and such, and lastly the
relocations for the .text section.
Each section header tells some information about the section, like where its
content is in the file. It may also be linked to another section (like .symtab
has a link to the table that contains the symbol names).
The readelf can pretty print the contents of some sections, as we will see in a
moment, but you can also use -x to view the hex dump:
$ readelf hello.o -x .shstrtab
Hex dump of section '.shstrtab':
0x00000000 002e6461 7461002e 74657874 002e7368 ..data..text..sh
0x00000010 73747274 6162002e 73796d74 6162002e strtab..symtab..
0x00000020 73747274 6162002e 72656c61 2e746578 strtab..rela.tex
0x00000030 7400 t.
Here for example we can see that the section “section header string table” is a list of null byte terminated strings, with the first string being empty.
$ readelf hello.o -s
Symbol table '.symtab' contains 7 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FILE LOCAL DEFAULT ABS hello.as
2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
3: 0000000000000000 0 SECTION LOCAL DEFAULT 2
4: 0000000000000000 0 NOTYPE LOCAL DEFAULT 1 hello
5: 000000000000000d 0 NOTYPE LOCAL DEFAULT ABS helloLen
6: 0000000000000000 0 NOTYPE GLOBAL DEFAULT 2 _start
With -s we can see the symbol table. The first one is always null. There are
the symbols that we defined in our assembly, and some others introduced by the
assembler like the file name and symbols for each section (used for relocation).
Each symbol contains a value. In the case of hello and start it is the
address of the symbol in its respective section (both are at the start of the
section, so they are 0) and in helloLen is the length of the string.
$ readelf hello.o -r
Relocation section '.rela.text' at offset 0x350 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
00000000000c 000200000001 R_X86_64_64 0000000000000000 .data + 0
And lastly we have the relocations. Here we have only a single one for the
.text section that applies at offset 0xc, use the symbol 2 (the first 2
bytes of info) on the linked section (.symtab), is of type R_X86_64_64 (each
processor has its own set of relocation types) and has an addend of 0. This
means that it replaces a 64bit word at 0xc by the value of the symbol .data.
If we look at the disassembly of the machine code, we can see that in offset
0xc we have the last 8 bytes of the movabs instruction, the one that loads
the address of the hello string:
$ objdump -d -M intel hello.o
hello.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <_start>:
0: b8 01 00 00 00 mov eax,0x1
5: bf 01 00 00 00 mov edi,0x1
a: 48 be 00 00 00 00 00 movabs rsi,0x0
11: 00 00 00
14: ba 0d 00 00 00 mov edx,0xd
19: 0f 05 syscall
1b: b8 3c 00 00 00 mov eax,0x3c
20: bf 00 00 00 00 mov edi,0x0
25: 0f 05 syscall
This means that during linking, after the linker have set the location in memory
that the data section should be loaded, it will path that instruction to the
correct address of the hello string.
And we can see all this in action, by inspecting the ./hello executable file:
$ readelf hello -S
There are 6 section headers, starting at offset 0x2158:
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .text PROGBITS 0000000000401000 00001000
0000000000000027 0000000000000000 AX 0 0 16
[ 2] .data PROGBITS 0000000000402000 00002000
000000000000000d 0000000000000000 WA 0 0 4
[ 3] .symtab SYMTAB 0000000000000000 00002010
00000000000000f0 0000000000000018 4 6 8
[ 4] .strtab STRTAB 0000000000000000 00002100
0000000000000031 0000000000000000 0 0 1
[ 5] .shstrtab STRTAB 0000000000000000 00002131
0000000000000027 0000000000000000 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
l (large), p (processor specific)
Here we can see that the address of the .text and .data sections have been
set up to 0x401000 and 0x402000. Now if we take a look in the disassembly:
$ objdump -d -M intel hello
hello: file format elf64-x86-64
Disassembly of section .text:
0000000000401000 <_start>:
401000: b8 01 00 00 00 mov eax,0x1
401005: bf 01 00 00 00 mov edi,0x1
40100a: 48 be 00 20 40 00 00 movabs rsi,0x402000
401011: 00 00 00
401014: ba 0d 00 00 00 mov edx,0xd
401019: 0f 05 syscall
40101b: b8 3c 00 00 00 mov eax,0x3c
401020: bf 00 00 00 00 mov edi,0x0
401025: 0f 05 syscall
Look! The address in the movabs instruction, at offset 0xc was updated
to 0x402000 (in little endian)!.
Another thing you may notice if you run readelf hello -a is that it now
contains a program header table:
$ readelf hello -l
Elf file type is EXEC (Executable file)
Entry point 0x401000
There are 3 program headers, starting at offset 64
Program Headers:
Type Offset VirtAddr PhysAddr
FileSiz MemSiz Flags Align
LOAD 0x0000000000000000 0x0000000000400000 0x0000000000400000
0x00000000000000e8 0x00000000000000e8 R 0x1000
LOAD 0x0000000000001000 0x0000000000401000 0x0000000000401000
0x0000000000000027 0x0000000000000027 R E 0x1000
LOAD 0x0000000000002000 0x0000000000402000 0x0000000000402000
0x000000000000000d 0x000000000000000d RW 0x1000
Section to Segment mapping:
Segment Sections...
00
01 .text
02 .data
A program header contains information about things that the system need to
prepared for the program execution. Here we have three headers of type LOAD
that tells which segments of the file need to be loaded in memory.
The first one tells to load 232 (0xe8) bytes starting at offset 0 of the file
(that is, the ELF header and program headers) with read permissions in virtual
address 0x40_0000 (or physical address 0x40_0000 but most PCs today uses
virtual memory). (I am not sure why the ELF header is loaded in memory.)
The second one loads the .text section, with read and exec permissions, and
the third loads .data with read and write permissions.
The program headers themselves don’t say which sections they are mapping (although readelf shows the mapping), but you can check this yourself by comparing the offset and address of the segments here, with the ones in the section header of each section.
A minimal hello world §
Again, it’s always good to start experimenting with an idea by implementing the simplest example that we can make. In our case that would be compiling a hello world program. But the one that I showed is still not minimal enough.
Because our 'Hello World!\n' string is only read during the execution, it does
not need to live in a section with read and write permission like the .data.
We could put it in a .rodata, which is read only, but we can take advantage
that the .text segment has read permission and put the string there, saving an
entire section:
section .text
global _start
_start:
mov rax, 1 ; 'write' system call = 1
mov rdi, 1 ; file descriptor 1 = STDOUT
lea rsi, [rel hello] ; string to write
mov rdx, helloLen ; length of string to write
syscall ; call the kernel
; Terminate program
mov rax, 60 ; 'exit' system call = 60
mov rdi, 0 ; exit with error code 0
syscall ; call the kernel
hello: db 'Hello world!',10
helloLen: equ $-hello
And by putting the string alongside the code, we can make sure the string is
always at a constant offset from the code. This means that I could replace the
mov of the absolute address of hello in the code, by a lea rsi, [rel
hello] rip relative addressing, saving a relocation!
If you take a look at the disassembly now, you will see that that instruction is
compiled down to lea rsi, [rip+0x13]:
$ nasm hello.as -f elf64 -o hello.o
$ objdump -d -M intel hello.o
hello.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <_start>:
0: b8 01 00 00 00 mov eax,0x1
5: bf 01 00 00 00 mov edi,0x1
a: 48 8d 35 13 00 00 00 lea rsi,[rip+0x13] # 24 <hello>
11: ba 0d 00 00 00 mov edx,0xd
16: 0f 05 syscall
18: b8 3c 00 00 00 mov eax,0x3c
1d: bf 00 00 00 00 mov edi,0x0
22: 0f 05 syscall
0000000000000024 <hello>:
24: 48 rex.W
25: 65 6c gs ins BYTE PTR es:[rdi],dx
27: 6c ins BYTE PTR es:[rdi],dx
28: 6f outs dx,DWORD PTR ds:[rsi]
29: 20 77 6f and BYTE PTR [rdi+0x6f],dh
2c: 72 6c jb 9a <hello+0x76>
2e: 64 21 0a and DWORD PTR fs:[rdx],ecx
(Also, these strange instruction are there only because objdump is trying to interpret the string data as code now.)
The object crate §
Now we can finally start making a small compiler. First, lets use dynasm, like we did in part two, to get our hello world program in Rust:
let mut code: VecAssembler<X64Relocation> = VecAssembler::new(0);
let hello_str = b"Hello world!\n";
let len = hello_str.len() as i32;
dynasm!(code
; mov eax,1 // 'write' system call = 1
; mov edi,1 // file descriptor 1 = STDOUT
; lea rsi, [>hello] // string to write
; mov edx, DWORD len // length of string to write
; syscall // call the kernel
// Terminate program
; mov eax,60 // 'exit' system call
; mov edi,0 // exit with error code 0
; syscall // call the kernel
; hello:
; .bytes hello_str
);
let code = code.finalize().unwrap();
We can directly run that code using memmap2, to make sure everything is working:
let mut buffer = memmap2::MmapOptions::new()
.len(code.len())
.map_anon()
.unwrap();
buffer.copy_from_slice(code.as_slice());
let buffer = buffer.make_exec().unwrap();
let hello: unsafe extern "C" fn() -> ! = std::mem::transmute(buffer.as_ptr());
hello()
If you run this, it will print Hello World!.
But we should be compiling it to an object file. For this we will use the
object crate. As its docs says, “the object crate provides a unified
interface to working with objects files across platforms”.
This crate will allow us to write our object files, without needing to worry about the details of each object format, making it easier to make our compiler cross-platform. It also allows writing ELF and PE executables directly, but we would need to use its lower level API for each format, so we will not cover that here.
So first we crate a Object struct with the specification of our host:
let mut obj = object::write::Object::new(
object::BinaryFormat::Elf,
object::Architecture::X86_64,
object::Endianness::Little,
);
Next we can add the _start symbol to the object:
let start = obj.add_symbol(Symbol {
name: b"_start".to_vec(),
kind: object::SymbolKind::Text,
scope: object::SymbolScope::Linkage,
weak: false,
flags: SymbolFlags::None,
value: 0,
size: 0,
section: object::write::SymbolSection::Undefined,
});
We set its name; its kind, text, because it points to executable code; its scope, linkage, which make the symbol global, like we did in the assembly; it doesn’t need to be weak (weak symbols can be overridden by non-weak symbols); and it won’t need any special flags.
Value, size and section will be updated when we add data to the symbol, so I put some default values there for now.
Now we can crate the .text section, and by calling add_symbol_data we append
our code to it and at same time we update the _start symbol.
x86 instructions don’t need to be aligned, so the alignment is 1.
let text = obj.section_id(object::write::StandardSection::Text);
obj.add_symbol_data(start, text, &code, 1);
And that is it! Now we can emit it, and save it to a file!
let mut out = Vec::new();
obj.emit(&mut out).unwrap();
std::fs::write("hello.o", out).unwrap();
If we take a look at the object generated, we see that everything is as we expected:
$ readelf -Srs hello.o
There are 5 section headers, starting at offset 0xd8:
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .text PROGBITS 0000000000000000 00000040
0000000000000031 0000000000000000 AX 0 0 1
[ 2] .symtab SYMTAB 0000000000000000 00000078
0000000000000030 0000000000000018 3 1 8
[ 3] .strtab STRTAB 0000000000000000 000000a8
0000000000000008 0000000000000000 0 0 1
[ 4] .shstrtab STRTAB 0000000000000000 000000b0
0000000000000021 0000000000000000 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
l (large), p (processor specific)
There are no relocations in this file.
Symbol table '.symtab' contains 2 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 49 FUNC GLOBAL HIDDEN 1 _start
Now let’s link and run it:
$ ld hello.o -o hello
$ ./hello
Hello world!
It works!
A zero-dependency Static Compiler §
Now we know everything necessary to make the first version of our brainfuck compiler!
First, I will take an old version of our JIT compiler, the one right after we
start using dynasm, while we were still using syscalls. This is
because now our compiled code will not have access to Rust functions (unless
we compile them to a library and link them, as we will see later).
We also will need to make some changes. In our JIT compiler we were passing the program’s memory as an argument to the compiled code, but we will not be able to do this anymore. So instead we will allocate that memory on the stack.
To allocate memory from the stack is very easy, we only need to decrease the
value rsp by how much memory we need to allocate (the stack grows downwards).
We also need to make sure to clear the memory, because brainfuck programs assume
that they are initially zeroed1.
Note that we are allocating a relatively large value, 30000 bytes, but modern desktop systems have at least 1 MiB of reserved space for the stack, so that should not be a problem.
Another change is that we can no longer finish our program with a ret, because
there is no one to return to. So we replace it with a exit syscall.
So here is what the code becomes:
struct Program {
code: Vec<u8>,
}
impl Program {
fn new(source: &[u8]) -> Result<Program, UnbalancedBrackets> {
let mut code: VecAssembler<X64Relocation> = VecAssembler::new(0);
// r12 will be the adress of `memory`
// r13 will be the value of `pointer`
// r13 is set to 0
dynasm! { code
; .arch x64
; push rbp
; mov rbp, rsp
; xor r13, r13
// allocate 30_0000 bytes on stack for the memory
; sub rsp, 30_000
; mov r12, rsp
// zero the memory
; xor eax, eax
; mov r11, r12
; loop_:
; mov QWORD [r11], rax
; add r11, 8
; cmp r11, rbp
; jne <loop_
};
let mut bracket_stack = Vec::new();
for b in source {
match b {
b'+' => dynasm! { code
; .arch x64
; add BYTE [r12 + r13], 1
},
b'-' => dynasm! { code
; .arch x64
; add BYTE [r12 + r13], -1
},
b'.' => dynasm! { code
; .arch x64
; mov rax, 1 // write syscall
; mov rdi, 1 // stdout's file descriptor
; lea rsi, [r12 + r13] // buf address
; mov rdx, 1 // length
; syscall
},
b',' => dynasm! { code
; .arch x64
; mov rax, 0 // read syscall
; mov rdi, 0 // stdin's file descriptor
; lea rsi, [r12 + r13] // buf address
; mov rdx, 1 // length
; syscall
},
b'<' => dynasm! { code
; .arch x64
; sub r13, 1
; mov eax, 29999
; cmovb r13, rax
},
b'>' => dynasm! { code
; .arch x64
; add r13, 1
; xor eax, eax
; cmp r13, 30000
; cmove r13, rax
},
b'[' => {
let start_label = code.new_dynamic_label();
let end_label = code.new_dynamic_label();
dynasm! { code
; .arch x64
; cmp BYTE [r12+r13], 0
; je =>end_label
; =>start_label
};
bracket_stack.push((start_label, end_label));
}
b']' => {
let (start_label, end_label) = match bracket_stack.pop() {
Some(x) => x,
None => return Err(UnbalancedBrackets(']', code.offset().0)),
};
dynasm! { code
; .arch x64
; cmp BYTE [r12 + r13], 0
; jne =>start_label
; => end_label
};
}
_ => continue,
}
}
if !bracket_stack.is_empty() {
return Err(UnbalancedBrackets(']', code.offset().0));
}
dynasm! { code
; .arch x64
; xor rax, rax
; ->exit:
; mov rdi, rax // exit error code
; mov rax, 60 // exit syscall
; syscall
}
Ok(Program {
code: code.finalize().unwrap(),
})
}
}
Now the only thing we need to do is to write it to an object file:
fn to_object(&self) -> Vec<u8> {
let mut obj = object::write::Object::new(
object::BinaryFormat::Elf,
object::Architecture::X86_64,
object::Endianness::Little,
);
let start = obj.add_symbol(Symbol {
name: b"_start".to_vec(),
value: 0,
size: 0,
kind: object::SymbolKind::Text,
scope: object::SymbolScope::Linkage,
weak: false,
section: object::write::SymbolSection::Undefined,
flags: SymbolFlags::None,
});
let text = obj.section_id(object::write::StandardSection::Text);
obj.add_symbol_data(start, text, &self.code, 16);
let mut out = Vec::new();
obj.emit(&mut out).unwrap();
out
}
And in the main:
use std::{
path::{Path, PathBuf},
process::ExitCode,
};
fn main() -> ExitCode {
let mut args = std::env::args();
let input_file = args.nth(1).unwrap();
let source = match std::fs::read(&input_file) {
Ok(x) => x,
Err(err) => {
eprintln!("Error reading '{}': {}", input_file, err);
return ExitCode::from(2);
}
};
let program = match Program::new(&source) {
Ok(x) => x,
Err(UnbalancedBrackets(c, address)) => {
eprintln!(
"Error parsing file: didn't found pair for `{}` at instruction index {}",
c, address
);
return ExitCode::from(3);
}
};
let file_name = Path::new(&input_file).file_name().unwrap();
let output_file = PathBuf::from(&file_name).with_extension("o");
let obj = program.to_object();
std::fs::write(output_file, obj).unwrap();
ExitCode::from(0)
}
And if we run:
$ cargo run -p singlepass-compiler -- programs/factor.bf
Finished dev [unoptimized + debuginfo] target(s) in 0.03s
Running `target/debug/singlepass-compiler programs/factor.bf`
$ ld factor.o -o factor
$ ./factor
123456
123456: 2 2 2 2 2 2 3 643
It works!
Linking object files §
Now let’s take a look at linking multiple object files.
First let’s modify our hello world example to instead of calling the write
syscall directly, it will call a function defined in another file. So we
declared that my_write is an external symbol, and call it, passing the string
address and length as argument:
section .text
global _start
extern my_write
_start:
lea rdi, [rel hello] ; string to write
mov rsi, helloLen ; length of string to write
call my_write
; Terminate program
mov rax, 60 ; 'exit' system call = 60
mov rdi, 0 ; exit with error code 0
syscall ; call the kernel
hello: db 'Hello world!',10
helloLen: equ $-hello
And in a file called write.as, we declared my_write as global:
section .text
global my_write
my_write:
push rbp ; push rbp to keep the stack 16 bytes aligned, and
mov rbp, rsp ; also setup the stack frame.
mov rdx, rsi ; length of string to write
mov rsi, rdi ; string to write
mov rax, 1 ; 'write' system call = 1
mov rdi, 1 ; file descriptor 1 = STDOUT
syscall ; call the kernel
pop rbp
ret
If we assemble and link everything, we see that it continues to work:
$ nasm hello.as -f elf64 -o hello.o
$ nasm write.as -f elf64 -o write.o
$ ld hello.o write.o -o hello
$ ./hello
Hello world!
Now if we take a look at hello.o we will see that it now contains relocations:
$ readelf -r hello.o
Relocation section '.rela.text' at offset 0x300 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
00000000000d 000500000002 R_X86_64_PC32 0000000000000000 my_write - 4
The relocation is of type R_X86_64_PC32, which means that it writes a 32-bit
word whose value is the offset from the relocation to the given symbol. This is
because the call instruction receives an offset as argument.
But the call instruction receives an offset relative to the address of the next
instruction, so instead of writing S - P (symbol minus relocation address) it
should be written S - (P + 4), i.e., S - P - 4. So the relocation has an
addend of -4.
So let’s translate that new version of the code to our example compiler. The code now is:
let mut code: VecAssembler<X64Relocation> = VecAssembler::new(0);
let hello_str = b"Hello world!\n";
let len = hello_str.len() as i32;
let relocation_offset;
dynasm!(code
; lea rdi, [>hello] // string to write
; mov rsi, DWORD len // length of string to write
; call DWORD 0
;; relocation_offset = code.offset().0 as u64 - 4
// Terminate program
; mov eax,60 // 'exit' system call
; mov edi,0 // exit with error code 0
; syscall // call the kernel
; hello:
; .bytes hello_str
);
let code = code.finalize().unwrap();
As the address of my_write is unknown at this point, the call instruction
receives a dummy value for now and the offset where the relocation will take
place is saved in relocation_offset.
So, we when we are building the Object, we add the my_write symbol, and the
relocation. The new symbol is mostly equal to the other one, the only difference
is the name, and that we will not call add_symbol_data to it.
The relocation will have size of 32bits; its kind is Relative; in this
particular case the encoding don’t change anything, so I set it to Generic;
and I make sure to set the addend to -4, as we have seen previously:
let my_write = obj.add_symbol(Symbol {
name: b"my_write".to_vec(),
value: 0,
size: 0,
kind: object::SymbolKind::Text,
scope: object::SymbolScope::Linkage,
weak: false,
section: object::write::SymbolSection::Undefined,
flags: SymbolFlags::None,
});
let text = obj.section_id(object::write::StandardSection::Text);
obj.add_relocation(
text,
Relocation {
offset: relocation_offset,
size: 32,
kind: object::RelocationKind::Relative,
encoding: object::RelocationEncoding::Generic,
symbol: my_write,
addend: -4,
},
)
.unwrap();
If we run and link to write.o we see that it works!
$ cargo run -p object-example -- obj
Finished dev [unoptimized + debuginfo] target(s) in 0.03s
Running `../target/debug/object-example obj`
$ ld hello.o write.o
$ ./hello
Hello world!
But now, let’s try, instead of linking to an object written in assembly, link to a static lib written in Rust.
For this, let’s rewrite write.as as write.rs:
#[no_mangle]
pub extern "sysv64" fn my_write(address: *const u8, len: usize) {
let string = unsafe { std::slice::from_raw_parts(address, len) };
let string = std::str::from_utf8(string).unwrap();
print!("{}", string);
}
We need to add the attribute no_mangle to make sure that rustc don’t
mangle the name of the symbol for this function.
So we can compile the code to a static library using rustc (I didn’t bother
creating an entire cargo project for a single function):
$ rustc --crate-type=staticlib write.rs
This produces a libwrite.a, which is a static library. Static libraries are
basically an archive containing multiple object files (you can list them by
running ar -t libwrite.a).
Now we can try linking the library with our compiler object (make sure to put object files before the libraries that they depend on):
$ ld hello.o libwrite.a
If run the command above, you will notice that it will output almost 3000 lines of “undefined symbol” errors. That is because the Rust library that we build is static linked to the Rust standard library, that in turn depends on some libraries provided by the OS.
One way of fixing the error is by finding all libraries that define all the
missing symbols, and add them as argument to the linker. This is kinda tricky, I
am not even sure if this would work, and it will vary between Linux distros, so
let’s instead use gcc to link everything. It will already take care of linking
all system libraries.
The std also needs some extra static libraries. To get a list of them you can
pass --print=native-static-libs to the rustc invocation:
$ rustc --crate-type=staticlib write.rs --print=native-static-libs
note: Link against the following native artifacts when linking against this static library. The order and any duplication can be significant on some platforms.
note: native-static-libs: -lgcc_s -lutil -lrt -lpthread -lm -ldl -lc
$ gcc hello.o libwrite.a -o hello -nostartfiles -lgcc_s -lutil -lrt -lpthread -lm -ldl -lc
$ ./hello
Hello world!
And it works! Note that I need to pass -nostartfiles, because I am declaring
_start directly, instead of declaring a main function that would be called
by the C runtime.
A Static Compiler §
Now we can make the final version of our single-pass compiler. First, we create a library with all functions that we will use in our compiled brainfuck programs.
We will put them in a file called bf_lib.rs. There will be our read and
write function, and also a function for exiting. Also, these function will not
return errors, because there is no one to report them like in our JIT version.
Instead, they only print the error message and exit.
I will also prefix each function with bf_ to avoid symbol conflicts:
use std::io::{Read, Write};
#[no_mangle]
pub extern "sysv64" fn bf_write(value: u8) {
// Writing a non-UTF-8 byte sequence on Windows error out.
if cfg!(target_os = "windows") && value >= 128 {
return;
}
let mut stdout = std::io::stdout().lock();
let result = stdout.write_all(&[value]).and_then(|_| stdout.flush());
if let Err(err) = result {
eprintln!("IO error: {}", err);
std::process::exit(1);
}
}
#[no_mangle]
pub unsafe extern "sysv64" fn bf_read(buf: *mut u8) {
let mut stdin = std::io::stdin().lock();
loop {
let mut value = 0;
let err = stdin.read_exact(std::slice::from_mut(&mut value));
if let Err(err) = err {
if err.kind() != std::io::ErrorKind::UnexpectedEof {
eprintln!("IO error: {}", err);
std::process::exit(1);
}
value = 0;
}
// ignore CR from Window's CRLF
if cfg!(target_os = "windows") && value == b'\r' {
continue;
}
*buf = value;
break;
}
}
#[no_mangle]
pub unsafe extern "sysv64" fn bf_exit() {
std::process::exit(0);
}
Now in our compiler, we will call these functions instead of the syscall. We need to register the relocations for each call.
So Program becomes:
struct Program {
code: Vec<u8>,
write_relocations: Vec<usize>,
read_relocations: Vec<usize>,
exit_relocation: usize,
}
And the compilation:
let mut write_relocations = Vec::new();
let mut read_relocations = Vec::new();
b'.' => dynasm! { code
; .arch x64
; mov rdi, [r12 + r13] // cell value
; call DWORD 0
;; write_relocations.push(code.offset().0 - 4)
},
b',' => dynasm! { code
; .arch x64
; lea rdi, [r12 + r13] // cell address
; call DWORD 0
;; read_relocations.push(code.offset().0 - 4)
},
let exit_relocation;
dynasm! { code
; .arch x64
; call DWORD 0
;; exit_relocation = code.offset().0 - 4
}
Ok(Program {
code: code.finalize().unwrap(),
write_relocations,
read_relocations,
exit_relocation,
})
And we make sure to write these relocations on the generated object:
fn to_elf_object(&self) -> Vec<u8> {
let mut obj = object::write::Object::new(
object::BinaryFormat::Elf,
object::Architecture::X86_64,
object::Endianness::Little,
);
let mut add_symbol = |name: &[u8]| {
obj.add_symbol(Symbol {
name: name.to_vec(),
value: 0,
size: 0,
kind: object::SymbolKind::Text,
scope: object::SymbolScope::Linkage,
weak: false,
section: object::write::SymbolSection::Undefined,
flags: SymbolFlags::None,
})
};
let start = add_symbol(b"_start");
let bf_write = add_symbol(b"bf_write");
let bf_read = add_symbol(b"bf_read");
let bf_exit = add_symbol(b"bf_exit");
let text = obj.section_id(object::write::StandardSection::Text);
obj.add_symbol_data(start, text, &self.code, 16);
let mut add_call_reloc = |offset, symbol| {
obj.add_relocation(
text,
Relocation {
offset: offset as u64,
symbol,
size: 32,
kind: object::RelocationKind::Relative,
encoding: object::RelocationEncoding::Generic,
addend: -4,
},
)
.unwrap();
};
for offset in self.read_relocations.iter().copied() {
add_call_reloc(offset, bf_read);
}
for offset in self.write_relocations.iter().copied() {
add_call_reloc(offset, bf_write);
}
add_call_reloc(self.exit_relocation, bf_exit);
let mut out = Vec::new();
obj.emit(&mut out).unwrap();
out
}
Now if we compile everything:
$ cargo run -p singlepass-compiler -- ../programs/factor.bf
Finished dev [unoptimized + debuginfo] target(s) in 0.03s
Running `../target/debug/singlepass-compiler programs/factor.bf`
$ rustc --crate-type=staticlib bf_lib.rs
$ gcc factor.o libbf_lib.a -nostartfiles -pthread -ldl -o factor
$ ./factor
123456
123456: 2 2 2 2 2 2 3 643
It works! Cool!
A Windows Port §
Following the spirit of the precious parts, let’s now try porting our compiler to Windows!
At first, it is very straightforward. In the compiler, we need to tell object to
crate a COFF object file on Windows, and we also need to replace the symbol
_start by WinMain, which is the one used as entry point on Windows.
let (format, entry_name) = if cfg!(target_os = "windows") {
(object::BinaryFormat::Coff, "WinMain")
} else if cfg!(target_os = "linux") {
(object::BinaryFormat::Elf, "_start")
} else {
unimplemented!("Only Linux and Windows are implemented")
};
let entry_name = entry_name.as_bytes();
let mut obj = object::write::Object::new(
format,
object::Architecture::X86_64,
object::Endianness::Little,
);
let mut add_symbol = |name: &[u8]| { /* ... */ };
let start = add_symbol(entry_name);
// ...
Then, if we use the x86_64-pc-windows-gnu target, we can continue to link our
objects with GCC:
> rustc --crate-type staticlib bf_lib.rs --target=x86_64-pc-windows-gnu
> cargo run -p singlepass-compiler -- ../programs/factor.bf
Finished dev [unoptimized + debuginfo] target(s) in 0.17s
Running `..\target\debug\singlepass-compiler.exe ../programs/factor.bf`
> gcc -o factor.exe factor.o libbf_lib.a -nostartfiles -ladvapi32 -luserenv -lkernel32 -lkernel32 -lws2_32 -lbcrypt
> factor.exe
If you test the executable now, you may notice that nothing happens. And if you open it on a debugger, you will notice that it is actually crashing on an access violation when clearing the first byte of the memory.
What is happening here is that, on Windows, only part of the reserved stack space is actually committed. When I tested it, for example, there were only 12 KiB of accessible space on the stack.
But at the end of the committed stack, there are guard pages, that whenever they are accessed, more pages are allocated for the stack. Pages have a size of 4096 bytes, but we are allocating 30000 bytes on the stack, which is causing us to miss the guard page, and access uncommitted memory.
The fix for this is very simple, we only need to make sure to not miss the guard page. An easy change is to start clearing our memory at the bottom end of the stack:
dynasm! { code
; .arch x64
; push rbp
; mov rbp, rsp
; xor r13, r13
// allocate 30_0000 bytes on stack for the memory
; sub rsp, 30_000
; mov r12, rsp
// zero the memory
; xor eax, eax
; mov r11, rbp
; loop_:
; add r11, -8
; mov QWORD [r11], rax
; cmp r11, r12
; jne <loop_
};
If we test our program now:
> rustc --crate-type staticlib bf_lib.rs --target=x86_64-pc-windows-gnu
> cargo run -p singlepass-compiler -- ../programs/factor.bf -o
Finished dev [unoptimized + debuginfo] target(s) in 0.17s
Running `..\target\debug\singlepass-compiler.exe ../programs/factor.bf`
> gcc -o factor.exe factor.o libbf_lib.a -nostartfiles -ladvapi32 -luserenv -lkernel32 -lkernel32 -lws2_32 -lbcrypt
> factor.exe
123456
123456: 2 2 2 2 2 2 3 643
It works!
We can also use the msvc tool chain. If we open a “Developer Command Prompt
for VS 22” (I have the Visual Studio 2022 installed), we can run the following:
> rustc --crate-type staticlib bf_lib.rs --target=x86_64-pc-windows-msvc -Copt-level=2 -Clto -Cpanic=abort
> link /subsystem:console /entry:WinMain advapi32.lib advapi32.lib userenv.lib kernel32.lib kernel32.lib ws2_32.lib bcrypt.lib msvcrt.lib vcruntime.lib factor.o bf_lib.lib
Microsoft (R) Incremental Linker Version 14.33.31629.0
Copyright (C) Microsoft Corporation. All rights reserved.
bf_lib.lib(bf_lib.bf_lib.58e9fd71-cgu.2.rcgu.o) : warning LNK4210: .CRT section exists; there may be unhandled static initializers or terminators
msvcrt.lib(tlssup.obj) : warning LNK4210: .CRT section exists; there may be unhandled static initializers or terminators
bf_lib.lib(bf_lib.bf_lib.58e9fd71-cgu.2.rcgu.o) : warning LNK4210: .CRT section exists; there may be unhandled static initializers or terminators
msvcrt.lib(tlssup.obj) : warning LNK4210: .CRT section exists; there may be
unhandled static initializers or terminators
> factor.exe
123456
123456: 2 2 2 2 2 2 3 643
I needed to include vcruntime.lib, even though --print=static-native-libs
didn’t report that it was used. Even so, there were some unresolved symbols, but
thankfully by setting panic=abort, enabling LTO and increasing the
optimization level, these symbols have gone away.
It still outputs some warnings about unhandled static initializers, but thankfully our program don’t need them (I think), and everything works!
Future work §
In this post we have seen the basic of object files, and how compile our programs to them, and them link them. But we only covered the very basic of this. There still things that we didn’t cover, like dynamic libraries, position independent executables, debug information, etc.
Also, all these file formats are system dependent, and the relocations in them vary greatly between architectures, so we again fall in the same problem that we discussed in the end of part 2. Thankfully code generators, like LLVM, also covers these problems.
A natural next step here would be to try exactly that using the Cranelift JIT
compiler that we made in the last part as basis. You can use
cranelift-module and cranelift-object to do that.
But this will be the last part of this blog post series. There is much more to explore on compilation, but brainfuck is too simple a language for them to be need.
But hopefully, these series has taught you at least the basics to let you be able to start writing your own compilers if the will ever came.
All the code developed during these series can be found here (but it may not contain the exactly snippets showed here).
-
Actually, on Linux, fresh allocated stack for a process is initially zeroed, and because we are the first function being executed (we are at the entry point) we can make sure that the memory is already clear. But I cleared it anyway, because it will be useful when we port this compiler to Windows. ↩