/*

* Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>

* All rights reserved.

*

* Redistribution and use in source and binary forms, with or without

* modification, are permitted provided that the following conditions are met:

*

* * Redistributions of source code must retain the above copyright notice,

* this list of conditions and the following disclaimer.

* * Redistributions in binary form must reproduce the above copyright

* notice, this list of conditions and the following disclaimer in the

* documentation and/or other materials provided with the distribution.

* * Neither the name of Redis nor the names of its contributors may be used

* to endorse or promote products derived from this software without

* specific prior written permission.

*

* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE

* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

* POSSIBILITY OF SUCH DAMAGE.

*/

#include "redis.h"

#include "cluster.h"

#include "slowlog.h"

#include "bio.h"

#include <time.h>

#include <signal.h>

#include <sys/wait.h>

#include <errno.h>

#include <assert.h>

#include <ctype.h>

#include <stdarg.h>

#include <arpa/inet.h>

#include <sys/stat.h>

#include <fcntl.h>

#include <sys/time.h>

#include <sys/resource.h>

#include <sys/uio.h>

#include <limits.h>

#include <float.h>

#include <math.h>

#include <sys/resource.h>

#include <sys/utsname.h>

#include <locale.h>

/* Our shared "common" objects */

struct sharedObjectsStruct shared;

/* Global vars that are actually used as constants. The following double

* values are used for double on-disk serialization, and are initialized

* at runtime to avoid strange compiler optimizations. */

double R_Zero, R_PosInf, R_NegInf, R_Nan;

/*================================= Globals ================================= */

/* Global vars */

struct redisServer server; /* server global state */

struct redisCommand *commandTable;

/* Our command table.

*

* Every entry is composed of the following fields:

*

* name: a string representing the command name.

* function: pointer to the C function implementing the command.

* arity: number of arguments, it is possible to use -N to say >= N

* sflags: command flags as string. See below for a table of flags.

* flags: flags as bitmask. Computed by Redis using the 'sflags' field.

* get_keys_proc: an optional function to get key arguments from a command.

* This is only used when the following three fields are not

* enough to specify what arguments are keys.

* first_key_index: first argument that is a key

* last_key_index: last argument that is a key

* key_step: step to get all the keys from first to last argument. For instance

* in MSET the step is two since arguments are key,val,key,val,...

* microseconds: microseconds of total execution time for this command.

* calls: total number of calls of this command.

*

* The flags, microseconds and calls fields are computed by Redis and should

* always be set to zero.

*

* Command flags are expressed using strings where every character represents

* a flag. Later the populateCommandTable() function will take care of

* populating the real 'flags' field using this characters.

*

* This is the meaning of the flags:

*

* w: write command (may modify the key space).

* r: read command (will never modify the key space).

* m: may increase memory usage once called. Don't allow if out of memory.

* a: admin command, like SAVE or SHUTDOWN.

* p: Pub/Sub related command.

* f: force replication of this command, regardless of server.dirty.

* s: command not allowed in scripts.

* R: random command. Command is not deterministic, that is, the same command

* with the same arguments, with the same key space, may have different

* results. For instance SPOP and RANDOMKEY are two random commands.

* S: Sort command output array if called from script, so that the output

* is deterministic.

* l: Allow command while loading the database.

* t: Allow command while a slave has stale data but is not allowed to

* server this data. Normally no command is accepted in this condition

* but just a few.

* M: Do not automatically propagate the command on MONITOR.

* k: Perform an implicit ASKING for this command, so the command will be

* accepted in cluster mode if the slot is marked as 'importing'.

*/

