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 <assert.h>
21 #include "log.h"
22 
23 static cb_cond_t maintenance_cond;
24 
25 
26 typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
27 typedef  unsigned       char ub1;   /* unsigned 1-byte quantities */
28 
29 /* how many powers of 2's worth of buckets we use */
30 static 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. */
36 static 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  */
42 static item** old_hashtable = 0;
43 
44 /* Number of items in the hash table. */
45 static unsigned int hash_items = 0;
46 
47 /* Flag: Are we in the middle of expanding now? */
48 static 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  */
54 static unsigned int expand_bucket = 0;
55 
assoc_init(void)56 void 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 
assoc_find(const char *key, const size_t nkey)65 item *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 
_hashitem_before(const char *key, const size_t nkey)95 static 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. */
assoc_expand(void)115 static 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 */
assoc_insert(item *it)133 int assoc_insert(item *it) {
134     uint32_t hv;
135     unsigned int oldbucket;
136 
137     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 
assoc_delete(const char *key, const size_t nkey)159 void 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     assert(*before != 0);
177 }
178 
179 
180 static volatile int do_run_maintenance_thread = 1;
181 
182 #define DEFAULT_HASH_BULK_MOVE 1
183 int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
184 
assoc_maintenance_thread(void *arg)185 static 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 
227 static cb_thread_t maintenance_tid;
228 
start_assoc_maintenance_threadnull229 int 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 
stop_assoc_maintenance_threadnull246 void 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