1 /******************************************************************************* 2 * 3 * Module Name: nsalloc - Namespace allocation and deletion utilities 4 * 5 ******************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2008, 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 = acpi_ns_get_parent_node(node); 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 = prev_node->peer; 172 } 173 174 if (prev_node) { 175 176 /* Node is not first child, unlink it */ 177 178 prev_node->peer = next_node->peer; 179 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) { 180 prev_node->flags |= ANOBJ_END_OF_PEER_LIST; 181 } 182 } else { 183 /* Node is first child (has no previous peer) */ 184 185 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) { 186 187 /* No peers at all */ 188 189 parent_node->child = NULL; 190 } else { /* Link peer list to parent */ 191 192 parent_node->child = next_node->peer; 193 } 194 } 195 196 /* Delete the node and any attached objects */ 197 198 acpi_ns_delete_node(node); 199 return_VOID; 200 } 201 202 /******************************************************************************* 203 * 204 * FUNCTION: acpi_ns_install_node 205 * 206 * PARAMETERS: walk_state - Current state of the walk 207 * parent_node - The parent of the new Node 208 * Node - The new Node to install 209 * Type - ACPI object type of the new Node 210 * 211 * RETURN: None 212 * 213 * DESCRIPTION: Initialize a new namespace node and install it amongst 214 * its peers. 215 * 216 * Note: Current namespace lookup is linear search. This appears 217 * to be sufficient as namespace searches consume only a small 218 * fraction of the execution time of the ACPI subsystem. 219 * 220 ******************************************************************************/ 221 222 void acpi_ns_install_node(struct acpi_walk_state *walk_state, struct acpi_namespace_node *parent_node, /* Parent */ 223 struct acpi_namespace_node *node, /* New Child */ 224 acpi_object_type type) 225 { 226 acpi_owner_id owner_id = 0; 227 struct acpi_namespace_node *child_node; 228 229 ACPI_FUNCTION_TRACE(ns_install_node); 230 231 /* 232 * Get the owner ID from the Walk state. The owner ID is used to track 233 * table deletion and deletion of objects created by methods. 234 */ 235 if (walk_state) { 236 owner_id = walk_state->owner_id; 237 } 238 239 /* Link the new entry into the parent and existing children */ 240 241 child_node = parent_node->child; 242 if (!child_node) { 243 parent_node->child = node; 244 node->flags |= ANOBJ_END_OF_PEER_LIST; 245 node->peer = parent_node; 246 } else { 247 while (!(child_node->flags & ANOBJ_END_OF_PEER_LIST)) { 248 child_node = child_node->peer; 249 } 250 251 child_node->peer = node; 252 253 /* Clear end-of-list flag */ 254 255 child_node->flags &= ~ANOBJ_END_OF_PEER_LIST; 256 node->flags |= ANOBJ_END_OF_PEER_LIST; 257 node->peer = parent_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 *child_node; 292 struct acpi_namespace_node *next_node; 293 u8 flags; 294 295 ACPI_FUNCTION_TRACE_PTR(ns_delete_children, parent_node); 296 297 if (!parent_node) { 298 return_VOID; 299 } 300 301 /* If no children, all done! */ 302 303 child_node = parent_node->child; 304 if (!child_node) { 305 return_VOID; 306 } 307 308 /* Deallocate all children at this level */ 309 310 do { 311 312 /* Get the things we need */ 313 314 next_node = child_node->peer; 315 flags = child_node->flags; 316 317 /* Grandchildren should have all been deleted already */ 318 319 if (child_node->child) { 320 ACPI_ERROR((AE_INFO, "Found a grandchild! P=%p C=%p", 321 parent_node, child_node)); 322 } 323 324 /* 325 * Delete this child node and move on to the next child in the list. 326 * No need to unlink the node since we are deleting the entire branch. 327 */ 328 acpi_ns_delete_node(child_node); 329 child_node = next_node; 330 331 } while (!(flags & ANOBJ_END_OF_PEER_LIST)); 332 333 /* Clear the parent's child pointer */ 334 335 parent_node->child = NULL; 336 return_VOID; 337 } 338 339 /******************************************************************************* 340 * 341 * FUNCTION: acpi_ns_delete_namespace_subtree 342 * 343 * PARAMETERS: parent_node - Root of the subtree to be deleted 344 * 345 * RETURN: None. 346 * 347 * DESCRIPTION: Delete a subtree of the namespace. This includes all objects 348 * stored within the subtree. 349 * 350 ******************************************************************************/ 351 352 void acpi_ns_delete_namespace_subtree(struct acpi_namespace_node *parent_node) 353 { 354 struct acpi_namespace_node *child_node = NULL; 355 u32 level = 1; 356 357 ACPI_FUNCTION_TRACE(ns_delete_namespace_subtree); 358 359 if (!parent_node) { 360 return_VOID; 361 } 362 363 /* 364 * Traverse the tree of objects until we bubble back up 365 * to where we started. 366 */ 367 while (level > 0) { 368 369 /* Get the next node in this scope (NULL if none) */ 370 371 child_node = acpi_ns_get_next_node(parent_node, child_node); 372 if (child_node) { 373 374 /* Found a child node - detach any attached object */ 375 376 acpi_ns_detach_object(child_node); 377 378 /* Check if this node has any children */ 379 380 if (child_node->child) { 381 /* 382 * There is at least one child of this node, 383 * visit the node 384 */ 385 level++; 386 parent_node = child_node; 387 child_node = NULL; 388 } 389 } else { 390 /* 391 * No more children of this parent node. 392 * Move up to the grandparent. 393 */ 394 level--; 395 396 /* 397 * Now delete all of the children of this parent 398 * all at the same time. 399 */ 400 acpi_ns_delete_children(parent_node); 401 402 /* New "last child" is this parent node */ 403 404 child_node = parent_node; 405 406 /* Move up the tree to the grandparent */ 407 408 parent_node = acpi_ns_get_parent_node(parent_node); 409 } 410 } 411 412 return_VOID; 413 } 414 415 /******************************************************************************* 416 * 417 * FUNCTION: acpi_ns_delete_namespace_by_owner 418 * 419 * PARAMETERS: owner_id - All nodes with this owner will be deleted 420 * 421 * RETURN: Status 422 * 423 * DESCRIPTION: Delete entries within the namespace that are owned by a 424 * specific ID. Used to delete entire ACPI tables. All 425 * reference counts are updated. 426 * 427 * MUTEX: Locks namespace during deletion walk. 428 * 429 ******************************************************************************/ 430 431 void acpi_ns_delete_namespace_by_owner(acpi_owner_id owner_id) 432 { 433 struct acpi_namespace_node *child_node; 434 struct acpi_namespace_node *deletion_node; 435 struct acpi_namespace_node *parent_node; 436 u32 level; 437 acpi_status status; 438 439 ACPI_FUNCTION_TRACE_U32(ns_delete_namespace_by_owner, owner_id); 440 441 if (owner_id == 0) { 442 return_VOID; 443 } 444 445 /* Lock namespace for possible update */ 446 447 status = acpi_ut_acquire_mutex(ACPI_MTX_NAMESPACE); 448 if (ACPI_FAILURE(status)) { 449 return_VOID; 450 } 451 452 deletion_node = NULL; 453 parent_node = acpi_gbl_root_node; 454 child_node = NULL; 455 level = 1; 456 457 /* 458 * Traverse the tree of nodes until we bubble back up 459 * to where we started. 460 */ 461 while (level > 0) { 462 /* 463 * Get the next child of this parent node. When child_node is NULL, 464 * the first child of the parent is returned 465 */ 466 child_node = acpi_ns_get_next_node(parent_node, child_node); 467 468 if (deletion_node) { 469 acpi_ns_delete_children(deletion_node); 470 acpi_ns_remove_node(deletion_node); 471 deletion_node = NULL; 472 } 473 474 if (child_node) { 475 if (child_node->owner_id == owner_id) { 476 477 /* Found a matching child node - detach any attached object */ 478 479 acpi_ns_detach_object(child_node); 480 } 481 482 /* Check if this node has any children */ 483 484 if (child_node->child) { 485 /* 486 * There is at least one child of this node, 487 * visit the node 488 */ 489 level++; 490 parent_node = child_node; 491 child_node = NULL; 492 } else if (child_node->owner_id == owner_id) { 493 deletion_node = child_node; 494 } 495 } else { 496 /* 497 * No more children of this parent node. 498 * Move up to the grandparent. 499 */ 500 level--; 501 if (level != 0) { 502 if (parent_node->owner_id == owner_id) { 503 deletion_node = parent_node; 504 } 505 } 506 507 /* New "last child" is this parent node */ 508 509 child_node = parent_node; 510 511 /* Move up the tree to the grandparent */ 512 513 parent_node = acpi_ns_get_parent_node(parent_node); 514 } 515 } 516 517 (void)acpi_ut_release_mutex(ACPI_MTX_NAMESPACE); 518 return_VOID; 519 } 520