[PATCH 0/6] improve list_sort test

[PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

Hi,

while hunting a non-existing bug in 'list_sort()', I've improved the
'list_sort_test()' function which tests the 'list_sort()' library call. Although
at the end I found a bug in my code, but not in 'list_sort()', I think my
clean-ups and improvements are worth merging because they make the test function
better.

Don, if you are ok with the patches, I'll send them to Andrew Morton.

Artem.

[PATCH 1/6] lib/Kconfig.debug: add list_sort debugging switch

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/Kconfig.debug |    9 +++++++++
 lib/list_sort.c   |    4 ++--
 2 files changed, 11 insertions(+), 2 deletions(-)

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e722e9d..4d5adde 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -684,6 +684,15 @@ config DEBUG_LIST
 
 	  If unsure, say N.
 
+config TEST_LIST_SORT
+	bool "Linked list sorting test"
+	depends on DEBUG_KERNEL
+	help
+	  Enable this to turn on 'list_sort()' function test. This test is
+	  executed only once during system boot, so affects only boot time.
+
+	  If unsure, say N.
+
 config DEBUG_SG
 	bool "Debug SG table operations"
 	depends on DEBUG_KERNEL
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 4b5cb79..9dd8d4a 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -141,7 +141,7 @@ void list_sort(void *priv, struct list_head *head,
 }
 EXPORT_SYMBOL(list_sort);
 
-#ifdef DEBUG_LIST_SORT
+#ifdef CONFIG_TEST_LIST_SORT
 struct debug_el {
 	struct list_head l_h;
 	int value;
@@ -214,4 +214,4 @@ static int __init list_sort_test(void)
 	return 0;
 }
 module_init(list_sort_test);
-#endif
+#endif /* CONFIG_TEST_LIST_SORT */
-- 
1.7.1.1

[PATCH 2/6] lib/list_sort: test: use more reasonable printk levels

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

I do not see any reason to use KERN_WARN for normal messages
and KERN_EMERG for error messages in the lib_sort testing routine.
Let's use more reasonable KERN_NORM and KERN_ERR levels.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |   16 ++++++++--------
 1 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 9dd8d4a..e0c2ccb 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -166,7 +166,7 @@ static int __init list_sort_test(void)
 	struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
 	struct list_head *cur;
 
-	printk(KERN_WARNING "testing list_sort()\n");
+	printk(KERN_DEBUG "testing list_sort()\n");
 
 	cur = head;
 	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
@@ -189,17 +189,17 @@ static int __init list_sort_test(void)
 		struct debug_el *el = container_of(cur, struct debug_el, l_h);
 		int cmp_result = cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
-			printk(KERN_EMERG "list_sort() returned "
-						"a corrupted list!\n");
+			printk(KERN_ERR "list_sort() returned "
+					"a corrupted list!\n");
 			return 1;
 		} else if (cmp_result > 0) {
-			printk(KERN_EMERG "list_sort() failed to sort!\n");
+			printk(KERN_ERR "list_sort() failed to sort!\n");
 			return 1;
 		} else if (cmp_result == 0 &&
 				el->serial >= container_of(cur->next,
 					struct debug_el, l_h)->serial) {
-			printk(KERN_EMERG "list_sort() failed to preserve order"
-						 " of equivalent elements!\n");
+			printk(KERN_ERR "list_sort() failed to preserve order "
+					"of equivalent elements!\n");
 			return 1;
 		}
 		kfree(cur->prev);
@@ -207,8 +207,8 @@ static int __init list_sort_test(void)
 	}
 	kfree(cur);
 	if (count != LIST_SORT_TEST_LENGTH) {
-		printk(KERN_EMERG "list_sort() returned list of"
-						"different length!\n");
+		printk(KERN_ERR "list_sort() returned list of "
+				"different length!\n");
 		return 1;
 	}
 	return 0;
-- 
1.7.1.1

[PATCH 3/6] lib/list_sort: test: use generic random32

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

Instead of using own pseudo-random generator, use generic linux
'random32()' function. Presumably, this should improve test coverage.

