[dm-devel] [PATCH v2 0/3] multipath: optimizations for large mptable

[dm-devel] [PATCH v2 0/3] 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 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 (3):
  libmultipath: merge_mptable(): sort table by wwid
  libmultipath: check_alias_settings(): pre-sort mptable by alias
  multipath: optimize program startup for frequent invocations

 libmultipath/alias.c  | 44 ++++++++++++++++++++++++++++++++++++++++---
 libmultipath/config.c | 24 +++++++++++++++++++++--
 libmultipath/vector.c |  8 ++++++++
 libmultipath/vector.h |  1 +
 multipath/main.c      | 33 ++++++++++++++++----------------
 5 files changed, 89 insertions(+), 21 deletions(-)

-- 
2.37.1

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

[dm-devel] [PATCH v2 1/3] libmultipath: merge_mptable(): sort table by wwid

[mwilck]

From: Martin Wilck <mwilck@suse.com>

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.

Signed-off-by: Martin Wilck <mwilck@suse.com>
---
 libmultipath/config.c | 24 ++++++++++++++++++++++--
 libmultipath/vector.c |  8 ++++++++
 libmultipath/vector.h |  1 +
 3 files changed, 31 insertions(+), 2 deletions(-)

diff --git a/libmultipath/config.c b/libmultipath/config.c
index ab8b26e..18d7159 100644
--- a/libmultipath/config.c
+++ b/libmultipath/config.c
@@ -520,6 +520,23 @@ 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;
+	int cmp = strcmp(wwid1, wwid2);
+
+	if (cmp)
+		return cmp;
+	/*
+	 * qsort by itself is not a stable sorting algorithm: it may permute
+	 * elements with equal keys, which we must avoid because of the way
+	 * merge_mpe() works.  Because the function arguments are offsets into
+	 * the array (struct mpentry **), we can simply compare the pointers.
+	 */
+	return p1 < p2 ? -1 : p1 > p2 ? 1 : 0;
+}
+
 void merge_mptable(vector mptable)
 {
 	struct mpentry *mp1, *mp2;
@@ -533,10 +550,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..0befe71 100644
--- a/libmultipath/vector.c
+++ b/libmultipath/vector.c
@@ -208,3 +208,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 qsort((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
-- 
2.37.1

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

[dm-devel] [PATCH v2 2/3] libmultipath: check_alias_settings(): pre-sort mptable by alias

[mwilck]

From: Martin Wilck <mwilck@suse.com>

add_binding() contains an optimization; it assumes that the list of
bindings is alphabetically sorted by alias, and tries to maintain
this order.

But conf->mptable is sorted by wwid. Therefore check_alias_settings() may take
a long time if the mptable is large.

Create a copy of the mptable, sorted by alias, and use it for add_bindings().
This speeds up check_alias_settings by roughly a factor of 10 (0.1s vs. 1s)
for my test setup with 10000 entries in the mptable.

Signed-off-by: Martin Wilck <mwilck@suse.com>
---
 libmultipath/alias.c | 44 +++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 41 insertions(+), 3 deletions(-)

diff --git a/libmultipath/alias.c b/libmultipath/alias.c
index 548a118..284092b 100644
--- a/libmultipath/alias.c
+++ b/libmultipath/alias.c
@@ -672,6 +672,31 @@ static void cleanup_fclose(void *p)
 	fclose(p);
 }
 
+static int alias_compar(const void *p1, const void *p2)
+{
+	const char *alias1 = (*(struct mpentry * const *)p1)->alias;
+	const char *alias2 = (*(struct mpentry * const *)p2)->alias;
+	int cmp;
+
+	if (alias1 && alias2)
+		cmp = strcmp(alias1, alias2);
+	else
+		/* Move NULL alias to the end */
+		cmp = alias1 ? -1 : alias2 ? 1 : 0;
+
+	if (cmp)
+		return cmp;
+
+	/* Ensure stable sort, see wwid_compar() in config.c */
+	return  p1 < p2 ? -1 : p1 > p2 ? 1 : 0;
+}
+
+static void cleanup_vector_free(void *arg)
+{
+	if  (arg)
+		vector_free((vector)arg);
+}
+
 /*
  * check_alias_settings(): test for inconsistent alias configuration
  *
@@ -693,12 +718,24 @@ int check_alias_settings(const struct config *conf)
 	int can_write;
 	int rc = 0, i, fd;
 	Bindings bindings = {.allocated = 0, };
+	vector mptable = NULL;
 	struct mpentry *mpe;
 
+	mptable = vector_convert(NULL, conf->mptable, struct mpentry *, identity);
+	if (!mptable)
+		return -1;
+
 	pthread_cleanup_push_cast(free_bindings, &bindings);
-	vector_foreach_slot(conf->mptable, mpe, i) {
-		if (!mpe->wwid || !mpe->alias)
-			continue;
+	pthread_cleanup_push(cleanup_vector_free, mptable);
+
+	vector_sort(mptable, alias_compar);
+	vector_foreach_slot(mptable, mpe, i) {
+		if (!mpe->alias)
+			/*
+			 * alias_compar() sorts NULL alias at the end,
+			 * so we can stop if we encounter this.
+			 */
+			break;
 		if (add_binding(&bindings, mpe->alias, mpe->wwid) ==
 		    BINDING_CONFLICT) {
 			condlog(0, "ERROR: alias \"%s\" bound to multiple wwids in multipath.conf, "
@@ -710,6 +747,7 @@ int check_alias_settings(const struct config *conf)
 	}
 	/* This clears the bindings */
 	pthread_cleanup_pop(1);
+	pthread_cleanup_pop(1);
 
 	pthread_cleanup_push_cast(free_bindings, &bindings);
 	fd = open_file(conf->bindings_file, &can_write, BINDINGS_FILE_HEADER);
-- 
2.37.1

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

[dm-devel] [PATCH v2 3/3] multipath: optimize program startup for frequent invocations

[mwilck]

From: Martin Wilck <mwilck@suse.com>

Neither "multipath -u" nor "multipath -U" need initialization of the
prioritizers, checkers, and foreign libraries. Also, these commands
need not fail if the bindings file is inconsistent. Move these
possibly slow initialization steps after these special command
invocations.

Signed-off-by: Martin Wilck <mwilck@suse.com>
Reviewed-by: Benjamin Marzinski <bmarzins@redhat.com>
---
 multipath/main.c | 33 +++++++++++++++++----------------
 1 file changed, 17 insertions(+), 16 deletions(-)

diff --git a/multipath/main.c b/multipath/main.c
index 034dd2f..8e5154a 100644
--- a/multipath/main.c
+++ b/multipath/main.c
@@ -957,11 +957,6 @@ main (int argc, char *argv[])
 		exit(RTVL_FAIL);
 	}
 
-	if (check_alias_settings(conf)) {
-		fprintf(stderr, "fatal configuration error, aborting");
-		exit(RTVL_FAIL);
-	}
-
 	if (optind < argc) {
 		dev = calloc(1, FILE_NAME_SIZE);
 
@@ -988,20 +983,9 @@ main (int argc, char *argv[])
 
 	libmp_udev_set_sync_support(1);
 
-	if (init_checkers()) {
-		condlog(0, "failed to initialize checkers");
-		goto out;
-	}
-	if (init_prio()) {
-		condlog(0, "failed to initialize prioritizers");
-		goto out;
-	}
-
 	if ((cmd == CMD_LIST_SHORT || cmd == CMD_LIST_LONG) && enable_foreign)
 		conf->enable_foreign = strdup("");
 
-	/* Failing here is non-fatal */
-	init_foreign(conf->enable_foreign);
 	if (cmd == CMD_USABLE_PATHS) {
 		r = check_usable_paths(conf, dev, dev_type) ?
 			RTVL_FAIL : RTVL_OK;
@@ -1036,6 +1020,23 @@ main (int argc, char *argv[])
 		break;
 	}
 
+	if (check_alias_settings(conf)) {
+		fprintf(stderr, "fatal configuration error, aborting");
+		exit(RTVL_FAIL);
+	}
+
+	if (init_checkers()) {
+		condlog(0, "failed to initialize checkers");
+		goto out;
+	}
+	if (init_prio()) {
+		condlog(0, "failed to initialize prioritizers");
+		goto out;
+	}
+
+	/* Failing here is non-fatal */
+	init_foreign(conf->enable_foreign);
+
 	if (cmd == CMD_RESET_WWIDS) {
 		struct multipath * mpp;
 		int i;
-- 
2.37.1

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