1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3 * Hash table
4 *
5 */
6 #include "config.h"
7 #include <fcntl.h>
8 #include <errno.h>
9 #include <stdlib.h>
10 #include <stdio.h>
11 #include <string.h>
12 #include <assert.h>
13 #include <pthread.h>
14
15 #include "default_engine.h"
16
17 #define hashsize(n) ((uint32_t)1<<(n))
18 #define hashmask(n) (hashsize(n)-1)
19
assoc_init(struct default_engine * engine)20 ENGINE_ERROR_CODE assoc_init(struct default_engine *engine) {
21 engine->assoc.primary_hashtable = calloc(hashsize(engine->assoc.hashpower), sizeof(void *));
22 return (engine->assoc.primary_hashtable != NULL) ? ENGINE_SUCCESS : ENGINE_ENOMEM;
23 }
24
assoc_find(struct default_engine * engine,uint32_t hash,const char * key,const size_t nkey)25 hash_item *assoc_find(struct default_engine *engine, uint32_t hash, const char *key, const size_t nkey) {
26 hash_item *it;
27 unsigned int oldbucket;
28
29 if (engine->assoc.expanding &&
30 (oldbucket = (hash & hashmask(engine->assoc.hashpower - 1))) >= engine->assoc.expand_bucket)
31 {
32 it = engine->assoc.old_hashtable[oldbucket];
33 } else {
34 it = engine->assoc.primary_hashtable[hash & hashmask(engine->assoc.hashpower)];
35 }
36
37 hash_item *ret = NULL;
38 int depth = 0;
39 while (it) {
40 if ((nkey == it->nkey) && (memcmp(key, item_get_key(it), nkey) == 0)) {
41 ret = it;
42 break;
43 }
44 it = it->h_next;
45 ++depth;
46 }
47 MEMCACHED_ASSOC_FIND(key, nkey, depth);
48 return ret;
49 }
50
51 /* returns the address of the item pointer before the key. if *item == 0,
52 the item wasn't found */
53
_hashitem_before(struct default_engine * engine,uint32_t hash,const char * key,const size_t nkey)54 static hash_item** _hashitem_before(struct default_engine *engine,
55 uint32_t hash,
56 const char *key,
57 const size_t nkey) {
58 hash_item **pos;
59 unsigned int oldbucket;
60
61 if (engine->assoc.expanding &&
62 (oldbucket = (hash & hashmask(engine->assoc.hashpower - 1))) >= engine->assoc.expand_bucket)
63 {
64 pos = &engine->assoc.old_hashtable[oldbucket];
65 } else {
66 pos = &engine->assoc.primary_hashtable[hash & hashmask(engine->assoc.hashpower)];
67 }
68
69 while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, item_get_key(*pos), nkey))) {
70 pos = &(*pos)->h_next;
71 }
72 return pos;
73 }
74
75 static void *assoc_maintenance_thread(void *arg);
76
77 /* grows the hashtable to the next power of 2. */
assoc_expand(struct default_engine * engine)78 static void assoc_expand(struct default_engine *engine) {
79 engine->assoc.old_hashtable = engine->assoc.primary_hashtable;
80
81 engine->assoc.primary_hashtable = calloc(hashsize(engine->assoc.hashpower + 1), sizeof(void *));
82 if (engine->assoc.primary_hashtable) {
83 engine->assoc.hashpower++;
84 engine->assoc.expanding = true;
85 engine->assoc.expand_bucket = 0;
86
87 /* start a thread to do the expansion */
88 int ret = 0;
89 pthread_t tid;
90 pthread_attr_t attr;
91
92 if (pthread_attr_init(&attr) != 0 ||
93 pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED) != 0 ||
94 (ret = pthread_create(&tid, &attr,
95 assoc_maintenance_thread, engine)) != 0)
96 {
97 EXTENSION_LOGGER_DESCRIPTOR *logger;
98 logger = (void*)engine->server.extension->get_extension(EXTENSION_LOGGER);
99 logger->log(EXTENSION_LOG_WARNING, NULL,
100 "Can't create thread: %s\n", strerror(ret));
101 engine->assoc.hashpower--;
102 engine->assoc.expanding = false;
103 free(engine->assoc.primary_hashtable);
104 engine->assoc.primary_hashtable =engine->assoc.old_hashtable;
105 }
106 } else {
107 engine->assoc.primary_hashtable = engine->assoc.old_hashtable;
108 /* Bad news, but we can keep running. */
109 }
110 }
111
112 /* Note: this isn't an assoc_update. The key must not already exist to call this */
assoc_insert(struct default_engine * engine,uint32_t hash,hash_item * it)113 int assoc_insert(struct default_engine *engine, uint32_t hash, hash_item *it) {
114 unsigned int oldbucket;
115
116 assert(assoc_find(engine, hash, item_get_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */
117
118 if (engine->assoc.expanding &&
119 (oldbucket = (hash & hashmask(engine->assoc.hashpower - 1))) >= engine->assoc.expand_bucket)
120 {
121 it->h_next = engine->assoc.old_hashtable[oldbucket];
122 engine->assoc.old_hashtable[oldbucket] = it;
123 } else {
124 it->h_next = engine->assoc.primary_hashtable[hash & hashmask(engine->assoc.hashpower)];
125 engine->assoc.primary_hashtable[hash & hashmask(engine->assoc.hashpower)] = it;
126 }
127
128 engine->assoc.hash_items++;
129 if (! engine->assoc.expanding && engine->assoc.hash_items > (hashsize(engine->assoc.hashpower) * 3) / 2) {
130 assoc_expand(engine);
131 }
132
133 MEMCACHED_ASSOC_INSERT(item_get_key(it), it->nkey, engine->assoc.hash_items);
134 return 1;
135 }
136
assoc_delete(struct default_engine * engine,uint32_t hash,const char * key,const size_t nkey)137 void assoc_delete(struct default_engine *engine, uint32_t hash, const char *key, const size_t nkey) {
138 hash_item **before = _hashitem_before(engine, hash, key, nkey);
139
140 if (*before) {
141 hash_item *nxt;
142 engine->assoc.hash_items--;
143 /* The DTrace probe cannot be triggered as the last instruction
144 * due to possible tail-optimization by the compiler
145 */
146 MEMCACHED_ASSOC_DELETE(key, nkey, engine->assoc.hash_items);
147 nxt = (*before)->h_next;
148 (*before)->h_next = 0; /* probably pointless, but whatever. */
149 *before = nxt;
150 return;
151 }
152 /* Note: we never actually get here. the callers don't delete things
153 they can't find. */
154 assert(*before != 0);
155 }
156
157
158
159 #define DEFAULT_HASH_BULK_MOVE 1
160 int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
161
assoc_maintenance_thread(void * arg)162 static void *assoc_maintenance_thread(void *arg) {
163 struct default_engine *engine = arg;
164 bool done = false;
165 do {
166 int ii;
167 pthread_mutex_lock(&engine->cache_lock);
168
169 for (ii = 0; ii < hash_bulk_move && engine->assoc.expanding; ++ii) {
170 hash_item *it, *next;
171 int bucket;
172
173 for (it = engine->assoc.old_hashtable[engine->assoc.expand_bucket];
174 NULL != it; it = next) {
175 next = it->h_next;
176
177 bucket = engine->server.core->hash(item_get_key(it), it->nkey, 0)
178 & hashmask(engine->assoc.hashpower);
179 it->h_next = engine->assoc.primary_hashtable[bucket];
180 engine->assoc.primary_hashtable[bucket] = it;
181 }
182
183 engine->assoc.old_hashtable[engine->assoc.expand_bucket] = NULL;
184 engine->assoc.expand_bucket++;
185 if (engine->assoc.expand_bucket == hashsize(engine->assoc.hashpower - 1)) {
186 engine->assoc.expanding = false;
187 free(engine->assoc.old_hashtable);
188 if (engine->config.verbose > 1) {
189 EXTENSION_LOGGER_DESCRIPTOR *logger;
190 logger = (void*)engine->server.extension->get_extension(EXTENSION_LOGGER);
191 logger->log(EXTENSION_LOG_INFO, NULL,
192 "Hash table expansion done\n");
193 }
194 }
195 }
196 if (!engine->assoc.expanding) {
197 done = true;
198 }
199 pthread_mutex_unlock(&engine->cache_lock);
200 } while (!done);
201
202 return NULL;
203 }
204