pswalk.c revision 67754
1/****************************************************************************** 2 * 3 * Module Name: pswalk - Parser routines to walk parsed op tree(s) 4 * $Revision: 47 $ 5 * 6 *****************************************************************************/ 7 8/****************************************************************************** 9 * 10 * 1. Copyright Notice 11 * 12 * Some or all of this work - Copyright (c) 1999, Intel Corp. All rights 13 * reserved. 14 * 15 * 2. License 16 * 17 * 2.1. This is your license from Intel Corp. under its intellectual property 18 * rights. You may have additional license terms from the party that provided 19 * you this software, covering your right to use that party's intellectual 20 * property rights. 21 * 22 * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a 23 * copy of the source code appearing in this file ("Covered Code") an 24 * irrevocable, perpetual, worldwide license under Intel's copyrights in the 25 * base code distributed originally by Intel ("Original Intel Code") to copy, 26 * make derivatives, distribute, use and display any portion of the Covered 27 * Code in any form, with the right to sublicense such rights; and 28 * 29 * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent 30 * license (with the right to sublicense), under only those claims of Intel 31 * patents that are infringed by the Original Intel Code, to make, use, sell, 32 * offer to sell, and import the Covered Code and derivative works thereof 33 * solely to the minimum extent necessary to exercise the above copyright 34 * license, and in no event shall the patent license extend to any additions 35 * to or modifications of the Original Intel Code. No other license or right 36 * is granted directly or by implication, estoppel or otherwise; 37 * 38 * The above copyright and patent license is granted only if the following 39 * conditions are met: 40 * 41 * 3. Conditions 42 * 43 * 3.1. Redistribution of Source with Rights to Further Distribute Source. 44 * Redistribution of source code of any substantial portion of the Covered 45 * Code or modification with rights to further distribute source must include 46 * the above Copyright Notice, the above License, this list of Conditions, 47 * and the following Disclaimer and Export Compliance provision. In addition, 48 * Licensee must cause all Covered Code to which Licensee contributes to 49 * contain a file documenting the changes Licensee made to create that Covered 50 * Code and the date of any change. Licensee must include in that file the 51 * documentation of any changes made by any predecessor Licensee. Licensee 52 * must include a prominent statement that the modification is derived, 53 * directly or indirectly, from Original Intel Code. 54 * 55 * 3.2. Redistribution of Source with no Rights to Further Distribute Source. 56 * Redistribution of source code of any substantial portion of the Covered 57 * Code or modification without rights to further distribute source must 58 * include the following Disclaimer and Export Compliance provision in the 59 * documentation and/or other materials provided with distribution. In 60 * addition, Licensee may not authorize further sublicense of source of any 61 * portion of the Covered Code, and must include terms to the effect that the 62 * license from Licensee to its licensee is limited to the intellectual 63 * property embodied in the software Licensee provides to its licensee, and 64 * not to intellectual property embodied in modifications its licensee may 65 * make. 66 * 67 * 3.3. Redistribution of Executable. Redistribution in executable form of any 68 * substantial portion of the Covered Code or modification must reproduce the 69 * above Copyright Notice, and the following Disclaimer and Export Compliance 70 * provision in the documentation and/or other materials provided with the 71 * distribution. 72 * 73 * 3.4. Intel retains all right, title, and interest in and to the Original 74 * Intel Code. 75 * 76 * 3.5. Neither the name Intel nor any other trademark owned or controlled by 77 * Intel shall be used in advertising or otherwise to promote the sale, use or 78 * other dealings in products derived from or relating to the Covered Code 79 * without prior written authorization from Intel. 80 * 81 * 4. Disclaimer and Export Compliance 82 * 83 * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED 84 * HERE. ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE 85 * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT, ASSISTANCE, 86 * INSTALLATION, TRAINING OR OTHER SERVICES. INTEL WILL NOT PROVIDE ANY 87 * UPDATES, ENHANCEMENTS OR EXTENSIONS. INTEL SPECIFICALLY DISCLAIMS ANY 88 * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A 89 * PARTICULAR PURPOSE. 90 * 91 * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES 92 * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR 93 * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT, 94 * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY 95 * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL 96 * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES. THESE LIMITATIONS 97 * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY 98 * LIMITED REMEDY. 99 * 100 * 4.3. Licensee shall not export, either directly or indirectly, any of this 101 * software or system incorporating such software without first obtaining any 102 * required license or other approval from the U. S. Department of Commerce or 103 * any other agency or department of the United States Government. In the 104 * event Licensee exports any such software from the United States or 105 * re-exports any such software from a foreign destination, Licensee shall 106 * ensure that the distribution and export/re-export of the software is in 107 * compliance with all laws, regulations, orders, or other restrictions of the 108 * U.S. Export Administration Regulations. Licensee agrees that neither it nor 109 * any of its subsidiaries will export/re-export any technical data, process, 110 * software, or service, directly or indirectly, to any country for which the 111 * United States government or any agency thereof requires an export license, 112 * other governmental approval, or letter of assurance, without first obtaining 113 * such license, approval or letter. 114 * 115 *****************************************************************************/ 116 117 118#include "acpi.h" 119#include "amlcode.h" 120#include "acparser.h" 121#include "acdispat.h" 122#include "acnamesp.h" 123#include "acinterp.h" 124 125#define _COMPONENT PARSER 126 MODULE_NAME ("pswalk") 127 128 129/******************************************************************************* 130 * 131 * FUNCTION: AcpiPsGetNextWalkOp 132 * 133 * PARAMETERS: WalkState - Current state of the walk 134 * Op - Current Op to be walked 135 * AscendingCallback - Procedure called when Op is complete 136 * 137 * RETURN: Status 138 * 139 * DESCRIPTION: Get the next Op in a walk of the parse tree. 140 * 141 ******************************************************************************/ 142 143ACPI_STATUS 144AcpiPsGetNextWalkOp ( 145 ACPI_WALK_STATE *WalkState, 146 ACPI_PARSE_OBJECT *Op, 147 ACPI_PARSE_UPWARDS AscendingCallback) 148{ 149 ACPI_PARSE_OBJECT *Next; 150 ACPI_PARSE_OBJECT *Parent; 151 ACPI_PARSE_OBJECT *GrandParent; 152 ACPI_STATUS Status; 153 154 155 FUNCTION_TRACE_PTR ("PsGetNextWalkOp", Op); 156 157 158 /* Check for a argument only if we are descending in the tree */ 159 160 if (WalkState->NextOpInfo != NEXT_OP_UPWARD) 161 { 162 /* Look for an argument or child of the current op */ 163 164 Next = AcpiPsGetArg (Op, 0); 165 if (Next) 166 { 167 /* Still going downward in tree (Op is not completed yet) */ 168 169 WalkState->PrevOp = Op; 170 WalkState->NextOp = Next; 171 WalkState->NextOpInfo = NEXT_OP_DOWNWARD; 172 173 return_ACPI_STATUS (AE_OK); 174 } 175 176 177 /* 178 * No more children, this Op is complete. Save Next and Parent 179 * in case the Op object gets deleted by the callback routine 180 */ 181 182 Next = Op->Next; 183 Parent = Op->Parent; 184 185 Status = AscendingCallback (WalkState, Op); 186 187 switch (Status) 188 { 189 case AE_CTRL_TERMINATE: 190 191 /* 192 * A control method was terminated via a RETURN statement. 193 * The walk of this method is complete. 194 */ 195 WalkState->PrevOp = WalkState->Origin; 196 WalkState->NextOp = NULL; 197 198 return_ACPI_STATUS (AE_OK); 199 break; 200 201 202 case AE_CTRL_FALSE: 203 204 /* 205 * Either an IF/WHILE Predicate was false or we encountered a BREAK 206 * opcode. In both cases, we do not execute the rest of the 207 * package; We simply close out the parent (finishing the walk of 208 * this branch of the tree) and continue execution at the parent 209 * level. 210 */ 211 212 Next = Parent->Next; 213 Status = AE_OK; 214 215 /* 216 * If there is a sibling to the parent, we must close out the 217 * parent now, because we are going to continue to go downward (to 218 * the sibling) in the parse tree. 219 */ 220 if (Next) 221 { 222 Status = AscendingCallback (WalkState, Parent); 223 224 /* The parent sibling will be next */ 225 226 WalkState->PrevOp = Op; 227 WalkState->NextOp = Next; 228 WalkState->NextOpInfo = NEXT_OP_DOWNWARD; 229 230 /* Continue downward */ 231 232 return_ACPI_STATUS (AE_OK); 233 } 234 235 /* 236 * Drop into the loop below because we are moving upwards in 237 * the tree 238 */ 239 240 break; 241 242 243 default: 244 /* 245 * If we are back to the starting point, the walk is complete. 246 */ 247 if (Op == WalkState->Origin) 248 { 249 /* Reached the point of origin, the walk is complete */ 250 251 WalkState->PrevOp = Op; 252 WalkState->NextOp = NULL; 253 254 return_ACPI_STATUS (Status); 255 } 256 257 /* 258 * Check for a sibling to the current op. A sibling means 259 * we are still going "downward" in the tree. 260 */ 261 262 if (Next) 263 { 264 /* There is a sibling, it will be next */ 265 266 WalkState->PrevOp = Op; 267 WalkState->NextOp = Next; 268 WalkState->NextOpInfo = NEXT_OP_DOWNWARD; 269 270 /* Continue downward */ 271 272 return_ACPI_STATUS (Status); 273 } 274 275 /* 276 * No sibling, but check status. 277 * Abort on error from callback routine 278 */ 279 if (ACPI_FAILURE (Status)) 280 { 281 /* Next op will be the parent */ 282 283 WalkState->PrevOp = Op; 284 WalkState->NextOp = Parent; 285 WalkState->NextOpInfo = NEXT_OP_UPWARD; 286 287 return_ACPI_STATUS (Status); 288 } 289 290 /* 291 * Drop into the loop below because we are moving upwards in 292 * the tree 293 */ 294 295 break; 296 } 297 } 298 299 else 300 { 301 /* 302 * We are resuming a walk, and we were (are) going upward in the tree. 303 * So, we want to drop into the parent loop below. 304 */ 305 306 Parent = Op; 307 } 308 309 310 /* 311 * Look for a sibling of the current Op's parent 312 * Continue moving up the tree until we find a node that has not been 313 * visited, or we get back to where we started. 314 */ 315 while (Parent) 316 { 317 /* We are moving up the tree, therefore this parent Op is complete */ 318 319 GrandParent = Parent->Parent; 320 Next = Parent->Next; 321 322 Status = AscendingCallback (WalkState, Parent); 323 324 325 switch (Status) 326 { 327 case AE_CTRL_FALSE: 328 329 /* 330 * Either an IF/WHILE Predicate was false or we encountered a 331 * BREAK opcode. In both cases, we do not execute the rest of the 332 * package; We simply close out the parent (finishing the walk of 333 * this branch of the tree) and continue execution at the parent 334 * level. 335 */ 336 337 Parent = GrandParent; 338 Next = GrandParent->Next; 339 GrandParent = GrandParent->Parent; 340 341 Status = AscendingCallback (WalkState, Parent); 342 343 /* Now continue to the next node in the tree */ 344 345 break; 346 347 348 case AE_CTRL_TRUE: 349 350 /* 351 * Predicate of a WHILE was true and the loop just completed an 352 * execution. Go back to the start of the loop and reevaluate the 353 * predicate. 354 */ 355 356 Op = WalkState->ControlState->Control.PredicateOp; 357 358 WalkState->ControlState->Common.State = CONTROL_PREDICATE_EXECUTING; 359 360 /* 361 * AcpiEvaluate the predicate again (next) 362 * Because we will traverse WHILE tree again 363 */ 364 365 WalkState->PrevOp = Op->Parent; 366 WalkState->NextOp = Op; 367 WalkState->NextOpInfo = NEXT_OP_DOWNWARD; 368 369 return_ACPI_STATUS (AE_OK); 370 break; 371 372 373 case AE_CTRL_TERMINATE: 374 375 /* 376 * A control method was terminated via a RETURN statement. 377 * The walk of this method is complete. 378 */ 379 WalkState->PrevOp = WalkState->Origin; 380 WalkState->NextOp = NULL; 381 382 return_ACPI_STATUS (AE_OK); 383 break; 384 } 385 386 387 /* 388 * If we are back to the starting point, the walk is complete. 389 */ 390 if (Parent == WalkState->Origin) 391 { 392 /* Reached the point of origin, the walk is complete */ 393 394 WalkState->PrevOp = Parent; 395 WalkState->NextOp = NULL; 396 397 return_ACPI_STATUS (Status); 398 } 399 400 401 /* 402 * If there is a sibling to this parent (it is not the starting point 403 * Op), then we will visit it. 404 */ 405 if (Next) 406 { 407 /* found sibling of parent */ 408 409 WalkState->PrevOp = Parent; 410 WalkState->NextOp = Next; 411 WalkState->NextOpInfo = NEXT_OP_DOWNWARD; 412 413 return_ACPI_STATUS (Status); 414 } 415 416 /* 417 * No sibling, check for an error from closing the parent 418 * (Also, AE_PENDING if a method call was encountered) 419 */ 420 if (ACPI_FAILURE (Status)) 421 { 422 WalkState->PrevOp = Parent; 423 WalkState->NextOp = GrandParent; 424 WalkState->NextOpInfo = NEXT_OP_UPWARD; 425 426 return_ACPI_STATUS (Status); 427 } 428 429 /* No siblings, no errors, just move up one more level in the tree */ 430 431 Op = Parent; 432 Parent = GrandParent; 433 WalkState->PrevOp = Op; 434 } 435 436 437 /* Got all the way to the top of the tree, we must be done! */ 438 /* However, the code should have terminated in the loop above */ 439 440 WalkState->NextOp = NULL; 441 442 return_ACPI_STATUS (AE_OK); 443} 444 445 446/******************************************************************************* 447 * 448 * FUNCTION: AcpiPsWalkLoop 449 * 450 * PARAMETERS: WalkList - State of the walk 451 * StartOp - Starting Op of the subtree to be walked 452 * DescendingCallback - Procedure called when a new Op is 453 * encountered 454 * AscendingCallback - Procedure called when Op is complete 455 * 456 * RETURN: Status 457 * 458 * DESCRIPTION: Perform a walk of the parsed AML tree. Begins and terminates at 459 * the StartOp. 460 * 461 ******************************************************************************/ 462 463ACPI_STATUS 464AcpiPsWalkLoop ( 465 ACPI_WALK_LIST *WalkList, 466 ACPI_PARSE_OBJECT *StartOp, 467 ACPI_PARSE_DOWNWARDS DescendingCallback, 468 ACPI_PARSE_UPWARDS AscendingCallback) 469{ 470 ACPI_STATUS Status = AE_OK; 471 ACPI_WALK_STATE *WalkState; 472 ACPI_PARSE_OBJECT *Op = StartOp; 473 474 475 FUNCTION_TRACE_PTR ("PsWalkLoop", StartOp); 476 477 478 WalkState = AcpiDsGetCurrentWalkState (WalkList); 479 480 481 /* Walk entire subtree, visiting all nodes depth-first */ 482 483 while (Op) 484 { 485 if (WalkState->NextOpInfo != NEXT_OP_UPWARD) 486 { 487 Status = DescendingCallback (Op->Opcode, Op, WalkState, NULL); 488 } 489 490 /* 491 * A TRUE exception means that an ELSE was detected, but the IF 492 * predicate evaluated TRUE. 493 */ 494 if (Status == AE_CTRL_TRUE) 495 { 496 /* 497 * Ignore the entire ELSE block by moving on to the the next opcode. 498 * And we do that by simply going up in the tree (either to the next 499 * sibling or to the parent) from here. 500 */ 501 502 WalkState->NextOpInfo = NEXT_OP_UPWARD; 503 } 504 505 /* Get the next node (op) in the depth-first walk */ 506 507 Status = AcpiPsGetNextWalkOp (WalkState, Op, AscendingCallback); 508 509 /* 510 * A PENDING exception means that a control method invocation has been 511 * detected 512 */ 513 514 if (Status == AE_CTRL_PENDING) 515 { 516 /* Transfer control to the called control method */ 517 518 Status = AcpiDsCallControlMethod (WalkList, WalkState, Op); 519 520 /* 521 * If the transfer to the new method method call worked, a new walk 522 * state was created -- get it 523 */ 524 525 WalkState = AcpiDsGetCurrentWalkState (WalkList); 526 } 527 528 /* Abort the walk on any exception */ 529 530 if (ACPI_FAILURE (Status)) 531 { 532 return_ACPI_STATUS (Status); 533 } 534 535 Op = WalkState->NextOp; 536 } 537 538 return_ACPI_STATUS (AE_OK); 539} 540 541 542/******************************************************************************* 543 * 544 * FUNCTION: AcpiPsWalkParsedAml 545 * 546 * PARAMETERS: StartOp - Starting Op of the subtree to be walked 547 * EndOp - Where to terminate the walk 548 * DescendingCallback - Procedure called when a new Op is 549 * encountered 550 * AscendingCallback - Procedure called when Op is complete 551 * 552 * RETURN: Status 553 * 554 * DESCRIPTION: Top level interface to walk the parsed AML tree. Handles 555 * preemption of executing control methods. 556 * 557 * NOTE: The EndOp is usually only different from the StartOp if 558 * we don't want to visit the StartOp during the tree descent. 559 * 560 ******************************************************************************/ 561 562ACPI_STATUS 563mmmmAcpiPsWalkParsedAml ( 564 ACPI_PARSE_OBJECT *StartOp, 565 ACPI_PARSE_OBJECT *EndOp, 566 ACPI_OPERAND_OBJECT *MthDesc, 567 ACPI_NAMESPACE_NODE *StartNode, 568 ACPI_OPERAND_OBJECT **Params, 569 ACPI_OPERAND_OBJECT **CallerReturnDesc, 570 ACPI_OWNER_ID OwnerId, 571 ACPI_PARSE_DOWNWARDS DescendingCallback, 572 ACPI_PARSE_UPWARDS AscendingCallback) 573{ 574 ACPI_PARSE_OBJECT *Op; 575 ACPI_WALK_STATE *WalkState; 576 ACPI_OPERAND_OBJECT *ReturnDesc; 577 ACPI_STATUS Status; 578 ACPI_WALK_LIST WalkList; 579 ACPI_WALK_LIST *PrevWalkList; 580 581 582 FUNCTION_TRACE_PTR ("PsWalkParsedAml", StartOp); 583 584 585 /* Parameter Validation */ 586 587 if (!StartOp || !EndOp) 588 { 589 return (AE_BAD_PARAMETER); 590 } 591 592 /* Initialize a new walk list */ 593 594 WalkList.WalkState = NULL; 595 596 WalkState = AcpiDsCreateWalkState (OwnerId, EndOp, MthDesc, &WalkList); 597 if (!WalkState) 598 { 599 return_ACPI_STATUS (AE_NO_MEMORY); 600 } 601 602 /* TBD: [Restructure] TEMP until we pass WalkState to the interpreter 603 */ 604 PrevWalkList = AcpiGbl_CurrentWalkList; 605 AcpiGbl_CurrentWalkList = &WalkList; 606 607 if (StartNode) 608 { 609 /* Push start scope on scope stack and make it current */ 610 611 Status = AcpiDsScopeStackPush (StartNode, ACPI_TYPE_METHOD, WalkState); 612 if (ACPI_FAILURE (Status)) 613 { 614 return_ACPI_STATUS (Status); 615 } 616 617 } 618 619 if (MthDesc) 620 { 621 /* Init arguments if this is a control method */ 622 /* TBD: [Restructure] add walkstate as a param */ 623 624 AcpiDsMethodDataInitArgs (Params, MTH_NUM_ARGS, WalkState); 625 } 626 627 Op = StartOp; 628 Status = AE_OK; 629 630 631 /* 632 * Execute the walk loop as long as there is a valid Walk State. This 633 * handles nested control method invocations without recursion. 634 */ 635 636 DEBUG_PRINT (TRACE_PARSE, ("PsWalkParsedAml: Op=%p EndOp=%p State=%p\n", 637 Op, EndOp, WalkState)); 638 639 while (WalkState) 640 { 641 if (ACPI_SUCCESS (Status)) 642 { 643 Status = AcpiPsWalkLoop (&WalkList, Op, DescendingCallback, 644 AscendingCallback); 645 } 646 647 DEBUG_PRINT (TRACE_PARSE, 648 ("PsWalkParsedAml: Completed one call to walk loop, State=%p\n", 649 WalkState)); 650 651 /* We are done with this walk, move on to the parent if any */ 652 653 BREAKPOINT3; 654 655 WalkState = AcpiDsPopWalkState (&WalkList); 656 657 /* Extract return value before we delete WalkState */ 658 659 ReturnDesc = WalkState->ReturnDesc; 660 661 DEBUG_PRINT (TRACE_PARSE, 662 ("PsWalkParsedAml: ReturnValue=%p, State=%p\n", 663 WalkState->ReturnDesc, WalkState)); 664 665 /* Reset the current scope to the beginning of scope stack */ 666 667 AcpiDsScopeStackClear (WalkState); 668 669 /* 670 * If we just returned from the execution of a control method, 671 * there's lots of cleanup to do 672 */ 673 674 if (WalkState->MethodDesc) 675 { 676 AcpiDsTerminateControlMethod (WalkState); 677 } 678 679 /* Delete this walk state and all linked control states */ 680 681 AcpiDsDeleteWalkState (WalkState); 682 683 /* Check if we have restarted a preempted walk */ 684 685 WalkState = AcpiDsGetCurrentWalkState (&WalkList); 686 if (WalkState && 687 ACPI_SUCCESS (Status)) 688 { 689 /* There is another walk state, restart it */ 690 691 /* 692 * If the method returned value is not used by the parent, 693 * The object is deleted 694 */ 695 696 AcpiDsRestartControlMethod (WalkState, ReturnDesc); 697 698 /* Get the next Op to process */ 699 700 Op = WalkState->NextOp; 701 } 702 703 /* 704 * Just completed a 1st-level method, save the final internal return 705 * value (if any) 706 */ 707 708 else if (CallerReturnDesc) 709 { 710 *CallerReturnDesc = ReturnDesc; /* NULL if no return value */ 711 } 712 713 else if (ReturnDesc) 714 { 715 /* Caller doesn't want it, must delete it */ 716 717 AcpiCmRemoveReference (ReturnDesc); 718 } 719 } 720 721 722 AcpiGbl_CurrentWalkList = PrevWalkList; 723 724 return_ACPI_STATUS (Status); 725} 726 727 728