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


/*
 * $Id: store_repl_heap.cc,v 1.7 2001/03/14 22:28:44 wessels Exp $
 *
 * DEBUG: section ?     HEAP based removal policies
 * AUTHOR: Henrik Nordstrom
 *
 * SQUID Web Proxy Cache          http://www.squid-cache.org/
 * ----------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from
 *  the Internet community; see the CONTRIBUTORS file for full
 *  details.   Many organizations have provided support for Squid's
 *  development; see the SPONSORS file for full details.  Squid is
 *  Copyrighted (C) 2001 by the Regents of the University of
 *  California; see the COPYRIGHT file for full details.  Squid
 *  incorporates software developed and/or copyrighted by other
 *  sources; 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;
};

static 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 = cbdataAlloc(RemovalPolicyWalker);
    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;
    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 = cbdataAlloc(RemovalPurgeWalker);
    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;
    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 = cbdataAlloc(RemovalPolicy);
    heap_data = xcalloc(1, sizeof(*heap_data));
    /* 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
6a566b9c	2	/*
0c2bd4fa	3	* $Id: store_repl_heap.cc,v 1.7 2001/03/14 22:28:44 wessels Exp $
6a566b9c	4	*
	5	* DEBUG: section ? HEAP based removal policies
	6	* AUTHOR: Henrik Nordstrom
	7	*
2b6662ba	8	* SQUID Web Proxy Cache http://www.squid-cache.org/
6a566b9c	9	* ----------------------------------------------------------
6a566b9c	10	*
2b6662ba	11	* Squid is the result of efforts by numerous individuals from
	12	* the Internet community; see the CONTRIBUTORS file for full
	13	* details. Many organizations have provided support for Squid's
	14	* development; see the SPONSORS file for full details. Squid is
	15	* Copyrighted (C) 2001 by the Regents of the University of
	16	* California; see the COPYRIGHT file for full details. Squid
	17	* incorporates software developed and/or copyrighted by other
	18	* sources; see the CREDITS file for full details.
6a566b9c	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;
be1ed2a4	51	enum heap_entry_type {
	52	TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
	53	} type;
6a566b9c	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))
be1ed2a4	82	return; /* We won't manage these.. they messes things up */
6a566b9c	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;
be1ed2a4	118	struct _HeapWalkData {
6a566b9c	119	int current;
	120	};
	121
2d72d4fd	122	static const StoreEntry *
6a566b9c	123	heap_walkNext(RemovalPolicyWalker * walker)
	124	{
	125	HeapWalkData *heap_walk = walker->_data;
	126	RemovalPolicy *policy = walker->_policy;
	127	HeapPolicyData *heap = policy->_data;
	128	StoreEntry *entry;
	129	if (heap_walk->current >= heap_nodes(heap->heap))
	130	return NULL; /* done */
	131	entry = (StoreEntry *) heap_peep(heap->heap, heap_walk->current++);
	132	return entry;
	133	}
	134
	135	static void
	136	heap_walkDone(RemovalPolicyWalker * walker)
	137	{
	138	RemovalPolicy *policy = walker->_policy;
	139	HeapPolicyData *heap = policy->_data;
	140	assert(strcmp(policy->_type, "heap") == 0);
	141	assert(heap->nwalkers > 0);
	142	heap->nwalkers -= 1;
	143	safe_free(walker->_data);
	144	cbdataFree(walker);
	145	}
	146
	147	static RemovalPolicyWalker *
	148	heap_walkInit(RemovalPolicy * policy)
	149	{
	150	HeapPolicyData *heap = policy->_data;
	151	RemovalPolicyWalker *walker;
	152	HeapWalkData *heap_walk;
	153	heap->nwalkers += 1;
72711e31	154	walker = cbdataAlloc(RemovalPolicyWalker);
6a566b9c	155	heap_walk = xcalloc(1, sizeof(*heap_walk));
	156	heap_walk->current = 0;
	157	walker->_policy = policy;
	158	walker->_data = heap_walk;
	159	walker->Next = heap_walkNext;
	160	walker->Done = heap_walkDone;
6a566b9c	161	return walker;
	162	}
	163
	164	/ RemovalPurgeWalker /
	165
	166	typedef struct _HeapPurgeData HeapPurgeData;
