From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from relay8-d.mail.gandi.net (relay8-d.mail.gandi.net [IPv6:2001:4b98:dc4:8::228]) by sourceware.org (Postfix) with ESMTPS id 2A23D3858D39 for ; Mon, 19 Sep 2022 09:34:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2A23D3858D39 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=seketeli.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=seketeli.org Received: (Authenticated sender: dodj@seketeli.org) by mail.gandi.net (Postfix) with ESMTPSA id 733CE1BF20B; Mon, 19 Sep 2022 09:34:52 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=seketeli.org; s=gm1; t=1663580092; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=FTjT3H9dRQ4Py29h7xNmS8jOx2MjJchYvwr78WhSyFM=; b=NGjSVv4yzgELBF+Hwi5rGY55EU1ErbgTi9tFcDmGr+3fr4TJ7qt6QkaByx1Vqi+mbcuoM2 lIa0IpzllBWDunmII2CxSHEUNWULU0FGaHrzMhflmKihwiW0bNDxINRXMTzDdIUMRavjtX uJp+gFC5uqR16RIRF9iepZDkr2dF84ufzgvDzAtPS91PUE+gK2fRwtZStatm6Ow6L6jU+k qBX3bBn6gFrMwwqWE8yZTgYH1MyZZ2BCagWkvZqbWdhymuE0hQfSE3kw+CafKf5Q3gikv4 tRxp3cNdlCFEJdn5F7L+xR7QOtJDs6dJ/jx5tHsWsjhF9KEksYksrV0EoI8H6A== Received: by localhost (Postfix, from userid 1001) id BFEB31A0BC9; Mon, 19 Sep 2022 11:34:51 +0200 (CEST) From: Dodji Seketeli To: Giuliano Procida Cc: Dodji Seketeli via Libabigail Subject: Re: [PATCH 2/2, RFC] Allow restricting analyzed decls to exported symbols Organization: Me, myself and I References: <871qsoke86.fsf@redhat.com> <87sfl4izh9.fsf@seketeli.org> X-Operating-System: Red Hat Enterprise Linux Server 7.9 X-URL: http://www.seketeli.net/~dodji Date: Mon, 19 Sep 2022 11:34:51 +0200 In-Reply-To: (Giuliano Procida's message of "Fri, 9 Sep 2022 14:03:49 +0100") Message-ID: <86zgevd7wk.fsf@seketeli.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-3.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,JMQ_SPF_NEUTRAL,RCVD_IN_DNSWL_LOW,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Hello, Giuliano Procida a =C3=A9crit: > Hi Dodji. > > Sorry for the late reply. I was down with Covid for a while. No problem. I hope you are doing fine now. [...] > My understanding is that the intention here is to make the DWARF > reader do less work (look at fewer type DIEs) than at present. I'd rather say, to make it do less unnecessary work by default. It first look at *interface* DIEs. And then it walks the graph of node to reach the type nodes that are connected. If it first encounters a type DIE, it ignores it. I will reach that DIE only if it's connected to an interface. > We are actually hoping that we may be able to make the DWARF reader > look at more type DIEs so that it is more likely to pick up full > definitions of types instead of declarations. If the definitions are not "used" by the interfaces, then by default, why bother, as far as ABI is concerned (not necessarily APIs)? But in any case, if you really want to look at type definitions even those that are not strictly connected to definitions, you still can. Just don't use the new option, I'd say. Said otherwise I don't think this change will inherently look at less actua= lly used type definitions. If it does, then it's a bug and it ought to be fixed. > > The rationale behind the change appears to be that DWARF processing is > expensive, in particular for kernel ABIs. I would say "measure first". I've profiledof the code and what I think I am seeing is that we are just looking at too many DIEs that incurs a lot of comparison at de-duplication (canonicalization) time. But I believe the heuristics I am using to speed up comparison can be improved. They are just taking me time. So I figured being able to avoid a significant number of comparisons to begin with was a somewhat lower hanging fruits, at least for me to be able to release 2.1. I'll keep on looking at ways to ameliorate the DIE canonicalization even more in the future, after 2.1. > Here's roughly how I think about things: > > 1. building the IR is very cheap Well, that's not what I see, when we have lots of DIEs that are built 'unnecessarily', and that would have to be compared to be de-duplicated. The reason why I am de-duplicating some types (not all of DIE kinds) at the DIE level is because I have seen over time that it significantly drops the size and time of de-duplication at the IR level. To see that for yourself, it's quite easy, I believe, to disable DIE de-duplication and run, says, "abidw --noout" on a sizeable binary. > A kernel ABI may end up with 40k IR elements. The cost of allocating > memory and calling constructors should be negligible. Any improvements > to this end of things is pointless. Again, you can just disable DIE canonicalization in the code and run abidw --noout on vmlinux to see for yourself how things degrade in practise. > 2. reading DWARF information is fairly cheap > > We may have 100MB of DWARF but just reading the data (decoding > attribute formats in particular) won't take that long. > > Reducing the number of DIEs examined at the top-level by a factor of 2 > will speed up this part by a factor of 2, but in the grand scheme of > things that may not be very important. Indeed. But I guess the gain might depends on the kind of nodes that got dropped. If the nodes are for types that participate in quadratic comparisons, then the gain might be higher. But I agree that all in all, what I am seeing is indeed a linear gain in general. It might not be very important in the grand scheme, but in practise, I'll take it :-) I understand though, that I still need to keep working on this to find ways to come up with better de-duplication schemes. That would be definitely for after 2.1 that I really want to see out now. It's overdue. > 3. chasing references is a bit more expensive > > Cross-references in DWARF are pretty common and the lack of locality > means that chasing cross-references is going to be a constant factor > slower than iterating through the main DWARF tree. > > 4. deciding whether a DIE needs to be turned into IR is currently very ex= pensive > > This is because it involves multiple look-ups and recursive comparison > of DIEs which cannot be unconditionally memoised. A.k.a de-duplication / canonicalization. > Those are only my thoughts. Some profiling should give a more accurate pi= cture. > > I was curious, so I did an analysis of the connectivity of a kernel > ABI (using the STG IR, not libabigail's - there are minor > differences). Here are some fun facts. > > The ABI has 34541 nodes. > There are 25196 strongly-connected components. > 25053 SCCs are just singleton nodes. > The largest 3 SCCs have sizes: 4960, 784, 343. > 1/7 of the ABI nodes are in one SCC! > > Completely idle speculation: Perhaps the really huge SCC contributes > significantly to comparison cost. I don't think we are saying different things. Thanks for the comments. [...] Cheers, --=20 Dodji