"Fossies" - the Fresh Open Source Software Archive

Member "memcached-1.6.9/assoc.c" (21 Nov 2020, 11468 Bytes) of package /linux/www/memcached-1.6.9.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "assoc.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 1.6.8_vs_1.6.9.

    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/resource.h>
   18 #include <signal.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 static pthread_mutex_t maintenance_lock = PTHREAD_MUTEX_INITIALIZER;
   30 
   31 typedef  uint32_t  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 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 /* Flag: Are we in the middle of expanding now? */
   50 static bool expanding = false;
   51 
   52 /*
   53  * During expansion we migrate values with bucket granularity; this is how
   54  * far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1.
   55  */
   56 static unsigned int expand_bucket = 0;
   57 
   58 void assoc_init(const int hashtable_init) {
   59     if (hashtable_init) {
   60         hashpower = hashtable_init;
   61     }
   62     primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
   63     if (! primary_hashtable) {
   64         fprintf(stderr, "Failed to init hashtable.\n");
   65         exit(EXIT_FAILURE);
   66     }
   67     STATS_LOCK();
   68     stats_state.hash_power_level = hashpower;
   69     stats_state.hash_bytes = hashsize(hashpower) * sizeof(void *);
   70     STATS_UNLOCK();
   71 }
   72 
   73 item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
   74     item *it;
   75     unsigned int oldbucket;
   76 
   77     if (expanding &&
   78         (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
   79     {
   80         it = old_hashtable[oldbucket];
   81     } else {
   82         it = primary_hashtable[hv & hashmask(hashpower)];
   83     }
   84 
   85     item *ret = NULL;
   86     int depth = 0;
   87     while (it) {
   88         if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
   89             ret = it;
   90             break;
   91         }
   92         it = it->h_next;
   93         ++depth;
   94     }
   95     MEMCACHED_ASSOC_FIND(key, nkey, depth);
   96     return ret;
   97 }
   98 
   99 /* returns the address of the item pointer before the key.  if *item == 0,
  100    the item wasn't found */
  101 
  102 static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
  103     item **pos;
  104     unsigned int oldbucket;
  105 
  106     if (expanding &&
  107         (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
  108     {
  109         pos = &old_hashtable[oldbucket];
  110     } else {
  111         pos = &primary_hashtable[hv & hashmask(hashpower)];
  112     }
  113 
  114     while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
  115         pos = &(*pos)->h_next;
  116     }
  117     return pos;
  118 }
  119 
  120 /* grows the hashtable to the next power of 2. */
  121 static void assoc_expand(void) {
  122     old_hashtable = primary_hashtable;
  123 
  124     primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
  125     if (primary_hashtable) {
  126         if (settings.verbose > 1)
  127             fprintf(stderr, "Hash table expansion starting\n");
  128         hashpower++;
  129         expanding = true;
  130         expand_bucket = 0;
  131         STATS_LOCK();
  132         stats_state.hash_power_level = hashpower;
  133         stats_state.hash_bytes += hashsize(hashpower) * sizeof(void *);
  134         stats_state.hash_is_expanding = true;
  135         STATS_UNLOCK();
  136     } else {
  137         primary_hashtable = old_hashtable;
  138         /* Bad news, but we can keep running. */
  139     }
  140 }
  141 
  142 void assoc_start_expand(uint64_t curr_items) {
  143     if (pthread_mutex_trylock(&maintenance_lock) == 0) {
  144         if (curr_items > (hashsize(hashpower) * 3) / 2 && hashpower < HASHPOWER_MAX) {
  145             pthread_cond_signal(&maintenance_cond);
  146         }
  147         pthread_mutex_unlock(&maintenance_lock);
  148     }
  149 }
  150 
  151 /* Note: this isn't an assoc_update.  The key must not already exist to call this */
  152 int assoc_insert(item *it, const uint32_t hv) {
  153     unsigned int oldbucket;
  154 
  155 //    assert(assoc_find(ITEM_key(it), it->nkey) == 0);  /* shouldn't have duplicately named things defined */
  156 
  157     if (expanding &&
  158         (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
  159     {
  160         it->h_next = old_hashtable[oldbucket];
  161         old_hashtable[oldbucket] = it;
  162     } else {
  163         it->h_next = primary_hashtable[hv & hashmask(hashpower)];
  164         primary_hashtable[hv & hashmask(hashpower)] = it;
  165     }
  166 
  167     MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey);
  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         /* The DTrace probe cannot be triggered as the last instruction
  177          * due to possible tail-optimization by the compiler
  178          */
  179         MEMCACHED_ASSOC_DELETE(key, nkey);
  180         nxt = (*before)->h_next;
  181         (*before)->h_next = 0;   /* probably pointless, but whatever. */
  182         *before = nxt;
  183         return;
  184     }
  185     /* Note:  we never actually get here.  the callers don't delete things
  186        they can't find. */
  187     assert(*before != 0);
  188 }
  189 
  190 
  191 static volatile int do_run_maintenance_thread = 1;
  192 
  193 #define DEFAULT_HASH_BULK_MOVE 1
  194 int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
  195 
  196 static void *assoc_maintenance_thread(void *arg) {
  197 
  198     mutex_lock(&maintenance_lock);
  199     while (do_run_maintenance_thread) {
  200         int ii = 0;
  201 
  202         /* There is only one expansion thread, so no need to global lock. */
  203         for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
  204             item *it, *next;
  205             unsigned int bucket;
  206             void *item_lock = NULL;
  207 
  208             /* bucket = hv & hashmask(hashpower) =>the bucket of hash table
  209              * is the lowest N bits of the hv, and the bucket of item_locks is
  210              *  also the lowest M bits of hv, and N is greater than M.
  211              *  So we can process expanding with only one item_lock. cool! */
  212             if ((item_lock = item_trylock(expand_bucket))) {
  213                     for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
  214                         next = it->h_next;
  215                         bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);
  216                         it->h_next = primary_hashtable[bucket];
  217                         primary_hashtable[bucket] = it;
  218                     }
  219 
  220                     old_hashtable[expand_bucket] = NULL;
  221 
  222                     expand_bucket++;
  223                     if (expand_bucket == hashsize(hashpower - 1)) {
  224                         expanding = false;
  225                         free(old_hashtable);
  226                         STATS_LOCK();
  227                         stats_state.hash_bytes -= hashsize(hashpower - 1) * sizeof(void *);
  228                         stats_state.hash_is_expanding = false;
  229                         STATS_UNLOCK();
  230                         if (settings.verbose > 1)
  231                             fprintf(stderr, "Hash table expansion done\n");
  232                     }
  233 
  234             } else {
  235                 usleep(10*1000);
  236             }
  237 
  238             if (item_lock) {
  239                 item_trylock_unlock(item_lock);
  240                 item_lock = NULL;
  241             }
  242         }
  243 
  244         if (!expanding) {
  245             /* We are done expanding.. just wait for next invocation */
  246             pthread_cond_wait(&maintenance_cond, &maintenance_lock);
  247             /* assoc_expand() swaps out the hash table entirely, so we need
  248              * all threads to not hold any references related to the hash
  249              * table while this happens.
  250              * This is instead of a more complex, possibly slower algorithm to
  251              * allow dynamic hash table expansion without causing significant
  252              * wait times.
  253              */
  254             if (do_run_maintenance_thread) {
  255                 pause_threads(PAUSE_ALL_THREADS);
  256                 assoc_expand();
  257                 pause_threads(RESUME_ALL_THREADS);
  258             }
  259         }
  260     }
  261     mutex_unlock(&maintenance_lock);
  262     return NULL;
  263 }
  264 
  265 static pthread_t maintenance_tid;
  266 
  267 int start_assoc_maintenance_thread() {
  268     int ret;
  269     char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
  270     if (env != NULL) {
  271         hash_bulk_move = atoi(env);
  272         if (hash_bulk_move == 0) {
  273             hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
  274         }
  275     }
  276 
  277     if ((ret = pthread_create(&maintenance_tid, NULL,
  278                               assoc_maintenance_thread, NULL)) != 0) {
  279         fprintf(stderr, "Can't create thread: %s\n", strerror(ret));
  280         return -1;
  281     }
  282     return 0;
  283 }
  284 
  285 void stop_assoc_maintenance_thread() {
  286     mutex_lock(&maintenance_lock);
  287     do_run_maintenance_thread = 0;
  288     pthread_cond_signal(&maintenance_cond);
  289     mutex_unlock(&maintenance_lock);
  290 
  291     /* Wait for the maintenance thread to stop */
  292     pthread_join(maintenance_tid, NULL);
  293 }
  294 
  295 struct assoc_iterator {
  296     unsigned int bucket;
  297     bool bucket_locked;
  298     item *it;
  299     item *next;
  300 };
  301 
  302 void *assoc_get_iterator(void) {
  303     struct assoc_iterator *iter = calloc(1, sizeof(struct assoc_iterator));
  304     if (iter == NULL) {
  305         return NULL;
  306     }
  307     // this will hang the caller while a hash table expansion is running.
  308     mutex_lock(&maintenance_lock);
  309     return iter;
  310 }
  311 
  312 bool assoc_iterate(void *iterp, item **it) {
  313     struct assoc_iterator *iter = (struct assoc_iterator *) iterp;
  314     *it = NULL;
  315     // - if locked bucket and next, update next and return
  316     if (iter->bucket_locked) {
  317         if (iter->next != NULL) {
  318             iter->it = iter->next;
  319             iter->next = iter->it->h_next;
  320             *it = iter->it;
  321         } else {
  322             // unlock previous bucket, if any
  323             item_unlock(iter->bucket);
  324             // iterate the bucket post since it starts at 0.
  325             iter->bucket++;
  326             iter->bucket_locked = false;
  327             *it = NULL;
  328         }
  329         return true;
  330     }
  331 
  332     // - loop until we hit the end or find something.
  333     if (iter->bucket != hashsize(hashpower)) {
  334         // - lock next bucket
  335         item_lock(iter->bucket);
  336         iter->bucket_locked = true;
  337         // - only check the primary hash table since expand is blocked.
  338         iter->it = primary_hashtable[iter->bucket];
  339         if (iter->it != NULL) {
  340             // - set it, next and return
  341             iter->next = iter->it->h_next;
  342             *it = iter->it;
  343         } else {
  344             // - nothing found in this bucket, try next.
  345             item_unlock(iter->bucket);
  346             iter->bucket_locked = false;
  347             iter->bucket++;
  348         }
  349     } else {
  350         return false;
  351     }
  352 
  353     return true;
  354 }
  355 
  356 void assoc_iterate_final(void *iterp) {
  357     struct assoc_iterator *iter = (struct assoc_iterator *) iterp;
  358     if (iter->bucket_locked) {
  359         item_unlock(iter->bucket);
  360     }
  361     mutex_unlock(&maintenance_lock);
  362     free(iter);
  363 }