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

LinkedBlockingDeque iterator/descendingIterator loops and owns lock forever

    Details

    • Subcomponent:
    • Introduced In Build:
      b01
    • Introduced In Version:
    • Resolved In Build:
      b120
    • CPU:
      x86
    • OS:
      linux
    • Verification:
      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

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

                  Dates

                  • Created:
                    Updated:
                    Resolved:
                    Imported:
                    Indexed: