LCOV - code coverage report
Current view: top level - drivers/acpi/acpica - nssearch.c (source / functions) Hit Total Coverage
Test: combined.info Lines: 37 50 74.0 %
Date: 2022-03-28 15:32:58 Functions: 2 2 100.0 %
Branches: 22 32 68.8 %

           Branch data     Line data    Source code
       1                 :            : // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0
       2                 :            : /*******************************************************************************
       3                 :            :  *
       4                 :            :  * Module Name: nssearch - Namespace search
       5                 :            :  *
       6                 :            :  ******************************************************************************/
       7                 :            : 
       8                 :            : #include <acpi/acpi.h>
       9                 :            : #include "accommon.h"
      10                 :            : #include "acnamesp.h"
      11                 :            : 
      12                 :            : #ifdef ACPI_ASL_COMPILER
      13                 :            : #include "amlcode.h"
      14                 :            : #endif
      15                 :            : 
      16                 :            : #define _COMPONENT          ACPI_NAMESPACE
      17                 :            : ACPI_MODULE_NAME("nssearch")
      18                 :            : 
      19                 :            : /* Local prototypes */
      20                 :            : static acpi_status
      21                 :            : acpi_ns_search_parent_tree(u32 target_name,
      22                 :            :                            struct acpi_namespace_node *node,
      23                 :            :                            acpi_object_type type,
      24                 :            :                            struct acpi_namespace_node **return_node);
      25                 :            : 
      26                 :            : /*******************************************************************************
      27                 :            :  *
      28                 :            :  * FUNCTION:    acpi_ns_search_one_scope
      29                 :            :  *
      30                 :            :  * PARAMETERS:  target_name     - Ascii ACPI name to search for
      31                 :            :  *              parent_node     - Starting node where search will begin
      32                 :            :  *              type            - Object type to match
      33                 :            :  *              return_node     - Where the matched Named obj is returned
      34                 :            :  *
      35                 :            :  * RETURN:      Status
      36                 :            :  *
      37                 :            :  * DESCRIPTION: Search a single level of the namespace. Performs a
      38                 :            :  *              simple search of the specified level, and does not add
      39                 :            :  *              entries or search parents.
      40                 :            :  *
      41                 :            :  *
      42                 :            :  *      Named object lists are built (and subsequently dumped) in the
      43                 :            :  *      order in which the names are encountered during the namespace load;
      44                 :            :  *
      45                 :            :  *      All namespace searching is linear in this implementation, but
      46                 :            :  *      could be easily modified to support any improved search
      47                 :            :  *      algorithm. However, the linear search was chosen for simplicity
      48                 :            :  *      and because the trees are small and the other interpreter
      49                 :            :  *      execution overhead is relatively high.
      50                 :            :  *
      51                 :            :  *      Note: CPU execution analysis has shown that the AML interpreter spends
      52                 :            :  *      a very small percentage of its time searching the namespace. Therefore,
      53                 :            :  *      the linear search seems to be sufficient, as there would seem to be
      54                 :            :  *      little value in improving the search.
      55                 :            :  *
      56                 :            :  ******************************************************************************/
      57                 :            : 
      58                 :            : acpi_status
      59                 :     191621 : acpi_ns_search_one_scope(u32 target_name,
      60                 :            :                          struct acpi_namespace_node *parent_node,
      61                 :            :                          acpi_object_type type,
      62                 :            :                          struct acpi_namespace_node **return_node)
      63                 :            : {
      64                 :     191621 :         struct acpi_namespace_node *node;
      65                 :            : 
      66                 :     191621 :         ACPI_FUNCTION_TRACE(ns_search_one_scope);
      67                 :            : 
      68                 :            : #ifdef ACPI_DEBUG_OUTPUT
      69                 :            :         if (ACPI_LV_NAMES & acpi_dbg_level) {
      70                 :            :                 char *scope_name;
      71                 :            : 
      72                 :            :                 scope_name = acpi_ns_get_normalized_pathname(parent_node, TRUE);
      73                 :            :                 if (scope_name) {
      74                 :            :                         ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
      75                 :            :                                           "Searching %s (%p) For [%4.4s] (%s)\n",
      76                 :            :                                           scope_name, parent_node,
      77                 :            :                                           ACPI_CAST_PTR(char, &target_name),
      78                 :            :                                           acpi_ut_get_type_name(type)));
      79                 :            : 
      80                 :            :                         ACPI_FREE(scope_name);
      81                 :            :                 }
      82                 :            :         }
      83                 :            : #endif
      84                 :            : 
      85                 :            :         /*
      86                 :            :          * Search for name at this namespace level, which is to say that we
      87                 :            :          * must search for the name among the children of this object
      88                 :            :          */
      89                 :     191621 :         node = parent_node->child;
      90         [ +  + ]:    1797711 :         while (node) {
      91                 :            : 
      92                 :            :                 /* Check for match against the name */
      93                 :            : 
      94         [ +  + ]:    1656595 :                 if (node->name.integer == target_name) {
      95                 :            : 
      96                 :            :                         /* Resolve a control method alias if any */
      97                 :            : 
      98         [ -  + ]:      50505 :                         if (acpi_ns_get_type(node) ==
      99                 :            :                             ACPI_TYPE_LOCAL_METHOD_ALIAS) {
     100                 :          0 :                                 node =
     101                 :            :                                     ACPI_CAST_PTR(struct acpi_namespace_node,
     102                 :            :                                                   node->object);
     103                 :            :                         }
     104                 :            : 
     105                 :            :                         /* Found matching entry */
     106                 :            : 
     107                 :            :                         ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
     108                 :            :                                           "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n",
     109                 :            :                                           ACPI_CAST_PTR(char, &target_name),
     110                 :            :                                           acpi_ut_get_type_name(node->type),
     111                 :            :                                           node,
     112                 :            :                                           acpi_ut_get_node_name(parent_node),
     113                 :      50505 :                                           parent_node));
     114                 :            : 
     115                 :      50505 :                         *return_node = node;
     116                 :      50505 :                         return_ACPI_STATUS(AE_OK);
     117                 :            :                 }
     118                 :            : 
     119                 :            :                 /* Didn't match name, move on to the next peer object */
     120                 :            : 
     121                 :    1606090 :                 node = node->peer;
     122                 :            :         }
     123                 :            : 
     124                 :            :         /* Searched entire namespace level, not found */
     125                 :            : 
     126                 :            :         ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
     127                 :            :                           "Name [%4.4s] (%s) not found in search in scope [%4.4s] "
     128                 :            :                           "%p first child %p\n",
     129                 :            :                           ACPI_CAST_PTR(char, &target_name),
     130                 :            :                           acpi_ut_get_type_name(type),
     131                 :            :                           acpi_ut_get_node_name(parent_node), parent_node,
     132                 :            :                           parent_node->child));
     133                 :            : 
     134                 :            :         return_ACPI_STATUS(AE_NOT_FOUND);
     135                 :            : }
     136                 :            : 
     137                 :            : /*******************************************************************************
     138                 :            :  *
     139                 :            :  * FUNCTION:    acpi_ns_search_parent_tree
     140                 :            :  *
     141                 :            :  * PARAMETERS:  target_name     - Ascii ACPI name to search for
     142                 :            :  *              node            - Starting node where search will begin
     143                 :            :  *              type            - Object type to match
     144                 :            :  *              return_node     - Where the matched Node is returned
     145                 :            :  *
     146                 :            :  * RETURN:      Status
     147                 :            :  *
     148                 :            :  * DESCRIPTION: Called when a name has not been found in the current namespace
     149                 :            :  *              level. Before adding it or giving up, ACPI scope rules require
     150                 :            :  *              searching enclosing scopes in cases identified by acpi_ns_local().
     151                 :            :  *
     152                 :            :  *              "A name is located by finding the matching name in the current
     153                 :            :  *              name space, and then in the parent name space. If the parent
     154                 :            :  *              name space does not contain the name, the search continues
     155                 :            :  *              recursively until either the name is found or the name space
     156                 :            :  *              does not have a parent (the root of the name space). This
     157                 :            :  *              indicates that the name is not found" (From ACPI Specification,
     158                 :            :  *              section 5.3)
     159                 :            :  *
     160                 :            :  ******************************************************************************/
     161                 :            : 
     162                 :            : static acpi_status
     163                 :            : acpi_ns_search_parent_tree(u32 target_name,
     164                 :            :                            struct acpi_namespace_node *node,
     165                 :            :                            acpi_object_type type,
     166                 :            :                            struct acpi_namespace_node **return_node)
     167                 :            : {
     168                 :            :         acpi_status status;
     169                 :            :         struct acpi_namespace_node *parent_node;
     170                 :            : 
     171                 :            :         ACPI_FUNCTION_TRACE(ns_search_parent_tree);
     172                 :            : 
     173                 :            :         parent_node = node->parent;
     174                 :            : 
     175                 :            :         /*
     176                 :            :          * If there is no parent (i.e., we are at the root) or type is "local",
     177                 :            :          * we won't be searching the parent tree.
     178                 :            :          */
     179                 :            :         if (!parent_node) {
     180                 :            :                 ACPI_DEBUG_PRINT((ACPI_DB_NAMES, "[%4.4s] has no parent\n",
     181                 :            :                                   ACPI_CAST_PTR(char, &target_name)));
     182                 :            :                 return_ACPI_STATUS(AE_NOT_FOUND);
     183                 :            :         }
     184                 :            : 
     185                 :            :         if (acpi_ns_local(type)) {
     186                 :            :                 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
     187                 :            :                                   "[%4.4s] type [%s] must be local to this scope (no parent search)\n",
     188                 :            :                                   ACPI_CAST_PTR(char, &target_name),
     189                 :            :                                   acpi_ut_get_type_name(type)));
     190                 :            :                 return_ACPI_STATUS(AE_NOT_FOUND);
     191                 :            :         }
     192                 :            : 
     193                 :            :         /* Search the parent tree */
     194                 :            : 
     195                 :            :         ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
     196                 :            :                           "Searching parent [%4.4s] for [%4.4s]\n",
     197                 :            :                           acpi_ut_get_node_name(parent_node),
     198                 :            :                           ACPI_CAST_PTR(char, &target_name)));
     199                 :            : 
     200                 :            :         /* Search parents until target is found or we have backed up to the root */
     201                 :            : 
     202                 :            :         while (parent_node) {
     203                 :            :                 /*
     204                 :            :                  * Search parent scope. Use TYPE_ANY because we don't care about the
     205                 :            :                  * object type at this point, we only care about the existence of
     206                 :            :                  * the actual name we are searching for. Typechecking comes later.
     207                 :            :                  */
     208                 :            :                 status =
     209                 :            :                     acpi_ns_search_one_scope(target_name, parent_node,
     210                 :            :                                              ACPI_TYPE_ANY, return_node);
     211                 :            :                 if (ACPI_SUCCESS(status)) {
     212                 :            :                         return_ACPI_STATUS(status);
     213                 :            :                 }
     214                 :            : 
     215                 :            :                 /* Not found here, go up another level (until we reach the root) */
     216                 :            : 
     217                 :            :                 parent_node = parent_node->parent;
     218                 :            :         }
     219                 :            : 
     220                 :            :         /* Not found in parent tree */
     221                 :            : 
     222                 :            :         return_ACPI_STATUS(AE_NOT_FOUND);
     223                 :            : }
     224                 :            : 
     225                 :            : /*******************************************************************************
     226                 :            :  *
     227                 :            :  * FUNCTION:    acpi_ns_search_and_enter
     228                 :            :  *
     229                 :            :  * PARAMETERS:  target_name         - Ascii ACPI name to search for (4 chars)
     230                 :            :  *              walk_state          - Current state of the walk
     231                 :            :  *              node                - Starting node where search will begin
     232                 :            :  *              interpreter_mode    - Add names only in ACPI_MODE_LOAD_PASS_x.
     233                 :            :  *                                    Otherwise,search only.
     234                 :            :  *              type                - Object type to match
     235                 :            :  *              flags               - Flags describing the search restrictions
     236                 :            :  *              return_node         - Where the Node is returned
     237                 :            :  *
     238                 :            :  * RETURN:      Status
     239                 :            :  *
     240                 :            :  * DESCRIPTION: Search for a name segment in a single namespace level,
     241                 :            :  *              optionally adding it if it is not found. If the passed
     242                 :            :  *              Type is not Any and the type previously stored in the
     243                 :            :  *              entry was Any (i.e. unknown), update the stored type.
     244                 :            :  *
     245                 :            :  *              In ACPI_IMODE_EXECUTE, search only.
     246                 :            :  *              In other modes, search and add if not found.
     247                 :            :  *
     248                 :            :  ******************************************************************************/
     249                 :            : 
     250                 :            : acpi_status
     251                 :     160993 : acpi_ns_search_and_enter(u32 target_name,
     252                 :            :                          struct acpi_walk_state *walk_state,
     253                 :            :                          struct acpi_namespace_node *node,
     254                 :            :                          acpi_interpreter_mode interpreter_mode,
     255                 :            :                          acpi_object_type type,
     256                 :            :                          u32 flags, struct acpi_namespace_node **return_node)
     257                 :            : {
     258                 :     160993 :         acpi_status status;
     259                 :     160993 :         struct acpi_namespace_node *new_node;
     260                 :            : 
     261                 :     160993 :         ACPI_FUNCTION_TRACE(ns_search_and_enter);
     262                 :            : 
     263                 :            :         /* Parameter validation */
     264                 :            : 
     265   [ +  -  -  + ]:     160993 :         if (!node || !target_name || !return_node) {
     266                 :          0 :                 ACPI_ERROR((AE_INFO,
     267                 :            :                             "Null parameter: Node %p Name 0x%X ReturnNode %p",
     268                 :            :                             node, target_name, return_node));
     269                 :          0 :                 return_ACPI_STATUS(AE_BAD_PARAMETER);
     270                 :            :         }
     271                 :            : 
     272                 :            :         /*
     273                 :            :          * Name must consist of valid ACPI characters. We will repair the name if
     274                 :            :          * necessary because we don't want to abort because of this, but we want
     275                 :            :          * all namespace names to be printable. A warning message is appropriate.
     276                 :            :          *
     277                 :            :          * This issue came up because there are in fact machines that exhibit
     278                 :            :          * this problem, and we want to be able to enable ACPI support for them,
     279                 :            :          * even though there are a few bad names.
     280                 :            :          */
     281                 :     160993 :         acpi_ut_repair_name(ACPI_CAST_PTR(char, &target_name));
     282                 :            : 
     283                 :            :         /* Try to find the name in the namespace level specified by the caller */
     284                 :            : 
     285                 :     160993 :         *return_node = ACPI_ENTRY_NOT_FOUND;
     286                 :     160993 :         status = acpi_ns_search_one_scope(target_name, node, type, return_node);
     287         [ +  + ]:     160993 :         if (status != AE_NOT_FOUND) {
     288                 :            :                 /*
     289                 :            :                  * If we found it AND the request specifies that a find is an error,
     290                 :            :                  * return the error
     291                 :            :                  */
     292         [ +  - ]:      33945 :                 if (status == AE_OK) {
     293                 :            : 
     294                 :            :                         /* The node was found in the namespace */
     295                 :            : 
     296                 :            :                         /*
     297                 :            :                          * If the namespace override feature is enabled for this node,
     298                 :            :                          * delete any existing attached sub-object and make the node
     299                 :            :                          * look like a new node that is owned by the override table.
     300                 :            :                          */
     301         [ -  + ]:      33945 :                         if (flags & ACPI_NS_OVERRIDE_IF_FOUND) {
     302                 :            :                                 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
     303                 :            :                                                   "Namespace override: %4.4s pass %u type %X Owner %X\n",
     304                 :            :                                                   ACPI_CAST_PTR(char,
     305                 :            :                                                                 &target_name),
     306                 :            :                                                   interpreter_mode,
     307                 :            :                                                   (*return_node)->type,
     308                 :          0 :                                                   walk_state->owner_id));
     309                 :            : 
     310                 :          0 :                                 acpi_ns_delete_children(*return_node);
     311         [ #  # ]:          0 :                                 if (acpi_gbl_runtime_namespace_override) {
     312                 :          0 :                                         acpi_ut_remove_reference((*return_node)->object);
     313                 :          0 :                                         (*return_node)->object = NULL;
     314                 :          0 :                                         (*return_node)->owner_id =
     315                 :          0 :                                             walk_state->owner_id;
     316                 :            :                                 } else {
     317                 :          0 :                                         acpi_ns_remove_node(*return_node);
     318                 :          0 :                                         *return_node = ACPI_ENTRY_NOT_FOUND;
     319                 :            :                                 }
     320                 :            :                         }
     321                 :            : 
     322                 :            :                         /* Return an error if we don't expect to find the object */
     323                 :            : 
     324         [ -  + ]:      33945 :                         else if (flags & ACPI_NS_ERROR_IF_FOUND) {
     325                 :          0 :                                 status = AE_ALREADY_EXISTS;
     326                 :            :                         }
     327                 :            :                 }
     328                 :            : #ifdef ACPI_ASL_COMPILER
     329                 :            :                 if (*return_node && (*return_node)->type == ACPI_TYPE_ANY) {
     330                 :            :                         (*return_node)->flags |= ANOBJ_IS_EXTERNAL;
     331                 :            :                 }
     332                 :            : #endif
     333                 :            : 
     334                 :            :                 /* Either found it or there was an error: finished either way */
     335                 :            : 
     336                 :      33945 :                 return_ACPI_STATUS(status);
     337                 :            :         }
     338                 :            : 
     339                 :            :         /*
     340                 :            :          * The name was not found. If we are NOT performing the first pass
     341                 :            :          * (name entry) of loading the namespace, search the parent tree (all the
     342                 :            :          * way to the root if necessary.) We don't want to perform the parent
     343                 :            :          * search when the namespace is actually being loaded. We want to perform
     344                 :            :          * the search when namespace references are being resolved (load pass 2)
     345                 :            :          * and during the execution phase.
     346                 :            :          */
     347         [ +  + ]:     127048 :         if ((interpreter_mode != ACPI_IMODE_LOAD_PASS1) &&
     348         [ +  + ]:     126180 :             (flags & ACPI_NS_SEARCH_PARENT)) {
     349                 :            :                 /*
     350                 :            :                  * Not found at this level - search parent tree according to the
     351                 :            :                  * ACPI specification
     352                 :            :                  */
     353                 :      16560 :                 status =
     354                 :      16560 :                     acpi_ns_search_parent_tree(target_name, node, type,
     355                 :            :                                                return_node);
     356         [ -  + ]:      16560 :                 if (ACPI_SUCCESS(status)) {
     357                 :            :                         return_ACPI_STATUS(status);
     358                 :            :                 }
     359                 :            :         }
     360                 :            : 
     361                 :            :         /* In execute mode, just search, never add names. Exit now */
     362                 :            : 
     363         [ +  + ]:     110488 :         if (interpreter_mode == ACPI_IMODE_EXECUTE) {
     364                 :            :                 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
     365                 :            :                                   "%4.4s Not found in %p [Not adding]\n",
     366                 :            :                                   ACPI_CAST_PTR(char, &target_name), node));
     367                 :            : 
     368                 :            :                 return_ACPI_STATUS(AE_NOT_FOUND);
     369                 :            :         }
     370                 :            : 
     371                 :            :         /* Create the new named object */
     372                 :            : 
     373                 :       8540 :         new_node = acpi_ns_create_node(target_name);
     374         [ +  - ]:       8540 :         if (!new_node) {
     375                 :            :                 return_ACPI_STATUS(AE_NO_MEMORY);
     376                 :            :         }
     377                 :            : #ifdef ACPI_ASL_COMPILER
     378                 :            : 
     379                 :            :         /* Node is an object defined by an External() statement */
     380                 :            : 
     381                 :            :         if (flags & ACPI_NS_EXTERNAL ||
     382                 :            :             (walk_state && walk_state->opcode == AML_SCOPE_OP)) {
     383                 :            :                 new_node->flags |= ANOBJ_IS_EXTERNAL;
     384                 :            :         }
     385                 :            : #endif
     386                 :            : 
     387         [ +  + ]:       8540 :         if (flags & ACPI_NS_TEMPORARY) {
     388                 :        532 :                 new_node->flags |= ANOBJ_TEMPORARY;
     389                 :            :         }
     390                 :            : 
     391                 :            :         /* Install the new object into the parent's list of children */
     392                 :            : 
     393                 :       8540 :         acpi_ns_install_node(walk_state, node, new_node, type);
     394                 :       8540 :         *return_node = new_node;
     395                 :       8540 :         return_ACPI_STATUS(AE_OK);
     396                 :            : }

Generated by: LCOV version 1.14