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