DEV Community: tyfkda

Running a C compiler in a browser

tyfkda — Fri, 05 Feb 2021 09:05:59 +0000

My own C compiler is designed for x86-64 and outputs ELF64 binary. My plan was that if I could output code that could run on x86-64, I could run it on my home computer, and I would be able to do this for the next 10 years. However, with the emergence of various processors, it seems that x86 may not remain the mainstream.

I also experienced the ability to compile code written in Rust to WASM and run it in a browser. I was quite surprised to find out that I can run code written in a language that can do low-level things like memory manipulation with pointers in a browser. I was quite surprised.

So I thought I'd try to make it possible to output wasm from the C compiler.

Online Demo

Architecture of WASM

I looked up the architecture of WASM a while ago, and the features are as follows:

Stack machine instruction set (no registers)
Local variables can be used
Only i32, i64, f32, f64 types are supported (not even strings)
Jumps can only be control-syntactic jumps (out of a block or back in a loop), not to a label (address)
There is no GC.

As for the data types that can be handled, there are no useful ones such as objects or strings, only byte array that can be manipulated, but I think this is a sufficient level to bring from a language specification of the level of C.

Policy for outputting WASM binaries from a C compiler

The original compiler was designed to convert to a register machine instruction set:

Front end (parser): C source -> Abstract Syntax Tree (AST)
Middle end (intermediate representation): AST -> Intermediate Representation (IR)
Backend: IR -> x86-64 binary (ELF64 format)

It would be nice to be able to switch the output target by sharing the middle end and replacing the backend, but it's a bit difficult.

In the middle end, jumps are converted to basic blocks, and finally to label jumps. However, in WASM, the jump is a control structure, and you can't place a label at an arbitrary point and make it jump. So if we want to do this, we need to recover the control structure from the label jump. It may be possible to recover the control structure by analyzing the control flow graph, but I don't think it's easy.

There are some other points that seem troublesome.

The calculation of the expression has been converted to an operation in three-address code between virtual registers, and it needs to be converted back to the stack machine method.

Since the AST stage can be used as-is, I decided to share only the front-end and output the wasm binary directly from the AST.

A few implementation points

Handling of local variables other than numeric types

WASM can only handle 32/64 bit integer/floating-point number types as local variables, not structures or arrays. What to do is to store them in linear memory.

It is necessary to manage which part of the linear memory to use by yourself. Therefore, we need to prepare a global variable that represents the stack pointer, store it in a local variable that represents the base pointer at the beginning of a function, modify the stack pointer, and then restore it when we exit.

If a reference is taken by & even if it is a numeric type, it is necessary to be able to rewrite it via the pointer, so it cannot be a local variable and should be placed in linear memory.

Returning from the middle of a function

When exiting with a value by return from the middle of a function, a real processor such as x86 will return to the caller with a value in the rax register according to ABI. In WASM, it is also possible to exit from a function and return the top of the stack with the return instruction, but there are cases where it is necessary to restore the stack pointer as described in the previous paragraph, so I want to unify the process of exiting from a function (epilogue).

In this case, we cannot use return from the middle of the function, so we need to prepare a local variable to store the return value, store it in the variable, jump to the epilogue, process the epilogue, retrieve the return value, and return it.

Handling of assignment expressions

In C language, assignment is an expression, so it can be connected to multiple expressions or mixed with other expressions. However, in WASM, storing a value in a local variable (local.set) or in linear memory (i32.store) removes the value from the top of the stack. Since there is no instruction like dup to duplicate the value on the stack, it is not possible to keep the assigned value (although it is possible to keep the value of a local variable while storing it with the local.tee instruction).

Therefore, the assignment expression is treated as void, and the value cannot keep alive. If the value of the assignment expression is still to be used, a local variable is allocated internally and converted to a comma expression (l = r is converted to ((void)(tmp = r), (void)(l = tmp), tmp)).

Switch statement

