memcached.h

/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */

/** \file
 * The main memcached header holding commonly used data
 * structures and function prototypes.
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdio.h>
#include <sys/types.h>
#include <sys/time.h>
#include <event.h>
#include <stdbool.h>
#include <stdint.h>
#include <pthread.h>

#include "work.h"
#include "genhash.h"

#include "protocol_binary.h"
#include "cache.h"

/** Maximum length of a key. */
#define KEY_MAX_LENGTH 250

/** Size of an incr buf. */
#define INCR_MAX_STORAGE_LEN 24

#define DATA_BUFFER_SIZE 2048
#define UDP_READ_BUFFER_SIZE 65536
#define UDP_MAX_PAYLOAD_SIZE 1400
#define UDP_HEADER_SIZE 8
#define MAX_SENDBUF_SIZE (256 * 1024 * 1024)

/* Port values */
#define EPHEMERAL -1
#define UNSPECIFIED -2

/* No. of seconds in 30 days - largest possible delta exptime. */
#define REALTIME_MAXDELTA 60*60*24*30

/* I'm told the max length of a 64-bit num converted to string is 20 bytes.
 * Plus a few for spaces, \r\n, \0 */
#define SUFFIX_SIZE 200

/** Initial size of list of items being returned by "get". */
#define ITEM_LIST_INITIAL 200

/** Initial size of list of CAS suffixes appended to "gets" lines. */
#define SUFFIX_LIST_INITIAL 20

/** Initial size of the sendmsg() scatter/gather array. */
#define IOV_LIST_INITIAL 400

/** Initial number of sendmsg() argument structures to allocate. */
#define MSG_LIST_INITIAL 10

/** High water marks for buffer shrinking */
#define READ_BUFFER_HIGHWAT 8192
#define ITEM_LIST_HIGHWAT 400
#define IOV_LIST_HIGHWAT 600
#define MSG_LIST_HIGHWAT 100

/* Binary protocol stuff */
#define MIN_BIN_PKT_LENGTH 16
#define BIN_PKT_HDR_WORDS (MIN_BIN_PKT_LENGTH/sizeof(uint32_t))

/* unistd.h is here */
#if HAVE_UNISTD_H
# include <unistd.h>
#endif

/* Slab sizing definitions. */
#define POWER_SMALLEST 1
#define POWER_LARGEST  200
#define POWER_BLOCK 1048576
#define CHUNK_ALIGN_BYTES 8
#define DONT_PREALLOC_SLABS
#define MAX_NUMBER_OF_SLAB_CLASSES (POWER_LARGEST + 1)

/** How long an object can reasonably be assumed to be locked before
    harvesting it on a low memory condition. */
#define TAIL_REPAIR_TIME (3 * 3600)

/* warning: don't use these macros with a function, as it evals its arg twice */
#define ITEM_get_cas(i) ((uint64_t)(((i)->it_flags & ITEM_CAS) ? \
                                    *(uint64_t*)&((i)->end[0]) : 0x0))
#define ITEM_set_cas(i,v) { if ((i)->it_flags & ITEM_CAS) { \
                          *(uint64_t*)&((i)->end[0]) = v; } }

#define ITEM_key(item) (((char*)&((item)->end[0])) \
         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))

#define ITEM_suffix(item) ((char*) &((item)->end[0]) + (item)->nkey + 1 \
         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))

#define ITEM_data(item) ((char*) &((item)->end[0]) + (item)->nkey + 1 \
         + (item)->nsuffix \
         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))

#define ITEM_ntotal(item) (sizeof(struct _stritem) + (item)->nkey + 1 \
         + (item)->nsuffix + (item)->nbytes \
         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))

#define STAT_KEY_LEN 128
#define STAT_VAL_LEN 128

/** Append a simple stat with a stat name, value format and value */
#define APPEND_STAT(name, fmt, val) \
    append_stat(name, add_stats, c, fmt, val);

#define APPEND_PREFIX_STAT(name, fmt, val) \
    append_prefix_stat(prefix, name, add_stats, c, fmt, val);

/** Append an indexed stat with a stat name (with format), value format
    and value */
#define APPEND_NUM_FMT_STAT(name_fmt, num, name, fmt, val)          \
    klen = snprintf(key_str, STAT_KEY_LEN, name_fmt, num, name);    \
    vlen = snprintf(val_str, STAT_VAL_LEN, fmt, val);               \
    add_stats(key_str, klen, val_str, vlen, c);

/** Common APPEND_NUM_FMT_STAT format. */
#define APPEND_NUM_STAT(num, name, fmt, val) \
    APPEND_NUM_FMT_STAT("%d:%s", num, name, fmt, val)

