Add Finite State Machine abstraction code

This code is supposed to formalize some of the state machine handling in
Osmocom code.

Change-Id: I0b0965a912598c1f6b84042a99fea9d522642466
Reviewed-on: https://gerrit.osmocom.org/163
Tested-by: Jenkins Builder
Reviewed-by: Harald Welte <laforge@gnumonks.org>

2 files changed, 423 insertions, 1 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 45a77e32..7a6f464d 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -9,7 +9,7 @@ lib_LTLIBRARIES = libosmocore.la
 
 libosmocore_la_LIBADD = $(BACKTRACE_LIB) $(TALLOC_LIBS)
 libosmocore_la_SOURCES = timer.c select.c signal.c msgb.c bits.c \
-			 bitvec.c bitcomp.c statistics.c \
+			 bitvec.c bitcomp.c statistics.c fsm.c \
 			 write_queue.c utils.c socket.c \
 			 logging.c logging_syslog.c rate_ctr.c \
 			 gsmtap_util.c crc16.c panic.c backtrace.c \
diff --git a/src/fsm.c b/src/fsm.c
new file mode 100644
index 00000000..ede769d8
--- /dev/null
+++ b/src/fsm.c
@@ -0,0 +1,422 @@
+/* Osmocom generic Finite State Machine implementation
+ *
+ * (C) 2016 by Harald Welte <laforge@gnumonks.org>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ *  MA  02110-1301, USA.
+ */
+
+#include <errno.h>
+#include <stdbool.h>
+
+#include <osmocom/core/fsm.h>
+#include <osmocom/core/talloc.h>
+#include <osmocom/core/logging.h>
+#include <osmocom/core/utils.h>
+
+/*! \addtogroup fsm
+ *  @{
+ */
+
+/*! \file fsm.c
+ *  \brief Finite State Machine abstraction
+ *
+ *  This is a generic C-language abstraction for implementing finite
+ *  state machines within the Osmocom framework.  It is intended to
+ *  replace existing hand-coded or even only implicitly existing FSMs
+ *  all over the existing code base.
+ *
+ *  An libosmocore FSM is described by its \ref osmo_fsm description,
+ *  which in turn refers to an array of \ref osmo_fsm_state descriptor,
+ *  each describing a single state in the FSM.
+ *
+ *  The general idea is that all actions performed within one state are
+ *  located at one position in the code (the state's action function),
+ *  as opposed to the 'message-centric' view of e.g. the existing
+ *  state machines of the LAPD(m) coe, where there is one message for
+ *  eahc possible event (primitive), and the function then needs to
+ *  concern itself on how to handle that event over all possible states.
+ *
+ *  For each state, there is a bit-mask of permitted input events for
+ *  this state, as well as a bit-mask of permitted new output states to
+ *  which the state can change.  Furthermore, there is a function
+ *  pointer implementing the actual handling of the input events
+ *  occurring whilst in thta state.
+ *
+ *  Furthermore, each state offers a function pointer that can be
+ *  executed just before leaving a state, and another one just after
+ *  entering a state.
+ *
+ *  When transitioning into a new state, an optional timer number and
+ *  time-out can be passed along.  The timer is started just after
+ *  entering the new state, and will call the \ref osmo_fsm timer_cb
+ *  function once it expires.  This is intended to be used in telecom
+ *  state machines where a given timer (identified by a certain number)
+ *  is started to terminate the fsm or terminate the fsm once expected
+ *  events are not happening before timeout expiration.
+ *
+ *  As there can often be many concurrent FSMs of one given class, we
+ *  introduce the concept of \ref osmo_fsm_inst, i.e. an FSM instance.
+ *  The instance keeps the actual state, while the \ref osmo_fsm
+ *  descriptor contains the static/const descriptor of the FSM's states
+ *  and possible transitions.
+ *
+ *  osmo_fsm are integrated with the libosmocore logging system.  The
+ *  logging sub-system is determined by the FSM descriptor, as we assume
+ *  one FSM (let's say one related to a location update procedure) is
+ *  inevitably always tied to a sub-system.  The logging level however
+ *  is configurable for each FSM instance, to ensure that e.g. DEBUG
+ *  logging can be used for the LU procedure of one subscriber, while
+ *  NOTICE level is used for all other subscribers.
+ *
+ *  In order to attach private state to the \ref osmo_fsm_inst, it
+ *  offers an opaque priv pointer.
+ *
+ */
+
+static LLIST_HEAD(g_fsms);
+static bool fsm_log_addr = true;
+
+/*! \brief specify if FSM instance addresses should be logged or not
+ *
+ *  By default, the FSM name includes the pointer address of the \ref
+ *  osmo_fsm_inst.  This behaviro can be disabled (and re-enabled)
+ *  using this function.
+ *
+ *  \param[in] log_addr Indicate if FSM instance address shall be logged
+ */
+void osmo_fsm_log_addr(bool log_addr)
+{
+	fsm_log_addr = false;
+}
+
+/*! \brief register a FSM with the core
+ *
+ *  A FSM descriptor needs to be registered with the core before any
+ *  instances can be created for it.
+ *
+ *  \param[in] fsm Descriptor of Finite State Machine to be registered
+ *  \returns 0 on success; negative on error
+ */
+int osmo_fsm_register(struct osmo_fsm *fsm)
+{
+	/* FIXME:check for duplicate name? */
+	llist_add_tail(&fsm->list, &g_fsms);
+	INIT_LLIST_HEAD(&fsm->instances);
+
+	return 0;
+}
+
+/*! \brief unregister a FSM from the core
+ *
+ *  Once the FSM descriptor is unregistered, active instances can still
+ *  use it, but no new instances may be created for it.
+ *
+ *  \param[in] fsm Descriptor of Finite State Machine to be removed
+ */
+void osmo_fsm_unregister(struct osmo_fsm *fsm)
+{
+	llist_del(&fsm->list);
+}
+
+/* small wrapper function around timer expiration (for logging) */
+static void fsm_tmr_cb(void *data)
+{
+	struct osmo_fsm_inst *fi = data;
+	struct osmo_fsm *fsm = fi->fsm;
+
+	LOGPFSM(fi, "Timeout of T%u\n", fi->T);
+
+	fsm->timer_cb(fi);
+}
+
+/*! \brief allocate a new instance of a specified FSM
+ *  \param[in] fsm Descriptor of the FSM
+ *  \param[in] ctx talloc context from which to allocate memory
+ *  \param[in] priv private data reference store in fsm instance
+ *  \param[in] log_level The log level for events of this FSM
+ *  \returns newly-allocated, initialized and registered FSM instance
+ */
+struct osmo_fsm_inst *osmo_fsm_inst_alloc(struct osmo_fsm *fsm, void *ctx, void *priv,
+					  int log_level, const char *id)
+{
+	struct osmo_fsm_inst *fi = talloc_zero(ctx, struct osmo_fsm_inst);
+
+	fi->fsm = fsm;
+	fi->priv = priv;
+	fi->log_level = log_level;
+	fi->timer.data = fi;
+	fi->timer.cb = fsm_tmr_cb;
+	fi->id = id;
+
+	if (!fsm_log_addr) {
+		if (id)
+			fi->name = talloc_asprintf(fi, "%s(%s)", fsm->name, id);
+		else
+			fi->name = talloc_asprintf(fi, "%s", fsm->name);
+	} else {
+		if (id)
+			fi->name = talloc_asprintf(fi, "%s(%s)[%p]", fsm->name,
+						   id, fi);
+		else
+			fi->name = talloc_asprintf(fi, "%s[%p]", fsm->name, fi);
+	}
+
+	INIT_LLIST_HEAD(&fi->proc.children);
+	INIT_LLIST_HEAD(&fi->proc.child);
+	llist_add(&fi->list, &fsm->instances);
+
+	LOGPFSM(fi, "Allocated\n");
+
+	return fi;
+}
+
+/*! \brief allocate a new instance of a specified FSM as child of
+ *  other FSM instance
+ *
+ *  This is like \ref osmo_fsm_inst_alloc but using the parent FSM as
+ *  talloc context, and inheriting the log level of the parent.
+ *
+ *  \param[in] fsm Descriptor of the to-be-allocated FSM
+ *  \param[in] parent Parent FSM instance
+ *  \param[in] parent_term_event Event to be sent to parent when terminating
+ *  \returns newly-allocated, initialized and registered FSM instance
+ */
+struct osmo_fsm_inst *osmo_fsm_inst_alloc_child(struct osmo_fsm *fsm,
+						struct osmo_fsm_inst *parent,
+						uint32_t parent_term_event)
+{
+	struct osmo_fsm_inst *fi;
+
+	fi = osmo_fsm_inst_alloc(fsm, parent, NULL, parent->log_level,
+				 parent->id);
+	if (!fi) {
+		/* indicate immediate termination to caller */
+		osmo_fsm_inst_dispatch(parent, parent_term_event, NULL);
+		return NULL;
+	}
+
+	LOGPFSM(fi, "is child of %s\n", osmo_fsm_inst_name(parent));
+
+	fi->proc.parent = parent;
+	fi->proc.parent_term_event = parent_term_event;
+	llist_add(&fi->proc.child, &parent->proc.children);
+
+	return fi;
+}
+
+/*! \brief delete a given instance of a FSM
+ *  \param[in] fsm The FSM to be un-registered and deleted
+ */
+void osmo_fsm_inst_free(struct osmo_fsm_inst *fi)
+{
+	osmo_timer_del(&fi->timer);
+	llist_del(&fi->list);
+	talloc_free(fi);
+}
+
+/*! \brief get human-readable name of FSM event
+ *  \param[in] fsm FSM descriptor of event
+ *  \param[in] event Event integer value
+ *  \returns string rendering of the event
+ */
+const char *osmo_fsm_event_name(struct osmo_fsm *fsm, uint32_t event)
+{
+	static char buf[32];
+	if (!fsm->event_names) {
+		snprintf(buf, sizeof(buf), "%u", event);
+		return buf;
+	} else
+		return get_value_string(fsm->event_names, event);
+}
+
+/*! \brief get human-readable name of FSM instance
+ *  \param[in] fi FSM instance
+ *  \returns string rendering of the FSM identity
+ */
+const char *osmo_fsm_inst_name(struct osmo_fsm_inst *fi)
+{
+	if (!fi)
+		return "NULL";
+
+	if (fi->name)
+		return fi->name;
+	else
+		return fi->fsm->name;
+}
+
+/*! \brief get human-readable name of FSM instance
+ *  \param[in] fsm FSM descriptor
+ *  \param[in] state FSM state number
+ *  \returns string rendering of the FSM state
+ */
+const char *osmo_fsm_state_name(struct osmo_fsm *fsm, uint32_t state)
+{
+	static char buf[32];
+	if (state >= fsm->num_states) {
+		snprintf(buf, sizeof(buf), "unknown %u", state);
+		return buf;
+	} else
+		return fsm->states[state].name;
+}
+
+/*! \brief perform a state change of the given FSM instance
+ *
+ *  All changes to the FSM instance state must be made via this
+ *  function.  It verifies that the existing state actually permits a
+ *  transiiton to new_state.
+ *
+ *  timeout_secs and T are optional parameters, and only have any effect
+ *  if timeout_secs is not 0.  If the timeout function is used, then the
+ *  new_state is entered, and the FSM instances timer is set to expire
+ *  in timeout_secs functions.   At that time, the FSM's timer_cb
+ *  function will be called for handling of the timeout by the user.
+ *
+ *  \param[in] fi FSM instance whose state is to change
+ *  \param[in] new_state The new state into which we should change
+ *  \param[in] timeout_secs Timeout in seconds (if !=0)
+ *  \param[in] T Timer number (if \ref timeout_secs != 0)
+ *  \returns 0 on success; negative on error
+ */
+int osmo_fsm_inst_state_chg(struct osmo_fsm_inst *fi, uint32_t new_state,
+			    unsigned long timeout_secs, int T)
+{
+	struct osmo_fsm *fsm = fi->fsm;
+	uint32_t old_state = fi->state;
+	const struct osmo_fsm_state *st = &fsm->states[fi->state];
+
+	/* validate if new_state is a valid state */
+	if (!(st->out_state_mask & (1 << new_state))) {
+		LOGP(fsm->log_subsys, LOGL_ERROR, "%s(%s): transition to "
+		     "state %s not permitted!\n",
+		     osmo_fsm_inst_name(fi),
+		     osmo_fsm_state_name(fsm, fi->state),
+		     osmo_fsm_state_name(fsm, new_state));
+		return -EPERM;
+	}
+
+	if (st->onleave)
+		st->onleave(fi, new_state);
+
+	LOGPFSM(fi, "state_chg to %s\n", osmo_fsm_state_name(fsm, new_state));
+	fi->state = new_state;
+
+	if (st->onenter)
+		st->onenter(fi, old_state);
+
+	if (timeout_secs) {
+		if (!fsm->timer_cb)
+			LOGP(fsm->log_subsys, LOGL_ERROR, "cannot start "
+			     "timer for FSM without timer call-back\n");
+		else {
+			fi->T = T;
+			osmo_timer_schedule(&fi->timer, timeout_secs, 0);
+		}
+	}
+
+	return 0;
+}
+
+/*! \brief dispatch an event to an osmocom finite state machine instance
+ *
+ *  Any incoming events to \ref osmo_fsm instances must be dispatched to
+ *  them via this function.  It verifies, whether the event is permitted
+ *  based on the current state of the FSM.  If not, -1 is returned.
+ *
+ *  \param[in] fi FSM instance
+ *  \param[in] event Event to send to FSM instance
+ *  \param[in] data Data to pass along with the event
+ *  \returns 0 in case of success; negative on error
+ */
+int osmo_fsm_inst_dispatch(struct osmo_fsm_inst *fi, uint32_t event, void *data)
+{
+	struct osmo_fsm *fsm;
+	const struct osmo_fsm_state *fs;
+
+	if (!fi) {
+		LOGP(DLGLOBAL, LOGL_ERROR, "Trying to dispatch event %u to "
+		     "non-existing FSM Instance!\n", event);
+		osmo_log_backtrace(DLGLOBAL, LOGL_ERROR);
+		return -ENODEV;
+	}
+
+	fsm = fi->fsm;
+	OSMO_ASSERT(fi->state < fsm->num_states);
+	fs = &fi->fsm->states[fi->state];
+
+	LOGPFSM(fi, "Received Event %s\n", osmo_fsm_event_name(fsm, event));
+
+	if (((1 << event) & fsm->allstate_event_mask) && fsm->allstate_action) {
+		fsm->allstate_action(fi, event, data);
+		return 0;
+	}
+
+	if (!((1 << event) & fs->in_event_mask)) {
+		LOGP(fsm->log_subsys, LOGL_ERROR, "%s(%s): Event %s not "
+		     "permitted\n", osmo_fsm_inst_name(fi),
+		     osmo_fsm_state_name(fsm, fi->state),
+		     osmo_fsm_event_name(fsm, event));
+		return -1;
+	}
+	fs->action(fi, event, data);
+
+	return 0;
+}
+
+/*! \brief Terminate FSM instance with given cause
+ *
+ *  This safely terminates the given FSM instance by first iterating
+ *  over all children and sending them a termination event.  Next, it
+ *  calls the FSM descriptors cleanup function (if any), followed by
+ *  releasing any memory associated with the FSM instance.
+ *
+ *  Finally, the parent FSM instance (if any) is notified using the
+ *  parent termination event configured at time of FSM instance start.
+ *
+ *  \param[in] fi FSM instance to be terminated
+ *  \param[in] cause Cause / reason for termination
+ *  \param[in] data Opaqueevent data to be passed to parent
+ */
+void osmo_fsm_inst_term(struct osmo_fsm_inst *fi,
+			enum osmo_fsm_term_cause cause, void *data)
+{
+	struct osmo_fsm_inst *child, *child2;
+	struct osmo_fsm_inst *parent = fi->proc.parent;
+	uint32_t parent_term_event = fi->proc.parent_term_event;
+
+	LOGPFSM(fi, "Terminating (cause = %u)\n", cause);
+
+	/* iterate over all children */
+	llist_for_each_entry_safe(child, child2, &fi->proc.children, proc.child) {
+		/* terminate child */
+		osmo_fsm_inst_term(child, OSMO_FSM_TERM_PARENT, NULL);
+	}
+
+	/* delete ourselves from the parent */
+	llist_del(&fi->proc.child);
+
+	/* call destructor / clean-up function */
+	if (fi->fsm->cleanup)
+		fi->fsm->cleanup(fi, cause);
+
+	LOGPFSM(fi, "Release\n");
+	osmo_fsm_inst_free(fi);
+
+	/* indicate our termination to the parent */
+	if (parent && cause != OSMO_FSM_TERM_PARENT)
+		osmo_fsm_inst_dispatch(parent, parent_term_event, data);
+}
+
+/*! @} */