/*
 * This file and its contents are supplied under the terms of the
 * Common Development and Distribution License ("CDDL"), version 1.0.
 * You may only use this file in accordance with the terms of version
 * 1.0 of the CDDL.
 *
 * A full copy of the text of the CDDL should have accompanied this
 * source.  A copy of the CDDL is also available via the Internet at
 * http://www.illumos.org/license/CDDL.
 */

/*
 * Copyright 2020 Joyent, Inc.
 */

/*
 * This file implements a set of APIs for creating, destroying and traversing
 * directed-graph (digraph) topologies.  The API is split into categories:
 * client API and module API.
 *
 * The client API can be used by libtopo consumers for traversing an existing
 * digraph topology.  The module API can be used by topo plugins to create or
 * destroy a digraph topology.
 *
 * client API
 * ----------
 * topo_digraph_get
 * topo_vertex_iter
 * topo_vertex_node
 * topo_edge_iter
 * topo_digraph_paths
 * topo_path_destroy
 *
 * module API
 * ----------
 * topo_digraph_new
 * topo_digraph_destroy
 * topo_vertex_new
 * topo_vertex_destroy
 * topo_edge_new
 *
 * A digraph is represented in-core by a topo_digraph_t structure which
 * maintains an adjacency list of vertices (see topo_digraph.h).  Vertices
 * are represented by topo_vertex_t structures which are essentially thin
 * wrappers around topo node (tnode_t) structures.  In addition to holding
 * a pointer to the underlyng topo node, the topo_vertex_t maintains a list
 * of incoming and outgoing edges and a pointer to the next and previous
 * vertices in digraph's adjecency list.
 *
 * Locking
 * -------
 * The module APIs should only be used during snapshot creation, which is
 * single-threaded, or as the result of a call to topo_snap_release() or
 * topo_close().  While libtopo does prevent concurrent calls to
 * topo_snap_release() and topo_close() via the topo_hdl_t lock, there is no
 * mechanism currently that prevents the situation where one or more threads
 * were to access the snapshot (e.g. they've got a cached tnode_t ptr or are
 * walking the snapshot) while another thread is calling topo_snap_release()
 * or topo_close().  The same is true for tree topologies.  It is up to the
 * library consumer to provide their own synchronization or reference counting
 * mechanism for that case. For example, fmd implements a reference counting
 * mechanism around topo snapshots so that individual fmd modules can safely
 * cache pointers to a given topo snapshot.
 *
 * None of the client APIs modify the state of the graph structure once
 * the snapshot is created.  The exception is the state of the underlyng topo
 * nodes for each vertex, who's properties may change as a result of the
 * following:
 *
 * 1) topo_prop_get operations for properties that are backed by topo methods
 * 2) topo_prop_set operations.
 *
 * For both of the above situations, synchronization is enforced by the per-node
 * locks. Thus there a no locks used for synchronizing access to
 * the topo_digraph_t or topo_vertex_t structures.
 *
 * path scheme FMRIs
 * -----------------
 * For digraph topologies it is useful to be able to treat paths between
 * vertices as resources and thus have a way to represent a unique path
 * between those vertices.  The path FMRI scheme is used for this purpose and
 * has the following form:
 *
 * path://scheme=<scheme>/<nodename>=<instance>/...
 *
 * The path FMRI for a path from one vertex to another vertex is represented by
 * a sequence of nodename/instance pairs where each pair represents a vertex on
 * the path between the two vertices.  The first nodename/instance pair
 * represents the "from" vertex and the last nodename/instance pair represents
 * the "to" vertex.
 *
 * For example, the path FMRI to represent a path from an initiator to a
 * target in a SAS scheme digraph might look like this:
 *
 * path://scheme=sas/initiator=5003048023567a00/port=5003048023567a00/
 *       port=500304801861347f/expander=500304801861347f/port=500304801861347f/
 *       port=5000c500adc881d5/target=5000c500adc881d4
 *
 * This file implements NVL2STR and STR2NVL methods for path-scheme FMRIs.
 */

#include <libtopo.h>
#include <sys/fm/protocol.h>

#include <topo_digraph.h>
#include <topo_method.h>

#define	__STDC_FORMAT_MACROS
#include <inttypes.h>


extern int path_fmri_str2nvl(topo_mod_t *, tnode_t *, topo_version_t,
    nvlist_t *, nvlist_t **);
extern int path_fmri_nvl2str(topo_mod_t *, tnode_t *, topo_version_t,
    nvlist_t *, nvlist_t **);

