Wednesday, October 29, 2014

A taste of Rust (yum) for C/C++ programmers

If, like me, you've been frustrated with the status quo in systems languages, this article will give you a taste of why Rust is so exciting. In a tiny amount of code, it shows a lot of ways that Rust really kicks ass compared to C and C++. It's not just safe and fast, it's a lot more convenient.

Web browsers do string interning to condense the strings that make up the Web, such as tag and attribute names, into small values that can be compared quickly. I recently added event logging support to Servo's string interner. This will allow us to record traces from real websites, which we can use to guide further optimizations.

Here are the events we can log:

pub enum Event {
    Insert(u64, String),

Interned strings have a 64-bit ID, which is recorded in every event. The String we store for "insert" events is like C++'s std::string; it points to a buffer in the heap, and it owns that buffer.

This enum is a bit fancier than a C enum, but its representation in memory is no more complex than a C struct. There's a tag for the three alternatives, a 64-bit ID, and a few fields that make up the String. When we pass or return an Event by value, it's at worst a memcpy of a few dozen bytes. There's no implicit heap allocation, garbage collection, or anything like that. We didn't define a way to copy an event; this means the String buffer always has a unique owner who is responsible for freeing it.

The deriving(Show) attribute tells the compiler to auto-generate a text representation, so we can print an Event just as easily as a built-in type.

Next we declare a global vector of events, protected by a mutex:

lazy_static! {
    pub static ref LOG: Mutex<Vec<Event>>
        = Mutex::new(Vec::with_capacity(50_000));

lazy_static! will initialize both of them when LOG is first used. Like String, the Vec is a growable buffer. We won't turn on event logging in release builds, so it's fine to pre-allocate space for 50,000 events. (You can put underscores anywhere in a integer literal to improve readability.)

lazy_static!, Mutex, and Vec are all implemented in Rust using gnarly low-level code. But the amazing thing is that all three expose a safe interface. It's simply not possible to use the variable before it's initialized, or to read the value the Mutex protects without locking it, or to modify the vector while iterating over it.

The worst you can do is deadlock. And Rust considers that pretty bad, still, which is why it discourages global state. But it's clearly what we need here. Rust takes a pragmatic approach to safety. You can always write the unsafe keyword and then use the same pointer tricks you'd use in C. But you don't need to be quite so guarded when writing the other 95% of your code. I want a language that assumes I'm brilliant but distracted :)

Rust catches these mistakes at compile time, and produces the same code you'd see with equivalent constructs in C++. For a more in-depth comparison, see Ruud van Asseldonk's excellent series of articles about porting a spectral path tracer from C++ to Rust. The Rust code performs basically the same as Clang / GCC / MSVC on the same platform. Not surprising, because Rust uses LLVM and benefits from the same backend optimizations as Clang.

lazy_static! is not a built-in language feature; it's a macro provided by a third-party library. Since the library uses Cargo, I can include it in my project by adding

git = ""

to Cargo.toml and then adding

extern crate lazy_static;

to src/ Cargo will automatically fetch and build all dependencies. Code reuse becomes no harder than in your favorite scripting language.

Finally, we define a function that pushes a new event onto the vector:

pub fn log(e: Event) {

LOG.lock() produces an RAII handle that will automatically unlock the mutex when it falls out of scope. In C++ I always hesitate to use temporaries like this because if they're destroyed too soon, my program will segfault or worse. Rust has compile-time lifetime checking, so I can do things that would be reckless in C++.

If you scroll up you'll see a lot of prose and not a lot of code. That's because I got a huge amount of functionality for free. Here's the logging module again:

pub enum Event {
    Insert(u64, String),

lazy_static! {
    pub static ref LOG: Mutex<Vec<Event>>

pub fn log(e: Event) {

This goes in src/ and we include it from src/

#[cfg(feature = "log-events")]
pub mod event;

The cfg attribute is how Rust does conditional compilation. Another project can specify

git = ""
features = ["log-events"]

and add code to dump the log:

for e in string_cache::event::LOG.lock().iter() {
    println!("{}", e);

Any project which doesn't opt in to log-events will see zero impact from any of this.

If you'd like to learn Rust, the Guide is a good place to start. We're getting close to 1.0 and the important concepts have been stable for a while, but the details of syntax and libraries are still in flux. It's not too early to learn, but it might be too early to maintain a large library.

By the way, here are the events generated by interning the three strings foobarbaz foo blockquote:

Insert(0x7f1daa023090, foobarbaz)

There are three different kinds of IDs, indicated by the least significant bits. The first is a pointer into a standard interning table, which is protected by a mutex. The other two are created without synchronization, which improves parallelism between parser threads.

In UTF-8, the string foo is smaller than a 64-bit pointer, so we store the characters directly. blockquote is too big for that, but it corresponds to a well-known HTML tag. 0xb is the index of blockquote in a static list of strings that are common on the Web. Static atoms can also be used in pattern matching, and LLVM's optimizations for C's switch statements will apply.

Wednesday, September 17, 2014

Raw system calls for Rust



#[phase(plugin, link)]
extern crate syscall;

    unsafe {

fn main() {


Wednesday, August 27, 2014

Calling a Rust library from C (or anything else!)





Using html5ever from C

Like most Rust libraries, html5ever builds with Cargo.

$ git clone
$ cd html5ever
$ git checkout dev
$ cargo build
    Updating git repository ``
   Compiling phf_mac v0.0.0 (
   Compiling phf v0.0.0 (


$ mkdir build
$ cd build
$ ../configure
$ make libhtml5ever_for_c.a
note: library: rt
note: library: dl
note: library: pthread
note: library: gcc_s
note: library: pthread
note: library: c
note: library: m


$ H5E_PATH=/tmp/html5ever

CHARS : Hello
TAG   : <i>
  ATTR: class="excellent"
CHARS : world!
TAG   : </i>


Let's look at the C client code.

#include <stdio.h>

#include "html5ever.h"

void put_str(const char *x) {
    fputs(x, stdout);

void put_buf(struct h5e_buf text) {
    fwrite(, text.len, 1, stdout);

    put_str("TAG   : <");
    if (self_closing) {

// ...

struct h5e_token_ops ops = {
    .do_chars = do_chars,
    .do_start_tag = do_start_tag,
    .do_tag_attr = do_tag_attr,
    .do_end_tag = do_end_tag,

struct h5e_token_sink sink = {
    .ops = &ops,
    .user = NULL,

    if (argc < 2) {
        return 1;

    struct h5e_tokenizer *tok = h5e_tokenizer_new(&sink);
    return 0;



Implementing the C API






pub struct h5e_token_ops {
        self_closing: c_int, num_attrs: size_t),
        value: h5e_buf),


    // ...





Then I wrote a C header file matching this ABI:

struct h5e_buf {
    unsigned char *data;
    size_t len;

struct h5e_buf h5e_buf_from_cstr(const char *str);

struct h5e_token_ops {
        int self_closing, size_t num_attrs);

        struct h5e_buf value);


    /// ...

struct h5e_tokenizer;

struct h5e_tokenizer *h5e_tokenizer_new(struct h5e_token_sink *sink);
void h5e_tokenizer_free(struct h5e_tokenizer *tok);
void h5e_tokenizer_end(struct h5e_tokenizer *tok);



Tuesday, February 11, 2014

x86 is Turing-complete with no registers

In which x86 has too many registers after all.



No registers?






So what's left that we can work with? Just

  • the instruction pointer,
  • memory operands, and
  • self-modifying code.


The instruction set


c6042500004000ba          mov byte  [0x400000], 0xba
66c7042500004000dbba      mov word  [0x400000], 0xbadb
c7042500004000efbead0b    mov dword [0x400000], 0xbadbeef
48c7042500004000efbead0b  mov qword [0x400000], 0xbadbeef


We can also perform arithmetic on a memory location in place:

8304250000400010          add dword [0x400000], 0x10



ff242500004000            jmp qword [0x400000]


Compiling from Brainfuck



TAPE_SIZE equ 30000

    times TAPE_SIZE dq cell0

head equ tape_start + (TAPE_SIZE / 2)



cont_zero:     dq 0
cont_nonzero:  dq 0
out_byte:      db 0

align 16
    jmp inc_cell

align 16
    mov byte [out_byte], 0
    jmp [cont_zero]

%assign cellval 1
%rep 255
    align 16
    mov byte [out_byte], cellval
    jmp [cont_nonzero]
    %assign cellval cellval+1

align 16
    jmp dec_cell




    jmp [head]

    add qword [head], 16
    jmp test_cell

    sub qword [head], 16
    jmp test_cell

    add dword [inc_cell+4],  8
    add dword [dec_cell+4],  8
    add dword [test_cell+3], 8
    jmp [cont_zero]

    sub dword [inc_cell+4],  8
    sub dword [dec_cell+4],  8
    sub dword [test_cell+3], 8
    jmp [cont_zero]





k00000000: do_branch k00000003, k00000001
k00000001: do_inc    k00000002
k00000002: do_branch k00000003, k00000001
k00000003: jmp exit

which blows up into something like

401205:  48c70425611240005c124000  mov qword ptr [0x401261], 0x40125c
401211:  48c704256912400022124000  mov qword ptr [0x401269], 0x401222
40121d:  e90cefffff                jmp 40012e <test_cell>

401222:  48c70425611240003f124000  mov qword ptr [0x401261], 0x40123f
40122e:  48c70425691240003f124000  mov qword ptr [0x401269], 0x40123f
40123a:  e9f6eeffff                jmp 400135 <inc_cell>

40123f:  48c70425611240005c124000  mov qword ptr [0x401261], 0x40125c
40124b:  48c704256912400022124000  mov qword ptr [0x401269], 0x401222
401257:  e9d2eeffffe9d2eeffff      jmp 40012e <test_cell>

40125c:  e9c1eeffff                jmp 400122 <exit>




$ curl -s | ./compiler
$ echo 'Uryyb, jbeyq!' | ./rip
Hello, world!

$ curl -s | ./compiler
$ ./rip


$ curl -s | ./compiler
$ (curl -s;
Hello, world!

This takes about 4.5 seconds on my machine.

Verifying it with ptrace


uint64_t regs_boundary;

void clobber_regs(pid_t child) {
    struct user_regs_struct   regs_int;
    struct user_fpregs_struct regs_fp;

    if ( < regs_boundary)


    // Clear everything before the instruction pointer,
    // plus the stack pointer and some bits of EFLAGS.
    regs_int.rsp = 0;
    regs_int.eflags &= EFLAGS_MASK;

    // Clear x87 and SSE registers.
    memset(regs_fp.st_space,  0, sizeof(regs_fp.st_space));
    memset(regs_fp.xmm_space, 0, sizeof(regs_fp.xmm_space));






while (1) {

    if (WIFEXITED(status))


And the demo:

$ gcc -O2 -Wall -o regclobber regclobber.c
$ curl -s | ./compiler
Hello, world!

Executed 81366 instructions; clobbered registers 81189 times.



Notes on universality

