What is the purpose of the loop, i.e. what is the state==old_state case?
If the semantics of compare_exchange_weak is both to check whether the existing value is state, and if it is exchange, otherwise write the existing value to state, then by definition surely if the compare fails, state must != old_state.
Well compare_exchange_weak can fail spuriously, so the loop actually is necessary there. But you're right, I should just change it to compare_exchange_strong and then not loop, that's simpler/clearer.
Your library seems to be missing the code for IncRef/DecRef.
What is the usage scenario?
I'm a little worried that since the DecRef atomic decrement is relaxed, that its effects could move above the threads usage of the object such that another thread sees the first thread's decrement, decrements the count to zero, and frees the object before the first thread is done using it.
"Your library seems to be missing the code for IncRef/DecRef."
Uh, yup. Fixed.
"I'm a little worried that since the DecRef atomic decrement is relaxed, that its effects could move above the threads usage of the object such that another thread sees the first thread's decrement, decrements the count to zero, and frees the object before the first thread is done using it."
Yeah, you have a point. I'll have to think about that a little more.
Yep, of course you're right - DecRef needs to be at least mo_release. That keeps it from moving up before ops on the pointer it protects. I think that's it (?)
That need is hidden if the object is internally protected by a mutex, or if the shared reference is protected by a mutex.
I really need to get CDSChecker running cuz Relacy is no good at modeling relaxed atomics.
Some threads I found on minimal memory ordering required for refcounts :
I would think you'd need a release on the normal decrement path and load acquire (or consume??) of the count on the path that you actually do the deletion...
You have to force a synchronization between the computation that uses the object and the computation that frees it.
I expect that the release alone would keep compilers in practice from breaking your code, but it isn't technically correct.
Herb Sutter briefly discussed the memory ordering requirements for refcounts in his "atomic<> Weapons" talk:
Part 1: http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-
Part 2: http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-2-of-2
It's a long talk. The bit about ref-counts is near the end of part 2, (timecode about 1h 20)
He says: relaxed increment. Acquire+Release decrement. Having said that, he wasn't talking about weak pointers; I don't know if that adds any extra twists.
Right. The actual ref decrement here is release, but then before an object is freed there's also the acq_rel to change the guid which is in the same atomic word. The guid change provides the acquire for the freeing of the object and slot.
(I suppose it's not obvious in the posted code, but state_get_guid and state_get_refcount are just pulling bit fields out of a single word.)
It's very easy (almost trivial (*)) to make the table-based {index/guid} style of weak reference lock free.
(* = obviously not trivial if you're trying to minimize the memory ordering constraints, as evidenced by the
revisions to this post that were required; it is trivial if you just make everything seq_cst)
Previous writings on this topic :
Smart & Weak Pointers - valuable tools for games - 03-27-04 cbloom rants 03-22-08 - 6 cbloom rants 07-05-10 - Counterpoint 2 cbloom rants 08-01-11 - A game threading model cbloom rants 03-05-12 - Oodle Handle Table
The primary ops conceptually are :
Add object to table; gives it a WeakRef id
WeakRef -> OwningRef (might be null)
OwningRef -> naked pointer
OwningRef construct/destruct = ref count inc/dec
The full code is in here : cbliblf.zip , but you can get a
taste for how it works from the ref count maintenance code :
handle_guid_shift);
if ( s->m_state($).compare_exchange_strong(old_state,new_state,mo_acq_rel,mo_relaxed) )
{
// I released the slot
// cmpx provides the acquire barrier for the free :
FreeSlot(s);
return;
}
// somebody else mucked with me
}
}
The maintenance of ref counts only requires relaxed atomic increment & release atomic decrement (except when the pointed-at object is
initially made and finally destroyed, then some more work is required). Even just the relaxed atomic incs
could get expensive if you did a ton of them, but my philosophy for how to use this kind of system is that you inc & dec refs
as rarely as possible. The key thing is that you don't write functions that take owning refs as arguments, like :
void bad_function( OwningRefTThingy> sptr )
{
more_bad_funcs(sptr);
}
void Stuff::bad_caller()
{
OwningRefTthingy> sptr( m_weakRef );
if ( sptr != NULL )
{
bad_function(sptr);
}
}
hence doing lots of inc & decs on refs all over the code. Instead you write all your
code with naked pointers, and only use the smart pointers where they are needed to ensure ownership for the lifetime
of usage. eg. :
void good_function( Thing * ptr )
{
more_good_funcs(ptr);
}
void Stuff::bad_caller()
{
OwningRefTthingy> sptr( m_weakRef );
Thingy * ptr = sptr.GetPtr();
if ( ptr != NULL )
{
good_function(ptr);
}
}
If you like formal rules, they're something like this :
1. All stored variables are either OwningRef or WeakRef , depending on whether it's
an "I own this" or "I see this" relationship. Never store a naked pointer.
2. All variables in function call args are naked pointers, as are variables on the
stack and temp work variables, when possible.
3. WeakRef to pointer resolution is only provided as WeakRef -> OwningRef. Naked pointers
are only retrieved from OwningRefs.
And obviously there are lots of enchancements to the system that are possible. A major one that I recommend is to put more information in
the reference table state word. If you use a 32-bit weak reference handle, and a 64-bit state word, then you have 32-bits of extra
space that you can check for free with the weak reference resolution. You could put some mutex bits in there
(or an rwlock) so that the state contains the lock for the object, but I'm not sure that is a big win (the only
advantage of having the lock built into the state is that you could atomically get a lock and inc refcount in a single
op). A better usage is to put some
object information in there that can be retrieved without chasing the pointer and inc'ing the ref and so on.
For example in Oodle I store the status of the object in the state table. (Oodle status is a progression
through Invalid->Pending->Done/Error). That way I can take a weak ref and query status in one atomic load.
I also store some lock bits, and you aren't allowed to get back naked pointers unless you have a lock on them.
The code for the weak ref table is now in the cbliblf.zip that I made for the last post.
Download : cbliblf.zip
( The old cblib has a non-LF weak reference table that's similar for comparison. It's also more developed
with helpers and fancier templates and such that could be ported to this version. Download :
cblib.zip )
ADDENDUM : alternative DecRef that uses CAS instead of atomic decrement. Removes the two-atomic free path.
Platforms that implement atomic add as a CAS loop should probably just use this form. Platforms that have
true atomic add should use the previously posted version.
// DecRef
void DecRef( handle_type h )
{
handle_type index = handle_get_index(h);
LF_OS_ASSERT( index >= 0 && index < c_num_slots );
Slot * s = &s_slots[index];
// no need to check guid because I must own a ref
handle_type state_prev = s->m_state($).load(mo_relaxed);
handle_type old_guid = handle_get_guid(h);
for(;;)
{
// I haven't done my dec yet, guid must still match :
LF_OS_ASSERT( state_get_guid(state_prev) == old_guid );
// check current refcount :
handle_type state_prev_rc = state_get_refcount(state_prev);
LF_OS_ASSERT( state_prev_rc >= 1 );
if ( state_prev_rc == 1 )
{
// I'm taking refcount to 0
// also inc guid, which releases the slot :
handle_type new_state = make_state(old_guid+1,0);
if ( s->m_state($).compare_exchange_weak(state_prev,new_state,mo_acq_rel,mo_relaxed) )
{
// I released the slot
// cmpx provides the acquire barrier for the free :
FreeSlot(s);
return;
}
}
else
{
// this is just a decrement
// but have to do it as a CAS to ensure state_prev_rc doesn't change on us
handle_type new_state = state_prev-1;
LF_OS_ASSERT( new_state == make_state(old_guid, state_prev_rc-1) );
if ( s->m_state($).compare_exchange_weak(state_prev,new_state,mo_release,mo_relaxed) )
{
// I dec'ed a ref
return;
}
}
}
}
"05-08-13 - A Lock Free Weak Reference Table"
12 Comments -
What is the purpose of the loop, i.e. what is the state==old_state case?
If the semantics of compare_exchange_weak is both to check whether the existing value is state, and if it is exchange, otherwise write the existing value to state, then by definition surely if the compare fails, state must != old_state.
May 9, 2013 at 12:05 PM
Well compare_exchange_weak can fail spuriously, so the loop actually is necessary there. But you're right, I should just change it to compare_exchange_strong and then not loop, that's simpler/clearer.
May 9, 2013 at 1:02 PM
Ah, makes sense, thanks
May 9, 2013 at 2:58 PM
Your library seems to be missing the code for IncRef/DecRef.
What is the usage scenario?
I'm a little worried that since the DecRef atomic decrement is relaxed, that its effects could move above the threads usage of the object such that another thread sees the first thread's decrement, decrements the count to zero, and frees the object before the first thread is done using it.
May 9, 2013 at 5:28 PM
"Your library seems to be missing the code for IncRef/DecRef."
Uh, yup. Fixed.
"I'm a little worried that since the DecRef atomic decrement is relaxed, that its effects could move above the threads usage of the object such that another thread sees the first thread's decrement, decrements the count to zero, and frees the object before the first thread is done using it."
Yeah, you have a point. I'll have to think about that a little more.
May 9, 2013 at 7:17 PM
Yep, of course you're right - DecRef needs to be at least mo_release. That keeps it from moving up before ops on the pointer it protects. I think that's it (?)
That need is hidden if the object is internally protected by a mutex, or if the shared reference is protected by a mutex.
I really need to get CDSChecker running cuz Relacy is no good at modeling relaxed atomics.
Some threads I found on minimal memory ordering required for refcounts :
https://groups.google.com/forum/?fromgroups=#!topic/comp.programming.threads/Wne5asVbNfA
https://groups.google.com/forum/?fromgroups=#!msg/comp.programming.threads/Sev_8xKh3RU/wEkEqnOhs_oJ
May 10, 2013 at 10:18 AM
I would think you'd need a release on the normal decrement path and load acquire (or consume??) of the count on the path that you actually do the deletion...
You have to force a synchronization between the computation that uses the object and the computation that frees it.
I expect that the release alone would keep compilers in practice from breaking your code, but it isn't technically correct.
May 10, 2013 at 11:18 AM
Herb Sutter briefly discussed the memory ordering requirements for refcounts in his "atomic<> Weapons" talk:
Part 1:
http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-
Part 2:
http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-2-of-2
It's a long talk. The bit about ref-counts is near the end of part 2, (timecode about 1h 20)
He says: relaxed increment. Acquire+Release decrement. Having said that, he wasn't talking about weak pointers; I don't know if that adds any extra twists.
May 10, 2013 at 12:25 PM
Sorry, first URL got truncated. Should be:
http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2
May 10, 2013 at 12:27 PM
An acquire fence would also work on free path of DecREf.
May 10, 2013 at 1:51 PM
Right. The actual ref decrement here is release, but then before an object is freed there's also the acq_rel to change the guid which is in the same atomic word. The guid change provides the acquire for the freeing of the object and slot.
(I suppose it's not obvious in the posted code, but state_get_guid and state_get_refcount are just pulling bit fields out of a single word.)
May 10, 2013 at 2:50 PM
Addendum to post : alternative DecRef.
May 10, 2013 at 3:40 PM