Posts for 2013 February

Powerpoint monkey

Post by Nico Brailovsky @ 2013-02-28 | Permalink | Leave a comment

I doubt this announcement will be of much use to anyone, but I've uploaded most of my latex presentations to my github repo (those for which I found the source code, anyway).

At least it's a great way to see crappy latex code which probably hasn't compiled in newer versions of latex for at least a couple of years.


C++ exceptions under the hood 4: catching what you throw

Post by Nico Brailovsky @ 2013-02-26 | Permalink | Leave a comment

In this series about exception handling, we have discovered quite a bit about exception throwing by looking at compiler and linker errors but we have so far not learned anything yet about exception catching. Let's sum up the few things we learned about exception throwing:

Quite simple so far, but exception catching is a bit more complicated, specially because it requires certain degree of reflexion (that is, the ability of a program to analyze its own source code). Let's keep on trying our same old method, let's add some catch statements throughout our code, compile it and see what happens:

#include "throw.h"
#include 
// Notice were adding a second exception type
struct Fake_Exception {};
void raise() {
    throw Exception();
}
// We will analyze what happens if a try block doesnt catch an exception
void try_but_dont_catch() {
    try {
        raise();
    } catch(Fake_Exception&) {
        printf("Running try_but_dont_catch::catch(Fake_Exception)\n");
    }
    printf("try_but_dont_catch handled an exception and resumed execution");
}
// And also what happens when it does
void catchit() {
    try {
        try_but_dont_catch();
    } catch(Exception&) {
        printf("Running try_but_dont_catch::catch(Exception)\n");
    } catch(Fake_Exception&) {
        printf("Running try_but_dont_catch::catch(Fake_Exception)\n");
    }
    printf("catchit handled an exception and resumed execution");
}
extern "C" {
    void seppuku() {
        catchit();
    }
}

Note: You can download the full sourcecode for this project in my github repo.

Just like before, we have our seppuku function linking the C world with the C++ world, only this time we have added some more function calls to make our stack more interesting, plus we have added a bunch of try/catch blocks so we can analyze how does libstdc++ handles them.

And just like before, we get some linker errors about missing ABI functions:

