| Message ID | alpine.LSU.2.20.1902041413310.23386@zhemvz.fhfr.qr |
|---|---|
| State | New |
| Headers | show |
| Series | Fix PR89150, GC of tree-form bitmaps | expand |
On Mon, Feb 4, 2019 at 2:16 PM Richard Biener <rguenther@suse.de> wrote: > When I introduced tree-form bitmaps I forgot to think about GC. > The following drops the chain_prev annotation to make the marker > work for trees. I don't understand this patch. How are the nodes in a bitmap tree now to be found for marking? This patch should cause an ICE on test cases with bitmaps as trees with ENABLE_GC_ALWAYS_COLLECT. Ciao! Steven
On Mon, 4 Feb 2019, Steven Bosscher wrote: > On Mon, Feb 4, 2019 at 2:16 PM Richard Biener <rguenther@suse.de> wrote: > > When I introduced tree-form bitmaps I forgot to think about GC. > > The following drops the chain_prev annotation to make the marker > > work for trees. > > I don't understand this patch. How are the nodes in a bitmap tree now > to be found for marking? > > This patch should cause an ICE on test cases with bitmaps as trees > with ENABLE_GC_ALWAYS_COLLECT. After the patch the marker routines look like void gt_ggc_mx_bitmap_head (void *x_p) { struct bitmap_head * const x = (struct bitmap_head *)x_p; if (ggc_test_and_set_mark (x)) { gt_ggc_m_14bitmap_element ((*x).first); } } void gt_ggc_mx_bitmap_element (void *x_p) { struct bitmap_element * x = (struct bitmap_element *)x_p; struct bitmap_element * xlimit = x; while (ggc_test_and_set_mark (xlimit)) xlimit = ((*xlimit).next); while (x != xlimit) { gt_ggc_m_14bitmap_element ((*x).next); gt_ggc_m_14bitmap_element ((*x).prev); x = ((*x).next); } } gt_ggc_m_14bitmap_element just is a NULL protected call to gt_ggc_mx_bitmap_element. So bitmap elements are marked by marking the ->next chain until we hit an already marked node and then recurse on all prev and next members (where the recursion will not chain ->next because we've already marked it). Previously it was void gt_ggc_mx_bitmap_element (void *x_p) { struct bitmap_element * x = (struct bitmap_element *)x_p; struct bitmap_element * xlimit = x; while (ggc_test_and_set_mark (xlimit)) xlimit = ((*xlimit).next); if (x != xlimit) for (;;) { struct bitmap_element * const xprev = ((*x).prev); if (xprev == NULL) break; x = xprev; (void) ggc_test_and_set_mark (xprev); } while (x != xlimit) { gt_ggc_m_14bitmap_element ((*x).next); gt_ggc_m_14bitmap_element ((*x).prev); x = ((*x).next); } } where the prev_chain handling "wrecked" things for trees and didn't help for the list implementation (since we've only come here via the bitmap_head->first link). Richard.
On 2/4/19 6:15 AM, Richard Biener wrote: > > When I introduced tree-form bitmaps I forgot to think about GC. > The following drops the chain_prev annotation to make the marker > work for trees. I've also maked the obstack member GTY skip > (and prevent bitmap_obstack from gengtype processing) because > the obstack isn't used for GC allocated bitmaps. > > Bootstrap & regtest running on x86_64-unknown-linux-gnu. > > Richard. > > 2019-02-04 Richard Biener <rguenther@suse.de> > > PR middle-end/89150 > * bitmap.h (struct bitmap_obstack): Do not mark GTY. > (struct bitmap_element): Drop chain_prev so we properly recurse on > the prev member, supporting tree views. > (struct bitmap_head): GTY skip the obstack member. Was there a particular failure mode you observed or was this discovered by inspection. The reason I ask is my tester is showing occasional failures bootstrapping hppa-linux-gnu with a segfault in ICF. I'd rather not have to dig into it if it can be avoided :-) Bootstrapping hppa via qemu is something like 6 hours... Jeff
On February 4, 2019 5:07:00 PM GMT+01:00, Jeff Law <law@redhat.com> wrote: >On 2/4/19 6:15 AM, Richard Biener wrote: >> >> When I introduced tree-form bitmaps I forgot to think about GC. >> The following drops the chain_prev annotation to make the marker >> work for trees. I've also maked the obstack member GTY skip >> (and prevent bitmap_obstack from gengtype processing) because >> the obstack isn't used for GC allocated bitmaps. >> >> Bootstrap & regtest running on x86_64-unknown-linux-gnu. >> >> Richard. >> >> 2019-02-04 Richard Biener <rguenther@suse.de> >> >> PR middle-end/89150 >> * bitmap.h (struct bitmap_obstack): Do not mark GTY. >> (struct bitmap_element): Drop chain_prev so we properly recurse on >> the prev member, supporting tree views. >> (struct bitmap_head): GTY skip the obstack member. >Was there a particular failure mode you observed or was this discovered >by inspection. It was discovered via an out of tree patch, the issue is only latent on trunk (together with another unfixed pch issue of bitmaps). >The reason I ask is my tester is showing occasional failures >bootstrapping hppa-linux-gnu with a segfault in ICF. Unlikely to fix this... >I'd rather not have to dig into it if it can be avoided :-) >Bootstrapping hppa via qemu is something like 6 hours... > >Jeff
On 2/4/19 9:07 AM, Jeff Law wrote: > On 2/4/19 6:15 AM, Richard Biener wrote: >> >> When I introduced tree-form bitmaps I forgot to think about GC. >> The following drops the chain_prev annotation to make the marker >> work for trees. I've also maked the obstack member GTY skip >> (and prevent bitmap_obstack from gengtype processing) because >> the obstack isn't used for GC allocated bitmaps. >> >> Bootstrap & regtest running on x86_64-unknown-linux-gnu. >> >> Richard. >> >> 2019-02-04 Richard Biener <rguenther@suse.de> >> >> PR middle-end/89150 >> * bitmap.h (struct bitmap_obstack): Do not mark GTY. >> (struct bitmap_element): Drop chain_prev so we properly recurse on >> the prev member, supporting tree views. >> (struct bitmap_head): GTY skip the obstack member. > Was there a particular failure mode you observed or was this discovered > by inspection. > > The reason I ask is my tester is showing occasional failures > bootstrapping hppa-linux-gnu with a segfault in ICF. > > I'd rather not have to dig into it if it can be avoided :-) > Bootstrapping hppa via qemu is something like 6 hours... And just to follow-up. I'm really starting to wonder if the hppa issue is a qemu bug of some kind. The faulting instruction, ACAICT, shouldn't be faulting. It appears to be loading from a valid address, it's a byte load (so no alignment issues). Furthermore, I can instruction-step over it in gdb. Anyway, I think we can reasonably conclude the PA issue is unrelated to your change. jeff
On 2019-02-04 11:39 a.m., Richard Biener wrote: > On February 4, 2019 5:07:00 PM GMT+01:00, Jeff Law <law@redhat.com> wrote: >> On 2/4/19 6:15 AM, Richard Biener wrote: >>> >>> When I introduced tree-form bitmaps I forgot to think about GC. >>> The following drops the chain_prev annotation to make the marker >>> work for trees. I've also maked the obstack member GTY skip >>> (and prevent bitmap_obstack from gengtype processing) because >>> the obstack isn't used for GC allocated bitmaps. >>> >>> Bootstrap & regtest running on x86_64-unknown-linux-gnu. >>> >>> Richard. >>> >>> 2019-02-04 Richard Biener <rguenther@suse.de> >>> >>> PR middle-end/89150 >>> * bitmap.h (struct bitmap_obstack): Do not mark GTY. >>> (struct bitmap_element): Drop chain_prev so we properly recurse on >>> the prev member, supporting tree views. >>> (struct bitmap_head): GTY skip the obstack member. >> Was there a particular failure mode you observed or was this discovered >> by inspection. > > It was discovered via an out of tree patch, the issue is only latent on trunk (together with another unfixed pch issue of bitmaps). My apologies for not noticing this thread/PR earlier. I originally discovered this issue while working on an experimental patch, but since then I've also come up with a test case for this specific issue. Is it worth adding it to trunk? - Michael From 9f1049a1e24cd1aa9852c5dddd1342dce0226416 Mon Sep 17 00:00:00 2001 From: Michael Ploujnikov <michael.ploujnikov@oracle.com> Date: Thu, 7 Feb 2019 14:43:40 -0500 Subject: [PATCH] Add a test for GC marking bitmaps in tree view mode gcc/ChangeLog: 2019-02-07 Michael Ploujnikov <michael.ploujnikov@oracle.com> PR middle-end/89150 * bitmap.c (test_bitmap_tree_marking): New test. (NOT_NULL_OR_GARBAGE): For shortening test_bitmap_tree_marking. (bitmap_c_tests): Add test_bitmap_tree_marking. --- gcc/bitmap.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) diff --git gcc/bitmap.c gcc/bitmap.c index 5a8236de75..7e802a1600 100644 --- gcc/bitmap.c +++ gcc/bitmap.c @@ -2626,6 +2626,11 @@ bitmap_head::dump () #if CHECKING_P +static GTY(()) bitmap selftest_test_bitmap; + +/* From ggc-internal.h */ +extern bool ggc_force_collect; + namespace selftest { /* Selftests for bitmaps. */ @@ -2722,6 +2727,82 @@ test_bitmap_single_bit_set_p () ASSERT_EQ (1066, bitmap_first_set_bit (b)); } +#define NOT_NULL_OR_GARBAGE(NODE) \ + (NODE != NULL && (unsigned long)(NODE) != 0xa5a5a5a5UL) + +static void +test_bitmap_tree_marking () +{ + selftest_test_bitmap = BITMAP_GGC_ALLOC (); + bitmap_tree_view (selftest_test_bitmap); + + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 1*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 5*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 10*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 15*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 30*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 25*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 3*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 4*BITMAP_ELEMENT_ALL_BITS)); + ASSERT_TRUE (bitmap_set_bit (selftest_test_bitmap, 26*BITMAP_ELEMENT_ALL_BITS)); + /* At this point it should look like: + 26 + / \ + 25 30 + / + 5 + / \ + 4 15 + / / + 3 10 + / + 1 + + */ + ggc_force_collect = true; + ggc_collect (); + ggc_force_collect = false; + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first)); + ASSERT_TRUE (selftest_test_bitmap->first->indx == 26); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->next)); + ASSERT_TRUE (selftest_test_bitmap->first->next->indx == 30); + ASSERT_TRUE (selftest_test_bitmap->first->next->next == NULL); + ASSERT_TRUE (selftest_test_bitmap->first->next->prev == NULL); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->prev)); + ASSERT_TRUE (selftest_test_bitmap->first->prev->indx == 25); + ASSERT_TRUE (selftest_test_bitmap->first->prev->next == NULL); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->prev->prev)); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->indx == 5); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->prev->prev->next)); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->next->indx == 15); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->next->next == NULL); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->prev->prev->next->prev)); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->next->prev->indx == 10); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->next->prev->prev == NULL); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->next->prev->next == NULL); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->prev->prev->prev)); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->prev->indx == 4); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->prev->next == NULL); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->prev->prev->prev->prev)); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->prev->prev->indx == 3); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->prev->prev->next == NULL); + + ASSERT_TRUE (NOT_NULL_OR_GARBAGE (selftest_test_bitmap->first->prev->prev->prev->prev->prev)); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->prev->prev->prev->indx == 1); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->prev->prev->prev->prev == NULL); + ASSERT_TRUE (selftest_test_bitmap->first->prev->prev->prev->prev->prev->next == NULL); + + ASSERT_TRUE (bitmap_bit_p (selftest_test_bitmap, 15*BITMAP_ELEMENT_ALL_BITS)); +} + /* Run all of the selftests within this file. */ void @@ -2732,6 +2813,7 @@ bitmap_c_tests () test_clear_bit_in_middle (); test_copying (); test_bitmap_single_bit_set_p (); + test_bitmap_tree_marking (); } } // namespace selftest
On Thu, Feb 07, 2019 at 03:04:21PM -0500, Michael Ploujnikov wrote: > 2019-02-07 Michael Ploujnikov <michael.ploujnikov@oracle.com> > > PR middle-end/89150 > * bitmap.c (test_bitmap_tree_marking): New test. > (NOT_NULL_OR_GARBAGE): For shortening > test_bitmap_tree_marking. > (bitmap_c_tests): Add test_bitmap_tree_marking. Could you do that instead in a plugin in the testsuite? I mean, the patch is adding garbage collection roots, so it will not affect just -fself-tests run, but also any time the compiler will do GC. Jakub
On 2019-02-07 3:09 p.m., Jakub Jelinek wrote: > On Thu, Feb 07, 2019 at 03:04:21PM -0500, Michael Ploujnikov wrote: >> 2019-02-07 Michael Ploujnikov <michael.ploujnikov@oracle.com> >> >> PR middle-end/89150 >> * bitmap.c (test_bitmap_tree_marking): New test. >> (NOT_NULL_OR_GARBAGE): For shortening >> test_bitmap_tree_marking. >> (bitmap_c_tests): Add test_bitmap_tree_marking. > > Could you do that instead in a plugin in the testsuite? > I mean, the patch is adding garbage collection roots, so it will not affect > just -fself-tests run, but also any time the compiler will do GC. > > Jakub > I'm not sure what I would need to do to get gengtype to process a test plugin source file and I can't find examples of this. Instead, shouldn't I just do something like what's at the bottom of gcc/ggc-tests.c and not worry about the extra root added to gt-bitmap.h? - Michael
On Fri, Feb 08, 2019 at 10:02:27AM -0500, Michael Ploujnikov wrote: > On 2019-02-07 3:09 p.m., Jakub Jelinek wrote: > > On Thu, Feb 07, 2019 at 03:04:21PM -0500, Michael Ploujnikov wrote: > >> 2019-02-07 Michael Ploujnikov <michael.ploujnikov@oracle.com> > >> > >> PR middle-end/89150 > >> * bitmap.c (test_bitmap_tree_marking): New test. > >> (NOT_NULL_OR_GARBAGE): For shortening > >> test_bitmap_tree_marking. > >> (bitmap_c_tests): Add test_bitmap_tree_marking. > > > > Could you do that instead in a plugin in the testsuite? > > I mean, the patch is adding garbage collection roots, so it will not affect > > just -fself-tests run, but also any time the compiler will do GC. > > > > Jakub > > > > I'm not sure what I would need to do to get gengtype to process a test > plugin source file and I can't find examples of this. > > Instead, shouldn't I just do something like what's at the bottom of > gcc/ggc-tests.c and not worry about the extra root added to > gt-bitmap.h? No, instead ggc-tests.c should be moved into a plugin too. You can run gengtype from within *.exp and the additional advantage is that you test how plugins work better. Jakub
Index: gcc/bitmap.h =================================================================== --- gcc/bitmap.h (revision 268509) +++ gcc/bitmap.h (working copy) @@ -288,10 +288,10 @@ typedef unsigned long BITMAP_WORD; #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS) /* Obstack for allocating bitmaps and elements from. */ -struct GTY (()) bitmap_obstack { +struct bitmap_obstack { struct bitmap_element *elements; struct bitmap_head *heads; - struct obstack GTY ((skip)) obstack; + struct obstack obstack; }; /* Bitmap set element. We use a linked list to hold only the bits that @@ -306,7 +306,7 @@ struct GTY (()) bitmap_obstack { bitmap_elt_clear_from to be implemented in unit time rather than linear in the number of elements to be freed. */ -struct GTY((chain_next ("%h.next"), chain_prev ("%h.prev"))) bitmap_element { +struct GTY((chain_next ("%h.next"))) bitmap_element { /* In list form, the next element in the linked list; in tree form, the left child node in the tree. */ struct bitmap_element *next; @@ -340,7 +340,7 @@ struct GTY(()) bitmap_head { /* Last element looked at. */ bitmap_element * GTY((skip(""))) current; /* Obstack to allocate elements from. If NULL, then use GGC allocation. */ - bitmap_obstack *obstack; + bitmap_obstack * GTY((skip(""))) obstack; void dump (); };