[PATCH v1 05/30] DynamicTablesPkg: AML tree interface

["Sami Mujawar" <sami.mujawar@arm.com>]

From: Pierre Gondois <pierre.gondois@arm.com>

The AML tree is composite and has the following node types:
  - Root node.
  - Object node.
  - Data node.

These nodes are part of the Fixed Arguments or the Variable
arguments list in the AML tree.

The AML tree interface provides functions to manage the fixed
and the variable argument nodes in the AML tree.

Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
Signed-off-by: Sami Mujawar <sami.mujawar@arm.com>
---
 DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.c | 1047 ++++++++++++++++++++
 DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.h |  127 +++
 2 files changed, 1174 insertions(+)

diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.c b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.c
new file mode 100644
index 0000000000000000000000000000000000000000..65dad95da2760c512563a5152ba4acf42d555019
--- /dev/null
+++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.c
@@ -0,0 +1,1047 @@
+/** @file
+  AML Tree.
+
+  Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.<BR>
+
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+**/
+
+#include <Tree/AmlTree.h>
+
+#include <AmlCoreInterface.h>
+#include <Tree/AmlNode.h>
+#include <Tree/AmlTreeTraversal.h>
+#include <Utils/AmlUtility.h>
+
+/** Get the parent node of the input Node.
+
+  @param [in] Node  Pointer to a node.
+
+  @return The parent node of the input Node.
+          NULL otherwise.
+**/
+AML_NODE_HEADER *
+EFIAPI
+AmlGetParent (
+  IN  AML_NODE_HEADER   * Node
+  )
+{
+  if (IS_AML_DATA_NODE (Node) ||
+      IS_AML_OBJECT_NODE (Node)) {
+    return Node->Parent;
+  }
+
+  return NULL;
+}
+
+/** Get the root node from any node of the tree.
+    This is done by climbing up the tree until the root node is reached.
+
+  @param  [in]  Node    Pointer to a node.
+
+  @return The root node of the tree.
+          NULL if error.
+*/
+AML_ROOT_NODE *
+EFIAPI
+AmlGetRootNode (
+  IN  CONST AML_NODE_HEADER   * Node
+  )
+{
+  if (!IS_AML_NODE_VALID (Node)) {
+    ASSERT (0);
+    return NULL;
+  }
+
+  while (!IS_AML_ROOT_NODE (Node)) {
+    Node = Node->Parent;
+    if (!IS_AML_NODE_VALID (Node)) {
+      ASSERT (0);
+      return NULL;
+    }
+  }
+  return (AML_ROOT_NODE*)Node;
+}
+
+/** Get the node at the input Index in the fixed argument list of the input
+    ObjectNode.
+
+  @param  [in]  ObjectNode  Pointer to an object node.
+  @param  [in]  Index       The Index of the fixed argument to get.
+
+  @return The node at the input Index in the fixed argument list
+          of the input ObjectNode.
+          NULL otherwise, e.g. if the node is not an object node, or no
+          node is available at this Index.
+**/
+AML_NODE_HEADER *
+EFIAPI
+AmlGetFixedArgument (
+  IN  AML_OBJECT_NODE     * ObjectNode,
+  IN  EAML_PARSE_INDEX      Index
+  )
+{
+  if (IS_AML_OBJECT_NODE (ObjectNode)) {
+    if (Index < (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (ObjectNode)) {
+      return ObjectNode->FixedArgs[Index];
+    }
+  }
+
+  return NULL;
+}
+
+/** Check whether the input Node is in the fixed argument list of its parent
+    node.
+
+  If so, IndexPtr contains this Index.
+
+  @param  [in]  Node          Pointer to a Node.
+  @param  [out] IndexPtr      Pointer holding the Index of the Node in
+                              its parent's fixed argument list.
+
+  @retval TRUE   The node is a fixed argument and the index
+                 in IndexPtr is valid.
+  @retval FALSE  The node is not a fixed argument.
+**/
+BOOLEAN
+EFIAPI
+AmlIsNodeFixedArgument (
+  IN  CONST  AML_NODE_HEADER     * Node,
+  OUT        EAML_PARSE_INDEX    * IndexPtr
+  )
+{
+  AML_NODE_HEADER         * ParentNode;
+
+  EAML_PARSE_INDEX        Index;
+  EAML_PARSE_INDEX        MaxIndex;
+
+  if ((IndexPtr == NULL)               ||
+      (!IS_AML_DATA_NODE (Node)        &&
+       !IS_AML_OBJECT_NODE (Node))) {
+    ASSERT (0);
+    return FALSE;
+  }
+
+  ParentNode = AmlGetParent ((AML_NODE_HEADER*)Node);
+  if (IS_AML_ROOT_NODE (ParentNode)) {
+    return FALSE;
+  } else if (IS_AML_DATA_NODE (ParentNode)) {
+    // Tree is inconsistent.
+    ASSERT (0);
+    return FALSE;
+  }
+
+  // Check whether the Node is in the fixed argument list.
+  MaxIndex = (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (
+                                 (AML_OBJECT_NODE*)ParentNode
+                                 );
+  for (Index = EAmlParseIndexTerm0; Index < MaxIndex; Index++) {
+    if (AmlGetFixedArgument ((AML_OBJECT_NODE*)ParentNode, Index) == Node) {
+      *IndexPtr = Index;
+      return TRUE;
+    }
+  }
+
+  return FALSE;
+}
+
+/** Set the fixed argument of the ObjectNode at the Index to the NewNode.
+
+  It is the caller's responsibility to save the old node, if desired,
+  otherwise the reference to the old node will be lost.
+  If NewNode is not NULL, set its parent to ObjectNode.
+
+  @param  [in]  ObjectNode    Pointer to an object node.
+  @param  [in]  Index         Index in the fixed argument list of
+                              the ObjectNode to set.
+  @param  [in]  NewNode       Pointer to the NewNode.
+                              Can be NULL, a data node or an object node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlSetFixedArgument (
+  IN  AML_OBJECT_NODE   * ObjectNode,
+  IN  EAML_PARSE_INDEX    Index,
+  IN  AML_NODE_HEADER   * NewNode
+  )
+{
+  if (IS_AML_OBJECT_NODE (ObjectNode)                                     &&
+      (Index <= (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (ObjectNode))  &&
+      ((NewNode == NULL)                                                  ||
+       IS_AML_OBJECT_NODE (NewNode)                                       ||
+       IS_AML_DATA_NODE (NewNode))) {
+    ObjectNode->FixedArgs[Index] = NewNode;
+
+    // If NewNode is a data node or an object node, set its parent.
+    if (NewNode != NULL) {
+      NewNode->Parent = (AML_NODE_HEADER*)ObjectNode;
+    }
+
+    return EFI_SUCCESS;
+  }
+
+  ASSERT (0);
+  return EFI_INVALID_PARAMETER;
+}
+
+/** If the given AML_NODE_HEADER has a variable list of arguments,
+    return a pointer to this list.
+    Return NULL otherwise.
+
+  @param  [in]  Node  Pointer to the AML_NODE_HEADER to check.
+
+  @return The list of variable arguments if there is one.
+          NULL otherwise.
+**/
+LIST_ENTRY *
+EFIAPI
+AmlNodeGetVariableArgList (
+  IN  CONST AML_NODE_HEADER   * Node
+  )
+{
+  if (IS_AML_ROOT_NODE (Node)) {
+    return &(((AML_ROOT_NODE*)Node)->VariableArgs);
+  } else if (IS_AML_OBJECT_NODE (Node)) {
+    return &(((AML_OBJECT_NODE*)Node)->VariableArgs);
+  }
+  return NULL;
+}
+
+/** Remove the Node from its parent's variable list of arguments.
+
+  The function will fail if the Node is in its parent's fixed
+  argument list.
+  The Node is not deleted. The deletion is done separately
+  from the removal.
+
+  @param  [in]  Node  Pointer to a Node.
+                      Must be a data node or an object node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlRemoveNodeFromVarArgList (
+  IN  AML_NODE_HEADER   * Node
+  )
+{
+  EFI_STATUS          Status;
+  AML_NODE_HEADER   * ParentNode;
+  UINT32              Size;
+
+  if ((!IS_AML_DATA_NODE (Node) &&
+       !IS_AML_OBJECT_NODE (Node))) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  ParentNode = AmlGetParent (Node);
+  if (!IS_AML_ROOT_NODE (ParentNode)  &&
+      !IS_AML_OBJECT_NODE (ParentNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Check the node is in its parent variable list of arguments.
+  if (!IsNodeInList (
+         AmlNodeGetVariableArgList (ParentNode),
+         &Node->Link)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Unlink Node from the tree.
+  RemoveEntryList (&Node->Link);
+  InitializeListHead (&Node->Link);
+  Node->Parent = NULL;
+
+  // Get the size of the node removed.
+  Status = AmlComputeSize (Node, &Size);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Propagate the information.
+  Status = AmlPropagateInformation (ParentNode, FALSE, Size, 1);
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
+
+/** Detach the Node from the tree.
+
+  The function will fail if the Node is in its parent's fixed
+  argument list.
+  The Node is not deleted. The deletion is done separately
+  from the removal.
+
+  @param  [in]  Node  Pointer to a Node.
+                      Must be a data node or an object node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlDetachNode (
+  IN  AML_NODE_HEADER   * Node
+  )
+{
+  return AmlRemoveNodeFromVarArgList (Node);
+}
+
+/** Add the NewNode to the head of the variable list of arguments
+    of the ParentNode.
+
+  @param  [in]  ParentNode  Pointer to the parent node.
+                            Must be a root or an object node.
+  @param  [in]  NewNode     Pointer to the node to add.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlVarListAddHead (
+  IN  AML_NODE_HEADER  * ParentNode,
+  IN  AML_NODE_HEADER  * NewNode
+  )
+{
+  EFI_STATUS    Status;
+  UINT32        NewSize;
+  LIST_ENTRY  * ChildrenList;
+
+  // Check arguments and that NewNode is not already attached to a tree.
+  // ParentNode != Data Node AND NewNode != Root Node AND NewNode != attached.
+  if ((!IS_AML_ROOT_NODE (ParentNode)     &&
+       !IS_AML_OBJECT_NODE (ParentNode))  ||
+      (!IS_AML_DATA_NODE (NewNode)        &&
+       !IS_AML_OBJECT_NODE (NewNode))     ||
+      !AML_NODE_IS_DETACHED (NewNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Insert it at the head of the list.
+  ChildrenList = AmlNodeGetVariableArgList (ParentNode);
+  if (ChildrenList == NULL) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  InsertHeadList (ChildrenList, &NewNode->Link);
+  NewNode->Parent = ParentNode;
+
+  // Get the size of the NewNode.
+  Status = AmlComputeSize (NewNode, &NewSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Propagate the new information.
+  Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
+
+/** Add the NewNode to the tail of the variable list of arguments
+    of the ParentNode.
+
+  NOTE: This is an internal function which does not propagate the size
+        when a new node is added.
+
+  @param  [in]  ParentNode  Pointer to the parent node.
+                            Must be a root or an object node.
+  @param  [in]  NewNode     Pointer to the node to add.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlVarListAddTailInternal (
+  IN  AML_NODE_HEADER  * ParentNode,
+  IN  AML_NODE_HEADER  * NewNode
+  )
+{
+  LIST_ENTRY  * ChildrenList;
+
+  // Check arguments and that NewNode is not already attached to a tree.
+  // ParentNode != Data Node AND NewNode != Root Node AND NewNode != attached.
+  if ((!IS_AML_ROOT_NODE (ParentNode)     &&
+       !IS_AML_OBJECT_NODE (ParentNode))  ||
+      (!IS_AML_DATA_NODE (NewNode)        &&
+       !IS_AML_OBJECT_NODE (NewNode))     ||
+      !AML_NODE_IS_DETACHED (NewNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Insert it at the tail of the list.
+  ChildrenList = AmlNodeGetVariableArgList (ParentNode);
+  if (ChildrenList == NULL) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  InsertTailList (ChildrenList, &NewNode->Link);
+  NewNode->Parent = ParentNode;
+
+  return EFI_SUCCESS;
+}
+
+/** Add the NewNode to the tail of the variable list of arguments
+    of the ParentNode.
+
+  @param  [in]  ParentNode  Pointer to the parent node.
+                            Must be a root or an object node.
+  @param  [in]  NewNode     Pointer to the node to add.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlVarListAddTail (
+  IN  AML_NODE_HEADER   * ParentNode,
+  IN  AML_NODE_HEADER   * NewNode
+  )
+{
+  EFI_STATUS  Status;
+  UINT32      NewSize;
+
+  // Add the NewNode and check arguments.
+  Status = AmlVarListAddTailInternal (ParentNode, NewNode);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Get the size of the NewNode.
+  Status = AmlComputeSize (NewNode, &NewSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Propagate the new information.
+  Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
+
+/** Add the NewNode before the Node in the list of variable
+    arguments of the Node's parent.
+
+  @param  [in]  Node      Pointer to a node.
+                          Must be a root or an object node.
+  @param  [in]  NewNode   Pointer to the node to add.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlVarListAddBefore (
+  IN  AML_NODE_HEADER  * Node,
+  IN  AML_NODE_HEADER  * NewNode
+  )
+{
+  EFI_STATUS         Status;
+  AML_NODE_HEADER  * ParentNode;
+  UINT32             NewSize;
+
+  // Check arguments and that NewNode is not already attached to a tree.
+  if ((!IS_AML_DATA_NODE (NewNode)        &&
+       !IS_AML_OBJECT_NODE (NewNode))     ||
+      !AML_NODE_IS_DETACHED (NewNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  ParentNode = AmlGetParent (Node);
+  if (!IS_AML_ROOT_NODE (ParentNode)    &&
+      !IS_AML_OBJECT_NODE (ParentNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Insert it before the input Node.
+  InsertTailList (&Node->Link, &NewNode->Link);
+  NewNode->Parent = ParentNode;
+
+  // Get the size of the NewNode.
+  Status = AmlComputeSize (NewNode, &NewSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Propagate the new information.
+  Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
+
+/** Add the NewNode after the Node in the variable list of arguments
+    of the Node's parent.
+
+  @param  [in]  Node      Pointer to a node.
+                          Must be a root or an object node.
+  @param  [in]  NewNode   Pointer to the node to add.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlVarListAddAfter (
+  IN  AML_NODE_HEADER   * Node,
+  IN  AML_NODE_HEADER   * NewNode
+  )
+{
+  EFI_STATUS          Status;
+  AML_NODE_HEADER   * ParentNode;
+  UINT32              NewSize;
+
+  // Check arguments and that NewNode is not already attached to a tree.
+  if ((!IS_AML_DATA_NODE (NewNode)        &&
+       !IS_AML_OBJECT_NODE (NewNode))     ||
+      !AML_NODE_IS_DETACHED (NewNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  ParentNode = AmlGetParent (Node);
+  if (!IS_AML_ROOT_NODE (ParentNode)    &&
+      !IS_AML_OBJECT_NODE (ParentNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Insert the new node after the input Node.
+  InsertHeadList (&Node->Link, &NewNode->Link);
+  NewNode->Parent = ParentNode;
+
+  // Get the size of the NewNode.
+  Status = AmlComputeSize (NewNode, &NewSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Propagate the new information.
+  Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
+
+/** Append a Resource Data node to the BufferOpNode.
+
+  The Resource Data node is added at the end of the variable
+  list of arguments of the BufferOpNode, but before the End Tag.
+  If no End Tag is found, the function returns an error.
+
+  @param  [in]  BufferOpNode  Buffer node containing resource data elements.
+  @param  [in]  NewRdNode     The new Resource Data node to add.
+
+  @retval  EFI_SUCCESS            The function completed successfully.
+  @retval  EFI_INVALID_PARAMETER  Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlAppendRdNode (
+  IN  AML_OBJECT_NODE   * BufferOpNode,
+  IN  AML_DATA_NODE     * NewRdNode
+  )
+{
+  EFI_STATUS        Status;
+  AML_DATA_NODE   * CurrRdNode;
+  AML_RD_HEADER     RdDataType;
+
+  if (!AmlNodeCompareOpCode (BufferOpNode, AML_BUFFER_OP, 0)  ||
+      !IS_AML_DATA_NODE (NewRdNode)                           ||
+      (NewRdNode->DataType != EAmlNodeDataTypeResourceData)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Get the first Resource data node in the variable list of
+  // argument of the BufferOp node.
+  CurrRdNode = (AML_DATA_NODE*)AmlGetNextVariableArgument (
+                                 (AML_NODE_HEADER*)BufferOpNode,
+                                 NULL
+                                 );
+  if ((CurrRdNode == NULL)             ||
+      !IS_AML_DATA_NODE (CurrRdNode)   ||
+      (CurrRdNode->DataType != EAmlNodeDataTypeResourceData)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Iterate through the Resource Data nodes to find the End Tag.
+  while (TRUE) {
+    Status = AmlGetResourceDataType (CurrRdNode, &RdDataType);
+    if (EFI_ERROR (Status)) {
+      ASSERT (0);
+      return Status;
+    }
+
+    // If the Resource Data is an End Tag,
+    // add the new node before and return.
+    if (AmlRdCompareDescId (
+          &RdDataType,
+          AML_RD_BUILD_SMALL_DESC_ID (ACPI_SMALL_END_TAG_DESCRIPTOR_NAME))) {
+      Status = AmlVarListAddBefore (
+                 (AML_NODE_HEADER*)CurrRdNode,
+                 (AML_NODE_HEADER*)NewRdNode)
+                 ;
+      if (EFI_ERROR (Status)) {
+        ASSERT (0);
+      }
+      return Status;
+    }
+
+    // Get the next Resource Data node.
+    // If this was the last node and no End Tag was found, return error.
+    // It is possible to have only one Resource Data in a BufferOp,
+    // but it should not be possible to add a new Resource Data in the list
+    // in this case.
+    CurrRdNode = (AML_DATA_NODE*)AmlGetSiblingVariableArgument (
+                                   (AML_NODE_HEADER*)CurrRdNode
+                                   );
+    if (!IS_AML_DATA_NODE (CurrRdNode)  ||
+        (CurrRdNode->DataType != EAmlNodeDataTypeResourceData)) {
+      ASSERT (0);
+      return EFI_INVALID_PARAMETER;
+    }
+  } // while
+}
+
+/** Replace the fixed argument at the Index of the ParentNode with the NewNode.
+
+  Note: This function unlinks the OldNode from the tree. It is the callers
+        responsibility to delete the OldNode if needed.
+
+  @param  [in]  ParentNode  Pointer to the parent node.
+                            Must be an object node.
+  @param  [in]  Index       Index of the fixed argument to replace.
+  @param  [in]  NewNode     The new node to insert.
+                            Must be an object node or a data node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+STATIC
+EFI_STATUS
+EFIAPI
+AmlReplaceFixedArgument (
+  IN  AML_OBJECT_NODE      * ParentNode,
+  IN  EAML_PARSE_INDEX       Index,
+  IN  AML_NODE_HEADER      * NewNode
+  )
+{
+  EFI_STATUS              Status;
+
+  AML_NODE_HEADER       * OldNode;
+  UINT32                  NewSize;
+  UINT32                  OldSize;
+  AML_PARSE_FORMAT        FixedArgType;
+
+  // Check arguments and that NewNode is not already attached to a tree.
+  if (!IS_AML_OBJECT_NODE (ParentNode)  ||
+      (!IS_AML_DATA_NODE (NewNode)      &&
+       !IS_AML_OBJECT_NODE (NewNode))   ||
+      !AML_NODE_IS_DETACHED (NewNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Perform some compatibility checks between NewNode and OldNode.
+  FixedArgType = ParentNode->AmlByteEncoding->Format[Index];
+  switch (FixedArgType) {
+    case EAmlFieldPkgLen:
+    {
+      // A FieldPkgLen can only have a parent node with the
+      // AML_IS_FIELD_ELEMENT flag.
+      if (!AmlNodeHasAttribute (
+             (AML_OBJECT_NODE*)ParentNode,
+             AML_HAS_FIELD_LIST)) {
+        ASSERT (0);
+        return EFI_INVALID_PARAMETER;
+      }
+      // Fall through.
+    }
+
+    case EAmlUInt8:
+    case EAmlUInt16:
+    case EAmlUInt32:
+    case EAmlUInt64:
+    case EAmlName:
+    case EAmlString:
+    {
+      // A uint, a name, a string and a FieldPkgLen can only be replaced by a
+      // data node of the same type.
+      // Note: This condition might be too strict, but safer.
+      if (!IS_AML_DATA_NODE (NewNode) ||
+          (((AML_DATA_NODE*)NewNode)->DataType !=
+            AmlTypeToNodeDataType (FixedArgType))) {
+        ASSERT (0);
+        return EFI_INVALID_PARAMETER;
+      }
+      break;
+    }
+
+    case EAmlObject:
+    {
+      // If it's an object node, the grammar is too complex to do any check.
+      break;
+    }
+
+    case EAmlNone:
+    default:
+    {
+      ASSERT (0);
+      return EFI_INVALID_PARAMETER;
+      break;
+    }
+  } // switch
+
+  // Replace the OldNode with the NewNode.
+  OldNode = AmlGetFixedArgument (ParentNode, Index);
+  if (!IS_AML_NODE_VALID (OldNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // Unlink the old node.
+  // Note: This function unlinks the OldNode from the tree. It is the callers
+  //       responsibility to delete the OldNode if needed.
+  OldNode->Parent = NULL;
+
+  Status = AmlSetFixedArgument (ParentNode, Index, NewNode);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Get the size of the OldNode.
+  Status = AmlComputeSize (OldNode, &OldSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Get the size of the NewNode.
+  Status = AmlComputeSize (NewNode, &NewSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Propagate the new information.
+  Status = AmlPropagateInformation (
+            (AML_NODE_HEADER*)ParentNode,
+            (NewSize > OldSize) ? TRUE : FALSE,
+            (NewSize > OldSize) ? (NewSize - OldSize) : (OldSize - NewSize),
+            0
+            );
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
+
+/** Replace the OldNode, which is in a variable list of arguments,
+    with the NewNode.
+
+  Note: This function unlinks the OldNode from the tree. It is the callers
+        responsibility to delete the OldNode if needed.
+
+  @param  [in]  OldNode   Pointer to the node to replace.
+                          Must be a data node or an object node.
+  @param  [in]  NewNode   The new node to insert.
+                          Must be a data node or an object node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlReplaceVariableArgument (
+  IN  AML_NODE_HEADER   * OldNode,
+  IN  AML_NODE_HEADER   * NewNode
+  )
+{
+  EFI_STATUS          Status;
+  UINT32              NewSize;
+  UINT32              OldSize;
+  EAML_PARSE_INDEX    Index;
+
+  AML_DATA_NODE     * NewDataNode;
+  AML_NODE_HEADER   * ParentNode;
+  LIST_ENTRY        * NextLink;
+
+  // Check arguments, that NewNode is not already attached to a tree,
+  // and that OldNode is attached and not in a fixed list of arguments.
+  if ((!IS_AML_DATA_NODE (OldNode)      &&
+       !IS_AML_OBJECT_NODE (OldNode))   ||
+      (!IS_AML_DATA_NODE (NewNode)      &&
+       !IS_AML_OBJECT_NODE (NewNode))   ||
+      !AML_NODE_IS_DETACHED (NewNode)   ||
+      AML_NODE_IS_DETACHED (OldNode)    ||
+      AmlIsNodeFixedArgument (OldNode, &Index)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  ParentNode = AmlGetParent (OldNode);
+    if (!IS_AML_ROOT_NODE (ParentNode)    &&
+        !IS_AML_OBJECT_NODE (ParentNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  NewDataNode = (AML_DATA_NODE*)NewNode;
+
+  // Check attributes if the parent node is an object node.
+  if (IS_AML_OBJECT_NODE (ParentNode)) {
+    // A child node of a node with the HAS_CHILD flag must be either a
+    // data node or an object node. This has already been checked. So,
+    // check for other cases.
+
+    if (AmlNodeHasAttribute ((AML_OBJECT_NODE*)ParentNode, AML_HAS_BYTE_LIST)) {
+      if (!IS_AML_DATA_NODE (NewNode)                       ||
+          ((NewDataNode->DataType != EAmlNodeDataTypeRaw)   &&
+           (NewDataNode->DataType != EAmlNodeDataTypeResourceData))) {
+        // A child node of a node with the BYTE_LIST flag must be a data node,
+        // containing raw data or a resource data.
+        ASSERT (0);
+        return EFI_INVALID_PARAMETER;
+      }
+    } else if (AmlNodeHasAttribute (
+                (AML_OBJECT_NODE*)ParentNode,
+                AML_HAS_FIELD_LIST)) {
+      if (!AmlNodeHasAttribute (
+             (CONST AML_OBJECT_NODE*)NewNode,
+              AML_IS_FIELD_ELEMENT)) {
+        // A child node of a node with the FIELD_LIST flag must be an object
+        // node with AML_IS_FIELD_ELEMENT flag.
+        ASSERT (0);
+        return EFI_INVALID_PARAMETER;
+      }
+    }
+  } else {
+    // Parent node is a root node.
+    // A root node cannot have a data node as its child.
+    if (!IS_AML_DATA_NODE (NewNode)) {
+      ASSERT (0);
+      return EFI_INVALID_PARAMETER;
+    }
+  }
+
+  // Unlink OldNode from the tree.
+  NextLink = RemoveEntryList (&OldNode->Link);
+  InitializeListHead (&OldNode->Link);
+  OldNode->Parent = NULL;
+
+  // Add the NewNode.
+  InsertHeadList (NextLink, &NewNode->Link);
+  NewNode->Parent = ParentNode;
+
+  // Get the size of the OldNode.
+  Status = AmlComputeSize (OldNode, &OldSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Get the size of the NewNode.
+  Status = AmlComputeSize (NewNode, &NewSize);
+  if (EFI_ERROR (Status)) {
+    ASSERT (0);
+    return Status;
+  }
+
+  // Propagate the new information.
+  Status = AmlPropagateInformation (
+             ParentNode,
+             (NewSize > OldSize) ? TRUE : FALSE,
+             (NewSize > OldSize) ? (NewSize - OldSize) : (OldSize - NewSize),
+             0
+             );
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
+
+/** Replace the OldNode by the NewNode.
+
+  Note: This function unlinks the OldNode from the tree. It is the callers
+        responsibility to delete the OldNode if needed.
+
+  @param  [in]  OldNode   Pointer to the node to replace.
+                          Must be a data node or an object node.
+  @param  [in]  NewNode   The new node to insert.
+                          Must be a data node or an object node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlReplaceArgument (
+  IN  AML_NODE_HEADER   * OldNode,
+  IN  AML_NODE_HEADER   * NewNode
+  )
+{
+  EFI_STATUS            Status;
+  AML_NODE_HEADER     * ParentNode;
+  EAML_PARSE_INDEX      Index;
+
+  // Check arguments and that NewNode is not already attached to a tree.
+  if ((!IS_AML_DATA_NODE (OldNode)      &&
+       !IS_AML_OBJECT_NODE (OldNode))   ||
+      (!IS_AML_DATA_NODE (NewNode)      &&
+       !IS_AML_OBJECT_NODE (NewNode))   ||
+      !AML_NODE_IS_DETACHED (NewNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // ParentNode can be a root node or an object node.
+  ParentNode = AmlGetParent (OldNode);
+  if (!IS_AML_ROOT_NODE (ParentNode)  &&
+      !IS_AML_OBJECT_NODE (ParentNode)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  if (AmlIsNodeFixedArgument (OldNode, &Index)) {
+    // OldNode is in its parent's fixed argument list at the Index.
+    Status = AmlReplaceFixedArgument (
+               (AML_OBJECT_NODE*)ParentNode,
+               Index,
+               NewNode
+               );
+    if (EFI_ERROR (Status)) {
+      ASSERT (0);
+      return Status;
+    }
+  } else {
+    // OldNode is not in its parent's fixed argument list.
+    // It must be in its variable list of arguments.
+    Status = AmlReplaceVariableArgument (OldNode, NewNode);
+    ASSERT_EFI_ERROR (Status);
+  }
+
+  return Status;
+}
+
+/** Delete a Node and its children.
+
+  The Node must be removed from the tree first,
+  or must be the root node.
+
+  @param  [in]  Node  Pointer to the node to delete.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlDeleteTree (
+  IN  AML_NODE_HEADER  * Node
+  )
+{
+  EFI_STATUS            Status;
+
+  EAML_PARSE_INDEX      Index;
+  EAML_PARSE_INDEX      MaxIndex;
+
+  AML_NODE_HEADER     * Arg;
+  LIST_ENTRY          * StartLink;
+  LIST_ENTRY          * CurrentLink;
+  LIST_ENTRY          * NextLink;
+
+  // Check that the node being deleted is unlinked.
+  // When removing the node, its parent pointer and
+  // its lists data structure are reset with
+  // InitializeListHead. Thus it must be detached
+  // from the tree to avoid memory leaks.
+  if (!IS_AML_NODE_VALID (Node)  ||
+      !AML_NODE_IS_DETACHED (Node)) {
+    ASSERT (0);
+    return EFI_INVALID_PARAMETER;
+  }
+
+  // 1. Recursively detach and delete the fixed arguments.
+  //    Iterate through the fixed list of arguments.
+  if (IS_AML_OBJECT_NODE (Node)) {
+    MaxIndex = (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (
+                                   (AML_OBJECT_NODE*)Node
+                                   );
+    for (Index = EAmlParseIndexTerm0; Index < MaxIndex; Index++) {
+      Arg = AmlGetFixedArgument ((AML_OBJECT_NODE*)Node, Index);
+      if (Arg == NULL) {
+        // A fixed argument is missing. The tree is inconsistent.
+        // Note: During CodeGeneration, the fixed arguments should be set
+        //       with an incrementing index, and then the variable arguments
+        //       should be added. This allows to free as many nodes as
+        //       possible if a crash occurs.
+        ASSERT (0);
+        return EFI_INVALID_PARAMETER;
+      }
+
+      // Remove the node from the fixed argument list.
+      Arg->Parent = NULL;
+      Status = AmlSetFixedArgument ((AML_OBJECT_NODE*)Node, Index, NULL);
+      if (EFI_ERROR (Status)) {
+        ASSERT (0);
+        return Status;
+      }
+
+      Status = AmlDeleteTree (Arg);
+      if (EFI_ERROR (Status)) {
+        ASSERT (0);
+        return Status;
+      }
+    }
+  }
+
+  // 2. Recursively detach and delete the variable arguments.
+  //    Iterate through the variable list of arguments.
+  StartLink = AmlNodeGetVariableArgList (Node);
+  if (StartLink != NULL) {
+    NextLink = StartLink->ForwardLink;
+    while (NextLink != StartLink) {
+      CurrentLink = NextLink;
+
+      // Unlink the node from the tree.
+      NextLink = RemoveEntryList (CurrentLink);
+      InitializeListHead (CurrentLink);
+      ((AML_NODE_HEADER*)CurrentLink)->Parent = NULL;
+
+      Status = AmlDeleteTree ((AML_NODE_HEADER*)CurrentLink);
+      if (EFI_ERROR (Status)) {
+        ASSERT (0);
+        return Status;
+      }
+    } // while
+  }
+
+  // 3. Delete the node.
+  Status = AmlDeleteNode (Node);
+  ASSERT_EFI_ERROR (Status);
+
+  return Status;
+}
diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.h b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.h
new file mode 100644
index 0000000000000000000000000000000000000000..0b3803c47c7f468ca248d717e72d161812d485d8
--- /dev/null
+++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.h
@@ -0,0 +1,127 @@
+/** @file
+  AML Tree.
+
+  Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.<BR>
+
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+**/
+
+#ifndef AML_TREE_H_
+#define AML_TREE_H_
+
+#include <AmlNodeDefines.h>
+
+/** Get the root node from any node of the tree.
+    This is done by climbing up the tree until the root node is reached.
+
+  @param  [in]  Node    Pointer to a node.
+
+  @return The root node of the tree.
+          NULL if error.
+*/
+AML_ROOT_NODE *
+EFIAPI
+AmlGetRootNode (
+  IN  CONST AML_NODE_HEADER   * Node
+  );
+
+/** Check whether the input Node is in the fixed argument list of its parent
+    node.
+
+  If so, IndexPtr contains this Index.
+
+  @param  [in]  Node          Pointer to a Node.
+  @param  [out] IndexPtr      Pointer holding the Index of the Node in
+                              its parent's fixed argument list.
+
+  @retval TRUE   The node is a fixed argument and the index
+                 in IndexPtr is valid.
+  @retval FALSE  The node is not a fixed argument.
+**/
+BOOLEAN
+EFIAPI
+AmlIsNodeFixedArgument (
+  IN  CONST  AML_NODE_HEADER     * Node,
+  OUT        EAML_PARSE_INDEX    * IndexPtr
+  );
+
+/** Set the fixed argument of the ObjectNode at the Index to the NewNode.
+
+  It is the caller's responsibility to save the old node, if desired,
+  otherwise the reference to the old node will be lost.
+  If NewNode is not NULL, set its parent to ObjectNode.
+
+  @param  [in]  ObjectNode    Pointer to an object node.
+  @param  [in]  Index         Index in the fixed argument list of
+                              the ObjectNode to set.
+  @param  [in]  NewNode       Pointer to the NewNode.
+                              Can be NULL, a data node or an object node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlSetFixedArgument (
+  IN  AML_OBJECT_NODE   * ObjectNode,
+  IN  EAML_PARSE_INDEX    Index,
+  IN  AML_NODE_HEADER   * NewNode
+  );
+
+/** If the given AML_NODE_HEADER has a variable list of arguments,
+    return a pointer to this list.
+    Return NULL otherwise.
+
+  @param  [in]  Node  Pointer to the AML_NODE_HEADER to check.
+
+  @return The list of variable arguments if there is one.
+          NULL otherwise.
+**/
+LIST_ENTRY *
+EFIAPI
+AmlNodeGetVariableArgList (
+  IN  CONST AML_NODE_HEADER   * Node
+  );
+
+/** Add the NewNode to the tail of the variable list of arguments
+    of the ParentNode.
+
+  NOTE: This is an internal function which does not propagate the size
+        when a new node is added.
+
+  @param  [in]  ParentNode  Pointer to the parent node.
+                            Must be a root or an object node.
+  @param  [in]  NewNode     Pointer to the node to add.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlVarListAddTailInternal (
+  IN  AML_NODE_HEADER  * ParentNode,
+  IN  AML_NODE_HEADER  * NewNode
+  );
+
+/** Replace the OldNode by the NewNode.
+
+  Note: This function unlinks the OldNode from the tree. It is the callers
+        responsibility to delete the OldNode if needed.
+
+  @param  [in]  OldNode   Pointer to the node to replace.
+                          Must be a data node or an object node.
+  @param  [in]  NewNode   The new node to insert.
+                          Must be a data node or an object node.
+
+  @retval EFI_SUCCESS             The function completed successfully.
+  @retval EFI_INVALID_PARAMETER   Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlReplaceArgument (
+  IN  AML_NODE_HEADER   * OldNode,
+  IN  AML_NODE_HEADER   * NewNode
+  );
+
+#endif // AML_TREE_H_
+
-- 
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'