Re: Atomically Thread-Safe Mostly Lock-Free Reference Counted Pointer For C...
Chris Thomasson
news:LMWdnXol59_2pHPb...@comcast.com...
Here is version 0.001 (pre-alpha/rough-draft) example implementation of
strongly thread-safe atomic reference counted pointers in C and PThreads:
http://appcore.home.comcast.net/refcount-c.html
I am working on some example applications and will post those in a day or
two. Anyway, how does the code look to you? Try not to flame me too hard!
:^)
blytkerchan
> "Chris Thomasson" <cris...@comcast.net> wrote in message
It looks interesting enough, but there are some details I don't quite
get:
* why a table of 64 mutexes? Why not just carry a mutex around with
your reference counted pointer? Do you expect more than 32 instances
of the reference counter to exist in your typical use-case and do you
expect a real optimization from using a table of mutexes because of
that?
* Why select the mutex to use from a piece of pointer arithmetic? Why
not use something more in the way of a unique ID for the pointer
instance? (something a fetchAndIncrement function on creation of the
instance would return) That would allow for something closer to
defined behavior and would probably distribute the burden on your
locks better (because you won't have any alignment issues to work
with)
* I notice that you're basically protecting your counter with a lock.
Don't you think that interlocked instructions might be cheaper than
mutexes when you're simply playing with integers? I'd have a tendency
to use an atomicIncrement and a fetchAndDecrement for this kinda thing
- the former being an interlocked add and the second a CAS. I know
that interlocked instructions can be expensive, but I'd assume that a
mutex implementation would need them at some point anyway..
* I also don't quite see why you use a separate set of locks for
swapping: what happens if I read the "state" pointer from an refcount
instance while a second thread is swapping that same instance (i.e.
refs > 1). Do you expect that to be safe and, if so, how so? As you
don't systematically protect your state pointer, I don't see why using
a non-R/W lock that you only optionally use on the entire state of
your refcounter will help anything. I'd personally use a R/W pointer
that I'd lock in a shared state for any access, and in an exclusive
state for swapping - but if that's not necessary, please tell me
why :). You wouldn't be able to carry around the R/W lock with the
refcount instance, of course.
On the style-side:
* I presume that refcount_sys_destroy is meant to be static? (that
would avoid accidental calls from outside the acquire/release
mechanism)
* I'd have a tendency to allow access to "state" only through a real
accessor, so no-one is tempted to change the pointer within the
refcount structure (i.e. make the structure opaque): it saves binary
compatibility and head-aches in the long run - especially if your
intended audience doesn't necessarily know what they're doing.
that could be overly paranoid on my part, though..
* I'd also have a tendency to add some more assertions - especially
where the pre-conditions of your functions are concerned - but again,
that's in case you have an intended audience that doesn't necessarily
know what they're doing
Just my C$0.02
rlc
Casper H.S. Dik
>* I notice that you're basically protecting your counter with a lock.
>Don't you think that interlocked instructions might be cheaper than
>mutexes when you're simply playing with integers? I'd have a tendency
>to use an atomicIncrement and a fetchAndDecrement for this kinda thing
>- the former being an interlocked add and the second a CAS. I know
>that interlocked instructions can be expensive, but I'd assume that a
>mutex implementation would need them at some point anyway..
I think the point here is to implement the code in C + Pthreads; not
using assembler or OS specific primitives.
>* I also don't quite see why you use a separate set of locks for
>swapping: what happens if I read the "state" pointer from an refcount
>instance while a second thread is swapping that same instance (i.e.
>refs > 1). Do you expect that to be safe and, if so, how so? As you
>don't systematically protect your state pointer, I don't see why using
>a non-R/W lock that you only optionally use on the entire state of
>your refcounter will help anything. I'd personally use a R/W pointer
>that I'd lock in a shared state for any access, and in an exclusive
>state for swapping - but if that's not necessary, please tell me
>why :). You wouldn't be able to carry around the R/W lock with the
>refcount instance, of course.
I don't see how an "atomic read" would work anyway it's a rather pointless
operation. (You've read a value and then all you know is that that value
was there somewhere in the past)
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
Chris Thomasson
news:1190175600....@22g2000hsm.googlegroups.com...
> On Sep 18, 6:36 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "Chris Thomasson" <cris...@comcast.net> wrote in message
>>
>> news:LMWdnXol59_2pHPb...@comcast.com...
>>
>> Here is version 0.001 (pre-alpha/rough-draft) example implementation of
>> strongly thread-safe atomic reference counted pointers in C and PThreads:
>>
>> http://appcore.home.comcast.net/refcount-c.html
>>
>> I am working on some example applications and will post those in a day or
>> two. Anyway, how does the code look to you? Try not to flame me too hard!
>
> It looks interesting enough, but there are some details I don't quite
> get:
> * why a table of 64 mutexes? Why not just carry a mutex around with
> your reference counted pointer?
You can keep a mutex per-refcount if your only supporting
weak/basic-thread-safety. For strong-safety you need to be able to extend a
mutex's lifetime beyond that of any refcount object that flow's through its
critical-section. Global locking table is any easy soultion to the problem
that does not add any per-object overhead (e.g., does not use per-object
meta-data).
> Do you expect more than 32 instances
> of the reference counter to exist in your typical use-case and do you
> expect a real optimization from using a table of mutexes because of
> that?
Yes.
> * Why select the mutex to use from a piece of pointer arithmetic? Why
> not use something more in the way of a unique ID for the pointer
> instance?
I want to keep refcount object state to a minimum... Alls it needs is a
counter, dtor-func-ptr and state fields. No need for per-refcount mutex/ID.
> (something a fetchAndIncrement function on creation of the
> instance would return) That would allow for something closer to
> defined behavior and would probably distribute the burden on your
> locks better (because you won't have any alignment issues to work
> with)
Can't use interlocked rmw instructions; this is C + PThread example. Anyway
you don't need to use this instruction wrt generating unesseary per-refcount
ID's.
> * I notice that you're basically protecting your counter with a lock.
Your half right. I also lock shared pointer location's for handling strongly
thread-safe swap/copy operations from a different locking table than the
counter uses...
[...]
> * I also don't quite see why you use a separate set of locks for
> swapping:
A swap/copy to a shared refcount* location needs to be syncronized on that
specific location. There is a special case for copy because it needs to load
from a shared refcount* location and increment the resulting refcount*'s
counter, if any, in a single atomic operation. So, you need to lock two
mutexs. One for the shared location, and one for any resulting refcount*.
Since a thread cannot lock more than one mutex from the same locking table
at any one time:
http://groups.google.com/group/microsoft.public.win32.programmer.kernel/msg/f7297761027a9459
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e0c011baf08844c4
> what happens if I read the "state" pointer from an refcount
> instance while a second thread is swapping that same instance (i.e.
> refs > 1).
The state pointer is set when a refcount object is created; after that, its
remains immutable.
> Do you expect that to be safe and, if so, how so? As you
> don't systematically protect your state pointer, I don't see why using
> a non-R/W lock that you only optionally use on the entire state of
> your refcounter will help anything.
There are no writes to the state pointer throughout the lifetime of a
refcount object.
> On the style-side:
> * I presume that refcount_sys_destroy is meant to be static? (that
> would avoid accidental calls from outside the acquire/release
> mechanism)
Yes.
[...]
Chris Thomasson
[...]
>>* I also don't quite see why you use a separate set of locks for
>>swapping: what happens if I read the "state" pointer from an refcount
>>instance while a second thread is swapping that same instance (i.e.
>>refs > 1). Do you expect that to be safe and, if so, how so? As you
>>don't systematically protect your state pointer, I don't see why using
>>a non-R/W lock that you only optionally use on the entire state of
>>your refcounter will help anything. I'd personally use a R/W pointer
>>that I'd lock in a shared state for any access,
> and in an exclusive
>>state for swapping - but if that's not necessary, please tell me
>>why :). You wouldn't be able to carry around the R/W lock with the
>>refcount instance, of course.
You could use global r/w locking table to sync shared refcount* locations
for sure. In fact, I almost put them in there... You would use read access
to protect copying and write access to protect swapping. Sure. I think I
will change the code and post another version...
Markus Elfring
struct refcount_s {
int refs;
refcount_fp_dtor fp_dtor;
void *state;
};
Would you like to use an unsigned integer like size_t?
How much does signedness matter for the count in your source code?
Regards,
Markus
Dmitriy Vyukov
> "Chris Thomasson" <cris...@comcast.net> wrote in message
> Here is version 0.001 (pre-alpha/rough-draft) example implementation of
> strongly thread-safe atomic reference counted pointers in C and PThreads:
>
> http://appcore.home.comcast.net/refcount-c.html
>
> I am working on some example applications and will post those in a day or
> two. Anyway, how does the code look to you? Try not to flame me too hard!
void refcount_sys_destroy(
refcount* const _this
) {
assert(_this->refs < 1);
if (_this->fp_dtor) {
_this->fp_dtor(_this->state);
}
free(_this);
// access in DBG_PRINTF to freed object is not very good thing
imho...
// maybe move this DBG_PRINTF to function beginning
DBG_PRINTF(("(%p/%p/%i)-refcount_sys_destroy(...)\n",
(void*)_this, _this->state, _this->refs));
}
Dmitriy V'jukov
Dmitriy Vyukov
> Here is version 0.001 (pre-alpha/rough-draft) example implementation of
> strongly thread-safe atomic reference counted pointers in C and PThreads:
>
> http://appcore.home.comcast.net/refcount-c.html
>
> I am working on some example applications and will post those in a day or
> two. Anyway, how does the code look to you? Try not to flame me too hard!
Why you need locktbl_lock/locktbl_unlock in refcount_create()?
I think it's like object constructor in C++. Before completion of
refcount_create() object is not constructed and must not be accessible
for other threads. So locktbl_lock/locktbl_unlock is useless here.
Dmitriy V'jukov
Dmitriy Vyukov
> Here is version 0.001 (pre-alpha/rough-draft) example implementation of
> strongly thread-safe atomic reference counted pointers in C and PThreads:
>
> http://appcore.home.comcast.net/refcount-c.html
>
> I am working on some example applications and will post those in a day or
> two. Anyway, how does the code look to you? Try not to flame me too hard!
Run this modified version of refcount_copy() with your test:
int refcount_copy(
refcount** const _psrc, /* ptr-to-shared */
refcount** const _pdest /* ptr-to-local */
) {
int status = locktbl_swaplock(_psrc);
if (! status) {
int inc_status;
refcount* const src = *_psrc; /* shared-load */
*_pdest = src; /* local-store */
////////////////////////////////////////////
// Consider this code is executed by another thread
// I.e. another thread is trying to replace same
// shared pointer to NULL
{
refcount* local = 0;
refcount_swap(_psrc, &local);
refcount_release(local);
}
////////////////////////////////////////////
// Here I get memory access violation
// src points to freed memory
inc_status = refcount_acquire(src);
status = locktbl_swapunlock(_psrc);
if (! status) {
DBG_PRINTF(("(%p/%p/%i)-refcount_copy(...)\n",
(void*)src, (src) ? src->state : 0, (src) ? src->refs : 0));
return inc_status;
}
}
return status;
}
What I miss?
Dmitriy V'jukov
Dmitriy Vyukov
False alarm. refcount_swap() can't be executed here because it's
protected by the same mutex as refcount_copy().
And as I understand I can't execute refcount_release() on shared
pointer, only on local pointer. So this is prohibited:
int refcount_copy(
refcount** const _psrc, /* ptr-to-shared */
refcount** const _pdest /* ptr-to-local */
) {
int status = locktbl_swaplock(_psrc);
if (! status) {
int inc_status;
refcount* const src = *_psrc; /* shared-load */
*_pdest = src; /* local-store */
////////////////////////////////////////////
// Consider this code is executed by another thread
{
refcount_release(*_psrc);
}
////////////////////////////////////////////
// Here I get memory access violation
// src points to freed memory
inc_status = refcount_acquire(src);
status = locktbl_swapunlock(_psrc);
if (! status) {
DBG_PRINTF(("(%p/%p/%i)-refcount_copy(...)\n",
(void*)src, (src) ? src->state : 0, (src) ? src->refs : 0));
return inc_status;
}
}
return status;
}
I must execute refcount_swap() on shared pointer first, and only then
refcount_release() on local pointer. Maybe it's better to distinguish
shared and local pointers more explicitly. For example make them
different types...
Dmitriy V'jukov
Chris Thomasson
news:1190207486.7...@q5g2000prf.googlegroups.com...
> On Sep 19, 2:36 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "Chris Thomasson" <cris...@comcast.net> wrote in message
>
>> Here is version 0.001 (pre-alpha/rough-draft) example implementation of
>> strongly thread-safe atomic reference counted pointers in C and PThreads:
>>
>> http://appcore.home.comcast.net/refcount-c.html
>>
>> I am working on some example applications and will post those in a day or
>> two. Anyway, how does the code look to you? Try not to flame me too hard!
>
>
> void refcount_sys_destroy(
> refcount* const _this
> ) {
> assert(_this->refs < 1);
> if (_this->fp_dtor) {
> _this->fp_dtor(_this->state);
> }
> free(_this);
>
> // access in DBG_PRINTF to freed object is not very good thing
> imho...
> // maybe move this DBG_PRINTF to function beginning
YIKES! Yes your correct of course!
> DBG_PRINTF(("(%p/%p/%i)-refcount_sys_destroy(...)\n",
> (void*)_this, _this->state, _this->refs));
> }
I am going to post another version in about 30 minutes with this fixed and
r/w locks for swaps/copy instead.
Thank you for looking!
Chris Thomasson
> On Sep 19, 5:21 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>> On Sep 19, 2:36 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>> > Here is version 0.001 (pre-alpha/rough-draft) example implementation of
>> > strongly thread-safe atomic reference counted pointers in C and
>> > PThreads:
>> >http://appcore.home.comcast.net/refcount-c.html
>>
>> > I am working on some example applications and will post those in a day
>> > or
>> > two. Anyway, how does the code look to you? Try not to flame me too
>> > hard!
>>
>> Run this modified version of refcount_copy() with your test:
>> int refcount_copy(
>> refcount** const _psrc, /* ptr-to-shared */
>> refcount** const _pdest /* ptr-to-local */
>> ) {
>> }
>> What I miss?
>
> False alarm. refcount_swap() can't be executed here because it's
> protected by the same mutex as refcount_copy().
right.
> And as I understand I can't execute refcount_release() on shared
> pointer, only on local pointer.
right.
> So this is prohibited:
>
> int refcount_copy(
> refcount** const _psrc, /* ptr-to-shared */
> refcount** const _pdest /* ptr-to-local */
> ) {
[...]
> return status;
> }
>
> I must execute refcount_swap() on shared pointer first, and only then
> refcount_release() on local pointer.
exactly.
> Maybe it's better to distinguish
> shared and local pointers more explicitly. For example make them
> different types...
Good idea; will do... Something simple like:
typedef refcount refcount_local;
typedef refcount refcount_shared;
So using the new type aliases:
static refcount_shared* g_foo = 0;
int consume() {
refcount_local* l_foo = 0;
int status = refcount_swap(&g_foo, &l_foo);
if (! status && l_foo) {
foo* const _this = refcount_get_state(l_foo);
_this->do_work();
refcount_release(l_foo);
}
return status;
}
int produce() {
refcount_local* l_foo;
int status = foo_create(&l_foo, ...);
if (! status) {
status = refcount_swap(&g_foo, &l_foo);
if (! status && l_foo) {
_this->do_work();
refcount_release(l_foo);
}
}
return status;
}
Chris Thomasson
> "Chris Thomasson" <cri...@comcast.net> wrote in message
> news:LMWdnXol59_2pHPb...@comcast.com...
>
> Here is version 0.001 (pre-alpha/rough-draft) example implementation of
> strongly thread-safe atomic reference counted pointers in C and PThreads:
>
> http://appcore.home.comcast.net/refcount-c.html
>
> I am working on some example applications and will post those in a day or
> two. Anyway, how does the code look to you? Try not to flame me too hard!
>
> :^)
Here is a newer version:
http://appcore.home.comcast.net/refcount-c-v0-002.html
That fixes this issue:
http://groups.google.com/group/comp.programming.threads/msg/ed9b815585433aef
And incorporates the following:
http://groups.google.com/group/comp.programming.threads/msg/de894745958c7b81
creates two new types 'refcount_local' and 'refcount_shared' to help
distinguish between shared and local accesses. Okay, can anybody notice any
possible problems in ver-0.002?
Chris Thomasson
news:5lcl71F...@mid.individual.net...
something like:
typedef unsigned long int refcount_refs;
struct refcount_s {
refcount_refs refs;
refcount_fp_dtor fp_dtor;
void *state;
};
perhaps...
Dmitriy Vyukov
> > Maybe it's better to distinguish
> > shared and local pointers more explicitly. For example make them
> > different types...
>
> Good idea; will do... Something simple like:
>
> typedef refcount refcount_local;
> typedef refcount refcount_shared;
Ok. All things fall into place.
And this makes more clear why you make 2 tables of mutexes. One table
protect refcount_local, and second - refcount_shared objects.
Dmitriy V'jukov
Dmitriy Vyukov
> Here is a newer version:
>
> http://appcore.home.comcast.net/refcount-c-v0-002.html
>
> That fixes this issue:
>
> http://groups.google.com/group/comp.programming.threads/msg/ed9b81558...
>
> And incorporates the following:
>
> http://groups.google.com/group/comp.programming.threads/msg/de8947459...
You forgot:
http://groups.google.com/group/comp.programming.threads/msg/9902d33dd9fc0869
:)
> creates two new types 'refcount_local' and 'refcount_shared' to help
> distinguish between shared and local accesses. Okay, can anybody notice any
> possible problems in ver-0.002?
Hmmm.... I think that because refcount_local is subject only for basic
thread safety you can use following optimization:
int refcount_release(
refcount_local* const _this
) {
int status = 0;
if (_this) {
///////////////////////////////////////
// here:
if (1 == _this->refs) {
refcount_sys_destroy(_this);
return 0;
}
///////////////////////////////////////
status = locktbl_lock(_this);
if (! status) {
int refs = --_this->refs;
status = locktbl_unlock(_this);
if (! status) {
DBG_PRINTF(("(%p/%p/%i)-refcount_release(...)\n",
(void*)_this, _this->state, refs));
if (refs < 1) {
refcount_sys_destroy(_this);
}
return 0;
}
}
}
return status;
}
Along with refcount_create() optimization this makes creation and
destruction of refcount_local local object a "no-op" wrt heavy
operations:
void f()
{
// no mutex lock/unlock here
refcount_local* l = 0;
refcount_create(&l);
refcount_release(l);
}
Dmitriy V'jukov
Chris Thomasson
> Hmmm.... I think that because refcount_local is subject only for basic
> thread safety you can use following optimization:
>
> int refcount_release(
> refcount_local* const _this
> ) {
> int status = 0;
> if (_this) {
>
> ///////////////////////////////////////
> // here:
> if (1 == _this->refs) {
> refcount_sys_destroy(_this);
> return 0;
> }
> ///////////////////////////////////////
> return status;
> }
I believe that this is a valid optimization. Version 0.003 on the way!
;^)
> Along with refcount_create() optimization this makes creation and
> destruction of refcount_local local object a "no-op" wrt heavy
> operations:
Thank you Dmitriy.
Chris Thomasson
> "Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
> news:1190216171....@v29g2000prd.googlegroups.com...
>> Hmmm.... I think that because refcount_local is subject only for basic
>> thread safety you can use following optimization:
>>
>> int refcount_release(
>> refcount_local* const _this
>> ) {
>> int status = 0;
>> if (_this) {
>>
>> ///////////////////////////////////////
>> // here:
>> if (1 == _this->refs) {
>> refcount_sys_destroy(_this);
>> return 0;
>> }
>> ///////////////////////////////////////
> [...]
>> return status;
>> }
>
> I believe that this is a valid optimization.
On second thought, this might violate POSIX rules. Think of two threads, one
(thread A) of which holds a local pointer and the other (thread B) one about
two swap NULL with a live shared pointer. Reference count 2:
Thread B: swap shared_ptr with local_ptr
Thread B: release local_ptr /* 2 - 1 */
Thread A: release local_ptr /* race-condition */
If thread A observes a reference count of 1 without using the per-counter
lock then that might of occurred at the same time thread B decremented. This
would be Thread A reading from a shared location during a write... Strictly
speaking, this violates POSIX no?
Humm...
Dmitriy Vyukov
> If thread A observes a reference count of 1 without using the
> per-counter lock then that might of occurred at the same time thread B
> decremented. This would be Thread A reading from a shared location
> during a write... Strictly speaking, this violates POSIX no?
Yes, this violates POSIX.
This will work only on systems with atomic stores and loads of machine
words. POSIX doesn't guarantee this...
Dmitriy V'jukov
blytkerchan
> "blytkerchan" <blytkerc...@gmail.com> wrote in message
> news:1190175600....@22g2000hsm.googlegroups.com...
> > On Sep 18, 6:36 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
> >> "Chris Thomasson" <cris...@comcast.net> wrote in message
> >>news:LMWdnXol59_2pHPb...@comcast.com...
>
> >> Here is version 0.001 (pre-alpha/rough-draft) example implementation of
> >> strongly thread-safe atomic reference counted pointers in C and PThreads:
>
> >>http://appcore.home.comcast.net/refcount-c.html
>
> >> I am working on some example applications and will post those in a day or
> >> two. Anyway, how does the code look to you? Try not to flame me too hard!
>
> > It looks interesting enough, but there are some details I don't quite
> > get:
> > * why a table of 64 mutexes? Why not just carry a mutex around with
> > your reference counted pointer?
>
> You can keep a mutex per-refcount if your only supporting
> weak/basic-thread-safety. For strong-safety you need to be able to extend a
> mutex's lifetime beyond that of any refcount object that flow's through its
> critical-section. Global locking table is any easy soultion to the problem
> that does not add any per-object overhead (e.g., does not use per-object
> meta-data).
True, but half your locks are only used to lock the counter itself, so
they could be carried around with the refcount instance. The other
half can protect the state of the refcount instance itself and cannot
be carried around - but you only use those for the swap and don't seem
to do any locking with them outside that.
[snip]
>
> > * Why select the mutex to use from a piece of pointer arithmetic? Why
> > not use something more in the way of a unique ID for the pointer
> > instance?
>
> I want to keep refcount object state to a minimum... Alls it needs is a
> counter, dtor-func-ptr and state fields. No need for per-refcount mutex/ID.
Yes, but you're counting on the fact that you *can* do pointer
arithmetic, basically saying that a pointer is an integer. And even if
you can do pointer arithmetic, if the instance of your refcount is
aligned a certain way more often that not (say on a 64-byte boundary)
you'll find yourself using a single lock most of the time (and the
others only sporadically), which takes away most of your optimization
(which you would get back for the price of an integer per refcount).
> > (something a fetchAndIncrement function on creation of the
> > instance would return) That would allow for something closer to
> > defined behavior and would probably distribute the burden on your
> > locks better (because you won't have any alignment issues to work
> > with)
>
> Can't use interlocked rmw instructions; this is C + PThread example. Anyway
> you don't need to use this instruction wrt generating unesseary per-refcount
> ID's.
OK for the C + PThread restriction. As for the need to have the ID,
see above why I think you might want one :)
>
> > * I notice that you're basically protecting your counter with a lock.
>
> Your half right. I also lock shared pointer location's for handling strongly
> thread-safe swap/copy operations from a different locking table than the
> counter uses...
I noticed, but (as stated below) I parsed the code wrong...
>
> [...]
>
> > * I also don't quite see why you use a separate set of locks for
> > swapping:
>
> A swap/copy to a shared refcount* location needs to be syncronized on that
> specific location. There is a special case for copy because it needs to load
> from a shared refcount* location and increment the resulting refcount*'s
> counter, if any, in a single atomic operation. So, you need to lock two
> mutexs. One for the shared location, and one for any resulting refcount*.
> Since a thread cannot lock more than one mutex from the same locking table
> at any one time:
>
> http://groups.google.com/group/microsoft.public.win32.programmer.kern...
>
> http://groups.google.com/group/comp.programming.threads/browse_frm/th...
>
> > what happens if I read the "state" pointer from an refcount
> > instance while a second thread is swapping that same instance (i.e.
> > refs > 1).
>
> The state pointer is set when a refcount object is created; after that, its
> remains immutable.
Ah, yes! That should teach me not to review this kind of code after an
already long night of coding :)
I hadn't noticed the refcount ** (parsed it as a refcount *)
> > Do you expect that to be safe and, if so, how so? As you
> > don't systematically protect your state pointer, I don't see why using
> > a non-R/W lock that you only optionally use on the entire state of
> > your refcounter will help anything.
>
> There are no writes to the state pointer throughout the lifetime of a
> refcount object.
Right - after a second look at the code, I see this..
> > On the style-side:
> > * I presume that refcount_sys_destroy is meant to be static? (that
> > would avoid accidental calls from outside the acquire/release
> > mechanism)
>
> Yes.
>
> [...]
rlc
Walter Roberson
Chris Thomasson <cri...@comcast.net> wrote:
>"Chris Thomasson" <cri...@comcast.net> wrote in message
>news:LMWdnXol59_2pHPb...@comcast.com...
>Here is version 0.001 (pre-alpha/rough-draft) example implementation of
>strongly thread-safe atomic reference counted pointers in C and PThreads:
Please remove comp.lang.c from this discussion. comp.lang.c is
for discussion of what can be done in ANSI/ISO C, not for discussion
of what can be done with ANSI/ISO C together with some system-
specific behaviour.
--
All is vanity. -- Ecclesiastes
Chris Thomasson
I need to use two locking tables because the 'refcount_copy' function has to
lock 2 mutexs in order to increment the reference counter. A thread cannot
lock more than 1 mutex at a time in a lock hashing scheme; otherwise, you
can deadlock.
>> > * Why select the mutex to use from a piece of pointer arithmetic? Why
>> > not use something more in the way of a unique ID for the pointer
>> > instance?
>>
>> I want to keep refcount object state to a minimum... Alls it needs is a
>> counter, dtor-func-ptr and state fields. No need for per-refcount
>> mutex/ID.
>
> Yes, but you're counting on the fact that you *can* do pointer
> arithmetic, basically saying that a pointer is an integer. And even if
> you can do pointer arithmetic, if the instance of your refcount is
> aligned a certain way more often that not (say on a 64-byte boundary)
> you'll find yourself using a single lock most of the time (and the
> others only sporadically), which takes away most of your optimization
> (which you would get back for the price of an integer per refcount).
Good point. Possible answer: Deriving an index into the locking table arrays
from a better pointer hashing technique and/or actual per-object meta-data.
>> > (something a fetchAndIncrement function on creation of the
>> > instance would return) That would allow for something closer to
>> > defined behavior and would probably distribute the burden on your
>> > locks better (because you won't have any alignment issues to work
>> > with)
>>
>> Can't use interlocked rmw instructions; this is C + PThread example.
>> Anyway
>> you don't need to use this instruction wrt generating unesseary
>> per-refcount
>> ID's.
>
> OK for the C + PThread restriction. As for the need to have the ID,
> see above why I think you might want one :)
Indeed.
>> > * I notice that you're basically protecting your counter with a lock.
>>
>> Your half right. I also lock shared pointer location's for handling
>> strongly
>> thread-safe swap/copy operations from a different locking table than the
>> counter uses...
>
> I noticed, but (as stated below) I parsed the code wrong...
;^)
>> [...]
>>
>> > * I also don't quite see why you use a separate set of locks for
>> > swapping:
>>
>> A swap/copy to a shared refcount* location needs to be syncronized on
>> that
>> specific location.
[...]
>> > what happens if I read the "state" pointer from an refcount
>> > instance while a second thread is swapping that same instance (i.e.
>> > refs > 1).
>>
>> The state pointer is set when a refcount object is created; after that,
>> its
>> remains immutable.
>
> Ah, yes! That should teach me not to review this kind of code after an
> already long night of coding :)
> I hadn't noticed the refcount ** (parsed it as a refcount *)
Yeah, the state pointer is constant and coherent.
[...]
Flash Gordon
>> blytkerchan <blytk...@gmail.com> writes:
<snip stuff about threads>
Since this is about threads and stuff that is not standard C would you
please restrict followups to comp.programming.threads.
--
Flash Gordon
Chris Thomasson
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1190224613....@v29g2000prd.googlegroups.com...
read this:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/a8792b05f35174d3
on topic?
Dmitriy Vyukov
> [comp.lang.c removes]
>
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
>
> news:1190224613....@v29g2000prd.googlegroups.com...
>
> > Chris Thomasson wrote:
>
> >> If thread A observes a reference count of 1 without using the
> >> per-counter lock then that might of occurred at the same time thread B
> >> decremented. This would be Thread A reading from a shared location
> >> during a write... Strictly speaking, this violates POSIX no?
>
> > Yes, this violates POSIX.
> > This will work only on systems with atomic stores and loads of machine
> > words. POSIX doesn't guarantee this...
>
> read this:
>
>
> on topic?
I So there must be:
int refcount_release(
refcount_local* const _this
) {
int status = 0;
if (_this) {
///////////////////////////////////////
// here:
if (1 == _this->refs) {
membar #StoreLoad|#StoreStore;
refcount_sys_destroy(_this);
return 0;
}
///////////////////////////////////////
status = locktbl_lock(_this);
if (! status) {
int refs = --_this->refs;
status = locktbl_unlock(_this);
if (! status) {
DBG_PRINTF(("(%p/%p/%i)-refcount_release(...)\n",
(void*)_this, _this->state, refs));
if (refs < 1) {
refcount_sys_destroy(_this);
}
return 0;
}
}
}
return status;
}
What you are prevent be this barrier?
#StoreLoad|#StoreStore = Store-acquire. But there are no store before
#StoreLoad|#StoreStore...
Dmitriy V'jukov
Chris Thomasson
> and for copy/swap?
Well, there _is_ a very important caveat with hashed locking that basically
prohibits any one thread from taking two locks from the same table at any
one time:
http://groups.google.com/group/microsoft.public.win32.programmer.kernel/msg/f7297761027a9459
I believe that two tables are necessary here, otherwise, I would have to an
analog of like two-phase locking on the copy operation:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e0c011baf08844c4
This can arrange a locking order in a way that completely prevents any
thread from deadlocking. I was thinking about using it to do a STM that is
compatible with C + PThreads...
> This will increase possibility of contention. But table must be large
> enough anyway to take down contention to minimum.
Indeed.
> But copy operation will have to acquire/release only one mutex instead
> of two. I think that copy operation is relatively frequently issued
> operation.
IMO, the "basic" problem is that copy needs to prevent any other threads
from rendering any mutations on the shared pointer location (e.g., swap
operation) _and_ the reference counter. The shared location and the counter
are essentially "non-related" in the sense that if you are going to
serialize access to both locations, you would need to use multi-word
interlocked operations, stm, two-phase locking, the method I use in the
mostly lock-free refcount, or of course you can rely on the good ol'
"big-global" locking scheme... Pointer's to shared locations _and_ pointer's
to actual refcount object's which are bound to the same mutex table could
potentially map into it in a way that's prone to deadlock... This is due to
a thread violating the "static" locking hierarchy implied with the mutex
table, which ends up being a full-blown race-condition. IMO, the only
"positive" point in that case is probably the fact that the race-condition
will cause deadlock, not silently corrupt some important data...
;^0
Chris Thomasson
we are going to reap the wraith of a thousand concurrent flames, if we keep
pissing those C programmers off!
;^0
Casper H.S. Dik
>Well, there _is_ a very important caveat with hashed locking that basically
>prohibits any one thread from taking two locks from the same table at any
>one time:
>http://groups.google.com/group/microsoft.public.win32.programmer.kernel/msg/f7297761027a9459
If you need to lock N items at the same time (no random sequence of
lock/unlocks while keeping certain items locked), sorting the
locks before locking will prevent any deadlocks.
There's corner case to consider of locking items which hash to the
same lock, but that can be easily fixed by skipping over equal locks.
In pseudo code:
locktable = alloc(N * sizeof (* lock));
for all objects
locktable[i] = lockhash(object);
sort locktable
for (i = 0; i < N; i++)
if (i == 0 || locktable[i] != locktable[i-1])
mutex_lock(lock_table[i]);
And unlocking can be done in the same order skipping the same duplicate
locks.
>http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e0c011baf08844c4
>This can arrange a locking order in a way that completely prevents any
>thread from deadlocking. I was thinking about using it to do a STM that is
>compatible with C + PThreads...
It needs generalizing to allow for multiple objects sharing the
same lock.
Locktables have one important issue, they cause false contention.
With a cacheline size of 64, you can generally fit 8 locks on a cache line
so:
mutex_t locks[8];
mutex_t bottleneck;
scale equally bad.
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
Chris Thomasson
>[...]
> What you are prevent be this barrier?
> #StoreLoad|#StoreStore = Store-acquire. But there are no store before
> #StoreLoad|#StoreStore...
There may be stores to the object that the refcount is protecting...
Chris Thomasson
_________________________________________________
int refcount_release(
refcount_local* const _this
) {
int status = 0;
if (_this) {
status = locktbl_lock(_this);
if (! status) {
refcount_refs refs = --_this->refs;
status = locktbl_unlock(_this);
if (! status) {
DBG_PRINTF(("(%p/%p/%u)-refcount_release(...)\n",
(void*)_this, _this->state, refs));
if (refs < 1) {
refcount_sys_destroy(_this);
}
return 0;
}
}
}
return status;
}
_________________________________________________
The call to DBG_PRINTF should be executed within the critical-section. This
is because another thread could drop the could to zero and destroy the
counter _before_ DBG_PRINTF gets called. Here is the correction:
_________________________________________________
int refcount_release(
refcount_local* const _this
) {
int status = 0;
if (_this) {
status = locktbl_lock(_this);
if (! status) {
refcount_refs refs = --_this->refs;
DBG_PRINTF(("(%p/%p/%u)-refcount_release(...)\n",
(void*)_this, _this->state, refs));
status = locktbl_unlock(_this);
if (! status) {
if (refs < 1) {
refcount_sys_destroy(_this);
}
return 0;
}
}
}
return status;
}
_________________________________________________