static const topo_method_t digraph_root_methods[] = {
	{ TOPO_METH_PATH_STR2NVL, TOPO_METH_STR2NVL_DESC,
	    TOPO_METH_STR2NVL_VERSION, TOPO_STABILITY_INTERNAL,
	    path_fmri_str2nvl },
	{ TOPO_METH_PATH_NVL2STR, TOPO_METH_NVL2STR_DESC,
	    TOPO_METH_NVL2STR_VERSION, TOPO_STABILITY_INTERNAL,
	    path_fmri_nvl2str },
	{ NULL }
};

/*
 * On success, returns a pointer to the digraph for the specified FMRI scheme.
 * On failure, returns NULL.
 */
topo_digraph_t *
topo_digraph_get(topo_hdl_t *thp, const char *scheme)
{
	topo_digraph_t *tdg;

	for (tdg = topo_list_next(&thp->th_digraphs); tdg != NULL;
	    tdg = topo_list_next(tdg)) {
		if (strcmp(scheme, tdg->tdg_scheme) == 0)
			return (tdg);
	}
	return (NULL);
}

static topo_digraph_t *
find_digraph(topo_mod_t *mod)
{
	return (topo_digraph_get(mod->tm_hdl, mod->tm_info->tmi_scheme));
}

/*
 * On successs, allocates a new topo_digraph_t structure for the requested
 * scheme.  The caller is responsible for free all memory allocated for this
 * structure when done via a call to topo_digraph_destroy().
 *
 * On failure, this function returns NULL and sets topo errno.
 */
topo_digraph_t *
topo_digraph_new(topo_hdl_t *thp, topo_mod_t *mod, const char *scheme)
{
	topo_digraph_t *tdg;
	tnode_t *tn = NULL;

	if ((tdg = topo_mod_zalloc(mod, sizeof (topo_digraph_t))) == NULL) {
		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
		return (NULL);
	}

	tdg->tdg_mod = mod;

	if ((tdg->tdg_scheme = topo_mod_strdup(mod, scheme)) == NULL) {
		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
		goto err;
	}

	/*
	 * For digraph topologies, the "root" node, which gets passed in to
	 * the scheme module's enum method is not part of the actual graph
	 * structure per-se.
	 * Its purpose is simply to provide a place on which to register the
	 * scheme-specific methods.  Client code then invokes these methods via
	 * the topo_fmri_* interfaces.
	 */
	if ((tn = topo_mod_zalloc(mod, sizeof (tnode_t))) == NULL)
		goto err;

	/*
	 * Adding the TOPO_NODE_ROOT state to the node has the effect of
	 * preventing topo_node_destroy() from trying to clean up the parent
	 * node's node hash, which is only necessary in tree topologies.
	 */
	tn->tn_state = TOPO_NODE_ROOT | TOPO_NODE_INIT;
	tn->tn_name = (char *)scheme;
	tn->tn_instance = 0;
	tn->tn_enum = mod;
	tn->tn_hdl = thp;
	topo_node_hold(tn);

	tdg->tdg_rootnode = tn;
	if (topo_method_register(mod, tn, digraph_root_methods) != 0) {
		topo_mod_dprintf(mod, "failed to register digraph root "
		    "methods");
		/* errno set */
		return (NULL);
	}

	/* This is released during topo_digraph_destroy() */
	topo_mod_hold(mod);

	return (tdg);
err:
	topo_mod_free(mod, tdg, sizeof (topo_digraph_t));
	return (NULL);
}

/*
 * Deallocates all memory associated with the specified topo_digraph_t.
 *
 * This only frees the memory allocated during topo_digraph_new().  To free the
 * actual graph vertices one should call topo_snap_destroy() prior to calling
 * topo_digraph_destroy().
 *
 * Calling topo_close() will also result in a call to topo_snap_destroy() and
 * topo_digraph_dstroy() for all digraphs associated with the library handle.
 *
 * This function is a NOP if NULL is passed in.
 */
void
topo_digraph_destroy(topo_digraph_t *tdg)
{
	topo_mod_t *mod;

	if (tdg == NULL)
		return;

	mod = tdg->tdg_mod;
	topo_method_unregister_all(mod, tdg->tdg_rootnode);
	topo_mod_strfree(mod, (char *)tdg->tdg_scheme);
	topo_mod_free(mod, tdg->tdg_rootnode, sizeof (tnode_t));
	topo_mod_free(mod, tdg, sizeof (topo_digraph_t));
	topo_mod_rele(mod);
}

