Attachment #285394 for bug #570670

View | Details | Raw Unified | Return to bug 570670 | Differences between
Collapse All | Expand All




import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveTask;
import java.util.stream.IntStream;

import org.eclipse.mat.collect.ArrayInt;
import org.eclipse.mat.collect.BitField;


/* 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
    {
        IndexManager idxManager = new IndexManager();
        ExecutorService es = Executors.newWorkStealingPool();

        try
        {

            // check if unreachable objects exist, then either mark as GC root
            // unreachable (keep objects) or store a histogram of unreachable
            // objects
            Map<Integer, Record> garbageHistogram = new GarbageHistogramTask(idx, reachable).invoke();

            if (newNoOfObjects < oldNoOfObjects)
            {
                Object un = idx.getSnapshotInfo().getProperty("keep_unreachable_objects"); //$NON-NLS-1$

                    int newRoot;
                    newRoot = (Integer)un;
                    newNoOfObjects = markUnreachableAsGCRoots(idx, reachable, newNoOfObjects, newRoot, listener);
                    // if we changed the class set, we need to re-calculate the histogram
                    garbageHistogram = new GarbageHistogramTask(idx, reachable).invoke();
                }
                if (newNoOfObjects < oldNoOfObjects)
                {
                    createHistogramOfUnreachableObjects(idx, garbageHistogram);
                }
            }


            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])

                }
            }

            garbageHistogram.values().parallelStream().forEach(gcRecord -> {
                long instsize = gcRecord.size / gcRecord.objectCount;
                long leftover = gcRecord.size % gcRecord.objectCount;

                // the first record will have the "remainder" also added in
                gcRecord.clazz.removeInstance(instsize + leftover);
                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);

                // start at i=1; as we have already completed one
                for (int i = 1; i < gcRecord.objectCount; i++)
                    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)
                {
                    gcRecord.clazz.removeInstance(instsize);
                }
            });

            long memFree = garbageHistogram.values().parallelStream().mapToLong(gcr -> gcr.size).sum();

            if (newNoOfObjects < oldNoOfObjects)
            {

                                                - newNoOfObjects, memFree), null);
            }

            es.shutdown();

            // classes cannot be removed right away
            // as they are needed to remove instances of this class
            for (Record gcRecord : garbageHistogram.values())
            {
                for (ClassImpl c : gcRecord.classesToRemove)
                {
                    classesById.remove(c.getObjectId());

                    ClassImpl superclass = classesById.get(c.getSuperClassId());
                    if (superclass != null)
                        superclass.removeSubClass(c);
                }
            }

            reachable = null; // early gc...

            // array size
            // //////////////////////////////////////////////////////////////

            final IOne2SizeIndex preA2size = idx.array2size;

            indexFile = Index.A2SIZE.getFile(idx.snapshotInfo.getPrefix());
            listener.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, new Object[] { indexFile
                            .getAbsolutePath() }));

                                }
                            });

            idxManager.setReader(Index.A2SIZE, new SizeIndexReader(newIdx));

            preA2size.close();
            preA2size.delete();

        ClassImpl clazz;
        int objectCount;
        long size;
        List<ClassImpl> classesToRemove = new ArrayList<>();

        public Record(ClassImpl clazz)
        {

        }
    }

    public static class GarbageHistogramTask extends RecursiveTask<HashMap<Integer, Record>>
                    final PreliminaryIndexImpl idx, final boolean[] reachable)
                                    throws InterruptedException, ExecutionException
    {
        final int BATCH_SIZE = 1_000_000;

        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());
        }

        /*
         * The parser might have already discarded some objects, so merge the histograms.
         */
        Serializable parserDeadObjects = idx.getSnapshotInfo().getProperty(UnreachableObjectsHistogram.class.getName());
        HashMap<Long, UnreachableObjectsHistogram.Record>parserRecords = new HashMap<Long, UnreachableObjectsHistogram.Record>();
        if (parserDeadObjects instanceof UnreachableObjectsHistogram)
        {
            UnreachableObjectsHistogram parserDeadObjectHistogram = (UnreachableObjectsHistogram)parserDeadObjects;
            for (UnreachableObjectsHistogram.Record r : parserDeadObjectHistogram.getRecords())
            {
                parserRecords.put(r.getClassAddress(), r);
            }
        }
        List<UnreachableObjectsHistogram.Record> records = new ArrayList<UnreachableObjectsHistogram.Record>();
        for(Record r : histogram.values()) {
            UnreachableObjectsHistogram.Record r2 = parserRecords.get(r.clazz.getObjectAddress());
            int existingCount = 0;
            long existingSize = 0L;
            if (r2 != null && r.clazz.getName().equals(r2.getClassName()))
            {
                existingCount = r2.getObjectCount();
                existingSize = r2.getShallowHeapSize();
                parserRecords.remove(r.clazz.getObjectAddress());
            }
            records.add(new UnreachableObjectsHistogram.Record(
                            r.clazz.getName(),
                            r.clazz.getObjectAddress(),
                            r.objectCount + existingCount,
                            r.size + existingSize));
        }
        records.addAll(parserRecords.values());

        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 end;

        GarbageHistogramTask(final PreliminaryIndexImpl idx, final boolean[] reachable)
        {
            this(idx, reachable, 0, reachable.length);
        }

        GarbageHistogramTask(final PreliminaryIndexImpl idx, final boolean[] reachable, final int start, final int end)
        {
            this.idx = idx;
            this.reachable = reachable;
            this.start = start;
            this.end = end;
        }

        protected HashMap<Integer, Record> directCompute()
        {
            HashMap<Integer, Record> results = new HashMap<Integer, Record>(end - start);
            for (int ii = start; ii < end; ii++)

            for (int ii = start; ii < (start + length); ii++)
            {
                if (!reachable[ii])
                {
                    final int objectNo = ii;
                    int classId = idx.object2classId.get(objectNo);
                    Record record = results.get(classId);
                    if (record == null)
                    {
                        record = new Record(idx.classesById.get(classId));
                        results.put(classId, record);
                    }

                    long size = 0;
                    if (record.clazz.isArrayType())
                    {
                        size = idx.array2size.getSize(objectNo);
                    }
                    else if (IClass.JAVA_LANG_CLASS.equals(record.clazz.getName()))
                    {
                        ClassImpl classImpl = idx.classesById.get(objectNo);
                        if (classImpl == null)
                        {
                            size = record.clazz.getHeapSizePerInstance();
                        }
                        else
                        {
                            size = classImpl.getUsedHeapSize();
                            record.classesToRemove.add(classImpl);
                        }
                    }
                    else
                    {
                        size = record.clazz.getHeapSizePerInstance();
                    }

                    record.size += size;
                    record.objectCount++;
                }
            }
            return results;
            return histogram;
        }
    }

    // //////////////////////////////////////////////////////////////
    // calculate garbage cleanup
    // //////////////////////////////////////////////////////////////

        protected HashMap<Integer, Record> compute()
        final HashMap<Integer, CleanupResult> results;
        final List<ClassImpl> classes2remove;
        public CleanupWrapper(final HashMap<Integer, CleanupResult> results, final List<ClassImpl> classes2remove)
        {
            if ((end - start) < BATCH_SIZE)
                return directCompute();

            // fork to left/right half, then merge
            int middle = (start + end) / 2;
            GarbageHistogramTask left = new GarbageHistogramTask(idx, reachable, start, middle);
            GarbageHistogramTask right = new GarbageHistogramTask(idx, reachable, middle, end);
            left.fork();
            HashMap<Integer, Record> rightMap = right.compute();
            HashMap<Integer, Record> leftMap = left.join();

            return mergeMap(rightMap, leftMap);
        }
    }

        protected HashMap<Integer, Record> mergeMap(HashMap<Integer, Record> leftMap, HashMap<Integer, Record> rightMap)
        int count = 0;
        long size = 0;
        final ClassImpl clazz;
        public CleanupResult(ClassImpl clazz)
        {
            HashMap<Integer, Record> biggerMap;
            HashMap<Integer, Record> smallerMap;

            if (rightMap.size() > leftMap.size())
            {
                biggerMap = rightMap;
                smallerMap = leftMap;
            }
            else
            {
                biggerMap = leftMap;
                smallerMap = rightMap;
            }

            // merge; minimise put() calls
            for (Record record : smallerMap.values())
            {
                int clazzId = record.clazz.getObjectId();
                Record existing = biggerMap.get(clazzId);
                if (existing == null)
                {
                    biggerMap.put(clazzId, record);
                }
                else
                {
                    existing.objectCount += record.objectCount;
                    existing.size += record.size;
                    existing.classesToRemove.addAll(record.classesToRemove);
                }
            }

            return biggerMap;
        }
    }

    private static void createHistogramOfUnreachableObjects(final PreliminaryIndexImpl idx, Map<Integer, Record> histogram)
    {
        /*
         * The parser might have already discarded some objects, so merge the
         * histograms.
         */
        Serializable parserDeadObjects = idx.getSnapshotInfo().getProperty(UnreachableObjectsHistogram.class.getName());

        HashMap<Long, UnreachableObjectsHistogram.Record> parserRecords = new HashMap<Long, UnreachableObjectsHistogram.Record>();
        if (parserDeadObjects instanceof UnreachableObjectsHistogram)
        {
            UnreachableObjectsHistogram parserDeadObjectHistogram = (UnreachableObjectsHistogram) parserDeadObjects;
            for (UnreachableObjectsHistogram.Record r : parserDeadObjectHistogram.getRecords())
            {
                parserRecords.put(r.getClassAddress(), r);
            }
        }
        List<UnreachableObjectsHistogram.Record> records = new ArrayList<UnreachableObjectsHistogram.Record>();
        for (Record r : histogram.values())
        {
            UnreachableObjectsHistogram.Record r2 = parserRecords.get(r.clazz.getObjectAddress());
            int existingCount = 0;
            long existingSize = 0L;
            if (r2 != null && r.clazz.getName().equals(r2.getClassName()))
            {
                existingCount = r2.getObjectCount();
                existingSize = r2.getShallowHeapSize();
                parserRecords.remove(r.clazz.getObjectAddress());
                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);
                    }
                }
            }
            records.add(new UnreachableObjectsHistogram.Record(r.clazz.getName(), r.clazz.getObjectAddress(),
                            r.objectCount + existingCount, r.size + existingSize));
        }
        records.addAll(parserRecords.values());

        UnreachableObjectsHistogram deadObjectHistogram = new UnreachableObjectsHistogram(records);
        idx.getSnapshotInfo().setProperty(UnreachableObjectsHistogram.class.getName(), deadObjectHistogram);
    }

    // //////////////////////////////////////////////////////////////

