drivers/acpi/acpica/nsalloc.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nsalloc - Namespace allocation and deletion utilities
   4  *
   5  ******************************************************************************/
   6
   7 /*
   8  * Copyright (C) 2000 - 2008, 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 = acpi_ns_get_parent_node(node);
 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 = prev_node->peer;
 172         }
 173
 174         if (prev_node) {
 175
 176                 /* Node is not first child, unlink it */
 177
 178                 prev_node->peer = next_node->peer;
 179                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 180                         prev_node->flags |= ANOBJ_END_OF_PEER_LIST;
 181                 }
 182         } else {
 183                 /* Node is first child (has no previous peer) */
 184
 185                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 186
 187                         /* No peers at all */
 188
 189                         parent_node->child = NULL;
 190                 } else {        /* Link peer list to parent */
 191
 192                         parent_node->child = next_node->peer;
 193                 }
 194         }
 195
 196         /* Delete the node and any attached objects */
 197
 198         acpi_ns_delete_node(node);
 199         return_VOID;
 200 }
 201
 202 /*******************************************************************************
 203  *
 204  * FUNCTION:    acpi_ns_install_node
 205  *
 206  * PARAMETERS:  walk_state      - Current state of the walk
 207  *              parent_node     - The parent of the new Node
 208  *              Node            - The new Node to install
 209  *              Type            - ACPI object type of the new Node
 210  *
 211  * RETURN:      None
 212  *
 213  * DESCRIPTION: Initialize a new namespace node and install it amongst
 214  *              its peers.
 215  *
 216  *              Note: Current namespace lookup is linear search. This appears
 217  *              to be sufficient as namespace searches consume only a small
 218  *              fraction of the execution time of the ACPI subsystem.
 219  *
 220  ******************************************************************************/
 221
 222 void acpi_ns_install_node(struct acpi_walk_state *walk_state, struct acpi_namespace_node *parent_node,  /* Parent */
 223                           struct acpi_namespace_node *node,     /* New Child */
 224                           acpi_object_type type)
 225 {
 226         acpi_owner_id owner_id = 0;
 227         struct acpi_namespace_node *child_node;
 228
 229         ACPI_FUNCTION_TRACE(ns_install_node);
 230
 231         /*
 232          * Get the owner ID from the Walk state. The owner ID is used to track
 233          * table deletion and deletion of objects created by methods.
 234          */
 235         if (walk_state) {
 236                 owner_id = walk_state->owner_id;
 237         }
 238
 239         /* Link the new entry into the parent and existing children */
 240
 241         child_node = parent_node->child;
 242         if (!child_node) {
 243                 parent_node->child = node;
 244                 node->flags |= ANOBJ_END_OF_PEER_LIST;
 245                 node->peer = parent_node;
 246         } else {
 247                 while (!(child_node->flags & ANOBJ_END_OF_PEER_LIST)) {
 248                         child_node = child_node->peer;
 249                 }
 250
 251                 child_node->peer = node;
 252
 253                 /* Clear end-of-list flag */
 254
 255                 child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
 256                 node->flags |= ANOBJ_END_OF_PEER_LIST;
 257                 node->peer = parent_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 *child_node;
 292         struct acpi_namespace_node *next_node;
 293         u8 flags;
 294
 295         ACPI_FUNCTION_TRACE_PTR(ns_delete_children, parent_node);
 296
 297         if (!parent_node) {
 298                 return_VOID;
 299         }
 300
 301         /* If no children, all done! */
 302
 303         child_node = parent_node->child;
 304         if (!child_node) {
 305                 return_VOID;
 306         }
 307
 308         /* Deallocate all children at this level */
 309
 310         do {
 311
 312                 /* Get the things we need */
 313
 314                 next_node = child_node->peer;
 315                 flags = child_node->flags;
 316
 317                 /* Grandchildren should have all been deleted already */
 318
 319                 if (child_node->child) {
 320                         ACPI_ERROR((AE_INFO, "Found a grandchild! P=%p C=%p",
 321                                     parent_node, child_node));
 322                 }
 323
 324                 /*
 325                  * Delete this child node and move on to the next child in the list.
 326                  * No need to unlink the node since we are deleting the entire branch.
 327                  */
 328                 acpi_ns_delete_node(child_node);
 329                 child_node = next_node;
 330
 331         } while (!(flags & ANOBJ_END_OF_PEER_LIST));
 332
 333         /* Clear the parent's child pointer */
 334
 335         parent_node->child = NULL;
 336         return_VOID;
 337 }
 338
 339 /*******************************************************************************
 340  *
 341  * FUNCTION:    acpi_ns_delete_namespace_subtree
 342  *
 343  * PARAMETERS:  parent_node     - Root of the subtree to be deleted
 344  *
 345  * RETURN:      None.
 346  *
 347  * DESCRIPTION: Delete a subtree of the namespace.  This includes all objects
 348  *              stored within the subtree.
 349  *
 350  ******************************************************************************/
 351
 352 void acpi_ns_delete_namespace_subtree(struct acpi_namespace_node *parent_node)
 353 {
 354         struct acpi_namespace_node *child_node = NULL;
 355         u32 level = 1;
 356
 357         ACPI_FUNCTION_TRACE(ns_delete_namespace_subtree);
 358
 359         if (!parent_node) {
 360                 return_VOID;
 361         }
 362
 363         /*
 364          * Traverse the tree of objects until we bubble back up
 365          * to where we started.
 366          */
 367         while (level > 0) {
 368
 369                 /* Get the next node in this scope (NULL if none) */
 370
 371                 child_node = acpi_ns_get_next_node(parent_node, child_node);
 372                 if (child_node) {
 373
 374                         /* Found a child node - detach any attached object */
 375
 376                         acpi_ns_detach_object(child_node);
 377
 378                         /* Check if this node has any children */
 379
 380                         if (child_node->child) {
 381                                 /*
 382                                  * There is at least one child of this node,
 383                                  * visit the node
 384                                  */
 385                                 level++;
 386                                 parent_node = child_node;
 387                                 child_node = NULL;
 388                         }
 389                 } else {
 390                         /*
 391                          * No more children of this parent node.
 392                          * Move up to the grandparent.
 393                          */
 394                         level--;
 395
 396                         /*
 397                          * Now delete all of the children of this parent
 398                          * all at the same time.
 399                          */
 400                         acpi_ns_delete_children(parent_node);
 401
 402                         /* New "last child" is this parent node */
 403
 404                         child_node = parent_node;
 405
 406                         /* Move up the tree to the grandparent */
 407
 408                         parent_node = acpi_ns_get_parent_node(parent_node);
 409                 }
 410         }
 411
 412         return_VOID;
 413 }
 414
 415 /*******************************************************************************
 416  *
 417  * FUNCTION:    acpi_ns_delete_namespace_by_owner
 418  *
 419  * PARAMETERS:  owner_id    - All nodes with this owner will be deleted
 420  *
 421  * RETURN:      Status
 422  *
 423  * DESCRIPTION: Delete entries within the namespace that are owned by a
 424  *              specific ID.  Used to delete entire ACPI tables.  All
 425  *              reference counts are updated.
 426  *
 427  * MUTEX:       Locks namespace during deletion walk.
 428  *
 429  ******************************************************************************/
 430
 431 void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id)
 432 {
 433         struct acpi_namespace_node *child_node;
 434         struct acpi_namespace_node *deletion_node;
 435         struct acpi_namespace_node *parent_node;
 436         u32 level;
 437         acpi_status status;
 438
 439         ACPI_FUNCTION_TRACE_U32(ns_delete_namespace_by_owner, owner_id);
 440
 441         if (owner_id == 0) {
 442                 return_VOID;
 443         }
 444
 445         /* Lock namespace for possible update */
 446
 447         status = acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE);
 448         if (ACPI_FAILURE(status)) {
 449                 return_VOID;
 450         }
 451
 452         deletion_node = NULL;
 453         parent_node = acpi_gbl_root_node;
 454         child_node = NULL;
 455         level = 1;
 456
 457         /*
 458          * Traverse the tree of nodes until we bubble back up
 459          * to where we started.
 460          */
 461         while (level > 0) {
 462                 /*
 463                  * Get the next child of this parent node. When child_node is NULL,
 464                  * the first child of the parent is returned
 465                  */
 466                 child_node = acpi_ns_get_next_node(parent_node, child_node);
 467
 468                 if (deletion_node) {
 469                         acpi_ns_delete_children(deletion_node);
 470                         acpi_ns_remove_node(deletion_node);
 471                         deletion_node = NULL;
 472                 }
 473
 474                 if (child_node) {
 475                         if (child_node->owner_id == owner_id) {
 476
 477                                 /* Found a matching child node - detach any attached object */
 478
 479                                 acpi_ns_detach_object(child_node);
 480                         }
 481
 482                         /* Check if this node has any children */
 483
 484                         if (child_node->child) {
 485                                 /*
 486                                  * There is at least one child of this node,
 487                                  * visit the node
 488                                  */
 489                                 level++;
 490                                 parent_node = child_node;
 491                                 child_node = NULL;
 492                         } else if (child_node->owner_id == owner_id) {
 493                                 deletion_node = child_node;
 494                         }
 495                 } else {
 496                         /*
 497                          * No more children of this parent node.
 498                          * Move up to the grandparent.
 499                          */
 500                         level--;
 501                         if (level != 0) {
 502                                 if (parent_node->owner_id == owner_id) {
 503                                         deletion_node = parent_node;
 504                                 }
 505                         }
 506
 507                         /* New "last child" is this parent node */
 508
 509                         child_node = parent_node;
 510
 511                         /* Move up the tree to the grandparent */
 512
 513                         parent_node = acpi_ns_get_parent_node(parent_node);
 514                 }
 515         }
 516
 517         (void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE);
 518         return_VOID;
 519 }