/*

 * Copyright 2000-2007 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.

 *

 */

//

// The ObjectHeap is an abstraction over all generations in the VM

// It gives access to all present objects and classes.

//

package sun.jvm.hotspot.oops;

import java.util.*;

import sun.jvm.hotspot.debugger.*;

import sun.jvm.hotspot.gc_interface.*;

import sun.jvm.hotspot.gc_implementation.parallelScavenge.*;

import sun.jvm.hotspot.memory.*;

import sun.jvm.hotspot.runtime.*;

import sun.jvm.hotspot.types.*;

import sun.jvm.hotspot.utilities.*;

public class ObjectHeap {

  private OopHandle              symbolKlassHandle;

  private OopHandle              methodKlassHandle;

  private OopHandle              constMethodKlassHandle;

  private OopHandle              methodDataKlassHandle;

  private OopHandle              constantPoolKlassHandle;

  private OopHandle              constantPoolCacheKlassHandle;

  private OopHandle              klassKlassHandle;

  private OopHandle              instanceKlassKlassHandle;

  private OopHandle              typeArrayKlassKlassHandle;

  private OopHandle              objArrayKlassKlassHandle;

  private OopHandle              boolArrayKlassHandle;

  private OopHandle              byteArrayKlassHandle;

  private OopHandle              charArrayKlassHandle;

  private OopHandle              intArrayKlassHandle;

  private OopHandle              shortArrayKlassHandle;

  private OopHandle              longArrayKlassHandle;

  private OopHandle              singleArrayKlassHandle;

  private OopHandle              doubleArrayKlassHandle;

  private OopHandle              arrayKlassKlassHandle;

  private OopHandle              compiledICHolderKlassHandle;

  private SymbolKlass            symbolKlassObj;

  private MethodKlass            methodKlassObj;

  private ConstMethodKlass       constMethodKlassObj;

  private MethodDataKlass        methodDataKlassObj;

  private ConstantPoolKlass      constantPoolKlassObj;

  private ConstantPoolCacheKlass constantPoolCacheKlassObj;

  private KlassKlass             klassKlassObj;

  private InstanceKlassKlass     instanceKlassKlassObj;

  private TypeArrayKlassKlass    typeArrayKlassKlassObj;

  private ObjArrayKlassKlass     objArrayKlassKlassObj;

  private TypeArrayKlass         boolArrayKlassObj;

  private TypeArrayKlass         byteArrayKlassObj;

  private TypeArrayKlass         charArrayKlassObj;

  private TypeArrayKlass         intArrayKlassObj;

  private TypeArrayKlass         shortArrayKlassObj;

  private TypeArrayKlass         longArrayKlassObj;

  private TypeArrayKlass         singleArrayKlassObj;

  private TypeArrayKlass         doubleArrayKlassObj;

  private ArrayKlassKlass        arrayKlassKlassObj;

  private CompiledICHolderKlass  compiledICHolderKlassObj;

