Skip to contentSkip to conversation

Linear temporal logic monitors for RT application

PATCH Superseded Nam Cao 3 participants 26 messages May 9, 2025 – Aug 10, 2025

Subsystems (11)
Documentation x86 MM core RISC-V +7 more subsystems

v7 of 13 Superseded 1 of 22 applied Latest is v13 →

lore
Share & tools
lore

Nam Cao

author
#0 lore raw

v7 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.

v6->v7 https://lore.kernel.org/lkml/[email protected]/
- Add missing parameter description for vpanic()
- Remove the now-redundant CFLAGS_fault.o for x86
- Change #if to #ifdef to resolve a build warning
- rtapp/sleep monitor:
+ Handle the case where an RT task "aborts" the sleep by setting state to TASK_RUNNING. This case previously caused a false positive. Fix it by adding "ABORT_SLEEP" as an RT-safe wake.
+ Also allow CLOCK_TAI for real-time tasks.

v5->v6 https://lore.kernel.org/lkml/[email protected]
- sleep monitor: Drop the block_on_rt_mutex tracepoints. The contention tracepoints are sufficient.

v4->v5 https://lore.kernel.org/lkml/[email protected]
- sleep monitor: Fix a false positive due to a race with waking and scheduling.
- sleep monitor: Add block_on_rt_mutex tracepoints and use them for BLOCK_ON_RT_MUTEX, instead of trace_sched_pi_setprio
- sleep monitor: tighten the rule on nanosleep: only clock_nanosleep() with TIMER_ABSTIME and CLOCK_MONOTONIC is allowed
- add comments explaining why it is correct to treat PI-boosted tasks as real-time tasks.

It should be noted that due to the changes in v5, 'perf' does not work as well as before, because sometimes the errors happen out of the real-time tasks' contexts. Fixing this is left for future work.

stress-ng is also far noisier in v5, because the rule on nanosleep is tightened.

v3->v4 https://lore.kernel.org/lkml/[email protected]
- support deadline tasks
- rtapp_sleep: use sched_pi_setprio tracepoint instead of contention tracepoints for BLOCK_ON_RT_MUTEX, so that proxy lock is covered.
- fix the scripts generating an "slightly" incorrect verification automaton
- makes rtapp monitor depends on RV_PER_TASK_MONITORS >= 2
- make the event tracepoint output a bit more readable
- some documentation's format fixes

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

Cc Petr Mladek <[email protected]>
Cc John Ogness <[email protected]>
Cc Sergey Senozhatsky <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Dave Hansen <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Catalin Marinas <[email protected]>
Cc Paul Walmsley <[email protected]>
Cc Palmer Dabbelt <[email protected]>
Cc Albert Ou <[email protected]>
Cc Alexandre Ghiti <[email protected]>

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              |   4 +-
 .../trace/rv/linear_temporal_logic.rst        | 122 ++++
 Documentation/trace/rv/monitor_rtapp.rst      | 116 ++++
 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/Makefile                          |   2 -
 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                                |  18 +-
 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   |  87 +++
 .../trace/rv/monitors/pagefault/pagefault.h   |  57 ++
 .../rv/monitors/pagefault/pagefault_trace.h   |  14 +
 kernel/trace/rv/monitors/rtapp/Kconfig        |   7 +
 kernel/trace/rv/monitors/rtapp/rtapp.c        |  33 ++
 kernel/trace/rv/monitors/rtapp/rtapp.h        |   3 +
 kernel/trace/rv/monitors/sleep/Kconfig        |  13 +
 kernel/trace/rv/monitors/sleep/sleep.c        | 234 ++++++++
 kernel/trace/rv/monitors/sleep/sleep.h        | 250 ++++++++
 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     |  22 +
 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       | 245 ++++++++
 .../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 +
 64 files changed, 2881 insertions(+), 552 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.h
Signature · 1 line
2.39.5
author
#1 lore raw

PATCH v7 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
index 422b75f58891..99c3801616d4 100644
@@ -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
author
#2 lore raw

PATCH v7 2/22 printk: Make vprintk_deferred() public

In reply to Nam Cao

vprintk_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
index 5b462029d03c..08f1775c60fd 100644
@@ -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, ...);
@@ -214,6 +215,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
index 48a24e7b309d..bbed41ad29cf 100644
@@ -72,7 +72,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
author
#3 lore raw

PATCH v7 3/22 panic: Add vpanic()

In reply to Nam Cao

vpanic() 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        | 18 +++++++++++++-----
 2 files changed, 16 insertions(+), 5 deletions(-)
