Sanitize dump payload: ziplist, listpack, zipmap, intset, stream

When loading an encoded payload we will at least do a shallow validation to
check that the size that's encoded in the payload matches the size of the
allocation.
This let's us later use this encoded size to make sure the various offsets
inside encoded payload don't reach outside the allocation, if they do, we'll
assert/panic, but at least we won't segfault or smear memory.

We can also do 'deep' validation which runs on all the records of the encoded
payload and validates that they don't contain invalid offsets. This lets us
detect corruptions early and reject a RESTORE command rather than accepting
it and asserting (crashing) later when accessing that payload via some command.

configuration:
- adding ACL flag skip-sanitize-payload
- adding config sanitize-dump-payload [yes/no/clients]

For now, we don't have a good way to ensure MIGRATE in cluster resharding isn't
being slowed down by these sanitation, so i'm setting the default value to `no`,
but later on it should be set to `clients` by default.

changes:
- changing rdbReportError not to `exit` in RESTORE command
- adding a new stat to be able to later check if cluster MIGRATE isn't being
  slowed down by sanitation.

1 files changed, 239 insertions, 57 deletions

diff --git a/src/ziplist.c b/src/ziplist.c
index dd7452006..a8ab57cfe 100644
--- a/src/ziplist.c
+++ b/src/ziplist.c
@@ -152,6 +152,7 @@
  *
  * Copyright (c) 2009-2012, Pieter Noordhuis <pcnoordhuis at gmail dot com>
  * Copyright (c) 2009-2017, Salvatore Sanfilippo <antirez at gmail dot com>
+ * Copyright (c) 2020, Redis Labs, Inc
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -298,10 +299,34 @@ typedef struct zlentry {
 /* Extract the encoding from the byte pointed by 'ptr' and set it into
  * 'encoding' field of the zlentry structure. */
 #define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
-    (encoding) = (ptr[0]); \
+    (encoding) = ((ptr)[0]); \
     if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
 } while(0)
 
+#define ZIP_ENCODING_SIZE_INVALID 0xff
+/* Return the number of bytes required to encode the entry type + length.
+ * On error, return ZIP_ENCODING_SIZE_INVALID */
+static inline unsigned int zipEncodingLenSize(unsigned char encoding) {
+    if (encoding == ZIP_INT_16B || encoding == ZIP_INT_32B ||
+        encoding == ZIP_INT_24B || encoding == ZIP_INT_64B ||
+        encoding == ZIP_INT_8B)
+        return 1;
+    if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
+        return 1;
+    if (encoding == ZIP_STR_06B)
+        return 1;
+    if (encoding == ZIP_STR_14B)
+        return 2;
+    if (encoding == ZIP_STR_32B)
+        return 5;
+    return ZIP_ENCODING_SIZE_INVALID;
+}
+
+#define ZIP_ASSERT_ENCODING(encoding) do {                          \
+    if (zipEncodingLenSize(encoding) == ZIP_ENCODING_SIZE_INVALID)     \
+        panic("Invalid encoding 0x%02X", encoding);                 \
+} while (0)
+
 /* Return bytes needed to store integer encoded by 'encoding'. */
 unsigned int zipIntSize(unsigned char encoding) {
     switch(encoding) {
@@ -313,7 +338,7 @@ unsigned int zipIntSize(unsigned char encoding) {
     }
     if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
         return 0; /* 4 bit immediate */
-    panic("Invalid integer encoding 0x%02X", encoding);
+    /* bad encoding, covered by a previous call to ZIP_ASSERT_ENCODING */
     return 0;
 }
 
@@ -365,11 +390,10 @@ unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, uns
 
 /* Decode the entry encoding type and data length (string length for strings,
  * number of bytes used for the integer for integer entries) encoded in 'ptr'.
- * The 'encoding' variable will hold the entry encoding, the 'lensize'
+ * The 'encoding' variable is input, extracted by the caller, the 'lensize'
  * variable will hold the number of bytes required to encode the entry
  * length, and the 'len' variable will hold the entry length. */
 #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    \
-    ZIP_ENTRY_ENCODING((ptr), (encoding));                                     \
     if ((encoding) < ZIP_STR_MASK) {                                           \
         if ((encoding) == ZIP_STR_06B) {                                       \
             (lensize) = 1;                                                     \
@@ -384,7 +408,8 @@ unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, uns
                     ((ptr)[3] <<  8) |                                         \
                     ((ptr)[4]);                                                \
         } else {                                                               \
-            panic("Invalid string encoding 0x%02X", (encoding));               \
+            len = 0; /* bad encoding, dead code */                             \
+            /* covered by a previous call to ZIP_ASSERT_ENCODING */            \
         }                                                                      \
     } else {                                                                   \
         (lensize) = 1;                                                         \
@@ -440,9 +465,10 @@ unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
     if ((prevlensize) == 1) {                                                  \
         (prevlen) = (ptr)[0];                                                  \
     } else if ((prevlensize) == 5) {                                           \
-        assert(sizeof((prevlen)) == 4);                                        \
-        memcpy(&(prevlen), ((char*)(ptr)) + 1, 4);                             \
-        memrev32ifbe(&prevlen);                                                \
+        (prevlen) = ((ptr)[4] << 24) |                                         \
+                    ((ptr)[3] << 16) |                                         \
+                    ((ptr)[2] <<  8) |                                         \
+                    ((ptr)[1]);                                                \
     }                                                                          \
 } while(0)
 
@@ -467,14 +493,6 @@ int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
     return zipStorePrevEntryLength(NULL, len) - prevlensize;
 }
 
