Re: 'hash_map<tree, hash_map<tree, tree>>'

Re: 'hash_map<tree, hash_map<tree, tree>>'

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 8427 bytes --]

Hi!

On 2021-08-12T17:15:44-0600, Martin Sebor via Gcc <gcc@gcc.gnu.org> wrote:
> On 8/6/21 10:57 AM, Thomas Schwinge wrote:
>> So I'm trying to do some C++...  ;-)
>>
>> Given:
>>
>>      /* A map from SSA names or var decls to record fields.  */
>>      typedef hash_map<tree, tree> field_map_t;
>>
>>      /* For each propagation record type, this is a map from SSA names or var decls
>>         to propagate, to the field in the record type that should be used for
>>         transmission and reception.  */
>>      typedef hash_map<tree, field_map_t> record_field_map_t;
>>
>> Thus, that's a 'hash_map<tree, hash_map<tree, tree>>'.  (I may do that,
>> right?)  Looking through GCC implementation files, very most of all uses
>> of 'hash_map' boil down to pointer key ('tree', for example) and
>> pointer/integer value.
>
> Right.  Because most GCC containers rely exclusively on GCC's own
> uses for testing, if your use case is novel in some way, chances
> are it might not work as intended in all circumstances.
>
> I've wrestled with hash_map a number of times.  A use case that's
> close to yours (i.e., a non-trivial value type) is in cp/parser.c:
> see class_to_loc_map_t.

Indeed, at the time you sent this email, I already had started looking
into that one!  (The Fortran test cases that I originally analyzed, which
triggered other cases of non-POD/non-trivial destructor, all didn't
result in a memory leak, because the non-trivial constructor doesn't
actually allocate any resources dynamically -- that's indeed different in
this case here.)  ..., and indeed:

> (I don't remember if I tested it for leaks
> though.  It's used to implement -Wmismatched-tags so compiling
> a few tests under Valgrind should show if it does leak.)

... it does leak memory at present.  :-| (See attached commit log for
details for one example.)

To that effect, to document the current behavior, I propose to
"Add more self-tests for 'hash_map' with Value type with non-trivial
constructor/destructor", see attached.  OK to push to master branch?
(Also cherry-pick into release branches, eventually?)

>> Then:
>>
>>      record_field_map_t field_map ([...]); // see below
>>      for ([...])
>>        {
>>          tree record_type = [...];
>>          [...]
>>          bool existed;
>>          field_map_t &fields
>>            = field_map.get_or_insert (record_type, &existed);
>>          gcc_checking_assert (!existed);
>>          [...]
>>          for ([...])
>>            fields.put ([...], [...]);
>>          [...]
>>        }
>>      [stuff that looks up elements from 'field_map']
>>      field_map.empty ();
>>
>> This generally works.
>>
>> If I instantiate 'record_field_map_t field_map (40);', Valgrind is happy.
>> If however I instantiate 'record_field_map_t field_map (13);' (where '13'
>> would be the default for 'hash_map'), Valgrind complains:
>>
>>      2,080 bytes in 10 blocks are definitely lost in loss record 828 of 876
>>         at 0x483DD99: calloc (vg_replace_malloc.c:762)
>>         by 0x175F010: xcalloc (xmalloc.c:162)
>>         by 0xAF4A2C: hash_table<hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_entry, false, xcallocator>::hash_table(unsigned long, bool, bool, bool, mem_alloc_origin) (hash-table.h:275)
>>         by 0x15E0120: hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_map(unsigned long, bool, bool, bool) (hash-map.h:143)
>>         by 0x15DEE87: hash_map<tree_node*, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >, simple_hashmap_traits<default_hash_traits<tree_node*>, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> > > >::get_or_insert(tree_node* const&, bool*) (hash-map.h:205)
>>         by 0x15DD52C: execute_omp_oacc_neuter_broadcast() (omp-oacc-neuter-broadcast.cc:1371)
>>         [...]
>>
>> (That's with '#pragma GCC optimize "O0"' at the top of the 'gcc/*.cc'
>> file.)
>>
>> My suspicion was that it is due to the 'field_map' getting resized as it
>> incrementally grows (and '40' being big enough for that to never happen),
>> and somehow the non-POD (?) value objects not being properly handled
>> during that.  Working my way a bit through 'gcc/hash-map.*' and
>> 'gcc/hash-table.*' (but not claiming that I understand all that, off
>> hand), it seems as if my theory is right: I'm able to plug this memory
>> leak as follows:
>>
>>      --- gcc/hash-table.h
>>      +++ gcc/hash-table.h
>>      @@ -820,6 +820,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>>               {
>>                 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>>            new ((void*) q) value_type (std::move (x));
>>      +     //BAD Descriptor::remove (x); // (doesn't make sense and) a ton of "Invalid read [...] inside a block of size [...] free'd"
>>      +     x.~value_type (); //GOOD This seems to work!  -- but does it make sense?
>>               }
>>
>>             p++;
>>
>> However, that doesn't exactly look like a correct fix, does it?  I'd
>> expect such a manual destructor call in combination with placement new
>> (that is being used here, obviously) -- but this is after 'std::move'?
>> However, this also survives a smoke-test-like run of parts of the GCC
>> testsuite, bootstrap and complete run now ongoing.
>
> If explicitly calling the dtor on the moved object is the right thing
> to do I'd expect to see such invocations elsewhere in hash_table but
> I don't.  It does seem like removed elements ought to be destroyed,
> but it also seems like the destruction should go through some traits
> class (e.g., call Descriptor::remove and mark_deleted or do some
> similar dance), and be called from other member functions that move
> elements.

So, we shall assume that any "real C++" use case (that is, C++ class) is
using the appropriate C++ method, that is, 'typed_delete_remove', which
does 'delete', which does destroy the C++ object, if applicable, else
'typed_noop_remove'.

(Shall we look into the few places that use 'typed_free_remove' via
'free_ptr_hash', and potentially replace them with 'typed_delete_remove'?
Or is there a reason for the two schemes to co-exist, other than for
legacy reasons?  Anyway, that's for another day.)

What is different in the 'hash_table::expand' case is that all the Value
objects do get 'std::move'd into a new blob of memory via placement new
(so a subsequent 'delete' via 'typed_delete_remove' is not appropriate),
but then the stale Value objects never get destructed.  And indeed an
explicit destructor call (which, as I understand is a no-op for primitive
types; "pseudo destructor") is the right thing to do; see
<https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
and others, for example.  (Therefore, I don't think this needs to be
routed through a "traits" function, but can rather be done in-line here,
after each placement new, before deallocation of the original blob of
memory.  Also, I argue it's the right thing to do also for 'm_ggc',
because even if in that case we're not going to leak memory (GC will
reclaim), but we still may leak other resources dynamically allocated in
a non-trivial constructor.)

The attached "Fix 'hash_table::expand' to destruct stale Value objects"
does prevent my original problem, does address the current 'class2loc'
memory leak in 'cp/parser.c' (see commit log for one example), and
adjusts the new
'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' test
case such that number of constructor calls matches the number of
destructor calls.  After some careful review regarding C++ details
(please!), OK to push to master branch?  (Also cherry-pick into release
branches, eventually?)  Is the source code comment that I'm adding
sufficiently explanatory and correct in C++ terms?


Grüße
 Thomas


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-more-self-tests-for-hash_map-with-Value-type-wit.patch --]
[-- Type: text/x-diff, Size: 4953 bytes --]

From 12fda2ece45ea477cdc9a697b5efc6e51c9da229 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 17:53:12 +0200
Subject: [PATCH] Add more self-tests for 'hash_map' with Value type with
 non-trivial constructor/destructor

... to document the current behavior.

	gcc/
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor): Extend.
	(test_map_of_type_with_ctor_and_dtor_expand): Add function.
	(hash_map_tests_c_tests): Call it.
---
 gcc/hash-map-tests.c | 142 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 142 insertions(+)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 5b6b192cd28..3c79a13c1a8 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -278,6 +278,146 @@ test_map_of_type_with_ctor_and_dtor ()
 
     ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
   }
+
+
+  /* Verify basic construction and destruction of Value objects.  */
+  {
+    const int N_elem = 1234;
+    void *a[N_elem];
+    for (int i = 0; i < N_elem; ++i)
+      a[i] = &a[i];
+
+    const int N_init = 44;
+
+    val_t::ndefault = 0;
+    val_t::ncopy = 0;
+    val_t::nassign = 0;
+    val_t::ndtor = 0;
+    Map m (N_init);
+    ASSERT_EQ (val_t::ndefault
+	       + val_t::ncopy
+	       + val_t::nassign
+	       + val_t::ndtor, 0);
+
+    for (int i = 0; i < N_elem; ++i)
+      {
+	m.get_or_insert (a[i]);
+	ASSERT_EQ (val_t::ndefault, 1 + i);
+	ASSERT_EQ (val_t::ncopy, 0);
+	ASSERT_EQ (val_t::nassign, 0);
+	ASSERT_EQ (val_t::ndtor, i);
+
+	m.remove (a[i]);
+	ASSERT_EQ (val_t::ndefault, 1 + i);
+	ASSERT_EQ (val_t::ncopy, 0);
+	ASSERT_EQ (val_t::nassign, 0);
+	ASSERT_EQ (val_t::ndtor, 1 + i);
+      }
+  }
+}
+
+/* Verify 'hash_table::expand'.  */
+
+static void
+test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
+{
+  typedef hash_map <void *, val_t> Map;
+
+  /* Note that we are starting with a fresh 'Map'.  Even if an existing one has
+     been cleared out completely, there remain 'deleted' elements, and these
+     would disturb the following logic, where we don't have access to the
+     actual 'm_n_deleted' value.  */
+  size_t m_n_deleted = 0;
+
+  const int N_elem = 1234;
+  void *a[N_elem];
+  for (int i = 0; i < N_elem; ++i)
+    a[i] = &a[i];
+
+  const int N_init = 4;
+
+  val_t::ndefault = 0;
+  val_t::ncopy = 0;
+  val_t::nassign = 0;
+  val_t::ndtor = 0;
+  Map m (N_init);
+
+  /* In the following, in particular related to 'expand', we're adapting from
+     the internal logic of 'hash_table', glossing over "some details" not
+     relevant for this testing here.  */
+
+  size_t m_size;
+  {
+    unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init);
+    m_size = prime_tab[size_prime_index_].prime;
+  }
+  int n_expand_moved = 0;
+
+  for (int i = 0; i < N_elem; ++i)
+    {
+      int elts = m.elements ();
+
+      /* Per 'hash_table::find_slot_with_hash'.  */
+      size_t m_n_elements = elts + m_n_deleted;
+      bool expand = m_size * 3 <= m_n_elements * 4;
+      m.get_or_insert (a[i]);
+      if (expand)
+	{
+	  /* Per 'hash_table::expand'.  */
+	  {
+	    unsigned int nindex = hash_table_higher_prime_index (elts * 2);
+	    m_size = prime_tab[nindex].prime;
+	  }
+	  m_n_deleted = 0;
+
+	  /* All non-deleted elements have been moved.  */
+	  n_expand_moved += i;
+	  if (remove_some_inline)
+	    n_expand_moved -= (i + 2) / 3;
+	}
+
+      ASSERT_EQ (val_t::ndefault, 1 + i);
+      ASSERT_EQ (val_t::ncopy, n_expand_moved);
+      ASSERT_EQ (val_t::nassign, 0);
+      if (remove_some_inline)
+	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+      else
+	ASSERT_EQ (val_t::ndtor, 0);
+
+      /* Remove some inline.  This never triggers an 'expand', but does
+	 influence any following via 'm_n_deleted'.  */
+      if (remove_some_inline
+	  && !(i % 3))
+	{
+	  m.remove (a[i]);
+	  /* Per 'hash_table::remove_elt_with_hash'.  */
+	  m_n_deleted++;
+
+	  ASSERT_EQ (val_t::ndefault, 1 + i);
+	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
+	  ASSERT_EQ (val_t::nassign, 0);
+	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	}
+    }
+
+  int ndefault = val_t::ndefault;
+  int ncopy = val_t::ncopy;
+  int nassign = val_t::nassign;
+  int ndtor = val_t::ndtor;
+
+  for (int i = 0; i < N_elem; ++i)
+    {
+      if (remove_some_inline
+	  && !(i % 3))
+	continue;
+
+      m.remove (a[i]);
+      ++ndtor;
+      ASSERT_EQ (val_t::ndefault, ndefault);
+      ASSERT_EQ (val_t::ncopy, ncopy);
+      ASSERT_EQ (val_t::nassign, nassign);
+      ASSERT_EQ (val_t::ndtor, ndtor);
+    }
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
@@ -309,6 +449,8 @@ hash_map_tests_c_tests ()
   test_map_of_strings_to_int ();
   test_map_of_int_to_strings ();
   test_map_of_type_with_ctor_and_dtor ();
+  test_map_of_type_with_ctor_and_dtor_expand (false);
+  test_map_of_type_with_ctor_and_dtor_expand (true);
   test_nonzero_empty_key ();
 }
 
-- 
2.30.2


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-Fix-hash_table-expand-to-destruct-stale-Value-object.patch --]
[-- Type: text/x-diff, Size: 17110 bytes --]

From 404d5b985c24d2a15d1908229456e6a8663b1ff3 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 18:03:38 +0200
Subject: [PATCH] Fix 'hash_table::expand' to destruct stale Value objects

Thus plugging potentional memory leaks if these have non-trivial
constructor/destructor.

See
<https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
and others.

As one example, compilation of 'g++.dg/warn/Wmismatched-tags.C' per
'valgrind --leak-check=full' improves as follows:

     [...]
    -
    -104 bytes in 1 blocks are definitely lost in loss record 399 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA43C71: cp_parser_parameter_declaration(cp_parser*, int, bool, bool*) (parser.c:24242)
    -
    -168 bytes in 3 blocks are definitely lost in loss record 422 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA53385: cp_parser_single_declaration(cp_parser*, vec<deferred_access_check, va_gc, vl_embed>*, bool, bool, bool*) (parser.c:31072)
    -
    -488 bytes in 7 blocks are definitely lost in loss record 449 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA49508: cp_parser_member_declaration(cp_parser*) (parser.c:26440)
    -
    -728 bytes in 7 blocks are definitely lost in loss record 455 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA57508: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32980)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -   by 0xA47D76: cp_parser_class_specifier(cp_parser*) (parser.c:25680)
    -   by 0xA37E27: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18912)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -
    -832 bytes in 8 blocks are definitely lost in loss record 458 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -
    -1,144 bytes in 11 blocks are definitely lost in loss record 466 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -
    -1,376 bytes in 10 blocks are definitely lost in loss record 467 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA301E0: cp_parser_simple_declaration(cp_parser*, bool, tree_node**) (parser.c:14772)
    -
    -3,552 bytes in 33 blocks are definitely lost in loss record 483 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA8964A: class_decl_loc_t::class_decl_loc_t(class_decl_loc_t const&) (parser.c:32689)
    -   by 0xA8F515: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::expand() (hash-table.h:839)
    -   by 0xA8D4B3: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::find_slot_with_hash(tree_node* const&, unsigned int, insert_option) (hash-table.h:1008)
    -   by 0xA8B1DC: hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::get_or_insert(tree_node* const&, bool*) (hash-map.h:200)
    -   by 0xA57128: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32888)
     [...]
     LEAK SUMMARY:
    -   definitely lost: 8,440 bytes in 81 blocks
    +   definitely lost: 48 bytes in 1 blocks
        indirectly lost: 12,529 bytes in 329 blocks
          possibly lost: 0 bytes in 0 blocks
        still reachable: 1,644,376 bytes in 768 blocks

	gcc/
	* hash-table.h (hash_table<Descriptor, Lazy, Allocator>::expand):
	Destruct stale Value objects.
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor_expand):
	Update.
---
 gcc/hash-map-tests.c | 9 +++++----
 gcc/hash-table.h     | 4 ++++
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 3c79a13c1a8..d49eafa0bb9 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -304,31 +304,31 @@ test_map_of_type_with_ctor_and_dtor ()
 	m.get_or_insert (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, i);
 
 	m.remove (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, 1 + i);
       }
   }
 }
 
-/* Verify 'hash_table::expand'.  */
+/* Verify that 'hash_table::expand' doesn't leak Value objects.  */
 
 static void
 test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 {
   typedef hash_map <void *, val_t> Map;
 
   /* Note that we are starting with a fresh 'Map'.  Even if an existing one has
      been cleared out completely, there remain 'deleted' elements, and these
      would disturb the following logic, where we don't have access to the
      actual 'm_n_deleted' value.  */
   size_t m_n_deleted = 0;
 
   const int N_elem = 1234;
   void *a[N_elem];
   for (int i = 0; i < N_elem; ++i)
@@ -368,68 +368,69 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 	    unsigned int nindex = hash_table_higher_prime_index (elts * 2);
 	    m_size = prime_tab[nindex].prime;
 	  }
 	  m_n_deleted = 0;
 
 	  /* All non-deleted elements have been moved.  */
 	  n_expand_moved += i;
 	  if (remove_some_inline)
 	    n_expand_moved -= (i + 2) / 3;
 	}
 
       ASSERT_EQ (val_t::ndefault, 1 + i);
       ASSERT_EQ (val_t::ncopy, n_expand_moved);
       ASSERT_EQ (val_t::nassign, 0);
       if (remove_some_inline)
-	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
       else
-	ASSERT_EQ (val_t::ndtor, 0);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved);
 
       /* Remove some inline.  This never triggers an 'expand', but does
 	 influence any following via 'm_n_deleted'.  */
       if (remove_some_inline
 	  && !(i % 3))
 	{
 	  m.remove (a[i]);
 	  /* Per 'hash_table::remove_elt_with_hash'.  */
 	  m_n_deleted++;
 
 	  ASSERT_EQ (val_t::ndefault, 1 + i);
 	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
 	  ASSERT_EQ (val_t::nassign, 0);
-	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	  ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
 	}
     }
 
   int ndefault = val_t::ndefault;
   int ncopy = val_t::ncopy;
   int nassign = val_t::nassign;
   int ndtor = val_t::ndtor;
 
   for (int i = 0; i < N_elem; ++i)
     {
       if (remove_some_inline
 	  && !(i % 3))
 	continue;
 
       m.remove (a[i]);
       ++ndtor;
       ASSERT_EQ (val_t::ndefault, ndefault);
       ASSERT_EQ (val_t::ncopy, ncopy);
       ASSERT_EQ (val_t::nassign, nassign);
       ASSERT_EQ (val_t::ndtor, ndtor);
     }
+  ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
    "empty" value.  */
 
 static void
 test_nonzero_empty_key ()
 {
   typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
   hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
 
   for (int i = 1; i != 32; ++i)
     x.put (i, i);
 
   ASSERT_EQ (x.get (0), NULL);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index a6e0ac8eea9..8c2a0589fbd 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -808,30 +808,34 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
   m_entries = nentries;
   m_size = nsize;
   m_size_prime_index = nindex;
   m_n_elements -= m_n_deleted;
   m_n_deleted = 0;
 
   value_type *p = oentries;
   do
     {
       value_type &x = *p;
 
       if (!is_empty (x) && !is_deleted (x))
         {
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 	  new ((void*) q) value_type (std::move (x));
+
+	  /* Manually invoke destructor of original object, to counterbalance
+	     object constructed via placement new.  */
+	  x.~value_type ();
         }
 
       p++;
     }
   while (p < olimit);
 
   if (!m_ggc)
     Allocator <value_type> ::data_free (oentries);
   else
     ggc_free (oentries);
 }
 
 /* Implements empty() in cases where it isn't a no-op.  */
 
 template<typename Descriptor, bool Lazy,
-- 
2.30.2

Re: 'hash_map<tree, hash_map<tree, tree>>'

[Martin Sebor]

On 8/16/21 6:44 AM, Thomas Schwinge wrote:
> Hi!
> 
> On 2021-08-12T17:15:44-0600, Martin Sebor via Gcc <gcc@gcc.gnu.org> wrote:
>> On 8/6/21 10:57 AM, Thomas Schwinge wrote:
>>> So I'm trying to do some C++...  ;-)
>>>
>>> Given:
>>>
>>>       /* A map from SSA names or var decls to record fields.  */
>>>       typedef hash_map<tree, tree> field_map_t;
>>>
>>>       /* For each propagation record type, this is a map from SSA names or var decls
>>>          to propagate, to the field in the record type that should be used for
>>>          transmission and reception.  */
>>>       typedef hash_map<tree, field_map_t> record_field_map_t;
>>>
>>> Thus, that's a 'hash_map<tree, hash_map<tree, tree>>'.  (I may do that,
>>> right?)  Looking through GCC implementation files, very most of all uses
>>> of 'hash_map' boil down to pointer key ('tree', for example) and
>>> pointer/integer value.
>>
>> Right.  Because most GCC containers rely exclusively on GCC's own
>> uses for testing, if your use case is novel in some way, chances
>> are it might not work as intended in all circumstances.
>>
>> I've wrestled with hash_map a number of times.  A use case that's
>> close to yours (i.e., a non-trivial value type) is in cp/parser.c:
>> see class_to_loc_map_t.
> 
> Indeed, at the time you sent this email, I already had started looking
> into that one!  (The Fortran test cases that I originally analyzed, which
> triggered other cases of non-POD/non-trivial destructor, all didn't
> result in a memory leak, because the non-trivial constructor doesn't
> actually allocate any resources dynamically -- that's indeed different in
> this case here.)  ..., and indeed:
> 
>> (I don't remember if I tested it for leaks
>> though.  It's used to implement -Wmismatched-tags so compiling
>> a few tests under Valgrind should show if it does leak.)
> 
> ... it does leak memory at present.  :-| (See attached commit log for
> details for one example.)
> 
> To that effect, to document the current behavior, I propose to
> "Add more self-tests for 'hash_map' with Value type with non-trivial
> constructor/destructor", see attached.  OK to push to master branch?
> (Also cherry-pick into release branches, eventually?)