include/linux/panic.h +3 -0
index 2494d51707ef..bcca63a02aef 100644
@@ -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 +13 -5
index a3889f38153d..278eae74bf17 100644
@@ -277,17 +277,17 @@ static void panic_other_cpus_shutdown(bool crash_kexec)
 }
 
 /**
- *	panic - halt the system
+ *	vpanic - halt the system
  *	@fmt: The text string to print
+ *	@args: Arguments for the format string
  *
  *	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 +338,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 +475,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
author
#4 lore raw

PATCH v7 4/22 Let the reactors take care of buffers

In reply to Nam Cao

Each RV monitor has one static buffer to send to the reactors. If multiple errors are detected simultaneously, the one buffer could be overwritten.

Instead, leave it to the reactors to handle buffering.

---
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
index 3452b5e4b29e..9428e62eb8e9 100644
@@ -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
index 0186ff4cbd0b..74c6bcc2c749 100644
@@ -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
index 178759dbf89f..2dae2916c05f 100644
@@ -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
index 9501ca886d83..740603670dd1 100644
@@ -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
author
#5 lore raw

PATCH v7 5/22 verification/dot2k: Make a separate dot2k_templates/Kconfig_container

In reply to Nam Cao

A 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
index 745d35a4a379..dd4b5528a4f2 100644
@@ -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
new file mode 100644
index 000000000000..a606111949c2
@@ -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
author
#6 lore raw

PATCH v7 6/22 verification/dot2k: Remove __buff_to_string()

In reply to Nam Cao

str.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
index dd4b5528a4f2..0922754454b9 100644
@@ -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
author
#7 lore raw

PATCH v7 7/22 verification/dot2k: Replace is_container() hack with subparsers

In reply to Nam Cao

dot2k is used for both generating deterministic automaton (DA) monitor and generating container monitor.

Generating DA monitor and generating container requires different parameters. This is implemented by peeking at sys.argv and check whether "--container" is specified, and use that information to make some parameters optional or required.

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
index 767064f415e7..133fb17d9d47 100644
@@ -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
index 0922754454b9..9ec99e297012 100644
@@ -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
author
#8 lore raw

PATCH v7 8/22 rename CONFIG_DA_MON_EVENTS to CONFIG_RV_MON_EVENTS

In reply to Nam Cao

CONFIG_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
index b39f36013ef2..6cdffc04b73c 100644
@@ -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
index e4077500a91d..e25d65fe432a 100644
@@ -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
author
#9 lore raw

PATCH v7 9/22 verification/dot2k: Prepare the frontend for LTL inclusion

In reply to 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

The old command:

python3 dot2/dot2k monitor -d wip.dot -t per_cpu

is equivalent to the new commands:

python3 rvgen 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
similarity index 55%
rename from tools/verification/dot2/Makefile
rename to tools/verification/rvgen/Makefile
index 021beb07a521..cea9c21c3bce 100644
@@ -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
similarity index 72%
rename from tools/verification/dot2/dot2k
rename to tools/verification/rvgen/__main__.py
index 133fb17d9d47..994d320ad2d1 100644
@@ -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
similarity index 97%
rename from tools/verification/dot2/dot2c
rename to tools/verification/rvgen/dot2c
index 3fe89ab88b65..bf0c67c5b66c 100644
@@ -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
similarity index 100%
rename from tools/verification/dot2/dot2k_templates/Kconfig
rename to tools/verification/rvgen/dot2k_templates/Kconfig
tools/verification/rvgen/dot2k_templates/Kconfig_container renamed from tools/verification/dot2/dot2k_templates/Kconfig_container +0 -0
similarity index 100%
rename from tools/verification/dot2/dot2k_templates/Kconfig_container
rename to tools/verification/rvgen/dot2k_templates/Kconfig_container
tools/verification/rvgen/dot2k_templates/main.c renamed from tools/verification/dot2/dot2k_templates/main.c +0 -0
similarity index 100%
rename from tools/verification/dot2/dot2k_templates/main.c
rename to tools/verification/rvgen/dot2k_templates/main.c
tools/verification/rvgen/dot2k_templates/main_container.c renamed from tools/verification/dot2/dot2k_templates/main_container.c +0 -0
similarity index 100%
rename from tools/verification/dot2/dot2k_templates/main_container.c
rename to tools/verification/rvgen/dot2k_templates/main_container.c
tools/verification/rvgen/dot2k_templates/main_container.h renamed from tools/verification/dot2/dot2k_templates/main_container.h +0 -0
similarity index 100%
rename from tools/verification/dot2/dot2k_templates/main_container.h
rename to tools/verification/rvgen/dot2k_templates/main_container.h
tools/verification/rvgen/dot2k_templates/trace.h renamed from tools/verification/dot2/dot2k_templates/trace.h +0 -0
similarity index 100%
rename from tools/verification/dot2/dot2k_templates/trace.h
rename to tools/verification/rvgen/dot2k_templates/trace.h
tools/verification/rvgen/rvgen/automata.py renamed from tools/verification/dot2/automata.py +0 -0
similarity index 100%
rename from tools/verification/dot2/automata.py
rename to tools/verification/rvgen/rvgen/automata.py
tools/verification/rvgen/rvgen/dot2c.py renamed from tools/verification/dot2/dot2c.py +1 -1
similarity index 99%
rename from tools/verification/dot2/dot2c.py
rename to tools/verification/rvgen/rvgen/dot2c.py
index fa2816ac7b61..6009caf568d9 100644
@@ -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
similarity index 98%
rename from tools/verification/dot2/dot2k.py
rename to tools/verification/rvgen/rvgen/dot2k.py
index 9ec99e297012..e29462413194 100644
@@ -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
author
#10 lore raw

PATCH v7 10/22 Documentation/rv: Prepare monitor synthesis document for LTL inclusion

In reply to Nam Cao

Monitor synthesis from deterministic automaton and linear temporal logic have a lot in common. Therefore a single document should describe both.

Change da_monitor_synthesis.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
index e80e0057feb4..8e411b76ec82 100644
@@ -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
similarity index 92%
rename from Documentation/trace/rv/da_monitor_synthesis.rst
rename to Documentation/trace/rv/monitor_synthesis.rst
index 0a92729c8a9b..85624062073b 100644
@@ -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
author
#11 lore raw

PATCH v7 11/22 verification/rvgen: Restructure the templates files

In reply to Nam Cao

To 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
index cea9c21c3bce..8d08825e7e54 100644
@@ -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
similarity index 100%
rename from tools/verification/rvgen/dot2k_templates/Kconfig
rename to tools/verification/rvgen/rvgen/templates/Kconfig
tools/verification/rvgen/rvgen/templates/container/Kconfig renamed from tools/verification/rvgen/dot2k_templates/Kconfig_container +0 -0
similarity index 100%
rename from tools/verification/rvgen/dot2k_templates/Kconfig_container
rename to tools/verification/rvgen/rvgen/templates/container/Kconfig
tools/verification/rvgen/rvgen/templates/container/main.c renamed from tools/verification/rvgen/dot2k_templates/main_container.c +0 -0
similarity index 100%
rename from tools/verification/rvgen/dot2k_templates/main_container.c
rename to tools/verification/rvgen/rvgen/templates/container/main.c
tools/verification/rvgen/rvgen/templates/container/main.h renamed from tools/verification/rvgen/dot2k_templates/main_container.h +0 -0
similarity index 100%
rename from tools/verification/rvgen/dot2k_templates/main_container.h
rename to tools/verification/rvgen/rvgen/templates/container/main.h
tools/verification/rvgen/rvgen/templates/dot2k/main.c renamed from tools/verification/rvgen/dot2k_templates/main.c +0 -0
similarity index 100%
rename from tools/verification/rvgen/dot2k_templates/main.c
rename to tools/verification/rvgen/rvgen/templates/dot2k/main.c
tools/verification/rvgen/rvgen/templates/dot2k/trace.h renamed from tools/verification/rvgen/dot2k_templates/trace.h +0 -0
similarity index 100%
rename from tools/verification/rvgen/dot2k_templates/trace.h
rename to tools/verification/rvgen/rvgen/templates/dot2k/trace.h
Signature · 1 line
2.39.5
author
#12 lore raw

PATCH v7 12/22 verification/rvgen: Restructure the classes to prepare for LTL inclusion

In reply to Nam Cao

Both 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] <- intended

This 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
index 8d08825e7e54..cca8c9ba82e8 100644
@@ -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
index 994d320ad2d1..63ecf0c37034 100644
@@ -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
new file mode 100644
index 000000000000..47d8ab2ad3ec
@@ -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
author
#13 lore raw

PATCH v7 13/22 Add support for LTL monitors

In reply to 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.

---
 Documentation/trace/rv/index.rst              |   1 +
 .../trace/rv/linear_temporal_logic.rst        | 122 ++++
 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       | 245 ++++++++
 .../rvgen/rvgen/templates/ltl2k/main.c        | 102 ++++
 .../rvgen/rvgen/templates/ltl2k/trace.h       |  14 +
 15 files changed, 1471 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
index 8e411b76ec82..2a27f6bc9429 100644
@@ -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 +122 -0

122 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
index c4b26cd8998b..ea57d4e12052 100644
@@ -2153,10 +2153,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
index 6cdffc04b73c..6e157f964991 100644
@@ -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
new file mode 100644
index 000000000000..1e288a076560
@@ -0,0 +1,3 @@
+__pycache__/
+parser.out
+parsetab.py
tools/verification/rvgen/Makefile +2 -0
index cca8c9ba82e8..cfc4056c1e87 100644
@@ -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
index 63ecf0c37034..fa6fc1f4de2f 100644
@@ -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 +245 -0

245 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
new file mode 100644
index 000000000000..49394c4b0f1c
@@ -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
author
#16 lore raw

PATCH v7 14/22 Add rtapp container monitor

In reply to 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.

---
 kernel/trace/rv/Kconfig                |  1 +
 kernel/trace/rv/Makefile               |  1 +
 kernel/trace/rv/monitors/rtapp/Kconfig |  6 +++++
 kernel/trace/rv/monitors/rtapp/rtapp.c | 33 ++++++++++++++++++++++++++
 kernel/trace/rv/monitors/rtapp/rtapp.h |  3 +++
 5 files changed, 44 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
index 6e157f964991..5c407d291661 100644
@@ -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
index f9b2cd0483c3..9b28c2419995 100644
@@ -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
new file mode 100644
index 000000000000..94689d66a79c
@@ -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 +33 -0
new file mode 100644
index 000000000000..fd75fc927d65
@@ -0,0 +1,33 @@
+// 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)
+{
+	return rv_register_monitor(&rv_rtapp, NULL);
+}
+
+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
new file mode 100644
index 000000000000..4c200d67c7f6
@@ -0,0 +1,3 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+extern struct rv_monitor rv_rtapp;
Signature · 1 line
2.39.5
author
#17 lore raw

PATCH v7 15/22 x86/tracing: Remove redundant trace_pagefault_key

In reply to Nam Cao

trace_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
deleted file mode 100644
index f0f9bcdb74d9..000000000000
@@ -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
index 6b1e87194809..34bc8214a2d7 100644
@@ -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
index 88e7f0f3bf62..7408bebdfde0 100644
@@ -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
index 84cfa179802c..99a783fd4691 100644
@@ -141,7 +141,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
deleted file mode 100644
index 03ae1caaa878..000000000000
@@ -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
index 296d294142c8..7e3e51fa1f95 100644
@@ -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
author
#18 lore raw

PATCH v7 16/22 x86/tracing: Move page fault trace points to generic

In reply to Nam Cao

Page 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/Makefile                                |  2 --
 arch/x86/mm/fault.c                                 |  2 +-
 .../asm/trace => include/trace/events}/exceptions.h | 13 ++++---------
 3 files changed, 5 insertions(+), 12 deletions(-)
 rename {arch/x86/include/asm/trace => include/trace/events}/exceptions.h (79%)
arch/x86/mm/Makefile +0 -2
index 32035d5be5a0..629a8bf12219 100644
@@ -34,8 +34,6 @@ obj-y				+= pat/
 CFLAGS_physaddr.o		:= -fno-stack-protector
 CFLAGS_mem_encrypt_identity.o	:= -fno-stack-protector
 
-CFLAGS_fault.o := -I $(src)/../include/asm/trace
-
 obj-$(CONFIG_X86_32)		+= pgtable_32.o iomap_32.o
 
 obj-$(CONFIG_HUGETLB_PAGE)	+= hugetlbpage.o
arch/x86/mm/fault.c +1 -1
index 7e3e51fa1f95..ad4cb1502316 100644
@@ -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
similarity index 79%
rename from arch/x86/include/asm/trace/exceptions.h
rename to include/trace/events/exceptions.h
index 34bc8214a2d7..a631f8de8917 100644
@@ -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
author
#19 lore raw

PATCH v7 17/22 arm64: mm: Add page fault trace points

In reply to Nam Cao

Add 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
index ec0a337891dd..55094030e377 100644
@@ -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
author
#20 lore raw

PATCH v7 18/22 riscv: mm: Add page fault trace points

In reply to Nam Cao

Add 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
index 0194324a0c50..04ed6f8acae4 100644
@@ -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
author
#21 lore raw

PATCH v7 19/22 Add rtapp_pagefault monitor

In reply to Nam Cao

Userspace real-time applications may have design flaws that they raise page faults in real-time threads, and thus have unexpected latencies.

Add an linear temporal logic monitor to detect this scenario.

---
 kernel/trace/rv/Kconfig                       |  1 +
 kernel/trace/rv/Makefile                      |  1 +
 kernel/trace/rv/monitors/pagefault/Kconfig    | 11 +++
 .../trace/rv/monitors/pagefault/pagefault.c   | 87 +++++++++++++++++++
 .../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, 173 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
index 5c407d291661..6f86d8501e87 100644
@@ -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
index 9b28c2419995..353ecf939d0e 100644
@@ -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
new file mode 100644
index 000000000000..b31dee208459
@@ -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 +87 -0

87 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
new file mode 100644
index 000000000000..fe1f82597b1a
@@ -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
index 12fe926ea853..cfa34af5551b 100644
@@ -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
new file mode 100644
index 000000000000..d7ce62102733
@@ -0,0 +1 @@
+RULE = always (RT imply not PAGEFAULT)
Signature · 1 line
2.39.5
author
#22 lore raw

PATCH v7 20/22 Add rtapp_sleep monitor

In reply to Nam Cao

Add 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

sleep: tai clock and abort_sleep

---
 kernel/trace/rv/Kconfig                      |   3 +-
 kernel/trace/rv/Makefile                     |   1 +
 kernel/trace/rv/monitors/sleep/Kconfig       |  13 +
 kernel/trace/rv/monitors/sleep/sleep.c       | 234 +++++++++++++++++
 kernel/trace/rv/monitors/sleep/sleep.h       | 250 +++++++++++++++++++
 kernel/trace/rv/monitors/sleep/sleep_trace.h |  14 ++
 kernel/trace/rv/rv_trace.h                   |   1 +
 tools/verification/models/rtapp/sleep.ltl    |  22 ++
 8 files changed, 537 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
index 6f86d8501e87..942d57575e67 100644
@@ -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
index 353ecf939d0e..13ec2944c665 100644
@@ -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
new file mode 100644
index 000000000000..d00aa1aae069
@@ -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 +234 -0

234 lines not on this page · raw message

kernel/trace/rv/monitors/sleep/sleep.h new file +250 -0

250 lines not on this page · raw message

kernel/trace/rv/monitors/sleep/sleep_trace.h new file +14 -0
new file mode 100644
index 000000000000..22eaf31da987
@@ -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
index cfa34af5551b..36ed96868dc4 100644
@@ -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 +22 -0
new file mode 100644
index 000000000000..7e2f11fa92b4
@@ -0,0 +1,22 @@
+RULE = always ((RT and 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 = FUTEX_WAIT_REQUEUE_PI
+                     or RT_FRIENDLY_NANOSLEEP
+
+RT_FRIENDLY_NANOSLEEP = CLOCK_NANOSLEEP
+                    and NANOSLEEP_TIMER_ABSTIME
+                    and (NANOSLEEP_CLOCK_MONOTONIC or NANOSLEEP_CLOCK_TAI)
+
+RT_FRIENDLY_WAKE = WOKEN_BY_EQUAL_OR_HIGHER_PRIO
+                or WOKEN_BY_HARDIRQ
+                or WOKEN_BY_NMI
+                or ABORT_SLEEP
+                or KTHREAD_SHOULD_STOP
+
+ALLOWLIST = BLOCK_ON_RT_MUTEX
+         or FUTEX_LOCK_PI
+         or TASK_IS_RCU
+         or TASK_IS_MIGRATION
Signature · 1 line
2.39.5
author
#23 lore raw

PATCH v7 21/22 Add documentation for rtapp monitor

In reply to Nam Cao

Add documentation describing the rtapp monitor.

---
 Documentation/trace/rv/index.rst         |   1 +
 Documentation/trace/rv/monitor_rtapp.rst | 116 +++++++++++++++++++++++
 2 files changed, 117 insertions(+)
 create mode 100644 Documentation/trace/rv/monitor_rtapp.rst
Documentation/trace/rv/index.rst +1 -0
index 2a27f6bc9429..a2812ac5cfeb 100644
@@ -14,3 +14,4 @@ Runtime Verification
    monitor_wip.rst
    monitor_wwnr.rst
    monitor_sched.rst
+   monitor_rtapp.rst
Documentation/trace/rv/monitor_rtapp.rst new file +116 -0

116 lines not on this page · raw message

Signature · 1 line
2.39.5
author
#24 lore raw

PATCH v7 22/22 Allow to configure the number of per-task monitor

In reply to Nam Cao

Now that there are 2 monitors for real-time applications, users may want to enable both of them simultaneously. Make the number of per-task monitor configurable. Default it to 2 for now.

---
 include/linux/rv.h                     | 9 +--------
 include/linux/sched.h                  | 8 +++-----
 kernel/trace/rv/Kconfig                | 9 +++++++++
 kernel/trace/rv/monitors/rtapp/Kconfig | 1 +
 kernel/trace/rv/rv.c                   | 8 ++++----
 5 files changed, 18 insertions(+), 17 deletions(-)
include/linux/rv.h +1 -8
index 2897aad16883..099b23c14e54 100644
@@ -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
index f96ac1982893..55fb32ce9657 100644
@@ -1634,12 +1634,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
index 942d57575e67..c11bf7e61ebf 100644
@@ -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/monitors/rtapp/Kconfig +1 -0
index 94689d66a79c..6a521c95a03f 100644
@@ -1,5 +1,6 @@
 config RV_MON_RTAPP
 	depends on RV
+	depends on RV_PER_TASK_MONITORS >= 2
 	bool "rtapp monitor"
 	help
 	  Collection of monitors to check for common problems with real-time application that cause
kernel/trace/rv/rv.c +4 -4
index e25d65fe432a..108429d16ec1 100644
@@ -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
maintainer
#14 lore raw

Re: [PATCH v7 13/22] rv: Add support for LTL monitors

In reply to Nam Cao
Quoted 10 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.

Quoted 6 lines

Add support for linear temporal logic runtime verification monitor.

For all the details, see the documentations added by this commit.

---

I tried generating some less than trivial monitors and I'm getting a few errors, please find below some questions/comments.
There are also some typos in the references.

Quoted 18 lines
Documentation/trace/rv/linear_temporal_logic.rst new file +12 -0
new file mode 100644
index 000000000000..6bf10d8e3761
@@ -0,0 +1,122 @@
+Linear temporal logic
+=====================
+
+Introduction
+------------
+
+Runtime verification monitor is a verification technique which checks that the kernel follows a
+specification. It does so by using tracepoints to monitor the kernel's execution trace, and
+verifying that the execution trace sastifies the specification.
+
+Initially, the specification can only be written in the form of deterministic automaton (DA).
+However, while attempting to implement DA monitors for some complex specifications, deterministic

Documentation/trace/rv/linear_temporal_logic.rst line 22

Quoted 10 lines
Documentation/trace/rv/linear_temporal_logic.rst new file +10 -0
+automaton is found to be inappropriate as the specification language. The automaton is complicated,
+hard to understand, and error-prone.
+
+Thus, RV monitors based on linear temporal logic (LTL) are introduced. This type of monitor uses LTL
+as specification instead of DA. For some cases, writing the specification as LTL is more concise and
+intuitive.
+
+Many materials explain LTL in details. One book is::
+
+  Christel Baier **aund** Joost-Pieter Katoen: Principles of Model Checking, The MIT Press, 2008.

Typo here and also in the references at the end of the page (omitted for brevity).

+ Christel Baier and Joost-Pieter Katoen: Principles of Model Checking, The MIT Press, 2008.

Quoted 339 lines

[...]

tools/verification/rvgen/rvgen/ltl2ba.py new file +87 -0
new file mode 100644
index 000000000000..aa5c3339aab8
@@ -0,0 +1,558 @@
+#!/usr/bin/env python3
+# SPDX-License-Identifier: GPL-2.0-only
+#
+# Implementation based on
+# Gerth, R., Peled, D., Vardi, M.Y., Wolper, P. (1996).
+# Simple On-the-fly Automatic Verification of Linear Temporal Logic.
+# https://doi.org/10.1007/978-0-387-34892-6_1
+# With extra optimizations
+
+from ply.lex import lex
+from ply.yacc import yacc
+
+# Grammar:
+# 	ltl ::= opd | ( ltl ) | ltl binop ltl | unop ltl
+#
+# Operands (opd):
+# 	true, false, user-defined names
+#
+# Unary Operators (unop):
+#       always
+#       eventually
+#       not
+#
+# Binary Operators (binop):
+#       until
+#       and
+#       or
+#       imply
+#       equivalent
+
+tokens = (
+   'AND',
+   'OR',
+   'IMPLY',
+   'UNTIL',
+   'ALWAYS',
+   'EVENTUALLY',
+   'VARIABLE',
+   'LITERAL',
+   'NOT',
+   'LPAREN',
+   'RPAREN',
+   'ASSIGN',
+)
+
+t_AND = r'and'
+t_OR = r'or'
+t_IMPLY = r'imply'
+t_UNTIL = r'until'
+t_ALWAYS = r'always'
+t_EVENTUALLY = r'eventually'
+t_VARIABLE = r'[A-Z_0-9]+'
+t_LITERAL = r'true|false'
+t_NOT = r'not'
+t_LPAREN = r'\('
+t_RPAREN = r'\)'
+t_ASSIGN = r'='
+t_ignore_COMMENT = r'\#.*'
+t_ignore = ' \t\n'
+
+def t_error(t):
+    raise ValueError("Illegal character '%s'" % t.value[0])
+
+lexer = lex()
+
+class GraphNode:
+    uid = 0
+
+    def __init__(self, incoming: set['GraphNode'], new, old, _next):
+        self.init = False
+        self.outgoing = set()
+        self.labels = set()
+        self.incoming = incoming.copy()
+        self.new = new.copy()
+        self.old = old.copy()
+        self.next = _next.copy()
+        self.id = GraphNode.uid
+        GraphNode.uid += 1
+
+    def expand(self, node_set):
+        if not self.new:
+            for nd in node_set:
+                if nd.old == self.old and nd.next == self.next:
+                    nd.incoming |= self.incoming
+                    return node_set
+
+            new_current_node = GraphNode({self}, self.next, set(),

set())
+            return new_current_node.expand({self} | node_set) +        n = self.new.pop()
+        return n.expand(self, node_set)

tools/verification/rvgen/rvgen/ltl2ba.py new file +77 -0
+
+    def __lt__(self, other):
+        return self.id < other.id
+
+class ASTNode:
+    uid = 1
+
+    def __init__(self, op):
+        self.op = op
+        self.id = ASTNode.uid
+        ASTNode.uid += 1
+
+    def __hash__(self):
+        return hash(self.op)
+
+    def __eq__(self, other):
+        return self is other
+
+    def __iter__(self):
+        yield self
+        yield from self.op
+
+    def negate(self):
+        self.op = self.op.negate()
+        return self
+
+    def expand(self, node, node_set):
+        return self.op.expand(self, node, node_set)
+
+    def __str__(self):
+        if isinstance(self.op, Literal):
+            return str(self.op.value)
+        elif isinstance(self.op, Variable):
+            return self.op.name.lower()
+        return "val" + str(self.id)
+
+    def normalize(self):
+        # Get rid of:
+        #   - ALWAYS
+        #   - EVENTUALLY
+        #   - IMPLY
+        # And move all the NOT to be inside
+        self.op = self.op.normalize()
+        return self
+
+class BinaryOp:
+    op_str = "not_supported"
+
+    def __init__(self, left: ASTNode, right: ASTNode):
+        self.left = left
+        self.right = right
+
+    def __hash__(self):
+        return hash((self.left, self.right))
+
+    def __iter__(self):
+        yield from self.left
+        yield from self.right
+
+    def normalize(self):
+        raise NotImplementedError
+
+    def negate(self):
+        raise NotImplementedError
+
+    def _is_temporal(self):
+        raise NotImplementedError
+
+    def is_temporal(self):
+        if self.left.op.is_temporal():
+            return True
+        if self.right.op.is_temporal():
+            return True
+        return self._is_temporal()
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        raise NotImplementedError

tools/verification/rvgen/rvgen/ltl2ba.py new file +18 -0
+
+class AndOp(BinaryOp):
+    op_str = '&&'
+
+    def __init__(self, left, right):
+        super().__init__(left, right)
+
+    def normalize(self):
+        return self
+
+    def negate(self):
+        return OrOp(self.left.negate(), self.right.negate())
+
+    def _is_temporal(self):
+        return False
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        if not n.op.is_temporal():
+            node.old.add(n)
+            return node.expand(node_set)
+
+        tmp = GraphNode(node.incoming,
+                        node.new | ({n.op.left, n.op.right} - node.old),
+                        node.old | {n},
+                        node.next)
+        return tmp.expand(node_set)

tools/verification/rvgen/rvgen/ltl2ba.py new file +18 -0
+
+class OrOp(BinaryOp):
+    op_str = '||'
+
+    def __init__(self, left, right):
+        super().__init__(left, right)
+
+    def normalize(self):
+        return self
+
+    def negate(self):
+        return AndOp(self.left.negate(), self.right.negate())
+
+    def _is_temporal(self):
+        return False
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        if not n.op.is_temporal():
+            node.old |= {n}
+            return node.expand(node_set)

tools/verification/rvgen/rvgen/ltl2ba.py new file +26 -0
+
+        node1 = GraphNode(node.incoming,
+                          node.new | ({n.op.left} - node.old),
+                          node.old | {n},
+                          node.next)
+        node2 = GraphNode(node.incoming,
+                          node.new | ({n.op.right} - node.old),
+                          node.old | {n},
+                          node.next)
+        return node2.expand(node1.expand(node_set))
+
+class UntilOp(BinaryOp):
+    def __init__(self, left, right):
+        super().__init__(left, right)
+
+    def normalize(self):
+        return self
+
+    def negate(self):
+        return VOp(self.left.negate(), self.right.negate())
+
+    def _is_temporal(self):
+        return True
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        node1 = GraphNode(node.incoming,
+                          node.new | ({n.op.left} - node.old), +                          node.old | {n},
+                          node.next | {n})
+        node2 = GraphNode(node.incoming,
+                          node.new | ({n.op.right} - node.old), +                          node.old | {n},
+                          node.next)
+        return node2.expand(node1.expand(node_set))

tools/verification/rvgen/rvgen/ltl2ba.py new file +16 -0
+
+class VOp(BinaryOp):
+    def __init__(self, left, right):
+        super().__init__(left, right)
+
+    def normalize(self):
+        return self
+
+    def negate(self):
+        return UntilOp(self.left.negate(), self.right.negate())
+
+    def _is_temporal(self):
+        return True
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        node1 = GraphNode(node.incoming,
+                          node.new | ({n.op.right} - node.old), +                          node.old | {n},
+                          node.next | {n})
+        node2 = GraphNode(node.incoming,
+                          node.new | ({n.op.left, n.op.right} - node.old),
+                          node.old | {n},
+                          node.next)
+        return node2.expand(node1.expand(node_set))

tools/verification/rvgen/rvgen/ltl2ba.py new file +47 -0
+
+class ImplyOp(BinaryOp):
+    def __init__(self, left, right):
+        super().__init__(left, right)
+
+    def normalize(self):
+        # P -> Q === !P | Q
+        return OrOp(self.left.negate(), self.right)
+
+    def _is_temporal(self):
+        return False
+
+    def negate(self):
+        # !(P -> Q) === !(!P | Q) === P & !Q
+        return AndOp(self.left, self.right.negate())
+
+class UnaryOp:
+    def __init__(self, child: ASTNode):
+        self.child = child
+
+    def __iter__(self):
+        yield from self.child
+
+    def __hash__(self):
+        return hash(self.child)
+
+    def normalize(self):
+        raise NotImplementedError
+
+    def _is_temporal(self):
+        raise NotImplementedError
+
+    def is_temporal(self):
+        if self.child.op.is_temporal():
+            return True
+        return self._is_temporal()
+
+    def negate(self):
+        raise NotImplementedError
+
+class EventuallyOp(UnaryOp):
+    def __init__(self, child):
+        super().__init__(child)
+
+    def __str__(self):
+        return "eventually " + str(self.child)
+

tools/verification/rvgen/rvgen/ltl2ba.py line 333

Quoted 10 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +10 -0
+    def normalize(self):
+        # <>F == true U F
+        return UntilOp(Literal(True), self.right)
+
+    def _is_temporal(self):
+        return True
+
+    def negate(self):
+        # !<>F == [](!F)
+        return AlwaysOp(self.right.negate()).normalize()

Shouldn't this be:
+        return AlwaysOp(self.child.negate()).normalize()

Quoted 16 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +16 -0
+
+class AlwaysOp(UnaryOp):
+    def __init__(self, child):
+        super().__init__(child)
+
+    def normalize(self):
+        # []F === !(true U !F) == false V F
+        new = ASTNode(Literal(False))
+        return VOp(new, self.child)
+
+    def _is_temporal(self):
+        return True
+
+    def negate(self):
+        # ![]F == <>(!F)
+        return EventuallyOp(self.left,
Quoted 1 line

self.right.negate()).normalize()

Shouldn't this be:
+        return EventuallyOp(self.child.negate()).normalize()

Quoted 130 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +19 -0
+
+class NotOp(UnaryOp):
+    def __init__(self, child):
+        super().__init__(child)
+
+    def __str__(self):
+        return "!" + str(self.child)
+
+    def normalize(self):
+        return self.child.op.negate()
+
+    def negate(self):
+        return self.child.op
+
+    def _is_temporal(self):
+        return False
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        for f in node.old:
+            if n.op.child is f:
+                return node_set
+        node.old |= {n}
+        return node.expand(node_set)

tools/verification/rvgen/rvgen/ltl2ba.py new file +23 -0
+
+class Variable:
+    def __init__(self, name: str):
+        self.name = name
+
+    def __hash__(self):
+        return hash(self.name)
+
+    def __iter__(self):
+        yield from ()
+
+    def negate(self):
+        new = ASTNode(self)
+        return NotOp(new)
+
+    def normalize(self):
+        return self
+
+    def is_temporal(self):
+        return False
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        for f in node.old:
+            if isinstance(f, NotOp) and f.op.child is n:
+                return node_set
+        node.old |= {n}
+        return node.expand(node_set)

tools/verification/rvgen/rvgen/ltl2ba.py new file +28 -0
+
+class Literal:
+    def __init__(self, value: bool):
+        self.value = value
+
+    def __iter__(self):
+        yield from ()
+
+    def __hash__(self):
+        return hash(self.value)
+
+    def __str__(self):
+        if self.value:
+            return "true"
+        return "false"
+
+    def negate(self):
+        self.value = not self.value
+        return self
+
+    def normalize(self):
+        return self
+
+    def is_temporal(self):
+        return False
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        if not n.op.value:
+            return node_set
+        node.old |= {n}
+        return node.expand(node_set)

tools/verification/rvgen/rvgen/ltl2ba.py new file +43 -0
+
+def p_spec(p):
+    '''
+    spec : assign
+         | assign spec
+    '''
+    if len(p) == 3:
+        p[2].append(p[1])
+        p[0] = p[2]
+    else:
+        p[0] = [p[1]]
+
+def p_assign(p):
+    '''
+    assign : VARIABLE ASSIGN ltl
+    '''
+    p[0] = (p[1], p[3])
+
+def p_ltl(p):
+    '''
+    ltl : opd
+        | binop
+        | unop
+    '''
+    p[0] = p[1]
+
+def p_opd(p):
+    '''
+    opd : VARIABLE
+        | LITERAL
+        | LPAREN ltl RPAREN
+    '''
+    if p[1] == "true":
+        p[0] = ASTNode(Literal(True))
+    elif p[1] == "false":
+        p[0] = ASTNode(Literal(False))
+    elif p[1] == '(':
+        p[0] = p[2]
+    else:
+        p[0] = ASTNode(Variable(p[1]))
+
+def p_unop(p):
+    '''

tools/verification/rvgen/rvgen/ltl2ba.py line 486

Quoted 10 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +10 -0
+    unop : ALWAYS ltl
+         | EVENTUALLY ltl
+         | NOT ltl
+    '''
+    if p[1] == "always":
+        op = AlwaysOp(p[2])
+    if p[1] == "eventually":
+        op = EventuallyOp(p[2])
+    if p[1] == "not":
+        op = NotOp(p[2])

Pylint is complaining about this one, wouldn't it be better changing it to an if/elif chain and addding:

else:
raise ValueError("Invalid unary operator: %s" % p[1])

Quoted 25 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +25 -0
+
+    p[0] = ASTNode(op)
+
+def p_binop(p):
+    '''
+    binop : opd UNTIL ltl
+          | opd AND ltl
+          | opd OR ltl
+          | opd IMPLY ltl
+    '''
+    if p[2] == "and":
+        op = AndOp(p[1], p[3])
+    elif p[2] == "until":
+        op = UntilOp(p[1], p[3])
+    elif p[2] == "or":
+        op = OrOp(p[1], p[3])
+    elif p[2] == "imply":
+        op = ImplyOp(p[1], p[3])
+    else:
+        raise ValueError("Invalid binary operator: %s" % p[2])
+
+    p[0] = ASTNode(op)
+
+parser = yacc()
+

tools/verification/rvgen/rvgen/ltl2ba.py line 521

Quoted 10 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +10 -0
+def parse_ltl(s: str) -> ASTNode:
+    spec = parser.parse(s)
+
+    subexpr = dict()
+
+    for assign in spec:
+        if assign[0] == "RULE":
+            rule = assign[1]
+        else:
+            subexpr[assign[0]] = assign[1]

rule may be undefined here (but I guess python will just say variable rule is undefined and it would be quite clear the ltl didn't start with a rule.

I'm still getting a few more errors but my model may be to blame, still need to play a bit.

Cheers,
Gabriele

Quoted 448 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +25 -0
+
+    for node in rule:
+        if not isinstance(node.op, Variable):
+            continue
+        replace = subexpr.get(node.op.name)
+        if replace is not None:
+            node.op = replace.op
+
+    return rule
+
+def create_graph(s: str):
+    atoms = set()
+
+    ltl = parse_ltl(s)
+    for c in ltl:
+        c.normalize()
+        if isinstance(c.op, Variable):
+            atoms.add(c.op.name)
+
+    init = GraphNode(set(), set(), set(), set())
+    head = GraphNode({init}, {ltl}, set(), set())
+    graph = sorted(head.expand(set()))
+
+    for i, node in enumerate(graph):
+        # The id assignment during graph generation has gaps.

Reassign them
+        node.id = i

tools/verification/rvgen/rvgen/ltl2ba.py new file +11 -0
+
+        for incoming in node.incoming:
+            if incoming is init:
+                node.init = True
+            else:
+                incoming.outgoing.add(node)
+        for o in node.old:
+            if not o.op.is_temporal():
+                node.labels.add(str(o))
+
+    return sorted(atoms), graph, ltl
tools/verification/rvgen/rvgen/ltl2k.py new file +44 -0
new file mode 100644
index 000000000000..b8da9094fb4f
@@ -0,0 +1,245 @@
+#!/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]:
+    def shorten(s: str) -> str:
+        skip = ["is", "by", "or", "and"]
+        return '_'.join([x[:2] for x in s.lower().split('_') if x

not in skip])

tools/verification/rvgen/rvgen/ltl2k.py new file +17 -0
+
+    abbrs = []
+    for atom in atoms:
+        for i in range(len(atom), -1, -1):
+            if sum(a.startswith(atom[:i]) for a in atoms) > 1:
+                break
+        share = atom[:i]
+        unique = atom[i:]
+        abbrs.append((shorten(share) + shorten(unique)))
+    return abbrs
+
+class ltl2k(generator.Monitor):
+    template_dir = "ltl2k"
+
+    def __init__(self, file_path, MonitorType, extra_params={}):
+        if MonitorType != "per_task":
+            raise NotImplementedError("Only per_task monitor is

supported for LTL")
+        super().__init__(extra_params)
+        with open(file_path) as f:
+            self.atoms, self.ba, self.ltl = ltl2ba.create_graph(f.read())
+        self.atoms_abbr = abbreviate_atoms(self.atoms) +        self.name = extra_params.get("model_name") +        if not self.name:
+            self.name = Path(file_path).stem

tools/verification/rvgen/rvgen/ltl2k.py new file +11 -0
+
+    def _fill_states(self) -> str:
+        buf = [
+            "enum ltl_buchi_state {",
+        ]
+
+        for node in self.ba:
+            buf.append("\tS%i," % node.id)
+        buf.append("\tRV_NUM_BA_STATES")
+        buf.append("};")
+        buf.append("static_assert(RV_NUM_BA_STATES <=

RV_MAX_BA_STATES);")
+        return buf
+
+    def _fill_atoms(self):
+        buf = ["enum ltl_atom {"]
+        for a in sorted(self.atoms):
+            buf.append("\tLTL_%s," % a)
+        buf.append("\tLTL_NUM_ATOM")
+        buf.append("};")
+        buf.append("static_assert(LTL_NUM_ATOM <= RV_MAX_LTL_ATOM);")
+        return buf

tools/verification/rvgen/rvgen/ltl2k.py new file +27 -0
+
+    def _fill_atoms_to_string(self):
+        buf = [
+            "static const char *ltl_atom_str(enum ltl_atom atom)",
+            "{",
+            "\tstatic const char *const names[] = {"
+        ]
+
+        for name in self.atoms_abbr:
+            buf.append("\t\t\"%s\"," % name)
+
+        buf.extend([
+            "\t};",
+            "",
+            "\treturn names[atom];",
+            "}"
+        ])
+        return buf
+
+    def _fill_atom_values(self):
+        buf = []
+        for node in self.ltl:
+            if node.op.is_temporal():
+                continue
+
+            if isinstance(node.op, ltl2ba.Variable):
+                buf.append("\tbool %s = test_bit(LTL_%s, mon-
Quoted 1 line

atoms);" % (node, node.op.name))

+            elif isinstance(node.op, ltl2ba.AndOp):
+                buf.append("\tbool %s = %s && %s;" % (node, node.op.left, node.op.right))
+            elif isinstance(node.op, ltl2ba.OrOp):
+                buf.append("\tbool %s = %s || %s;" % (node, node.op.left, node.op.right))
+            elif isinstance(node.op, ltl2ba.NotOp):
+                buf.append("\tbool %s = !%s;" % (node, node.op.child))
+        buf.reverse()

tools/verification/rvgen/rvgen/ltl2k.py new file +10 -0
+
+        buf2 = []
+        for line in buf:
+            buf2.extend(break_long_line(line, "\t     "))
+        return buf2
+
+    def _fill_transitions(self):
+        buf = [
+            "static void",
+            "ltl_possible_next_states(struct ltl_monitor *mon,

unsigned int state, unsigned long *next)",
+            "{"
+        ]
+        buf.extend(self._fill_atom_values())
+        buf.extend([
+            "",
+            "\tswitch (state) {"
+        ])

tools/verification/rvgen/rvgen/ltl2k.py new file +24 -0
+
+        for node in self.ba:
+            buf.append("\tcase S%i:" % node.id)
+
+            for o in sorted(node.outgoing):
+                line   = "\t\tif "
+                indent = "\t\t   "
+
+                line += build_condition_string(o)
+                lines = break_long_line(line, indent)
+                buf.extend(lines)
+
+                buf.append("\t\t\t__set_bit(S%i, next);" % o.id)
+            buf.append("\t\tbreak;")
+        buf.extend([
+            "\t}",
+            "}"
+        ])
+
+        return buf
+
+    def _fill_start(self):
+        buf = [
+            "static void ltl_start(struct task_struct *task, struct

ltl_monitor *mon)",
+            "{"
+        ]
+        buf.extend(self._fill_atom_values())
+        buf.append("")

tools/verification/rvgen/rvgen/ltl2k.py new file +19 -0
+
+        for node in self.ba:
+            if not node.init:
+                continue
+
+            line   = "\tif "
+            indent = "\t   "
+
+            line += build_condition_string(node)
+            lines = break_long_line(line, indent)
+            buf.extend(lines)
+
+            buf.append("\t\t__set_bit(S%i, mon->states);" % node.id)
+        buf.append("}")
+        return buf
+
+    def fill_tracepoint_handlers_skel(self):
+        buff = []
+        buff.append("static void handle_example_event(void *data, /*

XXX: fill header */)")
+        buff.append("{")
+        buff.append("\tltl_atom_update(task, LTL_%s, true/false);" % self.atoms[0])
+        buff.append("}")
+        buff.append("")
+        return '\n'.join(buff)
+
+    def fill_tracepoint_attach_probe(self):
+        return "\trv_attach_trace_probe(\"%s\", /* XXX: tracepoint */, handle_example_event);" \
+                % self.name
+
+    def fill_tracepoint_detach_helper(self):
+        return "\trv_detach_trace_probe(\"%s\", /* XXX: tracepoint */, handle_sample_event);" \
+                % self.name
+
+    def fill_atoms_init(self):
+        buff = []
+        for a in self.atoms:
+            buff.append("\tltl_atom_set(mon, LTL_%s, true/false);" %
a)
+        return '\n'.join(buff)

