X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/70b4b320ae1d04dd087ae9336bdd962a9615fbfe..f483ce5f:/redis.c diff --git a/redis.c b/redis.c index efaeb0f1..085d3553 100644 --- a/redis.c +++ b/redis.c @@ -77,7 +77,6 @@ #include "zipmap.h" /* Compact dictionary-alike data structure */ #include "ziplist.h" /* Compact list data structure */ #include "sha1.h" /* SHA1 is used for DEBUG DIGEST */ -#include "release.h" /* Release and/or git repository information */ /* Error codes */ #define REDIS_OK 0 @@ -130,11 +129,11 @@ #define REDIS_ENCODING_INT 1 /* Encoded as integer */ #define REDIS_ENCODING_HT 2 /* Encoded as hash table */ #define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */ -#define REDIS_ENCODING_LIST 4 /* Encoded as zipmap */ +#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */ #define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */ static char* strencoding[] = { - "raw", "int", "hashtable", "zipmap", "list", "ziplist" + "raw", "int", "hashtable", "zipmap", "linkedlist", "ziplist" }; /* Object types only used for dumping to disk */ @@ -538,7 +537,7 @@ typedef struct zset { #define REDIS_SHARED_INTEGERS 10000 struct sharedObjectsStruct { - robj *crlf, *ok, *err, *emptybulk, *czero, *cone, *pong, *space, + robj *crlf, *ok, *err, *emptybulk, *czero, *cone, *cnegone, *pong, *space, *colon, *nullbulk, *nullmultibulk, *queued, *emptymultibulk, *wrongtypeerr, *nokeyerr, *syntaxerr, *sameobjecterr, *outofrangeerr, *plus, @@ -575,6 +574,8 @@ typedef struct iojob { } iojob; /*================================ Prototypes =============================== */ +char *redisGitSHA1(void); +char *redisGitDirty(void); static void freeStringObject(robj *o); static void freeListObject(robj *o); @@ -1258,7 +1259,7 @@ static dictType keyptrDictType = { NULL, /* key dup */ NULL, /* val dup */ dictSdsKeyCompare, /* key compare */ - dictSdsDestructor, /* key destructor */ + NULL, /* key destructor */ NULL /* val destructor */ }; @@ -1677,6 +1678,7 @@ static void createSharedObjects(void) { shared.emptybulk = createObject(REDIS_STRING,sdsnew("$0\r\n\r\n")); shared.czero = createObject(REDIS_STRING,sdsnew(":0\r\n")); shared.cone = createObject(REDIS_STRING,sdsnew(":1\r\n")); + shared.cnegone = createObject(REDIS_STRING,sdsnew(":-1\r\n")); shared.nullbulk = createObject(REDIS_STRING,sdsnew("$-1\r\n")); shared.nullmultibulk = createObject(REDIS_STRING,sdsnew("*-1\r\n")); shared.emptymultibulk = createObject(REDIS_STRING,sdsnew("*0\r\n")); @@ -3057,7 +3059,7 @@ static robj *createListObject(void) { list *l = listCreate(); robj *o = createObject(REDIS_LIST,l); listSetFreeMethod(l,decrRefCount); - o->encoding = REDIS_ENCODING_LIST; + o->encoding = REDIS_ENCODING_LINKEDLIST; return o; } @@ -3099,7 +3101,7 @@ static void freeStringObject(robj *o) { static void freeListObject(robj *o) { switch (o->encoding) { - case REDIS_ENCODING_LIST: + case REDIS_ENCODING_LINKEDLIST: listRelease((list*) o->ptr); break; case REDIS_ENCODING_ZIPLIST: @@ -3531,12 +3533,10 @@ static robj *dbRandomKey(redisDb *db) { /* Delete a key, value, and associated expiration entry if any, from the DB */ static int dbDelete(redisDb *db, robj *key) { - int retval; - - if (dictSize(db->expires)) dictDelete(db->expires,key->ptr); - retval = dictDelete(db->dict,key->ptr); - - return retval == DICT_OK; + /* Deleting an entry from the expires dict will not free the sds of + * the key, because it is shared with the main dictionary. */ + if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr); + return dictDelete(db->dict,key->ptr) == DICT_OK; } /*============================ RDB saving/loading =========================== */ @@ -3777,7 +3777,7 @@ static int rdbSaveObject(FILE *fp, robj *o) { } p = ziplistNext(o->ptr,p); } - } else if (o->encoding == REDIS_ENCODING_LIST) { + } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) { list *list = o->ptr; listIter li; listNode *ln; @@ -4187,7 +4187,7 @@ static robj *rdbLoadObject(int type, FILE *fp) { if (o->encoding == REDIS_ENCODING_ZIPLIST && ele->encoding == REDIS_ENCODING_RAW && sdslen(ele->ptr) > server.list_max_ziplist_value) - listTypeConvert(o,REDIS_ENCODING_LIST); + listTypeConvert(o,REDIS_ENCODING_LINKEDLIST); if (o->encoding == REDIS_ENCODING_ZIPLIST) { dec = getDecodedObject(ele); @@ -4246,23 +4246,31 @@ static robj *rdbLoadObject(int type, FILE *fp) { while(hashlen--) { robj *key, *val; - if ((key = rdbLoadStringObject(fp)) == NULL) return NULL; - if ((val = rdbLoadStringObject(fp)) == NULL) return NULL; + if ((key = rdbLoadEncodedStringObject(fp)) == NULL) return NULL; + if ((val = rdbLoadEncodedStringObject(fp)) == NULL) return NULL; /* If we are using a zipmap and there are too big values * the object is converted to real hash table encoding. */ if (o->encoding != REDIS_ENCODING_HT && - (sdslen(key->ptr) > server.hash_max_zipmap_value || - sdslen(val->ptr) > server.hash_max_zipmap_value)) + ((key->encoding == REDIS_ENCODING_RAW && + sdslen(key->ptr) > server.hash_max_zipmap_value) || + (val->encoding == REDIS_ENCODING_RAW && + sdslen(val->ptr) > server.hash_max_zipmap_value))) { convertToRealHash(o); } if (o->encoding == REDIS_ENCODING_ZIPMAP) { unsigned char *zm = o->ptr; + robj *deckey, *decval; - zm = zipmapSet(zm,key->ptr,sdslen(key->ptr), - val->ptr,sdslen(val->ptr),NULL); + /* We need raw string objects to add them to the zipmap */ + deckey = getDecodedObject(key); + decval = getDecodedObject(val); + zm = zipmapSet(zm,deckey->ptr,sdslen(deckey->ptr), + decval->ptr,sdslen(decval->ptr),NULL); o->ptr = zm; + decrRefCount(deckey); + decrRefCount(decval); decrRefCount(key); decrRefCount(val); } else { @@ -4919,7 +4927,7 @@ static void listTypeTryConversion(robj *subject, robj *value) { if (subject->encoding != REDIS_ENCODING_ZIPLIST) return; if (value->encoding == REDIS_ENCODING_RAW && sdslen(value->ptr) > server.list_max_ziplist_value) - listTypeConvert(subject,REDIS_ENCODING_LIST); + listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST); } static void listTypePush(robj *subject, robj *value, int where) { @@ -4927,14 +4935,14 @@ static void listTypePush(robj *subject, robj *value, int where) { listTypeTryConversion(subject,value); if (subject->encoding == REDIS_ENCODING_ZIPLIST && ziplistLen(subject->ptr) >= server.list_max_ziplist_entries) - listTypeConvert(subject,REDIS_ENCODING_LIST); + listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST); if (subject->encoding == REDIS_ENCODING_ZIPLIST) { int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL; value = getDecodedObject(value); subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos); decrRefCount(value); - } else if (subject->encoding == REDIS_ENCODING_LIST) { + } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) { if (where == REDIS_HEAD) { listAddNodeHead(subject->ptr,value); } else { @@ -4964,7 +4972,7 @@ static robj *listTypePop(robj *subject, int where) { /* We only need to delete an element when it exists */ subject->ptr = ziplistDelete(subject->ptr,&p); } - } else if (subject->encoding == REDIS_ENCODING_LIST) { + } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) { list *list = subject->ptr; listNode *ln; if (where == REDIS_HEAD) { @@ -4986,7 +4994,7 @@ static robj *listTypePop(robj *subject, int where) { static unsigned long listTypeLength(robj *subject) { if (subject->encoding == REDIS_ENCODING_ZIPLIST) { return ziplistLen(subject->ptr); - } else if (subject->encoding == REDIS_ENCODING_LIST) { + } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) { return listLength((list*)subject->ptr); } else { redisPanic("Unknown list encoding"); @@ -5017,7 +5025,7 @@ static listTypeIterator *listTypeInitIterator(robj *subject, int index, unsigned li->direction = direction; if (li->encoding == REDIS_ENCODING_ZIPLIST) { li->zi = ziplistIndex(subject->ptr,index); - } else if (li->encoding == REDIS_ENCODING_LIST) { + } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) { li->ln = listIndex(subject->ptr,index); } else { redisPanic("Unknown list encoding"); @@ -5047,7 +5055,7 @@ static int listTypeNext(listTypeIterator *li, listTypeEntry *entry) { li->zi = ziplistPrev(li->subject->ptr,li->zi); return 1; } - } else if (li->encoding == REDIS_ENCODING_LIST) { + } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) { entry->ln = li->ln; if (entry->ln != NULL) { if (li->direction == REDIS_TAIL) @@ -5078,7 +5086,7 @@ static robj *listTypeGet(listTypeEntry *entry) { value = createStringObjectFromLongLong(vlong); } } - } else if (li->encoding == REDIS_ENCODING_LIST) { + } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) { redisAssert(entry->ln != NULL); value = listNodeValue(entry->ln); incrRefCount(value); @@ -5106,7 +5114,7 @@ static void listTypeInsert(listTypeEntry *entry, robj *value, int where) { subject->ptr = ziplistInsert(subject->ptr,entry->zi,value->ptr,sdslen(value->ptr)); } decrRefCount(value); - } else if (entry->li->encoding == REDIS_ENCODING_LIST) { + } else if (entry->li->encoding == REDIS_ENCODING_LINKEDLIST) { if (where == REDIS_TAIL) { listInsertNode(subject->ptr,entry->ln,value,AL_START_TAIL); } else { @@ -5124,7 +5132,7 @@ static int listTypeEqual(listTypeEntry *entry, robj *o) { if (li->encoding == REDIS_ENCODING_ZIPLIST) { redisAssert(o->encoding == REDIS_ENCODING_RAW); return ziplistCompare(entry->zi,o->ptr,sdslen(o->ptr)); - } else if (li->encoding == REDIS_ENCODING_LIST) { + } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) { return equalStringObjects(o,listNodeValue(entry->ln)); } else { redisPanic("Unknown list encoding"); @@ -5143,7 +5151,7 @@ static void listTypeDelete(listTypeEntry *entry) { li->zi = p; else li->zi = ziplistPrev(li->subject->ptr,p); - } else if (entry->li->encoding == REDIS_ENCODING_LIST) { + } else if (entry->li->encoding == REDIS_ENCODING_LINKEDLIST) { listNode *next; if (li->direction == REDIS_TAIL) next = entry->ln->next; @@ -5161,7 +5169,7 @@ static void listTypeConvert(robj *subject, int enc) { listTypeEntry entry; redisAssert(subject->type == REDIS_LIST); - if (enc == REDIS_ENCODING_LIST) { + if (enc == REDIS_ENCODING_LINKEDLIST) { list *l = listCreate(); listSetFreeMethod(l,decrRefCount); @@ -5170,7 +5178,7 @@ static void listTypeConvert(robj *subject, int enc) { while (listTypeNext(li,&entry)) listAddNodeTail(l,listTypeGet(&entry)); listTypeReleaseIterator(li); - subject->encoding = REDIS_ENCODING_LIST; + subject->encoding = REDIS_ENCODING_LINKEDLIST; zfree(subject->ptr); subject->ptr = l; } else { @@ -5218,10 +5226,6 @@ static void pushxGenericCommand(redisClient *c, robj *refval, robj *val, int whe if ((subject = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || checkType(c,subject,REDIS_LIST)) return; - if (handleClientsWaitingListPush(c,c->argv[1],val)) { - addReply(c,shared.cone); - return; - } if (refval != NULL) { /* Note: we expect refval to be string-encoded because it is *not* the @@ -5250,8 +5254,12 @@ static void pushxGenericCommand(redisClient *c, robj *refval, robj *val, int whe /* Check if the length exceeds the ziplist length threshold. */ if (subject->encoding == REDIS_ENCODING_ZIPLIST && ziplistLen(subject->ptr) > server.list_max_ziplist_entries) - listTypeConvert(subject,REDIS_ENCODING_LIST); + listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST); server.dirty++; + } else { + /* Notify client of a failed insert */ + addReply(c,shared.cnegone); + return; } } else { listTypePush(subject,val,where); @@ -5308,7 +5316,7 @@ static void lindexCommand(redisClient *c) { } else { addReply(c,shared.nullbulk); } - } else if (o->encoding == REDIS_ENCODING_LIST) { + } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) { listNode *ln = listIndex(o->ptr,index); if (ln != NULL) { value = listNodeValue(ln); @@ -5341,7 +5349,7 @@ static void lsetCommand(redisClient *c) { addReply(c,shared.ok); server.dirty++; } - } else if (o->encoding == REDIS_ENCODING_LIST) { + } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) { listNode *ln = listIndex(o->ptr,index); if (ln == NULL) { addReply(c,shared.outofrangeerr); @@ -5396,9 +5404,9 @@ static void lrangeCommand(redisClient *c) { if (start < 0) start = llen+start; if (end < 0) end = llen+end; if (start < 0) start = 0; - if (end < 0) end = 0; - /* indexes sanity checks */ + /* Invariant: start >= 0, so this test will be true when end < 0. + * The range is empty when start > end or start >= length. */ if (start > end || start >= llen) { /* Out of range start or start > end result in empty list */ addReply(c,shared.emptymultibulk); @@ -5436,9 +5444,9 @@ static void ltrimCommand(redisClient *c) { if (start < 0) start = llen+start; if (end < 0) end = llen+end; if (start < 0) start = 0; - if (end < 0) end = 0; - /* indexes sanity checks */ + /* Invariant: start >= 0, so this test will be true when end < 0. + * The range is empty when start > end or start >= length. */ if (start > end || start >= llen) { /* Out of range start or start > end result in empty list */ ltrim = llen; @@ -5453,7 +5461,7 @@ static void ltrimCommand(redisClient *c) { if (o->encoding == REDIS_ENCODING_ZIPLIST) { o->ptr = ziplistDeleteRange(o->ptr,0,ltrim); o->ptr = ziplistDeleteRange(o->ptr,-rtrim,rtrim); - } else if (o->encoding == REDIS_ENCODING_LIST) { + } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) { list = o->ptr; for (j = 0; j < ltrim; j++) { ln = listFirst(list); @@ -6401,9 +6409,9 @@ static void zremrangebyrankCommand(redisClient *c) { if (start < 0) start = llen+start; if (end < 0) end = llen+end; if (start < 0) start = 0; - if (end < 0) end = 0; - /* indexes sanity checks */ + /* Invariant: start >= 0, so this test will be true when end < 0. + * The range is empty when start > end or start >= length. */ if (start > end || start >= llen) { addReply(c,shared.czero); return; @@ -6654,11 +6662,10 @@ static void zrangeGenericCommand(redisClient *c, int reverse) { if (start < 0) start = llen+start; if (end < 0) end = llen+end; if (start < 0) start = 0; - if (end < 0) end = 0; - /* indexes sanity checks */ + /* Invariant: start >= 0, so this test will be true when end < 0. + * The range is empty when start > end or start >= length. */ if (start > end || start >= llen) { - /* Out of range start or start > end result in empty list */ addReply(c,shared.emptymultibulk); return; } @@ -7753,8 +7760,8 @@ static sds genRedisInfoString(void) { "vm_enabled:%d\r\n" "role:%s\r\n" ,REDIS_VERSION, - REDIS_GIT_SHA1, - strtol(REDIS_GIT_DIRTY,NULL,10) > 0, + redisGitSHA1(), + strtol(redisGitDirty(),NULL,10) > 0, (sizeof(long) == 8) ? "64" : "32", aeGetApiName(), (long) getpid(), @@ -7855,6 +7862,9 @@ static void monitorCommand(redisClient *c) { /* ================================= Expire ================================= */ static int removeExpire(redisDb *db, robj *key) { + /* An expire may only be removed if there is a corresponding entry in the + * main dict. Otherwise, the key will never be freed. */ + redisAssert(dictFind(db->dict,key->ptr) != NULL); if (dictDelete(db->expires,key->ptr) == DICT_OK) { return 1; } else { @@ -7863,9 +7873,11 @@ static int removeExpire(redisDb *db, robj *key) { } static int setExpire(redisDb *db, robj *key, time_t when) { - sds copy = sdsdup(key->ptr); - if (dictAdd(db->expires,copy,(void*)when) == DICT_ERR) { - sdsfree(copy); + dictEntry *de; + + /* Reuse the sds from the main dict in the expire dict */ + redisAssert((de = dictFind(db->dict,key->ptr)) != NULL); + if (dictAdd(db->expires,dictGetEntryKey(de),(void*)when) == DICT_ERR) { return 0; } else { return 1; @@ -7881,39 +7893,32 @@ static time_t getExpire(redisDb *db, robj *key) { if (dictSize(db->expires) == 0 || (de = dictFind(db->expires,key->ptr)) == NULL) return -1; + /* The entry was found in the expire dict, this means it should also + * be present in the main dict (safety check). */ + redisAssert(dictFind(db->dict,key->ptr) != NULL); return (time_t) dictGetEntryVal(de); } static int expireIfNeeded(redisDb *db, robj *key) { - time_t when; - dictEntry *de; + time_t when = getExpire(db,key); + if (when < 0) return 0; - /* No expire? return ASAP */ - if (dictSize(db->expires) == 0 || - (de = dictFind(db->expires,key->ptr)) == NULL) return 0; - - /* Lookup the expire */ - when = (time_t) dictGetEntryVal(de); + /* Return when this key has not expired */ if (time(NULL) <= when) return 0; /* Delete the key */ - dbDelete(db,key); server.stat_expiredkeys++; - return 1; + server.dirty++; + return dbDelete(db,key); } static int deleteIfVolatile(redisDb *db, robj *key) { - dictEntry *de; - - /* No expire? return ASAP */ - if (dictSize(db->expires) == 0 || - (de = dictFind(db->expires,key->ptr)) == NULL) return 0; + if (getExpire(db,key) < 0) return 0; /* Delete the key */ - server.dirty++; server.stat_expiredkeys++; - dictDelete(db->expires,key->ptr); - return dictDelete(db->dict,key->ptr) == DICT_OK; + server.dirty++; + return dbDelete(db,key); } static void expireGenericCommand(redisClient *c, robj *key, robj *param, long offset) { @@ -8023,6 +8028,7 @@ static void discardCommand(redisClient *c) { freeClientMultiState(c); initClientMultiState(c); c->flags &= (~REDIS_MULTI); + unwatchAllKeys(c); addReply(c,shared.ok); } @@ -9144,7 +9150,7 @@ static int rewriteAppendOnlyFile(char *filename) { } p = ziplistNext(zl,p); } - } else if (o->encoding == REDIS_ENCODING_LIST) { + } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) { list *list = o->ptr; listNode *ln; listIter li; @@ -11436,7 +11442,7 @@ static void daemonize(void) { static void version() { printf("Redis server version %s (%s:%d)\n", REDIS_VERSION, - REDIS_GIT_SHA1, atoi(REDIS_GIT_DIRTY) > 0); + redisGitSHA1(), atoi(redisGitDirty()) > 0); exit(0); }