sys/contrib/dev/acpica/Subsystem/Namespace/nssearch.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nssearch - Namespace search
   4  *              $Revision: 61 $
   5  *
   6  ******************************************************************************/
   7
   8 /******************************************************************************
   9  *
  10  * 1. Copyright Notice
  11  *
  12  * Some or all of this work - Copyright (c) 1999, 2000, Intel Corp.
  13  * All rights reserved.
  14  *
  15  * 2. License
  16  *
  17  * 2.1. This is your license from Intel Corp. under its intellectual property
  18  * rights.  You may have additional license terms from the party that provided
  19  * you this software, covering your right to use that party's intellectual
  20  * property rights.
  21  *
  22  * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a
  23  * copy of the source code appearing in this file ("Covered Code") an
  24  * irrevocable, perpetual, worldwide license under Intel's copyrights in the
  25  * base code distributed originally by Intel ("Original Intel Code") to copy,
  26  * make derivatives, distribute, use and display any portion of the Covered
  27  * Code in any form, with the right to sublicense such rights; and
  28  *
  29  * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent
  30  * license (with the right to sublicense), under only those claims of Intel
  31  * patents that are infringed by the Original Intel Code, to make, use, sell,
  32  * offer to sell, and import the Covered Code and derivative works thereof
  33  * solely to the minimum extent necessary to exercise the above copyright
  34  * license, and in no event shall the patent license extend to any additions
  35  * to or modifications of the Original Intel Code.  No other license or right
  36  * is granted directly or by implication, estoppel or otherwise;
  37  *
  38  * The above copyright and patent license is granted only if the following
  39  * conditions are met:
  40  *
  41  * 3. Conditions
  42  *
  43  * 3.1. Redistribution of Source with Rights to Further Distribute Source.
  44  * Redistribution of source code of any substantial portion of the Covered
  45  * Code or modification with rights to further distribute source must include
  46  * the above Copyright Notice, the above License, this list of Conditions,
  47  * and the following Disclaimer and Export Compliance provision.  In addition,
  48  * Licensee must cause all Covered Code to which Licensee contributes to
  49  * contain a file documenting the changes Licensee made to create that Covered
  50  * Code and the date of any change.  Licensee must include in that file the
  51  * documentation of any changes made by any predecessor Licensee.  Licensee
  52  * must include a prominent statement that the modification is derived,
  53  * directly or indirectly, from Original Intel Code.
  54  *
  55  * 3.2. Redistribution of Source with no Rights to Further Distribute Source.
  56  * Redistribution of source code of any substantial portion of the Covered
  57  * Code or modification without rights to further distribute source must
  58  * include the following Disclaimer and Export Compliance provision in the
  59  * documentation and/or other materials provided with distribution.  In
  60  * addition, Licensee may not authorize further sublicense of source of any
  61  * portion of the Covered Code, and must include terms to the effect that the
  62  * license from Licensee to its licensee is limited to the intellectual
  63  * property embodied in the software Licensee provides to its licensee, and
  64  * not to intellectual property embodied in modifications its licensee may
  65  * make.
  66  *
  67  * 3.3. Redistribution of Executable. Redistribution in executable form of any
  68  * substantial portion of the Covered Code or modification must reproduce the
  69  * above Copyright Notice, and the following Disclaimer and Export Compliance
  70  * provision in the documentation and/or other materials provided with the
  71  * distribution.
  72  *
  73  * 3.4. Intel retains all right, title, and interest in and to the Original
  74  * Intel Code.
  75  *
  76  * 3.5. Neither the name Intel nor any other trademark owned or controlled by
  77  * Intel shall be used in advertising or otherwise to promote the sale, use or
  78  * other dealings in products derived from or relating to the Covered Code
  79  * without prior written authorization from Intel.
  80  *
  81  * 4. Disclaimer and Export Compliance
  82  *
  83  * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED
  84  * HERE.  ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE
  85  * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT,  ASSISTANCE,
  86  * INSTALLATION, TRAINING OR OTHER SERVICES.  INTEL WILL NOT PROVIDE ANY
  87  * UPDATES, ENHANCEMENTS OR EXTENSIONS.  INTEL SPECIFICALLY DISCLAIMS ANY
  88  * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A
  89  * PARTICULAR PURPOSE.
  90  *
  91  * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES
  92  * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR
  93  * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT,
  94  * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY
  95  * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL
  96  * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES.  THESE LIMITATIONS
  97  * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY
  98  * LIMITED REMEDY.
  99  *
 100  * 4.3. Licensee shall not export, either directly or indirectly, any of this
 101  * software or system incorporating such software without first obtaining any
 102  * required license or other approval from the U. S. Department of Commerce or
 103  * any other agency or department of the United States Government.  In the
 104  * event Licensee exports any such software from the United States or
 105  * re-exports any such software from a foreign destination, Licensee shall
 106  * ensure that the distribution and export/re-export of the software is in
 107  * compliance with all laws, regulations, orders, or other restrictions of the
 108  * U.S. Export Administration Regulations. Licensee agrees that neither it nor
 109  * any of its subsidiaries will export/re-export any technical data, process,
 110  * software, or service, directly or indirectly, to any country for which the
 111  * United States government or any agency thereof requires an export license,
 112  * other governmental approval, or letter of assurance, without first obtaining
 113  * such license, approval or letter.
 114  *
 115  *****************************************************************************/
 116
 117 #define __NSSEARCH_C__
 118
 119 #include "acpi.h"
 120 #include "amlcode.h"
 121 #include "acinterp.h"
 122 #include "acnamesp.h"
 123
 124
 125 #define _COMPONENT          NAMESPACE
 126         MODULE_NAME         ("nssearch")
 127
 128
 129 /*******************************************************************************
 130  *
 131  * FUNCTION:    AcpiNsSearchNode
 132  *
 133  * PARAMETERS:  *TargetName         - Ascii ACPI name to search for
 134  *              *Node           - Starting table where search will begin
 135  *              Type                - Object type to match
 136  *              **ReturnNode    - Where the matched Named obj is returned
 137  *
 138  * RETURN:      Status
 139  *
 140  * DESCRIPTION: Search a single namespace table.  Performs a simple search,
 141  *              does not add entries or search parents.
 142  *
 143  *
 144  *      Named object lists are built (and subsequently dumped) in the
 145  *      order in which the names are encountered during the namespace load;
 146  *
 147  *      All namespace searching is linear in this implementation, but
 148  *      could be easily modified to support any improved search
 149  *      algorithm.  However, the linear search was chosen for simplicity
 150  *      and because the trees are small and the other interpreter
 151  *      execution overhead is relatively high.
 152  *
 153  ******************************************************************************/
 154
 155 ACPI_STATUS
 156 AcpiNsSearchNode (
 157     UINT32                  TargetName,
 158     ACPI_NAMESPACE_NODE     *Node,
 159     OBJECT_TYPE_INTERNAL    Type,
 160     ACPI_NAMESPACE_NODE     **ReturnNode)
 161 {
 162     ACPI_NAMESPACE_NODE     *NextNode;
 163
 164
 165     FUNCTION_TRACE ("NsSearchNode");
 166
 167     {
 168         DEBUG_EXEC (NATIVE_CHAR *ScopeName = AcpiNsGetTablePathname (Node));
 169         DEBUG_PRINT (TRACE_NAMES,
 170             ("NsSearchNode: Searching %s [%p]\n",
 171             ScopeName, Node));
 172         DEBUG_PRINT (TRACE_NAMES,
 173             ("NsSearchNode: For %4.4s (type %X)\n",
 174             &TargetName, Type));
 175         DEBUG_EXEC (AcpiCmFree (ScopeName));
 176     }
 177
 178
 179     /*
 180      * Search for name in this table, which is to say that we must search
 181      * for the name among the children of this object
 182      */
 183
 184     NextNode = Node->Child;
 185     while (NextNode)
 186     {
 187         /* Check for match against the name */
 188
 189         if (NextNode->Name == TargetName)
 190         {
 191             /*
 192              * Found matching entry.  Capture type if
 193              * appropriate before returning the entry.
 194              */
 195
 196             /*
 197              * The DefFieldDefn and BankFieldDefn cases
 198              * are actually looking up the Region in which
 199              * the field will be defined
 200              */
 201
 202             if ((INTERNAL_TYPE_DEF_FIELD_DEFN == Type) ||
 203                 (INTERNAL_TYPE_BANK_FIELD_DEFN == Type))
 204             {
 205                 Type = ACPI_TYPE_REGION;
 206             }
 207
 208             /*
 209              * Scope, DefAny, and IndexFieldDefn are bogus
 210              * "types" which do not actually have anything
 211              * to do with the type of the name being looked
 212              * up.  For any other value of Type, if the type
 213              * stored in the entry is Any (i.e. unknown),
 214              * save the actual type.
 215              */
 216
 217             if (Type != INTERNAL_TYPE_SCOPE &&
 218                 Type != INTERNAL_TYPE_DEF_ANY &&
 219                 Type != INTERNAL_TYPE_INDEX_FIELD_DEFN &&
 220                 NextNode->Type == ACPI_TYPE_ANY)
 221             {
 222                 NextNode->Type = (UINT8) Type;
 223             }
 224
 225             DEBUG_PRINT (TRACE_NAMES,
 226                 ("NsSearchNode: Name %4.4s (actual type %X) found at %p\n",
 227                 &TargetName, NextNode->Type, NextNode));
 228
 229             *ReturnNode = NextNode;
 230             return_ACPI_STATUS (AE_OK);
 231         }
 232
 233
 234         /*
 235          * The last entry in the list points back to the parent,
 236          * so a flag is used to indicate the end-of-list
 237          */
 238         if (NextNode->Flags & ANOBJ_END_OF_PEER_LIST)
 239         {
 240             /* Searched entire list, we are done */
 241
 242             break;
 243         }
 244
 245         /* Didn't match name, move on to the next peer object */
 246
 247         NextNode = NextNode->Peer;
 248     }
 249
 250
 251     /* Searched entire table, not found */
 252
 253     DEBUG_PRINT (TRACE_NAMES,
 254         ("NsSearchNode: Name %4.4s (type %X) not found at %p\n",
 255         &TargetName, Type, NextNode));
 256
 257
 258     return_ACPI_STATUS (AE_NOT_FOUND);
 259 }
 260
 261
 262 /*******************************************************************************
 263  *
 264  * FUNCTION:    AcpiNsSearchParentTree
 265  *
 266  * PARAMETERS:  *TargetName         - Ascii ACPI name to search for
 267  *              *Node           - Starting table where search will begin
 268  *              Type                - Object type to match
 269  *              **ReturnNode    - Where the matched Named Obj is returned
 270  *
 271  * RETURN:      Status
 272  *
 273  * DESCRIPTION: Called when a name has not been found in the current namespace
 274  *              table.  Before adding it or giving up, ACPI scope rules require
 275  *              searching enclosing scopes in cases identified by AcpiNsLocal().
 276  *
 277  *              "A name is located by finding the matching name in the current
 278  *              name space, and then in the parent name space. If the parent
 279  *              name space does not contain the name, the search continues
 280  *              recursively until either the name is found or the name space
 281  *              does not have a parent (the root of the name space).  This
 282  *              indicates that the name is not found" (From ACPI Specification,
 283  *              section 5.3)
 284  *
 285  ******************************************************************************/
 286
 287 static ACPI_STATUS
 288 AcpiNsSearchParentTree (
 289     UINT32                  TargetName,
 290     ACPI_NAMESPACE_NODE     *Node,
 291     OBJECT_TYPE_INTERNAL    Type,
 292     ACPI_NAMESPACE_NODE     **ReturnNode)
 293 {
 294     ACPI_STATUS             Status;
 295     ACPI_NAMESPACE_NODE     *ParentNode;
 296
 297
 298     FUNCTION_TRACE ("NsSearchParentTree");
 299
 300
 301     ParentNode = AcpiNsGetParentObject (Node);
 302
 303     /*
 304      * If there is no parent (at the root) or type is "local", we won't be
 305      * searching the parent tree.
 306      */
 307     if ((AcpiNsLocal (Type))    ||
 308         (!ParentNode))
 309     {
 310         if (!ParentNode)
 311         {
 312             DEBUG_PRINT (TRACE_NAMES,
 313                 ("NsSearchParentTree: [%4.4s] has no parent\n",
 314                 &TargetName));
 315         }
 316
 317         if (AcpiNsLocal (Type))
 318         {
 319             DEBUG_PRINT (TRACE_NAMES,
 320                 ("NsSearchParentTree: [%4.4s] (type %X) is local (no search)\n",
 321                 &TargetName, Type));
 322         }
 323
 324         return_ACPI_STATUS (AE_NOT_FOUND);
 325     }
 326
 327
 328     /* Search the parent tree */
 329
 330     DEBUG_PRINT (TRACE_NAMES,
 331         ("NsSearchParentTree: Searching parent for %4.4s\n",
 332         &TargetName));
 333
 334     /*
 335      * Search parents until found the target or we have backed up to
 336      * the root
 337      */
 338
 339     while (ParentNode)
 340     {
 341         /* Search parent scope */
 342         /* TBD: [Investigate] Why ACPI_TYPE_ANY? */
 343
 344         Status = AcpiNsSearchNode (TargetName, ParentNode,
 345                                         ACPI_TYPE_ANY, ReturnNode);
 346
 347         if (ACPI_SUCCESS (Status))
 348         {
 349             return_ACPI_STATUS (Status);
 350         }
 351
 352         /*
 353          * Not found here, go up another level
 354          * (until we reach the root)
 355          */
 356
 357         ParentNode = AcpiNsGetParentObject (ParentNode);
 358     }
 359
 360
 361     /* Not found in parent tree */
 362
 363     return_ACPI_STATUS (AE_NOT_FOUND);
 364 }
 365
 366
 367 /*******************************************************************************
 368  *
 369  * FUNCTION:    AcpiNsSearchAndEnter
 370  *
 371  * PARAMETERS:  TargetName          - Ascii ACPI name to search for (4 chars)
 372  *              WalkState           - Current state of the walk
 373  *              *Node           - Starting table where search will begin
 374  *              InterpreterMode     - Add names only in MODE_LoadPassX.
 375  *                                    Otherwise,search only.
 376  *              Type                - Object type to match
 377  *              Flags               - Flags describing the search restrictions
 378  *              **ReturnNode    - Where the Node is returned
 379  *
 380  * RETURN:      Status
 381  *
 382  * DESCRIPTION: Search for a name segment in a single name table,
 383  *              optionally adding it if it is not found.  If the passed
 384  *              Type is not Any and the type previously stored in the
 385  *              entry was Any (i.e. unknown), update the stored type.
 386  *
 387  *              In IMODE_EXECUTE, search only.
 388  *              In other modes, search and add if not found.
 389  *
 390  ******************************************************************************/
 391
 392 ACPI_STATUS
 393 AcpiNsSearchAndEnter (
 394     UINT32                  TargetName,
 395     ACPI_WALK_STATE         *WalkState,
 396     ACPI_NAMESPACE_NODE     *Node,
 397     OPERATING_MODE          InterpreterMode,
 398     OBJECT_TYPE_INTERNAL    Type,
 399     UINT32                  Flags,
 400     ACPI_NAMESPACE_NODE     **ReturnNode)
 401 {
 402     ACPI_STATUS             Status;
 403     ACPI_NAMESPACE_NODE     *NewNode;
 404
 405
 406     FUNCTION_TRACE ("NsSearchAndEnter");
 407
 408
 409     /* Parameter validation */
 410
 411     if (!Node || !TargetName || !ReturnNode)
 412     {
 413         DEBUG_PRINT (ACPI_ERROR,
 414             ("NsSearchAndEnter: Null param:  Table %p Name %p Return %p\n",
 415             Node, TargetName, ReturnNode));
 416
 417         REPORT_ERROR (("NsSearchAndEnter: bad (null) parameter\n"));
 418         return_ACPI_STATUS (AE_BAD_PARAMETER);
 419     }
 420
 421
 422     /* Name must consist of printable characters */
 423
 424     if (!AcpiCmValidAcpiName (TargetName))
 425     {
 426         DEBUG_PRINT (ACPI_ERROR,
 427             ("NsSearchAndEnter:  *** Bad character in name: %08lx *** \n",
 428             TargetName));
 429
 430         REPORT_ERROR (("NsSearchAndEnter: Bad character in ACPI Name\n"));
 431         return_ACPI_STATUS (AE_BAD_CHARACTER);
 432     }
 433
 434
 435     /* Try to find the name in the table specified by the caller */
 436
 437     *ReturnNode = ENTRY_NOT_FOUND;
 438     Status = AcpiNsSearchNode (TargetName, Node,
 439                                     Type, ReturnNode);
 440     if (Status != AE_NOT_FOUND)
 441     {
 442         /*
 443          * Either found it or there was an error
 444          * -- finished either way
 445          */
 446         return_ACPI_STATUS (Status);
 447     }
 448
 449
 450     /*
 451      * Not found in the table.  If we are NOT performing the
 452      * first pass (name entry) of loading the namespace, search
 453      * the parent tree (all the way to the root if necessary.)
 454      * We don't want to perform the parent search when the
 455      * namespace is actually being loaded.  We want to perform
 456      * the search when namespace references are being resolved
 457      * (load pass 2) and during the execution phase.
 458      */
 459
 460     if ((InterpreterMode != IMODE_LOAD_PASS1) &&
 461         (Flags & NS_SEARCH_PARENT))
 462     {
 463         /*
 464          * Not found in table - search parent tree according
 465          * to ACPI specification
 466          */
 467
 468         Status = AcpiNsSearchParentTree (TargetName, Node,
 469                                             Type, ReturnNode);
 470         if (ACPI_SUCCESS (Status))
 471         {
 472             return_ACPI_STATUS (Status);
 473         }
 474     }
 475
 476
 477     /*
 478      * In execute mode, just search, never add names.  Exit now.
 479      */
 480     if (InterpreterMode == IMODE_EXECUTE)
 481     {
 482         DEBUG_PRINT (TRACE_NAMES,
 483             ("NsSearchAndEnter: %4.4s Not found in %p [Not adding]\n",
 484             &TargetName, Node));
 485
 486         return_ACPI_STATUS (AE_NOT_FOUND);
 487     }
 488
 489
 490     /* Create the new named object */
 491
 492     NewNode = AcpiNsCreateNode (TargetName);
 493     if (!NewNode)
 494     {
 495         return_ACPI_STATUS (AE_NO_MEMORY);
 496     }
 497
 498     /* Install the new object into the parent's list of children */
 499
 500     AcpiNsInstallNode (WalkState, Node, NewNode, Type);
 501     *ReturnNode = NewNode;
 502
 503     return_ACPI_STATUS (AE_OK);
 504 }
 505