From nobody Fri May 17 09:18:41 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of groups.io designates 66.175.222.108 as permitted sender) client-ip=66.175.222.108; envelope-from=bounce+27952+68715+1787277+3901457@groups.io; helo=mail02.groups.io; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of groups.io designates 66.175.222.108 as permitted sender) smtp.mailfrom=bounce+27952+68715+1787277+3901457@groups.io; dmarc=fail(p=none dis=none) header.from=intel.com ARC-Seal: i=1; a=rsa-sha256; t=1607683753; cv=none; d=zohomail.com; s=zohoarc; b=ipDb5Rg+P5T/PPaU7fTBXJPDwTqNpREsJHBOt8Yi7OwQtnjej3SeMgoGDpNdkm8Xr1BSYF5CYmqxNYE2tpPUOsFdBHfQTMpbpBwbdzHJ0QDuBJ/q3VuTJmPA7Y3f+T8xw30/8Q9VMCj9rvfTtewVeTTTqMJjH3T5+i5sSCVcf9E= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1607683753; h=Content-Transfer-Encoding:Cc:Date:From:List-Id:List-Unsubscribe:MIME-Version:Message-ID:Reply-To:Sender:Subject:To; bh=OM4weFhPkyfTEZo1H71yehck1A5t+7N60uBXNEZZ+MQ=; b=UZq4FuEf6cWsH3MlhwFTiIfg/cckuYmNnBhR3nBuH4V14aoZ1XyFsd6DEV+EyZQNEfpMg27/Nv6YhvR19tGJ1sZoFzkwb/K0jO6DguAl8DLhJIrlWSr5QmnrNDVmQnZ3Ryd4EBpXuKkYjl4QQiLTG1snBEu36IECr4EraPkjuPw= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of groups.io designates 66.175.222.108 as permitted sender) smtp.mailfrom=bounce+27952+68715+1787277+3901457@groups.io; dmarc=fail header.from= (p=none dis=none) header.from= Received: from mail02.groups.io (mail02.groups.io [66.175.222.108]) by mx.zohomail.com with SMTPS id 1607683753006162.32857095298164; Fri, 11 Dec 2020 02:49:13 -0800 (PST) Return-Path: X-Received: by 127.0.0.2 with SMTP id 8NgkYY1788612xKxYMeNq0GN; Fri, 11 Dec 2020 02:49:12 -0800 X-Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by mx.groups.io with SMTP id smtpd.web08.4847.1607683752111898336 for ; Fri, 11 Dec 2020 02:49:12 -0800 IronPort-SDR: EiTV51W0H2ETMaRceADIuYj9shECIy88CP1ohxHSxAQmFykqqGmULEiErUmQpLpZUDbSS6FHqQ bIV8UNzGbQdQ== X-IronPort-AV: E=McAfee;i="6000,8403,9831"; a="173648922" X-IronPort-AV: E=Sophos;i="5.78,411,1599548400"; d="scan'208";a="173648922" X-Received: from orsmga001.jf.intel.com ([10.7.209.18]) by fmsmga103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 11 Dec 2020 02:49:11 -0800 IronPort-SDR: uELjAe85P+I9zXZKxyLz7RljRU6Gpsl0O2cjMYOUsNYTGCLx3WNQl5F1xlVx8aTrg93lm7JsVu 5QG2Tuvn7H+w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.78,411,1599548400"; d="scan'208";a="409155096" X-Received: from ray-dev.ccr.corp.intel.com ([10.239.158.87]) by orsmga001.jf.intel.com with ESMTP; 11 Dec 2020 02:49:10 -0800 From: "Ni, Ray" To: devel@edk2.groups.io Cc: Eric Dong , Star Zeng , Yun Lou , Laszlo Ersek Subject: [edk2-devel] [PATCH V2] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First Date: Fri, 11 Dec 2020 18:47:39 +0800 Message-Id: <20201211104739.172-1-ray.ni@intel.com> MIME-Version: 1.0 Precedence: Bulk List-Unsubscribe: Sender: devel@edk2.groups.io List-Id: Mailing-List: list devel@edk2.groups.io; contact devel+owner@edk2.groups.io Reply-To: devel@edk2.groups.io,ray.ni@intel.com X-Gm-Message-State: zjGGIAZWCl1SXykGmRAdxgmZx1787277AA= Content-Transfer-Encoding: quoted-printable DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=groups.io; q=dns/txt; s=20140610; t=1607683752; bh=52vvffBcK2/QFxpgUblYvU9x49Fp2kgfEEeXpZtJpK0=; h=Cc:Date:From:Reply-To:Subject:To; b=Ir7T9yqB37tzQLNGOC09c8kDOiwoItscf19TdY2f1widM02P7vGsXhF9rHgRXSAjkJZ qwk5NOwsBd1KTyFpAGuB986f8ekEedgwZq8gkPnIHMxvMmmWp/UfH+7JOR3d5eaiopjeH fRkdhhzYmZEbTBbux7yEvjcr3R34RNdj7mU= X-ZohoMail-DKIM: pass (identity @groups.io) Content-Type: text/plain; charset="utf-8" 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 Reviewed-by: Eric Dong Reviewed-by: Star Zeng --- .../CpuFeaturesInitialize.c | 96 +++++++++---------- 1 file changed, 47 insertions(+), 49 deletions(-) diff --git a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitializ= e.c b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c index d4a576385f..a1e972b1a2 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,69 @@ CpuInitDataInitialize ( =20 // // Initialize CpuFeaturesData->InitOrder[].CpuInfo.First + // Use AllocatePages () instead of AllocatePool () because pool cannot b= e freed in PEI phase but page can. // + Pages =3D EFI_SIZE_TO_PAGES (CpuStatus->PackageCount * sizeof (UINT3= 2) + CpuStatus->PackageCount * CpuStatus->MaxCoreCount * sizeof (UINT32)); + FirstCore =3D AllocatePages (Pages); + ASSERT (FirstCore !=3D NULL); + FirstThread =3D FirstCore + CpuStatus->PackageCount; =20 // - // Set First.Package for each thread belonging to the first package. + // Set FirstPackage, FirstCore[], FirstThread[] to maximum package ID, c= ore ID, thread ID. // - First =3D MAX_UINT32; + FirstPackage =3D MAX_UINT32; + SetMem32 (FirstCore, CpuStatus->PackageCount * sizeof (UINT32), MAX_UI= NT32); + SetMem32 (FirstThread, CpuStatus->PackageCount * CpuStatus->MaxCoreCount= * sizeof (UINT32), MAX_UINT32); + for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNum= ber++) { Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Proc= essorInfo.Location; - First =3D MIN (Location->Package, First); + + // + // Save the minimum package ID in the platform. + // + FirstPackage =3D MIN (Location->Package, FirstPackage); + =20 + // + // Save the minimum core ID per package. + // + FirstCore[Location->Package] =3D MIN (Location->Core, FirstCore[Locati= on->Package]); + =20 + // + // Save the minimum thread ID per core. + // + FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->Co= re] =3D MIN ( + Location->Thread, + FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->= Core] + ); } + + // + // Update the First field. + // for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNum= ber++) { Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Proc= essorInfo.Location; - if (Location->Package =3D=3D First) { + + if (Location->Package =3D=3D FirstPackage) { CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Package = =3D 1; } - } =20 - // - // Set First.Die/Tile/Module for each thread assuming: - // single Die under each package, single Tile under each Die, single Mo= dule under each Tile - // - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNum= ber++) { + // + // 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 =3D 1; CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Tile =3D 1; CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Module =3D 1; - } =20 - for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; Package= Index++) { - // - // Set First.Core for each thread in the first core of each package. - // - First =3D MAX_UINT32; - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorN= umber++) { - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Pr= ocessorInfo.Location; - if (Location->Package =3D=3D PackageIndex) { - First =3D MIN (Location->Core, First); - } + if (Location->Core =3D=3D FirstCore[Location->Package]) { + CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core =3D 1; } - - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorN= umber++) { - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.Pr= ocessorInfo.Location; - if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D F= irst) { - CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core =3D= 1; - } + if (Location->Thread =3D=3D FirstThread[Location->Package * CpuStatus-= >MaxCoreCount + Location->Core]) { + CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thread =3D= 1; } } =20 - for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; Package= Index++) { - for (CoreIndex =3D 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex++= ) { - // - // Set First.Thread for the first thread of each core. - // - First =3D MAX_UINT32; - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; Processo= rNumber++) { - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.= ProcessorInfo.Location; - if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D= CoreIndex) { - First =3D MIN (Location->Thread, First); - } - } - - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; Processo= rNumber++) { - Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.= ProcessorInfo.Location; - if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D= CoreIndex && Location->Thread =3D=3D First) { - CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thread= =3D 1; - } - } - } - } + FreePages (FirstCore, Pages); } =20 /** --=20 2.27.0.windows.1 -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#68715): https://edk2.groups.io/g/devel/message/68715 Mute This Topic: https://groups.io/mt/78876501/1787277 Group Owner: devel+owner@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [importer@patchew.org] -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-