Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
From:   "=?UTF-8?q?Christian=20K=C3=B6nig?=" 
        <ckoenig.leichtzumerken@gmail.com>
To:     mojha@codeaurora.org, jkosina@suse.cz, cezary.rojewski@intel.com,
        neilb@suse.com, b00073877@aus.edu,
        andriy.shevchenko@linux.intel.com, linux-kernel@vger.kernel.org
Subject: [PATCH] list: add more extensive double add check
Date:   Mon,  1 Feb 2021 14:52:51 +0100
Message-Id: <20210201135251.1884-1-christian.koenig@amd.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Precedence: bulk

Adding the same element to a linked list multiple times
seems to be a rather common programming mistake. To debug
those I've more than once written some code to check a
linked list for duplicates.

Since re-inventing the wheel over and over again is a bad
idea this patch tries to add some common code which allows
to check linked lists for duplicates while adding new
elements.

When list debugging is enabled we currently already check
the previous and next element if they are identical to the
new one. This patch now adds a configuration option to
check N elements before and after the desired position.

By default we still only test one item since testing more
means quite a large CPU overhead. This can be overwritten
on a per C file bases by defining DEBUG_LIST_DOUBLE_ADD
before including list.h.

A new kunit test is also added to the existing list tests
which intentionally triggers the debug functionality.

Signed-off-by: Christian König <christian.koenig@amd.com>
---
 include/linux/list.h    | 18 +++++++++++++++---
 include/linux/rculist.h |  2 +-
 lib/Kconfig.debug       | 14 ++++++++++++++
 lib/list-test.c         | 27 +++++++++++++++++++++++++++
 lib/list_debug.c        | 26 +++++++++++++++++++++-----
 5 files changed, 78 insertions(+), 9 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 89bdc92e75c3..e772e5e7c96d 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -37,14 +37,26 @@ static inline void INIT_LIST_HEAD(struct list_head *list)
 }
 
 #ifdef CONFIG_DEBUG_LIST
+
+#ifndef DEBUG_LIST_DOUBLE_ADD
+#define DEBUG_LIST_DOUBLE_ADD CONFIG_DEBUG_LIST_DOUBLE_ADD
+#endif
+
 extern bool __list_add_valid(struct list_head *new,
 			      struct list_head *prev,
-			      struct list_head *next);
+			      struct list_head *next,
+			      int num_entries);
 extern bool __list_del_entry_valid(struct list_head *entry);
 #else
+
+#ifndef DEBUG_LIST_DOUBLE_ADD
+#define DEBUG_LIST_DOUBLE_ADD 0
+#endif
+
 static inline bool __list_add_valid(struct list_head *new,
 				struct list_head *prev,
-				struct list_head *next)
+				struct list_head *next,
+				int num_entries)
 {
 	return true;
 }
