This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [RFC] two-phase marking in gt_cleare_cache
- From: Tom de Vries <Tom_deVries at mentor dot com>
- To: Michael Matz <matz at suse dot de>, Richard Biener <richard dot guenther at gmail dot com>
- Cc: "gcc-patches at gnu dot org" <gcc-patches at gnu dot org>
- Date: Thu, 9 Jul 2015 14:05:57 +0200
- Subject: Re: [RFC] two-phase marking in gt_cleare_cache
- Authentication-results: sourceware.org; auth=none
- References: <559A42E9 dot 6000303 at mentor dot com> <CAFiYyc3d8EJW_g6af1_7T-uBAA=rqB3D4CnSmNL0ccE4xL0Z0A at mail dot gmail dot com> <CAFiYyc0vHS2R0hKboHCPOd7oomU0EyrvpVxYNy_R79Jj9ebg9A at mail dot gmail dot com> <alpine dot LSU dot 2 dot 20 dot 1507061602300 dot 23227 at wotan dot suse dot de> <559E507F dot 5030107 at mentor dot com>
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<typename T> friend void gt_pch_nx (hash_table<T> *,
gt_pointer_operator, void *);
- template<typename T> friend void gt_cleare_cache (hash_table<T> *);
+ template<typename T> friend unsigned int gt_cleare_cache (hash_table<T> *,
+ 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<D> *h, gt_pointer_operator op, void *cookie)
}
template<typename H>
-inline void
-gt_cleare_cache (hash_table<H> *h)
+inline unsigned int
+gt_cleare_cache (hash_table<H> *h, unsigned int phase)
{
+ unsigned int clear_cnt = 0;
+
extern void gt_ggc_mx (typename H::value_type &t);
typedef hash_table<H> 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