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"
16 #include <sys/socket.h>
17 #include <sys/signal.h>
18 #include <sys/resource.h>
20 #include <netinet/in.h>
28 static pthread_cond_t maintenance_cond
= PTHREAD_COND_INITIALIZER
;
31 typedef unsigned long int ub4
; /* unsigned 4-byte quantities */
32 typedef unsigned char ub1
; /* unsigned 1-byte quantities */
34 /* how many powers of 2's worth of buckets we use */
35 static unsigned int hashpower
= HASHPOWER_DEFAULT
;
37 #define hashsize(n) ((ub4)1<<(n))
38 #define hashmask(n) (hashsize(n)-1)
40 /* Main hash table. This is where we look except during expansion. */
41 static item
** primary_hashtable
= 0;
44 * Previous hash table. During expansion, we look here for keys that haven't
45 * been moved over to the primary yet.
47 static item
** old_hashtable
= 0;
49 /* Number of items in the hash table. */
50 static unsigned int hash_items
= 0;
52 /* Flag: Are we in the middle of expanding now? */
53 static bool expanding
= false;
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.
59 static unsigned int expand_bucket
= 0;
61 void assoc_init(const int hashtable_init
) {
63 hashpower
= hashtable_init
;
65 primary_hashtable
= calloc(hashsize(hashpower
), sizeof(void *));
66 if (! primary_hashtable
) {
67 fprintf(stderr
, "Failed to init hashtable.\n");
71 stats
.hash_power_level
= hashpower
;
72 stats
.hash_bytes
= hashsize(hashpower
) * sizeof(void *);
76 item
*assoc_find(const char *key
, const size_t nkey
, const uint32_t hv
) {
78 unsigned int oldbucket
;
81 (oldbucket
= (hv
& hashmask(hashpower
- 1))) >= expand_bucket
)
83 it
= old_hashtable
[oldbucket
];
85 it
= primary_hashtable
[hv
& hashmask(hashpower
)];
91 if ((nkey
== it
->nkey
) && (memcmp(key
, ITEM_key(it
), nkey
) == 0)) {
98 MEMCACHED_ASSOC_FIND(key
, nkey
, depth
);
102 /* returns the address of the item pointer before the key. if *item == 0,
103 the item wasn't found */
105 static item
** _hashitem_before (const char *key
, const size_t nkey
, const uint32_t hv
) {
107 unsigned int oldbucket
;
110 (oldbucket
= (hv
& hashmask(hashpower
- 1))) >= expand_bucket
)
112 pos
= &old_hashtable
[oldbucket
];
114 pos
= &primary_hashtable
[hv
& hashmask(hashpower
)];
117 while (*pos
&& ((nkey
!= (*pos
)->nkey
) || memcmp(key
, ITEM_key(*pos
), nkey
))) {
118 pos
= &(*pos
)->h_next
;
123 /* grows the hashtable to the next power of 2. */
124 static void assoc_expand(void) {
125 old_hashtable
= primary_hashtable
;
127 primary_hashtable
= calloc(hashsize(hashpower
+ 1), sizeof(void *));
128 if (primary_hashtable
) {
129 if (settings
.verbose
> 1)
130 fprintf(stderr
, "Hash table expansion starting\n");
135 stats
.hash_power_level
= hashpower
;
136 stats
.hash_bytes
+= hashsize(hashpower
) * sizeof(void *);
137 stats
.hash_is_expanding
= 1;
139 pthread_cond_signal(&maintenance_cond
);
141 primary_hashtable
= old_hashtable
;
142 /* Bad news, but we can keep running. */
146 /* Note: this isn't an assoc_update. The key must not already exist to call this */
147 int assoc_insert(item
*it
, const uint32_t hv
) {
148 unsigned int oldbucket
;
150 // assert(assoc_find(ITEM_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */
153 (oldbucket
= (hv
& hashmask(hashpower
- 1))) >= expand_bucket
)
155 it
->h_next
= old_hashtable
[oldbucket
];
156 old_hashtable
[oldbucket
] = it
;
158 it
->h_next
= primary_hashtable
[hv
& hashmask(hashpower
)];
159 primary_hashtable
[hv
& hashmask(hashpower
)] = it
;
163 if (! expanding
&& hash_items
> (hashsize(hashpower
) * 3) / 2) {
167 MEMCACHED_ASSOC_INSERT(ITEM_key(it
), it
->nkey
, hash_items
);
171 void assoc_delete(const char *key
, const size_t nkey
, const uint32_t hv
) {
172 item
**before
= _hashitem_before(key
, nkey
, hv
);
177 /* The DTrace probe cannot be triggered as the last instruction
178 * due to possible tail-optimization by the compiler
180 MEMCACHED_ASSOC_DELETE(key
, nkey
, hash_items
);
181 nxt
= (*before
)->h_next
;
182 (*before
)->h_next
= 0; /* probably pointless, but whatever. */
186 /* Note: we never actually get here. the callers don't delete things
188 assert(*before
!= 0);
192 static volatile int do_run_maintenance_thread
= 1;
194 #define DEFAULT_HASH_BULK_MOVE 1
195 int hash_bulk_move
= DEFAULT_HASH_BULK_MOVE
;
197 static void *assoc_maintenance_thread(void *arg
) {
199 while (do_run_maintenance_thread
) {
202 /* Lock the cache, and bulk move multiple buckets to the new
204 mutex_lock(&cache_lock
);
206 for (ii
= 0; ii
< hash_bulk_move
&& expanding
; ++ii
) {
210 for (it
= old_hashtable
[expand_bucket
]; NULL
!= it
; it
= next
) {
213 bucket
= hash(ITEM_key(it
), it
->nkey
, 0) & hashmask(hashpower
);
214 it
->h_next
= primary_hashtable
[bucket
];
215 primary_hashtable
[bucket
] = it
;
218 old_hashtable
[expand_bucket
] = NULL
;
221 if (expand_bucket
== hashsize(hashpower
- 1)) {
225 stats
.hash_bytes
-= hashsize(hashpower
- 1) * sizeof(void *);
226 stats
.hash_is_expanding
= 0;
228 if (settings
.verbose
> 1)
229 fprintf(stderr
, "Hash table expansion done\n");
234 /* We are done expanding.. just wait for next invocation */
235 pthread_cond_wait(&maintenance_cond
, &cache_lock
);
238 mutex_unlock(&cache_lock
);
243 static pthread_t maintenance_tid
;
245 int start_assoc_maintenance_thread() {
247 char *env
= getenv("MEMCACHED_HASH_BULK_MOVE");
249 hash_bulk_move
= atoi(env
);
250 if (hash_bulk_move
== 0) {
251 hash_bulk_move
= DEFAULT_HASH_BULK_MOVE
;
254 if ((ret
= pthread_create(&maintenance_tid
, NULL
,
255 assoc_maintenance_thread
, NULL
)) != 0) {
256 fprintf(stderr
, "Can't create thread: %s\n", strerror(ret
));
262 void stop_assoc_maintenance_thread() {
263 mutex_lock(&cache_lock
);
264 do_run_maintenance_thread
= 0;
265 pthread_cond_signal(&maintenance_cond
);
266 mutex_unlock(&cache_lock
);
268 /* Wait for the maintenance thread to stop */
269 pthread_join(maintenance_tid
, NULL
);