sys/contrib/dev/acpica-unix/namespace/nsalloc.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nsalloc - Namespace allocation and deletion utilities
   4  *
   5  ******************************************************************************/
   6
   7 /******************************************************************************
   8  *
   9  * 1. Copyright Notice
  10  *
  11  * Some or all of this work - Copyright (c) 1999 - 2011, Intel Corp.
  12  * All rights reserved.
  13  *
  14  * 2. License
  15  *
  16  * 2.1. This is your license from Intel Corp. under its intellectual property
  17  * rights.  You may have additional license terms from the party that provided
  18  * you this software, covering your right to use that party's intellectual
  19  * property rights.
  20  *
  21  * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a
  22  * copy of the source code appearing in this file ("Covered Code") an
  23  * irrevocable, perpetual, worldwide license under Intel's copyrights in the
  24  * base code distributed originally by Intel ("Original Intel Code") to copy,
  25  * make derivatives, distribute, use and display any portion of the Covered
  26  * Code in any form, with the right to sublicense such rights; and
  27  *
  28  * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent
  29  * license (with the right to sublicense), under only those claims of Intel
  30  * patents that are infringed by the Original Intel Code, to make, use, sell,
  31  * offer to sell, and import the Covered Code and derivative works thereof
  32  * solely to the minimum extent necessary to exercise the above copyright
  33  * license, and in no event shall the patent license extend to any additions
  34  * to or modifications of the Original Intel Code.  No other license or right
  35  * is granted directly or by implication, estoppel or otherwise;
  36  *
  37  * The above copyright and patent license is granted only if the following
  38  * conditions are met:
  39  *
  40  * 3. Conditions
  41  *
  42  * 3.1. Redistribution of Source with Rights to Further Distribute Source.
  43  * Redistribution of source code of any substantial portion of the Covered
  44  * Code or modification with rights to further distribute source must include
  45  * the above Copyright Notice, the above License, this list of Conditions,
  46  * and the following Disclaimer and Export Compliance provision.  In addition,
  47  * Licensee must cause all Covered Code to which Licensee contributes to
  48  * contain a file documenting the changes Licensee made to create that Covered
  49  * Code and the date of any change.  Licensee must include in that file the
  50  * documentation of any changes made by any predecessor Licensee.  Licensee
  51  * must include a prominent statement that the modification is derived,
  52  * directly or indirectly, from Original Intel Code.
  53  *
  54  * 3.2. Redistribution of Source with no Rights to Further Distribute Source.
  55  * Redistribution of source code of any substantial portion of the Covered
  56  * Code or modification without rights to further distribute source must
  57  * include the following Disclaimer and Export Compliance provision in the
  58  * documentation and/or other materials provided with distribution.  In
  59  * addition, Licensee may not authorize further sublicense of source of any
  60  * portion of the Covered Code, and must include terms to the effect that the
  61  * license from Licensee to its licensee is limited to the intellectual
  62  * property embodied in the software Licensee provides to its licensee, and
  63  * not to intellectual property embodied in modifications its licensee may
  64  * make.
  65  *
  66  * 3.3. Redistribution of Executable. Redistribution in executable form of any
  67  * substantial portion of the Covered Code or modification must reproduce the
  68  * above Copyright Notice, and the following Disclaimer and Export Compliance
  69  * provision in the documentation and/or other materials provided with the
  70  * distribution.
  71  *
  72  * 3.4. Intel retains all right, title, and interest in and to the Original
  73  * Intel Code.
  74  *
  75  * 3.5. Neither the name Intel nor any other trademark owned or controlled by
  76  * Intel shall be used in advertising or otherwise to promote the sale, use or
  77  * other dealings in products derived from or relating to the Covered Code
  78  * without prior written authorization from Intel.
  79  *
  80  * 4. Disclaimer and Export Compliance
  81  *
  82  * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED
  83  * HERE.  ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE
  84  * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT,  ASSISTANCE,
  85  * INSTALLATION, TRAINING OR OTHER SERVICES.  INTEL WILL NOT PROVIDE ANY
  86  * UPDATES, ENHANCEMENTS OR EXTENSIONS.  INTEL SPECIFICALLY DISCLAIMS ANY
  87  * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A
  88  * PARTICULAR PURPOSE.
  89  *
  90  * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES
  91  * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR
  92  * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT,
  93  * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY
  94  * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL
  95  * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES.  THESE LIMITATIONS
  96  * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY
  97  * LIMITED REMEDY.
  98  *
  99  * 4.3. Licensee shall not export, either directly or indirectly, any of this
 100  * software or system incorporating such software without first obtaining any
 101  * required license or other approval from the U. S. Department of Commerce or
 102  * any other agency or department of the United States Government.  In the
 103  * event Licensee exports any such software from the United States or
 104  * re-exports any such software from a foreign destination, Licensee shall
 105  * ensure that the distribution and export/re-export of the software is in
 106  * compliance with all laws, regulations, orders, or other restrictions of the
 107  * U.S. Export Administration Regulations. Licensee agrees that neither it nor
 108  * any of its subsidiaries will export/re-export any technical data, process,
 109  * software, or service, directly or indirectly, to any country for which the
 110  * United States government or any agency thereof requires an export license,
 111  * other governmental approval, or letter of assurance, without first obtaining
 112  * such license, approval or letter.
 113  *
 114  *****************************************************************************/
 115
 116
 117 #define __NSALLOC_C__
 118
 119 #include "acpi.h"
 120 #include "accommon.h"
 121 #include "acnamesp.h"
 122
 123
 124 #define _COMPONENT          ACPI_NAMESPACE
 125         ACPI_MODULE_NAME    ("nsalloc")
 126
 127
 128 /*******************************************************************************
 129  *
 130  * FUNCTION:    AcpiNsCreateNode
 131  *
 132  * PARAMETERS:  Name            - Name of the new node (4 char ACPI name)
 133  *
 134  * RETURN:      New namespace node (Null on failure)
 135  *
 136  * DESCRIPTION: Create a namespace node
 137  *
 138  ******************************************************************************/
 139
 140 ACPI_NAMESPACE_NODE *
 141 AcpiNsCreateNode (
 142     UINT32                  Name)
 143 {
 144     ACPI_NAMESPACE_NODE     *Node;
 145 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
 146     UINT32                  Temp;
 147 #endif
 148
 149
 150     ACPI_FUNCTION_TRACE (NsCreateNode);
 151
 152
 153     Node = AcpiOsAcquireObject (AcpiGbl_NamespaceCache);
 154     if (!Node)
 155     {
 156         return_PTR (NULL);
 157     }
 158
 159     ACPI_MEM_TRACKING (AcpiGbl_NsNodeList->TotalAllocated++);
 160
 161 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
 162         Temp = AcpiGbl_NsNodeList->TotalAllocated -
 163                 AcpiGbl_NsNodeList->TotalFreed;
 164         if (Temp > AcpiGbl_NsNodeList->MaxOccupied)
 165         {
 166             AcpiGbl_NsNodeList->MaxOccupied = Temp;
 167         }
 168 #endif
 169
 170     Node->Name.Integer = Name;
 171     ACPI_SET_DESCRIPTOR_TYPE (Node, ACPI_DESC_TYPE_NAMED);
 172     return_PTR (Node);
 173 }
 174
 175
 176 /*******************************************************************************
 177  *
 178  * FUNCTION:    AcpiNsDeleteNode
 179  *
 180  * PARAMETERS:  Node            - Node to be deleted
 181  *
 182  * RETURN:      None
 183  *
 184  * DESCRIPTION: Delete a namespace node. All node deletions must come through
 185  *              here. Detaches any attached objects, including any attached
 186  *              data. If a handler is associated with attached data, it is
 187  *              invoked before the node is deleted.
 188  *
 189  ******************************************************************************/
 190
 191 void
 192 AcpiNsDeleteNode (
 193     ACPI_NAMESPACE_NODE     *Node)
 194 {
 195     ACPI_OPERAND_OBJECT     *ObjDesc;
 196
 197
 198     ACPI_FUNCTION_NAME (NsDeleteNode);
 199
 200
 201     /* Detach an object if there is one */
 202
 203     AcpiNsDetachObject (Node);
 204
 205     /*
 206      * Delete an attached data object if present (an object that was created
 207      * and attached via AcpiAttachData). Note: After any normal object is
 208      * detached above, the only possible remaining object is a data object.
 209      */
 210     ObjDesc = Node->Object;
 211     if (ObjDesc &&
 212         (ObjDesc->Common.Type == ACPI_TYPE_LOCAL_DATA))
 213     {
 214         /* Invoke the attached data deletion handler if present */
 215
 216         if (ObjDesc->Data.Handler)
 217         {
 218             ObjDesc->Data.Handler (Node, ObjDesc->Data.Pointer);
 219         }
 220
 221         AcpiUtRemoveReference (ObjDesc);
 222     }
 223
 224     /* Now we can delete the node */
 225
 226     (void) AcpiOsReleaseObject (AcpiGbl_NamespaceCache, Node);
 227
 228     ACPI_MEM_TRACKING (AcpiGbl_NsNodeList->TotalFreed++);
 229     ACPI_DEBUG_PRINT ((ACPI_DB_ALLOCATIONS, "Node %p, Remaining %X\n",
 230         Node, AcpiGbl_CurrentNodeCount));
 231 }
 232
 233
 234 /*******************************************************************************
 235  *
 236  * FUNCTION:    AcpiNsRemoveNode
 237  *
 238  * PARAMETERS:  Node            - Node to be removed/deleted
 239  *
 240  * RETURN:      None
 241  *
 242  * DESCRIPTION: Remove (unlink) and delete a namespace node
 243  *
 244  ******************************************************************************/
 245
 246 void
 247 AcpiNsRemoveNode (
 248     ACPI_NAMESPACE_NODE     *Node)
 249 {
 250     ACPI_NAMESPACE_NODE     *ParentNode;
 251     ACPI_NAMESPACE_NODE     *PrevNode;
 252     ACPI_NAMESPACE_NODE     *NextNode;
 253
 254
 255     ACPI_FUNCTION_TRACE_PTR (NsRemoveNode, Node);
 256
 257
 258     ParentNode = Node->Parent;
 259
 260     PrevNode = NULL;
 261     NextNode = ParentNode->Child;
 262
 263     /* Find the node that is the previous peer in the parent's child list */
 264
 265     while (NextNode != Node)
 266     {
 267         PrevNode = NextNode;
 268         NextNode = NextNode->Peer;
 269     }
 270
 271     if (PrevNode)
 272     {
 273         /* Node is not first child, unlink it */
 274
 275         PrevNode->Peer = Node->Peer;
 276     }
 277     else
 278     {
 279         /*
 280          * Node is first child (has no previous peer).
 281          * Link peer list to parent
 282          */
 283         ParentNode->Child = Node->Peer;
 284     }
 285
 286     /* Delete the node and any attached objects */
 287
 288     AcpiNsDeleteNode (Node);
 289     return_VOID;
 290 }
 291
 292
 293 /*******************************************************************************
 294  *
 295  * FUNCTION:    AcpiNsInstallNode
 296  *
 297  * PARAMETERS:  WalkState       - Current state of the walk
 298  *              ParentNode      - The parent of the new Node
 299  *              Node            - The new Node to install
 300  *              Type            - ACPI object type of the new Node
 301  *
 302  * RETURN:      None
 303  *
 304  * DESCRIPTION: Initialize a new namespace node and install it amongst
 305  *              its peers.
 306  *
 307  *              Note: Current namespace lookup is linear search. This appears
 308  *              to be sufficient as namespace searches consume only a small
 309  *              fraction of the execution time of the ACPI subsystem.
 310  *
 311  ******************************************************************************/
 312
 313 void
 314 AcpiNsInstallNode (
 315     ACPI_WALK_STATE         *WalkState,
 316     ACPI_NAMESPACE_NODE     *ParentNode,    /* Parent */
 317     ACPI_NAMESPACE_NODE     *Node,          /* New Child*/
 318     ACPI_OBJECT_TYPE        Type)
 319 {
 320     ACPI_OWNER_ID           OwnerId = 0;
 321     ACPI_NAMESPACE_NODE     *ChildNode;
 322
 323
 324     ACPI_FUNCTION_TRACE (NsInstallNode);
 325
 326
 327     if (WalkState)
 328     {
 329         /*
 330          * Get the owner ID from the Walk state. The owner ID is used to
 331          * track table deletion and deletion of objects created by methods.
 332          */
 333         OwnerId = WalkState->OwnerId;
 334
 335         if ((WalkState->MethodDesc) &&
 336             (ParentNode != WalkState->MethodNode))
 337         {
 338             /*
 339              * A method is creating a new node that is not a child of the
 340              * method (it is non-local). Mark the executing method as having
 341              * modified the namespace. This is used for cleanup when the
 342              * method exits.
 343              */
 344             WalkState->MethodDesc->Method.InfoFlags |= ACPI_METHOD_MODIFIED_NAMESPACE;
 345         }
 346     }
 347
 348     /* Link the new entry into the parent and existing children */
 349
 350     Node->Peer = NULL;
 351     Node->Parent = ParentNode;
 352     ChildNode = ParentNode->Child;
 353
 354     if (!ChildNode)
 355     {
 356         ParentNode->Child = Node;
 357     }
 358     else
 359     {
 360         /* Add node to the end of the peer list */
 361
 362         while (ChildNode->Peer)
 363         {
 364             ChildNode = ChildNode->Peer;
 365         }
 366
 367         ChildNode->Peer = Node;
 368     }
 369
 370     /* Init the new entry */
 371
 372     Node->OwnerId = OwnerId;
 373     Node->Type = (UINT8) Type;
 374
 375     ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 376         "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
 377         AcpiUtGetNodeName (Node), AcpiUtGetTypeName (Node->Type), Node, OwnerId,
 378         AcpiUtGetNodeName (ParentNode), AcpiUtGetTypeName (ParentNode->Type),
 379         ParentNode));
 380
 381     return_VOID;
 382 }
 383
 384
 385 /*******************************************************************************
 386  *
 387  * FUNCTION:    AcpiNsDeleteChildren
 388  *
 389  * PARAMETERS:  ParentNode      - Delete this objects children
 390  *
 391  * RETURN:      None.
 392  *
 393  * DESCRIPTION: Delete all children of the parent object. In other words,
 394  *              deletes a "scope".
 395  *
 396  ******************************************************************************/
 397
 398 void
 399 AcpiNsDeleteChildren (
 400     ACPI_NAMESPACE_NODE     *ParentNode)
 401 {
 402     ACPI_NAMESPACE_NODE     *NextNode;
 403     ACPI_NAMESPACE_NODE     *NodeToDelete;
 404
 405
 406     ACPI_FUNCTION_TRACE_PTR (NsDeleteChildren, ParentNode);
 407
 408
 409     if (!ParentNode)
 410     {
 411         return_VOID;
 412     }
 413
 414     /* Deallocate all children at this level */
 415
 416     NextNode = ParentNode->Child;
 417     while (NextNode)
 418     {
 419         /* Grandchildren should have all been deleted already */
 420
 421         if (NextNode->Child)
 422         {
 423             ACPI_ERROR ((AE_INFO, "Found a grandchild! P=%p C=%p",
 424                 ParentNode, NextNode));
 425         }
 426
 427         /*
 428          * Delete this child node and move on to the next child in the list.
 429          * No need to unlink the node since we are deleting the entire branch.
 430          */
 431         NodeToDelete = NextNode;
 432         NextNode = NextNode->Peer;
 433         AcpiNsDeleteNode (NodeToDelete);
 434     };
 435
 436     /* Clear the parent's child pointer */
 437
 438     ParentNode->Child = NULL;
 439     return_VOID;
 440 }
 441
 442
 443 /*******************************************************************************
 444  *
 445  * FUNCTION:    AcpiNsDeleteNamespaceSubtree
 446  *
 447  * PARAMETERS:  ParentNode      - Root of the subtree to be deleted
 448  *
 449  * RETURN:      None.
 450  *
 451  * DESCRIPTION: Delete a subtree of the namespace.  This includes all objects
 452  *              stored within the subtree.
 453  *
 454  ******************************************************************************/
 455
 456 void
 457 AcpiNsDeleteNamespaceSubtree (
 458     ACPI_NAMESPACE_NODE     *ParentNode)
 459 {
 460     ACPI_NAMESPACE_NODE     *ChildNode = NULL;
 461     UINT32                  Level = 1;
 462     ACPI_STATUS             Status;
 463
 464
 465     ACPI_FUNCTION_TRACE (NsDeleteNamespaceSubtree);
 466
 467
 468     if (!ParentNode)
 469     {
 470         return_VOID;
 471     }
 472
 473     /* Lock namespace for possible update */
 474
 475     Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
 476     if (ACPI_FAILURE (Status))
 477     {
 478         return_VOID;
 479     }
 480
 481     /*
 482      * Traverse the tree of objects until we bubble back up
 483      * to where we started.
 484      */
 485     while (Level > 0)
 486     {
 487         /* Get the next node in this scope (NULL if none) */
 488
 489         ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
 490         if (ChildNode)
 491         {
 492             /* Found a child node - detach any attached object */
 493
 494             AcpiNsDetachObject (ChildNode);
 495
 496             /* Check if this node has any children */
 497
 498             if (ChildNode->Child)
 499             {
 500                 /*
 501                  * There is at least one child of this node,
 502                  * visit the node
 503                  */
 504                 Level++;
 505                 ParentNode = ChildNode;
 506                 ChildNode  = NULL;
 507             }
 508         }
 509         else
 510         {
 511             /*
 512              * No more children of this parent node.
 513              * Move up to the grandparent.
 514              */
 515             Level--;
 516
 517             /*
 518              * Now delete all of the children of this parent
 519              * all at the same time.
 520              */
 521             AcpiNsDeleteChildren (ParentNode);
 522
 523             /* New "last child" is this parent node */
 524
 525             ChildNode = ParentNode;
 526
 527             /* Move up the tree to the grandparent */
 528
 529             ParentNode = ParentNode->Parent;
 530         }
 531     }
 532
 533     (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
 534     return_VOID;
 535 }
 536
 537
 538 /*******************************************************************************
 539  *
 540  * FUNCTION:    AcpiNsDeleteNamespaceByOwner
 541  *
 542  * PARAMETERS:  OwnerId     - All nodes with this owner will be deleted
 543  *
 544  * RETURN:      Status
 545  *
 546  * DESCRIPTION: Delete entries within the namespace that are owned by a
 547  *              specific ID.  Used to delete entire ACPI tables.  All
 548  *              reference counts are updated.
 549  *
 550  * MUTEX:       Locks namespace during deletion walk.
 551  *
 552  ******************************************************************************/
 553
 554 void
 555 AcpiNsDeleteNamespaceByOwner (
 556     ACPI_OWNER_ID            OwnerId)
 557 {
 558     ACPI_NAMESPACE_NODE     *ChildNode;
 559     ACPI_NAMESPACE_NODE     *DeletionNode;
 560     ACPI_NAMESPACE_NODE     *ParentNode;
 561     UINT32                  Level;
 562     ACPI_STATUS             Status;
 563
 564
 565     ACPI_FUNCTION_TRACE_U32 (NsDeleteNamespaceByOwner, OwnerId);
 566
 567
 568     if (OwnerId == 0)
 569     {
 570         return_VOID;
 571     }
 572
 573     /* Lock namespace for possible update */
 574
 575     Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
 576     if (ACPI_FAILURE (Status))
 577     {
 578         return_VOID;
 579     }
 580
 581     DeletionNode = NULL;
 582     ParentNode = AcpiGbl_RootNode;
 583     ChildNode = NULL;
 584     Level = 1;
 585
 586     /*
 587      * Traverse the tree of nodes until we bubble back up
 588      * to where we started.
 589      */
 590     while (Level > 0)
 591     {
 592         /*
 593          * Get the next child of this parent node. When ChildNode is NULL,
 594          * the first child of the parent is returned
 595          */
 596         ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
 597
 598         if (DeletionNode)
 599         {
 600             AcpiNsDeleteChildren (DeletionNode);
 601             AcpiNsRemoveNode (DeletionNode);
 602             DeletionNode = NULL;
 603         }
 604
 605         if (ChildNode)
 606         {
 607             if (ChildNode->OwnerId == OwnerId)
 608             {
 609                 /* Found a matching child node - detach any attached object */
 610
 611                 AcpiNsDetachObject (ChildNode);
 612             }
 613
 614             /* Check if this node has any children */
 615
 616             if (ChildNode->Child)
 617             {
 618                 /*
 619                  * There is at least one child of this node,
 620                  * visit the node
 621                  */
 622                 Level++;
 623                 ParentNode = ChildNode;
 624                 ChildNode  = NULL;
 625             }
 626             else if (ChildNode->OwnerId == OwnerId)
 627             {
 628                 DeletionNode = ChildNode;
 629             }
 630         }
 631         else
 632         {
 633             /*
 634              * No more children of this parent node.
 635              * Move up to the grandparent.
 636              */
 637             Level--;
 638             if (Level != 0)
 639             {
 640                 if (ParentNode->OwnerId == OwnerId)
 641                 {
 642                     DeletionNode = ParentNode;
 643                 }
 644             }
 645
 646             /* New "last child" is this parent node */
 647
 648             ChildNode = ParentNode;
 649
 650             /* Move up the tree to the grandparent */
 651
 652             ParentNode = ParentNode->Parent;
 653         }
 654     }
 655
 656     (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
 657     return_VOID;
 658 }
 659
 660