-/* Return the total number of bytes used by the entry pointed to by 'p'. */
-unsigned int zipRawEntryLength(unsigned char *p) {
-    unsigned int prevlensize, encoding, lensize, len;
-    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
-    ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
-    return prevlensize + lensize + len;
-}
-
 /* Check if string pointed to by 'entry' can be encoded as an integer.
  * Stores the integer value in 'v' and its encoding in 'encoding'. */
 int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
@@ -565,13 +583,85 @@ int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
     return ret;
 }
 
-/* Return a struct with all information about an entry. */
+/* Fills a struct with all information about an entry.
+ * This function is the "unsafe" alternative to the one blow.
+ * Generally, all function that return a pointer to an element in the ziplist
+ * will assert that this element is valid, so it can be freely used.
+ * Generally functions such ziplistGet assume the input pointer is already
+ * validated (since it's the return value of another function). */
 void zipEntry(unsigned char *p, zlentry *e) {
+    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
+    ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding);
+    ZIP_ASSERT_ENCODING(e->encoding);
+    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
+    e->headersize = e->prevrawlensize + e->lensize;
+    e->p = p;
+}
 
+/* Fills a struct with all information about an entry.
+ * This function is safe to use on untrusted pointers, it'll make sure not to
+ * try to access memory outside the ziplist payload.
+ * Returns 1 if the entry is valid, and 0 otherwise. */
+static inline int zipEntrySafe(unsigned char* zl, size_t zlbytes, unsigned char *p, zlentry *e, int validate_prevlen) {
+#define OUT_OF_RANGE(p) ( \
+        (p) < zl + ZIPLIST_HEADER_SIZE || \
+        (p) > zl + zlbytes - ZIPLIST_END_SIZE)
+
+    /* Make sure the pointer doesn't rech outside the edge of the ziplist */
+    if (OUT_OF_RANGE(p))
+        return 0;
+
+    /* Make sure the encoded prevlen header doesn't reach outside the allocation */
+    ZIP_DECODE_PREVLENSIZE(p, e->prevrawlensize);
+    if (OUT_OF_RANGE(p + e->prevrawlensize))
+        return 0;
+
+    /* Make sure encoded entry header is valid. */
+    ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding);
+    e->lensize = zipEncodingLenSize(e->encoding);
+    if (e->lensize == ZIP_ENCODING_SIZE_INVALID)
+        return 0;
+
+    /* Make sure the encoded entry header doesn't reach outside the allocation */
+    if (OUT_OF_RANGE(p + e->prevrawlensize + e->lensize))
+        return 0;
+
+    /* Decode the prevlen and entry len headers. */
     ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
     ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
     e->headersize = e->prevrawlensize + e->lensize;
