[dm-devel] [PATCH v4 0/5] multipath: optimizations for large mptable

[dm-devel] [PATCH v4 0/5] multipath: optimizations for large mptable

[mwilck]

From: Martin Wilck <mwilck@suse.com>

We observe that multipath operations take a long time if the multipaths
section in multipath.conf contains a lot of alias settings
(10000+ in our case). This hurts in particular in udev rules, when
multipath -u or multipath -U is invoked, but also for command line
invocations like "multipath -ll".

This series provides a few optimizations for this use case. It speeds
up simple multipath operations in the test case by a factor of 20.

Changes v3->v4:

 02: more compilation fixes for msort.c to make it pass CI
     (only re-posting this patch)

Changes v2->v3, after discussion with Benjamin Marzinski:

 01, 02: added msort.c from glibc and adapted to our needs.
         Numbering changes accordingly.
 03, 04: (was 01, 02): remove pointer comparisons from v2 again, this was a
         dumb idea. Use the stable msort algorithm instead.

Changes wrt v1, after suggestions from Benjamin Marzinski:

 01, 02: Use pointer comparisons to achieve stable sorting with qsort
 02:  Fix return without popping the cleanup handler. The way I fixed this
      leaves the possibility that some memory won't be freed if a thread is
      killed while executing vector_convert(). I think this is acceptible;
      avoiding it would complicate the code, with very small benefit.
 02: Remove unnecessary checks and break loop if alias==NULL is encountered.

Martin Wilck (5):
  libmultipath: add msort.c from glibc
  libmultipath: modifications for msort.c
  libmultipath: merge_mptable(): sort table by wwid
  libmultipath: check_alias_settings(): pre-sort mptable by alias
  multipath: optimize program startup for frequent invocations

 libmultipath/Makefile |   2 +-
 libmultipath/alias.c  |  37 +++++-
 libmultipath/config.c |  15 ++-
 libmultipath/msort.c  | 271 ++++++++++++++++++++++++++++++++++++++++++
 libmultipath/msort.h  |   6 +
 libmultipath/vector.c |   9 ++
 libmultipath/vector.h |   1 +
 multipath/main.c      |  33 ++---
 8 files changed, 352 insertions(+), 22 deletions(-)
 create mode 100644 libmultipath/msort.c
 create mode 100644 libmultipath/msort.h

-- 
2.37.1

--
dm-devel mailing list
dm-devel@redhat.com
https://listman.redhat.com/mailman/listinfo/dm-devel

[dm-devel] [PATCH v4 2/5] libmultipath: modifications for msort.c

[mwilck]

From: Martin Wilck <mwilck@suse.com>

We don't want to fallback to qsort if memory is tight, as libc's
routine does. Other than that, compile error fixes.

Signed-off-by: Martin Wilck <mwilck@suse.com>
---
 libmultipath/Makefile |  2 +-
 libmultipath/msort.c  | 88 ++++++++++++-------------------------------
 libmultipath/msort.h  |  6 +++
 3 files changed, 32 insertions(+), 64 deletions(-)
 create mode 100644 libmultipath/msort.h

diff --git a/libmultipath/Makefile b/libmultipath/Makefile
index fb03200..a70acab 100644
--- a/libmultipath/Makefile
+++ b/libmultipath/Makefile
@@ -64,7 +64,7 @@ OBJS-O := parser.o vector.o devmapper.o \
 	log.o configure.o structs_vec.o sysfs.o \
 	lock.o file.o wwids.o prioritizers/alua_rtpg.o prkey.o \
 	io_err_stat.o dm-generic.o generic.o nvme-lib.o \
-	libsg.o valid.o strbuf.o
+	libsg.o valid.o strbuf.o msort.o
 
 OBJS := $(OBJS-O) $(OBJS-U)
 
diff --git a/libmultipath/msort.c b/libmultipath/msort.c
index cbe9a4a..2963486 100644
--- a/libmultipath/msort.c
+++ b/libmultipath/msort.c
@@ -21,9 +21,11 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
-#include <memcopy.h>
+#include <string.h>
 #include <errno.h>
