From patchwork Thu Jun 9 11:17:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 54981 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 F3FF4383D83A for ; Thu, 9 Jun 2022 11:17:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F3FF4383D83A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1654773472; bh=7/4MXmRepMN0c04O5bzGJnoopHloRNnC/5mmsC7LAQI=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=FGIti/keybckAMFkp+koZ9m1vzGiN8CsdrOVZvmyE8wmw29v2cygqmuAYJzUp3Q6O ToCgo3CMpmRzX7O2j8gh2YW0IUEumqYPX6zEfRalROs5GBAcspIqlEQXgYqtOuHW8M g8LuQFApoRxf0ORMt7Mg+1KaA05+ttJJPH1VaHdw= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-ed1-x54a.google.com (mail-ed1-x54a.google.com [IPv6:2a00:1450:4864:20::54a]) by sourceware.org (Postfix) with ESMTPS id 26DC93856081 for ; Thu, 9 Jun 2022 11:17:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 26DC93856081 Received: by mail-ed1-x54a.google.com with SMTP id x15-20020a05640226cf00b004318eab9feaso5598901edd.12 for ; Thu, 09 Jun 2022 04:17:47 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=7/4MXmRepMN0c04O5bzGJnoopHloRNnC/5mmsC7LAQI=; b=Urxk/xr/j95tOgBWezI6GfAeLwcjMlSfibbBBKOqD8aMZig2UzRwI99JThHQls5HMS LBGU7L0njGQb8vDTUVgV+9jbETZ9bMNiBqMyoparNIYKQrXJaxRFMhe5waZoR9uvZaJX hoFTUlllSfQcE/NZrH6f7wRoJU7ENz1nGB0NwvlcDyblZmzirSeLqEA4IogugVu5mTWM N3E0TV15+28Kpi6u2FlETxlV3/np+dJBfm5crXIwZmY7hPFnbDaWdk2FHSLiEX8zgF/P ympIqkWQIPDkarP7q/pVubVLGJstdiSRTTtjLoyP34HgTNEPAmb9TFDLoAVZL/7pFf4B nmAg== X-Gm-Message-State: AOAM533SVy5MBXm5PJG9sngefaKlMvIexk0QKmqnR8RnhXNUh6vagokD kyp9Unit87mdP+GNKIOvLxXbsEeczadM8dzsj87bSXFmELDprX+eK5TiFeByvukUHmp6IVxem28 8eYloshr/I7Na4gGIW5TFtFYZhnNgWxI1/kPAAS/W8A62xvgQupwhQzneGM2FqjscvBUee7o= X-Google-Smtp-Source: ABdhPJwGS2cQeNY7ggyuFZIQ4G6h10rHi5doqcWi7/GT4mt8mbseQiG2eD3DKascKSJVm3InZ1h1RGyB19xnxA== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:209:4f16:ab95:20a4:cafb]) (user=gprocida job=sendgmr) by 2002:a05:6402:908:b0:428:11f5:509d with SMTP id g8-20020a056402090800b0042811f5509dmr44188839edz.253.1654773465841; Thu, 09 Jun 2022 04:17:45 -0700 (PDT) Date: Thu, 9 Jun 2022 12:17:35 +0100 In-Reply-To: <20220609110627.1469252-1-gprocida@google.com> Message-Id: <20220609111735.1488817-1-gprocida@google.com> Mime-Version: 1.0 References: <20220609110627.1469252-1-gprocida@google.com> X-Mailer: git-send-email 2.36.1.255.ge46751e96f-goog Subject: [PATCH v2] limit repeated DIE comparisons To: libabigail@sourceware.org X-Spam-Status: No, score=-21.4 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_SCC_BODY_TEXT_LINE, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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" Exponential explosion of DIE comparison has been possible since the limit of at most 5 pending struct/union DIE comparison pairs was lifted. This commit adds two things to control this (with a negligible chance of falsely finding that two DIEs are equivalent when they are not). - DIE self-comparisons immediately return true - once a DIE pair has been compared 10000 times, always return true * src/abg-dwarf-reader.cc (read_context): Add mutable die_comparison_visits_ member. (compare_dies): Return true if this is a self-comparison. Return true if we have visited this comparison 10000 times. Signed-off-by: Giuliano Procida --- src/abg-dwarf-reader.cc | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc index 7bf2375d..27dd4faf 100644 --- a/src/abg-dwarf-reader.cc +++ b/src/abg-dwarf-reader.cc @@ -2094,6 +2094,9 @@ public: /// A map that associates a function type representations to /// function types, inside a translation unit. mutable istring_fn_type_map_type per_tu_repr_to_fn_type_maps_; + mutable std::unordered_map, + size_t, + dwarf_offset_pair_hash> die_comparison_visits_; die_class_or_union_map_type die_wip_classes_map_; die_class_or_union_map_type alternate_die_wip_classes_map_; @@ -10216,6 +10219,15 @@ compare_dies(const read_context& ctxt, Dwarf_Off l_offset = dwarf_dieoffset(const_cast(l)), r_offset = dwarf_dieoffset(const_cast(r)); + + if (l_offset == r_offset) + return true; + auto& visit = ctxt.die_comparison_visits_[std::make_pair(l_offset, r_offset)]; + if (visit == 10000) + return true; + else + ++visit; + Dwarf_Off l_canonical_die_offset = 0, r_canonical_die_offset = 0; const die_source l_die_source = ctxt.get_die_source(l); const die_source r_die_source = ctxt.get_die_source(r);