From patchwork Tue Jun 22 10:33:13 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43950 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 69216388C00B for ; Tue, 22 Jun 2021 10:33:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 69216388C00B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624358014; bh=abe5TnZTcqwlS7on/3vBjGXbC5kDZTXaFiczc8Xydd8=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=dC5wbFoMpY/kmVO+Mtuq+QhLtcqrd+JRxLwMBbttE0qFLuw41ObCA3pDBi9OCLBTb KeYd/WBcOwNoni3uFH8JnK7mm4KPKre5aEGJHQoMtNEETuzVBDgXEvR+V2/V6lDmjn zrlVpxidEgqegU+JWFDM5N+cY/KUgXd5PdEl/ys8= 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 A50CB3848001 for ; Tue, 22 Jun 2021 10:33:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A50CB3848001 Received: by mail-wr1-x449.google.com with SMTP id k25-20020a5d52590000b0290114dee5b660so9559500wrc.16 for ; Tue, 22 Jun 2021 03:33: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=abe5TnZTcqwlS7on/3vBjGXbC5kDZTXaFiczc8Xydd8=; b=b0eOm2BVI+JX1QxK+TAqXKcdKz8tXHUroFkiPQNrj08ebcymdxfaP5WIgyMCQNEQcO wMmcR/edAxyilHgwoWeWt7elb61ifmuon8I5bTmTXdXtUsNkiDOnMTYeUrQAZh9UBS96 IZmfofFEOU6KB/nsB8pTCQs09a6dZ/hGF1581xXCqML6VZR9wzSQrmz7NPE5/AQBGawV ztVs0RqQk2iLbJmb3y4NSsEvrWi8YitsCGriHPjBrS2yQASmd5GMpP52GS2kONU0FhW2 PYfm1FbI03CSUOVZMNptGYQb49dIwpn5le1QYVj3OBsCvvzKIhH2MpKhlrOorj2KsIdl ua6A== X-Gm-Message-State: AOAM531VpD/gh0PJfjkzEVV0eLczPMqv5PFe8yt37SxeahdY6acLAP2F Of1YTHr2UeBrZNKONVvI+PFXXexIgeANSaqyD+njl5lURAIdNmptRir5aSE+vJds+9yrH4ikG14 WoDNFbnzv7aBhMr6aaHiuBzzIJFveGfAwkTMBwtovyNqGpmlBCmPdtklei3+0kO6vp2VZoBw= X-Google-Smtp-Source: ABdhPJwtaua0NyxRDUQQ01uhV8rdyFh6rclumCDwXk8/JithJAm5BpzeEOFN3CFNT3JA80x8r7EcmdoGcTWrhw== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:b7d7:a6fe:d167:7a5d]) (user=gprocida job=sendgmr) by 2002:a5d:548a:: with SMTP id h10mr3885157wrv.234.1624358006668; Tue, 22 Jun 2021 03:33:26 -0700 (PDT) Date: Tue, 22 Jun 2021 11:33:13 +0100 In-Reply-To: <20210622103318.478914-1-gprocida@google.com> Message-Id: <20210622103318.478914-2-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> <20210622103318.478914-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.288.g62a8d224e6-goog Subject: [PATCH v2 1/6] Allow C++17 code to be compiled 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, 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 Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" The BTF code and abitidy tool were both developed in a C++17 environment. 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 Tue Jun 22 10: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: 43951 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 19E4E388CC12 for ; Tue, 22 Jun 2021 10:33:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 19E4E388CC12 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624358017; bh=YOD9ZlDcGF5ddouFcIgSacFeCT6OeCZ4wp/gSHe/TTI=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=etY31EdgHq9PLIhGwpxs2QQIOzx6KOXPxvQ/g/WVRsck6g44iD+SZSB8HrmPI/0ol slE4Os4brwKPsC1VyKrukH/l5YWMD7/IbWdiQOzOwTGL8m7zFcc/Tb9jMtSrAkk3o7 iqp7LG5PQj3UNfhmi0+Q+xwpGUxYT/CC74t1Q0P8= 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 686303847802 for ; Tue, 22 Jun 2021 10:33:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 686303847802 Received: by mail-qv1-xf49.google.com with SMTP id ez18-20020ad459120000b029020e62abfcbdso8633405qvb.16 for ; Tue, 22 Jun 2021 03:33:29 -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=YOD9ZlDcGF5ddouFcIgSacFeCT6OeCZ4wp/gSHe/TTI=; b=H1PcUl+sUNNeFygFlpNJcC/PdmMeYyOlUsb6DYWIYvRzAKwR3i0aK5Sb2juVaDMykU 7tb+u/CjW3LVbJTjT/RGH2vOnelMIqetuhRWs3S/eZD5v3x09r7H485J/JM73dxeUs3p 1v0ASGqCwERXADoa7XpsCy8MYzztTnlXXo5NWzHKF9NuZlOXW4wicQRSS2rZxpyAg4Vs mVKNb6+nLVyDU8MYyr/8jG01L+pS16yPCzs+u7Z5qzYBEi1kRKIn3l61zWZVnEFpVX7A Jt62/2Vnn6i6NyEvvda3MASX8HGKlvkq8zbCWabYrFjCOcUWNUpNvZqsSAwUB81bsBAf WqDg== X-Gm-Message-State: AOAM530i5+sfwjH19ph3/CeE2GNrFaZMQwNFtthU18oSvey9yuDDPN4G UpXRXOZyFHQoBtMSJfpeFYyVfJCIkKDy15B7kCUr1D/mXK3qQy460LLxb+F4nJb5Sn/EX9G5NzK iWFiwCehw3TdS7Pg5t87Ct2ehFQFV+dWzzUbc325p7mfV/woZlW1EXozBvGFuxM8lebfPdhk= X-Google-Smtp-Source: ABdhPJy/RXLJGCpx+atlVCwaFp+IgDUahwVLzt6TNXowepX4QgwBZTxzYV7Cs1bJ/PQs9qTdBH0R5QJ6Ku5rMA== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:b7d7:a6fe:d167:7a5d]) (user=gprocida job=sendgmr) by 2002:ad4:5444:: with SMTP id h4mr24543397qvt.14.1624358008951; Tue, 22 Jun 2021 03:33:28 -0700 (PDT) Date: Tue, 22 Jun 2021 11:33:14 +0100 In-Reply-To: <20210622103318.478914-1-gprocida@google.com> Message-Id: <20210622103318.478914-3-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> <20210622103318.478914-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.288.g62a8d224e6-goog Subject: [PATCH v2 2/6] Tweak clang-format To: libabigail@sourceware.org X-Spam-Status: No, score=-22.2 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 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 Tue Jun 22 10: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: 43952 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 A4861394D828 for ; Tue, 22 Jun 2021 10:33:39 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A4861394D828 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624358019; bh=OyMpIQX54A93zGujrKZe5JsnTuUOPvbrnGPvVhA5ohs=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=camjHygpDZRUKG0BVZgk7KRfhtuzDKecCIOfkj1CI0AD1WD6ami3BYA7GPoJofAYw lyjKNwY8QiuuIwVe228u0YDFxbiRuSv1ARnzDOe1eKMi5P2pR6aRqSh6Qnpl0x17ZS uLYax98KC09ia1qvOC60q+nAu4RtX767GCPpkEM8= 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 368AE388C00B for ; Tue, 22 Jun 2021 10:33:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 368AE388C00B Received: by mail-wr1-x449.google.com with SMTP id h104-20020adf90710000b029010de8455a3aso9542924wrh.12 for ; Tue, 22 Jun 2021 03:33:32 -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=OyMpIQX54A93zGujrKZe5JsnTuUOPvbrnGPvVhA5ohs=; b=C1Txw7mOMzR9CANhTFX0qYrZliOfyeN+aoZur1nXRjCBuDHzf7ARXv1XmqWcIsuv92 FghkNWqf6KRmnakyS2lUKyMzbUWAHS+cwTHmvXhDfQxGPY+Wa0KLC0QI63+lBSJUIsal oE3A+SvOv0WtuKX73at0kehzAzUkNBS3KpDmsdYaKeWr0J41P78vTNcp3Ayt1o7WDKnX X6+AaVVPVxkwwi0bPZ6R0A1vVHBBhmV4lOVsbc+d8q60kCt+0efhs+yaVy5K9U+F2Z7Z vnaa4zPeSDVAyCfIjp5EGyldwOJYex5rltUIU0RhBVP/ZICd/sN+iEpci1n8QVzu+ATD 7HIA== X-Gm-Message-State: AOAM531zLsjSrM+IC690sxctLNgB5AwN6X2j8oB7N5xi0GIun7gKXX6U Xz/+WDhgoF5/NvZNtSWMBFT4XjPxfoL4BaeAmGo7sawMa+On2WMEwqEXBDc3YaOpe9s3nj0y83+ h1PB7RA1Gqj3nUr4MhVOotZi0JvJsuRK9n5xcyIf2lvmZVeqVm4ex+wak5XSCbLQVNSjsUOs= X-Google-Smtp-Source: ABdhPJwhOMxSEb2AQU1aWXCPke+XYP/DdBgQ4c1jt3DvnzPmAs4w/Det1Ft7Nvgd0HJXzi3nG+UnEaAfoCdHBw== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:b7d7:a6fe:d167:7a5d]) (user=gprocida job=sendgmr) by 2002:a05:6000:128b:: with SMTP id f11mr3876573wrx.171.1624358011277; Tue, 22 Jun 2021 03:33:31 -0700 (PDT) Date: Tue, 22 Jun 2021 11:33:15 +0100 In-Reply-To: <20210622103318.478914-1-gprocida@google.com> Message-Id: <20210622103318.478914-4-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> <20210622103318.478914-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.288.g62a8d224e6-goog Subject: [PATCH v2 3/6] BTF: add SCC finder and test 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, 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 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..8c542e67 --- /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 have a suitable hash function. + * + * 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 always follow edges to child nodes, even if it knows the + * node has already been visited. The SCC finder needs to know about all edges. + * + * The user code must ensure that nodes are not re-examined once they have been + * assigned to an SCC. The finder does not maintain any state for such nodes. + * + * GUARANTEES + * + * The SCC finder will ensure each node is 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 assigned to an SCC 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. + * Infomation about the node can be stored provisionally, but must NOT be used + * to make decisions about whether to revisit it - that is Open's job. + * + * Once the examination is done, call Close, passing in the handle. 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: + ~SCC() { + assert(open_.empty()); + assert(is_open_.empty()); + assert(root_index_.empty()); + } + + std::optional Open(const Node &node) { + // Insertion will fail if the node is already open. + auto [it, inserted] = is_open_.insert({node, is_open_.size()}); + auto ix = it->second; + if (!inserted) { + // Pop indices to nodes which cannot be the root of their SCC. + while (root_index_.back() > ix) + root_index_.pop_back(); + return {}; + } + // Unvisited, record open node and record root index. + open_.push_back(node); + root_index_.push_back(ix); + return ix; + } + + std::vector Close(size_t ix) { + std::vector scc; + assert(ix < open_.size()); + if (ix == root_index_.back()) { + // Close SCC. + for (size_t o = ix; o < open_.size(); ++o) + is_open_.erase(open_[o]); + std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); + open_.resize(ix); + root_index_.pop_back(); + } + return scc; + } + + private: + std::vector open_; // index to node + std::unordered_map is_open_; // node to index + 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..a75b1ae0 --- /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::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 Tue Jun 22 10: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: 43954 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 F14DA3889800 for ; Tue, 22 Jun 2021 10:33:45 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F14DA3889800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624358026; bh=UmHfiEPyDx2bUSwGvrkR9wrVOhqBUm7h1rwL4yb5FjQ=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=qdZ/AiTyJlva1m7e3JJ/LqHovXomEKLUNJ0M2A/sAJy/aX29pceOqikDphR/FZmLE AmL/6r+UDu86BEWjmBsT4JtOLWJCo8tJ37Jg541psSwaS1tffHbTCWYOoh2a32w71l wFGlPaTlYUhXX9v9r3QtduBKaELQHbGP+CAiJCe8= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-qv1-xf4a.google.com (mail-qv1-xf4a.google.com [IPv6:2607:f8b0:4864:20::f4a]) by sourceware.org (Postfix) with ESMTPS id 4DC043890036 for ; Tue, 22 Jun 2021 10:33:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4DC043890036 Received: by mail-qv1-xf4a.google.com with SMTP id cu3-20020a05621417c3b0290272a51302bdso6782906qvb.20 for ; Tue, 22 Jun 2021 03:33:34 -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=UmHfiEPyDx2bUSwGvrkR9wrVOhqBUm7h1rwL4yb5FjQ=; b=Anij84pEnuJ8mdLgZYKmcg4lhO4zHIWKvkR96vPi/eoNH1NnWx81BiFwZ4/N0rOI32 rfyYiT8mNnn/C4BaeCGXx8zOs/nTaiL0L4tha/gSqq0iFfP6fvGjCib9PkYvkZN9EYzu u3Opc5RrwSAk3ycZYpMkSeGDhLQ88P906BKXgqJB8RxdVaXDDld8/yCNdPHqg4/fvQdX MT9C2HWDSxYD1DDaV45OfCScwsHFJJU9ht67NXDtwrdXjsA0Ko2X/KGNqFYuir9hxyXa gOrrutOzIRf31eodhZ3+9vAV5pCgHPSiqVtcjZzBvwFXbvlqH3dBct7kGEBAmeWWE/EP jEtg== X-Gm-Message-State: AOAM530MgrBIPGFxD7WN7HKo/liAwZWEoVB5Wz/JWiRNjmoOPQhJorn+ IT2v8xVS1aNKHcbyxnkWppZXppGPMP0PTarA1zSREzBNNvasGSKUE5YvIA9/UeYg/JmlU1g8Nh+ 1eklqLLjMnWtkdGEGmSFvduPNkJYU6nUme667Tw7BQEQzHAiaDsKFoTbfyOe7fcM+Z6gTDT0= X-Google-Smtp-Source: ABdhPJy/sw26r4Or21mzoUaU043RpNvHw3sBHNe/1bUpTzv0nQG6gB+fKpbwQvoEQqJIIvO/HgQHD/nH3citUw== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:b7d7:a6fe:d167:7a5d]) (user=gprocida job=sendgmr) by 2002:ad4:4c43:: with SMTP id cs3mr21389467qvb.27.1624358013761; Tue, 22 Jun 2021 03:33:33 -0700 (PDT) Date: Tue, 22 Jun 2021 11:33:16 +0100 In-Reply-To: <20210622103318.478914-1-gprocida@google.com> Message-Id: <20210622103318.478914-5-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> <20210622103318.478914-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.288.g62a8d224e6-goog Subject: [PATCH v2 4/6] BTF: add core functionality 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, Maria Teguiani 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 | 582 +++++++++++++++++++ src/Makefile.am | 9 +- src/abg-btf.cc | 1369 +++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 1971 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..f7243fa3 --- /dev/null +++ b/include/abg-btf.h @@ -0,0 +1,582 @@ +// 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(const std::string &name) + : left_(name), precedence_(Precedence::NIL), right_() {} + Name(const std::string &left, Precedence precedence, const std::string &right) + : left_(left), precedence_(precedence), right_(right) {} + Name Add(Side side, Precedence precedence, const std::string &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_; +}; + +struct HashComparison { + size_t operator()(const Comparison &comparison) const { + size_t seed = 0; + std::hash h; + combine_hash(seed, h(comparison.first)); + combine_hash(seed, h(comparison.second)); + return seed; + } + static void combine_hash(size_t &seed, size_t hash) { + seed ^= hash + 0x9e3779b97f4a7c15 + (seed << 12) + (seed >> 4); + } +}; + +using Outcomes = std::unordered_map; +// unvisited (absent) -> started (false) -> finished (true) +using Seen = std::unordered_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, + Kind kind) + : types_(types), index_(index), kind_(kind) {} + virtual ~Type() = default; + uint32_t GetIndex() const { return index_; } + 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) { } + Outcomes &outcomes; + std::unordered_set known_equal; + Outcomes provisional; + 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 Kind kind_; +}; + +class Void : public Type { + public: + Void(const std::vector> &types, uint32_t index, + Kind kind) + : Type(types, index, 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, + Kind kind, uint32_t pointeeTypeId) + : Type(types, index, 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, + const std::string &name, Kind kind, uint32_t referredTypeId) + : Type(types, index, kind), + name_(name), + referredTypeId_(referredTypeId) {} + const std::string &GetName() const { return name_; } + 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 std::string name_; + const uint32_t referredTypeId_; +}; + +class Qualifier : public Type { + public: + Qualifier(const std::vector> &types, + uint32_t index, Kind kind, uint32_t qualifiedTypeId) + : Type(types, index, 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, + const std::string &name, Kind kind, uint32_t encoding, + uint32_t offset, uint32_t bitsize, uint32_t bytesize) + : Type(types, index, kind), + name_(name), + offset_(offset), + bitsize_(bitsize), + bytesize_(bytesize), + isBool_(encoding & BTF_INT_BOOL), + isSigned_(encoding & BTF_INT_SIGNED), + isChar_(encoding & BTF_INT_CHAR) {} + const std::string &GetName() const { return name_; } + 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 std::string name_; + 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, + Kind kind, uint32_t elementTypeId, uint32_t indexTypeId, + uint32_t numOfElements) + : Type(types, index, 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, const std::string &name, Kind kind, + uint32_t bytesize, std::map members) + : Type(types, index, kind), + name_(name), + bytesize_(bytesize), + members_(members) {} + const std::string &GetName() const { return name_; } + 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 std::string name_; + const uint32_t bytesize_; + const std::map members_; +}; + +class Enumeration : public Type { + public: + Enumeration(const std::vector> &types, + uint32_t index, const std::string &name, Kind kind, + uint32_t bytesize, std::map enumerators) + : Type(types, index, kind), + name_(name), + bytesize_(bytesize), + enumerators_(enumerators) {} + const std::string &GetName() const { return name_; } + 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 std::string name_; + 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, const std::string &name, Kind kind, + bool isUnion) + : Type(types, index, kind), + name_(name), + fwdKind_(isUnion ? ForwardDeclarationKind::UNION + : ForwardDeclarationKind::STRUCT) {} + const std::string &GetName() const { return name_; } + ForwardDeclarationKind GetFwdKind() const { return fwdKind_; } + Name MakeDescription(NameCache &names) const final; + Result Equals(const Type &other, State &state) const final; + + private: + const std::string name_; + const ForwardDeclarationKind fwdKind_; +}; + +class Function : public Type { + public: + enum class Linkage : uint16_t { STATIC, GLOBAL, EXTERN }; + Function(const std::vector> &types, + uint32_t index, const std::string &name, Kind kind, + uint32_t referredTypeId, Linkage linkage) + : Type(types, index, kind), + name_(name), + referredTypeId_(referredTypeId), + linkage_(linkage) {} + const std::string &GetName() const { return name_; } + 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 std::string name_; + const uint32_t referredTypeId_; + const Linkage linkage_; +}; + +class FunctionPrototype : public Type { + public: + FunctionPrototype(const std::vector> &types, + uint32_t index, Kind kind, uint32_t returnTypeId, + std::vector parameters) + : Type(types, index, 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, const std::string &name, Kind kind, + unsigned varTypeId, Linkage linkage) + : Type(types, index, kind), + name_(name), + varTypeId_(varTypeId), + linkage_(linkage) {} + const std::string &GetName() const { return name_; } + 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 std::string name_; + const uint32_t varTypeId_; + const Linkage linkage_; +}; + +class DataSection : public Type { + public: + DataSection(const std::vector> &types, + uint32_t index, Kind kind, uint32_t bytesize, + std::vector secinfos) + : Type(types, index, 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 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 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..39a8e480 --- /dev/null +++ b/src/abg-btf.cc @@ -0,0 +1,1369 @@ +// 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 + +#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, + const std::string &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) { + const 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. + state.provisional.insert({comparison, result.details_}); + auto comparisons = state.scc.Close(handle.value()); + 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); + return {true, {}}; + } else { + // Different. Record diffs. + for (auto &c : comparisons) { + auto it = state.provisional.find(c); + state.outcomes.insert(*it); + state.provisional.erase(it); + } + } + } + + // 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{"qualifier"}; +} + +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); +} + +static constexpr std::string_view ANON{"(anon)"}; + +std::ostream &operator<<(std::ostream &os, const Ptr &bp) { + os << kRawKindNames[bp.GetKind()] + << " '" << ANON << "'" + << " type_id=" << bp.GetPointeeTypeId() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Typedef &bp) { + os << kRawKindNames[bp.GetKind()] + << " '" << bp.GetName() << "'" + << " type_id=" << bp.GetReferredTypeId() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Qualifier &bp) { + os << kRawKindNames[bp.GetKind()] + << " '" << ANON << "'" + << " type_id=" << bp.GetQualifiedTypeId() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Integer &bi) { + os << kRawKindNames[bi.GetKind()] + << " '" << bi.GetName() << "'" + << " 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 << kRawKindNames[ba.GetKind()] + << " '" << ANON << "'" + << " 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) { + const auto &name = bsu.GetName(); + os << kRawKindNames[bsu.GetKind()] + << " '" << (name.empty() ? ANON : name) << "'" + << " 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) { + const auto &name = be.GetName(); + os << kRawKindNames[be.GetKind()] + << " '" << (name.empty() ? ANON : name) << "'" + << " 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 << kRawKindNames[bfd.GetKind()] + << " '" << bfd.GetName() << "'" + << " fwd_kind=" << bfd.GetFwdKind() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const Function &bf) { + os << kRawKindNames[bf.GetKind()] + << " '" << bf.GetName() << "'" + << " type_id=" << bf.GetReferredTypeId() + << " linkage=" << bf.GetLinkage() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const FunctionPrototype &bfp) { + os << kRawKindNames[bfp.GetKind()] + << " '" << ANON << "'" + << " 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 << kRawKindNames[bv.GetKind()] + << " type_id=" << bv.GetVarTypeId() + << ", linkage=" << bv.GetLinkage() + << '\n'; + return os; +} + +std::ostream &operator<<(std::ostream &os, const DataSection &bds) { + os << kRawKindNames[bds.GetKind()] + << " 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 << kRawKindNames[bes.GetKind()]; + // 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, 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, 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, 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, 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, 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, kind, t->size, secinfos)); + if (verbose_) { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_var_secinfo); + } + } + return type_size; +} + +std::string 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_begin = str_section_ + name_off; + const char *name_end = std::find(name_begin, section_end, '\0'); + m_assert(name_end < section_end, + "The name continues past the string section limit"); + return {name_begin, static_cast(name_end - name_begin)}; +} + +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 Tue Jun 22 10: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: 43953 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 8D2DE388A42D for ; Tue, 22 Jun 2021 10:33:42 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8D2DE388A42D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624358022; bh=kPkuAykLKvk++TUWpcyEKK8XLB5YMC7Ez4REcJVYw7Y=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=N6mEMRiobSlzrWuS7pRLGzgOJe1aQ7cFz35Su3bR4GgdSVZMyCaVYwnP9aP2kC3Bf lIcpKv6r6Tl5nba/D7BwkdMbm+HTdERIVz5CiJj1qL8py1LFnv7dA8d+s1b6ZZPRUy GjCjQnnTrqk15+TPm/aPAD9Z2L0MT1CuGKKIQjDk= 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 5BF3B3889800 for ; Tue, 22 Jun 2021 10:33:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5BF3B3889800 Received: by mail-qt1-x84a.google.com with SMTP id c29-20020ac86e9d0000b0290247b267c8e4so15459579qtv.22 for ; Tue, 22 Jun 2021 03:33:36 -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=kPkuAykLKvk++TUWpcyEKK8XLB5YMC7Ez4REcJVYw7Y=; b=TM7vFcNw4RIrPqiw5B2VZwyKtxzJkGmWnc8dYzM5JJc/WyiRSG9uElx5NjG6ey7GAp 25QYp6NaS+52LoEnXUaoEJohlrXLMs4TNexUXQZVoDP4yUFByAm/cjnVHKe4T56bVHNE 1Zv3oC3x8uK8Yb09gS75oVzkBz3lnpzr8JHllkxBp5NcMxOGHQTq93vFzdYcrIOuCF1i wAcoN9GZeXEBtOmYzWt9GikwW5N79hwcx+9TXeKRhwlGS2JnibxIdiqysMoxVmfqscNh hwBifmqvCOK8h4vlKcnfLIAjtFkoJt6f6euynIVkaN3e/SHMZfNgGvM9IRTUTj5jYAWU KW2Q== X-Gm-Message-State: AOAM530LNt/Yc64nn5Q8YFCIBVhaOrscwfCT72Pu2jX5aLjdJUTD4KIR JPdCDplG9MGtrntTi1SeFRvn66BSTI+FncPeAG+KKWMcEDxptXH+cQfXUaZ1JfejH0J2b8t0UsG OR/kYhnGEe+OANUwYMJAPpQajd8lZzTQb4PJadNr7wLaaOG+KkwLv3zIMcCFei1z5Ym4l34k= X-Google-Smtp-Source: ABdhPJwaGj1aQSObRPCdMJuIIAmQ/VxRSP8+Dzo/bGdf3u4QuJf4dws5UIcdv4mwTPVLm1tDGqMtcxycqjEERQ== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:b7d7:a6fe:d167:7a5d]) (user=gprocida job=sendgmr) by 2002:a0c:f0c5:: with SMTP id d5mr15931057qvl.2.1624358015913; Tue, 22 Jun 2021 03:33:35 -0700 (PDT) Date: Tue, 22 Jun 2021 11:33:17 +0100 In-Reply-To: <20210622103318.478914-1-gprocida@google.com> Message-Id: <20210622103318.478914-6-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> <20210622103318.478914-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.288.g62a8d224e6-goog Subject: [PATCH v2 5/6] BTF: add btfinfo and btfdiff tools To: libabigail@sourceware.org X-Spam-Status: No, score=-22.2 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, Maria Teguiani 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 | 68 +++++++++++++++++++++++++++++++++++++++++++++++ tools/btfinfo.cc | 19 +++++++++++++ 3 files changed, 101 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..0649821d --- /dev/null +++ b/tools/btfdiff.cc @@ -0,0 +1,68 @@ +// 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 Tue Jun 22 10: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: 43955 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 CDBFE383F404 for ; Tue, 22 Jun 2021 10:33:54 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org CDBFE383F404 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624358034; bh=6Gt5iSGZaBoMuEVWWPUSDCnGDntyGiX2D9zL/MHB9Es=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=D/dlmWAm+jHTvp+cJmCLPA6TQAgD5q+ZMULlX2S7P0NYClfk+gs8inytJnVqoXYzR vcsA0gyf+hc8OgP/4fzjHN6axnKVqITziJcnqCbrXN1+xNLzjcBoRFeqwWU/YqQ3zM AQUBq7+BRq0KQzQyPUc2iZPj7HZsFdGB4Cn7Lf2I= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-qk1-x74a.google.com (mail-qk1-x74a.google.com [IPv6:2607:f8b0:4864:20::74a]) by sourceware.org (Postfix) with ESMTPS id E367E388883E for ; Tue, 22 Jun 2021 10:33:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E367E388883E Received: by mail-qk1-x74a.google.com with SMTP id t131-20020a37aa890000b02903a9f6c1e8bfso17390270qke.10 for ; Tue, 22 Jun 2021 03:33:38 -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=6Gt5iSGZaBoMuEVWWPUSDCnGDntyGiX2D9zL/MHB9Es=; b=My6A8nzupnrlb0CqlXpjH3HKzXJWtAdjMD6YSIhux6/u7h9kQ0UR2GO+ilPxmnA+pa p2pHtEj+eT/SRGYZpWjLv7dm+qZbau+aNXlh/83t2OP/SLwhWXq/V05nuwYojl5IiplF ETp5nnankbEkejpwQCuOwEYAYd3KoyqohKNB81Mf8Geoc0yt3OxZ4BlFZOPCwQ2K/sqa IXx+Lni67ZAb5mmclqtEix8tWdbX4gxAiRMb5tmU5dOoVdua5JoNkxka4bPe3X61NT6r T/NiXZ6d7NQ9HJEizVyBwBFhBbP7OOMkcL0p/JyL4m1N3Hmcg0ZkCJSbOqX+0jNOoqTi QTyg== X-Gm-Message-State: AOAM533kS3X/1oHV0k/vdAVO1OJERkHn/TWFGTlVae3TMYQFqSHY4fur hqlmLg10YrJYhxZJ4/4Kee+6YJoDVw7WWfQJO4Oz4ibvrBIjb+sSdozzFKx/I6DtPmB9SE1IGE1 WN+mSJrgmHk+BBXwVrKjFJEeY2zvnmxEXGjddpydiMepFeEeMs1L1JvwPQehnKEdChrnwJ7k= X-Google-Smtp-Source: ABdhPJyUFoAsbUlxjeLvIAYigRGer2V7qq801hXcTrIe9t95oqbvNIG3r4mx0JXTxCH04u0+1ZoTc43HnD2Jjw== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:b7d7:a6fe:d167:7a5d]) (user=gprocida job=sendgmr) by 2002:a05:6214:966:: with SMTP id do6mr24514551qvb.57.1624358018418; Tue, 22 Jun 2021 03:33:38 -0700 (PDT) Date: Tue, 22 Jun 2021 11:33:18 +0100 In-Reply-To: <20210622103318.478914-1-gprocida@google.com> Message-Id: <20210622103318.478914-7-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> <20210622103318.478914-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.288.g62a8d224e6-goog Subject: [PATCH v2 6/6] BTF: clang-format all the new source files To: libabigail@sourceware.org X-Spam-Status: No, score=-22.5 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 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 | 1082 ++++++++++++++++--------- include/abg-scc.h | 68 +- src/abg-btf.cc | 1905 ++++++++++++++++++++++++++------------------- tests/test-scc.cc | 203 +++-- tools/btfdiff.cc | 55 +- tools/btfinfo.cc | 13 +- 6 files changed, 2012 insertions(+), 1314 deletions(-) diff --git a/include/abg-btf.h b/include/abg-btf.h index f7243fa3..7cb74246 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,125 +46,178 @@ 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; - -enum class Precedence { NIL, POINTER, ARRAY_FUNCTION, ATOMIC }; -enum class Side { LEFT, RIGHT }; +using Comparison = std::pair; -class Name { - public: - explicit Name(const std::string &name) - : left_(name), precedence_(Precedence::NIL), right_() {} - Name(const std::string &left, Precedence precedence, const std::string &right) - : left_(left), precedence_(precedence), right_(right) {} - Name Add(Side side, Precedence precedence, const std::string &text) const; - Name Qualify(const std::set &qualifiers) const; - std::ostream &Print(std::ostream &os) const; +enum class Precedence +{ + NIL, + POINTER, + ARRAY_FUNCTION, + ATOMIC +}; +enum class Side +{ + LEFT, + RIGHT +}; - private: +class Name +{ +public: + explicit Name(const std::string& name) + : left_(name), precedence_(Precedence::NIL), right_() + { + } + Name(const std::string& left, + Precedence precedence, + const std::string& right) + : left_(left), precedence_(precedence), right_(right) + { + } + Name + Add(Side side, Precedence precedence, const std::string& 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; Diff details_; }; -struct HashComparison { - size_t operator()(const Comparison &comparison) const { +struct HashComparison +{ + size_t + operator()(const Comparison& comparison) const + { size_t seed = 0; - std::hash h; + std::hash h; combine_hash(seed, h(comparison.first)); combine_hash(seed, h(comparison.second)); return seed; } - static void combine_hash(size_t &seed, size_t hash) { + static void + combine_hash(size_t& seed, size_t hash) + { seed ^= hash + 0x9e3779b97f4a7c15 + (seed << 12) + (seed >> 4); } }; @@ -170,21 +226,45 @@ using Outcomes = std::unordered_map; // unvisited (absent) -> started (false) -> finished (true) using Seen = std::unordered_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, +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, Kind kind) - : types_(types), index_(index), kind_(kind) {} + : types_(types), index_(index), kind_(kind) + { + } virtual ~Type() = default; - uint32_t GetIndex() const { return index_; } - Kind GetKind() const { return kind_; } - const std::vector> &GetTypes() const { + uint32_t + GetIndex() const + { + return index_; + } + Kind + GetKind() const + { + return kind_; + } + const std::vector>& + GetTypes() const + { return types_; } @@ -193,10 +273,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; } @@ -204,126 +286,215 @@ 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) { } - 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) {} + Outcomes& outcomes; std::unordered_set known_equal; Outcomes provisional; 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 Kind kind_; }; -class Void : public Type { - public: - Void(const std::vector> &types, uint32_t index, +class Void : public Type +{ +public: + Void(const std::vector>& types, + uint32_t index, Kind kind) - : Type(types, index, kind) {} - Name MakeDescription(NameCache &names) const final; - Result Equals(const Type &other, State &state) const final; + : Type(types, index, 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, - Kind kind, uint32_t pointeeTypeId) - : Type(types, index, 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, + Kind kind, + uint32_t pointeeTypeId) + : Type(types, index, 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, - const std::string &name, Kind kind, uint32_t referredTypeId) - : Type(types, index, kind), - name_(name), - referredTypeId_(referredTypeId) {} - const std::string &GetName() const { return name_; } - 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, + const std::string& name, + Kind kind, + uint32_t referredTypeId) + : Type(types, index, kind), name_(name), referredTypeId_(referredTypeId) + { + } + const std::string& + GetName() const + { + return name_; + } + 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 std::string name_; const uint32_t referredTypeId_; }; -class Qualifier : public Type { - public: - Qualifier(const std::vector> &types, - uint32_t index, Kind kind, uint32_t qualifiedTypeId) - : Type(types, index, 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, + Kind kind, + uint32_t qualifiedTypeId) + : Type(types, index, 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, - const std::string &name, Kind kind, uint32_t encoding, - uint32_t offset, uint32_t bitsize, uint32_t bytesize) - : Type(types, index, kind), - name_(name), - offset_(offset), - bitsize_(bitsize), - bytesize_(bytesize), - isBool_(encoding & BTF_INT_BOOL), - isSigned_(encoding & BTF_INT_SIGNED), - isChar_(encoding & BTF_INT_CHAR) {} - const std::string &GetName() const { return name_; } - 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, + const std::string& name, + Kind kind, + uint32_t encoding, + uint32_t offset, + uint32_t bitsize, + uint32_t bytesize) + : Type(types, index, kind), + name_(name), + offset_(offset), + bitsize_(bitsize), + bytesize_(bytesize), + isBool_(encoding & BTF_INT_BOOL), + isSigned_(encoding & BTF_INT_SIGNED), + isChar_(encoding & BTF_INT_CHAR) + { + } + const std::string& + GetName() const + { + return name_; + } + 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 std::string name_; const uint32_t offset_; const uint32_t bitsize_; @@ -333,250 +504,443 @@ class Integer : public Type { const bool isChar_; }; -class Array : public Type { - public: - Array(const std::vector> &types, uint32_t index, - Kind kind, uint32_t elementTypeId, uint32_t indexTypeId, - uint32_t numOfElements) - : Type(types, index, 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, + Kind kind, + uint32_t elementTypeId, + uint32_t indexTypeId, + uint32_t numOfElements) + : Type(types, index, 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, const std::string &name, Kind kind, - uint32_t bytesize, std::map members) - : Type(types, index, kind), - name_(name), - bytesize_(bytesize), - members_(members) {} - const std::string &GetName() const { return name_; } - 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, + const std::string& name, + Kind kind, + uint32_t bytesize, + std::map members) + : Type(types, index, kind), + name_(name), + bytesize_(bytesize), + members_(members) + { + } + const std::string& + GetName() const + { + return name_; + } + 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 std::string name_; const uint32_t bytesize_; const std::map members_; }; -class Enumeration : public Type { - public: - Enumeration(const std::vector> &types, - uint32_t index, const std::string &name, Kind kind, - uint32_t bytesize, std::map enumerators) - : Type(types, index, kind), - name_(name), - bytesize_(bytesize), - enumerators_(enumerators) {} - const std::string &GetName() const { return name_; } - 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, + const std::string& name, + Kind kind, + uint32_t bytesize, + std::map enumerators) + : Type(types, index, kind), + name_(name), + bytesize_(bytesize), + enumerators_(enumerators) + { + } + const std::string& + GetName() const + { + return name_; + } + 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 std::string name_; 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, const std::string &name, Kind kind, - bool isUnion) - : Type(types, index, kind), - name_(name), - fwdKind_(isUnion ? ForwardDeclarationKind::UNION - : ForwardDeclarationKind::STRUCT) {} - const std::string &GetName() const { return name_; } - 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, + const std::string& name, + Kind kind, + bool isUnion) + : Type(types, index, kind), + name_(name), + fwdKind_(isUnion ? ForwardDeclarationKind::UNION + : ForwardDeclarationKind::STRUCT) + { + } + const std::string& + GetName() const + { + return name_; + } + ForwardDeclarationKind + GetFwdKind() const + { + return fwdKind_; + } + Name + MakeDescription(NameCache& names) const final; + Result + Equals(const Type& other, State& state) const final; + +private: const std::string name_; const ForwardDeclarationKind fwdKind_; }; -class Function : public Type { - public: - enum class Linkage : uint16_t { STATIC, GLOBAL, EXTERN }; - Function(const std::vector> &types, - uint32_t index, const std::string &name, Kind kind, - uint32_t referredTypeId, Linkage linkage) - : Type(types, index, kind), - name_(name), - referredTypeId_(referredTypeId), - linkage_(linkage) {} - const std::string &GetName() const { return name_; } - 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, + const std::string& name, + Kind kind, + uint32_t referredTypeId, + Linkage linkage) + : Type(types, index, kind), + name_(name), + referredTypeId_(referredTypeId), + linkage_(linkage) + { + } + const std::string& + GetName() const + { + return name_; + } + 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 std::string name_; const uint32_t referredTypeId_; const Linkage linkage_; }; -class FunctionPrototype : public Type { - public: - FunctionPrototype(const std::vector> &types, - uint32_t index, Kind kind, uint32_t returnTypeId, - std::vector parameters) - : Type(types, index, 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, + Kind kind, + uint32_t returnTypeId, + std::vector parameters) + : Type(types, index, 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, const std::string &name, Kind kind, - unsigned varTypeId, Linkage linkage) - : Type(types, index, kind), - name_(name), - varTypeId_(varTypeId), - linkage_(linkage) {} - const std::string &GetName() const { return name_; } - 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, + const std::string& name, + Kind kind, + unsigned varTypeId, + Linkage linkage) + : Type(types, index, kind), + name_(name), + varTypeId_(varTypeId), + linkage_(linkage) + { + } + const std::string& + GetName() const + { + return name_; + } + 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 std::string name_; const uint32_t varTypeId_; const Linkage linkage_; }; -class DataSection : public Type { - public: - DataSection(const std::vector> &types, - uint32_t index, Kind kind, uint32_t bytesize, - std::vector secinfos) - : Type(types, index, 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, + Kind kind, + uint32_t bytesize, + std::vector secinfos) + : Type(types, index, 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 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 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 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 + 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 8c542e67..f1b3c8cc 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 @@ -47,10 +48,11 @@ namespace abigail { * USAGE * * Before examining a node, check it's not been assigned to an SCC 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. + * 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. * Infomation about the node can be stored provisionally, but must NOT be used @@ -62,50 +64,58 @@ namespace abigail { * the nodes as visited), this should be done now. Otherwise, an empty vector * will be returned. */ -template> class SCC { - public: - ~SCC() { +template > class SCC +{ +public: + ~SCC() + { assert(open_.empty()); assert(is_open_.empty()); assert(root_index_.empty()); } - std::optional Open(const Node &node) { + std::optional + Open(const Node& node) + { // Insertion will fail if the node is already open. auto [it, inserted] = is_open_.insert({node, is_open_.size()}); auto ix = it->second; - if (!inserted) { - // Pop indices to nodes which cannot be the root of their SCC. - while (root_index_.back() > ix) - root_index_.pop_back(); - return {}; - } + if (!inserted) + { + // Pop indices to nodes which cannot be the root of their SCC. + while (root_index_.back() > ix) + root_index_.pop_back(); + return {}; + } // Unvisited, record open node and record root index. open_.push_back(node); root_index_.push_back(ix); return ix; } - std::vector Close(size_t ix) { + std::vector + Close(size_t ix) + { std::vector scc; assert(ix < open_.size()); - if (ix == root_index_.back()) { - // Close SCC. - for (size_t o = ix; o < open_.size(); ++o) - is_open_.erase(open_[o]); - std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); - open_.resize(ix); - root_index_.pop_back(); - } + if (ix == root_index_.back()) + { + // Close SCC. + for (size_t o = ix; o < open_.size(); ++o) + is_open_.erase(open_[o]); + std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); + open_.resize(ix); + root_index_.pop_back(); + } return scc; } - private: - std::vector open_; // index to node - std::unordered_map is_open_; // node to index +private: + std::vector open_; // index to node + std::unordered_map is_open_; // node to index 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 39a8e480..c681bf2e 100644 --- a/src/abg-btf.cc +++ b/src/abg-btf.cc @@ -21,64 +21,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, - const std::string &text) const { +Name +Name::Add(Side side, Precedence precedence, const std::string& text) const +{ bool bracket = precedence < precedence_; std::ostringstream left; std::ostringstream right; @@ -100,32 +98,43 @@ Name Name::Add(Side side, Precedence precedence, 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); } @@ -134,47 +143,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); @@ -183,74 +202,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(); @@ -260,56 +304,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; @@ -322,158 +386,198 @@ 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) +{ const 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. state.provisional.insert({comparison, result.details_}); auto comparisons = state.scc.Close(handle.value()); - 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); - return {true, {}}; - } else { - // Different. Record diffs. - for (auto &c : comparisons) { - auto it = state.provisional.find(c); - state.outcomes.insert(*it); - state.provisional.erase(it); - } + 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); + return {true, {}}; + } + else + { + // Different. Record diffs. + for (auto& c : comparisons) + { + auto it = state.provisional.find(c); + state.outcomes.insert(*it); + state.provisional.erase(it); + } + } } - } // 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{"qualifier"}; } -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()) @@ -481,506 +585,606 @@ 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); } static constexpr std::string_view ANON{"(anon)"}; -std::ostream &operator<<(std::ostream &os, const Ptr &bp) { - os << kRawKindNames[bp.GetKind()] - << " '" << ANON << "'" - << " type_id=" << bp.GetPointeeTypeId() - << '\n'; +std::ostream& +operator<<(std::ostream& os, const Ptr& bp) +{ + os << kRawKindNames[bp.GetKind()] << " '" << ANON << "'" + << " type_id=" << bp.GetPointeeTypeId() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Typedef &bp) { - os << kRawKindNames[bp.GetKind()] - << " '" << bp.GetName() << "'" - << " type_id=" << bp.GetReferredTypeId() - << '\n'; +std::ostream& +operator<<(std::ostream& os, const Typedef& bp) +{ + os << kRawKindNames[bp.GetKind()] << " '" << bp.GetName() << "'" + << " type_id=" << bp.GetReferredTypeId() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Qualifier &bp) { - os << kRawKindNames[bp.GetKind()] - << " '" << ANON << "'" - << " type_id=" << bp.GetQualifiedTypeId() - << '\n'; +std::ostream& +operator<<(std::ostream& os, const Qualifier& bp) +{ + os << kRawKindNames[bp.GetKind()] << " '" << ANON << "'" + << " type_id=" << bp.GetQualifiedTypeId() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Integer &bi) { - os << kRawKindNames[bi.GetKind()] - << " '" << bi.GetName() << "'" - << " 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 << kRawKindNames[bi.GetKind()] << " '" << bi.GetName() << "'" + << " 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 << kRawKindNames[ba.GetKind()] - << " '" << ANON << "'" +std::ostream& +operator<<(std::ostream& os, const Array& ba) +{ + os << kRawKindNames[ba.GetKind()] << " '" << ANON << "'" << " type_id=" << ba.GetElementTypeId() << " index_type_id=" << ba.GetIndexTypeId() - << " nr_elems=" << ba.GetNumberOfElements() - << '\n'; + << " nr_elems=" << ba.GetNumberOfElements() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const StructUnion &bsu) { - const auto &name = bsu.GetName(); - os << kRawKindNames[bsu.GetKind()] - << " '" << (name.empty() ? ANON : name) << "'" - << " 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'; - } +std::ostream& +operator<<(std::ostream& os, const StructUnion& bsu) +{ + const auto& name = bsu.GetName(); + os << kRawKindNames[bsu.GetKind()] << " '" << (name.empty() ? ANON : name) + << "'" + << " 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) { - const auto &name = be.GetName(); - os << kRawKindNames[be.GetKind()] - << " '" << (name.empty() ? ANON : name) << "'" - << " size=" << be.GetByteSize() - << " vlen=" << be.GetEnums().size() +std::ostream& +operator<<(std::ostream& os, const Enumeration& be) +{ + const auto& name = be.GetName(); + os << kRawKindNames[be.GetKind()] << " '" << (name.empty() ? ANON : name) + << "'" + << " size=" << be.GetByteSize() << " vlen=" << be.GetEnums().size() << '\n'; - for (const auto &e : be.GetEnums()) { - os << "\t'" << e.first << "' val=" << e.second << '\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 << kRawKindNames[bfd.GetKind()] - << " '" << bfd.GetName() << "'" - << " fwd_kind=" << bfd.GetFwdKind() - << '\n'; +std::ostream& +operator<<(std::ostream& os, const ForwardDeclaration& bfd) +{ + os << kRawKindNames[bfd.GetKind()] << " '" << bfd.GetName() << "'" + << " fwd_kind=" << bfd.GetFwdKind() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const Function &bf) { - os << kRawKindNames[bf.GetKind()] - << " '" << bf.GetName() << "'" - << " type_id=" << bf.GetReferredTypeId() - << " linkage=" << bf.GetLinkage() +std::ostream& +operator<<(std::ostream& os, const Function& bf) +{ + os << kRawKindNames[bf.GetKind()] << " '" << bf.GetName() << "'" + << " type_id=" << bf.GetReferredTypeId() << " linkage=" << bf.GetLinkage() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const FunctionPrototype &bfp) { - os << kRawKindNames[bfp.GetKind()] - << " '" << ANON << "'" +std::ostream& +operator<<(std::ostream& os, const FunctionPrototype& bfp) +{ + os << kRawKindNames[bfp.GetKind()] << " '" << ANON << "'" << " 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 << kRawKindNames[bv.GetKind()] - << " type_id=" << bv.GetVarTypeId() - << ", linkage=" << bv.GetLinkage() - << '\n'; + os << kRawKindNames[bv.GetKind()] << " type_id=" << bv.GetVarTypeId() + << ", linkage=" << bv.GetLinkage() << '\n'; return os; } -std::ostream &operator<<(std::ostream &os, const DataSection &bds) { - os << kRawKindNames[bds.GetKind()] - << " 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 << kRawKindNames[bds.GetKind()] << " 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) { +std::ostream& +operator<<(std::ostream& os, const ElfSymbol& bes) +{ os << kRawKindNames[bes.GetKind()]; // 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. @@ -989,13 +1193,15 @@ Structs::Structs(const char *start, // recognized type starting from id 1. types_.push_back(std::make_unique(types_, 0, 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 @@ -1003,361 +1209,436 @@ 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, kind, t->type)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_PTR: + { + types_.push_back(std::make_unique(types_, index, 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, kind, t->type)); - if (verbose_) { - std::cout << types_.back()->as(); + case BTF_KIND_RESTRICT: + { + types_.push_back( + std::make_unique(types_, index, 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, 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, + 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(); + 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_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_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; } - 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_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; } - 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_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; } - 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_PROTO: + { + const auto* params = reinterpret_cast(data); + std::vector parameters = BuildParams(params, vlen); + types_.push_back(std::make_unique( + types_, index, kind, t->type, parameters)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_param); + 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, kind, t->type, parameters)); - 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; } - 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_DATASEC: + { + std::vector secinfos = BuildDatasec(t, vlen); + types_.push_back(std::make_unique( + types_, index, kind, t->size, secinfos)); + if (verbose_) + { + std::cout << types_.back()->as(); + } + type_size += vlen * sizeof(struct btf_var_secinfo); } - - 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, kind, t->size, secinfos)); - if (verbose_) { - std::cout << types_.back()->as(); - } - type_size += vlen * sizeof(struct btf_var_secinfo); } - } return type_size; } -std::string Structs::GetName(uint32_t name_off) { +std::string +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_begin = str_section_ + name_off; - const char *name_end = std::find(name_begin, section_end, '\0'); + "The name offset exceeds the section length"); + const char* section_end = str_section_ + header_->str_len; + const char* name_begin = str_section_ + name_off; + const char* name_end = std::find(name_begin, section_end, '\0'); m_assert(name_end < section_end, - "The name continues past the string section limit"); + "The name continues past the string section limit"); return {name_begin, static_cast(name_end - name_begin)}; } -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()); @@ -1365,5 +1646,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 a75b1ae0..62e840a1 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 0649821d..c90dc4c9 100644 --- a/tools/btfdiff.cc +++ b/tools/btfdiff.cc @@ -16,48 +16,51 @@ 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' }, - { nullptr, 0, nullptr, 0 }, + {"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"; + 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"; + << "' 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(); 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); + 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; 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);