Multicore

Archived Posts from this Category

November 5, 2008

Who ordered memory fences on an x86?

Posted by Bartosz Milewski under C++, Concurrency, Multicore, Multithreading, Programming
[54] Comments 

Multiprocessors with relaxed memory models can be very confusing. Writes can be seen out of order, reads can be speculative and return values from the future–what a mess! In order to impose some kind of consistency you have to use memory fences, and there are several kinds of them.

The x86 seems to be an oasis in the perilous landscape of relaxed memory multicores. The Intel x86 memory model, detailed in Intel 64 Architecture Memory Ordering White Paper and the AMD spec, AMD64 Architecture Programmer’s Manual, list a lot of memory ordering guarantees, among them:

  • Loads are not reordered with other loads.
  • Stores are not reordered with other stores.
  • Stores are not reordered with older loads.
  • In a multiprocessor system, memory ordering obeys causality (memory ordering respects transitive visibility).
  • In a multiprocessor system, stores to the same location have a total order.
  • In a multiprocessor system, locked instructions have a total order.
  • Loads and stores are not reordered with locked instructions.

The x86 also has (expensive–on the order of 100 cycles) memory fence instructions, mfence, lfence, and sfence; but, considering all those guarantees, why would anyone use them? The famous double-checked locking pattern, on the x86, works just fine without any fences.

This is a very important question, because you don’t want the compiler to over-fence your code and bring it to a crawl. On the other hand, you don’t want it to emit incorrect code. I decided to look for some answers.

There is one important non-guarantee listed in the x86 spec:

Loads may be reordered with older stores to different locations

Here’s an example from the x86 spec: x and y are in shared memory and they are both initialized to zero, r1 and r2 are processor registers.

Thread 0 Thread 1
mov [_x], 1
mov r1, [_y] 		mov [_y], 1
mov r2, [_x]

When the two threads execute on different cores, the non-intuitive result r1 == 0 and r2 == 0 is allowed. Notice that such result is consistent with the processor executing the loads before the stores (which access different locations).

How important is this example?

I needed to find an algorithm that would be broken by this relaxation. I’ve seen Dekker’s algorithm mentioned in this context. There is a more modern version of it used in the Peterson lock. It’s a mutual exclusion algorithm that works for two threads only. It assumes that each thread has access to a thread-local ID, which is 0 for one thread and 1 for the other. Here’s the version adapted from The Art of Multiprocessor Programming:

class Peterson
{
private:
    // indexed by thread ID, 0 or 1
    bool _interested[2];
    // who's yielding priority?
    int _victim;
public:
    Peterson()
    {
        _victim = 0;
        _interested[0] = false;
        _interested[1] = false;
    }
    void lock()
    {
        // threadID is thread local,
        // initialized either to zero or one
        int me = threadID;
        int he = 1 - me;
        _interested[me] = true;
        _victim = me;
        while (_interested[he] && _victim == me)
            continue;
    }
    void unlock()
    {
        int me = threadID;
        _interested[me] = false;
    }
}

To explain how it works, let me impersonate one of the threads. When I (the thread) want to take a lock, I set my _interested slot to true. I am the only writer of this slot, although the other guy can read it. I also toggle the _victim switch to point to myself. Now I check if the other guy is also interested. As long as he is, and I am the victim, I spin. But once he becomes uninterested or turns himself into a victim, the lock is mine. When I’m done executing critical code, I reset my _interested slot, thus potentially releasing the other guy.

Let me simplify this a little, and partition the code between the two threads. Instead of an array _interested, there are two variables zeroWants and oneWants corresponding to the two slots.

zeroWants = false;
oneWants = false;
victim = 0;
Thread 0 Thread 1
zeroWants = true;
victim = 0;
while (oneWants && victim == 0)
 continue;
// critical code
zeroWants = false; 		oneWants = true;
victim = 1;
while (zeroWants && victim == 1)
 continue;
// critical code
oneWants = false;

Finally, let me rewrite the initial part of the execution in pseudo assembly.

Thread 0 Thread 1
store(zeroWants, 1)
store(victim, 0)
r0 = load(oneWants)
r1 = load(victim) 		store(oneWants, 1)
store(victim, 1)
r0 = load(zeroWants)
r1 = load(victim)

Now look at the loads and stores to zeroWants and oneWants. They follow the same pattern as in the x86 reordering example. The processor is free to move the read of oneWants before the write to zeroWants (and to victim). Similarly, it can move the read of zeroWants before the write to oneWants. We may end up with the following execution:

Thread 0 Thread 1
r0 = load(oneWants)
store(zeroWants, 1)
store(victim, 0)
r1 = load(victim) 		r0 = load(zeroWants)
store(oneWants, 1)
store(victim, 1)
r1 = load(victim)

