1 /******************************************************************************
   2  *
   3  * Module Name: nswalk - Functions for walking the ACPI namespace
   4  *
   5  *****************************************************************************/
   6 
   7 /*
   8  * Copyright (C) 2000 - 2013, 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 __NSWALK_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    ("nswalk")
  54 
  55 
  56 /*******************************************************************************
  57  *
  58  * FUNCTION:    AcpiNsGetNextNode
  59  *
  60  * PARAMETERS:  ParentNode          - Parent node whose children we are
  61  *                                    getting
  62  *              ChildNode           - Previous child that was found.
  63  *                                    The NEXT child will be returned
  64  *
  65  * RETURN:      ACPI_NAMESPACE_NODE - Pointer to the NEXT child or NULL if
  66  *                                    none is found.
  67  *
  68  * DESCRIPTION: Return the next peer node within the namespace. If Handle
  69  *              is valid, Scope is ignored. Otherwise, the first node
  70  *              within Scope is returned.
  71  *
  72  ******************************************************************************/
  73 
  74 ACPI_NAMESPACE_NODE *
  75 AcpiNsGetNextNode (
  76     ACPI_NAMESPACE_NODE     *ParentNode,
  77     ACPI_NAMESPACE_NODE     *ChildNode)
  78 {
  79     ACPI_FUNCTION_ENTRY ();
  80 
  81 
  82     if (!ChildNode)
  83     {
  84         /* It's really the parent's _scope_ that we want */
  85 
  86         return (ParentNode->Child);
  87     }
  88 
  89     /* Otherwise just return the next peer */
  90 
  91     return (ChildNode->Peer);
  92 }
  93 
  94 
  95 /*******************************************************************************
  96  *
  97  * FUNCTION:    AcpiNsGetNextNodeTyped
  98  *
  99  * PARAMETERS:  Type                - Type of node to be searched for
 100  *              ParentNode          - Parent node whose children we are
 101  *                                    getting
 102  *              ChildNode           - Previous child that was found.
 103  *                                    The NEXT child will be returned
 104  *
 105  * RETURN:      ACPI_NAMESPACE_NODE - Pointer to the NEXT child or NULL if
 106  *                                    none is found.
 107  *
 108  * DESCRIPTION: Return the next peer node within the namespace. If Handle
 109  *              is valid, Scope is ignored. Otherwise, the first node
 110  *              within Scope is returned.
 111  *
 112  ******************************************************************************/
 113 
 114 ACPI_NAMESPACE_NODE *
 115 AcpiNsGetNextNodeTyped (
 116     ACPI_OBJECT_TYPE        Type,
 117     ACPI_NAMESPACE_NODE     *ParentNode,
 118     ACPI_NAMESPACE_NODE     *ChildNode)
 119 {
 120     ACPI_NAMESPACE_NODE     *NextNode = NULL;
 121 
 122 
 123     ACPI_FUNCTION_ENTRY ();
 124 
 125 
 126     NextNode = AcpiNsGetNextNode (ParentNode, ChildNode);
 127 
 128     /* If any type is OK, we are done */
 129 
 130     if (Type == ACPI_TYPE_ANY)
 131     {
 132         /* NextNode is NULL if we are at the end-of-list */
 133 
 134         return (NextNode);
 135     }
 136 
 137     /* Must search for the node -- but within this scope only */
 138 
 139     while (NextNode)
 140     {
 141         /* If type matches, we are done */
 142 
 143         if (NextNode->Type == Type)
 144         {
 145             return (NextNode);
 146         }
 147 
 148         /* Otherwise, move on to the next peer node */
 149 
 150         NextNode = NextNode->Peer;
 151     }
 152 
 153     /* Not found */
 154 
 155     return (NULL);
 156 }
 157 
 158 
 159 /*******************************************************************************
 160  *
 161  * FUNCTION:    AcpiNsWalkNamespace
 162  *
 163  * PARAMETERS:  Type                - ACPI_OBJECT_TYPE to search for
 164  *              StartNode           - Handle in namespace where search begins
 165  *              MaxDepth            - Depth to which search is to reach
 166  *              Flags               - Whether to unlock the NS before invoking
 167  *                                    the callback routine
 168  *              DescendingCallback  - Called during tree descent
 169  *                                    when an object of "Type" is found
 170  *              AscendingCallback   - Called during tree ascent
 171  *                                    when an object of "Type" is found
 172  *              Context             - Passed to user function(s) above
 173  *              ReturnValue         - from the UserFunction if terminated
 174  *                                    early. Otherwise, returns NULL.
 175  * RETURNS:     Status
 176  *
 177  * DESCRIPTION: Performs a modified depth-first walk of the namespace tree,
 178  *              starting (and ending) at the node specified by StartHandle.
 179  *              The callback function is called whenever a node that matches
 180  *              the type parameter is found. If the callback function returns
 181  *              a non-zero value, the search is terminated immediately and
 182  *              this value is returned to the caller.
 183  *
 184  *              The point of this procedure is to provide a generic namespace
 185  *              walk routine that can be called from multiple places to
 186  *              provide multiple services; the callback function(s) can be
 187  *              tailored to each task, whether it is a print function,
 188  *              a compare function, etc.
 189  *
 190  ******************************************************************************/
 191 
 192 ACPI_STATUS
 193 AcpiNsWalkNamespace (
 194     ACPI_OBJECT_TYPE        Type,
 195     ACPI_HANDLE             StartNode,
 196     UINT32                  MaxDepth,
 197     UINT32                  Flags,
 198     ACPI_WALK_CALLBACK      DescendingCallback,
 199     ACPI_WALK_CALLBACK      AscendingCallback,
 200     void                    *Context,
 201     void                    **ReturnValue)
 202 {
 203     ACPI_STATUS             Status;
 204     ACPI_STATUS             MutexStatus;
 205     ACPI_NAMESPACE_NODE     *ChildNode;
 206     ACPI_NAMESPACE_NODE     *ParentNode;
 207     ACPI_OBJECT_TYPE        ChildType;
 208     UINT32                  Level;
 209     BOOLEAN                 NodePreviouslyVisited = FALSE;
 210 
 211 
 212     ACPI_FUNCTION_TRACE (NsWalkNamespace);
 213 
 214 
 215     /* Special case for the namespace Root Node */
 216 
 217     if (StartNode == ACPI_ROOT_OBJECT)
 218     {
 219         StartNode = AcpiGbl_RootNode;
 220     }
 221 
 222     /* Null child means "get first node" */
 223 
 224     ParentNode  = StartNode;
 225     ChildNode   = AcpiNsGetNextNode (ParentNode, NULL);
 226     ChildType   = ACPI_TYPE_ANY;
 227     Level       = 1;
 228 
 229     /*
 230      * Traverse the tree of nodes until we bubble back up to where we
 231      * started. When Level is zero, the loop is done because we have
 232      * bubbled up to (and passed) the original parent handle (StartEntry)
 233      */
 234     while (Level > 0 && ChildNode)
 235     {
 236         Status = AE_OK;
 237 
 238         /* Found next child, get the type if we are not searching for ANY */
 239 
 240         if (Type != ACPI_TYPE_ANY)
 241         {
 242             ChildType = ChildNode->Type;
 243         }
 244 
 245         /*
 246          * Ignore all temporary namespace nodes (created during control
 247          * method execution) unless told otherwise. These temporary nodes
 248          * can cause a race condition because they can be deleted during
 249          * the execution of the user function (if the namespace is
 250          * unlocked before invocation of the user function.) Only the
 251          * debugger namespace dump will examine the temporary nodes.
 252          */
 253         if ((ChildNode->Flags & ANOBJ_TEMPORARY) &&
 254             !(Flags & ACPI_NS_WALK_TEMP_NODES))
 255         {
 256             Status = AE_CTRL_DEPTH;
 257         }
 258 
 259         /* Type must match requested type */
 260 
 261         else if (ChildType == Type)
 262         {
 263             /*
 264              * Found a matching node, invoke the user callback function.
 265              * Unlock the namespace if flag is set.
 266              */
 267             if (Flags & ACPI_NS_WALK_UNLOCK)
 268             {
 269                 MutexStatus = AcpiUtReleaseMutex (ACPI_MTX_NAMESPACE);
 270                 if (ACPI_FAILURE (MutexStatus))
 271                 {
 272                     return_ACPI_STATUS (MutexStatus);
 273                 }
 274             }
 275 
 276             /*
 277              * Invoke the user function, either descending, ascending,
 278              * or both.
 279              */
 280             if (!NodePreviouslyVisited)
 281             {
 282                 if (DescendingCallback)
 283                 {
 284                     Status = DescendingCallback (ChildNode, Level,
 285                                 Context, ReturnValue);
 286                 }
 287             }
 288             else
 289             {
 290                 if (AscendingCallback)
 291                 {
 292                     Status = AscendingCallback (ChildNode, Level,
 293                                 Context, ReturnValue);
 294                 }
 295             }
 296 
 297             if (Flags & ACPI_NS_WALK_UNLOCK)
 298             {
 299                 MutexStatus = AcpiUtAcquireMutex (ACPI_MTX_NAMESPACE);
 300                 if (ACPI_FAILURE (MutexStatus))
 301                 {
 302                     return_ACPI_STATUS (MutexStatus);
 303                 }
 304             }
 305 
 306             switch (Status)
 307             {
 308             case AE_OK:
 309             case AE_CTRL_DEPTH:
 310 
 311                 /* Just keep going */
 312                 break;
 313 
 314             case AE_CTRL_TERMINATE:
 315 
 316                 /* Exit now, with OK status */
 317 
 318                 return_ACPI_STATUS (AE_OK);
 319 
 320             default:
 321 
 322                 /* All others are valid exceptions */
 323 
 324                 return_ACPI_STATUS (Status);
 325             }
 326         }
 327 
 328         /*
 329          * Depth first search: Attempt to go down another level in the
 330          * namespace if we are allowed to. Don't go any further if we have
 331          * reached the caller specified maximum depth or if the user
 332          * function has specified that the maximum depth has been reached.
 333          */
 334         if (!NodePreviouslyVisited &&
 335             (Level < MaxDepth) &&
 336             (Status != AE_CTRL_DEPTH))
 337         {
 338             if (ChildNode->Child)
 339             {
 340                 /* There is at least one child of this node, visit it */
 341 
 342                 Level++;
 343                 ParentNode = ChildNode;
 344                 ChildNode = AcpiNsGetNextNode (ParentNode, NULL);
 345                 continue;
 346             }
 347         }
 348 
 349         /* No more children, re-visit this node */
 350 
 351         if (!NodePreviouslyVisited)
 352         {
 353             NodePreviouslyVisited = TRUE;
 354             continue;
 355         }
 356 
 357         /* No more children, visit peers */
 358 
 359         ChildNode = AcpiNsGetNextNode (ParentNode, ChildNode);
 360         if (ChildNode)
 361         {
 362             NodePreviouslyVisited = FALSE;
 363         }
 364 
 365         /* No peers, re-visit parent */
 366 
 367         else
 368         {
 369             /*
 370              * No more children of this node (AcpiNsGetNextNode failed), go
 371              * back upwards in the namespace tree to the node's parent.
 372              */
 373             Level--;
 374             ChildNode = ParentNode;
 375             ParentNode = ParentNode->Parent;
 376 
 377             NodePreviouslyVisited = TRUE;
 378         }
 379     }
 380 
 381     /* Complete walk, not terminated by user function */
 382 
 383     return_ACPI_STATUS (AE_OK);
 384 }