[PATCH 0/3] cxl/region: Autodiscovery position repair

[PATCH 0/3] cxl/region: Autodiscovery position repair

[alison.schofield]

From: Alison Schofield <alison.schofield@intel.com>

Some region configurations fail to assemble through the auto-discovered
region path. These are valid region configurations that can be assembled
correctly if presented as user defined regions.

The difference being that user defined regions arrive at the driver
with their targets in interleave order, whereas with autodiscovered
regions, the driver needs to assign each target in the interleave
set a correct position. And, in some cases, that fails.

cxl_region_sort_targets() uses the kernel sort() function to put the
targets in relative order. Once the relative ordering is complete,
positions are assigned based on each targets index in the sorted list.

That relative sort doesn't consider the offset of a port into its
parent port. In the failure case, a 2 + 2 config (2 host bridges each
with 2 endpoints), this causes the sort to put all targets of one port
ahead of another port, when they were expected to be interleaved.

While examining the problem and weighing the option of repairing the
existing sort algorithm with assigning positions another way, I chose
the latter. Each endpoint can be examined individually to discover its
position in the region interleave.

The presentation of this patchset was a challenge. While the changes
are essentially a replacement the resulting diff is horrible. (I did 
try multiple git diff algs). So, after a simple preparation patch,
its presented like this:

Patch 2:The new method, calc_interleave_pos(), is introduced and used
	in a dev_dbg() exercise on user defined regions.

Patch 3:Calc_interleave_pos() replaces the relative sort() in
	cxl_region_sort_targets() for auto-discoverd regions
	and the now obsolete sort helpers are removed.

The only function that seems useful for a side by side diff viewing
is cxl_region_sort_targets() and it is in Patch 3.


To test this, I've been able to validate that a previously failing 2+2
autodiscovered config now works. Also, using the dev_dbg() selftest
hook in Patch 2, proved the new calculation against all regions created
during the execution of the CXL unit test suite.

For example:
# meson test -C build cxl-xor-region.sh
# dmesg | grep Interleave
[  177.223243] cxl_core:cxl_region_attach:1765: cxl decoder8.1: Interleave calc match Success test_pos:0 cxled->pos:0
[  177.788170] cxl_core:cxl_region_attach:1765: cxl decoder8.1: Interleave calc match Success test_pos:0 cxled->pos:0
[  177.790720] cxl_core:cxl_region_attach:1765: cxl decoder10.0: Interleave calc match Success test_pos:1 cxled->pos:1
[  178.711246] cxl_core:cxl_region_attach:1765: cxl decoder8.1: Interleave calc match Success test_pos:0 cxled->pos:0
[  178.714015] cxl_core:cxl_region_attach:1765: cxl decoder16.0: Interleave calc match Success test_pos:1 cxled->pos:1
[  178.716846] cxl_core:cxl_region_attach:1765: cxl decoder17.0: Interleave calc match Success test_pos:2 cxled->pos:2
[  178.719660] cxl_core:cxl_region_attach:1765: cxl decoder18.0: Interleave calc match Success test_pos:3 cxled->pos:3


Alison Schofield (3):
  cxl/region: Prepare the decoder match range helper for reuse
  cxl/region: Calculate a target position in a region interleave
  cxl/region: Use calc_interleave_pos() with autodiscovered regions

 drivers/cxl/core/region.c | 205 ++++++++++++++++++++------------------
 1 file changed, 106 insertions(+), 99 deletions(-)


base-commit: 8a749fd1a8720d4619c91c8b6e7528c0a355c0aa
-- 
2.37.3

[PATCH 1/3] cxl/region: Prepare the decoder match range helper for reuse

[alison.schofield]

From: Alison Schofield <alison.schofield@intel.com>

match_decoder_by_range() and decoder_match_range() both determine
if an HPA range matches a decoder. The first does it for root
decoders and the second one operates on switch decoders.

Tidy these up with clear naming and make the switch helper more
like the root decoder helper in style and functionality. Make it
take the actual range, rather than an endpoint decoder from which
it extracts the range.

Aside from aethetics and maintainability, this is in preparation
for reuse.

Fixes: a32320b71f08 ("cxl/region: Add region autodiscovery")
Reported-by: Dmytro Adamenko <dmytro.adamenko@intel.com>
Signed-off-by: Alison Schofield <alison.schofield@intel.com>
---
 drivers/cxl/core/region.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/drivers/cxl/core/region.c b/drivers/cxl/core/region.c
index 6d63b8798c29..64206fc4d99b 100644
--- a/drivers/cxl/core/region.c
+++ b/drivers/cxl/core/region.c
@@ -1487,16 +1487,19 @@ static struct cxl_port *next_port(struct cxl_port *port)
 	return port->parent_dport->port;
 }
 
-static int decoder_match_range(struct device *dev, void *data)
+static int match_switch_decoder_by_range(struct device *dev, void *data)
 {
-	struct cxl_endpoint_decoder *cxled = data;
+	struct range *r1, *r2 = data;
 	struct cxl_switch_decoder *cxlsd;
 
 	if (!is_switch_decoder(dev))
 		return 0;
 
 	cxlsd = to_cxl_switch_decoder(dev);
-	return range_contains(&cxlsd->cxld.hpa_range, &cxled->cxld.hpa_range);
+	r1 = &cxlsd->cxld.hpa_range;
+	return range_contains(r1, r2);
+}
+
 }
 
 static void find_positions(const struct cxl_switch_decoder *cxlsd,
@@ -1565,7 +1568,8 @@ static int cmp_decode_pos(const void *a, const void *b)
 		goto err;
 	}
 
