[v3,3/5] libmultipath: merge_mptable(): sort table by wwid

Commit Message

Martin Wilck Aug. 26, 2022, 4:22 p.m. UTC

From: Martin Wilck <[e-mail]>

If the mptable is very large (for example, in a configuration with
lots of maps assigned individual aliases), merge_mptable may get
very slow because it needs to make O(n^2) string comparisons (with
n being the number of mptable entries). WWID strings often differ
only in the last few bytes, causing a lot of CPU time spent in
strcmp().

merge_mptable is executed whenever multipath or multipathd is started, that
is, also for "multipath -u" and "multipath -U" invocations from udev rules.
Optimize it by sorting the mptable before merging. This way we don't need
to iterate towards the end of the vector searching for duplicates.

Because of the way merge_mpe() works, we must make sure not to change
the order of entries with the same WWID. In other words, a stable sort
algorithm is required, which isn't the case for qsort(3) in general.
Therefore we explicitly use the msort() routine from glibc, which is a
stable merge sort algorithm, without fallback to quicksort.

Signed-off-by: Martin Wilck <[e-mail]>
---
 libmultipath/config.c | 15 +++++++++++++--
 libmultipath/vector.c |  9 +++++++++
 libmultipath/vector.h |  1 +
 3 files changed, 23 insertions(+), 2 deletions(-)

Patch

diff --git a/libmultipath/config.c b/libmultipath/config.c
index ab8b26e..a2c79a4 100644
--- a/libmultipath/config.c
+++ b/libmultipath/config.c
@@ -520,6 +520,14 @@  merge_mpe(struct mpentry *dst, struct mpentry *src)
 	merge_num(mode);
 }
 
+static int wwid_compar(const void *p1, const void *p2)
+{
+	const char *wwid1 = (*(struct mpentry * const *)p1)->wwid;
+	const char *wwid2 = (*(struct mpentry * const *)p2)->wwid;
+
+	return strcmp(wwid1, wwid2);
+}
+
 void merge_mptable(vector mptable)
 {
 	struct mpentry *mp1, *mp2;
@@ -533,10 +541,13 @@  void merge_mptable(vector mptable)
 			free_mpe(mp1);
 			continue;
 		}
+	}
+	vector_sort(mptable, wwid_compar);
+	vector_foreach_slot(mptable, mp1, i) {
 		j = i + 1;
 		vector_foreach_slot_after(mptable, mp2, j) {
-			if (!mp2->wwid || strcmp(mp1->wwid, mp2->wwid))
-				continue;
+			if (strcmp(mp1->wwid, mp2->wwid))
+				break;
 			condlog(1, "%s: duplicate multipath config section for %s",
 				__func__, mp1->wwid);
 			merge_mpe(mp2, mp1);
diff --git a/libmultipath/vector.c b/libmultipath/vector.c
index e2d1ec9..df59db5 100644
--- a/libmultipath/vector.c
+++ b/libmultipath/vector.c
@@ -21,6 +21,7 @@ 
 
 #include <stdlib.h>
 #include "vector.h"
+#include "msort.h"
 
 /*
  * Initialize vector struct.
@@ -208,3 +209,11 @@  int vector_find_or_add_slot(vector v, void *value)
 	vector_set_slot(v, value);
 	return VECTOR_SIZE(v) - 1;
 }
+
+void vector_sort(vector v, int (*compar)(const void *, const void *))
+{
+	if (!v || !v->slot || !v->allocated)
+		return;
+	return msort((void *)v->slot, v->allocated, sizeof(void *), compar);
+
+}
diff --git a/libmultipath/vector.h b/libmultipath/vector.h
index 2862dc2..c0b09cb 100644
--- a/libmultipath/vector.h
+++ b/libmultipath/vector.h
@@ -89,4 +89,5 @@  extern void vector_repack(vector v);
 extern void vector_dump(vector v);
 extern void dump_strvec(vector strvec);
 extern int vector_move_up(vector v, int src, int dest);
+void vector_sort(vector v, int (*compar)(const void *, const void *));
 #endif