From: Daniel Bristot de Oliveira <bristot@redhat.com>
To: linux-kernel@vger.kernel.org, Steven Rostedt <rostedt@goodmis.org>
Cc: Tommaso Cucinotta <tommaso.cucinotta@santannapisa.it>,
Kate Carcia <kcarcia@redhat.com>,
Daniel Bristot de Oliveira <bristot@redhat.com>,
Jonathan Corbet <corbet@lwn.net>, Ingo Molnar <mingo@redhat.com>,
Mauro Carvalho Chehab <mchehab@kernel.org>,
Thomas Gleixner <tglx@linutronix.de>,
Peter Zijlstra <peterz@infradead.org>,
Will Deacon <will@kernel.org>,
Catalin Marinas <catalin.marinas@arm.com>,
"Paul E. McKenney" <paulmck@kernel.org>,
Joel Fernandes <joel@joelfernandes.org>,
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
Gabriele Paoloni <gabriele.paoloni@intel.com>,
Juri Lelli <juri.lelli@redhat.com>,
Clark Williams <williams@redhat.com>,
linux-doc@vger.kernel.org
Subject: [RFC PATCH 03/16] rv/include: Add helper functions for deterministic automata
Date: Wed, 19 May 2021 13:36:24 +0200 [thread overview]
Message-ID: <e30553f3d1f8840737c7179f228c95549b936300.1621414942.git.bristot@redhat.com> (raw)
In-Reply-To: <cover.1621414942.git.bristot@redhat.com>
Formally, a deterministic automaton, denoted by G, is defined as a
quintuple:
G = { X, E, f, x_0, X_m }
where:
- X is the set of states;
- E is the finite set of events;
- x_0 is the initial state;
- X_m (subset of X) is the set of marked states.
- f : X x E -> X $ is the transition function. It defines the
state transition in the occurrence of a event from E in
the state X. In the special case of deterministic automata,
the occurence of the event in E in a state in X has a
deterministic next state from X.
An automaton can also be represented using a graphical format of
vertices (nodes) and edges. The open-source tool Graphviz can produce
this graphic format using the (textual) DOT language as the source code.
The dot2c tool presented in this paper:
DE OLIVEIRA, Daniel Bristot; CUCINOTTA, Tommaso; DE OLIVEIRA, Romulo
Silva. Efficient formal verification for the Linux kernel. In:
International Conference on Software Engineering and Formal Methods.
Springer, Cham, 2019. p. 315-332.
Translates a deterministic automaton in the DOT format into a C
source code representation that to be used for monitoring.
This header file implements helper functions to facilitate the usage
of the C output from dot2c for monitoring.
Cc: Jonathan Corbet <corbet@lwn.net>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Mauro Carvalho Chehab <mchehab@kernel.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Will Deacon <will@kernel.org>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joel@joelfernandes.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Gabriele Paoloni <gabriele.paoloni@intel.com>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Clark Williams <williams@redhat.com>
Cc: linux-doc@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com>
---
include/rv/automata.h | 52 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 52 insertions(+)
create mode 100644 include/rv/automata.h
diff --git a/include/rv/automata.h b/include/rv/automata.h
new file mode 100644
index 000000000000..b95941bf78ac
--- /dev/null
+++ b/include/rv/automata.h
@@ -0,0 +1,52 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Deterministic automata helper functions, to be used with the automata
+ * models in C generated by the dot2k tool.
+ *
+ * The dot2k tool is available at https://gitlab.com/linux-rv-tools/dot2/.
+ *
+ * Copyright (C) 2019-2021 Daniel Bristot de Oliveira <bristot@redhat.com>
+ */
+
+#define DECLARE_AUTOMATA_HELPERS(name, type) \
+ \
+static inline void *model_get_model_##name(void) \
+{ \
+ return (void *) &automaton_##name; \
+} \
+ \
+char *model_get_state_name_##name(enum states_##name state) \
+{ \
+ return automaton_##name.state_names[state]; \
+} \
+ \
+char *model_get_event_name_##name(enum events_##name event) \
+{ \
+ return automaton_##name.event_names[event]; \
+} \
+ \
+static inline type model_get_init_state_##name(void) \
+{ \
+ return automaton_##name.initial_state; \
+} \
+ \
+static inline type \
+model_get_next_state_##name(enum states_##name curr_state, \
+ enum events_##name event) \
+{ \
+ if ((curr_state < 0) || (curr_state > state_max)) \
+ return -1; \
+ \
+ if ((event < 0) || (event > event_max)) \
+ return -1; \
+ \
+ return automaton_##name.function[curr_state][event]; \
+} \
+ \
+static inline bool model_is_final_state_##name(enum states_##name state) \
+{ \
+ if ((state < 0) || (state > state_max)) \
+ return 0; \
+ \
+ return !!automaton_##name.final_states[state]; \
+}
--
2.26.2
next prev parent reply other threads:[~2021-05-19 11:37 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-05-19 11:36 [RFC PATCH 00/16] The Runtime Verification (RV) interface Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 01/16] rv: Add " Daniel Bristot de Oliveira
2021-05-19 18:10 ` Randy Dunlap
2021-05-20 6:54 ` Daniel Bristot de Oliveira
2021-08-04 1:31 ` Steven Rostedt
2021-05-19 11:36 ` [RFC PATCH 02/16] rv: Add runtime reactors interface Daniel Bristot de Oliveira
2021-05-19 11:36 ` Daniel Bristot de Oliveira [this message]
2021-05-19 11:36 ` [RFC PATCH 04/16] rv/include: Add deterministic automata monitor definition via C macros Daniel Bristot de Oliveira
2021-05-19 18:27 ` Peter Zijlstra
2021-05-20 7:13 ` Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 05/16] rv/include: Add tracing helper functions Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 06/16] tools/rv: Add dot2c Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 07/16] tools/rv: Add dot2k Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 08/16] rv/monitors: Add the wip monitor skeleton created by dot2k Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 09/16] rv/monitors: wip instrumentation and Makefile/Kconfig entries Daniel Bristot de Oliveira
2021-05-19 18:14 ` Randy Dunlap
2021-05-20 6:57 ` Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 10/16] rv/monitors: Add the wwnr monitor skeleton created by dot2k Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 11/16] rv/monitors: wwnr instrumentation and Makefile/Kconfig entries Daniel Bristot de Oliveira
2021-05-19 18:16 ` Randy Dunlap
2021-05-20 6:59 ` Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 12/16] rv/reactors: Add the printk reactor Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 13/16] rv/reactors: Add the panic reactor Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 14/16] rv/docs: Add a basic documentation Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 15/16] rv/docs: Add deterministic automata monitor synthesis documentation Daniel Bristot de Oliveira
2021-05-19 11:36 ` [RFC PATCH 16/16] rv/docs: Add deterministic automata instrumentation documentation Daniel Bristot de Oliveira
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=e30553f3d1f8840737c7179f228c95549b936300.1621414942.git.bristot@redhat.com \
--to=bristot@redhat.com \
--cc=catalin.marinas@arm.com \
--cc=corbet@lwn.net \
--cc=gabriele.paoloni@intel.com \
--cc=joel@joelfernandes.org \
--cc=juri.lelli@redhat.com \
--cc=kcarcia@redhat.com \
--cc=linux-doc@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mathieu.desnoyers@efficios.com \
--cc=mchehab@kernel.org \
--cc=mingo@redhat.com \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=rostedt@goodmis.org \
--cc=tglx@linutronix.de \
--cc=tommaso.cucinotta@santannapisa.it \
--cc=will@kernel.org \
--cc=williams@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).