src/lru.c - haproxy - Gitiles

 /*
  * Copyright (C) 2015 Willy Tarreau <w@1wt.eu>
  *
  * 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 <import/lru.h>

 /* 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 <key> in LRU cache <lru> for use with domain <domain> whose data's
  * current version is <revision>. 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 <key> from LRU cache <lru> for use with domain <domain> whose data's
  * current revision is <revision>. 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 <elem> with data <data>, domain <domain> and revision
  * <revision>.  <elem> 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 <size> 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 <lru>. 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 <nb> least used entries from the <lru> 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 <stdio.h>

 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=%d, misses=%d (%d %% hits)\n", ret, total-misses, misses, (int)((float)(total-misses) * 100.0 / total));

 	while (lru64_destroy(lru));

 	return 0;
 }

 #endif
	/*
	* Copyright (C) 2015 Willy Tarreau <w@1wt.eu>
	*
	* 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 <import/lru.h>

	/* 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 <key> in LRU cache <lru> for use with domain <domain> whose data's
	* current version is <revision>. 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 <key> from LRU cache <lru> for use with domain <domain> whose data's
	* current revision is <revision>. 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 <elem> with data <data>, domain <domain> and revision
	* <revision>. <elem> 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 <size> 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 <lru>. 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 <nb> least used entries from the <lru> 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 <stdio.h>

	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=%d, misses=%d (%d %% hits)\n", ret, total-misses, misses, (int)((float)(total-misses) * 100.0 / total));

	while (lru64_destroy(lru));

	return 0;
	}

	#endif