Skip to contentSkip to conversation

rv/ltl: Support the 'next' operator

PATCH In review Nam Cao 2 participants 8 messages Jul 11, 2025 – Jul 14, 2025

Subsystems (3)
lore
Share & tools
lore

Nam Cao

author
#0 lore raw

cover rv/ltl: Support the 'next' operator

Hi,

In the theory of linear temporal logic, there is also the 'next' unary operator defined as: next time, the operand must be true.

During my initial implementation, I thought kernel RV monitors would not have a use case for this operator. Therefore I omitted it.

However, me and Gabriele had a conversion off list, and he may have a use case for this operator.

Therefore, implement the theory completely and add the 'next' operator.

Nam Cao (2):
rv/ltl: Do not execute the Buchi automaton twice on start condition verification/rvgen: Support the 'next' operator

 .../trace/rv/linear_temporal_logic.rst        |  1 +
 include/rv/ltl_monitor.h                      |  4 ++-
 tools/verification/rvgen/rvgen/ltl2ba.py      | 26 +++++++++++++++++++
 3 files changed, 30 insertions(+), 1 deletion(-)
Signature · 1 line
2.39.5
author
#1 lore raw

PATCH 1/2 rv/ltl: Do not execute the Buchi automaton twice on start condition

On start condition of a Buchi automaton, the automaton is executed twice.

This is fine for now, as all the current LTL operators do not care about this. But it would break the 'next' operator, which will be introduced in a follow-up patch.

Prepare for the introduction of the 'next' operator, only execute the automaton once on start condition.

---
 include/rv/ltl_monitor.h | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
include/rv/ltl_monitor.h +3 -1
index 9a583125b566..67031a774e3d 100644
@@ -167,8 +167,10 @@ static void ltl_atom_update(struct task_struct *task, enum ltl_atom atom, bool v
 	ltl_atom_set(mon, atom, value);
 	ltl_atoms_fetch(task, mon);
 
-	if (!rv_ltl_valid_state(mon))
+	if (!rv_ltl_valid_state(mon)) {
 		ltl_attempt_start(task, mon);
+		return;
+	}
 
 	ltl_validate(task, mon);
 }
Signature · 1 line
2.39.5
author
#2 lore raw

PATCH 2/2 verification/rvgen: Support the 'next' operator

In reply to Nam Cao

The 'next' operator is a unary operator. It is defined as: "next time, the operand must be true".

Support this operator. For RV monitors, "next time" means the next invocation of ltl_validate().

---
 .../trace/rv/linear_temporal_logic.rst        |  1 +
 tools/verification/rvgen/rvgen/ltl2ba.py      | 26 +++++++++++++++++++
 2 files changed, 27 insertions(+)
Documentation/trace/rv/linear_temporal_logic.rst +1 -0
index 57f107fcf6dd..9eee09d9cacf 100644
@@ -41,6 +41,7 @@ Operands (opd):
 Unary Operators (unop):
     always
     eventually
+    next
     not
 
 Binary Operators (binop):
tools/verification/rvgen/rvgen/ltl2ba.py +26 -0
index d11840af7f5f..f14e6760ac3d 100644
@@ -19,6 +19,7 @@ from ply.yacc import yacc
 # Unary Operators (unop):
 #       always
 #       eventually
+#       next
 #       not
 #
 # Binary Operators (binop):
@@ -35,6 +36,7 @@ tokens = (
    'UNTIL',
    'ALWAYS',
    'EVENTUALLY',
+   'NEXT',
    'VARIABLE',
    'LITERAL',
    'NOT',
@@ -48,6 +50,7 @@ t_OR = r'or'
 t_IMPLY = r'imply'
 t_UNTIL = r'until'
 t_ALWAYS = r'always'
+t_NEXT = r'next'
 t_EVENTUALLY = r'eventually'
 t_VARIABLE = r'[A-Z_0-9]+'
 t_LITERAL = r'true|false'
@@ -327,6 +330,26 @@ class AlwaysOp(UnaryOp):
         # ![]F == <>(!F)
         return EventuallyOp(self.child.negate()).normalize()
 
+class NextOp(UnaryOp):
+    def normalize(self):
+        return self
+
+    def _is_temporal(self):
+        return True
+
+    def negate(self):
+        # not (next A) == next (not A)
+        self.child = self.child.negate()
+        return self
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) -> set[GraphNode]:
+        tmp = GraphNode(node.incoming,
+                        node.new,
+                        node.old | {n},
+                        node.next | {n.op.child})
+        return tmp.expand(node_set)
+
 class NotOp(UnaryOp):
     def __str__(self):
         return "!" + str(self.child)
@@ -452,12 +475,15 @@ def p_unop(p):
     '''
     unop : ALWAYS ltl
          | EVENTUALLY ltl
+         | NEXT ltl
          | NOT ltl
     '''
     if p[1] == "always":
         op = AlwaysOp(p[2])
     elif p[1] == "eventually":
         op = EventuallyOp(p[2])
+    elif p[1] == "next":
+        op = NextOp(p[2])
     elif p[1] == "not":
         op = NotOp(p[2])
     else:
Signature · 1 line
2.39.5
maintainer
#3 lore raw

Re: [PATCH 2/2] verification/rvgen: Support the 'next' operator

Quoted 8 lines · Nam Cao

The 'next' operator is a unary operator. It is defined as: "next time, the
operand must be true".

Support this operator. For RV monitors, "next time" means the next invocation of ltl_validate().

Hi Nam,

thanks for the series, I did a very stupid test like this:

RULE = always (SCHEDULING imply next SWITCH)

Despite the monitor working or not, the generator created code that doesn't build, specifically:

1. It creates a variable named switch
- sure I could change the name, but perhaps we could prepend
something to make sure local variables are not C keywords

2. It created unused variables in ltl_start
- _fill_atom_values creates all variables but _fill_start uses only
those where the .init field is true (maybe the model is wrong though)

Now, this specific model reports errors without the sched_switch_vain tracepoint which I'm introducing in another patch.

For it to work, I have to define it in such a way that scheduling becomes true at schedule_entry and becomes false right after the switch:

schedule_entry
SCHEDULING=true

sched_switch
SWITCH=true

schedule_exit
SCHEDULING=false
SWITCH=false

If I understood correctly that's intended behaviour since swapping the assignments in schedule_exit (or doing a pulse in sched_switch) would add another event when scheduling is true, which is against the next requirement.

Now I can't think of a way to rewrite the model to allow a pulse in sched_switch, that is /whenever scheduling turns to true, the next event is a switch/ instead of /any time scheduling is true, the next event is a switch/.

I tried something like:
RULE = always ((not SCHEDULING and next SCHEDULING) imply next
SWITCH)
but the parser got the two SCHEDULING as two different atoms, so I guess I did something I was not supposed to do..

Is the next operator only meaningful for atoms that are mutually exclusive (e.g. RED next GREEN, if GREEN is true RED turns to false) and/or when playing with ltl_atom_set without triggering validations?

What am I missing here?

Thanks,
Gabriele

Quoted 92 lines

---
 .../trace/rv/linear_temporal_logic.rst        |  1 + tools/verification/rvgen/rvgen/ltl2ba.py      | 26
+++++++++++++++++++

 2 files changed, 27 insertions(+)
Documentation/trace/rv/linear_temporal_logic.rst +0 -0
index 57f107fcf6dd..9eee09d9cacf 100644
@@ -41,6 +41,7 @@ Operands (opd):

 Unary Operators (unop):
     always
     eventually
+    next
     not

 Binary Operators (binop):

tools/verification/rvgen/rvgen/ltl2ba.py +2 -0
index d11840af7f5f..f14e6760ac3d 100644
@@ -19,6 +19,7 @@ from ply.yacc import yacc
  # Unary Operators (unop):
  #       always
  #       eventually
+#       next
  #       not
  #
  # Binary Operators (binop):
