[LTP] [PATCH 3/6] api/state_machine: Add validating state machines

[Richard Palethorpe]

Allows creating state machines where the state transitions are
validated. Also one can assert which states a line of code expects to
be executed in.

This is useful for verifying implicit or explicit state machines used
to process I/O events or data.

When a state violation is found a trace of previous state transitions
is printed.

Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
---
 include/tst_state_machine.h | 50 +++++++++++++++++++
 lib/tst_state_machine.c     | 98 +++++++++++++++++++++++++++++++++++++
 2 files changed, 148 insertions(+)
 create mode 100644 include/tst_state_machine.h
 create mode 100644 lib/tst_state_machine.c

diff --git a/include/tst_state_machine.h b/include/tst_state_machine.h
new file mode 100644
index 000000000..2e86535c6
--- /dev/null
+++ b/include/tst_state_machine.h
@@ -0,0 +1,50 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (c) 2022 SUSE LLC <rpalethorpe@suse.com>
+ */
+
+#include "inttypes.h"
+
+#ifndef TST_STATE_MACHINE_H
+#define TST_STATE_MACHINE_H
+
+#define TST_STATE_ANY (~(uint64_t)0)
+
+struct tst_state_matrix {
+	char *names[64];
+	uint64_t states[64];
+};
+
+struct tst_state_trace {
+	const char *file;
+	int line;
+	unsigned from;
+	unsigned to;
+};
+
+struct tst_state_mach {
+	const struct tst_state_matrix *mat;
+
+	unsigned top;
+	struct tst_state_trace ring[8];
+};
+
+#define TST_STATE_SET(mach, to) \
+	tst_state_set(__FILE__, __LINE__, mach, to)
+
+void tst_state_set(const char *const file, const int lineno,
+		  struct tst_state_mach *mach, unsigned to);
+
+#define TST_STATE_EXP(mach, mask) \
+	tst_state_exp(__FILE__, __LINE__, mach, mask)
+
+void tst_state_exp(const char *const file, const int lineno,
+		   struct tst_state_mach *mach, uint64_t mask);
+
+#define TST_STATE_GET(mach, mask) \
+	tst_state_get(__FILE__, __LINE__, mach, mask)
+
+unsigned tst_state_get(const char *const file, const int lineno,
+		       struct tst_state_mach *mach, uint64_t mask);
+
+#endif
diff --git a/lib/tst_state_machine.c b/lib/tst_state_machine.c
new file mode 100644
index 000000000..cb8ed79c4
--- /dev/null
+++ b/lib/tst_state_machine.c
@@ -0,0 +1,98 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (c) 2022 SUSE LLC <rpalethorpe@suse.com>
+ */
+
+#define _GNU_SOURCE
+#define TST_NO_DEFAULT_MAIN
+
+#include <unistd.h>
+#include "stdio.h"
+
+#include "tst_test.h"
+#include "tst_state_machine.h"
+
+static const char *state_trace(struct tst_state_mach *mach)
+{
+	static char buf[4096];
+	char *const *const names = mach->mat->names;
+	size_t off = 1;
+	unsigned c = 0, i;
+
+	buf[0] = '\n';
+
+	for (i = mach->top; c < 8; c++) {
+		const struct tst_state_trace *t = mach->ring + i;
+
+		if (!t->file)
+			break;
+
+		if (off >= sizeof(buf))
+			break;
+
+		off += snprintf(buf + off,
+				sizeof(buf) - off - 1,
+				"\t%s:%d %s (%u) -> %s (%u)\n",
+				t->file, t->line,
+				names[t->from], t->from,
+				names[t->to], t->to);
+
+		if (!i)
+			i = 7;
+		else
+			i--;
+	}
+
+	return buf;
+}
+
+static void state_trace_set(const char *const file, const int lineno,
+			    struct tst_state_trace *trace, unsigned from, unsigned to)
+{
+	trace->file = file;
+	trace->line = lineno;
+	trace->from = from;
+	trace->to = to;
+}
+
+void tst_state_set(const char *const file, const int lineno,
+		   struct tst_state_mach *mach, unsigned to)
+{
+	char *const *const names = mach->mat->names;
+	const unsigned cur = mach->ring[mach->top].to;
+
+	if (cur > 63)
+		tst_brk_(file, lineno, TBROK, "Attempting to transition from an invalid state: %u: %s", cur, state_trace(mach));
+
+	if (to > 63)
+		tst_brk_(file, lineno, TBROK, "Attempting to transition to invalid state: %u: %s", to, state_trace(mach));
+
+	if (!(mach->mat->states[cur] & (1 << to)))
+		tst_brk_(file, lineno, TBROK, "Invalid transition: %s (%u) -> %s (%u): %s", names[cur], cur, names[to], to, state_trace(mach));
+
+	if (++(mach->top) == 8)
+		mach->top = 0;
+
+	state_trace_set(file, lineno, &mach->ring[mach->top], cur, to);
+}
+
+unsigned tst_state_get(const char *const file, const int lineno,
+		       struct tst_state_mach *mach, uint64_t mask)
+{
+	char *const *const names = mach->mat->names;
+	const unsigned cur = mach->ring[mach->top].to;
+
+	if (mask & (1 << cur))
+		return cur;
+
+	tst_brk_(file, lineno, TBROK, "Should not reach here while in state: %s (%u): %s",
+		 names[cur], cur, state_trace(mach));
+
+	return cur;
+}
+
+void tst_state_exp(const char *const file, const int lineno,
+		   struct tst_state_mach *mach, uint64_t mask)
+{
+	tst_state_get(file, lineno, mach, mask);
+}
-- 
2.36.1