struct redisCommand redisCommandTable[] = {

{"get",getCommand,2,"r",0,NULL,1,1,1,0,0},

{"set",setCommand,-3,"wm",0,NULL,1,1,1,0,0},

{"setnx",setnxCommand,3,"wm",0,NULL,1,1,1,0,0},

{"setex",setexCommand,4,"wm",0,NULL,1,1,1,0,0},

{"psetex",psetexCommand,4,"wm",0,NULL,1,1,1,0,0},

{"append",appendCommand,3,"wm",0,NULL,1,1,1,0,0},

{"strlen",strlenCommand,2,"r",0,NULL,1,1,1,0,0},

{"del",delCommand,-2,"w",0,NULL,1,-1,1,0,0},

{"exists",existsCommand,2,"r",0,NULL,1,1,1,0,0},

{"setbit",setbitCommand,4,"wm",0,NULL,1,1,1,0,0},

{"getbit",getbitCommand,3,"r",0,NULL,1,1,1,0,0},

{"setrange",setrangeCommand,4,"wm",0,NULL,1,1,1,0,0},

{"getrange",getrangeCommand,4,"r",0,NULL,1,1,1,0,0},

{"substr",getrangeCommand,4,"r",0,NULL,1,1,1,0,0},

{"incr",incrCommand,2,"wm",0,NULL,1,1,1,0,0},

{"decr",decrCommand,2,"wm",0,NULL,1,1,1,0,0},

{"mget",mgetCommand,-2,"r",0,NULL,1,-1,1,0,0},

{"rpush",rpushCommand,-3,"wm",0,NULL,1,1,1,0,0},

{"lpush",lpushCommand,-3,"wm",0,NULL,1,1,1,0,0},

{"rpushx",rpushxCommand,3,"wm",0,NULL,1,1,1,0,0},

{"lpushx",lpushxCommand,3,"wm",0,NULL,1,1,1,0,0},

{"linsert",linsertCommand,5,"wm",0,NULL,1,1,1,0,0},

{"rpop",rpopCommand,2,"w",0,NULL,1,1,1,0,0},

{"lpop",lpopCommand,2,"w",0,NULL,1,1,1,0,0},

{"brpop",brpopCommand,-3,"ws",0,NULL,1,1,1,0,0},

{"brpoplpush",brpoplpushCommand,4,"wms",0,NULL,1,2,1,0,0},

{"blpop",blpopCommand,-3,"ws",0,NULL,1,-2,1,0,0},

{"llen",llenCommand,2,"r",0,NULL,1,1,1,0,0},

{"lindex",lindexCommand,3,"r",0,NULL,1,1,1,0,0},

{"lset",lsetCommand,4,"wm",0,NULL,1,1,1,0,0},

{"lrange",lrangeCommand,4,"r",0,NULL,1,1,1,0,0},

{"ltrim",ltrimCommand,4,"w",0,NULL,1,1,1,0,0},

{"lrem",lremCommand,4,"w",0,NULL,1,1,1,0,0},

{"rpoplpush",rpoplpushCommand,3,"wm",0,NULL,1,2,1,0,0},

{"sadd",saddCommand,-3,"wm",0,NULL,1,1,1,0,0},

{"srem",sremCommand,-3,"w",0,NULL,1,1,1,0,0},

{"smove",smoveCommand,4,"w",0,NULL,1,2,1,0,0},

{"sismember",sismemberCommand,3,"r",0,NULL,1,1,1,0,0},

{"scard",scardCommand,2,"r",0,NULL,1,1,1,0,0},

{"spop",spopCommand,2,"wRs",0,NULL,1,1,1,0,0},

{"srandmember",srandmemberCommand,-2,"rR",0,NULL,1,1,1,0,0},

{"sinter",sinterCommand,-2,"rS",0,NULL,1,-1,1,0,0},

{"sinterstore",sinterstoreCommand,-3,"wm",0,NULL,1,-1,1,0,0},

{"sunion",sunionCommand,-2,"rS",0,NULL,1,-1,1,0,0},

{"sunionstore",sunionstoreCommand,-3,"wm",0,NULL,1,-1,1,0,0},

{"sdiff",sdiffCommand,-2,"rS",0,NULL,1,-1,1,0,0},

{"sdiffstore",sdiffstoreCommand,-3,"wm",0,NULL,1,-1,1,0,0},

{"smembers",sinterCommand,2,"rS",0,NULL,1,1,1,0,0},

{"sscan",sscanCommand,-3,"rR",0,NULL,1,1,1,0,0},

{"zadd",zaddCommand,-4,"wm",0,NULL,1,1,1,0,0},

{"zincrby",zincrbyCommand,4,"wm",0,NULL,1,1,1,0,0},

{"zrem",zremCommand,-3,"w",0,NULL,1,1,1,0,0},

{"zremrangebyscore",zremrangebyscoreCommand,4,"w",0,NULL,1,1,1,0,0},

{"zremrangebyrank",zremrangebyrankCommand,4,"w",0,NULL,1,1,1,0,0},

{"zremrangebylex",zremrangebylexCommand,4,"w",0,NULL,1,1,1,0,0},

{"zunionstore",zunionstoreCommand,-4,"wm",0,zunionInterGetKeys,0,0,0,0,0},

{"zinterstore",zinterstoreCommand,-4,"wm",0,zunionInterGetKeys,0,0,0,0,0},

{"zrange",zrangeCommand,-4,"r",0,NULL,1,1,1,0,0},

{"zrangebyscore",zrangebyscoreCommand,-4,"r",0,NULL,1,1,1,0,0},

{"zrevrangebyscore",zrevrangebyscoreCommand,-4,"r",0,NULL,1,1,1,0,0},

{"zrangebylex",zrangebylexCommand,-4,"r",0,NULL,1,1,1,0,0},

{"zrevrangebylex",zrevrangebylexCommand,-4,"r",0,NULL,1,1,1,0,0},

{"zcount",zcountCommand,4,"r",0,NULL,1,1,1,0,0},

{"zlexcount",zlexcountCommand,4,"r",0,NULL,1,1,1,0,0},

{"zrevrange",zrevrangeCommand,-4,"r",0,NULL,1,1,1,0,0},

{"zcard",zcardCommand,2,"r",0,NULL,1,1,1,0,0},

{"zscore",zscoreCommand,3,"r",0,NULL,1,1,1,0,0},

{"zrank",zrankCommand,3,"r",0,NULL,1,1,1,0,0},

{"zrevrank",zrevrankCommand,3,"r",0,NULL,1,1,1,0,0},

{"zscan",zscanCommand,-3,"rR",0,NULL,1,1,1,0,0},

{"hset",hsetCommand,4,"wm",0,NULL,1,1,1,0,0},

{"hsetnx",hsetnxCommand,4,"wm",0,NULL,1,1,1,0,0},

{"hget",hgetCommand,3,"r",0,NULL,1,1,1,0,0},

{"hmset",hmsetCommand,-4,"wm",0,NULL,1,1,1,0,0},

{"hmget",hmgetCommand,-3,"r",0,NULL,1,1,1,0,0},

{"hincrby",hincrbyCommand,4,"wm",0,NULL,1,1,1,0,0},

{"hincrbyfloat",hincrbyfloatCommand,4,"wm",0,NULL,1,1,1,0,0},

{"hdel",hdelCommand,-3,"w",0,NULL,1,1,1,0,0},

{"hlen",hlenCommand,2,"r",0,NULL,1,1,1,0,0},

{"hkeys",hkeysCommand,2,"rS",0,NULL,1,1,1,0,0},

{"hvals",hvalsCommand,2,"rS",0,NULL,1,1,1,0,0},

{"hgetall",hgetallCommand,2,"r",0,NULL,1,1,1,0,0},

{"hexists",hexistsCommand,3,"r",0,NULL,1,1,1,0,0},

{"hscan",hscanCommand,-3,"rR",0,NULL,1,1,1,0,0},

{"incrby",incrbyCommand,3,"wm",0,NULL,1,1,1,0,0},

{"decrby",decrbyCommand,3,"wm",0,NULL,1,1,1,0,0},

{"incrbyfloat",incrbyfloatCommand,3,"wm",0,NULL,1,1,1,0,0},

{"getset",getsetCommand,3,"wm",0,NULL,1,1,1,0,0},

{"mset",msetCommand,-3,"wm",0,NULL,1,-1,2,0,0},

{"msetnx",msetnxCommand,-3,"wm",0,NULL,1,-1,2,0,0},

{"randomkey",randomkeyCommand,1,"rR",0,NULL,0,0,0,0,0},

{"select",selectCommand,2,"rl",0,NULL,0,0,0,0,0},

{"move",moveCommand,3,"w",0,NULL,1,1,1,0,0},

{"rename",renameCommand,3,"w",0,NULL,1,2,1,0,0},

{"renamenx",renamenxCommand,3,"w",0,NULL,1,2,1,0,0},

{"expire",expireCommand,3,"w",0,NULL,1,1,1,0,0},

{"expireat",expireatCommand,3,"w",0,NULL,1,1,1,0,0},

{"pexpire",pexpireCommand,3,"w",0,NULL,1,1,1,0,0},

{"pexpireat",pexpireatCommand,3,"w",0,NULL,1,1,1,0,0},

{"keys",keysCommand,2,"rS",0,NULL,0,0,0,0,0},

{"scan",scanCommand,-2,"rR",0,NULL,0,0,0,0,0},

{"dbsize",dbsizeCommand,1,"r",0,NULL,0,0,0,0,0},

{"auth",authCommand,2,"rslt",0,NULL,0,0,0,0,0},

{"ping",pingCommand,1,"rt",0,NULL,0,0,0,0,0},

{"echo",echoCommand,2,"r",0,NULL,0,0,0,0,0},

{"save",saveCommand,1,"ars",0,NULL,0,0,0,0,0},

{"bgsave",bgsaveCommand,1,"ar",0,NULL,0,0,0,0,0},

{"bgrewriteaof",bgrewriteaofCommand,1,"ar",0,NULL,0,0,0,0,0},

{"shutdown",shutdownCommand,-1,"arlt",0,NULL,0,0,0,0,0},

{"lastsave",lastsaveCommand,1,"rR",0,NULL,0,0,0,0,0},

{"type",typeCommand,2,"r",0,NULL,1,1,1,0,0},

{"multi",multiCommand,1,"rs",0,NULL,0,0,0,0,0},

{"exec",execCommand,1,"sM",0,NULL,0,0,0,0,0},

{"discard",discardCommand,1,"rs",0,NULL,0,0,0,0,0},

{"sync",syncCommand,1,"ars",0,NULL,0,0,0,0,0},

{"psync",syncCommand,3,"ars",0,NULL,0,0,0,0,0},

{"replconf",replconfCommand,-1,"arslt",0,NULL,0,0,0,0,0},

{"flushdb",flushdbCommand,1,"w",0,NULL,0,0,0,0,0},

{"flushall",flushallCommand,1,"w",0,NULL,0,0,0,0,0},

{"sort",sortCommand,-2,"wm",0,sortGetKeys,1,1,1,0,0},

{"info",infoCommand,-1,"rlt",0,NULL,0,0,0,0,0},

{"monitor",monitorCommand,1,"ars",0,NULL,0,0,0,0,0},

{"ttl",ttlCommand,2,"r",0,NULL,1,1,1,0,0},

{"pttl",pttlCommand,2,"r",0,NULL,1,1,1,0,0},

{"persist",persistCommand,2,"w",0,NULL,1,1,1,0,0},

{"slaveof",slaveofCommand,3,"ast",0,NULL,0,0,0,0,0},

{"debug",debugCommand,-2,"as",0,NULL,0,0,0,0,0},

{"config",configCommand,-2,"art",0,NULL,0,0,0,0,0},

{"subscribe",subscribeCommand,-2,"rpslt",0,NULL,0,0,0,0,0},

{"unsubscribe",unsubscribeCommand,-1,"rpslt",0,NULL,0,0,0,0,0},

{"psubscribe",psubscribeCommand,-2,"rpslt",0,NULL,0,0,0,0,0},

{"punsubscribe",punsubscribeCommand,-1,"rpslt",0,NULL,0,0,0,0,0},

{"publish",publishCommand,3,"pltr",0,NULL,0,0,0,0,0},

{"pubsub",pubsubCommand,-2,"pltrR",0,NULL,0,0,0,0,0},

{"watch",watchCommand,-2,"rs",0,NULL,1,-1,1,0,0},

{"unwatch",unwatchCommand,1,"rs",0,NULL,0,0,0,0,0},

{"cluster",clusterCommand,-2,"ar",0,NULL,0,0,0,0,0},

{"restore",restoreCommand,-4,"awm",0,NULL,1,1,1,0,0},

{"restore-asking",restoreCommand,-4,"awmk",0,NULL,1,1,1,0,0},

{"migrate",migrateCommand,-6,"aw",0,NULL,0,0,0,0,0},

{"asking",askingCommand,1,"r",0,NULL,0,0,0,0,0},

{"readonly",readonlyCommand,1,"r",0,NULL,0,0,0,0,0},

{"readwrite",readwriteCommand,1,"r",0,NULL,0,0,0,0,0},

{"dump",dumpCommand,2,"ar",0,NULL,1,1,1,0,0},

{"object",objectCommand,-2,"r",0,NULL,2,2,2,0,0},

{"client",clientCommand,-2,"ar",0,NULL,0,0,0,0,0},

{"eval",evalCommand,-3,"s",0,evalGetKeys,0,0,0,0,0},

{"evalsha",evalShaCommand,-3,"s",0,evalGetKeys,0,0,0,0,0},

{"slowlog",slowlogCommand,-2,"r",0,NULL,0,0,0,0,0},

{"script",scriptCommand,-2,"ras",0,NULL,0,0,0,0,0},

{"time",timeCommand,1,"rR",0,NULL,0,0,0,0,0},

{"bitop",bitopCommand,-4,"wm",0,NULL,2,-1,1,0,0},

{"bitcount",bitcountCommand,-2,"r",0,NULL,1,1,1,0,0},

{"bitpos",bitposCommand,-3,"r",0,NULL,1,1,1,0,0},

{"wait",waitCommand,3,"rs",0,NULL,0,0,0,0,0},

{"pfselftest",pfselftestCommand,1,"r",0,NULL,0,0,0,0,0},

{"pfadd",pfaddCommand,-2,"wm",0,NULL,1,1,1,0,0},

{"pfcount",pfcountCommand,-2,"w",0,NULL,1,1,1,0,0},

{"pfmerge",pfmergeCommand,-2,"wm",0,NULL,1,-1,1,0,0},

{"pfdebug",pfdebugCommand,-3,"w",0,NULL,0,0,0,0,0}

};

struct evictionPoolEntry *evictionPoolAlloc(void);

/*============================ Utility functions ============================ */

/* Low level logging. To use only for very big messages, otherwise

* redisLog() is to prefer. */

void redisLogRaw(int level, const char *msg) {

const int syslogLevelMap[] = { LOG_DEBUG, LOG_INFO, LOG_NOTICE, LOG_WARNING };

const char *c = ".-*#";

FILE *fp;

char buf[64];

int rawmode = (level & REDIS_LOG_RAW);

int log_to_stdout = server.logfile[0] == '\0';

level &= 0xff; /* clear flags */

if (level < server.verbosity) return;

fp = log_to_stdout ? stdout : fopen(server.logfile,"a");

if (!fp) return;

if (rawmode) {

fprintf(fp,"%s",msg);

} else {

int off;

struct timeval tv;

gettimeofday(&tv,NULL);

off = strftime(buf,sizeof(buf),"%d %b %H:%M:%S.",localtime(&tv.tv_sec));

snprintf(buf+off,sizeof(buf)-off,"%03d",(int)tv.tv_usec/1000);

fprintf(fp,"[%d] %s %c %s\n",(int)getpid(),buf,c[level],msg);

}

fflush(fp);

if (!log_to_stdout) fclose(fp);

if (server.syslog_enabled) syslog(syslogLevelMap[level], "%s", msg);

}

/* Like redisLogRaw() but with printf-alike support. This is the function that

* is used across the code. The raw version is only used in order to dump

* the INFO output on crash. */

void redisLog(int level, const char *fmt, ...) {

va_list ap;

char msg[REDIS_MAX_LOGMSG_LEN];

if ((level&0xff) < server.verbosity) return;

va_start(ap, fmt);

vsnprintf(msg, sizeof(msg), fmt, ap);

va_end(ap);

redisLogRaw(level,msg);

}

/* Log a fixed message without printf-alike capabilities, in a way that is

* safe to call from a signal handler.

*

* We actually use this only for signals that are not fatal from the point

* of view of Redis. Signals that are going to kill the server anyway and

* where we need printf-alike features are served by redisLog(). */

void redisLogFromHandler(int level, const char *msg) {

int fd;

int log_to_stdout = server.logfile[0] == '\0';

char buf[64];

if ((level&0xff) < server.verbosity || (log_to_stdout && server.daemonize))

return;

fd = log_to_stdout ? STDOUT_FILENO :

open(server.logfile, O_APPEND|O_CREAT|O_WRONLY, 0644);

if (fd == -1) return;

ll2string(buf,sizeof(buf),getpid());

if (write(fd,"[",1) == -1) goto err;

if (write(fd,buf,strlen(buf)) == -1) goto err;

if (write(fd," | signal handler] (",20) == -1) goto err;

ll2string(buf,sizeof(buf),time(NULL));

if (write(fd,buf,strlen(buf)) == -1) goto err;

if (write(fd,") ",2) == -1) goto err;

if (write(fd,msg,strlen(msg)) == -1) goto err;

if (write(fd,"\n",1) == -1) goto err;

err:

if (!log_to_stdout) close(fd);

}

/* Return the UNIX time in microseconds */

long long ustime(void) {

struct timeval tv;

long long ust;

gettimeofday(&tv, NULL);

ust = ((long long)tv.tv_sec)*1000000;

ust += tv.tv_usec;

return ust;

}

/* Return the UNIX time in milliseconds */

long long mstime(void) {

return ustime()/1000;

}

/* After an RDB dump or AOF rewrite we exit from children using _exit() instead of

* exit(), because the latter may interact with the same file objects used by

* the parent process. However if we are testing the coverage normal exit() is

* used in order to obtain the right coverage information. */

void exitFromChild(int retcode) {

#ifdef COVERAGE_TEST

exit(retcode);

#else

_exit(retcode);

#endif

}

/*====================== Hash table type implementation ==================== */

/* This is a hash table type that uses the SDS dynamic strings library as

* keys and radis objects as values (objects can hold SDS strings,

* lists, sets). */

void dictVanillaFree(void *privdata, void *val)

{

DICT_NOTUSED(privdata);

zfree(val);

}

void dictListDestructor(void *privdata, void *val)

{

DICT_NOTUSED(privdata);

listRelease((list*)val);

}

int dictSdsKeyCompare(void *privdata, const void *key1,

const void *key2)

{

int l1,l2;

DICT_NOTUSED(privdata);

l1 = sdslen((sds)key1);

l2 = sdslen((sds)key2);

if (l1 != l2) return 0;

return memcmp(key1, key2, l1) == 0;

}

/* A case insensitive version used for the command lookup table and other

* places where case insensitive non binary-safe comparison is needed. */

int dictSdsKeyCaseCompare(void *privdata, const void *key1,

const void *key2)

{

DICT_NOTUSED(privdata);

return strcasecmp(key1, key2) == 0;

}

void dictRedisObjectDestructor(void *privdata, void *val)

{

DICT_NOTUSED(privdata);

if (val == NULL) return; /* Values of swapped out keys as set to NULL */

decrRefCount(val);

}

void dictSdsDestructor(void *privdata, void *val)

{

DICT_NOTUSED(privdata);

sdsfree(val);

}

int dictObjKeyCompare(void *privdata, const void *key1,

const void *key2)

{

const robj *o1 = key1, *o2 = key2;

return dictSdsKeyCompare(privdata,o1->ptr,o2->ptr);

}

unsigned int dictObjHash(const void *key) {

const robj *o = key;

return dictGenHashFunction(o->ptr, sdslen((sds)o->ptr));

}

unsigned int dictSdsHash(const void *key) {

return dictGenHashFunction((unsigned char*)key, sdslen((char*)key));

}

unsigned int dictSdsCaseHash(const void *key) {

return dictGenCaseHashFunction((unsigned char*)key, sdslen((char*)key));

}

int dictEncObjKeyCompare(void *privdata, const void *key1,

const void *key2)

{

robj *o1 = (robj*) key1, *o2 = (robj*) key2;

int cmp;

if (o1->encoding == REDIS_ENCODING_INT &&

o2->encoding == REDIS_ENCODING_INT)

return o1->ptr == o2->ptr;

o1 = getDecodedObject(o1);

o2 = getDecodedObject(o2);

cmp = dictSdsKeyCompare(privdata,o1->ptr,o2->ptr);

decrRefCount(o1);

decrRefCount(o2);

return cmp;

}

unsigned int dictEncObjHash(const void *key) {

robj *o = (robj*) key;

if (sdsEncodedObject(o)) {

return dictGenHashFunction(o->ptr, sdslen((sds)o->ptr));

} else {

if (o->encoding == REDIS_ENCODING_INT) {

char buf[32];

int len;

len = ll2string(buf,32,(long)o->ptr);

return dictGenHashFunction((unsigned char*)buf, len);

} else {

unsigned int hash;

o = getDecodedObject(o);

hash = dictGenHashFunction(o->ptr, sdslen((sds)o->ptr));

decrRefCount(o);

return hash;

}

}

}

/* Sets type hash table */

dictType setDictType = {

dictEncObjHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictEncObjKeyCompare, /* key compare */

dictRedisObjectDestructor, /* key destructor */

NULL /* val destructor */

};

/* Sorted sets hash (note: a skiplist is used in addition to the hash table) */

dictType zsetDictType = {

dictEncObjHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictEncObjKeyCompare, /* key compare */

dictRedisObjectDestructor, /* key destructor */

NULL /* val destructor */

};

