[PATCH v3 1/7] seqnum_ops: Introduce Sequence Number Ops

[Shuah Khan <skhan@linuxfoundation.org>]

Sequence Number api provides interfaces for unsigned atomic up counters.

There are a number of atomic_t usages in the kernel where atomic_t api
is used for counting sequence numbers and other statistical counters.
Several of these usages, convert atomic_read() and atomic_inc_return()
return values to unsigned. Introducing sequence number ops supports
these use-cases with a standard core-api.

Sequence Number ops provide interfaces to initialize, increment and get
the sequence number. These ops also check for overflow and log message to
indicate when overflow occurs.

Signed-off-by: Shuah Khan <skhan@linuxfoundation.org>
---
 Documentation/core-api/index.rst      |   1 +
 Documentation/core-api/seqnum_ops.rst |  53 ++++++++++
 MAINTAINERS                           |   7 ++
 include/linux/seqnum_ops.h            | 129 +++++++++++++++++++++++++
 lib/Kconfig                           |   9 ++
 lib/Makefile                          |   1 +
 lib/test_seqnum_ops.c                 | 133 ++++++++++++++++++++++++++
 7 files changed, 333 insertions(+)
 create mode 100644 Documentation/core-api/seqnum_ops.rst
 create mode 100644 include/linux/seqnum_ops.h
 create mode 100644 lib/test_seqnum_ops.c

diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index f1c9d20bd42d..adc8b1ae2acf 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -54,6 +54,7 @@ How Linux keeps everything from happening at the same time.  See
    :maxdepth: 1
 
    refcount-vs-atomic
+   seqnum_ops
    irq/index
    local_ops
    padata
diff --git a/Documentation/core-api/seqnum_ops.rst b/Documentation/core-api/seqnum_ops.rst
new file mode 100644
index 000000000000..ed4eba394799
--- /dev/null
+++ b/Documentation/core-api/seqnum_ops.rst
@@ -0,0 +1,53 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+.. include:: <isonum.txt>
+
+.. _seqnum_ops:
+
+==========================
+Sequence Number Operations
+==========================
+
+:Author: Shuah Khan
+:Copyright: |copy| 2021, The Linux Foundation
+:Copyright: |copy| 2021, Shuah Khan <skhan@linuxfoundation.org>
+
+Sequence Number api provides interfaces for unsigned up counters.
+
+Sequence Number Ops
+===================
+
+seqnum32 and seqnum64 types support implementing unsigned up counters. ::
+
+        struct seqnum32 { u32 seqnum; };
+        struct seqnum64 { u64 seqnum; };
+
+Initializers
+------------
+
+Interfaces for initializing sequence numbers. ::
+
+        #define SEQNUM_INIT(i)    { .seqnum = i }
+        seqnum32_init(seqnum, val)
+        seqnum64_init(seqnum, val)
+
+Increment interface
+-------------------
+
+Increments sequence number and returns the new value. Checks for overflow
+conditions and logs message when overflow occurs. This check is intended
+to help catch cases where overflow could lead to problems. ::
+
+        seqnum32_inc(seqnum): Calls atomic_inc_return(seqnum).
+        seqnum64_inc(seqnum): Calls atomic64_inc_return(seqnum).
+
+Return/get value interface
+--------------------------
+
+Returns sequence number value. ::
+
+        seqnum32_get() - return seqnum value.
+        seqnum64_get() - return seqnum value.
+
+.. warning::
+        seqnum32 wraps around to INT_MIN when it overflows.
diff --git a/MAINTAINERS b/MAINTAINERS
index cc1e6a5ee6e6..f9fe1438a8cd 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -16235,6 +16235,13 @@ S:	Maintained
 F:	Documentation/fb/sm712fb.rst
 F:	drivers/video/fbdev/sm712*
 
+SEQNUM OPS
+M:	Shuah Khan <skhan@linuxfoundation.org>
+L:	linux-kernel@vger.kernel.org
+S:	Maintained
+F:	include/linux/seqnum_ops.h
+F:	lib/test_seqnum_ops.c
+
 SIMPLE FIRMWARE INTERFACE (SFI)
 S:	Obsolete
 W:	http://simplefirmware.org/