/*
 * This function creates a new vertex and adds it to the digraph associated
 * with the module.
 *
 * name: name of the vertex
 * instance: instance number of the vertex
 *
 * On success, it returns a pointer to the allocated topo_vertex_t associated
 * with the new vertex.  The caller is responsible for free-ing this structure
 * via a call to topo_vertex_destroy().
 *
 * On failures, this function returns NULL and sets topo_mod_errno.
 */
topo_vertex_t *
topo_vertex_new(topo_mod_t *mod, const char *name, topo_instance_t inst)
{
	tnode_t *tn = NULL;
	topo_vertex_t *vtx = NULL;
	topo_digraph_t *tdg;

	topo_mod_dprintf(mod, "Creating vertex %s=%" PRIx64 "", name, inst);
	if ((tdg = find_digraph(mod)) == NULL) {
		topo_mod_dprintf(mod, "%s faild: no existing digraph for FMRI "
		    " scheme %s", __func__, mod->tm_info->tmi_scheme);
		return (NULL);
	}
	if ((vtx = topo_mod_zalloc(mod, sizeof (topo_vertex_t))) == NULL ||
	    (tn = topo_mod_zalloc(mod, sizeof (tnode_t))) == NULL) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}
	if ((tn->tn_name = topo_mod_strdup(mod, name)) == NULL) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}
	tn->tn_enum = mod;
	tn->tn_hdl = mod->tm_hdl;
	tn->tn_vtx = vtx;
	tn->tn_instance = inst;
	/*
	 * Adding the TOPO_NODE_ROOT state to the node has the effect of
	 * preventing topo_node_destroy() from trying to clean up the parent
	 * node's node hash, which is only necessary in tree topologies.
	 */
	tn->tn_state = TOPO_NODE_ROOT | TOPO_NODE_BOUND;
	vtx->tvt_node = tn;
	topo_node_hold(tn);

	/* Bump the refcnt on the module that's creating this vertex. */
	topo_mod_hold(mod);

	if (tdg->tdg_nvertices == UINT32_MAX) {
		topo_mod_dprintf(mod, "Max vertices reached!");
		(void) topo_mod_seterrno(mod, EMOD_DIGRAPH_MAXSZ);
		topo_mod_rele(mod);
		goto err;
	}
	tdg->tdg_nvertices++;
	topo_list_append(&tdg->tdg_vertices, vtx);

	return (vtx);
err:
	topo_mod_dprintf(mod, "failed to add create vertex %s=%" PRIx64 "(%s)",
	    name, inst, topo_strerror(topo_mod_errno(mod)));
	if (tn != NULL) {
		topo_mod_strfree(mod, tn->tn_name);
		topo_mod_free(mod, tn, sizeof (tnode_t));
	}
	if (vtx != NULL)
		topo_mod_free(mod, vtx, sizeof (topo_vertex_t));

	return (NULL);
}

/*
 * Returns the underlying tnode_t structure for the specified vertex.
 */
tnode_t *
topo_vertex_node(topo_vertex_t *vtx)
{
	return (vtx->tvt_node);
}

/*
 * Convenience interface for deallocating a topo_vertex_t
 * This function is a NOP if NULL is passed in.
 */
void
topo_vertex_destroy(topo_mod_t *mod, topo_vertex_t *vtx)
{
	topo_edge_t *edge;

	if (vtx == NULL)
		return;

	topo_node_unbind(vtx->tvt_node);

	edge = topo_list_next(&vtx->tvt_incoming);
	while (edge != NULL) {
		topo_edge_t *tmp = edge;

		edge = topo_list_next(edge);
		topo_mod_free(mod, tmp, sizeof (topo_edge_t));
	}

	edge = topo_list_next(&vtx->tvt_outgoing);
	while (edge != NULL) {
		topo_edge_t *tmp = edge;

		edge = topo_list_next(edge);
		topo_mod_free(mod, tmp, sizeof (topo_edge_t));
	}

	topo_mod_free(mod, vtx, sizeof (topo_vertex_t));
}

