From patchwork Tue Jul 7 09:39:31 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: 492118 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 DBA691402A3 for ; Tue, 7 Jul 2015 19:40:42 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=UV3qsUV+; 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=Pn6rUR7/xdYaEIFFT Uaq8a8cV/9XifDonthdsKncp3S++3q+4IX7gQ0P6FaDBKoDcFCYMk93cChrgeh0A T9y3UB2CUOS3kFSTQPq19thZPgktJflsi34aCE6Cpdlazl3CIUThDQju469Ufpch aApepWDZKdvOZQsUIFgqLW/CZI= 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=5tL0pWgFqH91gJPArmR9ERA fZxg=; b=UV3qsUV+UVjnNTdrqTaIDuZL6c5eU46qIuxjlEzubUT9vzZNSZwoKIR KO3DT6U7lM8zIgUqfoRnkG7YkCl7nQDQ/6EhRrfaszMmBOKvMcOik0TZ8iyYmW9N i52MP5pDrWS8zBfO1jFaSgLMq/hwxfAs8M1EsQaw2m4MEJYzGjmc= Received: (qmail 10274 invoked by alias); 7 Jul 2015 09:40:35 -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 10263 invoked by uid 89); 7 Jul 2015 09:40:34 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.4 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; Tue, 07 Jul 2015 09:40:32 +0000 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38861) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1ZCPMc-0006TO-KO for gcc-patches@gnu.org; Tue, 07 Jul 2015 05:40:30 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZCPMY-0005v3-EG for gcc-patches@gnu.org; Tue, 07 Jul 2015 05:40:29 -0400 Received: from relay1.mentorg.com ([192.94.38.131]:39486) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZCPMY-0005qN-6B for gcc-patches@gnu.org; Tue, 07 Jul 2015 05:40:26 -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 1ZCPMU-0006lB-W2 from Tom_deVries@mentor.com ; Tue, 07 Jul 2015 02:40:23 -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; Tue, 7 Jul 2015 10:39:49 +0100 Message-ID: <559B9E53.5090803@mentor.com> Date: Tue, 7 Jul 2015 11:39:31 +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: Richard Biener CC: "gcc-patches@gnu.org" , Trevor Saunders Subject: Re: [RFC] two-phase marking in gt_cleare_cache References: <559A42E9.6000303@mentor.com> <559ABB05.50301@mentor.com> In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-Received-From: 192.94.38.131 On 07/07/15 10:42, Richard Biener wrote: > On Mon, Jul 6, 2015 at 7:29 PM, Tom de Vries wrote: >> On 06/07/15 15:29, Richard Biener wrote: >>> >>> On Mon, Jul 6, 2015 at 3:25 PM, Richard Biener >>> wrote: >>>> >>>> On Mon, Jul 6, 2015 at 10:57 AM, Tom de Vries >>>> wrote: >>>>> >>>>> 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? >>>> >>>> >>>> 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). >>> >>> >> >> [ Btw, we have been discussing a similar issue before: >> https://gcc.gnu.org/ml/gcc/2010-07/msg00077.html ] >> >> True, the problem exists at the scope of all variables marked with 'cache', >> and this patch addresses the problem only within a single variable. >> >>> Hmm, and don't we rather want to first mark and _then_ clear? >> >> >> I. In favor of first clear and then mark: >> >> It allows for: >> - a lazy one phase implementation for !ENABLE_CHECKING where >> you do a single clear-or-mark phase (so the clear is lazy). >> - an eager two phase implementation for ENABLE_CHECKING (where the >> clear is eager) >> The approach of first a marking phase and then a clearing phase means you >> always have to do these two phases (you can't do the marking lazily). > > True. > >> First mark and then clear means the marking should be done iteratively. Each >> time you mark something live, another entry in another hash table could >> become live. Marking iteratively could become quite costly. > > I don't see this - marking is done recursively so if one entry makes another > live and that makes another live the usual GC marking recursion will deal > with this? > That is not my understanding. Marking an item live doesn't mean that the associated cache entries become live. For that, we have to iterate again over all hash tables and all entries to find those entries. And by marking those, we may find new items which are live. And the process starts over again, until fixed point. [ If we maintain a per-item list of cache entries the item is the key for, then we can do this recursively, rather than iteratively. ] >> II. In favor of first mark and then clear: >> >> The users of garbage collection will need to be less precise. >> >>> 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'm not sure I understand the scenario you're concerned about, but ... say >> we have >> - entry B: item B -> item A >> - entry A: item A -> item Z >> >> If you do clear first and mark second, and you start out with item B live >> and item A dead: >> - during the clearing phase you clear entry A and keep entry B, and >> - during the marking phase you mark item A live. >> >> So we no longer have entry A, but item A is kept and entry B is kept. > > Yes. This makes the cache weaker in that after this GC operation > a lookup of A no longer succeeds but it still is there. > > The whole point of your patch was to make the behavior more predictable > and in some way it succeeds (within a cache). As it is supposed to > put more stress on the cache logic (it's ENABLE_CHECKING only) > it makes sense to clear optimistically (after all it's a cache and not > guaranteed to find a still live entry). It would be still nice to cover > all caches together because as I remember we've mostly seen issues > of caches interacting. > Attached patch (completed no-bootstrap c-only build) implements that. Thanks, - Tom Add clear-phase/mark-phase cache clearing 2015-07-07 Tom de Vries * gengtype.c (finish_cache_funcs): Add phase param to gt_clear_caches_ and gt_clear_caches. (write_roots): Add phase param to gt_clear_caches_, and use. * ggc-common.c (ggc_mark_roots): Add arg to call to gt_clear_caches. Call gt_clear_caches twice for ENABLE_CHECKING. * ggc.h (gt_clear_caches): Add phase param to declaration. * hash-table.h (gt_cleare_cache): Add and handle phase param. --- gcc/gengtype.c | 11 ++++++----- gcc/ggc-common.c | 11 ++++++++++- gcc/ggc.h | 2 +- gcc/hash-table.h | 55 ++++++++++++++++++++++++++++++++++++++++++++----------- 4 files changed, 61 insertions(+), 18 deletions(-) diff --git a/gcc/gengtype.c b/gcc/gengtype.c index 137e0ff..e138fd8 100644 --- a/gcc/gengtype.c +++ b/gcc/gengtype.c @@ -4211,12 +4211,13 @@ finish_cache_funcs (flist *flp) { oprintf (base_files[fnum], "extern void 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], + "void\ngt_clear_caches (unsigned int phase)\n{\n"); for (fli2 = flp; fli2; fli2 = fli2->next) if (fli2->started_p) @@ -4231,7 +4232,7 @@ finish_cache_funcs (flist *flp) { oprintf (base_files[fnum], " gt_clear_caches_"); put_mangled_filename (base_files[fnum], fli2->file); - oprintf (base_files[fnum], " ();\n"); + oprintf (base_files[fnum], " (phase);\n"); } } @@ -4660,10 +4661,10 @@ write_roots (pair_p variables, bool emit_pch) oprintf (f, "void\ngt_clear_caches_"); put_mangled_filename (f, v->line.file); - oprintf (f, " ()\n{\n"); + oprintf (f, " (unsigned int phase)\n{\n"); } - oprintf (f, " gt_cleare_cache (%s);\n", v->name); + oprintf (f, " 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..4f7e383 100644 --- a/gcc/ggc-common.c +++ b/gcc/ggc-common.c @@ -100,7 +100,16 @@ ggc_mark_roots (void) if (ggc_protect_identifiers) ggc_mark_stringpool (); - gt_clear_caches (); +#ifdef ENABLE_CHECKING + /* Phase 1: Clear. */ + gt_clear_caches (1); + + /* Phase 2: Mark. */ + gt_clear_caches (2); +#else + /* Phase 0: Mark or Clear. */ + gt_clear_caches (0); +#endif if (! ggc_protect_identifiers) ggc_purge_stringpool (); diff --git a/gcc/ggc.h b/gcc/ggc.h index ebc6a5d..0f6ff85 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 void 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..380e90f 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 void 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); @@ -1039,22 +1040,54 @@ gt_pch_nx (hash_table *h, gt_pointer_operator op, void *cookie) template inline void -gt_cleare_cache (hash_table *h) +gt_cleare_cache (hash_table *h, unsigned int phase) { extern void gt_ggc_mx (typename H::value_type &t); typedef hash_table table; if (!h) return; - 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: Mark or 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); + else if (res != -1) + gt_ggc_mx (*iter); + } + break; + + case 1: + /* Phase 1: 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; + + case 2: + /* Phase 2: 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; + + default: + gcc_unreachable (); + } } #endif /* TYPED_HASHTAB_H */ -- 1.9.1