[PATCH v2 0/4] lib: list_sort: Various minor improvements

[PATCH v2 0/4] lib: list_sort: Various minor improvements

[Rasmus Villemoes]

Reading the source of lib/list_sort.c, I came up with a few possible
improvements. I think 4/4 may be a bit controversial, but 1/4, 2/4 and
3/4 should be straightforward.

v2: Fix typo in 2/4, and add 3/4,4/4.

Rasmus Villemoes (4):
  lib: list_sort_test(): Return -ENOMEM when allocation fails
  lib: list_sort_test(): Add extra corruption check
  lib: list_sort_test(): Simplify and harden cleanup
  lib: list_sort.c: Limit number of unused cmp callbacks

 lib/list_sort.c | 24 +++++++++++++++---------
 1 file changed, 15 insertions(+), 9 deletions(-)

-- 
1.9.2

[PATCH v2 1/4] lib: list_sort_test(): Return -ENOMEM when allocation fails

[Rasmus Villemoes]

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/list_sort.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 1183fa7..291412a 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -207,7 +207,7 @@ static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
 
 static int __init list_sort_test(void)
 {
-	int i, count = 1, err = -EINVAL;
+	int i, count = 1, err = -ENOMEM;
 	struct debug_el *el;
 	struct list_head *cur, *tmp;
 	LIST_HEAD(head);
@@ -239,6 +239,7 @@ static int __init list_sort_test(void)
 
 	list_sort(NULL, &head, cmp);
 
+	err = -EINVAL;
 	for (cur = head.next; cur->next != &head; cur = cur->next) {
 		struct debug_el *el1;
 		int cmp_result;
-- 
1.9.2

[PATCH v2 2/4] lib: list_sort_test(): Add extra corruption check

[Rasmus Villemoes]

Add a check to make sure that the prev pointer of the list head points
to the last element on the list.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/list_sort.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 291412a..fbdbc86 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -272,6 +272,11 @@ static int __init list_sort_test(void)
 		}
 		count++;
 	}
