Making 100% Code Coverage as Easy as Flipping a Coin

We are obsessed with testing at Qumulo.

Shipping a new version of a distributed, scale-out file system every two weeks means we have to be confident that every commit to our codebase is bug-free. To that end, we have tens of thousands of unit tests, thousands of integration tests, and many hundreds of full system tests that batter every build to verify that we haven’t introduced a regression.

While these kinds of tests are important, we wanted to go further. We wanted a way to execute every possible path through a particular piece of code so that we could verify that, no matter what, the behavior of the code was correct and the invariants of the system held. A traditional approach to this problem might be to manually inspect code coverage reports and craft individual tests to exercise each branch of the code, but this is brittle because it requires a human to inspect the code coverage and it often involves a complex, sometime convoluted test to exercise the uncovered code. Alternatively, we could write fuzz tests that probabilistically explore the every branch of the code, but these are hard to craft well and, by their nature, may not explore all of the interesting cases. We thought we could do better.

A motivating example

Imagine that we have a function which de-serializes a kumquat order from a binary format into a struct kumquat_order</var/www/wordpress>:

struct kumquat_order {
    char     name[100];
    unsigned quantity;
};

int
deserialize_kumquat_order(struct istream *input, struct kumquat_order *out) {
    int error_code = istream_read(input, out->quantity, sizeof out->quantity);
    if (error_code != 0)
        return error_code;

    bool anonymous;
    error_code = istream_read(input, &anonymous, sizeof anonymous);
    if (error_code != 0)
        return error_code;

    if (anonymous)
        strcpy(order->name, "anonymous");
    else
        istream_read(input, out->name, sizeof out->name);

    return 0;
}

One of the invariants of this function is that if any call into the istream returns an error, the function must also return an error. As you can see, that invariant has been violated when we are reading out the name from the order, where the error code from istream_read()</var/www/wordpress> is completely ignored:

istream_read(input, out->name, sizeof out->name);</var/www/wordpress>

In this case, it wouldn’t be unimaginably hard to write a unit test to uncover this bug but as we add more fields to the kumquat_order and more complexity to the binary format, it would become harder and harder to craft individual unit tests to verify our invariant and protect against this class of bug. What we would really like is an implementation of the istream interface that can deterministically return an error at every point that it is called.

Introducing rseq

In order to drive these exhaustive coverage tests, we created a component that we call rseq, which stands for “random sequence” (although that’s a bit of a misnomer – there’s nothing “random” about rseq). The fundamental interface for rseq is remarkably simple:

struct rseq;
bool rseq_flip_coin(struct rseq *);
bool rseq_next_simulation(struct rseq *);

rseq is built on the concept of a simulation of a test. Each time the test reaches a decision point that it wants to be part of the set of decisions under simulation, it calls into rseq_flip_coin()</var/www/wordpress>, which returns a boolean that the test can use to influence the behavior of this simulation of the test. At the end of each simulation, the test calls rseq_next_simulation()</var/www/wordpress>, which will return false when there are no more simulations with unique paths through the decision space. Let’s look at a simple example:

struct rseq *rseq = rseq_new();
do {
    printf("%c", rseq_flip_coin(rseq) ? 't' : 'f');
    printf("%c", rseq_flip_coin(rseq) ? 't' : 'f');
    printf("%c,", rseq_flip_coin(rseq) ? 't' : 'f');
} while (rseq_next_simulation(rseq));

The output of this code is the complete set of combinations of decisions:

fff, fft, ftf, ftt, tff, tft, ttf, ttt,</var/www/wordpress>

Importantly, rseq is able to work even if calls to rseq_flip_coin()</var/www/wordpress> are conditional. For example, if we only make the second call to rseq_flip_coin()</var/www/wordpress> if the first call returns true:

struct rseq *rseq = rseq_new();
do {
    if (rseq_flip_coin(rseq)) {
        printf("a");
        printf("%c", rseq_flip_coin(rseq) ? 'b' : 'c');
    } else
        printf("d");
    printf("%c,", rseq_flip_coin(rseq) ? 'e' : 'f');
} while (rseq_next_simulation(rseq));

The output would be:

df, de, acf, ace, abf, abe</var/www/wordpress>

Non-binary decisions (e.g. choosing between five different options) can be implemented using coin flips, but rseq helpfully provides a function that does this for you:

unsigned rseq_roll_die(struct rseq *, unsigned sides);</var/www/wordpress>

rseq internals

As you may have noticed, rseq performs a sort of “false-first” search through the decision space. It accomplishes this in a relatively simple way: by keeping track of a script of decisions to return, implemented with a vector of booleans representing coin flip decisions and a cursor to keep track of the current position in the script.

