blob: c929f45071c0e10caf7cdfd4bb115f81f92faa9a [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*******************************************************************************
2 *
3 * Module Name: nssearch - Namespace search
4 *
5 ******************************************************************************/
6
7/*
Bob Moore4a90c7e2006-01-13 16:22:00 -05008 * Copyright (C) 2000 - 2006, R. Byron Moore
Linus Torvalds1da177e2005-04-16 15:20:36 -07009 * 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
Linus Torvalds1da177e2005-04-16 15:20:36 -070044#include <acpi/acpi.h>
45#include <acpi/acnamesp.h>
46
Linus Torvalds1da177e2005-04-16 15:20:36 -070047#define _COMPONENT ACPI_NAMESPACE
Len Brown4be44fc2005-08-05 00:44:28 -040048ACPI_MODULE_NAME("nssearch")
Linus Torvalds1da177e2005-04-16 15:20:36 -070049
Robert Moore44f6c012005-04-18 22:49:35 -040050/* Local prototypes */
Robert Moore44f6c012005-04-18 22:49:35 -040051static acpi_status
Len Brown4be44fc2005-08-05 00:44:28 -040052acpi_ns_search_parent_tree(u32 target_name,
53 struct acpi_namespace_node *node,
54 acpi_object_type type,
55 struct acpi_namespace_node **return_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -070056
57/*******************************************************************************
58 *
59 * FUNCTION: acpi_ns_search_node
60 *
Robert Moore44f6c012005-04-18 22:49:35 -040061 * PARAMETERS: target_name - Ascii ACPI name to search for
62 * Node - Starting node where search will begin
63 * Type - Object type to match
64 * return_node - Where the matched Named obj is returned
Linus Torvalds1da177e2005-04-16 15:20:36 -070065 *
66 * RETURN: Status
67 *
68 * DESCRIPTION: Search a single level of the namespace. Performs a
69 * simple search of the specified level, and does not add
70 * entries or search parents.
71 *
72 *
73 * Named object lists are built (and subsequently dumped) in the
74 * order in which the names are encountered during the namespace load;
75 *
76 * All namespace searching is linear in this implementation, but
77 * could be easily modified to support any improved search
78 * algorithm. However, the linear search was chosen for simplicity
79 * and because the trees are small and the other interpreter
80 * execution overhead is relatively high.
81 *
82 ******************************************************************************/
83
84acpi_status
Len Brown4be44fc2005-08-05 00:44:28 -040085acpi_ns_search_node(u32 target_name,
86 struct acpi_namespace_node *node,
87 acpi_object_type type,
88 struct acpi_namespace_node **return_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -070089{
Len Brown4be44fc2005-08-05 00:44:28 -040090 struct acpi_namespace_node *next_node;
Linus Torvalds1da177e2005-04-16 15:20:36 -070091
Len Brown4be44fc2005-08-05 00:44:28 -040092 ACPI_FUNCTION_TRACE("ns_search_node");
Linus Torvalds1da177e2005-04-16 15:20:36 -070093
94#ifdef ACPI_DEBUG_OUTPUT
95 if (ACPI_LV_NAMES & acpi_dbg_level) {
Len Brown4be44fc2005-08-05 00:44:28 -040096 char *scope_name;
Linus Torvalds1da177e2005-04-16 15:20:36 -070097
Len Brown4be44fc2005-08-05 00:44:28 -040098 scope_name = acpi_ns_get_external_pathname(node);
Linus Torvalds1da177e2005-04-16 15:20:36 -070099 if (scope_name) {
Len Brown4be44fc2005-08-05 00:44:28 -0400100 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
101 "Searching %s (%p) For [%4.4s] (%s)\n",
Bob Mooredefba1d2005-12-16 17:05:00 -0500102 scope_name, node, ACPI_CAST_PTR(char,
103 &target_name),
Len Brown4be44fc2005-08-05 00:44:28 -0400104 acpi_ut_get_type_name(type)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700105
Bob Moore83135242006-10-03 00:00:00 -0400106 ACPI_FREE(scope_name);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700107 }
108 }
109#endif
110
111 /*
112 * Search for name at this namespace level, which is to say that we
113 * must search for the name among the children of this object
114 */
115 next_node = node->child;
116 while (next_node) {
Bob Moore52fc0b02006-10-02 00:00:00 -0400117
Linus Torvalds1da177e2005-04-16 15:20:36 -0700118 /* Check for match against the name */
119
120 if (next_node->name.integer == target_name) {
Bob Moore52fc0b02006-10-02 00:00:00 -0400121
Linus Torvalds1da177e2005-04-16 15:20:36 -0700122 /* Resolve a control method alias if any */
123
Len Brown4be44fc2005-08-05 00:44:28 -0400124 if (acpi_ns_get_type(next_node) ==
125 ACPI_TYPE_LOCAL_METHOD_ALIAS) {
126 next_node =
127 ACPI_CAST_PTR(struct acpi_namespace_node,
128 next_node->object);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129 }
130
131 /*
132 * Found matching entry.
133 */
Len Brown4be44fc2005-08-05 00:44:28 -0400134 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
135 "Name [%4.4s] (%s) %p found in scope [%4.4s] %p\n",
Bob Mooredefba1d2005-12-16 17:05:00 -0500136 ACPI_CAST_PTR(char, &target_name),
Len Brown4be44fc2005-08-05 00:44:28 -0400137 acpi_ut_get_type_name(next_node->
138 type),
139 next_node,
140 acpi_ut_get_node_name(node), node));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141
142 *return_node = next_node;
Len Brown4be44fc2005-08-05 00:44:28 -0400143 return_ACPI_STATUS(AE_OK);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144 }
145
146 /*
147 * The last entry in the list points back to the parent,
148 * so a flag is used to indicate the end-of-list
149 */
150 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
Bob Moore52fc0b02006-10-02 00:00:00 -0400151
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152 /* Searched entire list, we are done */
153
154 break;
155 }
156
157 /* Didn't match name, move on to the next peer object */
158
159 next_node = next_node->peer;
160 }
161
162 /* Searched entire namespace level, not found */
163
Len Brown4be44fc2005-08-05 00:44:28 -0400164 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
165 "Name [%4.4s] (%s) not found in search in scope [%4.4s] %p first child %p\n",
Bob Mooredefba1d2005-12-16 17:05:00 -0500166 ACPI_CAST_PTR(char, &target_name),
167 acpi_ut_get_type_name(type),
Len Brown4be44fc2005-08-05 00:44:28 -0400168 acpi_ut_get_node_name(node), node, node->child));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169
Len Brown4be44fc2005-08-05 00:44:28 -0400170 return_ACPI_STATUS(AE_NOT_FOUND);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700171}
172
Linus Torvalds1da177e2005-04-16 15:20:36 -0700173/*******************************************************************************
174 *
175 * FUNCTION: acpi_ns_search_parent_tree
176 *
Robert Moore44f6c012005-04-18 22:49:35 -0400177 * PARAMETERS: target_name - Ascii ACPI name to search for
178 * Node - Starting node where search will begin
179 * Type - Object type to match
180 * return_node - Where the matched Node is returned
Linus Torvalds1da177e2005-04-16 15:20:36 -0700181 *
182 * RETURN: Status
183 *
184 * DESCRIPTION: Called when a name has not been found in the current namespace
185 * level. Before adding it or giving up, ACPI scope rules require
186 * searching enclosing scopes in cases identified by acpi_ns_local().
187 *
188 * "A name is located by finding the matching name in the current
189 * name space, and then in the parent name space. If the parent
190 * name space does not contain the name, the search continues
191 * recursively until either the name is found or the name space
192 * does not have a parent (the root of the name space). This
193 * indicates that the name is not found" (From ACPI Specification,
194 * section 5.3)
195 *
196 ******************************************************************************/
197
198static acpi_status
Len Brown4be44fc2005-08-05 00:44:28 -0400199acpi_ns_search_parent_tree(u32 target_name,
200 struct acpi_namespace_node *node,
201 acpi_object_type type,
202 struct acpi_namespace_node **return_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203{
Len Brown4be44fc2005-08-05 00:44:28 -0400204 acpi_status status;
205 struct acpi_namespace_node *parent_node;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206
Len Brown4be44fc2005-08-05 00:44:28 -0400207 ACPI_FUNCTION_TRACE("ns_search_parent_tree");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208
Len Brown4be44fc2005-08-05 00:44:28 -0400209 parent_node = acpi_ns_get_parent_node(node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210
211 /*
212 * If there is no parent (i.e., we are at the root) or type is "local",
213 * we won't be searching the parent tree.
214 */
215 if (!parent_node) {
Len Brown4be44fc2005-08-05 00:44:28 -0400216 ACPI_DEBUG_PRINT((ACPI_DB_NAMES, "[%4.4s] has no parent\n",
Bob Mooredefba1d2005-12-16 17:05:00 -0500217 ACPI_CAST_PTR(char, &target_name)));
Len Brown4be44fc2005-08-05 00:44:28 -0400218 return_ACPI_STATUS(AE_NOT_FOUND);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219 }
220
Len Brown4be44fc2005-08-05 00:44:28 -0400221 if (acpi_ns_local(type)) {
222 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
223 "[%4.4s] type [%s] must be local to this scope (no parent search)\n",
Bob Mooredefba1d2005-12-16 17:05:00 -0500224 ACPI_CAST_PTR(char, &target_name),
Len Brown4be44fc2005-08-05 00:44:28 -0400225 acpi_ut_get_type_name(type)));
226 return_ACPI_STATUS(AE_NOT_FOUND);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227 }
228
229 /* Search the parent tree */
230
Len Brown4be44fc2005-08-05 00:44:28 -0400231 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
232 "Searching parent [%4.4s] for [%4.4s]\n",
233 acpi_ut_get_node_name(parent_node),
Bob Mooredefba1d2005-12-16 17:05:00 -0500234 ACPI_CAST_PTR(char, &target_name)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700235
236 /*
237 * Search parents until target is found or we have backed up to the root
238 */
239 while (parent_node) {
240 /*
241 * Search parent scope. Use TYPE_ANY because we don't care about the
242 * object type at this point, we only care about the existence of
243 * the actual name we are searching for. Typechecking comes later.
244 */
Len Brown4be44fc2005-08-05 00:44:28 -0400245 status = acpi_ns_search_node(target_name, parent_node,
246 ACPI_TYPE_ANY, return_node);
247 if (ACPI_SUCCESS(status)) {
248 return_ACPI_STATUS(status);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700249 }
250
251 /*
252 * Not found here, go up another level
253 * (until we reach the root)
254 */
Len Brown4be44fc2005-08-05 00:44:28 -0400255 parent_node = acpi_ns_get_parent_node(parent_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256 }
257
258 /* Not found in parent tree */
259
Len Brown4be44fc2005-08-05 00:44:28 -0400260 return_ACPI_STATUS(AE_NOT_FOUND);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261}
262
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263/*******************************************************************************
264 *
265 * FUNCTION: acpi_ns_search_and_enter
266 *
267 * PARAMETERS: target_name - Ascii ACPI name to search for (4 chars)
268 * walk_state - Current state of the walk
Robert Moore44f6c012005-04-18 22:49:35 -0400269 * Node - Starting node where search will begin
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270 * interpreter_mode - Add names only in ACPI_MODE_LOAD_PASS_x.
271 * Otherwise,search only.
272 * Type - Object type to match
273 * Flags - Flags describing the search restrictions
Robert Moore44f6c012005-04-18 22:49:35 -0400274 * return_node - Where the Node is returned
Linus Torvalds1da177e2005-04-16 15:20:36 -0700275 *
276 * RETURN: Status
277 *
278 * DESCRIPTION: Search for a name segment in a single namespace level,
279 * optionally adding it if it is not found. If the passed
280 * Type is not Any and the type previously stored in the
281 * entry was Any (i.e. unknown), update the stored type.
282 *
283 * In ACPI_IMODE_EXECUTE, search only.
284 * In other modes, search and add if not found.
285 *
286 ******************************************************************************/
287
288acpi_status
Len Brown4be44fc2005-08-05 00:44:28 -0400289acpi_ns_search_and_enter(u32 target_name,
290 struct acpi_walk_state *walk_state,
291 struct acpi_namespace_node *node,
292 acpi_interpreter_mode interpreter_mode,
293 acpi_object_type type,
294 u32 flags, struct acpi_namespace_node **return_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295{
Len Brown4be44fc2005-08-05 00:44:28 -0400296 acpi_status status;
297 struct acpi_namespace_node *new_node;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700298
Len Brown4be44fc2005-08-05 00:44:28 -0400299 ACPI_FUNCTION_TRACE("ns_search_and_enter");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700300
301 /* Parameter validation */
302
303 if (!node || !target_name || !return_node) {
Bob Mooreb8e4d892006-01-27 16:43:00 -0500304 ACPI_ERROR((AE_INFO,
305 "Null param: Node %p Name %X return_node %p",
306 node, target_name, return_node));
Len Brown4be44fc2005-08-05 00:44:28 -0400307 return_ACPI_STATUS(AE_BAD_PARAMETER);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308 }
309
310 /* Name must consist of printable characters */
311
Len Brown4be44fc2005-08-05 00:44:28 -0400312 if (!acpi_ut_valid_acpi_name(target_name)) {
Bob Mooreb8e4d892006-01-27 16:43:00 -0500313 ACPI_ERROR((AE_INFO, "Bad character in ACPI Name: %X",
314 target_name));
Len Brown4be44fc2005-08-05 00:44:28 -0400315 return_ACPI_STATUS(AE_BAD_CHARACTER);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700316 }
317
318 /* Try to find the name in the namespace level specified by the caller */
319
320 *return_node = ACPI_ENTRY_NOT_FOUND;
Len Brown4be44fc2005-08-05 00:44:28 -0400321 status = acpi_ns_search_node(target_name, node, type, return_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700322 if (status != AE_NOT_FOUND) {
323 /*
324 * If we found it AND the request specifies that a find is an error,
325 * return the error
326 */
Len Brown4be44fc2005-08-05 00:44:28 -0400327 if ((status == AE_OK) && (flags & ACPI_NS_ERROR_IF_FOUND)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328 status = AE_ALREADY_EXISTS;
329 }
330
331 /*
332 * Either found it or there was an error
333 * -- finished either way
334 */
Len Brown4be44fc2005-08-05 00:44:28 -0400335 return_ACPI_STATUS(status);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336 }
337
338 /*
339 * The name was not found. If we are NOT performing the first pass
340 * (name entry) of loading the namespace, search the parent tree (all the
341 * way to the root if necessary.) We don't want to perform the parent
342 * search when the namespace is actually being loaded. We want to perform
343 * the search when namespace references are being resolved (load pass 2)
344 * and during the execution phase.
345 */
346 if ((interpreter_mode != ACPI_IMODE_LOAD_PASS1) &&
Len Brown4be44fc2005-08-05 00:44:28 -0400347 (flags & ACPI_NS_SEARCH_PARENT)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348 /*
349 * Not found at this level - search parent tree according to the
350 * ACPI specification
351 */
Len Brown4be44fc2005-08-05 00:44:28 -0400352 status =
353 acpi_ns_search_parent_tree(target_name, node, type,
354 return_node);
355 if (ACPI_SUCCESS(status)) {
356 return_ACPI_STATUS(status);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357 }
358 }
359
360 /*
361 * In execute mode, just search, never add names. Exit now.
362 */
363 if (interpreter_mode == ACPI_IMODE_EXECUTE) {
Len Brown4be44fc2005-08-05 00:44:28 -0400364 ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
365 "%4.4s Not found in %p [Not adding]\n",
Bob Mooredefba1d2005-12-16 17:05:00 -0500366 ACPI_CAST_PTR(char, &target_name), node));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700367
Len Brown4be44fc2005-08-05 00:44:28 -0400368 return_ACPI_STATUS(AE_NOT_FOUND);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700369 }
370
371 /* Create the new named object */
372
Len Brown4be44fc2005-08-05 00:44:28 -0400373 new_node = acpi_ns_create_node(target_name);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700374 if (!new_node) {
Len Brown4be44fc2005-08-05 00:44:28 -0400375 return_ACPI_STATUS(AE_NO_MEMORY);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376 }
377
378 /* Install the new object into the parent's list of children */
379
Len Brown4be44fc2005-08-05 00:44:28 -0400380 acpi_ns_install_node(walk_state, node, new_node, type);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381 *return_node = new_node;
382
Len Brown4be44fc2005-08-05 00:44:28 -0400383 return_ACPI_STATUS(AE_OK);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384}