About a year ago I was having a discussion with my friend Crutcher when he suggested that one could hot-swap versions of a running program. This post describes my implementation of just such a thing.

Why would you hot-swap? One of the major benefits of hotswapping is that the new version of the program will have access to all of the old version’s file-descriptors. This means that any files, sockets, or pipes that the previous version currently had open can still be open. For example, if one was careful, you could hotswap an application that was in the middle of serving a very large file to a user without him being aware that anything happened.

Before we begin discussing how this should work, let’s look at some of the problems. Sure we get file descriptors, but what about all of our state? Well, this is a problem. We cannot easily take our state with us. Since we’re updating versions here, you want to be particularly sure you only take state that you need. To do this, I would recommend using a serialization library for C. A bit of Googling showed me this one, TPL, though I haven’t tried it yet. For our example here, we’ll just manually move the only pieces of state we care about: a counter and a file descriptor to a file we’re currently writing to.

The basic idea of what’s going to happen is that we will create a pair of pipes and then fork(). The child process will hold the pipe that does the writing and the parent the one that does the reading. Now, the parent will exec. This is a bit odd. Normally when you fork, then exec, it’s the child process which does the exec. However, here we really want the new version of the program to have access to all of the old file descriptors. Luckily, execl preserves these. As an added benefit, the program gets the exact same process ID.

So, let’s look at the important bits of the hot-swap (reader and writer are the file descriptors for the pipe):

unsigned int outputFD = fileno(outputFile);

if(fork()) {
  /* I am the parent. */
  char readBuf[20] = {0};

  close(writer);
  sprintf(readBuf, "%d", reader);

  execl("./newbinary", "--hotswapping", readBuf, (char*)0);
  exit(0);
} else {
  /* I am the child.*/
  FILE *outputStream = fdopen(writer, "w");
  close(reader);

  fprintf(outputStream, "%d\n", i);
  fprintf(outputStream, "%u\n", (unsigned int) outputFD);
  fclose(outputStream);
  exit(0);
}

First, let’s look at what the parent process does. It simply closes its “writer” since it will never need to write to the pipe then it execs “newbinary” which is the new version of the program. It does so with a flag “–hotswapping”. This flag indicates another parameter will follow which is the file descriptor for the “read” end of the pipe we created. We do this so that the new binary can then get the state serialized across the pipe from the old binary.

Now, onto the child process. Line 32 creates a file handler from the file descriptor which is the “write” end of the pipe. Why? Because I’m lazy and I would prefer to work with fprintf() to write(). Now that we have this file handler, we can fprintf() directly to it and serialize the state we want. In this contrived case the only state I care about is my counter variable and the file descriptor of my output file. Line 19 gives me the descriptor from the handler using int fileno(FILE *).

So, to recap, we fork() then the parent exec’s to the new version of the binary and the child writes any relevant state to a pipe which the new binary is listening to.

Now, let’s look at what has to exist in the new binary. The new binary must recognize the argument “–hotswapping” which passes along the file descriptor of the “read” pipe. The following, in newversion.c does just this:

for(i = 0; i < argc; i++) {
  if(!strcmp(argv[i], "--hotswapping")) {
    int reader = atoi(argv[++i]);
    inputStream = fdopen(reader, "r");
  }
}

Notice that Line 17 does something interesting. It converts the file descriptor back to a file handler using fdopen(int, char*). Thus we can use this pipe just like we were reading from a file. So, now we can use fscanf to read from the pipe instead of having to worry about read() and buffers. This is done starting at line 21:

fscanf(inputStream, "%d", &i);
fscanf(inputStream, "%u", &outputFD);
fclose(inputStream);
outputFile = fdopen(outputFD, "w");

Once again, at line 24, we turn the file descriptor we read from the pipe back into a file handler. Now, we can resume writing to it, just as we did before. It will continue to append to the end of the file.

The files which implement this are available as gists here:

• Makefile
• original.c
• newversion.c

The output when run for 11 seconds is:

gcc -Wall -pedantic -o newbinary newversion.c
gcc -Wall -pedantic -o example original.c
./example
Original:       1 My PID=27272
Original:       2 My PID=27272
Original:       3 My PID=27272
Original:       4 My PID=27272
Original:       5 My PID=27272
New Binary:     6 My PID=27272
New Binary:     7 My PID=27272
New Binary:     8 My PID=27272
New Binary:     9 My PID=27272
New Binary:     10 My PID=27272
New Binary:     11 My PID=27272

Episode 2: hiding your data

Let’s consider a contrived example where you are representing people and their relationships. We want to represent a person’s name, social security number, address, and have pointers to mother and father.

typedef struct Person {
  char *name;
  char *address;
  int ssn;
  Person *mother;
  Person *father;
} Person;

Now, let’s say that we have some library which will create a queriable tree for us.

Person *mandy = insertPerson("Mandy", \
                  123331234, "Hut #13" 0, 0);
Person *naughtius = insertPerson("Naughtius", \
                  349830123, "Centurianville #2", 0, 0);
