SBCL Internals The pages on this CLiki-driven site can be edited by anybody at any time. No warranty of any kind can therefore be made; any implied warranties of merchantability or fitness for a particular purpose are expressly disclaimed

1) one machine word (an integer) that contains the state of a futex

2) wait queue that holds threads that are waiting on this futex

In linux, futex wait queue is managed by linux kernel and SBCL takes advantage of that. Also futexes have a very useful property that user of futex has just to know the address of an integer and the kernel does the rest. Very useful property of them is that lisp has to keep a pointer to an integer and thus it is very easy for dumping synchronization objects into a core image - there is no initialization, no finalization that must be done on a futex.

On operating systems other than linux futex API is implemented with pthreads.

(update by Kalyanov Dmitry, 20 April 2010)

Nathan Froyd had a go at removing the futex dependencies of the threading system recently. (Spoiler: the changes don't work yet.) Roughly in the order he learned about things, here's what he did:

• Created a new primitive object, FUTEX (for lack of a better name), with appropriate supporting machinery. The C object underlying a FUTEX is a POSIX semaphore. (Extremely hard; see below)
• Changed futex calls in linux-os.c to use POSIX semaphore calls instead. (Very easy)
• Changed calls in target-thread to use new FFI calls and suchlike. (Very easy)

The first step is really the trickiest. My initial idea was to have a FUTEX contain a SAP pointing to some underlying semaphore allocated by malloc. When the FUTEX was moved, the underlying semaphore would not be. One problem with this is that when FUTEXes are saved to cores, the underlying malloc'd memory disappears. This is potentially solvable with some hair in the runtime, e.g. saving information about active FUTEXes in a core. (I'm thinking about going back to this strategy; I believe I abandoned it too early.)

The next idea was to define a futex to contain an actual POSIX sem_t and have FUTEXes allocated in static space. This strategy is not workable in the long term (it could be under the assumption that mutexes are relatively rare and tend to be around for a while, but if one wants to associate mutexes with, say, nodes in a tree, this strategy is a poor one), but it held some promise for getting things working initially. Problems still exist with saving FUTEXes to cores.

The resulting build gets into cold-init, but dies in THREAD-INIT-OR-REINIT while allocating the first FUTEX, for reasons I can't explain. (It appears to die as it enters a WITHOUT-GCING, which seems strange.)

Garbage collecting FUTEXes is also tricky, because you want to sem_destroy the semaphore upon garbage collection. However, when running a finalizer for an object (a FUTEX), you're not allowed to reference the object in the finalizer. And the semaphore (currently) doesn't exist as a separate entity. A non-tracing garbage collector would solve this problem, but retrofitting such a thing onto SBCL's runtime is likely to be difficult.

Linux futexes are really the perfect solution to SBCL's threading problems; they have none of the initialization/destruction hair associated with pthread mutexes or semaphores. They're friendly to GC. It's too bad they don't exist on other platforms.

The first strategy sounds like a good solution to me (tfb). For the mechanics of saving the FUTEX objects at save-image time, you could reuse the original static-vector implementation that malloc'd memory, then copied the contents to the lisp heap when the image is being saved. It should work for you almost unmodified. Unfortunately, the current implementation allocates directly out of static space -- which means that, unlike the code I wrote, the static-vectors can't be GCd.

(The code I'm referring to can be found in the attachment to the sbcl-devel mail with message-id 16737.38269.848686.904175@conquest.OCF.Berkeley.EDU)

Nathan Froyd says: The current plan is to malloc the semaphore and have a FUTEX store the returned pointer. When saving a core, the saving process will record the number of and addresses of FUTEXes. When a core is loaded, the saved addresses will be processed and their semaphores sem_init'd before user code gets a chance to run.

Thomas Burdick says: That's probably a more robust approach anyway. Unless POSIX makes guarantees about what's not in a semaphore, it could contain all kinds of strange handles on kernal internals.

Question: Is removing the futex calls and using POSIX 1003.1b semaphores still on the TODO list? Not on linux at the moment. Obviously, if threads are to be supported by a non-linux platfrom futexes aren't available. The trouble with semaphores is that they are not movable by GC without sem_destroy and sem_init, but no threads should be waiting on the semaphore when sem_destroy is called. Gabor Melis?

I think sem_destroy can be called by a finalizer on FUTEXes. As a programming aid, we can call sem_trywait in the finalizer to check whether a thread is still waiting on the semaphore. If there is, we abort (since the waiting thread can no longer access the FUTEX by definition--that's why it's getting GC'd).

Making the semaphore a pointer to system memory stored inside a FUTEX means that, theoretically, one can FINALIZE on the FUTEX and sem_destroy the allocated semaphore, along with free'ing it. One problem is that finalization locks a mutex of its own, which means bootstrapping of some sort. The easiest workaround is to define a "giant" lock inside the runtime that gets used for finalization (possibly other things for convenience's sake).

This page is linked from: THREADING  

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively