ziplistFind(): don't assume that entries are comparable by encoding.

Because Redis 2.6 introduced new integer encodings it is no longer true
that if two entries have a different encoding they are not equal.

An old ziplist can be loaded from an RDB file generated with Redis 2.4,
in this case for instance a small unsigned integers is encoded with a
16 bit encoding, while in Redis 2.6 a more specific 8 bit encoding
format is used.

Because of this bug hashes ended with duplicated values or fields lookup
failed, causing many bad behaviors.
This in turn caused a crash while converting the ziplist encoded hash into
a real hash table because an assertion was raised on duplicated elements.

This commit fixes issue #547.

Many thanks to Pinterest's Marty Weiner and colleagues for discovering
the problem and helping us in the debugging process.

diff --git a/src/ziplist.c b/src/ziplist.c
index 31e61633e5b1ad494468b021658ed75f455cf2cc..50167651ba1d568940b05f2f2f86abafd9e5dffc 100644 (file)
--- a/src/ziplist.c
+++ b/src/ziplist.c
@@ -805,19 +805,24 @@ unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int v
                     return p;
                 }
             } else {
-                /* Find out if the specified entry can be encoded */
+                /* Find out if the searched field can be encoded. Note that
+                 * we do it only the first time, once done vencoding is set
+                 * to non-zero and vll is set to the integer value. */
                 if (vencoding == 0) {
-                    /* UINT_MAX when the entry CANNOT be encoded */
                     if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
+                        /* If the entry can't be encoded we set it to
+                         * UCHAR_MAX so that we don't retry again the next
+                         * time. */
                         vencoding = UCHAR_MAX;
                     }
-
                     /* Must be non-zero by now */
                     assert(vencoding);
                 }
 
-                /* Compare current entry with specified entry */
-                if (encoding == vencoding) {
+                /* Compare current entry with specified entry, do it only
+                 * if vencoding != UCHAR_MAX because if there is no encoding
+                 * possible for the field it can't be a valid integer. */
+                if (vencoding != UCHAR_MAX) {
                     long long ll = zipLoadInteger(q, encoding);
                     if (ll == vll) {
                         return p;