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     /* Configuration */
 367     int verbosity;
 368     int glueoutputbuf;
 369     int maxidletime;
 370     int dbnum;
 371     int daemonize;
 372     int appendonly;
 373     int appendfsync;
 374     int no_appendfsync_on_rewrite;
 375     int shutdown_asap;
 376     time_t lastfsync;
 377     int appendfd;
 378     int appendseldb;
 379     char *pidfile;
 380     pid_t bgsavechildpid;
 381     pid_t bgrewritechildpid;
 382     sds bgrewritebuf; /* buffer taken by parent during oppend only rewrite */
 383     sds aofbuf;       /* AOF buffer, written before entering the event loop */
 384     struct saveparam *saveparams;
 385     int saveparamslen;
 386     char *logfile;
 387     char *bindaddr;
 388     char *dbfilename;
 389     char *appendfilename;
 390     char *requirepass;
 391     int rdbcompression;
 392     int activerehashing;
 393     /* Replication related */
 394     int isslave;
 395     char *masterauth;
 396     char *masterhost;
 397     int masterport;
 398     redisClient *master;    /* client that is master for this slave */
 399     int replstate;
 400     unsigned int maxclients;
 401     unsigned long long maxmemory;
 402     int maxmemory_policy;
 403     int maxmemory_samples;
 404     unsigned int blpop_blocked_clients;
 405     unsigned int vm_blocked_clients;
 406     /* Sort parameters - qsort_r() is only available under BSD so we
 407      * have to take this state global, in order to pass it to sortCompare() */
 408     int sort_desc;
 409     int sort_alpha;
 410     int sort_bypattern;
 411     /* Virtual memory configuration */
 412     int vm_enabled;
 413     char *vm_swap_file;
 414     off_t vm_page_size;
 415     off_t vm_pages;
 416     unsigned long long vm_max_memory;
 417     /* Zip structure config */
 418     size_t hash_max_zipmap_entries;
 419     size_t hash_max_zipmap_value;
 420     size_t list_max_ziplist_entries;
 421     size_t list_max_ziplist_value;
 422     size_t set_max_intset_entries;
 423     /* Virtual memory state */
 424     FILE *vm_fp;
 425     int vm_fd;
 426     off_t vm_next_page; /* Next probably empty page */
 427     off_t vm_near_pages; /* Number of pages allocated sequentially */
 428     unsigned char *vm_bitmap; /* Bitmap of free/used pages */
 429     time_t unixtime;    /* Unix time sampled every second. */
 430     /* Virtual memory I/O threads stuff */
 431     /* An I/O thread process an element taken from the io_jobs queue and
 432      * put the result of the operation in the io_done list. While the
 433      * job is being processed, it's put on io_processing queue. */
 434     list *io_newjobs; /* List of VM I/O jobs yet to be processed */
 435     list *io_processing; /* List of VM I/O jobs being processed */
 436     list *io_processed; /* List of VM I/O jobs already processed */
 437     list *io_ready_clients; /* Clients ready to be unblocked. All keys loaded */
 438     pthread_mutex_t io_mutex; /* lock to access io_jobs/io_done/io_thread_job */
 439     pthread_mutex_t obj_freelist_mutex; /* safe redis objects creation/free */
 440     pthread_mutex_t io_swapfile_mutex; /* So we can lseek + write */
 441     pthread_attr_t io_threads_attr; /* attributes for threads creation */
 442     int io_active_threads; /* Number of running I/O threads */
 443     int vm_max_threads; /* Max number of I/O threads running at the same time */
 444     /* Our main thread is blocked on the event loop, locking for sockets ready
 445      * to be read or written, so when a threaded I/O operation is ready to be
 446      * processed by the main thread, the I/O thread will use a unix pipe to
 447      * awake the main thread. The followings are the two pipe FDs. */
 448     int io_ready_pipe_read;
 449     int io_ready_pipe_write;
 450     /* Virtual memory stats */
 451     unsigned long long vm_stats_used_pages;
 452     unsigned long long vm_stats_swapped_objects;
 453     unsigned long long vm_stats_swapouts;
 454     unsigned long long vm_stats_swapins;
 455     /* Pubsub */
 456     dict *pubsub_channels; /* Map channels to list of subscribed clients */
 457     list *pubsub_patterns; /* A list of pubsub_patterns */
 458     /* Misc */
 459     FILE *devnull;
 460     unsigned lruclock:22;        /* clock incrementing every minute, for LRU */
 461     unsigned lruclock_padding:10;
 462 };
 463
 464 typedef struct pubsubPattern {
 465     redisClient *client;
 466     robj *pattern;
 467 } pubsubPattern;
 468
 469 typedef void redisCommandProc(redisClient *c);
 470 typedef void redisVmPreloadProc(redisClient *c, struct redisCommand *cmd, int argc, robj **argv);
 471 struct redisCommand {
 472     char *name;
 473     redisCommandProc *proc;
 474     int arity;
 475     int flags;
 476     /* Use a function to determine which keys need to be loaded
 477      * in the background prior to executing this command. Takes precedence
 478      * over vm_firstkey and others, ignored when NULL */
 479     redisVmPreloadProc *vm_preload_proc;
 480     /* What keys should be loaded in background when calling this command? */
 481     int vm_firstkey; /* The first argument that's a key (0 = no keys) */
 482     int vm_lastkey;  /* THe last argument that's a key */
 483     int vm_keystep;  /* The step between first and last key */
 484 };
 485
 486 struct redisFunctionSym {
 487     char *name;
 488     unsigned long pointer;
 489 };
 490
 491 typedef struct _redisSortObject {
 492     robj *obj;
 493     union {
 494         double score;
 495         robj *cmpobj;
 496     } u;
 497 } redisSortObject;
 498
 499 typedef struct _redisSortOperation {
 500     int type;
 501     robj *pattern;
 502 } redisSortOperation;
 503
 504 /* ZSETs use a specialized version of Skiplists */
 505 typedef struct zskiplistNode {
 506     robj *obj;
 507     double score;
 508     struct zskiplistNode *backward;
 509     struct zskiplistLevel {
 510         struct zskiplistNode *forward;
 511         unsigned int span;
 512     } level[];
 513 } zskiplistNode;
 514
 515 typedef struct zskiplist {
 516     struct zskiplistNode *header, *tail;
 517     unsigned long length;
 518     int level;
 519 } zskiplist;
 520
 521 typedef struct zset {
 522     dict *dict;
 523     zskiplist *zsl;
 524 } zset;
 525
 526 /* VM threaded I/O request message */
 527 #define REDIS_IOJOB_LOAD 0          /* Load from disk to memory */
 528 #define REDIS_IOJOB_PREPARE_SWAP 1  /* Compute needed pages */
 529 #define REDIS_IOJOB_DO_SWAP 2       /* Swap from memory to disk */
 530 typedef struct iojob {
 531     int type;   /* Request type, REDIS_IOJOB_* */
 532     redisDb *db;/* Redis database */
 533     robj *key;  /* This I/O request is about swapping this key */
 534     robj *id;   /* Unique identifier of this job:
 535                    this is the object to swap for REDIS_IOREQ_*_SWAP, or the
 536                    vmpointer objct for REDIS_IOREQ_LOAD. */
 537     robj *val;  /* the value to swap for REDIS_IOREQ_*_SWAP, otherwise this
 538                  * field is populated by the I/O thread for REDIS_IOREQ_LOAD. */
 539     off_t page; /* Swap page where to read/write the object */
 540     off_t pages; /* Swap pages needed to save object. PREPARE_SWAP return val */
 541     int canceled; /* True if this command was canceled by blocking side of VM */
 542     pthread_t thread; /* ID of the thread processing this entry */
 543 } iojob;
 544
 545 /* Structure to hold list iteration abstraction. */
 546 typedef struct {
 547     robj *subject;
 548     unsigned char encoding;
 549     unsigned char direction; /* Iteration direction */
 550     unsigned char *zi;
 551     listNode *ln;
 552 } listTypeIterator;
 553
 554 /* Structure for an entry while iterating over a list. */
 555 typedef struct {
 556     listTypeIterator *li;
 557     unsigned char *zi;  /* Entry in ziplist */
 558     listNode *ln;       /* Entry in linked list */
 559 } listTypeEntry;
 560
 561 /* Structure to hold set iteration abstraction. */
 562 typedef struct {
 563     robj *subject;
 564     int encoding;
 565     int ii; /* intset iterator */
 566     dictIterator *di;
 567 } setTypeIterator;
 568
 569 /* Structure to hold hash iteration abstration. Note that iteration over
 570  * hashes involves both fields and values. Because it is possible that
 571  * not both are required, store pointers in the iterator to avoid
 572  * unnecessary memory allocation for fields/values. */
 573 typedef struct {
 574     int encoding;
 575     unsigned char *zi;
 576     unsigned char *zk, *zv;
 577     unsigned int zklen, zvlen;
 578
 579     dictIterator *di;
 580     dictEntry *de;
 581 } hashTypeIterator;
 582
 583 #define REDIS_HASH_KEY 1
 584 #define REDIS_HASH_VALUE 2
 585
 586 /*-----------------------------------------------------------------------------
 587  * Extern declarations
 588  *----------------------------------------------------------------------------*/
 589
 590 extern struct redisServer server;
 591 extern struct sharedObjectsStruct shared;
 592 extern dictType setDictType;
 593 extern dictType zsetDictType;
 594 extern double R_Zero, R_PosInf, R_NegInf, R_Nan;
 595 dictType hashDictType;
 596
 597 /*-----------------------------------------------------------------------------
 598  * Functions prototypes
 599  *----------------------------------------------------------------------------*/
 600
 601 /* networking.c -- Networking and Client related operations */
 602 redisClient *createClient(int fd);
 603 void closeTimedoutClients(void);
 604 void freeClient(redisClient *c);
 605 void resetClient(redisClient *c);
 606 void sendReplyToClient(aeEventLoop *el, int fd, void *privdata, int mask);
 607 void sendReplyToClientWritev(aeEventLoop *el, int fd, void *privdata, int mask);
 608 void addReply(redisClient *c, robj *obj);
 609 void *addDeferredMultiBulkLength(redisClient *c);
 610 void setDeferredMultiBulkLength(redisClient *c, void *node, long length);
 611 void addReplySds(redisClient *c, sds s);
 612 void processInputBuffer(redisClient *c);
 613 void acceptHandler(aeEventLoop *el, int fd, void *privdata, int mask);
 614 void readQueryFromClient(aeEventLoop *el, int fd, void *privdata, int mask);
 615 void addReplyBulk(redisClient *c, robj *obj);
 616 void addReplyBulkCString(redisClient *c, char *s);
 617 void acceptHandler(aeEventLoop *el, int fd, void *privdata, int mask);
 618 void addReply(redisClient *c, robj *obj);
 619 void addReplySds(redisClient *c, sds s);
 620 void addReplyError(redisClient *c, char *err);
 621 void addReplyStatus(redisClient *c, char *status);
 622 void addReplyDouble(redisClient *c, double d);
 623 void addReplyLongLong(redisClient *c, long long ll);
 624 void addReplyMultiBulkLen(redisClient *c, long length);
 625 void *dupClientReplyValue(void *o);
 626
 627 #ifdef __GNUC__
 628 void addReplyErrorFormat(redisClient *c, const char *fmt, ...)
 629     __attribute__((format(printf, 2, 3)));
 630 void addReplyStatusFormat(redisClient *c, const char *fmt, ...)
 631     __attribute__((format(printf, 2, 3)));
 632 #else
 633 void addReplyErrorFormat(redisClient *c, const char *fmt, ...);
 634 void addReplyStatusFormat(redisClient *c, const char *fmt, ...);
 635 #endif
 636
 637 /* List data type */
 638 void listTypeTryConversion(robj *subject, robj *value);
 639 void listTypePush(robj *subject, robj *value, int where);
 640 robj *listTypePop(robj *subject, int where);
 641 unsigned long listTypeLength(robj *subject);
 642 listTypeIterator *listTypeInitIterator(robj *subject, int index, unsigned char direction);
 643 void listTypeReleaseIterator(listTypeIterator *li);
 644 int listTypeNext(listTypeIterator *li, listTypeEntry *entry);
 645 robj *listTypeGet(listTypeEntry *entry);
 646 void listTypeInsert(listTypeEntry *entry, robj *value, int where);
 647 int listTypeEqual(listTypeEntry *entry, robj *o);
 648 void listTypeDelete(listTypeEntry *entry);
 649 void listTypeConvert(robj *subject, int enc);
 650 void unblockClientWaitingData(redisClient *c);
 651 int handleClientsWaitingListPush(redisClient *c, robj *key, robj *ele);
 652 void popGenericCommand(redisClient *c, int where);
 653
 654 /* MULTI/EXEC/WATCH... */
 655 void unwatchAllKeys(redisClient *c);
 656 void initClientMultiState(redisClient *c);
 657 void freeClientMultiState(redisClient *c);
 658 void queueMultiCommand(redisClient *c, struct redisCommand *cmd);
 659 void touchWatchedKey(redisDb *db, robj *key);
 660 void touchWatchedKeysOnFlush(int dbid);
 661
 662 /* Redis object implementation */
 663 void decrRefCount(void *o);
 664 void incrRefCount(robj *o);
 665 void freeStringObject(robj *o);
 666 void freeListObject(robj *o);
 667 void freeSetObject(robj *o);
 668 void freeZsetObject(robj *o);
 669 void freeHashObject(robj *o);
 670 robj *createObject(int type, void *ptr);
 671 robj *createStringObject(char *ptr, size_t len);
 672 robj *dupStringObject(robj *o);
 673 robj *tryObjectEncoding(robj *o);
 674 robj *getDecodedObject(robj *o);
 675 size_t stringObjectLen(robj *o);
 676 int tryFreeOneObjectFromFreelist(void);
 677 robj *createStringObjectFromLongLong(long long value);
 678 robj *createListObject(void);
 679 robj *createZiplistObject(void);
 680 robj *createSetObject(void);
 681 robj *createIntsetObject(void);
 682 robj *createHashObject(void);
 683 robj *createZsetObject(void);
 684 int getLongFromObjectOrReply(redisClient *c, robj *o, long *target, const char *msg);
 685 int checkType(redisClient *c, robj *o, int type);
 686 int getLongLongFromObjectOrReply(redisClient *c, robj *o, long long *target, const char *msg);
 687 int getDoubleFromObjectOrReply(redisClient *c, robj *o, double *target, const char *msg);
 688 int getLongLongFromObject(robj *o, long long *target);
 689 char *strEncoding(int encoding);
 690 int compareStringObjects(robj *a, robj *b);
 691 int equalStringObjects(robj *a, robj *b);
 692 unsigned long estimateObjectIdleTime(robj *o);
 693
 694 /* Replication */
 695 void replicationFeedSlaves(list *slaves, int dictid, robj **argv, int argc);
 696 void replicationFeedMonitors(list *monitors, int dictid, robj **argv, int argc);
 697 int syncWithMaster(void);
 698 void updateSlavesWaitingBgsave(int bgsaveerr);
 699
 700 /* RDB persistence */
 701 int rdbLoad(char *filename);
 702 int rdbSaveBackground(char *filename);
 703 void rdbRemoveTempFile(pid_t childpid);
 704 int rdbSave(char *filename);
 705 int rdbSaveObject(FILE *fp, robj *o);
 706 off_t rdbSavedObjectPages(robj *o, FILE *fp);
 707 off_t rdbSavedObjectLen(robj *o, FILE *fp);
 708 robj *rdbLoadObject(int type, FILE *fp);
 709 void backgroundSaveDoneHandler(int statloc);
 710
 711 /* AOF persistence */
 712 void flushAppendOnlyFile(void);
 713 void feedAppendOnlyFile(struct redisCommand *cmd, int dictid, robj **argv, int argc);
 714 void aofRemoveTempFile(pid_t childpid);
 715 int rewriteAppendOnlyFileBackground(void);
 716 int loadAppendOnlyFile(char *filename);
 717 void stopAppendOnly(void);
 718 int startAppendOnly(void);
 719 void backgroundRewriteDoneHandler(int statloc);
 720
 721 /* Sorted sets data type */
 722 zskiplist *zslCreate(void);
 723 void zslFree(zskiplist *zsl);
 724 zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj);
 725
 726 /* Core functions */
 727 void freeMemoryIfNeeded(void);
 728 int processCommand(redisClient *c);
 729 void setupSigSegvAction(void);
 730 struct redisCommand *lookupCommand(char *name);
 731 void call(redisClient *c, struct redisCommand *cmd);
 732 int prepareForShutdown();
 733 void redisLog(int level, const char *fmt, ...);
 734 void usage();
 735 void updateDictResizePolicy(void);
 736 int htNeedsResize(dict *dict);
 737 void oom(const char *msg);
 738
 739 /* Virtual Memory */
 740 void vmInit(void);
 741 void vmMarkPagesFree(off_t page, off_t count);
 742 robj *vmLoadObject(robj *o);
 743 robj *vmPreviewObject(robj *o);
 744 int vmSwapOneObjectBlocking(void);
 745 int vmSwapOneObjectThreaded(void);
 746 int vmCanSwapOut(void);
 747 void vmThreadedIOCompletedJob(aeEventLoop *el, int fd, void *privdata, int mask);
 748 void vmCancelThreadedIOJob(robj *o);
 749 void lockThreadedIO(void);
 750 void unlockThreadedIO(void);
 751 int vmSwapObjectThreaded(robj *key, robj *val, redisDb *db);
 752 void freeIOJob(iojob *j);
 753 void queueIOJob(iojob *j);
 754 int vmWriteObjectOnSwap(robj *o, off_t page);
 755 robj *vmReadObjectFromSwap(off_t page, int type);
 756 void waitEmptyIOJobsQueue(void);
 757 void vmReopenSwapFile(void);
 758 int vmFreePage(off_t page);
 759 void zunionInterBlockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd, int argc, robj **argv);
 760 void execBlockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd, int argc, robj **argv);
 761 int blockClientOnSwappedKeys(redisClient *c, struct redisCommand *cmd);
 762 int dontWaitForSwappedKey(redisClient *c, robj *key);
 763 void handleClientsBlockedOnSwappedKey(redisDb *db, robj *key);
 764 vmpointer *vmSwapObjectBlocking(robj *val);
 765
 766 /* Set data type */
 767 robj *setTypeCreate(robj *value);
 768 int setTypeAdd(robj *subject, robj *value);
 769 int setTypeRemove(robj *subject, robj *value);
 770 int setTypeIsMember(robj *subject, robj *value);
 771 setTypeIterator *setTypeInitIterator(robj *subject);
 772 void setTypeReleaseIterator(setTypeIterator *si);
 773 robj *setTypeNext(setTypeIterator *si);
 774 robj *setTypeRandomElement(robj *subject);
 775 unsigned long setTypeSize(robj *subject);
 776 void setTypeConvert(robj *subject, int enc);
 777
 778 /* Hash data type */
 779 void convertToRealHash(robj *o);
 780 void hashTypeTryConversion(robj *subject, robj **argv, int start, int end);
 781 void hashTypeTryObjectEncoding(robj *subject, robj **o1, robj **o2);
 782 robj *hashTypeGet(robj *o, robj *key);
 783 int hashTypeExists(robj *o, robj *key);
 784 int hashTypeSet(robj *o, robj *key, robj *value);
 785 int hashTypeDelete(robj *o, robj *key);
 786 unsigned long hashTypeLength(robj *o);
 787 hashTypeIterator *hashTypeInitIterator(robj *subject);
 788 void hashTypeReleaseIterator(hashTypeIterator *hi);
 789 int hashTypeNext(hashTypeIterator *hi);
 790 robj *hashTypeCurrent(hashTypeIterator *hi, int what);
 791 robj *hashTypeLookupWriteOrCreate(redisClient *c, robj *key);
 792
 793 /* Pub / Sub */
 794 int pubsubUnsubscribeAllChannels(redisClient *c, int notify);
 795 int pubsubUnsubscribeAllPatterns(redisClient *c, int notify);
 796 void freePubsubPattern(void *p);
 797 int listMatchPubsubPattern(void *a, void *b);
 798
 799 /* Utility functions */
 800 int stringmatchlen(const char *pattern, int patternLen,
 801         const char *string, int stringLen, int nocase);
 802 int stringmatch(const char *pattern, const char *string, int nocase);
 803 long long memtoll(const char *p, int *err);
 804 int ll2string(char *s, size_t len, long long value);
 805 int isStringRepresentableAsLong(sds s, long *longval);
 806 int isStringRepresentableAsLongLong(sds s, long long *longval);
 807 int isObjectRepresentableAsLongLong(robj *o, long long *llongval);
 808
 809 /* Configuration */
 810 void loadServerConfig(char *filename);
 811 void appendServerSaveParams(time_t seconds, int changes);
 812 void resetServerSaveParams();
 813
 814 /* db.c -- Keyspace access API */
 815 int removeExpire(redisDb *db, robj *key);
 816 void propagateExpire(redisDb *db, robj *key);
 817 int expireIfNeeded(redisDb *db, robj *key);
 818 time_t getExpire(redisDb *db, robj *key);
 819 void setExpire(redisDb *db, robj *key, time_t when);
 820 robj *lookupKey(redisDb *db, robj *key);
 821 robj *lookupKeyRead(redisDb *db, robj *key);
 822 robj *lookupKeyWrite(redisDb *db, robj *key);
 823 robj *lookupKeyReadOrReply(redisClient *c, robj *key, robj *reply);
 824 robj *lookupKeyWriteOrReply(redisClient *c, robj *key, robj *reply);
 825 int dbAdd(redisDb *db, robj *key, robj *val);
 826 int dbReplace(redisDb *db, robj *key, robj *val);
 827 int dbExists(redisDb *db, robj *key);
 828 robj *dbRandomKey(redisDb *db);
 829 int dbDelete(redisDb *db, robj *key);
 830 long long emptyDb();
 831 int selectDb(redisClient *c, int id);
 832
 833 /* Git SHA1 */
 834 char *redisGitSHA1(void);
 835 char *redisGitDirty(void);
 836
 837 /* Commands prototypes */
 838 void authCommand(redisClient *c);
 839 void pingCommand(redisClient *c);
 840 void echoCommand(redisClient *c);
 841 void setCommand(redisClient *c);
 842 void setnxCommand(redisClient *c);
 843 void setexCommand(redisClient *c);
 844 void getCommand(redisClient *c);
 845 void delCommand(redisClient *c);
 846 void existsCommand(redisClient *c);
 847 void incrCommand(redisClient *c);
 848 void decrCommand(redisClient *c);
 849 void incrbyCommand(redisClient *c);
 850 void decrbyCommand(redisClient *c);
 851 void selectCommand(redisClient *c);
 852 void randomkeyCommand(redisClient *c);
 853 void keysCommand(redisClient *c);
 854 void dbsizeCommand(redisClient *c);
 855 void lastsaveCommand(redisClient *c);
 856 void saveCommand(redisClient *c);
 857 void bgsaveCommand(redisClient *c);
 858 void bgrewriteaofCommand(redisClient *c);
 859 void shutdownCommand(redisClient *c);
 860 void moveCommand(redisClient *c);
 861 void renameCommand(redisClient *c);
 862 void renamenxCommand(redisClient *c);
 863 void lpushCommand(redisClient *c);
 864 void rpushCommand(redisClient *c);
 865 void lpushxCommand(redisClient *c);
 866 void rpushxCommand(redisClient *c);
 867 void linsertCommand(redisClient *c);
 868 void lpopCommand(redisClient *c);
 869 void rpopCommand(redisClient *c);
 870 void llenCommand(redisClient *c);
 871 void lindexCommand(redisClient *c);
 872 void lrangeCommand(redisClient *c);
 873 void ltrimCommand(redisClient *c);
 874 void typeCommand(redisClient *c);
 875 void lsetCommand(redisClient *c);
 876 void saddCommand(redisClient *c);
 877 void sremCommand(redisClient *c);
 878 void smoveCommand(redisClient *c);
 879 void sismemberCommand(redisClient *c);
 880 void scardCommand(redisClient *c);
 881 void spopCommand(redisClient *c);
 882 void srandmemberCommand(redisClient *c);
 883 void sinterCommand(redisClient *c);
 884 void sinterstoreCommand(redisClient *c);
 885 void sunionCommand(redisClient *c);
 886 void sunionstoreCommand(redisClient *c);
 887 void sdiffCommand(redisClient *c);
 888 void sdiffstoreCommand(redisClient *c);
 889 void syncCommand(redisClient *c);
 890 void flushdbCommand(redisClient *c);
 891 void flushallCommand(redisClient *c);
 892 void sortCommand(redisClient *c);
 893 void lremCommand(redisClient *c);
 894 void rpoplpushcommand(redisClient *c);
 895 void infoCommand(redisClient *c);
 896 void mgetCommand(redisClient *c);
 897 void monitorCommand(redisClient *c);
 898 void expireCommand(redisClient *c);
 899 void expireatCommand(redisClient *c);
 900 void getsetCommand(redisClient *c);
 901 void ttlCommand(redisClient *c);
 902 void persistCommand(redisClient *c);
 903 void slaveofCommand(redisClient *c);
 904 void debugCommand(redisClient *c);
 905 void msetCommand(redisClient *c);
 906 void msetnxCommand(redisClient *c);
 907 void zaddCommand(redisClient *c);
 908 void zincrbyCommand(redisClient *c);
 909 void zrangeCommand(redisClient *c);
 910 void zrangebyscoreCommand(redisClient *c);
 911 void zcountCommand(redisClient *c);
 912 void zrevrangeCommand(redisClient *c);
 913 void zcardCommand(redisClient *c);
 914 void zremCommand(redisClient *c);
 915 void zscoreCommand(redisClient *c);
 916 void zremrangebyscoreCommand(redisClient *c);
 917 void multiCommand(redisClient *c);
 918 void execCommand(redisClient *c);
 919 void discardCommand(redisClient *c);
 920 void blpopCommand(redisClient *c);
 921 void brpopCommand(redisClient *c);
 922 void appendCommand(redisClient *c);
 923 void substrCommand(redisClient *c);
 924 void strlenCommand(redisClient *c);
 925 void zrankCommand(redisClient *c);
 926 void zrevrankCommand(redisClient *c);
 927 void hsetCommand(redisClient *c);
 928 void hsetnxCommand(redisClient *c);
 929 void hgetCommand(redisClient *c);
 930 void hmsetCommand(redisClient *c);
 931 void hmgetCommand(redisClient *c);
 932 void hdelCommand(redisClient *c);
 933 void hlenCommand(redisClient *c);
 934 void zremrangebyrankCommand(redisClient *c);
 935 void zunionstoreCommand(redisClient *c);
 936 void zinterstoreCommand(redisClient *c);
 937 void hkeysCommand(redisClient *c);
 938 void hvalsCommand(redisClient *c);
 939 void hgetallCommand(redisClient *c);
 940 void hexistsCommand(redisClient *c);
 941 void configCommand(redisClient *c);
 942 void hincrbyCommand(redisClient *c);
 943 void subscribeCommand(redisClient *c);
 944 void unsubscribeCommand(redisClient *c);
 945 void psubscribeCommand(redisClient *c);
 946 void punsubscribeCommand(redisClient *c);
 947 void publishCommand(redisClient *c);
 948 void watchCommand(redisClient *c);
 949 void unwatchCommand(redisClient *c);
 950
 951 #if defined(__GNUC__)
 952 void *calloc(size_t count, size_t size) __attribute__ ((deprecated));
 953 void free(void *ptr) __attribute__ ((deprecated));
 954 void *malloc(size_t size) __attribute__ ((deprecated));
 955 void *realloc(void *ptr, size_t size) __attribute__ ((deprecated));
 956 #endif
 957
 958 #endif