Optimizing :enter - :exit pairs.
Doing so by not letting any events between XXX:enter and XXX:exit
events. This eliminates unnecessary permutations.
Example: 2 threads with 3 enter-exit pairs each would have produced 924
permutations before this, now only 20.
Bug: 120628042
Change-Id: Ia243d273a1d90202011679cc7520ea4c9e43918b
Tests: All tests that use race condition framework
diff --git a/src/com/android/launcher3/util/RaceConditionTracker.java b/src/com/android/launcher3/util/RaceConditionTracker.java
index 8b06787..6954d0e 100644
--- a/src/com/android/launcher3/util/RaceConditionTracker.java
+++ b/src/com/android/launcher3/util/RaceConditionTracker.java
@@ -24,6 +24,8 @@
public class RaceConditionTracker {
public final static boolean ENTER = true;
public final static boolean EXIT = false;
+ static final String ENTER_POSTFIX = "enter";
+ static final String EXIT_POSTFIX = "exit";
public interface EventProcessor {
void onEvent(String eventName);
@@ -46,7 +48,7 @@
}
public static String enterExitEvt(String eventName, boolean isEnter) {
- return eventName + ":" + (isEnter ? "enter" : "exit");
+ return eventName + ":" + (isEnter ? ENTER_POSTFIX : EXIT_POSTFIX);
}
public static String enterEvt(String eventName) {
diff --git a/tests/src/com/android/launcher3/util/RaceConditionReproducer.java b/tests/src/com/android/launcher3/util/RaceConditionReproducer.java
index 316e40d..0235f95 100644
--- a/tests/src/com/android/launcher3/util/RaceConditionReproducer.java
+++ b/tests/src/com/android/launcher3/util/RaceConditionReproducer.java
@@ -16,6 +16,9 @@
package com.android.launcher3.util;
+import static com.android.launcher3.util.RaceConditionTracker.ENTER_POSTFIX;
+import static com.android.launcher3.util.RaceConditionTracker.EXIT_POSTFIX;
+
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
@@ -46,7 +49,7 @@
* If an event A occurs before event B in the sequence, this is how execution order looks like:
* Events: ... A ... B ...
* Events and instructions, guaranteed order:
- * (instructions executed prior to A) A ... B (instructions executed after B)
+ * (instructions executed prior to A) A ... B (instructions executed after B)
*
* Each iteration has 3 parts (phases).
* Phase 1. Picking a previously seen event subsequence that we believe can have previously unseen
@@ -58,6 +61,8 @@
* Phase 3. Releasing all threads and letting the test iteration run till its end.
*
* The iterations end when all seen paths have been declared “uncontinuable”.
+ *
+ * When we register event XXX:enter, we hold all other events until we register XXX:exit.
*/
public class RaceConditionReproducer implements RaceConditionTracker.EventProcessor {
private static final String TAG = "RaceConditionReproducer";
@@ -81,7 +86,7 @@
private final Map<String, EventNode> mNextEvents = new HashMap<>();
// Whether we believe that further iterations will not be able to add more events to
// mNextEvents.
- private boolean mStoppedAddingChildren = false;
+ private boolean mStoppedAddingChildren = true;
private void debugDump(StringBuilder sb, int indent, String name) {
for (int i = 0; i < indent; ++i) sb.append('.');
@@ -134,6 +139,8 @@
}
}
if (!mStoppedAddingChildren) {
+ // Mark that we have finished adding children. It will remain true if no new
+ // children are added, or will be set to false upon adding a new child.
mStoppedAddingChildren = true;
return true;
}
@@ -216,6 +223,7 @@
RaceConditionTracker.setEventProcessor(null);
runResumeAllEventsCallbackLocked();
assertTrue("Non-empty postponed events", mPostponedEvents.isEmpty());
+ assertTrue("Last registered event is :enter", lastEventAsEnter() == null);
// No events came after mLastRegisteredEvent. It doesn't make sense to come to it again
// because we won't see new continuations.
@@ -246,12 +254,36 @@
}
/**
+ * Returns whether the last event was not an XXX:enter, or this event is a matching XXX:exit.
+ */
+ private boolean canRegisterEventNowLocked(String event) {
+ final String lastEventAsEnter = lastEventAsEnter();
+ final String thisEventAsExit = eventAsExit(event);
+
+ if (lastEventAsEnter != null) {
+ if (!lastEventAsEnter.equals(thisEventAsExit)) {
+ assertTrue("YYY:exit after XXX:enter", thisEventAsExit == null);
+ // Last event was :enter, but this event is not :exit.
+ return false;
+ }
+ } else {
+ // Previous event was not :enter.
+ assertTrue(":exit after a non-enter event", thisEventAsExit == null);
+ }
+ return true;
+ }
+
+ /**
* Registers an event issued by the app and returns null or decides that the event must be
* postponed, and returns an object to wait on.
*/
private synchronized Semaphore tryRegisterEvent(String event) {
Log.d(TAG, "Event issued by the app: " + event);
+ if (!canRegisterEventNowLocked(event)) {
+ return createWaitObjectForPostponedEventLocked(event);
+ }
+
if (mRegisteredEventCount < mSequenceToFollow.size()) {
// We are in the first part of the iteration. We only register events that follow the
// mSequenceToFollow and postponing all other events.
@@ -288,9 +320,14 @@
return createWaitObjectForPostponedEventLocked(event);
}
} else {
- // The second phase of the iteration. We are past the growth point and register
+ // The third phase of the iteration. We are past the growth point and register
// everything that comes.
registerEventLocked(event);
+ // Register events that may have been postponed while waiting for an :exit event
+ // during the third phase. We don't do this if just registered event is :enter.
+ if (eventAsEnter(event) == null && mRegisteredEventCount > mSequenceToFollow.size()) {
+ registerPostponedEventsLocked(new HashSet<>(mPostponedEvents.keySet()));
+ }
}
return null;
}
@@ -347,6 +384,11 @@
private void registerPostponedEventsLocked(Collection<String> events) {
for (String event : events) {
registerPostponedEventLocked(event);
+ if (eventAsEnter(event) != null) {
+ // Once :enter is registered, switch to waiting for :exit to come. Won't register
+ // other postponed events.
+ break;
+ }
}
}
@@ -355,14 +397,51 @@
registerEventLocked(event);
}
+ /**
+ * If the last registered event was XXX:enter, returns XXX, otherwise, null.
+ */
+ private String lastEventAsEnter() {
+ return eventAsEnter(mCurrentSequence.substring(mCurrentSequence.lastIndexOf("|") + 1));
+ }
+
+ /**
+ * If the event is XXX:postfix, returns XXX, otherwise, null.
+ */
+ private static String prefixFromPostfixedEvent(String event, String postfix) {
+ final int columnPos = event.indexOf(':');
+ if (columnPos != -1 && postfix.equals(event.substring(columnPos + 1))) {
+ return event.substring(0, columnPos);
+ }
+ return null;
+ }
+
+ /**
+ * If the event is XXX:enter, returns XXX, otherwise, null.
+ */
+ private static String eventAsEnter(String event) {
+ return prefixFromPostfixedEvent(event, ENTER_POSTFIX);
+ }
+
+ /**
+ * If the event is XXX:exit, returns XXX, otherwise, null.
+ */
+ private static String eventAsExit(String event) {
+ return prefixFromPostfixedEvent(event, EXIT_POSTFIX);
+ }
+
private void registerEventLocked(String event) {
+ assertTrue(canRegisterEventNowLocked(event));
+
Log.d(TAG, "Actually registering event: " + event);
EventNode next = mLastRegisteredEvent.mNextEvents.get(event);
if (next == null) {
// This event wasn't seen after mLastRegisteredEvent.
next = new EventNode();
mLastRegisteredEvent.mNextEvents.put(event, next);
- mLastRegisteredEvent.mStoppedAddingChildren = false;
+ // The fact that we've added a new event after the previous one means that the
+ // previous event is still a growth point, unless this event is :exit, which means
+ // that the previous event is :enter.
+ mLastRegisteredEvent.mStoppedAddingChildren = eventAsExit(event) != null;
}
mLastRegisteredEvent = next;
@@ -371,12 +450,6 @@
if (mCurrentSequence.length() > 0) mCurrentSequence.append("|");
mCurrentSequence.append(event);
Log.d(TAG, "Repro sequence: " + mCurrentSequence);
-
- if (mRegisteredEventCount == mSequenceToFollow.size() + 1) {
- // We just entered the third phase of the iteration, i.e. registered an event after
- // the growth point. Now we can let go of all postponed events.
- runResumeAllEventsCallbackLocked();
- }
}
private void runResumeAllEventsCallbackLocked() {
diff --git a/tests/src/com/android/launcher3/util/RaceConditionReproducerTest.java b/tests/src/com/android/launcher3/util/RaceConditionReproducerTest.java
index 7dde5cc..3fc268e 100644
--- a/tests/src/com/android/launcher3/util/RaceConditionReproducerTest.java
+++ b/tests/src/com/android/launcher3/util/RaceConditionReproducerTest.java
@@ -77,6 +77,46 @@
}
@Test
+ @Ignore // The test is too long for continuous testing.
+ // 2 threads, 3 events, including enter-exit pairs each.
+ public void test3_3_enter_exit() throws Exception {
+ final RaceConditionReproducer eventProcessor = new RaceConditionReproducer();
+ boolean sawTheValidSequence = false;
+
+ for (; ; ) {
+ eventProcessor.startIteration();
+ Thread tb = new Thread(() -> {
+ RaceConditionTracker.onEvent("B1:enter");
+ RaceConditionTracker.onEvent("B1:exit");
+ RaceConditionTracker.onEvent("B2");
+ RaceConditionTracker.onEvent("B3:enter");
+ RaceConditionTracker.onEvent("B3:exit");
+ });
+ tb.start();
+
+ RaceConditionTracker.onEvent("A1");
+ RaceConditionTracker.onEvent("A2:enter");
+ RaceConditionTracker.onEvent("A2:exit");
+ RaceConditionTracker.onEvent("A3:enter");
+ RaceConditionTracker.onEvent("A3:exit");
+
+ tb.join();
+ final boolean needMoreIterations = eventProcessor.finishIteration();
+
+ sawTheValidSequence = sawTheValidSequence ||
+ "B1:enter|B1:exit|A1|A2:enter|A2:exit|B2|A3:enter|A3:exit|B3:enter|B3:exit".
+ equals(eventProcessor.getCurrentSequenceString());
+
+ if (!needMoreIterations) break;
+ }
+
+ assertEquals("Wrong number of leaf nodes",
+ factorial(3 + 3) / (factorial(3) * factorial(3)),
+ eventProcessor.numberOfLeafNodes());
+ assertTrue(sawTheValidSequence);
+ }
+
+ @Test
// 2 threads, 3 events each; reproducing a particular event sequence.
public void test3_3_ReproMode() throws Exception {
final RaceConditionReproducer eventProcessor = new RaceConditionReproducer(
@@ -122,4 +162,42 @@
factorial(2 + 2 + 1) / (factorial(2) * factorial(2) * factorial(1)),
eventProcessor.numberOfLeafNodes());
}
+
+ @Test
+ @Ignore // The test is too long for continuous testing.
+ // 2 threads with 2 events; 1 thread with 1 event. Includes enter-exit pairs.
+ public void test2_1_2_enter_exit() throws Exception {
+ final RaceConditionReproducer eventProcessor = new RaceConditionReproducer();
+
+ for (; ; ) {
+ eventProcessor.startIteration();
+ Thread tb = new Thread(() -> {
+ RaceConditionTracker.onEvent("B1:enter");
+ RaceConditionTracker.onEvent("B1:exit");
+ RaceConditionTracker.onEvent("B2:enter");
+ RaceConditionTracker.onEvent("B2:exit");
+ });
+ tb.start();
+
+ Thread tc = new Thread(() -> {
+ RaceConditionTracker.onEvent("C1:enter");
+ RaceConditionTracker.onEvent("C1:exit");
+ });
+ tc.start();
+
+ RaceConditionTracker.onEvent("A1:enter");
+ RaceConditionTracker.onEvent("A1:exit");
+ RaceConditionTracker.onEvent("A2:enter");
+ RaceConditionTracker.onEvent("A2:exit");
+
+ tb.join();
+ tc.join();
+
+ if (!eventProcessor.finishIteration()) break;
+ }
+
+ assertEquals("Wrong number of leaf nodes",
+ factorial(2 + 2 + 1) / (factorial(2) * factorial(2) * factorial(1)),
+ eventProcessor.numberOfLeafNodes());
+ }
}