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

[Benjamin Marzinski <bmarzins@redhat.com>]

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

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