195857638SErik Schmauss // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0
295b482a8SLen Brown /*******************************************************************************
395b482a8SLen Brown *
495b482a8SLen Brown * Module Name: nssearch - Namespace search
595b482a8SLen Brown *
695b482a8SLen Brown ******************************************************************************/
795b482a8SLen Brown
895b482a8SLen Brown #include <acpi/acpi.h>
9e2f7a777SLen Brown #include "accommon.h"
10e2f7a777SLen Brown #include "acnamesp.h"
1195b482a8SLen Brown
12e4c1ebfcSBob Moore #ifdef ACPI_ASL_COMPILER
13e4c1ebfcSBob Moore #include "amlcode.h"
14e4c1ebfcSBob Moore #endif
15e4c1ebfcSBob Moore
1695b482a8SLen Brown #define _COMPONENT ACPI_NAMESPACE
1795b482a8SLen Brown ACPI_MODULE_NAME("nssearch")
1895b482a8SLen Brown
1995b482a8SLen Brown /* Local prototypes */
2095b482a8SLen Brown static acpi_status
2195b482a8SLen Brown acpi_ns_search_parent_tree(u32 target_name,
2295b482a8SLen Brown struct acpi_namespace_node *node,
2395b482a8SLen Brown acpi_object_type type,
2495b482a8SLen Brown struct acpi_namespace_node **return_node);
2595b482a8SLen Brown
2695b482a8SLen Brown /*******************************************************************************
2795b482a8SLen Brown *
2895b482a8SLen Brown * FUNCTION: acpi_ns_search_one_scope
2995b482a8SLen Brown *
3095b482a8SLen Brown * PARAMETERS: target_name - Ascii ACPI name to search for
3195b482a8SLen Brown * parent_node - Starting node where search will begin
32ba494beeSBob Moore * type - Object type to match
3395b482a8SLen Brown * return_node - Where the matched Named obj is returned
3495b482a8SLen Brown *
3595b482a8SLen Brown * RETURN: Status
3695b482a8SLen Brown *
3795b482a8SLen Brown * DESCRIPTION: Search a single level of the namespace. Performs a
3895b482a8SLen Brown * simple search of the specified level, and does not add
3995b482a8SLen Brown * entries or search parents.
4095b482a8SLen Brown *
4195b482a8SLen Brown *
4295b482a8SLen Brown * Named object lists are built (and subsequently dumped) in the
4395b482a8SLen Brown * order in which the names are encountered during the namespace load;
4495b482a8SLen Brown *
4595b482a8SLen Brown * All namespace searching is linear in this implementation, but
4695b482a8SLen Brown * could be easily modified to support any improved search
4795b482a8SLen Brown * algorithm. However, the linear search was chosen for simplicity
4895b482a8SLen Brown * and because the trees are small and the other interpreter
4995b482a8SLen Brown * execution overhead is relatively high.
5095b482a8SLen Brown *
5195b482a8SLen Brown * Note: CPU execution analysis has shown that the AML interpreter spends
5295b482a8SLen Brown * a very small percentage of its time searching the namespace. Therefore,
5395b482a8SLen Brown * the linear search seems to be sufficient, as there would seem to be
5495b482a8SLen Brown * little value in improving the search.
5595b482a8SLen Brown *
5695b482a8SLen Brown ******************************************************************************/
5795b482a8SLen Brown
5895b482a8SLen Brown acpi_status
acpi_ns_search_one_scope(u32 target_name,struct acpi_namespace_node * parent_node,acpi_object_type type,struct acpi_namespace_node ** return_node)5995b482a8SLen Brown acpi_ns_search_one_scope(u32 target_name,
6095b482a8SLen Brown struct acpi_namespace_node *parent_node,
6195b482a8SLen Brown acpi_object_type type,
6295b482a8SLen Brown struct acpi_namespace_node **return_node)
6395b482a8SLen Brown {
6495b482a8SLen Brown struct acpi_namespace_node *node;
6595b482a8SLen Brown
6695b482a8SLen Brown ACPI_FUNCTION_TRACE(ns_search_one_scope);
6795b482a8SLen Brown
6895b482a8SLen Brown #ifdef ACPI_DEBUG_OUTPUT
6995b482a8SLen Brown if (ACPI_LV_NAMES & acpi_dbg_level) {
7095b482a8SLen Brown char *scope_name;
7195b482a8SLen Brown
720e166e4fSLv Zheng scope_name = acpi_ns_get_normalized_pathname(parent_node, TRUE);
7395b482a8SLen Brown if (scope_name) {
7495b482a8SLen Brown ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
7595b482a8SLen Brown "Searching %s (%p) For [%4.4s] (%s)\n",
7695b482a8SLen Brown scope_name, parent_node,
7795b482a8SLen Brown ACPI_CAST_PTR(char, &target_name),
7895b482a8SLen Brown acpi_ut_get_type_name(type)));
7995b482a8SLen Brown
8095b482a8SLen Brown ACPI_FREE(scope_name);
8195b482a8SLen Brown }
8295b482a8SLen Brown }
8395b482a8SLen Brown #endif
8495b482a8SLen Brown
8595b482a8SLen Brown /*
8695b482a8SLen Brown * Search for name at this namespace level, which is to say that we
8795b482a8SLen Brown * must search for the name among the children of this object
8895b482a8SLen Brown */
8995b482a8SLen Brown node = parent_node->child;
9095b482a8SLen Brown while (node) {
9195b482a8SLen Brown
9295b482a8SLen Brown /* Check for match against the name */
9395b482a8SLen Brown
9495b482a8SLen Brown if (node->name.integer == target_name) {
9595b482a8SLen Brown
9695b482a8SLen Brown /* Resolve a control method alias if any */
9795b482a8SLen Brown
9895b482a8SLen Brown if (acpi_ns_get_type(node) ==
9995b482a8SLen Brown ACPI_TYPE_LOCAL_METHOD_ALIAS) {
10095b482a8SLen Brown node =
10195b482a8SLen Brown ACPI_CAST_PTR(struct acpi_namespace_node,
10295b482a8SLen Brown node->object);
10395b482a8SLen Brown }
10495b482a8SLen Brown
10595b482a8SLen Brown /* Found matching entry */
10695b482a8SLen Brown
10795b482a8SLen Brown ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
10895b482a8SLen Brown "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n",
10995b482a8SLen Brown ACPI_CAST_PTR(char, &target_name),
11095b482a8SLen Brown acpi_ut_get_type_name(node->type),
11195b482a8SLen Brown node,
11295b482a8SLen Brown acpi_ut_get_node_name(parent_node),
11395b482a8SLen Brown parent_node));
11495b482a8SLen Brown
11595b482a8SLen Brown *return_node = node;
11695b482a8SLen Brown return_ACPI_STATUS(AE_OK);
11795b482a8SLen Brown }
11895b482a8SLen Brown
11995b482a8SLen Brown /* Didn't match name, move on to the next peer object */
12095b482a8SLen Brown
12195b482a8SLen Brown node = node->peer;
12295b482a8SLen Brown }
12395b482a8SLen Brown
12495b482a8SLen Brown /* Searched entire namespace level, not found */
12595b482a8SLen Brown
12695b482a8SLen Brown ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
127d4913dc6SBob Moore "Name [%4.4s] (%s) not found in search in scope [%4.4s] "
128d4913dc6SBob Moore "%p first child %p\n",
12995b482a8SLen Brown ACPI_CAST_PTR(char, &target_name),
13095b482a8SLen Brown acpi_ut_get_type_name(type),
13195b482a8SLen Brown acpi_ut_get_node_name(parent_node), parent_node,
13295b482a8SLen Brown parent_node->child));
13395b482a8SLen Brown
13495b482a8SLen Brown return_ACPI_STATUS(AE_NOT_FOUND);
13595b482a8SLen Brown }
13695b482a8SLen Brown
13795b482a8SLen Brown /*******************************************************************************
13895b482a8SLen Brown *
13995b482a8SLen Brown * FUNCTION: acpi_ns_search_parent_tree
14095b482a8SLen Brown *
14195b482a8SLen Brown * PARAMETERS: target_name - Ascii ACPI name to search for
142ba494beeSBob Moore * node - Starting node where search will begin
143ba494beeSBob Moore * type - Object type to match
14495b482a8SLen Brown * return_node - Where the matched Node is returned
14595b482a8SLen Brown *
14695b482a8SLen Brown * RETURN: Status
14795b482a8SLen Brown *
14895b482a8SLen Brown * DESCRIPTION: Called when a name has not been found in the current namespace
14995b482a8SLen Brown * level. Before adding it or giving up, ACPI scope rules require
15095b482a8SLen Brown * searching enclosing scopes in cases identified by acpi_ns_local().
15195b482a8SLen Brown *
15295b482a8SLen Brown * "A name is located by finding the matching name in the current
15395b482a8SLen Brown * name space, and then in the parent name space. If the parent
15495b482a8SLen Brown * name space does not contain the name, the search continues
15595b482a8SLen Brown * recursively until either the name is found or the name space
15695b482a8SLen Brown * does not have a parent (the root of the name space). This
15795b482a8SLen Brown * indicates that the name is not found" (From ACPI Specification,
15895b482a8SLen Brown * section 5.3)
15995b482a8SLen Brown *
16095b482a8SLen Brown ******************************************************************************/
16195b482a8SLen Brown
16295b482a8SLen Brown static acpi_status
acpi_ns_search_parent_tree(u32 target_name,struct acpi_namespace_node * node,acpi_object_type type,struct acpi_namespace_node ** return_node)16395b482a8SLen Brown acpi_ns_search_parent_tree(u32 target_name,
16495b482a8SLen Brown struct acpi_namespace_node *node,
16595b482a8SLen Brown acpi_object_type type,
16695b482a8SLen Brown struct acpi_namespace_node **return_node)
16795b482a8SLen Brown {
16895b482a8SLen Brown acpi_status status;
16995b482a8SLen Brown struct acpi_namespace_node *parent_node;
17095b482a8SLen Brown
17195b482a8SLen Brown ACPI_FUNCTION_TRACE(ns_search_parent_tree);
17295b482a8SLen Brown
173c45b5c09SAlexey Starikovskiy parent_node = node->parent;
17495b482a8SLen Brown
17595b482a8SLen Brown /*
17695b482a8SLen Brown * If there is no parent (i.e., we are at the root) or type is "local",
17795b482a8SLen Brown * we won't be searching the parent tree.
17895b482a8SLen Brown */
17995b482a8SLen Brown if (!parent_node) {
18095b482a8SLen Brown ACPI_DEBUG_PRINT((ACPI_DB_NAMES, "[%4.4s] has no parent\n",
18195b482a8SLen Brown ACPI_CAST_PTR(char, &target_name)));
18295b482a8SLen Brown return_ACPI_STATUS(AE_NOT_FOUND);
18395b482a8SLen Brown }
18495b482a8SLen Brown
18595b482a8SLen Brown if (acpi_ns_local(type)) {
18695b482a8SLen Brown ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
18795b482a8SLen Brown "[%4.4s] type [%s] must be local to this scope (no parent search)\n",
18895b482a8SLen Brown ACPI_CAST_PTR(char, &target_name),
18995b482a8SLen Brown acpi_ut_get_type_name(type)));
19095b482a8SLen Brown return_ACPI_STATUS(AE_NOT_FOUND);
19195b482a8SLen Brown }
19295b482a8SLen Brown
19395b482a8SLen Brown /* Search the parent tree */
19495b482a8SLen Brown
19595b482a8SLen Brown ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
19695b482a8SLen Brown "Searching parent [%4.4s] for [%4.4s]\n",
19795b482a8SLen Brown acpi_ut_get_node_name(parent_node),
19895b482a8SLen Brown ACPI_CAST_PTR(char, &target_name)));
19995b482a8SLen Brown
200d4913dc6SBob Moore /* Search parents until target is found or we have backed up to the root */
201d4913dc6SBob Moore
20295b482a8SLen Brown while (parent_node) {
20395b482a8SLen Brown /*
20495b482a8SLen Brown * Search parent scope. Use TYPE_ANY because we don't care about the
20595b482a8SLen Brown * object type at this point, we only care about the existence of
20695b482a8SLen Brown * the actual name we are searching for. Typechecking comes later.
20795b482a8SLen Brown */
20895b482a8SLen Brown status =
20995b482a8SLen Brown acpi_ns_search_one_scope(target_name, parent_node,
21095b482a8SLen Brown ACPI_TYPE_ANY, return_node);
21195b482a8SLen Brown if (ACPI_SUCCESS(status)) {
21295b482a8SLen Brown return_ACPI_STATUS(status);
21395b482a8SLen Brown }
21495b482a8SLen Brown
21595b482a8SLen Brown /* Not found here, go up another level (until we reach the root) */
21695b482a8SLen Brown
217c45b5c09SAlexey Starikovskiy parent_node = parent_node->parent;
21895b482a8SLen Brown }
21995b482a8SLen Brown
22095b482a8SLen Brown /* Not found in parent tree */
22195b482a8SLen Brown
22295b482a8SLen Brown return_ACPI_STATUS(AE_NOT_FOUND);
22395b482a8SLen Brown }
22495b482a8SLen Brown
22595b482a8SLen Brown /*******************************************************************************
22695b482a8SLen Brown *
22795b482a8SLen Brown * FUNCTION: acpi_ns_search_and_enter
22895b482a8SLen Brown *
22995b482a8SLen Brown * PARAMETERS: target_name - Ascii ACPI name to search for (4 chars)
23095b482a8SLen Brown * walk_state - Current state of the walk
231ba494beeSBob Moore * node - Starting node where search will begin
23295b482a8SLen Brown * interpreter_mode - Add names only in ACPI_MODE_LOAD_PASS_x.
23395b482a8SLen Brown * Otherwise,search only.
234ba494beeSBob Moore * type - Object type to match
235ba494beeSBob Moore * flags - Flags describing the search restrictions
23695b482a8SLen Brown * return_node - Where the Node is returned
23795b482a8SLen Brown *
23895b482a8SLen Brown * RETURN: Status
23995b482a8SLen Brown *
24095b482a8SLen Brown * DESCRIPTION: Search for a name segment in a single namespace level,
24195b482a8SLen Brown * optionally adding it if it is not found. If the passed
24295b482a8SLen Brown * Type is not Any and the type previously stored in the
24395b482a8SLen Brown * entry was Any (i.e. unknown), update the stored type.
24495b482a8SLen Brown *
24595b482a8SLen Brown * In ACPI_IMODE_EXECUTE, search only.
24695b482a8SLen Brown * In other modes, search and add if not found.
24795b482a8SLen Brown *
24895b482a8SLen Brown ******************************************************************************/
24995b482a8SLen Brown
25095b482a8SLen Brown acpi_status
acpi_ns_search_and_enter(u32 target_name,struct acpi_walk_state * walk_state,struct acpi_namespace_node * node,acpi_interpreter_mode interpreter_mode,acpi_object_type type,u32 flags,struct acpi_namespace_node ** return_node)25195b482a8SLen Brown acpi_ns_search_and_enter(u32 target_name,
25295b482a8SLen Brown struct acpi_walk_state *walk_state,
25395b482a8SLen Brown struct acpi_namespace_node *node,
25495b482a8SLen Brown acpi_interpreter_mode interpreter_mode,
25595b482a8SLen Brown acpi_object_type type,
25695b482a8SLen Brown u32 flags, struct acpi_namespace_node **return_node)
25795b482a8SLen Brown {
25895b482a8SLen Brown acpi_status status;
25995b482a8SLen Brown struct acpi_namespace_node *new_node;
26095b482a8SLen Brown
26195b482a8SLen Brown ACPI_FUNCTION_TRACE(ns_search_and_enter);
26295b482a8SLen Brown
26395b482a8SLen Brown /* Parameter validation */
26495b482a8SLen Brown
26595b482a8SLen Brown if (!node || !target_name || !return_node) {
26695b482a8SLen Brown ACPI_ERROR((AE_INFO,
267f6a22b0bSBob Moore "Null parameter: Node %p Name 0x%X ReturnNode %p",
26895b482a8SLen Brown node, target_name, return_node));
26995b482a8SLen Brown return_ACPI_STATUS(AE_BAD_PARAMETER);
27095b482a8SLen Brown }
27195b482a8SLen Brown
27295b482a8SLen Brown /*
27395b482a8SLen Brown * Name must consist of valid ACPI characters. We will repair the name if
27495b482a8SLen Brown * necessary because we don't want to abort because of this, but we want
27595b482a8SLen Brown * all namespace names to be printable. A warning message is appropriate.
27695b482a8SLen Brown *
27795b482a8SLen Brown * This issue came up because there are in fact machines that exhibit
27895b482a8SLen Brown * this problem, and we want to be able to enable ACPI support for them,
27995b482a8SLen Brown * even though there are a few bad names.
28095b482a8SLen Brown */
28195b482a8SLen Brown acpi_ut_repair_name(ACPI_CAST_PTR(char, &target_name));
28295b482a8SLen Brown
28395b482a8SLen Brown /* Try to find the name in the namespace level specified by the caller */
28495b482a8SLen Brown
28595b482a8SLen Brown *return_node = ACPI_ENTRY_NOT_FOUND;
28695b482a8SLen Brown status = acpi_ns_search_one_scope(target_name, node, type, return_node);
28795b482a8SLen Brown if (status != AE_NOT_FOUND) {
28895b482a8SLen Brown /*
28995b482a8SLen Brown * If we found it AND the request specifies that a find is an error,
29095b482a8SLen Brown * return the error
29195b482a8SLen Brown */
2928f6f0361SLv Zheng if (status == AE_OK) {
2938f6f0361SLv Zheng
2948f6f0361SLv Zheng /* The node was found in the namespace */
2958f6f0361SLv Zheng
2968f6f0361SLv Zheng /*
2978f6f0361SLv Zheng * If the namespace override feature is enabled for this node,
2988ea98655SBob Moore * delete any existing attached sub-object and make the node
2998ea98655SBob Moore * look like a new node that is owned by the override table.
3008f6f0361SLv Zheng */
3018f6f0361SLv Zheng if (flags & ACPI_NS_OVERRIDE_IF_FOUND) {
3028ea98655SBob Moore ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
3038ea98655SBob Moore "Namespace override: %4.4s pass %u type %X Owner %X\n",
3048ea98655SBob Moore ACPI_CAST_PTR(char,
3058ea98655SBob Moore &target_name),
3068ea98655SBob Moore interpreter_mode,
3078ea98655SBob Moore (*return_node)->type,
3088ea98655SBob Moore walk_state->owner_id));
3098ea98655SBob Moore
3108f6f0361SLv Zheng acpi_ns_delete_children(*return_node);
3118ea98655SBob Moore if (acpi_gbl_runtime_namespace_override) {
3128ea98655SBob Moore acpi_ut_remove_reference((*return_node)->object);
3138ea98655SBob Moore (*return_node)->object = NULL;
3148ea98655SBob Moore (*return_node)->owner_id =
3158ea98655SBob Moore walk_state->owner_id;
3168ea98655SBob Moore } else {
3178f6f0361SLv Zheng acpi_ns_remove_node(*return_node);
3188f6f0361SLv Zheng *return_node = ACPI_ENTRY_NOT_FOUND;
3198f6f0361SLv Zheng }
3208ea98655SBob Moore }
3218f6f0361SLv Zheng
3228f6f0361SLv Zheng /* Return an error if we don't expect to find the object */
3238f6f0361SLv Zheng
3248f6f0361SLv Zheng else if (flags & ACPI_NS_ERROR_IF_FOUND) {
32595b482a8SLen Brown status = AE_ALREADY_EXISTS;
32695b482a8SLen Brown }
3278f6f0361SLv Zheng }
32856324c10SLv Zheng #ifdef ACPI_ASL_COMPILER
32956324c10SLv Zheng if (*return_node && (*return_node)->type == ACPI_TYPE_ANY) {
33056324c10SLv Zheng (*return_node)->flags |= ANOBJ_IS_EXTERNAL;
33156324c10SLv Zheng }
33256324c10SLv Zheng #endif
33395b482a8SLen Brown
33495b482a8SLen Brown /* Either found it or there was an error: finished either way */
33595b482a8SLen Brown
33695b482a8SLen Brown return_ACPI_STATUS(status);
33795b482a8SLen Brown }
33895b482a8SLen Brown
33995b482a8SLen Brown /*
34095b482a8SLen Brown * The name was not found. If we are NOT performing the first pass
34195b482a8SLen Brown * (name entry) of loading the namespace, search the parent tree (all the
34295b482a8SLen Brown * way to the root if necessary.) We don't want to perform the parent
34395b482a8SLen Brown * search when the namespace is actually being loaded. We want to perform
34495b482a8SLen Brown * the search when namespace references are being resolved (load pass 2)
34595b482a8SLen Brown * and during the execution phase.
34695b482a8SLen Brown */
34795b482a8SLen Brown if ((interpreter_mode != ACPI_IMODE_LOAD_PASS1) &&
34895b482a8SLen Brown (flags & ACPI_NS_SEARCH_PARENT)) {
34995b482a8SLen Brown /*
35095b482a8SLen Brown * Not found at this level - search parent tree according to the
35195b482a8SLen Brown * ACPI specification
35295b482a8SLen Brown */
35395b482a8SLen Brown status =
35495b482a8SLen Brown acpi_ns_search_parent_tree(target_name, node, type,
35595b482a8SLen Brown return_node);
35695b482a8SLen Brown if (ACPI_SUCCESS(status)) {
35795b482a8SLen Brown return_ACPI_STATUS(status);
35895b482a8SLen Brown }
35995b482a8SLen Brown }
36095b482a8SLen Brown
36195b482a8SLen Brown /* In execute mode, just search, never add names. Exit now */
36295b482a8SLen Brown
36395b482a8SLen Brown if (interpreter_mode == ACPI_IMODE_EXECUTE) {
36495b482a8SLen Brown ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
36595b482a8SLen Brown "%4.4s Not found in %p [Not adding]\n",
36695b482a8SLen Brown ACPI_CAST_PTR(char, &target_name), node));
36795b482a8SLen Brown
36895b482a8SLen Brown return_ACPI_STATUS(AE_NOT_FOUND);
36995b482a8SLen Brown }
37095b482a8SLen Brown
37195b482a8SLen Brown /* Create the new named object */
37295b482a8SLen Brown
37395b482a8SLen Brown new_node = acpi_ns_create_node(target_name);
37495b482a8SLen Brown if (!new_node) {
37595b482a8SLen Brown return_ACPI_STATUS(AE_NO_MEMORY);
37695b482a8SLen Brown }
37795b482a8SLen Brown #ifdef ACPI_ASL_COMPILER
378d4913dc6SBob Moore
379d4913dc6SBob Moore /* Node is an object defined by an External() statement */
380d4913dc6SBob Moore
38199567bc5SLv Zheng if (flags & ACPI_NS_EXTERNAL ||
38299567bc5SLv Zheng (walk_state && walk_state->opcode == AML_SCOPE_OP)) {
38395b482a8SLen Brown new_node->flags |= ANOBJ_IS_EXTERNAL;
38495b482a8SLen Brown }
38595b482a8SLen Brown #endif
38695b482a8SLen Brown
38795b482a8SLen Brown if (flags & ACPI_NS_TEMPORARY) {
38895b482a8SLen Brown new_node->flags |= ANOBJ_TEMPORARY;
38995b482a8SLen Brown }
39095b482a8SLen Brown
39195b482a8SLen Brown /* Install the new object into the parent's list of children */
39295b482a8SLen Brown
39395b482a8SLen Brown acpi_ns_install_node(walk_state, node, new_node, type);
39495b482a8SLen Brown *return_node = new_node;
39595b482a8SLen Brown return_ACPI_STATUS(AE_OK);
39695b482a8SLen Brown }
397