LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] lib/sort: Add the sort_r() variant
@ 2019-05-22 11:25 Boris Brezillon
  2019-05-22 18:33 ` Andrew Morton
  2019-05-23 20:04 ` Rasmus Villemoes
  0 siblings, 2 replies; 8+ messages in thread
From: Boris Brezillon @ 2019-05-22 11:25 UTC (permalink / raw)
  To: linux-kernel
  Cc: George Spelvin, Rasmus Villemoes, Andy Shevchenko, Andrew Morton,
	Andrey Abramov, kernel, Boris Brezillon

Some users might need extra context to compare 2 elements. This patch
adds the sort_r() which is similar to the qsort_r() variant of qsort().

Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
---
Hello,

A few more details about this patch.

Even though I post it as a standalone patch, I do intend to use it in
a real driver (v4l2 driver), just didn't want to have it burried in a
huge patch series.

Note that sort() and sort_r() are now implemented as wrappers around
do_sort() so that most of the code can be shared. I initially went for
a solution that implemented sort() as a wrapper around sort_r() (which
basically contained the do_sort() logic without the cmp_func arg)
but realized this was adding one extra indirect call (the compare func
wrapper), which I know are being chased.

There's another option, but I'm pretty sure other people already
considered it and thought it was not a good idea as it would make
the code size grow: move the code to sort.h as inline funcs/macros so
that the compiler can optimize things out and replace the indirect
cmp_func() calls by direct ones. I just tried it, and it makes my .o
file grow by 576 bytes, given that we currently have 122 users of
this function, that makes the kernel code grow by ~70k (that's kind
of a max estimate since not all users will be compiled in).

Please let me know if you think we shouldn't expose the sort_r() func
and I'll just implement a private version in my driver.

Regards,

Boris
---
 include/linux/sort.h |  5 +++
 lib/sort.c           | 85 ++++++++++++++++++++++++++++++++------------
 2 files changed, 67 insertions(+), 23 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 50855ea8c262..5db5602e52ee 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -167,27 +167,21 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)
 	return i / 2;
 }
 
-/**
- * sort - 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
- *
- * 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
- * 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))
+static int do_cmp(int (*cmp_func_r)(const void *, const void *, const void *),
+		  int (*cmp_func)(const void *, const void *),
+		  const void *a, const void *b, const void *priv)
+{
+	if (cmp_func)
+		return cmp_func(a, b);
+
+	return cmp_func_r(a, b, priv);
+}
+
+static void do_sort(void *base, size_t num, size_t size,
+		    int (*cmp_func_r)(const void *, const void *, const void *),
+		    int (*cmp_func)(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;
@@ -235,12 +229,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(cmp_func_r, cmp_func, base + c, base + d, 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(cmp_func_r, cmp_func, base + a, base + b, priv) >= 0)
 			b = parent(b, lsbit, size);
 		c = b;			/* Where "a" belongs */
 		while (b != a) {	/* Shift it into place */
@@ -249,4 +243,49 @@ void sort(void *base, size_t num, size_t size,
 		}
 	}
 }
+
+/**
+ * sort - 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
+ *
+ * This function does a heapsort on the given array. You may provide a
+ * swap_func function optimized to your element type.
+ *
+ * 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
+ * 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))
+{
+	return do_sort(base, num, size, NULL, cmp_func, swap_func, NULL);
+}
 EXPORT_SYMBOL(sort);
+
+/**
+ * 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: private data passed to the compare function
+ *
+ * Same as sort() except it takes an extra private argument and pass it back
+ * to the compare function. Particularly useful when some extra context is
+ * needed to do the comparison.
+ */
+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)
+{
+	return do_sort(base, num, size, cmp_func, NULL, swap_func, priv);
+}
+EXPORT_SYMBOL(sort_r);
-- 
2.20.1


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/sort: Add the sort_r() variant
  2019-05-22 11:25 [PATCH] lib/sort: Add the sort_r() variant Boris Brezillon
