Why SynchronousQueue.TransferQueue#clean() not clean the last node

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
        void clean(QNode pred, QNode s) {
            s.waiter = null; // forget thread
            while (pred.next == s) { 
                QNode h = head;
                QNode hn = h.next;   
                if (hn != null && hn.isCancelled()) {
                    advanceHead(h, hn);
                    continue;
                }
                QNode t = tail;      
                if (t == h)
                    return;
                QNode tn = t.next;
                if (t != tail)
                    continue;
                if (tn != null) {
                    advanceTail(t, tn);
                    continue;
                }
                if (s != t) {        // If not tail, try to unsplice
                    QNode sn = s.next;
                    if (sn == s || pred.casNext(s, sn))
                        return;
                }
                QNode dp = cleanMe;
                if (dp != null) {    
                    QNode d = dp.next;
                    QNode dn;
                    if (d == null ||               // d is gone or
                        d == dp ||                 // d is off list or
                        !d.isCancelled() ||        // d not cancelled or
                        (d != t &&                 // d not tail and
                         (dn = d.next) != null &&  //   has successor
                         dn != d &&                //   that is on list
                         dp.casNext(d, dn)))       // d unspliced
                        casCleanMe(dp, null);
                    if (dp == pred)
                        return;      
                } else if (casCleanMe(null, pred))
                    return;         
            }
        }

From above code, we can see that only if s is not tail, s will be cleaned in this invocation.
If s is tail, s will NOT be cleaned in this invocation.
Why to do this? Is there a situation we must avoid.

--------------------------------------------------------------------------------
Regards
Liu

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
Probably no one has carefully looked at that code in a decade.

Usually unsplicing nodes from linked lists helps reclaim resources,
but is not necessary for algorithm correctness.

On Fri, Aug 14, 2020 at 8:15 PM Liu via Concurrency-interest
<[hidden email]> wrote:

>
>         void clean(QNode pred, QNode s) {
>             s.waiter = null; // forget thread
>             while (pred.next == s) {
>                 QNode h = head;
>                 QNode hn = h.next;
>                 if (hn != null && hn.isCancelled()) {
>                     advanceHead(h, hn);
>                     continue;
>                 }
>                 QNode t = tail;
>                 if (t == h)
>                     return;
>                 QNode tn = t.next;
>                 if (t != tail)
>                     continue;
>                 if (tn != null) {
>                     advanceTail(t, tn);
>                     continue;
>                 }
>                 if (s != t) {        // If not tail, try to unsplice
>                     QNode sn = s.next;
>                     if (sn == s || pred.casNext(s, sn))
>                         return;
>                 }
>                 QNode dp = cleanMe;
>                 if (dp != null) {
>                     QNode d = dp.next;
>                     QNode dn;
>                     if (d == null ||               // d is gone or
>                         d == dp ||                 // d is off list or
>                         !d.isCancelled() ||        // d not cancelled or
>                         (d != t &&                 // d not tail and
>                          (dn = d.next) != null &&  //   has successor
>                          dn != d &&                //   that is on list
>                          dp.casNext(d, dn)))       // d unspliced
>                         casCleanMe(dp, null);
>                     if (dp == pred)
>                         return;
>                 } else if (casCleanMe(null, pred))
>                     return;
>             }
>         }
>
> From above code, we can see that only if s is not tail, s will be cleaned in this invocation.
> If s is tail, s will NOT be cleaned in this invocation.
> Why to do this? Is there a situation we must avoid.
>
> --------------------------------------------------------------------------------
> Regards
> Liu
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
If you formulate the correct state of the list after s == tail removed, you may be able to see the difficulty with removing it.


Alex

On Sat, 15 Aug 2020, 04:15 Liu via Concurrency-interest, <[hidden email]> wrote:
        void clean(QNode pred, QNode s) {
            s.waiter = null; // forget thread
            while (pred.next == s) { 
                QNode h = head;
                QNode hn = h.next;   
                if (hn != null && hn.isCancelled()) {
                    advanceHead(h, hn);
                    continue;
                }
                QNode t = tail;      
                if (t == h)
                    return;
                QNode tn = t.next;
                if (t != tail)
                    continue;
                if (tn != null) {
                    advanceTail(t, tn);
                    continue;
                }
                if (s != t) {        // If not tail, try to unsplice
                    QNode sn = s.next;
                    if (sn == s || pred.casNext(s, sn))
                        return;
                }
                QNode dp = cleanMe;
                if (dp != null) {    
                    QNode d = dp.next;
                    QNode dn;
                    if (d == null ||               // d is gone or
                        d == dp ||                 // d is off list or
                        !d.isCancelled() ||        // d not cancelled or
                        (d != t &&                 // d not tail and
                         (dn = d.next) != null &&  //   has successor
                         dn != d &&                //   that is on list
                         dp.casNext(d, dn)))       // d unspliced
                        casCleanMe(dp, null);
                    if (dp == pred)
                        return;      
                } else if (casCleanMe(null, pred))
                    return;         
            }
        }

