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

(coll) WeakHashMap's HashIterator may skip entries

    Details

    • Subcomponent:
    • Resolved In Build:
      b17
    • CPU:
      x86
    • OS:
      windows_xp
    • Verification:
      Not verified

      Description

      FULL PRODUCT VERSION :
      java version "1.6.0-rc"
      Java(TM) SE Runtime Environment (build 1.6.0-rc-b104)
      Java HotSpot(TM) Client VM (build 1.6.0-rc-b104, mixed mode, sharing)

      ADDITIONAL OS VERSION INFORMATION :
      Microsoft Windows XP [Version 5.1.2600]

      A DESCRIPTION OF THE PROBLEM :
      When iterating over the keys or values of a WeakHashMap, it can happen in some rare cases that keys/values are skipped.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      This is a theoretical bug that I have not encountered in reality, but I hope that my explanation will show how the bug can occur.

      Let's assume that the table of our WeakHashMap (named 'map') is populated as follows (the letters are the map's keys, we ignore the values):

      0[]
      1[A, B]
      2[]
      3[C, D, E]
      4[F]
      5[]

      We create the key iterator and run through it like this:

      Iterator it = map.keySet().iterator();
      while (it.hasNext()) {
        Object o = it.next();
        // do something with o
      }

      The iterator starts behind the last table index, moving upwards. If there is more than one entry at an index, it will first return the start entry's value and then walk through the next entries. I no entries are garbage collected during iteration, the sequence of returned values is F, C, D, E, A, B

      For simplicity let's assume that all objects except D are held by a strong reference, which means they cannot be garbage collected. Now we iterate until it.next() returned C. The iterator will then have the following state:

      lastReturned: entry[C];
      entry: = entry[D];
      currentKey: C;
      nextKey: null;

      Note that the iterator does not hold a strong reference to D, which means it can be garbage collections. Let's assume that D just now gets garbage collected. For some reason before doing the next iteration step we call one of the WeakHashMap methods should be safe to call because they do not change the map's structure and the map's modCount (for example size(), get(Object key)). These methods call (directly or indirectly) the expungeStaleEntries() method. In the the expungeStaleEntries() method, entry[D] will get removed from the table and its next-field will be set to null. If we then call hasNext(), the iterator decides it has reached the last entry at the current table index and decrement the table index. As a result, next() will return A, while it should return E.




      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      In our theoretical case, the iterator should return


      F, C, E, A, B
      ACTUAL -
      In our theoretical case, the iterator will return


      F, C, A, B

      REPRODUCIBILITY :
      This bug can be reproduced rarely.

      ---------- BEGIN SOURCE ----------
      Sorry, do not have one
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      I do not have a workaround, but there are basically three ways to fix the bug:

      1. In the expungeStaleEntries() method do not set the next-field to null for removed entries.
      2. Keep a strong reference to the entry's value after next() has been called, so it cannot be garbage collected.
      3. Determine the next entry and value in the constructor and in the next() method. The hasNext() method will then return true if nextValue is non-null, otherwise false.

        Attachments

          Activity

            People

            • Assignee:
              martin Martin Buchholz
              Reporter:
              tyao Ting-Yun Ingrid Yao (Inactive)
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:
                Imported:
                Indexed: