drivers/acpi/namespace/nsalloc.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nsalloc - Namespace allocation and deletion utilities
   4  *
   5  ******************************************************************************/
   6
   7 /*
   8  * Copyright (C) 2000 - 2005, R. Byron Moore
   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 #include <acpi/acpi.h>
  46 #include <acpi/acnamesp.h>
  47
  48
  49 #define _COMPONENT          ACPI_NAMESPACE
  50          ACPI_MODULE_NAME    ("nsalloc")
  51
  52 /* Local prototypes */
  53
  54 static void
  55 acpi_ns_remove_reference (
  56         struct acpi_namespace_node      *node);
  57
  58
  59 /*******************************************************************************
  60  *
  61  * FUNCTION:    acpi_ns_create_node
  62  *
  63  * PARAMETERS:  Name            - Name of the new node (4 char ACPI name)
  64  *
  65  * RETURN:      New namespace node (Null on failure)
  66  *
  67  * DESCRIPTION: Create a namespace node
  68  *
  69  ******************************************************************************/
  70
  71 struct acpi_namespace_node *
  72 acpi_ns_create_node (
  73         u32                             name)
  74 {
  75         struct acpi_namespace_node      *node;
  76
  77
  78         ACPI_FUNCTION_TRACE ("ns_create_node");
  79
  80
  81         node = ACPI_MEM_CALLOCATE (sizeof (struct acpi_namespace_node));
  82         if (!node) {
  83                 return_PTR (NULL);
  84         }
  85
  86         ACPI_MEM_TRACKING (acpi_gbl_ns_node_list->total_allocated++);
  87
  88         node->name.integer   = name;
  89         node->reference_count = 1;
  90         ACPI_SET_DESCRIPTOR_TYPE (node, ACPI_DESC_TYPE_NAMED);
  91
  92         return_PTR (node);
  93 }
  94
  95
  96 /*******************************************************************************
  97  *
  98  * FUNCTION:    acpi_ns_delete_node
  99  *
 100  * PARAMETERS:  Node            - Node to be deleted
 101  *
 102  * RETURN:      None
 103  *
 104  * DESCRIPTION: Delete a namespace node
 105  *
 106  ******************************************************************************/
 107
 108 void
 109 acpi_ns_delete_node (
 110         struct acpi_namespace_node      *node)
 111 {
 112         struct acpi_namespace_node      *parent_node;
 113         struct acpi_namespace_node      *prev_node;
 114         struct acpi_namespace_node      *next_node;
 115
 116
 117         ACPI_FUNCTION_TRACE_PTR ("ns_delete_node", node);
 118
 119
 120         parent_node = acpi_ns_get_parent_node (node);
 121
 122         prev_node = NULL;
 123         next_node = parent_node->child;
 124
 125         /* Find the node that is the previous peer in the parent's child list */
 126
 127         while (next_node != node) {
 128                 prev_node = next_node;
 129                 next_node = prev_node->peer;
 130         }
 131
 132         if (prev_node) {
 133                 /* Node is not first child, unlink it */
 134
 135                 prev_node->peer = next_node->peer;
 136                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 137                         prev_node->flags |= ANOBJ_END_OF_PEER_LIST;
 138                 }
 139         }
 140         else {
 141                 /* Node is first child (has no previous peer) */
 142
 143                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 144                         /* No peers at all */
 145
 146                         parent_node->child = NULL;
 147                 }
 148                 else {   /* Link peer list to parent */
 149
 150                         parent_node->child = next_node->peer;
 151                 }
 152         }
 153
 154         ACPI_MEM_TRACKING (acpi_gbl_ns_node_list->total_freed++);
 155
 156         /*
 157          * Detach an object if there is one then delete the node
 158          */
 159         acpi_ns_detach_object (node);
 160         ACPI_MEM_FREE (node);
 161         return_VOID;
 162 }
 163
 164
 165 /*******************************************************************************
 166  *
 167  * FUNCTION:    acpi_ns_install_node
 168  *
 169  * PARAMETERS:  walk_state      - Current state of the walk
 170  *              parent_node     - The parent of the new Node
 171  *              Node            - The new Node to install
 172  *              Type            - ACPI object type of the new Node
 173  *
 174  * RETURN:      None
 175  *
 176  * DESCRIPTION: Initialize a new namespace node and install it amongst
 177  *              its peers.
 178  *
 179  *              Note: Current namespace lookup is linear search. This appears
 180  *              to be sufficient as namespace searches consume only a small
 181  *              fraction of the execution time of the ACPI subsystem.
 182  *
 183  ******************************************************************************/
 184
 185 void
 186 acpi_ns_install_node (
 187         struct acpi_walk_state          *walk_state,
 188         struct acpi_namespace_node      *parent_node,   /* Parent */
 189         struct acpi_namespace_node      *node,          /* New Child*/
 190         acpi_object_type                type)
 191 {
 192         acpi_owner_id                   owner_id = 0;
 193         struct acpi_namespace_node      *child_node;
 194
 195
 196         ACPI_FUNCTION_TRACE ("ns_install_node");
 197
 198
 199         /*
 200          * Get the owner ID from the Walk state
 201          * The owner ID is used to track table deletion and
 202          * deletion of objects created by methods
 203          */
 204         if (walk_state) {
 205                 owner_id = walk_state->owner_id;
 206         }
 207
 208         /* Link the new entry into the parent and existing children */
 209
 210         child_node = parent_node->child;
 211         if (!child_node) {
 212                 parent_node->child = node;
 213                 node->flags |= ANOBJ_END_OF_PEER_LIST;
 214                 node->peer = parent_node;
 215         }
 216         else {
 217                 while (!(child_node->flags & ANOBJ_END_OF_PEER_LIST)) {
 218                         child_node = child_node->peer;
 219                 }
 220
 221                 child_node->peer = node;
 222
 223                 /* Clear end-of-list flag */
 224
 225                 child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
 226                 node->flags |= ANOBJ_END_OF_PEER_LIST;
 227                 node->peer = parent_node;
 228         }
 229
 230         /* Init the new entry */
 231
 232         node->owner_id = owner_id;
 233         node->type = (u8) type;
 234
 235         ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 236                 "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
 237                 acpi_ut_get_node_name (node), acpi_ut_get_type_name (node->type), node, owner_id,
 238                 acpi_ut_get_node_name (parent_node), acpi_ut_get_type_name (parent_node->type),
 239                 parent_node));
 240
 241         /*
 242          * Increment the reference count(s) of all parents up to
 243          * the root!
 244          */
 245         while ((node = acpi_ns_get_parent_node (node)) != NULL) {
 246                 node->reference_count++;
 247         }
 248
 249         return_VOID;
 250 }
 251
 252
 253 /*******************************************************************************
 254  *
 255  * FUNCTION:    acpi_ns_delete_children
 256  *
 257  * PARAMETERS:  parent_node     - Delete this objects children
 258  *
 259  * RETURN:      None.
 260  *
 261  * DESCRIPTION: Delete all children of the parent object. In other words,
 262  *              deletes a "scope".
 263  *
 264  ******************************************************************************/
 265
 266 void
 267 acpi_ns_delete_children (
 268         struct acpi_namespace_node      *parent_node)
 269 {
 270         struct acpi_namespace_node      *child_node;
 271         struct acpi_namespace_node      *next_node;
 272         struct acpi_namespace_node      *node;
 273         u8                              flags;
 274
 275
 276         ACPI_FUNCTION_TRACE_PTR ("ns_delete_children", parent_node);
 277
 278
 279         if (!parent_node) {
 280                 return_VOID;
 281         }
 282
 283         /* If no children, all done! */
 284
 285         child_node = parent_node->child;
 286         if (!child_node) {
 287                 return_VOID;
 288         }
 289
 290         /*
 291          * Deallocate all children at this level
 292          */
 293         do {
 294                 /* Get the things we need */
 295
 296                 next_node   = child_node->peer;
 297                 flags       = child_node->flags;
 298
 299                 /* Grandchildren should have all been deleted already */
 300
 301                 if (child_node->child) {
 302                         ACPI_DEBUG_PRINT ((ACPI_DB_ERROR, "Found a grandchild! P=%p C=%p\n",
 303                                 parent_node, child_node));
 304                 }
 305
 306                 /* Now we can free this child object */
 307
 308                 ACPI_MEM_TRACKING (acpi_gbl_ns_node_list->total_freed++);
 309
 310                 ACPI_DEBUG_PRINT ((ACPI_DB_ALLOCATIONS, "Object %p, Remaining %X\n",
 311                         child_node, acpi_gbl_current_node_count));
 312
 313                 /*
 314                  * Detach an object if there is one, then free the child node
 315                  */
 316                 acpi_ns_detach_object (child_node);
 317
 318                 /*
 319                  * Decrement the reference count(s) of all parents up to
 320                  * the root! (counts were incremented when the node was created)
 321                  */
 322                 node = child_node;
 323                 while ((node = acpi_ns_get_parent_node (node)) != NULL) {
 324                         node->reference_count--;
 325                 }
 326
 327                 /* There should be only one reference remaining on this node */
 328
 329                 if (child_node->reference_count != 1) {
 330                         ACPI_REPORT_WARNING ((
 331                                 "Existing references (%d) on node being deleted (%p)\n",
 332                                 child_node->reference_count, child_node));
 333                 }
 334
 335                 /* Now we can delete the node */
 336
 337                 ACPI_MEM_FREE (child_node);
 338
 339                 /* And move on to the next child in the list */
 340
 341                 child_node = next_node;
 342
 343         } while (!(flags & ANOBJ_END_OF_PEER_LIST));
 344
 345
 346         /* Clear the parent's child pointer */
 347
 348         parent_node->child = NULL;
 349
 350         return_VOID;
 351 }
 352
 353
 354 /*******************************************************************************
 355  *
 356  * FUNCTION:    acpi_ns_delete_namespace_subtree
 357  *
 358  * PARAMETERS:  parent_node     - Root of the subtree to be deleted
 359  *
 360  * RETURN:      None.
 361  *
 362  * DESCRIPTION: Delete a subtree of the namespace.  This includes all objects
 363  *              stored within the subtree.
 364  *
 365  ******************************************************************************/
 366
 367 void
 368 acpi_ns_delete_namespace_subtree (
 369         struct acpi_namespace_node      *parent_node)
 370 {
 371         struct acpi_namespace_node      *child_node = NULL;
 372         u32                             level = 1;
 373
 374
 375         ACPI_FUNCTION_TRACE ("ns_delete_namespace_subtree");
 376
 377
 378         if (!parent_node) {
 379                 return_VOID;
 380         }
 381
 382         /*
 383          * Traverse the tree of objects until we bubble back up
 384          * to where we started.
 385          */
 386         while (level > 0) {
 387                 /* Get the next node in this scope (NULL if none) */
 388
 389                 child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node,
 390                                  child_node);
 391                 if (child_node) {
 392                         /* Found a child node - detach any attached object */
 393
 394                         acpi_ns_detach_object (child_node);
 395
 396                         /* Check if this node has any children */
 397
 398                         if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, NULL)) {
 399                                 /*
 400                                  * There is at least one child of this node,
 401                                  * visit the node
 402                                  */
 403                                 level++;
 404                                 parent_node = child_node;
 405                                 child_node = NULL;
 406                         }
 407                 }
 408                 else {
 409                         /*
 410                          * No more children of this parent node.
 411                          * Move up to the grandparent.
 412                          */
 413                         level--;
 414
 415                         /*
 416                          * Now delete all of the children of this parent
 417                          * all at the same time.
 418                          */
 419                         acpi_ns_delete_children (parent_node);
 420
 421                         /* New "last child" is this parent node */
 422
 423                         child_node = parent_node;
 424
 425                         /* Move up the tree to the grandparent */
 426
 427                         parent_node = acpi_ns_get_parent_node (parent_node);
 428                 }
 429         }
 430
 431         return_VOID;
 432 }
 433
 434
 435 /*******************************************************************************
 436  *
 437  * FUNCTION:    acpi_ns_remove_reference
 438  *
 439  * PARAMETERS:  Node           - Named node whose reference count is to be
 440  *                               decremented
 441  *
 442  * RETURN:      None.
 443  *
 444  * DESCRIPTION: Remove a Node reference.  Decrements the reference count
 445  *              of all parent Nodes up to the root.  Any node along
 446  *              the way that reaches zero references is freed.
 447  *
 448  ******************************************************************************/
 449
 450 static void
 451 acpi_ns_remove_reference (
 452         struct acpi_namespace_node      *node)
 453 {
 454         struct acpi_namespace_node      *parent_node;
 455         struct acpi_namespace_node      *this_node;
 456
 457
 458         ACPI_FUNCTION_ENTRY ();
 459
 460
 461         /*
 462          * Decrement the reference count(s) of this node and all
 463          * nodes up to the root,  Delete anything with zero remaining references.
 464          */
 465         this_node = node;
 466         while (this_node) {
 467                 /* Prepare to move up to parent */
 468
 469                 parent_node = acpi_ns_get_parent_node (this_node);
 470
 471                 /* Decrement the reference count on this node */
 472
 473                 this_node->reference_count--;
 474
 475                 /* Delete the node if no more references */
 476
 477                 if (!this_node->reference_count) {
 478                         /* Delete all children and delete the node */
 479
 480                         acpi_ns_delete_children (this_node);
 481                         acpi_ns_delete_node (this_node);
 482                 }
 483
 484                 this_node = parent_node;
 485         }
 486 }
 487
 488
 489 /*******************************************************************************
 490  *
 491  * FUNCTION:    acpi_ns_delete_namespace_by_owner
 492  *
 493  * PARAMETERS:  owner_id    - All nodes with this owner will be deleted
 494  *
 495  * RETURN:      Status
 496  *
 497  * DESCRIPTION: Delete entries within the namespace that are owned by a
 498  *              specific ID.  Used to delete entire ACPI tables.  All
 499  *              reference counts are updated.
 500  *
 501  ******************************************************************************/
 502
 503 void
 504 acpi_ns_delete_namespace_by_owner (
 505         acpi_owner_id                    owner_id)
 506 {
 507         struct acpi_namespace_node      *child_node;
 508         struct acpi_namespace_node      *deletion_node;
 509         u32                             level;
 510         struct acpi_namespace_node      *parent_node;
 511
 512
 513         ACPI_FUNCTION_TRACE_U32 ("ns_delete_namespace_by_owner", owner_id);
 514
 515
 516         if (owner_id == 0) {
 517                 return_VOID;
 518         }
 519
 520         parent_node   = acpi_gbl_root_node;
 521         child_node    = NULL;
 522         deletion_node = 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                  * Get the next child of this parent node. When child_node is NULL,
 532                  * the first child of the parent is returned
 533                  */
 534                 child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node, child_node);
 535
 536                 if (deletion_node) {
 537                         acpi_ns_remove_reference (deletion_node);
 538                         deletion_node = NULL;
 539                 }
 540
 541                 if (child_node) {
 542                         if (child_node->owner_id == owner_id) {
 543                                 /* Found a matching child node - detach any attached object */
 544
 545                                 acpi_ns_detach_object (child_node);
 546                         }
 547
 548                         /* Check if this node has any children */
 549
 550                         if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, NULL)) {
 551                                 /*
 552                                  * There is at least one child of this node,
 553                                  * visit the node
 554                                  */
 555                                 level++;
 556                                 parent_node = child_node;
 557                                 child_node = NULL;
 558                         }
 559                         else if (child_node->owner_id == owner_id) {
 560                                 deletion_node = child_node;
 561                         }
 562                 }
 563                 else {
 564                         /*
 565                          * No more children of this parent node.
 566                          * Move up to the grandparent.
 567                          */
 568                         level--;
 569                         if (level != 0) {
 570                                 if (parent_node->owner_id == owner_id) {
 571                                         deletion_node = parent_node;
 572                                 }
 573                         }
 574
 575                         /* New "last child" is this parent node */
 576
 577                         child_node = parent_node;
 578
 579                         /* Move up the tree to the grandparent */
 580
 581                         parent_node = acpi_ns_get_parent_node (parent_node);
 582                 }
 583         }
 584
 585         return_VOID;
 586 }
 587
 588