Re: Hash Table Collisions (n.runs-SA-2011.004)

[David Kolf <kolf@...>]

Leo Razoumov wrote:
> Alternatively, as I suggested in an earlier post to this thread, you
> can use self-balancing trees like RB-tree to resolve collisions
> instead of lists when lists get larger. Most of the time current Lua
> hash-table implementation is in effect but it switches to RB-tree
> buckets when list performance gets in trouble (e.g. when under
> attack). RB-tree give you O(log(N)) performance which is sufficient to
> defeat the attack.

I started writing an RB-tree patch where I use one tree for every bucket 
in the global string table. It defeats my test attack quite well, but it 
still seems to have its own bugs...

I only changed the implementation of the global string table. For other 
tables I just #define'd hashstr to hashpointer. Since strings are 
internalized, this should work just as well and is quite simple.

I hope that I can find the time to get the bugs out of my patch. (Has 
somebody else already written such a patch?)

-- David