--- /dev/null
+/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/*
+ * Hash table
+ *
+ * The hash function used here is by Bob Jenkins, 1996:
+ * <http://burtleburtle.net/bob/hash/doobs.html>
+ * "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net.
+ * You may use this code any way you wish, private, educational,
+ * or commercial. It's free."
+ *
+ * The rest of the file is licensed under the BSD license. See LICENSE.
+ */
+
+#include "memcached.h"
+
+#include <sys/stat.h>
+#include <sys/socket.h>
+#include <sys/signal.h>
+#include <sys/resource.h>
+#include <fcntl.h>
+#include <netinet/in.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#include <pthread.h>
+
+static pthread_cond_t maintenance_cond = PTHREAD_COND_INITIALIZER;
+
+#ifndef __INTEL_COMPILER
+#pragma GCC diagnostic ignored "-Wstrict-aliasing"
+#endif
+
+#ifndef __INTEL_COMPILER
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+typedef unsigned long int ub4; /* unsigned 4-byte quantities */
+typedef unsigned char ub1; /* unsigned 1-byte quantities */
+
+/* how many powers of 2's worth of buckets we use */
+static unsigned int hashpower = HASHPOWER_DEFAULT;
+
+#define hashsize(n) ((ub4)1<<(n))
+#define hashmask(n) (hashsize(n)-1)
+
+/* Main hash table. This is where we look except during expansion. */
+static item** primary_hashtable = 0;
+
+/*
+ * Previous hash table. During expansion, we look here for keys that haven't
+ * been moved over to the primary yet.
+ */
+static item** old_hashtable = 0;
+
+/* Number of items in the hash table. */
+static unsigned int hash_items = 0;
+
+/* Flag: Are we in the middle of expanding now? */
+static bool expanding = false;
+
+/*
+ * During expansion we migrate values with bucket granularity; this is how
+ * far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1.
+ */
+static unsigned int expand_bucket = 0;
+
+void assoc_init(const int hashtable_init) {
+ if (hashtable_init) {
+ hashpower = hashtable_init;
+ }
+ primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
+ if (! primary_hashtable) {
+ fprintf(stderr, "Failed to init hashtable.\n");
+ exit(EXIT_FAILURE);
+ }
+ STATS_LOCK();
+ stats.hash_power_level = hashpower;
+ stats.hash_bytes = hashsize(hashpower) * sizeof(void *);
+ STATS_UNLOCK();
+}
+
+item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
+ item *it;
+ unsigned int oldbucket;
+
+ if (expanding &&
+ (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
+ {
+ it = old_hashtable[oldbucket];
+ } else {
+ it = primary_hashtable[hv & hashmask(hashpower)];
+ }
+
+ item *ret = NULL;
+ int depth = 0;
+ while (it) {
+ if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
+ ret = it;
+ break;
+ }
+ it = it->h_next;
+ ++depth;
+ }
+ MEMCACHED_ASSOC_FIND(key, nkey, depth);
+ return ret;
+}
+
+/* returns the address of the item pointer before the key. if *item == 0,
+ the item wasn't found */
+
+static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
+ item **pos;
+ unsigned int oldbucket;
+
+ if (expanding &&
+ (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
+ {
+ pos = &old_hashtable[oldbucket];
+ } else {
+ pos = &primary_hashtable[hv & hashmask(hashpower)];
+ }
+
+ while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
+ pos = &(*pos)->h_next;
+ }
+ return pos;
+}
+
+/* grows the hashtable to the next power of 2. */
+static void assoc_expand(void) {
+ old_hashtable = primary_hashtable;
+
+ primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
+ if (primary_hashtable) {
+ if (settings.verbose > 1)
+ fprintf(stderr, "Hash table expansion starting\n");
+ hashpower++;
+ expanding = true;
+ expand_bucket = 0;
+ STATS_LOCK();
+ stats.hash_power_level = hashpower;
+ stats.hash_bytes += hashsize(hashpower) * sizeof(void *);
+ stats.hash_is_expanding = 1;
+ STATS_UNLOCK();
+ pthread_cond_signal(&maintenance_cond);
+ } else {
+ primary_hashtable = old_hashtable;
+ /* Bad news, but we can keep running. */
+ }
+}
+
+/* Note: this isn't an assoc_update. The key must not already exist to call this */
+int assoc_insert(item *it, const uint32_t hv) {
+ unsigned int oldbucket;
+
+// assert(assoc_find(ITEM_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */
+
+ if (expanding &&
+ (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
+ {
+ it->h_next = old_hashtable[oldbucket];
+ old_hashtable[oldbucket] = it;
+ } else {
+ it->h_next = primary_hashtable[hv & hashmask(hashpower)];
+ primary_hashtable[hv & hashmask(hashpower)] = it;
+ }
+
+ hash_items++;
+ if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
+ assoc_expand();
+ }
+
+ MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items);
+ return 1;
+}
+
+void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
+ item **before = _hashitem_before(key, nkey, hv);
+
+ if (*before) {
+ item *nxt;
+ hash_items--;
+ /* The DTrace probe cannot be triggered as the last instruction
+ * due to possible tail-optimization by the compiler
+ */
+ MEMCACHED_ASSOC_DELETE(key, nkey, hash_items);
+ nxt = (*before)->h_next;
+ (*before)->h_next = 0; /* probably pointless, but whatever. */
+ *before = nxt;
+ return;
+ }
+ /* Note: we never actually get here. the callers don't delete things
+ they can't find. */
+ assert(*before != 0);
+}
+
+
+static volatile int do_run_maintenance_thread = 1;
+
+#define DEFAULT_HASH_BULK_MOVE 1
+int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
+
+static void *assoc_maintenance_thread(void *arg) {
+
+ while (do_run_maintenance_thread) {
+ int ii = 0;
+
+ /* Lock the cache, and bulk move multiple buckets to the new
+ * hash table. */
+ mutex_lock(&cache_lock);
+
+ for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
+ item *it, *next;
+ int bucket;
+
+ for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
+ next = it->h_next;
+
+ bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower);
+ it->h_next = primary_hashtable[bucket];
+ primary_hashtable[bucket] = it;
+ }
+
+ old_hashtable[expand_bucket] = NULL;
+
+ expand_bucket++;
+ if (expand_bucket == hashsize(hashpower - 1)) {
+ expanding = false;
+ free(old_hashtable);
+ STATS_LOCK();
+ stats.hash_bytes -= hashsize(hashpower - 1) * sizeof(void *);
+ stats.hash_is_expanding = 0;
+ STATS_UNLOCK();
+ if (settings.verbose > 1)
+ fprintf(stderr, "Hash table expansion done\n");
+ }
+ }
+
+ if (!expanding) {
+ /* We are done expanding.. just wait for next invocation */
+ pthread_cond_wait(&maintenance_cond, &cache_lock);
+ }
+
+ pthread_mutex_unlock(&cache_lock);
+ }
+ return NULL;
+}
+
+static pthread_t maintenance_tid;
+
+int start_assoc_maintenance_thread() {
+ int ret;
+ char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
+ if (env != NULL) {
+ hash_bulk_move = atoi(env);
+ if (hash_bulk_move == 0) {
+ hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
+ }
+ }
+ if ((ret = pthread_create(&maintenance_tid, NULL,
+ assoc_maintenance_thread, NULL)) != 0) {
+ fprintf(stderr, "Can't create thread: %s\n", strerror(ret));
+ return -1;
+ }
+ return 0;
+}
+
+void stop_assoc_maintenance_thread() {
+ mutex_lock(&cache_lock);
+ do_run_maintenance_thread = 0;
+ pthread_cond_signal(&maintenance_cond);
+ pthread_mutex_unlock(&cache_lock);
+
+ /* Wait for the maintenance thread to stop */
+ pthread_join(maintenance_tid, NULL);
+}
+
+
projects / awesomized / libmemcached / blobdiff