> g++ -c -o throw.o -O0 -ggdb throw.cpp
> gcc main.o throw.o mycppabi.o -O0 -ggdb -o app
throw.o: In function try_but_dont_catch():
throw.cpp:12: undefined reference to__cxa_begin_catch
throw.cpp:12: undefined reference to __cxa_end_catch
throw.o: In functioncatchit():
throw.cpp:20: undefined reference to __cxa_begin_catch
throw.cpp:20: undefined reference to__cxa_end_catch
throw.o:(.eh_frame+0x47): undefined reference to `__gxx_personality_v0
collect2: ld returned 1 exit status

Again we see a lot of interesting stuff going on here. The calls to __cxa_begin_catch and __cxa_end_catch are probably something we could have expected: we don't know what they are yet, but we can presume they are the equivalent of the throw/__cxa_allocate/throw conversions (you do remember that our throw keyword got translated to a pair of __cxa_allocate_exception and __cxa_throw functions, right?). The __gxx_personality_v0 thing is new, though, and the central piece of the next few articles.

What does the personality function do? We already said something about it on the introduction to this series but we will be looking into it with some more detail next time, together with our new two friends, __cxa_begin_catch and __cxa_end_catch.


Bebugging / Fault injection

Post by Nico Brailovsky @ 2013-02-21 | Permalink | Leave a comment

Releasing any software with a degree of confidence on its quality can be a difficult task. A way to improve this confidence is adding test. Easy enough, but then how do you know if you are actually testing what needs to be tested? Metrics like code coverage are very helpful but they also provide a false sense of security that can be even worse than having no unit testing at all.

One way of determining how reliable your testing suit is, is to test your testing suit. No, not by writing more tests but by writing more bugs!

The idea is simple: give your code to someone who is not a programmer on the project, someone who can know nothing about the implicit assumptions and preconditions you and your team mates already have about the code, the same assumptions and preconditions necessary to make stuff don't crash. Ask him to break things. Nothing too fancy, only subtle stuff; a memory leak over there, a sign vs unsigned comparison over here, an equal changed by a non-equal in an if (and please do it in a branch!).

Once you get a faulty branch of your project, try to see how many of the bugs you can detect using your testing suite (yes, valgrind should probably be part of your testing suit, albeit not a unit-test). No diffs, please.

Seeing how many bugs go unnoticed on a fault injection session can give you an idea of how comprehensive your unit tests are. It can be a very humbling experience, too.

You can find more information about bebugging in Wikipedia.


C++ exceptions under the hood 3: an ABI to appease the linker

Post by Nico Brailovsky @ 2013-02-19 | Permalink | Leave a comment

On our journey to understand exceptions we discovered that the heavy-lifting is done in libstdc++ as specified by the C++ ABI. Reading some linker errors we deduced last time that for handling exceptions we need help from the C++ ABI; we created a throwing C++ program, linked it together with a plain C program and found that the compiler somehow translated our throw instruction into something that is now calling a few libstd++ functions to actually throw an exception. Lost already? You can check the sourcode for this project so far in my github repo.

Anyway, we want to understand exactly how an exception is thrown, so we will try to implement our own mini-ABI, capable of throwing an exception. To do this, a lot of RTFM is needed, but a full ABI interface can be found here, for LLVM. Let's start by remembering what those missing functions are:

> gcc main.o throw.o -o app
throw.o: In function foo()':
throw.cpp:4: undefined reference to__cxa_allocate_exception'
throw.cpp:4: undefined reference to __cxa_throw'
throw.o:(.rodata._ZTI9Exception[typeinfo for Exception]+0x0): undefined reference tovtable for __cxxabiv1::__class_type_info'
collect2: ld returned 1 exit status

__cxa_allocate_exception

The name is quite self explanatory, I guess. __cxa_allocate_exception receives a size_t and allocates enough memory to hold the exception being thrown. There is more to this that what you would expect: when an exception is being thrown some magic will be happening with the stack, so allocating stuff here is not a good idea. Allocating memory on the heap might also not be a good idea, though, because we might have to throw if we're out of memory. A static allocation is also not a good idea, since we need this to be thread safe (otherwise two throwing threads at the same time would equal disaster). Given these constraints, most implementations seem to allocate memory on a local thread storage (heap) but resort to an emergency storage (presumably static) if out of memory. We, of course, don't want to worry about the ugly details so we can just have a static buffer if we want to.

__cxa_throw

The function doing all the throw-magic! According to the ABI reference, once the exception has been created __cxa_throw will be called. This function will be responsible of starting the stack unwinding. An important effect of this: __cxa_throw is never supposed to return. It either delegates execution to the correct catch block to handle the exception or calls (by default) std::terminate, but it never ever returns.

vtable for __cxxabiv1::__class_type_info

A weird one... __class_type_info is clearly some sort of RTTI, but what exactly? It's not easy to answer this one now and it's not terribly important for our mini ABI; we'll leave it to an appendix for after we are done analyzing the process of throwing exceptions, for now let's just say this is the entry point the ABI defines to know (in runtime) whether two types are the same or not. This is the function that gets called to determine whether a catch(Parent) can handle a throw Child. For now we'll focus on the basics: we need to give it an address for the linker (ie defining it won't be enough, we need to instantiate it) and it has to have a vtable (that is, it must have a virtual method).

Lot's of stuff happen on these functions, but let's try to implement the simplest exception thrower possible: one that will call exit when an exception is thrown. Our application was almost OK but missing some ABI-stuff, so let's create a mycppabi.cpp. Reading our ABI specification we can figure out the signatures for __cxa_allocate_exception and __cxa_throw:

#include 
#include 
#include 
namespace __cxxabiv1 {
    struct __class_type_info {
        virtual void foo() {}
    } ti;
}
#define EXCEPTION_BUFF_SIZE 255
char exception_buff[EXCEPTION_BUFF_SIZE];
extern "C" {
void __cxa_allocate_exception(size_t thrown_size)
{
    printf("alloc ex %i\n", thrown_size);
    if (thrown_size > EXCEPTION_BUFF_SIZE) printf("Exception too big");
    return &exception_buff;
}
void __cxa_free_exception(void thrown_exception);
#include 
void __cxa_throw(
          void thrown_exception,
          struct type_info tinfo,
          void (dest)(void))
{
    printf("throw\n");
    // __cxa_throw never returns
    exit(0);
}
} // extern "C"

Note: You can download the full sourcecode for this project in my github repo.

If we now compile mycppabi.cpp and link it with the other two .o files, we'll get a working binary which should print "alloc ex 1\nthrow" and then exit. Pretty simple, but an amazing feat nonetheless: we've managed to throw an exception without calling libc++. We've written a (very small) part of a C++ ABI!

Another important bit of wisdom we gained by creating our own mini ABI: the throw keyword is compiled into two function calls to libstdc++. No voodoo there, it's actually a pretty simple transformation. We can even disassemble our throwing function to verify it. Let's run this command "g++ -S throw.cpp".

seppuku:
.LFB3:
    [...]
    call    __cxa_allocate_exception
    movl    $0, 8(%esp)
    movl    $_ZTI9Exception, 4(%esp)
    movl    %eax, (%esp)
    call    __cxa_throw
    [...]

Even more magic happening: when the throw keyword gets translated into these two calls, the compiler doesn't even know how the exception is going to be handled. Since libstdc++ is the one defining __cxa_throw and friends, and libstdc++ is dynamically linked on runtime, the exception handling method could be chosen when we first run our executable.

We are now seeing some progress but we still have a long way to go. Our ABI can only throw exceptions right now. Can we extend it to handle a catch as well? We'll see how next time.


Monitor file changes on a CLI

Post by Nico Brailovsky @ 2013-02-14 | Permalink | Leave a comment

The other day I had a problem with a config file being overwritten. Some process, I did not know which one, was overwriting a configuration file I manually changed. Annoyed by this, I started looking for the culprit. lsof was no good, because that would list the open files; this process would most likely just open the file, write to it and then close it again. My chances of ever catching this process in the act were nil. Luckily I found auditd. Install it like this:

sudo apt-get install auditd

Then to monitor a file you can use the following command:

sudo auditctl -w $FILE -p war

Wait until $FILE has changed, then execute this command to get the results:

ausearch -f $FILE

Voila, now you have your culprit. Kill -9 at will.


C++ exceptions under the hood II: a tiny ABI

Post by Nico Brailovsky @ 2013-02-12 | Permalink | Leave a comment

If we are going to try and understand why exceptions are complex and how do they work, we can either read a lot of manuals or we can try to write something to handle the exceptions ourselves. Actually, I was surprised by the lack of good information on this topic: pretty much everything I found is either incredibly detailed or very basic, with one exception or two. Of course there are some specifications to implement (most notably the ABI for c++ but we also have CFI, DWARF and libstdc) but reading the specification alone is not enough to really learn what's going on under the hood.

Let's start with the obvious then: wheel reinvention! We know for a fact that plain C doesn't handle exceptions, so let's try to link a throwing C++ program with a plain C linker and see what happens. I came up with something simple like this:

#include "throw.h"
extern "C" {
    void seppuku() {
        throw Exception();
    }
}

Don't forget the extern stuff, otherwise g++ will helpfully mangle our little function's name and we won't be able to link it with our plain C program. Of course, we need a header file to "link" (no pun intended) the C++ world with the C world:

struct Exception {};
#ifdef __cplusplus
extern "C" {
#endif
    void seppuku();
#ifdef __cplusplus
}
#endif

And a very simple main:

#include "throw.h"
int main()
{
    seppuku();
    return 0;
}

What happens now if we try to compile and link together this frankencode?

> g++ -c -o throw.o -O0 -ggdb throw.cpp
> gcc -c -o main.o -O0 -ggdb main.c

Note: You can download the full sourcecode for this project in my github repo.

So far so good. Both g++ and gcc are happy in their little world. Chaos will ensue once we try to link them, though:

> gcc main.o throw.o -o app
throw.o: In function foo()':
throw.cpp:4: undefined reference to__cxa_allocate_exception'
throw.cpp:4: undefined reference to __cxa_throw'
throw.o:(.rodata._ZTI9Exception[typeinfo for Exception]+0x0): undefined reference tovtable for __cxxabiv1::__class_type_info'
collect2: ld returned 1 exit status

And sure enough, gcc complains about missing C++ symbols. Those are very special C++ symbols, though. Check the last error line: a vtable for cxxabiv1 is missing. cxxabi, defined in libstdc++, refers to the application binary interface for C++. So now we have learned that the exception handling is done with some help of the standard C++ library with an interface defined by C++'s ABI.

The C++ ABI defines a standard binary format so we can link objects together in a single program; if we compile a .o file with two different compilers, and those compilers use a different ABI, we won't be able to link the .o objects into an application. The ABI will also define some other formats, like for example the interface to perform stack unwinding or the throwing of an exception. In this case, the ABI defines an interface (not necessarily a binary format, just an interface) between C++ and some other library in our program which will handle the stack unwinding, ie the ABI defines C++ specific stuff so it can talk to non-C++ libraries: this is what would enable exceptions thrown from other languages to be caught in C++, amongst other things.

In any case, the linker errors are pointing us to the first layer into exception handling under the hood: an interface we'll have to implement ourselves, the cxxabi. For the next article we'll be starting our own mini ABI, as defined in the C++ ABI.


Quick C/C++ reference on the console

Post by Nico Brailovsky @ 2013-02-07 | Permalink | Leave a comment

What do you usually do when you don't remember whether fp is the first argument for fprintf or for fwrite? (Hint: it's the first argument for one, the last for the other. Handy, huh?). Well, there's no need to go and check the answer on Google, just sudo apt-get install manpages-dev and then do "man fprintf" or "man fwrite".

Note: you might also want posix-dev to check stuff like htons.


C++ exceptions under the hood

Post by Nico Brailovsky @ 2013-02-05 | Permalink | Leave a comment

Everyone knows that good exception handling is hard. Reasons for this abound, in every single layer of an exception "lifetime": it's hard to write exception safe code, an exception might be thrown from unexpected places (pun intended!), it's can be complicated to understand badly designed exception hierarchies, it's slow because a lot of voodoo is happening under the hood, it's dangerous because improperly throwing an exception might call the unforgiving std::terminate. And although anyone who might have had to battle an "exceptional" program might know this, the reasons for this mess are not widespread knowledge.

The first question we need to ask ourselves is then, how does it all work. This is the first article on a long series, in which I'll be writing about how exceptions are implemented under the hood in c++ (actually, c++ compiled with gcc on x86 platforms but this might apply to other platforms too). On these articles the process of throwing and catching an exception will be explained with quite a lot of detail, but for the impatient people here is a small brief of all the articles that will follow: how is an exception thrown in gcc/x86:

  1. When we write a throw statement, the compiler will translate it into a pair of calls into libstdc++ functions that allocate the exception and then start the stack unwinding process by calling libstdc.
  2. For each catch statement, the compiler will write some special information after the method's body, a table of exceptions this method can catch and a cleanup table (more on the cleanup table later).
  3. As the unwinder goes through the stack it will call a special function provided by libstdc++ (called personality routine) that checks for each function in the stack which exceptions can be caught.
  4. If no matching catch is found for the exception, std::terminate is called.
  5. If a matching catch is found, the unwinder now starts again on the top of the stack.
  6. As the unwinder goes through the stack a second time it will ask the personality routine to perform a cleanup for this method.
  7. The personality routine will check the cleanup table on the current method. If there are any cleanup actions to be run, it will "jump" into the current stack frame and run the cleanup code. This will run the destructor for each object allocated at the current scope.
  8. Once the unwinder reaches the frame in the stack that can handle the exception it will jump into the proper catch statement.
  9. Upon finishing the execution of the catch statement, a cleanup function will be called to release the memory held for the exception.

This already looks quite complicated and we haven't even started; that was but a short and inaccurate description of all the complexities needed to handle an exception.

To learn about all the details that happen under the hood on the next article we will start to implement our own mini libstdlibc++. Not all of it though, only the part that handles exceptions. Actually not even all of that, only the bare minimum we need to make a simple throw/catch statement work. Some assembly will be needed, but nothing too fancy. A lot of patience will be required, I'm afraid.

If you are too curious and want to start reading about exception handling implementation then you can start here, for a full specification of what we are going to implement on the next few articles. I'll try to make these articles a bit more didactic and easier to follow though, so see you next time to start our ABI!

** Disclaimer note: I'm in no way versed on the magic going on when an exception is thrown. These series will be about trying to demystify the stuff going on under the hood and learning something in the process, and while I hope some of it will be correct I have no doubts there will be a lot of subtleties not quite right. Let me know if you think I should correct something **