blog.s11n.net

Stupid C Tricks: Portably Passing Function Pointers via (void*)

Hello, fellow C programmers!

(If you don’t program in C (or even know what that means) then the following won’t interest you in the slightest. If you are a C programmer, it might interest you in the slightest.)

It is common for C code to use the venerable void pointer, and (despite what our OO teachings might tell us), the void pointer isn’t the bad guy. Mis-use of void pointers is the bad guy. Because there are lots of ways to abuse a void pointer, void pointers are, at least in higher-level APIs, generally to be avoided. Lower-level APIs often cannot get by without them.

Today’s talk is not about void pointers in general (there’s an awful lot to say about void!), but specifically about using a void pointer to hold a function pointer.

Did you know that passing a function pointer via a void pointer, casting that void pointer to the original function pointer, and dereferencing (i.e. calling) the casted function results in undefined behaviour? That’s what the C standard says.

What does that mean? It means the following code is invokes undefined behavhiour in any country or providence which respects the C Standard:

typedef int (*my_callback)( void * state );
my_callback cb = some_callback_function;
void * ptr = cb;
((my_callback)ptr)( ... ); // <--- undefined behaviour!

The above code is rather contrived, but it demonstrates a feature which is seen from time to time in ancient C code. It is also used in some OS-level functions which open DLLs (e.g. based on dlopen() on POSIX systems). DLL-loading systems often look for a symbol with a specific name within the DLL right after they open it. If they find it, they treat it like a function and call it. Some DLL-loading systems provide a similar feature for closing a DLL. Higher-level “plugin” systems, common in today’s applications, often use this approach to fetch a factory function from the DLL, which is then used to create an instance of the plugin.

If such systems expect their magic symbol(s) to be a function (and in my experience they do!), then they are relying on undefined behaviour. And we abhor undefined behaviour, don’t we?

There is a portable, and only slightly inconvenient, workaround. In short, we add a level of indirection between the function we want to fetch from the DLL and the symbol name the DLL-opener expects to find. That level of indirection is a tiny struct:

typedef int (*my_callback)( void * state );
typedef struct my_callback_struct {
    my_callback callback;
} my_callback_struct;

And in our DLLs we use that indirection like so:

/* implements the my_callback() interface. */
static int private_callback( void * state );
/* The symbol our DLL/plugin system will look for: */
const my_callback_struct TheExpectedSymbolName =  {private_callback};

In the DLL opening code, we look for “TheExpectedSymbolName”, but instead of casting it to a function pointer, we cast it to a my_callback_struct pointer. From that object, we can invoke its member function without invoking undefined behaviour. Obviously, if the DLL contains a non-my_callback_struct with the expected symbol name, behaviour is undefined, but the function-pointer approach has the same problem.

This approach can easily be expanded to provide open() and close() routines for plugins, or any other application-specific plugin functionality. It can be combined with macros to allow clients to easily implement a plugin by calling the macro and passing pointers to their callback implementations. Since the DLL lookup symbols must unique, however, it means we have a limitation of one logical plugin per DLL file. (That is the norm in most plugin systems, but this limitation makes it an explicitproperty of such systems.)

In C++ (as opposed to C), the ability to to construct objects and call functions during the DLL’s static initialization phase (i.e. while it’s being opened, before the DLL opener gets it back) allows for an elegant solution to all of the above-mentioned problems and limitations. We won’t go into that here, but for interested readers there is a detailed article about it, called Classloading in C++, over at http://wanderinghorse.net/computing/papers/.

Happing hacking!

—– stephan beal, 2 March 2010

Implementing not-quite-namespaces in C

Hi, all!

A few days ago i came across a trick in C. It isn’t new, but i hadn’t seen it used quite this way before and i wanted to share it…

Background: i have several mini-libraries which i tend to copy directly in to other projects. It has happened that i then use two other libraries together, and both of them internally use the same underlying mini-library. In some cases i want each to continue to use their own copy (maybe a different/incompatible version), but not collide with the other copy. Here’s one way to do it…

In the lib’s main header, before we declare any of its API:

#if !defined(MY_NS)
#  define MY_NS(X) my_namespace_prefix_ ## X
#endif

We then declare our types and functions using that macro:

int MY_NS(func1)( ... );
struct MY_NS(type1) { ... };

And throughout the implementation and client code we use:

int x = MY_NS(func1)( ... );

Each library which wants to import and rename the API then simply has to redefine MY_NS while building the included mini-library.

The major down-side is that this construct makes reading the docs through tools like doxygen more difficult.

Happy hacking!

Allocating memory in C without dynamic memory

Hi, all!

The past year or two i’ve been working on various C-based projects. Through that work i’ve taken a strong interest in conserving memory and reducing the number of calls made to make new memory available (e.g. via malloc()). For example, i’ve spent many hours optimizing the whefs embedded filesystem library to run with fewer than 2kb of dynamic memory for the average use case (and as little as 96 bytes(!!!) for a highly-optimized case).

The past few days, that latent fascination with saving calls to malloc() has culminated into a new library:

