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             fprintf(stderr, "Can't create thread: %s\n", strerror(ret));
98             engine->assoc.hashpower--;
99             engine->assoc.expanding = false;
100             free(engine->assoc.primary_hashtable);
101             engine->assoc.primary_hashtable =engine->assoc.old_hashtable;
102         }
103     } else {
104         engine->assoc.primary_hashtable = engine->assoc.old_hashtable;
105         /* Bad news, but we can keep running. */
106     }
107 }
108 
109 /* 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)110 int assoc_insert(struct default_engine *engine, uint32_t hash, hash_item *it) {
111     unsigned int oldbucket;
112 
113     assert(assoc_find(engine, hash, item_get_key(it), it->nkey) == 0);  /* shouldn't have duplicately named things defined */
114 
115     if (engine->assoc.expanding &&
116         (oldbucket = (hash & hashmask(engine->assoc.hashpower - 1))) >= engine->assoc.expand_bucket)
117     {
118         it->h_next = engine->assoc.old_hashtable[oldbucket];
119         engine->assoc.old_hashtable[oldbucket] = it;
120     } else {
121         it->h_next = engine->assoc.primary_hashtable[hash & hashmask(engine->assoc.hashpower)];
122         engine->assoc.primary_hashtable[hash & hashmask(engine->assoc.hashpower)] = it;
123     }
124 
125     engine->assoc.hash_items++;
126     if (! engine->assoc.expanding && engine->assoc.hash_items > (hashsize(engine->assoc.hashpower) * 3) / 2) {
127         assoc_expand(engine);
128     }
129 
130     MEMCACHED_ASSOC_INSERT(item_get_key(it), it->nkey, engine->assoc.hash_items);
131     return 1;
132 }
133 
assoc_delete(struct default_engine * engine,uint32_t hash,const char * key,const size_t nkey)134 void assoc_delete(struct default_engine *engine, uint32_t hash, const char *key, const size_t nkey) {
135     hash_item **before = _hashitem_before(engine, hash, key, nkey);
136 
137     if (*before) {
138         hash_item *nxt;
139         engine->assoc.hash_items--;
140         /* The DTrace probe cannot be triggered as the last instruction
141          * due to possible tail-optimization by the compiler
142          */
143         MEMCACHED_ASSOC_DELETE(key, nkey, engine->assoc.hash_items);
144         nxt = (*before)->h_next;
145         (*before)->h_next = 0;   /* probably pointless, but whatever. */
146         *before = nxt;
147         return;
148     }
149     /* Note:  we never actually get here.  the callers don't delete things
150        they can't find. */
151     assert(*before != 0);
152 }
153 
154 
155 
156 #define DEFAULT_HASH_BULK_MOVE 1
157 int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
158 
assoc_maintenance_thread(void * arg)159 static void *assoc_maintenance_thread(void *arg) {
160     struct default_engine *engine = arg;
161     bool done = false;
162     do {
163         int ii;
164         pthread_mutex_lock(&engine->cache_lock);
165 
166         for (ii = 0; ii < hash_bulk_move && engine->assoc.expanding; ++ii) {
167             hash_item *it, *next;
168             int bucket;
169 
170             for (it = engine->assoc.old_hashtable[engine->assoc.expand_bucket];
171                  NULL != it; it = next) {
172                 next = it->h_next;
173 
174                 bucket = engine->server.core->hash(item_get_key(it), it->nkey, 0)
175                     & hashmask(engine->assoc.hashpower);
176                 it->h_next = engine->assoc.primary_hashtable[bucket];
177                 engine->assoc.primary_hashtable[bucket] = it;
178             }
179 
180             engine->assoc.old_hashtable[engine->assoc.expand_bucket] = NULL;
181             engine->assoc.expand_bucket++;
182             if (engine->assoc.expand_bucket == hashsize(engine->assoc.hashpower - 1)) {
183                 engine->assoc.expanding = false;
184                 free(engine->assoc.old_hashtable);
185                 if (engine->config.verbose > 1) {
186                     fprintf(stderr, "Hash table expansion done\n");
187                 }
188             }
189         }
190         if (!engine->assoc.expanding) {
191             done = true;
192         }
193         pthread_mutex_unlock(&engine->cache_lock);
194     } while (!done);
195 
196     return NULL;
197 }
198