1 /****************************************************************************** 2 * 3 * Module Name: nswalk - Functions for walking the ACPI namespace 4 * 5 *****************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2008, Intel Corp. 9 * All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions, and the following disclaimer, 16 * without modification. 17 * 2. Redistributions in binary form must reproduce at minimum a disclaimer 18 * substantially similar to the "NO WARRANTY" disclaimer below 19 * ("Disclaimer") and any redistribution must be conditioned upon 20 * including a substantially similar Disclaimer requirement for further 21 * binary redistribution. 22 * 3. Neither the names of the above-listed copyright holders nor the names 23 * of any contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * Alternatively, this software may be distributed under the terms of the 27 * GNU General Public License ("GPL") version 2 as published by the Free 28 * Software Foundation. 29 * 30 * NO WARRANTY 31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 34 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 35 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 36 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 37 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 38 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 40 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 41 * POSSIBILITY OF SUCH DAMAGES. 42 */ 43 44 #include <acpi/acpi.h> 45 #include "accommon.h" 46 #include "acnamesp.h" 47 48 #define _COMPONENT ACPI_NAMESPACE 49 ACPI_MODULE_NAME("nswalk") 50 51 /******************************************************************************* 52 * 53 * FUNCTION: acpi_ns_get_next_node 54 * 55 * PARAMETERS: parent_node - Parent node whose children we are 56 * getting 57 * child_node - Previous child that was found. 58 * The NEXT child will be returned 59 * 60 * RETURN: struct acpi_namespace_node - Pointer to the NEXT child or NULL if 61 * none is found. 62 * 63 * DESCRIPTION: Return the next peer node within the namespace. If Handle 64 * is valid, Scope is ignored. Otherwise, the first node 65 * within Scope is returned. 66 * 67 ******************************************************************************/ 68 struct acpi_namespace_node *acpi_ns_get_next_node(struct acpi_namespace_node 69 *parent_node, 70 struct acpi_namespace_node 71 *child_node) 72 { 73 ACPI_FUNCTION_ENTRY(); 74 75 if (!child_node) { 76 77 /* It's really the parent's _scope_ that we want */ 78 79 return parent_node->child; 80 } 81 82 /* 83 * Get the next node. 84 * 85 * If we are at the end of this peer list, return NULL 86 */ 87 if (child_node->flags & ANOBJ_END_OF_PEER_LIST) { 88 return NULL; 89 } 90 91 /* Otherwise just return the next peer */ 92 93 return child_node->peer; 94 } 95 96 /******************************************************************************* 97 * 98 * FUNCTION: acpi_ns_get_next_node_typed 99 * 100 * PARAMETERS: Type - Type of node to be searched for 101 * parent_node - Parent node whose children we are 102 * getting 103 * child_node - Previous child that was found. 104 * The NEXT child will be returned 105 * 106 * RETURN: struct acpi_namespace_node - Pointer to the NEXT child or NULL if 107 * none is found. 108 * 109 * DESCRIPTION: Return the next peer node within the namespace. If Handle 110 * is valid, Scope is ignored. Otherwise, the first node 111 * within Scope is returned. 112 * 113 ******************************************************************************/ 114 115 struct acpi_namespace_node *acpi_ns_get_next_node_typed(acpi_object_type type, 116 struct 117 acpi_namespace_node 118 *parent_node, 119 struct 120 acpi_namespace_node 121 *child_node) 122 { 123 struct acpi_namespace_node *next_node = NULL; 124 125 ACPI_FUNCTION_ENTRY(); 126 127 next_node = acpi_ns_get_next_node(parent_node, child_node); 128 129 130 /* If any type is OK, we are done */ 131 132 if (type == ACPI_TYPE_ANY) { 133 134 /* next_node is NULL if we are at the end-of-list */ 135 136 return (next_node); 137 } 138 139 /* Must search for the node -- but within this scope only */ 140 141 while (next_node) { 142 143 /* If type matches, we are done */ 144 145 if (next_node->type == type) { 146 return (next_node); 147 } 148 149 /* Otherwise, move on to the next node */ 150 151 next_node = acpi_ns_get_next_valid_node(next_node); 152 } 153 154 /* Not found */ 155 156 return (NULL); 157 } 158 159 /******************************************************************************* 160 * 161 * FUNCTION: acpi_ns_walk_namespace 162 * 163 * PARAMETERS: Type - acpi_object_type to search for 164 * start_node - Handle in namespace where search begins 165 * max_depth - Depth to which search is to reach 166 * Flags - Whether to unlock the NS before invoking 167 * the callback routine 168 * pre_order_visit - Called during tree pre-order visit 169 * when an object of "Type" is found 170 * post_order_visit - Called during tree post-order visit 171 * when an object of "Type" is found 172 * Context - Passed to user function(s) above 173 * return_value - from the user_function if terminated 174 * early. Otherwise, returns NULL. 175 * RETURNS: Status 176 * 177 * DESCRIPTION: Performs a modified depth-first walk of the namespace tree, 178 * starting (and ending) at the node specified by start_handle. 179 * The callback function is called whenever a node that matches 180 * the type parameter is found. If the callback function returns 181 * a non-zero value, the search is terminated immediately and 182 * this value is returned to the caller. 183 * 184 * The point of this procedure is to provide a generic namespace 185 * walk routine that can be called from multiple places to 186 * provide multiple services; the callback function(s) can be 187 * tailored to each task, whether it is a print function, 188 * a compare function, etc. 189 * 190 ******************************************************************************/ 191 192 acpi_status 193 acpi_ns_walk_namespace(acpi_object_type type, 194 acpi_handle start_node, 195 u32 max_depth, 196 u32 flags, 197 acpi_walk_callback pre_order_visit, 198 acpi_walk_callback post_order_visit, 199 void *context, void **return_value) 200 { 201 acpi_status status; 202 acpi_status mutex_status; 203 struct acpi_namespace_node *child_node; 204 struct acpi_namespace_node *parent_node; 205 acpi_object_type child_type; 206 u32 level; 207 u8 node_previously_visited = FALSE; 208 209 ACPI_FUNCTION_TRACE(ns_walk_namespace); 210 211 /* Special case for the namespace Root Node */ 212 213 if (start_node == ACPI_ROOT_OBJECT) { 214 start_node = acpi_gbl_root_node; 215 } 216 217 /* Null child means "get first node" */ 218 219 parent_node = start_node; 220 child_node = acpi_ns_get_next_node(parent_node, NULL); 221 child_type = ACPI_TYPE_ANY; 222 level = 1; 223 224 /* 225 * Traverse the tree of nodes until we bubble back up to where we 226 * started. When Level is zero, the loop is done because we have 227 * bubbled up to (and passed) the original parent handle (start_entry) 228 */ 229 while (level > 0 && child_node) { 230 status = AE_OK; 231 232 /* Found next child, get the type if we are not searching for ANY */ 233 234 if (type != ACPI_TYPE_ANY) { 235 child_type = child_node->type; 236 } 237 238 /* 239 * Ignore all temporary namespace nodes (created during control 240 * method execution) unless told otherwise. These temporary nodes 241 * can cause a race condition because they can be deleted during 242 * the execution of the user function (if the namespace is 243 * unlocked before invocation of the user function.) Only the 244 * debugger namespace dump will examine the temporary nodes. 245 */ 246 if ((child_node->flags & ANOBJ_TEMPORARY) && 247 !(flags & ACPI_NS_WALK_TEMP_NODES)) { 248 status = AE_CTRL_DEPTH; 249 } 250 251 /* Type must match requested type */ 252 253 else if (child_type == type) { 254 /* 255 * Found a matching node, invoke the user callback function. 256 * Unlock the namespace if flag is set. 257 */ 258 if (flags & ACPI_NS_WALK_UNLOCK) { 259 mutex_status = 260 acpi_ut_release_mutex(ACPI_MTX_NAMESPACE); 261 if (ACPI_FAILURE(mutex_status)) { 262 return_ACPI_STATUS(mutex_status); 263 } 264 } 265 266 /* 267 * Invoke the user function, either pre-order or post-order 268 * or both. 269 */ 270 if (!node_previously_visited) { 271 if (pre_order_visit) { 272 status = 273 pre_order_visit(child_node, level, 274 context, 275 return_value); 276 } 277 } else { 278 if (post_order_visit) { 279 status = 280 post_order_visit(child_node, level, 281 context, 282 return_value); 283 } 284 } 285 286 if (flags & ACPI_NS_WALK_UNLOCK) { 287 mutex_status = 288 acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE); 289 if (ACPI_FAILURE(mutex_status)) { 290 return_ACPI_STATUS(mutex_status); 291 } 292 } 293 294 switch (status) { 295 case AE_OK: 296 case AE_CTRL_DEPTH: 297 298 /* Just keep going */ 299 break; 300 301 case AE_CTRL_TERMINATE: 302 303 /* Exit now, with OK status */ 304 305 return_ACPI_STATUS(AE_OK); 306 307 default: 308 309 /* All others are valid exceptions */ 310 311 return_ACPI_STATUS(status); 312 } 313 } 314 315 /* 316 * Depth first search: Attempt to go down another level in the 317 * namespace if we are allowed to. Don't go any further if we have 318 * reached the caller specified maximum depth or if the user 319 * function has specified that the maximum depth has been reached. 320 */ 321 if (!node_previously_visited && 322 (level < max_depth) && (status != AE_CTRL_DEPTH)) { 323 if (child_node->child) { 324 325 /* There is at least one child of this node, visit it */ 326 327 level++; 328 parent_node = child_node; 329 child_node = 330 acpi_ns_get_next_node(parent_node, NULL); 331 continue; 332 } 333 } 334 335 /* No more children, re-visit this node */ 336 337 if (!node_previously_visited) { 338 node_previously_visited = TRUE; 339 continue; 340 } 341 342 /* No more children, visit peers */ 343 344 child_node = acpi_ns_get_next_node(parent_node, child_node); 345 if (child_node) { 346 node_previously_visited = FALSE; 347 } 348 349 /* No peers, re-visit parent */ 350 351 else { 352 /* 353 * No more children of this node (acpi_ns_get_next_node failed), go 354 * back upwards in the namespace tree to the node's parent. 355 */ 356 level--; 357 child_node = parent_node; 358 parent_node = acpi_ns_get_parent_node(parent_node); 359 360 node_previously_visited = TRUE; 361 } 362 } 363 364 /* Complete walk, not terminated by user function */ 365 366 return_ACPI_STATUS(AE_OK); 367 } 368