From: "Ni, Ray" <ray.ni@intel.com>
To: devel@edk2.groups.io
Cc: Eric Dong <eric.dong@intel.com>, Star Zeng <star.zeng@intel.com>,
Yun Lou <yun.lou@intel.com>, Laszlo Ersek <lersek@redhat.com>
Subject: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First
Date: Tue, 8 Dec 2020 23:01:42 +0800 [thread overview]
Message-ID: <20201208150142.1894-1-ray.ni@intel.com> (raw)
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;
+ }
+ }
- //
- // 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
next reply other threads:[~2020-12-08 15:03 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-12-08 15:01 Ni, Ray [this message]
2020-12-09 8:48 ` [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First Zeng, Star
2020-12-11 10:39 ` Ni, Ray
2020-12-10 8:25 ` Laszlo Ersek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20201208150142.1894-1-ray.ni@intel.com \
--to=devel@edk2.groups.io \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox