Re: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First

["Laszlo Ersek" <lersek@redhat.com>]

Hi,

On 12/08/20 16:01, Ray Ni wrote:
> CpuInfo.First stores whether the current thread belongs to the first
> package in the platform, first core in a package, first thread in a
> core.
> 
> But the time complexity of original algorithm to calculate the
> CpuInfo.First is O (n) * O (p) * O (c).
>   n: number of processors
>   p: number of packages
>   c: number of cores per package
> 
> The patch trades time with space by storing the first package, first
> core per package, first thread per core in an array.
> The time complexity becomes O (n).
> 
> Signed-off-by: Ray Ni <ray.ni@intel.com>
> Cc: Eric Dong <eric.dong@intel.com>
> Cc: Star Zeng <star.zeng@intel.com>
> Cc: Yun Lou <yun.lou@intel.com>
> Cc: Laszlo Ersek <lersek@redhat.com>
> ---
>  .../CpuFeaturesInitialize.c                   | 87 ++++++++-----------
>  1 file changed, 36 insertions(+), 51 deletions(-)

as RegisterCpuFeaturesLib is not used by OVMF, I'll defer this review to
others.

Thanks
Laszlo

> 
> diff --git a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c
> index d4a576385f..d21a1eaf38 100644
> --- a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c
> +++ b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c
> @@ -105,7 +105,10 @@ CpuInitDataInitialize (
>    EFI_CPU_PHYSICAL_LOCATION            *Location;
>    UINT32                               PackageIndex;
>    UINT32                               CoreIndex;
> -  UINT32                               First;
> +  UINTN                                Pages;
> +  UINT32                               FirstPackage;
> +  UINT32                               *FirstCore;
> +  UINT32                               *FirstThread;
>    ACPI_CPU_DATA                        *AcpiCpuData;
>    CPU_STATUS_INFORMATION               *CpuStatus;
>    UINT32                               *ThreadCountPerPackage;
> @@ -236,74 +239,56 @@ CpuInitDataInitialize (
>  
>    //
>    // Initialize CpuFeaturesData->InitOrder[].CpuInfo.First
> +  // Use AllocatePages () instead of AllocatePool () because pool cannot be freed in PEI phase but page can.
>    //
> +  Pages     = EFI_SIZE_TO_PAGES (CpuStatus->PackageCount * sizeof (UINT32) + CpuStatus->PackageCount * CpuStatus->MaxCoreCount * sizeof (UINT32));
> +  FirstCore = AllocatePages (Pages);
> +  ASSERT (FirstCore != NULL);
> +  FirstThread  = FirstCore + CpuStatus->PackageCount;
> +
> +  FirstPackage = MAX_UINT32;
> +  for (PackageIndex = 0; PackageIndex < CpuStatus->PackageCount; PackageIndex++) {
> +    FirstCore[PackageIndex] = MAX_UINT32;
> +    for (CoreIndex = 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex++) {
> +      FirstThread[PackageIndex * CpuStatus->MaxCoreCount + CoreIndex] = MAX_UINT32;
> +    }
> +  }
>  
> -  //
> -  // Set First.Package for each thread belonging to the first package.
> -  //
> -  First = MAX_UINT32;
>    for (ProcessorNumber = 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {
>      Location = &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;
> -    First = MIN (Location->Package, First);
> +
> +    FirstPackage                 = MIN (Location->Package, FirstPackage);
> +    FirstCore[Location->Package] = MIN (Location->Core, FirstCore[Location->Package]);
> +    FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->Core] = MIN (
> +      Location->Thread,
> +      FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->Core]
> +    );
>    }
> +
>    for (ProcessorNumber = 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {
>      Location = &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;
> -    if (Location->Package == First) {
> +
> +    if (Location->Package == FirstPackage) {
>        CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Package = 1;
>      }
> -  }
>  
> -  //
> -  // Set First.Die/Tile/Module for each thread assuming:
> -  //  single Die under each package, single Tile under each Die, single Module under each Tile
> -  //
> -  for (ProcessorNumber = 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {
> +    //
> +    // Set First.Die/Tile/Module for each thread assuming:
> +    //  single Die under each package, single Tile under each Die, single Module under each Tile
> +    //
>      CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Die = 1;
>      CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Tile = 1;
>      CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Module = 1;
> -  }
>  
> -  for (PackageIndex = 0; PackageIndex < CpuStatus->PackageCount; PackageIndex++) {
> -    //
> -    // Set First.Core for each thread in the first core of each package.
> -    //
> -    First = MAX_UINT32;
> -    for (ProcessorNumber = 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {
> -      Location = &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;
> -      if (Location->Package == PackageIndex) {
> -        First = MIN (Location->Core, First);
> -      }
> +    if (Location->Core == FirstCore[Location->Package]) {
> +      CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core = 1;
>      }
> -
> -    for (ProcessorNumber = 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {
> -      Location = &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;
> -      if (Location->Package == PackageIndex && Location->Core == First) {
> -        CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core = 1;
> -      }
> +    if (Location->Thread == FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->Core]) {
> +      CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thread = 1;
>      }
>    }
>  
> -  for (PackageIndex = 0; PackageIndex < CpuStatus->PackageCount; PackageIndex++) {
> -    for (CoreIndex = 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex++) {
> -      //
> -      // Set First.Thread for the first thread of each core.
> -      //
> -      First = MAX_UINT32;
> -      for (ProcessorNumber = 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {
> -        Location = &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;
> -        if (Location->Package == PackageIndex && Location->Core == CoreIndex) {
> -          First = MIN (Location->Thread, First);
> -        }
> -      }
> -
> -      for (ProcessorNumber = 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {
> -        Location = &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;
> -        if (Location->Package == PackageIndex && Location->Core == CoreIndex && Location->Thread == First) {
> -          CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thread = 1;
> -        }
> -      }
> -    }
> -  }
> +  FreePages (FirstCore, Pages);
>  }
>  
>  /**
>