[RFC] "mostly" lock-free cas-based atomic reference counting...
Chris Thomasson
previous references to a given object, to try to acquire one. shared_ptr<>
dosen't allow for this to occur. You simply have to own a previous reference
in order to take a new one. This is a "classic race-condition", indeed:
http://groups.google.com/group/comp.programming.threads/msg/93983d56839ffb45
So, the only places where you need to have special sync is when you want to
grab that initial reference, and when you drop to zero. I differentiate from
two by labeling the special sync case a "Strong Increment/Decrement", and
calling the case when you own a previous reference and want another, a "Weak
Increment". My pseudo-code implementation uses a hashed spinlock scheme in
order to take a lock based on the pointer to a reference count object. The
entire locking scheme is completely separate state from the counter, and
simply never gets destroyed. This is necessary in order to safely and
atomically drop the reference count to zero, and subsequently destroy the
count object. The global spinlock state will persist throughout, and beyond
the lifetime of every single reference count object a user decides to
allocate. So, as long as you keep all of the strong increments AND strong
decrements "that work on pointers which all point to the exact same
reference counter object" atomic, you can safely acquire and release
references. Of course, if you don't care about atomic reference counting,
then you don't really need to read any more of this crap! lol.
;)
!!> Please note that this initial pseudo-code only demonstrates weak and
strong increments along with strong decrements. Next I will show how to swap
pointers to reference counter objects, to-and-from various shared-locations.
This stuff is more about your basic atomic pointer operations, rather than
reference counting in general; IMHO, its probably best to keep the logic
somewhat separate...
refs.c (pseudo-code only!)
-----------------------------------
/*=======\
\\//\\// Simple Word-Based Variables
==============================================*/
typedef int32_t intword_t;
typedef intword_t spinlock_t;
typedef intword_t rc_t;
/*\\// Critical Compile-Time Assertion */
struct critical_assert_na {
char test[(sizeof(intword_t) == sizeof(void*)) ? 1 : -1];
};
/*\\// Helper Macros */
#define PTR_TO_WORD(ptr) ((intword_t)((void*)(ptr)))
#define WORD_TO_PTR(wrd) ((void*)(intword_t)(wrd))
/*=======\
\\//\\// Global/Static Hashed Spinlocks
==============================================*/
/*\\// Helper Macros*/
#define SPINLOCK_DEPTH 1024
#define SPINLOCK_HASHPTR(ptr) \
(&gspinlocks[(PTR_TO_WORD(ptr) % SPINLOCK_DEPTH)])
/*\\// Global/Static Spinlock Array */
static spinlock_t gspinlocks[SPINLOCK_DEPTH] = { 0 };
/*\\// Locks a Hashed Spinlock */
static spinlock_t* spinlock_lock(void *hptr) {
spinlock_t *_this = SPINLOCK_HASHPTR(hptr);
while(! CAS_ACQUIRE(_this, 0, 1)) {
do { /* slow-path; wait until zero... */
_asm pause /* yield, whatever... */
} while((*_this));
}
return _this;
}
/*\\// Unlocks a Hashed Spinlock */
static void spinlock_unlock(spinlock_t *_this) {
STORE_RELEASE(_this, 0);
}
/*=======\
\\//\\// Atomic Reference Counted Pointers
==============================================*/
/*\\// User-State and Destructor Callbacks */
typedef void (*fp_general_t) (void*);
typedef fp_general_t refs_fp_dtor_t;
struct refs_ustate_t {
refs_fp_dtor_t fp_dtor;
void *state;
};
/*\\// Atomic Reference Counter */
struct refs_t {
rc_t count;
refs_ustate_t ustate;
};
/*\\// Allocates a new reference counter */
static int refs_alloc(refs_t **_pthis, refs_ustate_t const *ustate, int
count) {
refs_t *_this = malloc(sizeof(*_this));
if (_this) {
_this->count = count;
_this->ustate = *ustate;
*_pthis = _this;
return 0;
}
return ENOMEM;
}
/*\\// Decrements the refcnt by count, and fires
\\// the user-state callback if it drops to zero */
static void refs_dec(refs_t *_this, int count) {
if (XADD_RELEASE(&_this->refcnt, -count) == count) {
refs_ustate_t ustate;
/* lock, read and destroy... */
spinlock_t *lock = spinlock_lock(_this);
ustate = _this->ustate;
spinlock_unlock(lock);
free(_this);
/* Now, we process any user-state there may be... */
if (ustate.fp_dtor) {
ustate.fp_dtor(ustate.state);
}
}
}
/*\\// Increments the refcnt only if its greater-than zero */
static int refs_inc_if(refs_t *_this, int count) {
rc_t cmp;
do {
cmp = _this->count;
/* only if greater than 1! */
if (cmp < 1) { return 0; }
/* try to acquire the reference */
} while(! CAS_ACQUIRE(&_this->count, cmp, cmp + count));
return 1;
}
/*\\// Weakly increments a refcnt that was previously acquired
\\// with refs_inc_strong */
static void refs_inc_weak(refs_t *_this, int count) {
XADD_ACQUIRE(&_this->count, count);
}
/*\\// Strongly incrments a refcnt for the first time. That is,
\\// the calling thread dosen't own a prevoud reference... */
static refs_t* refs_inc_strong(refs_t **_pthis, int count) {
/* perform initial read */
refs_t *_this = *_pthis;
if (_this) {
refs_t *cmp;
/* and away we go, weeeeeee! lol. ;^) */
for(;;) {
/* lock the refcnt pointer */
spinlock_t *lock = spinlock_lock(_this);
/* double-check the initial read, and try to
increment if equal */
cmp = *_pthis;
if (_this == cmp && refs_inc_if(_this, count)) {
spinlock_unlock(_this);
break;
}
/* DAMN! We have to try this crap it all over again! ;^(... */
spinlock_unlock(_this);
_asm pause /* exponent backoff-retry, ect... */
_this = *_pthis;
}
}
return _this;
}
Thats all folks!
;^)
Any thoughts?
Chris Thomasson
Chris Thomasson
;)
I left out one word here. Let be clarify, this:
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:h-edncP5X6_luozY...@comcast.com...
> Atomic reference counting has to be able to allow a thread that does any
> previous references to a given object, to try to acquire one. shared_ptr<>
> dosen't allow for this to occur. You simply have to own a previous
> reference
> in order to take a new one. This is a "classic race-condition", indeed:
should read like this:
Atomic reference counting has to be able to allow a thread that does NOT OWN
any
previous references to a given object, to try to acquire one. shared_ptr<>
doesn't allow for this to occur. You simply have to own a previous reference
in order to take a new one. This is a "classic race-condition", indeed:
Sorry for any confusion.
Chris Thomasson
As with all of my quick pseudo-code, there are small bugs that piss me off,
and Murphy's law strikes again. I will try to correct all of them, as I see
them. Luckily, there are no major flaws with the algorithm, just minor typos
in pseudo-code...
;)
The follow code has a typo/bug:
> /* lock the refcnt pointer */
> spinlock_t *lock = spinlock_lock(_this);
I lock the spinlock, and keep a pointer to the spinlock state; lock var.
> /* double-check the initial read, and try to
> increment if equal */
> cmp = *_pthis;
> if (_this == cmp && refs_inc_if(_this, count)) {
> spinlock_unlock(_this);
^^^^^^^^^^
I call spinlock_unlock with a pointer to the reference count object instead
of the pointer to the previously locked spinlock state!! So, of course, it
should look like this:
spinlock_unlock(lock);
> break;
> }
>
> /* DAMN! We have to try this crap it all over again! ;^(... */
> spinlock_unlock(_this);
^^^^^^^^^^^^^^^^^^
Ditto!
spinlock_unlock(lock);
> _asm pause /* exponent backoff-retry, ect... */
> _this = *_pthis;
> }
> }
>
> return _this;
> }
Sorry!
;)
Chris Thomasson
> if (cmp < 1) { return 0; }
I mean only if greater than 1 of course!!!
Chris Thomasson
FU$@#@#ING SH$$IT DA##@MIT!!!
> I mean only if greater than 1 of course!!!
I mean only if greater than 0.
That's ZERO, got it???
Okay, I am through freaking out now...
;)
I need to slam a giant pot full of coffee in order to stay away for any
longer; I am kind of tired, please try to bear with me here...
Thank you all for you patience!
:)
Chris Thomasson
[...]
> /*\\// Strongly incrments a refcnt for the first time. That is,
> \\// the calling thread dosen't own a prevoud reference... */
> static refs_t* refs_inc_strong(refs_t **_pthis, int count) {
The read, lock, re-read, double-check, inc if greater than 0, and the final
lock-and-read when count finally drops to zero makes this pseudo-code
correct wrt true atomic reference counting...