| Message ID | 165765287277.435671.14320322485572083484.stgit@dwillia2-xfh |
|---|---|
| State | Superseded |
| Headers | show |
| Series | cxl: Region provisioning foundation | expand |
On Tue, Jul 12, 2022 at 12:07:52PM -0700, 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. > > 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) I see a list_add_before() in the latest ccan list code.[1] Should we just use that? The implementation is a bit different. [1] https://ccodearchive.net/info/list.html > +{ > + 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; Did you mean to add list_debug() here? Ira > +} > + > +#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_ */ > >
Ira Weiny wrote: > On Tue, Jul 12, 2022 at 12:07:52PM -0700, 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. > > > > 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) > > I see a list_add_before() in the latest ccan list code.[1] Should we just use > that? The implementation is a bit different. > > [1] https://ccodearchive.net/info/list.html Ah, thanks for checking. Yeah, probably time to refresh our fork to the latest upstream baseline. > > > +{ > > + 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; > > Did you mean to add list_debug() here? Looks like we get that for free with the upstream rebase.
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_ */ >
Davidlohr Bueso wrote: > 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. Done. > Reviewed-by: Davidlohr Bueso <dave@stgolabs.net> Thanks!
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_ */
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. 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(-)