nssearch.c revision 114237
150477Speter/******************************************************************************* 235388Smjacob * 335388Smjacob * Module Name: nssearch - Namespace search 435388Smjacob * $Revision: 95 $ 566189Smjacob * 635388Smjacob ******************************************************************************/ 752347Smjacob 835388Smjacob/****************************************************************************** 935388Smjacob * 1035388Smjacob * 1. Copyright Notice 1135388Smjacob * 1235388Smjacob * Some or all of this work - Copyright (c) 1999 - 2003, Intel Corp. 1335388Smjacob * All rights reserved. 1466189Smjacob * 1535388Smjacob * 2. License 1635388Smjacob * 1735388Smjacob * 2.1. This is your license from Intel Corp. under its intellectual property 1835388Smjacob * rights. You may have additional license terms from the party that provided 1935388Smjacob * you this software, covering your right to use that party's intellectual 2035388Smjacob * property rights. 2135388Smjacob * 2235388Smjacob * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a 2335388Smjacob * copy of the source code appearing in this file ("Covered Code") an 2435388Smjacob * irrevocable, perpetual, worldwide license under Intel's copyrights in the 2535388Smjacob * base code distributed originally by Intel ("Original Intel Code") to copy, 2635388Smjacob * make derivatives, distribute, use and display any portion of the Covered 2735388Smjacob * Code in any form, with the right to sublicense such rights; and 2835388Smjacob * 2935388Smjacob * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent 3035388Smjacob * license (with the right to sublicense), under only those claims of Intel 3135388Smjacob * patents that are infringed by the Original Intel Code, to make, use, sell, 3235388Smjacob * offer to sell, and import the Covered Code and derivative works thereof 3335388Smjacob * solely to the minimum extent necessary to exercise the above copyright 3444819Smjacob * license, and in no event shall the patent license extend to any additions 3535388Smjacob * to or modifications of the Original Intel Code. No other license or right 3653487Smjacob * is granted directly or by implication, estoppel or otherwise; 3753487Smjacob * 3856004Smjacob * The above copyright and patent license is granted only if the following 3935388Smjacob * conditions are met: 4053487Smjacob * 4135388Smjacob * 3. Conditions 4235388Smjacob * 4353487Smjacob * 3.1. Redistribution of Source with Rights to Further Distribute Source. 4453487Smjacob * Redistribution of source code of any substantial portion of the Covered 4556004Smjacob * Code or modification with rights to further distribute source must include 4635388Smjacob * the above Copyright Notice, the above License, this list of Conditions, 4753487Smjacob * and the following Disclaimer and Export Compliance provision. In addition, 4835388Smjacob * Licensee must cause all Covered Code to which Licensee contributes to 4942131Smjacob * contain a file documenting the changes Licensee made to create that Covered 5053487Smjacob * Code and the date of any change. Licensee must include in that file the 5153487Smjacob * documentation of any changes made by any predecessor Licensee. Licensee 5256004Smjacob * must include a prominent statement that the modification is derived, 5335388Smjacob * directly or indirectly, from Original Intel Code. 5453487Smjacob * 5535388Smjacob * 3.2. Redistribution of Source with no Rights to Further Distribute Source. 5664087Smjacob * Redistribution of source code of any substantial portion of the Covered 5787635Smjacob * Code or modification without rights to further distribute source must 5839235Sgibbs * include the following Disclaimer and Export Compliance provision in the 5935388Smjacob * documentation and/or other materials provided with distribution. In 6043420Smjacob * addition, Licensee may not authorize further sublicense of source of any 6135388Smjacob * portion of the Covered Code, and must include terms to the effect that the 6235388Smjacob * license from Licensee to its licensee is limited to the intellectual 6335388Smjacob * property embodied in the software Licensee provides to its licensee, and 6482689Smjacob * not to intellectual property embodied in modifications its licensee may 6582689Smjacob * make. 6674229Smjacob * 6774229Smjacob * 3.3. Redistribution of Executable. Redistribution in executable form of any 6874229Smjacob * substantial portion of the Covered Code or modification must reproduce the 6974229Smjacob * above Copyright Notice, and the following Disclaimer and Export Compliance 7082689Smjacob * provision in the documentation and/or other materials provided with the 7135388Smjacob * distribution. 7282689Smjacob * 7374229Smjacob * 3.4. Intel retains all right, title, and interest in and to the Original 7474229Smjacob * Intel Code. 7574229Smjacob * 7690224Smjacob * 3.5. Neither the name Intel nor any other trademark owned or controlled by 7735388Smjacob * Intel shall be used in advertising or otherwise to promote the sale, use or 7835388Smjacob * other dealings in products derived from or relating to the Covered Code 7935388Smjacob * without prior written authorization from Intel. 8035388Smjacob * 8164087Smjacob * 4. Disclaimer and Export Compliance 8264087Smjacob * 8364087Smjacob * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED 8482689Smjacob * HERE. ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE 8582689Smjacob * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT, ASSISTANCE, 8649909Smjacob * INSTALLATION, TRAINING OR OTHER SERVICES. INTEL WILL NOT PROVIDE ANY 8761772Smjacob * UPDATES, ENHANCEMENTS OR EXTENSIONS. INTEL SPECIFICALLY DISCLAIMS ANY 8849909Smjacob * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A 8982689Smjacob * PARTICULAR PURPOSE. 9082689Smjacob * 9182689Smjacob * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES 9282689Smjacob * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR 9382689Smjacob * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT, 9482689Smjacob * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY 9553487Smjacob * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL 9653487Smjacob * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES. THESE LIMITATIONS 9764087Smjacob * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY 9864087Smjacob * LIMITED REMEDY. 9953487Smjacob * 10082689Smjacob * 4.3. Licensee shall not export, either directly or indirectly, any of this 10182689Smjacob * software or system incorporating such software without first obtaining any 10253487Smjacob * required license or other approval from the U. S. Department of Commerce or 10353487Smjacob * any other agency or department of the United States Government. In the 10453487Smjacob * event Licensee exports any such software from the United States or 10553487Smjacob * re-exports any such software from a foreign destination, Licensee shall 10653487Smjacob * ensure that the distribution and export/re-export of the software is in 10753487Smjacob * compliance with all laws, regulations, orders, or other restrictions of the 10853487Smjacob * U.S. Export Administration Regulations. Licensee agrees that neither it nor 10953487Smjacob * any of its subsidiaries will export/re-export any technical data, process, 11053487Smjacob * software, or service, directly or indirectly, to any country for which the 11153487Smjacob * United States government or any agency thereof requires an export license, 11253487Smjacob * other governmental approval, or letter of assurance, without first obtaining 11353487Smjacob * such license, approval or letter. 11453487Smjacob * 11553487Smjacob *****************************************************************************/ 11653487Smjacob 11753487Smjacob#define __NSSEARCH_C__ 11853487Smjacob 11953487Smjacob#include "acpi.h" 12053487Smjacob#include "acnamesp.h" 12153487Smjacob 12253487Smjacob 12364087Smjacob#define _COMPONENT ACPI_NAMESPACE 12464087Smjacob ACPI_MODULE_NAME ("nssearch") 12553487Smjacob 12653487Smjacob 12753487Smjacob/******************************************************************************* 12853487Smjacob * 12953487Smjacob * FUNCTION: AcpiNsSearchNode 13053487Smjacob * 13153487Smjacob * PARAMETERS: *TargetName - Ascii ACPI name to search for 13264087Smjacob * *Node - Starting node where search will begin 13364087Smjacob * Type - Object type to match 13464087Smjacob * **ReturnNode - Where the matched Named obj is returned 13564087Smjacob * 13664087Smjacob * RETURN: Status 13764087Smjacob * 13864087Smjacob * DESCRIPTION: Search a single level of the namespace. Performs a 13964087Smjacob * simple search of the specified level, and does not add 14064087Smjacob * entries or search parents. 14164087Smjacob * 14264087Smjacob * 14364087Smjacob * Named object lists are built (and subsequently dumped) in the 14464087Smjacob * order in which the names are encountered during the namespace load; 14564087Smjacob * 14664087Smjacob * All namespace searching is linear in this implementation, but 14764087Smjacob * could be easily modified to support any improved search 14864087Smjacob * algorithm. However, the linear search was chosen for simplicity 14939235Sgibbs * and because the trees are small and the other interpreter 15064087Smjacob * execution overhead is relatively high. 15164087Smjacob * 15264087Smjacob ******************************************************************************/ 15364087Smjacob 15439235SgibbsACPI_STATUS 15539235SgibbsAcpiNsSearchNode ( 15639235Sgibbs UINT32 TargetName, 15765140Smjacob ACPI_NAMESPACE_NODE *Node, 15839235Sgibbs ACPI_OBJECT_TYPE Type, 15952347Smjacob ACPI_NAMESPACE_NODE **ReturnNode) 16065140Smjacob{ 16165140Smjacob ACPI_NAMESPACE_NODE *NextNode; 16253487Smjacob 16387635Smjacob 16487635Smjacob ACPI_FUNCTION_TRACE ("NsSearchNode"); 16587635Smjacob 16687635Smjacob 16753487Smjacob#ifdef ACPI_DEBUG_OUTPUT 16835388Smjacob if (ACPI_LV_NAMES & AcpiDbgLevel) 16946968Smjacob { 17035388Smjacob char *ScopeName; 17135388Smjacob 17235388Smjacob ScopeName = AcpiNsGetExternalPathname (Node); 17346968Smjacob if (ScopeName) 17452347Smjacob { 17552347Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "Searching %s [%p] For %4.4s (%s)\n", 17635388Smjacob ScopeName, Node, (char *) &TargetName, AcpiUtGetTypeName (Type))); 17735388Smjacob 17842461Smjacob ACPI_MEM_FREE (ScopeName); 17943420Smjacob } 18035388Smjacob } 18145040Smjacob#endif 18265140Smjacob 18335388Smjacob /* 18452347Smjacob * Search for name at this namespace level, which is to say that we 18552347Smjacob * must search for the name among the children of this object 18652347Smjacob */ 18735388Smjacob NextNode = Node->Child; 18852347Smjacob while (NextNode) 18952347Smjacob { 19052347Smjacob /* Check for match against the name */ 19135388Smjacob 19280582Smjacob if (NextNode->Name.Integer == TargetName) 19380582Smjacob { 19446968Smjacob /* 19580582Smjacob * Found matching entry. 19643420Smjacob */ 19743420Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 19880582Smjacob "Name %4.4s Type [%s] found at %p\n", 19980582Smjacob (char *) &TargetName, AcpiUtGetTypeName (NextNode->Type), NextNode)); 20080582Smjacob 20180582Smjacob *ReturnNode = NextNode; 20280582Smjacob return_ACPI_STATUS (AE_OK); 20380582Smjacob } 20480582Smjacob 20580582Smjacob /* 20680582Smjacob * The last entry in the list points back to the parent, 20735388Smjacob * so a flag is used to indicate the end-of-list 20846968Smjacob */ 20935388Smjacob if (NextNode->Flags & ANOBJ_END_OF_PEER_LIST) 21035388Smjacob { 21135388Smjacob /* Searched entire list, we are done */ 21235388Smjacob 21339235Sgibbs break; 21439235Sgibbs } 21539235Sgibbs 21639235Sgibbs /* Didn't match name, move on to the next peer object */ 21739235Sgibbs 21839235Sgibbs NextNode = NextNode->Peer; 21939235Sgibbs } 22039235Sgibbs 22165140Smjacob /* Searched entire namespace level, not found */ 22265140Smjacob 22365140Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "Name %4.4s Type [%s] not found at %p\n", 22443793Smjacob (char *) &TargetName, AcpiUtGetTypeName (Type), NextNode)); 22539235Sgibbs 22635388Smjacob return_ACPI_STATUS (AE_NOT_FOUND); 22739235Sgibbs} 22845040Smjacob 22965140Smjacob 23065140Smjacob/******************************************************************************* 23165140Smjacob * 23265140Smjacob * FUNCTION: AcpiNsSearchParentTree 23352347Smjacob * 23452347Smjacob * PARAMETERS: *TargetName - Ascii ACPI name to search for 23552347Smjacob * *Node - Starting node where search will begin 23652347Smjacob * Type - Object type to match 23735388Smjacob * **ReturnNode - Where the matched Named Obj is returned 23835388Smjacob * 23935388Smjacob * RETURN: Status 24035388Smjacob * 24152347Smjacob * DESCRIPTION: Called when a name has not been found in the current namespace 24252347Smjacob * level. Before adding it or giving up, ACPI scope rules require 24352347Smjacob * searching enclosing scopes in cases identified by AcpiNsLocal(). 24452347Smjacob * 24535388Smjacob * "A name is located by finding the matching name in the current 24652347Smjacob * name space, and then in the parent name space. If the parent 24784241Smjacob * name space does not contain the name, the search continues 24872355Smjacob * recursively until either the name is found or the name space 24948484Smjacob * does not have a parent (the root of the name space). This 25077776Smjacob * indicates that the name is not found" (From ACPI Specification, 25148484Smjacob * section 5.3) 25248484Smjacob * 25359454Smjacob ******************************************************************************/ 25448484Smjacob 25572355Smjacobstatic ACPI_STATUS 25639235SgibbsAcpiNsSearchParentTree ( 25739235Sgibbs UINT32 TargetName, 25872355Smjacob ACPI_NAMESPACE_NODE *Node, 25952347Smjacob ACPI_OBJECT_TYPE Type, 26082841Smjacob ACPI_NAMESPACE_NODE **ReturnNode) 26139235Sgibbs{ 26252347Smjacob ACPI_STATUS Status; 26352347Smjacob ACPI_NAMESPACE_NODE *ParentNode; 26452347Smjacob 26539235Sgibbs 26639235Sgibbs ACPI_FUNCTION_TRACE ("NsSearchParentTree"); 26748484Smjacob 26848484Smjacob 26935388Smjacob ParentNode = AcpiNsGetParentNode (Node); 27048484Smjacob 27148484Smjacob /* 27248484Smjacob * If there is no parent (i.e., we are at the root) or 27348484Smjacob * type is "local", we won't be searching the parent tree. 27448484Smjacob */ 27548484Smjacob if (!ParentNode) 27648484Smjacob { 27744819Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "[%4.4s] has no parent\n", 27848484Smjacob (char *) &TargetName)); 27952347Smjacob return_ACPI_STATUS (AE_NOT_FOUND); 28060221Smjacob } 28177776Smjacob 28277776Smjacob if (AcpiNsLocal (Type)) 28371079Smjacob { 28471079Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 28560221Smjacob "[%4.4s] type [%s] must be local to this scope (no parent search)\n", 28660221Smjacob (char *) &TargetName, AcpiUtGetTypeName (Type))); 28760221Smjacob return_ACPI_STATUS (AE_NOT_FOUND); 28852347Smjacob } 28948484Smjacob 29048484Smjacob /* Search the parent tree */ 29172355Smjacob 29244819Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "Searching parent for %4.4s\n", (char *) &TargetName)); 29344819Smjacob 29435388Smjacob /* 29535388Smjacob * Search parents until found the target or we have backed up to 29648195Smjacob * the root 29782689Smjacob */ 29835388Smjacob while (ParentNode) 29935388Smjacob { 30048484Smjacob /* 30148484Smjacob * Search parent scope. Use TYPE_ANY because we don't care about the 30248484Smjacob * object type at this point, we only care about the existence of 30348484Smjacob * the actual name we are searching for. Typechecking comes later. 30448484Smjacob */ 30548484Smjacob Status = AcpiNsSearchNode (TargetName, ParentNode, 30648484Smjacob ACPI_TYPE_ANY, ReturnNode); 30748484Smjacob if (ACPI_SUCCESS (Status)) 30835388Smjacob { 30948484Smjacob return_ACPI_STATUS (Status); 31048484Smjacob } 31148484Smjacob 31272355Smjacob /* 31372355Smjacob * Not found here, go up another level 31472355Smjacob * (until we reach the root) 31577776Smjacob */ 31677776Smjacob ParentNode = AcpiNsGetParentNode (ParentNode); 31777776Smjacob } 31835388Smjacob 31959454Smjacob /* Not found in parent tree */ 32059454Smjacob 32159454Smjacob return_ACPI_STATUS (AE_NOT_FOUND); 32259454Smjacob} 32359454Smjacob 32459454Smjacob 32542131Smjacob/******************************************************************************* 32635388Smjacob * 32735388Smjacob * FUNCTION: AcpiNsSearchAndEnter 32865140Smjacob * 32935388Smjacob * PARAMETERS: TargetName - Ascii ACPI name to search for (4 chars) 33035388Smjacob * WalkState - Current state of the walk 33135388Smjacob * *Node - Starting node where search will begin 33235388Smjacob * InterpreterMode - Add names only in ACPI_MODE_LOAD_PASS_x. 33335388Smjacob * Otherwise,search only. 33435388Smjacob * Type - Object type to match 33553487Smjacob * Flags - Flags describing the search restrictions 33635388Smjacob * **ReturnNode - Where the Node is returned 33735388Smjacob * 33835388Smjacob * RETURN: Status 33935388Smjacob * 34053487Smjacob * DESCRIPTION: Search for a name segment in a single namespace level, 34153487Smjacob * optionally adding it if it is not found. If the passed 34235388Smjacob * Type is not Any and the type previously stored in the 34335388Smjacob * entry was Any (i.e. unknown), update the stored type. 34453487Smjacob * 34553487Smjacob * In ACPI_IMODE_EXECUTE, search only. 34653487Smjacob * In other modes, search and add if not found. 34753487Smjacob * 34853487Smjacob ******************************************************************************/ 34953487Smjacob 35061772SmjacobACPI_STATUS 35135388SmjacobAcpiNsSearchAndEnter ( 35271079Smjacob UINT32 TargetName, 35390224Smjacob ACPI_WALK_STATE *WalkState, 35490224Smjacob ACPI_NAMESPACE_NODE *Node, 35587635Smjacob ACPI_INTERPRETER_MODE InterpreterMode, 35687635Smjacob ACPI_OBJECT_TYPE Type, 35753487Smjacob UINT32 Flags, 35853487Smjacob ACPI_NAMESPACE_NODE **ReturnNode) 35965140Smjacob{ 36087635Smjacob ACPI_STATUS Status; 36171079Smjacob ACPI_NAMESPACE_NODE *NewNode; 36271079Smjacob 36371079Smjacob 36471079Smjacob ACPI_FUNCTION_TRACE ("NsSearchAndEnter"); 36582689Smjacob 36682689Smjacob 36782689Smjacob /* Parameter validation */ 36882689Smjacob 36982689Smjacob if (!Node || !TargetName || !ReturnNode) 37069522Smjacob { 37169522Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_ERROR, "Null param: Node %p Name %X ReturnNode %p\n", 37269522Smjacob Node, TargetName, ReturnNode)); 37369522Smjacob 37469522Smjacob ACPI_REPORT_ERROR (("NsSearchAndEnter: Null parameter\n")); 37588855Smjacob return_ACPI_STATUS (AE_BAD_PARAMETER); 37688855Smjacob } 37788855Smjacob 37888855Smjacob /* Name must consist of printable characters */ 37988855Smjacob 38088855Smjacob if (!AcpiUtValidAcpiName (TargetName)) 38139235Sgibbs { 38235388Smjacob ACPI_REPORT_ERROR (("NsSearchAndEnter: Bad character in ACPI Name: %X\n", 38339235Sgibbs TargetName)); 38435388Smjacob return_ACPI_STATUS (AE_BAD_CHARACTER); 38535388Smjacob } 38662171Smjacob 38787635Smjacob /* Try to find the name in the namespace level specified by the caller */ 38887635Smjacob 38939235Sgibbs *ReturnNode = ACPI_ENTRY_NOT_FOUND; 39046968Smjacob Status = AcpiNsSearchNode (TargetName, Node, Type, ReturnNode); 39146968Smjacob if (Status != AE_NOT_FOUND) 39252347Smjacob { 39352347Smjacob /* 39452347Smjacob * If we found it AND the request specifies that a find is an error, 39552347Smjacob * return the error 39652347Smjacob */ 39762171Smjacob if ((Status == AE_OK) && 39871079Smjacob (Flags & ACPI_NS_ERROR_IF_FOUND)) 39990224Smjacob { 40090224Smjacob Status = AE_ALREADY_EXISTS; 40190224Smjacob } 40290224Smjacob 40335388Smjacob /* 40435388Smjacob * Either found it or there was an error 40553487Smjacob * -- finished either way 40635388Smjacob */ 40764087Smjacob return_ACPI_STATUS (Status); 40835388Smjacob } 40935388Smjacob 41052347Smjacob /* 41135388Smjacob * The name was not found. If we are NOT performing the 41248195Smjacob * first pass (name entry) of loading the namespace, search 41348195Smjacob * the parent tree (all the way to the root if necessary.) 41482689Smjacob * We don't want to perform the parent search when the 41582689Smjacob * namespace is actually being loaded. We want to perform 41665140Smjacob * the search when namespace references are being resolved 41735388Smjacob * (load pass 2) and during the execution phase. 41849909Smjacob */ 41949909Smjacob if ((InterpreterMode != ACPI_IMODE_LOAD_PASS1) && 42049909Smjacob (Flags & ACPI_NS_SEARCH_PARENT)) 42135388Smjacob { 42264087Smjacob /* 42335388Smjacob * Not found at this level - search parent tree according 42435388Smjacob * to ACPI specification 42535388Smjacob */ 42635388Smjacob Status = AcpiNsSearchParentTree (TargetName, Node, 42735388Smjacob Type, ReturnNode); 42835388Smjacob if (ACPI_SUCCESS (Status)) 42935388Smjacob { 43035388Smjacob return_ACPI_STATUS (Status); 43135388Smjacob } 43235388Smjacob } 43343793Smjacob 43484241Smjacob /* 43584241Smjacob * In execute mode, just search, never add names. Exit now. 43653487Smjacob */ 43753487Smjacob if (InterpreterMode == ACPI_IMODE_EXECUTE) 43869522Smjacob { 43969522Smjacob ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "%4.4s Not found in %p [Not adding]\n", 44069522Smjacob (char *) &TargetName, Node)); 44169522Smjacob 44269522Smjacob return_ACPI_STATUS (AE_NOT_FOUND); 44335388Smjacob } 44464087Smjacob 44571079Smjacob /* Create the new named object */ 44671079Smjacob 44771079Smjacob NewNode = AcpiNsCreateNode (TargetName); 44871079Smjacob if (!NewNode) 44971079Smjacob { 45071079Smjacob return_ACPI_STATUS (AE_NO_MEMORY); 45171079Smjacob } 45271079Smjacob 45371079Smjacob /* Install the new object into the parent's list of children */ 45471079Smjacob 45571079Smjacob AcpiNsInstallNode (WalkState, Node, NewNode, Type); 45671079Smjacob *ReturnNode = NewNode; 45771079Smjacob 45871079Smjacob return_ACPI_STATUS (AE_OK); 45971079Smjacob} 46071079Smjacob 46171079Smjacob