  public void initialize(TypeDataBase db) throws WrongTypeException {

    // Lookup the roots in the object hierarchy.

    Type universeType = db.lookupType("Universe");

    symbolKlassHandle         = universeType.getOopField("_symbolKlassObj").getValue();

    symbolKlassObj            = new SymbolKlass(symbolKlassHandle, this);

    methodKlassHandle         = universeType.getOopField("_methodKlassObj").getValue();

    methodKlassObj            = new MethodKlass(methodKlassHandle, this);

    constMethodKlassHandle    = universeType.getOopField("_constMethodKlassObj").getValue();

    constMethodKlassObj       = new ConstMethodKlass(constMethodKlassHandle, this);

    constantPoolKlassHandle   = universeType.getOopField("_constantPoolKlassObj").getValue();

    constantPoolKlassObj      = new ConstantPoolKlass(constantPoolKlassHandle, this);

    constantPoolCacheKlassHandle = universeType.getOopField("_constantPoolCacheKlassObj").getValue();

    constantPoolCacheKlassObj = new ConstantPoolCacheKlass(constantPoolCacheKlassHandle, this);

    klassKlassHandle          = universeType.getOopField("_klassKlassObj").getValue();

    klassKlassObj             = new KlassKlass(klassKlassHandle, this);

    arrayKlassKlassHandle     = universeType.getOopField("_arrayKlassKlassObj").getValue();

    arrayKlassKlassObj        = new ArrayKlassKlass(arrayKlassKlassHandle, this);

    instanceKlassKlassHandle  = universeType.getOopField("_instanceKlassKlassObj").getValue();

    instanceKlassKlassObj     = new InstanceKlassKlass(instanceKlassKlassHandle, this);

    typeArrayKlassKlassHandle = universeType.getOopField("_typeArrayKlassKlassObj").getValue();

    typeArrayKlassKlassObj    = new TypeArrayKlassKlass(typeArrayKlassKlassHandle, this);

    objArrayKlassKlassHandle  = universeType.getOopField("_objArrayKlassKlassObj").getValue();

    objArrayKlassKlassObj     = new ObjArrayKlassKlass(objArrayKlassKlassHandle, this);

    boolArrayKlassHandle      = universeType.getOopField("_boolArrayKlassObj").getValue();

    boolArrayKlassObj         = new TypeArrayKlass(boolArrayKlassHandle, this);

    byteArrayKlassHandle      = universeType.getOopField("_byteArrayKlassObj").getValue();

    byteArrayKlassObj         = new TypeArrayKlass(byteArrayKlassHandle, this);

    charArrayKlassHandle      = universeType.getOopField("_charArrayKlassObj").getValue();

    charArrayKlassObj         = new TypeArrayKlass(charArrayKlassHandle, this);

    intArrayKlassHandle       = universeType.getOopField("_intArrayKlassObj").getValue();

    intArrayKlassObj          = new TypeArrayKlass(intArrayKlassHandle, this);

    shortArrayKlassHandle     = universeType.getOopField("_shortArrayKlassObj").getValue();

    shortArrayKlassObj        = new TypeArrayKlass(shortArrayKlassHandle, this);

    longArrayKlassHandle      = universeType.getOopField("_longArrayKlassObj").getValue();

    longArrayKlassObj         = new TypeArrayKlass(longArrayKlassHandle, this);

    singleArrayKlassHandle    = universeType.getOopField("_singleArrayKlassObj").getValue();

    singleArrayKlassObj       = new TypeArrayKlass(singleArrayKlassHandle, this);

    doubleArrayKlassHandle    = universeType.getOopField("_doubleArrayKlassObj").getValue();

    doubleArrayKlassObj       = new TypeArrayKlass(doubleArrayKlassHandle, this);

    if (!VM.getVM().isCore()) {

      methodDataKlassHandle   = universeType.getOopField("_methodDataKlassObj").getValue();

      methodDataKlassObj      = new MethodDataKlass(methodDataKlassHandle, this);

      compiledICHolderKlassHandle = universeType.getOopField("_compiledICHolderKlassObj").getValue();

      compiledICHolderKlassObj= new CompiledICHolderKlass(compiledICHolderKlassHandle ,this);

    }

  }

  public ObjectHeap(TypeDataBase db) throws WrongTypeException {

    // Get commonly used sizes of basic types

    oopSize     = db.getOopSize();

    byteSize    = db.getJByteType().getSize();

    charSize    = db.getJCharType().getSize();

    booleanSize = db.getJBooleanType().getSize();

    intSize     = db.getJIntType().getSize();

    shortSize   = db.getJShortType().getSize();

    longSize    = db.getJLongType().getSize();

    floatSize   = db.getJFloatType().getSize();

    doubleSize  = db.getJDoubleType().getSize();

    initialize(db);

  }

  /** Comparison operation for oops, either or both of which may be null */

  public boolean equal(Oop o1, Oop o2) {

    if (o1 != null) return o1.equals(o2);

    return (o2 == null);

  }

  // Cached sizes of basic types

  private long oopSize;

  private long byteSize;

  private long charSize;

  private long booleanSize;

  private long intSize;

  private long shortSize;

  private long longSize;

  private long floatSize;

  private long doubleSize;

