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.

7 comments:

Tim Lovorn said...

Man, some of the subtleties of C throw me for a loop. I don't understand why you use char* for the function pointers in createAdder(). I'm amazed C will let you do it at all, but is there a technical reason for this?

Anonymous said...

char is guaranteed to be 1 byte. doing operations on char*'s guarantees you're dealing with bytes

Anonymous said...

Very bad idea! Many OSes will prevent executing from heap. And you have no guarantee that endOfAdderGeneric will be placed immediately after adderGeneric.
Ugly! Huh.

Anonymous said...

Gah. Depends on knowing the underlying compiler and architecture details, and on having them not change.

Use straight C for this sort of thing, e.g.,
http://pastebin.com/m72c604ed

Viktor Lofgren said...

Heh, this is a pretty neat hack (even though the hordes of programming.reddit.com will now whine about it, as they do with everything that comes their way). Keep up the work.

Anonymous said...

We had to solve a similar problem and tried this hack on a Opensuse 11.0 with 64 bit. On this configuration it just gives a segmentation fault instead of calling the closure. I guess the trick is so system dependent that we are out of luck.

Anonymous said...

may i know how to test this program? please...