A Standard Library for Qute

Qute is a software analysis framework for QBE. Since it executes software in the QBE intermediate representation, libraries used by the software (including the standard library) must also be available in that form. This post describes how a C standard library can be supplied using Qute.

Linking QBE Sources

Previously, for executing Hare software, I have simply concatenated the required QBE representation of standard library source files. This, however, does not scale, as these source files may define identical, non-exported symbols (e.g., helper functions). When combining such QBE sources into one file, the symbol names become ambiguous, and it is—for example—unclear which helper function an overloaded symbol refers to. To fix that, the non-exported symbols must be scoped—or, in other words, unique—on a translation unit basis.

LLVM provides a llvm-link tool for this purpose, which combines multiple LLVM IR source files into a single file:

$ cat 1.c
#include <stdio.h>
static const char *something = "foo";
void one(void) { puts(something); }
$ cat 2.c
#include <stdio.h>
static const char *something = "bar";
void two(void) { puts(something); }
$ clang -S -emit-llvm 1.c
$ clang -S -emit-llvm 2.c
$ llvm-link -S -o linked.ll 1.ll 2.ll

Both C source files define the non-exported something symbol. In order to resolve the ambiguity with respect to that symbol, it is renamed the second time it is defined and all uses of this symbol in the second translation unit are updated:

$ grep '@something' linked.ll
@something = internal global ptr @.str, align 8
@something.1 = internal global ptr @.str.2, align 8
  %1 = load ptr, ptr @something, align 8
  %1 = load ptr, ptr @something.1, align 8

In commit 73bc25e, I implemented a similar approach for QBE source files in Qute. This commit adds a Language.QBE.Linker Haskell module. The entry point of that module is the link function, which combines a list of QBE source files into a single source file. Internally, it tracks defined symbols and appends a suffix to already-defined symbols on a translation unit basis. With the QBE linker, we can safely combine multiple QBE sources into a single file.

QBE Archives

Additionally, to more easily integrate with the build systems of existing software, it is useful to provide a unified file format for libraries. Otherwise, the QBE representation of the application code must always be concatenated with all utilized libraries before it can be analyzed using Qute.

In the C world—at least for static libraries—the ar(5) file format is used for this purpose. This format is a generic archive format that, for the C use case, contains compiled object files. Since it is just a generic archive format, we can use it with Qute by creating ar(5) archives containing QBE source files instead of object files.

In commit d6ef81, I implemented a parser for the ar(5) format as described by OpenBSD and FreeBSD. Unfortunately, the ar(5) format has never been standardized.¹ Therefore, different ar(1) implementations emit different ar(5) formats. However, except for the handling of file names with spaces, the formats are commonly compatible with each other. As such, Qute can now load library code as .ar archives.

The SCC libc

Now that we have a format, we can make software libraries compatible with Qute. For C software, the C standard library is the most important one that we need first. The challenging part with respect to supporting that in Qute is the handling of system calls emitted by this library. Ideally, these should be intercepted by Qute and handled according to an environment model.

However, system calls cannot be expressed with the QBE intermediate representation. Instead, they are usually implemented through assembly files, which are then linked with the compiled QBE sources. Therefore, a closer integration of Qute and a specific C standard library is needed to intercept selected functions (i.e., the interface for kernel interactions) and emulate their behavior in Qute.

A suitable target for this integration is the libc provided by the SCC toolchain project. This project also provides a QBE-based C compiler frontend; hence, the individual C source files can be easily compiled to an equivalent QBE representation. Further, retargeting SCC’s libc “requires implementing less than 10 primitives” (i.e., syscalls). As such, I started working on a Qute libc target in an SCC fork. The foundation is there, but it is still in early stages of development and mainly supports the exit(2) system call. Nonetheless, with the current SCC changes, a libc.a archive is created that can be used with Qute.

The required steps for obtaining the Qute libc.a are described in README.qute within the SCC fork.

Preloading the Standard Library

Applications can then be compiled using the C compiler provided by the SCC toolchain. For this, my SCC fork includes a new command-line option to only emit a QBE representation. Using this option, a sample application can be compiled (within the SCC repository) as follows:

$ cat hello-malloc.c
#include <stdlib.h>

int main(void) {
	int *ptr = malloc(sizeof(int));
	*ptr = 42;
	return *ptr;
}
$ ./bin/scc -o hello-malloc.qbe -c hello-malloc.c -R
$ qute --preload ./lib/scc/amd64-qute/libc.a hello-malloc.qbe
$ echo $?
42

The same approach is applicable to the standard library of other programming languages (e.g., Hare). The main challenge is mapping the system call interface of the standard library to the intercepted functions of Qute. Currently, Qute only intercepts a limited amount of functions. The next step is defining an interface in Qute that is sufficient to support all syscalls required by SCC (probably boils down to having a POSIX file system interface in Qute). Once that is available, other standard libraries could also be retargeted to Qute.