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