Monday, June 27, 2011

Writing a C library, part 1

This is part one in a series of blog-posts about best practices for writing C libraries.

Base libraries

Since libc is a fairly low-level set of libraries, there exists higher-level libraries to make C programming a more pleasant experience including libraries in the GLib and and GTK+ stack. Even while the following is going to be somewhat GLib- and GTK+-centric, these notes are written to be useful for any C code whether it's based on libc, GLib or other libraries such as NSPR, APR or some of the Samba libraries.

Most programmers would agree that it's usually a bad idea to implement basic data-types such as string handling, memory allocation, lists, arrays, hash-tables or queues yourself just because you can - it only makes code harder to read and harder to maintain by others. This is where C libraries such as GLib and GTK+ come into play - these libraries provides much of this out of the box. Plus, when you end up needing non-trivial utility functions (and chances are you will) for, say, Unicode manipulation, rendering complex scripts, D-Bus support or calculating checksums, ask yourself (or worse: wait until your manager or peers ask you) if the decision to avoid a well-tested and well-maintained library was a good decision.

In particular, for things like cryptography, it is usually a bad idea to implement it yourself (however inventing your own algorithm is worse); instead, it is better to use an existing well-tested library such as NSS (and even if you do, be careful of using the library correctly). Specifically, said library may even be FIPS-140 certified which is a requirement if you want to do business with the US government.

Similarly, while it’s more efficient to use e.g. epoll than poll for event notification, maybe it doesn't matter if your application or library is only handling on the order of ten file descriptors. On the other hand, if you know that you are going to handle thousands of file descriptors, you can still use e.g. GLib for the bulk of your library or application - just use epoll from dedicated threads. Ditto, if you need O(1) removal from a list, maybe don’t use a GList - use an embedded list instead.

Above all, no matter what libraries or code you end up using, make sure you have at least a rudimentary understanding of the relevant data-types, concepts and implementation details. For example, with GLib it is very easy to use high-level constructs such as GHashTable, g_timeout_add() or g_file_set_contents() without knowing how things are implemented or what a file descriptor really is. For example, when saving data, you want to do so atomically (to avoid data-loss) and just knowing that g_file_set_contents() Does The Right Thing(tm) is often enough (often just reading the API docs will tell you what you need to know). Additionally make sure you understand both the algorithmic complexity of the data-types you end up using and how they work on modern hardware.

Finally, try not to get caught up in religious discussions about “bloated” libraries with random people on the Internet - it’s usually not a good a use of time and resources.

Checklist

  • Don’t reinvent basic data-types (unless performance is a concern).
  • Don’t avoid standard libraries just because they are portable.
  • Be wary of using multiple libraries with overlapping functionality.
  • To the extent where it’s possible, keep library usage as a private implementation detail.
  • Use the right tool for the right job - don’t waste time on religious discussions.

Library initialization and shutdown

Some libraries requires that an function, typically called foo_init(), is called before other functions in the library is called - this function typically initializes global variables and data structures used by the library. Additionally, libraries may also offer a shutdown function, typically called foo_shutdown() (forms such as foo_cleanup(), foo_fini(), foo_exit() and the grammatically dubious foo_deinit() have also been observed in the wild), to release all resources used by the library. The main reason for having a shutdown() function is to play nicer with Valgrind (for finding memory leaks) or to release all resources when using dlopen() and friends.

In general, library initialization and shutdown routines should be avoided since they might cause interference between two unrelated libraries in the dependency chain of an application; e.g. if you don’t call them from where they are used, you are possible forcing the application to call a init() function in main(), just because some library deep down in the dependency chain is using the library without initializing it.

However, without a library initialization routine, every function in the library would have to call the (internal) initialization routine which is not always practical and may also be a performance concern. In reality, the check only has to be done in a couple of functions since most functions in a library depends on an object or struct obtained from e.g. other functions in the library. So in reality, the check only has to be done in _new() functions and functions not operating on an object.

For example, every program using the GLib type system has to call g_type_init() and this includes libraries based on libgobject-2.0 such as libpolkit-gobject-1 - e.g. if you don’t call g_type_init() prior to calling polkit_authority_get_sync() then your program will probably segfault. Naturally this is something most people new to the GLib stack gets wrong and you can’t really blame them - if anything, g_type_init() is a great poster-child of why init() functions should be avoided if possible.

One reason for library initialization routine has to do with library configuration, either app-specific configuration (e.g. the application using the library might want to force a specific behavior) or end-user specific (by manipulating argc and argv) - for example, see gtk_init(). The best solution to this problem is of course to avoid configuration, but in the cases where it’s not possible it is often better to use e.g. environment variables to control behavior - see e.g. the environment variables supported by libgtk-3.0 and the environment variables supported by libgio-2.0 for examples.

