PFADD hangs on empty values

[pepijndevos]

The following Python snippet makes a Redis build of cf34507b870124f99a68f13128274af3d708b50b on Arch Linux hang at 100% CPU.

import redis
rcon = redis.StrictRedis()
rcon.execute_command('PFADD', "testest2", "a", "", "b")

[badboy]

The bug is in hyperloglog.c: https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L319-322

hash = MurmurHash64A(ele,elesize,0);
...
while((hash & bit) == 0) {

Because the string is empty it hashes to 0. The following while loop thus never ends.

[mattsta]

Exactly right!

Redis's MurmurHash64A is hashing the empty string to 0, which infinite loops us right here: https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L322 because (0 & X) can't not be 0.

Another implementation of murmur had the same problem (hash of the empty string being 0) and did a very tiny fix to include the string terminator \0 as well: johnhaddon/cortex@6a2cad3

If we give hllAdd the length of the entire string including the null terminator (len = sdslen(arg)+1), we stop infinite looping and generate meaningful hash values. Of course, that does change all existing hash values. Better to catch this now before anybody has production data running against it.

Before:

Returning H of: 510903276987443985 (hash of "a")
Returning H of: 0 (hash of "")
<infinite loop>

After:

Returning H of: 7517249135209847859  (hash of "a")
Returning H of: 6351753276682545529  (hash of "")
Returning H of: 3063979243939886323  (hash of "b")

[antirez]

Fixed, thank you. The bug was triggered by the behavior of this specific hash function implementation, but actually the bug is unrelated to that since a legitimate element may hash to 00000...0000.

[antirez]

Well actually I think we should follow Matt advice and modify the hash function since it is uncool that a common value maps to a such rare pattern...

[antirez]

Ok guys I've considered this a bit more. My opinion:

• The principle of changing the hashing function so that the empty string does not map to "" is good.
• The fix for cortex is wrong. The problem is not fixed, just the empty string is never hashed :-) Moreover semantically everything gets more complex, you can't pass a binary string which is not null terminated, you do always 1 byte more of work. No good reasons IMHO.

The real source of issues is that simply I selected "0" as seed. The seed argument is how the hash value is initialized, and is as a side effect the hash value of the empty string. The only issue here is that when I wrote the original code, I failed to realize this and set it to zero. So I'm changing this value.

However I'm tankful to my lameness since otherwise the bug about counting bits could be still there, even if the probability of it actually being triggered is very small for us to ever notice, probably! But could be used as a DOS triggered by outside.

[mattsta]

👍 Two fixes for the price of one bug report! Happy to see the "empty string avoids hashing" scenario got re-fixed too.