From above code, we can see that only if s is not tail, s will be cleaned in this invocation.
If s is tail, s will NOT be cleaned in this invocation.
Why to do this? Is there a situation we must avoid.

--------------------------------------------------------------------------------
Regards
Liu
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
Yes. There is an unspoken invariant that head and tail make progress in one direction. That is pretty much the only way to make sure the head never passes the tail. Then deleting tail cannot be done without moving the tail backwards to pred. This breaks the unspoken invariant in the presence of concurrent modifications of head.

Alex

On Sat, 15 Aug 2020, 07:18 Liu, <[hidden email]> wrote:
Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
I did more work on ConcurrentLinkedQueue, including recording the
invariants, notably:

     * Invariants:
     * - all live nodes are reachable from head via succ()
     * - head != null
     * - (tmp = head).next != tmp || tmp != head
     * Non-invariants:
     * - head.item may or may not be null.
     * - it is permitted for tail to lag behind head, that is, for tail
     *   to not be reachable from head!

On Fri, Aug 14, 2020 at 11:23 PM Alex Otenko via Concurrency-interest
<[hidden email]> wrote:

>
> Yes. There is an unspoken invariant that head and tail make progress in one direction. That is pretty much the only way to make sure the head never passes the tail. Then deleting tail cannot be done without moving the tail backwards to pred. This breaks the unspoken invariant in the presence of concurrent modifications of head.
>
> Alex
>
> On Sat, 15 Aug 2020, 07:18 Liu, <[hidden email]> wrote:
>>
>> Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
Great. But still head and tail point to nodes in the same chain, right?

Alex

On Sat, 15 Aug 2020, 08:02 Martin Buchholz, <[hidden email]> wrote:
I did more work on ConcurrentLinkedQueue, including recording the
invariants, notably:

     * Invariants:
     * - all live nodes are reachable from head via succ()
     * - head != null
     * - (tmp = head).next != tmp || tmp != head
     * Non-invariants:
     * - head.item may or may not be null.
     * - it is permitted for tail to lag behind head, that is, for tail
     *   to not be reachable from head!

On Fri, Aug 14, 2020 at 11:23 PM Alex Otenko via Concurrency-interest
<[hidden email]> wrote:
>
> Yes. There is an unspoken invariant that head and tail make progress in one direction. That is pretty much the only way to make sure the head never passes the tail. Then deleting tail cannot be done without moving the tail backwards to pred. This breaks the unspoken invariant in the presence of concurrent modifications of head.
>
> Alex
>
> On Sat, 15 Aug 2020, 07:18 Liu, <[hidden email]> wrote:
>>
>> Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
On Sat, Aug 15, 2020 at 1:24 AM Alex Otenko <[hidden email]> wrote:
>
> Great. But still head and tail point to nodes in the same chain, right?

java.util.concurrent is where data structure intuition goes to die.

    /**
     * A node from which the last node on list (that is, the unique
     * node with node.next == null) can be reached in O(1) time.
     * Invariants:
     * - the last node is always reachable from tail via succ()
     * - tail != null
     * Non-invariants:
     * - tail.item may or may not be null.
     * - it is permitted for tail to lag behind head, that is, for tail
     *   to not be reachable from head!
     * - tail.next may or may not be self-linked.
     */
    private transient volatile Node<E> tail;


>
> Alex
>
> On Sat, 15 Aug 2020, 08:02 Martin Buchholz, <[hidden email]> wrote:
>>
>> I did more work on ConcurrentLinkedQueue, including recording the
>> invariants, notably:
>>
>>      * Invariants:
>>      * - all live nodes are reachable from head via succ()
>>      * - head != null
>>      * - (tmp = head).next != tmp || tmp != head
>>      * Non-invariants:
>>      * - head.item may or may not be null.
>>      * - it is permitted for tail to lag behind head, that is, for tail
>>      *   to not be reachable from head!
>>
>> On Fri, Aug 14, 2020 at 11:23 PM Alex Otenko via Concurrency-interest
>> <[hidden email]> wrote:
>> >
>> > Yes. There is an unspoken invariant that head and tail make progress in one direction. That is pretty much the only way to make sure the head never passes the tail. Then deleting tail cannot be done without moving the tail backwards to pred. This breaks the unspoken invariant in the presence of concurrent modifications of head.
>> >
>> > Alex
>> >
>> > On Sat, 15 Aug 2020, 07:18 Liu, <[hidden email]> wrote:
>> >>
>> >> Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.
>> >
>> > _______________________________________________
>> > Concurrency-interest mailing list
>> > [hidden email]
>> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
Thanks. I realize that. I was merely trying to come up with a bullet-point-like explanation of what is wrong with unlinking the last element of the queue.

