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

["Zeng, Star" <star.zeng@intel.com>]

Only one minor comment inline, other parts look good to me.

> -----Original Message-----
> From: Ni, Ray <ray.ni@intel.com>
> Sent: Tuesday, December 8, 2020 11:02 PM
> To: devel@edk2.groups.io
> Cc: Dong, Eric <eric.dong@intel.com>; Zeng, Star <star.zeng@intel.com>;
> Lou, Yun <yun.lou@intel.com>; Laszlo Ersek <lersek@redhat.com>
> Subject: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc
> CpuInfo.First
> 
> 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(-)
> 
> 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;
> 
> +    }
> 
> +  }

Could this code block be replaced by a SetMem32(xxx, xxx, MAX_UINT32) call?


Thanks,
Star

> 
> 
> 
> -  //
> 
> -  // 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);
> 
>  }
> 
> 
> 
>  /**
> 
> --
> 2.27.0.windows.1