@@ -64,7 +76,7 @@ static inline void __list_add(struct list_head *new,
 			      struct list_head *prev,
 			      struct list_head *next)
 {
-	if (!__list_add_valid(new, prev, next))
+	if (!__list_add_valid(new, prev, next, DEBUG_LIST_DOUBLE_ADD))
 		return;
 
 	next->prev = new;
diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index f8633d37e358..186618ad11d9 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -85,7 +85,7 @@ static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
 static inline void __list_add_rcu(struct list_head *new,
 		struct list_head *prev, struct list_head *next)
 {
-	if (!__list_add_valid(new, prev, next))
+	if (!__list_add_valid(new, prev, next, DEBUG_LIST_DOUBLE_ADD))
 		return;
 
 	new->next = next;
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e6e58b26e888..ded75214ea76 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1508,6 +1508,20 @@ config DEBUG_LIST
 
 	  If unsure, say N.
 
+config DEBUG_LIST_DOUBLE_ADD
+	int "How many list entries are checked for double adds"
+	depends on DEBUG_LIST
+	default 1
+	help
+	  Controls how many list entries are checked while adding new ones.
+	  Larger values catch more double adds, but reduce the performance
+	  massively.
+
+	  Can be overwritten locally in a C file by defining
+	  DEBUG_LIST_DOUBLE_ADD to an arbitrary value.
+
+	  If unsure, say 1.
+
 config DEBUG_PLIST
 	bool "Debug priority linked list manipulation"
 	depends on DEBUG_KERNEL
diff --git a/lib/list-test.c b/lib/list-test.c
index ee09505df16f..05174051977b 100644
--- a/lib/list-test.c
+++ b/lib/list-test.c
@@ -5,6 +5,9 @@
  * Copyright (C) 2019, Google LLC.
  * Author: David Gow <davidgow@google.com>
  */
+
+#define DEBUG_LIST_DOUBLE_ADD 4
+
 #include <kunit/test.h>
 
 #include <linux/list.h>
@@ -698,6 +701,27 @@ static void list_test_list_for_each_entry_reverse(struct kunit *test)
 	KUNIT_EXPECT_EQ(test, i, -1);
 }
 
+
+#ifdef CONFIG_DEBUG_LIST
+static void list_test_list_double_add(struct kunit *test)
+{
+	struct list_head entries[DEBUG_LIST_DOUBLE_ADD];
+	LIST_HEAD(list);
+	int i;
+
+	for (i = 0; i < DEBUG_LIST_DOUBLE_ADD; ++i)
+		list_add_tail(&entries[i], &list);
+
+	/* Intentionally double add the first one, this should be catched and
+	 * prevented by the list debug code.
+	 */
+	list_add_tail(&entries[0], &list);
+
+	KUNIT_EXPECT_PTR_EQ(test, entries[0].next, &entries[1]);
+	KUNIT_EXPECT_PTR_EQ(test, entries[0].prev, &list);
+}
+#endif
+
 static struct kunit_case list_test_cases[] = {
 	KUNIT_CASE(list_test_list_init),
 	KUNIT_CASE(list_test_list_add),
@@ -735,6 +759,9 @@ static struct kunit_case list_test_cases[] = {
 	KUNIT_CASE(list_test_list_for_each_prev_safe),
 	KUNIT_CASE(list_test_list_for_each_entry),
 	KUNIT_CASE(list_test_list_for_each_entry_reverse),
+#ifdef CONFIG_DEBUG_LIST
+	KUNIT_CASE(list_test_list_double_add),
+#endif
 	{},
 };
 
diff --git a/lib/list_debug.c b/lib/list_debug.c
index 5d5424b51b74..df378b6ad3df 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -18,19 +18,35 @@
  */
 
 bool __list_add_valid(struct list_head *new, struct list_head *prev,
-		      struct list_head *next)
+		      struct list_head *next, int num_entries)
 {
+	struct list_head *tmp;
+	int cnt;
+
 	if (CHECK_DATA_CORRUPTION(next->prev != prev,
 			"list_add corruption. next->prev should be prev (%px), but was %px. (next=%px).\n",
 			prev, next->prev, next) ||
 	    CHECK_DATA_CORRUPTION(prev->next != next,
 			"list_add corruption. prev->next should be next (%px), but was %px. (prev=%px).\n",
-			next, prev->next, prev) ||
-	    CHECK_DATA_CORRUPTION(new == prev || new == next,
-			"list_add double add: new=%px, prev=%px, next=%px.\n",
-			new, prev, next))
+			next, prev->next, prev))
 		return false;
 
+	for (cnt = 0, tmp = prev; cnt < num_entries && tmp != next;
+	     ++cnt, tmp = tmp->prev)
+		if (CHECK_DATA_CORRUPTION(new == tmp,
+				"list_add double add: new=%px, prev=%px, next=%px.\n",
+				new, prev, next))
+			return false;
+
+	if (tmp == next)
+		return true;
+
+	for (cnt = 0, tmp = next; cnt < num_entries; ++cnt, tmp = tmp->next)
+		if (CHECK_DATA_CORRUPTION(new == tmp,
+				"list_add double add: new=%px, prev=%px, next=%px.\n",
+				new, prev, next))
+			return false;
+
 	return true;
 }
 EXPORT_SYMBOL(__list_add_valid);
-- 
2.25.1