The Unreasonable sem_open() Function

I have recently re-implemented named semaphores for the QNX OS. For those unfamiliar with the mechanism, a named semaphore is a semaphore that is associated with a unique name that can be accessed by multiple processes. This makes named semaphores handy for synchronization among threads in different processes.

The POSIX standard defines a few functions for dealing with named semaphores, which are modelled after the basic functions for dealing with files:

  • sem_open() – either creates a new named semaphore, or opens an existing one. If successful, the function returns a pointer to a sem_t object, which can then be used with the standard semaphore functions sem_post() and sem_wait(). The sem_t object itself is an opaque handle, defined differently by each operating system.
  • sem_close() – invalidates the handle returned by sem_open() and deallocates all system resources associated with it (the importance of this part of the specification will become clear shortly).
  • sem_unlink() – deletes the name, which prevents future calls to sem_open() from succeeding for that name, but does not affect any existing handles.

Various functional and performance tests showed that my implementation was good – multiple processes can open a semaphore and use it to synchronize the activity of various threads. But then, disaster struck – one of the POSIX conformance tests was failing. As it turns out, POSIX has this requirement as part of the specification for sem_open():

If a process makes multiple successful calls to sem_open() with the same value for name, the same semaphore address shall be returned for each such successful call, provided that there have been no calls to sem_unlink() for this semaphore, and at least one previous successful sem_open() call for this semaphore has not been matched with a sem_close() call.

In other words, POSIX mandates that in the following code, sem1 and sem2 should not only represent the same semaphore, but actually have the same virtual address:

sem_t * const sem1 = sem_open("foo", 0);
sem_t * const sem2 = sem_open("foo", 0);

What could possibly be the reason for such a requirement? There is nothing in the operation of a semaphore, especially one intended for sharing across processes, that would necessitate or even logically entail such a restriction. Even worse, it can easily lead to bugs. Remember the highlighted part of the description of sem_close()? According to POSIX

sem_close(sem1);

should release all resources for both sem1 and sem2. The same does not happen with file descriptors, for example:

int const fd1 = open("foo", O_RDONLY);
int const fd2 = open("foo", O_RDONLY);
close(fd1);

At this point fd2 is still fully functional.

In February I logged the following objection to sem_open() with the Austin Group, which is the body responsible for the standard, though I haven’t heard anything yet:

The current specification mandates that two calls to sem_open() with the same name made by the same process return the same virtual address, so long as no process called sem_unlink() in between the two calls.
I believe that this is an unreasonable requirement, for the following reasons:

  1. There is no dependency by any other sem_() function on this requirement. So long as the two sem_t pointers returned by the calls refer to the same underlying semaphore all sem_() functions will behave correctly when passed these pointers.
  2. It puts an unnecessary burden on the system to track virtual address usage by the calling process. The system should only need to track the association of any given sem_t pointer to the underlying object. If, for example, the sem_t pointer holds a file descriptor to an open semaphore, then the system only needs to track the file descriptor.
  3. Since sem_close() is documented as releasing all resources for the semaphore and making the pointer invalid for future use, the requirement promotes an unsafe “open twice, close once” paradigm.
  4. The requirement deviates from the standard approach to resource allocation, where multiple calls provide different handles, even if those handles refer to the same object (e.g., open(), shm_open(), mmap() with the same file descriptor and offset)
  5. The requirement may conflict with the following future direction: “A future version might require the sem_open() and sem_unlink() functions to have semantics similar to normal file system operations.”

Screenshot Galore!

The QNX desktop has seen some significant improvements over the last few months. While it is still mostly a one-person spare-time project, it is becoming more and more usable.

First, I owe a debt from my original post. I was reprimanded by commentators for the window decoration’s lack of visual appeal. To address this I added a simple theme plug-in API to the window manager, which facilitates the creation of new themes. These are built into shared objects that are loaded when the window manager starts. With the help of the Cairo library  I was able to write two new themes: one original, the other less so (see if you can spot it…).

Multimedia

No desktop system is complete without the ability to play back music and video. The QNX playback engine is called mm-renderer, which I was able to add to the system with ease, owing to some fairly good documentation. Moreover, the Qt libraries are already set up to use mm-renderer, which means that once it was running I was able to use Qt’s media player demo to play both music and videos. Nevertheless, this simple demo is a far cry from a good media player. After trying various options I found the excellent Musique music player. Musique has very few dependencies other than Qt, but it does rely on a playback library (QtAV) that I did not want to port (given that it has many dependencies of its own). Luckily Musique’s code is well organized, with media playback encapsulated by a separate library with its own interface. Implementing this interface using Qt’s native QMediaPlayer class was almost trivial and the result is fantastic.

Finally, starting mm-renderer allows the browser to play media without any further changes.

multimedia

Productivity

The lack of an office suite used to be a significant hurdle to the adoption of alternative desktop operating systems (I still remember my attempts to use WordPerfect and Star Office on RedHat Linux 5.0). Things have changed dramatically with the proliferation of web-based applications such as Google Docs and Office 365, which can be accessed by any system with a modern browser.

