From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by mx.groups.io with SMTP id smtpd.web11.10162.1607588747660137481 for ; Thu, 10 Dec 2020 00:25:47 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=Hr6whWqs; spf=pass (domain: redhat.com, ip: 216.205.24.124, mailfrom: lersek@redhat.com) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1607588746; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=OW1ADBtGx0k8GKFmPT2z/RElXC1tc57tgh4Slyyz/kM=; b=Hr6whWqsKlRzhVAmfkWDGFyES41QJXM/jVFVh90ZrJ6Uzf01bXTi7fY5GhcF3njQOMfTjO AiGit+Z13KfH+UL0H2mOCc+g9mYp8+mq9ddB9Rhv5BwjiFqj0WOZTxp0NcqHa26j7UGxYQ 10Vo4aaxoLqHpxasCFU4dmz4SfZfELI= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-367-AJg0S-s7NF-kZDblBMDpeQ-1; Thu, 10 Dec 2020 03:25:42 -0500 X-MC-Unique: AJg0S-s7NF-kZDblBMDpeQ-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id F4027423B8; Thu, 10 Dec 2020 08:25:40 +0000 (UTC) Received: from lacos-laptop-7.usersys.redhat.com (ovpn-113-52.ams2.redhat.com [10.36.113.52]) by smtp.corp.redhat.com (Postfix) with ESMTP id 70A6310074FC; Thu, 10 Dec 2020 08:25:39 +0000 (UTC) Subject: Re: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First To: Ray Ni , devel@edk2.groups.io Cc: Eric Dong , Star Zeng , Yun Lou References: <20201208150142.1894-1-ray.ni@intel.com> From: "Laszlo Ersek" Message-ID: Date: Thu, 10 Dec 2020 09:25:38 +0100 MIME-Version: 1.0 In-Reply-To: <20201208150142.1894-1-ray.ni@intel.com> X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=lersek@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit 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 > Cc: Eric Dong > Cc: Star Zeng > Cc: Yun Lou > Cc: Laszlo Ersek > --- > .../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); > } > > /** >