Move SyncStateMachine to staticlibs
Test: mm
Change-Id: I51685a454a3d0fab578fef1eeb42d600adef06e6
diff --git a/staticlibs/Android.bp b/staticlibs/Android.bp
index e2834b0..71f388d 100644
--- a/staticlibs/Android.bp
+++ b/staticlibs/Android.bp
@@ -39,12 +39,13 @@
"device/com/android/net/module/util/DeviceConfigUtils.java",
"device/com/android/net/module/util/DomainUtils.java",
"device/com/android/net/module/util/FdEventsReader.java",
+ "device/com/android/net/module/util/FeatureVersions.java",
+ "device/com/android/net/module/util/HandlerUtils.java",
"device/com/android/net/module/util/NetworkMonitorUtils.java",
"device/com/android/net/module/util/PacketReader.java",
"device/com/android/net/module/util/SharedLog.java",
"device/com/android/net/module/util/SocketUtils.java",
- "device/com/android/net/module/util/FeatureVersions.java",
- "device/com/android/net/module/util/HandlerUtils.java",
+ "device/com/android/net/module/util/SyncStateMachine.java",
// This library is used by system modules, for which the system health impact of Kotlin
// has not yet been evaluated. Annotations may need jarjar'ing.
// "src_devicecommon/**/*.kt",
@@ -68,6 +69,7 @@
"//packages/modules/CaptivePortalLogin",
],
static_libs: [
+ "modules-utils-statemachine",
"net-utils-framework-common",
],
libs: [
diff --git a/staticlibs/device/com/android/net/module/util/SyncStateMachine.java b/staticlibs/device/com/android/net/module/util/SyncStateMachine.java
new file mode 100644
index 0000000..cc113a4
--- /dev/null
+++ b/staticlibs/device/com/android/net/module/util/SyncStateMachine.java
@@ -0,0 +1,333 @@
+/**
+ * Copyright (C) 2023 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.net.module.util;
+
+import android.annotation.NonNull;
+import android.annotation.Nullable;
+import android.os.Message;
+import android.util.ArrayMap;
+import android.util.ArraySet;
+import android.util.Log;
+
+import com.android.internal.util.State;
+
+import java.util.ArrayDeque;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+
+/**
+ * An implementation of a state machine, meant to be called synchronously.
+ *
+ * This class implements a finite state automaton based on the same State
+ * class as StateMachine.
+ * All methods of this class must be called on only one thread.
+ */
+public class SyncStateMachine {
+ @NonNull private final String mName;
+ @NonNull private final Thread mMyThread;
+ private final boolean mDbg;
+ private final ArrayMap<State, StateInfo> mStateInfo = new ArrayMap<>();
+
+ // mCurrentState is the current state. mDestState is the target state that mCurrentState will
+ // transition to. The value of mDestState can be changed when a state processes a message and
+ // calls #transitionTo, but it cannot be changed during the state transition. When the state
+ // transition is complete, mDestState will be set to mCurrentState. Both mCurrentState and
+ // mDestState only be null before state machine starts and must only be touched on mMyThread.
+ @Nullable private State mCurrentState;
+ @Nullable private State mDestState;
+ private final ArrayDeque<Message> mSelfMsgQueue = new ArrayDeque<Message>();
+
+ // MIN_VALUE means not currently processing any message.
+ private int mCurrentlyProcessing = Integer.MIN_VALUE;
+ // Indicates whether automaton can send self message. Self messages can only be sent by
+ // automaton from State#enter, State#exit, or State#processMessage. Calling from outside
+ // of State is not allowed.
+ private boolean mSelfMsgAllowed = false;
+
+ /**
+ * A information class about a state and its parent. Used to maintain the state hierarchy.
+ */
+ public static class StateInfo {
+ /** The state who owns this StateInfo. */
+ public final State state;
+ /** The parent state. */
+ public final State parent;
+ // True when the state has been entered and on the stack.
+ private boolean mActive;
+
+ public StateInfo(@NonNull final State child, @Nullable final State parent) {
+ this.state = child;
+ this.parent = parent;
+ }
+ }
+
+ /**
+ * The constructor.
+ *
+ * @param name of this machine.
+ * @param thread the running thread of this machine. It must either be the thread on which this
+ * constructor is called, or a thread that is not started yet.
+ */
+ public SyncStateMachine(@NonNull final String name, @NonNull final Thread thread) {
+ this(name, thread, false /* debug */);
+ }
+
+ /**
+ * The constructor.
+ *
+ * @param name of this machine.
+ * @param thread the running thread of this machine. It must either be the thread on which this
+ * constructor is called, or a thread that is not started yet.
+ * @param dbg whether to print debug logs.
+ */
+ public SyncStateMachine(@NonNull final String name, @NonNull final Thread thread,
+ final boolean dbg) {
+ mMyThread = thread;
+ // Machine can either be setup from machine thread or before machine thread started.
+ ensureCorrectOrNotStartedThread();
+
+ mName = name;
+ mDbg = dbg;
+ }
+
+ /**
+ * Add all of states to the state machine. Different StateInfos which have same state are not
+ * allowed. In other words, a state can not have multiple parent states. #addAllStates can
+ * only be called once either from mMyThread or before mMyThread started.
+ */
+ public final void addAllStates(@NonNull final List<StateInfo> stateInfos) {
+ ensureCorrectOrNotStartedThread();
+
+ if (mCurrentState != null) {
+ throw new IllegalStateException("State only can be added before started");
+ }
+
+ if (stateInfos.isEmpty()) throw new IllegalStateException("Empty state is not allowed");
+
+ if (!mStateInfo.isEmpty()) throw new IllegalStateException("States are already configured");
+
+ final Set<Class> usedClasses = new ArraySet<>();
+ for (final StateInfo info : stateInfos) {
+ Objects.requireNonNull(info.state);
+ if (!usedClasses.add(info.state.getClass())) {
+ throw new IllegalStateException("Adding the same state multiple times in a state "
+ + "machine is forbidden because it tends to be confusing; it can be done "
+ + "with anonymous subclasses but consider carefully whether you want to "
+ + "use a single state or other alternatives instead.");
+ }
+
+ mStateInfo.put(info.state, info);
+ }
+
+ // Check whether all of parent states indicated from StateInfo are added.
+ for (final StateInfo info : stateInfos) {
+ if (info.parent != null) ensureExistingState(info.parent);
+ }
+ }
+
+ /**
+ * Start the state machine. The initial state can't be child state.
+ *
+ * @param initialState the first state of this machine. The state must be exact state object
+ * setting up by {@link #addAllStates}, not a copy of it.
+ */
+ public final void start(@NonNull final State initialState) {
+ ensureCorrectThread();
+ ensureExistingState(initialState);
+
+ mDestState = initialState;
+ mSelfMsgAllowed = true;
+ performTransitions();
+ mSelfMsgAllowed = false;
+ // If sendSelfMessage was called inside initialState#enter(), mSelfMsgQueue must be
+ // processed.
+ maybeProcessSelfMessageQueue();
+ }
+
+ /**
+ * Process the message synchronously then perform state transition. This method is used
+ * externally to the automaton to request that the automaton process the given message.
+ * The message is processed sequentially, so calling this method recursively is not permitted.
+ * In other words, using this method inside State#enter, State#exit, or State#processMessage
+ * is incorrect and will result in an IllegalStateException.
+ */
+ public final void processMessage(int what, int arg1, int arg2, @Nullable Object obj) {
+ ensureCorrectThread();
+
+ if (mCurrentlyProcessing != Integer.MIN_VALUE) {
+ throw new IllegalStateException("Message(" + mCurrentlyProcessing
+ + ") is still being processed");
+ }
+
+ // mCurrentlyProcessing tracks the external message request and it prevents this method to
+ // be called recursively. Once this message is processed and the transitions have been
+ // performed, the automaton will process the self message queue. The messages in the self
+ // message queue are added from within the automaton during processing external message.
+ // mCurrentlyProcessing is still the original external one and it will not prevent self
+ // messages from being processed.
+ mCurrentlyProcessing = what;
+ final Message msg = Message.obtain(null, what, arg1, arg2, obj);
+ currentStateProcessMessageThenPerformTransitions(msg);
+ msg.recycle();
+ maybeProcessSelfMessageQueue();
+
+ mCurrentlyProcessing = Integer.MIN_VALUE;
+ }
+
+ private void maybeProcessSelfMessageQueue() {
+ while (!mSelfMsgQueue.isEmpty()) {
+ currentStateProcessMessageThenPerformTransitions(mSelfMsgQueue.poll());
+ }
+ }
+
+ private void currentStateProcessMessageThenPerformTransitions(@NonNull final Message msg) {
+ mSelfMsgAllowed = true;
+ StateInfo consideredState = mStateInfo.get(mCurrentState);
+ while (null != consideredState) {
+ // Ideally this should compare with IState.HANDLED, but it is not public field so just
+ // checking whether the return value is true (IState.HANDLED = true).
+ if (consideredState.state.processMessage(msg)) {
+ if (mDbg) {
+ Log.d(mName, "State " + consideredState.state
+ + " processed message " + msg.what);
+ }
+ break;
+ }
+ consideredState = mStateInfo.get(consideredState.parent);
+ }
+ if (null == consideredState) {
+ Log.wtf(mName, "Message " + msg.what + " was not handled");
+ }
+
+ performTransitions();
+ mSelfMsgAllowed = false;
+ }
+
+ /**
+ * Send self message during state transition.
+ *
+ * Must only be used inside State processMessage, enter or exit. The typical use case is
+ * something wrong happens during state transition, sending an error message which would be
+ * handled after finishing current state transitions.
+ */
+ public final void sendSelfMessage(int what, int arg1, int arg2, Object obj) {
+ if (!mSelfMsgAllowed) {
+ throw new IllegalStateException("sendSelfMessage can only be called inside "
+ + "State#enter, State#exit or State#processMessage");
+ }
+
+ mSelfMsgQueue.add(Message.obtain(null, what, arg1, arg2, obj));
+ }
+
+ /**
+ * Transition to destination state. Upon returning from processMessage the automaton will
+ * transition to the given destination state.
+ *
+ * This function can NOT be called inside the State enter and exit function. The transition
+ * target is always defined and can never be changed mid-way of state transition.
+ *
+ * @param destState will be the state to transition to. The state must be the same instance set
+ * up by {@link #addAllStates}, not a copy of it.
+ */
+ public final void transitionTo(@NonNull final State destState) {
+ if (mDbg) Log.d(mName, "transitionTo " + destState);
+ ensureCorrectThread();
+ ensureExistingState(destState);
+
+ if (mDestState == mCurrentState) {
+ mDestState = destState;
+ } else {
+ throw new IllegalStateException("Destination already specified");
+ }
+ }
+
+ private void performTransitions() {
+ // 1. Determine the common ancestor state of current/destination states
+ // 2. Invoke state exit list from current state to common ancestor state.
+ // 3. Invoke state enter list from common ancestor state to destState by going
+ // through mEnterStateStack.
+ if (mDestState == mCurrentState) return;
+
+ final StateInfo commonAncestor = getLastActiveAncestor(mStateInfo.get(mDestState));
+
+ executeExitMethods(commonAncestor, mStateInfo.get(mCurrentState));
+ executeEnterMethods(commonAncestor, mStateInfo.get(mDestState));
+ mCurrentState = mDestState;
+ }
+
+ // Null is the root of all states.
+ private StateInfo getLastActiveAncestor(@Nullable final StateInfo start) {
+ if (null == start || start.mActive) return start;
+
+ return getLastActiveAncestor(mStateInfo.get(start.parent));
+ }
+
+ // Call the exit method from current state to common ancestor state.
+ // Both the commonAncestor and exitingState StateInfo can be null because null is the ancestor
+ // of all states.
+ // For example: When transitioning from state1 to state2, the
+ // executeExitMethods(commonAncestor, exitingState) function will be called twice, once with
+ // null and state1 as the argument, and once with null and null as the argument.
+ // root
+ // | \
+ // current <- state1 state2 -> destination
+ private void executeExitMethods(@Nullable StateInfo commonAncestor,
+ @Nullable StateInfo exitingState) {
+ if (commonAncestor == exitingState) return;
+
+ if (mDbg) Log.d(mName, exitingState.state + " exit()");
+ exitingState.state.exit();
+ exitingState.mActive = false;
+ executeExitMethods(commonAncestor, mStateInfo.get(exitingState.parent));
+ }
+
+ // Call the enter method from common ancestor state to destination state.
+ // Both the commonAncestor and enteringState StateInfo can be null because null is the ancestor
+ // of all states.
+ // For example: When transitioning from state1 to state2, the
+ // executeEnterMethods(commonAncestor, enteringState) function will be called twice, once with
+ // null and state2 as the argument, and once with null and null as the argument.
+ // root
+ // | \
+ // current <- state1 state2 -> destination
+ private void executeEnterMethods(@Nullable StateInfo commonAncestor,
+ @Nullable StateInfo enteringState) {
+ if (enteringState == commonAncestor) return;
+
+ executeEnterMethods(commonAncestor, mStateInfo.get(enteringState.parent));
+ if (mDbg) Log.d(mName, enteringState.state + " enter()");
+ enteringState.state.enter();
+ enteringState.mActive = true;
+ }
+
+ private void ensureCorrectThread() {
+ if (!mMyThread.equals(Thread.currentThread())) {
+ throw new IllegalStateException("Called from wrong thread");
+ }
+ }
+
+ private void ensureCorrectOrNotStartedThread() {
+ if (!mMyThread.isAlive()) return;
+
+ ensureCorrectThread();
+ }
+
+ private void ensureExistingState(@NonNull final State state) {
+ if (!mStateInfo.containsKey(state)) throw new IllegalStateException("Invalid state");
+ }
+}
diff --git a/staticlibs/tests/unit/src/com/android/net/module/util/SyncStateMachineTest.kt b/staticlibs/tests/unit/src/com/android/net/module/util/SyncStateMachineTest.kt
new file mode 100644
index 0000000..5fe962b
--- /dev/null
+++ b/staticlibs/tests/unit/src/com/android/net/module/util/SyncStateMachineTest.kt
@@ -0,0 +1,294 @@
+/**
+ * Copyright (C) 2023 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.net.module.util
+
+import android.os.Message
+import androidx.test.ext.junit.runners.AndroidJUnit4
+import androidx.test.filters.SmallTest
+import com.android.internal.util.State
+import com.android.net.module.util.SyncStateMachine.StateInfo
+import java.util.ArrayDeque
+import java.util.ArrayList
+import kotlin.test.assertFailsWith
+import org.junit.Assert.assertEquals
+import org.junit.Assert.assertTrue
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.mockito.ArgumentMatchers.any
+import org.mockito.Mockito.inOrder
+import org.mockito.Mockito.spy
+import org.mockito.Mockito.verifyNoMoreInteractions
+
+private const val MSG_INVALID = -1
+private const val MSG_1 = 1
+private const val MSG_2 = 2
+private const val MSG_3 = 3
+private const val MSG_4 = 4
+private const val MSG_5 = 5
+private const val MSG_6 = 6
+private const val MSG_7 = 7
+private const val ARG_1 = 100
+private const val ARG_2 = 200
+
+@RunWith(AndroidJUnit4::class)
+@SmallTest
+class SynStateMachineTest {
+ private val mState1 = spy(object : TestState(MSG_1) {})
+ private val mState2 = spy(object : TestState(MSG_2) {})
+ private val mState3 = spy(object : TestState(MSG_3) {})
+ private val mState4 = spy(object : TestState(MSG_4) {})
+ private val mState5 = spy(object : TestState(MSG_5) {})
+ private val mState6 = spy(object : TestState(MSG_6) {})
+ private val mState7 = spy(object : TestState(MSG_7) {})
+ private val mInOrder = inOrder(mState1, mState2, mState3, mState4, mState5, mState6, mState7)
+ // Lazy initialize to make sure running in test thread.
+ private val mSM by lazy {
+ SyncStateMachine("TestSyncStateMachine", Thread.currentThread(), true /* debug */)
+ }
+ private val mAllStates = ArrayList<StateInfo>()
+
+ private val mMsgProcessedResults = ArrayDeque<Pair<State, Int>>()
+
+ open inner class TestState(val expected: Int) : State() {
+ // Control destination state in obj field for testing.
+ override fun processMessage(msg: Message): Boolean {
+ mMsgProcessedResults.add(this to msg.what)
+ assertEquals(ARG_1, msg.arg1)
+ assertEquals(ARG_2, msg.arg2)
+
+ if (msg.what == expected) {
+ msg.obj?.let { mSM.transitionTo(it as State) }
+ return true
+ }
+
+ return false
+ }
+ }
+
+ private fun verifyNoMoreInteractions() {
+ verifyNoMoreInteractions(mState1, mState2, mState3, mState4, mState5, mState6)
+ }
+
+ private fun processMessage(what: Int, toState: State?) {
+ mSM.processMessage(what, ARG_1, ARG_2, toState)
+ }
+
+ private fun verifyMessageProcessedBy(what: Int, vararg processedStates: State) {
+ for (state in processedStates) {
+ // InOrder.verify can't check the Message content here because SyncSM will recycle the
+ // message after it's been processed. SyncSM reuses the same Message instance for all
+ // messages it processes. So, if using InOrder.verify to verify the content of a message
+ // after SyncSM has processed it, the content would be wrong.
+ mInOrder.verify(state).processMessage(any())
+ val (processedState, msgWhat) = mMsgProcessedResults.remove()
+ assertEquals(state, processedState)
+ assertEquals(what, msgWhat)
+ }
+ assertTrue(mMsgProcessedResults.isEmpty())
+ }
+
+ @Test
+ fun testInitialState() {
+ // mState1 -> initial
+ // |
+ // mState2
+ mAllStates.add(StateInfo(mState1, null))
+ mAllStates.add(StateInfo(mState2, mState1))
+ mSM.addAllStates(mAllStates)
+
+ mSM.start(mState1)
+ mInOrder.verify(mState1).enter()
+ verifyNoMoreInteractions()
+ }
+
+ @Test
+ fun testStartFromLeafState() {
+ // mState1 -> initial
+ // |
+ // mState2
+ // |
+ // mState3
+ mAllStates.add(StateInfo(mState1, null))
+ mAllStates.add(StateInfo(mState2, mState1))
+ mAllStates.add(StateInfo(mState3, mState2))
+ mSM.addAllStates(mAllStates)
+
+ mSM.start(mState3)
+ mInOrder.verify(mState1).enter()
+ mInOrder.verify(mState2).enter()
+ mInOrder.verify(mState3).enter()
+ verifyNoMoreInteractions()
+ }
+
+ private fun verifyStart() {
+ mSM.addAllStates(mAllStates)
+ mSM.start(mState1)
+ mInOrder.verify(mState1).enter()
+ verifyNoMoreInteractions()
+ }
+
+ fun addState(state: State, parent: State? = null) {
+ mAllStates.add(StateInfo(state, parent))
+ }
+
+ @Test
+ fun testAddState() {
+ // Add duplicated states.
+ mAllStates.add(StateInfo(mState1, null))
+ mAllStates.add(StateInfo(mState1, null))
+ assertFailsWith(IllegalStateException::class) {
+ mSM.addAllStates(mAllStates)
+ }
+ }
+
+ @Test
+ fun testProcessMessage() {
+ // mState1
+ // |
+ // mState2
+ addState(mState1)
+ addState(mState2, mState1)
+ verifyStart()
+
+ processMessage(MSG_1, null)
+ verifyMessageProcessedBy(MSG_1, mState1)
+ verifyNoMoreInteractions()
+ }
+
+ @Test
+ fun testTwoStates() {
+ // mState1 <-initial, mState2
+ addState(mState1)
+ addState(mState2)
+ verifyStart()
+
+ // Test transition to mState2
+ processMessage(MSG_1, mState2)
+ verifyMessageProcessedBy(MSG_1, mState1)
+ mInOrder.verify(mState1).exit()
+ mInOrder.verify(mState2).enter()
+ verifyNoMoreInteractions()
+
+ // If set destState to mState2 (current state), no state transition.
+ processMessage(MSG_2, mState2)
+ verifyMessageProcessedBy(MSG_2, mState2)
+ verifyNoMoreInteractions()
+ }
+
+ @Test
+ fun testTwoStateTrees() {
+ // mState1 -> initial mState4
+ // / \ / \
+ // mState2 mState3 mState5 mState6
+ addState(mState1)
+ addState(mState2, mState1)
+ addState(mState3, mState1)
+ addState(mState4)
+ addState(mState5, mState4)
+ addState(mState6, mState4)
+ verifyStart()
+
+ // mState1 -> current mState4
+ // / \ / \
+ // mState2 mState3 -> dest mState5 mState6
+ processMessage(MSG_1, mState3)
+ verifyMessageProcessedBy(MSG_1, mState1)
+ mInOrder.verify(mState3).enter()
+ verifyNoMoreInteractions()
+
+ // mState1 mState4
+ // / \ / \
+ // dest <- mState2 mState3 -> current mState5 mState6
+ processMessage(MSG_1, mState2)
+ verifyMessageProcessedBy(MSG_1, mState3, mState1)
+ mInOrder.verify(mState3).exit()
+ mInOrder.verify(mState2).enter()
+ verifyNoMoreInteractions()
+
+ // mState1 mState4
+ // / \ / \
+ // current <- mState2 mState3 mState5 mState6 -> dest
+ processMessage(MSG_2, mState6)
+ verifyMessageProcessedBy(MSG_2, mState2)
+ mInOrder.verify(mState2).exit()
+ mInOrder.verify(mState1).exit()
+ mInOrder.verify(mState4).enter()
+ mInOrder.verify(mState6).enter()
+ verifyNoMoreInteractions()
+ }
+
+ @Test
+ fun testMultiDepthTransition() {
+ // mState1 -> current
+ // | \
+ // mState2 mState6
+ // | \ |
+ // mState3 mState5 mState7
+ // |
+ // mState4
+ addState(mState1)
+ addState(mState2, mState1)
+ addState(mState6, mState1)
+ addState(mState3, mState2)
+ addState(mState5, mState2)
+ addState(mState7, mState6)
+ addState(mState4, mState3)
+ verifyStart()
+
+ // mState1 -> current
+ // | \
+ // mState2 mState6
+ // | \ |
+ // mState3 mState5 mState7
+ // |
+ // mState4 -> dest
+ processMessage(MSG_1, mState4)
+ verifyMessageProcessedBy(MSG_1, mState1)
+ mInOrder.verify(mState2).enter()
+ mInOrder.verify(mState3).enter()
+ mInOrder.verify(mState4).enter()
+ verifyNoMoreInteractions()
+
+ // mState1
+ // / \
+ // mState2 mState6
+ // | \ \
+ // mState3 mState5 -> dest mState7
+ // |
+ // mState4 -> current
+ processMessage(MSG_1, mState5)
+ verifyMessageProcessedBy(MSG_1, mState4, mState3, mState2, mState1)
+ mInOrder.verify(mState4).exit()
+ mInOrder.verify(mState3).exit()
+ mInOrder.verify(mState5).enter()
+ verifyNoMoreInteractions()
+
+ // mState1
+ // / \
+ // mState2 mState6
+ // | \ \
+ // mState3 mState5 -> current mState7 -> dest
+ // |
+ // mState4
+ processMessage(MSG_2, mState7)
+ verifyMessageProcessedBy(MSG_2, mState5, mState2)
+ mInOrder.verify(mState5).exit()
+ mInOrder.verify(mState2).exit()
+ mInOrder.verify(mState6).enter()
+ mInOrder.verify(mState7).enter()
+ verifyNoMoreInteractions()
+ }
+}