Atomically Thread-Safe Mostly Lock-Free Reference Counted Pointer For C...

[Chris Thomasson]

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]

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]

http://appcore.home.comcast.net/refcount-c.html

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" <[email protected]> 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]

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?

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]

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]

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]

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

- http://appcore.home.comcast.net/refcount-c-v0-001.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]

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?

something like:

typedef unsigned long int refcount_refs;

struct refcount_s {
refcount_refs refs;
refcount_fp_dtor fp_dtor;
void *state;
};

perhaps...

 

[Dmitriy Vyukov]

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]

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]

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]

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).

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

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 *)

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]

news:[email protected]...

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.

 

[Chris Thomasson]

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.

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.

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.

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.

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]

Chris Thomasson wrote, On 19/09/07 12:49:
<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.