Person *brian = insertPerson("Brian", \
                  593013297, "Hut #13", mandy, naughtius);

This is all well and good. But there’s a problem. The user of this library can do something like this:

Person *mary = insertPerson("Mary", \
                  012309821, "Bethleham", 0, 0);
brian->mother = mary;

There might possibly be a use-case where we want to allow this to happen, but in general this isn’t desirable whatsoever. We really want to keep the fields mother, father, and ssn immutable. We can do this in the following way:

/* FILE: library.h */
typedef struct Person {
  char *name;
  char *address;
} Person;

int getSSN(Person *);
Person *getMother(Person *);
Person *getFather(Person *);
Person *insertPerson(char *, int, char *, Person*, Person*);

Now we have a struct Person which exposes only information that we will allow to be mutable. How can we use this cleanly and effectively? We define the following:

/* FILE: library.c */
#include "library.h"
typedef struct privatePerson {
  Person p;
  int ssn;
  privatePerson *mother;
  privatePerson *father;
} privatePerson;
...

How does this help us? First, consider the following:

privatePerson *mary = ...;
Person *mom = (Person *) mary;

What will happen here? First, recall how struct layout works. Since Person p is the first entry in struct privatePerson then the offset in the privatePerson struct is 0. This means that the memory location of Person p is the same as the struct privatePerson which contains it. So, when we cast to the Person pointer we are, in fact pointing at a Person object. So, insertPerson(...) will use a struct privatePerson internally but will return a struct Person. As will getMother(...).

/* FILE: library.c */
...
Person *getMother(Person *p) {
  privatePerson *who = (privatePerson *) p;
  return (Person *) who->mother;
}

This example illustrates how we can also cast back to a privatePerson from a Person. Note that this REQUIRES that the pointer to the struct Person also be a pointer to a struct privatePerson, i.e. you’ve already cast it once. We can’t ensure that our user will never malloc his own struct Person. The best we can do is provide factories for construction (insertPerson above) and strongly document that doing so is unsupported and will lead to undefined behavior.

Because struct privatePerson is defined within library.c, it won’t be visible to anyone who includes library.h. Just like with the previous post on opaque pointers, this isn’t magic. The user can still opt-in to violate our model by including his own definition of a privatePerson struct and casting back to it. Though hopefully by doing so the user will be perfectly aware that he’s breaking our API and thus is writing code that could potentially break in the next minor point release of the library.

I’ve spent my entire adult life in academia. For some reason academia, even in software engineering courses, doesn’t really harp on best practices or good patterns to know. It is possible that some do and that I’ve just missed it since I specialized in theory. So, this article will be the first in a larger category of articles which will describe patterns and techniques that I should have known but didn’t.

Episode 1: opaque pointers

I don’t care what anyone says. C is a great language. About a year ago I undertook the task of implementing a Fibonacci heap for use in an empirical analysis of two labeled graph algorithms. I put the code away months and months ago, but luckily I just found out that I got some CPU time on a very prestigious cluster so I’ve been reworking the implementations to collect better statistics. Also, since I’m finally going to do this analysis and it’s going to be published (at least in my dissertation) then I will most definitely release all of the code so that the experiments can be replayed and verified. So, since other people will look at this code I’ve spent several hours over the last few days cleaning it up and making the interfaces more reasonable. This lead me to actually pulling my fibheap out into its own stand alone project.

The fibheap isn’t ready for GitHub just yet (though look for it soon), but I’ve been working on the API and learning a lot about how this kind of thing should work. The user should be completely unaware of the internal structure of the data structure. He shouldn’t be able to mutate it in any way except through the accessors that the API provides. Though, sometimes he will need to hold pointers to particular elements in the heap (for DecreaseKey calls). This means that we need some way of providing access to elements without giving away any of our top-secret structure. So, the very simple concept that I should have known about: opaque pointers.

The crux of the matter is to separate declaration from definition just like we were always told (except in the case of templated classes… sigh). In the example of the fibheap, we want the user to have a handle to the fibheap but to otherwise not be able to affect the heap except through the API functions. So, we do this:

/* FILE: fibheap.h */
typedef struct FibHeap FibHeap;

FibHeapElement *fibHeapGetRoot(FibHeap*);
unsigned int fibHeapGetSize(FibHeap*);

And that’s it. There is no definition of the structure here, only a declaration of it. Then:

/* FILE: fibheap.c */
struct FibHeap {
  FibHeapElement *root;
  unsigned int size;
};

Because only the declaration is in the header, whenever the user does #include "fibheap.h" he only gets the name of the struct, not the layout. Thus the user cannot access either of the fields without the accessor functions fibHeapGetRoot(FibHeap*) and fibHeapGetSize(FibHeap*). No instantiation for you! (caveat: the user could easily define the struct himself and have access to the internals of the structure. This is the kind of hard opt-in that hopefully makes it clear to the user that he’s violating the spirit of the API and that this will not necessarily be stable with future versions.)

So, to summarize:

The next installment will be of a couple of ways that you can provide partial information to the user instead of none. Stay tuned!