From 27d555d101c820ac4b1962680bd0192993c6e4e0 Mon Sep 17 00:00:00 2001 From: Rasmus Villemoes Date: Wed, 6 Aug 2014 16:09:38 -0700 Subject: lib: list_sort_test(): return -ENOMEM when allocation fails Signed-off-by: Rasmus Villemoes Cc: Artem Bityutskiy Cc: Don Mullis Cc: Dave Chinner Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_sort.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lib/list_sort.c') diff --git a/lib/list_sort.c b/lib/list_sort.c index 1183fa70a44..291412ade89 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; -- cgit v1.2.3-70-g09d2 From 9d418dcc6d15539a9567b2ad7fe7473648989f44 Mon Sep 17 00:00:00 2001 From: Rasmus Villemoes Date: Wed, 6 Aug 2014 16:09:40 -0700 Subject: lib: list_sort_test(): add extra corruption check 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 Cc: Artem Bityutskiy Cc: Don Mullis Cc: Dave Chinner Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_sort.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'lib/list_sort.c') diff --git a/lib/list_sort.c b/lib/list_sort.c index 291412ade89..fbdbc867b25 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", -- cgit v1.2.3-70-g09d2 From 694123031d12458a343492528fa40113e5ec843e Mon Sep 17 00:00:00 2001 From: Rasmus Villemoes Date: Wed, 6 Aug 2014 16:09:42 -0700 Subject: lib: list_sort_test(): simplify and harden cleanup 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 Cc: Artem Bityutskiy Cc: Don Mullis Cc: Dave Chinner Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_sort.c | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) (limited to 'lib/list_sort.c') diff --git a/lib/list_sort.c b/lib/list_sort.c index fbdbc867b25..a34c78c30d5 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); -- cgit v1.2.3-70-g09d2 From 61b3d6c48f059bb054b0019088736dab6c2ac0ec Mon Sep 17 00:00:00 2001 From: Rasmus Villemoes Date: Wed, 6 Aug 2014 16:09:44 -0700 Subject: lib: list_sort.c: Limit number of unused cmp callbacks 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 Cc: Artem Bityutskiy Cc: Don Mullis Cc: Dave Chinner Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_sort.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'lib/list_sort.c') diff --git a/lib/list_sort.c b/lib/list_sort.c index a34c78c30d5..6b9fdaf1d32 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; -- cgit v1.2.3-70-g09d2 From d0da23b0debcef135c866cc8117d197fb40a6079 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Wed, 6 Aug 2014 16:09:46 -0700 Subject: lib/list_sort.c: convert to pr_foo Cc: Rasmus Villemoes Cc: Artem Bityutskiy Cc: Don Mullis Cc: Dave Chinner Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_sort.c | 49 +++++++++++++++++++++---------------------------- 1 file changed, 21 insertions(+), 28 deletions(-) (limited to 'lib/list_sort.c') diff --git a/lib/list_sort.c b/lib/list_sort.c index 6b9fdaf1d32..12bcba1c861 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -1,3 +1,6 @@ + +#define pr_fmt(fmt) "list_sort_test: " fmt + #include #include #include @@ -125,9 +128,7 @@ void list_sort(void *priv, struct list_head *head, } 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"); + printk_once(KERN_DEBUG "list too long for efficiency\n"); lev--; } max_lev = lev; @@ -170,27 +171,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 +213,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 +244,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; } -- cgit v1.2.3-70-g09d2