[PATCH v1 0/3] Detect duplicate field values in ACPI tables

[PATCH v1 0/3] Detect duplicate field values in ACPI tables

[Krzysztof Koch]

This patch set introduces generic code for finding duplicate elements
in an array and uses it to validate two ACPI tables: MADT and GTDT.

This change is motivated by the need for certain ACPI table field
to have unique values across the entire table.

Changes can be seen at: https://github.com/KrzysztofKoch1/edk2/tree/479_find_duplicate_ids_v1


Krzysztof Koch (3):
  DynamicTablesPkg: Add code for finding duplicate values in arrays
  DynamicTablesPkg: Test for duplicate UIDs in MADT generator
  DynamicTablesPkg: Test for duplicate GT Block frame numbers

 DynamicTablesPkg/Include/Library/TableHelperLib.h                | 48 +++++++++++
 DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c | 66 +++++++++++++-
 DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c | 90 ++++++++++++++++++--
 DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c     | 64 ++++++++++++++
 4 files changed, 259 insertions(+), 9 deletions(-)

--
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'

[PATCH v1 1/3] DynamicTablesPkg: Add code for finding duplicate values in arrays

[Krzysztof Koch]

Added generic function for detecting duplicate values in an array.

Also defined a function prototype to test if two objects are equal.
The prototype is used as an argument to the 'FindDuplicateValues'
function.

Signed-off-by: Krzysztof Koch <krzysztof.koch@arm.com>
---
Notes:
    v1:
    - Add generic code for duplicate detection [Krzysztof]

 DynamicTablesPkg/Include/Library/TableHelperLib.h            | 48 +++++++++++++++
 DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c | 64 ++++++++++++++++++++
 2 files changed, 112 insertions(+)

diff --git a/DynamicTablesPkg/Include/Library/TableHelperLib.h b/DynamicTablesPkg/Include/Library/TableHelperLib.h
index 9c5b3835413f8768ef81ababa932c9f9be7ced82..e4a8dfa046bd97d89f0297ccad521f317bed5c36 100644
--- a/DynamicTablesPkg/Include/Library/TableHelperLib.h
+++ b/DynamicTablesPkg/Include/Library/TableHelperLib.h
@@ -4,6 +4,9 @@
 
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
+  @par Glossary:
+    - PFN   - Pointer to a Function
+
 **/
 
 #ifndef TABLE_HELPER_LIB_H_
@@ -59,4 +62,49 @@ AddAcpiHeader (
   IN      CONST UINT32                                        Length
   );
 
+/**
+  Function prototype for testing if two arbitrary objects are equal.
+
+  @param [in] Object1           Pointer to the first object to compare.
+  @param [in] Object2           Pointer to the second object to compare.
+  @param [in] Index1            Index of Object1. This value is optional and
+                                can be ignored by the specified implementation.
+  @param [in] Index2            Index of Object2. This value is optional and
+                                can be ignored by the specified implementation.
+
+  @retval TRUE                  Object1 and Object2 are equal.
+  @retval FALSE                 Object1 and Object2 are NOT equal.
+**/
+typedef
+BOOLEAN
+(EFIAPI *PFN_IS_EQUAL)(
+  IN CONST  VOID            * Object1,
+  IN CONST  VOID            * Object2,
+  IN        UINTN             Index1 OPTIONAL,
+  IN        UINTN             Index2 OPTIONAL
+  );
+
+/**
+  Test and report if a duplicate entry exists in the given array of comparable
+  elements.
+
+  @param [in] Array                 Array of elements to test for duplicates.
+  @param [in] Count                 Number of elements in Array.
+  @param [in] ElementSize           Size of an element in bytes
+  @param [in] EqualTestFunction     The function to call to check if any two
+                                    elements are equal.
+
+  @retval TRUE                      A duplicate element was found or one of
+                                    the input arguments is invalid.
+  @retval FALSE                     Every element in Array is unique.
+**/
+BOOLEAN
+EFIAPI
+FindDuplicateValue (
+  IN  CONST VOID          * Array,
+  IN  CONST UINTN           Count,
+  IN  CONST UINTN           ElementSize,
+  IN        PFN_IS_EQUAL    EqualTestFunction
+  );
+
 #endif // TABLE_HELPER_LIB_H_
