Bug 99641

Created attachment 129288 [details] [review]
dbus-hash: Fix a potential shift by a negative integer

As a hash table becomes unbelievably large and full, the down_shift
tends towards 0. The overflow detection code in rebuild_table() does not
prevent down_shift becoming negative, which then causes undefined
behaviour in RANDOM_INDEX for int-keyed tables.

Note that this can only happen with approachint INT_MAX entries in the
hash table, at which point we’ve almost certainly hit OOM somewhere, so
this is vanishingly unlikely to happen. This is why I can’t add a test
for the bug.

As always, thanks to Coverity.

Coverity ID: 54682

Comment on attachment 129288 [details] [review]
dbus-hash: Fix a potential shift by a negative integer

Review of attachment 129288 [details] [review]:
-----------------------------------------------------------------

Looks OK? Although I still hate the fact that we even have to implement a hash table here. So much of libdbus is "GLib, but not as good and under an incompatible license"...

> * Hash table implementation based on generic/tclHash.c from the Tcl
> * source code.

I don't suppose you've looked at Tcl's hash table to see whether it has the same bug or has already received the same fix?

(In reply to Simon McVittie from comment #3)
> > * Hash table implementation based on generic/tclHash.c from the Tcl
> > * source code.
> 
> I don't suppose you've looked at Tcl's hash table to see whether it has the
> same bug or has already received the same fix?

I didn’t notice that.

Looks like tclHash has a substantially different rebuildTable() function: https://github.com/tcltk/tcl/blob/master/generic/tclHash.c#L997

They don’t have any overflow checks for anything in there; and the downShift is never decreased again each time it is incremented by 2.

tclHash has also not seen too many changes recently: https://github.com/tcltk/tcl/commits/master/generic/tclHash.c

Fixed in git for 1.11.10, thanks