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 B7247D811BC for ; Fri, 12 Jan 2024 09:35:12 +0000 (UTC) DKIM-Signature: a=rsa-sha256; bh=HWkano6j6ql46/gYMAMGnhAG0aT2h2kKPO2tHsw0pWk=; 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=1705052111; v=1; b=Kx939qb2M9Hf51S07fMwZhd9XI/7PhjuVPTKQzqau8dzXmRlpDS8bwX2WG9Ad6HWKjavdhxr SwAT/P02uFK7wANbO/PHFRtcwp/c1KHS0sZCqPJ7HrUFsRIfShXDkgDtRwK0DTjQNHRthp4UufS 9YFZPLAebQ0xpAFVZVyZ1fhg= X-Received: by 127.0.0.2 with SMTP id Lc3PYY7687511xcjJIvsxLSI; Fri, 12 Jan 2024 01:35:11 -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.web11.3753.1705052110273155320 for ; Fri, 12 Jan 2024 01:35:10 -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-228-DMNT3PmrNJy4nMlaLreH4Q-1; Fri, 12 Jan 2024 04:35:03 -0500 X-MC-Unique: DMNT3PmrNJy4nMlaLreH4Q-1 X-Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (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 5610428EC10A; Fri, 12 Jan 2024 09:35:03 +0000 (UTC) X-Received: from [10.39.192.105] (unknown [10.39.192.105]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 6041E492BC6; Fri, 12 Jan 2024 09:35:02 +0000 (UTC) Message-ID: <7659165f-a73b-b628-59fe-c29e67beb850@redhat.com> Date: Fri, 12 Jan 2024 10:35:01 +0100 MIME-Version: 1.0 Subject: Re: [edk2-devel] Memory Attribute for depex section To: Pedro Falcato Cc: 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> <45b95719-f1fc-dbc6-a4cc-a022d691844c@redhat.com> <30901646-905c-798c-d088-255498028fff@redhat.com> From: "Laszlo Ersek" In-Reply-To: X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.9 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: P7nBw0QZlEQHhfsBX2dP9Mn3x7686176AA= 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=Kx939qb2; spf=pass (spool.mail.gandi.net: domain of bounce@groups.io designates 66.175.222.108 as permitted sender) smtp.mailfrom=bounce@groups.io; dmarc=fail reason="SPF not aligned (relaxed), DKIM not aligned (relaxed)" header.from=redhat.com (policy=none) On 1/12/24 03:10, Pedro Falcato wrote: > On Thu, Jan 11, 2024 at 8:46 AM Laszlo Ersek wrote: >> >> On 1/10/24 22:50, Pedro Falcato wrote: >>> 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 :) > > Hey, I happen to have written one! > https://github.com/heatd/Onyx/blob/master/kernel/kernel/radix.cpp > It just needs some C'ifying, then some EFI'ing on top, but I'm fairly > confident in its stability. Yes, this is absolutely viable and welcome. You seem to hold the copyright on it, too, so you could even relicense (although MIT should just be fine for edk2). (I had done the same with the rbtree code -- I had written that code much earlier, not for edk2. I re-verified it and ported it to edk2, and relicensed it.) >> 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.) > > Definitely, I use it in Ext4Dxe too, it's great! Heh, I didn't know that. Thanks! > (Although I do have a > small nit in that it allocates nodes itself, and there's no way around > it, but oh well...) Right, that's the usual intrusive vs. non-intrusive containers debate :) I didn't mind more allocations (and hence perhaps more fragmentation), but I wanted to (a) hide the node internals, (b) the possibility to link any given piece of user structure into multiple trees (and other containers) without having to modify the user structure itself (i.e. without embedding further node / link structs into the user struct). I figure each of intrusive and non-intrusive has its advantages over the other; I just went with my preferences. > My idea was to make each handle an index - like a file descriptor - > AFAIK there's no reason why it *needs* to be an actual pointer. > We'd allocate indices when creating a handle, and return that (casted to VOID*). Huh, sneaky. I see two potential problems with this. First, per C std, these "pointers" would be invalid (they wouldn't actually point to valid memory), so even just evaluating them (not dereferencing them!) would invoke undefined behavior. May or may not matter in practice. With compilers getting smarter about optimization (and stricter about std conformance), there could be issues, perhaps. The other concern is a bit contrived, but I *guess* there could be code out there that actually dereferences EFI_HANDLEs. That code would crash. May or may not matter, because such code is arguably already semantically invalid. (It would not necessarily be invalid at the language level -- cf. my previous paragraph --, because passing an otherwise valid EFI_HANDLE to CopyMem, for copying just 1 byte out of the underlying opaque data structure, would not violate the language.) > I should note that I find it super hard to get a concrete idea on > performance for EFI firmware without adequate tooling - I meant to > write a standalone flamegraph tool a few weeks back (even posted in > edk2-devel), but, as far as I could tell, the architectural timer > protocol couldn't get me the interrupt frame[1]. Until then, whether > any of this radix tree vs RB tree vs flat array stuff really > matters... I find it hard to say. > > [1] x86 has 3 timers (PIT, LAPIC timer, HPET) and performance > monitoring interrupts, and I couldn't freely use any of them :^) Edk2 has some form of profiling already (see "MdePkg/Include/Library/PerformanceLib.h"). Usually one sees core code peppered with PERF_CODE_BEGIN and PERF_CODE_END macros. I *think* there is something like a "display performance" (dp) shell application too, that can show the collected stats. But I've never used these facilities. The wiki seems to have two related articles: https://github.com/tianocore/tianocore.github.io/wiki/Edk2-Performance-Infrastructure https://github.com/tianocore/tianocore.github.io/wiki/PerformancePkg The former looks quite comprehensive, at a quick skim. Laszlo -=-=-=-=-=-=-=-=-=-=-=- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#113703): https://edk2.groups.io/g/devel/message/113703 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] -=-=-=-=-=-=-=-=-=-=-=-