tools/verification/rvgen/rvgen/ltl2k.py new file +37 -0
+
+    def fill_model_h(self):
+        buf = [
+            "/* SPDX-License-Identifier: GPL-2.0 */",
+            "",
+            "#include <linux/rv.h>",
+            "",
+            "#define MONITOR_NAME " + self.name,
+            ""
+        ]
+
+        buf.extend(self._fill_atoms())
+        buf.append('')
+
+        buf.extend(self._fill_atoms_to_string())
+        buf.append('')
+
+        buf.extend(self._fill_states())
+        buf.append('')
+
+        buf.extend(self._fill_start())
+        buf.append('')
+
+        buf.extend(self._fill_transitions())
+        buf.append('')
+
+        return '\n'.join(buf)
+
+    def fill_monitor_class_type(self):
+        return "LTL_MON_EVENTS_ID"
+
+    def fill_monitor_class(self):
+        return "ltl_monitor_id"
+
+    def fill_main_c(self):
+        main_c = super().fill_main_c()
+        main_c = main_c.replace("%%ATOMS_INIT%%",

self.fill_atoms_init())

tools/verification/rvgen/rvgen/ltl2k.py new file +2 -0
+
+        return main_c
tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +20 -0
new file mode 100644
index 000000000000..2f3c4d642746
@@ -0,0 +1,102 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/ftrace.h>
+#include <linux/tracepoint.h>
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/init.h>
+#include <linux/rv.h>
+#include <rv/instrumentation.h>
+
+#define MODULE_NAME "%%MODEL_NAME%%"
+
+/*
+ * XXX: include required tracepoint headers, e.g.,
+ * #include <trace/events/sched.h>
+ */
+#include <rv_trace.h>
+%%INCLUDE_PARENT%%
+
+/*
+ * This is the self-generated part of the monitor. Generally, there

is no need
+ * to touch this section.
+ */

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +4 -0
+#include "%%MODEL_NAME%%.h"
+#include <rv/ltl_monitor.h>
+
+static void ltl_atoms_fetch(struct task_struct *task, struct

ltl_monitor *mon)

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +3 -0
+{
+	/*
+	 * This is called everytime the Buchi automaton is

triggered.

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +2 -0
+	 *
+	 * This function could be used to fetch the atomic

propositions which are expensive to

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +1 -0
+	 * trace. It is possible only if the atomic proposition does

not need to be updated at

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +3 -0
+	 * precise time.
+	 *
+	 * It is recommended to use tracepoints and

ltl_atom_update() instead.

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +4 -0
+	 */
+}
+
+static void ltl_atoms_init(struct task_struct *task, struct

ltl_monitor *mon, bool task_creation)

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +3 -0
+{
+	/*
+	 * This should initialize as many atomic propositions as

possible.

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +2 -0
+	 *
+	 * @task_creation indicates whether the task is being

created. This is false if the task is

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +9 -0
+	 * already running before the monitor is enabled.
+	 */
+%%ATOMS_INIT%%
+}
+
+/*
+ * This is the instrumentation part of the monitor.
+ *
+ * This is the section where manual work is required. Here the

kernel events
+ * are translated into model's event.
+ */
+%%TRACEPOINT_HANDLERS_SKEL%%

