drivers/acpi/acpica/nsalloc.c

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