Atomically Thread-Safe Mostly Lock-Free Reference Counted Pointer For C...
Chris Thomasson
http://appcore.home.comcast.net/vzoom/refcount
Here is the very crude documentation:
http://appcore.home.comcast.net/vzoom/refcount/doc
Forget the C++ smart pointer wrapper. After all, its "basic" use is for
syntactic sugar over the C interface... This can serve as a basic example of
how strong thread-safety can be applied to C. This C-based smart pointer is
more "flexible" than Boost shared_ptr:
http://groups.google.com/group/comp.lang.c++/msg/7570cb55e32145a2
C++ is the sugar that makes this attractive... However, its all based on the
underlying C API which is ultimately based on underlying Intel assembly
language. This example shows how to mix several languages (e.g., C/C++/Intel
ASM) together in a coherent fashion.
Any thoughts?
--
Chris M. Thomasson
http://appcore.home.comcast.net
Chris Thomasson
news:LMWdnXol59_2pHPb...@comcast.com...
> Here is where to find the raw code:
Here is psuedo-code:
http://groups.google.com/group/comp.programming.threads/msg/6c7819fb85d06a65
______________________
rc* copy(rc **sloc, int count) {
1: load ptr from *sloc
if ptr is null goto 2
lock spinlock associated with ptr
re-load ptr from *sloc
compare w/ previous load
if not equal unlock and goto 1
XADD ptr's with count
* if the previous value was less than 1 unlock and goto 1
unlock
2: return ptr
}
bool dec(rc *ptr, int count) {
XADD ptr's refs with negated count;
if new value is greater than 0 then return false;
D1: lock spinlock associated with ptr;
unlock spinlock associated with ptr;
call ptr dtor;
return true;
}
______________________
This can be implemented with POSIX of course. No assembly language required.
The reason I was forces to use asm for the example impl is because neither C
or C++ has ANY concept of threads. Well, and of course because of this:
http://appcore.home.comcast.net/vzdoc/atomic/static-init
Section 2.1 is the relevant part...
Walter Roberson
Chris Thomasson <cri...@comcast.net> wrote:
>Forget the C++ smart pointer wrapper. After all, its "basic" use is for
>syntactic sugar over the C interface... This can serve as a basic example of
>how strong thread-safety can be applied to C.
>C++ is the sugar that makes this attractive... However, its all based on the
>underlying C API which is ultimately based on underlying Intel assembly
>language. This example shows how to mix several languages (e.g., C/C++/Intel
>ASM) together in a coherent fashion.
>Any thoughts?
If it has to resort to assembly, then it is *not* an indication
of "how strong thread-safety can be applied to C" -- it is an
indication at most of how strong thread-safety can be applied
to "C plus some extensions that restrict the portability severely."
You indicated in your follow up that it could be done in POSIX without
any extensions. I question that. POSIX.1, IEEE 1003.1-1990,
specifically refused to get into any kind of mandatory locking
or mutexes or semaphores. All that it has is -advisory- locking,
and -advisory- locking is WEAK thread-safety, not strong thread-safety.
The POSIX.* mandatory locking mechanisms don't come in until
"POSIX threads", which is a relatively heavy-weight package,
in the implementation sense of requiring a lot of changes to the
internals of any kernel not designed for threads from the ground up --
changes that are easy to get wrong. And I've seen a number of
grumblings about POSIX threads being hard to use and slow, leading
to people implementing their own "lightweight thread packages"
that are often somewhat clearer to use than native POSIX threads.
--
Programming is what happens while you're busy making other plans.
Chris Thomasson
news:fcm9at$2jf$1...@canopus.cc.umanitoba.ca...
> In article <LMWdnXol59_2pHPb...@comcast.com>,
> Chris Thomasson <cri...@comcast.net> wrote:
>
>>Forget the C++ smart pointer wrapper. After all, its "basic" use is for
>>syntactic sugar over the C interface... This can serve as a basic example
>>of
>>how strong thread-safety can be applied to C.
>
>>C++ is the sugar that makes this attractive... However, its all based on
>>the
>>underlying C API which is ultimately based on underlying Intel assembly
>>language. This example shows how to mix several languages (e.g.,
>>C/C++/Intel
>>ASM) together in a coherent fashion.
>
>>Any thoughts?
>
> If it has to resort to assembly, then it is *not* an indication
> of "how strong thread-safety can be applied to C" -- it is an
> indication at most of how strong thread-safety can be applied
> to "C plus some extensions that restrict the portability severely."
Fair enough.
> You indicated in your follow up that it could be done in POSIX without
> any extensions. I question that. POSIX.1, IEEE 1003.1-1990,
> specifically refused to get into any kind of mandatory locking
> or mutexes or semaphores. All that it has is -advisory- locking,
> and -advisory- locking is WEAK thread-safety, not strong thread-safety.
You can get strong thread-safety from mutexs. You basically have to use two
global array's of mutexs and hash the address of the reference count into an
index. If you use a mutex per-object your assertion that mutexs provide weak
thread-safety only basically holds true. You can get into a situation where
you need to destroy the object and unlock its mutex in a single atomic
operation. Here is a rough-draft pseudo-code sketch of how you can implement
my refcount algorithm using 100% POSIX and some C:
-------------------------------
/* Global Lock Table
_______________________________________________*/
#define LOCKTBL_HASHPTR_DEPTH() 8
#define LOCKTBL_DEPTH() (LOCKTBL_HASHPTR_DEPTH() + 1)
#define LOCKTBL_INIT() PTHREAD_MUTEX_INITIALIZER
#define LOCKTBL_HASHPTR(mp_ptr) \
(((mp_ptr)ptrdiff_t) % LOCKTBL_HASHPTR_DEPTH())
static pthread_mutex_t g_locktbl[2][LOCKTBL_DEPTH] = {
/* you can use the following pre-processor technique to initalize the
array
<url- http://groups.google.com/group/comp.lang.c/msg/71674afb7c772df8>
So, using that technique, the code looks like this:
*/
{ PLACE(LOCKTBL_INIT, LOCKTBL_DEPTH()) },
{ PLACE(LOCKTBL_INIT, LOCKTBL_DEPTH()) }
};
/* here is another method to setup the locking tables
<url- http://groups.google.com/group/comp.lang.c++/msg/b95dbe2de9ff6e1b>
*/
#define locktbl_lock(mp_ptr) \
pthread_mutex_lock(&g_locktbl[0][LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_unlock(mp_ptr) \
pthread_mutex_unlock(&g_locktbl[0][LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_swaplock(mp_ptr) \
pthread_mutex_lock(&g_locktbl[1][LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_swapunlock(mp_ptr) \
pthread_mutex_unlock(&g_locktbl[1][LOCKTBL_HASHPTR(mp_ptr)])
/* Atomic Reference Counting
_______________________________________________*/
typedef struct refcount_s refcount;
typedef void (*refcount_fp_dtor) (void*);
struct refcount_s {
int refs;
refcount_fp_dtor fp_dtor;
void *state;
};
int refcount_init(
refcount** const _pthis,
refcount_fp_dtor fp_dtor,
void* state
) {
int status = ENOMEM;
refcount* const _this = malloc(sizeof(*_this));
if (_this) {
status = locktbl_lock(_this);
if (! status) {
_this->refs = 1;
_this->fp_dtor = fp_dtor;
_this->state = state;
status = locktbl_unlock(_this);
if (! status) {
*_pthis = _this;
return 0;
}
}
free(_this);
}
return status;
}
/* private/system destroy; called from 'refcount_release' */
int refcount_sys_destroy(
refcount* const _this
) {
assert(_this->refs < 1);
if (_this->fp_dtor) {
_this->fp_dtor(_this->state);
}
free(_this);
}
/* increment */
int refcount_acquire(
refcount* const _this
) {
int status = 0;
if (_this) {
status = locktbl_lock(_this);
if (! status) {
int refs = _this->refs++;
status = locktbl_unlock(_this);
if (! status) {
if (refs > 0) {
return 0;
}
status = EINVAL;
assert(0);
}
}
}
return status;
}
/* decrement */
int refcount_release(
refcount* const _this
) {
int status = 0;
if (_this) {
status = locktbl_lock(_this);
if (! status) {
int refs = --_this->refs;
status = locktbl_unlock(_this);
if (! status) {
if (refs < 1) {
refcount_sys_destroy(_this);
}
return 0;
}
}
}
return status;
}
/* copy */
int refcount_copy(
refcount** const _pdest, /* ptr-to-shared */
refcount** const _psrc /* ptr-to-local */
) {
int status = locktbl_swaplock(_pdest);
if (! status) {
int inc_status;
*_psrc = *_pdest; /* shared-load; local-store */
inc_status = refcount_acquire(*_psrc /* local-load */);
status = locktbl_swapunlock(_pdest);
if (! status) {
return inc_status;
}
}
return status;
}
/* swap */
int refcount_swap(
refcount** const _pdest, /* ptr-to-shared */
refcount** const _psrc /* ptr-to-local */
) {
int status = locktbl_swaplock(_pdest);
if (! status) {
int inc_status;
refcount* const prev = *_pdest; /* shared-load */
*_pdest = *_psrc; /* local-load; shared-store */
*_psrc = prev; /* local-store */
status = locktbl_swapunlock(_pdest);
if (! status) {
return inc_status;
}
}
return status;
}
-------------------------------
Sorry for any typos; I just quickly typed that out in the newsreader! A 100%
lock-based reference counting algorithm like the example above _is_ strongly
thread-safe. The reason you have to use two global arrays is because a
swap/copy operation needs lock two levels deep. You cannot do this with a
single locking table; here is why:
http://groups.google.com/group/microsoft.public.win32.programmer.kernel/msg/f7297761027a9459
Humm... Would you be interested in looking a working implementation? I am
thinking of getting up on my website today or tomorrow... You won't need an
assembler to compile it either! Just C and POSIX.
;^)
Any comments/questions?
Chris Thomasson
> "Walter Roberson" <robe...@ibd.nrc-cnrc.gc.ca> wrote in message
> news:fcm9at$2jf$1...@canopus.cc.umanitoba.ca...
>> In article <LMWdnXol59_2pHPb...@comcast.com>,
>> Chris Thomasson <cri...@comcast.net> wrote:
> Sorry for any typos; I just quickly typed that out in the newsreader!
Crap! I found one:
> -------------------------------
> /* Global Lock Table
> _______________________________________________*/
> #define LOCKTBL_HASHPTR_DEPTH() 8
> #define LOCKTBL_DEPTH() (LOCKTBL_HASHPTR_DEPTH() + 1)
> #define LOCKTBL_INIT() PTHREAD_MUTEX_INITIALIZER
> #define LOCKTBL_HASHPTR(mp_ptr) \
> (((mp_ptr)ptrdiff_t) % LOCKTBL_HASHPTR_DEPTH())
>
> static pthread_mutex_t g_locktbl[2][LOCKTBL_DEPTH] = {
[...]
That last like needs to read as:
static pthread_mutex_t g_locktbl[2][LOCKTBL_DEPTH()] = {
I forgot the parenthesis in the call to LOCKTBL_DEPTH()!
Okay... I am going to create compliable code and some test applications. I
will post a link to it here and on comp.programming.threads when I am
finished so people can play around with it...
Walter Roberson
Chris Thomasson <cri...@comcast.net> wrote:
>"Walter Roberson" <robe...@ibd.nrc-cnrc.gc.ca> wrote in message
>news:fcm9at$2jf$1...@canopus.cc.umanitoba.ca...
>> You indicated in your follow up that it could be done in POSIX without
>> any extensions. I question that. POSIX.1, IEEE 1003.1-1990,
>> specifically refused to get into any kind of mandatory locking
>> or mutexes or semaphores. All that it has is -advisory- locking,
>> and -advisory- locking is WEAK thread-safety, not strong thread-safety.
>You can get strong thread-safety from mutexs. You basically have to use two
>global array's of mutexs and hash the address of the reference count into an
>index. If you use a mutex per-object your assertion that mutexs provide weak
>thread-safety only basically holds true.
I made no such assertion.
>Here is a rough-draft pseudo-code sketch of how you can implement
>my refcount algorithm using 100% POSIX and some C:
>static pthread_mutex_t g_locktbl[2][LOCKTBL_DEPTH] = {
> pthread_mutex_lock(&g_locktbl[0][LOCKTBL_HASHPTR(mp_ptr)])
I keep a printed copy of ISO/IEC 9945-1 IEEE-Std-1003.1-1990
literally within arms reach of my desk. Here's what it has to
say about pthread_mutex_lock and pthread_mutex_t, in between the arrows:
-><-
It says exactly the same thing about mutexs.
It speaks a little longer about mandatory locks, but only in the
Rationale, B.6.5.2 File Control:
Mandatory locks were omitted for several reasons:
(1) Mandatory lock setting was done by multiplexing the
set-group-ID bit in most implementations; this was confusing,
at best.
(2) The relationship to file truncation as supported in 4.2BSD was
not well specified.
(3) Any publicly readable file could be locked by anyone. Many
historical implementations keep the password database in a publicly
readable file. A malicious user could thus prohibit logins. Another
possibility would be to hold open a long-distance telephone line.
(4) Some demand-paged historical implementations offer memory mapped
files, and enforcement cannot be done on that type of file.
The same section mentions semphores long enough to say that they
are not included.
Mutexes and pthreads were not introduced until IEEE POSIX 1003.1c-1995.
(working group 1003.4a)
As I believe I indicated earlier, this is a rather heavy standard
to implement. Assuming its presence in comp.lang.c is somewhat like
assuming that airplanes are all fly-by-wire in a discussion with
small-aircraft enthusists.
--
Okay, buzzwords only. Two syllables, tops. -- Laurie Anderson
Chris Thomasson
> In article <UPidnX73-bYSiXLb...@comcast.com>,
> Chris Thomasson <cri...@comcast.net> wrote:
>>"Walter Roberson" <robe...@ibd.nrc-cnrc.gc.ca> wrote in message
>>news:fcm9at$2jf$1...@canopus.cc.umanitoba.ca...
>
>>> You indicated in your follow up that it could be done in POSIX without
>>> any extensions. I question that. POSIX.1, IEEE 1003.1-1990,
>>> specifically refused to get into any kind of mandatory locking
>>> or mutexes or semaphores. All that it has is -advisory- locking,
>>> and -advisory- locking is WEAK thread-safety, not strong thread-safety.
>
>>You can get strong thread-safety from mutexs. You basically have to use
>>two
>>global array's of mutexs and hash the address of the reference count into
>>an
>>index. If you use a mutex per-object your assertion that mutexs provide
>>weak
>>thread-safety only basically holds true.
>
> I made no such assertion.
I must have totally misunderstood your last sentence in the following
paragraph:
>>> You indicated in your follow up that it could be done in POSIX without
>>> any extensions. I question that. POSIX.1, IEEE 1003.1-1990,
>>> specifically refused to get into any kind of mandatory locking
>>> or mutexes or semaphores. All that it has is -advisory- locking,
>>> and -advisory- locking is WEAK thread-safety, not strong thread-safety.
> As I believe I indicated earlier, this is a rather heavy standard
> to implement. Assuming its presence in comp.lang.c is somewhat like
> assuming that airplanes are all fly-by-wire in a discussion with
> small-aircraft enthusists.
Okay. I will post follow-ups to comp.programming.threads. I will post a
single link to the conversation here after I finish creating the code.
Chris Thomasson
POSIX says that NO more than ONE thread may read/write a shared location at
any one time. IMVHO, this simply _IMPLIES_ some sort of mutual exclusion
technique. If you disagree, please post follow-ups over in
comp.programming.threads. David Butenhof can shed some light on the issue;
he is a highly appreciated and valuable contributed to that group.
Walter Roberson
Chris Thomasson <cri...@comcast.net> wrote:
>Not to sound like a smart-ass bastard; but one quick point:
>POSIX says that NO more than ONE thread may read/write a shared location at
>any one time. IMVHO, this simply _IMPLIES_ some sort of mutual exclusion
>technique.
Once more you are being cavelier about what POSIX is. POSIX
is not just one standard, it is a -set- of standards. And
POSIX.1-1990 says *nothing* about threads. If you want a POSIX
with threads, then you need to reference POSIX.1c-1995 or
POSIX.1-1996, and you have to understand that systems can
be completely POSIX.1-1996 compliant if they have dummy routines
for everything that just return a "Threads not supported" error.
Go ahead and cite a specific section and standard number that you
believe supports your view. I'd be amazed if said section does
not ultimately trace back to a clause that says, at heart,
"If you support threads at all, here is how they need to act."
And that conditional is crucial. If your OS doesn't support shared
locations and doesn't support threads, then whatever clause you
were thinking of is very likely irrelevant. Sort of like a
Standards Act that says "If you herd purebred Unicorns, then
you must paint them orange!": those of us that don't imagine
that we are herding purebred Unicorns are not affected by the
clause.
Once again: this is comp.lang.c. We deal here with what can be
done with the C language, as specified by ANSI and ISO.
POSIX and X and nethack are nice things that make the rest of our
life more interesting, but they must not be mistaken as being
parts of C, and any statement like yours saying, "See, you can do
it in C!" will be have its fine-print examined (if it isn't just
outright ridiculed.)
--
There are some ideas so wrong that only a very intelligent person
could believe in them. -- George Orwell
Chris Thomasson
> In article <gdqdna1H-qJPqnLb...@comcast.com>,
> Chris Thomasson <cri...@comcast.net> wrote:
>>Not to sound like a smart-ass bastard; but one quick point:
>
>>POSIX says that NO more than ONE thread may read/write a shared location
>>at
>>any one time. IMVHO, this simply _IMPLIES_ some sort of mutual exclusion
>>technique.
IMVHO, it is a commonly known practice;
> Go ahead and cite a specific section and standard number that you
> believe supports your view.
RTM. I read the POSIX standard as a basic rule that expects controlled
access to a shared piece of state that is an analog of mutual exclusion.
Basically, only one thread shall ever be able to access a given piece of
shared state at any one time. If you use a single-threaded application,
equal to the realm of an execution of a Standard C program; you are still
following POSIX rules to the tee... Ditto for using various forms of mutual
exclusion; one thread at any one time... For instance, you can use a mutex
to regulate a plurality of thread's compatible accesses to a commonly held
data-structure. You can also create a mutex-like-entity out of condition
variables and a mutex that is responsible to enforcing access to a piece of
state that represents a predicate that a thread may wait on. Agreed? If not,
well, I welcome any opportunity to learn new and interesting logic that
adheres to common sense with open brains indeed!
;^)
[...]
> Once again: this is comp.lang.c. We deal here with what can be
> done with the C language, as specified by ANSI and ISO.
> POSIX and X and nethack are nice things that make the rest of our
> life more interesting, but they must not be mistaken as being
> parts of C, and any statement like yours saying, "See, you can do
> it in C!" will be have its fine-print examined (if it isn't just
> outright ridiculed.)
I will post the code over in comp.programming.threads. I would like to hear
your opinion on the matter.
Chris Thomasson
I found another one:
[...]
> /* swap */
> int refcount_swap(
> refcount** const _pdest, /* ptr-to-shared */
> refcount** const _psrc /* ptr-to-local */
> ) {
> int status = locktbl_swaplock(_pdest);
> if (! status) {
> int inc_status;
^^^^^^^^^^^^^6
this variable is useless. delete that line.
> refcount* const prev = *_pdest; /* shared-load */
> *_pdest = *_psrc; /* local-load; shared-store */
> *_psrc = prev; /* local-store */
> status = locktbl_swapunlock(_pdest);
> if (! status) {
> return inc_status;
^^^^^^^^^^^^^^^^
exchange that line with:
return 0;
> }
> }
> return status;
> }
>
> -------------------------------
[...]
I am almost done with version-0.001-(pre-alpha) library that does the POSIX
compatible reference counting.
Chris Thomasson
This is not really a bug but a confusing nuisance!
the variable names the in the refcount_copy/swap functions should be changes
as follows:
change every '_pdest' with '_psrc'
and vise versa.
in other words:
/* copy */
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;
*_pdest = *_psrc; /* shared-load; local-store */
inc_status = refcount_acquire(*_pdest /* local-load */);
status = locktbl_swapunlock(_psrc);
if (! status) {
return inc_status;
}
}
return status;
}
/* swap */
int refcount_swap(
refcount** const _pdest, /* ptr-to-shared */
refcount** const _psrc /* ptr-to-local */
) {
int status = locktbl_swaplock(_psrc);
if (! status) {
int inc_status;
refcount* const prev = *_psrc; /* shared-load */
*_psrc = *_pdest; /* local-load; shared-store */
*_pdest = prev; /* local-store */
status = locktbl_swapunlock(_psrc);
Chris Thomasson
> This is not really a bug but a confusing nuisance!
> the variable names the in the refcount_copy/swap functions should be
> changes as follows:
> change every '_pdest' with '_psrc'
> and vise versa.
FUCK!
I forgot to change the function parameter names for the 'refcount_swap'
function; here is the good one:
/* swap */
int refcount_swap(
refcount** const _psrc, /*<--- This one! ptr-to-shared */
refcount** const _pdest /*<---- And this one! ptr-to-local */
) {
int status = locktbl_swaplock(_psrc);
if (! status) {
refcount* const prev = *_psrc; /* shared-load */
*_psrc = *_pdest; /* local-load; shared-store */
*_pdest = prev; /* local-store */
status = locktbl_swapunlock(_psrc);
if (! status) {
return 0;
}
}
return status;
}
I am very sorry for making these stupid typos. That's what I get for typing
code in the newsreader then cut-and-pasting it to source files. Luckily for
me, the algorithm is correct, the typos are out and code proofs are enforces
by mutual exclusion... Thing are easy now and almost ready to post. I will
do it tomorrow. Thank you all who decided not to flame me into crispy bacon
strips!
:^0
Chris Thomasson
> In article <gdqdna1H-qJPqnLb...@comcast.com>,
> Chris Thomasson <cri...@comcast.net> wrote:
>>Not to sound like a smart-ass bastard; but one quick point:
>
>>POSIX says that NO more than ONE thread may read/write a shared location
>>at
>>any one time. IMVHO, this simply _IMPLIES_ some sort of mutual exclusion
>>technique.
>
> Once more you are being cavelier about what POSIX is. POSIX
> is not just one standard, it is a -set- of standards. And
> POSIX.1-1990 says *nothing* about threads.
[...]
Luckily for me, some of the more "recent" additives to the POSIX standard
actually do say something about threads...
;^)
Chris Thomasson
> In article <gdqdna1H-qJPqnLb...@comcast.com>,
> Chris Thomasson <cri...@comcast.net> wrote:
>>Not to sound like a smart-ass bastard; but one quick point:
>
>>POSIX says that NO more than ONE thread may read/write a shared location
>>at
>>any one time. IMVHO, this simply _IMPLIES_ some sort of mutual exclusion
>>technique.
>
> Once more you are being cavelier about what POSIX is. POSIX
> is not just one standard, it is a -set- of standards. And
> POSIX.1-1990 says *nothing* about threads.
[...]
The old stuff says nothing about threads... The new POSIX standard which has
threads states that only one thread may access shared state at any one time.
How is that different than only using a single thread in the first place?
So, I guess you can say that PThreads actually revolves around the rule that
only a single-threaded access to state? How does that different
fundamentally differ from a single-threaded execution?
Humm...
Walter Roberson
Chris Thomasson <cri...@comcast.net> wrote:
>"Walter Roberson" <robe...@ibd.nrc-cnrc.gc.ca> wrote in message
>news:fcng1n$ngi$1...@canopus.cc.umanitoba.ca...
>> Once more you are being cavelier about what POSIX is. POSIX
>> is not just one standard, it is a -set- of standards. And
>> POSIX.1-1990 says *nothing* about threads.
>Luckily for me, some of the more "recent" additives to the POSIX standard
>actually do say something about threads...
http://www.opengroup.org/onlinepubs/009695399/
"The Open Group Base Specifications Issue 6"
Section 2.9 Threads
_
|x> The functionality described in this section is dependant upon
-
support of the Threads option (and the rest of this section is
not further shaded for this option). _
<x|
-
"Threads option". OPTION.
In other words, a system can be perfectly compliant to the newest
POSIX specification and yet have no threads support at all.
--
Is there any thing whereof it may be said, See, this is new? It hath
been already of old time, which was before us. -- Ecclesiastes
Chris Thomasson
> In article <y5idnehJGPZ_IXLb...@comcast.com>,
> Chris Thomasson <cri...@comcast.net> wrote:
>>"Walter Roberson" <robe...@ibd.nrc-cnrc.gc.ca> wrote in message
>>news:fcng1n$ngi$1...@canopus.cc.umanitoba.ca...
>
>>> Once more you are being cavelier about what POSIX is. POSIX
>>> is not just one standard, it is a -set- of standards. And
>>> POSIX.1-1990 says *nothing* about threads.
>
>>Luckily for me, some of the more "recent" additives to the POSIX standard
>>actually do say something about threads...
>
> http://www.opengroup.org/onlinepubs/009695399/
> "The Open Group Base Specifications Issue 6"
> Section 2.9 Threads
> _
> |x> The functionality described in this section is dependant upon
> -
> support of the Threads option (and the rest of this section is
> not further shaded for this option). _
> <x|
> -
>
> "Threads option". OPTION.
>
> In other words, a system can be perfectly compliant to the newest
> POSIX specification and yet have no threads support at all.
I see.
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!
:^)
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
> 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
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.