(+ 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." 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=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. Laszlo -=-=-=-=-=-=-=-=-=-=-=- 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/21656 Group Owner: devel+ow...@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/leave/9847357/21656/1706620634/xyzzy [arch...@mail-archive.com] -=-=-=-=-=-=-=-=-=-=-=-
