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