acpi/acpica/nssearch.c

0001 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0
0002 /*******************************************************************************
0003  *
0004  * Module Name: nssearch - Namespace search
0005  *
0006  ******************************************************************************/
0007
0008 #include <acpi/acpi.h>
0009 #include "accommon.h"
0010 #include "acnamesp.h"
0011
0012 #ifdef ACPI_ASL_COMPILER
0013 #include "amlcode.h"
0014 #endif
0015
0016 #define _COMPONENT          ACPI_NAMESPACE
0017 ACPI_MODULE_NAME("nssearch")
0018
0019 /* Local prototypes */
0020 static acpi_status
0021 acpi_ns_search_parent_tree(u32 target_name,
0022                struct acpi_namespace_node *node,
0023                acpi_object_type type,
0024                struct acpi_namespace_node **return_node);
0025
0026 /*******************************************************************************
0027  *
0028  * FUNCTION:    acpi_ns_search_one_scope
0029  *
0030  * PARAMETERS:  target_name     - Ascii ACPI name to search for
0031  *              parent_node     - Starting node where search will begin
0032  *              type            - Object type to match
0033  *              return_node     - Where the matched Named obj is returned
0034  *
0035  * RETURN:      Status
0036  *
0037  * DESCRIPTION: Search a single level of the namespace. Performs a
0038  *              simple search of the specified level, and does not add
0039  *              entries or search parents.
0040  *
0041  *
0042  *      Named object lists are built (and subsequently dumped) in the
0043  *      order in which the names are encountered during the namespace load;
0044  *
0045  *      All namespace searching is linear in this implementation, but
0046  *      could be easily modified to support any improved search
0047  *      algorithm. However, the linear search was chosen for simplicity
0048  *      and because the trees are small and the other interpreter
0049  *      execution overhead is relatively high.
0050  *
0051  *      Note: CPU execution analysis has shown that the AML interpreter spends
0052  *      a very small percentage of its time searching the namespace. Therefore,
0053  *      the linear search seems to be sufficient, as there would seem to be
0054  *      little value in improving the search.
0055  *
0056  ******************************************************************************/
0057
0058 acpi_status
0059 acpi_ns_search_one_scope(u32 target_name,
0060              struct acpi_namespace_node *parent_node,
0061              acpi_object_type type,
0062              struct acpi_namespace_node **return_node)
0063 {
0064     struct acpi_namespace_node *node;
0065
0066     ACPI_FUNCTION_TRACE(ns_search_one_scope);
0067
0068 #ifdef ACPI_DEBUG_OUTPUT
0069     if (ACPI_LV_NAMES & acpi_dbg_level) {
0070         char *scope_name;
0071
0072         scope_name = acpi_ns_get_normalized_pathname(parent_node, TRUE);
0073         if (scope_name) {
0074             ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0075                       "Searching %s (%p) For [%4.4s] (%s)\n",
0076                       scope_name, parent_node,
0077                       ACPI_CAST_PTR(char, &target_name),
0078                       acpi_ut_get_type_name(type)));
0079
0080             ACPI_FREE(scope_name);
0081         }
0082     }
0083 #endif
0084
0085     /*
0086      * Search for name at this namespace level, which is to say that we
0087      * must search for the name among the children of this object
0088      */
0089     node = parent_node->child;
0090     while (node) {
0091
0092         /* Check for match against the name */
0093
0094         if (node->name.integer == target_name) {
0095
0096             /* Resolve a control method alias if any */
0097
0098             if (acpi_ns_get_type(node) ==
0099                 ACPI_TYPE_LOCAL_METHOD_ALIAS) {
0100                 node =
0101                     ACPI_CAST_PTR(struct acpi_namespace_node,
0102                           node->object);
0103             }
0104
0105             /* Found matching entry */
0106
0107             ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0108                       "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n",
0109                       ACPI_CAST_PTR(char, &target_name),
0110                       acpi_ut_get_type_name(node->type),
0111                       node,
0112                       acpi_ut_get_node_name(parent_node),
0113                       parent_node));
0114
0115             *return_node = node;
0116             return_ACPI_STATUS(AE_OK);
0117         }
0118
0119         /* Didn't match name, move on to the next peer object */
0120
0121         node = node->peer;
0122     }
0123
0124     /* Searched entire namespace level, not found */
0125
0126     ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0127               "Name [%4.4s] (%s) not found in search in scope [%4.4s] "
0128               "%p first child %p\n",
0129               ACPI_CAST_PTR(char, &target_name),
0130               acpi_ut_get_type_name(type),
0131               acpi_ut_get_node_name(parent_node), parent_node,
0132               parent_node->child));
0133
0134     return_ACPI_STATUS(AE_NOT_FOUND);
0135 }
0136
0137 /*******************************************************************************
0138  *
0139  * FUNCTION:    acpi_ns_search_parent_tree
0140  *
0141  * PARAMETERS:  target_name     - Ascii ACPI name to search for
0142  *              node            - Starting node where search will begin
0143  *              type            - Object type to match
0144  *              return_node     - Where the matched Node is returned
0145  *
0146  * RETURN:      Status
0147  *
0148  * DESCRIPTION: Called when a name has not been found in the current namespace
0149  *              level. Before adding it or giving up, ACPI scope rules require
0150  *              searching enclosing scopes in cases identified by acpi_ns_local().
0151  *
0152  *              "A name is located by finding the matching name in the current
0153  *              name space, and then in the parent name space. If the parent
0154  *              name space does not contain the name, the search continues
0155  *              recursively until either the name is found or the name space
0156  *              does not have a parent (the root of the name space). This
0157  *              indicates that the name is not found" (From ACPI Specification,
0158  *              section 5.3)
0159  *
0160  ******************************************************************************/
0161
0162 static acpi_status
0163 acpi_ns_search_parent_tree(u32 target_name,
0164                struct acpi_namespace_node *node,
0165                acpi_object_type type,
0166                struct acpi_namespace_node **return_node)
0167 {
0168     acpi_status status;
0169     struct acpi_namespace_node *parent_node;
0170
0171     ACPI_FUNCTION_TRACE(ns_search_parent_tree);
0172
0173     parent_node = node->parent;
0174
0175     /*
0176      * If there is no parent (i.e., we are at the root) or type is "local",
0177      * we won't be searching the parent tree.
0178      */
0179     if (!parent_node) {
0180         ACPI_DEBUG_PRINT((ACPI_DB_NAMES, "[%4.4s] has no parent\n",
0181                   ACPI_CAST_PTR(char, &target_name)));
0182         return_ACPI_STATUS(AE_NOT_FOUND);
0183     }
0184
0185     if (acpi_ns_local(type)) {
0186         ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0187                   "[%4.4s] type [%s] must be local to this scope (no parent search)\n",
0188                   ACPI_CAST_PTR(char, &target_name),
0189                   acpi_ut_get_type_name(type)));
0190         return_ACPI_STATUS(AE_NOT_FOUND);
0191     }
0192
0193     /* Search the parent tree */
0194
0195     ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0196               "Searching parent [%4.4s] for [%4.4s]\n",
0197               acpi_ut_get_node_name(parent_node),
0198               ACPI_CAST_PTR(char, &target_name)));
0199
0200     /* Search parents until target is found or we have backed up to the root */
0201
0202     while (parent_node) {
0203         /*
0204          * Search parent scope. Use TYPE_ANY because we don't care about the
0205          * object type at this point, we only care about the existence of
0206          * the actual name we are searching for. Typechecking comes later.
0207          */
0208         status =
0209             acpi_ns_search_one_scope(target_name, parent_node,
0210                          ACPI_TYPE_ANY, return_node);
0211         if (ACPI_SUCCESS(status)) {
0212             return_ACPI_STATUS(status);
0213         }
0214
0215         /* Not found here, go up another level (until we reach the root) */
0216
0217         parent_node = parent_node->parent;
0218     }
0219
0220     /* Not found in parent tree */
0221
0222     return_ACPI_STATUS(AE_NOT_FOUND);
0223 }
0224
0225 /*******************************************************************************
0226  *
0227  * FUNCTION:    acpi_ns_search_and_enter
0228  *
0229  * PARAMETERS:  target_name         - Ascii ACPI name to search for (4 chars)
0230  *              walk_state          - Current state of the walk
0231  *              node                - Starting node where search will begin
0232  *              interpreter_mode    - Add names only in ACPI_MODE_LOAD_PASS_x.
0233  *                                    Otherwise,search only.
0234  *              type                - Object type to match
0235  *              flags               - Flags describing the search restrictions
0236  *              return_node         - Where the Node is returned
0237  *
0238  * RETURN:      Status
0239  *
0240  * DESCRIPTION: Search for a name segment in a single namespace level,
0241  *              optionally adding it if it is not found. If the passed
0242  *              Type is not Any and the type previously stored in the
0243  *              entry was Any (i.e. unknown), update the stored type.
0244  *
0245  *              In ACPI_IMODE_EXECUTE, search only.
0246  *              In other modes, search and add if not found.
0247  *
0248  ******************************************************************************/
0249
0250 acpi_status
0251 acpi_ns_search_and_enter(u32 target_name,
0252              struct acpi_walk_state *walk_state,
0253              struct acpi_namespace_node *node,
0254              acpi_interpreter_mode interpreter_mode,
0255              acpi_object_type type,
0256              u32 flags, struct acpi_namespace_node **return_node)
0257 {
0258     acpi_status status;
0259     struct acpi_namespace_node *new_node;
0260
0261     ACPI_FUNCTION_TRACE(ns_search_and_enter);
0262
0263     /* Parameter validation */
0264
0265     if (!node || !target_name || !return_node) {
0266         ACPI_ERROR((AE_INFO,
0267                 "Null parameter: Node %p Name 0x%X ReturnNode %p",
0268                 node, target_name, return_node));
0269         return_ACPI_STATUS(AE_BAD_PARAMETER);
0270     }
0271
0272     /*
0273      * Name must consist of valid ACPI characters. We will repair the name if
0274      * necessary because we don't want to abort because of this, but we want
0275      * all namespace names to be printable. A warning message is appropriate.
0276      *
0277      * This issue came up because there are in fact machines that exhibit
0278      * this problem, and we want to be able to enable ACPI support for them,
0279      * even though there are a few bad names.
0280      */
0281     acpi_ut_repair_name(ACPI_CAST_PTR(char, &target_name));
0282
0283     /* Try to find the name in the namespace level specified by the caller */
0284
0285     *return_node = ACPI_ENTRY_NOT_FOUND;
0286     status = acpi_ns_search_one_scope(target_name, node, type, return_node);
0287     if (status != AE_NOT_FOUND) {
0288         /*
0289          * If we found it AND the request specifies that a find is an error,
0290          * return the error
0291          */
0292         if (status == AE_OK) {
0293
0294             /* The node was found in the namespace */
0295
0296             /*
0297              * If the namespace override feature is enabled for this node,
0298              * delete any existing attached sub-object and make the node
0299              * look like a new node that is owned by the override table.
0300              */
0301             if (flags & ACPI_NS_OVERRIDE_IF_FOUND) {
0302                 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0303                           "Namespace override: %4.4s pass %u type %X Owner %X\n",
0304                           ACPI_CAST_PTR(char,
0305                                 &target_name),
0306                           interpreter_mode,
0307                           (*return_node)->type,
0308                           walk_state->owner_id));
0309
0310                 acpi_ns_delete_children(*return_node);
0311                 if (acpi_gbl_runtime_namespace_override) {
0312                     acpi_ut_remove_reference((*return_node)->object);
0313                     (*return_node)->object = NULL;
0314                     (*return_node)->owner_id =
0315                         walk_state->owner_id;
0316                 } else {
0317                     acpi_ns_remove_node(*return_node);
0318                     *return_node = ACPI_ENTRY_NOT_FOUND;
0319                 }
0320             }
0321
0322             /* Return an error if we don't expect to find the object */
0323
0324             else if (flags & ACPI_NS_ERROR_IF_FOUND) {
0325                 status = AE_ALREADY_EXISTS;
0326             }
0327         }
0328 #ifdef ACPI_ASL_COMPILER
0329         if (*return_node && (*return_node)->type == ACPI_TYPE_ANY) {
0330             (*return_node)->flags |= ANOBJ_IS_EXTERNAL;
0331         }
0332 #endif
0333
0334         /* Either found it or there was an error: finished either way */
0335
0336         return_ACPI_STATUS(status);
0337     }
0338
0339     /*
0340      * The name was not found. If we are NOT performing the first pass
0341      * (name entry) of loading the namespace, search the parent tree (all the
0342      * way to the root if necessary.) We don't want to perform the parent
0343      * search when the namespace is actually being loaded. We want to perform
0344      * the search when namespace references are being resolved (load pass 2)
0345      * and during the execution phase.
0346      */
0347     if ((interpreter_mode != ACPI_IMODE_LOAD_PASS1) &&
0348         (flags & ACPI_NS_SEARCH_PARENT)) {
0349         /*
0350          * Not found at this level - search parent tree according to the
0351          * ACPI specification
0352          */
0353         status =
0354             acpi_ns_search_parent_tree(target_name, node, type,
0355                            return_node);
0356         if (ACPI_SUCCESS(status)) {
0357             return_ACPI_STATUS(status);
0358         }
0359     }
0360
0361     /* In execute mode, just search, never add names. Exit now */
0362
0363     if (interpreter_mode == ACPI_IMODE_EXECUTE) {
0364         ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0365                   "%4.4s Not found in %p [Not adding]\n",
0366                   ACPI_CAST_PTR(char, &target_name), node));
0367
0368         return_ACPI_STATUS(AE_NOT_FOUND);
0369     }
0370
0371     /* Create the new named object */
0372
0373     new_node = acpi_ns_create_node(target_name);
0374     if (!new_node) {
0375         return_ACPI_STATUS(AE_NO_MEMORY);
0376     }
0377 #ifdef ACPI_ASL_COMPILER
0378
0379     /* Node is an object defined by an External() statement */
0380
0381     if (flags & ACPI_NS_EXTERNAL ||
0382         (walk_state && walk_state->opcode == AML_SCOPE_OP)) {
0383         new_node->flags |= ANOBJ_IS_EXTERNAL;
0384     }
0385 #endif
0386
0387     if (flags & ACPI_NS_TEMPORARY) {
0388         new_node->flags |= ANOBJ_TEMPORARY;
0389     }
0390
0391     /* Install the new object into the parent's list of children */
0392
0393     acpi_ns_install_node(walk_state, node, new_node, type);
0394     *return_node = new_node;
0395     return_ACPI_STATUS(AE_OK);
0396 }