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