git.m6w6.name Git - awesomized/libmemcached/blob - memcached/assoc.c

   1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 /*
   3  * Hash table
   4  *
   5  * The hash function used here is by Bob Jenkins, 1996:
   6  *    <http://burtleburtle.net/bob/hash/doobs.html>
   7  *       "By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.
   8  *       You may use this code any way you wish, private, educational,
   9  *       or commercial.  It's free."
  10  *
  11  * The rest of the file is licensed under the BSD license.  See LICENSE.
  12  */
  13
  14 #include "memcached.h"
  15
  16 #include <sys/stat.h>
  17 #include <sys/socket.h>
  18 #include <sys/signal.h>
  19 #include <sys/resource.h>
  20 #include <fcntl.h>
  21 #include <netinet/in.h>
  22 #include <errno.h>
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <assert.h>
  27 #include <pthread.h>
  28
  29 static pthread_cond_t maintenance_cond = PTHREAD_COND_INITIALIZER;
  30
  31 #ifndef __INTEL_COMPILER
  32 #pragma GCC diagnostic ignored "-Wstrict-aliasing"
  33 #endif
  34
  35 #ifndef __INTEL_COMPILER
  36 #pragma GCC diagnostic ignored "-Wunused-parameter"
  37 #endif
  38
  39 typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
  40 typedef  unsigned       char ub1;   /* unsigned 1-byte quantities */
  41
  42 /* how many powers of 2's worth of buckets we use */
  43 static unsigned int hashpower = HASHPOWER_DEFAULT;
  44
  45 #define hashsize(n) ((ub4)1<<(n))
  46 #define hashmask(n) (hashsize(n)-1)
  47
  48 /* Main hash table. This is where we look except during expansion. */
  49 static item** primary_hashtable = 0;
  50
  51 /*
  52  * Previous hash table. During expansion, we look here for keys that haven't
  53  * been moved over to the primary yet.
  54  */
  55 static item** old_hashtable = 0;
  56
  57 /* Number of items in the hash table. */
  58 static unsigned int hash_items = 0;
  59
  60 /* Flag: Are we in the middle of expanding now? */
  61 static bool expanding = false;
  62
  63 /*
  64  * During expansion we migrate values with bucket granularity; this is how
  65  * far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1.
  66  */
  67 static unsigned int expand_bucket = 0;
  68
  69 void assoc_init(const int hashtable_init) {
  70     if (hashtable_init) {
  71         hashpower = hashtable_init;
  72     }
  73     primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
  74     if (! primary_hashtable) {
  75         fprintf(stderr, "Failed to init hashtable.\n");
  76         exit(EXIT_FAILURE);
  77     }
  78     STATS_LOCK();
  79     stats.hash_power_level = hashpower;
  80     stats.hash_bytes = hashsize(hashpower) * sizeof(void *);
  81     STATS_UNLOCK();
  82 }
  83
  84 item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
  85     item *it;
  86     unsigned int oldbucket;
  87
  88     if (expanding &&
  89         (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
  90     {
  91         it = old_hashtable[oldbucket];
  92     } else {
  93         it = primary_hashtable[hv & hashmask(hashpower)];
  94     }
  95
  96     item *ret = NULL;
  97     int depth = 0;
  98     while (it) {
  99         if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
 100             ret = it;
 101             break;
 102         }
 103         it = it->h_next;
 104         ++depth;
 105     }
 106     MEMCACHED_ASSOC_FIND(key, nkey, depth);
 107     return ret;
 108 }
 109
 110 /* returns the address of the item pointer before the key.  if *item == 0,
 111    the item wasn't found */
 112
 113 static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
 114     item **pos;
 115     unsigned int oldbucket;
 116
 117     if (expanding &&
 118         (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
 119     {
 120         pos = &old_hashtable[oldbucket];
 121     } else {
 122         pos = &primary_hashtable[hv & hashmask(hashpower)];
 123     }
 124
 125     while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
 126         pos = &(*pos)->h_next;
 127     }
 128     return pos;
 129 }
 130
 131 /* grows the hashtable to the next power of 2. */
 132 static void assoc_expand(void) {
 133     old_hashtable = primary_hashtable;
 134
 135     primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
 136     if (primary_hashtable) {
 137         if (settings.verbose > 1)
 138             fprintf(stderr, "Hash table expansion starting\n");
 139         hashpower++;
 140         expanding = true;
 141         expand_bucket = 0;
 142         STATS_LOCK();
 143         stats.hash_power_level = hashpower;
 144         stats.hash_bytes += hashsize(hashpower) * sizeof(void *);
 145         stats.hash_is_expanding = 1;
 146         STATS_UNLOCK();
 147         pthread_cond_signal(&maintenance_cond);
 148     } else {
 149         primary_hashtable = old_hashtable;
 150         /* Bad news, but we can keep running. */
 151     }
 152 }
 153
 154 /* Note: this isn't an assoc_update.  The key must not already exist to call this */
 155 int assoc_insert(item *it, const uint32_t hv) {
 156     unsigned int oldbucket;
 157
 158 //    assert(assoc_find(ITEM_key(it), it->nkey) == 0);  /* shouldn't have duplicately named things defined */
 159
 160     if (expanding &&
 161         (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
 162     {
 163         it->h_next = old_hashtable[oldbucket];
 164         old_hashtable[oldbucket] = it;
 165     } else {
 166         it->h_next = primary_hashtable[hv & hashmask(hashpower)];
 167         primary_hashtable[hv & hashmask(hashpower)] = it;
 168     }
 169
 170     hash_items++;
 171     if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
 172         assoc_expand();
 173     }
 174
 175     MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items);
 176     return 1;
 177 }
 178
 179 void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
 180     item **before = _hashitem_before(key, nkey, hv);
 181
 182     if (*before) {
 183         item *nxt;
 184         hash_items--;
 185         /* The DTrace probe cannot be triggered as the last instruction
 186          * due to possible tail-optimization by the compiler
 187          */
 188         MEMCACHED_ASSOC_DELETE(key, nkey, hash_items);
 189         nxt = (*before)->h_next;
 190         (*before)->h_next = 0;   /* probably pointless, but whatever. */
 191         *before = nxt;
 192         return;
 193     }
 194     /* Note:  we never actually get here.  the callers don't delete things
 195        they can't find. */
 196     assert(*before != 0);
 197 }
 198
 199
 200 static volatile int do_run_maintenance_thread = 1;
 201
 202 #define DEFAULT_HASH_BULK_MOVE 1
 203 int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
 204
 205 static void *assoc_maintenance_thread(void *arg) {
 206
 207     while (do_run_maintenance_thread) {
 208         int ii = 0;
 209
 210         /* Lock the cache, and bulk move multiple buckets to the new
 211          * hash table. */
 212         mutex_lock(&cache_lock);
 213
 214         for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
 215             item *it, *next;
 216             int bucket;
 217
 218             for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
 219                 next = it->h_next;
 220
 221                 bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower);
 222                 it->h_next = primary_hashtable[bucket];
 223                 primary_hashtable[bucket] = it;
 224             }
 225
 226             old_hashtable[expand_bucket] = NULL;
 227
 228             expand_bucket++;
 229             if (expand_bucket == hashsize(hashpower - 1)) {
 230                 expanding = false;
 231                 free(old_hashtable);
 232                 STATS_LOCK();
 233                 stats.hash_bytes -= hashsize(hashpower - 1) * sizeof(void *);
 234                 stats.hash_is_expanding = 0;
 235                 STATS_UNLOCK();
 236                 if (settings.verbose > 1)
 237                     fprintf(stderr, "Hash table expansion done\n");
 238             }
 239         }
 240
 241         if (!expanding) {
 242             /* We are done expanding.. just wait for next invocation */
 243             pthread_cond_wait(&maintenance_cond, &cache_lock);
 244         }
 245
 246         pthread_mutex_unlock(&cache_lock);
 247     }
 248     return NULL;
 249 }
 250
 251 static pthread_t maintenance_tid;
 252
 253 int start_assoc_maintenance_thread() {
 254     int ret;
 255     char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
 256     if (env != NULL) {
 257         hash_bulk_move = atoi(env);
 258         if (hash_bulk_move == 0) {
 259             hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
 260         }
 261     }
 262     if ((ret = pthread_create(&maintenance_tid, NULL,
 263                               assoc_maintenance_thread, NULL)) != 0) {
 264         fprintf(stderr, "Can't create thread: %s\n", strerror(ret));
 265         return -1;
 266     }
 267     return 0;
 268 }
 269
 270 void stop_assoc_maintenance_thread() {
 271     mutex_lock(&cache_lock);
 272     do_run_maintenance_thread = 0;
 273     pthread_cond_signal(&maintenance_cond);
 274     pthread_mutex_unlock(&cache_lock);
 275
 276     /* Wait for the maintenance thread to stop */
 277     pthread_join(maintenance_tid, NULL);
 278 }
 279
 280