tools/verification/rvgen/rvgen/templates/ltl2k/main.c new file +46 -0
+static int enable_%%MODEL_NAME%%(void)
+{
+	int retval;
+
+	retval = ltl_monitor_init();
+	if (retval)
+		return retval;
+
+%%TRACEPOINT_ATTACH%%
+
+	return 0;
+}
+
+static void disable_%%MODEL_NAME%%(void)
+{
+%%TRACEPOINT_DETACH%%
+
+	ltl_monitor_destroy();
+}
+
+/*
+ * This is the monitor register section.
+ */
+static struct rv_monitor rv_%%MODEL_NAME%% = {
+	.name = "%%MODEL_NAME%%",
+	.description = "%%DESCRIPTION%%",
+	.enable = enable_%%MODEL_NAME%%,
+	.disable = disable_%%MODEL_NAME%%,
+};
+
+static int __init register_%%MODEL_NAME%%(void)
+{
+	return rv_register_monitor(&rv_%%MODEL_NAME%%, %%PARENT%%);
+}
+
+static void __exit unregister_%%MODEL_NAME%%(void)
+{
+	rv_unregister_monitor(&rv_%%MODEL_NAME%%);
+}
+
+module_init(register_%%MODEL_NAME%%);
+module_exit(unregister_%%MODEL_NAME%%);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR(/* TODO */);
+MODULE_DESCRIPTION("%%MODEL_NAME%%: %%DESCRIPTION%%");
tools/verification/rvgen/rvgen/templates/ltl2k/trace.h new file +9 -0
new file mode 100644
index 000000000000..49394c4b0f1c
@@ -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),