Adding more tests sounds like an excellent idea.  I'm not sure about
the idea of adding loopy selftests that iterate as many times as in
the patch (looks like 1234 times two?)  Selftests run each time GCC
builds (i.e., even during day to day development).  It seems to me
that it might be better to run such selftests only as part of
the bootstrap process.

> 
>>> Then:
>>>
>>>       record_field_map_t field_map ([...]); // see below
>>>       for ([...])
>>>         {
>>>           tree record_type = [...];
>>>           [...]
>>>           bool existed;
>>>           field_map_t &fields
>>>             = field_map.get_or_insert (record_type, &existed);
>>>           gcc_checking_assert (!existed);
>>>           [...]
>>>           for ([...])
>>>             fields.put ([...], [...]);
>>>           [...]
>>>         }
>>>       [stuff that looks up elements from 'field_map']
>>>       field_map.empty ();
>>>
>>> This generally works.
>>>
>>> If I instantiate 'record_field_map_t field_map (40);', Valgrind is happy.
>>> If however I instantiate 'record_field_map_t field_map (13);' (where '13'
>>> would be the default for 'hash_map'), Valgrind complains:
>>>
>>>       2,080 bytes in 10 blocks are definitely lost in loss record 828 of 876
>>>          at 0x483DD99: calloc (vg_replace_malloc.c:762)
>>>          by 0x175F010: xcalloc (xmalloc.c:162)
>>>          by 0xAF4A2C: hash_table<hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_entry, false, xcallocator>::hash_table(unsigned long, bool, bool, bool, mem_alloc_origin) (hash-table.h:275)
>>>          by 0x15E0120: hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_map(unsigned long, bool, bool, bool) (hash-map.h:143)
>>>          by 0x15DEE87: hash_map<tree_node*, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >, simple_hashmap_traits<default_hash_traits<tree_node*>, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> > > >::get_or_insert(tree_node* const&, bool*) (hash-map.h:205)
>>>          by 0x15DD52C: execute_omp_oacc_neuter_broadcast() (omp-oacc-neuter-broadcast.cc:1371)
>>>          [...]
>>>
>>> (That's with '#pragma GCC optimize "O0"' at the top of the 'gcc/*.cc'
>>> file.)
>>>
>>> My suspicion was that it is due to the 'field_map' getting resized as it
>>> incrementally grows (and '40' being big enough for that to never happen),
>>> and somehow the non-POD (?) value objects not being properly handled
>>> during that.  Working my way a bit through 'gcc/hash-map.*' and
>>> 'gcc/hash-table.*' (but not claiming that I understand all that, off
>>> hand), it seems as if my theory is right: I'm able to plug this memory
>>> leak as follows:
>>>
>>>       --- gcc/hash-table.h
>>>       +++ gcc/hash-table.h
>>>       @@ -820,6 +820,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>>>                {
>>>                  value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>>>             new ((void*) q) value_type (std::move (x));
>>>       +     //BAD Descriptor::remove (x); // (doesn't make sense and) a ton of "Invalid read [...] inside a block of size [...] free'd"
>>>       +     x.~value_type (); //GOOD This seems to work!  -- but does it make sense?
>>>                }
>>>
>>>              p++;
>>>
>>> However, that doesn't exactly look like a correct fix, does it?  I'd
>>> expect such a manual destructor call in combination with placement new
>>> (that is being used here, obviously) -- but this is after 'std::move'?
>>> However, this also survives a smoke-test-like run of parts of the GCC
>>> testsuite, bootstrap and complete run now ongoing.
>>
>> If explicitly calling the dtor on the moved object is the right thing
>> to do I'd expect to see such invocations elsewhere in hash_table but
>> I don't.  It does seem like removed elements ought to be destroyed,
>> but it also seems like the destruction should go through some traits
>> class (e.g., call Descriptor::remove and mark_deleted or do some
>> similar dance), and be called from other member functions that move
>> elements.
> 
> So, we shall assume that any "real C++" use case (that is, C++ class) is
> using the appropriate C++ method, that is, 'typed_delete_remove', which
> does 'delete', which does destroy the C++ object, if applicable, else
> 'typed_noop_remove'.
> 
> (Shall we look into the few places that use 'typed_free_remove' via
> 'free_ptr_hash', and potentially replace them with 'typed_delete_remove'?
> Or is there a reason for the two schemes to co-exist, other than for
> legacy reasons?  Anyway, that's for another day.)

I find all these these traits pretty much impenetrable.  I guess
intuitively, I'd expect Descriptor::remove() to destroy an element,
but I have no idea if that would be right given the design.

> 
> What is different in the 'hash_table::expand' case is that all the Value
> objects do get 'std::move'd into a new blob of memory via placement new
> (so a subsequent 'delete' via 'typed_delete_remove' is not appropriate),
> but then the stale Value objects never get destructed.  And indeed an
> explicit destructor call (which, as I understand is a no-op for primitive
> types; "pseudo destructor") is the right thing to do; see
> <https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
> and others, for example.  (Therefore, I don't think this needs to be
> routed through a "traits" function, but can rather be done in-line here,
> after each placement new, before deallocation of the original blob of
> memory.  Also, I argue it's the right thing to do also for 'm_ggc',
> because even if in that case we're not going to leak memory (GC will
> reclaim), but we still may leak other resources dynamically allocated in
> a non-trivial constructor.)

Yes, of course, all elements need to be eventually be destroyed.
My only hesitation was whether it should be done via one of these
traits classes (like it's done in C++ containers via allocators)
rather than directly, and whether there might be other places
where the destruction night need to happen.

> 
> The attached "Fix 'hash_table::expand' to destruct stale Value objects"
> does prevent my original problem, does address the current 'class2loc'
> memory leak in 'cp/parser.c' (see commit log for one example), and
> adjusts the new
> 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' test
> case such that number of constructor calls matches the number of
> destructor calls.  After some careful review regarding C++ details
> (please!), OK to push to master branch?  (Also cherry-pick into release
> branches, eventually?)  Is the source code comment that I'm adding
> sufficiently explanatory and correct in C++ terms?

Shouldn't the hash_table dtor (and perhaps also empty())  also
destroy the elements?  (Otherwise, what destroys the elements
newly constructed here, or anywhere else for that matter, such
as in the hash_table ctor?)

Also, shouldn't the destroyed slot be marked either deleted or
empty?)

(Sorry, I realize I have more questions than answers.)

Martin

> 
> 
> Grüße
>   Thomas
> 
> 
> -----------------
> Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955
> 

Expensive selftests (was: 'hash_map<tree, hash_map<tree, tree>>')

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 2542 bytes --]

Hi!

On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
> On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>> [...], to document the current behavior, I propose to
>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>> constructor/destructor", see attached.  OK to push to master branch?
>> (Also cherry-pick into release branches, eventually?)

(Attached again, for easy reference.)

> Adding more tests sounds like an excellent idea.  I'm not sure about
> the idea of adding loopy selftests that iterate as many times as in
> the patch (looks like 1234 times two?)

Correct, and I agree it's a sensible concern, generally.

The current 1234 times two iterations is really arbitrary (should
document that in the test case), just so that we trigger a few hash table
expansions.

For 'selftest-c', we've got originally:

    -fself-test: 74775 pass(es) in 0.309299 seconds
    -fself-test: 74775 pass(es) in 0.366041 seconds
    -fself-test: 74775 pass(es) in 0.356663 seconds
    -fself-test: 74775 pass(es) in 0.355009 seconds
    -fself-test: 74775 pass(es) in 0.367575 seconds
    -fself-test: 74775 pass(es) in 0.320406 seconds

..., and with my changes we've got:

    -fself-test: 94519 pass(es) in 0.327755 seconds
    -fself-test: 94519 pass(es) in 0.369522 seconds
    -fself-test: 94519 pass(es) in 0.355531 seconds
    -fself-test: 94519 pass(es) in 0.362179 seconds
    -fself-test: 94519 pass(es) in 0.363176 seconds
    -fself-test: 94519 pass(es) in 0.318930 seconds

So it really seems to be all in the noise?

Yet:

> Selftests run each time GCC
> builds (i.e., even during day to day development).  It seems to me
> that it might be better to run such selftests only as part of
> the bootstrap process.

I'd rather have thought about a '--param self-test-expensive' (or
similar), and then invoke the selftests via a new
'gcc/testsuite/selftests/expensive.exp' (or similar).

Or, adapt 'gcc/testsuite/gcc.dg/plugin/expensive_selftests_plugin.c',
that is, invoke them via the GCC plugin mechanism, which also seems to be
easy enough?

I don't have a strong opinion about where/when these tests get run, so
will happily take any suggestions.


Grüße
 Thomas


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-more-self-tests-for-hash_map-with-Value-type-wit.patch --]
[-- Type: text/x-diff, Size: 4953 bytes --]

From 12fda2ece45ea477cdc9a697b5efc6e51c9da229 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 17:53:12 +0200
Subject: [PATCH] Add more self-tests for 'hash_map' with Value type with
 non-trivial constructor/destructor

... to document the current behavior.

	gcc/
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor): Extend.
	(test_map_of_type_with_ctor_and_dtor_expand): Add function.
	(hash_map_tests_c_tests): Call it.
---
 gcc/hash-map-tests.c | 142 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 142 insertions(+)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 5b6b192cd28..3c79a13c1a8 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -278,6 +278,146 @@ test_map_of_type_with_ctor_and_dtor ()
 
     ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
   }
+
+
+  /* Verify basic construction and destruction of Value objects.  */
+  {
+    const int N_elem = 1234;
+    void *a[N_elem];
+    for (int i = 0; i < N_elem; ++i)
+      a[i] = &a[i];
+
+    const int N_init = 44;
+
+    val_t::ndefault = 0;
+    val_t::ncopy = 0;
+    val_t::nassign = 0;
+    val_t::ndtor = 0;
+    Map m (N_init);
+    ASSERT_EQ (val_t::ndefault
+	       + val_t::ncopy
+	       + val_t::nassign
+	       + val_t::ndtor, 0);
+
+    for (int i = 0; i < N_elem; ++i)
+      {
+	m.get_or_insert (a[i]);
+	ASSERT_EQ (val_t::ndefault, 1 + i);
+	ASSERT_EQ (val_t::ncopy, 0);
+	ASSERT_EQ (val_t::nassign, 0);
+	ASSERT_EQ (val_t::ndtor, i);
+
+	m.remove (a[i]);
+	ASSERT_EQ (val_t::ndefault, 1 + i);
+	ASSERT_EQ (val_t::ncopy, 0);
+	ASSERT_EQ (val_t::nassign, 0);
+	ASSERT_EQ (val_t::ndtor, 1 + i);
+      }
+  }
+}
+
+/* Verify 'hash_table::expand'.  */
+
+static void
+test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
+{
+  typedef hash_map <void *, val_t> Map;
+
+  /* Note that we are starting with a fresh 'Map'.  Even if an existing one has
+     been cleared out completely, there remain 'deleted' elements, and these
+     would disturb the following logic, where we don't have access to the
+     actual 'm_n_deleted' value.  */
+  size_t m_n_deleted = 0;
+
+  const int N_elem = 1234;
+  void *a[N_elem];
+  for (int i = 0; i < N_elem; ++i)
+    a[i] = &a[i];
+
+  const int N_init = 4;
+
+  val_t::ndefault = 0;
+  val_t::ncopy = 0;
+  val_t::nassign = 0;
+  val_t::ndtor = 0;
+  Map m (N_init);
+
+  /* In the following, in particular related to 'expand', we're adapting from
+     the internal logic of 'hash_table', glossing over "some details" not
+     relevant for this testing here.  */
+
+  size_t m_size;
+  {
+    unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init);
+    m_size = prime_tab[size_prime_index_].prime;
+  }
+  int n_expand_moved = 0;
+
+  for (int i = 0; i < N_elem; ++i)
+    {
+      int elts = m.elements ();
+
+      /* Per 'hash_table::find_slot_with_hash'.  */
+      size_t m_n_elements = elts + m_n_deleted;
+      bool expand = m_size * 3 <= m_n_elements * 4;
+      m.get_or_insert (a[i]);
+      if (expand)
+	{
+	  /* Per 'hash_table::expand'.  */
+	  {
+	    unsigned int nindex = hash_table_higher_prime_index (elts * 2);
+	    m_size = prime_tab[nindex].prime;
+	  }
+	  m_n_deleted = 0;
+
+	  /* All non-deleted elements have been moved.  */
+	  n_expand_moved += i;
+	  if (remove_some_inline)
+	    n_expand_moved -= (i + 2) / 3;
+	}
+
+      ASSERT_EQ (val_t::ndefault, 1 + i);
+      ASSERT_EQ (val_t::ncopy, n_expand_moved);
+      ASSERT_EQ (val_t::nassign, 0);
+      if (remove_some_inline)
+	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+      else
+	ASSERT_EQ (val_t::ndtor, 0);
+
+      /* Remove some inline.  This never triggers an 'expand', but does
+	 influence any following via 'm_n_deleted'.  */
+      if (remove_some_inline
+	  && !(i % 3))
+	{
+	  m.remove (a[i]);
+	  /* Per 'hash_table::remove_elt_with_hash'.  */
+	  m_n_deleted++;
+
+	  ASSERT_EQ (val_t::ndefault, 1 + i);
+	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
+	  ASSERT_EQ (val_t::nassign, 0);
+	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	}
+    }
+
+  int ndefault = val_t::ndefault;
+  int ncopy = val_t::ncopy;
+  int nassign = val_t::nassign;
+  int ndtor = val_t::ndtor;
+
+  for (int i = 0; i < N_elem; ++i)
+    {
+      if (remove_some_inline
+	  && !(i % 3))
+	continue;
+
+      m.remove (a[i]);
+      ++ndtor;
+      ASSERT_EQ (val_t::ndefault, ndefault);
+      ASSERT_EQ (val_t::ncopy, ncopy);
+      ASSERT_EQ (val_t::nassign, nassign);
+      ASSERT_EQ (val_t::ndtor, ndtor);
+    }
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
@@ -309,6 +449,8 @@ hash_map_tests_c_tests ()
   test_map_of_strings_to_int ();
   test_map_of_int_to_strings ();
   test_map_of_type_with_ctor_and_dtor ();
+  test_map_of_type_with_ctor_and_dtor_expand (false);
+  test_map_of_type_with_ctor_and_dtor_expand (true);
   test_nonzero_empty_key ();
 }
 
-- 
2.30.2

Re: Expensive selftests (was: 'hash_map<tree, hash_map<tree, tree>>')

[Richard Biener]

On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge <thomas@codesourcery.com> wrote:
>
> Hi!
>
> On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
> > On 8/16/21 6:44 AM, Thomas Schwinge wrote:
> >> [...], to document the current behavior, I propose to
> >> "Add more self-tests for 'hash_map' with Value type with non-trivial
> >> constructor/destructor", see attached.  OK to push to master branch?
> >> (Also cherry-pick into release branches, eventually?)
>
> (Attached again, for easy reference.)
>
> > Adding more tests sounds like an excellent idea.  I'm not sure about
> > the idea of adding loopy selftests that iterate as many times as in
> > the patch (looks like 1234 times two?)
>
> Correct, and I agree it's a sensible concern, generally.
>
> The current 1234 times two iterations is really arbitrary (should
> document that in the test case), just so that we trigger a few hash table
> expansions.

You could lower N_init (the default init is just 13!),
even with just 128 inserted elements you'll trigger
expansions to 31, 61 and 127 elements.

> For 'selftest-c', we've got originally:
>
>     -fself-test: 74775 pass(es) in 0.309299 seconds
>     -fself-test: 74775 pass(es) in 0.366041 seconds
>     -fself-test: 74775 pass(es) in 0.356663 seconds
>     -fself-test: 74775 pass(es) in 0.355009 seconds
>     -fself-test: 74775 pass(es) in 0.367575 seconds
>     -fself-test: 74775 pass(es) in 0.320406 seconds
>
> ..., and with my changes we've got:
>
>     -fself-test: 94519 pass(es) in 0.327755 seconds
>     -fself-test: 94519 pass(es) in 0.369522 seconds
>     -fself-test: 94519 pass(es) in 0.355531 seconds
>     -fself-test: 94519 pass(es) in 0.362179 seconds
>     -fself-test: 94519 pass(es) in 0.363176 seconds
>     -fself-test: 94519 pass(es) in 0.318930 seconds
>
> So it really seems to be all in the noise?

Yes.  I think the test is OK but it's also reasonable to lower
the '1234' times and add a comment as to the count should
trigger hashtable expansions "a few times".

Richard.

> Yet:
>
> > Selftests run each time GCC
> > builds (i.e., even during day to day development).  It seems to me
> > that it might be better to run such selftests only as part of
> > the bootstrap process.
>
> I'd rather have thought about a '--param self-test-expensive' (or
> similar), and then invoke the selftests via a new
> 'gcc/testsuite/selftests/expensive.exp' (or similar).
>
> Or, adapt 'gcc/testsuite/gcc.dg/plugin/expensive_selftests_plugin.c',
> that is, invoke them via the GCC plugin mechanism, which also seems to be
> easy enough?
>
> I don't have a strong opinion about where/when these tests get run, so
> will happily take any suggestions.
>
>
> Grüße
>  Thomas
>
>
> -----------------
> Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

Add more self-tests for 'hash_map' with Value type with non-trivial constructor/destructor (was: Expensive selftests)

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 2601 bytes --]

Hi!

On 2021-08-17T10:57:36+0200, Richard Biener <richard.guenther@gmail.com> wrote:
> On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge <thomas@codesourcery.com> wrote:
>> On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
>> > On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>> >> [...], to document the current behavior, I propose to
>> >> "Add more self-tests for 'hash_map' with Value type with non-trivial
>> >> constructor/destructor", see attached.  OK to push to master branch?
>> >> (Also cherry-pick into release branches, eventually?)

>> > Adding more tests sounds like an excellent idea.  I'm not sure about
>> > the idea of adding loopy selftests that iterate as many times as in
>> > the patch (looks like 1234 times two?)
>>
>> Correct, and I agree it's a sensible concern, generally.
>>
>> The current 1234 times two iterations is really arbitrary (should
>> document that in the test case), just so that we trigger a few hash table
>> expansions.
>
> You could lower N_init (the default init is just 13!),
> even with just 128 inserted elements you'll trigger
> expansions to 31, 61 and 127 elements.

> I think the test is OK but it's also reasonable to lower
> the '1234' times and add a comment as to the count should
> trigger hashtable expansions "a few times".

Did that as follows:

    /* Verify basic construction and destruction of Value objects.  */
    {
      /* Configure, arbitrary.  */
      const size_t N_init = 0;
      const int N_elem = 28;

..., and:

    /* Verify aspects of 'hash_table::expand'.  */

    static void
    test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
    {
      /* Configure, so that hash table expansion triggers a few times.  */
      const size_t N_init = 0;
      const int N_elem = 70;
      size_t expand_c_expected = 4;
    [...]
          if (expand)
        {
          ++expand_c;
    [...]
      ASSERT_EQ (expand_c, expand_c_expected);

Given that it's all deterministic (as far as I can tell...), we may
verify an exact number of hash table expansions.

Pushed "Add more self-tests for 'hash_map' with Value type with
non-trivial constructor/destructor" to master branch in commit
e4f16e9f357a38ec702fb69a0ffab9d292a6af9b, see attached.


Grüße
 Thomas


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-more-self-tests-for-hash_map-with-Value-type-wit.patch --]
[-- Type: text/x-diff, Size: 5252 bytes --]

From e4f16e9f357a38ec702fb69a0ffab9d292a6af9b Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 17:53:12 +0200
Subject: [PATCH] Add more self-tests for 'hash_map' with Value type with
 non-trivial constructor/destructor

... to document the current behavior.

	gcc/
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor): Extend.
	(test_map_of_type_with_ctor_and_dtor_expand): Add function.
	(hash_map_tests_c_tests): Call it.
---
 gcc/hash-map-tests.c | 152 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 152 insertions(+)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 5b6b192cd28..257f2be0c26 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -278,6 +278,156 @@ test_map_of_type_with_ctor_and_dtor ()
 
     ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
   }
