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