diff --git a/include/linux/seqnum_ops.h b/include/linux/seqnum_ops.h
new file mode 100644
index 000000000000..e8d8481445d3
--- /dev/null
+++ b/include/linux/seqnum_ops.h
@@ -0,0 +1,129 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * seqnum_ops.h - Interfaces for unsigned atomic sequential up counters.
+ *
+ * Copyright (c) 2021 Shuah Khan <skhan@linuxfoundation.org>
+ * Copyright (c) 2021 The Linux Foundation
+ *
+ * Sequence Number functions provide support for unsgined atomic up
+ * counters.
+ *
+ * The interface provides:
+ * seqnumu32 & seqnumu64 functions:
+ *	initialization
+ *	increment and return
+ *
+ * seqnumu32 and seqnumu64 functions leverage/use atomic*_t ops to
+ * implement support for unsigned atomic up counters.
+ *
+ * Reference and API guide:
+ *	Documentation/core-api/seqnum_ops.rst for more information.
+ */
+
+#ifndef __LINUX_SEQNUM_OPS_H
+#define __LINUX_SEQNUM_OPS_H
+
+#include <linux/atomic.h>
+
+/**
+ * struct seqnum32 - Sequence number atomic counter
+ * @seqnum: atomic_t
+ *
+ **/
+struct seqnum32 {
+	u32 seqnum;
+};
+
+#define SEQNUM_INIT(i)		{ .seqnum = i }
+
+/*
+ * seqnum32_init() - initialize seqnum value
+ * @seq: struct seqnum32 pointer
+ *
+ */
+static inline void seqnum32_init(struct seqnum32 *seq, u32 val)
+{
+	seq->seqnum = val;
+}
+
+/*
+ * seqnum32_inc() - increment seqnum value and return the new value
+ * @seq: struct seqnum32 pointer
+ *
+ * Return u32
+ */
+static inline u32 seqnum32_inc(struct seqnum32 *seq)
+{
+	atomic_t val = ATOMIC_INIT(seq->seqnum);
+
+	seq->seqnum = (u32) atomic_inc_return(&val);
+	if (seq->seqnum >= UINT_MAX)
+		pr_info("Sequence Number overflow %u detected\n",
+			seq->seqnum);
+	return seq->seqnum;
+}
+
+/*
+ * seqnum32_get() - get seqnum value
+ * @seq: struct seqnum32 pointer
+ *
+ * Return u32
+ */
+static inline u32 seqnum32_get(struct seqnum32 *seq)
+{
+	return seq->seqnum;
+}
+
+/*
+ * struct seqnum64 - Sequential/Statistical atomic counter
+ * @seq: atomic64_t
+ *
+ */
+struct seqnum64 {
+	u64 seqnum;
+};
+
+/* Add to a global include/vdso/limits.h and fix all other UINT64_MAX
+ * duplicate defines?
+ */
+#define SEQ_UINT64_MAX	((u64)(~((u64) 0)))	/* 0xFFFFFFFFFFFFFFFF */
+
+/*
+ * seqnum64_init() - initialize seqnum value
+ * @seq: struct seqnum64 pointer
+ *
+ */
+static inline void seqnum64_init(struct seqnum64 *seq, u64 val)
+{
+	seq->seqnum = val;
+}
+
+/*
+ * seqnum64_inc() - increment seqnum value and return the new value
+ * @seq: struct seqnum64 pointer
+ *
+ * Return u64
+ */
+static inline u64 seqnum64_inc(struct seqnum64 *seq)
+{
+	atomic64_t val = ATOMIC_INIT(seq->seqnum);
+
+	seq->seqnum = (u64) atomic64_inc_return(&val);
+	if (seq->seqnum >= SEQ_UINT64_MAX)
+		pr_info("Sequence Number overflow %llu detected\n",
+			seq->seqnum);
+	return seq->seqnum;
+}
+
+/*
+ * seqnum64_get() - get seqnum value
+ * @seq: struct seqnum64 pointer
+ *
+ * Return u64
+ */
+static inline u64 seqnum64_get(struct seqnum64 *seq)
+{
+	return (u64) seq->seqnum;
+}
+
+#endif /* __LINUX_SEQNUM_OPS_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 46806332a8cc..518de7d34606 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -663,6 +663,15 @@ config OBJAGG
 config STRING_SELFTEST
 	tristate "Test string functions"
 
+config TEST_SEQNUM_OPS
+	tristate "Test Sequence Number Ops API"
+	help
+	   A test module for Sequence Number Ops API. A corresponding
+	   selftest can be used to test the Seqnum Ops API. Select this
+	   for testing Sequence Number Ops API.
+
+	   See Documentation/core-api/seqnum_ops.rst
+
 endmenu
 
 config GENERIC_IOREMAP
diff --git a/lib/Makefile b/lib/Makefile
index afeff05fa8c5..917686063cb3 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -101,6 +101,7 @@ obj-$(CONFIG_TEST_MEMINIT) += test_meminit.o
 obj-$(CONFIG_TEST_LOCKUP) += test_lockup.o
 obj-$(CONFIG_TEST_HMM) += test_hmm.o
 obj-$(CONFIG_TEST_FREE_PAGES) += test_free_pages.o
+obj-$(CONFIG_TEST_SEQNUM_OPS) += test_seqnum_ops.o
 
 #
 # CFLAGS for compiling floating point code inside the kernel. x86/Makefile turns
