1 /*******************************************************************************
3 * Module Name: nsalloc - Namespace allocation and deletion utilities
5 ******************************************************************************/
8 * Copyright (C) 2000 - 2008, Intel Corp.
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>
48 #define _COMPONENT ACPI_NAMESPACE
49 ACPI_MODULE_NAME("nsalloc")
51 /*******************************************************************************
53 * FUNCTION: acpi_ns_create_node
55 * PARAMETERS: Name - Name of the new node (4 char ACPI name)
57 * RETURN: New namespace node (Null on failure)
59 * DESCRIPTION: Create a namespace node
61 ******************************************************************************/
62 struct acpi_namespace_node
*acpi_ns_create_node(u32 name
)
64 struct acpi_namespace_node
*node
;
65 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
69 ACPI_FUNCTION_TRACE(ns_create_node
);
71 node
= acpi_os_acquire_object(acpi_gbl_namespace_cache
);
76 ACPI_MEM_TRACKING(acpi_gbl_ns_node_list
->total_allocated
++);
78 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
80 acpi_gbl_ns_node_list
->total_allocated
-
81 acpi_gbl_ns_node_list
->total_freed
;
82 if (temp
> acpi_gbl_ns_node_list
->max_occupied
) {
83 acpi_gbl_ns_node_list
->max_occupied
= temp
;
87 node
->name
.integer
= name
;
88 ACPI_SET_DESCRIPTOR_TYPE(node
, ACPI_DESC_TYPE_NAMED
);
92 /*******************************************************************************
94 * FUNCTION: acpi_ns_delete_node
96 * PARAMETERS: Node - Node to be deleted
100 * DESCRIPTION: Delete a namespace node
102 ******************************************************************************/
104 void acpi_ns_delete_node(struct acpi_namespace_node
*node
)
106 struct acpi_namespace_node
*parent_node
;
107 struct acpi_namespace_node
*prev_node
;
108 struct acpi_namespace_node
*next_node
;
110 ACPI_FUNCTION_TRACE_PTR(ns_delete_node
, node
);
112 parent_node
= acpi_ns_get_parent_node(node
);
115 next_node
= parent_node
->child
;
117 /* Find the node that is the previous peer in the parent's child list */
119 while (next_node
!= node
) {
120 prev_node
= next_node
;
121 next_node
= prev_node
->peer
;
126 /* Node is not first child, unlink it */
128 prev_node
->peer
= next_node
->peer
;
129 if (next_node
->flags
& ANOBJ_END_OF_PEER_LIST
) {
130 prev_node
->flags
|= ANOBJ_END_OF_PEER_LIST
;
133 /* Node is first child (has no previous peer) */
135 if (next_node
->flags
& ANOBJ_END_OF_PEER_LIST
) {
137 /* No peers at all */
139 parent_node
->child
= NULL
;
140 } else { /* Link peer list to parent */
142 parent_node
->child
= next_node
->peer
;
146 ACPI_MEM_TRACKING(acpi_gbl_ns_node_list
->total_freed
++);
149 * Detach an object if there is one, then delete the node
151 acpi_ns_detach_object(node
);
152 (void)acpi_os_release_object(acpi_gbl_namespace_cache
, node
);
156 /*******************************************************************************
158 * FUNCTION: acpi_ns_install_node
160 * PARAMETERS: walk_state - Current state of the walk
161 * parent_node - The parent of the new Node
162 * Node - The new Node to install
163 * Type - ACPI object type of the new Node
167 * DESCRIPTION: Initialize a new namespace node and install it amongst
170 * Note: Current namespace lookup is linear search. This appears
171 * to be sufficient as namespace searches consume only a small
172 * fraction of the execution time of the ACPI subsystem.
174 ******************************************************************************/
176 void acpi_ns_install_node(struct acpi_walk_state
*walk_state
, struct acpi_namespace_node
*parent_node
, /* Parent */
177 struct acpi_namespace_node
*node
, /* New Child */
178 acpi_object_type type
)
180 acpi_owner_id owner_id
= 0;
181 struct acpi_namespace_node
*child_node
;
183 ACPI_FUNCTION_TRACE(ns_install_node
);
186 * Get the owner ID from the Walk state
187 * The owner ID is used to track table deletion and
188 * deletion of objects created by methods
191 owner_id
= walk_state
->owner_id
;
194 /* Link the new entry into the parent and existing children */
196 child_node
= parent_node
->child
;
198 parent_node
->child
= node
;
199 node
->flags
|= ANOBJ_END_OF_PEER_LIST
;
200 node
->peer
= parent_node
;
202 while (!(child_node
->flags
& ANOBJ_END_OF_PEER_LIST
)) {
203 child_node
= child_node
->peer
;
206 child_node
->peer
= node
;
208 /* Clear end-of-list flag */
210 child_node
->flags
&= ~ANOBJ_END_OF_PEER_LIST
;
211 node
->flags
|= ANOBJ_END_OF_PEER_LIST
;
212 node
->peer
= parent_node
;
215 /* Init the new entry */
217 node
->owner_id
= owner_id
;
218 node
->type
= (u8
) type
;
220 ACPI_DEBUG_PRINT((ACPI_DB_NAMES
,
221 "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
222 acpi_ut_get_node_name(node
),
223 acpi_ut_get_type_name(node
->type
), node
, owner_id
,
224 acpi_ut_get_node_name(parent_node
),
225 acpi_ut_get_type_name(parent_node
->type
),
231 /*******************************************************************************
233 * FUNCTION: acpi_ns_delete_children
235 * PARAMETERS: parent_node - Delete this objects children
239 * DESCRIPTION: Delete all children of the parent object. In other words,
242 ******************************************************************************/
244 void acpi_ns_delete_children(struct acpi_namespace_node
*parent_node
)
246 struct acpi_namespace_node
*child_node
;
247 struct acpi_namespace_node
*next_node
;
250 ACPI_FUNCTION_TRACE_PTR(ns_delete_children
, parent_node
);
256 /* If no children, all done! */
258 child_node
= parent_node
->child
;
264 * Deallocate all children at this level
268 /* Get the things we need */
270 next_node
= child_node
->peer
;
271 flags
= child_node
->flags
;
273 /* Grandchildren should have all been deleted already */
275 if (child_node
->child
) {
276 ACPI_ERROR((AE_INFO
, "Found a grandchild! P=%p C=%p",
277 parent_node
, child_node
));
280 /* Now we can free this child object */
282 ACPI_MEM_TRACKING(acpi_gbl_ns_node_list
->total_freed
++);
284 ACPI_DEBUG_PRINT((ACPI_DB_ALLOCATIONS
,
285 "Object %p, Remaining %X\n", child_node
,
286 acpi_gbl_current_node_count
));
289 * Detach an object if there is one, then free the child node
291 acpi_ns_detach_object(child_node
);
293 /* Now we can delete the node */
295 (void)acpi_os_release_object(acpi_gbl_namespace_cache
,
298 /* And move on to the next child in the list */
300 child_node
= next_node
;
302 } while (!(flags
& ANOBJ_END_OF_PEER_LIST
));
304 /* Clear the parent's child pointer */
306 parent_node
->child
= NULL
;
311 /*******************************************************************************
313 * FUNCTION: acpi_ns_delete_namespace_subtree
315 * PARAMETERS: parent_node - Root of the subtree to be deleted
319 * DESCRIPTION: Delete a subtree of the namespace. This includes all objects
320 * stored within the subtree.
322 ******************************************************************************/
324 void acpi_ns_delete_namespace_subtree(struct acpi_namespace_node
*parent_node
)
326 struct acpi_namespace_node
*child_node
= NULL
;
329 ACPI_FUNCTION_TRACE(ns_delete_namespace_subtree
);
336 * Traverse the tree of objects until we bubble back up
337 * to where we started.
341 /* Get the next node in this scope (NULL if none) */
344 acpi_ns_get_next_node(ACPI_TYPE_ANY
, parent_node
,
348 /* Found a child node - detach any attached object */
350 acpi_ns_detach_object(child_node
);
352 /* Check if this node has any children */
354 if (acpi_ns_get_next_node
355 (ACPI_TYPE_ANY
, child_node
, NULL
)) {
357 * There is at least one child of this node,
361 parent_node
= child_node
;
366 * No more children of this parent node.
367 * Move up to the grandparent.
372 * Now delete all of the children of this parent
373 * all at the same time.
375 acpi_ns_delete_children(parent_node
);
377 /* New "last child" is this parent node */
379 child_node
= parent_node
;
381 /* Move up the tree to the grandparent */
383 parent_node
= acpi_ns_get_parent_node(parent_node
);
390 /*******************************************************************************
392 * FUNCTION: acpi_ns_delete_namespace_by_owner
394 * PARAMETERS: owner_id - All nodes with this owner will be deleted
398 * DESCRIPTION: Delete entries within the namespace that are owned by a
399 * specific ID. Used to delete entire ACPI tables. All
400 * reference counts are updated.
402 * MUTEX: Locks namespace during deletion walk.
404 ******************************************************************************/
406 void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id
)
408 struct acpi_namespace_node
*child_node
;
409 struct acpi_namespace_node
*deletion_node
;
410 struct acpi_namespace_node
*parent_node
;
414 ACPI_FUNCTION_TRACE_U32(ns_delete_namespace_by_owner
, owner_id
);
420 /* Lock namespace for possible update */
422 status
= acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE
);
423 if (ACPI_FAILURE(status
)) {
427 deletion_node
= NULL
;
428 parent_node
= acpi_gbl_root_node
;
433 * Traverse the tree of nodes until we bubble back up
434 * to where we started.
438 * Get the next child of this parent node. When child_node is NULL,
439 * the first child of the parent is returned
442 acpi_ns_get_next_node(ACPI_TYPE_ANY
, parent_node
,
446 acpi_ns_delete_children(deletion_node
);
447 acpi_ns_delete_node(deletion_node
);
448 deletion_node
= NULL
;
452 if (child_node
->owner_id
== owner_id
) {
454 /* Found a matching child node - detach any attached object */
456 acpi_ns_detach_object(child_node
);
459 /* Check if this node has any children */
461 if (acpi_ns_get_next_node
462 (ACPI_TYPE_ANY
, child_node
, NULL
)) {
464 * There is at least one child of this node,
468 parent_node
= child_node
;
470 } else if (child_node
->owner_id
== owner_id
) {
471 deletion_node
= child_node
;
475 * No more children of this parent node.
476 * Move up to the grandparent.
480 if (parent_node
->owner_id
== owner_id
) {
481 deletion_node
= parent_node
;
485 /* New "last child" is this parent node */
487 child_node
= parent_node
;
489 /* Move up the tree to the grandparent */
491 parent_node
= acpi_ns_get_parent_node(parent_node
);
495 (void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE
);