[thirdparty/squid.git] / src / repl / heap / store_repl_heap.cc


/*
 * $Id: store_repl_heap.cc,v 1.1 2000/06/08 18:05:40 hno Exp $
 *
 * DEBUG: section ?     HEAP based removal policies
 * AUTHOR: Henrik Nordstrom
 *
 * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
 * ----------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from the
 *  Internet community.  Development is led by Duane Wessels of the
 *  National Laboratory for Applied Network Research and funded by the
 *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
 *  Duane Wessels and the University of California San Diego.  Please
 *  see the COPYRIGHT file for full details.  Squid incorporates
 *  software developed and/or copyrighted by other sources.  Please see
 *  the CREDITS file for full details.
 *
 *  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 2 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, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *
 */

#include "squid.h"
#include "heap.h"
#include "store_heap_replacement.h"

REMOVALPOLICYCREATE createRemovalPolicy_heap;

static int nr_heap_policies = 0;

typedef struct _HeapPolicyData HeapPolicyData;
struct _HeapPolicyData {
    RemovalPolicy *policy;
    heap *heap;
    heap_key_func *keyfunc;
    int count;
    int nwalkers;
    enum heap_entry_type
    { TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM }
    type;
};

/* Hack to avoid having to remember the RemovalPolicyNode location.
 * Needed by the purge walker.
 */
static enum heap_entry_type
heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
{
    if (node == &entry->repl)
	return TYPE_STORE_ENTRY;
    if (entry->mem_obj && node == &entry->mem_obj->repl)
	return TYPE_STORE_MEM;
    fatal("Heap Replacement: Unknown StoreEntry node type");
    return TYPE_UNKNOWN;
}
#define SET_POLICY_NODE(entry,value) \
    switch(heap->type) { \
    case TYPE_STORE_ENTRY: entry->repl.data = value; break ; \
    case TYPE_STORE_MEM: entry->mem_obj->repl.data = value ; break ; \
    default: break; \
    }

static void
heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
{
    HeapPolicyData *heap = policy->_data;
    assert(!node->data);
    if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
	return; /* We won't manage these.. they messes things up */
    node->data = heap_insert(heap->heap, entry);
    heap->count += 1;
    if (!heap->type)
	heap->type = heap_guessType(entry, node);
    /* Add a little more variance to the aging factor */
    heap->heap->age += heap->heap->age / 100000000;
}

static void
heap_remove(RemovalPolicy * policy, StoreEntry * entry,
    RemovalPolicyNode * node)
{
    HeapPolicyData *heap = policy->_data;
    heap_node *hnode = node->data;
    if (!hnode)
	return;
    heap_delete(heap->heap, hnode);
    node->data = NULL;
    heap->count -= 1;
}

static void
heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
    RemovalPolicyNode * node)
{
    HeapPolicyData *heap = policy->_data;
    heap_node *hnode = node->data;
    if (!hnode)
	return;
    heap_update(heap->heap, hnode, (StoreEntry *) entry);
}

/** RemovalPolicyWalker **/

typedef struct _HeapWalkData HeapWalkData;
struct _HeapWalkData
{
    int current;
};

const StoreEntry *
heap_walkNext(RemovalPolicyWalker * walker)
{
    HeapWalkData *heap_walk = walker->_data;
    RemovalPolicy *policy = walker->_policy;
    HeapPolicyData *heap = policy->_data;
    StoreEntry *entry;
    if (heap_walk->current >= heap_nodes(heap->heap))
	return NULL;		/* done */
    entry = (StoreEntry *) heap_peep(heap->heap, heap_walk->current++);
    return entry;
}

static void
heap_walkDone(RemovalPolicyWalker * walker)
{
    RemovalPolicy *policy = walker->_policy;
    HeapPolicyData *heap = policy->_data;
    assert(strcmp(policy->_type, "heap") == 0);
    assert(heap->nwalkers > 0);
    heap->nwalkers -= 1;
    safe_free(walker->_data);
    cbdataFree(walker);
}

