sys/contrib/dev/acpica/source/components/namespace/nssearch.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nssearch - Namespace search
   4  *
   5  ******************************************************************************/
   6
   7 /*
   8  * Copyright (C) 2000 - 2014, Intel Corp.
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions, and the following disclaimer,
  16  *    without modification.
  17  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
  18  *    substantially similar to the "NO WARRANTY" disclaimer below
  19  *    ("Disclaimer") and any redistribution must be conditioned upon
  20  *    including a substantially similar Disclaimer requirement for further
  21  *    binary redistribution.
  22  * 3. Neither the names of the above-listed copyright holders nor the names
  23  *    of any contributors may be used to endorse or promote products derived
  24  *    from this software without specific prior written permission.
  25  *
  26  * Alternatively, this software may be distributed under the terms of the
  27  * GNU General Public License ("GPL") version 2 as published by the Free
  28  * Software Foundation.
  29  *
  30  * NO WARRANTY
  31  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  32  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  33  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
  34  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  35  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  36  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  37  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  38  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  39  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  40  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  41  * POSSIBILITY OF SUCH DAMAGES.
  42  */
  43
  44 #define __NSSEARCH_C__
  45
  46 #include "acpi.h"
  47 #include "accommon.h"
  48 #include "acnamesp.h"
  49
  50 #ifdef ACPI_ASL_COMPILER
  51 #include "amlcode.h"
  52 #endif
  53
  54 #define _COMPONENT          ACPI_NAMESPACE
  55         ACPI_MODULE_NAME    ("nssearch")
  56
  57 /* Local prototypes */
  58
  59 static ACPI_STATUS
  60 AcpiNsSearchParentTree (
  61     UINT32                  TargetName,
  62     ACPI_NAMESPACE_NODE     *Node,
  63     ACPI_OBJECT_TYPE        Type,
  64     ACPI_NAMESPACE_NODE     **ReturnNode);
  65
  66
  67 /*******************************************************************************
  68  *
  69  * FUNCTION:    AcpiNsSearchOneScope
  70  *
  71  * PARAMETERS:  TargetName      - Ascii ACPI name to search for
  72  *              ParentNode      - Starting node where search will begin
  73  *              Type            - Object type to match
  74  *              ReturnNode      - Where the matched Named obj is returned
  75  *
  76  * RETURN:      Status
  77  *
  78  * DESCRIPTION: Search a single level of the namespace. Performs a
  79  *              simple search of the specified level, and does not add
  80  *              entries or search parents.
  81  *
  82  *
  83  *      Named object lists are built (and subsequently dumped) in the
  84  *      order in which the names are encountered during the namespace load;
  85  *
  86  *      All namespace searching is linear in this implementation, but
  87  *      could be easily modified to support any improved search
  88  *      algorithm. However, the linear search was chosen for simplicity
  89  *      and because the trees are small and the other interpreter
  90  *      execution overhead is relatively high.
  91  *
  92  *      Note: CPU execution analysis has shown that the AML interpreter spends
  93  *      a very small percentage of its time searching the namespace. Therefore,
  94  *      the linear search seems to be sufficient, as there would seem to be
  95  *      little value in improving the search.
  96  *
  97  ******************************************************************************/
  98
  99 ACPI_STATUS
 100 AcpiNsSearchOneScope (
 101     UINT32                  TargetName,
 102     ACPI_NAMESPACE_NODE     *ParentNode,
 103     ACPI_OBJECT_TYPE        Type,
 104     ACPI_NAMESPACE_NODE     **ReturnNode)
 105 {
 106     ACPI_NAMESPACE_NODE     *Node;
 107
 108
 109     ACPI_FUNCTION_TRACE (NsSearchOneScope);
 110
 111
 112 #ifdef ACPI_DEBUG_OUTPUT
 113     if (ACPI_LV_NAMES & AcpiDbgLevel)
 114     {
 115         char                *ScopeName;
 116
 117         ScopeName = AcpiNsGetExternalPathname (ParentNode);
 118         if (ScopeName)
 119         {
 120             ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 121                 "Searching %s (%p) For [%4.4s] (%s)\n",
 122                 ScopeName, ParentNode, ACPI_CAST_PTR (char, &TargetName),
 123                 AcpiUtGetTypeName (Type)));
 124
 125             ACPI_FREE (ScopeName);
 126         }
 127     }
 128 #endif
 129
 130     /*
 131      * Search for name at this namespace level, which is to say that we
 132      * must search for the name among the children of this object
 133      */
 134     Node = ParentNode->Child;
 135     while (Node)
 136     {
 137         /* Check for match against the name */
 138
 139         if (Node->Name.Integer == TargetName)
 140         {
 141             /* Resolve a control method alias if any */
 142
 143             if (AcpiNsGetType (Node) == ACPI_TYPE_LOCAL_METHOD_ALIAS)
 144             {
 145                 Node = ACPI_CAST_PTR (ACPI_NAMESPACE_NODE, Node->Object);
 146             }
 147
 148             /* Found matching entry */
 149
 150             ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 151                 "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n",
 152                 ACPI_CAST_PTR (char, &TargetName),
 153                 AcpiUtGetTypeName (Node->Type),
 154                 Node, AcpiUtGetNodeName (ParentNode), ParentNode));
 155
 156             *ReturnNode = Node;
 157             return_ACPI_STATUS (AE_OK);
 158         }
 159
 160         /* Didn't match name, move on to the next peer object */
 161
 162         Node = Node->Peer;
 163     }
 164
 165     /* Searched entire namespace level, not found */
 166
 167     ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 168         "Name [%4.4s] (%s) not found in search in scope [%4.4s] "
 169         "%p first child %p\n",
 170         ACPI_CAST_PTR (char, &TargetName), AcpiUtGetTypeName (Type),
 171         AcpiUtGetNodeName (ParentNode), ParentNode, ParentNode->Child));
 172
 173     return_ACPI_STATUS (AE_NOT_FOUND);
 174 }
 175
 176
 177 /*******************************************************************************
 178  *
 179  * FUNCTION:    AcpiNsSearchParentTree
 180  *
 181  * PARAMETERS:  TargetName      - Ascii ACPI name to search for
 182  *              Node            - Starting node where search will begin
 183  *              Type            - Object type to match
 184  *              ReturnNode      - Where the matched Node is returned
 185  *
 186  * RETURN:      Status
 187  *
 188  * DESCRIPTION: Called when a name has not been found in the current namespace
 189  *              level. Before adding it or giving up, ACPI scope rules require
 190  *              searching enclosing scopes in cases identified by AcpiNsLocal().
 191  *
 192  *              "A name is located by finding the matching name in the current
 193  *              name space, and then in the parent name space. If the parent
 194  *              name space does not contain the name, the search continues
 195  *              recursively until either the name is found or the name space
 196  *              does not have a parent (the root of the name space). This
 197  *              indicates that the name is not found" (From ACPI Specification,
 198  *              section 5.3)
 199  *
 200  ******************************************************************************/
 201
 202 static ACPI_STATUS
 203 AcpiNsSearchParentTree (
 204     UINT32                  TargetName,
 205     ACPI_NAMESPACE_NODE     *Node,
 206     ACPI_OBJECT_TYPE        Type,
 207     ACPI_NAMESPACE_NODE     **ReturnNode)
 208 {
 209     ACPI_STATUS             Status;
 210     ACPI_NAMESPACE_NODE     *ParentNode;
 211
 212
 213     ACPI_FUNCTION_TRACE (NsSearchParentTree);
 214
 215
 216     ParentNode = Node->Parent;
 217
 218     /*
 219      * If there is no parent (i.e., we are at the root) or type is "local",
 220      * we won't be searching the parent tree.
 221      */
 222     if (!ParentNode)
 223     {
 224         ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "[%4.4s] has no parent\n",
 225             ACPI_CAST_PTR (char, &TargetName)));
 226         return_ACPI_STATUS (AE_NOT_FOUND);
 227     }
 228
 229     if (AcpiNsLocal (Type))
 230     {
 231         ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 232             "[%4.4s] type [%s] must be local to this scope (no parent search)\n",
 233             ACPI_CAST_PTR (char, &TargetName), AcpiUtGetTypeName (Type)));
 234         return_ACPI_STATUS (AE_NOT_FOUND);
 235     }
 236
 237     /* Search the parent tree */
 238
 239     ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 240         "Searching parent [%4.4s] for [%4.4s]\n",
 241         AcpiUtGetNodeName (ParentNode), ACPI_CAST_PTR (char, &TargetName)));
 242
 243     /* Search parents until target is found or we have backed up to the root */
 244
 245     while (ParentNode)
 246     {
 247         /*
 248          * Search parent scope. Use TYPE_ANY because we don't care about the
 249          * object type at this point, we only care about the existence of
 250          * the actual name we are searching for. Typechecking comes later.
 251          */
 252         Status = AcpiNsSearchOneScope (
 253                     TargetName, ParentNode, ACPI_TYPE_ANY, ReturnNode);
 254         if (ACPI_SUCCESS (Status))
 255         {
 256             return_ACPI_STATUS (Status);
 257         }
 258
 259         /* Not found here, go up another level (until we reach the root) */
 260
 261         ParentNode = ParentNode->Parent;
 262     }
 263
 264     /* Not found in parent tree */
 265
 266     return_ACPI_STATUS (AE_NOT_FOUND);
 267 }
 268
 269
 270 /*******************************************************************************
 271  *
 272  * FUNCTION:    AcpiNsSearchAndEnter
 273  *
 274  * PARAMETERS:  TargetName          - Ascii ACPI name to search for (4 chars)
 275  *              WalkState           - Current state of the walk
 276  *              Node                - Starting node where search will begin
 277  *              InterpreterMode     - Add names only in ACPI_MODE_LOAD_PASS_x.
 278  *                                    Otherwise,search only.
 279  *              Type                - Object type to match
 280  *              Flags               - Flags describing the search restrictions
 281  *              ReturnNode          - Where the Node is returned
 282  *
 283  * RETURN:      Status
 284  *
 285  * DESCRIPTION: Search for a name segment in a single namespace level,
 286  *              optionally adding it if it is not found. If the passed
 287  *              Type is not Any and the type previously stored in the
 288  *              entry was Any (i.e. unknown), update the stored type.
 289  *
 290  *              In ACPI_IMODE_EXECUTE, search only.
 291  *              In other modes, search and add if not found.
 292  *
 293  ******************************************************************************/
 294
 295 ACPI_STATUS
 296 AcpiNsSearchAndEnter (
 297     UINT32                  TargetName,
 298     ACPI_WALK_STATE         *WalkState,
 299     ACPI_NAMESPACE_NODE     *Node,
 300     ACPI_INTERPRETER_MODE   InterpreterMode,
 301     ACPI_OBJECT_TYPE        Type,
 302     UINT32                  Flags,
 303     ACPI_NAMESPACE_NODE     **ReturnNode)
 304 {
 305     ACPI_STATUS             Status;
 306     ACPI_NAMESPACE_NODE     *NewNode;
 307
 308
 309     ACPI_FUNCTION_TRACE (NsSearchAndEnter);
 310
 311
 312     /* Parameter validation */
 313
 314     if (!Node || !TargetName || !ReturnNode)
 315     {
 316         ACPI_ERROR ((AE_INFO,
 317             "Null parameter: Node %p Name 0x%X ReturnNode %p",
 318             Node, TargetName, ReturnNode));
 319         return_ACPI_STATUS (AE_BAD_PARAMETER);
 320     }
 321
 322     /*
 323      * Name must consist of valid ACPI characters. We will repair the name if
 324      * necessary because we don't want to abort because of this, but we want
 325      * all namespace names to be printable. A warning message is appropriate.
 326      *
 327      * This issue came up because there are in fact machines that exhibit
 328      * this problem, and we want to be able to enable ACPI support for them,
 329      * even though there are a few bad names.
 330      */
 331     AcpiUtRepairName (ACPI_CAST_PTR (char, &TargetName));
 332
 333     /* Try to find the name in the namespace level specified by the caller */
 334
 335     *ReturnNode = ACPI_ENTRY_NOT_FOUND;
 336     Status = AcpiNsSearchOneScope (TargetName, Node, Type, ReturnNode);
 337     if (Status != AE_NOT_FOUND)
 338     {
 339         /*
 340          * If we found it AND the request specifies that a find is an error,
 341          * return the error
 342          */
 343         if ((Status == AE_OK) &&
 344             (Flags & ACPI_NS_ERROR_IF_FOUND))
 345         {
 346             Status = AE_ALREADY_EXISTS;
 347         }
 348
 349 #ifdef ACPI_ASL_COMPILER
 350         if (*ReturnNode && (*ReturnNode)->Type == ACPI_TYPE_ANY)
 351         {
 352             (*ReturnNode)->Flags |= ANOBJ_IS_EXTERNAL;
 353         }
 354 #endif
 355
 356         /* Either found it or there was an error: finished either way */
 357
 358         return_ACPI_STATUS (Status);
 359     }
 360
 361     /*
 362      * The name was not found. If we are NOT performing the first pass
 363      * (name entry) of loading the namespace, search the parent tree (all the
 364      * way to the root if necessary.) We don't want to perform the parent
 365      * search when the namespace is actually being loaded. We want to perform
 366      * the search when namespace references are being resolved (load pass 2)
 367      * and during the execution phase.
 368      */
 369     if ((InterpreterMode != ACPI_IMODE_LOAD_PASS1) &&
 370         (Flags & ACPI_NS_SEARCH_PARENT))
 371     {
 372         /*
 373          * Not found at this level - search parent tree according to the
 374          * ACPI specification
 375          */
 376         Status = AcpiNsSearchParentTree (TargetName, Node, Type, ReturnNode);
 377         if (ACPI_SUCCESS (Status))
 378         {
 379             return_ACPI_STATUS (Status);
 380         }
 381     }
 382
 383     /* In execute mode, just search, never add names. Exit now */
 384
 385     if (InterpreterMode == ACPI_IMODE_EXECUTE)
 386     {
 387         ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 388             "%4.4s Not found in %p [Not adding]\n",
 389             ACPI_CAST_PTR (char, &TargetName), Node));
 390
 391         return_ACPI_STATUS (AE_NOT_FOUND);
 392     }
 393
 394     /* Create the new named object */
 395
 396     NewNode = AcpiNsCreateNode (TargetName);
 397     if (!NewNode)
 398     {
 399         return_ACPI_STATUS (AE_NO_MEMORY);
 400     }
 401
 402 #ifdef ACPI_ASL_COMPILER
 403
 404     /* Node is an object defined by an External() statement */
 405
 406     if (Flags & ACPI_NS_EXTERNAL ||
 407         (WalkState && WalkState->Opcode == AML_SCOPE_OP))
 408     {
 409         NewNode->Flags |= ANOBJ_IS_EXTERNAL;
 410     }
 411 #endif
 412
 413     if (Flags & ACPI_NS_TEMPORARY)
 414     {
 415         NewNode->Flags |= ANOBJ_TEMPORARY;
 416     }
 417
 418     /* Install the new object into the parent's list of children */
 419
 420     AcpiNsInstallNode (WalkState, Node, NewNode, Type);
 421     *ReturnNode = NewNode;
 422     return_ACPI_STATUS (AE_OK);
 423 }