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 04FBD9409DE for ; Fri, 12 Jan 2024 02:44:33 +0000 (UTC) DKIM-Signature: a=rsa-sha256; bh=ImS/e+0W3aZELbXIXgUtnYRJasofEgdtwmqXaej3EeM=; c=relaxed/simple; d=groups.io; h=From:Message-id:MIME-version:Subject:Date:In-reply-to:Cc:To:References:Precedence:List-Subscribe:List-Help:Sender:List-Id:Mailing-List:Delivered-To:Reply-To:List-Unsubscribe-Post:List-Unsubscribe:Content-type; s=20140610; t=1705027472; v=1; b=Q+YsCH7QVoE15U+QoFbzIYRKolYFNvH9vdGSvh+iOQjSstqm7yG/lSzKXUb3hKRsjtUUsLMW +vAtHhUWsK+6ZisQEzgBwwTgubmFhYRCNfIRVzULAPXzMqZr8lwuXW3BzxeXbj92mRY1cGy0tza PHlNXJloiPh8czR2YZ1/Gwdo= X-Received: by 127.0.0.2 with SMTP id SEetYY7687511xgjBj0fVCyA; Thu, 11 Jan 2024 18:44:32 -0800 X-Received: from ma-mailsvcp-mx-lapp03.apple.com (ma-mailsvcp-mx-lapp03.apple.com [17.32.222.24]) by mx.groups.io with SMTP id smtpd.web11.10889.1705027471779512246 for ; Thu, 11 Jan 2024 18:44:31 -0800 X-Received: from rn-mailsvcp-mta-lapp03.rno.apple.com (rn-mailsvcp-mta-lapp03.rno.apple.com [10.225.203.151]) by ma-mailsvcp-mx-lapp03.apple.com (Oracle Communications Messaging Server 8.1.0.23.20230328 64bit (built Mar 28 2023)) with ESMTPS id <0S7400I2WNLSWF40@ma-mailsvcp-mx-lapp03.apple.com> for devel@edk2.groups.io; Thu, 11 Jan 2024 18:44:31 -0800 (PST) X-Proofpoint-GUID: vDdDiucErTsS0yAKZOd4LRDWUtTX6KMs X-Proofpoint-ORIG-GUID: vDdDiucErTsS0yAKZOd4LRDWUtTX6KMs X-Received: from rn-mailsvcp-mmp-lapp01.rno.apple.com (rn-mailsvcp-mmp-lapp01.rno.apple.com [17.179.253.14]) by rn-mailsvcp-mta-lapp03.rno.apple.com (Oracle Communications Messaging Server 8.1.0.23.20230328 64bit (built Mar 28 2023)) with ESMTPS id <0S7400A5KNLT3II0@rn-mailsvcp-mta-lapp03.rno.apple.com>; Thu, 11 Jan 2024 18:44:17 -0800 (PST) X-Received: from process_milters-daemon.rn-mailsvcp-mmp-lapp01.rno.apple.com by rn-mailsvcp-mmp-lapp01.rno.apple.com (Oracle Communications Messaging Server 8.1.0.23.20230328 64bit (built Mar 28 2023)) id <0S7400N00NGIJ800@rn-mailsvcp-mmp-lapp01.rno.apple.com>; Thu, 11 Jan 2024 18:44:17 -0800 (PST) X-Va-A: X-Va-T-CD: fe60454d8cca2d204232efa0cd93203e X-Va-E-CD: d38c7c8a8a09a1683f7c6688ae4723e1 X-Va-R-CD: 610f65e57ba77b9f82334b7102a66226 X-Va-ID: 7569a86f-57b5-44b4-83e3-b7c9a749cb49 X-Va-CD: 0 X-V-A: X-V-T-CD: fe60454d8cca2d204232efa0cd93203e X-V-E-CD: d38c7c8a8a09a1683f7c6688ae4723e1 X-V-R-CD: 610f65e57ba77b9f82334b7102a66226 X-V-ID: cce0e260-ceaf-46f6-92b9-9a3a943eb9df X-V-CD: 0 X-Received: from smtpclient.apple (unknown [17.11.120.186]) by rn-mailsvcp-mmp-lapp01.rno.apple.com (Oracle Communications Messaging Server 8.1.0.23.20230328 64bit (built Mar 28 2023)) with ESMTPSA id <0S7400R2ONLSIG00@rn-mailsvcp-mmp-lapp01.rno.apple.com>; Thu, 11 Jan 2024 18:44:17 -0800 (PST) From: "Andrew Fish via groups.io" Message-id: MIME-version: 1.0 (Mac OS X Mail 16.0 \(3774.300.61.1.2\)) Subject: Re: [edk2-devel] Memory Attribute for depex section Date: Thu, 11 Jan 2024 18:44:06 -0800 In-reply-to: <45b95719-f1fc-dbc6-a4cc-a022d691844c@redhat.com> Cc: nhi@os.amperecomputing.com, "ardb+tianocore@kernel.org" To: edk2-devel-groups-io , Laszlo Ersek References: <44ca139f-4d78-4322-b5b6-8e9788bb7486@os.amperecomputing.com> <2ad16043-754e-3bb9-3a4a-702d9a50bf63@redhat.com> <45b95719-f1fc-dbc6-a4cc-a022d691844c@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,afish@apple.com List-Unsubscribe-Post: List-Unsubscribe=One-Click List-Unsubscribe: X-Gm-Message-State: mKryOKKjeWqromzo37x7FoAMx7686176AA= Content-type: multipart/alternative; boundary="Apple-Mail=_A485BFC3-99AD-4F8B-94AC-A729B7E1BD0A" X-GND-Status: LEGIT Authentication-Results: spool.mail.gandi.net; dkim=pass header.d=groups.io header.s=20140610 header.b=Q+YsCH7Q; dmarc=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 --Apple-Mail=_A485BFC3-99AD-4F8B-94AC-A729B7E1BD0A Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Sorry need some more time to digest this=E2=80=A6. First thoughts. 1) The actual performance issue we hit was the explosion of CoreValidateHan= dle() calls as the number of protocols got large for some diags. The newer = handles tended to be at the end of the list if I remember correctly.=20 a) It looks like CoreValidateHandle() is the only place gHandleList was = walked, as the handle info is crossed referenced in the protocol database. = So that is why we changed that. 2) If the issue at hand is MM why not just drop the optimizations? b) If we have so many MM protocols and handles that seems like its own pr= oblem?=20 3) The issue is patching the grammar in place, why can=E2=80=99t we just ma= ke a copy for the dispatcher grammer, and operate on the copy. Maybe via a = copy on 1st update strategy?=20 Thanks, Andrew Fish > On Jan 10, 2024, at 5:45=E2=80=AFAM, Laszlo Ersek wro= te: >=20 > (+ Andrew) >=20 > On 1/10/24 14:09, Laszlo Ersek wrote: >=20 >> 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. >=20 > 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. >=20 > 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"). >=20 > (1) The "Tasks" wiki page mentions something *similar* (but not the > same); see >=20 > https://github.com/tianocore/tianocore.github.io/wiki/Tasks#datahub--gcd-= scalability >=20 > 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.= " >=20 > The same might apply more or less to the protocol database implementation= . >=20 > (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. >=20 > 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.) >=20 > Let me see if I can find the bugzilla ticket... >=20 > Ah, I got it. Apologies, I misremembered: Andrew's comment was not about > the protocol database, but about the handle database. Here it is: >=20 > https://bugzilla.tianocore.org/show_bug.cgi?id=3D988#c7 >=20 > (the BZ is still CONFIRMED btw...) >=20 > 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. >=20 > 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. >=20 > Laszlo >=20 >=20 >=20 >=20 >=20 >=20 -=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 (#113644): https://edk2.groups.io/g/devel/message/113644 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- --Apple-Mail=_A485BFC3-99AD-4F8B-94AC-A729B7E1BD0A Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 Sorry need some more time to dige= st this=E2=80=A6. First thoughts.

