Re: [dm-devel] [PATCH 05/21] libmultipath: lookup_binding: add comment about the algorithm

[Martin Wilck <mwilck@suse.com>]

On Wed, 2023-09-06 at 17:43 -0500, Benjamin Marzinski wrote:
> On Fri, Sep 01, 2023 at 08:02:18PM +0200, mwilck@suse.com wrote:
> > From: Martin Wilck <mwilck@suse.com>
> > 
> > When I read this code, I always get confused. Adding comments to
> > explain the algorithm.
> > 
> > Signed-off-by: Martin Wilck <mwilck@suse.com>
> > ---
> >  libmultipath/alias.c | 35 +++++++++++++++++++++++++++++++++++
> >  1 file changed, 35 insertions(+)
> > 
> > diff --git a/libmultipath/alias.c b/libmultipath/alias.c
> > index f7834d1..e61eb91 100644
> > --- a/libmultipath/alias.c
> > +++ b/libmultipath/alias.c
> > @@ -172,6 +172,41 @@ lookup_binding(FILE *f, const char *map_wwid,
> > char **map_alias,
> >                 alias = strtok_r(buf, " \t", &saveptr);
> >                 if (!alias) /* blank line */
> >                         continue;
> > +
> > +               /*
> > +                * Find an unused index - explanation of the
> > algorithm
> > +                *
> > +                * ID: 1 = mpatha, 2 = mpathb, ...
> > +                *
> > +                * We assume the bindings are unsorted. The only
> > constraint
> > +                * is that no ID occurs more than once. IDs that
> > occur in the
> > +                * bindings are called "used".
> > +                *
> > +                * We call the list 1,2,3,..., exactly in this
> > order, the list
> > +                * of "expected" IDs. The variable "id" always
> > holds the next
> > +                * "expected" ID, IOW the last "expected" ID
> > encountered plus 1.
> > +                * Thus all IDs below "id" are known to be used.
> > However, at the
> > +                * end of the loop, the value of "id" isn't
> > necessarily unused.
> > +                *
> > +                * "smallest_bigger_id" is the smallest used ID
> > that was
> > +                * encountered while it was larger than the next
> > "expected" ID
> > +                * at that iteration. Let X be some used ID. If all
> > IDs below X
> > +                * are used and encountered in the right sequence
> > before X, "id"
> > +                * will be > X when the loop ends. Otherwise, X was
> > encountered
> > +                * "out of order", the condition (X > id) holds
> > when X is
> > +                * encountered, and "smallest_bigger_id" will be
> > set to X; i.e.
> > +                * it will be less or equal than X when the loop
> > ends.
> > +                *
> > +                * At the end of the loop, (id <
> > smallest_bigger_id) means that
> > +                * the value of "id" had been encountered neither
> > in order nor
> > +                * out of order, and is thus unused. (id >=
> > smallest_bigger_id)
> 
> I know the check is (id >= smallest_bigger_id), but as long as no ID
> occurs more than once, id can never actually be bigger than
> smallest_bigger_id since id only gets incremented when (curr_id ==
> id)
> and if smallest_bigger_id is not INT_MAX, then smallest_bigger_id
> already occured once in the file before id was incremented to equal
> it.
> This means it can't occur again, so id can never get incremented past
> it. Not this this really matters, so

Right. Like you, I thought this didn't matter for the algorithm as
such, and that explaining it would make the lengthy explanation even
lengthier.

Btw, if you have a simpler explanation of this algorithm, please
provide it ;-)

Martin

> 
> Reviewed-by: Benjamin Marzinski <bmarzins@redhat.com>
> 
> > +                * means that "id"'s value is in use. In this case,
> > we play safe
> > +                * and use "biggest_id + 1" as the next value to
> > try.
> > +                *
> > +                * biggest_id is always > smallest_bigger_id,
> > except in the
> > +                * "perfectly ordered" case.
> > +                */
> > +
> >                 curr_id = scan_devname(alias, prefix);
> >                 if (curr_id == id) {
> >                         if (id < INT_MAX)
> > -- 
> > 2.41.0
> 

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