acpi/acpica/nsalloc.c

0001 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0
0002 /*******************************************************************************
0003  *
0004  * Module Name: nsalloc - Namespace allocation and deletion utilities
0005  *
0006  ******************************************************************************/
0007
0008 #include <acpi/acpi.h>
0009 #include "accommon.h"
0010 #include "acnamesp.h"
0011
0012 #define _COMPONENT          ACPI_NAMESPACE
0013 ACPI_MODULE_NAME("nsalloc")
0014
0015 /*******************************************************************************
0016  *
0017  * FUNCTION:    acpi_ns_create_node
0018  *
0019  * PARAMETERS:  name            - Name of the new node (4 char ACPI name)
0020  *
0021  * RETURN:      New namespace node (Null on failure)
0022  *
0023  * DESCRIPTION: Create a namespace node
0024  *
0025  ******************************************************************************/
0026 struct acpi_namespace_node *acpi_ns_create_node(u32 name)
0027 {
0028     struct acpi_namespace_node *node;
0029 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
0030     u32 temp;
0031 #endif
0032
0033     ACPI_FUNCTION_TRACE(ns_create_node);
0034
0035     node = acpi_os_acquire_object(acpi_gbl_namespace_cache);
0036     if (!node) {
0037         return_PTR(NULL);
0038     }
0039
0040     ACPI_MEM_TRACKING(acpi_gbl_ns_node_list->total_allocated++);
0041
0042 #ifdef ACPI_DBG_TRACK_ALLOCATIONS
0043     temp = acpi_gbl_ns_node_list->total_allocated -
0044         acpi_gbl_ns_node_list->total_freed;
0045     if (temp > acpi_gbl_ns_node_list->max_occupied) {
0046         acpi_gbl_ns_node_list->max_occupied = temp;
0047     }
0048 #endif
0049
0050     node->name.integer = name;
0051     ACPI_SET_DESCRIPTOR_TYPE(node, ACPI_DESC_TYPE_NAMED);
0052     return_PTR(node);
0053 }
0054
0055 /*******************************************************************************
0056  *
0057  * FUNCTION:    acpi_ns_delete_node
0058  *
0059  * PARAMETERS:  node            - Node to be deleted
0060  *
0061  * RETURN:      None
0062  *
0063  * DESCRIPTION: Delete a namespace node. All node deletions must come through
0064  *              here. Detaches any attached objects, including any attached
0065  *              data. If a handler is associated with attached data, it is
0066  *              invoked before the node is deleted.
0067  *
0068  ******************************************************************************/
0069
0070 void acpi_ns_delete_node(struct acpi_namespace_node *node)
0071 {
0072     union acpi_operand_object *obj_desc;
0073     union acpi_operand_object *next_desc;
0074
0075     ACPI_FUNCTION_NAME(ns_delete_node);
0076
0077     if (!node) {
0078         return_VOID;
0079     }
0080
0081     /* Detach an object if there is one */
0082
0083     acpi_ns_detach_object(node);
0084
0085     /*
0086      * Delete an attached data object list if present (objects that were
0087      * attached via acpi_attach_data). Note: After any normal object is
0088      * detached above, the only possible remaining object(s) are data
0089      * objects, in a linked list.
0090      */
0091     obj_desc = node->object;
0092     while (obj_desc && (obj_desc->common.type == ACPI_TYPE_LOCAL_DATA)) {
0093
0094         /* Invoke the attached data deletion handler if present */
0095
0096         if (obj_desc->data.handler) {
0097             obj_desc->data.handler(node, obj_desc->data.pointer);
0098         }
0099
0100         next_desc = obj_desc->common.next_object;
0101         acpi_ut_remove_reference(obj_desc);
0102         obj_desc = next_desc;
0103     }
0104
0105     /* Special case for the statically allocated root node */
0106
0107     if (node == acpi_gbl_root_node) {
0108         return;
0109     }
0110
0111     /* Now we can delete the node */
0112
0113     (void)acpi_os_release_object(acpi_gbl_namespace_cache, node);
0114
0115     ACPI_MEM_TRACKING(acpi_gbl_ns_node_list->total_freed++);
0116     ACPI_DEBUG_PRINT((ACPI_DB_ALLOCATIONS, "Node %p, Remaining %X\n",
0117               node, acpi_gbl_current_node_count));
0118 }
0119
0120 /*******************************************************************************
0121  *
0122  * FUNCTION:    acpi_ns_remove_node
0123  *
0124  * PARAMETERS:  node            - Node to be removed/deleted
0125  *
0126  * RETURN:      None
0127  *
0128  * DESCRIPTION: Remove (unlink) and delete a namespace node
0129  *
0130  ******************************************************************************/
0131
0132 void acpi_ns_remove_node(struct acpi_namespace_node *node)
0133 {
0134     struct acpi_namespace_node *parent_node;
0135     struct acpi_namespace_node *prev_node;
0136     struct acpi_namespace_node *next_node;
0137
0138     ACPI_FUNCTION_TRACE_PTR(ns_remove_node, node);
0139
0140     parent_node = node->parent;
0141
0142     prev_node = NULL;
0143     next_node = parent_node->child;
0144
0145     /* Find the node that is the previous peer in the parent's child list */
0146
0147     while (next_node != node) {
0148         prev_node = next_node;
0149         next_node = next_node->peer;
0150     }
0151
0152     if (prev_node) {
0153
0154         /* Node is not first child, unlink it */
0155
0156         prev_node->peer = node->peer;
0157     } else {
0158         /*
0159          * Node is first child (has no previous peer).
0160          * Link peer list to parent
0161          */
0162         parent_node->child = node->peer;
0163     }
0164
0165     /* Delete the node and any attached objects */
0166
0167     acpi_ns_delete_node(node);
0168     return_VOID;
0169 }
0170
0171 /*******************************************************************************
0172  *
0173  * FUNCTION:    acpi_ns_install_node
0174  *
0175  * PARAMETERS:  walk_state      - Current state of the walk
0176  *              parent_node     - The parent of the new Node
0177  *              node            - The new Node to install
0178  *              type            - ACPI object type of the new Node
0179  *
0180  * RETURN:      None
0181  *
0182  * DESCRIPTION: Initialize a new namespace node and install it amongst
0183  *              its peers.
0184  *
0185  *              Note: Current namespace lookup is linear search. This appears
0186  *              to be sufficient as namespace searches consume only a small
0187  *              fraction of the execution time of the ACPI subsystem.
0188  *
0189  ******************************************************************************/
0190
0191 void acpi_ns_install_node(struct acpi_walk_state *walk_state, struct acpi_namespace_node *parent_node,  /* Parent */
0192               struct acpi_namespace_node *node, /* New Child */
0193               acpi_object_type type)
0194 {
0195     acpi_owner_id owner_id = 0;
0196     struct acpi_namespace_node *child_node;
0197
0198     ACPI_FUNCTION_TRACE(ns_install_node);
0199
0200     if (walk_state) {
0201         /*
0202          * Get the owner ID from the Walk state. The owner ID is used to
0203          * track table deletion and deletion of objects created by methods.
0204          */
0205         owner_id = walk_state->owner_id;
0206
0207         if ((walk_state->method_desc) &&
0208             (parent_node != walk_state->method_node)) {
0209             /*
0210              * A method is creating a new node that is not a child of the
0211              * method (it is non-local). Mark the executing method as having
0212              * modified the namespace. This is used for cleanup when the
0213              * method exits.
0214              */
0215             walk_state->method_desc->method.info_flags |=
0216                 ACPI_METHOD_MODIFIED_NAMESPACE;
0217         }
0218     }
0219
0220     /* Link the new entry into the parent and existing children */
0221
0222     node->peer = NULL;
0223     node->parent = parent_node;
0224     child_node = parent_node->child;
0225
0226     if (!child_node) {
0227         parent_node->child = node;
0228     } else {
0229         /* Add node to the end of the peer list */
0230
0231         while (child_node->peer) {
0232             child_node = child_node->peer;
0233         }
0234
0235         child_node->peer = node;
0236     }
0237
0238     /* Init the new entry */
0239
0240     node->owner_id = owner_id;
0241     node->type = (u8) type;
0242
0243     ACPI_DEBUG_PRINT((ACPI_DB_NAMES,
0244               "%4.4s (%s) [Node %p Owner %3.3X] added to %4.4s (%s) [Node %p]\n",
0245               acpi_ut_get_node_name(node),
0246               acpi_ut_get_type_name(node->type), node, owner_id,
0247               acpi_ut_get_node_name(parent_node),
0248               acpi_ut_get_type_name(parent_node->type),
0249               parent_node));
0250
0251     return_VOID;
0252 }
0253
0254 /*******************************************************************************
0255  *
0256  * FUNCTION:    acpi_ns_delete_children
0257  *
0258  * PARAMETERS:  parent_node     - Delete this objects children
0259  *
0260  * RETURN:      None.
0261  *
0262  * DESCRIPTION: Delete all children of the parent object. In other words,
0263  *              deletes a "scope".
0264  *
0265  ******************************************************************************/
0266
0267 void acpi_ns_delete_children(struct acpi_namespace_node *parent_node)
0268 {
0269     struct acpi_namespace_node *next_node;
0270     struct acpi_namespace_node *node_to_delete;
0271
0272     ACPI_FUNCTION_TRACE_PTR(ns_delete_children, parent_node);
0273
0274     if (!parent_node) {
0275         return_VOID;
0276     }
0277
0278     /* Deallocate all children at this level */
0279
0280     next_node = parent_node->child;
0281     while (next_node) {
0282
0283         /* Grandchildren should have all been deleted already */
0284
0285         if (next_node->child) {
0286             ACPI_ERROR((AE_INFO, "Found a grandchild! P=%p C=%p",
0287                     parent_node, next_node));
0288         }
0289
0290         /*
0291          * Delete this child node and move on to the next child in the list.
0292          * No need to unlink the node since we are deleting the entire branch.
0293          */
0294         node_to_delete = next_node;
0295         next_node = next_node->peer;
0296         acpi_ns_delete_node(node_to_delete);
0297     }
0298
0299     /* Clear the parent's child pointer */
0300
0301     parent_node->child = NULL;
0302     return_VOID;
0303 }
0304
0305 /*******************************************************************************
0306  *
0307  * FUNCTION:    acpi_ns_delete_namespace_subtree
0308  *
0309  * PARAMETERS:  parent_node     - Root of the subtree to be deleted
0310  *
0311  * RETURN:      None.
0312  *
0313  * DESCRIPTION: Delete a subtree of the namespace. This includes all objects
0314  *              stored within the subtree.
0315  *
0316  ******************************************************************************/
0317
0318 void acpi_ns_delete_namespace_subtree(struct acpi_namespace_node *parent_node)
0319 {
0320     struct acpi_namespace_node *child_node = NULL;
0321     u32 level = 1;
0322     acpi_status status;
0323
0324     ACPI_FUNCTION_TRACE(ns_delete_namespace_subtree);
0325
0326     if (!parent_node) {
0327         return_VOID;
0328     }
0329
0330     /* Lock namespace for possible update */
0331
0332     status = acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE);
0333     if (ACPI_FAILURE(status)) {
0334         return_VOID;
0335     }
0336
0337     /*
0338      * Traverse the tree of objects until we bubble back up
0339      * to where we started.
0340      */
0341     while (level > 0) {
0342
0343         /* Get the next node in this scope (NULL if none) */
0344
0345         child_node = acpi_ns_get_next_node(parent_node, child_node);
0346         if (child_node) {
0347
0348             /* Found a child node - detach any attached object */
0349
0350             acpi_ns_detach_object(child_node);
0351
0352             /* Check if this node has any children */
0353
0354             if (child_node->child) {
0355                 /*
0356                  * There is at least one child of this node,
0357                  * visit the node
0358                  */
0359                 level++;
0360                 parent_node = child_node;
0361                 child_node = NULL;
0362             }
0363         } else {
0364             /*
0365              * No more children of this parent node.
0366              * Move up to the grandparent.
0367              */
0368             level--;
0369
0370             /*
0371              * Now delete all of the children of this parent
0372              * all at the same time.
0373              */
0374             acpi_ns_delete_children(parent_node);
0375
0376             /* New "last child" is this parent node */
0377
0378             child_node = parent_node;
0379
0380             /* Move up the tree to the grandparent */
0381
0382             parent_node = parent_node->parent;
0383         }
0384     }
0385
0386     (void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE);
0387     return_VOID;
0388 }
0389
0390 /*******************************************************************************
0391  *
0392  * FUNCTION:    acpi_ns_delete_namespace_by_owner
0393  *
0394  * PARAMETERS:  owner_id    - All nodes with this owner will be deleted
0395  *
0396  * RETURN:      Status
0397  *
0398  * DESCRIPTION: Delete entries within the namespace that are owned by a
0399  *              specific ID. Used to delete entire ACPI tables. All
0400  *              reference counts are updated.
0401  *
0402  * MUTEX:       Locks namespace during deletion walk.
0403  *
0404  ******************************************************************************/
0405
0406 void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id)
0407 {
0408     struct acpi_namespace_node *child_node;
0409     struct acpi_namespace_node *deletion_node;
0410     struct acpi_namespace_node *parent_node;
0411     u32 level;
0412     acpi_status status;
0413
0414     ACPI_FUNCTION_TRACE_U32(ns_delete_namespace_by_owner, owner_id);
0415
0416     if (owner_id == 0) {
0417         return_VOID;
0418     }
0419
0420     /* Lock namespace for possible update */
0421
0422     status = acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE);
0423     if (ACPI_FAILURE(status)) {
0424         return_VOID;
0425     }
0426
0427     deletion_node = NULL;
0428     parent_node = acpi_gbl_root_node;
0429     child_node = NULL;
0430     level = 1;
0431
0432     /*
0433      * Traverse the tree of nodes until we bubble back up
0434      * to where we started.
0435      */
0436     while (level > 0) {
0437         /*
0438          * Get the next child of this parent node. When child_node is NULL,
0439          * the first child of the parent is returned
0440          */
0441         child_node = acpi_ns_get_next_node(parent_node, child_node);
0442
0443         if (deletion_node) {
0444             acpi_ns_delete_children(deletion_node);
0445             acpi_ns_remove_node(deletion_node);
0446             deletion_node = NULL;
0447         }
0448
0449         if (child_node) {
0450             if (child_node->owner_id == owner_id) {
0451
0452                 /* Found a matching child node - detach any attached object */
0453
0454                 acpi_ns_detach_object(child_node);
0455             }
0456
0457             /* Check if this node has any children */
0458
0459             if (child_node->child) {
0460                 /*
0461                  * There is at least one child of this node,
0462                  * visit the node
0463                  */
0464                 level++;
0465                 parent_node = child_node;
0466                 child_node = NULL;
0467             } else if (child_node->owner_id == owner_id) {
0468                 deletion_node = child_node;
0469             }
0470         } else {
0471             /*
0472              * No more children of this parent node.
0473              * Move up to the grandparent.
0474              */
0475             level--;
0476             if (level != 0) {
0477                 if (parent_node->owner_id == owner_id) {
0478                     deletion_node = parent_node;
0479                 }
0480             }
0481
0482             /* New "last child" is this parent node */
0483
0484             child_node = parent_node;
0485
0486             /* Move up the tree to the grandparent */
0487
0488             parent_node = parent_node->parent;
0489         }
0490     }
0491
0492     (void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE);
0493     return_VOID;
0494 }