/*
 * This function can be used to iterate over all of the vertices in the
 * specified digraph.  The specified callback function is invoked for each
 * vertices.  Callback function should return the standard topo walker
 * (TOPO_WALK_*) return values.
 *
 * On success, this function returns 0.
 *
 * On failure this function returns -1.
 */
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)
{
	uint_t n = 0;

	for (topo_vertex_t *vtx = topo_list_next(&tdg->tdg_vertices);
	    vtx != NULL; vtx = topo_list_next(vtx), n++) {
		int ret;
		boolean_t last_vtx = B_FALSE;

		if (n == (tdg->tdg_nvertices - 1))
			last_vtx = B_TRUE;

		ret = func(thp, vtx, last_vtx, arg);

		switch (ret) {
		case TOPO_WALK_NEXT:
			continue;
		case TOPO_WALK_TERMINATE:
			goto out;
		case TOPO_WALK_ERR:
		default:
			return (-1);
		}
	}
out:
	return (0);
}

/*
 * Add a new outgoing edge the vertex "from" to the vertex "to".
 *
 * On success, this functions returns 0.
 *
 * On failure, this function returns -1.
 */
int
topo_edge_new(topo_mod_t *mod, topo_vertex_t *from, topo_vertex_t *to)
{
	topo_digraph_t *tdg;
	topo_edge_t *e_from = NULL, *e_to = NULL;

	topo_mod_dprintf(mod, "Adding edge from vertex %s=%" PRIx64 " to "
	    "%s=%" PRIx64"", topo_node_name(from->tvt_node),
	    topo_node_instance(from->tvt_node),
	    topo_node_name(to->tvt_node), topo_node_instance(to->tvt_node));

	if ((tdg = find_digraph(mod)) == NULL) {
		topo_mod_dprintf(mod, "Digraph lookup failed");
		return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
	}
	if (from->tvt_noutgoing == UINT32_MAX ||
	    to->tvt_nincoming == UINT32_MAX ||
	    tdg->tdg_nedges == UINT32_MAX) {
		topo_mod_dprintf(mod, "Max edges reached!");
		return (topo_mod_seterrno(mod, EMOD_DIGRAPH_MAXSZ));

	}
	if ((e_from = topo_mod_zalloc(mod, sizeof (topo_edge_t))) == NULL ||
	    (e_to = topo_mod_zalloc(mod, sizeof (topo_edge_t))) == NULL) {
		topo_mod_free(mod, e_from, sizeof (topo_edge_t));
		topo_mod_free(mod, e_to, sizeof (topo_edge_t));
		return (topo_mod_seterrno(mod, EMOD_NOMEM));
	}
	e_from->tve_vertex = from;
	e_to->tve_vertex = to;

	topo_list_append(&from->tvt_outgoing, e_to);
	from->tvt_noutgoing++;
	topo_list_append(&to->tvt_incoming, e_from);
	to->tvt_nincoming++;
	tdg->tdg_nedges++;

	return (0);
}

/*
 * This function can be used to iterate over all of the outgoing edges in
 * for specified vertex.  The specified callback function is invoked for each
 * edge.  Callback function should return the standard topo walker
 * (TOPO_WALK_*) return values.
 *
 * On success, this function returns 0.
 *
 * On failure this function returns -1.
 */
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)
{
	uint_t n = 0;

	for (topo_edge_t *edge = topo_list_next(&vtx->tvt_outgoing);
	    edge != NULL; edge = topo_list_next(edge), n++) {
		int ret;
		boolean_t last_edge = B_FALSE;

		if (n == (vtx->tvt_noutgoing - 1))
			last_edge = B_TRUE;

		ret = func(thp, edge, last_edge, arg);

		switch (ret) {
		case TOPO_WALK_NEXT:
			continue;
		case TOPO_WALK_TERMINATE:
			break;
		case TOPO_WALK_ERR:
		default:
			return (-1);
		}
	}
	return (0);
}

/*
 * Convenience interface for deallocating a topo_path_t
 * This function is a NOP if NULL is passed in.
 */
void
topo_path_destroy(topo_hdl_t *thp, topo_path_t *path)
{
	topo_path_component_t *pathcomp;

	if (path == NULL)
		return;

	topo_hdl_strfree(thp, (char *)path->tsp_fmristr);
	nvlist_free(path->tsp_fmri);

	pathcomp = topo_list_next(&path->tsp_components);
	while (pathcomp != NULL) {
		topo_path_component_t *tmp = pathcomp;

		pathcomp = topo_list_next(pathcomp);
		topo_hdl_free(thp, tmp, sizeof (topo_path_component_t));
	}

	topo_hdl_free(thp, path, sizeof (topo_path_t));
}

