1*c5591576SRob Johnston /*
2*c5591576SRob Johnston  * This file and its contents are supplied under the terms of the
3*c5591576SRob Johnston  * Common Development and Distribution License ("CDDL"), version 1.0.
4*c5591576SRob Johnston  * You may only use this file in accordance with the terms of version
5*c5591576SRob Johnston  * 1.0 of the CDDL.
6*c5591576SRob Johnston  *
7*c5591576SRob Johnston  * A full copy of the text of the CDDL should have accompanied this
8*c5591576SRob Johnston  * source.  A copy of the CDDL is also available via the Internet at
9*c5591576SRob Johnston  * http://www.illumos.org/license/CDDL.
10*c5591576SRob Johnston  */
11*c5591576SRob Johnston 
12*c5591576SRob Johnston /*
13*c5591576SRob Johnston  * Copyright 2020 Joyent, Inc.
14*c5591576SRob Johnston  */
15*c5591576SRob Johnston 
16*c5591576SRob Johnston /*
17*c5591576SRob Johnston  * This file implements a set of APIs for creating, destroying and traversing
18*c5591576SRob Johnston  * directed-graph (digraph) topologies.  The API is split into categories:
19*c5591576SRob Johnston  * client API and module API.
20*c5591576SRob Johnston  *
21*c5591576SRob Johnston  * The client API can be used by libtopo consumers for traversing an existing
22*c5591576SRob Johnston  * digraph topology.  The module API can be used by topo plugins to create or
23*c5591576SRob Johnston  * destroy a digraph topology.
24*c5591576SRob Johnston  *
25*c5591576SRob Johnston  * client API
26*c5591576SRob Johnston  * ----------
27*c5591576SRob Johnston  * topo_digraph_get
28*c5591576SRob Johnston  * topo_vertex_iter
29*c5591576SRob Johnston  * topo_vertex_node
30*c5591576SRob Johnston  * topo_edge_iter
31*c5591576SRob Johnston  * topo_digraph_paths
32*c5591576SRob Johnston  * topo_path_destroy
33*c5591576SRob Johnston  *
34*c5591576SRob Johnston  * module API
35*c5591576SRob Johnston  * ----------
36*c5591576SRob Johnston  * topo_digraph_new
37*c5591576SRob Johnston  * topo_digraph_destroy
38*c5591576SRob Johnston  * topo_vertex_new
39*c5591576SRob Johnston  * topo_vertex_destroy
40*c5591576SRob Johnston  * topo_edge_new
41*c5591576SRob Johnston  *
42*c5591576SRob Johnston  * A digraph is represented in-core by a topo_digraph_t structure which
43*c5591576SRob Johnston  * maintains an adjacency list of vertices (see topo_digraph.h).  Vertices
44*c5591576SRob Johnston  * are represented by topo_vertex_t structures which are essentially thin
45*c5591576SRob Johnston  * wrappers around topo node (tnode_t) structures.  In addition to holding
46*c5591576SRob Johnston  * a pointer to the underlyng topo node, the topo_vertex_t maintains a list
47*c5591576SRob Johnston  * of incoming and outgoing edges and a pointer to the next and previous
48*c5591576SRob Johnston  * vertices in digraph's adjecency list.
49*c5591576SRob Johnston  *
50*c5591576SRob Johnston  * Locking
51*c5591576SRob Johnston  * -------
52*c5591576SRob Johnston  * The module APIs should only be used during snapshot creation, which is
53*c5591576SRob Johnston  * single-threaded, or as the result of a call to topo_snap_release() or
54*c5591576SRob Johnston  * topo_close().  While libtopo does prevent concurrent calls to
55*c5591576SRob Johnston  * topo_snap_release() and topo_close() via the topo_hdl_t lock, there is no
56*c5591576SRob Johnston  * mechanism currently that prevents the situation where one or more threads
57*c5591576SRob Johnston  * were to access the snapshot (e.g. they've got a cached tnode_t ptr or are
58*c5591576SRob Johnston  * walking the snapshot) while another thread is calling topo_snap_release()
59*c5591576SRob Johnston  * or topo_close().  The same is true for tree topologies.  It is up to the
60*c5591576SRob Johnston  * library consumer to provide their own synchronization or reference counting
61*c5591576SRob Johnston  * mechanism for that case. For example, fmd implements a reference counting
62*c5591576SRob Johnston  * mechanism around topo snapshots so that individual fmd modules can safely
63*c5591576SRob Johnston  * cache pointers to a given topo snapshot.
64*c5591576SRob Johnston  *
65*c5591576SRob Johnston  * None of the client APIs modify the state of the graph structure once
66*c5591576SRob Johnston  * the snapshot is created.  The exception is the state of the underlyng topo
67*c5591576SRob Johnston  * nodes for each vertex, who's properties may change as a result of the
68*c5591576SRob Johnston  * following:
69*c5591576SRob Johnston  *
70*c5591576SRob Johnston  * 1) topo_prop_get operations for properties that are backed by topo methods
71*c5591576SRob Johnston  * 2) topo_prop_set operations.
72*c5591576SRob Johnston  *
73*c5591576SRob Johnston  * For both of the above situations, synchronization is enforced by the per-node
74*c5591576SRob Johnston  * locks. Thus there a no locks used for synchronizing access to
75*c5591576SRob Johnston  * the topo_digraph_t or topo_vertex_t structures.
76*c5591576SRob Johnston  *
77*c5591576SRob Johnston  * path scheme FMRIs
78*c5591576SRob Johnston  * -----------------
79*c5591576SRob Johnston  * For digraph topologies it is useful to be able to treat paths between
80*c5591576SRob Johnston  * vertices as resources and thus have a way to represent a unique path
81*c5591576SRob Johnston  * between those vertices.  The path FMRI scheme is used for this purpose and
82*c5591576SRob Johnston  * has the following form:
83*c5591576SRob Johnston  *
84*c5591576SRob Johnston  * path://scheme=<scheme>/<nodename>=<instance>/...
85*c5591576SRob Johnston  *
86*c5591576SRob Johnston  * The path FMRI for a path from one vertex to another vertex is represented by
87*c5591576SRob Johnston  * a sequence of nodename/instance pairs where each pair represents a vertex on
88*c5591576SRob Johnston  * the path between the two vertices.  The first nodename/instance pair
89*c5591576SRob Johnston  * represents the "from" vertex and the last nodename/instance pair represents
90*c5591576SRob Johnston  * the "to" vertex.
91*c5591576SRob Johnston  *
92*c5591576SRob Johnston  * For example, the path FMRI to represent a path from an initiator to a
93*c5591576SRob Johnston  * target in a SAS scheme digraph might look like this:
94*c5591576SRob Johnston  *
95*c5591576SRob Johnston  * path://scheme=sas/initiator=5003048023567a00/port=5003048023567a00/
96*c5591576SRob Johnston  *       port=500304801861347f/expander=500304801861347f/port=500304801861347f/
97*c5591576SRob Johnston  *       port=5000c500adc881d5/target=5000c500adc881d4
98*c5591576SRob Johnston  *
99*c5591576SRob Johnston  * This file implements NVL2STR and STR2NVL methods for path-scheme FMRIs.
100*c5591576SRob Johnston  */
101*c5591576SRob Johnston 
102*c5591576SRob Johnston #include <libtopo.h>
103*c5591576SRob Johnston #include <sys/fm/protocol.h>
104*c5591576SRob Johnston 
105*c5591576SRob Johnston #include <topo_digraph.h>
106*c5591576SRob Johnston #include <topo_method.h>
107*c5591576SRob Johnston 
108*c5591576SRob Johnston #define	__STDC_FORMAT_MACROS
109*c5591576SRob Johnston #include <inttypes.h>
110*c5591576SRob Johnston 
111*c5591576SRob Johnston 
112*c5591576SRob Johnston extern int path_fmri_str2nvl(topo_mod_t *, tnode_t *, topo_version_t,
113*c5591576SRob Johnston     nvlist_t *, nvlist_t **);
114*c5591576SRob Johnston extern int path_fmri_nvl2str(topo_mod_t *, tnode_t *, topo_version_t,
115*c5591576SRob Johnston     nvlist_t *, nvlist_t **);
116*c5591576SRob Johnston 
117*c5591576SRob Johnston static const topo_method_t digraph_root_methods[] = {
118*c5591576SRob Johnston 	{ TOPO_METH_PATH_STR2NVL, TOPO_METH_STR2NVL_DESC,
119*c5591576SRob Johnston 	    TOPO_METH_STR2NVL_VERSION, TOPO_STABILITY_INTERNAL,
120*c5591576SRob Johnston 	    path_fmri_str2nvl },
121*c5591576SRob Johnston 	{ TOPO_METH_PATH_NVL2STR, TOPO_METH_NVL2STR_DESC,
122*c5591576SRob Johnston 	    TOPO_METH_NVL2STR_VERSION, TOPO_STABILITY_INTERNAL,
123*c5591576SRob Johnston 	    path_fmri_nvl2str },
124*c5591576SRob Johnston 	{ NULL }
125*c5591576SRob Johnston };
126*c5591576SRob Johnston 
127*c5591576SRob Johnston /*
128*c5591576SRob Johnston  * On success, returns a pointer to the digraph for the specified FMRI scheme.
129*c5591576SRob Johnston  * On failure, returns NULL.
130*c5591576SRob Johnston  */
131*c5591576SRob Johnston topo_digraph_t *
topo_digraph_get(topo_hdl_t * thp,const char * scheme)132*c5591576SRob Johnston topo_digraph_get(topo_hdl_t *thp, const char *scheme)
133*c5591576SRob Johnston {
134*c5591576SRob Johnston 	topo_digraph_t *tdg;
135*c5591576SRob Johnston 
136*c5591576SRob Johnston 	for (tdg = topo_list_next(&thp->th_digraphs); tdg != NULL;
137*c5591576SRob Johnston 	    tdg = topo_list_next(tdg)) {
138*c5591576SRob Johnston 		if (strcmp(scheme, tdg->tdg_scheme) == 0)
139*c5591576SRob Johnston 			return (tdg);
140*c5591576SRob Johnston 	}
141*c5591576SRob Johnston 	return (NULL);
142*c5591576SRob Johnston }
143*c5591576SRob Johnston 
144*c5591576SRob Johnston static topo_digraph_t *
find_digraph(topo_mod_t * mod)145*c5591576SRob Johnston find_digraph(topo_mod_t *mod)
146*c5591576SRob Johnston {
147*c5591576SRob Johnston 	return (topo_digraph_get(mod->tm_hdl, mod->tm_info->tmi_scheme));
148*c5591576SRob Johnston }
149*c5591576SRob Johnston 
150*c5591576SRob Johnston /*
151*c5591576SRob Johnston  * On successs, allocates a new topo_digraph_t structure for the requested
152*c5591576SRob Johnston  * scheme.  The caller is responsible for free all memory allocated for this
153*c5591576SRob Johnston  * structure when done via a call to topo_digraph_destroy().
154*c5591576SRob Johnston  *
155*c5591576SRob Johnston  * On failure, this function returns NULL and sets topo errno.
156*c5591576SRob Johnston  */
157*c5591576SRob Johnston topo_digraph_t *
topo_digraph_new(topo_hdl_t * thp,topo_mod_t * mod,const char * scheme)158*c5591576SRob Johnston topo_digraph_new(topo_hdl_t *thp, topo_mod_t *mod, const char *scheme)
159*c5591576SRob Johnston {
160*c5591576SRob Johnston 	topo_digraph_t *tdg;
161*c5591576SRob Johnston 	tnode_t *tn = NULL;
162*c5591576SRob Johnston 
163*c5591576SRob Johnston 	if ((tdg = topo_mod_zalloc(mod, sizeof (topo_digraph_t))) == NULL) {
164*c5591576SRob Johnston 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
165*c5591576SRob Johnston 		return (NULL);
166*c5591576SRob Johnston 	}
167*c5591576SRob Johnston 
168*c5591576SRob Johnston 	tdg->tdg_mod = mod;
169*c5591576SRob Johnston 
170*c5591576SRob Johnston 	if ((tdg->tdg_scheme = topo_mod_strdup(mod, scheme)) == NULL) {
171*c5591576SRob Johnston 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
172*c5591576SRob Johnston 		goto err;
173*c5591576SRob Johnston 	}
174*c5591576SRob Johnston 
175*c5591576SRob Johnston 	/*
176*c5591576SRob Johnston 	 * For digraph topologies, the "root" node, which gets passed in to
177*c5591576SRob Johnston 	 * the scheme module's enum method is not part of the actual graph
178*c5591576SRob Johnston 	 * structure per-se.
179*c5591576SRob Johnston 	 * Its purpose is simply to provide a place on which to register the
180*c5591576SRob Johnston 	 * scheme-specific methods.  Client code then invokes these methods via
181*c5591576SRob Johnston 	 * the topo_fmri_* interfaces.
182*c5591576SRob Johnston 	 */
183*c5591576SRob Johnston 	if ((tn = topo_mod_zalloc(mod, sizeof (tnode_t))) == NULL)
184*c5591576SRob Johnston 		goto err;
185*c5591576SRob Johnston 
186*c5591576SRob Johnston 	/*
187*c5591576SRob Johnston 	 * Adding the TOPO_NODE_ROOT state to the node has the effect of
188*c5591576SRob Johnston 	 * preventing topo_node_destroy() from trying to clean up the parent
189*c5591576SRob Johnston 	 * node's node hash, which is only necessary in tree topologies.
190*c5591576SRob Johnston 	 */
191*c5591576SRob Johnston 	tn->tn_state = TOPO_NODE_ROOT | TOPO_NODE_INIT;
192*c5591576SRob Johnston 	tn->tn_name = (char *)scheme;
193*c5591576SRob Johnston 	tn->tn_instance = 0;
194*c5591576SRob Johnston 	tn->tn_enum = mod;
195*c5591576SRob Johnston 	tn->tn_hdl = thp;
196*c5591576SRob Johnston 	topo_node_hold(tn);
197*c5591576SRob Johnston 
198*c5591576SRob Johnston 	tdg->tdg_rootnode = tn;
199*c5591576SRob Johnston 	if (topo_method_register(mod, tn, digraph_root_methods) != 0) {
200*c5591576SRob Johnston 		topo_mod_dprintf(mod, "failed to register digraph root "
201*c5591576SRob Johnston 		    "methods");
202*c5591576SRob Johnston 		/* errno set */
203*c5591576SRob Johnston 		return (NULL);
204*c5591576SRob Johnston 	}
205*c5591576SRob Johnston 
206*c5591576SRob Johnston 	/* This is released during topo_digraph_destroy() */
207*c5591576SRob Johnston 	topo_mod_hold(mod);
208*c5591576SRob Johnston 
209*c5591576SRob Johnston 	return (tdg);
210*c5591576SRob Johnston err:
211*c5591576SRob Johnston 	topo_mod_free(mod, tdg, sizeof (topo_digraph_t));
212*c5591576SRob Johnston 	return (NULL);
213*c5591576SRob Johnston }
214*c5591576SRob Johnston 
215*c5591576SRob Johnston /*
216*c5591576SRob Johnston  * Deallocates all memory associated with the specified topo_digraph_t.
217*c5591576SRob Johnston  *
218*c5591576SRob Johnston  * This only frees the memory allocated during topo_digraph_new().  To free the
219*c5591576SRob Johnston  * actual graph vertices one should call topo_snap_destroy() prior to calling
220*c5591576SRob Johnston  * topo_digraph_destroy().
221*c5591576SRob Johnston  *
222*c5591576SRob Johnston  * Calling topo_close() will also result in a call to topo_snap_destroy() and
223*c5591576SRob Johnston  * topo_digraph_dstroy() for all digraphs associated with the library handle.
224*c5591576SRob Johnston  *
225*c5591576SRob Johnston  * This function is a NOP if NULL is passed in.
226*c5591576SRob Johnston  */
227*c5591576SRob Johnston void
topo_digraph_destroy(topo_digraph_t * tdg)228*c5591576SRob Johnston topo_digraph_destroy(topo_digraph_t *tdg)
229*c5591576SRob Johnston {
230*c5591576SRob Johnston 	topo_mod_t *mod;
231*c5591576SRob Johnston 
232*c5591576SRob Johnston 	if (tdg == NULL)
233*c5591576SRob Johnston 		return;
234*c5591576SRob Johnston 
235*c5591576SRob Johnston 	mod = tdg->tdg_mod;
236*c5591576SRob Johnston 	topo_method_unregister_all(mod, tdg->tdg_rootnode);
237*c5591576SRob Johnston 	topo_mod_strfree(mod, (char *)tdg->tdg_scheme);
238*c5591576SRob Johnston 	topo_mod_free(mod, tdg->tdg_rootnode, sizeof (tnode_t));
239*c5591576SRob Johnston 	topo_mod_free(mod, tdg, sizeof (topo_digraph_t));
240*c5591576SRob Johnston 	topo_mod_rele(mod);
241*c5591576SRob Johnston }
242*c5591576SRob Johnston 
243*c5591576SRob Johnston /*
244*c5591576SRob Johnston  * This function creates a new vertex and adds it to the digraph associated
245*c5591576SRob Johnston  * with the module.
246*c5591576SRob Johnston  *
247*c5591576SRob Johnston  * name: name of the vertex
248*c5591576SRob Johnston  * instance: instance number of the vertex
249*c5591576SRob Johnston  *
250*c5591576SRob Johnston  * On success, it returns a pointer to the allocated topo_vertex_t associated
251*c5591576SRob Johnston  * with the new vertex.  The caller is responsible for free-ing this structure
252*c5591576SRob Johnston  * via a call to topo_vertex_destroy().
253*c5591576SRob Johnston  *
254*c5591576SRob Johnston  * On failures, this function returns NULL and sets topo_mod_errno.
255*c5591576SRob Johnston  */
256*c5591576SRob Johnston topo_vertex_t *
topo_vertex_new(topo_mod_t * mod,const char * name,topo_instance_t inst)257*c5591576SRob Johnston topo_vertex_new(topo_mod_t *mod, const char *name, topo_instance_t inst)
258*c5591576SRob Johnston {
259*c5591576SRob Johnston 	tnode_t *tn = NULL;
260*c5591576SRob Johnston 	topo_vertex_t *vtx = NULL;
261*c5591576SRob Johnston 	topo_digraph_t *tdg;
262*c5591576SRob Johnston 
263*c5591576SRob Johnston 	topo_mod_dprintf(mod, "Creating vertex %s=%" PRIx64 "", name, inst);
264*c5591576SRob Johnston 	if ((tdg = find_digraph(mod)) == NULL) {
265*c5591576SRob Johnston 		topo_mod_dprintf(mod, "%s faild: no existing digraph for FMRI "
266*c5591576SRob Johnston 		    " scheme %s", __func__, mod->tm_info->tmi_scheme);
267*c5591576SRob Johnston 		return (NULL);
268*c5591576SRob Johnston 	}
269*c5591576SRob Johnston 	if ((vtx = topo_mod_zalloc(mod, sizeof (topo_vertex_t))) == NULL ||
270*c5591576SRob Johnston 	    (tn = topo_mod_zalloc(mod, sizeof (tnode_t))) == NULL) {
271*c5591576SRob Johnston 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
272*c5591576SRob Johnston 		goto err;
273*c5591576SRob Johnston 	}
274*c5591576SRob Johnston 	if ((tn->tn_name = topo_mod_strdup(mod, name)) == NULL) {
275*c5591576SRob Johnston 		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
276*c5591576SRob Johnston 		goto err;
277*c5591576SRob Johnston 	}
278*c5591576SRob Johnston 	tn->tn_enum = mod;
279*c5591576SRob Johnston 	tn->tn_hdl = mod->tm_hdl;
280*c5591576SRob Johnston 	tn->tn_vtx = vtx;
281*c5591576SRob Johnston 	tn->tn_instance = inst;
282*c5591576SRob Johnston 	/*
283*c5591576SRob Johnston 	 * Adding the TOPO_NODE_ROOT state to the node has the effect of
284*c5591576SRob Johnston 	 * preventing topo_node_destroy() from trying to clean up the parent
285*c5591576SRob Johnston 	 * node's node hash, which is only necessary in tree topologies.
286*c5591576SRob Johnston 	 */
287*c5591576SRob Johnston 	tn->tn_state = TOPO_NODE_ROOT | TOPO_NODE_BOUND;
288*c5591576SRob Johnston 	vtx->tvt_node = tn;
289*c5591576SRob Johnston 	topo_node_hold(tn);
290*c5591576SRob Johnston 
291*c5591576SRob Johnston 	/* Bump the refcnt on the module that's creating this vertex. */
292*c5591576SRob Johnston 	topo_mod_hold(mod);
293*c5591576SRob Johnston 
294*c5591576SRob Johnston 	if (tdg->tdg_nvertices == UINT32_MAX) {
295*c5591576SRob Johnston 		topo_mod_dprintf(mod, "Max vertices reached!");
296*c5591576SRob Johnston 		(void) topo_mod_seterrno(mod, EMOD_DIGRAPH_MAXSZ);
297*c5591576SRob Johnston 		topo_mod_rele(mod);
298*c5591576SRob Johnston 		goto err;
299*c5591576SRob Johnston 	}
300*c5591576SRob Johnston 	tdg->tdg_nvertices++;
301*c5591576SRob Johnston 	topo_list_append(&tdg->tdg_vertices, vtx);
302*c5591576SRob Johnston 
303*c5591576SRob Johnston 	return (vtx);
304*c5591576SRob Johnston err:
305*c5591576SRob Johnston 	topo_mod_dprintf(mod, "failed to add create vertex %s=%" PRIx64 "(%s)",
306*c5591576SRob Johnston 	    name, inst, topo_strerror(topo_mod_errno(mod)));
307*c5591576SRob Johnston 	if (tn != NULL) {
308*c5591576SRob Johnston 		topo_mod_strfree(mod, tn->tn_name);
309*c5591576SRob Johnston 		topo_mod_free(mod, tn, sizeof (tnode_t));
310*c5591576SRob Johnston 	}
311*c5591576SRob Johnston 	if (vtx != NULL)
312*c5591576SRob Johnston 		topo_mod_free(mod, vtx, sizeof (topo_vertex_t));
313*c5591576SRob Johnston 
314*c5591576SRob Johnston 	return (NULL);
315*c5591576SRob Johnston }
316*c5591576SRob Johnston 
317*c5591576SRob Johnston /*
318*c5591576SRob Johnston  * Returns the underlying tnode_t structure for the specified vertex.
319*c5591576SRob Johnston  */
320*c5591576SRob Johnston tnode_t *
topo_vertex_node(topo_vertex_t * vtx)321*c5591576SRob Johnston topo_vertex_node(topo_vertex_t *vtx)
322*c5591576SRob Johnston {
323*c5591576SRob Johnston 	return (vtx->tvt_node);
324*c5591576SRob Johnston }
325*c5591576SRob Johnston 
326*c5591576SRob Johnston /*
327*c5591576SRob Johnston  * Convenience interface for deallocating a topo_vertex_t
328*c5591576SRob Johnston  * This function is a NOP if NULL is passed in.
329*c5591576SRob Johnston  */
330*c5591576SRob Johnston void
topo_vertex_destroy(topo_mod_t * mod,topo_vertex_t * vtx)331*c5591576SRob Johnston topo_vertex_destroy(topo_mod_t *mod, topo_vertex_t *vtx)
332*c5591576SRob Johnston {
333*c5591576SRob Johnston 	topo_edge_t *edge;
334*c5591576SRob Johnston 
335*c5591576SRob Johnston 	if (vtx == NULL)
336*c5591576SRob Johnston 		return;
337*c5591576SRob Johnston 
338*c5591576SRob Johnston 	topo_node_unbind(vtx->tvt_node);
339*c5591576SRob Johnston 
340*c5591576SRob Johnston 	edge = topo_list_next(&vtx->tvt_incoming);
341*c5591576SRob Johnston 	while (edge != NULL) {
342*c5591576SRob Johnston 		topo_edge_t *tmp = edge;
343*c5591576SRob Johnston 
344*c5591576SRob Johnston 		edge = topo_list_next(edge);
345*c5591576SRob Johnston 		topo_mod_free(mod, tmp, sizeof (topo_edge_t));
346*c5591576SRob Johnston 	}
347*c5591576SRob Johnston 
348*c5591576SRob Johnston 	edge = topo_list_next(&vtx->tvt_outgoing);
349*c5591576SRob Johnston 	while (edge != NULL) {
350*c5591576SRob Johnston 		topo_edge_t *tmp = edge;
351*c5591576SRob Johnston 
352*c5591576SRob Johnston 		edge = topo_list_next(edge);
353*c5591576SRob Johnston 		topo_mod_free(mod, tmp, sizeof (topo_edge_t));
354*c5591576SRob Johnston 	}
355*c5591576SRob Johnston 
356*c5591576SRob Johnston 	topo_mod_free(mod, vtx, sizeof (topo_vertex_t));
357*c5591576SRob Johnston }
358*c5591576SRob Johnston 
359*c5591576SRob Johnston /*
360*c5591576SRob Johnston  * This function can be used to iterate over all of the vertices in the
361*c5591576SRob Johnston  * specified digraph.  The specified callback function is invoked for each
362*c5591576SRob Johnston  * vertices.  Callback function should return the standard topo walker
363*c5591576SRob Johnston  * (TOPO_WALK_*) return values.
364*c5591576SRob Johnston  *
365*c5591576SRob Johnston  * On success, this function returns 0.
366*c5591576SRob Johnston  *
367*c5591576SRob Johnston  * On failure this function returns -1.
368*c5591576SRob Johnston  */
369*c5591576SRob Johnston 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*c5591576SRob Johnston topo_vertex_iter(topo_hdl_t *thp, topo_digraph_t *tdg,
371*c5591576SRob Johnston     int (*func)(topo_hdl_t *, topo_vertex_t *, boolean_t, void *), void *arg)
372*c5591576SRob Johnston {
373*c5591576SRob Johnston 	uint_t n = 0;
374*c5591576SRob Johnston 
375*c5591576SRob Johnston 	for (topo_vertex_t *vtx = topo_list_next(&tdg->tdg_vertices);
376*c5591576SRob Johnston 	    vtx != NULL; vtx = topo_list_next(vtx), n++) {
377*c5591576SRob Johnston 		int ret;
378*c5591576SRob Johnston 		boolean_t last_vtx = B_FALSE;
379*c5591576SRob Johnston 
380*c5591576SRob Johnston 		if (n == (tdg->tdg_nvertices - 1))
381*c5591576SRob Johnston 			last_vtx = B_TRUE;
382*c5591576SRob Johnston 
383*c5591576SRob Johnston 		ret = func(thp, vtx, last_vtx, arg);
384*c5591576SRob Johnston 
385*c5591576SRob Johnston 		switch (ret) {
386*c5591576SRob Johnston 		case TOPO_WALK_NEXT:
387*c5591576SRob Johnston 			continue;
388*c5591576SRob Johnston 		case TOPO_WALK_TERMINATE:
389*c5591576SRob Johnston 			goto out;
390*c5591576SRob Johnston 		case TOPO_WALK_ERR:
391*c5591576SRob Johnston 		default:
392*c5591576SRob Johnston 			return (-1);
393*c5591576SRob Johnston 		}
394*c5591576SRob Johnston 	}
395*c5591576SRob Johnston out:
396*c5591576SRob Johnston 	return (0);
397*c5591576SRob Johnston }
398*c5591576SRob Johnston 
399*c5591576SRob Johnston /*
400*c5591576SRob Johnston  * Add a new outgoing edge the vertex "from" to the vertex "to".
401*c5591576SRob Johnston  *
402*c5591576SRob Johnston  * On success, this functions returns 0.
403*c5591576SRob Johnston  *
404*c5591576SRob Johnston  * On failure, this function returns -1.
405*c5591576SRob Johnston  */
406*c5591576SRob Johnston int
topo_edge_new(topo_mod_t * mod,topo_vertex_t * from,topo_vertex_t * to)407*c5591576SRob Johnston topo_edge_new(topo_mod_t *mod, topo_vertex_t *from, topo_vertex_t *to)
408*c5591576SRob Johnston {
409*c5591576SRob Johnston 	topo_digraph_t *tdg;
410*c5591576SRob Johnston 	topo_edge_t *e_from = NULL, *e_to = NULL;
411*c5591576SRob Johnston 
412*c5591576SRob Johnston 	topo_mod_dprintf(mod, "Adding edge from vertex %s=%" PRIx64 " to "
413*c5591576SRob Johnston 	    "%s=%" PRIx64"", topo_node_name(from->tvt_node),
414*c5591576SRob Johnston 	    topo_node_instance(from->tvt_node),
415*c5591576SRob Johnston 	    topo_node_name(to->tvt_node), topo_node_instance(to->tvt_node));
416*c5591576SRob Johnston 
417*c5591576SRob Johnston 	if ((tdg = find_digraph(mod)) == NULL) {
418*c5591576SRob Johnston 		topo_mod_dprintf(mod, "Digraph lookup failed");
419*c5591576SRob Johnston 		return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
420*c5591576SRob Johnston 	}
421*c5591576SRob Johnston 	if (from->tvt_noutgoing == UINT32_MAX ||
422*c5591576SRob Johnston 	    to->tvt_nincoming == UINT32_MAX ||
423*c5591576SRob Johnston 	    tdg->tdg_nedges == UINT32_MAX) {
424*c5591576SRob Johnston 		topo_mod_dprintf(mod, "Max edges reached!");
425*c5591576SRob Johnston 		return (topo_mod_seterrno(mod, EMOD_DIGRAPH_MAXSZ));
426*c5591576SRob Johnston 
427*c5591576SRob Johnston 	}
428*c5591576SRob Johnston 	if ((e_from = topo_mod_zalloc(mod, sizeof (topo_edge_t))) == NULL ||
429*c5591576SRob Johnston 	    (e_to = topo_mod_zalloc(mod, sizeof (topo_edge_t))) == NULL) {
430*c5591576SRob Johnston 		topo_mod_free(mod, e_from, sizeof (topo_edge_t));
431*c5591576SRob Johnston 		topo_mod_free(mod, e_to, sizeof (topo_edge_t));
432*c5591576SRob Johnston 		return (topo_mod_seterrno(mod, EMOD_NOMEM));
433*c5591576SRob Johnston 	}
434*c5591576SRob Johnston 	e_from->tve_vertex = from;
435*c5591576SRob Johnston 	e_to->tve_vertex = to;
436*c5591576SRob Johnston 
437*c5591576SRob Johnston 	topo_list_append(&from->tvt_outgoing, e_to);
438*c5591576SRob Johnston 	from->tvt_noutgoing++;
439*c5591576SRob Johnston 	topo_list_append(&to->tvt_incoming, e_from);
440*c5591576SRob Johnston 	to->tvt_nincoming++;
441*c5591576SRob Johnston 	tdg->tdg_nedges++;
442*c5591576SRob Johnston 
443*c5591576SRob Johnston 	return (0);
444*c5591576SRob Johnston }
445*c5591576SRob Johnston 
446*c5591576SRob Johnston /*
447*c5591576SRob Johnston  * This function can be used to iterate over all of the outgoing edges in
448*c5591576SRob Johnston  * for specified vertex.  The specified callback function is invoked for each
449*c5591576SRob Johnston  * edge.  Callback function should return the standard topo walker
450*c5591576SRob Johnston  * (TOPO_WALK_*) return values.
451*c5591576SRob Johnston  *
452*c5591576SRob Johnston  * On success, this function returns 0.
453*c5591576SRob Johnston  *
454*c5591576SRob Johnston  * On failure this function returns -1.
455*c5591576SRob Johnston  */
456*c5591576SRob Johnston 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*c5591576SRob Johnston topo_edge_iter(topo_hdl_t *thp, topo_vertex_t *vtx,
458*c5591576SRob Johnston     int (*func)(topo_hdl_t *, topo_edge_t *, boolean_t, void *), void *arg)
459*c5591576SRob Johnston {
460*c5591576SRob Johnston 	uint_t n = 0;
461*c5591576SRob Johnston 
462*c5591576SRob Johnston 	for (topo_edge_t *edge = topo_list_next(&vtx->tvt_outgoing);
463*c5591576SRob Johnston 	    edge != NULL; edge = topo_list_next(edge), n++) {
464*c5591576SRob Johnston 		int ret;
465*c5591576SRob Johnston 		boolean_t last_edge = B_FALSE;
466*c5591576SRob Johnston 
467*c5591576SRob Johnston 		if (n == (vtx->tvt_noutgoing - 1))
468*c5591576SRob Johnston 			last_edge = B_TRUE;
469*c5591576SRob Johnston 
470*c5591576SRob Johnston 		ret = func(thp, edge, last_edge, arg);
471*c5591576SRob Johnston 
472*c5591576SRob Johnston 		switch (ret) {
473*c5591576SRob Johnston 		case TOPO_WALK_NEXT:
474*c5591576SRob Johnston 			continue;
475*c5591576SRob Johnston 		case TOPO_WALK_TERMINATE:
476*c5591576SRob Johnston 			break;
477*c5591576SRob Johnston 		case TOPO_WALK_ERR:
478*c5591576SRob Johnston 		default:
479*c5591576SRob Johnston 			return (-1);
480*c5591576SRob Johnston 		}
481*c5591576SRob Johnston 	}
482*c5591576SRob Johnston 	return (0);
483*c5591576SRob Johnston }
484*c5591576SRob Johnston 
485*c5591576SRob Johnston /*
486*c5591576SRob Johnston  * Convenience interface for deallocating a topo_path_t
487*c5591576SRob Johnston  * This function is a NOP if NULL is passed in.
488*c5591576SRob Johnston  */
489*c5591576SRob Johnston void
topo_path_destroy(topo_hdl_t * thp,topo_path_t * path)490*c5591576SRob Johnston topo_path_destroy(topo_hdl_t *thp, topo_path_t *path)
491*c5591576SRob Johnston {
492*c5591576SRob Johnston 	topo_path_component_t *pathcomp;
493*c5591576SRob Johnston 
494*c5591576SRob Johnston 	if (path == NULL)
495*c5591576SRob Johnston 		return;
496*c5591576SRob Johnston 
497*c5591576SRob Johnston 	topo_hdl_strfree(thp, (char *)path->tsp_fmristr);
498*c5591576SRob Johnston 	nvlist_free(path->tsp_fmri);
499*c5591576SRob Johnston 
500*c5591576SRob Johnston 	pathcomp = topo_list_next(&path->tsp_components);
501*c5591576SRob Johnston 	while (pathcomp != NULL) {
502*c5591576SRob Johnston 		topo_path_component_t *tmp = pathcomp;
503*c5591576SRob Johnston 
504*c5591576SRob Johnston 		pathcomp = topo_list_next(pathcomp);
505*c5591576SRob Johnston 		topo_hdl_free(thp, tmp, sizeof (topo_path_component_t));
506*c5591576SRob Johnston 	}
507*c5591576SRob Johnston 
508*c5591576SRob Johnston 	topo_hdl_free(thp, path, sizeof (topo_path_t));
509*c5591576SRob Johnston }
510*c5591576SRob Johnston 
511*c5591576SRob Johnston /*
512*c5591576SRob Johnston  * This just wraps topo_path_t so that visit_vertex() can build a linked list
513*c5591576SRob Johnston  * of paths.
514*c5591576SRob Johnston  */
515*c5591576SRob Johnston struct digraph_path {
516*c5591576SRob Johnston 	topo_list_t	dgp_link;
517*c5591576SRob Johnston 	topo_path_t	*dgp_path;
518*c5591576SRob Johnston };
519*c5591576SRob Johnston 
520*c5591576SRob Johnston /*
521*c5591576SRob Johnston  * This is a callback function for the vertex iteration that gets initiated by
522*c5591576SRob Johnston  * topo_digraph_paths().
523*c5591576SRob Johnston  *
524*c5591576SRob Johnston  * This is used to implement a depth-first search for all paths that lead to
525*c5591576SRob Johnston  * the vertex pointed to by the "to" parameter.  As we walk the graph we
526*c5591576SRob Johnston  * maintain a linked list of the components (vertices) in the in-progress path
527*c5591576SRob Johnston  * as well as the string form of the current path being walked.  Whenever we
528*c5591576SRob Johnston  * eoncounter the "to" vertex, we save the current path to the all_paths list
529*c5591576SRob Johnston  * (which keeps track of all the paths we've found to the "to" vertex) and
530*c5591576SRob Johnston  * increment npaths (which keeps track of the number of paths we've found to
531*c5591576SRob Johnston  * the "to" vertex).
532*c5591576SRob Johnston  */
533*c5591576SRob Johnston 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*c5591576SRob Johnston visit_vertex(topo_hdl_t *thp, topo_vertex_t *vtx, topo_vertex_t *to,
535*c5591576SRob Johnston     topo_list_t *all_paths, const char *curr_path,
536*c5591576SRob Johnston     topo_list_t *curr_path_comps, uint_t *npaths)
537*c5591576SRob Johnston {
538*c5591576SRob Johnston 	struct digraph_path *pathnode = NULL;
539*c5591576SRob Johnston 	topo_path_t *path = NULL;
540*c5591576SRob Johnston 	topo_path_component_t *pathcomp = NULL;
541*c5591576SRob Johnston 	nvlist_t *fmri = NULL;
542*c5591576SRob Johnston 	char *pathstr;
543*c5591576SRob Johnston 	int err;
544*c5591576SRob Johnston 
545*c5591576SRob Johnston 	if (asprintf(&pathstr, "%s/%s=%" PRIx64"",
546*c5591576SRob Johnston 	    curr_path,
547*c5591576SRob Johnston 	    topo_node_name(vtx->tvt_node),
548*c5591576SRob Johnston 	    topo_node_instance(vtx->tvt_node)) < 0) {
549*c5591576SRob Johnston 		return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
550*c5591576SRob Johnston 	}
551*c5591576SRob Johnston 
552*c5591576SRob Johnston 	/*
553*c5591576SRob Johnston 	 * Check if this vertex is in the list of vertices in the
554*c5591576SRob Johnston 	 * curr_path_comps list.  If it is, then we've encountered a cycle
555*c5591576SRob Johnston 	 * and need to turn back.
556*c5591576SRob Johnston 	 */
557*c5591576SRob Johnston 	for (topo_path_component_t *pc = topo_list_next(curr_path_comps);
558*c5591576SRob Johnston 	    pc != NULL; pc = topo_list_next(pc)) {
559*c5591576SRob Johnston 		if (pc->tspc_vertex == vtx) {
560*c5591576SRob Johnston 			topo_dprintf(thp, TOPO_DBG_WALK, "Cycle detected: %s",
561*c5591576SRob Johnston 			    pathstr);
562*c5591576SRob Johnston 			free(pathstr);
563*c5591576SRob Johnston 			return (0);
564*c5591576SRob Johnston 		}
565*c5591576SRob Johnston 	}
566*c5591576SRob Johnston 
567*c5591576SRob Johnston 	if ((pathcomp = topo_hdl_zalloc(thp, sizeof (topo_path_component_t)))
568*c5591576SRob Johnston 	    == NULL) {
569*c5591576SRob Johnston 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
570*c5591576SRob Johnston 		goto err;
571*c5591576SRob Johnston 	}
572*c5591576SRob Johnston 	pathcomp->tspc_vertex = vtx;
573*c5591576SRob Johnston 	topo_list_append(curr_path_comps, pathcomp);
574*c5591576SRob Johnston 
575*c5591576SRob Johnston 	if (vtx == to) {
576*c5591576SRob Johnston 		(*npaths)++;
577*c5591576SRob Johnston 		pathnode = topo_hdl_zalloc(thp, sizeof (struct digraph_path));
578*c5591576SRob Johnston 
579*c5591576SRob Johnston 		if ((path = topo_hdl_zalloc(thp, sizeof (topo_path_t))) ==
580*c5591576SRob Johnston 		    NULL ||
581*c5591576SRob Johnston 		    (path->tsp_fmristr = topo_hdl_strdup(thp, pathstr)) ==
582*c5591576SRob Johnston 		    NULL) {
583*c5591576SRob Johnston 			(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
584*c5591576SRob Johnston 			goto err;
585*c5591576SRob Johnston 		}
586*c5591576SRob Johnston 
587*c5591576SRob Johnston 		if (topo_list_deepcopy(thp, &path->tsp_components,
588*c5591576SRob Johnston 		    curr_path_comps, sizeof (topo_path_component_t)) != 0) {
589*c5591576SRob Johnston 			(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
590*c5591576SRob Johnston 		}
591*c5591576SRob Johnston 		if (topo_fmri_str2nvl(thp, pathstr, &fmri, &err) != 0) {
592*c5591576SRob Johnston 			/* errno set */
593*c5591576SRob Johnston 			goto err;
594*c5591576SRob Johnston 		}
595*c5591576SRob Johnston 		path->tsp_fmri = fmri;
596*c5591576SRob Johnston 		pathnode->dgp_path = path;
597*c5591576SRob Johnston 
598*c5591576SRob Johnston 		topo_list_append(all_paths, pathnode);
599*c5591576SRob Johnston 		free(pathstr);
600*c5591576SRob Johnston 		topo_list_delete(curr_path_comps, pathcomp);
601*c5591576SRob Johnston 		topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
602*c5591576SRob Johnston 		return (0);
603*c5591576SRob Johnston 	}
604*c5591576SRob Johnston 
605*c5591576SRob Johnston 	for (topo_edge_t *edge = topo_list_next(&vtx->tvt_outgoing);
606*c5591576SRob Johnston 	    edge != NULL; edge = topo_list_next(edge)) {
607*c5591576SRob Johnston 
608*c5591576SRob Johnston 		if (visit_vertex(thp, edge->tve_vertex, to, all_paths, pathstr,
609*c5591576SRob Johnston 		    curr_path_comps, npaths) != 0)
610*c5591576SRob Johnston 			goto err;
611*c5591576SRob Johnston 	}
612*c5591576SRob Johnston 
613*c5591576SRob Johnston 	free(pathstr);
614*c5591576SRob Johnston 	topo_list_delete(curr_path_comps, pathcomp);
615*c5591576SRob Johnston 	topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
616*c5591576SRob Johnston 	return (0);
617*c5591576SRob Johnston 
618*c5591576SRob Johnston err:
619*c5591576SRob Johnston 	free(pathstr);
620*c5591576SRob Johnston 	topo_hdl_free(thp, pathnode, sizeof (struct digraph_path));
621*c5591576SRob Johnston 	topo_path_destroy(thp, path);
622*c5591576SRob Johnston 	return (-1);
623*c5591576SRob Johnston }
624*c5591576SRob Johnston 
625*c5591576SRob Johnston /*
626*c5591576SRob Johnston  * On success, 0 is returns and the "paths" parameter is populated with an
627*c5591576SRob Johnston  * array of topo_path_t structs representing all paths from the "from" vertex
628*c5591576SRob Johnston  * to the "to" vertex.  The caller is responsible for freeing this array.  The
629*c5591576SRob Johnston  * "npaths" parameter will be populated with the number of paths found or 0 if
630*c5591576SRob Johnston  * no paths were found.
631*c5591576SRob Johnston  *
632*c5591576SRob Johnston  * On error, -1 is returned.
633*c5591576SRob Johnston  */
634*c5591576SRob Johnston 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*c5591576SRob Johnston topo_digraph_paths(topo_hdl_t *thp, topo_digraph_t *tdg, topo_vertex_t *from,
636*c5591576SRob Johnston     topo_vertex_t *to, topo_path_t ***paths, uint_t *npaths)
637*c5591576SRob Johnston {
638*c5591576SRob Johnston 	topo_list_t all_paths = { 0 };
639*c5591576SRob Johnston 	char *curr_path;
640*c5591576SRob Johnston 	topo_path_component_t *pathcomp = NULL;
641*c5591576SRob Johnston 	topo_list_t curr_path_comps = { 0 };
642*c5591576SRob Johnston 	struct digraph_path *path;
643*c5591576SRob Johnston 	uint_t i;
644*c5591576SRob Johnston 	int ret;
645*c5591576SRob Johnston 
646*c5591576SRob Johnston 	if (asprintf(&curr_path, "%s://%s=%s/%s=%" PRIx64"",
647*c5591576SRob Johnston 	    FM_FMRI_SCHEME_PATH, FM_FMRI_SCHEME, tdg->tdg_scheme,
648*c5591576SRob Johnston 	    topo_node_name(from->tvt_node),
649*c5591576SRob Johnston 	    topo_node_instance(from->tvt_node)) < 1) {
650*c5591576SRob Johnston 		return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
651*c5591576SRob Johnston 	}
652*c5591576SRob Johnston 
653*c5591576SRob Johnston 	if ((pathcomp = topo_hdl_zalloc(thp, sizeof (topo_path_component_t)))
654*c5591576SRob Johnston 	    == NULL) {
655*c5591576SRob Johnston 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
656*c5591576SRob Johnston 		goto err;
657*c5591576SRob Johnston 	}
658*c5591576SRob Johnston 	pathcomp->tspc_vertex = from;
659*c5591576SRob Johnston 	topo_list_append(&curr_path_comps, pathcomp);
660*c5591576SRob Johnston 
661*c5591576SRob Johnston 	*npaths = 0;
662*c5591576SRob Johnston 	for (topo_edge_t *edge = topo_list_next(&from->tvt_outgoing);
663*c5591576SRob Johnston 	    edge != NULL; edge = topo_list_next(edge)) {
664*c5591576SRob Johnston 
665*c5591576SRob Johnston 		ret = visit_vertex(thp, edge->tve_vertex, to, &all_paths,
666*c5591576SRob Johnston 		    curr_path, &curr_path_comps, npaths);
667*c5591576SRob Johnston 		if (ret != 0) {
668*c5591576SRob Johnston 			/* errno set */
669*c5591576SRob Johnston 			goto err;
670*c5591576SRob Johnston 		}
671*c5591576SRob Johnston 	}
672*c5591576SRob Johnston 	topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
673*c5591576SRob Johnston 
674*c5591576SRob Johnston 	/*
675*c5591576SRob Johnston 	 * No paths were found between the "from" and "to" vertices, so
676*c5591576SRob Johnston 	 * we're done here.
677*c5591576SRob Johnston 	 */
678*c5591576SRob Johnston 	if (*npaths == 0) {
679*c5591576SRob Johnston 		free(curr_path);
680*c5591576SRob Johnston 		return (0);
681*c5591576SRob Johnston 	}
682*c5591576SRob Johnston 
683*c5591576SRob Johnston 	*paths = topo_hdl_zalloc(thp, (*npaths) * sizeof (topo_path_t *));
684*c5591576SRob Johnston 	if (*paths == NULL) {
685*c5591576SRob Johnston 		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
686*c5591576SRob Johnston 		goto err;
687*c5591576SRob Johnston 	}
688*c5591576SRob Johnston 
689*c5591576SRob Johnston 	for (i = 0, path = topo_list_next(&all_paths); path != NULL;
690*c5591576SRob Johnston 	    i++, path = topo_list_next(path)) {
691*c5591576SRob Johnston 
692*c5591576SRob Johnston 		*((*paths) + i) = path->dgp_path;
693*c5591576SRob Johnston 	}
694*c5591576SRob Johnston 
695*c5591576SRob Johnston 	path = topo_list_next(&all_paths);
696*c5591576SRob Johnston 	while (path != NULL) {
697*c5591576SRob Johnston 		struct digraph_path *tmp = path;
698*c5591576SRob Johnston 
699*c5591576SRob Johnston 		path = topo_list_next(path);
700*c5591576SRob Johnston 		topo_hdl_free(thp, tmp, sizeof (struct digraph_path));
701*c5591576SRob Johnston 	}
702*c5591576SRob Johnston 	free(curr_path);
703*c5591576SRob Johnston 	return (0);
704*c5591576SRob Johnston 
705*c5591576SRob Johnston err:
706*c5591576SRob Johnston 	free(curr_path);
707*c5591576SRob Johnston 	path = topo_list_next(&all_paths);
708*c5591576SRob Johnston 	while (path != NULL) {
709*c5591576SRob Johnston 		struct digraph_path *tmp = path;
710*c5591576SRob Johnston 
711*c5591576SRob Johnston 		path = topo_list_next(path);
712*c5591576SRob Johnston 		topo_hdl_free(thp, tmp, sizeof (struct digraph_path));
713*c5591576SRob Johnston 	}
714*c5591576SRob Johnston 
715*c5591576SRob Johnston 	topo_dprintf(thp, TOPO_DBG_ERR, "%s: failed (%s)", __func__,
716*c5591576SRob Johnston 	    topo_hdl_errmsg(thp));
717*c5591576SRob Johnston 	return (-1);
718*c5591576SRob Johnston }
719*c5591576SRob Johnston 
720*c5591576SRob Johnston /* Helper function for path_fmri_nvl2str() */
721*c5591576SRob Johnston static ssize_t
fmri_bufsz(nvlist_t * nvl)722*c5591576SRob Johnston fmri_bufsz(nvlist_t *nvl)
723*c5591576SRob Johnston {
724*c5591576SRob Johnston 	char *dg_scheme = NULL;
725*c5591576SRob Johnston 	nvlist_t **hops, *auth;
726*c5591576SRob Johnston 	uint_t nhops;
727*c5591576SRob Johnston 	ssize_t bufsz = 1;
728*c5591576SRob Johnston 	int ret;
729*c5591576SRob Johnston 
730*c5591576SRob Johnston 	if (nvlist_lookup_nvlist(nvl, FM_FMRI_AUTHORITY, &auth) != 0 ||
731*c5591576SRob Johnston 	    nvlist_lookup_string(auth, FM_FMRI_PATH_DIGRAPH_SCHEME,
732*c5591576SRob Johnston 	    &dg_scheme) != 0) {
733*c5591576SRob Johnston 		return (0);
734*c5591576SRob Johnston 	}
735*c5591576SRob Johnston 
736*c5591576SRob Johnston 	if ((ret = snprintf(NULL, 0, "%s://%s=%s", FM_FMRI_SCHEME_PATH,
737*c5591576SRob Johnston 	    FM_FMRI_SCHEME, dg_scheme)) < 0) {
738*c5591576SRob Johnston 		return (-1);
739*c5591576SRob Johnston 	}
740*c5591576SRob Johnston 	bufsz += ret;
741*c5591576SRob Johnston 
742*c5591576SRob Johnston 	if (nvlist_lookup_nvlist_array(nvl, FM_FMRI_PATH, &hops, &nhops) !=
743*c5591576SRob Johnston 	    0) {
744*c5591576SRob Johnston 		return (0);
745*c5591576SRob Johnston 	}
746*c5591576SRob Johnston 
747*c5591576SRob Johnston 	for (uint_t i = 0; i < nhops; i++) {
748*c5591576SRob Johnston 		char *name;
749*c5591576SRob Johnston 		uint64_t inst;
750*c5591576SRob Johnston 
751*c5591576SRob Johnston 		if (nvlist_lookup_string(hops[i], FM_FMRI_PATH_NAME, &name) !=
752*c5591576SRob Johnston 		    0 ||
753*c5591576SRob Johnston 		    nvlist_lookup_uint64(hops[i], FM_FMRI_PATH_INST, &inst) !=
754*c5591576SRob Johnston 		    0) {
755*c5591576SRob Johnston 			return (0);
756*c5591576SRob Johnston 		}
757*c5591576SRob Johnston 		if ((ret = snprintf(NULL, 0, "/%s=%" PRIx64 "", name, inst)) <
758*c5591576SRob Johnston 		    0) {
759*c5591576SRob Johnston 			return (-1);
760*c5591576SRob Johnston 		}
761*c5591576SRob Johnston 		bufsz += ret;
762*c5591576SRob Johnston 	}
763*c5591576SRob Johnston 	return (bufsz);
764*c5591576SRob Johnston }
765*c5591576SRob Johnston 
766