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