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

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