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
19ENGINE_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
25void 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
36hash_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
65static 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
86static void assoc_maintenance_thread(void *arg);
87
88/* grows the hashtable to the next power of 2. */
89static 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 */
121int 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
145void 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
168int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
169
170static 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