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 } 173 174 /* Null child means "get first node" */ 175 176 parent_node = start_node; 177 child_node = acpi_ns_get_next_node(parent_node, NULL); 178 child_type = ACPI_TYPE_ANY; 179 level = 1; 180 181 /* 182 * Traverse the tree of nodes until we bubble back up to where we 183 * started. When Level is zero, the loop is done because we have 184 * bubbled up to (and passed) the original parent handle (start_entry) 185 */ 186 while (level > 0 && child_node) { 187 status = AE_OK; 188 189 /* Found next child, get the type if we are not searching for ANY */ 190 191 if (type != ACPI_TYPE_ANY) { 192 child_type = child_node->type; 193 } 194 195 /* 196 * Ignore all temporary namespace nodes (created during control 197 * method execution) unless told otherwise. These temporary nodes 198 * can cause a race condition because they can be deleted during 199 * the execution of the user function (if the namespace is 200 * unlocked before invocation of the user function.) Only the 201 * debugger namespace dump will examine the temporary nodes. 202 */ 203 if ((child_node->flags & ANOBJ_TEMPORARY) && 204 !(flags & ACPI_NS_WALK_TEMP_NODES)) { 205 status = AE_CTRL_DEPTH; 206 } 207 208 /* Type must match requested type */ 209 210 else if (child_type == type) { 211 /* 212 * Found a matching node, invoke the user callback function. 213 * Unlock the namespace if flag is set. 214 */ 215 if (flags & ACPI_NS_WALK_UNLOCK) { 216 mutex_status = 217 acpi_ut_release_mutex(ACPI_MTX_NAMESPACE); 218 if (ACPI_FAILURE(mutex_status)) { 219 return_ACPI_STATUS(mutex_status); 220 } 221 } 222 223 /* 224 * Invoke the user function, either descending, ascending, 225 * or both. 226 */ 227 if (!node_previously_visited) { 228 if (descending_callback) { 229 status = 230 descending_callback(child_node, 231 level, context, 232 return_value); 233 } 234 } else { 235 if (ascending_callback) { 236 status = 237 ascending_callback(child_node, 238 level, context, 239 return_value); 240 } 241 } 242 243 if (flags & ACPI_NS_WALK_UNLOCK) { 244 mutex_status = 245 acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE); 246 if (ACPI_FAILURE(mutex_status)) { 247 return_ACPI_STATUS(mutex_status); 248 } 249 } 250 251 switch (status) { 252 case AE_OK: 253 case AE_CTRL_DEPTH: 254 255 /* Just keep going */ 256 break; 257 258 case AE_CTRL_TERMINATE: 259 260 /* Exit now, with OK status */ 261 262 return_ACPI_STATUS(AE_OK); 263 264 default: 265 266 /* All others are valid exceptions */ 267 268 return_ACPI_STATUS(status); 269 } 270 } 271 272 /* 273 * Depth first search: Attempt to go down another level in the 274 * namespace if we are allowed to. Don't go any further if we have 275 * reached the caller specified maximum depth or if the user 276 * function has specified that the maximum depth has been reached. 277 */ 278 if (!node_previously_visited && 279 (level < max_depth) && (status != AE_CTRL_DEPTH)) { 280 if (child_node->child) { 281 282 /* There is at least one child of this node, visit it */ 283 284 level++; 285 parent_node = child_node; 286 child_node = 287 acpi_ns_get_next_node(parent_node, NULL); 288 continue; 289 } 290 } 291 292 /* No more children, re-visit this node */ 293 294 if (!node_previously_visited) { 295 node_previously_visited = TRUE; 296 continue; 297 } 298 299 /* No more children, visit peers */ 300 301 child_node = acpi_ns_get_next_node(parent_node, child_node); 302 if (child_node) { 303 node_previously_visited = FALSE; 304 } 305 306 /* No peers, re-visit parent */ 307 308 else { 309 /* 310 * No more children of this node (acpi_ns_get_next_node failed), go 311 * back upwards in the namespace tree to the node's parent. 312 */ 313 level--; 314 child_node = parent_node; 315 parent_node = parent_node->parent; 316 317 node_previously_visited = TRUE; 318 } 319 } 320 321 /* Complete walk, not terminated by user function */ 322 323 return_ACPI_STATUS(AE_OK); 324 } 325