[ofa-general] [PATCHv3] opensm/osm_mesh.c: Reorder switches for lash

[Hal Rosenstock]

The goal of this patch is to change the order of the switches in the array kept
in the lash context from the original order to one in which the switches are
presented in 'odometer order'.

When the main routine in lash is called the switches are in an order that is
likely based on the order that the switches were originally visited by SM 
topology discovery which is some sort of tree walk. All of the analysis up to
this point is independent of the actual order of the switches, but lash will
use that order to enumerate the paths in the fabric and add them to the VL bins.

Odometer order means that the switches are labelled s[X0, ..., Xn-1] and
ordered s[0, ..., 0], s[0, ..., 1], s[0, ..., Ln-1], s[0, .. 1, 0] etc.
The dimensions are also reordered so that the dimension changing the fastest
has the largest length, i.e. Ln >= Ln-1 >= ... >= L1. [All this is modulo
possible end to end reversal but the basic idea is that the longest axis
changes fastest.]

TO INVESTIGATE: Rather than using an additional switches array in
sort_switches whether it can be done in place using p_lash->switches.

Signed-off-by: Robert Pearson <rpearson at systemfabricworks.com>
Signed-off-by: Hal Rosenstock <hal.rosenstock at gmail.com>
---
Changes since v2:
Made completion struct contain context rather than context pointer
Renamed variable from index to comp in sort_switches for better code clarity

Changes since v1:
Made change reentrant FWIW
Added more to patch description
Added memory allocation failure handling

diff --git a/opensm/opensm/osm_mesh.c b/opensm/opensm/osm_mesh.c
index 23fad87..72a9aa9 100644
--- a/opensm/opensm/osm_mesh.c
+++ b/opensm/opensm/osm_mesh.c
@@ -185,6 +185,16 @@ typedef struct _mesh {
 	int dim_order[MAX_DIMENSION];
 } mesh_t;
 
+typedef struct sort_ctx {
+	lash_t *p_lash;
+	mesh_t *mesh;
+} sort_ctx_t;
+
+typedef struct comp {
+	int index;
+	sort_ctx_t ctx;
+} comp_t;
+
 /*
  * poly_alloc
  *
@@ -1272,6 +1282,84 @@ static int reorder_links(lash_t *p_lash, mesh_t *mesh)
 }
 
 /*
+ * compare two switches in a sort
+ */
+static int compare_switches(const void *p1, const void *p2)
+{
+	int i, j, d;
+	const comp_t *cp1 = p1, *cp2 = p2;
+	const sort_ctx_t *ctx = &cp1->ctx;
+	switch_t *s1 = ctx->p_lash->switches[cp1->index];
+	switch_t *s2 = ctx->p_lash->switches[cp2->index];
+
+	for (i = 0; i < ctx->mesh->dimension; i++) {
+		j = ctx->mesh->dim_order[i];
+		d = s1->node->coord[j] - s2->node->coord[j];
+
+		if (d > 0)
+			return 1;
+
+		if (d < 0)
+			return -1;
+	}
+
+	return 0;
+}
+
+/*
+ * sort_switches - reorder switch array
+ */
+static void sort_switches(lash_t *p_lash, mesh_t *mesh)
+{
+	int i, j;
+	int num_switches = p_lash->num_switches;
+	comp_t *comp;
+	int *reverse;
+	switch_t *s;
+	switch_t **switches;
+
+	comp = malloc(num_switches * sizeof(comp_t));
+	reverse = malloc(num_switches * sizeof(int));
+	switches = malloc(num_switches * sizeof(switch_t *));
+	if (!comp || !reverse || !switches) {
+		OSM_LOG(&p_lash->p_osm->log, OSM_LOG_ERROR,
+			"Failed memory allocation - switches not sorted!\n");
+		goto Exit;
+	}
+
+	for (i = 0; i < num_switches; i++) {
+		comp[i].index = i;
+		comp[i].ctx.mesh = mesh;
+		comp[i].ctx.p_lash = p_lash;
+	}
+
+	qsort(comp, num_switches, sizeof(comp_t), compare_switches);
+
+	for (i = 0; i < num_switches; i++)
+		reverse[comp[i].index] = i;
+
+	for (i = 0; i < num_switches; i++) {
+		s = p_lash->switches[comp[i].index];
+		switches[i] = s;
+		s->id = i;
+		for (j = 0; j < s->node->num_links; j++)
+			s->node->links[j]->switch_id =
+				reverse[s->node->links[j]->switch_id];
+	}
+
+	for (i = 0; i < num_switches; i++)
+		p_lash->switches[i] = switches[i];
+
+Exit:
+	if (switches)
+		free(switches);
+	if (comp)
+		free(comp);
+	if (reverse)
+		free(reverse);
+}
+
+/*
  * osm_mesh_delete - free per mesh resources
  */
 static void mesh_delete(mesh_t *mesh)
@@ -1470,6 +1558,8 @@ int osm_do_mesh_analysis(lash_t *p_lash)
 		if (reorder_links(p_lash, mesh))
 			goto err;
 
+		sort_switches(p_lash, mesh);
+
 		p = buf;
 		p += sprintf(p, "found ");
 		for (i = 0; i < mesh->dimension; i++)