Programming for coverage part 4

This is a trivial C++ function that does an unchecked access of an array element. It is perfectly fine to use if i is in bounds, and the CFG is just the straight line you would expect. Testing wise, the only thing we really can do is call it with a valid vec and i in bounds, as anything else would be undefined.

int& unsafe_at(int* vec, std::size_t i) {
    return vec[i];
}

Here is a similar function with a bounds check. If the access would be out of bounds we throw an exception. This is what happens internally in std::vector::at.

int& checked_at(int* vec, std::size_t size, std::size_t i) {
    if (i >= size)
        throw std::exception();
    return vec[i];
}

Exception paths must exercised for coverage since exceptions are control flow constructs, too. Most C++ testing frameworks have first-class support for checking that the an exception is thrown, like this example using catch2:

TEST_CASE ("checked_at") {
    const std::size_t len = 5;

    // 0 1 2 3 4
    auto* vec = make_sequence(len);

    CHECK (checked_at(vec, len, 0) == 0);
    CHECK (checked_at(vec, len, 4) == 4);
    CHECK_THROWS (checked_at(vec, len, len));
}

The big change exceptions bring are paths that do not terminate in the special end block as the function does not return when an exception is thrown. When an exception is thrown the function terminates in a special throw block, which starts the stack unwinding and exception propagation. If we were to handle the exception it becomes regular control flow, as in this example.

int sum(int acc, int* vec, std::size_t size, std::size_t i) {
    try {
        const int v = checked_at(vec, size, i);
        acc += v;
    } catch (...) {
        acc += 0;
    }
    return acc;
}

It is quite important to also verify that exceptions are thrown as expected, and that they are handled as intended. I have written code where I assumed an exception would be thrown when it in fact did not. Exception handling is also a common source of bugs. Error paths can be difficult to test because the conditions leading up to them are hard to synthesize, and sometimes they are missed because the control flow is invisible. Coverage make these paths light up.

The exception thrown by checked_at should be easy to avoid in real programs. If an index comes from untrusted (e.g. user) input we usually validate before using it for access, and indices sourced from program logic tend to be derived from the array and consistent. This does not apply to all errors. Here is an rather innocent improvement to checked_at(), where the exception thrown is the richer std::out_of_range, the same exception thrown by std::vector::at.

int& checked_at(int* vec, std::size_t size, std::size_t i) {
    if (i >= size)
        throw std::out_of_range("i >= size");
    return vec[i];
}

Can you guess why there is a second throw block? Here are the signatures for the std::out_of_range constructor:

out_of_range(const std::string& what_arg);
out_of_range(const char* what_arg);
out_of_range(const out_of_range& other);

The std::out_of_range object constructs and copies a std::string for its message. std::string is dynamically sized which means it must allocate, which might fail and throw a std::bad_alloc. For it to be exercised we must try to access the array out-of-bounds and run out of memory during the error handling. This is a a problem for testing (and coverage) because memory is system dependent, global, and implicit resource that is hard to control. So what can we do?

One strategy is to accept missing coverage for exception paths. This is more of a coping strategy than anything, because you absolutely want to exercise some exceptions, or show why they cannot happen.

Since we do not control the allocations happening inside the standard library it is difficult to have them fail at the right time. Yet these failures are important as seen in the previous example because those paths are very much a part of the program. We also really don’t want to pollute with code that exists to support testing either, so adding if (in_test) fail_next_alloc() is not viable. Not all hope is lost, because C++ supports replacement functions which enable us to write a custom operator new.

What I usually do is instruct my allocation function to make the nth allocation fail. It might be possible to use sophisticated techniques such as stack scanning or parsing backtraces to figure out when to fail, but using a counter is usually enough. I add a few extra functions in my test suite:

static std::size_t remaining = std::numeric_limits<std::size_t>::max();

void fail_new_after(std::size_t n) {
    remaining = n;
}

void* operator new(std::size_t sz) {
    if (!remaining) throw std::bad_alloc{};
    remaining -= 1;
    if (sz == 0)
        ++sz;
    if (void *ptr = std::malloc(sz))
        return ptr;
    throw std::bad_alloc{};
}

void* operator new[](std::size_t sz) {
    if (!remaining) throw std::bad_alloc{};
    remaining -= 1;
    if (sz == 0)
        ++sz;
    if (void *ptr = std::malloc(sz))
        return ptr;
    throw std::bad_alloc{};
}

In my test I repeatedly increase the allocation allowance until the function succeeds. This is a standard testing technique John Lakos referred to as orthogonal perturbation at ACCU 2022 (ca 20m30s). It is a heavy-handed approach, but it works well enough. Pretty much nothing in C++ makes any guarantee on when or how allocations happen, so we can’t know in advance how many allocations are required for an operation to succeed. By limiting the iterations we can guarantee that the test will terminate, and if the limit is so low that we don’t observe the allocation failure we want, the coverage report will tell us.

TEST_CASE ("checked_at") {
    const std::size_t len = 5;

    // 0 1 2 3 4
    auto* vec = make_sequence(len);

    CHECK (checked_at(vec, len, 0) == 0);
    CHECK (checked_at(vec, len, 4) == 4);
    CHECK_THROWS (checked_at(vec, len, len));

    // If this call allocates more than 1000 times, consider it failing
    for (std::size_t i = 0; i != 1000; ++i) {
        fail_new_after(i);
        try {
            checked_at(vec, len, len);
        } catch (std::bad_alloc&) {
            continue;
        } catch (std::out_of_range&) {
            // The function succeeds by throwing out_of_range
            break;
        }
        assert (false);
    }
}

What alternatives do we have to replacing the global new? For some functions we can do all allocations up front and never use functions that could throw, but that’s honestly not practical in C++. For example, vector.push_back would be out.

