1 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0 2 /****************************************************************************** 3 * 4 * Module Name: nswalk - Functions for walking the ACPI namespace 5 * 6 * Copyright (C) 2000 - 2021, Intel Corp. 7 * 8 *****************************************************************************/ 9 10 #include <acpi/acpi.h> 11 #include "accommon.h" 12 #include "acnamesp.h" 13 14 #define _COMPONENT ACPI_NAMESPACE 15 ACPI_MODULE_NAME("nswalk") 16 17 /******************************************************************************* 18 * 19 * FUNCTION: acpi_ns_get_next_node 20 * 21 * PARAMETERS: parent_node - Parent node whose children we are 22 * getting 23 * child_node - Previous child that was found. 24 * The NEXT child will be returned 25 * 26 * RETURN: struct acpi_namespace_node - Pointer to the NEXT child or NULL if 27 * none is found. 28 * 29 * DESCRIPTION: Return the next peer node within the namespace. If Handle 30 * is valid, Scope is ignored. Otherwise, the first node 31 * within Scope is returned. 32 * 33 ******************************************************************************/ 34 struct acpi_namespace_node *acpi_ns_get_next_node(struct acpi_namespace_node 35 *parent_node, 36 struct acpi_namespace_node 37 *child_node) 38 { 39 ACPI_FUNCTION_ENTRY(); 40 41 if (!child_node) { 42 43 /* It's really the parent's _scope_ that we want */ 44 45 return (parent_node->child); 46 } 47 48 /* Otherwise just return the next peer */ 49 50 return (child_node->peer); 51 } 52 53 /******************************************************************************* 54 * 55 * FUNCTION: acpi_ns_get_next_node_typed 56 * 57 * PARAMETERS: type - Type of node to be searched for 58 * parent_node - Parent node whose children we are 59 * getting 60 * child_node - Previous child that was found. 61 * The NEXT child will be returned 62 * 63 * RETURN: struct acpi_namespace_node - Pointer to the NEXT child or NULL if 64 * none is found. 65 * 66 * DESCRIPTION: Return the next peer node within the namespace. If Handle 67 * is valid, Scope is ignored. Otherwise, the first node 68 * within Scope is returned. 69 * 70 ******************************************************************************/ 71 72 struct acpi_namespace_node *acpi_ns_get_next_node_typed(acpi_object_type type, 73 struct 74 acpi_namespace_node 75 *parent_node, 76 struct 77 acpi_namespace_node 78 *child_node) 79 { 80 struct acpi_namespace_node *next_node = NULL; 81 82 ACPI_FUNCTION_ENTRY(); 83 84 next_node = acpi_ns_get_next_node(parent_node, child_node); 85 86 87 /* If any type is OK, we are done */ 88 89 if (type == ACPI_TYPE_ANY) { 90 91 /* next_node is NULL if we are at the end-of-list */ 92 93 return (next_node); 94 } 95 96 /* Must search for the node -- but within this scope only */ 97 98 while (next_node) { 99 100 /* If type matches, we are done */ 101 102 if (next_node->type == type) { 103 return (next_node); 104 } 105 106 /* Otherwise, move on to the next peer node */ 107 108 next_node = next_node->peer; 109 } 110 111 /* Not found */ 112 113 return (NULL); 114 } 115 116 /******************************************************************************* 117 * 118 * FUNCTION: acpi_ns_walk_namespace 119 * 120 * PARAMETERS: type - acpi_object_type to search for 121 * start_node - Handle in namespace where search begins 122 * max_depth - Depth to which search is to reach 123 * flags - Whether to unlock the NS before invoking 124 * the callback routine 125 * descending_callback - Called during tree descent 126 * when an object of "Type" is found 127 * ascending_callback - Called during tree ascent 128 * when an object of "Type" is found 129 * context - Passed to user function(s) above 130 * return_value - from the user_function if terminated 131 * early. Otherwise, returns NULL. 132 * RETURNS: Status 133 * 134 * DESCRIPTION: Performs a modified depth-first walk of the namespace tree, 135 * starting (and ending) at the node specified by start_handle. 136 * The callback function is called whenever a node that matches 137 * the type parameter is found. If the callback function returns 138 * a non-zero value, the search is terminated immediately and 139 * this value is returned to the caller. 140 * 141 * The point of this procedure is to provide a generic namespace 142 * walk routine that can be called from multiple places to 143 * provide multiple services; the callback function(s) can be 144 * tailored to each task, whether it is a print function, 145 * a compare function, etc. 146 * 147 ******************************************************************************/ 148 149 acpi_status 150 acpi_ns_walk_namespace(acpi_object_type type, 151 acpi_handle start_node, 152 u32 max_depth, 153 u32 flags, 154 acpi_walk_callback descending_callback, 155 acpi_walk_callback ascending_callback, 156 void *context, void **return_value) 157 { 158 acpi_status status; 159 acpi_status mutex_status; 160 struct acpi_namespace_node *child_node; 161 struct acpi_namespace_node *parent_node; 162 acpi_object_type child_type; 163 u32 level; 164 u8 node_previously_visited = FALSE; 165 166 ACPI_FUNCTION_TRACE(ns_walk_namespace); 167 168 /* Special case for the namespace Root Node */ 169 170 if (start_node == ACPI_ROOT_OBJECT) { 171 start_node = acpi_gbl_root_node; 172 if (!start_node) { 173 return_ACPI_STATUS(AE_NO_NAMESPACE); 174 } 175 } 176 177 /* Null child means "get first node" */ 178 179 parent_node = start_node; 180 child_node = acpi_ns_get_next_node(parent_node, NULL); 181 child_type = ACPI_TYPE_ANY; 182 level = 1; 183 184 /* 185 * Traverse the tree of nodes until we bubble back up to where we 186 * started. When Level is zero, the loop is done because we have 187 * bubbled up to (and passed) the original parent handle (start_entry) 188 */ 189 while (level > 0 && child_node) { 190 status = AE_OK; 191 192 /* Found next child, get the type if we are not searching for ANY */ 193 194 if (type != ACPI_TYPE_ANY) { 195 child_type = child_node->type; 196 } 197 198 /* 199 * Ignore all temporary namespace nodes (created during control 200 * method execution) unless told otherwise. These temporary nodes 201 * can cause a race condition because they can be deleted during 202 * the execution of the user function (if the namespace is 203 * unlocked before invocation of the user function.) Only the 204 * debugger namespace dump will examine the temporary nodes. 205 */ 206 if ((child_node->flags & ANOBJ_TEMPORARY) && 207 !(flags & ACPI_NS_WALK_TEMP_NODES)) { 208 status = AE_CTRL_DEPTH; 209 } 210 211 /* Type must match requested type */ 212 213 else if (child_type == type) { 214 /* 215 * Found a matching node, invoke the user callback function. 216 * Unlock the namespace if flag is set. 217 */ 218 if (flags & ACPI_NS_WALK_UNLOCK) { 219 mutex_status = 220 acpi_ut_release_mutex(ACPI_MTX_NAMESPACE); 221 if (ACPI_FAILURE(mutex_status)) { 222 return_ACPI_STATUS(mutex_status); 223 } 224 } 225 226 /* 227 * Invoke the user function, either descending, ascending, 228 * or both. 229 */ 230 if (!node_previously_visited) { 231 if (descending_callback) { 232 status = 233 descending_callback(child_node, 234 level, context, 235 return_value); 236 } 237 } else { 238 if (ascending_callback) { 239 status = 240 ascending_callback(child_node, 241 level, context, 242 return_value); 243 } 244 } 245 246 if (flags & ACPI_NS_WALK_UNLOCK) { 247 mutex_status = 248 acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE); 249 if (ACPI_FAILURE(mutex_status)) { 250 return_ACPI_STATUS(mutex_status); 251 } 252 } 253 254 switch (status) { 255 case AE_OK: 256 case AE_CTRL_DEPTH: 257 258 /* Just keep going */ 259 break; 260 261 case AE_CTRL_TERMINATE: 262 263 /* Exit now, with OK status */ 264 265 return_ACPI_STATUS(AE_OK); 266 267 default: 268 269 /* All others are valid exceptions */ 270 271 return_ACPI_STATUS(status); 272 } 273 } 274 275 /* 276 * Depth first search: Attempt to go down another level in the 277 * namespace if we are allowed to. Don't go any further if we have 278 * reached the caller specified maximum depth or if the user 279 * function has specified that the maximum depth has been reached. 280 */ 281 if (!node_previously_visited && 282 (level < max_depth) && (status != AE_CTRL_DEPTH)) { 283 if (child_node->child) { 284 285 /* There is at least one child of this node, visit it */ 286 287 level++; 288 parent_node = child_node; 289 child_node = 290 acpi_ns_get_next_node(parent_node, NULL); 291 continue; 292 } 293 } 294 295 /* No more children, re-visit this node */ 296 297 if (!node_previously_visited) { 298 node_previously_visited = TRUE; 299 continue; 300 } 301 302 /* No more children, visit peers */ 303 304 child_node = acpi_ns_get_next_node(parent_node, child_node); 305 if (child_node) { 306 node_previously_visited = FALSE; 307 } 308 309 /* No peers, re-visit parent */ 310 311 else { 312 /* 313 * No more children of this node (acpi_ns_get_next_node failed), go 314 * back upwards in the namespace tree to the node's parent. 315 */ 316 level--; 317 child_node = parent_node; 318 parent_node = parent_node->parent; 319 320 node_previously_visited = TRUE; 321 } 322 } 323 324 /* Complete walk, not terminated by user function */ 325 326 return_ACPI_STATUS(AE_OK); 327 } 328