In Linux terms, the runtime verification monitors are encapsulated
inside the "RV monitor" abstraction. The "RV monitor" includes a set
of instances of the monitor (per-cpu monitor, per-task monitor, and
so on), the helper functions that glue the monitor to the system
reference model, and the trace output as a reaction for event parsing
and exceptions, as depicted below:
Linux +----- RV Monitor ----------------------------------+ Formal
Realm | | Realm
+-------------------+ +----------------+ +-----------------+
| Linux kernel | | Monitor | | Reference |
| Tracing | -> | Instance(s) | <- | Model |
| (instrumentation) | | (verification) | | (specification) |
+-------------------+ +----------------+ +-----------------+
| | |
| V |
| +----------+ |
| | Reaction | |
| +--+--+--+-+ |
| | | | |
| | | +-> trace output ? |
+------------------------|--|----------------------+
| +----> panic ?
+-------> <user-specified>
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 connecting
the Formal Reaml to Linux-like code.
This header file goes beyond, extending the code generation to the
verification stage, generating the code to the Monitor Instance(s)
level using C macros. The trace event code inspires this approach.
The benefits of the usage of macro for monitor synthesis is 3-fold:
- Reduces the code duplication;
- Facilitates the bug fix/improvement;
(but mainly:)
- Avoids the case of developers changing the core of the monitor
code to manipulate the model in a (let's say) non-standard
way.
This initial implementation presents two different types of monitor
instances:
- #define DECLARE_DA_MON_PER_CPU(name, type)
- #define DECLARE_DA_MON_PER_TASK(name, type)
The first declares the functions for deterministic automata monitor
with per-cpu instances, and the second with per-task instances.
In both cases, the name is a string that identifies the monitor,
and the type is the data type used by dot2c/k on the representation
of the model.
For example, the model "wip" below:
preempt_disable sched_waking
+############+ >------------------> +################+ >------------+
-># preemptive # # non-preemptive # |
+############+ <-----------------< +################+ <------------+
preempt_enable
with two states and three events can be stored in a 'char' type.
Considering that the preemption control is a per-cpu behavior, the
monitor declaration will be:
DECLARE_DA_MON_PER_CPU(wip, char);
The monitor is executed by sending events to be processed via the
functions presented below:
da_handle_event_$(MONITOR_NAME)($(event from event enum));
da_handle_init_event_$(MONITOR_NAME)($(event from event enum));
The function da_handle_event_$(MONITOR_NAME) is the regular case,
while the function da_handle_init_event_$(MONITOR_NAME)() is a
special case used to synchronize the system with the model.
When a monitor is enabled, it is placed in the initial state of the
automata. However, the monitor does not know if the system is in
the initial state. Hence, the monitor ignores events sent by
sent by da_handle_event_$(MONITOR_NAME) until the function
da_handle_init_event_$(MONITOR_NAME)() is called.
The function da_handle_init_event_$(MONITOR_NAME)() should be used for
the case in which the system generates the event is the one that returns
the automata to the initial state.
After receiving a da_handle_init_event_$(MONITOR_NAME)() event, the
monitor will know that it is in sync with the system and hence will
start processing the next events.
Using the wip model as example, the events "preempt_disable" and
"sched_waking" should be sent to to monitor, respectively, via:
da_handle_event_wip(preempt_disable);
da_handle_event_wip(sched_waking);
While the event "preempt_enabled" will use:
da_handle_init_event_wip(preempt_enable);
To notify the monitor that the system will be returning to the initial
state, so the system and the monitor should be in sync.
With the monitor synthesis in place, using these headers and dot2k,
the developer's work should be limited to the instrumentation of
the system, increasing the confidence in the overall approach.
Cc: Jonathan Corbet <corbet@xxxxxxx>
Cc: Steven Rostedt <rostedt@xxxxxxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Will Deacon <will@xxxxxxxxxx>
Cc: Catalin Marinas <catalin.marinas@xxxxxxx>
Cc: Marco Elver <elver@xxxxxxxxxx>
Cc: Dmitry Vyukov <dvyukov@xxxxxxxxxx>
Cc: "Paul E. McKenney" <paulmck@xxxxxxxxxx>
Cc: Shuah Khan <skhan@xxxxxxxxxxxxxxxxxxx>
Cc: Gabriele Paoloni <gpaoloni@xxxxxxxxxx>
Cc: Juri Lelli <juri.lelli@xxxxxxxxxx>
Cc: Clark Williams <williams@xxxxxxxxxx>
Cc: linux-doc@xxxxxxxxxxxxxxx
Cc: linux-kernel@xxxxxxxxxxxxxxx
Cc: linux-trace-devel@xxxxxxxxxxxxxxx
Signed-off-by: Daniel Bristot de Oliveira <bristot@xxxxxxxxxx>
---
include/rv/da_monitor.h | 398 ++++++++++++++++++++++++++++++++++++++++
1 file changed, 398 insertions(+)
create mode 100644 include/rv/da_monitor.h
diff --git a/include/rv/da_monitor.h b/include/rv/da_monitor.h
new file mode 100644
index 000000000000..6feea8a63afe
--- /dev/null
+++ b/include/rv/da_monitor.h
@@ -0,0 +1,398 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Deterministic automata (DA) monitor functions, to be used togheter
+ * with automata models in C generated by the dot2k tool.
+ *
+ * The dot2k tool is available at tools/tracing/rv/
+ *
+ * Copyright (C) 2019-2022 Daniel Bristot de Oliveira <bristot@xxxxxxxxxx>
+ */
+
+#include <rv/automata.h>
+#include <rv/trace_helpers.h>
+
+struct da_monitor {
+ char curr_state;
+ bool monitoring;
+ void *model;
+};
+
+#define MAX_PID 1024000
+
+/*
+ * Generic helpers for all types of deterministic automata monitors.
+ */
+#define DECLARE_DA_MON_GENERIC_HELPERS(name, type) \
+static char REACT_MSG[1024]; \
+ \
+static inline char \
+*format_react_msg(type curr_state, type event) \
+{ \
+ snprintf(REACT_MSG, 1024, \
+ "rv: monitor %s does not allow event %s on state %s\n", \
+ MODULE_NAME, \
+ model_get_event_name_##name(event), \
+ model_get_state_name_##name(curr_state)); \
+ return REACT_MSG; \
+} \
+ \
+static void cond_react(char *msg) \
+{ \
+ if (rv_##name.react) \
+ rv_##name.react(msg); \
+} \
+ \
+static inline void da_monitor_reset_##name(struct da_monitor *da_mon) \
+{ \
+ da_mon->monitoring = 0; \
+ da_mon->curr_state = model_get_init_state_##name(); \
+} \
+ \
+static inline type da_monitor_curr_state_##name(struct da_monitor *da_mon) \
+{ \
+ return da_mon->curr_state; \
+} \
+ \
+static inline void \
+da_monitor_set_state_##name(struct da_monitor *da_mon, enum states_##name state)\
+{ \
+ da_mon->curr_state = state; \
+} \
+static inline void da_monitor_start_##name(struct da_monitor *da_mon) \
+{ \
+ da_mon->monitoring = 1; \
+} \
+ \
+static inline bool da_monitoring_##name(struct da_monitor *da_mon) \
+{ \
+ return da_mon->monitoring; \
+}
+
+
+/*
+ * Event handler for implict monitors. Implicity monitor is the one which the
+ * handler does not need to specify which da_monitor to manilupulate. Examples
+ * of implicit monitor are the per_cpu or the global ones.
+ */
+#define DECLARE_DA_MON_MODEL_HANDLER_IMPLICIT(name, type) \
+static inline void \
+trace_event_##name(type state, type event, type next_state, bool safe); \
+static inline void trace_error_##name(type state, type event); \
+ \
+static inline bool \
+da_event_##name(struct da_monitor *da_mon, enum events_##name event) \
+{ \
+ type curr_state = da_monitor_curr_state_##name(da_mon); \
+ type next_state = model_get_next_state_##name(curr_state, event); \
+ \
+ if (next_state >= 0) { \
+ da_monitor_set_state_##name(da_mon, next_state); \
+ \
+ trace_event_##name(curr_state, event, next_state, \
+ model_is_final_state_##name(next_state)); \
+ \
+ return true; \
+ } \
+ \
+ if (reacting_on) \
+ cond_react(format_react_msg(curr_state, event)); \
+ \
+ trace_error_##name(curr_state, event); \
+ \
+ return false; \
+} \
+
+/*
+ * Event handler for per_task monitors.
+ */
+#define DECLARE_DA_MON_MODEL_HANDLER_PER_TASK(name, type) \
+ \
+static inline void \
+trace_event_##name(pid_t pid, type state, type event, \
+ type next_state, bool safe); \
+static inline void trace_error_##name(pid_t pid, type state, type event); \
+ \
+static inline type \
+da_event_##name(struct da_monitor *da_mon, pid_t pid, enum events_##name event) \
+{ \
+ type curr_state = da_monitor_curr_state_##name(da_mon); \
+ type next_state = model_get_next_state_##name(curr_state, event); \
+ \
+ if (next_state >= 0) { \
+ da_monitor_set_state_##name(da_mon, next_state); \
+ \
+ trace_event_##name(pid, curr_state, event, next_state, \
+ model_is_final_state_##name(next_state)); \
+ \
+ return true; \
+ } \
+ \
+ if (reacting_on && rv_##name.react) \
+ rv_##name.react(format_react_msg(curr_state, event)); \
+ \
+ trace_error_##name(pid, curr_state, event); \
+ \
+ return false; \
+}
+
+/*
+ * Functions to define, init and get a global monitor.
+ */
+#define DECLARE_DA_MON_INIT_GLOBAL(name, type) \
+ \
+static struct da_monitor da_mon_##name; \
+ \
+struct da_monitor *da_get_monitor_##name(void) \
+{ \
+ return &da_mon_##name; \
+} \
+ \
+void da_monitor_reset_all_##name(void) \
+{ \
+ da_monitor_reset_##name(da_mon_##name); \
+} \
+ \
+static inline void da_monitor_init_##name(void) \
+{ \
+ struct da_monitor *da_mon = &da_mon_##name \
+ da_mon->curr_state = model_get_init_state_##name(); \
+ da_mon->monitoring = 0; \
+ da_mon->model = model_get_model_##name(); \
+} \
+
+/*
+ * Functions to define, init and get a per-cpu monitor.
+ *
+ * XXX: Make it dynamic.
+ */
+#define DECLARE_DA_MON_INIT_PER_CPU(name, type) \
+ \
+DEFINE_PER_CPU(struct da_monitor, da_mon_##name); \
+ \
+struct da_monitor *da_get_monitor_##name(void) \
+{ \
+ return this_cpu_ptr(&da_mon_##name); \
+} \
+ \
+void da_monitor_reset_all_##name(void) \
+{ \
+ struct da_monitor *da_mon; \
+ int cpu; \
+ for_each_cpu(cpu, cpu_online_mask) { \
+ da_mon = per_cpu_ptr(&da_mon_##name, cpu); \
+ da_monitor_reset_##name(da_mon); \
+ } \
+} \
+ \
+static inline void da_monitor_init_##name(void) \
+{ \
+ struct da_monitor *da_mon; \
+ int cpu; \
+ for_each_cpu(cpu, cpu_online_mask) { \
+ da_mon = per_cpu_ptr(&da_mon_##name, cpu); \
+ da_mon->curr_state = model_get_init_state_##name(); \
+ da_mon->monitoring = 0; \
+ da_mon->model = model_get_model_##name(); \
+ } \
+} \
+
+
+/*
+ * Functions to define, init and get a per-task monitor.
+ *
+ * XXX: Make it dynamic using a list in task_struct (peterz)
+ */
+#define DECLARE_DA_MON_INIT_PER_TASK(name, type) \
+ \
+struct da_monitor da_mon_##name[MAX_PID]; \
+ \
+static inline struct da_monitor *da_get_monitor_##name(pid_t pid) \
+{ \
+ return &da_mon_##name[pid]; \
+} \
+ \
+void da_monitor_reset_all_##name(void) \
+{ \
+ struct da_monitor *mon = da_mon_##name; \
+ int i; \
+ for (i = 0; i < MAX_PID; i++) \
+ da_monitor_reset_##name(&mon[i]); \
+} \
+ \
+static void da_monitor_init_##name(void) \
+{ \
+ struct da_monitor *mon = da_mon_##name; \
+ int i; \
+ \
+ for (i = 0; i < MAX_PID; i++) { \
+ mon[i].curr_state = model_get_init_state_##name(); \
+ mon[i].monitoring = 0; \
+ mon[i].model = model_get_model_##name(); \
+ } \
+} \
+
+/*
+ * Handle event for implicit monitor: da_get_monitor_##name() will figure out
+ * the monitor.
+ */
+#define DECLARE_DA_MON_MONITOR_HANDLER_IMPLICIT(name, type) \
+ \
+static inline void __da_handle_event_##name(struct da_monitor *da_mon, \
+ enum events_##name event) \
+{ \
+ int retval; \
+ \
+ if (unlikely(!monitoring_on)) \
+ return; \
+ \
+ if (unlikely(!rv_##name.enabled)) \
+ return; \
+ \
+ if (unlikely(!da_monitoring_##name(da_mon))) \
+ return; \
+ \
+ retval = da_event_##name(da_mon, event); \
+ \
+ if (!retval) \
+ da_monitor_reset_##name(da_mon); \
+} \
+ \
+static inline void da_handle_event_##name(enum events_##name event) \
+{ \
+ struct da_monitor *da_mon = da_get_monitor_##name(); \
+ __da_handle_event_##name(da_mon, event); \
+} \
+ \
+static inline bool da_handle_init_event_##name(enum events_##name event) \
+{ \
+ struct da_monitor *da_mon; \
+ \
+ if (unlikely(!rv_##name.enabled)) \
+ return false; \
+ \
+ da_mon = da_get_monitor_##name(); \
+ \
+ if (unlikely(!da_monitoring_##name(da_mon))) { \
+ da_monitor_start_##name(da_mon); \
+ return false; \
+ } \
+ \
+ __da_handle_event_##name(da_mon, event); \
+ \
+ return true; \
+} \
+ \
+static inline bool da_handle_init_run_event_##name(enum events_##name event) \
+{ \
+ struct da_monitor *da_mon; \
+ \
+ if (unlikely(!rv_##name.enabled)) \
+ return false; \
+ \
+ da_mon = da_get_monitor_##name(); \
+ \
+ if (unlikely(!da_monitoring_##name(da_mon))) \
+ da_monitor_start_##name(da_mon); \
+ \
+ __da_handle_event_##name(da_mon, event); \
+ \
+ return true; \
+}
+
+/*
+ * Handle event for per task.
+ */
+#define DECLARE_DA_MON_MONITOR_HANDLER_PER_TASK(name, type) \
+ \
+static inline void \
+__da_handle_event_##name(struct da_monitor *da_mon, pid_t pid, \
+ enum events_##name event) \
+{ \
+ int retval; \
+ \
+ if (unlikely(!monitoring_on)) \
+ return; \
+ \
+ if (unlikely(!rv_##name.enabled)) \
+ return; \
+ \
+ if (unlikely(!da_monitoring_##name(da_mon))) \
+ return; \
+ \
+ retval = da_event_##name(da_mon, pid, event); \
+ \
+ if (!retval) \
+ da_monitor_reset_##name(da_mon); \
+} \
+ \
+static inline void \
+da_handle_event_##name(pid_t pid, enum events_##name event) \
+{ \
+ struct da_monitor *da_mon = da_get_monitor_##name(pid); \
+ __da_handle_event_##name(da_mon, pid, event); \
+} \
+ \
+static inline bool \
+da_handle_init_event_##name(pid_t pid, enum events_##name event) \
+{ \
+ struct da_monitor *da_mon; \
+ \
+ if (unlikely(!rv_##name.enabled)) \
+ return false; \
+ \
+ da_mon = da_get_monitor_##name(pid); \
+ \
+ if (unlikely(!da_monitoring_##name(da_mon))) { \
+ da_monitor_start_##name(da_mon); \
+ return false; \
+ } \
+ \
+ __da_handle_event_##name(da_mon, pid, event); \
+ \
+ return true; \
+}
+
+/*
+ * Entry point for the global monitor.
+ */
+#define DECLARE_DA_MON_GLOBAL(name, type) \
+ \
+DECLARE_AUTOMATA_HELPERS(name, type); \
+ \
+DECLARE_DA_MON_GENERIC_HELPERS(name, type); \
+ \
+DECLARE_DA_MON_MODEL_HANDLER_IMPLICIT(name, type); \
+ \
+DECLARE_DA_MON_INIT_PER_CPU(name, type); \
+ \
+DECLARE_DA_MON_MONITOR_HANDLER_IMPLICIT(name, type);
+
+/*
+ * Entry point for the per-cpu monitor.
+ */
+#define DECLARE_DA_MON_PER_CPU(name, type) \
+ \
+DECLARE_AUTOMATA_HELPERS(name, type); \
+ \
+DECLARE_DA_MON_GENERIC_HELPERS(name, type); \
+ \
+DECLARE_DA_MON_MODEL_HANDLER_IMPLICIT(name, type); \
+ \
+DECLARE_DA_MON_INIT_PER_CPU(name, type); \
+ \
+DECLARE_DA_MON_MONITOR_HANDLER_IMPLICIT(name, type);
+
+/*
+ * Entry point for the per-task monitor.
+ */
+#define DECLARE_DA_MON_PER_TASK(name, type) \
+ \
+DECLARE_AUTOMATA_HELPERS(name, type); \
+ \
+DECLARE_DA_MON_GENERIC_HELPERS(name, type); \
+ \
+DECLARE_DA_MON_MODEL_HANDLER_PER_TASK(name, type); \
+ \
+DECLARE_DA_MON_INIT_PER_TASK(name, type); \
+ \
+DECLARE_DA_MON_MONITOR_HANDLER_PER_TASK(name, type);
--
2.33.1
