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 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 #pragma ident "%Z%%M% %I% %E% SMI"
27
28 #include <sys/avl.h>
29
30 #include <mdb/mdb_modapi.h>
31
32 struct aw_info {
33 void *aw_buff; /* buffer to hold tree element */
34 avl_tree_t aw_tree; /* copy of avl_tree_t being walked */
35 uintptr_t aw_end; /* last node in specified range */
36 const char *aw_elem_name;
37 int (*aw_elem_check)(void *, uintptr_t, void *);
38 void *aw_elem_check_arg;
39 };
40
41 /*
42 * common code used to find the addr of the the leftmost child below
43 * an AVL node
44 */
45 static uintptr_t
46 avl_leftmostchild(uintptr_t addr, void *buff, size_t offset, size_t size,
47 const char *elem_name)
48 {
49 avl_node_t *node = (avl_node_t *)((uintptr_t)buff + offset);
50
51 for (;;) {
52 addr -= offset;
53 if (mdb_vread(buff, size, addr) == -1) {
54 mdb_warn("failed to read %s at %#lx", elem_name, addr);
55 return ((uintptr_t)-1L);
56 }
57 if (node->avl_child[0] == NULL)
58 break;
59 addr = (uintptr_t)node->avl_child[0];
60 }
61 return (addr);
62 }
63
64 /*
65 * initialize a forward walk thru an avl tree.
66 *
67 * begin and end optionally specify objects other than the first and last
68 * objects in the tree; either or both may be NULL (defaulting to first and
69 * last).
70 *
71 * avl_name and element_name specify command-specific labels other than
72 * "avl_tree_t" and "tree element" for use in error messages.
73 *
74 * element_check() returns -1, 1, or 0: abort the walk with an error, stop
75 * without an error, or allow the normal callback; arg is an optional user
76 * argument to element_check().
77 */
78 int
79 avl_walk_init_range(mdb_walk_state_t *wsp, uintptr_t begin, uintptr_t end,
80 const char *avl_name, const char *element_name,
81 int (*element_check)(void *, uintptr_t, void *), void *arg)
82 {
83 struct aw_info *aw;
84 avl_tree_t *tree;
85 uintptr_t addr;
86
87 if (avl_name == NULL)
88 avl_name = "avl_tree_t";
89 if (element_name == NULL)
90 element_name = "tree element";
91
92 /*
93 * allocate the AVL walk data
94 */
95 wsp->walk_data = aw = mdb_zalloc(sizeof (struct aw_info), UM_SLEEP);
96
97 /*
98 * get an mdb copy of the avl_tree_t being walked
99 */
100 tree = &aw->aw_tree;
101 if (mdb_vread(tree, sizeof (avl_tree_t), wsp->walk_addr) == -1) {
102 mdb_warn("failed to read %s at %#lx", avl_name, wsp->walk_addr);
103 goto error;
104 }
105 if (tree->avl_size < tree->avl_offset + sizeof (avl_node_t)) {
106 mdb_warn("invalid avl_tree_t at %p, avl_size:%d, avl_offset:%d",
107 wsp->walk_addr, tree->avl_size, tree->avl_offset);
108 goto error;
109 }
110
111 /*
112 * allocate a buffer to hold the mdb copy of tree's structs
113 * "node" always points at the avl_node_t field inside the struct
114 */
115 aw->aw_buff = mdb_zalloc(tree->avl_size, UM_SLEEP);
116 aw->aw_end = (end == NULL ? NULL : end + tree->avl_offset);
117 aw->aw_elem_name = element_name;
118 aw->aw_elem_check = element_check;
119 aw->aw_elem_check_arg = arg;
120
121 /*
122 * get the first avl_node_t address, use same algorithm
123 * as avl_start() -- leftmost child in tree from root
124 */
125 if (begin == NULL) {
126 addr = (uintptr_t)tree->avl_root;
127 if (addr == NULL) {
128 wsp->walk_addr = NULL;
129 return (WALK_NEXT);
130 }
131 addr = avl_leftmostchild(addr, aw->aw_buff, tree->avl_offset,
132 tree->avl_size, aw->aw_elem_name);
133 if (addr == (uintptr_t)-1L)
134 goto error;
135 wsp->walk_addr = addr;
136 } else {
137 wsp->walk_addr = begin + tree->avl_offset;
138 }
139
140 return (WALK_NEXT);
141
142 error:
143 if (aw->aw_buff != NULL)
144 mdb_free(aw->aw_buff, sizeof (tree->avl_size));
145 mdb_free(aw, sizeof (struct aw_info));
146 return (WALK_ERR);
147 }
148
149 int
150 avl_walk_init(mdb_walk_state_t *wsp)
151 {
152 return (avl_walk_init_range(wsp, NULL, NULL, NULL, NULL, NULL, NULL));
153 }
154
155 int
156 avl_walk_init_named(mdb_walk_state_t *wsp,
157 const char *avl_name, const char *element_name)
158 {
159 return (avl_walk_init_range(wsp, NULL, NULL, avl_name, element_name,
160 NULL, NULL));
161 }
162
163 int
164 avl_walk_init_checked(mdb_walk_state_t *wsp,
165 const char *avl_name, const char *element_name,
166 int (*element_check)(void *, uintptr_t, void *), void *arg)
167 {
168 return (avl_walk_init_range(wsp, NULL, NULL, avl_name, element_name,
169 element_check, arg));
170 }
171
172 /*
173 * At each step, visit (callback) the current node, then move to the next
174 * in the AVL tree. Uses the same algorithm as avl_walk().
175 */
176 int
177 avl_walk_step(mdb_walk_state_t *wsp)
178 {
179 struct aw_info *aw;
180 size_t offset;
181 size_t size;
182 uintptr_t addr;
183 avl_node_t *node;
184 int status;
185 int was_child;
186
187 /*
188 * don't walk past the end of the tree!
189 */
190 addr = wsp->walk_addr;
191 if (addr == NULL)
192 return (WALK_DONE);
193
194 aw = (struct aw_info *)wsp->walk_data;
195
196 if (aw->aw_end != NULL && wsp->walk_addr == aw->aw_end)
197 return (WALK_DONE);
198
199 size = aw->aw_tree.avl_size;
200 offset = aw->aw_tree.avl_offset;
201 node = (avl_node_t *)((uintptr_t)aw->aw_buff + offset);
202
203 /*
204 * must read the current node for the call back to use
205 */
206 if (mdb_vread(aw->aw_buff, size, addr) == -1) {
207 mdb_warn("failed to read %s at %#lx", aw->aw_elem_name, addr);
208 return (WALK_ERR);
209 }
210
211 if (aw->aw_elem_check != NULL) {
212 int rc = aw->aw_elem_check(aw->aw_buff, addr,
213 aw->aw_elem_check_arg);
214 if (rc == -1)
215 return (WALK_ERR);
216 else if (rc == 1)
217 return (WALK_DONE);
218 }
219
220 /*
221 * do the call back
222 */
223 status = wsp->walk_callback(addr, aw->aw_buff, wsp->walk_cbdata);
224 if (status != WALK_NEXT)
225 return (status);
226
227 /*
228 * move to the next node....
229 * note we read in new nodes, so the pointer to the buffer is fixed
230 */
231
232 /*
233 * if the node has a right child then go to it and then all the way
234 * thru as many left children as possible
235 */
236 addr = (uintptr_t)node->avl_child[1];
237 if (addr != NULL) {
238 addr = avl_leftmostchild(addr, aw->aw_buff, offset, size,
239 aw->aw_elem_name);
240 if (addr == (uintptr_t)-1L)
241 return (WALK_ERR);
242
243 /*
244 * othewise return to parent nodes, stopping if we ever return from
245 * a left child
246 */
247 } else {
248 for (;;) {
249 was_child = AVL_XCHILD(node);
250 addr = (uintptr_t)AVL_XPARENT(node);
251 if (addr == NULL)
252 break;
253 addr -= offset;
254 if (was_child == 0) /* stop on return from left child */
255 break;
256 if (mdb_vread(aw->aw_buff, size, addr) == -1) {
257 mdb_warn("failed to read %s at %#lx",
258 aw->aw_elem_name, addr);
259 return (WALK_ERR);
260 }
261 }
262 }
263
264 wsp->walk_addr = addr;
265 return (WALK_NEXT);
266 }
267
268 /*
269 * Release the memory allocated for the walk
270 */
271 void
272 avl_walk_fini(mdb_walk_state_t *wsp)
273 {
274 struct aw_info *aw;
275
276 aw = (struct aw_info *)wsp->walk_data;
277
278 if (aw == NULL)
279 return;
280
281 if (aw->aw_buff != NULL)
282 mdb_free(aw->aw_buff, aw->aw_tree.avl_size);
283
284 mdb_free(aw, sizeof (struct aw_info));
285 }