Originally, both zeroWants and oneWants are initialized to zero, so both r1 and r2 may end up zero. In that case, the spin loop is never executed and both threads march into the critical section. Peterson lock on the x86 is broken!

Of course, there is a way to fix it. An mfence will force the correct ordering. It can be put anywhere between the store of zeroWants and the load of oneWants in one thread, and between the store of oneWants and the load of zeroWants in the other thread.

So here we have a real-life example that requires an actual fence on an x86. The problem is real!

 

September 1, 2008

Thin Lock vs. Futex

Posted by Bartosz Milewski under Concurrency, Multicore, Programming
[10] Comments 

After my post on thin locks, several people asked me why not use a futex (fast userspace mutex) instead. They referred to a Linux implementation described in “Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux” by Franke and Russel from IBM. The questions prompted me to do some research, and here’s what I’ve found.

Futex is not mutex

Futex doesn’t have Lock/Unlock operations. Instead it’s a primitive that may be used to implement a fast userspace mutex. The two relevant operations are Wait and Wake. Both result in kernel calls, except in one case: The Wait call takes two arguments: one is the address of a user-defined integer variable, the other is the expected value of that variable. If the values don’t match, the call returns immediately. This prevents missed wakeup calls–a common problem with condition variables.

Building a futex mutex

Buildning a mutex from those primitives is a nontrivial task. It requires writing some user code to test and manipulate a user-level integral variable representing the lock. A typical implementation (see “Futexes are Tricky” by Ulrich Drepper–and also the code at the end of this post) assigns tree states to a futex variable:

  • zero means that the lock is not taken,
  • one that it’s taken but no other thread is blocked on it,
  • two means that the lock is taken and in all likelihood there are threads waiting for it.

To lock the mutext, user code tries to CAS the futex variable from zero to one. If successful, the call returns immediately (we have taken the lock).

Unlock tests if the futex variable is equal to one (we are the owner, and nobody is waiting). If true, it sets it to zero. This is the fast-track common-case execution that doesn’t make any futex calls whatsoever.

All other cases end up making futex kernel calls.

Let me summarize this

The fast path is implemented by the client. Only when the client detects contention (the CAS failed), does she escalate to the kernel call. However, before she can safely escalate, she has to wait for the lock to be released, otherwise the thread that holds the lock might do the wrong thing when unlocking. It’s up to the client to make the wait busy (spinlock) or to use futex to conditionally sleep on the futex variable.

Compare this with the thin lock implementation. Here too, the fast path is implemented by the client. Only when the client detects contention, does he inflate the lock (and escalate to the kernel call). But before the lock can be inflated, he has to wait for the lock to be released. In the current implementation this wait is busy.

What’s the main difference between the two?

The thin lock implementation inflates the lock only once–the first time it detects contention. It then switches implementation to use OS locking directly. The futex implementation escalates to the kernel call every time there is contention.

The two algorithms are optimized for different scenarios. Thin lock assumes that once contention happens, it will happen over and over again. This assumption has some empirical support, as the authors of the thin lock paper assert. Converseley, under heavy contention, the futex implementation forces every thread to escalate, which involves (potentially mutlitple) conditional waits.

Obviously there are many (often hidden) factors that might influence performance under heavy contention, so I wouldn’t automatically assume that the futex is slower. Only actual measurements could provide solid arguments.

Ultimately, what weighs the heaviest against the use of a futexes in monitors is how much that would special-case the Linux implementation. Granted, Windows has its own “slim” locks, but they are different enough from futexes to preclude significant refactoring. Plus they are only available on Vista (Google for Slim Reader/Writer (SRW) Locks to find out more).

Futex code

This is my version of the code described in Drepper’s article. CAS stands for atomic compare-and-store. Here, CAS returns true on success–it has seen the expected value and it stored the new value in its place.

class FastMutex
{
public:
    FastMutex() : _word(0) {}
    void lock()
    {
        // try to atimically swap 0 -> 1
        if (CAS(&_word, 0, 1))
            return; // success
        // wasn't zero -- somebody held the lock
        do
        {
            // assume lock is still taken, try to make it 2 and wait
            if (_word == 2 || CAS(&_word, 1, 2))
            {
                // let's wait, but only if the value is still 2
                futex_wait(&_word, 2);
            }
            // try (again) assuming the lock is free
        } while (!CAS(&_word, 0, 2);
        // we are here only if transition 0 -> 2 succeeded
    }
    void unlock()
    {
        // we own the lock, so it's either 1 or 2
        if (atomic_decrement(&_word) != 1)
        {
            // it was 2
            // important: we are still holding the lock!
            _word = 0; // not any more
            // wake up one thread (no fairness assumed)
            futex_wake(&_word, 1);
        }
    }
private:
    int _word;
};

Don’t design these mutexes at home!

The trickiest part of this algorithm is that a thread that doesn’t own the lock may modify it. Look at the CAS from 1 to 2. This change may become visible to the lock owner in the middle of unlock. Suppose that the lock value was 2 to begin with. The unlocker decrements it to 1. At this point another thread may CAS it back to 2 and call futex_wait.

