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