1 files changed, 590 insertions, 0 deletions

diff --git a/usr.sbin/nscd/cacheplcs.c b/usr.sbin/nscd/cacheplcs.c
new file mode 100644
index 000000000000..a7ee38de4801
--- /dev/null
+++ b/usr.sbin/nscd/cacheplcs.c
@@ -0,0 +1,590 @@
+/*-
+ * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <assert.h>
+#include <string.h>
+#include "cacheplcs.h"
+#include "debug.h"
+
+static void cache_fifo_policy_update_item(struct cache_policy_ *,
+	struct cache_policy_item_ *);
+static void cache_lfu_policy_add_item(struct cache_policy_ *,
+	struct cache_policy_item_ *);
+static struct cache_policy_item_ * cache_lfu_policy_create_item(void);
+static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *);
+static struct cache_policy_item_ *cache_lfu_policy_get_first_item(
+	struct cache_policy_ *);
+static struct cache_policy_item_ *cache_lfu_policy_get_last_item(
+	struct cache_policy_ *);
+static struct cache_policy_item_ *cache_lfu_policy_get_next_item(
+	struct cache_policy_ *, struct cache_policy_item_ *);
+static struct cache_policy_item_ *cache_lfu_policy_get_prev_item(
+	struct cache_policy_ *, struct cache_policy_item_ *);
+static void cache_lfu_policy_remove_item(struct cache_policy_ *,
+	struct cache_policy_item_ *);
+static void cache_lfu_policy_update_item(struct cache_policy_ *,
+	struct cache_policy_item_ *);
+static void cache_lru_policy_update_item(struct cache_policy_ *,
+	struct cache_policy_item_ *);
+static void cache_queue_policy_add_item(struct cache_policy_ *,
+	struct cache_policy_item_ *);
+static struct cache_policy_item_ * cache_queue_policy_create_item();
+static void cache_queue_policy_destroy_item(struct cache_policy_item_ *);
+static struct cache_policy_item_ *cache_queue_policy_get_first_item(
+	struct cache_policy_ *);
+static struct cache_policy_item_ *cache_queue_policy_get_last_item(
+	struct cache_policy_ *);
+static struct cache_policy_item_ *cache_queue_policy_get_next_item(
+	struct cache_policy_ *, struct cache_policy_item_ *);
+static struct cache_policy_item_ *cache_queue_policy_get_prev_item(
+	struct cache_policy_ *, struct cache_policy_item_ *);
+static void cache_queue_policy_remove_item(struct cache_policy_ *,
+	struct cache_policy_item_ *);
+static void destroy_cache_queue_policy(struct cache_queue_policy_ *);
+static struct cache_queue_policy_ *init_cache_queue_policy(void);
+
+/*
+ * All cache_queue_policy_XXX functions below will be used to fill
+ * the cache_queue_policy structure. They implement the most functionality of
+ * LRU and FIFO policies. LRU and FIFO policies are actually the
+ * cache_queue_policy_ with cache_update_item function changed.
+ */
+static struct cache_policy_item_ *
+cache_queue_policy_create_item()
+{
+	struct cache_queue_policy_item_ *retval;
+
+	TRACE_IN(cache_queue_policy_create_item);
+	retval = (struct cache_queue_policy_item_ *)malloc(
+		sizeof(struct cache_queue_policy_item_));
+	assert(retval != NULL);
+	memset(retval, 0, sizeof(struct cache_queue_policy_item_));
+
+	TRACE_OUT(cache_queue_policy_create_item);
+	return ((struct cache_policy_item_ *)retval);
+}
+
+static void
+cache_queue_policy_destroy_item(struct cache_policy_item_ *item)
+{
+
+	TRACE_IN(cache_queue_policy_destroy_item);
+	assert(item != NULL);
+	free(item);
+	TRACE_OUT(cache_queue_policy_destroy_item);
+}
+
+static void
+cache_queue_policy_add_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_queue_policy_ *queue_policy;
+	struct cache_queue_policy_item_ *queue_item;
+
+	TRACE_IN(cache_queue_policy_add_item);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	queue_item = (struct cache_queue_policy_item_ *)item;
+	TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
+	TRACE_OUT(cache_queue_policy_add_item);
+}
+
+static void
+cache_queue_policy_remove_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_queue_policy_ *queue_policy;
+	struct cache_queue_policy_item_	*queue_item;
+
+	TRACE_IN(cache_queue_policy_remove_item);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	queue_item = (struct cache_queue_policy_item_ *)item;
+	TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
+	TRACE_OUT(cache_queue_policy_remove_item);
+}
+
+static struct cache_policy_item_ *
+cache_queue_policy_get_first_item(struct cache_policy_ *policy)
+{
+	struct cache_queue_policy_ *queue_policy;
+
+	TRACE_IN(cache_queue_policy_get_first_item);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	TRACE_OUT(cache_queue_policy_get_first_item);
+	return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head));
+}
+
+static struct cache_policy_item_ *
+cache_queue_policy_get_last_item(struct cache_policy_ *policy)
+{
+	struct cache_queue_policy_ *queue_policy;
+
+	TRACE_IN(cache_queue_policy_get_last_item);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	TRACE_OUT(cache_queue_policy_get_last_item);
+	return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head,
+		cache_queue_policy_head_));
+}
+
+static struct cache_policy_item_ *
+cache_queue_policy_get_next_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_queue_policy_ *queue_policy;
+	struct cache_queue_policy_item_	*queue_item;
+
+	TRACE_IN(cache_queue_policy_get_next_item);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	queue_item = (struct cache_queue_policy_item_ *)item;
+
+	TRACE_OUT(cache_queue_policy_get_next_item);
+	return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries));
+}
+
+static struct cache_policy_item_ *
+cache_queue_policy_get_prev_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_queue_policy_ *queue_policy;
+	struct cache_queue_policy_item_	*queue_item;
+
+	TRACE_IN(cache_queue_policy_get_prev_item);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	queue_item = (struct cache_queue_policy_item_ *)item;
+
+	TRACE_OUT(cache_queue_policy_get_prev_item);
+	return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item,
+		cache_queue_policy_head_, entries));
+}
+
+/*
+ * Initializes cache_queue_policy_ by filling the structure with the functions
+ * pointers, defined above
+ */
+static struct cache_queue_policy_ *
+init_cache_queue_policy(void)
+{
+	struct cache_queue_policy_	*retval;
+
+	TRACE_IN(init_cache_queue_policy);
+	retval = (struct cache_queue_policy_ *)malloc(
+		sizeof(struct cache_queue_policy_));
+	assert(retval != NULL);
+	memset(retval, 0, sizeof(struct cache_queue_policy_));
+
+	retval->parent_data.create_item_func = cache_queue_policy_create_item;
+	retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item;
+
+	retval->parent_data.add_item_func = cache_queue_policy_add_item;
+	retval->parent_data.remove_item_func = cache_queue_policy_remove_item;
+
+	retval->parent_data.get_first_item_func =
+		cache_queue_policy_get_first_item;
+	retval->parent_data.get_last_item_func =
+		cache_queue_policy_get_last_item;
+	retval->parent_data.get_next_item_func =
+		cache_queue_policy_get_next_item;
+	retval->parent_data.get_prev_item_func =
+		cache_queue_policy_get_prev_item;
+
+	TAILQ_INIT(&retval->head);
+	TRACE_OUT(init_cache_queue_policy);
+	return (retval);
+}
+
+static void
+destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy)
+{
+	struct cache_queue_policy_item_	*queue_item;
+
+	TRACE_IN(destroy_cache_queue_policy);
+	while (!TAILQ_EMPTY(&queue_policy->head)) {
+		queue_item = TAILQ_FIRST(&queue_policy->head);
+		TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
+		cache_queue_policy_destroy_item(
+			(struct cache_policy_item_ *)queue_item);
+	}
+	free(queue_policy);
+	TRACE_OUT(destroy_cache_queue_policy);
+}
+
+/*
+ * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything,
+ * when the cache element is updated. So it always stays in its initial
+ * position in the queue - that is exactly the FIFO functionality.
+ */
+static void
+cache_fifo_policy_update_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+
+	TRACE_IN(cache_fifo_policy_update_item);
+	/* policy and item arguments are ignored */
+	TRACE_OUT(cache_fifo_policy_update_item);
+}
+
+struct cache_policy_ *
+init_cache_fifo_policy()
+{
+	struct cache_queue_policy_ *retval;
+
+	TRACE_IN(init_cache_fifo_policy);
+	retval = init_cache_queue_policy();
+	retval->parent_data.update_item_func = cache_fifo_policy_update_item;
+
+	TRACE_OUT(init_cache_fifo_policy);
+	return ((struct cache_policy_ *)retval);
+}
+
+void
+destroy_cache_fifo_policy(struct cache_policy_ *policy)
+{
+	struct cache_queue_policy_	*queue_policy;
+
+	TRACE_IN(destroy_cache_fifo_policy);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	destroy_cache_queue_policy(queue_policy);
+	TRACE_OUT(destroy_cache_fifo_policy);
+}
+
+/*
+ * Makes cache_queue_policy_ behave like LRU policy. On each update, cache
+ * element is moved to the end of the queue - so it would be deleted in last
+ * turn. That is exactly the LRU policy functionality.
+ */
+static void
+cache_lru_policy_update_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_queue_policy_ *queue_policy;
+	struct cache_queue_policy_item_ *queue_item;
+
+	TRACE_IN(cache_lru_policy_update_item);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	queue_item = (struct cache_queue_policy_item_ *)item;
+
+	TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
+	TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
+	TRACE_OUT(cache_lru_policy_update_item);
+}
+
+struct cache_policy_ *
+init_cache_lru_policy()
+{
+	struct cache_queue_policy_ *retval;
+
+	TRACE_IN(init_cache_lru_policy);
+	retval = init_cache_queue_policy();
+	retval->parent_data.update_item_func = cache_lru_policy_update_item;
+
+	TRACE_OUT(init_cache_lru_policy);
+	return ((struct cache_policy_ *)retval);
+}
+
+void
+destroy_cache_lru_policy(struct cache_policy_ *policy)
+{
+	struct cache_queue_policy_	*queue_policy;
+
+	TRACE_IN(destroy_cache_lru_policy);
+	queue_policy = (struct cache_queue_policy_ *)policy;
+	destroy_cache_queue_policy(queue_policy);
+	TRACE_OUT(destroy_cache_lru_policy);
+}
+
+/*
+ * LFU (least frequently used) policy implementation differs much from the
+ * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_
+ * functions are implemented specifically for this policy. The idea of this
+ * policy is to represent frequency (real number) as the integer number and
+ * use it as the index in the array. Each array's element is
+ * the list of elements. For example, if we have the 100-elements
+ * array for this policy, the elements with frequency 0.1 (calls per-second)
+ * would be in 10th element of the array.
+ */
+static struct cache_policy_item_ *
+cache_lfu_policy_create_item(void)
+{
+	struct cache_lfu_policy_item_ *retval;
+
+	TRACE_IN(cache_lfu_policy_create_item);
+	retval = (struct cache_lfu_policy_item_ *)malloc(
+		sizeof(struct cache_lfu_policy_item_));
+	assert(retval != NULL);
+	memset(retval, 0, sizeof(struct cache_lfu_policy_item_));
+
+	TRACE_OUT(cache_lfu_policy_create_item);
+	return ((struct cache_policy_item_ *)retval);
+}
+
+static void
+cache_lfu_policy_destroy_item(struct cache_policy_item_ *item)
+{
+
+	TRACE_IN(cache_lfu_policy_destroy_item);
+	assert(item != NULL);
+	free(item);
+	TRACE_OUT(cache_lfu_policy_destroy_item);
+}
+
+/*
+ * When placed in the LFU policy queue for the first time, the maximum
+ * frequency is assigned to the element
+ */
+static void
+cache_lfu_policy_add_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+
+	TRACE_IN(cache_lfu_policy_add_item);
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	lfu_item = (struct cache_lfu_policy_item_ *)item;
+
+	lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1;
+	TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]),
+		lfu_item, entries);
+	TRACE_OUT(cache_lfu_policy_add_item);
+}
+
+/*
+ * On each update the frequency of the element is recalculated and, if it
+ * changed, the element would be moved to the another place in the array.
+ */
+static void
+cache_lfu_policy_update_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+	int index;
+
+	TRACE_IN(cache_lfu_policy_update_item);
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	lfu_item = (struct cache_lfu_policy_item_ *)item;
+
+	/*
+	 * We calculate the square of the request_count to avoid grouping of
+	 * all elements at the start of the array (for example, if array size is
+	 * 100 and most of its elements has frequency below the 0.01, they
+	 * all would be grouped in the first array's position). Other
+	 * techniques should be used here later to ensure, that elements are
+	 * equally distributed  in the array and not grouped in its beginning.
+	 */
+	if (lfu_item->parent_data.last_request_time.tv_sec !=
+		lfu_item->parent_data.creation_time.tv_sec) {
+		index = ((double)lfu_item->parent_data.request_count *
+			(double)lfu_item->parent_data.request_count /
+			(lfu_item->parent_data.last_request_time.tv_sec -
+			    lfu_item->parent_data.creation_time.tv_sec + 1)) *
+			    CACHELIB_MAX_FREQUENCY;
+		if (index >= CACHELIB_MAX_FREQUENCY)
+			index = CACHELIB_MAX_FREQUENCY - 1;
+	} else
+		index = CACHELIB_MAX_FREQUENCY - 1;
+
+	TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
+		entries);
+	lfu_item->frequency = index;
+	TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries);
+
+	TRACE_OUT(cache_lfu_policy_update_item);
+}
+
+static void
+cache_lfu_policy_remove_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+
+	TRACE_IN(cache_lfu_policy_remove_item);
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	lfu_item = (struct cache_lfu_policy_item_ *)item;
+
+	TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
+		entries);
+	TRACE_OUT(cache_lfu_policy_remove_item);
+}
+
+static struct cache_policy_item_ *
+cache_lfu_policy_get_first_item(struct cache_policy_ *policy)
+{
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+	int i;
+
+	TRACE_IN(cache_lfu_policy_get_first_item);
+	lfu_item = NULL;
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
+		if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
+			lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
+			break;
+		}
+
+	TRACE_OUT(cache_lfu_policy_get_first_item);
+	return ((struct cache_policy_item_ *)lfu_item);
+}
+
+static struct cache_policy_item_ *
+cache_lfu_policy_get_last_item(struct cache_policy_ *policy)
+{
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+	int i;
+
+	TRACE_IN(cache_lfu_policy_get_last_item);
+	lfu_item = NULL;
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i)
+		if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
+			lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
+				cache_lfu_policy_group_);
+			break;
+		}
+
+	TRACE_OUT(cache_lfu_policy_get_last_item);
+	return ((struct cache_policy_item_ *)lfu_item);
+}
+
+static struct cache_policy_item_ *
+cache_lfu_policy_get_next_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+	int i;
+
+	TRACE_IN(cache_lfu_policy_get_next_item);
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries);
+	if (lfu_item == NULL)
+	{
+		for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1;
+			i < CACHELIB_MAX_FREQUENCY; ++i) {
+			if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
+			    lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
+			    break;
+			}
+		}
+	}
+
+	TRACE_OUT(cache_lfu_policy_get_next_item);
+	return ((struct cache_policy_item_ *)lfu_item);
+}
+
+static struct cache_policy_item_ *
+cache_lfu_policy_get_prev_item(struct cache_policy_ *policy,
+	struct cache_policy_item_ *item)
+{
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+	int i;
+
+	TRACE_IN(cache_lfu_policy_get_prev_item);
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item,
+		cache_lfu_policy_group_, entries);
+	if (lfu_item == NULL)
+	{
+		for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1;
+			i >= 0; --i)
+			if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
+				lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
+					cache_lfu_policy_group_);
+				break;
+		}
+	}
+
+	TRACE_OUT(cache_lfu_policy_get_prev_item);
+	return ((struct cache_policy_item_ *)lfu_item);
+}
+
+/*
+ * Initializes the cache_policy_ structure by filling it with appropriate
+ * functions pointers
+ */
+struct cache_policy_ *
+init_cache_lfu_policy()
+{
+	int i;
+	struct cache_lfu_policy_ *retval;
+
+	TRACE_IN(init_cache_lfu_policy);
+	retval = (struct cache_lfu_policy_ *)malloc(
+		sizeof(struct cache_lfu_policy_));
+	assert(retval != NULL);
+	memset(retval, 0, sizeof(struct cache_lfu_policy_));
+
+	retval->parent_data.create_item_func = cache_lfu_policy_create_item;
+	retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item;
+
+	retval->parent_data.add_item_func = cache_lfu_policy_add_item;
+	retval->parent_data.update_item_func = cache_lfu_policy_update_item;
+	retval->parent_data.remove_item_func = cache_lfu_policy_remove_item;
+
+	retval->parent_data.get_first_item_func =
+		cache_lfu_policy_get_first_item;
+	retval->parent_data.get_last_item_func =
+		cache_lfu_policy_get_last_item;
+	retval->parent_data.get_next_item_func =
+		cache_lfu_policy_get_next_item;
+	retval->parent_data.get_prev_item_func =
+		cache_lfu_policy_get_prev_item;
+
+	for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
+		TAILQ_INIT(&(retval->groups[i]));
+
+	TRACE_OUT(init_cache_lfu_policy);
+	return ((struct cache_policy_ *)retval);
+}
+
+void
+destroy_cache_lfu_policy(struct cache_policy_ *policy)
+{
+	int i;
+	struct cache_lfu_policy_ *lfu_policy;
+	struct cache_lfu_policy_item_ *lfu_item;
+
+	TRACE_IN(destroy_cache_lfu_policy);
+	lfu_policy = (struct cache_lfu_policy_ *)policy;
+	for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) {
+		while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
+			lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
+			TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item,
+				entries);
+			cache_lfu_policy_destroy_item(
+				(struct cache_policy_item_ *)lfu_item);
+		}
+	}
+	free(policy);
+	TRACE_OUT(destroy_cache_lfu_policy);
+}