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 94A3B941405 for ; Thu, 11 Jan 2024 08:46:38 +0000 (UTC) DKIM-Signature: a=rsa-sha256; bh=DPjoBsQRjQpR2XSacFpmYap/Pi3vvdyDaoNRfm4QF20=; c=relaxed/simple; d=groups.io; h=Message-ID:Date:MIME-Version:Subject:To:Cc:References:From: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=1704962797; v=1; b=XgNpI9Jny5HppGebEpLaC/lOx0VrZ1n8XbCKxeqlfaYMpQ/dBCIt/jH247gxWxQIPkHR8MLd ftReYLVyrwhgGZ0KxEbN5LlNeSb/qITSleAQRu57wdrLl9tTSle18NXMkfyqslXSX6J0OWYRyWC eoy+vO2Q8KQjjjT5DY/juW7M= X-Received: by 127.0.0.2 with SMTP id ey7YYY7687511xo3im35nNeL; Thu, 11 Jan 2024 00:46:37 -0800 X-Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by mx.groups.io with SMTP id smtpd.web10.7471.1704962796447698804 for ; Thu, 11 Jan 2024 00:46:36 -0800 X-Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-332-hMGxf5nANfKr2y0yetgSFw-1; Thu, 11 Jan 2024 03:46:32 -0500 X-MC-Unique: hMGxf5nANfKr2y0yetgSFw-1 X-Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.rdu2.redhat.com [10.11.54.3]) (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 83C7F1C068D6; Thu, 11 Jan 2024 08:46:32 +0000 (UTC) X-Received: from [10.39.193.20] (unknown [10.39.193.20]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 94F141121306; Thu, 11 Jan 2024 08:46:31 +0000 (UTC) Message-ID: <30901646-905c-798c-d088-255498028fff@redhat.com> Date: Thu, 11 Jan 2024 09:46:30 +0100 MIME-Version: 1.0 Subject: Re: [edk2-devel] Memory Attribute for depex section To: Pedro Falcato , devel@edk2.groups.io Cc: 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> <45b95719-f1fc-dbc6-a4cc-a022d691844c@redhat.com> From: "Laszlo Ersek" In-Reply-To: X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.3 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: rJZvTcg4JAKKnr4gil4hRDDgx7686176AA= Content-Language: en-US Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-GND-Status: LEGIT Authentication-Results: spool.mail.gandi.net; dkim=pass header.d=groups.io header.s=20140610 header.b=XgNpI9Jn; 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 On 1/10/24 22:50, Pedro Falcato wrote: > On Wed, Jan 10, 2024 at 1:45 PM Laszlo Ersek > wrote: >> >> (+ 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? No idea. > >> >> 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 > unfriendly... Sure, if someone contributes a different data structure that is suitable for the task :) RB trees may be cache unfriendly, but the functionality they provide with O(log(n)) worst case performance is amazing. You can use them as read-write associate arrays, sorted lists supporting forward and backward traversal (in fact tools for sorting), priority queues, etc. When I contributed the code, edk2 didn't have any associative array type, so something generic that would address the widest range of use cases looked like a good idea. (And indeed the library has been well applied in several of those use cases since, in various parts of edk2 -- for sorting, uniqueness-checking, async interface token tracking & lookups.) This is not an argument against a more suitable data structure of course. Just pointing out that the RB tree has worked well thus far. E.g., under the BZ link below, Andrew mentions a diagnostic tool that creates 3000 handles. Looking up an element in a 3000-element list would cost 1500 iterations on average; using a balanced binary search tree it might cost ~11 iterations. Assuming that linked lists and linked binary search trees are similarly cache-unfriendly, that's a ~136 factor of improvement. > >> >> 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=988#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] EFI_HANDLE is a typedef to (VOID*) per UEFI spec -- section 2.3.1 "Data Types" says: "A collection of related interfaces. Type VOID *" --, so EFI_HANDLE can't be redefined, it would break compatibility with everything. Internally, it could be cast to UINTN, and then those 32- or 64-bit long bit strings could be considered as keys for a radix tree. But I'm not sure if this would still be as useful as the two-level radix tree (with a fanout of 64) that you describe. (If we wanted to map the EFI_HANDLEs to the index space [0..4095], then we'd just land back at the original problem: storing the EFI_HANDLEs in an associative data structure, for example in a hash map. We could find a good hash function, but because it would mathematically reduce the key space from 64-bit pointers to 12-bit indices, collisions would be theoretically inevitable, and the data structure couldn't avoid *storing* the mapping. This is not a general argument against using a hash table, it just means that we'd have to provide a good initial table size, and then deal with resizing cost whenever necessary.) > 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?) I can answer this question reasonably well, I think. I have a script that collects symbolic names of GUIDs from the edk2 tree (plus hardcodes a number of well-known but not edk2 GUIDs), and creates a "sed" script out of them. Then another script uses this "sed" script for filtering edk2 logs -- the idea being to replace the whole bunch of logged GUIDs with their symbolic names. That makes logs much easier to read. The generator script is written such a way that the generated "sed" script only grows over time; put differently, this "dictionary" of name<->GUID associations never forgets, it only picks up new GUIDs. The "sed" script (= the dictionary file) consists of entries like s:FFB19961-79CC-4684-84A8-C31B0A2BBE82:[EarlyFdt16550SerialPortHookLib]:ig s:FFB56F09-65E3-4462-A799-2F0D1930D38C:[DxeContextBufferModuleConfigLib]:ig s:FFE06BDD-6107-46A6-7BB2-5A9C7EC5275C:[EfiAcpiTableProtocol]:ig s:FFF12B8D-7696-4C8B-A985-2747075B4F50:[EfiSystemNvDataFv]:ig it's sorted uniquely by GUID. Right now, it has 3074 entries. (People like generating GUIDs! :) In PI/UEFI/edk2, *everything* is a GUID, not just protocols!) So using 64 buckets would hash ~50 different protocol GUIDs to any given bucket (although, again, not all of those three thousand GUIDs are *protocol* GUIDs). 1024 buckets might work better. Laszlo -=-=-=-=-=-=-=-=-=-=-=- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#113595): https://edk2.groups.io/g/devel/message/113595 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/1913456212/xyzzy [rebecca@openfw.io] -=-=-=-=-=-=-=-=-=-=-=-