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