  • If the wait happens before the unlocker resets _word = 0, the wakup call is already bound to happen.
  • If, on the other hand, the unlocker manages to reset _word and call futex_wake, we are still fine. The wakeup call won’t be lost, because the other thread will enter futex_wait expecting 2 and finding 0 (or 1, if yet another thread grabbed the lock in the meanwhile).

And this is just one of the many possible interleavings! A full analysis would require a separate post.

 

August 24, 2008

Threads Don’t Scale, Processes Do

Posted by Bartosz Milewski under Concurrency, D Programming Language, Erlang, Multicore, Multithreading, Programming
[18] Comments 

With the multicore explosion in the making, are we going to be running hundreds of thousands of threads in a single program? Erlang programmers would emphatically say, yes! C++ and Java programmers would probably say no.

Why this discrepancy?

Thread model based on heavy-duty OS threads and mutexes has its limitations. You can ask server writers, or Google for “thread per connection” to convince yourself. Servers use thread pools exactly because of that.

Thread pools are an admission of defeat for the thread model. Having to pool threads tells you that:

  • Thread creation is not fast enough
  • Threads’ consumption of resources is substantial, so it makes sense to keep their numbers down

Granted, these are technical problems that might be overcome in future by improvements in operating systems.

The more fundamental problem with threads has its root in memory sharing. It seems like sharing offers great advantage in terms of performance, but sharing requires locking. It’s a well known fact that locking doesn’t scale (or compose). Between races and deadlocks, it’s also extremely hard to get right.

Here’s what Erlang does

Erlang gives up on sharing!

Threads that don’t share memory are called processes. We tend to think of processes as heavyweight beasts implemented by operating systems. That’s because one needs the operating system to strictly enforce the no-sharing policy (the isolation of address spaces). Only the OS can manage separate address spaces and the passing of data between them.

But that’s not the only way. The isolation might instead be enforced by the language. Erlang is a functional language with strict copy semantics and with no pointers or references. Erlang processes communicate by message passing. Of course, behind the scenes, messages are passed through shared memory, thus avoiding a large performance hit of inter-process communication. But that’s invisible to the client.

Erlang rolls out its own threads!

Erlang interpreter provides lightweight processes (so lightweight that there’s a benchmark running 20 million Erlang processes).

And there is a bonus: Erlang code that uses lightweight processes will also work with heavyweight processes and in a distributed environment.

Why don’t we all switch to Erlang?

As far as I know there are two main reasons:

  • It’s a weird language. Don’t get me wrong, I love functional programming for its mathematical beauty, terseness, and elegance. But I had to rewire my brain to be able to write pure functional programs. Functional paradigm is as alien to our everyday experience as quantum mechanics. (CS grad students: you’re not typical programmers.)
  • Messages have to be copied. You can’t deep-copy a large data structure without some performance degradation, and not all copying can be optimized away (it requires behind-the-scenes alias analysis). This is why mainstream languages (and I will even include Scala in this category) don’t abandon sharing. Instead they rely on programmer’s discipline or try to control aliasing.

Conclusions

Native threads are expensive. Interpreted languages, like Erlang, can afford to implement their own lightweight threads and schedulers. I don’t see that happening in compiled languages. The hope is that  operating systems will improve their implementations of threads–I hear Linux’s NPTL already is a big improvement in this area. In the meanwhile, we have to rely on thread pools.

Shared memory concurrency model is the reason why multithreaded programming is so difficult and error-prone. Separating address spaces simplifies programming, but at a performance cost. I believe that some kind of compromise is possible. A message-passing or an actor model can work with sharing, as long as aliasing is under control.

Inspiration for this post

After my last post on thin lock implementation, I was asked the question, why I used such a small number, 1024, for the maximum number of threads. It was actually a number I’ve found in the D compiler runtime. A thin lock could easily work with a much larger number of threads. In fact I’m going to substantially increase the number of bits for thread ID at the expense of recursion count. But this question got me thinking about scalability of threading in general.

Fibers

Fibers (as well as Java’s green threads) are not an alternative to heavyweight threads. Fibers can’t run in parallel, so they have no way to use multiple processors. They are more of a flow-of-control construct, often used interchangeably with coroutines.

Interesting reading

 

August 16, 2008

Thin Lock Implementation

Posted by Bartosz Milewski under Concurrency, D Programming Language, Multicore, Programming
[4] Comments 

Previously I have described a thin lock as a very efficient implementation of object monitor. It’s time to flesh out the design. Since most of the thin lock implementation is itself lock free, all kinds of multicore subtleties come into play. I did my best to analyze every step, but I’m only human. The code hasn’t yet been written in D, much less tested.

Object Layout

Every object (instance of a class) in the D programming language inherits from Object. Object contains a hidden header consisting of two fields:

