X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/fe458402014cdd98a10179c85899f1eca0307534..7eb850ef0e437323e2d84157ddc2e6e82af57bbc:/src/ziplist.c diff --git a/src/ziplist.c b/src/ziplist.c index 4880013a..23bad45c 100644 --- a/src/ziplist.c +++ b/src/ziplist.c @@ -52,12 +52,23 @@ * String value with length less than or equal to 16383 bytes (14 bits). * |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes * String value with length greater than or equal to 16384 bytes. - * |1100____| - 1 byte + * |11000000| - 1 byte * Integer encoded as int16_t (2 bytes). - * |1101____| - 1 byte + * |11010000| - 1 byte * Integer encoded as int32_t (4 bytes). - * |1110____| - 1 byte + * |11100000| - 1 byte * Integer encoded as int64_t (8 bytes). + * |11110000| - 1 byte + * Integer encoded as 24 bit signed (3 bytes). + * |11111110| - 1 byte + * Integer encoded as 8 bit signed (1 byte). + * |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer. + * Unsigned integer from 0 to 12. The encoded value is actually from + * 1 to 13 because 0000 and 1111 can not be used, so 1 should be + * subtracted from the encoded 4 bit value to obtain the right value. + * |11111111| - End of ziplist. + * + * All the integers are represented in little endian byte order. */ #include @@ -69,20 +80,30 @@ #include "zmalloc.h" #include "util.h" #include "ziplist.h" -#include "endian.h" +#include "endianconv.h" #define ZIP_END 255 #define ZIP_BIGLEN 254 /* Different encoding/length possibilities */ -#define ZIP_STR_MASK (0xc0) -#define ZIP_INT_MASK (0x30) +#define ZIP_STR_MASK 0xc0 +#define ZIP_INT_MASK 0x30 #define ZIP_STR_06B (0 << 6) #define ZIP_STR_14B (1 << 6) #define ZIP_STR_32B (2 << 6) #define ZIP_INT_16B (0xc0 | 0<<4) #define ZIP_INT_32B (0xc0 | 1<<4) #define ZIP_INT_64B (0xc0 | 2<<4) +#define ZIP_INT_24B (0xc0 | 3<<4) +#define ZIP_INT_8B 0xfe +/* 4 bit integer immediate encoding */ +#define ZIP_INT_IMM_MASK 0x0f +#define ZIP_INT_IMM_MIN 0xf1 /* 11110001 */ +#define ZIP_INT_IMM_MAX 0xfd /* 11111101 */ +#define ZIP_INT_IMM_VAL(v) (v & ZIP_INT_IMM_MASK) + +#define INT24_MAX 0x7fffff +#define INT24_MIN (-INT24_MAX - 1) /* Macro to determine type */ #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK) @@ -93,13 +114,15 @@ #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) -#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+ZIPLIST_TAIL_OFFSET(zl)) -#define ZIPLIST_ENTRY_END(zl) ((zl)+ZIPLIST_BYTES(zl)-1) +#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) +#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1) /* We know a positive increment can only be 1 because entries can only be * pushed one at a time. */ #define ZIPLIST_INCR_LENGTH(zl,incr) { \ - if (ZIPLIST_LENGTH(zl) < UINT16_MAX) ZIPLIST_LENGTH(zl)+=incr; } + if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \ + ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \ +} typedef struct zlentry { unsigned int prevrawlensize, prevrawlen; @@ -109,20 +132,22 @@ typedef struct zlentry { unsigned char *p; } zlentry; -#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \ - (encoding) = (ptr[0]) & (ZIP_STR_MASK | ZIP_INT_MASK); \ - if (((encoding) & ZIP_STR_MASK) < ZIP_STR_MASK) { \ - /* String encoding: 2 MSBs */ \ - (encoding) &= ZIP_STR_MASK; \ - } \ +/* Extract the encoding from the byte pointed by 'ptr' and set it into + * 'encoding'. */ +#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \ + (encoding) = (ptr[0]); \ + if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \ } while(0) /* Return bytes needed to store integer encoded by 'encoding' */ static unsigned int zipIntSize(unsigned char encoding) { switch(encoding) { - case ZIP_INT_16B: return sizeof(int16_t); - case ZIP_INT_32B: return sizeof(int32_t); - case ZIP_INT_64B: return sizeof(int64_t); + case ZIP_INT_8B: return 1; + case ZIP_INT_16B: return 2; + case ZIP_INT_24B: return 3; + case ZIP_INT_32B: return 4; + case ZIP_INT_64B: return 8; + default: return 0; /* 4 bit immediate */ } assert(NULL); return 0; @@ -238,7 +263,7 @@ static void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len) { } else if ((prevlensize) == 5) { \ assert(sizeof((prevlensize)) == 4); \ memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \ - memrev32ifbe(&len); \ + memrev32ifbe(&prevlen); \ } \ } while(0); @@ -267,8 +292,14 @@ static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long if (string2ll((char*)entry,entrylen,&value)) { /* Great, the string can be encoded. Check what's the smallest * of our encoding types that can hold this value. */ - if (value >= INT16_MIN && value <= INT16_MAX) { + if (value >= 0 && value <= 12) { + *encoding = ZIP_INT_IMM_MIN+value; + } else if (value >= INT8_MIN && value <= INT8_MAX) { + *encoding = ZIP_INT_8B; + } else if (value >= INT16_MIN && value <= INT16_MAX) { *encoding = ZIP_INT_16B; + } else if (value >= INT24_MIN && value <= INT24_MAX) { + *encoding = ZIP_INT_24B; } else if (value >= INT32_MIN && value <= INT32_MAX) { *encoding = ZIP_INT_32B; } else { @@ -285,10 +316,16 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi int16_t i16; int32_t i32; int64_t i64; - if (encoding == ZIP_INT_16B) { + if (encoding == ZIP_INT_8B) { + ((int8_t*)p)[0] = (int8_t)value; + } else if (encoding == ZIP_INT_16B) { i16 = value; memcpy(p,&i16,sizeof(i16)); memrev16ifbe(p); + } else if (encoding == ZIP_INT_24B) { + i32 = value<<8; + memrev32ifbe(&i32); + memcpy(p,((uint8_t*)&i32)+1,sizeof(i32)-sizeof(uint8_t)); } else if (encoding == ZIP_INT_32B) { i32 = value; memcpy(p,&i32,sizeof(i32)); @@ -297,6 +334,8 @@ static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encodi i64 = value; memcpy(p,&i64,sizeof(i64)); memrev64ifbe(p); + } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { + /* Nothing to do, the value is stored in the encoding itself. */ } else { assert(NULL); } @@ -307,18 +346,27 @@ static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { int16_t i16; int32_t i32; int64_t i64, ret = 0; - if (encoding == ZIP_INT_16B) { + if (encoding == ZIP_INT_8B) { + ret = ((int8_t*)p)[0]; + } else if (encoding == ZIP_INT_16B) { memcpy(&i16,p,sizeof(i16)); memrev16ifbe(&i16); ret = i16; } else if (encoding == ZIP_INT_32B) { memcpy(&i32,p,sizeof(i32)); - memrev16ifbe(&i32); + memrev32ifbe(&i32); ret = i32; + } else if (encoding == ZIP_INT_24B) { + i32 = 0; + memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t)); + memrev32ifbe(&i32); + ret = i32>>8; } else if (encoding == ZIP_INT_64B) { memcpy(&i64,p,sizeof(i64)); - memrev16ifbe(&i64); + memrev64ifbe(&i64); ret = i64; + } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { + ret = (encoding & ZIP_INT_IMM_MASK)-1; } else { assert(NULL); } @@ -340,8 +388,8 @@ static zlentry zipEntry(unsigned char *p) { unsigned char *ziplistNew(void) { unsigned int bytes = ZIPLIST_HEADER_SIZE+1; unsigned char *zl = zmalloc(bytes); - ZIPLIST_BYTES(zl) = bytes; - ZIPLIST_TAIL_OFFSET(zl) = ZIPLIST_HEADER_SIZE; + ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); + ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); ZIPLIST_LENGTH(zl) = 0; zl[bytes-1] = ZIP_END; return zl; @@ -350,7 +398,7 @@ unsigned char *ziplistNew(void) { /* Resize the ziplist. */ static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) { zl = zrealloc(zl,len); - ZIPLIST_BYTES(zl) = len; + ZIPLIST_BYTES(zl) = intrev32ifbe(len); zl[len-1] = ZIP_END; return zl; } @@ -376,7 +424,7 @@ static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) { * The pointer "p" points to the first entry that does NOT need to be * updated, i.e. consecutive fields MAY need an update. */ static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) { - size_t curlen = ZIPLIST_BYTES(zl), rawlen, rawlensize; + size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize; size_t offset, noffset, extra; unsigned char *np; zlentry cur, next; @@ -406,8 +454,10 @@ static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p noffset = np-zl; /* Update tail offset when next element is not the tail element. */ - if ((zl+ZIPLIST_TAIL_OFFSET(zl)) != np) - ZIPLIST_TAIL_OFFSET(zl) += extra; + if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) { + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra); + } /* Move the tail to the back. */ memmove(np+rawlensize, @@ -450,33 +500,39 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsig totlen = p-first.p; if (totlen > 0) { if (p[0] != ZIP_END) { - /* Tricky: storing the prevlen in this entry might reduce or - * increase the number of bytes needed, compared to the current - * prevlen. Note that we can always store this length because - * it was previously stored by an entry that is being deleted. */ + /* Storing `prevrawlen` in this entry may increase or decrease the + * number of bytes required compare to the current `prevrawlen`. + * There always is room to store this, because it was previously + * stored by an entry that is now being deleted. */ nextdiff = zipPrevLenByteDiff(p,first.prevrawlen); - zipPrevEncodeLength(p-nextdiff,first.prevrawlen); + p -= nextdiff; + zipPrevEncodeLength(p,first.prevrawlen); /* Update offset for tail */ - ZIPLIST_TAIL_OFFSET(zl) -= totlen; + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(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. */ tail = zipEntry(p); - if (p[tail.headersize+tail.len] != ZIP_END) - ZIPLIST_TAIL_OFFSET(zl) += nextdiff; + if (p[tail.headersize+tail.len] != ZIP_END) { + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); + } /* Move tail to the front of the ziplist */ - memmove(first.p,p-nextdiff,ZIPLIST_BYTES(zl)-(p-zl)-1+nextdiff); + memmove(first.p,p, + intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1); } else { /* The entire tail was deleted. No need to move memory. */ - ZIPLIST_TAIL_OFFSET(zl) = (first.p-zl)-first.prevrawlen; + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe((first.p-zl)-first.prevrawlen); } /* Resize and update length */ offset = first.p-zl; - zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen+nextdiff); + zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff); ZIPLIST_INCR_LENGTH(zl,-deleted); p = zl+offset; @@ -490,7 +546,7 @@ static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsig /* Insert item at "p". */ static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { - size_t curlen = ZIPLIST_BYTES(zl), reqlen, prevlen = 0; + size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, prevlen = 0; size_t offset; int nextdiff = 0; unsigned char encoding = 0; @@ -543,17 +599,20 @@ static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsig zipPrevEncodeLength(p+reqlen,reqlen); /* Update offset for tail */ - ZIPLIST_TAIL_OFFSET(zl) += reqlen; + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); /* 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. */ tail = zipEntry(p+reqlen); - if (p[reqlen+tail.headersize+tail.len] != ZIP_END) - ZIPLIST_TAIL_OFFSET(zl) += nextdiff; + if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { + ZIPLIST_TAIL_OFFSET(zl) = + intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); + } } else { /* This element will be the new tail. */ - ZIPLIST_TAIL_OFFSET(zl) = p-zl; + ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl); } /* When nextdiff != 0, the raw length of the next entry has changed, so @@ -715,12 +774,11 @@ unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int return 0; } } else { - /* Try to compare encoded values */ + /* Try to compare encoded values. Don't compare encoding because + * different implementations may encoded integers differently. */ if (zipTryEncoding(sstr,slen,&sval,&sencoding)) { - if (entry.encoding == sencoding) { - zval = zipLoadInteger(p+entry.headersize,entry.encoding); - return zval == sval; - } + zval = zipLoadInteger(p+entry.headersize,entry.encoding); + return zval == sval; } } return 0; @@ -748,19 +806,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; @@ -785,8 +848,8 @@ unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int v /* Return length of ziplist. */ unsigned int ziplistLen(unsigned char *zl) { unsigned int len = 0; - if (ZIPLIST_LENGTH(zl) < UINT16_MAX) { - len = ZIPLIST_LENGTH(zl); + if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) { + len = intrev16ifbe(ZIPLIST_LENGTH(zl)); } else { unsigned char *p = zl+ZIPLIST_HEADER_SIZE; while (*p != ZIP_END) { @@ -795,14 +858,14 @@ unsigned int ziplistLen(unsigned char *zl) { } /* Re-store length if small enough */ - if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = len; + if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len); } return len; } /* Return ziplist blob size in bytes. */ size_t ziplistBlobLen(unsigned char *zl) { - return ZIPLIST_BYTES(zl); + return intrev32ifbe(ZIPLIST_BYTES(zl)); } void ziplistRepr(unsigned char *zl) { @@ -814,9 +877,9 @@ void ziplistRepr(unsigned char *zl) { "{total bytes %d} " "{length %u}\n" "{tail offset %u}\n", - ZIPLIST_BYTES(zl), - ZIPLIST_LENGTH(zl), - ZIPLIST_TAIL_OFFSET(zl)); + intrev32ifbe(ZIPLIST_BYTES(zl)), + intrev16ifbe(ZIPLIST_LENGTH(zl)), + intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))); p = ZIPLIST_ENTRY_HEAD(zl); while(*p != ZIP_END) { entry = zipEntry(p); @@ -917,7 +980,7 @@ void stress(int pos, int num, int maxsize, int dnum) { zl = ziplistDeleteRange(zl,0,1); } printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n", - i,ZIPLIST_BYTES(zl),num,posstr[pos],usec()-start); + i,intrev32ifbe(ZIPLIST_BYTES(zl)),num,posstr[pos],usec()-start); zfree(zl); } } @@ -972,6 +1035,22 @@ int randstring(char *target, unsigned int min, unsigned int max) { return len; } +void verify(unsigned char *zl, zlentry *e) { + int i; + int len = ziplistLen(zl); + zlentry _e; + + for (i = 0; i < len; i++) { + memset(&e[i], 0, sizeof(zlentry)); + e[i] = zipEntry(ziplistIndex(zl, i)); + + memset(&_e, 0, sizeof(zlentry)); + _e = zipEntry(ziplistIndex(zl, -len+i)); + + assert(memcmp(&e[i], &_e, sizeof(zlentry)) == 0); + } +} + int main(int argc, char **argv) { unsigned char *zl, *p; unsigned char *entry; @@ -1253,6 +1332,43 @@ int main(int argc, char **argv) { printf("SUCCESS\n\n"); } + printf("Regression test deleting next to last entries:\n"); + { + char v[3][257]; + zlentry e[3]; + int i; + + for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) { + memset(v[i], 'a' + i, sizeof(v[0])); + } + + v[0][256] = '\0'; + v[1][ 1] = '\0'; + v[2][256] = '\0'; + + zl = ziplistNew(); + for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) { + zl = ziplistPush(zl, (unsigned char *) v[i], strlen(v[i]), ZIPLIST_TAIL); + } + + verify(zl, e); + + assert(e[0].prevrawlensize == 1); + assert(e[1].prevrawlensize == 5); + assert(e[2].prevrawlensize == 1); + + /* Deleting entry 1 will increase `prevrawlensize` for entry 2 */ + unsigned char *p = e[1].p; + zl = ziplistDelete(zl, &p); + + verify(zl, e); + + assert(e[0].prevrawlensize == 1); + assert(e[1].prevrawlensize == 5); + + printf("SUCCESS\n\n"); + } + printf("Create long list and check indices:\n"); { zl = ziplistNew();