@ 2019-05-22 18:33 ` Andrew Morton
  2019-05-23  8:14   ` Boris Brezillon
  2019-05-23 20:04 ` Rasmus Villemoes
  1 sibling, 1 reply; 8+ messages in thread
From: Andrew Morton @ 2019-05-22 18:33 UTC (permalink / raw)
  To: Boris Brezillon
  Cc: linux-kernel, George Spelvin, Rasmus Villemoes, Andy Shevchenko,
	Andrey Abramov, kernel

On Wed, 22 May 2019 13:25:50 +0200 Boris Brezillon <boris.brezillon@collabora.com> wrote:

> Some users might need extra context to compare 2 elements. This patch
> adds the sort_r() which is similar to the qsort_r() variant of qsort().
> 
> Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
> ---
> Hello,
> 
> A few more details about this patch.
> 
> Even though I post it as a standalone patch, I do intend to use it in
> a real driver (v4l2 driver), just didn't want to have it burried in a
> huge patch series.
> 
> Note that sort() and sort_r() are now implemented as wrappers around
> do_sort() so that most of the code can be shared. I initially went for
> a solution that implemented sort() as a wrapper around sort_r() (which
> basically contained the do_sort() logic without the cmp_func arg)
> but realized this was adding one extra indirect call (the compare func
> wrapper), which I know are being chased.

Please move the above text into the changelog.  It's probably useful
and we can afford the disk space ;)

> There's another option, but I'm pretty sure other people already
> considered it and thought it was not a good idea as it would make
> the code size grow: move the code to sort.h as inline funcs/macros so
> that the compiler can optimize things out and replace the indirect
> cmp_func() calls by direct ones. I just tried it, and it makes my .o
> file grow by 576 bytes, given that we currently have 122 users of
> this function, that makes the kernel code grow by ~70k (that's kind
> of a max estimate since not all users will be compiled in).

eep, let's not do that.

> --- a/include/linux/sort.h
> +++ b/include/linux/sort.h

Patch otherwise looks OK.  Please include it with the patch series
which uses it.  Feel free to add

Acked-by: Andrew Morton <akpm@linux-foundation.org>

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/sort: Add the sort_r() variant
  2019-05-22 18:33 ` Andrew Morton
@ 2019-05-23  8:14   ` Boris Brezillon
  0 siblings, 0 replies; 8+ messages in thread
From: Boris Brezillon @ 2019-05-23  8:14 UTC (permalink / raw)
  To: Andrew Morton
  Cc: linux-kernel, George Spelvin, Rasmus Villemoes, Andy Shevchenko,
	Andrey Abramov, kernel

Hi Andrew,

On Wed, 22 May 2019 11:33:15 -0700
Andrew Morton <akpm@linux-foundation.org> wrote:

> On Wed, 22 May 2019 13:25:50 +0200 Boris Brezillon <boris.brezillon@collabora.com> wrote:
> 
> > Some users might need extra context to compare 2 elements. This patch
> > adds the sort_r() which is similar to the qsort_r() variant of qsort().
> > 
> > Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
> > ---
> > Hello,
> > 
> > A few more details about this patch.
> > 
> > Even though I post it as a standalone patch, I do intend to use it in
> > a real driver (v4l2 driver), just didn't want to have it burried in a
> > huge patch series.
> > 
> > Note that sort() and sort_r() are now implemented as wrappers around
> > do_sort() so that most of the code can be shared. I initially went for
> > a solution that implemented sort() as a wrapper around sort_r() (which
> > basically contained the do_sort() logic without the cmp_func arg)
> > but realized this was adding one extra indirect call (the compare func
> > wrapper), which I know are being chased.  
> 
> Please move the above text into the changelog.  It's probably useful
> and we can afford the disk space ;)

Will do.

> 
> > There's another option, but I'm pretty sure other people already
> > considered it and thought it was not a good idea as it would make
> > the code size grow: move the code to sort.h as inline funcs/macros so
> > that the compiler can optimize things out and replace the indirect
> > cmp_func() calls by direct ones. I just tried it, and it makes my .o
> > file grow by 576 bytes, given that we currently have 122 users of
> > this function, that makes the kernel code grow by ~70k (that's kind
> > of a max estimate since not all users will be compiled in).  
> 
> eep, let's not do that.
> 
> > --- a/include/linux/sort.h
> > +++ b/include/linux/sort.h  
> 
> Patch otherwise looks OK.  Please include it with the patch series
> which uses it.  Feel free to add
> 
> Acked-by: Andrew Morton <akpm@linux-foundation.org>

Thanks for your review.

Boris

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/sort: Add the sort_r() variant
  2019-05-22 11:25 [PATCH] lib/sort: Add the sort_r() variant Boris Brezillon
  2019-05-22 18:33 ` Andrew Morton
@ 2019-05-23 20:04 ` Rasmus Villemoes
  2019-05-24 15:09   ` Boris Brezillon
  1 sibling, 1 reply; 8+ messages in thread
From: Rasmus Villemoes @ 2019-05-23 20:04 UTC (permalink / raw)
  To: Boris Brezillon, linux-kernel
  Cc: George Spelvin, Andy Shevchenko, Andrew Morton, Andrey Abramov, kernel

On 22/05/2019 13.25, Boris Brezillon wrote:
> Some users might need extra context to compare 2 elements. This patch
> adds the sort_r() which is similar to the qsort_r() variant of qsort().
> 
> Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
> ---
> Hello,
> 
> A few more details about this patch.
> 
> Even though I post it as a standalone patch, I do intend to use it in
> a real driver (v4l2 driver), just didn't want to have it burried in a
> huge patch series.
> 
> Note that sort() and sort_r() are now implemented as wrappers around
> do_sort() so that most of the code can be shared. I initially went for
> a solution that implemented sort() as a wrapper around sort_r() (which
> basically contained the do_sort() logic without the cmp_func arg)
> but realized this was adding one extra indirect call (the compare func
> wrapper), which I know are being chased.

