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