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