1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22/*
23 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
24 */
25
26/*
27 * Walk the LDOM PRI component nodes and create appropriate topology nodes
28 */
29
30#include <sys/types.h>
31#include <sys/time.h>
32#include <stddef.h>
33#include <inttypes.h>
34#include <strings.h>
35#include <string.h>
36#include <libuutil.h>
37#include <libnvpair.h>
38#include <sys/mdesc.h>
39#include <fm/topo_mod.h>
40#include <fm/topo_hc.h>
41#include "pi_impl.h"
42
43#define	PI_STR_MIN	"instance_min"
44#define	PI_STR_MAX	"instance_max"
45
46/*
47 * Allow for custom topo node creation routines based on topo-hc-name.
48 */
49struct pi_enum_functions_s {
50	pi_enum_fn_t	*func;
51	char		*hc_name;	/* topo-hc-name */
52};
53typedef struct pi_enum_functions_s pi_enum_functions_t;
54
55struct pi_methods_s {
56	topo_method_t	*meths;
57	char		*hc_name;
58};
59typedef struct pi_methods_s pi_methods_t;
60
61extern topo_method_t pi_cpu_methods[], pi_mem_methods[];
62
63/*
64 * List of custom enumerators for PRI nodes that require them.  The most
65 * common nodes are listed first.
66 */
67static pi_enum_functions_t pi_enum_fns_builtin[] = {
68	{pi_enum_cpu,		STRAND},
69	{pi_enum_cpu,		CPU},
70	{pi_enum_mem,		DIMM},
71	{pi_enum_cpu,		CORE},
72	{pi_enum_cpu,		CHIP},
73	{pi_enum_hostbridge,	HOSTBRIDGE},
74	{pi_enum_pciexrc,	PCIEX_ROOT},
75	{pi_enum_niu,		NIU},
76	{pi_enum_bay,		BAY},
77	{NULL, NULL}
78};
79static nvlist_t *pi_enum_fns;
80
81/* List of methods that will be registered in the nodes. */
82static pi_methods_t pi_meths_builtin[] = {
83	{pi_cpu_methods,	CHIP},
84	{pi_cpu_methods,	CORE},
85	{pi_cpu_methods,	STRAND},
86	{pi_cpu_methods,	CPU},
87	{pi_mem_methods,	DIMM},
88	{NULL, NULL}
89};
90nvlist_t *pi_meths;
91
92/*
93 * In order to create a topology node from a PRI MDE node we need to know the
94 * topology parent node that should be used.  So, after creating a topology
95 * node from an MDE node, we associate children of the MDE node with the new
96 * topology node.  Thus, when the children are visited we can know the
97 * appropriate parent topology node to use.
98 *
99 * We take advantage of the libtopo threading model here, which guarantees a
100 * single thread and a single invocation at a time for an enumerator.  This
101 * makes using a file-global safe.
102 */
103static uu_list_pool_t	*walker_pool = NULL;
104static uu_list_t	*walker_list = NULL;
105
106struct pi_walkernode_s {
107	uu_list_node_t	walker_node;
108	tnode_t		*t_parent;	/* Parent topology node */
109	mde_cookie_t	mde_node;	/* Child MDE node index */
110};
111typedef struct pi_walkernode_s pi_walkernode_t;
112
113
114/* The routine called for each node in the PRI while walking the graph */
115static int pi_walker_node(md_t *, mde_cookie_t, mde_cookie_t, void *);
116
117/*
118 * Create a sub-range for a given PRI node and associate the given topology
119 * node with the children.
120 */
121static int  pi_walker_node_range(topo_mod_t *, md_t *, tnode_t *, mde_cookie_t);
122static int  pi_walker_node_create(topo_mod_t *, md_t *, mde_cookie_t, tnode_t *,
123    topo_instance_t, tnode_t **);
124
125/* Routines to handle the list of topology parents and mde_nodes */
126static int  pi_walkerlist_compare(const void *, const void *, void *);
127static int  pi_walkerlist_create(topo_mod_t *);
128static void pi_walkerlist_destroy(topo_mod_t *);
129static int  pi_walkerlist_add(topo_mod_t *, tnode_t *, mde_cookie_t);
130static int  pi_walkerlist_addtype(topo_mod_t *, nvlist_t *, char *, uint32_t,
131    uint32_t);
132static int  pi_walkerlist_find(topo_mod_t *, mde_cookie_t, tnode_t **);
133
134
135int
136pi_walker_init(topo_mod_t *mod)
137{
138	int			result;
139	pi_enum_functions_t	*fp;
140	pi_methods_t		*mp;
141
142	result = topo_mod_nvalloc(mod, &pi_enum_fns, NV_UNIQUE_NAME);
143	result |= topo_mod_nvalloc(mod, &pi_meths, NV_UNIQUE_NAME);
144	if (result != 0) {
145		topo_mod_dprintf(mod, "pi_walker_init failed\n");
146		nvlist_free(pi_enum_fns);
147		nvlist_free(pi_meths);
148		return (-1);
149	}
150
151	/* Add the builtin functions to the list */
152	fp = pi_enum_fns_builtin;
153	while (fp != NULL && fp->hc_name != NULL) {
154		uint64_t	faddr;
155
156		faddr = (uint64_t)(uintptr_t)*(fp->func);
157		result |= nvlist_add_uint64(pi_enum_fns, fp->hc_name, faddr);
158		fp++;
159	}
160
161	/* Add the builtin methods to the list */
162	mp = pi_meths_builtin;
163	while (mp != NULL && mp->hc_name != NULL) {
164		uint64_t	maddr;
165
166		maddr = (uint64_t)(uintptr_t)mp->meths;
167		result |= nvlist_add_uint64(pi_meths, mp->hc_name, maddr);
168		mp++;
169	}
170
171	if (result != 0) {
172		topo_mod_dprintf(mod, "pi_walker_init failed\n");
173		nvlist_free(pi_enum_fns);
174		nvlist_free(pi_meths);
175		return (-1);
176	}
177
178	return (0);
179}
180
181
182void
183pi_walker_fini(topo_mod_t *mod)
184{
185	topo_mod_dprintf(mod, "pi_walker_fini: enter\n");
186	nvlist_free(pi_enum_fns);
187	nvlist_free(pi_meths);
188}
189
190
191/*
192 * Begin to walk the machine description array starting at the given PRI node.
193 */
194int
195pi_walker(pi_enum_t *pip, tnode_t *t_parent, const char *hc_name,
196    mde_cookie_t mde_node, mde_str_cookie_t component_cookie,
197    mde_str_cookie_t arc_cookie)
198{
199	int		result;
200	hrtime_t	starttime;
201	hrtime_t	endtime;
202	topo_mod_t	*mod;
203
204	if (pip == NULL) {
205		return (-1);
206	}
207	mod = pip->mod;
208
209	starttime = gethrtime();
210	topo_mod_dprintf(mod, "walker starting at node_0x%llx\n",
211	    mde_node);
212
213	/*
214	 * Create a list to store topology nodes and their associated machine
215	 * description index.  This allows the code to know the parent of a
216	 * node when creating topology entries.
217	 */
218	result = pi_walkerlist_create(mod);
219	if (result != 0) {
220		topo_mod_dprintf(mod, "walker could not create list\n");
221		return (result);
222	}
223
224	/* Create a walker node for the parent of the start node */
225	result = pi_walkerlist_add(mod, t_parent, mde_node);
226	if (result != 0) {
227		pi_walkerlist_destroy(mod);
228		topo_mod_dprintf(mod, "walker could not add to list\n");
229		(void) topo_mod_seterrno(mod, EMOD_UKNOWN_ENUM);
230		return (result);
231	}
232
233	/*
234	 * This is a top-level node.  Make sure we call the top level
235	 * enumerator if there is not already a custom enumerator registered.
236	 */
237	if (! nvlist_exists(pi_enum_fns, hc_name)) {
238		uint64_t	faddr;
239
240		/*
241		 * There is no enumerator function registered for this
242		 * hc name.  Automatically register the top level node
243		 * enumerator function.
244		 */
245		faddr = (uint64_t)(uintptr_t)pi_enum_top;
246		result = nvlist_add_uint64(pi_enum_fns, hc_name, faddr);
247		if (result != 0) {
248			pi_walkerlist_destroy(mod);
249			topo_mod_dprintf(mod,
250			    "walker could not register enumerator for type "
251			    "%s\n", hc_name);
252			(void) topo_mod_seterrno(mod, EMOD_UKNOWN_ENUM);
253			return (-1);
254		}
255		topo_mod_dprintf(mod,
256		    "walker registered pi_enum_top enumerator for type %s\n",
257		    hc_name);
258	}
259
260	/* Walk the machine description list starting at the given node */
261	result = md_walk_dag(pip->mdp, mde_node, component_cookie, arc_cookie,
262	    pi_walker_node, (void *)pip);
263	switch (result) {
264		case 0:
265			/* Successful completion */
266			/* DO NOTHING */
267		break;
268
269		case MDE_WALK_ERROR:
270			/*
271			 * Store that we have a partial enumeration and return
272			 * that we have encountered an error.
273			 */
274			(void) topo_mod_seterrno(mod, EMOD_PARTIAL_ENUM);
275			result = -1;
276		break;
277
278		default:
279			/*
280			 * This should not happen.  We want to always produce
281			 * as complete a topology as possible, even in the face
282			 * of errors, however, so set an error and continue.
283			 */
284			topo_mod_dprintf(mod,
285			    "walker encountered invalid result: %d. "
286			    "Continuing\n", result);
287			(void) topo_mod_seterrno(mod, EMOD_UKNOWN_ENUM);
288			result = 0;
289		break;
290	}
291
292	/* Destroy the walker list, which is no longer necessary */
293	pi_walkerlist_destroy(mod);
294
295	topo_mod_dprintf(mod, "walker done with node_0x%llx\n", mde_node);
296
297	endtime = gethrtime();
298	topo_mod_dprintf(mod, "walker scan time %lld ms\n",
299	    (endtime-starttime)/MICROSEC);
300
301	return (result);
302}
303
304
305/*
306 * Visited once for each node in the machine description.  Creates a topo
307 * node for the machine description node and associates it with it's parent,
308 * by calling an appropriate creation routine for the node type.
309 *
310 * Output:
311 * 	This routine returns MDE_WALK_NEXT, MDE_WALK_DONE or MDE_WALK_ERROR
312 * only.
313 */
314static int
315pi_walker_node(md_t *mdp, mde_cookie_t parent_mde_node, mde_cookie_t mde_node,
316    void *private)
317{
318	int		result;
319	pi_enum_t	*pip	= (pi_enum_t *)private;
320	uint64_t	skip;		/* flag in md to skip this node	*/
321	tnode_t		*t_parent;	/* topo parent to this md node	*/
322	tnode_t		*t_node;	/* topo parent to this md node	*/
323	topo_instance_t	inst;
324
325	topo_mod_t	*mod;
326
327	/* Make sure we have our private data */
328	if (pip == NULL) {
329		return (MDE_WALK_ERROR);
330	}
331	mod = pip->mod;
332
333	topo_mod_dprintf(pip->mod,
334	    "walker processing node_0x%llx parent node 0x%llx\n",
335	    (uint64_t)mde_node, (uint64_t)parent_mde_node);
336
337	/* Should we skip this node ? */
338	skip = pi_skip_node(mod, pip->mdp, mde_node);
339	if (skip) {
340		/* Skip this node and continue to the next node */
341		topo_mod_dprintf(mod, "walker skipping node_0x%llx\n",
342		    (uint64_t)mde_node);
343		return (MDE_WALK_NEXT);
344	}
345
346	result = pi_get_instance(mod, mdp, mde_node, &inst);
347	if (result != 0) {
348		/*
349		 * No ID available to place this mde node in the topology so
350		 * we cannot create a topology node.
351		 */
352		topo_mod_dprintf(mod, "walker skipping node_0x%llx: "
353		    "no instance\n", (uint64_t)mde_node);
354		(void) topo_mod_seterrno(mod, EMOD_PARTIAL_ENUM);
355		return (MDE_WALK_NEXT);
356	}
357
358	/*
359	 * Find the parent topo node for this machine description node.
360	 *
361	 * If found, the element will also be removed from the list and the
362	 * memory used to keep track of it released.  We will only visit an
363	 * MDE node once and so the memory is no longer needed.
364	 */
365	t_parent = NULL;
366	result = pi_walkerlist_find(mod, mde_node, &t_parent);
367	if (result != 0 || t_parent == NULL) {
368		/*
369		 * No parent was found or a NULL parent encountered.  We
370		 * cannot create a new topology node without a parent (
371		 * even for top level nodes).  We associate children of
372		 * this MDE node with a NULL parent to silently skip the
373		 * remainder of this MDE branch.
374		 */
375		topo_mod_dprintf(mod, "no topo parent found for node_0x%llx\n",
376		    mde_node);
377		result = pi_walker_node_range(mod, mdp, NULL, mde_node);
378		(void) topo_mod_seterrno(mod, EMOD_PARTIAL_ENUM);
379
380		return (result);
381	}
382
383	/*
384	 * We have the mde node instance and parent information.
385	 * Attempt to create a topology node for this mde node.
386	 */
387	t_node = NULL;
388	result = pi_walker_node_create(mod, mdp, mde_node, t_parent, inst,
389	    &t_node);
390	if (result != MDE_WALK_NEXT || t_node == NULL) {
391		/*
392		 * We have failed to create a new topology node based on
393		 * the current MDE node.  We set partial enumeration and
394		 * return without associating the children of this MDE
395		 * node with a topology parent.  This will propgate the
396		 * creation error down this MDE branch.
397		 */
398		(void) topo_mod_seterrno(mod, EMOD_PARTIAL_ENUM);
399		return (result);
400	}
401
402	/*
403	 * Associate the new topology node with any children of this mde node.
404	 */
405	result = pi_walker_node_range(mod, mdp, t_node, mde_node);
406
407	topo_mod_dprintf(mod, "walker completed node_0x%llx result = %d\n",
408	    (uint64_t)mde_node, result);
409
410	return (result);
411}
412
413
414static int
415pi_walker_node_create(topo_mod_t *mod, md_t *mdp, mde_cookie_t mde_node,
416    tnode_t *t_parent, topo_instance_t inst, tnode_t **t_node)
417{
418	int		result;
419	char		*hc_name;
420	uint64_t	faddr;
421	pi_enum_fn_t	*func;
422
423	if (t_parent == NULL) {
424		/*
425		 * A parent topology node is required even for top-level
426		 * nodes.
427		 */
428		return (MDE_WALK_NEXT);
429	}
430
431	/*
432	 * Find the topo-hc-name for this node which is used to find
433	 * the specific creation function
434	 */
435	hc_name = pi_get_topo_hc_name(mod, mdp, mde_node);
436	if (hc_name == NULL) {
437		/* Cannot get the hc-name */
438		topo_mod_dprintf(mod,
439		    "failed to find hc-name for node_0x%llx\n", mde_node);
440		return (MDE_WALK_NEXT);
441	}
442
443	/* Determine the topology node creation routine to use */
444	func = pi_enum_generic;
445	faddr = 0;
446	result = nvlist_lookup_uint64(pi_enum_fns, hc_name, &faddr);
447	if (result == 0) {
448		/*
449		 * A function is registered for this node. Convert the
450		 * address to a pointer to function
451		 */
452		func = (pi_enum_fn_t *)(uintptr_t)faddr;
453	}
454
455	/*
456	 * Create a topology node for this mde node by calling the identified
457	 * enumeration function
458	 */
459	*t_node = NULL;
460	result = (func)(mod, mdp, mde_node, inst, t_parent, hc_name, t_node);
461	if (result != 0) {
462		topo_mod_dprintf(mod,
463		    "failed to create topo entry for node_0x%llx type %s\n",
464		    (uint64_t)mde_node, hc_name);
465	}
466
467	topo_mod_strfree(mod, hc_name);
468
469	return (MDE_WALK_NEXT);
470}
471
472
473/*
474 * Scan the children of a given MDE node and find all the sets of topo-hc-name
475 * types and their instance ranges.  From this information we create topology
476 * node ranges on the given parent so that when the children are visited and a
477 * topology node is created, the range exists and the creation will succeed.
478 */
479static int
480pi_walker_node_range(topo_mod_t *mod, md_t *mdp, tnode_t *t_parent,
481    mde_cookie_t mde_node)
482{
483	int		result;
484	int		rc;
485	int		num_arcs;
486	nvlist_t	*typelist;
487	nvpair_t	*nvp;
488	mde_cookie_t	*arcp;
489	size_t		arcsize;
490	int		arcidx;
491	char		*hc_name;
492	nvlist_t	*hc_range;
493	topo_instance_t	inst;
494	uint32_t	min;
495	uint32_t	max;
496
497	if (t_parent == NULL) {
498		topo_mod_dprintf(mod,
499		"walker failed to create node range with a NULL parent\n");
500		return (MDE_WALK_NEXT);
501	}
502
503	/* Determine how many children the given node has */
504	num_arcs = md_get_prop_arcs(mdp, mde_node, MD_STR_FWD, NULL, 0);
505	if (num_arcs == 0) {
506		/* This node has no children */
507		return (MDE_WALK_NEXT);
508	}
509	topo_mod_dprintf(mod, "node_0x%llx has %d children\n",
510	    (uint64_t)mde_node, num_arcs);
511
512	/* Get the indexes for all the child nodes and put them in an array */
513	arcsize	= sizeof (mde_cookie_t) * num_arcs;
514	arcp = topo_mod_zalloc(mod, arcsize);
515	if (arcp == NULL) {
516		topo_mod_dprintf(mod, "out of memory\n");
517		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
518		return (MDE_WALK_ERROR);
519	}
520	num_arcs = md_get_prop_arcs(mdp, mde_node, MD_STR_FWD, arcp, arcsize);
521
522	/*
523	 * The children of the given node may have multiple types.
524	 * Potentially, each child may have a different type and we need to
525	 * create a topo node range for each one.
526	 *
527	 * We loop through the children and collect the type information for
528	 * each one and associate the child with the given parent topo node.
529	 */
530	result = topo_mod_nvalloc(mod, &typelist, NV_UNIQUE_NAME);
531	if (result != 0) {
532		topo_mod_free(mod, arcp, arcsize);
533		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
534		return (MDE_WALK_ERROR);
535	}
536
537	arcidx = 0;
538	for (arcidx = 0; arcidx < num_arcs; arcidx++) {
539		/* Should this node be skipped? */
540		if (pi_skip_node(mod, mdp, arcp[arcidx])) {
541			/* Skip this node */
542			topo_mod_dprintf(mod, "skipping node_0x%llx\n",
543			    (uint64_t)arcp[arcidx]);
544			continue;
545		}
546
547		/* Get the type of this node */
548		hc_name = pi_get_topo_hc_name(mod, mdp, arcp[arcidx]);
549		rc = pi_get_instance(mod, mdp, arcp[arcidx], &inst);
550		if (rc == 0 && hc_name != NULL) {
551			/* Increment the count of nodes with this type */
552			hc_range = NULL;
553			rc = nvlist_lookup_nvlist(typelist, hc_name, &hc_range);
554			if (rc != 0) {
555				/*
556				 * We have not visited this type yet.  Create
557				 * a new range based on this nodes instance
558				 * information.
559				 */
560				result = pi_walkerlist_addtype(mod, typelist,
561				    hc_name, (uint32_t)inst, (uint32_t)inst);
562				if (result != 0) {
563					/*
564					 * This error can only if there was a
565					 * memory failure of some kind.  Stop
566					 * the walk or it will just get worse.
567					 */
568					nvlist_free(typelist);
569					topo_mod_strfree(mod, hc_name);
570					topo_mod_free(mod, arcp, arcsize);
571					(void) topo_mod_seterrno(mod,
572					    EMOD_PARTIAL_ENUM);
573					return (MDE_WALK_ERROR);
574				}
575
576				/*
577				 * We know the list exists now or the above
578				 * would have failed.  Just look it up.
579				 */
580				(void) nvlist_lookup_nvlist(typelist, hc_name,
581				    &hc_range);
582			}
583
584			/* Re-calculate the range minimums and maximums */
585			(void) nvlist_lookup_uint32(hc_range, PI_STR_MIN, &min);
586			(void) nvlist_lookup_uint32(hc_range, PI_STR_MAX, &max);
587			min = MIN(min, (uint32_t)inst);
588			max = MAX(max, (uint32_t)inst);
589			(void) nvlist_add_uint32(hc_range, PI_STR_MIN, min);
590			(void) nvlist_add_uint32(hc_range, PI_STR_MAX, max);
591
592		} else {
593			if (hc_name == NULL) {
594				topo_mod_dprintf(mod, "node_0x%llx has no "
595				    "topo_hc_name.", (uint64_t)arcp[arcidx]);
596				(void) topo_mod_seterrno(mod,
597				    EMOD_PARTIAL_ENUM);
598				return (MDE_WALK_ERROR);
599			}
600
601			topo_mod_dprintf(mod, "node_0x%llx type %s has no id. "
602			    "Excluding from range", (uint64_t)arcp[arcidx],
603			    hc_name);
604		}
605		topo_mod_strfree(mod, hc_name);
606
607		/*
608		 * Associate this node with the given topo parent even if it
609		 * has no instance.  We do this so that later an error with
610		 * the PRI node will be reported instead of an internal
611		 * error about not being able to find the parent of a node
612		 */
613		rc = pi_walkerlist_add(mod, t_parent, arcp[arcidx]);
614		if (rc != 0) {
615			topo_mod_dprintf(mod,
616			    "could not add node_0x%llx to walker list\n",
617			    (uint64_t)arcp[arcidx]);
618		}
619	}
620
621	/*
622	 * We have associated all the child nodes with the given topo parent
623	 * in the walker list.  Now we need to create topo ranges for each
624	 * set of child types under the parent.
625	 */
626	nvp = nvlist_next_nvpair(typelist, NULL);
627	while (nvp != NULL) {
628		/* Get the type name and count from the list element */
629		hc_name = nvpair_name(nvp);
630		(void) nvpair_value_nvlist(nvp, &hc_range);
631		(void) nvlist_lookup_uint32(hc_range, PI_STR_MIN, &min);
632		(void) nvlist_lookup_uint32(hc_range, PI_STR_MAX, &max);
633
634		/*
635		 * We have the number of children with this type.
636		 * Create an appropriate range.
637		 */
638		topo_mod_dprintf(mod,
639		    "creating instance range %d to %d of type %s\n",
640		    min, max, hc_name);
641		rc = topo_node_range_create(mod, t_parent, hc_name,
642		    (topo_instance_t)min, (topo_instance_t)max);
643		if (rc != 0) {
644			topo_mod_dprintf(mod,
645			    "failed to created node range %d to %d for "
646			    "nodes of type %s\n", min, max, hc_name);
647		}
648
649		/* Check the next node */
650		nvp = nvlist_next_nvpair(typelist, nvp);
651	}
652	topo_mod_free(mod, arcp, arcsize);
653	nvlist_free(typelist);
654
655	return (MDE_WALK_NEXT);
656}
657
658
659static int
660pi_walkerlist_addtype(topo_mod_t *mod, nvlist_t *typelist, char *hc_name,
661    uint32_t min, uint32_t max)
662{
663	int		result;
664	nvlist_t	*nvl;
665
666	result = topo_mod_nvalloc(mod, &nvl, NV_UNIQUE_NAME);
667	if (result != 0) {
668		return (result);
669	}
670
671	/* Create min and max elements in this list */
672	if (nvlist_add_uint32(nvl, PI_STR_MIN, min) != 0 ||
673	    nvlist_add_uint32(nvl, PI_STR_MAX, max) != 0 ||
674	    nvlist_add_nvlist(typelist, hc_name, nvl) != 0) {
675		nvlist_free(nvl);
676		return (-1);
677	}
678	nvlist_free(nvl);
679
680	return (0);
681}
682
683
684/* ARGSUSED */
685static int
686pi_walkerlist_compare(const void *left, const void *right, void *private)
687{
688	pi_walkernode_t	*lp = (pi_walkernode_t *)left;
689	pi_walkernode_t	*rp = (pi_walkernode_t *)right;
690
691	if (lp->mde_node > rp->mde_node) {
692		return (1);
693	}
694	if (lp->mde_node < rp->mde_node) {
695		return (-1);
696	}
697	return (0);
698}
699
700
701static int
702pi_walkerlist_create(topo_mod_t *mod)
703{
704	/* Initialize the uutil list structure */
705	walker_pool = uu_list_pool_create("pi_walker_pool",
706	    sizeof (pi_walkernode_t), offsetof(pi_walkernode_t, walker_node),
707	    pi_walkerlist_compare, NULL);
708	if (walker_pool == NULL) {
709		(void) topo_mod_seterrno(mod, EMOD_NOMEM);
710		return (-1);
711	}
712	walker_list = uu_list_create(walker_pool, NULL, 0);
713	if (walker_list == NULL) {
714		uu_list_pool_destroy(walker_pool);
715		walker_pool = NULL;
716		return (-1);
717	}
718
719	return (0);
720}
721
722
723static void
724pi_walkerlist_destroy(topo_mod_t *mod)
725{
726	void		*wvp;
727	pi_walkernode_t	*wp;
728
729	/* Destroy our list of items */
730	while ((wvp = uu_list_first(walker_list)) != NULL) {
731		/*
732		 * First, we empty the list of elements and free each one.
733		 * We do not free the data elements as they are libtopo nodes
734		 * and will be freed by libtopo
735		 */
736		wp = (pi_walkernode_t *)wvp;
737		uu_list_remove(walker_list, wvp);
738		uu_list_node_fini(wp, &(wp->walker_node), walker_pool);
739
740		topo_mod_free(mod, wvp, sizeof (pi_walkernode_t));
741	}
742	uu_list_destroy(walker_list);
743	uu_list_pool_destroy(walker_pool);
744	walker_list = NULL;
745	walker_pool = NULL;
746}
747
748
749static int
750pi_walkerlist_add(topo_mod_t *mod, tnode_t *t_parent, mde_cookie_t mde_node)
751{
752	uu_list_index_t	idx;
753	pi_walkernode_t	*wnp;
754
755	wnp = topo_mod_zalloc(mod, sizeof (pi_walkernode_t));
756	if (wnp == NULL) {
757		topo_mod_dprintf(mod, "failed to add node_0x%llx parent %p\n",
758		    (uint64_t)mde_node, t_parent);
759		return (-1);
760	}
761	uu_list_node_init(wnp, &(wnp->walker_node), walker_pool);
762
763	wnp->t_parent	= t_parent;
764	wnp->mde_node	= mde_node;
765
766	(void) uu_list_find(walker_list, wnp, NULL, &idx);
767	uu_list_insert(walker_list, wnp, idx);
768
769	return (0);
770}
771
772
773/*
774 * Find the parent topo node for this machine description node.
775 *
776 * Nodes are removed from the list as they are found.  They are only
777 * visited once and this eliminates the need for a separate routine
778 * that walks the list to free elements later.
779 */
780static int
781pi_walkerlist_find(topo_mod_t *mod, mde_cookie_t mde_node, tnode_t **tpp)
782{
783	pi_walkernode_t	*result;
784
785	uu_list_index_t	idx;
786	pi_walkernode_t	search_criteria;
787
788	search_criteria.mde_node = mde_node;
789	search_criteria.t_parent = NULL;
790
791	*tpp = NULL;
792	result = uu_list_find(walker_list, &search_criteria, NULL, &idx);
793	if (result == NULL) {
794		return (-1);
795	}
796	*tpp = result->t_parent;
797
798	/* Remove this element from the list */
799	uu_list_remove(walker_list, result);
800	uu_list_node_fini(result, &(result->walker_node), walker_pool);
801	topo_mod_free(mod, result, sizeof (pi_walkernode_t));
802
803	return (0);
804}
805