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 } 491