ReactOS  0.4.15-dev-425-gc40b086
nssearch.c
Go to the documentation of this file.
1 /*******************************************************************************
2  *
3  * Module Name: nssearch - Namespace search
4  *
5  ******************************************************************************/
6 
7 /*
8  * Copyright (C) 2000 - 2020, 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 #include "acpi.h"
45 #include "accommon.h"
46 #include "acnamesp.h"
47 
48 #ifdef ACPI_ASL_COMPILER
49 #include "amlcode.h"
50 #endif
51 
52 #define _COMPONENT ACPI_NAMESPACE
53  ACPI_MODULE_NAME ("nssearch")
54 
55 /* Local prototypes */
56 
57 static ACPI_STATUS
62  ACPI_NAMESPACE_NODE **ReturnNode);
63 
64 
65 /*******************************************************************************
66  *
67  * FUNCTION: AcpiNsSearchOneScope
68  *
69  * PARAMETERS: TargetName - Ascii ACPI name to search for
70  * ParentNode - Starting node where search will begin
71  * Type - Object type to match
72  * ReturnNode - Where the matched Named obj is returned
73  *
74  * RETURN: Status
75  *
76  * DESCRIPTION: Search a single level of the namespace. Performs a
77  * simple search of the specified level, and does not add
78  * entries or search parents.
79  *
80  *
81  * Named object lists are built (and subsequently dumped) in the
82  * order in which the names are encountered during the namespace load;
83  *
84  * All namespace searching is linear in this implementation, but
85  * could be easily modified to support any improved search
86  * algorithm. However, the linear search was chosen for simplicity
87  * and because the trees are small and the other interpreter
88  * execution overhead is relatively high.
89  *
90  * Note: CPU execution analysis has shown that the AML interpreter spends
91  * a very small percentage of its time searching the namespace. Therefore,
92  * the linear search seems to be sufficient, as there would seem to be
93  * little value in improving the search.
94  *
95  ******************************************************************************/
96 
100  ACPI_NAMESPACE_NODE *ParentNode,
102  ACPI_NAMESPACE_NODE **ReturnNode)
103 {
105 
106 
107  ACPI_FUNCTION_TRACE (NsSearchOneScope);
108 
109 
110 #ifdef ACPI_DEBUG_OUTPUT
111  if (ACPI_LV_NAMES & AcpiDbgLevel)
112  {
113  char *ScopeName;
114 
115  ScopeName = AcpiNsGetNormalizedPathname (ParentNode, TRUE);
116  if (ScopeName)
117  {
119  "Searching %s (%p) For [%4.4s] (%s)\n",
120  ScopeName, ParentNode, ACPI_CAST_PTR (char, &TargetName),
122 
123  ACPI_FREE (ScopeName);
124  }
125  }
126 #endif
127 
128  /*
129  * Search for name at this namespace level, which is to say that we
130  * must search for the name among the children of this object
131  */
132  Node = ParentNode->Child;
133  while (Node)
134  {
135  /* Check for match against the name */
136 
137  if (Node->Name.Integer == TargetName)
138  {
139  /* Resolve a control method alias if any */
140 
142  {
144  }
145 
146  /* Found matching entry */
147 
149  "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n",
150  ACPI_CAST_PTR (char, &TargetName),
151  AcpiUtGetTypeName (Node->Type),
152  Node, AcpiUtGetNodeName (ParentNode), ParentNode));
153 
154  *ReturnNode = Node;
156  }
157 
158  /* Didn't match name, move on to the next peer object */
159 
160  Node = Node->Peer;
161  }
162 
163  /* Searched entire namespace level, not found */
164 
166  "Name [%4.4s] (%s) not found in search in scope [%4.4s] "
167  "%p first child %p\n",
169  AcpiUtGetNodeName (ParentNode), ParentNode, ParentNode->Child));
170 
172 }
173 
174 
175 /*******************************************************************************
176  *
177  * FUNCTION: AcpiNsSearchParentTree
178  *
179  * PARAMETERS: TargetName - Ascii ACPI name to search for
180  * Node - Starting node where search will begin
181  * Type - Object type to match
182  * ReturnNode - Where the matched Node is returned
183  *
184  * RETURN: Status
185  *
186  * DESCRIPTION: Called when a name has not been found in the current namespace
187  * level. Before adding it or giving up, ACPI scope rules require
188  * searching enclosing scopes in cases identified by AcpiNsLocal().
189  *
190  * "A name is located by finding the matching name in the current
191  * name space, and then in the parent name space. If the parent
192  * name space does not contain the name, the search continues
193  * recursively until either the name is found or the name space
194  * does not have a parent (the root of the name space). This
195  * indicates that the name is not found" (From ACPI Specification,
196  * section 5.3)
197  *
198  ******************************************************************************/
199 
200 static ACPI_STATUS
205  ACPI_NAMESPACE_NODE **ReturnNode)
206 {
208  ACPI_NAMESPACE_NODE *ParentNode;
209 
210 
211  ACPI_FUNCTION_TRACE (NsSearchParentTree);
212 
213 
214  ParentNode = Node->Parent;
215 
216  /*
217  * If there is no parent (i.e., we are at the root) or type is "local",
218  * we won't be searching the parent tree.
219  */
220  if (!ParentNode)
221  {
222  ACPI_DEBUG_PRINT ((ACPI_DB_NAMES, "[%4.4s] has no parent\n",
223  ACPI_CAST_PTR (char, &TargetName)));
225  }
226 
227  if (AcpiNsLocal (Type))
228  {
230  "[%4.4s] type [%s] must be local to this scope (no parent search)\n",
233  }
234 
235  /* Search the parent tree */
236 
238  "Searching parent [%4.4s] for [%4.4s]\n",
239  AcpiUtGetNodeName (ParentNode), ACPI_CAST_PTR (char, &TargetName)));
240 
241  /* Search parents until target is found or we have backed up to the root */
242 
243  while (ParentNode)
244  {
245  /*
246  * Search parent scope. Use TYPE_ANY because we don't care about the
247  * object type at this point, we only care about the existence of
248  * the actual name we are searching for. Typechecking comes later.
249  */
251  TargetName, ParentNode, ACPI_TYPE_ANY, ReturnNode);
252  if (ACPI_SUCCESS (Status))
253  {
255  }
256 
257  /* Not found here, go up another level (until we reach the root) */
258 
259  ParentNode = ParentNode->Parent;
260  }
261 
262  /* Not found in parent tree */
263 
265 }
266 
267 
268 /*******************************************************************************
269  *
270  * FUNCTION: AcpiNsSearchAndEnter
271  *
272  * PARAMETERS: TargetName - Ascii ACPI name to search for (4 chars)
273  * WalkState - Current state of the walk
274  * Node - Starting node where search will begin
275  * InterpreterMode - Add names only in ACPI_MODE_LOAD_PASS_x.
276  * Otherwise,search only.
277  * Type - Object type to match
278  * Flags - Flags describing the search restrictions
279  * ReturnNode - Where the Node is returned
280  *
281  * RETURN: Status
282  *
283  * DESCRIPTION: Search for a name segment in a single namespace level,
284  * optionally adding it if it is not found. If the passed
285  * Type is not Any and the type previously stored in the
286  * entry was Any (i.e. unknown), update the stored type.
287  *
288  * In ACPI_IMODE_EXECUTE, search only.
289  * In other modes, search and add if not found.
290  *
291  ******************************************************************************/
292 
296  ACPI_WALK_STATE *WalkState,
298  ACPI_INTERPRETER_MODE InterpreterMode,
300  UINT32 Flags,
301  ACPI_NAMESPACE_NODE **ReturnNode)
302 {
304  ACPI_NAMESPACE_NODE *NewNode;
305 
306 
307  ACPI_FUNCTION_TRACE (NsSearchAndEnter);
308 
309 
310  /* Parameter validation */
311 
312  if (!Node || !TargetName || !ReturnNode)
313  {
315  "Null parameter: Node %p Name 0x%X ReturnNode %p",
316  Node, TargetName, ReturnNode));
318  }
319 
320  /*
321  * Name must consist of valid ACPI characters. We will repair the name if
322  * necessary because we don't want to abort because of this, but we want
323  * all namespace names to be printable. A warning message is appropriate.
324  *
325  * This issue came up because there are in fact machines that exhibit
326  * this problem, and we want to be able to enable ACPI support for them,
327  * even though there are a few bad names.
328  */
330 
331  /* Try to find the name in the namespace level specified by the caller */
332 
333  *ReturnNode = ACPI_ENTRY_NOT_FOUND;
334  Status = AcpiNsSearchOneScope (TargetName, Node, Type, ReturnNode);
335  if (Status != AE_NOT_FOUND)
336  {
337  /*
338  * If we found it AND the request specifies that a find is an error,
339  * return the error
340  */
341  if (Status == AE_OK)
342  {
343  /* The node was found in the namespace */
344 
345  /*
346  * If the namespace override feature is enabled for this node,
347  * delete any existing attached sub-object and make the node
348  * look like a new node that is owned by the override table.
349  */
351  {
353  "Namespace override: %4.4s pass %u type %X Owner %X\n",
354  ACPI_CAST_PTR(char, &TargetName), InterpreterMode,
355  (*ReturnNode)->Type, WalkState->OwnerId));
356 
357  AcpiNsDeleteChildren (*ReturnNode);
358  if (AcpiGbl_RuntimeNamespaceOverride)
359  {
360  AcpiUtRemoveReference ((*ReturnNode)->Object);
361  (*ReturnNode)->Object = NULL;
362  (*ReturnNode)->OwnerId = WalkState->OwnerId;
363  }
364  else
365  {
366  AcpiNsRemoveNode (*ReturnNode);
367  *ReturnNode = ACPI_ENTRY_NOT_FOUND;
368  }
369  }
370 
371  /* Return an error if we don't expect to find the object */
372 
373  else if (Flags & ACPI_NS_ERROR_IF_FOUND)
374  {
376  }
377  }
378 
379 #ifdef ACPI_ASL_COMPILER
380  if (*ReturnNode && (*ReturnNode)->Type == ACPI_TYPE_ANY)
381  {
382  (*ReturnNode)->Flags |= ANOBJ_IS_EXTERNAL;
383  }
384 #endif
385 
386  /* Either found it or there was an error: finished either way */
387 
389  }
390 
391  /*
392  * The name was not found. If we are NOT performing the first pass
393  * (name entry) of loading the namespace, search the parent tree (all the
394  * way to the root if necessary.) We don't want to perform the parent
395  * search when the namespace is actually being loaded. We want to perform
396  * the search when namespace references are being resolved (load pass 2)
397  * and during the execution phase.
398  */
399  if ((InterpreterMode != ACPI_IMODE_LOAD_PASS1) &&
401  {
402  /*
403  * Not found at this level - search parent tree according to the
404  * ACPI specification
405  */
407  if (ACPI_SUCCESS (Status))
408  {
410  }
411  }
412 
413  /* In execute mode, just search, never add names. Exit now */
414 
415  if (InterpreterMode == ACPI_IMODE_EXECUTE)
416  {
418  "%4.4s Not found in %p [Not adding]\n",
419  ACPI_CAST_PTR (char, &TargetName), Node));
420 
422  }
423 
424  /* Create the new named object */
425 
426  NewNode = AcpiNsCreateNode (TargetName);
427  if (!NewNode)
428  {
430  }
431 
432 #ifdef ACPI_ASL_COMPILER
433 
434  /* Node is an object defined by an External() statement */
435 
436  if (Flags & ACPI_NS_EXTERNAL ||
437  (WalkState && WalkState->Opcode == AML_SCOPE_OP))
438  {
439  NewNode->Flags |= ANOBJ_IS_EXTERNAL;
440  }
441 #endif
442 
443  if (Flags & ACPI_NS_TEMPORARY)
444  {
445  NewNode->Flags |= ANOBJ_TEMPORARY;
446  }
447 
448  /* Install the new object into the parent's list of children */
449 
450  AcpiNsInstallNode (WalkState, Node, NewNode, Type);
451  *ReturnNode = NewNode;
453 }
void AcpiNsRemoveNode(ACPI_NAMESPACE_NODE *Node)
Definition: nsalloc.c:188
#define ACPI_NS_TEMPORARY
Definition: acnamesp.h:69
#define ACPI_NS_SEARCH_PARENT
Definition: acnamesp.h:63
#define ACPI_FREE(a)
Definition: actypes.h:386
UINT32 AcpiNsLocal(ACPI_OBJECT_TYPE Type)
Definition: nsutils.c:150
ACPI_INTERPRETER_MODE
Definition: aclocal.h:165
#define TRUE
Definition: types.h:120
#define ACPI_SUCCESS(a)
Definition: acexcep.h:94
void AcpiNsDeleteChildren(ACPI_NAMESPACE_NODE *Parent)
Definition: nsalloc.c:341
Type
Definition: Type.h:6
#define AE_NO_MEMORY
Definition: acexcep.h:112
#define AE_BAD_PARAMETER
Definition: acexcep.h:151
#define ACPI_LV_NAMES
Definition: acoutput.h:102
void AcpiUtRepairName(char *Name)
Definition: utstring.c:183
#define ACPI_NS_ERROR_IF_FOUND
Definition: acnamesp.h:66
ACPI_OWNER_ID OwnerId
Definition: acstruct.h:82
UINT32 ACPI_STATUS
Definition: actypes.h:460
struct acpi_namespace_node * Parent
Definition: aclocal.h:192
ACPI_OBJECT_TYPE AcpiNsGetType(ACPI_NAMESPACE_NODE *Node)
Definition: nsutils.c:120
ACPI_NAMESPACE_NODE * AcpiNsCreateNode(UINT32 Name)
Definition: nsalloc.c:66
static ACPI_STATUS AcpiNsSearchParentTree(UINT32 TargetName, ACPI_NAMESPACE_NODE *Node, ACPI_OBJECT_TYPE Type, ACPI_NAMESPACE_NODE **ReturnNode)
Definition: nssearch.c:201
_Must_inspect_result_ _In_ ULONG Flags
Definition: wsk.h:170
unsigned int UINT32
union node Node
Definition: types.h:1255
#define ACPI_MODULE_NAME(Name)
Definition: acoutput.h:216
smooth NULL
Definition: ftsmooth.c:416
#define AE_INFO
Definition: acoutput.h:230
#define ACPI_TYPE_LOCAL_METHOD_ALIAS
Definition: actypes.h:713
UINT32 ACPI_OBJECT_TYPE
Definition: actypes.h:677
#define AE_ALREADY_EXISTS
Definition: acexcep.h:115
#define ACPI_DEBUG_PRINT(pl)
Definition: acoutput.h:475
ACPI_STATUS AcpiNsSearchOneScope(UINT32 TargetName, ACPI_NAMESPACE_NODE *ParentNode, ACPI_OBJECT_TYPE Type, ACPI_NAMESPACE_NODE **ReturnNode)
Definition: nssearch.c:98
#define ACPI_ENTRY_NOT_FOUND
Definition: aclocal.h:154
#define AML_SCOPE_OP
Definition: amlcode.h:60
#define AE_NOT_FOUND
Definition: acexcep.h:113
#define ACPI_TYPE_ANY
Definition: actypes.h:679
WCHAR TargetName[256]
Definition: arping.c:27
void AcpiNsInstallNode(ACPI_WALK_STATE *WalkState, ACPI_NAMESPACE_NODE *ParentNode, ACPI_NAMESPACE_NODE *Node, ACPI_OBJECT_TYPE Type)
Definition: nsalloc.c:255
Status
Definition: gdiplustypes.h:24
char * AcpiNsGetNormalizedPathname(ACPI_NAMESPACE_NODE *Node, BOOLEAN NoTrailing)
Definition: nsnames.c:367
#define return_ACPI_STATUS(s)
Definition: acoutput.h:496
ACPI_STATUS AcpiNsSearchAndEnter(UINT32 TargetName, ACPI_WALK_STATE *WalkState, ACPI_NAMESPACE_NODE *Node, ACPI_INTERPRETER_MODE InterpreterMode, ACPI_OBJECT_TYPE Type, UINT32 Flags, ACPI_NAMESPACE_NODE **ReturnNode)
Definition: nssearch.c:294
#define ACPI_FUNCTION_TRACE(a)
Definition: acoutput.h:480
#define ACPI_NS_EXTERNAL
Definition: acnamesp.h:68
#define ACPI_DB_NAMES
Definition: acoutput.h:166
#define ACPI_NS_OVERRIDE_IF_FOUND
Definition: acnamesp.h:70
void AcpiUtRemoveReference(ACPI_OPERAND_OBJECT *Object)
Definition: utdelete.c:785
const char * AcpiUtGetTypeName(ACPI_OBJECT_TYPE Type)
Definition: utdecode.c:250
#define ACPI_ERROR(plist)
Definition: acoutput.h:240
const char * AcpiUtGetNodeName(void *Object)
Definition: utdecode.c:306
UINT16 Opcode
Definition: acstruct.h:78
#define ACPI_CAST_PTR(t, p)
Definition: actypes.h:544
#define AE_OK
Definition: acexcep.h:97
Definition: dlist.c:348
#define ANOBJ_TEMPORARY
Definition: aclocal.h:216
#define ANOBJ_IS_EXTERNAL
Definition: aclocal.h:224