[PATCH] UefiCpuPkg: Enhance CPU feature dependency check

["Song, BinX" <binx.song@intel.com>]

Current CPU feature dependency check will hang on when meet below or
similar case:
if (IsCpuFeatureSupported (CPU_FEATURE_AESNI)) {
  Status = RegisterCpuFeature (
             "AESNI",
             AesniGetConfigData,
             AesniSupport,
             AesniInitialize,
             CPU_FEATURE_AESNI,
             CPU_FEATURE_MWAIT | CPU_FEATURE_BEFORE,
             CPU_FEATURE_END
             );
  ASSERT_EFI_ERROR (Status);
}
if (IsCpuFeatureSupported (CPU_FEATURE_MWAIT)) {
  Status = RegisterCpuFeature (
             "MWAIT",
             NULL,
             MonitorMwaitSupport,
             MonitorMwaitInitialize,
             CPU_FEATURE_MWAIT,
             CPU_FEATURE_AESNI | CPU_FEATURE_BEFORE,
             CPU_FEATURE_END
             );
  ASSERT_EFI_ERROR (Status);
}

Solution is to separate current CPU feature dependency check into
sort and check two parts.

Sort function:
According to CPU feature's dependency, sort all CPU features.
Later dependency will override previous dependency if they are conflicted.

Check function:
Check sorted CPU features' relationship, ASSERT invalid relationship.

Cc: Eric Dong <eric.dong@intel.com>
Cc: Laszlo Ersek <lersek@redhat.com>
Contributed-under: TianoCore Contribution Agreement 1.1
Signed-off-by: Bell Song <binx.song@intel.com>
---
 .../RegisterCpuFeaturesLib/CpuFeaturesInitialize.c | 271 ++++++++++++++++++++-
 .../RegisterCpuFeaturesLib/RegisterCpuFeatures.h   |   7 +
 .../RegisterCpuFeaturesLib.c                       | 130 +---------
 3 files changed, 278 insertions(+), 130 deletions(-)

