OSDev.org

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!

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:

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.

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.

Gigasoft wrote: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.