diff --git a/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c b/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c
index 3938302b6d770c5bed2bc6c55a51c96ea8316dff..fc6cf3b088da1f7ad89dd4356b414bede9e80575 100644
--- a/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c
+++ b/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c
@@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
 // Module specific include files.
 #include <AcpiTableGenerator.h>
 #include <ConfigurationManagerObject.h>
+#include <Library/TableHelperLib.h>
 #include <Protocol/ConfigurationManagerProtocol.h>
 
 /** The GetCgfMgrInfo function gets the CM_STD_OBJ_CONFIGURATION_MANAGER_INFO
@@ -180,3 +181,66 @@ AddAcpiHeader (
 error_handler:
   return Status;
 }
+
+/**
+  Test and report if a duplicate entry exists in the given array of comparable
+  elements.
+
+  @param [in] Array                 Array of elements to test for duplicates.
+  @param [in] Count                 Number of elements in Array.
+  @param [in] ElementSize           Size of an element in bytes
+  @param [in] EqualTestFunction     The function to call to check if any two
+                                    elements are equal.
+
+  @retval TRUE                      A duplicate element was found or one of
+                                    the input arguments is invalid.
+  @retval FALSE                     Every element in Array is unique.
+**/
+BOOLEAN
+EFIAPI
+FindDuplicateValue (
+  IN  CONST VOID          * Array,
+  IN  CONST UINTN           Count,
+  IN  CONST UINTN           ElementSize,
+  IN        PFN_IS_EQUAL    EqualTestFunction
+  )
+{
+  UINTN         Index1;
+  UINTN         Index2;
+  UINT8       * Element1;
+  UINT8       * Element2;
+
+  if (Array == NULL) {
+    DEBUG ((DEBUG_ERROR, "ERROR: FindDuplicateValues: Array is NULL.\n"));
+    return TRUE;
+  }
+
+  if (ElementSize == 0) {
+    DEBUG ((DEBUG_ERROR, "ERROR: FindDuplicateValues: ElementSize is 0.\n"));
+    return TRUE;
+  }
+
+  if (EqualTestFunction == NULL) {
+    DEBUG ((
+      DEBUG_ERROR,
+      "ERROR: FindDuplicateValues: EqualTestFunction is NULL.\n"
+      ));
+    return TRUE;
+  }
+
+  if (Count < 2) {
+    return FALSE;
+  }
+
+  for (Index1 = 0; Index1 < Count - 1; Index1++) {
+    for (Index2 = Index1 + 1; Index2 < Count; Index2++) {
+      Element1 = (UINT8*)Array + (Index1 * ElementSize);
+      Element2 = (UINT8*)Array + (Index2 * ElementSize);
+
+      if (EqualTestFunction (Element1, Element2, Index1, Index2)) {
+        return TRUE;
+      }
+    }
+  }
+  return FALSE;
+}
--
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'

[PATCH v1 2/3] DynamicTablesPkg: Test for duplicate UIDs in MADT generator

[Krzysztof Koch]

Check for duplicate ACPI Processor UIDs when populating the GIC CPU
(GICC) Interface structures inside the MADT table generator.

Signed-off-by: Krzysztof Koch <krzysztof.koch@arm.com>
---

Notes:
    v1:
    - Detect duplicate ACPI Processor UIDs in GICCs [Krzysztof]

 DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c | 90 ++++++++++++++++++--
 1 file changed, 83 insertions(+), 7 deletions(-)

diff --git a/DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c b/DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c
index ab9734fb31480f1b653227d1d56abf60bb04f98a..613bf665d9cecc6495f5ac84c2515ea89f476194 100644
--- a/DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c
+++ b/DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c
@@ -140,28 +140,96 @@ AddGICC (
   Gicc->Reserved2[2] = EFI_ACPI_RESERVED_BYTE;
 }
 
