root/opal/mca/hwloc/hwloc201/hwloc/hwloc/distances.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. hwloc_internal_distances_init
  2. hwloc_internal_distances_prepare
  3. hwloc_internal_distances_free
  4. hwloc_internal_distances_destroy
  5. hwloc_internal_distances_dup_one
  6. hwloc_internal_distances_dup
  7. hwloc_distances_remove
  8. hwloc_distances_remove_by_depth
  9. hwloc_internal_distances__add
  10. hwloc_internal_distances_add_by_index
  11. hwloc_internal_distances_add
  12. hwloc_distances_add
  13. hwloc_find_obj_by_type_and_gp_index
  14. hwloc_internal_distances_restrict
  15. hwloc_internal_distances_refresh_one
  16. hwloc_internal_distances_refresh
  17. hwloc_internal_distances_invalidate_cached_objs
  18. hwloc_distances_release
  19. hwloc_distances_get_one
  20. hwloc__distances_get
  21. hwloc_distances_get
  22. hwloc_distances_get_by_depth
  23. hwloc_report_user_distance_error
  24. hwloc_compare_values
  25. hwloc__find_groups_by_min_distance
  26. hwloc__check_grouping_matrix
  27. hwloc__groups_by_distances
   1 /*
   2  * Copyright © 2010-2018 Inria.  All rights reserved.
   3  * Copyright © 2011-2012 Université Bordeaux
   4  * Copyright © 2011 Cisco Systems, Inc.  All rights reserved.
   5  * See COPYING in top-level directory.
   6  */
   7 
   8 #include <private/autogen/config.h>
   9 #include <hwloc.h>
  10 #include <private/private.h>
  11 #include <private/debug.h>
  12 #include <private/misc.h>
  13 
  14 #include <float.h>
  15 #include <math.h>
  16 
  17 /******************************************************
  18  * Global init, prepare, destroy, dup
  19  */
  20 
  21 /* called during topology init() */
  22 void hwloc_internal_distances_init(struct hwloc_topology *topology)
  23 {
  24   topology->first_dist = topology->last_dist = NULL;
  25   topology->next_dist_id = 0;
  26 }
  27 
  28 /* called at the beginning of load() */
  29 void hwloc_internal_distances_prepare(struct hwloc_topology *topology)
  30 {
  31   char *env;
  32   hwloc_localeswitch_declare;
  33 
  34   topology->grouping = 1;
  35   if (topology->type_filter[HWLOC_OBJ_GROUP] == HWLOC_TYPE_FILTER_KEEP_NONE)
  36     topology->grouping = 0;
  37   env = getenv("HWLOC_GROUPING");
  38   if (env && !atoi(env))
  39     topology->grouping = 0;
  40 
  41   if (topology->grouping) {
  42     topology->grouping_next_subkind = 0;
  43 
  44     HWLOC_BUILD_ASSERT(sizeof(topology->grouping_accuracies)/sizeof(*topology->grouping_accuracies) == 5);
  45     topology->grouping_accuracies[0] = 0.0f;
  46     topology->grouping_accuracies[1] = 0.01f;
  47     topology->grouping_accuracies[2] = 0.02f;
  48     topology->grouping_accuracies[3] = 0.05f;
  49     topology->grouping_accuracies[4] = 0.1f;
  50     topology->grouping_nbaccuracies = 5;
  51 
  52     hwloc_localeswitch_init();
  53     env = getenv("HWLOC_GROUPING_ACCURACY");
  54     if (!env) {
  55       /* only use 0.0 */
  56       topology->grouping_nbaccuracies = 1;
  57     } else if (strcmp(env, "try")) {
  58       /* use the given value */
  59       topology->grouping_nbaccuracies = 1;
  60       topology->grouping_accuracies[0] = (float) atof(env);
  61     } /* otherwise try all values */
  62     hwloc_localeswitch_fini();
  63 
  64     topology->grouping_verbose = 0;
  65     env = getenv("HWLOC_GROUPING_VERBOSE");
  66     if (env)
  67       topology->grouping_verbose = atoi(env);
  68   }
  69 }
  70 
  71 static void hwloc_internal_distances_free(struct hwloc_internal_distances_s *dist)
  72 {
  73   free(dist->indexes);
  74   free(dist->objs);
  75   free(dist->values);
  76   free(dist);
  77 }
  78 
  79 /* called during topology destroy */
  80 void hwloc_internal_distances_destroy(struct hwloc_topology * topology)
  81 {
  82   struct hwloc_internal_distances_s *dist, *next = topology->first_dist;
  83   while ((dist = next) != NULL) {
  84     next = dist->next;
  85     hwloc_internal_distances_free(dist);
  86   }
  87   topology->first_dist = topology->last_dist = NULL;
  88 }
  89 
  90 static int hwloc_internal_distances_dup_one(struct hwloc_topology *new, struct hwloc_internal_distances_s *olddist)
  91 {
  92   struct hwloc_tma *tma = new->tma;
  93   struct hwloc_internal_distances_s *newdist;
  94   unsigned nbobjs = olddist->nbobjs;
  95 
  96   newdist = hwloc_tma_malloc(tma, sizeof(*newdist));
  97   if (!newdist)
  98     return -1;
  99 
 100   newdist->type = olddist->type;
 101   newdist->nbobjs = nbobjs;
 102   newdist->kind = olddist->kind;
 103   newdist->id = olddist->id;
 104 
 105   newdist->indexes = hwloc_tma_malloc(tma, nbobjs * sizeof(*newdist->indexes));
 106   newdist->objs = hwloc_tma_calloc(tma, nbobjs * sizeof(*newdist->objs));
 107   newdist->objs_are_valid = 0;
 108   newdist->values = hwloc_tma_malloc(tma, nbobjs*nbobjs * sizeof(*newdist->values));
 109   if (!newdist->indexes || !newdist->objs || !newdist->values) {
 110     assert(!tma || !tma->dontfree); /* this tma cannot fail to allocate */
 111     hwloc_internal_distances_free(newdist);
 112     return -1;
 113   }
 114 
 115   memcpy(newdist->indexes, olddist->indexes, nbobjs * sizeof(*newdist->indexes));
 116   memcpy(newdist->values, olddist->values, nbobjs*nbobjs * sizeof(*newdist->values));
 117 
 118   newdist->next = NULL;
 119   newdist->prev = new->last_dist;
 120   if (new->last_dist)
 121     new->last_dist->next = newdist;
 122   else
 123     new->first_dist = newdist;
 124   new->last_dist = newdist;
 125 
 126   return 0;
 127 }
 128 
 129 /* This function may be called with topology->tma set, it cannot free() or realloc() */
 130 int hwloc_internal_distances_dup(struct hwloc_topology *new, struct hwloc_topology *old)
 131 {
 132   struct hwloc_internal_distances_s *olddist;
 133   int err;
 134   new->next_dist_id = old->next_dist_id;
 135   for(olddist = old->first_dist; olddist; olddist = olddist->next) {
 136     err = hwloc_internal_distances_dup_one(new, olddist);
 137     if (err < 0)
 138       return err;
 139   }
 140   return 0;
 141 }
 142 
 143 /******************************************************
 144  * Remove distances from the topology
 145  */
 146 
 147 int hwloc_distances_remove(hwloc_topology_t topology)
 148 {
 149   if (!topology->is_loaded) {
 150     errno = EINVAL;
 151     return -1;
 152   }
 153   hwloc_internal_distances_destroy(topology);
 154   return 0;
 155 }
 156 
 157 int hwloc_distances_remove_by_depth(hwloc_topology_t topology, int depth)
 158 {
 159   struct hwloc_internal_distances_s *dist, *next;
 160   hwloc_obj_type_t type;
 161 
 162   if (!topology->is_loaded) {
 163     errno = EINVAL;
 164     return -1;
 165   }
 166 
 167   /* switch back to types since we don't support groups for now */
 168   type = hwloc_get_depth_type(topology, depth);
 169   if (type == (hwloc_obj_type_t)-1) {
 170     errno = EINVAL;
 171     return -1;
 172   }
 173 
 174   next = topology->first_dist;
 175   while ((dist = next) != NULL) {
 176     next = dist->next;
 177     if (dist->type == type) {
 178       if (next)
 179         next->prev = dist->prev;
 180       else
 181         topology->last_dist = dist->prev;
 182       if (dist->prev)
 183         dist->prev->next = dist->next;
 184       else
 185         topology->first_dist = dist->next;
 186       hwloc_internal_distances_free(dist);
 187     }
 188   }
 189 
 190   return 0;
 191 }
 192 
 193 /******************************************************
 194  * Add distances to the topology
 195  */
 196 
 197 static void
 198 hwloc__groups_by_distances(struct hwloc_topology *topology, unsigned nbobjs, struct hwloc_obj **objs, uint64_t *values, unsigned long kind, unsigned nbaccuracies, float *accuracies, int needcheck);
 199 
 200 /* insert a distance matrix in the topology.
 201  * the caller gives us the distances and objs pointers, we'll free them later.
 202  */
 203 static int
 204 hwloc_internal_distances__add(hwloc_topology_t topology,
 205                               hwloc_obj_type_t type, unsigned nbobjs, hwloc_obj_t *objs, uint64_t *indexes, uint64_t *values,
 206                               unsigned long kind)
 207 {
 208   struct hwloc_internal_distances_s *dist = calloc(1, sizeof(*dist));
 209   if (!dist)
 210     goto err;
 211 
 212   dist->type = type;
 213   dist->nbobjs = nbobjs;
 214   dist->kind = kind;
 215 
 216   if (!objs) {
 217     assert(indexes);
 218     /* we only have indexes, we'll refresh objs from there */
 219     dist->indexes = indexes;
 220     dist->objs = calloc(nbobjs, sizeof(hwloc_obj_t));
 221     if (!dist->objs)
 222       goto err_with_dist;
 223     dist->objs_are_valid = 0;
 224 
 225   } else {
 226     unsigned i;
 227     assert(!indexes);
 228     /* we only have objs, generate the indexes arrays so that we can refresh objs later */
 229     dist->objs = objs;
 230     dist->objs_are_valid = 1;
 231     dist->indexes = malloc(nbobjs * sizeof(*dist->indexes));
 232     if (!dist->indexes)
 233       goto err_with_dist;
 234     if (dist->type == HWLOC_OBJ_PU || dist->type == HWLOC_OBJ_NUMANODE) {
 235       for(i=0; i<nbobjs; i++)
 236         dist->indexes[i] = objs[i]->os_index;
 237     } else {
 238       for(i=0; i<nbobjs; i++)
 239         dist->indexes[i] = objs[i]->gp_index;
 240     }
 241   }
 242 
 243   dist->values = values;
 244 
 245   dist->id = topology->next_dist_id++;
 246 
 247   if (topology->last_dist)
 248     topology->last_dist->next = dist;
 249   else
 250     topology->first_dist = dist;
 251   dist->prev = topology->last_dist;
 252   dist->next = NULL;
 253   topology->last_dist = dist;
 254   return 0;
 255 
 256  err_with_dist:
 257   free(dist);
 258  err:
 259   free(objs);
 260   free(indexes);
 261   free(values);
 262   return -1;
 263 }
 264 
 265 int hwloc_internal_distances_add_by_index(hwloc_topology_t topology,
 266                                           hwloc_obj_type_t type, unsigned nbobjs, uint64_t *indexes, uint64_t *values,
 267                                           unsigned long kind, unsigned long flags)
 268 {
 269   if (nbobjs < 2) {
 270     errno = EINVAL;
 271     goto err;
 272   }
 273 
 274   /* cannot group without objects,
 275    * and we don't group from XML anyway since the hwloc that generated the XML should have grouped already.
 276    */
 277   if (flags & HWLOC_DISTANCES_ADD_FLAG_GROUP) {
 278     errno = EINVAL;
 279     goto err;
 280   }
 281 
 282   return hwloc_internal_distances__add(topology, type, nbobjs, NULL, indexes, values, kind);
 283 
 284  err:
 285   free(indexes);
 286   free(values);
 287   return -1;
 288 }
 289 
 290 int hwloc_internal_distances_add(hwloc_topology_t topology,
 291                                  unsigned nbobjs, hwloc_obj_t *objs, uint64_t *values,
 292                                  unsigned long kind, unsigned long flags)
 293 {
 294   if (nbobjs < 2) {
 295     errno = EINVAL;
 296     goto err;
 297   }
 298 
 299   if (topology->grouping && (flags & HWLOC_DISTANCES_ADD_FLAG_GROUP)) {
 300     float full_accuracy = 0.f;
 301     float *accuracies;
 302     unsigned nbaccuracies;
 303 
 304     if (flags & HWLOC_DISTANCES_ADD_FLAG_GROUP_INACCURATE) {
 305       accuracies = topology->grouping_accuracies;
 306       nbaccuracies = topology->grouping_nbaccuracies;
 307     } else {
 308       accuracies = &full_accuracy;
 309       nbaccuracies = 1;
 310     }
 311 
 312     if (topology->grouping_verbose) {
 313       unsigned i, j;
 314       int gp = (objs[0]->type != HWLOC_OBJ_NUMANODE && objs[0]->type != HWLOC_OBJ_PU);
 315       fprintf(stderr, "Trying to group objects using distance matrix:\n");
 316       fprintf(stderr, "%s", gp ? "gp_index" : "os_index");
 317       for(j=0; j<nbobjs; j++)
 318         fprintf(stderr, " % 5d", (int)(gp ? objs[j]->gp_index : objs[j]->os_index));
 319       fprintf(stderr, "\n");
 320       for(i=0; i<nbobjs; i++) {
 321         fprintf(stderr, "  % 5d", (int)(gp ? objs[i]->gp_index : objs[i]->os_index));
 322         for(j=0; j<nbobjs; j++)
 323           fprintf(stderr, " % 5lld", (long long) values[i*nbobjs + j]);
 324         fprintf(stderr, "\n");
 325       }
 326     }
 327 
 328     hwloc__groups_by_distances(topology, nbobjs, objs, values,
 329                                kind, nbaccuracies, accuracies, 1 /* check the first matrice */);
 330   }
 331 
 332   return hwloc_internal_distances__add(topology, objs[0]->type, nbobjs, objs, NULL, values, kind);
 333 
 334  err:
 335   free(objs);
 336   free(values);
 337   return -1;
 338 }
 339 
 340 #define HWLOC_DISTANCES_KIND_FROM_ALL (HWLOC_DISTANCES_KIND_FROM_OS|HWLOC_DISTANCES_KIND_FROM_USER)
 341 #define HWLOC_DISTANCES_KIND_MEANS_ALL (HWLOC_DISTANCES_KIND_MEANS_LATENCY|HWLOC_DISTANCES_KIND_MEANS_BANDWIDTH)
 342 #define HWLOC_DISTANCES_KIND_ALL (HWLOC_DISTANCES_KIND_FROM_ALL|HWLOC_DISTANCES_KIND_MEANS_ALL)
 343 #define HWLOC_DISTANCES_ADD_FLAG_ALL (HWLOC_DISTANCES_ADD_FLAG_GROUP|HWLOC_DISTANCES_ADD_FLAG_GROUP_INACCURATE)
 344 
 345 /* The actual function exported to the user
 346  */
 347 int hwloc_distances_add(hwloc_topology_t topology,
 348                         unsigned nbobjs, hwloc_obj_t *objs, uint64_t *values,
 349                         unsigned long kind, unsigned long flags)
 350 {
 351   hwloc_obj_type_t type;
 352   unsigned i;
 353   uint64_t *_values;
 354   hwloc_obj_t *_objs;
 355   int err;
 356 
 357   if (nbobjs < 2 || !objs || !values || !topology->is_loaded) {
 358     errno = EINVAL;
 359     return -1;
 360   }
 361   if ((kind & ~HWLOC_DISTANCES_KIND_ALL)
 362       || hwloc_weight_long(kind & HWLOC_DISTANCES_KIND_FROM_ALL) != 1
 363       || hwloc_weight_long(kind & HWLOC_DISTANCES_KIND_MEANS_ALL) != 1
 364       || (flags & ~HWLOC_DISTANCES_ADD_FLAG_ALL)) {
 365     errno = EINVAL;
 366     return -1;
 367   }
 368 
 369   /* no strict need to check for duplicates, things shouldn't break */
 370 
 371   type = objs[0]->type;
 372   if (type == HWLOC_OBJ_GROUP) {
 373     /* not supported yet, would require we save the subkind together with the type. */
 374     errno = EINVAL;
 375     return -1;
 376   }
 377 
 378   for(i=1; i<nbobjs; i++)
 379     if (!objs[i] || objs[i]->type != type) {
 380       errno = EINVAL;
 381       return -1;
 382     }
 383 
 384   /* copy the input arrays and give them to the topology */
 385   _objs = malloc(nbobjs*sizeof(hwloc_obj_t));
 386   _values = malloc(nbobjs*nbobjs*sizeof(*_values));
 387   if (!_objs || !_values)
 388     goto out_with_arrays;
 389 
 390   memcpy(_objs, objs, nbobjs*sizeof(hwloc_obj_t));
 391   memcpy(_values, values, nbobjs*nbobjs*sizeof(*_values));
 392   err = hwloc_internal_distances_add(topology, nbobjs, _objs, _values, kind, flags);
 393   if (err < 0)
 394     goto out; /* _objs and _values freed in hwloc_internal_distances_add() */
 395 
 396   /* in case we added some groups, see if we need to reconnect */
 397   hwloc_topology_reconnect(topology, 0);
 398 
 399   return 0;
 400 
 401  out_with_arrays:
 402   free(_values);
 403   free(_objs);
 404  out:
 405   return -1;
 406 }
 407 
 408 /******************************************************
 409  * Refresh objects in distances
 410  */
 411 
 412 static hwloc_obj_t hwloc_find_obj_by_type_and_gp_index(hwloc_topology_t topology, hwloc_obj_type_t type, uint64_t gp_index)
 413 {
 414   hwloc_obj_t obj = hwloc_get_obj_by_type(topology, type, 0);
 415   while (obj) {
 416     if (obj->gp_index == gp_index)
 417       return obj;
 418     obj = obj->next_cousin;
 419   }
 420   return NULL;
 421 }
 422 
 423 static void
 424 hwloc_internal_distances_restrict(struct hwloc_internal_distances_s *dist,
 425                                   hwloc_obj_t *objs,
 426                                   unsigned disappeared)
 427 {
 428   unsigned nbobjs = dist->nbobjs;
 429   unsigned i, newi;
 430   unsigned j, newj;
 431 
 432   for(i=0, newi=0; i<nbobjs; i++)
 433     if (objs[i]) {
 434       for(j=0, newj=0; j<nbobjs; j++)
 435         if (objs[j]) {
 436           dist->values[newi*(nbobjs-disappeared)+newj] = dist->values[i*nbobjs+j];
 437           newj++;
 438         }
 439       newi++;
 440     }
 441 
 442   for(i=0, newi=0; i<nbobjs; i++)
 443     if (objs[i]) {
 444       objs[newi] = objs[i];
 445       dist->indexes[newi] = dist->indexes[i];
 446       newi++;
 447     }
 448 
 449   dist->nbobjs -= disappeared;
 450 }
 451 
 452 static int
 453 hwloc_internal_distances_refresh_one(hwloc_topology_t topology,
 454                                      struct hwloc_internal_distances_s *dist)
 455 {
 456   hwloc_obj_type_t type = dist->type;
 457   unsigned nbobjs = dist->nbobjs;
 458   hwloc_obj_t *objs = dist->objs;
 459   uint64_t *indexes = dist->indexes;
 460   unsigned disappeared = 0;
 461   unsigned i;
 462 
 463   if (dist->objs_are_valid)
 464     return 0;
 465 
 466   for(i=0; i<nbobjs; i++) {
 467     hwloc_obj_t obj;
 468     /* TODO use cpuset/nodeset to find pus/numas from the root?
 469      * faster than traversing the entire level?
 470      */
 471     if (type == HWLOC_OBJ_PU)
 472       obj = hwloc_get_pu_obj_by_os_index(topology, (unsigned) indexes[i]);
 473     else if (type == HWLOC_OBJ_NUMANODE)
 474       obj = hwloc_get_numanode_obj_by_os_index(topology, (unsigned) indexes[i]);
 475     else
 476       obj = hwloc_find_obj_by_type_and_gp_index(topology, type, indexes[i]);
 477     objs[i] = obj;
 478     if (!obj)
 479       disappeared++;
 480   }
 481 
 482   if (nbobjs-disappeared < 2)
 483     /* became useless, drop */
 484     return -1;
 485 
 486   if (disappeared)
 487     hwloc_internal_distances_restrict(dist, objs, disappeared);
 488 
 489   dist->objs_are_valid = 1;
 490   return 0;
 491 }
 492 
 493 /* This function may be called with topology->tma set, it cannot free() or realloc() */
 494 void
 495 hwloc_internal_distances_refresh(hwloc_topology_t topology)
 496 {
 497   struct hwloc_internal_distances_s *dist, *next;
 498 
 499   for(dist = topology->first_dist; dist; dist = next) {
 500     next = dist->next;
 501 
 502     if (hwloc_internal_distances_refresh_one(topology, dist) < 0) {
 503       assert(!topology->tma || !topology->tma->dontfree); /* this tma cannot fail to allocate */
 504       if (dist->prev)
 505         dist->prev->next = next;
 506       else
 507         topology->first_dist = next;
 508       if (next)
 509         next->prev = dist->prev;
 510       else
 511         topology->last_dist = dist->prev;
 512       hwloc_internal_distances_free(dist);
 513       continue;
 514     }
 515   }
 516 }
 517 
 518 void
 519 hwloc_internal_distances_invalidate_cached_objs(hwloc_topology_t topology)
 520 {
 521   struct hwloc_internal_distances_s *dist;
 522   for(dist = topology->first_dist; dist; dist = dist->next)
 523     dist->objs_are_valid = 0;
 524 }
 525 
 526 /******************************************************
 527  * User API for getting distances
 528  */
 529 
 530 void
 531 hwloc_distances_release(hwloc_topology_t topology __hwloc_attribute_unused,
 532                         struct hwloc_distances_s *distances)
 533 {
 534   free(distances->values);
 535   free(distances->objs);
 536   free(distances);
 537 }
 538 
 539 static struct hwloc_distances_s *
 540 hwloc_distances_get_one(hwloc_topology_t topology __hwloc_attribute_unused,
 541                         struct hwloc_internal_distances_s *dist)
 542 {
 543   struct hwloc_distances_s *distances;
 544   unsigned nbobjs;
 545 
 546   distances = malloc(sizeof(*distances));
 547   if (!distances)
 548     return NULL;
 549 
 550   nbobjs = distances->nbobjs = dist->nbobjs;
 551 
 552   distances->objs = malloc(nbobjs * sizeof(hwloc_obj_t));
 553   if (!distances->objs)
 554     goto out;
 555   memcpy(distances->objs, dist->objs, nbobjs * sizeof(hwloc_obj_t));
 556 
 557   distances->values = malloc(nbobjs * nbobjs * sizeof(*distances->values));
 558   if (!distances->values)
 559     goto out_with_objs;
 560   memcpy(distances->values, dist->values, nbobjs*nbobjs*sizeof(*distances->values));
 561 
 562   distances->kind = dist->kind;
 563   return distances;
 564 
 565  out_with_objs:
 566   free(distances->objs);
 567  out:
 568   free(distances);
 569   return NULL;
 570 }
 571 
 572 static int
 573 hwloc__distances_get(hwloc_topology_t topology,
 574                      hwloc_obj_type_t type,
 575                      unsigned *nrp, struct hwloc_distances_s **distancesp,
 576                      unsigned long kind, unsigned long flags __hwloc_attribute_unused)
 577 {
 578   struct hwloc_internal_distances_s *dist;
 579   unsigned nr = 0, i;
 580 
 581   /* We could return the internal arrays (as const),
 582    * but it would require to prevent removing distances between get() and free().
 583    * Not performance critical anyway.
 584    */
 585 
 586   if (flags) {
 587     errno = EINVAL;
 588     return -1;
 589   }
 590 
 591   /* we could refresh only the distances that match, but we won't have many distances anyway,
 592    * so performance is totally negligible.
 593    *
 594    * This is also useful in multithreaded apps that modify the topology.
 595    * They can call any valid hwloc_distances_get() to force a refresh after
 596    * changing the topology, so that future concurrent get() won't cause
 597    * concurrent refresh().
 598    */
 599   hwloc_internal_distances_refresh(topology);
 600 
 601   for(dist = topology->first_dist; dist; dist = dist->next) {
 602     unsigned long kind_from = kind & HWLOC_DISTANCES_KIND_FROM_ALL;
 603     unsigned long kind_means = kind & HWLOC_DISTANCES_KIND_MEANS_ALL;
 604 
 605     if (type != HWLOC_OBJ_TYPE_NONE && type != dist->type)
 606       continue;
 607 
 608     if (kind_from && !(kind_from & dist->kind))
 609       continue;
 610     if (kind_means && !(kind_means & dist->kind))
 611       continue;
 612 
 613     if (nr < *nrp) {
 614       struct hwloc_distances_s *distances = hwloc_distances_get_one(topology, dist);
 615       if (!distances)
 616         goto error;
 617       distancesp[nr] = distances;
 618     }
 619     nr++;
 620   }
 621 
 622   for(i=nr; i<*nrp; i++)
 623     distancesp[i] = NULL;
 624   *nrp = nr;
 625   return 0;
 626 
 627  error:
 628   for(i=0; i<nr; i++)
 629     hwloc_distances_release(topology, distancesp[i]);
 630   return -1;
 631 }
 632 
 633 int
 634 hwloc_distances_get(hwloc_topology_t topology,
 635                     unsigned *nrp, struct hwloc_distances_s **distancesp,
 636                     unsigned long kind, unsigned long flags)
 637 {
 638   if (flags || !topology->is_loaded) {
 639     errno = EINVAL;
 640     return -1;
 641   }
 642 
 643   return hwloc__distances_get(topology, HWLOC_OBJ_TYPE_NONE, nrp, distancesp, kind, flags);
 644 }
 645 
 646 int
 647 hwloc_distances_get_by_depth(hwloc_topology_t topology, int depth,
 648                              unsigned *nrp, struct hwloc_distances_s **distancesp,
 649                              unsigned long kind, unsigned long flags)
 650 {
 651   hwloc_obj_type_t type;
 652 
 653   if (flags || !topology->is_loaded) {
 654     errno = EINVAL;
 655     return -1;
 656   }
 657 
 658   /* switch back to types since we don't support groups for now */
 659   type = hwloc_get_depth_type(topology, depth);
 660   if (type == (hwloc_obj_type_t)-1) {
 661     errno = EINVAL;
 662     return -1;
 663   }
 664 
 665   return hwloc__distances_get(topology, type, nrp, distancesp, kind, flags);
 666 }
 667 
 668 /******************************************************
 669  * Grouping objects according to distances
 670  */
 671 
 672 static void hwloc_report_user_distance_error(const char *msg, int line)
 673 {
 674     static int reported = 0;
 675 
 676     if (!reported && !hwloc_hide_errors()) {
 677         fprintf(stderr, "****************************************************************************\n");
 678         fprintf(stderr, "* hwloc %s has encountered what looks like an error from user-given distances.\n", HWLOC_VERSION);
 679         fprintf(stderr, "*\n");
 680         fprintf(stderr, "* %s\n", msg);
 681         fprintf(stderr, "* Error occurred in topology.c line %d\n", line);
 682         fprintf(stderr, "*\n");
 683         fprintf(stderr, "* Please make sure that distances given through the interface or environment\n");
 684         fprintf(stderr, "* variables do not contradict any other topology information.\n");
 685         fprintf(stderr, "****************************************************************************\n");
 686         reported = 1;
 687     }
 688 }
 689 
 690 static int hwloc_compare_values(uint64_t a, uint64_t b, float accuracy)
 691 {
 692   if (accuracy != 0.0f && fabsf((float)a-(float)b) < (float)a * accuracy)
 693     return 0;
 694   return a < b ? -1 : a == b ? 0 : 1;
 695 }
 696 
 697 /*
 698  * Place objects in groups if they are in a transitive graph of minimal values.
 699  * Return how many groups were created, or 0 if some incomplete distance graphs were found.
 700  */
 701 static unsigned
 702 hwloc__find_groups_by_min_distance(unsigned nbobjs,
 703                                    uint64_t *_values,
 704                                    float accuracy,
 705                                    unsigned *groupids,
 706                                    int verbose)
 707 {
 708   uint64_t min_distance = UINT64_MAX;
 709   unsigned groupid = 1;
 710   unsigned i,j,k;
 711   unsigned skipped = 0;
 712 
 713 #define VALUE(i, j) _values[(i) * nbobjs + (j)]
 714 
 715   memset(groupids, 0, nbobjs*sizeof(*groupids));
 716 
 717   /* find the minimal distance */
 718   for(i=0; i<nbobjs; i++)
 719     for(j=0; j<nbobjs; j++) /* check the entire matrix, it may not be perfectly symmetric depending on the accuracy */
 720       if (i != j && VALUE(i, j) < min_distance) /* no accuracy here, we want the real minimal */
 721         min_distance = VALUE(i, j);
 722   hwloc_debug("  found minimal distance %llu between objects\n", (unsigned long long) min_distance);
 723 
 724   if (min_distance == UINT64_MAX)
 725     return 0;
 726 
 727   /* build groups of objects connected with this distance */
 728   for(i=0; i<nbobjs; i++) {
 729     unsigned size;
 730     unsigned firstfound;
 731 
 732     /* if already grouped, skip */
 733     if (groupids[i])
 734       continue;
 735 
 736     /* start a new group */
 737     groupids[i] = groupid;
 738     size = 1;
 739     firstfound = i;
 740 
 741     while (firstfound != (unsigned)-1) {
 742       /* we added new objects to the group, the first one was firstfound.
 743        * rescan all connections from these new objects (starting at first found) to any other objects,
 744        * so as to find new objects minimally-connected by transivity.
 745        */
 746       unsigned newfirstfound = (unsigned)-1;
 747       for(j=firstfound; j<nbobjs; j++)
 748         if (groupids[j] == groupid)
 749           for(k=0; k<nbobjs; k++)
 750               if (!groupids[k] && !hwloc_compare_values(VALUE(j, k), min_distance, accuracy)) {
 751               groupids[k] = groupid;
 752               size++;
 753               if (newfirstfound == (unsigned)-1)
 754                 newfirstfound = k;
 755               if (i == j)
 756                 hwloc_debug("  object %u is minimally connected to %u\n", k, i);
 757               else
 758                 hwloc_debug("  object %u is minimally connected to %u through %u\n", k, i, j);
 759             }
 760       firstfound = newfirstfound;
 761     }
 762 
 763     if (size == 1) {
 764       /* cancel this useless group, ignore this object and try from the next one */
 765       groupids[i] = 0;
 766       skipped++;
 767       continue;
 768     }
 769 
 770     /* valid this group */
 771     groupid++;
 772     if (verbose)
 773       fprintf(stderr, " Found transitive graph with %u objects with minimal distance %llu accuracy %f\n",
 774               size, (unsigned long long) min_distance, accuracy);
 775   }
 776 
 777   if (groupid == 2 && !skipped)
 778     /* we created a single group containing all objects, ignore it */
 779     return 0;
 780 
 781   /* return the last id, since it's also the number of used group ids */
 782   return groupid-1;
 783 }
 784 
 785 /* check that the matrix is ok */
 786 static int
 787 hwloc__check_grouping_matrix(unsigned nbobjs, uint64_t *_values, float accuracy, int verbose)
 788 {
 789   unsigned i,j;
 790   for(i=0; i<nbobjs; i++) {
 791     for(j=i+1; j<nbobjs; j++) {
 792       /* should be symmetric */
 793       if (hwloc_compare_values(VALUE(i, j), VALUE(j, i), accuracy)) {
 794         if (verbose)
 795           fprintf(stderr, " Distance matrix asymmetric ([%u,%u]=%llu != [%u,%u]=%llu), aborting\n",
 796                   i, j, (unsigned long long) VALUE(i, j), j, i, (unsigned long long) VALUE(j, i));
 797         return -1;
 798       }
 799       /* diagonal is smaller than everything else */
 800       if (hwloc_compare_values(VALUE(i, j), VALUE(i, i), accuracy) <= 0) {
 801         if (verbose)
 802           fprintf(stderr, " Distance to self not strictly minimal ([%u,%u]=%llu <= [%u,%u]=%llu), aborting\n",
 803                   i, j, (unsigned long long) VALUE(i, j), i, i, (unsigned long long) VALUE(i, i));
 804         return -1;
 805       }
 806     }
 807   }
 808   return 0;
 809 }
 810 
 811 /*
 812  * Look at object physical distances to group them.
 813  */
 814 static void
 815 hwloc__groups_by_distances(struct hwloc_topology *topology,
 816                            unsigned nbobjs,
 817                            struct hwloc_obj **objs,
 818                            uint64_t *_values,
 819                            unsigned long kind,
 820                            unsigned nbaccuracies,
 821                            float *accuracies,
 822                            int needcheck)
 823 {
 824   HWLOC_VLA(unsigned, groupids, nbobjs);
 825   unsigned nbgroups = 0;
 826   unsigned i,j;
 827   int verbose = topology->grouping_verbose;
 828 
 829   if (nbobjs <= 2)
 830       return;
 831 
 832   if (!(kind & HWLOC_DISTANCES_KIND_MEANS_LATENCY))
 833     /* don't know use to use those for grouping */
 834     /* TODO hwloc__find_groups_by_max_distance() for bandwidth */
 835     return;
 836 
 837   for(i=0; i<nbaccuracies; i++) {
 838     if (verbose)
 839       fprintf(stderr, "Trying to group %u %s objects according to physical distances with accuracy %f\n",
 840               nbobjs, hwloc_obj_type_string(objs[0]->type), accuracies[i]);
 841     if (needcheck && hwloc__check_grouping_matrix(nbobjs, _values, accuracies[i], verbose) < 0)
 842       continue;
 843     nbgroups = hwloc__find_groups_by_min_distance(nbobjs, _values, accuracies[i], groupids, verbose);
 844     if (nbgroups)
 845       break;
 846   }
 847   if (!nbgroups)
 848     return;
 849 
 850   {
 851       HWLOC_VLA(hwloc_obj_t, groupobjs, nbgroups);
 852       HWLOC_VLA(unsigned, groupsizes, nbgroups);
 853       HWLOC_VLA(uint64_t, groupvalues, nbgroups*nbgroups);
 854       unsigned failed = 0;
 855 
 856       /* create new Group objects and record their size */
 857       memset(&(groupsizes[0]), 0, sizeof(groupsizes[0]) * nbgroups);
 858       for(i=0; i<nbgroups; i++) {
 859           /* create the Group object */
 860           hwloc_obj_t group_obj, res_obj;
 861           group_obj = hwloc_alloc_setup_object(topology, HWLOC_OBJ_GROUP, HWLOC_UNKNOWN_INDEX);
 862           group_obj->cpuset = hwloc_bitmap_alloc();
 863           group_obj->attr->group.kind = HWLOC_GROUP_KIND_DISTANCE;
 864           group_obj->attr->group.subkind = topology->grouping_next_subkind;
 865           for (j=0; j<nbobjs; j++)
 866             if (groupids[j] == i+1) {
 867               /* assemble the group sets */
 868               hwloc_obj_add_other_obj_sets(group_obj, objs[j]);
 869               groupsizes[i]++;
 870             }
 871           hwloc_debug_1arg_bitmap("adding Group object with %u objects and cpuset %s\n",
 872                                   groupsizes[i], group_obj->cpuset);
 873           res_obj = hwloc__insert_object_by_cpuset(topology, NULL, group_obj,
 874                                                    (kind & HWLOC_DISTANCES_KIND_FROM_USER) ? hwloc_report_user_distance_error : hwloc_report_os_error);
 875           /* res_obj may be NULL on failure to insert. */
 876           if (!res_obj)
 877             failed++;
 878           /* or it may be different from groupobjs if we got groups from XML import before grouping */
 879           groupobjs[i] = res_obj;
 880       }
 881       topology->grouping_next_subkind++;
 882 
 883       if (failed)
 884         /* don't try to group above if we got a NULL group here, just keep this incomplete level */
 885         return;
 886 
 887       /* factorize values */
 888       memset(&(groupvalues[0]), 0, sizeof(groupvalues[0]) * nbgroups * nbgroups);
 889 #undef VALUE
 890 #define VALUE(i, j) _values[(i) * nbobjs + (j)]
 891 #define GROUP_VALUE(i, j) groupvalues[(i) * nbgroups + (j)]
 892       for(i=0; i<nbobjs; i++)
 893         if (groupids[i])
 894           for(j=0; j<nbobjs; j++)
 895             if (groupids[j])
 896                 GROUP_VALUE(groupids[i]-1, groupids[j]-1) += VALUE(i, j);
 897       for(i=0; i<nbgroups; i++)
 898           for(j=0; j<nbgroups; j++) {
 899               unsigned groupsize = groupsizes[i]*groupsizes[j];
 900               GROUP_VALUE(i, j) /= groupsize;
 901           }
 902 #ifdef HWLOC_DEBUG
 903       hwloc_debug("%s", "generated new distance matrix between groups:\n");
 904       hwloc_debug("%s", "  index");
 905       for(j=0; j<nbgroups; j++)
 906         hwloc_debug(" % 5d", (int) j); /* print index because os_index is -1 for Groups */
 907       hwloc_debug("%s", "\n");
 908       for(i=0; i<nbgroups; i++) {
 909         hwloc_debug("  % 5d", (int) i);
 910         for(j=0; j<nbgroups; j++)
 911           hwloc_debug(" %llu", (unsigned long long) GROUP_VALUE(i, j));
 912         hwloc_debug("%s", "\n");
 913       }
 914 #endif
 915 
 916       hwloc__groups_by_distances(topology, nbgroups, groupobjs, groupvalues, kind, nbaccuracies, accuracies, 0 /* no need to check generated matrix */);
 917   }
 918 }
/* [<][>][^][v][top][bottom][index][help] */