/*
 * This just wraps topo_path_t so that visit_vertex() can build a linked list
 * of paths.
 */
struct digraph_path {
	topo_list_t	dgp_link;
	topo_path_t	*dgp_path;
};

/*
 * This is a callback function for the vertex iteration that gets initiated by
 * topo_digraph_paths().
 *
 * This is used to implement a depth-first search for all paths that lead to
 * the vertex pointed to by the "to" parameter.  As we walk the graph we
 * maintain a linked list of the components (vertices) in the in-progress path
 * as well as the string form of the current path being walked.  Whenever we
 * eoncounter the "to" vertex, we save the current path to the all_paths list
 * (which keeps track of all the paths we've found to the "to" vertex) and
 * increment npaths (which keeps track of the number of paths we've found to
 * the "to" vertex).
 */
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)
{
	struct digraph_path *pathnode = NULL;
	topo_path_t *path = NULL;
	topo_path_component_t *pathcomp = NULL;
	nvlist_t *fmri = NULL;
	char *pathstr;
	int err;

	if (asprintf(&pathstr, "%s/%s=%" PRIx64"",
	    curr_path,
	    topo_node_name(vtx->tvt_node),
	    topo_node_instance(vtx->tvt_node)) < 0) {
		return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
	}

	/*
	 * Check if this vertex is in the list of vertices in the
	 * curr_path_comps list.  If it is, then we've encountered a cycle
	 * and need to turn back.
	 */
	for (topo_path_component_t *pc = topo_list_next(curr_path_comps);
	    pc != NULL; pc = topo_list_next(pc)) {
		if (pc->tspc_vertex == vtx) {
			topo_dprintf(thp, TOPO_DBG_WALK, "Cycle detected: %s",
			    pathstr);
			free(pathstr);
			return (0);
		}
	}

	if ((pathcomp = topo_hdl_zalloc(thp, sizeof (topo_path_component_t)))
	    == NULL) {
		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
		goto err;
	}
	pathcomp->tspc_vertex = vtx;
	topo_list_append(curr_path_comps, pathcomp);

	if (vtx == to) {
		(*npaths)++;
		pathnode = topo_hdl_zalloc(thp, sizeof (struct digraph_path));

		if ((path = topo_hdl_zalloc(thp, sizeof (topo_path_t))) ==
		    NULL ||
		    (path->tsp_fmristr = topo_hdl_strdup(thp, pathstr)) ==
		    NULL) {
			(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
			goto err;
		}

		if (topo_list_deepcopy(thp, &path->tsp_components,
		    curr_path_comps, sizeof (topo_path_component_t)) != 0) {
			(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
		}
		if (topo_fmri_str2nvl(thp, pathstr, &fmri, &err) != 0) {
			/* errno set */
			goto err;
		}
		path->tsp_fmri = fmri;
		pathnode->dgp_path = path;

		topo_list_append(all_paths, pathnode);
		free(pathstr);
		topo_list_delete(curr_path_comps, pathcomp);
		topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
		return (0);
	}

	for (topo_edge_t *edge = topo_list_next(&vtx->tvt_outgoing);
	    edge != NULL; edge = topo_list_next(edge)) {

		if (visit_vertex(thp, edge->tve_vertex, to, all_paths, pathstr,
		    curr_path_comps, npaths) != 0)
			goto err;
	}

	free(pathstr);
	topo_list_delete(curr_path_comps, pathcomp);
	topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));
	return (0);

err:
	free(pathstr);
	topo_hdl_free(thp, pathnode, sizeof (struct digraph_path));
	topo_path_destroy(thp, path);
	return (-1);
}