  public long getOopSize()     { return oopSize;     }

  public long getByteSize()    { return byteSize;    }

  public long getCharSize()    { return charSize;    }

  public long getBooleanSize() { return booleanSize; }

  public long getIntSize()     { return intSize;     }

  public long getShortSize()   { return shortSize;   }

  public long getLongSize()    { return longSize;    }

  public long getFloatSize()   { return floatSize;   }

  public long getDoubleSize()  { return doubleSize;  }

  // Accessors for well-known system classes (from Universe)

  public SymbolKlass            getSymbolKlassObj()            { return symbolKlassObj; }

  public MethodKlass            getMethodKlassObj()            { return methodKlassObj; }

  public ConstMethodKlass       getConstMethodKlassObj()       { return constMethodKlassObj; }

  public MethodDataKlass        getMethodDataKlassObj()        { return methodDataKlassObj; }

  public ConstantPoolKlass      getConstantPoolKlassObj()      { return constantPoolKlassObj; }

  public ConstantPoolCacheKlass getConstantPoolCacheKlassObj() { return constantPoolCacheKlassObj; }

  public KlassKlass             getKlassKlassObj()             { return klassKlassObj; }

  public ArrayKlassKlass        getArrayKlassKlassObj()        { return arrayKlassKlassObj; }

  public InstanceKlassKlass     getInstanceKlassKlassObj()     { return instanceKlassKlassObj; }

  public ObjArrayKlassKlass     getObjArrayKlassKlassObj()     { return objArrayKlassKlassObj; }

  public TypeArrayKlassKlass    getTypeArrayKlassKlassObj()    { return typeArrayKlassKlassObj; }

  public TypeArrayKlass         getBoolArrayKlassObj()         { return boolArrayKlassObj; }

  public TypeArrayKlass         getByteArrayKlassObj()         { return byteArrayKlassObj; }

  public TypeArrayKlass         getCharArrayKlassObj()         { return charArrayKlassObj; }

  public TypeArrayKlass         getIntArrayKlassObj()          { return intArrayKlassObj; }

  public TypeArrayKlass         getShortArrayKlassObj()        { return shortArrayKlassObj; }

  public TypeArrayKlass         getLongArrayKlassObj()         { return longArrayKlassObj; }

  public TypeArrayKlass         getSingleArrayKlassObj()       { return singleArrayKlassObj; }

  public TypeArrayKlass         getDoubleArrayKlassObj()       { return doubleArrayKlassObj; }

  public CompiledICHolderKlass  getCompiledICHolderKlassObj()  {

    if (Assert.ASSERTS_ENABLED) {

      Assert.that(!VM.getVM().isCore(), "must not be called for core build");

    }

    return compiledICHolderKlassObj;

  }

  /** Takes a BasicType and returns the corresponding primitive array

      klass */

  public Klass typeArrayKlassObj(int t) {

    if (t == BasicType.getTBoolean()) return getBoolArrayKlassObj();

    if (t == BasicType.getTChar())    return getCharArrayKlassObj();

    if (t == BasicType.getTFloat())   return getSingleArrayKlassObj();

    if (t == BasicType.getTDouble())  return getDoubleArrayKlassObj();

    if (t == BasicType.getTByte())    return getByteArrayKlassObj();

    if (t == BasicType.getTShort())   return getShortArrayKlassObj();

    if (t == BasicType.getTInt())     return getIntArrayKlassObj();

    if (t == BasicType.getTLong())    return getLongArrayKlassObj();

    throw new RuntimeException("Illegal basic type " + t);

  }

  /** an interface to filter objects while walking heap */

  public static interface ObjectFilter {

    public boolean canInclude(Oop obj);

  }

  /** The base heap iteration mechanism */

  public void iterate(HeapVisitor visitor) {

    iterateLiveRegions(collectLiveRegions(), visitor, null);

  }

  /** iterate objects satisfying a specified ObjectFilter */

  public void iterate(HeapVisitor visitor, ObjectFilter of) {

    iterateLiveRegions(collectLiveRegions(), visitor, of);

  }

