1 files changed, 273 insertions, 0 deletions
diff --git a/web/server/h2o/libh2o/lib/common/cache.c b/web/server/h2o/libh2o/lib/common/cache.c
new file mode 100644
index 00000000..cc8d8f00
--- /dev/null
+++ b/web/server/h2o/libh2o/lib/common/cache.c
@@ -0,0 +1,273 @@
+/*
+ * Copyright (c) 2014-2016 DeNA Co., Ltd., Kazuho Oku
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
+ * deal in the Software without restriction, including without limitation the
+ * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+#include <assert.h>
+#include <pthread.h>
+#include "khash.h"
+#include "h2o/cache.h"
+#include "h2o/linklist.h"
+#include "h2o/memory.h"
+#include "h2o/string_.h"
+
+static h2o_cache_hashcode_t get_keyhash(h2o_cache_ref_t *ref);
+static int is_equal(h2o_cache_ref_t *x, h2o_cache_ref_t *y);
+
+KHASH_INIT(cache, h2o_cache_ref_t *, char, 0, get_keyhash, is_equal)
+
+struct st_h2o_cache_t {
+    int flags;
+    khash_t(cache) * table;
+    size_t size;
+    size_t capacity;
+    h2o_linklist_t lru;
+    h2o_linklist_t age;
+    uint64_t duration;
+    void (*destroy_cb)(h2o_iovec_t value);
+    pthread_mutex_t mutex; /* only used if (flags & H2O_CACHE_FLAG_MULTITHREADED) != 0 */
+};
+
+static h2o_cache_hashcode_t get_keyhash(h2o_cache_ref_t *ref)
+{
+    return ref->keyhash;
+}
+
+static int is_equal(h2o_cache_ref_t *x, h2o_cache_ref_t *y)
+{
+    return x->key.len == y->key.len && memcmp(x->key.base, y->key.base, x->key.len) == 0;
+}
+
+static void lock_cache(h2o_cache_t *cache)
+{
+    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)
+        pthread_mutex_lock(&cache->mutex);
+}
+
+static void unlock_cache(h2o_cache_t *cache)
+{
+    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)
+        pthread_mutex_unlock(&cache->mutex);
+}
+
+static void erase_ref(h2o_cache_t *cache, khiter_t iter, int reuse)
+{
+    h2o_cache_ref_t *ref = kh_key(cache->table, iter);
+
+    if (!reuse)
+        kh_del(cache, cache->table, iter);
+    h2o_linklist_unlink(&ref->_lru_link);
+    h2o_linklist_unlink(&ref->_age_link);
+    cache->size -= ref->value.len;
+
+    h2o_cache_release(cache, ref);
+}
+
+static int64_t get_timeleft(h2o_cache_t *cache, h2o_cache_ref_t *ref, uint64_t now)
+{
+    return (int64_t)(ref->at + cache->duration) - now;
+}
+
+static void purge(h2o_cache_t *cache, uint64_t now)
+{
+    /* by cache size */
+    while (cache->capacity < cache->size) {
+        h2o_cache_ref_t *last;
+        assert(!h2o_linklist_is_empty(&cache->lru));
+        last = H2O_STRUCT_FROM_MEMBER(h2o_cache_ref_t, _lru_link, cache->lru.next);
+        erase_ref(cache, kh_get(cache, cache->table, last), 0);
+    }
+    /* by TTL */
+    while (!h2o_linklist_is_empty(&cache->age)) {
+        h2o_cache_ref_t *oldest = H2O_STRUCT_FROM_MEMBER(h2o_cache_ref_t, _age_link, cache->age.next);
+        if (get_timeleft(cache, oldest, now) >= 0)
+            break;
+        erase_ref(cache, kh_get(cache, cache->table, oldest), 0);
+    }
+}
+
+h2o_cache_hashcode_t h2o_cache_calchash(const char *s, size_t l)
+{
+    h2o_cache_hashcode_t h = 0;
+    for (; l != 0; --l)
+        h = (h << 5) - h + ((unsigned char *)s)[l - 1];
+    return h;
+}
+
+h2o_cache_t *h2o_cache_create(int flags, size_t capacity, uint64_t duration, void (*destroy_cb)(h2o_iovec_t value))
+{
+    h2o_cache_t *cache = h2o_mem_alloc(sizeof(*cache));
+
+    cache->flags = flags;
+    cache->table = kh_init(cache);
+    cache->size = 0;
+    cache->capacity = capacity;
+    h2o_linklist_init_anchor(&cache->lru);
+    h2o_linklist_init_anchor(&cache->age);
+    cache->duration = duration;
+    cache->destroy_cb = destroy_cb;
+    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)
+        pthread_mutex_init(&cache->mutex, NULL);
+
+    return cache;
+}
+
+void h2o_cache_destroy(h2o_cache_t *cache)
+{
+    h2o_cache_clear(cache);
+    kh_destroy(cache, cache->table);
+    if ((cache->flags & H2O_CACHE_FLAG_MULTITHREADED) != 0)
+        pthread_mutex_destroy(&cache->mutex);
+    free(cache);
+}
+
+void h2o_cache_clear(h2o_cache_t *cache)
+{
+    lock_cache(cache);
+
+    while (!h2o_linklist_is_empty(&cache->lru)) {
+        h2o_cache_ref_t *ref = H2O_STRUCT_FROM_MEMBER(h2o_cache_ref_t, _lru_link, cache->lru.next);
+        erase_ref(cache, kh_get(cache, cache->table, ref), 0);
+    }
+    assert(h2o_linklist_is_linked(&cache->age));
+    assert(kh_size(cache->table) == 0);
+    assert(cache->size == 0);
+
+    unlock_cache(cache);
+}
+
+h2o_cache_ref_t *h2o_cache_fetch(h2o_cache_t *cache, uint64_t now, h2o_iovec_t key, h2o_cache_hashcode_t keyhash)
+{
+    h2o_cache_ref_t search_key, *ref;
+    khiter_t iter;
+    int64_t timeleft;
+
+    if (keyhash == 0)
+        keyhash = h2o_cache_calchash(key.base, key.len);
+    search_key.key = key;
+    search_key.keyhash = keyhash;
+
+    lock_cache(cache);
+
+    purge(cache, now);
+
+    if ((iter = kh_get(cache, cache->table, &search_key)) == kh_end(cache->table))
+        goto NotFound;
+
+    /* found */
+    ref = kh_key(cache->table, iter);
+    timeleft = get_timeleft(cache, ref, now);
+    if (timeleft < 0)
+        goto NotFound;
+    if ((cache->flags & H2O_CACHE_FLAG_EARLY_UPDATE) != 0 && timeleft < 10 && !ref->_requested_early_update) {
+        ref->_requested_early_update = 1;
+        goto NotFound;
+    }
+    /* move the entry to the top of LRU */
+    h2o_linklist_unlink(&ref->_lru_link);
+    h2o_linklist_insert(&cache->lru, &ref->_lru_link);
+    __sync_fetch_and_add(&ref->_refcnt, 1);
+
+    /* unlock and return the found entry */
+    unlock_cache(cache);
+    return ref;
+
+NotFound:
+    unlock_cache(cache);
+    return NULL;
+}
+
+void h2o_cache_release(h2o_cache_t *cache, h2o_cache_ref_t *ref)
+{
+    if (__sync_fetch_and_sub(&ref->_refcnt, 1) == 1) {
+        assert(!h2o_linklist_is_linked(&ref->_lru_link));
+        assert(!h2o_linklist_is_linked(&ref->_age_link));
+        if (cache->destroy_cb != NULL)
+            cache->destroy_cb(ref->value);
+        free(ref->key.base);
+        free(ref);
+    }
+}
+
+int h2o_cache_set(h2o_cache_t *cache, uint64_t now, h2o_iovec_t key, h2o_cache_hashcode_t keyhash, h2o_iovec_t value)
+{
+    h2o_cache_ref_t *newref;
+    khiter_t iter;
+    int existed;
+
+    if (keyhash == 0)
+        keyhash = h2o_cache_calchash(key.base, key.len);
+
+    /* create newref */
+    newref = h2o_mem_alloc(sizeof(*newref));
+    *newref = (h2o_cache_ref_t){h2o_strdup(NULL, key.base, key.len), keyhash, now, value, 0, {NULL}, {NULL}, 1};
+
+    lock_cache(cache);
+
+    /* set or replace the named value */
+    iter = kh_get(cache, cache->table, newref);
+    if (iter != kh_end(cache->table)) {
+        erase_ref(cache, iter, 1);
+        kh_key(cache->table, iter) = newref;
+        existed = 1;
+    } else {
+        int unused;
+        kh_put(cache, cache->table, newref, &unused);
+        existed = 0;
+    }
+    h2o_linklist_insert(&cache->lru, &newref->_lru_link);
+    h2o_linklist_insert(&cache->age, &newref->_age_link);
+    cache->size += newref->value.len;
+
+    purge(cache, now);
+
+    unlock_cache(cache);
+
+    return existed;
+}
+
+void h2o_cache_delete(h2o_cache_t *cache, uint64_t now, h2o_iovec_t key, h2o_cache_hashcode_t keyhash)
+{
+    h2o_cache_ref_t search_key;
+    khiter_t iter;
+
+    if (keyhash == 0)
+        keyhash = h2o_cache_calchash(key.base, key.len);
+    search_key.key = key;
+    search_key.keyhash = keyhash;
+
+    lock_cache(cache);
+
+    purge(cache, now);
+
+    if ((iter = kh_get(cache, cache->table, &search_key)) != kh_end(cache->table))
+        erase_ref(cache, iter, 0);
+
+    unlock_cache(cache);
+}
+
+size_t h2o_cache_get_capacity(h2o_cache_t *cache)
+{
+    return cache->capacity;
+}
+
+uint64_t h2o_cache_get_duration(h2o_cache_t *cache)
+{
+    return cache->duration;
+}