From patchwork Fri Jun 11 15:33:14 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43831 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 49A23398B150 for ; Fri, 11 Jun 2021 15:34:20 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 49A23398B150 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623425660; bh=8tX5oOTxgJNV/iMUmCtv5gRO64GPMVHM1X4pClyfsmM=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=GAntACuibtOdWxQwAwk/Zn8h8uM9eW8KetD4sOVIoJaueAPpZSZrt/L5gLb9l1QQp 4SgurShFxJz4KhJqLF/nM1+P9QDR87RrCNE76YJFW8cONnxhnk3tgCuoKvRP3AvDgz A7X3+oNPKPcuFVwiPpY+QDyBvKBGsie2w8XogTBE= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-wm1-x349.google.com (mail-wm1-x349.google.com [IPv6:2a00:1450:4864:20::349]) by sourceware.org (Postfix) with ESMTPS id E1FD038618BB for ; Fri, 11 Jun 2021 15:34:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E1FD038618BB Received: by mail-wm1-x349.google.com with SMTP id r4-20020a7bc0840000b02901b7cb5713ecso2432078wmh.1 for ; Fri, 11 Jun 2021 08:34:15 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=8tX5oOTxgJNV/iMUmCtv5gRO64GPMVHM1X4pClyfsmM=; b=o+f22j9x6YtRHHEuh69MaeMh1W/b4Q41kWWUmci4pTZZGeXscj6KadjZX0bNXApfTr TK0Hh3shF7qXaihbdx1HVrX0+7UGMLG3Mo8/+sT/QgBBsyF/ZV0baFdNLxRLymsLnd7T o772X8TBYH6wTYFfamH9dyFEs0lfvRbvbaBJkZEEv3NOisW9PCA/cSycG2hush1fd6V1 /t3A3ATz/4BFo4c/JWgkjTmgX+bVowmx0FfLW53ALENQmWzwF4PiTfM/EqGq1bP6fVoH 4kTUbGCbeRkQ175DO8hUXqwqrE2r9i0lly31YcK2YtKbN1N2tN/YcaPgaH/o1PfqI645 GoAg== X-Gm-Message-State: AOAM5319sdY5xFvsRJGSvCFeqvhHSB02X2kahyUvwHN8lGoCDkv0/gtQ K0czGYnQ2RwfhfL6b2Ko0ELMhiBOckfvUGsJHv+BGhTJfxHFPcP8/iuH63R3nNF0Zr1B110GlcC QB0UNq67+BOhs6sJpwz0Hz9ztR01g0IPHqvrakHd2OluP1nVpwCVgUtQBTvebsbvCj29ayzA= X-Google-Smtp-Source: ABdhPJzw1Sf6Tgqlz+9ic2WbTf6THr4JHnFT0hRANrB9vReMdFxRvfW4U2WuLLc9qFqgGE56me4Q8/oZVGDrTQ== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:c264:c1f9:cf3c:2c0b]) (user=gprocida job=sendgmr) by 2002:a1c:1b4c:: with SMTP id b73mr20590785wmb.57.1623425654823; Fri, 11 Jun 2021 08:34:14 -0700 (PDT) Date: Fri, 11 Jun 2021 16:33:14 +0100 In-Reply-To: <20210611153319.778996-1-gprocida@google.com> Message-Id: <20210611153319.778996-2-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.272.g935e593368-goog Subject: [PATCH 1/6] Tweak clang-format To: libabigail@sourceware.org X-Spam-Status: No, score=-22.8 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-Patchwork-Original-From: Giuliano Procida via Libabigail From: Giuliano Procida Reply-To: Giuliano Procida Cc: maennich@google.com, kernel-team@android.com, teguiani@android.com Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" The BTF / SCC code is being migrated out of Google source control into AOSP. This comes with the opportunity to migrate the style to be closer libabigail's. In the first instance it makes sense to just reformat it with clang-format. I've updated this as follows. AlignConsecutiveDeclarations: false - as this is closer on average to libgabigail code and looks nicer for the new code anyway AllowShort*: (true) - these in theory should make things closer to libabigail style but in practice don't appear make any difference Cpp11BracedListStyle: true - this seems to improve some initialiser syntax BinPackArguments: false - we already turn this off for parameters SpaceAfterCStyleCast: true - seems to be the libabigail style * .clang-format: Various tweaks for new BTF code. Signed-off-by: Giuliano Procida --- .clang-format | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/.clang-format b/.clang-format index 1b422dfb..d09d739a 100644 --- a/.clang-format +++ b/.clang-format @@ -2,17 +2,24 @@ --- BasedOnStyle: GNU Standard: c++11 -AlignConsecutiveDeclarations: true +AlignConsecutiveDeclarations: false +AllowShortBlocksOnASingleLine: Always +AllowShortEnumsOnASingleLine: true +AllowShortFunctionsOnASingleLine: All +AllowShortLambdasOnASingleLine: All AlwaysBreakAfterReturnType: All BreakConstructorInitializers: BeforeColon ConstructorInitializerAllOnOneLineOrOnePerLine: true ConstructorInitializerIndentWidth: 2 +Cpp11BracedListStyle: true IndentWidth: 2 AlignAfterOpenBracket: Align +BinPackArguments: false BinPackParameters: false BreakStringLiterals: false PointerAlignment: Left SortUsingDeclarations: false +SpaceAfterCStyleCast: true SpaceBeforeParens: ControlStatements TabWidth: 8 UseTab: Always From patchwork Fri Jun 11 15:33:15 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43833 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 596A3398B17A for ; Fri, 11 Jun 2021 15:34:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 596A3398B17A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623425665; bh=VzAEt5kTgidTC8RHyXSLOz3CZEklU0u4F41awZqEx4U=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=cC2ipCoiF54pslkMsO/6qG08YpeWukMJQo2Y3DroeV6nq4h0ngcc28hygyy+QTwzu +pXojaL+yqe/HM1QYqlKkQgf6P4H/qQ9T6UyhAWjKotfoiNupkR4KP/LPO1Sz+KWmz wTe+ij2TTGK+fXw3ZarOxCP1eu4IhyCqNojMOWIc= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-qt1-x84a.google.com (mail-qt1-x84a.google.com [IPv6:2607:f8b0:4864:20::84a]) by sourceware.org (Postfix) with ESMTPS id 5D1BA38618BB for ; Fri, 11 Jun 2021 15:34:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5D1BA38618BB Received: by mail-qt1-x84a.google.com with SMTP id r3-20020a05622a0343b029024761fabab8so2132487qtw.11 for ; Fri, 11 Jun 2021 08:34:17 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=VzAEt5kTgidTC8RHyXSLOz3CZEklU0u4F41awZqEx4U=; b=qNG/qXe7gg6/92eiOGF1knD/mG7pzFLUJ2fUhrujZpW5bfVmAqEgaEomjDiVc9rWyG uSuykBpV4KhI2m2w6WOBawwxAs0/6WtLLMaYCNpFyFwedhT8lReYQ8SN0BZRg061g7UH gVy1kCdrSwmIO3QpwAz4PyqEZA6Wy/XG/TASAonrSI+merVZGMxo+yUxaf3k+rW3s+C/ jywOCaJVGe8z2LUyKHgKjjbX5gw1JcgiJfzJZsowQJWJPu7ekNPhUlTLrjpCGFLhSQVG Idip3be12KiGQneIFHlsRDSuwhIqDG/9YdcbY7J8njrlR4bxLPWm8qbXgO6QXa89ViTG vbxg== X-Gm-Message-State: AOAM5329aDwBOY6d7GXQOp+fgVU8g4Poqr9tStUe9aBvbnz2vJz7bzRw X2AktTk8AagHQJNuAjxxvAwAba56WX5juyk7IcuVExTp1Rtc5HZ9b/1HfhRKMW3398B4uZ21fjV My4dJmH3XXomjRlROYSO91/tbIxfbRqf074PXRh+p/XV/29IQ/9TuU5FUEmQY0Qs5x4XxbzI= X-Google-Smtp-Source: ABdhPJy917VmAsd6YeAivHFPMuZ6LUQRbTKvUlXd/maPsH/sXFhbHJxVEfiRXeWzRG+bF4ymSp2aZD7sTQdXBw== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:c264:c1f9:cf3c:2c0b]) (user=gprocida job=sendgmr) by 2002:ad4:5309:: with SMTP id y9mr5400919qvr.31.1623425656833; Fri, 11 Jun 2021 08:34:16 -0700 (PDT) Date: Fri, 11 Jun 2021 16:33:15 +0100 In-Reply-To: <20210611153319.778996-1-gprocida@google.com> Message-Id: <20210611153319.778996-3-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.272.g935e593368-goog Subject: [PATCH 2/6] Allow C++17 code to be compiled To: libabigail@sourceware.org X-Spam-Status: No, score=-22.3 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-Patchwork-Original-From: Giuliano Procida via Libabigail From: Giuliano Procida Reply-To: Giuliano Procida Cc: maennich@google.com, kernel-team@android.com, teguiani@android.com Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" The BTF code was developed in a C++17 environment. To ease integration here, allow C++17 to be enabled at configuration time. * configure.ac: Add --enable-cxx17 option defaulting to no. Signed-off-by: Giuliano Procida --- configure.ac | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) diff --git a/configure.ac b/configure.ac index 735cc9de..edd03cf8 100644 --- a/configure.ac +++ b/configure.ac @@ -138,6 +138,12 @@ AC_ARG_ENABLE(ubsan, ENABLE_UBSAN=$enableval, ENABLE_UBSAN=no) +AC_ARG_ENABLE(cxx17, + AS_HELP_STRING([--enable-cxx17=yes|no], + [enable features that use the C++17 compiler]), + ENABLE_CXX17=$enableval, + ENABLE_CXX17=no) + dnl ************************************************* dnl check for dependencies dnl ************************************************* @@ -153,7 +159,7 @@ AC_LANG([C++]) AC_LANG_COMPILER_REQUIRE dnl -dnl We use C++11 +dnl We use C++11 or C++17 if enabled dnl CXX_STANDARD=c++11 @@ -591,6 +597,12 @@ AX_VALGRIND_DFLT(sgcheck, off) AX_VALGRIND_CHECK +dnl Handle conditional use of a C++17 compiler +if test x$ENABLE_CXX17 = xyes; then + CXX_STANDARD=c++17 +fi +AM_CONDITIONAL(ENABLE_CXX17, test x$ENABLE_CXX17 = xyes) + dnl Set the list of libraries libabigail depends on DEPS_LIBS="$XML_LIBS $ELF_LIBS $DW_LIBS" From patchwork Fri Jun 11 15:33:16 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43834 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DB33A38515E7 for ; Fri, 11 Jun 2021 15:34:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DB33A38515E7 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623425667; bh=AppFbIGceq/7qgWRXZpcEsZGbclnV4KoLQEA1L+OJMY=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=n19+3S9cR0q8X+GGPfoEhxrOW3uPiHwgxjo2nxzHDJKU+Lxw90gmiZDEBOY/wUJpn zdmQmVMr/5wMJHEMbsk0o3cOn7GMMFR5Kh7Egb+WgdmlLGwsT9oPNMnOBiMwEAF+Jc DoY5mSbh9CF64iqqN6PV2E/FBW0jgB/USQOaurig= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-yb1-xb49.google.com (mail-yb1-xb49.google.com [IPv6:2607:f8b0:4864:20::b49]) by sourceware.org (Postfix) with ESMTPS id 8770C398B17A for ; Fri, 11 Jun 2021 15:34:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8770C398B17A Received: by mail-yb1-xb49.google.com with SMTP id g9-20020a25ae490000b029052f9e5b7d3fso4454476ybe.4 for ; Fri, 11 Jun 2021 08:34:19 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=AppFbIGceq/7qgWRXZpcEsZGbclnV4KoLQEA1L+OJMY=; b=JUnkTRv6ed96sJMOWaN2VzWZHiN6v6eR0nBn05I293OLSkZL4iMICnqB8QOUG1n8L+ L6ukIXlRncjOhtdSEXipFBIIHKOcU2nzs5DZrE/7VIiDTGNQ4FWFGsc4Ty7cQxVFufxZ BMwnlCnPGzLcMqqy6ORhkWES8V8W+fzpw27yp3octXCuMTNUrAlfSUjsUbz5Gcsj8qgx 7i0vCtYU4nwzYa+GP36rr8FiUSyPETWQASjdquSrkd9a8cQ0q07jJ373xcISKuSX1tu/ DcP659WrDboJf/GAzuBDhro0zSFuXxQIBt1/2wYj/v78+YD5O3w64yzf2HS3m/EyATUl P7gQ== X-Gm-Message-State: AOAM531yzqYb32TpmjyXzpDhplgnyXXr8ZJj901b7oVh0m9pLpxSF+Bq M1fvQoWupLZvTnSkkIzh622vuE8OgTMjkLW7xJNp2weUj1SMf38wZAXSwSHQe0iCzIzJV1A10xs 76P1ZC1rQ+iq1erMWBy72GuJQ/idRl0Iwlqmd1jlcQ99COjtr/r1Vk27aFi0oFy9zVnLg/Vs= X-Google-Smtp-Source: ABdhPJwt6jDP43IZKA5wHBBFWvamZbfsIxqmG/fr3xa+Ng7Mos42s9Xe+tzQi5iJpXqvqSZvHzxJ8/oZ3Lac+w== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:c264:c1f9:cf3c:2c0b]) (user=gprocida job=sendgmr) by 2002:a25:5383:: with SMTP id h125mr6478473ybb.463.1623425659003; Fri, 11 Jun 2021 08:34:19 -0700 (PDT) Date: Fri, 11 Jun 2021 16:33:16 +0100 In-Reply-To: <20210611153319.778996-1-gprocida@google.com> Message-Id: <20210611153319.778996-4-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.272.g935e593368-goog Subject: [PATCH 3/6] BTF: add SCC finder and test To: libabigail@sourceware.org X-Spam-Status: No, score=-22.8 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-Patchwork-Original-From: Giuliano Procida via Libabigail From: Giuliano Procida Reply-To: Giuliano Procida Cc: maennich@google.com, kernel-team@android.com, teguiani@android.com Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" The files are almost a straight copy of the originals. Changes: - Files renamed and #includes updated. - Header guards and include order are now in libabigail style. * include/abg-scc.h (SCC): New class to find SCCs. * tests/test-scc.cc: SCC test with randomly-generated graphs. * tests/Makefile.am: Add SCC test, conditional on C++17. Signed-off-by: Giuliano Procida --- include/abg-scc.h | 111 ++++++++++++++++++++++++++++ tests/Makefile.am | 7 ++ tests/test-scc.cc | 183 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 301 insertions(+) create mode 100644 include/abg-scc.h create mode 100644 tests/test-scc.cc diff --git a/include/abg-scc.h b/include/abg-scc.h new file mode 100644 index 00000000..d60b1aed --- /dev/null +++ b/include/abg-scc.h @@ -0,0 +1,111 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020 Google, Inc. +// +// Author: Giuliano Procida + +#ifndef __ABG_SCC_H__ +#define __ABG_SCC_H__ + +#include +#include +#include +#include +#include + +namespace abigail { + +/* + * This is a streamlined Strongly-Connected Component finder for use with + * procedurally generated or explored graphs, where the nodes and edges are not + * known a priori. + * + * REQUIREMENTS + * + * The Node type must be copyable and the user must supply a well-behaved + * comparison function (allowing arbitrary data to accompany each node). + * + * The user code must take the form of a Depth First Search which can be + * repeatedly invoked on unvisited nodes until the whole graph has been + * traversed. + * + * The user code must ensure that nodes are not revisited once they have been + * assigned to an SCC. The finder does not maintain any state for such nodes. + * + * GUARANTEES + * + * Each node will be examined exactly once. + * + * The SCCs will be presented in a topological order, leaves first. + * + * Note that within each SCC, nodes will be presented in DFS traversal order, + * roots first. However, this is just an implemention detail, not a guarantee. + * + * USAGE + * + * Before examining a node, check it's not been visited already and then call + * Open. If the node is already "open" (i.e., is already waiting to be assigned + * to an SCC), this will return an empty optional value and the node should not + * be examined. If Open succeeds, a numerical node handle will be returned and + * the node will be recorded as waiting to be assigned to an SCC. + * + * Now examine the node, making recursive calls to follow edges to other nodes. + * + * Once the examination is done, call Close, passing in the handle and + * optionally a function to update data associated with the node. If the node + * has been identified as the "root" of an SCC, the whole SCC will be returned + * as a vector of nodes. If any processing needs to be done (such as recording + * the nodes as visited), this should be done now. Otherwise, an empty vector + * will be returned. + */ +template class SCC { + public: + explicit SCC(std::function cmp) : cmp_(cmp) + {} + ~SCC() { + assert(open_.empty()); + assert(root_index_.empty()); + } + + std::optional Open(const Node &node) { + for (size_t ix = 0; ix < open_.size(); ++ix) { + const auto &other = open_[ix]; + // node == other? + if (!cmp_(node, other) && !cmp_(other, node)) { + // Pop indices to nodes which cannot be the root of their SCC. + while (root_index_.back() > ix) + root_index_.pop_back(); + return {}; + } + } + // Unvisited, mark node as open and record root index. + auto ix = open_.size(); + open_.push_back(node); + root_index_.push_back(ix); + return ix; + } + + std::vector Close( + size_t ix, std::function update = [](Node &){}) { + std::vector scc; + assert(ix < open_.size()); + update(open_[ix]); + if (ix == root_index_.back()) { + // Close SCC. + root_index_.pop_back(); + std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); + open_.resize(ix); + } + return scc; + } + + private: + std::function cmp_; + std::vector open_; + std::vector root_index_; +}; + +} // namespace abigail + +#endif // __ABG_SCC_H__ diff --git a/tests/Makefile.am b/tests/Makefile.am index 7a3a1f98..95df9542 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -53,6 +53,10 @@ else TESTS += runtestdefaultsupprs.py endif +if ENABLE_CXX17 +TESTS += runtestscc +endif + EXTRA_DIST = \ runtestcanonicalizetypes.sh.in \ runtestfedabipkgdiff.py.in \ @@ -166,6 +170,9 @@ testdiff2_LDADD=$(top_builddir)/src/libabigail.la printdifftree_SOURCES = print-diff-tree.cc printdifftree_LDADD = $(top_builddir)/src/libabigail.la +runtestscc_SOURCES = test-scc.cc +runtestscc_LDADD = libcatch.la + runtestslowselfcompare_sh_SOURCES = runtestslowselfcompare.sh$(EXEEXT): diff --git a/tests/test-scc.cc b/tests/test-scc.cc new file mode 100644 index 00000000..ccabb471 --- /dev/null +++ b/tests/test-scc.cc @@ -0,0 +1,183 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020 Google, Inc. +// +// Author: Giuliano Procida + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "lib/catch.hpp" + +#include "abg-scc.h" + +namespace Test { + +using abigail::SCC; + +// Nodes are [0, N), the sets are the out-edges. +typedef std::vector> Graph; + +std::ostream &operator<<(std::ostream &os, const Graph &g) { + for (size_t i = 0; i < g.size(); ++i) { + os << i << ':'; + for (auto o : g[i]) + os << ' ' << o; + os << '\n'; + } + return os; +} + +template Graph invent(size_t n, G& gen) { + Graph graph(n); + std::uniform_int_distribution toss(0, 1); + for (auto &node : graph) { + for (size_t o = 0; o < n; ++o) { + if (toss(gen)) + node.insert(o); + } + } + return graph; +} + +// Generate a graph g' where a -> b iff a and b are strongly connected in g. +Graph symmetric_subset_of_reflexive_transitive_closure(Graph g) { + const size_t n = g.size(); + // transitive closure using Floyd-Warshall + for (size_t o = 0; o < n; ++o) + g[o].insert(o); + for (size_t k = 0; k < n; ++k) { + for (size_t i = 0; i < n; ++i) { + for (size_t j = 0; j < n; ++j) { + if (!g[i].count(j) && g[i].count(k) && g[k].count(j)) + g[i].insert(j); + } + } + } + // now a -> b iff a has path to b in g + for (size_t i = 0; i < n; ++i) { + for (size_t j = i + 1; j < n; ++j) { + // discard a -> b if not b -> a and vice versa + auto ij = g[i].count(j); + auto ji = g[j].count(i); + if (ij < ji) g[j].erase(i); + if (ji < ij) g[i].erase(j); + } + } + // now have a -> b iff a has path to b and b has path to a in g + return g; +} + +// Generate a graph where a -> b iff a and b are in the same SCC. +Graph scc_strong_connectivity(const std::vector> &sccs) { + size_t n = 0; + std::map *> edges; + for (const auto &scc : sccs) { + for (auto o : scc) { + if (o >= n) + n = o + 1; + edges[o] = &scc; + } + } + Graph g(n); + for (size_t o = 0; o < n; ++o) + g[o] = *edges[o]; + return g; +} + +void dfs(std::set &visited, SCC &scc, + const Graph &g, size_t node, + std::vector> &sccs) { + if (visited.count(node)) + return; + auto handle = scc.Open(node); + if (!handle) + return; + for (auto o : g[node]) + dfs(visited, scc, g, o, sccs); + auto nodes = scc.Close(handle.value()); + if (!nodes.empty()) { + std::set scc_set; + for (auto o : nodes) { + CHECK(visited.insert(o).second); + CHECK(scc_set.insert(o).second); + } + sccs.push_back(scc_set); + } +} + +void process(const Graph &g) { + const size_t n = g.size(); + + // find SCCs + std::set visited; + SCC scc{std::less()}; + std::vector> sccs; + for (size_t o = 0; o < n; ++o) + dfs(visited, scc, g, o, sccs); + + // check partition and topological order properties + std::set seen; + for (const auto &nodes : sccs) { + CHECK(!nodes.empty()); + for (auto node : nodes) { + // value in range [0, n) + CHECK(node < n); + // value seen at most once + CHECK(seen.insert(node).second); + } + for (auto node : nodes) { + for (auto o : g[node]) { + // edges point to nodes in this or earlier SCCs + CHECK(seen.count(o)); + } + } + } + // exactly n values seen + CHECK(seen.size() == n); + + // check strong connectivity + auto g_scc_closure = scc_strong_connectivity(sccs); + auto g_closure = symmetric_subset_of_reflexive_transitive_closure(g); + // catch isn't printing nicely + if (g_scc_closure != g_closure) { + std::cerr << "original:\n" << g + << "SCC finder:\n" << g_scc_closure + << "SCCs independently:\n" << g_closure; + } + CHECK(g_scc_closure == g_closure); +} + +TEST_CASE("randomly-generated graphs") { + std::mt19937 gen; + auto seed = gen(); + // NOTES: + // Graphs of size 6 are plenty big enough to shake out bugs. + // There are O(2^k^2) possible directed graphs of size k. + // Testing costs are O(k^3) so we restrict accordingly. + uint64_t budget = 10000; + for (size_t k = 0; k < 7; ++k) { + uint64_t count = std::min(static_cast(1) << (k*k), + budget / (k ? k * k * k : 1)); + INFO("testing with " << count << " graphs of size " << k); + for (uint64_t n = 0; n < count; ++n, ++seed) { + gen.seed(seed); + Graph g = invent(k, gen); + std::ostringstream os; + os << "a graph of " << k << " nodes generated using seed " << seed; + GIVEN(os.str()) { + process(g); + } + } + } +} + +} // namespace Test From patchwork Fri Jun 11 15:33:17 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43836 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 999803988408 for ; Fri, 11 Jun 2021 15:34:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 999803988408 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623425673; bh=p8mcokSbbopDlaxzeaTeN1RQdO41PUBIGX855WPf4RQ=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=gBF2L517U4EPLO7VBRgjHc4Zph5x1HBrMAWR3qo9RBuvYstuPgTmx4XowO01oicSE 9kyDOVAX232D4rlCQVioJTltmj+p1zjqfZtmHmB+BYzbuBbwldmsYzyaybNoem05aC 8ZnrW5+GkmWgo9lXDxWTujUl5mTVrK4YPbBIWrE0= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-qt1-x849.google.com (mail-qt1-x849.google.com [IPv6:2607:f8b0:4864:20::849]) by sourceware.org (Postfix) with ESMTPS id D45293985477 for ; Fri, 11 Jun 2021 15:34:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D45293985477 Received: by mail-qt1-x849.google.com with SMTP id l6-20020ac84cc60000b0290243ab0e481cso2153850qtv.2 for ; Fri, 11 Jun 2021 08:34:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=p8mcokSbbopDlaxzeaTeN1RQdO41PUBIGX855WPf4RQ=; b=CLMNrTk4WOjxa/Bzd/kjYeeyb1FHCScfvgxpVlOBbhv2FDzJkNPp+Y8+aGnm84yU89 OEgAhgmd8h8K6rjDNt31noCltTEzS/GbZ0Rtthp090ktg6/2AEzMAfXIxkLEcVLVMS5u bmo2CC4fZOcLemgk6fxORxWlvVH+FtJ4DHwmh+jW4E8/2DealuOIrefHmS+IqaT1ucKO jmYJ4+3BA/MBHiWpP4U+F6lRVbvQnM58edip3qb814VpgWYQVOmpbvC7esXCrSot9KTU J0N9j0FsWaFelc396qiMMRMJrp6XFCJn2sa080LNLH9uz5bCGK1rfHF/plCikuSP3T17 4szQ== X-Gm-Message-State: AOAM533zlmlock/NekmI2khOQm6QNlwPQ1Le0U2i65lMogknhJ9ghZi1 9wXPrKEMWCr4UGc5EfXmhA1kLdJjd4kALXVPHkQ5uoBNJQgpmbmGC6O76hx1Bl9uh4RVp4R8lcf Yla+o72ssWE10gFKuGQsibFC3yyuU1YTBHtE1+qOrVFTi8zCV9HiBcZfljOSCe5vx6nx31IU= X-Google-Smtp-Source: ABdhPJzR7jpw6zMC3Kr29dw/93m9pS8AyGCqyjQ4L8aSwnuDjr30cQ6golzQ/uo8dAZn8Rz67K2a65FzylX0mw== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:c264:c1f9:cf3c:2c0b]) (user=gprocida job=sendgmr) by 2002:a05:6214:1514:: with SMTP id e20mr5293251qvy.55.1623425661387; Fri, 11 Jun 2021 08:34:21 -0700 (PDT) Date: Fri, 11 Jun 2021 16:33:17 +0100 In-Reply-To: <20210611153319.778996-1-gprocida@google.com> Message-Id: <20210611153319.778996-5-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.272.g935e593368-goog Subject: [PATCH 4/6] BTF: add core functionality To: libabigail@sourceware.org X-Spam-Status: No, score=-22.0 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-Patchwork-Original-From: Giuliano Procida via Libabigail From: Giuliano Procida Reply-To: Giuliano Procida Cc: teguiani@android.com, maennich@google.com, Maria Teguiani , kernel-team@android.com Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" This commit adds core BTF functionality. The code can: - read ELF symbols using the symtab_reader - read BTF into a graph of type and symbol information - optionally perform a text dump of BTF as it's read - compute diffs between two BTF graphs as a diff graph - done using DFS and with the help of the SCC finder - create and cache full names for types - serialise a diff graph as a textual diff report - done using DFS The files are almost a straight copy of the originals. Changes: - Files renamed and #includes updated. - Header guards and include order are now in libabigail style. * COMPILING: Add note about BTF dependency. * configure.ac: Add check for . * src/Makefile.am: Add abg-btf.cc, conditional on C++17 and presence of . * include/abg-btf.h: New file. * src/abg-btf.cc: New file. Co-authored-by: Maria Teguiani Signed-off-by: Giuliano Procida --- COMPILING | 5 + configure.ac | 7 + include/abg-btf.h | 551 ++++++++++++++++++ src/Makefile.am | 9 +- src/abg-btf.cc | 1364 +++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 1935 insertions(+), 1 deletion(-) create mode 100644 include/abg-btf.h create mode 100644 src/abg-btf.cc diff --git a/COMPILING b/COMPILING index 33613a37..75a6588a 100644 --- a/COMPILING +++ b/COMPILING @@ -5,6 +5,11 @@ the moment the dependencies are the following Free Software packages: libtool libxml2 +To build the BTF tools, you will need which can be found +in the development package of: + + linux-libc + If you are building from the Git repository, then you'd also need the following packages: diff --git a/configure.ac b/configure.ac index edd03cf8..d9125d99 100644 --- a/configure.ac +++ b/configure.ac @@ -603,6 +603,13 @@ if test x$ENABLE_CXX17 = xyes; then fi AM_CONDITIONAL(ENABLE_CXX17, test x$ENABLE_CXX17 = xyes) +dnl Check for the presence of the BTF header. +HAVE_BTF=no +AC_CHECK_HEADER([linux/btf.h], + [HAVE_BTF=yes], + [AC_MSG_NOTICE([No linux/btf.h found, omitted BTF support.])]) +AM_CONDITIONAL(HAVE_BTF, test x$HAVE_BTF = xyes) + dnl Set the list of libraries libabigail depends on DEPS_LIBS="$XML_LIBS $ELF_LIBS $DW_LIBS" diff --git a/include/abg-btf.h b/include/abg-btf.h new file mode 100644 index 00000000..d47b4ac9 --- /dev/null +++ b/include/abg-btf.h @@ -0,0 +1,551 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020-2021 Google, Inc. +// +// Author: Maria Teguiani +// Author: Giuliano Procida + +#ifndef __ABG_BTF_H__ +#define __ABG_BTF_H__ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "abg-ir.h" +#include "abg-scc.h" + +namespace abigail { +namespace btf { + +#define m_assert(expr, msg) assert(((void)(msg), (expr))) + +using Kind = uint32_t; + +// A Member refers to a data element of a struct or union, used in the context +// of StructUnion +struct Member { + uint32_t typeId_; + uint32_t offset_; + uint32_t bitfieldSize_; +}; + +// A Parameter refers to a variable declared in the function declaration, used +// in the context of Function +struct Parameter { + std::string name_; + uint32_t typeId_; +}; + +struct Secinfo { + uint32_t typeId_; + uint32_t offset_; + uint32_t bytesize_; +}; + +enum class ForwardDeclarationKind { STRUCT, UNION }; + +std::ostream &operator<<(std::ostream &os, ForwardDeclarationKind kind); + +class Type; + +using Comparison = std::pair; + +enum class Precedence { NIL, POINTER, ARRAY_FUNCTION, ATOMIC }; +enum class Side { LEFT, RIGHT }; + +class Name { + public: + explicit Name(std::string_view name) + : left_(name), precedence_(Precedence::NIL), right_() {} + Name(std::string_view left, Precedence precedence, std::string_view right) + : left_(left), precedence_(precedence), right_(right) {} + Name Add(Side side, Precedence precedence, std::string_view text) const; + Name Qualify(const std::set &qualifiers) const; + std::ostream &Print(std::ostream &os) const; + + private: + std::string left_; + Precedence precedence_; + std::string right_; +}; + +std::ostream &operator<<(std::ostream &os, const Name &name); + +using NameCache = std::unordered_map; + +struct DiffDetail { + DiffDetail(const std::string &text, const std::optional &edge) + : text_(text), edge_(edge) {} + std::string text_; + std::optional edge_; +}; + +using Diff = std::vector; + +struct Result { + void AddDiff(const std::string &text) { + equals_ = false; + details_.emplace_back(text, std::optional()); + } + + void AddDiff(const std::string &text, Comparison comparison) { + equals_ = false; + details_.emplace_back(text, comparison); + } + + void MaybeAddDiff(const std::string &text, + const std::pair> &p) { + equals_ &= p.first; + const auto &diff = p.second; + if (diff) + details_.emplace_back(text, diff); + } + + // Maximally powerful lazy version, takes a function that outputs an "edge" + // diff description, to be used only when a diff is present. + void MaybeAddDiff(std::function text, + const std::pair> &p) { + equals_ &= p.first; + const auto &diff = p.second; + if (diff) { + std::ostringstream os; + text(os); + details_.emplace_back(os.str(), diff); + } + } + + template void MaybeAddDiff( + const std::string &text, const T &before, const T &after) { + if (before != after) { + equals_ = false; + std::ostringstream os; + os << text << " changed from " << before << " to " << after; + AddDiff(os.str()); + } + } + + // Lazy version. + template void MaybeAddDiff( + std::function text, + const T &before, const T &after) { + if (before != after) { + equals_ = false; + std::ostringstream os; + text(os); + os << " changed from " << before << " to " << after; + AddDiff(os.str()); + } + } + + bool equals_ = true; + Diff details_; +}; + +using Outcomes = std::map; +// unvisited (absent) -> started (false) -> finished (true) +using Seen = std::map; + +void Print(const Comparison &comparison, const Outcomes &outcomes, Seen &seen, + NameCache &names, std::ostream &os, size_t indent = 0); + +void Print(const Diff &details, const Outcomes &outcomes, Seen &seen, + NameCache &names, std::ostream &os, size_t indent = 0); + +class Type { + public: + Type(const std::vector> &types, uint32_t index, + std::string_view name, Kind kind) + : types_(types), index_(index), name_(name), kind_(kind) {} + virtual ~Type() = default; + uint32_t GetIndex() const { return index_; } + std::string_view GetName() const { return name_; } + Kind GetKind() const { return kind_; } + const std::vector> &GetTypes() const { + return types_; + } + + // as() provides a method to defer downcasting to the base class, + // instead of needing to use dynamic_cast in a local context. If the type is + // not correct, the assert will trigger in debug mode. In release mode, this + // will crash dereferencing the nullptr. + template + const Target &as() const { + static_assert(std::is_convertible::value, + "Target must publically inherit Type"); + const Target *t = dynamic_cast(this); + m_assert(t, "Invalid downcast"); + return *t; + } + // Separate qualifiers from underlying type. + // + // The caller must always be prepared to receive a different type as + // qualifiers are sometimes discarded. + virtual const Type &ResolveQualifiers(std::set &qualifiers) const; + virtual const Type &ResolveTypedef( + std::vector &typedefs) const; + + const Name &GetDescription(NameCache &names) const; + static Result CompareSymbols( + const std::map &lhs, + const std::map &rhs, + Outcomes &outcomes); + + protected: + struct State { + explicit State(Outcomes &o) : outcomes(o), scc(o.value_comp()) { } + Outcomes &outcomes; + std::set known_equal; + SCC scc; + }; + const Type &GetTypeAtIndex(size_t index) const; + + virtual Name MakeDescription(NameCache &names) const = 0; + virtual Result Equals(const Type &other, State &state) const = 0; + static Comparison Removed(const Type &lhs, State &state); + static Comparison Added(const Type &rhs, State &state); + static std::pair> Compare( + const Type &lhs, const Type &rhs, State &state); + + private: + static std::string GetDiffMessage(NameCache &names, + const Type &lhs, const Type &rhs, + const std::string &message = std::string()); + const std::vector> &types_; + const uint32_t index_; + const std::string name_; + const Kind kind_; +}; + +class Void : public Type { + public: + Void(const std::vector> &types, uint32_t index, + std::string_view name, Kind kind) + : Type(types, index, name, kind) {} + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; +}; + +class Ptr : public Type { + public: + Ptr(const std::vector> &types, uint32_t index, + std::string_view name, Kind kind, uint32_t pointeeTypeId) + : Type(types, index, name, kind), + pointeeTypeId_(pointeeTypeId) {} + uint32_t GetPointeeTypeId() const { return pointeeTypeId_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t pointeeTypeId_; +}; + +class Typedef : public Type { + public: + Typedef(const std::vector> &types, uint32_t index, + std::string_view name, Kind kind, uint32_t referredTypeId) + : Type(types, index, name, kind), + referredTypeId_(referredTypeId) {} + uint32_t GetReferredTypeId() const { return referredTypeId_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + const Type &ResolveTypedef( + std::vector &typedefs) const final; + + private: + const uint32_t referredTypeId_; +}; + +class Qualifier : public Type { + public: + Qualifier(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + uint32_t qualifiedTypeId) + : Type(types, index, name, kind), + qualifiedTypeId_(qualifiedTypeId) {} + uint32_t GetQualifiedTypeId() const { return qualifiedTypeId_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + const Type &ResolveQualifiers(std::set &qualifiers) const final; + + private: + const uint32_t qualifiedTypeId_; +}; + +class Integer : public Type { + public: + Integer(const std::vector> &types, uint32_t index, + std::string_view name, Kind kind, uint32_t encoding, + uint32_t offset, uint32_t bitsize, uint32_t bytesize) + : Type(types, index, name, kind), + offset_(offset), + bitsize_(bitsize), + bytesize_(bytesize), + isBool_(encoding & BTF_INT_BOOL), + isSigned_(encoding & BTF_INT_SIGNED), + isChar_(encoding & BTF_INT_CHAR) {} + bool isBool() const { return isBool_; } + bool isSigned() const { return isSigned_; } + bool isChar() const { return isChar_; } + uint32_t GetOffset() const { return offset_; } + + // GetBitSize() gives the semantics of the field. GetByteSize() gives the + // storage size, and is equal or greater than GetBitSize()*8 + uint32_t GetBitSize() const { return bitsize_; } + uint32_t GetByteSize() const { return bytesize_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t offset_; + const uint32_t bitsize_; + const uint32_t bytesize_; + const bool isBool_; + const bool isSigned_; + const bool isChar_; +}; + +class Array : public Type { + public: + Array(const std::vector> &types, uint32_t index, + std::string_view name, Kind kind, uint32_t elementTypeId, + uint32_t indexTypeId, uint32_t numOfElements) + : Type(types, index, name, kind), + elementTypeId_(elementTypeId), + indexTypeId_(indexTypeId), + numOfElements_(numOfElements) {} + uint32_t GetElementTypeId() const { return elementTypeId_; } + uint32_t GetIndexTypeId() const { return indexTypeId_; } + uint32_t GetNumberOfElements() const { return numOfElements_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t elementTypeId_; + const uint32_t indexTypeId_; + const uint32_t numOfElements_; +}; + +class StructUnion : public Type { + public: + StructUnion(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + uint32_t bytesize, std::map members) + : Type(types, index, name, kind), + bytesize_(bytesize), + members_(members) {} + uint32_t GetByteSize() const { return bytesize_; } + const std::map &GetMembers() const { return members_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t bytesize_; + const std::map members_; +}; + +class Enumeration : public Type { + public: + Enumeration(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + uint32_t bytesize, std::map enumerators) + : Type(types, index, name, kind), + bytesize_(bytesize), + enumerators_(enumerators) {} + uint32_t GetByteSize() const { return bytesize_; } + const std::map &GetEnums() const { return enumerators_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t bytesize_; + const std::map enumerators_; +}; + +// BTF only considers structs and unions as forward-declared types, and does not +// include forward-declared enums. They are treated as BTF_KIND_ENUMs with vlen +// set to zero +class ForwardDeclaration : public Type { + public: + ForwardDeclaration(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + bool isUnion) + : Type(types, index, name, kind), + fwdKind_(isUnion ? ForwardDeclarationKind::UNION + : ForwardDeclarationKind::STRUCT) {} + ForwardDeclarationKind GetFwdKind() const { return fwdKind_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const ForwardDeclarationKind fwdKind_; +}; + +class Function : public Type { + public: + enum class Linkage : uint16_t { STATIC, GLOBAL, EXTERN }; + Function(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + uint32_t referredTypeId, Linkage linkage) + : Type(types, index, name, kind), + referredTypeId_(referredTypeId), + linkage_(linkage) {} + uint32_t GetReferredTypeId() const { return referredTypeId_; } + Linkage GetLinkage() const { return linkage_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t referredTypeId_; + const Linkage linkage_; +}; + +class FunctionPrototype : public Type { + public: + FunctionPrototype(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + uint32_t returnTypeId, std::vector parameters) + : Type(types, index, name, kind), + returnTypeId_(returnTypeId), + parameters_(parameters) {} + uint32_t GetReturnTypeId() const { return returnTypeId_; } + const std::vector &GetParameters() const { return parameters_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t returnTypeId_; + const std::vector parameters_; +}; + +class Variable : public Type { + public: + enum class Linkage : uint32_t { STATIC, GLOBAL_ALLOC, GLOBAL_EXTERN }; + Variable(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + unsigned varTypeId, Linkage linkage) + : Type(types, index, name, kind), + varTypeId_(varTypeId), + linkage_(linkage) {} + uint32_t GetVarTypeId() const { return varTypeId_; } + Linkage GetLinkage() const { return linkage_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t varTypeId_; + const Linkage linkage_; +}; + +class DataSection : public Type { + public: + DataSection(const std::vector> &types, + uint32_t index, std::string_view name, Kind kind, + uint32_t bytesize, std::vector secinfos) + : Type(types, index, name, kind), + bytesize_(bytesize), + secinfos_(secinfos) {} + uint32_t GetByteSize() const { return bytesize_; } + const std::vector &GetSecinfos() const { return secinfos_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const uint32_t bytesize_; + const std::vector secinfos_; +}; + +// Not actually a BTF type but needed for uniformity of representation. +class ElfSymbol : public Type { + public: + ElfSymbol(const std::vector> &types, + abigail::elf_symbol_sptr symbol, uint32_t type_id) + : Type(types, -1, {}, -1), symbol_(symbol), type_id_(type_id) {} + abigail::elf_symbol_sptr GetElfSymbol() const { return symbol_; } + uint32_t GetTypeId() const { return type_id_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + abigail::elf_symbol_sptr symbol_; + uint32_t type_id_; +}; + +std::ostream &operator<<(std::ostream &os, const Type &bt); +std::ostream &operator<<(std::ostream &os, const Ptr &bp); +std::ostream &operator<<(std::ostream &os, const Typedef &bp); +std::ostream &operator<<(std::ostream &os, const Qualifier &bp); +std::ostream &operator<<(std::ostream &os, const Integer &bi); +std::ostream &operator<<(std::ostream &os, const Array &ba); +std::ostream &operator<<(std::ostream &os, const StructUnion &bsu); +std::ostream &operator<<(std::ostream &os, const Enumeration &be); +std::ostream &operator<<(std::ostream &os, const ForwardDeclaration &bfd); +std::ostream &operator<<(std::ostream &os, const Function &bf); +std::ostream &operator<<(std::ostream &os, const FunctionPrototype &bfp); +std::ostream &operator<<(std::ostream &os, const Variable &bv); +std::ostream &operator<<(std::ostream &os, const DataSection &bds); +std::ostream &operator<<(std::ostream &os, const ElfSymbol &bes); +std::ostream &operator<<(std::ostream &os, Variable::Linkage linkage); +std::ostream &operator<<(std::ostream &os, Function::Linkage linkage); + +// BTF Specification: https://www.kernel.org/doc/html/latest/bpf/btf.html +class Structs { + public: + Structs(const char *start, std::unique_ptr env, + const abigail::symtab_reader::symtab_sptr tab, + const bool verbose = false); + ~Structs() = default; + void PrintHeader(); + void BuildTypes(); + void PrintStringSection(); + const std::map &GetSymbols( + bool use_elf_symbols) const { + return use_elf_symbols ? elf_symbols_ : btf_symbols_; + } + + private: + const btf_header *header_; + const btf_type *type_section_; + const char *str_section_; + const std::unique_ptr env_; + const abigail::symtab_reader::symtab_sptr tab_; + const bool verbose_; + + std::vector> types_; + std::unordered_map btf_symbol_types_; + std::map btf_symbols_; + std::map elf_symbols_; + + std::vector bad_names_; + std::string bad_prefix_1_; + std::string bad_prefix_2_; + + int BuildOneType(const btf_type *t, uint32_t index); + void BuildElfSymbols(); + std::map BuildMembers( + bool kflag, const btf_member *members, size_t vlen); + std::map BuildEnums(const struct btf_enum *enums, + size_t vlen); + std::vector BuildParams(const struct btf_param *params, + size_t vlen); + std::vector BuildDatasec(const btf_type *type, size_t vlen); + std::string_view GetName(uint32_t name_off); +}; + +Structs ReadFile(const std::string &path, bool verbose = false); + +} // end namespace btf +} // end namespace abigail + +#endif // __ABG_BTF_H__ diff --git a/src/Makefile.am b/src/Makefile.am index 430ce98d..d67c604c 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -8,6 +8,12 @@ VIZ_SOURCES = abg-viz-common.cc \ abg-viz-dot.cc \ abg-viz-svg.cc +if ENABLE_CXX17 +if HAVE_BTF + BTF_SOURCES = abg-btf.cc +endif +endif + libabigail_la_SOURCES = \ abg-internal.h \ abg-traverse.cc \ @@ -39,7 +45,8 @@ abg-elf-helpers.cc \ abg-regex.cc \ abg-symtab-reader.h \ abg-symtab-reader.cc \ -$(VIZ_SOURCES) +$(VIZ_SOURCES) \ +$(BTF_SOURCES) libabigail_la_LIBADD = $(DEPS_LIBS) libabigail_la_LDFLAGS = -lpthread -Wl,--as-needed -no-undefined diff --git a/src/abg-btf.cc b/src/abg-btf.cc new file mode 100644 index 00000000..8e4f9ea6 --- /dev/null +++ b/src/abg-btf.cc @@ -0,0 +1,1364 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020-2021 Google, Inc. +// +// Author: Maria Teguiani +// Author: Giuliano Procida + +#include + +#include +#include +#include +#include +#include + +#include "abg-elf-helpers.h" +#include "abg-symtab-reader.h" +#include "abg-tools-utils.h" + +#include "abg-btf.h" + +namespace abigail { +namespace btf { + +// This is a helper map that yields the name of a Type in the preferred +// print style by indexing into the vector with a Kind +static constexpr std::array kKindNames = { + "void type", + "integer type", + "pointer type", + "array type", + "struct type", + "union type", + "enum type", + "forward declaration", + "typedef", + "volatile", + "const", + "restrict", + "function", + "function type", + "variable", + "data section" +}; + +// This matches bpftool dump format raw. +static constexpr std::array kRawKindNames = { + "VOID", + "INT", + "PTR", + "ARRAY", + "STRUCT", + "UNION", + "ENUM", + "FWD", + "TYPEDEF", + "VOLATILE", + "CONST", + "RESTRICT", + "FUNC", + "FUNC_PROTO", + "VAR", + "DATASEC" +}; + +static constexpr std::array kVarLinkage = { + "static", + "global-alloc", + "global-extern" // NOTE: bpftool currently says "(unknown)" +}; + +static constexpr std::array kFunLinkage = { + "static", + "global", + "extern" +}; + +Name Name::Add(Side side, Precedence precedence, std::string_view text) const { + bool bracket = precedence < precedence_; + std::ostringstream left; + std::ostringstream right; + + // Bits on the left need (sometimes) to be separated by whitespace. + left << left_; + if (bracket) + left << '('; + else if (side == Side::LEFT) + left << ' '; + + (side == Side::LEFT ? left : right) << text; + + // Bits on the right are arrays [] and functions () and need no whitespace. + if (bracket) + right << ')'; + right << right_; + + return Name{left.str(), precedence, right.str()}; +} + +Name Name::Qualify(const std::set &qualifiers) const { + // this covers the case when bad qualifiers have been dropped + if (qualifiers.empty()) + return *this; + // add qualifiers to the left or right of the type stem + std::ostringstream os; + if (precedence_ == Precedence::NIL) { + for (const auto &qualifier : qualifiers) + os << kKindNames[qualifier] << ' '; + os << left_; + } else if (precedence_ == Precedence::POINTER) { + os << left_; + for (const auto &qualifier : qualifiers) + os << ' ' << kKindNames[qualifier]; + } else { + m_assert(false, "unqualifiable element"); + } + // qualifiers attach without affecting precedence + return Name{os.str(), precedence_, right_}; +} + +std::ostream &Name::Print(std::ostream &os) const { + return os << left_ << right_; +} + +std::ostream &operator<<(std::ostream &os, const Name &name) { + return name.Print(os); +} + +// There are several reasons for treating CV-qualifiers specially. +// 1. They upset the precedence scheme we've got going here. +// 2. Qualifiers need to be placed according to what they qualify. +// 3. The BTF model doesn't preclude ordering and duplication issues. +// 4. A better model would have qualifiers as part of the types. +const Name &Type::GetDescription(NameCache &names) const { + // infinite recursion prevention - insert at most once + static const Name black_hole{"#"}; + + auto insertion = names.insert({this, black_hole}); + Name &cached = insertion.first->second; + + if (insertion.second) { + // newly inserted, need to determine name of type + std::set qualifiers; + const Type &under = ResolveQualifiers(qualifiers); + if (this == &under) { + // unqualified, simple case + cached = MakeDescription(names); + } else { + // qualified, but we may end up adding no qualifiers + auto insertion_under = names.insert({&under, black_hole}); + Name &cached_under = insertion_under.first->second; + + // newly inserted underlying type name + if (insertion_under.second) + cached_under = under.MakeDescription(names); + + // add the qualifiers (to the appropriate side) + cached = cached_under.Qualify(qualifiers); + } + } + + return cached; +} + +std::string GetPlainDescription(NameCache &names, const Type &type) { + std::ostringstream os; + os << '"' << type.GetDescription(names) << '"'; + return os.str(); +} + +std::string GetTypedefDescription(NameCache &names, const Type &given) { + std::ostringstream os; + std::vector typedefs; + const Type &type = given.ResolveTypedef(typedefs); + for (auto td : typedefs) + os << std::quoted(td) << " = "; + os << GetPlainDescription(names, type); + return os.str(); +} + +constexpr size_t INDENT_INCREMENT = 2; + +void Print(const Comparison &comparison, const Outcomes &outcomes, Seen &seen, + NameCache &names, std::ostream &os, size_t indent) { + const auto *lhs = comparison.first; + const auto *rhs = comparison.second; + if (!rhs) { + os << GetPlainDescription(names, *lhs) << " was removed\n"; + return; + } + if (!lhs) { + os << GetPlainDescription(names, *rhs) << " was added\n"; + return; + } + bool td = lhs->GetKind() == BTF_KIND_TYPEDEF + || rhs->GetKind() == BTF_KIND_TYPEDEF; + const std::string lhs_descr = td ? GetTypedefDescription(names, *lhs) + : GetPlainDescription(names, *lhs); + const std::string rhs_descr = td ? GetTypedefDescription(names, *rhs) + : GetPlainDescription(names, *rhs); + if (lhs_descr == rhs_descr) + os << lhs_descr << " changed"; + else + os << "changed from " << lhs_descr << " to " << rhs_descr; + const auto &details = outcomes.find(comparison)->second; + auto insertion = seen.insert({comparison, false}); + if (!insertion.second) { + if (!insertion.first->second) + os << " (being reported)"; + else if (!details.empty()) + os << " (already reported)"; + } + os << '\n'; + if (insertion.second) { + Print(details, outcomes, seen, names, os, indent + INDENT_INCREMENT); + insertion.first->second = true; + } + // paragraph spacing + if (!indent) + os << '\n'; +} + +void Print(const Diff &details, const Outcomes &outcomes, Seen &seen, + NameCache &names, std::ostream &os, size_t indent) { + for (const auto &detail : details) { + os << std::string(indent, ' ') << detail.text_; + if (!detail.edge_) { + os << '\n'; + } else { + os << ' '; + Print(detail.edge_.value(), outcomes, seen, names, os, indent); + } + } +} + +const Type &Type::GetTypeAtIndex(size_t index) const { + m_assert(index < types_.size(), "Index out of bounds."); + return *(types_[index].get()); +} + +std::string QualifiersMessage(Kind qualifier, const std::string &action) { + std::ostringstream os; + os << "qualifier " << kKindNames[qualifier] << ' ' << action; + return os.str(); +} + +Result Type::CompareSymbols( + const std::map &lhs, + const std::map &rhs, + Outcomes &outcomes) { + Result result; + State state(outcomes); + auto lit = lhs.begin(); + auto rit = rhs.begin(); + // Each branch contains a NULL pointer check in case BTF information is + // missing for a symbol. We conservatively have to assume that any symbol + // without BTF information may have changed type. + // + // NOTE: this currently happens for all global variables + while (lit != lhs.end() || rit != rhs.end()) { + if (rit == rhs.end() || (lit != lhs.end() && lit->first < rit->first)) { + // removed + if (lit->second) { + auto diff = Removed(*lit->second, state); + result.AddDiff("symbol", diff); + } else { + std::ostringstream os; + os << "symbol " << std::quoted(lit->first) + << " (of unknown type) was removed"; + result.AddDiff(os.str()); + } + ++lit; + } else if (lit == lhs.end() || (rit != rhs.end() && lit->first > rit->first)) { + // added + if (rit->second) { + auto diff = Added(*rit->second, state); + result.AddDiff("symbol", diff); + } else { + std::ostringstream os; + os << "symbol " << std::quoted(rit->first) + << " (if unknown type) was added"; + result.AddDiff(os.str()); + } + ++rit; + } else { + // in both + if (lit->second && rit->second) { + auto diff = Compare(*lit->second, *rit->second, state); + result.MaybeAddDiff("symbol", diff); + } else { + std::ostringstream os; + os << "symbol " << std::quoted(lit->first) + << " (of unknown type) may have changed"; + result.AddDiff(os.str()); + } + ++lit; + ++rit; + } + } + return result; +} + +Comparison Type::Removed(const Type &lhs, State &state) { + Comparison comparison{&lhs, nullptr}; + state.outcomes.insert({comparison, {}}); + return comparison; +} + +Comparison Type::Added(const Type &rhs, State &state) { + Comparison comparison{nullptr, &rhs}; + state.outcomes.insert({comparison, {}}); + return comparison; +} + +/* + * We compute a diff for every visited node. + * + * Each node has one of: + * 1. equals = true; perhaps only tentative edge differences + * 2. equals = false; at least one definitive node or edge difference + * + * On the first visit to a node we can put a placeholder in, the equals value is + * irrelevant, the diff may contain local and edge differences. If an SCC + * contains only internal edge differences (and equivalently equals is true) + * then the differences can all (eventually) be discarded. + * + * On exit from the first visit to a node, equals reflects the tree of + * comparisons below that node in the DFS and similarly, the diff graph starting + * from the node contains a subtree of this tree plus potentially edges to + * existing nodes to the side or below (already visited SCCs, sharing), or above + * (back links forming cycles). + * + * When an SCC is closed, all equals implies deleting all diffs, any false + * implies updating all to false. + * + * On subsequent visits to a node, there are 2 cases. The node is still open: + * return true and an edge diff. The node is closed, return the stored value and + * an edge diff. + */ +std::pair> Type::Compare( + const Type &lhs, const Type &rhs, Type::State &state) { + Comparison comparison{&lhs, &rhs}; + + // 1. Check if the comparison has an already known result. + if (state.known_equal.count(comparison)) { + // Already visited and closed. Equal. + return {true, {}}; + } + if (state.outcomes.count(comparison)) { + // Already visited and closed. Different. + return {false, {comparison}}; + } + // Either open or not visited at all + + // 2. Record node with Strongly-Connected Component finder. + auto handle = state.scc.Open({comparison, {}}); + if (!handle) { + // Already open. + // + // Return a dummy true outcome and some tentative diffs. The diffs may end + // up not being used and, while it would be nice to be lazier, they encode + // all the cycling-breaking edges needed to recreate a full diff structure. + return {true, {comparison}}; + } + // Comparison opened, need to close it before returning. + + Result result; + + std::set lhs_quals; + std::set rhs_quals; + const Type &l = lhs.ResolveQualifiers(lhs_quals); + const Type &r = rhs.ResolveQualifiers(rhs_quals); + if (!lhs_quals.empty() || !rhs_quals.empty()) { + // 3.1 Qualified type difference. + auto lit = lhs_quals.begin(); + auto rit = rhs_quals.begin(); + auto lend = lhs_quals.end(); + auto rend = rhs_quals.end(); + while (lit != lend || rit != rend) { + if (rit == rend || (lit != lend && *lit < *rit)) { + result.AddDiff(QualifiersMessage(*lit, "removed")); + ++lit; + } else if (lit == lend || (rit != rend && *lit > *rit)) { + result.AddDiff(QualifiersMessage(*rit, "added")); + ++rit; + } else { + ++lit; + ++rit; + } + } + const auto comp = Compare(l, r, state); + result.MaybeAddDiff("underlying type", comp); + } else if (l.GetKind() == BTF_KIND_TYPEDEF + || r.GetKind() == BTF_KIND_TYPEDEF) { + // 3.2 Typedef difference. + std::vector l_typedefs; + std::vector r_typedefs; + const Type &l_ref = l.ResolveTypedef(l_typedefs); + const Type &r_ref = r.ResolveTypedef(r_typedefs); + const auto comp = Compare(l_ref, r_ref, state); + result.MaybeAddDiff("via typedefs", comp); + } else if (typeid(l) != typeid(r)) { + // 4. Incomparable. + result.equals_ = false; + } else { + // 5. Actually compare with dynamic type dispatch. + result = l.Equals(r, state); + } + + // 6. Update result and check for a complete Strongly-Connected Component. + auto comparisons = state.scc.Close(handle.value(), + [&result](Outcomes::value_type &p) { + p.second = result.details_; + }); + if (!comparisons.empty()) { + // Closed SCC. + // + // Note that result now incorporates every inequality and difference in the + // SCC via the DFS spanning tree. + if (result.equals_) { + // Same. Record equalities. + for (auto &c : comparisons) + state.known_equal.insert(c.first); + return {true, {}}; + } else { + // Different. Record diffs. + state.outcomes.insert(std::make_move_iterator(comparisons.begin()), + std::make_move_iterator(comparisons.end())); + } + } + + // Note that both equals and diff are tentative iff comparison is open. + return {result.equals_, {comparison}}; +} + +Name Void::MakeDescription(NameCache &names) const { + return Name{"void"}; +} + +Name Ptr::MakeDescription(NameCache &names) const { + return GetTypeAtIndex(GetPointeeTypeId()).GetDescription(names).Add( + Side::LEFT, Precedence::POINTER, "*"); +} + +Name Typedef::MakeDescription(NameCache &names) const { + return Name{GetName()}; +} + +Name Qualifier::MakeDescription(NameCache &names) const { + m_assert(false, "should not be called"); // NOLINT + return Name{GetName()}; +} + +Name Integer::MakeDescription(NameCache &names) const { + return Name{GetName()}; +} + +Name Array::MakeDescription(NameCache &names) const { + std::ostringstream os; + os << '[' << GetNumberOfElements() << ']'; + return GetTypeAtIndex(GetElementTypeId()).GetDescription(names).Add( + Side::RIGHT, Precedence::ARRAY_FUNCTION, os.str()); +} + +Name StructUnion::MakeDescription(NameCache &names) const { + std::ostringstream os; + os << (GetKind() == BTF_KIND_STRUCT ? "struct" : "union") + << ' ' << (GetName().empty() ? "" : GetName()); + return Name{os.str()}; +} + +Name Enumeration::MakeDescription(NameCache &names) const { + std::ostringstream os; + os << "enum " << (GetName().empty() ? "" : GetName()); + if (GetEnums().empty()) + os << ""; + return Name{os.str()}; +} + +Name ForwardDeclaration::MakeDescription(NameCache &names) const { + std::ostringstream os; + os << GetFwdKind() << ' ' << GetName() << ""; + return Name{os.str()}; +} + +Name FunctionPrototype::MakeDescription(NameCache &names) const { + std::ostringstream os; + os << '('; + bool sep = false; + for (const auto &p : GetParameters()) { + if (sep) + os << ", "; + else + sep = true; + const auto &arg_descr = GetTypeAtIndex(p.typeId_).GetDescription(names); + if (p.name_.empty()) + os << arg_descr; + else + os << arg_descr.Add(Side::LEFT, Precedence::ATOMIC, p.name_); + } + os << ')'; + return GetTypeAtIndex(GetReturnTypeId()).GetDescription(names).Add( + Side::RIGHT, Precedence::ARRAY_FUNCTION, os.str()); +} + +Name Variable::MakeDescription(NameCache &names) const { + return GetTypeAtIndex(GetVarTypeId()).GetDescription(names).Add( + Side::LEFT, Precedence::ATOMIC, GetName()); +} + +Name Function::MakeDescription(NameCache &names) const { + return GetTypeAtIndex(GetReferredTypeId()).GetDescription(names).Add( + Side::LEFT, Precedence::ATOMIC, GetName()); +} + +Name DataSection::MakeDescription(NameCache &names) const { + // NOTE: not yet encountered in the wild + return Name{"Unimplemented"}; +} + +Name ElfSymbol::MakeDescription(NameCache &names) const { + return Name{symbol_->get_name()}; +} + +Result Void::Equals(const Type &other, State &state) const { + return {}; +} + +Result Ptr::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + const auto ref_diff = Compare(GetTypeAtIndex(GetPointeeTypeId()), + o.GetTypeAtIndex(o.GetPointeeTypeId()), state); + result.MaybeAddDiff("pointed-to type", ref_diff); + return result; +} + +Result Typedef::Equals(const Type &other, State &state) const { + m_assert(false, "should not be called"); // NOLINT + return {}; +} + +Result Qualifier::Equals(const Type &other, State &state) const { + m_assert(false, "should not be called"); // NOLINT + return {}; +} + +Result Integer::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + if (isBool() != o.isBool()) { + result.AddDiff(isBool() ? "the first one is a boolean" + : "the second one is a boolean"); + } + if (isSigned() != o.isSigned()) { + result.AddDiff(isSigned() ? "the first one is signed" + : "the second one is signed"); + } + if (isChar() != o.isChar()) { + result.AddDiff(isChar() ? "the first one is a char" + : "the second one is a char"); + } + result.MaybeAddDiff("offset", GetOffset(), o.GetOffset()); + result.MaybeAddDiff("bit size", GetBitSize(), o.GetBitSize()); + if (GetBitSize() != GetByteSize() * 8 && + o.GetBitSize() != o.GetByteSize() * 8) + result.MaybeAddDiff("byte size", GetByteSize(), o.GetByteSize()); + return result; +} + +Result Array::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + result.MaybeAddDiff("number of elements", + GetNumberOfElements(), o.GetNumberOfElements()); + const auto index_type_diff = + Compare(GetTypeAtIndex(GetIndexTypeId()), + o.GetTypeAtIndex(o.GetIndexTypeId()), state); + result.MaybeAddDiff("index type", index_type_diff); + const auto element_type_diff = + Compare(GetTypeAtIndex(GetElementTypeId()), + o.GetTypeAtIndex(o.GetElementTypeId()), state); + result.MaybeAddDiff("element type", element_type_diff); + + return result; +} + +Result StructUnion::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + if (GetKind() != o.GetKind()) { + result.AddDiff(GetKind() == BTF_KIND_STRUCT + ? "changed from struct to union" + : "changed from union to struct"); + } + + result.MaybeAddDiff("byte size", GetByteSize(), o.GetByteSize()); + + const auto &members1 = GetMembers(); + const auto &members2 = o.GetMembers(); + std::set visited_members; + for (const auto &m1 : members1) { + visited_members.insert(m1.first); + auto iter = members2.find(m1.first); + if (iter == members2.end()) { + std::ostringstream os; + os << "member " << std::quoted(m1.first) << " of type"; + auto diff = Removed(GetTypeAtIndex(m1.second.typeId_), state); + result.AddDiff(os.str(), diff); + } else { + result.MaybeAddDiff([&](std::ostream &os) { + os << "member " << std::quoted(m1.first) << " offset"; + }, m1.second.offset_, iter->second.offset_); + result.MaybeAddDiff([&](std::ostream &os) { + os << "member " << std::quoted(m1.first) << " bitfield size"; + }, m1.second.bitfieldSize_, iter->second.bitfieldSize_); + const auto sub_diff = + Compare(GetTypeAtIndex(m1.second.typeId_), + o.GetTypeAtIndex(iter->second.typeId_), state); + result.MaybeAddDiff([&](std::ostream &os) { + os << "member " << std::quoted(m1.first) << " type"; + }, sub_diff); + } + } + for (const auto &m2 : members2) { + if (visited_members.find(m2.first) == visited_members.end()) { + std::ostringstream os; + os << "member " << std::quoted(m2.first) << " of type"; + auto diff = Added(o.GetTypeAtIndex(m2.second.typeId_), state); + result.AddDiff(os.str(), diff); + } + } + + return result; +} + +Result Enumeration::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + result.MaybeAddDiff("byte size", GetByteSize(), o.GetByteSize()); + + const auto &enums1 = GetEnums(); + const auto &enums2 = o.GetEnums(); + std::set visited_enums; + for (const auto &e1 : enums1) { + visited_enums.insert(e1.first); + auto iter = enums2.find(e1.first); + if (iter == enums2.end()) { + std::ostringstream os; + os << "enumerator " << std::quoted(e1.first) + << " (" << e1.second << ") was removed"; + result.AddDiff(os.str()); + } else { + result.MaybeAddDiff([&](std::ostream &os) { + os << "enumerator " << std::quoted(e1.first) << " value"; + }, e1.second, iter->second); + } + } + for (const auto &e2 : enums2) { + if (visited_enums.find(e2.first) == visited_enums.end()) { + std::ostringstream os; + os << "enumerator " << std::quoted(e2.first) + << " (" << e2.second << ") was added"; + result.AddDiff(os.str()); + } + } + + return result; +} + +Result ForwardDeclaration::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + result.MaybeAddDiff("kind", GetFwdKind(), o.GetFwdKind()); + + return result; +} + +Result Function::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + result.MaybeAddDiff("linkage", GetLinkage(), o.GetLinkage()); + const auto func_proto_diff = + Compare(GetTypeAtIndex(GetReferredTypeId()), + o.GetTypeAtIndex(o.GetReferredTypeId()), state); + result.MaybeAddDiff("type", func_proto_diff); + + return result; +} + +Result FunctionPrototype::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + const auto return_type_diff = + Compare(GetTypeAtIndex(GetReturnTypeId()), + o.GetTypeAtIndex(o.GetReturnTypeId()), state); + result.MaybeAddDiff("return type", return_type_diff); + + const auto ¶meters1 = GetParameters(); + const auto ¶meters2 = o.GetParameters(); + size_t min = std::min(parameters1.size(), parameters2.size()); + for (size_t i = 0; i < min; ++i) { + const auto &p1 = parameters1.at(i); + const auto &p2 = parameters2.at(i); + const auto sub_diff = Compare(GetTypeAtIndex(p1.typeId_), + o.GetTypeAtIndex(p2.typeId_), state); + result.MaybeAddDiff([&](std::ostream &os) { + os << "parameter " << i + 1; + const auto &n1 = p1.name_; + const auto &n2 = p2.name_; + if (n1 == n2 && !n1.empty()) { + os << " (" << std::quoted(n1) << ")"; + } else if (n1 != n2) { + os << " ("; + if (!n1.empty()) os << "was " << std::quoted(n1); + if (!n1.empty() && !n2.empty()) os << ", "; + if (!n2.empty()) os << "now " << std::quoted(n2); + os << ")"; + } + os << " type"; + }, sub_diff); + } + + bool added = parameters1.size() < parameters2.size(); + const auto ¶meters = added ? parameters2 : parameters1; + for (size_t i = min; i < parameters.size(); ++i) { + const auto ¶meter = parameters.at(i); + std::ostringstream os; + os << "parameter " << i + 1; + if (!parameter.name_.empty()) + os << " (" << std::quoted(parameter.name_) << ")"; + os << " of type"; + const auto ¶meter_type = GetTypeAtIndex(parameter.typeId_); + auto diff = added ? Added(parameter_type, state) + : Removed(parameter_type, state); + result.AddDiff(os.str(), diff); + } + + return result; +} + +// NOTE: not yet encountered in the wild +Result Variable::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + + result.MaybeAddDiff("linkage", GetLinkage(), o.GetLinkage()); + const auto var_diff = Compare(GetTypeAtIndex(GetVarTypeId()), + o.GetTypeAtIndex(o.GetVarTypeId()), state); + result.MaybeAddDiff("type", var_diff); + + return result; +} + +Result DataSection::Equals(const Type &other, State &state) const { + Result result; + result.AddDiff("Unimplemented"); + + // NOTE: not yet encountered in the wild + m_assert(false, "Unimplemented\n"); // NOLINT + + return result; +} + +Result ElfSymbol::Equals(const Type &other, State &state) const { + Result result; + const auto &o = other.as(); + // TODO: compare ELF symbol attributes + const auto type_diff = Compare(GetTypeAtIndex(type_id_), + o.GetTypeAtIndex(o.type_id_), state); + result.MaybeAddDiff("type", type_diff); + return result; +} + +const Type &Type::ResolveQualifiers(std::set &qualifiers) const { + if (kind_ == BTF_KIND_ARRAY || kind_ == BTF_KIND_FUNC_PROTO) { + // There should be no qualifiers here. + qualifiers.clear(); + } + return *this; +} + +const Type &Qualifier::ResolveQualifiers( + std::set &qualifiers) const { + qualifiers.insert(GetKind()); + return GetTypeAtIndex(GetQualifiedTypeId()).ResolveQualifiers(qualifiers); +} + +const Type &Type::ResolveTypedef( + std::vector &typedefs) const { + return *this; +} + +const Type &Typedef::ResolveTypedef( + std::vector &typedefs) const { + typedefs.push_back(GetName()); + return GetTypeAtIndex(GetReferredTypeId()).ResolveTypedef(typedefs); +} + +std::ostream &operator<<(std::ostream &os, const Type &bt) { + auto name = bt.GetName(); + os << kRawKindNames[bt.GetKind()] + << " '" << (name.empty() ? "(anon)" : name) << '\''; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Ptr &bp) { + os << static_cast(bp) + << " type_id=" << bp.GetPointeeTypeId() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Typedef &bp) { + os << static_cast(bp) + << " type_id=" << bp.GetReferredTypeId() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Qualifier &bp) { + os << static_cast(bp) + << " type_id=" << bp.GetQualifiedTypeId() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Integer &bi) { + os << static_cast(bi) + << " size=" << bi.GetByteSize() + << " bits_offset=" << bi.GetOffset() + << " nr_bits=" << bi.GetBitSize() + << " bool=" << bi.isBool() + << " char=" << bi.isChar() + << " signed=" << bi.isSigned() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Array &ba) { + os << static_cast(ba) + << " type_id=" << ba.GetElementTypeId() + << " index_type_id=" << ba.GetIndexTypeId() + << " nr_elems=" << ba.GetNumberOfElements() + << '\n'; + return os; + } + +std::ostream &operator<<(std::ostream &os, const StructUnion &bsu) { + os << static_cast(bsu) + << " size=" << bsu.GetByteSize() + << " vlen=" << bsu.GetMembers().size() << '\n'; + for (const auto &member : bsu.GetMembers()) { + os << "\t'" << member.first << '\'' + << " type_id=" << member.second.typeId_ + << " bits_offset=" << member.second.offset_; + if (member.second.bitfieldSize_) + os << " bitfield_size=" << member.second.bitfieldSize_; + os << '\n'; + } + return os; +} + +std::ostream &operator<<(std::ostream &os, const Enumeration &be) { + os << static_cast(be) + << " size=" << be.GetByteSize() + << " vlen=" << be.GetEnums().size() + << '\n'; + for (const auto &e : be.GetEnums()) { + os << "\t'" << e.first << "' val=" << e.second << '\n'; + } + return os; +} + +std::ostream &operator<<(std::ostream &os, const ForwardDeclaration &bfd) { + os << static_cast(bfd) + << " fwd_kind=" << bfd.GetFwdKind() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Function &bf) { + os << static_cast(bf) + << " type_id=" << bf.GetReferredTypeId() + << " linkage=" << bf.GetLinkage() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const FunctionPrototype &bfp) { + os << static_cast(bfp) + << " ret_type_id=" << bfp.GetReturnTypeId() + << " vlen=" << bfp.GetParameters().size() + << '\n'; + for (const auto ¶m : bfp.GetParameters()) { + os << "\t'" << (param.name_.empty() ? "(anon)" : param.name_) + << "' type_id=" << param.typeId_ << '\n'; + } + return os; +} + +std::ostream &operator<<(std::ostream &os, const Variable &bv) { + // NOTE: The odd comma is to match bpftool dump. + os << static_cast(bv) + << " type_id=" << bv.GetVarTypeId() + << ", linkage=" << bv.GetLinkage() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const DataSection &bds) { + os << static_cast(bds) + << " size=" << bds.GetByteSize() + << '\n'; + for (const auto &secinfo : bds.GetSecinfos()) { + os << "\ttype_id=" << secinfo.typeId_ + << " offset=" << secinfo.offset_ + << " size=" << secinfo.bytesize_ << '\n'; + } + return os; +} + +std::ostream &operator<<(std::ostream &os, const ElfSymbol &bes) { + os << static_cast(bes); + // TODO: report ELF symbol attributes + os << " type=" << bes.GetTypeId() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, ForwardDeclarationKind kind) { + switch (kind) { + case ForwardDeclarationKind::STRUCT: + os << "struct"; + break; + case ForwardDeclarationKind::UNION: + os << "union"; + break; + } + return os; +} + +std::ostream &operator<<(std::ostream &os, Variable::Linkage linkage) { + auto ix = static_cast(linkage); + return os << (ix < kVarLinkage.size() ? kVarLinkage[ix] : "(unknown)"); +} + +std::ostream &operator<<(std::ostream &os, Function::Linkage linkage) { + auto ix = static_cast(linkage); + return os << (ix < kFunLinkage.size() ? kFunLinkage[ix] : "(unknown)"); +} + +Structs::Structs(const char *start, + std::unique_ptr env, + const abigail::symtab_reader::symtab_sptr tab, + const bool verbose) + : env_(std::move(env)), + tab_(tab), + verbose_(verbose) { + header_ = reinterpret_cast(start); + m_assert(header_->magic == 0xEB9F, "Magic field must be 0xEB9F for BTF"); + + type_section_ = reinterpret_cast(start + header_->hdr_len + + header_->type_off); + str_section_ = start + header_->hdr_len + header_->str_off; + + // every btf_type struct in the type section has an implicit type id. + // type id 0 is reserved for void type, so it is set to a Void here. + // The type section is parsed sequentially and type id is assigned to each + // recognized type starting from id 1. + types_.push_back(std::make_unique(types_, 0, "void", 0)); + + if (verbose_) { + PrintHeader(); + } + BuildTypes(); + if (verbose_) { + PrintStringSection(); + } + + // NOTE: a whole bunch of Linux kernel symbols appear with duplicate (but not + // necessarily identical) BTF type information + // + // TODO: find a better way of resolving this + bad_prefix_1_ = "__arm64_sys_"; + bad_prefix_2_ = "__arm64_compat_sys_"; + bad_names_ = { + "arch_prctl_spec_ctrl_get", + "arch_prctl_spec_ctrl_set", + "ioremap_cache", + "kvm_arch_set_irq_inatomic", + "module_frob_arch_sections", + "vsnprintf" + }; +} + +void Structs::PrintHeader() { + std::cout << "BTF header:\n" + << "\tmagic " << header_->magic + << ", version " << static_cast(header_->version) + << ", flags " << static_cast(header_->flags) + << ", hdr_len " << header_->hdr_len << "\n" + << "\ttype_off " << header_->type_off + << ", type_len " << header_->type_len << "\n" + << "\tstr_off " << header_->str_off + << ", str_len " << header_->str_len << "\n"; +} + +// vlen: vector length, the number of struct/union members +std::map Structs::BuildMembers( + bool kflag, const btf_member *members, size_t vlen) { + std::map result; + int anonymous = 0; + for (size_t i = 0; i < vlen; ++i) { + const auto raw_offset = members[i].offset; + Member member{ + .typeId_ = members[i].type, + .offset_ = kflag ? BTF_MEMBER_BIT_OFFSET(raw_offset) : raw_offset, + .bitfieldSize_ = kflag ? BTF_MEMBER_BITFIELD_SIZE(raw_offset) : 0}; + std::string name = std::string(GetName(members[i].name_off)); + if (name.empty()) { + name = "anon member #" + std::to_string(anonymous); + ++anonymous; + } + result.emplace(name, member); + } + return result; +} + +// vlen: vector length, the number of enum values +std::map Structs::BuildEnums(const struct btf_enum *enums, + size_t vlen) { + std::map result; + for (size_t i = 0; i < vlen; ++i) { + result.emplace(std::string(GetName(enums[i].name_off)), enums[i].val); + } + return result; +} + +// vlen: vector length, the number of parameters +std::vector Structs::BuildParams(const struct btf_param *params, + size_t vlen) { + std::vector result; + result.reserve(vlen); + for (size_t i = 0; i < vlen; ++i) { + Parameter parameter{ + .name_ = std::string(GetName(params[i].name_off)), + .typeId_ = params[i].type}; + result.push_back(parameter); + } + return result; +} + +// vlen: vector length, the number of variables +std::vector Structs::BuildDatasec(const btf_type *type, + size_t vlen) { + std::vector result; + result.reserve(vlen); + const auto *secinfos = reinterpret_cast(type + 1); + for (size_t i = 0; i < vlen; ++i) { + Secinfo secinfo{.typeId_ = secinfos[i].type, + .offset_ = secinfos[i].offset, + .bytesize_ = secinfos[i].size}; + result.push_back(secinfo); + } + return result; +} + +void Structs::BuildTypes() { + m_assert(!(header_->type_off & (sizeof(uint32_t) - 1)), "Unaligned type_off"); + if (header_->type_len == 0) { + std::cerr << "No types found"; + return; + } + if (verbose_) { + std::cout << "Type section:\n"; + } + + const char *curr = reinterpret_cast(type_section_); + const char *end = curr + header_->type_len; + uint32_t index = 1; + while (curr < end) { + const btf_type *t = reinterpret_cast(curr); + int type_size = BuildOneType(t, index); + m_assert(type_size > 0, "Could not identify BTF type"); + curr += type_size; + ++index; + } + + BuildElfSymbols(); +} + +int Structs::BuildOneType(const btf_type *t, uint32_t index) { + const auto kind = BTF_INFO_KIND(t->info); + const auto vlen = BTF_INFO_VLEN(t->info); + // Data following the btf_type struct. + const void *data = reinterpret_cast(t + 1); + m_assert(kind >= 0 && kind < NR_BTF_KINDS, "Unknown BTF kind"); + + if (verbose_) std::cout << '[' << index << "] "; + int type_size = sizeof(struct btf_type); + switch (kind) { + case BTF_KIND_INT: { + const auto bits = *reinterpret_cast(data); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, + BTF_INT_ENCODING(bits), BTF_INT_OFFSET(bits), BTF_INT_BITS(bits), + t->size)); + if (verbose_) { + std::cout << types_.back()->as(); + } + type_size += sizeof(uint32_t); + break; + } + case BTF_KIND_PTR: { + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type)); + if (verbose_) { + std::cout << types_.back()->as(); + } + break; + } + case BTF_KIND_TYPEDEF: { + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type)); + if (verbose_) { + std::cout << types_.back()->as(); + } + break; + } + case BTF_KIND_VOLATILE: + case BTF_KIND_CONST: + case BTF_KIND_RESTRICT: { + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type)); + if (verbose_) { + std::cout << types_.back()->as(); + } + break; + } + case BTF_KIND_ARRAY: { + const auto *array = reinterpret_cast(data); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, array->type, + array->index_type, array->nelems)); + if (verbose_) { + std::cout << types_.back()->as(); + } + type_size += sizeof(struct btf_array); + break; + } + case BTF_KIND_STRUCT: + case BTF_KIND_UNION: { + const bool kflag = BTF_INFO_KFLAG(t->info); + const auto *btf_members = reinterpret_cast(data); + const auto members = BuildMembers(kflag, btf_members, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->size, members)); + if (verbose_) { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_member); + break; + } + case BTF_KIND_ENUM: { + const auto *enums = reinterpret_cast(data); + std::map enumerators = BuildEnums(enums, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, + t->size, enumerators)); + if (verbose_) { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_enum); + break; + } + case BTF_KIND_FWD: { + const bool kflag = BTF_INFO_KFLAG(t->info); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, kflag)); + if (verbose_) { + std::cout << types_.back()->as(); + } + break; + } + case BTF_KIND_FUNC: { + const auto name = GetName(t->name_off); + types_.push_back(std::make_unique( + types_, index, name, kind, t->type, + Function::Linkage(vlen))); + if (verbose_) { + std::cout << types_.back()->as(); + } + bool inserted = btf_symbol_types_.insert({name, t->type}).second; + if (!inserted) { + // NOTE: duplicate BTF symbols could be considered a bug in pahole + // + // TODO: remove these checks once resolved + bool known = !name.compare(0, bad_prefix_1_.size(), bad_prefix_1_) || + !name.compare(0, bad_prefix_2_.size(), bad_prefix_2_) || + std::find(bad_names_.begin(), bad_names_.end(), name) != + bad_names_.end(); + m_assert(known, "Insertion failed, duplicate found in symbol map"); + (void)known; + } + btf_symbols_.insert({name, types_.back().get()}); + break; + } + case BTF_KIND_FUNC_PROTO: { + const auto *params = reinterpret_cast(data); + std::vector parameters = BuildParams(params, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type, + parameters)); + if (verbose_) { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_param); + break; + } + case BTF_KIND_VAR: { + // NOTE: not yet encountered in the wild + const auto *variable = reinterpret_cast(data); + const auto name = GetName(t->name_off); + types_.push_back(std::make_unique( + types_, index, name, kind, t->type, + Variable::Linkage(variable->linkage))); + if (verbose_) { + std::cout << types_.back()->as(); + } + + bool inserted = btf_symbol_types_.insert({name, t->type}).second; + m_assert(inserted, "Insertion failed, duplicate found in symbol map"); + (void)inserted; + btf_symbols_.insert({name, types_.back().get()}); + + type_size += sizeof(struct btf_var); + break; + } + case BTF_KIND_DATASEC: { + std::vector secinfos = BuildDatasec(t, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->size, + secinfos)); + if (verbose_) { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_var_secinfo); + } + } + return type_size; +} + +std::string_view Structs::GetName(uint32_t name_off) { + m_assert(name_off < header_->str_len, + "The name offset exceeds the section length"); + const char *section_end = str_section_ + header_->str_len; + const char *name_end = std::find(&str_section_[name_off], section_end, '\0'); + m_assert(name_end < section_end, + "The name continues past the string section limit"); + (void)name_end; + + std::string_view name{&str_section_[name_off]}; + return name; +} + +void Structs::PrintStringSection() { + std::cout << "String section:\n"; + const char *curr = str_section_; + const char *limit = str_section_ + header_->str_len; + while (curr < limit) { + const char *pos = std::find(curr, limit, '\0'); + m_assert(pos < limit, "Error reading the string section"); + std::cout << ' ' << curr; + curr = pos + 1; + } + std::cout << '\n'; +} + +void Structs::BuildElfSymbols() { + const auto filter = [&]() { + auto filter = tab_->make_filter(); + filter.set_public_symbols(); + return filter; + }(); + for (const auto &symbol : + abigail::symtab_reader::filtered_symtab(*tab_, filter)) { + const auto &symbol_name = symbol->get_name(); + const auto &main_symbol_name = symbol->get_main_symbol()->get_name(); + auto it = btf_symbol_types_.find(main_symbol_name); + if (it == btf_symbol_types_.end()) { + // missing BTF information is tracked explicitly + std::cerr << "ELF symbol " << std::quoted(symbol_name); + if (symbol_name != main_symbol_name) + std::cerr << " (aliased to " << std::quoted(main_symbol_name) << ')'; + std::cerr << " BTF info missing\n"; + types_.push_back(nullptr); + } else { + uint32_t type_id = it->second; + types_.push_back(std::make_unique(types_, symbol, type_id)); + } + elf_symbols_.emplace(symbol_name, types_.back().get()); + } +} + +class ElfHandle { + public: + ElfHandle(const std::string &path) : dwfl_(nullptr, dwfl_end) { + string name; + tools_utils::base_name(path, name); + elf_version(EV_CURRENT); + + dwfl_ = std::unique_ptr( + dwfl_begin(&offline_callbacks_), dwfl_end); + auto dwfl_module = dwfl_report_offline(dwfl_.get(), name.c_str(), + path.c_str(), -1); + GElf_Addr bias; + elf_handle_ = dwfl_module_getelf(dwfl_module, &bias); + } + + // Conversion operator to act as a drop-in replacement for Elf* + operator Elf *() const { return elf_handle_; } + + Elf *get() const { return elf_handle_; } + + private: + // Dwfl owns all our data, hence only keep track of this + std::unique_ptr dwfl_; + Elf *elf_handle_; + + Dwfl_Callbacks offline_callbacks_; +}; + +Structs ReadFile(const std::string &path, bool verbose) { + using abigail::symtab_reader::symtab; + + ElfHandle elf(path); + m_assert(elf.get() != nullptr, "Could not get elf handle from file."); + + Elf_Scn *btf_section = + abigail::elf_helpers::find_section(elf, ".BTF", SHT_PROGBITS); + m_assert(btf_section != nullptr, + "The given file does not have a BTF section"); + Elf_Data *elf_data = elf_rawdata(btf_section, 0); + m_assert(elf_data != nullptr, "The BTF section is invalid"); + const char *btf_start = static_cast(elf_data->d_buf); + + auto env = std::make_unique(); + auto tab = symtab::load(elf, env.get()); + + return Structs(btf_start, std::move(env), std::move(tab), verbose); +} + +} // end namespace btf +} // end namespace abigail From patchwork Fri Jun 11 15:33:18 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43835 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 668B8398B854 for ; Fri, 11 Jun 2021 15:34:30 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 668B8398B854 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623425670; bh=nHM642hA4+vHF1FqEEH0921UM67phOhZB8+ouDte0xs=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=ECVi54TtKAcfyK3HBWw8C5JjF8xhpbEHeHSgkda3XXiZAuEjV8mUmkQ9ybDrDXC5n bkT0f8fypwU2Sg1kbSpb9MIMElnFvgkEXJbW/bcfMrMVU/Mo8CJubiuXWjJvHyTwHQ t2dwL0NBDif6ODC7BAQ7b5fC3GP/09BcI3HuiyPE= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-qv1-xf49.google.com (mail-qv1-xf49.google.com [IPv6:2607:f8b0:4864:20::f49]) by sourceware.org (Postfix) with ESMTPS id 34204399BC07 for ; Fri, 11 Jun 2021 15:34:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 34204399BC07 Received: by mail-qv1-xf49.google.com with SMTP id if5-20020a0562141c45b029021fee105740so18671787qvb.9 for ; Fri, 11 Jun 2021 08:34:24 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=nHM642hA4+vHF1FqEEH0921UM67phOhZB8+ouDte0xs=; b=l7tSMgoovCudEWEHhnVxmoNQGkjGq0PCVa/CCOyqUklMToQiAIfp6uUi/aVtFdi9T6 zvFAZeoP4Ia0c39DveTrJldF0fKX7FJkjhOIOxJcBt3alxoWn8s08zd8PS3QnCit5+Mg 9accND3sAq3fm8ffwNpk+9xNu6nv/CVbSr/k98P/D5mhc3nSRmwshmcmvcJ2u4+WnsMe t9OxKM1TMe9BEMKmUTtDLXNangVK0Oe8LIEmvpfgQSvCF0fLIXGVyVQD2FAEJACLRqwC L9N49na8+NYA+k3DtroCXMG8r1zUWj6XMTq5kvDUzH0r0glHubuPDiA8d/RdXeigPKaZ Db6A== X-Gm-Message-State: AOAM530xvAuzjdNwSeQ4xEL72knxUl2YC0XxbCr+FqwibAkbSq1La0t8 QKDAuhXueqWOcIYAdTEckP65rHQjh6TMn+xCykaWyL6M3LrtW+tDPfG8h9oIxx6hR12PS4g7ixP CMN3FnPPljWmqDAZzi2dBGd0VAm+rtRiBFZWvQ+Hwzwoz3FNWUgGyas5RK+YDFMGMuag6w0M= X-Google-Smtp-Source: ABdhPJxG2j2DvMVDr6bmymMGfNpA7Pb2SBsgpqfpxGxwR5Slq05DymGRIvZEfnih8fd9WXcf+xrBGdw9F9SMwQ== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:c264:c1f9:cf3c:2c0b]) (user=gprocida job=sendgmr) by 2002:a0c:c3d1:: with SMTP id p17mr5359887qvi.44.1623425663679; Fri, 11 Jun 2021 08:34:23 -0700 (PDT) Date: Fri, 11 Jun 2021 16:33:18 +0100 In-Reply-To: <20210611153319.778996-1-gprocida@google.com> Message-Id: <20210611153319.778996-6-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.272.g935e593368-goog Subject: [PATCH 5/6] BTF: add btfinfo and btfdiff tools To: libabigail@sourceware.org X-Spam-Status: No, score=-22.3 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-Patchwork-Original-From: Giuliano Procida via Libabigail From: Giuliano Procida Reply-To: Giuliano Procida Cc: teguiani@android.com, maennich@google.com, Maria Teguiani , kernel-team@android.com Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" This commit adds BTF command line tools. They are fairly thin wrappers around the core BTF functionality. The files are almost a straight copy of the originals. Changes: - Files renamed and #includes updated. * tools/Makefile.am: Compile BTF tools, conditional on C++17 and . * tools/btfdiff.cc: New utility that compares BTF information. * tools/btfinfo.cc: New utility that dumps BTF information. Co-authored-by: Maria Teguiani Signed-off-by: Giuliano Procida --- tools/Makefile.am | 14 ++++++++++ tools/btfdiff.cc | 67 +++++++++++++++++++++++++++++++++++++++++++++++ tools/btfinfo.cc | 19 ++++++++++++++ 3 files changed, 100 insertions(+) create mode 100644 tools/btfdiff.cc create mode 100644 tools/btfinfo.cc diff --git a/tools/Makefile.am b/tools/Makefile.am index 648a71b5..bd310c18 100644 --- a/tools/Makefile.am +++ b/tools/Makefile.am @@ -9,6 +9,12 @@ else noinst_SCRIPTS = fedabipkgdiff endif +if ENABLE_CXX17 +if HAVE_BTF + bin_PROGRAMS += btfinfo btfdiff +endif +endif + noinst_PROGRAMS = abisym abinilint abidiff_SOURCES = abidiff.cc @@ -45,6 +51,14 @@ kmidiffdir = $(bindir) kmidiff_LDADD = $(abs_top_builddir)/src/libabigail.la kmidiff_LDFLAGS = -pthread +btfinfo_SOURCES = btfinfo.cc +btfinfodir = $(bindir) +btfinfo_LDADD = ../src/libabigail.la + +btfdiff_SOURCES = btfdiff.cc +btfdiffdir = $(bindir) +btfdiff_LDADD = ../src/libabigail.la + AM_CXXFLAGS = \ $(VISIBILITY_FLAGS) -I$(abs_top_srcdir)/include \ -I$(abs_top_srcdir)/tools -fPIC diff --git a/tools/btfdiff.cc b/tools/btfdiff.cc new file mode 100644 index 00000000..58c40e42 --- /dev/null +++ b/tools/btfdiff.cc @@ -0,0 +1,67 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020-2021 Google, Inc. +// +// Author: Maria Teguiani +// Author: Giuliano Procida + +#include +#include + +#include +#include + +#include "abg-btf.h" + +const int kAbiChange = 4; + +int main(int argc, char* argv[]) { + bool use_elf_symbols = true; + static option opts[]{ + {"symbols", required_argument, nullptr, 's'}, + {nullptr, 0, nullptr, 0}, + }; + auto usage = [&]() { + std::cerr << "usage: " << argv[0] << " [-s|--symbols type] file1 file2\n" + << " where type is elf (the default) or btf\n"; + return 1; + }; + auto bad_arg = [&](int ix) { + std::cerr << argv[0] << ": option '--" << opts[ix].name + << "' unrecognized argument '" << optarg << "'\n"; + return usage(); + }; + while (true) { + int ix; + int c = getopt_long(argc, argv, "s:", opts, &ix); + if (c == -1) + break; + switch (c) { + case 's': + if (!strcmp(optarg, "btf")) + use_elf_symbols = false; + else if (!strcmp(optarg, "elf")) + use_elf_symbols = true; + else + return bad_arg(ix); + break; + default: + return usage(); + } + } + if (optind + 2 != argc) + return usage(); + + const auto structs1 = abigail::btf::ReadFile(argv[optind++]); + const auto structs2 = abigail::btf::ReadFile(argv[optind++]); + const auto& map1 = structs1.GetSymbols(use_elf_symbols); + const auto& map2 = structs2.GetSymbols(use_elf_symbols); + abigail::btf::Outcomes outcomes; + auto result = abigail::btf::Type::CompareSymbols(map1, map2, outcomes); + abigail::btf::NameCache names; + abigail::btf::Seen seen; + abigail::btf::Print(result.details_, outcomes, seen, names, std::cout); + + return result.equals_ ? 0 : kAbiChange; +} diff --git a/tools/btfinfo.cc b/tools/btfinfo.cc new file mode 100644 index 00000000..dbda7945 --- /dev/null +++ b/tools/btfinfo.cc @@ -0,0 +1,19 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020 Google, Inc. +// +// Author: Maria Teguiani + +#include "abg-btf.h" + +int main(int argc, const char *argv[]) { + if (argc != 2) { + std::cerr << "Please specify the path to a BTF file."; + return 1; + } + + (void) abigail::btf::ReadFile(argv[1], /* verbose = */ true); + + return 0; +} From patchwork Fri Jun 11 15:33:19 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43837 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CF285398B854 for ; Fri, 11 Jun 2021 15:34:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org CF285398B854 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623425681; bh=nSisJB4s/K+ppZXLxdUZFXCXrEODD7kVFGNNNKDtj6k=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=K3eJmrkJYeAG+cs6QcjkGutKYpVaFOyOsoMzrlzHrMbDMpVaO3eBwrgizxBHYopJP y3HGtDcQzCCNZrjl/RN+bN5CYTwqBzmd21eQD3T7vWxwokq5D/t35QCvfhYVlEqsq4 GoiIUerMz3fasMr8FqRuB5z/+rKv+SxbsYnpSDIg= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-wr1-x449.google.com (mail-wr1-x449.google.com [IPv6:2a00:1450:4864:20::449]) by sourceware.org (Postfix) with ESMTPS id 20BEF398EC0F for ; Fri, 11 Jun 2021 15:34:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 20BEF398EC0F Received: by mail-wr1-x449.google.com with SMTP id z13-20020adfec8d0000b0290114cc6b21c4so2774215wrn.22 for ; Fri, 11 Jun 2021 08:34:27 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=nSisJB4s/K+ppZXLxdUZFXCXrEODD7kVFGNNNKDtj6k=; b=dZXxX2pnVrNjqGuFRTThvC/EN5WoT4gF/7DW1rC4CoKCT1FlY2m3SSW6pcoWbeE8oP n2NMUNzCviynD7my3P9K2BBDHRAR3fJu0uDx+5cW7KCCU9tvqU3CwTKnicVjvM0O63x0 3VJYRub1UDvsk7GfyVNnO8U9Ne44cVA0ciDJKVUdgXjcX5W/5U5EsNUgOqKg3N1g4sq2 HZ6ba7ctZJGDNM2443XAXsEdu/5r2ceCGYpxdH/i76ywLCovqXR1+roGpte2cE/q34bF 82t9VlmdG/4Bez0AYzYuodFedQLVYnbakxA8OsZgpf9mS2nfz15zgaiye0M4zrgUzzc6 6Luw== X-Gm-Message-State: AOAM530wKS/YZ4D3O7gCLI/qgs5hLuNye73SMxzkUJETT1oRZlvKFSep 2i1RqrcOOF8a1qoLYEzv3l4SF3W4C0BzPyBGH3CJTLej3c4OLqLPuAz6kD0IShzwFHhWKtHwvZj DSxzPY1I97PcmyPkQ6mHgx1qsHuDtCHazJOgW5Mq7TIqCY66Nvz+6SrTqA8UrJMCwn0TGUJM= X-Google-Smtp-Source: ABdhPJyqq6FOmJ4lyGL+Ly7TrTgNUm92T39TIJl8yA0rjHmzZv+9tuRIH5WHDDBl4ZUUQRyKzTyDJ4U+LBx/VA== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:c264:c1f9:cf3c:2c0b]) (user=gprocida job=sendgmr) by 2002:adf:cd8d:: with SMTP id q13mr438620wrj.78.1623425666074; Fri, 11 Jun 2021 08:34:26 -0700 (PDT) Date: Fri, 11 Jun 2021 16:33:19 +0100 In-Reply-To: <20210611153319.778996-1-gprocida@google.com> Message-Id: <20210611153319.778996-7-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.272.g935e593368-goog Subject: [PATCH 6/6] BTF: clang-format all the new source files To: libabigail@sourceware.org X-Spam-Status: No, score=-23.0 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_FILL_THIS_FORM_SHORT, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-Patchwork-Original-From: Giuliano Procida via Libabigail From: Giuliano Procida Reply-To: Giuliano Procida Cc: maennich@google.com, kernel-team@android.com, teguiani@android.com Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" This is to bring them closer to the libabigail coding style. * include/abg-btf.h: Reformatted with clang-format. * include/abg-scc.h: Reformatted with clang-format. * src/abg-btf.cc: Reformatted with clang-format. * tests/test-scc.cc: Reformatted with clang-format. * tools/btfdiff.cc: Reformatted with clang-format. * tools/btfinfo.cc: Reformatted with clang-format. Signed-off-by: Giuliano Procida --- include/abg-btf.h | 1025 ++++++++++++++++-------- include/abg-scc.h | 67 +- src/abg-btf.cc | 1903 ++++++++++++++++++++++++++------------------- tests/test-scc.cc | 203 +++-- tools/btfdiff.cc | 40 +- tools/btfinfo.cc | 13 +- 6 files changed, 1964 insertions(+), 1287 deletions(-) diff --git a/include/abg-btf.h b/include/abg-btf.h index d47b4ac9..478a2a78 100644 --- a/include/abg-btf.h +++ b/include/abg-btf.h @@ -26,16 +26,19 @@ #include "abg-ir.h" #include "abg-scc.h" -namespace abigail { -namespace btf { +namespace abigail +{ +namespace btf +{ -#define m_assert(expr, msg) assert(((void)(msg), (expr))) +#define m_assert(expr, msg) assert(((void) (msg), (expr))) using Kind = uint32_t; // A Member refers to a data element of a struct or union, used in the context // of StructUnion -struct Member { +struct Member +{ uint32_t typeId_; uint32_t offset_; uint32_t bitfieldSize_; @@ -43,110 +46,156 @@ struct Member { // A Parameter refers to a variable declared in the function declaration, used // in the context of Function -struct Parameter { +struct Parameter +{ std::string name_; uint32_t typeId_; }; -struct Secinfo { +struct Secinfo +{ uint32_t typeId_; uint32_t offset_; uint32_t bytesize_; }; -enum class ForwardDeclarationKind { STRUCT, UNION }; +enum class ForwardDeclarationKind +{ + STRUCT, + UNION +}; -std::ostream &operator<<(std::ostream &os, ForwardDeclarationKind kind); +std::ostream& +operator<<(std::ostream& os, ForwardDeclarationKind kind); class Type; -using Comparison = std::pair; +using Comparison = std::pair; -enum class Precedence { NIL, POINTER, ARRAY_FUNCTION, ATOMIC }; -enum class Side { LEFT, RIGHT }; +enum class Precedence +{ + NIL, + POINTER, + ARRAY_FUNCTION, + ATOMIC +}; +enum class Side +{ + LEFT, + RIGHT +}; -class Name { - public: +class Name +{ +public: explicit Name(std::string_view name) - : left_(name), precedence_(Precedence::NIL), right_() {} + : left_(name), precedence_(Precedence::NIL), right_() + { + } Name(std::string_view left, Precedence precedence, std::string_view right) - : left_(left), precedence_(precedence), right_(right) {} - Name Add(Side side, Precedence precedence, std::string_view text) const; - Name Qualify(const std::set &qualifiers) const; - std::ostream &Print(std::ostream &os) const; - - private: + : left_(left), precedence_(precedence), right_(right) + { + } + Name + Add(Side side, Precedence precedence, std::string_view text) const; + Name + Qualify(const std::set& qualifiers) const; + std::ostream& + Print(std::ostream& os) const; + +private: std::string left_; Precedence precedence_; std::string right_; }; -std::ostream &operator<<(std::ostream &os, const Name &name); +std::ostream& +operator<<(std::ostream& os, const Name& name); -using NameCache = std::unordered_map; +using NameCache = std::unordered_map; -struct DiffDetail { - DiffDetail(const std::string &text, const std::optional &edge) - : text_(text), edge_(edge) {} +struct DiffDetail +{ + DiffDetail(const std::string& text, const std::optional& edge) + : text_(text), edge_(edge) + { + } std::string text_; std::optional edge_; }; using Diff = std::vector; -struct Result { - void AddDiff(const std::string &text) { +struct Result +{ + void + AddDiff(const std::string& text) + { equals_ = false; details_.emplace_back(text, std::optional()); } - void AddDiff(const std::string &text, Comparison comparison) { + void + AddDiff(const std::string& text, Comparison comparison) + { equals_ = false; details_.emplace_back(text, comparison); } - void MaybeAddDiff(const std::string &text, - const std::pair> &p) { + void + MaybeAddDiff(const std::string& text, + const std::pair>& p) + { equals_ &= p.first; - const auto &diff = p.second; + const auto& diff = p.second; if (diff) details_.emplace_back(text, diff); } // Maximally powerful lazy version, takes a function that outputs an "edge" // diff description, to be used only when a diff is present. - void MaybeAddDiff(std::function text, - const std::pair> &p) { + void + MaybeAddDiff(std::function text, + const std::pair>& p) + { equals_ &= p.first; - const auto &diff = p.second; - if (diff) { - std::ostringstream os; - text(os); - details_.emplace_back(os.str(), diff); - } + const auto& diff = p.second; + if (diff) + { + std::ostringstream os; + text(os); + details_.emplace_back(os.str(), diff); + } } - template void MaybeAddDiff( - const std::string &text, const T &before, const T &after) { - if (before != after) { - equals_ = false; - std::ostringstream os; - os << text << " changed from " << before << " to " << after; - AddDiff(os.str()); - } + template + void + MaybeAddDiff(const std::string& text, const T& before, const T& after) + { + if (before != after) + { + equals_ = false; + std::ostringstream os; + os << text << " changed from " << before << " to " << after; + AddDiff(os.str()); + } } // Lazy version. - template void MaybeAddDiff( - std::function text, - const T &before, const T &after) { - if (before != after) { - equals_ = false; - std::ostringstream os; - text(os); - os << " changed from " << before << " to " << after; - AddDiff(os.str()); - } + template + void + MaybeAddDiff(std::function text, + const T& before, + const T& after) + { + if (before != after) + { + equals_ = false; + std::ostringstream os; + text(os); + os << " changed from " << before << " to " << after; + AddDiff(os.str()); + } } bool equals_ = true; @@ -157,22 +206,51 @@ using Outcomes = std::map; // unvisited (absent) -> started (false) -> finished (true) using Seen = std::map; -void Print(const Comparison &comparison, const Outcomes &outcomes, Seen &seen, - NameCache &names, std::ostream &os, size_t indent = 0); - -void Print(const Diff &details, const Outcomes &outcomes, Seen &seen, - NameCache &names, std::ostream &os, size_t indent = 0); - -class Type { - public: - Type(const std::vector> &types, uint32_t index, - std::string_view name, Kind kind) - : types_(types), index_(index), name_(name), kind_(kind) {} +void +Print(const Comparison& comparison, + const Outcomes& outcomes, + Seen& seen, + NameCache& names, + std::ostream& os, + size_t indent = 0); + +void +Print(const Diff& details, + const Outcomes& outcomes, + Seen& seen, + NameCache& names, + std::ostream& os, + size_t indent = 0); + +class Type +{ +public: + Type(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind) + : types_(types), index_(index), name_(name), kind_(kind) + { + } virtual ~Type() = default; - uint32_t GetIndex() const { return index_; } - std::string_view GetName() const { return name_; } - Kind GetKind() const { return kind_; } - const std::vector> &GetTypes() const { + uint32_t + GetIndex() const + { + return index_; + } + std::string_view + GetName() const + { + return name_; + } + Kind + GetKind() const + { + return kind_; + } + const std::vector>& + GetTypes() const + { return types_; } @@ -181,10 +259,12 @@ class Type { // not correct, the assert will trigger in debug mode. In release mode, this // will crash dereferencing the nullptr. template - const Target &as() const { - static_assert(std::is_convertible::value, - "Target must publically inherit Type"); - const Target *t = dynamic_cast(this); + const Target& + as() const + { + static_assert(std::is_convertible::value, + "Target must publically inherit Type"); + const Target* t = dynamic_cast(this); m_assert(t, "Invalid downcast"); return *t; } @@ -192,122 +272,206 @@ class Type { // // The caller must always be prepared to receive a different type as // qualifiers are sometimes discarded. - virtual const Type &ResolveQualifiers(std::set &qualifiers) const; - virtual const Type &ResolveTypedef( - std::vector &typedefs) const; - - const Name &GetDescription(NameCache &names) const; - static Result CompareSymbols( - const std::map &lhs, - const std::map &rhs, - Outcomes &outcomes); - - protected: - struct State { - explicit State(Outcomes &o) : outcomes(o), scc(o.value_comp()) { } - Outcomes &outcomes; + virtual const Type& + ResolveQualifiers(std::set& qualifiers) const; + virtual const Type& + ResolveTypedef(std::vector& typedefs) const; + + const Name& + GetDescription(NameCache& names) const; + static Result + CompareSymbols(const std::map& lhs, + const std::map& rhs, + Outcomes& outcomes); + +protected: + struct State + { + explicit State(Outcomes& o) : outcomes(o), scc(o.value_comp()) {} + Outcomes& outcomes; std::set known_equal; SCC scc; }; - const Type &GetTypeAtIndex(size_t index) const; - - virtual Name MakeDescription(NameCache &names) const = 0; - virtual Result Equals(const Type &other, State &state) const = 0; - static Comparison Removed(const Type &lhs, State &state); - static Comparison Added(const Type &rhs, State &state); - static std::pair> Compare( - const Type &lhs, const Type &rhs, State &state); - - private: - static std::string GetDiffMessage(NameCache &names, - const Type &lhs, const Type &rhs, - const std::string &message = std::string()); - const std::vector> &types_; + const Type& + GetTypeAtIndex(size_t index) const; + + virtual Name + MakeDescription(NameCache& names) const = 0; + virtual Result + Equals(const Type& other, State& state) const = 0; + static Comparison + Removed(const Type& lhs, State& state); + static Comparison + Added(const Type& rhs, State& state); + static std::pair> + Compare(const Type& lhs, const Type& rhs, State& state); + +private: + static std::string + GetDiffMessage(NameCache& names, + const Type& lhs, + const Type& rhs, + const std::string& message = std::string()); + const std::vector>& types_; const uint32_t index_; const std::string name_; const Kind kind_; }; -class Void : public Type { - public: - Void(const std::vector> &types, uint32_t index, - std::string_view name, Kind kind) - : Type(types, index, name, kind) {} - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; +class Void : public Type +{ +public: + Void(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind) + : Type(types, index, name, kind) + { + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; }; -class Ptr : public Type { - public: - Ptr(const std::vector> &types, uint32_t index, - std::string_view name, Kind kind, uint32_t pointeeTypeId) - : Type(types, index, name, kind), - pointeeTypeId_(pointeeTypeId) {} - uint32_t GetPointeeTypeId() const { return pointeeTypeId_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class Ptr : public Type +{ +public: + Ptr(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t pointeeTypeId) + : Type(types, index, name, kind), pointeeTypeId_(pointeeTypeId) + { + } + uint32_t + GetPointeeTypeId() const + { + return pointeeTypeId_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t pointeeTypeId_; }; -class Typedef : public Type { - public: - Typedef(const std::vector> &types, uint32_t index, - std::string_view name, Kind kind, uint32_t referredTypeId) - : Type(types, index, name, kind), - referredTypeId_(referredTypeId) {} - uint32_t GetReferredTypeId() const { return referredTypeId_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - const Type &ResolveTypedef( - std::vector &typedefs) const final; - - private: +class Typedef : public Type +{ +public: + Typedef(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t referredTypeId) + : Type(types, index, name, kind), referredTypeId_(referredTypeId) + { + } + uint32_t + GetReferredTypeId() const + { + return referredTypeId_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + const Type& + ResolveTypedef(std::vector& typedefs) const final; + +private: const uint32_t referredTypeId_; }; -class Qualifier : public Type { - public: - Qualifier(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - uint32_t qualifiedTypeId) - : Type(types, index, name, kind), - qualifiedTypeId_(qualifiedTypeId) {} - uint32_t GetQualifiedTypeId() const { return qualifiedTypeId_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - const Type &ResolveQualifiers(std::set &qualifiers) const final; - - private: +class Qualifier : public Type +{ +public: + Qualifier(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t qualifiedTypeId) + : Type(types, index, name, kind), qualifiedTypeId_(qualifiedTypeId) + { + } + uint32_t + GetQualifiedTypeId() const + { + return qualifiedTypeId_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + const Type& + ResolveQualifiers(std::set& qualifiers) const final; + +private: const uint32_t qualifiedTypeId_; }; -class Integer : public Type { - public: - Integer(const std::vector> &types, uint32_t index, - std::string_view name, Kind kind, uint32_t encoding, - uint32_t offset, uint32_t bitsize, uint32_t bytesize) - : Type(types, index, name, kind), - offset_(offset), - bitsize_(bitsize), - bytesize_(bytesize), - isBool_(encoding & BTF_INT_BOOL), - isSigned_(encoding & BTF_INT_SIGNED), - isChar_(encoding & BTF_INT_CHAR) {} - bool isBool() const { return isBool_; } - bool isSigned() const { return isSigned_; } - bool isChar() const { return isChar_; } - uint32_t GetOffset() const { return offset_; } +class Integer : public Type +{ +public: + Integer(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t encoding, + uint32_t offset, + uint32_t bitsize, + uint32_t bytesize) + : Type(types, index, name, kind), + offset_(offset), + bitsize_(bitsize), + bytesize_(bytesize), + isBool_(encoding & BTF_INT_BOOL), + isSigned_(encoding & BTF_INT_SIGNED), + isChar_(encoding & BTF_INT_CHAR) + { + } + bool + isBool() const + { + return isBool_; + } + bool + isSigned() const + { + return isSigned_; + } + bool + isChar() const + { + return isChar_; + } + uint32_t + GetOffset() const + { + return offset_; + } // GetBitSize() gives the semantics of the field. GetByteSize() gives the // storage size, and is equal or greater than GetBitSize()*8 - uint32_t GetBitSize() const { return bitsize_; } - uint32_t GetByteSize() const { return bytesize_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; + uint32_t + GetBitSize() const + { + return bitsize_; + } + uint32_t + GetByteSize() const + { + return bytesize_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; - private: +private: const uint32_t offset_; const uint32_t bitsize_; const uint32_t bytesize_; @@ -316,236 +480,409 @@ class Integer : public Type { const bool isChar_; }; -class Array : public Type { - public: - Array(const std::vector> &types, uint32_t index, - std::string_view name, Kind kind, uint32_t elementTypeId, - uint32_t indexTypeId, uint32_t numOfElements) - : Type(types, index, name, kind), - elementTypeId_(elementTypeId), - indexTypeId_(indexTypeId), - numOfElements_(numOfElements) {} - uint32_t GetElementTypeId() const { return elementTypeId_; } - uint32_t GetIndexTypeId() const { return indexTypeId_; } - uint32_t GetNumberOfElements() const { return numOfElements_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class Array : public Type +{ +public: + Array(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t elementTypeId, + uint32_t indexTypeId, + uint32_t numOfElements) + : Type(types, index, name, kind), + elementTypeId_(elementTypeId), + indexTypeId_(indexTypeId), + numOfElements_(numOfElements) + { + } + uint32_t + GetElementTypeId() const + { + return elementTypeId_; + } + uint32_t + GetIndexTypeId() const + { + return indexTypeId_; + } + uint32_t + GetNumberOfElements() const + { + return numOfElements_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t elementTypeId_; const uint32_t indexTypeId_; const uint32_t numOfElements_; }; -class StructUnion : public Type { - public: - StructUnion(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - uint32_t bytesize, std::map members) - : Type(types, index, name, kind), - bytesize_(bytesize), - members_(members) {} - uint32_t GetByteSize() const { return bytesize_; } - const std::map &GetMembers() const { return members_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class StructUnion : public Type +{ +public: + StructUnion(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t bytesize, + std::map members) + : Type(types, index, name, kind), bytesize_(bytesize), members_(members) + { + } + uint32_t + GetByteSize() const + { + return bytesize_; + } + const std::map& + GetMembers() const + { + return members_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t bytesize_; const std::map members_; }; -class Enumeration : public Type { - public: - Enumeration(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - uint32_t bytesize, std::map enumerators) - : Type(types, index, name, kind), - bytesize_(bytesize), - enumerators_(enumerators) {} - uint32_t GetByteSize() const { return bytesize_; } - const std::map &GetEnums() const { return enumerators_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class Enumeration : public Type +{ +public: + Enumeration(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t bytesize, + std::map enumerators) + : Type(types, index, name, kind), + bytesize_(bytesize), + enumerators_(enumerators) + { + } + uint32_t + GetByteSize() const + { + return bytesize_; + } + const std::map& + GetEnums() const + { + return enumerators_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t bytesize_; const std::map enumerators_; }; -// BTF only considers structs and unions as forward-declared types, and does not -// include forward-declared enums. They are treated as BTF_KIND_ENUMs with vlen -// set to zero -class ForwardDeclaration : public Type { - public: - ForwardDeclaration(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - bool isUnion) - : Type(types, index, name, kind), - fwdKind_(isUnion ? ForwardDeclarationKind::UNION - : ForwardDeclarationKind::STRUCT) {} - ForwardDeclarationKind GetFwdKind() const { return fwdKind_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +// BTF only considers structs and unions as forward-declared types, and does +// not include forward-declared enums. They are treated as BTF_KIND_ENUMs with +// vlen set to zero +class ForwardDeclaration : public Type +{ +public: + ForwardDeclaration(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + bool isUnion) + : Type(types, index, name, kind), + fwdKind_(isUnion ? ForwardDeclarationKind::UNION + : ForwardDeclarationKind::STRUCT) + { + } + ForwardDeclarationKind + GetFwdKind() const + { + return fwdKind_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const ForwardDeclarationKind fwdKind_; }; -class Function : public Type { - public: - enum class Linkage : uint16_t { STATIC, GLOBAL, EXTERN }; - Function(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - uint32_t referredTypeId, Linkage linkage) - : Type(types, index, name, kind), - referredTypeId_(referredTypeId), - linkage_(linkage) {} - uint32_t GetReferredTypeId() const { return referredTypeId_; } - Linkage GetLinkage() const { return linkage_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class Function : public Type +{ +public: + enum class Linkage : uint16_t + { + STATIC, + GLOBAL, + EXTERN + }; + Function(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t referredTypeId, + Linkage linkage) + : Type(types, index, name, kind), + referredTypeId_(referredTypeId), + linkage_(linkage) + { + } + uint32_t + GetReferredTypeId() const + { + return referredTypeId_; + } + Linkage + GetLinkage() const + { + return linkage_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t referredTypeId_; const Linkage linkage_; }; -class FunctionPrototype : public Type { - public: - FunctionPrototype(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - uint32_t returnTypeId, std::vector parameters) - : Type(types, index, name, kind), - returnTypeId_(returnTypeId), - parameters_(parameters) {} - uint32_t GetReturnTypeId() const { return returnTypeId_; } - const std::vector &GetParameters() const { return parameters_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class FunctionPrototype : public Type +{ +public: + FunctionPrototype(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t returnTypeId, + std::vector parameters) + : Type(types, index, name, kind), + returnTypeId_(returnTypeId), + parameters_(parameters) + { + } + uint32_t + GetReturnTypeId() const + { + return returnTypeId_; + } + const std::vector& + GetParameters() const + { + return parameters_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t returnTypeId_; const std::vector parameters_; }; -class Variable : public Type { - public: - enum class Linkage : uint32_t { STATIC, GLOBAL_ALLOC, GLOBAL_EXTERN }; - Variable(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - unsigned varTypeId, Linkage linkage) - : Type(types, index, name, kind), - varTypeId_(varTypeId), - linkage_(linkage) {} - uint32_t GetVarTypeId() const { return varTypeId_; } - Linkage GetLinkage() const { return linkage_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class Variable : public Type +{ +public: + enum class Linkage : uint32_t + { + STATIC, + GLOBAL_ALLOC, + GLOBAL_EXTERN + }; + Variable(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + unsigned varTypeId, + Linkage linkage) + : Type(types, index, name, kind), varTypeId_(varTypeId), linkage_(linkage) + { + } + uint32_t + GetVarTypeId() const + { + return varTypeId_; + } + Linkage + GetLinkage() const + { + return linkage_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t varTypeId_; const Linkage linkage_; }; -class DataSection : public Type { - public: - DataSection(const std::vector> &types, - uint32_t index, std::string_view name, Kind kind, - uint32_t bytesize, std::vector secinfos) - : Type(types, index, name, kind), - bytesize_(bytesize), - secinfos_(secinfos) {} - uint32_t GetByteSize() const { return bytesize_; } - const std::vector &GetSecinfos() const { return secinfos_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class DataSection : public Type +{ +public: + DataSection(const std::vector>& types, + uint32_t index, + std::string_view name, + Kind kind, + uint32_t bytesize, + std::vector secinfos) + : Type(types, index, name, kind), bytesize_(bytesize), secinfos_(secinfos) + { + } + uint32_t + GetByteSize() const + { + return bytesize_; + } + const std::vector& + GetSecinfos() const + { + return secinfos_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const uint32_t bytesize_; const std::vector secinfos_; }; // Not actually a BTF type but needed for uniformity of representation. -class ElfSymbol : public Type { - public: - ElfSymbol(const std::vector> &types, - abigail::elf_symbol_sptr symbol, uint32_t type_id) - : Type(types, -1, {}, -1), symbol_(symbol), type_id_(type_id) {} - abigail::elf_symbol_sptr GetElfSymbol() const { return symbol_; } - uint32_t GetTypeId() const { return type_id_; } - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; - - private: +class ElfSymbol : public Type +{ +public: + ElfSymbol(const std::vector>& types, + abigail::elf_symbol_sptr symbol, + uint32_t type_id) + : Type(types, -1, {}, -1), symbol_(symbol), type_id_(type_id) + { + } + abigail::elf_symbol_sptr + GetElfSymbol() const + { + return symbol_; + } + uint32_t + GetTypeId() const + { + return type_id_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: abigail::elf_symbol_sptr symbol_; uint32_t type_id_; }; -std::ostream &operator<<(std::ostream &os, const Type &bt); -std::ostream &operator<<(std::ostream &os, const Ptr &bp); -std::ostream &operator<<(std::ostream &os, const Typedef &bp); -std::ostream &operator<<(std::ostream &os, const Qualifier &bp); -std::ostream &operator<<(std::ostream &os, const Integer &bi); -std::ostream &operator<<(std::ostream &os, const Array &ba); -std::ostream &operator<<(std::ostream &os, const StructUnion &bsu); -std::ostream &operator<<(std::ostream &os, const Enumeration &be); -std::ostream &operator<<(std::ostream &os, const ForwardDeclaration &bfd); -std::ostream &operator<<(std::ostream &os, const Function &bf); -std::ostream &operator<<(std::ostream &os, const FunctionPrototype &bfp); -std::ostream &operator<<(std::ostream &os, const Variable &bv); -std::ostream &operator<<(std::ostream &os, const DataSection &bds); -std::ostream &operator<<(std::ostream &os, const ElfSymbol &bes); -std::ostream &operator<<(std::ostream &os, Variable::Linkage linkage); -std::ostream &operator<<(std::ostream &os, Function::Linkage linkage); +std::ostream& +operator<<(std::ostream& os, const Type& bt); +std::ostream& +operator<<(std::ostream& os, const Ptr& bp); +std::ostream& +operator<<(std::ostream& os, const Typedef& bp); +std::ostream& +operator<<(std::ostream& os, const Qualifier& bp); +std::ostream& +operator<<(std::ostream& os, const Integer& bi); +std::ostream& +operator<<(std::ostream& os, const Array& ba); +std::ostream& +operator<<(std::ostream& os, const StructUnion& bsu); +std::ostream& +operator<<(std::ostream& os, const Enumeration& be); +std::ostream& +operator<<(std::ostream& os, const ForwardDeclaration& bfd); +std::ostream& +operator<<(std::ostream& os, const Function& bf); +std::ostream& +operator<<(std::ostream& os, const FunctionPrototype& bfp); +std::ostream& +operator<<(std::ostream& os, const Variable& bv); +std::ostream& +operator<<(std::ostream& os, const DataSection& bds); +std::ostream& +operator<<(std::ostream& os, const ElfSymbol& bes); +std::ostream& +operator<<(std::ostream& os, Variable::Linkage linkage); +std::ostream& +operator<<(std::ostream& os, Function::Linkage linkage); // BTF Specification: https://www.kernel.org/doc/html/latest/bpf/btf.html -class Structs { - public: - Structs(const char *start, std::unique_ptr env, - const abigail::symtab_reader::symtab_sptr tab, - const bool verbose = false); +class Structs +{ +public: + Structs(const char* start, + std::unique_ptr env, + const abigail::symtab_reader::symtab_sptr tab, + const bool verbose = false); ~Structs() = default; - void PrintHeader(); - void BuildTypes(); - void PrintStringSection(); - const std::map &GetSymbols( - bool use_elf_symbols) const { + void + PrintHeader(); + void + BuildTypes(); + void + PrintStringSection(); + const std::map& + GetSymbols(bool use_elf_symbols) const + { return use_elf_symbols ? elf_symbols_ : btf_symbols_; } - private: - const btf_header *header_; - const btf_type *type_section_; - const char *str_section_; +private: + const btf_header* header_; + const btf_type* type_section_; + const char* str_section_; const std::unique_ptr env_; const abigail::symtab_reader::symtab_sptr tab_; const bool verbose_; std::vector> types_; std::unordered_map btf_symbol_types_; - std::map btf_symbols_; - std::map elf_symbols_; + std::map btf_symbols_; + std::map elf_symbols_; std::vector bad_names_; std::string bad_prefix_1_; std::string bad_prefix_2_; - int BuildOneType(const btf_type *t, uint32_t index); - void BuildElfSymbols(); - std::map BuildMembers( - bool kflag, const btf_member *members, size_t vlen); - std::map BuildEnums(const struct btf_enum *enums, - size_t vlen); - std::vector BuildParams(const struct btf_param *params, - size_t vlen); - std::vector BuildDatasec(const btf_type *type, size_t vlen); - std::string_view GetName(uint32_t name_off); + int + BuildOneType(const btf_type* t, uint32_t index); + void + BuildElfSymbols(); + std::map + BuildMembers(bool kflag, const btf_member* members, size_t vlen); + std::map + BuildEnums(const struct btf_enum* enums, size_t vlen); + std::vector + BuildParams(const struct btf_param* params, size_t vlen); + std::vector + BuildDatasec(const btf_type* type, size_t vlen); + std::string_view + GetName(uint32_t name_off); }; -Structs ReadFile(const std::string &path, bool verbose = false); +Structs +ReadFile(const std::string& path, bool verbose = false); -} // end namespace btf -} // end namespace abigail +} // end namespace btf +} // end namespace abigail -#endif // __ABG_BTF_H__ +#endif // __ABG_BTF_H__ diff --git a/include/abg-scc.h b/include/abg-scc.h index d60b1aed..c152def0 100644 --- a/include/abg-scc.h +++ b/include/abg-scc.h @@ -14,7 +14,8 @@ #include #include -namespace abigail { +namespace abigail +{ /* * This is a streamlined Strongly-Connected Component finder for use with @@ -59,26 +60,33 @@ namespace abigail { * the nodes as visited), this should be done now. Otherwise, an empty vector * will be returned. */ -template class SCC { - public: - explicit SCC(std::function cmp) : cmp_(cmp) - {} - ~SCC() { +template class SCC +{ +public: + explicit SCC(std::function cmp) : cmp_(cmp) + { + } + ~SCC() + { assert(open_.empty()); assert(root_index_.empty()); } - std::optional Open(const Node &node) { - for (size_t ix = 0; ix < open_.size(); ++ix) { - const auto &other = open_[ix]; - // node == other? - if (!cmp_(node, other) && !cmp_(other, node)) { - // Pop indices to nodes which cannot be the root of their SCC. - while (root_index_.back() > ix) - root_index_.pop_back(); - return {}; + std::optional + Open(const Node& node) + { + for (size_t ix = 0; ix < open_.size(); ++ix) + { + const auto& other = open_[ix]; + // node == other? + if (!cmp_(node, other) && !cmp_(other, node)) + { + // Pop indices to nodes which cannot be the root of their SCC. + while (root_index_.back() > ix) + root_index_.pop_back(); + return {}; + } } - } // Unvisited, mark node as open and record root index. auto ix = open_.size(); open_.push_back(node); @@ -86,26 +94,29 @@ template class SCC { return ix; } - std::vector Close( - size_t ix, std::function update = [](Node &){}) { + std::vector + Close( + size_t ix, std::function update = [](Node&) {}) + { std::vector scc; assert(ix < open_.size()); update(open_[ix]); - if (ix == root_index_.back()) { - // Close SCC. - root_index_.pop_back(); - std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); - open_.resize(ix); - } + if (ix == root_index_.back()) + { + // Close SCC. + root_index_.pop_back(); + std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); + open_.resize(ix); + } return scc; } - private: - std::function cmp_; +private: + std::function cmp_; std::vector open_; std::vector root_index_; }; -} // namespace abigail +} // namespace abigail -#endif // __ABG_SCC_H__ +#endif // __ABG_SCC_H__ diff --git a/src/abg-btf.cc b/src/abg-btf.cc index 8e4f9ea6..6da52d5c 100644 --- a/src/abg-btf.cc +++ b/src/abg-btf.cc @@ -20,63 +20,62 @@ #include "abg-btf.h" -namespace abigail { -namespace btf { +namespace abigail +{ +namespace btf +{ // This is a helper map that yields the name of a Type in the preferred // print style by indexing into the vector with a Kind static constexpr std::array kKindNames = { - "void type", - "integer type", - "pointer type", - "array type", - "struct type", - "union type", - "enum type", - "forward declaration", - "typedef", - "volatile", - "const", - "restrict", - "function", - "function type", - "variable", - "data section" -}; + "void type", + "integer type", + "pointer type", + "array type", + "struct type", + "union type", + "enum type", + "forward declaration", + "typedef", + "volatile", + "const", + "restrict", + "function", + "function type", + "variable", + "data section"}; // This matches bpftool dump format raw. static constexpr std::array kRawKindNames = { - "VOID", - "INT", - "PTR", - "ARRAY", - "STRUCT", - "UNION", - "ENUM", - "FWD", - "TYPEDEF", - "VOLATILE", - "CONST", - "RESTRICT", - "FUNC", - "FUNC_PROTO", - "VAR", - "DATASEC" -}; + "VOID", + "INT", + "PTR", + "ARRAY", + "STRUCT", + "UNION", + "ENUM", + "FWD", + "TYPEDEF", + "VOLATILE", + "CONST", + "RESTRICT", + "FUNC", + "FUNC_PROTO", + "VAR", + "DATASEC"}; static constexpr std::array kVarLinkage = { - "static", - "global-alloc", - "global-extern" // NOTE: bpftool currently says "(unknown)" + "static", + "global-alloc", + "global-extern" // NOTE: bpftool currently says "(unknown)" }; static constexpr std::array kFunLinkage = { - "static", - "global", - "extern" -}; + "static", "global", "extern"}; -Name Name::Add(Side side, Precedence precedence, std::string_view text) const { +Name +Name::Add(Side side, Precedence precedence, std::string_view text) const +{ bool bracket = precedence < precedence_; std::ostringstream left; std::ostringstream right; @@ -98,32 +97,43 @@ Name Name::Add(Side side, Precedence precedence, std::string_view text) const { return Name{left.str(), precedence, right.str()}; } -Name Name::Qualify(const std::set &qualifiers) const { +Name +Name::Qualify(const std::set& qualifiers) const +{ // this covers the case when bad qualifiers have been dropped if (qualifiers.empty()) return *this; // add qualifiers to the left or right of the type stem std::ostringstream os; - if (precedence_ == Precedence::NIL) { - for (const auto &qualifier : qualifiers) - os << kKindNames[qualifier] << ' '; - os << left_; - } else if (precedence_ == Precedence::POINTER) { - os << left_; - for (const auto &qualifier : qualifiers) - os << ' ' << kKindNames[qualifier]; - } else { - m_assert(false, "unqualifiable element"); - } + if (precedence_ == Precedence::NIL) + { + for (const auto& qualifier : qualifiers) + os << kKindNames[qualifier] << ' '; + os << left_; + } + else if (precedence_ == Precedence::POINTER) + { + os << left_; + for (const auto& qualifier : qualifiers) + os << ' ' << kKindNames[qualifier]; + } + else + { + m_assert(false, "unqualifiable element"); + } // qualifiers attach without affecting precedence return Name{os.str(), precedence_, right_}; } -std::ostream &Name::Print(std::ostream &os) const { +std::ostream& +Name::Print(std::ostream& os) const +{ return os << left_ << right_; } -std::ostream &operator<<(std::ostream &os, const Name &name) { +std::ostream& +operator<<(std::ostream& os, const Name& name) +{ return name.Print(os); } @@ -132,47 +142,57 @@ std::ostream &operator<<(std::ostream &os, const Name &name) { // 2. Qualifiers need to be placed according to what they qualify. // 3. The BTF model doesn't preclude ordering and duplication issues. // 4. A better model would have qualifiers as part of the types. -const Name &Type::GetDescription(NameCache &names) const { +const Name& +Type::GetDescription(NameCache& names) const +{ // infinite recursion prevention - insert at most once static const Name black_hole{"#"}; auto insertion = names.insert({this, black_hole}); - Name &cached = insertion.first->second; - - if (insertion.second) { - // newly inserted, need to determine name of type - std::set qualifiers; - const Type &under = ResolveQualifiers(qualifiers); - if (this == &under) { - // unqualified, simple case - cached = MakeDescription(names); - } else { - // qualified, but we may end up adding no qualifiers - auto insertion_under = names.insert({&under, black_hole}); - Name &cached_under = insertion_under.first->second; - - // newly inserted underlying type name - if (insertion_under.second) - cached_under = under.MakeDescription(names); - - // add the qualifiers (to the appropriate side) - cached = cached_under.Qualify(qualifiers); + Name& cached = insertion.first->second; + + if (insertion.second) + { + // newly inserted, need to determine name of type + std::set qualifiers; + const Type& under = ResolveQualifiers(qualifiers); + if (this == &under) + { + // unqualified, simple case + cached = MakeDescription(names); + } + else + { + // qualified, but we may end up adding no qualifiers + auto insertion_under = names.insert({&under, black_hole}); + Name& cached_under = insertion_under.first->second; + + // newly inserted underlying type name + if (insertion_under.second) + cached_under = under.MakeDescription(names); + + // add the qualifiers (to the appropriate side) + cached = cached_under.Qualify(qualifiers); + } } - } return cached; } -std::string GetPlainDescription(NameCache &names, const Type &type) { +std::string +GetPlainDescription(NameCache& names, const Type& type) +{ std::ostringstream os; os << '"' << type.GetDescription(names) << '"'; return os.str(); } -std::string GetTypedefDescription(NameCache &names, const Type &given) { +std::string +GetTypedefDescription(NameCache& names, const Type& given) +{ std::ostringstream os; std::vector typedefs; - const Type &type = given.ResolveTypedef(typedefs); + const Type& type = given.ResolveTypedef(typedefs); for (auto td : typedefs) os << std::quoted(td) << " = "; os << GetPlainDescription(names, type); @@ -181,74 +201,99 @@ std::string GetTypedefDescription(NameCache &names, const Type &given) { constexpr size_t INDENT_INCREMENT = 2; -void Print(const Comparison &comparison, const Outcomes &outcomes, Seen &seen, - NameCache &names, std::ostream &os, size_t indent) { - const auto *lhs = comparison.first; - const auto *rhs = comparison.second; - if (!rhs) { - os << GetPlainDescription(names, *lhs) << " was removed\n"; - return; - } - if (!lhs) { - os << GetPlainDescription(names, *rhs) << " was added\n"; - return; - } - bool td = lhs->GetKind() == BTF_KIND_TYPEDEF - || rhs->GetKind() == BTF_KIND_TYPEDEF; +void +Print(const Comparison& comparison, + const Outcomes& outcomes, + Seen& seen, + NameCache& names, + std::ostream& os, + size_t indent) +{ + const auto* lhs = comparison.first; + const auto* rhs = comparison.second; + if (!rhs) + { + os << GetPlainDescription(names, *lhs) << " was removed\n"; + return; + } + if (!lhs) + { + os << GetPlainDescription(names, *rhs) << " was added\n"; + return; + } + bool td = + lhs->GetKind() == BTF_KIND_TYPEDEF || rhs->GetKind() == BTF_KIND_TYPEDEF; const std::string lhs_descr = td ? GetTypedefDescription(names, *lhs) - : GetPlainDescription(names, *lhs); + : GetPlainDescription(names, *lhs); const std::string rhs_descr = td ? GetTypedefDescription(names, *rhs) - : GetPlainDescription(names, *rhs); + : GetPlainDescription(names, *rhs); if (lhs_descr == rhs_descr) os << lhs_descr << " changed"; else os << "changed from " << lhs_descr << " to " << rhs_descr; - const auto &details = outcomes.find(comparison)->second; + const auto& details = outcomes.find(comparison)->second; auto insertion = seen.insert({comparison, false}); - if (!insertion.second) { - if (!insertion.first->second) - os << " (being reported)"; - else if (!details.empty()) - os << " (already reported)"; - } + if (!insertion.second) + { + if (!insertion.first->second) + os << " (being reported)"; + else if (!details.empty()) + os << " (already reported)"; + } os << '\n'; - if (insertion.second) { - Print(details, outcomes, seen, names, os, indent + INDENT_INCREMENT); - insertion.first->second = true; - } + if (insertion.second) + { + Print(details, outcomes, seen, names, os, indent + INDENT_INCREMENT); + insertion.first->second = true; + } // paragraph spacing if (!indent) os << '\n'; } -void Print(const Diff &details, const Outcomes &outcomes, Seen &seen, - NameCache &names, std::ostream &os, size_t indent) { - for (const auto &detail : details) { - os << std::string(indent, ' ') << detail.text_; - if (!detail.edge_) { - os << '\n'; - } else { - os << ' '; - Print(detail.edge_.value(), outcomes, seen, names, os, indent); +void +Print(const Diff& details, + const Outcomes& outcomes, + Seen& seen, + NameCache& names, + std::ostream& os, + size_t indent) +{ + for (const auto& detail : details) + { + os << std::string(indent, ' ') << detail.text_; + if (!detail.edge_) + { + os << '\n'; + } + else + { + os << ' '; + Print(detail.edge_.value(), outcomes, seen, names, os, indent); + } } - } } -const Type &Type::GetTypeAtIndex(size_t index) const { +const Type& +Type::GetTypeAtIndex(size_t index) const +{ m_assert(index < types_.size(), "Index out of bounds."); return *(types_[index].get()); } -std::string QualifiersMessage(Kind qualifier, const std::string &action) { +std::string +QualifiersMessage(Kind qualifier, const std::string& action) +{ std::ostringstream os; os << "qualifier " << kKindNames[qualifier] << ' ' << action; return os.str(); } -Result Type::CompareSymbols( - const std::map &lhs, - const std::map &rhs, - Outcomes &outcomes) { +Result +Type::CompareSymbols(const std::map& lhs, + const std::map& rhs, + Outcomes& outcomes) +{ Result result; State state(outcomes); auto lit = lhs.begin(); @@ -258,56 +303,76 @@ Result Type::CompareSymbols( // without BTF information may have changed type. // // NOTE: this currently happens for all global variables - while (lit != lhs.end() || rit != rhs.end()) { - if (rit == rhs.end() || (lit != lhs.end() && lit->first < rit->first)) { - // removed - if (lit->second) { - auto diff = Removed(*lit->second, state); - result.AddDiff("symbol", diff); - } else { - std::ostringstream os; - os << "symbol " << std::quoted(lit->first) - << " (of unknown type) was removed"; - result.AddDiff(os.str()); - } - ++lit; - } else if (lit == lhs.end() || (rit != rhs.end() && lit->first > rit->first)) { - // added - if (rit->second) { - auto diff = Added(*rit->second, state); - result.AddDiff("symbol", diff); - } else { - std::ostringstream os; - os << "symbol " << std::quoted(rit->first) - << " (if unknown type) was added"; - result.AddDiff(os.str()); - } - ++rit; - } else { - // in both - if (lit->second && rit->second) { - auto diff = Compare(*lit->second, *rit->second, state); - result.MaybeAddDiff("symbol", diff); - } else { - std::ostringstream os; - os << "symbol " << std::quoted(lit->first) - << " (of unknown type) may have changed"; - result.AddDiff(os.str()); - } - ++lit; - ++rit; + while (lit != lhs.end() || rit != rhs.end()) + { + if (rit == rhs.end() || (lit != lhs.end() && lit->first < rit->first)) + { + // removed + if (lit->second) + { + auto diff = Removed(*lit->second, state); + result.AddDiff("symbol", diff); + } + else + { + std::ostringstream os; + os << "symbol " << std::quoted(lit->first) + << " (of unknown type) was removed"; + result.AddDiff(os.str()); + } + ++lit; + } + else if (lit == lhs.end() + || (rit != rhs.end() && lit->first > rit->first)) + { + // added + if (rit->second) + { + auto diff = Added(*rit->second, state); + result.AddDiff("symbol", diff); + } + else + { + std::ostringstream os; + os << "symbol " << std::quoted(rit->first) + << " (if unknown type) was added"; + result.AddDiff(os.str()); + } + ++rit; + } + else + { + // in both + if (lit->second && rit->second) + { + auto diff = Compare(*lit->second, *rit->second, state); + result.MaybeAddDiff("symbol", diff); + } + else + { + std::ostringstream os; + os << "symbol " << std::quoted(lit->first) + << " (of unknown type) may have changed"; + result.AddDiff(os.str()); + } + ++lit; + ++rit; + } } - } return result; } -Comparison Type::Removed(const Type &lhs, State &state) { +Comparison +Type::Removed(const Type& lhs, State& state) +{ Comparison comparison{&lhs, nullptr}; state.outcomes.insert({comparison, {}}); return comparison; } -Comparison Type::Added(const Type &rhs, State &state) { +Comparison +Type::Added(const Type& rhs, State& state) +{ Comparison comparison{nullptr, &rhs}; state.outcomes.insert({comparison, {}}); return comparison; @@ -320,157 +385,196 @@ Comparison Type::Added(const Type &rhs, State &state) { * 1. equals = true; perhaps only tentative edge differences * 2. equals = false; at least one definitive node or edge difference * - * On the first visit to a node we can put a placeholder in, the equals value is - * irrelevant, the diff may contain local and edge differences. If an SCC + * On the first visit to a node we can put a placeholder in, the equals value + * is irrelevant, the diff may contain local and edge differences. If an SCC * contains only internal edge differences (and equivalently equals is true) * then the differences can all (eventually) be discarded. * * On exit from the first visit to a node, equals reflects the tree of - * comparisons below that node in the DFS and similarly, the diff graph starting - * from the node contains a subtree of this tree plus potentially edges to - * existing nodes to the side or below (already visited SCCs, sharing), or above - * (back links forming cycles). + * comparisons below that node in the DFS and similarly, the diff graph + * starting from the node contains a subtree of this tree plus potentially + * edges to existing nodes to the side or below (already visited SCCs, + * sharing), or above (back links forming cycles). * * When an SCC is closed, all equals implies deleting all diffs, any false * implies updating all to false. * * On subsequent visits to a node, there are 2 cases. The node is still open: - * return true and an edge diff. The node is closed, return the stored value and - * an edge diff. + * return true and an edge diff. The node is closed, return the stored value + * and an edge diff. */ -std::pair> Type::Compare( - const Type &lhs, const Type &rhs, Type::State &state) { +std::pair> +Type::Compare(const Type& lhs, const Type& rhs, Type::State& state) +{ Comparison comparison{&lhs, &rhs}; // 1. Check if the comparison has an already known result. - if (state.known_equal.count(comparison)) { - // Already visited and closed. Equal. - return {true, {}}; - } - if (state.outcomes.count(comparison)) { - // Already visited and closed. Different. - return {false, {comparison}}; - } + if (state.known_equal.count(comparison)) + { + // Already visited and closed. Equal. + return {true, {}}; + } + if (state.outcomes.count(comparison)) + { + // Already visited and closed. Different. + return {false, {comparison}}; + } // Either open or not visited at all // 2. Record node with Strongly-Connected Component finder. auto handle = state.scc.Open({comparison, {}}); - if (!handle) { - // Already open. - // - // Return a dummy true outcome and some tentative diffs. The diffs may end - // up not being used and, while it would be nice to be lazier, they encode - // all the cycling-breaking edges needed to recreate a full diff structure. - return {true, {comparison}}; - } + if (!handle) + { + // Already open. + // + // Return a dummy true outcome and some tentative diffs. The diffs may + // end up not being used and, while it would be nice to be lazier, they + // encode all the cycling-breaking edges needed to recreate a full diff + // structure. + return {true, {comparison}}; + } // Comparison opened, need to close it before returning. Result result; std::set lhs_quals; std::set rhs_quals; - const Type &l = lhs.ResolveQualifiers(lhs_quals); - const Type &r = rhs.ResolveQualifiers(rhs_quals); - if (!lhs_quals.empty() || !rhs_quals.empty()) { - // 3.1 Qualified type difference. - auto lit = lhs_quals.begin(); - auto rit = rhs_quals.begin(); - auto lend = lhs_quals.end(); - auto rend = rhs_quals.end(); - while (lit != lend || rit != rend) { - if (rit == rend || (lit != lend && *lit < *rit)) { - result.AddDiff(QualifiersMessage(*lit, "removed")); - ++lit; - } else if (lit == lend || (rit != rend && *lit > *rit)) { - result.AddDiff(QualifiersMessage(*rit, "added")); - ++rit; - } else { - ++lit; - ++rit; - } + const Type& l = lhs.ResolveQualifiers(lhs_quals); + const Type& r = rhs.ResolveQualifiers(rhs_quals); + if (!lhs_quals.empty() || !rhs_quals.empty()) + { + // 3.1 Qualified type difference. + auto lit = lhs_quals.begin(); + auto rit = rhs_quals.begin(); + auto lend = lhs_quals.end(); + auto rend = rhs_quals.end(); + while (lit != lend || rit != rend) + { + if (rit == rend || (lit != lend && *lit < *rit)) + { + result.AddDiff(QualifiersMessage(*lit, "removed")); + ++lit; + } + else if (lit == lend || (rit != rend && *lit > *rit)) + { + result.AddDiff(QualifiersMessage(*rit, "added")); + ++rit; + } + else + { + ++lit; + ++rit; + } + } + const auto comp = Compare(l, r, state); + result.MaybeAddDiff("underlying type", comp); + } + else if (l.GetKind() == BTF_KIND_TYPEDEF || r.GetKind() == BTF_KIND_TYPEDEF) + { + // 3.2 Typedef difference. + std::vector l_typedefs; + std::vector r_typedefs; + const Type& l_ref = l.ResolveTypedef(l_typedefs); + const Type& r_ref = r.ResolveTypedef(r_typedefs); + const auto comp = Compare(l_ref, r_ref, state); + result.MaybeAddDiff("via typedefs", comp); + } + else if (typeid(l) != typeid(r)) + { + // 4. Incomparable. + result.equals_ = false; + } + else + { + // 5. Actually compare with dynamic type dispatch. + result = l.Equals(r, state); } - const auto comp = Compare(l, r, state); - result.MaybeAddDiff("underlying type", comp); - } else if (l.GetKind() == BTF_KIND_TYPEDEF - || r.GetKind() == BTF_KIND_TYPEDEF) { - // 3.2 Typedef difference. - std::vector l_typedefs; - std::vector r_typedefs; - const Type &l_ref = l.ResolveTypedef(l_typedefs); - const Type &r_ref = r.ResolveTypedef(r_typedefs); - const auto comp = Compare(l_ref, r_ref, state); - result.MaybeAddDiff("via typedefs", comp); - } else if (typeid(l) != typeid(r)) { - // 4. Incomparable. - result.equals_ = false; - } else { - // 5. Actually compare with dynamic type dispatch. - result = l.Equals(r, state); - } // 6. Update result and check for a complete Strongly-Connected Component. - auto comparisons = state.scc.Close(handle.value(), - [&result](Outcomes::value_type &p) { - p.second = result.details_; - }); - if (!comparisons.empty()) { - // Closed SCC. - // - // Note that result now incorporates every inequality and difference in the - // SCC via the DFS spanning tree. - if (result.equals_) { - // Same. Record equalities. - for (auto &c : comparisons) - state.known_equal.insert(c.first); - return {true, {}}; - } else { - // Different. Record diffs. - state.outcomes.insert(std::make_move_iterator(comparisons.begin()), - std::make_move_iterator(comparisons.end())); + auto comparisons = + state.scc.Close(handle.value(), [&result](Outcomes::value_type& p) { + p.second = result.details_; + }); + if (!comparisons.empty()) + { + // Closed SCC. + // + // Note that result now incorporates every inequality and difference in + // the SCC via the DFS spanning tree. + if (result.equals_) + { + // Same. Record equalities. + for (auto& c : comparisons) + state.known_equal.insert(c.first); + return {true, {}}; + } + else + { + // Different. Record diffs. + state.outcomes.insert(std::make_move_iterator(comparisons.begin()), + std::make_move_iterator(comparisons.end())); + } } - } // Note that both equals and diff are tentative iff comparison is open. return {result.equals_, {comparison}}; } -Name Void::MakeDescription(NameCache &names) const { +Name +Void::MakeDescription(NameCache& names) const +{ return Name{"void"}; } -Name Ptr::MakeDescription(NameCache &names) const { - return GetTypeAtIndex(GetPointeeTypeId()).GetDescription(names).Add( - Side::LEFT, Precedence::POINTER, "*"); +Name +Ptr::MakeDescription(NameCache& names) const +{ + return GetTypeAtIndex(GetPointeeTypeId()) + .GetDescription(names) + .Add(Side::LEFT, Precedence::POINTER, "*"); } -Name Typedef::MakeDescription(NameCache &names) const { +Name +Typedef::MakeDescription(NameCache& names) const +{ return Name{GetName()}; } -Name Qualifier::MakeDescription(NameCache &names) const { - m_assert(false, "should not be called"); // NOLINT +Name +Qualifier::MakeDescription(NameCache& names) const +{ + m_assert(false, "should not be called"); // NOLINT return Name{GetName()}; } -Name Integer::MakeDescription(NameCache &names) const { +Name +Integer::MakeDescription(NameCache& names) const +{ return Name{GetName()}; } -Name Array::MakeDescription(NameCache &names) const { +Name +Array::MakeDescription(NameCache& names) const +{ std::ostringstream os; os << '[' << GetNumberOfElements() << ']'; - return GetTypeAtIndex(GetElementTypeId()).GetDescription(names).Add( - Side::RIGHT, Precedence::ARRAY_FUNCTION, os.str()); + return GetTypeAtIndex(GetElementTypeId()) + .GetDescription(names) + .Add(Side::RIGHT, Precedence::ARRAY_FUNCTION, os.str()); } -Name StructUnion::MakeDescription(NameCache &names) const { +Name +StructUnion::MakeDescription(NameCache& names) const +{ std::ostringstream os; - os << (GetKind() == BTF_KIND_STRUCT ? "struct" : "union") - << ' ' << (GetName().empty() ? "" : GetName()); + os << (GetKind() == BTF_KIND_STRUCT ? "struct" : "union") << ' ' + << (GetName().empty() ? "" : GetName()); return Name{os.str()}; } -Name Enumeration::MakeDescription(NameCache &names) const { +Name +Enumeration::MakeDescription(NameCache& names) const +{ std::ostringstream os; os << "enum " << (GetName().empty() ? "" : GetName()); if (GetEnums().empty()) @@ -478,499 +582,605 @@ Name Enumeration::MakeDescription(NameCache &names) const { return Name{os.str()}; } -Name ForwardDeclaration::MakeDescription(NameCache &names) const { +Name +ForwardDeclaration::MakeDescription(NameCache& names) const +{ std::ostringstream os; os << GetFwdKind() << ' ' << GetName() << ""; return Name{os.str()}; } -Name FunctionPrototype::MakeDescription(NameCache &names) const { +Name +FunctionPrototype::MakeDescription(NameCache& names) const +{ std::ostringstream os; os << '('; bool sep = false; - for (const auto &p : GetParameters()) { - if (sep) - os << ", "; - else - sep = true; - const auto &arg_descr = GetTypeAtIndex(p.typeId_).GetDescription(names); - if (p.name_.empty()) - os << arg_descr; - else - os << arg_descr.Add(Side::LEFT, Precedence::ATOMIC, p.name_); - } + for (const auto& p : GetParameters()) + { + if (sep) + os << ", "; + else + sep = true; + const auto& arg_descr = GetTypeAtIndex(p.typeId_).GetDescription(names); + if (p.name_.empty()) + os << arg_descr; + else + os << arg_descr.Add(Side::LEFT, Precedence::ATOMIC, p.name_); + } os << ')'; - return GetTypeAtIndex(GetReturnTypeId()).GetDescription(names).Add( - Side::RIGHT, Precedence::ARRAY_FUNCTION, os.str()); + return GetTypeAtIndex(GetReturnTypeId()) + .GetDescription(names) + .Add(Side::RIGHT, Precedence::ARRAY_FUNCTION, os.str()); } -Name Variable::MakeDescription(NameCache &names) const { - return GetTypeAtIndex(GetVarTypeId()).GetDescription(names).Add( - Side::LEFT, Precedence::ATOMIC, GetName()); +Name +Variable::MakeDescription(NameCache& names) const +{ + return GetTypeAtIndex(GetVarTypeId()) + .GetDescription(names) + .Add(Side::LEFT, Precedence::ATOMIC, GetName()); } -Name Function::MakeDescription(NameCache &names) const { - return GetTypeAtIndex(GetReferredTypeId()).GetDescription(names).Add( - Side::LEFT, Precedence::ATOMIC, GetName()); +Name +Function::MakeDescription(NameCache& names) const +{ + return GetTypeAtIndex(GetReferredTypeId()) + .GetDescription(names) + .Add(Side::LEFT, Precedence::ATOMIC, GetName()); } -Name DataSection::MakeDescription(NameCache &names) const { +Name +DataSection::MakeDescription(NameCache& names) const +{ // NOTE: not yet encountered in the wild return Name{"Unimplemented"}; } -Name ElfSymbol::MakeDescription(NameCache &names) const { +Name +ElfSymbol::MakeDescription(NameCache& names) const +{ return Name{symbol_->get_name()}; } -Result Void::Equals(const Type &other, State &state) const { +Result +Void::Equals(const Type& other, State& state) const +{ return {}; } -Result Ptr::Equals(const Type &other, State &state) const { +Result +Ptr::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); const auto ref_diff = Compare(GetTypeAtIndex(GetPointeeTypeId()), - o.GetTypeAtIndex(o.GetPointeeTypeId()), state); + o.GetTypeAtIndex(o.GetPointeeTypeId()), + state); result.MaybeAddDiff("pointed-to type", ref_diff); return result; } -Result Typedef::Equals(const Type &other, State &state) const { - m_assert(false, "should not be called"); // NOLINT +Result +Typedef::Equals(const Type& other, State& state) const +{ + m_assert(false, "should not be called"); // NOLINT return {}; } -Result Qualifier::Equals(const Type &other, State &state) const { - m_assert(false, "should not be called"); // NOLINT +Result +Qualifier::Equals(const Type& other, State& state) const +{ + m_assert(false, "should not be called"); // NOLINT return {}; } -Result Integer::Equals(const Type &other, State &state) const { +Result +Integer::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); - if (isBool() != o.isBool()) { - result.AddDiff(isBool() ? "the first one is a boolean" - : "the second one is a boolean"); - } - if (isSigned() != o.isSigned()) { - result.AddDiff(isSigned() ? "the first one is signed" - : "the second one is signed"); - } - if (isChar() != o.isChar()) { - result.AddDiff(isChar() ? "the first one is a char" - : "the second one is a char"); - } + if (isBool() != o.isBool()) + { + result.AddDiff(isBool() ? "the first one is a boolean" + : "the second one is a boolean"); + } + if (isSigned() != o.isSigned()) + { + result.AddDiff(isSigned() ? "the first one is signed" + : "the second one is signed"); + } + if (isChar() != o.isChar()) + { + result.AddDiff(isChar() ? "the first one is a char" + : "the second one is a char"); + } result.MaybeAddDiff("offset", GetOffset(), o.GetOffset()); result.MaybeAddDiff("bit size", GetBitSize(), o.GetBitSize()); - if (GetBitSize() != GetByteSize() * 8 && - o.GetBitSize() != o.GetByteSize() * 8) + if (GetBitSize() != GetByteSize() * 8 + && o.GetBitSize() != o.GetByteSize() * 8) result.MaybeAddDiff("byte size", GetByteSize(), o.GetByteSize()); return result; } -Result Array::Equals(const Type &other, State &state) const { +Result +Array::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); - result.MaybeAddDiff("number of elements", - GetNumberOfElements(), o.GetNumberOfElements()); - const auto index_type_diff = - Compare(GetTypeAtIndex(GetIndexTypeId()), - o.GetTypeAtIndex(o.GetIndexTypeId()), state); + result.MaybeAddDiff( + "number of elements", GetNumberOfElements(), o.GetNumberOfElements()); + const auto index_type_diff = Compare(GetTypeAtIndex(GetIndexTypeId()), + o.GetTypeAtIndex(o.GetIndexTypeId()), + state); result.MaybeAddDiff("index type", index_type_diff); const auto element_type_diff = Compare(GetTypeAtIndex(GetElementTypeId()), - o.GetTypeAtIndex(o.GetElementTypeId()), state); + o.GetTypeAtIndex(o.GetElementTypeId()), + state); result.MaybeAddDiff("element type", element_type_diff); return result; } -Result StructUnion::Equals(const Type &other, State &state) const { +Result +StructUnion::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); - if (GetKind() != o.GetKind()) { - result.AddDiff(GetKind() == BTF_KIND_STRUCT - ? "changed from struct to union" - : "changed from union to struct"); - } + if (GetKind() != o.GetKind()) + { + result.AddDiff(GetKind() == BTF_KIND_STRUCT + ? "changed from struct to union" + : "changed from union to struct"); + } result.MaybeAddDiff("byte size", GetByteSize(), o.GetByteSize()); - const auto &members1 = GetMembers(); - const auto &members2 = o.GetMembers(); + const auto& members1 = GetMembers(); + const auto& members2 = o.GetMembers(); std::set visited_members; - for (const auto &m1 : members1) { - visited_members.insert(m1.first); - auto iter = members2.find(m1.first); - if (iter == members2.end()) { - std::ostringstream os; - os << "member " << std::quoted(m1.first) << " of type"; - auto diff = Removed(GetTypeAtIndex(m1.second.typeId_), state); - result.AddDiff(os.str(), diff); - } else { - result.MaybeAddDiff([&](std::ostream &os) { - os << "member " << std::quoted(m1.first) << " offset"; - }, m1.second.offset_, iter->second.offset_); - result.MaybeAddDiff([&](std::ostream &os) { - os << "member " << std::quoted(m1.first) << " bitfield size"; - }, m1.second.bitfieldSize_, iter->second.bitfieldSize_); - const auto sub_diff = - Compare(GetTypeAtIndex(m1.second.typeId_), - o.GetTypeAtIndex(iter->second.typeId_), state); - result.MaybeAddDiff([&](std::ostream &os) { - os << "member " << std::quoted(m1.first) << " type"; - }, sub_diff); + for (const auto& m1 : members1) + { + visited_members.insert(m1.first); + auto iter = members2.find(m1.first); + if (iter == members2.end()) + { + std::ostringstream os; + os << "member " << std::quoted(m1.first) << " of type"; + auto diff = Removed(GetTypeAtIndex(m1.second.typeId_), state); + result.AddDiff(os.str(), diff); + } + else + { + result.MaybeAddDiff( + [&](std::ostream& os) { + os << "member " << std::quoted(m1.first) << " offset"; + }, + m1.second.offset_, + iter->second.offset_); + result.MaybeAddDiff( + [&](std::ostream& os) { + os << "member " << std::quoted(m1.first) << " bitfield size"; + }, + m1.second.bitfieldSize_, + iter->second.bitfieldSize_); + const auto sub_diff = Compare(GetTypeAtIndex(m1.second.typeId_), + o.GetTypeAtIndex(iter->second.typeId_), + state); + result.MaybeAddDiff( + [&](std::ostream& os) { + os << "member " << std::quoted(m1.first) << " type"; + }, + sub_diff); + } } - } - for (const auto &m2 : members2) { - if (visited_members.find(m2.first) == visited_members.end()) { - std::ostringstream os; - os << "member " << std::quoted(m2.first) << " of type"; - auto diff = Added(o.GetTypeAtIndex(m2.second.typeId_), state); - result.AddDiff(os.str(), diff); + for (const auto& m2 : members2) + { + if (visited_members.find(m2.first) == visited_members.end()) + { + std::ostringstream os; + os << "member " << std::quoted(m2.first) << " of type"; + auto diff = Added(o.GetTypeAtIndex(m2.second.typeId_), state); + result.AddDiff(os.str(), diff); + } } - } return result; } -Result Enumeration::Equals(const Type &other, State &state) const { +Result +Enumeration::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); result.MaybeAddDiff("byte size", GetByteSize(), o.GetByteSize()); - const auto &enums1 = GetEnums(); - const auto &enums2 = o.GetEnums(); + const auto& enums1 = GetEnums(); + const auto& enums2 = o.GetEnums(); std::set visited_enums; - for (const auto &e1 : enums1) { - visited_enums.insert(e1.first); - auto iter = enums2.find(e1.first); - if (iter == enums2.end()) { - std::ostringstream os; - os << "enumerator " << std::quoted(e1.first) - << " (" << e1.second << ") was removed"; - result.AddDiff(os.str()); - } else { - result.MaybeAddDiff([&](std::ostream &os) { - os << "enumerator " << std::quoted(e1.first) << " value"; - }, e1.second, iter->second); + for (const auto& e1 : enums1) + { + visited_enums.insert(e1.first); + auto iter = enums2.find(e1.first); + if (iter == enums2.end()) + { + std::ostringstream os; + os << "enumerator " << std::quoted(e1.first) << " (" << e1.second + << ") was removed"; + result.AddDiff(os.str()); + } + else + { + result.MaybeAddDiff( + [&](std::ostream& os) { + os << "enumerator " << std::quoted(e1.first) << " value"; + }, + e1.second, + iter->second); + } } - } - for (const auto &e2 : enums2) { - if (visited_enums.find(e2.first) == visited_enums.end()) { - std::ostringstream os; - os << "enumerator " << std::quoted(e2.first) - << " (" << e2.second << ") was added"; - result.AddDiff(os.str()); + for (const auto& e2 : enums2) + { + if (visited_enums.find(e2.first) == visited_enums.end()) + { + std::ostringstream os; + os << "enumerator " << std::quoted(e2.first) << " (" << e2.second + << ") was added"; + result.AddDiff(os.str()); + } } - } return result; } -Result ForwardDeclaration::Equals(const Type &other, State &state) const { +Result +ForwardDeclaration::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); result.MaybeAddDiff("kind", GetFwdKind(), o.GetFwdKind()); return result; } -Result Function::Equals(const Type &other, State &state) const { +Result +Function::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); result.MaybeAddDiff("linkage", GetLinkage(), o.GetLinkage()); - const auto func_proto_diff = - Compare(GetTypeAtIndex(GetReferredTypeId()), - o.GetTypeAtIndex(o.GetReferredTypeId()), state); + const auto func_proto_diff = Compare(GetTypeAtIndex(GetReferredTypeId()), + o.GetTypeAtIndex(o.GetReferredTypeId()), + state); result.MaybeAddDiff("type", func_proto_diff); return result; } -Result FunctionPrototype::Equals(const Type &other, State &state) const { +Result +FunctionPrototype::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); - const auto return_type_diff = - Compare(GetTypeAtIndex(GetReturnTypeId()), - o.GetTypeAtIndex(o.GetReturnTypeId()), state); + const auto return_type_diff = Compare(GetTypeAtIndex(GetReturnTypeId()), + o.GetTypeAtIndex(o.GetReturnTypeId()), + state); result.MaybeAddDiff("return type", return_type_diff); - const auto ¶meters1 = GetParameters(); - const auto ¶meters2 = o.GetParameters(); + const auto& parameters1 = GetParameters(); + const auto& parameters2 = o.GetParameters(); size_t min = std::min(parameters1.size(), parameters2.size()); - for (size_t i = 0; i < min; ++i) { - const auto &p1 = parameters1.at(i); - const auto &p2 = parameters2.at(i); - const auto sub_diff = Compare(GetTypeAtIndex(p1.typeId_), - o.GetTypeAtIndex(p2.typeId_), state); - result.MaybeAddDiff([&](std::ostream &os) { - os << "parameter " << i + 1; - const auto &n1 = p1.name_; - const auto &n2 = p2.name_; - if (n1 == n2 && !n1.empty()) { - os << " (" << std::quoted(n1) << ")"; - } else if (n1 != n2) { - os << " ("; - if (!n1.empty()) os << "was " << std::quoted(n1); - if (!n1.empty() && !n2.empty()) os << ", "; - if (!n2.empty()) os << "now " << std::quoted(n2); - os << ")"; - } - os << " type"; - }, sub_diff); - } + for (size_t i = 0; i < min; ++i) + { + const auto& p1 = parameters1.at(i); + const auto& p2 = parameters2.at(i); + const auto sub_diff = Compare( + GetTypeAtIndex(p1.typeId_), o.GetTypeAtIndex(p2.typeId_), state); + result.MaybeAddDiff( + [&](std::ostream& os) { + os << "parameter " << i + 1; + const auto& n1 = p1.name_; + const auto& n2 = p2.name_; + if (n1 == n2 && !n1.empty()) + { + os << " (" << std::quoted(n1) << ")"; + } + else if (n1 != n2) + { + os << " ("; + if (!n1.empty()) + os << "was " << std::quoted(n1); + if (!n1.empty() && !n2.empty()) + os << ", "; + if (!n2.empty()) + os << "now " << std::quoted(n2); + os << ")"; + } + os << " type"; + }, + sub_diff); + } bool added = parameters1.size() < parameters2.size(); - const auto ¶meters = added ? parameters2 : parameters1; - for (size_t i = min; i < parameters.size(); ++i) { - const auto ¶meter = parameters.at(i); - std::ostringstream os; - os << "parameter " << i + 1; - if (!parameter.name_.empty()) - os << " (" << std::quoted(parameter.name_) << ")"; - os << " of type"; - const auto ¶meter_type = GetTypeAtIndex(parameter.typeId_); - auto diff = added ? Added(parameter_type, state) - : Removed(parameter_type, state); - result.AddDiff(os.str(), diff); - } + const auto& parameters = added ? parameters2 : parameters1; + for (size_t i = min; i < parameters.size(); ++i) + { + const auto& parameter = parameters.at(i); + std::ostringstream os; + os << "parameter " << i + 1; + if (!parameter.name_.empty()) + os << " (" << std::quoted(parameter.name_) << ")"; + os << " of type"; + const auto& parameter_type = GetTypeAtIndex(parameter.typeId_); + auto diff = added ? Added(parameter_type, state) + : Removed(parameter_type, state); + result.AddDiff(os.str(), diff); + } return result; } // NOTE: not yet encountered in the wild -Result Variable::Equals(const Type &other, State &state) const { +Result +Variable::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); result.MaybeAddDiff("linkage", GetLinkage(), o.GetLinkage()); const auto var_diff = Compare(GetTypeAtIndex(GetVarTypeId()), - o.GetTypeAtIndex(o.GetVarTypeId()), state); + o.GetTypeAtIndex(o.GetVarTypeId()), + state); result.MaybeAddDiff("type", var_diff); return result; } -Result DataSection::Equals(const Type &other, State &state) const { +Result +DataSection::Equals(const Type& other, State& state) const +{ Result result; result.AddDiff("Unimplemented"); // NOTE: not yet encountered in the wild - m_assert(false, "Unimplemented\n"); // NOLINT + m_assert(false, "Unimplemented\n"); // NOLINT return result; } -Result ElfSymbol::Equals(const Type &other, State &state) const { +Result +ElfSymbol::Equals(const Type& other, State& state) const +{ Result result; - const auto &o = other.as(); + const auto& o = other.as(); // TODO: compare ELF symbol attributes - const auto type_diff = Compare(GetTypeAtIndex(type_id_), - o.GetTypeAtIndex(o.type_id_), state); + const auto type_diff = + Compare(GetTypeAtIndex(type_id_), o.GetTypeAtIndex(o.type_id_), state); result.MaybeAddDiff("type", type_diff); return result; } -const Type &Type::ResolveQualifiers(std::set &qualifiers) const { - if (kind_ == BTF_KIND_ARRAY || kind_ == BTF_KIND_FUNC_PROTO) { - // There should be no qualifiers here. - qualifiers.clear(); - } +const Type& +Type::ResolveQualifiers(std::set& qualifiers) const +{ + if (kind_ == BTF_KIND_ARRAY || kind_ == BTF_KIND_FUNC_PROTO) + { + // There should be no qualifiers here. + qualifiers.clear(); + } return *this; } -const Type &Qualifier::ResolveQualifiers( - std::set &qualifiers) const { +const Type& +Qualifier::ResolveQualifiers(std::set& qualifiers) const +{ qualifiers.insert(GetKind()); return GetTypeAtIndex(GetQualifiedTypeId()).ResolveQualifiers(qualifiers); } -const Type &Type::ResolveTypedef( - std::vector &typedefs) const { +const Type& +Type::ResolveTypedef(std::vector& typedefs) const +{ return *this; } -const Type &Typedef::ResolveTypedef( - std::vector &typedefs) const { +const Type& +Typedef::ResolveTypedef(std::vector& typedefs) const +{ typedefs.push_back(GetName()); return GetTypeAtIndex(GetReferredTypeId()).ResolveTypedef(typedefs); } -std::ostream &operator<<(std::ostream &os, const Type &bt) { +std::ostream& +operator<<(std::ostream& os, const Type& bt) +{ auto name = bt.GetName(); - os << kRawKindNames[bt.GetKind()] - << " '" << (name.empty() ? "(anon)" : name) << '\''; + os << kRawKindNames[bt.GetKind()] << " '" << (name.empty() ? "(anon)" : name) + << '\''; return os; } -std::ostream &operator<<(std::ostream &os, const Ptr &bp) { - os << static_cast(bp) - << " type_id=" << bp.GetPointeeTypeId() +std::ostream& +operator<<(std::ostream& os, const Ptr& bp) +{ + os << static_cast(bp) << " type_id=" << bp.GetPointeeTypeId() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Typedef &bp) { - os << static_cast(bp) - << " type_id=" << bp.GetReferredTypeId() +std::ostream& +operator<<(std::ostream& os, const Typedef& bp) +{ + os << static_cast(bp) << " type_id=" << bp.GetReferredTypeId() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Qualifier &bp) { - os << static_cast(bp) - << " type_id=" << bp.GetQualifiedTypeId() +std::ostream& +operator<<(std::ostream& os, const Qualifier& bp) +{ + os << static_cast(bp) << " type_id=" << bp.GetQualifiedTypeId() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Integer &bi) { - os << static_cast(bi) - << " size=" << bi.GetByteSize() - << " bits_offset=" << bi.GetOffset() - << " nr_bits=" << bi.GetBitSize() - << " bool=" << bi.isBool() - << " char=" << bi.isChar() - << " signed=" << bi.isSigned() - << '\n'; +std::ostream& +operator<<(std::ostream& os, const Integer& bi) +{ + os << static_cast(bi) << " size=" << bi.GetByteSize() + << " bits_offset=" << bi.GetOffset() << " nr_bits=" << bi.GetBitSize() + << " bool=" << bi.isBool() << " char=" << bi.isChar() + << " signed=" << bi.isSigned() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Array &ba) { - os << static_cast(ba) - << " type_id=" << ba.GetElementTypeId() - << " index_type_id=" << ba.GetIndexTypeId() - << " nr_elems=" << ba.GetNumberOfElements() - << '\n'; - return os; - } +std::ostream& +operator<<(std::ostream& os, const Array& ba) +{ + os << static_cast(ba) << " type_id=" << ba.GetElementTypeId() + << " index_type_id=" << ba.GetIndexTypeId() + << " nr_elems=" << ba.GetNumberOfElements() << '\n'; + return os; +} -std::ostream &operator<<(std::ostream &os, const StructUnion &bsu) { - os << static_cast(bsu) - << " size=" << bsu.GetByteSize() +std::ostream& +operator<<(std::ostream& os, const StructUnion& bsu) +{ + os << static_cast(bsu) << " size=" << bsu.GetByteSize() << " vlen=" << bsu.GetMembers().size() << '\n'; - for (const auto &member : bsu.GetMembers()) { - os << "\t'" << member.first << '\'' - << " type_id=" << member.second.typeId_ - << " bits_offset=" << member.second.offset_; - if (member.second.bitfieldSize_) - os << " bitfield_size=" << member.second.bitfieldSize_; - os << '\n'; - } + for (const auto& member : bsu.GetMembers()) + { + os << "\t'" << member.first << '\'' + << " type_id=" << member.second.typeId_ + << " bits_offset=" << member.second.offset_; + if (member.second.bitfieldSize_) + os << " bitfield_size=" << member.second.bitfieldSize_; + os << '\n'; + } return os; } -std::ostream &operator<<(std::ostream &os, const Enumeration &be) { - os << static_cast(be) - << " size=" << be.GetByteSize() - << " vlen=" << be.GetEnums().size() - << '\n'; - for (const auto &e : be.GetEnums()) { - os << "\t'" << e.first << "' val=" << e.second << '\n'; - } +std::ostream& +operator<<(std::ostream& os, const Enumeration& be) +{ + os << static_cast(be) << " size=" << be.GetByteSize() + << " vlen=" << be.GetEnums().size() << '\n'; + for (const auto& e : be.GetEnums()) + { + os << "\t'" << e.first << "' val=" << e.second << '\n'; + } return os; } -std::ostream &operator<<(std::ostream &os, const ForwardDeclaration &bfd) { - os << static_cast(bfd) - << " fwd_kind=" << bfd.GetFwdKind() +std::ostream& +operator<<(std::ostream& os, const ForwardDeclaration& bfd) +{ + os << static_cast(bfd) << " fwd_kind=" << bfd.GetFwdKind() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Function &bf) { - os << static_cast(bf) - << " type_id=" << bf.GetReferredTypeId() - << " linkage=" << bf.GetLinkage() - << '\n'; +std::ostream& +operator<<(std::ostream& os, const Function& bf) +{ + os << static_cast(bf) << " type_id=" << bf.GetReferredTypeId() + << " linkage=" << bf.GetLinkage() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const FunctionPrototype &bfp) { - os << static_cast(bfp) +std::ostream& +operator<<(std::ostream& os, const FunctionPrototype& bfp) +{ + os << static_cast(bfp) << " ret_type_id=" << bfp.GetReturnTypeId() - << " vlen=" << bfp.GetParameters().size() - << '\n'; - for (const auto ¶m : bfp.GetParameters()) { - os << "\t'" << (param.name_.empty() ? "(anon)" : param.name_) - << "' type_id=" << param.typeId_ << '\n'; - } + << " vlen=" << bfp.GetParameters().size() << '\n'; + for (const auto& param : bfp.GetParameters()) + { + os << "\t'" << (param.name_.empty() ? "(anon)" : param.name_) + << "' type_id=" << param.typeId_ << '\n'; + } return os; } -std::ostream &operator<<(std::ostream &os, const Variable &bv) { +std::ostream& +operator<<(std::ostream& os, const Variable& bv) +{ // NOTE: The odd comma is to match bpftool dump. - os << static_cast(bv) - << " type_id=" << bv.GetVarTypeId() - << ", linkage=" << bv.GetLinkage() - << '\n'; + os << static_cast(bv) << " type_id=" << bv.GetVarTypeId() + << ", linkage=" << bv.GetLinkage() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const DataSection &bds) { - os << static_cast(bds) - << " size=" << bds.GetByteSize() - << '\n'; - for (const auto &secinfo : bds.GetSecinfos()) { - os << "\ttype_id=" << secinfo.typeId_ - << " offset=" << secinfo.offset_ - << " size=" << secinfo.bytesize_ << '\n'; - } +std::ostream& +operator<<(std::ostream& os, const DataSection& bds) +{ + os << static_cast(bds) << " size=" << bds.GetByteSize() << '\n'; + for (const auto& secinfo : bds.GetSecinfos()) + { + os << "\ttype_id=" << secinfo.typeId_ << " offset=" << secinfo.offset_ + << " size=" << secinfo.bytesize_ << '\n'; + } return os; } -std::ostream &operator<<(std::ostream &os, const ElfSymbol &bes) { - os << static_cast(bes); +std::ostream& +operator<<(std::ostream& os, const ElfSymbol& bes) +{ + os << static_cast(bes); // TODO: report ELF symbol attributes - os << " type=" << bes.GetTypeId() - << '\n'; + os << " type=" << bes.GetTypeId() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, ForwardDeclarationKind kind) { - switch (kind) { +std::ostream& +operator<<(std::ostream& os, ForwardDeclarationKind kind) +{ + switch (kind) + { case ForwardDeclarationKind::STRUCT: os << "struct"; break; case ForwardDeclarationKind::UNION: os << "union"; break; - } + } return os; } -std::ostream &operator<<(std::ostream &os, Variable::Linkage linkage) { +std::ostream& +operator<<(std::ostream& os, Variable::Linkage linkage) +{ auto ix = static_cast(linkage); return os << (ix < kVarLinkage.size() ? kVarLinkage[ix] : "(unknown)"); } -std::ostream &operator<<(std::ostream &os, Function::Linkage linkage) { +std::ostream& +operator<<(std::ostream& os, Function::Linkage linkage) +{ auto ix = static_cast(linkage); return os << (ix < kFunLinkage.size() ? kFunLinkage[ix] : "(unknown)"); } -Structs::Structs(const char *start, - std::unique_ptr env, - const abigail::symtab_reader::symtab_sptr tab, - const bool verbose) - : env_(std::move(env)), - tab_(tab), - verbose_(verbose) { - header_ = reinterpret_cast(start); +Structs::Structs(const char* start, + std::unique_ptr env, + const abigail::symtab_reader::symtab_sptr tab, + const bool verbose) + : env_(std::move(env)), tab_(tab), verbose_(verbose) +{ + header_ = reinterpret_cast(start); m_assert(header_->magic == 0xEB9F, "Magic field must be 0xEB9F for BTF"); - type_section_ = reinterpret_cast(start + header_->hdr_len + - header_->type_off); + type_section_ = reinterpret_cast(start + header_->hdr_len + + header_->type_off); str_section_ = start + header_->hdr_len + header_->str_off; // every btf_type struct in the type section has an implicit type id. @@ -979,13 +1189,15 @@ Structs::Structs(const char *start, // recognized type starting from id 1. types_.push_back(std::make_unique(types_, 0, "void", 0)); - if (verbose_) { - PrintHeader(); - } + if (verbose_) + { + PrintHeader(); + } BuildTypes(); - if (verbose_) { - PrintStringSection(); - } + if (verbose_) + { + PrintStringSection(); + } // NOTE: a whole bunch of Linux kernel symbols appear with duplicate (but not // necessarily identical) BTF type information @@ -993,366 +1205,439 @@ Structs::Structs(const char *start, // TODO: find a better way of resolving this bad_prefix_1_ = "__arm64_sys_"; bad_prefix_2_ = "__arm64_compat_sys_"; - bad_names_ = { - "arch_prctl_spec_ctrl_get", - "arch_prctl_spec_ctrl_set", - "ioremap_cache", - "kvm_arch_set_irq_inatomic", - "module_frob_arch_sections", - "vsnprintf" - }; + bad_names_ = {"arch_prctl_spec_ctrl_get", + "arch_prctl_spec_ctrl_set", + "ioremap_cache", + "kvm_arch_set_irq_inatomic", + "module_frob_arch_sections", + "vsnprintf"}; } -void Structs::PrintHeader() { +void +Structs::PrintHeader() +{ std::cout << "BTF header:\n" - << "\tmagic " << header_->magic - << ", version " << static_cast(header_->version) - << ", flags " << static_cast(header_->flags) - << ", hdr_len " << header_->hdr_len << "\n" - << "\ttype_off " << header_->type_off - << ", type_len " << header_->type_len << "\n" - << "\tstr_off " << header_->str_off - << ", str_len " << header_->str_len << "\n"; + << "\tmagic " << header_->magic << ", version " + << static_cast(header_->version) << ", flags " + << static_cast(header_->flags) << ", hdr_len " + << header_->hdr_len << "\n" + << "\ttype_off " << header_->type_off << ", type_len " + << header_->type_len << "\n" + << "\tstr_off " << header_->str_off << ", str_len " + << header_->str_len << "\n"; } // vlen: vector length, the number of struct/union members -std::map Structs::BuildMembers( - bool kflag, const btf_member *members, size_t vlen) { +std::map +Structs::BuildMembers(bool kflag, const btf_member* members, size_t vlen) +{ std::map result; int anonymous = 0; - for (size_t i = 0; i < vlen; ++i) { - const auto raw_offset = members[i].offset; - Member member{ - .typeId_ = members[i].type, - .offset_ = kflag ? BTF_MEMBER_BIT_OFFSET(raw_offset) : raw_offset, - .bitfieldSize_ = kflag ? BTF_MEMBER_BITFIELD_SIZE(raw_offset) : 0}; - std::string name = std::string(GetName(members[i].name_off)); - if (name.empty()) { - name = "anon member #" + std::to_string(anonymous); - ++anonymous; + for (size_t i = 0; i < vlen; ++i) + { + const auto raw_offset = members[i].offset; + Member member{ + .typeId_ = members[i].type, + .offset_ = kflag ? BTF_MEMBER_BIT_OFFSET(raw_offset) : raw_offset, + .bitfieldSize_ = kflag ? BTF_MEMBER_BITFIELD_SIZE(raw_offset) : 0}; + std::string name = std::string(GetName(members[i].name_off)); + if (name.empty()) + { + name = "anon member #" + std::to_string(anonymous); + ++anonymous; + } + result.emplace(name, member); } - result.emplace(name, member); - } return result; } // vlen: vector length, the number of enum values -std::map Structs::BuildEnums(const struct btf_enum *enums, - size_t vlen) { +std::map +Structs::BuildEnums(const struct btf_enum* enums, size_t vlen) +{ std::map result; - for (size_t i = 0; i < vlen; ++i) { - result.emplace(std::string(GetName(enums[i].name_off)), enums[i].val); - } + for (size_t i = 0; i < vlen; ++i) + { + result.emplace(std::string(GetName(enums[i].name_off)), enums[i].val); + } return result; } // vlen: vector length, the number of parameters -std::vector Structs::BuildParams(const struct btf_param *params, - size_t vlen) { +std::vector +Structs::BuildParams(const struct btf_param* params, size_t vlen) +{ std::vector result; result.reserve(vlen); - for (size_t i = 0; i < vlen; ++i) { - Parameter parameter{ - .name_ = std::string(GetName(params[i].name_off)), - .typeId_ = params[i].type}; - result.push_back(parameter); - } + for (size_t i = 0; i < vlen; ++i) + { + Parameter parameter{.name_ = std::string(GetName(params[i].name_off)), + .typeId_ = params[i].type}; + result.push_back(parameter); + } return result; } // vlen: vector length, the number of variables -std::vector Structs::BuildDatasec(const btf_type *type, - size_t vlen) { +std::vector +Structs::BuildDatasec(const btf_type* type, size_t vlen) +{ std::vector result; result.reserve(vlen); - const auto *secinfos = reinterpret_cast(type + 1); - for (size_t i = 0; i < vlen; ++i) { - Secinfo secinfo{.typeId_ = secinfos[i].type, - .offset_ = secinfos[i].offset, - .bytesize_ = secinfos[i].size}; - result.push_back(secinfo); - } + const auto* secinfos = reinterpret_cast(type + 1); + for (size_t i = 0; i < vlen; ++i) + { + Secinfo secinfo{.typeId_ = secinfos[i].type, + .offset_ = secinfos[i].offset, + .bytesize_ = secinfos[i].size}; + result.push_back(secinfo); + } return result; } -void Structs::BuildTypes() { - m_assert(!(header_->type_off & (sizeof(uint32_t) - 1)), "Unaligned type_off"); - if (header_->type_len == 0) { - std::cerr << "No types found"; - return; - } - if (verbose_) { - std::cout << "Type section:\n"; - } +void +Structs::BuildTypes() +{ + m_assert(!(header_->type_off & (sizeof(uint32_t) - 1)), + "Unaligned type_off"); + if (header_->type_len == 0) + { + std::cerr << "No types found"; + return; + } + if (verbose_) + { + std::cout << "Type section:\n"; + } - const char *curr = reinterpret_cast(type_section_); - const char *end = curr + header_->type_len; + const char* curr = reinterpret_cast(type_section_); + const char* end = curr + header_->type_len; uint32_t index = 1; - while (curr < end) { - const btf_type *t = reinterpret_cast(curr); - int type_size = BuildOneType(t, index); - m_assert(type_size > 0, "Could not identify BTF type"); - curr += type_size; - ++index; - } + while (curr < end) + { + const btf_type* t = reinterpret_cast(curr); + int type_size = BuildOneType(t, index); + m_assert(type_size > 0, "Could not identify BTF type"); + curr += type_size; + ++index; + } BuildElfSymbols(); } -int Structs::BuildOneType(const btf_type *t, uint32_t index) { +int +Structs::BuildOneType(const btf_type* t, uint32_t index) +{ const auto kind = BTF_INFO_KIND(t->info); const auto vlen = BTF_INFO_VLEN(t->info); // Data following the btf_type struct. - const void *data = reinterpret_cast(t + 1); + const void* data = reinterpret_cast(t + 1); m_assert(kind >= 0 && kind < NR_BTF_KINDS, "Unknown BTF kind"); - if (verbose_) std::cout << '[' << index << "] "; + if (verbose_) + std::cout << '[' << index << "] "; int type_size = sizeof(struct btf_type); - switch (kind) { - case BTF_KIND_INT: { - const auto bits = *reinterpret_cast(data); - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, - BTF_INT_ENCODING(bits), BTF_INT_OFFSET(bits), BTF_INT_BITS(bits), - t->size)); - if (verbose_) { - std::cout << types_.back()->as(); + switch (kind) + { + case BTF_KIND_INT: + { + const auto bits = *reinterpret_cast(data); + types_.push_back(std::make_unique(types_, + index, + GetName(t->name_off), + kind, + BTF_INT_ENCODING(bits), + BTF_INT_OFFSET(bits), + BTF_INT_BITS(bits), + t->size)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += sizeof(uint32_t); + break; } - type_size += sizeof(uint32_t); - break; - } - case BTF_KIND_PTR: { - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, t->type)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_PTR: + { + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + break; } - break; - } - case BTF_KIND_TYPEDEF: { - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, t->type)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_TYPEDEF: + { + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + break; } - break; - } case BTF_KIND_VOLATILE: case BTF_KIND_CONST: - case BTF_KIND_RESTRICT: { - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, t->type)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_RESTRICT: + { + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + break; } - break; - } - case BTF_KIND_ARRAY: { - const auto *array = reinterpret_cast(data); - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, array->type, - array->index_type, array->nelems)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_ARRAY: + { + const auto* array = reinterpret_cast(data); + types_.push_back(std::make_unique(types_, + index, + GetName(t->name_off), + kind, + array->type, + array->index_type, + array->nelems)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += sizeof(struct btf_array); + break; } - type_size += sizeof(struct btf_array); - break; - } case BTF_KIND_STRUCT: - case BTF_KIND_UNION: { - const bool kflag = BTF_INFO_KFLAG(t->info); - const auto *btf_members = reinterpret_cast(data); - const auto members = BuildMembers(kflag, btf_members, vlen); - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, t->size, members)); - if (verbose_) { - std::cout << types_.back()->as(); - } - type_size += vlen * sizeof(struct btf_member); - break; - } - case BTF_KIND_ENUM: { - const auto *enums = reinterpret_cast(data); - std::map enumerators = BuildEnums(enums, vlen); - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, - t->size, enumerators)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_UNION: + { + const bool kflag = BTF_INFO_KFLAG(t->info); + const auto* btf_members = reinterpret_cast(data); + const auto members = BuildMembers(kflag, btf_members, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->size, members)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_member); + break; } - type_size += vlen * sizeof(struct btf_enum); - break; - } - case BTF_KIND_FWD: { - const bool kflag = BTF_INFO_KFLAG(t->info); - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, kflag)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_ENUM: + { + const auto* enums = reinterpret_cast(data); + std::map enumerators = BuildEnums(enums, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->size, enumerators)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_enum); + break; } - break; - } - case BTF_KIND_FUNC: { - const auto name = GetName(t->name_off); - types_.push_back(std::make_unique( - types_, index, name, kind, t->type, - Function::Linkage(vlen))); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_FWD: + { + const bool kflag = BTF_INFO_KFLAG(t->info); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, kflag)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + break; } - bool inserted = btf_symbol_types_.insert({name, t->type}).second; - if (!inserted) { - // NOTE: duplicate BTF symbols could be considered a bug in pahole - // - // TODO: remove these checks once resolved - bool known = !name.compare(0, bad_prefix_1_.size(), bad_prefix_1_) || - !name.compare(0, bad_prefix_2_.size(), bad_prefix_2_) || - std::find(bad_names_.begin(), bad_names_.end(), name) != - bad_names_.end(); - m_assert(known, "Insertion failed, duplicate found in symbol map"); - (void)known; + case BTF_KIND_FUNC: + { + const auto name = GetName(t->name_off); + types_.push_back(std::make_unique( + types_, index, name, kind, t->type, Function::Linkage(vlen))); + if (verbose_) + { + std::cout << types_.back()->as(); + } + bool inserted = btf_symbol_types_.insert({name, t->type}).second; + if (!inserted) + { + // NOTE: duplicate BTF symbols could be considered a bug in pahole + // + // TODO: remove these checks once resolved + bool known = + !name.compare(0, bad_prefix_1_.size(), bad_prefix_1_) + || !name.compare(0, bad_prefix_2_.size(), bad_prefix_2_) + || std::find(bad_names_.begin(), bad_names_.end(), name) + != bad_names_.end(); + m_assert(known, "Insertion failed, duplicate found in symbol map"); + (void) known; + } + btf_symbols_.insert({name, types_.back().get()}); + break; } - btf_symbols_.insert({name, types_.back().get()}); - break; - } - case BTF_KIND_FUNC_PROTO: { - const auto *params = reinterpret_cast(data); - std::vector parameters = BuildParams(params, vlen); - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, t->type, - parameters)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_FUNC_PROTO: + { + const auto* params = reinterpret_cast(data); + std::vector parameters = BuildParams(params, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->type, parameters)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_param); + break; } - type_size += vlen * sizeof(struct btf_param); - break; - } - case BTF_KIND_VAR: { - // NOTE: not yet encountered in the wild - const auto *variable = reinterpret_cast(data); - const auto name = GetName(t->name_off); - types_.push_back(std::make_unique( - types_, index, name, kind, t->type, - Variable::Linkage(variable->linkage))); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_VAR: + { + // NOTE: not yet encountered in the wild + const auto* variable = reinterpret_cast(data); + const auto name = GetName(t->name_off); + types_.push_back( + std::make_unique(types_, + index, + name, + kind, + t->type, + Variable::Linkage(variable->linkage))); + if (verbose_) + { + std::cout << types_.back()->as(); + } + + bool inserted = btf_symbol_types_.insert({name, t->type}).second; + m_assert(inserted, "Insertion failed, duplicate found in symbol map"); + (void) inserted; + btf_symbols_.insert({name, types_.back().get()}); + + type_size += sizeof(struct btf_var); + break; } - - bool inserted = btf_symbol_types_.insert({name, t->type}).second; - m_assert(inserted, "Insertion failed, duplicate found in symbol map"); - (void)inserted; - btf_symbols_.insert({name, types_.back().get()}); - - type_size += sizeof(struct btf_var); - break; - } - case BTF_KIND_DATASEC: { - std::vector secinfos = BuildDatasec(t, vlen); - types_.push_back(std::make_unique( - types_, index, GetName(t->name_off), kind, t->size, - secinfos)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_DATASEC: + { + std::vector secinfos = BuildDatasec(t, vlen); + types_.push_back(std::make_unique( + types_, index, GetName(t->name_off), kind, t->size, secinfos)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_var_secinfo); } - type_size += vlen * sizeof(struct btf_var_secinfo); } - } return type_size; } -std::string_view Structs::GetName(uint32_t name_off) { +std::string_view +Structs::GetName(uint32_t name_off) +{ m_assert(name_off < header_->str_len, - "The name offset exceeds the section length"); - const char *section_end = str_section_ + header_->str_len; - const char *name_end = std::find(&str_section_[name_off], section_end, '\0'); + "The name offset exceeds the section length"); + const char* section_end = str_section_ + header_->str_len; + const char* name_end = std::find(&str_section_[name_off], section_end, '\0'); m_assert(name_end < section_end, - "The name continues past the string section limit"); - (void)name_end; + "The name continues past the string section limit"); + (void) name_end; std::string_view name{&str_section_[name_off]}; return name; } -void Structs::PrintStringSection() { +void +Structs::PrintStringSection() +{ std::cout << "String section:\n"; - const char *curr = str_section_; - const char *limit = str_section_ + header_->str_len; - while (curr < limit) { - const char *pos = std::find(curr, limit, '\0'); - m_assert(pos < limit, "Error reading the string section"); - std::cout << ' ' << curr; - curr = pos + 1; - } + const char* curr = str_section_; + const char* limit = str_section_ + header_->str_len; + while (curr < limit) + { + const char* pos = std::find(curr, limit, '\0'); + m_assert(pos < limit, "Error reading the string section"); + std::cout << ' ' << curr; + curr = pos + 1; + } std::cout << '\n'; } -void Structs::BuildElfSymbols() { +void +Structs::BuildElfSymbols() +{ const auto filter = [&]() { auto filter = tab_->make_filter(); filter.set_public_symbols(); return filter; }(); - for (const auto &symbol : - abigail::symtab_reader::filtered_symtab(*tab_, filter)) { - const auto &symbol_name = symbol->get_name(); - const auto &main_symbol_name = symbol->get_main_symbol()->get_name(); - auto it = btf_symbol_types_.find(main_symbol_name); - if (it == btf_symbol_types_.end()) { - // missing BTF information is tracked explicitly - std::cerr << "ELF symbol " << std::quoted(symbol_name); - if (symbol_name != main_symbol_name) - std::cerr << " (aliased to " << std::quoted(main_symbol_name) << ')'; - std::cerr << " BTF info missing\n"; - types_.push_back(nullptr); - } else { - uint32_t type_id = it->second; - types_.push_back(std::make_unique(types_, symbol, type_id)); + for (const auto& symbol : + abigail::symtab_reader::filtered_symtab(*tab_, filter)) + { + const auto& symbol_name = symbol->get_name(); + const auto& main_symbol_name = symbol->get_main_symbol()->get_name(); + auto it = btf_symbol_types_.find(main_symbol_name); + if (it == btf_symbol_types_.end()) + { + // missing BTF information is tracked explicitly + std::cerr << "ELF symbol " << std::quoted(symbol_name); + if (symbol_name != main_symbol_name) + std::cerr << " (aliased to " << std::quoted(main_symbol_name) + << ')'; + std::cerr << " BTF info missing\n"; + types_.push_back(nullptr); + } + else + { + uint32_t type_id = it->second; + types_.push_back( + std::make_unique(types_, symbol, type_id)); + } + elf_symbols_.emplace(symbol_name, types_.back().get()); } - elf_symbols_.emplace(symbol_name, types_.back().get()); - } } -class ElfHandle { - public: - ElfHandle(const std::string &path) : dwfl_(nullptr, dwfl_end) { +class ElfHandle +{ +public: + ElfHandle(const std::string& path) : dwfl_(nullptr, dwfl_end) + { string name; tools_utils::base_name(path, name); elf_version(EV_CURRENT); dwfl_ = std::unique_ptr( - dwfl_begin(&offline_callbacks_), dwfl_end); - auto dwfl_module = dwfl_report_offline(dwfl_.get(), name.c_str(), - path.c_str(), -1); + dwfl_begin(&offline_callbacks_), dwfl_end); + auto dwfl_module = + dwfl_report_offline(dwfl_.get(), name.c_str(), path.c_str(), -1); GElf_Addr bias; elf_handle_ = dwfl_module_getelf(dwfl_module, &bias); } // Conversion operator to act as a drop-in replacement for Elf* - operator Elf *() const { return elf_handle_; } + operator Elf*() const { return elf_handle_; } - Elf *get() const { return elf_handle_; } + Elf* + get() const + { + return elf_handle_; + } - private: +private: // Dwfl owns all our data, hence only keep track of this std::unique_ptr dwfl_; - Elf *elf_handle_; + Elf* elf_handle_; Dwfl_Callbacks offline_callbacks_; }; -Structs ReadFile(const std::string &path, bool verbose) { +Structs +ReadFile(const std::string& path, bool verbose) +{ using abigail::symtab_reader::symtab; ElfHandle elf(path); m_assert(elf.get() != nullptr, "Could not get elf handle from file."); - Elf_Scn *btf_section = + Elf_Scn* btf_section = abigail::elf_helpers::find_section(elf, ".BTF", SHT_PROGBITS); m_assert(btf_section != nullptr, - "The given file does not have a BTF section"); - Elf_Data *elf_data = elf_rawdata(btf_section, 0); + "The given file does not have a BTF section"); + Elf_Data* elf_data = elf_rawdata(btf_section, 0); m_assert(elf_data != nullptr, "The BTF section is invalid"); - const char *btf_start = static_cast(elf_data->d_buf); + const char* btf_start = static_cast(elf_data->d_buf); auto env = std::make_unique(); auto tab = symtab::load(elf, env.get()); @@ -1360,5 +1645,5 @@ Structs ReadFile(const std::string &path, bool verbose) { return Structs(btf_start, std::move(env), std::move(tab), verbose); } -} // end namespace btf -} // end namespace abigail +} // end namespace btf +} // end namespace abigail diff --git a/tests/test-scc.cc b/tests/test-scc.cc index ccabb471..c0c685c0 100644 --- a/tests/test-scc.cc +++ b/tests/test-scc.cc @@ -19,83 +19,109 @@ #include "abg-scc.h" -namespace Test { +namespace Test +{ using abigail::SCC; // Nodes are [0, N), the sets are the out-edges. typedef std::vector> Graph; -std::ostream &operator<<(std::ostream &os, const Graph &g) { - for (size_t i = 0; i < g.size(); ++i) { - os << i << ':'; - for (auto o : g[i]) - os << ' ' << o; - os << '\n'; - } +std::ostream& +operator<<(std::ostream& os, const Graph& g) +{ + for (size_t i = 0; i < g.size(); ++i) + { + os << i << ':'; + for (auto o : g[i]) + os << ' ' << o; + os << '\n'; + } return os; } -template Graph invent(size_t n, G& gen) { +template +Graph +invent(size_t n, G& gen) +{ Graph graph(n); std::uniform_int_distribution toss(0, 1); - for (auto &node : graph) { - for (size_t o = 0; o < n; ++o) { - if (toss(gen)) - node.insert(o); + for (auto& node : graph) + { + for (size_t o = 0; o < n; ++o) + { + if (toss(gen)) + node.insert(o); + } } - } return graph; } // Generate a graph g' where a -> b iff a and b are strongly connected in g. -Graph symmetric_subset_of_reflexive_transitive_closure(Graph g) { +Graph +symmetric_subset_of_reflexive_transitive_closure(Graph g) +{ const size_t n = g.size(); // transitive closure using Floyd-Warshall for (size_t o = 0; o < n; ++o) g[o].insert(o); - for (size_t k = 0; k < n; ++k) { - for (size_t i = 0; i < n; ++i) { - for (size_t j = 0; j < n; ++j) { - if (!g[i].count(j) && g[i].count(k) && g[k].count(j)) - g[i].insert(j); - } + for (size_t k = 0; k < n; ++k) + { + for (size_t i = 0; i < n; ++i) + { + for (size_t j = 0; j < n; ++j) + { + if (!g[i].count(j) && g[i].count(k) && g[k].count(j)) + g[i].insert(j); + } + } } - } // now a -> b iff a has path to b in g - for (size_t i = 0; i < n; ++i) { - for (size_t j = i + 1; j < n; ++j) { - // discard a -> b if not b -> a and vice versa - auto ij = g[i].count(j); - auto ji = g[j].count(i); - if (ij < ji) g[j].erase(i); - if (ji < ij) g[i].erase(j); + for (size_t i = 0; i < n; ++i) + { + for (size_t j = i + 1; j < n; ++j) + { + // discard a -> b if not b -> a and vice versa + auto ij = g[i].count(j); + auto ji = g[j].count(i); + if (ij < ji) + g[j].erase(i); + if (ji < ij) + g[i].erase(j); + } } - } // now have a -> b iff a has path to b and b has path to a in g return g; } // Generate a graph where a -> b iff a and b are in the same SCC. -Graph scc_strong_connectivity(const std::vector> &sccs) { +Graph +scc_strong_connectivity(const std::vector>& sccs) +{ size_t n = 0; - std::map *> edges; - for (const auto &scc : sccs) { - for (auto o : scc) { - if (o >= n) - n = o + 1; - edges[o] = &scc; + std::map*> edges; + for (const auto& scc : sccs) + { + for (auto o : scc) + { + if (o >= n) + n = o + 1; + edges[o] = &scc; + } } - } Graph g(n); for (size_t o = 0; o < n; ++o) g[o] = *edges[o]; return g; } -void dfs(std::set &visited, SCC &scc, - const Graph &g, size_t node, - std::vector> &sccs) { +void +dfs(std::set& visited, + SCC& scc, + const Graph& g, + size_t node, + std::vector>& sccs) +{ if (visited.count(node)) return; auto handle = scc.Open(node); @@ -104,17 +130,21 @@ void dfs(std::set &visited, SCC &scc, for (auto o : g[node]) dfs(visited, scc, g, o, sccs); auto nodes = scc.Close(handle.value()); - if (!nodes.empty()) { - std::set scc_set; - for (auto o : nodes) { - CHECK(visited.insert(o).second); - CHECK(scc_set.insert(o).second); + if (!nodes.empty()) + { + std::set scc_set; + for (auto o : nodes) + { + CHECK(visited.insert(o).second); + CHECK(scc_set.insert(o).second); + } + sccs.push_back(scc_set); } - sccs.push_back(scc_set); - } } -void process(const Graph &g) { +void +process(const Graph& g) +{ const size_t n = g.size(); // find SCCs @@ -126,21 +156,25 @@ void process(const Graph &g) { // check partition and topological order properties std::set seen; - for (const auto &nodes : sccs) { - CHECK(!nodes.empty()); - for (auto node : nodes) { - // value in range [0, n) - CHECK(node < n); - // value seen at most once - CHECK(seen.insert(node).second); - } - for (auto node : nodes) { - for (auto o : g[node]) { - // edges point to nodes in this or earlier SCCs - CHECK(seen.count(o)); - } + for (const auto& nodes : sccs) + { + CHECK(!nodes.empty()); + for (auto node : nodes) + { + // value in range [0, n) + CHECK(node < n); + // value seen at most once + CHECK(seen.insert(node).second); + } + for (auto node : nodes) + { + for (auto o : g[node]) + { + // edges point to nodes in this or earlier SCCs + CHECK(seen.count(o)); + } + } } - } // exactly n values seen CHECK(seen.size() == n); @@ -148,15 +182,18 @@ void process(const Graph &g) { auto g_scc_closure = scc_strong_connectivity(sccs); auto g_closure = symmetric_subset_of_reflexive_transitive_closure(g); // catch isn't printing nicely - if (g_scc_closure != g_closure) { - std::cerr << "original:\n" << g - << "SCC finder:\n" << g_scc_closure - << "SCCs independently:\n" << g_closure; - } + if (g_scc_closure != g_closure) + { + std::cerr << "original:\n" + << g << "SCC finder:\n" + << g_scc_closure << "SCCs independently:\n" + << g_closure; + } CHECK(g_scc_closure == g_closure); } -TEST_CASE("randomly-generated graphs") { +TEST_CASE("randomly-generated graphs") +{ std::mt19937 gen; auto seed = gen(); // NOTES: @@ -164,20 +201,20 @@ TEST_CASE("randomly-generated graphs") { // There are O(2^k^2) possible directed graphs of size k. // Testing costs are O(k^3) so we restrict accordingly. uint64_t budget = 10000; - for (size_t k = 0; k < 7; ++k) { - uint64_t count = std::min(static_cast(1) << (k*k), - budget / (k ? k * k * k : 1)); - INFO("testing with " << count << " graphs of size " << k); - for (uint64_t n = 0; n < count; ++n, ++seed) { - gen.seed(seed); - Graph g = invent(k, gen); - std::ostringstream os; - os << "a graph of " << k << " nodes generated using seed " << seed; - GIVEN(os.str()) { - process(g); - } + for (size_t k = 0; k < 7; ++k) + { + uint64_t count = std::min(static_cast(1) << (k * k), + budget / (k ? k * k * k : 1)); + INFO("testing with " << count << " graphs of size " << k); + for (uint64_t n = 0; n < count; ++n, ++seed) + { + gen.seed(seed); + Graph g = invent(k, gen); + std::ostringstream os; + os << "a graph of " << k << " nodes generated using seed " << seed; + GIVEN(os.str()) { process(g); } + } } - } } -} // namespace Test +} // namespace Test diff --git a/tools/btfdiff.cc b/tools/btfdiff.cc index 58c40e42..e7fc27c8 100644 --- a/tools/btfdiff.cc +++ b/tools/btfdiff.cc @@ -16,7 +16,9 @@ const int kAbiChange = 4; -int main(int argc, char* argv[]) { +int +main(int argc, char* argv[]) +{ bool use_elf_symbols = true; static option opts[]{ {"symbols", required_argument, nullptr, 's'}, @@ -32,24 +34,26 @@ int main(int argc, char* argv[]) { << "' unrecognized argument '" << optarg << "'\n"; return usage(); }; - while (true) { - int ix; - int c = getopt_long(argc, argv, "s:", opts, &ix); - if (c == -1) - break; - switch (c) { - case 's': - if (!strcmp(optarg, "btf")) - use_elf_symbols = false; - else if (!strcmp(optarg, "elf")) - use_elf_symbols = true; - else - return bad_arg(ix); - break; - default: - return usage(); + while (true) + { + int ix; + int c = getopt_long(argc, argv, "s:", opts, &ix); + if (c == -1) + break; + switch (c) + { + case 's': + if (!strcmp(optarg, "btf")) + use_elf_symbols = false; + else if (!strcmp(optarg, "elf")) + use_elf_symbols = true; + else + return bad_arg(ix); + break; + default: + return usage(); + } } - } if (optind + 2 != argc) return usage(); diff --git a/tools/btfinfo.cc b/tools/btfinfo.cc index dbda7945..8b40cc96 100644 --- a/tools/btfinfo.cc +++ b/tools/btfinfo.cc @@ -7,11 +7,14 @@ #include "abg-btf.h" -int main(int argc, const char *argv[]) { - if (argc != 2) { - std::cerr << "Please specify the path to a BTF file."; - return 1; - } +int +main(int argc, const char* argv[]) +{ + if (argc != 2) + { + std::cerr << "Please specify the path to a BTF file."; + return 1; + } (void) abigail::btf::ReadFile(argv[1], /* verbose = */ true);