shadow/scallion — Issue #9: Tor and LLVM
Author: robgjansen
Created: 2011-11-09 20:49:13+00:00
State: open
Labels: feature

This was taken from http://mailman.cs.umn.edu/archives/shadow-dev/2011-November/000001.html
Rob
=========

This is a quick and dirty writeup, so please don't assume I've got all the details right!

== Summary:

We could use LLVM to solve Shadow's problems with isolating shared
state between program runs!

== Shadow background:

Not included. I'm assuming you know about Shadow already. The
important thing to know (IIUC) is that Shadow needs to be able to have
many instances of a program running in a process space, and needs to
be able to swap global state between them whenever it switches from
one instance of the program to another. Therefore, we want a way to
transform programs so that their global state is easily isolated and
swapped.

== LLVM Background:

LLVM is basically a static-single-assignment register transfer
language useful both for JITs and for more optimized compilation.
It's got a bitcode representation, a textual assembly language
representation, and an in-memory representation. The implementation
is in C++; there are frontends in a variety of languages.

There are two good ways to compile C to LLVM: first, by using the
"llvm-gcc" frontend (a modified GCC that can output native binaries,
LLVM bitcodes or assembly), and second, by using the "clang" compiler
(a written-from-scratch LLVM-based compiler that can do the same).

== Why is this a good idea anyway?

It should work on arbitrary programs, it can handle a wide variety of
languages, and it can target a wide variety of target architectures.
Unlike some other approaches, it lets you do the context switch
operation as a single pointer assignment. It's comprehensible in
terms of a high-level program transformation. It has enough semantic
coherence that it's easily demonstrated to be correct.

== The key transformation that Shadow needs:

Suppose that you've taken your entire C program and compiled it into
LLVM. Before you optimize it too hard, you want to make it so that
it's easy for shadow to swap the global state. In effect, you're
going to transform the program so that there's a struct holding
everything that would otherwise be a global or static variable, and so
that the only global state left is a pointer to that struct.

So if your program is (in part):

int a=99;
static const char *b="foo";
int x(void) {static int c; return ++c;}
unsigned y(void) {static unsigned c; return --c;}

then we want to transform it into something like:

struct _globals {
int a;
const char *modname_b;
int modname_x_c;
int modname_y_c;
};

void _init_globals(struct _globals *g) {
g->a=99
g->b="foo";
g->c=0;
g->d=0;
};

struct _globals *_the_globals;

int x(void) {return ++_the_globals->modname_x_c;}
unsigned y(void) { return --_the_globals->modname_y_c;}

We can express this transformation more easily in LLVM than in C; let's see how.

Let's explain it as two whole-program passes. In pass one, we're
going to map every global or static variable to a position in the
globals struct. At this time we also write a function to initialize
new instances of this structure. Unlike in C, we don't actually need
to name the fields of the struct, so we don't need to do any name
mangling here. In pass two, we prefix every load or store to a global
variable with a load and an indirection.

To be concrete, the above program compiles to unoptimized LLVM as
follows. (See http://llvm.org/docs/LangRef.html for the LLVM language
reference. It's pretty straightforward if you've ever dealt with
assembly or compilers before. If the discussion here makes no sense
to you, you should probably skim it and try reading this again.)

@a = global i32 99, align 4
@x.c = internal global i32 0, align 4
@y.c = internal global i32 0, align 4

define i32 @x() nounwind {
%1 = load i32* @x.c, align 4
%2 = add nsw i32 %1, 1
store i32 %2, i32* @x.c, align 4
ret i32 %2
}

define i32 @y() nounwind {
%1 = load i32* @y.c, align 4
%2 = add i32 %1, -1
store i32 %2, i32* @y.c, align 4
ret i32 %2
}

So in the above program, after the first pass, we should have a new
struct declaration:

%_globals = type { i32, i8*, i32, i32 }

and a variable definition:

@_the_globals = common global %struct._globals* null

and an internal mapping that tells us that the four elements of
_globals correspond to a,b,x.c, and y.c respectively. We get the
members of %_globals by just gathering up the types of all the
variable declarations in the program; the @_the_globals declaration is
boilerplate.

If the offset of "global" is OFF, we we replace every "%N = Load
(type) (global)" with
; Load the current value of '_the_globals' into %N'
%N' = Load %_globals** @_the_globals
; Let N'' be the offset of "global" within %N'
%N'' = getelementptr inbounds %_globals* %N', i64 0, i32 OFF
; Now do the actual load
%N = Load (type) %N''

And we replace every "Store (type) %VAL, (type)* (global)" with:
; Load the current value of '_the_globals' into %N'
%N' = Load %_globals** @_the_globals
; Let N'' be the offset of "global" within %N'
%N'' = getelementptr inbounds %_globals* %N', i64 0, i32 OFF
; Now do the actual store
Store (type) %VAL, (type*) %N''

This transformation will result in many extraneous "load _the_globals"
operations, but a later compiler optimization pass should make them go
away. If you prefer, you can stick a "load globals" instruction into
the beginning of any function that needs a global variable, and just
do the getelementpointer and load/store as needed.

In our example, the function x would become:

define i32 @x() nounwind {
%1 = load %struct._globals** @_the_globals
%2 = getelementptr inbounds %struct._globals* %1, i32 0, i32 2
%3 = load i32* %2,
%4 = add nsw i32 %3, 1
store i32 %4, i32* %2
ret i32 %4
}

== What am I glossing over?

Alignment, tricky initializers, the correct handling of various
linkage types, and and the correct handling of loads and stores from
fields of global structures. These aren't so bad, but you'll actually
need to think them through.

== Okay, how to build it?

This is where I got stuck. The LLVM API is powerful but complex. In
order to do this transformation properly, it needs to happen as a
whole-program transformation. The cleanest way to do that would be a
clang plugin... Plugging into LLVM's whole-program-optimization
support, writing an additional clang plugin, and making clang actually
invoke it as needed proved to be more than I could figure out in my
spare time.

The easiest way to do this could well be "a dirty hack": compile all
your .c files to LLVM assembly or bitcode, then write a program to
transform the assembly (using the appropriate LLVM tools), then feed
those LLVM files back into the LLVM toolchain to get an optimized
binary. It's not too elegant, though, and you'd need to really bang
on the build system to make it work.

== Who will bell the cat?

Not me any time soon. I've got Tor deadlines looming. :)

cheers,
--
Nick