From 77e50caaf2ef81cd91075cf836fed0e75718ffb4 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 13 Apr 2024 23:12:02 +0200 Subject: Adding debian version 1.8.3-2. Signed-off-by: Daniel Baumann --- debian/vendor-h2o/lib/common/cache.c | 273 +++++++++++++++++++++++++++++++++++ 1 file changed, 273 insertions(+) create mode 100644 debian/vendor-h2o/lib/common/cache.c (limited to 'debian/vendor-h2o/lib/common/cache.c') diff --git a/debian/vendor-h2o/lib/common/cache.c b/debian/vendor-h2o/lib/common/cache.c new file mode 100644 index 0000000..cc8d8f0 --- /dev/null +++ b/debian/vendor-h2o/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 +#include +#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; +} -- cgit v1.2.3