43 changes: 28 additions & 15 deletions src/t_zset.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -1238,15 +1238,18 @@ void zsetConvert(robj *zobj, int encoding) {
}

/* Convert the sorted set object into a ziplist if it is not already a ziplist
* and if the number of elements and the maximum element size is within the
* expected ranges. */
void zsetConvertToZiplistIfNeeded(robj *zobj, size_t maxelelen) {
* and if the number of elements and the maximum element size and total elements size
* are within the expected ranges. */
void zsetConvertToZiplistIfNeeded(robj *zobj, size_t maxelelen, size_t totelelen) {
if (zobj->encoding == OBJ_ENCODING_ZIPLIST) return;
zset *zset = zobj->ptr;

if (zset->zsl->length <= server.zset_max_ziplist_entries &&
maxelelen <= server.zset_max_ziplist_value)
zsetConvert(zobj,OBJ_ENCODING_ZIPLIST);
maxelelen <= server.zset_max_ziplist_value &&
ziplistSafeToAdd(NULL, totelelen))
{
zsetConvert(zobj,OBJ_ENCODING_ZIPLIST);
}
}

/* Return (by reference) the score of the specified member of the sorted set
Expand Down Expand Up @@ -1355,20 +1358,28 @@ int zsetAdd(robj *zobj, double score, sds ele, int *flags, double *newscore) {
}
return 1;
} else if (!xx) {
/* Optimize: check if the element is too large or the list
/* check if the element is too large or the list
* becomes too long *before* executing zzlInsert. */
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries ||
sdslen(ele) > server.zset_max_ziplist_value)
if (zzlLength(zobj->ptr)+1 > server.zset_max_ziplist_entries ||
sdslen(ele) > server.zset_max_ziplist_value ||
!ziplistSafeToAdd(zobj->ptr, sdslen(ele)))
{
zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
if (newscore) *newscore = score;
*flags |= ZADD_ADDED;
return 1;
} else {
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
if (newscore) *newscore = score;
*flags |= ZADD_ADDED;
return 1;
}
} else {
*flags |= ZADD_NOP;
return 1;
}
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
}

/* Note that the above block handling ziplist would have either returned or
* converted the key to skiplist. */
if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zobj->ptr;
zskiplistNode *znode;
dictEntry *de;
Expand Down Expand Up @@ -2180,7 +2191,7 @@ void zunionInterGenericCommand(client *c, robj *dstkey, int op) {
zsetopsrc *src;
zsetopval zval;
sds tmp;
size_t maxelelen = 0;
size_t maxelelen = 0, totelelen = 0;
robj *dstobj;
zset *dstzset;
zskiplistNode *znode;
Expand Down Expand Up @@ -2304,6 +2315,7 @@ void zunionInterGenericCommand(client *c, robj *dstkey, int op) {
tmp = zuiNewSdsFromValue(&zval);
znode = zslInsert(dstzset->zsl,score,tmp);
dictAdd(dstzset->dict,tmp,&znode->score);
totelelen += sdslen(tmp);
if (sdslen(tmp) > maxelelen) maxelelen = sdslen(tmp);
}
}
Expand Down Expand Up @@ -2340,6 +2352,7 @@ void zunionInterGenericCommand(client *c, robj *dstkey, int op) {
/* Remember the longest single element encountered,
* to understand if it's possible to convert to ziplist
* at the end. */
totelelen += sdslen(tmp);
if (sdslen(tmp) > maxelelen) maxelelen = sdslen(tmp);
/* Update the element with its initial score. */
dictSetKey(accumulator, de, tmp);
Expand Down Expand Up @@ -2380,7 +2393,7 @@ void zunionInterGenericCommand(client *c, robj *dstkey, int op) {
if (dbDelete(c->db,dstkey))
touched = 1;
if (dstzset->zsl->length) {
zsetConvertToZiplistIfNeeded(dstobj,maxelelen);
zsetConvertToZiplistIfNeeded(dstobj,maxelelen,totelelen);
dbAdd(c->db,dstkey,dstobj);
addReplyLongLong(c,zsetLength(dstobj));
signalModifiedKey(c,c->db,dstkey);
Expand Down
17 changes: 16 additions & 1 deletion src/ziplist.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -265,6 +265,17 @@
ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
}

/* Don't let ziplists grow over 1GB in any case, don't wanna risk overflow in
* zlbytes*/
#define ZIPLIST_MAX_SAFETY_SIZE (1<<30)
int ziplistSafeToAdd(unsigned char* zl, size_t add) {
size_t len = zl? ziplistBlobLen(zl): 0;
if (len + add > ZIPLIST_MAX_SAFETY_SIZE)
return 0;
return 1;
}


/* We use this function to receive information about a ziplist entry.
* Note that this is not how the data is actually encoded, is just what we
* get filled by a function in order to operate more easily. */
Expand Down Expand Up @@ -586,7 +597,8 @@ unsigned char *ziplistNew(void) {
}

/* Resize the ziplist. */
unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
unsigned char *ziplistResize(unsigned char *zl, size_t len) {
assert(len < UINT32_MAX);
zl = zrealloc(zl,len);
ZIPLIST_BYTES(zl) = intrev32ifbe(len);
zl[len-1] = ZIP_END;
Expand Down Expand Up @@ -898,6 +910,9 @@ unsigned char *ziplistMerge(unsigned char **first, unsigned char **second) {
/* Combined zl length should be limited within UINT16_MAX */
zllength = zllength < UINT16_MAX ? zllength : UINT16_MAX;

/* larger values can't be stored into ZIPLIST_BYTES */
assert(zlbytes < UINT32_MAX);

/* Save offset positions before we start ripping memory apart. */
size_t first_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*first));
size_t second_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*second));
Expand Down
1 change: 1 addition & 0 deletions src/ziplist.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -49,6 +49,7 @@ unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int v
unsigned int ziplistLen(unsigned char *zl);
size_t ziplistBlobLen(unsigned char *zl);
void ziplistRepr(unsigned char *zl);
int ziplistSafeToAdd(unsigned char* zl, size_t add);

