From d3f3c942013a6f1c6bde7ba6ca41ca97bab51663 Mon Sep 17 00:00:00 2001 From: Laszlo Ersek Date: Wed, 13 Jan 2021 09:54:52 +0100 Subject: [PATCH] OvmfPkg: disable list length checks in NOOPT and DEBUG builds MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit In NOOPT and DEBUG builds, if "PcdMaximumLinkedListLength" is nonzero, then several LIST_ENTRY *node* APIs in BaseLib compare the *full* list length against the PCD. This turns the time complexity of node-level APIs from constant to linear, and that of full-list manipulations from linear to quadratic. As an example, consider the EFI_SHELL_FILE_INFO list, which is a data structure that's widely used in the UEFI shell. I randomly extracted 5000 files from "/usr/include" on my laptop, spanning 1095 subdirectories out of 1538, and then ran "DIR -R" in the UEFI shell on this tree. These are the wall-clock times: PcdMaximumLinkedListLength PcdMaximumLinkedListLength =1,000,000 =0 -------------------------- --------------------------- FAT 4 min 31 s 18 s virtio-fs 5 min 13 s 1 min 33 s Checking list lengths against an arbitrary maximum (default: 1,000,000) seems useless even in NOOPT and DEBUG builds, while the cost is significant; so set the PCD to 0. Cc: Anthony Perard Cc: Ard Biesheuvel Cc: Jordan Justen Cc: Julien Grall Cc: Leif Lindholm Cc: Peter Grehan Cc: Philippe Mathieu-Daudé Cc: Rebecca Cran Cc: Sami Mujawar Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3152 Signed-off-by: Laszlo Ersek Acked-by: Ard Biesheuvel Message-Id: <20210113085453.10168-10-lersek@redhat.com> Reviewed-by: Philippe Mathieu-Daudé --- OvmfPkg/AmdSev/AmdSevX64.dsc | 1 + OvmfPkg/Bhyve/BhyveX64.dsc | 1 + OvmfPkg/OvmfPkgIa32.dsc | 1 + OvmfPkg/OvmfPkgIa32X64.dsc | 1 + OvmfPkg/OvmfPkgX64.dsc | 1 + OvmfPkg/OvmfXen.dsc | 1 + 6 files changed, 6 insertions(+) diff --git a/OvmfPkg/AmdSev/AmdSevX64.dsc b/OvmfPkg/AmdSev/AmdSevX64.dsc index dad8635c33..e6d545ab52 100644 --- a/OvmfPkg/AmdSev/AmdSevX64.dsc +++ b/OvmfPkg/AmdSev/AmdSevX64.dsc @@ -441,6 +441,7 @@ gEfiMdeModulePkgTokenSpaceGuid.PcdStatusCodeMemorySize|1 gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10 + gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048) gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000 gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800 diff --git a/OvmfPkg/Bhyve/BhyveX64.dsc b/OvmfPkg/Bhyve/BhyveX64.dsc index 33edf3d2d6..a1f43eaa4d 100644 --- a/OvmfPkg/Bhyve/BhyveX64.dsc +++ b/OvmfPkg/Bhyve/BhyveX64.dsc @@ -431,6 +431,7 @@ gEfiMdeModulePkgTokenSpaceGuid.PcdStatusCodeMemorySize|1 gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10 + gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048) gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000 gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800 diff --git a/OvmfPkg/OvmfPkgIa32.dsc b/OvmfPkg/OvmfPkgIa32.dsc index 8b6dbb8345..e5184ef067 100644 --- a/OvmfPkg/OvmfPkgIa32.dsc +++ b/OvmfPkg/OvmfPkgIa32.dsc @@ -478,6 +478,7 @@ gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE !endif gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10 + gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048) gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000 gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800 diff --git a/OvmfPkg/OvmfPkgIa32X64.dsc b/OvmfPkg/OvmfPkgIa32X64.dsc index 4d7a26636a..3bfec9196e 100644 --- a/OvmfPkg/OvmfPkgIa32X64.dsc +++ b/OvmfPkg/OvmfPkgIa32X64.dsc @@ -482,6 +482,7 @@ gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE !endif gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10 + gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048) gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000 gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800 diff --git a/OvmfPkg/OvmfPkgX64.dsc b/OvmfPkg/OvmfPkgX64.dsc index 10f6a64d7f..1376158e37 100644 --- a/OvmfPkg/OvmfPkgX64.dsc +++ b/OvmfPkg/OvmfPkgX64.dsc @@ -484,6 +484,7 @@ gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE !endif gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10 + gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048) gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000 gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800 diff --git a/OvmfPkg/OvmfXen.dsc b/OvmfPkg/OvmfXen.dsc index 8ae6ed07b2..b79ee866c5 100644 --- a/OvmfPkg/OvmfXen.dsc +++ b/OvmfPkg/OvmfXen.dsc @@ -358,6 +358,7 @@ gEfiMdeModulePkgTokenSpaceGuid.PcdStatusCodeMemorySize|1 gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10 + gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048) gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000 gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800 -- 2.39.2