+/**
+  Function to test if two GIC CPU Interface information structures have the
+  same ACPI Processor UID.
+
+  @param [in]  GicCInfo1          Pointer to the first GICC info structure.
+  @param [in]  GicCInfo2          Pointer to the second GICC info structure.
+  @param [in]  Index1             Index of GicCInfo1 in the shared list of GIC
+                                  CPU Interface Info structures.
+  @param [in]  Index2             Index of GicCInfo2 in the shared list of GIC
+                                  CPU Interface Info structures.
+
+  @retval TRUE                    GicCInfo1 and GicCInfo2 have the same UID.
+  @retval FALSE                   GicCInfo1 and GicCInfo2 have different UIDs.
+**/
+BOOLEAN
+EFIAPI
+IsAcpiUidEqual (
+  IN  CONST VOID          * GicCInfo1,
+  IN  CONST VOID          * GicCInfo2,
+  IN        UINTN           Index1,
+  IN        UINTN           Index2
+  )
+{
+  UINT32      Uid1;
+  UINT32      Uid2;
+
+  ASSERT ((GicCInfo1 != NULL) && (GicCInfo2 != NULL));
+
+  Uid1 = ((CM_ARM_GICC_INFO*)GicCInfo1)->AcpiProcessorUid;
+  Uid2 = ((CM_ARM_GICC_INFO*)GicCInfo2)->AcpiProcessorUid;
+
+  if (Uid1 == Uid2) {
+    DEBUG ((
+      DEBUG_ERROR,
+      "ERROR: MADT: GICC Info Structures %d and %d have the same ACPI " \
+      "Processor UID: 0x%x.\n",
+      Index1,
+      Index2,
+      Uid1
+      ));
+    return TRUE;
+  }
+
+  return FALSE;
+}
+
 /** Add the GIC CPU Interface Information to the MADT Table.
 
-  @param [in]  Gicc      Pointer to GIC CPU Interface
-                         structure list.
-  @param [in]  GicCInfo  Pointer to the GIC CPU
-                         Information list.
-  @param [in]  GicCCount Count of GIC CPU Interfaces.
+  This function also checks for duplicate ACPI Processor UIDs.
+
+  @param [in]  Gicc                 Pointer to GIC CPU Interface structure list.
+  @param [in]  GicCInfo             Pointer to the GIC CPU Information list.
+  @param [in]  GicCCount            Count of GIC CPU Interfaces.
+
+  @retval EFI_SUCCESS               GIC CPU Interface Information was added
+                                    successfully.
+  @retval EFI_INVALID_PARAMETER     One or more invalid GIC CPU Info values were
+                                    provided and the generator failed to add the
+                                    information to the table.
 **/
 STATIC
-VOID
+EFI_STATUS
 AddGICCList (
   IN  EFI_ACPI_6_2_GIC_STRUCTURE  * Gicc,
   IN  CONST CM_ARM_GICC_INFO      * GicCInfo,
   IN        UINT32                  GicCCount
   )
 {
+  BOOLEAN   IsAcpiProcUidDuplicated;
+
   ASSERT (Gicc != NULL);
   ASSERT (GicCInfo != NULL);
 
+  IsAcpiProcUidDuplicated = FindDuplicateValue (
+                              GicCInfo,
+                              GicCCount,
+                              sizeof (CM_ARM_GICC_INFO),
+                              IsAcpiUidEqual
+                              );
+  // Duplicate ACPI Processor UID was found so the GICC info provided
+  // is invalid
+  if (IsAcpiProcUidDuplicated) {
+    return EFI_INVALID_PARAMETER;
+  }
+
   while (GicCCount-- != 0) {
     AddGICC (Gicc++, GicCInfo++);
   }
+
+  return EFI_SUCCESS;
 }
 
 /** Update the GIC Distributor Information in the MADT Table.
@@ -577,11 +645,19 @@ BuildMadtTable (
     goto error_handler;
   }
 
-  AddGICCList (
+  Status = AddGICCList (
     (EFI_ACPI_6_2_GIC_STRUCTURE*)((UINT8*)Madt + GicCOffset),
     GicCInfo,
     GicCCount
     );
+  if (EFI_ERROR (Status)) {
+    DEBUG ((
+      DEBUG_ERROR,
+      "ERROR: MADT: Failed to add GICC structures. Status = %r\n",
+      Status
+      ));
+    goto error_handler;
+  }
 
   AddGICD (
     (EFI_ACPI_6_2_GIC_DISTRIBUTOR_STRUCTURE*)((UINT8*)Madt + GicDOffset),
--
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'

[PATCH v1 3/3] DynamicTablesPkg: Test for duplicate GT Block frame numbers

[Krzysztof Koch]

Check for duplicate frame numbers when populating the GT Block Timer
Frames inside the GTDT table generator.

Signed-off-by: Krzysztof Koch <krzysztof.koch@arm.com>
---

Notes:
    v1:
    - Detect duplicate GT Frame Numbers in GTDT [Krzysztof]

 DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c | 66 +++++++++++++++++++-
 1 file changed, 64 insertions(+), 2 deletions(-)

diff --git a/DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c b/DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c
index 8d9ddcf9244b9f8b795edf7a53dd8a071bb121bc..d1ac9110cc5c8df8506b6db09cc362fdb0df8d76 100644
--- a/DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c
+++ b/DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c
@@ -179,6 +179,55 @@ AddGenericWatchdogList (
   } // for
 }
 
+/**
+  Function to test if two Generic Timer Block Frame Info structures have the
+  same frame number.
+
+  @param [in]  Frame1           Pointer to the first GT Block Frame Info
+                                structure.
+  @param [in]  Frame2           Pointer to the second GT Block Frame Info
+                                structure.
+  @param [in]  Index1           Index of Frame1 in the shared GT Block Frame
+                                Information List.
+  @param [in]  Index2           Index of Frame2 in the shared GT Block Frame
+                                Information List.
+
+  @retval TRUE                  Frame1 and Frame2 have the same frame number.
+  @return FALSE                 Frame1 and Frame2 have different frame numbers.
+
+**/
+BOOLEAN
+EFIAPI
+IsGtFrameNumberEqual (
+  IN  CONST VOID          * Frame1,
+  IN  CONST VOID          * Frame2,
+  IN        UINTN           Index1,
+  IN        UINTN           Index2
+  )
+{
+  UINT8     FrameNumber1;
+  UINT8     FrameNumber2;
+
+  ASSERT ((Frame1 != NULL) && (Frame2 != NULL));
+
+  FrameNumber1 = ((CM_ARM_GTBLOCK_TIMER_FRAME_INFO*)Frame1)->FrameNumber;
+  FrameNumber2 = ((CM_ARM_GTBLOCK_TIMER_FRAME_INFO*)Frame2)->FrameNumber;
+
+  if (FrameNumber1 == FrameNumber2) {
+    DEBUG ((
+      DEBUG_ERROR,
+      "ERROR: GTDT: GT Block Frame Info Structures %d and %d have the same " \
+      "frame number: 0x%x.\n",
+      Index1,
+      Index2,
+      FrameNumber1
+      ));
+    return TRUE;
+  }
+
+  return FALSE;
+}
+
 /** Update the GT Block Timer Frame lists in the GTDT Table.
 
   @param [in]  GtBlockFrame           Pointer to the GT Block Frames
@@ -187,8 +236,8 @@ AddGenericWatchdogList (
                                       Information List.
   @param [in]  GTBlockFrameCount      Number of GT Block Frames.
 
-  @retval EFI_SUCCESS           Table generated successfully.
-  @retval EFI_INVALID_PARAMETER A parameter is invalid.
+  @retval EFI_SUCCESS                 Table generated successfully.
+  @retval EFI_INVALID_PARAMETER       A parameter is invalid.
 **/
 STATIC
 EFI_STATUS
