Merge branch 'HEAD' of master.kernel.org:/pub/scm/linux/kernel/git/herbert/crypto-2.6
[linux-2.6] / drivers / acpi / namespace / nswalk.c
1 /******************************************************************************
2  *
3  * Module Name: nswalk - Functions for walking the ACPI namespace
4  *
5  *****************************************************************************/
6
7 /*
8  * Copyright (C) 2000 - 2007, R. Byron Moore
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 #include <acpi/acpi.h>
45 #include <acpi/acnamesp.h>
46
47 #define _COMPONENT          ACPI_NAMESPACE
48 ACPI_MODULE_NAME("nswalk")
49
50 /*******************************************************************************
51  *
52  * FUNCTION:    acpi_ns_get_next_node
53  *
54  * PARAMETERS:  Type                - Type of node to be searched for
55  *              parent_node         - Parent node whose children we are
56  *                                    getting
57  *              child_node          - Previous child that was found.
58  *                                    The NEXT child will be returned
59  *
60  * RETURN:      struct acpi_namespace_node - Pointer to the NEXT child or NULL if
61  *                                    none is found.
62  *
63  * DESCRIPTION: Return the next peer node within the namespace.  If Handle
64  *              is valid, Scope is ignored.  Otherwise, the first node
65  *              within Scope is returned.
66  *
67  ******************************************************************************/
68 struct acpi_namespace_node *acpi_ns_get_next_node(acpi_object_type type,
69                                                   struct acpi_namespace_node
70                                                   *parent_node,
71                                                   struct acpi_namespace_node
72                                                   *child_node)
73 {
74         struct acpi_namespace_node *next_node = NULL;
75
76         ACPI_FUNCTION_ENTRY();
77
78         if (!child_node) {
79
80                 /* It's really the parent's _scope_ that we want */
81
82                 if (parent_node->child) {
83                         next_node = parent_node->child;
84                 }
85         }
86
87         else {
88                 /* Start search at the NEXT node */
89
90                 next_node = acpi_ns_get_next_valid_node(child_node);
91         }
92
93         /* If any type is OK, we are done */
94
95         if (type == ACPI_TYPE_ANY) {
96
97                 /* next_node is NULL if we are at the end-of-list */
98
99                 return (next_node);
100         }
101
102         /* Must search for the node -- but within this scope only */
103
104         while (next_node) {
105
106                 /* If type matches, we are done */
107
108                 if (next_node->type == type) {
109                         return (next_node);
110                 }
111
112                 /* Otherwise, move on to the next node */
113
114                 next_node = acpi_ns_get_next_valid_node(next_node);
115         }
116
117         /* Not found */
118
119         return (NULL);
120 }
121
122 /*******************************************************************************
123  *
124  * FUNCTION:    acpi_ns_walk_namespace
125  *
126  * PARAMETERS:  Type                - acpi_object_type to search for
127  *              start_node          - Handle in namespace where search begins
128  *              max_depth           - Depth to which search is to reach
129  *              Flags               - Whether to unlock the NS before invoking
130  *                                    the callback routine
131  *              user_function       - Called when an object of "Type" is found
132  *              Context             - Passed to user function
133  *              return_value        - from the user_function if terminated early.
134  *                                    Otherwise, returns NULL.
135  * RETURNS:     Status
136  *
137  * DESCRIPTION: Performs a modified depth-first walk of the namespace tree,
138  *              starting (and ending) at the node specified by start_handle.
139  *              The user_function is called whenever a node that matches
140  *              the type parameter is found.  If the user function returns
141  *              a non-zero value, the search is terminated immediately and this
142  *              value is returned to the caller.
143  *
144  *              The point of this procedure is to provide a generic namespace
145  *              walk routine that can be called from multiple places to
146  *              provide multiple services;  the User Function can be tailored
147  *              to each task, whether it is a print function, a compare
148  *              function, etc.
149  *
150  ******************************************************************************/
151
152 acpi_status
153 acpi_ns_walk_namespace(acpi_object_type type,
154                        acpi_handle start_node,
155                        u32 max_depth,
156                        u32 flags,
157                        acpi_walk_callback user_function,
158                        void *context, void **return_value)
159 {
160         acpi_status status;
161         acpi_status mutex_status;
162         struct acpi_namespace_node *child_node;
163         struct acpi_namespace_node *parent_node;
164         acpi_object_type child_type;
165         u32 level;
166
167         ACPI_FUNCTION_TRACE(ns_walk_namespace);
168
169         /* Special case for the namespace Root Node */
170
171         if (start_node == ACPI_ROOT_OBJECT) {
172                 start_node = acpi_gbl_root_node;
173         }
174
175         /* Null child means "get first node" */
176
177         parent_node = start_node;
178         child_node = NULL;
179         child_type = ACPI_TYPE_ANY;
180         level = 1;
181
182         /*
183          * Traverse the tree of nodes until we bubble back up to where we
184          * started. When Level is zero, the loop is done because we have
185          * bubbled up to (and passed) the original parent handle (start_entry)
186          */
187         while (level > 0) {
188
189                 /* Get the next node in this scope.  Null if not found */
190
191                 status = AE_OK;
192                 child_node =
193                     acpi_ns_get_next_node(ACPI_TYPE_ANY, parent_node,
194                                           child_node);
195                 if (child_node) {
196
197                         /* Found next child, get the type if we are not searching for ANY */
198
199                         if (type != ACPI_TYPE_ANY) {
200                                 child_type = child_node->type;
201                         }
202
203                         /*
204                          * Ignore all temporary namespace nodes (created during control
205                          * method execution) unless told otherwise. These temporary nodes
206                          * can cause a race condition because they can be deleted during the
207                          * execution of the user function (if the namespace is unlocked before
208                          * invocation of the user function.) Only the debugger namespace dump
209                          * will examine the temporary nodes.
210                          */
211                         if ((child_node->flags & ANOBJ_TEMPORARY) &&
212                             !(flags & ACPI_NS_WALK_TEMP_NODES)) {
213                                 status = AE_CTRL_DEPTH;
214                         }
215
216                         /* Type must match requested type */
217
218                         else if (child_type == type) {
219                                 /*
220                                  * Found a matching node, invoke the user callback function.
221                                  * Unlock the namespace if flag is set.
222                                  */
223                                 if (flags & ACPI_NS_WALK_UNLOCK) {
224                                         mutex_status =
225                                             acpi_ut_release_mutex
226                                             (ACPI_MTX_NAMESPACE);
227                                         if (ACPI_FAILURE(mutex_status)) {
228                                                 return_ACPI_STATUS
229                                                     (mutex_status);
230                                         }
231                                 }
232
233                                 status =
234                                     user_function(child_node, level, context,
235                                                   return_value);
236
237                                 if (flags & ACPI_NS_WALK_UNLOCK) {
238                                         mutex_status =
239                                             acpi_ut_acquire_mutex
240                                             (ACPI_MTX_NAMESPACE);
241                                         if (ACPI_FAILURE(mutex_status)) {
242                                                 return_ACPI_STATUS
243                                                     (mutex_status);
244                                         }
245                                 }
246
247                                 switch (status) {
248                                 case AE_OK:
249                                 case AE_CTRL_DEPTH:
250
251                                         /* Just keep going */
252                                         break;
253
254                                 case AE_CTRL_TERMINATE:
255
256                                         /* Exit now, with OK status */
257
258                                         return_ACPI_STATUS(AE_OK);
259
260                                 default:
261
262                                         /* All others are valid exceptions */
263
264                                         return_ACPI_STATUS(status);
265                                 }
266                         }
267
268                         /*
269                          * Depth first search: Attempt to go down another level in the
270                          * namespace if we are allowed to.  Don't go any further if we have
271                          * reached the caller specified maximum depth or if the user
272                          * function has specified that the maximum depth has been reached.
273                          */
274                         if ((level < max_depth) && (status != AE_CTRL_DEPTH)) {
275                                 if (acpi_ns_get_next_node
276                                     (ACPI_TYPE_ANY, child_node, NULL)) {
277
278                                         /* There is at least one child of this node, visit it */
279
280                                         level++;
281                                         parent_node = child_node;
282                                         child_node = NULL;
283                                 }
284                         }
285                 } else {
286                         /*
287                          * No more children of this node (acpi_ns_get_next_node failed), go
288                          * back upwards in the namespace tree to the node's parent.
289                          */
290                         level--;
291                         child_node = parent_node;
292                         parent_node = acpi_ns_get_parent_node(parent_node);
293                 }
294         }
295
296         /* Complete walk, not terminated by user function */
297
298         return_ACPI_STATUS(AE_OK);
299 }