The standard C++ container types have an allocator parameter. From cppref:

template<
    class T,
    class Allocator = std::allocator<T>
> class vector;

It is tempting to think that we could achieve the same thing using the allocator, but it is unfortunately not that simple. The allocator is a static parameter, which means that std::vector<int, std::allocator<int>> is a different type than std::vector<int, failing_allocator<int>>. That means functions expecting a std::vector<int> cannot be called with the failing cousin, and since we won’t be exercising the same code this feature is not helpful for coverage. Here is an example program that shows the allocation parameter causing different overload selection.

#include <cstdio>
#include <vector>

template <typename T>
struct noisy_allocator : public std::allocator<int> {
    template <class U>
    struct rebind { using other = noisy_allocator<U>; };

    using std::allocator<T>::allocator;
    T* allocate(std::size_t n) {
        std::printf("Allocating %zu elements\n", n);
        return std::allocator<int>::allocate(n);
    }
};

int sum(const std::vector<int>& v) {
    int s = 0;
    for (auto x : v)
        s += x;
    return s;
}

int sum(const std::vector<int, noisy_allocator<int>>& v) {
    int s = 0;
    for (auto x : v)
        s += x;
    return s;
}

int main() {
    std::vector<int> quiet;
    std::vector<int, noisy_allocator<int>> noisy;

    for (std::size_t i = 0; i != 100; ++i) {
        quiet.push_back(i);
        noisy.push_back(i);
    }
    std::printf("quiet sum = %d, noisy sum = %d\n", sum(quiet), sum(noisy));
}

The sum() calls will resolve to different function calls. This can be clearly seen in the symbol table.

$ g++ alloc.cc -o alloc && ./alloc
Allocating 1 elements
Allocating 2 elements
Allocating 4 elements
Allocating 8 elements
Allocating 16 elements
Allocating 32 elements
Allocating 64 elements
Allocating 128 elements
quiet sum = 4950, noisy sum = 4950

$ nm -g alloc | grep sum
00000000004015be T _Z3sumRKSt6vectorIi15noisy_allocatorIiEE
0000000000401376 T _Z3sumRKSt6vectorIiSaIiEE

Even if these types had been overload-compatible it would not have solved the problem when code uses the standard containers in functions. For example, if we want to find the most frequent word in a text:

std::string wordcount(const std::vector<std::string>& text) {
    std::map<std::string, std::size_t> wc;
    for (const auto& word : text)
        wc[word] += 1;
    std::string* winner;
    std::size_t top = 0;
    for (auto& [word, count] : wc) {
        if (count > top) {
            top = count;
            winner = &word;
        }
    }
    return *winner;
}

This is quite straight forward C++, and the function variables use the default allocator. Even if we could drop in our failing allocator for the text argument, that would not change the map or strings in the map, which have have error paths involving allocation failure as seen in the CFG as paths ending in block 35-THROW. All exceptions that this function might throw are allocation failures.

What we need is for the program to be more dynamic and configurable. The POSIX open_memstream provides a FILE handle compatible with the stdio API (fread, fwrite, etc.) backed by user-provided memory, which makes it easy to simulate truncated files. SQLite uses similar techniques to synthesize failed writes, failed reads, etc., all dynamically resolved through configurable handles. SQLite applies the same technique to allocations by consistently using its own configurable malloc. Going through a vtable does not invalidate testing or change the structure, unlike changing the type statically.

One way to introduce dynamism is to use the polymorphic allocators everywhere, and seed them with a failing memory resource in test suite. This is a more precise alternative than replacing the new itself, with a much smaller blast radius. Code would have to be specifically written to leverage the pmr types, which means it may interoperate poorly with third-party libraries, but it is worth keeping in mind.

In Zig there is a convention that an allocator is an explicit parameter to any function that may need to allocate. Allocator is an interface, which gives the caller the opportunity to select the allocation strategy at call time, which for testing may include leak monitoring and allocation failure. This is a rough port of the C++ function to Zig; note the explicit allocator argument.

const std = @import("std");
const Allocator = std.mem.Allocator;

fn wordcount(allocator: Allocator, text: []const [] const u8) ![]u8 {
    var wc = std.StringHashMap(usize).init(allocator);
    defer wc.deinit();

    for (text) |word| {
        const v = try wc.getOrPutValue(word, 0);
        v.value_ptr.* += 1;
    }

    var winner: *[]const u8 = undefined;
    var top: usize = 0;
    var it = wc.iterator();
    while (it.next()) |entry| {
        const count = entry.value_ptr.*;
        if (count > top) {
            top = count;
            winner = entry.key_ptr;
        }
    }

    return try allocator.dupe(u8, winner.*);
}

const expect = std.testing.expect;
test "basic test" {
    const text: [12][]const u8 = .{
        "foo", "bar", "baz",
        "fof", "bar", "biz",
        "foo", "bar", "bap",
        "oof", "rab", "zab",
    };
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    const mostfreq = try wordcount(allocator, &text);
    defer allocator.free(mostfreq);
    try expect(std.mem.eql(u8, mostfreq, "bar"));
}

test "failing allocation" {
    const text: [12][]const u8 = .{
        "foo", "bar", "baz",
        "fof", "bar", "biz",
        "foo", "bar", "bap",
        "oof", "rab", "zab",
    };
    const allocator = failing_allocator();
    const mostfreq = try wordcount(allocator, &text);
    defer allocator.free(mostfreq);
    // should fail
    try expect(std.mem.eql(u8, mostfreq, "bar"));
}

In C++ we apply this design by using polymorphic allocator containers consistently and pass std::memory_resource to functions that might need to allocate. The explicit (or embedded, in the case of pmr) dynamic allocator is an example of dependency injection applied to memory.