Hm, I don't like the "pass one or the other, but not both". Yes, the
direct way to implement sort() in terms of sort_r would be

cmp_wrapper(void *a, void *b, void *priv)
{ return ((cmp_func_t)priv)(a, b); }

void sort(...) { sort_r(...., cmp_wrapper, cmp_func); }

but it's easy enough to get rid of that extra indirect call similar to
how the swap functions are done: pass a sentinel value, and use a single
(highly predictable) branch to check whether we have an old-style cmp
function.

[Are there actually any architectures where passing a third argument to
a function just expecting two would not Just Work? I.e., could one
simply cast a new-style comparison function to an old-style and pass
NULL as priv? Well, we'd better not go down that road.]

So I propose this somewhat simpler (at least in terms of diffstat)
patch, which also fits nicely with some optimizations I plan on doing to
eliminate "trivial" comparison functions (those that just do a single
integer comparison of some field inside the structs). Sorry if it's
whitespace-damaged. I also wonder if one should make the priv argument
void* instead of const void*, to help avoid mixing up the elements with
the context, but the function should be pure, so I'm inclined to stick
with the three const void* args.

 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 50855ea8c262..8737d47d87bf 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -141,6 +141,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)1L)
+
+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.
@@ -168,12 +180,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
@@ -185,9 +198,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;
@@ -235,12 +249,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 */
@@ -249,4 +263,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);


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/sort: Add the sort_r() variant
  2019-05-23 20:04 ` Rasmus Villemoes
@ 2019-05-24 15:09   ` Boris Brezillon
  2019-06-17 13:51     ` Boris Brezillon
  0 siblings, 1 reply; 8+ messages in thread
From: Boris Brezillon @ 2019-05-24 15:09 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: linux-kernel, George Spelvin, Andy Shevchenko, Andrew Morton,
	Andrey Abramov, kernel

Hello Rasmus,

On Thu, 23 May 2019 22:04:35 +0200
Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:

> On 22/05/2019 13.25, Boris Brezillon wrote:
> > Some users might need extra context to compare 2 elements. This patch
> > adds the sort_r() which is similar to the qsort_r() variant of qsort().
> > 
> > Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
> > ---
> > Hello,
> > 
> > A few more details about this patch.
> > 
> > Even though I post it as a standalone patch, I do intend to use it in
> > a real driver (v4l2 driver), just didn't want to have it burried in a
> > huge patch series.
> > 
> > Note that sort() and sort_r() are now implemented as wrappers around
> > do_sort() so that most of the code can be shared. I initially went for
> > a solution that implemented sort() as a wrapper around sort_r() (which
> > basically contained the do_sort() logic without the cmp_func arg)
> > but realized this was adding one extra indirect call (the compare func
> > wrapper), which I know are being chased.  
> 
> Hm, I don't like the "pass one or the other, but not both". Yes, the
> direct way to implement sort() in terms of sort_r would be
> 
> cmp_wrapper(void *a, void *b, void *priv)
> { return ((cmp_func_t)priv)(a, b); }
> 
> void sort(...) { sort_r(...., cmp_wrapper, cmp_func); }
> 
> but it's easy enough to get rid of that extra indirect call similar to
> how the swap functions are done: pass a sentinel value, and use a single
> (highly predictable) branch to check whether we have an old-style cmp
> function.
> 
> [Are there actually any architectures where passing a third argument to
> a function just expecting two would not Just Work? I.e., could one
> simply cast a new-style comparison function to an old-style and pass
> NULL as priv? Well, we'd better not go down that road.]
> 
> So I propose this somewhat simpler (at least in terms of diffstat)
> patch, which also fits nicely with some optimizations I plan on doing to
> eliminate "trivial" comparison functions (those that just do a single
> integer comparison of some field inside the structs).

Works for me. If you plan to send changes on top (or before) would you
mind making this patch part of the series so that we don't have to deal
with merge conflicts.

Thanks,

Boris

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/sort: Add the sort_r() variant
  2019-05-24 15:09   ` Boris Brezillon
@ 2019-06-17 13:51     ` Boris Brezillon
  2019-06-17 21:14       ` [PATCH] lib/sort.c: implement sort() variant taking context argument Rasmus Villemoes
  0 siblings, 1 reply; 8+ messages in thread
From: Boris Brezillon @ 2019-06-17 13:51 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: linux-kernel, George Spelvin, Andy Shevchenko, Andrew Morton,
	Andrey Abramov, kernel

