[PATCH v2 01/13] seqnum_ops: Introduce Sequence Number Ops
From: Shuah Khan
Date: Fri Nov 13 2020 - 12:46:40 EST
Sequence Number api provides interfaces for unsigned atomic up counters
leveraging atomic_t and atomic64_t ops underneath.
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.
The atomic_t api provides a wide range of atomic operations as a base
api to implement atomic counters, bitops, spinlock interfaces. The usages
also evolved into being used for resource lifetimes and state management.
The refcount_t api was introduced to address resource lifetime problems
related to atomic_t wrapping. There is a large overlap between the
atomic_t api used for resource lifetimes and just counters, stats, and
sequence numbers. It has become difficult to differentiate between the
atomic_t usages that should be converted to refcount_t and the ones that
can be left alone. Introducing seqnum_ops to wrap the usages that are
stats, counters, sequence numbers makes it easier for tools that scan
for underflow and overflow on atomic_t usages to detect overflow and
underflows to scan just the cases that are prone to errors.
In addition, to supporting sequence number use-cases, Sequence Number Ops
helps differentiate atomic_t counter usages from atomic_t usages that guard
object lifetimes, hence prone to overflow and underflow errors from up
counting use-cases.
Signed-off-by: Shuah Khan <skhan@xxxxxxxxxxxxxxxxxxx>
---
Documentation/core-api/atomic_ops.rst | 4 +
Documentation/core-api/index.rst | 1 +
Documentation/core-api/seqnum_ops.rst | 80 +++++++++++++++++
MAINTAINERS | 7 ++
include/linux/seqnum_ops.h | 116 +++++++++++++++++++++++++
lib/Kconfig | 9 ++
lib/Makefile | 1 +
lib/test_seqnum_ops.c | 119 ++++++++++++++++++++++++++
8 files changed, 337 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/atomic_ops.rst b/Documentation/core-api/atomic_ops.rst
index 724583453e1f..762cbc0947e7 100644
--- a/Documentation/core-api/atomic_ops.rst
+++ b/Documentation/core-api/atomic_ops.rst
@@ -1,3 +1,7 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+.. _atomic_ops:
+
=======================================================
Semantics and Behavior of Atomic and Bitmask Operations
=======================================================
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index 69171b1799f2..be958afe757c 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -55,6 +55,7 @@ How Linux keeps everything from happening at the same time. See
atomic_ops
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..10b775a9ac05
--- /dev/null
+++ b/Documentation/core-api/seqnum_ops.rst
@@ -0,0 +1,80 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+.. include:: <isonum.txt>
+
+.. _seqnum_ops:
+
+==========================
+Sequence Number Operations
+==========================
+
+:Author: Shuah Khan
+:Copyright: |copy| 2020, The Linux Foundation
+:Copyright: |copy| 2020, Shuah Khan <skhan@xxxxxxxxxxxxxxxxxxx>
+
+Sequence Number api provides interfaces for unsigned up counters
+leveraging atomic_t and atomic64_t ops underneath.
+
+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.
+
+The atomic_t api provides a wide range of atomic operations as a base
+api to implement atomic counters, bitops, spinlock interfaces. The usages
+also evolved into being used for resource lifetimes and state management.
+The refcount_t api was introduced to address resource lifetime problems
+related to atomic_t wrapping. There is a large overlap between the
+atomic_t api used for resource lifetimes and just counters, stats, and
+sequence numbers. It has become difficult to differentiate between the
+atomic_t usages that should be converted to refcount_t and the ones that
+can be left alone. Introducing seqnum_ops to wrap the usages that are
+stats, counters, sequence numbers makes it easier for tools that scan
+for underflow and overflow on atomic_t usages to detect overflow and
+underflows to scan just the cases that are prone to errors.
+
+In addition, to supporting sequence number use-cases, Sequence Number Ops
+helps differentiate atomic_t counter usages from atomic_t usages that guard
+object lifetimes, hence prone to overflow and underflow errors from up
+counting use-cases.
+
+Sequence Number Ops
+===================
+
+seqnum32 and seqnum64 types use atomic_t and atomic64_t underneath to
+leverage atomic_t api, to provide increment by 1 and return new value
+and fetch current value interfaces necessary to support unsigned up
+counters. ::
+
+ struct seqnum32 { atomic_t seqnum; };
+ struct seqnum64 { atomic64_t seqnum; };
+
+Please see :ref:`Documentation/core-api/atomic_ops.rst <atomic_ops>` for
+information on the Semantics and Behavior of Atomic operations.
+
+Initializers
+------------
+
+Interfaces for initializing sequence numbers are write operations which
+in turn invoke their ``ATOMIC_INIT() and atomic_set()`` counterparts ::
+
+ #define SEQNUM_INIT(i) { .seqnum = ATOMIC_INIT(i) }
+ seqnum32_init() --> atomic_set() to 0
+ seqnum64_init() --> atomic64_set() to 0
+
+Increment interface
+-------------------
+
+Increments sequence number and returns the new value. ::
+
+ seqnum32_inc_return() --> (u32) atomic_inc_return(seqnum)
+ seqnum64_inc_return() --> (u64) atomic64_inc_return(seqnum)
+
+Fetch interface
+---------------
+
+Fetched and returns current sequence number value. ::
+
+ seqnum32_fetch() --> (u32) atomic_add_return(0, seqnum)
+ seqnum64_fetch() --> (u64) atomic64_add_return(0, seqnum)
diff --git a/MAINTAINERS b/MAINTAINERS
index b516bb34a8d5..c83a6f05610b 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -15977,6 +15977,13 @@ S: Maintained
F: Documentation/fb/sm712fb.rst
F: drivers/video/fbdev/sm712*
+SEQNUM OPS
+M: Shuah Khan <skhan@xxxxxxxxxxxxxxxxxxx>
+L: linux-kernel@xxxxxxxxxxxxxxx
+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..17d327b78050
--- /dev/null
+++ b/include/linux/seqnum_ops.h
@@ -0,0 +1,116 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * seqnum_ops.h - Interfaces for sequential and statistical counters.
+ *
+ * Copyright (c) 2020 Shuah Khan <skhan@xxxxxxxxxxxxxxxxxxx>
+ * Copyright (c) 2020 The Linux Foundation
+ *
+ * Sequence Number functions provide support for unsgined atomic up
+ * counters.
+ *
+ * The interface provides:
+ * seqnumu32 & seqnumu64 functions:
+ * initialization
+ * increment and return
+ * fetch 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 - Sequential/Statistical atomic counter
+ * @seqnum: atomic_t
+ *
+ **/
+struct seqnum32 {
+ atomic_t seqnum;
+};
+
+#define SEQNUM_INIT(i) { .seqnum = ATOMIC_INIT(i) }
+
+/*
+ * seqnum32_init() - initialize seqnum value
+ * @seq: struct seqnum32 pointer
+ *
+ */
+static inline void seqnum32_init(struct seqnum32 *seq)
+{
+ atomic_set(&seq->seqnum, 0);
+}
+
+/*
+ * seqnum32_inc_return() - increment seqnum value and return the new value
+ * @seq: struct seqnum32 pointer
+ *
+ * Return u32
+ */
+static inline u32 seqnum32_inc_return(struct seqnum32 *seq)
+{
+ return (u32) atomic_inc_return(&seq->seqnum);
+}
+
+/*
+ * seqnum32_fetch() - return the current value
+ * @seq: struct seqnum32 pointer
+ *
+ * Return u32
+ */
+static inline u32 seqnum32_fetch(struct seqnum32 *seq)
+{
+ return (u32) atomic_add_return(0, &seq->seqnum);
+}
+
+#ifdef CONFIG_64BIT
+/* atomic64_t is defined in CONFIG_64BIT in include/linux/types.h */
+/*
+ * struct seqnum64 - Sequential/Statistical atomic counter
+ * @seq: atomic64_t
+ *
+ */
+struct seqnum64 {
+ atomic64_t seqnum;
+};
+
+/*
+ * seqnum64_init() - initialize seqnum value
+ * @seq: struct seqnum64 pointer
+ *
+ */
+static inline void seqnum64_init(struct seqnum64 *seq)
+{
+ atomic64_set(&seq->seqnum, 0);
+}
+
+/*
+ * seqnum64_inc() - increment seqnum value and return the new value
+ * @seq: struct seqnum64 pointer
+ *
+ * Return u64
+ */
+static inline u64 seqnum64_inc_return(struct seqnum64 *seq)
+{
+ return (u64) atomic64_inc_return(&seq->seqnum);
+}
+
+/*
+ * seqnum64_fetch() - return the current value
+ * @seq: struct seqnum64 pointer
+ *
+ * Return u64
+ */
+static inline u64 seqnum64_fetch(struct seqnum64 *seq)
+{
+ return (u64) atomic64_add_return(0, &seq->seqnum);
+}
+#endif /* CONFIG_64BIT */
+
+#endif /* __LINUX_SEQNUM_OPS_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index b46a9fd122c8..c362c2713e11 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 ce45af50983a..7d17c25e4d73 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..6e58b6a0a2be
--- /dev/null
+++ b/lib/test_seqnum_ops.c
@@ -0,0 +1,119 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * test_seqnum_ops.c - Kernel module for testing Seqnum API
+ *
+ * Copyright (c) 2020 Shuah Khan <skhan@xxxxxxxxxxxxxxxxxxx>
+ * Copyright (c) 2020 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)
+{
+ static struct seqnum32 seq = SEQNUM_INIT(0);
+ u32 start_val = seqnum32_fetch(&seq);
+ u32 end_val;
+
+ end_val = seqnum32_inc_return(&seq);
+ test_seqnum32_result("Test fetch and increment",
+ start_val, end_val, start_val+1);
+
+ start_val = seqnum32_fetch(&seq);
+ seqnum32_init(&seq);
+ end_val = seqnum32_fetch(&seq);
+ test_seqnum32_result("Test init", start_val, end_val, 0);
+
+}
+
+static void test_seqnum32_overflow(void)
+{
+ static struct seqnum32 seq = SEQNUM_INIT(UINT_MAX-1);
+ u32 start_val = seqnum32_fetch(&seq);
+ u32 end_val = seqnum32_inc_return(&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);
+}
+
+#ifdef CONFIG_64BIT
+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)
+{
+ static struct seqnum64 seq = SEQNUM_INIT(0);
+ u64 start_val = seqnum64_fetch(&seq);
+ u64 end_val;
+
+ end_val = seqnum64_inc_return(&seq);
+ test_seqnum64_result("Test fetch and increment",
+ start_val, end_val, start_val+1);
+
+ start_val = seqnum64_fetch(&seq);
+ seqnum64_init(&seq);
+ end_val = seqnum64_fetch(&seq);
+ test_seqnum64_result("Test init", start_val, end_val, 0);
+}
+
+static void test_seqnum64_overflow(void)
+{
+ static struct seqnum64 seq = SEQNUM_INIT(UINT_MAX-1);
+ u64 start_val = seqnum64_fetch(&seq);
+ u64 end_val = seqnum64_inc_return(&seq);
+
+ test_seqnum64_result("Test UINT_MAX limit compare with (val+1)",
+ start_val, end_val, start_val+1);
+ test_seqnum64_result("Test UINT_MAX limit compare with (UINT_MAX)",
+ start_val, end_val, UINT_MAX);
+}
+#endif /* CONFIG_64BIT */
+
+static int __init test_seqnum_ops_init(void)
+{
+ pr_info("Start seqnum32_*() interfaces test\n");
+ test_seqnum32();
+ test_seqnum32_overflow();
+ pr_info("End seqnum32_*() interfaces test\n\n");
+
+#ifdef CONFIG_64BIT
+ pr_info("Start seqnum64_*() interfaces test\n");
+ test_seqnum64();
+ test_seqnum64_overflow();
+ pr_info("End seqnum64_*() interfaces test\n\n");
+#endif /* CONFIG_64BIT */
+
+ 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@xxxxxxxxxxxxxxxxxxx>");
+MODULE_LICENSE("GPL v2");
--
2.27.0