  /** iterate objects of given Klass. param 'includeSubtypes' tells whether to

   *  include objects of subtypes or not */

  public void iterateObjectsOfKlass(HeapVisitor visitor, final Klass k, boolean includeSubtypes) {

    if (includeSubtypes) {

      if (k.isFinal()) {

        // do the simpler "exact" klass loop

        iterateExact(visitor, k);

      } else {

        iterateSubtypes(visitor, k);

      }

    } else {

      // there can no object of abstract classes and interfaces

      if (!k.isAbstract() && !k.isInterface()) {

        iterateExact(visitor, k);

      }

    }

  }

  /** iterate objects of given Klass (objects of subtypes included) */

  public void iterateObjectsOfKlass(HeapVisitor visitor, final Klass k) {

    iterateObjectsOfKlass(visitor, k, true);

  }

  /** This routine can be used to iterate through the heap at an

      extremely low level (stepping word-by-word) to provide the

      ability to do very low-level debugging */

  public void iterateRaw(RawHeapVisitor visitor) {

    List liveRegions = collectLiveRegions();

    // Summarize size

    long totalSize = 0;

    for (int i = 0; i < liveRegions.size(); i += 2) {

      Address bottom = (Address) liveRegions.get(i);

      Address top    = (Address) liveRegions.get(i+1);

      totalSize += top.minus(bottom);

    }

    visitor.prologue(totalSize);

    for (int i = 0; i < liveRegions.size(); i += 2) {

      Address bottom = (Address) liveRegions.get(i);

      Address top    = (Address) liveRegions.get(i+1);

      // Traverses the space from bottom to top

      while (bottom.lessThan(top)) {

        visitor.visitAddress(bottom);

        bottom = bottom.addOffsetTo(VM.getVM().getAddressSize());

      }

    }

    visitor.epilogue();

  }

  // Iterates through only the perm generation for the purpose of

  // finding static fields for liveness analysis

  public void iteratePerm(HeapVisitor visitor) {

    CollectedHeap heap = VM.getVM().getUniverse().heap();

    List liveRegions = new ArrayList();

    addPermGenLiveRegions(liveRegions, heap);

    sortLiveRegions(liveRegions);

    iterateLiveRegions(liveRegions, visitor, null);

  }

  // Creates an instance from the Oop hierarchy based based on the handle

