/usr/include/libkres/lru.h is in libkres-dev 2.1.1-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 | /* Copyright (C) 2016-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
/**
* @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);
*
* // Insert some values
* int *pi = lru_get_new(lru, "luke", strlen("luke"));
* if (pi)
* *pi = 42;
* pi = lru_get_new(lru, "leia", strlen("leia"));
* if (pi)
* *pi = 24;
*
* // Retrieve values
* int *ret = lru_get_try(lru, "luke", strlen("luke"));
* 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]));
* if (val)
* *val = i;
* }
*
* // We're done
* lru_free(lru);
* @endcode
*
* \addtogroup generics
* @{
*/
#pragma once
#include <assert.h>
#include <stdint.h>
#include <stddef.h>
#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
* @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).
*/
#define lru_create(ptable, max_slots, mm_ctx_array, mm_ctx) do { \
(void)(((__typeof__((*(ptable))->pdata_t))0) == (void *)0); /* typecheck lru_t */ \
*(ptable) = (__typeof__(*(ptable))) \
lru_create_impl((max_slots), (mm_ctx_array), (mm_ctx)); \
} 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)
/**
* @brief Return pointer to value, inserting if needed (zeroed).
*
* @param table pointer to LRU
* @param key_ lookup key
* @param len_ key lengthkeys
* @return pointer to data or NULL (can be even if memory could be allocated!)
*/
#define lru_get_new(table, key_, len_) \
(__typeof__((table)->pdata_t)) \
lru_get_impl(&(table)->lru, (key_), (len_), sizeof(*(table)->pdata_t), true)
/**
* @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)
/** @brief Round the value up to a multiple of (1 << power). */
static inline uint round_power(uint size, uint power)
{
uint res = ((size - 1) & ~((1 << power) - 1)) + (1 << power);
assert(__builtin_ctz(res) >= power);
assert(size <= res && res < size + (1 << power));
return res;
}
/* ======================== 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, 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);
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. */
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)
{
assert(lru);
return (1 << lru->log_groups) * LRU_ASSOC;
}
/** @endcond */
/** @} (addtogroup generics) */
|