Linear temporal logic monitors for RT application
Subsystems (11)
v3 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-12 cleanup and 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.
v2->v3 https://lore.kernel.org/lkml/[email protected]/
- fix a problem with sleep monitor's specification (around KTHREAD_SHOULD_STOP)
- merge the patches that move the dot2k/rvgen scripts around
- pull panic/printk changes into separate patches
- fixup some build errors
- fixup monitor's init function return code
- fix some flake8 warnings with the scripts
- add some references to LTL documentation
- fixup some mistakes with rtapp documentation
- fixup capitalization mistake with monitor_synthesis.rst
- remove the now-redundant macro RV_PER_TASK_MONITORS
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: Add #undef TRACE_INCLUDE_FILE
printk: Make vprintk_deferred() public
panic: Add vpanic()
rv: Let the reactors take care of buffers 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: Restructure the templates files 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 | 119 ++++
Documentation/trace/rv/monitor_rtapp.rst | 107 ++++
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 | 74 ++-
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 | 80 +++
.../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 | 216 +++++++
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 | 10 +-
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 | 27 +
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} | 249 ++------
tools/verification/rvgen/rvgen/ltl2ba.py | 558 ++++++++++++++++++
tools/verification/rvgen/rvgen/ltl2k.py | 242 ++++++++
.../rvgen/templates}/Kconfig | 0
.../rvgen/rvgen/templates/container/Kconfig | 5 +
.../rvgen/templates/container/main.c} | 0
.../rvgen/templates/container/main.h} | 0
.../rvgen/templates/dot2k}/main.c | 0
.../rvgen/templates/dot2k}/trace.h | 0
.../rvgen/rvgen/templates/ltl2k/main.c | 102 ++++
.../rvgen/rvgen/templates/ltl2k/trace.h | 14 +
63 files changed, 2875 insertions(+), 550 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} (52%)
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/rvgen/templates}/Kconfig (100%)
create mode 100644 tools/verification/rvgen/rvgen/templates/container/Kconfig
rename tools/verification/{dot2/dot2k_templates/main_container.c => rvgen/rvgen/templates/container/main.c} (100%)
rename tools/verification/{dot2/dot2k_templates/main_container.h => rvgen/rvgen/templates/container/main.h} (100%)
rename tools/verification/{dot2/dot2k_templates => rvgen/rvgen/templates/dot2k}/main.c (100%)
rename tools/verification/{dot2/dot2k_templates => rvgen/rvgen/templates/dot2k}/trace.h (100%)
create mode 100644 tools/verification/rvgen/rvgen/templates/ltl2k/main.c
create mode 100644 tools/verification/rvgen/rvgen/templates/ltl2k/trace.hSignature · 1 line
2.39.5
PATCH v3 1/22 Add #undef TRACE_INCLUDE_FILE
Without "#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 v3 2/22 printk: Make vprintk_deferred() public
In reply to Nam Caovprintk_deferred() is useful for implementing runtime verification reactors. Make it public.
---
Cc: John Ogness <[email protected]>
Cc: Sergey Senozhatsky <[email protected]>
--- include/linux/printk.h | 5 +++++ kernel/printk/internal.h | 1 - 2 files changed, 5 insertions(+), 1 deletion(-)
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, ...) {
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 );
Signature · 1 line
2.39.5
PATCH v3 3/22 panic: Add vpanic()
In reply to Nam Caovpanic() is useful for implementing runtime verification reactors. Add it.
---
Cc: John Ogness <[email protected]>
Cc: Sergey Senozhatsky <[email protected]>
--- include/linux/panic.h | 3 +++ kernel/panic.c | 17 ++++++++++++----- 2 files changed, 15 insertions(+), 5 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 );
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) \
Signature · 1 line
2.39.5
PATCH v3 4/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/rv.h | 9 +++++-- include/rv/da_monitor.h | 45 +++++++------------------------- kernel/trace/rv/reactor_panic.c | 8 ++++-- kernel/trace/rv/reactor_printk.c | 8 ++++-- kernel/trace/rv/rv_reactors.c | 2 +- 5 files changed, 30 insertions(+), 42 deletions(-)
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 +static inline 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/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) +__printf(1, 2) 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) +__printf(1, 2) 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) +__printf(1, 2) static void rv_nop_reaction(const char *msg, ...) { }
Signature · 1 line
2.39.5
PATCH v3 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/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/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 v3 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/dot2k.py | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-)
tools/verification/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 v3 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/dot2k | 37 +++++++++++++++++--------------- tools/verification/dot2/dot2k.py | 2 +- 2 files changed, 21 insertions(+), 18 deletions(-)
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())
tools/verification/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()
Signature · 1 line
2.39.5
PATCH v3 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 v3 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 => rvgen/rvgen}/automata.py | 0
.../{dot2 => rvgen/rvgen}/dot2c.py | 2 +-
.../{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 => rvgen/rvgen}/automata.py (100%)
rename tools/verification/{dot2 => rvgen/rvgen}/dot2c.py (99%)
rename tools/verification/{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) automata.py -D -m 644 $(DESTDIR)$(PYLIB)/dot2/automata.py - $(INSTALL) 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) 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/automata.py +0 -0
tools/verification/rvgen/rvgen/dot2c.py renamed from tools/verification/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/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
Re: [PATCH v3 09/22] verification/dot2k: Prepare the frontend for LTL inclusion
Quoted 12 lines · Nam Cao
The 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
Quoted 7 lines
The old command:
python3 dot2/dot2k monitor -d wip.dot -t
per_cpuis equivalent to the new commands:
python3 dot2/dot2k monitor -c da -s wip.dot -t
per_cpu
Some more things changed here:
python3 rvgen monitor -c da -s wip.dot -t per_cpu
For the rest, all changes in the scripts (11-12/22) look good to me.
Thanks,
Gabriele
Quoted 260 lines
Signed-off-by Nam Cao <[email protected]>---
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 => rvgen/rvgen}/automata.py | 0 .../{dot2 => rvgen/rvgen}/dot2c.py | 2 +- .../{dot2 => rvgen/rvgen}/dot2k.py | 10 +++++-----12 files changed, 25 insertions(+), 17 deletions(-)rename
tools/verification/{dot2=> rvgen}/Makefile (55%) renametools/verification/{dot2/dot2k=>rvgen/__main__.py} (72%) renametools/verification/{dot2=> rvgen}/dot2c (97%) renametools/verification/{dot2=> rvgen}/dot2k_templates/Kconfig (100%)
renametools/verification/{dot2=> rvgen}/dot2k_templates/Kconfig_container (100%)
renametools/verification/{dot2=>rvgen}/dot2k_templates/main.c(100%)
renametools/verification/{dot2=>rvgen}/dot2k_templates/main_container.c(100%)
renametools/verification/{dot2=>rvgen}/dot2k_templates/main_container.h(100%)
renametools/verification/{dot2=>rvgen}/dot2k_templates/trace.h(100%)
renametools/verification/{dot2=>rvgen/rvgen}/automata.py(100%) renametools/verification/{dot2=>rvgen/rvgen}/dot2c.py(99%) renametools/verification/{dot2=>rvgen/rvgen}/dot2k.py(98%)tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +0
-0@@ -3,7 +3,7 @@ INSTALL=installprefix ?= /usr
bindir ?= $(prefix)/bin
mandir ?= $(prefix)/share/mantools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +1
-1-miscdir ?= $(prefix)/share/dot2 +miscdir ?= $(prefix)/share/rvgensrcdir ?= $(prefix)/src
PYLIB ?= $(shell python3 -c 'import sysconfig; print (sysconfig.get_path("purelib"))')tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +0
-0@@ -16,11 +16,11 @@ clean:
.PHONY: install
install:tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +0
-1- $(INSTALL) automata.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/automata.py
tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +0
-1- $(INSTALL) dot2c.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/dot2c.py
tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +1
-0+ $(INSTALL) rvgen/automata.py -D -m 644$(DESTDIR)$(PYLIB)/rvgen/automata.py
tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +1
-0+ $(INSTALL) rvgen/dot2c.py -D -m 644$(DESTDIR)$(PYLIB)/rvgen/dot2c.py
$(INSTALL) dot2c -D -m 755 $(DESTDIR)$(bindir)/tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +0
-1- $(INSTALL) dot2k.py -D -m 644$(DESTDIR)$(PYLIB)/dot2/dot2k.py
tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +1
-1- $(INSTALL) dot2k -D -m 755 $(DESTDIR)$(bindir)/ + $(INSTALL) rvgen/dot2k.py -D -m 644$(DESTDIR)$(PYLIB)/rvgen/dot2k.py
tools/verification/rvgen/Makefile renamed from tools/verification/dot2/Makefile +1
-0+ $(INSTALL) __main__.py -D -m 755 $(DESTDIR)$(bindir)/rvgen
mkdir -p ${miscdir}/
cp -rpdot2k_templates$(DESTDIR)$(miscdir)/tools/verification/rvgen/__main__.py renamed from tools/verification/dot2/dot2k +0
-0@@ -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,tools/verification/rvgen/__main__.py renamed from tools/verification/dot2/dot2k +0
-0@@ -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())}")tools/verification/rvgen/__main__.py renamed from tools/verification/dot2/dot2k +0
-0@@ -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 +0
-0@@ -14,7 +14,7 @@ # Documentation/trace/rv/deterministic_automata.rst
if__name__== '__main__':
- from dot2 import dot2c
+ from rvgen import dot2c
import argparse
import systools/verification/rvgen/dot2k_templates/Kconfig renamed from tools/verification/dot2/dot2k_templates/Kconfig +0
-0diff --git a/tools/verification/dot2/dot2k_templates/Kconfig_container b/tools/verification/rvgen/dot2k_templates/Kconfig_container similarity index 100%
rename fromtools/verification/dot2/dot2k_templates/Kconfig_containerrename totools/verification/rvgen/dot2k_templates/Kconfig_containertools/verification/rvgen/dot2k_templates/main.c renamed from tools/verification/dot2/dot2k_templates/main.c +0
-0tools/verification/rvgen/dot2k_templates/main_container.c renamed from tools/verification/dot2/dot2k_templates/main_container.c +0
-0tools/verification/rvgen/dot2k_templates/main_container.h renamed from tools/verification/dot2/dot2k_templates/main_container.h +0
-0tools/verification/rvgen/dot2k_templates/trace.h renamed from tools/verification/dot2/dot2k_templates/trace.h +0
-0tools/verification/rvgen/rvgen/automata.py renamed from tools/verification/dot2/automata.py +0
-0tools/verification/rvgen/rvgen/dot2c.py renamed from tools/verification/dot2/dot2c.py +0
-0@@ -13,7 +13,7 @@ # For further information, see: # Documentation/trace/rv/deterministic_automata.rsttools/verification/rvgen/rvgen/dot2c.py renamed from tools/verification/dot2/dot2c.py +1
-1-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/dot2k.py +0
-0@@ -8,13 +8,13 @@ # For further information, see: # Documentation/trace/rv/da_monitor_synthesis.rsttools/verification/rvgen/rvgen/dot2k.py renamed from tools/verification/dot2/dot2k.py +1
-1-from dot2.dot2c import Dot2c +from .dot2c import Dot2cimport 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"tools/verification/rvgen/rvgen/dot2k.py renamed from tools/verification/dot2/dot2k.py +0
-0@@ -60,14 +60,14 @@ class dot2k(Dot2c):if
platform.system()!= "Linux":
raiseOSError("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())
ifos.path.exists(kernel_path):
self.monitor_templates_dir =kernel_pathreturn
- ifos.path.exists("/usr/share/dot2/dot2k_templates/"):
- self.monitor_templates_dir = "/usr/share/dot2/dot2k_templates/"
+ ifos.path.exists("/usr/share/rvgen/dot2k_templates/"):
+ self.monitor_templates_dir = "/usr/share/rvgen/dot2k_templates/"
return
raiseFileNotFoundError("Could not find the template directory, do you have the kernel source installed?")
PATCH v3 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 v3 11/22 verification/rvgen: Restructure the templates files
In reply to Nam CaoTo simply the scripts and to allow easy integration of new monitor types, restructure the template files as followed:
1. Move the template files to be in the same directory as the rvgen package. Furthermore, the installation will now only install the templates to the package directory, not /usr/share/. This simplify templates reading, as the scripts do not need to find the templates at multiple places.
2. Move dot2k_templates/* to:
- templates/dot2k/
- templates/container/
This allows sharing templates reading code between DA monitor generation and container generation (and any future generation type).
For template files which can be shared between different generation types, support putting them in templates/
This restructure aligns with the recommendation from:
https://python-packaging.readthedocs.io/en/latest/non-code-files.html
---
tools/verification/rvgen/Makefile | 5 +-
tools/verification/rvgen/rvgen/dot2k.py | 47 ++++++++-----------
.../templates}/Kconfig | 0
.../templates/container/Kconfig} | 0
.../templates/container/main.c} | 0
.../templates/container/main.h} | 0
.../templates/dot2k}/main.c | 0
.../templates/dot2k}/trace.h | 0
8 files changed, 20 insertions(+), 32 deletions(-)
rename tools/verification/rvgen/{dot2k_templates => rvgen/templates}/Kconfig (100%)
rename tools/verification/rvgen/{dot2k_templates/Kconfig_container => rvgen/templates/container/Kconfig} (100%)
rename tools/verification/rvgen/{dot2k_templates/main_container.c => rvgen/templates/container/main.c} (100%)
rename tools/verification/rvgen/{dot2k_templates/main_container.h => rvgen/templates/container/main.h} (100%)
rename tools/verification/rvgen/{dot2k_templates => rvgen/templates/dot2k}/main.c (100%)
rename tools/verification/rvgen/{dot2k_templates => rvgen/templates/dot2k}/trace.h (100%)tools/verification/rvgen/Makefile +1 -4
@@ -3,7 +3,6 @@ INSTALL=install prefix ?= /usr bindir ?= $(prefix)/bin mandir ?= $(prefix)/share/man -miscdir ?= $(prefix)/share/rvgen srcdir ?= $(prefix)/src PYLIB ?= $(shell python3 -c 'import sysconfig; print (sysconfig.get_path("purelib"))')
@@ -21,6 +20,4 @@ install: $(INSTALL) dot2c -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)/ + cp -rp rvgen/templates $(DESTDIR)$(PYLIB)/rvgen/
tools/verification/rvgen/rvgen/dot2k.py +19 -28
83 lines not on this page · raw message
tools/verification/rvgen/rvgen/templates/Kconfig renamed from tools/verification/rvgen/dot2k_templates/Kconfig +0 -0
tools/verification/rvgen/rvgen/templates/container/Kconfig renamed from tools/verification/rvgen/dot2k_templates/Kconfig_container +0 -0
tools/verification/rvgen/rvgen/templates/container/main.c renamed from tools/verification/rvgen/dot2k_templates/main_container.c +0 -0
tools/verification/rvgen/rvgen/templates/container/main.h renamed from tools/verification/rvgen/dot2k_templates/main_container.h +0 -0
tools/verification/rvgen/rvgen/templates/dot2k/main.c renamed from tools/verification/rvgen/dot2k_templates/main.c +0 -0
tools/verification/rvgen/rvgen/templates/dot2k/trace.h renamed from tools/verification/rvgen/dot2k_templates/trace.h +0 -0
Signature · 1 line
2.39.5
PATCH v3 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 | 275 ++------------------ tools/verification/rvgen/rvgen/generator.py | 264 +++++++++++++++++++ 5 files changed, 308 insertions(+), 261 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
@@ -19,5 +19,7 @@ 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 cp -rp rvgen/templates $(DESTDIR)$(PYLIB)/rvgen/
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): + template_dir = "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 -259
301 lines not on this page · raw message
tools/verification/rvgen/rvgen/generator.py new file +264 -0
264 lines not on this page · raw message
Signature · 1 line
2.39.5
PATCH v3 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 | 119 ++++ Documentation/trace/rv/monitor_synthesis.rst | 141 ++++- include/linux/rv.h | 62 +- 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 | 558 ++++++++++++++++++ tools/verification/rvgen/rvgen/ltl2k.py | 242 ++++++++ .../rvgen/rvgen/templates/ltl2k/main.c | 102 ++++ .../rvgen/rvgen/templates/ltl2k/trace.h | 14 + 15 files changed, 1465 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/rvgen/templates/ltl2k/main.c create mode 100644 tools/verification/rvgen/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 +119 -0
119 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 +58 -4
81 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
@@ -21,5 +21,7 @@ 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 cp -rp rvgen/templates $(DESTDIR)$(PYLIB)/rvgen/
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 +558 -0
558 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/rvgen/templates/ltl2k/main.c new file +102 -0
102 lines not on this page · raw message
tools/verification/rvgen/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
Gabriele Monaco
maintainerRe: [PATCH v3 13/22] rv: Add support for LTL monitors
Quoted 80 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 | 119 ++++ Documentation/trace/rv/monitor_synthesis.rst | 141 ++++- include/linux/rv.h | 62 +- 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 | 558
++++++++++++++++++
tools/verification/rvgen/rvgen/ltl2k.py | 242 ++++++++ .../rvgen/rvgen/templates/ltl2k/main.c | 102 ++++ .../rvgen/rvgen/templates/ltl2k/trace.h | 14 +15 files changed, 1465 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/rvgen/templates/ltl2k/main.ccreate mode 100644tools/verification/rvgen/rvgen/templates/ltl2k/trace.h[...]
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
Quoted 2 lines
include/rv/ltl_monitor.h new file +2
-0+ task->comm, task->pid); +}
What about adding more context here (see below).
Quoted 51 lines
include/rv/ltl_monitor.h new file +6
-0+#else +static void rv_cond_react (struct task_struct *task) +{ +} +#endif +kernel/trace/rv/rv_trace.h +0
-0@@ -127,6 +127,53 @@ DECLARE_EVENT_CLASS(error_da_monitor_id, // Add new monitors based on CONFIG_DA_MON_EVENTS_ID here
#endif /*CONFIG_DA_MON_EVENTS_ID*/kernel/trace/rv/rv_trace.h +4
-0+#if CONFIG_LTL_MON_EVENTS_ID +TRACE_EVENT(event_ltl_monitor_id, + + TP_PROTO(struct task_struct *task, char *states, char*atoms, char *next),
kernel/trace/rv/rv_trace.h +20
-0+ +TP_ARGS (task, states, atoms, next), + +TP_STRUCT__entry ( + __string(comm, task->comm) + __field(pid_t, pid) + __string(states, states) + __string(atoms, atoms) +__string (next, next) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; +__assign_str (states); +__assign_str (atoms); +__assign_str (next); + ), + + TP_printk("%s[%d]: (%s) x (%s) -> (%s)", __get_str(comm),
__entry->pid,__get_str(states),kernel/trace/rv/rv_trace.h +10
-0+ __get_str(atoms), __get_str(next)) +); + +TRACE_EVENT(error_ltl_monitor_id, + + TP_PROTO(struct task_struct *task), + + TP_ARGS(task), + + TP_STRUCT__entry(
kernel/trace/rv/rv_trace.h DECLARE_EVENT_CLASS(error_da_monitor_id,
Quoted 10 lines
kernel/trace/rv/rv_trace.h +10
-0+ __string(comm, task->comm) +__field (pid_t, pid) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; + ), + + TP_printk("%s[%d]: violation detected", __get_str(comm),
In your workflow you're probably using events and errors together, but wouldn't it help printing the atoms together with the violation detected?
At least to give a clue on the error in case the user doesn't want to see the entire trace (which might be needed for a full debug though).
The same could be said from reactors, the user doesn't have much information to infer what went wrong.
Quoted 56 lines
__entry->pid)kernel/trace/rv/rv_trace.h +3
-0+); +// Add new monitors based on CONFIG_LTL_MON_EVENTS_ID here +#endif /* CONFIG_LTL_MON_EVENTS_ID */ #endif /*
_TRACE_RV_H*/
/* This part must be outside protection */
[...]tools/verification/rvgen/rvgen/ltl2k.py new file +41
-0@@ -0,0 +1,242 @@ +#!/usr/bin/env python3 +# SPDX-License-Identifier: GPL-2.0-only + +from pathlib import Path +from . import generator +from . import ltl2ba + +COLUMN_LIMIT = 100 + +def line_len(line: str) -> int: + tabs = line.count('\t') + return tabs * 7 + len(line) + +def break_long_line(line: str, indent='') -> list[str]: + result = [] + while line_len(line) > COLUMN_LIMIT: + i = line[:COLUMN_LIMIT - line_len(line)].rfind(' ') + result.append(line[:i]) + line = indent + line[i + 1:] + if line: + result.append(line) + return result + +def build_condition_string(node: ltl2ba.GraphNode): + if not node.labels: + return "(true)" + + result = "(" + + first = True + for label in sorted(node.labels): + if not first: + result += " && " + result += label + first = False + + result += ")" + + return result + +def abbreviate_atoms(atoms: list[str]) -> list[str]:
tools/verification/rvgen/rvgen/ltl2k.py line 51
Quoted 10 lines
tools/verification/rvgen/rvgen/ltl2k.py new file +10
-0+ abbrs = list() + for atom in atoms: + size = 1 + while True: + abbr = atom[:size] + if sum(a.startswith(abbr) for a in atoms) == 1: + break + size += 1 + abbrs.append(abbr.lower()) + return abbrs
I get this is just a matter of preference, so feel free to ignore my suggestion.
This abbreviation algorithm doesn't work too well with atoms starting with the same substring and can produce some unexpected result:
LTL_BLOCK_ON_RT_MUTEX: b, LTL_KERNEL_THREAD: ke, LTL_KTHREAD_SHOULD_STOP: kt, LTL_NANOSLEEP: n, LTL_PI_FUTEX: p, LTL_RT: r, LTL_SLEEP: s, LTL_TASK_IS_MIGRATION: task_is_m, LTL_TASK_IS_RCU: task_is_r, LTL_WAKE: wa, LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO: woken_by_e, LTL_WOKEN_BY_HARDIRQ: woken_by_h, LTL_WOKEN_BY_NMI: woken_by_n,
"woken_by_*" and "task_is_*" atom can get unnecessarily long and while reading "kt" I might think about kernel_thread.
I was thinking about something like:
LTL_BLOCK_ON_RT_MUTEX: b_o_r_m LTL_KERNEL_THREAD: k_t LTL_KTHREAD_SHOULD_STOP: k_s_s LTL_NANOSLEEP: n LTL_PI_FUTEX: p_f LTL_RT: r LTL_SLEEP: s LTL_TASK_IS_MIGRATION: t_i_m LTL_TASK_IS_RCU: t_i_r LTL_WAKE: w LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO: w_b_e_o_h_p LTL_WOKEN_BY_HARDIRQ: w_b_h LTL_WOKEN_BY_NMI: w_b_n
or even
LTL_BLOCK_ON_RT_MUTEX: b_m LTL_KERNEL_THREAD: k_t LTL_KTHREAD_SHOULD_STOP: k_s_s LTL_NANOSLEEP: n LTL_PI_FUTEX: p_f LTL_RT: r LTL_SLEEP: s LTL_TASK_IS_MIGRATION: t_m LTL_TASK_IS_RCU: t_r LTL_WAKE: w LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO: w_e_h_p LTL_WOKEN_BY_HARDIRQ: w_h LTL_WOKEN_BY_NMI: w_n
I used the following code to come up with this:
def abbreviate_atoms(atoms: list[str]) -> list[str]:
# completely arbitrary..
skip = [ "is", "by", "or", "and" ]
def abbr (n, s):
return '_'.join(word[:n] for word in s.lower().split('_') if word not in skip)
for n in range(1, 32):
abbrs = [abbr(n, a) for a in atoms]
if len(abbrs) == len(set(abbrs)):
return abbrsWhich could even be tuned to use 2 letters per block instead of 1 (improving readability by a lot actually)..
'bl_on_rt_mu', 'ke_th', 'kt_sh_st', 'na', 'pi_fu', 'rt', 'sl', 'ta_mi', 'ta_rc', 'wa', 'wo_eq_hi_pr', 'wo_ha', 'wo_nm'
What do you think?
Thanks,
Gabriele
Re: [PATCH v3 13/22] rv: Add support for LTL monitors
Quoted 55 lines · Gabriele Monaco
Quoted 37 lines · Nam Cao
#endif /*
CONFIG_DA_MON_EVENTS_ID*/kernel/trace/rv/rv_trace.h +4
-0+#if CONFIG_LTL_MON_EVENTS_ID +TRACE_EVENT(event_ltl_monitor_id, + + TP_PROTO(struct task_struct *task, char *states, char*atoms, char *next),
kernel/trace/rv/rv_trace.h +20
-0+ +TP_ARGS (task, states, atoms, next), + +TP_STRUCT__entry ( + __string(comm, task->comm) + __field(pid_t, pid) + __string(states, states) + __string(atoms, atoms) +__string (next, next) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; +__assign_str (states); +__assign_str (atoms); +__assign_str (next); + ), + + TP_printk("%s[%d]: (%s) x (%s) -> (%s)", __get_str(comm),
__entry->pid,__get_str(states),kernel/trace/rv/rv_trace.h +10
-0+ __get_str(atoms), __get_str(next)) +); + +TRACE_EVENT(error_ltl_monitor_id, + + TP_PROTO(struct task_struct *task), + + TP_ARGS(task), + + TP_STRUCT__entry(kernel/trace/rv/rv_trace.h DECLARE_EVENT_CLASS(error_da_monitor_id,
Quoted 10 lines
kernel/trace/rv/rv_trace.h +10
-0+ __string(comm, task->comm) +__field (pid_t, pid) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; + ), + + TP_printk("%s[%d]: violation detected", __get_str(comm),In your workflow you're probably using events and errors together, but wouldn't it help printing the atoms together with the violation detected?
At least to give a clue on the error in case the user doesn't want to see the entire trace (which might be needed for a full debug though).
Quoted 2 lines
The same could be said from reactors, the user doesn't have much information to infer what went wrong.
Actually my intention for the "event" tracepoints are only for debugging the monitor itself. I don't want to bother users with the Büchi automaton, because that's implementation details.
The "error" tracepoints should be enough for identifying problems with realtime applications. Because errors from the monitors are unambiguous:
- pagefault monitor: error means an RT task is raising pagefault
- sleep monitor: error means an RT task is delayed unboundedly
That and a stacktrace (e.g. from perf) is enough to understand the problem. That was all I need to identifying problems with pipewire using the monitors.
In the future, we can have other monitors whose warnings are ambiguous, and a more detailed error message will be necessary. But for now, I think we can keep it simple.
Quoted 78 lines
Quoted 11 lines
+def
abbreviate_atoms(atoms: list[str])-> list[str]:
+ abbrs =list()
+ for atom in atoms:
+ size = 1
+ while True:
+ abbr = atom[:size]
+ if sum(a.startswith(abbr) for a in atoms) == 1:
+ break
+ size += 1
+ abbrs.append(abbr.lower())
+ return abbrsI get this is just a matter of preference, so feel free to ignore my suggestion.
This abbreviation algorithm doesn't work too well with atoms starting with the same substring and can produce some unexpected result:LTL_BLOCK_ON_RT_MUTEX: b, LTL_KERNEL_THREAD: ke, LTL_KTHREAD_SHOULD_STOP: kt, LTL_NANOSLEEP: n, LTL_PI_FUTEX: p, LTL_RT: r, LTL_SLEEP: s, LTL_TASK_IS_MIGRATION: task_is_m, LTL_TASK_IS_RCU: task_is_r, LTL_WAKE: wa, LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO: woken_by_e, LTL_WOKEN_BY_HARDIRQ: woken_by_h, LTL_WOKEN_BY_NMI: woken_by_n,"woken_by_*" and "task_is_*" atom can get unnecessarily long and while reading "kt" I might think about
kernel_thread.I was thinking about something like:
LTL_BLOCK_ON_RT_MUTEX: b_o_r_m LTL_KERNEL_THREAD: k_t LTL_KTHREAD_SHOULD_STOP: k_s_s LTL_NANOSLEEP: n LTL_PI_FUTEX: p_f LTL_RT: r LTL_SLEEP: s LTL_TASK_IS_MIGRATION: t_i_m LTL_TASK_IS_RCU: t_i_r LTL_WAKE: w LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO: w_b_e_o_h_p LTL_WOKEN_BY_HARDIRQ: w_b_h LTL_WOKEN_BY_NMI: w_b_nor even
LTL_BLOCK_ON_RT_MUTEX: b_m LTL_KERNEL_THREAD: k_t LTL_KTHREAD_SHOULD_STOP: k_s_s LTL_NANOSLEEP: n LTL_PI_FUTEX: p_f LTL_RT: r LTL_SLEEP: s LTL_TASK_IS_MIGRATION: t_m LTL_TASK_IS_RCU: t_r LTL_WAKE: w LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO: w_e_h_p LTL_WOKEN_BY_HARDIRQ: w_h LTL_WOKEN_BY_NMI: w_nI used the following code to come up with this:
def
abbreviate_atoms(atoms: list[str])-> list[str]:# completely arbitrary.. skip = [ "is", "by", "or", "and" ] def abbr (n, s): return '_'.join(word[:n] for word in s.lower().split('_') if word not in skip) for n in range(1, 32): abbrs = [abbr(n, a) for a in atoms] if len(abbrs) == len(set(abbrs)): return abbrs
Quoted 6 lines
Which could even be tuned to use 2 letters per block instead of 1 (improving readability by a lot actually)..
'bl_on_rt_mu', 'ke_th', 'kt_sh_st', 'na', 'pi_fu', 'rt', 'sl', 'ta_mi', 'ta_rc', 'wa', 'wo_eq_hi_pr', 'wo_ha', 'wo_nm'What do you think?
Yes, this would be very nice. But as mentioned, this is mainly for debugging the monitors, not for end users. Therefore I don't want to spend too much energy on it.
Let me see how "nice" we can make it without spending too many hours. Thanks for the suggestion!
Best regards,
Nam
Re: [PATCH v3 13/22] rv: Add support for LTL monitors
Quoted 82 lines · Nam Cao
Quoted 59 lines · Gabriele Monaco
Quoted 38 lines · Nam Cao
#endif /*
CONFIG_DA_MON_EVENTS_ID*/kernel/trace/rv/rv_trace.h +4
-0+#if CONFIG_LTL_MON_EVENTS_ID +TRACE_EVENT(event_ltl_monitor_id, + + TP_PROTO(struct task_struct *task, char *states, char*atoms, char *next),
kernel/trace/rv/rv_trace.h +20
-0+ +TP_ARGS (task, states, atoms, next), + +TP_STRUCT__entry ( + __string(comm, task->comm) + __field(pid_t, pid) + __string(states, states) + __string(atoms, atoms) +__string (next, next) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; +__assign_str (states); +__assign_str (atoms); +__assign_str (next); + ), + + TP_printk("%s[%d]: (%s) x (%s) -> (%s)",
__get_str(comm),__entry->pid,__get_str(states),kernel/trace/rv/rv_trace.h +10
-0+ __get_str(atoms), __get_str(next)) +); + +TRACE_EVENT(error_ltl_monitor_id, + + TP_PROTO(struct task_struct *task), + + TP_ARGS(task), + + TP_STRUCT__entry(kernel/trace/rv/rv_trace.h DECLARE_EVENT_CLASS(error_da_monitor_id,
Quoted 10 lines
kernel/trace/rv/rv_trace.h +10
-0+ __string(comm, task->comm) +__field (pid_t, pid) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; + ), + + TP_printk("%s[%d]: violation detected", __get_str(comm),In your workflow you're probably using events and errors together, but
wouldn't it help printing the atoms together with the violation detected?
At least to give a clue on the error in case the user doesn't want to
see the entire trace (which might be needed for a full debug though).Quoted 2 lines
The same could be said from reactors, the user doesn't have much information to infer what went wrong.
Actually my intention for the "event" tracepoints are only for debugging
the monitor itself. I don't want to bother users with the Büchi automaton,
because that's implementation details.The "error" tracepoints should be enough for identifying problems with
realtime applications. Because errors from the monitors are unambiguous:- pagefault monitor: error means an RT task is raising pagefault
- sleep monitor: error means an RT task is delayed unboundedlyThat and a stacktrace (e.g. from perf) is enough to understand the problem.
That was all I need to identifying problems with pipewire using the monitors.
Quoted 6 lines
In the future, we can have other monitors whose warnings are ambiguous, and
a more detailed error message will be necessary. But for now, I think we
can keep it simple.
Mmh alright, makes sense, you can ignore it then.
Quoted 89 lines
Quoted 81 lines
Quoted 11 lines
+def
abbreviate_atoms(atoms: list[str])-> list[str]:
+ abbrs =list()
+ for atom in atoms:
+ size = 1
+ while True:
+ abbr = atom[:size]
+ if sum(a.startswith(abbr) for a in atoms) == 1:
+ break
+ size += 1
+ abbrs.append(abbr.lower())
+ return abbrsI get this is just a matter of preference, so feel free to ignore my
suggestion.
This abbreviation algorithm doesn't work too well with atoms starting
with the same substring and can produce some unexpected result:LTL_BLOCK_ON_RT_MUTEX: b,
LTL_KERNEL_THREAD: ke,
LTL_KTHREAD_SHOULD_STOP: kt,
LTL_NANOSLEEP: n,
LTL_PI_FUTEX: p,
LTL_RT: r,
LTL_SLEEP: s,
LTL_TASK_IS_MIGRATION:task_is_m,
LTL_TASK_IS_RCU:task_is_r,
LTL_WAKE: wa,
LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO:woken_by_e,
LTL_WOKEN_BY_HARDIRQ:woken_by_h,
LTL_WOKEN_BY_NMI:woken_by_n,"woken_by_*" and "task_is_*" atom can get unnecessarily long and while reading "kt" I might think about
kernel_thread.I was thinking about something like:
LTL_BLOCK_ON_RT_MUTEX:
b_o_r_m
LTL_KERNEL_THREAD:k_t
LTL_KTHREAD_SHOULD_STOP:k_s_s
LTL_NANOSLEEP: n
LTL_PI_FUTEX:p_f
LTL_RT: r
LTL_SLEEP: s
LTL_TASK_IS_MIGRATION:t_i_m
LTL_TASK_IS_RCU:t_i_r
LTL_WAKE: w
LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO:w_b_e_o_h_p
LTL_WOKEN_BY_HARDIRQ:w_b_h
LTL_WOKEN_BY_NMI:w_b_nor even
LTL_BLOCK_ON_RT_MUTEX:
b_m
LTL_KERNEL_THREAD:k_t
LTL_KTHREAD_SHOULD_STOP:k_s_s
LTL_NANOSLEEP: n
LTL_PI_FUTEX:p_f
LTL_RT: r
LTL_SLEEP: s
LTL_TASK_IS_MIGRATION:t_m
LTL_TASK_IS_RCU:t_r
LTL_WAKE: w
LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO:w_e_h_p
LTL_WOKEN_BY_HARDIRQ:w_h
LTL_WOKEN_BY_NMI:w_nI used the following code to come up with this:
def
abbreviate_atoms(atoms: list[str])-> list[str]:# completely arbitrary.. skip = [ "is", "by", "or", "and" ] def abbr (n, s): return '_'.join(word[:n] for word in s.lower().split('_') if word not in skip) for n in range(1, 32): abbrs = [abbr(n, a) for a in atoms] if len(abbrs) == len(set(abbrs)): return abbrsQuoted 7 lines
Which could even be tuned to use 2 letters per block instead of 1 (improving readability by a lot actually).. '
bl_on_rt_mu', 'ke_th', 'kt_sh_st', 'na', 'pi_fu', 'rt', 'sl', 'ta_mi',
'ta_rc', 'wa', 'wo_eq_hi_pr', 'wo_ha', 'wo_nm'What do you think?
Quoted 8 lines
Yes, this would be very nice. But as mentioned, this is mainly for debugging the monitors, not for end users. Therefore I don't want to spend
too much energy on it.Let me see how "nice" we can make it without spending too many hours. Thanks for the suggestion!
Sure, do what you see fit.
From my point of view the monitors (19-20/22) and synthesis look good.
Thanks,
Gabriele
Gabriele Monaco
maintainerRe: [PATCH v3 13/22] rv: Add support for LTL monitors
In reply to Nam CaoQuoted 177 lines · Nam Cao
Quoted 59 lines · Gabriele Monaco
Quoted 38 lines · Nam Cao
#endif /*
CONFIG_DA_MON_EVENTS_ID*/kernel/trace/rv/rv_trace.h +4
-0+#if CONFIG_LTL_MON_EVENTS_ID +TRACE_EVENT(event_ltl_monitor_id, + + TP_PROTO(struct task_struct *task, char *states, char*atoms, char *next),
kernel/trace/rv/rv_trace.h +20
-0+ +TP_ARGS (task, states, atoms, next), + +TP_STRUCT__entry ( + __string(comm, task->comm) + __field(pid_t, pid) + __string(states, states) + __string(atoms, atoms) +__string (next, next) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; +__assign_str (states); +__assign_str (atoms); +__assign_str (next); + ), + + TP_printk("%s[%d]: (%s) x (%s) -> (%s)",
__get_str(comm),__entry->pid,__get_str(states),kernel/trace/rv/rv_trace.h +10
-0+ __get_str(atoms), __get_str(next)) +); + +TRACE_EVENT(error_ltl_monitor_id, + + TP_PROTO(struct task_struct *task), + + TP_ARGS(task), + + TP_STRUCT__entry(kernel/trace/rv/rv_trace.h DECLARE_EVENT_CLASS(error_da_monitor_id,
Quoted 10 lines
kernel/trace/rv/rv_trace.h +10
-0+ __string(comm, task->comm) +__field (pid_t, pid) + ), + +TP_fast_assign ( + __assign_str(comm); + __entry->pid = task->pid; + ), + + TP_printk("%s[%d]: violation detected", __get_str(comm),In your workflow you're probably using events and errors together, but
wouldn't it help printing the atoms together with the violation detected?
At least to give a clue on the error in case the user doesn't want to
see the entire trace (which might be needed for a full debug though).Quoted 2 lines
The same could be said from reactors, the user doesn't have much information to infer what went wrong.
Actually my intention for the "event" tracepoints are only for debugging
the monitor itself. I don't want to bother users with the Büchi automaton,
because that's implementation details.The "error" tracepoints should be enough for identifying problems with
realtime applications. Because errors from the monitors are unambiguous:- pagefault monitor: error means an RT task is raising pagefault
- sleep monitor: error means an RT task is delayed unboundedlyThat and a stacktrace (e.g. from perf) is enough to understand the problem.
That was all I need to identifying problems with pipewire using the monitors.In the future, we can have other monitors whose warnings are ambiguous, and
a more detailed error message will be necessary. But for now, I think we
can keep it simple.Quoted 81 lines
Quoted 11 lines
+def
abbreviate_atoms(atoms: list[str])-> list[str]:
+ abbrs =list()
+ for atom in atoms:
+ size = 1
+ while True:
+ abbr = atom[:size]
+ if sum(a.startswith(abbr) for a in atoms) == 1:
+ break
+ size += 1
+ abbrs.append(abbr.lower())
+ return abbrsI get this is just a matter of preference, so feel free to ignore my
suggestion.
This abbreviation algorithm doesn't work too well with atoms starting
with the same substring and can produce some unexpected result:LTL_BLOCK_ON_RT_MUTEX: b,
LTL_KERNEL_THREAD: ke,
LTL_KTHREAD_SHOULD_STOP: kt,
LTL_NANOSLEEP: n,
LTL_PI_FUTEX: p,
LTL_RT: r,
LTL_SLEEP: s,
LTL_TASK_IS_MIGRATION:task_is_m,
LTL_TASK_IS_RCU:task_is_r,
LTL_WAKE: wa,
LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO:woken_by_e,
LTL_WOKEN_BY_HARDIRQ:woken_by_h,
LTL_WOKEN_BY_NMI:woken_by_n,"woken_by_*" and "task_is_*" atom can get unnecessarily long and while reading "kt" I might think about
kernel_thread.I was thinking about something like:
LTL_BLOCK_ON_RT_MUTEX:
b_o_r_m
LTL_KERNEL_THREAD:k_t
LTL_KTHREAD_SHOULD_STOP:k_s_s
LTL_NANOSLEEP: n
LTL_PI_FUTEX:p_f
LTL_RT: r
LTL_SLEEP: s
LTL_TASK_IS_MIGRATION:t_i_m
LTL_TASK_IS_RCU:t_i_r
LTL_WAKE: w
LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO:w_b_e_o_h_p
LTL_WOKEN_BY_HARDIRQ:w_b_h
LTL_WOKEN_BY_NMI:w_b_nor even
LTL_BLOCK_ON_RT_MUTEX:
b_m
LTL_KERNEL_THREAD:k_t
LTL_KTHREAD_SHOULD_STOP:k_s_s
LTL_NANOSLEEP: n
LTL_PI_FUTEX:p_f
LTL_RT: r
LTL_SLEEP: s
LTL_TASK_IS_MIGRATION:t_m
LTL_TASK_IS_RCU:t_r
LTL_WAKE: w
LTL_WOKEN_BY_EQUAL_OR_HIGHER_PRIO:w_e_h_p
LTL_WOKEN_BY_HARDIRQ:w_h
LTL_WOKEN_BY_NMI:w_nI used the following code to come up with this:
def
abbreviate_atoms(atoms: list[str])-> list[str]:# completely arbitrary.. skip = [ "is", "by", "or", "and" ] def abbr (n, s): return '_'.join(word[:n] for word in s.lower().split('_') if word not in skip) for n in range(1, 32): abbrs = [abbr(n, a) for a in atoms] if len(abbrs) == len(set(abbrs)): return abbrsQuoted 7 lines
Which could even be tuned to use 2 letters per block instead of 1 (improving readability by a lot actually).. '
bl_on_rt_mu', 'ke_th', 'kt_sh_st', 'na', 'pi_fu', 'rt', 'sl', 'ta_mi',
'ta_rc', 'wa', 'wo_eq_hi_pr', 'wo_ha', 'wo_nm'What do you think?
Quoted 8 lines
Yes, this would be very nice. But as mentioned, this is mainly for debugging the monitors, not for end users. Therefore I don't want to spend
too much energy on it.Let me see how "nice" we can make it without spending too many hours. Thanks for the suggestion!
By the way, no matter what you choose, just make sure the function cannot get stuck in an infinite loop (at most it can fail and tell the user to find better names).
Just tried the current parser with a simple monitor with states SLEEP, SLEEPABLE and SLEEPING, and I couldn't get through.
Cheers,
Gabriele
Re: [PATCH v3 13/22] rv: Add support for LTL monitors
Quoted 6 lines · Gabriele Monaco
By the way, no matter what you choose, just make sure the function cannot get stuck in an infinite loop (at most it can fail and tell the user to find better names).
Just tried the current parser with a simple monitor with states SLEEP, SLEEPABLE and SLEEPING, and I couldn't get through.
Right. Thanks for the tip!
Nam
Gabriele Monaco
maintainerRe: [PATCH v3 13/22] rv: Add support for LTL monitors
In reply to Nam CaoDocumentation/trace/rv/linear_temporal_logic.rst line 3
Quoted 10 lines · Nam Cao
Documentation/trace/rv/linear_temporal_logic.rst new file +3
-0@@ -0,0 +1,119 @@ +Introduction +============ +
Just noticed you misplaced the sections in this file, it should be like:
Linear Temporal Logic
=====================
Introduction
------------
[...]
Grammar
-------
[...]
Example linear temporal logic
-----------------------------
[...]
E.g. use === only for the page's title (which is missing) and --- for the sections, otherwise you get it oddly integrated in the index.
Thanks,
Gabriele
Quoted 147 lines
Documentation/trace/rv/linear_temporal_logic.rst new file +1
-0+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 +5
-0+intuitive. + +Many materials explain LTL in details. One book is:: + + Christel Baier aund Joost-Pieter Katoen: Principles of ModelChecking, The MIT Press, 2008.
Documentation/trace/rv/linear_temporal_logic.rst new file +5
-0+ +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 aBuchi automaton - a
+non-deterministic state machine which checks the satisfiability of the LTL. See+Documentation/trace/rv/monitor_synthesis.rstfor details on usingrvgen.Documentation/trace/rv/linear_temporal_logic.rst new file +7
-0+ +References +========== + +One book covering model checking and linear temporal logic is:: + + Christel Baier aund Joost-Pieter Katoen: Principles of ModelChecking, The MIT Press, 2008.
Documentation/trace/rv/linear_temporal_logic.rst new file +2
-0+ +For an example of using linear temporal logic in software testing,see::
+
+ Ruijie Meng, Zhen Dong, Jialin Li, Ivan Beschastnikh, and Abhik Roychoudhury. 2022. Linear-time
+ temporal logic guided greybox fuzzing. In Proceedings of the 44th International Conference on
+ Software Engineering (ICSE '22). Association for Computing Machinery, New York, NY, USA,
+ 1343–1355. https://doi.org/10.1145/3510003.3510082Documentation/trace/rv/linear_temporal_logic.rst new file +4
-0+ +The kernel's LTL monitor implementation is based on:: + + Gerth, R., Peled, D., Vardi, M.Y., Wolper, P. (1996). Simple On-the-fly Automatic Verification of
+ Linear Temporal Logic. In: Dembiński, P., Średniawa, M. (eds) Protocol Specification, Testing and
+ Verification XV. PSTV 1995. IFIP Advances in Information and Communication Technology. Springer,
+ Boston, MA. https://doi.org/10.1007/978-0-387-34892-6_1
PATCH v3 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
Re: [PATCH v3 14/22] rv: Add rtapp container monitor
Quoted 51 lines · Nam Cao
Add 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.Signed-off-by Nam Cao <[email protected]>---
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/Kconfigcreate mode 100644kernel/trace/rv/monitors/rtapp/rtapp.ccreate mode 100644kernel/trace/rv/monitors/rtapp/rtapp.hkernel/trace/rv/Kconfig +0
-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
configRV_REACTORSkernel/trace/rv/Makefile +0
-0@@ -12,6 +12,7 @@ obj-$(CONFIG_RV_MON_SNROC) +=
monitors/snroc/snroc.oobj-$(CONFIG_RV_MON_SCPD) +=monitors/scpd/scpd.oobj-$(CONFIG_RV_MON_SNEP) +=monitors/snep/snep.oobj-$(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.okernel/trace/rv/monitors/rtapp/Kconfig new file +0
-0
kernel/trace/rv/monitors/rtapp/Kconfig line 2
Quoted 2 lines
kernel/trace/rv/monitors/rtapp/Kconfig new file +2
-0@@ -0,0 +1,6 @@ +config RV_MON_RTAPP + depends on RV
depends on RV_PER_TASK_MONITORS >= 2
Not sure we want to be that picky, but what about making sure we can run the monitor in its entirety?
Ignore this if your use case doesn't expect both monitors to be run together.
Other than that
Thanks,
Gabriele
Quoted 58 lines
kernel/trace/rv/monitors/rtapp/Kconfig new file +3
-0+ bool "rtapp monitor" + help + Collection of monitors to check for common problems withreal-time application that cause
kernel/trace/rv/monitors/rtapp/Kconfig new file +1
-0+ unexpected latency.kernel/trace/rv/monitors/rtapp/rtapp.c new file +15
-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 detectingproblems with real-time applications",
kernel/trace/rv/monitors/rtapp/rtapp.c new file +19
-0+}; + +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 problemswith 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;
Re: [PATCH v3 14/22] rv: Add rtapp container monitor
Quoted 12 lines · Gabriele Monaco
kernel/trace/rv/monitors/rtapp/Kconfig line 2
Quoted 9 lines · Nam Cao
kernel/trace/rv/monitors/rtapp/Kconfig new file +2
-0@@ -0,0 +1,6 @@ +config RV_MON_RTAPP + depends on RVdepends on
RV_PER_TASK_MONITORS>= 2
Quoted 2 lines
Not sure we want to be that picky, but what about making sure we can run the monitor in its entirety?
That makes sense. But CONFIG_RV_PER_TASK_MONITORS doesn't exist yet at this point. I will add this in the commit adding CONFIG_RV_PER_TASK_MONITORS.
Quoted 5 lines
Ignore this if your use case doesn't expect both monitors to be run together.
Other than that
Reviewed-by Gabriele Monaco <[email protected]>
Thanks!
Nam
PATCH v3 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 v3 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 v3 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 v3 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 v3 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.
--- kernel/trace/rv/Kconfig | 1 + kernel/trace/rv/Makefile | 1 + kernel/trace/rv/monitors/pagefault/Kconfig | 11 +++ .../trace/rv/monitors/pagefault/pagefault.c | 80 +++++++++++++++++++ .../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, 166 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 +80 -0
80 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 v3 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 | 216 ++++++++++++++ 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, 555 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 +216 -0
216 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 + or KTHREAD_SHOULD_STOP + +ALLOWLIST = BLOCK_ON_RT_MUTEX + or TASK_IS_RCU + or TASK_IS_MIGRATION
Signature · 1 line
2.39.5
PATCH v3 21/22 Add documentation for rtapp monitor
In reply to Nam CaoAdd documentation describing the rtapp monitor.
--- Documentation/trace/rv/monitor_rtapp.rst | 107 +++++++++++++++++++++++ 1 file changed, 107 insertions(+) create mode 100644 Documentation/trace/rv/monitor_rtapp.rst
Documentation/trace/rv/monitor_rtapp.rst new file +107 -0
@@ -0,0 +1,107 @@ +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 + or KTHREAD_SHOULD_STOP + + ALLOWLIST = BLOCK_ON_RT_MUTEX + or TASK_IS_RCU + or TASK_IS_MIGRATION + +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. + - `KTHREAD_SHOULD_STOP`: a non-real-time thread may stop a real-time kernel thread by waking it + and waiting for it to exit (`kthread_stop()`). This wakeup is safe for real-time. + - `ALLOWLIST`: to handle known false positives with the kernel. + - `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 disabled for the duration.
Signature · 1 line
2.39.5
Gabriele Monaco
maintainerRe: [PATCH v3 21/22] rv: Add documentation for rtapp monitor
Quoted 10 lines · Nam Cao
Add documentation describing the rtapp monitor.
Reviewed-by Gabriele Monaco <[email protected]>Signed-off-by Nam Cao <[email protected]>---
Documentation/trace/rv/monitor_rtapp.rst | 107
+++++++++++++++++++++++1 file changed, 107 insertions(+)create mode 100644
Documentation/trace/rv/monitor_rtapp.rst
Documentation/trace/rv/monitor_rtapp.rst: WARNING: document isn't included in any toctree
You forgot adding this document to the index (and I forgot while reviewing ;) )
Thanks,
Gabriele
PATCH v3 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 | 9 +-------- include/linux/sched.h | 8 +++----- kernel/trace/rv/Kconfig | 9 +++++++++ kernel/trace/rv/rv.c | 8 ++++---- 4 files changed, 17 insertions(+), 17 deletions(-)
include/linux/rv.h +1 -8
@@ -74,14 +74,7 @@ struct ltl_monitor {};#endif /* CONFIG_RV_LTL_MONITOR */ -/* -* Per-task RV monitors count. 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. -*/ -#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
This patch was applied to riscv/linux.git (fixes) by Steven Rostedt (Google) <[email protected]>:
Hello:
This patch was applied to riscv/linux.git (fixes)
by Steven Rostedt (Google) <[email protected]>:
Quoted 10 lines · On Wed, 16 Apr 2025 08:51:06 +0200 you wrote:
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.
[...]
Here is the summary with links:
- [v3,18/22] riscv: mm: Add page fault trace points
https://git.kernel.org/riscv/c/a37c71ca412d
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html