/**
 * Callback for any function producing stats.
 *
 * @param key the stat's key
 * @param klen length of the key
 * @param val the stat's value in an ascii form (e.g. text form of a number)
 * @param vlen length of the value
 * @parm cookie magic callback cookie
 */
typedef void (*ADD_STAT)(const char *key, const uint16_t klen,
                         const char *val, const uint32_t vlen,
                         const void *cookie);

/*
 * NOTE: If you modify this table you _MUST_ update the function state_text
 */
/**
 * Possible states of a connection.
 */
enum conn_states {
    conn_listening,  /**< the socket which listens for connections */
    conn_new_cmd,    /**< Prepare connection for next command */
    conn_waiting,    /**< waiting for a readable socket */
    conn_read,       /**< reading in a command line */
    conn_parse_cmd,  /**< try to parse a command from the input buffer */
    conn_write,      /**< writing out a simple response */
    conn_nread,      /**< reading in a fixed number of bytes */
    conn_swallow,    /**< swallowing unnecessary bytes w/o storing */
    conn_closing,    /**< closing this connection */
    conn_mwrite,     /**< writing out many items sequentially */
    conn_pause,      /**< waiting for asynchronous event */
    conn_connecting, /**< the socket is in connecting state*/
    conn_max_state   /**< Max state value (used for assertion) */
};

enum bin_substates {
    bin_no_state,
    bin_reading_set_header,
    bin_reading_cas_header,
    bin_read_set_value,
    bin_reading_get_key,
    bin_reading_stat,
    bin_reading_del_header,
    bin_reading_incr_header,
    bin_read_flush_exptime
};

enum protocol {
    ascii_prot = 3, /* arbitrary value. */
    binary_prot,
    proxy_upstream_ascii_prot,
    proxy_upstream_binary_prot,
    proxy_downstream_ascii_prot,
    proxy_downstream_binary_prot,
    negotiating_proxy_prot,
    negotiating_prot /* Discovering the protocol */
};

enum network_transport {
    local_transport, /* Unix sockets*/
    tcp_transport,
    udp_transport
};

#define IS_UDP(x) (x == udp_transport)
#define IS_ASCII(x) (x == ascii_prot || \
                     x == proxy_upstream_ascii_prot || \
                     x == proxy_downstream_ascii_prot)
#define IS_BINARY(x) (x == binary_prot || \
                      x == proxy_upstream_binary_prot || \
                      x == proxy_downstream_binary_prot)
#define IS_NEGOTIATING(x) (x == negotiating_prot || \
                           x == negotiating_proxy_prot)
#define IS_PROXY(x) (x == proxy_upstream_ascii_prot || \
                     x == proxy_upstream_binary_prot || \
                     x == proxy_downstream_ascii_prot || \
                     x == proxy_downstream_binary_prot || \
                     x == negotiating_proxy_prot)
#define IS_DOWNSTREAM(x) (x == proxy_downstream_ascii_prot || \
                          x == proxy_downstream_binary_prot)

#define NREAD_ADD 1
#define NREAD_SET 2
#define NREAD_REPLACE 3
#define NREAD_APPEND 4
#define NREAD_PREPEND 5
#define NREAD_CAS 6

enum store_item_type {
    NOT_STORED=0, STORED, EXISTS, NOT_FOUND
};

enum delta_result_type {
    OK, NON_NUMERIC, EOM
};

/** Time relative to server start. Smaller than time_t on 64-bit systems. */
typedef unsigned int rel_time_t;

/** Stats stored per slab (and per thread). */
struct slab_stats {
    uint64_t  set_cmds;
    uint64_t  get_hits;
    uint64_t  delete_hits;
    uint64_t  cas_hits;
    uint64_t  cas_badval;
    uint64_t  incr_hits;
    uint64_t  decr_hits;
};

/**
 * Stats stored per-thread.
 */
struct thread_stats {
    pthread_mutex_t   mutex;
    uint64_t          get_cmds;
    uint64_t          get_misses;
    uint64_t          delete_misses;
    uint64_t          incr_misses;
    uint64_t          decr_misses;
    uint64_t          cas_misses;
    uint64_t          bytes_read;
    uint64_t          bytes_written;
    uint64_t          flush_cmds;
    uint64_t          conn_yields; /* # of yields for connections (-R option)*/
    struct slab_stats slab_stats[MAX_NUMBER_OF_SLAB_CLASSES];
};

/**
 * Global stats.
 */
