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 #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 |= ACPI_METHOD_MODIFIED_NAMESPACE;
281 }
282 }
283
284 /* Link the new entry into the parent and existing children */
285
286 Node->Peer = NULL;
287 Node->Parent = ParentNode;
288 ChildNode = ParentNode->Child;
289
290 if (!ChildNode)
291 {
292 ParentNode->Child = Node;
293 }
294 else
295 {
296 /* Add node to the end of the peer list */
297
298 while (ChildNode->Peer)
299 {
300 ChildNode = ChildNode->Peer;
301 }
302
303 ChildNode->Peer = Node;
304 }
305
306 /* Init the new entry */
307
308 Node->OwnerId = OwnerId;
309 Node->Type = (UINT8) Type;
310
311 ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
312 "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
313 AcpiUtGetNodeName (Node), AcpiUtGetTypeName (Node->Type), Node, OwnerId,
314 AcpiUtGetNodeName (ParentNode), AcpiUtGetTypeName (ParentNode->Type),
315 ParentNode));
316
317 return_VOID;
318 }
319
320
321 /*******************************************************************************
322 *
323 * FUNCTION: AcpiNsDeleteChildren
324 *
325 * PARAMETERS: ParentNode - Delete this objects children
326 *
327 * RETURN: None.
328 *
329 * DESCRIPTION: Delete all children of the parent object. In other words,
330 * deletes a "scope".
331 *
332 ******************************************************************************/
333
334 void
AcpiNsDeleteChildren(ACPI_NAMESPACE_NODE * ParentNode)335 AcpiNsDeleteChildren (
336 ACPI_NAMESPACE_NODE *ParentNode)
337 {
338 ACPI_NAMESPACE_NODE *NextNode;
339 ACPI_NAMESPACE_NODE *NodeToDelete;
340
341
342 ACPI_FUNCTION_TRACE_PTR (NsDeleteChildren, ParentNode);
343
344
345 if (!ParentNode)
346 {
347 return_VOID;
348 }
349
350 /* Deallocate all children at this level */
351
352 NextNode = ParentNode->Child;
353 while (NextNode)
354 {
355 /* Grandchildren should have all been deleted already */
356
357 if (NextNode->Child)
358 {
359 ACPI_ERROR ((AE_INFO, "Found a grandchild! P=%p C=%p",
360 ParentNode, NextNode));
361 }
362
363 /*
364 * Delete this child node and move on to the next child in the list.
365 * No need to unlink the node since we are deleting the entire branch.
366 */
367 NodeToDelete = NextNode;
368 NextNode = NextNode->Peer;
369 AcpiNsDeleteNode (NodeToDelete);
370 };
371
372 /* Clear the parent's child pointer */
373
374 ParentNode->Child = NULL;
375 return_VOID;
376 }
377
378
379 /*******************************************************************************
380 *
381 * FUNCTION: AcpiNsDeleteNamespaceSubtree
382 *
383 * PARAMETERS: ParentNode - Root of the subtree to be deleted
384 *
385 * RETURN: None.
386 *
387 * DESCRIPTION: Delete a subtree of the namespace. This includes all objects
388 * stored within the subtree.
389 *
390 ******************************************************************************/
391
392 void
AcpiNsDeleteNamespaceSubtree(ACPI_NAMESPACE_NODE * ParentNode)393 AcpiNsDeleteNamespaceSubtree (
394 ACPI_NAMESPACE_NODE *ParentNode)
395 {
396 ACPI_NAMESPACE_NODE *ChildNode = NULL;
397 UINT32 Level = 1;
398 ACPI_STATUS Status;
399
400
401 ACPI_FUNCTION_TRACE (NsDeleteNamespaceSubtree);
402
403
404 if (!ParentNode)
405 {
406 return_VOID;
407 }
408
409 /* Lock namespace for possible update */
410
411 Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
412 if (ACPI_FAILURE (Status))
413 {
414 return_VOID;
415 }
416
417 /*
418 * Traverse the tree of objects until we bubble back up
419 * to where we started.
420 */
421 while (Level > 0)
422 {
423 /* Get the next node in this scope (NULL if none) */
424
425 ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
426 if (ChildNode)
427 {
428 /* Found a child node - detach any attached object */
429
430 AcpiNsDetachObject (ChildNode);
431
432 /* Check if this node has any children */
433
434 if (ChildNode->Child)
435 {
436 /*
437 * There is at least one child of this node,
438 * visit the node
439 */
440 Level++;
441 ParentNode = ChildNode;
442 ChildNode = NULL;
443 }
444 }
445 else
446 {
447 /*
448 * No more children of this parent node.
449 * Move up to the grandparent.
450 */
451 Level--;
452
453 /*
454 * Now delete all of the children of this parent
455 * all at the same time.
456 */
457 AcpiNsDeleteChildren (ParentNode);
458
459 /* New "last child" is this parent node */
460
461 ChildNode = ParentNode;
462
463 /* Move up the tree to the grandparent */
464
465 ParentNode = ParentNode->Parent;
466 }
467 }
468
469 (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
470 return_VOID;
471 }
472
473
474 /*******************************************************************************
475 *
476 * FUNCTION: AcpiNsDeleteNamespaceByOwner
477 *
478 * PARAMETERS: OwnerId - All nodes with this owner will be deleted
479 *
480 * RETURN: Status
481 *
482 * DESCRIPTION: Delete entries within the namespace that are owned by a
483 * specific ID. Used to delete entire ACPI tables. All
484 * reference counts are updated.
485 *
486 * MUTEX: Locks namespace during deletion walk.
487 *
488 ******************************************************************************/
489
490 void
AcpiNsDeleteNamespaceByOwner(ACPI_OWNER_ID OwnerId)491 AcpiNsDeleteNamespaceByOwner (
492 ACPI_OWNER_ID OwnerId)
493 {
494 ACPI_NAMESPACE_NODE *ChildNode;
495 ACPI_NAMESPACE_NODE *DeletionNode;
496 ACPI_NAMESPACE_NODE *ParentNode;
497 UINT32 Level;
498 ACPI_STATUS Status;
499
500
501 ACPI_FUNCTION_TRACE_U32 (NsDeleteNamespaceByOwner, OwnerId);
502
503
504 if (OwnerId == 0)
505 {
506 return_VOID;
507 }
508
509 /* Lock namespace for possible update */
510
511 Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
512 if (ACPI_FAILURE (Status))
513 {
514 return_VOID;
515 }
516
517 DeletionNode = NULL;
518 ParentNode = AcpiGbl_RootNode;
519 ChildNode = NULL;
520 Level = 1;
521
522 /*
523 * Traverse the tree of nodes until we bubble back up
524 * to where we started.
525 */
526 while (Level > 0)
527 {
528 /*
529 * Get the next child of this parent node. When ChildNode is NULL,
530 * the first child of the parent is returned
531 */
532 ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
533
534 if (DeletionNode)
535 {
536 AcpiNsDeleteChildren (DeletionNode);
537 AcpiNsRemoveNode (DeletionNode);
538 DeletionNode = NULL;
539 }
540
541 if (ChildNode)
542 {
543 if (ChildNode->OwnerId == OwnerId)
544 {
545 /* Found a matching child node - detach any attached object */
546
547 AcpiNsDetachObject (ChildNode);
548 }
549
550 /* Check if this node has any children */
551
552 if (ChildNode->Child)
553 {
554 /*
555 * There is at least one child of this node,
556 * visit the node
557 */
558 Level++;
559 ParentNode = ChildNode;
560 ChildNode = NULL;
561 }
562 else if (ChildNode->OwnerId == OwnerId)
563 {
564 DeletionNode = ChildNode;
565 }
566 }
567 else
568 {
569 /*
570 * No more children of this parent node.
571 * Move up to the grandparent.
572 */
573 Level--;
574 if (Level != 0)
575 {
576 if (ParentNode->OwnerId == OwnerId)
577 {
578 DeletionNode = ParentNode;
579 }
580 }
581
582 /* New "last child" is this parent node */
583
584 ChildNode = ParentNode;
585
586 /* Move up the tree to the grandparent */
587
588 ParentNode = ParentNode->Parent;
589 }
590 }
591
592 (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
593 return_VOID;
594 }
595