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