1 /*
2  * This file and its contents are supplied under the terms of the
3  * Common Development and Distribution License ("CDDL"), version 1.0.
4  * You may only use this file in accordance with the terms of version
5  * 1.0 of the CDDL.
6  *
7  * A full copy of the text of the CDDL should have accompanied this
8  * source.  A copy of the CDDL is also available via the Internet at
9  * http://www.illumos.org/license/CDDL.
10  */
11 
12 /*
13  * Copyright 2020 Joyent, Inc.
14  */
15 
16 /*
17  * This file implements a set of APIs for creating, destroying and traversing
18  * directed-graph (digraph) topologies.  The API is split into categories:
19  * client API and module API.
20  *
21  * The client API can be used by libtopo consumers for traversing an existing
22  * digraph topology.  The module API can be used by topo plugins to create or
23  * destroy a digraph topology.
24  *
25  * client API
26  * ----------
27  * topo_digraph_get
28  * topo_vertex_iter
29  * topo_vertex_node
30  * topo_edge_iter
31  * topo_digraph_paths
32  * topo_path_destroy
33  *
34  * module API
35  * ----------
36  * topo_digraph_new
37  * topo_digraph_destroy
38  * topo_vertex_new
39  * topo_vertex_destroy
40  * topo_edge_new
41  *
42  * A digraph is represented in-core by a topo_digraph_t structure which
43  * maintains an adjacency list of vertices (see topo_digraph.h).  Vertices
44  * are represented by topo_vertex_t structures which are essentially thin
45  * wrappers around topo node (tnode_t) structures.  In addition to holding
46  * a pointer to the underlyng topo node, the topo_vertex_t maintains a list
47  * of incoming and outgoing edges and a pointer to the next and previous
48  * vertices in digraph's adjecency list.
49  *
50  * Locking
51  * -------
52  * The module APIs should only be used during snapshot creation, which is
53  * single-threaded, or as the result of a call to topo_snap_release() or
54  * topo_close().  While libtopo does prevent concurrent calls to
55  * topo_snap_release() and topo_close() via the topo_hdl_t lock, there is no
56  * mechanism currently that prevents the situation where one or more threads
57  * were to access the snapshot (e.g. they've got a cached tnode_t ptr or are
58  * walking the snapshot) while another thread is calling topo_snap_release()
59  * or topo_close().  The same is true for tree topologies.  It is up to the
60  * library consumer to provide their own synchronization or reference counting
61  * mechanism for that case. For example, fmd implements a reference counting
62  * mechanism around topo snapshots so that individual fmd modules can safely
63  * cache pointers to a given topo snapshot.
64  *
65  * None of the client APIs modify the state of the graph structure once
66  * the snapshot is created.  The exception is the state of the underlyng topo
67  * nodes for each vertex, who's properties may change as a result of the
68  * following:
69  *
70  * 1) topo_prop_get operations for properties that are backed by topo methods
71  * 2) topo_prop_set operations.
72  *
73  * For both of the above situations, synchronization is enforced by the per-node
74  * locks. Thus there a no locks used for synchronizing access to
75  * the topo_digraph_t or topo_vertex_t structures.
76  *
77  * path scheme FMRIs
78  * -----------------
79  * For digraph topologies it is useful to be able to treat paths between
80  * vertices as resources and thus have a way to represent a unique path
81  * between those vertices.  The path FMRI scheme is used for this purpose and
82  * has the following form:
83  *
84  * path://scheme=<scheme>/<nodename>=<instance>/...
85  *
86  * The path FMRI for a path from one vertex to another vertex is represented by
87  * a sequence of nodename/instance pairs where each pair represents a vertex on
88  * the path between the two vertices.  The first nodename/instance pair
89  * represents the "from" vertex and the last nodename/instance pair represents
90  * the "to" vertex.
91  *
92  * For example, the path FMRI to represent a path from an initiator to a
93  * target in a SAS scheme digraph might look like this:
94  *
95  * path://scheme=sas/initiator=5003048023567a00/port=5003048023567a00/
96  *       port=500304801861347f/expander=500304801861347f/port=500304801861347f/
97  *       port=5000c500adc881d5/target=5000c500adc881d4
98  *
99  * This file implements NVL2STR and STR2NVL methods for path-scheme FMRIs.
100  */
101 
102 #include <libtopo.h>
103 #include <sys/fm/protocol.h>
104 
105 #include <topo_digraph.h>
106 #include <topo_method.h>
107 
108 #define	__STDC_FORMAT_MACROS
109 #include <inttypes.h>
110 
111 
112 extern int path_fmri_str2nvl(topo_mod_t *, tnode_t *, topo_version_t,
113     nvlist_t *, nvlist_t **);
114 extern int path_fmri_nvl2str(topo_mod_t *, tnode_t *, topo_version_t,
115     nvlist_t *, nvlist_t **);
116 
117 static const topo_method_t digraph_root_methods[] = {
118 	{ TOPO_METH_PATH_STR2NVL, TOPO_METH_STR2NVL_DESC,
119 	    TOPO_METH_STR2NVL_VERSION, TOPO_STABILITY_INTERNAL,
120 	    path_fmri_str2nvl },
121 	{ TOPO_METH_PATH_NVL2STR, TOPO_METH_NVL2STR_DESC,
122 	    TOPO_METH_NVL2STR_VERSION, TOPO_STABILITY_INTERNAL,
123 	    path_fmri_nvl2str },
124 	{ NULL }
125 };
126 
127 /*
128  * On success, returns a pointer to the digraph for the specified FMRI scheme.
129  * On failure, returns NULL.
130  */
131 topo_digraph_t *
topo_digraph_get(topo_hdl_t * thp,const char * scheme)132 topo_digraph_get(topo_hdl_t *thp, const char *scheme)
133 {
134 	topo_digraph_t *tdg;
135 
136 	for (tdg = topo_list_next(&thp->th_digraphs); tdg != NULL;
137 	    tdg = topo_list_next(tdg)) {
138 		if (strcmp(scheme, tdg->tdg_scheme) == 0)
139 			return (tdg);
140 	}
141 	return (NULL);
142 }
143 
144 static topo_digraph_t *
find_digraph(topo_mod_t * mod)145 find_digraph(topo_mod_t *mod)
146 {
147 	return (topo_digraph_get(mod->tm_hdl, mod->tm_info->tmi_scheme));
148 }
149 
150 /*
151  * On successs, allocates a new topo_digraph_t structure for the requested
152  * scheme.  The caller is responsible for free all memory allocated for this
153  * structure when done via a call to topo_digraph_destroy().
154  *
155  * On failure, this function returns NULL and sets topo errno.
156  */
157 topo_digraph_t *
topo_digraph_new(topo_hdl_t * thp,topo_mod_t * mod,const char * scheme)158 topo_digraph_new(topo_hdl_t *thp, topo_mod_t *mod, const char *scheme)
159 {
160 	topo_digraph_t *tdg;
161 	tnode_t *tn = NULL;
162 
163 	if ((tdg = topo_mod_zalloc(mod, sizeof (topo_digraph_t))) == NULL) {
164 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
165 		return (NULL);
166 	}
167 
168 	tdg->tdg_mod = mod;
169 
170 	if ((tdg->tdg_scheme = topo_mod_strdup(mod, scheme)) == NULL) {
171 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
172 		goto err;
173 	}
174 
175 	/*
176 	 * For digraph topologies, the "root" node, which gets passed in to
177 	 * the scheme module's enum method is not part of the actual graph
178 	 * structure per-se.
179 	 * Its purpose is simply to provide a place on which to register the
180 	 * scheme-specific methods.  Client code then invokes these methods via
181 	 * the topo_fmri_* interfaces.
182 	 */
183 	if ((tn = topo_mod_zalloc(mod, sizeof (tnode_t))) == NULL)
184 		goto err;
185 
186 	/*
187 	 * Adding the TOPO_NODE_ROOT state to the node has the effect of
188 	 * preventing topo_node_destroy() from trying to clean up the parent
189 	 * node's node hash, which is only necessary in tree topologies.
190 	 */
191 	tn->tn_state = TOPO_NODE_ROOT | TOPO_NODE_INIT;
192 	tn->tn_name = (char *)scheme;
193 	tn->tn_instance = 0;
194 	tn->tn_enum = mod;
195 	tn->tn_hdl = thp;
196 	topo_node_hold(tn);
197 
198 	tdg->tdg_rootnode = tn;
199 	if (topo_method_register(mod, tn, digraph_root_methods) != 0) {
200 		topo_mod_dprintf(mod, "failed to register digraph root "
201 		    "methods");
202 		/* errno set */
203 		return (NULL);
204 	}
205 
206 	/* This is released during topo_digraph_destroy() */
207 	topo_mod_hold(mod);
208 
209 	return (tdg);
210 err:
211 	topo_mod_free(mod, tdg, sizeof (topo_digraph_t));
212 	return (NULL);
213 }
214 
215 /*
216  * Deallocates all memory associated with the specified topo_digraph_t.
217  *
218  * This only frees the memory allocated during topo_digraph_new().  To free the
219  * actual graph vertices one should call topo_snap_destroy() prior to calling
220  * topo_digraph_destroy().
221  *
222  * Calling topo_close() will also result in a call to topo_snap_destroy() and
223  * topo_digraph_dstroy() for all digraphs associated with the library handle.
224  *
225  * This function is a NOP if NULL is passed in.
226  */
227 void
topo_digraph_destroy(topo_digraph_t * tdg)228 topo_digraph_destroy(topo_digraph_t *tdg)
229 {
230 	topo_mod_t *mod;
231 
232 	if (tdg == NULL)
233 		return;
234 
235 	mod = tdg->tdg_mod;
236 	topo_method_unregister_all(mod, tdg->tdg_rootnode);
237 	topo_mod_strfree(mod, (char *)tdg->tdg_scheme);
238 	topo_mod_free(mod, tdg->tdg_rootnode, sizeof (tnode_t));
239 	topo_mod_free(mod, tdg, sizeof (topo_digraph_t));
240 	topo_mod_rele(mod);
241 }
242 
243 /*
244  * This function creates a new vertex and adds it to the digraph associated
245  * with the module.
246  *
247  * name: name of the vertex
248  * instance: instance number of the vertex
249  *
250  * On success, it returns a pointer to the allocated topo_vertex_t associated
251  * with the new vertex.  The caller is responsible for free-ing this structure
252  * via a call to topo_vertex_destroy().
253  *
254  * On failures, this function returns NULL and sets topo_mod_errno.
255  */
256 topo_vertex_t *
topo_vertex_new(topo_mod_t * mod,const char * name,topo_instance_t inst)257 topo_vertex_new(topo_mod_t *mod, const char *name, topo_instance_t inst)
258 {
259 	tnode_t *tn = NULL;
260 	topo_vertex_t *vtx = NULL;
261 	topo_digraph_t *tdg;
262 
263 	topo_mod_dprintf(mod, "Creating vertex %s=%" PRIx64 "", name, inst);
264 	if ((tdg = find_digraph(mod)) == NULL) {
265 		topo_mod_dprintf(mod, "%s faild: no existing digraph for FMRI "
266 		    " scheme %s", __func__, mod->tm_info->tmi_scheme);
267 		return (NULL);
268 	}
269 	if ((vtx = topo_mod_zalloc(mod, sizeof (topo_vertex_t))) == NULL ||
270 	    (tn = topo_mod_zalloc(mod, sizeof (tnode_t))) == NULL) {
271 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
272 		goto err;
273 	}
274 	if ((tn->tn_name = topo_mod_strdup(mod, name)) == NULL) {
275 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
276 		goto err;
277 	}
278 	tn->tn_enum = mod;
279 	tn->tn_hdl = mod->tm_hdl;
280 	tn->tn_vtx = vtx;
281 	tn->tn_instance = inst;
282 	/*
283 	 * Adding the TOPO_NODE_ROOT state to the node has the effect of
284 	 * preventing topo_node_destroy() from trying to clean up the parent
285 	 * node's node hash, which is only necessary in tree topologies.
286 	 */
287 	tn->tn_state = TOPO_NODE_ROOT | TOPO_NODE_BOUND;
288 	vtx->tvt_node = tn;
289 	topo_node_hold(tn);
290 
291 	/* Bump the refcnt on the module that's creating this vertex. */
292 	topo_mod_hold(mod);
293 
294 	if (tdg->tdg_nvertices == UINT32_MAX) {
295 		topo_mod_dprintf(mod, "Max vertices reached!");
296 		(void) topo_mod_seterrno(mod, EMOD_DIGRAPH_MAXSZ);
297 		topo_mod_rele(mod);
298 		goto err;
299 	}
300 	tdg->tdg_nvertices++;
301 	topo_list_append(&tdg->tdg_vertices, vtx);
302 
303 	return (vtx);
304 err:
305 	topo_mod_dprintf(mod, "failed to add create vertex %s=%" PRIx64 "(%s)",
306 	    name, inst, topo_strerror(topo_mod_errno(mod)));
307 	if (tn != NULL) {
308 		topo_mod_strfree(mod, tn->tn_name);
309 		topo_mod_free(mod, tn, sizeof (tnode_t));
310 	}
311 	if (vtx != NULL)
312 		topo_mod_free(mod, vtx, sizeof (topo_vertex_t));
313 
314 	return (NULL);
315 }
316 
317 /*
318  * Returns the underlying tnode_t structure for the specified vertex.
319  */
320 tnode_t *
topo_vertex_node(topo_vertex_t * vtx)321 topo_vertex_node(topo_vertex_t *vtx)
322 {
323 	return (vtx->tvt_node);
324 }
325 
326 /*
327  * Convenience interface for deallocating a topo_vertex_t
328  * This function is a NOP if NULL is passed in.
329  */
330 void
topo_vertex_destroy(topo_mod_t * mod,topo_vertex_t * vtx)331 topo_vertex_destroy(topo_mod_t *mod, topo_vertex_t *vtx)
332 {
333 	topo_edge_t *edge;
334 
335 	if (vtx == NULL)
336 		return;
337 
338 	topo_node_unbind(vtx->tvt_node);
339 
340 	edge = topo_list_next(&vtx->tvt_incoming);
341 	while (edge != NULL) {
342 		topo_edge_t *tmp = edge;
343 
344 		edge = topo_list_next(edge);
345 		topo_mod_free(mod, tmp, sizeof (topo_edge_t));
346 	}
347 
348 	edge = topo_list_next(&vtx->tvt_outgoing);
349 	while (edge != NULL) {
350 		topo_edge_t *tmp = edge;
351 
352 		edge = topo_list_next(edge);
353 		topo_mod_free(mod, tmp, sizeof (topo_edge_t));
354 	}
355 
356 	topo_mod_free(mod, vtx, sizeof (topo_vertex_t));
357 }
358 
359 /*
360  * This function can be used to iterate over all of the vertices in the
361  * specified digraph.  The specified callback function is invoked for each
362  * vertices.  Callback function should return the standard topo walker
363  * (TOPO_WALK_*) return values.
364  *
365  * On success, this function returns 0.
366  *
367  * On failure this function returns -1.
368  */
369 int
topo_vertex_iter(topo_hdl_t * thp,topo_digraph_t * tdg,int (* func)(topo_hdl_t *,topo_vertex_t *,boolean_t,void *),void * arg)370 topo_vertex_iter(topo_hdl_t *thp, topo_digraph_t *tdg,
371     int (*func)(topo_hdl_t *, topo_vertex_t *, boolean_t, void *), void *arg)
372 {
373 	uint_t n = 0;
374 
375 	for (topo_vertex_t *vtx = topo_list_next(&tdg->tdg_vertices);
376 	    vtx != NULL; vtx = topo_list_next(vtx), n++) {
377 		int ret;
378 		boolean_t last_vtx = B_FALSE;
379 
380 		if (n == (tdg->tdg_nvertices - 1))
381 			last_vtx = B_TRUE;
382 
383 		ret = func(thp, vtx, last_vtx, arg);
384 
385 		switch (ret) {
386 		case TOPO_WALK_NEXT:
387 			continue;
388 		case TOPO_WALK_TERMINATE:
389 			goto out;
390 		case TOPO_WALK_ERR:
391 		default:
392 			return (-1);
393 		}
394 	}
395 out:
396 	return (0);
397 }
398 
399 /*
400  * Add a new outgoing edge the vertex "from" to the vertex "to".
401  *
402  * On success, this functions returns 0.
403  *
404  * On failure, this function returns -1.
405  */
406 int
topo_edge_new(topo_mod_t * mod,topo_vertex_t * from,topo_vertex_t * to)407 topo_edge_new(topo_mod_t *mod, topo_vertex_t *from, topo_vertex_t *to)
408 {
409 	topo_digraph_t *tdg;
410 	topo_edge_t *e_from = NULL, *e_to = NULL;
411 
412 	topo_mod_dprintf(mod, "Adding edge from vertex %s=%" PRIx64 " to "
413 	    "%s=%" PRIx64"", topo_node_name(from->tvt_node),
414 	    topo_node_instance(from->tvt_node),
415 	    topo_node_name(to->tvt_node), topo_node_instance(to->tvt_node));
416 
417 	if ((tdg = find_digraph(mod)) == NULL) {
418 		topo_mod_dprintf(mod, "Digraph lookup failed");
419 		return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
420 	}
421 	if (from->tvt_noutgoing == UINT32_MAX ||
422 	    to->tvt_nincoming == UINT32_MAX ||
423 	    tdg->tdg_nedges == UINT32_MAX) {
424 		topo_mod_dprintf(mod, "Max edges reached!");
425 		return (topo_mod_seterrno(mod, EMOD_DIGRAPH_MAXSZ));
426 
427 	}
428 	if ((e_from = topo_mod_zalloc(mod, sizeof (topo_edge_t))) == NULL ||
429 	    (e_to = topo_mod_zalloc(mod, sizeof (topo_edge_t))) == NULL) {
430 		topo_mod_free(mod, e_from, sizeof (topo_edge_t));
431 		topo_mod_free(mod, e_to, sizeof (topo_edge_t));
432 		return (topo_mod_seterrno(mod, EMOD_NOMEM));
433 	}
434 	e_from->tve_vertex = from;
435 	e_to->tve_vertex = to;
436 
437 	topo_list_append(&from->tvt_outgoing, e_to);
438 	from->tvt_noutgoing++;
439 	topo_list_append(&to->tvt_incoming, e_from);
440 	to->tvt_nincoming++;
441 	tdg->tdg_nedges++;
442 
443 	return (0);
444 }
445 
446 /*
447  * This function can be used to iterate over all of the outgoing edges in
448  * for specified vertex.  The specified callback function is invoked for each
449  * edge.  Callback function should return the standard topo walker
450  * (TOPO_WALK_*) return values.
451  *
452  * On success, this function returns 0.
453  *
454  * On failure this function returns -1.
455  */
456 int
topo_edge_iter(topo_hdl_t * thp,topo_vertex_t * vtx,int (* func)(topo_hdl_t *,topo_edge_t *,boolean_t,void *),void * arg)457 topo_edge_iter(topo_hdl_t *thp, topo_vertex_t *vtx,
458     int (*func)(topo_hdl_t *, topo_edge_t *, boolean_t, void *), void *arg)
459 {
460 	uint_t n = 0;
461 
462 	for (topo_edge_t *edge = topo_list_next(&vtx->tvt_outgoing);
463 	    edge != NULL; edge = topo_list_next(edge), n++) {
464 		int ret;
465 		boolean_t last_edge = B_FALSE;
466 
467 		if (n == (vtx->tvt_noutgoing - 1))
468 			last_edge = B_TRUE;
469 
470 		ret = func(thp, edge, last_edge, arg);
471 
472 		switch (ret) {
473 		case TOPO_WALK_NEXT:
474 			continue;
475 		case TOPO_WALK_TERMINATE:
476 			break;
477 		case TOPO_WALK_ERR:
478 		default:
479 			return (-1);
480 		}
481 	}
482 	return (0);
483 }
484 
485 /*
486  * Convenience interface for deallocating a topo_path_t
487  * This function is a NOP if NULL is passed in.
488  */
489 void
topo_path_destroy(topo_hdl_t * thp,topo_path_t * path)490 topo_path_destroy(topo_hdl_t *thp, topo_path_t *path)
491 {
492 	topo_path_component_t *pathcomp;
493 
494 	if (path == NULL)
495 		return;
496 
497 	topo_hdl_strfree(thp, (char *)path->tsp_fmristr);
498 	nvlist_free(path->tsp_fmri);
499 
500 	pathcomp = topo_list_next(&path->tsp_components);
501 	while (pathcomp != NULL) {
502 		topo_path_component_t *tmp = pathcomp;
503 
504 		pathcomp = topo_list_next(pathcomp);
505 		topo_hdl_free(thp, tmp, sizeof (topo_path_component_t));
506 	}
507 
508 	topo_hdl_free(thp, path, sizeof (topo_path_t));
509 }
510 
511 /*
512  * This just wraps topo_path_t so that visit_vertex() can build a linked list
513  * of paths.
514  */
515 struct digraph_path {
516 	topo_list_t	dgp_link;
517 	topo_path_t	*dgp_path;
518 };
519 
520 /*
521  * This is a callback function for the vertex iteration that gets initiated by
522  * topo_digraph_paths().
523  *
524  * This is used to implement a depth-first search for all paths that lead to
525  * the vertex pointed to by the "to" parameter.  As we walk the graph we
526  * maintain a linked list of the components (vertices) in the in-progress path
527  * as well as the string form of the current path being walked.  Whenever we
528  * eoncounter the "to" vertex, we save the current path to the all_paths list
529  * (which keeps track of all the paths we've found to the "to" vertex) and
530  * increment npaths (which keeps track of the number of paths we've found to
531  * the "to" vertex).
532  */
533 static int
visit_vertex(topo_hdl_t * thp,topo_vertex_t * vtx,topo_vertex_t * to,topo_list_t * all_paths,const char * curr_path,topo_list_t * curr_path_comps,uint_t * npaths)534 visit_vertex(topo_hdl_t *thp, topo_vertex_t *vtx, topo_vertex_t *to,
535     topo_list_t *all_paths, const char *curr_path,
536     topo_list_t *curr_path_comps, uint_t *npaths)
537 {
538 	struct digraph_path *pathnode = NULL;
539 	topo_path_t *path = NULL;
540 	topo_path_component_t *pathcomp = NULL;
541 	nvlist_t *fmri = NULL;
542 	char *pathstr;
543 	int err;
544 
545 	if (asprintf(&pathstr, "%s/%s=%" PRIx64"",
546 	    curr_path,
547 	    topo_node_name(vtx->tvt_node),
548 	    topo_node_instance(vtx->tvt_node)) < 0) {
549 		return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
550 	}
551 
552 	/*
553 	 * Check if this vertex is in the list of vertices in the
554 	 * curr_path_comps list.  If it is, then we've encountered a cycle
555 	 * and need to turn back.
556 	 */
557 	for (topo_path_component_t *pc = topo_list_next(curr_path_comps);
558 	    pc != NULL; pc = topo_list_next(pc)) {
559 		if (pc->tspc_vertex == vtx) {
560 			topo_dprintf(thp, TOPO_DBG_WALK, "Cycle detected: %s",
561 			    pathstr);
562 			free(pathstr);
563 			return (0);
564 		}
565 	}
566 
567 	if ((pathcomp = topo_hdl_zalloc(thp, sizeof (topo_path_component_t)))
568 	    == NULL) {
569 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
570 		goto err;
571 	}
572 	pathcomp->tspc_vertex = vtx;
573 	topo_list_append(curr_path_comps, pathcomp);
574 
575 	if (vtx == to) {
576 		(*npaths)++;
577 		pathnode = topo_hdl_zalloc(thp, sizeof (struct digraph_path));
578 
579 		if ((path = topo_hdl_zalloc(thp, sizeof (topo_path_t))) ==
580 		    NULL ||
581 		    (path->tsp_fmristr = topo_hdl_strdup(thp, pathstr)) ==
582 		    NULL) {
583 			(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
584 			goto err;
585 		}
586 
587 		if (topo_list_deepcopy(thp, &path->tsp_components,
588 		    curr_path_comps, sizeof (topo_path_component_t)) != 0) {
589 			(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
590 		}
591 		if (topo_fmri_str2nvl(thp, pathstr, &fmri, &err) != 0) {
592 			/* errno set */
593 			goto err;
594 		}
595 		path->tsp_fmri = fmri;
596 		pathnode->dgp_path = path;
597 
598 		topo_list_append(all_paths, pathnode);
599 		free(pathstr);
600 		topo_list_delete(curr_path_comps, pathcomp);
601 		topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
602 		return (0);
603 	}
604 
605 	for (topo_edge_t *edge = topo_list_next(&vtx->tvt_outgoing);
606 	    edge != NULL; edge = topo_list_next(edge)) {
607 
608 		if (visit_vertex(thp, edge->tve_vertex, to, all_paths, pathstr,
609 		    curr_path_comps, npaths) != 0)
610 			goto err;
611 	}
612 
613 	free(pathstr);
614 	topo_list_delete(curr_path_comps, pathcomp);
615 	topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
616 	return (0);
617 
618 err:
619 	free(pathstr);
620 	topo_hdl_free(thp, pathnode, sizeof (struct digraph_path));
621 	topo_path_destroy(thp, path);
622 	return (-1);
623 }
624 
625 /*
626  * On success, 0 is returns and the "paths" parameter is populated with an
627  * array of topo_path_t structs representing all paths from the "from" vertex
628  * to the "to" vertex.  The caller is responsible for freeing this array.  The
629  * "npaths" parameter will be populated with the number of paths found or 0 if
630  * no paths were found.
631  *
632  * On error, -1 is returned.
633  */
634 int
topo_digraph_paths(topo_hdl_t * thp,topo_digraph_t * tdg,topo_vertex_t * from,topo_vertex_t * to,topo_path_t *** paths,uint_t * npaths)635 topo_digraph_paths(topo_hdl_t *thp, topo_digraph_t *tdg, topo_vertex_t *from,
636     topo_vertex_t *to, topo_path_t ***paths, uint_t *npaths)
637 {
638 	topo_list_t all_paths = { 0 };
639 	char *curr_path;
640 	topo_path_component_t *pathcomp = NULL;
641 	topo_list_t curr_path_comps = { 0 };
642 	struct digraph_path *path;
643 	uint_t i;
644 	int ret;
645 
646 	if (asprintf(&curr_path, "%s://%s=%s/%s=%" PRIx64"",
647 	    FM_FMRI_SCHEME_PATH, FM_FMRI_SCHEME, tdg->tdg_scheme,
648 	    topo_node_name(from->tvt_node),
649 	    topo_node_instance(from->tvt_node)) < 1) {
650 		return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
651 	}
652 
653 	if ((pathcomp = topo_hdl_zalloc(thp, sizeof (topo_path_component_t)))
654 	    == NULL) {
655 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
656 		goto err;
657 	}
658 	pathcomp->tspc_vertex = from;
659 	topo_list_append(&curr_path_comps, pathcomp);
660 
661 	*npaths = 0;
662 	for (topo_edge_t *edge = topo_list_next(&from->tvt_outgoing);
663 	    edge != NULL; edge = topo_list_next(edge)) {
664 
665 		ret = visit_vertex(thp, edge->tve_vertex, to, &all_paths,
666 		    curr_path, &curr_path_comps, npaths);
667 		if (ret != 0) {
668 			/* errno set */
669 			goto err;
670 		}
671 	}
672 	topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
673 
674 	/*
675 	 * No paths were found between the "from" and "to" vertices, so
676 	 * we're done here.
677 	 */
678 	if (*npaths == 0) {
679 		free(curr_path);
680 		return (0);
681 	}
682 
683 	*paths = topo_hdl_zalloc(thp, (*npaths) * sizeof (topo_path_t *));
684 	if (*paths == NULL) {
685 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
686 		goto err;
687 	}
688 
689 	for (i = 0, path = topo_list_next(&all_paths); path != NULL;
690 	    i++, path = topo_list_next(path)) {
691 
692 		*((*paths) + i) = path->dgp_path;
693 	}
694 
695 	path = topo_list_next(&all_paths);
696 	while (path != NULL) {
697 		struct digraph_path *tmp = path;
698 
699 		path = topo_list_next(path);
700 		topo_hdl_free(thp, tmp, sizeof (struct digraph_path));
701 	}
702 	free(curr_path);
703 	return (0);
704 
705 err:
706 	free(curr_path);
707 	path = topo_list_next(&all_paths);
708 	while (path != NULL) {
709 		struct digraph_path *tmp = path;
710 
711 		path = topo_list_next(path);
712 		topo_hdl_free(thp, tmp, sizeof (struct digraph_path));
713 	}
714 
715 	topo_dprintf(thp, TOPO_DBG_ERR, "%s: failed (%s)", __func__,
716 	    topo_hdl_errmsg(thp));
717 	return (-1);
718 }
719 
720 /* Helper function for path_fmri_nvl2str() */
721 static ssize_t
fmri_bufsz(nvlist_t * nvl)722 fmri_bufsz(nvlist_t *nvl)
723 {
724 	char *dg_scheme = NULL;
725 	nvlist_t **hops, *auth;
726 	uint_t nhops;
727 	ssize_t bufsz = 1;
728 	int ret;
729 
730 	if (nvlist_lookup_nvlist(nvl, FM_FMRI_AUTHORITY, &auth) != 0 ||
731 	    nvlist_lookup_string(auth, FM_FMRI_PATH_DIGRAPH_SCHEME,
732 	    &dg_scheme) != 0) {
733 		return (0);
734 	}
735 
736 	if ((ret = snprintf(NULL, 0, "%s://%s=%s", FM_FMRI_SCHEME_PATH,
737 	    FM_FMRI_SCHEME, dg_scheme)) < 0) {
738 		return (-1);
739 	}
740 	bufsz += ret;
741 
742 	if (nvlist_lookup_nvlist_array(nvl, FM_FMRI_PATH, &hops, &nhops) !=
743 	    0) {
744 		return (0);
745 	}
746 
747 	for (uint_t i = 0; i < nhops; i++) {
748 		char *name;
749 		uint64_t inst;
750 
751 		if (nvlist_lookup_string(hops[i], FM_FMRI_PATH_NAME, &name) !=
752 		    0 ||
753 		    nvlist_lookup_uint64(hops[i], FM_FMRI_PATH_INST, &inst) !=
754 		    0) {
755 			return (0);
756 		}
757 		if ((ret = snprintf(NULL, 0, "/%s=%" PRIx64 "", name, inst)) <
758 		    0) {
759 			return (-1);
760 		}
761 		bufsz += ret;
762 	}
763 	return (bufsz);
764 }
765 
766 int
path_fmri_nvl2str(topo_mod_t * mod,tnode_t * node,topo_version_t version,nvlist_t * in,nvlist_t ** out)767 path_fmri_nvl2str(topo_mod_t *mod, tnode_t *node, topo_version_t version,
768     nvlist_t *in, nvlist_t **out)
769 {
770 	uint8_t scheme_vers;
771 	nvlist_t *outnvl;
772 	nvlist_t **paths, *auth;
773 	uint_t nelem;
774 	ssize_t bufsz, end = 0;
775 	char *buf, *dg_scheme;
776 	int ret;
777 
778 	if (version > TOPO_METH_NVL2STR_VERSION)
779 		return (topo_mod_seterrno(mod, EMOD_VER_NEW));
780 
781 	if (nvlist_lookup_uint8(in, FM_FMRI_PATH_VERSION, &scheme_vers) != 0) {
782 		return (topo_mod_seterrno(mod, EMOD_NOMEM));
783 	}
784 
785 	if (scheme_vers != FM_PATH_SCHEME_VERSION) {
786 		return (topo_mod_seterrno(mod, EMOD_FMRI_NVL));
787 	}
788 
789 	/*
790 	 * Get size of buffer needed to hold the string representation of the
791 	 * FMRI.
792 	 */
793 	bufsz = fmri_bufsz(in);
794 	if (bufsz == 0) {
795 		return (topo_mod_seterrno(mod, EMOD_FMRI_MALFORM));
796 	} else if (bufsz < 1) {
797 		return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
798 	}
799 
800 	if ((buf = topo_mod_zalloc(mod, bufsz)) == NULL) {
801 		return (topo_mod_seterrno(mod, EMOD_NOMEM));
802 	}
803 
804 	/*
805 	 * We've already successfully done these nvlist lookups in fmri_bufsz()
806 	 * so we don't worry about checking retvals this time around.
807 	 */
808 	(void) nvlist_lookup_nvlist(in, FM_FMRI_AUTHORITY, &auth);
809 	(void) nvlist_lookup_string(auth, FM_FMRI_PATH_DIGRAPH_SCHEME,
810 	    &dg_scheme);
811 	(void) nvlist_lookup_nvlist_array(in, FM_FMRI_PATH, &paths,
812 	    &nelem);
813 	if ((ret = snprintf(buf, bufsz, "%s://%s=%s", FM_FMRI_SCHEME_PATH,
814 	    FM_FMRI_SCHEME, dg_scheme)) < 0) {
815 		topo_mod_free(mod, buf, bufsz);
816 		return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
817 	}
818 	end += ret;
819 
820 	for (uint_t i = 0; i < nelem; i++) {
821 		char *pathname;
822 		uint64_t pathinst;
823 
824 		(void) nvlist_lookup_string(paths[i], FM_FMRI_PATH_NAME,
825 		    &pathname);
826 		(void) nvlist_lookup_uint64(paths[i], FM_FMRI_PATH_INST,
827 		    &pathinst);
828 
829 		if ((ret = snprintf(buf + end, (bufsz - end), "/%s=%" PRIx64 "",
830 		    pathname, pathinst)) < 0) {
831 			topo_mod_free(mod, buf, bufsz);
832 			return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
833 		}
834 		end += ret;
835 	}
836 
837 	if (topo_mod_nvalloc(mod, &outnvl, NV_UNIQUE_NAME) != 0) {
838 		topo_mod_free(mod, buf, bufsz);
839 		return (topo_mod_seterrno(mod, EMOD_FMRI_NVL));
840 	}
841 	if (nvlist_add_string(outnvl, "fmri-string", buf) != 0) {
842 		nvlist_free(outnvl);
843 		topo_mod_free(mod, buf, bufsz);
844 		return (topo_mod_seterrno(mod, EMOD_FMRI_NVL));
845 	}
846 	topo_mod_free(mod, buf, bufsz);
847 	*out = outnvl;
848 
849 	return (0);
850 }
851 
852 int
path_fmri_str2nvl(topo_mod_t * mod,tnode_t * node,topo_version_t version,nvlist_t * in,nvlist_t ** out)853 path_fmri_str2nvl(topo_mod_t *mod, tnode_t *node, topo_version_t version,
854     nvlist_t *in, nvlist_t **out)
855 {
856 	char *fmristr, *tmp = NULL, *lastpair;
857 	char *dg_scheme, *dg_scheme_end, *pathname, *path_start;
858 	nvlist_t *fmri = NULL, *auth = NULL, **path = NULL;
859 	uint_t npairs = 0, i = 0, fmrilen, path_offset;
860 
861 	if (version > TOPO_METH_STR2NVL_VERSION)
862 		return (topo_mod_seterrno(mod, EMOD_VER_NEW));
863 
864 	if (nvlist_lookup_string(in, "fmri-string", &fmristr) != 0)
865 		return (topo_mod_seterrno(mod, EMOD_METHOD_INVAL));
866 
867 	if (strncmp(fmristr, "path://", 7) != 0)
868 		return (topo_mod_seterrno(mod, EMOD_FMRI_MALFORM));
869 
870 	if (topo_mod_nvalloc(mod, &fmri, NV_UNIQUE_NAME) != 0) {
871 		/* errno set */
872 		return (-1);
873 	}
874 	if (nvlist_add_string(fmri, FM_FMRI_SCHEME,
875 	    FM_FMRI_SCHEME_PATH) != 0 ||
876 	    nvlist_add_uint8(fmri, FM_FMRI_PATH_VERSION,
877 	    FM_PATH_SCHEME_VERSION) != 0) {
878 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
879 		goto err;
880 	}
881 
882 	/*
883 	 * We need to make a copy of the fmri string because strtok will
884 	 * modify it.  We can't use topo_mod_strdup/strfree because
885 	 * topo_mod_strfree will end up leaking part of the string because
886 	 * of the NUL chars that strtok inserts - which will cause
887 	 * topo_mod_strfree to miscalculate the length of the string.  So we
888 	 * keep track of the length of the original string and use
889 	 * topo_mod_alloc/topo_mod_free.
890 	 */
891 	fmrilen = strlen(fmristr) + 1;
892 	if ((tmp = topo_mod_alloc(mod, fmrilen)) == NULL) {
893 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
894 		goto err;
895 	}
896 	bcopy(fmristr, tmp, fmrilen);
897 
898 	/*
899 	 * Find the offset of the "/" after the authority portion of the FMRI.
900 	 */
901 	if ((path_start = strchr(tmp + 7, '/')) == NULL) {
902 		(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
903 		goto err;
904 	}
905 
906 	path_offset = path_start - tmp;
907 	pathname = fmristr + path_offset + 1;
908 
909 	/*
910 	 * Count the number of "=" chars after the "path:///" portion of the
911 	 * FMRI to determine how big the path array needs to be.
912 	 */
913 	(void) strtok_r(tmp + path_offset, "=", &lastpair);
914 	while (strtok_r(NULL, "=", &lastpair) != NULL)
915 		npairs++;
916 
917 	if (npairs == 0) {
918 		(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
919 		goto err;
920 	}
921 
922 	if ((path = topo_mod_zalloc(mod, npairs * sizeof (nvlist_t *))) ==
923 	    NULL) {
924 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
925 		goto err;
926 	}
927 
928 	/*
929 	 * Build the auth nvlist.  There is only one nvpair in the path FMRI
930 	 * scheme, which is the scheme of the underlying digraph.
931 	 */
932 	if (topo_mod_nvalloc(mod, &auth, NV_UNIQUE_NAME) != 0) {
933 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
934 		goto err;
935 	}
936 
937 	if ((dg_scheme = strchr(tmp + 7, '=')) == NULL ||
938 	    dg_scheme > path_start) {
939 		(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
940 		goto err;
941 	}
942 	dg_scheme_end = tmp + path_offset;
943 	*dg_scheme_end = '\0';
944 
945 	if (nvlist_add_string(auth, FM_FMRI_PATH_DIGRAPH_SCHEME, dg_scheme) !=
946 	    0 ||
947 	    nvlist_add_nvlist(fmri, FM_FMRI_AUTHORITY, auth) != 0) {
948 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
949 		goto err;
950 	}
951 
952 	while (i < npairs) {
953 		nvlist_t *pathcomp;
954 		uint64_t pathinst;
955 		char *end, *addrstr, *estr;
956 
957 		if (topo_mod_nvalloc(mod, &pathcomp, NV_UNIQUE_NAME) != 0) {
958 			(void) topo_mod_seterrno(mod, EMOD_NOMEM);
959 			goto err;
960 		}
961 		if ((end = strchr(pathname, '=')) == NULL) {
962 			(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
963 			goto err;
964 		}
965 		*end = '\0';
966 		addrstr = end + 1;
967 
968 		/*
969 		 * If this is the last pair, then addrstr will already be
970 		 * nul-terminated.
971 		 */
972 		if (i < (npairs - 1)) {
973 			if ((end = strchr(addrstr, '/')) == NULL) {
974 				(void) topo_mod_seterrno(mod,
975 				    EMOD_FMRI_MALFORM);
976 				goto err;
977 			}
978 			*end = '\0';
979 		}
980 
981 		/*
982 		 * Convert addrstr to a uint64_t
983 		 */
984 		errno = 0;
985 		pathinst = strtoull(addrstr, &estr, 16);
986 		if (errno != 0 || *estr != '\0') {
987 			(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
988 			goto err;
989 		}
990 
991 		/*
992 		 * Add both nvpairs to the nvlist and then add the nvlist to
993 		 * the path nvlist array.
994 		 */
995 		if (nvlist_add_string(pathcomp, FM_FMRI_PATH_NAME, pathname) !=
996 		    0 ||
997 		    nvlist_add_uint64(pathcomp, FM_FMRI_PATH_INST, pathinst) !=
998 		    0) {
999 			(void) topo_mod_seterrno(mod, EMOD_NOMEM);
1000 			goto err;
1001 		}
1002 		path[i++] = pathcomp;
1003 		pathname = end + 1;
1004 	}
1005 	if (nvlist_add_nvlist_array(fmri, FM_FMRI_PATH, path, npairs) != 0) {
1006 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
1007 		goto err;
1008 	}
1009 	*out = fmri;
1010 
1011 	if (path != NULL) {
1012 		for (i = 0; i < npairs; i++)
1013 			nvlist_free(path[i]);
1014 
1015 		topo_mod_free(mod, path, npairs * sizeof (nvlist_t *));
1016 	}
1017 	nvlist_free(auth);
1018 	topo_mod_free(mod, tmp, fmrilen);
1019 	return (0);
1020 
1021 err:
1022 	topo_mod_dprintf(mod, "%s failed: %s", __func__,
1023 	    topo_strerror(topo_mod_errno(mod)));
1024 	if (path != NULL) {
1025 		for (i = 0; i < npairs; i++)
1026 			nvlist_free(path[i]);
1027 
1028 		topo_mod_free(mod, path, npairs * sizeof (nvlist_t *));
1029 	}
1030 	nvlist_free(auth);
1031 	nvlist_free(fmri);
1032 	if (tmp != NULL)
1033 		topo_mod_free(mod, tmp, fmrilen);
1034 	return (-1);
1035 }
1036