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, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 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 the tree's data structure */ 35 avl_tree_t aw_tree; /* copy of avl_tree_t being walked */ 36 }; 37 38 /* 39 * common code used to find the addr of the the leftmost child below 40 * an AVL node 41 */ 42 static uintptr_t 43 avl_leftmostchild(uintptr_t addr, void * buff, size_t offset, size_t size) 44 { 45 avl_node_t *node = (avl_node_t *)((uintptr_t)buff + offset); 46 47 for (;;) { 48 addr -= offset; 49 if (mdb_vread(buff, size, addr) == -1) { 50 mdb_warn("read of avl_node_t failed: %p", addr); 51 return ((uintptr_t)-1L); 52 } 53 if (node->avl_child[0] == NULL) 54 break; 55 addr = (uintptr_t)node->avl_child[0]; 56 } 57 return (addr); 58 } 59 60 /* 61 * initialize a forward walk thru an avl tree. 62 */ 63 int 64 avl_walk_init(mdb_walk_state_t *wsp) 65 { 66 struct aw_info *aw; 67 avl_tree_t *tree; 68 uintptr_t addr; 69 70 /* 71 * allocate the AVL walk data 72 */ 73 wsp->walk_data = aw = mdb_zalloc(sizeof (struct aw_info), UM_SLEEP); 74 75 /* 76 * get an mdb copy of the avl_tree_t being walked 77 */ 78 tree = &aw->aw_tree; 79 if (mdb_vread(tree, sizeof (avl_tree_t), wsp->walk_addr) == -1) { 80 mdb_warn("read of avl_tree_t failed: %p", wsp->walk_addr); 81 goto error; 82 } 83 if (tree->avl_size < tree->avl_offset + sizeof (avl_node_t)) { 84 mdb_warn("invalid avl_tree_t at %p, avl_size:%d, avl_offset:%d", 85 wsp->walk_addr, tree->avl_size, tree->avl_offset); 86 goto error; 87 } 88 89 /* 90 * allocate a buffer to hold the mdb copy of tree's structs 91 * "node" always points at the avl_node_t field inside the struct 92 */ 93 aw->aw_buff = mdb_zalloc(tree->avl_size, UM_SLEEP); 94 95 /* 96 * get the first avl_node_t address, use same algorithm 97 * as avl_start() -- leftmost child in tree from root 98 */ 99 addr = (uintptr_t)tree->avl_root; 100 if (addr == NULL) { 101 wsp->walk_addr = NULL; 102 return (WALK_NEXT); 103 } 104 addr = avl_leftmostchild(addr, aw->aw_buff, tree->avl_offset, 105 tree->avl_size); 106 if (addr == (uintptr_t)-1L) 107 goto error; 108 109 wsp->walk_addr = addr; 110 return (WALK_NEXT); 111 112 error: 113 if (aw->aw_buff != NULL) 114 mdb_free(aw->aw_buff, sizeof (tree->avl_size)); 115 mdb_free(aw, sizeof (struct aw_info)); 116 return (WALK_ERR); 117 } 118 119 /* 120 * At each step, visit (callback) the current node, then move to the next 121 * in the AVL tree. Uses the same algorithm as avl_walk(). 122 */ 123 int 124 avl_walk_step(mdb_walk_state_t *wsp) 125 { 126 struct aw_info *aw; 127 size_t offset; 128 size_t size; 129 uintptr_t addr; 130 avl_node_t *node; 131 int status; 132 int was_child; 133 134 /* 135 * don't walk past the end of the tree! 136 */ 137 addr = wsp->walk_addr; 138 if (addr == NULL) 139 return (WALK_DONE); 140 141 aw = (struct aw_info *)wsp->walk_data; 142 size = aw->aw_tree.avl_size; 143 offset = aw->aw_tree.avl_offset; 144 node = (avl_node_t *)((uintptr_t)aw->aw_buff + offset); 145 146 /* 147 * must read the current node for the call back to use 148 */ 149 if (mdb_vread(aw->aw_buff, size, addr) == -1) { 150 mdb_warn("read of avl_node_t failed: %p", addr); 151 return (WALK_ERR); 152 } 153 154 /* 155 * do the call back 156 */ 157 status = wsp->walk_callback(addr, aw->aw_buff, wsp->walk_cbdata); 158 if (status != WALK_NEXT) 159 return (status); 160 161 /* 162 * move to the next node.... 163 * note we read in new nodes, so the pointer to the buffer is fixed 164 */ 165 166 /* 167 * if the node has a right child then go to it and then all the way 168 * thru as many left children as possible 169 */ 170 addr = (uintptr_t)node->avl_child[1]; 171 if (addr != NULL) { 172 addr = avl_leftmostchild(addr, aw->aw_buff, offset, size); 173 if (addr == (uintptr_t)-1L) 174 return (WALK_ERR); 175 176 /* 177 * othewise return to parent nodes, stopping if we ever return from 178 * a left child 179 */ 180 } else { 181 for (;;) { 182 was_child = AVL_XCHILD(node); 183 addr = (uintptr_t)AVL_XPARENT(node); 184 if (addr == NULL) 185 break; 186 addr -= offset; 187 if (was_child == 0) /* stop on return from left child */ 188 break; 189 if (mdb_vread(aw->aw_buff, size, addr) == -1) { 190 mdb_warn("read of avl_node_t failed: %p", addr); 191 return (WALK_ERR); 192 } 193 } 194 } 195 196 wsp->walk_addr = addr; 197 return (WALK_NEXT); 198 } 199 200 /* 201 * Release the memory allocated for the walk 202 */ 203 void 204 avl_walk_fini(mdb_walk_state_t *wsp) 205 { 206 struct aw_info *aw; 207 208 aw = (struct aw_info *)wsp->walk_data; 209 210 if (aw == NULL) 211 return; 212 213 if (aw->aw_buff != NULL) 214 mdb_free(aw->aw_buff, aw->aw_tree.avl_size); 215 216 mdb_free(aw, sizeof (struct aw_info)); 217 } 218