struct stats {
    pthread_mutex_t mutex;
    unsigned int  curr_items;
    unsigned int  total_items;
    uint64_t      curr_bytes;
    unsigned int  curr_conns;
    unsigned int  total_conns;
    unsigned int  conn_structs;
    uint64_t      get_cmds;
    uint64_t      set_cmds;
    uint64_t      get_hits;
    uint64_t      get_misses;
    uint64_t      evictions;
    time_t        started;          /* when the process was started */
    bool          accepting_conns;  /* whether we are currently accepting */
    uint64_t      listen_disabled_num;
};

struct proxy_stats_cmd_info {
    bool do_info;
    bool do_settings;
    bool do_behaviors;
    bool do_frontcache;
    bool do_keystats;
    bool do_stats;
    bool do_zeros; /* might be used later */
};

#define MAX_VERBOSITY_LEVEL 4

/* When adding a setting, be sure to update process_stat_settings */
/**
 * Globally accessible settings as derived from the commandline.
 */
struct settings {
    size_t maxbytes;
    int maxconns;
    int port;
    int udpport;
    char *inter;
    int verbose;
    rel_time_t oldest_live; /* ignore existing items older than this */
    int evict_to_free;
    char *socketpath;   /* path to unix socket if using local socket */
    int access;  /* access mask (a la chmod) for unix domain socket */
    double factor;          /* chunk size growth factor */
    int chunk_size;
    int num_threads;        /* number of libevent threads to run */
    char prefix_delimiter;  /* character that marks a key prefix (for stats) */
    int detail_enabled;     /* nonzero if we're collecting detailed stats */
    int reqs_per_event;     /* Maximum number of io to process on each
                               io-event. */
    bool use_cas;
    enum protocol binding_protocol;
    int backlog;
    bool enable_mcmux_mode; /* enable mcmux compatiblity mode, disables libvbucket/libmemcached support */
};

extern struct stats stats;
extern time_t process_started;
extern struct settings settings;

#define ITEM_LINKED 1
#define ITEM_CAS 2

/* temp */
#define ITEM_SLABBED 4

/**
 * Structure for storing items within memcached.
 */
typedef struct _stritem {
    struct _stritem *next;
    struct _stritem *prev;
    struct _stritem *h_next;    /* hash chain next */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    void * end[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

typedef struct bin_cmd bin_cmd;

struct bin_cmd {
    item *request_item;  // Has 1 refcount.
    item *response_item; // Has 1 refcount.
    bin_cmd *next;
};

typedef struct {
    pthread_t thread_id;        /* unique ID of this thread */
    struct event_base *base;    /* libevent handle this thread uses */
    struct event notify_event;  /* listen event for notify pipe */
    int notify_receive_fd;      /* receiving end of notify pipe */
    int notify_send_fd;         /* sending end of notify pipe */
    struct thread_stats stats;  /* Stats generated by this thread */
    struct conn_queue *new_conn_queue; /* queue of new connections to handle */
    cache_t *suffix_cache;      /* suffix cache */
    work_queue *work_queue;
    genhash_t *conn_hash;       /* per thread connection hash, keyed by host_ident */
} LIBEVENT_THREAD;

/**
 * The structure representing a connection into memcached.
 */
typedef struct conn conn;
typedef struct conn_funcs conn_funcs;

struct conn_funcs {
    /* Function pointers so that drive_machine loop is reusable. */
    bool (*conn_init)(conn *c);
    void (*conn_close)(conn *c);
    bool (*conn_connect)(conn *c);
    void (*conn_process_ascii_command)(conn *c, char *command);
    void (*conn_process_binary_command)(conn *c);
    void (*conn_complete_nread_ascii)(conn *c);
    void (*conn_complete_nread_binary)(conn *c);
    void (*conn_pause)(conn *c);
    rel_time_t (*conn_realtime)(const time_t exptime);
    void (*conn_state_change)(conn *c, enum conn_states next_state);

    /* PROTOCOL_BINARY_REQ/RES */
    uint8_t conn_binary_command_magic;
};

struct conn {
    int    sfd;
    enum conn_states  state;
    enum bin_substates substate;
    struct event event;
    short  ev_flags;
    short  which;   /** which events were just triggered */

    char   *rbuf;   /** buffer to read commands into */
    char   *rcurr;  /** but if we parsed some already, this is where we stopped */
    int    rsize;   /** total allocated size of rbuf */
    int    rbytes;  /** how much data, starting from rcur, do we have unparsed */

    char   *wbuf;
    char   *wcurr;
    int    wsize;
    int    wbytes;
    /** which state to go into after finishing current write */
    enum conn_states  write_and_go;
    void   *write_and_free; /** free this memory after finishing writing */

    char   *ritem;  /** when we read in an item's value, it goes here */
    int    rlbytes;

    /* data for the nread state */

    /**
     * item is used to hold an item structure created after reading the command
     * line of set/add/replace commands, but before we finished reading the actual
     * data. The data is read into ITEM_data(item) to avoid extra copying.
     */

    void   *item;     /* for commands set/add/replace  */

    /* data for the swallow state */
    int    sbytes;    /* how many bytes to swallow */

    /* data for the mwrite state */
    struct iovec *iov;
    int    iovsize;   /* number of elements allocated in iov[] */
    int    iovused;   /* number of elements used in iov[] */

    struct msghdr *msglist;
    int    msgsize;   /* number of elements allocated in msglist[] */
    int    msgused;   /* number of elements used in msglist[] */
    int    msgcurr;   /* element in msglist[] being transmitted now */
    int    msgbytes;  /* number of bytes in current msg */

    item   **ilist;   /* list of items to write out */
    int    isize;
    item   **icurr;
    int    ileft;

    char   **suffixlist;
    int    suffixsize;
    char   **suffixcurr;
    int    suffixleft;

    enum protocol protocol;   /* which protocol this connection speaks */
    enum network_transport transport; /* what transport is used by this connection */

    /* data for UDP clients */
    int    request_id; /* Incoming UDP request ID, if this is a UDP "connection" */
    struct sockaddr request_addr; /* Who sent the most recent request */
    socklen_t request_addr_size;
    unsigned char *hdrbuf; /* udp packet headers */
    int    hdrsize;   /* number of headers' worth of space is allocated */

    bool   noreply;   /* True if the reply should not be sent. */
    /* current stats command */
    struct {
        char *buffer;
        size_t size;
        size_t offset;
    } stats;

    /* Binary protocol stuff */
    /* This is where the binary header goes */
    protocol_binary_request_header binary_header;
    uint64_t cas; /* the cas to return */
    short cmd; /* current command being processed */
    int opaque;
    int keylen;
    conn *next;     /* Used for generating a list of conn structures */
    LIBEVENT_THREAD *thread; /* Pointer to the thread object serving this connection */

    conn_funcs *funcs;
    void *extra;

    protocol_binary_command cmd_curr;

    char     *cmd_start;      // Pointer into rbuf, snapshot of rcurr.
    uint64_t  cmd_start_time; // Snapshot of usec_now or msec_current_time.
    int       cmd_retries;

    bin_cmd *corked;

    char *host_ident; // Uniquely identifies a memcached server, including
                      // address:port and possibly optional bucket/usr/pwd info.
    char *peer_host;    // this and the following two paramters are used for mcmux
    unsigned int peer_protocol;  // compatiblity mode
    int peer_port;

    const char *update_diag;
};

extern conn *listen_conn;

typedef struct token_s {
    char *value;
    size_t length;
} token_t;

size_t tokenize_command(char *command, token_t *tokens,
                        const size_t max_tokens);

/* current time of day (updated periodically) */
extern volatile rel_time_t current_time;

/*
 * Functions
 */
void do_accept_new_conns(const bool do_accept);
enum delta_result_type do_add_delta(conn *c, item *item, const bool incr,
                                    const int64_t delta, char *buf);
enum store_item_type do_store_item(item *item, int comm, conn* c);

conn *conn_new(const int sfd, const enum conn_states init_state,
               const int event_flags, const int read_buffer_size,
               enum network_transport transport,
               struct event_base *base,
               conn_funcs *funcs, void *extra);
void conn_set_state(conn *c, enum conn_states state);
void add_bytes_read(conn *c, int bytes_read);
void out_string(conn *c, const char *str);

#define ___update_event_str(a) #a
#define __update_event_str(a) ___update_event_str(a)

#define update_event(c, new_flags) update_event_real(c, new_flags, (__FILE__ ":" __update_event_str(__LINE__)))
#define update_event_timed(c, new_flags, timeout) update_event_timed_real(c, new_flags, timeout, (__FILE__ ":" __update_event_str(__LINE__)))

bool update_event_real(conn *c, const int new_flags, const char *update_diag);
bool update_event_timed_real(conn *c, const int new_flags, struct timeval *timeout, const char *update_diag);

int try_read_command(conn *c);
void process_command(conn *c, char *command);
void process_update_command(conn *c, token_t *tokens, const size_t ntokens, int comm, bool handle_cas);
void process_stats_proxy_command(conn *c, token_t *tokens, const size_t ntokens);
void process_verbosity_command(conn *c, token_t *tokens, const size_t ntokens);
void dispatch_bin_command(conn *c);
void process_bin_noreply(conn *c);
void bin_read_key(conn *c, enum bin_substates next_substate, int extra);
char* binary_get_key(conn *c);
void* binary_get_request(conn *c);
uint64_t mc_swap64(uint64_t in);
void reset_cmd_handler(conn *c);
void complete_nread(conn *c);
void complete_nread_binary(conn *c);
void complete_nread_ascii(conn *c);
int ensure_iov_space(conn *c);
int add_iov(conn *c, const void *buf, int len);
int add_msghdr(conn *c);
void set_noreply_maybe(conn *c, token_t *tokens, size_t ntokens);

const char *state_text(enum conn_states state);

#ifndef WIN32
extern int daemonize(int nochdir, int noclose);
#endif

int server_socket(const int port,
                  enum network_transport transport,
                  FILE *portnum_file);

#ifdef HAVE_SYS_UN_H
int server_socket_unix(const char *path, int access_mask);
#endif

void drive_machine(conn *c);

void write_bin_response(conn *c, void *d, int hlen, int keylen, int dlen);
void write_bin_error(conn *c, protocol_binary_response_status err, int swallow);

#include "stats.h"
#include "slabs.h"
#include "assoc.h"
#include "items.h"
#include "trace.h"
#include "hash.h"
#include "util.h"

/*
 * Functions such as the libevent-related calls that need to do cross-thread
 * communication in multithreaded mode (rather than actually doing the work
 * in the current thread) are called via "dispatch_" frontends, which are
 * also #define-d to directly call the underlying code in singlethreaded mode.
 */

void thread_init(int nthreads, struct event_base *main_base);
int  thread_index(pthread_t thread_id);
LIBEVENT_THREAD *thread_by_index(int i);

int  dispatch_event_add(int thread, conn *c);

void dispatch_conn_new(int sfd, enum conn_states init_state,
                       int event_flags,
                       int read_buffer_size,
                       enum protocol prot,
                       enum network_transport transport,
                       conn_funcs *funcs, void *extra);

void dispatch_conn_new_to_thread(int tid, int sfd, enum conn_states init_state,
                                 int event_flags,
                                 int read_buffer_size,
                                 enum protocol prot,
                                 enum network_transport transport,
                                 conn_funcs *funcs, void *extra);

/* Lock wrappers for cache functions that are called from main loop. */
enum delta_result_type add_delta(conn *c, item *item, const int incr,
                                 const int64_t delta, char *buf);
void accept_new_conns(const bool do_accept);
conn *conn_from_freelist(void);
bool  conn_add_to_freelist(conn *c);
int   is_listen_thread(void);
item *item_alloc(char *key, size_t nkey, int flags, rel_time_t exptime, int nbytes);
char *item_cachedump(const unsigned int slabs_clsid, const unsigned int limit, unsigned int *bytes);
void  item_flush_expired(void);
item *item_get(const char *key, const size_t nkey);
int   item_link(item *it);
void  item_remove(item *it);
int   item_replace(item *it, item *new_it);
void  item_stats(ADD_STAT add_stats, void *c);
void  item_stats_sizes(ADD_STAT add_stats, void *c);
void  item_unlink(item *it);
void  item_update(item *it);

void STATS_LOCK(void);
void STATS_UNLOCK(void);
void threadlocal_stats_reset(void);
void threadlocal_stats_aggregate(struct thread_stats *stats);
void slab_stats_aggregate(struct thread_stats *stats, struct slab_stats *out);

/* Stat processing functions */
void append_stat(const char *name, ADD_STAT add_stats, void *c,
                 const char *fmt, ...);

void append_prefix_stat(const char *prefix, const char *name, ADD_STAT add_stats, void *c,
                        const char *fmt, ...);

void server_stats(ADD_STAT add_stats, void *c, const char *prefix);
void process_stat_settings(ADD_STAT add_stats, void *c, const char *prefix);

enum store_item_type store_item(item *item, int comm, conn *c);

#ifdef HAVE_DROP_PRIVILEGES
extern void drop_privileges(void);
#else
#define drop_privileges()
#endif

/* If supported, give compiler hints for branch prediction. */
#if !defined(__GNUC__) || (__GNUC__ == 2 && __GNUC_MINOR__ < 96)
#define __builtin_expect(x, expected_value) (x)
#endif

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

// used by unit tests
void start_main(char *arg0, ...);