From da76459dc21b5af2449af2d36eb95226cb186ce2 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:35:11 +0200 Subject: Adding upstream version 2.6.12. Signed-off-by: Daniel Baumann --- src/lru.c | 305 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 305 insertions(+) create mode 100644 src/lru.c (limited to 'src/lru.c') diff --git a/src/lru.c b/src/lru.c new file mode 100644 index 0000000..07ef50c --- /dev/null +++ b/src/lru.c @@ -0,0 +1,305 @@ +/* + * Copyright (C) 2015 Willy Tarreau + * + * 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 + +/* Minimal list manipulation macros for lru64_list */ +#define LIST_INSERT(lh, el) ({ (el)->n = (lh)->n; (el)->n->p = (lh)->n = (el); (el)->p = (lh); }) +#define LIST_DELETE(el) ({ (el)->n->p = (el)->p; (el)->p->n = (el)->n; }) + + +/* Lookup key in LRU cache for use with domain whose data's + * current version is . It differs from lru64_get as it does not + * create missing keys. The function returns NULL if an error or a cache miss + * occurs. */ +struct lru64 *lru64_lookup(unsigned long long key, struct lru64_head *lru, + void *domain, unsigned long long revision) +{ + struct eb64_node *node; + struct lru64 *elem; + + node = __eb64_lookup(&lru->keys, key); + elem = container_of(node, typeof(*elem), node); + if (elem) { + /* Existing entry found, check validity then move it at the + * head of the LRU list. + */ + if (elem->domain == domain && elem->revision == revision) { + LIST_DELETE(&elem->lru); + LIST_INSERT(&lru->list, &elem->lru); + return elem; + } + } + return NULL; +} + +/* Get key from LRU cache for use with domain whose data's + * current revision is . If the key doesn't exist it's first created + * with ->domain = NULL. The caller detects this situation by checking ->domain + * and must perform the operation to be cached then call lru64_commit() to + * complete the operation. A lock (mutex or spinlock) may be added around the + * function to permit use in a multi-threaded environment. The function may + * return NULL upon memory allocation failure. + */ +struct lru64 *lru64_get(unsigned long long key, struct lru64_head *lru, + void *domain, unsigned long long revision) +{ + struct eb64_node *node; + struct lru64 *elem; + + if (!lru->spare) { + if (!lru->cache_size) + return NULL; + lru->spare = malloc(sizeof(*lru->spare)); + if (!lru->spare) + return NULL; + lru->spare->domain = NULL; + } + + /* Lookup or insert */ + lru->spare->node.key = key; + node = __eb64_insert(&lru->keys, &lru->spare->node); + elem = container_of(node, typeof(*elem), node); + + if (elem != lru->spare) { + /* Existing entry found, check validity then move it at the + * head of the LRU list. + */ + if (elem->domain == domain && elem->revision == revision) { + LIST_DELETE(&elem->lru); + LIST_INSERT(&lru->list, &elem->lru); + return elem; + } + + if (!elem->domain) + return NULL; // currently locked + + /* recycle this entry */ + LIST_DELETE(&elem->lru); + } + else { + /* New entry inserted, initialize and move to the head of the + * LRU list, and lock it until commit. + */ + lru->cache_usage++; + lru->spare = NULL; // used, need a new one next time + } + + elem->domain = NULL; + LIST_INSERT(&lru->list, &elem->lru); + + if (lru->cache_usage > lru->cache_size) { + /* try to kill oldest entry */ + struct lru64 *old; + + old = container_of(lru->list.p, typeof(*old), lru); + if (old->domain) { + /* not locked */ + LIST_DELETE(&old->lru); + __eb64_delete(&old->node); + if (old->data && old->free) + old->free(old->data); + if (!lru->spare) + lru->spare = old; + else { + free(old); + } + lru->cache_usage--; + } + } + return elem; +} + +/* Commit element with data , domain and revision + * . is checked for NULL so that it's possible to call it + * with the result from a call to lru64_get(). The caller might lock it using a + * spinlock or mutex shared with the one around lru64_get(). + */ +void lru64_commit(struct lru64 *elem, void *data, void *domain, + unsigned long long revision, void (*free)(void *)) +{ + if (!elem) + return; + + elem->data = data; + elem->revision = revision; + elem->domain = domain; + elem->free = free; +} + +/* Create a new LRU cache of entries. Returns the new cache or NULL in + * case of allocation failure. + */ +struct lru64_head *lru64_new(int size) +{ + struct lru64_head *lru; + + lru = malloc(sizeof(*lru)); + if (lru) { + lru->list.p = lru->list.n = &lru->list; + lru->keys = EB_ROOT_UNIQUE; + lru->spare = NULL; + lru->cache_size = size; + lru->cache_usage = 0; + } + return lru; +} + +/* Tries to destroy the LRU cache . Returns the number of locked entries + * that prevent it from being destroyed, or zero meaning everything was done. + */ +int lru64_destroy(struct lru64_head *lru) +{ + struct lru64 *elem, *next; + + if (!lru) + return 0; + + elem = container_of(lru->list.p, typeof(*elem), lru); + while (&elem->lru != &lru->list) { + next = container_of(elem->lru.p, typeof(*next), lru); + if (elem->domain) { + /* not locked */ + LIST_DELETE(&elem->lru); + eb64_delete(&elem->node); + if (elem->data && elem->free) + elem->free(elem->data); + free(elem); + lru->cache_usage--; + lru->cache_size--; + } + elem = next; + } + + if (lru->cache_usage) + return lru->cache_usage; + + free(lru); + return 0; +} + +/* kill the least used entries from the cache */ +void lru64_kill_oldest(struct lru64_head *lru, unsigned long int nb) +{ + struct lru64 *elem, *next; + + for (elem = container_of(lru->list.p, typeof(*elem), lru); + nb && (&elem->lru != &lru->list); + elem = next) { + next = container_of(elem->lru.p, typeof(*next), lru); + if (!elem->domain) + continue; /* locked entry */ + + LIST_DELETE(&elem->lru); + eb64_delete(&elem->node); + if (elem->data && elem->free) + elem->free(elem->data); + if (!lru->spare) + lru->spare = elem; + else + free(elem); + lru->cache_usage--; + nb--; + } +} + +/* The code below is just for validation and performance testing. It's an + * example of a function taking some time to return results that could be + * cached. + */ +#ifdef STANDALONE + +#include + +static unsigned int misses; + +static unsigned long long sum(unsigned long long x) +{ +#ifndef TEST_LRU_FAST_OPERATION + if (x < 1) + return 0; + return x + sum(x * 99 / 100 - 1); +#else + return (x << 16) - (x << 8) - 1; +#endif +} + +static long get_value(struct lru64_head *lru, long a) +{ + struct lru64 *item = NULL; + + if (lru) { + item = lru64_get(a, lru, lru, 0); + if (item && item->domain) + return (long)item->data; + } + misses++; + /* do the painful work here */ + a = sum(a); + if (item) + lru64_commit(item, (void *)a, lru, 1, 0); + return a; +} + +static inline unsigned int statistical_prng() +{ + static unsigned int statistical_prng_state = 0x12345678; + unsigned int x = statistical_prng_state; + + x ^= x << 13; + x ^= x >> 17; + x ^= x << 5; + return statistical_prng_state = x; +} + +/* pass #of loops in argv[1] and set argv[2] to something to use the LRU */ +int main(int argc, char **argv) +{ + struct lru64_head *lru = NULL; + long long ret; + int total, loops; + + if (argc < 2) { + printf("Need a number of rounds and optionally an LRU cache size (0..65536)\n"); + exit(1); + } + + total = atoi(argv[1]); + + if (argc > 2) /* cache size */ + lru = lru64_new(atoi(argv[2])); + + ret = 0; + for (loops = 0; loops < total; loops++) { + ret += get_value(lru, statistical_prng() & 65535); + } + /* just for accuracy control */ + printf("ret=%llx, hits=%u, misses=%u (%d %% hits)\n", ret, (unsigned)(total-misses), misses, (int)((float)(total-misses) * 100.0 / total)); + + while (lru64_destroy(lru)); + + return 0; +} + +#endif -- cgit v1.2.3