| // Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| package com.android.tools.r8.horizontalclassmerging.policies; |
| |
| import static com.android.tools.r8.graph.DexClassAndMethod.asProgramMethodOrNull; |
| import static com.android.tools.r8.ir.desugar.LambdaDescriptor.isLambdaMetafactoryMethod; |
| import static com.android.tools.r8.utils.MapUtils.ignoreKey; |
| |
| import com.android.tools.r8.code.CfOrDexInstruction; |
| import com.android.tools.r8.graph.AppView; |
| import com.android.tools.r8.graph.DexCallSite; |
| import com.android.tools.r8.graph.DexClassAndMethod; |
| import com.android.tools.r8.graph.DexField; |
| import com.android.tools.r8.graph.DexMethod; |
| import com.android.tools.r8.graph.DexProgramClass; |
| import com.android.tools.r8.graph.DexType; |
| import com.android.tools.r8.graph.MethodResolutionResult; |
| import com.android.tools.r8.graph.ProgramMethod; |
| import com.android.tools.r8.graph.UseRegistry; |
| import com.android.tools.r8.horizontalclassmerging.MergeGroup; |
| import com.android.tools.r8.horizontalclassmerging.MultiClassPolicyWithPreprocessing; |
| import com.android.tools.r8.horizontalclassmerging.policies.deadlock.SingleCallerInformation; |
| import com.android.tools.r8.shaking.AppInfoWithLiveness; |
| import com.android.tools.r8.utils.InternalOptions.HorizontalClassMergerOptions; |
| import com.android.tools.r8.utils.SetUtils; |
| import com.android.tools.r8.utils.TraversalContinuation; |
| import com.android.tools.r8.utils.collections.ProgramMethodSet; |
| import com.google.common.collect.ImmutableList; |
| import com.google.common.collect.Sets; |
| import java.util.ArrayDeque; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Deque; |
| import java.util.IdentityHashMap; |
| import java.util.LinkedHashMap; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.ListIterator; |
| import java.util.Map; |
| import java.util.Set; |
| import java.util.concurrent.ExecutionException; |
| import java.util.concurrent.ExecutorService; |
| |
| /** |
| * Disallows merging of classes when the merging could introduce class initialization deadlocks. |
| * |
| * <p>Example: In the below example, if thread t0 triggers the class initialization of A, and thread |
| * t1 triggers the class initialization of C, then the program will never deadlock. However, if |
| * classes B and C are merged, then the program may all of a sudden deadlock, since thread t0 may |
| * hold the lock for A and wait for BC's lock, meanwhile thread t1 holds the lock for BC while |
| * waiting for A's lock. |
| * |
| * <pre> |
| * class A { |
| * static { |
| * new B(); |
| * } |
| * } |
| * class B extends A {} |
| * class C extends A {} |
| * </pre> |
| * |
| * <p>To identify the above situation, we perform a tracing from {@code A.<clinit>} to check if |
| * there is an execution path that triggers the class initialization of B or C. In that case, the |
| * reached subclass is ineligible for class merging. |
| * |
| * <p>Example: In the below example, if thread t0 triggers the class initialization of A, and thread |
| * t1 triggers the class initialization of B, then the program will never deadlock. However, if |
| * classes B and C are merged, then the program may all of a sudden deadlock, since thread 0 may |
| * hold the lock for A and wait for BC's lock, meanwhile thread t1 holds the lock for BC while |
| * waiting for A's lock. |
| * |
| * <pre> |
| * class A { |
| * static { |
| * new C(); |
| * } |
| * } |
| * class B { |
| * static { |
| * new A(); |
| * } |
| * } |
| * class C {} |
| * </pre> |
| * |
| * <p>To identify the above situation, we perform a tracing for each {@code <clinit>} in the merge |
| * group. If we find an execution path from the class initializer of one class in the merge group to |
| * the class initializer of another class in the merge group, then after merging there is a cycle in |
| * the class initialization that could lead to a deadlock. |
| */ |
| public class NoClassInitializerCycles extends MultiClassPolicyWithPreprocessing<Void> { |
| |
| final AppView<AppInfoWithLiveness> appView; |
| |
| // Mapping from each merge candidate to its merge group. |
| final Map<DexProgramClass, MergeGroup> allGroups = new IdentityHashMap<>(); |
| |
| private SingleCallerInformation singleCallerInformation; |
| |
| public NoClassInitializerCycles(AppView<AppInfoWithLiveness> appView) { |
| this.appView = appView; |
| } |
| |
| @Override |
| public Collection<MergeGroup> apply(MergeGroup group, Void nothing) { |
| // Partition the merge group into smaller groups that may be merged. If the class initialization |
| // of a parent class may initialize a member of the merge group, then this member is not |
| // eligible for class merging, unless the only way to class initialize this member is from the |
| // class initialization of the parent class. In this case, the member may be merged with other |
| // group members that are also guaranteed to only be class initialized from the class |
| // initialization of the parent class. |
| List<MergeGroup> partitioning = partitionClassesWithPossibleClassInitializerDeadlock(group); |
| List<MergeGroup> newGroups = new LinkedList<>(); |
| |
| // Revisit each partition. If the class initialization of a group member may initialize another |
| // class (not necessarily a group member), and vice versa, then class initialization could |
| // deadlock if the group member is merged with another class that is initialized concurrently. |
| for (MergeGroup partition : partitioning) { |
| List<MergeGroup> newGroupsFromPartition = new LinkedList<>(); |
| Tracer tracer = new Tracer(partition); |
| for (DexProgramClass clazz : partition) { |
| MergeGroup newGroup = getOrCreateGroupFor(clazz, newGroupsFromPartition, tracer); |
| if (newGroup != null) { |
| newGroup.add(clazz); |
| } else { |
| // Ineligible for merging. |
| } |
| } |
| newGroups.addAll(newGroupsFromPartition); |
| } |
| removeTrivialGroups(newGroups); |
| commit(group, newGroups); |
| return newGroups; |
| } |
| |
| private void commit(MergeGroup oldGroup, List<MergeGroup> newGroups) { |
| for (MergeGroup newGroup : newGroups) { |
| for (DexProgramClass member : newGroup) { |
| allGroups.put(member, newGroup); |
| } |
| } |
| for (DexProgramClass member : oldGroup) { |
| MergeGroup newGroup = allGroups.get(member); |
| if (newGroup == oldGroup) { |
| allGroups.remove(member); |
| } |
| } |
| } |
| |
| private MergeGroup getOrCreateGroupFor( |
| DexProgramClass clazz, List<MergeGroup> groups, Tracer tracer) { |
| assert !tracer.hasPossibleClassInitializerDeadlock(clazz); |
| |
| if (clazz.hasClassInitializer()) { |
| // Trace from the class initializer of this group member. If an execution path is found that |
| // leads back to the class initializer then this class may be involved in a deadlock, and we |
| // should not merge any other classes into it. |
| tracer.setTracingRoot(clazz); |
| tracer.enqueueTracingRoot(clazz.getProgramClassInitializer()); |
| tracer.trace(); |
| if (tracer.hasPossibleClassInitializerDeadlock(clazz)) { |
| // Ineligible for merging. |
| return null; |
| } |
| } |
| |
| for (MergeGroup group : groups) { |
| if (canMerge(clazz, group, tracer)) { |
| return group; |
| } |
| } |
| |
| MergeGroup newGroup = new MergeGroup(); |
| groups.add(newGroup); |
| return newGroup; |
| } |
| |
| private boolean canMerge(DexProgramClass clazz, MergeGroup group, Tracer tracer) { |
| for (DexProgramClass member : group) { |
| // Check that the class initialization of the given class cannot reach the class initializer |
| // of the current group member. |
| if (tracer.isClassInitializedByClassInitializationOf(member, clazz)) { |
| return false; |
| } |
| // Check that the class initialization of the current group member cannot reach the class |
| // initializer of the given class. |
| if (tracer.isClassInitializedByClassInitializationOf(clazz, member)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /** |
| * Runs the tracer from the parent class initializers, using the entire group as tracing context. |
| * If the class initializer of one of the classes in the merge group is reached, then that class |
| * is not eligible for merging. |
| */ |
| private List<MergeGroup> partitionClassesWithPossibleClassInitializerDeadlock(MergeGroup group) { |
| Set<DexProgramClass> superclasses = Sets.newIdentityHashSet(); |
| appView |
| .appInfo() |
| .traverseSuperClasses( |
| group.iterator().next(), |
| (supertype, superclass, immediateSubclass) -> { |
| if (superclass != null && superclass.isProgramClass()) { |
| superclasses.add(superclass.asProgramClass()); |
| return TraversalContinuation.CONTINUE; |
| } |
| return TraversalContinuation.BREAK; |
| }); |
| |
| // Run the tracer from the class initializers of the superclasses. |
| Tracer tracer = new Tracer(group); |
| tracer.setTracingRoots(group); |
| for (DexProgramClass superclass : superclasses) { |
| if (superclass.hasClassInitializer()) { |
| tracer.enqueueTracingRoot(superclass.getProgramClassInitializer()); |
| } |
| } |
| tracer.trace(); |
| |
| MergeGroup notInitializedByInitializationOfParent = new MergeGroup(); |
| Map<DexProgramClass, MergeGroup> partitioning = new LinkedHashMap<>(); |
| for (DexProgramClass member : group) { |
| if (tracer.hasPossibleClassInitializerDeadlock(member)) { |
| DexProgramClass nearestLock = getNearestLock(member, superclasses); |
| if (nearestLock != null) { |
| partitioning.computeIfAbsent(nearestLock, ignoreKey(MergeGroup::new)).add(member); |
| } else { |
| // Ineligible for merging. |
| } |
| } else { |
| notInitializedByInitializationOfParent.add(member); |
| } |
| } |
| |
| return ImmutableList.<MergeGroup>builder() |
| .add(notInitializedByInitializationOfParent) |
| .addAll(partitioning.values()) |
| .build(); |
| } |
| |
| private DexProgramClass getNearestLock( |
| DexProgramClass clazz, Set<DexProgramClass> candidateOwners) { |
| ProgramMethodSet seen = ProgramMethodSet.create(); |
| ProgramMethod singleCaller = singleCallerInformation.getSingleClassInitializerCaller(clazz); |
| while (singleCaller != null && seen.add(singleCaller)) { |
| if (singleCaller.getDefinition().isClassInitializer() |
| && candidateOwners.contains(singleCaller.getHolder())) { |
| return singleCaller.getHolder(); |
| } |
| singleCaller = singleCallerInformation.getSingleCaller(singleCaller); |
| } |
| return null; |
| } |
| |
| @Override |
| public void clear() { |
| allGroups.clear(); |
| } |
| |
| @Override |
| public String getName() { |
| return "NoClassInitializerCycles"; |
| } |
| |
| @Override |
| public Void preprocess(Collection<MergeGroup> groups, ExecutorService executorService) |
| throws ExecutionException { |
| for (MergeGroup group : groups) { |
| for (DexProgramClass clazz : group) { |
| allGroups.put(clazz, group); |
| } |
| } |
| singleCallerInformation = |
| SingleCallerInformation.builder(appView).analyze(executorService).build(); |
| return null; |
| } |
| |
| @Override |
| public boolean shouldSkipPolicy() { |
| HorizontalClassMergerOptions options = appView.options().horizontalClassMergerOptions(); |
| return !options.isClassInitializerDeadlockDetectionEnabled(); |
| } |
| |
| private class Tracer { |
| |
| final MergeGroup group; |
| |
| // The members of the existing merge group, for efficient membership querying. |
| final Set<DexProgramClass> groupMembers; |
| |
| private final Set<DexProgramClass> seenClassInitializers = Sets.newIdentityHashSet(); |
| private final ProgramMethodSet seenMethods = ProgramMethodSet.create(); |
| private final Deque<ProgramMethod> worklist = new ArrayDeque<>(); |
| |
| // Mapping from each merge grop member to the set of merge group members whose class |
| // initializers may trigger the class initialization of the group member. |
| private final Map<DexProgramClass, Set<DexProgramClass>> classInitializerReachableFromClasses = |
| new IdentityHashMap<>(); |
| |
| // The current tracing roots (either the entire merge group or one of the classes in the merge |
| // group). |
| private Collection<DexProgramClass> tracingRoots; |
| |
| Tracer(MergeGroup group) { |
| this.group = group; |
| this.groupMembers = SetUtils.newIdentityHashSet(group); |
| } |
| |
| void clearSeen() { |
| seenClassInitializers.clear(); |
| seenMethods.clear(); |
| } |
| |
| void clearWorklist() { |
| worklist.clear(); |
| } |
| |
| boolean markClassInitializerAsSeen(DexProgramClass clazz) { |
| return seenClassInitializers.add(clazz); |
| } |
| |
| boolean enqueueMethod(ProgramMethod method) { |
| if (seenMethods.add(method)) { |
| worklist.addLast(method); |
| return true; |
| } |
| return false; |
| } |
| |
| void enqueueTracingRoot(ProgramMethod tracingRoot) { |
| boolean added = seenMethods.add(tracingRoot); |
| assert added; |
| worklist.add(tracingRoot); |
| } |
| |
| void recordClassInitializerReachableFromTracingRoots(DexProgramClass clazz) { |
| assert groupMembers.contains(clazz); |
| classInitializerReachableFromClasses |
| .computeIfAbsent(clazz, ignoreKey(Sets::newIdentityHashSet)) |
| .addAll(tracingRoots); |
| } |
| |
| void recordTracingRootsIneligibleForClassMerging() { |
| for (DexProgramClass tracingRoot : tracingRoots) { |
| classInitializerReachableFromClasses |
| .computeIfAbsent(tracingRoot, ignoreKey(Sets::newIdentityHashSet)) |
| .add(tracingRoot); |
| } |
| } |
| |
| boolean hasSingleTracingRoot(DexProgramClass clazz) { |
| return tracingRoots.size() == 1 && tracingRoots.contains(clazz); |
| } |
| |
| boolean hasPossibleClassInitializerDeadlock(DexProgramClass clazz) { |
| return classInitializerReachableFromClasses |
| .getOrDefault(clazz, Collections.emptySet()) |
| .contains(clazz); |
| } |
| |
| boolean isClassInitializedByClassInitializationOf( |
| DexProgramClass classToBeInitialized, DexProgramClass classBeingInitialized) { |
| return classInitializerReachableFromClasses |
| .getOrDefault(classToBeInitialized, Collections.emptySet()) |
| .contains(classBeingInitialized); |
| } |
| |
| private void processWorklist() { |
| while (!worklist.isEmpty()) { |
| ProgramMethod method = worklist.removeLast(); |
| method.registerCodeReferences(new TracerUseRegistry(method)); |
| } |
| } |
| |
| void setTracingRoot(DexProgramClass tracingRoot) { |
| setTracingRoots(ImmutableList.of(tracingRoot)); |
| } |
| |
| void setTracingRoots(Collection<DexProgramClass> tracingRoots) { |
| assert verifySeenSetIsEmpty(); |
| assert verifyWorklistIsEmpty(); |
| this.tracingRoots = tracingRoots; |
| } |
| |
| void trace() { |
| processWorklist(); |
| clearSeen(); |
| } |
| |
| boolean verifySeenSetIsEmpty() { |
| assert seenClassInitializers.isEmpty(); |
| assert seenMethods.isEmpty(); |
| return true; |
| } |
| |
| boolean verifyWorklistIsEmpty() { |
| assert worklist.isEmpty(); |
| return true; |
| } |
| |
| class TracerUseRegistry extends UseRegistry { |
| |
| private final ProgramMethod context; |
| |
| TracerUseRegistry(ProgramMethod context) { |
| super(appView.dexItemFactory()); |
| this.context = context; |
| } |
| |
| private ProgramMethod getContext() { |
| return context; |
| } |
| |
| private void fail() { |
| // Ensures that hasPossibleClassInitializerDeadlock() returns true for each tracing root. |
| recordTracingRootsIneligibleForClassMerging(); |
| doBreak(); |
| clearWorklist(); |
| } |
| |
| private void triggerClassInitializerIfNotAlreadyTriggeredInContext(DexType type) { |
| DexProgramClass clazz = type.asProgramClass(appView); |
| if (clazz != null) { |
| triggerClassInitializerIfNotAlreadyTriggeredInContext(clazz); |
| } |
| } |
| |
| private void triggerClassInitializerIfNotAlreadyTriggeredInContext(DexProgramClass clazz) { |
| if (!isClassAlreadyInitializedInCurrentContext(clazz)) { |
| triggerClassInitializer(clazz); |
| } |
| } |
| |
| private boolean isClassAlreadyInitializedInCurrentContext(DexProgramClass clazz) { |
| return appView.appInfo().isSubtype(getContext().getHolder(), clazz); |
| } |
| |
| private void triggerClassInitializer(DexType type) { |
| DexProgramClass clazz = type.asProgramClass(appView); |
| if (clazz != null) { |
| triggerClassInitializer(clazz); |
| } |
| } |
| |
| private void triggerClassInitializer(DexProgramClass clazz) { |
| if (!markClassInitializerAsSeen(clazz)) { |
| return; |
| } |
| |
| if (groupMembers.contains(clazz)) { |
| if (hasSingleTracingRoot(clazz)) { |
| // We found an execution path from the class initializer of the given class back to its |
| // own class initializer. Therefore this class is not eligible for merging. |
| fail(); |
| } else { |
| // Record that this class initializer is reachable from the tracing roots. |
| recordClassInitializerReachableFromTracingRoots(clazz); |
| } |
| } |
| |
| ProgramMethod classInitializer = clazz.getProgramClassInitializer(); |
| if (classInitializer != null) { |
| if (!enqueueMethod(classInitializer)) { |
| // This class initializer is already seen in the current context, thus all of the parent |
| // class initializers are also seen in the current context. |
| return; |
| } |
| } |
| |
| triggerClassInitializer(clazz.getSuperType()); |
| |
| MergeGroup other = allGroups.get(clazz); |
| if (other != null && other != group) { |
| for (DexProgramClass member : other) { |
| triggerClassInitializer(member); |
| } |
| } |
| } |
| |
| @Override |
| public void registerInitClass(DexType type) { |
| DexType rewrittenType = appView.graphLens().lookupType(type); |
| triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenType); |
| } |
| |
| @Override |
| public void registerInvokeDirect(DexMethod method) { |
| DexMethod rewrittenMethod = |
| appView.graphLens().lookupInvokeDirect(method, getContext()).getReference(); |
| MethodResolutionResult resolutionResult = |
| appView.appInfo().resolveMethodOnClass(rewrittenMethod); |
| if (resolutionResult.isSingleResolution() |
| && resolutionResult.getResolvedHolder().isProgramClass()) { |
| enqueueMethod(resolutionResult.getResolvedProgramMethod()); |
| } |
| } |
| |
| @Override |
| public void registerInvokeInterface(DexMethod method) { |
| DexMethod rewrittenMethod = |
| appView.graphLens().lookupInvokeInterface(method, getContext()).getReference(); |
| DexClassAndMethod resolvedMethod = |
| appView.appInfo().resolveMethodOnInterface(rewrittenMethod).getResolutionPair(); |
| if (resolvedMethod != null) { |
| fail(); |
| } |
| } |
| |
| @Override |
| public void registerInvokeStatic(DexMethod method) { |
| DexMethod rewrittenMethod = |
| appView.graphLens().lookupInvokeStatic(method, getContext()).getReference(); |
| ProgramMethod resolvedMethod = |
| appView |
| .appInfo() |
| .unsafeResolveMethodDueToDexFormat(rewrittenMethod) |
| .getResolvedProgramMethod(); |
| if (resolvedMethod != null) { |
| triggerClassInitializerIfNotAlreadyTriggeredInContext(resolvedMethod.getHolder()); |
| enqueueMethod(resolvedMethod); |
| } |
| } |
| |
| @Override |
| public void registerInvokeSuper(DexMethod method) { |
| DexMethod rewrittenMethod = |
| appView.graphLens().lookupInvokeSuper(method, getContext()).getReference(); |
| ProgramMethod superTarget = |
| asProgramMethodOrNull( |
| appView.appInfo().lookupSuperTarget(rewrittenMethod, getContext())); |
| if (superTarget != null) { |
| enqueueMethod(superTarget); |
| } |
| } |
| |
| @Override |
| public void registerInvokeVirtual(DexMethod method) { |
| DexMethod rewrittenMethod = |
| appView.graphLens().lookupInvokeVirtual(method, getContext()).getReference(); |
| DexClassAndMethod resolvedMethod = |
| appView.appInfo().resolveMethodOnClass(rewrittenMethod).getResolutionPair(); |
| if (resolvedMethod != null) { |
| if (!resolvedMethod.getHolder().isEffectivelyFinal(appView)) { |
| fail(); |
| } else if (resolvedMethod.isProgramMethod()) { |
| enqueueMethod(resolvedMethod.asProgramMethod()); |
| } |
| } |
| } |
| |
| @Override |
| public void registerNewInstance(DexType type) { |
| DexType rewrittenType = appView.graphLens().lookupType(type); |
| triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenType); |
| } |
| |
| @Override |
| public void registerStaticFieldRead(DexField field) { |
| DexField rewrittenField = appView.graphLens().lookupField(field); |
| triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenField.getHolderType()); |
| } |
| |
| @Override |
| public void registerStaticFieldWrite(DexField field) { |
| DexField rewrittenField = appView.graphLens().lookupField(field); |
| triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenField.getHolderType()); |
| } |
| |
| @Override |
| public void registerTypeReference(DexType type) { |
| // Intentionally empty, new-array etc. does not trigger any class initialization. |
| } |
| |
| @Override |
| public void registerCallSite(DexCallSite callSite) { |
| if (isLambdaMetafactoryMethod(callSite, appView.appInfo())) { |
| // Use of lambda metafactory does not trigger any class initialization. |
| } else { |
| fail(); |
| } |
| } |
| |
| @Override |
| public void registerCheckCast(DexType type) { |
| // Intentionally empty, does not trigger any class initialization. |
| } |
| |
| @Override |
| public void registerConstClass( |
| DexType type, ListIterator<? extends CfOrDexInstruction> iterator) { |
| // Intentionally empty, does not trigger any class initialization. |
| } |
| |
| @Override |
| public void registerInstanceFieldRead(DexField field) { |
| // Intentionally empty, does not trigger any class initialization. |
| } |
| |
| @Override |
| public void registerInstanceFieldWrite(DexField field) { |
| // Intentionally empty, does not trigger any class initialization. |
| } |
| |
| @Override |
| public void registerInstanceOf(DexType type) { |
| // Intentionally empty, does not trigger any class initialization. |
| } |
| |
| @Override |
| public void registerExceptionGuard(DexType guard) { |
| // Intentionally empty, does not trigger any class initialization. |
| } |
| } |
| } |
| } |