[PATCH] libosmocore[master]: Add Finite State Machine abstraction code

Hello Jenkins Builder, I'd like you to reexamine a change. Please visit https://gerrit.osmocom.org/163 to look at the new patch set (#2). Add Finite State Machine abstraction code This code is supposed to formalize some of the state machine handling in Osmocom code. Change-Id: I0b0965a912598c1f6b84042a99fea9d522642466 --- M include/Makefile.am A include/osmocom/core/fsm.h M src/Makefile.am A src/fsm.c M tests/Makefile.am A tests/fsm/fsm_test.c A tests/fsm/fsm_test.err A tests/fsm/fsm_test.ok M tests/testsuite.at 9 files changed, 546 insertions(+), 3 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/63/163/2 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 &lt;laforge(a)gnumonks.org&gt; + * + * 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 -- To view, visit https://gerrit.osmocom.org/163 To unsubscribe, visit https://gerrit.osmocom.org/settings Gerrit-MessageType: newpatchset Gerrit-Change-Id: I0b0965a912598c1f6b84042a99fea9d522642466 Gerrit-PatchSet: 2 Gerrit-Project: libosmocore Gerrit-Branch: master Gerrit-Owner: Harald Welte &lt;laforge(a)gnumonks.org&gt; Gerrit-Reviewer: Jenkins Builder