--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/agent/src/share/classes/sun/jvm/hotspot/utilities/ReversePtrsAnalysis.java	Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,299 @@
+/*
+ * Copyright 2002-2006 Sun Microsystems, Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+package sun.jvm.hotspot.utilities;
+
+import java.io.*;
+import java.util.*;
+import sun.jvm.hotspot.debugger.*;
+import sun.jvm.hotspot.gc_interface.*;
+import sun.jvm.hotspot.memory.*;
+import sun.jvm.hotspot.oops.*;
+import sun.jvm.hotspot.runtime.*;
+import sun.jvm.hotspot.utilities.*;
+
+/** For a set of known roots, descends recursively into the object
+    graph, for each object recording those objects (and their fields)
+    which point to it. NOTE: currently only a subset of the roots
+    known to the VM is exposed to the SA: objects on the stack, static
+    fields in classes, and JNI handles. These should be most of the
+    user-level roots keeping objects alive. */
+
+public class ReversePtrsAnalysis {
+  // Used for debugging this code
+  private static final boolean DEBUG = false;
+
+  public ReversePtrsAnalysis() {
+  }
+
+  /** Sets an optional progress thunk */
+  public void setHeapProgressThunk(HeapProgressThunk thunk) {
+    progressThunk = thunk;
+  }
+
+
+  /** Runs the analysis algorithm */
+  public void run() {
+    if (VM.getVM().getRevPtrs() != null) {
+      return; // Assume already done
+    }
+
+    VM vm = VM.getVM();
+    rp = new ReversePtrs();
+    vm.setRevPtrs(rp);
+    Universe universe = vm.getUniverse();
+    CollectedHeap collHeap = universe.heap();
+    usedSize = collHeap.used();
+    visitedSize = 0;
+
+    // Note that an experiment to iterate the heap linearly rather
+    // than in recursive-descent order has been done. It turns out
+    // that the recursive-descent algorithm is nearly twice as fast
+    // due to the fact that it scans only live objects and (currently)
+    // only a fraction of the perm gen, namely the static fields
+    // contained in instanceKlasses. (Iterating the heap linearly
+    // would also change the semantics of the result so that
+    // ReversePtrs.get() would return a non-null value even for dead
+    // objects.) Nonetheless, the reverse pointer computation is still
+    // quite slow and optimization in field iteration of objects
+    // should be done.
+
+    if (progressThunk != null) {
+      // Get it started
+      progressThunk.heapIterationFractionUpdate(0);
+    }
+
+    // Allocate mark bits for heap
+    markBits = new MarkBits(collHeap);
+
+    // Get a hold of the object heap
+    heap = vm.getObjectHeap();
+
+    // Do each thread's roots
+    for (JavaThread thread = VM.getVM().getThreads().first();
+         thread != null;
+         thread = thread.next()) {
+      ByteArrayOutputStream bos = new ByteArrayOutputStream();
+      thread.printThreadIDOn(new PrintStream(bos));
+      String threadDesc =
+        " in thread \"" + thread.getThreadName() +
+        "\" (id " + bos.toString() + ")";
+      doStack(thread,
+              new RootVisitor("Stack root" + threadDesc));
+      doJNIHandleBlock(thread.activeHandles(),
+                       new RootVisitor("JNI handle root" + threadDesc));
+    }
+
+    // Do global JNI handles
+    JNIHandles handles = VM.getVM().getJNIHandles();
+    doJNIHandleBlock(handles.globalHandles(),
+                     new RootVisitor("Global JNI handle root"));
+    doJNIHandleBlock(handles.weakGlobalHandles(),
+                     new RootVisitor("Weak global JNI handle root"));
+
+    // Do Java-level static fields in perm gen
+    heap.iteratePerm(new DefaultHeapVisitor() {
+        public boolean doObj(Oop obj) {
+          if (obj instanceof InstanceKlass) {
+            final InstanceKlass ik = (InstanceKlass) obj;
+            ik.iterateFields(
+               new DefaultOopVisitor() {
+                   public void doOop(OopField field, boolean isVMField) {
+                     Oop next = field.getValue(ik);
+                     LivenessPathElement lp = new LivenessPathElement(null,
+                             new NamedFieldIdentifier("Static field \"" +
+                                                field.getID().getName() +
+                                                "\" in class \"" +
+                                                ik.getName().asString() + "\""));
+                     rp.put(lp, next);
+                     try {
+                       markAndTraverse(next);
+                     } catch (AddressException e) {
+                       System.err.print("RevPtrs analysis: WARNING: AddressException at 0x" +
+                                        Long.toHexString(e.getAddress()) +
+                                        " while traversing static fields of InstanceKlass ");
+                       ik.printValueOn(System.err);
+                       System.err.println();
+                     } catch (UnknownOopException e) {
+                       System.err.println("RevPtrs analysis: WARNING: UnknownOopException while " +
+                                          "traversing static fields of InstanceKlass ");
+                       ik.printValueOn(System.err);
+                       System.err.println();
+                     }
+                   }
+                 },
+               false);
+          }
+                  return false;
+        }
+      });
+
+    if (progressThunk != null) {
+      progressThunk.heapIterationComplete();
+    }
+
+    // Clear out markBits
+    markBits = null;
+  }
+
+
+  //---------------------------------------------------------------------------
+  // Internals only below this point
+  //
+  private HeapProgressThunk   progressThunk;
+  private long                usedSize;
+  private long                visitedSize;
+  private double              lastNotificationFraction;
+  private static final double MINIMUM_NOTIFICATION_FRACTION = 0.01;
+  private ObjectHeap          heap;
+  private MarkBits            markBits;
+  private int                 depth; // Debugging only
+  private ReversePtrs         rp;
+
+  private void markAndTraverse(OopHandle handle) {
+    try {
+      markAndTraverse(heap.newOop(handle));
+    } catch (AddressException e) {
+      System.err.println("RevPtrs analysis: WARNING: AddressException at 0x" +
+                         Long.toHexString(e.getAddress()) +
+                         " while traversing oop at " + handle);
+    } catch (UnknownOopException e) {
+      System.err.println("RevPtrs analysis: WARNING: UnknownOopException for " +
+                         "oop at " + handle);
+    }
+  }
+
+  private void printHeader() {
+    for (int i = 0; i < depth; i++) {
+      System.err.print(" ");
+    }
+  }
+
+  private void markAndTraverse(final Oop obj) {
+
+    // End of path
+    if (obj == null) {
+      return;
+    }
+
+    // Visited object
+    if (!markBits.mark(obj)) {
+      return;
+    }
+
+    // Root of work list for objects to be visited.  A simple
+    // stack for saving new objects to be analyzed.
+
+    final Stack workList = new Stack();
+
+    // Next object to be visited.
+    Oop next = obj;
+
+    try {
+      // Node in the list currently being visited.
+
+      while (true) {
+        final Oop currObj = next;
+
+        // For the progress meter
+        if (progressThunk != null) {
+          visitedSize += currObj.getObjectSize();
+          double curFrac = (double) visitedSize / (double) usedSize;
+          if (curFrac >
+              lastNotificationFraction + MINIMUM_NOTIFICATION_FRACTION) {
+            progressThunk.heapIterationFractionUpdate(curFrac);
+            lastNotificationFraction = curFrac;
+          }
+        }
+
+        if (DEBUG) {
+          ++depth;
+          printHeader();
+          System.err.println("ReversePtrs.markAndTraverse(" +
+              currObj.getHandle() + ")");
+        }
+
+        // Iterate over the references in the object.  Do the
+        // reverse pointer analysis for each reference.
+        // Add the reference to the work-list so that its
+        // references will be visited.
+        currObj.iterate(new DefaultOopVisitor() {
+          public void doOop(OopField field, boolean isVMField) {
+            // "field" refers to a reference in currObj
+            Oop next = field.getValue(currObj);
+            rp.put(new LivenessPathElement(currObj, field.getID()), next);
+            if ((next != null) && markBits.mark(next)) {
+              workList.push(next);
+            }
+          }
+        }, false);
+
+        if (DEBUG) {
+          --depth;
+        }
+
+        // Get the next object to visit.
+        next = (Oop) workList.pop();
+      }
+    } catch (EmptyStackException e) {
+      // Done
+    } catch (NullPointerException e) {
+      System.err.println("ReversePtrs: WARNING: " + e +
+        " during traversal");
+    } catch (Exception e) {
+      System.err.println("ReversePtrs: WARNING: " + e +
+        " during traversal");
+    }
+  }
+
+
+  class RootVisitor implements AddressVisitor {
+    RootVisitor(String baseRootDescription) {
+      this.baseRootDescription = baseRootDescription;
+    }
+
+    public void visitAddress(Address addr) {
+      Oop next = heap.newOop(addr.getOopHandleAt(0));
+      LivenessPathElement lp = new LivenessPathElement(null,
+                                        new NamedFieldIdentifier(baseRootDescription +
+                                                                 " @ " + addr));
+      rp.put(lp, next);
+      markAndTraverse(next);
+    }
+
+    private String baseRootDescription;
+  }
+
+  // Traverse the roots on a given thread's stack
+  private void doStack(JavaThread thread, AddressVisitor oopVisitor) {
+    for (StackFrameStream fst = new StackFrameStream(thread); !fst.isDone(); fst.next()) {
+      fst.getCurrent().oopsDo(oopVisitor, fst.getRegisterMap());
+    }
+  }
+
+  // Traverse a JNIHandleBlock
+  private void doJNIHandleBlock(JNIHandleBlock handles, AddressVisitor oopVisitor) {
+    handles.oopsDo(oopVisitor);
+  }
+}