| Message ID | 20241203214702.107918-2-mwilck@suse.com (mailing list archive) |
|---|---|
| State | Not Applicable, archived |
| Delegated to: | Benjamin Marzinski |
| Headers | show |
| Series | multipath-tools fixes | expand |
On Tue, Dec 03, 2024 at 10:47:02PM +0100, Martin Wilck wrote: > pgp->id is not only calculated with a weak XOR hash, it can also > get wrong if any path regrouping occurs. As it's not a big gain > performance-wise, just drop pgp->id and compare path groups > directly. > > The previous algorithm didn't detect the case case where cpgp > contained a path that was not contained in pgp. Fix this, too, > by comparing the number of paths in the path groups and making > sure that each pg of mpp is matched by exactly one pg of cmpp. > > Fixes: 90773ba ("libmultipath: resolve hash collisions in pgcmp()") > Suggested-by: Benjamin Marzinski <bmarzins@redhat.com> > Signed-off-by: Martin Wilck <mwilck@suse.com> Reviewed-by: Benjamin Marzinski <bmarzins@redhat.com> > --- > libmultipath/configure.c | 87 ++++++++++++++++++++++++++-------------- > libmultipath/dmparser.c | 1 - > libmultipath/structs.h | 1 - > 3 files changed, 56 insertions(+), 33 deletions(-) > > diff --git a/libmultipath/configure.c b/libmultipath/configure.c > index 9ab84d5..bfa8a39 100644 > --- a/libmultipath/configure.c > +++ b/libmultipath/configure.c > @@ -416,16 +416,6 @@ int setup_map(struct multipath *mpp, char **params, struct vectors *vecs) > return 0; > } > > -static void > -compute_pgid(struct pathgroup * pgp) > -{ > - struct path * pp; > - int i; > - > - vector_foreach_slot (pgp->paths, pp, i) > - pgp->id ^= (long)pp; > -} > - > static int pathcmp(const struct pathgroup *pgp, const struct pathgroup *cpgp) > { > int i, j; > @@ -445,32 +435,71 @@ static int pathcmp(const struct pathgroup *pgp, const struct pathgroup *cpgp) > return pnum - found; > } > > -static int > -pgcmp (struct multipath * mpp, struct multipath * cmpp) > +static int pgcmp(struct multipath *mpp, struct multipath *cmpp) > { > int i, j; > - struct pathgroup * pgp; > - struct pathgroup * cpgp; > - int r = 0; > + struct pathgroup *pgp, *cpgp; > + BITFIELD(bf, bits_per_slot); > + struct bitfield *bf__ __attribute__((cleanup(cleanup_bitfield))) = NULL; > > - if (!mpp) > - return 0; > + if (VECTOR_SIZE(mpp->pg) != VECTOR_SIZE(cmpp->pg)) > + return 1; > + > + /* handle the unlikely case of more than 64 pgs */ > + if ((unsigned int)VECTOR_SIZE(cmpp->pg) > bits_per_slot) { > + bf__ = alloc_bitfield(VECTOR_SIZE(cmpp->pg)); > + if (bf__ == NULL) > + /* error - if in doubt, assume not equal */ > + return 1; > + bf = bf__; > + } > > vector_foreach_slot (mpp->pg, pgp, i) { > - compute_pgid(pgp); > > - vector_foreach_slot (cmpp->pg, cpgp, j) { > - if (pgp->id == cpgp->id && > - !pathcmp(pgp, cpgp)) { > - r = 0; > - break; > + if (VECTOR_SIZE(pgp->paths) == 0) { > + bool found = false; > + > + vector_foreach_slot (cmpp->pg, cpgp, j) { > + if (!is_bit_set_in_bitfield(j, bf) && > + VECTOR_SIZE(cpgp->paths) == 0) { > + set_bit_in_bitfield(j, bf); > + found = true; > + break; > + } > } > - r++; > + if (!found) > + return 1; > + } else { > + bool found = false; > + struct path *pp = VECTOR_SLOT(pgp->paths, 0); > + > + /* search for a pg in cmpp that contains pp */ > + vector_foreach_slot (cmpp->pg, cpgp, j) { > + if (!is_bit_set_in_bitfield(j, bf) && > + VECTOR_SIZE(cpgp->paths) == VECTOR_SIZE(pgp->paths)) { > + int k; > + struct path *cpp; > + > + vector_foreach_slot(cpgp->paths, cpp, k) { > + if (cpp != pp) > + continue; > + /* > + * cpgp contains pp. > + * See if it's identical. > + */ > + set_bit_in_bitfield(j, bf); > + if (pathcmp(pgp, cpgp)) > + return 1; > + found = true; > + break; > + } > + } > + } > + if (!found) > + return 1; > } > - if (r) > - return r; > } > - return r; > + return 0; > } > > void trigger_partitions_udev_change(struct udev_device *dev, > @@ -763,10 +792,6 @@ void select_action (struct multipath *mpp, const struct vector_s *curmp, > select_reload_action(mpp, "minio change"); > return; > } > - if (!cmpp->pg || VECTOR_SIZE(cmpp->pg) != VECTOR_SIZE(mpp->pg)) { > - select_reload_action(mpp, "path group number change"); > - return; > - } > if (pgcmp(mpp, cmpp)) { > select_reload_action(mpp, "path group topology change"); > return; > diff --git a/libmultipath/dmparser.c b/libmultipath/dmparser.c > index 1d0506d..c8c47e0 100644 > --- a/libmultipath/dmparser.c > +++ b/libmultipath/dmparser.c > @@ -307,7 +307,6 @@ int disassemble_map(const struct vector_s *pathvec, > > free(word); > > - pgp->id ^= (long)pp; > pp->pgindex = i + 1; > > for (k = 0; k < num_paths_args; k++) > diff --git a/libmultipath/structs.h b/libmultipath/structs.h > index 49d9a2f..2159cb3 100644 > --- a/libmultipath/structs.h > +++ b/libmultipath/structs.h > @@ -531,7 +531,6 @@ static inline int san_path_check_enabled(const struct multipath *mpp) > } > > struct pathgroup { > - long id; > int status; > int priority; > int enabled_paths; > -- > 2.47.0
diff --git a/libmultipath/configure.c b/libmultipath/configure.c index 9ab84d5..bfa8a39 100644 --- a/libmultipath/configure.c +++ b/libmultipath/configure.c @@ -416,16 +416,6 @@ int setup_map(struct multipath *mpp, char **params, struct vectors *vecs) return 0; } -static void -compute_pgid(struct pathgroup * pgp) -{ - struct path * pp; - int i; - - vector_foreach_slot (pgp->paths, pp, i) - pgp->id ^= (long)pp; -} - static int pathcmp(const struct pathgroup *pgp, const struct pathgroup *cpgp) { int i, j; @@ -445,32 +435,71 @@ static int pathcmp(const struct pathgroup *pgp, const struct pathgroup *cpgp) return pnum - found; } -static int -pgcmp (struct multipath * mpp, struct multipath * cmpp) +static int pgcmp(struct multipath *mpp, struct multipath *cmpp) { int i, j; - struct pathgroup * pgp; - struct pathgroup * cpgp; - int r = 0; + struct pathgroup *pgp, *cpgp; + BITFIELD(bf, bits_per_slot); + struct bitfield *bf__ __attribute__((cleanup(cleanup_bitfield))) = NULL; - if (!mpp) - return 0; + if (VECTOR_SIZE(mpp->pg) != VECTOR_SIZE(cmpp->pg)) + return 1; + + /* handle the unlikely case of more than 64 pgs */ + if ((unsigned int)VECTOR_SIZE(cmpp->pg) > bits_per_slot) { + bf__ = alloc_bitfield(VECTOR_SIZE(cmpp->pg)); + if (bf__ == NULL) + /* error - if in doubt, assume not equal */ + return 1; + bf = bf__; + } vector_foreach_slot (mpp->pg, pgp, i) { - compute_pgid(pgp); - vector_foreach_slot (cmpp->pg, cpgp, j) { - if (pgp->id == cpgp->id && - !pathcmp(pgp, cpgp)) { - r = 0; - break; + if (VECTOR_SIZE(pgp->paths) == 0) { + bool found = false; + + vector_foreach_slot (cmpp->pg, cpgp, j) { + if (!is_bit_set_in_bitfield(j, bf) && + VECTOR_SIZE(cpgp->paths) == 0) { + set_bit_in_bitfield(j, bf); + found = true; + break; + } } - r++; + if (!found) + return 1; + } else { + bool found = false; + struct path *pp = VECTOR_SLOT(pgp->paths, 0); + + /* search for a pg in cmpp that contains pp */ + vector_foreach_slot (cmpp->pg, cpgp, j) { + if (!is_bit_set_in_bitfield(j, bf) && + VECTOR_SIZE(cpgp->paths) == VECTOR_SIZE(pgp->paths)) { + int k; + struct path *cpp; + + vector_foreach_slot(cpgp->paths, cpp, k) { + if (cpp != pp) + continue; + /* + * cpgp contains pp. + * See if it's identical. + */ + set_bit_in_bitfield(j, bf); + if (pathcmp(pgp, cpgp)) + return 1; + found = true; + break; + } + } + } + if (!found) + return 1; } - if (r) - return r; } - return r; + return 0; } void trigger_partitions_udev_change(struct udev_device *dev, @@ -763,10 +792,6 @@ void select_action (struct multipath *mpp, const struct vector_s *curmp, select_reload_action(mpp, "minio change"); return; } - if (!cmpp->pg || VECTOR_SIZE(cmpp->pg) != VECTOR_SIZE(mpp->pg)) { - select_reload_action(mpp, "path group number change"); - return; - } if (pgcmp(mpp, cmpp)) { select_reload_action(mpp, "path group topology change"); return; diff --git a/libmultipath/dmparser.c b/libmultipath/dmparser.c index 1d0506d..c8c47e0 100644 --- a/libmultipath/dmparser.c +++ b/libmultipath/dmparser.c @@ -307,7 +307,6 @@ int disassemble_map(const struct vector_s *pathvec, free(word); - pgp->id ^= (long)pp; pp->pgindex = i + 1; for (k = 0; k < num_paths_args; k++) diff --git a/libmultipath/structs.h b/libmultipath/structs.h index 49d9a2f..2159cb3 100644 --- a/libmultipath/structs.h +++ b/libmultipath/structs.h @@ -531,7 +531,6 @@ static inline int san_path_check_enabled(const struct multipath *mpp) } struct pathgroup { - long id; int status; int priority; int enabled_paths;
pgp->id is not only calculated with a weak XOR hash, it can also get wrong if any path regrouping occurs. As it's not a big gain performance-wise, just drop pgp->id and compare path groups directly. The previous algorithm didn't detect the case case where cpgp contained a path that was not contained in pgp. Fix this, too, by comparing the number of paths in the path groups and making sure that each pg of mpp is matched by exactly one pg of cmpp. Fixes: 90773ba ("libmultipath: resolve hash collisions in pgcmp()") Suggested-by: Benjamin Marzinski <bmarzins@redhat.com> Signed-off-by: Martin Wilck <mwilck@suse.com> --- libmultipath/configure.c | 87 ++++++++++++++++++++++++++-------------- libmultipath/dmparser.c | 1 - libmultipath/structs.h | 1 - 3 files changed, 56 insertions(+), 33 deletions(-)