[edk2-devel] [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First
Laszlo Ersek
lersek at redhat.com
Thu Dec 10 08:25:38 UTC 2020
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 at intel.com>
> Cc: Eric Dong <eric.dong at intel.com>
> Cc: Star Zeng <star.zeng at intel.com>
> Cc: Yun Lou <yun.lou at intel.com>
> Cc: Laszlo Ersek <lersek at 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);
> }
>
> /**
>
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#68639): https://edk2.groups.io/g/devel/message/68639
Mute This Topic: https://groups.io/mt/78804897/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-
More information about the edk2-devel-archive
mailing list