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 CBF0F740034 for ; Wed, 10 Jan 2024 21:51:09 +0000 (UTC) DKIM-Signature: a=rsa-sha256; bh=nwEWoPk6xPqXGWFKaUa70rJN3Xq8s3G1L2HaQ+nil2A=; c=relaxed/simple; d=groups.io; h=MIME-Version:References:In-Reply-To:From:Date:Message-ID:Subject:To:Cc:Precedence:List-Subscribe:List-Help:Sender:List-Id:Mailing-List:Delivered-To:Reply-To:List-Unsubscribe-Post:List-Unsubscribe:Content-Type:Content-Transfer-Encoding; s=20140610; t=1704923468; v=1; b=Jj5mhu9jaO/HXzo8kPGzu6tTGrZSZiWEBPyznCfbNUxJVZuV/4Z7Tl+/p9iwMG/0svUhl5qG RXDWWcnpjAVAoB0/iWyy5k0nGfZaWhHjslhSYhdzbUeV9vMQE9RNWTJtI6mF+jJuCjEKDwHNWz7 zWXwVabArvtKMLLGraYe9m/Q= X-Received: by 127.0.0.2 with SMTP id joIHYY7687511xBT8TC66oCa; Wed, 10 Jan 2024 13:51:08 -0800 X-Received: from mail-vs1-f44.google.com (mail-vs1-f44.google.com [209.85.217.44]) by mx.groups.io with SMTP id smtpd.web11.6497.1704923467634814544 for ; Wed, 10 Jan 2024 13:51:07 -0800 X-Received: by mail-vs1-f44.google.com with SMTP id ada2fe7eead31-46777099deeso960888137.0 for ; Wed, 10 Jan 2024 13:51:07 -0800 (PST) X-Gm-Message-State: NpJpOIVMaDUMmXkSNsjskYnox7686176AA= X-Google-Smtp-Source: AGHT+IHL4kQnSKARmLm98bdYQaXwkc4F9vMD6yF9aNku7iU7ll3EVqLuyFUcwd8C6F4DkAWnlWaa8k4zBgNSEsJtMc0= X-Received: by 2002:a05:6102:6c3:b0:468:633:aab3 with SMTP id m3-20020a05610206c300b004680633aab3mr162441vsg.19.1704923466059; Wed, 10 Jan 2024 13:51:06 -0800 (PST) MIME-Version: 1.0 References: <44ca139f-4d78-4322-b5b6-8e9788bb7486@os.amperecomputing.com> <2ad16043-754e-3bb9-3a4a-702d9a50bf63@redhat.com> <45b95719-f1fc-dbc6-a4cc-a022d691844c@redhat.com> In-Reply-To: <45b95719-f1fc-dbc6-a4cc-a022d691844c@redhat.com> From: "Pedro Falcato" Date: Wed, 10 Jan 2024 21:50:54 +0000 Message-ID: Subject: Re: [edk2-devel] Memory Attribute for depex section To: devel@edk2.groups.io, lersek@redhat.com Cc: nhi@os.amperecomputing.com, "ardb+tianocore@kernel.org" , Andrew Fish 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,pedro.falcato@gmail.com List-Unsubscribe-Post: List-Unsubscribe=One-Click List-Unsubscribe: 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=Jj5mhu9j; dmarc=fail reason="SPF not aligned (relaxed), DKIM not aligned (relaxed)" header.from=gmail.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 On Wed, Jan 10, 2024 at 1:45=E2=80=AFPM Laszlo Ersek wr= ote: > > (+ 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. > > > > Can you try this? (I have only build-tested and "uncrustified" it.) > > > > 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-= scalability > > 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.= " How large do they usually get? What's the worst case? > > 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.) FWIW, can we do better than an RB tree? They're notoriously cache unfriendl= y... > > 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. Ok, some thoughts: For the handle database, if we made EFI_HANDLE an integer instead, we could very easily use something similar to a radix tree (see Linux's xarray). This would provide O(log(n)) lookups and insertion with a much higher fan-out, without needing CoreValidateHandle's awful O(n) lookup every time it gets an EFI_HANDLE. You'd just look up the handle in the tree and if NULL, it's invalid. [1] For the protocol database, you'd replace the linked list with a simple hashtable, hashed by protocol. Something as simple as LIST_ENTRY mProtocolHashtable[64]; would probably be enough to fan out most of the problems (I think? How many different protocols are there?) --=20 Pedro [1] One could be wary of doing this lookup for every EFI_HANDLE instead of having the pointer directly. But this is much more efficient than needing to iterate a linked list to validate a pointer. Considering an xarray-like radix tree as previously described, two levels with a fan-out of 64 could describe indices 0 - 4096 (64 * 64), which is much more efficient than chasing through pointers (worst case) 4096 times until we find the handle. -=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 (#113541): https://edk2.groups.io/g/devel/message/113541 Mute This Topic: https://groups.io/mt/103594587/7686176 Group Owner: devel+owner@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [rebecca@openfw.io] -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-