diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig | 6 | ||||
| -rw-r--r-- | lib/Makefile | 4 | ||||
| -rw-r--r-- | lib/bitmap.c | 20 | ||||
| -rw-r--r-- | lib/sg_split.c | 12 | ||||
| -rw-r--r-- | lib/sort.c | 34 | ||||
| -rw-r--r-- | lib/stackdepot.c | 4 | ||||
| -rw-r--r-- | lib/timerqueue.c | 30 |
7 files changed, 72 insertions, 38 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index f33d66fc0e86..4e6b1c3e4c98 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -631,6 +631,9 @@ config SBITMAP config PARMAN tristate "parman" if COMPILE_TEST +config OBJAGG + tristate "objagg" if COMPILE_TEST + config STRING_SELFTEST tristate "Test string functions" @@ -653,6 +656,3 @@ config GENERIC_LIB_CMPDI2 config GENERIC_LIB_UCMPDI2 bool - -config OBJAGG - tristate "objagg" if COMPILE_TEST diff --git a/lib/Makefile b/lib/Makefile index 29c02a924973..c5892807e06f 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -21,10 +21,6 @@ KCOV_INSTRUMENT_dynamic_debug.o := n ifdef CONFIG_AMD_MEM_ENCRYPT KASAN_SANITIZE_string.o := n -ifdef CONFIG_FUNCTION_TRACER -CFLAGS_REMOVE_string.o = -pg -endif - CFLAGS_string.o := $(call cc-option, -fno-stack-protector) endif diff --git a/lib/bitmap.c b/lib/bitmap.c index bbe2589e8497..f9e834841e94 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -59,6 +59,26 @@ int __bitmap_equal(const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_equal); +bool __bitmap_or_equal(const unsigned long *bitmap1, + const unsigned long *bitmap2, + const unsigned long *bitmap3, + unsigned int bits) +{ + unsigned int k, lim = bits / BITS_PER_LONG; + unsigned long tmp; + + for (k = 0; k < lim; ++k) { + if ((bitmap1[k] | bitmap2[k]) != bitmap3[k]) + return false; + } + + if (!(bits % BITS_PER_LONG)) + return true; + + tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k]; + return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0; +} + void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits) { unsigned int k, lim = BITS_TO_LONGS(bits); diff --git a/lib/sg_split.c b/lib/sg_split.c index 9982c63d1063..60a0babebf2e 100644 --- a/lib/sg_split.c +++ b/lib/sg_split.c @@ -176,11 +176,13 @@ int sg_split(struct scatterlist *in, const int in_mapped_nents, * The order of these 3 calls is important and should be kept. */ sg_split_phys(splitters, nb_splits); - ret = sg_calculate_split(in, in_mapped_nents, nb_splits, skip, - split_sizes, splitters, true); - if (ret < 0) - goto err; - sg_split_mapped(splitters, nb_splits); + if (in_mapped_nents) { + ret = sg_calculate_split(in, in_mapped_nents, nb_splits, skip, + split_sizes, splitters, true); + if (ret < 0) + goto err; + sg_split_mapped(splitters, nb_splits); + } for (i = 0; i < nb_splits; i++) { out[i] = splitters[i].out_sg; diff --git a/lib/sort.c b/lib/sort.c index cf408aec3733..d54cf97e9548 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -144,6 +144,18 @@ static void do_swap(void *a, void *b, size_t size, swap_func_t swap_func) swap_func(a, b, (int)size); } +typedef int (*cmp_func_t)(const void *, const void *); +typedef int (*cmp_r_func_t)(const void *, const void *, const void *); +#define _CMP_WRAPPER ((cmp_r_func_t)0L) + +static int do_cmp(const void *a, const void *b, + cmp_r_func_t cmp, const void *priv) +{ + if (cmp == _CMP_WRAPPER) + return ((cmp_func_t)(priv))(a, b); + return cmp(a, b, priv); +} + /** * 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. @@ -171,12 +183,13 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size) } /** - * sort - sort an array of elements + * sort_r - sort an array of elements * @base: pointer to data to sort * @num: number of elements * @size: size of each element * @cmp_func: pointer to comparison function * @swap_func: pointer to swap function or NULL + * @priv: third argument passed to comparison function * * 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 @@ -188,9 +201,10 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size) * 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)) +void sort_r(void *base, size_t num, size_t size, + int (*cmp_func)(const void *, const void *, const void *), + void (*swap_func)(void *, void *, int size), + const void *priv) { /* pre-scale counters for performance */ size_t n = num * size, a = (num/2) * size; @@ -238,12 +252,12 @@ void sort(void *base, size_t num, size_t size, * 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; + b = do_cmp(base + c, base + d, cmp_func, priv) >= 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) + while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0) b = parent(b, lsbit, size); c = b; /* Where "a" belongs */ while (b != a) { /* Shift it into place */ @@ -252,4 +266,12 @@ void sort(void *base, size_t num, size_t size, } } } +EXPORT_SYMBOL(sort_r); + +void sort(void *base, size_t num, size_t size, + int (*cmp_func)(const void *, const void *), + void (*swap_func)(void *, void *, int size)) +{ + return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func); +} EXPORT_SYMBOL(sort); diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 66cab785bea0..ed717dd08ff3 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -87,7 +87,7 @@ static bool init_stack_slab(void **prealloc) stack_slabs[depot_index + 1] = *prealloc; /* * This smp_store_release pairs with smp_load_acquire() from - * |next_slab_inited| above and in depot_save_stack(). + * |next_slab_inited| above and in stack_depot_save(). */ smp_store_release(&next_slab_inited, 1); } @@ -114,7 +114,7 @@ static struct stack_record *depot_alloc_stack(unsigned long *entries, int size, depot_offset = 0; /* * smp_store_release() here pairs with smp_load_acquire() from - * |next_slab_inited| in depot_save_stack() and + * |next_slab_inited| in stack_depot_save() and * init_stack_slab(). */ if (depot_index + 1 < STACK_ALLOC_MAX_SLABS) diff --git a/lib/timerqueue.c b/lib/timerqueue.c index bc7e64df27df..c52710964593 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -26,9 +26,10 @@ */ bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) { - struct rb_node **p = &head->head.rb_node; + struct rb_node **p = &head->rb_root.rb_root.rb_node; struct rb_node *parent = NULL; - struct timerqueue_node *ptr; + struct timerqueue_node *ptr; + bool leftmost = true; /* Make sure we don't add nodes that are already added */ WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); @@ -36,19 +37,17 @@ bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) while (*p) { parent = *p; ptr = rb_entry(parent, struct timerqueue_node, node); - if (node->expires < ptr->expires) + if (node->expires < ptr->expires) { p = &(*p)->rb_left; - else + } else { p = &(*p)->rb_right; + leftmost = false; + } } rb_link_node(&node->node, parent, p); - rb_insert_color(&node->node, &head->head); + rb_insert_color_cached(&node->node, &head->rb_root, leftmost); - if (!head->next || node->expires < head->next->expires) { - head->next = node; - return true; - } - return false; + return leftmost; } EXPORT_SYMBOL_GPL(timerqueue_add); @@ -65,15 +64,10 @@ bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) { WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); - /* update next pointer */ - if (head->next == node) { - struct rb_node *rbn = rb_next(&node->node); - - head->next = rb_entry_safe(rbn, struct timerqueue_node, node); - } - rb_erase(&node->node, &head->head); + rb_erase_cached(&node->node, &head->rb_root); RB_CLEAR_NODE(&node->node); - return head->next != NULL; + + return !RB_EMPTY_ROOT(&head->rb_root.rb_root); } EXPORT_SYMBOL_GPL(timerqueue_del); |