From patchwork Thu Jul 9 12:05:57 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: 493393 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 28BE11402AA for ; Thu, 9 Jul 2015 22:06:41 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=RamnfEwn; 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:cc:subject:references :in-reply-to:content-type; q=dns; s=default; b=IBA/Jq8aALJ7crsXD i2OZod3EtQLtgi3gNvXBv2e9T2sACTG4n/pGGyAZzM/SRQ9pHxWPycvQYSZNP6hf flvObkreZBHFQcPXlI8JSn7dzXJZnhyF2f0G+PtqvEOssEjZtwu8IYSrr/v2hqW/ xyTVDq2vFXtAFfZDSDRFh9bdfg= 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:cc:subject:references :in-reply-to:content-type; s=default; bh=QIShambOoGcd0GdxY0iJnLj C1Cc=; b=RamnfEwnxj76MTt2DX5thGYT/XRDPnpUCiwvtFazfBaRCqtnr/a9/4X z4Dgt4yCK0zwlLphktnFLqSWmfU7qO/QiL2HG+NKP/E/HyjyegSFjE/n+lfzng3/ 96c21TMyWBaTEUQRC4YjTYMaHnaThAUxMV8jBFSesJ/JV7RSkyug= Received: (qmail 36781 invoked by alias); 9 Jul 2015 12:06:34 -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 36767 invoked by uid 89); 9 Jul 2015 12:06:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 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; Thu, 09 Jul 2015 12:06:31 +0000 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53417) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1ZDAaz-00064n-EM for gcc-patches@gnu.org; Thu, 09 Jul 2015 08:06:29 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZDAat-0007wV-93 for gcc-patches@gnu.org; Thu, 09 Jul 2015 08:06:29 -0400 Received: from relay1.mentorg.com ([192.94.38.131]:34409) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZDAat-0007w2-09 for gcc-patches@gnu.org; Thu, 09 Jul 2015 08:06:23 -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 1ZDAar-0001RC-6D from Tom_deVries@mentor.com ; Thu, 09 Jul 2015 05:06:21 -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; Thu, 9 Jul 2015 13:06:19 +0100 Message-ID: <559E63A5.1000108@mentor.com> Date: Thu, 9 Jul 2015 14:05:57 +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: Michael Matz , Richard Biener CC: "gcc-patches@gnu.org" Subject: Re: [RFC] two-phase marking in gt_cleare_cache References: <559A42E9.6000303@mentor.com> <559E507F.5030107@mentor.com> In-Reply-To: <559E507F.5030107@mentor.com> X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-Received-From: 192.94.38.131 On 09/07/15 12:44, Tom de Vries wrote: > On 07/07/15 16:00, Michael Matz wrote: >> Hi, >> >> On Mon, 6 Jul 2015, Richard Biener wrote: >> >>>>> 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? >>>> >>>> I think it is only half-way correct in your proposed change. You only >>>> fix the issue for hashes of the same kind. To truly fix the issue >>>> you'd >>>> have to change generated code for gt_clear_caches () and provide >>>> a clearing-only implementation (or pass a operation mode bool to >>>> the core worker in hash-table.h). >>> >>> Hmm, and don't we rather want to first mark and _then_ clear? Because >>> if entry B in the hash is live and would keep A live then A _is_ kept in >>> the end but you'll remove it from the hash, possibly no longer using a >>> still live copy. >> >> I don't think such use has ever worked with the caching hash tables. >> Even >> the old (before c++) scheme didn't iterate, i.e. if a cache-hash entry A >> became life from outside, but it itself kept an entry B live in the hash >> table (with no other references to B) then this never worked (or only by >> luck), because the slot was always cleared if !ggc_marked_p, so if B was >> visited before A it was removed from the hash-table (and in particular >> B's >> gt_ggc_mx routine was never called, so whatever B needed wasn't even >> marked). >> >> Given this I think the call to gt_ggc_mx is superfluous because it >> wouldn't work relyably for multi-step dependencies anyway. Hence a >> situation that works with that call in place, and breaking without it is >> actually a bug waiting to be uncovered. >> > > Attached patch tries to get multi-step dependencies right, without using > iteration-till-fixed-point. And for the record, attached patch implements a naive iterative approach. Thanks, - Tom Use iterative strategy for caches --- gcc/gengtype.c | 29 +++++++++++++++++---------- gcc/ggc-common.c | 26 +++++++++++++++++++++++- gcc/ggc.h | 2 +- gcc/hash-table.h | 61 ++++++++++++++++++++++++++++++++++++++++++++------------ 4 files changed, 93 insertions(+), 25 deletions(-) diff --git a/gcc/gengtype.c b/gcc/gengtype.c index 137e0ff..3e912e3 100644 --- a/gcc/gengtype.c +++ b/gcc/gengtype.c @@ -4197,7 +4197,10 @@ finish_cache_funcs (flist *flp) for (fli2 = flp; fli2; fli2 = fli2->next) if (fli2->started_p) { - oprintf (fli2->f, "}\n\n"); + oprintf (fli2->f, + " return clear_cnt;\n" + "}\n" + "\n"); } for (fli2 = flp; fli2 && base_files; fli2 = fli2->next) @@ -4209,14 +4212,18 @@ finish_cache_funcs (flist *flp) for (fnum = 0; bitmap != 0; fnum++, bitmap >>= 1) if (bitmap & 1) { - oprintf (base_files[fnum], "extern void gt_clear_caches_"); + oprintf (base_files[fnum], "extern unsigned int gt_clear_caches_"); put_mangled_filename (base_files[fnum], fli2->file); - oprintf (base_files[fnum], " ();\n"); + oprintf (base_files[fnum], " (unsigned int);\n"); } } for (size_t fnum = 0; base_files && fnum < num_lang_dirs; fnum++) - oprintf (base_files[fnum], "void\ngt_clear_caches ()\n{\n"); + oprintf (base_files[fnum], + "unsigned int\n" + "gt_clear_caches (unsigned int phase)\n" + "{\n" + " unsigned int clear_cnt = 0;\n"); for (fli2 = flp; fli2; fli2 = fli2->next) if (fli2->started_p) @@ -4229,15 +4236,17 @@ finish_cache_funcs (flist *flp) for (fnum = 0; base_files && bitmap != 0; fnum++, bitmap >>= 1) if (bitmap & 1) { - oprintf (base_files[fnum], " gt_clear_caches_"); + oprintf (base_files[fnum], " clear_cnt += gt_clear_caches_"); put_mangled_filename (base_files[fnum], fli2->file); - oprintf (base_files[fnum], " ();\n"); + oprintf (base_files[fnum], " (phase);\n"); } } for (size_t fnum = 0; base_files && fnum < num_lang_dirs; fnum++) { - oprintf (base_files[fnum], "}\n"); + oprintf (base_files[fnum], + " return clear_cnt;\n" + "}\n"); } } @@ -4658,12 +4667,12 @@ write_roots (pair_p variables, bool emit_pch) { fli->started_p = 1; - oprintf (f, "void\ngt_clear_caches_"); + oprintf (f, "unsigned int\ngt_clear_caches_"); put_mangled_filename (f, v->line.file); - oprintf (f, " ()\n{\n"); + oprintf (f, " (unsigned int phase)\n{\n unsigned int clear_cnt = 0;\n"); } - oprintf (f, " gt_cleare_cache (%s);\n", v->name); + oprintf (f, " clear_cnt += gt_cleare_cache (%s, phase);\n", v->name); } finish_cache_funcs (flp); diff --git a/gcc/ggc-common.c b/gcc/ggc-common.c index 5096837..110640c 100644 --- a/gcc/ggc-common.c +++ b/gcc/ggc-common.c @@ -100,7 +100,31 @@ ggc_mark_roots (void) if (ggc_protect_identifiers) ggc_mark_stringpool (); - gt_clear_caches (); + unsigned int clear_cnt, prev_clear_cnt; + unsigned int iteration = 0; + + /* Mark. */ + ++iteration; + gt_clear_caches (1); + + /* Count. */ + clear_cnt = gt_clear_caches (0); + + do + { + prev_clear_cnt = clear_cnt; + + /* Mark. */ + ++iteration; + gt_clear_caches (1); + + /* Count. */ + clear_cnt = gt_clear_caches (0); + } + while (clear_cnt != prev_clear_cnt); + + /* Clear. */ + gt_clear_caches (2); if (! ggc_protect_identifiers) ggc_purge_stringpool (); diff --git a/gcc/ggc.h b/gcc/ggc.h index ebc6a5d..eaf4236 100644 --- a/gcc/ggc.h +++ b/gcc/ggc.h @@ -54,7 +54,7 @@ extern int gt_pch_note_object (void *, void *, gt_note_pointers); extern void gt_pch_note_reorder (void *, void *, gt_handle_reorder); /* generated function to clear caches in gc memory. */ -extern void gt_clear_caches (); +extern unsigned int gt_clear_caches (unsigned int); /* Mark the object in the first parameter and anything it points to. */ typedef void (*gt_pointer_walker) (void *); diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 12e0c96..2408953 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -491,7 +491,8 @@ private: template friend void gt_pch_nx (hash_table *, gt_pointer_operator, void *); - template friend void gt_cleare_cache (hash_table *); + template friend unsigned int gt_cleare_cache (hash_table *, + unsigned int phase); value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const; value_type *find_empty_slot_for_expand (hashval_t); @@ -1038,23 +1039,57 @@ gt_pch_nx (hash_table *h, gt_pointer_operator op, void *cookie) } template -inline void -gt_cleare_cache (hash_table *h) +inline unsigned int +gt_cleare_cache (hash_table *h, unsigned int phase) { + unsigned int clear_cnt = 0; + extern void gt_ggc_mx (typename H::value_type &t); typedef hash_table table; if (!h) - return; + return clear_cnt; - for (typename table::iterator 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); - else if (res != -1) - gt_ggc_mx (*iter); - } + typename table::iterator iter; + switch (phase) + { + case 0: + /* Phase 0: Count. */ + 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) + clear_cnt++; + } + break; + + case 1: + /* Phase 1: Mark. */ + 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 == 1) + gt_ggc_mx (*iter); + } + break; + + case 2: + /* Phase 2: Clear. */ + 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); + } + break; + + default: + gcc_unreachable (); + } + + return clear_cnt; } #endif /* TYPED_HASHTAB_H */ -- 1.9.1