'hash_map<tree, hash_map<tree, tree>>'
Thomas Schwinge
thomas@codesourcery.com
Mon Aug 16 12:43:42 GMT 2021
Hi!
On 2021-08-07T09:54:53+0100, Jonathan Wakely via Gcc <gcc@gcc.gnu.org> wrote:
> On Sat, 7 Aug 2021, 09:08 Thomas Schwinge, <thomas@codesourcery.com> wrote:
>> On 2021-08-06T19:37:58+0100, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>> > On Fri, 6 Aug 2021, 17:58 Thomas Schwinge, <thomas@codesourcery.com> 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.
>> >>
>> >> 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: [...]
>> >>
>> >> 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.
>>
>> That testing came back without any issues.
>>
>> > Does GCC's hash_map assume you only use it to store POD (plain old data)
>> > types
>>
>> Don't you disappoint me, C++!
>
> It's not a limitation of C++, just this data structure.
(Understood, of course. Yet, the programming language paves the way for
making it "easy" to achieve similar behavior for different kinds of data
types -- but I know, the devil's in the details, always.)
Actually, I suppose not "non-POD" is the problem here, but rather
non-trivial constructor/destructor, because the latter is how you have a
C++ class data type allocate additional resources (such as memory), which
is what's the problem here regarding the memory leak.
>> > which don't need to be destroyed, because they don't have any
>> > dynamically allocated memory or other resources?
>> >
>> > A hash_map is not a POD, because it does have dynamically allocated memory.
>>
>> ACK, that's what I tried to say above in my "layman's terms". ;-)
>>
>> > If my guess is right, then hash_map should really use a static_assert to
>> > enforce that requirement, instead of letting you use it in a way that will
>> > leak.
>>
>> Eh, yes, at the very least!
'gcc/hash-map.h':
/* Class hash_map is a hash-value based container mapping objects of
KeyId type to those of the Value type.
Both KeyId and Value may be non-trivial (non-POD) types provided
a suitabe Traits class. [...]
..., so this ought to work in principle. Indeed, if I try:
--- gcc/hash-map.h
+++ gcc/hash-map.h
@@ -38,6 +38,9 @@ template<typename KeyId, typename Value,
Value> */>
class GTY((user)) hash_map
{
+ static_assert (std::is_pod<KeyId>::value, "non-POD KeyId");
+ static_assert (std::is_pod<Value>::value, "non-POD Value");
+
[...]
... we get a very lot of complaints.
Trying another thing (catching non-trivial destructor instead of
non-POD):
--- gcc/hash-table.h
+++ gcc/hash-table.h
@@ -814,30 +814,36 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
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));
}
p++;
}
while (p < olimit);
+ /* If we get here for types with non-trivial destructor, there is a memory
+ leak: above, the individual 'x's have been 'move'd, and below, the
+ original 'm_entries' container gets 'free'd -- but the individual 'x's
+ never get destructed. */
+ gcc_checking_assert (std::is_trivially_destructible<value_type>::value);
+
if (!m_ggc)
Allocator <value_type> ::data_free (oentries);
else
ggc_free (oentries);
}
..., that is getting closer, but it still fires in a number of places
where there in fact is no leak (because the non-trivial constructor
doesn't actually allocate any resources dynamically). (See attached,
just for posterity.)
>> Or, of course, make it work? I mean GCC surely isn't the first software
>> project to desire implementing a 'hash_map' storing non-POD objects?
>> Don't you disappoint me, C++!
>
> Of course it's possible.
So let's do it. :-)
>> Alternative to that manual destructor call (per my patch/hack above) --
>> is maybe something wrong in the 'value_type' constructor implementation
>> or any other bits related to the 'std::move'? (Is that where the non-POD
>> source data ought to be destructed; via "move" instead of "copy"
>> semantics?)
>
> No, a move is just a transfer of resources, it doesn't end the object's
> lifetime. You still need a destructor. I don't know if that is the right
> place to do it though (I haven't looked into it). The destructor should be
> run just before an object is removed from the container.
ACK, thanks. For a continuation of this specific discussion, please see
my reply to Martin Sebor's email.
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-WIP-In-hash_table-expand-verify-is_trivially_destruc.patch
Type: text/x-diff
Size: 7700 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20210816/35f2ff00/attachment.bin>
More information about the Gcc
mailing list