1) The actual performa= nce issue we hit was the explosion of CoreValidateHandle() calls as th= e number of protocols got large for some diags. The newer handles tended to= be at the end of the list if I remember correctly. 
  = a) It looks like CoreValidateHandle() is the only place  gH= andleList was walked, as the handle info is crossed referen= ced in the protocol database. So that is why we changed that.
2) = If the issue at hand is MM why not just drop the optimizations?
&= nbsp; b) If we have so many MM protocols and handles that seems like its ow= n problem? 
3) The issue is patching the grammar in place, w= hy can=E2=80=99t we just make a copy for the dispatcher grammer, and operat= e on the copy. Maybe via a copy on 1st update strategy? 
Thanks,

Andrew Fish
On Jan 10, 2024, at 5:45=E2=80=AFAM, Laszlo= Ersek <lersek@redhat.com> wrote:

(+ Andrew)

On 1/10/24 14:09, Laszlo Ersek wrote:=

I think that keeping the depex section re= ad-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 su= cceed. I'd simply start by
removing the optimization, and measuring how = much driver dispatch slows
down in practice, on various platforms.
Can you try this? (I have only build-tested and "uncrustified" it.)
The patch removes the EFI_DEP_REPLACE_TRUE handling altogether, plus itCONST-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.

O= n a tangent: the optimization in question highlights a more general
prob= lem, namely that the DXE (and possibly MM/SMM) protocol databases
are co= nsidered slow, for some access patterns.

Edk2 implements those proto= col databases with linked lists, where lookup
costs O(n) operations (ave= rage and worst cases). And protocol lookups
are quite frequent (for exam= ple, in depex evaluations, they could be
considered "particularly freque= nt").

(1) The "Tasks" wiki page mentions something *similar* (but no= t the
same); see

https://github.com/tianocore/tianocore.github.io= /wiki/Tasks#datahub--gcd-scalability

The description is: "The DXE co= re's DataHub and GCD (Global Coherency
Domain) layers don't scale well a= s the number of data items gets large,
since they are based on simple li= nked lists. Find better data structures."

The same might apply more = or less to the protocol database implementation.

(2) More to the poi= nt, Andrew Fish reported earlier that at Apple, they
had rewritten the D= XE protocol database, using the red-black tree
OrderedCollectionLib that= I had contributed previously to edk2 -- and
they saw significant perfor= mance improvements.

So upstreaming that feature to edk2 could be ver= y valuable. (Red-black
trees have O(log(n)) time cost (worst case) for l= ookup, insertion and
deletion, and O(n) cost for iterating through the w= hole 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 interf= ace from a handle, then the handle
is destroyed -- in fact that's the *o= nly* way to destroy a handle, to my
understanding. See EFI_BOOT_SERVICES= .UninstallProtocolInterface() in the
UEFI spec: "If the last protocol in= terface is removed from a handle, the
handle is freed and is no longer v= alid". Furthermore, calling
InstallProtocolInterface() and InstallMultip= leProtocolInterfaces() is
how one *creates* new handles.

So given= how handles and protocol interfaces are conceptually
interlinked, an rb= tree-based protocol DB might have to maintain multiple
rbtrees internall= y (for the ability to search the database quickly with
different types o= f "keys"). I don't have a design ready in my mind at
all (I'm not that f= amiliar with the *current*, list-based implementation
to begin with!). U= pstreaming Apple's (experimental?) code could prove
very helpful.
Laszlo







_._,_._,_
Groups.io Links:

=20 You receive all messages sent to this group. =20 =20

View/Reply Online (#113644) | =20 | Mute= This Topic | New Topic
Your Subscriptio= n | Contact Group Owner | Unsubscribe [rebecca@openfw.io]

_._,_._,_
--Apple-Mail=_A485BFC3-99AD-4F8B-94AC-A729B7E1BD0A--