-#include <atomic.h>
+#include "msort.h"
+
+typedef int(*__compar_d_fn_t)(const void *, const void *, void *);
 
 struct msort_param
 {
@@ -140,13 +142,13 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
 	{
 	  if ((*cmp) (b1, b2, arg) <= 0)
 	    {
-	      tmp = (char *) __mempcpy (tmp, b1, s);
+	      tmp = (char *) mempcpy (tmp, b1, s);
 	      b1 += s;
 	      --n1;
 	    }
 	  else
 	    {
-	      tmp = (char *) __mempcpy (tmp, b2, s);
+	      tmp = (char *) mempcpy (tmp, b2, s);
 	      b2 += s;
 	      --n2;
 	    }
@@ -160,8 +162,8 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
 }
 
 
-void
-__qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
+static void
+msort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
 {
   size_t size = n * s;
   char *tmp = NULL;
@@ -173,60 +175,15 @@ __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
 
   if (size < 1024)
     /* The temporary array is small, so put it on the stack.  */
-    p.t = __alloca (size);
+    p.t = alloca (size);
   else
     {
-      /* We should avoid allocating too much memory since this might
-	 have to be backed up by swap space.  */
-      static long int phys_pages;
-      static int pagesize;
-
-      if (pagesize == 0)
-	{
-	  phys_pages = __sysconf (_SC_PHYS_PAGES);
-
-	  if (phys_pages == -1)
-	    /* Error while determining the memory size.  So let's
-	       assume there is enough memory.  Otherwise the
-	       implementer should provide a complete implementation of
-	       the `sysconf' function.  */
-	    phys_pages = (long int) (~0ul >> 1);
-
-	  /* The following determines that we will never use more than
-	     a quarter of the physical memory.  */
-	  phys_pages /= 4;
-
-	  /* Make sure phys_pages is written to memory.  */
-	  atomic_write_barrier ();
-
-	  pagesize = __sysconf (_SC_PAGESIZE);
-	}
-
-      /* Just a comment here.  We cannot compute
-	   phys_pages * pagesize
-	   and compare the needed amount of memory against this value.
-	   The problem is that some systems might have more physical
-	   memory then can be represented with a `size_t' value (when
-	   measured in bytes.  */
-
-      /* If the memory requirements are too high don't allocate memory.  */
-      if (size / pagesize > (size_t) phys_pages)
-	{
-	  _quicksort (b, n, s, cmp, arg);
-	  return;
-	}
-
       /* It's somewhat large, so malloc it.  */
       int save = errno;
       tmp = malloc (size);
-      __set_errno (save);
+      errno = save;
       if (tmp == NULL)
-	{
-	  /* Couldn't get space, so use the slower algorithm
-	     that doesn't need a temporary array.  */
-	  _quicksort (b, n, s, cmp, arg);
-	  return;
-	}
+	      return;
       p.t = tmp;
     }
 
@@ -281,15 +238,15 @@ __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
   else
     {
       if ((s & (sizeof (uint32_t) - 1)) == 0
-	  && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
+	  && ((unsigned long) b) % __alignof__ (uint32_t) == 0)
 	{
 	  if (s == sizeof (uint32_t))
 	    p.var = 0;
 	  else if (s == sizeof (uint64_t)
-		   && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
+		   && ((unsigned long) b) % __alignof__ (uint64_t) == 0)
 	    p.var = 1;
 	  else if ((s & (sizeof (unsigned long) - 1)) == 0
-		   && ((char *) b - (char *) 0)
+		   && ((unsigned long) b)
 		      % __alignof__ (unsigned long) == 0)
 	    p.var = 2;
 	}
@@ -297,13 +254,18 @@ __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
     }
   free (tmp);
 }
-libc_hidden_def (__qsort_r)
-weak_alias (__qsort_r, qsort_r)
-
 
+/*
+ * glibc apparently doesn't use -Wcast-function-type.
+ * If this is safe for them, it should be for us, too.
+ */
+#pragma GCC diagnostic push
+#if __GNUC__ >= 8
+#pragma GCC diagnostic ignored "-Wcast-function-type"
+#endif
 void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
+msort (void *b, size_t n, size_t s, __compar_fn_t cmp)
 {
-  return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
+	return msort_r (b, n, s, (__compar_d_fn_t)cmp, NULL);
 }
-libc_hidden_def (qsort)
+#pragma GCC diagnostic pop
diff --git a/libmultipath/msort.h b/libmultipath/msort.h
new file mode 100644
index 0000000..caef9b6
--- /dev/null
+++ b/libmultipath/msort.h
@@ -0,0 +1,6 @@
+#ifndef __MSORT_H
+#define __MSORT_H
+typedef int(*__compar_fn_t)(const void *, const void *);
+void msort (void *b, size_t n, size_t s, __compar_fn_t cmp);
+
+#endif
-- 
2.37.1

--
dm-devel mailing list
dm-devel@redhat.com
https://listman.redhat.com/mailman/listinfo/dm-devel

Re: [dm-devel] [PATCH v4 0/5] multipath: optimizations for large mptable

[Benjamin Marzinski]

On Fri, Aug 26, 2022 at 08:05:51PM +0200, mwilck@suse.com wrote:
> From: Martin Wilck <mwilck@suse.com>

For the set:
Reviewed-by: Benjamin Marzinski <bmarzins@redhat.com>

> 
> We observe that multipath operations take a long time if the multipaths
> section in multipath.conf contains a lot of alias settings
> (10000+ in our case). This hurts in particular in udev rules, when
> multipath -u or multipath -U is invoked, but also for command line
> invocations like "multipath -ll".
> 
> This series provides a few optimizations for this use case. It speeds
> up simple multipath operations in the test case by a factor of 20.
> 
> Changes v3->v4:
> 
>  02: more compilation fixes for msort.c to make it pass CI
>      (only re-posting this patch)
> 
> Changes v2->v3, after discussion with Benjamin Marzinski:
> 
>  01, 02: added msort.c from glibc and adapted to our needs.
>          Numbering changes accordingly.
>  03, 04: (was 01, 02): remove pointer comparisons from v2 again, this was a
>          dumb idea. Use the stable msort algorithm instead.
> 
> Changes wrt v1, after suggestions from Benjamin Marzinski:
> 
>  01, 02: Use pointer comparisons to achieve stable sorting with qsort
>  02:  Fix return without popping the cleanup handler. The way I fixed this
>       leaves the possibility that some memory won't be freed if a thread is
>       killed while executing vector_convert(). I think this is acceptible;
>       avoiding it would complicate the code, with very small benefit.
>  02: Remove unnecessary checks and break loop if alias==NULL is encountered.
> 
> Martin Wilck (5):
>   libmultipath: add msort.c from glibc
>   libmultipath: modifications for msort.c
>   libmultipath: merge_mptable(): sort table by wwid
>   libmultipath: check_alias_settings(): pre-sort mptable by alias
>   multipath: optimize program startup for frequent invocations
> 
>  libmultipath/Makefile |   2 +-
>  libmultipath/alias.c  |  37 +++++-
>  libmultipath/config.c |  15 ++-
>  libmultipath/msort.c  | 271 ++++++++++++++++++++++++++++++++++++++++++
>  libmultipath/msort.h  |   6 +
>  libmultipath/vector.c |   9 ++
>  libmultipath/vector.h |   1 +
>  multipath/main.c      |  33 ++---
>  8 files changed, 352 insertions(+), 22 deletions(-)
>  create mode 100644 libmultipath/msort.c
>  create mode 100644 libmultipath/msort.h
> 
> -- 
> 2.37.1
--
dm-devel mailing list
dm-devel@redhat.com
https://listman.redhat.com/mailman/listinfo/dm-devel