sys/contrib/dev/acpica/source/components/namespace/nswalk.c

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