libosmocore[master]: Add Finite State Machine abstraction code

diff --git a/include/Makefile.am b/include/Makefile.am
index 2e58d7e..b775c9f 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -17,6 +17,7 @@ 
                        osmocom/core/crcgen.h \
                        osmocom/core/endian.h \
                        osmocom/core/defs.h \
+                       osmocom/core/fsm.h \
                        osmocom/core/gsmtap.h \
                        osmocom/core/gsmtap_util.h \
                        osmocom/core/linuxlist.h \
diff --git a/include/osmocom/core/fsm.h b/include/osmocom/core/fsm.h
new file mode 100644
index 0000000..0e6a372
--- /dev/null
+++ b/include/osmocom/core/fsm.h
@@ -0,0 +1,87 @@ 
+#pragma once
+
+#include <stdint.h>
+
+#include <osmocom/core/linuxlist.h>
+#include <osmocom/core/timer.h>
+#include <osmocom/core/utils.h>
+
+/*! \defgroup fsm Finite State Machine abstraction
+ *  @{
+ */
+
+/*! \file fsm.h
+ *  \brief Finite State Machine
+ */
+
+struct osmo_fsm_inst;
+
+/*! \brief description of a rule in the FSM */
+struct osmo_fsm_state {
+	/*! \brief bit-mask of permitted input events for this state */
+	uint32_t in_event_mask;
+	/*! \brief bit-mask to which other states this state may transiton */
+	uint32_t out_state_mask;
+	/*! \brief human-readable name of this state */
+	const char *name;
+	/*! \brief function pointer to be called for this state */
+	void (*action)(struct osmo_fsm_inst *fi, uint32_t event, void *data);
+};
+
+/*! \brief a description of an osmocom finite state machine */
+struct osmo_fsm {
+	/*! \brief global list */
+	struct llist_head list;
+	/*! \brief list of instances of this FSM */
+	struct llist_head instances;
+	/*! \brief human readable name */
+	const char *name;
+	/*! \brief table of state transition rules */
+	struct osmo_fsm_state *states;
+	/*! \brief bit-mask of events permitted in all states */
+	uint32_t allstate_event_mask;
+	/*! \brief function pointer to be called for allstate events */
+	void (*allstate_action)(struct osmo_fsm_inst *fi, uint32_t event, void *data);
+	/*! \brief number of entries in \ref states */
+	unsigned int num_states;
+	/*! \brief logging sub-system for this FSM */
+	int log_subsys;
+	/*! \brief human-readable names of events */
+	const struct value_string *event_names;
+};
+
+/*! \brief a single instanceof an osmocom finite state machine */
+struct osmo_fsm_inst {
+	/*! \brief member in the fsm->instances list */
+	struct llist_head list;
+	/*! \brief back-pointer to the FSM of which we are an instance */
+	struct osmo_fsm *fsm;
+	/*! \brief human readable name */
+	const char *name;
+	/*! \brief some private data of this instance */
+	void *priv;
+	/*! \brief logging level for this FSM */
+	int log_level;
+	/*! \brief current state of the FSM */
+	uint32_t state;
+
+	/*! \brief timer call-back for states with time-out */
+	void (*timer_cb)(struct osmo_fsm_inst *fi);
+	/*! \brief timer number for states with time-out */
+	int T;
+	/*! \brief timer back-end for states with time-out */
+	struct osmo_timer_list timer;
+};
+
+struct osmo_fsm_inst *osmo_fsm_inst_alloc(struct osmo_fsm *fsm, void *ctx, void *priv,
+					  int log_level);
+void osmo_fsm_inst_free(struct osmo_fsm_inst *fi);
+const char *osmo_fsm_event_name(struct osmo_fsm *fsm, uint32_t event);
+const char *osmo_fsm_inst_name(struct osmo_fsm_inst *fi);
+const char *osmo_fsm_state_name(struct osmo_fsm *fsm, uint32_t state);
+int osmo_fsm_inst_state_chg(struct osmo_fsm_inst *fi, uint32_t new_state,
+			    unsigned long timeout_secs, int T);
+int osmo_fsm_dispatch(struct osmo_fsm_inst *fi, uint32_t event, void *data);
+int osmo_fsm_register(struct osmo_fsm *fsm);
+
+/*! @} */
diff --git a/src/Makefile.am b/src/Makefile.am
index 45a77e3..7a6f464 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -9,7 +9,7 @@ 
 
 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 0000000..6b58fe3
