From e2c1104c504024b6bbee7c34a87cc9add59f37d5 Mon Sep 17 00:00:00 2001 From: Pierre Gondois Date: Mon, 3 Aug 2020 16:39:57 +0100 Subject: DynamicTablesPkg: AML tree iterator The AML tree iterator provides interfaces to traverse the nodes in the AML tree. The iterator can traverse the AML tree nodes in the following order: - Linear progression: Iterate following the AML byte stream order (depth first). - Branch progression: Iterate following the AML byte stream order (depth first), but stop iterating at the end of the branch. Signed-off-by: Pierre Gondois Signed-off-by: Sami Mujawar Reviewed-by: Alexei Fedorov --- .../Library/Common/AmlLib/Tree/AmlTreeIterator.c | 353 +++++++++++++++++++++ .../Library/Common/AmlLib/Tree/AmlTreeIterator.h | 220 +++++++++++++ 2 files changed, 573 insertions(+) create mode 100644 DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c create mode 100644 DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h (limited to 'DynamicTablesPkg') diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c new file mode 100644 index 0000000000..e99c234990 --- /dev/null +++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c @@ -0,0 +1,353 @@ +/** @file + AML Tree Iterator. + + Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.
+ + SPDX-License-Identifier: BSD-2-Clause-Patent +**/ + +#include +#include + +#include +#include + +/** Iterator to traverse the tree. + + This is an internal structure. +*/ +typedef struct AmlTreeInternalIterator { + /// External iterator structure, containing the external APIs. + /// Must be the first field. + AML_TREE_ITERATOR Iterator; + + // Note: The following members of this structure are opaque to the users + // of the Tree iterator APIs. + + /// Pointer to the node on which the iterator has been initialized. + CONST AML_NODE_HEADER * InitialNode; + + /// Pointer to the current node. + CONST AML_NODE_HEADER * CurrentNode; + + /// Iteration mode. + /// Allow to choose how to traverse the tree/choose which node is next. + EAML_ITERATOR_MODE Mode; +} AML_TREE_ITERATOR_INTERNAL; + +/** Get the current node of an iterator. + + @param [in] Iterator Pointer to an iterator. + @param [out] OutNode Pointer holding the current node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +AmlIteratorGetNode ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HEADER ** OutNode + ) +{ + AML_TREE_ITERATOR_INTERNAL * InternalIterator; + + InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator; + + // CurrentNode can be NULL, but InitialNode cannot. + if ((OutNode == NULL) || + (InternalIterator == NULL) || + (InternalIterator->Mode <= EAmlIteratorUnknown) || + (InternalIterator->Mode >= EAmlIteratorModeMax) || + !IS_AML_NODE_VALID (InternalIterator->InitialNode) || + ((InternalIterator->CurrentNode != NULL) && + !IS_AML_NODE_VALID (InternalIterator->CurrentNode))) { + ASSERT (0); + return EFI_INVALID_PARAMETER; + } + + *OutNode = (AML_NODE_HEADER*)InternalIterator->CurrentNode; + + return EFI_SUCCESS; +} + +/** Move the current node of the iterator to the next node, + according to the iteration mode selected. + + If NextNode is not NULL, return the next node. + + @param [in] Iterator Pointer to an iterator. + @param [out] NextNode If not NULL, updated to the next node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +AmlIteratorGetNextLinear ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HEADER ** NextNode + ) +{ + AML_TREE_ITERATOR_INTERNAL * InternalIterator; + + InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator; + + // CurrentNode can be NULL, but InitialNode cannot. + if ((InternalIterator == NULL) || + (InternalIterator->Mode != EAmlIteratorLinear) || + !IS_AML_NODE_VALID (InternalIterator->InitialNode) || + !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) { + ASSERT (0); + return EFI_INVALID_PARAMETER; + } + + // Get the next node according to the iteration mode. + InternalIterator->CurrentNode = AmlGetNextNode ( + InternalIterator->CurrentNode + ); + + if (NextNode != NULL) { + *NextNode = (AML_NODE_HEADER*)InternalIterator->CurrentNode; + } + return EFI_SUCCESS; +} + +/** Move the current node of the iterator to the previous node, + according to the iteration mode selected. + + If PrevNode is not NULL, return the previous node. + + @param [in] Iterator Pointer to an iterator. + @param [out] PrevNode If not NULL, updated to the previous node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +AmlIteratorGetPreviousLinear ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HEADER ** PrevNode + ) +{ + AML_TREE_ITERATOR_INTERNAL * InternalIterator; + + InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator; + + // CurrentNode can be NULL, but InitialNode cannot. + if ((InternalIterator == NULL) || + (InternalIterator->Mode != EAmlIteratorLinear) || + !IS_AML_NODE_VALID (InternalIterator->InitialNode) || + !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) { + ASSERT (0); + return EFI_INVALID_PARAMETER; + } + + // Get the previous node according to the iteration mode. + InternalIterator->CurrentNode = AmlGetPreviousNode ( + InternalIterator->CurrentNode + ); + if (PrevNode != NULL) { + *PrevNode = (AML_NODE_HEADER*)InternalIterator->CurrentNode; + } + return EFI_SUCCESS; +} + +/** Move the current node of the iterator to the next node, + according to the iteration mode selected. + + If NextNode is not NULL, return the next node. + + @param [in] Iterator Pointer to an iterator. + @param [out] NextNode If not NULL, updated to the next node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +AmlIteratorGetNextBranch ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HEADER ** NextNode + ) +{ + AML_TREE_ITERATOR_INTERNAL * InternalIterator; + AML_NODE_HEADER * Node; + + InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator; + + // CurrentNode can be NULL, but InitialNode cannot. + if ((InternalIterator == NULL) || + (InternalIterator->Mode != EAmlIteratorBranch) || + !IS_AML_NODE_VALID (InternalIterator->InitialNode) || + !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) { + ASSERT (0); + return EFI_INVALID_PARAMETER; + } + + Node = AmlGetNextNode (InternalIterator->CurrentNode); + // Check whether NextNode is a sibling of InitialNode. + if (AmlGetParent (Node) == + AmlGetParent ((AML_NODE_HEADER*)InternalIterator->InitialNode)) { + Node = NULL; + } + + InternalIterator->CurrentNode = Node; + + if (NextNode != NULL) { + *NextNode = Node; + } + return EFI_SUCCESS; +} + +/** Move the current node of the iterator to the previous node, + according to the iteration mode selected. + + If PrevNode is not NULL, return the previous node. + + @param [in] Iterator Pointer to an iterator. + @param [out] PrevNode If not NULL, updated to the previous node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +STATIC +EFI_STATUS +EFIAPI +AmlIteratorGetPreviousBranch ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HEADER ** PrevNode + ) +{ + AML_TREE_ITERATOR_INTERNAL * InternalIterator; + AML_NODE_HEADER * Node; + + InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator; + + // CurrentNode can be NULL, but InitialNode cannot. + if ((InternalIterator == NULL) || + (InternalIterator->Mode != EAmlIteratorBranch) || + !IS_AML_NODE_VALID (InternalIterator->InitialNode) || + !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) { + ASSERT (0); + return EFI_INVALID_PARAMETER; + } + + Node = AmlGetPreviousNode (InternalIterator->CurrentNode); + // Check whether PreviousNode is a sibling of InitialNode. + if (AmlGetParent (Node) == + AmlGetParent ((AML_NODE_HEADER*)InternalIterator->InitialNode)) { + Node = NULL; + } + + InternalIterator->CurrentNode = Node; + + if (PrevNode != NULL) { + *PrevNode = Node; + } + return EFI_SUCCESS; +} + +/** Initialize an iterator. + + Note: The caller must call AmlDeleteIterator () to free the memory + allocated for the iterator. + + @param [in] Node Pointer to the node. + @param [in] IteratorMode Selected mode to traverse the tree. + @param [out] IteratorPtr Pointer holding the created iterator. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Could not allocate memory. +**/ +EFI_STATUS +EFIAPI +AmlInitializeIterator ( + IN AML_NODE_HEADER * Node, + IN EAML_ITERATOR_MODE IteratorMode, + OUT AML_TREE_ITERATOR ** IteratorPtr + ) +{ + AML_TREE_ITERATOR_INTERNAL * InternalIterator; + + if (!IS_AML_NODE_VALID (Node) || + (IteratorMode <= EAmlIteratorUnknown) || + (IteratorMode >= EAmlIteratorModeMax) || + (IteratorPtr == NULL)) { + ASSERT (0); + return EFI_INVALID_PARAMETER; + } + + *IteratorPtr = NULL; + InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)AllocateZeroPool ( + sizeof ( + AML_TREE_ITERATOR_INTERNAL + ) + ); + if (InternalIterator == NULL) { + ASSERT (0); + return EFI_OUT_OF_RESOURCES; + } + + InternalIterator->InitialNode = Node; + InternalIterator->CurrentNode = Node; + InternalIterator->Mode = IteratorMode; + InternalIterator->Iterator.GetNode = AmlIteratorGetNode; + + switch (InternalIterator->Mode) { + case EAmlIteratorLinear: + { + InternalIterator->Iterator.GetNext = AmlIteratorGetNextLinear; + InternalIterator->Iterator.GetPrevious = AmlIteratorGetPreviousLinear; + break; + } + case EAmlIteratorBranch: + { + InternalIterator->Iterator.GetNext = AmlIteratorGetNextBranch; + InternalIterator->Iterator.GetPrevious = AmlIteratorGetPreviousBranch; + break; + } + default: + { + ASSERT (0); + FreePool (InternalIterator); + return EFI_INVALID_PARAMETER; + } + } // switch + + *IteratorPtr = &InternalIterator->Iterator; + + return EFI_SUCCESS; +} + +/** Delete an iterator. + + Note: The caller must have first initialized the iterator with the + AmlInitializeIterator () function. + + @param [in] Iterator Pointer to an iterator. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +EFI_STATUS +EFIAPI +AmlDeleteIterator ( + IN AML_TREE_ITERATOR * Iterator + ) +{ + if (Iterator == NULL) { + ASSERT (0); + return EFI_INVALID_PARAMETER; + } + + FreePool (Iterator); + + return EFI_SUCCESS; +} diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h new file mode 100644 index 0000000000..d96eecab91 --- /dev/null +++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h @@ -0,0 +1,220 @@ +/** @file + AML Iterator. + + Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.
+ + SPDX-License-Identifier: BSD-2-Clause-Patent +**/ + +#ifndef AML_ITERATOR_H_ +#define AML_ITERATOR_H_ + +/* This header file does not include internal Node definition, + i.e. AML_ROOT_NODE, AML_OBJECT_NODE, etc. The node definitions + must be included by the caller file. The function prototypes must + only expose AML_NODE_HANDLE, AML_ROOT_NODE_HANDLE, etc. node + definitions. + This allows to keep the functions defined here both internal and + potentially external. If necessary, any function of this file can + be exposed externally. + The Api folder is internal to the AmlLib, but should only use these + functions. They provide a "safe" way to interact with the AmlLib. +*/ + +/** + @defgroup IteratorLibrary Iterator library + @ingroup NavigationApis + @{ + The iterator library allow to navigate in the AML tree using an iterator. + It is possible to initialize/delete an iterator. + + This iterator can progress in the tree by different orders: + - Linear progression: Iterate following the AML bytestream order + (depth first). + - Branch progression: Iterate following the AML bytestream order + (depth first), but stop iterating at the + end of the branch. + + An iterator has the following features: + - GetNode: Get the current node pointed by the iterator. + - GetNext: Move the current node of the iterator to the next + node, according to the iteration mode selected. + - GetPrevious: Move the current node of the iterator to the previous + node, according to the iteration mode selected. + @} +*/ + +/** + @defgroup IteratorApis Iterator APIs + @ingroup IteratorLibrary + @{ + Iterator APIs defines the action that can be done on an iterator: + - Initialization; + - Deletion; + - Getting the node currently pointed by the iterator; + - Moving to the next node; + - Moving to the previous node. + @} +*/ + +/** + @defgroup IteratorStructures Iterator structures + @ingroup IteratorLibrary + @{ + Iterator structures define the enum/define values and structures related + to iterators. + @} +*/ + +/** Iterator mode. + + Modes to choose how the iterator is progressing in the tree. + A + \-B <- Iterator initialized with this node. + | \-C + | | \-D + | \-E + | \-F + | \-G + \-H + \-I + + @ingroup IteratorStructures +*/ +typedef enum EAmlIteratorMode { + EAmlIteratorUnknown, ///< Unknown/Invalid AML IteratorMode + EAmlIteratorLinear, ///< Iterate following the AML bytestream order + /// (depth first). + /// The order followed by the iterator would be: + /// B, C, D, E, F, G, H, I, NULL. + EAmlIteratorBranch, ///< Iterate through the node of a branch. + /// The iteration follows the AML bytestream + /// order but within the branch B. + /// The order followed by the iterator would be: + /// B, C, D, E, F, G, NULL. + EAmlIteratorModeMax ///< Max enum. +} EAML_ITERATOR_MODE; + +/** Iterator. + + Allows to traverse the tree in different orders. + + @ingroup IteratorStructures +*/ +typedef struct AmlTreeIterator AML_TREE_ITERATOR; + +/** Function pointer to a get the current node of the iterator. + + @ingroup IteratorApis + + @param [in] Iterator Pointer to an iterator. + @param [out] OutNode Pointer holding the current node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +*/ +typedef +EFI_STATUS +(EFIAPI * EDKII_AML_TREE_ITERATOR_GET_NODE) ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HANDLE * OutNode + ); + +/** Function pointer to move the current node of the iterator to the + next node, according to the iteration mode selected. + + If NextNode is not NULL, return the next node. + + @ingroup IteratorApis + + @param [in] Iterator Pointer to an iterator. + @param [out] NextNode If not NULL, updated to the next node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +*/ +typedef +EFI_STATUS +(EFIAPI * EDKII_AML_TREE_ITERATOR_GET_NEXT) ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HANDLE * NextNode + ); + +/** Function pointer to move the current node of the iterator to the + previous node, according to the iteration mode selected. + + If PrevNode is not NULL, return the previous node. + + @ingroup IteratorApis + + @param [in] Iterator Pointer to an iterator. + @param [out] PrevNode If not NULL, updated to the previous node. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +*/ +typedef +EFI_STATUS +(EFIAPI * EDKII_AML_TREE_ITERATOR_GET_PREVIOUS) ( + IN AML_TREE_ITERATOR * Iterator, + OUT AML_NODE_HANDLE * PrevNode + ); + +/** Iterator structure to traverse the tree. + + @ingroup IteratorStructures +*/ +typedef struct AmlTreeIterator { + /// Get the current node of the iterator. + EDKII_AML_TREE_ITERATOR_GET_NODE GetNode; + + /// Update the current node of the iterator with the next node. + EDKII_AML_TREE_ITERATOR_GET_NEXT GetNext; + + /// Update the current node of the iterator with the previous node. + EDKII_AML_TREE_ITERATOR_GET_PREVIOUS GetPrevious; +} AML_TREE_ITERATOR; + + +/** Initialize an iterator. + + Note: The caller must call AmlDeleteIterator () to free the memory + allocated for the iterator. + + @ingroup IteratorApis + + @param [in] Node Pointer to the node. + @param [in] IteratorMode Selected mode to traverse the tree. + @param [out] IteratorPtr Pointer holding the created iterator. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. + @retval EFI_OUT_OF_RESOURCES Could not allocate memory. +**/ +EFI_STATUS +EFIAPI +AmlInitializeIterator ( + IN AML_NODE_HANDLE Node, + IN EAML_ITERATOR_MODE IteratorMode, + OUT AML_TREE_ITERATOR ** IteratorPtr + ); + +/** Delete an iterator. + + Note: The caller must have first initialized the iterator with the + AmlInitializeIterator () function. + + @ingroup IteratorApis + + @param [in] Iterator Pointer to an iterator. + + @retval EFI_SUCCESS The function completed successfully. + @retval EFI_INVALID_PARAMETER Invalid parameter. +**/ +EFI_STATUS +EFIAPI +AmlDeleteIterator ( + IN AML_TREE_ITERATOR * Iterator + ); + +#endif // AML_ITERATOR_H_ -- cgit v1.2.3