be1ed2a4	167	struct _HeapPurgeData {
6a566b9c	168	link_list *locked_entries;
	169	heap_key min_age;
	170	};
	171
	172	static StoreEntry *
	173	heap_purgeNext(RemovalPurgeWalker * walker)
	174	{
	175	HeapPurgeData *heap_walker = walker->_data;
	176	RemovalPolicy *policy = walker->_policy;
	177	HeapPolicyData *heap = policy->_data;
	178	StoreEntry *entry;
	179	heap_key age;
	180	try_again:
	181	if (!heap_nodes(heap->heap) > 0)
	182	return NULL; /* done */
	183	age = heap_peepminkey(heap->heap);
	184	entry = heap_extractmin(heap->heap);
	185	if (storeEntryLocked(entry)) {
	186	linklistPush(&heap_walker->locked_entries, entry);
	187	goto try_again;
	188	}
	189	heap_walker->min_age = age;
	190	SET_POLICY_NODE(entry, NULL);
	191	return entry;
	192	}
	193
	194	static void
	195	heap_purgeDone(RemovalPurgeWalker * walker)
	196	{
	197	HeapPurgeData *heap_walker = walker->_data;
	198	RemovalPolicy *policy = walker->_policy;
	199	HeapPolicyData *heap = policy->_data;
	200	StoreEntry *entry;
	201	assert(strcmp(policy->_type, "heap") == 0);
	202	assert(heap->nwalkers > 0);
	203	heap->nwalkers -= 1;
	204	if (heap_walker->min_age > 0) {
	205	heap->heap->age = heap_walker->min_age;
be1ed2a4	206	debug(81, 3) ("heap_purgeDone: Heap age set to %f\n",
be1ed2a4	207	(double) heap->heap->age);
6a566b9c	208	}
	209	/*
	210	* Reinsert the locked entries
	211	*/
	212	while ((entry = linklistShift(&heap_walker->locked_entries))) {
	213	heap_node *node = heap_insert(heap->heap, entry);
	214	SET_POLICY_NODE(entry, node);
	215	}
	216	safe_free(walker->_data);
	217	cbdataFree(walker);
	218	}
	219
	220	static RemovalPurgeWalker *
	221	heap_purgeInit(RemovalPolicy * policy, int max_scan)
	222	{
	223	HeapPolicyData *heap = policy->_data;
	224	RemovalPurgeWalker *walker;
	225	HeapPurgeData *heap_walk;
	226	heap->nwalkers += 1;
72711e31	227	walker = cbdataAlloc(RemovalPurgeWalker);
6a566b9c	228	heap_walk = xcalloc(1, sizeof(*heap_walk));
	229	heap_walk->min_age = 0.0;
	230	heap_walk->locked_entries = NULL;
	231	walker->_policy = policy;
	232	walker->_data = heap_walk;
	233	walker->max_scan = max_scan;
	234	walker->Next = heap_purgeNext;
	235	walker->Done = heap_purgeDone;
6a566b9c	236	return walker;
	237	}
	238
	239	static void
	240	heap_free(RemovalPolicy * policy)
	241	{
	242	HeapPolicyData *heap = policy->_data;
	243	/* Make some verification of the policy state */
	244	assert(strcmp(policy->_type, "heap") == 0);
	245	assert(heap->nwalkers);
	246	assert(heap->count);
	247	/* Ok, time to destroy this policy */
	248	safe_free(policy->_data);
	249	memset(policy, 0, sizeof(*policy));
	250	cbdataFree(policy);
	251	}
	252
	253	RemovalPolicy *
	254	createRemovalPolicy_heap(wordlist * args)
	255	{
	256	RemovalPolicy *policy;
	257	HeapPolicyData *heap_data;
	258	char *keytype;
	259	/* Allocate the needed structures */
72711e31	260	policy = cbdataAlloc(RemovalPolicy);
6a566b9c	261	heap_data = xcalloc(1, sizeof(*heap_data));
6a566b9c	262	/* Initialize the policy data */
	263	heap_data->policy = policy;
	264	if (args) {
	265	keytype = args->key;
	266	args = args->next;
	267	} else {
	268	debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
	269	keytype = "LRU";
	270	}
	271	if (!strcmp(keytype, "GDSF"))
	272	heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
	273	else if (!strcmp(keytype, "LFUDA"))
	274	heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
	275	else if (!strcmp(keytype, "LRU"))
	276	heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
	277	else {
	278	debug(81, 0) ("createRemovalPolicy_heap: Unknown key type \"%s\". Using LRU\n",
	279	keytype);
	280	heap_data->keyfunc = HeapKeyGen_StoreEntry_LRU;
	281	}
	282	/* No additional arguments expected */
	283	assert(!args);
	284	heap_data->heap = new_heap(1000, heap_data->keyfunc);
	285	heap_data->heap->age = 1.0;
	286	/* Populate the policy structure */
	287	policy->_type = "heap";
	288	policy->_data = heap_data;
	289	policy->Free = heap_free;
	290	policy->Add = heap_add;
	291	policy->Remove = heap_remove;
	292	policy->Referenced = NULL;
	293	policy->Dereferenced = heap_referenced;
	294	policy->WalkInit = heap_walkInit;
	295	policy->PurgeInit = heap_purgeInit;
	296	/* Increase policy usage count */
	297	nr_heap_policies += 0;
	298	return policy;
	299	}