--- /dev/null
+++ b/src/fsm.c
@@ -0,0 +1,283 @@ 
+/* 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 <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.
+ *
+ *  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 FMS 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.
+ */
+
+static LLIST_HEAD(g_fsms);
+
+/*! \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;
+
+	LOGP(fsm->log_subsys, fi->log_level, "%s(%s): Timeout of T%u\n",
+	     osmo_fsm_inst_name(fi),
+	     osmo_fsm_state_name(fsm, fi->state), fi->T);
+
+	fi->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)
+{
+	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;
+	llist_add(&fi->list, &fsm->instances);
+	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->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;
+	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;
+	}
+
+	LOGP(fsm->log_subsys, fi->log_level, "%s(%s): state_chg to %s\n",
+		osmo_fsm_inst_name(fi),
+		osmo_fsm_state_name(fsm, fi->state),
+		osmo_fsm_state_name(fsm, new_state));
+
+	fi->state = new_state;
+
+	if (timeout_secs) {
+		if (!fi->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_dispatch(struct osmo_fsm_inst *fi, uint32_t event, void *data)
+{
+	struct osmo_fsm *fsm = fi->fsm;
+	struct osmo_fsm_state *fs;
+
+	OSMO_ASSERT(fi->state < fsm->num_states);
+
+	fs = &fi->fsm->states[fi->state];
+
+
+	LOGP(fsm->log_subsys, fi->log_level, "%s(%s): Received Event %s\n",
+		osmo_fsm_inst_name(fi), osmo_fsm_state_name(fsm, fi->state),
+		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;
+}
+
+/*! @} */
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 55aaa07..263af0a 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -13,7 +13,7 @@ 
 		 vty/vty_test comp128/comp128_test utils/utils_test	\
 		 smscb/gsm0341_test stats/stats_test			\
 		 bitvec/bitvec_test msgb/msgb_test bits/bitcomp_test	\
-		 sim/sim_test tlv/tlv_test gsup/gsup_test
+		 sim/sim_test tlv/tlv_test gsup/gsup_test fsm/fsm_test
 
 if ENABLE_MSGFILE
 check_PROGRAMS += msgfile/msgfile_test
@@ -118,6 +118,9 @@ 
 gsup_gsup_test_SOURCES = gsup/gsup_test.c
 gsup_gsup_test_LDADD = $(top_builddir)/src/gsm/libosmogsm.la $(top_builddir)/src/libosmocore.la
 
