aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig18
-rw-r--r--lib/Kconfig.debug29
-rw-r--r--lib/Makefile15
-rw-r--r--lib/bitmap.c280
-rw-r--r--lib/hweight.c4
-rw-r--r--lib/list_sort.c242
-rw-r--r--lib/math/Kconfig11
-rw-r--r--lib/math/Makefile5
-rw-r--r--lib/math/cordic.c (renamed from lib/cordic.c)0
-rw-r--r--lib/math/div64.c (renamed from lib/div64.c)2
-rw-r--r--lib/math/gcd.c (renamed from lib/gcd.c)0
-rw-r--r--lib/math/int_pow.c32
-rw-r--r--lib/math/int_sqrt.c (renamed from lib/int_sqrt.c)0
-rw-r--r--lib/math/lcm.c (renamed from lib/lcm.c)0
-rw-r--r--lib/math/prime_numbers.c (renamed from lib/prime_numbers.c)0
-rw-r--r--lib/math/rational.c (renamed from lib/rational.c)0
-rw-r--r--lib/math/reciprocal_div.c (renamed from lib/reciprocal_div.c)0
-rw-r--r--lib/plist.c4
-rw-r--r--lib/sort.c254
-rw-r--r--lib/test_bitmap.c67
-rw-r--r--lib/test_sysctl.c18
-rw-r--r--lib/test_vmalloc.c8
22 files changed, 692 insertions, 297 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index f323b85ad11c..8d9239a4156c 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -46,9 +46,6 @@ config HAVE_ARCH_BITREVERSE
This option enables the use of hardware bit-reversal instructions on
architectures which support such operations.
-config RATIONAL
- bool
-
config GENERIC_STRNCPY_FROM_USER
bool
@@ -61,6 +58,8 @@ config GENERIC_NET_UTILS
config GENERIC_FIND_FIRST_BIT
bool
+source "lib/math/Kconfig"
+
config NO_GENERIC_PCI_IOPORT_MAP
bool
@@ -531,12 +530,6 @@ config LRU_CACHE
config CLZ_TAB
bool
-config CORDIC
- tristate "CORDIC algorithm"
- help
- This option provides an implementation of the CORDIC algorithm;
- calculations are in fixed point. Module will be called cordic.
-
config DDR
bool "JEDEC DDR data"
help
@@ -608,6 +601,10 @@ config ARCH_NO_SG_CHAIN
config ARCH_HAS_PMEM_API
bool
+# use memcpy to implement user copies for nommu architectures
+config UACCESS_MEMCPY
+ bool
+
config ARCH_HAS_UACCESS_FLUSHCACHE
bool
@@ -628,9 +625,6 @@ config SBITMAP
config PARMAN
tristate "parman" if COMPILE_TEST
-config PRIME_NUMBERS
- tristate
-
config STRING_SELFTEST
tristate "Test string functions"
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index d695ec1477f3..eae43952902e 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -318,6 +318,20 @@ config HEADERS_CHECK
exported to $(INSTALL_HDR_PATH) (usually 'usr/include' in
your build tree), to make sure they're suitable.
+config OPTIMIZE_INLINING
+ bool "Allow compiler to uninline functions marked 'inline'"
+ help
+ This option determines if the kernel forces gcc to inline the functions
+ developers have marked 'inline'. Doing so takes away freedom from gcc to
+ do what it thinks is best, which is desirable for the gcc 3.x series of
+ compilers. The gcc 4.x series have a rewritten inlining algorithm and
+ enabling this option will generate a smaller kernel there. Hopefully
+ this algorithm is so good that allowing gcc 4.x and above to make the
+ decision will become the default in the future. Until then this option
+ is there to test gcc for this.
+
+ If unsure, say N.
+
config DEBUG_SECTION_MISMATCH
bool "Enable full Section mismatch analysis"
help
@@ -446,6 +460,15 @@ config DEBUG_KERNEL
Say Y here if you are developing drivers or trying to debug and
identify kernel problems.
+config DEBUG_MISC
+ bool "Miscellaneous debug code"
+ default DEBUG_KERNEL
+ depends on DEBUG_KERNEL
+ help
+ Say Y here if you need to enable miscellaneous debug code that should
+ be under a more specific debug option but isn't.
+
+
menu "Memory Debugging"
source "mm/Kconfig.debug"
@@ -519,10 +542,6 @@ config DEBUG_SLAB
allocation as well as poisoning memory on free to catch use of freed
memory. This can make kmalloc/kfree-intensive workloads much slower.
-config DEBUG_SLAB_LEAK
- bool "Memory leak debugging"
- depends on DEBUG_SLAB
-
config SLUB_DEBUG_ON
bool "SLUB debugging on by default"
depends on SLUB && SLUB_DEBUG
@@ -1358,7 +1377,7 @@ config DEBUG_LIST
If unsure, say N.
-config DEBUG_PI_LIST
+config DEBUG_PLIST
bool "Debug priority linked list manipulation"
depends on DEBUG_KERNEL
help
diff --git a/lib/Makefile b/lib/Makefile
index 83d7df2661ff..fb7697031a79 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -30,7 +30,7 @@ endif
lib-y := ctype.o string.o vsprintf.o cmdline.o \
rbtree.o radix-tree.o timerqueue.o xarray.o \
- idr.o int_sqrt.o extable.o \
+ idr.o extable.o \
sha1.o chacha.o irq_regs.o argv_split.o \
flex_proportions.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
@@ -44,11 +44,11 @@ lib-$(CONFIG_SMP) += cpumask.o
lib-y += kobject.o klist.o
obj-y += lockref.o
-obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \
+obj-y += bcd.o sort.o parser.o debug_locks.o random32.o \
bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \
- gcd.o lcm.o list_sort.o uuid.o iov_iter.o clz_ctz.o \
+ list_sort.o uuid.o iov_iter.o clz_ctz.o \
bsearch.o find_bit.o llist.o memweight.o kfifo.o \
- percpu-refcount.o rhashtable.o reciprocal_div.o \
+ percpu-refcount.o rhashtable.o \
once.o refcount.o usercopy.o errseq.o bucket_locks.o \
generic-radix-tree.o
obj-$(CONFIG_STRING_SELFTEST) += test_string.o
@@ -102,6 +102,8 @@ endif
obj-$(CONFIG_DEBUG_INFO_REDUCED) += debug_info.o
CFLAGS_debug_info.o += $(call cc-option, -femit-struct-debug-detailed=any)
+obj-y += math/
+
obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
obj-$(CONFIG_GENERIC_PCI_IOMAP) += pci_iomap.o
obj-$(CONFIG_HAS_IOMEM) += iomap_copy.o devres.o
@@ -121,7 +123,6 @@ obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
obj-$(CONFIG_BITREVERSE) += bitrev.o
obj-$(CONFIG_PACKING) += packing.o
-obj-$(CONFIG_RATIONAL) += rational.o
obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o
obj-$(CONFIG_CRC16) += crc16.o
obj-$(CONFIG_CRC_T10DIF)+= crc-t10dif.o
@@ -195,8 +196,6 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o
-obj-$(CONFIG_CORDIC) += cordic.o
-
obj-$(CONFIG_DQL) += dynamic_queue_limits.o
obj-$(CONFIG_GLOB) += glob.o
@@ -238,8 +237,6 @@ obj-$(CONFIG_ASN1) += asn1_decoder.o
obj-$(CONFIG_FONT_SUPPORT) += fonts/
-obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o
-
hostprogs-y := gen_crc32table
hostprogs-y += gen_crc64table
clean-files := crc32table.h
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 98872e9025da..f235434df87b 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -20,6 +20,8 @@
#include <asm/page.h>
+#include "kstrtox.h"
+
/**
* DOC: bitmap introduction
*
@@ -477,12 +479,128 @@ int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
}
EXPORT_SYMBOL(bitmap_print_to_pagebuf);
+/*
+ * Region 9-38:4/10 describes the following bitmap structure:
+ * 0 9 12 18 38
+ * .........****......****......****......
+ * ^ ^ ^ ^
+ * start off group_len end
+ */
+struct region {
+ unsigned int start;
+ unsigned int off;
+ unsigned int group_len;
+ unsigned int end;
+};
+
+static int bitmap_set_region(const struct region *r,
+ unsigned long *bitmap, int nbits)
+{
+ unsigned int start;
+
+ if (r->end >= nbits)
+ return -ERANGE;
+
+ for (start = r->start; start <= r->end; start += r->group_len)
+ bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
+
+ return 0;
+}
+
+static int bitmap_check_region(const struct region *r)
+{
+ if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
+ return -EINVAL;
+
+ return 0;
+}
+
+static const char *bitmap_getnum(const char *str, unsigned int *num)
+{
+ unsigned long long n;
+ unsigned int len;
+
+ len = _parse_integer(str, 10, &n);
+ if (!len)
+ return ERR_PTR(-EINVAL);
+ if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
+ return ERR_PTR(-EOVERFLOW);
+
+ *num = n;
+ return str + len;
+}
+
+static inline bool end_of_str(char c)
+{
+ return c == '\0' || c == '\n';
+}
+
+static inline bool __end_of_region(char c)
+{
+ return isspace(c) || c == ',';
+}
+
+static inline bool end_of_region(char c)
+{
+ return __end_of_region(c) || end_of_str(c);
+}
+
+/*
+ * The format allows commas and whitespases at the beginning
+ * of the region.
+ */
+static const char *bitmap_find_region(const char *str)
+{
+ while (__end_of_region(*str))
+ str++;
+
+ return end_of_str(*str) ? NULL : str;
+}
+
+static const char *bitmap_parse_region(const char *str, struct region *r)
+{
+ str = bitmap_getnum(str, &r->start);
+ if (IS_ERR(str))
+ return str;
+
+ if (end_of_region(*str))
+ goto no_end;
+
+ if (*str != '-')
+ return ERR_PTR(-EINVAL);
+
+ str = bitmap_getnum(str + 1, &r->end);
+ if (IS_ERR(str))
+ return str;
+
+ if (end_of_region(*str))
+ goto no_pattern;
+
+ if (*str != ':')
+ return ERR_PTR(-EINVAL);
+
+ str = bitmap_getnum(str + 1, &r->off);
+ if (IS_ERR(str))
+ return str;
+
+ if (*str != '/')
+ return ERR_PTR(-EINVAL);
+
+ return bitmap_getnum(str + 1, &r->group_len);
+
+no_end:
+ r->end = r->start;
+no_pattern:
+ r->off = r->end + 1;
+ r->group_len = r->end + 1;
+
+ return end_of_str(*str) ? NULL : str;
+}
+
/**
- * __bitmap_parselist - convert list format ASCII string to bitmap
- * @buf: read nul-terminated user string from this buffer
- * @buflen: buffer size in bytes. If string is smaller than this
- * then it must be terminated with a \0.
- * @is_user: location of buffer, 0 indicates kernel space
+ * bitmap_parselist - convert list format ASCII string to bitmap
+ * @buf: read user string from this buffer; must be terminated
+ * with a \0 or \n.
* @maskp: write resulting mask here
* @nmaskbits: number of bits in mask to be written
*
@@ -498,127 +616,38 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf);
*
* Returns: 0 on success, -errno on invalid input strings. Error values:
*
- * - ``-EINVAL``: second number in range smaller than first
+ * - ``-EINVAL``: wrong region format
* - ``-EINVAL``: invalid character in string
* - ``-ERANGE``: bit number specified too large for mask
+ * - ``-EOVERFLOW``: integer overflow in the input parameters
*/
-static int __bitmap_parselist(const char *buf, unsigned int buflen,
- int is_user, unsigned long *maskp,
- int nmaskbits)
+int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
{
- unsigned int a, b, old_a, old_b;
- unsigned int group_size, used_size, off;
- int c, old_c, totaldigits, ndigits;
- const char __user __force *ubuf = (const char __user __force *)buf;
- int at_start, in_range, in_partial_range;
+ struct region r;
+ long ret;
- totaldigits = c = 0;
- old_a = old_b = 0;
- group_size = used_size = 0;
bitmap_zero(maskp, nmaskbits);
- do {
- at_start = 1;
- in_range = 0;
- in_partial_range = 0;
- a = b = 0;
- ndigits = totaldigits;
-
- /* Get the next cpu# or a range of cpu#'s */
- while (buflen) {
- old_c = c;
- if (is_user) {
- if (__get_user(c, ubuf++))
- return -EFAULT;
- } else
- c = *buf++;
- buflen--;
- if (isspace(c))
- continue;
-
- /* A '\0' or a ',' signal the end of a cpu# or range */
- if (c == '\0' || c == ',')
- break;
- /*
- * whitespaces between digits are not allowed,
- * but it's ok if whitespaces are on head or tail.
- * when old_c is whilespace,
- * if totaldigits == ndigits, whitespace is on head.
- * if whitespace is on tail, it should not run here.
- * as c was ',' or '\0',
- * the last code line has broken the current loop.
- */
- if ((totaldigits != ndigits) && isspace(old_c))
- return -EINVAL;
- if (c == '/') {
- used_size = a;
- at_start = 1;
- in_range = 0;
- a = b = 0;
- continue;
- }
+ while (buf) {
+ buf = bitmap_find_region(buf);
+ if (buf == NULL)
+ return 0;
- if (c == ':') {
- old_a = a;
- old_b = b;
- at_start = 1;
- in_range = 0;
- in_partial_range = 1;
- a = b = 0;
- continue;
- }
+ buf = bitmap_parse_region(buf, &r);
+ if (IS_ERR(buf))
+ return PTR_ERR(buf);
- if (c == '-') {
- if (at_start || in_range)
- return -EINVAL;
- b = 0;
- in_range = 1;
- at_start = 1;
- continue;
- }
+ ret = bitmap_check_region(&r);
+ if (ret)
+ return ret;
- if (!isdigit(c))
- return -EINVAL;
+ ret = bitmap_set_region(&r, maskp, nmaskbits);
+ if (ret)
+ return ret;
+ }
- b = b * 10 + (c - '0');
- if (!in_range)
- a = b;
- at_start = 0;
- totaldigits++;
- }
- if (ndigits == totaldigits)
- continue;
- if (in_partial_range) {
- group_size = a;
- a = old_a;
- b = old_b;
- old_a = old_b = 0;
- } else {
- used_size = group_size = b - a + 1;
- }
- /* if no digit is after '-', it's wrong*/
- if (at_start && in_range)
- return -EINVAL;
- if (!(a <= b) || group_size == 0 || !(used_size <= group_size))
- return -EINVAL;
- if (b >= nmaskbits)
- return -ERANGE;
- while (a <= b) {
- off = min(b - a + 1, used_size);
- bitmap_set(maskp, a, off);
- a += group_size;
- }
- } while (buflen && c == ',');
return 0;
}
-
-int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
-{
- char *nl = strchrnul(bp, '\n');
- int len = nl - bp;
-
- return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
-}
EXPORT_SYMBOL(bitmap_parselist);
@@ -632,23 +661,27 @@ EXPORT_SYMBOL(bitmap_parselist);
* @nmaskbits: size of bitmap, in bits.
*
* Wrapper for bitmap_parselist(), providing it with user buffer.
- *
- * We cannot have this as an inline function in bitmap.h because it needs
- * linux/uaccess.h to get the access_ok() declaration and this causes
- * cyclic dependencies.
*/
int bitmap_parselist_user(const char __user *ubuf,
unsigned int ulen, unsigned long *maskp,
int nmaskbits)
{
- if (!access_ok(ubuf, ulen))
- return -EFAULT;
- return __bitmap_parselist((const char __force *)ubuf,
- ulen, 1, maskp, nmaskbits);
+ char *buf;
+ int ret;
+
+ buf = memdup_user_nul(ubuf, ulen);
+ if (IS_ERR(buf))
+ return PTR_ERR(buf);
+
+ ret = bitmap_parselist(buf, maskp, nmaskbits);
+
+ kfree(buf);
+ return ret;
}
EXPORT_SYMBOL(bitmap_parselist_user);
+#ifdef CONFIG_NUMA
/**
* bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
* @buf: pointer to a bitmap
@@ -757,7 +790,6 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
}
}
-EXPORT_SYMBOL(bitmap_remap);
/**
* bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
@@ -795,7 +827,6 @@ int bitmap_bitremap(int oldbit, const unsigned long *old,
else
return bitmap_ord_to_pos(new, n % w, bits);
}
-EXPORT_SYMBOL(bitmap_bitremap);
/**
* bitmap_onto - translate one bitmap relative to another
@@ -930,7 +961,6 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
m++;
}
}
-EXPORT_SYMBOL(bitmap_onto);
/**
* bitmap_fold - fold larger bitmap into smaller, modulo specified size
@@ -955,7 +985,7 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
for_each_set_bit(oldbit, orig, nbits)
set_bit(oldbit % sz, dst);
}
-EXPORT_SYMBOL(bitmap_fold);
+#endif /* CONFIG_NUMA */
/*
* Common code for bitmap_*_region() routines.
diff --git a/lib/hweight.c b/lib/hweight.c
index 7660d88fd496..c94586b62551 100644
--- a/lib/hweight.c
+++ b/lib/hweight.c
@@ -10,7 +10,6 @@
* The Hamming Weight of a number is the total number of bits set in it.
*/
-#ifndef __HAVE_ARCH_SW_HWEIGHT
unsigned int __sw_hweight32(unsigned int w)
{
#ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER
@@ -27,7 +26,6 @@ unsigned int __sw_hweight32(unsigned int w)
#endif
}
EXPORT_SYMBOL(__sw_hweight32);
-#endif
unsigned int __sw_hweight16(unsigned int w)
{
@@ -46,7 +44,6 @@ unsigned int __sw_hweight8(unsigned int w)
}
EXPORT_SYMBOL(__sw_hweight8);
-#ifndef __HAVE_ARCH_SW_HWEIGHT
unsigned long __sw_hweight64(__u64 w)
{
#if BITS_PER_LONG == 32
@@ -69,4 +66,3 @@ unsigned long __sw_hweight64(__u64 w)
#endif
}
EXPORT_SYMBOL(__sw_hweight64);
-#endif
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 85759928215b..06e900c5587b 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -7,33 +7,41 @@
#include <linux/list_sort.h>
#include <linux/list.h>
-#define MAX_LIST_LENGTH_BITS 20
+typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,
+ struct list_head const *, struct list_head const *);
/*
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
*/
-static struct list_head *merge(void *priv,
- int (*cmp)(void *priv, struct list_head *a,
- struct list_head *b),
+__attribute__((nonnull(2,3,4)))
+static struct list_head *merge(void *priv, cmp_func cmp,
struct list_head *a, struct list_head *b)
{
- struct list_head head, *tail = &head;
+ struct list_head *head, **tail = &head;
- while (a && b) {
+ for (;;) {
/* if equal, take 'a' -- important for sort stability */
- if ((*cmp)(priv, a, b) <= 0) {
- tail->next = a;
+ if (cmp(priv, a, b) <= 0) {
+ *tail = a;
+ tail = &a->next;
a = a->next;
+ if (!a) {
+ *tail = b;
+ break;
+ }
} else {
- tail->next = b;
+ *tail = b;
+ tail = &b->next;
b = b->next;
+ if (!b) {
+ *tail = a;
+ break;
+ }
}
- tail = tail->next;
}
- tail->next = a?:b;
- return head.next;
+ return head;
}
/*
@@ -43,44 +51,52 @@ static struct list_head *merge(void *priv,
* prev-link restoration pass, or maintaining the prev links
* throughout.
*/
-static void merge_and_restore_back_links(void *priv,
- int (*cmp)(void *priv, struct list_head *a,
- struct list_head *b),
- struct list_head *head,
- struct list_head *a, struct list_head *b)
+__attribute__((nonnull(2,3,4,5)))
+static void merge_final(void *priv, cmp_func cmp, struct list_head *head,
+ struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
u8 count = 0;
- while (a && b) {
+ for (;;) {
/* if equal, take 'a' -- important for sort stability */
- if ((*cmp)(priv, a, b) <= 0) {
+ if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
+ tail = a;
a = a->next;
+ if (!a)
+ break;
} else {
tail->next = b;
b->prev = tail;
+ tail = b;
b = b->next;
+ if (!b) {
+ b = a;
+ break;
+ }
}
- tail = tail->next;
}
- tail->next = a ? : b;
+ /* Finish linking remainder of list b on to tail */
+ tail->next = b;
do {
/*
- * In worst cases this loop may run many iterations.
+ * If the merge is highly unbalanced (e.g. the input is
+ * already sorted), 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.
*/
- if (unlikely(!(++count)))
- (*cmp)(priv, tail->next, tail->next);
-
- tail->next->prev = tail;
- tail = tail->next;
- } while (tail->next);
-
+ if (unlikely(!++count))
+ cmp(priv, b, b);
+ b->prev = tail;
+ tail = b;
+ b = b->next;
+ } while (b);
+
+ /* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
@@ -91,55 +107,149 @@ static void merge_and_restore_back_links(void *priv,
* @head: the list to sort
* @cmp: the elements comparison function
*
- * This function implements "merge sort", which has O(nlog(n))
- * complexity.
+ * The comparison funtion @cmp must return > 0 if @a should sort after
+ * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
+ * sort before @b *or* their original order should be preserved. It is
+ * always called with the element that came first in the input in @a,
+ * and list_sort is a stable sort, so it is not necessary to distinguish
+ * the @a < @b and @a == @b cases.
+ *
+ * This is compatible with two styles of @cmp function:
+ * - The traditional style which returns <0 / =0 / >0, or
+ * - Returning a boolean 0/1.
+ * The latter offers a chance to save a few cycles in the comparison
+ * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
+ *
+ * A good way to write a multi-word comparison is
+ * if (a->high != b->high)
+ * return a->high > b->high;
+ * if (a->middle != b->middle)
+ * return a->middle > b->middle;
+ * return a->low > b->low;
+ *
+ *
+ * This mergesort is as eager as possible while always performing at least
+ * 2:1 balanced merges. Given two pending sublists of size 2^k, they are
+ * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
+ *
+ * Thus, it will avoid cache thrashing as long as 3*2^k elements can
+ * fit into the cache. Not quite as good as a fully-eager bottom-up
+ * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
+ * the common case that everything fits into L1.
+ *
+ *
+ * The merging is controlled by "count", the number of elements in the
+ * pending lists. This is beautiully simple code, but rather subtle.
*
- * The comparison function @cmp must return a negative value if @a
- * 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.
+ * Each time we increment "count", we set one bit (bit k) and clear
+ * bits k-1 .. 0. Each time this happens (except the very first time
+ * for each bit, when count increments to 2^k), we merge two lists of
+ * size 2^k into one list of size 2^(k+1).
+ *
+ * This merge happens exactly when the count reaches an odd multiple of
+ * 2^k, which is when we have 2^k elements pending in smaller lists,
+ * so it's safe to merge away two lists of size 2^k.
+ *
+ * After this happens twice, we have created two lists of size 2^(k+1),
+ * which will be merged into a list of size 2^(k+2) before we create
+ * a third list of size 2^(k+1), so there are never more than two pending.
+ *
+ * The number of pending lists of size 2^k is determined by the
+ * state of bit k of "count" plus two extra pieces of information:
+ * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
+ * - Whether the higher-order bits are zero or non-zero (i.e.
+ * is count >= 2^(k+1)).
+ * There are six states we distinguish. "x" represents some arbitrary
+ * bits, and "y" represents some arbitrary non-zero bits:
+ * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
+ * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
+ * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
+ * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * (merge and loop back to state 2)
+ *
+ * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
+ * bit k-1 is set while the more significant bits are non-zero) and
+ * merge them away in the 5->2 transition. Note in particular that just
+ * before the 5->2 transition, all lower-order bits are 11 (state 3),
+ * so there is one list of each smaller size.
+ *
+ * When we reach the end of the input, we merge all the pending
+ * lists, from smallest to largest. If you work through cases 2 to
+ * 5 above, you can see that the number of elements we merge with a list
+ * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
+ * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
*/
+__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b))
{
- struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
- -- last slot is a sentinel */
- int lev; /* index into part[] */
- int max_lev = 0;
- struct list_head *list;
+ struct list_head *list = head->next, *pending = NULL;
+ size_t count = 0; /* Count of pending */
- if (list_empty(head))
+ if (list == head->prev) /* Zero or one elements */
return;
- memset(part, 0, sizeof(part));
-
+ /* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
- list = head->next;
-
- while (list) {
- struct list_head *cur = list;
- list = list->next;
- cur->next = NULL;
- for (lev = 0; part[lev]; lev++) {
- cur = merge(priv, cmp, part[lev], cur);
- part[lev] = NULL;
- }
- if (lev > max_lev) {
- if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
- printk_once(KERN_DEBUG "list too long for efficiency\n");
- lev--;
- }
- max_lev = lev;
+ /*
+ * Data structure invariants:
+ * - All lists are singly linked and null-terminated; prev
+ * pointers are not maintained.
+ * - pending is a prev-linked "list of lists" of sorted
+ * sublists awaiting further merging.
+ * - Each of the sorted sublists is power-of-two in size.
+ * - Sublists are sorted by size and age, smallest & newest at front.
+ * - There are zero to two sublists of each size.
+ * - A pair of pending sublists are merged as soon as the number
+ * of following pending elements equals their size (i.e.
+ * each time count reaches an odd multiple of that size).
+ * That ensures each later final merge will be at worst 2:1.
+ * - Each round consists of:
+ * - Merging the two sublists selected by the highest bit
+ * which flips when count is incremented, and
+ * - Adding an element from the input as a size-1 sublist.
+ */
+ do {
+ size_t bits;
+ struct list_head **tail = &pending;
+
+ /* Find the least-significant clear bit in count */
+ for (bits = count; bits & 1; bits >>= 1)
+ tail = &(*tail)->prev;
+ /* Do the indicated merge */
+ if (likely(bits)) {
+ struct list_head *a = *tail, *b = a->prev;
+
+ a = merge(priv, (cmp_func)cmp, b, a);
+ /* Install the merged result in place of the inputs */
+ a->prev = b->prev;
+ *tail = a;
}
- part[lev] = cur;
- }
- for (lev = 0; lev < max_lev; lev++)
- if (part[lev])
- list = merge(priv, cmp, part[lev], list);
-
- merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
+ /* Move one element from input list to pending */
+ list->prev = pending;
+ pending = list;
+ list = list->next;
+ pending->next = NULL;
+ count++;
+ } while (list);
+
+ /* End of input; merge together all the pending lists. */
+ list = pending;
+ pending = pending->prev;
+ for (;;) {
+ struct list_head *next = pending->prev;
+
+ if (!next)
+ break;
+ list = merge(priv, (cmp_func)cmp, pending, list);
+ pending = next;
+ }
+ /* The final merge, rebuilding prev links */
+ merge_final(priv, (cmp_func)cmp, head, pending, list);
}
EXPORT_SYMBOL(list_sort);
diff --git a/lib/math/Kconfig b/lib/math/Kconfig
new file mode 100644
index 000000000000..73bdf37178d1
--- /dev/null
+++ b/lib/math/Kconfig
@@ -0,0 +1,11 @@
+config CORDIC
+ tristate "CORDIC algorithm"
+ help
+ This option provides an implementation of the CORDIC algorithm;
+ calculations are in fixed point. Module will be called cordic.
+
+config PRIME_NUMBERS
+ tristate
+
+config RATIONAL
+ bool
diff --git a/lib/math/Makefile b/lib/math/Makefile
new file mode 100644
index 000000000000..583bbfebfc09
--- /dev/null
+++ b/lib/math/Makefile
@@ -0,0 +1,5 @@
+obj-y += div64.o gcd.o lcm.o int_pow.o int_sqrt.o reciprocal_div.o
+
+obj-$(CONFIG_CORDIC) += cordic.o
+obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o
+obj-$(CONFIG_RATIONAL) += rational.o
diff --git a/lib/cordic.c b/lib/math/cordic.c
index 8ef27c12956f..8ef27c12956f 100644
--- a/lib/cordic.c
+++ b/lib/math/cordic.c
diff --git a/lib/div64.c b/lib/math/div64.c
index ee146bb4c558..368ca7fd0d82 100644
--- a/lib/div64.c
+++ b/lib/math/div64.c
@@ -10,7 +10,7 @@
* Generic C version of 64bit/32bit division and modulo, with
* 64bit result and 32bit remainder.
*
- * The fast case for (n>>32 == 0) is handled inline by do_div().
+ * The fast case for (n>>32 == 0) is handled inline by do_div().
*
* Code generated for this function might be very inefficient
* for some CPUs. __div64_32() can be overridden by linking arch-specific
diff --git a/lib/gcd.c b/lib/math/gcd.c
index 7948ab27f0a4..7948ab27f0a4 100644
--- a/lib/gcd.c
+++ b/lib/math/gcd.c
diff --git a/lib/math/int_pow.c b/lib/math/int_pow.c
new file mode 100644
index 000000000000..622fc1ab3c74
--- /dev/null
+++ b/lib/math/int_pow.c
@@ -0,0 +1,32 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * An integer based power function
+ *
+ * Derived from drivers/video/backlight/pwm_bl.c
+ */
+
+#include <linux/export.h>
+#include <linux/kernel.h>
+#include <linux/types.h>
+
+/**
+ * int_pow - computes the exponentiation of the given base and exponent
+ * @base: base which will be raised to the given power
+ * @exp: power to be raised to
+ *
+ * Computes: pow(base, exp), i.e. @base raised to the @exp power
+ */
+u64 int_pow(u64 base, unsigned int exp)
+{
+ u64 result = 1;
+
+ while (exp) {
+ if (exp & 1)
+ result *= base;
+ exp >>= 1;
+ base *= base;
+ }
+
+ return result;
+}
+EXPORT_SYMBOL_GPL(int_pow);
diff --git a/lib/int_sqrt.c b/lib/math/int_sqrt.c
index 30e0f9770f88..30e0f9770f88 100644
--- a/lib/int_sqrt.c
+++ b/lib/math/int_sqrt.c
diff --git a/lib/lcm.c b/lib/math/lcm.c
index 03d7fcb420b5..03d7fcb420b5 100644
--- a/lib/lcm.c
+++ b/lib/math/lcm.c
diff --git a/lib/prime_numbers.c b/lib/math/prime_numbers.c
index 550eec457c2e..550eec457c2e 100644
--- a/lib/prime_numbers.c
+++ b/lib/math/prime_numbers.c
diff --git a/lib/rational.c b/lib/math/rational.c
index ba7443677c90..ba7443677c90 100644
--- a/lib/rational.c
+++ b/lib/math/rational.c
diff --git a/lib/reciprocal_div.c b/lib/math/reciprocal_div.c
index bf043258fa00..bf043258fa00 100644
--- a/lib/reciprocal_div.c
+++ b/lib/math/reciprocal_div.c
diff --git a/lib/plist.c b/lib/plist.c
index 199408f91057..d3bd8827186f 100644
--- a/lib/plist.c
+++ b/lib/plist.c
@@ -26,7 +26,7 @@
#include <linux/bug.h>
#include <linux/plist.h>
-#ifdef CONFIG_DEBUG_PI_LIST
+#ifdef CONFIG_DEBUG_PLIST
static struct plist_head test_head;
@@ -173,7 +173,7 @@ void plist_requeue(struct plist_node *node, struct plist_head *head)
plist_check_head(head);
}
-#ifdef CONFIG_DEBUG_PI_LIST
+#ifdef CONFIG_DEBUG_PLIST
#include <linux/sched.h>
#include <linux/sched/clock.h>
#include <linux/module.h>
diff --git a/lib/sort.c b/lib/sort.c
index d6b7a202b0b6..50855ea8c262 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -1,8 +1,13 @@
// SPDX-License-Identifier: GPL-2.0
/*
- * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
+ * A fast, small, non-recursive O(n log n) sort for the Linux kernel
*
- * Jan 23 2005 Matt Mackall <mpm@selenic.com>
+ * This performs n*log2(n) + 0.37*n + o(n) comparisons on average,
+ * and 1.5*n*log2(n) + O(n) in the (very contrived) worst case.
+ *
+ * Glibc qsort() manages n*log2(n) - 1.26*n for random inputs (1.63*n
+ * better) at the expense of stack usage and much larger code to avoid
+ * quicksort's O(n^2) worst case.
*/
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
@@ -11,35 +16,155 @@
#include <linux/export.h>
#include <linux/sort.h>
-static int alignment_ok(const void *base, int align)
+/**
+ * is_aligned - is this pointer & size okay for word-wide copying?
+ * @base: pointer to data
+ * @size: size of each element
+ * @align: required alignment (typically 4 or 8)
+ *
+ * Returns true if elements can be copied using word loads and stores.
+ * The size must be a multiple of the alignment, and the base address must
+ * be if we do not have CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS.
+ *
+ * For some reason, gcc doesn't know to optimize "if (a & mask || b & mask)"
+ * to "if ((a | b) & mask)", so we do that by hand.
+ */
+__attribute_const__ __always_inline
+static bool is_aligned(const void *base, size_t size, unsigned char align)
{
- return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
- ((unsigned long)base & (align - 1)) == 0;
+ unsigned char lsbits = (unsigned char)size;
+
+ (void)base;
+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+ lsbits |= (unsigned char)(uintptr_t)base;
+#endif
+ return (lsbits & (align - 1)) == 0;
}
-static void u32_swap(void *a, void *b, int size)
+/**
+ * swap_words_32 - swap two elements in 32-bit chunks
+ * @a, @b: pointers to the elements
+ * @size: element size (must be a multiple of 4)
+ *
+ * Exchange the two objects in memory. This exploits base+index addressing,
+ * which basically all CPUs have, to minimize loop overhead computations.
+ *
+ * For some reason, on x86 gcc 7.3.0 adds a redundant test of n at the
+ * bottom of the loop, even though the zero flag is stil valid from the
+ * subtract (since the intervening mov instructions don't alter the flags).
+ * Gcc 8.1.0 doesn't have that problem.
+ */
+static void swap_words_32(void *a, void *b, size_t n)
{
- u32 t = *(u32 *)a;
- *(u32 *)a = *(u32 *)b;
- *(u32 *)b = t;
+ do {
+ u32 t = *(u32 *)(a + (n -= 4));
+ *(u32 *)(a + n) = *(u32 *)(b + n);
+ *(u32 *)(b + n) = t;
+ } while (n);
}
-static void u64_swap(void *a, void *b, int size)
+/**
+ * swap_words_64 - swap two elements in 64-bit chunks
+ * @a, @b: pointers to the elements
+ * @size: element size (must be a multiple of 8)
+ *
+ * Exchange the two objects in memory. This exploits base+index
+ * addressing, which basically all CPUs have, to minimize loop overhead
+ * computations.
+ *
+ * We'd like to use 64-bit loads if possible. If they're not, emulating
+ * one requires base+index+4 addressing which x86 has but most other
+ * processors do not. If CONFIG_64BIT, we definitely have 64-bit loads,
+ * but it's possible to have 64-bit loads without 64-bit pointers (e.g.
+ * x32 ABI). Are there any cases the kernel needs to worry about?
+ */
+static void swap_words_64(void *a, void *b, size_t n)
{
- u64 t = *(u64 *)a;
- *(u64 *)a = *(u64 *)b;
- *(u64 *)b = t;
+ do {
+#ifdef CONFIG_64BIT
+ u64 t = *(u64 *)(a + (n -= 8));
+ *(u64 *)(a + n) = *(u64 *)(b + n);
+ *(u64 *)(b + n) = t;
+#else
+ /* Use two 32-bit transfers to avoid base+index+4 addressing */
+ u32 t = *(u32 *)(a + (n -= 4));
+ *(u32 *)(a + n) = *(u32 *)(b + n);
+ *(u32 *)(b + n) = t;
+
+ t = *(u32 *)(a + (n -= 4));
+ *(u32 *)(a + n) = *(u32 *)(b + n);
+ *(u32 *)(b + n) = t;
+#endif
+ } while (n);
}
-static void generic_swap(void *a, void *b, int size)
+/**
+ * swap_bytes - swap two elements a byte at a time
+ * @a, @b: pointers to the elements
+ * @size: element size
+ *
+ * This is the fallback if alignment doesn't allow using larger chunks.
+ */
+static void swap_bytes(void *a, void *b, size_t n)
{
- char t;
-
do {
- t = *(char *)a;
- *(char *)a++ = *(char *)b;
- *(char *)b++ = t;
- } while (--size > 0);
+ char t = ((char *)a)[--n];
+ ((char *)a)[n] = ((char *)b)[n];
+ ((char *)b)[n] = t;
+ } while (n);
+}
+
+typedef void (*swap_func_t)(void *a, void *b, int size);
+
+/*
+ * The values are arbitrary as long as they can't be confused with
+ * a pointer, but small integers make for the smallest compare
+ * instructions.
+ */
+#define SWAP_WORDS_64 (swap_func_t)0
+#define SWAP_WORDS_32 (swap_func_t)1
+#define SWAP_BYTES (swap_func_t)2
+
+/*
+ * The function pointer is last to make tail calls most efficient if the
+ * compiler decides not to inline this function.
+ */
+static void do_swap(void *a, void *b, size_t size, swap_func_t swap_func)
+{
+ if (swap_func == SWAP_WORDS_64)
+ swap_words_64(a, b, size);
+ else if (swap_func == SWAP_WORDS_32)
+ swap_words_32(a, b, size);
+ else if (swap_func == SWAP_BYTES)
+ swap_bytes(a, b, size);
+ else
+ swap_func(a, b, (int)size);
+}
+
+/**
+ * parent - given the offset of the child, find the offset of the parent.
+ * @i: the offset of the heap element whose parent is sought. Non-zero.
+ * @lsbit: a precomputed 1-bit mask, equal to "size & -size"
+ * @size: size of each element
+ *
+ * In terms of array indexes, the parent of element j = @i/@size is simply
+ * (j-1)/2. But when working in byte offsets, we can't use implicit
+ * truncation of integer divides.
+ *
+ * Fortunately, we only need one bit of the quotient, not the full divide.
+ * @size has a least significant bit. That bit will be clear if @i is
+ * an even multiple of @size, and set if it's an odd multiple.
+ *
+ * Logically, we're doing "if (i & lsbit) i -= size;", but since the
+ * branch is unpredictable, it's done with a bit of clever branch-free
+ * code instead.
+ */
+__attribute_const__ __always_inline
+static size_t parent(size_t i, unsigned int lsbit, size_t size)
+{
+ i -= size;
+ i -= size & -(i & lsbit);
+ return i / 2;
}
/**
@@ -50,57 +175,78 @@ static void generic_swap(void *a, void *b, int size)
* @cmp_func: pointer to comparison function
* @swap_func: pointer to swap function or NULL
*
- * This function does a heapsort on the given array. You may provide a
- * swap_func function optimized to your element type.
+ * This function does a heapsort on the given array. You may provide
+ * a swap_func function if you need to do something more than a memory
+ * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
+ * avoids a slow retpoline and so is significantly faster.
*
* Sorting time is O(n log n) both on average and worst-case. While
- * qsort is about 20% faster on average, it suffers from exploitable
+ * quicksort is slightly faster on average, it suffers from exploitable
* O(n*n) worst-case behavior and extra memory requirements that make
* it less suitable for kernel use.
*/
-
void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
void (*swap_func)(void *, void *, int size))
{
/* pre-scale counters for performance */
- int i = (num/2 - 1) * size, n = num * size, c, r;
+ size_t n = num * size, a = (num/2) * size;
+ const unsigned int lsbit = size & -size; /* Used to find parent */
+
+ if (!a) /* num < 2 || size == 0 */
+ return;
if (!swap_func) {
- if (size == 4 && alignment_ok(base, 4))
- swap_func = u32_swap;
- else if (size == 8 && alignment_ok(base, 8))
- swap_func = u64_swap;
+ if (is_aligned(base, size, 8))
+ swap_func = SWAP_WORDS_64;
+ else if (is_aligned(base, size, 4))
+ swap_func = SWAP_WORDS_32;
else
- swap_func = generic_swap;
+ swap_func = SWAP_BYTES;
}
- /* heapify */
- for ( ; i >= 0; i -= size) {
- for (r = i; r * 2 + size < n; r = c) {
- c = r * 2 + size;
- if (c < n - size &&
- cmp_func(base + c, base + c + size) < 0)
- c += size;
- if (cmp_func(base + r, base + c) >= 0)
- break;
- swap_func(base + r, base + c, size);
- }
- }
+ /*
+ * Loop invariants:
+ * 1. elements [a,n) satisfy the heap property (compare greater than
+ * all of their children),
+ * 2. elements [n,num*size) are sorted, and
+ * 3. a <= b <= c <= d <= n (whenever they are valid).
+ */
+ for (;;) {
+ size_t b, c, d;
+
+ if (a) /* Building heap: sift down --a */
+ a -= size;
+ else if (n -= size) /* Sorting: Extract root to --n */
+ do_swap(base, base + n, size, swap_func);
+ else /* Sort complete */
+ break;
- /* sort */
- for (i = n - size; i > 0; i -= size) {
- swap_func(base, base + i, size);
- for (r = 0; r * 2 + size < i; r = c) {
- c = r * 2 + size;
- if (c < i - size &&
- cmp_func(base + c, base + c + size) < 0)
- c += size;
- if (cmp_func(base + r, base + c) >= 0)
- break;
- swap_func(base + r, base + c, size);
+ /*
+ * Sift element at "a" down into heap. This is the
+ * "bottom-up" variant, which significantly reduces
+ * calls to cmp_func(): we find the sift-down path all
+ * the way to the leaves (one compare per level), then
+ * backtrack to find where to insert the target element.
+ *
+ * Because elements tend to sift down close to the leaves,
+ * this uses fewer compares than doing two per level
+ * on the way down. (A bit more than half as many on
+ * average, 3/4 worst-case.)
+ */
+ for (b = a; c = 2*b + size, (d = c + size) < n;)
+ b = cmp_func(base + c, base + d) >= 0 ? c : d;
+ if (d == n) /* Special case last leaf with no sibling */
+ b = c;
+
+ /* Now backtrack from "b" to the correct location for "a" */
+ while (b != a && cmp_func(base + a, base + b) >= 0)
+ b = parent(b, lsbit, size);
+ c = b; /* Where "a" belongs */
+ while (b != a) { /* Shift it into place */
+ b = parent(b, lsbit, size);
+ do_swap(base + b, base + c, size, swap_func);
}
}
}
-
EXPORT_SYMBOL(sort);
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 792d90608052..d3a501f2a81a 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -11,6 +11,7 @@
#include <linux/printk.h>
#include <linux/slab.h>
#include <linux/string.h>
+#include <linux/uaccess.h>
#include "../tools/testing/selftests/kselftest_module.h"
@@ -226,7 +227,8 @@ static const unsigned long exp[] __initconst = {
BITMAP_FROM_U64(0xffffffff),
BITMAP_FROM_U64(0xfffffffe),
BITMAP_FROM_U64(0x3333333311111111ULL),
- BITMAP_FROM_U64(0xffffffff77777777ULL)
+ BITMAP_FROM_U64(0xffffffff77777777ULL),
+ BITMAP_FROM_U64(0),
};
static const unsigned long exp2[] __initconst = {
@@ -249,55 +251,93 @@ static const struct test_bitmap_parselist parselist_tests[] __initconst = {
{0, "1-31:4/4", &exp[9 * step], 32, 0},
{0, "0-31:1/4,32-63:2/4", &exp[10 * step], 64, 0},
{0, "0-31:3/4,32-63:4/4", &exp[11 * step], 64, 0},
+ {0, " ,, 0-31:3/4 ,, 32-63:4/4 ,, ", &exp[11 * step], 64, 0},
{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4", exp2, 128, 0},
{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
+ {0, "", &exp[12 * step], 8, 0},
+ {0, "\n", &exp[12 * step], 8, 0},
+ {0, ",, ,, , , ,", &exp[12 * step], 8, 0},
+ {0, " , ,, , , ", &exp[12 * step], 8, 0},
+ {0, " , ,, , , \n", &exp[12 * step], 8, 0},
+
{-EINVAL, "-1", NULL, 8, 0},
{-EINVAL, "-0", NULL, 8, 0},
{-EINVAL, "10-1", NULL, 8, 0},
{-EINVAL, "0-31:", NULL, 8, 0},
{-EINVAL, "0-31:0", NULL, 8, 0},
+ {-EINVAL, "0-31:0/", NULL, 8, 0},
{-EINVAL, "0-31:0/0", NULL, 8, 0},
{-EINVAL, "0-31:1/0", NULL, 8, 0},
{-EINVAL, "0-31:10/1", NULL, 8, 0},
+ {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
+
+ {-EINVAL, "a-31", NULL, 8, 0},
+ {-EINVAL, "0-a1", NULL, 8, 0},
+ {-EINVAL, "a-31:10/1", NULL, 8, 0},
+ {-EINVAL, "0-31:a/1", NULL, 8, 0},
+ {-EINVAL, "0-\n", NULL, 8, 0},
};
-static void __init test_bitmap_parselist(void)
+static void __init __test_bitmap_parselist(int is_user)
{
int i;
int err;
- cycles_t cycles;
+ ktime_t time;
DECLARE_BITMAP(bmap, 2048);
+ char *mode = is_user ? "_user" : "";
for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
#define ptest parselist_tests[i]
- cycles = get_cycles();
- err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
- cycles = get_cycles() - cycles;
+ if (is_user) {
+ mm_segment_t orig_fs = get_fs();
+ size_t len = strlen(ptest.in);
+
+ set_fs(KERNEL_DS);
+ time = ktime_get();
+ err = bitmap_parselist_user(ptest.in, len,
+ bmap, ptest.nbits);
+ time = ktime_get() - time;
+ set_fs(orig_fs);
+ } else {
+ time = ktime_get();
+ err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
+ time = ktime_get() - time;
+ }
if (err != ptest.errno) {
- pr_err("test %d: input is %s, errno is %d, expected %d\n",
- i, ptest.in, err, ptest.errno);
+ pr_err("parselist%s: %d: input is %s, errno is %d, expected %d\n",
+ mode, i, ptest.in, err, ptest.errno);
continue;
}
if (!err && ptest.expected
&& !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
- pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
- i, ptest.in, bmap[0], *ptest.expected);
+ pr_err("parselist%s: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
+ mode, i, ptest.in, bmap[0],
+ *ptest.expected);
continue;
}
if (ptest.flags & PARSE_TIME)
- pr_err("test %d: input is '%s' OK, Time: %llu\n",
- i, ptest.in,
- (unsigned long long)cycles);
+ pr_err("parselist%s: %d: input is '%s' OK, Time: %llu\n",
+ mode, i, ptest.in, time);
}
}
+static void __init test_bitmap_parselist(void)
+{
+ __test_bitmap_parselist(0);
+}
+
+static void __init test_bitmap_parselist_user(void)
+{
+ __test_bitmap_parselist(1);
+}
+
#define EXP_BYTES (sizeof(exp) * 8)
static void __init test_bitmap_arr32(void)
@@ -370,6 +410,7 @@ static void __init selftest(void)
test_copy();
test_bitmap_arr32();
test_bitmap_parselist();
+ test_bitmap_parselist_user();
test_mem_optimisations();
}
diff --git a/lib/test_sysctl.c b/lib/test_sysctl.c
index 3dd801c1c85b..566dad3f4196 100644
--- a/lib/test_sysctl.c
+++ b/lib/test_sysctl.c
@@ -47,6 +47,9 @@ struct test_sysctl_data {
unsigned int uint_0001;
char string_0001[65];
+
+#define SYSCTL_TEST_BITMAP_SIZE 65536
+ unsigned long *bitmap_0001;
};
static struct test_sysctl_data test_data = {
@@ -102,6 +105,13 @@ static struct ctl_table test_table[] = {
.mode = 0644,
.proc_handler = proc_dostring,
},
+ {
+ .procname = "bitmap_0001",
+ .data = &test_data.bitmap_0001,
+ .maxlen = SYSCTL_TEST_BITMAP_SIZE,
+ .mode = 0644,
+ .proc_handler = proc_do_large_bitmap,
+ },
{ }
};
@@ -129,15 +139,21 @@ static struct ctl_table_header *test_sysctl_header;
static int __init test_sysctl_init(void)
{
+ test_data.bitmap_0001 = kzalloc(SYSCTL_TEST_BITMAP_SIZE/8, GFP_KERNEL);
+ if (!test_data.bitmap_0001)
+ return -ENOMEM;
test_sysctl_header = register_sysctl_table(test_sysctl_root_table);
- if (!test_sysctl_header)
+ if (!test_sysctl_header) {
+ kfree(test_data.bitmap_0001);
return -ENOMEM;
+ }
return 0;
}
late_initcall(test_sysctl_init);
static void __exit test_sysctl_exit(void)
{
+ kfree(test_data.bitmap_0001);
if (test_sysctl_header)
unregister_sysctl_table(test_sysctl_header);
}
diff --git a/lib/test_vmalloc.c b/lib/test_vmalloc.c
index f832b095afba..8bbefcaddfe8 100644
--- a/lib/test_vmalloc.c
+++ b/lib/test_vmalloc.c
@@ -384,12 +384,11 @@ static int test_func(void *private)
{
struct test_driver *t = private;
int random_array[ARRAY_SIZE(test_case_array)];
- int index, i, j, ret;
+ int index, i, j;
ktime_t kt;
u64 delta;
- ret = set_cpus_allowed_ptr(current, cpumask_of(t->cpu));
- if (ret < 0)
+ if (set_cpus_allowed_ptr(current, cpumask_of(t->cpu)) < 0)
pr_err("Failed to set affinity to %d CPU\n", t->cpu);
for (i = 0; i < ARRAY_SIZE(test_case_array); i++)
@@ -415,8 +414,7 @@ static int test_func(void *private)
kt = ktime_get();
for (j = 0; j < test_repeat_count; j++) {
- ret = test_case_array[index].test_func();
- if (!ret)
+ if (!test_case_array[index].test_func())
per_cpu_test_data[t->cpu][index].test_passed++;
else
per_cpu_test_data[t->cpu][index].test_failed++;
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.