From nobody Tue Oct 7 08:14:42 2025 Received: from galois.linutronix.de (Galois.linutronix.de [193.142.43.55]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 24B142BF3CF; Fri, 11 Jul 2025 13:17:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=193.142.43.55 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1752239870; cv=none; b=I3+TarBr06U5zf+KkAbxJF6dlPnG8mFRp1QeswFtFCK5ILQmUCncCkWB12RLST5AGjBKlehLH1CUiDi2icW7BxmEGpgfcRkaGgcZM47RW3wUGWYd1OWc6Pxwv+TFjuomzFTgCgtD3iZWd0G/38OkueOASJrxBpQgri9D31Su3zc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1752239870; c=relaxed/simple; bh=2sx+KHYNlqmjmePdZpE8eMjypL3Mb80fn3kZxiey0PA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=LCIjwRg2UChOtFxNMNCRzY+k6Sd1wu4Dom7ThN6Hnvy/6kHlinDWuOphHClRLxBZvsgmxQs97HsrelQKtHDIGKcfAyALQD7LiZUU+wP8CBF02l1peeNuh9ZpsPp/prWjnltv9ez4H8xUULRNEXDSxHKxlmb+TVeEHDd1g3gkpGM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linutronix.de; spf=pass smtp.mailfrom=linutronix.de; dkim=pass (2048-bit key) header.d=linutronix.de header.i=@linutronix.de header.b=qkn4WlHO; dkim=permerror (0-bit key) header.d=linutronix.de header.i=@linutronix.de header.b=ho3SL/ik; arc=none smtp.client-ip=193.142.43.55 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linutronix.de Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linutronix.de Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=linutronix.de header.i=@linutronix.de header.b="qkn4WlHO"; dkim=permerror (0-bit key) header.d=linutronix.de header.i=@linutronix.de header.b="ho3SL/ik" From: Nam Cao DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1752239867; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=kmSeSCaMLTxjNle1bg96T1FnAl3KVrKCCr1RGJGYED4=; b=qkn4WlHORQUrFdQhPExQFdwDpontQI2oyBhYQz9t1T91kDagDvRjVH00EDS1PuLmpJkwmJ k8C/L1oBiZrOgEu37vgwCSiMV4WFpzmjVRPge078ymPiRWdTqluOd4kbDQ2qLZBA9TNc/M 78OnznMULS8oq4nfKAMGTHrK9P9Lc3KK5EcwH9t2oLoJmGK8q7eqbaCpPoWlxxyexD+sWW qy5ijG4J0MTw7EwoHTo5O8gwPUoFawnHHsy6N4nUfQ+Onkl6OOJKYIwTplDDoQzLIFtquI oWcvb4HF3vBfoL3AkeE7wry6HQ7Lr8EEA+twRVAOsD+xu1cbHFabVPgDtQO7Jg== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1752239867; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=kmSeSCaMLTxjNle1bg96T1FnAl3KVrKCCr1RGJGYED4=; b=ho3SL/ik71cNHV7Z0fe1DIrlJnkTfnPjH89WsDnFYQ1T8dLlVuATes6EbnzeRuCQGb3lvM 63KmJSt1FIlBovDg== To: Steven Rostedt , John Ogness , Masami Hiramatsu , Mathieu Desnoyers , Gabriele Monaco , linux-trace-kernel@vger.kernel.org, linux-kernel@vger.kernel.org Cc: Nam Cao Subject: [PATCH 1/2] rv/ltl: Do not execute the Buchi automaton twice on start condition Date: Fri, 11 Jul 2025 15:17:37 +0200 Message-Id: <9379f4e7b9c1c69a6dca3e20a22936c850a25ca7.1752239482.git.namcao@linutronix.de> In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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. Signed-off-by: Nam Cao --- include/rv/ltl_monitor.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/include/rv/ltl_monitor.h b/include/rv/ltl_monitor.h index 9a583125b566..67031a774e3d 100644 --- a/include/rv/ltl_monitor.h +++ b/include/rv/ltl_monitor.h @@ -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); =20 - if (!rv_ltl_valid_state(mon)) + if (!rv_ltl_valid_state(mon)) { ltl_attempt_start(task, mon); + return; + } =20 ltl_validate(task, mon); } --=20 2.39.5 From nobody Tue Oct 7 08:14:42 2025 Received: from galois.linutronix.de (Galois.linutronix.de [193.142.43.55]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 24B932D2389; Fri, 11 Jul 2025 13:17:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=193.142.43.55 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1752239871; cv=none; b=IWk72vNjG9gUPyTwhqZs5i0CJAR9QU3yvlEeHj/k/CCjLGmJYIRky5Pwi49wgnWUF5sdqKoya61l2HlgrkhFGdGc9FC1IX8bfbmnmakCrp06fhGpmUNACpNFd+ZwrHe1owpGM2aMtlliMt48O5p6Imo0WcOdh6TuQw6zNIfnWvs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1752239871; c=relaxed/simple; bh=lw4OZfHfnI2cVyTNXtVLShhvrDH7ooKpfetSbu5fhRU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=s2rpPtlqgQBlGswPGGU7aKfFR7ijWG9fhQKzyl23Cu9luZPflkYWC8h1H3fO9a02ij4peFyc3DA04OOp3+skkHMW1S6hJ5eSGO2A/Ty99cm48bB5zPlDWCQzBOheopCcrWt8kBzSRz/pJBwiVlMEm2L8DiMKrx8uMmIK/mXtyNQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linutronix.de; spf=pass smtp.mailfrom=linutronix.de; dkim=pass (2048-bit key) header.d=linutronix.de header.i=@linutronix.de header.b=yyYHfoZk; dkim=permerror (0-bit key) header.d=linutronix.de header.i=@linutronix.de header.b=WgYXpM25; arc=none smtp.client-ip=193.142.43.55 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linutronix.de Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linutronix.de Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=linutronix.de header.i=@linutronix.de header.b="yyYHfoZk"; dkim=permerror (0-bit key) header.d=linutronix.de header.i=@linutronix.de header.b="WgYXpM25" From: Nam Cao DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1752239867; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=INu2KwXEZtpuyVFsgoK8s73FgdhQHIbE4KfHUbehgOU=; b=yyYHfoZkWZ1PibU39z748ytleE2WmXwUF+wUZcJYeVfHrm3e9/QhPDWqbzuVRyhpBCKaSL DSDQVs4k1koG26Lt49CEMNl8iD1iht08m5FJ/9GdHEfV8ehomMzLXblNNPvQ3pmsu3tgzk P+fcFSyCVLULw5DbeLTkx4v1AKXdrRFUvWoibaI0CHLIsoSbgc/A0tNAmn3bt63K5kwt2v zmEtv47RneL0JTdW7SQoEKRsml4Uyju0cdCvuBQ91MwUwo/lN2MIoGYSpR2fqtOXw8sWOV +SbUY4smsstnApo75pgSlapq/BjPHVGWevx2Desavq4R9mwb3ixYhFBxvHaItg== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1752239867; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=INu2KwXEZtpuyVFsgoK8s73FgdhQHIbE4KfHUbehgOU=; b=WgYXpM258leJ9ZiEYDxJgmBqOjOmgAKB1VfnnhQaJlSDMRFaHXwL79lvvJnnK0LQkcjqfa WpZv++/TzT8KWhDA== To: Steven Rostedt , John Ogness , Masami Hiramatsu , Mathieu Desnoyers , Gabriele Monaco , linux-trace-kernel@vger.kernel.org, linux-kernel@vger.kernel.org Cc: Nam Cao Subject: [PATCH 2/2] verification/rvgen: Support the 'next' operator Date: Fri, 11 Jul 2025 15:17:38 +0200 Message-Id: <9c32cec04dd18d2e956fddd84b0e0a2503daa75a.1752239482.git.namcao@linutronix.de> In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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(). Signed-off-by: Nam Cao Tested-by: Gabriele Monaco --- .../trace/rv/linear_temporal_logic.rst | 1 + tools/verification/rvgen/rvgen/ltl2ba.py | 26 +++++++++++++++++++ 2 files changed, 27 insertions(+) diff --git a/Documentation/trace/rv/linear_temporal_logic.rst b/Documentati= on/trace/rv/linear_temporal_logic.rst index 57f107fcf6dd..9eee09d9cacf 100644 --- a/Documentation/trace/rv/linear_temporal_logic.rst +++ b/Documentation/trace/rv/linear_temporal_logic.rst @@ -41,6 +41,7 @@ Operands (opd): Unary Operators (unop): always eventually + next not =20 Binary Operators (binop): diff --git a/tools/verification/rvgen/rvgen/ltl2ba.py b/tools/verification/= rvgen/rvgen/ltl2ba.py index d11840af7f5f..f14e6760ac3d 100644 --- a/tools/verification/rvgen/rvgen/ltl2ba.py +++ b/tools/verification/rvgen/rvgen/ltl2ba.py @@ -19,6 +19,7 @@ from ply.yacc import yacc # Unary Operators (unop): # always # eventually +# next # not # # Binary Operators (binop): @@ -35,6 +36,7 @@ tokens =3D ( 'UNTIL', 'ALWAYS', 'EVENTUALLY', + 'NEXT', 'VARIABLE', 'LITERAL', 'NOT', @@ -48,6 +50,7 @@ t_OR =3D r'or' t_IMPLY =3D r'imply' t_UNTIL =3D r'until' t_ALWAYS =3D r'always' +t_NEXT =3D r'next' t_EVENTUALLY =3D r'eventually' t_VARIABLE =3D r'[A-Z_0-9]+' t_LITERAL =3D r'true|false' @@ -327,6 +330,26 @@ class AlwaysOp(UnaryOp): # ![]F =3D=3D <>(!F) return EventuallyOp(self.child.negate()).normalize() =20 +class NextOp(UnaryOp): + def normalize(self): + return self + + def _is_temporal(self): + return True + + def negate(self): + # not (next A) =3D=3D next (not A) + self.child =3D self.child.negate() + return self + + @staticmethod + def expand(n: ASTNode, node: GraphNode, node_set) -> set[GraphNode]: + tmp =3D 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] =3D=3D "always": op =3D AlwaysOp(p[2]) elif p[1] =3D=3D "eventually": op =3D EventuallyOp(p[2]) + elif p[1] =3D=3D "next": + op =3D NextOp(p[2]) elif p[1] =3D=3D "not": op =3D NotOp(p[2]) else: --=20 2.39.5