Dynamic hash table size (with static has load)
Shachar Shemesh
rsync at shemesh.biz
Sun Feb 26 16:55:18 GMT 2006
Wayne Davison wrote:
>On Sun, Feb 26, 2006 at 10:34:25AM +0200, Shachar Shemesh wrote:
>
>
>>A line of credit would have been nice :-)
>>
>>
>
>Sure 'nuff.
>
>
Thanks.
>>2. In "sum_buf", sum1 is defined to be unsigned. It seems dangerous to
>>me to hash it into a signed index, even if it's almost guarenteed to be ok.
>>
>>
>The result is an index into the array (and can be no larger than the max
>size of the array), so I like to use the same type as the other indexes.
>
>
If you are not convinced, I will not press this matter further. Still,
the paranoid in me (I've spent over two years at Check Point,
manufacturer of Firewall-1, as their chief paranoid engineer) (the
official title was "Security Focus Team Leader", thought) is uneasy with
this. Strike that, I think I can actually exploit this.
I'll draw you a scenario:
- Attacker puts just enough checksums in the count to make the 20%
expansion overflow the 32bit variable. We now get a tablesize of "1".
- The gettag divides the sums by 1, resulting in negative indexes into
the array.
- Profit
Conclusions:
- We need to guard the expansion code from integer overflows.
- Please, please please please please, make the indexes unsigned!
>>initialize the chain element to -1 instead of 0, as
>>that's the "null" value).
>>
>>
>The latter was a bug, since it results in the 0th element being checked
>in every chain -- good catch.
>
>
Thanks, but I really do think it's a simple style matter. As far as I
can tell, the chain variable is overwritten (s->sums[i].chain =
sum_table[t];) before the first time it is used, so no actual bug, just
style.
>..wayne..
>
>
Shachar
Suggested guard code in case I did not convince you to switch to unsigned:
static const int32 MAXHASHES=(0x7fffffff-11)/10*8;
...
if( s->count > MAXHASHES )
Error
If you do make the right decision ;-), the number above needs to be
amended a little.
static const size_t MAXHASHES=((~((size_t)0))-11)/10*8
More information about the rsync
mailing list