src/redis.h

   1 #ifndef __REDIS_H
   2 #define __REDIS_H
   3
   4 #include "fmacros.h"
   5 #include "config.h"
   6
   7 #if defined(__sun)
   8 #include "solarisfixes.h"
   9 #endif
  10
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <time.h>
  15 #include <limits.h>
  16 #include <unistd.h>
  17 #include <errno.h>
  18 #include <inttypes.h>
  19 #include <pthread.h>
  20
  21 #include "ae.h"     /* Event driven programming library */
  22 #include "sds.h"    /* Dynamic safe strings */
  23 #include "dict.h"   /* Hash tables */
  24 #include "adlist.h" /* Linked lists */
  25 #include "zmalloc.h" /* total memory usage aware version of malloc/free */
  26 #include "anet.h"   /* Networking the easy way */
  27 #include "zipmap.h" /* Compact string -> string data structure */
  28 #include "ziplist.h" /* Compact list data structure */
  29 #include "intset.h" /* Compact integer set structure */
  30 #include "version.h"
  31
  32 /* Error codes */
  33 #define REDIS_OK                0
  34 #define REDIS_ERR               -1
  35
  36 /* Static server configuration */
  37 #define REDIS_SERVERPORT        6379    /* TCP port */
  38 #define REDIS_MAXIDLETIME       (60*5)  /* default client timeout */
  39 #define REDIS_IOBUF_LEN         1024
  40 #define REDIS_LOADBUF_LEN       1024
  41 #define REDIS_STATIC_ARGS       8
  42 #define REDIS_DEFAULT_DBNUM     16
  43 #define REDIS_CONFIGLINE_MAX    1024
  44 #define REDIS_OBJFREELIST_MAX   1000000 /* Max number of objects to cache */
  45 #define REDIS_MAX_SYNC_TIME     60      /* Slave can't take more to sync */
  46 #define REDIS_EXPIRELOOKUPS_PER_CRON    10 /* lookup 10 expires per loop */
  47 #define REDIS_MAX_WRITE_PER_EVENT (1024*64)
  48 #define REDIS_REQUEST_MAX_SIZE (1024*1024*256) /* max bytes in inline command */
  49 #define REDIS_SHARED_INTEGERS 10000
  50 #define REDIS_REPLY_CHUNK_BYTES (5*1500) /* 5 TCP packets with default MTU */
  51
  52 /* If more then REDIS_WRITEV_THRESHOLD write packets are pending use writev */
  53 #define REDIS_WRITEV_THRESHOLD      3
  54 /* Max number of iovecs used for each writev call */
  55 #define REDIS_WRITEV_IOVEC_COUNT    256
  56
  57 /* Hash table parameters */
  58 #define REDIS_HT_MINFILL        10      /* Minimal hash table fill 10% */
  59
  60 /* Command flags */
  61 #define REDIS_CMD_BULK          1       /* Bulk write command */
  62 #define REDIS_CMD_INLINE        2       /* Inline command */
  63 /* REDIS_CMD_DENYOOM reserves a longer comment: all the commands marked with
  64    this flags will return an error when the 'maxmemory' option is set in the
  65    config file and the server is using more than maxmemory bytes of memory.
  66    In short this commands are denied on low memory conditions. */
  67 #define REDIS_CMD_DENYOOM       4
  68 #define REDIS_CMD_FORCE_REPLICATION 8 /* Force replication even if dirty is 0 */
  69
  70 /* Object types */
  71 #define REDIS_STRING 0
  72 #define REDIS_LIST 1
  73 #define REDIS_SET 2
  74 #define REDIS_ZSET 3
  75 #define REDIS_HASH 4
  76 #define REDIS_VMPOINTER 8
  77
  78 /* Objects encoding. Some kind of objects like Strings and Hashes can be
  79  * internally represented in multiple ways. The 'encoding' field of the object
  80  * is set to one of this fields for this object. */
  81 #define REDIS_ENCODING_RAW 0     /* Raw representation */
  82 #define REDIS_ENCODING_INT 1     /* Encoded as integer */
  83 #define REDIS_ENCODING_HT 2      /* Encoded as hash table */
  84 #define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
  85 #define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
  86 #define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
  87 #define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
  88
  89 /* Object types only used for dumping to disk */
  90 #define REDIS_EXPIRETIME 253
  91 #define REDIS_SELECTDB 254
  92 #define REDIS_EOF 255
  93
  94 /* Defines related to the dump file format. To store 32 bits lengths for short
  95  * keys requires a lot of space, so we check the most significant 2 bits of
  96  * the first byte to interpreter the length:
  97  *
  98  * 00|000000 => if the two MSB are 00 the len is the 6 bits of this byte
  99  * 01|000000 00000000 =>  01, the len is 14 byes, 6 bits + 8 bits of next byte
 100  * 10|000000 [32 bit integer] => if it's 01, a full 32 bit len will follow
 101  * 11|000000 this means: specially encoded object will follow. The six bits
 102  *           number specify the kind of object that follows.
 103  *           See the REDIS_RDB_ENC_* defines.
 104  *
 105  * Lenghts up to 63 are stored using a single byte, most DB keys, and may
 106  * values, will fit inside. */
 107 #define REDIS_RDB_6BITLEN 0
 108 #define REDIS_RDB_14BITLEN 1
 109 #define REDIS_RDB_32BITLEN 2
 110 #define REDIS_RDB_ENCVAL 3
 111 #define REDIS_RDB_LENERR UINT_MAX
 112
 113 /* When a length of a string object stored on disk has the first two bits
 114  * set, the remaining two bits specify a special encoding for the object
 115  * accordingly to the following defines: */
 116 #define REDIS_RDB_ENC_INT8 0        /* 8 bit signed integer */
 117 #define REDIS_RDB_ENC_INT16 1       /* 16 bit signed integer */
 118 #define REDIS_RDB_ENC_INT32 2       /* 32 bit signed integer */
 119 #define REDIS_RDB_ENC_LZF 3         /* string compressed with FASTLZ */
 120
 121 /* Virtual memory object->where field. */
 122 #define REDIS_VM_MEMORY 0       /* The object is on memory */
 123 #define REDIS_VM_SWAPPED 1      /* The object is on disk */
 124 #define REDIS_VM_SWAPPING 2     /* Redis is swapping this object on disk */
 125 #define REDIS_VM_LOADING 3      /* Redis is loading this object from disk */
 126
 127 /* Virtual memory static configuration stuff.
 128  * Check vmFindContiguousPages() to know more about this magic numbers. */
 129 #define REDIS_VM_MAX_NEAR_PAGES 65536
 130 #define REDIS_VM_MAX_RANDOM_JUMP 4096
 131 #define REDIS_VM_MAX_THREADS 32
 132 #define REDIS_THREAD_STACK_SIZE (1024*1024*4)
 133 /* The following is the *percentage* of completed I/O jobs to process when the
 134  * handelr is called. While Virtual Memory I/O operations are performed by
 135  * threads, this operations must be processed by the main thread when completed
 136  * in order to take effect. */
 137 #define REDIS_MAX_COMPLETED_JOBS_PROCESSED 1
 138
 139 /* Client flags */
 140 #define REDIS_SLAVE 1       /* This client is a slave server */
 141 #define REDIS_MASTER 2      /* This client is a master server */
 142 #define REDIS_MONITOR 4     /* This client is a slave monitor, see MONITOR */
 143 #define REDIS_MULTI 8       /* This client is in a MULTI context */
 144 #define REDIS_BLOCKED 16    /* The client is waiting in a blocking operation */
 145 #define REDIS_IO_WAIT 32    /* The client is waiting for Virtual Memory I/O */
 146 #define REDIS_DIRTY_CAS 64  /* Watched keys modified. EXEC will fail. */
 147
 148 /* Slave replication state - slave side */
 149 #define REDIS_REPL_NONE 0   /* No active replication */
 150 #define REDIS_REPL_CONNECT 1    /* Must connect to master */
 151 #define REDIS_REPL_CONNECTED 2  /* Connected to master */
 152
 153 /* Slave replication state - from the point of view of master
 154  * Note that in SEND_BULK and ONLINE state the slave receives new updates
 155  * in its output queue. In the WAIT_BGSAVE state instead the server is waiting
 156  * to start the next background saving in order to send updates to it. */
 157 #define REDIS_REPL_WAIT_BGSAVE_START 3 /* master waits bgsave to start feeding it */
 158 #define REDIS_REPL_WAIT_BGSAVE_END 4 /* master waits bgsave to start bulk DB transmission */
 159 #define REDIS_REPL_SEND_BULK 5 /* master is sending the bulk DB */
 160 #define REDIS_REPL_ONLINE 6 /* bulk DB already transmitted, receive updates */
 161
 162 /* List related stuff */
 163 #define REDIS_HEAD 0
 164 #define REDIS_TAIL 1
 165
 166 /* Sort operations */
 167 #define REDIS_SORT_GET 0
 168 #define REDIS_SORT_ASC 1
 169 #define REDIS_SORT_DESC 2
 170 #define REDIS_SORTKEY_MAX 1024
 171
 172 /* Log levels */
 173 #define REDIS_DEBUG 0
 174 #define REDIS_VERBOSE 1
 175 #define REDIS_NOTICE 2
 176 #define REDIS_WARNING 3
 177
 178 /* Anti-warning macro... */
 179 #define REDIS_NOTUSED(V) ((void) V)
 180
 181 #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
 182 #define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
 183
 184 /* Append only defines */
 185 #define APPENDFSYNC_NO 0
 186 #define APPENDFSYNC_ALWAYS 1
 187 #define APPENDFSYNC_EVERYSEC 2
 188
 189 /* Zip structure related defaults */
 190 #define REDIS_HASH_MAX_ZIPMAP_ENTRIES 64
 191 #define REDIS_HASH_MAX_ZIPMAP_VALUE 512
 192 #define REDIS_LIST_MAX_ZIPLIST_ENTRIES 1024
 193 #define REDIS_LIST_MAX_ZIPLIST_VALUE 32
 194 #define REDIS_SET_MAX_INTSET_ENTRIES 4096
 195
 196 /* Sets operations codes */
 197 #define REDIS_OP_UNION 0
 198 #define REDIS_OP_DIFF 1
 199 #define REDIS_OP_INTER 2
 200
 201 /* Redis maxmemory strategies */
 202 #define REDIS_MAXMEMORY_VOLATILE_LRU 0
 203 #define REDIS_MAXMEMORY_VOLATILE_TTL 1
 204 #define REDIS_MAXMEMORY_VOLATILE_RANDOM 2
 205 #define REDIS_MAXMEMORY_ALLKEYS_LRU 3
 206 #define REDIS_MAXMEMORY_ALLKEYS_RANDOM 4
 207
 208 /* We can print the stacktrace, so our assert is defined this way: */
 209 #define redisAssert(_e) ((_e)?(void)0 : (_redisAssert(#_e,__FILE__,__LINE__),_exit(1)))
 210 #define redisPanic(_e) _redisPanic(#_e,__FILE__,__LINE__),_exit(1)
 211 void _redisAssert(char *estr, char *file, int line);
 212 void _redisPanic(char *msg, char *file, int line);
 213
 214 /*-----------------------------------------------------------------------------
 215  * Data types
 216  *----------------------------------------------------------------------------*/
 217
 218 /* A redis object, that is a type able to hold a string / list / set */
 219
 220 /* The actual Redis Object */
 221 #define REDIS_LRU_CLOCK_MAX ((1<<21)-1) /* Max value of obj->lru */
 222 #define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */
 223 typedef struct redisObject {
 224     unsigned type:4;
 225     unsigned storage:2;     /* REDIS_VM_MEMORY or REDIS_VM_SWAPPING */
 226     unsigned encoding:4;
 227     unsigned lru:22;        /* lru time (relative to server.lruclock) */
 228     int refcount;
 229     void *ptr;
 230     /* VM fields are only allocated if VM is active, otherwise the
 231      * object allocation function will just allocate
 232      * sizeof(redisObjct) minus sizeof(redisObjectVM), so using
 233      * Redis without VM active will not have any overhead. */
 234 } robj;
 235
 236 /* The VM pointer structure - identifies an object in the swap file.
 237  *
 238  * This object is stored in place of the value
 239  * object in the main key->value hash table representing a database.
 240  * Note that the first fields (type, storage) are the same as the redisObject
 241  * structure so that vmPointer strucuters can be accessed even when casted
 242  * as redisObject structures.
 243  *
 244  * This is useful as we don't know if a value object is or not on disk, but we
 245  * are always able to read obj->storage to check this. For vmPointer
 246  * structures "type" is set to REDIS_VMPOINTER (even if without this field
 247  * is still possible to check the kind of object from the value of 'storage').*/
 248 typedef struct vmPointer {
 249     unsigned type:4;
 250     unsigned storage:2; /* REDIS_VM_SWAPPED or REDIS_VM_LOADING */
 251     unsigned notused:26;
 252     unsigned int vtype; /* type of the object stored in the swap file */
 253     off_t page;         /* the page at witch the object is stored on disk */
 254     off_t usedpages;    /* number of pages used on disk */
 255 } vmpointer;
 256
 257 /* Macro used to initalize a Redis object allocated on the stack.
 258  * Note that this macro is taken near the structure definition to make sure
 259  * we'll update it when the structure is changed, to avoid bugs like
 260  * bug #85 introduced exactly in this way. */
 261 #define initStaticStringObject(_var,_ptr) do { \
 262     _var.refcount = 1; \
 263     _var.type = REDIS_STRING; \
 264     _var.encoding = REDIS_ENCODING_RAW; \
 265     _var.ptr = _ptr; \
 266     _var.storage = REDIS_VM_MEMORY; \
 267 } while(0);
 268
 269 typedef struct redisDb {
 270     dict *dict;                 /* The keyspace for this DB */
 271     dict *expires;              /* Timeout of keys with a timeout set */
 272     dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */
 273     dict *io_keys;              /* Keys with clients waiting for VM I/O */
 274     dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
 275     int id;
 276 } redisDb;
 277
 278 /* Client MULTI/EXEC state */
 279 typedef struct multiCmd {
 280     robj **argv;
 281     int argc;
 282     struct redisCommand *cmd;
 283 } multiCmd;
 284
 285 typedef struct multiState {
 286     multiCmd *commands;     /* Array of MULTI commands */
 287     int count;              /* Total number of MULTI commands */
 288 } multiState;
 289
 290 /* With multiplexing we need to take per-clinet state.
 291  * Clients are taken in a liked list. */
 292 typedef struct redisClient {
 293     int fd;
 294     redisDb *db;
 295     int dictid;
 296     sds querybuf;
 297     robj **argv, **mbargv;
 298     char *newline;          /* pointing to the detected newline in querybuf */
 299     int argc, mbargc;
 300     long bulklen;            /* bulk read len. -1 if not in bulk read mode */
 301     int multibulk;          /* multi bulk command format active */
 302     list *reply;
 303     int sentlen;
 304     time_t lastinteraction; /* time of the last interaction, used for timeout */
 305     int flags;              /* REDIS_SLAVE | REDIS_MONITOR | REDIS_MULTI ... */
 306     int slaveseldb;         /* slave selected db, if this client is a slave */
 307     int authenticated;      /* when requirepass is non-NULL */
 308     int replstate;          /* replication state if this is a slave */
 309     int repldbfd;           /* replication DB file descriptor */
 310     long repldboff;         /* replication DB file offset */
 311     off_t repldbsize;       /* replication DB file size */
 312     multiState mstate;      /* MULTI/EXEC state */
 313     robj **blocking_keys;   /* The key we are waiting to terminate a blocking
 314                              * operation such as BLPOP. Otherwise NULL. */
 315     int blocking_keys_num;  /* Number of blocking keys */
 316     time_t blockingto;      /* Blocking operation timeout. If UNIX current time
 317                              * is >= blockingto then the operation timed out. */
 318     list *io_keys;          /* Keys this client is waiting to be loaded from the
 319                              * swap file in order to continue. */
 320     list *watched_keys;     /* Keys WATCHED for MULTI/EXEC CAS */
 321     dict *pubsub_channels;  /* channels a client is interested in (SUBSCRIBE) */
 322     list *pubsub_patterns;  /* patterns a client is interested in (SUBSCRIBE) */
 323
 324     /* Response buffer */
 325     int bufpos;
 326     char buf[REDIS_REPLY_CHUNK_BYTES];
 327 } redisClient;
 328
 329 struct saveparam {
 330     time_t seconds;
 331     int changes;
 332 };
 333
 334 struct sharedObjectsStruct {
 335     robj *crlf, *ok, *err, *emptybulk, *czero, *cone, *cnegone, *pong, *space,
 336     *colon, *nullbulk, *nullmultibulk, *queued,
 337     *emptymultibulk, *wrongtypeerr, *nokeyerr, *syntaxerr, *sameobjecterr,
 338     *outofrangeerr, *plus,
 339     *select0, *select1, *select2, *select3, *select4,
 340     *select5, *select6, *select7, *select8, *select9,
 341     *messagebulk, *pmessagebulk, *subscribebulk, *unsubscribebulk, *mbulk3,
 342     *mbulk4, *psubscribebulk, *punsubscribebulk,
 343     *integers[REDIS_SHARED_INTEGERS];
 344 };
 345
 346 /* Global server state structure */
 347 struct redisServer {
 348     pthread_t mainthread;
 349     int port;
 350     int fd;
 351     redisDb *db;
 352     long long dirty;            /* changes to DB from the last save */
 353     long long dirty_before_bgsave; /* used to restore dirty on failed BGSAVE */
 354     list *clients;
 355     list *slaves, *monitors;
 356     char neterr[ANET_ERR_LEN];
 357     aeEventLoop *el;
 358     int cronloops;              /* number of times the cron function run */
 359     list *objfreelist;          /* A list of freed objects to avoid malloc() */
 360     time_t lastsave;                /* Unix time of last save succeeede */
 361     /* Fields used only for stats */
 362     time_t stat_starttime;          /* server start time */
 363     long long stat_numcommands;     /* number of processed commands */
 364     long long stat_numconnections;  /* number of connections received */
 365     long long stat_expiredkeys;     /* number of expired keys */
 366     long long stat_keyspace_hits;   /* number of successful lookups of keys */
 367     long long stat_keyspace_misses; /* number of failed lookups of keys */
 368     /* Configuration */
 369     int verbosity;
 370     int glueoutputbuf;
 371     int maxidletime;
 372     int dbnum;
 373     int daemonize;
 374     int appendonly;
 375     int appendfsync;
 376     int no_appendfsync_on_rewrite;
 377     int shutdown_asap;
 378     time_t lastfsync;
 379     int appendfd;
 380     int appendseldb;
 381     char *pidfile;
 382     pid_t bgsavechildpid;
 383     pid_t bgrewritechildpid;
 384     sds bgrewritebuf; /* buffer taken by parent during oppend only rewrite */
 385     sds aofbuf;       /* AOF buffer, written before entering the event loop */
 386     struct saveparam *saveparams;
 387     int saveparamslen;
 388     char *logfile;
 389     char *bindaddr;
 390     char *dbfilename;
 391     char *appendfilename;
 392     char *requirepass;
 393     int rdbcompression;
 394     int activerehashing;
 395     /* Replication related */
 396     int isslave;
 397     char *masterauth;
 398     char *masterhost;
 399     int masterport;
 400     redisClient *master;    /* client that is master for this slave */
 401     int replstate;
 402     unsigned int maxclients;
 403     unsigned long long maxmemory;
 404     int maxmemory_policy;
 405     int maxmemory_samples;
 406     unsigned int blpop_blocked_clients;
 407     unsigned int vm_blocked_clients;
 408     /* Sort parameters - qsort_r() is only available under BSD so we
 409      * have to take this state global, in order to pass it to sortCompare() */
 410     int sort_desc;
 411     int sort_alpha;
 412     int sort_bypattern;
 413     /* Virtual memory configuration */
 414     int vm_enabled;
 415     char *vm_swap_file;
 416     off_t vm_page_size;
 417     off_t vm_pages;
 418     unsigned long long vm_max_memory;
 419     /* Zip structure config */
 420     size_t hash_max_zipmap_entries;
 421     size_t hash_max_zipmap_value;
 422     size_t list_max_ziplist_entries;
 423     size_t list_max_ziplist_value;
 424     size_t set_max_intset_entries;
 425     /* Virtual memory state */
 426     FILE *vm_fp;
 427     int vm_fd;
 428     off_t vm_next_page; /* Next probably empty page */
 429     off_t vm_near_pages; /* Number of pages allocated sequentially */
 430     unsigned char *vm_bitmap; /* Bitmap of free/used pages */
 431     time_t unixtime;    /* Unix time sampled every second. */
 432     /* Virtual memory I/O threads stuff */
 433     /* An I/O thread process an element taken from the io_jobs queue and
 434      * put the result of the operation in the io_done list. While the
 435      * job is being processed, it's put on io_processing queue. */
 436     list *io_newjobs; /* List of VM I/O jobs yet to be processed */
 437     list *io_processing; /* List of VM I/O jobs being processed */
 438     list *io_processed; /* List of VM I/O jobs already processed */
 439     list *io_ready_clients; /* Clients ready to be unblocked. All keys loaded */
 440     pthread_mutex_t io_mutex; /* lock to access io_jobs/io_done/io_thread_job */
 441     pthread_mutex_t obj_freelist_mutex; /* safe redis objects creation/free */
 442     pthread_mutex_t io_swapfile_mutex; /* So we can lseek + write */
 443     pthread_attr_t io_threads_attr; /* attributes for threads creation */
 444     int io_active_threads; /* Number of running I/O threads */
 445     int vm_max_threads; /* Max number of I/O threads running at the same time */
 446     /* Our main thread is blocked on the event loop, locking for sockets ready
 447      * to be read or written, so when a threaded I/O operation is ready to be
 448      * processed by the main thread, the I/O thread will use a unix pipe to
 449      * awake the main thread. The followings are the two pipe FDs. */
 450     int io_ready_pipe_read;
 451     int io_ready_pipe_write;
 452     /* Virtual memory stats */
 453     unsigned long long vm_stats_used_pages;
 454     unsigned long long vm_stats_swapped_objects;
 455     unsigned long long vm_stats_swapouts;
 456     unsigned long long vm_stats_swapins;
 457     /* Pubsub */
 458     dict *pubsub_channels; /* Map channels to list of subscribed clients */
 459     list *pubsub_patterns; /* A list of pubsub_patterns */
 460     /* Misc */
 461     FILE *devnull;
 462     unsigned lruclock:22;        /* clock incrementing every minute, for LRU */
 463     unsigned lruclock_padding:10;
 464 };
 465
 466 typedef struct pubsubPattern {
 467     redisClient *client;
 468     robj *pattern;
 469 } pubsubPattern;
 470
 471 typedef void redisCommandProc(redisClient *c);
 472 typedef void redisVmPreloadProc(redisClient *c, struct redisCommand *cmd, int argc, robj **argv);
 473 struct redisCommand {
 474     char *name;
 475     redisCommandProc *proc;
 476     int arity;
 477     int flags;
 478     /* Use a function to determine which keys need to be loaded
 479      * in the background prior to executing this command. Takes precedence
 480      * over vm_firstkey and others, ignored when NULL */
 481     redisVmPreloadProc *vm_preload_proc;
 482     /* What keys should be loaded in background when calling this command? */
 483     int vm_firstkey; /* The first argument that's a key (0 = no keys) */
 484     int vm_lastkey;  /* THe last argument that's a key */
 485     int vm_keystep;  /* The step between first and last key */
 486 };
 487
 488 struct redisFunctionSym {
 489     char *name;
 490     unsigned long pointer;
 491 };
 492
 493 typedef struct _redisSortObject {
 494     robj *obj;
 495     union {
 496         double score;
 497         robj *cmpobj;
 498     } u;
 499 } redisSortObject;
 500
 501 typedef struct _redisSortOperation {
 502     int type;
 503     robj *pattern;
 504 } redisSortOperation;
 505
 506 /* ZSETs use a specialized version of Skiplists */
 507 typedef struct zskiplistNode {
 508     robj *obj;
 509     double score;
 510     struct zskiplistNode *backward;
 511     struct zskiplistLevel {
 512         struct zskiplistNode *forward;
 513         unsigned int span;
 514     } level[];
 515 } zskiplistNode;
 516
 517 typedef struct zskiplist {
 518     struct zskiplistNode *header, *tail;
 519     unsigned long length;
 520     int level;
 521 } zskiplist;
 522
 523 typedef struct zset {
 524     dict *dict;
 525     zskiplist *zsl;
 526 } zset;
 527
 528 /* VM threaded I/O request message */
 529 #define REDIS_IOJOB_LOAD 0          /* Load from disk to memory */
 530 #define REDIS_IOJOB_PREPARE_SWAP 1  /* Compute needed pages */
 531 #define REDIS_IOJOB_DO_SWAP 2       /* Swap from memory to disk */
 532 typedef struct iojob {
 533     int type;   /* Request type, REDIS_IOJOB_* */
 534     redisDb *db;/* Redis database */
 535     robj *key;  /* This I/O request is about swapping this key */
 536     robj *id;   /* Unique identifier of this job:
 537                    this is the object to swap for REDIS_IOREQ_*_SWAP, or the
 538                    vmpointer objct for REDIS_IOREQ_LOAD. */
 539     robj *val;  /* the value to swap for REDIS_IOREQ_*_SWAP, otherwise this
 540                  * field is populated by the I/O thread for REDIS_IOREQ_LOAD. */
 541     off_t page; /* Swap page where to read/write the object */
 542     off_t pages; /* Swap pages needed to save object. PREPARE_SWAP return val */
 543     int canceled; /* True if this command was canceled by blocking side of VM */
 544     pthread_t thread; /* ID of the thread processing this entry */
 545 } iojob;
 546
 547 /* Structure to hold list iteration abstraction. */
 548 typedef struct {
 549     robj *subject;
 550     unsigned char encoding;
 551     unsigned char direction; /* Iteration direction */
 552     unsigned char *zi;
 553     listNode *ln;
 554 } listTypeIterator;
 555
 556 /* Structure for an entry while iterating over a list. */
 557 typedef struct {
 558     listTypeIterator *li;
 559     unsigned char *zi;  /* Entry in ziplist */
 560     listNode *ln;       /* Entry in linked list */
 561 } listTypeEntry;
 562
 563 /* Structure to hold set iteration abstraction. */
 564 typedef struct {
 565     robj *subject;
 566     int encoding;
 567     int ii; /* intset iterator */
 568     dictIterator *di;
 569 } setTypeIterator;
 570
 571 /* Structure to hold hash iteration abstration. Note that iteration over
 572  * hashes involves both fields and values. Because it is possible that
 573  * not both are required, store pointers in the iterator to avoid
 574  * unnecessary memory allocation for fields/values. */
 575 typedef struct {
 576     int encoding;
 577     unsigned char *zi;
 578     unsigned char *zk, *zv;
 579     unsigned int zklen, zvlen;
 580
 581     dictIterator *di;
 582     dictEntry *de;
 583 } hashTypeIterator;
 584
 585 #define REDIS_HASH_KEY 1
 586 #define REDIS_HASH_VALUE 2
 587
 588 /*-----------------------------------------------------------------------------
 589  * Extern declarations
 590  *----------------------------------------------------------------------------*/
 591
 592 extern struct redisServer server;
 593 extern struct sharedObjectsStruct shared;
 594 extern dictType setDictType;
 595 extern dictType zsetDictType;
 596 extern double R_Zero, R_PosInf, R_NegInf, R_Nan;
 597 dictType hashDictType;
 598
 599 /*-----------------------------------------------------------------------------
 600  * Functions prototypes
 601  *----------------------------------------------------------------------------*/
 602
 603 /* networking.c -- Networking and Client related operations */
 604 redisClient *createClient(int fd);
 605 void closeTimedoutClients(void);
 606 void freeClient(redisClient *c);
 607 void resetClient(redisClient *c);
 608 void sendReplyToClient(aeEventLoop *el, int fd, void *privdata, int mask);
 609 void sendReplyToClientWritev(aeEventLoop *el, int fd, void *privdata, int mask);
 610 void addReply(redisClient *c, robj *obj);
 611 void *addDeferredMultiBulkLength(redisClient *c);
 612 void setDeferredMultiBulkLength(redisClient *c, void *node, long length);
 613 void addReplySds(redisClient *c, sds s);
 614 void processInputBuffer(redisClient *c);
 615 void acceptHandler(aeEventLoop *el, int fd, void *privdata, int mask);
 616 void readQueryFromClient(aeEventLoop *el, int fd, void *privdata, int mask);
 617 void addReplyBulk(redisClient *c, robj *obj);
 618 void addReplyBulkCString(redisClient *c, char *s);
 619 void acceptHandler(aeEventLoop *el, int fd, void *privdata, int mask);
 620 void addReply(redisClient *c, robj *obj);
 621 void addReplySds(redisClient *c, sds s);
 622 void addReplyError(redisClient *c, char *err);
 623 void addReplyStatus(redisClient *c, char *status);
 624 void addReplyDouble(redisClient *c, double d);
 625 void addReplyLongLong(redisClient *c, long long ll);
 626 void addReplyMultiBulkLen(redisClient *c, long length);
 627 void *dupClientReplyValue(void *o);
 628
 629 #ifdef __GNUC__
 630 void addReplyErrorFormat(redisClient *c, const char *fmt, ...)
 631     __attribute__((format(printf, 2, 3)));
 632 void addReplyStatusFormat(redisClient *c, const char *fmt, ...)
 633     __attribute__((format(printf, 2, 3)));
 634 #else
 635 void addReplyErrorFormat(redisClient *c, const char *fmt, ...);
 636 void addReplyStatusFormat(redisClient *c, const char *fmt, ...);
 637 #endif
 638
 639 /* List data type */
 640 void listTypeTryConversion(robj *subject, robj *value);
 641 void listTypePush(robj *subject, robj *value, int where);
 642 robj *listTypePop(robj *subject, int where);
 643 unsigned long listTypeLength(robj *subject);
 644 listTypeIterator *listTypeInitIterator(robj *subject, int index, unsigned char direction);
 645 void listTypeReleaseIterator(listTypeIterator *li);
 646 int listTypeNext(listTypeIterator *li, listTypeEntry *entry);
 647 robj *listTypeGet(listTypeEntry *entry);
 648 void listTypeInsert(listTypeEntry *entry, robj *value, int where);
 649 int listTypeEqual(listTypeEntry *entry, robj *o);
 650 void listTypeDelete(listTypeEntry *entry);
 651 void listTypeConvert(robj *subject, int enc);
 652 void unblockClientWaitingData(redisClient *c);
 653 int handleClientsWaitingListPush(redisClient *c, robj *key, robj *ele);
 654 void popGenericCommand(redisClient *c, int where);
 655
 656 /* MULTI/EXEC/WATCH... */
 657 void unwatchAllKeys(redisClient *c);
 658 void initClientMultiState(redisClient *c);
 659 void freeClientMultiState(redisClient *c);
 660 void queueMultiCommand(redisClient *c, struct redisCommand *cmd);
 661 void touchWatchedKey(redisDb *db, robj *key);
 662 void touchWatchedKeysOnFlush(int dbid);
 663
 664 /* Redis object implementation */
 665 void decrRefCount(void *o);
 666 void incrRefCount(robj *o);
 667 void freeStringObject(robj *o);
 668 void freeListObject(robj *o);
 669 void freeSetObject(robj *o);
 670 void freeZsetObject(robj *o);
 671 void freeHashObject(robj *o);
 672 robj *createObject(int type, void *ptr);
 673 robj *createStringObject(char *ptr, size_t len);
 674 robj *dupStringObject(robj *o);
 675 robj *tryObjectEncoding(robj *o);
 676 robj *getDecodedObject(robj *o);
 677 size_t stringObjectLen(robj *o);
 678 int tryFreeOneObjectFromFreelist(void);
 679 robj *createStringObjectFromLongLong(long long value);
 680 robj *createListObject(void);
 681 robj *createZiplistObject(void);
 682 robj *createSetObject(void);
 683 robj *createIntsetObject(void);
 684 robj *createHashObject(void);
 685 robj *createZsetObject(void);
 686 int getLongFromObjectOrReply(redisClient *c, robj *o, long *target, const char *msg);
 687 int checkType(redisClient *c, robj *o, int type);
 688 int getLongLongFromObjectOrReply(redisClient *c, robj *o, long long *target, const char *msg);
 689 int getDoubleFromObjectOrReply(redisClient *c, robj *o, double *target, const char *msg);
 690 int getLongLongFromObject(robj *o, long long *target);
 691 char *strEncoding(int encoding);
 692 int compareStringObjects(robj *a, robj *b);
 693 int equalStringObjects(robj *a, robj *b);
 694 unsigned long estimateObjectIdleTime(robj *o);
 695
 696 /* Replication */
 697 void replicationFeedSlaves(list *slaves, int dictid, robj **argv, int argc);
 698 void replicationFeedMonitors(list *monitors, int dictid, robj **argv, int argc);
 699 int syncWithMaster(void);
 700 void updateSlavesWaitingBgsave(int bgsaveerr);
 701
 702 /* RDB persistence */
 703 int rdbLoad(char *filename);
 704 int rdbSaveBackground(char *filename);
 705 void rdbRemoveTempFile(pid_t childpid);
 706 int rdbSave(char *filename);
 707 int rdbSaveObject(FILE *fp, robj *o);
 708 off_t rdbSavedObjectPages(robj *o, FILE *fp);
 709 off_t rdbSavedObjectLen(robj *o, FILE *fp);
 710 robj *rdbLoadObject(int type, FILE *fp);
 711 void backgroundSaveDoneHandler(int statloc);
 712
 713 /* AOF persistence */
 714 void flushAppendOnlyFile(void);
 715 void feedAppendOnlyFile(struct redisCommand *cmd, int dictid, robj **argv, int argc);
 716 void aofRemoveTempFile(pid_t childpid);
 717 int rewriteAppendOnlyFileBackground(void);
 718 int loadAppendOnlyFile(char *filename);
 719 void stopAppendOnly(void);
 720 int startAppendOnly(void);
 721 void backgroundRewriteDoneHandler(int statloc);
 722
 723 /* Sorted sets data type */
 724 zskiplist *zslCreate(void);
 725 void zslFree(zskiplist *zsl);
 726 zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj);
 727
 728 /* Core functions */
 729 void freeMemoryIfNeeded(void);
 730 int processCommand(redisClient *c);
 731 void setupSigSegvAction(void);
 732 struct redisCommand *lookupCommand(char *name);
 733 void call(redisClient *c, struct redisCommand *cmd);
 734 int prepareForShutdown();
 735 void redisLog(int level, const char *fmt, ...);
 736 void usage();
 737 void updateDictResizePolicy(void);
 738 int htNeedsResize(dict *dict);
 739 void oom(const char *msg);
 740
 741 /* Virtual Memory */
 742 void vmInit(void);
 743 void vmMarkPagesFree(off_t page, off_t count);
 744 robj *vmLoadObject(robj *o);
 745 robj *vmPreviewObject(robj *o);
 746 int vmSwapOneObjectBlocking(void);
 747 int vmSwapOneObjectThreaded(void);
 748 int vmCanSwapOut(void);
 749 void vmThreadedIOCompletedJob(aeEventLoop *el, int fd, void *privdata, int mask);
 750 void vmCancelThreadedIOJob(robj *o);
 751 void lockThreadedIO(void);
 752 void unlockThreadedIO(void);
 753 int vmSwapObjectThreaded(robj *key, robj *val, redisDb *db);
 754 void freeIOJob(iojob *j);
 755 void queueIOJob(iojob *j);
 756 int vmWriteObjectOnSwap(robj *o, off_t page);
 757 robj *vmReadObjectFromSwap(off_t page, int type);
 758 void waitEmptyIOJobsQueue(void);
 759 void vmReopenSwapFile(void);
 760 int vmFreePage(off_t page);
 761 void zunionInterBlockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd, int argc, robj **argv);
 762 void execBlockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd, int argc, robj **argv);
 763 int blockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd);
 764 int dontWaitForSwappedKey(redisClient *c, robj *key);
 765 void handleClientsBlockedOnSwappedKey(redisDb *db, robj *key);
 766 vmpointer *vmSwapObjectBlocking(robj *val);
 767
 768 /* Set data type */
 769 robj *setTypeCreate(robj *value);
 770 int setTypeAdd(robj *subject, robj *value);
 771 int setTypeRemove(robj *subject, robj *value);
 772 int setTypeIsMember(robj *subject, robj *value);
 773 setTypeIterator *setTypeInitIterator(robj *subject);
 774 void setTypeReleaseIterator(setTypeIterator *si);
 775 robj *setTypeNext(setTypeIterator *si);
 776 robj *setTypeRandomElement(robj *subject);
 777 unsigned long setTypeSize(robj *subject);
 778 void setTypeConvert(robj *subject, int enc);
 779
 780 /* Hash data type */
 781 void convertToRealHash(robj *o);
 782 void hashTypeTryConversion(robj *subject, robj **argv, int start, int end);
 783 void hashTypeTryObjectEncoding(robj *subject, robj **o1, robj **o2);
 784 robj *hashTypeGet(robj *o, robj *key);
 785 int hashTypeExists(robj *o, robj *key);
 786 int hashTypeSet(robj *o, robj *key, robj *value);
 787 int hashTypeDelete(robj *o, robj *key);
 788 unsigned long hashTypeLength(robj *o);
 789 hashTypeIterator *hashTypeInitIterator(robj *subject);
 790 void hashTypeReleaseIterator(hashTypeIterator *hi);
 791 int hashTypeNext(hashTypeIterator *hi);
 792 robj *hashTypeCurrent(hashTypeIterator *hi, int what);
 793 robj *hashTypeLookupWriteOrCreate(redisClient *c, robj *key);
 794
 795 /* Pub / Sub */
 796 int pubsubUnsubscribeAllChannels(redisClient *c, int notify);
 797 int pubsubUnsubscribeAllPatterns(redisClient *c, int notify);
 798 void freePubsubPattern(void *p);
 799 int listMatchPubsubPattern(void *a, void *b);
 800
 801 /* Utility functions */
 802 int stringmatchlen(const char *pattern, int patternLen,
 803         const char *string, int stringLen, int nocase);
 804 int stringmatch(const char *pattern, const char *string, int nocase);
 805 long long memtoll(const char *p, int *err);
 806 int ll2string(char *s, size_t len, long long value);
 807 int isStringRepresentableAsLong(sds s, long *longval);
 808 int isStringRepresentableAsLongLong(sds s, long long *longval);
 809 int isObjectRepresentableAsLongLong(robj *o, long long *llongval);
 810
 811 /* Configuration */
 812 void loadServerConfig(char *filename);
 813 void appendServerSaveParams(time_t seconds, int changes);
 814 void resetServerSaveParams();
 815
 816 /* db.c -- Keyspace access API */
 817 int removeExpire(redisDb *db, robj *key);
 818 void propagateExpire(redisDb *db, robj *key);
 819 int expireIfNeeded(redisDb *db, robj *key);
 820 time_t getExpire(redisDb *db, robj *key);
 821 void setExpire(redisDb *db, robj *key, time_t when);
 822 robj *lookupKey(redisDb *db, robj *key);
 823 robj *lookupKeyRead(redisDb *db, robj *key);
 824 robj *lookupKeyWrite(redisDb *db, robj *key);
 825 robj *lookupKeyReadOrReply(redisClient *c, robj *key, robj *reply);
 826 robj *lookupKeyWriteOrReply(redisClient *c, robj *key, robj *reply);
 827 int dbAdd(redisDb *db, robj *key, robj *val);
 828 int dbReplace(redisDb *db, robj *key, robj *val);
 829 int dbExists(redisDb *db, robj *key);
 830 robj *dbRandomKey(redisDb *db);
 831 int dbDelete(redisDb *db, robj *key);
 832 long long emptyDb();
 833 int selectDb(redisClient *c, int id);
 834
 835 /* Git SHA1 */
 836 char *redisGitSHA1(void);
 837 char *redisGitDirty(void);
 838
 839 /* Commands prototypes */
 840 void authCommand(redisClient *c);
 841 void pingCommand(redisClient *c);
 842 void echoCommand(redisClient *c);
 843 void setCommand(redisClient *c);
 844 void setnxCommand(redisClient *c);
 845 void setexCommand(redisClient *c);
 846 void getCommand(redisClient *c);
 847 void delCommand(redisClient *c);
 848 void existsCommand(redisClient *c);
 849 void incrCommand(redisClient *c);
 850 void decrCommand(redisClient *c);
 851 void incrbyCommand(redisClient *c);
 852 void decrbyCommand(redisClient *c);
 853 void selectCommand(redisClient *c);
 854 void randomkeyCommand(redisClient *c);
 855 void keysCommand(redisClient *c);
 856 void dbsizeCommand(redisClient *c);
 857 void lastsaveCommand(redisClient *c);
 858 void saveCommand(redisClient *c);
 859 void bgsaveCommand(redisClient *c);
 860 void bgrewriteaofCommand(redisClient *c);
 861 void shutdownCommand(redisClient *c);
 862 void moveCommand(redisClient *c);
 863 void renameCommand(redisClient *c);
 864 void renamenxCommand(redisClient *c);
 865 void lpushCommand(redisClient *c);
 866 void rpushCommand(redisClient *c);
 867 void lpushxCommand(redisClient *c);
 868 void rpushxCommand(redisClient *c);
 869 void linsertCommand(redisClient *c);
 870 void lpopCommand(redisClient *c);
 871 void rpopCommand(redisClient *c);
 872 void llenCommand(redisClient *c);
 873 void lindexCommand(redisClient *c);
 874 void lrangeCommand(redisClient *c);
 875 void ltrimCommand(redisClient *c);
 876 void typeCommand(redisClient *c);
 877 void lsetCommand(redisClient *c);
 878 void saddCommand(redisClient *c);
 879 void sremCommand(redisClient *c);
 880 void smoveCommand(redisClient *c);
 881 void sismemberCommand(redisClient *c);
 882 void scardCommand(redisClient *c);
 883 void spopCommand(redisClient *c);
 884 void srandmemberCommand(redisClient *c);
 885 void sinterCommand(redisClient *c);
 886 void sinterstoreCommand(redisClient *c);
 887 void sunionCommand(redisClient *c);
 888 void sunionstoreCommand(redisClient *c);
 889 void sdiffCommand(redisClient *c);
 890 void sdiffstoreCommand(redisClient *c);
 891 void syncCommand(redisClient *c);
 892 void flushdbCommand(redisClient *c);
 893 void flushallCommand(redisClient *c);
 894 void sortCommand(redisClient *c);
 895 void lremCommand(redisClient *c);
 896 void rpoplpushcommand(redisClient *c);
 897 void infoCommand(redisClient *c);
 898 void mgetCommand(redisClient *c);
 899 void monitorCommand(redisClient *c);
 900 void expireCommand(redisClient *c);
 901 void expireatCommand(redisClient *c);
 902 void getsetCommand(redisClient *c);
 903 void ttlCommand(redisClient *c);
 904 void persistCommand(redisClient *c);
 905 void slaveofCommand(redisClient *c);
 906 void debugCommand(redisClient *c);
 907 void msetCommand(redisClient *c);
 908 void msetnxCommand(redisClient *c);
 909 void zaddCommand(redisClient *c);
 910 void zincrbyCommand(redisClient *c);
 911 void zrangeCommand(redisClient *c);
 912 void zrangebyscoreCommand(redisClient *c);
 913 void zcountCommand(redisClient *c);
 914 void zrevrangeCommand(redisClient *c);
 915 void zcardCommand(redisClient *c);
 916 void zremCommand(redisClient *c);
 917 void zscoreCommand(redisClient *c);
 918 void zremrangebyscoreCommand(redisClient *c);
 919 void multiCommand(redisClient *c);
 920 void execCommand(redisClient *c);
 921 void discardCommand(redisClient *c);
 922 void blpopCommand(redisClient *c);
 923 void brpopCommand(redisClient *c);
 924 void appendCommand(redisClient *c);
 925 void substrCommand(redisClient *c);
 926 void strlenCommand(redisClient *c);
 927 void zrankCommand(redisClient *c);
 928 void zrevrankCommand(redisClient *c);
 929 void hsetCommand(redisClient *c);
 930 void hsetnxCommand(redisClient *c);
 931 void hgetCommand(redisClient *c);
 932 void hmsetCommand(redisClient *c);
 933 void hmgetCommand(redisClient *c);
 934 void hdelCommand(redisClient *c);
 935 void hlenCommand(redisClient *c);
 936 void zremrangebyrankCommand(redisClient *c);
 937 void zunionstoreCommand(redisClient *c);
 938 void zinterstoreCommand(redisClient *c);
 939 void hkeysCommand(redisClient *c);
 940 void hvalsCommand(redisClient *c);
 941 void hgetallCommand(redisClient *c);
 942 void hexistsCommand(redisClient *c);
 943 void configCommand(redisClient *c);
 944 void hincrbyCommand(redisClient *c);
 945 void subscribeCommand(redisClient *c);
 946 void unsubscribeCommand(redisClient *c);
 947 void psubscribeCommand(redisClient *c);
 948 void punsubscribeCommand(redisClient *c);
 949 void publishCommand(redisClient *c);
 950 void watchCommand(redisClient *c);
 951 void unwatchCommand(redisClient *c);
 952
 953 #if defined(__GNUC__)
 954 void *calloc(size_t count, size_t size) __attribute__ ((deprecated));
 955 void free(void *ptr) __attribute__ ((deprecated));
 956 void *malloc(size_t size) __attribute__ ((deprecated));
 957 void *realloc(void *ptr, size_t size) __attribute__ ((deprecated));
 958 #endif
 959
 960 #endif