| Message ID | 20241127230430.139639-6-mwilck@suse.com (mailing list archive) |
|---|---|
| State | Not Applicable, archived |
| Delegated to: | Benjamin Marzinski |
| Headers | show |
| Series | multipath-tools fixes | expand |
On Thu, Nov 28, 2024 at 12:04:27AM +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> > --- > libmultipath/configure.c | 94 ++++++++++++++++++++++++++-------------- > libmultipath/dmparser.c | 1 - > libmultipath/structs.h | 1 - > 3 files changed, 61 insertions(+), 35 deletions(-) > > diff --git a/libmultipath/configure.c b/libmultipath/configure.c > index 9ab84d5..bd71e68 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,74 @@ 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; Nitpick. I'm pretty sure we can't call pgcmp() unless mpp and cmpp are set. It seems like we should either trust the parameters (this is a static function with one caller) or check both of them. > if (!mpp) > return 0; > > - vector_foreach_slot (mpp->pg, pgp, i) { > - compute_pgid(pgp); > + if (VECTOR_SIZE(mpp->pg) != VECTOR_SIZE(cmpp->pg)) > + return 1; > > - vector_foreach_slot (cmpp->pg, cpgp, j) { > - if (pgp->id == cpgp->id && > - !pathcmp(pgp, cpgp)) { > - r = 0; > - break; > - } > - r++; > - } > - if (r) > - return r; > + /* 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__; > } > - return r; > + > + vector_foreach_slot (mpp->pg, pgp, i) { > + > + 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; > + } > + } > + 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; > + } > + } > + return 0; > } > > void trigger_partitions_udev_change(struct udev_device *dev, > @@ -763,11 +795,7 @@ 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)) { > + if (!cmpp->pg || pgcmp(mpp, cmpp)) { I know that the code did this before, but is there a reason why we always reload if cmpp->pg is NULL? I'm pretty sure it's possible to call select action when neither mpp nor cmpp have any paths. (cli_reload on a pathless device should do that). In this case, the topology isn't changing, and AFAICS pgcmp() should work with no pathgroups. -Ben > 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
On Mon, 2024-12-02 at 19:17 -0500, Benjamin Marzinski wrote: > On Thu, Nov 28, 2024 at 12:04:27AM +0100, Martin Wilck wrote: > > > > @@ -763,11 +795,7 @@ 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)) { > > + if (!cmpp->pg || pgcmp(mpp, cmpp)) { > > I know that the code did this before, but is there a reason why we > always reload if cmpp->pg is NULL? I'm pretty sure it's possible to > call > select action when neither mpp nor cmpp have any paths. (cli_reload > on a > pathless device should do that). In this case, the topology isn't > changing, and AFAICS pgcmp() should work with no pathgroups. It dates back to b0991a8 ("Allow zero paths for multipath map"), multipath-tools 0.4.9. I guess back then Hannes either encountered in crash in some situation, or he was just being cautious. I can remove this check. Martin
On Tue, 2024-12-03 at 13:40 +0100, Martin Wilck wrote: > On Mon, 2024-12-02 at 19:17 -0500, Benjamin Marzinski wrote: > > On Thu, Nov 28, 2024 at 12:04:27AM +0100, Martin Wilck wrote: > > > > > > @@ -763,11 +795,7 @@ 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)) { > > > + if (!cmpp->pg || pgcmp(mpp, cmpp)) { > > > > I know that the code did this before, but is there a reason why we > > always reload if cmpp->pg is NULL? I'm pretty sure it's possible to > > call > > select action when neither mpp nor cmpp have any paths. (cli_reload > > on a > > pathless device should do that). In this case, the topology isn't > > changing, and AFAICS pgcmp() should work with no pathgroups. > > > It dates back to b0991a8 ("Allow zero paths for multipath map"), > multipath-tools 0.4.9. > > I guess back then Hannes either encountered in crash in some > situation, > or he was just being cautious. > > I can remove this check. As all our vector macros handle the (V==NULL) case, we can rely on them doing the "right thing" if we just check VECTOR_SIZE(). While I kind of dislike these hidden checks (other code bases like systemd use assert() instead, which probably helps finding bugs), we rely on this behavior basically everywhere in our code, so why not here. Regards Martin
diff --git a/libmultipath/configure.c b/libmultipath/configure.c index 9ab84d5..bd71e68 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,74 @@ 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; - vector_foreach_slot (mpp->pg, pgp, i) { - compute_pgid(pgp); + if (VECTOR_SIZE(mpp->pg) != VECTOR_SIZE(cmpp->pg)) + return 1; - vector_foreach_slot (cmpp->pg, cpgp, j) { - if (pgp->id == cpgp->id && - !pathcmp(pgp, cpgp)) { - r = 0; - break; - } - r++; - } - if (r) - return r; + /* 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__; } - return r; + + vector_foreach_slot (mpp->pg, pgp, i) { + + 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; + } + } + 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; + } + } + return 0; } void trigger_partitions_udev_change(struct udev_device *dev, @@ -763,11 +795,7 @@ 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)) { + if (!cmpp->pg || 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 | 94 ++++++++++++++++++++++++++-------------- libmultipath/dmparser.c | 1 - libmultipath/structs.h | 1 - 3 files changed, 61 insertions(+), 35 deletions(-)