This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Allow (limited) recursive use of hash tables


Jakub Jelinek wrote:

Hi!

https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=157308
contains a testcase that with current gcc-3_4-branch as well as
Red Hat 3.4.3 and 3.4.2 based compilers exhibits an interesting
problem.
const_desc_htab hash table's hash function calls const_hash_1,
which in turn can call decode_addr_const (for ADDR_EXPR/FDESC_EXPR)
and that can call output_constant_def (on the above referenced
testcase there is <ADDR_EXPR <CONSTRUCTOR ...>> in the const_desc_htab
table's value) and that in turn calls htab_find_slot (const_desc_htab, ...).
This is problematic in hash table expansion.
Current htab_expand puts the new elements array as htab->elements
and afterwards iterates over the old elements array and inserts
the entries into initially empty hash table. For each of the entries
it calls htab->hash_f. Now as const_desc_htab->hash_f uses
const_desc_htab hashtable internally, it can happen that
what it is looking up is not yet in the new hash table (and the old
elements array is not accessible), so it creates new SYMBOL_REF
(but deferred one, so it is never output and results in undefined
references to .LC* symbols).


Jakub, sorry. I don't review this code anymore. I lost track of changes a few years ago. But I don't like a situation that something is inserted in the table during its extension. When I designed the expanded hash tables, I always thought that hash and compare functions are atomic (no side effects for user's code) and inexpensive (all preliminary expensive work for hashing is done before using the tables). But it looks like people abused the hash table power (or more probably missed this complication because there is no checking). This situation is a surprise for me. Long ago I wanted to add some check to prevent this kind of situations. I have should done this the first time.

I see 2 possible solutions for this:

One is add a hashval_t element into the constant_descriptor_tree structure,
use htab_find{,_slot}_with_hash after calling const_hash_1 () explicitely
instead of htab_find{,_slot} and just return the recorded hashval_t from
const_desc_hash. This means the hash table will never be used recursively,
the drawback is bigger memory footprint (4 bytes per entry on 32-bit
and 8 bytes per entry on 64-bit hosts).


I'd prefer the first solution even if it is more expensive (although these data are not so big to worry about smaller footprint).

Alternatively, htab_expand can be changed to allow limited recursion.
Particularly, the hash table can be used read-only from hash_f function
(where read-only means no entry insertion or deletion, statistics can
be changed).  That's all that varasm.c actually needs (the hash function
has been already called on the entry before, so it will never need to
add new things into the hash table).

I have implemented the latter.

The static int recursive variable is in there because we should IMHO
allow htab_find_slot with INSERT called from htab_f, as long as it doesn't
actually insert new entry.  But as soon as htab is filled to 3/4,
each such htab_find_slot would try to call htab_expand again.






Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]