1 /*******************************************************************************
2 *
3 * Module Name: nsalloc - Namespace allocation and deletion utilities
4 *
5 ******************************************************************************/
6
7 /*
8 * Copyright (C) 2000 - 2011, Intel Corp.
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
45 #define __NSALLOC_C__
46
47 #include "acpi.h"
48 #include "accommon.h"
49 #include "acnamesp.h"
50
51
52 #define _COMPONENT ACPI_NAMESPACE
53 ACPI_MODULE_NAME ("nsalloc")
54
55
56 /*******************************************************************************
57 *
58 * FUNCTION: AcpiNsCreateNode
59 *
60 * PARAMETERS: Name - Name of the new node (4 char ACPI name)
61 *
62 * RETURN: New namespace node (Null on failure)
63 *
64 * DESCRIPTION: Create a namespace node
65 *
66 ******************************************************************************/
67
68 ACPI_NAMESPACE_NODE *
69 AcpiNsCreateNode (
70 UINT32 Name)
71 {
72 ACPI_NAMESPACE_NODE *Node;
73 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
74 UINT32 Temp;
75 #endif
76
77
78 ACPI_FUNCTION_TRACE (NsCreateNode);
79
80
81 Node = AcpiOsAcquireObject (AcpiGbl_NamespaceCache);
82 if (!Node)
83 {
84 return_PTR (NULL);
85 }
86
87 ACPI_MEM_TRACKING (AcpiGbl_NsNodeList->TotalAllocated++);
88
89 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
90 Temp = AcpiGbl_NsNodeList->TotalAllocated -
91 AcpiGbl_NsNodeList->TotalFreed;
92 if (Temp > AcpiGbl_NsNodeList->MaxOccupied)
93 {
94 AcpiGbl_NsNodeList->MaxOccupied = Temp;
95 }
96 #endif
97
98 Node->Name.Integer = Name;
99 ACPI_SET_DESCRIPTOR_TYPE (Node, ACPI_DESC_TYPE_NAMED);
100 return_PTR (Node);
101 }
102
103
104 /*******************************************************************************
105 *
106 * FUNCTION: AcpiNsDeleteNode
107 *
108 * PARAMETERS: Node - Node to be deleted
109 *
110 * RETURN: None
111 *
112 * DESCRIPTION: Delete a namespace node. All node deletions must come through
113 * here. Detaches any attached objects, including any attached
114 * data. If a handler is associated with attached data, it is
115 * invoked before the node is deleted.
116 *
117 ******************************************************************************/
118
119 void
120 AcpiNsDeleteNode (
121 ACPI_NAMESPACE_NODE *Node)
122 {
123 ACPI_OPERAND_OBJECT *ObjDesc;
124
125
126 ACPI_FUNCTION_NAME (NsDeleteNode);
127
128
129 /* Detach an object if there is one */
130
131 AcpiNsDetachObject (Node);
132
133 /*
134 * Delete an attached data object if present (an object that was created
135 * and attached via AcpiAttachData). Note: After any normal object is
136 * detached above, the only possible remaining object is a data object.
137 */
138 ObjDesc = Node->Object;
139 if (ObjDesc &&
140 (ObjDesc->Common.Type == ACPI_TYPE_LOCAL_DATA))
141 {
142 /* Invoke the attached data deletion handler if present */
143
144 if (ObjDesc->Data.Handler)
145 {
146 ObjDesc->Data.Handler (Node, ObjDesc->Data.Pointer);
147 }
148
149 AcpiUtRemoveReference (ObjDesc);
150 }
151
152 /* Now we can delete the node */
153
154 (void) AcpiOsReleaseObject (AcpiGbl_NamespaceCache, Node);
155
156 ACPI_MEM_TRACKING (AcpiGbl_NsNodeList->TotalFreed++);
157 ACPI_DEBUG_PRINT ((ACPI_DB_ALLOCATIONS, "Node %p, Remaining %X\n",
158 Node, AcpiGbl_CurrentNodeCount));
159 }
160
161
162 /*******************************************************************************
163 *
164 * FUNCTION: AcpiNsRemoveNode
165 *
166 * PARAMETERS: Node - Node to be removed/deleted
167 *
168 * RETURN: None
169 *
170 * DESCRIPTION: Remove (unlink) and delete a namespace node
171 *
172 ******************************************************************************/
173
174 void
175 AcpiNsRemoveNode (
176 ACPI_NAMESPACE_NODE *Node)
177 {
178 ACPI_NAMESPACE_NODE *ParentNode;
179 ACPI_NAMESPACE_NODE *PrevNode;
180 ACPI_NAMESPACE_NODE *NextNode;
181
182
183 ACPI_FUNCTION_TRACE_PTR (NsRemoveNode, Node);
184
185
186 ParentNode = Node->Parent;
187
188 PrevNode = NULL;
189 NextNode = ParentNode->Child;
190
191 /* Find the node that is the previous peer in the parent's child list */
192
193 while (NextNode != Node)
194 {
195 PrevNode = NextNode;
196 NextNode = NextNode->Peer;
197 }
198
199 if (PrevNode)
200 {
201 /* Node is not first child, unlink it */
202
203 PrevNode->Peer = Node->Peer;
204 }
205 else
206 {
207 /*
208 * Node is first child (has no previous peer).
209 * Link peer list to parent
210 */
211 ParentNode->Child = Node->Peer;
212 }
213
214 /* Delete the node and any attached objects */
215
216 AcpiNsDeleteNode (Node);
217 return_VOID;
218 }
219
220
221 /*******************************************************************************
222 *
223 * FUNCTION: AcpiNsInstallNode
224 *
225 * PARAMETERS: WalkState - Current state of the walk
226 * ParentNode - The parent of the new Node
227 * Node - The new Node to install
228 * Type - ACPI object type of the new Node
229 *
230 * RETURN: None
231 *
232 * DESCRIPTION: Initialize a new namespace node and install it amongst
233 * its peers.
234 *
235 * Note: Current namespace lookup is linear search. This appears
236 * to be sufficient as namespace searches consume only a small
237 * fraction of the execution time of the ACPI subsystem.
238 *
239 ******************************************************************************/
240
241 void
242 AcpiNsInstallNode (
243 ACPI_WALK_STATE *WalkState,
244 ACPI_NAMESPACE_NODE *ParentNode, /* Parent */
245 ACPI_NAMESPACE_NODE *Node, /* New Child*/
246 ACPI_OBJECT_TYPE Type)
247 {
248 ACPI_OWNER_ID OwnerId = 0;
249 ACPI_NAMESPACE_NODE *ChildNode;
250
251
252 ACPI_FUNCTION_TRACE (NsInstallNode);
253
254
255 if (WalkState)
256 {
257 /*
258 * Get the owner ID from the Walk state. The owner ID is used to
259 * track table deletion and deletion of objects created by methods.
260 */
261 OwnerId = WalkState->OwnerId;
262
263 if ((WalkState->MethodDesc) &&
264 (ParentNode != WalkState->MethodNode))
265 {
266 /*
267 * A method is creating a new node that is not a child of the
268 * method (it is non-local). Mark the executing method as having
269 * modified the namespace. This is used for cleanup when the
270 * method exits.
271 */
272 WalkState->MethodDesc->Method.InfoFlags |= ACPI_METHOD_MODIFIED_NAMESPACE;
273 }
274 }
275
276 /* Link the new entry into the parent and existing children */
277
278 Node->Peer = NULL;
279 Node->Parent = ParentNode;
280 ChildNode = ParentNode->Child;
281
282 if (!ChildNode)
283 {
284 ParentNode->Child = Node;
285 }
286 else
287 {
288 /* Add node to the end of the peer list */
289
290 while (ChildNode->Peer)
291 {
292 ChildNode = ChildNode->Peer;
293 }
294
295 ChildNode->Peer = Node;
296 }
297
298 /* Init the new entry */
299
300 Node->OwnerId = OwnerId;
301 Node->Type = (UINT8) Type;
302
303 ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
304 "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
305 AcpiUtGetNodeName (Node), AcpiUtGetTypeName (Node->Type), Node, OwnerId,
306 AcpiUtGetNodeName (ParentNode), AcpiUtGetTypeName (ParentNode->Type),
307 ParentNode));
308
309 return_VOID;
310 }
311
312
313 /*******************************************************************************
314 *
315 * FUNCTION: AcpiNsDeleteChildren
316 *
317 * PARAMETERS: ParentNode - Delete this objects children
318 *
319 * RETURN: None.
320 *
321 * DESCRIPTION: Delete all children of the parent object. In other words,
322 * deletes a "scope".
323 *
324 ******************************************************************************/
325
326 void
327 AcpiNsDeleteChildren (
328 ACPI_NAMESPACE_NODE *ParentNode)
329 {
330 ACPI_NAMESPACE_NODE *NextNode;
331 ACPI_NAMESPACE_NODE *NodeToDelete;
332
333
334 ACPI_FUNCTION_TRACE_PTR (NsDeleteChildren, ParentNode);
335
336
337 if (!ParentNode)
338 {
339 return_VOID;
340 }
341
342 /* Deallocate all children at this level */
343
344 NextNode = ParentNode->Child;
345 while (NextNode)
346 {
347 /* Grandchildren should have all been deleted already */
348
349 if (NextNode->Child)
350 {
351 ACPI_ERROR ((AE_INFO, "Found a grandchild! P=%p C=%p",
352 ParentNode, NextNode));
353 }
354
355 /*
356 * Delete this child node and move on to the next child in the list.
357 * No need to unlink the node since we are deleting the entire branch.
358 */
359 NodeToDelete = NextNode;
360 NextNode = NextNode->Peer;
361 AcpiNsDeleteNode (NodeToDelete);
362 };
363
364 /* Clear the parent's child pointer */
365
366 ParentNode->Child = NULL;
367 return_VOID;
368 }
369
370
371 /*******************************************************************************
372 *
373 * FUNCTION: AcpiNsDeleteNamespaceSubtree
374 *
375 * PARAMETERS: ParentNode - Root of the subtree to be deleted
376 *
377 * RETURN: None.
378 *
379 * DESCRIPTION: Delete a subtree of the namespace. This includes all objects
380 * stored within the subtree.
381 *
382 ******************************************************************************/
383
384 void
385 AcpiNsDeleteNamespaceSubtree (
386 ACPI_NAMESPACE_NODE *ParentNode)
387 {
388 ACPI_NAMESPACE_NODE *ChildNode = NULL;
389 UINT32 Level = 1;
390 ACPI_STATUS Status;
391
392
393 ACPI_FUNCTION_TRACE (NsDeleteNamespaceSubtree);
394
395
396 if (!ParentNode)
397 {
398 return_VOID;
399 }
400
401 /* Lock namespace for possible update */
402
403 Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
404 if (ACPI_FAILURE (Status))
405 {
406 return_VOID;
407 }
408
409 /*
410 * Traverse the tree of objects until we bubble back up
411 * to where we started.
412 */
413 while (Level > 0)
414 {
415 /* Get the next node in this scope (NULL if none) */
416
417 ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
418 if (ChildNode)
419 {
420 /* Found a child node - detach any attached object */
421
422 AcpiNsDetachObject (ChildNode);
423
424 /* Check if this node has any children */
425
426 if (ChildNode->Child)
427 {
428 /*
429 * There is at least one child of this node,
430 * visit the node
431 */
432 Level++;
433 ParentNode = ChildNode;
434 ChildNode = NULL;
435 }
436 }
437 else
438 {
439 /*
440 * No more children of this parent node.
441 * Move up to the grandparent.
442 */
443 Level--;
444
445 /*
446 * Now delete all of the children of this parent
447 * all at the same time.
448 */
449 AcpiNsDeleteChildren (ParentNode);
450
451 /* New "last child" is this parent node */
452
453 ChildNode = ParentNode;
454
455 /* Move up the tree to the grandparent */
456
457 ParentNode = ParentNode->Parent;
458 }
459 }
460
461 (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
462 return_VOID;
463 }
464
465
466 /*******************************************************************************
467 *
468 * FUNCTION: AcpiNsDeleteNamespaceByOwner
469 *
470 * PARAMETERS: OwnerId - All nodes with this owner will be deleted
471 *
472 * RETURN: Status
473 *
474 * DESCRIPTION: Delete entries within the namespace that are owned by a
475 * specific ID. Used to delete entire ACPI tables. All
476 * reference counts are updated.
477 *
478 * MUTEX: Locks namespace during deletion walk.
479 *
480 ******************************************************************************/
481
482 void
483 AcpiNsDeleteNamespaceByOwner (
484 ACPI_OWNER_ID OwnerId)
485 {
486 ACPI_NAMESPACE_NODE *ChildNode;
487 ACPI_NAMESPACE_NODE *DeletionNode;
488 ACPI_NAMESPACE_NODE *ParentNode;
489 UINT32 Level;
490 ACPI_STATUS Status;
491
492
493 ACPI_FUNCTION_TRACE_U32 (NsDeleteNamespaceByOwner, OwnerId);
494
495
496 if (OwnerId == 0)
497 {
498 return_VOID;
499 }
500
501 /* Lock namespace for possible update */
502
503 Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
504 if (ACPI_FAILURE (Status))
505 {
506 return_VOID;
507 }
508
509 DeletionNode = NULL;
510 ParentNode = AcpiGbl_RootNode;
511 ChildNode = NULL;
512 Level = 1;
513
514 /*
515 * Traverse the tree of nodes until we bubble back up
516 * to where we started.
517 */
518 while (Level > 0)
519 {
520 /*
521 * Get the next child of this parent node. When ChildNode is NULL,
522 * the first child of the parent is returned
523 */
524 ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
525
526 if (DeletionNode)
527 {
528 AcpiNsDeleteChildren (DeletionNode);
529 AcpiNsRemoveNode (DeletionNode);
530 DeletionNode = NULL;
531 }
532
533 if (ChildNode)
534 {
535 if (ChildNode->OwnerId == OwnerId)
536 {
537 /* Found a matching child node - detach any attached object */
538
539 AcpiNsDetachObject (ChildNode);
540 }
541
542 /* Check if this node has any children */
543
544 if (ChildNode->Child)
545 {
546 /*
547 * There is at least one child of this node,
548 * visit the node
549 */
550 Level++;
551 ParentNode = ChildNode;
552 ChildNode = NULL;
553 }
554 else if (ChildNode->OwnerId == OwnerId)
555 {
556 DeletionNode = ChildNode;
557 }
558 }
559 else
560 {
561 /*
562 * No more children of this parent node.
563 * Move up to the grandparent.
564 */
565 Level--;
566 if (Level != 0)
567 {
568 if (ParentNode->OwnerId == OwnerId)
569 {
570 DeletionNode = ParentNode;
571 }
572 }
573
574 /* New "last child" is this parent node */
575
576 ChildNode = ParentNode;
577
578 /* Move up the tree to the grandparent */
579
580 ParentNode = ParentNode->Parent;
581 }
582 }
583
584 (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
585 return_VOID;
586 }
587
588