lib/sort: Add the sort_r() variant
diff mbox series

Message ID 20190522112550.31814-1-boris.brezillon@collabora.com
State New
Headers show
Series
  • lib/sort: Add the sort_r() variant
Related show

Commit Message

Boris Brezillon May 22, 2019, 11:25 a.m. UTC
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(-)

Comments

Andrew Morton May 22, 2019, 6:33 p.m. UTC | #1
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>
Boris Brezillon May 23, 2019, 8:14 a.m. UTC | #2
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
Rasmus Villemoes May 23, 2019, 8:04 p.m. UTC | #3
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);
Boris Brezillon May 24, 2019, 3:09 p.m. UTC | #4
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
Boris Brezillon June 17, 2019, 1:51 p.m. UTC | #5
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

Patch
diff mbox series

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