reactos/drivers/bus/acpi/acpica/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 - 2009, 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 = AcpiNsGetParentNode (Node);
 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 = PrevNode->Peer;
 269     }
 270
 271     if (PrevNode)
 272     {
 273         /* Node is not first child, unlink it */
 274
 275         PrevNode->Peer = NextNode->Peer;
 276         if (NextNode->Flags & ANOBJ_END_OF_PEER_LIST)
 277         {
 278             PrevNode->Flags |= ANOBJ_END_OF_PEER_LIST;
 279         }
 280     }
 281     else
 282     {
 283         /* Node is first child (has no previous peer) */
 284
 285         if (NextNode->Flags & ANOBJ_END_OF_PEER_LIST)
 286         {
 287             /* No peers at all */
 288
 289             ParentNode->Child = NULL;
 290         }
 291         else
 292         {   /* Link peer list to parent */
 293
 294             ParentNode->Child = NextNode->Peer;
 295         }
 296     }
 297
 298     /* Delete the node and any attached objects */
 299
 300     AcpiNsDeleteNode (Node);
 301     return_VOID;
 302 }
 303
 304
 305 /*******************************************************************************
 306  *
 307  * FUNCTION:    AcpiNsInstallNode
 308  *
 309  * PARAMETERS:  WalkState       - Current state of the walk
 310  *              ParentNode      - The parent of the new Node
 311  *              Node            - The new Node to install
 312  *              Type            - ACPI object type of the new Node
 313  *
 314  * RETURN:      None
 315  *
 316  * DESCRIPTION: Initialize a new namespace node and install it amongst
 317  *              its peers.
 318  *
 319  *              Note: Current namespace lookup is linear search. This appears
 320  *              to be sufficient as namespace searches consume only a small
 321  *              fraction of the execution time of the ACPI subsystem.
 322  *
 323  ******************************************************************************/
 324
 325 void
 326 AcpiNsInstallNode (
 327     ACPI_WALK_STATE         *WalkState,
 328     ACPI_NAMESPACE_NODE     *ParentNode,    /* Parent */
 329     ACPI_NAMESPACE_NODE     *Node,          /* New Child*/
 330     ACPI_OBJECT_TYPE        Type)
 331 {
 332     ACPI_OWNER_ID           OwnerId = 0;
 333     ACPI_NAMESPACE_NODE     *ChildNode;
 334
 335
 336     ACPI_FUNCTION_TRACE (NsInstallNode);
 337
 338
 339     /*
 340      * Get the owner ID from the Walk state. The owner ID is used to track
 341      * table deletion and deletion of objects created by methods.
 342      */
 343     if (WalkState)
 344     {
 345         OwnerId = WalkState->OwnerId;
 346     }
 347
 348     /* Link the new entry into the parent and existing children */
 349
 350     ChildNode = ParentNode->Child;
 351     if (!ChildNode)
 352     {
 353         ParentNode->Child = Node;
 354         Node->Flags |= ANOBJ_END_OF_PEER_LIST;
 355         Node->Peer = ParentNode;
 356     }
 357     else
 358     {
 359         while (!(ChildNode->Flags & ANOBJ_END_OF_PEER_LIST))
 360         {
 361             ChildNode = ChildNode->Peer;
 362         }
 363
 364         ChildNode->Peer = Node;
 365
 366         /* Clear end-of-list flag */
 367
 368         ChildNode->Flags &= ~ANOBJ_END_OF_PEER_LIST;
 369         Node->Flags |= ANOBJ_END_OF_PEER_LIST;
 370         Node->Peer = ParentNode;
 371     }
 372
 373     /* Init the new entry */
 374
 375     Node->OwnerId = OwnerId;
 376     Node->Type = (UINT8) Type;
 377
 378     ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 379         "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
 380         AcpiUtGetNodeName (Node), AcpiUtGetTypeName (Node->Type), Node, OwnerId,
 381         AcpiUtGetNodeName (ParentNode), AcpiUtGetTypeName (ParentNode->Type),
 382         ParentNode));
 383
 384     return_VOID;
 385 }
 386
 387
 388 /*******************************************************************************
 389  *
 390  * FUNCTION:    AcpiNsDeleteChildren
 391  *
 392  * PARAMETERS:  ParentNode      - Delete this objects children
 393  *
 394  * RETURN:      None.
 395  *
 396  * DESCRIPTION: Delete all children of the parent object. In other words,
 397  *              deletes a "scope".
 398  *
 399  ******************************************************************************/
 400
 401 void
 402 AcpiNsDeleteChildren (
 403     ACPI_NAMESPACE_NODE     *ParentNode)
 404 {
 405     ACPI_NAMESPACE_NODE     *ChildNode;
 406     ACPI_NAMESPACE_NODE     *NextNode;
 407     UINT8                   Flags;
 408
 409
 410     ACPI_FUNCTION_TRACE_PTR (NsDeleteChildren, ParentNode);
 411
 412
 413     if (!ParentNode)
 414     {
 415         return_VOID;
 416     }
 417
 418     /* If no children, all done! */
 419
 420     ChildNode = ParentNode->Child;
 421     if (!ChildNode)
 422     {
 423         return_VOID;
 424     }
 425
 426     /* Deallocate all children at this level */
 427
 428     do
 429     {
 430         /* Get the things we need */
 431
 432         NextNode = ChildNode->Peer;
 433         Flags = ChildNode->Flags;
 434
 435         /* Grandchildren should have all been deleted already */
 436
 437         if (ChildNode->Child)
 438         {
 439             ACPI_ERROR ((AE_INFO, "Found a grandchild! P=%p C=%p",
 440                 ParentNode, ChildNode));
 441         }
 442
 443         /*
 444          * Delete this child node and move on to the next child in the list.
 445          * No need to unlink the node since we are deleting the entire branch.
 446          */
 447         AcpiNsDeleteNode (ChildNode);
 448         ChildNode = NextNode;
 449
 450     } while (!(Flags & ANOBJ_END_OF_PEER_LIST));
 451
 452     /* Clear the parent's child pointer */
 453
 454     ParentNode->Child = NULL;
 455     return_VOID;
 456 }
 457
 458
 459 /*******************************************************************************
 460  *
 461  * FUNCTION:    AcpiNsDeleteNamespaceSubtree
 462  *
 463  * PARAMETERS:  ParentNode      - Root of the subtree to be deleted
 464  *
 465  * RETURN:      None.
 466  *
 467  * DESCRIPTION: Delete a subtree of the namespace.  This includes all objects
 468  *              stored within the subtree.
 469  *
 470  ******************************************************************************/
 471
 472 void
 473 AcpiNsDeleteNamespaceSubtree (
 474     ACPI_NAMESPACE_NODE     *ParentNode)
 475 {
 476     ACPI_NAMESPACE_NODE     *ChildNode = NULL;
 477     UINT32                  Level = 1;
 478
 479
 480     ACPI_FUNCTION_TRACE (NsDeleteNamespaceSubtree);
 481
 482
 483     if (!ParentNode)
 484     {
 485         return_VOID;
 486     }
 487
 488     /*
 489      * Traverse the tree of objects until we bubble back up
 490      * to where we started.
 491      */
 492     while (Level > 0)
 493     {
 494         /* Get the next node in this scope (NULL if none) */
 495
 496         ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
 497         if (ChildNode)
 498         {
 499             /* Found a child node - detach any attached object */
 500
 501             AcpiNsDetachObject (ChildNode);
 502
 503             /* Check if this node has any children */
 504
 505             if (ChildNode->Child)
 506             {
 507                 /*
 508                  * There is at least one child of this node,
 509                  * visit the node
 510                  */
 511                 Level++;
 512                 ParentNode = ChildNode;
 513                 ChildNode  = NULL;
 514             }
 515         }
 516         else
 517         {
 518             /*
 519              * No more children of this parent node.
 520              * Move up to the grandparent.
 521              */
 522             Level--;
 523
 524             /*
 525              * Now delete all of the children of this parent
 526              * all at the same time.
 527              */
 528             AcpiNsDeleteChildren (ParentNode);
 529
 530             /* New "last child" is this parent node */
 531
 532             ChildNode = ParentNode;
 533
 534             /* Move up the tree to the grandparent */
 535
 536             ParentNode = AcpiNsGetParentNode (ParentNode);
 537         }
 538     }
 539
 540     return_VOID;
 541 }
 542
 543
 544 /*******************************************************************************
 545  *
 546  * FUNCTION:    AcpiNsDeleteNamespaceByOwner
 547  *
 548  * PARAMETERS:  OwnerId     - All nodes with this owner will be deleted
 549  *
 550  * RETURN:      Status
 551  *
 552  * DESCRIPTION: Delete entries within the namespace that are owned by a
 553  *              specific ID.  Used to delete entire ACPI tables.  All
 554  *              reference counts are updated.
 555  *
 556  * MUTEX:       Locks namespace during deletion walk.
 557  *
 558  ******************************************************************************/
 559
 560 void
 561 AcpiNsDeleteNamespaceByOwner (
 562     ACPI_OWNER_ID            OwnerId)
 563 {
 564     ACPI_NAMESPACE_NODE     *ChildNode;
 565     ACPI_NAMESPACE_NODE     *DeletionNode;
 566     ACPI_NAMESPACE_NODE     *ParentNode;
 567     UINT32                  Level;
 568     ACPI_STATUS             Status;
 569
 570
 571     ACPI_FUNCTION_TRACE_U32 (NsDeleteNamespaceByOwner, OwnerId);
 572
 573
 574     if (OwnerId == 0)
 575     {
 576         return_VOID;
 577     }
 578
 579     /* Lock namespace for possible update */
 580
 581     Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
 582     if (ACPI_FAILURE (Status))
 583     {
 584         return_VOID;
 585     }
 586
 587     DeletionNode = NULL;
 588     ParentNode = AcpiGbl_RootNode;
 589     ChildNode = NULL;
 590     Level = 1;
 591
 592     /*
 593      * Traverse the tree of nodes until we bubble back up
 594      * to where we started.
 595      */
 596     while (Level > 0)
 597     {
 598         /*
 599          * Get the next child of this parent node. When ChildNode is NULL,
 600          * the first child of the parent is returned
 601          */
 602         ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
 603
 604         if (DeletionNode)
 605         {
 606             AcpiNsDeleteChildren (DeletionNode);
 607             AcpiNsRemoveNode (DeletionNode);
 608             DeletionNode = NULL;
 609         }
 610
 611         if (ChildNode)
 612         {
 613             if (ChildNode->OwnerId == OwnerId)
 614             {
 615                 /* Found a matching child node - detach any attached object */
 616
 617                 AcpiNsDetachObject (ChildNode);
 618             }
 619
 620             /* Check if this node has any children */
 621
 622             if (ChildNode->Child)
 623             {
 624                 /*
 625                  * There is at least one child of this node,
 626                  * visit the node
 627                  */
 628                 Level++;
 629                 ParentNode = ChildNode;
 630                 ChildNode  = NULL;
 631             }
 632             else if (ChildNode->OwnerId == OwnerId)
 633             {
 634                 DeletionNode = ChildNode;
 635             }
 636         }
 637         else
 638         {
 639             /*
 640              * No more children of this parent node.
 641              * Move up to the grandparent.
 642              */
 643             Level--;
 644             if (Level != 0)
 645             {
 646                 if (ParentNode->OwnerId == OwnerId)
 647                 {
 648                     DeletionNode = ParentNode;
 649                 }
 650             }
 651
 652             /* New "last child" is this parent node */
 653
 654             ChildNode = ParentNode;
 655
 656             /* Move up the tree to the grandparent */
 657
 658             ParentNode = AcpiNsGetParentNode (ParentNode);
 659         }
 660     }
 661
 662     (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
 663     return_VOID;
 664 }
 665
 666