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