diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-03-09 13:19:22 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-03-09 13:19:22 +0000 |
commit | c21c3b0befeb46a51b6bf3758ffa30813bea0ff0 (patch) | |
tree | 9754ff1ca740f6346cf8483ec915d4054bc5da2d /web/server/h2o/libh2o/lib/common/cache.c | |
parent | Adding upstream version 1.43.2. (diff) | |
download | netdata-0d980fd06561f4670f5d8170c5aedd74023e3702.tar.xz netdata-0d980fd06561f4670f5d8170c5aedd74023e3702.zip |
Adding upstream version 1.44.3.upstream/1.44.3
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'web/server/h2o/libh2o/lib/common/cache.c')
-rw-r--r-- | web/server/h2o/libh2o/lib/common/cache.c | 273 |
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 000000000..cc8d8f007 --- /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; +} |