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