whalloc (the WanderingHorse.net Allocator) is a small C library which provides an alternative memory management approach. It is initialized with a block of client-supplied memory, typically a stack-allocated char buffer, and then it can slice up that memory and use it for allocations and deallocations. The whole process looks a bit like:

whalloc_bt pool = whalloc_bt_empty;
enum { BufLen = 1024 * 8 };
unsigned char buffer[BufLen];
whalloc_size_t blockSize = sizeof(my_type);
int rc = whalloc_bt_init(&pool, buffer, BufLen, blockSize );
if( whalloc_rc.OK != rc ) { … error … }
my_type * m = whalloc_bt_alloc(&pool, sizeof(my_type));
// ^^^ m now lives somewhere inside of buffer
…
whalloc_bt_free(&pool, m); // makes the memory available for re-use
whalloc_bt_drain(&pool); // “deallocates” all allocated objects at once

The most interesting part is how it stores its memory management information: by taking up a small slice of the memory it is managing. It needs only two bits of storage for each block of memory it manages (there are (memBufferSize/blockSize) blocks in the buffer). The allocator takes up, worst-case (block size of 1 byte), 18-19% of that memory, dropping to 11% for 2-byte blocks, 6% for 4-byte-blocks, and halving for each additional doubling of block size. With a block size of 64 bytes it uses less than 0.5% of the memory for its own purposes. If its storing only a small number of blocks (default setting=128) then it can use its own few-byte-long internal cache and must reserve none of the client’s memory for its own purposes.

For the average use case, where objects are destroyed in reverse of their allocation order, it can perform O(1) if the allocations are equal to or smaller than the defined block size. Its worst-case performance is O(N), with N being a function of the number of blocks being allocated, the total number of blocks managed, and current memory pool fill status. Deallocation is always O(N), with N being the number of blocks being deallocated. For deallocation, finding the underlying management data is always O(1) - a simple hashing operation which uniquely maps any given pointer to its memory block index.

There’s also a variant of the allocator which requires 2 bytes (instead of 2 bits) per managed block. The primary difference is that it stores the requested size of each allocation, whereas the optimized variation simply knows whether a block as a whole has been allocated or not.

The allocators optionally support a client-provided mutex, to lock the allocator, and fallback allocation/deallocation functions, which they can use if their own pool runs out of space (e.g. falling back to malloc() and free()).

For those of you interested in C, in particular in shaving off a few bytes of dynamic memory in your C apps, the code is available (it’s in the Public Domain) over on the whalloc web page:

http://fossil.wanderinghorse.net/repos/whalloc

Happy hacking!

The Chicken/Egg Scenario

The age-old question goes:

Which came first: the chicken or the egg?

And i think the point of it is that nobody really knows. Kind of like the ancient Egyptian saying, “if a tree falls in the dunes of the Sahara desert and no one hears it, did it really emit audible vibrations?” (Though the original hieroglyph looks something like a man with an axe in one hand and the other hand cupped to his ear.)

But i think there might be a solution:

A chicken, by definition, comes from an egg. Not just any egg, mind you, but a chicken egg. Thus it is impossible that the chicken came before the egg. Ergo, what laid the first chicken egg was not a chicken. That creature might indeed have been hatched from an egg, but because it cannot have been a chicken egg (as we just established), the first chicken egg still came before the first chicken.

Elementary, dear Watson!

whefs: an embedded filesystem library for C

Hi, all!

Late last year i started working on an embedded filesystem library for C. The library uses “container files” (called embedded filesystems, or EFSes), in which the client can store “files” (i call them “pseudofiles”). The API allows random read/write access to them using a flexible i/o device interface. If you’ve ever programmed with sqlite - whefs is similar in concept but creates an embedded/virtual filesystem instead an embedded/virtual SQL server.

While whefs is still beta and open for lots of experimentation, it seems to be in a usable state.

To give whefs a more public home, a couple days ago i moved whefs over from its original source repository to Google Code:

http://code.google.com/p/whefs/

The project is of course open to collaboration, and i invite any interested C hackers out there to get in touch.

Happy hacking!

Ubuntu: “it just works”

Okay, it’s time to evangelize a bit…

The past few weeks i’ve been considering buying a netbook (sub-notebook). Not because i particularly need one, but because they’re so damned cute and they’re relatively cheap nowadays. In my various train trips i’ve always found a laptop too be more trouble than they’re worth - heavy, battery-hungry, and i only end up getting 1-2 hours of use out of them per trip. i figured with a smaller device i could once again justify taking my computing on the road with me.

This morning i got up and walked about 8 miles around town, visiting just about every computer/electronics shop in central Munich (about 12 shops in total). i found only one shop which had netbooks without Windows preinstalled, and those models had only 4GB of SSD storage. Since my Dropbox has about 14GB of stuff in it, i need at least that much space on my netbook. So i gave up on the idea of buying one which came without Windows, and figured i could use an external CD drive to install Linux on whichever one i ended up getting.

