1 /******************************************************************************* 2 * 3 * Module Name: nsalloc - Namespace allocation and deletion utilities 4 * 5 ******************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2010, 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.flags |= 238 AOPOBJ_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 345 ACPI_FUNCTION_TRACE(ns_delete_namespace_subtree); 346 347 if (!parent_node) { 348 return_VOID; 349 } 350 351 /* 352 * Traverse the tree of objects until we bubble back up 353 * to where we started. 354 */ 355 while (level > 0) { 356 357 /* Get the next node in this scope (NULL if none) */ 358 359 child_node = acpi_ns_get_next_node(parent_node, child_node); 360 if (child_node) { 361 362 /* Found a child node - detach any attached object */ 363 364 acpi_ns_detach_object(child_node); 365 366 /* Check if this node has any children */ 367 368 if (child_node->child) { 369 /* 370 * There is at least one child of this node, 371 * visit the node 372 */ 373 level++; 374 parent_node = child_node; 375 child_node = NULL; 376 } 377 } else { 378 /* 379 * No more children of this parent node. 380 * Move up to the grandparent. 381 */ 382 level--; 383 384 /* 385 * Now delete all of the children of this parent 386 * all at the same time. 387 */ 388 acpi_ns_delete_children(parent_node); 389 390 /* New "last child" is this parent node */ 391 392 child_node = parent_node; 393 394 /* Move up the tree to the grandparent */ 395 396 parent_node = parent_node->parent; 397 } 398 } 399 400 return_VOID; 401 } 402 403 /******************************************************************************* 404 * 405 * FUNCTION: acpi_ns_delete_namespace_by_owner 406 * 407 * PARAMETERS: owner_id - All nodes with this owner will be deleted 408 * 409 * RETURN: Status 410 * 411 * DESCRIPTION: Delete entries within the namespace that are owned by a 412 * specific ID. Used to delete entire ACPI tables. All 413 * reference counts are updated. 414 * 415 * MUTEX: Locks namespace during deletion walk. 416 * 417 ******************************************************************************/ 418 419 void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id) 420 { 421 struct acpi_namespace_node *child_node; 422 struct acpi_namespace_node *deletion_node; 423 struct acpi_namespace_node *parent_node; 424 u32 level; 425 acpi_status status; 426 427 ACPI_FUNCTION_TRACE_U32(ns_delete_namespace_by_owner, owner_id); 428 429 if (owner_id == 0) { 430 return_VOID; 431 } 432 433 /* Lock namespace for possible update */ 434 435 status = acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE); 436 if (ACPI_FAILURE(status)) { 437 return_VOID; 438 } 439 440 deletion_node = NULL; 441 parent_node = acpi_gbl_root_node; 442 child_node = NULL; 443 level = 1; 444 445 /* 446 * Traverse the tree of nodes until we bubble back up 447 * to where we started. 448 */ 449 while (level > 0) { 450 /* 451 * Get the next child of this parent node. When child_node is NULL, 452 * the first child of the parent is returned 453 */ 454 child_node = acpi_ns_get_next_node(parent_node, child_node); 455 456 if (deletion_node) { 457 acpi_ns_delete_children(deletion_node); 458 acpi_ns_remove_node(deletion_node); 459 deletion_node = NULL; 460 } 461 462 if (child_node) { 463 if (child_node->owner_id == owner_id) { 464 465 /* Found a matching child node - detach any attached object */ 466 467 acpi_ns_detach_object(child_node); 468 } 469 470 /* Check if this node has any children */ 471 472 if (child_node->child) { 473 /* 474 * There is at least one child of this node, 475 * visit the node 476 */ 477 level++; 478 parent_node = child_node; 479 child_node = NULL; 480 } else if (child_node->owner_id == owner_id) { 481 deletion_node = child_node; 482 } 483 } else { 484 /* 485 * No more children of this parent node. 486 * Move up to the grandparent. 487 */ 488 level--; 489 if (level != 0) { 490 if (parent_node->owner_id == owner_id) { 491 deletion_node = parent_node; 492 } 493 } 494 495 /* New "last child" is this parent node */ 496 497 child_node = parent_node; 498 499 /* Move up the tree to the grandparent */ 500 501 parent_node = parent_node->parent; 502 } 503 } 504 505 (void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE); 506 return_VOID; 507 } 508