OSDev.org https://forum.osdev.org/ |
|
Best sync method/primitive for array of reference counters https://forum.osdev.org/viewtopic.php?f=13&t=56409 |
Page 1 of 1 |
Author: | USRapt0r [ Sat Aug 06, 2022 2:23 pm ] |
Post subject: | Best sync method/primitive for array of reference counters |
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! |
Author: | Octocontrabass [ Sun Aug 14, 2022 8:38 pm ] |
Post subject: | Re: Best sync method/primitive for array of reference counte |
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: #include <stdatomic.h>
#include <stdbool.h> bool example( atomic_int * counter ) { return !--*counter; } |
Author: | Demindiro [ Mon Aug 15, 2022 4:28 am ] |
Post subject: | Re: Best sync method/primitive for array of reference counte |
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. |
Author: | Gigasoft [ Mon Aug 15, 2022 9:31 am ] |
Post subject: | Re: Best sync method/primitive for array of reference counte |
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. |
Author: | Octocontrabass [ Mon Aug 15, 2022 11:53 am ] |
Post subject: | Re: Best sync method/primitive for array of reference counte |
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. |
Page 1 of 1 | All times are UTC - 6 hours |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |