Walter Roberson said:
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?
. You wouldn't be able to carry around the R/W lock with the