/* Db->dict, keys are sds strings, vals are Redis objects. */

dictType dbDictType = {

dictSdsHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCompare, /* key compare */

dictSdsDestructor, /* key destructor */

dictRedisObjectDestructor /* val destructor */

};

/* server.lua_scripts sha (as sds string) -> scripts (as robj) cache. */

dictType shaScriptObjectDictType = {

dictSdsCaseHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCaseCompare, /* key compare */

dictSdsDestructor, /* key destructor */

dictRedisObjectDestructor /* val destructor */

};

/* Db->expires */

dictType keyptrDictType = {

dictSdsHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCompare, /* key compare */

NULL, /* key destructor */

NULL /* val destructor */

};

/* Command table. sds string -> command struct pointer. */

dictType commandTableDictType = {

dictSdsCaseHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCaseCompare, /* key compare */

dictSdsDestructor, /* key destructor */

NULL /* val destructor */

};

/* Hash type hash table (note that small hashes are represented with ziplists) */

dictType hashDictType = {

dictEncObjHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictEncObjKeyCompare, /* key compare */

dictRedisObjectDestructor, /* key destructor */

dictRedisObjectDestructor /* val destructor */

};

/* Keylist hash table type has unencoded redis objects as keys and

* lists as values. It's used for blocking operations (BLPOP) and to

* map swapped keys to a list of clients waiting for this keys to be loaded. */

dictType keylistDictType = {

dictObjHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictObjKeyCompare, /* key compare */

dictRedisObjectDestructor, /* key destructor */

dictListDestructor /* val destructor */

};

/* Cluster nodes hash table, mapping nodes addresses 1.2.3.4:6379 to

* clusterNode structures. */

dictType clusterNodesDictType = {

dictSdsHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCompare, /* key compare */

dictSdsDestructor, /* key destructor */

NULL /* val destructor */

};

/* Cluster re-addition blacklist. This maps node IDs to the time

* we can re-add this node. The goal is to avoid readding a removed

* node for some time. */

dictType clusterNodesBlackListDictType = {

dictSdsCaseHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCaseCompare, /* key compare */

dictSdsDestructor, /* key destructor */

NULL /* val destructor */

};

/* Migrate cache dict type. */

dictType migrateCacheDictType = {

dictSdsHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCompare, /* key compare */

dictSdsDestructor, /* key destructor */

NULL /* val destructor */

};

/* Replication cached script dict (server.repl_scriptcache_dict).

* Keys are sds SHA1 strings, while values are not used at all in the current

* implementation. */

dictType replScriptCacheDictType = {

dictSdsCaseHash, /* hash function */

NULL, /* key dup */

NULL, /* val dup */

dictSdsKeyCaseCompare, /* key compare */

dictSdsDestructor, /* key destructor */

NULL /* val destructor */

};

int htNeedsResize(dict *dict) {

long long size, used;

size = dictSlots(dict);

used = dictSize(dict);

return (size && used && size > DICT_HT_INITIAL_SIZE &&

(used*100/size < REDIS_HT_MINFILL));

}

/* If the percentage of used slots in the HT reaches REDIS_HT_MINFILL

* we resize the hash table to save memory */

void tryResizeHashTables(int dbid) {

if (htNeedsResize(server.db[dbid].dict))

dictResize(server.db[dbid].dict);

if (htNeedsResize(server.db[dbid].expires))

dictResize(server.db[dbid].expires);

}

/* Our hash table implementation performs rehashing incrementally while

* we write/read from the hash table. Still if the server is idle, the hash

* table will use two tables for a long time. So we try to use 1 millisecond

* of CPU time at every call of this function to perform some rehahsing.

*

* The function returns 1 if some rehashing was performed, otherwise 0

* is returned. */

int incrementallyRehash(int dbid) {

/* Keys dictionary */

if (dictIsRehashing(server.db[dbid].dict)) {

dictRehashMilliseconds(server.db[dbid].dict,1);

return 1; /* already used our millisecond for this loop... */

}

/* Expires */

if (dictIsRehashing(server.db[dbid].expires)) {

dictRehashMilliseconds(server.db[dbid].expires,1);

return 1; /* already used our millisecond for this loop... */

}

return 0;

}

/* This function is called once a background process of some kind terminates,

* as we want to avoid resizing the hash tables when there is a child in order

* to play well with copy-on-write (otherwise when a resize happens lots of

* memory pages are copied). The goal of this function is to update the ability

* for dict.c to resize the hash tables accordingly to the fact we have o not

* running childs. */

void updateDictResizePolicy(void) {

if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)

dictEnableResize();

else

dictDisableResize();

}

/* ======================= Cron: called every 100 ms ======================== */

/* Helper function for the activeExpireCycle() function.

* This function will try to expire the key that is stored in the hash table

* entry 'de' of the 'expires' hash table of a Redis database.

*

* If the key is found to be expired, it is removed from the database and

* 1 is returned. Otherwise no operation is performed and 0 is returned.

*

* When a key is expired, server.stat_expiredkeys is incremented.

*

* The parameter 'now' is the current time in milliseconds as is passed

* to the function to avoid too many gettimeofday() syscalls. */

