drivers/bus/acpi/namespace/nssearch.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nssearch - Namespace search
   4  *              $Revision$
   5  *
   6  ******************************************************************************/
   7
   8 /*
   9  *  Copyright (C) 2000, 2001 R. Byron Moore
  10  *
  11  *  This program is free software; you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License as published by
  13  *  the Free Software Foundation; either version 2 of the License, or
  14  *  (at your option) any later version.
  15  *
  16  *  This program is distributed in the hope that it will be useful,
  17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  *  GNU General Public License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License
  22  *  along with this program; if not, write to the Free Software
  23  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  24  */
  25
  26
  27 #include "acpi.h"
  28 #include "amlcode.h"
  29 #include "acinterp.h"
  30 #include "acnamesp.h"
  31
  32
  33 #define _COMPONENT          ACPI_NAMESPACE
  34          MODULE_NAME         ("nssearch")
  35
  36
  37 /*******************************************************************************
  38  *
  39  * FUNCTION:    Acpi_ns_search_node
  40  *
  41  * PARAMETERS:  *Target_name        - Ascii ACPI name to search for
  42  *              *Node               - Starting table where search will begin
  43  *              Type                - Object type to match
  44  *              **Return_node       - Where the matched Named obj is returned
  45  *
  46  * RETURN:      Status
  47  *
  48  * DESCRIPTION: Search a single namespace table.  Performs a simple search,
  49  *              does not add entries or search parents.
  50  *
  51  *
  52  *      Named object lists are built (and subsequently dumped) in the
  53  *      order in which the names are encountered during the namespace load;
  54  *
  55  *      All namespace searching is linear in this implementation, but
  56  *      could be easily modified to support any improved search
  57  *      algorithm.  However, the linear search was chosen for simplicity
  58  *      and because the trees are small and the other interpreter
  59  *      execution overhead is relatively high.
  60  *
  61  ******************************************************************************/
  62
  63 ACPI_STATUS
  64 acpi_ns_search_node (
  65         u32                     target_name,
  66         ACPI_NAMESPACE_NODE     *node,
  67         OBJECT_TYPE_INTERNAL    type,
  68         ACPI_NAMESPACE_NODE     **return_node)
  69 {
  70         ACPI_NAMESPACE_NODE     *next_node;
  71
  72
  73         /*
  74          * Search for name in this table, which is to say that we must search
  75          * for the name among the children of this object
  76          */
  77
  78         next_node = node->child;
  79         while (next_node) {
  80                 /* Check for match against the name */
  81
  82                 if (next_node->name == target_name) {
  83                         /*
  84                          * Found matching entry.  Capture the type if appropriate, before
  85                          * returning the entry.
  86                          *
  87                          * The Def_field_defn and Bank_field_defn cases are actually looking up
  88                          * the Region in which the field will be defined
  89                          */
  90
  91                         if ((INTERNAL_TYPE_DEF_FIELD_DEFN == type) ||
  92                                 (INTERNAL_TYPE_BANK_FIELD_DEFN == type)) {
  93                                 type = ACPI_TYPE_REGION;
  94                         }
  95
  96                         /*
  97                          * Scope, Def_any, and Index_field_defn are bogus "types" which do not
  98                          * actually have anything to do with the type of the name being
  99                          * looked up.  For any other value of Type, if the type stored in
 100                          * the entry is Any (i.e. unknown), save the actual type.
 101                          */
 102
 103                         if (type != INTERNAL_TYPE_SCOPE &&
 104                                 type != INTERNAL_TYPE_DEF_ANY &&
 105                                 type != INTERNAL_TYPE_INDEX_FIELD_DEFN &&
 106                                 next_node->type == ACPI_TYPE_ANY) {
 107                                 next_node->type = (u8) type;
 108                         }
 109
 110                         *return_node = next_node;
 111                         return (AE_OK);
 112                 }
 113
 114
 115                 /*
 116                  * The last entry in the list points back to the parent,
 117                  * so a flag is used to indicate the end-of-list
 118                  */
 119                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 120                         /* Searched entire list, we are done */
 121
 122                         break;
 123                 }
 124
 125                 /* Didn't match name, move on to the next peer object */
 126
 127                 next_node = next_node->peer;
 128         }
 129
 130
 131         /* Searched entire table, not found */
 132
 133
 134         return (AE_NOT_FOUND);
 135 }
 136
 137
 138 /*******************************************************************************
 139  *
 140  * FUNCTION:    Acpi_ns_search_parent_tree
 141  *
 142  * PARAMETERS:  *Target_name        - Ascii ACPI name to search for
 143  *              *Node               - Starting table where search will begin
 144  *              Type                - Object type to match
 145  *              **Return_node       - Where the matched Named Obj is returned
 146  *
 147  * RETURN:      Status
 148  *
 149  * DESCRIPTION: Called when a name has not been found in the current namespace
 150  *              table.  Before adding it or giving up, ACPI scope rules require
 151  *              searching enclosing scopes in cases identified by Acpi_ns_local().
 152  *
 153  *              "A name is located by finding the matching name in the current
 154  *              name space, and then in the parent name space. If the parent
 155  *              name space does not contain the name, the search continues
 156  *              recursively until either the name is found or the name space
 157  *              does not have a parent (the root of the name space).  This
 158  *              indicates that the name is not found" (From ACPI Specification,
 159  *              section 5.3)
 160  *
 161  ******************************************************************************/
 162
 163 static ACPI_STATUS
 164 acpi_ns_search_parent_tree (
 165         u32                     target_name,
 166         ACPI_NAMESPACE_NODE     *node,
 167         OBJECT_TYPE_INTERNAL    type,
 168         ACPI_NAMESPACE_NODE     **return_node)
 169 {
 170         ACPI_STATUS             status;
 171         ACPI_NAMESPACE_NODE     *parent_node;
 172
 173
 174         parent_node = acpi_ns_get_parent_object (node);
 175
 176         /*
 177          * If there is no parent (at the root) or type is "local", we won't be
 178          * searching the parent tree.
 179          */
 180         if ((acpi_ns_local (type))  ||
 181                 (!parent_node)) {
 182
 183
 184                 return (AE_NOT_FOUND);
 185         }
 186
 187
 188         /* Search the parent tree */
 189
 190         /*
 191          * Search parents until found the target or we have backed up to
 192          * the root
 193          */
 194
 195         while (parent_node) {
 196                 /* Search parent scope */
 197                 /* TBD: [Investigate] Why ACPI_TYPE_ANY? */
 198
 199                 status = acpi_ns_search_node (target_name, parent_node,
 200                                    ACPI_TYPE_ANY, return_node);
 201
 202                 if (ACPI_SUCCESS (status)) {
 203                         return (status);
 204                 }
 205
 206                 /*
 207                  * Not found here, go up another level
 208                  * (until we reach the root)
 209                  */
 210
 211                 parent_node = acpi_ns_get_parent_object (parent_node);
 212         }
 213
 214
 215         /* Not found in parent tree */
 216
 217         return (AE_NOT_FOUND);
 218 }
 219
 220
 221 /*******************************************************************************
 222  *
 223  * FUNCTION:    Acpi_ns_search_and_enter
 224  *
 225  * PARAMETERS:  Target_name         - Ascii ACPI name to search for (4 chars)
 226  *              Walk_state          - Current state of the walk
 227  *              *Node               - Starting table where search will begin
 228  *              Interpreter_mode    - Add names only in MODE_Load_pass_x.
 229  *                                    Otherwise,search only.
 230  *              Type                - Object type to match
 231  *              Flags               - Flags describing the search restrictions
 232  *              **Return_node       - Where the Node is returned
 233  *
 234  * RETURN:      Status
 235  *
 236  * DESCRIPTION: Search for a name segment in a single name table,
 237  *              optionally adding it if it is not found.  If the passed
 238  *              Type is not Any and the type previously stored in the
 239  *              entry was Any (i.e. unknown), update the stored type.
 240  *
 241  *              In IMODE_EXECUTE, search only.
 242  *              In other modes, search and add if not found.
 243  *
 244  ******************************************************************************/
 245
 246 ACPI_STATUS
 247 acpi_ns_search_and_enter (
 248         u32                     target_name,
 249         ACPI_WALK_STATE         *walk_state,
 250         ACPI_NAMESPACE_NODE     *node,
 251         OPERATING_MODE          interpreter_mode,
 252         OBJECT_TYPE_INTERNAL    type,
 253         u32                     flags,
 254         ACPI_NAMESPACE_NODE     **return_node)
 255 {
 256         ACPI_STATUS             status;
 257         ACPI_NAMESPACE_NODE     *new_node;
 258
 259
 260         /* Parameter validation */
 261
 262         if (!node || !target_name || !return_node) {
 263                 REPORT_ERROR (("Ns_search_and_enter: bad (null) parameter\n"));
 264                 return (AE_BAD_PARAMETER);
 265         }
 266
 267
 268         /* Name must consist of printable characters */
 269
 270         if (!acpi_cm_valid_acpi_name (target_name)) {
 271                 REPORT_ERROR (("Ns_search_and_enter: Bad character in ACPI Name\n"));
 272                 return (AE_BAD_CHARACTER);
 273         }
 274
 275
 276         /* Try to find the name in the table specified by the caller */
 277
 278         *return_node = ENTRY_NOT_FOUND;
 279         status = acpi_ns_search_node (target_name, node,
 280                            type, return_node);
 281         if (status != AE_NOT_FOUND) {
 282                 /*
 283                  * If we found it AND the request specifies that a find is an error,
 284                  * return the error
 285                  */
 286                 if ((status == AE_OK) &&
 287                         (flags & NS_ERROR_IF_FOUND)) {
 288                         status = AE_EXIST;
 289                 }
 290
 291                 /*
 292                  * Either found it or there was an error
 293                  * -- finished either way
 294                  */
 295                 return (status);
 296         }
 297
 298
 299         /*
 300          * Not found in the table.  If we are NOT performing the
 301          * first pass (name entry) of loading the namespace, search
 302          * the parent tree (all the way to the root if necessary.)
 303          * We don't want to perform the parent search when the
 304          * namespace is actually being loaded.  We want to perform
 305          * the search when namespace references are being resolved
 306          * (load pass 2) and during the execution phase.
 307          */
 308
 309         if ((interpreter_mode != IMODE_LOAD_PASS1) &&
 310                 (flags & NS_SEARCH_PARENT)) {
 311                 /*
 312                  * Not found in table - search parent tree according
 313                  * to ACPI specification
 314                  */
 315
 316                 status = acpi_ns_search_parent_tree (target_name, node,
 317                                  type, return_node);
 318                 if (ACPI_SUCCESS (status)) {
 319                         return (status);
 320                 }
 321         }
 322
 323
 324         /*
 325          * In execute mode, just search, never add names.  Exit now.
 326          */
 327         if (interpreter_mode == IMODE_EXECUTE) {
 328                 return (AE_NOT_FOUND);
 329         }
 330
 331
 332         /* Create the new named object */
 333
 334         new_node = acpi_ns_create_node (target_name);
 335         if (!new_node) {
 336                 return (AE_NO_MEMORY);
 337         }
 338
 339         /* Install the new object into the parent's list of children */
 340
 341         acpi_ns_install_node (walk_state, node, new_node, type);
 342         *return_node = new_node;
 343
 344         return (AE_OK);
 345 }
 346