static RemovalPolicyWalker *
heap_walkInit(RemovalPolicy * policy)
{
    HeapPolicyData *heap = policy->_data;
    RemovalPolicyWalker *walker;
    HeapWalkData *heap_walk;
    heap->nwalkers += 1;
    walker = xcalloc(1, sizeof(*walker));
    heap_walk = xcalloc(1, sizeof(*heap_walk));
    heap_walk->current = 0;
    walker->_policy = policy;
    walker->_data = heap_walk;
    walker->Next = heap_walkNext;
    walker->Done = heap_walkDone;
    cbdataAdd(walker, cbdataXfree, 0);
    return walker;
}

/** RemovalPurgeWalker **/

typedef struct _HeapPurgeData HeapPurgeData;
struct _HeapPurgeData
{
    link_list *locked_entries;
    heap_key min_age;
};

static StoreEntry *
heap_purgeNext(RemovalPurgeWalker * walker)
{
    HeapPurgeData *heap_walker = walker->_data;
    RemovalPolicy *policy = walker->_policy;
    HeapPolicyData *heap = policy->_data;
    StoreEntry *entry;
    heap_key age;
  try_again:
    if (!heap_nodes(heap->heap) > 0)
	return NULL;		/* done */
    age = heap_peepminkey(heap->heap);
    entry = heap_extractmin(heap->heap);
    if (storeEntryLocked(entry)) {
	linklistPush(&heap_walker->locked_entries, entry);
	goto try_again;
    }
    heap_walker->min_age = age;
    SET_POLICY_NODE(entry, NULL);
    return entry;
}

static void
heap_purgeDone(RemovalPurgeWalker * walker)
{
    HeapPurgeData *heap_walker = walker->_data;
    RemovalPolicy *policy = walker->_policy;
    HeapPolicyData *heap = policy->_data;
    StoreEntry *entry;
    assert(strcmp(policy->_type, "heap") == 0);
    assert(heap->nwalkers > 0);
    heap->nwalkers -= 1;
    if (heap_walker->min_age > 0) {
	heap->heap->age = heap_walker->min_age;
	debug (81, 3) ("heap_purgeDone: Heap age set to %f\n",
		(double) heap->heap->age);
    }
    /*
     * Reinsert the locked entries
     */
    while ((entry = linklistShift(&heap_walker->locked_entries))) {
	heap_node *node = heap_insert(heap->heap, entry);
	SET_POLICY_NODE(entry, node);
    }
    safe_free(walker->_data);
    cbdataFree(walker);
}

static RemovalPurgeWalker *
heap_purgeInit(RemovalPolicy * policy, int max_scan)
{
    HeapPolicyData *heap = policy->_data;
    RemovalPurgeWalker *walker;
    HeapPurgeData *heap_walk;
    heap->nwalkers += 1;
    walker = xcalloc(1, sizeof(*walker));
    heap_walk = xcalloc(1, sizeof(*heap_walk));
    heap_walk->min_age = 0.0;
    heap_walk->locked_entries = NULL;
    walker->_policy = policy;
    walker->_data = heap_walk;
    walker->max_scan = max_scan;
    walker->Next = heap_purgeNext;
    walker->Done = heap_purgeDone;
    cbdataAdd(walker, cbdataXfree, 0);
#if HEAP_REPLACEMENT_DEBUG
    if (!verify_heap_property(heap->heap)) {
	debug(81, 1) ("Heap property violated!\n");
    }
#endif
    return walker;
}

static void
heap_free(RemovalPolicy * policy)
{
    HeapPolicyData *heap = policy->_data;
    /* Make some verification of the policy state */
    assert(strcmp(policy->_type, "heap") == 0);
    assert(heap->nwalkers);
    assert(heap->count);
    /* Ok, time to destroy this policy */
    safe_free(policy->_data);
    memset(policy, 0, sizeof(*policy));
    cbdataFree(policy);
}

