Libnifty Overview

This project contains pthread packages for use in multi-threaded C code. They use a low-overhead, reference-counting mechanism for accessing shared objects, which helps to protect against stale-pointer errors and memory leaks:

Package | Description ----------------|---------------------------------------------- nft_list | Linked lists with thread-local free node cache. nft_pool | Thread pool to execute tasks asynchronously. nft_queue | Inter-thread event queue or message channel. nft_rbtree | Balanced red-black btree for associative mapping. nft_sack | Bulk memory allocator used by nft_list. nft_task | Schedule tasks to execute at a specified time. nft_vector | Set operations using sorted arrays for peformance. nft_core | The base class for the other Nifty packages. nft_win32 | A limited pthread emulation layer for Windows.

Consult the header files in ./include/ for the API definitions. The ANSI C implementations in ./src/ also contain test programs (look for #ifdef MAIN) that illustrate how to use the package.

These packages generally use elastic data structures and optimal algorithms for best performance. All of these packages are thread-safe, and are cancellation-safe using the normal deferred-cancellation mode. All of the blocking calls are deferred cancellation points.

To build, tweak src/Makefile to your liking, then

$ make -C src

To build and run the unit test programs, do

$ make -C src test

This code should build on most modern Unix systems, but you may need to tweak the Makefile, and you may wish to adjust the implementation of the nft_gettime() call in nft_gettime.h to suit your platform.

This file gives a detailed discussion how you can create your own "classes" using libnifty, and why it may be advantageous to do so. See the section Object-oriented development based on nft_core, below.

Note also that there is a lockless implementation of the handle subsystem, which you can enable in the Makefile. This is not yet practical, because it also requires you to fix the size of the handle table. See src/nft_handle.c for more information.

The libnifty packages can be built on WIN32. For more information, refer to the section WIN32 Notes below.

If you have questions or contributions, send them to sean@xenadyne.com.

How to use the Nifty packages

Of the packages that we list above, only the thread pool, message queue, and task scheduler are directly useful. The message queue package is by far the most useful. In any multithreaded program, your threads are going to need to communicate, and message queues are a simple and convenient way to do this.

So, let's discuss the nft_queue package in detail, since it is useful, and it illustrates many common features of the libnifty packages. The source code is in src/nft_queue.c, and like all libnifty packages, there is a test program at the bottom of the .c file, enclosed by #ifdef MAIN ... #endif. This test program demonstrates how to use the nft_queue package.

Let's look at some of the code that you can see in the test program. Here, we create a queue:

    // Create an unlimited queue.
    nft_queue_h Q = nft_queue_new(0);

The parameter 0 means that there is no limit on the queue size, which comes into play when you try to add an item to the queue. More on this later. The _new() function returns a "handle" for the queue, and even though it is defined to be a pointer to a struct, it is really not a pointer value, it is just a number generated by incrementing a counter.

While you cannot dereference the handle returned from nft_queue_create(), you can use it to interact with the queue via the queue's APIs. For example, you can add an item to the end of the queue:

     int rc = nft_queue_add( Q, strdup("hello"));

Because you do not dereference the handle, these APIs help to improve encapsulation, and because the handle is not a pointer, it is very easy to prevent "stale" handles being used. You can convert the handle to a real pointer - you just need to be more careful when doing so. We discuss this in detail, a little further on.

The nft_queue_add() call returns an error code. Most libnifty APIs that return an error code, use zero to indicate success, and use POSIX error codes like EINVAL or ENOMEM to indicate failure. These error codes are defined in errno.h, but libnifty calls do not set the errno variable (though errno may be set by system libraries that libnifty calls). The error codes that a particular call can return, are documented in the package header file.

Most libnifty calls that can block have a timeout parameter, such as this call to pop an item from the head of the queue:

   void * item = nft_queue_pop_wait( Q, -1);

In the example above, if the queue is empty, the nft_queue_pop_wait() call may block indefinitely, if no other thread enqueues an item, because the timeout parameter is negative. If the timeout parameter is zero or positive, then the call would return NULL after that many seconds, if no item were queued in the meantime. So a zero timeout will return immediately, returning NULL if the queue was empty.

When we wish to do away with the queue, we call nft_queue_shutdown():

    rc = nft_queue_shutdown( Q, 10);

The _shutdown call also takes a timeout parameter. Shutdown waits for the queue to become empty, and so this operation may time out. Attempts to add items will fail once the shutdown operation begins, so the shutdown should complete eventually, as long as some thread is popping items from the queue. But it's best to set a timeout, just to be safe.

You may wonder, why we did not name this function nft_queue_destroy, since it appears to be the counterpart to nft_queue_new? In fact, there is a nft_queue_destroy() function, but it is very rarely called directly, because libnifty objects are reference-counted. Because of this, you cannot be certain that the queue has been destroyed, even after nft_queue_shutdown() returns successfully.

Every thread that is blocked within a nft_queue API call, will hold a reference to the underlying object for the duration of that call. Each thread will discard that reference as it returns from the API that it had called. The handle will be invalidated, and the queue destroyed, only when the last reference has been discarded.

This discussion illustrates why libnifty API calls use handles. Reference counting of some kind, is virtually unavoidable when sharing pointers to dynamically-allocated (malloc'ed) memory in a multithreaded program. However, reference counting does not solve every problem - while it can prevent the use of stale references, it is still possible to leak reference counts, and so leak memory.

The virtue of handles, is that all of the reference counting happens inside the API calls, where we can take pains to ensure correctness. Let's look at the implementation of the nft_queue_pop_wait() call, to demonstrate how this works:

void *
nft_queue_pop_wait(nft_queue_h handle, int timeout)
{
    nft_queue * q = nft_queue_lookup(handle);
    if (!q) return NULL;

    pthread_mutex_lock(&q->mutex);
    void * item = nft_queue_dequeue(q, timeout);
    pthread_mutex_unlock(&q->mutex);

    nft_queue_discard(q);
    return item;
}

First, we call nft_queue_lookup() to convert the caller's queue handle to a pointer. If the queue had been destroyed, the lookup operation would return NULL, so the _pop_wait call will reject stale handles. The nft_queue_lookup() operation also will not return an object pointer, unless that object is really a nft_queue, or a nft_queue subclass. So, handles that were incorrectly type-cast are also rejected.

The queue's reference count is incremented atomically by the lookup operation, so the pointer that is returned is guaranteed to be protected by the reference count. Therefore, it is important that we call nft_queue_discard(), to decrement the reference count, before returning. If we wish to be cancellation-safe, we must further ensure that the reference will be discarded by a cancellation cleanup handler, in the event that the thread is cancelled.

In fact, the nft_queue_dequeue() function, which has a timeout and thus can can block, is a deferred cancellation point. It pushes a cancellation cleanup handler that will discard the reference, and also release the mutex, if the thread is cancelled while waiting. So, by using handles, it becomes much easier to create APIs that provide strong guarantees to callers.

The concepts and conventions that we just discussed, are common to the other libnifty packages. I hope that you are persuaded that using the Nifty library will make your pthread programs simpler, and more stable.

Now, if you review the header file nft_queue.h, you may notice that calls such as nft_queue_dequeue(), and nft_queue_destroy(), and indeed, the struct declaration of the nft_queue object itself, are exposed. You might have assumed, after all this talk of encapsulation, that these details would be hidden, and the APIs declared static, within nft_queue.c. The reason that these APIs are published, is to enable subclasses to be built from nft_queue. In fact, the nft_pool package is itself a subclass of nft_queue. In the section that follows, we discuss how this works in detail.

"Object-oriented" development based on nft_core

Many of the Nifty packages are derived in "object-oriented" style from nft_core. This section discusses how this derivation works. Our approach is as simple as possible. The goals are to:

• Support only simple single-inheritance,
• Produce APIs with strong static type-checking,
• Provide effective runtime type-checking,
• Use reference-counts to manage shared pointers,
• Classes publish handles, keeping pointers private.

The idea is that e