Return to bug 570670

Lines 20-30 import java.util.HashMap; Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/internal/GarbageCleaner.java (-203 / +138 lines)
20	import java.util.Iterator;	20	import java.util.Iterator;
21	import java.util.List;	21	import java.util.List;
22	import java.util.Map;	22	import java.util.Map;
23	import java.util.concurrent.Callable;	23	import java.util.concurrent.ForkJoinPool;
24	import java.util.concurrent.ExecutionException;
25	import java.util.concurrent.ExecutorService;
26	import java.util.concurrent.Executors;
27	import java.util.concurrent.Future;	24	import java.util.concurrent.Future;
		25	import java.util.concurrent.RecursiveTask;
		26	import java.util.stream.IntStream;
28		27
29	import org.eclipse.mat.collect.ArrayInt;	28	import org.eclipse.mat.collect.ArrayInt;
30	import org.eclipse.mat.collect.BitField;	29	import org.eclipse.mat.collect.BitField;
Lines 53-66 import org.eclipse.mat.util.SilentProgressListener; Link Here
53		52
54	/* package */class GarbageCleaner	53	/* package */class GarbageCleaner
55	{	54	{
56
57	private final static int PARALLEL_CHUNK_SIZE = 1610241024;
58	public static int[] clean(final PreliminaryIndexImpl idx, final SnapshotImplBuilder builder,	55	public static int[] clean(final PreliminaryIndexImpl idx, final SnapshotImplBuilder builder,
59	Map<String, String> arguments, IProgressListener listener)	56	Map<String, String> arguments, IProgressListener listener)
60	throws IOException, InterruptedException, ExecutionException	57	throws IOException, InterruptedException
61	{	58	{
62	IndexManager idxManager = new IndexManager();	59	IndexManager idxManager = new IndexManager();
63	ExecutorService es = Executors.newWorkStealingPool();
64		60
65	try	61	try
66	{	62	{
Lines 123-128 import org.eclipse.mat.util.SilentProgressListener; Link Here
123	// check if unreachable objects exist, then either mark as GC root	119	// check if unreachable objects exist, then either mark as GC root
124	// unreachable (keep objects) or store a histogram of unreachable	120	// unreachable (keep objects) or store a histogram of unreachable
125	// objects	121	// objects
		122	Map<Integer, Record> garbageHistogram = new GarbageHistogramTask(idx, reachable).invoke();
		123
126	if (newNoOfObjects < oldNoOfObjects)	124	if (newNoOfObjects < oldNoOfObjects)
127	{	125	{
128	Object un = idx.getSnapshotInfo().getProperty("keep_unreachable_objects"); //$NON-NLS-1$	126	Object un = idx.getSnapshotInfo().getProperty("keep_unreachable_objects"); //$NON-NLS-1$
Lines 131-140 import org.eclipse.mat.util.SilentProgressListener; Link Here
131	int newRoot;	129	int newRoot;
132	newRoot = (Integer)un;	130	newRoot = (Integer)un;
133	newNoOfObjects = markUnreachableAsGCRoots(idx, reachable, newNoOfObjects, newRoot, listener);	131	newNoOfObjects = markUnreachableAsGCRoots(idx, reachable, newNoOfObjects, newRoot, listener);
		132	// if we changed the class set, we need to re-calculate the histogram
		133	garbageHistogram = new GarbageHistogramTask(idx, reachable).invoke();
134	}	134	}
135	if (newNoOfObjects < oldNoOfObjects)	135	if (newNoOfObjects < oldNoOfObjects)
136	{	136	{
137	createHistogramOfUnreachableObjects(es, idx, reachable);	137	createHistogramOfUnreachableObjects(idx, garbageHistogram);
138	}	138	}
139	}	139	}
140		140
Lines 147-156 import org.eclipse.mat.util.SilentProgressListener; Link Here
147	final int[] map = new int[oldNoOfObjects];	147	final int[] map = new int[oldNoOfObjects];
148	final long[] id2a = new long[newNoOfObjects];	148	final long[] id2a = new long[newNoOfObjects];
149		149
150	List<ClassImpl> classes2remove = new ArrayList<ClassImpl>();
151
152	final IOne2SizeIndex preA2size = idx.array2size;
153	long memFree = 0;
154	for (int ii = 0, jj = 0; ii < oldNoOfObjects; ii++)	150	for (int ii = 0, jj = 0; ii < oldNoOfObjects; ii++)
155	{	151	{
156	if (reachable[ii])	152	if (reachable[ii])
Lines 164-197 import org.eclipse.mat.util.SilentProgressListener; Link Here
164	}	160	}
165	}	161	}
166		162
167	ArrayList<Callable<CleanupWrapper>> tasks = new ArrayList<Callable<CleanupWrapper>>();	163	garbageHistogram.values().parallelStream().forEach(gcRecord -> {
		164	long instsize = gcRecord.size / gcRecord.objectCount;
		165	long leftover = gcRecord.size % gcRecord.objectCount;
168		166
169	for(int i = 0; i < oldNoOfObjects; i += PARALLEL_CHUNK_SIZE) {	167	// the first record will have the "remainder" also added in
170	final int start = i;	168	gcRecord.clazz.removeInstance(instsize + leftover);
171	final int length = Math.min(PARALLEL_CHUNK_SIZE, reachable.length - start);
172	tasks.add(new CalculateGarbageCleanupForClass(idx, reachable, start, length));
173	}
174
175	List<Future<CleanupWrapper>> wrappers = null;
176	wrappers = es.invokeAll(tasks);
177		169
178	for(Future<CleanupWrapper> wrapper : wrappers) {	170	// start at i=1; as we have already completed one
179	for(CleanupResult cr : wrapper.get().results.values()) {	171	for (int i = 1; i < gcRecord.objectCount; i++)
180	long totalmem = cr.size;
181	for (int i = cr.count; i > 0; --i)
182	{
183	// Remove one by one as removeInstanceBulk is not yet API
184	long instsize = totalmem / i;
185	totalmem -= instsize;
186	cr.clazz.removeInstance(instsize);
187	}
188	memFree += cr.size;
189	}
190	for(ClassImpl c : wrapper.get().classes2remove)
191	{	172	{
192	classes2remove.add(c);	173	gcRecord.clazz.removeInstance(instsize);
193	}	174	}
194	}	175	});
		176
		177	long memFree = garbageHistogram.values().parallelStream().mapToLong(gcr -> gcr.size).sum();
195		178
196	if (newNoOfObjects < oldNoOfObjects)	179	if (newNoOfObjects < oldNoOfObjects)
197	{	180	{
Lines 200-216 import org.eclipse.mat.util.SilentProgressListener; Link Here
200	- newNoOfObjects, memFree), null);	183	- newNoOfObjects, memFree), null);
201	}	184	}
202		185
203	es.shutdown();
204
205	// classes cannot be removed right away	186	// classes cannot be removed right away
206	// as they are needed to remove instances of this class	187	// as they are needed to remove instances of this class
207	for (ClassImpl c : classes2remove)	188	for (Record gcRecord : garbageHistogram.values())
208	{	189	{
209	classesById.remove(c.getObjectId());	190	for (ClassImpl c : gcRecord.classesToRemove)
		191	{
		192	classesById.remove(c.getObjectId());
210		193
211	ClassImpl superclass = classesById.get(c.getSuperClassId());	194	ClassImpl superclass = classesById.get(c.getSuperClassId());
212	if (superclass != null)	195	if (superclass != null)
213	superclass.removeSubClass(c);	196	superclass.removeSubClass(c);
		197	}
214	}	198	}
215		199
216	reachable = null; // early gc...	200	reachable = null; // early gc...
Lines 293-298 import org.eclipse.mat.util.SilentProgressListener; Link Here
293	// array size	277	// array size
294	// //////////////////////////////////////////////////////////////	278	// //////////////////////////////////////////////////////////////
295		279
		280	final IOne2SizeIndex preA2size = idx.array2size;
		281
