From 830407e88f9d40d954356c3754f2647f91d5c06a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:26:00 +0200 Subject: Adding upstream version 5.6.0. Signed-off-by: Daniel Baumann --- lib/generic/lru.c | 249 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 249 insertions(+) create mode 100644 lib/generic/lru.c (limited to 'lib/generic/lru.c') diff --git a/lib/generic/lru.c b/lib/generic/lru.c new file mode 100644 index 0000000..857b20b --- /dev/null +++ b/lib/generic/lru.c @@ -0,0 +1,249 @@ +/* Copyright (C) CZ.NIC, z.s.p.o. + * SPDX-License-Identifier: GPL-3.0-or-later + */ + +#include "lib/generic/lru.h" +#include "contrib/murmurhash3/murmurhash3.h" +#include "contrib/ucw/mempool.h" + +typedef struct lru_group lru_group_t; + +struct lru_item { + uint16_t key_len, val_len; /**< Two bytes should be enough for our purposes. */ + char data[]; + /**< Place for both key and value. + * + * We use "char" to satisfy the C99+ aliasing rules. + * See C99 section 6.5 Expressions, paragraph 7. + * Any type can be accessed through char-pointer, + * so we can use a common struct definition + * for all types being held. + * + * The value address is restricted by val_alignment. + * Approach: require slightly larger sizes from the allocator + * and shift value on the closest address with val_alignment. + */ +}; + +/** @brief Round the value up to a multiple of mul (a power of two). */ +static inline size_t round_power(size_t size, size_t mult) +{ + kr_require(__builtin_popcount(mult) == 1); + size_t res = ((size - 1) & ~(mult - 1)) + mult; + kr_require(__builtin_ctz(res) >= __builtin_ctz(mult)); + kr_require(size <= res && res < size + mult); + return res; +} + +/** @internal Compute the allocation size for an lru_item. */ +static uint item_size(const struct lru *lru, uint key_len, uint val_len) +{ + uint key_end = offsetof(struct lru_item, data) + key_len; + return key_end + (lru->val_alignment - 1) + val_len; + /* ^^^ worst-case padding length + * Well, we might compute the bound a bit more precisely, + * as we know that lru_item will get alignment at least + * some sizeof(void*) and we know all the lengths, + * but let's not complicate it, as the gain would be small anyway. */ +} + +/** @internal Return pointer to value in an lru_item. */ +static void * item_val(const struct lru *lru, struct lru_item *it) +{ + size_t key_end = it->data + it->key_len - (char *)NULL; + size_t val_begin = round_power(key_end, lru->val_alignment); + return (char *)NULL + val_begin; +} + +/** @internal Free each item. */ +KR_EXPORT void lru_free_items_impl(struct lru *lru) +{ + if (kr_fails_assert(lru)) + return; + for (size_t i = 0; i < (1 << (size_t)lru->log_groups); ++i) { + lru_group_t *g = &lru->groups[i]; + for (int j = 0; j < LRU_ASSOC; ++j) + mm_free(lru->mm, g->items[j]); + } +} + +/** @internal See lru_apply. */ +KR_EXPORT void lru_apply_impl(struct lru *lru, lru_apply_fun f, void *baton) +{ + if (kr_fails_assert(lru && f)) + return; + for (size_t i = 0; i < (1 << (size_t)lru->log_groups); ++i) { + lru_group_t *g = &lru->groups[i]; + for (uint j = 0; j < LRU_ASSOC; ++j) { + struct lru_item *it = g->items[j]; + if (!it) + continue; + enum lru_apply_do ret = + f(it->data, it->key_len, item_val(lru, it), baton); + switch(ret) { + case LRU_APPLY_DO_EVICT: // evict + mm_free(lru->mm, it); + g->items[j] = NULL; + g->counts[j] = 0; + g->hashes[j] = 0; + break; + default: + kr_assert(ret == LRU_APPLY_DO_NOTHING); + } + } + } +} + +/** @internal See lru_create. */ +KR_EXPORT struct lru * lru_create_impl(uint max_slots, uint val_alignment, + knot_mm_t *mm_array, knot_mm_t *mm) +{ + if (kr_fails_assert(max_slots && __builtin_popcount(val_alignment) == 1)) + return NULL; + // let lru->log_groups = ceil(log2(max_slots / (float) assoc)) + // without trying for efficiency + uint group_count = (max_slots - 1) / LRU_ASSOC + 1; + uint log_groups = 0; + for (uint s = group_count - 1; s; s /= 2) + ++log_groups; + group_count = 1 << log_groups; + if (kr_fails_assert(max_slots <= group_count * LRU_ASSOC && group_count * LRU_ASSOC < 2 * max_slots)) + return NULL; + + /* Get a sufficiently aligning mm_array if NULL is passed. */ + if (!mm_array) { + static knot_mm_t mm_array_default = { 0 }; + if (!mm_array_default.ctx) + mm_ctx_init_aligned(&mm_array_default, alignof(struct lru)); + mm_array = &mm_array_default; + } + if (kr_fails_assert(mm_array->alloc && mm_array->alloc != (knot_mm_alloc_t)mp_alloc)) + return NULL; + + size_t size = offsetof(struct lru, groups[group_count]); + struct lru *lru = mm_alloc(mm_array, size); + if (unlikely(lru == NULL)) + return NULL; + *lru = (struct lru){ + .mm = mm, + .mm_array = mm_array, + .log_groups = log_groups, + .val_alignment = val_alignment, + }; + // zeros are a good init + memset(lru->groups, 0, size - offsetof(struct lru, groups)); + return lru; +} + +/** @internal Decrement all counters within a group. */ +static void group_dec_counts(lru_group_t *g) { + g->counts[LRU_TRACKED] = LRU_TRACKED; + for (uint i = 0; i < LRU_TRACKED + 1; ++i) + if (likely(g->counts[i])) + --g->counts[i]; +} + +/** @internal Increment a counter within a group. */ +static void group_inc_count(lru_group_t *g, int i) { + if (likely(++(g->counts[i]))) + return; + g->counts[i] = -1; + // We could've decreased or halved all of them, but let's keep the max. +} + +/** @internal Implementation of both getting and insertion. + * Note: val_len is only meaningful if do_insert. + * *is_new is only meaningful when return value isn't NULL, contains + * true when returned lru entry has been allocated right now + * if return value is NULL, *is_new remains untouched. + */ +KR_EXPORT void * lru_get_impl(struct lru *lru, const char *key, uint key_len, + uint val_len, bool do_insert, bool *is_new) +{ + bool ok = lru && (key || !key_len) && key_len <= UINT16_MAX + && (!do_insert || val_len <= UINT16_MAX); + if (kr_fails_assert(ok)) + return NULL; // reasonable fallback when not debugging + bool is_new_entry = false; + // find the right group + uint32_t khash = hash(key, key_len); + uint16_t khash_top = khash >> 16; + lru_group_t *g = &lru->groups[khash & ((1 << lru->log_groups) - 1)]; + struct lru_item *it = NULL; + uint i; + // scan the *stored* elements in the group + for (i = 0; i < LRU_ASSOC; ++i) { + if (g->hashes[i] == khash_top) { + it = g->items[i]; + if (likely(it && it->key_len == key_len + && (key_len == 0 || memcmp(it->data, key, key_len) == 0))) { + /* Found a key, but trying to insert a value larger than available + * space in the allocated slot, so the entry must be resized to fit. */ + if (unlikely(do_insert && val_len > it->val_len)) { + goto insert; + } else { + goto found; // to reduce huge nesting depth + } + } + } + } + // key not found; first try an empty/counted-out place to insert + if (do_insert) + for (i = 0; i < LRU_ASSOC; ++i) + if (g->items[i] == NULL || g->counts[i] == 0) + goto insert; + // check if we track key's count at least + for (i = LRU_ASSOC; i < LRU_TRACKED; ++i) { + if (g->hashes[i] == khash_top) { + group_inc_count(g, i); + if (!do_insert) + return NULL; + // check if we trumped some stored key + for (uint j = 0; j < LRU_ASSOC; ++j) + if (unlikely(g->counts[i] > g->counts[j])) { + // evict key j, i.e. swap with i + --g->counts[i]; // we increment it below + SWAP(g->counts[i], g->counts[j]); + SWAP(g->hashes[i], g->hashes[j]); + i = j; + goto insert; + } + return NULL; + } + } + // not found at all: decrement all counts but only on every LRU_TRACKED occasion + if (g->counts[LRU_TRACKED]) + --g->counts[LRU_TRACKED]; + else + group_dec_counts(g); + return NULL; +insert: // insert into position i (incl. key) + if (kr_fails_assert(i < LRU_ASSOC)) + return NULL; + g->hashes[i] = khash_top; + it = g->items[i]; + uint new_size = item_size(lru, key_len, val_len); + if (it == NULL || new_size != item_size(lru, it->key_len, it->val_len)) { + // (re)allocate + mm_free(lru->mm, it); + it = g->items[i] = mm_alloc(lru->mm, new_size); + if (it == NULL) + return NULL; + } + it->key_len = key_len; + it->val_len = val_len; + if (key_len > 0) { + memcpy(it->data, key, key_len); + } + memset(item_val(lru, it), 0, val_len); // clear the value + is_new_entry = true; +found: // key and hash OK on g->items[i]; now update stamps + if (kr_fails_assert(i < LRU_ASSOC)) + return NULL; + group_inc_count(g, i); + if (is_new) { + *is_new = is_new_entry; + } + return item_val(lru, g->items[i]); +} + -- cgit v1.2.3