From patchwork Mon Jul 6 08:57:13 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 491498 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id AF562140DB8 for ; Mon, 6 Jul 2015 18:58:22 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=kMrjphJz; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=xmFDEbFrEcyYtu5XnPBpb+9g27uSb2kcjYn22/zqN4ESlb XgbXAC6uWfR9CK9PnxAjf5/Aa2SGpIvvSZqMLq6dQBv7vb52QKeFDzWVjosba4ta /ZIHvUgtoLFBLjTCwKASlq0wkSdHcuJtpAWp35M80DZpt6DYrE8mMfgtsE4cU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=gsA2HS3z9aqVTVdbcOLWxqelxg0=; b=kMrjphJzkeD6+NooPf8V 6hk06YkVGtN3w6pGyCy8ULHFFKUlAnTH6JmnUs/fPUcyDlIJu2iFqqy6+EfoJUht AllwdDJvXPOH5USFCDD6wkB1HG2ZZwxaqpwE2W6Epg6tYkEqQKC8FTy1zDsDaxmj 5xs649+T3mXjdFOlpPTMoh0= Received: (qmail 26893 invoked by alias); 6 Jul 2015 08:58:13 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 26878 invoked by uid 89); 6 Jul 2015 08:58:12 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 X-HELO: fencepost.gnu.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (208.118.235.10) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 06 Jul 2015 08:58:11 +0000 Received: from eggs.gnu.org ([2001:4830:134:3::10]:36464) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1ZC2E5-0008OV-M6 for gcc-patches@gnu.org; Mon, 06 Jul 2015 04:58:09 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZC2E1-0008CJ-6W for gcc-patches@gnu.org; Mon, 06 Jul 2015 04:58:09 -0400 Received: from relay1.mentorg.com ([192.94.38.131]:37403) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZC2E1-0008Bz-0I for gcc-patches@gnu.org; Mon, 06 Jul 2015 04:58:05 -0400 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-FEM-01.mgc.mentorg.com) by relay1.mentorg.com with esmtp id 1ZC2Dx-0003xR-SM from Tom_deVries@mentor.com for gcc-patches@gnu.org; Mon, 06 Jul 2015 01:58:02 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.3.224.2; Mon, 6 Jul 2015 09:57:28 +0100 Message-ID: <559A42E9.6000303@mentor.com> Date: Mon, 6 Jul 2015 10:57:13 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0 MIME-Version: 1.0 To: "gcc-patches@gnu.org" Subject: [RFC] two-phase marking in gt_cleare_cache X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-Received-From: 192.94.38.131 Hi, Using attached untested patch, I managed to minimize a test-case failure for PR 66714. The patch introduces two-phase marking in gt_cleare_cache: - first phase, it loops over all the hash table entries and removes those which are dead - second phase, it runs over all the live hash table entries and marks live items that are reachable from those live entries By doing so, we make the behaviour of gt_cleare_cache independent of the order in which the entries are visited, turning: - hard-to-trigger bugs which trigger for one visiting order but not for another, into - more easily triggered bugs which trigger for any visiting order. Any comments? Thanks, - Tom Add checking in gt_cleare_cache --- gcc/hash-table.h | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 12e0c96..c2ea112 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -1046,7 +1046,37 @@ gt_cleare_cache (hash_table *h) if (!h) return; - for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter) + typename table::iterator iter; + +#ifdef CHECKING + /* Say we have: + 1. cache entry A, with keep_change_entry (A) == 1, and + 2. cache entry B, with keep_change_entry (B) == 0, and + 3. gt_ggc_mx (A) marks things live in such a way that keep_change_entry (B) + becomes 1. + + In the loop at the end of the function, if A is visited first, then B is + kept. If B is visited first, it is deleted. + + We don't want the situation that the result of this function is dependent + on the order in which the entries are visited, so we consider this + situation a bug. + + In order to stabilize the result of the function in presence of the bug, we + first clear all entries E with keep_change_entry (E) == 0. By doing so, we + also maximize the impact of the liveness analysis done up until now, which + we hope makes it more likely that we run into bugs regarding that analysis. + We only do this when checking since it's more expensive. */ + for (iter = h->begin (); iter != h->end (); ++iter) + if (!table::is_empty (*iter) && !table::is_deleted (*iter)) + { + int res = H::keep_cache_entry (*iter); + if (res == 0) + h->clear_slot (&*iter); + } +#endif + + for (iter = h->begin (); iter != h->end (); ++iter) if (!table::is_empty (*iter) && !table::is_deleted (*iter)) { int res = H::keep_cache_entry (*iter); -- 1.9.1