  public Oop newOop(OopHandle handle) {

    // The only known way to detect the right type of an oop is

    // traversing the class chain until a well-known klass is recognized.

    // A more direct solution would require the klasses to expose

    // the C++ vtbl structure.

    // Handle the null reference

    if (handle == null) return null;

    // First check if handle is one of the root objects

    if (handle.equals(methodKlassHandle))              return getMethodKlassObj();

    if (handle.equals(constMethodKlassHandle))         return getConstMethodKlassObj();

    if (handle.equals(symbolKlassHandle))              return getSymbolKlassObj();

    if (handle.equals(constantPoolKlassHandle))        return getConstantPoolKlassObj();

    if (handle.equals(constantPoolCacheKlassHandle))   return getConstantPoolCacheKlassObj();

    if (handle.equals(instanceKlassKlassHandle))       return getInstanceKlassKlassObj();

    if (handle.equals(objArrayKlassKlassHandle))       return getObjArrayKlassKlassObj();

    if (handle.equals(klassKlassHandle))               return getKlassKlassObj();

    if (handle.equals(arrayKlassKlassHandle))          return getArrayKlassKlassObj();

    if (handle.equals(typeArrayKlassKlassHandle))      return getTypeArrayKlassKlassObj();

    if (handle.equals(boolArrayKlassHandle))           return getBoolArrayKlassObj();

    if (handle.equals(byteArrayKlassHandle))           return getByteArrayKlassObj();

    if (handle.equals(charArrayKlassHandle))           return getCharArrayKlassObj();

    if (handle.equals(intArrayKlassHandle))            return getIntArrayKlassObj();

    if (handle.equals(shortArrayKlassHandle))          return getShortArrayKlassObj();

    if (handle.equals(longArrayKlassHandle))           return getLongArrayKlassObj();

    if (handle.equals(singleArrayKlassHandle))         return getSingleArrayKlassObj();

    if (handle.equals(doubleArrayKlassHandle))         return getDoubleArrayKlassObj();

    if (!VM.getVM().isCore()) {

      if (handle.equals(compiledICHolderKlassHandle))  return getCompiledICHolderKlassObj();

      if (handle.equals(methodDataKlassHandle))        return getMethodDataKlassObj();

    }

    // Then check if obj.klass() is one of the root objects

    OopHandle klass = Oop.getKlassForOopHandle(handle);

    if (klass != null) {

      if (klass.equals(methodKlassHandle))              return new Method(handle, this);

      if (klass.equals(constMethodKlassHandle))         return new ConstMethod(handle, this);

      if (klass.equals(symbolKlassHandle))              return new Symbol(handle, this);

      if (klass.equals(constantPoolKlassHandle))        return new ConstantPool(handle, this);

      if (klass.equals(constantPoolCacheKlassHandle))   return new ConstantPoolCache(handle, this);

      if (!VM.getVM().isCore()) {

        if (klass.equals(compiledICHolderKlassHandle))  return new CompiledICHolder(handle, this);

        if (klass.equals(methodDataKlassHandle))        return new MethodData(handle, this);

      }

      if (klass.equals(instanceKlassKlassHandle))       return new InstanceKlass(handle, this);

      if (klass.equals(objArrayKlassKlassHandle))       return new ObjArrayKlass(handle, this);

      if (klass.equals(typeArrayKlassKlassHandle))      return new TypeArrayKlass(handle, this);

      // Lastly check if obj.klass().klass() is on of the root objects

      OopHandle klassKlass = Oop.getKlassForOopHandle(klass);

      if (klassKlass != null) {

        if (klassKlass.equals(instanceKlassKlassHandle))    return new Instance(handle, this);

        if (klassKlass.equals(objArrayKlassKlassHandle))    return new ObjArray(handle, this);

        if (klassKlass.equals(typeArrayKlassKlassHandle))   return new TypeArray(handle, this);

      }

    }

    System.err.println("Unknown oop at " + handle);

    System.err.println("Oop's klass is " + klass);

    throw new UnknownOopException();

  }

  // Print all objects in the object heap

  public void print() {

    HeapPrinter printer = new HeapPrinter(System.out);

    iterate(printer);

  }

  //---------------------------------------------------------------------------

  // Internals only below this point

  //

  private void iterateExact(HeapVisitor visitor, final Klass k) {

    iterateLiveRegions(collectLiveRegions(), visitor, new ObjectFilter() {

          public boolean canInclude(Oop obj) {

            Klass tk = obj.getKlass();

            // null Klass is seen sometimes!

            return (tk != null && tk.equals(k));

          }

        });

  }

  private void iterateSubtypes(HeapVisitor visitor, final Klass k) {

    iterateLiveRegions(collectLiveRegions(), visitor, new ObjectFilter() {

          public boolean canInclude(Oop obj) {

            Klass tk = obj.getKlass();

            // null Klass is seen sometimes!

            return (tk != null && tk.isSubtypeOf(k));

          }

        });

  }