As calls to rseq_flip_coin()</var/www/wordpress> are made, the decision at the current cursor is returned. If the cursor is at the end of the script when the call is made, we append a false decision to the script and return false from the rseq_flip_coin()</var/www/wordpress> call.

When rseq_next_simulation()</var/www/wordpress> is called, we trim trailing true decisions from the end of the script, which represent decision paths that have been fully explored, and flip the last false decision in the script to true and rseq_next_simulation() returns true. If the script is empty after trimming trailing true decisions, the decision tree has been fully explored and rseq_next_simulation()</var/www/wordpress> returns false.

In case that English wasn’t clear, we created a basic interactive Python version of rseq at repl.it, which you can play with to help yourself understand how it works.

Exhaustively testing the kumquat_order</var/www/wordpress> deserializer

One common way that we use rseq at Qumulo is in a test-double implementation of an interface that is dependency injected into the system under test (SUT).

Going back to the example from above, what we’d like is a version of the istream interface that either returns an error or falls through to another implementation of istream that does the actual work. For reasons that will become clear later, we’re also going to want to know that some call into this rseq-aware istream has returned an error. Here’s an example implementation that uses a bit of Qumulo C interface magic:

struct rseq_error_istream {
    a_implements(istream); // Qumulo magic!
    struct rseq *rseq;
    bool returned_error; // Initialized to false
    struct istream *delegate;
};

int
rseq_error_istream_read(struct rseq_error_istream *self, void *data, unsigned c)
{
    if (rseq_flip_coin(self->rseq)) {
        self->returned_error = true;
        return -1;
    } else
        return istream_read(self->delegate, data, c);
}

By using rseq here, we are guaranteed that by the time rseq_next_simulation()</var/www/wordpress> returns false, every call into istream_read made by the SUT will have returned an error in at least one of the simulations. Using such an implementation of istream, we can now write a test which will fail when run against our kumquat_order</var/www/wordpress> deserializer:

struct rseq *rseq = rseq_new();
do {
    // Fixture setup
    struct file_istream *order_istream = file_istream_new('test_order'));
    struct rseq_error_istream *rseq_istream = rseq_error_istream_new(
        rseq, istream_from_file_istream(order_istream));

    // Exercise SUT
    struct kumquat_order order;
    int error = deserialize_kumquat_order(
        istream_from_rseq_error_istream(rseq_istream), &order);

    // Verify
    if (rseq_istream->returned_error)
        assert(error == -1);
    else
        assert(kumquat_order_is_correct(&order));

    // Fixture teardown
    rseq_error_istream_free(rseq_istream);
    file_istream_free(order_istream);
} while (rseq_next_simulation());

The really awesome thing about this test is that it’s completely agnostic to how deserialize_kumquat_order()</var/www/wordpress> uses the istream. As we add more complexity to the deserialization code, this test will continue to exercise every possible error path through the SUT, verifying our invariant without us having to write a new test for each new path. We could even extend the invariant to say that no calls should be made into the istream after it returns an error with relative ease by making the following modification:

int
rseq_error_istream_read(struct rseq_error_istream *self, void *data, unsigned c)
{
    assert(!self->returned_error);
    if (rseq_flip_coin(self->rseq)) {
        self->returned_error = true;
        return -1;
    } else
        return istream_read(self->delegate, data, c);
}

Other uses for rseq

Fail-fast verification is one of many usages of rseq at Qumulo. Other interesting things we’ve done with rseq include:

• Simulating every possible ordering of RPCs that are simultaneously delivered to a node in our cluster
• Simulating every possible interleaving of user-space cooperative threads (yes, we’ve written our own user-space threading library!) by using rseq in the scheduler to select the next thread to run when a thread yields.
• Simulating every possible state of a complex system and demonstrating that our code can proceed from that state (e.g. distributed transaction recovery)
  rseq pitfalls

While rseq is extremely useful, it does have its pitfalls:

• rseq doesn’t do well with non-determinism because it relies on the order of calls to rseq_flip_coin() being deterministic for each simulation. For example, if the SUT uses a rand() to decide whether to make a call that eventually calls into rseq, it will quickly become confused. To get around this, we encapsulate this randomness into an dependency-injected interface which has a production implementation that calls into rand() but can be substituted with a test double that uses rseq when run in tests.
• Likewise, it is dangerous to use rseq in a multi-threaded environment. If multiple threads can be acting on the same rseq instance during a simulation, this introduces non-determinism in the call order to rseq. For this and many other reasons, we try very hard to keep the vast majority of our code single-threaded, using async calling patterns rather than spawning threads whenever possible.
• When the SUT is complex, rseq can get into a state explosion causing the number of simulations that must be run to exhaustively search the decision space to grow exponentially. We haven’t had too much trouble with this in practice, but luckily, rseq lends itself nicely to running in a distributed manner with workers each taking some portion of the search space if we ever want to do that.