From patchwork Thu Jun 9 11:06:27 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 54980 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 54366383DB91 for ; Thu, 9 Jun 2022 11:06:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 54366383DB91 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1654772801; bh=/Q+9aaHgj72MGftRtmG3dYgk3J2Z5hyZs7O0Y+IEpnc=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Help: List-Subscribe:From:Reply-To:Cc:From; b=p5azzstaYVPOlaz9/kgr8pxllkM2t/T28fVZmnw82nbsjLZ4TcEByuX0AXDxk/i9a UFyZDlkciepPvq9BMb1Z18DMZrsINRLKNUW5b9EqWG7titpzHQhaVYbn/vVooRClwE GtTvm1uvFVzQU7E2JmLuP91baF3S5Hyktf4q2dqc= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-ed1-x549.google.com (mail-ed1-x549.google.com [IPv6:2a00:1450:4864:20::549]) by sourceware.org (Postfix) with ESMTPS id EEA21384B122 for ; Thu, 9 Jun 2022 11:06:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EEA21384B122 Received: by mail-ed1-x549.google.com with SMTP id m6-20020aa7c2c6000000b0042dc237d9e7so16909180edp.15 for ; Thu, 09 Jun 2022 04:06:35 -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:message-id:mime-version:subject:from:to:cc; bh=/Q+9aaHgj72MGftRtmG3dYgk3J2Z5hyZs7O0Y+IEpnc=; b=QIY2e9alLESspjVlussfGPuH2Kkr4grnWVM046hsDBErFsJIMhutccueFhtjcYp1oc WIQi0dNT0NIVb7sPir0QwnoqTigAqKDOalXTjOOyGpp8utZalqzRIz2ntMLn9p49M6hC LfkBzREAEcbAIUPzGVoz8MhtXGXHJuAyTjALRp70Eb8zEHJKYKqlFNdZrixRqyCYNct+ 6SqPv/VuzN240cbXA1056bACmL9xaKEROVOEG2F+07PqF9ELpeFM6/h1V+ZaX9qzfUzQ bE1bw4pybrTYcBBV8JrnD/mUuoU3qhP2DR0ODuU147aGAdPEiU5pFndowtwyO0JighSr YHuQ== X-Gm-Message-State: AOAM533zTg3Of0J7oaZOKvFKBEMGIvpo5hEDgPj0Tti8eIBbQN1/nft+ CV71cPt8U+ePNd62LkgKWzTZwk+o/PYKrFU+CCmNUcNwipxj/Opm6nKbpD92o/ojPpvwceiwKoo r2vsZSulIY2tfJVZoQayZcA9io3Vd74ylGG0Foy4VRmQSlFvAMrxj2Pi7tTrbb3tpBQd1qhs= X-Google-Smtp-Source: ABdhPJwKaL7SRQGQIwIimuSGahHTESE1XBoeExlfgGHNUoS1BER+ECGKQlBNVqNExo51Tl4u1smP97q6EZVCrA== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:209:4f16:ab95:20a4:cafb]) (user=gprocida job=sendgmr) by 2002:aa7:c604:0:b0:42d:cffb:f4dc with SMTP id h4-20020aa7c604000000b0042dcffbf4dcmr45229605edq.270.1654772794592; Thu, 09 Jun 2022 04:06:34 -0700 (PDT) Date: Thu, 9 Jun 2022 12:06:27 +0100 Message-Id: <20220609110627.1469252-1-gprocida@google.com> Mime-Version: 1.0 X-Mailer: git-send-email 2.36.1.255.ge46751e96f-goog Subject: [PATCH] limit repeated DIE comparisons To: libabigail@sourceware.org X-Spam-Status: No, score=-21.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_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 | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc index 7bf2375d..11436bb0 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,13 @@ 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; + 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);