Lock-free Reference Counting

Question

I'm working on a system that requires extensive C API interop. Part of the interop requires initialization and shutdown of the system in question before and after any operations. Failure to do either will result in instability in the system. I've accomplished this by simply implementing reference counting in a core disposable environment class like this:

public FooEnvironment()
{
  lock(EnvironmentLock)
  {
    if(_initCount == 0)
    {
      Init();  // global startup
    }
    _initCount++;
  }
}

private void Dispose(bool disposing)
{
  if(_disposed)
    return;

  if(disposing)
  {
    lock(EnvironmentLock)
    {
      _initCount--;
      if(_initCount == 0)
      {
        Term(); // global termination
      }
    }
  }
}

This works fine and accomplished the goal. However, since any interop operation must be nested in a FooEnvironment using block, we are locking all the time and profiling suggests that this locking accounts for close to 50% of the work done during run-time. It seems to me that this is a fundamental enough concept that something in .NET or the CLR must address it. Is there a better way to do reference counting?

Answer 1

This is a trickier task than you might expect at first blush. I don't believe that Interlocked.Increment will be sufficient to your task. Rather, I expect you to need to perform some wizardry with CAS (Compare-And-Swap).

Note also that it's very easy to get this mostly-right, but mostly-right is still completely wrong when your program crashes with heisenbugs.

I strongly suggest some genuine research before going down this path. A couple good jumping off points pop to the top if you do a search for "Lock free reference counting." This Dr. Dobbs article is useful, and this SO Question might be relevant.

Above all, remember that lock free programming is hard. If this is not your specialty, consider stepping back and adjusting your expectations around the granularity of your reference counts. It may be much, much less expensive to rethink your fundamental refcount policy than to create a reliable lock-free mechanism if you're not an expert. Especially when you don't yet know that a lock-free technique will actually be any faster.

Answer 2

As harold's comment notes the answer is Interlocked:

public FooEnvironment() {
  if (Interlocked.Increment(ref _initCount) == 1) {
    Init();  // global startup
  }
}

private void Dispose(bool disposing) {
  if(_disposed)
    return;

  if (disposing) {
    if (0 == Interlocked.Decrement(ref _initCount)) {
      Term(); // global termination
    }
  }
}

Both Increment and Decrement return the new count (just for this kind of usage), hence different checks.

But note: this will not work if anything else needs concurrency protection. Interlocked operations are themselves safe, but nothing else is (including different threads relative ordering of Interlocked calls). In the above code Init() can still be running after another thread has completed the constructor.