| Message ID | or5ydxh4l4.fsf@lxoliva.fsfla.org |
|---|---|
| State | New |
| Headers | show |
On 12/27/22 05:07, Alexandre Oliva via Gcc-patches wrote: > > While looking into another issue that corrupted hash tables, I added > code to check consistency of element counts, and hit numerous issues > that were concerning, of three kinds: insertion of entries that seem > empty, dangling insertions, and lookups during insertions. > > These problems may all have the effect of replacing a deleted entry > with one that seems empty, which may disconnect double-hashing chains > involving that entry, and thus cause entries to go missing. > > This patch, opening the patch series, only adds code to detect these > problems to the hash table verifier method. I'm not sure it makes > sense to put it in, but I post it for the record. Fixes and cheaper > detectors for some of these errors are going to be posted separately. > > The number of bugs it revealed tells me that leaving callers in charge > of completing insertions is too error prone. I found this > verification code a bit too expensive to enable in general. Hello. I really like the verification code you added. It's quite similar to what I added to hash-table.h: void hash_table<Descriptor, Lazy, Allocator> ::verify (const compare_type &comparable, hashval_t hash) where the check is also expensive, but I guard it with a param value: hash-table-verification-limit The number of elements for which hash table verification is done for each searched element. You can utilize the parameter or come up with your own. Cheers, Martin > We could > add check entry count cheaply at expand time and catch some of these > at very low cost, which would likely catch at least some of the > errors, but perhaps a safer interface could avoid them entirely. > WDYT? > > > I'm going to post a collection of 13 patches a as a followup to this > one, fixing various problems it has detected, or adding code to catch > some of these problems sooner. > > > for gcc/ChangeLog > > * hash-table.h (verify): Check elements and deleted counts. > --- > gcc/hash-table.h | 17 +++++++++++++++++ > 1 file changed, 17 insertions(+) > > diff --git a/gcc/hash-table.h b/gcc/hash-table.h > index 53507daae26c3..7dbeea05373a2 100644 > --- a/gcc/hash-table.h > +++ b/gcc/hash-table.h > @@ -1035,6 +1035,23 @@ hash_table<Descriptor, Lazy, Allocator> > && Descriptor::equal (*entry, comparable)) > hashtab_chk_error (); > } > + > + if (m_size < 2048) > + { > + size_t elmts = m_n_elements, dels = m_n_deleted; > + for (size_t i = 0; i < m_size; i++) > + { > + value_type *entry = &m_entries[i]; > + if (!is_empty (*entry)) > + { > + elmts--; > + if (is_deleted (*entry)) > + dels--; > + } > + } > + if (elmts || dels) > + hashtab_chk_error (); > + } > } > > /* This function deletes an element with the given COMPARABLE value > >
diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 53507daae26c3..7dbeea05373a2 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -1035,6 +1035,23 @@ hash_table<Descriptor, Lazy, Allocator> && Descriptor::equal (*entry, comparable)) hashtab_chk_error (); } + + if (m_size < 2048) + { + size_t elmts = m_n_elements, dels = m_n_deleted; + for (size_t i = 0; i < m_size; i++) + { + value_type *entry = &m_entries[i]; + if (!is_empty (*entry)) + { + elmts--; + if (is_deleted (*entry)) + dels--; + } + } + if (elmts || dels) + hashtab_chk_error (); + } } /* This function deletes an element with the given COMPARABLE value