Previously in emulator basics: <! forgive me, for I have sinned >
1. a stack and register machine

In this post we'll extend x86e to support the exit and write Linux system calls, or syscalls. A syscall is a function handled by the kernel that allows the process to interact with data outside of its memory. The SYSCALL instruction takes arguments in the same order that the regular CALL instruction does. But SYSCALL additionally requires the RAX register to contain the integer number of the syscall.

Historically, there have been a number of different ways to make syscalls. All methods perform variations on a software interrupt. Before AMD64, on x86 processors, there was the SYSENTER instruction. And before that there was only INT 80h to trigger the interrupt with the syscall handler (since interrupts can be used for more than just syscalls). The various instructions around interrupts have been added for efficiency as the processors and use by operating systems evolved.

Since this is a general need and AMD64 processors are among the most common today, you'll see similar code in every modern operating system such as FreeBSD, OpenBSD, NetBSD, macOS, and Linux. (I have no background in Windows.) The calling convention may differ (e.g. which arguments are in which registers) and the syscall numbers differ. Even within Linux both the calling convention and the syscall numbers differ between x86 (32-bit) and AMD64/x86_64 (64-bit) versions.

See this StackOverflow post for some more detail.

Code for this post in full is available as a Gist.

Exit

The exit syscall is how a child process communicates with the process that spawned it (its parent) when the child is finished running. Exit takes one argument, called the exit code or status code. It is an arbitrary signed 8-bit integer. If the high bit is set (i.e. the number is negative), this is interpreted to mean the process exited abnormally such as due to a segfault. Shells additionally interpret any non-zero exit code as a "failure". Otherwise, and ignoring these two common conventions, it can be used to mean anything the programmer wants.

The wait syscall is how the parent process can block until exit is called by the child and receive its exit code.

On AMD64 Linux the syscall number is 60. For example:

  MOV RDI, 0
  MOV RAX, 60
  SYSCALL

This calls exit with a status code of 0.

Write

The write syscall is how a process can send data to file descriptors, which are integers representing some file-like object. By default, a Linux process is given access to three file descriptors with consistent integer values: stdin is 0, stdout is 1, and stderr is 2. Write takes three arguments: the file descriptor integer to write to, a starting address to memory that is interpreted as a byte array, and the number of bytes to write to the file descriptor beginning at the start address.

On AMD64 Linux the syscall number is 1. For example:

  MOV RDI, 1   ; stdout
  MOV RSI, R12 ; address of string
  MOV RDX, 8   ; 8 bytes to write
  MOV RAX, 1   ; write
  SYSCALL

This writes 8 bytes to stdout starting from the string whose address is in R12.

Implementing syscalls

Our emulator is simplistic and is currently only implementing process emulation, not full CPU emulation. So the syscalls themselves will be handled in JavaScript. First we'll write out stubs for the two syscalls we are adding. And we'll provide a map from syscall id to the syscall.

const SYSCALLS_BY_ID = {
  1: function sys_write(process) {},
  60: function sys_exit(process) {},
};

We need to add an instruction handler to our instruction switch. In doing so we must convert the value in RAX from a BigInt to a regular Number so we can look it up in the syscall map.

      case 'syscall': {
        const idNumber = Number(process.registers.RAX);
        SYSCALLS_BY_ID[idNumber](process);
        process.registers.RIP++;
        break;
      }

Exit

Exit is really simple. It will be implemented by calling Node's global.process.exit(). Again we'll need to convert the register's BigInt value to a Number.

const SYSCALLS_BY_ID = {
  1: function sys_write(process) {},
  60: function sys_exit(process) {
    global.process.exit(Number(process.registers.RDI));
  },
};

Write

Write will be implemented by iterating over the process memory as bytes and by calling write() on the relevant file descriptor. We'll store a map of these on the process object and supply stdout, stderr, and stdin proxies on startup.

function main(file) {
  ...

  const process = {
    registers,
    memory,
    instructions,
    labels,
    fd: {
      // stdout
      1: global.process.stdout,
    }
  };

  ...
}

The base address is stored in RSI, the number of bytes to write are stored in RDX. And the file descriptor to write to is stored in RDI.

