From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by mx.groups.io with SMTP id smtpd.web09.1773.1610703058738718027 for ; Fri, 15 Jan 2021 01:30:58 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=aCzAYO87; spf=pass (domain: redhat.com, ip: 63.128.21.124, mailfrom: philmd@redhat.com) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1610703057; 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=Nx92wMQ3qFdo93m9HudokplU0SJ+qKaz9lPz9xTTqGc=; b=aCzAYO8735W+J1N8Qwk7BQTosY2KCCG/Qw5JXRm6m6nMNgV46vN1F0s+eEOdVL5sKyN6Ea xS/uyh89hzSBMN2bYXYzpFv5AlhD7tN7aDrePhUwQSkG2j1uAYKZcuWTAC7hMgz8n2yjtn EdMY8522AnV7+8Typ901/JUl9GmCy8U= Received: from mail-ej1-f70.google.com (mail-ej1-f70.google.com [209.85.218.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-324-NHHyJ4sjNUKYUgKTCpzODw-1; Fri, 15 Jan 2021 04:30:54 -0500 X-MC-Unique: NHHyJ4sjNUKYUgKTCpzODw-1 Received: by mail-ej1-f70.google.com with SMTP id h4so3387998eja.12 for ; Fri, 15 Jan 2021 01:30:54 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=Nx92wMQ3qFdo93m9HudokplU0SJ+qKaz9lPz9xTTqGc=; b=C9Qk4+sgwjWvzV+CJZQTJZuMOj+C1tXZff6MEOEBx2hxg52I8Ud0FihNqttaDuw/A3 j1ZJ8xhQ5H7rbpbBMD2e1LgnvdOYsoR8tsGGp1n4+gljnpe2JdcwbfqsYMAxX6p2AZVF gEiMjmekjh4DXDVE4DKtM5HJcLn2g9wm0eKMwUGPuK7chufxEmkVZx2PlWI9wKsr0gwM Pyaf/em9YdJIYKJKYXThRmsjd1WbLL1LxLb4zMLtIpwqObbkMae+X33Vh0fOU+O+eX5+ M6ZceezXYB7HoDJ9wTa29Wuyg28huH8llpEbxB06vziKzYhEpz7pWsIZeQftOivnNLLx NcuQ== X-Gm-Message-State: AOAM532GER3iQziyPQn9d2Kxt1WIwp1HufBPsZJySVfOBUcyVTC7ZtqG xOxQ6dFgelkQthxWmhyKeRiEP+OZoDcB0II4F2s3Rkrps1Bo1ImrJhze4xfL94Z4z+IBtmAJkQ2 kWlDKmbMO/OHsvw== X-Received: by 2002:a17:906:3899:: with SMTP id q25mr8024972ejd.173.1610703053060; Fri, 15 Jan 2021 01:30:53 -0800 (PST) X-Google-Smtp-Source: ABdhPJxZk/jmLoNYM2GYj+Uw5R2OIdTieUe7ltKlY0Mw+w84/wtg27uOuutEaHfXvyeGtp/KgwXSmg== X-Received: by 2002:a17:906:3899:: with SMTP id q25mr8024958ejd.173.1610703052918; Fri, 15 Jan 2021 01:30:52 -0800 (PST) Return-Path: Received: from [192.168.1.36] (13.red-83-57-169.dynamicip.rima-tde.net. [83.57.169.13]) by smtp.gmail.com with ESMTPSA id b7sm3037262ejz.4.2021.01.15.01.30.51 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 15 Jan 2021 01:30:52 -0800 (PST) Subject: Re: [PATCH v2 09/10] OvmfPkg: disable list length checks in NOOPT and DEBUG builds To: Laszlo Ersek , devel@edk2.groups.io Cc: Anthony Perard , Ard Biesheuvel , Jordan Justen , Julien Grall , Leif Lindholm , Peter Grehan , Rebecca Cran , Sami Mujawar References: <20210113085453.10168-1-lersek@redhat.com> <20210113085453.10168-10-lersek@redhat.com> From: =?UTF-8?B?UGhpbGlwcGUgTWF0aGlldS1EYXVkw6k=?= Message-ID: <1a58ca6b-b8b0-83ac-37e5-2022bddb7bc0@redhat.com> Date: Fri, 15 Jan 2021 10:30:50 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.6.0 MIME-Version: 1.0 In-Reply-To: <20210113085453.10168-10-lersek@redhat.com> Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=philmd@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: 8bit On 1/13/21 9:54 AM, Laszlo Ersek wrote: > 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 > --- > > Notes: > v2: > - no changes > - pick up Ard's A-b > > 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(+) Reviewed-by: Philippe Mathieu-Daude