So moving tail "up" to point to prev atomically with the unlinking of the last node is one - without atomicity of such update can't ensure the actual last element of the queue remains reachable from the tail.

And even in "tailless" designs there is a problem: last node remains attachable even after unlinking - concurrent attempts to add elements to the queue can be modifying next after the node is unlinked.

Alex

On Sun, 16 Aug 2020, 20:55 Martin Buchholz, <[hidden email]> wrote:
On Sat, Aug 15, 2020 at 1:24 AM Alex Otenko <[hidden email]> wrote:
>
> Great. But still head and tail point to nodes in the same chain, right?

java.util.concurrent is where data structure intuition goes to die.

    /**
     * A node from which the last node on list (that is, the unique
     * node with node.next == null) can be reached in O(1) time.
     * Invariants:
     * - the last node is always reachable from tail via succ()
     * - tail != null
     * Non-invariants:
     * - tail.item may or may not be null.
     * - it is permitted for tail to lag behind head, that is, for tail
     *   to not be reachable from head!
     * - tail.next may or may not be self-linked.
     */
    private transient volatile Node<E> tail;


>
> Alex
>
> On Sat, 15 Aug 2020, 08:02 Martin Buchholz, <[hidden email]> wrote:
>>
>> I did more work on ConcurrentLinkedQueue, including recording the
>> invariants, notably:
>>
>>      * Invariants:
>>      * - all live nodes are reachable from head via succ()
>>      * - head != null
>>      * - (tmp = head).next != tmp || tmp != head
>>      * Non-invariants:
>>      * - head.item may or may not be null.
>>      * - it is permitted for tail to lag behind head, that is, for tail
>>      *   to not be reachable from head!
>>
>> On Fri, Aug 14, 2020 at 11:23 PM Alex Otenko via Concurrency-interest
>> <[hidden email]> wrote:
>> >
>> > Yes. There is an unspoken invariant that head and tail make progress in one direction. That is pretty much the only way to make sure the head never passes the tail. Then deleting tail cannot be done without moving the tail backwards to pred. This breaks the unspoken invariant in the presence of concurrent modifications of head.
>> >
>> > Alex
>> >
>> > On Sat, 15 Aug 2020, 07:18 Liu, <[hidden email]> wrote:
>> >>
>> >> Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.
>> >
>> > _______________________________________________
>> > Concurrency-interest mailing list
>> > [hidden email]
>> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
I realize now that "tail" is ambiguous, and can also refer to what I
called trailing node.

            // Never unlink trailing node.

On Sun, Aug 16, 2020 at 4:13 PM Alex Otenko <[hidden email]> wrote:

