xref: /freebsd/sys/contrib/dev/acpica/components/namespace/nssearch.c (revision ddd5b8e9b4d8957fce018c520657cdfa4ecffad3)
1 /*******************************************************************************
2  *
3  * Module Name: nssearch - Namespace search
4  *
5  ******************************************************************************/
6 
7 /*
8  * Copyright (C) 2000 - 2013, 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 <contrib/dev/acpica/include/acpi.h>
47 #include <contrib/dev/acpica/include/accommon.h>
48 #include <contrib/dev/acpica/include/acnamesp.h>
49 
50 #ifdef ACPI_ASL_COMPILER
51 #include <contrib/dev/acpica/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