1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
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."
11 * The rest of the file is licensed under the BSD license. See LICENSE.
14 #include "memcached.h"
17 #include <sys/socket.h>
18 #include <sys/signal.h>
19 #include <sys/resource.h>
21 #include <netinet/in.h>
29 static pthread_cond_t maintenance_cond
= PTHREAD_COND_INITIALIZER
;
31 #ifndef __INTEL_COMPILER
32 #pragma GCC diagnostic ignored "-Wstrict-aliasing"
35 #ifndef __INTEL_COMPILER
36 #pragma GCC diagnostic ignored "-Wunused-parameter"
39 typedef unsigned long int ub4
; /* unsigned 4-byte quantities */
40 typedef unsigned char ub1
; /* unsigned 1-byte quantities */
42 /* how many powers of 2's worth of buckets we use */
43 static unsigned int hashpower
= HASHPOWER_DEFAULT
;
45 #define hashsize(n) ((ub4)1<<(n))
46 #define hashmask(n) (hashsize(n)-1)
48 /* Main hash table. This is where we look except during expansion. */
49 static item
** primary_hashtable
= 0;
52 * Previous hash table. During expansion, we look here for keys that haven't
53 * been moved over to the primary yet.
55 static item
** old_hashtable
= 0;
57 /* Number of items in the hash table. */
58 static unsigned int hash_items
= 0;
60 /* Flag: Are we in the middle of expanding now? */
61 static bool expanding
= false;
64 * During expansion we migrate values with bucket granularity; this is how
65 * far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1.
67 static unsigned int expand_bucket
= 0;
69 void assoc_init(const int hashtable_init
) {
71 hashpower
= hashtable_init
;
73 primary_hashtable
= calloc(hashsize(hashpower
), sizeof(void *));
74 if (! primary_hashtable
) {
75 fprintf(stderr
, "Failed to init hashtable.\n");
79 stats
.hash_power_level
= hashpower
;
80 stats
.hash_bytes
= hashsize(hashpower
) * sizeof(void *);
84 item
*assoc_find(const char *key
, const size_t nkey
, const uint32_t hv
) {
86 unsigned int oldbucket
;
89 (oldbucket
= (hv
& hashmask(hashpower
- 1))) >= expand_bucket
)
91 it
= old_hashtable
[oldbucket
];
93 it
= primary_hashtable
[hv
& hashmask(hashpower
)];
99 if ((nkey
== it
->nkey
) && (memcmp(key
, ITEM_key(it
), nkey
) == 0)) {
106 MEMCACHED_ASSOC_FIND(key
, nkey
, depth
);
110 /* returns the address of the item pointer before the key. if *item == 0,
111 the item wasn't found */
113 static item
** _hashitem_before (const char *key
, const size_t nkey
, const uint32_t hv
) {
115 unsigned int oldbucket
;
118 (oldbucket
= (hv
& hashmask(hashpower
- 1))) >= expand_bucket
)
120 pos
= &old_hashtable
[oldbucket
];
122 pos
= &primary_hashtable
[hv
& hashmask(hashpower
)];
125 while (*pos
&& ((nkey
!= (*pos
)->nkey
) || memcmp(key
, ITEM_key(*pos
), nkey
))) {
126 pos
= &(*pos
)->h_next
;
131 /* grows the hashtable to the next power of 2. */
132 static void assoc_expand(void) {
133 old_hashtable
= primary_hashtable
;
135 primary_hashtable
= calloc(hashsize(hashpower
+ 1), sizeof(void *));
136 if (primary_hashtable
) {
137 if (settings
.verbose
> 1)
138 fprintf(stderr
, "Hash table expansion starting\n");
143 stats
.hash_power_level
= hashpower
;
144 stats
.hash_bytes
+= hashsize(hashpower
) * sizeof(void *);
145 stats
.hash_is_expanding
= 1;
147 pthread_cond_signal(&maintenance_cond
);
149 primary_hashtable
= old_hashtable
;
150 /* Bad news, but we can keep running. */
154 /* Note: this isn't an assoc_update. The key must not already exist to call this */
155 int assoc_insert(item
*it
, const uint32_t hv
) {
156 unsigned int oldbucket
;
158 // assert(assoc_find(ITEM_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */
161 (oldbucket
= (hv
& hashmask(hashpower
- 1))) >= expand_bucket
)
163 it
->h_next
= old_hashtable
[oldbucket
];
164 old_hashtable
[oldbucket
] = it
;
166 it
->h_next
= primary_hashtable
[hv
& hashmask(hashpower
)];
167 primary_hashtable
[hv
& hashmask(hashpower
)] = it
;
171 if (! expanding
&& hash_items
> (hashsize(hashpower
) * 3) / 2) {
175 MEMCACHED_ASSOC_INSERT(ITEM_key(it
), it
->nkey
, hash_items
);
179 void assoc_delete(const char *key
, const size_t nkey
, const uint32_t hv
) {
180 item
**before
= _hashitem_before(key
, nkey
, hv
);
185 /* The DTrace probe cannot be triggered as the last instruction
186 * due to possible tail-optimization by the compiler
188 MEMCACHED_ASSOC_DELETE(key
, nkey
, hash_items
);
189 nxt
= (*before
)->h_next
;
190 (*before
)->h_next
= 0; /* probably pointless, but whatever. */
194 /* Note: we never actually get here. the callers don't delete things
196 assert(*before
!= 0);
200 static volatile int do_run_maintenance_thread
= 1;
202 #define DEFAULT_HASH_BULK_MOVE 1
203 int hash_bulk_move
= DEFAULT_HASH_BULK_MOVE
;
205 static void *assoc_maintenance_thread(void *arg
) {
207 while (do_run_maintenance_thread
) {
210 /* Lock the cache, and bulk move multiple buckets to the new
212 mutex_lock(&cache_lock
);
214 for (ii
= 0; ii
< hash_bulk_move
&& expanding
; ++ii
) {
218 for (it
= old_hashtable
[expand_bucket
]; NULL
!= it
; it
= next
) {
221 bucket
= hash(ITEM_key(it
), it
->nkey
, 0) & hashmask(hashpower
);
222 it
->h_next
= primary_hashtable
[bucket
];
223 primary_hashtable
[bucket
] = it
;
226 old_hashtable
[expand_bucket
] = NULL
;
229 if (expand_bucket
== hashsize(hashpower
- 1)) {
233 stats
.hash_bytes
-= hashsize(hashpower
- 1) * sizeof(void *);
234 stats
.hash_is_expanding
= 0;
236 if (settings
.verbose
> 1)
237 fprintf(stderr
, "Hash table expansion done\n");
242 /* We are done expanding.. just wait for next invocation */
243 pthread_cond_wait(&maintenance_cond
, &cache_lock
);
246 pthread_mutex_unlock(&cache_lock
);
251 static pthread_t maintenance_tid
;
253 int start_assoc_maintenance_thread() {
255 char *env
= getenv("MEMCACHED_HASH_BULK_MOVE");
257 hash_bulk_move
= atoi(env
);
258 if (hash_bulk_move
== 0) {
259 hash_bulk_move
= DEFAULT_HASH_BULK_MOVE
;
262 if ((ret
= pthread_create(&maintenance_tid
, NULL
,
263 assoc_maintenance_thread
, NULL
)) != 0) {
264 fprintf(stderr
, "Can't create thread: %s\n", strerror(ret
));
270 void stop_assoc_maintenance_thread() {
271 mutex_lock(&cache_lock
);
272 do_run_maintenance_thread
= 0;
273 pthread_cond_signal(&maintenance_cond
);
274 pthread_mutex_unlock(&cache_lock
);
276 /* Wait for the maintenance thread to stop */
277 pthread_join(maintenance_tid
, NULL
);