296	indexFile = Index.A2SIZE.getFile(idx.snapshotInfo.getPrefix());	282	indexFile = Index.A2SIZE.getFile(idx.snapshotInfo.getPrefix());
297	listener.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, new Object[] { indexFile	283	listener.subTask(MessageUtil.format(Messages.GarbageCleaner_Writing, new Object[] { indexFile
298	.getAbsolutePath() }));	284	.getAbsolutePath() }));
Lines 322-328 import org.eclipse.mat.util.SilentProgressListener; Link Here
322	}	308	}
323	});	309	});
324		310
325	idxManager.setReader(Index.A2SIZE, new SizeIndexReader(newIdx));	311	idxManager.setReader(Index.A2SIZE, new SizeIndexReader(newIdx));
326		312
327	preA2size.close();	313	preA2size.close();
328	preA2size.delete();	314	preA2size.delete();
Lines 517-522 import org.eclipse.mat.util.SilentProgressListener; Link Here
517	ClassImpl clazz;	503	ClassImpl clazz;
518	int objectCount;	504	int objectCount;
519	long size;	505	long size;
		506	List<ClassImpl> classesToRemove = new ArrayList<>();
520		507
521	public Record(ClassImpl clazz)	508	public Record(ClassImpl clazz)
522	{	509	{
Lines 524-738 import org.eclipse.mat.util.SilentProgressListener; Link Here
524	}	511	}
525	}	512	}
526		513
527	private static void createHistogramOfUnreachableObjects(final ExecutorService es,	514	public static class GarbageHistogramTask extends RecursiveTask<HashMap<Integer, Record>>
528	final PreliminaryIndexImpl idx, final boolean[] reachable)
529	throws InterruptedException, ExecutionException
530	{	515	{
531	ArrayList<Callable<HashMap<Integer, Record>>> tasks = new ArrayList<Callable<HashMap<Integer, Record>>>();	516	final int BATCH_SIZE = 1_000_000;
532
533	for(int i = 0; i < reachable.length; i += PARALLEL_CHUNK_SIZE) {
534	final int start = i;
535	final int length = Math.min(PARALLEL_CHUNK_SIZE, reachable.length - start);
536	tasks.add(new CreateHistogramOfUnreachableObjectsChunk(idx, reachable, start, length));
537	}
538
539	List<Future<HashMap<Integer, Record>>> results = null;
540	results = es.invokeAll(tasks);
541
542	final HashMap<Integer, Record> histogram = new HashMap<Integer, Record>(reachable.length);
543
544	for(Future<HashMap<Integer, Record>> subhistogram : results) {
545	histogram.putAll(subhistogram.get());
546	}
547
548	/*
549	* The parser might have already discarded some objects, so merge the histograms.
550	*/
551	Serializable parserDeadObjects = idx.getSnapshotInfo().getProperty(UnreachableObjectsHistogram.class.getName());
552	HashMap<Long, UnreachableObjectsHistogram.Record>parserRecords = new HashMap<Long, UnreachableObjectsHistogram.Record>();
553	if (parserDeadObjects instanceof UnreachableObjectsHistogram)
554	{
555	UnreachableObjectsHistogram parserDeadObjectHistogram = (UnreachableObjectsHistogram)parserDeadObjects;
556	for (UnreachableObjectsHistogram.Record r : parserDeadObjectHistogram.getRecords())
557	{
558	parserRecords.put(r.getClassAddress(), r);
559	}
560	}
561	List<UnreachableObjectsHistogram.Record> records = new ArrayList<UnreachableObjectsHistogram.Record>();
562	for(Record r : histogram.values()) {
563	UnreachableObjectsHistogram.Record r2 = parserRecords.get(r.clazz.getObjectAddress());
564	int existingCount = 0;
565	long existingSize = 0L;
566	if (r2 != null && r.clazz.getName().equals(r2.getClassName()))
567	{
568	existingCount = r2.getObjectCount();
569	existingSize = r2.getShallowHeapSize();
570	parserRecords.remove(r.clazz.getObjectAddress());
571	}
572	records.add(new UnreachableObjectsHistogram.Record(
573	r.clazz.getName(),
574	r.clazz.getObjectAddress(),
575	r.objectCount + existingCount,
576	r.size + existingSize));
577	}
578	records.addAll(parserRecords.values());
579		517
580	UnreachableObjectsHistogram deadObjectHistogram = new UnreachableObjectsHistogram(records);
581	idx.getSnapshotInfo().setProperty(UnreachableObjectsHistogram.class.getName(), deadObjectHistogram);
582	}
583
584
585	private static class CreateHistogramOfUnreachableObjectsChunk implements Callable<HashMap<Integer, Record>>
586	{
587	final PreliminaryIndexImpl idx;	518	final PreliminaryIndexImpl idx;
588	final boolean[] reachable;	519	final boolean[] reachable;
589	final int start;	520	final int start;
590	final int length;	521	final int end;
591		522
592	public CreateHistogramOfUnreachableObjectsChunk(PreliminaryIndexImpl idx,	523	GarbageHistogramTask(final PreliminaryIndexImpl idx, final boolean[] reachable)
593	boolean[] reachable, int start, int length)	524	{
		525	this(idx, reachable, 0, reachable.length);
		526	}
		527
		528	GarbageHistogramTask(final PreliminaryIndexImpl idx, final boolean[] reachable, final int start, final int end)
594	{	529	{
595	this.idx = idx;	530	this.idx = idx;
596	this.reachable = reachable;	531	this.reachable = reachable;
597	this.start = start;	532	this.start = start;
598	this.length = length;	533	this.end = end;
599	}	534	}
600		535
601	public HashMap<Integer, Record> call() {	536	protected HashMap<Integer, Record> directCompute()
602	IOne2SizeIndex array2size = idx.array2size;	537	{
603		538	HashMap<Integer, Record> results = new HashMap<Integer, Record>(end - start);
604	HashMap<Integer, Record> histogram = new HashMap<Integer, Record>(length);	539	for (int ii = start; ii < end; ii++)
605
606	for (int ii = start; ii < (start + length); ii++)
607	{	540	{
608	if (!reachable[ii])	541	if (!reachable[ii])
609	{	542	{
610	final int classId = idx.object2classId.get(ii);	543	final int objectNo = ii;
611	Record r = histogram.get(classId);	544	int classId = idx.object2classId.get(objectNo);
612	if (r == null)	545	Record record = results.get(classId);
		546	if (record == null)
613	{	547	{
614	r = new Record(idx.classesById.get(classId));	548	record = new Record(idx.classesById.get(classId));
615	histogram.put(classId, r);	549	results.put(classId, record);
616	}	550	}
617		551
618	long s = array2size.getSize(ii);	552	long size = 0;
619	if (s > 0)	553	if (record.clazz.isArrayType())
620	{	554	{
621	// Already got the size	555	size = idx.array2size.getSize(objectNo);
622	}	556	}
623	else if (IClass.JAVA_LANG_CLASS.equals(r.clazz.getName()))	557	else if (IClass.JAVA_LANG_CLASS.equals(record.clazz.getName()))
624	{	558	{
625	ClassImpl classImpl = idx.classesById.get(ii);	559	ClassImpl classImpl = idx.classesById.get(objectNo);
626	if (classImpl == null)	560	if (classImpl == null)
627	{	561	{
628	s = r.clazz.getHeapSizePerInstance();	562	size = record.clazz.getHeapSizePerInstance();
629	}	563	}
630	else	564	else
631	{	565	{
632	s = classImpl.getUsedHeapSize();	566	size = classImpl.getUsedHeapSize();
		567	record.classesToRemove.add(classImpl);
633	}	568	}
634	}	569	}
635	else	570	else
636	{	571	{
637	s = r.clazz.getHeapSizePerInstance();	572	size = record.clazz.getHeapSizePerInstance();
638	}	573	}
639		574
640	r.size += s;	575	record.size += size;
641	r.objectCount += 1;	576	record.objectCount++;
642	}	577	}
643	}	578	}
644		579	return results;
645	return histogram;
646	}	580	}
647	}
648
649	// //////////////////////////////////////////////////////////////
650	// calculate garbage cleanup
651	// //////////////////////////////////////////////////////////////
652		581
653	private static class CleanupWrapper {	582	protected HashMap<Integer, Record> compute()
654	final HashMap<Integer, CleanupResult> results;
655	final List<ClassImpl> classes2remove;
656	public CleanupWrapper(final HashMap<Integer, CleanupResult> results, final List<ClassImpl> classes2remove)
657	{	583	{
658	this.results = results;	584	if ((end - start) < BATCH_SIZE)
659	this.classes2remove = classes2remove;	585	return directCompute();
		586
		587	// fork to left/right half, then merge
		588	int middle = (start + end) / 2;
		589	GarbageHistogramTask left = new GarbageHistogramTask(idx, reachable, start, middle);
		590	GarbageHistogramTask right = new GarbageHistogramTask(idx, reachable, middle, end);
		591	left.fork();
		592	HashMap<Integer, Record> rightMap = right.compute();
		593	HashMap<Integer, Record> leftMap = left.join();
		594
		595	return mergeMap(rightMap, leftMap);
660	}	596	}
661	}
662		597
663	private static class CleanupResult {	598	protected HashMap<Integer, Record> mergeMap(HashMap<Integer, Record> leftMap, HashMap<Integer, Record> rightMap)
664	int count = 0;
665	long size = 0;
666	final ClassImpl clazz;
667	public CleanupResult(ClassImpl clazz)
668	{	599	{
669	this.clazz = clazz;	600	HashMap<Integer, Record> biggerMap;
		601	HashMap<Integer, Record> smallerMap;
		602
		603	if (rightMap.size() > leftMap.size())
		604	{
		605	biggerMap = rightMap;
		606	smallerMap = leftMap;
		607	}
		608	else
		609	{
		610	biggerMap = leftMap;
		611	smallerMap = rightMap;
		612	}
		613
		614	// merge; minimise put() calls
		615	for (Record record : smallerMap.values())
		616	{
		617	int clazzId = record.clazz.getObjectId();
		618	Record existing = biggerMap.get(clazzId);
		619	if (existing == null)
		620	{
		621	biggerMap.put(clazzId, record);
		622	}
		623	else
		624	{
		625	existing.objectCount += record.objectCount;
		626	existing.size += record.size;
		627	existing.classesToRemove.addAll(record.classesToRemove);
		628	}
		629	}
		630
		631	return biggerMap;
670	}	632	}
671	}	633	}
672		634
673	private static class CalculateGarbageCleanupForClass implements Callable<CleanupWrapper>	635	private static void createHistogramOfUnreachableObjects(final PreliminaryIndexImpl idx, Map<Integer, Record> histogram)
674	{	636	{
675	final PreliminaryIndexImpl idx;	637	/*
676	final boolean[] reachable;	638	* The parser might have already discarded some objects, so merge the
677	final int start;	639	* histograms.
678	final int length;	640	*/
		641	Serializable parserDeadObjects = idx.getSnapshotInfo().getProperty(UnreachableObjectsHistogram.class.getName());
679		642
680	public CalculateGarbageCleanupForClass(PreliminaryIndexImpl idx,	643	HashMap<Long, UnreachableObjectsHistogram.Record> parserRecords = new HashMap<Long, UnreachableObjectsHistogram.Record>();
681	boolean[] reachable, int start, int length)	644	if (parserDeadObjects instanceof UnreachableObjectsHistogram)
682	{	645	{
683	this.idx = idx;	646	UnreachableObjectsHistogram parserDeadObjectHistogram = (UnreachableObjectsHistogram) parserDeadObjects;
684	this.reachable = reachable;	647	for (UnreachableObjectsHistogram.Record r : parserDeadObjectHistogram.getRecords())
685	this.start = start;	648	{
686	this.length = length;	649	parserRecords.put(r.getClassAddress(), r);
		650	}
687	}	651	}
688		652	List<UnreachableObjectsHistogram.Record> records = new ArrayList<UnreachableObjectsHistogram.Record>();
689	public CleanupWrapper call() throws Exception	653	for (Record r : histogram.values())
690	{	654	{
691	HashMap<Integer, CleanupResult> results = new HashMap<Integer, CleanupResult>();	655	UnreachableObjectsHistogram.Record r2 = parserRecords.get(r.clazz.getObjectAddress());
692	List<ClassImpl> classes2remove = new ArrayList<ClassImpl>();	656	int existingCount = 0;
693	for (int ii = start; ii < (start + length); ii++)	657	long existingSize = 0L;
		658	if (r2 != null && r.clazz.getName().equals(r2.getClassName()))
694	{	659	{
695	if (reachable[ii])	660	existingCount = r2.getObjectCount();
696	continue;	661	existingSize = r2.getShallowHeapSize();
697		662	parserRecords.remove(r.clazz.getObjectAddress());
698	int classId = idx.object2classId.get(ii);
699	ClassImpl clazz = idx.classesById.get(classId);
700
701	CleanupResult cr = results.get(classId);
702	if (cr == null)
703	{
704	cr = new CleanupResult(clazz);
705	results.put(classId, cr);
706	}
707
708	long arraySize = idx.array2size.getSize(ii);
709	if (arraySize > 0)
710	{
711	cr.count += 1;
712	cr.size += arraySize;
713	}
714	else
715	{
716	// [INFO] some instances of java.lang.Class are not
717	// reported as HPROF_GC_CLASS_DUMP but as
718	// HPROF_GC_INSTANCE_DUMP
719	ClassImpl c = idx.classesById.get(ii);
720
721	if (c == null)
722	{
723	cr.count += 1;
724	cr.size += clazz.getHeapSizePerInstance();
725	}
726	else
727	{
728	cr.count += 1;
729	cr.size += c.getUsedHeapSize();
730	classes2remove.add(c);
731	}
732	}
733	}	663	}
734	return new CleanupWrapper(results, classes2remove);	664	records.add(new UnreachableObjectsHistogram.Record(r.clazz.getName(), r.clazz.getObjectAddress(),
		665	r.objectCount + existingCount, r.size + existingSize));
735	}	666	}
		667	records.addAll(parserRecords.values());
		668
		669	UnreachableObjectsHistogram deadObjectHistogram = new UnreachableObjectsHistogram(records);
		670	idx.getSnapshotInfo().setProperty(UnreachableObjectsHistogram.class.getName(), deadObjectHistogram);
736	}	671	}
737		672
738	// //////////////////////////////////////////////////////////////	673	// //////////////////////////////////////////////////////////////