A technique for ABA version counters...
Chris Thomasson
one:
pseudo-code
--------------------------
struct item_s {
/* ... */
uint32_t aba_count_1; /* init to 0 */
uint32_t aba_count_2; /* init to 0 */
};
struct anchor_s {
item_s *item;
uint32_t aba_count;
};
#define COUNT_OVERFLOW() 0x1
void inc_anchor_item_aba(anchor_s *_this, item_s *i) {
uint32_t flags = 0, laba = i->aba_count_1;
if (! (laba + 1)) {
laba = _this->aba_count_2;
if (laba + 1) {
/* we rolled the first 32-bit count... */
flags = COUNT_OVERFLOW();
} else {
/* we rolled both 32-bit counts... */
_this->aba_count_1 = 1;
_this->aba_count_2 = 0;
laba = 1;
}
} else {
i->aba_count_1 = laba + 1;
}
{
anchor_s xchg, cmp = *_this;
xchg.item = i | flags;
xchg.aba_count = laba;
while(! DWCAS(_this, &cmp, &xchg));
}
}
When the items counter overflows, it switches to the other 32-bit count, and
sets a bit on the item pointer in the anchor. Since we are using a
"distributed" aba counting scheme (e.g., per-item), we can use the bit to
distinguish item_s::aba_count_1 from item_s::aba_count_2. If counter 1
rolls, we set the bit and use counter 2...
You could further extend this by defining extra bits to represent different
counts. Think of this:
#define COUNT_DEPTH() 3
#define COUNT_OVERFLOW_0() 0x1
#define COUNT_OVERFLOW_1() 0x2
#define COUNT_OVERFLOW_2() 0x4
struct item_s {
/* ... */
uint32_t aba_count[COUNT_DEPTH()];
};
Any thoughts on this technique? Have you seen it before?
Humm...
Chris Thomasson
[...]
> if (! (laba + 1)) {
> laba = _this->aba_count_2;
>
> if (laba + 1) {
> /* we rolled the first 32-bit count... */
I totally forgot to add the increment to the second counter! Add this:
i->aba_count_2 = laba + 1;
Chris Thomasson
> laba = _this->aba_count_2;
>
> if (laba + 1) {
> /* we rolled the first 32-bit count... */
>
> } else {
>
> /* we rolled both 32-bit counts... */
> _this->aba_count_1 = 1;
> _this->aba_count_2 = 0;
> laba = 1;
^^^^^^^^^^^^^^^^
should be laba = 0;
Joe Seigh
> Here is a little trick that you can use to get two 32-bit counters, out of
> one:
>
>
> When the items counter overflows, it switches to the other 32-bit count, and
> sets a bit on the item pointer in the anchor. Since we are using a
> "distributed" aba counting scheme (e.g., per-item), we can use the bit to
> distinguish item_s::aba_count_1 from item_s::aba_count_2. If counter 1
> rolls, we set the bit and use counter 2...
>
>
> You could further extend this by defining extra bits to represent different
> counts. Think of this:
>
[...]
>
>
> Any thoughts on this technique? Have you seen it before?
>
>
> Humm...
>
>
Two 32 bit counters ganged together only gets you a 33 bit counter.
But since you're giving up a bit, they're really 2 31 bit counters
ganged into a 32 bit counter. To gang 4 counters, you give up
2 bits and still only get a 32 counter. Unless I'm missing something
here.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Chris Thomasson
news:Q9KdnfXcub1G097Y...@comcast.com...
> Chris Thomasson wrote:
>> Here is a little trick that you can use to get two 32-bit counters, out
>> of one:
[...]
>> You could further extend this by defining extra bits to represent
>> different counts. Think of this:
[...]
>> Any thoughts on this technique? Have you seen it before?
[...]
> Two 32 bit counters ganged together only gets you a 33 bit counter.
I was trying to make an item have to gone through a complete push/pop
to/from a collection, (ULONG_MAX * K) number of times before the counter
would actually roll.
> But since you're giving up a bit, they're really 2 31 bit counters
> ganged into a 32 bit counter. To gang 4 counters, you give up
> 2 bits and still only get a 32 counter. Unless I'm missing something
> here.
I set the bit on the anchor_s::item pointer, not on the anchor_s::aba_count.
So, I don't give up a bit on the counter in the anchor, I add a bit to its
pointer; if align items on a sufficient boundary, I can get at a number of
bits...
Anyway, I think I am going to take your advice of using PDR to solve ABA...
However, I am going to amortize the use of PDR by only deferring items only
after all of their private aba counters roll... In other words, I will not
push an item into a shared collection if its aba counters have rolled, I
defer to PDR instead. After PDR decides to call me back with some info on
the item that states that its quiescent, I then reset counters and the item
doesn't see PDR again until it rolls its private counters again...
IMHO, using PDR to sole ABA is overkill, however, if you amortize its usage
across a distributed (e.g., per-item) ABA counting scheme, then it doesn't
seem so bad anymore... Humm...
Sound workable to you Joe? If not, Any suggestions'?
IMHO, I think it will work out fairly good...
Joe Seigh
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:Q9KdnfXcub1G097Y...@comcast.com...
>
>
>
> I was trying to make an item have to gone through a complete push/pop
> to/from a collection, (ULONG_MAX * K) number of times before the counter
> would actually roll.
>
>
>
>>But since you're giving up a bit, they're really 2 31 bit counters
>>ganged into a 32 bit counter. To gang 4 counters, you give up
>>2 bits and still only get a 32 counter. Unless I'm missing something
>>here.
>
>
> I set the bit on the anchor_s::item pointer, not on the anchor_s::aba_count.
> So, I don't give up a bit on the counter in the anchor, I add a bit to its
> pointer; if align items on a sufficient boundary, I can get at a number of
> bits...
Ok, you get log(n) extra bits for n extra counters. Also per prior
discussion on per item version counts, log(n) extra bits for n items
best case, 0 extra bits worst case.
>
> Anyway, I think I am going to take your advice of using PDR to solve ABA...
> However, I am going to amortize the use of PDR by only deferring items only
> after all of their private aba counters roll... In other words, I will not
> push an item into a shared collection if its aba counters have rolled, I
> defer to PDR instead. After PDR decides to call me back with some info on
> the item that states that its quiescent, I then reset counters and the item
> doesn't see PDR again until it rolls its private counters again...
>
> IMHO, using PDR to sole ABA is overkill, however, if you amortize its usage
> across a distributed (e.g., per-item) ABA counting scheme, then it doesn't
> seem so bad anymore... Humm...
>
>
> Sound workable to you Joe? If not, Any suggestions'?
Depends on whether the PDR scheme is amortizable or not. I guess that's
the trick, whether you get any synergy out of it.
Chris Thomasson
> Chris Thomasson wrote:
>> "Joe Seigh" <jsei...@xemaps.com> wrote in message
>> news:Q9KdnfXcub1G097Y...@comcast.com...
[...]
>> Anyway, I think I am going to take your advice of using PDR to solve
>> ABA... However, I am going to amortize the use of PDR by only deferring
>> items only after all of their private aba counters roll... In other
>> words, I will not push an item into a shared collection if its aba
>> counters have rolled, I defer to PDR instead. After PDR decides to call
>> me back with some info on the item that states that its quiescent, I then
>> reset counters and the item doesn't see PDR again until it rolls its
>> private counters again...
>>
>> IMHO, using PDR to sole ABA is overkill, however, if you amortize its
>> usage across a distributed (e.g., per-item) ABA counting scheme, then it
>> doesn't seem so bad anymore... Humm...
>>
>>
>> Sound workable to you Joe? If not, Any suggestions'?
>
> Depends on whether the PDR scheme is amortizable or not. I guess that's
> the trick, whether you get any synergy out of it.
I am planning on amortizing the number of times I have to call into the PDR
API (e.g., pdr_defer(...)). IMO, "normal" usage of PDR wrt solving the ABA
problem "usually" involves calling the defer function every time you pop a
node from a lock-free shared collection. You can free yourself from using
any ABA counters when you do it this way; for example:
void pdr_node_quiescent(void *s) {
node_t *n = s;
if (we_can_reuse_the_node(...)) {
node_cache_push(n);
} else if(or_we_can_free_the_node(...)) {
node_free(n);
}
}
void pop_the_normal_way() {
node_t *n = lfcollection_pop(...);
if (n) { PDR_DEFER(pdr_node_quiescent, n); }
}
I am thinking of performing the pop another way; for example:
void pop_the_amortized_way() {
node_t *n = lfcollection_pop(...);
if (n) {
/* check if our counters are okay to inc-and-reuse */
if (node_have_aba_counters_rolled(n)) {
/* okay, our counters are rolled, and its not safe to reuse; defer it!
*/
PDR_DEFER(pdr_node_quiescent, n);
} else {
/* our counters are valid; inc them! */
node_inc_aba_counters(n);
/* reuse it! */
node_cache_push(n);
}
}
}
I skip calls into PDR, until a nodes private counters (e.g., per-item) are
no longer safe to reuse (e.g., they rolled). This method can drastically cut
down on the number of times you have to defer a node through PDR. So, you
get to freely reuse a node, and not make any use of PDR, until the nodes
private counters have rolled and are no longer safe to reuse... That is the
amortization scheme I am thinking of experimenting with.
I mean, why would you want to call PDR every time you pop a node? If you do
it that way, you are going to be making use of PDR every time you pop from a
lock-free linked node-based shared collection; that is plain overkill
IMHO... This amortization technique can allow you to skip PDR if the nodes
counters can be reused. I think it could turn out to be a fairly good
solution for using PDR to solve ABA...