+
+    /* Make sure the entry doesn't rech outside the edge of the ziplist */
+    if (OUT_OF_RANGE(p + e->headersize + e->len))
+        return 0;
+
+    /* Make sure prevlen doesn't rech outside the edge of the ziplist */
+    if (validate_prevlen && OUT_OF_RANGE(p - e->prevrawlen))
+        return 0;
+
     e->p = p;
+    return 1;
+#undef OUT_OF_RANGE
+}
+
+/* Return the total number of bytes used by the entry pointed to by 'p'. */
+static inline unsigned int zipRawEntryLengthSafe(unsigned char* zl, size_t zlbytes, unsigned char *p) {
+    zlentry e;
+    assert(zipEntrySafe(zl, zlbytes, p, &e, 0));
+    return e.headersize + e.len;
+}
+
+/* Return the total number of bytes used by the entry pointed to by 'p'. */
+static inline unsigned int zipRawEntryLength(unsigned char *p) {
+    zlentry e;
+    zipEntry(p, &e);
+    return e.headersize + e.len;
+}
+
+/* Validate that the entry doesn't reach outside the ziplist allocation. */
+static inline void zipAssertValidEntry(unsigned char* zl, size_t zlbytes, unsigned char *p) {
+    zlentry e;
+    assert(zipEntrySafe(zl, zlbytes, p, &e, 1));
 }
 
 /* Create a new empty ziplist. */
@@ -625,7 +715,7 @@ unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
     /* Empty ziplist */
     if (p[0] == ZIP_END) return zl;
 
-    zipEntry(p, &cur);
+    zipEntry(p, &cur); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */
     firstentrylen = prevlen = cur.headersize + cur.len;
     prevlensize = zipStorePrevEntryLength(NULL, prevlen);
     prevoffset = p - zl;