  • pointer to vtable
  • pointer-sized thin lock

I’m not adding any new fields, just replacing an existing pointer field with the thin lock. The pointer used to point to a lazily evaluated Monitor object.

Thin lock is a union of a bit field and a pointer to a FatLock struct. The union is discriminated by the two lowest bits–if they are zero, it’s a pointer. A null pointer has special meaning–the object can never be shared (it was created as non-shared). See sharing and unsharing n D.

Here’s the thin lock bit-field layout (the low 32-bits; the whole field is either 32- or 64-bit wide, depending on native pointer size).

Bits Name Purpose
11 thread index One-based index into the global thread table
19 recursion counter Used for recursive locking by the same thread
1 currently shared Set during the creation of a shared object. It can be turned off and back on with the help of sharing casts.
1 created shared Set only if the object was created as shared

D runtime has a fixed-size global array of threads. An index into this array is used to identify a thread. This is different from the operating-system-defined thread ID.

Sharing policy

To share an object between threads, it must be created as shared (possibly allocated from a separate, shared heap). Any global object that is not declared shared is only accessible through thread-local handles.

A shared object’s thin lock (which hasn’t been inflated to a fat lock, see later) has the two lowest bits set. Sharing can be cast away, at which point the currently-shared bit is cleared, but the created-shared bit is still on. The object can then be cast back to shared; however, if the created-shared bit is not on, such a cast will throw an exception.

This guarantees that an object that was not created for sharing can never be cast to shared.

When sharing is cast away, the casting thread’s identifier is remembered in the thread index field. The object becomes exclusively owned by the current thread (essentially, locked by it). Any attempt by a different thread to lock such an object will result in an exception.

Locking a never-shared object

An object that was created as non-shared (the default) has zero in its thin lock. This state is permanent and not reachable from any other state.

Originally I thought that the comparison (thinlock == 0) didn’t require any synchronization. I totally spaced out on publication safety (thank you, Andrei, for a reality check!). In general, this test has to be preceded by a read fence. Fortunately, on an x86, publication safety is guaranteed without fencing, so at least on that platform, the check is lightning fast. Because the thin lock is co-located with the rest of the object–next to the vtable pointer–even the overhead of fetching it from main memory is rarely incurred.

Therefore the incentive for writing two versions of a class–one with synchronized, and the other with non-synchronized methods–is practically absent in D.

I mentioned before that the D compiler might be able to elide synchronization of non-shared objects altogether. If that happens, the testing of the two sharing bits in the thin lock would be redundant. There is however a code-size/performance trade-off between the two solutions.

Locking algorithm

– Test thin lock for zero (on an x86, without any synchronization, otherwise precede it with a read fence). If zero, return. This is the most common case: the object was not created for sharing and will never be accessed by another thread.

– Fetch current compact thread ID, which is conveniently stored in thread-local memory. Compact thread ID is pre-calculated for each thread using an 11-bit thread index (see above) shifted left by 21 and OR’ed with 3 (the lowest two bits are set). This is an optimization. Notice that an XOR with a compact thread ID flips the two lowest bits of the thin lock, which makes subsequent tests look logically inverted.

– XOR thin lock with this ID. If the result is 2 (remember the inversion), return. This is the case when the object was created shared, but was cast to non-shared by the current thread. This operation doesn’t require any synchronization, because only the current thread could cast the object back to shared.

if (thinlock ^ compactThreadId == 2)
  return;

– If we are past this point, we know that the object is shared, or we are attempting (incorrectly) to lock an object that is exclusive to (cast to non-shared by) another thread.

– Perform a CAS (atomic Compare And Swap operation) on thinlock. The value we are expecting is 3 (two lowest bits set and noting else), the replacement value is the compact thread ID of the current thread. This operation will succeed in the next most common case–the object is shared but is not currently locked. The resulting thin lock state has the thread index filled with a non-zero value, and the two lowest bits set (see the description of compact thread ID). This state is interpreted as “locked once by a given thread”.

– If the CAS fails (thinlock didn’t have the expected value and the swap did not occur), we know that the object is locked (or the thin lock has been inflated to a fat lock, see later).

– Try the next most common case–the object is locked by the current thread (recursive locking). First XOR the value of the thin lock with the current compact thread ID to isolate the count field. If the result is less that the maximum count shifted left by 2 and the two lowest bits are zero (meaning, they were set before the XOR), then increment the count. These operations don’t require any synchronization, because they only succeed when the lock is owned by the current thread.

uint tmp = thinlock ^ compactTID;
if (tmp < MAX_COUNT_MASK && (tmp & 3) == 0)
{
  thinlock += COUNT_INCREMENT;
  return;
}

– Check for the error of trying to lock an object that is owned exclusively by another thread.

if ((thinlock & 3) == 1)
  throw new ExclusiveLockViolation;

– Check if the lock has been inflated (the two lowest bits are zero). If so, interpret the thin lock as a pointer to FatLock and lock it. Fat lock is implemented using the operating system locking primitives and can deal with contention. Return.

– If we reach this point, we know that there is contention for the lock or the count has overflowed. In either case we have to inflate the lock. We have to preserve one invariant–the lock can only be modified by the thread that holds it, otherwise we are open to all kinds of races. Therefore we have to busy-wait for the lock to be released.

while (thinlock != 3 && (thinlock & 3) != 0)
  compiler_fence();

Notice that busy waiting requires that the compiler not optimize this loop–we need a “compiler fence”. However, no processor memory fences are required, because there is no ordering dependence. It’s enough that, when another thread modifies the lock, the new value eventually becomes visible to the spinning thread.

It’s possible to miss the unlocked state and spin longer than necessary. Starvation is theoretically possible if the other thread keeps unlocking and locking without discovering a contention; with the current thread repeatedly missing the unlocked state. (This part of the algorithm may be optimized further by introducing exponential backup.)

– The loop is exited if either the lock has been released (thinlock == 3) or another thread managed to inflate the lock (the two lowest bits are zero, signifying that the value stored is a pointer to FatLock).

– Try to acquire the lock using CAS (the arguments are the same as in the original attempt).

– If it succeeds, allocate the fat lock, lock it, and atomically store the pointer to it in the thin lock. Return. Once the lock has been inflated, it will remain so for the lifetime of the object.

– If we reach this point, we know that: either the lock has been inflated, another thread is in the process of inflating it, or another thread has acquired the lock without contention while we were busy waiting.

– Try again: go back to busy waiting.

Unlocking

When unlocking, we have the guarantee that the current thread owns the lock, so we don’t need any additional synchronization.

