| Message ID | CAF6KqwWcuO+kLjOKfRKK6_bWtPKSnU2JvLv1sU2N+gxtCUVFYA@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
On Tue, Jul 26, 2011 at 16:13, Delesley Hutchins <delesley@google.com> wrote: > This patch fixes a bug in pointer_set.c, where removing a pointer from > a pointer set would corrupt the hash table if the pointer was involved > in any hash collisions. Could you include a test case? It's not clear to me what you are fixing and when this happens. Is this a bug in trunk as well? The pointer-set implementation has been around for a while, so I'm surprised that you are running into this now. Or is this something that only happens with the pointer set changes we have in for annotalysis? Thanks. Diego.
Le-Chun added the additional routine to remove pointers from a set; that code is unique to annotalysis. I can't easily include a test case, because the bug is difficult to trigger. It occurs only when there is a hash collision between two pointers in the set, and the first pointer is removed before the second. I do have a test case, but it will only work for my particular build on my machine, since the actual pointer addresses involved will change as soon as you touch something. I could write a unit test using bogus pointer values that are engineered to trigger a collision, but it wouldn't be a normal compiler test case; where would I put it? -DeLesley On Tue, Jul 26, 2011 at 5:59 PM, Diego Novillo <dnovillo@google.com> wrote: > On Tue, Jul 26, 2011 at 16:13, Delesley Hutchins <delesley@google.com> wrote: >> This patch fixes a bug in pointer_set.c, where removing a pointer from >> a pointer set would corrupt the hash table if the pointer was involved >> in any hash collisions. > > Could you include a test case? It's not clear to me what you are > fixing and when this happens. Is this a bug in trunk as well? The > pointer-set implementation has been around for a while, so I'm > surprised that you are running into this now. Or is this something > that only happens with the pointer set changes we have in for > annotalysis? > > > Thanks. Diego. >
On 07/26/2011 04:13 PM, Delesley Hutchins wrote: > This patch fixes a bug in pointer_set.c, where removing a pointer from > a pointer set would corrupt the hash table if the pointer was involved > in any hash collisions. > > Bootstrapped and passed gcc regression testsuite on x86_64-unknown-linux-gnu. > > Okay for google/gcc-4_6? > > -DeLesley > > gcc/Changelog.annotalysis: > 2011-7-26 DeLesley Hutchins <delesley@google.com> > > * gcc/pointer-set.c (pointer_set_delete) bugfix for case of > hash collisions The logic of the patch looks good. I certainly agree it's a real bug. > + /* find location of p */ But please fix up all the comments to be properly punctuated sentences. > + pset->slots[n] = 0; /* remove ptr from set. */ And avoid end-of-line comments. Put it on the previous line. r~
Okay for google/gcc-4_6. Ollie On Tue, Jul 26, 2011 at 7:27 PM, Delesley Hutchins <delesley@google.com> wrote: > > Le-Chun added the additional routine to remove pointers from a set; > that code is unique to annotalysis. I can't easily include a test > case, because the bug is difficult to trigger. It occurs only when > there is a hash collision between two pointers in the set, and the > first pointer is removed before the second. I do have a test case, > but it will only work for my particular build on my machine, since the > actual pointer addresses involved will change as soon as you touch > something. I could write a unit test using bogus pointer values that > are engineered to trigger a collision, but it wouldn't be a normal > compiler test case; where would I put it? > > -DeLesley > > On Tue, Jul 26, 2011 at 5:59 PM, Diego Novillo <dnovillo@google.com> wrote: > > On Tue, Jul 26, 2011 at 16:13, Delesley Hutchins <delesley@google.com> wrote: > >> This patch fixes a bug in pointer_set.c, where removing a pointer from > >> a pointer set would corrupt the hash table if the pointer was involved > >> in any hash collisions. > > > > Could you include a test case? It's not clear to me what you are > > fixing and when this happens. Is this a bug in trunk as well? The > > pointer-set implementation has been around for a while, so I'm > > surprised that you are running into this now. Or is this something > > that only happens with the pointer set changes we have in for > > annotalysis? > > > > > > Thanks. Diego. > > > > > > -- > DeLesley Hutchins | Software Engineer | delesley@google.com | 505-206-0315
Index: gcc/pointer-set.c =================================================================== --- gcc/pointer-set.c (revision 176809) +++ gcc/pointer-set.c (working copy) @@ -192,19 +192,16 @@ int pointer_set_delete (struct pointer_set_t *pset, const void *p) { size_t n = hash1 (p, pset->n_slots, pset->log_slots); + size_t n2; + const void* ptr; + /* find location of p */ while (true) { if (pset->slots[n] == p) - { - pset->slots[n] = 0; - --pset->n_elements; - return 1; - } + break; else if (pset->slots[n] == 0) - { - return 0; - } + return 0; else { ++n; @@ -212,6 +209,29 @@ pointer_set_delete (struct pointer_set_t *pset, co n = 0; } } + + /* Remove p from set. */ + pset->slots[n] = 0; + + /* Now we need to scan foward and re-hash every value that we encounter, + until we find an empty slot. + */ + while (true) + { + ++n; + if (n >= pset->n_slots) + n = 0; + ptr = pset->slots[n]; + + if (ptr == 0) break; + + pset->slots[n] = 0; /* remove ptr from set. */ + n2 = insert_aux(ptr, pset->slots, pset->n_slots, pset->log_slots); + pset->slots[n2] = ptr; /* put ptr back in set. */ + } + + --pset->n_elements; + return 1; } /* Pass each pointer in PSET to the function in FN, together with the fixed
This patch fixes a bug in pointer_set.c, where removing a pointer from a pointer set would corrupt the hash table if the pointer was involved in any hash collisions. Bootstrapped and passed gcc regression testsuite on x86_64-unknown-linux-gnu. Okay for google/gcc-4_6? -DeLesley gcc/Changelog.annotalysis: 2011-7-26 DeLesley Hutchins <delesley@google.com> * gcc/pointer-set.c (pointer_set_delete) bugfix for case of hash collisions