|
Home > Archive > Unix Programming > September 2007 > Strongly Thread-Safe Atomic Reference Counted Pointers...
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Strongly Thread-Safe Atomic Reference Counted Pointers...
|
|
|
|
| Rainer Weikusat 2007-09-20, 7:30 am |
| "Chris Thomasson" <cristom@comcast.net> writes:
> Since I am new to this group, I was wondering if the following
> discussion would be on topic:
>
> http://groups.google.com/group/comp...cb281c562c694a6
>
> its basically a pure 'C and POSIX Threads' implementation of a fairly
> versatile, general purpose, strongly thread-safe reference counted
> pointer algorithm:
My humble personal opinion on this it is unlikely that people who swallow
Yes, but you're counting on the fact that you *can* do pointer
arithmetic, basically saying that a pointer is an integer.
<1190225076.909068.10060@19g2000hsx.googlegroups.com>
but claim to be programming in C have anything of value to communicate
(yet).
| |
| Chris Thomasson 2007-09-21, 7:22 pm |
| "Rainer Weikusat" <rweikusat@mssgmbh.com> wrote in message
news:87lkb1el7w.fsf@fever.mssgmbh.com...
> "Chris Thomasson" <cristom@comcast.net> writes:
>
> My humble personal opinion on this it is unlikely that people who swallow
>
> Yes, but you're counting on the fact that you *can* do pointer
> arithmetic, basically saying that a pointer is an integer.
> <1190225076.909068.10060@19g2000hsx.googlegroups.com>
>
> but claim to be programming in C have anything of value to communicate
> (yet).
Yeah. That sure does sound cheesy... However, I kind of need a way to hash a
pointer value into an integer which represents an index into an array. It
dosen't really matter to the "code in question" if any data is lost during
the hashing process. The following post contains some pseudo-code that uses
the hash from a pointer to index into a global table of mutexs. This makes
it so I don't need per-object meta-data wrt syncronization object state; I
don't need a mutex per-object:
http://groups.google.com/group/comp...0c011baf08844c4
In the code in question, under the Global Lock Table section:
http://appcore.home.comcast.net/refcount-c-v0-002.html
I would like to know of better/safer/kosher ways to doing this in C...
Specifically, the stupid-simple hashing technique in the following snippet
from the code linked above:
________________________________________
________________________
#define LOCKTBL_HASHPTR_DEPTH() 31
#define LOCKTBL_DEPTH() 32 /* power of 2 */
#define LOCKTBL_INIT() PTHREAD_MUTEX_INITIALIZER
#define LOCKTBL_RWINIT() PTHREAD_RWLOCK_INITIALIZER
#define LOCKTBL_HASHPTR(mp_ptr) \
(((ptrdiff_t)(mp_ptr)) % LOCKTBL_HASHPTR_DEPTH())
static pthread_mutex_t g_locktbl[LOCKTBL_DEPTH()] = {
PLACE(LOCKTBL_INIT, LOCKTBL_DEPTH())
};
static pthread_rwlock_t g_rwlocktbl[LOCKTBL_DEPTH()] = {
PLACE(LOCKTBL_RWINIT, LOCKTBL_DEPTH())
};
#define locktbl_lock(mp_ptr) \
pthread_mutex_lock(&g_locktbl[LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_unlock(mp_ptr) \
pthread_mutex_unlock(&g_locktbl[LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_rdlock(mp_ptr) \
pthread_rwlock_rdlock(&g_rwlocktbl[LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_rdunlock(mp_ptr) \
pthread_rwlock_unlock(&g_rwlocktbl[LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_wrlock(mp_ptr) \
pthread_rwlock_wrlock(&g_rwlocktbl[LOCKTBL_HASHPTR(mp_ptr)])
#define locktbl_wrunlock(mp_ptr) \
pthread_rwlock_unlock(&g_rwlocktbl[LOCKTBL_HASHPTR(mp_ptr)])
________________________________________
________________________
Can you see _any_ possibility of this code enticing an army of evil
undefined-behavior that decides it would be fun to make a computer that's
runs it explode, and get its user canned in a single atomic operation?
;^)
| |
| Scott Lurndal 2007-09-21, 7:22 pm |
| "Chris Thomasson" <cristom@comcast.net> writes:
>
>I would like to know of better/safer/kosher ways to doing this in C...
>Specifically, the stupid-simple hashing technique in the following snippet
>from the code linked above:
> ________________________________________
________________________
>#define LOCKTBL_HASHPTR_DEPTH() 31
>#define LOCKTBL_DEPTH() 32 /* power of 2 */
>#define LOCKTBL_INIT() PTHREAD_MUTEX_INITIALIZER
>#define LOCKTBL_RWINIT() PTHREAD_RWLOCK_INITIALIZER
>#define LOCKTBL_HASHPTR(mp_ptr) \
> (((ptrdiff_t)(mp_ptr)) % LOCKTBL_HASHPTR_DEPTH())
First, lose the empty parenthesis on the macro definitions. They're
not required. Remember that cpp (the C pre processor) just does
simple substitution.
Second if you are using malloc(3) to allocate your mp_ptr's, be
aware that the allocated pointers will typically be aligned on a
16 or 32-byte boundary. This may cause your hash algorithm to
hash all entries to the same bucket. If not dynamically
allocated, things will still be allocated at addresses that are
congruent to zero modulo four or eight, which still reduces the
number of hash buckets you'll hit.
If you really want to use a pointer as a hash index (not generally
recommended), use bits other than the low-order bits as your key.
Good coding practice would frame LOCKTABLE_HASHPTR_DEPTH in
terms of LOCKTBL_DEPTH:
#define LOCKTBL_HASHPTR_DEPTH (LOCKTBL_DEPTH-1)
> ________________________________________
________________________
>
>Can you see _any_ possibility of this code enticing an army of evil
>undefined-behavior that decides it would be fun to make a computer that's
>runs it explode, and get its user canned in a single atomic operation?
Why, again, do you need more than a single lock per processor?
I'll point you to this:
<http://portal.acm.org/citation.cfm?id=645604.662583>
scott
| |
| Chris Thomasson 2007-09-23, 7:29 am |
| "Scott Lurndal" <scott@slp53.sl.home> wrote in message
news:L9ZIi.4990$3Y1.4869@newssvr17.news.prodigy.net...
> "Chris Thomasson" <cristom@comcast.net> writes:
>
>
> First, lose the empty parenthesis on the macro definitions. They're
> not required. Remember that cpp (the C pre processor) just does
> simple substitution.
Sometimes it "useful" to define macro as functions:
http://groups.google.com/group/comp...83fd8524cddcae9
> Second if you are using malloc(3) to allocate your mp_ptr's, be
> aware that the allocated pointers will typically be aligned on a
> 16 or 32-byte boundary. This may cause your hash algorithm to
> hash all entries to the same bucket. If not dynamically
> allocated, things will still be allocated at addresses that are
> congruent to zero modulo four or eight, which still reduces the
> number of hash buckets you'll hit.
Great point indeed. Perhaps I could multply the pointer value by 307 or
something followed by a right shift by 8 or so bits.
[...]
>
> Good coding practice would frame LOCKTABLE_HASHPTR_DEPTH in
> terms of LOCKTBL_DEPTH:
>
> #define LOCKTBL_HASHPTR_DEPTH (LOCKTBL_DEPTH-1)
Unfortunately, this is incompatible with the pre-processor technique I am
using to initialize the mutex tables with 'PTHREAD_xxx__INITIALIZER' macros.
>
> Why, again, do you need more than a single lock per processor?
[...]
You could use a single-lock per-processor in a way that allows reader
threads to acquire access to a common shared data-structure by taking a lock
on "it's" processor. Writer threads take all the locks in order to block out
any and all readers.
| |
| Chris Thomasson 2007-09-24, 7:23 pm |
| "Chris Thomasson" <cristom@comcast.net> wrote in message
news:y5GdnbUbmIXohWvbnZ2dnUVZ_oesnZ2d@co
mcast.com...[vbcol=seagreen]
> "Scott Lurndal" <scott@slp53.sl.home> wrote in message
> news:L9ZIi.4990$3Y1.4869@newssvr17.news.prodigy.net...
[...]
[vbcol=seagreen]
>
> Unfortunately, this is incompatible with the pre-processor technique I am
> using to initialize the mutex tables with 'PTHREAD_xxx__INITIALIZER'
> macros.
[...]
Actually, that is compatible:
#define LOCKTBL_DEPTH() 32
#define LOCKTBL_HASHPTR_DEPTH() (LOCKTBL_DEPTH() - 1)
The following would not be:
#define LOCKTBL_HASHPTR_DEPTH() 31
#define LOCKTBL_DEPTH() (LOCKTBL_HASHPTR_DEPTH() + 1)
|
|
|
|
|