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 * 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 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 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 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 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 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 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