/******************************************************************************* | |
* Copyright (c) 2008, 2019 SAP AG and others. | |
* All rights reserved. This program and the accompanying materials | |
* are made available under the terms of the Eclipse Public License v1.0 | |
* which accompanies this distribution, and is available at | |
* http://www.eclipse.org/legal/epl-v10.html | |
* | |
* Contributors: | |
* SAP AG - initial API and implementation | |
* Netflix (Jason Koch) - refactors for increased performance and concurrency | |
*******************************************************************************/ | |
package org.eclipse.mat.parser.internal; | |
import java.io.File; | |
import java.io.IOException; | |
import java.io.Serializable; | |
import java.util.ArrayList; | |
import java.util.Collections; | |
import java.util.HashMap; | |
import java.util.Iterator; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.concurrent.Callable; | |
import java.util.concurrent.ExecutionException; | |
import java.util.concurrent.ExecutorService; | |
import java.util.concurrent.Executors; | |
import java.util.concurrent.Future; | |
import org.eclipse.mat.collect.ArrayInt; | |
import org.eclipse.mat.collect.BitField; | |
import org.eclipse.mat.collect.HashMapIntObject; | |
import org.eclipse.mat.collect.IteratorInt; | |
import org.eclipse.mat.parser.index.IIndexReader.IOne2LongIndex; | |
import org.eclipse.mat.parser.index.IIndexReader.IOne2ManyIndex; | |
import org.eclipse.mat.parser.index.IIndexReader.IOne2OneIndex; | |
import org.eclipse.mat.parser.index.IIndexReader.IOne2SizeIndex; | |
import org.eclipse.mat.parser.index.IndexManager; | |
import org.eclipse.mat.parser.index.IndexManager.Index; | |
import org.eclipse.mat.parser.index.IndexReader.SizeIndexReader; | |
import org.eclipse.mat.parser.index.IndexWriter; | |
import org.eclipse.mat.parser.index.IndexWriter.IntIndexStreamer; | |
import org.eclipse.mat.parser.index.IndexWriter.LongIndexStreamer; | |
import org.eclipse.mat.parser.internal.snapshot.ObjectMarker; | |
import org.eclipse.mat.parser.model.ClassImpl; | |
import org.eclipse.mat.parser.model.XGCRootInfo; | |
import org.eclipse.mat.snapshot.UnreachableObjectsHistogram; | |
import org.eclipse.mat.snapshot.model.IClass; | |
import org.eclipse.mat.util.IProgressListener; | |
import org.eclipse.mat.util.IProgressListener.OperationCanceledException; | |
import org.eclipse.mat.util.IProgressListener.Severity; | |
import org.eclipse.mat.util.MessageUtil; | |
import org.eclipse.mat.util.SilentProgressListener; | |
/* package */class GarbageCleaner | |
{ | |
private final static int PARALLEL_CHUNK_SIZE = 16*1024*1024; | |
public static int[] clean(final PreliminaryIndexImpl idx, final SnapshotImplBuilder builder, | |
Map<String, String> arguments, IProgressListener listener) | |
throws IOException, InterruptedException, ExecutionException | |
{ | |
IndexManager idxManager = new IndexManager(); | |
ExecutorService es = Executors.newWorkStealingPool(); | |
try | |
{ | |
listener.beginTask(Messages.GarbageCleaner_RemovingUnreachableObjects, 11); | |
listener.subTask(Messages.GarbageCleaner_SearchingForUnreachableObjects); | |
final int oldNoOfObjects = idx.identifiers.size(); | |
// determine reachable objects | |
boolean[] reachable = new boolean[oldNoOfObjects]; | |
int newNoOfObjects = 0; | |
int[] newRoots = idx.gcRoots.getAllKeys(); | |
IOne2LongIndex identifiers = idx.identifiers; | |
IOne2ManyIndex preOutbound = idx.outbound; | |
IOne2OneIndex object2classId = idx.object2classId; | |
HashMapIntObject<ClassImpl> classesById = idx.classesById; | |
/* | |
* START - marking objects use ObjectMarker to mark the reachable | |
* objects if more than 1 CPUs are available - use multithreading | |
*/ | |
ObjectMarker marker = new ObjectMarker(newRoots, reachable, preOutbound, new SilentProgressListener( | |
listener)); | |
int numProcessors = Runtime.getRuntime().availableProcessors(); | |
if (numProcessors > 1) | |
{ | |
try | |
{ | |
marker.markMultiThreaded(numProcessors); | |
} | |
catch (InterruptedException e) | |
{ | |
IOException ioe = new IOException(e.getMessage()); | |
ioe.initCause(e); | |
throw ioe; | |
} | |
// find the number of new objects. It's not returned by marker | |
for (boolean b : reachable) | |
if (b) | |
newNoOfObjects++; | |
} | |
else | |
{ | |
try | |
{ | |
newNoOfObjects = marker.markSingleThreaded(); | |
} | |
catch (OperationCanceledException e) | |
{ | |
// $JL-EXC$ | |
return null; | |
} | |
} | |
marker = null; | |
/* END - marking objects */ | |
// check if unreachable objects exist, then either mark as GC root | |
// unreachable (keep objects) or store a histogram of unreachable | |
// objects | |
if (newNoOfObjects < oldNoOfObjects) | |
{ | |
Object un = idx.getSnapshotInfo().getProperty("keep_unreachable_objects"); //$NON-NLS-1$ | |
if (un instanceof Integer) | |
{ | |
int newRoot; | |
newRoot = (Integer)un; | |
newNoOfObjects = markUnreachableAsGCRoots(idx, reachable, newNoOfObjects, newRoot, listener); | |
} | |
if (newNoOfObjects < oldNoOfObjects) | |
{ | |
createHistogramOfUnreachableObjects(es, idx, reachable); | |
} | |
} | |
if (listener.isCanceled()) | |
throw new IProgressListener.OperationCanceledException(); | |
listener.worked(1); // 3 | |
listener.subTask(Messages.GarbageCleaner_ReIndexingObjects); | |
// create re-index map | |
final int[] map = new int[oldNoOfObjects]; | |
final long[] id2a = new long[newNoOfObjects]; | |
List<ClassImpl> classes2remove = new ArrayList<ClassImpl>(); | |
final IOne2SizeIndex preA2size = idx.array2size; | |
long memFree = 0; | |
for (int ii = 0, jj = 0; ii < oldNoOfObjects; ii++) | |
{ | |
if (reachable[ii]) | |
{ | |
map[ii] = jj; | |
id2a[jj++] = identifiers.get(ii); | |
} | |
else | |
{ | |
map[ii] = -1; | |
} | |
} | |
ArrayList<Callable<CleanupWrapper>> tasks = new ArrayList<Callable<CleanupWrapper>>(); | |
for(int i = 0; i < oldNoOfObjects; i += PARALLEL_CHUNK_SIZE) { | |
final int start = i; | |
final int length = Math.min(PARALLEL_CHUNK_SIZE, reachable.length - start); | |
tasks.add(new CalculateGarbageCleanupForClass(idx, reachable, start, length)); | |
} | |
List<Future<CleanupWrapper>> wrappers = null; | |
wrappers = es.invokeAll(tasks); | |
for(Future<CleanupWrapper> wrapper : wrappers) { | |
for(CleanupResult cr : wrapper.get().results.values()) { | |
long totalmem = cr.size; | |
for (int i = cr.count; i > 0; --i) | |
{ | |
// Remove one by one as removeInstanceBulk is not yet API | |
long instsize = totalmem / i; | |
totalmem -= instsize; | |
cr.clazz.removeInstance(instsize); | |
} | |
memFree += cr.size; | |
} | |
for(ClassImpl c : wrapper.get().classes2remove) | |
{ | |
classes2remove.add(c); | |
} | |
} | |
if (newNoOfObjects < oldNoOfObjects) | |
{ | |
listener.sendUserMessage(Severity.INFO, MessageUtil.format( | |
Messages.GarbageCleaner_RemovedUnreachableObjects, oldNoOfObjects | |
- newNoOfObjects, memFree), null); | |
} | |
es.shutdown(); | |
// classes cannot be removed right away | |
// as they are needed to remove instances of this class | |
for (ClassImpl c : classes2remove) | |
{ | |
classesById.remove(c.getObjectId()); | |
ClassImpl superclass = classesById.get(c.getSuperClassId()); | |
if (superclass != null) | |
superclass.removeSubClass(c); | |
} | |
reachable = null; // early gc... | |
identifiers.close(); | |
identifiers.delete(); | |
identifiers = null; | |
if (listener.isCanceled()) | |
throw new IProgressListener.OperationCanceledException(); | |
listener.worked(1); // 4 | |
listener.subTask(Messages.GarbageCleaner_ReIndexingClasses); | |
// fix classes | |
HashMapIntObject<ClassImpl> classesByNewId = new HashMapIntObject<ClassImpl>(classesById.size()); | |
for (Iterator<ClassImpl> iter = classesById.values(); iter.hasNext();) | |
{ | |
ClassImpl clazz = iter.next(); | |
int index = map[clazz.getObjectId()]; | |
clazz.setObjectId(index); | |
if (clazz.getSuperClassId() >= 0) // java.lang.Object | |
clazz.setSuperClassIndex(map[clazz.getSuperClassId()]); | |
clazz.setClassLoaderIndex(map[clazz.getClassLoaderId()]); | |
classesByNewId.put(index, clazz); | |
} | |
idx.getSnapshotInfo().setNumberOfClasses(classesByNewId.size()); | |
if (listener.isCanceled()) | |
throw new IProgressListener.OperationCanceledException(); | |
listener.worked(1); // 5 | |
// ////////////////////////////////////////////////////////////// | |
// identifiers | |
// ////////////////////////////////////////////////////////////// | |
File indexFile = Index.IDENTIFIER.getFile(idx.snapshotInfo.getPrefix()); | |
listener.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, indexFile.getAbsolutePath())); | |
idxManager.setReader(Index.IDENTIFIER, new LongIndexStreamer().writeTo(indexFile, id2a)); | |
if (listener.isCanceled()) | |
throw new IProgressListener.OperationCanceledException(); | |
listener.worked(1); // 6 | |
// ////////////////////////////////////////////////////////////// | |
// object 2 class Id | |
// ////////////////////////////////////////////////////////////// | |
indexFile = Index.O2CLASS.getFile(idx.snapshotInfo.getPrefix()); | |
listener.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, indexFile.getAbsolutePath())); | |
idxManager.setReader(Index.O2CLASS, new IntIndexStreamer().writeTo(indexFile, | |
new NewObjectIntIterator() | |
{ | |
@Override | |
int doGetNextInt(int index) | |
{ | |
return map[idx.object2classId.get(nextIndex)]; | |
// return | |
// map[object2classId.get(nextIndex)]; | |
} | |
@Override | |
int[] getMap() | |
{ | |
return map; | |
} | |
})); | |
object2classId.close(); | |
object2classId.delete(); | |
object2classId = null; | |
if (listener.isCanceled()) | |
throw new IProgressListener.OperationCanceledException(); | |
listener.worked(1); // 7 | |
// ////////////////////////////////////////////////////////////// | |
// array size | |
// ////////////////////////////////////////////////////////////// | |
indexFile = Index.A2SIZE.getFile(idx.snapshotInfo.getPrefix()); | |
listener.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, new Object[] { indexFile | |
.getAbsolutePath() })); | |
final BitField arrayObjects = new BitField(newNoOfObjects); | |
// arrayObjects | |
IOne2OneIndex newIdx = new IntIndexStreamer().writeTo(indexFile, | |
new NewObjectIntIterator() | |
{ | |
IOne2SizeIndex a2size = preA2size; | |
int newIndex = 0; | |
@Override | |
int doGetNextInt(int index) | |
{ | |
int size = a2size.get(nextIndex); | |
// Get the compressed size, 0 means 0 | |
if (size != 0) | |
arrayObjects.set(newIndex); | |
newIndex++; | |
return size; | |
} | |
@Override | |
int[] getMap() | |
{ | |
return map; | |
} | |
}); | |
idxManager.setReader(Index.A2SIZE, new SizeIndexReader(newIdx)); | |
preA2size.close(); | |
preA2size.delete(); | |
if (listener.isCanceled()) | |
throw new IProgressListener.OperationCanceledException(); | |
listener.worked(1); // 9 | |
// ////////////////////////////////////////////////////////////// | |
// inbound, outbound | |
// ////////////////////////////////////////////////////////////// | |
listener.subTask(Messages.GarbageCleaner_ReIndexingOutboundIndex); | |
IndexWriter.IntArray1NSortedWriter w_out = new IndexWriter.IntArray1NSortedWriter(newNoOfObjects, | |
IndexManager.Index.OUTBOUND.getFile(idx.snapshotInfo.getPrefix())); | |
IndexWriter.InboundWriter w_in = new IndexWriter.InboundWriter(newNoOfObjects, IndexManager.Index.INBOUND | |
.getFile(idx.snapshotInfo.getPrefix())); | |
for (int ii = 0; ii < oldNoOfObjects; ii++) | |
{ | |
int k = map[ii]; | |
if (k < 0) continue; | |
int[] a = preOutbound.get(ii); | |
int[] tl = new int[a.length]; | |
for (int jj = 0; jj < a.length; jj++) | |
{ | |
int t = map[a[jj]]; | |
/* No check if the referenced objects are alive */ | |
/* The garbage can't be reached from a live object */ | |
// removed if (t >= 0) ... | |
tl[jj] = t; | |
w_in.log(t, k, jj == 0); | |
} | |
w_out.log(k, tl); | |
} | |
preOutbound.close(); | |
preOutbound.delete(); | |
preOutbound = null; | |
if (listener.isCanceled()) | |
{ | |
w_in.cancel(); | |
w_out.cancel(); | |
throw new IProgressListener.OperationCanceledException(); | |
} | |
listener.worked(1); // 10 | |
listener | |
.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, w_in.getIndexFile() | |
.getAbsolutePath())); | |
idxManager.setReader(Index.INBOUND, w_in.flush(listener, new KeyWriterImpl(classesByNewId))); | |
w_in = null; | |
if (listener.isCanceled()) | |
{ | |
w_out.cancel(); | |
throw new IProgressListener.OperationCanceledException(); | |
} | |
listener.worked(1); // 11 | |
listener.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, new Object[] { w_out.getIndexFile() | |
.getAbsolutePath() })); | |
idxManager.setReader(Index.OUTBOUND, w_out.flush()); | |
w_out = null; | |
if (listener.isCanceled()) | |
throw new IProgressListener.OperationCanceledException(); | |
listener.worked(1); // 12 | |
// fix roots | |
HashMapIntObject<XGCRootInfo[]> roots = fix(idx.gcRoots, map); | |
idx.getSnapshotInfo().setNumberOfGCRoots(roots.size()); | |
// fix threads 2 objects 2 roots | |
HashMapIntObject<HashMapIntObject<XGCRootInfo[]>> rootsPerThread = new HashMapIntObject<HashMapIntObject<XGCRootInfo[]>>(); | |
for (IteratorInt iter = idx.thread2objects2roots.keys(); iter.hasNext();) | |
{ | |
int threadId = iter.next(); | |
int fixedThreadId = map[threadId]; | |
if (fixedThreadId < 0) | |
continue; | |
rootsPerThread.put(fixedThreadId, fix(idx.thread2objects2roots.get(threadId), map)); | |
} | |
// fill stuff into builder | |
builder.setIndexManager(idxManager); | |
builder.setClassCache(classesByNewId); | |
builder.setArrayObjects(arrayObjects); | |
builder.setRoots(roots); | |
builder.setRootsPerThread(rootsPerThread); | |
return map; | |
} | |
finally | |
{ | |
// delete all temporary indices | |
idx.delete(); | |
if (idxManager != null && listener.isCanceled()) | |
idxManager.delete(); | |
} | |
} | |
private static HashMapIntObject<XGCRootInfo[]> fix(HashMapIntObject<List<XGCRootInfo>> roots, final int[] map) | |
{ | |
HashMapIntObject<XGCRootInfo[]> answer = new HashMapIntObject<XGCRootInfo[]>(roots.size()); | |
for (Iterator<List<XGCRootInfo>> iter = roots.values(); iter.hasNext();) | |
{ | |
List<XGCRootInfo> r = iter.next(); | |
XGCRootInfo[] a = new XGCRootInfo[r.size()]; | |
for (int ii = 0; ii < a.length; ii++) | |
{ | |
a[ii] = r.get(ii); | |
a[ii].setObjectId(map[a[ii].getObjectId()]); | |
if (a[ii].getContextAddress() != 0) | |
a[ii].setContextId(map[a[ii].getContextId()]); | |
} | |
answer.put(a[0].getObjectId(), a); | |
} | |
return answer; | |
} | |
private static abstract class NewObjectIterator | |
{ | |
int nextIndex = -1; | |
int[] $map; | |
public NewObjectIterator() | |
{ | |
$map = getMap(); | |
findNext(); | |
} | |
protected void findNext() | |
{ | |
nextIndex++; | |
while (nextIndex < $map.length && $map[nextIndex] < 0) | |
nextIndex++; | |
} | |
public boolean hasNext() | |
{ | |
return nextIndex < $map.length; | |
} | |
abstract int[] getMap(); | |
} | |
private static abstract class NewObjectIntIterator extends NewObjectIterator implements IteratorInt | |
{ | |
public int next() | |
{ | |
int answer = doGetNextInt(nextIndex); | |
findNext(); | |
return answer; | |
} | |
abstract int doGetNextInt(int nextIndex); | |
} | |
private static class KeyWriterImpl implements IndexWriter.KeyWriter | |
{ | |
HashMapIntObject<ClassImpl> classesByNewId; | |
KeyWriterImpl(HashMapIntObject<ClassImpl> classesByNewId) | |
{ | |
this.classesByNewId = classesByNewId; | |
} | |
public void storeKey(int index, Serializable key) | |
{ | |
ClassImpl impl = classesByNewId.get(index); | |
impl.setCacheEntry(key); | |
} | |
} | |
// ////////////////////////////////////////////////////////////// | |
// create histogram of unreachable objects | |
// ////////////////////////////////////////////////////////////// | |
private static final class Record | |
{ | |
ClassImpl clazz; | |
int objectCount; | |
long size; | |
public Record(ClassImpl clazz) | |
{ | |
this.clazz = clazz; | |
} | |
} | |
private static void createHistogramOfUnreachableObjects(final ExecutorService es, | |
final PreliminaryIndexImpl idx, final boolean[] reachable) | |
throws InterruptedException, ExecutionException | |
{ | |
ArrayList<Callable<HashMap<Integer, Record>>> tasks = new ArrayList<Callable<HashMap<Integer, Record>>>(); | |
for(int i = 0; i < reachable.length; i += PARALLEL_CHUNK_SIZE) { | |
final int start = i; | |
final int length = Math.min(PARALLEL_CHUNK_SIZE, reachable.length - start); | |
tasks.add(new CreateHistogramOfUnreachableObjectsChunk(idx, reachable, start, length)); | |
} | |
List<Future<HashMap<Integer, Record>>> results = null; | |
results = es.invokeAll(tasks); | |
final HashMap<Integer, Record> histogram = new HashMap<Integer, Record>(reachable.length); | |
for(Future<HashMap<Integer, Record>> subhistogram : results) { | |
histogram.putAll(subhistogram.get()); | |
} | |
List<UnreachableObjectsHistogram.Record> records = new ArrayList<UnreachableObjectsHistogram.Record>(); | |
for(Record r : histogram.values()) { | |
records.add(new UnreachableObjectsHistogram.Record( | |
r.clazz.getName(), | |
r.clazz.getObjectAddress(), | |
r.objectCount, | |
r.size)); | |
} | |
UnreachableObjectsHistogram deadObjectHistogram = new UnreachableObjectsHistogram(records); | |
idx.getSnapshotInfo().setProperty(UnreachableObjectsHistogram.class.getName(), deadObjectHistogram); | |
} | |
private static class CreateHistogramOfUnreachableObjectsChunk implements Callable<HashMap<Integer, Record>> | |
{ | |
final PreliminaryIndexImpl idx; | |
final boolean[] reachable; | |
final int start; | |
final int length; | |
public CreateHistogramOfUnreachableObjectsChunk(PreliminaryIndexImpl idx, | |
boolean[] reachable, int start, int length) | |
{ | |
this.idx = idx; | |
this.reachable = reachable; | |
this.start = start; | |
this.length = length; | |
} | |
public HashMap<Integer, Record> call() { | |
IOne2SizeIndex array2size = idx.array2size; | |
HashMap<Integer, Record> histogram = new HashMap<Integer, Record>(length); | |
for (int ii = start; ii < (start + length); ii++) | |
{ | |
if (!reachable[ii]) | |
{ | |
final int classId = idx.object2classId.get(ii); | |
Record r = histogram.get(classId); | |
if (r == null) | |
{ | |
r = new Record(idx.classesById.get(classId)); | |
histogram.put(classId, r); | |
} | |
long s = array2size.getSize(ii); | |
if (s > 0) | |
{ | |
// Already got the size | |
} | |
else if (IClass.JAVA_LANG_CLASS.equals(r.clazz.getName())) | |
{ | |
ClassImpl classImpl = idx.classesById.get(ii); | |
if (classImpl == null) | |
{ | |
s = r.clazz.getHeapSizePerInstance(); | |
} | |
else | |
{ | |
s = classImpl.getUsedHeapSize(); | |
} | |
} | |
else | |
{ | |
s = r.clazz.getHeapSizePerInstance(); | |
} | |
r.size += s; | |
r.objectCount += 1; | |
} | |
} | |
return histogram; | |
} | |
} | |
// ////////////////////////////////////////////////////////////// | |
// calculate garbage cleanup | |
// ////////////////////////////////////////////////////////////// | |
private static class CleanupWrapper { | |
final HashMap<Integer, CleanupResult> results; | |
final List<ClassImpl> classes2remove; | |
public CleanupWrapper(final HashMap<Integer, CleanupResult> results, final List<ClassImpl> classes2remove) | |
{ | |
this.results = results; | |
this.classes2remove = classes2remove; | |
} | |
} | |
private static class CleanupResult { | |
int count = 0; | |
long size = 0; | |
final ClassImpl clazz; | |
public CleanupResult(ClassImpl clazz) | |
{ | |
this.clazz = clazz; | |
} | |
} | |
private static class CalculateGarbageCleanupForClass implements Callable<CleanupWrapper> | |
{ | |
final PreliminaryIndexImpl idx; | |
final boolean[] reachable; | |
final int start; | |
final int length; | |
public CalculateGarbageCleanupForClass(PreliminaryIndexImpl idx, | |
boolean[] reachable, int start, int length) | |
{ | |
this.idx = idx; | |
this.reachable = reachable; | |
this.start = start; | |
this.length = length; | |
} | |
public CleanupWrapper call() throws Exception | |
{ | |
HashMap<Integer, CleanupResult> results = new HashMap<Integer, CleanupResult>(); | |
List<ClassImpl> classes2remove = new ArrayList<ClassImpl>(); | |
for (int ii = start; ii < (start + length); ii++) | |
{ | |
if (reachable[ii]) | |
continue; | |
int classId = idx.object2classId.get(ii); | |
ClassImpl clazz = idx.classesById.get(classId); | |
CleanupResult cr = results.get(classId); | |
if (cr == null) | |
{ | |
cr = new CleanupResult(clazz); | |
results.put(classId, cr); | |
} | |
long arraySize = idx.array2size.getSize(ii); | |
if (arraySize > 0) | |
{ | |
cr.count += 1; | |
cr.size += arraySize; | |
} | |
else | |
{ | |
// [INFO] some instances of java.lang.Class are not | |
// reported as HPROF_GC_CLASS_DUMP but as | |
// HPROF_GC_INSTANCE_DUMP | |
ClassImpl c = idx.classesById.get(ii); | |
if (c == null) | |
{ | |
cr.count += 1; | |
cr.size += clazz.getHeapSizePerInstance(); | |
} | |
else | |
{ | |
cr.count += 1; | |
cr.size += c.getUsedHeapSize(); | |
classes2remove.add(c); | |
} | |
} | |
} | |
return new CleanupWrapper(results, classes2remove); | |
} | |
} | |
// ////////////////////////////////////////////////////////////// | |
// mark unreachable objects as GC unknown | |
// ////////////////////////////////////////////////////////////// | |
private static int markUnreachableAsGCRoots(final PreliminaryIndexImpl idx, // | |
boolean[] reachable, // | |
int noReachableObjects, // | |
int extraRootType, IProgressListener listener) | |
{ | |
final int noOfObjects = reachable.length; | |
final IOne2LongIndex identifiers = idx.identifiers; | |
final IOne2ManyIndex preOutbound = idx.outbound; | |
// find objects not referenced by any other object | |
byte inbounds[] = new byte[noOfObjects]; | |
for (int ii = 0; ii < noOfObjects; ++ii) | |
{ | |
if (!reachable[ii]) | |
{ | |
// We only need search the unreachable objects as | |
// the reachable ones will have already marked | |
// its outbound refs. | |
for (int out : preOutbound.get(ii)) | |
{ | |
// Exclude objects pointing to themselves | |
if (out != ii) | |
{ | |
// Avoid overflow | |
if (inbounds[out] != -1) inbounds[out]++; | |
} | |
} | |
} | |
} | |
// First pass mark only the unreferenced objects | |
ArrayInt unref = new ArrayInt(); | |
for (int ii = 0; ii < noOfObjects; ++ii) | |
{ | |
// Do the objects with no inbounds first | |
if (!reachable[ii] && inbounds[ii] == 0) | |
{ | |
// Identify this unreachable object as a root, | |
// No need to mark it as the marker will do that | |
unref.add(ii); | |
XGCRootInfo xgc = new XGCRootInfo(identifiers.get(ii), 0, extraRootType); | |
xgc.setObjectId(ii); | |
List<XGCRootInfo> xgcs = Collections.singletonList(xgc); | |
idx.gcRoots.put(ii, xgcs); | |
} | |
} | |
// See what else is now reachable | |
ObjectMarker marker2 = new ObjectMarker(unref.toArray(), reachable, preOutbound, new SilentProgressListener(listener)); | |
int numProcessors = Runtime.getRuntime().availableProcessors(); | |
if (numProcessors > 1 && unref.size() > 1) | |
{ | |
try | |
{ | |
marker2.markMultiThreaded(numProcessors); | |
} | |
catch (InterruptedException e) | |
{ | |
OperationCanceledException oc = new IProgressListener.OperationCanceledException(); | |
oc.initCause(e); | |
throw oc; | |
} | |
// find the number of new objects. It's not returned by marker | |
int newNoOfObjects = 0; | |
for (boolean b : reachable) | |
if (b) | |
newNoOfObjects++; | |
noReachableObjects = newNoOfObjects; | |
} | |
else | |
{ | |
int marked2 = marker2.markSingleThreaded(); | |
noReachableObjects += marked2; | |
} | |
// find remaining unreachable objects | |
unref.clear(); | |
for (int ii = 0; ii < noOfObjects; ++ii) | |
{ | |
if (!reachable[ii]) | |
{ | |
// Add to list | |
unref.add(ii); | |
} | |
} | |
int root[] = new int[1]; | |
ObjectMarker marker = new ObjectMarker(root, reachable, preOutbound, new SilentProgressListener(listener)); | |
int passes = 10; | |
for (int pass = 0; pass < passes; ++pass) | |
{ | |
// find remaining unreachable objects | |
ArrayInt unref2 = new ArrayInt(); | |
byte outbounds[] = new byte[noOfObjects]; | |
for (IteratorInt it = unref.iterator(); it.hasNext();) | |
{ | |
int ii = it.next(); | |
if (!reachable[ii]) | |
{ | |
// We only need search the unreachable objects as | |
// the reachable ones will have already marked | |
// its outbound refs. | |
unref2.add(ii); | |
for (int out : preOutbound.get(ii)) | |
{ | |
// Exclude objects pointing to themselves | |
// and only count unreachable refs | |
// We only need to recount outbound refs as the | |
// inbound ref count will be unchanged. | |
if (out != ii && !reachable[out]) | |
{ | |
// Avoid overflow | |
if (outbounds[ii] != -1) outbounds[ii]++; | |
} | |
} | |
} | |
} | |
unref = unref2; | |
// choose some of the remaining unreachable objects as roots | |
for (IteratorInt it = unref.iterator(); it.hasNext() && noReachableObjects < noOfObjects;) | |
{ | |
int ii = it.next(); | |
ii = selectRoot(ii, pass, passes, reachable, preOutbound, outbounds, inbounds); | |
if (ii >= 0) { | |
// Identify this unreachable object as a root, | |
// and see what else is now reachable | |
// No need to mark it as the marker will do that | |
root[0] = ii; | |
XGCRootInfo xgc = new XGCRootInfo(identifiers.get(ii), 0, extraRootType); | |
xgc.setObjectId(ii); | |
List<XGCRootInfo> xgcs = Collections.singletonList(xgc); | |
idx.gcRoots.put(ii, xgcs); | |
int marked = marker.markSingleThreaded(); | |
noReachableObjects += marked; | |
} | |
} | |
} | |
// update GC root information | |
idx.setGcRoots(idx.gcRoots); | |
idx.getSnapshotInfo().setNumberOfGCRoots(idx.gcRoots.size()); | |
return noReachableObjects; | |
} | |
/** | |
* Decide on next root to choose. | |
* A sophisticated version would convert the object graph to a DAG | |
* of strongly connected components and choose an example member from | |
* each (currently unreached) source strongly connected component. | |
* This version is not minimal but covers the object graph. | |
* @param ii candidate root | |
* @param pass from 0 to passes -1 | |
* @param passes number of passes | |
* @param reachable which object have already been marked | |
* @param preOutbound the outbound refs for each object | |
* @param outbounds count of outbounds (as 0..255) | |
* @param inbounds count of inbounds (as 0..255) | |
* @return candidate root or -1 | |
*/ | |
private static int selectRoot(int ii, int pass, int passes, boolean[] reachable, final IOne2ManyIndex preOutbound, | |
byte[] outbounds, byte[] inbounds) | |
{ | |
if (reachable[ii]) | |
return -1; | |
// Check for objects with 1 inbound, pointing to another object | |
// with 1 inbound, pointing back to this. | |
// The cycle has no entry, so must be a root. | |
if (pass == 0) | |
{ | |
if ((inbounds[ii] & 0xff) == 1) | |
{ | |
for (int out : preOutbound.get(ii)) | |
{ | |
// Exclude objects pointing to themselves | |
// and only count unreachable refs | |
if (out != ii && !reachable[out]) | |
{ | |
if ((inbounds[out] & 0xff) != 1) | |
continue; | |
for (int out2 : preOutbound.get(out)) | |
{ | |
if (out2 == ii) | |
{ | |
// Choose as a root as this cycle of objects | |
// has no external entry | |
return ii; | |
} | |
} | |
} | |
} | |
} | |
return -1; | |
} | |
// Don't do objects with only one inbound until the end as perhaps the | |
// predecessor will get marked. | |
// Don't choose an object with no unref outbounds as we should choose a | |
// predecessor of this object instead. | |
// Choose objects with lots of outbounds first as they might mark | |
// a lot of objects. | |
boolean chooseAsRoot = (outbounds[ii] & 0xff) > 0 | |
&& (pass == passes - 1 || (inbounds[ii] & 0xff) > 1 | |
&& (outbounds[ii] & 0xff) - (inbounds[ii] & 0xff) >= passes - pass - 2); | |
return chooseAsRoot ? ii : -1; | |
} | |
} |