From d3f3c942013a6f1c6bde7ba6ca41ca97bab51663 Mon Sep 17 00:00:00 2001 From: Laszlo Ersek Date: Wed, 13 Jan 2021 09:54:52 +0100 Subject: OvmfPkg: disable list length checks in NOOPT and DEBUG builds MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 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/OvmfXen.dsc | 1 + 1 file changed, 1 insertion(+) (limited to 'OvmfPkg/OvmfXen.dsc') 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 -- cgit v1.2.3