1 /*
2 * Copyright (c) 2008-2009 Voltaire, Inc. All rights reserved.
3 * Copyright (c) 2008,2009 System Fabric Works, Inc. All rights reserved.
4 *
5 * This software is available to you under a choice of one of two
6 * licenses. You may choose to be licensed under the terms of the GNU
7 * General Public License (GPL) Version 2, available from the file
8 * COPYING in the main directory of this source tree, or the
9 * OpenIB.org BSD license below:
10 *
11 * Redistribution and use in source and binary forms, with or
12 * without modification, are permitted provided that the following
13 * conditions are met:
14 *
15 * - Redistributions of source code must retain the above
16 * copyright notice, this list of conditions and the following
17 * disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials
22 * provided with the distribution.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
28 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
29 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
30 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
31 * SOFTWARE.
32 *
33 */
34
35 /*
36 * Abstract:
37 * routines to analyze certain meshes
38 */
39
40 #if HAVE_CONFIG_H
41 # include <config.h>
42 #endif /* HAVE_CONFIG_H */
43
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <opensm/osm_file_ids.h>
47 #define FILE_ID OSM_FILE_MESH_C
48 #include <opensm/osm_switch.h>
49 #include <opensm/osm_opensm.h>
50 #include <opensm/osm_log.h>
51 #include <opensm/osm_mesh.h>
52 #include <opensm/osm_ucast_lash.h>
53
54 #define MAX_DEGREE (8)
55 #define MAX_DIMENSION (8)
56 #define LARGE (0x7fffffff)
57
58 /*
59 * characteristic polynomials for selected 1d through 8d tori
60 */
61 static const struct mesh_info {
62 int dimension; /* dimension of the torus */
63 int size[MAX_DIMENSION]; /* size of the torus */
64 unsigned int degree; /* degree of polynomial */
65 int poly[MAX_DEGREE+1]; /* polynomial */
66 } mesh_info[] = {
67 {0, {0}, 0, {0}, },
68
69 {1, {2}, 1, {0, -1}, },
70 {1, {3}, 2, {-1, 0, 1}, },
71 {1, {5}, 2, {-9, 0, 1}, },
72 {1, {6}, 2, {-36, 0, 1}, },
73
74 {2, {2, 2}, 2, {-4, 0, 1}, },
75 {2, {3, 2}, 3, {8, 9, 0, -1}, },
76 {2, {5, 2}, 3, {24, 17, 0, -1}, },
77 {2, {6, 2}, 3, {32, 24, 0, -1}, },
78 {2, {3, 3}, 4, {-15, -32, -18, 0, 1}, },
79 {2, {5, 3}, 4, {-39, -64, -26, 0, 1}, },
80 {2, {6, 3}, 4, {-48, -80, -33, 0, 1}, },
81 {2, {5, 5}, 4, {-63, -96, -34, 0, 1}, },
82 {2, {6, 5}, 4, {-48, -112, -41, 0, 1}, },
83 {2, {6, 6}, 4, {0, -128, -48, 0, 1}, },
84
85 {3, {2, 2, 2}, 3, {16, 12, 0, -1}, },
86 {3, {3, 2, 2}, 4, {-28, -48, -21, 0, 1}, },
87 {3, {5, 2, 2}, 4, {-60, -80, -29, 0, 1}, },
88 {3, {6, 2, 2}, 4, {-64, -96, -36, 0, 1}, },
89 {3, {3, 3, 2}, 5, {48, 127, 112, 34, 0, -1}, },
90 {3, {5, 3, 2}, 5, {96, 215, 160, 42, 0, -1}, },
91 {3, {6, 3, 2}, 5, {96, 232, 184, 49, 0, -1}, },
92 {3, {5, 5, 2}, 5, {144, 303, 208, 50, 0, -1}, },
93 {3, {6, 5, 2}, 5, {96, 296, 232, 57, 0, -1}, },
94 {3, {6, 6, 2}, 5, {0, 256, 256, 64, 0, -1}, },
95 {3, {3, 3, 3}, 6, {-81, -288, -381, -224, -51, 0, 1}, },
96 {3, {5, 3, 3}, 6, {-153, -480, -557, -288, -59, 0, 1}, },
97 {3, {6, 3, 3}, 6, {-144, -480, -591, -320, -66, 0, 1}, },
98 {3, {5, 5, 3}, 6, {-225, -672, -733, -352, -67, 0, 1}, },
99 {3, {6, 5, 3}, 6, {-144, -576, -743, -384, -74, 0, 1}, },
100 {3, {6, 6, 3}, 6, {0, -384, -720, -416, -81, 0, 1}, },
101 {3, {5, 5, 5}, 6, {-297, -864, -909, -416, -75, 0, 1}, },
102 {3, {6, 5, 5}, 6, {-144, -672, -895, -448, -82, 0, 1}, },
103 {3, {6, 6, 5}, 6, {0, -384, -848, -480, -89, 0, 1}, },
104 {3, {6, 6, 6}, 6, {0, 0, -768, -512, -96, 0, 1}, },
105
106 {4, {2, 2, 2, 2}, 4, {-48, -64, -24, 0, 1}, },
107 {4, {3, 2, 2, 2}, 5, {80, 180, 136, 37, 0, -1}, },
108 {4, {5, 2, 2, 2}, 5, {144, 276, 184, 45, 0, -1}, },
109 {4, {6, 2, 2, 2}, 5, {128, 288, 208, 52, 0, -1}, },
110 {4, {3, 3, 2, 2}, 6, {-132, -416, -487, -256, -54, 0, 1}, },
111 {4, {5, 3, 2, 2}, 6, {-228, -640, -671, -320, -62, 0, 1}, },
112 {4, {6, 3, 2, 2}, 6, {-192, -608, -700, -352, -69, 0, 1}, },
113 {4, {5, 5, 2, 2}, 6, {-324, -864, -855, -384, -70, 0, 1}, },
114 {4, {6, 5, 2, 2}, 6, {-192, -736, -860, -416, -77, 0, 1}, },
115 {4, {6, 6, 2, 2}, 6, {0, -512, -832, -448, -84, 0, 1}, },
116 {4, {3, 3, 3, 2}, 7, {216, 873, 1392, 1101, 440, 75, 0, -1}, },
117 {4, {5, 3, 3, 2}, 7, {360, 1329, 1936, 1405, 520, 83, 0, -1}, },
118 {4, {6, 3, 3, 2}, 7, {288, 1176, 1872, 1455, 560, 90, 0, -1}, },
119 {4, {5, 5, 3, 2}, 7, {504, 1785, 2480, 1709, 600, 91, 0, -1}, },
120 {4, {6, 5, 3, 2}, 7, {288, 1368, 2272, 1735, 640, 98, 0, -1}, },
121 {4, {6, 6, 3, 2}, 7, {0, 768, 1920, 1728, 680, 105, 0, -1}, },
122 {4, {5, 5, 5, 2}, 7, {648, 2241, 3024, 2013, 680, 99, 0, -1}, },
123 {4, {6, 5, 5, 2}, 7, {288, 1560, 2672, 2015, 720, 106, 0, -1}, },
124 {4, {6, 6, 5, 2}, 7, {0, 768, 2176, 1984, 760, 113, 0, -1}, },
125 {4, {6, 6, 6, 2}, 7, {0, 0, 1536, 1920, 800, 120, 0, -1}, },
126 {4, {3, 3, 3, 3}, 8, {-351, -1728, -3492, -3712, -2202, -704, -100, 0, 1}, },
127 {4, {5, 3, 3, 3}, 8, {-567, -2592, -4860, -4800, -2658, -800, -108, 0, 1}, },
128 {4, {6, 3, 3, 3}, 8, {-432, -2160, -4401, -4672, -2733, -848, -115, 0, 1}, },
129 {4, {5, 5, 3, 3}, 8, {-783, -3456, -6228, -5888, -3114, -896, -116, 0, 1}, },
130 {4, {6, 5, 3, 3}, 8, {-432, -2448, -5241, -5568, -3165, -944, -123, 0, 1}, },
131 {4, {6, 6, 3, 3}, 8, {0, -1152, -3888, -5056, -3183, -992, -130, 0, 1}, },
132 {4, {5, 5, 5, 3}, 8, {-999, -4320, -7596, -6976, -3570, -992, -124, 0, 1}, },
133 {4, {6, 5, 5, 3}, 8, {-432, -2736, -6081, -6464, -3597, -1040, -131, 0, 1}, },
134 {4, {6, 6, 5, 3}, 8, {0, -1152, -4272, -5760, -3591, -1088, -138, 0, 1}, },
135 {4, {6, 6, 6, 3}, 8, {0, 0, -2304, -4864, -3552, -1136, -145, 0, 1}, },
136
137 {5, {2, 2, 2, 2, 2}, 5, {128, 240, 160, 40, 0, -1}, },
138 {5, {3, 2, 2, 2, 2}, 6, {-208, -576, -600, -288, -57, 0, 1}, },
139 {5, {5, 2, 2, 2, 2}, 6, {-336, -832, -792, -352, -65, 0, 1}, },
140 {5, {6, 2, 2, 2, 2}, 6, {-256, -768, -816, -384, -72, 0, 1}, },
141 {5, {3, 3, 2, 2, 2}, 7, {336, 1228, 1776, 1287, 480, 78, 0, -1}, },
142 {5, {5, 3, 2, 2, 2}, 7, {528, 1772, 2368, 1599, 560, 86, 0, -1}, },
143 {5, {6, 3, 2, 2, 2}, 7, {384, 1504, 2256, 1644, 600, 93, 0, -1}, },
144 {5, {5, 5, 2, 2, 2}, 7, {720, 2316, 2960, 1911, 640, 94, 0, -1}, },
145 {5, {6, 5, 2, 2, 2}, 7, {384, 1760, 2704, 1932, 680, 101, 0, -1}, },
146 {5, {6, 6, 2, 2, 2}, 7, {0, 1024, 2304, 1920, 720, 108, 0, -1}, },
147 {5, {3, 3, 3, 2, 2}, 8, {-540, -2448, -4557, -4480, -2481, -752, -103, 0, 1}, },
148 {5, {5, 3, 3, 2, 2}, 8, {-828, -3504, -6101, -5632, -2945, -848, -111, 0, 1}, },
149 {5, {6, 3, 3, 2, 2}, 8, {-576, -2784, -5412, -5440, -3015, -896, -118, 0, 1}, },
150 {5, {5, 5, 3, 2, 2}, 8, {-1116, -4560, -7645, -6784, -3409, -944, -119, 0, 1}, },
151 {5, {6, 5, 3, 2, 2}, 8, {-576, -3168, -6404, -6400, -3455, -992, -126, 0, 1}, },
152 {5, {6, 6, 3, 2, 2}, 8, {0, -1536, -4800, -5824, -3468, -1040, -133, 0, 1}, },
153 {5, {5, 5, 5, 2, 2}, 8, {-1404, -5616, -9189, -7936, -3873, -1040, -127, 0, 1}, },
154 {5, {6, 5, 5, 2, 2}, 8, {-576, -3552, -7396, -7360, -3895, -1088, -134, 0, 1}, },
155 {5, {6, 6, 5, 2, 2}, 8, {0, -1536, -5312, -6592, -3884, -1136, -141, 0, 1}, },
156 {5, {6, 6, 6, 2, 2}, 8, {0, 0, -3072, -5632, -3840, -1184, -148, 0, 1}, },
157
158 {6, {2, 2, 2, 2, 2, 2}, 6, {-320, -768, -720, -320, -60, 0, 1}, },
159 {6, {3, 2, 2, 2, 2, 2}, 7, {512, 1680, 2208, 1480, 520, 81, 0, -1}, },
160 {6, {5, 2, 2, 2, 2, 2}, 7, {768, 2320, 2848, 1800, 600, 89, 0, -1}, },
161 {6, {6, 2, 2, 2, 2, 2}, 7, {512, 1920, 2688, 1840, 640, 96, 0, -1}, },
162 {6, {3, 3, 2, 2, 2, 2}, 8, {-816, -3392, -5816, -5312, -2767, -800, -106, 0, 1}, },
163 {6, {5, 3, 2, 2, 2, 2}, 8, {-1200, -4672, -7544, -6528, -3239, -896, -114, 0, 1}, },
164 {6, {6, 3, 2, 2, 2, 2}, 8, {-768, -3584, -6608, -6272, -3304, -944, -121, 0, 1}, },
165 {6, {5, 5, 2, 2, 2, 2}, 8, {-1584, -5952, -9272, -7744, -3711, -992, -122, 0, 1}, },
166 {6, {6, 5, 2, 2, 2, 2}, 8, {-768, -4096, -7760, -7296, -3752, -1040, -129, 0, 1}, },
167 {6, {6, 6, 2, 2, 2, 2}, 8, {0, -2048, -5888, -6656, -3760, -1088, -136, 0, 1}, },
168
169 {7, {2, 2, 2, 2, 2, 2, 2}, 7, {768, 2240, 2688, 1680, 560, 84, 0, -1}, },
170 {7, {3, 2, 2, 2, 2, 2, 2}, 8, {-1216, -4608, -7280, -6208, -3060, -848, -109, 0, 1}, },
171 {7, {5, 2, 2, 2, 2, 2, 2}, 8, {-1728, -6144, -9200, -7488, -3540, -944, -117, 0, 1}, },
172 {7, {6, 2, 2, 2, 2, 2, 2}, 8, {-1024, -4608, -8000, -7168, -3600, -992, -124, 0, 1}, },
173
174 {8, {2, 2, 2, 2, 2, 2, 2, 2}, 8, {-1792, -6144, -8960, -7168, -3360, -896, -112, 0, 1}, },
175
176 /*
177 * mesh errors
178 */
179 {2, {6, 6}, 4, {-192, -256, -80, 0, 1}, },
180
181 {-1, {0,}, 0, {0, }, },
182 };
183
184 /*
185 * per fabric mesh info
186 */
187 typedef struct _mesh {
188 int num_class; /* number of switch classes */
189 int *class_type; /* index of first switch found for each class */
190 int *class_count; /* population of each class */
191 int dimension; /* mesh dimension */
192 int *size; /* an array to hold size of mesh */
193 int dim_order[MAX_DIMENSION];
194 } mesh_t;
195
196 typedef struct sort_ctx {
197 lash_t *p_lash;
198 mesh_t *mesh;
199 } sort_ctx_t;
200
201 typedef struct comp {
202 int index;
203 sort_ctx_t ctx;
204 } comp_t;
205
206 /*
207 * poly_alloc
208 *
209 * allocate a polynomial of degree n
210 */
poly_alloc(lash_t * p_lash,int n)211 static int *poly_alloc(lash_t *p_lash, int n)
212 {
213 osm_log_t *p_log = &p_lash->p_osm->log;
214 int *p;
215
216 if (!(p = calloc(n+1, sizeof(int))))
217 OSM_LOG(p_log, OSM_LOG_ERROR,
218 "Failed allocating poly - out of memory\n");
219
220 return p;
221 }
222
223 /*
224 * print a polynomial
225 */
poly_print(int n,int * coeff)226 static char *poly_print(int n, int *coeff)
227 {
228 static char str[(MAX_DEGREE+1)*20];
229 char *p = str;
230 int i;
231 int first = 1;
232 int t;
233 int sign;
234
235 str[0] = 0;
236
237 for (i = 0; i <= n; i++) {
238 if (!coeff[i])
239 continue;
240
241 if (coeff[i] < 0) {
242 sign = 1;
243 t = -coeff[i];
244 } else {
245 sign = 0;
246 t = coeff[i];
247 }
248
249 p += sprintf(p, "%s", sign? "-" : (first? "" : "+"));
250 first = 0;
251
252 if (t != 1 || i == 0)
253 p += sprintf(p, "%d", t);
254
255 if (i)
256 p += sprintf(p, "x");
257 if (i > 1)
258 p += sprintf(p, "^%d", i);
259 }
260
261 return str;
262 }
263
264 /*
265 * poly_diff
266 *
267 * return a nonzero value if polynomials differ else 0
268 */
poly_diff(unsigned int n,const int * p,switch_t * s)269 static int poly_diff(unsigned int n, const int *p, switch_t *s)
270 {
271 if (s->node->num_links != n)
272 return 1;
273
274 return memcmp(p, s->node->poly, n*sizeof(int));
275 }
276
277 /*
278 * m_free
279 *
280 * free a square matrix of rank l
281 */
m_free(int ** m,int l)282 static void m_free(int **m, int l)
283 {
284 int i;
285
286 if (m) {
287 for (i = 0; i < l; i++) {
288 if (m[i])
289 free(m[i]);
290 }
291 free(m);
292 }
293 }
294
295 /*
296 * m_alloc
297 *
298 * allocate a square matrix of rank l
299 */
m_alloc(lash_t * p_lash,int l)300 static int **m_alloc(lash_t *p_lash, int l)
301 {
302 osm_log_t *p_log = &p_lash->p_osm->log;
303 int i;
304 int **m = NULL;
305
306 do {
307 if (!(m = calloc(l, sizeof(int *))))
308 break;
309
310 for (i = 0; i < l; i++) {
311 if (!(m[i] = calloc(l, sizeof(int))))
312 break;
313 }
314 if (i != l)
315 break;
316
317 return m;
318 } while (0);
319
320 OSM_LOG(p_log, OSM_LOG_ERROR,
321 "Failed allocating matrix - out of memory\n");
322
323 m_free(m, l);
324 return NULL;
325 }
326
327 /*
328 * pm_free
329 *
330 * free a square matrix of rank l of polynomials
331 */
pm_free(int *** m,int l)332 static void pm_free(int ***m, int l)
333 {
334 int i, j;
335
336 if (m) {
337 for (i = 0; i < l; i++) {
338 if (m[i]) {
339 for (j = 0; j < l; j++) {
340 if (m[i][j])
341 free(m[i][j]);
342 }
343 free(m[i]);
344 }
345 }
346 free(m);
347 }
348 }
349
350 /*
351 * pm_alloc
352 *
353 * allocate a square matrix of rank l of polynomials of degree n
354 */
pm_alloc(lash_t * p_lash,int l,int n)355 static int ***pm_alloc(lash_t *p_lash, int l, int n)
356 {
357 osm_log_t *p_log = &p_lash->p_osm->log;
358 int i, j;
359 int ***m = NULL;
360
361 do {
362 if (!(m = calloc(l, sizeof(int **))))
363 break;
364
365 for (i = 0; i < l; i++) {
366 if (!(m[i] = calloc(l, sizeof(int *))))
367 break;
368
369 for (j = 0; j < l; j++) {
370 if (!(m[i][j] = calloc(n+1, sizeof(int))))
371 break;
372 }
373 if (j != l)
374 break;
375 }
376 if (i != l)
377 break;
378
379 return m;
380 } while (0);
381
382 OSM_LOG(p_log, OSM_LOG_ERROR,
383 "Failed allocating matrix - out of memory\n");
384
385 pm_free(m, l);
386 return NULL;
387 }
388
389 static int determinant(lash_t *p_lash, int n, int rank, int ***m, int *p);
390
391 /*
392 * sub_determinant
393 *
394 * compute the determinant of a submatrix of matrix of rank l of polynomials of degree n
395 * with row and col removed in poly. caller must free poly
396 */
sub_determinant(lash_t * p_lash,int n,int l,int row,int col,int *** matrix,int ** poly)397 static int sub_determinant(lash_t *p_lash, int n, int l, int row, int col,
398 int ***matrix, int **poly)
399 {
400 int ret = -1;
401 int ***m = NULL;
402 int *p = NULL;
403 int i, j, k, x, y;
404 int rank = l - 1;
405
406 do {
407 if (!(p = poly_alloc(p_lash, n))) {
408 break;
409 }
410
411 if (rank <= 0) {
412 p[0] = 1;
413 ret = 0;
414 break;
415 }
416
417 if (!(m = pm_alloc(p_lash, rank, n))) {
418 free(p);
419 p = NULL;
420 break;
421 }
422
423 x = 0;
424 for (i = 0; i < l; i++) {
425 if (i == row)
426 continue;
427
428 y = 0;
429 for (j = 0; j < l; j++) {
430 if (j == col)
431 continue;
432
433 for (k = 0; k <= n; k++)
434 m[x][y][k] = matrix[i][j][k];
435
436 y++;
437 }
438 x++;
439 }
440
441 if (determinant(p_lash, n, rank, m, p)) {
442 free(p);
443 p = NULL;
444 break;
445 }
446
447 ret = 0;
448 } while (0);
449
450 pm_free(m, rank);
451 *poly = p;
452 return ret;
453 }
454
455 /*
456 * determinant
457 *
458 * compute the determinant of matrix m of rank of polynomials of degree deg
459 * and add the result to polynomial p allocated by caller
460 */
determinant(lash_t * p_lash,int deg,int rank,int *** m,int * p)461 static int determinant(lash_t *p_lash, int deg, int rank, int ***m, int *p)
462 {
463 int i, j, k;
464 int *q;
465 int sign = 1;
466
467 /*
468 * handle simple case of 1x1 matrix
469 */
470 if (rank == 1) {
471 for (i = 0; i <= deg; i++)
472 p[i] += m[0][0][i];
473 }
474
475 /*
476 * handle simple case of 2x2 matrix
477 */
478 else if (rank == 2) {
479 for (i = 0; i <= deg; i++) {
480 if (m[0][0][i] == 0)
481 continue;
482
483 for (j = 0; j <= deg; j++) {
484 if (m[1][1][j] == 0)
485 continue;
486
487 p[i+j] += m[0][0][i]*m[1][1][j];
488 }
489 }
490
491 for (i = 0; i <= deg; i++) {
492 if (m[0][1][i] == 0)
493 continue;
494
495 for (j = 0; j <= deg; j++) {
496 if (m[1][0][j] == 0)
497 continue;
498
499 p[i+j] -= m[0][1][i]*m[1][0][j];
500 }
501 }
502 }
503
504 /*
505 * handle the general case
506 */
507 else {
508 for (i = 0; i < rank; i++) {
509 if (sub_determinant(p_lash, deg, rank, 0, i, m, &q))
510 return -1;
511
512 for (j = 0; j <= deg; j++) {
513 if (m[0][i][j] == 0)
514 continue;
515
516 for (k = 0; k <= deg; k++) {
517 if (q[k] == 0)
518 continue;
519
520 p[j+k] += sign*m[0][i][j]*q[k];
521 }
522 }
523
524 free(q);
525 sign = -sign;
526 }
527 }
528
529 return 0;
530 }
531
532 /*
533 * char_poly
534 *
535 * compute the characteristic polynomial of matrix of rank
536 * by computing the determinant of m-x*I and return in poly
537 * as an array. caller must free poly
538 */
char_poly(lash_t * p_lash,int rank,int ** matrix,int ** poly)539 static int char_poly(lash_t *p_lash, int rank, int **matrix, int **poly)
540 {
541 osm_log_t *p_log = &p_lash->p_osm->log;
542 int ret = -1;
543 int i, j;
544 int ***m = NULL;
545 int *p = NULL;
546 int deg = rank;
547
548 OSM_LOG_ENTER(p_log);
549
550 do {
551 if (!matrix)
552 break;
553
554 if (!(p = poly_alloc(p_lash, deg)))
555 break;
556
557 if (!(m = pm_alloc(p_lash, rank, deg))) {
558 free(p);
559 p = NULL;
560 break;
561 }
562
563 for (i = 0; i < rank; i++) {
564 for (j = 0; j < rank; j++) {
565 m[i][j][0] = matrix[i][j];
566 }
567 m[i][i][1] = -1;
568 }
569
570 if (determinant(p_lash, deg, rank, m, p)) {
571 free(p);
572 p = NULL;
573 break;
574 }
575
576 ret = 0;
577 } while (0);
578
579 pm_free(m, rank);
580 *poly = p;
581
582 OSM_LOG_EXIT(p_log);
583 return ret;
584 }
585
586 /*
587 * get_switch_metric
588 *
589 * compute the matrix of minimum distances between each of
590 * the adjacent switch nodes to sw along paths
591 * that do not go through sw. do calculation by
592 * relaxation method
593 * allocate space for the matrix and save in node_t structure
594 */
get_switch_metric(lash_t * p_lash,int sw)595 static int get_switch_metric(lash_t *p_lash, int sw)
596 {
597 osm_log_t *p_log = &p_lash->p_osm->log;
598 int ret = -1;
599 unsigned int i, j, change;
600 int sw1, sw2, sw3;
601 switch_t *s = p_lash->switches[sw];
602 switch_t *s1, *s2, *s3;
603 int **m;
604 mesh_node_t *node = s->node;
605 unsigned int num_links = node->num_links;
606
607 OSM_LOG_ENTER(p_log);
608
609 do {
610 if (!(m = m_alloc(p_lash, num_links)))
611 break;
612
613 for (i = 0; i < num_links; i++) {
614 sw1 = node->links[i]->switch_id;
615 s1 = p_lash->switches[sw1];
616
617 /* make all distances big except s1 to itself */
618 for (sw2 = 0; sw2 < p_lash->num_switches; sw2++)
619 p_lash->switches[sw2]->node->temp = LARGE;
620
621 s1->node->temp = 0;
622
623 do {
624 change = 0;
625
626 for (sw2 = 0; sw2 < p_lash->num_switches; sw2++) {
627 s2 = p_lash->switches[sw2];
628 if (s2->node->temp == LARGE)
629 continue;
630 for (j = 0; j < s2->node->num_links; j++) {
631 sw3 = s2->node->links[j]->switch_id;
632 s3 = p_lash->switches[sw3];
633
634 if (sw3 == sw)
635 continue;
636
637 if ((s2->node->temp + 1) < s3->node->temp) {
638 s3->node->temp = s2->node->temp + 1;
639 change++;
640 }
641 }
642 }
643 } while (change);
644
645 for (j = 0; j < num_links; j++) {
646 sw2 = node->links[j]->switch_id;
647 s2 = p_lash->switches[sw2];
648 m[i][j] = s2->node->temp;
649 }
650 }
651
652 if (char_poly(p_lash, num_links, m, &node->poly)) {
653 m_free(m, num_links);
654 m = NULL;
655 break;
656 }
657
658 ret = 0;
659 } while (0);
660
661 node->matrix = m;
662
663 OSM_LOG_EXIT(p_log);
664 return ret;
665 }
666
667 /*
668 * classify_switch
669 *
670 * add switch to histogram of switch types
671 * we keep a reference to the first switch
672 * found of each type as an exemplar
673 */
classify_switch(lash_t * p_lash,mesh_t * mesh,int sw)674 static void classify_switch(lash_t *p_lash, mesh_t *mesh, int sw)
675 {
676 osm_log_t *p_log = &p_lash->p_osm->log;
677 int i;
678 switch_t *s = p_lash->switches[sw];
679 switch_t *s1;
680
681 OSM_LOG_ENTER(p_log);
682
683 if (!s->node->poly)
684 goto done;
685
686 for (i = 0; i < mesh->num_class; i++) {
687 s1 = p_lash->switches[mesh->class_type[i]];
688
689 if (poly_diff(s->node->num_links, s->node->poly, s1))
690 continue;
691
692 mesh->class_count[i]++;
693 goto done;
694 }
695
696 mesh->class_type[mesh->num_class] = sw;
697 mesh->class_count[mesh->num_class] = 1;
698 mesh->num_class++;
699
700 done:
701 OSM_LOG_EXIT(p_log);
702 }
703
704 /*
705 * classify_mesh_type
706 *
707 * try to look up node polynomial in table
708 */
classify_mesh_type(lash_t * p_lash,int sw)709 static void classify_mesh_type(lash_t *p_lash, int sw)
710 {
711 osm_log_t *p_log = &p_lash->p_osm->log;
712 int i;
713 switch_t *s = p_lash->switches[sw];
714 const struct mesh_info *t;
715
716 OSM_LOG_ENTER(p_log);
717
718 if (!s->node->poly)
719 goto done;
720
721 for (i = 1; (t = &mesh_info[i])->dimension != -1; i++) {
722 if (poly_diff(t->degree, t->poly, s))
723 continue;
724
725 s->node->type = i;
726 s->node->dimension = t->dimension;
727 OSM_LOG_EXIT(p_log);
728 return;
729 }
730
731 done:
732 s->node->type = 0;
733 OSM_LOG_EXIT(p_log);
734 return;
735 }
736
737 /*
738 * remove_edges
739 *
740 * remove type from nodes that have fewer links
741 * than adjacent nodes
742 */
remove_edges(lash_t * p_lash)743 static void remove_edges(lash_t *p_lash)
744 {
745 osm_log_t *p_log = &p_lash->p_osm->log;
746 int sw;
747 mesh_node_t *n, *nn;
748 unsigned i;
749
750 OSM_LOG_ENTER(p_log);
751
752 for (sw = 0; sw < p_lash->num_switches; sw++) {
753 n = p_lash->switches[sw]->node;
754 if (!n->type)
755 continue;
756
757 for (i = 0; i < n->num_links; i++) {
758 nn = p_lash->switches[n->links[i]->switch_id]->node;
759
760 if (nn->num_links > n->num_links) {
761 OSM_LOG(p_log, OSM_LOG_DEBUG,
762 "removed edge switch %s\n",
763 p_lash->switches[sw]->p_sw->p_node->print_desc);
764 n->type = -1;
765 break;
766 }
767 }
768 }
769
770 OSM_LOG_EXIT(p_log);
771 }
772
773 /*
774 * get_local_geometry
775 *
776 * analyze the local geometry around each switch
777 */
get_local_geometry(lash_t * p_lash,mesh_t * mesh)778 static int get_local_geometry(lash_t *p_lash, mesh_t *mesh)
779 {
780 osm_log_t *p_log = &p_lash->p_osm->log;
781 int sw;
782 int status = 0;
783
784 OSM_LOG_ENTER(p_log);
785
786 for (sw = 0; sw < p_lash->num_switches; sw++) {
787 /*
788 * skip switches with more links than MAX_DEGREE
789 * since they will never match a known case
790 */
791 if (p_lash->switches[sw]->node->num_links > MAX_DEGREE)
792 continue;
793
794 if (get_switch_metric(p_lash, sw)) {
795 status = -1;
796 goto Exit;
797 }
798 classify_mesh_type(p_lash, sw);
799 }
800
801 remove_edges(p_lash);
802
803 for (sw = 0; sw < p_lash->num_switches; sw++) {
804 if (p_lash->switches[sw]->node->type < 0)
805 continue;
806 classify_switch(p_lash, mesh, sw);
807 }
808
809 Exit:
810 OSM_LOG_EXIT(p_log);
811 return status;
812 }
813
print_axis(lash_t * p_lash,char * p,int sw,int port)814 static void print_axis(lash_t *p_lash, char *p, int sw, int port)
815 {
816 mesh_node_t *node = p_lash->switches[sw]->node;
817 char *name = p_lash->switches[sw]->p_sw->p_node->print_desc;
818 int c = node->axes[port];
819
820 p += sprintf(p, "%s[%d] = ", name, port);
821 if (c)
822 p += sprintf(p, "%s%c -> ", ((c - 1) & 1) ? "-" : "+", 'X' + (c - 1)/2);
823 else
824 p += sprintf(p, "N/A -> ");
825 p += sprintf(p, "%s\n",
826 p_lash->switches[node->links[port]->switch_id]->p_sw->p_node->print_desc);
827 }
828
829 /*
830 * seed_axes
831 *
832 * assign axes to the links of the seed switch
833 * assumes switch is of type cartesian mesh
834 * axes are numbered 1 to n i.e. +x => 1 -x => 2 etc.
835 * this assumes that if all distances are 2 that
836 * an axis has only 2 nodes so +A and -A collapse to +A
837 */
seed_axes(lash_t * p_lash,int sw)838 static void seed_axes(lash_t *p_lash, int sw)
839 {
840 osm_log_t *p_log = &p_lash->p_osm->log;
841 mesh_node_t *node = p_lash->switches[sw]->node;
842 int n = node->num_links;
843 int i, j, c;
844
845 OSM_LOG_ENTER(p_log);
846
847 if (!node->matrix || !node->dimension)
848 goto done;
849
850 for (c = 1; c <= 2*node->dimension; c++) {
851 /*
852 * find the next unassigned axis
853 */
854 for (i = 0; i < n; i++) {
855 if (!node->axes[i])
856 break;
857 }
858
859 node->axes[i] = c++;
860
861 /*
862 * find the matching opposite direction
863 */
864 for (j = 0; j < n; j++) {
865 if (node->axes[j] || j == i)
866 continue;
867
868 if (node->matrix[i][j] != 2)
869 break;
870 }
871
872 if (j != n) {
873 node->axes[j] = c;
874 }
875 }
876
877 if (OSM_LOG_IS_ACTIVE_V2(p_log, OSM_LOG_DEBUG)) {
878 char buf[256], *p;
879
880 for (i = 0; i < n; i++) {
881 p = buf;
882 print_axis(p_lash, p, sw, i);
883 OSM_LOG(p_log, OSM_LOG_DEBUG, "%s", buf);
884 }
885 }
886
887 done:
888 OSM_LOG_EXIT(p_log);
889 }
890
891 /*
892 * opposite
893 *
894 * compute the opposite of axis for switch
895 */
opposite(switch_t * s,int axis)896 static inline int opposite(switch_t *s, int axis)
897 {
898 unsigned i, j;
899 int negaxis = 1 + (1 ^ (axis - 1));
900
901 if (!s->node->matrix)
902 return 0;
903
904 for (i = 0; i < s->node->num_links; i++) {
905 if (s->node->axes[i] == axis) {
906 for (j = 0; j < s->node->num_links; j++) {
907 if (j == i)
908 continue;
909 if (s->node->matrix[i][j] != 2)
910 return negaxis;
911 }
912
913 return axis;
914 }
915 }
916
917 return 0;
918 }
919
920 /*
921 * make_geometry
922 *
923 * induce a geometry on the switches
924 */
make_geometry(lash_t * p_lash,int sw)925 static void make_geometry(lash_t *p_lash, int sw)
926 {
927 osm_log_t *p_log = &p_lash->p_osm->log;
928 int num_switches = p_lash->num_switches;
929 int sw1, sw2;
930 switch_t *s, *s1, *s2, *seed;
931 unsigned int i, j, k, l, n, m;
932 unsigned int change;
933
934 OSM_LOG_ENTER(p_log);
935
936 s = p_lash->switches[sw];
937
938 if (!s->node->matrix)
939 goto done;
940
941 /*
942 * assign axes to seed switch
943 */
944 seed_axes(p_lash, sw);
945 seed = p_lash->switches[sw];
946
947 /*
948 * induce axes in other switches until
949 * there is no more change
950 */
951 do {
952 change = 0;
953
954 /* phase 1 opposites */
955 for (sw1 = 0; sw1 < num_switches; sw1++) {
956 s1 = p_lash->switches[sw1];
957 n = s1->node->num_links;
958
959 /*
960 * ignore chain fragments
961 */
962 if (n < seed->node->num_links && n <= 2)
963 continue;
964
965 /*
966 * only process 'mesh' switches
967 */
968 if (!s1->node->matrix)
969 continue;
970
971 for (i = 0; i < n; i++) {
972 if (!s1->node->axes[i])
973 continue;
974
975 /*
976 * can't tell across if more than one
977 * likely looking link
978 */
979 m = 0;
980 for (j = 0; j < n; j++) {
981 if (j == i)
982 continue;
983
984 if (s1->node->matrix[i][j] != 2)
985 m++;
986 }
987
988 if (m != 1) {
989 continue;
990 }
991
992 for (j = 0; j < n; j++) {
993 if (j == i)
994 continue;
995
996 /* Rule out opposite nodes when distance greater than 4 */
997 if (s1->node->matrix[i][j] != 2 &&
998 s1->node->matrix[i][j] <= 4) {
999 if (s1->node->axes[j]) {
1000 if (s1->node->axes[j] != opposite(seed, s1->node->axes[i])) {
1001 OSM_LOG(p_log, OSM_LOG_DEBUG,
1002 "phase 1 mismatch\n");
1003 }
1004 } else {
1005 s1->node->axes[j] = opposite(seed, s1->node->axes[i]);
1006 change++;
1007 }
1008 }
1009 }
1010 }
1011 }
1012
1013 /* phase 2 switch to switch */
1014 for (sw1 = 0; sw1 < num_switches; sw1++) {
1015 s1 = p_lash->switches[sw1];
1016 n = s1->node->num_links;
1017
1018 if (!s1->node->matrix)
1019 continue;
1020
1021 for (i = 0; i < n; i++) {
1022 int l2 = s1->node->links[i]->link_id;
1023
1024 if (!s1->node->axes[i])
1025 continue;
1026
1027 if (l2 == -1) {
1028 OSM_LOG(p_log, OSM_LOG_DEBUG,
1029 "no reverse link\n");
1030 continue;
1031 }
1032
1033 sw2 = s1->node->links[i]->switch_id;
1034 s2 = p_lash->switches[sw2];
1035
1036 if (!s2->node->matrix)
1037 continue;
1038
1039 if (!s2->node->axes[l2]) {
1040 /*
1041 * set axis to opposite of s1->axes[i]
1042 */
1043 s2->node->axes[l2] = opposite(seed, s1->node->axes[i]);
1044 change++;
1045 } else {
1046 if (s2->node->axes[l2] != opposite(seed, s1->node->axes[i])) {
1047 OSM_LOG(p_log, OSM_LOG_DEBUG,
1048 "phase 2 mismatch\n");
1049 }
1050 }
1051 }
1052 }
1053
1054 /* Phase 3 corners */
1055 for (sw1 = 0; sw1 < num_switches; sw1++) {
1056 s = p_lash->switches[sw1];
1057 n = s->node->num_links;
1058
1059 if (!s->node->matrix)
1060 continue;
1061
1062 for (i = 0; i < n; i++) {
1063 if (!s->node->axes[i])
1064 continue;
1065
1066 for (j = 0; j < n; j++) {
1067 if (i == j || !s->node->axes[j] || s->node->matrix[i][j] != 2)
1068 continue;
1069
1070 s1 = p_lash->switches[s->node->links[i]->switch_id];
1071 s2 = p_lash->switches[s->node->links[j]->switch_id];
1072
1073 /*
1074 * find switch (other than s1) that neighbors i and j
1075 * have in common
1076 */
1077 for (k = 0; k < s1->node->num_links; k++) {
1078 if (s1->node->links[k]->switch_id == sw1)
1079 continue;
1080
1081 for (l = 0; l < s2->node->num_links; l++) {
1082 if (s2->node->links[l]->switch_id == sw1)
1083 continue;
1084
1085 if (s1->node->links[k]->switch_id == s2->node->links[l]->switch_id) {
1086 if (s1->node->axes[k]) {
1087 if (s1->node->axes[k] != s->node->axes[j]) {
1088 OSM_LOG(p_log, OSM_LOG_DEBUG, "phase 3 mismatch\n");
1089 }
1090 } else {
1091 s1->node->axes[k] = s->node->axes[j];
1092 change++;
1093 }
1094
1095 if (s2->node->axes[l]) {
1096 if (s2->node->axes[l] != s->node->axes[i]) {
1097 OSM_LOG(p_log, OSM_LOG_DEBUG, "phase 3 mismatch\n");
1098 }
1099 } else {
1100 s2->node->axes[l] = s->node->axes[i];
1101 change++;
1102 }
1103 goto next_j;
1104 }
1105 }
1106 }
1107 next_j:
1108 ;
1109 }
1110 }
1111 }
1112 } while (change);
1113
1114 done:
1115 OSM_LOG_EXIT(p_log);
1116 }
1117
1118 /*
1119 * return |a| < |b|
1120 */
ltmag(int a,int b)1121 static inline int ltmag(int a, int b)
1122 {
1123 int a1 = (a >= 0)? a : -a;
1124 int b1 = (b >= 0)? b : -b;
1125
1126 return (a1 < b1) || (a1 == b1 && a > b);
1127 }
1128
1129 /*
1130 * reorder_node_links
1131 *
1132 * reorder the links out of a switch in sign/dimension order
1133 */
reorder_node_links(lash_t * p_lash,mesh_t * mesh,int sw)1134 static int reorder_node_links(lash_t *p_lash, mesh_t *mesh, int sw)
1135 {
1136 osm_log_t *p_log = &p_lash->p_osm->log;
1137 switch_t *s = p_lash->switches[sw];
1138 mesh_node_t *node = s->node;
1139 int n = node->num_links;
1140 link_t **links;
1141 int *axes;
1142 int i, j, k, l;
1143 int c;
1144 int next = 0;
1145 int dimension = mesh->dimension;
1146
1147 if (!(links = calloc(n, sizeof(link_t *)))) {
1148 OSM_LOG(p_log, OSM_LOG_ERROR,
1149 "Failed allocating links array - out of memory\n");
1150 return -1;
1151 }
1152
1153 if (!(axes = calloc(n, sizeof(int)))) {
1154 free(links);
1155 OSM_LOG(p_log, OSM_LOG_ERROR,
1156 "Failed allocating axes array - out of memory\n");
1157 return -1;
1158 }
1159
1160 /*
1161 * find the links with axes
1162 */
1163 for (i = 0; i < dimension; i++) {
1164 j = mesh->dim_order[i];
1165 for (k = 1; k <= 2; k++) {
1166 c = 2*j + k;
1167
1168 if (node->coord[j] > 0)
1169 c = opposite(s, c);
1170
1171 for (l = 0; l < n; l++) {
1172 if (!node->links[l])
1173 continue;
1174 if (node->axes[l] == c) {
1175 links[next] = node->links[l];
1176 axes[next] = node->axes[l];
1177 node->links[l] = NULL;
1178 next++;
1179 }
1180 }
1181 }
1182 }
1183
1184 /*
1185 * get the rest
1186 */
1187 for (i = 0; i < n; i++) {
1188 if (!node->links[i])
1189 continue;
1190
1191 links[next] = node->links[i];
1192 axes[next] = node->axes[i];
1193 node->links[i] = NULL;
1194 next++;
1195 }
1196
1197 for (i = 0; i < n; i++) {
1198 node->links[i] = links[i];
1199 node->axes[i] = axes[i];
1200 }
1201
1202 free(links);
1203 free(axes);
1204
1205 return 0;
1206 }
1207
1208 /*
1209 * make_coord
1210 */
make_coord(lash_t * p_lash,mesh_t * mesh,int seed)1211 static int make_coord(lash_t *p_lash, mesh_t *mesh, int seed)
1212 {
1213 osm_log_t *p_log = &p_lash->p_osm->log;
1214 unsigned int i, j, k;
1215 int sw;
1216 switch_t *s, *s1;
1217 unsigned int change;
1218 unsigned int dimension = mesh->dimension;
1219 int num_switches = p_lash->num_switches;
1220 int assigned_axes = 0, unassigned_axes = 0;
1221
1222 OSM_LOG_ENTER(p_log);
1223
1224 for (sw = 0; sw < num_switches; sw++) {
1225 s = p_lash->switches[sw];
1226
1227 s->node->coord = calloc(dimension, sizeof(int));
1228 if (!s->node->coord) {
1229 OSM_LOG(p_log, OSM_LOG_ERROR,
1230 "Failed allocating coord - out of memory\n");
1231 OSM_LOG_EXIT(p_log);
1232 return -1;
1233 }
1234
1235 for (i = 0; i < dimension; i++)
1236 s->node->coord[i] = (sw == seed) ? 0 : LARGE;
1237
1238 for (i = 0; i < s->node->num_links; i++)
1239 if (s->node->axes[i] == 0)
1240 unassigned_axes++;
1241 else
1242 assigned_axes++;
1243 }
1244
1245 OSM_LOG(p_log, OSM_LOG_DEBUG, "%d/%d unassigned/assigned axes\n",
1246 unassigned_axes, assigned_axes);
1247
1248 do {
1249 change = 0;
1250
1251 for (sw = 0; sw < num_switches; sw++) {
1252 s = p_lash->switches[sw];
1253
1254 if (s->node->coord[0] == LARGE)
1255 continue;
1256
1257 for (j = 0; j < s->node->num_links; j++) {
1258 if (!s->node->axes[j])
1259 continue;
1260
1261 s1 = p_lash->switches[s->node->links[j]->switch_id];
1262
1263 for (k = 0; k < dimension; k++) {
1264 int coord = s->node->coord[k];
1265 unsigned axis = s->node->axes[j] - 1;
1266
1267 if (k == axis/2)
1268 coord += (axis & 1)? -1 : +1;
1269
1270 if (ltmag(coord, s1->node->coord[k])) {
1271 s1->node->coord[k] = coord;
1272 change++;
1273 }
1274 }
1275 }
1276 }
1277 } while (change);
1278
1279 OSM_LOG_EXIT(p_log);
1280 return 0;
1281 }
1282
1283 /*
1284 * measure geometry
1285 */
measure_geometry(lash_t * p_lash,mesh_t * mesh)1286 static int measure_geometry(lash_t *p_lash, mesh_t *mesh)
1287 {
1288 osm_log_t *p_log = &p_lash->p_osm->log;
1289 int i, j;
1290 int sw;
1291 switch_t *s;
1292 int dimension = mesh->dimension;
1293 int num_switches = p_lash->num_switches;
1294 int max[MAX_DIMENSION];
1295 int min[MAX_DIMENSION];
1296 int size[MAX_DIMENSION];
1297 int max_size;
1298 int max_index;
1299
1300 OSM_LOG_ENTER(p_log);
1301
1302 mesh->size = calloc(dimension, sizeof(int));
1303 if (!mesh->size) {
1304 OSM_LOG(p_log, OSM_LOG_ERROR,
1305 "Failed allocating size - out of memory\n");
1306 OSM_LOG_EXIT(p_log);
1307 return -1;
1308 }
1309
1310 for (i = 0; i < dimension; i++) {
1311 max[i] = -LARGE;
1312 min[i] = LARGE;
1313 }
1314
1315 for (sw = 0; sw < num_switches; sw++) {
1316 s = p_lash->switches[sw];
1317
1318 for (i = 0; i < dimension; i++) {
1319 if (s->node->coord[i] == LARGE)
1320 continue;
1321 if (s->node->coord[i] > max[i])
1322 max[i] = s->node->coord[i];
1323 if (s->node->coord[i] < min[i])
1324 min[i] = s->node->coord[i];
1325 }
1326 }
1327
1328 for (i = 0; i < dimension; i++)
1329 mesh->size[i] = size[i] = max[i] - min[i] + 1;
1330
1331 /*
1332 * find an order of dimensions that places largest
1333 * sizes first since this seems to work best with LASH
1334 */
1335 for (j = 0; j < dimension; j++) {
1336 max_size = -1;
1337 max_index = -1;
1338
1339 for (i = 0; i < dimension; i++) {
1340 if (size[i] > max_size) {
1341 max_size = size[i];
1342 max_index = i;
1343 }
1344 }
1345
1346 mesh->dim_order[j] = max_index;
1347 size[max_index] = -1;
1348 }
1349
1350 OSM_LOG_EXIT(p_log);
1351 return 0;
1352 }
1353
1354 /*
1355 * reorder links
1356 */
reorder_links(lash_t * p_lash,mesh_t * mesh)1357 static int reorder_links(lash_t *p_lash, mesh_t *mesh)
1358 {
1359 osm_log_t *p_log = &p_lash->p_osm->log;
1360 int sw;
1361 int num_switches = p_lash->num_switches;
1362
1363 OSM_LOG_ENTER(p_log);
1364
1365 for (sw = 0; sw < num_switches; sw++) {
1366 if (reorder_node_links(p_lash, mesh, sw)) {
1367 OSM_LOG_EXIT(p_log);
1368 return -1;
1369 }
1370 }
1371
1372 OSM_LOG_EXIT(p_log);
1373 return 0;
1374 }
1375
1376 /*
1377 * compare two switches in a sort
1378 */
compare_switches(const void * p1,const void * p2)1379 static int compare_switches(const void *p1, const void *p2)
1380 {
1381 const comp_t *cp1 = p1, *cp2 = p2;
1382 const sort_ctx_t *ctx = &cp1->ctx;
1383 switch_t *s1 = ctx->p_lash->switches[cp1->index];
1384 switch_t *s2 = ctx->p_lash->switches[cp2->index];
1385 int i, j;
1386 int ret;
1387
1388 for (i = 0; i < ctx->mesh->dimension; i++) {
1389 j = ctx->mesh->dim_order[i];
1390 ret = s1->node->coord[j] - s2->node->coord[j];
1391 if (ret)
1392 return ret;
1393 }
1394
1395 return 0;
1396 }
1397
1398 /*
1399 * sort_switches - reorder switch array
1400 */
sort_switches(lash_t * p_lash,mesh_t * mesh)1401 static void sort_switches(lash_t *p_lash, mesh_t *mesh)
1402 {
1403 unsigned int i, j;
1404 unsigned int num_switches = p_lash->num_switches;
1405 comp_t *comp;
1406 int *reverse;
1407 switch_t *s;
1408 switch_t **switches;
1409
1410 comp = malloc(num_switches * sizeof(comp_t));
1411 reverse = malloc(num_switches * sizeof(int));
1412 switches = malloc(num_switches * sizeof(switch_t *));
1413 if (!comp || !reverse || !switches) {
1414 OSM_LOG(&p_lash->p_osm->log, OSM_LOG_ERROR,
1415 "Failed memory allocation - switches not sorted!\n");
1416 goto Exit;
1417 }
1418
1419 for (i = 0; i < num_switches; i++) {
1420 comp[i].index = i;
1421 comp[i].ctx.mesh = mesh;
1422 comp[i].ctx.p_lash = p_lash;
1423 }
1424
1425 qsort(comp, num_switches, sizeof(comp_t), compare_switches);
1426
1427 for (i = 0; i < num_switches; i++)
1428 reverse[comp[i].index] = i;
1429
1430 for (i = 0; i < num_switches; i++) {
1431 s = p_lash->switches[comp[i].index];
1432 switches[i] = s;
1433 s->id = i;
1434 for (j = 0; j < s->node->num_links; j++)
1435 s->node->links[j]->switch_id =
1436 reverse[s->node->links[j]->switch_id];
1437 }
1438
1439 for (i = 0; i < num_switches; i++)
1440 p_lash->switches[i] = switches[i];
1441
1442 Exit:
1443 if (switches)
1444 free(switches);
1445 if (comp)
1446 free(comp);
1447 if (reverse)
1448 free(reverse);
1449 }
1450
1451 /*
1452 * osm_mesh_delete - free per mesh resources
1453 */
mesh_delete(mesh_t * mesh)1454 static void mesh_delete(mesh_t *mesh)
1455 {
1456 if (mesh) {
1457 if (mesh->class_type)
1458 free(mesh->class_type);
1459
1460 if (mesh->class_count)
1461 free(mesh->class_count);
1462
1463 if (mesh->size)
1464 free(mesh->size);
1465
1466 free(mesh);
1467 }
1468 }
1469
1470 /*
1471 * osm_mesh_create - allocate per mesh resources
1472 */
mesh_create(lash_t * p_lash)1473 static mesh_t *mesh_create(lash_t *p_lash)
1474 {
1475 osm_log_t *p_log = &p_lash->p_osm->log;
1476 mesh_t *mesh;
1477
1478 if(!(mesh = calloc(1, sizeof(mesh_t))))
1479 goto err;
1480
1481 if (!(mesh->class_type = calloc(p_lash->num_switches, sizeof(int))))
1482 goto err;
1483
1484 if (!(mesh->class_count = calloc(p_lash->num_switches, sizeof(int))))
1485 goto err;
1486
1487 return mesh;
1488
1489 err:
1490 mesh_delete(mesh);
1491 OSM_LOG(p_log, OSM_LOG_ERROR,
1492 "Failed allocating mesh - out of memory\n");
1493 return NULL;
1494 }
1495
1496 /*
1497 * osm_mesh_node_delete - cleanup per switch resources
1498 */
osm_mesh_node_delete(lash_t * p_lash,switch_t * sw)1499 void osm_mesh_node_delete(lash_t *p_lash, switch_t *sw)
1500 {
1501 osm_log_t *p_log = &p_lash->p_osm->log;
1502 unsigned i;
1503 mesh_node_t *node = sw->node;
1504 unsigned num_ports = sw->p_sw->num_ports;
1505
1506 OSM_LOG_ENTER(p_log);
1507
1508 if (node) {
1509 for (i = 0; i < num_ports; i++)
1510 if (node->links[i])
1511 free(node->links[i]);
1512
1513 if (node->poly)
1514 free(node->poly);
1515
1516 if (node->matrix) {
1517 for (i = 0; i < node->num_links; i++) {
1518 if (node->matrix[i])
1519 free(node->matrix[i]);
1520 }
1521 free(node->matrix);
1522 }
1523
1524 if (node->axes)
1525 free(node->axes);
1526
1527 if (node->coord)
1528 free(node->coord);
1529
1530 free(node);
1531
1532 sw->node = NULL;
1533 }
1534
1535 OSM_LOG_EXIT(p_log);
1536 }
1537
1538 /*
1539 * osm_mesh_node_create - allocate per switch resources
1540 */
osm_mesh_node_create(lash_t * p_lash,switch_t * sw)1541 int osm_mesh_node_create(lash_t *p_lash, switch_t *sw)
1542 {
1543 osm_log_t *p_log = &p_lash->p_osm->log;
1544 unsigned i;
1545 mesh_node_t *node;
1546 unsigned num_ports = sw->p_sw->num_ports;
1547
1548 OSM_LOG_ENTER(p_log);
1549
1550 if (!(node = sw->node = calloc(1, sizeof(mesh_node_t) + num_ports * sizeof(link_t *))))
1551 goto err;
1552
1553 for (i = 0; i < num_ports; i++)
1554 if (!(node->links[i] = calloc(1, sizeof(link_t) + num_ports * sizeof(int))))
1555 goto err;
1556
1557 if (!(node->axes = calloc(num_ports, sizeof(int))))
1558 goto err;
1559
1560 for (i = 0; i < num_ports; i++) {
1561 node->links[i]->switch_id = NONE;
1562 }
1563
1564 OSM_LOG_EXIT(p_log);
1565 return 0;
1566
1567 err:
1568 osm_mesh_node_delete(p_lash, sw);
1569 OSM_LOG(p_log, OSM_LOG_ERROR,
1570 "Failed allocating mesh node - out of memory\n");
1571 OSM_LOG_EXIT(p_log);
1572 return -1;
1573 }
1574
dump_mesh(lash_t * p_lash)1575 static void dump_mesh(lash_t *p_lash)
1576 {
1577 osm_log_t *p_log = &p_lash->p_osm->log;
1578 int sw;
1579 int num_switches = p_lash->num_switches;
1580 int dimension;
1581 int i, j, k, n;
1582 switch_t *s, *s2;
1583 char buf[256];
1584
1585 OSM_LOG_ENTER(p_log);
1586
1587 for (sw = 0; sw < num_switches; sw++) {
1588 s = p_lash->switches[sw];
1589 dimension = s->node->dimension;
1590 n = sprintf(buf, "[");
1591 for (i = 0; i < dimension; i++) {
1592 n += snprintf(buf + n, sizeof(buf) - n,
1593 "%2d", s->node->coord[i]);
1594 if (n > sizeof(buf))
1595 n = sizeof(buf);
1596 if (i != dimension - 1) {
1597 n += snprintf(buf + n, sizeof(buf) - n, "%s", ",");
1598 if (n > sizeof(buf))
1599 n = sizeof(buf);
1600 }
1601 }
1602 n += snprintf(buf + n, sizeof(buf) - n, "]");
1603 if (n > sizeof(buf))
1604 n = sizeof(buf);
1605 for (j = 0; j < s->node->num_links; j++) {
1606 s2 = p_lash->switches[s->node->links[j]->switch_id];
1607 n += snprintf(buf + n, sizeof(buf) - n, " [%d]->[", j);
1608 if (n > sizeof(buf))
1609 n = sizeof(buf);
1610 for (k = 0; k < dimension; k++) {
1611 n += snprintf(buf + n, sizeof(buf) - n, "%2d",
1612 s2->node->coord[k]);
1613 if (n > sizeof(buf))
1614 n = sizeof(buf);
1615 if (k != dimension - 1) {
1616 n += snprintf(buf + n, sizeof(buf) - n,
1617 ",");
1618 if (n > sizeof(buf))
1619 n = sizeof(buf);
1620 }
1621 }
1622 n += snprintf(buf + n, sizeof(buf) - n, "]");
1623 if (n > sizeof(buf))
1624 n = sizeof(buf);
1625 }
1626 OSM_LOG(p_log, OSM_LOG_DEBUG, "%s\n", buf);
1627 }
1628
1629 OSM_LOG_EXIT(p_log);
1630 }
1631
1632 /*
1633 * osm_do_mesh_analysis
1634 */
osm_do_mesh_analysis(lash_t * p_lash)1635 int osm_do_mesh_analysis(lash_t *p_lash)
1636 {
1637 osm_log_t *p_log = &p_lash->p_osm->log;
1638 mesh_t *mesh;
1639 int max_class_num = 0;
1640 int max_class_type = -1;
1641 int i;
1642 switch_t *s;
1643 char buf[256], *p;
1644
1645 OSM_LOG_ENTER(p_log);
1646
1647 mesh = mesh_create(p_lash);
1648 if (!mesh)
1649 goto err;
1650
1651 if (get_local_geometry(p_lash, mesh))
1652 goto err;
1653
1654 if (mesh->num_class == 0) {
1655 OSM_LOG(p_log, OSM_LOG_INFO,
1656 "found no likely mesh nodes - done\n");
1657 goto done;
1658 }
1659
1660 /*
1661 * find dominant switch class
1662 */
1663 OSM_LOG(p_log, OSM_LOG_INFO, "found %d node class%s\n",
1664 mesh->num_class, (mesh->num_class == 1) ? "" : "es");
1665 for (i = 0; i < mesh->num_class; i++) {
1666 OSM_LOG(p_log, OSM_LOG_INFO,
1667 "class[%d] has %d members with type = %d\n",
1668 i, mesh->class_count[i],
1669 p_lash->switches[mesh->class_type[i]]->node->type);
1670 if (mesh->class_count[i] > max_class_num) {
1671 max_class_num = mesh->class_count[i];
1672 max_class_type = mesh->class_type[i];
1673 }
1674 }
1675
1676 s = p_lash->switches[max_class_type];
1677
1678 p = buf;
1679 p += sprintf(p, "%snode shape is ",
1680 (mesh->num_class == 1) ? "" : "most common ");
1681
1682 if (s->node->type) {
1683 const struct mesh_info *t = &mesh_info[s->node->type];
1684
1685 for (i = 0; i < t->dimension; i++) {
1686 p += sprintf(p, "%s%d%s", i? " x " : "", t->size[i],
1687 (t->size[i] == 6)? "+" : "");
1688 }
1689 p += sprintf(p, " mesh\n");
1690
1691 mesh->dimension = t->dimension;
1692 } else {
1693 p += sprintf(p, "unknown geometry\n");
1694 }
1695
1696 OSM_LOG(p_log, OSM_LOG_INFO, "%s", buf);
1697
1698 OSM_LOG(p_log, OSM_LOG_INFO, "poly = %s\n",
1699 poly_print(s->node->num_links, s->node->poly));
1700
1701 if (s->node->type) {
1702 make_geometry(p_lash, max_class_type);
1703
1704 if (make_coord(p_lash, mesh, max_class_type))
1705 goto err;
1706
1707 if (measure_geometry(p_lash, mesh))
1708 goto err;
1709
1710 if (reorder_links(p_lash, mesh))
1711 goto err;
1712
1713 sort_switches(p_lash, mesh);
1714
1715 p = buf;
1716 p += sprintf(p, "found ");
1717 for (i = 0; i < mesh->dimension; i++)
1718 p += sprintf(p, "%s%d", i? " x " : "", mesh->size[i]);
1719 p += sprintf(p, " mesh\n");
1720
1721 OSM_LOG(p_log, OSM_LOG_INFO, "%s", buf);
1722 }
1723
1724 if (OSM_LOG_IS_ACTIVE_V2(p_log, OSM_LOG_DEBUG))
1725 dump_mesh(p_lash);
1726
1727 done:
1728 mesh_delete(mesh);
1729 OSM_LOG_EXIT(p_log);
1730 return 0;
1731
1732 err:
1733 mesh_delete(mesh);
1734 OSM_LOG_EXIT(p_log);
1735 return -1;
1736 }
1737