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