Implement a thread-safe invalidate-able cache with lock-free reads?

Question

I am trying to reason out in my head how to implement a thread-safe caching mechanism for a reference counted value with an API roughly like this: (Note: I'm using Objective-C syntax, but the problem is not language-specific)

typedef id (^InvalidatingLazyGenerator)();

@interface InvalidatingLazyObject : NSObject

- (id)initWithGenerator: (InvalidatingLazyGenerator)generator;

@property (readonly) id value;

- (void)invalidate;

@end

When someone requests -value, if it has an existing cached value, it should return a -retain/-autoreleased version of that value. If it doesn't have a value, or if the value isn't valid, it should generate one using a generation block passed in at init time, then it should cache that value for any future reads until someone calls -invalidate.

Let's assume we don't care if the generator block is called multiple times (i.e. a second reader arrives while the first reader is in the generator block), as long as the objects it returns aren't leaked when that happens. A first pass, non-wait-free implementation of this might look something like:

- (id)value
{
    id retVal = nil;
    @synchronized(self)
    {
        retVal = [mValue retain];
    }
    if (!retVal)
    {
        retVal = [[mGenerator() retain] retain]; // Once for the ivar and once for the return value
        id oldVal = nil;
        @synchronized(self)
        {
            oldVal = mValue;
            mValue = retVal;
        }
        [oldVal release];
    }
    return [retVal autorelease];
}

- (void)invalidate
{
    id val = nil;
    @synchronized(self)
    {
        val = mValue;
        mValue = nil;
    }
    [val release];
}

Naturally, this results in crappy read performance because concurrent reads are serialized by the lock. A reader/writer lock improves things from this, but is still quite slow in the read path. The performance goal here is for cached reads to be as fast as possible (hopefully lock-free). It's OK for reads to be slow if we have to calculate a new value, and it's OK for -invalidate to be slow.

So... I am trying to figure out a way to make reads lock/wait-free. My first (flawed - see below) thought involved adding an invalidation counter whose value is atomically, monotonically incremented and read using memory barriers. It looked like this:

- (id)value
{
    // I think we don't need a memory barrier before this first read, because
    // a stale read of the count can only cause us to generate a value unnecessarily,
    // but should never cause us to return a stale value.
    const int64_t startCount = mWriteCount;

    id retVal = [mValue retain];

    OSMemoryBarrier(); // But we definitely want a "fresh" read here.
    const int64_t endCount = mWriteCount;

    if (retVal && startCount == endCount)
    {
        return [retVal autorelease];
    }

    // Now we're in the slow path
    retVal = [mGenerator() retain]; // we assume generator has given us an autoreleased object

    @synchronized(self)
    {
        mValue = retVal;
        OSAtomicIncrement64Barrier(&mWriteCount);
    }
    return retVal;
}

- (void)invalidate
{
    id value = nil;
    @synchronized(self)
    {
        value = mValue;
        mValue = nil;
        OSAtomicIncrement64Barrier(&mWriteCount);
    }
    [value release];
}

But I can already see problems here. For instance, the [mValue retain] in the read path: we need the value to be retained, but it's possible that in the time between the read of mValue and the call to -retain another thread could -invalidate, causing the value to have been dealloc'ed by the time the retain call is made. So this approach won't work as is. There may be other problems too.

Has anyone already worked something like this out and care to share? Or have a pointer to something similar in the wild?

Answer 1

I ended up taking this approach to the problem: Read-Copy-Update. It seems to work quite well -- the read performance is 50x faster than the lock-based approach (but that's hardly surprising.)