diff --git a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c
index 4d75c07..2fd0d5f 100644
--- a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c
+++ b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c
@@ -423,6 +423,271 @@ DumpRegisterTableOnProcessor (
 }
 
 /**
+  From FeatureBitMask, find the right feature entry in CPU feature list.
+
+  @param[in]  FeatureList    The pointer to CPU feature list.
+  @param[in]  CurrentFeature The pointer to current CPU feature.
+  @param[in]  BeforeFlag     TRUE: BeforeFeatureBitMask; FALSE: AfterFeatureBitMask.
+
+  @return  The pointer to right CPU feature entry.
+**/
+LIST_ENTRY *
+FindFeatureInList(
+  IN LIST_ENTRY              *CpuFeatureList,
+  IN CPU_FEATURES_ENTRY      *CurrentCpuFeature,
+  IN BOOLEAN                  BeforeFlag
+  )
+{
+  LIST_ENTRY                 *TempEntry;
+  CPU_FEATURES_ENTRY         *TempFeature;
+  UINT8                      *FeatureBitMask;
+
+  FeatureBitMask = BeforeFlag ? CurrentCpuFeature->BeforeFeatureBitMask : CurrentCpuFeature->AfterFeatureBitMask;
+  TempEntry = GetFirstNode (CpuFeatureList);
+  while (!IsNull (CpuFeatureList, TempEntry)) {
+    TempFeature = CPU_FEATURE_ENTRY_FROM_LINK (TempEntry);
+    if (IsBitMaskMatchCheck (FeatureBitMask, TempFeature->FeatureMask)){
+      return TempEntry;
+    }
+    TempEntry = TempEntry->ForwardLink;
+  }
+
+  DEBUG ((DEBUG_ERROR, "Error: Feature %a ", CurrentCpuFeature->FeatureName, BeforeFlag ? "before ":"after ", "condition is invalid!\n"));
+  DEBUG ((DEBUG_ERROR, "Error: Please check %a relationship!\n", CurrentCpuFeature->FeatureName));
+  ASSERT (FALSE);
+
+  return NULL;
+}
+
+/**
+  In CPU feature list, check if one entry is before another entry.
+
+  @param[in]  FeatureList  The pointer to CPU feature list.
+  @param[in]  OneEntry     The pointer to current CPU feature entry.
+  @param[in]  AnotherEntry The pointer to checked CPU feature entry.
+
+  @return TRUE             One entry is before another entry.
+  @return FALSE            One entry is NOT before another entry.
+**/
+BOOLEAN
+CheckEntryBeforeEntry(
+  IN LIST_ENTRY              *CpuFeatureList,
+  IN LIST_ENTRY              *OneEntry,
+  IN LIST_ENTRY              *AnotherEntry
+  )
+{
+  LIST_ENTRY                 *TempEntry;
+
+  TempEntry = OneEntry;
+  while (!IsNull (CpuFeatureList, TempEntry)) {
+    if (IsNull (AnotherEntry, TempEntry)) {
+      return TRUE;
+    }
+    TempEntry = TempEntry->ForwardLink;
+  }
+  return FALSE;
+}
+
+/**
+  Check sorted CPU features' relationship, ASSERT invalid one.
+
+  @param[in]  FeatureList  The pointer to CPU feature list.
+**/
+VOID
+CheckCpuFeaturesRelationShip (
+  IN LIST_ENTRY              *FeatureList
+  )
+{
+  LIST_ENTRY                 *CurrentEntry;
+  CPU_FEATURES_ENTRY         *CurrentFeature;
+  LIST_ENTRY                 *CheckEntry;
+  CPU_FEATURES_ENTRY         *CheckFeature;
+
+  //
+  // From head to tail, one by one to check all CPU features.
+  //
+  CurrentEntry = GetFirstNode (FeatureList);
+  while (!IsNull (FeatureList, CurrentEntry)) {
+    CurrentFeature = CPU_FEATURE_ENTRY_FROM_LINK (CurrentEntry);
+    ASSERT (CurrentFeature->Sorted);
+    if (CurrentFeature->BeforeAll) {
+      CheckEntry = CurrentEntry->BackLink;
+      while (!IsNull (FeatureList, CheckEntry)) {
+        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
+        //
+        // Check all features before this entry,
+        // ASSERT when feature has no BeforeAll flag.
+        //
+        if (!CheckFeature->BeforeAll){
+          DEBUG ((DEBUG_ERROR, "Error: Feature %a before all is invalid!\n", CurrentFeature->FeatureName));
+          DEBUG ((DEBUG_ERROR, "Error: Please check %a relationship!\n", CurrentFeature->FeatureName));
+          ASSERT (FALSE);
+        }
+        CheckEntry = CheckEntry->BackLink;
+      }
+    }
+
+    if (CurrentFeature->AfterAll) {
+      CheckEntry = CurrentEntry->ForwardLink;
+      while (!IsNull (FeatureList, CheckEntry)) {
+        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
+        //
+        // Check all features after this entry,
+        // ASSERT when feature has no AfterAll flag.
+        //
+        if(!CheckFeature->AfterAll){
+          DEBUG ((DEBUG_ERROR, "Error: Feature %a after all is invalid!\n", CurrentFeature->FeatureName));
+          DEBUG ((DEBUG_ERROR, "Error: Please check %a relationship!\n", CurrentFeature->FeatureName));
+          ASSERT (FALSE);
+        }
+        CheckEntry = CheckEntry->ForwardLink;
+      }
+    }
+
+    if (CurrentFeature->BeforeFeatureBitMask != NULL) {
+      //
+      // Get correct feature entry in feature list.
+      //
+      CheckEntry = FindFeatureInList (FeatureList, CurrentFeature, TRUE);
+      //
+      // ASSERT when current feature's relationship is invalid.
+      //
+      if (!CheckEntryBeforeEntry(FeatureList, CurrentEntry, CheckEntry)) {
+        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
+        DEBUG ((DEBUG_ERROR, "Error: Feature %a before %a is invalid!\n", CurrentFeature->FeatureName, CheckFeature->FeatureName));
+        DEBUG ((DEBUG_ERROR, "Error: Please check %a relationship!\n", CurrentFeature->FeatureName));
+        ASSERT (FALSE);
+      }
+    }
+
+    if (CurrentFeature->AfterFeatureBitMask != NULL) {
+      //
+      // Get correct feature entry in feature list.
+      //
+      CheckEntry = FindFeatureInList (FeatureList, CurrentFeature, FALSE);
+      //
+      // ASSERT when current feature's relationship is invalid.
+      //
+      if (CheckEntryBeforeEntry(FeatureList, CurrentEntry, CheckEntry)) {
+        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
+        DEBUG ((DEBUG_ERROR, "Error: Feature %a after %a is invalid!\n", CurrentFeature->FeatureName, CheckFeature->FeatureName));
+        DEBUG ((DEBUG_ERROR, "Error: Please check %a relationship!\n", CurrentFeature->FeatureName));
+        ASSERT (FALSE);
+      }
+    }
+    //
+    // Check next feature entry.
+    //
+    CurrentEntry = CurrentEntry->ForwardLink;
+  }
+}
+
+/**
+  According to CPU feature's dependency, sort all CPU features.
+  Later dependency will override previous dependency if they are conflicted.
+
+  @param[in]  FeatureList  The pointer to CPU feature list.
+**/
+VOID
+SortCpuFeatures (
+  IN LIST_ENTRY              *FeatureList
+  )
+{
+  LIST_ENTRY                 *CurrentEntry;
+  CPU_FEATURES_ENTRY         *CurrentFeature;
+  LIST_ENTRY                 *CheckEntry;
+  LIST_ENTRY                 *TempEntry;
+  BOOLEAN                    Swapped;
+
+  //
+  // Initinate all CPU features' Sorted = FALSE.
+  //
+  CurrentEntry = GetFirstNode (FeatureList);
+  while (!IsNull (FeatureList, CurrentEntry)) {
+    CurrentFeature = CPU_FEATURE_ENTRY_FROM_LINK (CurrentEntry);
+    CurrentFeature->Sorted = FALSE;
+    CurrentEntry = CurrentEntry->ForwardLink;
+  }
+
+  //
+  // From head to tail, one by one to sort all CPU features.
+  //
+  CurrentEntry = GetFirstNode (FeatureList);
+  while (!IsNull (FeatureList, CurrentEntry)) {
+    Swapped = FALSE;
+    CurrentFeature = CPU_FEATURE_ENTRY_FROM_LINK (CurrentEntry);
+    //
+    // Keep previous feature entry. When current feature entry is swapped,
+    // check current feature entry position again.
+    //
+    TempEntry = CurrentEntry->BackLink;
+    if (!CurrentFeature->Sorted) {
+      if (CurrentFeature->BeforeAll) {
+        RemoveEntryList (CurrentEntry);
+        InsertHeadList (FeatureList, CurrentEntry);
+        Swapped = TRUE;
+      }
+
+      if (CurrentFeature->AfterAll) {
+        RemoveEntryList (CurrentEntry);
+        InsertTailList (FeatureList, CurrentEntry);
+        Swapped = TRUE;
+      }
+
+      if (CurrentFeature->BeforeFeatureBitMask != NULL) {
+        //
+        // Get correct feature entry in feature list.
+        //
+        CheckEntry = FindFeatureInList (FeatureList, CurrentFeature, TRUE);
+        //
+        // Swap them if need
+        //
+        if (!CheckEntryBeforeEntry(FeatureList, CurrentEntry, CheckEntry)) {
+          RemoveEntryList (CheckEntry);
+          InsertHeadList (CurrentEntry, CheckEntry);
+          Swapped = TRUE;
+        }
+      }
+
+      if (CurrentFeature->AfterFeatureBitMask != NULL) {
+        //
+        // Get correct feature entry in feature list.
+        //
+        CheckEntry = FindFeatureInList (FeatureList, CurrentFeature, FALSE);
+        //
+        // Swap them if need.
+        //
+        if (CheckEntryBeforeEntry(FeatureList, CurrentEntry, CheckEntry)) {
+          RemoveEntryList (CheckEntry);
+          InsertTailList (CurrentEntry, CheckEntry);
+          Swapped = TRUE;
+        }
+      }
+      //
+      // This feature has been sorted.
+      //
+      CurrentFeature->Sorted = TRUE;
+      if (Swapped) {
+        //
+        // Check current entry position again.
+        //
+        CurrentEntry = TempEntry->ForwardLink;
+      } else {
+        //
+        // Check next feature entry.
+        //
+        CurrentEntry = CurrentEntry->ForwardLink;
+      }
+    } else {
+      //
+      // Check next feature entry.
+      //
+      CurrentEntry = CurrentEntry->ForwardLink;
+    }
+  }
+}
+
+/**
   Analysis register CPU features on each processor and save CPU setting in CPU register table.
 
   @param[in]  NumberOfCpus  Number of processor in system
@@ -466,7 +731,11 @@ AnalysisProcessorFeatures (
   //
   SetCapabilityPcd (CpuFeaturesData->CapabilityPcd);
   SetSettingPcd (CpuFeaturesData->SettingPcd);
-
+  //
+  // Sort and check CPU feature list
+  //
+  SortCpuFeatures(&CpuFeaturesData->FeatureList);
+  CheckCpuFeaturesRelationShip(&CpuFeaturesData->FeatureList);
   //
   // Dump the last CPU feature list
   //
diff --git a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeatures.h b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeatures.h
index 69b4121..550036b 100644
--- a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeatures.h
+++ b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeatures.h
@@ -49,6 +49,7 @@ typedef struct {
   VOID                         *ConfigData;
   BOOLEAN                      BeforeAll;
   BOOLEAN                      AfterAll;
+  BOOLEAN                      Sorted;
 } CPU_FEATURES_ENTRY;
 
 typedef struct {
@@ -190,4 +191,10 @@ DumpCpuFeature (
   IN CPU_FEATURES_ENTRY  *CpuFeature
   );
 
+BOOLEAN
+IsBitMaskMatchCheck (
+  IN UINT8        *FeatureMask,
+  IN UINT8        *DependentBitMask
+  );
+
 #endif
diff --git a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeaturesLib.c b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeaturesLib.c
index dd6a82b..a2dfcf7 100644
--- a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeaturesLib.c
+++ b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/RegisterCpuFeaturesLib.c
@@ -113,131 +113,6 @@ IsBitMaskMatchCheck (
 }
 
 /**
-  Checks and adjusts CPU features order per dependency relationship.
-
-  @param[in]  FeatureList        Pointer to CPU feature list
-**/
-VOID
-CheckCpuFeaturesDependency (
-  IN LIST_ENTRY              *FeatureList
-  )
-{
-  LIST_ENTRY                 *CurrentEntry;
-  CPU_FEATURES_ENTRY         *CpuFeature;
-  LIST_ENTRY                 *CheckEntry;
-  CPU_FEATURES_ENTRY         *CheckFeature;
-  BOOLEAN                    Swapped;
-  LIST_ENTRY                 *TempEntry;
-
-  CurrentEntry = GetFirstNode (FeatureList);
-  while (!IsNull (FeatureList, CurrentEntry)) {
-    Swapped = FALSE;
-    CpuFeature = CPU_FEATURE_ENTRY_FROM_LINK (CurrentEntry);
-    if (CpuFeature->BeforeAll) {
-      //
-      // Check all features dispatched before this entry
-      //
-      CheckEntry = GetFirstNode (FeatureList);
-      while (CheckEntry != CurrentEntry) {
-        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
-        if (!CheckFeature->BeforeAll) {
-          //
-          // If this feature has no BeforeAll flag and is dispatched before CpuFeature,
-          // insert currentEntry before Checked feature
-          //
-          RemoveEntryList (CurrentEntry);
-          InsertTailList (CheckEntry, CurrentEntry);
-          Swapped = TRUE;
-          break;
-        }
-        CheckEntry = CheckEntry->ForwardLink;
-      }
-      if (Swapped) {
-        continue;
-      }
-    }
-
-    if (CpuFeature->AfterAll) {
-      //
-      // Check all features dispatched after this entry
-      //
-      CheckEntry = GetNextNode (FeatureList, CurrentEntry);
-      while (!IsNull (FeatureList, CheckEntry)) {
-        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
-        if (!CheckFeature->AfterAll) {
-          //
-          // If this feature has no AfterAll flag and is dispatched after CpuFeature,
-          // insert currentEntry after Checked feature
-          //
-          TempEntry = GetNextNode (FeatureList, CurrentEntry);
-          RemoveEntryList (CurrentEntry);
-          InsertHeadList (CheckEntry, CurrentEntry);
-          CurrentEntry = TempEntry;
-          Swapped = TRUE;
-          break;
-        }
-        CheckEntry = CheckEntry->ForwardLink;
-      }
-      if (Swapped) {
-        continue;
-      }
-    }
-
-    if (CpuFeature->BeforeFeatureBitMask != NULL) {
-      //
-      // Check all features dispatched before this entry
-      //
-      CheckEntry = GetFirstNode (FeatureList);
-      while (CheckEntry != CurrentEntry) {
-        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
-        if (IsBitMaskMatchCheck (CheckFeature->FeatureMask, CpuFeature->BeforeFeatureBitMask)) {
-          //
-          // If there is dependency, swap them
-          //
-          RemoveEntryList (CurrentEntry);
-          InsertTailList (CheckEntry, CurrentEntry);
-          Swapped = TRUE;
-          break;
-        }
-        CheckEntry = CheckEntry->ForwardLink;
-      }
-      if (Swapped) {
-        continue;
-      }
-    }
-
-    if (CpuFeature->AfterFeatureBitMask != NULL) {
-      //
-      // Check all features dispatched after this entry
-      //
-      CheckEntry = GetNextNode (FeatureList, CurrentEntry);
-      while (!IsNull (FeatureList, CheckEntry)) {
-        CheckFeature = CPU_FEATURE_ENTRY_FROM_LINK (CheckEntry);
-        if (IsBitMaskMatchCheck (CheckFeature->FeatureMask, CpuFeature->AfterFeatureBitMask)) {
-          //
-          // If there is dependency, swap them
-          //
-          TempEntry = GetNextNode (FeatureList, CurrentEntry);
-          RemoveEntryList (CurrentEntry);
-          InsertHeadList (CheckEntry, CurrentEntry);
-          CurrentEntry = TempEntry;
-          Swapped = TRUE;
-          break;
-        }
-        CheckEntry = CheckEntry->ForwardLink;
-      }
-      if (Swapped) {
-        continue;
-      }
-    }
-    //
-    // No swap happened, check the next feature
-    //
-    CurrentEntry = CurrentEntry->ForwardLink;
-  }
-}
-
-/**
   Worker function to register CPU Feature.
 
   @param[in]  CpuFeature            Pointer to CPU feature entry
@@ -334,10 +209,7 @@ RegisterCpuFeatureWorker (
     FreePool (CpuFeature->FeatureMask);
     FreePool (CpuFeature);
   }
-  //
-  // Verify CPU features dependency can change CPU feature order
-  //
-  CheckCpuFeaturesDependency (&CpuFeaturesData->FeatureList);
+
   return RETURN_SUCCESS;
 }
 
-- 
2.10.2.windows.1