@@ -198,6 +247,8 @@ AddGTBlockTimerFrames (
   IN       UINT32                                             GTBlockFrameCount
 )
 {
+  BOOLEAN    IsFrameNumberDuplicated;
+
   ASSERT (GtBlockFrame != NULL);
   ASSERT (GTBlockTimerFrameList != NULL);
 
@@ -211,6 +262,17 @@ AddGTBlockTimerFrames (
     return EFI_INVALID_PARAMETER;
   }
 
+  IsFrameNumberDuplicated = FindDuplicateValue (
+                              GTBlockTimerFrameList,
+                              GTBlockFrameCount,
+                              sizeof (CM_ARM_GTBLOCK_TIMER_FRAME_INFO),
+                              IsGtFrameNumberEqual
+                              );
+  // Duplicate entry was found so timer frame numbers provided are invalid
+  if (IsFrameNumberDuplicated) {
+    return EFI_INVALID_PARAMETER;
+  }
+
   while (GTBlockFrameCount-- != 0) {
     DEBUG ((
       DEBUG_INFO,
--
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'

Re: [edk2-devel] [PATCH v1 0/3] Detect duplicate field values in ACPI tables

[Alexei.Fedorov]

[-- Attachment #1: Type: text/plain, Size: 79 bytes --]

Reviewed-by: Alexei Fedorov Alexei.Fedorov@arm.com ( Alexei.Fedorov@arm.com )

[-- Attachment #2: Type: text/html, Size: 140 bytes --]

Re: [PATCH v1 0/3] Detect duplicate field values in ACPI tables

[Sami Mujawar]

Reviewed-by: Sami Mujawar <sami.mujawar@arm.com>

-----Original Message-----
From: Krzysztof Koch <krzysztof.koch@arm.com> 
Sent: 16 May 2019 11:12 AM
To: devel@edk2.groups.io
Cc: leif.lindholm@linaro.org; Sami Mujawar <Sami.Mujawar@arm.com>; Alexei Fedorov <Alexei.Fedorov@arm.com>; Matteo Carlini <Matteo.Carlini@arm.com>; Stephanie Hughes-Fitt <Stephanie.Hughes-Fitt@arm.com>; nd <nd@arm.com>
Subject: [PATCH v1 0/3] Detect duplicate field values in ACPI tables

This patch set introduces generic code for finding duplicate elements in an array and uses it to validate two ACPI tables: MADT and GTDT.

This change is motivated by the need for certain ACPI table field to have unique values across the entire table.

Changes can be seen at: https://github.com/KrzysztofKoch1/edk2/tree/479_find_duplicate_ids_v1


Krzysztof Koch (3):
  DynamicTablesPkg: Add code for finding duplicate values in arrays
  DynamicTablesPkg: Test for duplicate UIDs in MADT generator
  DynamicTablesPkg: Test for duplicate GT Block frame numbers

 DynamicTablesPkg/Include/Library/TableHelperLib.h                | 48 +++++++++++
 DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c | 66 +++++++++++++-  DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c | 90 ++++++++++++++++++--
 DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c     | 64 ++++++++++++++
 4 files changed, 259 insertions(+), 9 deletions(-)

--
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'

Re: [PATCH v1 0/3] Detect duplicate field values in ACPI tables

[Sami Mujawar]

Pushed as 75bf10a68914..ccc97f6df415

-----Original Message-----
From: Sami Mujawar 
Sent: 10 June 2019 08:46 PM
To: devel@edk2.groups.io
Cc: nd <nd@arm.com>
Subject: RE: [PATCH v1 0/3] Detect duplicate field values in ACPI tables

Reviewed-by: Sami Mujawar <sami.mujawar@arm.com>

-----Original Message-----
From: Krzysztof Koch <krzysztof.koch@arm.com> 
Sent: 16 May 2019 11:12 AM
To: devel@edk2.groups.io
Cc: leif.lindholm@linaro.org; Sami Mujawar <Sami.Mujawar@arm.com>; Alexei Fedorov <Alexei.Fedorov@arm.com>; Matteo Carlini <Matteo.Carlini@arm.com>; Stephanie Hughes-Fitt <Stephanie.Hughes-Fitt@arm.com>; nd <nd@arm.com>
Subject: [PATCH v1 0/3] Detect duplicate field values in ACPI tables

This patch set introduces generic code for finding duplicate elements in an array and uses it to validate two ACPI tables: MADT and GTDT.

This change is motivated by the need for certain ACPI table field to have unique values across the entire table.

Changes can be seen at: https://github.com/KrzysztofKoch1/edk2/tree/479_find_duplicate_ids_v1


Krzysztof Koch (3):
  DynamicTablesPkg: Add code for finding duplicate values in arrays
  DynamicTablesPkg: Test for duplicate UIDs in MADT generator
  DynamicTablesPkg: Test for duplicate GT Block frame numbers

 DynamicTablesPkg/Include/Library/TableHelperLib.h                | 48 +++++++++++
 DynamicTablesPkg/Library/Acpi/Arm/AcpiGtdtLibArm/GtdtGenerator.c | 66 +++++++++++++-  DynamicTablesPkg/Library/Acpi/Arm/AcpiMadtLibArm/MadtGenerator.c | 90 ++++++++++++++++++--
 DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c     | 64 ++++++++++++++
 4 files changed, 259 insertions(+), 9 deletions(-)

--
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'