lock-free singly linked list design
Toby Douglass
I've had a thought or two. I will fall off my chair if any of this is
original. What I would like however is to see what you guys think,
since it's nicer to find mistakes *before* you've put in hours and hours
of implementation work.
Having looked somewhat at the literature, there seem to be a number of
lists which require GC and one from Valois which does not; where his
list is critised (in another paper) for its cursor construct, which
apparently can effectively lock, by blocking forward progress.
I read about Harris' delete bit, which is critised I think by Michael,
where he points out you can't use Harris' technique with a freelist; he
doesn't explain why, but I can guess if you have a thread pointing at an
element and that element is unlinked, returned to the freelist and then
re-used and then the original thread comes to look at that element,
well, you're in trouble.
So, I thought, well, the problem is, we need to be able to see that the
element we have a pointer to is no longer valid.
What if we had, in our cursor, a copy not just of the pointer to the
element, but also its ABA counter? setting aside the requirement for
extra bits for now, if we could do this, then when we come to use the
element we point at, we could check its still valid for us, by comparing
its current ABA counter with the value we have, where the ABA counter is
incremented when an element is unlinked from the list.
So that would let us look at an element safely. But what about getting
the next element?
We can look at our current element and get our next pointer - which we
do. But now we have the same problem again; all we have is a pointer.
We don't have the ABA counter for the next element. So that element
could be invalidated before we look at it and we'd never know.
So in an element (not in a cursor) we also need to store the ABA counter
of next element, not just the pointer to the next element.
So that gives us the following requirement in a cursor;
1. pointer to current element
2. ABA of current element
And the following requirement in an element;
1. our ABA counter
2. pointer to next
3. ABA counter of next
4. user data
I don't think we need a delete bit any more, because we can simply bump
the ABA counter as the logical step of deleting.
So, let's say we have a 64 bit machine with contigious double-word
compare-and-swap. That gives us 128 atomic bits.
Our element then might look like this;
1. our ABA counter (21 bits)
2. pointer to next (21 bits)
3. ABA counter of next (21 bits)
4. user data (64 bits)
And the cursor like this;
1. pointer to current element (32 bits)
2. ABA of current element (32 bits)
Now the obvious problem is a 21 bit ABA counter. It's too short. But
what we could do is rather than use a freelist for backing store, use a
*queue*. That way we have to be unlucky on the ABA counter *and*
unlucky on the queue. So the chance of our ABA counter failing is 1/2^
21. If we put 2^11 elements in the queue, we now effectively have a 32
bit ABA counter. 2^11 is 2048 elements, which are 2 bytes each, so
that's 4kb per list - which is pretty acceptable.
Of course, the queue is slower than the freelist - I benchmark M&S'
queue about 2/3rds the speed of Treibers freelist (on the latest quad
core ARM running Linux).
Finally, note the user data is part of the atomic bits. This means when
we come to read or write the user data, we can in the act of reading or
writing atomically check the ABA counter is correct - e.g. that the
element remains valid.
So - what have I blatantly missed? how does it all fall over? :-)
Chris M. Thomasson
news:MPG.25adcb375...@text.giganews.com...
> I've been thinking about lock-free singly linked lists.
>
> I've had a thought or two. I will fall off my chair if any of this is
> original. What I would like however is to see what you guys think,
> since it's nicer to find mistakes *before* you've put in hours and hours
> of implementation work.
>
> Having looked somewhat at the literature, there seem to be a number of
> lists which require GC and one from Valois which does not; where his
> list is critised (in another paper) for its cursor construct, which
> apparently can effectively lock, by blocking forward progress.
>
> I read about Harris' delete bit, which is critised I think by Michael,
> where he points out you can't use Harris' technique with a freelist; he
> doesn't explain why, but I can guess if you have a thread pointing at an
> element and that element is unlinked, returned to the freelist and then
> re-used and then the original thread comes to look at that element,
> well, you're in trouble.
>
> So, I thought, well, the problem is, we need to be able to see that the
> element we have a pointer to is no longer valid.
>
> What if we had, in our cursor, a copy not just of the pointer to the
> element, but also its ABA counter? setting aside the requirement for
> extra bits for now, if we could do this, then when we come to use the
> element we point at, we could check its still valid for us, by comparing
> its current ABA counter with the value we have, where the ABA counter is
> incremented when an element is unlinked from the list.
>
> So that would let us look at an element safely.
How would you handle issue in which Thread A verifies that an element E is
valid, then right before it tries to dereference the pointer, Thread B pops
E from the stack, bumps the aba counter and inserts it into a freelist. Now,
Thread A dereferences E and operates on state of a node that is in the
freelist. This could create a race-condition. Think if Thread A is in the
middle of accessing element E and then E is popped and reused? BTW, this is
not meant to be a solution to memory reclamation right?
Toby Douglass
> "Toby Douglass" <a...@b.com> wrote in message
> > So, I thought, well, the problem is, we need to be able to see that
the
> > element we have a pointer to is no longer valid.
> >
> > What if we had, in our cursor, a copy not just of the pointer to the
> > element, but also its ABA counter? setting aside the requirement for
> > extra bits for now, if we could do this, then when we come to use the
> > element we point at, we could check its still valid for us, by comparing
> > its current ABA counter with the value we have, where the ABA counter is
> > incremented when an element is unlinked from the list.
> >
> > So that would let us look at an element safely.
>
> How would you handle issue in which Thread A verifies that an element E is
> valid, then right before it tries to dereference the pointer, Thread B pops
> E from the stack, bumps the aba counter and inserts it into a freelist. Now,
> Thread A dereferences E and operates on state of a node that is in the
> freelist. This could create a race-condition. Think if Thread A is in the
> middle of accessing element E and then E is popped and reused?
When a thread has to verify an element is valid, it will be doing so
because there is data is wishes to obtain from that element; and that
data is either the pointer to next, the ABA counter of next, the user
data in the element, or finally, the ABA counter of the element (with a
view to bumping it, as the first stage of a delete).
The solution in principle is that in all cases, the thread is able, *in
the CAS of verification*, to obtain, or to set, the data it is
manipulating - because all of this data exists inside the double-word
which is the element and so can all be seen in a single double-word
compare-and-swap.
The cursor consists of a 32 bit index and a 32 bit ABA counter. The
index is the index of the element the cursor points at and the ABA
counter is the ABA counter of the element the cursor points at.
To access an element, we first perform a normal, non-atomic read. We
have to do this to obtain, from the element, the index and ABA counter
of the next element and the user data, so we can form up a two-word
element which is what we think the element looks like now.
We then DCAS, using that element that we formed up; if the DCAS
succeeds, we know we caught the element with the correct ABA counter -
and that means we now have valid data.
So, for example;
cursor( cursor_target_index, cursor_target_aba );
element( element_aba, element_next_index, element_next_aba, user_data );
So our cursor points at an element; we first read the element. That
gives us a copy of current element data (which may change at any time,
of course). We might already see the ABA counter is incorrect and fail
at this point. Say what we want to do is bump the ABA counter to
delete, the element; so we now form up an element in memory, like so;
new_element( element_aba+1, element_next_index, element_next_aba,
user_data );
We then DCAS( &element, new_element, copy_element );
If we succeed, all is dandy; we know we must have succeeded on the same
ABA counter, so we know the element is valid. If we fail, we could fail
for a number of reasons - but we can see which reason from examining the
original value of element and then we can decide what to do.
Note in fact in this case, we don't need to do anything with user data,
and trying to do just makes us more able to fail, since we can fail due
to the user data changing; so really, we'd just use CAS, not DCAS.
> BTW, this is
> not meant to be a solution to memory reclamation right?
Correct. All it does is permit you to use a freelist (or queue, in this
case).
Chris M. Thomasson
Ahh. I missed the fact that the user data is embedded within the
double-word!
You mean it allows one to access elements in a stack and atomically verifies
that they are still indeed in the stack and NOT in the freelist at the time
of verification right?
Humm, I am not exactly sure if this is very practical or not. Was this
specifically designed for 64-bit machines with DWCAS? AFAICT, this greatly
limits the type of data the user can store in an element.
What am I missing from you're design here Toby?
Chris M. Thomasson
> I've been thinking about lock-free singly linked lists.
> Now the obvious problem is a 21 bit ABA counter. It's too short. But
> what we could do is rather than use a freelist for backing store, use a
> *queue*. That way we have to be unlucky on the ABA counter *and*
> unlucky on the queue. So the chance of our ABA counter failing is 1/2^
> 21. If we put 2^11 elements in the queue, we now effectively have a 32
> bit ABA counter. 2^11 is 2048 elements, which are 2 bytes each, so
> that's 4kb per list - which is pretty acceptable.
>
> Of course, the queue is slower than the freelist - I benchmark M&S'
> queue about 2/3rds the speed of Treibers freelist (on the latest quad
> core ARM running Linux).
What about the ABA counters in the queue itself? Why would a 21-bit counter
be too small for a stack, and be okay for a queue?
> Finally, note the user data is part of the atomic bits. This means when
> we come to read or write the user data, we can in the act of reading or
> writing atomically check the ABA counter is correct - e.g. that the
> element remains valid.
> So - what have I blatantly missed? how does it all fall over? :-)
How would the user process the read data? Within the DWCAS loop, or after
the DWCAS loop succeeds? In either case, the object can be removed and
reused. AFAICT, this design does not prevent a user from operating on
logically deleted data, or operate on inconsistent data because the item was
reused.
Okay, the user got some data from a successful verification process. Now,
what can the user do with that data when it can be logically deleted and/or
reused at any time? Sure the data was in the stack at the time of
verification, but after that all bets are off.
Where am I going wrong here? Could you give a super brief usage example
please?
BTW, try to be patient with me okay?
:^)
Chris M. Thomasson
news:WX51n.12172$_H7....@newsfe24.iad...[...]
>> So - what have I blatantly missed? how does it all fall over? :-)
>
> How would the user process the read data? Within the DWCAS loop, or after
> the DWCAS loop succeeds? In either case, the object can be removed and
> reused. AFAICT, this design does not prevent a user from operating on
> logically deleted data, or operate on inconsistent data because the item
> was reused.
>
> Okay, the user got some data from a successful verification process. Now,
> what can the user do with that data when it can be logically deleted
> and/or reused at any time? Sure the data was in the stack at the time of
> verification, but after that all bets are off.
I guess it would not be wise to store a pointer to an object in an element.
I think I would need to see a legitimate usage example in order to clear my
thoughts Toby.
Toby Douglass
> "Toby Douglass" <a...@b.com> wrote in message
> > The solution in principle is that in all cases, the thread is able,
*in
> > the CAS of verification*, to obtain, or to set, the data it is
> > manipulating - because all of this data exists inside the double-word
> > which is the element and so can all be seen in a single double-word
> > compare-and-swap.
>
> Ahh. I missed the fact that the user data is embedded within the
> double-word!
Yup!
> >> BTW, this is
> >> not meant to be a solution to memory reclamation right?
> >
> > Correct.
>
> > All it does is permit you to use a freelist (or queue, in this
> > case).
>
> You mean it allows one to access elements in a stack and atomically verifies
> that they are still indeed in the stack and NOT in the freelist at the time
> of verification right?
Correct. *Exactly*.
> Humm, I am not exactly sure if this is very practical or not. Was this
> specifically designed for 64-bit machines with DWCAS? AFAICT, this greatly
> limits the type of data the user can store in an element.
It wasn't my aim to target that machine type particularly; what happened
was that I was exploring the line of thought 'well, how can you know
that the element is still valid' and I just went were it took me - and
where it's taken me, right now, this time, is a design which requires 64
bit and DCAS.
Having said that, the fact is, I want a singly linked list which does
not use garbage collection and which does not require memory management,
e.g. no GC and runs off a freelist.
I have no seen such a design in the literature.
> What am I missing from you're design here Toby?
Naaaaaathing. Remember, keep your expectations low, so you're thinking
on the right level to deal with the stuff I come out with :-)
Chris M. Thomasson
news:WX51n.12172$_H7....@newsfe24.iad...
> news:MPG.25adcb375...@text.giganews.com...
>> I've been thinking about lock-free singly linked lists.
> [...]
>> Now the obvious problem is a 21 bit ABA counter. It's too short. But
>> what we could do is rather than use a freelist for backing store, use a
>> *queue*. That way we have to be unlucky on the ABA counter *and*
>> unlucky on the queue. So the chance of our ABA counter failing is 1/2^
>> 21. If we put 2^11 elements in the queue, we now effectively have a 32
>> bit ABA counter. 2^11 is 2048 elements, which are 2 bytes each, so
>> that's 4kb per list - which is pretty acceptable.
>>
>> Of course, the queue is slower than the freelist - I benchmark M&S'
>> queue about 2/3rds the speed of Treibers freelist (on the latest quad
>> core ARM running Linux).
>
> What about the ABA counters in the queue itself? Why would a 21-bit
> counter be too small for a stack, and be okay for a queue?
Are you using the per-element ABA counter in the actual stack anchor?
Something like this:
http://groups.google.com/group/comp.programming.threads/msg/3796240ba6eeaa1c
This definitely reduces the chances of ABA problem. Also, keep in mind that
you do not need to increment the ABA counter in push, and you don't even
need DWCAS in push. However, there are some caveats wrt not using DWCAS in
push:
http://groups.google.com/group/comp.programming.threads/msg/c5004dea42e42aaa
(brief description of the race-condition)
http://groups.google.com/group/comp.programming.threads/msg/95706ec49f3cbc0c
(detailed description of the race-condition and presents several solutions)
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/1e166dc04c3df118/d5c074ce23435ae8
(read all, because it's very interesting thread, well, IMHO of course!)
Toby Douglass
> "Toby Douglass" <a...@b.com> wrote in message
> > Now the obvious problem is a 21 bit ABA counter. It's too short.
But
> > what we could do is rather than use a freelist for backing store, use a
> > *queue*. That way we have to be unlucky on the ABA counter *and*
> > unlucky on the queue. So the chance of our ABA counter failing is 1/2^
> > 21. If we put 2^11 elements in the queue, we now effectively have a 32
> > bit ABA counter. 2^11 is 2048 elements, which are 2 bytes each, so
> > that's 4kb per list - which is pretty acceptable.
> >
> > Of course, the queue is slower than the freelist - I benchmark M&S'
> > queue about 2/3rds the speed of Treibers freelist (on the latest quad
> > core ARM running Linux).
>
> What about the ABA counters in the queue itself? Why would a 21-bit counter
> be too small for a stack, and be okay for a queue?
It's okay - the queue isn't using indexes. It's running off a freelist
and that freelist is using normal DCAS pointer/counter pairs - with full
local pointer length bit widths. The freelist/queue here convert the
pointers into indexes for external users.
> > So - what have I blatantly missed? how does it all fall over? :-)
>
> How would the user process the read data? Within the DWCAS loop, or after
> the DWCAS loop succeeds? In either case, the object can be removed and
> reused. AFAICT, this design does not prevent a user from operating on
> logically deleted data, or operate on inconsistent data because the item was
> reused.
Well, you have a cursor, which points to an element - which is to say,
it contains the index and aba counter of the element it points to.
When you come to read the element the cursor points at, you'll compare
the ABA counter in the cursor to the ABA counter in the element; and the
ABA counter in the element is bumped when the element is logically
deleted. So you can know that the element is valid, since you'll know
the ABA counter is valid.
> Okay, the user got some data from a successful verification process. Now,
> what can the user do with that data when it can be logically deleted and/or
> reused at any time? Sure the data was in the stack at the time of
> verification, but after that all bets are off.
Yes - but that's also true for a lock-based list. If the user reads
*user* data from an element and then deletes that element, what does he
do with the data? that isn't the responsibility of the list.
> Where am I going wrong here? Could you give a super brief usage example
> please?
Let's imagine we have a list in existence. Each element contains its
own ABA counter, the index of the next element, the ABA counter of the
next elmement and the user data. Now imagine we have a cursor pointing
to some element in the list - the cursor contains the index and ABA
counter of the element it points to.
Let's imagine we want to get the user data from the element.
First, we do a non-atomic read of the element, all 128 bits.
We can now do our first check on the ABA counters (we'll do a second
later). If the ABA counter in the cursor differs to the ABA counter in
the element, then we already know the element is invalid; the user data
read fails, because the target element has been deleted.
However, if the ABA counters match, we can now do the atomic DWCAS
check. We prepare an element which we expect to be identical to element
the cursor points at - and we try a DWCAS. If we succeed, *we now have
user data which we know comes from this ABA counter*.
Now let's imagine we want to get the next element.
We have basically the same work to do - except this time, we're not
getting the user data, we're getting the next index and next ABA
counter.
> BTW, try to be patient with me okay?
>
> :^)
lol! I think you're doing an amazing job - I have always found it very,
very hard to comprehend lock-free data structures from written
descriptions. The extent to which you're picking this up and speed with
which you do so is impressive!
Toby Douglass
> I guess it would not be wise to store a pointer to an object in an
element.
> I think I would need to see a legitimate usage example in order to clear my
> thoughts Toby.
I'm implementing ATM - if it works (big if) it'll be in the next liblfds
release.
Toby Douglass
> Are you using the per-element ABA counter in the actual stack anchor?
> Something like this:
>
> http://groups.google.com/group/comp.programming.threads/msg/3796240ba6eeaa1c
No - but it's possible; the list elements could each contain an ABA
counter. That would be nice - then there's no 2^11 minimum element
count requirement.
The worse case, as far as I can think of, is a freelist, with a single
element being repeatedly popped and pushed. That way you have the same
single pointer and you just need to get unlucky on the ABA counter. A
per-element ABA counter here won't improve your chances. It does
improve your chances in all other cases.
> This definitely reduces the chances of ABA problem. Also, keep in mind that
> you do not need to increment the ABA counter in push,
That's new to me - but let me think; I think I see. It's about not
needing to increment on pop *and* push - it's wasted effort. You only
need to do it on one of them; e.g. if you exit the list and you've
incremented then, you've *already* incremented the counter. Why do it a
second time when you re-enter the list?
> and you don't even
> need DWCAS in push.
Now that IS news to me. Clarification please - to begin with, do you
mean for example with Treibers freelist? you mean you can add new
elements to the freelist without atomic compare-and-swap?
> However, there are some caveats wrt not using DWCAS in
> push:
>
> http://groups.google.com/group/comp.programming.threads/msg/c5004dea42e42aaa
> (brief description of the race-condition)
>
> http://groups.google.com/group/comp.programming.threads/msg/95706ec49f3cbc0c
> (detailed description of the race-condition and presents several solutions)
>
> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/1e166dc04c3df118/d5c074ce23435ae8
> (read all, because it's very interesting thread, well, IMHO of course!)
Right - I need some time to understand these and it's bed time!
I shall reply again when I've read them.
Dmitriy Vyukov
> > How would the user process the read data? Within the DWCAS loop, or after
> > the DWCAS loop succeeds? In either case, the object can be removed and
> > reused. AFAICT, this design does not prevent a user from operating on
> > logically deleted data, or operate on inconsistent data because the item was
> > reused.
>
> Well, you have a cursor, which points to an element - which is to say,
> it contains the index and aba counter of the element it points to.
>
> When you come to read the element the cursor points at, you'll compare
> the ABA counter in the cursor to the ABA counter in the element; and the
> ABA counter in the element is bumped when the element is logically
> deleted. So you can know that the element is valid, since you'll know
> the ABA counter is valid.
>
> > Okay, the user got some data from a successful verification process. Now,
> > what can the user do with that data when it can be logically deleted and/or
> > reused at any time? Sure the data was in the stack at the time of
> > verification, but after that all bets are off.
>
> Yes - but that's also true for a lock-based list. If the user reads
> *user* data from an element and then deletes that element, what does he
> do with the data? that isn't the responsibility of the list.
Hi Toby,
Humm... probably you underestimate the issue. With lock-based list
iteration over a list and removal of elements are mutually exclusive.
With lock-free list iteration and removal are concurrent. So it may be
the case that user data is a pointer to same external object, one
thread processes the external object, and other thread concurrently
removes the element and deletes the external object. Total mess.
Program will crash at best.
With TSM (freelist) and ABA counters you protect and ensure
consistency only of your nodes, but you have to do the same for user
data (external object pointer to which stored in your node) too.
Otherwise the data structure is basically useless, user wants to work
with inconsistent/deleted data even less then you do.
You can overcome this by moving user processing inside of DWCAS-loop
(as Chris suggested). But then it will be a kind of SeqLock protected
data with all the consequences.
--
Dmitriy V'jukov
Dmitriy Vyukov
If you use ABA-counters for protection, then it's reasonable to think
as if each and every pointer (either contained within shared structure
or in thread-local iterator) is a set of:
struct POINTER
{
void* ptr;
uintptr_t version;
};
Raw pointer (w\o version) in such scheme is senseless.
Now it's obvious where ABA-counters must be placed - with each and
every pointer.
I do not think that you need to pack all that stuff:
> 1. our ABA counter (21 bits)
> 2. pointer to next (21 bits)
> 3. ABA counter of next (21 bits)
> 4. user data (64 bits)
into single atomic variable.
Only pointer+counter must be operable atomically.
Algorithm for iteration is:
// load list head
node_t* next_ptr = ...;
unsigned next_ver = ...;
begin:
node_t* next_next_ptr = next_ptr->next_ptr;
unsigned next_next_ver = next_ptr->next_ver;
T user_data = next_ptr->data;
// verify consistency of previously read vars
if (next_ptr->ver != next_ver)
goto elsewhere;
// here we know that read vars are (was) consistent
process(user_data); // here user data may be already inconsistent
(issue raised by Chris)
next_ptr = next_next_ptr;
next_ver = next_next_ver;
goto begin;
When you need to remove node, you just bump it's ABA counter. When you
will reuse the node, you will install pointer to it along with new
version.
It's actually a SeqLock, with the exception that you read version in
one place (along with pointer to node), and verify it with a version
stored in another place (node itself). Between the read and the
verification you can read arbitrary amount of other data (here: next
pointer, next version, user data), and you are sure that all read data
is consistent (if verification succeeds, of course).
--
Dmitriy V'jukov
Toby Douglass
> On Jan 7, 12:11ï¿œam, Toby Douglass <a...@b.com> wrote:
> > CT wrote:
> > > Okay, the user got some data from a successful verification
process. Now,
> > > what can the user do with that data when it can be logically deleted and/or
> > > reused at any time? Sure the data was in the stack at the time of
> > > verification, but after that all bets are off.
> >
> > Yes - but that's also true for a lock-based list. ï¿œIf the user reads
> > *user* data from an element and then deletes that element, what does he
> > do with the data? ï¿œthat isn't the responsibility of the list.
> Humm... probably you underestimate the issue. With lock-based list
> iteration over a list and removal of elements are mutually exclusive.
> With lock-free list iteration and removal are concurrent. So it may be
> the case that user data is a pointer to same external object, one
> thread processes the external object, and other thread concurrently
> removes the element and deletes the external object. Total mess.
> Program will crash at best.
In the design I've described, obtaining the user data in an element is
atomic. So *strictly*, you can't bomb because of it; if your thread was
able to get the user data, *it was there and was valid and was supposed
to be visible*, at the instant you obtained it.
Of course, it might be that one instruction later, it was deleted.
But that seems to me to be inherent behaviour in a non-reference
counting list. The user has to understand that it is so, when he comes
to use the API. The only way I can see to avoid avoid this is with
reference counting.
> With TSM (freelist) and ABA counters you protect and ensure
> consistency only of your nodes, but you have to do the same for user
> data (external object pointer to which stored in your node) too.
> Otherwise the data structure is basically useless, user wants to work
> with inconsistent/deleted data even less then you do.
As far as I can see, this requirement is met.
> You can overcome this by moving user processing inside of DWCAS-loop
> (as Chris suggested). But then it will be a kind of SeqLock protected
> data with all the consequences.
I didn't pick that up from Chris' post, not yet - but them I'm still
reading through the links and digesting.
However, you appreciate that the user data is part of the atomic data
and as such, it's validity is correct - you can only obtain user data
which is, at the instant you obtain it, valid.
Toby Douglass
> On Jan 6, 12:19ï¿œam, Toby Douglass <a...@b.com> wrote:
> > Our element then might look like this;
> >
> > 1. our ABA counter (21 bits)
> > 2. pointer to next (21 bits)
> > 3. ABA counter of next (21 bits)
> > 4. user data (64 bits)
> >
> > And the cursor like this;
> >
> > 1. pointer to current element (32 bits)
> > 2. ABA of current element (32 bits)
>
> If you use ABA-counters for protection, then it's reasonable to think
> as if each and every pointer (either contained within shared structure
> or in thread-local iterator) is a set of:
>
> struct POINTER
> {
> void* ptr;
> uintptr_t version;
> };
Yes. In my head I have also been thinking of the ABA counters as
version counters. (And this I think must be starting to be close to a
smart pointer? but I've not really read up on exactly what/how they do
whatever it is that they do).
> Raw pointer (w\o version) in such scheme is senseless.
Yes. You can't know if what you point at is valid without accessing it,
and if you access it when it's not valid, problems.
> Now it's obvious where ABA-counters must be placed - with each and
> every pointer.
Yes.
> I do not think that you need to pack all that stuff:
> > 1. our ABA counter (21 bits)
> > 2. pointer to next (21 bits)
> > 3. ABA counter of next (21 bits)
> > 4. user data (64 bits)
> into single atomic variable.
I have been wondering about this also, with mixed thoughts...right now
I've been working on implementing the idea I currently have, to make
sure it works, and then evolving it some more. As I've been
implementing it, there have been places where it's been apparent to me
there are possibilities for non-atomic data storage, which might permit
less information having to be stored in our atomic bits.
> Only pointer+counter must be operable atomically.
> Algorithm for iteration is:
>
> // load list head
> node_t* next_ptr = ...;
> unsigned next_ver = ...;
>
> begin:
> node_t* next_next_ptr = next_ptr->next_ptr;
> unsigned next_next_ver = next_ptr->next_ver;
> T user_data = next_ptr->data;
>
> // verify consistency of previously read vars
> if (next_ptr->ver != next_ver)
> goto elsewhere;
>
> // here we know that read vars are (was) consistent
>
> process(user_data); // here user data may be already inconsistent
> (issue raised by Chris)
Yeee-e-e-s-s-s...no, wait. No?
I'll have to re-read Chris' comment.
I mean, you read the user data before you checked the version numbers;
if they do match, your user data - well, it might have changed since
then, but you certainly obtained *a* valid user data, the one correct at
the time. You can reduce this problem away by making the user data
atomic along with the version counter, so you get them together, but I
was wondering if it was really necessary. If you give it up, you don't
have to be atomic in the get_user_data() function.
> next_ptr = next_next_ptr;
> next_ver = next_next_ver;
> goto begin;
>
> When you need to remove node, you just bump it's ABA counter. When you
> will reuse the node, you will install pointer to it along with new
> version.
Yes.
> It's actually a SeqLock,
Something I've not heard of.
> with the exception that you read version in
> one place (along with pointer to node), and verify it with a version
> stored in another place (node itself). Between the read and the
> verification you can read arbitrary amount of other data (here: next
> pointer, next version, user data), and you are sure that all read data
> is consistent (if verification succeeds, of course).
Indeed so - and I see this behaviour used in the M&S queue, for example.
However, where I've been dreaming this up from scratch and I'm not so
experienced in lock-free, I've been mentally sufficiently loaded that
these extra ideas haven't had room :-)
Once I get the basic list working, then there will be considerable
redesign - this idea seems almost certain to get in, which would I think
remove the need for contigious double-word CAS.
One thing I realised yesterday was that I had misunderstood Harris'
delete bit - which isn't surprising, since I'd not actually had to think
about it's use with a view to implementing it. I now see that it will
be required. What I said before was that you could bump the ABA
counter; I meant of the element *being deleted*. This isn't much use, I
think - if you're on an element and you want to delete what it points
to, inbetween the act of getting the next element and bumping its
counter, any number of elements might be inserted after the element
you're on. Harris' delete bit is of course *in* the element which
*points* at the element which is to be deleted; it it your single stroke
where by you prevent insertions at that element.
Dmitriy Vyukov
> dvyu...@gmail.com wrote:
> > On Jan 7, 12:11 am, Toby Douglass <a...@b.com> wrote:
> > > CT wrote:
> > > > Okay, the user got some data from a successful verification
> process. Now,
> > > > what can the user do with that data when it can be logically deleted and/or
> > > > reused at any time? Sure the data was in the stack at the time of
> > > > verification, but after that all bets are off.
>
> > > *user* data from an element and then deletes that element, what does he
> > Humm... probably you underestimate the issue. With lock-based list
> > iteration over a list and removal of elements are mutually exclusive.
> > With lock-free list iteration and removal are concurrent. So it may be
> > the case that user data is a pointer to same external object, one
> > thread processes the external object, and other thread concurrently
> > removes the element and deletes the external object. Total mess.
> > Program will crash at best.
>
> In the design I've described, obtaining the user data in an element is
> atomic. So *strictly*, you can't bomb because of it; if your thread was
> able to get the user data, *it was there and was valid and was supposed
> to be visible*, at the instant you obtained it.
>
> Of course, it might be that one instruction later, it was deleted.
>
> But that seems to me to be inherent behaviour in a non-reference
> counting list. The user has to understand that it is so, when he comes
> to use the API. The only way I can see to avoid avoid this is with
> reference counting.
But do you see any useful application for a list with such semantics?
Basically you are saying to a user "data passed your callback may be
valid/invalid/in process of destruction/in process of construction/
unmapped from address space/whatever", and what a user is supposed to
do?
Yes, this can be avoided with reference counting (or any other form of
safe memory reclamation/garbage collection).
> > You can overcome this by moving user processing inside of DWCAS-loop
> > (as Chris suggested). But then it will be a kind of SeqLock protected
> > data with all the consequences.
>
> I didn't pick that up from Chris' post, not yet - but them I'm still
> reading through the links and digesting.
>
> However, you appreciate that the user data is part of the atomic data
> and as such, it's validity is correct - you can only obtain user data
> which is, at the instant you obtain it, valid.
And what value in obtaining consistent data?
There must easier way to achieve such semantics - generate random
trash each time. As far as I see, from user point of view, it will be
exactly the same. No?
--
Dmitriy V'jukov
Toby Douglass
> dvy...@gmail.com wrote:
> > I do not think that you need to pack all that stuff:
> > > 1. our ABA counter (21 bits)
> > > 2. pointer to next (21 bits)
> > > 3. ABA counter of next (21 bits)
> > > 4. user data (64 bits)
> > into single atomic variable.
>
> I have been wondering about this also, with mixed thoughts...right now
> I've been working on implementing the idea I currently have, to make
> sure it works, and then evolving it some more. As I've been
> implementing it, there have been places where it's been apparent to me
> there are possibilities for non-atomic data storage, which might permit
> less information having to be stored in our atomic bits.
Actually, I realised; the big difference is that you become viable on a
32 bit platform. You still need DWCAS on that platform, but all the
same - your ABA lengths are now long enough you're viable.
Toby Douglass
> On Jan 9, 3:22ï¿œam, Toby Douglass <a...@b.com> wrote:
> > In the design I've described, obtaining the user data in an element
is
> > atomic. ï¿œSo *strictly*, you can't bomb because of it; if your thread was
> > able to get the user data, *it was there and was valid and was supposed
> > to be visible*, at the instant you obtained it.
> >
> > Of course, it might be that one instruction later, it was deleted.
> >
> > But that seems to me to be inherent behaviour in a non-reference
> > counting list. ï¿œThe user has to understand that it is so, when he comes
> > to use the API. ï¿œThe only way I can see to avoid avoid this is with
> > reference counting.
>
> But do you see any useful application for a list with such semantics?
> Basically you are saying to a user "data passed your callback may be
> valid/invalid/in process of destruction/in process of construction/
> unmapped from address space/whatever", and what a user is supposed to
> do?
Organise his data so this doesn't happen. Arrange matters so when you
come to delete an item, you do it in a time and at a place where you
know no-one else will be using that item. That's a design restriction
imposed upon you by using a lock-free data structure.
It seems to me to be the equivelent of a lock-based list, with reference
counting, where the usage domain is that which consists of situations
where you never need to use the reference counting; you add elements to
the list and when you're done with an element, you know no one else will
be using it (by that I mean, using the user data, as opposed to having a
cursor which happens to be passing through that element, which would
also raise the ref count).
> Yes, this can be avoided with reference counting (or any other form of
> safe memory reclamation/garbage collection).
I'm under the impression reference counting is a big no-no, because of
the performance hit.
GC would work, because the state the void pointer of user data points at
will remain until the user gives up his pointer to it; but I am looking
not to use GC at all.
Safe memory reclamation in that context seems to me to be like GC, I
think?
> > > You can overcome this by moving user processing inside of DWCAS-
loop
> > > (as Chris suggested). But then it will be a kind of SeqLock protected
> > > data with all the consequences.
> >
> > I didn't pick that up from Chris' post, not yet - but them I'm still
> > reading through the links and digesting.
> >
> > However, you appreciate that the user data is part of the atomic data
> > and as such, it's validity is correct - you can only obtain user data
> > which is, at the instant you obtain it, valid.
>
> And what value in obtaining consistent data?
> There must easier way to achieve such semantics - generate random
> trash each time. As far as I see, from user point of view, it will be
> exactly the same. No?
I think I see now what Chris means about moving the user processing into
the DWCAS loop. I think I can see also what you mean; in a heavily
concurrent environment, where many threads are often concurrently
accessing user data in a given element, where there is no clear point at
which no more threads will be accessing a given element, it is not
possible to have a single thread be in a position where the user can
know that thread is the final accessor of the user data, who can do the
delete.
I'm thinking you could have a reference counter which you atomically
bump when you read the user data (DWCAS again) and atomically decrement
when you're done with the user data; the deletion of the element from
the list would be seperated from the deallocation of the user data,
which would only happen once the element is out of the list and the ref
counter hits 0.
This would mean when you delete an element from the list, it goes back
not into the main freelist, but into a second singly linked list, which
consists of elements which still have readers on their user data.
(I'm writing this off the cuff; I'd have to see if I can really arrange
for the behaviour described here to be atomic).
That second linked list could of the simpler type, where we do not have
reference counting on user data, because there will be only a single
final accessor - the thread which decrements the ref count to zero.
So in fact this list design described in previous posts because a
backing-store list, which you need for a proper singly linked list.
I suspect I'm starting to wander into the general area of safe memory
reclaimation here.
Dmitriy Vyukov
> dvyu...@gmail.com wrote:
> > On Jan 9, 3:22 am, Toby Douglass <a...@b.com> wrote:
> > > In the design I've described, obtaining the user data in an element
> is
> > > able to get the user data, *it was there and was valid and was supposed
> > > to be visible*, at the instant you obtained it.
>
> > > Of course, it might be that one instruction later, it was deleted.
>
> > > But that seems to me to be inherent behaviour in a non-reference
> > > to use the API. The only way I can see to avoid avoid this is with
> > > reference counting.
>
> > But do you see any useful application for a list with such semantics?
> > Basically you are saying to a user "data passed your callback may be
> > valid/invalid/in process of destruction/in process of construction/
> > unmapped from address space/whatever", and what a user is supposed to
> > do?
>
> Organise his data so this doesn't happen. Arrange matters so when you
> come to delete an item, you do it in a time and at a place where you
> know no-one else will be using that item. That's a design restriction
> imposed upon you by using a lock-free data structure.
Well, it makes sense.
It substantially limits applicability, though. And note that handling
of consistency of your internal nodes and user data is effectively a
single problem. If you allow only such usages (where there are
application level quiescence points where it's safe to reclaim user
data objects), then it's reasonable to reclaim your internal nodes at
those points too. Then you do not need to cope with all these ABA
counters and DWCASes, etc, just provide compact() method in which you
will reclaim all previously removed nodes. Simple. Your node occupies
only few words, and it's reasonable to assume that user object is
larger; so if user allows to live N superfluous objects then he is Ok
with N superfluous list nodes too.
--
Dmitriy V'jukov
Dmitriy Vyukov
> > Yes, this can be avoided with reference counting (or any other form of
> > safe memory reclamation/garbage collection).
>
> I'm under the impression reference counting is a big no-no, because of
> the performance hit.
Well, if you are going to issue DWCAS on shared location per node then
you are already there anyway.
> GC would work, because the state the void pointer of user data points at
> will remain until the user gives up his pointer to it; but I am looking
> not to use GC at all.
>
> Safe memory reclamation in that context seems to me to be like GC, I
> think?
Yes, in this context I use terms GC and SMR as a synonyms.
Why you are trying to avoid "GC"?
--
Dmitriy V'jukov
Dmitriy Vyukov
> I think I see now what Chris means about moving the user processing into
> the DWCAS loop. I think I can see also what you mean; in a heavily
> concurrent environment, where many threads are often concurrently
> accessing user data in a given element, where there is no clear point at
> which no more threads will be accessing a given element, it is not
> possible to have a single thread be in a position where the user can
> know that thread is the final accessor of the user data, who can do the
> delete.
Indeed. For example, consider server application with a bunch of
worker threads. Each worker thread constantly accesses some shared
data structures. There are no special safe points for the whole
duration of work.
--
Dmitriy V'jukov
Toby Douglass
> On 9 ???, 14:47, Toby Douglass <a...@b.com> wrote:
> > Safe memory reclamation in that context ï¿œseems to me to be like GC,
I
> > think?
>
> Yes, in this context I use terms GC and SMR as a synonyms.
> Why you are trying to avoid "GC"?
GC is often unavailable. So I think if you write for GC, you limit
applicability.
Toby Douglass
> On 9 ???, 14:47, Toby Douglass <a...@b.com> wrote:
> > Organise his data so this doesn't happen. ï¿œArrange matters so when
you
> > come to delete an item, you do it in a time and at a place where you
> > know no-one else will be using that item. ï¿œThat's a design restriction
> > imposed upon you by using a lock-free data structure.
>
> Well, it makes sense.
> It substantially limits applicability, though.
Yup. I hadn't fully appreciated how much so. It's useful in situations
where lock-free is what matters (interrupt handlers, etc). It's not
useful in situations where you have intensive use.
> And note that handling
> of consistency of your internal nodes and user data is effectively a
> single problem. If you allow only such usages (where there are
> application level quiescence points where it's safe to reclaim user
> data objects), then it's reasonable to reclaim your internal nodes at
> those points too. Then you do not need to cope with all these ABA
> counters and DWCASes, etc, just provide compact() method in which you
> will reclaim all previously removed nodes. Simple. Your node occupies
> only few words, and it's reasonable to assume that user object is
> larger; so if user allows to live N superfluous objects then he is Ok
> with N superfluous list nodes too.
Need to think this through (mainly thinking about what you said about
not needing ADA/DWCAS...). Reply in due course.
Dmitriy Vyukov
> > Algorithm for iteration is:
>
> > // load list head
> > node_t* next_ptr = ...;
> > unsigned next_ver = ...;
>
> > begin:
> > node_t* next_next_ptr = next_ptr->next_ptr;
> > unsigned next_next_ver = next_ptr->next_ver;
> > T user_data = next_ptr->data;
>
> > // verify consistency of previously read vars
> > if (next_ptr->ver != next_ver)
> > goto elsewhere;
>
> > // here we know that read vars are (was) consistent
>
> > process(user_data); // here user data may be already inconsistent
> > (issue raised by Chris)
>
> Yeee-e-e-s-s-s...no, wait. No?
>
> I'll have to re-read Chris' comment.
>
> I mean, you read the user data before you checked the version numbers;
> if they do match, your user data - well, it might have changed since
> then, but you certainly obtained *a* valid user data, the one correct at
> the time. You can reduce this problem away by making the user data
> atomic along with the version counter, so you get them together, but I
> was wondering if it was really necessary. If you give it up, you don't
> have to be atomic in the get_user_data() function.
In what way it (atomic read of user data along with version counter)
reduces the problem?
>
> > next_ptr = next_next_ptr;
> > next_ver = next_next_ver;
> > goto begin;
>
> > When you need to remove node, you just bump it's ABA counter. When you
> > will reuse the node, you will install pointer to it along with new
> > version.
>
> Yes.
>
> > It's actually a SeqLock,
>
> Something I've not heard of.
http://en.wikipedia.org/wiki/Seqlock
> > with the exception that you read version in
> > one place (along with pointer to node), and verify it with a version
> > stored in another place (node itself). Between the read and the
> > verification you can read arbitrary amount of other data (here: next
> > pointer, next version, user data), and you are sure that all read data
> > is consistent (if verification succeeds, of course).
>
> Indeed so - and I see this behaviour used in the M&S queue, for example.
> However, where I've been dreaming this up from scratch and I'm not so
> experienced in lock-free, I've been mentally sufficiently loaded that
> these extra ideas haven't had room :-)
>
> Once I get the basic list working, then there will be considerable
> redesign - this idea seems almost certain to get in, which would I think
> remove the need for contigious double-word CAS.
>
> One thing I realised yesterday was that I had misunderstood Harris'
> delete bit - which isn't surprising, since I'd not actually had to think
> about it's use with a view to implementing it. I now see that it will
> be required. What I said before was that you could bump the ABA
> counter; I meant of the element *being deleted*. This isn't much use, I
> think - if you're on an element and you want to delete what it points
> to, inbetween the act of getting the next element and bumping its
> counter, any number of elements might be inserted after the element
> you're on. Harris' delete bit is of course *in* the element which
> *points* at the element which is to be deleted; it it your single stroke
> where by you prevent insertions at that element.
There is 2 "levels" of "lock-free". (1) lock-free readers, (2) totally
lock-free.
On level (1) one just says that all mutation operations have to be
performed under a mutex, i.e. one does not have to implement lock-free
synchronization between writers, however lock-free synchronization
between writer and readers have to be implemented. Level (1) is enough
sometimes, because some real-life problems have high read-to-write
ratio, and frequently mutated shared data structure can not be fast
and scalable no matter how one will implement it (at least on current
x86 hardware).
So one choice if to implement only lock-free readers, then you do not
need delete bit (no concurrent mutators). ABA counters still required,
because they provide synchronization between writer and readers.
Another choice is to implement lock-free readers and writers. Then you
delete bit too, because they are required for writer-writer
synchronization.
--
Dmitriy V'jukov
Dmitriy Vyukov
> I wrote:
Well, that is nice side effect too :)
Also note that some 64-bit systems do not feature double-word CAS. So
you will have hard time packing 4 variables into single 64-bit word.
Pointer+counter is easier to pack, for example on 64-bit Windows
system you may pack pointer into 39 bits, this leaves 25 bits for ABA
counter (which is not all that bad, previous version of Microsoft
SList API uses only 9-bit ABA counter).
Humm... and of course, just why pack 4 vars when 2 is enough? :)
--
Dmitriy V'jukov
Dmitriy Vyukov
> you
> > > come to delete an item, you do it in a time and at a place where you
> > > imposed upon you by using a lock-free data structure.
>
> > Well, it makes sense.
> > It substantially limits applicability, though.
>
> Yup. I hadn't fully appreciated how much so. It's useful in situations
> where lock-free is what matters (interrupt handlers, etc). It's not
> useful in situations where you have intensive use.
There are 2 kinds of intensive use: (1) high write rate, (2) high read
rate.
As for (1), lock-free indeed does not make much sense performance-
wise. However, as for (2), smart lock-free design can make huge sense
performance-wise (IIRC Paul McKenney reported 500x speedup for some
subsystem in Linux kernel on 32-way system). Assume that lock-free
list is a list of active CPUs in a system, or a list of directories in
a filesystem, or a list of users of some system. They can be accessed
in each transaction, but changes once in a hour/day/month. IMVHO
that's where lock-free matters (I just do not write interrupt
handlers).
--
Dmitriy V'jukov
Dmitriy Vyukov
> I
> > > think?
>
> > Yes, in this context I use terms GC and SMR as a synonyms.
> > Why you are trying to avoid "GC"?
>
> GC is often unavailable. So I think if you write for GC, you limit
> applicability.
Well, C/C++ do not feature built-in reference-counting too (especially
multithreading safe)... and XML processing, and network communication,
and...
I meant that you can built your own SMR system. Then all that problems
like pointer packing, ABA counters, requirement to have double-word
CAS, freelists, inconsistent data, performance destroying per-element
atomic RMW, limited applicability (periodic application level
quiescence points), etc-etc will just go away.
--
Dmitriy V'jukov
Dmitriy Vyukov
What are you going to do if ABA counter verification fails?
You can return to the previous element and try to re-read next
pointer, but the previous element can also become invalid now. You can
return to previous-previous element, but it can also become invalid...
You can restart from the beginning, but then how to determine already
visited elements? Anyway this can lead to livelock and be too costly.
I do not see good ways to handle this... What I am missing? What
mentioned authors write about this?
--
Dmitriy V'jukov
Toby Douglass
> On Jan 6, 12:19ï¿œam, Toby Douglass <a...@b.com> wrote:
> > So that gives us the following requirement in a cursor;
> >
> > 1. pointer to current element
> > 2. ABA of current element
>
> What are you going to do if ABA counter verification fails?
You're out. The element your cursor was looking at has been deleted.
This is part of arranging your data use to account for the limitations
of the data structure; only delete an element when you're done with it.
I'm almost embarrassed about this now, actually; really, it's not
parallal at all. It's almost a single-threaded list, implemented using
lock-free semantics. Useful for interrupt/event handlers only.
Basically, I'd not really thought through fully the implications of the
limitations I was expecting to place on the user and his use of the data
structure.
> You can return to the previous element and try to re-read next
> pointer, but the previous element can also become invalid now. You can
> return to previous-previous element, but it can also become invalid...
> You can restart from the beginning, but then how to determine already
> visited elements? Anyway this can lead to livelock and be too costly.
> I do not see good ways to handle this... What I am missing?
Nothing; you're merely experiencing expectation/reality mismatch :-)