"Fossies" - the Fresh Open Source Software Archive

Member "memcached-1.6.15/assoc.c" (21 Feb 2022, 11320 Bytes) of package /linux/www/memcached-1.6.15.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 last Fossies "Diffs" side-by-side code changes report: 1.6.13_vs_1.6.14.

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