tools/verification/rvgen/rvgen/templates/ltl2k/trace.h new file +5 -0
+	     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%% */
author
#15 lore raw

Re: [PATCH v7 13/22] rv: Add support for LTL monitors

Quoted 8 lines · Gabriele Monaco
Quoted 4 lines · Nam Cao

+    def negate(self):
+        # ![]F == <>(!F)
+        return EventuallyOp(self.left,
self.right.negate()).normalize()

Shouldn't this be:
+        return EventuallyOp(self.child.negate()).normalize()

Yes, remnant of the old version :(

Quoted 13 lines
Quoted 4 lines

+def p_unop(p):
+    '''
+    unop : ALWAYS ltl
+         | EVENTUALLY ltl

Quoted 8 lines

+         | NOT ltl
+    '''
+    if p[1] == "always":
+        op = AlwaysOp(p[2])
+    if p[1] == "eventually":
+        op = EventuallyOp(p[2])
+    if p[1] == "not":
+        op = NotOp(p[2])

Quoted 5 lines

Pylint is complaining about this one, wouldn't it be better changing it to an if/elif chain and addding:

else:
raise ValueError("Invalid unary operator: %s" % p[1])

lex should have failed due to unknown token before getting here. But yes, this would be a good change.

Quoted 5 lines
Quoted 5 lines
tools/verification/rvgen/rvgen/ltl2ba.py new file +5 -0
+def parse_ltl(s: str) -> ASTNode:
+    spec = parser.parse(s)
+
+    subexpr = dict()
+
Quoted 8 lines
Quoted 5 lines

+    for assign in spec:
+        if assign[0] == "RULE":
+            rule = assign[1]
+        else:
+            subexpr[assign[0]] = assign[1]

rule may be undefined here (but I guess python will just say variable rule is undefined and it would be quite clear the ltl didn't start with a rule.

We could make the error verbose.

Quoted 2 lines

I'm still getting a few more errors but my model may be to blame, still need to play a bit.

Feel free to send me the model. Maybe it is a bug in the script. But I would be happy to help debugging your model as well.

Thanks for the feedback,
Nam

#25 lore raw
In reply to Nam Cao
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 Fri, 9 May 2025 10:11:59 +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:
- [v7,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