-	dev = device_find_child(&port->dev, cxled_a, decoder_match_range);
+	dev = device_find_child(&port->dev, &cxled_a->cxld.hpa_range,
+				match_switch_decoder_by_range);
 	if (!dev) {
 		struct range *range = &cxled_a->cxld.hpa_range;
 
@@ -2696,7 +2700,7 @@ static int devm_cxl_add_dax_region(struct cxl_region *cxlr)
 	return rc;
 }
 
-static int match_decoder_by_range(struct device *dev, void *data)
+static int match_root_decoder_by_range(struct device *dev, void *data)
 {
 	struct range *r1, *r2 = data;
 	struct cxl_root_decoder *cxlrd;
@@ -2827,7 +2831,7 @@ int cxl_add_to_region(struct cxl_port *root, struct cxl_endpoint_decoder *cxled)
 	int rc;
 
 	cxlrd_dev = device_find_child(&root->dev, &cxld->hpa_range,
-				      match_decoder_by_range);
+				      match_root_decoder_by_range);
 	if (!cxlrd_dev) {
 		dev_err(cxlmd->dev.parent,
 			"%s:%s no CXL window for range %#llx:%#llx\n",
-- 
2.37.3

[PATCH 2/3] cxl/region: Calculate a target position in a region interleave

[alison.schofield]

From: Alison Schofield <alison.schofield@intel.com>

Introduce a calculation that determines a targets position in a region
interleave. Perform a selftest of the calculation on user-defined
regions.

The region driver users the kernel sort() function to put region
targets in relative order. Positions are assigned based on each
targets index in that sorted list. That relative sort doesn't
consider the offset of a port into its parent port causing some
autodiscovered regions to fail creation. In one failure case,
a 2 + 2 config (2 host bridges each with 2 endpoints), the sort
put all targets of one port ahead of another port, when they were
expected to be interleaved.

In preparation for repairing the autodiscovery region assembly,
introduce a new method for discovering a target position in the
region interleave.

cxl_interleave_pos() offers a method to determine a targets position
by ascending from an endpoint to a root decoder. The calculation starts
with the endpoints local position and its position in its parents port.
Traversing towards the root decoder and examining position and ways,
allows the position to be refined all the way to the root decoder.

This calculation, applied iteratively, yields the correct position:

position = position * parent_ways + parent_pos;

...when you follow these rules:

Rule #1 - When (parent_ways == region_ways), abort.
	  position = parent_position;
	  This rule is applied in calc_interleave_pos()

Rule #2 - Use an index into the target list when finding pos.
	  This rule is applied in the helper find_pos_and_ways().

Include a selftest that exercises this new position calculation against
every successfully configured user-defined region.

Fixes: a32320b71f08 ("cxl/region: Add region autodiscovery")
Reported-by: Dmytro Adamenko <dmytro.adamenko@intel.com>
Signed-off-by: Alison Schofield <alison.schofield@intel.com>
---
 drivers/cxl/core/region.c | 100 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)

diff --git a/drivers/cxl/core/region.c b/drivers/cxl/core/region.c
index 64206fc4d99b..297b9132d5b3 100644
--- a/drivers/cxl/core/region.c
+++ b/drivers/cxl/core/region.c
@@ -1500,6 +1500,91 @@ static int match_switch_decoder_by_range(struct device *dev, void *data)
 	return range_contains(r1, r2);
 }
 
