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