  • If the thin locks is zero, return. The object was not created for sharing.
  • XOR thin lock with the compact thread ID.
  • If the result is 2, we own the object exclusively. Return.
  • If the result is zero, we hit the next most common case–the lock has been taken once by the current thread. Store 3 in the thin lock and return.
  • If the result of XOR is non-zero and its lowest two bits are clear, decrement the recursion count.
  • Otherwise, the lock has been inflated. Unlock the fat lock.

FatLock must also contain a field exclusively-owned-by. This field is filled with a compact thread ID when sharing is cast away. When sharing is re-established, this field goes back to zero. Therefore, after locking the fat lock, additional checking is done: If the field is non-zero and the result of XOR with the current compact thread ID is also non-zero, an exception is thrown (attempt to lock an exclusively owned object).

 

August 11, 2008

Sharing and Unsharing of Data Between Threads

Posted by Bartosz Milewski under Concurrency, D Programming Language, Multicore, Multithreading, Programming
Leave a Comment 

I already mentioned the paper, SharC: Checking Data Sharing Strategies for Multithreaded C, by Anderson at al. The authors describe a strategy for checking multithreaded correctness of C programs. They were able to classify sharing modes into five categories:

  • Private (to current thread)
  • Read only
  • Shared under a specific lock (the lock is part of the type)
  • Racy (no checking)
  • Dynamically checked (to be either read-only or private)

The programmer makes strategic annotations by adding sharing type qualifiers to declarations of shared data. The SharC tool then derives the rest, and flags inconsistencies. There is also a run-time component for checking dynamically shared data and allowing safe casting between sharing modes.

You might notice some similarities to the D sharing model. For one, SharC assumes that all unannotated sharing is unintended and treats it as an error. In D, if you don’t annotate something as shared, it will be allocated from thread-private pool and it will be invisible to other threads.

The annotation system of SharC was not designed to be very practical. The authors didn’t expect the programmer to precisely annotate all shared variables–it’s clearly too much work. Instead they fell back on global program analysis, which is quite expensive and requires access to all sources.

In D we’ll have to make a few compromises to get maximum benefit from the types system without over-burdening the programmer with tedious annotations. (Making the right trade-offs is the hardest part of language design. You know you got it right when half of the programmers hate you for making it too strict, and the other half for making it too relaxed.) D reduces sharing annotations to just two type qualifiers: shared and invariant. I talked about shared in one of my previous post. The invariant type modifier is already well defined and in use in D 2.0.

The most interesting part of any sharing scheme based on types is the transitions between modes. A common example where such transitions might be desirable is in the producer consumer queue. Objects may be passed between threads–through the queue–either by value or by reference. When they are passed by reference, they have to be shared–multiple threads may access them concurrently. However, once the consumer gets exclusive access to such an object, she might want to treat it as non-shared. Why? Because she might want to pass itto a library function, which was not designed to deal with shared objects.

For obvious reasons we don’t want conversions between shared and non-shared data to be implicit. That would pretty much defeat the whole scheme. So we are left with explicit casting. Here’s my current thinking (which hasn’t been peer-reviewed yet).

There are two types of casts, unchecked and checked. An unchecked cast always succeeds (assuming it compiles), a checked one might throw an exception. C++ dynamic_cast is checked. So is D cast when applied to class objects. There are unchecked casts for numeric types in D, but the standard library provides a checked template to (in the module std.conv), which checks for over- and underflows.

How can you check a cast that strips the shared modifier– i.e., privatizes the object? SharC offers one solution–reference counting.

You can be 100% sure that no other thread has access to your shared data when you can prove that you have the only reference to it. SharC’s run-time uses a very clever reference counting scheme borrowed from a garbage collector to accomplish just that. Could we do it in D? We probably could, if we committed to the reference-counting GC, but that’s rather unlikely.

What’s the next best thing? Locking the object! This will only work for class objects, which have a built-in monitor but, at least in the SafeD subset, we expect class objects to play a major role. Locking the object when privatizing it has several advantages.

