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