int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {

long long t = dictGetSignedIntegerVal(de);

if (now > t) {

sds key = dictGetKey(de);

robj *keyobj = createStringObject(key,sdslen(key));

propagateExpire(db,keyobj);

dbDelete(db,keyobj);

notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,

"expired",keyobj,db->id);

decrRefCount(keyobj);

server.stat_expiredkeys++;

return 1;

} else {

return 0;

}

}

/* Try to expire a few timed out keys. The algorithm used is adaptive and

* will use few CPU cycles if there are few expiring keys, otherwise

* it will get more aggressive to avoid that too much memory is used by

* keys that can be removed from the keyspace.

*

* No more than REDIS_DBCRON_DBS_PER_CALL databases are tested at every

* iteration.

*

* This kind of call is used when Redis detects that timelimit_exit is

* true, so there is more work to do, and we do it more incrementally from

* the beforeSleep() function of the event loop.

*

* Expire cycle type:

*

* If type is ACTIVE_EXPIRE_CYCLE_FAST the function will try to run a

* "fast" expire cycle that takes no longer than EXPIRE_FAST_CYCLE_DURATION

* microseconds, and is not repeated again before the same amount of time.

*

* If type is ACTIVE_EXPIRE_CYCLE_SLOW, that normal expire cycle is

* executed, where the time limit is a percentage of the REDIS_HZ period

* as specified by the REDIS_EXPIRELOOKUPS_TIME_PERC define. */

void activeExpireCycle(int type) {

/* This function has some global state in order to continue the work

* incrementally across calls. */

static unsigned int current_db = 0; /* Last DB tested. */

static int timelimit_exit = 0; /* Time limit hit in previous call? */

static long long last_fast_cycle = 0; /* When last fast cycle ran. */

unsigned int j, iteration = 0;

unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;

long long start = ustime(), timelimit;

if (type == ACTIVE_EXPIRE_CYCLE_FAST) {

/* Don't start a fast cycle if the previous cycle did not exited

* for time limt. Also don't repeat a fast cycle for the same period

* as the fast cycle total duration itself. */

if (!timelimit_exit) return;

if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;

last_fast_cycle = start;

}

/* We usually should test REDIS_DBCRON_DBS_PER_CALL per iteration, with

* two exceptions:

*

* 1) Don't test more DBs than we have.

* 2) If last time we hit the time limit, we want to scan all DBs

* in this iteration, as there is work to do in some DB and we don't want

* expired keys to use memory for too much time. */

if (dbs_per_call > server.dbnum || timelimit_exit)

dbs_per_call = server.dbnum;

/* We can use at max ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC percentage of CPU time

* per iteration. Since this function gets called with a frequency of

* server.hz times per second, the following is the max amount of

* microseconds we can spend in this function. */

timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;

timelimit_exit = 0;

if (timelimit <= 0) timelimit = 1;

if (type == ACTIVE_EXPIRE_CYCLE_FAST)

timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; /* in microseconds. */

for (j = 0; j < dbs_per_call; j++) {

int expired;

redisDb *db = server.db+(current_db % server.dbnum);

/* Increment the DB now so we are sure if we run out of time

* in the current DB we'll restart from the next. This allows to

* distribute the time evenly across DBs. */

current_db++;

/* Continue to expire if at the end of the cycle more than 25%

* of the keys were expired. */

do {

unsigned long num, slots;

long long now, ttl_sum;

int ttl_samples;

/* If there is nothing to expire try next DB ASAP. */

if ((num = dictSize(db->expires)) == 0) {

db->avg_ttl = 0;

break;

}

slots = dictSlots(db->expires);

now = mstime();

/* When there are less than 1% filled slots getting random

* keys is expensive, so stop here waiting for better times...

* The dictionary will be resized asap. */

if (num && slots > DICT_HT_INITIAL_SIZE &&

(num*100/slots < 1)) break;

/* The main collection cycle. Sample random keys among keys

* with an expire set, checking for expired ones. */

expired = 0;

ttl_sum = 0;

ttl_samples = 0;

if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)

num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;

while (num--) {

dictEntry *de;

long long ttl;

if ((de = dictGetRandomKey(db->expires)) == NULL) break;

ttl = dictGetSignedIntegerVal(de)-now;

if (activeExpireCycleTryExpire(db,de,now)) expired++;

if (ttl < 0) ttl = 0;

ttl_sum += ttl;

ttl_samples++;

}

/* Update the average TTL stats for this database. */

if (ttl_samples) {

long long avg_ttl = ttl_sum/ttl_samples;

if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;

/* Smooth the value averaging with the previous one. */

db->avg_ttl = (db->avg_ttl+avg_ttl)/2;

}

/* We can't block forever here even if there are many keys to

* expire. So after a given amount of milliseconds return to the

* caller waiting for the other active expire cycle. */

iteration++;

if ((iteration & 0xf) == 0 && /* check once every 16 iterations. */

(ustime()-start) > timelimit)

{

timelimit_exit = 1;

}

if (timelimit_exit) return;

/* We don't repeat the cycle if there are less than 25% of keys

* found expired in the current DB. */

} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);

}

}