/*
 * On success, 0 is returns and the "paths" parameter is populated with an
 * array of topo_path_t structs representing all paths from the "from" vertex
 * to the "to" vertex.  The caller is responsible for freeing this array.  The
 * "npaths" parameter will be populated with the number of paths found or 0 if
 * no paths were found.
 *
 * On error, -1 is returned.
 */
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)
{
	topo_list_t all_paths = { 0 };
	char *curr_path;
	topo_path_component_t *pathcomp = NULL;
	topo_list_t curr_path_comps = { 0 };
	struct digraph_path *path;
	uint_t i;
	int ret;

	if (asprintf(&curr_path, "%s://%s=%s/%s=%" PRIx64"",
	    FM_FMRI_SCHEME_PATH, FM_FMRI_SCHEME, tdg->tdg_scheme,
	    topo_node_name(from->tvt_node),
	    topo_node_instance(from->tvt_node)) < 1) {
		return (topo_hdl_seterrno(thp, ETOPO_NOMEM));
	}

	if ((pathcomp = topo_hdl_zalloc(thp, sizeof (topo_path_component_t)))
	    == NULL) {
		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
		goto err;
	}
	pathcomp->tspc_vertex = from;
	topo_list_append(&curr_path_comps, pathcomp);

	*npaths = 0;
	for (topo_edge_t *edge = topo_list_next(&from->tvt_outgoing);
	    edge != NULL; edge = topo_list_next(edge)) {

		ret = visit_vertex(thp, edge->tve_vertex, to, &all_paths,
		    curr_path, &curr_path_comps, npaths);
		if (ret != 0) {
			/* errno set */
			goto err;
		}
	}
	topo_hdl_free(thp, pathcomp, sizeof (topo_path_component_t));

	/*
	 * No paths were found between the "from" and "to" vertices, so
	 * we're done here.
	 */
	if (*npaths == 0) {
		free(curr_path);
		return (0);
	}

	*paths = topo_hdl_zalloc(thp, (*npaths) * sizeof (topo_path_t *));
	if (*paths == NULL) {
		(void) topo_hdl_seterrno(thp, ETOPO_NOMEM);
		goto err;
	}

	for (i = 0, path = topo_list_next(&all_paths); path != NULL;
	    i++, path = topo_list_next(path)) {

		*((*paths) + i) = path->dgp_path;
	}

	path = topo_list_next(&all_paths);
	while (path != NULL) {
		struct digraph_path *tmp = path;

		path = topo_list_next(path);
		topo_hdl_free(thp, tmp, sizeof (struct digraph_path));
	}
	free(curr_path);
	return (0);

err:
	free(curr_path);
	path = topo_list_next(&all_paths);
	while (path != NULL) {
		struct digraph_path *tmp = path;

		path = topo_list_next(path);
		topo_hdl_free(thp, tmp, sizeof (struct digraph_path));
	}

	topo_dprintf(thp, TOPO_DBG_ERR, "%s: failed (%s)", __func__,
	    topo_hdl_errmsg(thp));
	return (-1);
}

/* Helper function for path_fmri_nvl2str() */
static ssize_t
fmri_bufsz(nvlist_t *nvl)
{
	char *dg_scheme = NULL;
	nvlist_t **hops, *auth;
	uint_t nhops;
	ssize_t bufsz = 1;
	int ret;

	if (nvlist_lookup_nvlist(nvl, FM_FMRI_AUTHORITY, &auth) != 0 ||
	    nvlist_lookup_string(auth, FM_FMRI_PATH_DIGRAPH_SCHEME,
	    &dg_scheme) != 0) {
		return (0);
	}

	if ((ret = snprintf(NULL, 0, "%s://%s=%s", FM_FMRI_SCHEME_PATH,
	    FM_FMRI_SCHEME, dg_scheme)) < 0) {
		return (-1);
	}
	bufsz += ret;

	if (nvlist_lookup_nvlist_array(nvl, FM_FMRI_PATH, &hops, &nhops) !=
	    0) {
		return (0);
	}

	for (uint_t i = 0; i < nhops; i++) {
		char *name;
		uint64_t inst;

		if (nvlist_lookup_string(hops[i], FM_FMRI_PATH_NAME, &name) !=
		    0 ||
		    nvlist_lookup_uint64(hops[i], FM_FMRI_PATH_INST, &inst) !=
		    0) {
			return (0);
		}
		if ((ret = snprintf(NULL, 0, "/%s=%" PRIx64 "", name, inst)) <
		    0) {
			return (-1);
		}
		bufsz += ret;
	}
	return (bufsz);
}