+fsm_fsm_test_SOURCES = fsm/fsm_test.c
+fsm_fsm_test_LDADD = $(top_builddir)/src/libosmocore.la
+
 # The `:;' works around a Bash 3.2 bug when the output is not writeable.
 $(srcdir)/package.m4: $(top_srcdir)/configure.ac
 	:;{ \
@@ -152,7 +155,8 @@ 
 	     vty/vty_test.ok comp128/comp128_test.ok			\
 	     utils/utils_test.ok stats/stats_test.ok			\
 	     bitvec/bitvec_test.ok msgb/msgb_test.ok bits/bitcomp_test.ok \
-	     sim/sim_test.ok tlv/tlv_test.ok gsup/gsup_test.ok
+	     sim/sim_test.ok tlv/tlv_test.ok gsup/gsup_test.ok		\
+	     fsm/fsm_test.ok
 
 DISTCLEANFILES = atconfig
 
diff --git a/tests/fsm/fsm_test.c b/tests/fsm/fsm_test.c
new file mode 100644
index 0000000..d8db908
--- /dev/null
+++ b/tests/fsm/fsm_test.c
@@ -0,0 +1,152 @@ 
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <unistd.h>
+#include <string.h>
+
+#include <osmocom/core/utils.h>
+#include <osmocom/core/select.h>
+#include <osmocom/core/logging.h>
+#include <osmocom/core/fsm.h>
+
+enum {
+	DMAIN,
+};
+
+static void *g_ctx;
+
+
+enum test_fsm_states {
+	ST_NULL = 0,
+	ST_ONE,
+	ST_TWO,
+};
+
+enum test_fsm_evt {
+	EV_A,
+	EV_B,
+};
+
+static void test_fsm_null(struct osmo_fsm_inst *fi, uint32_t event, void *data)
+{
+	switch (event) {
+	case EV_A:
+		OSMO_ASSERT(data == (void *) 23);
+		osmo_fsm_inst_state_chg(fi, ST_ONE, 0, 0);
+		break;
+	default:
+		OSMO_ASSERT(0);
+		break;
+	}
+}
+
+static void test_fsm_one(struct osmo_fsm_inst *fi, uint32_t event, void *data)
+{
+	switch (event) {
+	case EV_B:
+		OSMO_ASSERT(data == (void *) 42);
+		osmo_fsm_inst_state_chg(fi,ST_TWO, 1, 2342);
+		break;
+	default:
+		OSMO_ASSERT(0);
+		break;
+	}
+}
+
+static void test_fsm_tmr_cb(struct osmo_fsm_inst *fi)
+{
+	OSMO_ASSERT(fi->T == 2342);
+	OSMO_ASSERT(fi->state == ST_TWO);
+	LOGP(DMAIN, LOGL_INFO, "Timer\n");
+
+	exit(0);
+}
+
+static struct osmo_fsm_state test_fsm_states[] = {
+	[ST_NULL] = {
+		.in_event_mask = (1 << EV_A),
+		.out_state_mask = (1 << ST_ONE),
+		.name = "NULL",
+		.action = test_fsm_null,
+	},
+	[ST_ONE]= {
+		.in_event_mask = (1 << EV_B),
+		.out_state_mask = (1 << ST_TWO),
+		.name = "ONE",
+		.action= test_fsm_one,
+	},
+	[ST_TWO]= {
+		.in_event_mask = 0,
+		.name = "TWO",
+		.action = NULL,
+	},
+};
+
+static struct osmo_fsm fsm = {
+	.name = "Test FSM",
+	.states = test_fsm_states,
+	.num_states = ARRAY_SIZE(test_fsm_states),
+	.log_subsys = DMAIN,
+};
+
+static int foo(void)
+{
+	struct osmo_fsm_inst *fi;
+
+	LOGP(DMAIN, LOGL_INFO, "Checking FSM allocation\n");
+	fi = osmo_fsm_inst_alloc(&fsm, g_ctx, NULL, LOGL_DEBUG);
+	OSMO_ASSERT(fi);
+	OSMO_ASSERT(fi->fsm == &fsm);
+	OSMO_ASSERT(!strcmp(osmo_fsm_inst_name(fi), fsm.name));
+	OSMO_ASSERT(fi->state == ST_NULL);
+	OSMO_ASSERT(fi->log_level == LOGL_DEBUG);
+
+	/* Try invalid state transition */
+	osmo_fsm_dispatch(fi, EV_B, (void *) 42);
+	OSMO_ASSERT(fi->state == ST_NULL);
+
+	/* Legitimate state transition */
+	osmo_fsm_dispatch(fi, EV_A, (void *) 23);
+	OSMO_ASSERT(fi->state == ST_ONE);
+
+	/* Legitimate transition with timer */
+	fi->timer_cb = test_fsm_tmr_cb;
+	osmo_fsm_dispatch(fi, EV_B, (void *) 42);
+	OSMO_ASSERT(fi->state == ST_TWO);
+
+
+	return 0;
+}
+
+static const struct log_info_cat default_categories[] = {
+	[DMAIN] = {
+		.name = "DMAIN",
+		.description = "Main",
+		.enabled = 1, .loglevel = LOGL_DEBUG,
+	},
+};
+
+static const struct log_info log_info = {
+	.cat = default_categories,
+	.num_cat = ARRAY_SIZE(default_categories),
+};
+
+int main(int argc, char **argv)
+{
+	struct log_target *stderr_target;
+
+	log_init(&log_info, NULL);
+	stderr_target = log_target_create_stderr();
+	log_add_target(stderr_target);
+
+	g_ctx = NULL;
+	osmo_fsm_register(&fsm);
+
+	foo();
+
+	while (1) {
+		osmo_select_main(0);
+	}
+
+	exit(0);
+}
diff --git a/tests/fsm/fsm_test.err b/tests/fsm/fsm_test.err
new file mode 100644
index 0000000..1d0bce2
--- /dev/null
+++ b/tests/fsm/fsm_test.err
@@ -0,0 +1,9 @@ 
+<0000> fsm/fsm_test.c:94 Checking FSM allocation
+<0000> fsm.c:111 Test FSM(NULL): Event 1 not permitted
+<0000> fsm.c:117 Test FSM(NULL): Received Event 0
+<0000> fsm.c:81 Test FSM(NULL): state_chg to ONE
+<0000> fsm.c:117 Test FSM(ONE): Received Event 1
+<0000> fsm.c:81 Test FSM(ONE): state_chg to TWO
+<0000> fsm.c:30 Test FSM(TWO): Timeout of T2342
+<0000> fsm/fsm_test.c:60 Timer
+
\ No newline at end of file
diff --git a/tests/fsm/fsm_test.ok b/tests/fsm/fsm_test.ok
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/tests/fsm/fsm_test.ok
diff --git a/tests/testsuite.at b/tests/testsuite.at
index d49f7ff..93373c1 100644
--- a/tests/testsuite.at
+++ b/tests/testsuite.at
@@ -201,3 +201,10 @@ 
 cat $abs_srcdir/gsup/gsup_test.ok > expout
 AT_CHECK([$abs_top_builddir/tests/gsup/gsup_test], [0], [expout], [ignore])
 AT_CLEANUP
+
+AT_SETUP([fsm])
+AT_KEYWORDS([fsm])
+cat $abs_srcdir/fsm/fsm_test.ok > expout
+cat $abs_srcdir/fsm/fsm_test.err > experr
+AT_CHECK([$abs_top_builddir/tests/fsm/fsm_test], [0], [expout], [experr])
+AT_CLEANUP