/* * Copyright (C) 2016 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.android.ahat.heapdump; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.Deque; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; public class Diff { /** * Perform a diff between two heap lists. * * Heaps are diffed based on heap name. PlaceHolder heaps will be added to * the given lists as necessary so that every heap in A has a corresponding * heap in B and vice-versa. */ private static void heaps(List<AhatHeap> a, List<AhatHeap> b) { int asize = a.size(); int bsize = b.size(); for (int i = 0; i < bsize; i++) { // Set the B heap's baseline as null to mark that we have not yet // matched it with an A heap. b.get(i).setBaseline(null); } for (int i = 0; i < asize; i++) { AhatHeap aheap = a.get(i); aheap.setBaseline(null); for (int j = 0; j < bsize; j++) { AhatHeap bheap = b.get(j); if (bheap.getBaseline() == null && aheap.getName().equals(bheap.getName())) { // We found a match between aheap and bheap. aheap.setBaseline(bheap); bheap.setBaseline(aheap); break; } } if (aheap.getBaseline() == null) { // We did not find any match for aheap in snapshot B. // Create a placeholder heap in snapshot B to use as the baseline. b.add(AhatHeap.newPlaceHolderHeap(aheap.getName(), aheap)); } } // Make placeholder heaps in snapshot A for any unmatched heaps in // snapshot B. for (int i = 0; i < bsize; i++) { AhatHeap bheap = b.get(i); if (bheap.getBaseline() == null) { a.add(AhatHeap.newPlaceHolderHeap(bheap.getName(), bheap)); } } } /** * Key represents an equivalence class of AhatInstances that are allowed to * be considered for correspondence between two different snapshots. */ private static class Key { // Corresponding objects must belong to classes of the same name. private final String mClass; // Corresponding objects must belong to heaps of the same name. private final String mHeapName; // Corresponding string objects must have the same value. // mStringValue is set to the empty string for non-string objects. private final String mStringValue; // Corresponding class objects must have the same class name. // mClassName is set to the empty string for non-class objects. private final String mClassName; // Corresponding array objects must have the same length. // mArrayLength is set to 0 for non-array objects. private final int mArrayLength; private Key(AhatInstance inst) { mClass = inst.getClassName(); mHeapName = inst.getHeap().getName(); mClassName = inst.isClassObj() ? inst.asClassObj().getName() : ""; String string = inst.asString(); mStringValue = string == null ? "" : string; AhatArrayInstance array = inst.asArrayInstance(); mArrayLength = array == null ? 0 : array.getLength(); } /** * Return the key for the given instance. */ public static Key keyFor(AhatInstance inst) { return new Key(inst); } @Override public boolean equals(Object other) { if (!(other instanceof Key)) { return false; } Key o = (Key)other; return mClass.equals(o.mClass) && mHeapName.equals(o.mHeapName) && mStringValue.equals(o.mStringValue) && mClassName.equals(o.mClassName) && mArrayLength == o.mArrayLength; } @Override public int hashCode() { return Objects.hash(mClass, mHeapName, mStringValue, mClassName, mArrayLength); } } private static class InstanceListPair { public final List<AhatInstance> a; public final List<AhatInstance> b; public InstanceListPair() { this.a = new ArrayList<AhatInstance>(); this.b = new ArrayList<AhatInstance>(); } public InstanceListPair(List<AhatInstance> a, List<AhatInstance> b) { this.a = a; this.b = b; } } /** * Recursively create place holder instances for the given instance and * every instance dominated by that instance. * Returns the place holder instance created for the given instance. * Adds all allocated placeholders to the given placeholders list. */ private static AhatInstance createPlaceHolders(AhatInstance inst, List<AhatInstance> placeholders) { // Don't actually use recursion, because we could easily smash the stack. // Instead we iterate. AhatInstance result = inst.newPlaceHolderInstance(); placeholders.add(result); Deque<AhatInstance> deque = new ArrayDeque<AhatInstance>(); deque.push(inst); while (!deque.isEmpty()) { inst = deque.pop(); for (AhatInstance child : inst.getDominated()) { placeholders.add(child.newPlaceHolderInstance()); deque.push(child); } } return result; } /** * Recursively diff two dominator trees of instances. * PlaceHolder objects are appended to the lists as needed to ensure every * object has a corresponding baseline in the other list. All PlaceHolder * objects are also appended to the given placeholders list, so their Site * info can be updated later on. */ private static void instances(List<AhatInstance> a, List<AhatInstance> b, List<AhatInstance> placeholders) { // Don't actually use recursion, because we could easily smash the stack. // Instead we iterate. Deque<InstanceListPair> deque = new ArrayDeque<InstanceListPair>(); deque.push(new InstanceListPair(a, b)); while (!deque.isEmpty()) { InstanceListPair p = deque.pop(); // Group instances of the same equivalence class together. Map<Key, InstanceListPair> byKey = new HashMap<Key, InstanceListPair>(); for (AhatInstance inst : p.a) { Key key = Key.keyFor(inst); InstanceListPair pair = byKey.get(key); if (pair == null) { pair = new InstanceListPair(); byKey.put(key, pair); } pair.a.add(inst); } for (AhatInstance inst : p.b) { Key key = Key.keyFor(inst); InstanceListPair pair = byKey.get(key); if (pair == null) { pair = new InstanceListPair(); byKey.put(key, pair); } pair.b.add(inst); } // diff objects from the same key class. for (InstanceListPair pair : byKey.values()) { // Sort by retained size and assume the elements at the top of the lists // correspond to each other in that order. This could probably be // improved if desired, but it gives good enough results for now. Collections.sort(pair.a, Sort.INSTANCE_BY_TOTAL_RETAINED_SIZE); Collections.sort(pair.b, Sort.INSTANCE_BY_TOTAL_RETAINED_SIZE); int common = Math.min(pair.a.size(), pair.b.size()); for (int i = 0; i < common; i++) { AhatInstance ainst = pair.a.get(i); AhatInstance binst = pair.b.get(i); ainst.setBaseline(binst); binst.setBaseline(ainst); deque.push(new InstanceListPair(ainst.getDominated(), binst.getDominated())); } // Add placeholder objects for anything leftover. for (int i = common; i < pair.a.size(); i++) { p.b.add(createPlaceHolders(pair.a.get(i), placeholders)); } for (int i = common; i < pair.b.size(); i++) { p.a.add(createPlaceHolders(pair.b.get(i), placeholders)); } } } } /** * Sets the baseline for root and all its descendants to baseline. */ private static void setSitesBaseline(Site root, Site baseline) { root.setBaseline(baseline); for (Site child : root.getChildren()) { setSitesBaseline(child, baseline); } } /** * Recursively diff the two sites, setting them and their descendants as * baselines for each other as appropriate. * * This requires that instances have already been diffed. In particular, we * require all AhatClassObjs in one snapshot have corresponding (possibly * place-holder) AhatClassObjs in the other snapshot. */ private static void sites(Site a, Site b) { // Set the sites as baselines of each other. a.setBaseline(b); b.setBaseline(a); // Set the site's ObjectsInfos as baselines of each other. This implicitly // adds new empty ObjectsInfo as needed. for (Site.ObjectsInfo ainfo : a.getObjectsInfos()) { AhatClassObj baseClassObj = null; if (ainfo.classObj != null) { baseClassObj = (AhatClassObj) ainfo.classObj.getBaseline(); } ainfo.setBaseline(b.getObjectsInfo(ainfo.heap.getBaseline(), baseClassObj)); } for (Site.ObjectsInfo binfo : b.getObjectsInfos()) { AhatClassObj baseClassObj = null; if (binfo.classObj != null) { baseClassObj = (AhatClassObj) binfo.classObj.getBaseline(); } binfo.setBaseline(a.getObjectsInfo(binfo.heap.getBaseline(), baseClassObj)); } // Set B children's baselines as null to mark that we have not yet matched // them with A children. for (Site bchild : b.getChildren()) { bchild.setBaseline(null); } for (Site achild : a.getChildren()) { achild.setBaseline(null); for (Site bchild : b.getChildren()) { if (achild.getLineNumber() == bchild.getLineNumber() && achild.getMethodName().equals(bchild.getMethodName()) && achild.getSignature().equals(bchild.getSignature()) && achild.getFilename().equals(bchild.getFilename())) { // We found a match between achild and bchild. sites(achild, bchild); break; } } if (achild.getBaseline() == null) { // We did not find any match for achild in site B. // Use B for the baseline of achild and its descendants. setSitesBaseline(achild, b); } } for (Site bchild : b.getChildren()) { if (bchild.getBaseline() == null) { setSitesBaseline(bchild, a); } } } /** * Perform a diff of the two snapshots, setting each as the baseline for the * other. */ public static void snapshots(AhatSnapshot a, AhatSnapshot b) { a.setBaseline(b); b.setBaseline(a); // Diff the heaps of each snapshot. heaps(a.getHeaps(), b.getHeaps()); // Diff the instances of each snapshot. List<AhatInstance> placeholders = new ArrayList<AhatInstance>(); instances(a.getRooted(), b.getRooted(), placeholders); // Diff the sites of each snapshot. // This requires the instances have already been diffed. sites(a.getRootSite(), b.getRootSite()); // Add placeholders to their corresponding sites. // This requires the sites have already been diffed. for (AhatInstance placeholder : placeholders) { placeholder.getBaseline().getSite().getBaseline().addPlaceHolderInstance(placeholder); } } /** * Diff two lists of field values. * PlaceHolder objects are added to the given lists as needed to ensure * every FieldValue in A ends up with a corresponding FieldValue in B. */ public static void fields(List<FieldValue> a, List<FieldValue> b) { // Fields with the same name and type are considered matching fields. // For simplicity, we assume the matching fields are in the same order in // both A and B, though some fields may be added or removed in either // list. If our assumption is wrong, in the worst case the quality of the // field diff is poor. for (int i = 0; i < a.size(); i++) { FieldValue afield = a.get(i); afield.setBaseline(null); // Find the matching field in B, if any. for (int j = i; j < b.size(); j++) { FieldValue bfield = b.get(j); if (afield.getName().equals(bfield.getName()) && afield.getType().equals(bfield.getType())) { // We found the matching field in B. // Assume fields i, ..., j-1 in B have no match in A. for ( ; i < j; i++) { a.add(i, FieldValue.newPlaceHolderFieldValue(b.get(i))); } afield.setBaseline(bfield); bfield.setBaseline(afield); break; } } if (afield.getBaseline() == null) { b.add(i, FieldValue.newPlaceHolderFieldValue(afield)); } } // All remaining fields in B are unmatched by any in A. for (int i = a.size(); i < b.size(); i++) { a.add(i, FieldValue.newPlaceHolderFieldValue(b.get(i))); } } }