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 2008 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 #include <sys/types.h>
28 #include <sys/param.h>
29 #ifdef _KERNEL
30 #include <sys/systm.h>
31 #else
32 #include <string.h>
33 #include <strings.h>
34 #endif
35
36 #include <sys/mdesc.h>
37 #include <sys/mdesc_impl.h>
38
39 static int
40 mdl_walk_dag(md_impl_t *, mde_cookie_t, mde_cookie_t, mde_str_cookie_t,
41 mde_str_cookie_t, uint8_t *, md_walk_fn_t, void *, int);
42
43
44 /*
45 * Walk the machine description directed graph from a starting
46 * node searching for nodes of a given node name and using a
47 * given arc type. Call a callback function for each node found.
48 * Each node will be visited only once.
49 *
50 * Input Description
51 * ------------------- ----------------------------------------
52 * md_t * Pointer to md session
53 * mde_cookie_t Index of the starting node
54 * mde_str_cookie_t Node name cookie of the nodes to call
55 * the walk function
56 * mde_str_cookie_t Arc name cookie of the path to follow
57 * md_walk_fn_t The function to call for each node
58 * void * Private data to pass to the walker function
59 *
60 */
61 int
md_walk_dag(md_t * ptr,mde_cookie_t startnode,mde_str_cookie_t node_name_cookie,mde_str_cookie_t arc_name_cookie,md_walk_fn_t func,void * private)62 md_walk_dag(md_t *ptr, mde_cookie_t startnode,
63 mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
64 md_walk_fn_t func, void *private)
65 {
66 int res;
67 uint8_t *seenp;
68 md_impl_t *mdp;
69 mde_cookie_t start;
70
71 mdp = (md_impl_t *)ptr;
72 if (mdp == NULL) {
73 return (-1);
74 }
75
76 /*
77 * Possible the caller was lazy and didn't check the
78 * validitiy of either the node name or the arc name
79 * on calling ... in which case fail to find any
80 * nodes.
81 * This is distinct, from a fail (-1) since we return
82 * that nothing was found.
83 */
84 if (node_name_cookie == MDE_INVAL_STR_COOKIE ||
85 arc_name_cookie == MDE_INVAL_STR_COOKIE) {
86 return (0);
87 }
88
89 /*
90 * if we want to start at the top, start at index 0
91 */
92 start = startnode;
93 if (start == MDE_INVAL_ELEM_COOKIE) {
94 start = 0;
95 }
96
97 /*
98 * Scan from the start point until the first node.
99 */
100 while (start < mdp->element_count &&
101 MDE_TAG(&mdp->mdep[start]) == MDET_NULL) {
102 start++;
103 }
104
105 /*
106 * This was a bogus start point if no node found
107 */
108 if (MDE_TAG(&mdp->mdep[start]) != MDET_NODE) {
109 return (-1); /* illegal start node specified */
110 }
111
112 /*
113 * Allocate a recursion detection structure so we only visit
114 * each node once.
115 */
116 seenp = (uint8_t *)mdp->allocp(mdp->element_count);
117 if (seenp == NULL) {
118 return (-1);
119 }
120 (void) memset(seenp, 0, mdp->element_count);
121
122 /*
123 * Now build the list of requested nodes.
124 */
125 res = mdl_walk_dag(mdp, MDE_INVAL_ELEM_COOKIE, start,
126 node_name_cookie, arc_name_cookie, seenp, func, private, 0);
127
128 mdp->freep(seenp, mdp->element_count);
129
130 return (res >= 0 ? 0 : res);
131 }
132
133
134 static int
mdl_walk_dag(md_impl_t * mdp,mde_cookie_t parentidx,mde_cookie_t nodeidx,mde_str_cookie_t node_name_cookie,mde_str_cookie_t arc_name_cookie,uint8_t * seenp,md_walk_fn_t func,void * private,int level)135 mdl_walk_dag(md_impl_t *mdp, mde_cookie_t parentidx, mde_cookie_t nodeidx,
136 mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
137 uint8_t *seenp, md_walk_fn_t func, void *private, int level)
138 {
139 int result;
140 md_element_t *mdep;
141
142 /* Get the node element from the session */
143 mdep = &(mdp->mdep[nodeidx]);
144
145 /* see if cookie is infact a node */
146 if (MDE_TAG(mdep) != MDET_NODE) {
147 return (MDE_WALK_ERROR);
148 }
149
150 /* have we been here before ? */
151 if (seenp[nodeidx]) {
152 return (MDE_WALK_NEXT);
153 }
154 seenp[nodeidx] = 1;
155
156 #ifdef DEBUG_LIBMDESC
157 {
158 int x;
159 for (x = 0; x < level; x++) {
160 printf("-");
161 }
162 printf("%d (%s)\n", nodeidx,
163 (char *)(mdp->datap + MDE_NAME(mdep)));
164 }
165 #endif
166
167 /* is this node of the type we seek ? */
168 if (MDE_NAME(mdep) == node_name_cookie) {
169 /*
170 * Yes. Call the callback function.
171 */
172 result = (func)((md_t *)mdp, parentidx, nodeidx, private);
173 if (result != MDE_WALK_NEXT) {
174 return (result);
175 }
176 }
177
178 /*
179 * Simply walk the elements in the node.
180 * if we find a matching arc, then recursively call
181 * the subordinate looking for a match
182 */
183 result = MDE_WALK_NEXT;
184 for (mdep++; MDE_TAG(mdep) != MDET_NODE_END; mdep++) {
185 if (MDE_TAG(mdep) == MDET_PROP_ARC &&
186 MDE_NAME(mdep) == arc_name_cookie) {
187 /*
188 * The current node becomes the parent node, and the
189 * arc index is the new current node.
190 */
191 result = mdl_walk_dag(mdp, nodeidx, mdep->d.prop_idx,
192 node_name_cookie, arc_name_cookie, seenp, func,
193 private, level+1);
194 if (result != MDE_WALK_NEXT) {
195 /* The walk is complete or terminated. */
196 return (result);
197 }
198 }
199 }
200
201 return (result);
202 }
203