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/signal.h> |
18 |
#include <sys/resource.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 |
|
30 |
|
31 |
typedef unsigned long int 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 |
static unsigned int hashpower = 16; |
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 |
/* Number of items in the hash table. */ |
50 |
static unsigned int hash_items = 0; |
51 |
|
52 |
/* Flag: Are we in the middle of expanding now? */ |
53 |
static bool expanding = false; |
54 |
|
55 |
/* |
56 |
* During expansion we migrate values with bucket granularity; this is how |
57 |
* far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1. |
58 |
*/ |
59 |
static unsigned int expand_bucket = 0; |
60 |
|
61 |
void assoc_init(void) { |
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 |
} |
68 |
|
69 |
item *assoc_find(const char *key, const size_t nkey) { |
70 |
uint32_t hv = hash(key, nkey, 0); |
71 |
item *it; |
72 |
unsigned int 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) { |
100 |
uint32_t hv = hash(key, nkey, 0); |
101 |
item **pos; |
102 |
unsigned int oldbucket; |
103 |
|
104 |
if (expanding && |
105 |
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) |
106 |
{ |
107 |
pos = &old_hashtable[oldbucket]; |
108 |
} else { |
109 |
pos = &primary_hashtable[hv & hashmask(hashpower)]; |
110 |
} |
111 |
|
112 |
while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) { |
113 |
pos = &(*pos)->h_next; |
114 |
} |
115 |
return pos; |
116 |
} |
117 |
|
118 |
/* grows the hashtable to the next power of 2. */ |
119 |
static void assoc_expand(void) { |
120 |
old_hashtable = primary_hashtable; |
121 |
|
122 |
primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *)); |
123 |
if (primary_hashtable) { |
124 |
if (settings.verbose > 1) |
125 |
fprintf(stderr, "Hash table expansion starting\n"); |
126 |
hashpower++; |
127 |
expanding = true; |
128 |
expand_bucket = 0; |
129 |
pthread_cond_signal(&maintenance_cond); |
130 |
} else { |
131 |
primary_hashtable = old_hashtable; |
132 |
/* Bad news, but we can keep running. */ |
133 |
} |
134 |
} |
135 |
|
136 |
/* Note: this isn't an assoc_update. The key must not already exist to call this */ |
137 |
int assoc_insert(item *it) { |
138 |
uint32_t hv; |
139 |
unsigned int oldbucket; |
140 |
|
141 |
assert(assoc_find(ITEM_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */ |
142 |
|
143 |
hv = hash(ITEM_key(it), it->nkey, 0); |
144 |
if (expanding && |
145 |
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) |
146 |
{ |
147 |
it->h_next = old_hashtable[oldbucket]; |
148 |
old_hashtable[oldbucket] = it; |
149 |
} else { |
150 |
it->h_next = primary_hashtable[hv & hashmask(hashpower)]; |
151 |
primary_hashtable[hv & hashmask(hashpower)] = it; |
152 |
} |
153 |
|
154 |
hash_items++; |
155 |
if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) { |
156 |
assoc_expand(); |
157 |
} |
158 |
|
159 |
MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items); |
160 |
return 1; |
161 |
} |
162 |
|
163 |
void assoc_delete(const char *key, const size_t nkey) { |
164 |
item **before = _hashitem_before(key, nkey); |
165 |
|
166 |
if (*before) { |
167 |
item *nxt; |
168 |
hash_items--; |
169 |
/* The DTrace probe cannot be triggered as the last instruction |
170 |
* due to possible tail-optimization by the compiler |
171 |
*/ |
172 |
MEMCACHED_ASSOC_DELETE(key, nkey, hash_items); |
173 |
nxt = (*before)->h_next; |
174 |
(*before)->h_next = 0; /* probably pointless, but whatever. */ |
175 |
*before = nxt; |
176 |
return; |
177 |
} |
178 |
/* Note: we never actually get here. the callers don't delete things |
179 |
they can't find. */ |
180 |
assert(*before != 0); |
181 |
} |
182 |
|
183 |
|
184 |
static volatile int do_run_maintenance_thread = 1; |
185 |
|
186 |
#define DEFAULT_HASH_BULK_MOVE 1 |
187 |
int hash_bulk_move = DEFAULT_HASH_BULK_MOVE; |
188 |
|
189 |
static void *assoc_maintenance_thread(void *arg) { |
190 |
|
191 |
while (do_run_maintenance_thread) { |
192 |
int ii = 0; |
193 |
|
194 |
/* Lock the cache, and bulk move multiple buckets to the new |
195 |
* hash table. */ |
196 |
pthread_mutex_lock(&cache_lock); |
197 |
|
198 |
for (ii = 0; ii < hash_bulk_move && expanding; ++ii) { |
199 |
item *it, *next; |
200 |
int bucket; |
201 |
|
202 |
for (it = old_hashtable[expand_bucket]; NULL != it; it = next) { |
203 |
next = it->h_next; |
204 |
|
205 |
bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower); |
206 |
it->h_next = primary_hashtable[bucket]; |
207 |
primary_hashtable[bucket] = it; |
208 |
} |
209 |
|
210 |
old_hashtable[expand_bucket] = NULL; |
211 |
|
212 |
expand_bucket++; |
213 |
if (expand_bucket == hashsize(hashpower - 1)) { |
214 |
expanding = false; |
215 |
free(old_hashtable); |
216 |
if (settings.verbose > 1) |
217 |
fprintf(stderr, "Hash table expansion done\n"); |
218 |
} |
219 |
} |
220 |
|
221 |
if (!expanding) { |
222 |
/* We are done expanding.. just wait for next invocation */ |
223 |
pthread_cond_wait(&maintenance_cond, &cache_lock); |
224 |
} |
225 |
|
226 |
pthread_mutex_unlock(&cache_lock); |
227 |
} |
228 |
return NULL; |
229 |
} |
230 |
|
231 |
static pthread_t maintenance_tid; |
232 |
|
233 |
int start_assoc_maintenance_thread() { |
234 |
int ret; |
235 |
char *env = getenv("MEMCACHED_HASH_BULK_MOVE"); |
236 |
if (env != NULL) { |
237 |
hash_bulk_move = atoi(env); |
238 |
if (hash_bulk_move == 0) { |
239 |
hash_bulk_move = DEFAULT_HASH_BULK_MOVE; |
240 |
} |
241 |
} |
242 |
if ((ret = pthread_create(&maintenance_tid, NULL, |
243 |
assoc_maintenance_thread, NULL)) != 0) { |
244 |
fprintf(stderr, "Can't create thread: %s\n", strerror(ret)); |
245 |
return -1; |
246 |
} |
247 |
return 0; |
248 |
} |
249 |
|
250 |
void stop_assoc_maintenance_thread() { |
251 |
pthread_mutex_lock(&cache_lock); |
252 |
do_run_maintenance_thread = 0; |
253 |
pthread_cond_signal(&maintenance_cond); |
254 |
pthread_mutex_unlock(&cache_lock); |
255 |
|
256 |
/* Wait for the maintenance thread to stop */ |
257 |
pthread_join(maintenance_tid, NULL); |
258 |
} |
259 |
|
260 |
|