23 April, 2017

Testing error handling in C

Writing tests is an useful tool in any programmers toolbox. For C programmers it tends to be slightly more cumbersome compared to other more high level languages. Especially if you are like me and fall in the "handmade" category (see the Handmade Manifesto) and don't just want to use any and every library and framework you can get your hands on.

Even so, I tend to write test suites and measure code coverage (see my other article) to make sure I get as close as possible to execute all potential code paths in my projects. In my foundation codebase I recently hit the wall where I was basically testing everything I could except for one thing. Code handling standard library or system call failures.

In some cases you can provoke a failure in order to test your error handling by sending in invalid values. But this might not always be possible, like if your function makes the standard library call with parameters independent of the arguments of the function you are testing. No matter what your test passes to the function, the standard library call will succeed. It will only fail due to external factors which are impossible or at least very difficult for your test to control. One simple example, using getcwd on POSIX-compliant system to get the path of the current working directory for the process. In my codebase the call looks something like

char*
function_we_want_to_test(int arg) {
 //Some code goes here
 char buffer[MAX_PATH_LEN];
 if (!getcwd(buffer, sizeof(buffer)) {
  //Error handling code goes here
  return 0;
 }
 //Success code path...
}

In this snippet, buffer is a local variable which is independent from whatever arguments the enclosing function has. No matter what my tests sends to the function, the call will most likely succeed. In order to make it fail, the test has to either make sure the test process does not have read access to a part of the working directory path, or has been removed. This could be hard to reproduce, or at least take a lot of custom wrapping code to get right without affecting other tests or be guaranteed to work on other systems.

However, those two cases might very well occur in real use of the code, and I would like to make sure the error handling is working as expected. Ideally the test should be able to provoke the error in a way that can be used for any standard library or system call, and not rely on writing lots of code just to test a single point of failure.

To do this, I came up with a simple solution. I create a mock library which is linked last in the list of libraries when linking the final test executable. The mock library adds a mock/proxy implementation of the standard library function, and use available platform support calls (like dlsym or GetProcAddress) to locate the real entry point of the standard library implementation of the function and depending on a toggle either call the real implementation, or produce the wanted error.

The test code then only has to call a function in the mock library to toggle the wanted error, execute the test, and then toggle off the mock implementation causing the real implementation to be executed in the next call. This can easily be reproduced for other standard library calls in an identical fashion (but with separate mock functions). For getcwd the mock wrappers could look like this:

static bool getcwd_is_mocked;
static char* getcwd_ret;
static int getcwd_err;

void
getcwd_mock(char* ret, int err) {
    getcwd_is_mocked = true;
    getcwd_ret = ret;
    getcwd_err = err;
}

void
getcwd_unmock(void) {
    getcwd_is_mocked = false;
}

char*
getcwd(char* arg0, size_t arg1) {
    if (getcwd_is_mocked) {
        errno = getcwd_err;
        return getcwd_ret;
    }
    static void* real_getcwd = 0;
    if (!real_getcwd)
        real_getcwd = dlsym(RTLD_NEXT, "getcwd");
    return (*(char* (*)(char*, size_t))real_getcwd)(arg0, arg1);
}
The test code could then be:

getcwd_mock(0, EACCESS);
char* ret = function_we_want_to_test(arg);
getcwd_unmock();
// verify that ret is 0
// verify that errno is EACCESS

A couple of caveats:
  • The test is inherently aware of the implementation to test, and actually testing not the function as in given input results in the expected output, but rather that external conditions affect the expected implementation in the correct way. The function is no longer a black box, and the implementation cannot change without invalidating the test.

  • Depending on the implementation, it can be hard to verify that the expected error path was entered. Maybe the success path can return the same value? But at least code coverage should show that the error path was executed.

  • Link order will be important. By placing the mock library last it should resolve any references to the mocked entry points from the standard library.

16 March, 2017

A faster memory allocator - rpmalloc

Repository: https://github.com/rampantpixels/rpmalloc

We just released our new memory allocator, rpmalloc, to the public domain. It is designed to be faster than most popular memory allocators like tcmalloc, hoard, ptmalloc3 and others. We also believe the implementation to be easier to read and modify compared to these allocators, as it is a single source file of ~1300 lines of C code. And it is in the public domain - use it without any restrictions.

Performance

Contained in the repository is a benchmark utility that performs interleaved allocations (both aligned to 8 or 16 bytes, and unaligned) and deallocations (both in-thread and cross-thread) in multiple threads. It measures number of memory operations performed per CPU second, as well as memory overhead by comparing the virtual memory mapped with the number of bytes requested in allocation calls. The setup of number of thread, cross-thread deallocation rate and allocation size limits is configured by command line arguments.

Below is an example performance comparison chart of rpmalloc and other popular allocator implementations.

This example chart shows benchmarks results when running the benchmark suite on a 8-core Windows 10 machine (crt is the Microsoft standard c runtime malloc implementation).

Implementation details

The allocator is based on 64k alignment, where all runs of memory pages are mapped to 64KiB boundaries. On Windows this is automatically guaranteed by the VirtualAlloc granularity, and on mmap systems it is achieved by atomically incrementing the address where pages are mapped to. By aligning to 64KiB boundaries the free operation can locate the header of the memory block without having to do a table lookup (as tcmalloc does) by simply masking out the low 16 bits of the address.

Memory blocks are divided into three categories. Small blocks are [16, 2032] bytes, medium blocks (2032, 32720] bytes, and large blocks (32720, 2097120] bytes. The three categories are further divided in size classes.

Small blocks have a size class granularity of 16 bytes each in 127 buckets. Medium blocks have a granularity of 512 bytes, 60 buckets. Large blocks have a 64KiB granularity, 32 buckets. All allocations are fitted to these size class boundaries (an allocation of 34 bytes will allocate a block of 48 bytes). Each small and medium size class has an associated span (meaning a contiguous set of memory pages) configuration describing how many pages the size class will allocate each time the cache is empty and a new allocation is requested.

Spans for small and medium blocks are cached in four levels to avoid calls to map/unmap memory pages. The first level is a per thread single active span for each size class. The second level is a per thread list of partially free spans for each size class. The third level is a per thread list of free spans for each number of pages in the span configuration. The fourth level is a global list of free spans for each number of pages in the span configuration. Each cache level can be configured to control memory usage versus performance.

Each span for a small and medium size class keeps track of how many blocks are allocated/free, as well as a list of which blocks that are free for allocation. To avoid locks, each span is completely owned by the allocating thread, and all cross-thread deallocations will be deferred to the owner thread.

Large blocks, or super spans, are cached in two levels. The first level is a per thread list of free super spans. The second level is a global list of free super spans. Each cache level can be configured to control memory usage versus performance.

Support us

If you find this useful, please consider our Patreon - https://www.patreon.com/rampantpixels

09 August, 2016

Code coverage

A powerful tool that will help you write better quality code is measuring code coverage. This post will explain the basics how I use this in my foundation library project (https://github.com/rampantpixels/foundation_lib) written in C, but the principles apply to other languages and toolchains as well. All code I publish is released under public domain and free to use for any purpose.

Code coverage measures how many times each line of code is executed while running your test suite. By looking at the lines that have not been executed you can find potential errors in your code or learn which test cases that needs to be improved in order to test all code paths. I use the free service at https://codecov.io to visualize the results.

For an example, look at https://goo.gl/TtNJl1 to see the coverage results of a module in the library. The lines that have been executed at least once are marked in green, the lines that have never been executed are marked in red, and the lines that are not generating any instructions are unmarked.

Coverage is pretty good, but in the function profile_end_block there is a while loop marked with the comment "Walk sibling list backwards" that is never executed.



Is this dead code that can be removed (as in, will this case never happen due to logic in other parts of the code) or are the test cases lacking the proper tests? If the latter, we have no idea if the code actually works or not, since it has not been executed. Finding these untested parts of the code is that goal of code coverage analysis.

If you have an already existing code base it might seem a daunting task to start using code coverage as you will most likely find many parts of the code which is not covered. But once you find an fix the first bug in one of these dark areas of the code it will be worth it! It's gamification at its best, you will work hard to reach that elusive 100% coverage, and your code quality will rise quickly.

In order to generate the code coverage measurements I use the built-in functionality of the clang compiler by passing the "--coverage" argument to compiler and linker. When the code is compiled a .gcno metadata file is generated by the compiler for each object file, and once the final test case binary is executed it will generate a corresponding .gcda coverage data file.



These files can then be parsed together with the corresponding source file to find the execution count per line per file using the llvm-cov tool. This tool can output a gcov text file with the wanted data (similar/compatible to what the gcc toolchain also uses).

I wrote two python scripts to do the job invoking llvm-cov, parsing these gcov files and upload the results to codecov.io. Read a gcov file at https://goo.gl/bH4AUm, invoke llvm-cov and build a report for codecov.io at https://goo.gl/bH4AUm.

As a closing remark also note that code coverage can be used with profile guided optimization by feeding the coverage data from your final executable back to the compiler. But this is a topic for another post.

31 July, 2014

Heroines


A good friend of mine is creating a touchpad game and chose to change the main character from a passive anonymous guy to an active girl. Awesome!

I love the design and its a great example on how you can create an obviously female character without resorting to using stereotypic design choices such as broken armor.

Take the time to check out the game in it’s current state at gnbw.com

(Reblogged from my tumblr: maniccoder.tumblr.com)

07 June, 2014

Rampant Kittens

Just promoting myself a bit here. We finally managed to get our little block drop game Rampant Kittens published on all our major platforms. Try it out!


iPhone/iPad: iTunes App Store
Android: Google Play
MacOS X: Mac App Store
Windows: Our website

10 May, 2014

Rovio Game Jam

I participated in the 12 hour Rovio Game Jam yesterday together with a friend, and the theme of the jam was "eqality". So we created a game called Agenda about distributing wealth and resources between cities. The end result was good enough to earn us a second place in the competition, and we'll polish it up and release on Android/iOS tablets at some point.

26 April, 2014

SublimeText & clang on Windows

After getting Intel compiler to play nice with SublimeText and SCons on Windows, the next target was getting it to use clang. The LLVM environment on Windows requires the MinGW base package for headers and libs, and I decided to use the MinGW-x64 prebuilt mingw-builds distribution from http://mingw-w64.sourceforge.net/download.php#mingw-builds

However, the headers do not play nice with clang and -Wall, with a bunch of typedef and macro redefinitions. I ended up adding

env.Append( CFLAGS=['-Wno-ignored-attributes', '-Wno-typedef-redefinition', '-Wno-undef',
'-Wno-unknown-pragmas', '-Wno-redundant-decls', '-Wno-shadow'] )

to my SConscript environment setup in order to get it to build, only to be greeted with a bunch of alignmen cast compilation warnings and then multiple definition errors when linking

lib\win64\debug/libfoundation.a(log.o): In function `GetCurrentFiber':
D:\dev\mingw\include/winnt.h:8139: multiple definition of `GetCurrentFiber'
lib\win64\debug/libfoundation.a(main.o):D:\dev\mingw\include/winnt.h:8139: first defined here
lib\win64\debug/libfoundation.a(log.o): In function `GetFiberData':
D:\dev\mingw\include/winnt.h:8140: multiple definition of `GetFiberData'

More to follow