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