Re: [PATCH 5/11] cxl/lib: Maintain decoders in id order

From: Davidlohr Bueso <dave@stgolabs.net>
To: Dan Williams <dan.j.williams@intel.com>
Cc: vishal.l.verma@intel.com, alison.schofield@intel.com,
	nvdimm@lists.linux.dev, linux-cxl@vger.kernel.org,
	a.manzanares@samsung.com
Subject: Re: [PATCH 5/11] cxl/lib: Maintain decoders in id order
Date: Wed, 13 Jul 2022 12:45:02 -0700	[thread overview]
Message-ID: <20220713194502.5hxf5jxpwzvsukx7@offworld> (raw)
In-Reply-To: <165765287277.435671.14320322485572083484.stgit@dwillia2-xfh>

On Tue, 12 Jul 2022, Dan Williams wrote:

>Given that decoder instance order is fundamental to the DPA translation
>sequence for endpoint decoders, enforce that cxl_decoder_for_each() returns
>decoders in instance order. Otherwise, they show up in readddir() order
>which is not predictable.
>
>Add a list_add_sorted() to generically handle inserting into a sorted list.

With the already available list_add_before ccan code nit already pointed out
by Ira.

Reviewed-by: Davidlohr Bueso <dave@stgolabs.net>

>
>Signed-off-by: Dan Williams <dan.j.williams@intel.com>
>---
> cxl/lib/libcxl.c |    8 ++++++-
> util/list.h      |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 68 insertions(+), 1 deletion(-)
>
>diff --git a/cxl/lib/libcxl.c b/cxl/lib/libcxl.c
>index f36edcfc735a..e4c5d3819e88 100644
>--- a/cxl/lib/libcxl.c
>+++ b/cxl/lib/libcxl.c
>@@ -19,6 +19,7 @@
> #include <ccan/short_types/short_types.h>
>
> #include <util/log.h>
>+#include <util/list.h>
> #include <util/size.h>
> #include <util/sysfs.h>
> #include <util/bitmap.h>
>@@ -908,6 +909,11 @@ cxl_endpoint_get_memdev(struct cxl_endpoint *endpoint)
> 	return NULL;
> }
>
>+static int decoder_id_cmp(struct cxl_decoder *d1, struct cxl_decoder *d2)
>+{
>+	return d1->id - d2->id;
>+}
>+
> static void *add_cxl_decoder(void *parent, int id, const char *cxldecoder_base)
> {
> 	const char *devname = devpath_to_devname(cxldecoder_base);
>@@ -1049,7 +1055,7 @@ static void *add_cxl_decoder(void *parent, int id, const char *cxldecoder_base)
> 			return decoder_dup;
> 		}
>
>-	list_add(&port->decoders, &decoder->list);
>+	list_add_sorted(&port->decoders, decoder, list, decoder_id_cmp);
>
> 	free(path);
> 	return decoder;
>diff --git a/util/list.h b/util/list.h
>index 1ea9c59b9f0c..c6584e3ec725 100644
>--- a/util/list.h
>+++ b/util/list.h
>@@ -37,4 +37,65 @@ static inline void list_add_after_(struct list_head *h,
> 	(void)list_debug(h, abortstr);
> }
>
>+/**
>+ * list_add_before - add an entry before the given node in the linked list.
>+ * @h: the list_head to add the node to
>+ * @l: the list_node before which to add to
>+ * @n: the list_node to add to the list.
>+ *
>+ * The list_node does not need to be initialized; it will be overwritten.
>+ * Example:
>+ *	struct child *child = malloc(sizeof(*child));
>+ *
>+ *	child->name = "geoffrey";
>+ *	list_add_before(&parent->children, &child1->list, &child->list);
>+ *	parent->num_children++;
>+ */
>+#define list_add_before(h, l, n) list_add_before_(h, l, n, LIST_LOC)
>+static inline void list_add_before_(struct list_head *h, struct list_node *l,
>+				    struct list_node *n, const char *abortstr)
>+{
>+	if (l->prev == &h->n) {
>+		/* l is the first element, this becomes a list_add */
>+		list_add(h, n);
>+		return;
>+	}
>+
>+	n->next = l;
>+	n->prev = l->prev;
>+	l->prev->next = n;
>+	l->prev = n;
>+}
>+
>+#define list_add_sorted(head, n, node, cmp)                                    \
>+	do {                                                                   \
>+		struct list_head *__head = (head);                             \
>+		typeof(n) __iter, __next;                                      \
>+		typeof(n) __new = (n);                                         \
>+                                                                               \
>+		if (list_empty(__head)) {                                      \
>+			list_add(__head, &__new->node);                        \
>+			break;                                                 \
>+		}                                                              \
>+                                                                               \
>+		list_for_each (__head, __iter, node) {                         \
>+			if (cmp(__new, __iter) < 0) {                          \
>+				list_add_before(__head, &__iter->node,         \
>+						&__new->node);                 \
>+				break;                                         \
>+			}                                                      \
>+			__next = list_next(__head, __iter, node);              \
>+			if (!__next) {                                         \
>+				list_add_after(__head, &__iter->node,          \
>+					       &__new->node);                  \
>+				break;                                         \
>+			}                                                      \
>+			if (cmp(__new, __next) < 0) {                          \
>+				list_add_before(__head, &__next->node,         \
>+						&__new->node);                 \
>+				break;                                         \
>+			}                                                      \
>+		}                                                              \
>+	} while (0)
>+
> #endif /* _NDCTL_LIST_H_ */
>