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
  53 /*******************************************************************************
  54  *
  55  * FUNCTION:    acpi_ns_create_node
  56  *
  57  * PARAMETERS:  acpi_name       - Name of the new node
  58  *
  59  * RETURN:      None
  60  *
  61  * DESCRIPTION: Create a namespace node
  62  *
  63  ******************************************************************************/
  64
  65 struct acpi_namespace_node *
  66 acpi_ns_create_node (
  67         u32                             name)
  68 {
  69         struct acpi_namespace_node      *node;
  70
  71
  72         ACPI_FUNCTION_TRACE ("ns_create_node");
  73
  74
  75         node = ACPI_MEM_CALLOCATE (sizeof (struct acpi_namespace_node));
  76         if (!node) {
  77                 return_PTR (NULL);
  78         }
  79
  80         ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_allocated++);
  81
  82         node->name.integer   = name;
  83         node->reference_count = 1;
  84         ACPI_SET_DESCRIPTOR_TYPE (node, ACPI_DESC_TYPE_NAMED);
  85
  86         return_PTR (node);
  87 }
  88
  89
  90 /*******************************************************************************
  91  *
  92  * FUNCTION:    acpi_ns_delete_node
  93  *
  94  * PARAMETERS:  Node            - Node to be deleted
  95  *
  96  * RETURN:      None
  97  *
  98  * DESCRIPTION: Delete a namespace node
  99  *
 100  ******************************************************************************/
 101
 102 void
 103 acpi_ns_delete_node (
 104         struct acpi_namespace_node      *node)
 105 {
 106         struct acpi_namespace_node      *parent_node;
 107         struct acpi_namespace_node      *prev_node;
 108         struct acpi_namespace_node      *next_node;
 109
 110
 111         ACPI_FUNCTION_TRACE_PTR ("ns_delete_node", node);
 112
 113
 114         parent_node = acpi_ns_get_parent_node (node);
 115
 116         prev_node = NULL;
 117         next_node = parent_node->child;
 118
 119         /* Find the node that is the previous peer in the parent's child list */
 120
 121         while (next_node != node) {
 122                 prev_node = next_node;
 123                 next_node = prev_node->peer;
 124         }
 125
 126         if (prev_node) {
 127                 /* Node is not first child, unlink it */
 128
 129                 prev_node->peer = next_node->peer;
 130                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 131                         prev_node->flags |= ANOBJ_END_OF_PEER_LIST;
 132                 }
 133         }
 134         else {
 135                 /* Node is first child (has no previous peer) */
 136
 137                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 138                         /* No peers at all */
 139
 140                         parent_node->child = NULL;
 141                 }
 142                 else {   /* Link peer list to parent */
 143
 144                         parent_node->child = next_node->peer;
 145                 }
 146         }
 147
 148
 149         ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_freed++);
 150
 151         /*
 152          * Detach an object if there is one then delete the node
 153          */
 154         acpi_ns_detach_object (node);
 155         ACPI_MEM_FREE (node);
 156         return_VOID;
 157 }
 158
 159
 160 #ifdef ACPI_ALPHABETIC_NAMESPACE
 161 /*******************************************************************************
 162  *
 163  * FUNCTION:    acpi_ns_compare_names
 164  *
 165  * PARAMETERS:  Name1           - First name to compare
 166  *              Name2           - Second name to compare
 167  *
 168  * RETURN:      value from strncmp
 169  *
 170  * DESCRIPTION: Compare two ACPI names.  Names that are prefixed with an
 171  *              underscore are forced to be alphabetically first.
 172  *
 173  ******************************************************************************/
 174
 175 int
 176 acpi_ns_compare_names (
 177         char                            *name1,
 178         char                            *name2)
 179 {
 180         char                            reversed_name1[ACPI_NAME_SIZE];
 181         char                            reversed_name2[ACPI_NAME_SIZE];
 182         u32                             i;
 183         u32                             j;
 184
 185
 186         /*
 187          * Replace all instances of "underscore" with a value that is smaller so
 188          * that all names that are prefixed with underscore(s) are alphabetically
 189          * first.
 190          *
 191          * Reverse the name bytewise so we can just do a 32-bit compare instead
 192          * of a strncmp.
 193          */
 194         for (i = 0, j= (ACPI_NAME_SIZE - 1); i < ACPI_NAME_SIZE; i++, j--) {
 195                 reversed_name1[j] = name1[i];
 196                 if (name1[i] == '_') {
 197                         reversed_name1[j] = '*';
 198                 }
 199
 200                 reversed_name2[j] = name2[i];
 201                 if (name2[i] == '_') {
 202                         reversed_name2[j] = '*';
 203                 }
 204         }
 205
 206         return (*(int *) reversed_name1 - *(int *) reversed_name2);
 207 }
 208 #endif
 209
 210
 211 /*******************************************************************************
 212  *
 213  * FUNCTION:    acpi_ns_install_node
 214  *
 215  * PARAMETERS:  walk_state      - Current state of the walk
 216  *              parent_node     - The parent of the new Node
 217  *              Node            - The new Node to install
 218  *              Type            - ACPI object type of the new Node
 219  *
 220  * RETURN:      None
 221  *
 222  * DESCRIPTION: Initialize a new namespace node and install it amongst
 223  *              its peers.
 224  *
 225  *              Note: Current namespace lookup is linear search.  However, the
 226  *              nodes are linked in alphabetical order to 1) put all reserved
 227  *              names (start with underscore) first, and to 2) make a readable
 228  *              namespace dump.
 229  *
 230  ******************************************************************************/
 231
 232 void
 233 acpi_ns_install_node (
 234         struct acpi_walk_state          *walk_state,
 235         struct acpi_namespace_node      *parent_node,   /* Parent */
 236         struct acpi_namespace_node      *node,          /* New Child*/
 237         acpi_object_type                type)
 238 {
 239         u16                             owner_id = 0;
 240         struct acpi_namespace_node      *child_node;
 241 #ifdef ACPI_ALPHABETIC_NAMESPACE
 242
 243         struct acpi_namespace_node      *previous_child_node;
 244 #endif
 245
 246
 247         ACPI_FUNCTION_TRACE ("ns_install_node");
 248
 249
 250         /*
 251          * Get the owner ID from the Walk state
 252          * The owner ID is used to track table deletion and
 253          * deletion of objects created by methods
 254          */
 255         if (walk_state) {
 256                 owner_id = walk_state->owner_id;
 257         }
 258
 259         /* Link the new entry into the parent and existing children */
 260
 261         child_node = parent_node->child;
 262         if (!child_node) {
 263                 parent_node->child = node;
 264                 node->flags |= ANOBJ_END_OF_PEER_LIST;
 265                 node->peer = parent_node;
 266         }
 267         else {
 268 #ifdef ACPI_ALPHABETIC_NAMESPACE
 269                 /*
 270                  * Walk the list whilst searching for the correct
 271                  * alphabetic placement.
 272                  */
 273                 previous_child_node = NULL;
 274                 while (acpi_ns_compare_names (acpi_ut_get_node_name (child_node), acpi_ut_get_node_name (node)) < 0) {
 275                         if (child_node->flags & ANOBJ_END_OF_PEER_LIST) {
 276                                 /* Last peer;  Clear end-of-list flag */
 277
 278                                 child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
 279
 280                                 /* This node is the new peer to the child node */
 281
 282                                 child_node->peer = node;
 283
 284                                 /* This node is the new end-of-list */
 285
 286                                 node->flags |= ANOBJ_END_OF_PEER_LIST;
 287                                 node->peer = parent_node;
 288                                 break;
 289                         }
 290
 291                         /* Get next peer */
 292
 293                         previous_child_node = child_node;
 294                         child_node = child_node->peer;
 295                 }
 296
 297                 /* Did the node get inserted at the end-of-list? */
 298
 299                 if (!(node->flags & ANOBJ_END_OF_PEER_LIST)) {
 300                         /*
 301                          * Loop above terminated without reaching the end-of-list.
 302                          * Insert the new node at the current location
 303                          */
 304                         if (previous_child_node) {
 305                                 /* Insert node alphabetically */
 306
 307                                 node->peer = child_node;
 308                                 previous_child_node->peer = node;
 309                         }
 310                         else {
 311                                 /* Insert node alphabetically at start of list */
 312
 313                                 node->peer = child_node;
 314                                 parent_node->child = node;
 315                         }
 316                 }
 317 #else
 318                 while (!(child_node->flags & ANOBJ_END_OF_PEER_LIST)) {
 319                         child_node = child_node->peer;
 320                 }
 321
 322                 child_node->peer = node;
 323
 324                 /* Clear end-of-list flag */
 325
 326                 child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
 327                 node->flags     |= ANOBJ_END_OF_PEER_LIST;
 328                 node->peer = parent_node;
 329 #endif
 330         }
 331
 332         /* Init the new entry */
 333
 334         node->owner_id = owner_id;
 335         node->type = (u8) type;
 336
 337         ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
 338                 "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
 339                 acpi_ut_get_node_name (node), acpi_ut_get_type_name (node->type), node, owner_id,
 340                 acpi_ut_get_node_name (parent_node), acpi_ut_get_type_name (parent_node->type),
 341                 parent_node));
 342
 343         /*
 344          * Increment the reference count(s) of all parents up to
 345          * the root!
 346          */
 347         while ((node = acpi_ns_get_parent_node (node)) != NULL) {
 348                 node->reference_count++;
 349         }
 350
 351         return_VOID;
 352 }
 353
 354
 355 /*******************************************************************************
 356  *
 357  * FUNCTION:    acpi_ns_delete_children
 358  *
 359  * PARAMETERS:  parent_node     - Delete this objects children
 360  *
 361  * RETURN:      None.
 362  *
 363  * DESCRIPTION: Delete all children of the parent object. In other words,
 364  *              deletes a "scope".
 365  *
 366  ******************************************************************************/
 367
 368 void
 369 acpi_ns_delete_children (
 370         struct acpi_namespace_node      *parent_node)
 371 {
 372         struct acpi_namespace_node      *child_node;
 373         struct acpi_namespace_node      *next_node;
 374         struct acpi_namespace_node      *node;
 375         u8                              flags;
 376
 377
 378         ACPI_FUNCTION_TRACE_PTR ("ns_delete_children", parent_node);
 379
 380
 381         if (!parent_node) {
 382                 return_VOID;
 383         }
 384
 385         /* If no children, all done! */
 386
 387         child_node = parent_node->child;
 388         if (!child_node) {
 389                 return_VOID;
 390         }
 391
 392         /*
 393          * Deallocate all children at this level
 394          */
 395         do {
 396                 /* Get the things we need */
 397
 398                 next_node   = child_node->peer;
 399                 flags       = child_node->flags;
 400
 401                 /* Grandchildren should have all been deleted already */
 402
 403                 if (child_node->child) {
 404                         ACPI_DEBUG_PRINT ((ACPI_DB_ERROR, "Found a grandchild! P=%p C=%p\n",
 405                                 parent_node, child_node));
 406                 }
 407
 408                 /* Now we can free this child object */
 409
 410                 ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_freed++);
 411
 412                 ACPI_DEBUG_PRINT ((ACPI_DB_ALLOCATIONS, "Object %p, Remaining %X\n",
 413                         child_node, acpi_gbl_current_node_count));
 414
 415                 /*
 416                  * Detach an object if there is one, then free the child node
 417                  */
 418                 acpi_ns_detach_object (child_node);
 419
 420                 /*
 421                  * Decrement the reference count(s) of all parents up to
 422                  * the root! (counts were incremented when the node was created)
 423                  */
 424                 node = child_node;
 425                 while ((node = acpi_ns_get_parent_node (node)) != NULL) {
 426                         node->reference_count--;
 427                 }
 428
 429                 /* There should be only one reference remaining on this node */
 430
 431                 if (child_node->reference_count != 1) {
 432                         ACPI_REPORT_WARNING (("Existing references (%d) on node being deleted (%p)\n",
 433                                 child_node->reference_count, child_node));
 434                 }
 435
 436                 /* Now we can delete the node */
 437
 438                 ACPI_MEM_FREE (child_node);
 439
 440                 /* And move on to the next child in the list */
 441
 442                 child_node = next_node;
 443
 444         } while (!(flags & ANOBJ_END_OF_PEER_LIST));
 445
 446
 447         /* Clear the parent's child pointer */
 448
 449         parent_node->child = NULL;
 450
 451         return_VOID;
 452 }
 453
 454
 455 /*******************************************************************************
 456  *
 457  * FUNCTION:    acpi_ns_delete_namespace_subtree
 458  *
 459  * PARAMETERS:  parent_node     - Root of the subtree to be deleted
 460  *
 461  * RETURN:      None.
 462  *
 463  * DESCRIPTION: Delete a subtree of the namespace.  This includes all objects
 464  *              stored within the subtree.
 465  *
 466  ******************************************************************************/
 467
 468 void
 469 acpi_ns_delete_namespace_subtree (
 470         struct acpi_namespace_node      *parent_node)
 471 {
 472         struct acpi_namespace_node      *child_node = NULL;
 473         u32                             level = 1;
 474
 475
 476         ACPI_FUNCTION_TRACE ("ns_delete_namespace_subtree");
 477
 478
 479         if (!parent_node) {
 480                 return_VOID;
 481         }
 482
 483         /*
 484          * Traverse the tree of objects until we bubble back up
 485          * to where we started.
 486          */
 487         while (level > 0) {
 488                 /* Get the next node in this scope (NULL if none) */
 489
 490                 child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node,
 491                                  child_node);
 492                 if (child_node) {
 493                         /* Found a child node - detach any attached object */
 494
 495                         acpi_ns_detach_object (child_node);
 496
 497                         /* Check if this node has any children */
 498
 499                         if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, NULL)) {
 500                                 /*
 501                                  * There is at least one child of this node,
 502                                  * visit the node
 503                                  */
 504                                 level++;
 505                                 parent_node = child_node;
 506                                 child_node = NULL;
 507                         }
 508                 }
 509                 else {
 510                         /*
 511                          * No more children of this parent node.
 512                          * Move up to the grandparent.
 513                          */
 514                         level--;
 515
 516                         /*
 517                          * Now delete all of the children of this parent
 518                          * all at the same time.
 519                          */
 520                         acpi_ns_delete_children (parent_node);
 521
 522                         /* New "last child" is this parent node */
 523
 524                         child_node = parent_node;
 525
 526                         /* Move up the tree to the grandparent */
 527
 528                         parent_node = acpi_ns_get_parent_node (parent_node);
 529                 }
 530         }
 531
 532         return_VOID;
 533 }
 534
 535
 536 /*******************************************************************************
 537  *
 538  * FUNCTION:    acpi_ns_remove_reference
 539  *
 540  * PARAMETERS:  Node           - Named node whose reference count is to be
 541  *                               decremented
 542  *
 543  * RETURN:      None.
 544  *
 545  * DESCRIPTION: Remove a Node reference.  Decrements the reference count
 546  *              of all parent Nodes up to the root.  Any node along
 547  *              the way that reaches zero references is freed.
 548  *
 549  ******************************************************************************/
 550
 551 void
 552 acpi_ns_remove_reference (
 553         struct acpi_namespace_node      *node)
 554 {
 555         struct acpi_namespace_node      *parent_node;
 556         struct acpi_namespace_node      *this_node;
 557
 558
 559         ACPI_FUNCTION_ENTRY ();
 560
 561
 562         /*
 563          * Decrement the reference count(s) of this node and all
 564          * nodes up to the root,  Delete anything with zero remaining references.
 565          */
 566         this_node = node;
 567         while (this_node) {
 568                 /* Prepare to move up to parent */
 569
 570                 parent_node = acpi_ns_get_parent_node (this_node);
 571
 572                 /* Decrement the reference count on this node */
 573
 574                 this_node->reference_count--;
 575
 576                 /* Delete the node if no more references */
 577
 578                 if (!this_node->reference_count) {
 579                         /* Delete all children and delete the node */
 580
 581                         acpi_ns_delete_children (this_node);
 582                         acpi_ns_delete_node (this_node);
 583                 }
 584
 585                 this_node = parent_node;
 586         }
 587 }
 588
 589
 590 /*******************************************************************************
 591  *
 592  * FUNCTION:    acpi_ns_delete_namespace_by_owner
 593  *
 594  * PARAMETERS:  owner_id    - All nodes with this owner will be deleted
 595  *
 596  * RETURN:      Status
 597  *
 598  * DESCRIPTION: Delete entries within the namespace that are owned by a
 599  *              specific ID.  Used to delete entire ACPI tables.  All
 600  *              reference counts are updated.
 601  *
 602  ******************************************************************************/
 603
 604 void
 605 acpi_ns_delete_namespace_by_owner (
 606         u16                             owner_id)
 607 {
 608         struct acpi_namespace_node      *child_node;
 609         struct acpi_namespace_node      *deletion_node;
 610         u32                             level;
 611         struct acpi_namespace_node      *parent_node;
 612
 613
 614         ACPI_FUNCTION_TRACE_U32 ("ns_delete_namespace_by_owner", owner_id);
 615
 616
 617         parent_node   = acpi_gbl_root_node;
 618         child_node    = NULL;
 619         deletion_node = NULL;
 620         level         = 1;
 621
 622         /*
 623          * Traverse the tree of nodes until we bubble back up
 624          * to where we started.
 625          */
 626         while (level > 0) {
 627                 /*
 628                  * Get the next child of this parent node. When child_node is NULL,
 629                  * the first child of the parent is returned
 630                  */
 631                 child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node, child_node);
 632
 633                 if (deletion_node) {
 634                         acpi_ns_remove_reference (deletion_node);
 635                         deletion_node = NULL;
 636                 }
 637
 638                 if (child_node) {
 639                         if (child_node->owner_id == owner_id) {
 640                                 /* Found a matching child node - detach any attached object */
 641
 642                                 acpi_ns_detach_object (child_node);
 643                         }
 644
 645                         /* Check if this node has any children */
 646
 647                         if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, NULL)) {
 648                                 /*
 649                                  * There is at least one child of this node,
 650                                  * visit the node
 651                                  */
 652                                 level++;
 653                                 parent_node = child_node;
 654                                 child_node = NULL;
 655                         }
 656                         else if (child_node->owner_id == owner_id) {
 657                                 deletion_node = child_node;
 658                         }
 659                 }
 660                 else {
 661                         /*
 662                          * No more children of this parent node.
 663                          * Move up to the grandparent.
 664                          */
 665                         level--;
 666                         if (level != 0) {
 667                                 if (parent_node->owner_id == owner_id) {
 668                                         deletion_node = parent_node;
 669                                 }
 670                         }
 671
 672                         /* New "last child" is this parent node */
 673
 674                         child_node = parent_node;
 675
 676                         /* Move up the tree to the grandparent */
 677
 678                         parent_node = acpi_ns_get_parent_node (parent_node);
 679                 }
 680         }
 681
 682         return_VOID;
 683 }
 684
 685