Hi Rasmus,
On Mon, 17 Jun 2019 23:14:52 +0200
Rasmus Villemoes <li...@rasmusvillemoes.dk> wrote:
> Our list_sort() utility has always supported a context argument that
> is passed through to the comparison routine. Now there's a use case
> for the similar thing for sort().
>
> This implements sort_r by simply extending the existing sort function
> in the obvious way. To avoid code duplication, we want to implement
> sort() in terms of sort_r(). The naive way to do that is
>
> static int cmp_wrapper(const void *a, const void *b, const void *ctx)
> {
> int (*real_cmp)(const void*, const void*) = ctx;
> return real_cmp(a, b);
> }
>
> sort(..., cmp) { sort_r(..., cmp_wrapper, cmp) }
>
> but this would do two indirect calls for each comparison. Instead, do
> as is done for the default swap functions - that only adds a cost of a
> single easily predicted branch to each comparison call.
>
> Aside from introducing support for the context argument, this also
> serves as preparation for patches that will eliminate the indirect
> comparison calls in common cases.
>
> Requested-by: Boris Brezillon <boris.brezil...@collabora.com>
> Signed-off-by: Rasmus Villemoes <li...@rasmusvillemoes.dk>
> ---
> Hi Boris
>
> Sorry, completely dropped the ball on this one.
No problem.
> Here's a formal patch
> with change log. I won't have time to do the other changes I mention
> this side of the merge window, so it's perfectly fine if you carry
> this as part of your series.
Not sure my series will make it for the next release, but I'll let you
know either way.
> It's only been tested by booting a kernel
> in qemu with CONFIG_TEST_SORT=y, and nothing exploded.
Thanks for the patch.
Boris
>
> include/linux/sort.h | 5 +++++
> lib/sort.c | 34 ++++++++++++++++++++++++++++------
> 2 files changed, 33 insertions(+), 6 deletions(-)
>
> diff --git a/include/linux/sort.h b/include/linux/sort.h
> index 2b99a5dd073d..61b96d0ebc44 100644
> --- a/include/linux/sort.h
> +++ b/include/linux/sort.h
> @@ -4,6 +4,11 @@
>
> #include <linux/types.h>
>
> +void sort_r(void *base, size_t num, size_t size,
> + int (*cmp)(const void *, const void *, const void *),
> + void (*swap)(void *, void *, int),
> + const void *priv);
> +
> void sort(void *base, size_t num, size_t size,
> int (*cmp)(const void *, const void *),
> void (*swap)(void *, void *, int));
> diff --git a/lib/sort.c b/lib/sort.c
> index cf408aec3733..36fcc2040be5 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);