In WASM, only structured jumps are possible, but how to implement a switch statement? I was wondering how to implement the switch statement, but it was nothing, I just had to nest as many blocks as the number of cases and br each one.

There is also an instruction called br_table, which allows you to do table jumps instead of br_if in order (I haven't tried it).

Variable Length Arguments

The number of arguments of a function and their types must be fixed in WASM. As for how to handle variable-length arguments, we'll pass them in linear memory. We can internally pass function arguments to ... Internally, convert the function argument to the argument before ... + pointer to store the variable length arguments.

Pointer length

The pointer is treated as an offset in the linear memory, but since the offset is u32, the pointer should be 32 bits long. Therefore, I decided to use sizeof(void*) == sizeof(long) == sizeof(int) == 4. The data type model is called ILP32. i64 will be handled as a long long.

It is recommended to have the __ILP32__ macro pre-defined so that the code can determine this.

Function call using function pointer

In WASM, normal function call is not by name or label, but by an index that is assigned to the function in order. In order to handle function pointer, it was not possible to do so by using the index.

You need to register the function you want to handle as a function pointer in a table, and use that index.

Old Function Prototype Declarations

In the prototype declarations of functions in the old C language, parameters can be omitted. In that case, the function is compiled assuming that the type of the argument given by the caller matches the entity, and if it does not, it will malfunction.

In WASM, if the type or number of arguments of the function to be called is not correct, a runtime error will occur, so make it an error at compile time.

Runtime Environment

One of the advantages of compiling to binary is that you don't have to write a runtime because everything is resolved at compile time. However, this does not mean that the standalone executable is truly independent, but rather depends on the OS system calls.

In the same way, the world of wasm binaries only allows computations, so if you want to communicate with the outside world, you need to prepare a call equivalent to a system call. From wasm, it can be executed as a call to an imported function. Prepare functions such as open and read that are equivalent to unistd and make them available.

Running in a browser

As usual, if you compile the source of the compiler itself, you can get a compiler that runs as WebAssembly, which is self-hosting. It's interesting to note that cross-compilation is included this time:

C compiler source (wcc.c) → gcc on Mac → C compiler running on Mac that can emit wasm (wcc on Mac)
C compiler source (wcc.c) → wcc on Mac → C compiler running on wasm that can emit wasm (wcc on wasm)
Prepare a runtime and run wcc on wasm in a browser.

Just by enabling the C compiler to emit wasm, you've got a C compiler that automatically runs on your browser! This is a good deal.

After that, I'll make up a file system, and incorporate Ace editor as a text editor that runs in the browser, so that I can compile and execute with a button.

Problems

Some of the problems with WASM, not necessarily on the browser, are

Asynchronous processing is not possible.
You can't wait until something is done synchronously, because you can't explicitly give away the process.
Cannot fork a process
Cannot do global escaping

In JavaScript, asynchronous processing is possible with Promise, but it is currently not possible with wasm. If I had to do it, I'd separate functions in the middle and let them sleep the process once... but that's not possible in places where function calls are nested.

If you can't do global escaping, you can't handle exceptions, which is fine in C and Rust, but how do you handle exceptions in C++?

Unimplemented features

Jumps with goto are not supported because they cannot be easily converted to structural jumps. Disabling goto is not enough, but looping over a case inside a switch breaks the structure (Duff's device), so it is not supported.

Others: passing/returning values of structs, compound literals.

Impressions

I thought it would be interesting to be able to run code written in C on a browser, but then I realized that there is no need for me to go through the trouble of coding in C on a browser... orz

jp: https://tyfkda.github.io/blog/2021/02/04/c-on-browser.html

Implement `pwd` command on xv6

tyfkda — Thu, 07 Jun 2018 14:19:26 +0000

I just started playing with xv6, re-implementation of Unix version 6. It can easily build and run.

I thought implementing some command is a good practice, so I decided to add simple one, pwd. It can be made in pure user land, and no additional system call required.

Extract file information on xv6

Referring to ls.c, you can extract file information (struct stat) using stat function.

You can also enumerate directory entries calling open function with directory path, read contents as struct dirent.

Find absolute path

I am not familiar with concept of Unix, so looking for the code, and it seems struct inode (and its inum, inode number) is the key part for the file system. But interestingly, it doesn't have its file name. To get file name, you have to enumerate its directory and search for inum.

To get absolute path, you have to get file name recursively, until reach to the root.

Code

Here is the main function:

#include "types.h"
#include "fcntl.h"
#include "fs.h"
#include "stat.h"
#include "user.h"

#define NULL   ((void*)0)
#define FALSE  (0)
#define TRUE   (1)

#define PATH_SEPARATOR   "/"

static int getcwd(char* resultPath);
static char* goUp(int ino, char* ancestorPath, char* resultPath);
static int dirlookup(int fd, int ino, char* p);

int main(int argc, char *argv[]) {
  char resultPath[512];
  if (getcwd(resultPath))
    printf(1, "%s\n", resultPath);
  else
    printf(2, "pwd failed");
  exit();
}

getcwd function returns current working directory to the given buffer:

static int getcwd(char* resultPath) {
  resultPath[0] = '\0';

  char ancestorPath[512];
  strcpy(ancestorPath, ".");

  struct stat st;
  if (stat(ancestorPath, &st) < 0)
    return FALSE;

  char* p = goUp(st.ino, ancestorPath, resultPath);
  if (p == NULL)
    return FALSE;
  if (resultPath[0] == '\0')
    strcpy(resultPath, PATH_SEPARATOR);
  return TRUE;
}

ancestorPath holds relative path to ancestors. It becomes ".", "./..", "./../..", ... and is used to pass to stat function.

goUp function goes to parent directory for ancestorPath, and find the absolute path, recursively:

static char* goUp(int ino, char* ancestorPath, char* resultPath) {
  strcpy(ancestorPath + strlen(ancestorPath), PATH_SEPARATOR "..");
  struct stat st;
  if (stat(ancestorPath, &st) < 0)
    return NULL;

  if (st.ino == ino) {
    // No parent directory exists: must be the root.
    return resultPath;
  }

  char* foundPath = NULL;
  int fd = open(ancestorPath, O_RDONLY);
  if (fd >= 0) {
    char* p = goUp(st.ino, ancestorPath, resultPath);
    if (p != NULL) {
      strcpy(p, PATH_SEPARATOR);
      p += sizeof(PATH_SEPARATOR) - 1;

      // Find current directory.
      if (dirlookup(fd, ino, p))
        foundPath = p + strlen(p);
    }
    close(fd);
  }
  return foundPath;
}

Even if you are at the root directory, you can get stat for the parent direcotry without error (and you can cd ..). It seems you have to detect you are at the root if parent's and current directory's ino are same.

dirlookup function finds file name for the given inode number from its parent directory:

// @param fd   file descriptor for a directory.
// @param ino  target inode number.
// @param p    [out] file name (part of absPath), overwritten by the file name of the ino.
static int dirlookup(int fd, int ino, char* p) {
  struct dirent de;
  while (read(fd, &de, sizeof(de)) == sizeof(de)) {
    if (de.inum == 0)
      continue;
    if (de.inum == ino) {
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = '\0';
      return TRUE;
    }
  }
  return FALSE;
}

Build and add to file image

You can easily add your extra command to image file on xv6 . Modify UPROGS in Makefile with naming convention, add _pwd to it.

Test

$ pwd
/
$ mkdir foo
$ mkdir foo/bar
$ cd foo/bar
$ /pwd
/foo/bar

I stumbled using pwd at /foo/bar. It seems xv6 doesn't have environment variables, and search path in a shell:

$ pwd  # <= without '/' causes exec error, because cannot find the command.
exec: fail
exec pwd failed

You have to add / to point exact command path on xv6.