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