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
17ACPI_MODULE_NAME("nssearch")
18
19/* Local prototypes */
20static acpi_status
21acpi_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
58acpi_status
59acpi_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(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
162static acpi_status
163acpi_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
250acpi_status
251acpi_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, 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(*return_node);
311				if (acpi_gbl_runtime_namespace_override) {
312					acpi_ut_remove_reference((*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(*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(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, node, new_node, type);
394	*return_node = new_node;
395	return_ACPI_STATUS(AE_OK);
396}
397