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

[mwilck at suse.com]

From: Martin Wilck <mwilck at suse.com>

When I read this code, I always get confused. Adding comments to
explain the algorithm.

Signed-off-by: Martin Wilck <mwilck at 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)
+		 * 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