At the same time, do the following changes:
  o Use shorter macro name for test list length
  o Do not use strange 'l_h' name for 'struct list_head' element,
    use 'list', because it is traditional name and thus, makes the
    code more obvious and readable.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |   27 +++++++++++++++------------
 1 files changed, 15 insertions(+), 12 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index e0c2ccb..8600e8f 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -142,42 +142,45 @@ void list_sort(void *priv, struct list_head *head,
 EXPORT_SYMBOL(list_sort);
 
 #ifdef CONFIG_TEST_LIST_SORT
+
+#include <linux/random.h>
+
 struct debug_el {
-	struct list_head l_h;
+	struct list_head list;
 	int value;
 	unsigned serial;
 };
 
 static int cmp(void *priv, struct list_head *a, struct list_head *b)
 {
-	return container_of(a, struct debug_el, l_h)->value
-	     - container_of(b, struct debug_el, l_h)->value;
+	return container_of(a, struct debug_el, list)->value
+	     - container_of(b, struct debug_el, list)->value;
 }
 
 /*
  * The pattern of set bits in the list length determines which cases
  * are hit in list_sort().
  */
-#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
+#define TEST_LIST_LEN (512+128+2) /* not including head */
 
 static int __init list_sort_test(void)
 {
-	int i, r = 1, count;
+	int i, count;
 	struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
 	struct list_head *cur;
 
 	printk(KERN_DEBUG "testing list_sort()\n");
 
 	cur = head;
-	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
+	for (i = 0; i < TEST_LIST_LEN; i++) {
 		struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
 		BUG_ON(!el);
 		 /* force some equivalencies */
-		el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
+		el->value = random32() % (TEST_LIST_LEN/3);
 		el->serial = i;
 
-		el->l_h.prev = cur;
-		cur->next = &el->l_h;
+		el->list.prev = cur;
+		cur->next = &el->list;
 		cur = cur->next;
 	}
 	head->prev = cur;
@@ -186,7 +189,7 @@ static int __init list_sort_test(void)
 
 	count = 1;
 	for (cur = head->next; cur->next != head; cur = cur->next) {
-		struct debug_el *el = container_of(cur, struct debug_el, l_h);
+		struct debug_el *el = container_of(cur, struct debug_el, list);
 		int cmp_result = cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
 			printk(KERN_ERR "list_sort() returned "
@@ -197,7 +200,7 @@ static int __init list_sort_test(void)
 			return 1;
 		} else if (cmp_result == 0 &&
 				el->serial >= container_of(cur->next,
-					struct debug_el, l_h)->serial) {
+					struct debug_el, list)->serial) {
 			printk(KERN_ERR "list_sort() failed to preserve order "
 					"of equivalent elements!\n");
 			return 1;
@@ -206,7 +209,7 @@ static int __init list_sort_test(void)
 		count++;
 	}
 	kfree(cur);
-	if (count != LIST_SORT_TEST_LENGTH) {
+	if (count != TEST_LIST_LEN) {
 		printk(KERN_ERR "list_sort() returned list of "
 				"different length!\n");
 		return 1;
-- 
1.7.1.1

[PATCH 4/6] lib/list_sort: test: improve errors handling

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

The 'lib_sort()' test does not free memory if it fails, and it
makes the kernel panic if it cannot allocate memory. This patch
fixes the problem.

This patch also changes several small things:
 o use 'list_add()' helper instead of adding manually
 o introduce temporary 'el1' variable to avoid ugly and unreadalbe
   "if" statement
 o make 'head' to be stack variable instead of 'kmalloc()'ed, which
   simplifies code a bit

Overall, this patch is of clean-up type.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |   65 ++++++++++++++++++++++++++++++++----------------------
 1 files changed, 38 insertions(+), 27 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 8600e8f..b9a9474 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -165,56 +165,67 @@ static int cmp(void *priv, struct list_head *a, struct list_head *b)
 
 static int __init list_sort_test(void)
 {
-	int i, count;
-	struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
-	struct list_head *cur;
+	int i, count = 1, err = -EINVAL;
+	struct debug_el *el;
+	struct list_head *cur, *tmp;
+	LIST_HEAD(head);
 
 	printk(KERN_DEBUG "testing list_sort()\n");
 
-	cur = head;
 	for (i = 0; i < TEST_LIST_LEN; i++) {
-		struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
-		BUG_ON(!el);
+		el = kmalloc(sizeof(*el), GFP_KERNEL);
+		if (!el) {
+			printk(KERN_ERR "cancel list_sort() testing - cannot "
+					"allocate memory\n");
+			goto exit;
+		}
 		 /* force some equivalencies */
 		el->value = random32() % (TEST_LIST_LEN/3);
 		el->serial = i;
-
-		el->list.prev = cur;
-		cur->next = &el->list;
-		cur = cur->next;
+		list_add_tail(&el->list, &head);
 	}
-	head->prev = cur;
 
-	list_sort(NULL, head, cmp);
+	list_sort(NULL, &head, cmp);
+
+	for (cur = head.next; cur->next != &head; cur = cur->next) {
+		struct debug_el *el1;
+		int cmp_result;
 
-	count = 1;
-	for (cur = head->next; cur->next != head; cur = cur->next) {
-		struct debug_el *el = container_of(cur, struct debug_el, list);
-		int cmp_result = cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
 			printk(KERN_ERR "list_sort() returned "
 					"a corrupted list!\n");
-			return 1;
-		} else if (cmp_result > 0) {
+			goto exit;
+		}
+
+		cmp_result = cmp(NULL, cur, cur->next);
+		if (cmp_result > 0) {
 			printk(KERN_ERR "list_sort() failed to sort!\n");
-			return 1;
-		} else if (cmp_result == 0 &&
-				el->serial >= container_of(cur->next,
-					struct debug_el, list)->serial) {
+			goto exit;
+		}
+
+		el = container_of(cur, struct debug_el, list);
+		el1 = container_of(cur->next, struct debug_el, list);
+		if (cmp_result == 0 && el->serial >= el1->serial) {
 			printk(KERN_ERR "list_sort() failed to preserve order "
 					"of equivalent elements!\n");
-			return 1;
+			goto exit;
 		}
-		kfree(cur->prev);
 		count++;
 	}
-	kfree(cur);
+
 	if (count != TEST_LIST_LEN) {
 		printk(KERN_ERR "list_sort() returned list of "
 				"different length!\n");
-		return 1;
+		goto exit;
+	}
+
+	err = 0;
+exit:
+	list_for_each_safe(cur, tmp, &head) {
+		list_del(cur);
+		kfree(container_of(cur, struct debug_el, list));
 	}
-	return 0;
+	return err;
 }
 module_init(list_sort_test);
 #endif /* CONFIG_TEST_LIST_SORT */
-- 
1.7.1.1

[PATCH 5/6] lib/list_sort: test: unify test messages

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

This patch unifies 'list_sort_test()' messages a bit and makes sure
all of them start with the "list_sort_test:" prefix to make it obvious
for users where the messages come from.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |   19 ++++++++++---------
 1 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index b9a9474..44dbdec 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -170,12 +170,12 @@ static int __init list_sort_test(void)
 	struct list_head *cur, *tmp;
 	LIST_HEAD(head);
 
-	printk(KERN_DEBUG "testing list_sort()\n");
+	printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
 
 	for (i = 0; i < TEST_LIST_LEN; i++) {
 		el = kmalloc(sizeof(*el), GFP_KERNEL);
 		if (!el) {
-			printk(KERN_ERR "cancel list_sort() testing - cannot "
+			printk(KERN_ERR "list_sort_test: error: cannot "
 					"allocate memory\n");
 			goto exit;
 		}
@@ -192,30 +192,31 @@ static int __init list_sort_test(void)
 		int cmp_result;
 
 		if (cur->next->prev != cur) {
-			printk(KERN_ERR "list_sort() returned "
-					"a corrupted list!\n");
+			printk(KERN_ERR "list_sort_test: error: list is "
+					"corrupted\n");
 			goto exit;
 		}
 
 		cmp_result = cmp(NULL, cur, cur->next);
 		if (cmp_result > 0) {
-			printk(KERN_ERR "list_sort() failed to sort!\n");
+			printk(KERN_ERR "list_sort_test: error: list is not "
+					"sorted\n");
 			goto exit;
 		}
 
 		el = container_of(cur, struct debug_el, list);
 		el1 = container_of(cur->next, struct debug_el, list);
 		if (cmp_result == 0 && el->serial >= el1->serial) {
-			printk(KERN_ERR "list_sort() failed to preserve order "
-					"of equivalent elements!\n");
+			printk(KERN_ERR "list_sort_test: error: order of "
+					"equivalent elements not preserved\n");
 			goto exit;
 		}
 		count++;
 	}
 
 	if (count != TEST_LIST_LEN) {
-		printk(KERN_ERR "list_sort() returned list of "
-				"different length!\n");
+		printk(KERN_ERR "list_sort_test: error: bad list length %d",
+				count);
 		goto exit;
 	}
 
-- 
1.7.1.1

[PATCH 6/6] lib/list_sort: test: check element addresses

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

Improve 'lib_sort()' test and check that:
 o 'cmp()' is called only for elements which were present in the original list,
   i.e., the 'a' and 'b' parameters are valid
 o the resulted (sorted) list consists onlly of the original elements
 o intdoruce "poison" fields to make sure data around 'struc list_head' field
   are not corrupted.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |   75 +++++++++++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 67 insertions(+), 8 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 44dbdec..3828071 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -145,23 +145,65 @@ EXPORT_SYMBOL(list_sort);
 
 #include <linux/random.h>
 
+/*
+ * The pattern of set bits in the list length determines which cases
+ * are hit in list_sort().
+ */
+#define TEST_LIST_LEN (512+128+2) /* not including head */
+
+#define TEST_POISON1 0xDEADBEEF
+#define TEST_POISON2 0xA324354C
+
 struct debug_el {
+	unsigned int poison1;
 	struct list_head list;
+	unsigned int poison2;
 	int value;
 	unsigned serial;
 };
 
-static int cmp(void *priv, struct list_head *a, struct list_head *b)
+/* Array, containing pointers to all elements in the test list */
+static struct debug_el **elts __initdata;
+
+static int __init check(struct debug_el *ela, struct debug_el *elb)
 {
-	return container_of(a, struct debug_el, list)->value
-	     - container_of(b, struct debug_el, list)->value;
+	if (ela->serial >= TEST_LIST_LEN) {
+		printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
+				ela->serial);
+		return -EINVAL;
+	}
+	if (elb->serial >= TEST_LIST_LEN) {
+		printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
+				elb->serial);
+		return -EINVAL;
+	}
+	if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
+		printk(KERN_ERR "list_sort_test: error: phantom element\n");
+		return -EINVAL;
+	}
+	if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
+		printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
+				ela->poison1, ela->poison2);
+		return -EINVAL;
+	}
+	if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
+		printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
+				elb->poison1, elb->poison2);
+		return -EINVAL;
+	}
+	return 0;
 }
 
-/*
- * The pattern of set bits in the list length determines which cases
- * are hit in list_sort().
- */
-#define TEST_LIST_LEN (512+128+2) /* not including head */
+static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
+{
+	struct debug_el *ela, *elb;
+
+	ela = container_of(a, struct debug_el, list);
+	elb = container_of(b, struct debug_el, list);
+
+	check(ela, elb);
+	return ela->value - elb->value;
+}
 
 static int __init list_sort_test(void)
 {
@@ -172,6 +214,13 @@ static int __init list_sort_test(void)
 
 	printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
 
+	elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL);
+	if (!elts) {
+		printk(KERN_ERR "list_sort_test: error: cannot allocate "
+				"memory\n");
+		goto exit;
+	}
+
 	for (i = 0; i < TEST_LIST_LEN; i++) {
 		el = kmalloc(sizeof(*el), GFP_KERNEL);
 		if (!el) {
@@ -182,6 +231,9 @@ static int __init list_sort_test(void)
 		 /* force some equivalencies */
 		el->value = random32() % (TEST_LIST_LEN/3);
 		el->serial = i;
+		el->poison1 = TEST_POISON1;
+		el->poison2 = TEST_POISON2;
+		elts[i] = el;
 		list_add_tail(&el->list, &head);
 	}
 
@@ -211,6 +263,12 @@ static int __init list_sort_test(void)
 					"equivalent elements not preserved\n");
 			goto exit;
 		}
+
+		if (check(el, el1)) {
+			printk(KERN_ERR "list_sort_test: error: element check "
+					"failed\n");
+			goto exit;
+		}
 		count++;
 	}
 
@@ -222,6 +280,7 @@ static int __init list_sort_test(void)
 
 	err = 0;
 exit:
+	kfree(elts);
 	list_for_each_safe(cur, tmp, &head) {
 		list_del(cur);
 		kfree(container_of(cur, struct debug_el, list));
-- 
1.7.1.1

Re: [PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

On Sat, 2010-08-07 at 11:10 +0300, Artem Bityutskiy wrote:
> Hi,
> 
> while hunting a non-existing bug in 'list_sort()', I've improved the
> 'list_sort_test()' function which tests the 'list_sort()' library call. Although
> at the end I found a bug in my code, but not in 'list_sort()', I think my
> clean-ups and improvements are worth merging because they make the test function
> better.

Actually, your 'list_sort()' version does have a problem. I found out
that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these
cases 'a' and 'b' can point to something which is not a valid element of
the original list. Probably a senitel or something like that.

It is easy to work around this by adding:

if (a == b)
	return 0;

in the 'cmp()' function, but this is nevertheless a bug (not too bad,
though) and should be fixed. Also, the fact that 'cmp()' is called with
'a==b' sometimes should be documented.

I'm CC-ing 2 other users of 'list_sort()' for head-ups (xfs, drm).

I've fixed assertions in UBIFS using the following patch:

===========================================================================

>From 3ea1708e2d0462dc8eaf1076ebf973d82700952b Mon Sep 17 00:00:00 2001
From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Date: Sun, 8 Aug 2010 12:45:23 +0300
Subject: [PATCHv2 8/9] UBIFS: fix assertion warnings in comparison function

When running the integrity test ('integck' from mtd-utils) on current
UBIFS on 2.6.35, I see that assertions in UBIFS 'list_sort()' comparison
functions trigger sometimes, e.g.:

UBIFS assert failed in data_nodes_cmp at 132 (pid 28311)

My investigation showed that this happens when 'list_sort()' calls the 'cmp()'
function with equivalent arguments. In this case, the 'struct list_head'
parameter, passed to 'cmp()' is bogus, and it does not belong to any element in
the original list.

And this issue seems to be introduced by commit:

commit 835cc0c8477fdbc59e0217891d6f11061b1ac4e2
Author: Don Mullis <don.mullis@gmail.com>
Date:   Fri Mar 5 13:43:15 2010 -0800

It is easy to work around the issue by doing:

if (a == b)
	return 0;

in UBIFS. It works, but 'lib_sort()' should nevertheless be fixed. Although it
is harmless to have this piece of code in UBIFS.

This patch adds that code to both UBIFS 'cmp()' functions:
'data_nodes_cmp()' and 'nondata_nodes_cmp()'.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/gc.c |    6 ++++++
 1 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 8dbe36f..84ab9aa 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -125,6 +125,9 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 	struct ubifs_scan_node *sa, *sb;
 
 	cond_resched();
+	if (a == b)
+		return 0;
+
 	sa = list_entry(a, struct ubifs_scan_node, list);
 	sb = list_entry(b, struct ubifs_scan_node, list);
 
@@ -165,6 +168,9 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 	struct ubifs_scan_node *sa, *sb;
 
 	cond_resched();
+	if (a == b)
+		return 0;
+
 	sa = list_entry(a, struct ubifs_scan_node, list);
 	sb = list_entry(b, struct ubifs_scan_node, list);
 
-- 
1.7.1.1



-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Re: [PATCH 0/6] improve list_sort test

[Don Mullis]

Artem Bityutskiy <dedekind1@gmail.com> writes:
> Actually, your 'list_sort()' version does have a problem. I found out
> that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these
> cases 'a' and 'b' can point to something which is not a valid element of
> the original list. Probably a senitel or something like that.
>
> It is easy to work around this by adding:
>
> if (a == b)
>        return 0;
>
> in the 'cmp()' function, but this is nevertheless a bug (not too bad,
> though) and should be fixed.

Yes, invalid 'a' or 'b' pointers would be a bug.  If providing a test
case is hard, can you say what segment is pointed to?  Into the stack?
Into address ranges normal for elements, but not now on the list?  Is
there a pattern to the values returned?  Is it perhaps always the
first or last callback from a particular call to list_sort()?

That sometimes a==b is, on the other hand, by design:

	/*
	 * In worst cases this loop may run many iterations.
	 * Continue callbacks to the client even though no
	 * element comparison is needed, so the client's cmp()
	 * routine can invoke cond_resched() periodically.
	 */
	(*cmp)(priv, tail, tail);

Adding a sentence to the function header comment reminding callers
that they need to be able to handle a==b seems like a good idea.

Re: [PATCH 0/6] improve list_sort test

[Don Mullis]

On Sun, Aug 8, 2010 at 12:31 PM, Don Mullis <don.mullis@gmail.com> wrote:
> Artem Bityutskiy <dedekind1@gmail.com> writes:
>> Actually, your 'list_sort()' version does have a problem. I found out
>> that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these
>> cases 'a' and 'b' can point to something which is not a valid element of
>> the original list. Probably a senitel or something like that.

Looks like if the original list is a POT in length, the first callback
from line 73 will pass a==b both pointing to the original list_head.
Would you be able to test this fix?

--- linux-2.6.orig/lib/list_sort.c
+++ linux-2.6/lib/list_sort.c
@@ -70,7 +70,7 @@ static void merge_and_restore_back_links
                 * element comparison is needed, so the client's cmp()
                 * routine can invoke cond_resched() periodically.
                 */
-               (*cmp)(priv, tail, tail);
+               (*cmp)(priv, tail->next, tail->next);

                tail->next->prev = tail;
                tail = tail->next;

Re: [PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

On Sun, 2010-08-08 at 13:07 -0700, Don Mullis wrote:
> On Sun, Aug 8, 2010 at 12:31 PM, Don Mullis <don.mullis@gmail.com> wrote:
> > Artem Bityutskiy <dedekind1@gmail.com> writes:
> >> Actually, your 'list_sort()' version does have a problem. I found out
> >> that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these
> >> cases 'a' and 'b' can point to something which is not a valid element of
> >> the original list. Probably a senitel or something like that.
> 
> Looks like if the original list is a POT in length, the first callback
> from line 73 will pass a==b both pointing to the original list_head.
> Would you be able to test this fix?
> 
> --- linux-2.6.orig/lib/list_sort.c
> +++ linux-2.6/lib/list_sort.c
> @@ -70,7 +70,7 @@ static void merge_and_restore_back_links
>                  * element comparison is needed, so the client's cmp()
>                  * routine can invoke cond_resched() periodically.
>                  */
> -               (*cmp)(priv, tail, tail);
> +               (*cmp)(priv, tail->next, tail->next);
> 
>                 tail->next->prev = tail;
>                 tail = tail->next;

Hi, thanks. I'm out of office, and probably will be able to do this few
weeks later.

Artem.

Re: [PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

On Sun, 2010-08-08 at 12:31 -0700, Don Mullis wrote:
> Yes, invalid 'a' or 'b' pointers would be a bug.  If providing a test
> case is hard, can you say what segment is pointed to?  Into the stack?
> Into address ranges normal for elements, but not now on the list?  Is
> there a pattern to the values returned?  Is it perhaps always the
> first or last callback from a particular call to list_sort()?

You've correctly identified in the the other mail that 'a' and 'b'
sometimes point to the list head. I've just checked this.

> That sometimes a==b is, on the other hand, by design:
> 
> 	/*
> 	 * In worst cases this loop may run many iterations.
> 	 * Continue callbacks to the client even though no
> 	 * element comparison is needed, so the client's cmp()
> 	 * routine can invoke cond_resched() periodically.
> 	 */
> 	(*cmp)(priv, tail, tail);
> 
> Adding a sentence to the function header comment reminding callers
> that they need to be able to handle a==b seems like a good idea.

OK, I'll add it.

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Re: [PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

On Sun, 2010-08-08 at 13:07 -0700, Don Mullis wrote:
> On Sun, Aug 8, 2010 at 12:31 PM, Don Mullis <don.mullis@gmail.com> wrote:
> > Artem Bityutskiy <dedekind1@gmail.com> writes:
> >> Actually, your 'list_sort()' version does have a problem. I found out
> >> that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these
> >> cases 'a' and 'b' can point to something which is not a valid element of
> >> the original list. Probably a senitel or something like that.
> 
> Looks like if the original list is a POT in length, the first callback
> from line 73 will pass a==b both pointing to the original list_head.
> Would you be able to test this fix?
> 
> --- linux-2.6.orig/lib/list_sort.c
> +++ linux-2.6/lib/list_sort.c
> @@ -70,7 +70,7 @@ static void merge_and_restore_back_links
>                  * element comparison is needed, so the client's cmp()
>                  * routine can invoke cond_resched() periodically.
>                  */
> -               (*cmp)(priv, tail, tail);
> +               (*cmp)(priv, tail->next, tail->next);

Ack, this fix works, thanks.

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Re: [PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

On Sun, 2010-08-08 at 13:07 -0700, Don Mullis wrote:
> On Sun, Aug 8, 2010 at 12:31 PM, Don Mullis <don.mullis@gmail.com> wrote:
> > Artem Bityutskiy <dedekind1@gmail.com> writes:
> >> Actually, your 'list_sort()' version does have a problem. I found out
> >> that it calls 'cmp(priv, a, b)' with 'a = b' sometimes, and in these
> >> cases 'a' and 'b' can point to something which is not a valid element of
> >> the original list. Probably a senitel or something like that.
> 
> Looks like if the original list is a POT in length, the first callback
> from line 73 will pass a==b both pointing to the original list_head.
> Would you be able to test this fix?

I'll turn your patch into a git am-able form and add CC to stable, and
send to you. You can then propagate it forward, or if you want, I can
send it to Andrew.

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

[PATCH] lib/list_sort: do not pass bad pointers to cmp callback

[Artem Bityutskiy]

From: Don Mullis <don.mullis@gmail.com>

If the original list is a POT in length, the first callback from line 73 will
pass a==b both pointing to the original list_head. This is dangerous because
the 'list_sort()' user can use 'container_of()' and accesses the "containing"
object, which does not necessary exist for the list head. So the user can
access RAM which does not belong to him. If this is a write access, we can end
up with memory corruption. This patch fixes the issue.

Signed-off-by: Don Mullis <don.mullis@gmail.com>
Tested-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Cc: stable@kernel.org
---
 lib/list_sort.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 4b5cb79..a7616fa 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -70,7 +70,7 @@ static void merge_and_restore_back_links(void *priv,
 		 * element comparison is needed, so the client's cmp()
 		 * routine can invoke cond_resched() periodically.
 		 */
-		(*cmp)(priv, tail, tail);
+		(*cmp)(priv, tail->next, tail->next);
 
 		tail->next->prev = tail;
 		tail = tail->next;
-- 
1.7.1.1


-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Re: [PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

On Sat, 2010-08-07 at 11:10 +0300, Artem Bityutskiy wrote:
> Hi,
> 
> while hunting a non-existing bug in 'list_sort()', I've improved the
> 'list_sort_test()' function which tests the 'list_sort()' library call. Although
> at the end I found a bug in my code, but not in 'list_sort()', I think my
> clean-ups and improvements are worth merging because they make the test function
> better.
> 
> Don, if you are ok with the patches, I'll send them to Andrew Morton.

Any feedback?

I'm also going to add this patch to the series:

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Subject: [PATCH 1/7] lib/list_sort: improve comments

Document the fact that 'list_sort()' can call the 'cmp()' function with
'a' == 'b' for the sake of 'cond_reshed()'.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 4b5cb79..d134b41 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -93,6 +93,11 @@ static void merge_and_restore_back_links(void *priv,
  * should sort before @b, and a positive value if @a should sort after
  * @b. If @a and @b are equivalent, and their original relative
  * ordering is to be preserved, @cmp must return 0.
+ *
+ * This function can be used in atomic context. This means that @cmp has to
+ * take care of calling 'cond_resched()' when needed. And 'list_sort()' will
+ * sometimes call @cmp with @a equivalent to @b, just to let the user call
+ * 'cond_resched()'.
  */
 void list_sort(void *priv, struct list_head *head,
 		int (*cmp)(void *priv, struct list_head *a,
-- 
1.7.1.1

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Re: [PATCH 0/6] improve list_sort test

[don.mullis]

Artem Bityutskiy <dedekind1@gmail.com> writes:
> Any feedback?
>
> I'm also going to add this patch to the series:
>
> From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> Subject: [PATCH 1/7] lib/list_sort: improve comments
>
> Document the fact that 'list_sort()' can call the 'cmp()' function with
> 'a' == 'b' for the sake of 'cond_reshed()'.
>
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> ---
>  lib/list_sort.c |    5 +++++
>  1 files changed, 5 insertions(+), 0 deletions(-)
>
> diff --git a/lib/list_sort.c b/lib/list_sort.c
> index 4b5cb79..d134b41 100644
> --- a/lib/list_sort.c
> +++ b/lib/list_sort.c
> @@ -93,6 +93,11 @@ static void merge_and_restore_back_links(void *priv,
>   * should sort before @b, and a positive value if @a should sort after
>   * @b. If @a and @b are equivalent, and their original relative
>   * ordering is to be preserved, @cmp must return 0.
> + *
> + * This function can be used in atomic context. This means that @cmp has to
> + * take care of calling 'cond_resched()' when needed. And 'list_sort()' will
> + * sometimes call @cmp with @a equivalent to @b, just to let the user call
> + * 'cond_resched()'.
>   */
>  void list_sort(void *priv, struct list_head *head,
>  		int (*cmp)(void *priv, struct list_head *a,
> -- 

Thanks, Artem.  I've prepared and tested locally a patch series that
brings in most of the series you sent earlier, and adds a few more
cleanups.  The one patch of yours that I did replace was the last one,
that modifies semantics of the correctness test.  My reasoning is that
the value of testing lies in exposing bugs, as economically as possible,
and your test wasn't exposing my power-of-two bug.  So I created an
alternative that's as simple as possible while picking at the corner
cases, e.g. power-of-two.

Last in my local patch series is the bug fix itself.  Setting
CONFIG_TEST_LIST_SORT and testing with all but the last patch applied
produces failure messages on the boot console.  Pushing the final "fix"
patch makes them go away :-)

Okay if I incorporate your comment addition, above, and post the series
for review?

Don

Re: [PATCH 0/6] improve list_sort test

[Artem Bityutskiy]

On Sat, 2010-08-21 at 09:59 -0700, don.mullis@gmail.com wrote:
> Thanks, Artem.  I've prepared and tested locally a patch series that
> brings in most of the series you sent earlier, and adds a few more
> cleanups.  The one patch of yours that I did replace was the last one,
> that modifies semantics of the correctness test.  My reasoning is that
> the value of testing lies in exposing bugs, as economically as possible,
> and your test wasn't exposing my power-of-two bug.  So I created an
> alternative that's as simple as possible while picking at the corner
> cases, e.g. power-of-two.

That's fine, thanks.

> Last in my local patch series is the bug fix itself.  Setting
> CONFIG_TEST_LIST_SORT and testing with all but the last patch applied
> produces failure messages on the boot console.  Pushing the final "fix"
> patch makes them go away :-)

Sounds good.

> Okay if I incorporate your comment addition, above, and post the series
> for review?

Sure, I'll be happy if you take care of this, just keep me in CC when
you submit the patches, please.

Thanks,
Artem.