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 | 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 | struct acpi_namespace_node *node; |
65 | |
66 | 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(node: 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 | node = parent_node->child; |
90 | while (node) { |
91 | |
92 | /* Check for match against the name */ |
93 | |
94 | if (node->name.integer == target_name) { |
95 | |
96 | /* Resolve a control method alias if any */ |
97 | |
98 | if (acpi_ns_get_type(node) == |
99 | ACPI_TYPE_LOCAL_METHOD_ALIAS) { |
100 | 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 | parent_node)); |
114 | |
115 | *return_node = node; |
116 | return_ACPI_STATUS(AE_OK); |
117 | } |
118 | |
119 | /* Didn't match name, move on to the next peer object */ |
120 | |
121 | 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 | 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 | acpi_status status; |
259 | struct acpi_namespace_node *new_node; |
260 | |
261 | ACPI_FUNCTION_TRACE(ns_search_and_enter); |
262 | |
263 | /* Parameter validation */ |
264 | |
265 | if (!node || !target_name || !return_node) { |
266 | ACPI_ERROR((AE_INFO, |
267 | "Null parameter: Node %p Name 0x%X ReturnNode %p" , |
268 | node, target_name, return_node)); |
269 | 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 | 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 | *return_node = ACPI_ENTRY_NOT_FOUND; |
286 | status = acpi_ns_search_one_scope(target_name, parent_node: node, type, return_node); |
287 | 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 | 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 | 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 | walk_state->owner_id)); |
309 | |
310 | acpi_ns_delete_children(parent: *return_node); |
311 | if (acpi_gbl_runtime_namespace_override) { |
312 | acpi_ut_remove_reference(object: (*return_node)->object); |
313 | (*return_node)->object = NULL; |
314 | (*return_node)->owner_id = |
315 | walk_state->owner_id; |
316 | } else { |
317 | acpi_ns_remove_node(node: *return_node); |
318 | *return_node = ACPI_ENTRY_NOT_FOUND; |
319 | } |
320 | } |
321 | |
322 | /* Return an error if we don't expect to find the object */ |
323 | |
324 | else if (flags & ACPI_NS_ERROR_IF_FOUND) { |
325 | 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 | 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 | if ((interpreter_mode != ACPI_IMODE_LOAD_PASS1) && |
348 | (flags & ACPI_NS_SEARCH_PARENT)) { |
349 | /* |
350 | * Not found at this level - search parent tree according to the |
351 | * ACPI specification |
352 | */ |
353 | status = |
354 | acpi_ns_search_parent_tree(target_name, node, type, |
355 | return_node); |
356 | 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 | 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 | new_node = acpi_ns_create_node(name: target_name); |
374 | 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 | if (flags & ACPI_NS_TEMPORARY) { |
388 | new_node->flags |= ANOBJ_TEMPORARY; |
389 | } |
390 | |
391 | /* Install the new object into the parent's list of children */ |
392 | |
393 | acpi_ns_install_node(walk_state, parent_node: node, node: new_node, type); |
394 | *return_node = new_node; |
395 | return_ACPI_STATUS(AE_OK); |
396 | } |
397 | |