1 /*******************************************************************************
3 * Module Name: nsalloc - Namespace allocation and deletion utilities
5 ******************************************************************************/
8 * Copyright (C) 2000 - 2006, R. Byron Moore
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
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.
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.
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.
44 #include <acpi/acpi.h>
45 #include <acpi/acnamesp.h>
47 #define _COMPONENT ACPI_NAMESPACE
48 ACPI_MODULE_NAME("nsalloc")
50 /*******************************************************************************
52 * FUNCTION: acpi_ns_create_node
54 * PARAMETERS: Name - Name of the new node (4 char ACPI name)
56 * RETURN: New namespace node (Null on failure)
58 * DESCRIPTION: Create a namespace node
60 ******************************************************************************/
61 struct acpi_namespace_node
*acpi_ns_create_node(u32 name
)
63 struct acpi_namespace_node
*node
;
65 ACPI_FUNCTION_TRACE(ns_create_node
);
67 node
= acpi_os_acquire_object(acpi_gbl_namespace_cache
);
72 ACPI_MEM_TRACKING(acpi_gbl_ns_node_list
->total_allocated
++);
74 node
->name
.integer
= name
;
75 ACPI_SET_DESCRIPTOR_TYPE(node
, ACPI_DESC_TYPE_NAMED
);
79 /*******************************************************************************
81 * FUNCTION: acpi_ns_delete_node
83 * PARAMETERS: Node - Node to be deleted
87 * DESCRIPTION: Delete a namespace node
89 ******************************************************************************/
91 void acpi_ns_delete_node(struct acpi_namespace_node
*node
)
93 struct acpi_namespace_node
*parent_node
;
94 struct acpi_namespace_node
*prev_node
;
95 struct acpi_namespace_node
*next_node
;
97 ACPI_FUNCTION_TRACE_PTR(ns_delete_node
, node
);
99 parent_node
= acpi_ns_get_parent_node(node
);
102 next_node
= parent_node
->child
;
104 /* Find the node that is the previous peer in the parent's child list */
106 while (next_node
!= node
) {
107 prev_node
= next_node
;
108 next_node
= prev_node
->peer
;
113 /* Node is not first child, unlink it */
115 prev_node
->peer
= next_node
->peer
;
116 if (next_node
->flags
& ANOBJ_END_OF_PEER_LIST
) {
117 prev_node
->flags
|= ANOBJ_END_OF_PEER_LIST
;
120 /* Node is first child (has no previous peer) */
122 if (next_node
->flags
& ANOBJ_END_OF_PEER_LIST
) {
124 /* No peers at all */
126 parent_node
->child
= NULL
;
127 } else { /* Link peer list to parent */
129 parent_node
->child
= next_node
->peer
;
133 ACPI_MEM_TRACKING(acpi_gbl_ns_node_list
->total_freed
++);
136 * Detach an object if there is one, then delete the node
138 acpi_ns_detach_object(node
);
139 (void)acpi_os_release_object(acpi_gbl_namespace_cache
, node
);
143 /*******************************************************************************
145 * FUNCTION: acpi_ns_install_node
147 * PARAMETERS: walk_state - Current state of the walk
148 * parent_node - The parent of the new Node
149 * Node - The new Node to install
150 * Type - ACPI object type of the new Node
154 * DESCRIPTION: Initialize a new namespace node and install it amongst
157 * Note: Current namespace lookup is linear search. This appears
158 * to be sufficient as namespace searches consume only a small
159 * fraction of the execution time of the ACPI subsystem.
161 ******************************************************************************/
163 void acpi_ns_install_node(struct acpi_walk_state
*walk_state
, struct acpi_namespace_node
*parent_node
, /* Parent */
164 struct acpi_namespace_node
*node
, /* New Child */
165 acpi_object_type type
)
167 acpi_owner_id owner_id
= 0;
168 struct acpi_namespace_node
*child_node
;
170 ACPI_FUNCTION_TRACE(ns_install_node
);
173 * Get the owner ID from the Walk state
174 * The owner ID is used to track table deletion and
175 * deletion of objects created by methods
178 owner_id
= walk_state
->owner_id
;
181 /* Link the new entry into the parent and existing children */
183 child_node
= parent_node
->child
;
185 parent_node
->child
= node
;
186 node
->flags
|= ANOBJ_END_OF_PEER_LIST
;
187 node
->peer
= parent_node
;
189 while (!(child_node
->flags
& ANOBJ_END_OF_PEER_LIST
)) {
190 child_node
= child_node
->peer
;
193 child_node
->peer
= node
;
195 /* Clear end-of-list flag */
197 child_node
->flags
&= ~ANOBJ_END_OF_PEER_LIST
;
198 node
->flags
|= ANOBJ_END_OF_PEER_LIST
;
199 node
->peer
= parent_node
;
202 /* Init the new entry */
204 node
->owner_id
= owner_id
;
205 node
->type
= (u8
) type
;
207 ACPI_DEBUG_PRINT((ACPI_DB_NAMES
,
208 "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
209 acpi_ut_get_node_name(node
),
210 acpi_ut_get_type_name(node
->type
), node
, owner_id
,
211 acpi_ut_get_node_name(parent_node
),
212 acpi_ut_get_type_name(parent_node
->type
),
218 /*******************************************************************************
220 * FUNCTION: acpi_ns_delete_children
222 * PARAMETERS: parent_node - Delete this objects children
226 * DESCRIPTION: Delete all children of the parent object. In other words,
229 ******************************************************************************/
231 void acpi_ns_delete_children(struct acpi_namespace_node
*parent_node
)
233 struct acpi_namespace_node
*child_node
;
234 struct acpi_namespace_node
*next_node
;
237 ACPI_FUNCTION_TRACE_PTR(ns_delete_children
, parent_node
);
243 /* If no children, all done! */
245 child_node
= parent_node
->child
;
251 * Deallocate all children at this level
255 /* Get the things we need */
257 next_node
= child_node
->peer
;
258 flags
= child_node
->flags
;
260 /* Grandchildren should have all been deleted already */
262 if (child_node
->child
) {
263 ACPI_ERROR((AE_INFO
, "Found a grandchild! P=%p C=%p",
264 parent_node
, child_node
));
267 /* Now we can free this child object */
269 ACPI_MEM_TRACKING(acpi_gbl_ns_node_list
->total_freed
++);
271 ACPI_DEBUG_PRINT((ACPI_DB_ALLOCATIONS
,
272 "Object %p, Remaining %X\n", child_node
,
273 acpi_gbl_current_node_count
));
276 * Detach an object if there is one, then free the child node
278 acpi_ns_detach_object(child_node
);
280 /* Now we can delete the node */
282 (void)acpi_os_release_object(acpi_gbl_namespace_cache
,
285 /* And move on to the next child in the list */
287 child_node
= next_node
;
289 } while (!(flags
& ANOBJ_END_OF_PEER_LIST
));
291 /* Clear the parent's child pointer */
293 parent_node
->child
= NULL
;
298 /*******************************************************************************
300 * FUNCTION: acpi_ns_delete_namespace_subtree
302 * PARAMETERS: parent_node - Root of the subtree to be deleted
306 * DESCRIPTION: Delete a subtree of the namespace. This includes all objects
307 * stored within the subtree.
309 ******************************************************************************/
311 void acpi_ns_delete_namespace_subtree(struct acpi_namespace_node
*parent_node
)
313 struct acpi_namespace_node
*child_node
= NULL
;
316 ACPI_FUNCTION_TRACE(ns_delete_namespace_subtree
);
323 * Traverse the tree of objects until we bubble back up
324 * to where we started.
328 /* Get the next node in this scope (NULL if none) */
331 acpi_ns_get_next_node(ACPI_TYPE_ANY
, parent_node
,
335 /* Found a child node - detach any attached object */
337 acpi_ns_detach_object(child_node
);
339 /* Check if this node has any children */
341 if (acpi_ns_get_next_node
342 (ACPI_TYPE_ANY
, child_node
, NULL
)) {
344 * There is at least one child of this node,
348 parent_node
= child_node
;
353 * No more children of this parent node.
354 * Move up to the grandparent.
359 * Now delete all of the children of this parent
360 * all at the same time.
362 acpi_ns_delete_children(parent_node
);
364 /* New "last child" is this parent node */
366 child_node
= parent_node
;
368 /* Move up the tree to the grandparent */
370 parent_node
= acpi_ns_get_parent_node(parent_node
);
377 /*******************************************************************************
379 * FUNCTION: acpi_ns_delete_namespace_by_owner
381 * PARAMETERS: owner_id - All nodes with this owner will be deleted
385 * DESCRIPTION: Delete entries within the namespace that are owned by a
386 * specific ID. Used to delete entire ACPI tables. All
387 * reference counts are updated.
389 ******************************************************************************/
391 void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id
)
393 struct acpi_namespace_node
*child_node
;
394 struct acpi_namespace_node
*deletion_node
;
396 struct acpi_namespace_node
*parent_node
;
398 ACPI_FUNCTION_TRACE_U32(ns_delete_namespace_by_owner
, owner_id
);
404 deletion_node
= NULL
;
405 parent_node
= acpi_gbl_root_node
;
410 * Traverse the tree of nodes until we bubble back up
411 * to where we started.
415 * Get the next child of this parent node. When child_node is NULL,
416 * the first child of the parent is returned
419 acpi_ns_get_next_node(ACPI_TYPE_ANY
, parent_node
,
423 acpi_ns_delete_children(deletion_node
);
424 acpi_ns_delete_node(deletion_node
);
425 deletion_node
= NULL
;
429 if (child_node
->owner_id
== owner_id
) {
431 /* Found a matching child node - detach any attached object */
433 acpi_ns_detach_object(child_node
);
436 /* Check if this node has any children */
438 if (acpi_ns_get_next_node
439 (ACPI_TYPE_ANY
, child_node
, NULL
)) {
441 * There is at least one child of this node,
445 parent_node
= child_node
;
447 } else if (child_node
->owner_id
== owner_id
) {
448 deletion_node
= child_node
;
452 * No more children of this parent node.
453 * Move up to the grandparent.
457 if (parent_node
->owner_id
== owner_id
) {
458 deletion_node
= parent_node
;
462 /* New "last child" is this parent node */
464 child_node
= parent_node
;
466 /* Move up the tree to the grandparent */
468 parent_node
= acpi_ns_get_parent_node(parent_node
);