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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 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 */ 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