Lockless/non-blocking ref.counting?
Alexander Terekhov
It seems to me that for ref.counting of immutable
objects it is sufficient to have atomic increments
and decrements only (CAS/LLSC). The memory coherency
protocol (which is provided by a general mutex
protecting the ref.count) is not needed on top of
whatever correct/appropriate mechanism which threads
would have to use to communicate shared immutable
objects (their refs/ptrs) after object creation
completes in some thread (creator thread).
Is this correct?
I also believe that, for ref.counting of mutable
objects (threads could change them synchronizing
themselves using either an object's lock
(readwrite/mutex) or even some other higher
level locking scheme), it is sufficient to have
much less expensive memory coherency protocol than
the one provided by general mutex (protects the
ref.count) or by some other lock (readwrite/mutex)
associated with an object+count.
I think that if all threads "unref" objects AFTER
creation/readwrite&unlock (this is quite reasonable,
I guess ;) then in addition to atomic ++/--, the
only MEMORY BARRIER needed for correct ref.counting
is the READ MEMORY BARRIER when ref.count reaches
the ZERO (to ensure proper mem.visibility for
object destruction). That would also allow threads
to "unref" while some other thread is still busy
updating the object (or while some other threads
still busy reading the object) - this would allow
higher concurrency/less contention with respect to
object locking without having an extra lock for
ref.count.
Is this correct?
Well, I am also puzzled because if the above is
true (and so far, I really think so) then why
does PTHREADS not have a non-blocking/faster/less
expensive interface for ref.counting than general
mutexes/rw-locks and even spinlocks (for an appl
that is able to ensure correct usage of spinlock)?
regards,
alexander.
Kaz Kylheku
>
>It seems to me that for ref.counting of immutable
>objects it is sufficient to have atomic increments
>and decrements only (CAS/LLSC). The memory coherency
>protocol (which is provided by a general mutex
>protecting the ref.count) is not needed on top of
>whatever correct/appropriate mechanism which threads
>would have to use to communicate shared immutable
>objects (their refs/ptrs) after object creation
>completes in some thread (creator thread).
>
>Is this correct?
I think so.
>I also believe that, for ref.counting of mutable
>objects (threads could change them synchronizing
>themselves using either an object's lock
>(readwrite/mutex) or even some other higher
>level locking scheme), it is sufficient to have
>much less expensive memory coherency protocol than
>the one provided by general mutex (protects the
>ref.count) or by some other lock (readwrite/mutex)
>associated with an object+count.
I think you are right. The reference count is, conceptually, a separate
object from the object it is attached to. All we care about is that
it is correctly manipulated, and that we can reliably detect when it
reaches zero. There aren't really any data dependency issues between
the counter and the object it is attached to.
The only time we take an action which depends on the value of the counter
is when we delete the object. So we have to be sure that if we observe a
zero value of the counter, there rest of the object is stable. I think
that can already be assumed due to the manner in which we obtained the
pointer to the object, assuming proper synchronization was used when
the pointer was handed from one thread to another.
Can you think of any scenarios in which this assumption breaks?
>I think that if all threads "unref" objects AFTER
>creation/readwrite&unlock (this is quite reasonable,
>I guess ;) then in addition to atomic ++/--, the
>only MEMORY BARRIER needed for correct ref.counting
>is the READ MEMORY BARRIER when ref.count reaches
>the ZERO (to ensure proper mem.visibility for
>object destruction).
I don't think you even need that. You already have a pointer to the
object which you safely obtained at some point. The integrity of the
data structures used by your allocator routines is in the hands of those
routines, which use their own memory barriers as necessary.
If you have the correct pointer, you should be able to trust your
allocator to free the object without having to ensure memory visibility
yourself.
If you need to access the object to clean it up before deleting it,
you can lock it, to make sure you have the latest value. Do not assume
that just because the refcount is zero, you don't have to lock.
Then you should be okay.
Alexander Terekhov
Kaz Kylheku wrote:
[...]
> >I also believe that, for ref.counting of mutable
> >objects (threads could change them synchronizing
> >themselves using either an object's lock
> >(readwrite/mutex) or even some other higher
> >level locking scheme), it is sufficient to have
> >much less expensive memory coherency protocol than
> >the one provided by general mutex (protects the
> >ref.count) or by some other lock (readwrite/mutex)
> >associated with an object+count.
>
> I think you are right. The reference count is, conceptually, a separate
> object from the object it is attached to. All we care about is that
> it is correctly manipulated, and that we can reliably detect when it
> reaches zero. There aren't really any data dependency issues between
> the counter and the object it is attached to.
>
> The only time we take an action which depends on the value of the counter
> is when we delete the object. So we have to be sure that if we observe a
> zero value of the counter, there rest of the object is stable. I think
> that can already be assumed due to the manner in which we obtained the
> pointer to the object, assuming proper synchronization was used when
> the pointer was handed from one thread to another.
>
> Can you think of any scenarios in which this assumption breaks?
My concern was that since a mutable object could
be changed in a thread other than a thread that
happened to be the last one to "unref", it is not
guaranteed that this thread would see an object's
up-to-date content that might be needed for object
cleanup. Seems to me that below, you suggest locking
in order to ensure proper visibility for cleanup;
I just wanted to avoid this. (with "READ MEMORY
BARRIER when ref.count reaches the ZERO" provided
by mutable-object-"unref" interface).
> >I think that if all threads "unref" objects AFTER
> >creation/readwrite&unlock (this is quite reasonable,
> >I guess ;) then in addition to atomic ++/--, the
> >only MEMORY BARRIER needed for correct ref.counting
> >is the READ MEMORY BARRIER when ref.count reaches
> >the ZERO (to ensure proper mem.visibility for
> >object destruction).
>
> I don't think you even need that. You already have a pointer to the
> object which you safely obtained at some point. The integrity of the
> data structures used by your allocator routines is in the hands of those
> routines, which use their own memory barriers as necessary.
>
> If you have the correct pointer, you should be able to trust your
> allocator to free the object without having to ensure memory visibility
> yourself.
>
> If you need to access the object to clean it up before deleting it,
> you can lock it, to make sure you have the latest value. Do not assume
> that just because the refcount is zero, you don't have to lock.
Yeah, that would solve the visibility problem for
cleanup of mutable objects. However, with a lock
protecting more than one object we could still
block -- which would cause an unnecessary decrease
in concurrency, increased contention. Also, the
memory access reordering constrain (MBAR) injected
by unlock seems to be absolutely redundant to me
in this situation (and we would need unlock even
in the situation with a dedicated lock per object,
to ensure that lock destruction would not fail
with e.g. EBUSY, AFAIK).
regards,
alexander.
Mike Mowbray
> > My concern was that since a mutable object could
> > be changed in a thread other than a thread that
> > happened to be the last one to "unref", it is not
> > guaranteed that this thread would see an object's
> > up-to-date content that might be needed for object
> > cleanup. Seems to me that below, you suggest locking
> > in order to ensure proper visibility for cleanup;
> > I just wanted to avoid this. (with "READ MEMORY
> > BARRIER when ref.count reaches the ZERO" provided
> > by mutable-object-"unref" interface).
For the case of a cas instruction on sparcv8+ and sparcv9,
I was under the impression (from reading the Sparc V9
Architecture Manual) that the atomicity of the cas
instructions is such that memory visibility issues are
already handled inside the semantics of the cas instruction
itself.
Am I deluded?
- MikeM.