"Fossies" - the Fresh Open Source Software Archive 
Member "memcached-1.6.9/assoc.c" (21 Nov 2020, 11468 Bytes) of package /linux/www/memcached-1.6.9.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "assoc.c" see the
Fossies "Dox" file reference documentation and the latest
Fossies "Diffs" side-by-side code changes report:
1.6.8_vs_1.6.9.
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/resource.h>
18 #include <signal.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 static pthread_mutex_t maintenance_lock = PTHREAD_MUTEX_INITIALIZER;
30
31 typedef uint32_t 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 unsigned int hashpower = HASHPOWER_DEFAULT;
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 /* Flag: Are we in the middle of expanding now? */
50 static bool expanding = false;
51
52 /*
53 * During expansion we migrate values with bucket granularity; this is how
54 * far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1.
55 */
56 static unsigned int expand_bucket = 0;
57
58 void assoc_init(const int hashtable_init) {
59 if (hashtable_init) {
60 hashpower = hashtable_init;
61 }
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 STATS_LOCK();
68 stats_state.hash_power_level = hashpower;
69 stats_state.hash_bytes = hashsize(hashpower) * sizeof(void *);
70 STATS_UNLOCK();
71 }
72
73 item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
74 item *it;
75 unsigned int oldbucket;
76
77 if (expanding &&
78 (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
79 {
80 it = old_hashtable[oldbucket];
81 } else {
82 it = primary_hashtable[hv & hashmask(hashpower)];
83 }
84
85 item *ret = NULL;
86 int depth = 0;
87 while (it) {
88 if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
89 ret = it;
90 break;
91 }
92 it = it->h_next;
93 ++depth;
94 }
95 MEMCACHED_ASSOC_FIND(key, nkey, depth);
96 return ret;
97 }
98
99 /* returns the address of the item pointer before the key. if *item == 0,
100 the item wasn't found */
101
102 static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
103 item **pos;
104 unsigned int oldbucket;
105
106 if (expanding &&
107 (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
108 {
109 pos = &old_hashtable[oldbucket];
110 } else {
111 pos = &primary_hashtable[hv & hashmask(hashpower)];
112 }
113
114 while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
115 pos = &(*pos)->h_next;
116 }
117 return pos;
118 }
119
120 /* grows the hashtable to the next power of 2. */
121 static void assoc_expand(void) {
122 old_hashtable = primary_hashtable;
123
124 primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
125 if (primary_hashtable) {
126 if (settings.verbose > 1)
127 fprintf(stderr, "Hash table expansion starting\n");
128 hashpower++;
129 expanding = true;
130 expand_bucket = 0;
131 STATS_LOCK();
132 stats_state.hash_power_level = hashpower;
133 stats_state.hash_bytes += hashsize(hashpower) * sizeof(void *);
134 stats_state.hash_is_expanding = true;
135 STATS_UNLOCK();
136 } else {
137 primary_hashtable = old_hashtable;
138 /* Bad news, but we can keep running. */
139 }
140 }
141
142 void assoc_start_expand(uint64_t curr_items) {
143 if (pthread_mutex_trylock(&maintenance_lock) == 0) {
144 if (curr_items > (hashsize(hashpower) * 3) / 2 && hashpower < HASHPOWER_MAX) {
145 pthread_cond_signal(&maintenance_cond);
146 }
147 pthread_mutex_unlock(&maintenance_lock);
148 }
149 }
150
151 /* Note: this isn't an assoc_update. The key must not already exist to call this */
152 int assoc_insert(item *it, const uint32_t hv) {
153 unsigned int oldbucket;
154
155 // assert(assoc_find(ITEM_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */
156
157 if (expanding &&
158 (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
159 {
160 it->h_next = old_hashtable[oldbucket];
161 old_hashtable[oldbucket] = it;
162 } else {
163 it->h_next = primary_hashtable[hv & hashmask(hashpower)];
164 primary_hashtable[hv & hashmask(hashpower)] = it;
165 }
166
167 MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey);
168 return 1;
169 }
170
171 void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
172 item **before = _hashitem_before(key, nkey, hv);
173
174 if (*before) {
175 item *nxt;
176 /* The DTrace probe cannot be triggered as the last instruction
177 * due to possible tail-optimization by the compiler
178 */
179 MEMCACHED_ASSOC_DELETE(key, nkey);
180 nxt = (*before)->h_next;
181 (*before)->h_next = 0; /* probably pointless, but whatever. */
182 *before = nxt;
183 return;
184 }
185 /* Note: we never actually get here. the callers don't delete things
186 they can't find. */
187 assert(*before != 0);
188 }
189
190
191 static volatile int do_run_maintenance_thread = 1;
192
193 #define DEFAULT_HASH_BULK_MOVE 1
194 int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
195
196 static void *assoc_maintenance_thread(void *arg) {
197
198 mutex_lock(&maintenance_lock);
199 while (do_run_maintenance_thread) {
200 int ii = 0;
201
202 /* There is only one expansion thread, so no need to global lock. */
203 for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
204 item *it, *next;
205 unsigned int bucket;
206 void *item_lock = NULL;
207
208 /* bucket = hv & hashmask(hashpower) =>the bucket of hash table
209 * is the lowest N bits of the hv, and the bucket of item_locks is
210 * also the lowest M bits of hv, and N is greater than M.
211 * So we can process expanding with only one item_lock. cool! */
212 if ((item_lock = item_trylock(expand_bucket))) {
213 for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
214 next = it->h_next;
215 bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);
216 it->h_next = primary_hashtable[bucket];
217 primary_hashtable[bucket] = it;
218 }
219
220 old_hashtable[expand_bucket] = NULL;
221
222 expand_bucket++;
223 if (expand_bucket == hashsize(hashpower - 1)) {
224 expanding = false;
225 free(old_hashtable);
226 STATS_LOCK();
227 stats_state.hash_bytes -= hashsize(hashpower - 1) * sizeof(void *);
228 stats_state.hash_is_expanding = false;
229 STATS_UNLOCK();
230 if (settings.verbose > 1)
231 fprintf(stderr, "Hash table expansion done\n");
232 }
233
234 } else {
235 usleep(10*1000);
236 }
237
238 if (item_lock) {
239 item_trylock_unlock(item_lock);
240 item_lock = NULL;
241 }
242 }
243
244 if (!expanding) {
245 /* We are done expanding.. just wait for next invocation */
246 pthread_cond_wait(&maintenance_cond, &maintenance_lock);
247 /* assoc_expand() swaps out the hash table entirely, so we need
248 * all threads to not hold any references related to the hash
249 * table while this happens.
250 * This is instead of a more complex, possibly slower algorithm to
251 * allow dynamic hash table expansion without causing significant
252 * wait times.
253 */
254 if (do_run_maintenance_thread) {
255 pause_threads(PAUSE_ALL_THREADS);
256 assoc_expand();
257 pause_threads(RESUME_ALL_THREADS);
258 }
259 }
260 }
261 mutex_unlock(&maintenance_lock);
262 return NULL;
263 }
264
265 static pthread_t maintenance_tid;
266
267 int start_assoc_maintenance_thread() {
268 int ret;
269 char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
270 if (env != NULL) {
271 hash_bulk_move = atoi(env);
272 if (hash_bulk_move == 0) {
273 hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
274 }
275 }
276
277 if ((ret = pthread_create(&maintenance_tid, NULL,
278 assoc_maintenance_thread, NULL)) != 0) {
279 fprintf(stderr, "Can't create thread: %s\n", strerror(ret));
280 return -1;
281 }
282 return 0;
283 }
284
285 void stop_assoc_maintenance_thread() {
286 mutex_lock(&maintenance_lock);
287 do_run_maintenance_thread = 0;
288 pthread_cond_signal(&maintenance_cond);
289 mutex_unlock(&maintenance_lock);
290
291 /* Wait for the maintenance thread to stop */
292 pthread_join(maintenance_tid, NULL);
293 }
294
295 struct assoc_iterator {
296 unsigned int bucket;
297 bool bucket_locked;
298 item *it;
299 item *next;
300 };
301
302 void *assoc_get_iterator(void) {
303 struct assoc_iterator *iter = calloc(1, sizeof(struct assoc_iterator));
304 if (iter == NULL) {
305 return NULL;
306 }
307 // this will hang the caller while a hash table expansion is running.
308 mutex_lock(&maintenance_lock);
309 return iter;
310 }
311
312 bool assoc_iterate(void *iterp, item **it) {
313 struct assoc_iterator *iter = (struct assoc_iterator *) iterp;
314 *it = NULL;
315 // - if locked bucket and next, update next and return
316 if (iter->bucket_locked) {
317 if (iter->next != NULL) {
318 iter->it = iter->next;
319 iter->next = iter->it->h_next;
320 *it = iter->it;
321 } else {
322 // unlock previous bucket, if any
323 item_unlock(iter->bucket);
324 // iterate the bucket post since it starts at 0.
325 iter->bucket++;
326 iter->bucket_locked = false;
327 *it = NULL;
328 }
329 return true;
330 }
331
332 // - loop until we hit the end or find something.
333 if (iter->bucket != hashsize(hashpower)) {
334 // - lock next bucket
335 item_lock(iter->bucket);
336 iter->bucket_locked = true;
337 // - only check the primary hash table since expand is blocked.
338 iter->it = primary_hashtable[iter->bucket];
339 if (iter->it != NULL) {
340 // - set it, next and return
341 iter->next = iter->it->h_next;
342 *it = iter->it;
343 } else {
344 // - nothing found in this bucket, try next.
345 item_unlock(iter->bucket);
346 iter->bucket_locked = false;
347 iter->bucket++;
348 }
349 } else {
350 return false;
351 }
352
353 return true;
354 }
355
356 void assoc_iterate_final(void *iterp) {
357 struct assoc_iterator *iter = (struct assoc_iterator *) iterp;
358 if (iter->bucket_locked) {
359 item_unlock(iter->bucket);
360 }
361 mutex_unlock(&maintenance_lock);
362 free(iter);
363 }