diff options
Diffstat (limited to 'src/ziplist.c')
| -rw-r--r-- | src/ziplist.c | 296 |
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"); |