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