-
/*
- * $Id: store_repl_lru.cc,v 1.13 2003/01/23 00:38:29 robertc Exp $
- *
- * DEBUG: section ? LRU Removal policy
- * 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.
+ * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
*
+ * 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: none LRU Removal Policy */
+
#include "squid.h"
-#include "Store.h"
#include "MemObject.h"
+#include "SquidTime.h"
+#include "Store.h"
+
+/* because LruNode use explicit memory alloc()/freeOne() calls.
+ * XXX: convert to MEMPROXY_CLASS() API
+ */
+#include "mem/Pool.h"
REMOVALPOLICYCREATE createRemovalPolicy_lru;
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;
};
repl_guessType(StoreEntry * entry, RemovalPolicyNode * node)
{
if (node == &entry->repl)
- return LruPolicyData::TYPE_STORE_ENTRY;
+ return LruPolicyData::TYPE_STORE_ENTRY;
+
if (entry->mem_obj && node == &entry->mem_obj->repl)
- return LruPolicyData::TYPE_STORE_MEM;
+ return LruPolicyData::TYPE_STORE_MEM;
+
fatal("Heap Replacement: Unknown StoreEntry node type");
+
return LruPolicyData::TYPE_UNKNOWN;
}
LruPolicyData::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;
+
+ case TYPE_STORE_ENTRY:
+ entry->repl.data = value;
+ break ;
+
+ case TYPE_STORE_MEM:
+ entry->mem_obj->repl.data = value ;
+ break ;
+
+ default:
+ break;
}
}
typedef struct _LruNode LruNode;
+
struct _LruNode {
/* Note: the dlink_node MUST be the first member of the LruNode
* structure. This member is later pointer typecasted to LruNode *.
dlink_node node;
};
-static MemPool *lru_node_pool = NULL;
+static MemAllocator *lru_node_pool = NULL;
static int nr_lru_policies = 0;
static void
LruPolicyData *lru = (LruPolicyData *)policy->_data;
LruNode *lru_node;
assert(!node->data);
- node->data = lru_node = (LruNode *)memPoolAlloc(lru_node_pool);
+ node->data = lru_node = (LruNode *)lru_node_pool->alloc();
dlinkAddTail(entry, &lru_node->node, &lru->list);
lru->count += 1;
+
if (!lru->type)
- lru->type = repl_guessType(entry, node);
+ lru->type = repl_guessType(entry, node);
}
static void
{
LruPolicyData *lru = (LruPolicyData *)policy->_data;
LruNode *lru_node = (LruNode *)node->data;
+
if (!lru_node)
- return;
+ return;
+
/*
* It seems to be possible for an entry to exist in the hash
* but not be in the LRU list, so check for that case rather
* than suffer a NULL pointer access.
*/
if (NULL == lru_node->node.data)
- return;
+ return;
+
assert(lru_node->node.data == entry);
+
node->data = NULL;
+
dlinkDelete(&lru_node->node, &lru->list);
- memPoolFree(lru_node_pool, lru_node);
+
+ lru_node_pool->freeOne(lru_node);
+
lru->count -= 1;
}
static void
lru_referenced(RemovalPolicy * policy, const StoreEntry * entry,
- RemovalPolicyNode * node)
+ RemovalPolicyNode * node)
{
LruPolicyData *lru = (LruPolicyData *)policy->_data;
LruNode *lru_node = (LruNode *)node->data;
+
if (!lru_node)
- return;
+ return;
+
dlinkDelete(&lru_node->node, &lru->list);
+
dlinkAddTail((void *) entry, &lru_node->node, &lru->list);
}
/** RemovalPolicyWalker **/
typedef struct _LruWalkData LruWalkData;
+
struct _LruWalkData {
LruNode *current;
};
{
LruWalkData *lru_walk = (LruWalkData *)walker->_data;
LruNode *lru_node = lru_walk->current;
+
if (!lru_node)
- return NULL;
+ return NULL;
+
lru_walk->current = (LruNode *) lru_node->node.next;
+
return (StoreEntry *) lru_node->node.data;
}
assert(lru->nwalkers > 0);
lru->nwalkers -= 1;
safe_free(walker->_data);
- cbdataFree(walker);
+ delete walker;
}
static RemovalPolicyWalker *
RemovalPolicyWalker *walker;
LruWalkData *lru_walk;
lru->nwalkers += 1;
- walker = cbdataAlloc(RemovalPolicyWalker);
+ walker = new RemovalPolicyWalker;
lru_walk = (LruWalkData *)xcalloc(1, sizeof(*lru_walk));
walker->_policy = policy;
walker->_data = lru_walk;
/** RemovalPurgeWalker **/
typedef struct _LruPurgeData LruPurgeData;
+
struct _LruPurgeData {
LruNode *current;
LruNode *start;
LruPolicyData *lru = (LruPolicyData *)policy->_data;
LruNode *lru_node;
StoreEntry *entry;
- try_again:
+
+try_again:
lru_node = lru_walker->current;
+
if (!lru_node || walker->scanned >= walker->max_scan)
- return NULL;
+ return NULL;
+
walker->scanned += 1;
+
lru_walker->current = (LruNode *) lru_node->node.next;
+
if (lru_walker->current == lru_walker->start) {
- /* Last node found */
- lru_walker->current = NULL;
+ /* Last node found */
+ lru_walker->current = NULL;
}
+
entry = (StoreEntry *) lru_node->node.data;
dlinkDelete(&lru_node->node, &lru->list);
- if (storeEntryLocked(entry)) {
- /* Shit, it is locked. we can't return this one */
- walker->locked++;
- dlinkAddTail(entry, &lru_node->node, &lru->list);
- goto try_again;
+
+ if (entry->locked()) {
+ /* Shit, it is locked. we can't return this one */
+ ++ walker->locked;
+ dlinkAddTail(entry, &lru_node->node, &lru->list);
+ goto try_again;
}
- memPoolFree(lru_node_pool, lru_node);
+
+ lru_node_pool->freeOne(lru_node);
lru->count -= 1;
lru->setPolicyNode(entry, NULL);
return entry;
assert(lru->nwalkers > 0);
lru->nwalkers -= 1;
safe_free(walker->_data);
- cbdataFree(walker);
+ delete walker;
}
static RemovalPurgeWalker *
RemovalPurgeWalker *walker;
LruPurgeData *lru_walk;
lru->nwalkers += 1;
- walker = cbdataAlloc(RemovalPurgeWalker);
+ walker = new RemovalPurgeWalker;
lru_walk = (LruPurgeData *)xcalloc(1, sizeof(*lru_walk));
walker->_policy = policy;
walker->_data = lru_walk;
LruPolicyData *lru = (LruPolicyData *)policy->_data;
LruNode *lru_node = (LruNode *) lru->list.head;
- again:
+again:
+
if (lru_node) {
- StoreEntry *entry = (StoreEntry *) lru_node->node.data;
- if (storeEntryLocked(entry)) {
- lru_node = (LruNode *) lru_node->node.next;
- goto again;
- }
- storeAppendPrintf(sentry, "LRU reference age: %.2f days\n", (double) (squid_curtime - entry->lastref) / (double) (24 * 60 * 60));
+ StoreEntry *entry = (StoreEntry *) lru_node->node.data;
+
+ if (entry->locked()) {
+ lru_node = (LruNode *) lru_node->node.next;
+ goto again;
+ }
+
+ storeAppendPrintf(sentry, "LRU reference age: %.2f days\n", (double) (squid_curtime - entry->lastref) / (double) (24 * 60 * 60));
}
}
assert(lru->nwalkers);
assert(lru->count);
/* Ok, time to destroy this policy */
- safe_free(policy->_data);
+ safe_free(lru);
memset(policy, 0, sizeof(*policy));
- cbdataFree(policy);
+ delete policy;
}
RemovalPolicy *
/* no arguments expected or understood */
assert(!args);
/* Initialize */
+
if (!lru_node_pool) {
- lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode));
- memPoolSetChunkSize(lru_node_pool, 512 * 1024);
+ /* Must be chunked */
+ lru_node_pool = memPoolCreate("LRU policy node", sizeof(LruNode));
+ lru_node_pool->setChunkSize(512 * 1024);
}
+
/* Allocate the needed structures */
lru_data = (LruPolicyData *)xcalloc(1, sizeof(*lru_data));
- policy = cbdataAlloc(RemovalPolicy);
+
+ policy = new RemovalPolicy;
+
/* Initialize the URL data */
lru_data->policy = policy;
+
/* Populate the policy structure */
policy->_type = "lru";
+
policy->_data = lru_data;
+
policy->Free = lru_free;
+
policy->Add = lru_add;
+
policy->Remove = lru_remove;
+
policy->Referenced = lru_referenced;
+
policy->Dereferenced = lru_referenced;
+
policy->WalkInit = lru_walkInit;
+
policy->PurgeInit = lru_purgeInit;
+
policy->Stats = lru_stats;
+
/* Increase policy usage count */
nr_lru_policies += 0;
+
return policy;
}
+