[jaunty] Segmentation fault in hsearch_r of glibc-2.9

[Alexey Khoroshilov]

LSB tests have detected several segmentation faults in hsearch/hsearch_r functions of Ubuntu-9.04 [1].

Investigation shows that there are two bugs introduced by the patch [2] included into glibc-2.9. The first bug [3] has been already fixed in glibc cvs, the second bug [4] has been fixed in glibc cvs after our bug report [5].

[1] http://bugs.linuxbase.org/show_bug.cgi?id=2606
[2] http://sourceware.org/bugzilla/show_bug.cgi?id=6966
[3] http://linuxtesting.org/results/report?num=S0790
[4] http://linuxtesting.org/results/report?num=S0791
[5] http://sourceware.org/bugzilla/show_bug.cgi?id=10100

[Bugzilla-t (bugzilla-t)]

hsearch references Kunth vol. 3 6.4 on "open addressing" but the code does
implement the algorithm from Knuth. Instead of generating the second hash from
the first, the code generates the second hash from the first index. Because
this hash is then used to step the index, the result is that the first index
generated is (almost) always the same.

This partly defeats the purpose of using a secondary hash.

I say "almost" because it happens for all but 2 of the possible index values in
any given table. For example, in a table of size 11, all secondary probes will
start at index 10 unless the inital hash produced 9 or 10.

This was reported on news:comp.lang.c by James Dow Allen and I decided to check
on it. I have a simple patch but I am not sure of the procedure for posting
patches to glibc.

[Bugzilla-t (bugzilla-t)]

Created attachment 3006
Suggested fix.

The patch suggests two related changes. First, that idx be set from hval
without reducing havl % htab->size. hval2 can now be derived from hval without
generating the same probe sequence all the time. Secondly, a new variable must
be used to detect the wrap-around, since hval no longer contains the initial
value of idx.

[Drepper-fsp (drepper-fsp)]

Applied to cvs.