C itself is a fairly straightforward language. There are no objects or templates, and FactoryFactories are probably considered forbidden in most shops. However, there are plently of ways to write object oriented code in C. Obviously, the language itself has its corner cases and we need to avoid trying to implement anything that relies on undefined behavior.

Nothing I’ll cover here is new or particularly interesting for veterans of the craft, but I felt it was a worthwhile exercise to write and benchmark.

I decided I’d like to implement a taggable counter. That is, essentially

1
2
3
4

struct taggable_counter {
    char * tag;
    uint64_t counter;
}

I need it to be both performant, since it’s a counter, and safe-ish, because I’d rather have safe strings at one point in the code than spread all throughout. I’d also like to be able to extend the library to support multiple tags in the future without changing the client code extensively.

While this example may seem a bit contrived, it should be obvious that the basic concept of an object with public and private fields is quite nice to have.

Method 1: Opaque typedefs

We could, for example, define an interface using a set of functions and a completely opaque typedef. This forces all field accesses to the struct to go through the provided helper functions and allows us to replace the implementation at any time. If you’re implementing a library for the public, this is probably the best way to go. However, it might incur an additional function call for each access to a field!

Private header

1
2
3
4
5

struct opaque_container {
    uint64_t private_counter;
    char * private_tag;
    uint64_t public_counter;
};

Public header

1
2
3
4
5
6

typedef struct opaque_container opaque_container_t;

void increment_counter_o(opaque_container_t *);
uint64_t read_counter_o(opaque_container_t *);
opaque_container_t* init_counter_o();
bool tag_counter_o(opaque_container_t *, char *);

As you can see from the header, the user is passing us a pointer to our own struct, but they cannot easily access the fields in it. In my experience, this method can be slightly opaque for the compiler optimizer, if only because the function definition for increment lives in a library and cannot be well optimized without using link time or whole program optimization.

Method 2: Public fields, private fields

It would be nice if we could allow normal access to the counter field. After all, it’s “just” a uint64_t. We can do this by providing a public struct with the fields that the user cares about or can be trusted to access correctly. Then we’ll keep private fields in a separate struct that can be accessed only by the library.

In order to accomplish this, we can nest the public data within the private struct. We’ll have to do a bit of pointer and offset arithmetic, but nothing too complicated, especially since we have the offsetof¹ macro Luckily, we’ve got offsetof to help us with this.

Private header

1
2
3
4
5

typedef struct {
    uint64_t private_counter;
    char * private_tag;
    public_data_t public_data;
} private_container_t;

Public header

1
2
3
4
5
6

typedef struct {
    uint64_t counter;
} public_data_t;

public_data_t* init_counter_c();
bool tag_counter_c(public_data_t *, char *);

As you can see from the header, the user is only passing us a pointer to the public struct. To access the private container, we do the following:

1
2
3

bool tag_counter_c(public_data_t *pub, char *tag) {
    private_container_t * container = (private_container_t *) (
        (char *)pub - offsetof(private_container_t, public_data));

However, since the exercise here was to avoid duplicating a piece of code that is very easy to screw up, it doesn’t seem like a good idea to duplicate the snippet above in each function!

Let’s try to factor it out into a function of its own.

1
2
3
4

inline private_container_t * container enclosing_container(public_data_t *pub) {
    return (private_container_t *) (
        (char *)pub - offsetof(private_container_t, public_data));
}

That wasn’t so hard. Now our usage looks like

1
2

bool tag_counter_c(public_data_t *pub, char *tag) {
    private_container_t * container = enclosing_container(pub);

This is great for our individual library with its single private structure, but what happens if we’re working on a larger software project. If we want to use this pattern, can we abstract this out so we don’t need to write the enclosing_container function over and over?

If we already had the enclosing container, maybe we could store a pointer to a function generated by a factory… Even then, we’d have to find a way to pass the proper field name to the offsetof macro. Too bad.

While C itself is straightforward, it does have a preprocessor with fairly reasonable semantics and functionality. Can we leverage the preprocessor to provide a more pleasant and safer interface for our own use?

Yes! Enter the container_of macro.

1
2
3

bool tag_counter_c(public_data_t *pub, char *tag) {
    private_container_t * container = container_of(
        pub, private_container_t, public_data);

That’s pretty good. It’s somewhere in between our specialized function and implementing the operations ourselves. What does it look like underneath?

1
2
3
4

#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
            (type *)( (char *)__mptr - offsetof(type,member) );})
#endif

So, a little more complicated, but easily testable. It’s essentially a fully parameterized version of what we wrote before. We pass in the public struct pointer, the type of our private container, and the name of the public data field within our container, obviously to be use for offset_of.

Optimization notes

I considered adding a section on benchmarking these different approaches, but every situation is unique. For example, in a simple loop based benchmark that incremented the counter argv[1] times, I noticed that the loop was completely optimized out with the public fields, but not with the opaque counter. Since we’re linking it in as a library, this makes perfect sense. This is a trivial example, but demonstrates what you can miss out on with a lack of transparancy. However, the repo ² has link time optimization enabled and adds an asm noop so the loop in the test programs is not optimized out.

With LTO, these two implementations have no statistically significant differences in running time, so I ended up leaving out the benchmarking section.

Final notes

You’ll find that using the container_of macro is a very common paradigm in larger software projects. For example, it is used in:

• linux kernel
• nodejs
• xorg
• virtually everything

though the most famous example is definitely the Linux kernel. It provides fairly good information hiding attributes, while not hindering the programmer trying to use your library - they can still treat the public struct as a regular struct, rather than as an opaque object.

Please note that all the code I wrote for this post can be accessed at this GitHub repository.