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 } 286