167754Smsmith/******************************************************************************* 267754Smsmith * 367754Smsmith * Module Name: nssearch - Namespace search 467754Smsmith * 567754Smsmith ******************************************************************************/ 667754Smsmith 7217365Sjkim/* 8306536Sjkim * Copyright (C) 2000 - 2016, 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 44193341Sjkim#include <contrib/dev/acpica/include/acpi.h> 45193341Sjkim#include <contrib/dev/acpica/include/accommon.h> 46193341Sjkim#include <contrib/dev/acpica/include/acnamesp.h> 4767754Smsmith 48193267Sjkim#ifdef ACPI_ASL_COMPILER 49193341Sjkim#include <contrib/dev/acpica/include/amlcode.h> 50193267Sjkim#endif 5167754Smsmith 5277424Smsmith#define _COMPONENT ACPI_NAMESPACE 5391116Smsmith ACPI_MODULE_NAME ("nssearch") 5467754Smsmith 55151937Sjkim/* Local prototypes */ 5667754Smsmith 57151937Sjkimstatic ACPI_STATUS 58151937SjkimAcpiNsSearchParentTree ( 59151937Sjkim UINT32 TargetName, 60151937Sjkim ACPI_NAMESPACE_NODE *Node, 61151937Sjkim ACPI_OBJECT_TYPE Type, 62151937Sjkim ACPI_NAMESPACE_NODE **ReturnNode); 63151937Sjkim 64151937Sjkim 6567754Smsmith/******************************************************************************* 6667754Smsmith * 67167802Sjkim * FUNCTION: AcpiNsSearchOneScope 6867754Smsmith * 69151937Sjkim * PARAMETERS: TargetName - Ascii ACPI name to search for 70167802Sjkim * ParentNode - Starting node where search will begin 71151937Sjkim * Type - Object type to match 72151937Sjkim * ReturnNode - Where the matched Named obj is returned 7367754Smsmith * 7467754Smsmith * RETURN: Status 7567754Smsmith * 76167802Sjkim * DESCRIPTION: Search a single level of the namespace. Performs a 77114237Snjl * simple search of the specified level, and does not add 78107325Siwasaki * entries or search parents. 7967754Smsmith * 8067754Smsmith * 8167754Smsmith * Named object lists are built (and subsequently dumped) in the 8267754Smsmith * order in which the names are encountered during the namespace load; 8367754Smsmith * 8467754Smsmith * All namespace searching is linear in this implementation, but 8567754Smsmith * could be easily modified to support any improved search 86167802Sjkim * algorithm. However, the linear search was chosen for simplicity 8767754Smsmith * and because the trees are small and the other interpreter 8867754Smsmith * execution overhead is relatively high. 8967754Smsmith * 90167802Sjkim * Note: CPU execution analysis has shown that the AML interpreter spends 91167802Sjkim * a very small percentage of its time searching the namespace. Therefore, 92167802Sjkim * the linear search seems to be sufficient, as there would seem to be 93167802Sjkim * little value in improving the search. 94167802Sjkim * 9567754Smsmith ******************************************************************************/ 9667754Smsmith 9767754SmsmithACPI_STATUS 98167802SjkimAcpiNsSearchOneScope ( 9967754Smsmith UINT32 TargetName, 100167802Sjkim ACPI_NAMESPACE_NODE *ParentNode, 10191116Smsmith ACPI_OBJECT_TYPE Type, 10267754Smsmith ACPI_NAMESPACE_NODE **ReturnNode) 10367754Smsmith{ 104167802Sjkim ACPI_NAMESPACE_NODE *Node; 10567754Smsmith 10667754Smsmith 107167802Sjkim ACPI_FUNCTION_TRACE (NsSearchOneScope); 10867754Smsmith 10971867Smsmith 110102550Siwasaki#ifdef ACPI_DEBUG_OUTPUT 11182367Smsmith if (ACPI_LV_NAMES & AcpiDbgLevel) 11267754Smsmith { 113114237Snjl char *ScopeName; 11477424Smsmith 115306536Sjkim ScopeName = AcpiNsGetNormalizedPathname (ParentNode, TRUE); 11671867Smsmith if (ScopeName) 11771867Smsmith { 118138287Smarks ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 119138287Smarks "Searching %s (%p) For [%4.4s] (%s)\n", 120167802Sjkim ScopeName, ParentNode, ACPI_CAST_PTR (char, &TargetName), 121138287Smarks AcpiUtGetTypeName (Type))); 12271867Smsmith 123167802Sjkim ACPI_FREE (ScopeName); 12471867Smsmith } 12567754Smsmith } 12671867Smsmith#endif 12767754Smsmith 12867754Smsmith /* 129114237Snjl * Search for name at this namespace level, which is to say that we 130107325Siwasaki * must search for the name among the children of this object 13167754Smsmith */ 132167802Sjkim Node = ParentNode->Child; 133167802Sjkim while (Node) 13467754Smsmith { 13567754Smsmith /* Check for match against the name */ 13667754Smsmith 137167802Sjkim if (Node->Name.Integer == TargetName) 13867754Smsmith { 139128212Snjl /* Resolve a control method alias if any */ 140128212Snjl 141167802Sjkim if (AcpiNsGetType (Node) == ACPI_TYPE_LOCAL_METHOD_ALIAS) 142128212Snjl { 143167802Sjkim Node = ACPI_CAST_PTR (ACPI_NAMESPACE_NODE, Node->Object); 144128212Snjl } 145128212Snjl 146167802Sjkim /* Found matching entry */ 147167802Sjkim 14883174Smsmith ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 149123315Snjl "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n", 150167802Sjkim ACPI_CAST_PTR (char, &TargetName), 151167802Sjkim AcpiUtGetTypeName (Node->Type), 152167802Sjkim Node, AcpiUtGetNodeName (ParentNode), ParentNode)); 15367754Smsmith 154167802Sjkim *ReturnNode = Node; 15567754Smsmith return_ACPI_STATUS (AE_OK); 15667754Smsmith } 15767754Smsmith 15867754Smsmith /* Didn't match name, move on to the next peer object */ 15967754Smsmith 160167802Sjkim Node = Node->Peer; 16167754Smsmith } 16267754Smsmith 163107325Siwasaki /* Searched entire namespace level, not found */ 16467754Smsmith 165117521Snjl ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 166193267Sjkim "Name [%4.4s] (%s) not found in search in scope [%4.4s] " 167193267Sjkim "%p first child %p\n", 168167802Sjkim ACPI_CAST_PTR (char, &TargetName), AcpiUtGetTypeName (Type), 169167802Sjkim AcpiUtGetNodeName (ParentNode), ParentNode, ParentNode->Child)); 17067754Smsmith 17167754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 17267754Smsmith} 17367754Smsmith 17467754Smsmith 17567754Smsmith/******************************************************************************* 17667754Smsmith * 17767754Smsmith * FUNCTION: AcpiNsSearchParentTree 17867754Smsmith * 179151937Sjkim * PARAMETERS: TargetName - Ascii ACPI name to search for 180151937Sjkim * Node - Starting node where search will begin 181151937Sjkim * Type - Object type to match 182151937Sjkim * ReturnNode - Where the matched Node is returned 18367754Smsmith * 18467754Smsmith * RETURN: Status 18567754Smsmith * 18667754Smsmith * DESCRIPTION: Called when a name has not been found in the current namespace 187167802Sjkim * level. Before adding it or giving up, ACPI scope rules require 18867754Smsmith * searching enclosing scopes in cases identified by AcpiNsLocal(). 18967754Smsmith * 19067754Smsmith * "A name is located by finding the matching name in the current 19167754Smsmith * name space, and then in the parent name space. If the parent 19267754Smsmith * name space does not contain the name, the search continues 19367754Smsmith * recursively until either the name is found or the name space 194167802Sjkim * does not have a parent (the root of the name space). This 19567754Smsmith * indicates that the name is not found" (From ACPI Specification, 19667754Smsmith * section 5.3) 19767754Smsmith * 19867754Smsmith ******************************************************************************/ 19967754Smsmith 20069450Smsmithstatic ACPI_STATUS 20167754SmsmithAcpiNsSearchParentTree ( 20267754Smsmith UINT32 TargetName, 20367754Smsmith ACPI_NAMESPACE_NODE *Node, 20491116Smsmith ACPI_OBJECT_TYPE Type, 20567754Smsmith ACPI_NAMESPACE_NODE **ReturnNode) 20667754Smsmith{ 20767754Smsmith ACPI_STATUS Status; 20867754Smsmith ACPI_NAMESPACE_NODE *ParentNode; 20967754Smsmith 21067754Smsmith 211167802Sjkim ACPI_FUNCTION_TRACE (NsSearchParentTree); 21267754Smsmith 21367754Smsmith 214209746Sjkim ParentNode = Node->Parent; 21567754Smsmith 21667754Smsmith /* 217138287Smarks * If there is no parent (i.e., we are at the root) or type is "local", 218138287Smarks * we won't be searching the parent tree. 21967754Smsmith */ 220107325Siwasaki if (!ParentNode) 22167754Smsmith { 222107325Siwasaki ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "[%4.4s] has no parent\n", 223167802Sjkim ACPI_CAST_PTR (char, &TargetName))); 224138287Smarks return_ACPI_STATUS (AE_NOT_FOUND); 225107325Siwasaki } 22667754Smsmith 227107325Siwasaki if (AcpiNsLocal (Type)) 228107325Siwasaki { 229107325Siwasaki ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 230107325Siwasaki "[%4.4s] type [%s] must be local to this scope (no parent search)\n", 231167802Sjkim ACPI_CAST_PTR (char, &TargetName), AcpiUtGetTypeName (Type))); 23267754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 23367754Smsmith } 23467754Smsmith 23567754Smsmith /* Search the parent tree */ 23667754Smsmith 237138287Smarks ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 238138287Smarks "Searching parent [%4.4s] for [%4.4s]\n", 239167802Sjkim AcpiUtGetNodeName (ParentNode), ACPI_CAST_PTR (char, &TargetName))); 24067754Smsmith 241193267Sjkim /* Search parents until target is found or we have backed up to the root */ 242193267Sjkim 24367754Smsmith while (ParentNode) 24467754Smsmith { 24591116Smsmith /* 246167802Sjkim * Search parent scope. Use TYPE_ANY because we don't care about the 24791116Smsmith * object type at this point, we only care about the existence of 248167802Sjkim * the actual name we are searching for. Typechecking comes later. 24987031Smsmith */ 250167802Sjkim Status = AcpiNsSearchOneScope ( 251306536Sjkim TargetName, ParentNode, ACPI_TYPE_ANY, ReturnNode); 25267754Smsmith if (ACPI_SUCCESS (Status)) 25367754Smsmith { 25467754Smsmith return_ACPI_STATUS (Status); 25567754Smsmith } 25667754Smsmith 257167802Sjkim /* Not found here, go up another level (until we reach the root) */ 258167802Sjkim 259209746Sjkim ParentNode = ParentNode->Parent; 26067754Smsmith } 26167754Smsmith 26267754Smsmith /* Not found in parent tree */ 26367754Smsmith 26467754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 26567754Smsmith} 26667754Smsmith 26767754Smsmith 26867754Smsmith/******************************************************************************* 26967754Smsmith * 27067754Smsmith * FUNCTION: AcpiNsSearchAndEnter 27167754Smsmith * 27267754Smsmith * PARAMETERS: TargetName - Ascii ACPI name to search for (4 chars) 27367754Smsmith * WalkState - Current state of the walk 274151937Sjkim * Node - Starting node where search will begin 275107325Siwasaki * InterpreterMode - Add names only in ACPI_MODE_LOAD_PASS_x. 27667754Smsmith * Otherwise,search only. 27767754Smsmith * Type - Object type to match 27867754Smsmith * Flags - Flags describing the search restrictions 279151937Sjkim * ReturnNode - Where the Node is returned 28067754Smsmith * 28167754Smsmith * RETURN: Status 28267754Smsmith * 283107325Siwasaki * DESCRIPTION: Search for a name segment in a single namespace level, 284167802Sjkim * optionally adding it if it is not found. If the passed 28567754Smsmith * Type is not Any and the type previously stored in the 28667754Smsmith * entry was Any (i.e. unknown), update the stored type. 28767754Smsmith * 288107325Siwasaki * In ACPI_IMODE_EXECUTE, search only. 28967754Smsmith * In other modes, search and add if not found. 29067754Smsmith * 29167754Smsmith ******************************************************************************/ 29267754Smsmith 29367754SmsmithACPI_STATUS 29467754SmsmithAcpiNsSearchAndEnter ( 29567754Smsmith UINT32 TargetName, 29667754Smsmith ACPI_WALK_STATE *WalkState, 29767754Smsmith ACPI_NAMESPACE_NODE *Node, 29891116Smsmith ACPI_INTERPRETER_MODE InterpreterMode, 29991116Smsmith ACPI_OBJECT_TYPE Type, 30067754Smsmith UINT32 Flags, 30167754Smsmith ACPI_NAMESPACE_NODE **ReturnNode) 30267754Smsmith{ 30367754Smsmith ACPI_STATUS Status; 30467754Smsmith ACPI_NAMESPACE_NODE *NewNode; 30567754Smsmith 30667754Smsmith 307167802Sjkim ACPI_FUNCTION_TRACE (NsSearchAndEnter); 30867754Smsmith 30967754Smsmith 31067754Smsmith /* Parameter validation */ 31167754Smsmith 31267754Smsmith if (!Node || !TargetName || !ReturnNode) 31367754Smsmith { 314167802Sjkim ACPI_ERROR ((AE_INFO, 315204773Sjkim "Null parameter: Node %p Name 0x%X ReturnNode %p", 31667754Smsmith Node, TargetName, ReturnNode)); 31767754Smsmith return_ACPI_STATUS (AE_BAD_PARAMETER); 31867754Smsmith } 31967754Smsmith 320167802Sjkim /* 321167802Sjkim * Name must consist of valid ACPI characters. We will repair the name if 322167802Sjkim * necessary because we don't want to abort because of this, but we want 323167802Sjkim * all namespace names to be printable. A warning message is appropriate. 324167802Sjkim * 325167802Sjkim * This issue came up because there are in fact machines that exhibit 326167802Sjkim * this problem, and we want to be able to enable ACPI support for them, 327167802Sjkim * even though there are a few bad names. 328167802Sjkim */ 329193267Sjkim AcpiUtRepairName (ACPI_CAST_PTR (char, &TargetName)); 330167802Sjkim 331107325Siwasaki /* Try to find the name in the namespace level specified by the caller */ 33267754Smsmith 33391116Smsmith *ReturnNode = ACPI_ENTRY_NOT_FOUND; 334167802Sjkim Status = AcpiNsSearchOneScope (TargetName, Node, Type, ReturnNode); 33567754Smsmith if (Status != AE_NOT_FOUND) 33667754Smsmith { 33767754Smsmith /* 33877424Smsmith * If we found it AND the request specifies that a find is an error, 33977424Smsmith * return the error 34071867Smsmith */ 341306536Sjkim if (Status == AE_OK) 34271867Smsmith { 343306536Sjkim /* The node was found in the namespace */ 344306536Sjkim 345306536Sjkim /* 346306536Sjkim * If the namespace override feature is enabled for this node, 347306536Sjkim * delete any existing attached sub-object and make the node 348306536Sjkim * look like a new node that is owned by the override table. 349306536Sjkim */ 350306536Sjkim if (Flags & ACPI_NS_OVERRIDE_IF_FOUND) 351306536Sjkim { 352306536Sjkim ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 353306536Sjkim "Namespace override: %4.4s pass %u type %X Owner %X\n", 354306536Sjkim ACPI_CAST_PTR(char, &TargetName), InterpreterMode, 355306536Sjkim (*ReturnNode)->Type, WalkState->OwnerId)); 356306536Sjkim 357306536Sjkim AcpiNsDeleteChildren (*ReturnNode); 358306536Sjkim if (AcpiGbl_RuntimeNamespaceOverride) 359306536Sjkim { 360306536Sjkim AcpiUtRemoveReference ((*ReturnNode)->Object); 361306536Sjkim (*ReturnNode)->Object = NULL; 362306536Sjkim (*ReturnNode)->OwnerId = WalkState->OwnerId; 363306536Sjkim } 364306536Sjkim else 365306536Sjkim { 366306536Sjkim AcpiNsRemoveNode (*ReturnNode); 367306536Sjkim *ReturnNode = ACPI_ENTRY_NOT_FOUND; 368306536Sjkim } 369306536Sjkim } 370306536Sjkim 371306536Sjkim /* Return an error if we don't expect to find the object */ 372306536Sjkim 373306536Sjkim else if (Flags & ACPI_NS_ERROR_IF_FOUND) 374306536Sjkim { 375306536Sjkim Status = AE_ALREADY_EXISTS; 376306536Sjkim } 37771867Smsmith } 37871867Smsmith 379193267Sjkim#ifdef ACPI_ASL_COMPILER 380193267Sjkim if (*ReturnNode && (*ReturnNode)->Type == ACPI_TYPE_ANY) 381193267Sjkim { 382193267Sjkim (*ReturnNode)->Flags |= ANOBJ_IS_EXTERNAL; 383193267Sjkim } 384193267Sjkim#endif 385193267Sjkim 386167802Sjkim /* Either found it or there was an error: finished either way */ 387167802Sjkim 38867754Smsmith return_ACPI_STATUS (Status); 38967754Smsmith } 39067754Smsmith 39167754Smsmith /* 392167802Sjkim * The name was not found. If we are NOT performing the first pass 393138287Smarks * (name entry) of loading the namespace, search the parent tree (all the 394138287Smarks * way to the root if necessary.) We don't want to perform the parent 395167802Sjkim * search when the namespace is actually being loaded. We want to perform 396138287Smarks * the search when namespace references are being resolved (load pass 2) 397138287Smarks * and during the execution phase. 39867754Smsmith */ 39991116Smsmith if ((InterpreterMode != ACPI_IMODE_LOAD_PASS1) && 40091116Smsmith (Flags & ACPI_NS_SEARCH_PARENT)) 40167754Smsmith { 40267754Smsmith /* 403138287Smarks * Not found at this level - search parent tree according to the 404138287Smarks * ACPI specification 40567754Smsmith */ 406138287Smarks Status = AcpiNsSearchParentTree (TargetName, Node, Type, ReturnNode); 40767754Smsmith if (ACPI_SUCCESS (Status)) 40867754Smsmith { 40967754Smsmith return_ACPI_STATUS (Status); 41067754Smsmith } 41167754Smsmith } 41267754Smsmith 413167802Sjkim /* In execute mode, just search, never add names. Exit now */ 414167802Sjkim 41591116Smsmith if (InterpreterMode == ACPI_IMODE_EXECUTE) 41667754Smsmith { 417138287Smarks ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, 418138287Smarks "%4.4s Not found in %p [Not adding]\n", 419167802Sjkim ACPI_CAST_PTR (char, &TargetName), Node)); 42067754Smsmith 42167754Smsmith return_ACPI_STATUS (AE_NOT_FOUND); 42267754Smsmith } 42367754Smsmith 42467754Smsmith /* Create the new named object */ 42567754Smsmith 42667754Smsmith NewNode = AcpiNsCreateNode (TargetName); 42767754Smsmith if (!NewNode) 42867754Smsmith { 42967754Smsmith return_ACPI_STATUS (AE_NO_MEMORY); 43067754Smsmith } 43167754Smsmith 432167802Sjkim#ifdef ACPI_ASL_COMPILER 433193267Sjkim 434193267Sjkim /* Node is an object defined by an External() statement */ 435193267Sjkim 436193267Sjkim if (Flags & ACPI_NS_EXTERNAL || 437193267Sjkim (WalkState && WalkState->Opcode == AML_SCOPE_OP)) 438167802Sjkim { 439167802Sjkim NewNode->Flags |= ANOBJ_IS_EXTERNAL; 440167802Sjkim } 441167802Sjkim#endif 442167802Sjkim 443167802Sjkim if (Flags & ACPI_NS_TEMPORARY) 444167802Sjkim { 445167802Sjkim NewNode->Flags |= ANOBJ_TEMPORARY; 446167802Sjkim } 447167802Sjkim 44867754Smsmith /* Install the new object into the parent's list of children */ 44967754Smsmith 45067754Smsmith AcpiNsInstallNode (WalkState, Node, NewNode, Type); 45167754Smsmith *ReturnNode = NewNode; 45267754Smsmith return_ACPI_STATUS (AE_OK); 45367754Smsmith} 454