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

[Hal Rosenstock]

This patch changes 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.]

Signed-off-by: Robert Pearson <rpearson at systemfabricworks.com>
Signed-off-by: Hal Rosenstock <hal.rosenstock at gmail.com>
---
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..dce2ea1 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,87 @@ static int reorder_links(lash_t *p_lash, mesh_t *mesh)
 }
 
 /*
+ * compare two switches in a sort
+ */
+static int compare_switch(const void *p1, const void *p2)
+{
+	int i, j, d;
+	const comp_t *cp1 = p1, *cp2 = p2;
+	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;
+	sort_ctx_t sort_ctx;
+	comp_t *index;
+	int *reverse;
+	switch_t *s;
+	switch_t **switches;
+
+	index = malloc(num_switches * sizeof(comp_t));
+	reverse = malloc(num_switches * sizeof(int));
+	switches = malloc(num_switches * sizeof(switch_t *));
+	if (!index || !reverse || !switches) {
+		OSM_LOG(&p_lash->p_osm->log, OSM_LOG_ERROR,
+			"Failed memory allocation - switches not sorted!\n");
+		goto Exit;
+	}
+
+	sort_ctx.mesh = mesh;
+	sort_ctx.p_lash = p_lash;
+	
+	for (i = 0; i < num_switches; i++) {
+		index[i].index = i;
+		index[i].ctx = &sort_ctx;
+	}
+
+	qsort(index, num_switches, sizeof(comp_t), compare_switch);
+
+	for (i = 0; i < num_switches; i++)
+		reverse[index[i].index] = i;
+
+	for (i = 0; i < num_switches; i++) {
+		s = p_lash->switches[index[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 (index)
+		free(index);
+	if (reverse)
+		free(reverse);
+}
+
+/*
  * osm_mesh_delete - free per mesh resources
  */
 static void mesh_delete(mesh_t *mesh)
@@ -1470,6 +1561,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++)