If your library does have an initialization routine, do make sure that it is idempotent and thread-safe, e.g. that it can be called multiple times and from multiple threads at the same time. If your library also has a shutdown routine, make sure that some kind of “initialization count” is used so the library is only shutdown once all users of it have called its shutdown() routine. Also, if possible, ensure that your library init/shutdown routines calls the init/shutdown routines for libraries that it depends on.

Often, a library's init() and shutdown() functions can be removed by introducing a context object - this also fixes the problem of global state (which is undesirable and often break multiple library users in the same process), locking (which can then be per context instance) and callbacks / notification (which can call back / post events to separate threads). For example, see libudev's struct udev_monitor.

Checklist

  • Avoid init() / shutdown() routines - if you can’t avoid them, do make sure they are idempotent, thread-safe and reference-counted.
  • Use environment variables for library initialization parameters, not argc and argv.
  • You can easily have two unrelated library users in the same process - often without the main application knowing about the library at all. Make sure your library can handle that.
  • Avoid unsafe API like atexit(3) and, if portability is a concern, unportable constructs like library constructors and destructors (e.g. gcc’s __attribute__ ((constructor)) and __attribute__ ((destructor))).

Memory management

It is good practice to provide a matching free() function or each kind of allocated object that your API returns. If your library uses reference counting, it is often more appropriate to use the suffix _unref instead of _free. An example of this in the GLib/GTK+ stack the functions used are g_object_new(), g_object_ref() and g_object_unref() that operate on instances of the GObject type (including derived types). Similarly, for the GtkTextIter type, the relevant functions are gtk_text_iter_copy() and gtk_text_iter_free(). Also, note that some objects may be stack-allocated (such as GtkTextIter) while others (such as GObject) can only be heap-allocated.

Note that some object-oriented libraries with the concept of derived types may require the app to use the unref() method from a base type - for example, an instance of a GtkButton must be released with g_object_unref() because GtkButton is also a GObject. Additionally, some libraries have the concept of floating references (see e.g. GInitiallyUnowned, GtkWidget and GVariant) - this can make it more more convenient to use the type system from C since it e.g. allows using the g_variant_new() constructor in place of a parameter like in the example code for g_dbus_proxy_call_sync() without leaking any references.

Unless it’s self-evident, all functions should have documentation explaining how parameters are managed. It is often a good idea to try to force some kind of consistency on the API. For example, in the GLib stack the general rule is that the caller owns parameters passed to a function (so the function need to take a reference or make a copy if the parameter is used after the function returns) and that the callee owns the returned parameters (so the caller needs to make a copy or increase the reference count) unless the function can be called from multiple threads (in which case the caller needs to free the returned object).

Note that thread-safety often dictates what the API looks like - for example, for a thread-safe object pool, the lookup() function (returning an object) must return a reference (that the caller must unref()) because the returned object could be removed from another thread just after lookup() returns - one such example is g_dbus_object_manager_get_object().

If you implement reference counting for an object or struct, make sure it is using atomic operations or otherwise protect the reference count from being modified simultaneously by multiple threads.

If a function is returning a pointer to memory that the caller isn’t supposed to free or unref, it is often necessary to document for how long the pointer is valid - for example the documentation for the getenv() C library function says “The string pointed to by the return value of getenv() may be statically allocated, and can be modified by a subsequent call to getenv(), putenv(3), setenv(3), or unsetenv(3).”. This is useful information because it shows that care should be taken if the result from getenv() is used by multiple threads; also this kind of API can never work in a multi-threaded application and the only reason it works is that applications or libraries normally don’t modify the environment.

It is often advantageous for an application to not worry about out-of-memory conditions and instead just call abort() if the underlying allocator signals an out-of-memory condition. This holds true for most libraries as well since it allows a simpler and better API and huge code-footprint reductions. If you do decide to worry about OOM in your library, do make sure that you test all code-paths or your effort will very likely have been in vain. On the other hand, if you know your library is going to be used in e.g. process 1 (the init process) or other critical processes, then not handling OOM is not an option.

Checklist

  • Provide a free() or unref() function for each type your library introduces.
  • Ensure that memory handling consistent across your library.
  • Note that multi-threading may impose certain kinds of API.
  • Make sure the documentation is clear on how memory is managed.
  • Abort on OOM unless there are very good reasons for handling OOM.

Multiple Threads and Processes


A library should clearly document if and how it can be used from multiple threads. There are often multiple levels of thread-safety involved - if the library has a concept of objects and a pool of objects (as most libraries do), the enumeration and management of the pool might be thread safe while applications are supposed to provide their own locking when operating on a single object from multiple threads, concurrently.

If you are providing a function performing synchronous I/O, it is often a good idea to make it thread-safe so an application can safely use it from a helper thread

If your library is using threads internally, be wary of manipulating process-wide state, such as the current directory, locale, etc. Doing so from your private worker thread will have unexpected consequences for the application using your library.

A library should always use thread-safe functions (e.g. getpwnam_r() rather than getpwnam()) and avoid libraries and code that is not thread-safe. If you can’t do this, clearly state that your library isn’t thread-safe so applications can use it from a dedicated helper process instead if they need thread-safety.

It is also important to document if your library is using threads internally, e.g. for a pool of worker threads. Even though you think of the thread as a private implementation detail, its existence can affect users of your library; e.g. Unix signals might need to be handled differently in the the presence of threads, and there are extra complications when forking a threaded application.

If your library has interfaces involving resources that can be inherited over fork(), such as file descriptors, locks, memory obtained from mmap(), etc, you should try to establish a clear policy for how an application can use your library before/after a fork. Often, the simplest policy is the best: start using nontrivial libraries only after the fork, or offer a way to reinitialize the library in the forked process. For file descriptors, using FD_CLOEXEC is a good idea. In reality most libraries have undefined behavior after the fork() call, so the only safe thing to do is to call the exec() function.

Checklist

  • Document if and how the library can be used from multiple threads.
  • Document what steps need to be taken after fork() or if the library is now unusable.
  • Document if the library is creating private worker threads.

8 comments:

  1. If your library does do proper synchronization for multiple threads, but you don't want to pay the overhead of pthreads for single-threaded programs, or you want to preserve portability to platforms without pthreads, try libpthread-stubs.

    ReplyDelete
  2. I am think that this is a very tricky requirement. If you make all adds atomic, its a large amount of overhead. I don't see how you can prevent their modification by multiple thread without adding critical section or severely limiting functionality. Perhaps I am misunderstanding your point. Can you please clarify.

    Aater (i.e., the futurechips guy)

    ReplyDelete
  3. Hey Aater, just to be clear the suggestion was only to use atomic ops for reference counting, not any kind of add - the typical use is like this

    http://git.gnome.org/browse/glib/tree/gio/gfileattribute.c?id=2.29.8#n923

    using g_atomic_int_inc() and g_atomic_int_dec_and_test() for atomic operations. See their docs here

    http://developer.gnome.org/glib/unstable/glib-Atomic-Operations.html#glib-Atomic-Operations.description

    in particular the implementation details. Now, implementation-wise, with recent GLib libraries and recent gcc compilers, these are implemented as macros that expand using gcc built-ins, see

    http://git.gnome.org/browse/glib/tree/glib/gatomic.h?id=2.29.8#n72

    which IIRC results to just a couple of assembler instructions if using a modern CPU (such as x86_64) and falls back to a slower path otherwise. See http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html#Atomic-Builtins and http://gcc.gnu.org/wiki/Atomic

    ReplyDelete
  4. >"Don’t reinvent basic data-types (unless performance is a concern)."

    glib violates this very simple rule right from the start. gpointer is just as bad as PVOID. “Just fuckin write void *.”

    >Avoid init() / shutdown() routines [...] Avoid unsafe API like atexit(3) and, if portability is a concern, unportable constructs like library constructors and destructors (e.g. gcc’s __attribute__ ((constructor)) and __attribute__ ((destructor))).

    Explicit destructor seems better. libgcrypt has a track record with all those issues http://comments.gmane.org/gmane.comp.encryption.gpg.libgcrypt.devel/2126 where it seems that explicit init/exit (refcounted of course) is the superior solution.

    >if you don’t call them from where they are used, you are possible forcing the application to call a init() function in main(), just because some library deep down in the dependency chain is using the library without initializing it.

    Fix the intermittent component in question, not main.

    ReplyDelete
  5. -- Library initialization and shutdown --

    "Avoid init() / shutdown() routines - if you can’t avoid them, do make sure they are idempotent, thread-safe and reference-counted."

    This is not clear enough. Global init and shutdown should be avoided or treated as non-thread/fork safe. A structure that holds all the state information for a library should have corresponding init() and shutdown() calls.

    "Use environment variables for library initialization parameters, not argc and argv."

    At a low level, a library should have all parameters set with API calls. One level up would include a call such as get_env_opts() to grab environement variable settings and get_cmd_opts(char *) to parse a well defined command line argument list. Then the library user or executable can decide how to handle the library configuration.

    "You can easily have two unrelated library users in the same process - often without the main application knowing about the library at all. Make sure your library can handle that."

    Uh... this makes little to no sense. But I'll supplement it with... make sure to clearly document the capabilities and behavior of your library in a multi-threaded or multi-process environment. Simply making something "thread-safe" is pointless without context and usage guidance.

    "Avoid unsafe API like atexit(3) and, if portability is a concern, unportable constructs like library constructors and destructors (e.g. gcc’s __attribute__ ((constructor)) and __attribute__ ((destructor)))."

    OK... so to put this more simple, if portability (of source code) is of high concern, know your dependencies! Highly portable code should by default avoid compiler dependent extensions, and non-POSIX functions. The exception is allowing for tweaked code to be enabled with CPP (pre-processor macros).

    ReplyDelete
  6. -- Memory management --

    "Provide a free() or unref() function for each type your library introduces."

    Agreed. But IMHO:
    - type_init - sets and allocated type to sane values
    - type_new - allocates a type and inits the new allocation
    - type_free - deallocates a type
    - type_ref, type_getref, type_get - creates a new reference (increments reference count)
    - type_unref, type_release, type_put - removes reference (decrements reference count)

    Another one I like to include (separate from type_free()) is:
    void type_destroy(type_t ** t)
    Usually when freeing memory, you should always

    free(ptr);
    ptr = NULL;

    I like to simplify that to a one liner that looks like:

    type_destroy(&ptr);

    type_destroy exists to decrement reference count, deallocate memory if reference count is zero, and sets pointer to NULL so subsequent "if (ptr)" checks operate as intended.

    "Ensure that memory handling consistent across your library."

    Memory management should be complete and well defined. As always, it should be clearly described in documentation with trivial and non-trivial examples.

    "Note that multi-threading may impose certain kinds of API."

    This should be inherit in the programmers skill set, but I agree. OO programming with instanced variables/references and locking mechanisms lend toward a more friendly multi-threaded experience. Static variables, global variables, lend to a less thread safe experience.

    My rule of thumb for this is usually:
    If there no non-constant variables defined globally, the library is _capable_ of being thread safe. The effort to make the library thread safe depends on the locking or concurrency logic overhead required.

    "Make sure the documentation is clear on how memory is managed."

    Documentation should always have trivial AND non-trivial examples and a list of potential Pitfalls

    "Abort on OOM unless there are very good reasons for handling OOM."

    Disagree. There may be valid exceptions to this, and one involves allocations that require _HUGE_ amounts of memory. If this occurs and fails, it is likely something caused by user input and not that the system is low on memory. Prime example is loading a >4GB file into memory on a 32bit system.

    Some extra advise (stuff I've struggled with in the past with my own libraries) includes:
    - Minimize the usage of "user-defined" void* types.
    - When doing memory management, don't forget to think about where the memory your pointers are pointing to is located with respect to the heap or the stack. Nastyness can occur if you free stack memory or don't free heap memory.
    - C does not do reference counting, so having a reference counting mechanism for C in a multi-threaded environment should be an absolute requirement. Realistically, you won't be able to always track when to free an allocated type without reference counting. This should especially be considered when using lists or trees to store references to memory.

    ReplyDelete
  7. -- Multiple Threads and Processes --

    "Document if and how the library can be used from multiple threads."

    Agreed, documentation should include trivial and non-trivial examples and a list of potential pitfalls.

    "Document what steps need to be taken after fork() or if the library is now unusable."

    You need to understand that your library is now duplicated but looking at the same file descriptors and streams as another as well as having a different pid. To handle this case gracefully, you'll need advanced locking, or IPC techniques. I agree that it'd be safer to just exec() if possible.

    "Document if the library is creating private worker threads."
    And don't forget about child processes.

    Some extra advised that I've struggled with in the past with my own libraries include:
    - Another multi-threading pitfall I've found is knowing where/when to create a new reference to memory. In short, you should always create a reference that a thread will use outside and before the thread execution (if applicable.) The issue is when you have multiple threads executing on a structure, at any time a thread can "unref" the memory potentially causing it to be freed. But as long as your current scope has a valid reference, reference counted memory should prevent it from being freed.

    ReplyDelete
  8. This article had all types of goodies, but you really have to know what you're looking for to find them. To prevent from being the stereotypical internet pessimist... here are some real comments I have on the article (without peer review.) ;-)

    As a foot note:
    I'd advise you get a peer review on any follow up parts to this series to make the language flow a little better. Other than the roughness of the article, it did have some good advise.

    Thanks,
    Chenz

    ReplyDelete