office

Of course, real men (and women, and small furry creatures from Alpha Centauri) don’t use word processors. They us LaTeX. And if writing LaTeX code in Emacs is not your thing, there is TexMaker to the rescue.

texmaker

Development

On top of the existing set of development tools (GCC, GDB, Emacs, Vim, Valgrind) the QNX desktop now includes Qt Creator. The following screenshot is my homage to the most aesthetically-pleasing desktop ever created, including an attempt to write a matching Qt style.

qtcreator

And one more thing…

Need access to a Linux-based system? No problem. The QNX Hypervisor supports various Linux flavours, including Ubuntu and Android.

ubuntu-qvm

Functional Programming with C++ Templates

About 10 years ago I bought C++ Template Metaprogramming by David Abrahams and Aleksey Gurtovoy. I read the book and even dabbled at template metaprogramming in the never-finished version 2.0 of KScope. My career, however, soon took me very far away from modern C++, and I have not had a chance to get fully immersed in the techniques described in the book.

A few weeks ago I decided to give the book another chance, and this time try to understand the concepts rather than the syntax of the MPL library. Things went south fairly quickly.

C++ template metaprogramming as implemented by MPL is essentially a new functional language built on top of C++ templates. The data manipulated by the language consists of types (int, long, double, structs and classes, etc.) and the manipulation is done by functions that take and return types. These functions (or metafunctions as they are referred to in the book), use template parameters as arguments and type definitions to return a result. For example, the following function takes a type T and returns a type that is a pointer to T:

template<T>
struct add_pointer
{
    typedef T* type;
};

So far so good, as it is easy to draw parallels from the description of this language to other functional languages, such as Scheme. But this warm, fuzzy feeling of familiarity doesn’t last long.

One of the most important characteristics of functional languages is the ability to write higher-order functions, which are functions that take and/or return other functions. Chapter 3 in the book introduces higher-order functions using an example: the function twice, which takes a function and an argument, and returns the application of the function twice on that argument, i.e.:

twice(f, x) = f(f(x))

The problem is that with the book’s definition of a metafunction it is impossible to write one that takes another metafunction as an argument:

  1. Metafunctions are templates that take types as arguments
  2. A template is not a type

The rest of the chapter is devoted to techniques that turn metafunctions into types (metafunction classes, placeholder expressions) so that they can be passed around to and from other metafunctions.

It took me a while to understand what it is that bothers me with the treatment of this fundamental topic of functional languages by the book. I went back to my 20-year-old copy of Structure and Interpretation of Computer Programs by Abelson and Sussman (x2) and reread the introduction to higher-order functions. Let us consider how twice would have been implemented in Scheme. First, a Scheme function is really a lambda expression with a name (which, in my opinion, is better than to say that a lambda expression is an unnamed function):

(define (sum a b) (+ a b))

is really syntactic sugar (SIoCP’s favourite expression) for

(define sum (lambda (a b) (+ a b)))

Since lambda expressions in Scheme can be freely passed around as arguments to other lambda expressions, and be returned by other lambda expressions, we have a language that naturally implements higher-order functions. We can make twice a function that takes a function and returns another function which will apply the first one twice to its argument (note that we are returning a new function, not the application of a function to an argument):

(define (twice f) (lambda (x) (f (f x))))

And since twice is really just a name for a lambda expression, it can be passed around as a parameter to other functions or be returned by them.

How can we implement the same concept in C++?

First, let us change the way a metafunction is implemented from a template to a structure with a member template called lambda, which, in turn, defines a type called result (this is similar to how the book defines a metafunction class):

struct add_pointer
{
    template<typename A>
    struct lambda
    {
        typedef A* result;
    };
};

Invoking the function consists of instantiating the result type, e.g.:

int a = 5;
add_pointer::lambda<int>::result p = &a;
std::cout << *p << std::endl;

With the new definition, we can implement twice as a function that takes a function and returns a function:

// The function's name.
struct twice
{
    // The lambda expression that takes a function as an argument.
    template<typename F>
    struct lambda
    {
        // The result, which is itself a type.
        struct result
        {
            // The result is a lambda expression that, when invoked,
            // applies the function F twice to its argument.
            template<typename A>
            struct lambda
            {
                typedef typename F::template lambda<A>::result once;
                typedef typename F::template lambda<once>::result result;
            };
        };
    };
};

We can then name the new function that twice returns when invoked with add_pointer as its argument:

typedef twice::lambda<add_pointer>::result add_pointer_pointer;

and invoke the new function:

add_pointer_pointer::lambda<int>::result pp = &p;
std::cout << **pp << std::endl;

My approach is considerably more verbose than the one taken by MPL, and it is quite possible that it is severely limited in some way. Nevertheless, it seems to me that it is more in-line with traditional functional languages and as such easier to follow if you are familiar with functional programming.

Desclaimer: The above should in no way be read as criticism of either the book, its authors or the MPL. My extremely limited experience with template metaprogramming prevents me from passing judgement. The article is about my struggle with understanding the subject and the way I found to elucidate the important topic of higher-order functions using C++ templates.