Branch data Line data Source code
1 : : // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0
2 : : /*******************************************************************************
3 : : *
4 : : * Module Name: nssearch - Namespace search
5 : : *
6 : : ******************************************************************************/
7 : :
8 : : #include <acpi/acpi.h>
9 : : #include "accommon.h"
10 : : #include "acnamesp.h"
11 : :
12 : : #ifdef ACPI_ASL_COMPILER
13 : : #include "amlcode.h"
14 : : #endif
15 : :
16 : : #define _COMPONENT ACPI_NAMESPACE
17 : : ACPI_MODULE_NAME("nssearch")
18 : :
19 : : /* Local prototypes */
20 : : static acpi_status
21 : : acpi_ns_search_parent_tree(u32 target_name,
22 : : struct acpi_namespace_node *node,
23 : : acpi_object_type type,
24 : : struct acpi_namespace_node **return_node);
25 : :
26 : : /*******************************************************************************
27 : : *
28 : : * FUNCTION: acpi_ns_search_one_scope
29 : : *
30 : : * PARAMETERS: target_name - Ascii ACPI name to search for
31 : : * parent_node - Starting node where search will begin
32 : : * type - Object type to match
33 : : * return_node - Where the matched Named obj is returned
34 : : *
35 : : * RETURN: Status
36 : : *
37 : : * DESCRIPTION: Search a single level of the namespace. Performs a
38 : : * simple search of the specified level, and does not add
39 : : * entries or search parents.
40 : : *
41 : : *
42 : : * Named object lists are built (and subsequently dumped) in the
43 : : * order in which the names are encountered during the namespace load;
44 : : *
45 : : * All namespace searching is linear in this implementation, but
46 : : * could be easily modified to support any improved search
47 : : * algorithm. However, the linear search was chosen for simplicity
48 : : * and because the trees are small and the other interpreter
49 : : * execution overhead is relatively high.
50 : : *
51 : : * Note: CPU execution analysis has shown that the AML interpreter spends
52 : : * a very small percentage of its time searching the namespace. Therefore,
53 : : * the linear search seems to be sufficient, as there would seem to be
54 : : * little value in improving the search.
55 : : *
56 : : ******************************************************************************/
57 : :
58 : : acpi_status
59 : 97916 : acpi_ns_search_one_scope(u32 target_name,
60 : : struct acpi_namespace_node *parent_node,
61 : : acpi_object_type type,
62 : : struct acpi_namespace_node **return_node)
63 : : {
64 : 97916 : struct acpi_namespace_node *node;
65 : :
66 : 97916 : ACPI_FUNCTION_TRACE(ns_search_one_scope);
67 : :
68 : : #ifdef ACPI_DEBUG_OUTPUT
69 : : if (ACPI_LV_NAMES & acpi_dbg_level) {
70 : : char *scope_name;
71 : :
72 : : scope_name = acpi_ns_get_normalized_pathname(parent_node, TRUE);
73 : : if (scope_name) {
74 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
75 : : "Searching %s (%p) For [%4.4s] (%s)\n",
76 : : scope_name, parent_node,
77 : : ACPI_CAST_PTR(char, &target_name),
78 : : acpi_ut_get_type_name(type)));
79 : :
80 : : ACPI_FREE(scope_name);
81 : : }
82 : : }
83 : : #endif
84 : :
85 : : /*
86 : : * Search for name at this namespace level, which is to say that we
87 : : * must search for the name among the children of this object
88 : : */
89 : 97916 : node = parent_node->child;
90 [ + + ]: 1032681 : while (node) {
91 : :
92 : : /* Check for match against the name */
93 : :
94 [ + + ]: 961220 : if (node->name.integer == target_name) {
95 : :
96 : : /* Resolve a control method alias if any */
97 : :
98 [ - + ]: 26455 : if (acpi_ns_get_type(node) ==
99 : : ACPI_TYPE_LOCAL_METHOD_ALIAS) {
100 : 0 : node =
101 : : ACPI_CAST_PTR(struct acpi_namespace_node,
102 : : node->object);
103 : : }
104 : :
105 : : /* Found matching entry */
106 : :
107 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
108 : : "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n",
109 : : ACPI_CAST_PTR(char, &target_name),
110 : : acpi_ut_get_type_name(node->type),
111 : : node,
112 : : acpi_ut_get_node_name(parent_node),
113 : 26455 : parent_node));
114 : :
115 : 26455 : *return_node = node;
116 : 26455 : return_ACPI_STATUS(AE_OK);
117 : : }
118 : :
119 : : /* Didn't match name, move on to the next peer object */
120 : :
121 : 934765 : node = node->peer;
122 : : }
123 : :
124 : : /* Searched entire namespace level, not found */
125 : :
126 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
127 : : "Name [%4.4s] (%s) not found in search in scope [%4.4s] "
128 : : "%p first child %p\n",
129 : : ACPI_CAST_PTR(char, &target_name),
130 : : acpi_ut_get_type_name(type),
131 : : acpi_ut_get_node_name(parent_node), parent_node,
132 : : parent_node->child));
133 : :
134 : : return_ACPI_STATUS(AE_NOT_FOUND);
135 : : }
136 : :
137 : : /*******************************************************************************
138 : : *
139 : : * FUNCTION: acpi_ns_search_parent_tree
140 : : *
141 : : * PARAMETERS: target_name - Ascii ACPI name to search for
142 : : * node - Starting node where search will begin
143 : : * type - Object type to match
144 : : * return_node - Where the matched Node is returned
145 : : *
146 : : * RETURN: Status
147 : : *
148 : : * DESCRIPTION: Called when a name has not been found in the current namespace
149 : : * level. Before adding it or giving up, ACPI scope rules require
150 : : * searching enclosing scopes in cases identified by acpi_ns_local().
151 : : *
152 : : * "A name is located by finding the matching name in the current
153 : : * name space, and then in the parent name space. If the parent
154 : : * name space does not contain the name, the search continues
155 : : * recursively until either the name is found or the name space
156 : : * does not have a parent (the root of the name space). This
157 : : * indicates that the name is not found" (From ACPI Specification,
158 : : * section 5.3)
159 : : *
160 : : ******************************************************************************/
161 : :
162 : : static acpi_status
163 : : acpi_ns_search_parent_tree(u32 target_name,
164 : : struct acpi_namespace_node *node,
165 : : acpi_object_type type,
166 : : struct acpi_namespace_node **return_node)
167 : : {
168 : : acpi_status status;
169 : : struct acpi_namespace_node *parent_node;
170 : :
171 : : ACPI_FUNCTION_TRACE(ns_search_parent_tree);
172 : :
173 : : parent_node = node->parent;
174 : :
175 : : /*
176 : : * If there is no parent (i.e., we are at the root) or type is "local",
177 : : * we won't be searching the parent tree.
178 : : */
179 : : if (!parent_node) {
180 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES, "[%4.4s] has no parent\n",
181 : : ACPI_CAST_PTR(char, &target_name)));
182 : : return_ACPI_STATUS(AE_NOT_FOUND);
183 : : }
184 : :
185 : : if (acpi_ns_local(type)) {
186 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
187 : : "[%4.4s] type [%s] must be local to this scope (no parent search)\n",
188 : : ACPI_CAST_PTR(char, &target_name),
189 : : acpi_ut_get_type_name(type)));
190 : : return_ACPI_STATUS(AE_NOT_FOUND);
191 : : }
192 : :
193 : : /* Search the parent tree */
194 : :
195 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
196 : : "Searching parent [%4.4s] for [%4.4s]\n",
197 : : acpi_ut_get_node_name(parent_node),
198 : : ACPI_CAST_PTR(char, &target_name)));
199 : :
200 : : /* Search parents until target is found or we have backed up to the root */
201 : :
202 : : while (parent_node) {
203 : : /*
204 : : * Search parent scope. Use TYPE_ANY because we don't care about the
205 : : * object type at this point, we only care about the existence of
206 : : * the actual name we are searching for. Typechecking comes later.
207 : : */
208 : : status =
209 : : acpi_ns_search_one_scope(target_name, parent_node,
210 : : ACPI_TYPE_ANY, return_node);
211 : : if (ACPI_SUCCESS(status)) {
212 : : return_ACPI_STATUS(status);
213 : : }
214 : :
215 : : /* Not found here, go up another level (until we reach the root) */
216 : :
217 : : parent_node = parent_node->parent;
218 : : }
219 : :
220 : : /* Not found in parent tree */
221 : :
222 : : return_ACPI_STATUS(AE_NOT_FOUND);
223 : : }
224 : :
225 : : /*******************************************************************************
226 : : *
227 : : * FUNCTION: acpi_ns_search_and_enter
228 : : *
229 : : * PARAMETERS: target_name - Ascii ACPI name to search for (4 chars)
230 : : * walk_state - Current state of the walk
231 : : * node - Starting node where search will begin
232 : : * interpreter_mode - Add names only in ACPI_MODE_LOAD_PASS_x.
233 : : * Otherwise,search only.
234 : : * type - Object type to match
235 : : * flags - Flags describing the search restrictions
236 : : * return_node - Where the Node is returned
237 : : *
238 : : * RETURN: Status
239 : : *
240 : : * DESCRIPTION: Search for a name segment in a single namespace level,
241 : : * optionally adding it if it is not found. If the passed
242 : : * Type is not Any and the type previously stored in the
243 : : * entry was Any (i.e. unknown), update the stored type.
244 : : *
245 : : * In ACPI_IMODE_EXECUTE, search only.
246 : : * In other modes, search and add if not found.
247 : : *
248 : : ******************************************************************************/
249 : :
250 : : acpi_status
251 : 77753 : acpi_ns_search_and_enter(u32 target_name,
252 : : struct acpi_walk_state *walk_state,
253 : : struct acpi_namespace_node *node,
254 : : acpi_interpreter_mode interpreter_mode,
255 : : acpi_object_type type,
256 : : u32 flags, struct acpi_namespace_node **return_node)
257 : : {
258 : 77753 : acpi_status status;
259 : 77753 : struct acpi_namespace_node *new_node;
260 : :
261 : 77753 : ACPI_FUNCTION_TRACE(ns_search_and_enter);
262 : :
263 : : /* Parameter validation */
264 : :
265 [ + - - + ]: 77753 : if (!node || !target_name || !return_node) {
266 : 0 : ACPI_ERROR((AE_INFO,
267 : : "Null parameter: Node %p Name 0x%X ReturnNode %p",
268 : : node, target_name, return_node));
269 : 0 : return_ACPI_STATUS(AE_BAD_PARAMETER);
270 : : }
271 : :
272 : : /*
273 : : * Name must consist of valid ACPI characters. We will repair the name if
274 : : * necessary because we don't want to abort because of this, but we want
275 : : * all namespace names to be printable. A warning message is appropriate.
276 : : *
277 : : * This issue came up because there are in fact machines that exhibit
278 : : * this problem, and we want to be able to enable ACPI support for them,
279 : : * even though there are a few bad names.
280 : : */
281 : 77753 : acpi_ut_repair_name(ACPI_CAST_PTR(char, &target_name));
282 : :
283 : : /* Try to find the name in the namespace level specified by the caller */
284 : :
285 : 77753 : *return_node = ACPI_ENTRY_NOT_FOUND;
286 : 77753 : status = acpi_ns_search_one_scope(target_name, node, type, return_node);
287 [ + + ]: 77753 : if (status != AE_NOT_FOUND) {
288 : : /*
289 : : * If we found it AND the request specifies that a find is an error,
290 : : * return the error
291 : : */
292 [ + - ]: 15795 : if (status == AE_OK) {
293 : :
294 : : /* The node was found in the namespace */
295 : :
296 : : /*
297 : : * If the namespace override feature is enabled for this node,
298 : : * delete any existing attached sub-object and make the node
299 : : * look like a new node that is owned by the override table.
300 : : */
301 [ - + ]: 15795 : if (flags & ACPI_NS_OVERRIDE_IF_FOUND) {
302 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
303 : : "Namespace override: %4.4s pass %u type %X Owner %X\n",
304 : : ACPI_CAST_PTR(char,
305 : : &target_name),
306 : : interpreter_mode,
307 : : (*return_node)->type,
308 : 0 : walk_state->owner_id));
309 : :
310 : 0 : acpi_ns_delete_children(*return_node);
311 [ # # ]: 0 : if (acpi_gbl_runtime_namespace_override) {
312 : 0 : acpi_ut_remove_reference((*return_node)->object);
313 : 0 : (*return_node)->object = NULL;
314 : 0 : (*return_node)->owner_id =
315 : 0 : walk_state->owner_id;
316 : : } else {
317 : 0 : acpi_ns_remove_node(*return_node);
318 : 0 : *return_node = ACPI_ENTRY_NOT_FOUND;
319 : : }
320 : : }
321 : :
322 : : /* Return an error if we don't expect to find the object */
323 : :
324 [ - + ]: 15795 : else if (flags & ACPI_NS_ERROR_IF_FOUND) {
325 : 0 : status = AE_ALREADY_EXISTS;
326 : : }
327 : : }
328 : : #ifdef ACPI_ASL_COMPILER
329 : : if (*return_node && (*return_node)->type == ACPI_TYPE_ANY) {
330 : : (*return_node)->flags |= ANOBJ_IS_EXTERNAL;
331 : : }
332 : : #endif
333 : :
334 : : /* Either found it or there was an error: finished either way */
335 : :
336 : 15795 : return_ACPI_STATUS(status);
337 : : }
338 : :
339 : : /*
340 : : * The name was not found. If we are NOT performing the first pass
341 : : * (name entry) of loading the namespace, search the parent tree (all the
342 : : * way to the root if necessary.) We don't want to perform the parent
343 : : * search when the namespace is actually being loaded. We want to perform
344 : : * the search when namespace references are being resolved (load pass 2)
345 : : * and during the execution phase.
346 : : */
347 [ + + ]: 61958 : if ((interpreter_mode != ACPI_IMODE_LOAD_PASS1) &&
348 [ + + ]: 61555 : (flags & ACPI_NS_SEARCH_PARENT)) {
349 : : /*
350 : : * Not found at this level - search parent tree according to the
351 : : * ACPI specification
352 : : */
353 : 10660 : status =
354 : 10660 : acpi_ns_search_parent_tree(target_name, node, type,
355 : : return_node);
356 [ - + ]: 10660 : if (ACPI_SUCCESS(status)) {
357 : : return_ACPI_STATUS(status);
358 : : }
359 : : }
360 : :
361 : : /* In execute mode, just search, never add names. Exit now */
362 : :
363 [ + + ]: 51298 : if (interpreter_mode == ACPI_IMODE_EXECUTE) {
364 : : ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
365 : : "%4.4s Not found in %p [Not adding]\n",
366 : : ACPI_CAST_PTR(char, &target_name), node));
367 : :
368 : : return_ACPI_STATUS(AE_NOT_FOUND);
369 : : }
370 : :
371 : : /* Create the new named object */
372 : :
373 : 3965 : new_node = acpi_ns_create_node(target_name);
374 [ + - ]: 3965 : if (!new_node) {
375 : : return_ACPI_STATUS(AE_NO_MEMORY);
376 : : }
377 : : #ifdef ACPI_ASL_COMPILER
378 : :
379 : : /* Node is an object defined by an External() statement */
380 : :
381 : : if (flags & ACPI_NS_EXTERNAL ||
382 : : (walk_state && walk_state->opcode == AML_SCOPE_OP)) {
383 : : new_node->flags |= ANOBJ_IS_EXTERNAL;
384 : : }
385 : : #endif
386 : :
387 [ + + ]: 3965 : if (flags & ACPI_NS_TEMPORARY) {
388 : 247 : new_node->flags |= ANOBJ_TEMPORARY;
389 : : }
390 : :
391 : : /* Install the new object into the parent's list of children */
392 : :
393 : 3965 : acpi_ns_install_node(walk_state, node, new_node, type);
394 : 3965 : *return_node = new_node;
395 : 3965 : return_ACPI_STATUS(AE_OK);
396 : : }
|
