diff options
author | antirez <antirez@gmail.com> | 2014-04-03 19:31:26 +0200 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2014-04-03 19:31:26 +0200 |
commit | 349c97818995de9ff6fed337844ff4bbb1b36153 (patch) | |
tree | c6958c954ad030e895aecfaf63b8715e003d512f | |
parent | b612affba305fd34662fc4afae5663c764915c12 (diff) | |
download | redis-349c97818995de9ff6fed337844ff4bbb1b36153.tar.gz |
Fix PFADD infinite loop.
We need to guarantee that the last bit is 1, otherwise an element may
hash to just zeroes with probability 1/(2^64) and trigger an infinite
loop.
See issue #1657.
-rw-r--r-- | src/hyperloglog.c | 9 |
1 files changed, 3 insertions, 6 deletions
diff --git a/src/hyperloglog.c b/src/hyperloglog.c index a6a600cfd..d32a94be2 100644 --- a/src/hyperloglog.c +++ b/src/hyperloglog.c @@ -317,14 +317,11 @@ int hllAdd(uint8_t *registers, unsigned char *ele, size_t elesize) { * This may sound like inefficient, but actually in the average case * there are high probabilities to find a 1 after a few iterations. */ hash = MurmurHash64A(ele,elesize,0); - bit = REDIS_HLL_REGISTERS; - count = 1; + hash |= ((uint64_t)1<<63); /* Make sure the loop terminates. */ + bit = REDIS_HLL_REGISTERS; /* First bit not used to address the register. */ + count = 1; /* Initialized to 1 since we count the "00000...1" pattern. */ while((hash & bit) == 0) { count++; - /* Test the next bit. Note that if we run out of bits in the 64 - * bit integer, bit will be set to 0, and the while test will fail, - * so we can save the explicit check and yet the algorithm will - * terminate. */ bit <<= 1; } |