Re: [PATCH] UefiCpuPkg: Enhance CPU feature dependency check

[Laszlo Ersek <lersek@redhat.com>]

On 02/01/18 06:10, Ni, Ruiyu wrote:
> On 1/31/2018 5:44 PM, Laszlo Ersek wrote:
>> On 01/31/18 08:00, Song, BinX wrote:
>>> 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"));
>>
>> Hi, I skimmed this patch quickly -- I can tell that I can't really tell
>> what's going on. I don't know how the feature dependencies are defined
>> in the first place, and what the bug is.
>>
>> However, I do see that the above DEBUG macro invocation is incorrect.
>> The format string has one (1) %a conversion specification, but we pass
>> three (3) arguments.
>>
>> I think the last argument ("condition is invalid!\n") should actually be
>> part of the format string. And then, the "before"/"after" string has to
>> be printed somehow as well.
>>
>> Another superficial observation below:
>>
>>> +/**
>>> +  Check sorted CPU features' relationship, ASSERT invalid one.
>>> +
>>> +  @param[in]  FeatureList  The pointer to CPU feature list.
>>> +**/
>>> +VOID
>>> +CheckCpuFeaturesRelationShip (
>>
>> I don't think we should capitalize "Ship" in this identifier.
>>
>> Third comment: there are several ways to define "sorting", so I'm not
>> sure my question applies, but: can we replace the manual sorting with
>> SortLib?
> 
> Laszlo,
> I haven't checked the patch in details.
> But regarding to the SortLib suggestion, the feature entry is chained in
> linked list, while SortLib can only perform sorting in array.
> 
> Bin,
> Can we have a simpler fix to this issue?
> If my understanding is correct, the patch tries to fix the infinite loop
> in code.
> If that's true, can we just firstly calculate how many loops are
> expected before looping, then exit when the maximum loop is met?
> Upon that, when the sort hasn't been finished, a wrong dependency
> exists.

I wonder how the algorithm works right now; why is an infinite loop
possible in the first place?

I don't remember working with topological (= dependency) sorting in the
last 15 years :) , but I believe "non-termination" is not the expected
behavior for a dependency graph that has a cycle.

https://en.wikipedia.org/wiki/Topological_sorting

Anyway, if we'd like to find out whether a singly-linked list is looped,
a maximum list length can be enforced (like you say), or there's the
"trick" where one pointer advances 1 node and another pointer advances 2
nodes, and the faster pointer catches up with the slower one.

(Sorry I have no idea how the current algorithm works.)

Thanks
Laszlo