+/* Find the position of a port in it's parent and the parents ways */
+static int find_pos_and_ways(struct cxl_port *port, struct range *range,
+			     int *pos, int *ways)
+{
+	struct cxl_switch_decoder *cxlsd;
+	struct cxl_port *parent;
+	int child_ways = *ways;
+	int child_pos = *pos;
+	struct device *dev;
+	int index = 0;
+	int rc = -1;
+
+	parent = next_port(port);
+	if (!parent)
+		return rc;
+
+	dev = device_find_child(&parent->dev, range,
+				match_switch_decoder_by_range);
+	if (!dev) {
+		dev_err(port->uport_dev,
+			"failed to find decoder mapping %#llx-%#llx\n",
+			range->start, range->end);
+		return rc;
+	}
+	cxlsd = to_cxl_switch_decoder(dev);
+	*ways = cxlsd->cxld.interleave_ways;
+
+	/* Use the child ways/pos as index to target list */
+	if (cxlsd->nr_targets > child_ways)
+		index = child_pos * child_ways;
+
+	for (int i = index; i < *ways; i++) {
+		if (cxlsd->target[i] == port->parent_dport) {
+			*pos = i;
+			rc = 0;
+			break;
+		}
+	}
+	put_device(dev);
+
+	return rc;
+}
+
+static int calc_interleave_pos(struct cxl_endpoint_decoder *cxled,
+			       int region_ways)
+{
+	struct cxl_port *iter, *port = cxled_to_port(cxled);
+	struct cxl_memdev *cxlmd = cxled_to_memdev(cxled);
+	struct range *range = &cxled->cxld.hpa_range;
+	int parent_ways = 0;
+	int parent_pos = 0;
+	int rc, pos;
+
+	/* Initialize pos to its local position */
+	rc = find_pos_and_ways(port, range, &parent_pos, &parent_ways);
+	if (rc)
+		return -ENXIO;
+
+	pos = parent_pos;
+
+	if (parent_ways == region_ways)
+		goto out;
+
+	/* Iterate up the ancestral tree refining the position */
+	for (iter = next_port(port); iter; iter = next_port(iter)) {
+		if (is_cxl_root(iter))
+			break;
+
+		rc = find_pos_and_ways(iter, range, &parent_pos, &parent_ways);
+		if (rc)
+			return -ENXIO;
+
+		if (parent_ways == region_ways) {
+			pos = parent_pos;
+			break;
+		}
+		pos = pos * parent_ways + parent_pos;
+	}
+out:
+	dev_dbg(&cxlmd->dev,
+		"decoder:%s parent:%s port:%s range:%#llx-%#llx pos:%d\n",
+		dev_name(&cxled->cxld.dev), dev_name(cxlmd->dev.parent),
+		dev_name(&port->dev), range->start, range->end, pos);
+
+	return pos;
 }
 
 static void find_positions(const struct cxl_switch_decoder *cxlsd,
@@ -1765,6 +1850,21 @@ static int cxl_region_attach(struct cxl_region *cxlr,
 		.end = p->res->end,
 	};
 
+	if (p->nr_targets != p->interleave_ways)
+		return 0;
+
+	/* Exercise position calculator on user-defined regions */
+	for (int i = 0; i < p->nr_targets; i++) {
+		struct cxl_endpoint_decoder *cxled = p->targets[i];
+		int test_pos;
+
+		test_pos = calc_interleave_pos(cxled, p->interleave_ways);
+		dev_dbg(&cxled->cxld.dev,
+			"Interleave calc match %s test_pos:%d cxled->pos:%d\n",
+			(test_pos == cxled->pos) ? "Success" : "Fail",
+			test_pos, cxled->pos);
+	}
+
 	return 0;
 
 err_decrement:
-- 
2.37.3

[PATCH 3/3] cxl/region: Use calc_interleave_pos() with autodiscovered regions

[alison.schofield]

From: Alison Schofield <alison.schofield@intel.com>

For auto-discovered regions, the driver must assign each target to
the correct position in the region interleave set.

cxl_region_sort_targets() uses the kernel sort() function to put the
targets in relative order. Once the relative ordering is complete,
positions are assigned based on each targets index in that sorted list.

The sort() compare function does not consider the child offset into a
parent port. The sort put all targets of one port ahead of another
port when an interleave was expected, causing the region assembly to
fail.

Replace the relative sort, with calc_interleave_pos() on each target
in the region target list. That will find the exact position for each
target based on a walk up the ancestral tree from endpoint to root
decoder.

calc_interleave_pos() was introduced in a prior patch, so the work
here is to use in cxl_region_sort_targets().

Cleanup the obsolete helper functions from the prior sort().

Fixes: a32320b71f08 ("cxl/region: Add region autodiscovery")
Reported-by: Dmytro Adamenko <dmytro.adamenko@intel.com>
Signed-off-by: Alison Schofield <alison.schofield@intel.com>
---
 drivers/cxl/core/region.c | 127 +++++---------------------------------
 1 file changed, 15 insertions(+), 112 deletions(-)

diff --git a/drivers/cxl/core/region.c b/drivers/cxl/core/region.c
index 297b9132d5b3..5a4a70ceb4ce 100644
--- a/drivers/cxl/core/region.c
+++ b/drivers/cxl/core/region.c
@@ -1480,6 +1480,14 @@ static int cxl_region_attach_auto(struct cxl_region *cxlr,
 	return 0;
 }
 
+static int cmp_interleave_pos(const void *a, const void *b)
+{
+	struct cxl_endpoint_decoder *cxled_a = *(typeof(cxled_a) *)a;
+	struct cxl_endpoint_decoder *cxled_b = *(typeof(cxled_b) *)b;
+
+	return cxled_a->pos - cxled_b->pos;
+}
+
 static struct cxl_port *next_port(struct cxl_port *port)
 {
 	if (!port->parent_dport)
@@ -1587,131 +1595,26 @@ static int calc_interleave_pos(struct cxl_endpoint_decoder *cxled,
 	return pos;
 }
 
-static void find_positions(const struct cxl_switch_decoder *cxlsd,
-			   const struct cxl_port *iter_a,
-			   const struct cxl_port *iter_b, int *a_pos,
-			   int *b_pos)
-{
-	int i;
-
-	for (i = 0, *a_pos = -1, *b_pos = -1; i < cxlsd->nr_targets; i++) {
-		if (cxlsd->target[i] == iter_a->parent_dport)
-			*a_pos = i;
-		else if (cxlsd->target[i] == iter_b->parent_dport)
-			*b_pos = i;
-		if (*a_pos >= 0 && *b_pos >= 0)
-			break;
-	}
-}
-
-static int cmp_decode_pos(const void *a, const void *b)
-{
-	struct cxl_endpoint_decoder *cxled_a = *(typeof(cxled_a) *)a;
-	struct cxl_endpoint_decoder *cxled_b = *(typeof(cxled_b) *)b;
-	struct cxl_memdev *cxlmd_a = cxled_to_memdev(cxled_a);
-	struct cxl_memdev *cxlmd_b = cxled_to_memdev(cxled_b);
-	struct cxl_port *port_a = cxled_to_port(cxled_a);
-	struct cxl_port *port_b = cxled_to_port(cxled_b);
-	struct cxl_port *iter_a, *iter_b, *port = NULL;
-	struct cxl_switch_decoder *cxlsd;
-	struct device *dev;
-	int a_pos, b_pos;
-	unsigned int seq;
-
-	/* Exit early if any prior sorting failed */
-	if (cxled_a->pos < 0 || cxled_b->pos < 0)
-		return 0;
-
-	/*
-	 * Walk up the hierarchy to find a shared port, find the decoder that
-	 * maps the range, compare the relative position of those dport
-	 * mappings.
-	 */
-	for (iter_a = port_a; iter_a; iter_a = next_port(iter_a)) {
-		struct cxl_port *next_a, *next_b;
-
-		next_a = next_port(iter_a);
-		if (!next_a)
-			break;
-
-		for (iter_b = port_b; iter_b; iter_b = next_port(iter_b)) {
-			next_b = next_port(iter_b);
-			if (next_a != next_b)
-				continue;
-			port = next_a;
-			break;
-		}
-
-		if (port)
-			break;
-	}
-
-	if (!port) {
-		dev_err(cxlmd_a->dev.parent,
-			"failed to find shared port with %s\n",
-			dev_name(cxlmd_b->dev.parent));
-		goto err;
-	}
-
-	dev = device_find_child(&port->dev, &cxled_a->cxld.hpa_range,
-				match_switch_decoder_by_range);
-	if (!dev) {
-		struct range *range = &cxled_a->cxld.hpa_range;
-
-		dev_err(port->uport_dev,
-			"failed to find decoder that maps %#llx-%#llx\n",
-			range->start, range->end);
-		goto err;
-	}
-
-	cxlsd = to_cxl_switch_decoder(dev);
-	do {
-		seq = read_seqbegin(&cxlsd->target_lock);
-		find_positions(cxlsd, iter_a, iter_b, &a_pos, &b_pos);
-	} while (read_seqretry(&cxlsd->target_lock, seq));
-
-	put_device(dev);
-
-	if (a_pos < 0 || b_pos < 0) {
-		dev_err(port->uport_dev,
-			"failed to find shared decoder for %s and %s\n",
-			dev_name(cxlmd_a->dev.parent),
-			dev_name(cxlmd_b->dev.parent));
-		goto err;
-	}
-
-	dev_dbg(port->uport_dev, "%s comes %s %s\n",
-		dev_name(cxlmd_a->dev.parent),
-		a_pos - b_pos < 0 ? "before" : "after",
-		dev_name(cxlmd_b->dev.parent));
-
-	return a_pos - b_pos;
-err:
-	cxled_a->pos = -1;
-	return 0;
-}
-
 static int cxl_region_sort_targets(struct cxl_region *cxlr)
 {
 	struct cxl_region_params *p = &cxlr->params;
 	int i, rc = 0;
 
-	sort(p->targets, p->nr_targets, sizeof(p->targets[0]), cmp_decode_pos,
-	     NULL);
-
 	for (i = 0; i < p->nr_targets; i++) {
 		struct cxl_endpoint_decoder *cxled = p->targets[i];
 
+		cxled->pos = calc_interleave_pos(cxled, p->interleave_ways);
 		/*
-		 * Record that sorting failed, but still continue to restore
-		 * cxled->pos with its ->targets[] position so that follow-on
-		 * code paths can reliably do p->targets[cxled->pos] to
-		 * self-reference their entry.
+		 * Record that sorting failed, but still continue to calc
+		 * cxled->pos so that follow-on code paths can reliably
+		 * do p->targets[cxled->pos] to self-reference their entry.
 		 */
 		if (cxled->pos < 0)
 			rc = -ENXIO;
-		cxled->pos = i;
 	}
+	/* Keep the cxlr target list in interleave position order */
+	sort(p->targets, p->nr_targets, sizeof(p->targets[0]),
+	     cmp_interleave_pos, NULL);
 
 	dev_dbg(&cxlr->dev, "region sort %s\n", rc ? "failed" : "successful");
 	return rc;
-- 
2.37.3

Re: [PATCH 1/3] cxl/region: Prepare the decoder match range helper for reuse

[Jonathan Cameron]

On Thu,  5 Oct 2023 17:43:11 -0700
alison.schofield@intel.com wrote:

> From: Alison Schofield <alison.schofield@intel.com>
> 
> match_decoder_by_range() and decoder_match_range() both determine
> if an HPA range matches a decoder. The first does it for root
> decoders and the second one operates on switch decoders.
> 
> Tidy these up with clear naming and make the switch helper more
> like the root decoder helper in style and functionality. Make it
> take the actual range, rather than an endpoint decoder from which
> it extracts the range.
> 
> Aside from aethetics and maintainability, this is in preparation
> for reuse.
> 
> Fixes: a32320b71f08 ("cxl/region: Add region autodiscovery")
> Reported-by: Dmytro Adamenko <dmytro.adamenko@intel.com>
> Signed-off-by: Alison Schofield <alison.schofield@intel.com>

Reviewed-by: Jonathan Cameron <Jonathan.Cameron@huawei.com>

> ---
>  drivers/cxl/core/region.c | 16 ++++++++++------
>  1 file changed, 10 insertions(+), 6 deletions(-)
> 
> diff --git a/drivers/cxl/core/region.c b/drivers/cxl/core/region.c
> index 6d63b8798c29..64206fc4d99b 100644
> --- a/drivers/cxl/core/region.c
> +++ b/drivers/cxl/core/region.c
> @@ -1487,16 +1487,19 @@ static struct cxl_port *next_port(struct cxl_port *port)
>  	return port->parent_dport->port;
>  }
>  
> -static int decoder_match_range(struct device *dev, void *data)
> +static int match_switch_decoder_by_range(struct device *dev, void *data)
>  {
> -	struct cxl_endpoint_decoder *cxled = data;
> +	struct range *r1, *r2 = data;
>  	struct cxl_switch_decoder *cxlsd;
>  
>  	if (!is_switch_decoder(dev))
>  		return 0;
>  
>  	cxlsd = to_cxl_switch_decoder(dev);
> -	return range_contains(&cxlsd->cxld.hpa_range, &cxled->cxld.hpa_range);
> +	r1 = &cxlsd->cxld.hpa_range;
> +	return range_contains(r1, r2);
> +}
> +
>  }
>  
>  static void find_positions(const struct cxl_switch_decoder *cxlsd,
> @@ -1565,7 +1568,8 @@ static int cmp_decode_pos(const void *a, const void *b)
>  		goto err;
>  	}
>  
> -	dev = device_find_child(&port->dev, cxled_a, decoder_match_range);
> +	dev = device_find_child(&port->dev, &cxled_a->cxld.hpa_range,
> +				match_switch_decoder_by_range);
>  	if (!dev) {
>  		struct range *range = &cxled_a->cxld.hpa_range;
>  
> @@ -2696,7 +2700,7 @@ static int devm_cxl_add_dax_region(struct cxl_region *cxlr)
>  	return rc;
>  }
>  
> -static int match_decoder_by_range(struct device *dev, void *data)
> +static int match_root_decoder_by_range(struct device *dev, void *data)
>  {
>  	struct range *r1, *r2 = data;
>  	struct cxl_root_decoder *cxlrd;
> @@ -2827,7 +2831,7 @@ int cxl_add_to_region(struct cxl_port *root, struct cxl_endpoint_decoder *cxled)
>  	int rc;
>  
>  	cxlrd_dev = device_find_child(&root->dev, &cxld->hpa_range,
> -				      match_decoder_by_range);
> +				      match_root_decoder_by_range);
>  	if (!cxlrd_dev) {
>  		dev_err(cxlmd->dev.parent,
>  			"%s:%s no CXL window for range %#llx:%#llx\n",

Re: [PATCH 1/3] cxl/region: Prepare the decoder match range helper for reuse

[Dave Jiang]

On 10/5/23 17:43, alison.schofield@intel.com wrote:
> From: Alison Schofield <alison.schofield@intel.com>
> 
> match_decoder_by_range() and decoder_match_range() both determine
> if an HPA range matches a decoder. The first does it for root
> decoders and the second one operates on switch decoders.
> 
> Tidy these up with clear naming and make the switch helper more
> like the root decoder helper in style and functionality. Make it
> take the actual range, rather than an endpoint decoder from which
> it extracts the range.
> 
> Aside from aethetics and maintainability, this is in preparation

s/aethetics/aesthetics/

> for reuse.
> 
> Fixes: a32320b71f08 ("cxl/region: Add region autodiscovery")
> Reported-by: Dmytro Adamenko <dmytro.adamenko@intel.com>
> Signed-off-by: Alison Schofield <alison.schofield@intel.com>

Those two function names are definitely very confusing. 

Reviewed-by: Dave Jiang <dave.jiang@intel.com>

> ---
>  drivers/cxl/core/region.c | 16 ++++++++++------
>  1 file changed, 10 insertions(+), 6 deletions(-)
> 
> diff --git a/drivers/cxl/core/region.c b/drivers/cxl/core/region.c
> index 6d63b8798c29..64206fc4d99b 100644
> --- a/drivers/cxl/core/region.c
> +++ b/drivers/cxl/core/region.c
> @@ -1487,16 +1487,19 @@ static struct cxl_port *next_port(struct cxl_port *port)
>  	return port->parent_dport->port;
>  }
>  
> -static int decoder_match_range(struct device *dev, void *data)
> +static int match_switch_decoder_by_range(struct device *dev, void *data)
>  {
> -	struct cxl_endpoint_decoder *cxled = data;
> +	struct range *r1, *r2 = data;
>  	struct cxl_switch_decoder *cxlsd;
>  
>  	if (!is_switch_decoder(dev))
>  		return 0;
>  
>  	cxlsd = to_cxl_switch_decoder(dev);
> -	return range_contains(&cxlsd->cxld.hpa_range, &cxled->cxld.hpa_range);
> +	r1 = &cxlsd->cxld.hpa_range;
> +	return range_contains(r1, r2);
> +}
> +
>  }
>  
>  static void find_positions(const struct cxl_switch_decoder *cxlsd,
> @@ -1565,7 +1568,8 @@ static int cmp_decode_pos(const void *a, const void *b)
>  		goto err;
>  	}
>  
> -	dev = device_find_child(&port->dev, cxled_a, decoder_match_range);
> +	dev = device_find_child(&port->dev, &cxled_a->cxld.hpa_range,
> +				match_switch_decoder_by_range);
>  	if (!dev) {
>  		struct range *range = &cxled_a->cxld.hpa_range;
>  
> @@ -2696,7 +2700,7 @@ static int devm_cxl_add_dax_region(struct cxl_region *cxlr)
>  	return rc;
>  }
>  
> -static int match_decoder_by_range(struct device *dev, void *data)
> +static int match_root_decoder_by_range(struct device *dev, void *data)
>  {
>  	struct range *r1, *r2 = data;
>  	struct cxl_root_decoder *cxlrd;
> @@ -2827,7 +2831,7 @@ int cxl_add_to_region(struct cxl_port *root, struct cxl_endpoint_decoder *cxled)
>  	int rc;
>  
>  	cxlrd_dev = device_find_child(&root->dev, &cxld->hpa_range,
> -				      match_decoder_by_range);
> +				      match_root_decoder_by_range);
>  	if (!cxlrd_dev) {
>  		dev_err(cxlmd->dev.parent,
>  			"%s:%s no CXL window for range %#llx:%#llx\n",

Re: [PATCH 2/3] cxl/region: Calculate a target position in a region interleave

[Dave Jiang]

On 10/5/23 17:43, alison.schofield@intel.com wrote:
> From: Alison Schofield <alison.schofield@intel.com>
> 
> Introduce a calculation that determines a targets position in a region
> interleave. Perform a selftest of the calculation on user-defined
> regions.
> 
> The region driver users the kernel sort() function to put region

s/users/uses/

> targets in relative order. Positions are assigned based on each
> targets index in that sorted list. That relative sort doesn't

s/targets/target/

> consider the offset of a port into its parent port causing some

s/causing/which causes/

> autodiscovered regions to fail creation. In one failure case,

s/autodiscovered/auto-discovered/

> a 2 + 2 config (2 host bridges each with 2 endpoints), the sort
> put all targets of one port ahead of another port, when they were

s/put/puts/
s/targets/the targets/
comma not needed

> expected to be interleaved.
> 
> In preparation for repairing the autodiscovery region assembly,

s/autodiscovery/auto-discovery/

> introduce a new method for discovering a target position in the
> region interleave.
> 
> cxl_interleave_pos() offers a method to determine a targets position
> by ascending from an endpoint to a root decoder. The calculation starts
> with the endpoints local position and its position in its parents port.
> Traversing towards the root decoder and examining position and ways,
> allows the position to be refined all the way to the root decoder.

Please consider:
It transverses towards the root decoder and examines both position and ways in order to allow the position to be refined all the way to the root decoder.

> 
> This calculation, applied iteratively, yields the correct position:
> 
> position = position * parent_ways + parent_pos;
> 
> ...when you follow these rules:
> 
> Rule #1 - When (parent_ways == region_ways), abort.
> 	  position = parent_position;
> 	  This rule is applied in calc_interleave_pos()
> 
> Rule #2 - Use an index into the target list when finding pos.
> 	  This rule is applied in the helper find_pos_and_ways().
> 
> Include a selftest that exercises this new position calculation against
> every successfully configured user-defined region.
> 
> Fixes: a32320b71f08 ("cxl/region: Add region autodiscovery")
> Reported-by: Dmytro Adamenko <dmytro.adamenko@intel.com>
> Signed-off-by: Alison Schofield <alison.schofield@intel.com>
> ---
>  drivers/cxl/core/region.c | 100 ++++++++++++++++++++++++++++++++++++++
>  1 file changed, 100 insertions(+)
> 
> diff --git a/drivers/cxl/core/region.c b/drivers/cxl/core/region.c
> index 64206fc4d99b..297b9132d5b3 100644
> --- a/drivers/cxl/core/region.c
> +++ b/drivers/cxl/core/region.c
> @@ -1500,6 +1500,91 @@ static int match_switch_decoder_by_range(struct device *dev, void *data)
>  	return range_contains(r1, r2);
>  }
>  
> +/* Find the position of a port in it's parent and the parents ways */
> +static int find_pos_and_ways(struct cxl_port *port, struct range *range,
> +			     int *pos, int *ways)
> +{
> +	struct cxl_switch_decoder *cxlsd;
> +	struct cxl_port *parent;
> +	int child_ways = *ways;
> +	int child_pos = *pos;
> +	struct device *dev;
> +	int index = 0;
> +	int rc = -1;
> +
> +	parent = next_port(port);
> +	if (!parent)
> +		return rc;
> +
> +	dev = device_find_child(&parent->dev, range,
> +				match_switch_decoder_by_range);
> +	if (!dev) {
> +		dev_err(port->uport_dev,
> +			"failed to find decoder mapping %#llx-%#llx\n",
> +			range->start, range->end);
> +		return rc;
> +	}
> +	cxlsd = to_cxl_switch_decoder(dev);
> +	*ways = cxlsd->cxld.interleave_ways;
> +
> +	/* Use the child ways/pos as index to target list */
> +	if (cxlsd->nr_targets > child_ways)
> +		index = child_pos * child_ways;
> +
> +	for (int i = index; i < *ways; i++) {
> +		if (cxlsd->target[i] == port->parent_dport) {
> +			*pos = i;
> +			rc = 0;
> +			break;
> +		}
> +	}
> +	put_device(dev);
> +
> +	return rc;
> +}
> +
> +static int calc_interleave_pos(struct cxl_endpoint_decoder *cxled,
> +			       int region_ways)
> +{
> +	struct cxl_port *iter, *port = cxled_to_port(cxled);
> +	struct cxl_memdev *cxlmd = cxled_to_memdev(cxled);
> +	struct range *range = &cxled->cxld.hpa_range;
> +	int parent_ways = 0;
> +	int parent_pos = 0;
> +	int rc, pos;
> +
> +	/* Initialize pos to its local position */
> +	rc = find_pos_and_ways(port, range, &parent_pos, &parent_ways);
> +	if (rc)
> +		return -ENXIO;
> +
> +	pos = parent_pos;
> +
> +	if (parent_ways == region_ways)
> +		goto out;
> +
> +	/* Iterate up the ancestral tree refining the position */
> +	for (iter = next_port(port); iter; iter = next_port(iter)) {
> +		if (is_cxl_root(iter))
> +			break;
> +
> +		rc = find_pos_and_ways(iter, range, &parent_pos, &parent_ways);
> +		if (rc)
> +			return -ENXIO;
> +
> +		if (parent_ways == region_ways) {
> +			pos = parent_pos;
> +			break;
> +		}
> +		pos = pos * parent_ways + parent_pos;
> +	}
> +out:
> +	dev_dbg(&cxlmd->dev,
> +		"decoder:%s parent:%s port:%s range:%#llx-%#llx pos:%d\n",
> +		dev_name(&cxled->cxld.dev), dev_name(cxlmd->dev.parent),
> +		dev_name(&port->dev), range->start, range->end, pos);
> +
> +	return pos;
>  }
>  
>  static void find_positions(const struct cxl_switch_decoder *cxlsd,
> @@ -1765,6 +1850,21 @@ static int cxl_region_attach(struct cxl_region *cxlr,
>  		.end = p->res->end,
>  	};
>  
> +	if (p->nr_targets != p->interleave_ways)
> +		return 0;
> +
> +	/* Exercise position calculator on user-defined regions */
> +	for (int i = 0; i < p->nr_targets; i++) {
> +		struct cxl_endpoint_decoder *cxled = p->targets[i];
> +		int test_pos;
> +
> +		test_pos = calc_interleave_pos(cxled, p->interleave_ways);
> +		dev_dbg(&cxled->cxld.dev,
> +			"Interleave calc match %s test_pos:%d cxled->pos:%d\n",
> +			(test_pos == cxled->pos) ? "Success" : "Fail",
> +			test_pos, cxled->pos);

Mismatch from selftest does not cause error?

> +	}
> +
>  	return 0;
>  
>  err_decrement:

Re: [PATCH 3/3] cxl/region: Use calc_interleave_pos() with autodiscovered regions

[Dave Jiang]

On 10/5/23 17:43, alison.schofield@intel.com wrote:
> From: Alison Schofield <alison.schofield@intel.com>
> 
> For auto-discovered regions, the driver must assign each target to
> the correct position in the region interleave set.
> 
> cxl_region_sort_targets() uses the kernel sort() function to put the
> targets in relative order. Once the relative ordering is complete,
> positions are assigned based on each targets index in that sorted list.
> 
> The sort() compare function does not consider the child offset into a
> parent port. The sort put all targets of one port ahead of another
> port when an interleave was expected, causing the region assembly to
> fail.
> 
> Replace the relative sort, with calc_interleave_pos() on each target
> in the region target list. That will find the exact position for each
> target based on a walk up the ancestral tree from endpoint to root
> decoder.
> 
> calc_interleave_pos() was introduced in a prior patch, so the work
> here is to use in cxl_region_sort_targets().
> 
> Cleanup the obsolete helper functions from the prior sort().
> 
> Fixes: a32320b71f08 ("cxl/region: Add region autodiscovery")
> Reported-by: Dmytro Adamenko <dmytro.adamenko@intel.com>
> Signed-off-by: Alison Schofield <alison.schofield@intel.com>

Reviewed-by: Dave Jiang <dave.jiang@intel.com>
> ---
>  drivers/cxl/core/region.c | 127 +++++---------------------------------
>  1 file changed, 15 insertions(+), 112 deletions(-)
> 
> diff --git a/drivers/cxl/core/region.c b/drivers/cxl/core/region.c
> index 297b9132d5b3..5a4a70ceb4ce 100644
> --- a/drivers/cxl/core/region.c
> +++ b/drivers/cxl/core/region.c
> @@ -1480,6 +1480,14 @@ static int cxl_region_attach_auto(struct cxl_region *cxlr,
>  	return 0;
>  }
>  
> +static int cmp_interleave_pos(const void *a, const void *b)
> +{
> +	struct cxl_endpoint_decoder *cxled_a = *(typeof(cxled_a) *)a;
> +	struct cxl_endpoint_decoder *cxled_b = *(typeof(cxled_b) *)b;
> +
> +	return cxled_a->pos - cxled_b->pos;
> +}
> +
>  static struct cxl_port *next_port(struct cxl_port *port)
>  {
>  	if (!port->parent_dport)
> @@ -1587,131 +1595,26 @@ static int calc_interleave_pos(struct cxl_endpoint_decoder *cxled,
>  	return pos;
>  }
>  
> -static void find_positions(const struct cxl_switch_decoder *cxlsd,
> -			   const struct cxl_port *iter_a,
> -			   const struct cxl_port *iter_b, int *a_pos,
> -			   int *b_pos)
> -{
> -	int i;
> -
> -	for (i = 0, *a_pos = -1, *b_pos = -1; i < cxlsd->nr_targets; i++) {
> -		if (cxlsd->target[i] == iter_a->parent_dport)
> -			*a_pos = i;
> -		else if (cxlsd->target[i] == iter_b->parent_dport)
> -			*b_pos = i;
> -		if (*a_pos >= 0 && *b_pos >= 0)
> -			break;
> -	}
> -}
> -
> -static int cmp_decode_pos(const void *a, const void *b)
> -{
> -	struct cxl_endpoint_decoder *cxled_a = *(typeof(cxled_a) *)a;
> -	struct cxl_endpoint_decoder *cxled_b = *(typeof(cxled_b) *)b;
> -	struct cxl_memdev *cxlmd_a = cxled_to_memdev(cxled_a);
> -	struct cxl_memdev *cxlmd_b = cxled_to_memdev(cxled_b);
> -	struct cxl_port *port_a = cxled_to_port(cxled_a);
> -	struct cxl_port *port_b = cxled_to_port(cxled_b);
> -	struct cxl_port *iter_a, *iter_b, *port = NULL;
> -	struct cxl_switch_decoder *cxlsd;
> -	struct device *dev;
> -	int a_pos, b_pos;
> -	unsigned int seq;
> -
> -	/* Exit early if any prior sorting failed */
> -	if (cxled_a->pos < 0 || cxled_b->pos < 0)
> -		return 0;
> -
> -	/*
> -	 * Walk up the hierarchy to find a shared port, find the decoder that
> -	 * maps the range, compare the relative position of those dport
> -	 * mappings.
> -	 */
> -	for (iter_a = port_a; iter_a; iter_a = next_port(iter_a)) {
> -		struct cxl_port *next_a, *next_b;
> -
> -		next_a = next_port(iter_a);
> -		if (!next_a)
> -			break;
> -
> -		for (iter_b = port_b; iter_b; iter_b = next_port(iter_b)) {
> -			next_b = next_port(iter_b);
> -			if (next_a != next_b)
> -				continue;
> -			port = next_a;
> -			break;
> -		}
> -
> -		if (port)
> -			break;
> -	}
> -
> -	if (!port) {
> -		dev_err(cxlmd_a->dev.parent,
> -			"failed to find shared port with %s\n",
> -			dev_name(cxlmd_b->dev.parent));
> -		goto err;
> -	}
> -
> -	dev = device_find_child(&port->dev, &cxled_a->cxld.hpa_range,
> -				match_switch_decoder_by_range);
> -	if (!dev) {
> -		struct range *range = &cxled_a->cxld.hpa_range;
> -
> -		dev_err(port->uport_dev,
> -			"failed to find decoder that maps %#llx-%#llx\n",
> -			range->start, range->end);
> -		goto err;
> -	}
> -
> -	cxlsd = to_cxl_switch_decoder(dev);
> -	do {
> -		seq = read_seqbegin(&cxlsd->target_lock);
> -		find_positions(cxlsd, iter_a, iter_b, &a_pos, &b_pos);
> -	} while (read_seqretry(&cxlsd->target_lock, seq));
> -
> -	put_device(dev);
> -
> -	if (a_pos < 0 || b_pos < 0) {
> -		dev_err(port->uport_dev,
> -			"failed to find shared decoder for %s and %s\n",
> -			dev_name(cxlmd_a->dev.parent),
> -			dev_name(cxlmd_b->dev.parent));
> -		goto err;
> -	}
> -
> -	dev_dbg(port->uport_dev, "%s comes %s %s\n",
> -		dev_name(cxlmd_a->dev.parent),
> -		a_pos - b_pos < 0 ? "before" : "after",
> -		dev_name(cxlmd_b->dev.parent));
> -
> -	return a_pos - b_pos;
> -err:
> -	cxled_a->pos = -1;
> -	return 0;
> -}
> -
>  static int cxl_region_sort_targets(struct cxl_region *cxlr)
>  {
>  	struct cxl_region_params *p = &cxlr->params;
>  	int i, rc = 0;
>  
> -	sort(p->targets, p->nr_targets, sizeof(p->targets[0]), cmp_decode_pos,
> -	     NULL);
> -
>  	for (i = 0; i < p->nr_targets; i++) {
>  		struct cxl_endpoint_decoder *cxled = p->targets[i];
>  
> +		cxled->pos = calc_interleave_pos(cxled, p->interleave_ways);
>  		/*
> -		 * Record that sorting failed, but still continue to restore
> -		 * cxled->pos with its ->targets[] position so that follow-on
> -		 * code paths can reliably do p->targets[cxled->pos] to
> -		 * self-reference their entry.
> +		 * Record that sorting failed, but still continue to calc
> +		 * cxled->pos so that follow-on code paths can reliably
> +		 * do p->targets[cxled->pos] to self-reference their entry.
>  		 */
>  		if (cxled->pos < 0)
>  			rc = -ENXIO;
> -		cxled->pos = i;
>  	}
> +	/* Keep the cxlr target list in interleave position order */
> +	sort(p->targets, p->nr_targets, sizeof(p->targets[0]),
> +	     cmp_interleave_pos, NULL);
>  
>  	dev_dbg(&cxlr->dev, "region sort %s\n", rc ? "failed" : "successful");
>  	return rc;

Re: [PATCH 2/3] cxl/region: Calculate a target position in a region interleave

[Alison Schofield]

On Thu, Oct 12, 2023 at 04:49:15PM -0700, Dave Jiang wrote:
> 

Thanks for the review Dave -
I took all the commit msg updates w one exception noted below.

> 
> On 10/5/23 17:43, alison.schofield@intel.com wrote:
> > From: Alison Schofield <alison.schofield@intel.com>
> > 
> > Introduce a calculation that determines a targets position in a region
> > interleave. Perform a selftest of the calculation on user-defined
> > regions.
> > 
> > The region driver users the kernel sort() function to put region
> 
> s/users/uses/
> 
> > targets in relative order. Positions are assigned based on each
> > targets index in that sorted list. That relative sort doesn't
> 
> s/targets/target/

"targets" was wrong because it is the plural noun, but I actually
want the possessive noun "target's", not the singular "target".

> 
> > consider the offset of a port into its parent port causing some
> 
> s/causing/which causes/
> 
> > autodiscovered regions to fail creation. In one failure case,
> 
> s/autodiscovered/auto-discovered/
> 
> > a 2 + 2 config (2 host bridges each with 2 endpoints), the sort
> > put all targets of one port ahead of another port, when they were
> 
> s/put/puts/
> s/targets/the targets/
> comma not needed
> 
> > expected to be interleaved.
> > 
> > In preparation for repairing the autodiscovery region assembly,
> 
> s/autodiscovery/auto-discovery/
> 
> > introduce a new method for discovering a target position in the
> > region interleave.
> > 
> > cxl_interleave_pos() offers a method to determine a targets position
> > by ascending from an endpoint to a root decoder. The calculation starts
> > with the endpoints local position and its position in its parents port.
> > Traversing towards the root decoder and examining position and ways,
> > allows the position to be refined all the way to the root decoder.
> 
> Please consider:
> It transverses towards the root decoder and examines both position and ways in order to allow the position to be refined all the way to the root decoder.
> 
> > 
> > This calculation, applied iteratively, yields the correct position:

..skip..


> > +
> > +	/* Exercise position calculator on user-defined regions */
> > +	for (int i = 0; i < p->nr_targets; i++) {
> > +		struct cxl_endpoint_decoder *cxled = p->targets[i];
> > +		int test_pos;
> > +
> > +		test_pos = calc_interleave_pos(cxled, p->interleave_ways);
> > +		dev_dbg(&cxled->cxld.dev,
> > +			"Interleave calc match %s test_pos:%d cxled->pos:%d\n",
> > +			(test_pos == cxled->pos) ? "Success" : "Fail",
> > +			test_pos, cxled->pos);
> 
> Mismatch from selftest does not cause error?

So I'm doing something weird here and am looking for input on how and
where this check might be inserted, if at all. Here I have inserted
the check at the end of the successful creation of a user-defined region. 
This tells us if the driver would have been able to create the same
region in the auto-discovery path. So for the region created at this
moment, everything is fine.

This is how I've been testing the various interleave flavors of
auto-discovered regions for this patchset. I create the regions as a
user and check that the new calculation finds the interleave positions.

I am imagining a less than finite set of interleave configs and thinking
this may give early warning to configs where the interleave calc fails.

I'm going to post a v2 without any change here and we can continue
this discussion in v2.

Alison

> 
> > +	}
> > +
> >  	return 0;
> >  
> >  err_decrement: