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