Linear temporal logic monitors for RT application
Subsystems (12)
v2 cover Linear temporal logic monitors for RT application
Real-time applications may have design flaws causing them to have unexpected latency. For example, the applications may raise page faults, or may be blocked trying to take a mutex without priority inheritance.
However, while attempting to implement DA monitors for these real-time rules, deterministic automaton is found to be inappropriate as the specification language. The automaton is complicated, hard to understand, and error-prone.
For these cases, linear temporal logic is found to be more suitable. The LTL is more concise and intuitive.
This series adds support for LTL RV monitor, and use it to implement two monitors for reporting problems with real-time tasks.
Patch 1-7 do some cleanups to RV.
Patch 8-12 prepare the RV code for the integration of LTL monitors.
Patch 13 adds support for LTL monitors.
Patch 14 adds the container monitor "rtapp". This encapsulates the sub-monitors for real-time.
Patch 15-18 prepares the pagefault tracepoints, so that patch 19 can add the monitor which watches real-time tasks doing page faults.
Patch 20 adds the "sleep" monitor: it detects potential undesirable latency with real-time threads.
Patch 21 adds documentation on the new monitors.
Patch 22 allows the number of per-task monitors to be configurable, so that the two new monitors can be enabled simultaneously.
v1->v2 https://lore.kernel.org/lkml/[email protected]/
- Integrate the LTL scripts into the existing dot2k tool, taking advantage of the existing monitor generation scripts.
- Switch the struct ltl_monitor to use bitmap instead of an array, to optimize memory usage.
- Correct the generated code to be non-deterministic state machine, instead of deterministic state machine
- Put common code for all LTL monitors into a single file (include/rv/ltl_monitor.h), reducing code duplication
- Change the LTL monitors to make user of container. Add a bug fix to container while at it.
- Make the number of per-task monitor configurable
Nam Cao (22):
rv: Fix out-of-bound memory access in rv_is_container_monitor()
rv: Add #undef TRACE_INCLUDE_FILE
rv: Let the reactors take care of buffers verification/dot2k: Make it possible to invoke dot2k without
installation
verification/dot2k: Make a separate dot2k_templates/Kconfig_container verification/dot2k: Remove __buff_to_string() verification/dot2k: Replace is_container() hack with subparsers
rv: rename CONFIG_DA_MON_EVENTS to CONFIG_RV_MON_EVENTS verification/dot2k: Prepare the frontend for LTL inclusion Documentation/rv: Prepare monitor synthesis document for LTL inclusion verification/rvgen: Prepare the templates for LTL inclusion verification/rvgen: Restructure the classes to prepare for LTL
inclusion
rv: Add support for LTL monitors
rv: Add rtapp container monitor
x86/tracing: Remove redundant trace_pagefault_key x86/tracing: Move page fault trace points to generic
arm64: mm: Add page fault trace points
riscv: mm: Add page fault trace points
rv: Add rtapp_pagefault monitor
rv: Add rtapp_sleep monitor
rv: Add documentation for rtapp monitor
rv: Allow to configure the number of per-task monitor
.../trace/rv/da_monitor_synthesis.rst | 147 -----
Documentation/trace/rv/index.rst | 3 +-
.../trace/rv/linear_temporal_logic.rst | 97 +++
Documentation/trace/rv/monitor_rtapp.rst | 105 ++++
Documentation/trace/rv/monitor_synthesis.rst | 256 ++++++++
arch/arm64/mm/fault.c | 8 +
arch/riscv/mm/fault.c | 8 +
arch/x86/include/asm/trace/common.h | 12 -
arch/x86/include/asm/trace/irq_vectors.h | 1 -
arch/x86/kernel/Makefile | 1 -
arch/x86/kernel/tracepoint.c | 21 -
arch/x86/mm/fault.c | 5 +-
include/linux/panic.h | 3 +
include/linux/printk.h | 5 +
include/linux/rv.h | 67 ++-
include/linux/sched.h | 8 +-
include/rv/da_monitor.h | 45 +-
include/rv/ltl_monitor.h | 184 ++++++
.../trace/events}/exceptions.h | 27 +-
kernel/fork.c | 5 +-
kernel/panic.c | 17 +-
kernel/printk/internal.h | 1 -
kernel/trace/rv/Kconfig | 27 +-
kernel/trace/rv/Makefile | 3 +
kernel/trace/rv/monitors/pagefault/Kconfig | 11 +
.../trace/rv/monitors/pagefault/pagefault.c | 83 +++
.../trace/rv/monitors/pagefault/pagefault.h | 57 ++
.../rv/monitors/pagefault/pagefault_trace.h | 14 +
kernel/trace/rv/monitors/rtapp/Kconfig | 6 +
kernel/trace/rv/monitors/rtapp/rtapp.c | 34 ++
kernel/trace/rv/monitors/rtapp/rtapp.h | 3 +
kernel/trace/rv/monitors/sleep/Kconfig | 13 +
kernel/trace/rv/monitors/sleep/sleep.c | 217 +++++++
kernel/trace/rv/monitors/sleep/sleep.h | 293 ++++++++++
kernel/trace/rv/monitors/sleep/sleep_trace.h | 14 +
kernel/trace/rv/reactor_panic.c | 8 +-
kernel/trace/rv/reactor_printk.c | 8 +-
kernel/trace/rv/rv.c | 17 +-
kernel/trace/rv/rv_reactors.c | 2 +-
kernel/trace/rv/rv_trace.h | 52 +-
tools/verification/dot2/Makefile | 26 -
tools/verification/dot2/dot2k | 53 --
tools/verification/models/rtapp/pagefault.ltl | 1 +
tools/verification/models/rtapp/sleep.ltl | 15 +
tools/verification/rvgen/.gitignore | 3 +
tools/verification/rvgen/Makefile | 30 +
tools/verification/rvgen/__main__.py | 67 +++
tools/verification/{dot2 => rvgen}/dot2c | 2 +-
.../{dot2 => rvgen/rvgen}/automata.py | 0
tools/verification/rvgen/rvgen/container.py | 22 +
.../{dot2 => rvgen/rvgen}/dot2c.py | 2 +-
tools/verification/rvgen/rvgen/dot2k.py | 129 ++++
.../dot2k.py => rvgen/rvgen/generator.py} | 233 ++------
tools/verification/rvgen/rvgen/ltl2ba.py | 552 ++++++++++++++++++
tools/verification/rvgen/rvgen/ltl2k.py | 242 ++++++++
.../templates}/Kconfig | 0
.../rvgen/templates/container/Kconfig | 5 +
.../templates/container/main.c} | 0
.../templates/container/main.h} | 0
.../templates/dot2k}/main.c | 0
.../templates/dot2k}/trace.h | 0
.../verification/rvgen/templates/ltl2k/main.c | 102 ++++
.../rvgen/templates/ltl2k/trace.h | 14 +
63 files changed, 2857 insertions(+), 529 deletions(-)
delete mode 100644 Documentation/trace/rv/da_monitor_synthesis.rst
create mode 100644 Documentation/trace/rv/linear_temporal_logic.rst
create mode 100644 Documentation/trace/rv/monitor_rtapp.rst
create mode 100644 Documentation/trace/rv/monitor_synthesis.rst
delete mode 100644 arch/x86/include/asm/trace/common.h
delete mode 100644 arch/x86/kernel/tracepoint.c
create mode 100644 include/rv/ltl_monitor.h
rename {arch/x86/include/asm/trace => include/trace/events}/exceptions.h (55%)
create mode 100644 kernel/trace/rv/monitors/pagefault/Kconfig
create mode 100644 kernel/trace/rv/monitors/pagefault/pagefault.c
create mode 100644 kernel/trace/rv/monitors/pagefault/pagefault.h
create mode 100644 kernel/trace/rv/monitors/pagefault/pagefault_trace.h
create mode 100644 kernel/trace/rv/monitors/rtapp/Kconfig
create mode 100644 kernel/trace/rv/monitors/rtapp/rtapp.c
create mode 100644 kernel/trace/rv/monitors/rtapp/rtapp.h
create mode 100644 kernel/trace/rv/monitors/sleep/Kconfig
create mode 100644 kernel/trace/rv/monitors/sleep/sleep.c
create mode 100644 kernel/trace/rv/monitors/sleep/sleep.h
create mode 100644 kernel/trace/rv/monitors/sleep/sleep_trace.h
delete mode 100644 tools/verification/dot2/Makefile
delete mode 100644 tools/verification/dot2/dot2k
create mode 100644 tools/verification/models/rtapp/pagefault.ltl
create mode 100644 tools/verification/models/rtapp/sleep.ltl
create mode 100644 tools/verification/rvgen/.gitignore
create mode 100644 tools/verification/rvgen/Makefile
create mode 100644 tools/verification/rvgen/__main__.py
rename tools/verification/{dot2 => rvgen}/dot2c (97%)
rename tools/verification/{dot2 => rvgen/rvgen}/automata.py (100%)
create mode 100644 tools/verification/rvgen/rvgen/container.py
rename tools/verification/{dot2 => rvgen/rvgen}/dot2c.py (99%)
create mode 100644 tools/verification/rvgen/rvgen/dot2k.py
rename tools/verification/{dot2/dot2k.py => rvgen/rvgen/generator.py} (56%)
create mode 100644 tools/verification/rvgen/rvgen/ltl2ba.py
create mode 100644 tools/verification/rvgen/rvgen/ltl2k.py
rename tools/verification/{dot2/dot2k_templates => rvgen/templates}/Kconfig (100%)
create mode 100644 tools/verification/rvgen/templates/container/Kconfig
rename tools/verification/{dot2/dot2k_templates/main_container.c => rvgen/templates/container/main.c} (100%)
rename tools/verification/{dot2/dot2k_templates/main_container.h => rvgen/templates/container/main.h} (100%)
rename tools/verification/{dot2/dot2k_templates => rvgen/templates/dot2k}/main.c (100%)
rename tools/verification/{dot2/dot2k_templates => rvgen/templates/dot2k}/trace.h (100%)
create mode 100644 tools/verification/rvgen/templates/ltl2k/main.c
create mode 100644 tools/verification/rvgen/templates/ltl2k/trace.hSignature · 1 line
2.39.5
PATCH v2 1/22 Fix out-of-bound memory access in rv_is_container_monitor()
When rv_is_container_monitor() is called on the last monitor in rv_monitors_list, KASAN yells:
BUG: KASAN: global-out-of-bounds in rv_is_container_monitor+0x101/0x110 Read of size 8 at addr ffffffff97c7c798 by task setup/221 The buggy address belongs to the variable: rv_monitors_list+0x18/0x40
This is due to list_next_entry() is called on the last entry in the list. It wraps around to the first list_head, and the first list_head is not embedded in struct rv_monitor_def.
Fix it by checking if the monitor is last in the list.
--- kernel/trace/rv/rv.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/trace/rv/rv.c +6 -1
@@ -225,7 +225,12 @@ bool rv_is_nested_monitor(struct rv_monitor_def *mdef)*/ bool rv_is_container_monitor (struct rv_monitor_def *mdef) { -struct rv_monitor_def *next =list_next_entry (mdef, list); +struct rv_monitor_def *next; + +if (list_is_last (&mdef->list, &rv_monitors_list)) +return false; + + next =list_next_entry (mdef, list);return next->parent == mdef->monitor || !mdef->monitor->enable; }
Signature · 1 line
2.39.5
PATCH v2 2/22 Add #undef TRACE_INCLUDE_FILE
In reply to Nam CaoWithout "#undef TRACE_INCLUDE_FILE", there could be a build error due to TRACE_INCLUDE_FILE being redefined. Therefore add it.
Also fix a typo while at it.
--- kernel/trace/rv/rv_trace.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/trace/rv/rv_trace.h +2 -1
@@ -129,8 +129,9 @@ DECLARE_EVENT_CLASS(error_da_monitor_id,#endif /* CONFIG_DA_MON_EVENTS_ID */ #endif /* _TRACE_RV_H */ -/* This part ust be outside protection */ +/* This part must be outside protection */ #undef TRACE_INCLUDE_PATH#define TRACE_INCLUDE_PATH . +#undef TRACE_INCLUDE_FILE#define TRACE_INCLUDE_FILE rv_trace#include <trace/define_trace.h>
Signature · 1 line
2.39.5
PATCH v2 3/22 Let the reactors take care of buffers
In reply to Nam CaoEach RV monitor has one static buffer to send to the reactors. If multiple errors are detected simultaneously, the one buffer could be overwritten.
Instead, leave it to the reactors to handle buffering.
---
Cc: Petr Mladek <[email protected]>
Cc: John Ogness <[email protected]>
Cc: Sergey Senozhatsky <[email protected]>
--- include/linux/panic.h | 3 +++ include/linux/printk.h | 5 ++++ include/linux/rv.h | 9 +++++-- include/rv/da_monitor.h | 45 +++++++------------------------- kernel/panic.c | 17 ++++++++---- kernel/printk/internal.h | 1 - kernel/trace/rv/reactor_panic.c | 8 ++++-- kernel/trace/rv/reactor_printk.c | 8 ++++-- kernel/trace/rv/rv_reactors.c | 2 +- 9 files changed, 50 insertions(+), 48 deletions(-)
include/linux/panic.h +3 -0
@@ -3,6 +3,7 @@#define _LINUX_PANIC_H#include <linux/compiler_attributes.h> +#include <linux/stdarg.h> #include <linux/types.h> struct pt_regs ;
@@ -10,6 +11,8 @@ struct pt_regs;extern long (*panic_blink)(int state); __printf(1, 2)void panic (const char *fmt, ...)__noreturn __cold ; +__printf(1, 0) +void vpanic (const char *fmt,va_list args)__noreturn __cold ;void nmi_panic (struct pt_regs *regs,const char *msg);void check_panic_on_warn (const char *origin);extern void oops_enter (void );
include/linux/printk.h +5 -0
@@ -154,6 +154,7 @@ int vprintk_emit(int facility, int level, asmlinkage __printf(1, 0) int vprintk(const char *fmt, va_list args); +__printf(1, 0) int vprintk_deferred(const char *fmt, va_list args); asmlinkage __printf(1, 2) __cold int _printk(const char *fmt, ...);
@@ -213,6 +214,10 @@ int vprintk(const char *s, va_list args) {return 0 ; } +__printf(1, 0) int vprintk_deferred(const char *fmt, va_list args) +{ +return 0 ; +} static inline __printf(1, 2) __cold int _printk(const char *s, ...) {
include/linux/rv.h +7 -2
@@ -38,7 +38,7 @@ union rv_task_monitor {struct rv_reactor {const char *name;const char *description; -void (*react)(char *msg); + __printf(1, 2) void (*react)(const char *msg, ...); };#endif
@@ -50,7 +50,7 @@ struct rv_monitor {void (*disable)(void );void (*reset)(void );#ifdef CONFIG_RV_REACTORS -void (*react)(char *msg); + __printf(1, 2) void (*react)(const char *msg, ...);#endif };
@@ -64,6 +64,11 @@ void rv_put_task_monitor_slot(int slot);bool rv_reacting_on (void );int rv_unregister_reactor (struct rv_reactor *reactor);int rv_register_reactor (struct rv_reactor *reactor); +#else +bool rv_reacting_on (void ) +{ +return false; +}#endif /* CONFIG_RV_REACTORS */ #endif /* CONFIG_RV */
include/rv/da_monitor.h +10 -35
71 lines not on this page · raw message
kernel/panic.c +12 -5
@@ -277,17 +277,16 @@ static void panic_other_cpus_shutdown(bool crash_kexec) }/** -* panic - halt the system +* vpanic - halt the system * @fmt: The text string to print * * Display a message, then perform cleanups. * * This function never returns. */ -void panic (const char *fmt, ...) +void vpanic (const char *fmt,va_list args) {static char buf[1024 ]; -va_list args;long i, i_next =0 , len;int state =0 ;int old_cpu, this_cpu;
@@ -338,9 +337,7 @@ void panic(const char *fmt, ...)console_verbose ();bust_spinlocks (1 ); -va_start (args, fmt); len =vscnprintf (buf,sizeof (buf), fmt, args); -va_end (args);if (len && buf[len -1 ] =='\n' ) buf[len -1 ] ='\0' ;
@@ -477,7 +474,17 @@ void panic(const char *fmt, ...)mdelay (PANIC_TIMER_STEP ); } } +EXPORT_SYMBOL (vpanic); +/* Identical to vpanic(), except it takes variadic arguments instead of va_list */ +void panic (const char *fmt, ...) +{ +va_list args; + +va_start (args, fmt); +vpanic (fmt, args); +va_end (args); +}EXPORT_SYMBOL (panic);#define TAINT_FLAG (taint, _c_true, _c_false, _module) \
kernel/printk/internal.h +0 -1
@@ -71,7 +71,6 @@ int vprintk_store(int facility, int level, const char *fmt, va_list args); __printf(1, 0) int vprintk_default(const char *fmt, va_list args); -__printf(1, 0) int vprintk_deferred(const char *fmt, va_list args);void __printk_safe_enter (void );void __printk_safe_exit (void );
kernel/trace/rv/reactor_panic.c +6 -2
@@ -13,9 +13,13 @@#include <linux/init.h> #include <linux/rv.h> -static void rv_panic_reaction (char *msg) +static void rv_panic_reaction (const char *msg, ...) { -panic (msg); +va_list args; + +va_start (args, msg); +vpanic (msg, args); +va_end (args); }static struct rv_reactor rv_panic = {
kernel/trace/rv/reactor_printk.c +6 -2
@@ -12,9 +12,13 @@#include <linux/init.h> #include <linux/rv.h> -static void rv_printk_reaction (char *msg) +static void rv_printk_reaction (const char *msg, ...) { -printk_deferred (msg); +va_list args; + +va_start (args, msg); +vprintk_deferred (msg, args); +va_end (args); }static struct rv_reactor rv_printk = {
kernel/trace/rv/rv_reactors.c +1 -1
@@ -490,7 +490,7 @@ void reactor_cleanup_monitor(struct rv_monitor_def *mdef)/* * Nop reactor register */ -static void rv_nop_reaction (char *msg) +static void rv_nop_reaction (const char *msg, ...) { }
Signature · 1 line
2.39.5
PATCH v2 4/22 verification/dot2k: Make it possible to invoke dot2k without installation
In reply to Nam CaoWithout installation, dot2k doesn't work:
namcao@yellow:~/linux/tools/verification$ python3 ./dot2/dot2k
Traceback (most recent call last):
File "/home/namcao/linux/tools/verification/./dot2/dot2k", line 12, in <module>
from dot2.dot2k import dot2k
ModuleNotFoundError: No module named 'dot2'Installing dot2k to the system is not always desirable. Sometimes it is not even possible (e.g. no root permission).
Restructure the files to make it work without installing.
---
tools/verification/dot2/Makefile | 6 +++---
tools/verification/dot2/{ => dot2}/automata.py | 0
tools/verification/dot2/{ => dot2}/dot2c.py | 0
tools/verification/dot2/{ => dot2}/dot2k.py | 0
4 files changed, 3 insertions(+), 3 deletions(-)
rename tools/verification/dot2/{ => dot2}/automata.py (100%)
rename tools/verification/dot2/{ => dot2}/dot2c.py (100%)
rename tools/verification/dot2/{ => dot2}/dot2k.py (100%)tools/verification/dot2/Makefile +3 -3
@@ -16,10 +16,10 @@ clean: .PHONY: install install: - $(INSTALL) automata.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/automata.py - $(INSTALL) dot2c.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/dot2c.py + $(INSTALL) dot2/automata.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/automata.py + $(INSTALL) dot2/dot2c.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/dot2c.py $(INSTALL) dot2c -D -m 755 $(DESTDIR)$(bindir)/ - $(INSTALL) dot2k.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/dot2k.py + $(INSTALL) dot2/dot2k.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/dot2k.py $(INSTALL) dot2k -D -m 755 $(DESTDIR)$(bindir)/ mkdir -p ${miscdir}/
tools/verification/dot2/dot2/automata.py renamed from tools/verification/dot2/automata.py +0 -0
tools/verification/dot2/dot2/dot2c.py renamed from tools/verification/dot2/dot2c.py +0 -0
tools/verification/dot2/dot2/dot2k.py renamed from tools/verification/dot2/dot2k.py +0 -0
Signature · 1 line
2.39.5
PATCH v2 5/22 verification/dot2k: Make a separate dot2k_templates/Kconfig_container
In reply to Nam CaoA generated container's Kconfig has an incorrect line:
select DA_MON_EVENTS_IMPLICIT
This is due to container generation uses the same template Kconfig file as deterministic automaton monitor.
Therefore, make a separate Kconfig template for container which has only the necessaries for container.
---
Alternatively, we could also modify the Python scripts. I tried both and this solution seems cleaner.
--- tools/verification/dot2/dot2/dot2k.py | 3 ++- tools/verification/dot2/dot2k_templates/Kconfig_container | 5 +++++ 2 files changed, 7 insertions(+), 1 deletion(-) create mode 100644 tools/verification/dot2/dot2k_templates/Kconfig_container
tools/verification/dot2/dot2/dot2k.py +2 -1
@@ -35,6 +35,7 @@ class dot2k(Dot2c): self.states = [] self.main_c = self.__read_file(self.monitor_templates_dir + "main_container.c") self.main_h = self.__read_file(self.monitor_templates_dir + "main_container.h") + self.kconfig = self.__read_file(self.monitor_templates_dir + "Kconfig_container") else: super().__init__(file_path, extra_params.get("model_name"))
@@ -44,7 +45,7 @@ class dot2k(Dot2c): self.monitor_type = MonitorType self.main_c = self.__read_file(self.monitor_templates_dir + "main.c") self.trace_h = self.__read_file(self.monitor_templates_dir + "trace.h") - self.kconfig = self.__read_file(self.monitor_templates_dir + "Kconfig") + self.kconfig = self.__read_file(self.monitor_templates_dir + "Kconfig") self.enum_suffix = "_%s" % self.name self.description = extra_params.get("description", self.name) or "auto-generated" self.auto_patch = extra_params.get("auto_patch")
tools/verification/dot2/dot2k_templates/Kconfig_container new file +5 -0
@@ -0,0 +1,5 @@ +config RV_MON_%%MODEL_NAME_UP%% + depends on RV + bool "%%MODEL_NAME%% monitor" + help + %%DESCRIPTION%%
Signature · 1 line
2.39.5
PATCH v2 6/22 verification/dot2k: Remove __buff_to_string()
In reply to Nam Caostr.join() can do what __buff_to_string() does. Therefore replace __buff_to_string() to make the scripts more pythonic.
--- tools/verification/dot2/dot2/dot2k.py | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-)
tools/verification/dot2/dot2/dot2k.py +6 -15
@@ -109,15 +109,6 @@ class dot2k(Dot2c): fd.close() return content - def __buff_to_string(self, buff): - string = "" - - for line in buff: - string = string + line + "\n" - - # cut off the last \n - return string[:-1] - def fill_monitor_type(self): return self.monitor_type.upper()
@@ -148,19 +139,19 @@ class dot2k(Dot2c): buff.append("\tda_%s_%s(%s%s);" % (handle, self.name, event, self.enum_suffix)); buff.append("}") buff.append("") - return self.__buff_to_string(buff) + return '\n'.join(buff) def fill_tracepoint_attach_probe(self): buff = [] for event in self.events: buff.append("\trv_attach_trace_probe(\"%s\", /* XXX: tracepoint */, handle_%s);" % (self.name, event)) - return self.__buff_to_string(buff) + return '\n'.join(buff) def fill_tracepoint_detach_helper(self): buff = [] for event in self.events: buff.append("\trv_detach_trace_probe(\"%s\", /* XXX: tracepoint */, handle_%s);" % (self.name, event)) - return self.__buff_to_string(buff) + return '\n'.join(buff) def fill_main_c(self): main_c = self.main_c
@@ -210,7 +201,7 @@ class dot2k(Dot2c): buff = self.fill_model_h_header() buff += self.format_model() - return self.__buff_to_string(buff) + return '\n'.join(buff) def fill_monitor_class_type(self): if self.monitor_type == "per_task":
@@ -242,7 +233,7 @@ class dot2k(Dot2c): tp_args_c = ", ".join([b for a,b in tp_args]) buff.append(" TP_PROTO(%s)," % tp_proto_c) buff.append(" TP_ARGS(%s)" % tp_args_c) - return self.__buff_to_string(buff) + return '\n'.join(buff) def fill_monitor_deps(self): buff = []
@@ -250,7 +241,7 @@ class dot2k(Dot2c): if self.parent: buff.append(" depends on RV_MON_%s" % self.parent.upper()) buff.append(" default y") - return self.__buff_to_string(buff) + return '\n'.join(buff) def fill_trace_h(self): trace_h = self.trace_h
Signature · 1 line
2.39.5
PATCH v2 7/22 verification/dot2k: Replace is_container() hack with subparsers
In reply to Nam Caodot2k is used for both generating deterministic automaton (DA) monitor and generating container monitor.
Generating DA monitor and generating container requires different parameters. This is implemented by peeking at sys.argv and check whether "--container" is specified, and use that information to make some parameters optional or required.
This works, but is quite hacky and ugly.
Replace this hack with Python's built-in subparsers.
The old commands:
python3 dot2/dot2k -d wip.dot -t per_cpu python3 dot2/dot2k -n sched --container
are equivalent to the new commands:
python3 dot2/dot2k monitor -d wip.dot -t per_cpu python3 dot2/dot2k container -n sched
--- tools/verification/dot2/dot2/dot2k.py | 2 +- tools/verification/dot2/dot2k | 37 +++++++++++++++------------ 2 files changed, 21 insertions(+), 18 deletions(-)
tools/verification/dot2/dot2/dot2k.py +1 -1
@@ -19,7 +19,7 @@ class dot2k(Dot2c): monitor_type = "per_cpu" def __init__(self, file_path, MonitorType, extra_params={}): - self.container = extra_params.get("container") + self.container = extra_params.get("subcmd") == "container" self.parent = extra_params.get("parent") self.__fill_rv_templates_dir()
tools/verification/dot2/dot2k +20 -17
@@ -13,30 +13,33 @@ if __name__ == '__main__': import argparse import sys - def is_container(): - """Should work even before parsing the arguments""" - return "-c" in sys.argv or "--container" in sys.argv - parser = argparse.ArgumentParser(description='transform .dot file into kernel rv monitor') - parser.add_argument('-d', "--dot", dest="dot_file", required=not is_container()) - parser.add_argument('-t', "--monitor_type", dest="monitor_type", required=not is_container(), - help=f"Available options: {', '.join(dot2k.monitor_types.keys())}") - parser.add_argument('-n', "--model_name", dest="model_name", required=is_container()) parser.add_argument("-D", "--description", dest="description", required=False) parser.add_argument("-a", "--auto_patch", dest="auto_patch", action="store_true", required=False, help="Patch the kernel in place") - parser.add_argument("-p", "--parent", dest="parent", - required=False, help="Create a monitor nested to parent") - parser.add_argument("-c", "--container", dest="container", - action="store_true", required=False, - help="Create an empty monitor to be used as a container") + + subparsers = parser.add_subparsers(dest="subcmd", required=True) + + monitor_parser = subparsers.add_parser("monitor") + monitor_parser.add_argument('-n', "--model_name", dest="model_name") + monitor_parser.add_argument("-p", "--parent", dest="parent", + required=False, help="Create a monitor nested to parent") + monitor_parser.add_argument('-d', "--dot", dest="dot_file") + monitor_parser.add_argument('-t', "--monitor_type", dest="monitor_type", + help=f"Available options: {', '.join(dot2k.monitor_types.keys())}") + + container_parser = subparsers.add_parser("container") + container_parser.add_argument('-n', "--model_name", dest="model_name", required=True) + params = parser.parse_args() - if not is_container(): - print("Opening and parsing the dot file %s" % params.dot_file) try: - monitor=dot2k(params.dot_file, params.monitor_type, vars(params)) + if params.subcmd == "monitor": + print("Opening and parsing the dot file %s" % params.dot_file) + monitor = dot2k(params.dot_file, params.monitor_type, vars(params)) + else: + monitor = dot2k(None, None, vars(params)) except Exception as e: print('Error: '+ str(e)) print("Sorry : :-(")
@@ -45,7 +48,7 @@ if __name__ == '__main__': print("Writing the monitor into the directory %s" % monitor.name) monitor.print_files() print("Almost done, checklist") - if not is_container(): + if params.subcmd == "monitor": print(" - Edit the %s/%s.c to add the instrumentation" % (monitor.name, monitor.name)) print(monitor.fill_tracepoint_tooltip()) print(monitor.fill_makefile_tooltip())
Signature · 1 line
2.39.5
PATCH v2 8/22 rename CONFIG_DA_MON_EVENTS to CONFIG_RV_MON_EVENTS
In reply to Nam CaoCONFIG_DA_MON_EVENTS is not specific to deterministic automaton. It could be used for other monitor types. Therefore rename it to CONFIG_RV_MON_EVENTS.
This prepares for the introduction of linear temporal logic monitor.
--- kernel/trace/rv/Kconfig | 6 +++--- kernel/trace/rv/rv.c | 2 +- 2 files changed, 4 insertions(+), 4 deletions(-)
kernel/trace/rv/Kconfig +3 -3
@@ -1,14 +1,14 @@ # SPDX-License-Identifier: GPL-2.0-only # -config DA_MON_EVENTS +config RV_MON_EVENTS bool config DA_MON_EVENTS_IMPLICIT - select DA_MON_EVENTS + select RV_MON_EVENTS bool config DA_MON_EVENTS_ID - select DA_MON_EVENTS + select RV_MON_EVENTS bool menuconfig RV
kernel/trace/rv/rv.c +1 -1
@@ -143,7 +143,7 @@#include <linux/init.h> #include <linux/slab.h> -#ifdef CONFIG_DA_MON_EVENTS +#ifdef CONFIG_RV_MON_EVENTS #define CREATE_TRACE_POINTS #include <rv_trace.h> #endif
Signature · 1 line
2.39.5
PATCH v2 9/22 verification/dot2k: Prepare the frontend for LTL inclusion
In reply to Nam CaoThe dot2k tool has some code that can be reused for linear temporal logic monitor. Prepare its frontend for LTL inclusion:
1. Rename to be generic: rvgen
2. Replace the parameter --dot with 2 parameters:
--class: to specific the monitor class, can be 'da' or 'ltl' --spec: the monitor specification file, .dot file for DA, and .ltl
file for LTL
The old command:
python3 dot2/dot2k monitor -d wip.dot -t per_cpu
is equivalent to the new commands:
python3 dot2/dot2k monitor -c da -s wip.dot -t per_cpu
---
tools/verification/{dot2 => rvgen}/Makefile | 10 +++++-----
.../{dot2/dot2k => rvgen/__main__.py} | 18 +++++++++++++-----
tools/verification/{dot2 => rvgen}/dot2c | 2 +-
.../{dot2 => rvgen}/dot2k_templates/Kconfig | 0
.../dot2k_templates/Kconfig_container | 0
.../{dot2 => rvgen}/dot2k_templates/main.c | 0
.../dot2k_templates/main_container.c | 0
.../dot2k_templates/main_container.h | 0
.../{dot2 => rvgen}/dot2k_templates/trace.h | 0
.../{dot2/dot2 => rvgen/rvgen}/automata.py | 0
.../{dot2/dot2 => rvgen/rvgen}/dot2c.py | 2 +-
.../{dot2/dot2 => rvgen/rvgen}/dot2k.py | 10 +++++-----
12 files changed, 25 insertions(+), 17 deletions(-)
rename tools/verification/{dot2 => rvgen}/Makefile (55%)
rename tools/verification/{dot2/dot2k => rvgen/__main__.py} (72%)
rename tools/verification/{dot2 => rvgen}/dot2c (97%)
rename tools/verification/{dot2 => rvgen}/dot2k_templates/Kconfig (100%)
rename tools/verification/{dot2 => rvgen}/dot2k_templates/Kconfig_container (100%)
rename tools/verification/{dot2 => rvgen}/dot2k_templates/main.c (100%)
rename tools/verification/{dot2 => rvgen}/dot2k_templates/main_container.c (100%)
rename tools/verification/{dot2 => rvgen}/dot2k_templates/main_container.h (100%)
rename tools/verification/{dot2 => rvgen}/dot2k_templates/trace.h (100%)
rename tools/verification/{dot2/dot2 => rvgen/rvgen}/automata.py (100%)
rename tools/verification/{dot2/dot2 => rvgen/rvgen}/dot2c.py (99%)
rename tools/verification/{dot2/dot2 => rvgen/rvgen}/dot2k.py (98%)tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +5 -5
@@ -3,7 +3,7 @@ INSTALL=install prefix ?= /usr bindir ?= $(prefix)/bin mandir ?= $(prefix)/share/man -miscdir ?= $(prefix)/share/dot2 +miscdir ?= $(prefix)/share/rvgen srcdir ?= $(prefix)/src PYLIB ?= $(shell python3 -c 'import sysconfig; print (sysconfig.get_path("purelib"))')
@@ -16,11 +16,11 @@ clean: .PHONY: install install: - $(INSTALL) dot2/automata.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/automata.py - $(INSTALL) dot2/dot2c.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/dot2c.py + $(INSTALL) rvgen/automata.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/automata.py + $(INSTALL) rvgen/dot2c.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/dot2c.py $(INSTALL) dot2c -D -m 755 $(DESTDIR)$(bindir)/ - $(INSTALL) dot2/dot2k.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/dot2k.py - $(INSTALL) dot2k -D -m 755 $(DESTDIR)$(bindir)/ + $(INSTALL) rvgen/dot2k.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/dot2k.py + $(INSTALL) __main__.py -D -m 755 $(DESTDIR)$(bindir)/rvgen mkdir -p ${miscdir}/ cp -rp dot2k_templates $(DESTDIR)$(miscdir)/
tools/verification/rvgen/__main__.py renamed from tools/verification/dot2/dot2k +13 -5
@@ -9,11 +9,11 @@ # Documentation/trace/rv/da_monitor_synthesis.rst if __name__ == '__main__': - from dot2.dot2k import dot2k + from rvgen.dot2k import dot2k import argparse import sys - parser = argparse.ArgumentParser(description='transform .dot file into kernel rv monitor') + parser = argparse.ArgumentParser(description='Generate kernel rv monitor') parser.add_argument("-D", "--description", dest="description", required=False) parser.add_argument("-a", "--auto_patch", dest="auto_patch", action="store_true", required=False,
@@ -25,7 +25,9 @@ if __name__ == '__main__': monitor_parser.add_argument('-n', "--model_name", dest="model_name") monitor_parser.add_argument("-p", "--parent", dest="parent", required=False, help="Create a monitor nested to parent") - monitor_parser.add_argument('-d', "--dot", dest="dot_file") + monitor_parser.add_argument('-c', "--class", dest="monitor_class", + help="Monitor class, either \"da\" or \"ltl\"") + monitor_parser.add_argument('-s', "--spec", dest="spec", help="Monitor specification file") monitor_parser.add_argument('-t', "--monitor_type", dest="monitor_type", help=f"Available options: {', '.join(dot2k.monitor_types.keys())}")
@@ -36,8 +38,14 @@ if __name__ == '__main__': try: if params.subcmd == "monitor": - print("Opening and parsing the dot file %s" % params.dot_file) - monitor = dot2k(params.dot_file, params.monitor_type, vars(params)) + print("Opening and parsing the specification file %s" % params.spec) + if params.monitor_class == "da": + monitor = dot2k(params.spec, params.monitor_type, vars(params)) + elif params.monitor_class == "ltl": + raise NotImplementedError + else: + print("Unknown monitor class:", params.monitor_class) + sys.exit(1) else: monitor = dot2k(None, None, vars(params)) except Exception as e:
tools/verification/rvgen/dot2c renamed from tools/verification/dot2/dot2c +1 -1
@@ -14,7 +14,7 @@ # Documentation/trace/rv/deterministic_automata.rst if __name__ == '__main__': - from dot2 import dot2c + from rvgen import dot2c import argparse import sys
tools/verification/rvgen/dot2k_templates/Kconfig renamed from tools/verification/dot2/dot2k_templates/Kconfig +0 -0
tools/verification/rvgen/dot2k_templates/Kconfig_container renamed from tools/verification/dot2/dot2k_templates/Kconfig_container +0 -0
tools/verification/rvgen/dot2k_templates/main.c renamed from tools/verification/dot2/dot2k_templates/main.c +0 -0
tools/verification/rvgen/dot2k_templates/main_container.c renamed from tools/verification/dot2/dot2k_templates/main_container.c +0 -0
tools/verification/rvgen/dot2k_templates/main_container.h renamed from tools/verification/dot2/dot2k_templates/main_container.h +0 -0
tools/verification/rvgen/dot2k_templates/trace.h renamed from tools/verification/dot2/dot2k_templates/trace.h +0 -0
tools/verification/rvgen/rvgen/automata.py renamed from tools/verification/dot2/dot2/automata.py +0 -0
tools/verification/rvgen/rvgen/dot2c.py renamed from tools/verification/dot2/dot2/dot2c.py +1 -1
@@ -13,7 +13,7 @@ # For further information, see: # Documentation/trace/rv/deterministic_automata.rst -from dot2.automata import Automata +from .automata import Automata class Dot2c(Automata): enum_suffix = ""
tools/verification/rvgen/rvgen/dot2k.py renamed from tools/verification/dot2/dot2/dot2k.py +5 -5
@@ -8,13 +8,13 @@ # For further information, see: # Documentation/trace/rv/da_monitor_synthesis.rst -from dot2.dot2c import Dot2c +from .dot2c import Dot2c import platform import os class dot2k(Dot2c): monitor_types = { "global" : 1, "per_cpu" : 2, "per_task" : 3 } - monitor_templates_dir = "dot2/dot2k_templates/" + monitor_templates_dir = "rvgen/dot2k_templates/" rv_dir = "kernel/trace/rv" monitor_type = "per_cpu"
@@ -60,14 +60,14 @@ class dot2k(Dot2c): if platform.system() != "Linux": raise OSError("I can only run on Linux.") - kernel_path = "/lib/modules/%s/build/tools/verification/dot2/dot2k_templates/" % (platform.release()) + kernel_path = "/lib/modules/%s/build/tools/verification/rvgen/dot2k_templates/" % (platform.release()) if os.path.exists(kernel_path): self.monitor_templates_dir = kernel_path return - if os.path.exists("/usr/share/dot2/dot2k_templates/"): - self.monitor_templates_dir = "/usr/share/dot2/dot2k_templates/" + if os.path.exists("/usr/share/rvgen/dot2k_templates/"): + self.monitor_templates_dir = "/usr/share/rvgen/dot2k_templates/" return raise FileNotFoundError("Could not find the template directory, do you have the kernel source installed?")
Signature · 1 line
2.39.5
PATCH v2 10/22 Documentation/rv: Prepare monitor synthesis document for LTL inclusion
In reply to Nam CaoMonitor synthesis from deterministic automaton and linear temporal logic have a lot in common. Therefore a single document should describe both.
Change da_monitor_synthesis.rst to monitor_synthesis.rst. LTL monitor synthesis will be added to this file by a follow-up commit.
This makes the diff far easier to read. If renaming and adding LTL info is done in a single commit, git wouldn't recognize it as a rename, but a file removal and a file addition.
While at it, correct the old dot2k commands to the new rvgen commands.
---
Documentation/trace/rv/index.rst | 2 +-
...or_synthesis.rst => monitor_synthesis.rst} | 20 +++++++++----------
2 files changed, 11 insertions(+), 11 deletions(-)
rename Documentation/trace/rv/{da_monitor_synthesis.rst => monitor_synthesis.rst} (92%)Documentation/trace/rv/index.rst +1 -1
@@ -8,7 +8,7 @@ Runtime Verification runtime-verification.rst deterministic_automata.rst - da_monitor_synthesis.rst + monitor_synthesis.rst da_monitor_instrumentation.rst monitor_wip.rst monitor_wwnr.rst
Documentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +10 -10
@@ -1,5 +1,5 @@ -Deterministic Automata Monitor Synthesis -======================================== +Runtime verification Monitor Synthesis +====================================== The starting point for the application of runtime verification (RV) techniques is the *specification* or *modeling* of the desired (or undesired) behavior
@@ -36,24 +36,24 @@ below:: | +----> panic ? +-------> <user-specified> -DA monitor synthesis +RV monitor synthesis -------------------- The synthesis of automata-based models into the Linux *RV monitor* abstraction -is automated by the dot2k tool and the rv/da_monitor.h header file that +is automated by the rvgen tool and the rv/da_monitor.h header file that contains a set of macros that automatically generate the monitor's code. -dot2k +rvgen ----- -The dot2k utility leverages dot2c by converting an automaton model in +The rvgen utility leverages dot2c by converting an automaton model in the DOT format into the C representation [1] and creating the skeleton of a kernel monitor in C. For example, it is possible to transform the wip.dot model present in [1] into a per-cpu monitor with the following command:: - $ dot2k -d wip.dot -t per_cpu + $ rvgen monitor -c da -s wip.dot -t per_cpu This will create a directory named wip/ with the following files:
@@ -87,7 +87,7 @@ the second for monitors with per-cpu instances, and the third with per-task instances. In all cases, the 'name' argument is a string that identifies the monitor, and -the 'type' argument is the data type used by dot2k on the representation of +the 'type' argument is the data type used by rvgen on the representation of the model in C. For example, the wip model with two states and three events can be
@@ -134,7 +134,7 @@ Final remarks ------------- With the monitor synthesis in place using the rv/da_monitor.h and -dot2k, the developer's work should be limited to the instrumentation +rvgen, the developer's work should be limited to the instrumentation of the system, increasing the confidence in the overall approach. [1] For details about deterministic automata format and the translation
@@ -142,6 +142,6 @@ from one representation to another, see:: Documentation/trace/rv/deterministic_automata.rst -[2] dot2k appends the monitor's name suffix to the events enums to +[2] rvgen appends the monitor's name suffix to the events enums to avoid conflicting variables when exporting the global vmlinux.h use by BPF programs.
Signature · 1 line
2.39.5
PATCH v2 11/22 verification/rvgen: Prepare the templates for LTL inclusion
In reply to Nam CaoTo prepare for the inclusion of linear temporal logic monitor, prepare the generation template files:
- Rename the directory dot2k_templates to templates
- Move the dot2k-specific files to templates/dot2k
- Move the container-specific files to templates/container
(Kconfig can be shared with LTL, therefore leave it at templates/)
This new structure allows sharing code for reading Kconfig and main.c templates between DA monitor, container monitor and LTL monitor.
The intention is to add template files for LTL to templates/ltl.
---
tools/verification/rvgen/Makefile | 2 +-
tools/verification/rvgen/rvgen/dot2k.py | 33 +++++++++++++------
.../{dot2k_templates => templates}/Kconfig | 0
.../container/Kconfig} | 0
.../container/main.c} | 0
.../container/main.h} | 0
.../dot2k}/main.c | 0
.../dot2k}/trace.h | 0
8 files changed, 24 insertions(+), 11 deletions(-)
rename tools/verification/rvgen/{dot2k_templates => templates}/Kconfig (100%)
rename tools/verification/rvgen/{dot2k_templates/Kconfig_container => templates/container/Kconfig} (100%)
rename tools/verification/rvgen/{dot2k_templates/main_container.c => templates/container/main.c} (100%)
rename tools/verification/rvgen/{dot2k_templates/main_container.h => templates/container/main.h} (100%)
rename tools/verification/rvgen/{dot2k_templates => templates/dot2k}/main.c (100%)
rename tools/verification/rvgen/{dot2k_templates => templates/dot2k}/trace.h (100%)tools/verification/rvgen/Makefile +1 -1
@@ -23,4 +23,4 @@ install: $(INSTALL) __main__.py -D -m 755 $(DESTDIR)$(bindir)/rvgen mkdir -p ${miscdir}/ - cp -rp dot2k_templates $(DESTDIR)$(miscdir)/ + cp -rp templates $(DESTDIR)$(miscdir)/
tools/verification/rvgen/rvgen/dot2k.py +23 -10
@@ -14,13 +14,16 @@ import os class dot2k(Dot2c): monitor_types = { "global" : 1, "per_cpu" : 2, "per_task" : 3 } - monitor_templates_dir = "rvgen/dot2k_templates/" rv_dir = "kernel/trace/rv" monitor_type = "per_cpu" def __init__(self, file_path, MonitorType, extra_params={}): self.container = extra_params.get("subcmd") == "container" self.parent = extra_params.get("parent") + if self.container: + self.monitor_templates_dir = "rvgen/templates/container" + else: + self.monitor_templates_dir = "rvgen/templates/dot2k" self.__fill_rv_templates_dir() if self.container:
@@ -33,9 +36,7 @@ class dot2k(Dot2c): self.name = extra_params.get("model_name") self.events = [] self.states = [] - self.main_c = self.__read_file(self.monitor_templates_dir + "main_container.c") - self.main_h = self.__read_file(self.monitor_templates_dir + "main_container.h") - self.kconfig = self.__read_file(self.monitor_templates_dir + "Kconfig_container") + self.main_h = self._read_template_file("main.h") else: super().__init__(file_path, extra_params.get("model_name"))
@@ -43,9 +44,10 @@ class dot2k(Dot2c): if self.monitor_type is None: raise ValueError("Unknown monitor type: %s" % MonitorType) self.monitor_type = MonitorType - self.main_c = self.__read_file(self.monitor_templates_dir + "main.c") - self.trace_h = self.__read_file(self.monitor_templates_dir + "trace.h") - self.kconfig = self.__read_file(self.monitor_templates_dir + "Kconfig") + self.trace_h = self._read_template_file("trace.h") + + self.main_c = self._read_template_file("main.c") + self.kconfig = self._read_template_file("Kconfig") self.enum_suffix = "_%s" % self.name self.description = extra_params.get("description", self.name) or "auto-generated" self.auto_patch = extra_params.get("auto_patch")
@@ -60,14 +62,15 @@ class dot2k(Dot2c): if platform.system() != "Linux": raise OSError("I can only run on Linux.") - kernel_path = "/lib/modules/%s/build/tools/verification/rvgen/dot2k_templates/" % (platform.release()) + kernel_path = "/lib/modules/%s/build/tools/verification/%s/" \ + % (platform.release(), self.monitor_templates_dir) if os.path.exists(kernel_path): self.monitor_templates_dir = kernel_path return - if os.path.exists("/usr/share/rvgen/dot2k_templates/"): - self.monitor_templates_dir = "/usr/share/rvgen/dot2k_templates/" + if os.path.exists("/usr/share/%s/" % self.monitor_templates_dir): + self.monitor_templates_dir = "/usr/share/%s/" % self.monitor_templates_dir return raise FileNotFoundError("Could not find the template directory, do you have the kernel source installed?")
@@ -109,6 +112,16 @@ class dot2k(Dot2c): fd.close() return content + def _read_template_file(self, file): + try: + path = os.path.join(self.monitor_templates_dir, file) + return self.__read_file(path) + except Exception: + # Specific template file not found. Try the generic template file in the template/ + # directory, which is one level up + path = os.path.join(self.monitor_templates_dir, "..", file) + return self.__read_file(path) + def fill_monitor_type(self): return self.monitor_type.upper()
tools/verification/rvgen/templates/Kconfig renamed from tools/verification/rvgen/dot2k_templates/Kconfig +0 -0
tools/verification/rvgen/templates/container/Kconfig renamed from tools/verification/rvgen/dot2k_templates/Kconfig_container +0 -0
tools/verification/rvgen/templates/container/main.c renamed from tools/verification/rvgen/dot2k_templates/main_container.c +0 -0
tools/verification/rvgen/templates/container/main.h renamed from tools/verification/rvgen/dot2k_templates/main_container.h +0 -0
tools/verification/rvgen/templates/dot2k/main.c renamed from tools/verification/rvgen/dot2k_templates/main.c +0 -0
tools/verification/rvgen/templates/dot2k/trace.h renamed from tools/verification/rvgen/dot2k_templates/trace.h +0 -0
Signature · 1 line
2.39.5
PATCH v2 12/22 verification/rvgen: Restructure the classes to prepare for LTL inclusion
In reply to Nam CaoBoth container generation and DA monitor generation is implemented in the class dot2k. That requires some ugly "if is_container ... else ...". If linear temporal logic support is added at the current state, the "if else" chain is longer and uglier.
Furthermore, container generation is irrevelant to .dot files. It is therefore illogical to be implemented in class "dot2k".
Clean it up, restructure the dot2k class into the following class hierarchy:
(RVGenerator)
/\
/ \
/ \
/ \
/ \
(Container) (Monitor)
/\
/ \
/ \
/ \
(dot2k) [ltl2k] <- intendedThis allows a simple and clean integration of LTL.
--- tools/verification/rvgen/Makefile | 2 + tools/verification/rvgen/__main__.py | 6 +- tools/verification/rvgen/rvgen/container.py | 22 ++ tools/verification/rvgen/rvgen/dot2k.py | 297 ++------------------ tools/verification/rvgen/rvgen/generator.py | 284 +++++++++++++++++++ 5 files changed, 328 insertions(+), 283 deletions(-) create mode 100644 tools/verification/rvgen/rvgen/container.py create mode 100644 tools/verification/rvgen/rvgen/generator.py
tools/verification/rvgen/Makefile +2 -0
@@ -20,6 +20,8 @@ install: $(INSTALL) rvgen/dot2c.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/dot2c.py $(INSTALL) dot2c -D -m 755 $(DESTDIR)$(bindir)/ $(INSTALL) rvgen/dot2k.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/dot2k.py + $(INSTALL) rvgen/container.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/container.py + $(INSTALL) rvgen/generator.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/generator.py $(INSTALL) __main__.py -D -m 755 $(DESTDIR)$(bindir)/rvgen mkdir -p ${miscdir}/
tools/verification/rvgen/__main__.py +4 -2
@@ -10,6 +10,8 @@ if __name__ == '__main__': from rvgen.dot2k import dot2k + from rvgen.generator import Monitor + from rvgen.container import Container import argparse import sys
@@ -29,7 +31,7 @@ if __name__ == '__main__': help="Monitor class, either \"da\" or \"ltl\"") monitor_parser.add_argument('-s', "--spec", dest="spec", help="Monitor specification file") monitor_parser.add_argument('-t', "--monitor_type", dest="monitor_type", - help=f"Available options: {', '.join(dot2k.monitor_types.keys())}") + help=f"Available options: {', '.join(Monitor.monitor_types.keys())}") container_parser = subparsers.add_parser("container") container_parser.add_argument('-n', "--model_name", dest="model_name", required=True)
@@ -47,7 +49,7 @@ if __name__ == '__main__': print("Unknown monitor class:", params.monitor_class) sys.exit(1) else: - monitor = dot2k(None, None, vars(params)) + monitor = Container(vars(params)) except Exception as e: print('Error: '+ str(e)) print("Sorry : :-(")
tools/verification/rvgen/rvgen/container.py new file +22 -0
@@ -0,0 +1,22 @@ +#!/usr/bin/env python3 +# SPDX-License-Identifier: GPL-2.0-only +# +# Copyright (C) 2019-2022 Red Hat, Inc. Daniel Bristot de Oliveira <[email protected]> +# +# Generator for runtime verification monitor container + +from . import generator + + +class Container(generator.RVGenerator): + monitor_templates_dir = "rvgen/templates/container" + + def __init__(self, extra_params={}): + super().__init__(extra_params) + self.name = extra_params.get("model_name") + self.main_h = self._read_template_file("main.h") + + def fill_model_h(self): + main_h = self.main_h + main_h = main_h.replace("%%MODEL_NAME%%", self.name) + return main_h
tools/verification/rvgen/rvgen/dot2k.py +16 -281
323 lines not on this page · raw message
tools/verification/rvgen/rvgen/generator.py new file +284 -0
284 lines not on this page · raw message
Signature · 1 line
2.39.5
PATCH v2 13/22 Add support for LTL monitors
In reply to Nam CaoWhile attempting to implement DA monitors for some complex specifications, deterministic automaton is found to be inappropriate as the specification language. The automaton is complicated, hard to understand, and error-prone.
For these cases, linear temporal logic is more suitable as the specification language.
Add support for linear temporal logic runtime verification monitor.
For all the details, see the documentations added by this commit.
--- Documentation/trace/rv/index.rst | 1 + .../trace/rv/linear_temporal_logic.rst | 97 +++ Documentation/trace/rv/monitor_synthesis.rst | 141 ++++- include/linux/rv.h | 56 +- include/rv/ltl_monitor.h | 184 ++++++ kernel/fork.c | 5 +- kernel/trace/rv/Kconfig | 7 + kernel/trace/rv/rv_trace.h | 47 ++ tools/verification/rvgen/.gitignore | 3 + tools/verification/rvgen/Makefile | 2 + tools/verification/rvgen/__main__.py | 3 +- tools/verification/rvgen/rvgen/ltl2ba.py | 552 ++++++++++++++++++ tools/verification/rvgen/rvgen/ltl2k.py | 242 ++++++++ .../verification/rvgen/templates/ltl2k/main.c | 102 ++++ .../rvgen/templates/ltl2k/trace.h | 14 + 15 files changed, 1431 insertions(+), 25 deletions(-) create mode 100644 Documentation/trace/rv/linear_temporal_logic.rst create mode 100644 include/rv/ltl_monitor.h create mode 100644 tools/verification/rvgen/.gitignore create mode 100644 tools/verification/rvgen/rvgen/ltl2ba.py create mode 100644 tools/verification/rvgen/rvgen/ltl2k.py create mode 100644 tools/verification/rvgen/templates/ltl2k/main.c create mode 100644 tools/verification/rvgen/templates/ltl2k/trace.h
Documentation/trace/rv/index.rst +1 -0
@@ -8,6 +8,7 @@ Runtime Verification runtime-verification.rst deterministic_automata.rst + linear_temporal_logic.rst monitor_synthesis.rst da_monitor_instrumentation.rst monitor_wip.rst
Documentation/trace/rv/linear_temporal_logic.rst new file +97 -0
97 lines not on this page · raw message
Documentation/trace/rv/monitor_synthesis.rst +125 -16
169 lines not on this page · raw message
include/linux/rv.h +52 -4
75 lines not on this page · raw message
include/rv/ltl_monitor.h new file +184 -0
184 lines not on this page · raw message
kernel/fork.c +1 -4
@@ -2127,10 +2127,7 @@ static void copy_oom_score_adj(u64 clone_flags, struct task_struct *tsk)#ifdef CONFIG_RV static void rv_task_fork (struct task_struct *p) { -int i; - -for (i =0 ; i <RV_PER_TASK_MONITORS ; i++) - p->rv[i].da_mon.monitoring = false; +memset (p->rv,0 ,sizeof (p->rv)); }#else #define rv_task_fork (p) do {} while (0)
kernel/trace/rv/Kconfig +7 -0
@@ -11,6 +11,13 @@ config DA_MON_EVENTS_ID select RV_MON_EVENTS bool +config LTL_MON_EVENTS_ID + select RV_MON_EVENTS + bool + +config RV_LTL_MONITOR + bool + menuconfig RV bool "Runtime Verification" depends on TRACING
kernel/trace/rv/rv_trace.h +47 -0
53 lines not on this page · raw message
tools/verification/rvgen/.gitignore new file +3 -0
@@ -0,0 +1,3 @@ +__pycache__/ +parser.out +parsetab.py
tools/verification/rvgen/Makefile +2 -0
@@ -22,6 +22,8 @@ install: $(INSTALL) rvgen/dot2k.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/dot2k.py $(INSTALL) rvgen/container.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/container.py $(INSTALL) rvgen/generator.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/generator.py + $(INSTALL) rvgen/ltl2ba.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/ltl2ba.py + $(INSTALL) rvgen/ltl2k.py -D -m 644 $(DESTDIR)$(PYLIB)/rvgen/ltl2k.py $(INSTALL) __main__.py -D -m 755 $(DESTDIR)$(bindir)/rvgen mkdir -p ${miscdir}/
tools/verification/rvgen/__main__.py +2 -1
@@ -12,6 +12,7 @@ if __name__ == '__main__': from rvgen.dot2k import dot2k from rvgen.generator import Monitor from rvgen.container import Container + from rvgen.ltl2k import ltl2k import argparse import sys
@@ -44,7 +45,7 @@ if __name__ == '__main__': if params.monitor_class == "da": monitor = dot2k(params.spec, params.monitor_type, vars(params)) elif params.monitor_class == "ltl": - raise NotImplementedError + monitor = ltl2k(params.spec, params.monitor_type, vars(params)) else: print("Unknown monitor class:", params.monitor_class) sys.exit(1)
tools/verification/rvgen/rvgen/ltl2ba.py new file +552 -0
552 lines not on this page · raw message
tools/verification/rvgen/rvgen/ltl2k.py new file +242 -0
242 lines not on this page · raw message
tools/verification/rvgen/templates/ltl2k/main.c new file +102 -0
102 lines not on this page · raw message
tools/verification/rvgen/templates/ltl2k/trace.h new file +14 -0
@@ -0,0 +1,14 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +/* +* Snippet to be included in rv_trace.h +*/ + +#ifdef CONFIG_RV_MON_%%MODEL_NAME_UP%% +DEFINE_EVENT(event_%%MONITOR_CLASS%%, event_%%MODEL_NAME%%, + TP_PROTO(struct task_struct *task, char *states, char *atoms, char *next), +TP_ARGS (task, states, atoms, next)); +DEFINE_EVENT(error_%%MONITOR_CLASS%%, error_%%MODEL_NAME%%, + TP_PROTO(struct task_struct *task), +TP_ARGS (task)); +#endif /* CONFIG_RV_MON_%%MODEL_NAME_UP%% */
Signature · 1 line
2.39.5
PATCH v2 14/22 Add rtapp container monitor
In reply to Nam CaoAdd the container "rtapp" which is the monitor collection for detecting problems with real-time applications. The monitors will be added in the follow-up commits.
--- kernel/trace/rv/Kconfig | 1 + kernel/trace/rv/Makefile | 1 + kernel/trace/rv/monitors/rtapp/Kconfig | 6 +++++ kernel/trace/rv/monitors/rtapp/rtapp.c | 34 ++++++++++++++++++++++++++ kernel/trace/rv/monitors/rtapp/rtapp.h | 3 +++ 5 files changed, 45 insertions(+) create mode 100644 kernel/trace/rv/monitors/rtapp/Kconfig create mode 100644 kernel/trace/rv/monitors/rtapp/rtapp.c create mode 100644 kernel/trace/rv/monitors/rtapp/rtapp.h
kernel/trace/rv/Kconfig +1 -0
@@ -41,6 +41,7 @@ source "kernel/trace/rv/monitors/snroc/Kconfig" source "kernel/trace/rv/monitors/scpd/Kconfig" source "kernel/trace/rv/monitors/snep/Kconfig" source "kernel/trace/rv/monitors/sncid/Kconfig" +source "kernel/trace/rv/monitors/rtapp/Kconfig" # Add new monitors here config RV_REACTORS
kernel/trace/rv/Makefile +1 -0
@@ -12,6 +12,7 @@ obj-$(CONFIG_RV_MON_SNROC) += monitors/snroc/snroc.o obj-$(CONFIG_RV_MON_SCPD) += monitors/scpd/scpd.o obj-$(CONFIG_RV_MON_SNEP) += monitors/snep/snep.o obj-$(CONFIG_RV_MON_SNCID) += monitors/sncid/sncid.o +obj-$(CONFIG_RV_MON_RTAPP) += monitors/rtapp/rtapp.o # Add new monitors here obj-$(CONFIG_RV_REACTORS) += rv_reactors.o obj-$(CONFIG_RV_REACT_PRINTK) += reactor_printk.o
kernel/trace/rv/monitors/rtapp/Kconfig new file +6 -0
@@ -0,0 +1,6 @@ +config RV_MON_RTAPP + depends on RV + bool "rtapp monitor" + help + Collection of monitors to check for common problems with real-time application that cause + unexpected latency.
kernel/trace/rv/monitors/rtapp/rtapp.c new file +34 -0
@@ -0,0 +1,34 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/init.h> +#include <linux/rv.h> + +#define MODULE_NAME "rtapp" + +#include "rtapp.h" + +struct rv_monitor rv_rtapp; + +struct rv_monitor rv_rtapp = { + .name ="rtapp" , + .description ="Collection of monitors for detecting problems with real-time applications" , +}; + +static int __init register_rtapp (void ) +{ +rv_register_monitor (&rv_rtapp,NULL ); +return 0 ; +} + +static void __exit unregister_rtapp(void) +{ +rv_unregister_monitor (&rv_rtapp); +} + +module_init (register_rtapp); +module_exit (unregister_rtapp); + +MODULE_LICENSE ("GPL" ); +MODULE_AUTHOR ("Nam Cao <[email protected]>" ); +MODULE_DESCRIPTION ("Collection of monitors for detecting problems with real-time applications" );
kernel/trace/rv/monitors/rtapp/rtapp.h new file +3 -0
@@ -0,0 +1,3 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +extern struct rv_monitor rv_rtapp;
Signature · 1 line
2.39.5
PATCH v2 15/22 x86/tracing: Remove redundant trace_pagefault_key
In reply to Nam Caotrace_pagefault_key is used to optimize the pagefault tracepoints when it is disabled. However, tracepoints already have built-in static_key for this exact purpose.
Remove this redundant key.
---
Cc: Thomas Gleixner <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Borislav Petkov <[email protected]>
Cc: Dave Hansen <[email protected]>
Cc: [email protected]
Cc: H. Peter Anvin <[email protected]>
Cc: Andy Lutomirski <[email protected]>
Cc: Peter Zijlstra <[email protected]>
--- arch/x86/include/asm/trace/common.h | 12 ------------ arch/x86/include/asm/trace/exceptions.h | 18 ++++++------------ arch/x86/include/asm/trace/irq_vectors.h | 1 - arch/x86/kernel/Makefile | 1 - arch/x86/kernel/tracepoint.c | 21 --------------------- arch/x86/mm/fault.c | 3 --- 6 files changed, 6 insertions(+), 50 deletions(-) delete mode 100644 arch/x86/include/asm/trace/common.h delete mode 100644 arch/x86/kernel/tracepoint.c
arch/x86/include/asm/trace/common.h deleted +0 -12
@@ -1,12 +0,0 @@ -#ifndef _ASM_TRACE_COMMON_H -#define _ASM_TRACE_COMMON_H - -#ifdef CONFIG_TRACING -DECLARE_STATIC_KEY_FALSE (trace_pagefault_key); -#define trace_pagefault_enabled () \ - static_branch_unlikely(&trace_pagefault_key) -#else -static inline bool trace_pagefault_enabled (void ) {return false; } -#endif - -#endif
arch/x86/include/asm/trace/exceptions.h +6 -12
@@ -6,10 +6,6 @@#define _TRACE_PAGE_FAULT_H#include <linux/tracepoint.h> -#include <asm/trace/common.h> - -extern int trace_pagefault_reg (void ); -extern void trace_pagefault_unreg (void ); DECLARE_EVENT_CLASS(x86_exceptions,
@@ -34,15 +30,13 @@ DECLARE_EVENT_CLASS(x86_exceptions, (void *)__entry->address, (void *)__entry->ip, __entry->error_code) ); -#define DEFINE_PAGE_FAULT_EVENT (name) \ -DEFINE_EVENT_FN(x86_exceptions, name, \ - TP_PROTO(unsigned long address, struct pt_regs *regs, \ - unsigned long error_code), \ - TP_ARGS(address, regs, error_code), \ - trace_pagefault_reg, trace_pagefault_unreg); +DEFINE_EVENT (x86_exceptions, page_fault_user, + TP_PROTO(unsigned long address, struct pt_regs *regs, unsigned long error_code), +TP_ARGS (address, regs, error_code)); -DEFINE_PAGE_FAULT_EVENT (page_fault_user); -DEFINE_PAGE_FAULT_EVENT (page_fault_kernel); +DEFINE_EVENT (x86_exceptions, page_fault_kernel, + TP_PROTO(unsigned long address, struct pt_regs *regs, unsigned long error_code), +TP_ARGS (address, regs, error_code));#undef TRACE_INCLUDE_PATH#undef TRACE_INCLUDE_FILE
arch/x86/include/asm/trace/irq_vectors.h +0 -1
@@ -6,7 +6,6 @@#define _TRACE_IRQ_VECTORS_H#include <linux/tracepoint.h> -#include <asm/trace/common.h> #ifdef CONFIG_X86_LOCAL_APIC
arch/x86/kernel/Makefile +0 -1
@@ -139,7 +139,6 @@ obj-$(CONFIG_OF) += devicetree.o obj-$(CONFIG_UPROBES) += uprobes.o obj-$(CONFIG_PERF_EVENTS) += perf_regs.o -obj-$(CONFIG_TRACING) += tracepoint.o obj-$(CONFIG_SCHED_MC_PRIO) += itmt.o obj-$(CONFIG_X86_UMIP) += umip.o
arch/x86/kernel/tracepoint.c deleted +0 -21
@@ -1,21 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 -/* -* Copyright (C) 2013 Seiji Aguchi <[email protected]> -*/ -#include <linux/jump_label.h> -#include <linux/atomic.h> - -#include <asm/trace/exceptions.h> - -DEFINE_STATIC_KEY_FALSE (trace_pagefault_key); - -int trace_pagefault_reg (void ) -{ -static_branch_inc (&trace_pagefault_key); -return 0 ; -} - -void trace_pagefault_unreg (void ) -{ -static_branch_dec (&trace_pagefault_key); -}
arch/x86/mm/fault.c +0 -3
@@ -1455,9 +1455,6 @@ static __always_inline void trace_page_fault_entries(struct pt_regs *regs, unsigned long error_code, unsigned long address) { - if (!trace_pagefault_enabled()) - return; - if (user_mode(regs)) trace_page_fault_user(address, regs, error_code); else
Signature · 1 line
2.39.5
PATCH v2 16/22 x86/tracing: Move page fault trace points to generic
In reply to Nam CaoPage fault trace points are interesting for other architectures as well. Move them to be generic.
---
Cc: Thomas Gleixner <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Borislav Petkov <[email protected]>
Cc: Dave Hansen <[email protected]>
Cc: [email protected]
Cc: "H. Peter Anvin" <[email protected]>
Cc: Andy Lutomirski <[email protected]>
Cc: Peter Zijlstra <[email protected]>
---
arch/x86/mm/fault.c | 2 +-
.../asm/trace => include/trace/events}/exceptions.h | 13 ++++---------
2 files changed, 5 insertions(+), 10 deletions(-)
rename {arch/x86/include/asm/trace => include/trace/events}/exceptions.h (79%)arch/x86/mm/fault.c +1 -1
@@ -38,7 +38,7 @@#include <asm/sev.h> /* snp_dump_hva_rmpentry() */ #define CREATE_TRACE_POINTS -#include <asm/trace/exceptions.h> +#include <trace/events/exceptions.h> /* * Returns 0 if mmiotrace is disabled, or if the fault is not
include/trace/events/exceptions.h renamed from arch/x86/include/asm/trace/exceptions.h +4 -9
@@ -7,7 +7,7 @@#include <linux/tracepoint.h> -DECLARE_EVENT_CLASS(x86_exceptions, +DECLARE_EVENT_CLASS(exceptions, TP_PROTO(unsigned long address, struct pt_regs *regs, unsigned long error_code),
@@ -22,7 +22,7 @@ DECLARE_EVENT_CLASS(x86_exceptions,TP_fast_assign ( __entry->address = address; - __entry->ip = regs->ip; + __entry->ip =instruction_pointer (regs); __entry->error_code = error_code; ),
@@ -30,18 +30,13 @@ DECLARE_EVENT_CLASS(x86_exceptions, (void *)__entry->address, (void *)__entry->ip, __entry->error_code) ); -DEFINE_EVENT (x86_exceptions, page_fault_user, +DEFINE_EVENT (exceptions, page_fault_user, TP_PROTO(unsigned long address, struct pt_regs *regs, unsigned long error_code),TP_ARGS (address, regs, error_code)); - -DEFINE_EVENT (x86_exceptions, page_fault_kernel, +DEFINE_EVENT (exceptions, page_fault_kernel, TP_PROTO(unsigned long address, struct pt_regs *regs, unsigned long error_code),TP_ARGS (address, regs, error_code)); -#undef TRACE_INCLUDE_PATH -#undef TRACE_INCLUDE_FILE -#define TRACE_INCLUDE_PATH . -#define TRACE_INCLUDE_FILE exceptions#endif /* _TRACE_PAGE_FAULT_H */ /* This part must be outside protection */
Signature · 1 line
2.39.5
PATCH v2 17/22 arm64: mm: Add page fault trace points
In reply to Nam CaoAdd page fault trace points, which are useful to implement RV monitor which watches page faults.
---
Cc: Catalin Marinas <[email protected]>
Cc: Will Deacon <[email protected]>
Cc: [email protected]
--- arch/arm64/mm/fault.c | 8 ++++++++ 1 file changed, 8 insertions(+)
arch/arm64/mm/fault.c +8 -0
@@ -44,6 +44,9 @@#include <asm/tlbflush.h> #include <asm/traps.h> +#define CREATE_TRACE_POINTS +#include <trace/events/exceptions.h> +struct fault_info {int (*fn)(unsigned long far,unsigned long esr,struct pt_regs *regs);
@@ -559,6 +562,11 @@ static int __kprobes do_page_fault(unsigned long far, unsigned long esr,if (kprobe_page_fault (regs, esr))return 0 ; +if (user_mode (regs)) +trace_page_fault_user (addr, regs, esr); +else +trace_page_fault_kernel (addr, regs, esr); +/* * If we're in an interrupt or have no user context, we must not take * the fault.
Signature · 1 line
2.39.5
PATCH v2 18/22 riscv: mm: Add page fault trace points
In reply to Nam CaoAdd page fault trace points, which are useful to implement RV monitor that watches page faults.
---
Cc: Paul Walmsley <[email protected]>
Cc: Palmer Dabbelt <[email protected]>
Cc: Albert Ou <[email protected]>
Cc: [email protected]
--- arch/riscv/mm/fault.c | 8 ++++++++ 1 file changed, 8 insertions(+)
arch/riscv/mm/fault.c +8 -0
@@ -20,6 +20,9 @@#include <asm/ptrace.h> #include <asm/tlbflush.h> +#define CREATE_TRACE_POINTS +#include <trace/events/exceptions.h> +#include "../kernel/head.h" static void show_pte (unsigned long addr)
@@ -291,6 +294,11 @@ void handle_page_fault(struct pt_regs *regs)if (kprobe_page_fault (regs, cause))return ; +if (user_mode (regs)) +trace_page_fault_user (addr, regs, cause); +else +trace_page_fault_kernel (addr, regs, cause); +/* * Fault-in kernel-space virtual memory on-demand. * The 'reference' page table is init_mm.pgd.
Signature · 1 line
2.39.5
PATCH v2 19/22 Add rtapp_pagefault monitor
In reply to Nam CaoUserspace real-time applications may have design flaws that they raise page faults in real-time threads, and thus have unexpected latencies.
Add an linear temporal logic monitor to detect this scenario.
---
Cc: Catalin Marinas <[email protected]>
Cc: Will Deacon <[email protected]>
Cc: Paul Walmsley <[email protected]>
Cc: Palmer Dabbelt <[email protected]>
Cc: Albert Ou <[email protected]>
Cc: Alexandre Ghiti <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Borislav Petkov <[email protected]>
Cc: Dave Hansen <[email protected]>
Cc: [email protected]
Cc: H. Peter Anvin <[email protected]>
Cc: Andy Lutomirski <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: [email protected]
Cc: [email protected]
--- kernel/trace/rv/Kconfig | 1 + kernel/trace/rv/Makefile | 1 + kernel/trace/rv/monitors/pagefault/Kconfig | 11 +++ .../trace/rv/monitors/pagefault/pagefault.c | 83 +++++++++++++++++++ .../trace/rv/monitors/pagefault/pagefault.h | 57 +++++++++++++ .../rv/monitors/pagefault/pagefault_trace.h | 14 ++++ kernel/trace/rv/rv_trace.h | 1 + tools/verification/models/rtapp/pagefault.ltl | 1 + 8 files changed, 169 insertions(+) create mode 100644 kernel/trace/rv/monitors/pagefault/Kconfig create mode 100644 kernel/trace/rv/monitors/pagefault/pagefault.c create mode 100644 kernel/trace/rv/monitors/pagefault/pagefault.h create mode 100644 kernel/trace/rv/monitors/pagefault/pagefault_trace.h create mode 100644 tools/verification/models/rtapp/pagefault.ltl
kernel/trace/rv/Kconfig +1 -0
@@ -42,6 +42,7 @@ source "kernel/trace/rv/monitors/scpd/Kconfig" source "kernel/trace/rv/monitors/snep/Kconfig" source "kernel/trace/rv/monitors/sncid/Kconfig" source "kernel/trace/rv/monitors/rtapp/Kconfig" +source "kernel/trace/rv/monitors/pagefault/Kconfig" # Add new monitors here config RV_REACTORS
kernel/trace/rv/Makefile +1 -0
@@ -13,6 +13,7 @@ obj-$(CONFIG_RV_MON_SCPD) += monitors/scpd/scpd.o obj-$(CONFIG_RV_MON_SNEP) += monitors/snep/snep.o obj-$(CONFIG_RV_MON_SNCID) += monitors/sncid/sncid.o obj-$(CONFIG_RV_MON_RTAPP) += monitors/rtapp/rtapp.o +obj-$(CONFIG_RV_MON_PAGEFAULT) += monitors/pagefault/pagefault.o # Add new monitors here obj-$(CONFIG_RV_REACTORS) += rv_reactors.o obj-$(CONFIG_RV_REACT_PRINTK) += reactor_printk.o
kernel/trace/rv/monitors/pagefault/Kconfig new file +11 -0
@@ -0,0 +1,11 @@ +# SPDX-License-Identifier: GPL-2.0-only +# +config RV_MON_PAGEFAULT + depends on RV + select RV_LTL_MONITOR + depends on RV_MON_RTAPP + default y + select LTL_MON_EVENTS_ID + bool "pagefault monitor" + help + Monitor that real-time tasks do not raise page faults
kernel/trace/rv/monitors/pagefault/pagefault.c new file +83 -0
83 lines not on this page · raw message
kernel/trace/rv/monitors/pagefault/pagefault.h new file +57 -0
57 lines not on this page · raw message
kernel/trace/rv/monitors/pagefault/pagefault_trace.h new file +14 -0
@@ -0,0 +1,14 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +/* +* Snippet to be included in rv_trace.h +*/ + +#ifdef CONFIG_RV_MON_PAGEFAULT +DEFINE_EVENT (event_ltl_monitor_id, event_pagefault, + TP_PROTO(struct task_struct *task, char *states, char *atoms, char *next), +TP_ARGS (task, states, atoms, next)); +DEFINE_EVENT (error_ltl_monitor_id, error_pagefault, + TP_PROTO(struct task_struct *task), +TP_ARGS (task)); +#endif /* CONFIG_RV_MON_PAGEFAULT */
kernel/trace/rv/rv_trace.h +1 -0
@@ -172,6 +172,7 @@ TRACE_EVENT(error_ltl_monitor_id,TP_printk ("%s[%d]: violation detected" ,__get_str (comm), __entry->pid) ); +#include <monitors/pagefault/pagefault_trace.h> // Add new monitors based on CONFIG_LTL_MON_EVENTS_ID here #endif /* CONFIG_LTL_MON_EVENTS_ID */ #endif /* _TRACE_RV_H */
tools/verification/models/rtapp/pagefault.ltl new file +1 -0
@@ -0,0 +1 @@ +RULE = always (RT imply not PAGEFAULT)
Signature · 1 line
2.39.5
PATCH v2 20/22 Add rtapp_sleep monitor
In reply to Nam CaoAdd a monitor for checking that real-time tasks do not go to sleep in a manner that may cause undesirable latency.
Also change
RV depends on TRACING
to
RV select TRACING
to avoid the following recursive dependency:
error: recursive dependency detected!
symbol TRACING is selected by PREEMPTIRQ_TRACEPOINTS symbol PREEMPTIRQ_TRACEPOINTS depends on TRACE_IRQFLAGS symbol TRACE_IRQFLAGS is selected by RV_MON_SLEEP symbol RV_MON_SLEEP depends on RV
symbol RV depends on TRACING
--- kernel/trace/rv/Kconfig | 3 +- kernel/trace/rv/Makefile | 1 + kernel/trace/rv/monitors/sleep/Kconfig | 13 + kernel/trace/rv/monitors/sleep/sleep.c | 217 ++++++++++++++ kernel/trace/rv/monitors/sleep/sleep.h | 293 +++++++++++++++++++ kernel/trace/rv/monitors/sleep/sleep_trace.h | 14 + kernel/trace/rv/rv_trace.h | 1 + tools/verification/models/rtapp/sleep.ltl | 15 + 8 files changed, 556 insertions(+), 1 deletion(-) create mode 100644 kernel/trace/rv/monitors/sleep/Kconfig create mode 100644 kernel/trace/rv/monitors/sleep/sleep.c create mode 100644 kernel/trace/rv/monitors/sleep/sleep.h create mode 100644 kernel/trace/rv/monitors/sleep/sleep_trace.h create mode 100644 tools/verification/models/rtapp/sleep.ltl
kernel/trace/rv/Kconfig +2 -1
@@ -20,7 +20,7 @@ config RV_LTL_MONITOR menuconfig RV bool "Runtime Verification" - depends on TRACING + select TRACING help Enable the kernel runtime verification infrastructure. RV is a lightweight (yet rigorous) method that complements classical
@@ -43,6 +43,7 @@ source "kernel/trace/rv/monitors/snep/Kconfig" source "kernel/trace/rv/monitors/sncid/Kconfig" source "kernel/trace/rv/monitors/rtapp/Kconfig" source "kernel/trace/rv/monitors/pagefault/Kconfig" +source "kernel/trace/rv/monitors/sleep/Kconfig" # Add new monitors here config RV_REACTORS
kernel/trace/rv/Makefile +1 -0
@@ -14,6 +14,7 @@ obj-$(CONFIG_RV_MON_SNEP) += monitors/snep/snep.o obj-$(CONFIG_RV_MON_SNCID) += monitors/sncid/sncid.o obj-$(CONFIG_RV_MON_RTAPP) += monitors/rtapp/rtapp.o obj-$(CONFIG_RV_MON_PAGEFAULT) += monitors/pagefault/pagefault.o +obj-$(CONFIG_RV_MON_SLEEP) += monitors/sleep/sleep.o # Add new monitors here obj-$(CONFIG_RV_REACTORS) += rv_reactors.o obj-$(CONFIG_RV_REACT_PRINTK) += reactor_printk.o
kernel/trace/rv/monitors/sleep/Kconfig new file +13 -0
@@ -0,0 +1,13 @@ +# SPDX-License-Identifier: GPL-2.0-only +# +config RV_MON_SLEEP + depends on RV + select RV_LTL_MONITOR + depends on HAVE_SYSCALL_TRACEPOINTS + depends on RV_MON_RTAPP + select TRACE_IRQFLAGS + default y + select LTL_MON_EVENTS_ID + bool "sleep monitor" + help + Monitor that real-time tasks do not sleep in a manner that may cause undesirable latency.
kernel/trace/rv/monitors/sleep/sleep.c new file +217 -0
217 lines not on this page · raw message
kernel/trace/rv/monitors/sleep/sleep.h new file +293 -0
293 lines not on this page · raw message
kernel/trace/rv/monitors/sleep/sleep_trace.h new file +14 -0
@@ -0,0 +1,14 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +/* +* Snippet to be included in rv_trace.h +*/ + +#ifdef CONFIG_RV_MON_SLEEP +DEFINE_EVENT (event_ltl_monitor_id, event_sleep, + TP_PROTO(struct task_struct *task, char *states, char *atoms, char *next), +TP_ARGS (task, states, atoms, next)); +DEFINE_EVENT (error_ltl_monitor_id, error_sleep, + TP_PROTO(struct task_struct *task), +TP_ARGS (task)); +#endif /* CONFIG_RV_MON_SLEEP */
kernel/trace/rv/rv_trace.h +1 -0
@@ -173,6 +173,7 @@ TRACE_EVENT(error_ltl_monitor_id,TP_printk ("%s[%d]: violation detected" ,__get_str (comm), __entry->pid) );#include <monitors/pagefault/pagefault_trace.h> +#include <monitors/sleep/sleep_trace.h> // Add new monitors based on CONFIG_LTL_MON_EVENTS_ID here #endif /* CONFIG_LTL_MON_EVENTS_ID */ #endif /* _TRACE_RV_H */
tools/verification/models/rtapp/sleep.ltl new file +15 -0
@@ -0,0 +1,15 @@ +RULE = always (RT imply (SLEEP imply (RT_FRIENDLY_SLEEP or ALLOWLIST))) + +RT_FRIENDLY_SLEEP = (RT_VALID_SLEEP_REASON or KERNEL_THREAD) + and ((not WAKE) until RT_FRIENDLY_WAKE) + +RT_VALID_SLEEP_REASON = PI_FUTEX or NANOSLEEP + +RT_FRIENDLY_WAKE = WOKEN_BY_EQUAL_OR_HIGHER_PRIO + or WOKEN_BY_HARDIRQ + or WOKEN_BY_NMI + +ALLOWLIST = BLOCK_ON_RT_MUTEX + or TASK_IS_RCU + or TASK_IS_MIGRATION + or KTHREAD_SHOULD_STOP
Signature · 1 line
2.39.5
PATCH v2 21/22 Add documentation for rtapp monitor
In reply to Nam CaoAdd documentation describing the rtapp monitor.
--- Documentation/trace/rv/monitor_rtapp.rst | 105 +++++++++++++++++++++++ 1 file changed, 105 insertions(+) create mode 100644 Documentation/trace/rv/monitor_rtapp.rst
Documentation/trace/rv/monitor_rtapp.rst new file +105 -0
@@ -0,0 +1,105 @@ +Scheduler monitors +================== + +- Name: rtapp +- Type: container for multiple monitors +- Author: Nam Cao <[email protected]> + +Description +----------- + +Real-time applications may have design flaws such that they experience unexpected latency and fail +to meet their time requirements. Often, these flaws follow a few patterns: + + - Page faults: A real-time thread may access memory that does not have a mapped physical backing + or must first be copied (such as for copy-on-write). Thus a page fault is raised and the kernel + must first perform the expensive action. This causes significant delays to the real-time thread + - Priority inversion: A real-time thread blocks waiting for a lower-priority thread. This causes + the real-time thread to effectively take on the scheduling priority of the lower-priority + thread. For example, the real-time thread needs to access a shared resource that is protected by + a non-pi-mutex, but the mutex is currently owned by a non-real-time thread. + +The `rtapp` monitor detects these patterns. It aids developers to identify reasons for unexpected +latency with real-time applications. It is a container of multiple sub-monitors described in the +following sections. + +Monitor pagefault ++++++++++++++++++ + +The `pagefault` monitor reports real-time tasks raising page faults. Its specification is:: + + RULE = always (RT imply not PAGEFAULT) + +To fix warnings reported by this monitor, `mlockall()` or `mlock()` can be used to ensure physical +backing for memory. + +This monitor may have false negatives because the pages used by the real-time threads may just +happen to be directly available during testing. To minimize this, the system can be put under memory +pressure (e.g. invoking the OOM killer using a program that does `ptr = malloc(SIZE_OF_RAM); +memset(ptr, 0, SIZE_OF_RAM);`) so that the kernel executes aggressive strategies to recycle as much +physical memory as possible. + +Monitor sleep ++++++++++++++ + +The `sleep` monitor reports real-time threads sleeping in a manner that may cause undesirable +latency. Real-time applications should only put a real-time thread to sleep for one of the following +reasons: + + - Cyclic work: real-time thread sleeps waiting for the next cycle. For this case, only the + `nanosleep` syscall should be used. No other method is safe for real-time. For example, threads + waiting for timerfd can be woken by softirq which provides no real-time guarantee. + - Real-time thread waiting for something to happen (e.g. another thread releasing shared + resources, or a completion signal from another thread). In this case, only futexes with priority + inheritance (PI) should be used. Applications usually do not use futexes directly, but use PI + mutexes and PI condition variables which are built on top of futexes. Be aware that the C + library might not implement conditional variables as safe for real-time. As an alternative, the + librtpi library exists to provide a conditional variable implementation that is correct for + real-time applications in Linux. + +Beside the reason for sleeping, the eventual waker should also be real-time-safe. Namely, one of: + + - An equal-or-higher-priority thread + - Hard interrupt handler + - Non-maskable interrupt handler + +This monitor's warning usually means one of the following: + + - Real-time thread is blocked by a non-real-time thread (e.g. due to contention on a mutex without + priority inheritance). This is priority inversion. + - Time-critical work waits for something which is not safe for real-time (e.g. timerfd). + - The work executed by the real-time thread does not need to run at real-time priority at all. + This is not a problem for the real-time thread itself, but it is potentially taking the CPU away + from other important real-time work. + +Application developers may purposely choose to have their real-time application sleep in a way that +is not safe for real-time. It is debatable whether that is a problem. Application developers must +analyze the warnings to make a proper assessment. + +The monitor's specification is:: + + RULE = always (RT imply (SLEEP imply (RT_FRIENDLY_SLEEP or ALLOWLIST))) + + RT_FRIENDLY_SLEEP = (RT_VALID_SLEEP_REASON or KERNEL_THREAD) + and ((not WAKE) until RT_FRIENDLY_WAKE) + + RT_VALID_SLEEP_REASON = PI_FUTEX or NANOSLEEP + + RT_FRIENDLY_WAKE = WOKEN_BY_EQUAL_OR_HIGHER_PRIO + or WOKEN_BY_HARDIRQ + or WOKEN_BY_NMI + + ALLOWLIST = BLOCK_ON_RT_MUTEX + or TASK_IS_RCU + or TASK_IS_MIGRATION + or KTHREAD_SHOULD_STOP + +Beside the scenarios described above, this specification also handle some special cases: + + - `KERNEL_THREAD`: kernel tasks do not have any pattern that can be recognized as valid real-time + sleeping reasons. Therefore sleeping reason is not checked for kernel tasks. + - `RT_SLEEP_WHITELIST`: to handle known false positives with kernel tasks. + - `BLOCK_ON_RT_MUTEX` is included in the allowlist due to its implementation. In the release path + of rt_mutex, a boosted task is de-boosted before waking the rt_mutex's waiter. Consequently, the + monitor may see a real-time-unsafe wakeup (e.g. non-real-time task waking real-time task). This + is actually real-time-safe because preemption is disable for the duration.
Signature · 1 line
2.39.5
PATCH v2 22/22 Allow to configure the number of per-task monitor
In reply to Nam CaoNow that there are 2 monitors for real-time applications, users may want to enable both of them simultaneously. Make the number of per-task monitor configurable. Default it to 2 for now.
--- include/linux/rv.h | 2 +- include/linux/sched.h | 8 +++----- kernel/trace/rv/Kconfig | 9 +++++++++ kernel/trace/rv/rv.c | 8 ++++---- 4 files changed, 17 insertions(+), 10 deletions(-)
include/linux/rv.h +1 -1
@@ -75,7 +75,7 @@ static inline bool rv_ltl_all_atoms_known(struct ltl_monitor *mon)* these are justified. */ #define RV_PER_TASK_MONITORS 1 -#define RV_PER_TASK_MONITOR_INIT (RV_PER_TASK_MONITORS) +#define RV_PER_TASK_MONITOR_INIT (CONFIG_RV_PER_TASK_MONITORS)union rv_task_monitor {struct da_monitor da_mon;
include/linux/sched.h +3 -5
@@ -1623,12 +1623,10 @@ struct task_struct {#ifdef CONFIG_RV /* -* Per-task RV monitor. Nowadays fixed in RV_PER_TASK_MONITORS. -* If we find justification for more monitors, we can think -* about adding more or developing a dynamic method. So far, -* none of these are justified. +* Per-task RV monitor, fixed in CONFIG_RV_PER_TASK_MONITORS. +* If memory becomes a concern, we can think about a dynamic method. */ -union rv_task_monitor rv[RV_PER_TASK_MONITORS ]; +union rv_task_monitor rv[CONFIG_RV_PER_TASK_MONITORS ];#endif #ifdef CONFIG_USER_EVENTS
kernel/trace/rv/Kconfig +9 -0
@@ -32,6 +32,15 @@ menuconfig RV For further information, see: Documentation/trace/rv/runtime-verification.rst +config RV_PER_TASK_MONITORS + int "Maximum number of per-task monitor" + depends on RV + range 1 8 + default 2 + help + This option configures the maximum number of per-task RV monitors that can run + simultaneously. + source "kernel/trace/rv/monitors/wip/Kconfig" source "kernel/trace/rv/monitors/wwnr/Kconfig" source "kernel/trace/rv/monitors/sched/Kconfig"
kernel/trace/rv/rv.c +4 -4
@@ -165,7 +165,7 @@ struct dentry *get_monitors_root(void)LIST_HEAD (rv_monitors_list);static int task_monitor_count; -static bool task_monitor_slots[RV_PER_TASK_MONITORS ]; +static bool task_monitor_slots[CONFIG_RV_PER_TASK_MONITORS ];int rv_get_task_monitor_slot (void ) {
@@ -173,12 +173,12 @@ int rv_get_task_monitor_slot(void)lockdep_assert_held (&rv_interface_lock); -if (task_monitor_count ==RV_PER_TASK_MONITORS ) +if (task_monitor_count ==CONFIG_RV_PER_TASK_MONITORS )return -EBUSY ; task_monitor_count++; -for (i =0 ; i <RV_PER_TASK_MONITORS ; i++) { +for (i =0 ; i <CONFIG_RV_PER_TASK_MONITORS ; i++) {if (task_monitor_slots[i] == false) { task_monitor_slots[i] = true;return i;
@@ -194,7 +194,7 @@ void rv_put_task_monitor_slot(int slot) {lockdep_assert_held (&rv_interface_lock); -if (slot <0 || slot >=RV_PER_TASK_MONITORS ) { +if (slot <0 || slot >=CONFIG_RV_PER_TASK_MONITORS ) {WARN_ONCE (1 ,"RV releasing an invalid slot!: %d\n" , slot);return ; }
Signature · 1 line
2.39.5
Re: [PATCH v2 03/22] rv: Let the reactors take care of buffers
In reply to Nam CaoQuoted 66 lines · Nam Cao
Each RV monitor has one static buffer to send to the reactors. If multiple
errors are detected simultaneously, the one buffer could be overwritten.Instead, leave it to the reactors to handle buffering.
Signed-off-by Nam Cao <[email protected]>---
Cc: Petr Mladek <[email protected]>
Cc: John Ogness <[email protected]>
Cc: Sergey Senozhatsky <[email protected]>
---
include/linux/panic.h | 3 +++ include/linux/printk.h | 5 ++++ include/linux/rv.h | 9 +++++-- include/rv/da_monitor.h | 45 +++++++----------------------- --
kernel/panic.c | 17 ++++++++---- kernel/printk/internal.h | 1 - kernel/trace/rv/reactor_panic.c | 8 ++++--kernel/trace/rv/reactor_printk.c| 8 ++++-- kernel/trace/rv/rv_reactors.c | 2 +-9 files changed, 50 insertions(+), 48 deletions(-)include/linux/panic.h +0
-0@@ -3,6 +3,7 @@ #define _LINUX_PANIC_H
#include <linux/compiler_attributes.h>
+#include <linux/stdarg.h>
#include <linux/types.h>
structpt_regs;include/linux/panic.h +2
-0@@ -10,6 +11,8 @@ struct pt_regs; extern long (*panic_blink)(int state); __printf(1, 2) void panic(const char *fmt, ...) __noreturn __cold; +__printf(1, 0) +void vpanic (const char *fmt,va_list args)__noreturn __cold ; void nmi_panic(struct pt_regs *regs, const char *msg); void check_panic_on_warn(const char *origin); extern void oops_enter(void);include/linux/printk.h +0
-0@@ -154,6 +154,7 @@ int vprintk_emit(int facility, int level,
asmlinkage__printf(1, 0)
intvprintk(const char *fmt, va_list args);
+__printf(1, 0) intvprintk_deferred(const char *fmt, va_list args);
asmlinkage__printf(1, 2)__cold
int_printk(const char *fmt, ...);include/linux/printk.h +4
-0@@ -213,6 +214,10 @@ int vprintk(const char *s, va_list args) { return 0; } +__printf(1, 0) int vprintk_deferred(const char *fmt, va_list args) +{ +return 0 ; +}
Quoted 3 lines
static inline
__printf(1, 2)__cold
int_printk(const char *s, ...)
{
From the RV perspective this patch looks really good to me, although you're doing a bit more than just RV here.
I hate to be the one telling you to split patches (22 is already scary as it is!) but probably the vpanic and vprintk_deferred belong in separate patches.
Feel free to mark the RV part (and also 1/22 2/22)
Thanks,
Gabriele
Quoted 300 lines
include/linux/rv.h +1
-1@@ -38,7 +38,7 @@ union rv_task_monitor { struct rv_reactor { const char *name; const char *description; -void (*react)(char *msg); + __printf(1, 2) void (*react)(const char *msg, ...); }; #endifinclude/linux/rv.h +1
-1@@ -50,7 +50,7 @@ struct rv_monitor { void (*disable)(void); void (*reset)(void); #ifdef CONFIG_RV_REACTORS -void (*react)(char *msg); + __printf(1, 2) void (*react)(const char *msg, ...); #endif };include/linux/rv.h +5
-0@@ -64,6 +64,11 @@ void rv_put_task_monitor_slot(int slot); bool rv_reacting_on(void); int rv_unregister_reactor(struct rv_reactor *reactor); int rv_register_reactor(struct rv_reactor *reactor); +#else +bool rv_reacting_on (void ) +{ +return false; +} #endif /* CONFIG_RV_REACTORS */
#endif /*CONFIG_RV*/include/rv/da_monitor.h +0
-0@@ -19,45 +19,22 @@ #ifdef CONFIG_RV_REACTORS
#define DECLARE_RV_REACTING_HELPERS(name,
type) \
-static char
REACT_MSG_##name[1024]; \
-\-static inline char *format_react_msg_##name(type
curr_state, type
event) \
-
{ \include/rv/da_monitor.h +0
-1- snprintf(REACT_MSG_##name,1024, \
include/rv/da_monitor.h +0
-1- "rv: monitor %s does not allow event %s on state%s\n", \
include/rv/da_monitor.h +0
-1-#name, \
include/rv/da_monitor.h +0
-1-model_get_event_name_##name(event), \
include/rv/da_monitor.h +0
-1-model_get_state_name_##name(curr_state)); \
include/rv/da_monitor.h +0
-1-return REACT_MSG_##name; \
-
} \
-\-static void cond_react_##name(char
*msg) \
+static void cond_react_##name(typecurr_state, type
event) \{ \include/rv/da_monitor.h +0
-1- if(rv_##name.react) \
-rv_##name.react(msg); \ - } \ - \-static bool
rv_reacting_on_##name(void) \
-
{ \include/rv/da_monitor.h +0
-1-return
rv_reacting_on(); \include/rv/da_monitor.h +1
-0+ if (!rv_reacting_on() ||!rv_##name.react) \
include/rv/da_monitor.h +1
-0+return ;\include/rv/da_monitor.h +1
-0+ rv_##name.react("rv: monitor %s does not allow event %s onstate %s\n", \
include/rv/da_monitor.h +1
-0+#name ,\include/rv/da_monitor.h +1
-0+ model_get_event_name_##name(event),\include/rv/da_monitor.h +1
-0+ model_get_state_name_##name(curr_state));\}
#else /*CONFIG_RV_REACTOR*/
#define DECLARE_RV_REACTING_HELPERS(name,
type) \
-static inline char *format_react_msg_##name(typecurr_state, type
event) \
-
{ \include/rv/da_monitor.h +0
-1-return NULL; \
-
} \
-\-static void cond_react_##name(char
*msg) \
+static void cond_react_##name(typecurr_state, type
event) \{ \ return; \ - } \ - \-static bool
rv_reacting_on_##name(void) \
-
{ \include/rv/da_monitor.h +0
-1-return 0; \
}
#endifinclude/rv/da_monitor.h +0
-0@@ -170,8 +147,7 @@ da_event_##name(struct da_monitor *da_mon, enum events_##name event) \return
true; \
}\ \include/rv/da_monitor.h +0
-1- if(rv_reacting_on_##name()) \
-cond_react_##name(format_react_msg_##name(curr_state, event)); \include/rv/da_monitor.h +1
-0+ cond_react_##name(curr_state,event); \
\ trace_error_##name(model_get_state_name_##name(curr_state), \
model_get_event_name_##name(event)); \include/rv/da_monitor.h +0
-0@@ -202,8 +178,7 @@ static inline bool da_event_##name(struct
da_monitor*da_mon, structtask_struct
return
true; \
}\ \include/rv/da_monitor.h +0
-1- if(rv_reacting_on_##name()) \
-cond_react_##name(format_react_msg_##name(curr_state, event)); \include/rv/da_monitor.h +1
-0+ cond_react_##name(curr_state,event); \
\trace_error_##name(tsk-
Quoted 1 line
pid, \
model_get_state_name_##name(curr_state), \kernel/panic.c +0
-0@@ -277,17 +277,16 @@ static void panic_other_cpus_shutdown(bool crash_kexec) }
/**
- * panic - halt the system
+ * vpanic - halt the system
* @fmt: The text string to print
*
* Display a message, then perform cleanups.
*
* This function never returns.
*/kernel/panic.c +1
-1-void panic (const char *fmt, ...) +void vpanic (const char *fmt,va_list args){
static char buf[1024];kernel/panic.c +0
-1-va_list args;long i,
i_next= 0, len;
int state = 0;
intold_cpu,this_cpu;kernel/panic.c +0
-0@@ -338,9 +337,7 @@ void panic(const char *fmt, ...)
console_verbose();
bust_spinlocks(1);kernel/panic.c +0
-1-va_start (args, fmt);len =
vscnprintf(buf, sizeof(buf), fmt, args);kernel/panic.c +0
-1-va_end (args);
if (len && buf[len - 1] == '\n')
buf[len - 1] = '\0';kernel/panic.c +1
-0@@ -477,7 +474,17 @@ void panic(const char *fmt, ...) mdelay(PANIC_TIMER_STEP); } } +EXPORT_SYMBOL (vpanic);
+/* Identical tovpanic(), except it takes variadic arguments instead ofva_list*/kernel/panic.c +8
-0+void panic (const char *fmt, ...) +{ +va_list args; + +va_start (args, fmt); +vpanic (fmt, args); +va_end (args); +}EXPORT_SYMBOL(panic);
#define TAINT_FLAG(taint,_c_true,_c_false,_module) \kernel/printk/internal.h +0
-0@@ -71,7 +71,6 @@ int vprintk_store(int facility, int level, const char *fmt, va_list args);
__printf(1, 0) intvprintk_default(const char *fmt, va_list args); -__printf(1, 0) intvprintk_deferred(const char *fmt, va_list args);
void__printk_safe_enter(void);
void__printk_safe_exit(void);kernel/trace/rv/reactor_panic.c +0
-0@@ -13,9 +13,13 @@ #include <linux/init.h> #include <linux/rv.h>kernel/trace/rv/reactor_panic.c +1
-1-static void rv_panic_reaction (char *msg) +static void rv_panic_reaction (const char *msg, ...){
kernel/trace/rv/reactor_panic.c +5
-1-panic (msg); +va_list args; + +va_start (args, msg); +vpanic (msg, args); +va_end (args);}
static structrv_reactorrv_panic= {kernel/trace/rv/reactor_printk.c +0
-0@@ -12,9 +12,13 @@ #include <linux/init.h> #include <linux/rv.h>kernel/trace/rv/reactor_printk.c +1
-1-static void rv_printk_reaction (char *msg) +static void rv_printk_reaction (const char *msg, ...){
kernel/trace/rv/reactor_printk.c +5
-1-printk_deferred (msg); +va_list args; + +va_start (args, msg); +vprintk_deferred (msg, args); +va_end (args);}
static structrv_reactorrv_printk= {kernel/trace/rv/rv_reactors.c +1
-1@@ -490,7 +490,7 @@ void reactor_cleanup_monitor(struct rv_monitor_def *mdef) /** Nop reactor register */ -static void rv_nop_reaction (char *msg) +static void rv_nop_reaction (const char *msg, ...) { }
Re: [PATCH v2 06/22] verification/dot2k: Remove __buff_to_string()
In reply to Nam CaoQuoted 75 lines · Nam Cao
str.join()can do what__buff_to_string()does. Therefore replace__buff_to_string()to make the scripts more pythonic.Signed-off-by Nam Cao <[email protected]>---
tools/verification/dot2/dot2/dot2k.py | 21 ++++++---------------1 file changed, 6 insertions(+), 15 deletions(-)tools/verification/dot2/dot2/dot2k.py +0
-0@@ -109,15 +109,6 @@ class dot2k(Dot2c): fd.close()return content
- def__buff_to_string(self, buff):
- string = ""tools/verification/dot2/dot2/dot2k.py +0
-7- - for line in buff: - string = string + line + "\n" - - # cut off the last \n - return string[:-1] -def
fill_monitor_type(self):
returnself.monitor_type.upper()tools/verification/dot2/dot2/dot2k.py +1
-1@@ -148,19 +139,19 @@ class dot2k(Dot2c): buff.append("\tda_%s_%s(%s%s);" % (handle, self.name, event, self.enum_suffix)); buff.append("}") buff.append("") - return self.__buff_to_string(buff) + return '\n'.join(buff)
deffill_tracepoint_attach_probe(self):
buff = []
for event in self.events:
buff.append("\trv_attach_trace_probe(\"%s\", /* XXX:
tracepoint */, handle_%s);" % (self.name, event))
- returnself.__buff_to_string(buff)
+ return '\n'.join(buff)
deffill_tracepoint_detach_helper(self):
buff = []
for event in self.events:
buff.append("\trv_detach_trace_probe(\"%s\", /* XXX:
tracepoint */, handle_%s);" % (self.name, event))
- returnself.__buff_to_string(buff)
+ return '\n'.join(buff)
deffill_main_c(self):
main_c= self.main_ctools/verification/dot2/dot2/dot2k.py +0
-0@@ -210,7 +201,7 @@ class dot2k(Dot2c): buff = self.fill_model_h_header() buff += self.format_model()
- returnself.__buff_to_string(buff)
+ return '\n'.join(buff)
deffill_monitor_class_type(self):
if self.monitor_type == "per_task":tools/verification/dot2/dot2/dot2k.py +1
-1@@ -242,7 +233,7 @@ class dot2k(Dot2c): tp_args_c = ", ".join([b for a,b in tp_args]) buff.append(" TP_PROTO(%s)," % tp_proto_c) buff.append(" TP_ARGS(%s)" % tp_args_c) - return self.__buff_to_string(buff) + return '\n'.join(buff)
deffill_monitor_deps(self):
buff = []tools/verification/dot2/dot2/dot2k.py +0
-0@@ -250,7 +241,7 @@ class dot2k(Dot2c):if self.parent:
Quoted 8 lines
buff.append(" depends on RV_MON_%s" %
self.parent.upper())
buff.append(" default y")
- returnself.__buff_to_string(buff)
+ return '\n'.join(buff)
deffill_trace_h(self):
trace_h= self.trace_h
Good one, I've been too lazy to do it. Thanks!
Re: [PATCH v2 05/22] verification/dot2k: Make a separate dot2k_templates/Kconfig_container
In reply to Nam CaoQuoted 63 lines · Nam Cao
A generated container's
Kconfighas an incorrect line:select
DA_MON_EVENTS_IMPLICITThis is due to container generation uses the same template
Kconfigfile as
deterministic automaton monitor.Therefore, make a separate
Kconfigtemplate for container which has only
the necessaries for container.Signed-off-by Nam Cao <[email protected]>---
Alternatively, we could also modify the Python scripts. I tried both and
this solution seems cleaner.
---
tools/verification/dot2/dot2/dot2k.py | 3 ++-tools/verification/dot2/dot2k_templates/Kconfig_container| 5 +++++2 files changed, 7 insertions(+), 1 deletion(-)create mode 100644
tools/verification/dot2/dot2k_templates/Kconfig_containertools/verification/dot2/dot2/dot2k.py +0
-0@@ -35,6 +35,7 @@ class dot2k(Dot2c):self.states = []
self.main_c =self.__read_file(self.monitor_templates_dir + "main_container.c")self.main_h =self.__read_file(self.monitor_templates_dir + "main_container.h")+ self.kconfig =self.__read_file(self.monitor_templates_dir + "Kconfig_container")else:
super().__init__(file_path,extra_params.get("model_name"))tools/verification/dot2/dot2/dot2k.py +0
-0@@ -44,7 +45,7 @@ class dot2k(Dot2c):self.monitor_type = MonitorType
self.main_c =self.__read_file(self.monitor_templates_dir + "main.c")self.trace_h =self.__read_file(self.monitor_templates_dir + "trace.h")
- self.kconfig =self.__read_file(self.monitor_templates_dir + "Kconfig")
+ self.kconfig =self.__read_file(self.monitor_templates_dir + "Kconfig")self.enum_suffix = "_%s" % self.name self.description =extra_params.get("description", self.name)or "auto-generated"
self.auto_patch =extra_params.get("auto_patch")diff --git a/tools/verification/dot2/dot2k_templates/Kconfig_container b/tools/verification/dot2/dot2k_templates/Kconfig_container new file mode 100644
index 000000000000..a606111949c2
tools/verification/dot2/dot2k_templates/Kconfig_container line 5
Quoted 5 lines
tools/verification/dot2/dot2k_templates/Kconfig_container new file +5
-0@@ -0,0 +1,5 @@ +config RV_MON_%%MODEL_NAME_UP%% + depends on RV + bool "%%MODEL_NAME%% monitor" + help + %%DESCRIPTION%%
Good catch
Re: [PATCH v2 07/22] verification/dot2k: Replace is_container() hack with subparsers
In reply to Nam CaoQuoted 10 lines · Nam Cao
dot2k is used for both generating deterministic automaton (DA) monitor and
generating container monitor.Generating DA monitor and generating container requires different parameters. This is implemented by peeking at sys.argv and check whether
"--container" is specified, and use that information to make some parameters optional or required.
Quoted 4 lines
This works, but is quite hacky and ugly.
Replace this hack with Python's built-in subparsers.
Yeah, that's much neater, thanks!
Quoted 114 lines
The old commands:
python3 dot2/dot2k -d wip.dot -t
per_cpu
python3 dot2/dot2k -n sched --containerare equivalent to the new commands:
python3 dot2/dot2k monitor -d wip.dot -t
per_cpupython3 dot2/dot2k container -n schedSigned-off-by Nam Cao <[email protected]>---
tools/verification/dot2/dot2/dot2k.py | 2 +- tools/verification/dot2/dot2k | 37 +++++++++++++++---------- --2 files changed, 21 insertions(+), 18 deletions(-)tools/verification/dot2/dot2/dot2k.py +0
-0@@ -19,7 +19,7 @@ class dot2k(Dot2c):
monitor_type= "per_cpu"
def__init__(self, file_path, MonitorType, extra_params={}):
- self.container =extra_params.get("container")+ self.container =extra_params.get("subcmd")== "container" self.parent =extra_params.get("parent")self.__fill_rv_templates_dir()tools/verification/dot2/dot2k +0
-0@@ -13,30 +13,33 @@ if __name__ == '__main__':import argparse
import sys
- defis_container():
- """Should work even before parsing the arguments""" - return "-c" in sys.argv or "--container" in sys.argv -
parser =argparse.ArgumentParser(description='transform .dot file into kernel rv monitor')
-parser.add_argument('-d', "--dot", dest="dot_file", required=not is_container())
- parser.add_argument('-t', "--monitor_type", dest="monitor_type", required=notis_container(),
- help=f"Available options: {', '.join(dot2k.monitor_types.keys())}")
-parser.add_argument('-n', "--model_name", dest="model_name", required=is_container())
parser.add_argument("-D", "--description", dest="description", required=False)
parser.add_argument("-a", "--auto_patch", dest="auto_patch", action="store_true", required=False, help="Patch the kernel in place") - parser.add_argument("-p", "--parent", dest="parent", - required=False, help="Create a monitor nested to parent")
- parser.add_argument("-c", "--container", dest="container", - action="store_true", required=False, - help="Create an empty monitor to be used as a container")tools/verification/dot2/dot2k +5
-0+ + subparsers = parser.add_subparsers(dest="subcmd", required=True) + + monitor_parser = subparsers.add_parser("monitor") + monitor_parser.add_argument('-n', "--model_name",dest="model_name")
+ monitor_parser.add_argument("-p", "--parent", dest="parent", + required=False, help="Create a monitor nested to parent")
+monitor_parser.add_argument('-d', "--dot", dest="dot_file")+ monitor_parser.add_argument('-t', "--monitor_type", dest="monitor_type",
+ help=f"Available options: {', '.join(dot2k.monitor_types.keys())}")
+
+container_parser=subparsers.add_parser("container")+container_parser.add_argument('-n', "--model_name", dest="model_name", required=True)
+
params =parser.parse_args()
- if notis_container():
-print("Opening and parsing the dot file %s" % params.dot_file)
try:
- monitor=dot2k(params.dot_file, params.monitor_type, vars(params))
+ if params.subcmd == "monitor":
+print("Opening and parsing the dot file %s" % params.dot_file)
+ monitor =dot2k(params.dot_file, params.monitor_type, vars(params))
+ else:
+ monitor =dot2k(None, None, vars(params))except Exception as e:
print('Error: '+ str(e))
print("Sorry : :-(")tools/verification/dot2/dot2k +0
-0@@ -45,7 +48,7 @@ if __name__ == '__main__':
print("Writing the monitor into the directory %s" % monitor.name)
monitor.print_files()
print("Almost done, checklist")
- if notis_container():
+ if params.subcmd == "monitor":
print(" - Edit the %s/%s.c to add the instrumentation" % (monitor.name, monitor.name))print(monitor.fill_tracepoint_tooltip()) print(monitor.fill_makefile_tooltip())
Gabriele Monaco
maintainerRe: [PATCH v2 04/22] verification/dot2k: Make it possible to invoke dot2k without installation
In reply to Nam CaoQuoted 9 lines · Nam Cao
Without installation, dot2k doesn't work:
namcao@yellow:~/linux/tools/verification$ python3 ./dot2/dot2k Traceback (most recent call last): File "/home/namcao/linux/tools/verification/./dot2/dot2k", line 12, in <module> from dot2.dot2k import dot2k ModuleNotFoundError: No module named 'dot2'
Quoted 7 lines
Installing dot2k to the system is not always desirable. Sometimes it is not
even possible (e.g. no root permission).Restructure the files to make it work without installing.
Signed-off-by Nam Cao <[email protected]>
Mmh, the workflow
pushd tools/verification
...
popd
has always been working in my case, but probably that's because I have PYTHONPATH="." , not sure how much of a good practice that is.
Anyway, since you're already moving things around in 9/22 ("verification/dot2k: Prepare the frontend for LTL inclusion"), does it make sense to keep the commits separated? Or you could directly move to rvgen here and just add the ltl related changes in the later commit.
Also, after your changes on my system, I can run the script from the kernel directory too, which is much better than having to cd to tools/verification .
If that's something portable, I'd change the default definition of monitor_templates_dir and allow the user to run the script only from the kernel root.
What do you think?
Thanks,
Gabriele
Quoted 50 lines
---
tools/verification/dot2/Makefile | 6 +++---tools/verification/dot2/{=>dot2}/automata.py| 0tools/verification/dot2/{=> dot2}/dot2c.py | 0tools/verification/dot2/{=> dot2}/dot2k.py | 04 files changed, 3 insertions(+), 3 deletions(-)rename
tools/verification/dot2/{=>dot2}/automata.py(100%) renametools/verification/dot2/{=>dot2}/dot2c.py(100%) renametools/verification/dot2/{=>dot2}/dot2k.py(100%)tools/verification/dot2/Makefile +0
-0@@ -16,10 +16,10 @@ clean:
.PHONY: install
install:tools/verification/dot2/Makefile +0
-1- $(INSTALL) automata.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/automata.py
tools/verification/dot2/Makefile +0
-1- $(INSTALL) dot2c.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/dot2c.py
tools/verification/dot2/Makefile +1
-0+ $(INSTALL) dot2/automata.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/automata.py
tools/verification/dot2/Makefile +1
-0+ $(INSTALL) dot2/dot2c.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/dot2c.py
$(INSTALL) dot2c -D -m 755 $(DESTDIR)$(bindir)/tools/verification/dot2/Makefile +0
-1- $(INSTALL) dot2k.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/dot2k.py
tools/verification/dot2/Makefile +1
-0+ $(INSTALL) dot2/dot2k.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/dot2k.py
$(INSTALL) dot2k -D -m 755 $(DESTDIR)$(bindir)/
mkdir -p ${miscdir}/tools/verification/dot2/dot2/automata.py renamed from tools/verification/dot2/automata.py +0
-0tools/verification/dot2/dot2/dot2c.py renamed from tools/verification/dot2/dot2c.py +0
-0tools/verification/dot2/dot2/dot2k.py renamed from tools/verification/dot2/dot2k.py +0
-0
Re: [PATCH v2 10/22] Documentation/rv: Prepare monitor synthesis document for LTL inclusion
In reply to Nam CaoQuoted 49 lines · Nam Cao
Monitor synthesis from deterministic automaton and linear temporal logic
have a lot in common. Therefore a single document should describe both.Change
da_monitor_synthesis.rsttomonitor_synthesis.rst. LTL monitor synthesis will be added to this file by a follow-up commit.This makes the diff far easier to read. If renaming and adding LTL info is
done in a single commit, git wouldn't recognize it as a rename, but a file
removal and a file addition.While at it, correct the old dot2k commands to the new rvgen commands.
Signed-off-by Nam Cao <[email protected]>---
Documentation/trace/rv/index.rst | 2 +-...or_synthesis.rst=>monitor_synthesis.rst} | 20 +++++++++-------- --2 files changed, 11 insertions(+), 11 deletions(-)rename
Documentation/trace/rv/{da_monitor_synthesis.rst=>monitor_synthesis.rst} (92%)Documentation/trace/rv/index.rst +0
-0@@ -8,7 +8,7 @@ Runtime Verification
runtime-verification.rst
deterministic_automata.rst
-da_monitor_synthesis.rst
+monitor_synthesis.rst
da_monitor_instrumentation.rst
monitor_wip.rst
monitor_wwnr.rstDocumentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +0
-0
Documentation/trace/rv/monitor_synthesis.rst line 2
Quoted 4 lines
Documentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +2
-2@@ -1,5 +1,5 @@ -Deterministic Automata Monitor Synthesis -======================================== +Runtime verification Monitor Synthesis +======================================
+Runtime Verification Monitor Synthesis
The title is capitalised here.
The rest looks good, thanks.
Quoted 74 lines
The starting point for the application of runtime verification (RV) techniques
is the *specification* or *modeling* of the desired (or undesired) behaviorDocumentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +0
-0@@ -36,24 +36,24 @@ below::| +----> panic ? +-------> <user-specified>
Documentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +1
-1-DA monitor synthesis +RV monitor synthesis--------------------
The synthesis of automata-based models into the Linux *RV monitor* abstraction
-is automated by the dot2k tool and therv/da_monitor.hheader file that
+is automated by the rvgen tool and therv/da_monitor.hheader file that
contains a set of macros that automatically generate the monitor's code.Documentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +1
-1-dot2k +rvgen-----
-The dot2k utility leverages dot2c by converting an automaton model in
+The rvgen utility leverages dot2c by converting an automaton model in
the DOT format into the C representation [1] and creating the skeleton of
a kernel monitor in C.
For example, it is possible to transform the wip.dot model present in
[1] into a per-cpu monitor with the following command::
- $ dot2k -d wip.dot -tper_cpu
+ $ rvgen monitor -c da -s wip.dot -tper_cpu
This will create a directory named wip/ with the following files:Documentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +0
-0@@ -87,7 +87,7 @@ the second for monitors with per-cpu instances, andthe third with per-task
instances.
In all cases, the 'name' argument is a string that identifies the monitor, and
-the 'type' argument is the data type used by dot2k on the representation of
+the 'type' argument is the data type used by rvgen on the representation of
the model in C.
For example, the wip model with two states and three events can beDocumentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +0
-0@@ -134,7 +134,7 @@ Final remarks-------------
With the monitor synthesis in place using therv/da_monitor.handDocumentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +1
-1-dot2k, the developer's work should be limited to the instrumentation +rvgen, the developer's work should be limited to the instrumentationof the system, increasing the confidence in the overall approach.
[1] For details about deterministic automata format and the translationDocumentation/trace/rv/monitor_synthesis.rst renamed from Documentation/trace/rv/da_monitor_synthesis.rst +0
-0@@ -142,6 +142,6 @@ from one representation to another, see::
Documentation/trace/rv/deterministic_automata.rst
-[2] dot2k appends the monitor's name suffix to the events enums to +[2] rvgen appends the monitor's name suffix to the events enums to avoid conflicting variables when exporting the globalvmlinux.huse by BPF programs.
Re: [PATCH v2 08/22] rv: rename CONFIG_DA_MON_EVENTS to CONFIG_RV_MON_EVENTS
In reply to Nam CaoQuoted 9 lines · Nam Cao
CONFIG_DA_MON_EVENTSis not specific to deterministic automaton. It could
be used for other monitor types. Therefore rename it toCONFIG_RV_MON_EVENTS.This prepares for the introduction of linear temporal logic monitor.
Signed-off-by Nam Cao <[email protected]>---
Gabriele Monaco
maintainerRe: [PATCH v2 13/22] rv: Add support for LTL monitors
In reply to Nam CaoQuoted 95 lines · Nam Cao
While attempting to implement DA monitors for some complex specifications,
deterministic automaton is found to be inappropriate as the specification
language. The automaton is complicated, hard to understand, and error-prone.For these cases, linear temporal logic is more suitable as the specification language.
Add support for linear temporal logic runtime verification monitor.
For all the details, see the documentations added by this commit.
Signed-off-by Nam Cao <[email protected]>---
Documentation/trace/rv/index.rst | 1 + .../trace/rv/linear_temporal_logic.rst | 97 +++ Documentation/trace/rv/monitor_synthesis.rst | 141 ++++- include/linux/rv.h | 56 +- include/rv/ltl_monitor.h | 184 ++++++ kernel/fork.c | 5 +- kernel/trace/rv/Kconfig | 7 + kernel/trace/rv/rv_trace.h | 47 ++ tools/verification/rvgen/.gitignore | 3 + tools/verification/rvgen/Makefile | 2 + tools/verification/rvgen/__main__.py | 3 +- tools/verification/rvgen/rvgen/ltl2ba.py | 552
++++++++++++++++++
tools/verification/rvgen/rvgen/ltl2k.py | 242 ++++++++.../verification/rvgen/templates/ltl2k/main.c| 102 ++++ .../rvgen/templates/ltl2k/trace.h | 14 +15 files changed, 1431 insertions(+), 25 deletions(-)create mode 100644
Documentation/trace/rv/linear_temporal_logic.rstcreate mode 100644include/rv/ltl_monitor.h
create mode 100644tools/verification/rvgen/.gitignorecreate mode 100644tools/verification/rvgen/rvgen/ltl2ba.pycreate mode 100644tools/verification/rvgen/rvgen/ltl2k.pycreate mode 100644tools/verification/rvgen/templates/ltl2k/main.ccreate mode 100644tools/verification/rvgen/templates/ltl2k/trace.hDocumentation/trace/rv/index.rst +0
-0include/linux/rv.h +0
-0@@ -10,6 +10,10 @@ #define MAX_DA_NAME_LEN 32
#ifdefCONFIG_RVinclude/linux/rv.h +4
-0+#include <linux/bitops.h> +#include <linux/types.h> +#include <linux/array_size.h> +/*
* Deterministic automaton per-object variables.
*/include/linux/rv.h +0
-0@@ -18,6 +22,52 @@ struct da_monitor { unsigned int curr_state; };
+/*
+ * In the future, if the number of atomic propositions or the size of Buchi automaton is larger, we
+ * can switch to dynamic allocation. For now, the code is simpler this way.
+ */include/linux/rv.h +5
-0+#define RV_MAX_LTL_ATOM 32 +#define RV_MAX_BA_STATES 32 + +/** +* struct ltl_monitor - A linear temporal logic runtime verification monitor
+ * @states: States in the Buchi automaton. As Buchi automaton is
a
+ * non-deterministic state machine, the monitor can be
in multiple states
+ * simultaneously. This is a bitmask of all possible
states.
+ * If this is zero, that means either:
+ * - The monitor has not started yet (e.g. because
not all atomic propositions are
+ * known).
+ * - there is no possible state to be in. In other
words, a violation of the
+ * LTL property is detected.
+ * @atoms: The values of atomic propositions.
+ * @unknown_atoms: Atomic propositions which are still unknown.
+ */
include/linux/rv.h struct da_monitor { · line 51
Quoted 7 lines
include/linux/rv.h +7
-0+struct ltl_monitor { +#ifdef CONFIG_RV_LTL_MONITOR + DECLARE_BITMAP(states, RV_MAX_BA_STATES); + DECLARE_BITMAP(atoms, RV_MAX_LTL_ATOM); + DECLARE_BITMAP(unknown_atoms, RV_MAX_LTL_ATOM); +#endif +};
Mmh, we have a lot of those ifdefs in quite inappropriate places, but I think we can do better than this.
What about something like:
#ifdef CONFIG_RV_LTL_MONITOR
struct ltl_monitor {
DECLARE_BITMAP(states, RV_MAX_BA_STATES);
DECLARE_BITMAP(atoms, RV_MAX_LTL_ATOM);
DECLARE_BITMAP(unknown_atoms, RV_MAX_LTL_ATOM);
};static inline bool rv_ltl_valid_state(struct ltl_monitor *mon)
{
...
}static inline bool rv_ltl_all_atoms_known(struct ltl_monitor *mon)
{
...
}#else
/*
* Leave the struct empty not to use up space
* In a later patch we could do the same for DAs.. */
struct ltl_monitor { };
#endif
include/rv/ltl_monitor.h
Quoted 42 lines
include/linux/rv.h +19
-0+ +static inline bool rv_ltl_valid_state (struct ltl_monitor *mon) +{ +for (int i =0 ; i <ARRAY_SIZE (mon->states); ++i) { +if (mon->states[i]) +return true; + } +return false; +} + +static inline bool rv_ltl_all_atoms_known (struct ltl_monitor *mon) +{ +for (int i =0 ; i <ARRAY_SIZE (mon->unknown_atoms); ++i) { +if (mon->unknown_atoms[i]) +return false; + } +return true; +} +/*
* Per-task RV monitors count. Nowadays fixed inRV_PER_TASK_MONITORS.
* If we find justification for more monitors, we can think aboutinclude/linux/rv.h +0
-0@@ -27,11 +77,9 @@ struct da_monitor { #define RV_PER_TASK_MONITORS 1 #define RV_PER_TASK_MONITOR_INIT (RV_PER_TASK_MONITORS)
-/*
- * Futher monitor types are expected, so make this a union.
- */
unionrv_task_monitor{include/linux/rv.h +2
-1-struct da_monitor da_mon; +struct da_monitor da_mon; +struct ltl_monitor ltl_mon;};
#ifdefCONFIG_RV_REACTORSinclude/rv/ltl_monitor.h new file +0
-0
You hate macros don't you? :)
Anyway I really like your approach, very neat.
Quoted 45 lines
include/rv/ltl_monitor.h new file +3
-0@@ -0,0 +1,184 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/** +* This file must be combined with the $(MODEL_NAME).h file generated by
+ *tools/verification/rvgen.
+ */include/rv/ltl_monitor.h new file +11
-0+ +#include <linux/args.h> +#include <linux/rv.h> +#include <linux/stringify.h> +#include <linux/seq_buf.h> +#include <rv/instrumentation.h> +#include <trace/events/task.h> +#include <trace/events/sched.h> + +#ifndef MONITOR_NAME +#error "MONITOR_NAME macro is not defined. Did you include$(MODEL_NAME).h generated by rvgen?"
include/rv/ltl_monitor.h new file +11
-0+#endif + +#ifdef CONFIG_RV_REACTORS +#define RV_MONITOR_NAME CONCATENATE(rv_, MONITOR_NAME) +static struct rv_monitor RV_MONITOR_NAME ; + +static void rv_cond_react (struct task_struct *task) +{ +if (!rv_reacting_on () || !RV_MONITOR_NAME .react) +return ; + RV_MONITOR_NAME.react("rv: "__stringify(MONITOR_NAME)":%s[%d]: violation detected\n",
include/rv/ltl_monitor.h new file +11
-0+ task->comm, task->pid); +} +#else +static void rv_cond_react (struct task_struct *task) +{ +} +#endif + +static int ltl_monitor_slot =RV_PER_TASK_MONITOR_INIT ; + +static void ltl_atoms_fetch(struct task_struct *task, struct
ltl_monitor*mon);
+static voidltl_atoms_init(struct task_struct *task, struct ltl_monitor *mon, bool task_creation);
include/rv/ltl_monitor.h line 44
Quoted 5 lines
include/rv/ltl_monitor.h new file +5
-0+ +static struct ltl_monitor *ltl_get_monitor (struct task_struct *task) +{ +return &task->rv[ltl_monitor_slot].ltl_mon; +}
This means ltl monitors only support per-task, right?
It shouldn't take much effort putting an ifdef chain here and defining e.g. PER_CPU in the header file to choose a different get_monitor. Or directly an ltl_monitor_implicit.h
I think this patch is ready without it, just trying to brainstorm how we could potentially extend this.
I need more time to play with these, but it looks promising.
Thanks,
Gabriele
Re: [PATCH v2 22/22] rv: Allow to configure the number of per-task monitor
In reply to Nam CaoQuoted 19 lines · Nam Cao
Now that there are 2 monitors for real-time applications, users may want to
enable both of them simultaneously. Make the number of per-task monitor
configurable. Default it to 2 for now.Signed-off-by Nam Cao <[email protected]>---
include/linux/rv.h | 2 +-
include/linux/sched.h | 8 +++-----
kernel/trace/rv/Kconfig | 9 +++++++++
kernel/trace/rv/rv.c | 8 ++++----4 files changed, 17 insertions(+), 10 deletions(-)include/linux/rv.h +0
-0
include/linux/rv.h static inline bool rv_ltl_all_atoms_known(struct · line 78
Quoted 4 lines
include/linux/rv.h +0
-0@@ -75,7 +75,7 @@ static inline bool rv_ltl_all_atoms_known(structltl_monitor *mon) * these are justified. */ #define RV_PER_TASK_MONITORS 1
We could get rid of RV_PER_TASK_MONITORS too I guess.
Rest looks good, thanks.
Quoted 89 lines
include/linux/rv.h +1
-1-#define RV_PER_TASK_MONITOR_INIT (RV_PER_TASK_MONITORS) +#define RV_PER_TASK_MONITOR_INIT (CONFIG_RV_PER_TASK_MONITORS)
unionrv_task_monitor{
structda_monitorda_mon;include/linux/sched.h +0
-0@@ -1623,12 +1623,10 @@ struct task_struct {
#ifdefCONFIG_RV
/*include/linux/sched.h +0
-1-* Per-task RV monitor. Nowadays fixed in
RV_PER_TASK_MONITORS.include/linux/sched.h +1
-3-* If we find justification for more monitors, we can think -* about adding more or developing a dynamic method. So far, -* none of these are justified. +* Per-task RV monitor, fixed in
CONFIG_RV_PER_TASK_MONITORS.include/linux/sched.h +1
-0+* If memory becomes a concern, we can think about a dynamic method.
*/include/linux/sched.h +1
-1-union rv_task_monitor rv[RV_PER_TASK_MONITORS ]; + union
rv_task_monitorrv[CONFIG_RV_PER_TASK_MONITORS];
#endif
#ifdefCONFIG_USER_EVENTSkernel/trace/rv/Kconfig +0
-0@@ -32,6 +32,15 @@ menuconfig RVFor further information, see:
Documentation/trace/rv/runtime-verification.rstkernel/trace/rv/Kconfig +7
-0+config RV_PER_TASK_MONITORS + int "Maximum number of per-task monitor" + depends on RV + range 1 8 + default 2 + help + This option configures the maximum number of per-task RVmonitors that can run
kernel/trace/rv/Kconfig +2
-0+ simultaneously. +source "
kernel/trace/rv/monitors/wip/Kconfig"
source "kernel/trace/rv/monitors/wwnr/Kconfig"
source "kernel/trace/rv/monitors/sched/Kconfig"kernel/trace/rv/rv.c +0
-0@@ -165,7 +165,7 @@ struct dentry *get_monitors_root(void) LIST_HEAD(rv_monitors_list);
static inttask_monitor_count;kernel/trace/rv/rv.c +1
-1-static bool task_monitor_slots[RV_PER_TASK_MONITORS ]; +static bool task_monitor_slots[CONFIG_RV_PER_TASK_MONITORS ];
intrv_get_task_monitor_slot(void)
{kernel/trace/rv/rv.c +0
-0@@ -173,12 +173,12 @@ int rv_get_task_monitor_slot(void)
lockdep_assert_held(&rv_interface_lock);kernel/trace/rv/rv.c +1
-1-if (task_monitor_count ==RV_PER_TASK_MONITORS ) +if (task_monitor_count ==CONFIG_RV_PER_TASK_MONITORS )return
-EBUSY;
task_monitor_count++;kernel/trace/rv/rv.c +1
-1-for (i =0 ; i <RV_PER_TASK_MONITORS ; i++) { +for (i =0 ; i <CONFIG_RV_PER_TASK_MONITORS ; i++) {if (task_monitor_slots[i] == false) { task_monitor_slots[i] = true; return i;
kernel/trace/rv/rv.c +0
-0@@ -194,7 +194,7 @@ void rv_put_task_monitor_slot(int slot) { lockdep_assert_held(&rv_interface_lock);kernel/trace/rv/rv.c +1
-1-if (slot <0 || slot >=RV_PER_TASK_MONITORS ) { +if (slot <0 || slot >=CONFIG_RV_PER_TASK_MONITORS ) {
WARN_ONCE(1, "RV releasing an invalid slot!: %d\n", slot);
return;
}
Re: [PATCH v2 04/22] verification/dot2k: Make it possible to invoke dot2k without installation
In reply to Gabriele MonacoQuoted 20 lines · Gabriele Monaco
Quoted 9 lines · Nam Cao
Without installation, dot2k doesn't work:
namcao@yellow:~/linux/tools/verification$ python3 ./dot2/dot2k Traceback (most recent call last): File "/home/namcao/linux/tools/verification/./dot2/dot2k", line 12, in <module> from dot2.dot2k import dot2k ModuleNotFoundError: No module named 'dot2'Quoted 7 lines
Installing dot2k to the system is not always desirable. Sometimes it is not
even possible (e.g. no root permission).Restructure the files to make it work without installing.
Signed-off-by Nam Cao <[email protected]>Mmh, the workflow
Quoted 7 lines
pushd
tools/verification
...
popdhas always been working in my case, but probably that's because I have PYTHONPATH="." , not sure how much of a good practice that is.
Ahh, PYTHONPATH is the trick. But that shouldn't be required. The scripts should work out of the box without any environment setup.
Quoted 4 lines
Anyway, since you're already moving things around in 9/22 ("verification/dot2k: Prepare the frontend for LTL inclusion"), does it make sense to keep the commits separated? Or you could directly move to rvgen here and just add the ltl related changes in the later commit.
Yes, it makes sense to move them to rvgen here.
Quoted 8 lines
Also, after your changes on my system, I can run the script from the kernel directory too, which is much better than having to cd to
tools/verification.
If that's something portable, I'd change the default definition ofmonitor_templates_dirand allow the user to run the script only from the kernel root.What do you think?
I actually prefer running the script from tools/verification. We can allow user to run from anywhere, with something like:
class dot2k(Monitor, Dot2c):
- monitor_templates_dir = "rvgen/templates/dot2k"
+ monitor_templates_dir = os.path.join(os.path.dirname(__file__), "../../rvgen/templates/dot2k")
Best regards,
Nam
Re: [PATCH v2 13/22] rv: Add support for LTL monitors
In reply to Gabriele MonacoQuoted 34 lines · Gabriele Monaco
include/linux/rv.h struct da_monitor { · line 51
Quoted 7 lines · Nam Cao
include/linux/rv.h +7
-0+struct ltl_monitor { +#ifdef CONFIG_RV_LTL_MONITOR + DECLARE_BITMAP(states, RV_MAX_BA_STATES); + DECLARE_BITMAP(atoms, RV_MAX_LTL_ATOM); + DECLARE_BITMAP(unknown_atoms, RV_MAX_LTL_ATOM); +#endif +};Mmh, we have a lot of those ifdefs in quite inappropriate places, but I think we can do better than this.
What about something like:
#ifdef
CONFIG_RV_LTL_MONITORstruct ltl_monitor { DECLARE_BITMAP(states, RV_MAX_BA_STATES); DECLARE_BITMAP(atoms, RV_MAX_LTL_ATOM); DECLARE_BITMAP(unknown_atoms, RV_MAX_LTL_ATOM); };static inline bool
rv_ltl_valid_state(struct ltl_monitor *mon){ ... }static inline bool
rv_ltl_all_atoms_known(struct ltl_monitor *mon){ ... }#else
Quoted 7 lines
/*
* Leave the struct empty not to use up space
* In a later patch we could do the same for DAs.. */
structltl_monitor{ };#endif
I have no preference for either, so sure!
Quoted 7 lines
include/rv/ltl_monitor.h
Quoted 5 lines
include/rv/ltl_monitor.h new file +0
-0You hate macros don't you? :)
YES!
Quoted 1 line
Anyway I really like your approach, very neat.
Thank you! I'm very happy to have found a way to escape the macros.
Quoted 6 lines
include/rv/ltl_monitor.h line 44
Quoted 4 lines
include/rv/ltl_monitor.h new file +4
-0+static struct ltl_monitor *ltl_get_monitor (struct task_struct *task) +{ +return &task->rv[ltl_monitor_slot].ltl_mon; +}This means ltl monitors only support per-task, right?
Yes.
Quoted 3 lines
It shouldn't take much effort putting an ifdef chain here and defining e.g.
PER_CPUin the header file to choose a differentget_monitor. Or directly anltl_monitor_implicit.h
Yes, either can work.
Quoted 4 lines
I think this patch is ready without it, just trying to brainstorm how we could potentially extend this.
I need more time to play with these, but it looks promising.
Thank you,
Nam
Gabriele Monaco
maintainerRe: [PATCH v2 04/22] verification/dot2k: Make it possible to invoke dot2k without installation
In reply to Nam CaoQuoted 57 lines · Nam Cao
Quoted 22 lines · Gabriele Monaco
Quoted 10 lines · Nam Cao
Without installation, dot2k doesn't work:
namcao@yellow:~/linux/tools/verification$ python3 ./dot2/dot2k Traceback (most recent call last): File "/home/namcao/linux/tools/verification/./dot2/dot2k", line 12, in <module> from dot2.dot2k import dot2k ModuleNotFoundError: No module named 'dot2'Quoted 8 lines
Installing dot2k to the system is not always desirable. Sometimes it
is not
even possible (e.g. no root permission).Restructure the files to make it work without installing.
Signed-off-by Nam Cao <[email protected]>Mmh, the workflow
Quoted 8 lines
pushd
tools/verification
...
popdhas always been working in my case, but probably that's because I have
PYTHONPATH="." , not sure how much of a good practice that is.Ahh, PYTHONPATH is the trick. But that shouldn't be required. The scripts
should work out of the box without any environment setup.Quoted 7 lines
Anyway, since you're already moving things around in 9/22 ("verification/dot2k: Prepare the frontend for LTL inclusion"), does it
make sense to keep the commits separated? Or you could directly move to
rvgen here and just add the ltl related changes in the later commit.Yes, it makes sense to move them to rvgen here.
Quoted 10 lines
Also, after your changes on my system, I can run the script from the
kernel directory too, which is much better than having to cd totools/verification.
If that's something portable, I'd change the default definition ofmonitor_templates_dirand allow the user to run the script only from
the kernel root.What do you think?
Quoted 8 lines
I actually prefer running the script from
tools/verification. We can allow
user to run from anywhere, with something like:class
dot2k(Monitor, Dot2c):
-monitor_templates_dir= "rvgen/templates/dot2k"
+monitor_templates_dir=os.path.join(os.path.dirname(__file__), "../../rvgen/templates/dot2k")
That looks like a good option!
Thanks,
Gabriele
Re: [PATCH v2 03/22] rv: Let the reactors take care of buffers
In reply to Nam CaoQuoted 5 lines · Nam Cao
Each RV monitor has one static buffer to send to the reactors. If multiple errors are detected simultaneously, the one buffer could be overwritten.
Instead, leave it to the reactors to handle buffering.
Quoted 10 lines
include/linux/panic.h | 3 +++ include/linux/printk.h | 5 ++++ include/linux/rv.h | 9 +++++-- include/rv/da_monitor.h | 45 +++++++------------------------- kernel/panic.c | 17 ++++++++---- kernel/printk/internal.h | 1 - kernel/trace/rv/reactor_panic.c | 8 ++++-- kernel/trace/rv/reactor_printk.c | 8 ++++-- kernel/trace/rv/rv_reactors.c | 2 +- 9 files changed, 50 insertions(+), 48 deletions(-)
For the changes in the printk and panic code:
I have just briefly looked at the changes in the rv code. I wonder if a __printf(1, 2) declaration might be needed in the printk and panic reactors code, see below.
Quoted 23 lines
include/linux/rv.h +2
-2@@ -38,7 +38,7 @@ union rv_task_monitor {struct rv_reactor {const char *name;const char *description; -void (*react)(char *msg); + __printf(1, 2) void (*react)(const char *msg, ...); };#endif @@ -50,7 +50,7 @@ struct rv_monitor {void (*disable)(void );void (*reset)(void );#ifdef CONFIG_RV_REACTORS -void (*react)(char *msg); + __printf(1, 2) void (*react)(const char *msg, ...);#endif };
kernel/trace/rv/reactor_printk.c line 15
Quoted 5 lines
kernel/trace/rv/reactor_printk.c +1
-1@@ -12,9 +12,13 @@#include <linux/init.h> #include <linux/rv.h> -static void rv_printk_reaction (char *msg) +static void rv_printk_reaction (const char *msg, ...)
I wonder whether "make W=1 kernel/trace/rv/reactor_printk.o" would start complaining about that this function is a candidate for ‘gnu_printf’ format attribute.
I am not sure. Maybe it is enough that this function is later assigned to the .react callback in struct rv_reactor.
I wanted to tried it myself. But I was not able to compile the code in linux-next. I got something like:
./include/linux/rv.h: In function ‘rv_ltl_valid_state’:./include/linux/rv.h:55:43: error: ‘struct ltl_monitor’ has no member named ‘states’
55 | for (int i = 0; i < ARRAY_SIZE(mon->states); ++i) {
| ^~
...
I am actually not sure against which tree I should apply this patchset. It did apply on linux-next after skipping the 1st patch.
But it does not compile there.
And there are more conflicts when I tried to apply it on Linus' master.
kernel/trace/rv/reactor_printk.c line 22
Quoted 8 lines
kernel/trace/rv/reactor_printk.c +5
-1{ -printk_deferred (msg); +va_list args; + +va_start (args, msg); +vprintk_deferred (msg, args); +va_end (args); }
The __printf statement might be missing also in the other two reactors (panic, nop).
Best Regards,
Petr
Re: [PATCH v2 03/22] rv: Let the reactors take care of buffers
Quoted 7 lines · Petr Mladek
kernel/trace/rv/reactor_printk.c line 15
Quoted 2 lines · Nam Cao
kernel/trace/rv/reactor_printk.c +1
-1-static void rv_printk_reaction (char *msg) +static void rv_printk_reaction (const char *msg, ...)I wonder whether "make W=1
kernel/trace/rv/reactor_printk.o" would start complaining about that this function is a candidate for ‘gnu_printf’ format attribute.
I checked, it does. Thanks for pointing it out.
Quoted 10 lines
I am not sure. Maybe it is enough that this function is later assigned to the .react callback in struct
rv_reactor.I wanted to tried it myself. But I was not able to compile the code in linux-next. I got something like:
./include/linux/rv.h: In function ‘rv_ltl_valid_state’:./include/linux/rv.h:55:43: error: ‘struct ltl_monitor’ has no member named ‘states’
55 | for (int i = 0; i <ARRAY_SIZE(mon->states); ++i) {
| ^~
This is a problem with the series. For now, you could "fix" this error with CONFIG_RV_MON_RTAPP=y. I will fix it up properly in the next version.
Quoted 5 lines
...
I am actually not sure against which tree I should apply this patchset. It did apply on linux-next after skipping the 1st patch.
But it does not compile there.
linux-next is supposed to be fine. It doesn't build due to a problem introduced by this series.
Quoted 2 lines
The
__printfstatement might be missing also in the other two reactors (panic, nop).
Yes. Will be fixed.
Thanks for the review!
Nam
Gabriele Monaco
maintainerRe: [PATCH v2 19/22] rv: Add rtapp_pagefault monitor
In reply to Nam CaoQuoted 161 lines · Nam Cao
Userspace real-time applications may have design flaws that they raise
page faults in real-time threads, and thus have unexpected latencies.Add an linear temporal logic monitor to detect this scenario.
Signed-off-by Nam Cao <[email protected]>---
Cc: Catalin Marinas <[email protected]>
Cc: Will Deacon <[email protected]>
Cc: Paul Walmsley <[email protected]>
Cc: Palmer Dabbelt <[email protected]>
Cc: Albert Ou <[email protected]>
Cc: Alexandre Ghiti <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Borislav Petkov <[email protected]>
Cc: Dave Hansen <[email protected]>
Cc: [email protected]
Cc: H. Peter Anvin <[email protected]>
Cc: Andy Lutomirski <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: [email protected]
Cc: [email protected]
---
kernel/trace/rv/Kconfig | 1 + kernel/trace/rv/Makefile | 1 + kernel/trace/rv/monitors/pagefault/Kconfig | 11 +++ .../trace/rv/monitors/pagefault/pagefault.c | 83
+++++++++++++++++++
.../trace/rv/monitors/pagefault/pagefault.h | 57 +++++++++++++ .../rv/monitors/pagefault/pagefault_trace.h | 14 ++++ kernel/trace/rv/rv_trace.h | 1 +tools/verification/models/rtapp/pagefault.ltl| 1 +8 files changed, 169 insertions(+)create mode 100644
kernel/trace/rv/monitors/pagefault/Kconfigcreate mode 100644kernel/trace/rv/monitors/pagefault/pagefault.ccreate mode 100644kernel/trace/rv/monitors/pagefault/pagefault.hcreate mode 100644kernel/trace/rv/monitors/pagefault/pagefault_trace.hcreate mode 100644tools/verification/models/rtapp/pagefault.ltlkernel/trace/rv/Kconfig +0
-0@@ -42,6 +42,7 @@ source "kernel/trace/rv/monitors/scpd/Kconfig"source "
kernel/trace/rv/monitors/snep/Kconfig" source "kernel/trace/rv/monitors/sncid/Kconfig" source "kernel/trace/rv/monitors/rtapp/Kconfig" +source "kernel/trace/rv/monitors/pagefault/Kconfig" # Add new monitors here
configRV_REACTORSkernel/trace/rv/Makefile +0
-0@@ -13,6 +13,7 @@ obj-$(CONFIG_RV_MON_SCPD) += monitors/scpd/scpd.oobj-$(CONFIG_RV_MON_SNEP) +=
monitors/snep/snep.oobj-$(CONFIG_RV_MON_SNCID) +=monitors/sncid/sncid.oobj-$(CONFIG_RV_MON_RTAPP) +=monitors/rtapp/rtapp.o+obj-$(CONFIG_RV_MON_PAGEFAULT) +=monitors/pagefault/pagefault.o# Add new monitors here
obj-$(CONFIG_RV_REACTORS) += rv_reactors.o obj-$(CONFIG_RV_REACT_PRINTK) += reactor_printk.okernel/trace/rv/monitors/pagefault/Kconfig new file +11
-0@@ -0,0 +1,11 @@ +# SPDX-License-Identifier: GPL-2.0-only +# +config RV_MON_PAGEFAULT + depends on RV + select RV_LTL_MONITOR + depends on RV_MON_RTAPP + default y + select LTL_MON_EVENTS_ID + bool "pagefault monitor" + help + Monitor that real-time tasks do not raise page faultskernel/trace/rv/monitors/pagefault/pagefault.c new file +19
-0@@ -0,0 +1,83 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <linux/ftrace.h> +#include <linux/tracepoint.h> +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/init.h> +#include <linux/rv.h> +#include <rv/instrumentation.h> + +#define MODULE_NAME "pagefault" + +#include <rv_trace.h> +#include <trace/events/exceptions.h> +#include <monitors/rtapp/rtapp.h> + +#include "pagefault.h" +#include <rv/ltl_monitor.h> + +static void ltl_atoms_fetch(struct task_struct *task, struct
ltl_monitor*mon)kernel/trace/rv/monitors/pagefault/pagefault.c new file +5
-0+{ +ltl_atom_set (mon,LTL_RT ,rt_task (task)); +} + +static void ltl_atoms_init(struct task_struct *task, struct
ltl_monitor*mon, booltask_creation)kernel/trace/rv/monitors/pagefault/pagefault.c new file +6
-0+{ +if (task_creation) +ltl_atom_set (mon,LTL_PAGEFAULT , false); +} + +static void handle_page_fault(void *data, unsigned long address,struct
pt_regs*regs,kernel/trace/rv/monitors/pagefault/pagefault.c new file +14
-0+ unsigned long error_code) +{ +ltl_atom_pulse (current,LTL_PAGEFAULT , true); +} + +static int enable_pagefault (void ) +{ +int retval; + + retval =ltl_monitor_init (); +if (retval) +return retval; + + rv_attach_trace_probe("pagefault", page_fault_kernel,
handle_page_fault);kernel/trace/rv/monitors/pagefault/pagefault.c new file +1
-0+ rv_attach_trace_probe("pagefault", page_fault_user,
handle_page_fault);kernel/trace/rv/monitors/pagefault/pagefault.c new file +9
-0+ +return 0 ; +} + +static void disable_pagefault (void ) +{ + rv_pagefault.enabled =0 ; + + rv_detach_trace_probe("rtapp_pagefault", page_fault_kernel,
handle_page_fault);kernel/trace/rv/monitors/pagefault/pagefault.c new file +1
-0+ rv_detach_trace_probe("rtapp_pagefault", page_fault_user,
handle_page_fault);kernel/trace/rv/monitors/pagefault/pagefault.c new file +7
-0+ +ltl_monitor_destroy (); +} + +static struct rv_monitor rv_pagefault = { + .name ="pagefault" , + .description = "Monitor that RT tasks do not raise pagefaults",
kernel/trace/rv/monitors/pagefault/pagefault.c line 70
Quoted 8 lines
kernel/trace/rv/monitors/pagefault/pagefault.c new file +8
-0+ .enable = enable_pagefault, + .disable = disable_pagefault, +}; + +static int __init register_pagefault (void ) +{ +rv_register_monitor (&rv_pagefault, &rv_rtapp); +return 0 ;
Any reason why you aren't returning the error value from the monitor registration?
Other than that, the monitor seems neat and reasonably easy to generate.
May not be necessary in this series, but try to keep compatibility with the userspace RV tool as well, you need to have some special case in its tracing components because fields are not matching:
# rv mon sleep -t
rcuc/11-108 [011] event <CANT FIND FIELD final_state>
(null) x (null) -> (null) Y
rcuc/11-108 [011] event <CANT FIND FIELD final_state>
(null) x (null) -> (null) Y
ktimers/11-109 [011] event <CANT FIND FIELD final_state>
(null) x (null) -> (null) YThanks,
Gabriele
Re: [PATCH v2 19/22] rv: Add rtapp_pagefault monitor
Quoted 8 lines · Gabriele Monaco
kernel/trace/rv/monitors/pagefault/pagefault.c line 70
Quoted 4 lines · Nam Cao
kernel/trace/rv/monitors/pagefault/pagefault.c new file +4
-0+static int __init register_pagefault (void ) +{ +rv_register_monitor (&rv_pagefault, &rv_rtapp); +return 0 ;Any reason why you aren't returning the error value from the monitor registration?
Copy-paste from dot2k :P
Quoted 6 lines
Other than that, the monitor seems neat and reasonably easy to generate.
May not be necessary in this series, but try to keep compatibility with the userspace RV tool as well, you need to have some special case in its tracing components because fields are not matching:
Quoted 7 lines
# rv mon sleep -t
rcuc/11-108 [011] event <CANT FIND FIELD final_state>
(null) x (null) -> (null) Y
rcuc/11-108 [011] event <CANT FIND FIELD final_state>
(null) x (null) -> (null) Y
ktimers/11-109 [011] event <CANT FIND FIELD final_state>
(null) x (null) -> (null) YI have this userspace RV tool in my "later" TODO list, if that's okay.
Honestly, I haven't looked at what it does yet. perf already does what I need.
Best regards,
Nam
Gabriele Monaco
maintainerRe: [PATCH v2 19/22] rv: Add rtapp_pagefault monitor
Quoted 11 lines · Nam Cao
Quoted 9 lines · Gabriele Monaco
kernel/trace/rv/monitors/pagefault/pagefault.c line 70
Quoted 4 lines · Nam Cao
kernel/trace/rv/monitors/pagefault/pagefault.c new file +4
-0+static int __init register_pagefault (void ) +{ +rv_register_monitor (&rv_pagefault, &rv_rtapp); +return 0 ;Any reason why you aren't returning the error value from the monitor
registration?
Quoted 1 line
Copy-paste from dot2k :P
Mmh, you're right! All other monitors are broken in this sense..
Quoted 20 lines
Quoted 9 lines
Other than that, the monitor seems neat and reasonably easy to generate.
May not be necessary in this series, but try to keep compatibility with
the userspace RV tool as well, you need to have some special case in
its tracing components because fields are not matching:Quoted 10 lines
# rv mon sleep -t rcuc/11-108 [011] event <CANT FIND FIELD final_state> (null) x (null) -> (null) Y rcuc/11-108 [011] event <CANT FIND FIELD final_state> (null) x (null) -> (null) Y ktimers/11-109 [011] event <CANT FIND FIELD final_state> (null) x (null) -> (null) Y
Quoted 6 lines
I have this userspace RV tool in my "later" TODO list, if that's okay.
Honestly, I haven't looked at what it does yet. perf already does what I
need.
Yeah, no rush, the tool is mostly for enabling the monitor and reactors in a single command, the rest (tracing) you can already do with perf, trace-cmd and friends, after enabling the monitor manually, of course.
We may even consider integrating RV in other tools instead of maintaining a separate one, but that's for another day.
Thanks,
Gabriele
Re: [PATCH v2 21/22] rv: Add documentation for rtapp monitor
In reply to Nam CaoQuoted 149 lines · Nam Cao
Add documentation describing the rtapp monitor.
Signed-off-by Nam Cao <[email protected]>---
Documentation/trace/rv/monitor_rtapp.rst | 105
+++++++++++++++++++++++1 file changed, 105 insertions(+)create mode 100644
Documentation/trace/rv/monitor_rtapp.rstDocumentation/trace/rv/monitor_rtapp.rst new file +11
-0@@ -0,0 +1,105 @@ +Scheduler monitors +================== + +- Name: rtapp +- Type: container for multiple monitors +- Author: Nam Cao <[email protected]> + +Description +----------- + +Real-time applications may have design flaws such that theyexperience unexpected latency and fail
+to meet their time requirements. Often, these flaws follow a few patterns:
+
+ - Page faults: A real-time thread may access memory that does not have a mapped physical backing
+ or must first be copied (such as for copy-on-write). Thus a page fault is raised and the kernel
+ must first perform the expensive action. This causes significant delays to the real-time thread
+ - Priority inversion: A real-time thread blocks waiting for a lower-priority thread. This causes
+ the real-time thread to effectively take on the scheduling priority of the lower-priority
+ thread. For example, the real-time thread needs to access a shared resource that is protected by
+ a non-pi-mutex, but the mutex is currently owned by a non-real- time thread.Documentation/trace/rv/monitor_rtapp.rst new file +2
-0+ +The `rtapp` monitor detects these patterns. It aids developers toidentify reasons for unexpected
+latency with real-time applications. It is a container of multiple sub-monitors described in theDocumentation/trace/rv/monitor_rtapp.rst new file +6
-0+following sections. + +Monitor pagefault ++++++++++++++++++ + +The `pagefault` monitor reports real-time tasks raising page faults.Its specification is::
Documentation/trace/rv/monitor_rtapp.rst new file +4
-0+ + RULE = always (RT imply not PAGEFAULT) + +To fix warnings reported by this monitor, `mlockall()` or `mlock()`can be used to ensure physical
Documentation/trace/rv/monitor_rtapp.rst new file +3
-0+backing for memory. + +This monitor may have false negatives because the pages used by thereal-time threads may just
+happen to be directly available during testing. To minimize this, the system can be put under memory
+pressure (e.g. invoking the OOM killer using a program that does `ptr =malloc(SIZE_OF_RAM);
+memset(ptr, 0, SIZE_OF_RAM);`) so that the kernel executes aggressive strategies to recycle as muchDocumentation/trace/rv/monitor_rtapp.rst new file +6
-0+physical memory as possible. + +Monitor sleep ++++++++++++++ + +The `sleep` monitor reports real-time threads sleeping in a mannerthat may cause undesirable
+latency. Real-time applications should only put a real-time thread to sleep for one of the followingDocumentation/trace/rv/monitor_rtapp.rst new file +3
-0+reasons: + + - Cyclic work: real-time thread sleeps waiting for the next cycle.For this case, only the
+nanosleepsyscall should be used. No other method is safe for real-time. For example, threads
+ waiting for timerfd can be woken by softirq which provides no real-time guarantee.
+ - Real-time thread waiting for something to happen (e.g. another thread releasing shared
+ resources, or a completion signal from another thread). In this case, only futexes with priority
+ inheritance (PI) should be used. Applications usually do not use futexes directly, but use PI
+ mutexes and PI condition variables which are built on top of futexes. Be aware that the C
+ library might not implement conditional variables as safe for real-time. As an alternative, the
+ librtpi library exists to provide a conditional variable implementation that is correct for
+ real-time applications in Linux.Documentation/trace/rv/monitor_rtapp.rst new file +2
-0+ +Beside the reason for sleeping, the eventual waker should also bereal-time-safe. Namely, one of:
Documentation/trace/rv/monitor_rtapp.rst new file +8
-0+ + - An equal-or-higher-priority thread + - Hard interrupt handler + - Non-maskable interrupt handler + +This monitor's warning usually means one of the following: + + - Real-time thread is blocked by a non-real-time thread (e.g. dueto contention on a mutex without
+ priority inheritance). This is priority inversion.
+ - Time-critical work waits for something which is not safe for real-time (e.g. timerfd).
+ - The work executed by the real-time thread does not need to run at real-time priority at all.
+ This is not a problem for the real-time thread itself, but it is potentially taking the CPU away
+ from other important real-time work.Documentation/trace/rv/monitor_rtapp.rst new file +2
-0+ +Application developers may purposely choose to have their real-timeapplication sleep in a way that
+is not safe for real-time. It is debatable whether that is a problem. Application developers mustDocumentation/trace/rv/monitor_rtapp.rst new file +5
-0+analyze the warnings to make a proper assessment. + +The monitor's specification is:: + + RULE = always (RT imply (SLEEP imply (RT_FRIENDLY_SLEEP orALLOWLIST)))
Documentation/trace/rv/monitor_rtapp.rst new file +16
-0+ + RT_FRIENDLY_SLEEP = (RT_VALID_SLEEP_REASON or KERNEL_THREAD) + and ((not WAKE) until RT_FRIENDLY_WAKE) + + RT_VALID_SLEEP_REASON = PI_FUTEX or NANOSLEEP + + RT_FRIENDLY_WAKE = WOKEN_BY_EQUAL_OR_HIGHER_PRIO + or WOKEN_BY_HARDIRQ + or WOKEN_BY_NMI + + ALLOWLIST = BLOCK_ON_RT_MUTEX + or TASK_IS_RCU + or TASK_IS_MIGRATION + or KTHREAD_SHOULD_STOP + +Beside the scenarios described above, this specification also handle
Quoted 8 lines
some special cases:
+
+ -KERNEL_THREAD: kernel tasks do not have any pattern that can be recognized as valid real-time
+ sleeping reasons. Therefore sleeping reason is not checked for kernel tasks.
+ -RT_SLEEP_WHITELIST: to handle known false positives with kernel tasks.
Is this what you call ALLOWLIST?
Just out of curiosity, normal kernel threads are not forced to follow a VALID_SLEEP_REASON but need RT_FRIENDLY_WAKE, how are tasks like RCU and migration not following this?
The monitors are not designed for deadline tasks, any plan to extend to those too?
Other than this, nice explanation and monitors, thanks.
Quoted 8 lines
+ -
BLOCK_ON_RT_MUTEXis included in the allowlist due to its implementation. In the release path
+ ofrt_mutex, a boosted task is de-boosted before waking the rt_mutex's waiter. Consequently, the
+ monitor may see a real-time-unsafe wakeup (e.g. non-real-time task waking real-time task). This
+ is actually real-time-safe because preemption is disable for the duration.
Typo:
+ is actually real-time-safe because preemption is disable**d** for
the duration.
Gabriele Monaco
maintainerRe: [PATCH v2 13/22] rv: Add support for LTL monitors
In reply to Nam CaoQuoted 176 lines · Nam Cao
While attempting to implement DA monitors for some complex specifications,
deterministic automaton is found to be inappropriate as the specification
language. The automaton is complicated, hard to understand, and error-prone.For these cases, linear temporal logic is more suitable as the specification language.
Add support for linear temporal logic runtime verification monitor.
For all the details, see the documentations added by this commit.
Signed-off-by Nam Cao <[email protected]>---
Documentation/trace/rv/index.rst | 1 + .../trace/rv/linear_temporal_logic.rst | 97 +++ Documentation/trace/rv/monitor_synthesis.rst | 141 ++++- include/linux/rv.h | 56 +- include/rv/ltl_monitor.h | 184 ++++++ kernel/fork.c | 5 +- kernel/trace/rv/Kconfig | 7 + kernel/trace/rv/rv_trace.h | 47 ++ tools/verification/rvgen/.gitignore | 3 + tools/verification/rvgen/Makefile | 2 + tools/verification/rvgen/__main__.py | 3 +- tools/verification/rvgen/rvgen/ltl2ba.py | 552
++++++++++++++++++
tools/verification/rvgen/rvgen/ltl2k.py | 242 ++++++++.../verification/rvgen/templates/ltl2k/main.c| 102 ++++ .../rvgen/templates/ltl2k/trace.h | 14 +15 files changed, 1431 insertions(+), 25 deletions(-)create mode 100644
Documentation/trace/rv/linear_temporal_logic.rstcreate mode 100644include/rv/ltl_monitor.h
create mode 100644tools/verification/rvgen/.gitignorecreate mode 100644tools/verification/rvgen/rvgen/ltl2ba.pycreate mode 100644tools/verification/rvgen/rvgen/ltl2k.pycreate mode 100644tools/verification/rvgen/templates/ltl2k/main.ccreate mode 100644tools/verification/rvgen/templates/ltl2k/trace.hDocumentation/trace/rv/index.rst +0
-0@@ -8,6 +8,7 @@ Runtime Verification
runtime-verification.rst
deterministic_automata.rst
+linear_temporal_logic.rst
monitor_synthesis.rst
da_monitor_instrumentation.rst
monitor_wip.rstDocumentation/trace/rv/linear_temporal_logic.rst new file +4
-0@@ -0,0 +1,97 @@ +Introduction +============ + +Runtime verification monitor is a verification technique whichchecks that the kernel follows a
+specification. It does so by using tracepoints to monitor the kernel's execution trace, andDocumentation/trace/rv/linear_temporal_logic.rst new file +3
-0+verifying that the execution trace sastifies the specification. + +Initially, the specification can only be written in the form ofdeterministic automaton (DA).
+However, while attempting to implement DA monitors for some complex specifications, deterministic
+automaton is found to be inappropriate as the specification language. The automaton is complicated,Documentation/trace/rv/linear_temporal_logic.rst new file +3
-0+hard to understand, and error-prone. + +Thus, RV monitors based on linear temporal logic (LTL) areintroduced. This type of monitor uses LTL
+as specification instead of DA. For some cases, writing the specification as LTL is more concise andDocumentation/trace/rv/linear_temporal_logic.rst new file +3
-0+intuitive. + +Documents regarding LTL are widely available on the internet, thisdocument will not go into
Documentation/trace/rv/linear_temporal_logic.rst new file +6
-0+details. + +Grammar +======== + +Unlike some existing syntax, kernel's implementation of LTL is moreverbose. This is motivated by
+considering that the people who read the LTL specifications may not be well-versed in LTL.Documentation/trace/rv/linear_temporal_logic.rst new file +6
-0+ +Grammar: + ltl ::= opd | ( ltl ) | ltl binop ltl | unop ltl + +Operands (opd): + true, false, user-defined names consisting of upper-casecharacters, digits, and underscore.
Documentation/trace/rv/linear_temporal_logic.rst new file +14
-0+ +Unary Operators (unop): + always + eventually + not + +Binary Operators (binop): + until + and + or + imply + equivalent + +This grammar is ambiguous: operator precedence is not defined.Parentheses must be used.
Documentation/trace/rv/linear_temporal_logic.rst new file +22
-0+ +Example linear temporal logic +============================= +.. code-block:: + + RAIN imply (GO_OUTSIDE imply HAVE_UMBRELLA) + +means: if it is raining, going outside means having an umbrella. + +.. code-block:: + + RAIN imply (WET until not RAIN) + +means: if it is raining, it is going to be wet until the rain stops. + +.. code-block:: + + RAIN imply eventually not RAIN + +means: if it is raining, rain will eventually stop. + +The above examples are referring to the current time instance only.For kernel verification, the
+alwaysoperator is usually desirable, to specify that something is always true at the present andDocumentation/trace/rv/linear_temporal_logic.rst new file +7
-0+for all future. For example:: + + always (RAIN imply eventually not RAIN) + +means: *all* rain eventually stops. + +In the above examples, `RAIN`, `GO_OUTSIDE`, `HAVE_UMBRELLA` and
WETare the "atomicDocumentation/trace/rv/linear_temporal_logic.rst new file +6
-0+propositions". + +Monitor synthesis +================= + +To synthesize an LTL into a kernel monitor, the `rvgen` tool can beused:
+tools/verification/rvgen. The specification needs to be provided as a file, and it must have a
+"RULE = LTL" assignment. For example::
+
+ RULE = always (ACQUIRE imply ((not KILLED and not CRASHED) until RELEASE))Documentation/trace/rv/linear_temporal_logic.rst new file +2
-0+ +which says: if `ACQUIRE`, then `RELEASE` must happen before `KILLED`or
CRASHED.Documentation/trace/rv/linear_temporal_logic.rst new file +2
-0+ +The LTL can be broken down using sub-expressions. The above isequivalent to:
Documentation/trace/rv/linear_temporal_logic.rst new file +7
-0+ + .. code-block:: + + RULE = always (ACQUIRE imply (ALIVE until RELEASE)) + ALIVE = not KILLED and not CRASHED + +From this specification, `rvgen` generates the C implementation of a
Quoted 5 lines
Buchi automaton - a
+non-deterministic state machine which checks the satisfiability of the LTL. See+Documentation/trace/rv/monitor_synthesis.rstfor details on usingrvgen.
You probably read a lot to write this, do you mind adding a brief Reference section for the curious reader? Asking for a friend ;)
Something like
https://docs.kernel.org/trace/rv/deterministic_automata.html#references
would do.
Thanks,
Gabriele
Re: [PATCH v2 13/22] rv: Add support for LTL monitors
Quoted 2 lines · Gabriele Monaco
You probably read a lot to write this, do you mind adding a brief Reference section for the curious reader? Asking for a friend ;)
I actually learned lots of it during university.
But I certainly can link some materials.
Best regards,
Nam
Re: [PATCH v2 21/22] rv: Add documentation for rtapp monitor
In reply to Gabriele MonacoQuoted 5 lines · Gabriele Monaco
Quoted 2 lines · Nam Cao
+ -
RT_SLEEP_WHITELIST: to handle known false positives with kernel tasks.Is this what you call ALLOWLIST?
Yes. A colleague already poked me off-list about this error :(
Quoted 3 lines
Just out of curiosity, normal kernel threads are not forced to follow a
VALID_SLEEP_REASONbut needRT_FRIENDLY_WAKE, how are tasks like RCU and migration not following this?
Because that's how RCU and migration works, they are intended to be woken by anything.
It is also possible that people deliberately design their userspace real-time threads to be woken by non-real-time threads. For example, pipewire has a non-real-time thread waking a real-time thread to do some non-critical work. That's still okayish from real-time perspective (but it is better if the non-real-time thread just does the work itself).
This monitor's warning is not exactly a "here's a bug, fix it". But more like "something seems really wrong here, please investigate". People can decide whether this particular suspicious instance is acceptable for their case.
The initial implementation of the monitor didn't have this allowlist. And we had a bunch of warnings on the rcu_preempt and migration/ threads. We decided that due to how rcu and migration works, these warnings are okay.
Quoted 2 lines
The monitors are not designed for deadline tasks, any plan to extend to those too?
I haven't thought much about deadline tasks. But it could be extended by changing "RT" into "RT or DL", if needed.
Quoted 3 lines
Other than this, nice explanation and monitors, thanks.
Reviewed-by Gabriele Monaco <[email protected]>
Thanks so much for the review!
Nam