From: Martin Wilck <mwilck@xxxxxxxx>
When I read this code, I always get confused. Adding comments to
explain the algorithm.
Signed-off-by: Martin Wilck <mwilck@xxxxxxxx>
---
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
--
dm-devel mailing list
dm-devel@xxxxxxxxxx
https://listman.redhat.com/mailman/listinfo/dm-devel
