167754Smsmith/******************************************************************************* 267754Smsmith * 367754Smsmith * Module Name: nssearch - Namespace search 467754Smsmith * 567754Smsmith ******************************************************************************/ 667754Smsmith 7217365Sjkim/* 8245582Sjkim * Copyright (C) 2000 - 2013, Intel Corp. 970243Smsmith * All rights reserved. 1067754Smsmith * 11217365Sjkim * Redistribution and use in source and binary forms, with or without 12217365Sjkim * modification, are permitted provided that the following conditions 13217365Sjkim * are met: 14217365Sjkim * 1. Redistributions of source code must retain the above copyright 15217365Sjkim * notice, this list of conditions, and the following disclaimer, 16217365Sjkim * without modification. 17217365Sjkim * 2. Redistributions in binary form must reproduce at minimum a disclaimer 18217365Sjkim * substantially similar to the "NO WARRANTY" disclaimer below 19217365Sjkim * ("Disclaimer") and any redistribution must be conditioned upon 20217365Sjkim * including a substantially similar Disclaimer requirement for further 21217365Sjkim * binary redistribution. 22217365Sjkim * 3. Neither the names of the above-listed copyright holders nor the names 23217365Sjkim * of any contributors may be used to endorse or promote products derived 24217365Sjkim * from this software without specific prior written permission. 2567754Smsmith * 26217365Sjkim * Alternatively, this software may be distributed under the terms of the 27217365Sjkim * GNU General Public License ("GPL") version 2 as published by the Free 28217365Sjkim * Software Foundation. 2967754Smsmith * 30217365Sjkim * NO WARRANTY 31217365Sjkim * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32217365Sjkim * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33217365Sjkim * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 34217365Sjkim * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 35217365Sjkim * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 36217365Sjkim * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 37217365Sjkim * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 38217365Sjkim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 39217365Sjkim * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 40217365Sjkim * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 41217365Sjkim * POSSIBILITY OF SUCH DAMAGES. 42217365Sjkim */ 4367754Smsmith 4467754Smsmith#define __NSSEARCH_C__ 4567754Smsmith 46193341Sjkim#include <contrib/dev/acpica/include/acpi.h> 47193341Sjkim#include <contrib/dev/acpica/include/accommon.h> 48193341Sjkim#include <contrib/dev/acpica/include/acnamesp.h> 4967754Smsmith 50193267Sjkim#ifdef ACPI_ASL_COMPILER 51193341Sjkim#include <contrib/dev/acpica/include/amlcode.h> 52193267Sjkim#endif 5367754Smsmith 5477424Smsmith#define _COMPONENT ACPI_NAMESPACE 5591116Smsmith ACPI_MODULE_NAME ("nssearch") 5667754Smsmith 57151937Sjkim/* Local prototypes */ 5867754Smsmith 59151937Sjkimstatic ACPI_STATUS 60151937SjkimAcpiNsSearchParentTree ( 61151937Sjkim UINT32 TargetName, 62151937Sjkim ACPI_NAMESPACE_NODE *Node, 63151937Sjkim ACPI_OBJECT_TYPE Type, 64151937Sjkim ACPI_NAMESPACE_NODE **ReturnNode); 65151937Sjkim 66151937Sjkim 6767754Smsmith/******************************************************************************* 6867754Smsmith * 69167802Sjkim * FUNCTION: AcpiNsSearchOneScope 7067754Smsmith * 71151937Sjkim * PARAMETERS: TargetName - Ascii ACPI name to search for 72167802Sjkim * ParentNode - Starting node where search will begin 73151937Sjkim * Type - Object type to match 74151937Sjkim * ReturnNode - Where the matched Named obj is returned 7567754Smsmith * 7667754Smsmith * RETURN: Status 7767754Smsmith * 78167802Sjkim * DESCRIPTION: Search a single level of the namespace. Performs a 79114237Snjl * simple search of the specified level, and does not add 80107325Siwasaki * entries or search parents. 8167754Smsmith * 8267754Smsmith * 8367754Smsmith * Named object lists are built (and subsequently dumped) in the 8467754Smsmith * order in which the names are encountered during the namespace load; 8567754Smsmith * 8667754Smsmith * All namespace searching is linear in this implementation, but 8767754Smsmith * could be easily modified to support any improved search 88167802Sjkim * algorithm. However, the linear search was chosen for simplicity 8967754Smsmith * and because the trees are small and the other interpreter 9067754Smsmith * execution overhead is relatively high. 9167754Smsmith * 92167802Sjkim * Note: CPU execution analysis has shown that the AML interpreter spends 93167802Sjkim * a very small percentage of its time searching the namespace. Therefore, 94167802Sjkim * the linear search seems to be sufficient, as there would seem to be 95167802Sjkim * little value in improving the search. 96167802Sjkim * 9767754Smsmith ******************************************************************************/ 9867754Smsmith 9967754SmsmithACPI_STATUS 100167802SjkimAcpiNsSearchOneScope ( 10167754Smsmith UINT32 TargetName, 102167802Sjkim ACPI_NAMESPACE_NODE *ParentNode, 10391116Smsmith ACPI_OBJECT_TYPE Type, 10467754Smsmith ACPI_NAMESPACE_NODE **ReturnNode) 10567754Smsmith{ 106167802Sjkim ACPI_NAMESPACE_NODE *Node; 10767754Smsmith 10867754Smsmith 109167802Sjkim ACPI_FUNCTION_TRACE (NsSearchOneScope); 11067754Smsmith 11171867Smsmith 112102550Siwasaki#ifdef ACPI_DEBUG_OUTPUT 11382367Smsmith if (ACPI_LV_NAMES & AcpiDbgLevel) 11467754Smsmith { 115114237Snjl char *ScopeName; 11677424Smsmith 117167802Sjkim ScopeName = AcpiNsGetExternalPathname (ParentNode); 11871867Smsmith if (ScopeName) 11971867Smsmith { 120138287Smarks ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 121138287Smarks "Searching %s (%p) For [%4.4s] (%s)\n", 122167802Sjkim ScopeName, ParentNode, ACPI_CAST_PTR (char, &TargetName), 123138287Smarks AcpiUtGetTypeName (Type))); 12471867Smsmith 125167802Sjkim ACPI_FREE (ScopeName); 12671867Smsmith } 12767754Smsmith } 12871867Smsmith#endif 12967754Smsmith 13067754Smsmith /* 131114237Snjl * Search for name at this namespace level, which is to say that we 132107325Siwasaki * must search for the name among the children of this object 13367754Smsmith */ 134167802Sjkim Node = ParentNode->Child; 135167802Sjkim while (Node) 13667754Smsmith { 13767754Smsmith /* Check for match against the name */ 13867754Smsmith 139167802Sjkim if (Node->Name.Integer == TargetName) 14067754Smsmith { 141128212Snjl /* Resolve a control method alias if any */ 142128212Snjl 143167802Sjkim if (AcpiNsGetType (Node) == ACPI_TYPE_LOCAL_METHOD_ALIAS) 144128212Snjl { 145167802Sjkim Node = ACPI_CAST_PTR (ACPI_NAMESPACE_NODE, Node->Object); 146128212Snjl } 147128212Snjl 148167802Sjkim /* Found matching entry */ 149167802Sjkim 15083174Smsmith ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 151123315Snjl "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n", 152167802Sjkim ACPI_CAST_PTR (char, &TargetName), 153167802Sjkim AcpiUtGetTypeName (Node->Type), 154167802Sjkim Node, AcpiUtGetNodeName (ParentNode), ParentNode)); 15567754Smsmith 156167802Sjkim *ReturnNode = Node; 15767754Smsmith return_ACPI_STATUS (AE_OK); 15867754Smsmith } 15967754Smsmith 16067754Smsmith /* Didn't match name, move on to the next peer object */ 16167754Smsmith 162167802Sjkim Node = Node->Peer; 16367754Smsmith } 16467754Smsmith 165107325Siwasaki /* Searched entire namespace level, not found */ 16667754Smsmith 167117521Snjl ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 168193267Sjkim "Name [%4.4s] (%s) not found in search in scope [%4.4s] " 169193267Sjkim "%p first child %p\n", 170167802Sjkim ACPI_CAST_PTR (char, &TargetName), AcpiUtGetTypeName (Type), 171167802Sjkim AcpiUtGetNodeName (ParentNode), ParentNode, ParentNode->Child)); 17267754Smsmith 17367754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 17467754Smsmith} 17567754Smsmith 17667754Smsmith 17767754Smsmith/******************************************************************************* 17867754Smsmith * 17967754Smsmith * FUNCTION: AcpiNsSearchParentTree 18067754Smsmith * 181151937Sjkim * PARAMETERS: TargetName - Ascii ACPI name to search for 182151937Sjkim * Node - Starting node where search will begin 183151937Sjkim * Type - Object type to match 184151937Sjkim * ReturnNode - Where the matched Node is returned 18567754Smsmith * 18667754Smsmith * RETURN: Status 18767754Smsmith * 18867754Smsmith * DESCRIPTION: Called when a name has not been found in the current namespace 189167802Sjkim * level. Before adding it or giving up, ACPI scope rules require 19067754Smsmith * searching enclosing scopes in cases identified by AcpiNsLocal(). 19167754Smsmith * 19267754Smsmith * "A name is located by finding the matching name in the current 19367754Smsmith * name space, and then in the parent name space. If the parent 19467754Smsmith * name space does not contain the name, the search continues 19567754Smsmith * recursively until either the name is found or the name space 196167802Sjkim * does not have a parent (the root of the name space). This 19767754Smsmith * indicates that the name is not found" (From ACPI Specification, 19867754Smsmith * section 5.3) 19967754Smsmith * 20067754Smsmith ******************************************************************************/ 20167754Smsmith 20269450Smsmithstatic ACPI_STATUS 20367754SmsmithAcpiNsSearchParentTree ( 20467754Smsmith UINT32 TargetName, 20567754Smsmith ACPI_NAMESPACE_NODE *Node, 20691116Smsmith ACPI_OBJECT_TYPE Type, 20767754Smsmith ACPI_NAMESPACE_NODE **ReturnNode) 20867754Smsmith{ 20967754Smsmith ACPI_STATUS Status; 21067754Smsmith ACPI_NAMESPACE_NODE *ParentNode; 21167754Smsmith 21267754Smsmith 213167802Sjkim ACPI_FUNCTION_TRACE (NsSearchParentTree); 21467754Smsmith 21567754Smsmith 216209746Sjkim ParentNode = Node->Parent; 21767754Smsmith 21867754Smsmith /* 219138287Smarks * If there is no parent (i.e., we are at the root) or type is "local", 220138287Smarks * we won't be searching the parent tree. 22167754Smsmith */ 222107325Siwasaki if (!ParentNode) 22367754Smsmith { 224107325Siwasaki ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "[%4.4s] has no parent\n", 225167802Sjkim ACPI_CAST_PTR (char, &TargetName))); 226138287Smarks return_ACPI_STATUS (AE_NOT_FOUND); 227107325Siwasaki } 22867754Smsmith 229107325Siwasaki if (AcpiNsLocal (Type)) 230107325Siwasaki { 231107325Siwasaki ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 232107325Siwasaki "[%4.4s] type [%s] must be local to this scope (no parent search)\n", 233167802Sjkim ACPI_CAST_PTR (char, &TargetName), AcpiUtGetTypeName (Type))); 23467754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 23567754Smsmith } 23667754Smsmith 23767754Smsmith /* Search the parent tree */ 23867754Smsmith 239138287Smarks ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 240138287Smarks "Searching parent [%4.4s] for [%4.4s]\n", 241167802Sjkim AcpiUtGetNodeName (ParentNode), ACPI_CAST_PTR (char, &TargetName))); 24267754Smsmith 243193267Sjkim /* Search parents until target is found or we have backed up to the root */ 244193267Sjkim 24567754Smsmith while (ParentNode) 24667754Smsmith { 24791116Smsmith /* 248167802Sjkim * Search parent scope. Use TYPE_ANY because we don't care about the 24991116Smsmith * object type at this point, we only care about the existence of 250167802Sjkim * the actual name we are searching for. Typechecking comes later. 25187031Smsmith */ 252167802Sjkim Status = AcpiNsSearchOneScope ( 253167802Sjkim TargetName, ParentNode, ACPI_TYPE_ANY, ReturnNode); 25467754Smsmith if (ACPI_SUCCESS (Status)) 25567754Smsmith { 25667754Smsmith return_ACPI_STATUS (Status); 25767754Smsmith } 25867754Smsmith 259167802Sjkim /* Not found here, go up another level (until we reach the root) */ 260167802Sjkim 261209746Sjkim ParentNode = ParentNode->Parent; 26267754Smsmith } 26367754Smsmith 26467754Smsmith /* Not found in parent tree */ 26567754Smsmith 26667754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 26767754Smsmith} 26867754Smsmith 26967754Smsmith 27067754Smsmith/******************************************************************************* 27167754Smsmith * 27267754Smsmith * FUNCTION: AcpiNsSearchAndEnter 27367754Smsmith * 27467754Smsmith * PARAMETERS: TargetName - Ascii ACPI name to search for (4 chars) 27567754Smsmith * WalkState - Current state of the walk 276151937Sjkim * Node - Starting node where search will begin 277107325Siwasaki * InterpreterMode - Add names only in ACPI_MODE_LOAD_PASS_x. 27867754Smsmith * Otherwise,search only. 27967754Smsmith * Type - Object type to match 28067754Smsmith * Flags - Flags describing the search restrictions 281151937Sjkim * ReturnNode - Where the Node is returned 28267754Smsmith * 28367754Smsmith * RETURN: Status 28467754Smsmith * 285107325Siwasaki * DESCRIPTION: Search for a name segment in a single namespace level, 286167802Sjkim * optionally adding it if it is not found. If the passed 28767754Smsmith * Type is not Any and the type previously stored in the 28867754Smsmith * entry was Any (i.e. unknown), update the stored type. 28967754Smsmith * 290107325Siwasaki * In ACPI_IMODE_EXECUTE, search only. 29167754Smsmith * In other modes, search and add if not found. 29267754Smsmith * 29367754Smsmith ******************************************************************************/ 29467754Smsmith 29567754SmsmithACPI_STATUS 29667754SmsmithAcpiNsSearchAndEnter ( 29767754Smsmith UINT32 TargetName, 29867754Smsmith ACPI_WALK_STATE *WalkState, 29967754Smsmith ACPI_NAMESPACE_NODE *Node, 30091116Smsmith ACPI_INTERPRETER_MODE InterpreterMode, 30191116Smsmith ACPI_OBJECT_TYPE Type, 30267754Smsmith UINT32 Flags, 30367754Smsmith ACPI_NAMESPACE_NODE **ReturnNode) 30467754Smsmith{ 30567754Smsmith ACPI_STATUS Status; 30667754Smsmith ACPI_NAMESPACE_NODE *NewNode; 30767754Smsmith 30867754Smsmith 309167802Sjkim ACPI_FUNCTION_TRACE (NsSearchAndEnter); 31067754Smsmith 31167754Smsmith 31267754Smsmith /* Parameter validation */ 31367754Smsmith 31467754Smsmith if (!Node || !TargetName || !ReturnNode) 31567754Smsmith { 316167802Sjkim ACPI_ERROR ((AE_INFO, 317204773Sjkim "Null parameter: Node %p Name 0x%X ReturnNode %p", 31867754Smsmith Node, TargetName, ReturnNode)); 31967754Smsmith return_ACPI_STATUS (AE_BAD_PARAMETER); 32067754Smsmith } 32167754Smsmith 322167802Sjkim /* 323167802Sjkim * Name must consist of valid ACPI characters. We will repair the name if 324167802Sjkim * necessary because we don't want to abort because of this, but we want 325167802Sjkim * all namespace names to be printable. A warning message is appropriate. 326167802Sjkim * 327167802Sjkim * This issue came up because there are in fact machines that exhibit 328167802Sjkim * this problem, and we want to be able to enable ACPI support for them, 329167802Sjkim * even though there are a few bad names. 330167802Sjkim */ 331193267Sjkim AcpiUtRepairName (ACPI_CAST_PTR (char, &TargetName)); 332167802Sjkim 333107325Siwasaki /* Try to find the name in the namespace level specified by the caller */ 33467754Smsmith 33591116Smsmith *ReturnNode = ACPI_ENTRY_NOT_FOUND; 336167802Sjkim Status = AcpiNsSearchOneScope (TargetName, Node, Type, ReturnNode); 33767754Smsmith if (Status != AE_NOT_FOUND) 33867754Smsmith { 33967754Smsmith /* 34077424Smsmith * If we found it AND the request specifies that a find is an error, 34177424Smsmith * return the error 34271867Smsmith */ 34371867Smsmith if ((Status == AE_OK) && 34491116Smsmith (Flags & ACPI_NS_ERROR_IF_FOUND)) 34571867Smsmith { 34687031Smsmith Status = AE_ALREADY_EXISTS; 34771867Smsmith } 34871867Smsmith 349193267Sjkim#ifdef ACPI_ASL_COMPILER 350193267Sjkim if (*ReturnNode && (*ReturnNode)->Type == ACPI_TYPE_ANY) 351193267Sjkim { 352193267Sjkim (*ReturnNode)->Flags |= ANOBJ_IS_EXTERNAL; 353193267Sjkim } 354193267Sjkim#endif 355193267Sjkim 356167802Sjkim /* Either found it or there was an error: finished either way */ 357167802Sjkim 35867754Smsmith return_ACPI_STATUS (Status); 35967754Smsmith } 36067754Smsmith 36167754Smsmith /* 362167802Sjkim * The name was not found. If we are NOT performing the first pass 363138287Smarks * (name entry) of loading the namespace, search the parent tree (all the 364138287Smarks * way to the root if necessary.) We don't want to perform the parent 365167802Sjkim * search when the namespace is actually being loaded. We want to perform 366138287Smarks * the search when namespace references are being resolved (load pass 2) 367138287Smarks * and during the execution phase. 36867754Smsmith */ 36991116Smsmith if ((InterpreterMode != ACPI_IMODE_LOAD_PASS1) && 37091116Smsmith (Flags & ACPI_NS_SEARCH_PARENT)) 37167754Smsmith { 37267754Smsmith /* 373138287Smarks * Not found at this level - search parent tree according to the 374138287Smarks * ACPI specification 37567754Smsmith */ 376138287Smarks Status = AcpiNsSearchParentTree (TargetName, Node, Type, ReturnNode); 37767754Smsmith if (ACPI_SUCCESS (Status)) 37867754Smsmith { 37967754Smsmith return_ACPI_STATUS (Status); 38067754Smsmith } 38167754Smsmith } 38267754Smsmith 383167802Sjkim /* In execute mode, just search, never add names. Exit now */ 384167802Sjkim 38591116Smsmith if (InterpreterMode == ACPI_IMODE_EXECUTE) 38667754Smsmith { 387138287Smarks ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 388138287Smarks "%4.4s Not found in %p [Not adding]\n", 389167802Sjkim ACPI_CAST_PTR (char, &TargetName), Node)); 39067754Smsmith 39167754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 39267754Smsmith } 39367754Smsmith 39467754Smsmith /* Create the new named object */ 39567754Smsmith 39667754Smsmith NewNode = AcpiNsCreateNode (TargetName); 39767754Smsmith if (!NewNode) 39867754Smsmith { 39967754Smsmith return_ACPI_STATUS (AE_NO_MEMORY); 40067754Smsmith } 40167754Smsmith 402167802Sjkim#ifdef ACPI_ASL_COMPILER 403193267Sjkim 404193267Sjkim /* Node is an object defined by an External() statement */ 405193267Sjkim 406193267Sjkim if (Flags & ACPI_NS_EXTERNAL || 407193267Sjkim (WalkState && WalkState->Opcode == AML_SCOPE_OP)) 408167802Sjkim { 409167802Sjkim NewNode->Flags |= ANOBJ_IS_EXTERNAL; 410167802Sjkim } 411167802Sjkim#endif 412167802Sjkim 413167802Sjkim if (Flags & ACPI_NS_TEMPORARY) 414167802Sjkim { 415167802Sjkim NewNode->Flags |= ANOBJ_TEMPORARY; 416167802Sjkim } 417167802Sjkim 41867754Smsmith /* Install the new object into the parent's list of children */ 41967754Smsmith 42067754Smsmith AcpiNsInstallNode (WalkState, Node, NewNode, Type); 42167754Smsmith *ReturnNode = NewNode; 42267754Smsmith return_ACPI_STATUS (AE_OK); 42367754Smsmith} 424