int
path_fmri_nvl2str(topo_mod_t *mod, tnode_t *node, topo_version_t version,
    nvlist_t *in, nvlist_t **out)
{
	uint8_t scheme_vers;
	nvlist_t *outnvl;
	nvlist_t **paths, *auth;
	uint_t nelem;
	ssize_t bufsz, end = 0;
	char *buf, *dg_scheme;
	int ret;

	if (version > TOPO_METH_NVL2STR_VERSION)
		return (topo_mod_seterrno(mod, EMOD_VER_NEW));

	if (nvlist_lookup_uint8(in, FM_FMRI_PATH_VERSION, &scheme_vers) != 0) {
		return (topo_mod_seterrno(mod, EMOD_NOMEM));
	}

	if (scheme_vers != FM_PATH_SCHEME_VERSION) {
		return (topo_mod_seterrno(mod, EMOD_FMRI_NVL));
	}

	/*
	 * Get size of buffer needed to hold the string representation of the
	 * FMRI.
	 */
	bufsz = fmri_bufsz(in);
	if (bufsz == 0) {
		return (topo_mod_seterrno(mod, EMOD_FMRI_MALFORM));
	} else if (bufsz < 1) {
		return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
	}

	if ((buf = topo_mod_zalloc(mod, bufsz)) == NULL) {
		return (topo_mod_seterrno(mod, EMOD_NOMEM));
	}

	/*
	 * We've already successfully done these nvlist lookups in fmri_bufsz()
	 * so we don't worry about checking retvals this time around.
	 */
	(void) nvlist_lookup_nvlist(in, FM_FMRI_AUTHORITY, &auth);
	(void) nvlist_lookup_string(auth, FM_FMRI_PATH_DIGRAPH_SCHEME,
	    &dg_scheme);
	(void) nvlist_lookup_nvlist_array(in, FM_FMRI_PATH, &paths,
	    &nelem);
	if ((ret = snprintf(buf, bufsz, "%s://%s=%s", FM_FMRI_SCHEME_PATH,
	    FM_FMRI_SCHEME, dg_scheme)) < 0) {
		topo_mod_free(mod, buf, bufsz);
		return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
	}
	end += ret;

	for (uint_t i = 0; i < nelem; i++) {
		char *pathname;
		uint64_t pathinst;

		(void) nvlist_lookup_string(paths[i], FM_FMRI_PATH_NAME,
		    &pathname);
		(void) nvlist_lookup_uint64(paths[i], FM_FMRI_PATH_INST,
		    &pathinst);

		if ((ret = snprintf(buf + end, (bufsz - end), "/%s=%" PRIx64 "",
		    pathname, pathinst)) < 0) {
			topo_mod_free(mod, buf, bufsz);
			return (topo_mod_seterrno(mod, EMOD_UNKNOWN));
		}
		end += ret;
	}

	if (topo_mod_nvalloc(mod, &outnvl, NV_UNIQUE_NAME) != 0) {
		topo_mod_free(mod, buf, bufsz);
		return (topo_mod_seterrno(mod, EMOD_FMRI_NVL));
	}
	if (nvlist_add_string(outnvl, "fmri-string", buf) != 0) {
		nvlist_free(outnvl);
		topo_mod_free(mod, buf, bufsz);
		return (topo_mod_seterrno(mod, EMOD_FMRI_NVL));
	}
	topo_mod_free(mod, buf, bufsz);
	*out = outnvl;

	return (0);
}

