xref: /titanic_41/usr/src/cmd/mdb/common/modules/genunix/avl.c (revision 0b42f15ac52b077791d4ba079e8c163c592c3fda)
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
avl_leftmostchild(uintptr_t addr,void * buff,size_t offset,size_t size,const char * elem_name)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
avl_walk_init_range(mdb_walk_state_t * wsp,uintptr_t begin,uintptr_t end,const char * avl_name,const char * element_name,int (* element_check)(void *,uintptr_t,void *),void * arg)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
avl_walk_init(mdb_walk_state_t * wsp)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
avl_walk_init_named(mdb_walk_state_t * wsp,const char * avl_name,const char * element_name)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
avl_walk_init_checked(mdb_walk_state_t * wsp,const char * avl_name,const char * element_name,int (* element_check)(void *,uintptr_t,void *),void * arg)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
avl_walk_step(mdb_walk_state_t * wsp)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
avl_walk_fini(mdb_walk_state_t * wsp)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
avl_walk_mdb(uintptr_t addr,mdb_walk_cb_t callback,void * cbdata)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 }
309