Hello Rasmus,

On Fri, 24 May 2019 17:09:37 +0200
Boris Brezillon <boris.brezillon@collabora.com> wrote:

> Hello Rasmus,
> 
> On Thu, 23 May 2019 22:04:35 +0200
> Rasmus Villemoes <linux@rasmusvillemoes.dk> wrote:
> 
> > On 22/05/2019 13.25, Boris Brezillon wrote:  
> > > Some users might need extra context to compare 2 elements. This patch
> > > adds the sort_r() which is similar to the qsort_r() variant of qsort().
> > > 
> > > Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
> > > ---
> > > Hello,
> > > 
> > > A few more details about this patch.
> > > 
> > > Even though I post it as a standalone patch, I do intend to use it in
> > > a real driver (v4l2 driver), just didn't want to have it burried in a
> > > huge patch series.
> > > 
> > > Note that sort() and sort_r() are now implemented as wrappers around
> > > do_sort() so that most of the code can be shared. I initially went for
> > > a solution that implemented sort() as a wrapper around sort_r() (which
> > > basically contained the do_sort() logic without the cmp_func arg)
> > > but realized this was adding one extra indirect call (the compare func
> > > wrapper), which I know are being chased.    
> > 
> > Hm, I don't like the "pass one or the other, but not both". Yes, the
> > direct way to implement sort() in terms of sort_r would be
> > 
> > cmp_wrapper(void *a, void *b, void *priv)
> > { return ((cmp_func_t)priv)(a, b); }
> > 
> > void sort(...) { sort_r(...., cmp_wrapper, cmp_func); }
> > 
> > but it's easy enough to get rid of that extra indirect call similar to
> > how the swap functions are done: pass a sentinel value, and use a single
> > (highly predictable) branch to check whether we have an old-style cmp
> > function.
> > 
> > [Are there actually any architectures where passing a third argument to
> > a function just expecting two would not Just Work? I.e., could one
> > simply cast a new-style comparison function to an old-style and pass
> > NULL as priv? Well, we'd better not go down that road.]
> > 
> > So I propose this somewhat simpler (at least in terms of diffstat)
> > patch, which also fits nicely with some optimizations I plan on doing to
> > eliminate "trivial" comparison functions (those that just do a single
> > integer comparison of some field inside the structs).  
> 
> Works for me. If you plan to send changes on top (or before) would you
> mind making this patch part of the series so that we don't have to deal
> with merge conflicts.

Gentle ping. How should I proceed with that patch? Do you plan to send
(or have already sent) the changes you were mentioning above?

Regards,

Boris

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [PATCH] lib/sort.c: implement sort() variant taking context argument
  2019-06-17 13:51     ` Boris Brezillon
@ 2019-06-17 21:14       ` Rasmus Villemoes
  2019-06-18  8:40         ` Boris Brezillon
  0 siblings, 1 reply; 8+ messages in thread
From: Rasmus Villemoes @ 2019-06-17 21:14 UTC (permalink / raw)
  To: Boris Brezillon, Andrew Morton, Rasmus Villemoes, George Spelvin,
	Andrey Abramov, Andy Shevchenko, Randy Dunlap
  Cc: kernel, linux-kernel

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.brezillon@collabora.com>
Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
Hi Boris

Sorry, completely dropped the ball on this one. 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. It's only been tested by booting a kernel
in qemu with CONFIG_TEST_SORT=y, and nothing exploded.

 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);
-- 
2.20.1


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/sort.c: implement sort() variant taking context argument
  2019-06-17 21:14       ` [PATCH] lib/sort.c: implement sort() variant taking context argument Rasmus Villemoes
@ 2019-06-18  8:40         ` Boris Brezillon
  0 siblings, 0 replies; 8+ messages in thread
From: Boris Brezillon @ 2019-06-18  8:40 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Andrew Morton, George Spelvin, Andrey Abramov, Andy Shevchenko,
	Randy Dunlap, kernel, linux-kernel

Hi Rasmus,

On Mon, 17 Jun 2019 23:14:52 +0200
Rasmus Villemoes <linux@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.brezillon@collabora.com>
> Signed-off-by: Rasmus Villemoes <linux@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);


^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2019-06-18  8:40 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-05-22 11:25 [PATCH] lib/sort: Add the sort_r() variant Boris Brezillon
2019-05-22 18:33 ` Andrew Morton
2019-05-23  8:14   ` Boris Brezillon
2019-05-23 20:04 ` Rasmus Villemoes
2019-05-24 15:09   ` Boris Brezillon
2019-06-17 13:51     ` Boris Brezillon
2019-06-17 21:14       ` [PATCH] lib/sort.c: implement sort() variant taking context argument Rasmus Villemoes
2019-06-18  8:40         ` Boris Brezillon

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).