const SYSCALLS_BY_ID = {
  1: function sys_write(process) {
    const msg = BigInt(process.registers.RSI);
    const bytes = Number(process.registers.RDX);
    for (let i = 0; i < bytes; i++) {
      const byte = readMemoryBytes(process, msg + BigInt(i), 1);
      const char = String.fromCharCode(Number(byte));
      process.fd[Number(process.registers.RDI)].write(char);
    }
  },
  ...

All together

$ cat exit3.asm
main:
  MOV RDI, 1
  MOV RSI, 2
  ADD RDI, RSI

  MOV RAX, 60 ; exit
  SYSCALL
$ node emulator.js exit3.asm
$ echo $?
3

$ cat hello.asm
main:
  PUSH 10  ; \n
  PUSH 33  ; !
  PUSH 111 ; o
  PUSH 108 ; l
  PUSH 108 ; l
  PUSH 101 ; e
  PUSH 72  ; H

  MOV RDI, 1   ; stdout
  MOV RSI, RSP ; address of string
  MOV RDX, 56  ; 7 8-bit characters in the string but PUSH acts on 64-bit integers
  MOV RAX, 1   ; write
  SYSCALL

  MOV RDI, 0
  MOV RAX, 60
  SYSCALL
$ node emulator.js hello.asm
Hello!
$

Next steps

We still aren't setting flags appropriately to support conditionals, so that's low-hanging fruit. There are some other fun syscalls to implement that would also give us access to an emulated VGA card so we could render graphics. Syntactic support for string constants would also be convenient and more efficient.

Latest post in the emulator basics series up: implementing some syscalls starting with sys_exit and sys_write so we can print a nice hello message. https://t.co/NEfId0lnJx #javascript #x86

— Phil Eaton (@phil_eaton) July 20, 2019

Previously in compiler basics: <! forgive me, for I have sinned >
1. lisp to assembly
2. user-defined functions and variables
3. LLVM
4. LLVM conditionals and compiling fibonacci
Next in compiler basics:
5. an x86 upgrade

In this post we'll extend the ulisp compiler's LLVM backend to support printing integers to stdout.

Exit code limitations

Until now we've validated program state by setting the exit code to the result of the program computation. But the exit code is an eight bit integer. What if we want to validate a computation that produces a result larger than 255?

To do this we need a way to print integers. This is challenging because printing normally deals with byte arrays. libc's printf, for example, takes a byte array as its first argument.

The shortest path forward is to add support for system calls so we can print one character at a time. Here's a version of a print form that hacks around not having arrays to send each integer in a number to stdout.

(def print-char (c)
     ; First argument is stdout
     ; Second argument is a pointer to a char array (of length one)
     ; Third argument is the length of the char array
     (syscall/sys_write 1 &c 1))

(def print (n)
     (if (> n 9)
         (print (/ n 10)))

     ; 48 is the ASCII code for '0'
     (print-char (+ 48 (% n 10))))

In order to support this we need to add the syscall/sys_write, >, %, and / builtin forms. We'll also need to add support for taking the address of a variable.

All code is available on Github as is the particular commit related to this post.

References

The sys_write syscall requires us to pass the memory address of the byte array to write. We don't support arrays, but we can treat an individual variable as an array of length one by passing the variable's address.

If we were compiling to C we could just pass the address of a local variable. But LLVM doesn't allow us to take the address of variables directly. We need to push the variable onto the LLVM stack to get an address.

Under the hood LLVM will likely optimize this into a local variable reference instead of first pushing to the stack.

Since LLVM IR is typed, the value representing the address of a local variable will be a pointer type. We'll need to refer to all uses of this value as a pointer. So we'll need to modify ulisp to track local types rather than hard-coding i64 everywhere.

Scope

To begin we'll modify the Scope class to track types. We only need to do this on registration. Afterward, we'll have to find all uses of local variables to make sure they use the local's value and type fields appropriately.

class Scope {

  ...

  register(local) {
    let copy = local.replace('-', '_');
    let n = 1;
    while (this.locals[copy]) {
      copy = local + n++;
    }

    this.locals[local] = {
      value: copy,
      type: 'i64',
    };
    return this.locals[local];
  }

  ...

}

We won't go through every use of a Scope variable in this post, but you can find it in the related commit to ulisp.

Reference

The long-term approach for handling a reference syntactically is probably to rewrite &x to (& x) in the parser. The lazy approach we'll take for now is to handle a reference as a special kind of identifier in compileExpression.

We'll use the LLVM alloca instruction to create space on the stack. This will return a pointer and will turn the destination variable into a pointer type. Then we'll use store to set the value at the address to the current value of the variable being referenced.

class Compiler {

  ...

  compileExpression(exp, destination, context) {

    ...

    // Is a reference, push onto the stack and return its address
    if (exp.startsWith('&')) {
      const symbol = exp.substring(1);
      const tmp = context.scope.symbol();
      this.compileExpression(symbol, tmp, context);
      this.emit(1, `%${destination.value} = alloca ${tmp.type}, align 4`);
      destination.type = tmp.type + '*';
      this.emit(1, `store ${tmp.type} %${tmp.value}, ${destination.type} %${destination.value}, align 4`);
      return;
    }

    ...

  }

  ...

}

And now we're set to take the address of any code.

System calls

LLVM IR provides no high-level means for making system calls. The only way is to use inline assembly. This syntax is based on GCC inline assembly and is confusing, with few explained examples, and unhelpful error messages.

Thankfully the assembly code needed for a syscall is only one line, one word: the syscall assembly instruction. We use inline assembly variable-to-register mapping functionality to line up all the parameters for the syscall. Here is an example:

%result = call i64 asm sideeffect "syscall", "=r,{rax},{rdi},{rsi},{rdx}" (i64 %raxArg, i64 %rdiArg, i64 %rsiArg, i64 %rdxArg)

This says to execute the inline assembly string, "syscall". The sideeffect flag means that this assembly should always be run even if the result isn't used. =r means the inline assembly returns a value, and the rest of the string is the list of registers that arguments should be mapped to. Finally we call the function with all the LLVM variables we want to be mapped.

Eventually we should also use the inline assembly syntax to list registers that are modified so that LLVM can know to save them before and after.

Code

We'll add a mapping for syscall/sys_write and a helper function for generating syscall code using the example above as a template. We'll suport 64-bit Darwin and Linux kernels.

const SYSCALL_TABLE = {
  darwin: {
    sys_write: 0x2000004,
    sys_exit: 0x2000001,
  },
  linux: {
    sys_write: 1,
    sys_exit: 60,
  },
}[process.platform];

class Compiler {
  constructor() {
    this.outBuffer = [];
    this.primitiveFunctions = {
      def: this.compileDefine.bind(this),
      begin: this.compileBegin.bind(this),
      'if': this.compileIf.bind(this),
      '+': this.compileOp('add'),
      '-': this.compileOp('sub'),
      '*': this.compileOp('mul'),
      '%': this.compileOp('urem'),
      '<': this.compileOp('icmp slt'),
      '=': this.compileOp('icmp eq'),
      'syscall/sys_write': this.compileSyscall(SYSCALL_TABLE.sys_write),
    };
  }

  ...

  compileSyscall(id) {
    return (args, destination, context) => {
      const argTmps = args.map((arg) => {
          const tmp = context.scope.symbol();
          this.compileExpression(arg, tmp, context);
          return tmp.type + ' %' + tmp.value;
      }).join(', ');
      const regs = ['rdi', 'rsi', 'rdx', 'r10', 'r8', 'r9'];
      const params = args.map((arg, i) => `{${regs[i]}}`).join(',');
      const idTmp = context.scope.symbol().value;
      this.emit(1, `%${idTmp} = add i64 ${id}, 0`)
      this.emit(1, `%${destination.value} = call ${destination.type} asm sideeffect "syscall", "=r,{rax},${params},~{dirflag},~{fpsr},~{flags}" (i64 %${idTmp}, ${argTmps})`);
    }
  }
}

>, /

Finally, we have a few new operations to add support for. But they'll be pretty simple using the compileOp helper function.

class Compiler {
  constructor() {
    this.outBuffer = [];
    this.primitiveFunctions = {
      def: this.compileDefine.bind(this),
      begin: this.compileBegin.bind(this),
      'if': this.compileIf.bind(this),
      '+': this.compileOp('add'),
      '-': this.compileOp('sub'),
      '*': this.compileOp('mul'),
      '/': this.compileOp('udiv'),
      '%': this.compileOp('urem'),
      '<': this.compileOp('icmp slt'),
      '>': this.compileOp('icmp sgt'),
      '=': this.compileOp('icmp eq'),
      'syscall/sys_write': this.compileSyscall(SYSCALL_TABLE.sys_write),
    };
  }

  ...

}

print

We're ready to give our print function a shot.

$ cat test.lisp
(def print-char (c)
     ; First argument is stdout
     ; Second argument is a pointer to a char array (of length one)
     ; Third argument is the length of the char array
     (syscall/sys_write 1 &c 1))

(def print (n)
     (if (> n 9)
         (print (/ n 10)))

     ; 48 is the ASCII code for '0'
     (print-char (+ 48 (% n 10))))

(def main ()
     (print 1234)
     0)
$ node ulisp.js test.lisp
$ ./build/a.out
1234

Looks good! In the next post we'll talk about tail call elimination.

It's been a slow month for the blog. But new post on compiler basics is up! Printing integers to stdout and making syscalls in LLVM (all without arrays). This was a pre-req for playing with tail-call elimination (post coming soon) https://t.co/fDtblUZRI8

— Phil Eaton (@phil_eaton) June 23, 2019