  • It will fail if the object is already locked by another thread
  • If another thread still has shared access to it after privatization, and tries to lock it, it will fail
  • The reverse operation, casting an object back to shared, can be checked.

Most of this can be easily accomplished by slightly modifying thin locks (see my previous post). I’ll provide more details later.

Now, let’s talk about casting back to shared (I’m using “back” deliberately, as we don’t want to share objects that were created as non-shared). This cast is much more tricky, since a lot of bad things might have happen while the object was unshared. We can check for some of them and trust the programmer not to do others.

We have to trust the programmer not to squirrel away non-shared aliases to a temporarily unshared object (or its internals). Such aliases become unprotected back doors to the object when it becomes shared again. Remember that, even if you call a synchronized method on an object that is not declared as shared, the synchronization is statically elided by the compiler (at least that’s the plan).

Another danger is that non-shared objects may be inserted into a temporarily unshared object. For that we could check during casting, if we used a different heap for allocating shared objects. We could ask the garbage collector if a given pointer points into the shared heap or not. For class objects, this check can be made much faster by testing a special bit in the thin lock.

Checked sharing casts in both directions have to be recursive, since the shared qualifier is transitive. When casting from shared to non-shared, each class object must have its thin lock put in the “exclusively owned by current thread” state. When casting back to shared, each class object must have its thin lock put back in the sharing state, and all pointers must be checked against the shared heap.

Conveniently enough, in D, such checked casts can be implemented in the library using unchecked casts and reflection.

 

August 4, 2008

Multicores and Publication Safety

Posted by Bartosz Milewski under Concurrency, D Programming Language, Multicore, Multithreading, Programming
[12] Comments 

Publication safety is the core issue in the famously non-intuitive Double-Checked Locking Pattern.

What’s publication? In a nutshell, one thread prepares data and publishes it–other threads check if the data has been published and use it. Common scenario is the creation of a shared object (this example is written in the D programming language, but it’s pretty self-explanatory).

shared Foo foo = new shared Foo();

When a thread creates an object, it first runs its constructor (Foo()) and then points the shared handle (foo) to it. Other threads check the handle for non-null and then happily access the object.

if (foo !is null) foo.doSomething();

Naturally, in our naivete, we tend to assume that if the second thread can see a non-null handle, the construction of the object must have completed. That belief is known as publication safety and, guess what!, it’s not guaranteed on modern multi-processors that use relaxed memory models.

To understand what’s happening, let’s simplify the problem even further and write it in pseudo assembly. Initially the globals x and ready are zero. R is a thread-local variable (register). Think of writing to x as part of the construction of an object and writing to ready as the publication (the initialization of a shared handle).

Thread 1 Thread 2
x = 1
ready = 1		 if ready == 1
R = x

Can Thread 2 see ready == 1 and x == 0? Yes, for two separate reasons. On a relaxed-memory-model multiprocessor

