-
/*
- * $Id: store_repl_heap.cc,v 1.10 2002/04/08 09:03:17 hno Exp $
+ * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
*
- * DEBUG: section ? HEAP based removal policies
- * AUTHOR: Henrik Nordstrom
+ * Squid software is distributed under GPLv2+ license and includes
+ * contributions from numerous individuals and organizations.
+ * Please see the COPYING and CONTRIBUTORS files for details.
+ */
+
+/*
+ * DEBUG: section 81 Store HEAP Removal Policies
*
* Based on the ideas of the heap policy implemented by John Dilley of
* Hewlett Packard. Rewritten from scratch when modularizing the removal
*
* For details on the original heap policy work and the thinking behind see
* http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
- *
- *
- * 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 "MemObject.h"
+#include "Store.h"
#include "store_heap_replacement.h"
+#include "wordlist.h"
+
+#include <queue>
REMOVALPOLICYCREATE createRemovalPolicy_heap;
static int nr_heap_policies = 0;
-typedef struct _HeapPolicyData HeapPolicyData;
-struct _HeapPolicyData {
+struct HeapPolicyData {
+ void setPolicyNode (StoreEntry *, void *) const;
RemovalPolicy *policy;
- heap *heap;
+ heap *theHeap;
heap_key_func *keyfunc;
int count;
int nwalkers;
enum heap_entry_type {
- TYPE_UNKNOWN = 0, TYPE_STORE_ENTRY, TYPE_STORE_MEM
+ 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
+static enum HeapPolicyData::heap_entry_type
heap_guessType(StoreEntry * entry, RemovalPolicyNode * node)
{
if (node == &entry->repl)
- return TYPE_STORE_ENTRY;
+ return HeapPolicyData::TYPE_STORE_ENTRY;
+
if (entry->mem_obj && node == &entry->mem_obj->repl)
- return TYPE_STORE_MEM;
+ return HeapPolicyData::TYPE_STORE_MEM;
+
fatal("Heap Replacement: Unknown StoreEntry node type");
- return TYPE_UNKNOWN;
+
+ return HeapPolicyData::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; \
+
+void
+HeapPolicyData::setPolicyNode (StoreEntry *entry, void *value) const
+{
+ switch (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;
+ HeapPolicyData *h = (HeapPolicyData *)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);
+ return; /* We won't manage these.. they messes things up */
+
+ node->data = heap_insert(h->theHeap, entry);
+
+ h->count += 1;
+
+ if (!h->type)
+ h->type = heap_guessType(entry, node);
+
/* Add a little more variance to the aging factor */
- heap->heap->age += heap->heap->age / 100000000;
+ h->theHeap->age += h->theHeap->age / 100000000;
}
static void
heap_remove(RemovalPolicy * policy, StoreEntry * entry,
- RemovalPolicyNode * node)
+ RemovalPolicyNode * node)
{
- HeapPolicyData *heap = policy->_data;
- heap_node *hnode = node->data;
+ HeapPolicyData *h = (HeapPolicyData *)policy->_data;
+ heap_node *hnode = (heap_node *)node->data;
+
if (!hnode)
- return;
- heap_delete(heap->heap, hnode);
+ return;
+
+ heap_delete(h->theHeap, hnode);
+
node->data = NULL;
- heap->count -= 1;
+
+ h->count -= 1;
}
static void
heap_referenced(RemovalPolicy * policy, const StoreEntry * entry,
- RemovalPolicyNode * node)
+ RemovalPolicyNode * node)
{
- HeapPolicyData *heap = policy->_data;
- heap_node *hnode = node->data;
+ HeapPolicyData *h = (HeapPolicyData *)policy->_data;
+ heap_node *hnode = (heap_node *)node->data;
+
if (!hnode)
- return;
- heap_update(heap->heap, hnode, (StoreEntry *) entry);
+ return;
+
+ heap_update(h->theHeap, hnode, (StoreEntry *) entry);
}
/** RemovalPolicyWalker **/
typedef struct _HeapWalkData HeapWalkData;
+
struct _HeapWalkData {
- int current;
+ size_t current;
};
static const StoreEntry *
heap_walkNext(RemovalPolicyWalker * walker)
{
- HeapWalkData *heap_walk = walker->_data;
+ HeapWalkData *heap_walk = (HeapWalkData *)walker->_data;
RemovalPolicy *policy = walker->_policy;
- HeapPolicyData *heap = policy->_data;
+ HeapPolicyData *h = (HeapPolicyData *)policy->_data;
StoreEntry *entry;
- if (heap_walk->current >= heap_nodes(heap->heap))
- return NULL; /* done */
- entry = (StoreEntry *) heap_peep(heap->heap, heap_walk->current++);
+
+ if (heap_walk->current >= heap_nodes(h->theHeap))
+ return NULL; /* done */
+
+ entry = (StoreEntry *) heap_peep(h->theHeap, heap_walk->current++);
+
return entry;
}
heap_walkDone(RemovalPolicyWalker * walker)
{
RemovalPolicy *policy = walker->_policy;
- HeapPolicyData *heap = policy->_data;
+ HeapPolicyData *h = (HeapPolicyData *)policy->_data;
assert(strcmp(policy->_type, "heap") == 0);
- assert(heap->nwalkers > 0);
- heap->nwalkers -= 1;
+ assert(h->nwalkers > 0);
+ h->nwalkers -= 1;
safe_free(walker->_data);
- cbdataFree(walker);
+ delete walker;
}
static RemovalPolicyWalker *
heap_walkInit(RemovalPolicy * policy)
{
- HeapPolicyData *heap = policy->_data;
+ HeapPolicyData *h = (HeapPolicyData *)policy->_data;
RemovalPolicyWalker *walker;
HeapWalkData *heap_walk;
- heap->nwalkers += 1;
- walker = cbdataAlloc(RemovalPolicyWalker);
- heap_walk = xcalloc(1, sizeof(*heap_walk));
+ h->nwalkers += 1;
+ walker = new RemovalPolicyWalker;
+ heap_walk = (HeapWalkData *)xcalloc(1, sizeof(*heap_walk));
heap_walk->current = 0;
walker->_policy = policy;
walker->_data = heap_walk;
/** RemovalPurgeWalker **/
-typedef struct _HeapPurgeData HeapPurgeData;
-struct _HeapPurgeData {
- link_list *locked_entries;
- heap_key min_age;
+class HeapPurgeData
+{
+public:
+ std::queue<StoreEntry *> locked_entries;
+ heap_key min_age = 0.0;
};
static StoreEntry *
heap_purgeNext(RemovalPurgeWalker * walker)
{
- HeapPurgeData *heap_walker = walker->_data;
+ HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
RemovalPolicy *policy = walker->_policy;
- HeapPolicyData *heap = policy->_data;
+ HeapPolicyData *h = (HeapPolicyData *)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;
+
+try_again:
+
+ if (heap_empty(h->theHeap))
+ return NULL; /* done */
+
+ age = heap_peepminkey(h->theHeap);
+
+ entry = (StoreEntry *)heap_extractmin(h->theHeap);
+
+ if (entry->locked()) {
+
+ entry->lock("heap_purgeNext");
+ heap_walker->locked_entries.push(entry);
+
+ goto try_again;
}
+
heap_walker->min_age = age;
- SET_POLICY_NODE(entry, NULL);
+ h->setPolicyNode(entry, NULL);
return entry;
}
static void
heap_purgeDone(RemovalPurgeWalker * walker)
{
- HeapPurgeData *heap_walker = walker->_data;
+ HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data;
RemovalPolicy *policy = walker->_policy;
- HeapPolicyData *heap = policy->_data;
- StoreEntry *entry;
+ HeapPolicyData *h = (HeapPolicyData *)policy->_data;
assert(strcmp(policy->_type, "heap") == 0);
- assert(heap->nwalkers > 0);
- heap->nwalkers -= 1;
+ assert(h->nwalkers > 0);
+ h->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);
+ h->theHeap->age = heap_walker->min_age;
+ debugs(81, 3, "Heap age set to " << h->theHeap->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);
+
+ // Reinsert the locked entries
+ while (!heap_walker->locked_entries.empty()) {
+ StoreEntry *entry = heap_walker->locked_entries.front();
+ heap_node *node = heap_insert(h->theHeap, entry);
+ h->setPolicyNode(entry, node);
+ entry->unlock("heap_purgeDone");
+ heap_walker->locked_entries.pop();
}
- safe_free(walker->_data);
- cbdataFree(walker);
+
+ delete heap_walker;
+ delete walker;
}
static RemovalPurgeWalker *
heap_purgeInit(RemovalPolicy * policy, int max_scan)
{
- HeapPolicyData *heap = policy->_data;
+ HeapPolicyData *h = (HeapPolicyData *)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;
+ h->nwalkers += 1;
+ walker = new RemovalPurgeWalker;
+ heap_walk = new HeapPurgeData;
walker->_policy = policy;
walker->_data = heap_walk;
walker->max_scan = max_scan;
static void
heap_free(RemovalPolicy * policy)
{
- HeapPolicyData *heap = policy->_data;
+ HeapPolicyData *h = (HeapPolicyData *)policy->_data;
/* Make some verification of the policy state */
assert(strcmp(policy->_type, "heap") == 0);
- assert(heap->nwalkers);
- assert(heap->count);
+ assert(h->nwalkers);
+ assert(h->count);
/* Ok, time to destroy this policy */
- safe_free(policy->_data);
+ safe_free(h);
memset(policy, 0, sizeof(*policy));
- cbdataFree(policy);
+ delete policy;
}
RemovalPolicy *
HeapPolicyData *heap_data;
const char *keytype;
/* Allocate the needed structures */
- policy = cbdataAlloc(RemovalPolicy);
- heap_data = xcalloc(1, sizeof(*heap_data));
+ policy = new RemovalPolicy;
+ heap_data = (HeapPolicyData *)xcalloc(1, sizeof(*heap_data));
/* Initialize the policy data */
heap_data->policy = policy;
+
if (args) {
- keytype = args->key;
- args = args->next;
+ keytype = args->key;
+ args = args->next;
} else {
- debug(81, 1) ("createRemovalPolicy_heap: No key type specified. Using LRU\n");
- keytype = "LRU";
+ debugs(81, DBG_IMPORTANT, "createRemovalPolicy_heap: No key type specified. Using LRU");
+ keytype = "LRU";
}
+
if (!strcmp(keytype, "GDSF"))
- heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
+ heap_data->keyfunc = HeapKeyGen_StoreEntry_GDSF;
else if (!strcmp(keytype, "LFUDA"))
- heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
+ heap_data->keyfunc = HeapKeyGen_StoreEntry_LFUDA;
else if (!strcmp(keytype, "LRU"))
- heap_data->keyfunc = HeapKeyGen_StoreEntry_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;
+ debugs(81, DBG_CRITICAL, "createRemovalPolicy_heap: Unknown key type \"" << keytype << "\". Using LRU");
+ 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;
+ while (args) {
+ debugs(81, DBG_IMPORTANT, "WARNING: discarding unknown removal policy '" << args->key << "'");
+ args = args->next;
+ }
+
+ heap_data->theHeap = new_heap(1000, heap_data->keyfunc);
+
+ heap_data->theHeap->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;
}
+
projects / thirdparty / squid.git / blobdiff