Tuesday, October 27, 2009

"Article 9 and 10"

Yesterday evening I checked my real mailbox and I found the following surprise:
My first instinct was to call the police and tell them that some drug dealer must have stashed his stuff in my mailbox. Then I cooled down and checked the hard-to-see-in-the-picture red label and it had my address written on it; I was sure someone was playing a practical joke on me. Then I checked out the back of the label and it had the magic number 85.83 written on it. Mystery solved. While 85.83 might not mean anything to you, it was the cost of some books I ordered from Amazon a few weeks back.
Inside the dubious bag there was a normal Amazon paper box and inside the box my "*-at-work" books in good condition:On the label of the blue bag there was an yellow sticker written in a language resembling English which reads "Goods Do Not Meet The Requirement Of Article 9 and 10 Of The Contract For The Foundation Of The European Community" (verbatim). Googling for this mysterious "Contract" only returns blogposts about the same sticker. If anyone has any idea what is the deal with the weird blue bag please let me know.
Meta-blogging aside, I've started reading the interview with Jamie Zawinski in "Coders at Work" and it seems pretty good. I'll be commenting on it on the blog later on. I can't wait to read the three books.

Tuesday, September 1, 2009

Adventures in C++ land

I have recently discovered an interesting bug in a prototype implementation that I did for my research. For the current discussion, what exactly the implementation is about is irrelevant. It suffices to say that the code is C++ code.

I thought I'd share the experience so that others can avoid the same pitfall. The code in question is slightly complicated, but the problem is well illustrated by the following abstracted version:


std::vector<Foo> foos;

void bar(const Foo &foo)
{
while (*) {
foos.push_back(foo);
}
}

int main()
{
// ...
assert(foos.size() > 0);
while (*) {
bar(foos[0]);
}
}


Here "Foo" is a very well behaved user defined class, such as the favorite class of every C++ book author, the "ComplexNumber" class. The tests in the while loops are irrelevant, so I replaced them by nondeterministic tests (denoted by "*"; so just imagine for example that each loop runs for a small number of iterations).

The above code can crash. I experienced two types of crashes occurring: either the program terminates with an uncaught std::bad_alloc, or simply the program is terminated by a segfault.

So let me describe why the crash happens. The problem is that the "foo" argument is passed by reference. The std::vector class implements a variable-sized array. Therefore, when the underlying implementation of the vector runs out of space, the std::vector class
decides to allocate a bigger piece of memory, copies the old values of the vector into the newly allocated memory, and deletes the old memory.

So this entire thing could very well happen during the push_back call. But what is "foo"? Well, "foo" is exactly a reference to memory that might be deleted during the push_back call. Ooops. Accessing such memory is of course undefined behavior which means very bad things could happen. I solved the problem by passing the argument by value.

So the next time you do the classic "best practice" of passing arguments by const reference you might want to be more careful. It is interesting of course to analyze what led to this bug. One of the problems is having a global variable ("foos") which is used in an imperative fashion. This leads to the surprising sharing of state between the global variable "foos" and the local variable "foo".

The second problem is the leaky mental model that I had of the vector class. I thought of it as an array that can grow. But in fact it's not, it's an array that is sometimes replaced by a bigger array...

Also note that the bug lies entirely in the "bar" function, which is not correct in the particular case where "foo" is a reference to an element of "foos". However, the syntax of passing arguments by reference (indistinguishable from passing by value) does not help in detecting the possible bug at the point of call.

I scratched my head for a long while without finding the source of the bug. I finally installed valgrind, which is a great piece of software of course, and which I recommend whole-heartedly.

Sunday, February 1, 2009

How to Hack Closures in your C Code (or "The Closure Design-Pattern in C").

A lot of languages have support for various forms of closures.

For example, in most functional languages (Common Lisp, Scheme, Ocaml, Haskell), closures are first class citizens. In Java, you can implement them using inner classes. You can use defunctionalization to simulate closures in almost any programming language. However, for several reasons described at the end of the post, this can be impractical in some scenarios.

In this post, I'm not going to talk about any theoretical stuff. I'm going to present a hackish, evil and practical way to dynamically construct closures in C.

C already contains a restricted form of closures that come in the shape of function pointers. Essentially, a function pointer can be though of as a closure without the data. With a little care, you can use function pointers in a type unsafe (platform dependant, ready to blow up in your face) way that gets you closures.

Let's take the classical example of a closure that adds a number to another number. You might implement such a closure in Haskell in the following way:

let add x y = x + y

let adder3 = add 3

There you go: adder3 is exactly our closure: when you evaluate 'adder3 10' you get 13.

How can you do this in C?

Well, we'll start with a simple adder:

int adder3(int x)
{
 int data = 3;
 return data + x;
}

Not much of a closure, is it? What if we want to use something else instead of 3? What we would need is a function

typedef int (*adder)(int);

adder createAdder(int data)
{
  // ...
}

that returns such an adder. But you can't do this in C, because functions are not first class objects. Oh wait! Actually, in C, memory is a first class citizen, and therefore you are free to do whatever you want with it. Including, wait for this, placing code in memory and returning a pointer to it.

Without further discussion, we need the code for a generic adder function. This is not difficult to get, and we'll kindly ask the compiler to provide to us so we don't actually have to write machine code:

int adderGeneric(int x)
{
 int data = MAGIC;
 return data + x;
}

void endOfAdderGeneric() {}

There you go. The machine code for the generic adder function is now between the starting addresses of the adderGeneric and endOfAdderGeneric function. Now our createAdder function only needs to copy this code, modify the data, and return the result:

adder createAdder(int data)
{
 char *start = (char *)adderGeneric;
 char *end = (char *)endOfAdderGeneric;

 char *result = (char *)malloc(end - start);
 memcpy(result, start, end - start);
 
 char *p;
 for (p = result; ; ++p) {
  int *q = (int *)p;
  if (*q == MAGIC) {
  *q = data;
  break;
  }
 }

 return (adder)result;
}

void deleteAdder(adder a)
{
 char *m = (char *)a;
 free(m);
}

The createAdder first allocates enough memory for our adder. It knows how much it needs because (usually) C functions are laid out sequentially in memory; therefore the starting address of function endOfAdderFunction should match the end of the adderFunction.

Then it copies the code of the adderGeneric function into the newly allocated location. Now all it needs to do is set the internal data. An unsafe, platform dependant, ready to blow up in your face way to do this is to search for the constant MAGIC in the function code. When it finds this magic number, it replaces it by the actual data.

I defined MAGIC as follows:

#define MAGIC 0xAEAEAEAE

but you're free to set it to anything reasonable for your platform.

Then the pointer to the newly created block of code is returned, which should work as well as the generic adder.

To complete the example, check out the main code:

int main()
{
 adder add3 = createAdder(3);
 adder add5 = createAdder(5);
 printf("%d %d\n", add3(10), add5(10));
 deleteAdder(add3);
 deleteAdder(add5);
 return 0;
}

There you go: you have closures in C. The only question that remains is when you would want to use such a trick. The answer is: very sparingly. The above code can send you and your team in debugging hell. Any new version of the compiler might decide to optimize stuff in a different way, changing the way functions are laid out in memory and any other number of things can go wrong.

However, you might have to do this when working with legacy code. The above code was inspired by the following question asked on stackoverflow:

http://stackoverflow.com/questions/499153/

The person asking the question wants a way to register a callback function that is a member of an object. Unfortunately, there is not way to explicitly pass around the this pointer. Being unable to change the interface of the library, a quick hack like the one I described can do wonders.

I have uploaded the full code sample to pastie 376806.