@@ -633,7 +723,7 @@ unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
 
     /* Iterate ziplist to find out how many extra bytes do we need to update it. */
     while (p[0] != ZIP_END) {
-        zipEntry(p, &cur);
+        assert(zipEntrySafe(zl, curlen, p, &cur, 0));
 
         /* Abort when "prevlen" has not changed. */
         if (cur.prevrawlen == prevlen) break;
@@ -690,7 +780,7 @@ unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
 
     /* Iterate all entries that need to be updated tail to head. */
     while (cnt) {
-        zipEntry(zl + prevoffset, &cur);
+        zipEntry(zl + prevoffset, &cur); /* no need for "safe" variant since we already iterated on all these entries above. */
         rawlen = cur.headersize + cur.len;
         /* Move entry to tail and reset prevlen. */
         memmove(p - (rawlen - cur.prevrawlensize), 
@@ -717,15 +807,18 @@ unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int
     size_t offset;
     int nextdiff = 0;
     zlentry first, tail;
+    size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl));
 
-    zipEntry(p, &first);
+    zipEntry(p, &first); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */
     for (i = 0; p[0] != ZIP_END && i < num; i++) {
-        p += zipRawEntryLength(p);
+        p += zipRawEntryLengthSafe(zl, zlbytes, p);
         deleted++;
     }
 
+    assert(p >= first.p);
     totlen = p-first.p; /* Bytes taken by the element(s) to delete. */
     if (totlen > 0) {
+        uint32_t set_tail;
         if (p[0] != ZIP_END) {
             /* Storing `prevrawlen` in this entry may increase or decrease the
              * number of bytes required compare to the current `prevrawlen`.
@@ -738,36 +831,44 @@ unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int
              * had a 5 bytes prevlen header, so there is for sure at least
              * 5 bytes free and we need just 4. */
             p -= nextdiff;
+            assert(p >= first.p && p<zl+zlbytes-1);
             zipStorePrevEntryLength(p,first.prevrawlen);
 
             /* Update offset for tail */
-            ZIPLIST_TAIL_OFFSET(zl) =
-                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
+            set_tail = intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen;
 
             /* When the tail contains more than one entry, we need to take
              * "nextdiff" in account as well. Otherwise, a change in the
              * size of prevlen doesn't have an effect on the *tail* offset. */
-            zipEntry(p, &tail);
+            assert(zipEntrySafe(zl, zlbytes, p, &tail, 1));
             if (p[tail.headersize+tail.len] != ZIP_END) {
-                ZIPLIST_TAIL_OFFSET(zl) =
-                   intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
+                set_tail = set_tail + nextdiff;
             }
 
             /* Move tail to the front of the ziplist */
-            memmove(first.p,p,
-                intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
+            /* since we asserted that p >= first.p. we know totlen >= 0,
+             * so we know that p > first.p and this is guaranteed not to reach
+             * beyond the allocation, even if the entries lens are corrupted. */
+            size_t bytes_to_move = zlbytes-(p-zl)-1;
+            memmove(first.p,p,bytes_to_move);
         } else {
             /* The entire tail was deleted. No need to move memory. */
-            ZIPLIST_TAIL_OFFSET(zl) =
-                intrev32ifbe((first.p-zl)-first.prevrawlen);
+            set_tail = (first.p-zl)-first.prevrawlen;
         }
 
-        /* Resize and update length */
+        /* Resize the ziplist */
         offset = first.p-zl;
-        zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
-        ZIPLIST_INCR_LENGTH(zl,-deleted);
+        zlbytes -= totlen - nextdiff;
+        zl = ziplistResize(zl, zlbytes);
         p = zl+offset;
 
+        /* Update record count */
+        ZIPLIST_INCR_LENGTH(zl,-deleted);
+
+        /* Set the tail offset computed above */
+        assert(set_tail <= zlbytes - ZIPLIST_END_SIZE);
+        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(set_tail);
+
         /* When nextdiff != 0, the raw length of the next entry has changed, so
          * we need to cascade the update throughout the ziplist */
         if (nextdiff != 0)
@@ -778,7 +879,7 @@ unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int
 
 /* Insert item at "p". */
 unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
-    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
+    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, newlen;
     unsigned int prevlensize, prevlen = 0;
     size_t offset;
     int nextdiff = 0;
@@ -794,7 +895,7 @@ unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned cha
     } else {
         unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
         if (ptail[0] != ZIP_END) {
-            prevlen = zipRawEntryLength(ptail);
+            prevlen = zipRawEntryLengthSafe(zl, curlen, ptail);
         }
     }
 
@@ -824,7 +925,8 @@ unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned cha
 
     /* Store offset because a realloc may change the address of zl. */
     offset = p-zl;
-    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
+    newlen = curlen+reqlen+nextdiff;
+    zl = ziplistResize(zl,newlen);
     p = zl+offset;
 
     /* Apply memory move when necessary and update tail offset. */
@@ -845,7 +947,7 @@ unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned cha
         /* When the tail contains more than one entry, we need to take
          * "nextdiff" in account as well. Otherwise, a change in the
          * size of prevlen doesn't have an effect on the *tail* offset. */
-        zipEntry(p+reqlen, &tail);
+        assert(zipEntrySafe(zl, newlen, p+reqlen, &tail, 1));
         if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
             ZIPLIST_TAIL_OFFSET(zl) =
                 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
@@ -1002,23 +1104,35 @@ unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int sle
 unsigned char *ziplistIndex(unsigned char *zl, int index) {
     unsigned char *p;
     unsigned int prevlensize, prevlen = 0;
+    size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl));
     if (index < 0) {
         index = (-index)-1;
         p = ZIPLIST_ENTRY_TAIL(zl);
         if (p[0] != ZIP_END) {
+            /* No need for "safe" check: when going backwards, we know the header
+             * we're parsing is in the range, we just need to assert (below) that
+             * the size we take doesn't cause p to go outside the allocation. */
             ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
             while (prevlen > 0 && index--) {
                 p -= prevlen;
+                assert(p >= zl + ZIPLIST_HEADER_SIZE && p < zl + zlbytes - ZIPLIST_END_SIZE);
                 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
             }
         }
     } else {
         p = ZIPLIST_ENTRY_HEAD(zl);
-        while (p[0] != ZIP_END && index--) {
-            p += zipRawEntryLength(p);
+        while (index--) {
+            /* Use the "safe" length: When we go forward, we need to be careful
+             * not to decode an entry header if it's past the ziplist allocation. */
+            p += zipRawEntryLengthSafe(zl, zlbytes, p);
+            if (p[0] == ZIP_END)
+                break;
         }
     }
-    return (p[0] == ZIP_END || index > 0) ? NULL : p;
+    if (p[0] == ZIP_END || index > 0)
+        return NULL;
+    zipAssertValidEntry(zl, zlbytes, p);
+    return p;
 }
 
 /* Return pointer to next entry in ziplist.
@@ -1029,6 +1143,7 @@ unsigned char *ziplistIndex(unsigned char *zl, int index) {
  * The element after 'p' is returned, otherwise NULL if we are at the end. */
 unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
     ((void) zl);
+    size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl));
 
     /* "p" could be equal to ZIP_END, caused by ziplistDelete,
      * and we should return NULL. Otherwise, we should return NULL
@@ -1042,6 +1157,7 @@ unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
         return NULL;
     }
 
+    zipAssertValidEntry(zl, zlbytes, p);
     return p;
 }
 
@@ -1060,7 +1176,10 @@ unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
     } else {
         ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
         assert(prevlen > 0);
-        return p-prevlen;
+        p-=prevlen;
+        size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl));
+        zipAssertValidEntry(zl, zlbytes, p);
+        return p;
     }
 }
 
@@ -1073,7 +1192,7 @@ unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *sl
     if (p == NULL || p[0] == ZIP_END) return 0;
     if (sstr) *sstr = NULL;
 
-    zipEntry(p, &entry);
+    zipEntry(p, &entry); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */
     if (ZIP_IS_STR(entry.encoding)) {
         if (sstr) {
             *slen = entry.len;
@@ -1121,7 +1240,7 @@ unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int
     long long zval, sval;
     if (p[0] == ZIP_END) return 0;
 
-    zipEntry(p, &entry);
+    zipEntry(p, &entry); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */
     if (ZIP_IS_STR(entry.encoding)) {
         /* Raw compare */
         if (entry.len == slen) {
@@ -1142,23 +1261,23 @@ unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int
 
 /* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
  * between every comparison. Returns NULL when the field could not be found. */
-unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
+unsigned char *ziplistFind(unsigned char *zl, unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
     int skipcnt = 0;
     unsigned char vencoding = 0;
     long long vll = 0;
+    size_t zlbytes = ziplistBlobLen(zl);
 
     while (p[0] != ZIP_END) {
-        unsigned int prevlensize, encoding, lensize, len;
+        struct zlentry e;
         unsigned char *q;
 
-        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
-        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
-        q = p + prevlensize + lensize;
+        assert(zipEntrySafe(zl, zlbytes, p, &e, 1));
+        q = p + e.prevrawlensize + e.lensize;
 
         if (skipcnt == 0) {
             /* Compare current entry with specified entry */
-            if (ZIP_IS_STR(encoding)) {
-                if (len == vlen && memcmp(q, vstr, vlen) == 0) {
+            if (ZIP_IS_STR(e.encoding)) {
+                if (e.len == vlen && memcmp(q, vstr, vlen) == 0) {
                     return p;
                 }
             } else {
@@ -1180,7 +1299,7 @@ unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int v
                  * 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);
+                    long long ll = zipLoadInteger(q, e.encoding);
                     if (ll == vll) {
                         return p;
                     }
@@ -1195,7 +1314,7 @@ unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int v
         }
 
         /* Move to next entry */
-        p = q + len;
+        p = q + e.len;
     }
 
     return NULL;
@@ -1208,8 +1327,9 @@ unsigned int ziplistLen(unsigned char *zl) {
         len = intrev16ifbe(ZIPLIST_LENGTH(zl));
     } else {
         unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
+        size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl));
         while (*p != ZIP_END) {
-            p += zipRawEntryLength(p);
+            p += zipRawEntryLengthSafe(zl, zlbytes, p);
             len++;
         }
 
@@ -1228,6 +1348,7 @@ void ziplistRepr(unsigned char *zl) {
     unsigned char *p;
     int index = 0;
     zlentry entry;
+    size_t zlbytes = ziplistBlobLen(zl);
 
     printf(
         "{total bytes %u} "
@@ -1238,7 +1359,7 @@ void ziplistRepr(unsigned char *zl) {
         intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)));
     p = ZIPLIST_ENTRY_HEAD(zl);
     while(*p != ZIP_END) {
-        zipEntry(p, &entry);
+        assert(zipEntrySafe(zl, zlbytes, p, &entry, 1));
         printf(
             "{\n"
                 "\taddr 0x%08lx,\n"
@@ -1282,6 +1403,63 @@ void ziplistRepr(unsigned char *zl) {
     printf("{end}\n\n");
 }
 
+/* Validate the integrity of the data stracture.
+ * when `deep` is 0, only the integrity of the header is validated.
+ * when `deep` is 1, we scan all the entries one by one. */
+int ziplistValidateIntegrity(unsigned char *zl, size_t size, int deep) {
+    /* check that we can actually read the header. (and ZIP_END) */
+    if (size < ZIPLIST_HEADER_SIZE + ZIPLIST_END_SIZE)
+        return 0;
+
+    /* check that the encoded size in the header must match the allocated size. */
+    size_t bytes = intrev32ifbe(ZIPLIST_BYTES(zl));
+    if (bytes != size)
+        return 0;
+
+    /* the last byte must be the terminator. */
+    if (zl[size - ZIPLIST_END_SIZE] != ZIP_END)
+        return 0;
+
+    /* make sure the tail offset isn't reaching outside the allocation. */
+    if (intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)) > size - ZIPLIST_END_SIZE)
+        return 0;
+
+    if (!deep)
+        return 1;
+
+    unsigned int count = 0;
+    unsigned char *p = ZIPLIST_ENTRY_HEAD(zl);
+    unsigned char *prev = NULL;
+    size_t prev_raw_size = 0;
+    while(*p != ZIP_END) {
+        struct zlentry e;
+        /* Decode the entry headers and fail if invalid or reaches outside the allocation */
+        if (!zipEntrySafe(zl, size, p, &e, 1))
+            return 0;
+
+        /* Make sure the record stating the prev entry size is correct. */
+        if (e.prevrawlen != prev_raw_size)
+            return 0;
+
+        /* Move to the next entry */
+        prev_raw_size = e.headersize + e.len;
+        prev = p;
+        p += e.headersize + e.len;
+        count++;
+    }
+
+    /* Make sure the <zltail> entry really do point to the start of the last entry. */
+    if (prev != ZIPLIST_ENTRY_TAIL(zl))
+        return 0;
+
+    /* Check that the count in the header is correct */
+    unsigned int header_count = intrev16ifbe(ZIPLIST_LENGTH(zl));
+    if (header_count != UINT16_MAX && count != header_count)
+        return 0;
+
+    return 1;
+}
+
 #ifdef REDIS_TEST
 #include <sys/time.h>
 #include "adlist.h"
@@ -1784,6 +1962,7 @@ int ziplistTest(int argc, char **argv) {
 
     printf("Create long list and check indices:\n");
     {
+        unsigned long long start = usec();
         zl = ziplistNew();
         char buf[32];
         int i,len;
@@ -1800,7 +1979,7 @@ int ziplistTest(int argc, char **argv) {
             assert(ziplistGet(p,NULL,NULL,&value));
             assert(999-i == value);
         }
-        printf("SUCCESS\n\n");
+        printf("SUCCESS. usec=%lld\n\n", usec()-start);
         zfree(zl);
     }
 
@@ -1907,6 +2086,7 @@ int ziplistTest(int argc, char **argv) {
 
     printf("Stress with random payloads of different encoding:\n");
     {
+        unsigned long long start = usec();
         int i,j,len,where;
         unsigned char *p;
         char buf[1024];
@@ -1979,13 +2159,15 @@ int ziplistTest(int argc, char **argv) {
             zfree(zl);
             listRelease(ref);
         }
-        printf("SUCCESS\n\n");
+        printf("Done. usec=%lld\n\n", usec()-start);
     }
 
     printf("Stress with variable ziplist size:\n");
     {
+        unsigned long long start = usec();
         stress(ZIPLIST_HEAD,100000,16384,256);
         stress(ZIPLIST_TAIL,100000,16384,256);
+        printf("Done. usec=%lld\n\n", usec()-start);
     }
 
     printf("Stress __ziplistCascadeUpdate:\n");