1 /*
2 * Copyright © 2013-2014 University of Wisconsin-La Crosse.
3 * All rights reserved.
4 * Copyright © 2016-2017 Inria. All rights reserved.
5 *
6 * $COPYRIGHT$
7 *
8 * Additional copyrights may follow
9 * See COPYING in top-level directory.
10 *
11 * $HEADER$
12 */
13
14 #define _GNU_SOURCE /* See feature_test_macros(7) */
15 #include <stdio.h>
16 #include <sys/types.h>
17 #include <dirent.h>
18 #include <libgen.h>
19
20 #include <private/netloc.h>
21
22 static char *line_get_next_field(char **string);
23 static void read_partition_list(char *list, UT_array *array);
24 static int edges_sort_by_dest(netloc_edge_t *a, netloc_edge_t *b);
25 static int find_reverse_edges(netloc_topology_t *topology);
26 static int find_similar_nodes(netloc_topology_t *topology);
27 static int netloc_node_get_virtual_id(char *id);
28 static int edge_merge_into(netloc_edge_t *dest, netloc_edge_t *src, int keep);
29
netloc_topology_construct(char * path)30 netloc_topology_t *netloc_topology_construct(char *path)
31 {
32 int ret;
33 char *line = NULL;
34 size_t linesize = 0;
35
36 netloc_topology_t *topology = NULL;
37
38 FILE *input = fopen(path, "r");
39
40 if (!input ) {
41 fprintf(stderr, "Cannot open topology file %s\n", path);
42 perror("fopen");
43 exit(-1);
44 }
45
46 int version;
47 if (fscanf(input , "%d\n,", &version) != 1) {
48 fprintf(stderr, "Cannot read the version number in %s\n", path);
49 perror("fscanf");
50 fclose(input);
51 return NULL;
52 } else if (version != NETLOCFILE_VERSION) {
53 fprintf(stderr, "Incorrect version number, "
54 "please generate your input file again\n");
55 fclose(input);
56 return NULL;
57 }
58
59 char *subnet;
60 if (netloc_line_get(&line, &linesize, input) == -1) {
61 fprintf(stderr, "Cannot read the subnet in %s\n", path);
62 perror("fscanf");
63 free(line);
64 fclose(input);
65 return NULL;
66 } else {
67 subnet = strdup(line);
68 }
69
70 char *hwlocpath;
71 if (netloc_line_get(&line, &linesize, input) == -1) {
72 fprintf(stderr, "Cannot read hwloc path in %s\n", path);
73 perror("fscanf");
74 free(subnet);
75 fclose(input);
76 return NULL;
77 } else if (!strlen(line)) {
78 hwlocpath = NULL;
79 } else {
80 hwlocpath = strdup(line);
81 }
82
83 if (hwlocpath) {
84 DIR *hwlocdir;
85 char *realhwlocpath;
86 if (hwlocpath[0] != '/') {
87 char *path_tmp = strdup(path);
88 asprintf(&realhwlocpath, "%s/%s", dirname(path_tmp), hwlocpath);
89 free(path_tmp);
90 } else {
91 realhwlocpath = strdup(hwlocpath);
92 }
93 if (!(hwlocdir = opendir(realhwlocpath))) {
94 fprintf(stderr, "Couldn't open hwloc directory: \"%s\"\n", realhwlocpath);
95 perror("opendir");
96 free(subnet);
97 free(realhwlocpath);
98 fclose(input);
99 return NULL;
100 } else {
101 closedir(hwlocdir);
102 free(realhwlocpath);
103 }
104 }
105
106 int num_nodes;
107 if (fscanf(input , "%d\n", &num_nodes) != 1) {
108 fprintf(stderr, "Cannot read the number of nodes in %s\n", path);
109 perror("fscanf");
110 free(subnet);
111 fclose(input);
112 return NULL;
113 }
114
115 if (num_nodes <= 0) {
116 fprintf(stderr, "Oups: incorrect number of nodes (%d) in %s\n",
117 num_nodes, path);
118 free(subnet);
119 fclose(input);
120 return NULL;
121 }
122
123 /*
124 * Allocate Memory
125 */
126 topology = (netloc_topology_t *)malloc(sizeof(netloc_topology_t) * 1);
127 if( NULL == topology ) {
128 free(subnet);
129 fclose(input);
130 return NULL;
131 }
132
133 /*
134 * Initialize the structure
135 */
136 topology->topopath = path;
137 topology->hwlocpath = hwlocpath;
138 topology->subnet_id = subnet;
139 topology->nodes = NULL;
140 topology->physical_links = NULL;
141 topology->type = NETLOC_TOPOLOGY_TYPE_INVALID ;
142 topology->nodesByHostname = NULL;
143 topology->hwloc_topos = NULL;
144 utarray_new(topology->partitions, &ut_str_icd);
145 utarray_new(topology->topos, &ut_str_icd);
146
147 /* Read nodes from file */
148 for (int n = 0; n < num_nodes; n++) {
149 netloc_node_t *node = netloc_node_construct();
150 netloc_line_get(&line, &linesize, input);
151 char *remain_line = line;
152
153 strncpy(node->physical_id, line_get_next_field(&remain_line), 20);
154 /* Should be shorter than 20 */
155 node->physical_id[19] = '\0'; /* If a problem occurs */
156 node->logical_id = atoi(line_get_next_field(&remain_line));
157 node->type = atoi(line_get_next_field(&remain_line));
158 read_partition_list(line_get_next_field(&remain_line), node->partitions);
159 node->description = strdup(line_get_next_field(&remain_line));
160 node->hostname = strdup(line_get_next_field(&remain_line));
161
162 HASH_ADD_STR(topology->nodes, physical_id, node);
163 if (strlen(node->hostname) > 0) {
164 HASH_ADD_KEYPTR(hh2, topology->nodesByHostname, node->hostname,
165 strlen(node->hostname), node);
166 }
167 }
168
169 /* Read edges from file */
170 for (int n = 0; n < num_nodes; n++) {
171 char *field;
172 netloc_node_t *node;
173
174 netloc_line_get(&line, &linesize, input);
175 char *remain_line = line;
176
177 field = line_get_next_field(&remain_line);
178 if (strlen(field) > 19)
179 field[19] = '\0';
180 HASH_FIND_STR(topology->nodes, field, node);
181
182 if (!node) {
183 fprintf(stderr, "Node not found: %s\n", field);
184 utarray_free(topology->partitions);
185 utarray_free(topology->topos);
186 return NULL;
187 }
188
189 while ((field = line_get_next_field(&remain_line))) {
190 /* There is an edge */
191 netloc_edge_t *edge = netloc_edge_construct();
192
193 HASH_FIND_STR(topology->nodes, field, edge->dest);
194 edge->total_gbits = strtof(line_get_next_field(&remain_line), NULL);
195 read_partition_list(line_get_next_field(&remain_line), edge->partitions);
196
197 edge->node = node;
198 HASH_ADD_PTR(node->edges, dest, edge);
199
200 /* Read links */
201 int num_links = atoi(line_get_next_field(&remain_line));
202 assert(num_links >= 0);
203 utarray_reserve(edge->physical_links, (unsigned int)num_links);
204 utarray_reserve(node->physical_links, (unsigned int)num_links);
205 for (int i = 0; i < num_links; i++) {
206 netloc_physical_link_t *link;
207 link = netloc_physical_link_construct();
208
209 link->id = atoi(line_get_next_field(&remain_line));
210
211 link->src = node;
212 link->dest = edge->dest;
213
214 link->ports[0] = atoi(line_get_next_field(&remain_line));
215 link->ports[1] = atoi(line_get_next_field(&remain_line));
216
217 link->width = strdup(line_get_next_field(&remain_line));
218 link->speed = strdup(line_get_next_field(&remain_line));
219 link->gbits = strtof(line_get_next_field(&remain_line), NULL);
220 link->description = strdup(line_get_next_field(&remain_line));
221 link->other_way_id = atoi(line_get_next_field(&remain_line));
222
223 read_partition_list(line_get_next_field(&remain_line),
224 link->partitions);
225
226 HASH_ADD_INT(topology->physical_links, id, link);
227
228 utarray_push_back(node->physical_links, &link);
229 utarray_push_back(edge->physical_links, &link);
230 }
231
232 }
233 HASH_SRT(hh, node->edges, edges_sort_by_dest);
234 }
235
236 /* Read partitions from file */
237 {
238 netloc_line_get(&line, &linesize, input);
239 char *remain_line = line;
240 char *field;
241
242 while ((field = line_get_next_field(&remain_line))) {
243 utarray_push_back(topology->partitions, &field);
244 }
245 }
246
247 /* Read paths */
248 while (netloc_line_get(&line, &linesize, input) != -1) {
249 netloc_node_t *node;
250 netloc_path_t *path;
251 char *field;
252
253 char *remain_line = line;
254 char *src_id = line_get_next_field(&remain_line);
255 char *dest_id = line_get_next_field(&remain_line);
256
257 HASH_FIND_STR(topology->nodes, src_id, node);
258
259 path = netloc_path_construct();
260 strncpy(path->dest_id, dest_id, 20); /* Should be shorter than 20 */
261 path->dest_id[19] = '\0'; /* If a problem occurs */
262
263 while ((field = line_get_next_field(&remain_line))) {
264 int link_id = atoi(field);
265 netloc_physical_link_t *link;
266
267 HASH_FIND_INT(topology->physical_links, &link_id, link);
268 utarray_push_back(path->links, &link);
269 }
270
271 HASH_ADD_STR(node->paths, dest_id, path);
272 }
273
274 fclose(input);
275 free(line);
276
277 if (find_reverse_edges(topology) != NETLOC_SUCCESS) {
278 netloc_topology_destruct(topology);
279 return NULL;
280 }
281
282 ret = find_similar_nodes(topology);
283 if (ret != NETLOC_SUCCESS) {
284 netloc_topology_destruct(topology);
285 return NULL;
286 }
287
288 return topology;
289 }
290
netloc_topology_destruct(netloc_topology_t * topology)291 int netloc_topology_destruct(netloc_topology_t *topology)
292 {
293 /*
294 * Sanity Check
295 */
296 if( NULL == topology ) {
297 fprintf(stderr, "Error: Detaching from a NULL pointer\n");
298 return NETLOC_ERROR;
299 }
300
301 free(topology->topopath);
302 free(topology->hwlocpath);
303 free(topology->subnet_id);
304
305 /* Nodes */
306 netloc_node_t *node, *node_tmp;
307 HASH_ITER(hh, topology->nodes, node, node_tmp) {
308 HASH_DELETE(hh, topology->nodes, node);
309 }
310
311 netloc_topology_iter_nodes(topology, node, node_tmp) {
312 HASH_DELETE(hh, topology->nodes, node);
313 netloc_node_destruct(node);
314 }
315
316 /** Partition List */
317 utarray_free(topology->partitions);
318
319 /** Physical links */
320 netloc_physical_link_t *link, *link_tmp;
321 HASH_ITER(hh, topology->physical_links, link, link_tmp) {
322 HASH_DEL(topology->physical_links, link);
323 netloc_physical_link_destruct(link);
324 }
325
326 /** Hwloc topology List */
327 for (unsigned int t = 0; t < utarray_len(topology->topos); t++) {
328 if (topology->hwloc_topos[t])
329 hwloc_topology_destroy(topology->hwloc_topos[t]);
330 }
331 free(topology->hwloc_topos);
332
333 /** Hwloc topology name List */
334 utarray_free(topology->topos);
335
336 free(topology);
337
338 return NETLOC_SUCCESS;
339 }
340
netloc_topology_find_partition_idx(netloc_topology_t * topology,char * partition_name)341 int netloc_topology_find_partition_idx(netloc_topology_t *topology, char *partition_name)
342 {
343 if (!partition_name)
344 return -1;
345
346 /* Find the selected partition in the topology */
347 unsigned int p = 0;
348 int found = 0;
349 while (p < utarray_len(topology->partitions)) {
350 char *current_name = *(char **)utarray_eltptr(topology->partitions, p);
351
352 if (!strcmp(current_name, partition_name)) {
353 found = 1;
354 break;
355 }
356 p++;
357 }
358
359 if (!found)
360 return -2;
361
362 assert(p <= INT_MAX);
363
364 return (int)p;
365 }
366
line_get_next_field(char ** string)367 static char *line_get_next_field(char **string)
368 {
369 return netloc_line_get_next_token(string, ',');
370 }
371
read_partition_list(char * list,UT_array * array)372 static void read_partition_list(char *list, UT_array *array)
373 {
374 char *partition;
375 if (!strlen(list))
376 return;
377 while ((partition = netloc_line_get_next_token(&list, ':'))) {
378 int partition_num = atoi(partition);
379 utarray_push_back(array, &partition_num);
380 }
381 }
382
edges_sort_by_dest(netloc_edge_t * a,netloc_edge_t * b)383 static int edges_sort_by_dest(netloc_edge_t *a, netloc_edge_t *b)
384 {
385 return strcmp(a->dest->physical_id, b->dest->physical_id);
386 }
387
find_reverse_edges(netloc_topology_t * topology)388 static int find_reverse_edges(netloc_topology_t *topology)
389 {
390 netloc_node_t *node, *node_tmp;
391 HASH_ITER(hh, topology->nodes, node, node_tmp) {
392 netloc_edge_t *edge, *edge_tmp;
393 netloc_node_iter_edges(node, edge, edge_tmp) {
394 netloc_node_t *dest = edge->dest;
395 if (dest > node) {
396 netloc_edge_t *reverse_edge;
397 HASH_FIND_PTR(dest->edges, &node, reverse_edge);
398 if (reverse_edge == NULL) {
399 return NETLOC_ERROR;
400 }
401 edge->other_way = reverse_edge;
402 reverse_edge->other_way = edge;
403 }
404 }
405 }
406 return NETLOC_SUCCESS;
407 }
408
find_similar_nodes(netloc_topology_t * topology)409 static int find_similar_nodes(netloc_topology_t * topology)
410 {
411 int ret;
412
413 /* Build edge lists by node */
414 int num_nodes = HASH_COUNT(topology->nodes);
415 netloc_node_t **nodes = (netloc_node_t **)malloc(num_nodes*sizeof(netloc_node_t *));
416 netloc_node_t ***edgedest_by_node = (netloc_node_t ***)malloc(num_nodes*sizeof(netloc_node_t **));
417 int *num_edges_by_node = (int *)malloc(num_nodes*sizeof(int));
418 netloc_node_t *node, *node_tmp;
419 int idx = -1;
420 netloc_topology_iter_nodes(topology, node, node_tmp) {
421 idx++;
422 if (netloc_node_is_host(node)) {
423 nodes[idx] = NULL;
424 edgedest_by_node[idx] = NULL;
425 continue;
426 }
427 int num_edges = HASH_COUNT(node->edges);
428 nodes[idx] = node;
429 num_edges_by_node[idx] = num_edges;
430 edgedest_by_node[idx] = (netloc_node_t **)malloc(num_edges*sizeof(netloc_node_t *));
431
432 netloc_edge_t *edge, *edge_tmp;
433 int edge_idx = 0;
434 netloc_node_iter_edges(node, edge, edge_tmp) {
435 edgedest_by_node[idx][edge_idx] = edge->dest;
436 edge_idx++;
437 }
438 }
439
440 /* We compare the edge lists to find similar nodes */
441 UT_array *similar_nodes;
442 utarray_new(similar_nodes, &ut_ptr_icd);
443 for (int idx1 = 0; idx1 < num_nodes; idx1++) {
444 netloc_node_t *node1 = nodes[idx1];
445 netloc_node_t *virtual_node = NULL;
446 netloc_edge_t *first_virtual_edge = NULL;
447 if (!node1)
448 continue;
449 for (int idx2 = idx1+1; idx2 < num_nodes; idx2++) {
450 netloc_node_t *node2 = nodes[idx2];
451 if (!node2)
452 continue;
453 if (num_edges_by_node[idx2] != num_edges_by_node[idx1])
454 continue;
455 if (idx2 == idx1)
456 continue;
457
458 int equal = 1;
459 for (int i = 0; i < num_edges_by_node[idx1]; i++) {
460 if (edgedest_by_node[idx2][i] != edgedest_by_node[idx1][i]) {
461 equal = 0;
462 break;
463 }
464 }
465
466 /* If we have similar nodes */
467 if (equal) {
468 /* We create a new virtual node to contain all of them */
469 if (!virtual_node) {
470 virtual_node = netloc_node_construct();
471 netloc_node_get_virtual_id(virtual_node->physical_id);
472
473 virtual_node->type = node1->type;
474 utarray_concat(virtual_node->physical_links, node1->physical_links);
475 virtual_node->description = strdup(virtual_node->physical_id);
476
477 utarray_push_back(virtual_node->subnodes, &node1);
478 utarray_concat(virtual_node->partitions, node1->partitions);
479
480 // TODO paths
481
482 /* Set edges */
483 netloc_edge_t *edge1, *edge_tmp1;
484 netloc_node_iter_edges(node1, edge1, edge_tmp1) {
485 netloc_edge_t *virtual_edge = netloc_edge_construct();
486 if (!first_virtual_edge)
487 first_virtual_edge = virtual_edge;
488 virtual_edge->node = virtual_node;
489 virtual_edge->dest = edge1->dest;
490 ret = edge_merge_into(virtual_edge, edge1, 0);
491 if (ret != NETLOC_SUCCESS) {
492 netloc_edge_destruct(virtual_edge);
493 goto ERROR;
494 }
495 HASH_ADD_PTR(virtual_node->edges, dest, virtual_edge);
496
497 /* Change the reverse edge of the neighbours (reverse nodes) */
498 netloc_node_t *reverse_node = edge1->dest;
499 netloc_edge_t *reverse_edge = edge1->other_way;
500
501 netloc_edge_t *reverse_virtual_edge =
502 netloc_edge_construct();
503 reverse_virtual_edge->dest = virtual_node;
504 reverse_virtual_edge->node = reverse_node;
505 reverse_virtual_edge->other_way = virtual_edge;
506 virtual_edge->other_way = reverse_virtual_edge;
507 HASH_ADD_PTR(reverse_node->edges, dest, reverse_virtual_edge);
508 ret = edge_merge_into(reverse_virtual_edge, reverse_edge, 1);
509 if (ret != NETLOC_SUCCESS) {
510 goto ERROR;
511 }
512 HASH_DEL(reverse_node->edges, reverse_edge);
513 }
514
515 /* We remove the node from the list of nodes */
516 HASH_DEL(topology->nodes, node1);
517 HASH_ADD_STR(topology->nodes, physical_id, virtual_node);
518 printf("First node found: %s (%s)\n", node1->description, node1->physical_id);
519 }
520
521 utarray_concat(virtual_node->physical_links, node2->physical_links);
522 utarray_push_back(virtual_node->subnodes, &node2);
523 utarray_concat(virtual_node->partitions, node2->partitions);
524
525 /* Set edges */
526 netloc_edge_t *edge2, *edge_tmp2;
527 netloc_edge_t *virtual_edge = first_virtual_edge;
528 netloc_node_iter_edges(node2, edge2, edge_tmp2) {
529 /* Merge the edges from the physical node into the virtual node */
530 ret = edge_merge_into(virtual_edge, edge2, 0);
531 if (ret != NETLOC_SUCCESS) {
532 goto ERROR;
533 }
534
535 /* Change the reverse edge of the neighbours (reverse nodes) */
536 netloc_node_t *reverse_node = edge2->dest;
537 netloc_edge_t *reverse_edge = edge2->other_way;
538
539 netloc_edge_t *reverse_virtual_edge;
540 HASH_FIND_PTR(reverse_node->edges, &virtual_node,
541 reverse_virtual_edge);
542 ret = edge_merge_into(reverse_virtual_edge, reverse_edge, 1);
543 if (ret != NETLOC_SUCCESS) {
544 goto ERROR;
545 }
546 HASH_DEL(reverse_node->edges, reverse_edge);
547
548 /* Get the next edge */
549 virtual_edge = virtual_edge->hh.next;
550 }
551
552 /* We remove the node from the list of nodes */
553 HASH_DEL(topology->nodes, node2);
554 printf("\t node found: %s (%s)\n", node2->description, node2->physical_id);
555
556 nodes[idx2] = NULL;
557 }
558 }
559 utarray_clear(similar_nodes);
560 }
561
562 ret = NETLOC_SUCCESS;
563 ERROR:
564 free(nodes);
565
566 for (int idx = 0; idx < num_nodes; idx++) {
567 if (edgedest_by_node[idx])
568 free(edgedest_by_node[idx]);
569 }
570 free(edgedest_by_node);
571 free(num_edges_by_node);
572 free(similar_nodes);
573 return ret;
574 }
575
netloc_node_get_virtual_id(char * id)576 static int netloc_node_get_virtual_id(char *id)
577 {
578 static int virtual_id = 0;
579 sprintf(id, "virtual%d", virtual_id++);
580 return 0;
581 }
582
edge_merge_into(netloc_edge_t * dest,netloc_edge_t * src,int keep)583 static int edge_merge_into(netloc_edge_t *dest, netloc_edge_t *src, int keep)
584 {
585 if (!dest || !src) {
586 return NETLOC_ERROR;
587 }
588
589 utarray_concat(dest->physical_links, src->physical_links);
590 dest->total_gbits += src->total_gbits;
591 utarray_concat(dest->partitions, src->partitions);
592 /* it will keep the duplicated edges */
593 if (keep)
594 utarray_push_back(dest->subnode_edges, &src);
595
596 return NETLOC_SUCCESS;
597 }
598
599