@@ -35,6 +36,7 @@ tokens = (
     'UNTIL',
     'ALWAYS',
     'EVENTUALLY',
+   'NEXT',
     'VARIABLE',
     'LITERAL',
     'NOT',
@@ -48,6 +50,7 @@ t_OR = r'or'

 t_IMPLY = r'imply'
 t_UNTIL = r'until'
 t_ALWAYS = r'always'
+t_NEXT = r'next'
 t_EVENTUALLY = r'eventually'
 t_VARIABLE = r'[A-Z_0-9]+'
 t_LITERAL = r'true|false'

tools/verification/rvgen/rvgen/ltl2ba.py +0 -0
@@ -327,6 +330,26 @@ class AlwaysOp(UnaryOp):
          # ![]F == <>(!F)
          return EventuallyOp(self.child.negate()).normalize()

tools/verification/rvgen/rvgen/ltl2ba.py +14 -0
+class NextOp(UnaryOp):
+    def normalize(self):
+        return self
+
+    def _is_temporal(self):
+        return True
+
+    def negate(self):
+        # not (next A) == next (not A)
+        self.child = self.child.negate()
+        return self
+
+    @staticmethod
+    def expand(n: ASTNode, node: GraphNode, node_set) ->

set[GraphNode]:
+        tmp = GraphNode(node.incoming,
+                        node.new,
+                        node.old | {n},
+                        node.next | {n.op.child}) +        return tmp.expand(node_set)
+
 class NotOp(UnaryOp):
     def __str__(self):
         return "!" + str(self.child)

tools/verification/rvgen/rvgen/ltl2ba.py +0 -0
@@ -452,12 +475,15 @@ def p_unop(p):

     '''
     unop : ALWAYS ltl
          | EVENTUALLY ltl
+         | NEXT ltl
          | NOT ltl
     '''
     if p[1] == "always":
         op = AlwaysOp(p[2])
     elif p[1] == "eventually":
         op = EventuallyOp(p[2])
+    elif p[1] == "next":
+        op = NextOp(p[2])
     elif p[1] == "not":
         op = NotOp(p[2])
     else:

author
#4 lore raw

Re: [PATCH 2/2] verification/rvgen: Support the 'next' operator

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

The 'next' operator is a unary operator. It is defined as: "next time, the
operand must be true".

Support this operator. For RV monitors, "next time" means the next invocation of ltl_validate().

Hi Nam,

thanks for the series, I did a very stupid test like this:

Quoted 8 lines

RULE = always (SCHEDULING imply next SWITCH)

Despite the monitor working or not, the generator created code that doesn't build, specifically:

1. It creates a variable named switch
- sure I could change the name, but perhaps we could prepend
something to make sure local variables are not C keywords

Right. Maybe we can prefix them with "ltl_".

Quoted 3 lines

2. It created unused variables in ltl_start
- _fill_atom_values creates all variables but _fill_start uses only
those where the .init field is true (maybe the model is wrong though)

Not sure what you mean by .init field, but yes the scripts always generate all variables, even if they are unused. Let me change the scripts.

Quoted 13 lines

Now, this specific model reports errors without the sched_switch_vain tracepoint which I'm introducing in another patch.

For it to work, I have to define it in such a way that scheduling becomes true at schedule_entry and becomes false right after the switch:

schedule_entry
SCHEDULING=true

sched_switch
SWITCH=true

Quoted 8 lines

schedule_exit
SCHEDULING=false
SWITCH=false

If I understood correctly that's intended behaviour since swapping the assignments in schedule_exit (or doing a pulse in sched_switch) would add another event when scheduling is true, which is against the next requirement.

Yes.

Quoted 8 lines

Now I can't think of a way to rewrite the model to allow a pulse in sched_switch, that is /whenever scheduling turns to true, the next event is a switch/ instead of /any time scheduling is true, the next event is a switch/.

I tried something like:
RULE = always ((not SCHEDULING and next SCHEDULING) imply next
SWITCH)

Be careful of operator precedence. This rule is also what I would suggest, but you need parentheses:

RULE = always (((not SCHEDULING) and (next SCHEDULING)) imply (next SWITCH))

because I think the parser understood your rule as:

RULE = always ((not (SCHEDULING and next SCHEDULING)) imply (next SWITCH))

Defining an operator precedence rules is on my TODO list. Unfortunately no theory defines this AFAIK, so it is not obvious how should they be defined.

Quoted 2 lines

but the parser got the two SCHEDULING as two different atoms, so I guess I did something I was not supposed to do..

This is just the parser's shortcoming. Currently it thinks that they are different variables.

Quoted 5 lines

Is the next operator only meaningful for atoms that are mutually exclusive (e.g. RED next GREEN, if GREEN is true RED turns to false) and/or when playing with ltl_atom_set without triggering validations?

What am I missing here?

I hope the above already answered your questions. Let me know if anything is unclear.

Thanks for the report, I will post some patches to address these problems with the scripts.

Best regards,
Nam

author
#5 lore raw

Re: [PATCH 2/2] verification/rvgen: Support the 'next' operator

Quoted 6 lines · Nam Cao
Quoted 5 lines · Gabriele Monaco

Now I can't think of a way to rewrite the model to allow a pulse in sched_switch, that is /whenever scheduling turns to true, the next event is a switch/ instead of /any time scheduling is true, the next event is a switch/.

Quoted 8 lines
Quoted 3 lines

I tried something like:
RULE = always ((not SCHEDULING and next SCHEDULING) imply next
SWITCH)

Be careful of operator precedence. This rule is also what I would suggest, but you need parentheses:

RULE = always (((not SCHEDULING) and (next SCHEDULING)) imply (next SWITCH))

Actually no, this also does not work. You need double 'next':

RULE = always (((not SCHEDULING) and (next SCHEDULING)) imply (next next SWITCH))

Or if you want to allow some other things to happen inbetween, then:

RULE = always (((not SCHEDULING) and (next SCHEDULING)) imply (SCHEDULING until SWITCH))

Best regards,
Nam

author
#6 lore raw

Re: [PATCH 2/2] verification/rvgen: Support the 'next' operator

Quoted 1 line · Nam Cao

RULE = always (((not SCHEDULING) and (next SCHEDULING)) imply (next next SWITCH))

Btw, I think this "(not X) and (next X)" seems very useful. So we could define a helper for this, perhaps something like "rising_edge".

Nam

maintainer Tested-by
#7 lore raw

Re: [PATCH 2/2] verification/rvgen: Support the 'next' operator

In reply to Nam Cao
Quoted 18 lines · Nam Cao
Quoted 17 lines · Nam Cao
Quoted 11 lines · Gabriele Monaco

Now I can't think of a way to rewrite the model to allow a pulse in
sched_switch, that is /whenever scheduling turns to true, the next
event is a switch/ instead of /any time scheduling is true, the next
event is a switch/.

I tried something like:
  RULE = always ((not SCHEDULING and next SCHEDULING) imply next SWITCH)

Be careful of operator precedence. This rule is also what I would suggest,
but you need parentheses:

Quoted 8 lines
Quoted 2 lines

    RULE = always (((not SCHEDULING) and (next SCHEDULING)) imply (next SWITCH))

Actually no, this also does not work. You need double 'next':

     RULE = always (((not SCHEDULING) and (next SCHEDULING)) imply (next next SWITCH))

Thanks! This one seems to work.

Quoted 1 line

Not sure what you mean by .init field

I meant in ltl2k there's this condition for variable usage but not for variable definition. I'm not sure exactly what it stands for.
_fill_start():

	...
	if not node.init:
		continue

But I guess you got what I meant already.

Quoted 3 lines

Btw, I think this "(not X) and (next X)" seems very useful. So we could
define a helper for this, perhaps something like "rising_edge".

Yeah good idea! I see myself mixing up in the future otherwise.. I guess you'd need to define also a falling_edge for its counterpart. Or perhaps making it more compact as just rising/falling (with good documentation or references to somewhere defining it).

Also we need to make clear this operator takes 2 instances, so whatever happens after (next) it needs a double next.

Maybe it gets complicated but in the future we might have also some nextN (next2, next3, etc. with a sensible limit not to explode the generated code) or something along the line.

Quoted 3 lines

Thanks for the report, I will post some patches to address these problems
with the scripts.

Great, thanks!
I'd say since those are unrelated and the next works as intended, feel free to add

Thanks again,
Gabriele