linux-toradex.git/lib/list_sort.c, branch v4.4.93

lib/list_sort: use late_initcall to hook in self tests

2015-06-16T18:12:35+00:00

This was using module_init, but there is no way this code can
be modular.  In the non-modular case, a module_init becomes a
device_initcall, but this really isn't a device.   So we should
choose a more appropriate initcall bucket to put it in.

Assuming boot time self tests need to be observed over a console
to be useful, and that the console device could possibly not be
fully functional until after device_initcall, we move this to the
late_initcall bucket, which is immediately after device_initcall.

Cc: Andrew Morton 
Signed-off-by: Paul Gortmaker

lib/list_sort.c: rearrange includes

2015-02-13T02:54:15+00:00

Memory allocation only happens in the self test, just as random numbers
are only used there.  So move the inclusion of slab.h inside the
CONFIG_TEST_LIST_SORT.

We don't need module.h and all of the stuff it carries with it, so replace
with export.h and compiler.h.  Unfortunately, the ARRAY_SIZE macro from
kernel.h requires the user to ensure bug.h is also included (for
BUILD_BUG_ON_ZERO, used by __must_be_array).  We used to get that through
some maze of nested includes, but just include it explicitly.

linux/string.h is then only included implicitly through
kernel.h->printk.h->dynamic_debug.h, but only if !CONFIG_DYNAMIC_DEBUG, so
just include it explicitly (for memset).

objdump -d says the generated code is the same, and wc -l says that
lib/.list_sort.o.cmd went from 579 to 165 lines.

Signed-off-by: Rasmus Villemoes 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

lib/list_sort.c: convert to pr_foo

2014-08-07T01:01:25+00:00

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:25+00:00

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:25+00:00

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:25+00:00

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:25+00:00

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:42+00:00

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:19+00:00

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:19+00:00

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