+	if (head.prev != cur) {
+		printk(KERN_ERR "list_sort_test: error: list is corrupted\n");
+		goto exit;
+	}
+
 
 	if (count != TEST_LIST_LEN) {
 		printk(KERN_ERR "list_sort_test: error: bad list length %d",
-- 
1.9.2

[PATCH v2 3/4] lib: list_sort_test(): Simplify and harden cleanup

[Rasmus Villemoes]

There is no reason to maintain the list structure while freeing the
debug elements. Aside from the redundant pointer manipulations, it is
also inefficient from a locality-of-reference viewpoint, since they
are visited in a random order (wrt. the order they were
allocated). Furthermore, if we jumped to exit: after detecting list
corruption, it is actually dangerous.

So just free the elements in the order they were allocated, using the
backing array elts. Allocate that using kcalloc(), so that if
allocation of one of the debug element fails, we just end up calling
kfree(NULL) for the trailing elements.

Minor details: Use sizeof(*elts) instead of sizeof(void *), and return
err immediately when allocation of elts fails, to avoid introducing
another label just before the final return statement.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/list_sort.c | 12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index fbdbc86..a34c78c 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -209,16 +209,16 @@ static int __init list_sort_test(void)
 {
 	int i, count = 1, err = -ENOMEM;
 	struct debug_el *el;
-	struct list_head *cur, *tmp;
+	struct list_head *cur;
 	LIST_HEAD(head);
 
 	printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
 
-	elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL);
+	elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
 	if (!elts) {
 		printk(KERN_ERR "list_sort_test: error: cannot allocate "
 				"memory\n");
-		goto exit;
+		return err;
 	}
 
 	for (i = 0; i < TEST_LIST_LEN; i++) {
@@ -286,11 +286,9 @@ static int __init list_sort_test(void)
 
 	err = 0;
 exit:
+	for (i = 0; i < TEST_LIST_LEN; i++)
+		kfree(elts[i]);
 	kfree(elts);
-	list_for_each_safe(cur, tmp, &head) {
-		list_del(cur);
-		kfree(container_of(cur, struct debug_el, list));
-	}
 	return err;
 }
 module_init(list_sort_test);
-- 
1.9.2

[PATCH v2 4/4] lib: list_sort.c: Limit number of unused cmp callbacks

[Rasmus Villemoes]

The helper merge_and_restore_back_links() makes sure to call the
caller's cmp function during the final ->prev pointer fixup, so that
the cmp function may call cond_resched(). However, if the cmp function
does not call cond_resched() at all, this is entirely redundant. If it
does, doing at least two function calls for every two pointer
assignments is a bit excessive. This patch limits the calls to once
for every 256 iterations.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/list_sort.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index a34c78c..6b9fdaf 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -47,6 +47,7 @@ static void merge_and_restore_back_links(void *priv,
 				struct list_head *a, struct list_head *b)
 {
 	struct list_head *tail = head;
+	u8 count = 0;
 
 	while (a && b) {
 		/* if equal, take 'a' -- important for sort stability */
@@ -70,7 +71,8 @@ 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->next, tail->next);
+		if (unlikely(!(++count)))
+			(*cmp)(priv, tail->next, tail->next);
 
 		tail->next->prev = tail;
 		tail = tail->next;
-- 
1.9.2

Re: [PATCH v2 0/4] lib: list_sort: Various minor improvements

[Andrew Morton]

On Tue, 24 Jun 2014 12:06:27 +0200 Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:

> Reading the source of lib/list_sort.c, I came up with a few possible
> improvements. I think 4/4 may be a bit controversial, but 1/4, 2/4 and
> 3/4 should be straightforward.
> 

All looks OK to me.

We may as well do the pr_foo() conversion as well.  As often happens,
the results are quite pleasing.

--- a/lib/list_sort.c~lib-list_sortc-convert-to-pr_foo
+++ a/lib/list_sort.c
@@ -1,3 +1,6 @@
+
+#define pr_fmt(fmt) "list_sort_test: " fmt
+
 #include <linux/kernel.h>
 #include <linux/module.h>
 #include <linux/list_sort.h>
@@ -125,9 +128,8 @@ void list_sort(void *priv, struct list_h
 		}
 		if (lev > max_lev) {
 			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
-				printk_once(KERN_DEBUG "list passed to"
-					" list_sort() too long for"
-					" efficiency\n");
+				pr_debug_once("list passed to list_sort() too "
+					      "long for efficiency\n");
 				lev--;
 			}
 			max_lev = lev;
@@ -170,27 +172,25 @@ static struct debug_el **elts __initdata
 static int __init check(struct debug_el *ela, struct debug_el *elb)
 {
 	if (ela->serial >= TEST_LIST_LEN) {
-		printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
-				ela->serial);
+		pr_err("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);
+		pr_err("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");
+		pr_err("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);
+		pr_err("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);
+		pr_err("error: bad poison: %#x/%#x\n",
+			elb->poison1, elb->poison2);
 		return -EINVAL;
 	}
 	return 0;
@@ -214,20 +214,18 @@ static int __init list_sort_test(void)
 	struct list_head *cur;
 	LIST_HEAD(head);
 
-	printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
+	pr_debug("start testing list_sort()\n");
 
 	elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
 	if (!elts) {
-		printk(KERN_ERR "list_sort_test: error: cannot allocate "
-				"memory\n");
+		pr_err("error: cannot allocate memory\n");
 		return err;
 	}
 
 	for (i = 0; i < TEST_LIST_LEN; i++) {
 		el = kmalloc(sizeof(*el), GFP_KERNEL);
 		if (!el) {
-			printk(KERN_ERR "list_sort_test: error: cannot "
-					"allocate memory\n");
+			pr_err("error: cannot allocate memory\n");
 			goto exit;
 		}
 		 /* force some equivalencies */
@@ -247,42 +245,38 @@ static int __init list_sort_test(void)
 		int cmp_result;
 
 		if (cur->next->prev != cur) {
-			printk(KERN_ERR "list_sort_test: error: list is "
-					"corrupted\n");
+			pr_err("error: list is corrupted\n");
 			goto exit;
 		}
 
 		cmp_result = cmp(NULL, cur, cur->next);
 		if (cmp_result > 0) {
-			printk(KERN_ERR "list_sort_test: error: list is not "
-					"sorted\n");
+			pr_err("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_test: error: order of "
-					"equivalent elements not preserved\n");
+			pr_err("error: order of equivalent elements not "
+				"preserved\n");
 			goto exit;
 		}
 
 		if (check(el, el1)) {
-			printk(KERN_ERR "list_sort_test: error: element check "
-					"failed\n");
+			pr_err("error: element check failed\n");
 			goto exit;
 		}
 		count++;
 	}
 	if (head.prev != cur) {
-		printk(KERN_ERR "list_sort_test: error: list is corrupted\n");
+		pr_err("error: list is corrupted\n");
 		goto exit;
 	}
 
 
 	if (count != TEST_LIST_LEN) {
-		printk(KERN_ERR "list_sort_test: error: bad list length %d",
-				count);
+		pr_err("error: bad list length %d", count);
 		goto exit;
 	}
 
_

Re: [PATCH v2 0/4] lib: list_sort: Various minor improvements

[Rasmus Villemoes]

Andrew Morton <akpm@linux-foundation.org> writes:

> On Tue, 24 Jun 2014 12:06:27 +0200 Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:
>
>> Reading the source of lib/list_sort.c, I came up with a few possible
>> improvements. I think 4/4 may be a bit controversial, but 1/4, 2/4 and
>> 3/4 should be straightforward.
>> 
>
> All looks OK to me.

Thanks.

> We may as well do the pr_foo() conversion as well.  As often happens,
> the results are quite pleasing.
>
> --- a/lib/list_sort.c~lib-list_sortc-convert-to-pr_foo
> +++ a/lib/list_sort.c
> @@ -1,3 +1,6 @@
> +
> +#define pr_fmt(fmt) "list_sort_test: " fmt
> +
>  #include <linux/kernel.h>
>  #include <linux/module.h>
>  #include <linux/list_sort.h>
> @@ -125,9 +128,8 @@ void list_sort(void *priv, struct list_h
>  		}
>  		if (lev > max_lev) {
>  			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
> -				printk_once(KERN_DEBUG "list passed to"
> -					" list_sort() too long for"
> -					" efficiency\n");
> +				pr_debug_once("list passed to list_sort() too "
> +					      "long for efficiency\n");

Minor comment: Won't this end up saying "list_sort_test: list passed to
...", despite the list coming from a 'real' user? Maybe change the first
#define to '"list_sort: " fmt', the above message to "passed list too
long for efficiency", and redefine pr_fmt right after #ifdef
CONFIG_TEST_LIST_SORT.

Rasmus

Re: [PATCH v2 0/4] lib: list_sort: Various minor improvements

[Andrew Morton]

On Thu, 26 Jun 2014 00:28:18 +0200 Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:

> > We may as well do the pr_foo() conversion as well.  As often happens,
> > the results are quite pleasing.
> >
> > --- a/lib/list_sort.c~lib-list_sortc-convert-to-pr_foo
> > +++ a/lib/list_sort.c
> > @@ -1,3 +1,6 @@
> > +
> > +#define pr_fmt(fmt) "list_sort_test: " fmt
> > +
> >  #include <linux/kernel.h>
> >  #include <linux/module.h>
> >  #include <linux/list_sort.h>
> > @@ -125,9 +128,8 @@ void list_sort(void *priv, struct list_h
> >  		}
> >  		if (lev > max_lev) {
> >  			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
> > -				printk_once(KERN_DEBUG "list passed to"
> > -					" list_sort() too long for"
> > -					" efficiency\n");
> > +				pr_debug_once("list passed to list_sort() too "
> > +					      "long for efficiency\n");
> 
> Minor comment: Won't this end up saying "list_sort_test: list passed to
> ...", despite the list coming from a 'real' user? Maybe change the first
> #define to '"list_sort: " fmt', the above message to "passed list too
> long for efficiency", and redefine pr_fmt right after #ifdef
> CONFIG_TEST_LIST_SORT.

Yeah, I was hoping nobody would notice that ;)

How about just

		printk_once(KERN_DEBUG "list too long for efficiency\n");

Re: [PATCH v2 0/4] lib: list_sort: Various minor improvements

[Rasmus Villemoes]

Andrew Morton <akpm@linux-foundation.org> writes:

> On Thu, 26 Jun 2014 00:28:18 +0200 Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:
>
>> Minor comment: Won't this end up saying "list_sort_test: list passed to
>> ...", despite the list coming from a 'real' user? Maybe change the first
>> #define to '"list_sort: " fmt', the above message to "passed list too
>> long for efficiency", and redefine pr_fmt right after #ifdef
>> CONFIG_TEST_LIST_SORT.
>
> Yeah, I was hoping nobody would notice that ;)
>
> How about just
>
> 		printk_once(KERN_DEBUG "list too long for efficiency\n");

FWIW, fine by me.

Rasmus