+
+
+  /* Verify basic construction and destruction of Value objects.  */
+  {
+    /* Configure, arbitrary.  */
+    const size_t N_init = 0;
+    const int N_elem = 28;
+
+    void *a[N_elem];
+    for (size_t i = 0; i < N_elem; ++i)
+      a[i] = &a[i];
+
+    val_t::ndefault = 0;
+    val_t::ncopy = 0;
+    val_t::nassign = 0;
+    val_t::ndtor = 0;
+    Map m (N_init);
+    ASSERT_EQ (val_t::ndefault
+	       + val_t::ncopy
+	       + val_t::nassign
+	       + val_t::ndtor, 0);
+
+    for (int i = 0; i < N_elem; ++i)
+      {
+	m.get_or_insert (a[i]);
+	ASSERT_EQ (val_t::ndefault, 1 + i);
+	ASSERT_EQ (val_t::ncopy, 0);
+	ASSERT_EQ (val_t::nassign, 0);
+	ASSERT_EQ (val_t::ndtor, i);
+
+	m.remove (a[i]);
+	ASSERT_EQ (val_t::ndefault, 1 + i);
+	ASSERT_EQ (val_t::ncopy, 0);
+	ASSERT_EQ (val_t::nassign, 0);
+	ASSERT_EQ (val_t::ndtor, 1 + i);
+      }
+  }
+}
+
+/* Verify aspects of 'hash_table::expand'.  */
+
+static void
+test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
+{
+  /* Configure, so that hash table expansion triggers a few times.  */
+  const size_t N_init = 0;
+  const int N_elem = 70;
+  size_t expand_c_expected = 4;
+  size_t expand_c = 0;
+
+  void *a[N_elem];
+  for (size_t i = 0; i < N_elem; ++i)
+    a[i] = &a[i];
+
+  typedef hash_map <void *, val_t> Map;
+
+  /* Note that we are starting with a fresh 'Map'.  Even if an existing one has
+     been cleared out completely, there remain 'deleted' elements, and these
+     would disturb the following logic, where we don't have access to the
+     actual 'm_n_deleted' value.  */
+  size_t m_n_deleted = 0;
+
+  val_t::ndefault = 0;
+  val_t::ncopy = 0;
+  val_t::nassign = 0;
+  val_t::ndtor = 0;
+  Map m (N_init);
+
+  /* In the following, in particular related to 'expand', we're adapting from
+     the internal logic of 'hash_table', glossing over "some details" not
+     relevant for this testing here.  */
+
+  /* Per 'hash_table::hash_table'.  */
+  size_t m_size;
+  {
+    unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init);
+    m_size = prime_tab[size_prime_index_].prime;
+  }
+
+  int n_expand_moved = 0;
+
+  for (int i = 0; i < N_elem; ++i)
+    {
+      size_t elts = m.elements ();
+
+      /* Per 'hash_table::find_slot_with_hash'.  */
+      size_t m_n_elements = elts + m_n_deleted;
+      bool expand = m_size * 3 <= m_n_elements * 4;
+
+      m.get_or_insert (a[i]);
+      if (expand)
+	{
+	  ++expand_c;
+
+	  /* Per 'hash_table::expand'.  */
+	  {
+	    unsigned int nindex = hash_table_higher_prime_index (elts * 2);
+	    m_size = prime_tab[nindex].prime;
+	  }
+	  m_n_deleted = 0;
+
+	  /* All non-deleted elements have been moved.  */
+	  n_expand_moved += i;
+	  if (remove_some_inline)
+	    n_expand_moved -= (i + 2) / 3;
+	}
+
+      ASSERT_EQ (val_t::ndefault, 1 + i);
+      ASSERT_EQ (val_t::ncopy, n_expand_moved);
+      ASSERT_EQ (val_t::nassign, 0);
+      if (remove_some_inline)
+	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+      else
+	ASSERT_EQ (val_t::ndtor, 0);
+
+      /* Remove some inline.  This never triggers an 'expand' here, but via
+	 'm_n_deleted' does influence any following one.  */
+      if (remove_some_inline
+	  && !(i % 3))
+	{
+	  m.remove (a[i]);
+	  /* Per 'hash_table::remove_elt_with_hash'.  */
+	  m_n_deleted++;
+
+	  ASSERT_EQ (val_t::ndefault, 1 + i);
+	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
+	  ASSERT_EQ (val_t::nassign, 0);
+	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	}
+    }
+  ASSERT_EQ (expand_c, expand_c_expected);
+
+  int ndefault = val_t::ndefault;
+  int ncopy = val_t::ncopy;
+  int nassign = val_t::nassign;
+  int ndtor = val_t::ndtor;
+
+  for (int i = 0; i < N_elem; ++i)
+    {
+      if (remove_some_inline
+	  && !(i % 3))
+	continue;
+
+      m.remove (a[i]);
+      ++ndtor;
+      ASSERT_EQ (val_t::ndefault, ndefault);
+      ASSERT_EQ (val_t::ncopy, ncopy);
+      ASSERT_EQ (val_t::nassign, nassign);
+      ASSERT_EQ (val_t::ndtor, ndtor);
+    }
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
@@ -309,6 +459,8 @@ hash_map_tests_c_tests ()
   test_map_of_strings_to_int ();
   test_map_of_int_to_strings ();
   test_map_of_type_with_ctor_and_dtor ();
+  test_map_of_type_with_ctor_and_dtor_expand (false);
+  test_map_of_type_with_ctor_and_dtor_expand (true);
   test_nonzero_empty_key ();
 }
 
-- 
2.30.2

Re: Expensive selftests (was: 'hash_map<tree, hash_map<tree, tree>>')

[David Edelsohn]

This causes a bootstrap failure for me.

PR/101959

On Tue, Aug 17, 2021 at 5:00 AM Richard Biener via Gcc <gcc@gcc.gnu.org> wrote:
>
> On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge <thomas@codesourcery.com> wrote:
> >
> > Hi!
> >
> > On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
> > > On 8/16/21 6:44 AM, Thomas Schwinge wrote:
> > >> [...], to document the current behavior, I propose to
> > >> "Add more self-tests for 'hash_map' with Value type with non-trivial
> > >> constructor/destructor", see attached.  OK to push to master branch?
> > >> (Also cherry-pick into release branches, eventually?)
> >
> > (Attached again, for easy reference.)
> >
> > > Adding more tests sounds like an excellent idea.  I'm not sure about
> > > the idea of adding loopy selftests that iterate as many times as in
> > > the patch (looks like 1234 times two?)
> >
> > Correct, and I agree it's a sensible concern, generally.
> >
> > The current 1234 times two iterations is really arbitrary (should
> > document that in the test case), just so that we trigger a few hash table
> > expansions.
>
> You could lower N_init (the default init is just 13!),
> even with just 128 inserted elements you'll trigger
> expansions to 31, 61 and 127 elements.
>
> > For 'selftest-c', we've got originally:
> >
> >     -fself-test: 74775 pass(es) in 0.309299 seconds
> >     -fself-test: 74775 pass(es) in 0.366041 seconds
> >     -fself-test: 74775 pass(es) in 0.356663 seconds
> >     -fself-test: 74775 pass(es) in 0.355009 seconds
> >     -fself-test: 74775 pass(es) in 0.367575 seconds
> >     -fself-test: 74775 pass(es) in 0.320406 seconds
> >
> > ..., and with my changes we've got:
> >
> >     -fself-test: 94519 pass(es) in 0.327755 seconds
> >     -fself-test: 94519 pass(es) in 0.369522 seconds
> >     -fself-test: 94519 pass(es) in 0.355531 seconds
> >     -fself-test: 94519 pass(es) in 0.362179 seconds
> >     -fself-test: 94519 pass(es) in 0.363176 seconds
> >     -fself-test: 94519 pass(es) in 0.318930 seconds
> >
> > So it really seems to be all in the noise?
>
> Yes.  I think the test is OK but it's also reasonable to lower
> the '1234' times and add a comment as to the count should
> trigger hashtable expansions "a few times".
>
> Richard.
>
> > Yet:
> >
> > > Selftests run each time GCC
> > > builds (i.e., even during day to day development).  It seems to me
> > > that it might be better to run such selftests only as part of
> > > the bootstrap process.
> >
> > I'd rather have thought about a '--param self-test-expensive' (or
> > similar), and then invoke the selftests via a new
> > 'gcc/testsuite/selftests/expensive.exp' (or similar).
> >
> > Or, adapt 'gcc/testsuite/gcc.dg/plugin/expensive_selftests_plugin.c',
> > that is, invoke them via the GCC plugin mechanism, which also seems to be
> > easy enough?
> >
> > I don't have a strong opinion about where/when these tests get run, so
> > will happily take any suggestions.
> >
> >
> > Grüße
> >  Thomas
> >
> >
> > -----------------
> > Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' work on 32-bit architectures [PR101959]

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 4069 bytes --]

Hi!

On 2021-08-18T09:35:25-0400, David Edelsohn <dje.gcc@gmail.com> wrote:
> This causes a bootstrap failure for me.
>
> PR/101959

Sorry for that; "details".  ;-|  OK to push the attached
"Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand'
work on 32-bit architectures [PR101959]", which does resolve the issue
for a '-m32' i686-pc-linux-gnu build?


Grüße
 Thomas


> On Tue, Aug 17, 2021 at 5:00 AM Richard Biener via Gcc <gcc@gcc.gnu.org> wrote:
>>
>> On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge <thomas@codesourcery.com> wrote:
>> >
>> > Hi!
>> >
>> > On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
>> > > On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>> > >> [...], to document the current behavior, I propose to
>> > >> "Add more self-tests for 'hash_map' with Value type with non-trivial
>> > >> constructor/destructor", see attached.  OK to push to master branch?
>> > >> (Also cherry-pick into release branches, eventually?)
>> >
>> > (Attached again, for easy reference.)
>> >
>> > > Adding more tests sounds like an excellent idea.  I'm not sure about
>> > > the idea of adding loopy selftests that iterate as many times as in
>> > > the patch (looks like 1234 times two?)
>> >
>> > Correct, and I agree it's a sensible concern, generally.
>> >
>> > The current 1234 times two iterations is really arbitrary (should
>> > document that in the test case), just so that we trigger a few hash table
>> > expansions.
>>
>> You could lower N_init (the default init is just 13!),
>> even with just 128 inserted elements you'll trigger
>> expansions to 31, 61 and 127 elements.
>>
>> > For 'selftest-c', we've got originally:
>> >
>> >     -fself-test: 74775 pass(es) in 0.309299 seconds
>> >     -fself-test: 74775 pass(es) in 0.366041 seconds
>> >     -fself-test: 74775 pass(es) in 0.356663 seconds
>> >     -fself-test: 74775 pass(es) in 0.355009 seconds
>> >     -fself-test: 74775 pass(es) in 0.367575 seconds
>> >     -fself-test: 74775 pass(es) in 0.320406 seconds
>> >
>> > ..., and with my changes we've got:
>> >
>> >     -fself-test: 94519 pass(es) in 0.327755 seconds
>> >     -fself-test: 94519 pass(es) in 0.369522 seconds
>> >     -fself-test: 94519 pass(es) in 0.355531 seconds
>> >     -fself-test: 94519 pass(es) in 0.362179 seconds
>> >     -fself-test: 94519 pass(es) in 0.363176 seconds
>> >     -fself-test: 94519 pass(es) in 0.318930 seconds
>> >
>> > So it really seems to be all in the noise?
>>
>> Yes.  I think the test is OK but it's also reasonable to lower
>> the '1234' times and add a comment as to the count should
>> trigger hashtable expansions "a few times".
>>
>> Richard.
>>
>> > Yet:
>> >
>> > > Selftests run each time GCC
>> > > builds (i.e., even during day to day development).  It seems to me
>> > > that it might be better to run such selftests only as part of
>> > > the bootstrap process.
>> >
>> > I'd rather have thought about a '--param self-test-expensive' (or
>> > similar), and then invoke the selftests via a new
>> > 'gcc/testsuite/selftests/expensive.exp' (or similar).
>> >
>> > Or, adapt 'gcc/testsuite/gcc.dg/plugin/expensive_selftests_plugin.c',
>> > that is, invoke them via the GCC plugin mechanism, which also seems to be
>> > easy enough?
>> >
>> > I don't have a strong opinion about where/when these tests get run, so
>> > will happily take any suggestions.
>> >
>> >
>> > Grüße
>> >  Thomas
>> >
>> >
>> > -----------------
>> > Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Make-gcc-hash-map-tests.c-test_map_of_type_with_ctor.patch --]
[-- Type: text/x-diff, Size: 1954 bytes --]

From a6075945f392a93fa03eaf163cbe34fc5cfe8fe1 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Wed, 18 Aug 2021 17:20:40 +0200
Subject: [PATCH] Make
 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' work on
 32-bit architectures [PR101959]

Bug fix for recent commit e4f16e9f357a38ec702fb69a0ffab9d292a6af9b
"Add more self-tests for 'hash_map' with Value type with non-trivial
constructor/destructor".

	gcc/
	PR bootstrap/101959
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor_expand):
	Use an 'int_hash'.
---
 gcc/hash-map-tests.c | 17 ++++++++++++++---
 1 file changed, 14 insertions(+), 3 deletions(-)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 257f2be0c26..6acc0d4337e 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -328,11 +328,22 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
   size_t expand_c_expected = 4;
   size_t expand_c = 0;
 
-  void *a[N_elem];
+  /* For stability of this testing, we need all Key values 'k' to produce
+     unique hash values 'Traits::hash (k)', as otherwise the dynamic
+     insert/remove behavior may diverge across different architectures.  This
+     is, for example, a problem when using the standard 'pointer_hash::hash',
+     which is simply doing a 'k >> 3' operation, which is fine on 64-bit
+     architectures, but on 32-bit architectures produces the same hash value
+     for subsequent 'a[i] = &a[i]' array elements.  Therefore, use an
+     'int_hash'.  */
+
+  int a[N_elem];
   for (size_t i = 0; i < N_elem; ++i)
-    a[i] = &a[i];
+    a[i] = i;
 
-  typedef hash_map <void *, val_t> Map;
+  const int EMPTY = -1;
+  const int DELETED = -2;
+  typedef hash_map<int_hash<int, EMPTY, DELETED>, val_t> Map;
 
   /* Note that we are starting with a fresh 'Map'.  Even if an existing one has
      been cleared out completely, there remain 'deleted' elements, and these
-- 
2.30.2

Re: Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' work on 32-bit architectures [PR101959]

[Richard Biener]

On August 18, 2021 5:34:28 PM GMT+02:00, Thomas Schwinge <thomas@codesourcery.com> wrote:
>Hi!
>
>On 2021-08-18T09:35:25-0400, David Edelsohn <dje.gcc@gmail.com> wrote:
>> This causes a bootstrap failure for me.
>>
>> PR/101959
>
>Sorry for that; "details".  ;-|  OK to push the attached
>"Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand'
>work on 32-bit architectures [PR101959]", which does resolve the issue
>for a '-m32' i686-pc-linux-gnu build?

Ok. 

Richard. 


>
>Grüße
> Thomas
>
>
>> On Tue, Aug 17, 2021 at 5:00 AM Richard Biener via Gcc <gcc@gcc.gnu.org> wrote:
>>>
>>> On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge <thomas@codesourcery.com> wrote:
>>> >
>>> > Hi!
>>> >
>>> > On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
>>> > > On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>>> > >> [...], to document the current behavior, I propose to
>>> > >> "Add more self-tests for 'hash_map' with Value type with non-trivial
>>> > >> constructor/destructor", see attached.  OK to push to master branch?
>>> > >> (Also cherry-pick into release branches, eventually?)
>>> >
>>> > (Attached again, for easy reference.)
>>> >
>>> > > Adding more tests sounds like an excellent idea.  I'm not sure about
>>> > > the idea of adding loopy selftests that iterate as many times as in
>>> > > the patch (looks like 1234 times two?)
>>> >
>>> > Correct, and I agree it's a sensible concern, generally.
>>> >
>>> > The current 1234 times two iterations is really arbitrary (should
>>> > document that in the test case), just so that we trigger a few hash table
>>> > expansions.
>>>
>>> You could lower N_init (the default init is just 13!),
>>> even with just 128 inserted elements you'll trigger
>>> expansions to 31, 61 and 127 elements.
>>>
>>> > For 'selftest-c', we've got originally:
>>> >
>>> >     -fself-test: 74775 pass(es) in 0.309299 seconds
>>> >     -fself-test: 74775 pass(es) in 0.366041 seconds
>>> >     -fself-test: 74775 pass(es) in 0.356663 seconds
>>> >     -fself-test: 74775 pass(es) in 0.355009 seconds
>>> >     -fself-test: 74775 pass(es) in 0.367575 seconds
>>> >     -fself-test: 74775 pass(es) in 0.320406 seconds
>>> >
>>> > ..., and with my changes we've got:
>>> >
>>> >     -fself-test: 94519 pass(es) in 0.327755 seconds
>>> >     -fself-test: 94519 pass(es) in 0.369522 seconds
>>> >     -fself-test: 94519 pass(es) in 0.355531 seconds
>>> >     -fself-test: 94519 pass(es) in 0.362179 seconds
>>> >     -fself-test: 94519 pass(es) in 0.363176 seconds
>>> >     -fself-test: 94519 pass(es) in 0.318930 seconds
>>> >
>>> > So it really seems to be all in the noise?
>>>
>>> Yes.  I think the test is OK but it's also reasonable to lower
>>> the '1234' times and add a comment as to the count should
>>> trigger hashtable expansions "a few times".
>>>
>>> Richard.
>>>
>>> > Yet:
>>> >
>>> > > Selftests run each time GCC
>>> > > builds (i.e., even during day to day development).  It seems to me
>>> > > that it might be better to run such selftests only as part of
>>> > > the bootstrap process.
>>> >
>>> > I'd rather have thought about a '--param self-test-expensive' (or
>>> > similar), and then invoke the selftests via a new
>>> > 'gcc/testsuite/selftests/expensive.exp' (or similar).
>>> >
>>> > Or, adapt 'gcc/testsuite/gcc.dg/plugin/expensive_selftests_plugin.c',
>>> > that is, invoke them via the GCC plugin mechanism, which also seems to be
>>> > easy enough?
>>> >
>>> > I don't have a strong opinion about where/when these tests get run, so
>>> > will happily take any suggestions.
>>> >
>>> >
>>> > Grüße
>>> >  Thomas
>>> >
>>> >
>>> > -----------------
>>> > Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955
>
>
>-----------------
>Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

Re: Expensive selftests

[Martin Sebor]

On 8/17/21 12:40 AM, Thomas Schwinge wrote:
> Hi!
> 
> On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
>> On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>>> [...], to document the current behavior, I propose to
>>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>>> constructor/destructor", see attached.  OK to push to master branch?
>>> (Also cherry-pick into release branches, eventually?)
> 
> (Attached again, for easy reference.)
> 
>> Adding more tests sounds like an excellent idea.  I'm not sure about
>> the idea of adding loopy selftests that iterate as many times as in
>> the patch (looks like 1234 times two?)
> 
> Correct, and I agree it's a sensible concern, generally.
> 
> The current 1234 times two iterations is really arbitrary (should
> document that in the test case), just so that we trigger a few hash table
> expansions.
> 
> For 'selftest-c', we've got originally:
> 
>      -fself-test: 74775 pass(es) in 0.309299 seconds
>      -fself-test: 74775 pass(es) in 0.366041 seconds
>      -fself-test: 74775 pass(es) in 0.356663 seconds
>      -fself-test: 74775 pass(es) in 0.355009 seconds
>      -fself-test: 74775 pass(es) in 0.367575 seconds
>      -fself-test: 74775 pass(es) in 0.320406 seconds
> 
> ..., and with my changes we've got:
> 
>      -fself-test: 94519 pass(es) in 0.327755 seconds
>      -fself-test: 94519 pass(es) in 0.369522 seconds
>      -fself-test: 94519 pass(es) in 0.355531 seconds
>      -fself-test: 94519 pass(es) in 0.362179 seconds
>      -fself-test: 94519 pass(es) in 0.363176 seconds
>      -fself-test: 94519 pass(es) in 0.318930 seconds
> 
> So it really seems to be all in the noise?
> 
> Yet:
> 
>> Selftests run each time GCC
>> builds (i.e., even during day to day development).  It seems to me
>> that it might be better to run such selftests only as part of
>> the bootstrap process.
> 
> I'd rather have thought about a '--param self-test-expensive' (or
> similar), and then invoke the selftests via a new
> 'gcc/testsuite/selftests/expensive.exp' (or similar).
> 
> Or, adapt 'gcc/testsuite/gcc.dg/plugin/expensive_selftests_plugin.c',
> that is, invoke them via the GCC plugin mechanism, which also seems to be
> easy enough?
> 
> I don't have a strong opinion about where/when these tests get run, so
> will happily take any suggestions.

I think the right design is to move all these basic building blocks
(at a minimum, all containers, but ultimately even higher level
general-purpose APIs) into a standalone library with its own unit
tests run independently of GCC.

I'm fine with adding these tests if no one else is concerned about
the overhead, especially with a lower number of iterations like
Richard suggests (as long as it still exercises the expansion,
of course).

Thanks
Martin

> 
> 
> Grüße
>   Thomas
> 
> 
> -----------------
> Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955
> 

Fix 'hash_table::expand' to destruct stale Value objects (was: 'hash_map<tree, hash_map<tree, tree>>')

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 12279 bytes --]

Hi!

Ping -- we still need to plug the memory leak; see patch attached, and/or
long discussion here:

On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
> On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>> On 2021-08-12T17:15:44-0600, Martin Sebor via Gcc <gcc@gcc.gnu.org> wrote:
>>> On 8/6/21 10:57 AM, Thomas Schwinge wrote:
>>>> So I'm trying to do some C++...  ;-)
>>>>
>>>> Given:
>>>>
>>>>       /* A map from SSA names or var decls to record fields.  */
>>>>       typedef hash_map<tree, tree> field_map_t;
>>>>
>>>>       /* For each propagation record type, this is a map from SSA names or var decls
>>>>          to propagate, to the field in the record type that should be used for
>>>>          transmission and reception.  */
>>>>       typedef hash_map<tree, field_map_t> record_field_map_t;
>>>>
>>>> Thus, that's a 'hash_map<tree, hash_map<tree, tree>>'.  (I may do that,
>>>> right?)  Looking through GCC implementation files, very most of all uses
>>>> of 'hash_map' boil down to pointer key ('tree', for example) and
>>>> pointer/integer value.
>>>
>>> Right.  Because most GCC containers rely exclusively on GCC's own
>>> uses for testing, if your use case is novel in some way, chances
>>> are it might not work as intended in all circumstances.
>>>
>>> I've wrestled with hash_map a number of times.  A use case that's
>>> close to yours (i.e., a non-trivial value type) is in cp/parser.c:
>>> see class_to_loc_map_t.
>>
>> Indeed, at the time you sent this email, I already had started looking
>> into that one!  (The Fortran test cases that I originally analyzed, which
>> triggered other cases of non-POD/non-trivial destructor, all didn't
>> result in a memory leak, because the non-trivial constructor doesn't
>> actually allocate any resources dynamically -- that's indeed different in
>> this case here.)  ..., and indeed:
>>
>>> (I don't remember if I tested it for leaks
>>> though.  It's used to implement -Wmismatched-tags so compiling
>>> a few tests under Valgrind should show if it does leak.)
>>
>> ... it does leak memory at present.  :-| (See attached commit log for
>> details for one example.)

