Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-6993789

LinkedBlockingDeque iterator/descendingIterator loops and owns lock forever

    XMLWordPrintable

Details

    • b01
    • b120
    • x86
    • linux
    • Verified

    Backports

      Description

        FULL PRODUCT VERSION :
        java version "1.6.0_21"
        Java(TM) SE Runtime Environment (build 1.6.0_21-b06)
        Java HotSpot(TM) Server VM (build 17.0-b16, mixed mode)

        Same with build 1.7.0-ea-b114

        ADDITIONAL OS VERSION INFORMATION :
        Linux ... 2.6.34.7-0.3-desktop #1 SMP PREEMPT 2010-09-20 15:27:38 +0200 i686 i686 i386 GNU/Linux

        A DESCRIPTION OF THE PROBLEM :
        The iterator of the LinkedBlockingDeque can loop for ever in a particular case when attempting to retrieve the next item to return. As the iterator owns the deque's lock, the deque becomes unusable. Indeed, this blocks all threads attempting to access the deque and the thread that uses the iterator.

        The test case that reproduces the issue follows but here is what is happening (switch to monospace for the illustration).

        - Add three elements in the deque: "1", "2", "3"
        - Create an iterator and iterate just once. The iterator has returned the "1" item and is internally referencing the node of the "2".
        - Remove in that order "2", "1", "3". The implementation of the unlinkFirst() method sets the next reference of the node removed to itself. Thus, nodes "1" and "3" both have their next references to themselves. Here is the illustration of the iterator


                +-----+ +-----+
                | | | |
                v | v |
             +-----+ | +-----+ +-----+ |
             | |--+ | |---->| |--+
             | 1 | | 2 | | 3 |
          X<-| |<----| | X<-| |
             +-----+ +-----+ +-----+
                | | |
                v v v
                X X X


        - From that situation, the iterator loops forever.



        REPRODUCIBILITY :
        This bug can be reproduced always.

        ---------- BEGIN SOURCE ----------
            Deque<String> deque = new LinkedBlockingDeque<String>();
            deque.add("1");
            deque.add("2");
            deque.add("3");

            int i=1;

            for(String s:deque)
            {
              System.out.println(s);
              if ( i == 1 )
              {
                deque.remove("2");
                deque.remove("1");
                deque.remove("3");
              }
              
              i++;
            }
        ---------- END SOURCE ----------

        Attachments

          Issue Links

            Activity

              People

                chegar Chris Hegarty
                webbuggrp Webbug Group
                Votes:
                0 Vote for this issue
                Watchers:
                1 Start watching this issue

                Dates

                  Created:
                  Updated:
                  Resolved:
                  Imported:
                  Indexed: