OSDev.org

The Place to Start for Operating System Developers
It is currently Mon Sep 26, 2022 11:38 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: Best sync method/primitive for array of reference counters
PostPosted: Sat Aug 06, 2022 2:23 pm 
Offline

Joined: Sat Aug 06, 2022 1:54 pm
Posts: 1
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!


Top
 Profile  
 
 Post subject: Re: Best sync method/primitive for array of reference counte
PostPosted: Sun Aug 14, 2022 8:38 pm 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 4142
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;
}


Top
 Profile  
 
 Post subject: Re: Best sync method/primitive for array of reference counte
PostPosted: Mon Aug 15, 2022 4:28 am 
Online
Member
Member
User avatar

Joined: Fri Jun 11, 2021 6:02 am
Posts: 78
Location: Belgium
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.

_________________
My OS is Norost B (website, Github, sourcehut)


Top
 Profile  
 
 Post subject: Re: Best sync method/primitive for array of reference counte
PostPosted: Mon Aug 15, 2022 9:31 am 
Offline
Member
Member

Joined: Sat Nov 21, 2009 5:11 pm
Posts: 791
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.


Top
 Profile  
 
 Post subject: Re: Best sync method/primitive for array of reference counte
PostPosted: Mon Aug 15, 2022 11:53 am 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 4142
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group