Re: int_cst_hash_table mapping persistence and the garbage collector

[Richard Guenther <richard dot guenther at gmail dot com>]

On Mon, Oct 10, 2011 at 7:02 PM, Gary Funck <gary@intrepid.com> wrote:
> Recently, a few UPC test programs failed to compile
> due to mis-matches of parameters in a prototype and its
> corresponding function definition. ?The mis-match was
> based upon the apparent inequality of UPC layout qualifiers
> (blocking factors).
>
> UPC blocking factors are integer constants. ?They are
> recorded in a hash table indexed by the type tree node
> that they correspond to.
>
> Currently, the test for equality of blocking factors
> tests only the pointer to the tree node defining the constant.
> All blocking factors are recorded as "sizetype" type'd nodes.
> Given that integer constants are hashed by type/value, it seemed
> safe to assume that a given blocking factor would map to
> a single tree node due to the underlying hash method that is used
> when integral constants are created.
>
> Is it valid to assume that pointer equality is sufficient
> to ensure that two integer constants are equal as long
> as their type and values are equal?
>
> The bug that we ran into occurred because a garbage collection
> pass was run between the point that the function prototype
> tree node was created and the point at which the function declaration
> was processed. ?The garbage collector decided that the integer
> constant representing the blocking factor was no longer in use,
> because it had not been marked.
>
> In fact, the integer constant was needed because it appeared
> in the blocking factor hash table, but not via a direct pointer.
> Rather it was referenced by nature of the fact that
> the blocking factor hash table referenced the integer constant
> that is mapped in the integer constant hash table.
>
> Here's a rough diagram:
>
> ? tree (type) -> [ blocking factor hash ] -> tree (integer constant)
> ? tree (integer constant) -> [ integer constant hash ] {unique map}
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?-> tree (integer constant)
>
> When the garbage collector deleted the entry from the
> "integer constant hash", it forced a new integer constant tree
> node to be created for the same (type, value) integral constant
> blocking factor.
>
> One easy way to address the current issue is to call
> tree_int_cst_equal() if the integer constant tree pointers
> do not match:
>
> ? ?if ((c1 != c2) && !tree_int_cst_equal (c1, c2))
> ? ? ?/* integer constants aren't equal. ?*/
>
> This may be necessary if 'int_cst_hash_table' is viewed as
> a cache rather than a persistent, unique mapping.
>
> Another approach, would be to somehow mark the node
> in int_cst_hash_table as in use when the blocking factor
> hash table is traversed by the garbage collector, or
> to add logic the hash table delete function associated
> with int_cst_hash_table; to dis-allow the delete if the
> integer constant is present in the UPC blocking factor
> hash table.
>
> To effect this change in a modular way probably the hash table
> delete function associated with 'int_cst_hash_table' would have
> to be daisy-chained, where the UPC blocking factor check is made
> first. ?The difficulty with implementing the daisy chaining is that
> int_cst_hash_table needs to exist before the UPC-related initialization
> code is run. ?One way to handle this might be yet another language
> hook, called from the code that creates 'int_cst_hash_table'.
> That seems overly complex.
>
> For reference, the current blocking factor mapping table
> is created as follows:
>
> ?upc_block_factor_for_type = htab_create_ggc (512, tree_map_hash,
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? tree_map_eq, 0);
>
> Summary:
>
> 1. Is it valid to assume that pointer equality is sufficient
> to compare two integer constants for equality as long as they
> have identical type and value?

Yes, if both constants are "live"

> 2. Should 'int_cst_hash_table' be viewed as a cache, where
> the mapping of a given (type, value) integer constant may
> vary over time?

Yes, if a constant is unused it may get collected and re-allocated
later.  Cannot be observed from any valid use of 1.

> 3. If the answer to 1. is "yes" and the answer to 2. is "no"
> then what is the recommended way to ensure that nodes in
> 'int_cst_hash_table' are not removed if the integer constant
> is being referenced via the 'upc_block_factor_for_type'
> hash table?

You need to ensure the constants are marked properly.

Richard.

> thanks,
> - Gary
>