From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail02.groups.io (mail02.groups.io [66.175.222.108]) by spool.mail.gandi.net (Postfix) with ESMTPS id 21371941A31 for ; Wed, 10 Jan 2024 13:45:22 +0000 (UTC) DKIM-Signature: a=rsa-sha256; bh=lwlXKQXQxtOVl3pKLLJxCO43zSSMnc9BHn2uRHEBqz8=; c=relaxed/simple; d=groups.io; h=Message-ID:Date:MIME-Version:Subject:From:To:References:In-Reply-To:Precedence:List-Subscribe:List-Help:Sender:List-Id:Mailing-List:Delivered-To:Reply-To:List-Unsubscribe-Post:List-Unsubscribe:Content-Language:Content-Type:Content-Transfer-Encoding; s=20140610; t=1704894321; v=1; b=p3cCzaT4eKEUkELJnBVHfEMpqkZpVp3KhyKlU6a8hVInWo40pJ+R2kqgSRpu5Pq6GNmBi7/E 7tnUW3GPuAunkeFwpWJRnUGllML5blMWXbN6b1/z+YQXCNyMRtXRLr/OHhUcdl94mZVZIXodSVl z9tDt6wZZNLM7TltUI3sCn4U= X-Received: by 127.0.0.2 with SMTP id mwSBYY7687511xqR0LMucAK0; Wed, 10 Jan 2024 05:45:21 -0800 X-Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by mx.groups.io with SMTP id smtpd.web10.11794.1704894321058064955 for ; Wed, 10 Jan 2024 05:45:21 -0800 X-Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-325-35z8bjlzN9GNlZnMpLlxHw-1; Wed, 10 Jan 2024 08:45:17 -0500 X-MC-Unique: 35z8bjlzN9GNlZnMpLlxHw-1 X-Received: from smtp.corp.redhat.com (int-mx10.intmail.prod.int.rdu2.redhat.com [10.11.54.10]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id B052A85A588; Wed, 10 Jan 2024 13:45:16 +0000 (UTC) X-Received: from [10.39.192.166] (unknown [10.39.192.166]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 0E6E8492BF0; Wed, 10 Jan 2024 13:45:15 +0000 (UTC) Message-ID: <45b95719-f1fc-dbc6-a4cc-a022d691844c@redhat.com> Date: Wed, 10 Jan 2024 14:45:14 +0100 MIME-Version: 1.0 Subject: Re: [edk2-devel] Memory Attribute for depex section From: "Laszlo Ersek" To: devel@edk2.groups.io, nhi@os.amperecomputing.com, "ardb+tianocore@kernel.org" , Andrew Fish References: <44ca139f-4d78-4322-b5b6-8e9788bb7486@os.amperecomputing.com> <2ad16043-754e-3bb9-3a4a-702d9a50bf63@redhat.com> In-Reply-To: <2ad16043-754e-3bb9-3a4a-702d9a50bf63@redhat.com> X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.10 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Precedence: Bulk List-Subscribe: List-Help: 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,lersek@redhat.com List-Unsubscribe-Post: List-Unsubscribe=One-Click List-Unsubscribe: X-Gm-Message-State: hFoVgawkqhK30KkjpAQgdgxBx7686176AA= Content-Language: en-US Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-GND-Status: LEGIT Authentication-Results: spool.mail.gandi.net; dkim=pass header.d=groups.io header.s=20140610 header.b=p3cCzaT4; dmarc=fail reason="SPF not aligned (relaxed), DKIM not aligned (relaxed)" header.from=redhat.com (policy=none); spf=pass (spool.mail.gandi.net: domain of bounce@groups.io designates 66.175.222.108 as permitted sender) smtp.mailfrom=bounce@groups.io (+ Andrew) On 1/10/24 14:09, Laszlo Ersek wrote: > I think that keeping the depex section read-only is valuable, so I'd > rule out #2. I'd also not start with option #1 -- copying the depex to > heap memory, just so this optimization can succeed. I'd simply start by > removing the optimization, and measuring how much driver dispatch slows > down in practice, on various platforms. >=20 > Can you try this? (I have only build-tested and "uncrustified" it.) >=20 > The patch removes the EFI_DEP_REPLACE_TRUE handling altogether, plus it > CONST-ifies the Iterator pointer (which points into the DEPEX section), > so that the compiler catch any possible accesses at *build time* that > would write to the write-protected DEPEX memory area. On a tangent: the optimization in question highlights a more general problem, namely that the DXE (and possibly MM/SMM) protocol databases are considered slow, for some access patterns. Edk2 implements those protocol databases with linked lists, where lookup costs O(n) operations (average and worst cases). And protocol lookups are quite frequent (for example, in depex evaluations, they could be considered "particularly frequent"). (1) The "Tasks" wiki page mentions something *similar* (but not the same); see https://github.com/tianocore/tianocore.github.io/wiki/Tasks#datahub--gcd-sc= alability The description is: "The DXE core's DataHub and GCD (Global Coherency Domain) layers don't scale well as the number of data items gets large, since they are based on simple linked lists. Find better data structures." The same might apply more or less to the protocol database implementation. (2) More to the point, Andrew Fish reported earlier that at Apple, they had rewritten the DXE protocol database, using the red-black tree OrderedCollectionLib that I had contributed previously to edk2 -- and they saw significant performance improvements. So upstreaming that feature to edk2 could be very valuable. (Red-black trees have O(log(n)) time cost (worst case) for lookup, insertion and deletion, and O(n) cost for iterating through the whole data structure.) Let me see if I can find the bugzilla ticket... Ah, I got it. Apologies, I misremembered: Andrew's comment was not about the protocol database, but about the handle database. Here it is: https://bugzilla.tianocore.org/show_bug.cgi?id=3D988#c7 (the BZ is still CONFIRMED btw...) Still, I think it must be related in a way. Namely, an EFI handle exists if and only if at least one protocol interface is installed on it. If you uninstall the last protocol interface from a handle, then the handle is destroyed -- in fact that's the *only* way to destroy a handle, to my understanding. See EFI_BOOT_SERVICES.UninstallProtocolInterface() in the UEFI spec: "If the last protocol interface is removed from a handle, the handle is freed and is no longer valid". Furthermore, calling InstallProtocolInterface() and InstallMultipleProtocolInterfaces() is how one *creates* new handles. So given how handles and protocol interfaces are conceptually interlinked, an rbtree-based protocol DB might have to maintain multiple rbtrees internally (for the ability to search the database quickly with different types of "keys"). I don't have a design ready in my mind at all (I'm not that familiar with the *current*, list-based implementation to begin with!). Upstreaming Apple's (experimental?) code could prove very helpful. Laszlo -=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 (#113532): https://edk2.groups.io/g/devel/message/113532 Mute This Topic: https://groups.io/mt/103594587/7686176 Group Owner: devel+owner@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/leave/12367111/7686176/19134562= 12/xyzzy [rebecca@openfw.io] -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-