linux/lib/list_sort.c, branch v3.19

lib/list_sort.c: convert to pr_foo

2014-08-07T01:01:25Z

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: Limit number of unused cmp callbacks

2014-08-07T01:01:25Z

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_test(): simplify and harden cleanup

2014-08-07T01:01:25Z

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_test(): add extra corruption check

2014-08-07T01:01:25Z

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_test(): return -ENOMEM when allocation fails

2014-08-07T01:01:25Z

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/: rename random32() to prandom_u32()

2013-04-30T01:28:42Z

Use preferable function name which implies using a pseudo-random number generator. Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/list_sort: test: check element addresses

2010-10-26T23:52:19Z

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 Cc: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/list_sort: test: unify test messages

2010-10-26T23:52:19Z

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 Cc: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/list_sort: test: improve errors handling

2010-10-26T23:52:19Z

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 Cc: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/list_sort: test: use generic random32

2010-10-26T23:52:19Z

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 Cc: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds