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.h | 240 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 240 insertions(+) create mode 100644 lib/generic/lru.h (limited to 'lib/generic/lru.h') diff --git a/lib/generic/lru.h b/lib/generic/lru.h new file mode 100644 index 0000000..448c1b9 --- /dev/null +++ b/lib/generic/lru.h @@ -0,0 +1,240 @@ +/* Copyright (C) CZ.NIC, z.s.p.o. + * SPDX-License-Identifier: GPL-3.0-or-later + */ +/** + * @file lru.h + * @brief A lossy cache. + * + * @note The implementation tries to keep frequent keys and avoid others, + * even if "used recently", so it may refuse to store it on lru_get_new(). + * It uses hashing to split the problem pseudo-randomly into smaller groups, + * and within each it tries to approximate relative usage counts of several + * most frequent keys/hashes. This tracking is done for *more* keys than + * those that are actually stored. + * + * Example usage: + * @code{.c} + * // Define new LRU type + * typedef lru_t(int) lru_int_t; + * + * // Create LRU + * lru_int_t *lru; + * lru_create(&lru, 5, NULL, NULL); + * + * // Insert some values + * int *pi = lru_get_new(lru, "luke", strlen("luke"), NULL); + * if (pi) + * *pi = 42; + * pi = lru_get_new(lru, "leia", strlen("leia"), NULL); + * if (pi) + * *pi = 24; + * + * // Retrieve values + * int *ret = lru_get_try(lru, "luke", strlen("luke"), NULL); + * if (!ret) printf("luke dropped out!\n"); + * else printf("luke's number is %d\n", *ret); + * + * char *enemies[] = {"goro", "raiden", "subzero", "scorpion"}; + * for (int i = 0; i < 4; ++i) { + * int *val = lru_get_new(lru, enemies[i], strlen(enemies[i]), NULL); + * if (val) + * *val = i; + * } + * + * // We're done + * lru_free(lru); + * @endcode + * + * \addtogroup generics + * @{ + */ + +#pragma once + +#include +#include +#include + +#include "contrib/ucw/lib.h" +#include "lib/utils.h" +#include "libknot/mm_ctx.h" + +/* ================================ Interface ================================ */ + +/** @brief The type for LRU, parametrized by value type. */ +#define lru_t(type) \ + union { \ + type *pdata_t; /* only the *type* information is used */ \ + struct lru lru; \ + } + +/** + * @brief Allocate and initialize an LRU with default associativity. + * + * The real limit on the number of slots can be a bit larger but less than double. + * + * @param ptable pointer to a pointer to the LRU + * @param max_slots number of slots + * @param mm_ctx_array memory context to use for the huge array, NULL for default + * If you pass your own, it needs to produce CACHE_ALIGNED allocations (ubsan). + * @param mm_ctx memory context to use for individual key-value pairs, NULL for default + * + * @note The pointers to memory contexts need to remain valid + * during the whole life of the structure (or be NULL). + */ +/* Pragmas: C11 only standardizes alignof on type names, not on expressions. + * That's a GNU extension; in clang it's supported but may generate warnings. + * It seems hard to disable warnings that are only supported by some compilers. */ +#define lru_create(ptable, max_slots, mm_ctx_array, mm_ctx) do { \ + (void)(((__typeof__((*(ptable))->pdata_t))0) == (void *)0); /* typecheck lru_t */ \ + _Pragma("GCC diagnostic push") \ + _Pragma("GCC diagnostic ignored \"-Wpragmas\"") \ + _Pragma("GCC diagnostic ignored \"-Wunknown-pragmas\"") \ + _Pragma("GCC diagnostic ignored \"-Wgnu-alignof-expression\"") \ + *(ptable) = (__typeof__(*(ptable))) \ + lru_create_impl((max_slots), alignof(*( (*(ptable))->pdata_t )), \ + (mm_ctx_array), (mm_ctx)); \ + _Pragma("GCC diagnostic pop") \ + } while (false) + +/** @brief Free an LRU created by lru_create (it can be NULL). */ +#define lru_free(table) \ + lru_free_impl(&(table)->lru) + +/** @brief Reset an LRU to the empty state (but preserve any settings). */ +#define lru_reset(table) \ + lru_reset_impl(&(table)->lru) + +/** + * @brief Find key in the LRU and return pointer to the corresponding value. + * + * @param table pointer to LRU + * @param key_ lookup key + * @param len_ key length + * @return pointer to data or NULL if not found + */ +#define lru_get_try(table, key_, len_) \ + (__typeof__((table)->pdata_t)) \ + lru_get_impl(&(table)->lru, (key_), (len_), -1, false, NULL) + +/** + * @brief Return pointer to value, inserting if needed (zeroed). + * + * @param table pointer to LRU + * @param key_ lookup key + * @param len_ key lengthkeys + * @param is_new pointer to bool to store result of operation + * (true if entry is newly added, false otherwise; can be NULL). + * @return pointer to data or NULL (can be even if memory could be allocated!) + */ +#define lru_get_new(table, key_, len_, is_new) \ + (__typeof__((table)->pdata_t)) \ + lru_get_impl(&(table)->lru, (key_), (len_), \ + sizeof(*(table)->pdata_t), true, is_new) + +/** + * @brief Apply a function to every item in LRU. + * + * @param table pointer to LRU + * @param function enum lru_apply_do (*function)(const char *key, uint len, val_type *val, void *baton) + * See enum lru_apply_do for the return type meanings. + * @param baton extra pointer passed to each function invocation + */ +#define lru_apply(table, function, baton) do { \ + lru_apply_fun_g(fun_dummy, __typeof__(*(table)->pdata_t)) = 0; \ + (void)(fun_dummy == (function)); /* produce a warning with incompatible function type */ \ + lru_apply_impl(&(table)->lru, (lru_apply_fun)(function), (baton)); \ + } while (false) + +/** @brief Possible actions to do with an element. */ +enum lru_apply_do { + LRU_APPLY_DO_NOTHING, + LRU_APPLY_DO_EVICT, + /* maybe more in future*/ +}; + +/** + * @brief Return the real capacity - maximum number of keys holdable within. + * + * @param table pointer to LRU + */ +#define lru_capacity(table) lru_capacity_impl(&(table)->lru) + + + +/* ======================== Inlined part of implementation ======================== */ +/** @cond internal */ + +#define lru_apply_fun_g(name, val_type) \ + enum lru_apply_do (*(name))(const char *key, uint len, val_type *val, void *baton) +typedef lru_apply_fun_g(lru_apply_fun, void); + +#if __GNUC__ >= 4 + #define CACHE_ALIGNED __attribute__((aligned(64))) +#else + #define CACHE_ALIGNED +#endif + +struct lru; +void lru_free_items_impl(struct lru *lru); +struct lru * lru_create_impl(uint max_slots, uint val_alignment, + knot_mm_t *mm_array, knot_mm_t *mm); +void * lru_get_impl(struct lru *lru, const char *key, uint key_len, + uint val_len, bool do_insert, bool *is_new); +void lru_apply_impl(struct lru *lru, lru_apply_fun f, void *baton); + +struct lru_item; + +#if SIZE_MAX > (1 << 32) + /** @internal The number of keys stored within each group. */ + #define LRU_ASSOC 3 +#else + #define LRU_ASSOC 4 +#endif +/** @internal The number of hashes tracked within each group: 10-1 or 12-1. */ +#define LRU_TRACKED ((64 - sizeof(size_t) * LRU_ASSOC) / 4 - 1) + +struct lru_group { + uint16_t counts[LRU_TRACKED+1]; /*!< Occurrence counters; the last one is special. */ + uint16_t hashes[LRU_TRACKED+1]; /*!< Top halves of hashes; the last one is unused. */ + struct lru_item *items[LRU_ASSOC]; /*!< The full items. */ +} CACHE_ALIGNED; + +/* The sizes are chosen so lru_group just fits into a single x86 cache line. */ +static_assert(64 == sizeof(struct lru_group) + && 64 == LRU_ASSOC * sizeof(void*) + (LRU_TRACKED+1) * 4, + "bad sizing for your sizeof(void*)"); + +struct lru { + struct knot_mm *mm, /**< Memory context to use for keys. */ + *mm_array; /**< Memory context to use for this structure itself. */ + uint log_groups; /**< Logarithm of the number of LRU groups. */ + uint val_alignment; /**< Alignment for the values. */ + struct lru_group groups[] CACHE_ALIGNED; /**< The groups of items. */ +}; + +/** @internal See lru_free. */ +static inline void lru_free_impl(struct lru *lru) +{ + if (!lru) + return; + lru_free_items_impl(lru); + mm_free(lru->mm_array, lru); +} + +/** @internal See lru_reset. */ +static inline void lru_reset_impl(struct lru *lru) +{ + lru_free_items_impl(lru); + memset(lru->groups, 0, sizeof(lru->groups[0]) * (1 << lru->log_groups)); +} + +/** @internal See lru_capacity. */ +static inline uint lru_capacity_impl(struct lru *lru) +{ + kr_require(lru); + return (1 << lru->log_groups) * LRU_ASSOC; +} + +/** @endcond */ +/** @} (addtogroup generics) */ -- cgit v1.2.3