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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



From: Martin Wilck <mwilck@xxxxxxxx>

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@xxxxxxxx>
---
 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@xxxxxxxxxx
https://listman.redhat.com/mailman/listinfo/dm-devel




[Index of Archives]     [DM Crypt]     [Fedora Desktop]     [ATA RAID]     [Fedora Marketing]     [Fedora Packaging]     [Fedora SELinux]     [Yosemite Discussion]     [KDE Users]     [Fedora Docs]

  Powered by Linux