RemovalPolicy *
createRemovalPolicy_heap(wordlist * args)
{
    RemovalPolicy *policy;
    HeapPolicyData *heap_data;
    char *keytype;
    /* Allocate the needed structures */
    policy = xcalloc(1, sizeof(*policy));
    heap_data = xcalloc(1, sizeof(*heap_data));
    /* cbdata register the policy */
    cbdataAdd(policy, cbdataXfree, 0);
    /* Initialize the policy data */
    heap_data->policy = policy;
    if (args) {
	keytype = args->key;
	args = args->next;
    } else {
	debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
	keytype = "LRU";
    }
    if (!strcmp(keytype, "GDSF"))
	heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
    else if (!strcmp(keytype, "LFUDA"))
	heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
    else if (!strcmp(keytype, "LRU"))
	heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
    else {
	debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
	    keytype);
	heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
    }
    /* No additional arguments expected */
    assert(!args);
    heap_data->heap = new_heap(1000, heap_data->keyfunc);
    heap_data->heap->age = 1.0;
    /* Populate the policy structure */
    policy->_type = "heap";
    policy->_data = heap_data;
    policy->Free = heap_free;
    policy->Add = heap_add;
    policy->Remove = heap_remove;
    policy->Referenced = NULL;
    policy->Dereferenced = heap_referenced;
    policy->WalkInit = heap_walkInit;
    policy->PurgeInit = heap_purgeInit;
    /* Increase policy usage count */
    nr_heap_policies += 0;
    return policy;
}
Commit	Line	Data
6a566b9c	1
	2	/*
	3	* $Id: store_repl_heap.cc,v 1.1 2000/06/08 18:05:40 hno Exp $
	4	*
	5	* DEBUG: section ? HEAP based removal policies
	6	* AUTHOR: Henrik Nordstrom
	7	*
	8	* SQUID Internet Object Cache http://squid.nlanr.net/Squid/
	9	* ----------------------------------------------------------
	10	*
	11	* Squid is the result of efforts by numerous individuals from the
	12	* Internet community. Development is led by Duane Wessels of the
	13	* National Laboratory for Applied Network Research and funded by the
	14	* National Science Foundation. Squid is Copyrighted (C) 1998 by
	15	* Duane Wessels and the University of California San Diego. Please
	16	* see the COPYRIGHT file for full details. Squid incorporates
	17	* software developed and/or copyrighted by other sources. Please see
	18	* the CREDITS file for full details.
	19	*
	20	* This program is free software; you can redistribute it and/or modify
	21	* it under the terms of the GNU General Public License as published by
	22	* the Free Software Foundation; either version 2 of the License, or
	23	* (at your option) any later version.
	24	*
	25	* This program is distributed in the hope that it will be useful,
	26	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	27	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	28	* GNU General Public License for more details.
	29	*
	30	* You should have received a copy of the GNU General Public License
	31	* along with this program; if not, write to the Free Software
	32	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
	33	*
	34	*/
	35
	36	#include "squid.h"
	37	#include "heap.h"
	38	#include "store_heap_replacement.h"
	39
	40	REMOVALPOLICYCREATE createRemovalPolicy_heap;
	41
	42	static int nr_heap_policies = 0;
	43
	44	typedef struct _HeapPolicyData HeapPolicyData;
	45	struct _HeapPolicyData {
	46	RemovalPolicy *policy;
	47	heap *heap;
	48	heap_key_func *keyfunc;
	49	int count;
	50	int nwalkers;
	51	enum heap_entry_type
	52	{ TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM }
	53	type;
	54	};
	55
	56	/* Hack to avoid having to remember the RemovalPolicyNode location.
	57	* Needed by the purge walker.
	58	*/
	59	static enum heap_entry_type
	60	heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
	61	{
	62	if (node == &entry->repl)
	63	return TYPE_STORE_ENTRY;
	64	if (entry->mem_obj && node == &entry->mem_obj->repl)
65	return TYPE_STORE_MEM;
66	fatal("Heap Replacement: Unknown StoreEntry node type");
67	return TYPE_UNKNOWN;
68	}
69	#define SET_POLICY_NODE(entry,value) \
70	switch(heap->type) { \
71	case TYPE_STORE_ENTRY: entry->repl.data = value; break ; \
72	case TYPE_STORE_MEM: entry->mem_obj->repl.data = value ; break ; \
73	default: break; \
74	}
75
76	static void
77	heap_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node)
78	{
79	HeapPolicyData *heap = policy->_data;
80	assert(!node->data);
81	if (EBIT_TEST(entry->flags, ENTRY_SPECIAL))
82	return; /* We won't manage these.. they messes things up */
83	node->data = heap_insert(heap->heap, entry);
84	heap->count += 1;
85	if (!heap->type)
86	heap->type = heap_guessType(entry, node);
87	/* Add a little more variance to the aging factor */
88	heap->heap->age += heap->heap->age / 100000000;
89	}
90
91	static void
92	heap_remove(RemovalPolicy * policy, StoreEntry * entry,
93	RemovalPolicyNode * node)
94	{
95	HeapPolicyData *heap = policy->_data;
96	heap_node *hnode = node->data;
97	if (!hnode)
98	return;
99	heap_delete(heap->heap, hnode);
100	node->data = NULL;
101	heap->count -= 1;
102	}
103
104	static void
105	heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
106	RemovalPolicyNode * node)
107	{
108	HeapPolicyData *heap = policy->_data;
109	heap_node *hnode = node->data;
110	if (!hnode)
111	return;
112	heap_update(heap->heap, hnode, (StoreEntry *) entry);
113	}
114
115	/ RemovalPolicyWalker /
116
117	typedef struct _HeapWalkData HeapWalkData;
118	struct _HeapWalkData
119	{
120	int current;
121	};
122
123	const StoreEntry *
124	heap_walkNext(RemovalPolicyWalker * walker)
125	{
126	HeapWalkData *heap_walk = walker->_data;
127	RemovalPolicy *policy = walker->_policy;
128	HeapPolicyData *heap = policy->_data;
129	StoreEntry *entry;
130	if (heap_walk->current >= heap_nodes(heap->heap))
131	return NULL; /* done */
132	entry = (StoreEntry *) heap_peep(heap->heap, heap_walk->current++);
133	return entry;
134	}
135
136	static void
137	heap_walkDone(RemovalPolicyWalker * walker)
138	{
139	RemovalPolicy *policy = walker->_policy;
140	HeapPolicyData *heap = policy->_data;
141	assert(strcmp(policy->_type, "heap") == 0);
142	assert(heap->nwalkers > 0);
143	heap->nwalkers -= 1;
144	safe_free(walker->_data);
145	cbdataFree(walker);
146	}
147
148	static RemovalPolicyWalker *
149	heap_walkInit(RemovalPolicy * policy)
150	{
151	HeapPolicyData *heap = policy->_data;
152	RemovalPolicyWalker *walker;
153	HeapWalkData *heap_walk;
154	heap->nwalkers += 1;
155	walker = xcalloc(1, sizeof(*walker));
156	heap_walk = xcalloc(1, sizeof(*heap_walk));
157	heap_walk->current = 0;
158	walker->_policy = policy;
159	walker->_data = heap_walk;
160	walker->Next = heap_walkNext;
161	walker->Done = heap_walkDone;
162	cbdataAdd(walker, cbdataXfree, 0);
163	return walker;
164	}
165
166	/ RemovalPurgeWalker /
167
168	typedef struct _HeapPurgeData HeapPurgeData;
169	struct _HeapPurgeData
170	{
171	link_list *locked_entries;
172	heap_key min_age;
173	};
174
175	static StoreEntry *
176	heap_purgeNext(RemovalPurgeWalker * walker)
177	{
178	HeapPurgeData *heap_walker = walker->_data;
179	RemovalPolicy *policy = walker->_policy;
180	HeapPolicyData *heap = policy->_data;
181	StoreEntry *entry;
182	heap_key age;
183	try_again:
184	if (!heap_nodes(heap->heap) > 0)
185	return NULL; /* done */
186	age = heap_peepminkey(heap->heap);
187	entry = heap_extractmin(heap->heap);
188	if (storeEntryLocked(entry)) {
189	linklistPush(&heap_walker->locked_entries, entry);
190	goto try_again;
191	}
192	heap_walker->min_age = age;
193	SET_POLICY_NODE(entry, NULL);
194	return entry;
195	}
196
197	static void
198	heap_purgeDone(RemovalPurgeWalker * walker)
199	{
200	HeapPurgeData *heap_walker = walker->_data;
201	RemovalPolicy *policy = walker->_policy;
202	HeapPolicyData *heap = policy->_data;
203	StoreEntry *entry;
204	assert(strcmp(policy->_type, "heap") == 0);
205	assert(heap->nwalkers > 0);
206	heap->nwalkers -= 1;
207	if (heap_walker->min_age > 0) {
208	heap->heap->age = heap_walker->min_age;
209	debug (81, 3) ("heap_purgeDone: Heap age set to %f\n",
210	(double) heap->heap->age);
211	}
212	/*
213	* Reinsert the locked entries
214	*/
215	while ((entry = linklistShift(&heap_walker->locked_entries))) {
216	heap_node *node = heap_insert(heap->heap, entry);
217	SET_POLICY_NODE(entry, node);
218	}
219	safe_free(walker->_data);
220	cbdataFree(walker);
221	}
222
223	static RemovalPurgeWalker *
224	heap_purgeInit(RemovalPolicy * policy, int max_scan)
225	{
226	HeapPolicyData *heap = policy->_data;
227	RemovalPurgeWalker *walker;
228	HeapPurgeData *heap_walk;
229	heap->nwalkers += 1;
230	walker = xcalloc(1, sizeof(*walker));
231	heap_walk = xcalloc(1, sizeof(*heap_walk));
232	heap_walk->min_age = 0.0;
233	heap_walk->locked_entries = NULL;
234	walker->_policy = policy;
235	walker->_data = heap_walk;
236	walker->max_scan = max_scan;
237	walker->Next = heap_purgeNext;
238	walker->Done = heap_purgeDone;
239	cbdataAdd(walker, cbdataXfree, 0);
240	#if HEAP_REPLACEMENT_DEBUG
241	if (!verify_heap_property(heap->heap)) {
242	debug(81, 1) ("Heap property violated!\n");
243	}
244	#endif
245	return walker;
246	}
247
248	static void
249	heap_free(RemovalPolicy * policy)
250	{
251	HeapPolicyData *heap = policy->_data;
252	/* Make some verification of the policy state */
253	assert(strcmp(policy->_type, "heap") == 0);
254	assert(heap->nwalkers);
255	assert(heap->count);
256	/* Ok, time to destroy this policy */
257	safe_free(policy->_data);
258	memset(policy, 0, sizeof(*policy));
259	cbdataFree(policy);
260	}
261
262	RemovalPolicy *
263	createRemovalPolicy_heap(wordlist * args)
264	{
265	RemovalPolicy *policy;
266	HeapPolicyData *heap_data;
267	char *keytype;
268	/* Allocate the needed structures */
269	policy = xcalloc(1, sizeof(*policy));
270	heap_data = xcalloc(1, sizeof(*heap_data));
271	/* cbdata register the policy */
272	cbdataAdd(policy, cbdataXfree, 0);
273	/* Initialize the policy data */
274	heap_data->policy = policy;
275	if (args) {
276	keytype = args->key;
277	args = args->next;
278	} else {
279	debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
280	keytype = "LRU";
281	}
282	if (!strcmp(keytype, "GDSF"))
283	heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
284	else if (!strcmp(keytype, "LFUDA"))
285	heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
286	else if (!strcmp(keytype, "LRU"))
287	heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
288	else {
289	debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
290	keytype);
291	heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
292	}
293	/* No additional arguments expected */
294	assert(!args);
295	heap_data->heap = new_heap(1000, heap_data->keyfunc);
296	heap_data->heap->age = 1.0;
297	/* Populate the policy structure */
298	policy->_type = "heap";
299	policy->_data = heap_data;
300	policy->Free = heap_free;
301	policy->Add = heap_add;
302	policy->Remove = heap_remove;
303	policy->Referenced = NULL;
304	policy->Dereferenced = heap_referenced;
305	policy->WalkInit = heap_walkInit;
306	policy->PurgeInit = heap_purgeInit;
307	/* Increase policy usage count */
308	nr_heap_policies += 0;
309	return policy;
310	}