  1. writes to memory can be completed out of order and
  2. reads from memory can be satisfied out of order.

Imagine processors sending e-mail messages to memory. Thread 1 sends a message instructing the memory to write 1 to x. Then it sends another message instructing it to write 1 to ready. It’s perfectly possible on modern processors that the first message gets delayed and the write to ready completes before the write to x.

The way to make sure this doesn’t happen is to separate the two writes by a memory barrier, or fence. Every relaxed-memory-model multiprocessor offers some ways to do it. The x86’s (x > 3) have such instructions (mfence, lfence, and sfence), even though they implement processor-order memory model.

But beware, even if the writes are ordered by a (write) fence, the reads in Thread 2 may still execute out of order. Imagine that Thread 2 sends two e-mail messages asking for the values of ready and x. The second message arrives first, before any writes by Thread 1 are done. The memory sends back an e-mail with the value 0 for x. Next, the two writes by Thread 1 are committed. Then the first read message (fetch ready) arrives, and the memory responds with the value 1. Thread 2 sees a non-zero value of ready, but a zero (uninitialized) value of x. We’re in trouble!

Notice that the read of x is speculative. The processor issues the read request just in case the branch ready == 1 were taken. If it’s not, it can always abandon the speculation.

Again, the way to ensure that the two reads are satisfied in program order is to put a fence between them. Here’s the pseudocode.

Thread 1 Thread 2
x = 1
write fence
ready = 1		 if ready == 1
read fence
R = x

Both fences are necessary!

The write fence is easier to remember. In our publication example,  it makes sense to put it at the end of the constructor. It has the connotation of flushing all the writes performed during construction, before the public handle is initialized.

It’s the need for the read fence that is often overlooked. It’s not immediately obvious that every time you access a published shared variable you have to use a fence. It’s the “every time” part that seems excessive, especially if your code initializes the handle only once (as in the double-checked locking pattern). Sure, there are a few cases when a benign race is acceptable, but even the best of us get it wrong half of the time.

Why is this whole low-level discussion relevant? Very few programmers will be inserting (non-portable) fences into their code. Most programmer will use monitors and locks, which have appropriate fences (or their equivalents) built in. Java programmers will mark shared variables volatile, which will tell the compiler to issue memory fences on every access. C++ and D programmers will occasionally use atomics, which are implemented with all the fencing in place.

But look at it this way: This is a cautionary story for high-level programmers too. Do not elide synchronization even in the simplest, seemingly obvious cases! Don’t try to be clever! The processors (and the compilers) are out there to get you. The slightest slip and they will “optimize” your code in a way that is contrary to your intuitions.

 

August 1, 2008

Musings about the D Memory Model

Posted by Bartosz Milewski under Concurrency, D Programming Language, Multicore, Multithreading, Programming
Leave a Comment 

Most modern multi-processors implement relaxed memory models. How much should you care about that?

When you program in a high-level language, you shouldn’t have to worry about your processor’s memory model, as long as you follow some simple rules.

In Java, for instance, you must make sure that access to shared variables (both for reading and writing) is protected by locks (e.g., synchronized sections). If you are adventurous, and want to share variables without locking, you must declare them as volatile. Finally, if you try to share non-volatile variables without locking, you are introducing data races and your program is considered incorrect (it might still work on some processors). This is what the Java memory model is about, in a nutshell.

C++ memory model proposal takes a similar approach, except that the use of volatile is replaced by the atomic library. Renegade Java programmers beware–C++ volatile has no multi-thread connotations (except in some vendor-specific extensions).

The D programming language tries to bridge the gap between safe and simple (Java-like), and unsafe and efficient (systems) programming. That almost requires two different memory models.

In the SafeD subset, we’d ideally want to ban all races and deadlocks. That could be accomplished only by eliminating lock-based programming. It seems like a drastic step until you consider that (a) you could still use certified libraries that internally use locking, and (b) you’d have futures, message passing, and STM (Software Transactional Memory) at your disposal. There are languages, like Erlang, that base all concurrency on message passing. And there’s a lot of code written in Erlang, despite its idiosyncratic syntax.

On the systems-programming end, D might as well follow the C++ memory model, down to “raw” atomics, which let you introduce low-level data races.

The volatile keyword is reserved in D, but it’s not clear what it should mean. We might simply get rid of it or change its definition. The problem is that volatile means many different things. In Java, it’s both a directive to the compiler to insert appropriate fences (memory barriers), as well as a directive to the optimizer not to perform code motion or caching. This is also how Microsoft implemented volatile in their C++ compiler. In principle, code motion and fencing are orthogonal issues. Hans Boehm’s implementation of atomics, for instance, uses a low level primitive AO_compiler_barrier, which prevents code movement without introducing memory fences (it’s implementation is very compiler-specific).

Of course, the D atomics library would not be certified for use in SafeD; but some lock-free data structures based on it, would.

 

July 30, 2008

Sharing in D

Posted by Bartosz Milewski under Concurrency, D Programming Language, Multicore, Multithreading, Programming
1 Comment 

Andrei brought up the idea of encoding the sharing of an object between threads in the type of the object. After months of discussions we are still not sure how far we want to go with it. One thing is for sure, letting the programmer mark objects for sharing can help the compiler prevent a lot of concurrency bugs.

One of the common concurrency errors is accidental sharing. Some data structures are designed for multi-threaded access, e.g., objects with synchronized methods; and they usually work just fine (except for deadlocks). The problem is when a chunk of data that was not designed for sharing is accessed by multiple threads. There is no easy way to detect this error since, in general, concurrency bugs are hard to reproduce.

The proposal is to make accidental sharing impossible. This requires that all objects, by default, be thread local. For instance, if you declare a global object and initialize it in one thread, another thread will see a different version of this object. In most cases it will see a null pointer or an unitialized object handle, and you’ll get an easy to reproduce null-reference error.

If you consciously want to share an object, you have to declare it “shared”. This type modifier is transitive (just like const and invariant in the D programming language), so you  can’t have references to non-shared object inside a shared object. It simply won’t compile.

A function may declare its (reference) parameter as “shared”, in which case the compiler won’t let you pass a non-shared object to it. Conversely, if the parameter is declared as non-shared (the default), no shared argument may be passed in its place. There is a guarantee that it will be thread-local. (See however “unsharing”.)

Let me discuss potential objections to this scheme.

The first is performance–not for shared objects, mind you, but for the non-shared ones. Walter tells us that accessing a thread-local static variable adds between 1 to 3 instructions of overhead. That seems quite reasonable. Especially considering that in multi-threaded environment the use of global non-shared variables is rarely correct.

There is also a performance penalty when starting a new thread–all static variables it has access to have to be default-initialized, plus all module constructors have to be called. This might amount to quite a bit. We will recommend not to overuse global variables and module constructors. The way to amortize this cost is to create thread pools.

What about invariant objects (ones that are never modified)? Those can be safely shared, so they must be allocated as not thread-local. It is okay for a shared object to contain references to invariant objects.

Can a shared object be “unshared”? This is a tricky one. There are situations when threads hand over objects to each other. The object is only shared during the handover, but otherwise is accessed by one thread at a time. The currently owning thread should be able to call regular library functions (that don’t expect sharing) with such objects. So we need some kind of share/unshare cast. On the other hand, such cast creates a wormhole into accidental sharing. There is an interesting SharC paper that discusses runtime techniques to make “unsharing” safe. Safe casting from temporarily non-shared to shared is even more tricky. I’ll talk more about it in my next post.

Finally, there is an unexpected bonus from this scheme for the garbage collector. We will be able to use a separate shared heap (which will also store invariant objects), and separate per-thread heaps for non-shared objects. Since there can’t be any references going from the shared/invariant heap to non-shared ones, per-thread garbage collection will be easy. Only occasional collection of the shared heap would require the cooperation of all threads, and even that could be done without stopping the world.

 

July 24, 2008

Thin Locks in D

Posted by Bartosz Milewski under Concurrency, D Programming Language, Multicore, Multithreading, Programming | Tags: |
[11] Comments 

I’ve been working recently on improving the performance of locking in D (the D programming language). At this moment the synchronized statement in D simply uses the underlying OS facilities–CriticalSection on Windows and pthread  mutex on Linux. This incurs a substantial performance hit for multithreaded programming.

I looked at research in the Java community and found some interesting solutions. They are all versions of Thin Locks, first described by Bacon et al. These guys figured out that when a program is entering a synchronized section, in about 80% of the cases the section is not locked by anybody. The next most common case is nested locking–the section is locked by the same thread recursively. Only rarely there is actual contention for a lock.  And when that happens, it’s very likely that it will happen again and again. Such contended lock is most likely part of a shared data structure designed to be accessed by multiple threads.

Thin Locks optimize the most common case of no contention. Every Java Object has a word in its header that is used as a thin lock. If this field is zero (I’m skipping details here), the object is not locked. When a thread enters a synchronized section, it optimistically assumes that the lock is zero and tries to flip it to a non-zero value. This is done in one atomic operation, Compare And Swap (CAS). Most processor either have such an instruction built in, or provide primitives to implement it.

CAS checks the value in memory, comparing it to the “expected value.” If the comparison succeeds, the “new value” is written in its place. In our case, we expected the value of the thin lock to be zero, and the new value we want to put there is the (non-zero) thread ID of the lock taker. If the CAS succeeds, we are done, we owne the lock.

If the CAS fails, the lock has already been taken. Again, the most likely case is that our own thread holds it. So we check if our thread ID is stored in the thin lock. If so, we increment the count field of the thin lock (several fields are cleverly mashed together into one word). We’re done!

If we don’t find our own thread ID in the thin lock, we know we have contention. We have to inflate the lock–allocate an additional object (the fat lock) that holds the general-purpose OS-based mutex. Of course we also check if the thin lock hasn’t already been inflated, in which case we just lock the fat lock.

The inflation process is a little tricky–we can’t just modify the thin lock while it’s bein held by another thread. Instead we spin wait for it to be released, then try to acquire it ourselves, and then inflate it. Once inflated, the lock remains inflated forever; which usually is the right thing to do anyway, since a lock that’s been contended once, is likely to be contended many times. The one-time spinning is amortized across many accesses.

Of course there are details that I’ve omitted, but I gave you the gist of the algorithm.  It makes un-contended locking so cheap (one CAS) that in most cases there is no reason to implement two versions, one for single- and one for multithreaded use, of the same data structure. A single-threaded program doesn’t have to pay the multithreaded penalty when using general-purpose libraries.

 

« Previous Page