int
path_fmri_str2nvl(topo_mod_t *mod, tnode_t *node, topo_version_t version,
    nvlist_t *in, nvlist_t **out)
{
	char *fmristr, *tmp = NULL, *lastpair;
	char *dg_scheme, *dg_scheme_end, *pathname, *path_start;
	nvlist_t *fmri = NULL, *auth = NULL, **path = NULL;
	uint_t npairs = 0, i = 0, fmrilen, path_offset;

	if (version > TOPO_METH_STR2NVL_VERSION)
		return (topo_mod_seterrno(mod, EMOD_VER_NEW));

	if (nvlist_lookup_string(in, "fmri-string", &fmristr) != 0)
		return (topo_mod_seterrno(mod, EMOD_METHOD_INVAL));

	if (strncmp(fmristr, "path://", 7) != 0)
		return (topo_mod_seterrno(mod, EMOD_FMRI_MALFORM));

	if (topo_mod_nvalloc(mod, &fmri, NV_UNIQUE_NAME) != 0) {
		/* errno set */
		return (-1);
	}
	if (nvlist_add_string(fmri, FM_FMRI_SCHEME,
	    FM_FMRI_SCHEME_PATH) != 0 ||
	    nvlist_add_uint8(fmri, FM_FMRI_PATH_VERSION,
	    FM_PATH_SCHEME_VERSION) != 0) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}

	/*
	 * We need to make a copy of the fmri string because strtok will
	 * modify it.  We can't use topo_mod_strdup/strfree because
	 * topo_mod_strfree will end up leaking part of the string because
	 * of the NUL chars that strtok inserts - which will cause
	 * topo_mod_strfree to miscalculate the length of the string.  So we
	 * keep track of the length of the original string and use
	 * topo_mod_alloc/topo_mod_free.
	 */
	fmrilen = strlen(fmristr) + 1;
	if ((tmp = topo_mod_alloc(mod, fmrilen)) == NULL) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}
	bcopy(fmristr, tmp, fmrilen);

	/*
	 * Find the offset of the "/" after the authority portion of the FMRI.
	 */
	if ((path_start = strchr(tmp + 7, '/')) == NULL) {
		(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
		goto err;
	}

	path_offset = path_start - tmp;
	pathname = fmristr + path_offset + 1;

	/*
	 * Count the number of "=" chars after the "path:///" portion of the
	 * FMRI to determine how big the path array needs to be.
	 */
	(void) strtok_r(tmp + path_offset, "=", &lastpair);
	while (strtok_r(NULL, "=", &lastpair) != NULL)
		npairs++;

	if (npairs == 0) {
		(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
		goto err;
	}

	if ((path = topo_mod_zalloc(mod, npairs * sizeof (nvlist_t *))) ==
	    NULL) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}

	/*
	 * Build the auth nvlist.  There is only one nvpair in the path FMRI
	 * scheme, which is the scheme of the underlying digraph.
	 */
	if (topo_mod_nvalloc(mod, &auth, NV_UNIQUE_NAME) != 0) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}

	if ((dg_scheme = strchr(tmp + 7, '=')) == NULL ||
	    dg_scheme > path_start) {
		(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
		goto err;
	}
	dg_scheme_end = tmp + path_offset;
	*dg_scheme_end = '\0';

	if (nvlist_add_string(auth, FM_FMRI_PATH_DIGRAPH_SCHEME, dg_scheme) !=
	    0 ||
	    nvlist_add_nvlist(fmri, FM_FMRI_AUTHORITY, auth) != 0) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}

	while (i < npairs) {
		nvlist_t *pathcomp;
		uint64_t pathinst;
		char *end, *addrstr, *estr;

		if (topo_mod_nvalloc(mod, &pathcomp, NV_UNIQUE_NAME) != 0) {
			(void) topo_mod_seterrno(mod, EMOD_NOMEM);
			goto err;
		}
		if ((end = strchr(pathname, '=')) == NULL) {
			(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
			goto err;
		}
		*end = '\0';
		addrstr = end + 1;

		/*
		 * If this is the last pair, then addrstr will already be
		 * nul-terminated.
		 */
		if (i < (npairs - 1)) {
			if ((end = strchr(addrstr, '/')) == NULL) {
				(void) topo_mod_seterrno(mod,
				    EMOD_FMRI_MALFORM);
				goto err;
			}
			*end = '\0';
		}

		/*
		 * Convert addrstr to a uint64_t
		 */
		errno = 0;
		pathinst = strtoull(addrstr, &estr, 16);
		if (errno != 0 || *estr != '\0') {
			(void) topo_mod_seterrno(mod, EMOD_FMRI_MALFORM);
			goto err;
		}

		/*
		 * Add both nvpairs to the nvlist and then add the nvlist to
		 * the path nvlist array.
		 */
		if (nvlist_add_string(pathcomp, FM_FMRI_PATH_NAME, pathname) !=
		    0 ||
		    nvlist_add_uint64(pathcomp, FM_FMRI_PATH_INST, pathinst) !=
		    0) {
			(void) topo_mod_seterrno(mod, EMOD_NOMEM);
			goto err;
		}
		path[i++] = pathcomp;
		pathname = end + 1;
	}
	if (nvlist_add_nvlist_array(fmri, FM_FMRI_PATH, path, npairs) != 0) {
		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
		goto err;
	}
	*out = fmri;

	if (path != NULL) {
		for (i = 0; i < npairs; i++)
			nvlist_free(path[i]);

		topo_mod_free(mod, path, npairs * sizeof (nvlist_t *));
	}
	nvlist_free(auth);
	topo_mod_free(mod, tmp, fmrilen);
	return (0);

err:
	topo_mod_dprintf(mod, "%s failed: %s", __func__,
	    topo_strerror(topo_mod_errno(mod)));
	if (path != NULL) {
		for (i = 0; i < npairs; i++)
			nvlist_free(path[i]);

		topo_mod_free(mod, path, npairs * sizeof (nvlist_t *));
	}
	nvlist_free(auth);
	nvlist_free(fmri);
	if (tmp != NULL)
		topo_mod_free(mod, tmp, fmrilen);
	return (-1);
}