United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6724218 Incorrect code is generated for org.apache.commons.collections.list.AbstractLinkedList::removeNode
JDK-6724218 : Incorrect code is generated for org.apache.commons.collections.list.AbstractLinkedList::removeNode

Details
Type:
Bug
Submit Date:
2008-07-09
Status:
Resolved
Updated Date:
2010-05-10
Project Name:
JDK
Resolved Date:
2008-07-19
Component:
hotspot
OS:
linux
Sub-Component:
compiler
CPU:
x86
Priority:
P3
Resolution:
Fixed
Affected Versions:
hs10
Fixed Versions:
hs11 (b15)

Related Reports
Backport:
Backport:
Backport:
Relates:

Sub Tasks

Description
Keith McNeill from Streambase reported the problem with latest jdk6u6 on linux-x86 32-bits VM.

Keith McNeill wrote:
> Hotspot is producing incorrect code deep in the bowels of our system.
> A simple example doesn't produce the problem.
> 
> java -Xinternalversion
> Java HotSpot(TM) Server VM (10.0-b22) for linux-x86 JRE (1.6.0_06-b02), built on Mar 25 2008 00:26:44 by "java_re" with gcc 3.2.1-7a (J2SE release)
> 
> Note that the problem has occurred on every 1.6 jdk I've tried up to the latest 1.6.0_10 beta
> 
> The problem does not occur on JDK 1.5
>
> 
> I've enclosed a tarfile.  With the debug VM the problem is much more 
> intermittent than without the debug VM.  So I've included output from 2 
> runs.  One showing the problem (bad directory).  The other not showing 
> the problem (good directory).
> I've also included the source and the .class file for the class in 
> question.

                                    

Comments
EVALUATION

C2 generated incorrect code for AbstractLinkedList::removeNode 
which is inlined into customer's method Mailbox.nextEvent():

else if (!_paused && _events.size() > 0) {
    return _events.getNext();
}

Inlining stack:

# org.apache.commons.collections.list.AbstractLinkedList::removeNode
# org.apache.commons.collections.list.NodeCachingLinkedList::removeNode
# org.apache.commons.collections.list.AbstractLinkedList::removeFirst
# com.streambase.sb.runtime.sbd.Mailbox$OrderedSet::getNext

In the bad case the field node.value could be
NULLed before the value is returned: 

  if (!Mailbox._paused) {
    LinkedList list = _events._list;
    int size = list.size;
    if (size > 0) {

      LinkedList$Node head = list.header;
      LinkedList$Node node = head.next;
       
      LinkedList$Node firstCached = list.firstCachedNode;
      int maxCacheSize = list.maximumCacheSize;
      int modCount = list.modCount;
      int cacheSize = list.cacheSize;

      size -= 1;
      cacheSize += 1;
      modCount += 1;

      if (node == head) {
        // the code which was not executed before this JIT compilation
      }
      LinkedList$Node previous = node.previous;
      previous.next = node.next
      
      LinkedList$Node next = node.next;
      next.previous = previous;

      if (list.cacheSize < maxCacheSize) {
          list.firstCachedNode = node;
        list.cacheSize = cacheSize;
        node.next = firstCached;
        node.previous = NULL;
        node.value = NULL;
      }
      list.size     = size;
      list.modCount = modCount;
      Object value = node.value;

      return value;
    }
  }
    

In good case node.value is saved in a register before 
the field node.value is NULLed:

      LinkedList$Node next = node.next;
      next.previous = previous;
      list.size     = size;
      list.modCount = modCount;
      Object value = node.value;

      if (list.cacheSize < maxCacheSize) {
          list.firstCachedNode = node;
        list.cacheSize = cacheSize;
        node.next = firstCached;
        node.previous = NULL;
        node.value = NULL;
      }
      return value;
    }
  }
                                     
2008-07-09
SUGGESTED FIX

Fix raise_LCA_above_marks() early termination.

src/share/vm/opto/gcm.cpp
@@ -308,27 +308,29 @@
     Block* mid = worklist.pop();
     if (mid == early)  continue;  // stop searching here
 
     // Test and set the visited bit.
     if (mid->raise_LCA_visited() == mark)  continue;  // already visited
-    mid->set_raise_LCA_visited(mark);
 
     // Don't process the current LCA, otherwise the search may terminate early
     if (mid != LCA && mid->raise_LCA_mark() == mark) {
       // Raise the LCA.
       LCA = mid->dom_lca(LCA);
       if (LCA == early)  break;   // stop searching everywhere
       assert(early->dominates(LCA), "early is high enough");
       // Resume searching at that point, skipping intermediate levels.
       worklist.push(LCA);
+      if (LCA == mid)
+        continue; // Don't mark as visited to avoid early termination.
     } else {
       // Keep searching through this block's predecessors.
       for (uint j = 1, jmax = mid->num_preds(); j < jmax; j++) {
         Block* mid_parent = bbs[ mid->pred(j)->_idx ];
         worklist.push(mid_parent);
       }
     }
+    mid->set_raise_LCA_visited(mark);
   }
   return LCA;
 }
                                     
2008-07-12



Hardware and Software, Engineered to Work Together