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