(Attached "Fix 'hash_table::expand' to destruct stale Value objects"
again.)

>> To that effect, to document the current behavior, I propose to
>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>> constructor/destructor"

(We've done that in commit e4f16e9f357a38ec702fb69a0ffab9d292a6af9b
"Add more self-tests for 'hash_map' with Value type with non-trivial
constructor/destructor", quickly followed by bug fix
commit bb04a03c6f9bacc890118b9e12b657503093c2f8
"Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand'
work on 32-bit architectures [PR101959]".

>> (Also cherry-pick into release branches, eventually?)

>>>> Then:
>>>>
>>>>       record_field_map_t field_map ([...]); // see below
>>>>       for ([...])
>>>>         {
>>>>           tree record_type = [...];
>>>>           [...]
>>>>           bool existed;
>>>>           field_map_t &fields
>>>>             = field_map.get_or_insert (record_type, &existed);
>>>>           gcc_checking_assert (!existed);
>>>>           [...]
>>>>           for ([...])
>>>>             fields.put ([...], [...]);
>>>>           [...]
>>>>         }
>>>>       [stuff that looks up elements from 'field_map']
>>>>       field_map.empty ();
>>>>
>>>> This generally works.
>>>>
>>>> If I instantiate 'record_field_map_t field_map (40);', Valgrind is happy.
>>>> If however I instantiate 'record_field_map_t field_map (13);' (where '13'
>>>> would be the default for 'hash_map'), Valgrind complains:
>>>>
>>>>       2,080 bytes in 10 blocks are definitely lost in loss record 828 of 876
>>>>          at 0x483DD99: calloc (vg_replace_malloc.c:762)
>>>>          by 0x175F010: xcalloc (xmalloc.c:162)
>>>>          by 0xAF4A2C: hash_table<hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_entry, false, xcallocator>::hash_table(unsigned long, bool, bool, bool, mem_alloc_origin) (hash-table.h:275)
>>>>          by 0x15E0120: hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_map(unsigned long, bool, bool, bool) (hash-map.h:143)
>>>>          by 0x15DEE87: hash_map<tree_node*, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >, simple_hashmap_traits<default_hash_traits<tree_node*>, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> > > >::get_or_insert(tree_node* const&, bool*) (hash-map.h:205)
>>>>          by 0x15DD52C: execute_omp_oacc_neuter_broadcast() (omp-oacc-neuter-broadcast.cc:1371)
>>>>          [...]
>>>>
>>>> (That's with '#pragma GCC optimize "O0"' at the top of the 'gcc/*.cc'
>>>> file.)
>>>>
>>>> My suspicion was that it is due to the 'field_map' getting resized as it
>>>> incrementally grows (and '40' being big enough for that to never happen),
>>>> and somehow the non-POD (?) value objects not being properly handled
>>>> during that.  Working my way a bit through 'gcc/hash-map.*' and
>>>> 'gcc/hash-table.*' (but not claiming that I understand all that, off
>>>> hand), it seems as if my theory is right: I'm able to plug this memory
>>>> leak as follows:
>>>>
>>>>       --- gcc/hash-table.h
>>>>       +++ gcc/hash-table.h
>>>>       @@ -820,6 +820,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>>>>                {
>>>>                  value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>>>>             new ((void*) q) value_type (std::move (x));
>>>>       +     //BAD Descriptor::remove (x); // (doesn't make sense and) a ton of "Invalid read [...] inside a block of size [...] free'd"
>>>>       +     x.~value_type (); //GOOD This seems to work!  -- but does it make sense?
>>>>                }
>>>>
>>>>              p++;
>>>>
>>>> However, that doesn't exactly look like a correct fix, does it?  I'd
>>>> expect such a manual destructor call in combination with placement new
>>>> (that is being used here, obviously) -- but this is after 'std::move'?
>>>> However, this also survives a smoke-test-like run of parts of the GCC
>>>> testsuite, bootstrap and complete run now ongoing.
>>>
>>> If explicitly calling the dtor on the moved object is the right thing
>>> to do I'd expect to see such invocations elsewhere in hash_table but
>>> I don't.  It does seem like removed elements ought to be destroyed,
>>> but it also seems like the destruction should go through some traits
>>> class (e.g., call Descriptor::remove and mark_deleted or do some
>>> similar dance), and be called from other member functions that move
>>> elements.
>>
>> So, we shall assume that any "real C++" use case (that is, C++ class) is
>> using the appropriate C++ method, that is, 'typed_delete_remove', which
>> does 'delete', which does destroy the C++ object, if applicable, else
>> 'typed_noop_remove'.
>>
>> (Shall we look into the few places that use 'typed_free_remove' via
>> 'free_ptr_hash', and potentially replace them with 'typed_delete_remove'?
>> Or is there a reason for the two schemes to co-exist, other than for
>> legacy reasons?  Anyway, that's for another day.)
>
> I find all these these traits pretty much impenetrable.

(Indeed.  ... which triggered this reflex with me, to try simplifying
this by getting rid of 'typed_free_remove' etc...)

> I guess
> intuitively, I'd expect Descriptor::remove() to destroy an element,
> but I have no idea if that would be right given the design.

So 'typed_delete_remove' does destruct via 'delete'.  'typed_free_remove'
doesn't -- but is only used via 'free_ptr_hash', where this isn't
relevant?  'typed_noop_remove' I haven't considered yet regarding that
issue.  Anyway, that's all for another day.

>> What is different in the 'hash_table::expand' case is that all the Value
>> objects do get 'std::move'd into a new blob of memory via placement new
>> (so a subsequent 'delete' via 'typed_delete_remove' is not appropriate),
>> but then the stale Value objects never get destructed.  And indeed an
>> explicit destructor call (which, as I understand is a no-op for primitive
>> types; "pseudo destructor") is the right thing to do; see
>> <https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
>> and others, for example.  (Therefore, I don't think this needs to be
>> routed through a "traits" function, but can rather be done in-line here,
>> after each placement new, before deallocation of the original blob of
>> memory.  Also, I argue it's the right thing to do also for 'm_ggc',
>> because even if in that case we're not going to leak memory (GC will
>> reclaim), but we still may leak other resources dynamically allocated in
>> a non-trivial constructor.)
>
> Yes, of course, all elements need to be eventually be destroyed.
> My only hesitation was whether it should be done via one of these
> traits classes (like it's done in C++ containers via allocators)
> rather than directly

Given that there is (apparently) no issue to do a placement new in
'hash_table::expand', I'd asumme a -- corresponding -- explicit
destructor call would be likewise appropriate?  (But I'll of course route
this through a (new) "traits" function if someone explains why this is
the right thing to do.)

> and whether there might be other places
> where the destruction night need to happen.

(Possibly, yes, per discussion above -- but that's a separate issue?)

>> The attached "Fix 'hash_table::expand' to destruct stale Value objects"
>> does prevent my original problem, does address the current 'class2loc'
>> memory leak in 'cp/parser.c' (see commit log for one example), and
>> adjusts the new
>> 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' test
>> case such that number of constructor calls matches the number of
>> destructor calls.  After some careful review regarding C++ details
>> (please!), OK to push to master branch?  (Also cherry-pick into release
>> branches, eventually?)  Is the source code comment that I'm adding
>> sufficiently explanatory and correct in C++ terms?

Ping.

> Shouldn't the hash_table dtor (and perhaps also empty())  also
> destroy the elements?  (Otherwise, what destroys the elements
> newly constructed here, or anywhere else for that matter, such
> as in the hash_table ctor?)

Per my understanding, per discussion above, they (eventually) do get
destroyed via 'delete' in 'typed_delete_remove', for example, via
'Descriptor::remove' calls for all/relevant entries in
'hash_table::~hash_table', 'hash_table::empty_slow',
'hash_table::clear_slot', 'hash_table::remove_elt_with_hash'.

(This means that if there has been an intermediate 'expand', this may
(eventually) destroy objects at a different memory location from where
they originally have been created -- but that's fine.)

The 'expand' case itself is different: any (live) entries are *moved*
into a new storage memory object via placement new.  (And then the
hollow entries in the old storage memory object linger.)

> Also, shouldn't the destroyed slot be marked either deleted or
> empty?)

Per my understanding, irrelevant in 'expand': working through 'oentries',
the *move* is only done 'if (!is_empty (x) && !is_deleted (x))' (so
combined with the item above, there is no memory leak for any entries
that have already been 'remove'd -- they have already been destructed),
and the whole (old) storage memory object will be deallocated right after
the 'oentries' loop.


> (Sorry, I realize I have more questions than answers.)

No worries, happens to me most of the times!  Thanks for looking into
this.


Grüße
 Thomas


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-hash_table-expand-to-destruct-stale-Value-object.patch --]
[-- Type: text/x-diff, Size: 17345 bytes --]

From 2275962abd72acd1636d438d1cb176bbabdcef06 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 18:03:38 +0200
Subject: [PATCH] Fix 'hash_table::expand' to destruct stale Value objects

Thus plugging potentional memory leaks if these have non-trivial
constructor/destructor.

See
<https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
and others.

As one example, compilation of 'g++.dg/warn/Wmismatched-tags.C' per
'valgrind --leak-check=full' improves as follows:

     [...]
    -
    -104 bytes in 1 blocks are definitely lost in loss record 399 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA43C71: cp_parser_parameter_declaration(cp_parser*, int, bool, bool*) (parser.c:24242)
    -
    -168 bytes in 3 blocks are definitely lost in loss record 422 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA53385: cp_parser_single_declaration(cp_parser*, vec<deferred_access_check, va_gc, vl_embed>*, bool, bool, bool*) (parser.c:31072)
    -
    -488 bytes in 7 blocks are definitely lost in loss record 449 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA49508: cp_parser_member_declaration(cp_parser*) (parser.c:26440)
    -
    -728 bytes in 7 blocks are definitely lost in loss record 455 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA57508: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32980)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -   by 0xA47D76: cp_parser_class_specifier(cp_parser*) (parser.c:25680)
    -   by 0xA37E27: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18912)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -
    -832 bytes in 8 blocks are definitely lost in loss record 458 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -
    -1,144 bytes in 11 blocks are definitely lost in loss record 466 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -
    -1,376 bytes in 10 blocks are definitely lost in loss record 467 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA301E0: cp_parser_simple_declaration(cp_parser*, bool, tree_node**) (parser.c:14772)
    -
    -3,552 bytes in 33 blocks are definitely lost in loss record 483 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA8964A: class_decl_loc_t::class_decl_loc_t(class_decl_loc_t const&) (parser.c:32689)
    -   by 0xA8F515: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::expand() (hash-table.h:839)
    -   by 0xA8D4B3: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::find_slot_with_hash(tree_node* const&, unsigned int, insert_option) (hash-table.h:1008)
    -   by 0xA8B1DC: hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::get_or_insert(tree_node* const&, bool*) (hash-map.h:200)
    -   by 0xA57128: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32888)
     [...]
     LEAK SUMMARY:
    -   definitely lost: 8,440 bytes in 81 blocks
    +   definitely lost: 48 bytes in 1 blocks
        indirectly lost: 12,529 bytes in 329 blocks
          possibly lost: 0 bytes in 0 blocks
        still reachable: 1,644,376 bytes in 768 blocks

	gcc/
	* hash-table.h (hash_table<Descriptor, Lazy, Allocator>::expand):
	Destruct stale Value objects.
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor_expand):
	Update.
---
 gcc/hash-map-tests.c | 10 ++++++----
 gcc/hash-table.h     |  4 ++++
 2 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 6acc0d4337e..511d4342087 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -305,31 +305,32 @@ test_map_of_type_with_ctor_and_dtor ()
 	m.get_or_insert (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, i);
 
 	m.remove (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, 1 + i);
       }
   }
 }
 
-/* Verify aspects of 'hash_table::expand'.  */
+/* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
+   Value objects.  */
 
 static void
 test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 {
   /* Configure, so that hash table expansion triggers a few times.  */
   const size_t N_init = 0;
   const int N_elem = 70;
   size_t expand_c_expected = 4;
   size_t expand_c = 0;
 
   /* For stability of this testing, we need all Key values 'k' to produce
      unique hash values 'Traits::hash (k)', as otherwise the dynamic
      insert/remove behavior may diverge across different architectures.  This
      is, for example, a problem when using the standard 'pointer_hash::hash',
      which is simply doing a 'k >> 3' operation, which is fine on 64-bit
@@ -388,69 +389,70 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 	    unsigned int nindex = hash_table_higher_prime_index (elts * 2);
 	    m_size = prime_tab[nindex].prime;
 	  }
 	  m_n_deleted = 0;
 
 	  /* All non-deleted elements have been moved.  */
 	  n_expand_moved += i;
 	  if (remove_some_inline)
 	    n_expand_moved -= (i + 2) / 3;
 	}
 
       ASSERT_EQ (val_t::ndefault, 1 + i);
       ASSERT_EQ (val_t::ncopy, n_expand_moved);
       ASSERT_EQ (val_t::nassign, 0);
       if (remove_some_inline)
-	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
       else
-	ASSERT_EQ (val_t::ndtor, 0);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved);
 
       /* Remove some inline.  This never triggers an 'expand' here, but via
 	 'm_n_deleted' does influence any following one.  */
       if (remove_some_inline
 	  && !(i % 3))
 	{
 	  m.remove (a[i]);
 	  /* Per 'hash_table::remove_elt_with_hash'.  */
 	  m_n_deleted++;
 
 	  ASSERT_EQ (val_t::ndefault, 1 + i);
 	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
 	  ASSERT_EQ (val_t::nassign, 0);
-	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	  ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
 	}
     }
   ASSERT_EQ (expand_c, expand_c_expected);
 
   int ndefault = val_t::ndefault;
   int ncopy = val_t::ncopy;
   int nassign = val_t::nassign;
   int ndtor = val_t::ndtor;
 
   for (int i = 0; i < N_elem; ++i)
     {
       if (remove_some_inline
 	  && !(i % 3))
 	continue;
 
       m.remove (a[i]);
       ++ndtor;
       ASSERT_EQ (val_t::ndefault, ndefault);
       ASSERT_EQ (val_t::ncopy, ncopy);
       ASSERT_EQ (val_t::nassign, nassign);
       ASSERT_EQ (val_t::ndtor, ndtor);
     }
+  ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
    "empty" value.  */
 
 static void
 test_nonzero_empty_key ()
 {
   typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
   hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
 
   for (int i = 1; i != 32; ++i)
     x.put (i, i);
 
   ASSERT_EQ (x.get (0), NULL);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index a6e0ac8eea9..8c2a0589fbd 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -808,30 +808,34 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
   m_entries = nentries;
   m_size = nsize;
   m_size_prime_index = nindex;
   m_n_elements -= m_n_deleted;
   m_n_deleted = 0;
 
   value_type *p = oentries;
   do
     {
       value_type &x = *p;
 
       if (!is_empty (x) && !is_deleted (x))
         {
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 	  new ((void*) q) value_type (std::move (x));
+
+	  /* Manually invoke destructor of original object, to counterbalance
+	     object constructed via placement new.  */
+	  x.~value_type ();
         }
 
       p++;
     }
   while (p < olimit);
 
   if (!m_ggc)
     Allocator <value_type> ::data_free (oentries);
   else
     ggc_free (oentries);
 }
 
 /* Implements empty() in cases where it isn't a no-op.  */
 
 template<typename Descriptor, bool Lazy,
-- 
2.30.2

Re: Fix 'hash_table::expand' to destruct stale Value objects

[Martin Sebor]

On 8/30/21 4:46 AM, Thomas Schwinge wrote:
> Hi!
> 
> Ping -- we still need to plug the memory leak; see patch attached, and/or
> long discussion here:

Thanks for answering my questions.  I have no concerns with going
forward with the patch as is.  Just a suggestion/request: unless
this patch fixes all the outstanding problems you know of or suspect
in this area (leaks/missing dtor calls) and unless you plan to work
on those in the near future, please open a bug for them with a brain
dump of what you learned.  That should save us time when the day
comes to tackle those.

Martin

> 
> On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
>> On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>>> On 2021-08-12T17:15:44-0600, Martin Sebor via Gcc <gcc@gcc.gnu.org> wrote:
>>>> On 8/6/21 10:57 AM, Thomas Schwinge wrote:
>>>>> So I'm trying to do some C++...  ;-)
>>>>>
>>>>> Given:
>>>>>
>>>>>        /* A map from SSA names or var decls to record fields.  */
>>>>>        typedef hash_map<tree, tree> field_map_t;
>>>>>
>>>>>        /* For each propagation record type, this is a map from SSA names or var decls
>>>>>           to propagate, to the field in the record type that should be used for
>>>>>           transmission and reception.  */
>>>>>        typedef hash_map<tree, field_map_t> record_field_map_t;
>>>>>
>>>>> Thus, that's a 'hash_map<tree, hash_map<tree, tree>>'.  (I may do that,
>>>>> right?)  Looking through GCC implementation files, very most of all uses
>>>>> of 'hash_map' boil down to pointer key ('tree', for example) and
>>>>> pointer/integer value.
>>>>
>>>> Right.  Because most GCC containers rely exclusively on GCC's own
>>>> uses for testing, if your use case is novel in some way, chances
>>>> are it might not work as intended in all circumstances.
>>>>
>>>> I've wrestled with hash_map a number of times.  A use case that's
>>>> close to yours (i.e., a non-trivial value type) is in cp/parser.c:
>>>> see class_to_loc_map_t.
>>>
>>> Indeed, at the time you sent this email, I already had started looking
>>> into that one!  (The Fortran test cases that I originally analyzed, which
>>> triggered other cases of non-POD/non-trivial destructor, all didn't
>>> result in a memory leak, because the non-trivial constructor doesn't
>>> actually allocate any resources dynamically -- that's indeed different in
>>> this case here.)  ..., and indeed:
>>>
>>>> (I don't remember if I tested it for leaks
>>>> though.  It's used to implement -Wmismatched-tags so compiling
>>>> a few tests under Valgrind should show if it does leak.)
>>>
>>> ... it does leak memory at present.  :-| (See attached commit log for
>>> details for one example.)
> 
> (Attached "Fix 'hash_table::expand' to destruct stale Value objects"
> again.)
> 
>>> To that effect, to document the current behavior, I propose to
>>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>>> constructor/destructor"
> 
> (We've done that in commit e4f16e9f357a38ec702fb69a0ffab9d292a6af9b
> "Add more self-tests for 'hash_map' with Value type with non-trivial
> constructor/destructor", quickly followed by bug fix
> commit bb04a03c6f9bacc890118b9e12b657503093c2f8
> "Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand'
> work on 32-bit architectures [PR101959]".
> 
>>> (Also cherry-pick into release branches, eventually?)
> 
>>>>> Then:
>>>>>
>>>>>        record_field_map_t field_map ([...]); // see below
>>>>>        for ([...])
>>>>>          {
>>>>>            tree record_type = [...];
>>>>>            [...]
>>>>>            bool existed;
>>>>>            field_map_t &fields
>>>>>              = field_map.get_or_insert (record_type, &existed);
>>>>>            gcc_checking_assert (!existed);
>>>>>            [...]
>>>>>            for ([...])
>>>>>              fields.put ([...], [...]);
>>>>>            [...]
>>>>>          }
>>>>>        [stuff that looks up elements from 'field_map']
>>>>>        field_map.empty ();
>>>>>
>>>>> This generally works.
>>>>>
>>>>> If I instantiate 'record_field_map_t field_map (40);', Valgrind is happy.
>>>>> If however I instantiate 'record_field_map_t field_map (13);' (where '13'
>>>>> would be the default for 'hash_map'), Valgrind complains:
>>>>>
>>>>>        2,080 bytes in 10 blocks are definitely lost in loss record 828 of 876
>>>>>           at 0x483DD99: calloc (vg_replace_malloc.c:762)
>>>>>           by 0x175F010: xcalloc (xmalloc.c:162)
>>>>>           by 0xAF4A2C: hash_table<hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_entry, false, xcallocator>::hash_table(unsigned long, bool, bool, bool, mem_alloc_origin) (hash-table.h:275)
>>>>>           by 0x15E0120: hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_map(unsigned long, bool, bool, bool) (hash-map.h:143)
>>>>>           by 0x15DEE87: hash_map<tree_node*, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >, simple_hashmap_traits<default_hash_traits<tree_node*>, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> > > >::get_or_insert(tree_node* const&, bool*) (hash-map.h:205)
>>>>>           by 0x15DD52C: execute_omp_oacc_neuter_broadcast() (omp-oacc-neuter-broadcast.cc:1371)
>>>>>           [...]
>>>>>
>>>>> (That's with '#pragma GCC optimize "O0"' at the top of the 'gcc/*.cc'
>>>>> file.)
>>>>>
>>>>> My suspicion was that it is due to the 'field_map' getting resized as it
>>>>> incrementally grows (and '40' being big enough for that to never happen),
>>>>> and somehow the non-POD (?) value objects not being properly handled
>>>>> during that.  Working my way a bit through 'gcc/hash-map.*' and
>>>>> 'gcc/hash-table.*' (but not claiming that I understand all that, off
>>>>> hand), it seems as if my theory is right: I'm able to plug this memory
>>>>> leak as follows:
>>>>>
>>>>>        --- gcc/hash-table.h
>>>>>        +++ gcc/hash-table.h
>>>>>        @@ -820,6 +820,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>>>>>                 {
>>>>>                   value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>>>>>              new ((void*) q) value_type (std::move (x));
>>>>>        +     //BAD Descriptor::remove (x); // (doesn't make sense and) a ton of "Invalid read [...] inside a block of size [...] free'd"
>>>>>        +     x.~value_type (); //GOOD This seems to work!  -- but does it make sense?
>>>>>                 }
>>>>>
>>>>>               p++;
>>>>>
>>>>> However, that doesn't exactly look like a correct fix, does it?  I'd
>>>>> expect such a manual destructor call in combination with placement new
>>>>> (that is being used here, obviously) -- but this is after 'std::move'?
>>>>> However, this also survives a smoke-test-like run of parts of the GCC
>>>>> testsuite, bootstrap and complete run now ongoing.
>>>>
>>>> If explicitly calling the dtor on the moved object is the right thing
>>>> to do I'd expect to see such invocations elsewhere in hash_table but
>>>> I don't.  It does seem like removed elements ought to be destroyed,
>>>> but it also seems like the destruction should go through some traits
>>>> class (e.g., call Descriptor::remove and mark_deleted or do some
>>>> similar dance), and be called from other member functions that move
>>>> elements.
>>>
>>> So, we shall assume that any "real C++" use case (that is, C++ class) is
>>> using the appropriate C++ method, that is, 'typed_delete_remove', which
>>> does 'delete', which does destroy the C++ object, if applicable, else
>>> 'typed_noop_remove'.
>>>
>>> (Shall we look into the few places that use 'typed_free_remove' via
>>> 'free_ptr_hash', and potentially replace them with 'typed_delete_remove'?
>>> Or is there a reason for the two schemes to co-exist, other than for
>>> legacy reasons?  Anyway, that's for another day.)
>>
>> I find all these these traits pretty much impenetrable.
> 
> (Indeed.  ... which triggered this reflex with me, to try simplifying
> this by getting rid of 'typed_free_remove' etc...)
> 
>> I guess
>> intuitively, I'd expect Descriptor::remove() to destroy an element,
>> but I have no idea if that would be right given the design.
> 
> So 'typed_delete_remove' does destruct via 'delete'.  'typed_free_remove'
> doesn't -- but is only used via 'free_ptr_hash', where this isn't
> relevant?  'typed_noop_remove' I haven't considered yet regarding that
> issue.  Anyway, that's all for another day.
> 
>>> What is different in the 'hash_table::expand' case is that all the Value
>>> objects do get 'std::move'd into a new blob of memory via placement new
>>> (so a subsequent 'delete' via 'typed_delete_remove' is not appropriate),
>>> but then the stale Value objects never get destructed.  And indeed an
>>> explicit destructor call (which, as I understand is a no-op for primitive
>>> types; "pseudo destructor") is the right thing to do; see
>>> <https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
>>> and others, for example.  (Therefore, I don't think this needs to be
>>> routed through a "traits" function, but can rather be done in-line here,
>>> after each placement new, before deallocation of the original blob of
>>> memory.  Also, I argue it's the right thing to do also for 'm_ggc',
>>> because even if in that case we're not going to leak memory (GC will
>>> reclaim), but we still may leak other resources dynamically allocated in
>>> a non-trivial constructor.)
>>
>> Yes, of course, all elements need to be eventually be destroyed.
>> My only hesitation was whether it should be done via one of these
>> traits classes (like it's done in C++ containers via allocators)
>> rather than directly
> 
> Given that there is (apparently) no issue to do a placement new in
> 'hash_table::expand', I'd asumme a -- corresponding -- explicit
> destructor call would be likewise appropriate?  (But I'll of course route
> this through a (new) "traits" function if someone explains why this is
> the right thing to do.)
> 
>> and whether there might be other places
>> where the destruction night need to happen.
> 
> (Possibly, yes, per discussion above -- but that's a separate issue?)
> 
>>> The attached "Fix 'hash_table::expand' to destruct stale Value objects"
>>> does prevent my original problem, does address the current 'class2loc'
>>> memory leak in 'cp/parser.c' (see commit log for one example), and
>>> adjusts the new
>>> 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' test
>>> case such that number of constructor calls matches the number of
>>> destructor calls.  After some careful review regarding C++ details
>>> (please!), OK to push to master branch?  (Also cherry-pick into release
>>> branches, eventually?)  Is the source code comment that I'm adding
>>> sufficiently explanatory and correct in C++ terms?
> 
> Ping.
> 
>> Shouldn't the hash_table dtor (and perhaps also empty())  also
>> destroy the elements?  (Otherwise, what destroys the elements
>> newly constructed here, or anywhere else for that matter, such
>> as in the hash_table ctor?)
> 
> Per my understanding, per discussion above, they (eventually) do get
> destroyed via 'delete' in 'typed_delete_remove', for example, via
> 'Descriptor::remove' calls for all/relevant entries in
> 'hash_table::~hash_table', 'hash_table::empty_slow',
> 'hash_table::clear_slot', 'hash_table::remove_elt_with_hash'.
> 
> (This means that if there has been an intermediate 'expand', this may
> (eventually) destroy objects at a different memory location from where
> they originally have been created -- but that's fine.)
> 
> The 'expand' case itself is different: any (live) entries are *moved*
> into a new storage memory object via placement new.  (And then the
> hollow entries in the old storage memory object linger.)
> 
>> Also, shouldn't the destroyed slot be marked either deleted or
>> empty?)
> 
> Per my understanding, irrelevant in 'expand': working through 'oentries',
> the *move* is only done 'if (!is_empty (x) && !is_deleted (x))' (so
> combined with the item above, there is no memory leak for any entries
> that have already been 'remove'd -- they have already been destructed),
> and the whole (old) storage memory object will be deallocated right after
> the 'oentries' loop.
> 
> 
>> (Sorry, I realize I have more questions than answers.)
> 
> No worries, happens to me most of the times!  Thanks for looking into
> this.
> 
> 
> Grüße
>   Thomas
> 
> 
> -----------------
> Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955
> 

[PING] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 13931 bytes --]

Hi!

On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
>> Ping -- we still need to plug the memory leak; see patch attached, and/or
>> long discussion here:
>
> Thanks for answering my questions.  I have no concerns with going
> forward with the patch as is.

Thanks, Martin.  Ping for formal approval (and review for using proper
C++ terminology in the 'gcc/hash-table.h:hash_table::expand' source code
comment that I'm adding).  Patch again attached, for easy reference.


> Just a suggestion/request: unless
> this patch fixes all the outstanding problems you know of or suspect
> in this area (leaks/missing dtor calls) and unless you plan to work
> on those in the near future, please open a bug for them with a brain
> dump of what you learned.  That should save us time when the day
> comes to tackle those.

ACK.  I'm not aware of any additional known problems.  (In our email
discussion, we did have some "vague ideas" for opportunities of
clarification/clean-up, but these aren't worth filing PRs for; needs
someone to gain understanding, taking a look.)


Grüße
 Thomas


>> On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
>>> On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>>>> On 2021-08-12T17:15:44-0600, Martin Sebor via Gcc <gcc@gcc.gnu.org> wrote:
>>>>> On 8/6/21 10:57 AM, Thomas Schwinge wrote:
>>>>>> So I'm trying to do some C++...  ;-)
>>>>>>
>>>>>> Given:
>>>>>>
>>>>>>        /* A map from SSA names or var decls to record fields.  */
>>>>>>        typedef hash_map<tree, tree> field_map_t;
>>>>>>
>>>>>>        /* For each propagation record type, this is a map from SSA names or var decls
>>>>>>           to propagate, to the field in the record type that should be used for
>>>>>>           transmission and reception.  */
>>>>>>        typedef hash_map<tree, field_map_t> record_field_map_t;
>>>>>>
>>>>>> Thus, that's a 'hash_map<tree, hash_map<tree, tree>>'.  (I may do that,
>>>>>> right?)  Looking through GCC implementation files, very most of all uses
>>>>>> of 'hash_map' boil down to pointer key ('tree', for example) and
>>>>>> pointer/integer value.
>>>>>
>>>>> Right.  Because most GCC containers rely exclusively on GCC's own
>>>>> uses for testing, if your use case is novel in some way, chances
>>>>> are it might not work as intended in all circumstances.
>>>>>
>>>>> I've wrestled with hash_map a number of times.  A use case that's
>>>>> close to yours (i.e., a non-trivial value type) is in cp/parser.c:
>>>>> see class_to_loc_map_t.
>>>>
>>>> Indeed, at the time you sent this email, I already had started looking
>>>> into that one!  (The Fortran test cases that I originally analyzed, which
>>>> triggered other cases of non-POD/non-trivial destructor, all didn't
>>>> result in a memory leak, because the non-trivial constructor doesn't
>>>> actually allocate any resources dynamically -- that's indeed different in
>>>> this case here.)  ..., and indeed:
>>>>
>>>>> (I don't remember if I tested it for leaks
>>>>> though.  It's used to implement -Wmismatched-tags so compiling
>>>>> a few tests under Valgrind should show if it does leak.)
>>>>
>>>> ... it does leak memory at present.  :-| (See attached commit log for
>>>> details for one example.)
>>
>> (Attached "Fix 'hash_table::expand' to destruct stale Value objects"
>> again.)
>>
>>>> To that effect, to document the current behavior, I propose to
>>>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>>>> constructor/destructor"
>>
>> (We've done that in commit e4f16e9f357a38ec702fb69a0ffab9d292a6af9b
>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>> constructor/destructor", quickly followed by bug fix
>> commit bb04a03c6f9bacc890118b9e12b657503093c2f8
>> "Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand'
>> work on 32-bit architectures [PR101959]".
>>
>>>> (Also cherry-pick into release branches, eventually?)
>>
>>>>>> Then:
>>>>>>
>>>>>>        record_field_map_t field_map ([...]); // see below
>>>>>>        for ([...])
>>>>>>          {
>>>>>>            tree record_type = [...];
>>>>>>            [...]
>>>>>>            bool existed;
>>>>>>            field_map_t &fields
>>>>>>              = field_map.get_or_insert (record_type, &existed);
>>>>>>            gcc_checking_assert (!existed);
>>>>>>            [...]
>>>>>>            for ([...])
>>>>>>              fields.put ([...], [...]);
>>>>>>            [...]
>>>>>>          }
>>>>>>        [stuff that looks up elements from 'field_map']
>>>>>>        field_map.empty ();
>>>>>>
>>>>>> This generally works.
>>>>>>
>>>>>> If I instantiate 'record_field_map_t field_map (40);', Valgrind is happy.
>>>>>> If however I instantiate 'record_field_map_t field_map (13);' (where '13'
>>>>>> would be the default for 'hash_map'), Valgrind complains:
>>>>>>
>>>>>>        2,080 bytes in 10 blocks are definitely lost in loss record 828 of 876
>>>>>>           at 0x483DD99: calloc (vg_replace_malloc.c:762)
>>>>>>           by 0x175F010: xcalloc (xmalloc.c:162)
>>>>>>           by 0xAF4A2C: hash_table<hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_entry, false, xcallocator>::hash_table(unsigned long, bool, bool, bool, mem_alloc_origin) (hash-table.h:275)
>>>>>>           by 0x15E0120: hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_map(unsigned long, bool, bool, bool) (hash-map.h:143)
>>>>>>           by 0x15DEE87: hash_map<tree_node*, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >, simple_hashmap_traits<default_hash_traits<tree_node*>, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> > > >::get_or_insert(tree_node* const&, bool*) (hash-map.h:205)
>>>>>>           by 0x15DD52C: execute_omp_oacc_neuter_broadcast() (omp-oacc-neuter-broadcast.cc:1371)
>>>>>>           [...]
>>>>>>
>>>>>> (That's with '#pragma GCC optimize "O0"' at the top of the 'gcc/*.cc'
>>>>>> file.)
>>>>>>
>>>>>> My suspicion was that it is due to the 'field_map' getting resized as it
>>>>>> incrementally grows (and '40' being big enough for that to never happen),
>>>>>> and somehow the non-POD (?) value objects not being properly handled
>>>>>> during that.  Working my way a bit through 'gcc/hash-map.*' and
>>>>>> 'gcc/hash-table.*' (but not claiming that I understand all that, off
>>>>>> hand), it seems as if my theory is right: I'm able to plug this memory
>>>>>> leak as follows:
>>>>>>
>>>>>>        --- gcc/hash-table.h
>>>>>>        +++ gcc/hash-table.h
>>>>>>        @@ -820,6 +820,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>>>>>>                 {
>>>>>>                   value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>>>>>>              new ((void*) q) value_type (std::move (x));
>>>>>>        +     //BAD Descriptor::remove (x); // (doesn't make sense and) a ton of "Invalid read [...] inside a block of size [...] free'd"
>>>>>>        +     x.~value_type (); //GOOD This seems to work!  -- but does it make sense?
>>>>>>                 }
>>>>>>
>>>>>>               p++;
>>>>>>
>>>>>> However, that doesn't exactly look like a correct fix, does it?  I'd
>>>>>> expect such a manual destructor call in combination with placement new
>>>>>> (that is being used here, obviously) -- but this is after 'std::move'?
>>>>>> However, this also survives a smoke-test-like run of parts of the GCC
>>>>>> testsuite, bootstrap and complete run now ongoing.
>>>>>
>>>>> If explicitly calling the dtor on the moved object is the right thing
>>>>> to do I'd expect to see such invocations elsewhere in hash_table but
>>>>> I don't.  It does seem like removed elements ought to be destroyed,
>>>>> but it also seems like the destruction should go through some traits
>>>>> class (e.g., call Descriptor::remove and mark_deleted or do some
>>>>> similar dance), and be called from other member functions that move
>>>>> elements.
>>>>
>>>> So, we shall assume that any "real C++" use case (that is, C++ class) is
>>>> using the appropriate C++ method, that is, 'typed_delete_remove', which
>>>> does 'delete', which does destroy the C++ object, if applicable, else
>>>> 'typed_noop_remove'.
>>>>
>>>> (Shall we look into the few places that use 'typed_free_remove' via
>>>> 'free_ptr_hash', and potentially replace them with 'typed_delete_remove'?
>>>> Or is there a reason for the two schemes to co-exist, other than for
>>>> legacy reasons?  Anyway, that's for another day.)
>>>
>>> I find all these these traits pretty much impenetrable.
>>
>> (Indeed.  ... which triggered this reflex with me, to try simplifying
>> this by getting rid of 'typed_free_remove' etc...)
>>
>>> I guess
>>> intuitively, I'd expect Descriptor::remove() to destroy an element,
>>> but I have no idea if that would be right given the design.
>>
>> So 'typed_delete_remove' does destruct via 'delete'.  'typed_free_remove'
>> doesn't -- but is only used via 'free_ptr_hash', where this isn't
>> relevant?  'typed_noop_remove' I haven't considered yet regarding that
>> issue.  Anyway, that's all for another day.
>>
>>>> What is different in the 'hash_table::expand' case is that all the Value
>>>> objects do get 'std::move'd into a new blob of memory via placement new
>>>> (so a subsequent 'delete' via 'typed_delete_remove' is not appropriate),
>>>> but then the stale Value objects never get destructed.  And indeed an
>>>> explicit destructor call (which, as I understand is a no-op for primitive
>>>> types; "pseudo destructor") is the right thing to do; see
>>>> <https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
>>>> and others, for example.  (Therefore, I don't think this needs to be
>>>> routed through a "traits" function, but can rather be done in-line here,
>>>> after each placement new, before deallocation of the original blob of
>>>> memory.  Also, I argue it's the right thing to do also for 'm_ggc',
>>>> because even if in that case we're not going to leak memory (GC will
>>>> reclaim), but we still may leak other resources dynamically allocated in
>>>> a non-trivial constructor.)
>>>
>>> Yes, of course, all elements need to be eventually be destroyed.
>>> My only hesitation was whether it should be done via one of these
>>> traits classes (like it's done in C++ containers via allocators)
>>> rather than directly
>>
>> Given that there is (apparently) no issue to do a placement new in
>> 'hash_table::expand', I'd asumme a -- corresponding -- explicit
>> destructor call would be likewise appropriate?  (But I'll of course route
>> this through a (new) "traits" function if someone explains why this is
>> the right thing to do.)
>>
>>> and whether there might be other places
>>> where the destruction night need to happen.
>>
>> (Possibly, yes, per discussion above -- but that's a separate issue?)
>>
>>>> The attached "Fix 'hash_table::expand' to destruct stale Value objects"
>>>> does prevent my original problem, does address the current 'class2loc'
>>>> memory leak in 'cp/parser.c' (see commit log for one example), and
>>>> adjusts the new
>>>> 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' test
>>>> case such that number of constructor calls matches the number of
>>>> destructor calls.  After some careful review regarding C++ details
>>>> (please!), OK to push to master branch?  (Also cherry-pick into release
>>>> branches, eventually?)  Is the source code comment that I'm adding
>>>> sufficiently explanatory and correct in C++ terms?
>>
>> Ping.
>>
>>> Shouldn't the hash_table dtor (and perhaps also empty())  also
>>> destroy the elements?  (Otherwise, what destroys the elements
>>> newly constructed here, or anywhere else for that matter, such
>>> as in the hash_table ctor?)
>>
>> Per my understanding, per discussion above, they (eventually) do get
>> destroyed via 'delete' in 'typed_delete_remove', for example, via
>> 'Descriptor::remove' calls for all/relevant entries in
>> 'hash_table::~hash_table', 'hash_table::empty_slow',
>> 'hash_table::clear_slot', 'hash_table::remove_elt_with_hash'.
>>
>> (This means that if there has been an intermediate 'expand', this may
>> (eventually) destroy objects at a different memory location from where
>> they originally have been created -- but that's fine.)
>>
>> The 'expand' case itself is different: any (live) entries are *moved*
>> into a new storage memory object via placement new.  (And then the
>> hollow entries in the old storage memory object linger.)
>>
>>> Also, shouldn't the destroyed slot be marked either deleted or
>>> empty?)
>>
>> Per my understanding, irrelevant in 'expand': working through 'oentries',
>> the *move* is only done 'if (!is_empty (x) && !is_deleted (x))' (so
>> combined with the item above, there is no memory leak for any entries
>> that have already been 'remove'd -- they have already been destructed),
>> and the whole (old) storage memory object will be deallocated right after
>> the 'oentries' loop.
>>
>>
>>> (Sorry, I realize I have more questions than answers.)
>>
>> No worries, happens to me most of the times!  Thanks for looking into
>> this.
>>
>>
>> Grüße
>>   Thomas


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-hash_table-expand-to-destruct-stale-Value-object.patch --]
[-- Type: text/x-diff, Size: 17345 bytes --]

From 2275962abd72acd1636d438d1cb176bbabdcef06 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 18:03:38 +0200
Subject: [PATCH] Fix 'hash_table::expand' to destruct stale Value objects

Thus plugging potentional memory leaks if these have non-trivial
constructor/destructor.

See
<https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
and others.

As one example, compilation of 'g++.dg/warn/Wmismatched-tags.C' per
'valgrind --leak-check=full' improves as follows:

     [...]
    -
    -104 bytes in 1 blocks are definitely lost in loss record 399 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA43C71: cp_parser_parameter_declaration(cp_parser*, int, bool, bool*) (parser.c:24242)
    -
    -168 bytes in 3 blocks are definitely lost in loss record 422 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA53385: cp_parser_single_declaration(cp_parser*, vec<deferred_access_check, va_gc, vl_embed>*, bool, bool, bool*) (parser.c:31072)
    -
    -488 bytes in 7 blocks are definitely lost in loss record 449 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA49508: cp_parser_member_declaration(cp_parser*) (parser.c:26440)
    -
    -728 bytes in 7 blocks are definitely lost in loss record 455 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA57508: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32980)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -   by 0xA47D76: cp_parser_class_specifier(cp_parser*) (parser.c:25680)
    -   by 0xA37E27: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18912)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -
    -832 bytes in 8 blocks are definitely lost in loss record 458 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -
    -1,144 bytes in 11 blocks are definitely lost in loss record 466 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -
    -1,376 bytes in 10 blocks are definitely lost in loss record 467 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA301E0: cp_parser_simple_declaration(cp_parser*, bool, tree_node**) (parser.c:14772)
    -
    -3,552 bytes in 33 blocks are definitely lost in loss record 483 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA8964A: class_decl_loc_t::class_decl_loc_t(class_decl_loc_t const&) (parser.c:32689)
    -   by 0xA8F515: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::expand() (hash-table.h:839)
    -   by 0xA8D4B3: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::find_slot_with_hash(tree_node* const&, unsigned int, insert_option) (hash-table.h:1008)
    -   by 0xA8B1DC: hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::get_or_insert(tree_node* const&, bool*) (hash-map.h:200)
    -   by 0xA57128: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32888)
     [...]
     LEAK SUMMARY:
    -   definitely lost: 8,440 bytes in 81 blocks
    +   definitely lost: 48 bytes in 1 blocks
        indirectly lost: 12,529 bytes in 329 blocks
          possibly lost: 0 bytes in 0 blocks
        still reachable: 1,644,376 bytes in 768 blocks

	gcc/
	* hash-table.h (hash_table<Descriptor, Lazy, Allocator>::expand):
	Destruct stale Value objects.
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor_expand):
	Update.