  private void iterateLiveRegions(List liveRegions, HeapVisitor visitor, ObjectFilter of) {

    // Summarize size

    long totalSize = 0;

    for (int i = 0; i < liveRegions.size(); i += 2) {

      Address bottom = (Address) liveRegions.get(i);

      Address top    = (Address) liveRegions.get(i+1);

      totalSize += top.minus(bottom);

    }

    visitor.prologue(totalSize);

    CompactibleFreeListSpace cmsSpaceOld = null;

    CompactibleFreeListSpace cmsSpacePerm = null;

    CollectedHeap heap = VM.getVM().getUniverse().heap();

    if (heap instanceof GenCollectedHeap) {

      GenCollectedHeap genHeap = (GenCollectedHeap) heap;

      Generation genOld = genHeap.getGen(1);

      Generation genPerm = genHeap.permGen();

      if (genOld instanceof ConcurrentMarkSweepGeneration) {

          ConcurrentMarkSweepGeneration concGen = (ConcurrentMarkSweepGeneration)genOld;

          cmsSpaceOld = concGen.cmsSpace();

      }

      if (genPerm instanceof ConcurrentMarkSweepGeneration) {

          ConcurrentMarkSweepGeneration concGen = (ConcurrentMarkSweepGeneration)genPerm;

          cmsSpacePerm = concGen.cmsSpace();

      }

    }

    for (int i = 0; i < liveRegions.size(); i += 2) {

      Address bottom = (Address) liveRegions.get(i);

      Address top    = (Address) liveRegions.get(i+1);

      try {

        // Traverses the space from bottom to top

        OopHandle handle = bottom.addOffsetToAsOopHandle(0);

        while (handle.lessThan(top)) {

        Oop obj = null;

          try {

            obj = newOop(handle);

          } catch (UnknownOopException exp) {

          }

          if (obj == null) {

             //Find the object size using Printezis bits and skip over

             System.err.println("Finding object size using Printezis bits and skipping over...");

             long size = 0;

             if ( (cmsSpaceOld != null) && cmsSpaceOld.contains(handle) ){

                 size = cmsSpaceOld.collector().blockSizeUsingPrintezisBits(handle);

             } else if ((cmsSpacePerm != null) && cmsSpacePerm.contains(handle) ){

                 size = cmsSpacePerm.collector().blockSizeUsingPrintezisBits(handle);

             }

             if (size <= 0) {

                //Either Printezis bits not set or handle is not in cms space.

                throw new UnknownOopException();

             }

             handle = handle.addOffsetToAsOopHandle(CompactibleFreeListSpace.adjustObjectSizeInBytes(size));

             continue;

          }

          if (of == null || of.canInclude(obj)) {

                  if (visitor.doObj(obj)) {

                         // doObj() returns true to abort this loop.

                          break;

                  }

          }

          if ( (cmsSpaceOld != null) && cmsSpaceOld.contains(handle) ||

               (cmsSpacePerm != null) && cmsSpacePerm.contains(handle) ) {

              handle = handle.addOffsetToAsOopHandle(CompactibleFreeListSpace.adjustObjectSizeInBytes(obj.getObjectSize()) );

          } else {

              handle = handle.addOffsetToAsOopHandle(obj.getObjectSize());

          }

        }

      }

      catch (AddressException e) {

        // This is okay at the top of these regions

      }

      catch (UnknownOopException e) {

        // This is okay at the top of these regions

      }

    }

    visitor.epilogue();

  }

  private void addPermGenLiveRegions(List output, CollectedHeap heap) {

    LiveRegionsCollector lrc = new LiveRegionsCollector(output);

    if (heap instanceof GenCollectedHeap) {

       GenCollectedHeap genHeap = (GenCollectedHeap) heap;

       Generation gen = genHeap.permGen();

       gen.spaceIterate(lrc, true);

    } else if (heap instanceof ParallelScavengeHeap) {

       ParallelScavengeHeap psh = (ParallelScavengeHeap) heap;

       PSPermGen permGen = psh.permGen();

       addLiveRegions(permGen.objectSpace().getLiveRegions(), output);

    } else {

       if (Assert.ASSERTS_ENABLED) {

          Assert.that(false, "Expecting GenCollectedHeap or ParallelScavengeHeap, but got " +

                             heap.getClass().getName());

       }

    }

  }

  private void addLiveRegions(List input, List output) {

     for (Iterator itr = input.iterator(); itr.hasNext();) {

        MemRegion reg = (MemRegion) itr.next();

        Address top = reg.end();

        Address bottom = reg.start();

        if (Assert.ASSERTS_ENABLED) {

           Assert.that(top != null, "top address in a live region should not be null");

        }

        if (Assert.ASSERTS_ENABLED) {

           Assert.that(bottom != null, "bottom address in a live region should not be null");

        }

        output.add(top);

        output.add(bottom);

     }

  }

  private class LiveRegionsCollector implements SpaceClosure {

     LiveRegionsCollector(List l) {