Wednesday, November 30, 2011

Read/Write Lockless Exclusion

With the recent release of iOS 5, GCD now has a simple and elegant solution to the reader writer problem that utilizes lockless exclusion. In summary, this involves using dispatch_async (or dispatch_sync) to enqueue "reader" blocks onto a user concurrent queue. These blocks may be used to read some kind of data but not write to it. If we need write access, then we can use the new dispatch_barrier_async (or dispatch_barrier_sync) function. This will put a special barrier block on the queue. The blocks are still dequeued in FIFO order. However, when there are one or more reader blocks running, then a writer block may not be dequeued. While a single writer block is running, no other blocks may be dequeued, including other writer blocks. This guarantees that writer blocks have exclusive access and reader blocks may share access.

The new barrier blocks and user concurrent queues are immensely valuable. Lately, I've been considering how they relate to my recently developed Lockless Exclusion Accessor (LEA) design pattern. If you are not already familiar with my LEA pattern, you should first read my LEA article. The intent of a LEA is to make mutual exclusion easy and efficient. Since we want to be efficient, let's push efficiency further by allowing shared read access. Here is some generic code that does just that:

/// Block type to use when accessing the shared memory.
/// The type is 'id' just to be generic. With a real
/// LEA, you should use the exact type.
typedef void(^LEABlock)(id sharedMemory);

/// Class extension for holding the private, shared memory
/// and its associated queue.
@interface MyObject ()

@property (nonatomic, strong) id sharedMemory;
@property (nonatomic, assign) dispatch_queue_t leaQueue;

@end

@implementation MyObject

@synthesize sharedMemory = _sharedMemory;
@synthesize leaQueue = _leaQueue;

- (id)init {
    if ((self = [super init])) {
        // The queue MUST be concurrent to gain shared readership.
        dispatch_queue_t queue = NULL;
        queue = dispatch_queue_create(
          "com.RobBrown.LEAQueue",
          DISPATCH_QUEUE_CONCURRENT);
        [self setLeaQueue:queue];

        // Initialize shared memory here.
    }
    return self;
}

- (void)accessSharedMemoryReadWriteAsync:(LEABlock)block {

    // Block must not be nil.
    NSParameterAssert(block);

    // Executes the block asynchronously with exclusive access.
    dispatch_barrier_async([self leaQueue], ^{
        block([self sharedMemory]);
    });
}

- (void)accessSharedMemoryReadOnlyAsync:(LEABlock)block {

    // Block must not be nil.
    NSParameterAssert(block);

    // Executes the block asynchronously with shared access.
    dispatch_async([self leaQueue], ^{
        block([self sharedMemory]);
    });
}

@end

The first thing to note is that the dispatch queue is now concurrent instead of serial. If you use a serial queue then you will have no added benefits. The next thing to note is that every previous LEA in your object splits in two: a readonly version and a read write version. It's only four extra lines for a potentially great increase in efficiency.

As always, you should favor dispatch_async over dispatch_sync. If you must have synchronous access, then you can add synchronous variants too. You must, however, never use my dispatch_sync_checked function. It is not and never will be compatible with barrier blocks.

By introducing the readonly LEA, we now introduce a potential point of failure. What if we write some code that uses a readonly LEA, then we later change the code to modify the shared memory without switching to a read write LEA? This could introduce race conditions. If needed, you can add a sanity check to your readonly LEA. Here are a few options:
  1. If the object you are passing back has mutable and immutable variants, create two block types. The read write LEA will use the mutable variant and the readonly LEA will use the immutable variant. This is the best solution.
  2. If you don't have mutable and immutable variants, then you can simply pass a copy of the shared memory to the readonly block. This can potentially mask errors since you won't know if you accidentally use a readonly LEA when you meant to use a read write LEA.
  3. Before calling the block, you copy the shared memory. Then after calling the block, you check that the shared memory was not changed by comparing it to the earlier copy. If it was changed, then throw an exception. Although Objective-C rarely throws exceptions, this is an appropriate place to do so. Overall, this solution can be tedious work. You should also use a pre-processor macro to remove this check from release builds for efficiency.
  4. You can create a subclass of NSProxy. Instead of passing back the shared memory you can pass it the proxy. This proxy should throw an exception if any setters are called. This too can be tedious work. You may want to use a pre-processor macro here as well to remove the proxy in release builds.
Don't forget that user concurrent queues and barrier blocks are iOS 5 (and Mac OS X Lion) only. If you are using iOS 5 and you need mutual exclusion, I highly recommend using Read/Write LEAs (or at least regular LEAs). They make mutual exclusion fast and easy.

Monday, November 28, 2011

dispatch_sync_safe Deprecated

A while back I wrote a pseudo-category for GCD and posted it to Github. It contains several convenience functions. One of them was a method that makes synchronous calls “safe,” or so I thought. The code looked like this:

void dispatch_sync_safe(dispatch_queue_t queue, dispatch_block_t block) {
    // If we're already on the given queue, just run the block.
    if (dispatch_get_current_queue() == queue)
        block();
    // Otherwise, dispatch to the given queue.
    else
        dispatch_sync(queue, block);
}

The idea is that when doing a synchronous dispatch to a queue, I check if the program was already running on that queue. If it is, then the block is immediately executed. Otherwise, the block is run with a regular dispatch_sync. In my naïve implementation I thought this would prevent deadlock. The idea is nice but not correct. Consider the case when we dispatch_sync_safe to queue A. Next, we dispatch_sync_safe to queue B. Finally, we dispatch_sync_safe back to queue A. This is guaranteed deadlock.

As a result of this case, I immediately marked dispatch_sync_safe as deprecated in my Github repo. Anyone using this function thinking it is perfectly safe should think again. I did, however, add another function called dispatch_sync_checked. It is actually the same implementation as dispatch_sync_safe just under a different name. I recognize that this simple function has great value, but the old name was misleading. The moral of the story is, use dispatch_async (or one of my dispatch_async convenience methods) whenever possible. If you must run code synchronously, use dispatch_sync_checked and be very cautious of deadlock.

As I mentioned previously, dispatch_sync_checked still has great value. There is at least one case where you can guarantee you won’t deadlock. Consider the case when you have an object with a private serial dispatch queue. This queue is used to serialize access to some shared memory within the object. Using dispatch_sync_checked on the private queue allows you to keep your object’s methods synchronous and thread safe. This requires following two conditions in your critical code:
  1. Do not make synchronous calls to external objects (which could synchronously call the calling object again).
  2. Do not call dispatch_sync on any queue (or dispatch_sync_checked on any queue except the private queue).
Also, since these methods check for running on the private queue, they can call each other without worrying about deadlock. This gives similar behavior to a recursive lock without the overhead. If @synchronized(self) { … } just isn’t fast enough, consider switching to dispatch_sync_checked(_queue, ^{ … }).