Closures in the Nanos Unikernel

Introduction

This article does an overview on the use of closures in the Nanos kernel. Closures are common in languages like Ruby and Swift. The C language does not include them, thus, the Nanos kernel relies on its own implementation. We use closures not only to implement callbacks with saved variables but also to compose continuations for asynchronous operations. In this article, we present what a closure is and we show the dedicated API that the Nanos kernel provides to manipulate closures.

What is a closure?

Before defining closures, let's roughly present the notion of callbacks. A callback is a pointer to a function that is passed into another function as an argument. For example, the qsort() function requires as an argument a pointer to the comparator function. The qsort() function is declared as follows:

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

In some cases, the callback may require additional arguments. For example, to sort an array of two-dimensional coordinates based on their distance from some target, the comparator needs to know the target. However, the qsort() interface has no way to pass this information. A simple solution would be to use a global variable to store the target. A completely different solution is to use a unique function pointer for each callback. This unique function would invoke the callback with the corresponding arguments. In our example, the target could be an array of coordinates and we could define an unique function for each coordinate in the array.

Generally speaking, we call this unique function a closure, which is a callback with saved variables. We call the saved variables that the function requires for working, e.g., target, closed over variables or left-hand side arguments. These variables make the environment of the closure. We call the arguments that are used for the invocation, e.g., two pairs of coordinates, the right-hand side arguments. Let’s illustrate how a sample API might look like to do this at runtime:

int (*closure)(const void *, const void *);
new_closure = closure_create(comparator, 3, &target);
qsort(coords, ncoords, sizeof(coords[0]), new_closure);
closure_destroy(closure);

The closure_create function builds a new function named new_closure that accepts two arguments, i.e., the two pairs of coordinates. We use new_closure as the comparator for qsort(). The new_closure function shall invoke the comparator with the two passed arguments and the closed over variable, i.e., target. Note that this is only an example of how the API would like.

To streamline the process of defining closures, the Nanos kernel provides dedicated macros to:

• define closure functions
• declare closure functions
• ease the manipulation of the closed over variables or left-hand side arguments
• define closure_types to make the code more composable

In the following, we run through different examples and we show the power of the API implemented in Nanos to manipulate closures.

Basic example

Let's start with a made-up example to show the elements that define a closure. In the following example, we have the creation of the closure function bar and a closed over argument a:

closure_function(1, 1, u64, bar, 
                 u64, l0,
                 u64, r0)
{
    u64 sum = bound(l0) + r0;
    return sum;
}

typedef closure_type(bartype, u64, u64);

u64 sum(u64 a, u64 b)
{
    bartype sh = stack_closure(bar, a);
    return apply(sh, b)
}

The stack_closure macro creates an instance of a closure that lives on the stack. Note that the value of the closed over variable a is captured when stack_closure is issued. By using the apply macro, we apply the closure function by specifying the free variable b as argument. The sum function returns the sum of a plus b.

We use the closure_function macro to define a type of closure. The first two arguments of the macro are the number of closed over variables and the number of applied or right-hand side arguments, respectively. The environment consists of a single word l0. The closure application accepts a single argument r0. To access the closed over variables, we use the macro bound.

This is an example of a synchronous continuation. The closure environment lives in the current stack-frame. Thus, values are lost after sum() returns. Let's see how to define closures in which the environment is kept after it is applied.

Callbacks

We use closures to implement callbacks. In this example, we show the use of closures to define the callback to visit the nodes of a red-black tree (rbtree). This is the declaration of the function to allocate a rbtree:

rbtree allocate_rbtree(heap h, rb_key_compare key_compare, rbnode_handler print_key);

The function key_compare is the callback for comparing nodes in the rbtree. The rb_key_compare closure type is defined by using the closure_type macro:

typedef closure_type(rb_key_compare, int, rbnode a, rbnode b);

The function is defined using the closure_function macro. The following code defines the thread_tid_compare closure function:

closure_function(0, 2, int, thread_tid_compare,
                 rbnode, a, rbnode, b)
{
    thread ta = struct_from_field(a, thread, n);
    thread tb = struct_from_field(b, thread, n);
    return ta->tid == tb->tid ? 0 : (ta->tid < tb->tid ? -1 : 1);
}

This is the actual code that compares nodes in the rbtree that contains the threads of the system. The closure function accepts two arguments: a and b of type rbnode. The closure function has no closed over variables. We instantiate the closure function by using the closure macro that creates an instance of the closure function from the heap:

rb_key_compare rb_key_compare_i = closure(h,thread_tid_compare)
p->threads = allocate_rbtree(h, rb_key_compare_i, closure(h,
tid_print_key));