unsigned int getLRUClock(void) {

return (mstime()/REDIS_LRU_CLOCK_RESOLUTION) & REDIS_LRU_CLOCK_MAX;

}

/* Add a sample to the operations per second array of samples. */

void trackOperationsPerSecond(void) {

long long t = mstime() - server.ops_sec_last_sample_time;

long long ops = server.stat_numcommands - server.ops_sec_last_sample_ops;

long long ops_sec;

ops_sec = t > 0 ? (ops*1000/t) : 0;

server.ops_sec_samples[server.ops_sec_idx] = ops_sec;

server.ops_sec_idx = (server.ops_sec_idx+1) % REDIS_OPS_SEC_SAMPLES;

server.ops_sec_last_sample_time = mstime();

server.ops_sec_last_sample_ops = server.stat_numcommands;

}

/* Return the mean of all the samples. */

long long getOperationsPerSecond(void) {

int j;

long long sum = 0;

for (j = 0; j < REDIS_OPS_SEC_SAMPLES; j++)

sum += server.ops_sec_samples[j];

return sum / REDIS_OPS_SEC_SAMPLES;

}

/* Check for timeouts. Returns non-zero if the client was terminated */

int clientsCronHandleTimeout(redisClient *c) {

time_t now = server.unixtime;

if (server.maxidletime &&

!(c->flags & REDIS_SLAVE) && /* no timeout for slaves */

!(c->flags & REDIS_MASTER) && /* no timeout for masters */

!(c->flags & REDIS_BLOCKED) && /* no timeout for BLPOP */

dictSize(c->pubsub_channels) == 0 && /* no timeout for pubsub */

listLength(c->pubsub_patterns) == 0 &&

(now - c->lastinteraction > server.maxidletime))

{

redisLog(REDIS_VERBOSE,"Closing idle client");

freeClient(c);

return 1;

} else if (c->flags & REDIS_BLOCKED) {

/* Blocked OPS timeout is handled with milliseconds resolution.

* However note that the actual resolution is limited by

* server.hz. */

mstime_t now_ms = mstime();

if (c->bpop.timeout != 0 && c->bpop.timeout < now_ms) {

replyToBlockedClientTimedOut(c);

unblockClient(c);

}

}

return 0;

}

/* The client query buffer is an sds.c string that can end with a lot of

* free space not used, this function reclaims space if needed.

*

* The function always returns 0 as it never terminates the client. */

int clientsCronResizeQueryBuffer(redisClient *c) {

size_t querybuf_size = sdsAllocSize(c->querybuf);

time_t idletime = server.unixtime - c->lastinteraction;

/* There are two conditions to resize the query buffer:

* 1) Query buffer is > BIG_ARG and too big for latest peak.

* 2) Client is inactive and the buffer is bigger than 1k. */

if (((querybuf_size > REDIS_MBULK_BIG_ARG) &&

(querybuf_size/(c->querybuf_peak+1)) > 2) ||

(querybuf_size > 1024 && idletime > 2))

{

/* Only resize the query buffer if it is actually wasting space. */

if (sdsavail(c->querybuf) > 1024) {

c->querybuf = sdsRemoveFreeSpace(c->querybuf);

}

}

/* Reset the peak again to capture the peak memory usage in the next

* cycle. */

c->querybuf_peak = 0;

return 0;

}

void clientsCron(void) {

/* Make sure to process at least 1/(server.hz*10) of clients per call.

* Since this function is called server.hz times per second we are sure that

* in the worst case we process all the clients in 10 seconds.

* In normal conditions (a reasonable number of clients) we process

* all the clients in a shorter time. */

int numclients = listLength(server.clients);

int iterations = numclients/(server.hz*10);

if (iterations < 50)

iterations = (numclients < 50) ? numclients : 50;

while(listLength(server.clients) && iterations--) {

redisClient *c;

listNode *head;

/* Rotate the list, take the current head, process.

* This way if the client must be removed from the list it's the

* first element and we don't incur into O(N) computation. */

listRotate(server.clients);

head = listFirst(server.clients);

c = listNodeValue(head);

/* The following functions do different service checks on the client.

* The protocol is that they return non-zero if the client was

* terminated. */

if (clientsCronHandleTimeout(c)) continue;

if (clientsCronResizeQueryBuffer(c)) continue;

}

}

/* This function handles 'background' operations we are required to do

* incrementally in Redis databases, such as active key expiring, resizing,

* rehashing. */

void databasesCron(void) {

/* Expire keys by random sampling. Not required for slaves

* as master will synthesize DELs for us. */

if (server.active_expire_enabled && server.masterhost == NULL)

activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);

/* Perform hash tables rehashing if needed, but only if there are no

* other processes saving the DB on disk. Otherwise rehashing is bad

* as will cause a lot of copy-on-write of memory pages. */

if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) {

/* We use global counters so if we stop the computation at a given

* DB we'll be able to start from the successive in the next

* cron loop iteration. */

static unsigned int resize_db = 0;

static unsigned int rehash_db = 0;

unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;

unsigned int j;

/* Don't test more DBs than we have. */

if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;

/* Resize */

for (j = 0; j < dbs_per_call; j++) {

tryResizeHashTables(resize_db % server.dbnum);

resize_db++;

}

/* Rehash */

if (server.activerehashing) {