#ifdef REDIS_TEST
int ziplistTest(int argc, char *argv[]);
Expand Down
18 changes: 17 additions & 1 deletion tests/support/util.tcl
View file
Original file line number Diff line number Diff line change
Expand Up @@ -109,7 +109,23 @@ proc wait_done_loading r {

# count current log lines in server's stdout
proc count_log_lines {srv_idx} {
set _ [exec wc -l < [srv $srv_idx stdout]]
set _ [string trim [exec wc -l < [srv $srv_idx stdout]]]
}

# returns the number of times a line with that pattern appears in a file
proc count_message_lines {file pattern} {
set res 0
# exec fails when grep exists with status other than 0 (when the patter wasn't found)
catch {
set res [string trim [exec grep $pattern $file 2> /dev/null | wc -l]]
}
return $res
}

# returns the number of times a line with that pattern appears in the log
proc count_log_message {srv_idx pattern} {
set stdout [srv $srv_idx stdout]
return [count_message_lines $stdout $pattern]
}

# verify pattern exists in server's sdtout after a certain line number
Expand Down
156 changes: 156 additions & 0 deletions tests/unit/violations.tcl
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,156 @@
# These tests consume massive amounts of memory, and are not
# suitable to be executed as part of the normal test suite
set ::str500 [string repeat x 500000000] ;# 500mb

# Utility function to write big argument into redis client connection
proc write_big_bulk {size} {
r write "\$$size\r\n"
while {$size >= 500000000} {
r write $::str500
incr size -500000000
}
if {$size > 0} {
r write [string repeat x $size]
}
r write "\r\n"
}

# One XADD with one huge 5GB field
# Expected to fail resulting in an empty stream
start_server [list overrides [list save ""] ] {
test {XADD one huge field} {
r config set proto-max-bulk-len 10000000000 ;#10gb
r config set client-query-buffer-limit 10000000000 ;#10gb
r write "*5\r\n\$4\r\nXADD\r\n\$2\r\nS1\r\n\$1\r\n*\r\n"
r write "\$1\r\nA\r\n"
write_big_bulk 5000000000 ;#5gb
r flush
catch {r read} err
assert_match {*too large*} $err
r xlen S1
} {0}
}

# One XADD with one huge (exactly nearly) 4GB field
# This uncovers the overflow in lpEncodeGetType
# Expected to fail resulting in an empty stream
start_server [list overrides [list save ""] ] {
test {XADD one huge field - 1} {
r config set proto-max-bulk-len 10000000000 ;#10gb
r config set client-query-buffer-limit 10000000000 ;#10gb
r write "*5\r\n\$4\r\nXADD\r\n\$2\r\nS1\r\n\$1\r\n*\r\n"
r write "\$1\r\nA\r\n"
write_big_bulk 4294967295 ;#4gb-1
r flush
catch {r read} err
assert_match {*too large*} $err
r xlen S1
} {0}
}

# Gradually add big stream fields using repeated XADD calls
start_server [list overrides [list save ""] ] {
test {several XADD big fields} {
r config set stream-node-max-bytes 0
for {set j 0} {$j<10} {incr j} {
r xadd stream * 1 $::str500 2 $::str500
}
r ping
r xlen stream
} {10}
}

# Add over 4GB to a single stream listpack (one XADD command)
# Expected to fail resulting in an empty stream
start_server [list overrides [list save ""] ] {
test {single XADD big fields} {
r write "*23\r\n\$4\r\nXADD\r\n\$1\r\nS\r\n\$1\r\n*\r\n"
for {set j 0} {$j<10} {incr j} {
r write "\$1\r\n$j\r\n"
write_big_bulk 500000000 ;#500mb
}
r flush
catch {r read} err
assert_match {*too large*} $err
r xlen S
} {0}
}

# Gradually add big hash fields using repeated HSET calls
# This reproduces the overflow in the call to ziplistResize
# Object will be converted to hashtable encoding
start_server [list overrides [list save ""] ] {
r config set hash-max-ziplist-value 1000000000 ;#1gb
test {hash with many big fields} {
for {set j 0} {$j<10} {incr j} {
r hset h $j $::str500
}
r object encoding h
} {hashtable}
}

# Add over 4GB to a single hash field (one HSET command)
# Object will be converted to hashtable encoding
start_server [list overrides [list save ""] ] {
test {hash with one huge field} {
catch {r config set hash-max-ziplist-value 10000000000} ;#10gb
r config set proto-max-bulk-len 10000000000 ;#10gb
r config set client-query-buffer-limit 10000000000 ;#10gb
r write "*4\r\n\$4\r\nHSET\r\n\$2\r\nH1\r\n"
r write "\$1\r\nA\r\n"
write_big_bulk 5000000000 ;#5gb
r flush
r read
r object encoding H1
} {hashtable}
}

# Add over 4GB to a single list member (one LPUSH command)
# Currently unsupported, and expected to fail rather than being truncated
# Expected to fail resulting in a non-existing list
start_server [list overrides [list save ""] ] {
test {list with one huge field} {
r config set proto-max-bulk-len 10000000000 ;#10gb
r config set client-query-buffer-limit 10000000000 ;#10gb
r write "*3\r\n\$5\r\nLPUSH\r\n\$2\r\nL1\r\n"
write_big_bulk 5000000000 ;#5gb
r flush
catch {r read} err
assert_match {*too large*} $err
r exists L1
} {0}
}

# SORT which attempts to store an element larger than 4GB into a list.
# Currently unsupported and results in an assertion instead of truncation
start_server [list overrides [list save ""] ] {
test {SORT adds huge field to list} {
r config set proto-max-bulk-len 10000000000 ;#10gb
r config set client-query-buffer-limit 10000000000 ;#10gb
r write "*3\r\n\$3\r\nSET\r\n\$2\r\nS1\r\n"
write_big_bulk 5000000000 ;#5gb
r flush
r read
assert_equal [r strlen S1] 5000000000
r set S2 asdf
r sadd myset 1 2
r mset D1 1 D2 2
catch {r sort myset by D* get S* store mylist}
# assert_equal [count_log_message 0 "crashed by signal"] 0 - not suitable for 6.0
assert_equal [count_log_message 0 "ASSERTION FAILED"] 1
}
}

# SORT which stores an integer encoded element into a list.
# Just for coverage, no news here.
start_server [list overrides [list save ""] ] {
test {SORT adds integer field to list} {
r set S1 asdf
r set S2 123 ;# integer encoded
assert_encoding "int" S2
r sadd myset 1 2
r mset D1 1 D2 2
r sort myset by D* get S* store mylist
r llen mylist
} {2}
}