diff --git a/lib/test_seqnum_ops.c b/lib/test_seqnum_ops.c
new file mode 100644
index 000000000000..173278314f26
--- /dev/null
+++ b/lib/test_seqnum_ops.c
@@ -0,0 +1,133 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * test_seqnum_ops.c - Kernel module for testing Seqnum API
+ *
+ * Copyright (c) 2021 Shuah Khan <skhan@linuxfoundation.org>
+ * Copyright (c) 2021 The Linux Foundation
+ *
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/module.h>
+#include <linux/seqnum_ops.h>
+
+static inline void
+test_seqnum32_result(char *msg, u32 start, u32 end, u32 expected)
+{
+	pr_info("%s: %u to %u - %s\n",
+		msg, start, end,
+		((expected == end) ? "PASS" : "FAIL"));
+}
+
+
+static void test_seqnum32(void)
+{
+	u32 start_val = 0;
+	struct seqnum32 seq = SEQNUM_INIT(start_val);
+	u32 end_val;
+
+	end_val = seqnum32_inc(&seq);
+	test_seqnum32_result("Test increment",
+			     start_val, end_val, start_val+1);
+
+	/* Initialize sequence number to 0 */
+	seqnum32_init(&seq, 0);
+	end_val = seqnum32_inc(&seq);
+	/* If seqnum32_init() works correctly end_val should be 1 */
+	test_seqnum32_result("Test init", start_val, end_val, 1);
+
+	/* seqnum32_get() test for seqnum value == 1 */
+	start_val = end_val = seqnum32_get(&seq);
+	test_seqnum32_result("Test get", start_val, end_val, 1);
+}
+
+static void test_seqnum32_overflow(u32 val)
+{
+	u32 start_val;
+	struct seqnum32 seq;
+	u32 end_val;
+
+	pr_info("Test with start_val UINT_MAX-1 + %u\n", val);
+	start_val = UINT_MAX-1 + val;
+	seqnum32_init(&seq, start_val);
+	end_val = seqnum32_inc(&seq);
+	test_seqnum32_result("Test UINT_MAX limit compare with (val+1)",
+			     start_val, end_val, start_val+1);
+	test_seqnum32_result("Test UINT_MAX limit compare with (UINT_MAX)",
+			     start_val, end_val, UINT_MAX+val);
+}
+
+static inline void
+test_seqnum64_result(char *msg, u64 start, u64 end, u64 expected)
+{
+	pr_info("%s: %llu to %llu - %s\n",
+		msg, start, end,
+		((expected == end) ? "PASS" : "FAIL"));
+}
+
+static void test_seqnum64(void)
+{
+	u64 start_val = 0;
+	struct seqnum64 seq = SEQNUM_INIT(start_val);
+	u64 end_val;
+
+	end_val = seqnum64_inc(&seq);
+	test_seqnum64_result("Test increment",
+			     start_val, end_val, start_val+1);
+
+	/* Initialize sequence number to 0 */
+	seqnum64_init(&seq, start_val);
+	end_val = seqnum64_inc(&seq);
+
+	/* if seqnum642_init() works correctly end_val should be 1 */
+	test_seqnum64_result("Test init", start_val, end_val, 1);
+	/* seqnum64_get() test for seqnum value == 1 */
+	start_val = end_val = seqnum64_get(&seq);
+	test_seqnum64_result("Test get", start_val, end_val, 1);
+}
+
+static void test_seqnum64_overflow(u64 val)
+{
+	u64 start_val;
+	struct seqnum64 seq;
+	u64 end_val;
+
+	pr_info("Test with start_val SEQ_UINT64_MAX-1 + %llu\n", val);
+	start_val = SEQ_UINT64_MAX-1 + val;
+	seqnum64_init(&seq, start_val);
+	end_val = seqnum64_inc(&seq);
+	test_seqnum64_result("Test UINT64_MAX limit compare with (val+1)",
+			     start_val, end_val, start_val+1);
+	test_seqnum64_result("Test UINT64_MAX limit compare with (UINT64_MAX)",
+			     start_val, end_val, SEQ_UINT64_MAX+val);
+}
+
+static int __init test_seqnum_ops_init(void)
+{
+	pr_info("Start seqnum32_*() interfaces test\n");
+	test_seqnum32();
+	test_seqnum32_overflow(0);
+	test_seqnum32_overflow(5);
+	pr_info("End seqnum32_*() interfaces test\n\n");
+
+	pr_info("Start seqnum64_*() interfaces test\n");
+	test_seqnum64();
+	test_seqnum64_overflow(0);
+	test_seqnum64_overflow(5);
+	pr_info("End seqnum64_*() interfaces test\n\n");
+
+	return 0;
+}
+
+module_init(test_seqnum_ops_init);
+
+static void __exit test_seqnum_ops_exit(void)
+{
+	pr_info("exiting.\n");
+}
+
+module_exit(test_seqnum_ops_exit);
+
+MODULE_AUTHOR("Shuah Khan <skhan@linuxfoundation.org>");
+MODULE_LICENSE("GPL v2");
-- 
2.27.0