DynamicTablesPkg/Library/Common/AmlLib/NameSpace/AmlNameSpace.c

   1 /** @file
   2   AML NameSpace.
   3
   4   Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.<BR>
   5
   6   SPDX-License-Identifier: BSD-2-Clause-Patent
   7 **/
   8
   9 /* Lexicon:
  10
  11   NameSeg:
  12   - An ASL NameSeg is a name made of at most 4 chars.
  13     Cf. ACPI 6.3 specification, s19.2.2 'Name and Pathname Terms'.
  14   - An AML NameSeg is a name made of 4 chars.
  15     Cf. ACPI 6.3 specification, s20.2.2 'Name Objects Encoding'.
  16
  17   NameString:
  18   A NameString is analogous to a pathname. It is made of 0 to 255 NameSegs.
  19   A NameString can be prefixed by a root char ('\') or 0 to 255 carets ('^').
  20
  21   A NameString can be ASL or AML encoded.
  22   AML NameStrings can have a NameString prefix (dual or multi-name prefix)
  23   between the root/carets and the list of NameSegs. If the prefix is the
  24   multi-name prefix, then the number of NameSegs is encoded on one single byte.
  25   Cf. ACPI 6.3 specification, s19.2.2 'Name and Pathname Terms'.
  26   Cf. ACPI 6.3 specification, s20.2.2 'Name Objects Encoding'.
  27
  28   Namespace level:
  29   One level in the AML Namespace level corresponds to one NameSeg. In ASL,
  30   objects names are NameStrings. This means a device can have a name which
  31   spans multiple levels.
  32   E.g.: The ASL code: Device (CLU0.CPU0) corresponds to 2 levels.
  33
  34   Namespace node:
  35   A namespace node is an object node which has an associated name, and which
  36   changes the current scope.
  37   E.g.:
  38     1. The "Device ()" ASL statement adds a name to the AML namespace and
  39        changes the current scope to the device scope, this is a namespace node.
  40     2. The "Scope ()" ASL statement changes the current scope, this is a
  41        namespace node.
  42     3. A method invocation has a name, but does not add nor change the current
  43        AML scope. This is not a namespace node.
  44
  45   - Object nodes with the AML_IN_NAMESPACE attribute are namespace nodes.
  46     Buffers (), Packages (), etc. are not part of the namespace. It is however
  47     possible to associate them with a name with the Name () ASL statement.
  48   - The root node is considered as being part of the namespace.
  49   - Some resource data elements can have a name when defining them in
  50     an ASL statement. However, this name is stripped by the ASL compiler.
  51     Thus, they don't have a name in the AML bytestream, and are therefore
  52     not part of the AML namespace.
  53   - Field list elements are part of the namespace.
  54     Fields created by an CreateXXXField () ASL statement are part of the
  55     namespace. The name of these node can be found in the third or fourth
  56     fixed argument. The exact index of the name can be found in the NameIndex
  57     field of the AML_BYTE_ENCODING array.
  58     Field are at the same level as their ASL statement in the namespace.
  59     E.g:
  60     Scope (\) {
  61       OperationRegion (REG0, SystemIO, 0x100, 0x100)
  62       Field (REG0, ByteAcc, NoLock, Preserve) {
  63         FIE0, 1,
  64         FIE1, 5
  65       }
  66
  67       Name (BUF0, Buffer (100) {})
  68       CreateField (BUF0, 5, 2, MEM0)
  69     }
  70
  71     produces this namespace:
  72     \ (Root)
  73     \-REG0
  74     \-FIE0
  75     \-FIE1
  76     \-BUF0
  77     \-MEM0
  78
  79   Raw AML pathname or Raw AML NameString:
  80   In order to easily manipulate AML NameStrings, the non-NameSegs chars are
  81   removed in raw pathnames/NameStrings. Non-NameSegs chars are the
  82   root char ('\'), carets ('^') and NameString prefixes (Dual/Multi name char).
  83   E.g. The following terminology is defined in this AML Library.
  84   ASL absolute path:  "[RootChar]AAAA.BBBB.CCCC\0"
  85   AML absolute path:  "[RootChar][MultiNamePrefix][3(NameSegs)]AAAABBBBCCCC"
  86   Raw absolute path:  "AAAABBBBCCCC"
  87
  88   Multi-name:
  89   A NameString with at least 2 NameSegs. A node can have a name which spans
  90   multiple namespace levels.
  91 */
  92
  93 #include <NameSpace/AmlNameSpace.h>
  94
  95 #include <AmlCoreInterface.h>
  96 #include <AmlDbgPrint/AmlDbgPrint.h>
  97 #include <String/AmlString.h>
  98 #include <Tree/AmlNode.h>
  99 #include <Tree/AmlTree.h>
 100 #include <Tree/AmlTreeTraversal.h>
 101
 102 /** Context of the path search callback function.
 103
 104   The function finding a node from a path and a reference node enumerates
 105   the namespace nodes in the tree and compares their absolute path with the
 106   searched path. The enumeration function uses a callback function that can
 107   receive a context.
 108   This structure is used to store the context information required in the
 109   callback function.
 110 */
 111 typedef struct AmlPathSearchContext {
 112   /// Backward stream holding the raw AML absolute searched path.
 113   AML_STREAM        * SearchPathBStream;
 114
 115   /// An empty backward stream holding a pre-allocated buffer. This prevents
 116   /// from having to do multiple allocations during the search.
 117   /// This stream is used to query the raw AML absolute path of the node
 118   /// currently being probed.
 119   AML_STREAM        * CurrNodePathBStream;
 120
 121   /// If the node being visited is the node being searched,
 122   /// i.e. its path and the searched path match,
 123   /// save its reference in this pointer.
 124   AML_NODE_HEADER   * OutNode;
 125 } AML_PATH_SEARCH_CONTEXT;
 126
 127 /** Return the first AML namespace node up in the parent hierarchy.
 128
 129     Return the root node if no namespace node is found is the hierarchy.
 130
 131   @param  [in]  Node      Node to look at the parents from.
 132                           If Node is the root node, OutNode is NULL.
 133   @param  [out] OutNode   If a namespace node is found, pointer to the
 134                           first namespace node of Node's parents.
 135                           Stop at the root node otherwise.
 136
 137   @retval EFI_SUCCESS             The function completed successfully.
 138   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 139   **/
 140 EFI_STATUS
 141 EFIAPI
 142 AmlGetFirstAncestorNameSpaceNode (
 143   IN  CONST AML_NODE_HEADER   * Node,
 144   OUT       AML_NODE_HEADER  ** OutNode
 145   )
 146 {
 147   if (!IS_AML_NODE_VALID (Node) ||
 148       (OutNode == NULL)) {
 149     ASSERT (0);
 150     return EFI_INVALID_PARAMETER;
 151   }
 152
 153   // If Node is the root node, return NULL.
 154   if (IS_AML_ROOT_NODE (Node)) {
 155     *OutNode = NULL;
 156     return EFI_SUCCESS;
 157   } else {
 158     // Else, get the parent node.
 159     Node = AmlGetParent ((AML_NODE_HEADER*)Node);
 160     if (!IS_AML_NODE_VALID (Node)) {
 161       ASSERT (0);
 162       return EFI_INVALID_PARAMETER;
 163     }
 164   }
 165
 166   // Continue getting the parent node while no namespace node is encountered.
 167   while (TRUE) {
 168     if (IS_AML_ROOT_NODE (Node)) {
 169       break;
 170     } else if (AmlNodeHasAttribute (
 171                  (CONST AML_OBJECT_NODE*)Node,
 172                  AML_IN_NAMESPACE
 173                  )) {
 174       break;
 175     } else {
 176       Node = AmlGetParent ((AML_NODE_HEADER*)Node);
 177       if (!IS_AML_NODE_VALID (Node)) {
 178         ASSERT (0);
 179         return EFI_INVALID_PARAMETER;
 180       }
 181     }
 182   } // while
 183
 184   *OutNode = (AML_NODE_HEADER*)Node;
 185   return EFI_SUCCESS;
 186 }
 187
 188 /** Climb up the AML namespace hierarchy.
 189
 190   This function get the ancestor namespace node in the AML namespace.
 191   If Levels is not zero, skip Levels namespace nodes in the AML namespace.
 192   If Levels is zero, return the first ancestor namespace node.
 193     I.e. if Levels = n, this function returns the (n + 1) ancestor.
 194
 195   @param  [in] Node         Pointer to an object node.
 196   @param  [in, out] Levels  Pointer holding a number of AML namespace levels:
 197                              - At entry, the number of levels to go up in
 198                                the AML namespace;
 199                              - At exit, the number of levels that still need
 200                                to be climbed in case of a multi-named node.
 201                                Indeed, if a node with a multi-name is found,
 202                                and Levels is less than the number of NameSegs
 203                                in this name, then the function returns with
 204                                the number of levels that still need to be
 205                                climbed.
 206                                E.g.: If the first ancestor node's name is
 207                                      "AAAA.BBBB.CCCC" and
 208                                      Levels = 2  -> i.e go up 3 levels
 209                                       \
 210                                       ...
 211                                       \-"AAAA.BBBB.CCCC"    <----- OutNode
 212                                          \-"DDDD"           <----- Node (Input)
 213
 214                                      The function should ideally return a node
 215                                      with the name "AAAA". However, it is not
 216                                      possible to split the node name
 217                                      "AAAA.BBBB.CCCC" to "AAAA".
 218                                      Thus, OutNode is set to the input node,
 219                                      and Levels = 2.
 220                                In most cases the number of levels to climb
 221                                correspond to non multi-name node, and therefore
 222                                Levels = 0 at exit.
 223   @param  [out] HasRoot     The returned node in OutNode has an AML absolute
 224                             name, starting with a root char ('\'), or if OutNode
 225                             is the root node.
 226   @param  [out] OutNode     The Levels+1 namespace ancestor of the input node in
 227                             the AML namespace. Must be the root node or a
 228                             namespace node.
 229
 230   @retval EFI_SUCCESS             The function completed successfully.
 231   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 232 **/
 233 STATIC
 234 EFI_STATUS
 235 EFIAPI
 236 AmlGetAncestorNameSpaceNode (
 237   IN      CONST AML_OBJECT_NODE   * Node,
 238   IN OUT        UINT32            * Levels,
 239      OUT        UINT32            * HasRoot,
 240      OUT  CONST AML_NODE_HEADER  ** OutNode
 241   )
 242 {
 243   EFI_STATUS                Status;
 244
 245   CONST AML_NODE_HEADER   * NameSpaceNode;
 246   CHAR8                   * NodeName;
 247   UINT32                    ParentCnt;
 248
 249   UINT32                    Root;
 250   UINT32                    ParentPrefix;
 251   UINT32                    SegCount;
 252
 253   if (!IS_AML_OBJECT_NODE (Node)    ||
 254       (Levels == NULL)              ||
 255       (HasRoot == NULL)             ||
 256       (OutNode == NULL)) {
 257     ASSERT (0);
 258     return EFI_INVALID_PARAMETER;
 259   }
 260
 261   ParentCnt = *Levels;
 262   *HasRoot = 0;
 263
 264   // ParentCnt namespace levels need to be climbed.
 265   do {
 266     // Get the next namespace node in the hierarchy.
 267     Status = AmlGetFirstAncestorNameSpaceNode (
 268                (CONST AML_NODE_HEADER*)Node,
 269                (AML_NODE_HEADER**)&NameSpaceNode
 270                );
 271     if (EFI_ERROR (Status)) {
 272       ASSERT (0);
 273       return Status;
 274     }
 275
 276     Node = (CONST AML_OBJECT_NODE*)NameSpaceNode;
 277
 278     if (IS_AML_ROOT_NODE (Node)) {
 279       // Node is the root node. It is not possible to go beyond.
 280       if (ParentCnt != 0) {
 281         ASSERT (0);
 282         return EFI_INVALID_PARAMETER;
 283       }
 284       *HasRoot = 1;
 285       break;
 286     }
 287
 288     NodeName = AmlNodeGetName ((CONST AML_OBJECT_NODE*)Node);
 289     if (NodeName == NULL) {
 290       ASSERT (0);
 291       return EFI_INVALID_PARAMETER;
 292     }
 293
 294     // Analyze the node name.
 295     Status = AmlParseNameStringInfo (
 296                 NodeName,
 297                 &Root,
 298                 &ParentPrefix,
 299                 &SegCount
 300                 );
 301     if (EFI_ERROR (Status)) {
 302       ASSERT (0);
 303       return Status;
 304     }
 305
 306     if (Root != 0) {
 307       // NodeName is an absolute pathname.
 308       *HasRoot = Root;
 309
 310       // If the node has Root then it cannot have ParentPrefixes (Carets).
 311       if (ParentPrefix != 0) {
 312         ASSERT (0);
 313         return EFI_INVALID_PARAMETER;
 314       }
 315
 316       if (SegCount == ParentCnt) {
 317         // There are exactly enough AML namespace levels to consume.
 318         // This means the root node was the searched node.
 319         Node = (CONST AML_OBJECT_NODE*)AmlGetRootNode (
 320                                          (CONST AML_NODE_HEADER*)Node
 321                                          );
 322         if (!IS_AML_ROOT_NODE (Node)) {
 323           ASSERT (0);
 324           return EFI_INVALID_PARAMETER;
 325         }
 326
 327         ParentCnt = 0;
 328         break;
 329       } else if (ParentCnt < SegCount) {
 330         // There are too many AML namespace levels in this name.
 331         // ParentCnt has the right value, just return.
 332         break;
 333       } else {
 334         // ParentCnt > SegCount
 335         // Return error as there must be at least ParentCnt AML namespace
 336         // levels left in the absolute path.
 337         ASSERT (0);
 338         return EFI_INVALID_PARAMETER;
 339       }
 340     } else {
 341       // Root is 0.
 342       if (ParentCnt < SegCount) {
 343         // NodeName is a relative path.
 344         // NodeName has enough levels to consume all the ParentCnt.
 345         // Exit.
 346         break;
 347       } else if (SegCount == ParentCnt) {
 348         // There are exactly enough AML namespace levels to consume.
 349         if (ParentPrefix == 0) {
 350           // The node name doesn't have any carets. Get the next namespace
 351           // node and return.
 352           Status = AmlGetFirstAncestorNameSpaceNode (
 353                      (CONST AML_NODE_HEADER*)Node,
 354                      (AML_NODE_HEADER**)&NameSpaceNode
 355                      );
 356           if (EFI_ERROR (Status)) {
 357             ASSERT (0);
 358             return Status;
 359           }
 360           Node = (CONST AML_OBJECT_NODE*)NameSpaceNode;
 361           ParentCnt = 0;
 362           break;
 363         } else {
 364           // The node name has carets. Need to continue climbing the
 365           // AML namespace.
 366           ParentCnt = ParentPrefix;
 367         }
 368       } else {
 369         // ParentCnt > SegCount
 370         // NodeName doesn't have enough levels to consume all the ParentCnt.
 371         // Update ParentCnt: Consume SegCount levels and add ParentPrefix
 372         // levels. Continue climbing the tree.
 373         ParentCnt = ParentCnt + ParentPrefix - SegCount;
 374       }
 375     }
 376   } while (ParentCnt != 0);
 377
 378   *OutNode = (CONST AML_NODE_HEADER*)Node;
 379   *Levels = ParentCnt;
 380
 381   return EFI_SUCCESS;
 382 }
 383
 384 /** Build the raw absolute AML pathname to Node and write it to a stream.
 385
 386   A raw AML pathname is an AML pathname where the root char ('\'),
 387   prefix chars ('^') and NameString prefix byte (e.g.: DualNamePrefix)
 388   have been removed. A raw AML pathname is a list of concatenated
 389   NameSegs.
 390
 391   E.g.:
 392   ASL absolute path:  "[RootChar]AAAA.BBBB.CCCC\0"
 393   AML absolute path:  "[RootChar][MultiNamePrefix][3(NameSegs)]AAAABBBBCCCC"
 394   Raw absolute path:  "AAAABBBBCCCC"
 395
 396   @param  [in]   Node         Node to build the raw absolute path to
 397                               Must be a root node, or a namespace node.
 398   @param  [in]  InputParent   Skip InputParent AML namespace levels before
 399                               starting building the raw absolute pathname.
 400                               E.g.: - Node's name being "^AAAA.BBBB.CCCC";
 401                                     - InputParent = 2;
 402                                     "BBBB.CCCC" will be skipped (2
 403                                     levels), and "^AAAA" will remain. The
 404                                     first caret is not related to InputParent.
 405   @param  [out]  RawAbsPathBStream  Backward stream to write the raw
 406                                     pathname to.
 407                                     If Node is the root node, the Stream data
 408                                     Buffer will stay empty.
 409                                     The stream must not be at its end.
 410
 411   @retval EFI_SUCCESS             The function completed successfully.
 412   @retval EFI_BUFFER_TOO_SMALL    No space left in the buffer.
 413   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 414 **/
 415 EFI_STATUS
 416 EFIAPI
 417 AmlGetRawNameSpacePath (
 418   IN  CONST AML_NODE_HEADER   * Node,
 419   IN        UINT32              InputParent,
 420   OUT       AML_STREAM        * RawAbsPathBStream
 421   )
 422 {
 423   EFI_STATUS          Status;
 424
 425   AML_NODE_HEADER   * ParentNode;
 426   CHAR8             * NodeName;
 427
 428   UINT32              Root;
 429   UINT32              ParentPrefix;
 430   UINT32              SegCount;
 431   CONST   CHAR8     * NameSeg;
 432
 433   if ((!IS_AML_ROOT_NODE (Node)                 &&
 434        !AmlNodeHasAttribute (
 435          (CONST AML_OBJECT_NODE*)Node,
 436          AML_IN_NAMESPACE))                     ||
 437       !IS_STREAM (RawAbsPathBStream)            ||
 438       IS_END_OF_STREAM (RawAbsPathBStream)      ||
 439       !IS_STREAM_BACKWARD (RawAbsPathBStream)   ||
 440       (InputParent > MAX_UINT8)) {
 441     ASSERT (0);
 442     return EFI_INVALID_PARAMETER;
 443   }
 444
 445   while (1) {
 446     if (IS_AML_ROOT_NODE (Node)) {
 447       break;
 448     }
 449
 450     NodeName = AmlNodeGetName ((CONST AML_OBJECT_NODE*)Node);
 451     if (NodeName == NULL) {
 452       ASSERT (0);
 453       return EFI_INVALID_PARAMETER;
 454     }
 455
 456     Status = AmlParseNameStringInfo (
 457                NodeName,
 458                &Root,
 459                &ParentPrefix,
 460                &SegCount
 461                );
 462     if (EFI_ERROR (Status)) {
 463       ASSERT (0);
 464       return Status;
 465     }
 466
 467     if (SegCount > InputParent) {
 468       // 1.1. If the Node's name has enough levels to consume all the
 469       //      InputParent carets, write the levels that are left.
 470       NameSeg = AmlGetFirstNameSeg (NodeName, Root, ParentPrefix);
 471       Status = AmlStreamWrite (
 472                   RawAbsPathBStream,
 473                   (CONST UINT8*)NameSeg,
 474                   (SegCount - InputParent) * AML_NAME_SEG_SIZE
 475                   );
 476       if (EFI_ERROR (Status)) {
 477         ASSERT (0);
 478         return Status;
 479       }
 480       InputParent = 0;
 481     } else {
 482       // (SegCount <= InputParent)
 483       // 1.2. Else save the InputParent in TotalParent to climb
 484       //      them later.
 485       InputParent -= SegCount;
 486     }
 487
 488     InputParent += ParentPrefix;
 489
 490     if (Root != 0) {
 491     // 2. The Node's name is an absolute path.
 492     //    Exit, the root has been reached.
 493       if (InputParent != 0) {
 494         ASSERT (0);
 495         return EFI_NOT_FOUND;
 496       }
 497       break;
 498     }
 499
 500     Status = AmlGetAncestorNameSpaceNode (
 501                (CONST AML_OBJECT_NODE*)Node,
 502                &InputParent,
 503                &Root,
 504                (CONST AML_NODE_HEADER**)&ParentNode
 505                );
 506     if (EFI_ERROR (Status)  ||
 507         (!IS_AML_NODE_VALID (ParentNode))) {
 508       ASSERT (0);
 509       return Status;
 510     }
 511
 512     Node = ParentNode;
 513
 514     if (IS_AML_ROOT_NODE (Node)) {
 515       // 3.1. If the root node has been found while climbing,
 516       //      no need to write NameSegs.
 517       //      Exit.
 518       break;
 519     } else if (Root != 0) {
 520       // 3.2. An absolute path has been found while climbing the tree.
 521       //      If (InputParent != 0), the raw pathname is not the root.
 522       //      Write the first [SegCount - InputParent] NameSegs of this
 523       //      absolute path.
 524       //      Then exit.
 525       if (InputParent != 0) {
 526         // Get the absolute pathname.
 527         NodeName = AmlNodeGetName ((CONST AML_OBJECT_NODE*)Node);
 528         if (NodeName == NULL) {
 529           ASSERT (0);
 530           return EFI_INVALID_PARAMETER;
 531         }
 532
 533         // Analyze the absolute pathname.
 534         Status = AmlParseNameStringInfo (
 535                     NodeName,
 536                     &Root,
 537                     &ParentPrefix,
 538                     &SegCount
 539                     );
 540         if (EFI_ERROR (Status)) {
 541           ASSERT (0);
 542           return Status;
 543         }
 544
 545         // Writing the n first NameSegs.
 546         // n = SegCount - InputParent
 547         NameSeg = AmlGetFirstNameSeg (NodeName, Root, ParentPrefix);
 548         Status = AmlStreamWrite (
 549                     RawAbsPathBStream,
 550                     (CONST UINT8*)NameSeg,
 551                     (SegCount - InputParent) * AML_NAME_SEG_SIZE
 552                     );
 553         if (EFI_ERROR (Status)) {
 554           ASSERT (0);
 555           return Status;
 556         }
 557
 558         break;
 559       } // (InputParent != 0)
 560
 561     }
 562   } // while
 563
 564   return EFI_SUCCESS;
 565 }
 566
 567 /** Add the RootChar and prefix byte to the raw AML NameString in the
 568     input Stream to create a valid absolute path.
 569
 570   The prefix byte can be AML_DUAL_NAME_PREFIX, AML_MULTI_NAME_PREFIX
 571   or nothing.
 572
 573   @param  [in, out] AmlPathBStream  The Stream initially contains a raw
 574                                     NameString (i.e. a list of NameSegs).
 575                                     The Stream can be empty (e.g.: for the
 576                                     root path).
 577                                     The stream must not be at its end.
 578
 579   @retval EFI_SUCCESS             The function completed successfully.
 580   @retval EFI_BUFFER_TOO_SMALL    No space left in the buffer.
 581   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 582 **/
 583 STATIC
 584 EFI_STATUS
 585 EFIAPI
 586 AmlAddPrefix (
 587   IN  OUT AML_STREAM    * AmlPathBStream
 588   )
 589 {
 590   EFI_STATUS    Status;
 591   UINT32        NameSegCount;
 592   UINT32        NameSegSize;
 593
 594   // At most 3 bytes are needed for: RootChar + MultiNamePrefix + SegCount.
 595   CHAR8         Prefix[3];
 596   UINT32        PrefixSize;
 597
 598   // The Stream contains concatenated NameSegs.
 599   if (!IS_STREAM (AmlPathBStream)       ||
 600       IS_END_OF_STREAM (AmlPathBStream) ||
 601       !IS_STREAM_BACKWARD (AmlPathBStream)) {
 602     ASSERT (0);
 603     return EFI_INVALID_PARAMETER;
 604   }
 605
 606   // Its size should be a multiple of AML_NAME_SEG_SIZE.
 607   // AML_NAME_SEG_SIZE = 4. Check the 2 lowest bits.
 608   NameSegSize = AmlStreamGetIndex (AmlPathBStream);
 609   if ((NameSegSize & (AML_NAME_SEG_SIZE - 1)) != 0) {
 610     ASSERT (0);
 611     return EFI_INVALID_PARAMETER;
 612   }
 613
 614   // Each NameSeg is 4 bytes so divide the NameSegSize by 4.
 615   NameSegCount = NameSegSize >> 2;
 616   if (NameSegCount > MAX_UINT8) {
 617     // There can be at most 255 NameSegs.
 618     ASSERT (0);
 619     return EFI_INVALID_PARAMETER;
 620   }
 621
 622   Prefix[0] = AML_ROOT_CHAR;
 623
 624   switch (NameSegCount) {
 625     case 0:
 626     {
 627       // Root and parents only NameString (no NameSeg(s)) end with '\0'.
 628       Prefix[1] = AML_ZERO_OP;
 629       PrefixSize = 2;
 630       break;
 631     }
 632     case 1:
 633     {
 634       PrefixSize = 1;
 635       break;
 636     }
 637     case 2:
 638     {
 639       Prefix[1] = AML_DUAL_NAME_PREFIX;
 640       PrefixSize = 2;
 641       break;
 642     }
 643     default:
 644     {
 645       Prefix[1] = AML_MULTI_NAME_PREFIX;
 646       Prefix[2] = (UINT8)NameSegCount;
 647       PrefixSize = 3;
 648       break;
 649     }
 650   }
 651
 652   // Add the RootChar + prefix (if needed) at the beginning of the pathname.
 653   Status = AmlStreamWrite (AmlPathBStream, (CONST UINT8*)Prefix, PrefixSize);
 654   if (EFI_ERROR (Status)) {
 655     ASSERT (0);
 656     return Status;
 657   }
 658
 659   return Status;
 660 }
 661
 662 /** Remove the prefix bytes of an AML NameString stored in a backward stream
 663     to get a raw NameString.
 664
 665   The AML encoding for '\', '^', Dual name or multi-name prefix are
 666   stripped off.
 667   E.g: If the ASL path was "\AAAA.BBBB", the AML equivalent would be
 668        "{RootChar}{DualNamePrefix}AAAABBBB". So resultant raw NameString
 669        is "AAAABBBB".
 670
 671   @param  [in, out] AmlPathBStream    Backward stream containing an AML
 672                                       NameString.
 673                                       The stream must not be at its end.
 674
 675   @retval EFI_SUCCESS             The function completed successfully.
 676   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 677 */
 678 STATIC
 679 EFI_STATUS
 680 EFIAPI
 681 AmlRemovePrefix (
 682   IN  OUT AML_STREAM  * AmlPathBStream
 683   )
 684 {
 685   EFI_STATUS    Status;
 686
 687   UINT32        TotalSize;
 688   UINT32        RewindSize;
 689
 690   UINT32        Root;
 691   UINT32        ParentPrefix;
 692   UINT32        SegCount;
 693
 694   if (!IS_STREAM (AmlPathBStream)         ||
 695       IS_END_OF_STREAM (AmlPathBStream)   ||
 696       !IS_STREAM_BACKWARD (AmlPathBStream)) {
 697     ASSERT (0);
 698     return EFI_INVALID_PARAMETER;
 699   }
 700
 701   Status = AmlParseNameStringInfo (
 702              (CHAR8*)AmlStreamGetCurrPos (AmlPathBStream),
 703              &Root,
 704              &ParentPrefix,
 705              &SegCount
 706              );
 707   if (EFI_ERROR (Status)) {
 708     ASSERT (0);
 709     return Status;
 710   }
 711
 712   TotalSize = AmlComputeNameStringSize (Root, ParentPrefix, SegCount);
 713   if (TotalSize == 0) {
 714     ASSERT (0);
 715     return EFI_INVALID_PARAMETER;
 716   }
 717
 718   // Rewind the stream of all the bytes that are not SegCounts
 719   // to drop the prefix.
 720   RewindSize = TotalSize - (SegCount * AML_NAME_SEG_SIZE);
 721   if (RewindSize != 0) {
 722     Status = AmlStreamRewind (AmlPathBStream, RewindSize);
 723     if (EFI_ERROR (Status)) {
 724       ASSERT (0);
 725       return Status;
 726     }
 727   }
 728
 729   return EFI_SUCCESS;
 730 }
 731
 732 /** Build the absolute ASL pathname to Node.
 733
 734   BufferSize is always updated to the size of the pathname.
 735
 736   If:
 737    - the content of BufferSize is >= to the size of the pathname AND;
 738    - Buffer is not NULL.
 739   then copy the pathname in the Buffer. A buffer of the size
 740   MAX_ASL_NAMESTRING_SIZE is big enough to receive any ASL pathname.
 741
 742   @param  [in]      Node            Node to build the absolute path to.
 743                                     Must be a root node, or a namespace node.
 744   @param  [out]     Buffer          Buffer to write the path to.
 745                                     If NULL, only update *BufferSize.
 746   @param  [in, out] BufferSize      Pointer holding:
 747                                     - At entry, the size of the Buffer;
 748                                     - At exit, the size of the pathname.
 749
 750   @retval EFI_SUCCESS             The function completed successfully.
 751   @retval EFI_BUFFER_TOO_SMALL    No space left in the buffer.
 752   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 753   @retval EFI_OUT_OF_RESOURCES    Out of memory.
 754 **/
 755 EFI_STATUS
 756 EFIAPI
 757 AmlGetAslPathName (
 758   IN      AML_NODE_HEADER   * Node,
 759       OUT CHAR8             * Buffer,
 760   IN  OUT UINT32            * BufferSize
 761   )
 762 {
 763   EFI_STATUS      Status;
 764
 765   // Backward stream used to build the raw AML absolute path to the node.
 766   AML_STREAM      RawAmlAbsPathBStream;
 767   CHAR8         * RawAmlAbsPathBuffer;
 768   UINT32          RawAmlAbsPathBufferSize;
 769
 770   CHAR8         * AmlPathName;
 771   CHAR8         * AslPathName;
 772   UINT32          AslPathNameSize;
 773
 774   UINT32          Root;
 775   UINT32          ParentPrefix;
 776   UINT32          SegCount;
 777
 778   if ((!IS_AML_ROOT_NODE (Node)         &&
 779        !AmlNodeHasAttribute (
 780          (CONST AML_OBJECT_NODE*)Node,
 781          AML_IN_NAMESPACE))             ||
 782       (BufferSize == NULL)) {
 783     ASSERT (0);
 784     return EFI_INVALID_PARAMETER;
 785   }
 786
 787   AslPathName = NULL;
 788
 789   // Allocate a Stream to get the raw AML absolute pathname.
 790   RawAmlAbsPathBufferSize = MAX_AML_NAMESTRING_SIZE;
 791   RawAmlAbsPathBuffer = AllocateZeroPool (RawAmlAbsPathBufferSize);
 792   if (RawAmlAbsPathBuffer == NULL) {
 793     ASSERT (0);
 794     return EFI_OUT_OF_RESOURCES;
 795   }
 796
 797   Status = AmlStreamInit (
 798              &RawAmlAbsPathBStream,
 799              (UINT8*)RawAmlAbsPathBuffer,
 800              RawAmlAbsPathBufferSize,
 801              EAmlStreamDirectionBackward
 802              );
 803   if (EFI_ERROR (Status)) {
 804     ASSERT (0);
 805     goto exit_handler;
 806   }
 807
 808   // Get the raw pathname of the Node. The raw pathname being an
 809   // AML NameString without the RootChar and prefix byte.
 810   // It is a list of concatenated NameSegs.
 811   Status = AmlGetRawNameSpacePath (Node, 0, &RawAmlAbsPathBStream);
 812   if (EFI_ERROR (Status)) {
 813     ASSERT (0);
 814     goto exit_handler;
 815   }
 816
 817   // Add the RootChar and prefix byte.
 818   Status = AmlAddPrefix (&RawAmlAbsPathBStream);
 819   if (EFI_ERROR (Status)) {
 820     ASSERT (0);
 821     goto exit_handler;
 822   }
 823
 824   AmlPathName = (CHAR8*)AmlStreamGetCurrPos (&RawAmlAbsPathBStream);
 825
 826   // Analyze the NameString.
 827   Status = AmlParseNameStringInfo (
 828              (CONST CHAR8*)AmlPathName,
 829              &Root,
 830              &ParentPrefix,
 831              &SegCount
 832              );
 833   if (EFI_ERROR (Status)) {
 834     ASSERT (0);
 835     goto exit_handler;
 836   }
 837
 838   // Compute the size the ASL pathname will take.
 839   AslPathNameSize = AslComputeNameStringSize (Root, ParentPrefix, SegCount);
 840   if (AslPathNameSize == 0) {
 841     ASSERT (0);
 842     Status = EFI_INVALID_PARAMETER;
 843     goto exit_handler;
 844   }
 845
 846   // Input Buffer is large enough. Copy the pathname if the Buffer is valid.
 847   if ((Buffer != NULL) && (AslPathNameSize <= *BufferSize)) {
 848     Status = ConvertAmlNameToAslName (AmlPathName, &AslPathName);
 849     if (EFI_ERROR (Status)) {
 850       ASSERT (0);
 851       Status = EFI_OUT_OF_RESOURCES;
 852       goto exit_handler;
 853     }
 854
 855     CopyMem (Buffer, AslPathName, AslPathNameSize);
 856   }
 857
 858   *BufferSize = AslPathNameSize;
 859
 860 exit_handler:
 861   // Free allocated memory.
 862   FreePool (RawAmlAbsPathBuffer);
 863   if (AslPathName != NULL) {
 864     FreePool (AslPathName);
 865   }
 866
 867   return Status;
 868 }
 869
 870 #if !defined (MDEPKG_NDEBUG)
 871
 872 /** Recursively print the pathnames in the AML namespace in Node's branch.
 873
 874   @param  [in]  Node          Pointer to a node.
 875   @param  [in]  Context       An empty forward stream holding a pre-allocated
 876                               buffer. This prevents from having to do multiple
 877                               allocations during the enumeration.
 878   @param  [in, out] Status    At entry, contains the status returned by the
 879                               last call to this exact function during the
 880                               enumeration.
 881                               As exit, contains the returned status of the
 882                               call to this function.
 883                               Optional, can be NULL.
 884
 885   @retval TRUE if the enumeration can continue or has finished without
 886           interruption.
 887   @retval FALSE if the enumeration needs to stopped or has stopped.
 888 **/
 889 STATIC
 890 BOOLEAN
 891 EFIAPI
 892 AmlDbgPrintNameSpaceCallback (
 893   IN      AML_NODE_HEADER  * Node,
 894   IN      VOID             * Context,
 895   IN  OUT EFI_STATUS       * Status   OPTIONAL
 896   )
 897 {
 898   BOOLEAN           ContinueEnum;
 899   EFI_STATUS        Status1;
 900
 901   AML_STREAM      * CurrNodePathFStream;
 902   CHAR8           * CurrNodePathBuffer;
 903   UINT32            CurrNodePathBufferSize;
 904
 905   ContinueEnum = TRUE;
 906   Status1 = EFI_SUCCESS;
 907
 908   if (!IS_AML_NODE_VALID (Node) ||
 909       (Context == NULL)) {
 910     ASSERT (0);
 911     Status1 = EFI_INVALID_PARAMETER;
 912     ContinueEnum = FALSE;
 913     goto exit_handler;
 914   }
 915
 916   if (!IS_AML_ROOT_NODE (Node)  &&
 917       !AmlNodeHasAttribute (
 918          (CONST AML_OBJECT_NODE*)Node,
 919          AML_IN_NAMESPACE)) {
 920     // Skip this node and continue enumeration.
 921     goto exit_handler;
 922   }
 923
 924   if (IS_AML_ROOT_NODE (Node)) {
 925     DEBUG ((DEBUG_INFO, "\\\n"));
 926   } else if (AmlNodeHasAttribute (
 927                (CONST AML_OBJECT_NODE*)Node,
 928                AML_IN_NAMESPACE)) {
 929
 930   CurrNodePathFStream = (AML_STREAM*)Context;
 931
 932   // Check the Context's content.
 933   if (!IS_STREAM (CurrNodePathFStream)           ||
 934       IS_END_OF_STREAM (CurrNodePathFStream)     ||
 935       !IS_STREAM_FORWARD (CurrNodePathFStream)) {
 936     ASSERT (0);
 937     Status1 = EFI_INVALID_PARAMETER;
 938     ContinueEnum = FALSE;
 939     goto exit_handler;
 940   }
 941
 942   CurrNodePathBuffer = (CHAR8*)AmlStreamGetBuffer (CurrNodePathFStream);
 943   CurrNodePathBufferSize = AmlStreamGetMaxBufferSize (CurrNodePathFStream);
 944
 945   Status1 = AmlGetAslPathName (
 946               (AML_NODE_HEADER*)Node,
 947               CurrNodePathBuffer,
 948               &CurrNodePathBufferSize
 949               );
 950   if (EFI_ERROR (Status1)) {
 951     ASSERT (0);
 952     ContinueEnum = FALSE;
 953     goto exit_handler;
 954   }
 955
 956   DEBUG ((DEBUG_INFO, "%a\n", CurrNodePathBuffer));
 957
 958   } else {
 959     ASSERT (0);
 960     Status1 = EFI_INVALID_PARAMETER;
 961     ContinueEnum = FALSE;
 962   }
 963
 964 exit_handler:
 965   if (Status != NULL) {
 966     *Status = Status1;
 967   }
 968
 969   return ContinueEnum;
 970 }
 971
 972 /** Print the absolute pathnames in the AML namespace of
 973     all the nodes in the tree starting from the Root node.
 974
 975   @param  [in]  RootNode    Pointer to a root node.
 976
 977   @retval EFI_SUCCESS             The function completed successfully.
 978   @retval EFI_BUFFER_TOO_SMALL    No space left in the buffer.
 979   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 980   @retval EFI_OUT_OF_RESOURCES    Out of memory.
 981 **/
 982 EFI_STATUS
 983 EFIAPI
 984 AmlDbgPrintNameSpace (
 985   IN  AML_ROOT_NODE   * RootNode
 986   )
 987 {
 988   EFI_STATUS      Status;
 989
 990   AML_STREAM      CurrNodePathFStream;
 991   CHAR8         * CurrNodePathBuffer;
 992   UINT32          CurrNodePathBufferSize;
 993
 994   if (!IS_AML_ROOT_NODE (RootNode)) {
 995     ASSERT (0);
 996     return EFI_INVALID_PARAMETER;
 997   }
 998
 999   DEBUG ((DEBUG_INFO, "AmlNameSpace: AML namespace:\n"));
1000
1001   // Allocate memory to build the absolute ASL path to each node.
1002   CurrNodePathBufferSize = MAX_AML_NAMESTRING_SIZE;
1003   CurrNodePathBuffer = AllocateZeroPool (CurrNodePathBufferSize);
1004   if (CurrNodePathBuffer == NULL) {
1005     ASSERT (0);
1006     return EFI_OUT_OF_RESOURCES;
1007   }
1008
1009   // An empty forward stream holding a pre-allocated buffer is used
1010   // to avoid multiple allocations during the enumeration.
1011   Status = AmlStreamInit (
1012              &CurrNodePathFStream,
1013              (UINT8*)CurrNodePathBuffer,
1014              CurrNodePathBufferSize,
1015              EAmlStreamDirectionForward
1016              );
1017   if (EFI_ERROR (Status)) {
1018     ASSERT (0);
1019     goto exit_handler;
1020   }
1021
1022   AmlEnumTree (
1023     (AML_NODE_HEADER*)RootNode,
1024     AmlDbgPrintNameSpaceCallback,
1025     (VOID*)&CurrNodePathFStream,
1026     &Status
1027     );
1028   ASSERT_EFI_ERROR (Status);
1029
1030 exit_handler:
1031   FreePool (CurrNodePathBuffer);
1032
1033   return Status;
1034 }
1035
1036 #endif // MDEPKG_NDEBUG
1037
1038 /** Callback function to find the node corresponding to an absolute pathname.
1039
1040   For each namespace node, build its raw AML absolute path. Then compare this
1041   path with the raw AML absolute path of the search node available in the
1042   Context.
1043
1044   @param  [in]      Node      Pointer to the node to whose pathname is being
1045                               tested.
1046   @param  [in, out] Context   A pointer to AML_PATH_SEARCH_CONTEXT that has:
1047                                - The searched path stored in a stream;
1048                                - An empty stream to query the pathname of the
1049                                  probed node;
1050                                - A node pointer to store the searched node
1051                                  if found.
1052   @param  [in, out] Status    At entry, contains the status returned by the
1053                               last call to this exact function during the
1054                               enumeration.
1055                               As exit, contains the returned status of the
1056                               call to this function.
1057                               Optional, can be NULL.
1058
1059   @retval TRUE if the enumeration can continue or has finished without
1060           interruption.
1061   @retval FALSE if the enumeration needs to stopped or has stopped.
1062 **/
1063 STATIC
1064 BOOLEAN
1065 EFIAPI
1066 AmlEnumeratePathCallback (
1067   IN      AML_NODE_HEADER  * Node,
1068   IN  OUT VOID             * Context,
1069   IN  OUT EFI_STATUS       * Status   OPTIONAL
1070 )
1071 {
1072   BOOLEAN                     ContinueEnum;
1073   EFI_STATUS                  Status1;
1074
1075   AML_PATH_SEARCH_CONTEXT   * PathSearchContext;
1076
1077   AML_STREAM                * SearchPathBStream;
1078   CHAR8                     * SearchedPath;
1079
1080   AML_STREAM                * CurrNodePathBStream;
1081   CHAR8                     * CurrNodePath;
1082   UINT32                      CurrNodePathSize;
1083
1084   ContinueEnum = TRUE;
1085   Status1 = EFI_SUCCESS;
1086
1087   if (!IS_AML_NODE_VALID (Node) ||
1088       (Context == NULL)) {
1089     ASSERT (0);
1090     Status1 = EFI_INVALID_PARAMETER;
1091     ContinueEnum = FALSE;
1092     goto exit_handler;
1093   }
1094
1095   if (!AmlNodeHasAttribute (
1096          (CONST AML_OBJECT_NODE*)Node,
1097          AML_IN_NAMESPACE)) {
1098     goto exit_handler;
1099   }
1100
1101   PathSearchContext = (AML_PATH_SEARCH_CONTEXT*)Context;
1102   SearchPathBStream = PathSearchContext->SearchPathBStream;
1103   CurrNodePathBStream = PathSearchContext->CurrNodePathBStream;
1104
1105   // Check the Context's content.
1106   if (!IS_STREAM (SearchPathBStream)            ||
1107       IS_END_OF_STREAM (SearchPathBStream)      ||
1108       !IS_STREAM_BACKWARD (SearchPathBStream)   ||
1109       !IS_STREAM (CurrNodePathBStream)          ||
1110       IS_END_OF_STREAM (CurrNodePathBStream)    ||
1111       !IS_STREAM_BACKWARD (CurrNodePathBStream)) {
1112     ASSERT (0);
1113     Status1 = EFI_INVALID_PARAMETER;
1114     ContinueEnum = FALSE;
1115     goto exit_handler;
1116   }
1117
1118   CurrNodePathSize = AmlStreamGetMaxBufferSize (CurrNodePathBStream);
1119   if (CurrNodePathSize == 0) {
1120     ASSERT (0);
1121     Status1 = EFI_INVALID_PARAMETER;
1122     ContinueEnum = FALSE;
1123     goto exit_handler;
1124   }
1125
1126   SearchedPath = (CHAR8*)AmlStreamGetCurrPos (SearchPathBStream);
1127   CurrNodePath = (CHAR8*)AmlStreamGetCurrPos (CurrNodePathBStream);
1128
1129   // Get the raw AML absolute pathname of the current node.
1130   Status1 = AmlGetRawNameSpacePath (Node, 0, CurrNodePathBStream);
1131   if (EFI_ERROR (Status1)) {
1132     ASSERT (0);
1133     ContinueEnum = FALSE;
1134     goto exit_handler;
1135   }
1136
1137   DEBUG ((
1138     DEBUG_VERBOSE,
1139     "AmlNameSpace: "
1140     "Comparing search path with current node path.\n"
1141     ));
1142   DEBUG ((DEBUG_VERBOSE, "Search path:"));
1143   AmlDbgPrintChars (
1144     DEBUG_VERBOSE,
1145     (CHAR8*)AmlStreamGetCurrPos (SearchPathBStream),
1146     AmlStreamGetIndex (SearchPathBStream)
1147     );
1148   DEBUG ((DEBUG_VERBOSE, "\nPath of the current node: "));
1149   AmlDbgPrintChars (
1150     DEBUG_VERBOSE,
1151     (CHAR8*)AmlStreamGetCurrPos (CurrNodePathBStream),
1152     AmlStreamGetIndex (CurrNodePathBStream)
1153     );
1154   DEBUG ((DEBUG_VERBOSE, "\n"));
1155
1156   // Compare the searched path and Node's path.
1157   if ((AmlStreamGetIndex (CurrNodePathBStream)  ==
1158          AmlStreamGetIndex (SearchPathBStream))     &&
1159       (CompareMem (
1160          AmlStreamGetCurrPos (CurrNodePathBStream),
1161          AmlStreamGetCurrPos (SearchPathBStream),
1162          AmlStreamGetIndex (SearchPathBStream)) == 0)) {
1163     Status1 = EFI_SUCCESS;
1164     ContinueEnum = FALSE;
1165     PathSearchContext->OutNode = Node;
1166   } else {
1167     // If the paths don't match, reset the CurrNodePathStream's content.
1168     Status1 = AmlStreamReset (CurrNodePathBStream);
1169     if (EFI_ERROR (Status1)) {
1170       ASSERT (0);
1171       ContinueEnum = FALSE;
1172     }
1173   }
1174
1175 exit_handler:
1176   if (Status != NULL) {
1177     *Status = Status1;
1178   }
1179
1180   return ContinueEnum;
1181 }
1182
1183 /** Build a raw AML absolute path from a reference node and a relative
1184     ASL path.
1185
1186   The AslPath can be a relative path or an absolute path.
1187   Node must be a root node or a namespace node.
1188   A root node is expected to be at the top of the tree.
1189
1190   @param  [in]  ReferenceNode               Reference node.
1191                                             If a relative path is given, the
1192                                             search is done from this node. If
1193                                             an absolute path is given, the
1194                                             search is done from the root node.
1195                                             Must be a root node or an object
1196                                             node which is part of the
1197                                             namespace.
1198   @param  [in]  AslPath                     ASL path to the searched node in
1199                                             the namespace. An ASL path name is
1200                                             NULL terminated. Can be a relative
1201                                             or absolute path.
1202                                             E.g.: "\\_SB.CLU0.CPU0".
1203   @param  [in, out] RawAmlAbsSearchPathBStream  Backward stream to write the
1204                                                 raw absolute AML path of the
1205                                                 searched node.
1206                                                 The stream must not be at
1207                                                 its end.
1208
1209   @retval EFI_SUCCESS             The function completed successfully.
1210   @retval EFI_BUFFER_TOO_SMALL    No space left in the buffer.
1211   @retval EFI_INVALID_PARAMETER   Invalid parameter.
1212   @retval EFI_OUT_OF_RESOURCES    Out of memory.
1213 **/
1214 STATIC
1215 EFI_STATUS
1216 EFIAPI
1217 AmlBuildAbsoluteAmlPath (
1218   IN      AML_NODE_HEADER   * ReferenceNode,
1219   IN      CHAR8             * AslPath,
1220   IN  OUT AML_STREAM        * RawAmlAbsSearchPathBStream
1221   )
1222 {
1223   EFI_STATUS    Status;
1224   CHAR8       * AmlPath;
1225
1226   UINT32        AmlNameStringSize;
1227   UINT32        Root;
1228   UINT32        ParentPrefix;
1229   UINT32        SegCount;
1230
1231   if ((!IS_AML_ROOT_NODE (ReferenceNode)              &&
1232        !AmlNodeHasAttribute (
1233          (CONST AML_OBJECT_NODE*)ReferenceNode,
1234          AML_IN_NAMESPACE))                           ||
1235       (AslPath == NULL)                               ||
1236       !IS_STREAM (RawAmlAbsSearchPathBStream)         ||
1237       IS_END_OF_STREAM (RawAmlAbsSearchPathBStream)   ||
1238       !IS_STREAM_BACKWARD (RawAmlAbsSearchPathBStream)) {
1239     ASSERT (0);
1240     return EFI_INVALID_PARAMETER;
1241   }
1242
1243   // 1. Validate, analyze and convert the AslPath to an AmlPath.
1244   Status = ConvertAslNameToAmlName (AslPath, &AmlPath);
1245   if (EFI_ERROR (Status)) {
1246     ASSERT (0);
1247     return Status;
1248   }
1249
1250   Status = AmlParseNameStringInfo (AmlPath, &Root, &ParentPrefix, &SegCount);
1251   if (EFI_ERROR (Status)) {
1252     ASSERT (0);
1253     goto exit_handler;
1254   }
1255
1256   // Not possible to go beyond the root.
1257   if (IS_AML_ROOT_NODE (ReferenceNode) && (ParentPrefix != 0)) {
1258     Status = EFI_INVALID_PARAMETER;
1259     ASSERT (0);
1260     goto exit_handler;
1261   }
1262
1263   AmlNameStringSize = AmlComputeNameStringSize (Root, ParentPrefix, SegCount);
1264   if (AmlNameStringSize == 0) {
1265     Status = EFI_INVALID_PARAMETER;
1266     ASSERT (0);
1267     goto exit_handler;
1268   }
1269
1270   // 2.1. Write the AML path to the stream.
1271   Status = AmlStreamWrite (
1272               RawAmlAbsSearchPathBStream,
1273               (CONST UINT8*)AmlPath,
1274               AmlNameStringSize
1275               );
1276   if (EFI_ERROR (Status)) {
1277     ASSERT (0);
1278     goto exit_handler;
1279   }
1280
1281   // 2.2. Then remove the AML prefix (root char, parent prefix, etc.)
1282   //      to obtain a raw AML NameString. Raw AML NameString are easier
1283   //      to manipulate.
1284   Status = AmlRemovePrefix (RawAmlAbsSearchPathBStream);
1285   if (EFI_ERROR (Status)) {
1286     ASSERT (0);
1287     goto exit_handler;
1288   }
1289
1290   // 3. If AslPath is a relative path and the reference Node is not
1291   //    the root node, fill the Stream with the absolute path to the
1292   //    reference node.
1293   if ((Root == 0) && !IS_AML_ROOT_NODE (ReferenceNode)) {
1294     Status = AmlGetRawNameSpacePath (
1295                ReferenceNode,
1296                ParentPrefix,
1297                RawAmlAbsSearchPathBStream
1298                );
1299     if (EFI_ERROR (Status)) {
1300       ASSERT (0);
1301     }
1302   }
1303
1304 exit_handler:
1305   // Free allocated memory.
1306   FreePool (AmlPath);
1307
1308   return Status;
1309 }
1310
1311 /** Find a node in the AML namespace, given an ASL path and a reference Node.
1312
1313    - The AslPath can be an absolute path, or a relative path from the
1314      reference Node;
1315    - Node must be a root node or a namespace node;
1316    - A root node is expected to be at the top of the tree.
1317
1318   E.g.:
1319   For the following AML namespace, with the ReferenceNode being the node with
1320   the name "AAAA":
1321    - the node with the name "BBBB" can be found by looking for the ASL
1322      path "BBBB";
1323    - the root node can be found by looking for the ASL relative path "^",
1324      or the absolute path "\\".
1325
1326   AML namespace:
1327   \
1328   \-AAAA      <- ReferenceNode
1329     \-BBBB
1330
1331   @param  [in]  ReferenceNode   Reference node.
1332                                 If a relative path is given, the
1333                                 search is done from this node. If
1334                                 an absolute path is given, the
1335                                 search is done from the root node.
1336                                 Must be a root node or an object
1337                                 node which is part of the
1338                                 namespace.
1339   @param  [in]  AslPath         ASL path to the searched node in
1340                                 the namespace. An ASL path name is
1341                                 NULL terminated. Can be a relative
1342                                 or absolute path.
1343                                 E.g.: "\\_SB.CLU0.CPU0" or "^CPU0"
1344   @param  [out] OutNode         Pointer to the found node.
1345                                 Contains NULL if not found.
1346
1347   @retval EFI_SUCCESS             The function completed successfully.
1348   @retval EFI_BUFFER_TOO_SMALL    No space left in the buffer.
1349   @retval EFI_INVALID_PARAMETER   Invalid parameter.
1350   @retval EFI_OUT_OF_RESOURCES    Out of memory.
1351 **/
1352 EFI_STATUS
1353 EFIAPI
1354 AmlFindNode (
1355   IN  AML_NODE_HEADER     * ReferenceNode,
1356   IN  CHAR8               * AslPath,
1357   OUT AML_NODE_HEADER    ** OutNode
1358   )
1359 {
1360   EFI_STATUS                  Status;
1361
1362   AML_PATH_SEARCH_CONTEXT     PathSearchContext;
1363   AML_ROOT_NODE             * RootNode;
1364
1365   // Backward stream used to build the raw AML absolute path to the searched
1366   // node.
1367   AML_STREAM                  RawAmlAbsSearchPathBStream;
1368   CHAR8                     * RawAmlAbsSearchPathBuffer;
1369   UINT32                      RawAmlAbsSearchPathBufferSize;
1370
1371   // Backward stream used to store the raw AML absolute path of the node
1372   // currently enumerated in the tree. This path can then be compared to the
1373   // RawAmlAbsSearchPath.
1374   AML_STREAM                  RawAmlAbsCurrNodePathBStream;
1375   CHAR8                     * RawAmlAbsCurrNodePathBuffer;
1376   UINT32                      RawAmlAbsCurrNodePathBufferSize;
1377
1378   if ((!IS_AML_ROOT_NODE (ReferenceNode)        &&
1379        !AmlNodeHasAttribute (
1380          (CONST AML_OBJECT_NODE*)ReferenceNode,
1381          AML_IN_NAMESPACE))                     ||
1382       (AslPath == NULL)                         ||
1383       (OutNode == NULL)) {
1384     ASSERT (0);
1385     return EFI_INVALID_PARAMETER;
1386   }
1387
1388   *OutNode = NULL;
1389   RawAmlAbsCurrNodePathBuffer = NULL;
1390
1391   // 1. Build a raw absolute AML path from the reference node and the ASL
1392   //    path. For this:
1393   // 1.1. First initialize a backward stream.
1394   RawAmlAbsSearchPathBufferSize = MAX_AML_NAMESTRING_SIZE;
1395   RawAmlAbsSearchPathBuffer = AllocateZeroPool (RawAmlAbsSearchPathBufferSize);
1396   if (RawAmlAbsSearchPathBuffer == NULL) {
1397     ASSERT (0);
1398     return EFI_OUT_OF_RESOURCES;
1399   }
1400
1401   Status = AmlStreamInit (
1402              &RawAmlAbsSearchPathBStream,
1403              (UINT8*)RawAmlAbsSearchPathBuffer,
1404              RawAmlAbsSearchPathBufferSize,
1405              EAmlStreamDirectionBackward
1406              );
1407   if (EFI_ERROR (Status)) {
1408     ASSERT (0);
1409     goto exit_handler;
1410   }
1411
1412   // 1.2. Then build the raw AML absolute path.
1413   Status = AmlBuildAbsoluteAmlPath (
1414              ReferenceNode,
1415              AslPath,
1416              &RawAmlAbsSearchPathBStream
1417              );
1418   if (EFI_ERROR (Status)) {
1419     ASSERT (0);
1420     goto exit_handler;
1421   }
1422
1423   // 2. Find the root node by climbing up the tree from the reference node.
1424   RootNode = AmlGetRootNode (ReferenceNode);
1425   if (RootNode == NULL) {
1426     ASSERT (0);
1427     Status = EFI_INVALID_PARAMETER;
1428     goto exit_handler;
1429   }
1430
1431   // 3. If the searched node is the root node, return.
1432   //    For the Root Node there is no NameSegs so the length of
1433   //     the stream will be zero.
1434   if (AmlStreamGetIndex (&RawAmlAbsSearchPathBStream) == 0) {
1435     *OutNode = (AML_NODE_HEADER*)RootNode;
1436     Status = EFI_SUCCESS;
1437     goto exit_handler;
1438   }
1439
1440   // 4. Create a backward stream large enough to hold the current node path
1441   //    during enumeration. This prevents from doing multiple allocation/free
1442   //    operations.
1443   RawAmlAbsCurrNodePathBufferSize = MAX_ASL_NAMESTRING_SIZE;
1444   RawAmlAbsCurrNodePathBuffer = AllocateZeroPool (
1445                                   RawAmlAbsCurrNodePathBufferSize
1446                                   );
1447   if (RawAmlAbsCurrNodePathBuffer == NULL) {
1448     ASSERT (0);
1449     Status = EFI_OUT_OF_RESOURCES;
1450     goto exit_handler;
1451   }
1452
1453   Status = AmlStreamInit (
1454              &RawAmlAbsCurrNodePathBStream,
1455              (UINT8*)RawAmlAbsCurrNodePathBuffer,
1456              RawAmlAbsCurrNodePathBufferSize,
1457              EAmlStreamDirectionBackward
1458              );
1459   if (EFI_ERROR (Status)) {
1460     ASSERT (0);
1461     goto exit_handler;
1462   }
1463
1464   // 5. Fill a path search context structure with:
1465   //     - SearchPathStream: backward stream containing the raw absolute AML
1466   //       path to the searched node;
1467   //     - CurrNodePathStream: backward stream containing the raw absolute AML
1468   //       of the node currently being enumerated;
1469   //     - OutNode: node pointer to the store the potentially found node.
1470   PathSearchContext.SearchPathBStream = &RawAmlAbsSearchPathBStream;
1471   PathSearchContext.CurrNodePathBStream = &RawAmlAbsCurrNodePathBStream;
1472   PathSearchContext.OutNode = NULL;
1473
1474   // 6. Iterate through the namespace nodes of the tree.
1475   //    For each namespace node, build its raw AML absolute path. Then compare
1476   //    it with the search path.
1477   AmlEnumTree (
1478     (AML_NODE_HEADER*)RootNode,
1479     AmlEnumeratePathCallback,
1480     (VOID*)&PathSearchContext,
1481     &Status
1482     );
1483   if (EFI_ERROR (Status)) {
1484     ASSERT (0);
1485     goto exit_handler;
1486   }
1487
1488   *OutNode = PathSearchContext.OutNode;
1489   if (*OutNode == NULL) {
1490     Status = EFI_NOT_FOUND;
1491   }
1492
1493 exit_handler:
1494   // Free allocated memory.
1495   FreePool (RawAmlAbsSearchPathBuffer);
1496   if (RawAmlAbsCurrNodePathBuffer != NULL) {
1497     FreePool (RawAmlAbsCurrNodePathBuffer);
1498   }
1499
1500   return Status;
1501 }