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