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
