drivers/acpi/acpica/nsalloc.c

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