>
> Thanks. I realize that. I was merely trying to come up with a bullet-point-like explanation of what is wrong with unlinking the last element of the queue.
>
> So moving tail "up" to point to prev atomically with the unlinking of the last node is one - without atomicity of such update can't ensure the actual last element of the queue remains reachable from the tail.
>
> And even in "tailless" designs there is a problem: last node remains attachable even after unlinking - concurrent attempts to add elements to the queue can be modifying next after the node is unlinked.
>
> Alex
>
> On Sun, 16 Aug 2020, 20:55 Martin Buchholz, <[hidden email]> wrote:
>>
>> On Sat, Aug 15, 2020 at 1:24 AM Alex Otenko <[hidden email]> wrote:
>> >
>> > Great. But still head and tail point to nodes in the same chain, right?
>>
>> java.util.concurrent is where data structure intuition goes to die.
>>
>>     /**
>>      * A node from which the last node on list (that is, the unique
>>      * node with node.next == null) can be reached in O(1) time.
>>      * Invariants:
>>      * - the last node is always reachable from tail via succ()
>>      * - tail != null
>>      * Non-invariants:
>>      * - tail.item may or may not be null.
>>      * - it is permitted for tail to lag behind head, that is, for tail
>>      *   to not be reachable from head!
>>      * - tail.next may or may not be self-linked.
>>      */
>>     private transient volatile Node<E> tail;
>>
>>
>> >
>> > Alex
>> >
>> > On Sat, 15 Aug 2020, 08:02 Martin Buchholz, <[hidden email]> wrote:
>> >>
>> >> I did more work on ConcurrentLinkedQueue, including recording the
>> >> invariants, notably:
>> >>
>> >>      * Invariants:
>> >>      * - all live nodes are reachable from head via succ()
>> >>      * - head != null
>> >>      * - (tmp = head).next != tmp || tmp != head
>> >>      * Non-invariants:
>> >>      * - head.item may or may not be null.
>> >>      * - it is permitted for tail to lag behind head, that is, for tail
>> >>      *   to not be reachable from head!
>> >>
>> >> On Fri, Aug 14, 2020 at 11:23 PM Alex Otenko via Concurrency-interest
>> >> <[hidden email]> wrote:
>> >> >
>> >> > Yes. There is an unspoken invariant that head and tail make progress in one direction. That is pretty much the only way to make sure the head never passes the tail. Then deleting tail cannot be done without moving the tail backwards to pred. This breaks the unspoken invariant in the presence of concurrent modifications of head.
>> >> >
>> >> > Alex
>> >> >
>> >> > On Sat, 15 Aug 2020, 07:18 Liu, <[hidden email]> wrote:
>> >> >>
>> >> >> Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.
>> >> >
>> >> > _______________________________________________
>> >> > Concurrency-interest mailing list
>> >> > [hidden email]
>> >> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list


I try to understand what you guys are saying.

Firstly,    A -> B -> C(tail) -> null, and if C should be cleaned,
 it should become A -> B(tail)  -> null. but there is No such atomic operation.

Secondly, some threads may see A -> B  -> null and C(tail), and may append node
after C which is wrong.




 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
When a thread wants to enqueue a new element at the end, it finds the
last Node (the unique one whose next is null) and tries to CAS next to
a new Node containing the new element.  If the CAS succeeds, it must
have atomically enqueued the new element.

On Sun, Aug 16, 2020 at 7:14 PM Liu <[hidden email]> wrote:

>
>
> I try to understand what you guys are saying.
>
> Firstly,    A -> B -> C(tail) -> null, and if C should be cleaned,
>  it should become A -> B(tail)  -> null. but there is No such atomic operation.
>
> Secondly, some threads may see A -> B  -> null and C(tail), and may append node
> after C which is wrong.
>
>
>
>
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Correct. In addition, notice that updating tail to point to B can't be done atomically with unlinking of C. Then it's possible for head and tail to point to chains with no common nodes.

Alex

On Mon, 17 Aug 2020, 03:14 Liu, <[hidden email]> wrote:


I try to understand what you guys are saying.

Firstly,    A -> B -> C(tail) -> null, and if C should be cleaned,
 it should become A -> B(tail)  -> null. but there is No such atomic operation.

Secondly, some threads may see A -> B  -> null and C(tail), and may append node
after C which is wrong.




 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

JSR166 Concurrency mailing list
What I meant to point out, was the subtle difference between the two cases. Your second picture makes it look like the first case.

The first way for this to go wrong. No atomic update of tail - cannot guarantee it may not guarantee tail may not refer to a chain with some nodes reachable from head. Reasoning locally (an important tool in analyzing algorithms) - that is, considering the unlinking logic alone - we can prove that updating tail cannot be done safely, if it is not atomic with unlinking. A breaking case is unlinking B and C concurrently. 

The second way for this to go wrong assumes we solve the atomicity of tail update in some way. (For the sake of argument, assume tail always points to one or two nodes before last; appending is still O(1)) Even in this case removing the last node is not correct, because updating B.next (unlinking C) and C.next (enqueue D) is concurrent. But this seems to require reasoning about other methods (not local).

Alex

On Mon, 17 Aug 2020, 07:17 Alex Otenko, <[hidden email]> wrote:
Correct. In addition, notice that updating tail to point to B can't be done atomically with unlinking of C. Then it's possible for head and tail to point to chains with no common nodes.

Alex

On Mon, 17 Aug 2020, 03:14 Liu, <[hidden email]> wrote:


I try to understand what you guys are saying.

Firstly,    A -> B -> C(tail) -> null, and if C should be cleaned,
 it should become A -> B(tail)  -> null. but there is No such atomic operation.

Secondly, some threads may see A -> B  -> null and C(tail), and may append node
after C which is wrong.




 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest