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

[Martin Wilck <mwilck@suse.com>]

On Wed, 2022-08-24 at 19:02 +0200, Martin Wilck wrote:
> On Wed, 2022-08-24 at 11:16 -0500, Benjamin Marzinski wrote:
> > On Wed, Aug 24, 2022 at 09:07:56AM +0200, Martin Wilck wrote:
> > > On Tue, 2022-08-23 at 15:48 -0500, Benjamin Marzinski wrote:
> > > > On Thu, Aug 18, 2022 at 11:06:28PM +0200,
> > > > mwilck@suse.com wrote:
> > > > > 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 | 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.
> > > 
> > > Thanks for pointing this out. I believe it's easier than that: as
> > > we're
> > > passed the offsets into the array (aka struct mpentry **), we can
> > > simply compare p1 and p2 if the strings are equal.
> > > 
> > > Agree?
> > 
> > I don't think so. Comparing the array offsets assumes that two
> > mpentries
> > are still ordered correctly when they are compared against each
> > other.
> > But the way quick sort works, array elements can get swapped around
> > multiple times, based on whether they are larger or smaller than
> > some
> > pivot point. It's possible that the two mpentries already switched
> > order
> > before they were compared.
> > 
> > Essentially, all comparing the offset does is force qsort to not
> > switch
> > the place of two otherwise equal entries. But for speed reasons
> > alone,
> > there is no reason why qsort would bother to swap the location of
> > two
> > equal entries.  
> > 
> > Here's an example of what could go wrong:
> > 
> > Say you start with the array (I'm also tracking the mpentry's
> > original
> > config index)
> > 
> > array offset:   0       1       2       3       4
> > config_idx:     0       1       2       3       4
> > wwid:           D       B       C       D       A       
> > 
> > Say qsort picks the element at array offset 2 (wwid "C") as the
> > pivot.
> > Usually quicksort works by walking towards the center of the array
> > segment from both ends, swapping the positions of elements bigger
> > than
> > the pivot with the positions of ones smaller than or equal to the
> > pivot.
> > So after the first round you would swap the element at array offset
> > 4
> > (wwid "A") with the element at array offset 0 (wwid "D"). This
> > would
> > give you.
> > 
> > array offset:   0       1       2       3       4
> > config_idx      4       1       2       3       0
> > wwid:           A       B       C       D       D
> > 
> > After this no further swaps will happen using the original
> > wwid_compar(). Adding a comparison to the array offset won't change
> > anything. But the wwid "D" mpentry that was orinally earlier in the
> > config (config_idx = 0) is now after the wwid "D" mpentry that was
> > originally later (config_idx = 3).
> > 
> > Comparing the config_idx will cause the elements at array offset 3
> > and 4
> > to switch places, restoring their original ordering.
> 
> Hm, too bad. 
> 
> I don't like the idea of adding another field to the array just to
> stabilize the sort. But a fast, stable sort algorithm in for strings
> in
> C seems to be hard to find. So yes, let's add the sort index for now,
> perhaps we'll find a more elegant solution later.

Digging some more, I found that glibc's qsort() is actually merge sort,
which is a stable sort algorithm and doesn't suffer from this issue.
The glibc documentation is misleading in this respect. Unfortunately
we'can't just support glibc. But we could simply copy in glibc's
msort.c code for other libraries.

Martin

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