GNU Hash Table Support in Mimick

Background

I’m a big proponent of software tests (which I’l likely write about a fair amount) and am most comfortable when programming consists of making automated tests pass and therefore trusting that things will work as they should. I’ve spent many months working on service code without ever running those services locally: simply creating and satisfying tests and then pushing the code through CI/CD.

Over time I’ve grown to tend to avoid mocking libraries. Sometimes they are required due to platform rigidity but often they are at best needlessly complex, and at worst may be hiding questionable design decisions. If you have well defined interactions with appropriately segregated interfaces then directly providing test implementations should be relatively trivial. Maintaining a distinction between pure logic and risky concerns such as IO is another attractive design principle that can further drive down the proposed value of a mocking library particularly given how easily mocked IO calls can provide a false sense of security.

In C, however, the prospect of packaging your code up in some referentially transparent bubble wrap is far more elusive; access to dynamic memory is not absorbed by a lower layer and is likely to be fairly ubiquitous in any relatively large application. While these calls may not be likely to fail it seems reckless to assume that they will not and so code and tests should at least be aware of that possibility.

This seems like a suitable case for mocking. One evident alternative was to introduce preprocessor directives to enable different functionality while testing, but I’m generally opposed to corrupting primary files solely for the sake of tests (very often the design may be tuned to support tests in ways that at least based on my rationalizations are design improvements). Beyond questions of pollution this also implies some degree of difference between the code that is tested and that which is ultimately used. Another option would be to introduce some form of injectable allocator which could provide an appropriate indirection over the system calls, but that seems very clunky and noisy, especially with an eye towards moving away from C.

Quickly scanning around I came across Mimick which seemed like a promising fairly lightweight option. I’d already started using Criterion by the same author (an option I landed on years ago and haven’t felt the need to reevaluate) so it certainly made a lot of sense (I ended up stumbling across a reference to it somewhere on the Web rather than finding any direct path from Criterion). That the example in the README was for stubbing malloc offerred strong support that my needs would be addressed.

The Catch

Unfortunately when attempting to actually use Mimick to simulate allocation failure I received an error from the library about vital functions missing. A search led me to an existing but unresponded to issue(1) for the problem filed by someone else who was using the same distribution I use (Gentoo).

Diagnosis

My first steps were to check for anything obvious on my system. I made sure that those libraries were present and I checked and fiddled with some of the use flags for glibc that may be having an impact. My integration of Mimick involves checking out the source into a vendor directory so I also concurrently starting sprinkling some printfs throughout the code to see where things were blowing up. I tend to default to the mainstay of debugging through vomiting out debug lines since it’s a quick option to get info without remembering platform specific tools and configuration. I quickly zeroed in on the regions of code that were failing in the code for working with ELF procedure lookup tables (PLT). After fishing around to figure out what fields within what structs would be worth printing I dumped out the libraries that were accessed prior to the results for each and noticed no hash table was found for the libc library.

This confirmed suspicions I had earlier on and so I took a quick detour to see if I could quickly adjust my libc build but it didn’t come together immediately and didn’t seem like the ideal solution regardless. I added some additional information to identify the tags that were present within that file and confirm the suspicion that one of them matched that for the GNU hash table which it did. The standard ELF hash table can have unfortunate runtime along the lines of linear probing in cases where entries are missing which is unfortunately one of those worst case edge cases that is likely to be very common (2).

Issue identified, now for the fun part of rolling up my sleeves to fix the problem.

Put Away the Hand Soap

As revealed on the ticket I’d left the firm diagnosis in the morning before the start of my workday and a PR(3) was already opened by the end of the workday without my having to/getting to do anything. I’m not sure if that work was coincidentally already in flight or was just turned around quickly, but it solves my problems so I’m back to other tasks.

The code in the PR appears is in line with that which is typically used to perform lookups on GNU hash tables, making use of constants Mimick provides to properly target the build system. The format itself makes use of a bloom filter to probabalistically short circuit for entries that are not present before looking up entries in the table itself which seems like a more typical modern hash table with more contrained practical worst case performance.

1.
2.
ELF: Symbol lookup via DT_HASH | flapenguin.me [online]. May 2021. Available from: https://flapenguin.me/elf-dt-hash
3.