From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by mx.groups.io with SMTP id smtpd.web09.9685.1607439806416376466 for ; Tue, 08 Dec 2020 07:03:26 -0800 Authentication-Results: mx.groups.io; dkim=missing; spf=pass (domain: intel.com, ip: 192.55.52.115, mailfrom: ray.ni@intel.com) IronPort-SDR: fDPzUZG1KZEYl4kvQBH70flUQttNX7j1vEaMCJIURFWUNuI9UadkHDAjgHKkSKJoxDDVPtfqOi QTOzW9APOurw== X-IronPort-AV: E=McAfee;i="6000,8403,9828"; a="173138723" X-IronPort-AV: E=Sophos;i="5.78,402,1599548400"; d="scan'208";a="173138723" Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 Dec 2020 07:03:15 -0800 IronPort-SDR: tAsFvegOthcqK5Px2KBGsbyxMEQbKUw4a43yvcRXgGH/gclNX8YmIxWYhz75p2ddnnGzGbaAc1 y9LQb2UVrtDw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.78,402,1599548400"; d="scan'208";a="407647094" Received: from ray-dev.ccr.corp.intel.com ([10.239.158.87]) by orsmga001.jf.intel.com with ESMTP; 08 Dec 2020 07:03:13 -0800 From: "Ni, Ray" To: devel@edk2.groups.io Cc: Eric Dong , Star Zeng , Yun Lou , Laszlo Ersek Subject: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First Date: Tue, 8 Dec 2020 23:01:42 +0800 Message-Id: <20201208150142.1894-1-ray.ni@intel.com> X-Mailer: git-send-email 2.27.0.windows.1 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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 Cc: Eric Dong Cc: Star Zeng Cc: Yun Lou Cc: Laszlo Ersek --- .../CpuFeaturesInitialize.c | 87 ++++++++----------- 1 file changed, 36 insertions(+), 51 deletions(-) diff --git a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitializ= e.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;=0D UINT32 PackageIndex;=0D UINT32 CoreIndex;=0D - UINT32 First;=0D + UINTN Pages;=0D + UINT32 FirstPackage;=0D + UINT32 *FirstCore;=0D + UINT32 *FirstThread;=0D ACPI_CPU_DATA *AcpiCpuData;=0D CPU_STATUS_INFORMATION *CpuStatus;=0D UINT32 *ThreadCountPerPackage;=0D @@ -236,74 +239,56 @@ CpuInitDataInitialize ( =0D //=0D // Initialize CpuFeaturesData->InitOrder[].CpuInfo.First=0D + // Use AllocatePages () instead of AllocatePool () because pool cannot b= e freed in PEI phase but page can.=0D //=0D + Pages =3D EFI_SIZE_TO_PAGES (CpuStatus->PackageCount * sizeof (UINT3= 2) + CpuStatus->PackageCount * CpuStatus->MaxCoreCount * sizeof (UINT32));= =0D + FirstCore =3D AllocatePages (Pages);=0D + ASSERT (FirstCore !=3D NULL);=0D + FirstThread =3D FirstCore + CpuStatus->PackageCount;=0D +=0D + FirstPackage =3D MAX_UINT32;=0D + for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; Package= Index++) {=0D + FirstCore[PackageIndex] =3D MAX_UINT32;=0D + for (CoreIndex =3D 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex++= ) {=0D + FirstThread[PackageIndex * CpuStatus->MaxCoreCount + CoreIndex] =3D = MAX_UINT32;=0D + }=0D + }=0D =0D - //=0D - // Set First.Package for each thread belonging to the first package.=0D - //=0D - First =3D MAX_UINT32;=0D for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNum= ber++) {=0D Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Proc= essorInfo.Location;=0D - First =3D MIN (Location->Package, First);=0D +=0D + FirstPackage =3D MIN (Location->Package, FirstPackage)= ;=0D + FirstCore[Location->Package] =3D MIN (Location->Core, FirstCore[Locati= on->Package]);=0D + FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->Co= re] =3D MIN (=0D + Location->Thread,=0D + FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->= Core]=0D + );=0D }=0D +=0D for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNum= ber++) {=0D Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Proc= essorInfo.Location;=0D - if (Location->Package =3D=3D First) {=0D +=0D + if (Location->Package =3D=3D FirstPackage) {=0D CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Package = =3D 1;=0D }=0D - }=0D =0D - //=0D - // Set First.Die/Tile/Module for each thread assuming:=0D - // single Die under each package, single Tile under each Die, single Mo= dule under each Tile=0D - //=0D - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNum= ber++) {=0D + //=0D + // Set First.Die/Tile/Module for each thread assuming:=0D + // single Die under each package, single Tile under each Die, single = Module under each Tile=0D + //=0D CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Die =3D 1;=0D CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Tile =3D 1;= =0D CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Module =3D 1= ;=0D - }=0D =0D - for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; Package= Index++) {=0D - //=0D - // Set First.Core for each thread in the first core of each package.=0D - //=0D - First =3D MAX_UINT32;=0D - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorN= umber++) {=0D - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Pr= ocessorInfo.Location;=0D - if (Location->Package =3D=3D PackageIndex) {=0D - First =3D MIN (Location->Core, First);=0D - }=0D + if (Location->Core =3D=3D FirstCore[Location->Package]) {=0D + CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core =3D 1= ;=0D }=0D -=0D - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorN= umber++) {=0D - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Pr= ocessorInfo.Location;=0D - if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D F= irst) {=0D - CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core =3D= 1;=0D - }=0D + if (Location->Thread =3D=3D FirstThread[Location->Package * CpuStatus-= >MaxCoreCount + Location->Core]) {=0D + CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thread =3D= 1;=0D }=0D }=0D =0D - for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; Package= Index++) {=0D - for (CoreIndex =3D 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex++= ) {=0D - //=0D - // Set First.Thread for the first thread of each core.=0D - //=0D - First =3D MAX_UINT32;=0D - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; Processo= rNumber++) {=0D - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.= ProcessorInfo.Location;=0D - if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D= CoreIndex) {=0D - First =3D MIN (Location->Thread, First);=0D - }=0D - }=0D -=0D - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; Processo= rNumber++) {=0D - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.= ProcessorInfo.Location;=0D - if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D= CoreIndex && Location->Thread =3D=3D First) {=0D - CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thread= =3D 1;=0D - }=0D - }=0D - }=0D - }=0D + FreePages (FirstCore, Pages);=0D }=0D =0D /**=0D --=20 2.27.0.windows.1