---
 gcc/hash-map-tests.c | 10 ++++++----
 gcc/hash-table.h     |  4 ++++
 2 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 6acc0d4337e..511d4342087 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -305,31 +305,32 @@ test_map_of_type_with_ctor_and_dtor ()
 	m.get_or_insert (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, i);
 
 	m.remove (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, 1 + i);
       }
   }
 }
 
-/* Verify aspects of 'hash_table::expand'.  */
+/* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
+   Value objects.  */
 
 static void
 test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 {
   /* Configure, so that hash table expansion triggers a few times.  */
   const size_t N_init = 0;
   const int N_elem = 70;
   size_t expand_c_expected = 4;
   size_t expand_c = 0;
 
   /* For stability of this testing, we need all Key values 'k' to produce
      unique hash values 'Traits::hash (k)', as otherwise the dynamic
      insert/remove behavior may diverge across different architectures.  This
      is, for example, a problem when using the standard 'pointer_hash::hash',
      which is simply doing a 'k >> 3' operation, which is fine on 64-bit
@@ -388,69 +389,70 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 	    unsigned int nindex = hash_table_higher_prime_index (elts * 2);
 	    m_size = prime_tab[nindex].prime;
 	  }
 	  m_n_deleted = 0;
 
 	  /* All non-deleted elements have been moved.  */
 	  n_expand_moved += i;
 	  if (remove_some_inline)
 	    n_expand_moved -= (i + 2) / 3;
 	}
 
       ASSERT_EQ (val_t::ndefault, 1 + i);
       ASSERT_EQ (val_t::ncopy, n_expand_moved);
       ASSERT_EQ (val_t::nassign, 0);
       if (remove_some_inline)
-	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
       else
-	ASSERT_EQ (val_t::ndtor, 0);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved);
 
       /* Remove some inline.  This never triggers an 'expand' here, but via
 	 'm_n_deleted' does influence any following one.  */
       if (remove_some_inline
 	  && !(i % 3))
 	{
 	  m.remove (a[i]);
 	  /* Per 'hash_table::remove_elt_with_hash'.  */
 	  m_n_deleted++;
 
 	  ASSERT_EQ (val_t::ndefault, 1 + i);
 	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
 	  ASSERT_EQ (val_t::nassign, 0);
-	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	  ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
 	}
     }
   ASSERT_EQ (expand_c, expand_c_expected);
 
   int ndefault = val_t::ndefault;
   int ncopy = val_t::ncopy;
   int nassign = val_t::nassign;
   int ndtor = val_t::ndtor;
 
   for (int i = 0; i < N_elem; ++i)
     {
       if (remove_some_inline
 	  && !(i % 3))
 	continue;
 
       m.remove (a[i]);
       ++ndtor;
       ASSERT_EQ (val_t::ndefault, ndefault);
       ASSERT_EQ (val_t::ncopy, ncopy);
       ASSERT_EQ (val_t::nassign, nassign);
       ASSERT_EQ (val_t::ndtor, ndtor);
     }
+  ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
    "empty" value.  */
 
 static void
 test_nonzero_empty_key ()
 {
   typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
   hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
 
   for (int i = 1; i != 32; ++i)
     x.put (i, i);
 
   ASSERT_EQ (x.get (0), NULL);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index a6e0ac8eea9..8c2a0589fbd 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -808,30 +808,34 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
   m_entries = nentries;
   m_size = nsize;
   m_size_prime_index = nindex;
   m_n_elements -= m_n_deleted;
   m_n_deleted = 0;
 
   value_type *p = oentries;
   do
     {
       value_type &x = *p;
 
       if (!is_empty (x) && !is_deleted (x))
         {
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 	  new ((void*) q) value_type (std::move (x));
+
+	  /* Manually invoke destructor of original object, to counterbalance
+	     object constructed via placement new.  */
+	  x.~value_type ();
         }
 
       p++;
     }
   while (p < olimit);
 
   if (!m_ggc)
     Allocator <value_type> ::data_free (oentries);
   else
     ggc_free (oentries);
 }
 
 /* Implements empty() in cases where it isn't a no-op.  */
 
 template<typename Descriptor, bool Lazy,
-- 
2.30.2

[PING^2] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 14287 bytes --]

Hi!

On 2021-09-10T10:00:25+0200, I wrote:
> On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
>>> Ping -- we still need to plug the memory leak; see patch attached, and/or
>>> long discussion here:
>>
>> Thanks for answering my questions.  I have no concerns with going
>> forward with the patch as is.
>
> Thanks, Martin.  Ping for formal approval (and review for using proper
> C++ terminology in the 'gcc/hash-table.h:hash_table::expand' source code
> comment that I'm adding).  Patch again attached, for easy reference.

Ping, once again.


Grüße
 Thomas


>> Just a suggestion/request: unless
>> this patch fixes all the outstanding problems you know of or suspect
>> in this area (leaks/missing dtor calls) and unless you plan to work
>> on those in the near future, please open a bug for them with a brain
>> dump of what you learned.  That should save us time when the day
>> comes to tackle those.
>
> ACK.  I'm not aware of any additional known problems.  (In our email
> discussion, we did have some "vague ideas" for opportunities of
> clarification/clean-up, but these aren't worth filing PRs for; needs
> someone to gain understanding, taking a look.)
>
>
> Grüße
>  Thomas
>
>
>>> On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
>>>> On 8/16/21 6:44 AM, Thomas Schwinge wrote:
>>>>> On 2021-08-12T17:15:44-0600, Martin Sebor via Gcc <gcc@gcc.gnu.org> wrote:
>>>>>> On 8/6/21 10:57 AM, Thomas Schwinge wrote:
>>>>>>> So I'm trying to do some C++...  ;-)
>>>>>>>
>>>>>>> Given:
>>>>>>>
>>>>>>>        /* A map from SSA names or var decls to record fields.  */
>>>>>>>        typedef hash_map<tree, tree> field_map_t;
>>>>>>>
>>>>>>>        /* For each propagation record type, this is a map from SSA names or var decls
>>>>>>>           to propagate, to the field in the record type that should be used for
>>>>>>>           transmission and reception.  */
>>>>>>>        typedef hash_map<tree, field_map_t> record_field_map_t;
>>>>>>>
>>>>>>> Thus, that's a 'hash_map<tree, hash_map<tree, tree>>'.  (I may do that,
>>>>>>> right?)  Looking through GCC implementation files, very most of all uses
>>>>>>> of 'hash_map' boil down to pointer key ('tree', for example) and
>>>>>>> pointer/integer value.
>>>>>>
>>>>>> Right.  Because most GCC containers rely exclusively on GCC's own
>>>>>> uses for testing, if your use case is novel in some way, chances
>>>>>> are it might not work as intended in all circumstances.
>>>>>>
>>>>>> I've wrestled with hash_map a number of times.  A use case that's
>>>>>> close to yours (i.e., a non-trivial value type) is in cp/parser.c:
>>>>>> see class_to_loc_map_t.
>>>>>
>>>>> Indeed, at the time you sent this email, I already had started looking
>>>>> into that one!  (The Fortran test cases that I originally analyzed, which
>>>>> triggered other cases of non-POD/non-trivial destructor, all didn't
>>>>> result in a memory leak, because the non-trivial constructor doesn't
>>>>> actually allocate any resources dynamically -- that's indeed different in
>>>>> this case here.)  ..., and indeed:
>>>>>
>>>>>> (I don't remember if I tested it for leaks
>>>>>> though.  It's used to implement -Wmismatched-tags so compiling
>>>>>> a few tests under Valgrind should show if it does leak.)
>>>>>
>>>>> ... it does leak memory at present.  :-| (See attached commit log for
>>>>> details for one example.)
>>>
>>> (Attached "Fix 'hash_table::expand' to destruct stale Value objects"
>>> again.)
>>>
>>>>> To that effect, to document the current behavior, I propose to
>>>>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>>>>> constructor/destructor"
>>>
>>> (We've done that in commit e4f16e9f357a38ec702fb69a0ffab9d292a6af9b
>>> "Add more self-tests for 'hash_map' with Value type with non-trivial
>>> constructor/destructor", quickly followed by bug fix
>>> commit bb04a03c6f9bacc890118b9e12b657503093c2f8
>>> "Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand'
>>> work on 32-bit architectures [PR101959]".
>>>
>>>>> (Also cherry-pick into release branches, eventually?)
>>>
>>>>>>> Then:
>>>>>>>
>>>>>>>        record_field_map_t field_map ([...]); // see below
>>>>>>>        for ([...])
>>>>>>>          {
>>>>>>>            tree record_type = [...];
>>>>>>>            [...]
>>>>>>>            bool existed;
>>>>>>>            field_map_t &fields
>>>>>>>              = field_map.get_or_insert (record_type, &existed);
>>>>>>>            gcc_checking_assert (!existed);
>>>>>>>            [...]
>>>>>>>            for ([...])
>>>>>>>              fields.put ([...], [...]);
>>>>>>>            [...]
>>>>>>>          }
>>>>>>>        [stuff that looks up elements from 'field_map']
>>>>>>>        field_map.empty ();
>>>>>>>
>>>>>>> This generally works.
>>>>>>>
>>>>>>> If I instantiate 'record_field_map_t field_map (40);', Valgrind is happy.
>>>>>>> If however I instantiate 'record_field_map_t field_map (13);' (where '13'
>>>>>>> would be the default for 'hash_map'), Valgrind complains:
>>>>>>>
>>>>>>>        2,080 bytes in 10 blocks are definitely lost in loss record 828 of 876
>>>>>>>           at 0x483DD99: calloc (vg_replace_malloc.c:762)
>>>>>>>           by 0x175F010: xcalloc (xmalloc.c:162)
>>>>>>>           by 0xAF4A2C: hash_table<hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_entry, false, xcallocator>::hash_table(unsigned long, bool, bool, bool, mem_alloc_origin) (hash-table.h:275)
>>>>>>>           by 0x15E0120: hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_map(unsigned long, bool, bool, bool) (hash-map.h:143)
>>>>>>>           by 0x15DEE87: hash_map<tree_node*, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >, simple_hashmap_traits<default_hash_traits<tree_node*>, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> > > >::get_or_insert(tree_node* const&, bool*) (hash-map.h:205)
>>>>>>>           by 0x15DD52C: execute_omp_oacc_neuter_broadcast() (omp-oacc-neuter-broadcast.cc:1371)
>>>>>>>           [...]
>>>>>>>
>>>>>>> (That's with '#pragma GCC optimize "O0"' at the top of the 'gcc/*.cc'
>>>>>>> file.)
>>>>>>>
>>>>>>> My suspicion was that it is due to the 'field_map' getting resized as it
>>>>>>> incrementally grows (and '40' being big enough for that to never happen),
>>>>>>> and somehow the non-POD (?) value objects not being properly handled
>>>>>>> during that.  Working my way a bit through 'gcc/hash-map.*' and
>>>>>>> 'gcc/hash-table.*' (but not claiming that I understand all that, off
>>>>>>> hand), it seems as if my theory is right: I'm able to plug this memory
>>>>>>> leak as follows:
>>>>>>>
>>>>>>>        --- gcc/hash-table.h
>>>>>>>        +++ gcc/hash-table.h
>>>>>>>        @@ -820,6 +820,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>>>>>>>                 {
>>>>>>>                   value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>>>>>>>              new ((void*) q) value_type (std::move (x));
>>>>>>>        +     //BAD Descriptor::remove (x); // (doesn't make sense and) a ton of "Invalid read [...] inside a block of size [...] free'd"
>>>>>>>        +     x.~value_type (); //GOOD This seems to work!  -- but does it make sense?
>>>>>>>                 }
>>>>>>>
>>>>>>>               p++;
>>>>>>>
>>>>>>> However, that doesn't exactly look like a correct fix, does it?  I'd
>>>>>>> expect such a manual destructor call in combination with placement new
>>>>>>> (that is being used here, obviously) -- but this is after 'std::move'?
>>>>>>> However, this also survives a smoke-test-like run of parts of the GCC
>>>>>>> testsuite, bootstrap and complete run now ongoing.
>>>>>>
>>>>>> If explicitly calling the dtor on the moved object is the right thing
>>>>>> to do I'd expect to see such invocations elsewhere in hash_table but
>>>>>> I don't.  It does seem like removed elements ought to be destroyed,
>>>>>> but it also seems like the destruction should go through some traits
>>>>>> class (e.g., call Descriptor::remove and mark_deleted or do some
>>>>>> similar dance), and be called from other member functions that move
>>>>>> elements.
>>>>>
>>>>> So, we shall assume that any "real C++" use case (that is, C++ class) is
>>>>> using the appropriate C++ method, that is, 'typed_delete_remove', which
>>>>> does 'delete', which does destroy the C++ object, if applicable, else
>>>>> 'typed_noop_remove'.
>>>>>
>>>>> (Shall we look into the few places that use 'typed_free_remove' via
>>>>> 'free_ptr_hash', and potentially replace them with 'typed_delete_remove'?
>>>>> Or is there a reason for the two schemes to co-exist, other than for
>>>>> legacy reasons?  Anyway, that's for another day.)
>>>>
>>>> I find all these these traits pretty much impenetrable.
>>>
>>> (Indeed.  ... which triggered this reflex with me, to try simplifying
>>> this by getting rid of 'typed_free_remove' etc...)
>>>
>>>> I guess
>>>> intuitively, I'd expect Descriptor::remove() to destroy an element,
>>>> but I have no idea if that would be right given the design.
>>>
>>> So 'typed_delete_remove' does destruct via 'delete'.  'typed_free_remove'
>>> doesn't -- but is only used via 'free_ptr_hash', where this isn't
>>> relevant?  'typed_noop_remove' I haven't considered yet regarding that
>>> issue.  Anyway, that's all for another day.
>>>
>>>>> What is different in the 'hash_table::expand' case is that all the Value
>>>>> objects do get 'std::move'd into a new blob of memory via placement new
>>>>> (so a subsequent 'delete' via 'typed_delete_remove' is not appropriate),
>>>>> but then the stale Value objects never get destructed.  And indeed an
>>>>> explicit destructor call (which, as I understand is a no-op for primitive
>>>>> types; "pseudo destructor") is the right thing to do; see
>>>>> <https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
>>>>> and others, for example.  (Therefore, I don't think this needs to be
>>>>> routed through a "traits" function, but can rather be done in-line here,
>>>>> after each placement new, before deallocation of the original blob of
>>>>> memory.  Also, I argue it's the right thing to do also for 'm_ggc',
>>>>> because even if in that case we're not going to leak memory (GC will
>>>>> reclaim), but we still may leak other resources dynamically allocated in
>>>>> a non-trivial constructor.)
>>>>
>>>> Yes, of course, all elements need to be eventually be destroyed.
>>>> My only hesitation was whether it should be done via one of these
>>>> traits classes (like it's done in C++ containers via allocators)
>>>> rather than directly
>>>
>>> Given that there is (apparently) no issue to do a placement new in
>>> 'hash_table::expand', I'd asumme a -- corresponding -- explicit
>>> destructor call would be likewise appropriate?  (But I'll of course route
>>> this through a (new) "traits" function if someone explains why this is
>>> the right thing to do.)
>>>
>>>> and whether there might be other places
>>>> where the destruction night need to happen.
>>>
>>> (Possibly, yes, per discussion above -- but that's a separate issue?)
>>>
>>>>> The attached "Fix 'hash_table::expand' to destruct stale Value objects"
>>>>> does prevent my original problem, does address the current 'class2loc'
>>>>> memory leak in 'cp/parser.c' (see commit log for one example), and
>>>>> adjusts the new
>>>>> 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' test
>>>>> case such that number of constructor calls matches the number of
>>>>> destructor calls.  After some careful review regarding C++ details
>>>>> (please!), OK to push to master branch?  (Also cherry-pick into release
>>>>> branches, eventually?)  Is the source code comment that I'm adding
>>>>> sufficiently explanatory and correct in C++ terms?
>>>
>>> Ping.
>>>
>>>> Shouldn't the hash_table dtor (and perhaps also empty())  also
>>>> destroy the elements?  (Otherwise, what destroys the elements
>>>> newly constructed here, or anywhere else for that matter, such
>>>> as in the hash_table ctor?)
>>>
>>> Per my understanding, per discussion above, they (eventually) do get
>>> destroyed via 'delete' in 'typed_delete_remove', for example, via
>>> 'Descriptor::remove' calls for all/relevant entries in
>>> 'hash_table::~hash_table', 'hash_table::empty_slow',
>>> 'hash_table::clear_slot', 'hash_table::remove_elt_with_hash'.
>>>
>>> (This means that if there has been an intermediate 'expand', this may
>>> (eventually) destroy objects at a different memory location from where
>>> they originally have been created -- but that's fine.)
>>>
>>> The 'expand' case itself is different: any (live) entries are *moved*
>>> into a new storage memory object via placement new.  (And then the
>>> hollow entries in the old storage memory object linger.)
>>>
>>>> Also, shouldn't the destroyed slot be marked either deleted or
>>>> empty?)
>>>
>>> Per my understanding, irrelevant in 'expand': working through 'oentries',
>>> the *move* is only done 'if (!is_empty (x) && !is_deleted (x))' (so
>>> combined with the item above, there is no memory leak for any entries
>>> that have already been 'remove'd -- they have already been destructed),
>>> and the whole (old) storage memory object will be deallocated right after
>>> the 'oentries' loop.
>>>
>>>
>>>> (Sorry, I realize I have more questions than answers.)
>>>
>>> No worries, happens to me most of the times!  Thanks for looking into
>>> this.
>>>
>>>
>>> Grüße
>>>   Thomas


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-hash_table-expand-to-destruct-stale-Value-object.patch --]
[-- Type: text/x-diff, Size: 17345 bytes --]

From 2275962abd72acd1636d438d1cb176bbabdcef06 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 18:03:38 +0200
Subject: [PATCH] Fix 'hash_table::expand' to destruct stale Value objects

Thus plugging potentional memory leaks if these have non-trivial
constructor/destructor.

See
<https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
and others.

As one example, compilation of 'g++.dg/warn/Wmismatched-tags.C' per
'valgrind --leak-check=full' improves as follows:

     [...]
    -
    -104 bytes in 1 blocks are definitely lost in loss record 399 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA43C71: cp_parser_parameter_declaration(cp_parser*, int, bool, bool*) (parser.c:24242)
    -
    -168 bytes in 3 blocks are definitely lost in loss record 422 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA53385: cp_parser_single_declaration(cp_parser*, vec<deferred_access_check, va_gc, vl_embed>*, bool, bool, bool*) (parser.c:31072)
    -
    -488 bytes in 7 blocks are definitely lost in loss record 449 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA49508: cp_parser_member_declaration(cp_parser*) (parser.c:26440)
    -
    -728 bytes in 7 blocks are definitely lost in loss record 455 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA57508: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32980)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -   by 0xA47D76: cp_parser_class_specifier(cp_parser*) (parser.c:25680)
    -   by 0xA37E27: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18912)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -
    -832 bytes in 8 blocks are definitely lost in loss record 458 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -
    -1,144 bytes in 11 blocks are definitely lost in loss record 466 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -
    -1,376 bytes in 10 blocks are definitely lost in loss record 467 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA301E0: cp_parser_simple_declaration(cp_parser*, bool, tree_node**) (parser.c:14772)
    -
    -3,552 bytes in 33 blocks are definitely lost in loss record 483 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA8964A: class_decl_loc_t::class_decl_loc_t(class_decl_loc_t const&) (parser.c:32689)
    -   by 0xA8F515: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::expand() (hash-table.h:839)
    -   by 0xA8D4B3: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::find_slot_with_hash(tree_node* const&, unsigned int, insert_option) (hash-table.h:1008)
    -   by 0xA8B1DC: hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::get_or_insert(tree_node* const&, bool*) (hash-map.h:200)
    -   by 0xA57128: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32888)
     [...]
     LEAK SUMMARY:
    -   definitely lost: 8,440 bytes in 81 blocks
    +   definitely lost: 48 bytes in 1 blocks
        indirectly lost: 12,529 bytes in 329 blocks
          possibly lost: 0 bytes in 0 blocks
        still reachable: 1,644,376 bytes in 768 blocks

	gcc/
	* hash-table.h (hash_table<Descriptor, Lazy, Allocator>::expand):
	Destruct stale Value objects.
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor_expand):
	Update.
---
 gcc/hash-map-tests.c | 10 ++++++----
 gcc/hash-table.h     |  4 ++++
 2 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 6acc0d4337e..511d4342087 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -305,31 +305,32 @@ test_map_of_type_with_ctor_and_dtor ()
 	m.get_or_insert (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, i);
 
 	m.remove (a[i]);
 	ASSERT_EQ (val_t::ndefault, 1 + i);
 	ASSERT_EQ (val_t::ncopy, 0);
 	ASSERT_EQ (val_t::nassign, 0);
 	ASSERT_EQ (val_t::ndtor, 1 + i);
       }
   }
 }
 
-/* Verify aspects of 'hash_table::expand'.  */
+/* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
+   Value objects.  */
 
 static void
 test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 {
   /* Configure, so that hash table expansion triggers a few times.  */
   const size_t N_init = 0;
   const int N_elem = 70;
   size_t expand_c_expected = 4;
   size_t expand_c = 0;
 
   /* For stability of this testing, we need all Key values 'k' to produce
      unique hash values 'Traits::hash (k)', as otherwise the dynamic
      insert/remove behavior may diverge across different architectures.  This
      is, for example, a problem when using the standard 'pointer_hash::hash',
      which is simply doing a 'k >> 3' operation, which is fine on 64-bit
@@ -388,69 +389,70 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 	    unsigned int nindex = hash_table_higher_prime_index (elts * 2);
 	    m_size = prime_tab[nindex].prime;
 	  }
 	  m_n_deleted = 0;
 
 	  /* All non-deleted elements have been moved.  */
 	  n_expand_moved += i;
 	  if (remove_some_inline)
 	    n_expand_moved -= (i + 2) / 3;
 	}
 
       ASSERT_EQ (val_t::ndefault, 1 + i);
       ASSERT_EQ (val_t::ncopy, n_expand_moved);
       ASSERT_EQ (val_t::nassign, 0);
       if (remove_some_inline)
-	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
       else
-	ASSERT_EQ (val_t::ndtor, 0);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved);
 
       /* Remove some inline.  This never triggers an 'expand' here, but via
 	 'm_n_deleted' does influence any following one.  */
       if (remove_some_inline
 	  && !(i % 3))
 	{
 	  m.remove (a[i]);
 	  /* Per 'hash_table::remove_elt_with_hash'.  */
 	  m_n_deleted++;
 
 	  ASSERT_EQ (val_t::ndefault, 1 + i);
 	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
 	  ASSERT_EQ (val_t::nassign, 0);
-	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	  ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
 	}
     }
   ASSERT_EQ (expand_c, expand_c_expected);
 
   int ndefault = val_t::ndefault;
   int ncopy = val_t::ncopy;
   int nassign = val_t::nassign;
   int ndtor = val_t::ndtor;
 
   for (int i = 0; i < N_elem; ++i)
     {
       if (remove_some_inline
 	  && !(i % 3))
 	continue;
 
       m.remove (a[i]);
       ++ndtor;
       ASSERT_EQ (val_t::ndefault, ndefault);
       ASSERT_EQ (val_t::ncopy, ncopy);
       ASSERT_EQ (val_t::nassign, nassign);
       ASSERT_EQ (val_t::ndtor, ndtor);
     }
+  ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
    "empty" value.  */
 
 static void
 test_nonzero_empty_key ()
 {
   typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
   hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
 
   for (int i = 1; i != 32; ++i)
     x.put (i, i);
 
   ASSERT_EQ (x.get (0), NULL);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index a6e0ac8eea9..8c2a0589fbd 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -808,30 +808,34 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
   m_entries = nentries;
   m_size = nsize;
   m_size_prime_index = nindex;
   m_n_elements -= m_n_deleted;
   m_n_deleted = 0;
 
   value_type *p = oentries;
   do
     {
       value_type &x = *p;
 
       if (!is_empty (x) && !is_deleted (x))
         {
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 	  new ((void*) q) value_type (std::move (x));
+
+	  /* Manually invoke destructor of original object, to counterbalance
+	     object constructed via placement new.  */
+	  x.~value_type ();
         }
 
       p++;
     }
   while (p < olimit);
 
   if (!m_ggc)
     Allocator <value_type> ::data_free (oentries);
   else
     ggc_free (oentries);
 }
 
 /* Implements empty() in cases where it isn't a no-op.  */
 
 template<typename Descriptor, bool Lazy,
-- 
2.30.2

Re: [PING^2] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Richard Biener]

On Fri, Sep 17, 2021 at 1:17 PM Thomas Schwinge <thomas@codesourcery.com> wrote:
>
> Hi!
>
> On 2021-09-10T10:00:25+0200, I wrote:
> > On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> >> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
> >>> Ping -- we still need to plug the memory leak; see patch attached, and/or
> >>> long discussion here:
> >>
> >> Thanks for answering my questions.  I have no concerns with going
> >> forward with the patch as is.
> >
> > Thanks, Martin.  Ping for formal approval (and review for using proper
> > C++ terminology in the 'gcc/hash-table.h:hash_table::expand' source code
> > comment that I'm adding).  Patch again attached, for easy reference.
>
> Ping, once again.

I'm happy when a C++ literate approves the main change which I quote as

          new ((void*) q) value_type (std::move (x));
+
+         /* Manually invoke destructor of original object, to counterbalance
+            object constructed via placement new.  */
+         x.~value_type ();

but I had the impression that std::move already "moves away" from the source?
That said, the dance above looks iffy, there must be a nicer way to "move"
an object in C++?

What happens if the dtor is deleted btw?  Shouldn't you use sth
like a placement 'delete' instead of invoking a DTOR?

But the above clearly shows I know nothing of C++ :P

Richard.

>
> Grüße
>  Thomas
>
>
> >> Just a suggestion/request: unless
> >> this patch fixes all the outstanding problems you know of or suspect
> >> in this area (leaks/missing dtor calls) and unless you plan to work
> >> on those in the near future, please open a bug for them with a brain
> >> dump of what you learned.  That should save us time when the day
> >> comes to tackle those.
> >
> > ACK.  I'm not aware of any additional known problems.  (In our email
> > discussion, we did have some "vague ideas" for opportunities of
> > clarification/clean-up, but these aren't worth filing PRs for; needs
> > someone to gain understanding, taking a look.)
> >
> >
> > Grüße
> >  Thomas
> >
> >
> >>> On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> wrote:
> >>>> On 8/16/21 6:44 AM, Thomas Schwinge wrote:
> >>>>> On 2021-08-12T17:15:44-0600, Martin Sebor via Gcc <gcc@gcc.gnu.org> wrote:
> >>>>>> On 8/6/21 10:57 AM, Thomas Schwinge wrote:
> >>>>>>> So I'm trying to do some C++...  ;-)
> >>>>>>>
> >>>>>>> Given:
> >>>>>>>
> >>>>>>>        /* A map from SSA names or var decls to record fields.  */
> >>>>>>>        typedef hash_map<tree, tree> field_map_t;
> >>>>>>>
> >>>>>>>        /* For each propagation record type, this is a map from SSA names or var decls
> >>>>>>>           to propagate, to the field in the record type that should be used for
> >>>>>>>           transmission and reception.  */
> >>>>>>>        typedef hash_map<tree, field_map_t> record_field_map_t;
> >>>>>>>
> >>>>>>> Thus, that's a 'hash_map<tree, hash_map<tree, tree>>'.  (I may do that,
> >>>>>>> right?)  Looking through GCC implementation files, very most of all uses
> >>>>>>> of 'hash_map' boil down to pointer key ('tree', for example) and
> >>>>>>> pointer/integer value.
> >>>>>>
> >>>>>> Right.  Because most GCC containers rely exclusively on GCC's own
> >>>>>> uses for testing, if your use case is novel in some way, chances
> >>>>>> are it might not work as intended in all circumstances.
> >>>>>>
> >>>>>> I've wrestled with hash_map a number of times.  A use case that's
> >>>>>> close to yours (i.e., a non-trivial value type) is in cp/parser.c:
> >>>>>> see class_to_loc_map_t.
> >>>>>
> >>>>> Indeed, at the time you sent this email, I already had started looking
> >>>>> into that one!  (The Fortran test cases that I originally analyzed, which
> >>>>> triggered other cases of non-POD/non-trivial destructor, all didn't
> >>>>> result in a memory leak, because the non-trivial constructor doesn't
> >>>>> actually allocate any resources dynamically -- that's indeed different in
> >>>>> this case here.)  ..., and indeed:
> >>>>>
> >>>>>> (I don't remember if I tested it for leaks
> >>>>>> though.  It's used to implement -Wmismatched-tags so compiling
> >>>>>> a few tests under Valgrind should show if it does leak.)
> >>>>>
> >>>>> ... it does leak memory at present.  :-| (See attached commit log for
> >>>>> details for one example.)
> >>>
> >>> (Attached "Fix 'hash_table::expand' to destruct stale Value objects"
> >>> again.)
> >>>
> >>>>> To that effect, to document the current behavior, I propose to
> >>>>> "Add more self-tests for 'hash_map' with Value type with non-trivial
> >>>>> constructor/destructor"
> >>>
> >>> (We've done that in commit e4f16e9f357a38ec702fb69a0ffab9d292a6af9b
> >>> "Add more self-tests for 'hash_map' with Value type with non-trivial
> >>> constructor/destructor", quickly followed by bug fix
> >>> commit bb04a03c6f9bacc890118b9e12b657503093c2f8
> >>> "Make 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand'
> >>> work on 32-bit architectures [PR101959]".
> >>>
> >>>>> (Also cherry-pick into release branches, eventually?)
> >>>
> >>>>>>> Then:
> >>>>>>>
> >>>>>>>        record_field_map_t field_map ([...]); // see below
> >>>>>>>        for ([...])
> >>>>>>>          {
> >>>>>>>            tree record_type = [...];
> >>>>>>>            [...]
> >>>>>>>            bool existed;
> >>>>>>>            field_map_t &fields
> >>>>>>>              = field_map.get_or_insert (record_type, &existed);
> >>>>>>>            gcc_checking_assert (!existed);
> >>>>>>>            [...]
> >>>>>>>            for ([...])
> >>>>>>>              fields.put ([...], [...]);
> >>>>>>>            [...]
> >>>>>>>          }
> >>>>>>>        [stuff that looks up elements from 'field_map']
> >>>>>>>        field_map.empty ();
> >>>>>>>
> >>>>>>> This generally works.
> >>>>>>>
> >>>>>>> If I instantiate 'record_field_map_t field_map (40);', Valgrind is happy.
> >>>>>>> If however I instantiate 'record_field_map_t field_map (13);' (where '13'
> >>>>>>> would be the default for 'hash_map'), Valgrind complains:
> >>>>>>>
> >>>>>>>        2,080 bytes in 10 blocks are definitely lost in loss record 828 of 876
> >>>>>>>           at 0x483DD99: calloc (vg_replace_malloc.c:762)
> >>>>>>>           by 0x175F010: xcalloc (xmalloc.c:162)
> >>>>>>>           by 0xAF4A2C: hash_table<hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_entry, false, xcallocator>::hash_table(unsigned long, bool, bool, bool, mem_alloc_origin) (hash-table.h:275)
> >>>>>>>           by 0x15E0120: hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >::hash_map(unsigned long, bool, bool, bool) (hash-map.h:143)
> >>>>>>>           by 0x15DEE87: hash_map<tree_node*, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> >, simple_hashmap_traits<default_hash_traits<tree_node*>, hash_map<tree_node*, tree_node*, simple_hashmap_traits<default_hash_traits<tree_node*>, tree_node*> > > >::get_or_insert(tree_node* const&, bool*) (hash-map.h:205)
> >>>>>>>           by 0x15DD52C: execute_omp_oacc_neuter_broadcast() (omp-oacc-neuter-broadcast.cc:1371)
> >>>>>>>           [...]
> >>>>>>>
> >>>>>>> (That's with '#pragma GCC optimize "O0"' at the top of the 'gcc/*.cc'
> >>>>>>> file.)
> >>>>>>>
> >>>>>>> My suspicion was that it is due to the 'field_map' getting resized as it
> >>>>>>> incrementally grows (and '40' being big enough for that to never happen),
> >>>>>>> and somehow the non-POD (?) value objects not being properly handled
> >>>>>>> during that.  Working my way a bit through 'gcc/hash-map.*' and
> >>>>>>> 'gcc/hash-table.*' (but not claiming that I understand all that, off
> >>>>>>> hand), it seems as if my theory is right: I'm able to plug this memory
> >>>>>>> leak as follows:
> >>>>>>>
> >>>>>>>        --- gcc/hash-table.h
> >>>>>>>        +++ gcc/hash-table.h
> >>>>>>>        @@ -820,6 +820,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
> >>>>>>>                 {
> >>>>>>>                   value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
> >>>>>>>              new ((void*) q) value_type (std::move (x));
> >>>>>>>        +     //BAD Descriptor::remove (x); // (doesn't make sense and) a ton of "Invalid read [...] inside a block of size [...] free'd"
> >>>>>>>        +     x.~value_type (); //GOOD This seems to work!  -- but does it make sense?
> >>>>>>>                 }
> >>>>>>>
> >>>>>>>               p++;
> >>>>>>>
> >>>>>>> However, that doesn't exactly look like a correct fix, does it?  I'd
> >>>>>>> expect such a manual destructor call in combination with placement new
> >>>>>>> (that is being used here, obviously) -- but this is after 'std::move'?
> >>>>>>> However, this also survives a smoke-test-like run of parts of the GCC
> >>>>>>> testsuite, bootstrap and complete run now ongoing.
> >>>>>>
> >>>>>> If explicitly calling the dtor on the moved object is the right thing
> >>>>>> to do I'd expect to see such invocations elsewhere in hash_table but
> >>>>>> I don't.  It does seem like removed elements ought to be destroyed,
> >>>>>> but it also seems like the destruction should go through some traits
> >>>>>> class (e.g., call Descriptor::remove and mark_deleted or do some
> >>>>>> similar dance), and be called from other member functions that move
> >>>>>> elements.
> >>>>>
> >>>>> So, we shall assume that any "real C++" use case (that is, C++ class) is
> >>>>> using the appropriate C++ method, that is, 'typed_delete_remove', which
> >>>>> does 'delete', which does destroy the C++ object, if applicable, else
> >>>>> 'typed_noop_remove'.
> >>>>>
> >>>>> (Shall we look into the few places that use 'typed_free_remove' via
> >>>>> 'free_ptr_hash', and potentially replace them with 'typed_delete_remove'?
> >>>>> Or is there a reason for the two schemes to co-exist, other than for
> >>>>> legacy reasons?  Anyway, that's for another day.)
> >>>>
> >>>> I find all these these traits pretty much impenetrable.
> >>>
> >>> (Indeed.  ... which triggered this reflex with me, to try simplifying
> >>> this by getting rid of 'typed_free_remove' etc...)
> >>>
> >>>> I guess
> >>>> intuitively, I'd expect Descriptor::remove() to destroy an element,
> >>>> but I have no idea if that would be right given the design.
> >>>
> >>> So 'typed_delete_remove' does destruct via 'delete'.  'typed_free_remove'
> >>> doesn't -- but is only used via 'free_ptr_hash', where this isn't
> >>> relevant?  'typed_noop_remove' I haven't considered yet regarding that
> >>> issue.  Anyway, that's all for another day.
> >>>
> >>>>> What is different in the 'hash_table::expand' case is that all the Value
> >>>>> objects do get 'std::move'd into a new blob of memory via placement new
> >>>>> (so a subsequent 'delete' via 'typed_delete_remove' is not appropriate),
> >>>>> but then the stale Value objects never get destructed.  And indeed an
> >>>>> explicit destructor call (which, as I understand is a no-op for primitive
> >>>>> types; "pseudo destructor") is the right thing to do; see
> >>>>> <https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
> >>>>> and others, for example.  (Therefore, I don't think this needs to be
> >>>>> routed through a "traits" function, but can rather be done in-line here,
> >>>>> after each placement new, before deallocation of the original blob of
> >>>>> memory.  Also, I argue it's the right thing to do also for 'm_ggc',
> >>>>> because even if in that case we're not going to leak memory (GC will
> >>>>> reclaim), but we still may leak other resources dynamically allocated in
> >>>>> a non-trivial constructor.)
> >>>>
> >>>> Yes, of course, all elements need to be eventually be destroyed.
> >>>> My only hesitation was whether it should be done via one of these
> >>>> traits classes (like it's done in C++ containers via allocators)
> >>>> rather than directly
> >>>
> >>> Given that there is (apparently) no issue to do a placement new in
> >>> 'hash_table::expand', I'd asumme a -- corresponding -- explicit
> >>> destructor call would be likewise appropriate?  (But I'll of course route
> >>> this through a (new) "traits" function if someone explains why this is
> >>> the right thing to do.)
> >>>
> >>>> and whether there might be other places
> >>>> where the destruction night need to happen.
> >>>
> >>> (Possibly, yes, per discussion above -- but that's a separate issue?)
> >>>
> >>>>> The attached "Fix 'hash_table::expand' to destruct stale Value objects"
> >>>>> does prevent my original problem, does address the current 'class2loc'
> >>>>> memory leak in 'cp/parser.c' (see commit log for one example), and
> >>>>> adjusts the new
> >>>>> 'gcc/hash-map-tests.c:test_map_of_type_with_ctor_and_dtor_expand' test
> >>>>> case such that number of constructor calls matches the number of
> >>>>> destructor calls.  After some careful review regarding C++ details
> >>>>> (please!), OK to push to master branch?  (Also cherry-pick into release
> >>>>> branches, eventually?)  Is the source code comment that I'm adding
> >>>>> sufficiently explanatory and correct in C++ terms?
> >>>
> >>> Ping.
> >>>
> >>>> Shouldn't the hash_table dtor (and perhaps also empty())  also
> >>>> destroy the elements?  (Otherwise, what destroys the elements
> >>>> newly constructed here, or anywhere else for that matter, such
> >>>> as in the hash_table ctor?)
> >>>
> >>> Per my understanding, per discussion above, they (eventually) do get
> >>> destroyed via 'delete' in 'typed_delete_remove', for example, via
> >>> 'Descriptor::remove' calls for all/relevant entries in
> >>> 'hash_table::~hash_table', 'hash_table::empty_slow',
> >>> 'hash_table::clear_slot', 'hash_table::remove_elt_with_hash'.
> >>>
> >>> (This means that if there has been an intermediate 'expand', this may
> >>> (eventually) destroy objects at a different memory location from where
> >>> they originally have been created -- but that's fine.)
> >>>
> >>> The 'expand' case itself is different: any (live) entries are *moved*
> >>> into a new storage memory object via placement new.  (And then the
> >>> hollow entries in the old storage memory object linger.)
> >>>
> >>>> Also, shouldn't the destroyed slot be marked either deleted or
> >>>> empty?)
> >>>
> >>> Per my understanding, irrelevant in 'expand': working through 'oentries',
> >>> the *move* is only done 'if (!is_empty (x) && !is_deleted (x))' (so
> >>> combined with the item above, there is no memory leak for any entries
> >>> that have already been 'remove'd -- they have already been destructed),
> >>> and the whole (old) storage memory object will be deallocated right after
> >>> the 'oentries' loop.
> >>>
> >>>
> >>>> (Sorry, I realize I have more questions than answers.)
> >>>
> >>> No worries, happens to me most of the times!  Thanks for looking into
> >>> this.
> >>>
> >>>
> >>> Grüße
> >>>   Thomas
>
>
> -----------------
> Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

Re: [PING^2] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Jonathan Wakely]

On Fri, 17 Sept 2021 at 13:08, Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Fri, Sep 17, 2021 at 1:17 PM Thomas Schwinge <thomas@codesourcery.com> wrote:
> >
> > Hi!
> >
> > On 2021-09-10T10:00:25+0200, I wrote:
> > > On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> > >> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
> > >>> Ping -- we still need to plug the memory leak; see patch attached, and/or
> > >>> long discussion here:
> > >>
> > >> Thanks for answering my questions.  I have no concerns with going
> > >> forward with the patch as is.
> > >
> > > Thanks, Martin.  Ping for formal approval (and review for using proper
> > > C++ terminology in the 'gcc/hash-table.h:hash_table::expand' source code
> > > comment that I'm adding).  Patch again attached, for easy reference.
> >
> > Ping, once again.
>
> I'm happy when a C++ literate approves the main change which I quote as
>
>           new ((void*) q) value_type (std::move (x));
> +
> +         /* Manually invoke destructor of original object, to counterbalance
> +            object constructed via placement new.  */
> +         x.~value_type ();
>
> but I had the impression that std::move already "moves away" from the source?

It just casts the argument to an rvalue reference, which allows the
value_type constructor to steal its guts.

> That said, the dance above looks iffy, there must be a nicer way to "move"
> an object in C++?

The code above is doing two things: transfer the resources from x to a
new object at location *q, and then destroy x.

The first part (moving its resources) has nothing to do with
destruction. An object still needs to be destroyed, even if its guts
have been moved to another object.

The second part is destroying the object, to end its lifetime. You
wouldn't usually call a destructor explicitly, because it would be
done automatically at the end of scope for objects on the stack, or
done by delete when you free obejcts on the heap. This is a special
case where the object's lifetime is manually managed in storage that
is manually managed.

>
> What happens if the dtor is deleted btw?

If the destructor is deleted you have created an unusable type that
cannot be stored in containers. It can only be created using new, and
then never destroyed. If you play stupid games, you win stupid prizes.
Don't do that.

> Shouldn't you use sth
> like a placement 'delete' instead of invoking a DTOR?

No, there is no placement delete. This is exactly the right way to
destroy an object in-place.

I haven't read the rest of the patch, but the snippet above looks fine.

Re: [PING^2] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Richard Biener]

On Fri, Sep 17, 2021 at 2:39 PM Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>
> On Fri, 17 Sept 2021 at 13:08, Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Fri, Sep 17, 2021 at 1:17 PM Thomas Schwinge <thomas@codesourcery.com> wrote:
> > >
> > > Hi!
> > >
> > > On 2021-09-10T10:00:25+0200, I wrote:
> > > > On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> > > >> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
> > > >>> Ping -- we still need to plug the memory leak; see patch attached, and/or
> > > >>> long discussion here:
> > > >>
> > > >> Thanks for answering my questions.  I have no concerns with going
> > > >> forward with the patch as is.
> > > >
> > > > Thanks, Martin.  Ping for formal approval (and review for using proper
> > > > C++ terminology in the 'gcc/hash-table.h:hash_table::expand' source code
> > > > comment that I'm adding).  Patch again attached, for easy reference.
> > >
> > > Ping, once again.
> >
> > I'm happy when a C++ literate approves the main change which I quote as
> >
> >           new ((void*) q) value_type (std::move (x));
> > +
> > +         /* Manually invoke destructor of original object, to counterbalance
> > +            object constructed via placement new.  */
> > +         x.~value_type ();
> >
> > but I had the impression that std::move already "moves away" from the source?
>
> It just casts the argument to an rvalue reference, which allows the
> value_type constructor to steal its guts.
>
> > That said, the dance above looks iffy, there must be a nicer way to "move"
> > an object in C++?
>
> The code above is doing two things: transfer the resources from x to a
> new object at location *q, and then destroy x.
>
> The first part (moving its resources) has nothing to do with
> destruction. An object still needs to be destroyed, even if its guts
> have been moved to another object.
>
> The second part is destroying the object, to end its lifetime. You
> wouldn't usually call a destructor explicitly, because it would be
> done automatically at the end of scope for objects on the stack, or
> done by delete when you free obejcts on the heap. This is a special
> case where the object's lifetime is manually managed in storage that
> is manually managed.
>
> >
> > What happens if the dtor is deleted btw?
>
> If the destructor is deleted you have created an unusable type that
> cannot be stored in containers. It can only be created using new, and
> then never destroyed. If you play stupid games, you win stupid prizes.
> Don't do that.
>
> > Shouldn't you use sth
> > like a placement 'delete' instead of invoking a DTOR?
>
> No, there is no placement delete. This is exactly the right way to
> destroy an object in-place.
>
> I haven't read the rest of the patch, but the snippet above looks fine.

OK, thanks for clarifying.

The patch is OK then.

Thanks,
Richard.

Re: [PING^2] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Thomas Schwinge]

[-- Attachment #1: Type: text/plain, Size: 3504 bytes --]

Hi!

On 2021-09-17T15:03:18+0200, Richard Biener <richard.guenther@gmail.com> wrote:
> On Fri, Sep 17, 2021 at 2:39 PM Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>> On Fri, 17 Sept 2021 at 13:08, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>> > On Fri, Sep 17, 2021 at 1:17 PM Thomas Schwinge <thomas@codesourcery.com> wrote:
>> > > On 2021-09-10T10:00:25+0200, I wrote:
>> > > > On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>> > > >> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
>> > > >>> Ping -- we still need to plug the memory leak; see patch attached, [...]

>> > > > Ping for formal approval (and review for using proper
>> > > > C++ terminology in the 'gcc/hash-table.h:hash_table::expand' source code
>> > > > comment that I'm adding).  Patch again attached, for easy reference.

>> > I'm happy when a C++ literate approves the main change which I quote as
>> >
>> >           new ((void*) q) value_type (std::move (x));
>> > +
>> > +         /* Manually invoke destructor of original object, to counterbalance
>> > +            object constructed via placement new.  */
>> > +         x.~value_type ();
>> >
>> > but I had the impression that std::move already "moves away" from the source?
>>
>> It just casts the argument to an rvalue reference, which allows the
>> value_type constructor to steal its guts.
>>
>> > That said, the dance above looks iffy, there must be a nicer way to "move"
>> > an object in C++?
>>
>> The code above is doing two things: transfer the resources from x to a
>> new object at location *q, and then destroy x.
>>
>> The first part (moving its resources) has nothing to do with
>> destruction. An object still needs to be destroyed, even if its guts
>> have been moved to another object.
>>
>> The second part is destroying the object, to end its lifetime. You
>> wouldn't usually call a destructor explicitly, because it would be
>> done automatically at the end of scope for objects on the stack, or
>> done by delete when you free obejcts on the heap. This is a special
>> case where the object's lifetime is manually managed in storage that
>> is manually managed.

ACK, and happy that I understood this correctly.

And, thanks for providing some proper C++-esque wording, which I
summarized to replace my original source code comment.

>> > What happens if the dtor is deleted btw?
>>
>> If the destructor is deleted you have created an unusable type that
>> cannot be stored in containers. It can only be created using new, and
>> then never destroyed. If you play stupid games, you win stupid prizes.
>> Don't do that.

Haha!  ;-)

And, by the way, as I understood this: if the destructor is "trivial"
(which includes POD types, for example), the explicit destructor call
here is a no-op.

>> I haven't read the rest of the patch, but the snippet above looks fine.
>
> OK, thanks for clarifying.
>
> The patch is OK then.

Thanks, pushed to master branch
commit 89be17a1b231ade643f28fbe616d53377e069da8
"Fix 'hash_table::expand' to destruct stale Value objects".

Should this be backported to release branches, after a while?


Grüße
 Thomas


-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-hash_table-expand-to-destruct-stale-Value-object.patch --]
[-- Type: text/x-diff, Size: 15052 bytes --]

From 89be17a1b231ade643f28fbe616d53377e069da8 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Fri, 13 Aug 2021 18:03:38 +0200
Subject: [PATCH] Fix 'hash_table::expand' to destruct stale Value objects

Thus plugging potentional memory leaks if these have non-trivial
constructor/destructor.

See
<https://stackoverflow.com/questions/6730403/how-to-delete-object-constructed-via-placement-new-operator>
and others.

As one example, compilation of 'g++.dg/warn/Wmismatched-tags.C' per
'valgrind --leak-check=full' improves as follows:

     [...]
    -
    -104 bytes in 1 blocks are definitely lost in loss record 399 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA43C71: cp_parser_parameter_declaration(cp_parser*, int, bool, bool*) (parser.c:24242)
    -
    -168 bytes in 3 blocks are definitely lost in loss record 422 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA53385: cp_parser_single_declaration(cp_parser*, vec<deferred_access_check, va_gc, vl_embed>*, bool, bool, bool*) (parser.c:31072)
    -
    -488 bytes in 7 blocks are definitely lost in loss record 449 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA49508: cp_parser_member_declaration(cp_parser*) (parser.c:26440)
    -
    -728 bytes in 7 blocks are definitely lost in loss record 455 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA57508: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32980)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -   by 0xA47D76: cp_parser_class_specifier(cp_parser*) (parser.c:25680)
    -   by 0xA37E27: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18912)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -
    -832 bytes in 8 blocks are definitely lost in loss record 458 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -
    -1,144 bytes in 11 blocks are definitely lost in loss record 466 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA896B1: class_decl_loc_t::operator=(class_decl_loc_t const&) (parser.c:32697)
    -   by 0xA571FD: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32899)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA48BC6: cp_parser_class_head(cp_parser*, bool*) (parser.c:26090)
    -   by 0xA4674B: cp_parser_class_specifier_1(cp_parser*) (parser.c:25302)
    -
    -1,376 bytes in 10 blocks are definitely lost in loss record 467 of 519
    -   at 0x483DFAF: realloc (vg_replace_malloc.c:836)
    -   by 0x223B62C: xrealloc (xmalloc.c:179)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA8B373: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::reserve(unsigned int, bool) (vec.h:1858)
    -   by 0xA8B277: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::safe_push(class_decl_loc_t::class_key_loc_t const&) (vec.h:1967)
    -   by 0xA57481: class_decl_loc_t::add_or_diag_mismatched_tag(tree_node*, tag_types, bool, bool) (parser.c:32967)
    -   by 0xA573E1: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32941)
    -   by 0xA56C52: cp_parser_check_class_key(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32819)
    -   by 0xA3AD12: cp_parser_elaborated_type_specifier(cp_parser*, bool, bool) (parser.c:20227)
    -   by 0xA37EF2: cp_parser_type_specifier(cp_parser*, int, cp_decl_specifier_seq*, bool, int*, bool*) (parser.c:18942)
    -   by 0xA31CDD: cp_parser_decl_specifier_seq(cp_parser*, int, cp_decl_specifier_seq*, int*) (parser.c:15517)
    -   by 0xA301E0: cp_parser_simple_declaration(cp_parser*, bool, tree_node**) (parser.c:14772)
    -
    -3,552 bytes in 33 blocks are definitely lost in loss record 483 of 519
    -   at 0x483B7F3: malloc (vg_replace_malloc.c:309)
    -   by 0x223B63F: xrealloc (xmalloc.c:177)
    -   by 0xA8D848: void va_heap::reserve<class_decl_loc_t::class_key_loc_t>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:290)
    -   by 0xA901ED: bool vec_safe_reserve<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int, bool) (vec.h:697)
    -   by 0xA8F161: void vec_alloc<class_decl_loc_t::class_key_loc_t, va_heap>(vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>*&, unsigned int) (vec.h:718)
    -   by 0xA8D18D: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_embed>::copy() const (vec.h:979)
    -   by 0xA8B0C3: vec<class_decl_loc_t::class_key_loc_t, va_heap, vl_ptr>::copy() const (vec.h:1824)
    -   by 0xA8964A: class_decl_loc_t::class_decl_loc_t(class_decl_loc_t const&) (parser.c:32689)
    -   by 0xA8F515: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::expand() (hash-table.h:839)
    -   by 0xA8D4B3: hash_table<hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::hash_entry, false, xcallocator>::find_slot_with_hash(tree_node* const&, unsigned int, insert_option) (hash-table.h:1008)
    -   by 0xA8B1DC: hash_map<tree_decl_hash, class_decl_loc_t, simple_hashmap_traits<default_hash_traits<tree_decl_hash>, class_decl_loc_t> >::get_or_insert(tree_node* const&, bool*) (hash-map.h:200)
    -   by 0xA57128: class_decl_loc_t::add(cp_parser*, unsigned int, tag_types, tree_node*, bool, bool) (parser.c:32888)
     [...]
     LEAK SUMMARY:
    -   definitely lost: 8,440 bytes in 81 blocks
    +   definitely lost: 48 bytes in 1 blocks
        indirectly lost: 12,529 bytes in 329 blocks
          possibly lost: 0 bytes in 0 blocks
        still reachable: 1,644,376 bytes in 768 blocks

	gcc/
	* hash-table.h (hash_table<Descriptor, Lazy, Allocator>::expand):
	Destruct stale Value objects.
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor_expand):
	Update.
---
 gcc/hash-map-tests.c | 10 ++++++----
 gcc/hash-table.h     |  3 +++
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 6acc0d4337e..511d4342087 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -317,7 +317,8 @@ test_map_of_type_with_ctor_and_dtor ()
   }
 }
 
-/* Verify aspects of 'hash_table::expand'.  */
+/* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
+   Value objects.  */
 
 static void
 test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
@@ -400,9 +401,9 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
       ASSERT_EQ (val_t::ncopy, n_expand_moved);
       ASSERT_EQ (val_t::nassign, 0);
       if (remove_some_inline)
-	ASSERT_EQ (val_t::ndtor, (i + 2) / 3);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
       else
-	ASSERT_EQ (val_t::ndtor, 0);
+	ASSERT_EQ (val_t::ndtor, n_expand_moved);
 
       /* Remove some inline.  This never triggers an 'expand' here, but via
 	 'm_n_deleted' does influence any following one.  */
@@ -416,7 +417,7 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 	  ASSERT_EQ (val_t::ndefault, 1 + i);
 	  ASSERT_EQ (val_t::ncopy, n_expand_moved);
 	  ASSERT_EQ (val_t::nassign, 0);
-	  ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3);
+	  ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
 	}
     }
   ASSERT_EQ (expand_c, expand_c_expected);
@@ -439,6 +440,7 @@ test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
       ASSERT_EQ (val_t::nassign, nassign);
       ASSERT_EQ (val_t::ndtor, ndtor);
     }
+  ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
 }
 
 /* Test calling empty on a hash_map that has a key type with non-zero
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index a6e0ac8eea9..ff415c7250b 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -820,6 +820,9 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
         {
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 	  new ((void*) q) value_type (std::move (x));
+	  /* After the resources of 'x' have been moved to a new object at 'q',
+	     we now have to destroy the 'x' object, to end its lifetime.  */
+	  x.~value_type ();
         }
 
       p++;
-- 
2.33.0

Re: [PING^2] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Jonathan Wakely]

On Fri, 17 Sep 2021, 16:52 Thomas Schwinge, <thomas@codesourcery.com> wrote:

> Hi!
>
> On 2021-09-17T15:03:18+0200, Richard Biener <richard.guenther@gmail.com>
> wrote:
> > On Fri, Sep 17, 2021 at 2:39 PM Jonathan Wakely <jwakely.gcc@gmail.com>
> wrote:
> >> On Fri, 17 Sept 2021 at 13:08, Richard Biener
> >> <richard.guenther@gmail.com> wrote:
> >> > On Fri, Sep 17, 2021 at 1:17 PM Thomas Schwinge <
> thomas@codesourcery.com> wrote:
> >> > > On 2021-09-10T10:00:25+0200, I wrote:
> >> > > > On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <
> gcc-patches@gcc.gnu.org> wrote:
> >> > > >> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
> >> > > >>> Ping -- we still need to plug the memory leak; see patch
> attached, [...]
>
> >> > > > Ping for formal approval (and review for using proper
> >> > > > C++ terminology in the 'gcc/hash-table.h:hash_table::expand'
> source code
> >> > > > comment that I'm adding).  Patch again attached, for easy
> reference.
>
> >> > I'm happy when a C++ literate approves the main change which I quote
> as
> >> >
> >> >           new ((void*) q) value_type (std::move (x));
> >> > +
> >> > +         /* Manually invoke destructor of original object, to
> counterbalance
> >> > +            object constructed via placement new.  */
> >> > +         x.~value_type ();
> >> >
> >> > but I had the impression that std::move already "moves away" from the
> source?
> >>
> >> It just casts the argument to an rvalue reference, which allows the
> >> value_type constructor to steal its guts.
> >>
> >> > That said, the dance above looks iffy, there must be a nicer way to
> "move"
> >> > an object in C++?
> >>
> >> The code above is doing two things: transfer the resources from x to a
> >> new object at location *q, and then destroy x.
> >>
> >> The first part (moving its resources) has nothing to do with
> >> destruction. An object still needs to be destroyed, even if its guts
> >> have been moved to another object.
> >>
> >> The second part is destroying the object, to end its lifetime. You
> >> wouldn't usually call a destructor explicitly, because it would be
> >> done automatically at the end of scope for objects on the stack, or
> >> done by delete when you free obejcts on the heap. This is a special
> >> case where the object's lifetime is manually managed in storage that
> >> is manually managed.
>
> ACK, and happy that I understood this correctly.
>
> And, thanks for providing some proper C++-esque wording, which I
> summarized to replace my original source code comment.
>
> >> > What happens if the dtor is deleted btw?
> >>
> >> If the destructor is deleted you have created an unusable type that
> >> cannot be stored in containers. It can only be created using new, and
> >> then never destroyed. If you play stupid games, you win stupid prizes.
> >> Don't do that.
>
> Haha!  ;-)
>
> And, by the way, as I understood this: if the destructor is "trivial"
> (which includes POD types, for example), the explicit destructor call
> here is a no-op.
>

Right.

And you can even do x.~value_type(); for things which aren't classes and
don't have any destructor at all, not even a trivial one. So in a template
function, if the template argument T is int or char or long*, it's ok to do
t.~T(). This is called a pseudo-destructor call (because scalar types like
int don't actually have a destructor). This will also be a no-op.

This allows you to write the same template code for any types* and it will
correctly destroy them, whether they have a non-trivial destructor that
does real work, or a trivial one, or if they are not even classes and have
no destructor at all.

* Well, nearly any types... You can't do it if the destructor is deleted,
as Richi asked about, or private, and you can't do it for non-object types
(references, functions, void) but that's ok because you can't store them in
a container anyway.

Re: [PING^2] Re: Fix 'hash_table::expand' to destruct stale Value objects

[Richard Biener]

On Fri, Sep 17, 2021 at 5:52 PM Thomas Schwinge <thomas@codesourcery.com> wrote:
>
> Hi!
>
> On 2021-09-17T15:03:18+0200, Richard Biener <richard.guenther@gmail.com> wrote:
> > On Fri, Sep 17, 2021 at 2:39 PM Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> >> On Fri, 17 Sept 2021 at 13:08, Richard Biener
> >> <richard.guenther@gmail.com> wrote:
> >> > On Fri, Sep 17, 2021 at 1:17 PM Thomas Schwinge <thomas@codesourcery.com> wrote:
> >> > > On 2021-09-10T10:00:25+0200, I wrote:
> >> > > > On 2021-09-01T19:31:19-0600, Martin Sebor via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> >> > > >> On 8/30/21 4:46 AM, Thomas Schwinge wrote:
> >> > > >>> Ping -- we still need to plug the memory leak; see patch attached, [...]
>
> >> > > > Ping for formal approval (and review for using proper
> >> > > > C++ terminology in the 'gcc/hash-table.h:hash_table::expand' source code
> >> > > > comment that I'm adding).  Patch again attached, for easy reference.
>
> >> > I'm happy when a C++ literate approves the main change which I quote as
> >> >
> >> >           new ((void*) q) value_type (std::move (x));
> >> > +
> >> > +         /* Manually invoke destructor of original object, to counterbalance
> >> > +            object constructed via placement new.  */
> >> > +         x.~value_type ();
> >> >
> >> > but I had the impression that std::move already "moves away" from the source?
> >>
> >> It just casts the argument to an rvalue reference, which allows the
> >> value_type constructor to steal its guts.
> >>
> >> > That said, the dance above looks iffy, there must be a nicer way to "move"
> >> > an object in C++?
> >>
> >> The code above is doing two things: transfer the resources from x to a
> >> new object at location *q, and then destroy x.
> >>
> >> The first part (moving its resources) has nothing to do with
> >> destruction. An object still needs to be destroyed, even if its guts
> >> have been moved to another object.
> >>
> >> The second part is destroying the object, to end its lifetime. You
> >> wouldn't usually call a destructor explicitly, because it would be
> >> done automatically at the end of scope for objects on the stack, or
> >> done by delete when you free obejcts on the heap. This is a special
> >> case where the object's lifetime is manually managed in storage that
> >> is manually managed.
>
> ACK, and happy that I understood this correctly.
>
> And, thanks for providing some proper C++-esque wording, which I
> summarized to replace my original source code comment.
>
> >> > What happens if the dtor is deleted btw?
> >>
> >> If the destructor is deleted you have created an unusable type that
> >> cannot be stored in containers. It can only be created using new, and
> >> then never destroyed. If you play stupid games, you win stupid prizes.
> >> Don't do that.
>
> Haha!  ;-)
>
> And, by the way, as I understood this: if the destructor is "trivial"
> (which includes POD types, for example), the explicit destructor call
> here is a no-op.
>
> >> I haven't read the rest of the patch, but the snippet above looks fine.
> >
> > OK, thanks for clarifying.
> >
> > The patch is OK then.
>
> Thanks, pushed to master branch
> commit 89be17a1b231ade643f28fbe616d53377e069da8
> "Fix 'hash_table::expand' to destruct stale Value objects".
>
> Should this be backported to release branches, after a while?

You'd have to cross-check the status of C++ support in our containers there.
If it is a memory leak fix then yes, but as said, something older than
GCC 11 needs
double-checking if it is a) affected and b) has other bits already.

Richard.

>
> Grüße
>  Thomas
>
>
> -----------------
> Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955