After going through about a dozen stores, i ended up buying an Acer Aspire One (colored dark blue). When i got home i started puting it together and was sorely disappointed to find that it cannot read my external CD drive (which i bought for my oldest laptop, which has a flaky internal drive, and which i use to install Linux on that laptop). After a bit of googling i found a page explaining how to transfer an Ubuntu installation CD to an SD card. Some more googling revealed Ubuntu-specific pages for getting an Acer Aspire One to work, and i was a bit underwhelmed at the amount of manual hackery which was reportedly needed to get it running (or running optimally). Not really interested in spending two days hacking to make it work, i decided to try a vanilla Ubuntu install using the SD card method “just to see what happens.”

An hour later, i was online with Ubuntu 9.04 on my new netbook. i’m writing this post from the netbook, in fact, and the only thing which bugs me so far is that there is no END key (you’ve got to tap Fn-PageDown to simulate the End key).

The Windows XP installation is still there (Simone insisted that i allow it to live, so that she can use it for some of her work-related activities), and everything’s living in harmony on the spacious 160GB drive.

What surprises me the most is:

• WLAN works as-is with no driver module parameter tweaks needed. i had noticed in the Windows setup that it has a Broadcom chipset, and i’ve heard bad things about them vis-a-vis Linux, so i didn’t expect it to work. Works for me, though perhaps a bit more slowly than i would expect. Update 2 May 2009: i take that back about being slow - my speed problems appear to have been transient in nature, and i’m now getting the speeds i would expect.
• Bluetooth works. i’ve just got to press the little Bluetooth button, the hardware activates, and Ubuntu starts up a bluetooth management tool which allows me to connect to, e.g., my mobile phone. i don’t use bluetooth at all, but i love that it works.
• Even on a tiny 1024×600 screen resolution, it looks damned good. Screen space is somewhat tight, but it looks surprisingly good nonetheless.
• OMG, the builtin webcam even works using Cheese (who’s author is one of the few OSS developers i’ve had the pleasure of meeting in person).

So, chalk another one up to the Ubuntu team. And to Linus. And Daniel (author of Cheese). And the tens of thousands of people who have hacked the OS and Gnome and all these other parts over the years.

Now let’s go read up on what the optional hacks for optimizing the Acer Aspire entail…

Happy Hacking!

Extending the Google v8 JavaScript Engine

Hi, all!

In late February i happened to come across a very interesting open source project, Google’s v8 JavaScript engine. Being a long-time hacker of add-ons for the Mozilla SpiderMonkey engine, i felt compelled to try it out.

After a couple of days i was convinced that v8 was a cool platform to work with and put together a project page for my v8-related hackings:

http://code.google.com/p/v8-juice/

v8-juice (the v8 JavaScript Userland Integratable Components Emporium) is its name.

If there are any other C++/JavaScript half-breeds out there, the project is looking for talented hackers to improve and expand it.

Happy hacking!

OMFG: i am on the cover of Dr. Dobb’s Journal #416 (Feb 2009)!

Back in October i briefly met Mr. Jonathan Erickson, editor of Dr. Dobb’s Journal, and spoke to him a bit about the presentation he had made at the Qt Developer Days conference in Munich, Germany (primarily about concurrency). After he returned to the States we shared a few emails and then went around our business. He had, in one email exchange, asked if i would fill out a short questionnaire for a column DDJ does now and then to briefly present random programmers they meet. Not one to miss a good opportunity to write, i of course answered. That was, incidentally, on October 30th (my father’s birthday and the two year anniversary of my cancer diagnosis), and i hadn’t given it any thought since then. But i just learned that all that time, Jon was busy plotting…

A couple hours ago my mother called me to tell me that (A) she loved me, (B) the latest edition of DDJ had arrived (my subscription is sent to her to save the overseas shipping costs), and (C) that i was on the cover.

What? i beg your pardon? i seem to have a small mammal in my ears, interfering with my hearing. i thought you just said that i’m on the cover of DDJ. The DDJ.

No, seriously. The cover is my face. It’s the same picture from my home page. Only a lot bigger. Huge, one might say. (For the curious, the picture was taken in Sylt, Germany, in August of 2006, by my girlfriend, Simone.)

The articles mentioned on the cover have absolutely nothing to do with me (nor i with them) except for the little blurb on the bottom/right:

Freelance Programmer Stephan Beal, see page 12

No, seriously.

My mugshot certainly isn’t going to help them sell copies, so why that picture for the cover, of all the lovely and beautiful images they could have used? Your guess is as good as mine. My only theory at the moment is the visual association of a cloudy sky (which is mostly cropped out of that copy of the image) with the headline article, entitled “Computing in the Clouds” (but, again, i’m not associated with that article). Well, and maybe because my clothes match the overall color scheme pretty well. No idea, really.

Unfortunately, the February edition of DDJ isn’t online yet, so i can prove to you not one word of what i just wrote. i can’t post the scanned copy my mother sent (for copyright reasons). So it’s my word against… well, against someone’s, certainly.

So here’s how we can settle this: if you’ll go to your favourite I.T. news stand right now, you might just find me waiting for you! If you’re a DDJ subscriber, i’m already there.

Happy hacking!

PS: Thanks again, Jon! That really made my day!