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