drivers/acpi/namespace/nsalloc.c

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