sys/contrib/dev/acpica/components/namespace/nsalloc.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nsalloc - Namespace allocation and deletion utilities
   4  *
   5  ******************************************************************************/
   6
   7 /*
   8  * Copyright (C) 2000 - 2013, 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 <contrib/dev/acpica/include/acpi.h>
  48 #include <contrib/dev/acpica/include/accommon.h>
  49 #include <contrib/dev/acpica/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 }