We first instantiated the function thread_tid_compare, and then, we set it as the comparator function for the new rbtree. Note that this use-case requires that the closure function be allocated from the heap. This is because the function may be invoked from any scope.

Closures for asynchronous continuation

In this example, we present how we define closures from the heap. By doing so, the values are kept until the closure is deallocated. The following code shows an example of an asynchronous continuation for the unix syscall sync (excerpt):

closure_function (1, 1, void, sync_complete,
                  thread, t,
                  status, s)
{
    thread t = bound(t);
    syscall_return(t, is_ok(s) ? 0 : -EIO);
    closure_finish();
}

sysreturn sync(void){
    status_handler sh = closure(general, sync_complete, current);
    if (sh == INVALID_ADDRESS)
        return -ENOMEM;
    storage_sync(sh);
    return thread_maybe_sleep_uninterruptible(current);
}

The sync_complete closure function takes a thread as an argument and a status_handler type as a closed over variable. In the sync function, we use closure to create an instance of the sync_complete closure function from the general heap. We pass a closed over reference to the current thread. Then, storage_sync is invoked with the status_handler, which initiates the filesystem sync routine.

Unlike the previous example, the closure is allocated from the general heap since it may be called after the storage_sync function has returned. The thread_maybe_sleep_uninterruptible sleeps the current thread until the completion is invoked. The thread does go to sleep if there are dirty pages that need to be flushed to disk. In that case, after all filesystems are synced, the supplied status_handler is scheduled to run. sync_complete is invoked with the saved environment which calls syscall_return, thus setting the error return value and scheduling the thread to resume execution. Finally, closure_finish deallocates the closure and scheduler resumes after sync_complete returns.

Completions in stages and joining parallel operations

This example shows how we fork, and then, join parallel operations by using closures. The following code corresponds with the read function in the logging extent-based filesystem. The read function is itself a closure created per file with references to the filesystem and the file object closed over:

closure_function(2, 3, void, filesystem_storage_read,
                 filesystem, fs, fsfile, f, sg_list, sg, range, q, status_handler, complete)
{
    filesystem fs = bound (fs);
    fsfile f = bound(f);
    merge m = allocate_merge(fs->h, complete);
    status_handler k = apply_merge(m)
    
    rage blocks = range_rshift_pad(q, fs->blocksize_order);
    rangemap_range_lookup_with_gaps(f->extentmap, blocks,
                                    stack_closure(read_extent, fs, sg, m, blocks),
                                    stack_closure(zero_hole, fs, sg, blocks));
    apply(k, STATUS_OK);
}

The filesystem_storage_read closure function takes a completion argument to apply when the operation is finished. The allocate_merge macro provides a way to join together the completions of multiple operations issued in parallel, culminating into a single completion. Each call to apply_merge returns a newly created status_handler. When all such status_handlers are called, the completion passed to allocate_merge is invoked and the merge deallocates itself. read_extent takes as an argument the merge m allocated above. If read_extent determines that there are blocks to be read, it will first call apply_merge, which bumps the internal reference count within the merge and creates a status handler. This status handler is passed to the block device request handler as completion to be invoked once the io has finished. Coming back to filesystem_storage_read, first call to apply_merge that returns the status_handler k takes a single reference to hold the merge open for the span of the function. Once the request for all individual file extents have been issued, it is applied at the end of the function. This is to prevent a synchronous read completion prematurely invoking the upstream merge completion before all requests have been issued.

Using closures for scheduling

In Nanos, we use closures to schedule operations. These operations are embedded into a thunk, which is simply a closure that takes no arguments. The following code shows a simple implementation of an scheduler by relying on thunks:

thunk t;
while ((t = dequeue(runqueue)) != INVALID_ADDRESS) {
    apply(t);
}

The scheduler dequeues a thunk from a lock-free queue. If the thunk is valid, the thunk environment is loaded by using the apply macro. Note that the scheduler does not know about unix threads or program state frames; it just calls thunks, thus leaving the details of scheduling each thunk encapsulated within the captured closure environment.

Conclusion

We have reviewed the concept of closures which are rarely used in kernel development. The Nanos kernel heavily uses closures not only to implement callbacks but also to handle synchronous and asynchronous continuations. A complex operation can be split into smaller operations that potentially execute in parallel. The Nanos kernel provides a dedicated API to manipulate closures. Thus, developers can tackle different use-cases by relying on a simple set of macros. Closures are a powerful programming construct - typically only available in other languages - but we have successfully adapted it to a kernel environment written in C. The result is a kernel written in a more composable manner, with less boilerplate so often seen in other system software written in C.

Matias E. Vara Larsen