Best sync method/primitive for array of reference counters

[USRapt0r]

Hello,

I'm working on a program that will utilize a sort-of garbage collection mechanism, tracked by a single array of reference counters that can be read and/or modified by multiple threads (and/or processes via shared memory). I've been researching thread/process synchronization methods to try to figure out the quickest way to atomically update the reference counters - the only operations would be to increment an element's counter (one of the counters in the array that is), or decrement it, but after decrementing, a check is made to see if the count is 0, in which case a routine is run to free the element of that reference counter. That latter part is what I'm getting hung on up - the check needs to be atomic as well to ensure multiple threads don't end up double-freeing (or leaking) the object. But the usual methods (POSIX mutexes and semaphores) seem to involve a lot of overhead, so I've also been trying to learn about transactional memory, atomic types, and even assembly methods (lock cmpxchng, though I haven't figured out how that could work). I can't help but think it could be done in userspace with minimal overhead. Would anyone have any advice?

Thank you!

[Octocontrabass]

It sounds like you want atomic types, but the specifics will depend on the language you're using and you didn't mention that.

Here's a C function that decrements a reference counter and returns true if the caller held the last reference:

Code: Select all

#include <stdatomic.h>
#include <stdbool.h>

bool example( atomic_int * counter )
{
    return !--*counter;
}

[Demindiro]

If you don't mind Rust, I recommend reading the implementation of Arc (specifically, Clone and Drop). It should give you a good idea of what to pay attention to.

[Gigasoft]

In GCC, __atomic_fetch_add or one of the other similarly named builtins does what you need. In Visual Studio, there is _InterlockedIncrement, _InterlockedDecrement and _InterlockedExchangeAdd. They map to instructions such as lock inc, lock dec and lock xadd.

[Octocontrabass]

In GCC, __atomic_fetch_add or one of the other similarly named builtins does what you need. In Visual Studio, there is _InterlockedIncrement, _InterlockedDecrement and _InterlockedExchangeAdd. They map to instructions such as lock inc, lock dec and lock xadd.

The standard library headers (stdatomic.h in C, atomic in C++) are wrappers around these builtins.