1/*******************************************************************************
2 *
3 * Module Name: nsalloc - Namespace allocation and deletion utilities
4 *
5 ******************************************************************************/
6
7/*
8 * Copyright (C) 2000 - 2011, 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
45#define __NSALLOC_C__
46
47#include "acpi.h"
48#include "accommon.h"
49#include "acnamesp.h"
50
51
52#define _COMPONENT          ACPI_NAMESPACE
53        ACPI_MODULE_NAME    ("nsalloc")
54
55
56/*******************************************************************************
57 *
58 * FUNCTION:    AcpiNsCreateNode
59 *
60 * PARAMETERS:  Name            - Name of the new node (4 char ACPI name)
61 *
62 * RETURN:      New namespace node (Null on failure)
63 *
64 * DESCRIPTION: Create a namespace node
65 *
66 ******************************************************************************/
67
68ACPI_NAMESPACE_NODE *
69AcpiNsCreateNode (
70    UINT32                  Name)
71{
72    ACPI_NAMESPACE_NODE     *Node;
73#ifdef ACPI_DBG_TRACK_ALLOCATIONS
74    UINT32                  Temp;
75#endif
76
77
78    ACPI_FUNCTION_TRACE (NsCreateNode);
79
80
81    Node = AcpiOsAcquireObject (AcpiGbl_NamespaceCache);
82    if (!Node)
83    {
84        return_PTR (NULL);
85    }
86
87    ACPI_MEM_TRACKING (AcpiGbl_NsNodeList->TotalAllocated++);
88
89#ifdef ACPI_DBG_TRACK_ALLOCATIONS
90        Temp = AcpiGbl_NsNodeList->TotalAllocated -
91                AcpiGbl_NsNodeList->TotalFreed;
92        if (Temp > AcpiGbl_NsNodeList->MaxOccupied)
93        {
94            AcpiGbl_NsNodeList->MaxOccupied = Temp;
95        }
96#endif
97
98    Node->Name.Integer = Name;
99    ACPI_SET_DESCRIPTOR_TYPE (Node, ACPI_DESC_TYPE_NAMED);
100    return_PTR (Node);
101}
102
103
104/*******************************************************************************
105 *
106 * FUNCTION:    AcpiNsDeleteNode
107 *
108 * PARAMETERS:  Node            - Node to be deleted
109 *
110 * RETURN:      None
111 *
112 * DESCRIPTION: Delete a namespace node. All node deletions must come through
113 *              here. Detaches any attached objects, including any attached
114 *              data. If a handler is associated with attached data, it is
115 *              invoked before the node is deleted.
116 *
117 ******************************************************************************/
118
119void
120AcpiNsDeleteNode (
121    ACPI_NAMESPACE_NODE     *Node)
122{
123    ACPI_OPERAND_OBJECT     *ObjDesc;
124
125
126    ACPI_FUNCTION_NAME (NsDeleteNode);
127
128
129    /* Detach an object if there is one */
130
131    AcpiNsDetachObject (Node);
132
133    /*
134     * Delete an attached data object if present (an object that was created
135     * and attached via AcpiAttachData). Note: After any normal object is
136     * detached above, the only possible remaining object is a data object.
137     */
138    ObjDesc = Node->Object;
139    if (ObjDesc &&
140        (ObjDesc->Common.Type == ACPI_TYPE_LOCAL_DATA))
141    {
142        /* Invoke the attached data deletion handler if present */
143
144        if (ObjDesc->Data.Handler)
145        {
146            ObjDesc->Data.Handler (Node, ObjDesc->Data.Pointer);
147        }
148
149        AcpiUtRemoveReference (ObjDesc);
150    }
151
152    /* Now we can delete the node */
153
154    (void) AcpiOsReleaseObject (AcpiGbl_NamespaceCache, Node);
155
156    ACPI_MEM_TRACKING (AcpiGbl_NsNodeList->TotalFreed++);
157    ACPI_DEBUG_PRINT ((ACPI_DB_ALLOCATIONS, "Node %p, Remaining %X\n",
158        Node, AcpiGbl_CurrentNodeCount));
159}
160
161
162/*******************************************************************************
163 *
164 * FUNCTION:    AcpiNsRemoveNode
165 *
166 * PARAMETERS:  Node            - Node to be removed/deleted
167 *
168 * RETURN:      None
169 *
170 * DESCRIPTION: Remove (unlink) and delete a namespace node
171 *
172 ******************************************************************************/
173
174void
175AcpiNsRemoveNode (
176    ACPI_NAMESPACE_NODE     *Node)
177{
178    ACPI_NAMESPACE_NODE     *ParentNode;
179    ACPI_NAMESPACE_NODE     *PrevNode;
180    ACPI_NAMESPACE_NODE     *NextNode;
181
182
183    ACPI_FUNCTION_TRACE_PTR (NsRemoveNode, Node);
184
185
186    ParentNode = Node->Parent;
187
188    PrevNode = NULL;
189    NextNode = ParentNode->Child;
190
191    /* Find the node that is the previous peer in the parent's child list */
192
193    while (NextNode != Node)
194    {
195        PrevNode = NextNode;
196        NextNode = NextNode->Peer;
197    }
198
199    if (PrevNode)
200    {
201        /* Node is not first child, unlink it */
202
203        PrevNode->Peer = Node->Peer;
204    }
205    else
206    {
207        /*
208         * Node is first child (has no previous peer).
209         * Link peer list to parent
210         */
211        ParentNode->Child = Node->Peer;
212    }
213
214    /* Delete the node and any attached objects */
215
216    AcpiNsDeleteNode (Node);
217    return_VOID;
218}
219
220
221/*******************************************************************************
222 *
223 * FUNCTION:    AcpiNsInstallNode
224 *
225 * PARAMETERS:  WalkState       - Current state of the walk
226 *              ParentNode      - The parent of the new Node
227 *              Node            - The new Node to install
228 *              Type            - ACPI object type of the new Node
229 *
230 * RETURN:      None
231 *
232 * DESCRIPTION: Initialize a new namespace node and install it amongst
233 *              its peers.
234 *
235 *              Note: Current namespace lookup is linear search. This appears
236 *              to be sufficient as namespace searches consume only a small
237 *              fraction of the execution time of the ACPI subsystem.
238 *
239 ******************************************************************************/
240
241void
242AcpiNsInstallNode (
243    ACPI_WALK_STATE         *WalkState,
244    ACPI_NAMESPACE_NODE     *ParentNode,    /* Parent */
245    ACPI_NAMESPACE_NODE     *Node,          /* New Child*/
246    ACPI_OBJECT_TYPE        Type)
247{
248    ACPI_OWNER_ID           OwnerId = 0;
249    ACPI_NAMESPACE_NODE     *ChildNode;
250
251
252    ACPI_FUNCTION_TRACE (NsInstallNode);
253
254
255    if (WalkState)
256    {
257        /*
258         * Get the owner ID from the Walk state. The owner ID is used to
259         * track table deletion and deletion of objects created by methods.
260         */
261        OwnerId = WalkState->OwnerId;
262
263        if ((WalkState->MethodDesc) &&
264            (ParentNode != WalkState->MethodNode))
265        {
266            /*
267             * A method is creating a new node that is not a child of the
268             * method (it is non-local). Mark the executing method as having
269             * modified the namespace. This is used for cleanup when the
270             * method exits.
271             */
272            WalkState->MethodDesc->Method.InfoFlags |= ACPI_METHOD_MODIFIED_NAMESPACE;
273        }
274    }
275
276    /* Link the new entry into the parent and existing children */
277
278    Node->Peer = NULL;
279    Node->Parent = ParentNode;
280    ChildNode = ParentNode->Child;
281
282    if (!ChildNode)
283    {
284        ParentNode->Child = Node;
285    }
286    else
287    {
288        /* Add node to the end of the peer list */
289
290        while (ChildNode->Peer)
291        {
292            ChildNode = ChildNode->Peer;
293        }
294
295        ChildNode->Peer = Node;
296    }
297
298    /* Init the new entry */
299
300    Node->OwnerId = OwnerId;
301    Node->Type = (UINT8) Type;
302
303    ACPI_DEBUG_PRINT ((ACPI_DB_NAMES,
304        "%4.4s (%s) [Node %p Owner %X] added to %4.4s (%s) [Node %p]\n",
305        AcpiUtGetNodeName (Node), AcpiUtGetTypeName (Node->Type), Node, OwnerId,
306        AcpiUtGetNodeName (ParentNode), AcpiUtGetTypeName (ParentNode->Type),
307        ParentNode));
308
309    return_VOID;
310}
311
312
313/*******************************************************************************
314 *
315 * FUNCTION:    AcpiNsDeleteChildren
316 *
317 * PARAMETERS:  ParentNode      - Delete this objects children
318 *
319 * RETURN:      None.
320 *
321 * DESCRIPTION: Delete all children of the parent object. In other words,
322 *              deletes a "scope".
323 *
324 ******************************************************************************/
325
326void
327AcpiNsDeleteChildren (
328    ACPI_NAMESPACE_NODE     *ParentNode)
329{
330    ACPI_NAMESPACE_NODE     *NextNode;
331    ACPI_NAMESPACE_NODE     *NodeToDelete;
332
333
334    ACPI_FUNCTION_TRACE_PTR (NsDeleteChildren, ParentNode);
335
336
337    if (!ParentNode)
338    {
339        return_VOID;
340    }
341
342    /* Deallocate all children at this level */
343
344    NextNode = ParentNode->Child;
345    while (NextNode)
346    {
347        /* Grandchildren should have all been deleted already */
348
349        if (NextNode->Child)
350        {
351            ACPI_ERROR ((AE_INFO, "Found a grandchild! P=%p C=%p",
352                ParentNode, NextNode));
353        }
354
355        /*
356         * Delete this child node and move on to the next child in the list.
357         * No need to unlink the node since we are deleting the entire branch.
358         */
359        NodeToDelete = NextNode;
360        NextNode = NextNode->Peer;
361        AcpiNsDeleteNode (NodeToDelete);
362    };
363
364    /* Clear the parent's child pointer */
365
366    ParentNode->Child = NULL;
367    return_VOID;
368}
369
370
371/*******************************************************************************
372 *
373 * FUNCTION:    AcpiNsDeleteNamespaceSubtree
374 *
375 * PARAMETERS:  ParentNode      - Root of the subtree to be deleted
376 *
377 * RETURN:      None.
378 *
379 * DESCRIPTION: Delete a subtree of the namespace.  This includes all objects
380 *              stored within the subtree.
381 *
382 ******************************************************************************/
383
384void
385AcpiNsDeleteNamespaceSubtree (
386    ACPI_NAMESPACE_NODE     *ParentNode)
387{
388    ACPI_NAMESPACE_NODE     *ChildNode = NULL;
389    UINT32                  Level = 1;
390    ACPI_STATUS             Status;
391
392
393    ACPI_FUNCTION_TRACE (NsDeleteNamespaceSubtree);
394
395
396    if (!ParentNode)
397    {
398        return_VOID;
399    }
400
401    /* Lock namespace for possible update */
402
403    Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
404    if (ACPI_FAILURE (Status))
405    {
406        return_VOID;
407    }
408
409    /*
410     * Traverse the tree of objects until we bubble back up
411     * to where we started.
412     */
413    while (Level > 0)
414    {
415        /* Get the next node in this scope (NULL if none) */
416
417        ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
418        if (ChildNode)
419        {
420            /* Found a child node - detach any attached object */
421
422            AcpiNsDetachObject (ChildNode);
423
424            /* Check if this node has any children */
425
426            if (ChildNode->Child)
427            {
428                /*
429                 * There is at least one child of this node,
430                 * visit the node
431                 */
432                Level++;
433                ParentNode = ChildNode;
434                ChildNode  = NULL;
435            }
436        }
437        else
438        {
439            /*
440             * No more children of this parent node.
441             * Move up to the grandparent.
442             */
443            Level--;
444
445            /*
446             * Now delete all of the children of this parent
447             * all at the same time.
448             */
449            AcpiNsDeleteChildren (ParentNode);
450
451            /* New "last child" is this parent node */
452
453            ChildNode = ParentNode;
454
455            /* Move up the tree to the grandparent */
456
457            ParentNode = ParentNode->Parent;
458        }
459    }
460
461    (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
462    return_VOID;
463}
464
465
466/*******************************************************************************
467 *
468 * FUNCTION:    AcpiNsDeleteNamespaceByOwner
469 *
470 * PARAMETERS:  OwnerId     - All nodes with this owner will be deleted
471 *
472 * RETURN:      Status
473 *
474 * DESCRIPTION: Delete entries within the namespace that are owned by a
475 *              specific ID.  Used to delete entire ACPI tables.  All
476 *              reference counts are updated.
477 *
478 * MUTEX:       Locks namespace during deletion walk.
479 *
480 ******************************************************************************/
481
482void
483AcpiNsDeleteNamespaceByOwner (
484    ACPI_OWNER_ID            OwnerId)
485{
486    ACPI_NAMESPACE_NODE     *ChildNode;
487    ACPI_NAMESPACE_NODE     *DeletionNode;
488    ACPI_NAMESPACE_NODE     *ParentNode;
489    UINT32                  Level;
490    ACPI_STATUS             Status;
491
492
493    ACPI_FUNCTION_TRACE_U32 (NsDeleteNamespaceByOwner, OwnerId);
494
495
496    if (OwnerId == 0)
497    {
498        return_VOID;
499    }
500
501    /* Lock namespace for possible update */
502
503    Status = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
504    if (ACPI_FAILURE (Status))
505    {
506        return_VOID;
507    }
508
509    DeletionNode = NULL;
510    ParentNode = AcpiGbl_RootNode;
511    ChildNode = NULL;
512    Level = 1;
513
514    /*
515     * Traverse the tree of nodes until we bubble back up
516     * to where we started.
517     */
518    while (Level > 0)
519    {
520        /*
521         * Get the next child of this parent node. When ChildNode is NULL,
522         * the first child of the parent is returned
523         */
524        ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
525
526        if (DeletionNode)
527        {
528            AcpiNsDeleteChildren (DeletionNode);
529            AcpiNsRemoveNode (DeletionNode);
530            DeletionNode = NULL;
531        }
532
533        if (ChildNode)
534        {
535            if (ChildNode->OwnerId == OwnerId)
536            {
537                /* Found a matching child node - detach any attached object */
538
539                AcpiNsDetachObject (ChildNode);
540            }
541
542            /* Check if this node has any children */
543
544            if (ChildNode->Child)
545            {
546                /*
547                 * There is at least one child of this node,
548                 * visit the node
549                 */
550                Level++;
551                ParentNode = ChildNode;
552                ChildNode  = NULL;
553            }
554            else if (ChildNode->OwnerId == OwnerId)
555            {
556                DeletionNode = ChildNode;
557            }
558        }
559        else
560        {
561            /*
562             * No more children of this parent node.
563             * Move up to the grandparent.
564             */
565            Level--;
566            if (Level != 0)
567            {
568                if (ParentNode->OwnerId == OwnerId)
569                {
570                    DeletionNode = ParentNode;
571                }
572            }
573
574            /* New "last child" is this parent node */
575
576            ChildNode = ParentNode;
577
578            /* Move up the tree to the grandparent */
579
580            ParentNode = ParentNode->Parent;
581        }
582    }
583
584    (void) AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
585    return_VOID;
586}
587
588
589