drivers/acpi/namespace/nssearch.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nssearch - Namespace search
   4  *              $Revision: 62 $
   5  *
   6  ******************************************************************************/
   7
   8 /*
   9  *  Copyright (C) 2000 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          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
  75         /*
  76          * Search for name in this table, which is to say that we must search
  77          * for the name among the children of this object
  78          */
  79
  80         next_node = node->child;
  81         while (next_node) {
  82                 /* Check for match against the name */
  83
  84                 if (next_node->name == target_name) {
  85                         /*
  86                          * Found matching entry.  Capture type if
  87                          * appropriate before returning the entry.
  88                          */
  89
  90                         /*
  91                          * The Def_field_defn and Bank_field_defn cases
  92                          * are actually looking up the Region in which
  93                          * the field will be defined
  94                          */
  95
  96                         if ((INTERNAL_TYPE_DEF_FIELD_DEFN == type) ||
  97                                 (INTERNAL_TYPE_BANK_FIELD_DEFN == type))
  98                         {
  99                                 type = ACPI_TYPE_REGION;
 100                         }
 101
 102                         /*
 103                          * Scope, Def_any, and Index_field_defn are bogus
 104                          * "types" which do not actually have anything
 105                          * to do with the type of the name being looked
 106                          * up.  For any other value of Type, if the type
 107                          * stored in the entry is Any (i.e. unknown),
 108                          * save the actual type.
 109                          */
 110
 111                         if (type != INTERNAL_TYPE_SCOPE &&
 112                                 type != INTERNAL_TYPE_DEF_ANY &&
 113                                 type != INTERNAL_TYPE_INDEX_FIELD_DEFN &&
 114                                 next_node->type == ACPI_TYPE_ANY)
 115                         {
 116                                 next_node->type = (u8) type;
 117                         }
 118
 119                         *return_node = next_node;
 120                         return (AE_OK);
 121                 }
 122
 123
 124                 /*
 125                  * The last entry in the list points back to the parent,
 126                  * so a flag is used to indicate the end-of-list
 127                  */
 128                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 129                         /* Searched entire list, we are done */
 130
 131                         break;
 132                 }
 133
 134                 /* Didn't match name, move on to the next peer object */
 135
 136                 next_node = next_node->peer;
 137         }
 138
 139
 140         /* Searched entire table, not found */
 141
 142
 143         return (AE_NOT_FOUND);
 144 }
 145
 146
 147 /*******************************************************************************
 148  *
 149  * FUNCTION:    Acpi_ns_search_parent_tree
 150  *
 151  * PARAMETERS:  *Target_name        - Ascii ACPI name to search for
 152  *              *Node           - Starting table where search will begin
 153  *              Type                - Object type to match
 154  *              **Return_node   - Where the matched Named Obj is returned
 155  *
 156  * RETURN:      Status
 157  *
 158  * DESCRIPTION: Called when a name has not been found in the current namespace
 159  *              table.  Before adding it or giving up, ACPI scope rules require
 160  *              searching enclosing scopes in cases identified by Acpi_ns_local().
 161  *
 162  *              "A name is located by finding the matching name in the current
 163  *              name space, and then in the parent name space. If the parent
 164  *              name space does not contain the name, the search continues
 165  *              recursively until either the name is found or the name space
 166  *              does not have a parent (the root of the name space).  This
 167  *              indicates that the name is not found" (From ACPI Specification,
 168  *              section 5.3)
 169  *
 170  ******************************************************************************/
 171
 172 static ACPI_STATUS
 173 acpi_ns_search_parent_tree (
 174         u32                     target_name,
 175         ACPI_NAMESPACE_NODE     *node,
 176         OBJECT_TYPE_INTERNAL    type,
 177         ACPI_NAMESPACE_NODE     **return_node)
 178 {
 179         ACPI_STATUS             status;
 180         ACPI_NAMESPACE_NODE     *parent_node;
 181
 182
 183         parent_node = acpi_ns_get_parent_object (node);
 184
 185         /*
 186          * If there is no parent (at the root) or type is "local", we won't be
 187          * searching the parent tree.
 188          */
 189         if ((acpi_ns_local (type))  ||
 190                 (!parent_node))
 191         {
 192
 193
 194                 return (AE_NOT_FOUND);
 195         }
 196
 197
 198         /* Search the parent tree */
 199
 200         /*
 201          * Search parents until found the target or we have backed up to
 202          * the root
 203          */
 204
 205         while (parent_node) {
 206                 /* Search parent scope */
 207                 /* TBD: [Investigate] Why ACPI_TYPE_ANY? */
 208
 209                 status = acpi_ns_search_node (target_name, parent_node,
 210                                    ACPI_TYPE_ANY, return_node);
 211
 212                 if (ACPI_SUCCESS (status)) {
 213                         return (status);
 214                 }
 215
 216                 /*
 217                  * Not found here, go up another level
 218                  * (until we reach the root)
 219                  */
 220
 221                 parent_node = acpi_ns_get_parent_object (parent_node);
 222         }
 223
 224
 225         /* Not found in parent tree */
 226
 227         return (AE_NOT_FOUND);
 228 }
 229
 230
 231 /*******************************************************************************
 232  *
 233  * FUNCTION:    Acpi_ns_search_and_enter
 234  *
 235  * PARAMETERS:  Target_name         - Ascii ACPI name to search for (4 chars)
 236  *              Walk_state          - Current state of the walk
 237  *              *Node           - Starting table where search will begin
 238  *              Interpreter_mode    - Add names only in MODE_Load_pass_x.
 239  *                                    Otherwise,search only.
 240  *              Type                - Object type to match
 241  *              Flags               - Flags describing the search restrictions
 242  *              **Return_node   - Where the Node is returned
 243  *
 244  * RETURN:      Status
 245  *
 246  * DESCRIPTION: Search for a name segment in a single name table,
 247  *              optionally adding it if it is not found.  If the passed
 248  *              Type is not Any and the type previously stored in the
 249  *              entry was Any (i.e. unknown), update the stored type.
 250  *
 251  *              In IMODE_EXECUTE, search only.
 252  *              In other modes, search and add if not found.
 253  *
 254  ******************************************************************************/
 255
 256 ACPI_STATUS
 257 acpi_ns_search_and_enter (
 258         u32                     target_name,
 259         ACPI_WALK_STATE         *walk_state,
 260         ACPI_NAMESPACE_NODE     *node,
 261         OPERATING_MODE          interpreter_mode,
 262         OBJECT_TYPE_INTERNAL    type,
 263         u32                     flags,
 264         ACPI_NAMESPACE_NODE     **return_node)
 265 {
 266         ACPI_STATUS             status;
 267         ACPI_NAMESPACE_NODE     *new_node;
 268
 269
 270         /* Parameter validation */
 271
 272         if (!node || !target_name || !return_node) {
 273                 REPORT_ERROR (("Ns_search_and_enter: bad (null) parameter\n"));
 274                 return (AE_BAD_PARAMETER);
 275         }
 276
 277
 278         /* Name must consist of printable characters */
 279
 280         if (!acpi_cm_valid_acpi_name (target_name)) {
 281                 REPORT_ERROR (("Ns_search_and_enter: Bad character in ACPI Name\n"));
 282                 return (AE_BAD_CHARACTER);
 283         }
 284
 285
 286         /* Try to find the name in the table specified by the caller */
 287
 288         *return_node = ENTRY_NOT_FOUND;
 289         status = acpi_ns_search_node (target_name, node,
 290                            type, return_node);
 291         if (status != AE_NOT_FOUND) {
 292                 /*
 293                  * If we found it AND the request specifies that a
 294                  * find is an error, return the error
 295                  */
 296                 if ((status == AE_OK) &&
 297                         (flags & NS_ERROR_IF_FOUND))
 298                 {
 299                         status = AE_EXIST;
 300                 }
 301
 302                 /*
 303                  * Either found it or there was an error
 304                  * -- finished either way
 305                  */
 306                 return (status);
 307         }
 308
 309
 310         /*
 311          * Not found in the table.  If we are NOT performing the
 312          * first pass (name entry) of loading the namespace, search
 313          * the parent tree (all the way to the root if necessary.)
 314          * We don't want to perform the parent search when the
 315          * namespace is actually being loaded.  We want to perform
 316          * the search when namespace references are being resolved
 317          * (load pass 2) and during the execution phase.
 318          */
 319
 320         if ((interpreter_mode != IMODE_LOAD_PASS1) &&
 321                 (flags & NS_SEARCH_PARENT))
 322         {
 323                 /*
 324                  * Not found in table - search parent tree according
 325                  * to ACPI specification
 326                  */
 327
 328                 status = acpi_ns_search_parent_tree (target_name, node,
 329                                  type, return_node);
 330                 if (ACPI_SUCCESS (status)) {
 331                         return (status);
 332                 }
 333         }
 334
 335
 336         /*
 337          * In execute mode, just search, never add names.  Exit now.
 338          */
 339         if (interpreter_mode == IMODE_EXECUTE) {
 340                 return (AE_NOT_FOUND);
 341         }
 342
 343
 344         /* Create the new named object */
 345
 346         new_node = acpi_ns_create_node (target_name);
 347         if (!new_node) {
 348                 return (AE_NO_MEMORY);
 349         }
 350
 351         /* Install the new object into the parent's list of children */
 352
 353         acpi_ns_install_node (walk_state, node, new_node, type);
 354         *return_node = new_node;
 355
 356         return (AE_OK);
 357 }
 358