1 /*******************************************************************************
2 *
3 * Module Name: nsalloc - Namespace allocation and deletion utilities
4 *
5 ******************************************************************************/
6
7 /*
8 * Copyright (C) 2000 - 2004, R. Byron Moore
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
45 #include <acpi/acpi.h>
46 #include <acpi/acnamesp.h>
47
48
49 #define _COMPONENT ACPI_NAMESPACE
50 ACPI_MODULE_NAME ("nsalloc")
51
52
53 /*******************************************************************************
54 *
55 * FUNCTION: acpi_ns_create_node
56 *
57 * PARAMETERS: acpi_name - Name of the new node
58 *
59 * RETURN: None
60 *
61 * DESCRIPTION: Create a namespace node
62 *
63 ******************************************************************************/
64
65 struct acpi_namespace_node *
acpi_ns_create_node(u32 name)66 acpi_ns_create_node (
67 u32 name)
68 {
69 struct acpi_namespace_node *node;
70
71
72 ACPI_FUNCTION_TRACE ("ns_create_node");
73
74
75 node = ACPI_MEM_CALLOCATE (sizeof (struct acpi_namespace_node));
76 if (!node) {
77 return_PTR (NULL);
78 }
79
80 ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_allocated++);
81
82 node->name.integer = name;
83 node->reference_count = 1;
84 ACPI_SET_DESCRIPTOR_TYPE (node, ACPI_DESC_TYPE_NAMED);
85
86 return_PTR (node);
87 }
88
89
90 /*******************************************************************************
91 *
92 * FUNCTION: acpi_ns_delete_node
93 *
94 * PARAMETERS: Node - Node to be deleted
95 *
96 * RETURN: None
97 *
98 * DESCRIPTION: Delete a namespace node
99 *
100 ******************************************************************************/
101
102 void
acpi_ns_delete_node(struct acpi_namespace_node * node)103 acpi_ns_delete_node (
104 struct acpi_namespace_node *node)
105 {
106 struct acpi_namespace_node *parent_node;
107 struct acpi_namespace_node *prev_node;
108 struct acpi_namespace_node *next_node;
109
110
111 ACPI_FUNCTION_TRACE_PTR ("ns_delete_node", node);
112
113
114 parent_node = acpi_ns_get_parent_node (node);
115
116 prev_node = NULL;
117 next_node = parent_node->child;
118
119 /* Find the node that is the previous peer in the parent's child list */
120
121 while (next_node != node) {
122 prev_node = next_node;
123 next_node = prev_node->peer;
124 }
125
126 if (prev_node) {
127 /* Node is not first child, unlink it */
128
129 prev_node->peer = next_node->peer;
130 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
131 prev_node->flags |= ANOBJ_END_OF_PEER_LIST;
132 }
133 }
134 else {
135 /* Node is first child (has no previous peer) */
136
137 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
138 /* No peers at all */
139
140 parent_node->child = NULL;
141 }
142 else { /* Link peer list to parent */
143
144 parent_node->child = next_node->peer;
145 }
146 }
147
148
149 ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_freed++);
150
151 /*
152 * Detach an object if there is one then delete the node
153 */
154 acpi_ns_detach_object (node);
155 ACPI_MEM_FREE (node);
156 return_VOID;
157 }
158
159
160 #ifdef ACPI_ALPHABETIC_NAMESPACE
161 /*******************************************************************************
162 *
163 * FUNCTION: acpi_ns_compare_names
164 *
165 * PARAMETERS: Name1 - First name to compare
166 * Name2 - Second name to compare
167 *
168 * RETURN: value from strncmp
169 *
170 * DESCRIPTION: Compare two ACPI names. Names that are prefixed with an
171 * underscore are forced to be alphabetically first.
172 *
173 ******************************************************************************/
174
175 int
acpi_ns_compare_names(char * name1,char * name2)176 acpi_ns_compare_names (
177 char *name1,
178 char *name2)
179 {
180 char reversed_name1[ACPI_NAME_SIZE];
181 char reversed_name2[ACPI_NAME_SIZE];
182 u32 i;
183 u32 j;
184
185
186 /*
187 * Replace all instances of "underscore" with a value that is smaller so
188 * that all names that are prefixed with underscore(s) are alphabetically
189 * first.
190 *
191 * Reverse the name bytewise so we can just do a 32-bit compare instead
192 * of a strncmp.
193 */
194 for (i = 0, j= (ACPI_NAME_SIZE - 1); i < ACPI_NAME_SIZE; i++, j--) {
195 reversed_name1[j] = name1[i];
196 if (name1[i] == '_') {
197 reversed_name1[j] = '*';
198 }
199
200 reversed_name2[j] = name2[i];
201 if (name2[i] == '_') {
202 reversed_name2[j] = '*';
203 }
204 }
205
206 return (*(int *) reversed_name1 - *(int *) reversed_name2);
207 }
208 #endif
209
210
211 /*******************************************************************************
212 *
213 * FUNCTION: acpi_ns_install_node
214 *
215 * PARAMETERS: walk_state - Current state of the walk
216 * parent_node - The parent of the new Node
217 * Node - The new Node to install
218 * Type - ACPI object type of the new Node
219 *
220 * RETURN: None
221 *
222 * DESCRIPTION: Initialize a new namespace node and install it amongst
223 * its peers.
224 *
225 * Note: Current namespace lookup is linear search. However, the
226 * nodes are linked in alphabetical order to 1) put all reserved
227 * names (start with underscore) first, and to 2) make a readable
228 * namespace dump.
229 *
230 ******************************************************************************/
231
232 void
acpi_ns_install_node(struct acpi_walk_state * walk_state,struct acpi_namespace_node * parent_node,struct acpi_namespace_node * node,acpi_object_type type)233 acpi_ns_install_node (
234 struct acpi_walk_state *walk_state,
235 struct acpi_namespace_node *parent_node, /* Parent */
236 struct acpi_namespace_node *node, /* New Child*/
237 acpi_object_type type)
238 {
239 u16 owner_id = 0;
240 struct acpi_namespace_node *child_node;
241 #ifdef ACPI_ALPHABETIC_NAMESPACE
242
243 struct acpi_namespace_node *previous_child_node;
244 #endif
245
246
247 ACPI_FUNCTION_TRACE ("ns_install_node");
248
249
250 /*
251 * Get the owner ID from the Walk state
252 * The owner ID is used to track table deletion and
253 * deletion of objects created by methods
254 */
255 if (walk_state) {
256 owner_id = walk_state->owner_id;
257 }
258
259 /* Link the new entry into the parent and existing children */
260
261 child_node = parent_node->child;
262 if (!child_node) {
263 parent_node->child = node;
264 node->flags |= ANOBJ_END_OF_PEER_LIST;
265 node->peer = parent_node;
266 }
267 else {
268 #ifdef ACPI_ALPHABETIC_NAMESPACE
269 /*
270 * Walk the list whilst searching for the the correct
271 * alphabetic placement.
272 */
273 previous_child_node = NULL;
274 while (acpi_ns_compare_names (acpi_ut_get_node_name (child_node), acpi_ut_get_node_name (node)) < 0) {
275 if (child_node->flags & ANOBJ_END_OF_PEER_LIST) {
276 /* Last peer; Clear end-of-list flag */
277
278 child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
279
280 /* This node is the new peer to the child node */
281
282 child_node->peer = node;
283
284 /* This node is the new end-of-list */
285
286 node->flags |= ANOBJ_END_OF_PEER_LIST;
287 node->peer = parent_node;
288 break;
289 }
290
291 /* Get next peer */
292
293 previous_child_node = child_node;
294 child_node = child_node->peer;
295 }
296
297 /* Did the node get inserted at the end-of-list? */
298
299 if (!(node->flags & ANOBJ_END_OF_PEER_LIST)) {
300 /*
301 * Loop above terminated without reaching the end-of-list.
302 * Insert the new node at the current location
303 */
304 if (previous_child_node) {
305 /* Insert node alphabetically */
306
307 node->peer = child_node;
308 previous_child_node->peer = node;
309 }
310 else {
311 /* Insert node alphabetically at start of list */
312
313 node->peer = child_node;
314 parent_node->child = node;
315 }
316 }
317 #else
318 while (!(child_node->flags & ANOBJ_END_OF_PEER_LIST)) {
319 child_node = child_node->peer;
320 }
321
322 child_node->peer = node;
323
324 /* Clear end-of-list flag */
325
326 child_node->flags &= ~ANOBJ_END_OF_PEER_LIST;
327 node->flags |= ANOBJ_END_OF_PEER_LIST;
328 node->peer = parent_node;
329 #endif
330 }
331
332 /* Init the new entry */
333
334 node->owner_id = owner_id;
335 node->type = (u8) type;
336
337 ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
338 "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
339 acpi_ut_get_node_name (node), acpi_ut_get_type_name (node->type), node, owner_id,
340 acpi_ut_get_node_name (parent_node), acpi_ut_get_type_name (parent_node->type),
341 parent_node));
342
343 /*
344 * Increment the reference count(s) of all parents up to
345 * the root!
346 */
347 while ((node = acpi_ns_get_parent_node (node)) != NULL) {
348 node->reference_count++;
349 }
350
351 return_VOID;
352 }
353
354
355 /*******************************************************************************
356 *
357 * FUNCTION: acpi_ns_delete_children
358 *
359 * PARAMETERS: parent_node - Delete this objects children
360 *
361 * RETURN: None.
362 *
363 * DESCRIPTION: Delete all children of the parent object. In other words,
364 * deletes a "scope".
365 *
366 ******************************************************************************/
367
368 void
acpi_ns_delete_children(struct acpi_namespace_node * parent_node)369 acpi_ns_delete_children (
370 struct acpi_namespace_node *parent_node)
371 {
372 struct acpi_namespace_node *child_node;
373 struct acpi_namespace_node *next_node;
374 struct acpi_namespace_node *node;
375 u8 flags;
376
377
378 ACPI_FUNCTION_TRACE_PTR ("ns_delete_children", parent_node);
379
380
381 if (!parent_node) {
382 return_VOID;
383 }
384
385 /* If no children, all done! */
386
387 child_node = parent_node->child;
388 if (!child_node) {
389 return_VOID;
390 }
391
392 /*
393 * Deallocate all children at this level
394 */
395 do {
396 /* Get the things we need */
397
398 next_node = child_node->peer;
399 flags = child_node->flags;
400
401 /* Grandchildren should have all been deleted already */
402
403 if (child_node->child) {
404 ACPI_DEBUG_PRINT ((ACPI_DB_ERROR, "Found a grandchild! P=%p C=%p\n",
405 parent_node, child_node));
406 }
407
408 /* Now we can free this child object */
409
410 ACPI_MEM_TRACKING (acpi_gbl_memory_lists[ACPI_MEM_LIST_NSNODE].total_freed++);
411
412 ACPI_DEBUG_PRINT ((ACPI_DB_ALLOCATIONS, "Object %p, Remaining %X\n",
413 child_node, acpi_gbl_current_node_count));
414
415 /*
416 * Detach an object if there is one, then free the child node
417 */
418 acpi_ns_detach_object (child_node);
419
420 /*
421 * Decrement the reference count(s) of all parents up to
422 * the root! (counts were incremented when the node was created)
423 */
424 node = child_node;
425 while ((node = acpi_ns_get_parent_node (node)) != NULL) {
426 node->reference_count--;
427 }
428
429 /* There should be only one reference remaining on this node */
430
431 if (child_node->reference_count != 1) {
432 ACPI_REPORT_WARNING (("Existing references (%d) on node being deleted (%p)\n",
433 child_node->reference_count, child_node));
434 }
435
436 /* Now we can delete the node */
437
438 ACPI_MEM_FREE (child_node);
439
440 /* And move on to the next child in the list */
441
442 child_node = next_node;
443
444 } while (!(flags & ANOBJ_END_OF_PEER_LIST));
445
446
447 /* Clear the parent's child pointer */
448
449 parent_node->child = NULL;
450
451 return_VOID;
452 }
453
454
455 /*******************************************************************************
456 *
457 * FUNCTION: acpi_ns_delete_namespace_subtree
458 *
459 * PARAMETERS: parent_node - Root of the subtree to be deleted
460 *
461 * RETURN: None.
462 *
463 * DESCRIPTION: Delete a subtree of the namespace. This includes all objects
464 * stored within the subtree.
465 *
466 ******************************************************************************/
467
468 void
acpi_ns_delete_namespace_subtree(struct acpi_namespace_node * parent_node)469 acpi_ns_delete_namespace_subtree (
470 struct acpi_namespace_node *parent_node)
471 {
472 struct acpi_namespace_node *child_node = NULL;
473 u32 level = 1;
474
475
476 ACPI_FUNCTION_TRACE ("ns_delete_namespace_subtree");
477
478
479 if (!parent_node) {
480 return_VOID;
481 }
482
483 /*
484 * Traverse the tree of objects until we bubble back up
485 * to where we started.
486 */
487 while (level > 0) {
488 /* Get the next node in this scope (NULL if none) */
489
490 child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node,
491 child_node);
492 if (child_node) {
493 /* Found a child node - detach any attached object */
494
495 acpi_ns_detach_object (child_node);
496
497 /* Check if this node has any children */
498
499 if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, 0)) {
500 /*
501 * There is at least one child of this node,
502 * visit the node
503 */
504 level++;
505 parent_node = child_node;
506 child_node = 0;
507 }
508 }
509 else {
510 /*
511 * No more children of this parent node.
512 * Move up to the grandparent.
513 */
514 level--;
515
516 /*
517 * Now delete all of the children of this parent
518 * all at the same time.
519 */
520 acpi_ns_delete_children (parent_node);
521
522 /* New "last child" is this parent node */
523
524 child_node = parent_node;
525
526 /* Move up the tree to the grandparent */
527
528 parent_node = acpi_ns_get_parent_node (parent_node);
529 }
530 }
531
532 return_VOID;
533 }
534
535
536 /*******************************************************************************
537 *
538 * FUNCTION: acpi_ns_remove_reference
539 *
540 * PARAMETERS: Node - Named node whose reference count is to be
541 * decremented
542 *
543 * RETURN: None.
544 *
545 * DESCRIPTION: Remove a Node reference. Decrements the reference count
546 * of all parent Nodes up to the root. Any node along
547 * the way that reaches zero references is freed.
548 *
549 ******************************************************************************/
550
551 void
acpi_ns_remove_reference(struct acpi_namespace_node * node)552 acpi_ns_remove_reference (
553 struct acpi_namespace_node *node)
554 {
555 struct acpi_namespace_node *parent_node;
556 struct acpi_namespace_node *this_node;
557
558
559 ACPI_FUNCTION_ENTRY ();
560
561
562 /*
563 * Decrement the reference count(s) of this node and all
564 * nodes up to the root, Delete anything with zero remaining references.
565 */
566 this_node = node;
567 while (this_node) {
568 /* Prepare to move up to parent */
569
570 parent_node = acpi_ns_get_parent_node (this_node);
571
572 /* Decrement the reference count on this node */
573
574 this_node->reference_count--;
575
576 /* Delete the node if no more references */
577
578 if (!this_node->reference_count) {
579 /* Delete all children and delete the node */
580
581 acpi_ns_delete_children (this_node);
582 acpi_ns_delete_node (this_node);
583 }
584
585 this_node = parent_node;
586 }
587 }
588
589
590 /*******************************************************************************
591 *
592 * FUNCTION: acpi_ns_delete_namespace_by_owner
593 *
594 * PARAMETERS: owner_id - All nodes with this owner will be deleted
595 *
596 * RETURN: Status
597 *
598 * DESCRIPTION: Delete entries within the namespace that are owned by a
599 * specific ID. Used to delete entire ACPI tables. All
600 * reference counts are updated.
601 *
602 ******************************************************************************/
603
604 void
acpi_ns_delete_namespace_by_owner(u16 owner_id)605 acpi_ns_delete_namespace_by_owner (
606 u16 owner_id)
607 {
608 struct acpi_namespace_node *child_node;
609 struct acpi_namespace_node *deletion_node;
610 u32 level;
611 struct acpi_namespace_node *parent_node;
612
613
614 ACPI_FUNCTION_TRACE_U32 ("ns_delete_namespace_by_owner", owner_id);
615
616
617 parent_node = acpi_gbl_root_node;
618 child_node = NULL;
619 deletion_node = NULL;
620 level = 1;
621
622 /*
623 * Traverse the tree of nodes until we bubble back up
624 * to where we started.
625 */
626 while (level > 0) {
627 /*
628 * Get the next child of this parent node. When child_node is NULL,
629 * the first child of the parent is returned
630 */
631 child_node = acpi_ns_get_next_node (ACPI_TYPE_ANY, parent_node, child_node);
632
633 if (deletion_node) {
634 acpi_ns_remove_reference (deletion_node);
635 deletion_node = NULL;
636 }
637
638 if (child_node) {
639 if (child_node->owner_id == owner_id) {
640 /* Found a matching child node - detach any attached object */
641
642 acpi_ns_detach_object (child_node);
643 }
644
645 /* Check if this node has any children */
646
647 if (acpi_ns_get_next_node (ACPI_TYPE_ANY, child_node, NULL)) {
648 /*
649 * There is at least one child of this node,
650 * visit the node
651 */
652 level++;
653 parent_node = child_node;
654 child_node = NULL;
655 }
656 else if (child_node->owner_id == owner_id) {
657 deletion_node = child_node;
658 }
659 }
660 else {
661 /*
662 * No more children of this parent node.
663 * Move up to the grandparent.
664 */
665 level--;
666 if (level != 0) {
667 if (parent_node->owner_id == owner_id) {
668 deletion_node = parent_node;
669 }
670 }
671
672 /* New "last child" is this parent node */
673
674 child_node = parent_node;
675
676 /* Move up the tree to the grandparent */
677
678 parent_node = acpi_ns_get_parent_node (parent_node);
679 }
680 }
681
682 return_VOID;
683 }
684
685
686