On Thu, Aug 18, 2022 at 11:06:28PM +0200, mwilck@xxxxxxxx wrote:
> 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 | 15 +++++++++++++--
> libmultipath/vector.c | 8 ++++++++
> libmultipath/vector.h | 1 +
> 3 files changed, 22 insertions(+), 2 deletions(-)
>
> 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);
The way merge_mpe() works, values are only copied from mp1's variables
if the corresponding variable is unset in mp2. This requires the
original order of mp1 and mp2 to be unchanged by the sorting algorithm,
but according to the qsort() man page "If two members compare as equal,
their order in the sorted array is undefined."
One quick and dirty way we could fix this is to add a variable to struct
mptable called config_idx, which is its index in the config file. If
the wwids are equal, you compare that.
Something like (only compile tested):
------------
diff --git a/libmultipath/config.c b/libmultipath/config.c
index a2c79a48..a8e2620b 100644
--- a/libmultipath/config.c
+++ b/libmultipath/config.c
@@ -522,10 +522,15 @@ merge_mpe(struct mpentry *dst, struct mpentry *src)
static int wwid_compar(const void *p1, const void *p2)
{
+ int r;
const char *wwid1 = (*(struct mpentry * const *)p1)->wwid;
const char *wwid2 = (*(struct mpentry * const *)p2)->wwid;
+ int idx1 = (*(struct mpentry * const *)p1)->config_idx;
+ int idx2 = (*(struct mpentry * const *)p2)->config_idx;
- return strcmp(wwid1, wwid2);
+ if ((r = strcmp(wwid1, wwid2)) != 0)
+ return r;
+ return idx1 - idx2;
}
void merge_mptable(vector mptable)
@@ -541,6 +546,7 @@ void merge_mptable(vector mptable)
free_mpe(mp1);
continue;
}
+ mp1->config_idx = i;
}
vector_sort(mptable, wwid_compar);
vector_foreach_slot(mptable, mp1, i) {
diff --git a/libmultipath/config.h b/libmultipath/config.h
index fdcdff0a..fc44914c 100644
--- a/libmultipath/config.h
+++ b/libmultipath/config.h
@@ -133,6 +133,7 @@ struct mpentry {
uid_t uid;
gid_t gid;
mode_t mode;
+ int config_idx;
};
struct config {
------------
-Ben
> 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
