--------------------- PatchSet 5345 Date: 2002/10/12 03:01:00 Author: rbcollins Branch: rbcollins_cxxtest Tag: (none) Log: repl policies Members: configure.in:1.70.2.4->1.70.2.5 include/heap.h:1.5->1.5.44.1 include/md5.h:1.8.44.1->1.8.44.2 include/snmp_debug.h:1.7->1.7.6.1 include/snmp_pdu.h:1.7->1.7.28.1 include/snmp_util.h:1.4->1.4.44.1 include/snmp_vars.h:1.5->1.5.44.1 include/util.h:1.11.20.8->1.11.20.9 src/Makefile.am:1.29.2.25->1.29.2.26 src/repl/Makefile.am:1.3.32.2->1.3.32.3 src/repl/heap/Makefile.am:1.2->1.2.72.1(DEAD) src/repl/heap/store_heap_replacement.c:1.8.18.1->1.8.18.2(DEAD) src/repl/heap/store_heap_replacement.cc:1.1->1.1.2.1 src/repl/heap/store_repl_heap.c:1.10.18.1->1.10.18.2(DEAD) src/repl/heap/store_repl_heap.cc:1.1->1.1.2.1 src/repl/lru/Makefile.am:1.2->1.2.72.1(DEAD) src/repl/lru/store_repl_lru.c:1.10.20.1->1.10.20.2(DEAD) src/repl/lru/store_repl_lru.cc:1.1->1.1.2.1 Index: squid/configure.in =================================================================== RCS file: /cvsroot/squid-sf//squid/configure.in,v retrieving revision 1.70.2.4 retrieving revision 1.70.2.5 diff -u -r1.70.2.4 -r1.70.2.5 --- squid/configure.in 7 Oct 2002 02:07:11 -0000 1.70.2.4 +++ squid/configure.in 12 Oct 2002 03:01:00 -0000 1.70.2.5 @@ -3,7 +3,7 @@ dnl dnl Duane Wessels, wessels@nlanr.net, February 1996 (autoconf v2.9) dnl -dnl $Id: configure.in,v 1.70.2.4 2002/10/07 02:07:11 rbcollins Exp $ +dnl $Id: configure.in,v 1.70.2.5 2002/10/12 03:01:00 rbcollins Exp $ dnl dnl dnl @@ -13,7 +13,7 @@ AC_CONFIG_AUX_DIR(cfgaux) AM_INIT_AUTOMAKE(squid, 2.6-DEVEL) AM_CONFIG_HEADER(include/autoconf.h) -AC_REVISION($Revision: 1.70.2.4 $)dnl +AC_REVISION($Revision: 1.70.2.5 $)dnl AC_PREFIX_DEFAULT(/usr/local/squid) AM_MAINTAINER_MODE @@ -2304,9 +2304,6 @@ src/fs/Makefile \ src/repl/Makefile \ src/auth/Makefile \ - src/auth/basic/Makefile \ - src/auth/digest/Makefile \ - src/auth/ntlm/Makefile \ contrib/Makefile \ snmplib/Makefile \ icons/Makefile \ @@ -2316,8 +2313,6 @@ src/fs/diskd/Makefile \ src/fs/null/Makefile \ src/fs/ufs/Makefile \ - src/repl/heap/Makefile \ - src/repl/lru/Makefile \ doc/Makefile \ helpers/Makefile \ helpers/basic_auth/Makefile \ Index: squid/include/heap.h =================================================================== RCS file: /cvsroot/squid-sf//squid/include/heap.h,v retrieving revision 1.5 retrieving revision 1.5.44.1 diff -u -r1.5 -r1.5.44.1 --- squid/include/heap.h 9 Oct 2001 21:17:59 -0000 1.5 +++ squid/include/heap.h 12 Oct 2002 03:01:02 -0000 1.5.44.1 @@ -1,5 +1,5 @@ /* - * $Id: heap.h,v 1.5 2001/10/09 21:17:59 squidadm Exp $ + * $Id: heap.h,v 1.5.44.1 2002/10/12 03:01:02 rbcollins Exp $ * * AUTHOR: John Dilley, Hewlett Packard * @@ -89,13 +89,13 @@ /* * Create and initialize a new heap. */ -extern heap *new_heap(int init_size, heap_key_func gen_key); +SQUIDCEXTERN heap *new_heap(int init_size, heap_key_func gen_key); /* * Delete a heap and clean up its memory. Does not delete what the heap * nodes are pointing to! */ -extern void delete_heap(heap *); +SQUIDCEXTERN void delete_heap(heap *); /* * Insert a new node into a heap, returning a pointer to it. The heap_node @@ -103,13 +103,13 @@ * should be done with this data structure (especially modifying it!) The * heap does not assume ownership of the data passed to it. */ -extern heap_node *heap_insert(heap *, heap_t dat); +SQUIDCEXTERN heap_node *heap_insert(heap *, heap_t dat); /* * Delete a node out of a heap. Returns the heap data from the deleted * node. The caller is responsible for freeing this data. */ -extern heap_t heap_delete(heap *, heap_node * elm); +SQUIDCEXTERN heap_t heap_delete(heap *, heap_node * elm); /* * The semantics of this routine is the same as the followings: @@ -118,13 +118,13 @@ * Returns the old data object from elm (the one being replaced). The * caller must free this as necessary. */ -extern heap_t heap_update(heap *, heap_node * elm, heap_t dat); +SQUIDCEXTERN heap_t heap_update(heap *, heap_node * elm, heap_t dat); /* * Generate a heap key for a given data object. Alternative macro form: */ #ifdef MACRO_DEBUG -extern heap_key heap_gen_key(heap * hp, heap_t dat); +SQUIDCEXTERN heap_key heap_gen_key(heap * hp, heap_t dat); #else #define heap_gen_key(hp,md) ((hp)->gen_key((md),(hp)->age)) #endif /* MACRO_DEBUG */ @@ -135,7 +135,7 @@ * Returns the data pointed to by the root node, which the caller must * free as necessary. */ -extern heap_t heap_extractmin(heap *); +SQUIDCEXTERN heap_t heap_extractmin(heap *); /* * Extract the last leaf node (does not change the heap property). @@ -144,24 +144,24 @@ * parent, but may not be less than any of the other (leaf or parent) notes * in the tree. This operation is fast but imprecise. */ -extern heap_t heap_extractlast(heap * hp); +SQUIDCEXTERN heap_t heap_extractlast(heap * hp); /* * Get the root key, the nth key, the root (smallest) element, or the nth * element. None of these operations modify the heap. */ -extern heap_key heap_peepminkey(heap *); -extern heap_key heap_peepkey(heap *, int n); +SQUIDCEXTERN heap_key heap_peepminkey(heap *); +SQUIDCEXTERN heap_key heap_peepkey(heap *, int n); -extern heap_t heap_peepmin(heap *); -extern heap_t heap_peep(heap *, int n); +SQUIDCEXTERN heap_t heap_peepmin(heap *); +SQUIDCEXTERN heap_t heap_peep(heap *, int n); /* * Is the heap empty? How many nodes (data objects) are in it? */ #ifdef MACRO_DEBUG -extern int heap_empty(heap *); -extern int heap_nodes(heap *); +SQUIDCEXTERN int heap_empty(heap *); +SQUIDCEXTERN int heap_nodes(heap *); #else /* MACRO_DEBUG */ #define heap_nodes(heap) ((heap)->last) #define heap_empty(heap) (((heap)->last <= 0) ? 1 : 0) @@ -170,9 +170,9 @@ /* * Print the heap or a node in the heap. */ -extern void heap_print(heap *); -extern void heap_printnode(char *msg, heap_node * elm); +SQUIDCEXTERN void heap_print(heap *); +SQUIDCEXTERN void heap_printnode(char *msg, heap_node * elm); -extern int verify_heap_property(heap *); +SQUIDCEXTERN int verify_heap_property(heap *); #endif /* SQUID_HEAP_H */ Index: squid/include/md5.h =================================================================== RCS file: /cvsroot/squid-sf//squid/include/md5.h,v retrieving revision 1.8.44.1 retrieving revision 1.8.44.2 diff -u -r1.8.44.1 -r1.8.44.2 --- squid/include/md5.h 6 Oct 2002 04:01:13 -0000 1.8.44.1 +++ squid/include/md5.h 12 Oct 2002 03:01:03 -0000 1.8.44.2 @@ -1,5 +1,5 @@ /* - * $Id: md5.h,v 1.8.44.1 2002/10/06 04:01:13 rbcollins Exp $ + * $Id: md5.h,v 1.8.44.2 2002/10/12 03:01:03 rbcollins Exp $ */ #ifndef SQUID_MD5_H @@ -61,9 +61,9 @@ unsigned char buffer[64]; /* input buffer */ } MD5_CTX; -void MD5Init(MD5_CTX *); -void MD5Update(MD5_CTX *, const void *, unsigned long); -void MD5Final(unsigned char *, MD5_CTX *); +SQUIDCEXTERN void MD5Init(MD5_CTX *); +SQUIDCEXTERN void MD5Update(MD5_CTX *, const void *, unsigned long); +SQUIDCEXTERN void MD5Final(unsigned char *, MD5_CTX *); #define MD5_DIGEST_CHARS 16 Index: squid/include/snmp_debug.h =================================================================== RCS file: /cvsroot/squid-sf//squid/include/snmp_debug.h,v retrieving revision 1.7 retrieving revision 1.7.6.1 diff -u -r1.7 -r1.7.6.1 --- squid/include/snmp_debug.h 15 Sep 2002 21:45:35 -0000 1.7 +++ squid/include/snmp_debug.h 12 Oct 2002 03:01:04 -0000 1.7.6.1 @@ -1,10 +1,14 @@ /* - * $Id: snmp_debug.h,v 1.7 2002/09/15 21:45:35 squidadm Exp $ + * $Id: snmp_debug.h,v 1.7.6.1 2002/10/12 03:01:04 rbcollins Exp $ */ #ifndef SQUID_SNMP_DEBUG_H #define SQUID_SNMP_DEBUG_H +#ifdef __cplusplus +extern "C" { +#endif + #if STDC_HEADERS extern void snmplib_debug(int, const char *,...) PRINTF_FORMAT_ARG2; @@ -12,5 +16,8 @@ extern void snmplib_debug (va_alist); #endif +#ifdef __cplusplus +}; +#endif #endif /* SQUID_SNMP_DEBUG_H */ Index: squid/include/snmp_pdu.h =================================================================== RCS file: /cvsroot/squid-sf//squid/include/snmp_pdu.h,v retrieving revision 1.7 retrieving revision 1.7.28.1 diff -u -r1.7 -r1.7.28.1 --- squid/include/snmp_pdu.h 13 Feb 2002 17:24:41 -0000 1.7 +++ squid/include/snmp_pdu.h 12 Oct 2002 03:01:04 -0000 1.7.28.1 @@ -25,10 +25,14 @@ * * Author: Ryan Troll * - * $Id: snmp_pdu.h,v 1.7 2002/02/13 17:24:41 squidadm Exp $ + * $Id: snmp_pdu.h,v 1.7.28.1 2002/10/12 03:01:04 rbcollins Exp $ * **********************************************************************/ +#ifdef __cplusplus +extern "C" { +#endif + typedef struct sockaddr_in ipaddr; /* An SNMP PDU */ @@ -109,4 +113,8 @@ #define SNMP_TRAP_ENTERPRISESPECIFIC (0x6) #endif +#ifdef __cplusplus +} +#endif + #endif /* SQUID_SNMP_PDU_H */ Index: squid/include/snmp_util.h =================================================================== RCS file: /cvsroot/squid-sf//squid/include/snmp_util.h,v retrieving revision 1.4 retrieving revision 1.4.44.1 diff -u -r1.4 -r1.4.44.1 --- squid/include/snmp_util.h 9 Oct 2001 21:18:00 -0000 1.4 +++ squid/include/snmp_util.h 12 Oct 2002 03:01:05 -0000 1.4.44.1 @@ -1,10 +1,14 @@ /* - * $Id: snmp_util.h,v 1.4 2001/10/09 21:18:00 squidadm Exp $ + * $Id: snmp_util.h,v 1.4.44.1 2002/10/12 03:01:05 rbcollins Exp $ */ #ifndef SQUID_SNMP_UTIL_H #define SQUID_SNMP_UTIL_H +#ifdef __cplusplus +extern "C" { +#endif + /* call a function at regular intervals (in seconds): */ extern void snmp_alarm(int ival, void (*handler) (void)); @@ -46,4 +50,8 @@ int Util_file_write(char *file, int offset, char *data, int dataSz); /* ---------------------------------------------------------------------- */ + +#ifdef __cplusplus +} +#endif #endif /* SQUID_SNMP_UTIL_H */ Index: squid/include/snmp_vars.h =================================================================== RCS file: /cvsroot/squid-sf//squid/include/snmp_vars.h,v retrieving revision 1.5 retrieving revision 1.5.44.1 diff -u -r1.5 -r1.5.44.1 --- squid/include/snmp_vars.h 9 Oct 2001 21:18:00 -0000 1.5 +++ squid/include/snmp_vars.h 12 Oct 2002 03:01:05 -0000 1.5.44.1 @@ -25,10 +25,14 @@ * * Author: Ryan Troll * - * $Id: snmp_vars.h,v 1.5 2001/10/09 21:18:00 squidadm Exp $ + * $Id: snmp_vars.h,v 1.5.44.1 2002/10/12 03:01:05 rbcollins Exp $ * **********************************************************************/ +#ifdef __cplusplus +extern "C" { +#endif + struct variable_list { struct variable_list *next_variable; /* NULL for last variable */ oid *name; /* Object identifier of variable */ @@ -73,4 +77,8 @@ typedef struct variable variable; typedef struct variable_list variable_list; +#ifdef __cplusplus +} +#endif + #endif /* SQUID_SNMP_VARS_H */ Index: squid/include/util.h =================================================================== RCS file: /cvsroot/squid-sf//squid/include/util.h,v retrieving revision 1.11.20.8 retrieving revision 1.11.20.9 diff -u -r1.11.20.8 -r1.11.20.9 --- squid/include/util.h 9 Oct 2002 14:14:15 -0000 1.11.20.8 +++ squid/include/util.h 12 Oct 2002 03:01:05 -0000 1.11.20.9 @@ -1,5 +1,5 @@ /* - * $Id: util.h,v 1.11.20.8 2002/10/09 14:14:15 rbcollins Exp $ + * $Id: util.h,v 1.11.20.9 2002/10/12 03:01:05 rbcollins Exp $ * * AUTHOR: Harvest Derived * @@ -112,7 +112,7 @@ typedef struct in_addr SIA; SQUIDCEXTERN int safe_inet_addr(const char *, SIA *); -extern time_t parse_iso3307_time(const char *buf); +SQUIDCEXTERN time_t parse_iso3307_time(const char *buf); SQUIDCEXTERN char *base64_decode(const char *coded); SQUIDCEXTERN const char *base64_encode(const char *decoded); SQUIDCEXTERN const char *base64_encode_bin(const char *data, int len); Index: squid/src/Makefile.am =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Makefile.am,v retrieving revision 1.29.2.25 retrieving revision 1.29.2.26 diff -u -r1.29.2.25 -r1.29.2.26 --- squid/src/Makefile.am 11 Oct 2002 23:20:20 -0000 1.29.2.25 +++ squid/src/Makefile.am 12 Oct 2002 03:01:06 -0000 1.29.2.26 @@ -229,7 +229,7 @@ $(WIN32SOURCE) nodist_squid_SOURCES = \ - repl_modules.c \ + repl_modules.cc \ auth_modules.cc \ store_modules.c \ cf_parser.h \ @@ -271,7 +271,7 @@ cf_parser.h \ globals.c \ string_arrays.c \ - repl_modules.c \ + repl_modules.cc \ auth_modules.cc \ store_modules.c @@ -368,8 +368,8 @@ store_modules.c: store_modules.sh Makefile $(SHELL) $(srcdir)/store_modules.sh $(STORE_MODULES) >store_modules.c -repl_modules.c: repl_modules.sh Makefile - $(SHELL) $(srcdir)/repl_modules.sh $(REPL_POLICIES) > repl_modules.c +repl_modules.cc: repl_modules.sh Makefile + $(SHELL) $(srcdir)/repl_modules.sh $(REPL_POLICIES) > repl_modules.cc auth_modules.cc: auth_modules.sh Makefile @$(SHELL) $(srcdir)/auth_modules.sh $(AUTH_MODULES) >auth_modules.cc @@ -400,7 +400,7 @@ fi DISTCLEANFILES = cf_gen_defines.h cf.data cf_parser.h squid.conf.default \ - globals.c string_arrays.c repl_modules.c auth_modules.cc store_modules.c + globals.c string_arrays.c repl_modules.cc auth_modules.cc store_modules.c ##install-pinger: ## @f=$(PINGER_EXE); \ Index: squid/src/repl/Makefile.am =================================================================== RCS file: /cvsroot/squid-sf//squid/src/repl/Makefile.am,v retrieving revision 1.3.32.2 retrieving revision 1.3.32.3 diff -u -r1.3.32.2 -r1.3.32.3 --- squid/src/repl/Makefile.am 4 Oct 2002 21:22:10 -0000 1.3.32.2 +++ squid/src/repl/Makefile.am 12 Oct 2002 03:01:07 -0000 1.3.32.3 @@ -10,45 +10,13 @@ DIST_SUBDIRS = lru heap SUBDIRS = # No recursion is needed for the subdirs, we build from here. // @REPL_POLICIES@ -OUTLIBS = @REPL_LIBS@ EXTRA_LIBRARIES = liblru.a libheap.a noinst_LIBRARIES = @REPL_LIBS@ -liblru_a_SOURCES = lru/store_repl_lru.c -libheap_a_SOURCES = heap/store_heap_replacement.h heap/store_heap_replacement.c heap/store_repl_heap.c +liblru_a_SOURCES = lru/store_repl_lru.cc +libheap_a_SOURCES = heap/store_heap_replacement.h heap/store_heap_replacement.cc heap/store_repl_heap.cc INCLUDES = -I. -I$(top_builddir)/include -I$(top_srcdir)/include \ -I$(top_srcdir)/src/ -##all: -## @test -z "$(SUBDIRS)" || for dir in $(SUBDIRS); do \ -## sh -c "cd $$dir && $(MAKE) $(MFLAGS) all" || exit 1; \ -## done; \ -## if [ ! -f stamp ]; then \ -## touch stamp; \ -## fi - -##$(OUTLIBS): -## @sh -c "cd `basename $@ .a` && $(MAKE) $(MFLAGS) ../$@" - -##clean: -## -rm -f *.a stamp -## -for dir in *; do \ -## if [ -f $$dir/Makefile ]; then \ -## sh -c "cd $$dir && $(MAKE) $(MFLAGS) $@" || exit 1;\ -## fi; \ -## done - -##distclean: -## -rm -f *.a Makefile -## -for dir in *; do \ -## if [ -f $$dir/Makefile ]; then \ -## sh -c "cd $$dir && $(MAKE) $(MFLAGS) distclean"; \ -## fi; \ -## done - -##.DEFAULT: -## @test -z "$(SUBDIRS)" || for dir in $(SUBDIRS); do \ -## sh -c "cd $$dir && $(MAKE) $(MFLAGS) $@" || exit 1; \ -## done --- squid/src/repl/heap/store_heap_replacement.c Wed Feb 14 01:07:41 2007 +++ /dev/null Wed Feb 14 01:07:22 2007 @@ -1,143 +0,0 @@ - -/* - * $Id$ - * - * DEBUG: section 20 Storage Manager Heap-based replacement - * AUTHOR: John Dilley - * - * 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. - * - */ - -/* - * The code in this file is Copyrighted (C) 1999 by Hewlett Packard. - * - * - * For a description of these cache replacement policies see -- - * http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html - */ - -#include "squid.h" -#include "heap.h" -#include "store_heap_replacement.h" -#include "Store.h" - -/* - * Key generation function to implement the LFU-DA policy (Least - * Frequently Used with Dynamic Aging). Similar to classical LFU - * but with aging to handle turnover of the popular document set. - * Maximizes byte hit rate by keeping more currently popular objects - * in cache regardless of size. Achieves lower hit rate than GDS - * because there are more large objects in cache (so less room for - * smaller popular objects). - * - * This version implements a tie-breaker based upon recency - * (e->lastref): for objects that have the same reference count - * the most recent object wins (gets a higher key value). - * - * Note: this does not properly handle when the aging factor - * gets so huge that the added value is outside of the - * precision of double. However, Squid has to stay up - * for quite a extended period of time (number of requests) - * for this to become a problem. (estimation is 10^8 cache - * turnarounds) - */ -heap_key -HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age) -{ - StoreEntry *e = entry; - heap_key key; - double tie; - if (e->lastref <= 0) - tie = 0.0; - else if (squid_curtime <= e->lastref) - tie = 0.0; - else - tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0); - key = heap_age + (double) e->refcount - tie; - debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: %s refcnt=%d lastref=%ld heap_age=%f tie=%f -> %f\n", - storeKeyText(e->hash.key), (int)e->refcount, e->lastref, heap_age, tie, key); - if (e->mem_obj && e->mem_obj->url) - debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: url=%s\n", - e->mem_obj->url); - return (double) key; -} - - -/* - * Key generation function to implement the GDS-Frequency policy. - * Similar to Greedy Dual-Size Hits policy, but adds aging of - * documents to prevent pollution. Maximizes object hit rate by - * keeping more small, popular objects in cache. Achieves lower - * byte hit rate than LFUDA because there are fewer large objects - * in cache. - * - * This version implements a tie-breaker based upon recency - * (e->lastref): for objects that have the same reference count - * the most recent object wins (gets a higher key value). - * - * Note: this does not properly handle when the aging factor - * gets so huge that the added value is outside of the - * precision of double. However, Squid has to stay up - * for quite a extended period of time (number of requests) - * for this to become a problem. (estimation is 10^8 cache - * turnarounds) - */ -heap_key -HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age) -{ - StoreEntry *e = entry; - heap_key key; - double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0; - double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0; - key = heap_age + ((double) e->refcount / size) - tie; - debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: %s size=%f refcnt=%d lastref=%ld heap_age=%f tie=%f -> %f\n", - storeKeyText(e->hash.key), size, (int)e->refcount, e->lastref, heap_age, tie, key); - if (e->mem_obj && e->mem_obj->url) - debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: url=%s\n", - e->mem_obj->url); - return key; -} - -/* - * Key generation function to implement the LRU policy. Normally - * one would not do this with a heap -- use the linked list instead. - * For testing and performance characterization it was useful. - * Don't use it unless you are trying to compare performance among - * heap-based replacement policies... - */ -heap_key -HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age) -{ - StoreEntry *e = entry; - debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: %s heap_age=%f lastref=%f\n", - storeKeyText(e->hash.key), heap_age, (double) e->lastref); - if (e->mem_obj && e->mem_obj->url) - debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: url=%s\n", - e->mem_obj->url); - return (heap_key) e->lastref; -} --- /dev/null Wed Feb 14 01:07:22 2007 +++ squid/src/repl/heap/store_heap_replacement.cc Wed Feb 14 01:07:41 2007 @@ -0,0 +1,143 @@ + +/* + * $Id: store_heap_replacement.cc,v 1.1.2.1 2002/10/12 03:01:09 rbcollins Exp $ + * + * DEBUG: section 20 Storage Manager Heap-based replacement + * AUTHOR: John Dilley + * + * 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. + * + */ + +/* + * The code in this file is Copyrighted (C) 1999 by Hewlett Packard. + * + * + * For a description of these cache replacement policies see -- + * http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html + */ + +#include "squid.h" +#include "heap.h" +#include "store_heap_replacement.h" +#include "Store.h" + +/* + * Key generation function to implement the LFU-DA policy (Least + * Frequently Used with Dynamic Aging). Similar to classical LFU + * but with aging to handle turnover of the popular document set. + * Maximizes byte hit rate by keeping more currently popular objects + * in cache regardless of size. Achieves lower hit rate than GDS + * because there are more large objects in cache (so less room for + * smaller popular objects). + * + * This version implements a tie-breaker based upon recency + * (e->lastref): for objects that have the same reference count + * the most recent object wins (gets a higher key value). + * + * Note: this does not properly handle when the aging factor + * gets so huge that the added value is outside of the + * precision of double. However, Squid has to stay up + * for quite a extended period of time (number of requests) + * for this to become a problem. (estimation is 10^8 cache + * turnarounds) + */ +heap_key +HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age) +{ + StoreEntry *e = (StoreEntry *)entry; + heap_key key; + double tie; + if (e->lastref <= 0) + tie = 0.0; + else if (squid_curtime <= e->lastref) + tie = 0.0; + else + tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0); + key = heap_age + (double) e->refcount - tie; + debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: %s refcnt=%d lastref=%ld heap_age=%f tie=%f -> %f\n", + storeKeyText((const cache_key *)e->hash.key), (int)e->refcount, e->lastref, heap_age, tie, key); + if (e->mem_obj && e->mem_obj->url) + debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: url=%s\n", + e->mem_obj->url); + return (double) key; +} + + +/* + * Key generation function to implement the GDS-Frequency policy. + * Similar to Greedy Dual-Size Hits policy, but adds aging of + * documents to prevent pollution. Maximizes object hit rate by + * keeping more small, popular objects in cache. Achieves lower + * byte hit rate than LFUDA because there are fewer large objects + * in cache. + * + * This version implements a tie-breaker based upon recency + * (e->lastref): for objects that have the same reference count + * the most recent object wins (gets a higher key value). + * + * Note: this does not properly handle when the aging factor + * gets so huge that the added value is outside of the + * precision of double. However, Squid has to stay up + * for quite a extended period of time (number of requests) + * for this to become a problem. (estimation is 10^8 cache + * turnarounds) + */ +heap_key +HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age) +{ + StoreEntry *e = (StoreEntry *)entry; + heap_key key; + double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0; + double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0; + key = heap_age + ((double) e->refcount / size) - tie; + debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: %s size=%f refcnt=%d lastref=%ld heap_age=%f tie=%f -> %f\n", + storeKeyText((const cache_key *)e->hash.key), size, (int)e->refcount, e->lastref, heap_age, tie, key); + if (e->mem_obj && e->mem_obj->url) + debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: url=%s\n", + e->mem_obj->url); + return key; +} + +/* + * Key generation function to implement the LRU policy. Normally + * one would not do this with a heap -- use the linked list instead. + * For testing and performance characterization it was useful. + * Don't use it unless you are trying to compare performance among + * heap-based replacement policies... + */ +heap_key +HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age) +{ + StoreEntry *e = (StoreEntry *)entry; + debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: %s heap_age=%f lastref=%f\n", + storeKeyText((const cache_key *)e->hash.key), heap_age, (double) e->lastref); + if (e->mem_obj && e->mem_obj->url) + debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: url=%s\n", + e->mem_obj->url); + return (heap_key) e->lastref; +} --- squid/src/repl/heap/store_repl_heap.c Wed Feb 14 01:07:41 2007 +++ /dev/null Wed Feb 14 01:07:22 2007 @@ -1,308 +0,0 @@ - -/* - * $Id$ - * - * DEBUG: section ? HEAP based removal policies - * AUTHOR: Henrik Nordstrom - * - * Based on the ideas of the heap policy implemented by John Dilley of - * Hewlett Packard. Rewritten from scratch when modularizing the removal - * policy implementation of Squid. - * - * 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 "store_heap_replacement.h" -#include "Store.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; - const 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; -} --- /dev/null Wed Feb 14 01:07:22 2007 +++ squid/src/repl/heap/store_repl_heap.cc Wed Feb 14 01:07:41 2007 @@ -0,0 +1,312 @@ + +/* + * $Id: store_repl_heap.cc,v 1.1.2.1 2002/10/12 03:01:09 rbcollins Exp $ + * + * DEBUG: section ? HEAP based removal policies + * AUTHOR: Henrik Nordstrom + * + * Based on the ideas of the heap policy implemented by John Dilley of + * Hewlett Packard. Rewritten from scratch when modularizing the removal + * policy implementation of Squid. + * + * 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 "store_heap_replacement.h" +#include "Store.h" + +REMOVALPOLICYCREATE createRemovalPolicy_heap; + +static int nr_heap_policies = 0; + +struct HeapPolicyData { + void setPolicyNode (StoreEntry *, void *) const; + RemovalPolicy *policy; + heap *theHeap; + 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 HeapPolicyData::heap_entry_type +heap_guessType(StoreEntry * entry, RemovalPolicyNode * node) +{ + if (node == &entry->repl) + return HeapPolicyData::TYPE_STORE_ENTRY; + if (entry->mem_obj && node == &entry->mem_obj->repl) + return HeapPolicyData::TYPE_STORE_MEM; + fatal("Heap Replacement: Unknown StoreEntry node type"); + return HeapPolicyData::TYPE_UNKNOWN; +} + +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 = (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->theHeap, entry); + heap->count += 1; + if (!heap->type) + heap->type = heap_guessType(entry, node); + /* Add a little more variance to the aging factor */ + heap->theHeap->age += heap->theHeap->age / 100000000; +} + +static void +heap_remove(RemovalPolicy * policy, StoreEntry * entry, + RemovalPolicyNode * node) +{ + HeapPolicyData *heap = (HeapPolicyData *)policy->_data; + heap_node *hnode = (heap_node *)node->data; + if (!hnode) + return; + heap_delete(heap->theHeap, hnode); + node->data = NULL; + heap->count -= 1; +} + +static void +heap_referenced(RemovalPolicy * policy, const StoreEntry * entry, + RemovalPolicyNode * node) +{ + HeapPolicyData *heap = (HeapPolicyData *)policy->_data; + heap_node *hnode = (heap_node *)node->data; + if (!hnode) + return; + heap_update(heap->theHeap, hnode, (StoreEntry *) entry); +} + +/** RemovalPolicyWalker **/ + +typedef struct _HeapWalkData HeapWalkData; +struct _HeapWalkData { + size_t current; +}; + +static const StoreEntry * +heap_walkNext(RemovalPolicyWalker * walker) +{ + HeapWalkData *heap_walk = (HeapWalkData *)walker->_data; + RemovalPolicy *policy = walker->_policy; + HeapPolicyData *heap = (HeapPolicyData *)policy->_data; + StoreEntry *entry; + if (heap_walk->current >= heap_nodes(heap->theHeap)) + return NULL; /* done */ + entry = (StoreEntry *) heap_peep(heap->theHeap, heap_walk->current++); + return entry; +} + +static void +heap_walkDone(RemovalPolicyWalker * walker) +{ + RemovalPolicy *policy = walker->_policy; + HeapPolicyData *heap = (HeapPolicyData *)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 = (HeapPolicyData *)policy->_data; + RemovalPolicyWalker *walker; + HeapWalkData *heap_walk; + heap->nwalkers += 1; + walker = cbdataAlloc(RemovalPolicyWalker); + heap_walk = (HeapWalkData *)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 = (HeapPurgeData *)walker->_data; + RemovalPolicy *policy = walker->_policy; + HeapPolicyData *heap = (HeapPolicyData *)policy->_data; + StoreEntry *entry; + heap_key age; + try_again: + if (!heap_nodes(heap->theHeap) > 0) + return NULL; /* done */ + age = heap_peepminkey(heap->theHeap); + entry = (StoreEntry *)heap_extractmin(heap->theHeap); + if (storeEntryLocked(entry)) { + linklistPush(&heap_walker->locked_entries, entry); + goto try_again; + } + heap_walker->min_age = age; + heap->setPolicyNode(entry, NULL); + return entry; +} + +static void +heap_purgeDone(RemovalPurgeWalker * walker) +{ + HeapPurgeData *heap_walker = (HeapPurgeData *)walker->_data; + RemovalPolicy *policy = walker->_policy; + HeapPolicyData *heap = (HeapPolicyData *)policy->_data; + StoreEntry *entry; + assert(strcmp(policy->_type, "heap") == 0); + assert(heap->nwalkers > 0); + heap->nwalkers -= 1; + if (heap_walker->min_age > 0) { + heap->theHeap->age = heap_walker->min_age; + debug(81, 3) ("heap_purgeDone: Heap age set to %f\n", + (double) heap->theHeap->age); + } + /* + * Reinsert the locked entries + */ + while ((entry = (StoreEntry *)linklistShift(&heap_walker->locked_entries))) { + heap_node *node = heap_insert(heap->theHeap, entry); + heap->setPolicyNode(entry, node); + } + safe_free(walker->_data); + cbdataFree(walker); +} + +static RemovalPurgeWalker * +heap_purgeInit(RemovalPolicy * policy, int max_scan) +{ + HeapPolicyData *heap = (HeapPolicyData *)policy->_data; + RemovalPurgeWalker *walker; + HeapPurgeData *heap_walk; + heap->nwalkers += 1; + walker = cbdataAlloc(RemovalPurgeWalker); + heap_walk = (HeapPurgeData *)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 = (HeapPolicyData *)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; + const char *keytype; + /* Allocate the needed structures */ + policy = cbdataAlloc(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; + } 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->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; +} --- squid/src/repl/lru/store_repl_lru.c Wed Feb 14 01:07:41 2007 +++ /dev/null Wed Feb 14 01:07:22 2007 @@ -1,308 +0,0 @@ - -/* - * $Id$ - * - * 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. - * - */ - -#include "squid.h" -#include "Store.h" - -REMOVALPOLICYCREATE createRemovalPolicy_lru; - -typedef struct _LruPolicyData LruPolicyData; -struct _LruPolicyData { - RemovalPolicy *policy; - dlink_list list; - 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 to clear the policy information - */ -static enum heap_entry_type -repl_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(lru->type) { \ - 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 int nr_lru_policies = 0; - -static void -lru_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) -{ - LruPolicyData *lru = policy->_data; - LruNode *lru_node; - assert(!node->data); - node->data = lru_node = memPoolAlloc(lru_node_pool); - dlinkAddTail(entry, &lru_node->node, &lru->list); - lru->count += 1; - if (!lru->type) - lru->type = repl_guessType(entry, node); -} - -static void -lru_remove(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) -{ - LruPolicyData *lru = policy->_data; - LruNode *lru_node = node->data; - if (!lru_node) - 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; - assert(lru_node->node.data == entry); - node->data = NULL; - dlinkDelete(&lru_node->node, &lru->list); - memPoolFree(lru_node_pool, lru_node); - lru->count -= 1; -} - -static void -lru_referenced(RemovalPolicy * policy, const StoreEntry * entry, - RemovalPolicyNode * node) -{ - LruPolicyData *lru = policy->_data; - LruNode *lru_node = node->data; - if (!lru_node) - return; - dlinkDelete(&lru_node->node, &lru->list); - dlinkAddTail((void *) entry, &lru_node->node, &lru->list); -} - -/** RemovalPolicyWalker **/ - -typedef struct _LruWalkData LruWalkData; -struct _LruWalkData { - LruNode *current; -}; - -static const StoreEntry * -lru_walkNext(RemovalPolicyWalker * walker) -{ - LruWalkData *lru_walk = walker->_data; - LruNode *lru_node = lru_walk->current; - if (!lru_node) - return NULL; - lru_walk->current = (LruNode *) lru_node->node.next; - return (StoreEntry *) lru_node->node.data; -} - -static void -lru_walkDone(RemovalPolicyWalker * walker) -{ - RemovalPolicy *policy = walker->_policy; - LruPolicyData *lru = policy->_data; - assert(strcmp(policy->_type, "lru") == 0); - assert(lru->nwalkers > 0); - lru->nwalkers -= 1; - safe_free(walker->_data); - cbdataFree(walker); -} - -static RemovalPolicyWalker * -lru_walkInit(RemovalPolicy * policy) -{ - LruPolicyData *lru = policy->_data; - RemovalPolicyWalker *walker; - LruWalkData *lru_walk; - lru->nwalkers += 1; - walker = cbdataAlloc(RemovalPolicyWalker); - lru_walk = xcalloc(1, sizeof(*lru_walk)); - walker->_policy = policy; - walker->_data = lru_walk; - walker->Next = lru_walkNext; - walker->Done = lru_walkDone; - lru_walk->current = (LruNode *) lru->list.head; - return walker; -} - -/** RemovalPurgeWalker **/ - -typedef struct _LruPurgeData LruPurgeData; -struct _LruPurgeData { - LruNode *current; - LruNode *start; -}; - -static StoreEntry * -lru_purgeNext(RemovalPurgeWalker * walker) -{ - LruPurgeData *lru_walker = walker->_data; - RemovalPolicy *policy = walker->_policy; - LruPolicyData *lru = policy->_data; - LruNode *lru_node; - StoreEntry *entry; - try_again: - lru_node = lru_walker->current; - if (!lru_node || walker->scanned >= walker->max_scan) - 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; - } - 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; - } - memPoolFree(lru_node_pool, lru_node); - lru->count -= 1; - SET_POLICY_NODE(entry, NULL); - return entry; -} - -static void -lru_purgeDone(RemovalPurgeWalker * walker) -{ - RemovalPolicy *policy = walker->_policy; - LruPolicyData *lru = policy->_data; - assert(strcmp(policy->_type, "lru") == 0); - assert(lru->nwalkers > 0); - lru->nwalkers -= 1; - safe_free(walker->_data); - cbdataFree(walker); -} - -static RemovalPurgeWalker * -lru_purgeInit(RemovalPolicy * policy, int max_scan) -{ - LruPolicyData *lru = policy->_data; - RemovalPurgeWalker *walker; - LruPurgeData *lru_walk; - lru->nwalkers += 1; - walker = cbdataAlloc(RemovalPurgeWalker); - lru_walk = xcalloc(1, sizeof(*lru_walk)); - walker->_policy = policy; - walker->_data = lru_walk; - walker->max_scan = max_scan; - walker->Next = lru_purgeNext; - walker->Done = lru_purgeDone; - lru_walk->start = lru_walk->current = (LruNode *) lru->list.head; - return walker; -} - -static void -lru_stats(RemovalPolicy * policy, StoreEntry * sentry) -{ - LruPolicyData *lru = policy->_data; - LruNode *lru_node = (LruNode *) lru->list.head; - - 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)); - } -} - -static void -lru_free(RemovalPolicy * policy) -{ - LruPolicyData *lru = policy->_data; - /* Make some verification of the policy state */ - assert(strcmp(policy->_type, "lru") == 0); - assert(lru->nwalkers); - assert(lru->count); - /* Ok, time to destroy this policy */ - safe_free(policy->_data); - memset(policy, 0, sizeof(*policy)); - cbdataFree(policy); -} - -RemovalPolicy * -createRemovalPolicy_lru(wordlist * args) -{ - RemovalPolicy *policy; - LruPolicyData *lru_data; - /* 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); - } - /* Allocate the needed structures */ - lru_data = xcalloc(1, sizeof(*lru_data)); - policy = cbdataAlloc(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; -} --- /dev/null Wed Feb 14 01:07:22 2007 +++ squid/src/repl/lru/store_repl_lru.cc Wed Feb 14 01:07:41 2007 @@ -0,0 +1,312 @@ + +/* + * $Id: store_repl_lru.cc,v 1.1.2.1 2002/10/12 03:01:13 rbcollins 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. + * + */ + +#include "squid.h" +#include "Store.h" + +REMOVALPOLICYCREATE createRemovalPolicy_lru; + +struct LruPolicyData { + void setPolicyNode (StoreEntry *, void *) const; + RemovalPolicy *policy; + dlink_list list; + 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 to clear the policy information + */ +static enum LruPolicyData::heap_entry_type +repl_guessType(StoreEntry * entry, RemovalPolicyNode * node) +{ + if (node == &entry->repl) + return LruPolicyData::TYPE_STORE_ENTRY; + if (entry->mem_obj && node == &entry->mem_obj->repl) + return LruPolicyData::TYPE_STORE_MEM; + fatal("Heap Replacement: Unknown StoreEntry node type"); + return LruPolicyData::TYPE_UNKNOWN; +} + +void +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; + } +} + +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 int nr_lru_policies = 0; + +static void +lru_add(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) +{ + LruPolicyData *lru = (LruPolicyData *)policy->_data; + LruNode *lru_node; + assert(!node->data); + node->data = lru_node = (LruNode *)memPoolAlloc(lru_node_pool); + dlinkAddTail(entry, &lru_node->node, &lru->list); + lru->count += 1; + if (!lru->type) + lru->type = repl_guessType(entry, node); +} + +static void +lru_remove(RemovalPolicy * policy, StoreEntry * entry, RemovalPolicyNode * node) +{ + LruPolicyData *lru = (LruPolicyData *)policy->_data; + LruNode *lru_node = (LruNode *)node->data; + if (!lru_node) + 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; + assert(lru_node->node.data == entry); + node->data = NULL; + dlinkDelete(&lru_node->node, &lru->list); + memPoolFree(lru_node_pool, lru_node); + lru->count -= 1; +} + +static void +lru_referenced(RemovalPolicy * policy, const StoreEntry * entry, + RemovalPolicyNode * node) +{ + LruPolicyData *lru = (LruPolicyData *)policy->_data; + LruNode *lru_node = (LruNode *)node->data; + if (!lru_node) + return; + dlinkDelete(&lru_node->node, &lru->list); + dlinkAddTail((void *) entry, &lru_node->node, &lru->list); +} + +/** RemovalPolicyWalker **/ + +typedef struct _LruWalkData LruWalkData; +struct _LruWalkData { + LruNode *current; +}; + +static const StoreEntry * +lru_walkNext(RemovalPolicyWalker * walker) +{ + LruWalkData *lru_walk = (LruWalkData *)walker->_data; + LruNode *lru_node = lru_walk->current; + if (!lru_node) + return NULL; + lru_walk->current = (LruNode *) lru_node->node.next; + return (StoreEntry *) lru_node->node.data; +} + +static void +lru_walkDone(RemovalPolicyWalker * walker) +{ + RemovalPolicy *policy = walker->_policy; + LruPolicyData *lru = (LruPolicyData *)policy->_data; + assert(strcmp(policy->_type, "lru") == 0); + assert(lru->nwalkers > 0); + lru->nwalkers -= 1; + safe_free(walker->_data); + cbdataFree(walker); +} + +static RemovalPolicyWalker * +lru_walkInit(RemovalPolicy * policy) +{ + LruPolicyData *lru = (LruPolicyData *)policy->_data; + RemovalPolicyWalker *walker; + LruWalkData *lru_walk; + lru->nwalkers += 1; + walker = cbdataAlloc(RemovalPolicyWalker); + lru_walk = (LruWalkData *)xcalloc(1, sizeof(*lru_walk)); + walker->_policy = policy; + walker->_data = lru_walk; + walker->Next = lru_walkNext; + walker->Done = lru_walkDone; + lru_walk->current = (LruNode *) lru->list.head; + return walker; +} + +/** RemovalPurgeWalker **/ + +typedef struct _LruPurgeData LruPurgeData; +struct _LruPurgeData { + LruNode *current; + LruNode *start; +}; + +static StoreEntry * +lru_purgeNext(RemovalPurgeWalker * walker) +{ + LruPurgeData *lru_walker = (LruPurgeData *)walker->_data; + RemovalPolicy *policy = walker->_policy; + LruPolicyData *lru = (LruPolicyData *)policy->_data; + LruNode *lru_node; + StoreEntry *entry; + try_again: + lru_node = lru_walker->current; + if (!lru_node || walker->scanned >= walker->max_scan) + 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; + } + 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; + } + memPoolFree(lru_node_pool, lru_node); + lru->count -= 1; + lru->setPolicyNode(entry, NULL); + return entry; +} + +static void +lru_purgeDone(RemovalPurgeWalker * walker) +{ + RemovalPolicy *policy = walker->_policy; + LruPolicyData *lru = (LruPolicyData *)policy->_data; + assert(strcmp(policy->_type, "lru") == 0); + assert(lru->nwalkers > 0); + lru->nwalkers -= 1; + safe_free(walker->_data); + cbdataFree(walker); +} + +static RemovalPurgeWalker * +lru_purgeInit(RemovalPolicy * policy, int max_scan) +{ + LruPolicyData *lru = (LruPolicyData *)policy->_data; + RemovalPurgeWalker *walker; + LruPurgeData *lru_walk; + lru->nwalkers += 1; + walker = cbdataAlloc(RemovalPurgeWalker); + lru_walk = (LruPurgeData *)xcalloc(1, sizeof(*lru_walk)); + walker->_policy = policy; + walker->_data = lru_walk; + walker->max_scan = max_scan; + walker->Next = lru_purgeNext; + walker->Done = lru_purgeDone; + lru_walk->start = lru_walk->current = (LruNode *) lru->list.head; + return walker; +} + +static void +lru_stats(RemovalPolicy * policy, StoreEntry * sentry) +{ + LruPolicyData *lru = (LruPolicyData *)policy->_data; + LruNode *lru_node = (LruNode *) lru->list.head; + + 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)); + } +} + +static void +lru_free(RemovalPolicy * policy) +{ + LruPolicyData *lru = (LruPolicyData *)policy->_data; + /* Make some verification of the policy state */ + assert(strcmp(policy->_type, "lru") == 0); + assert(lru->nwalkers); + assert(lru->count); + /* Ok, time to destroy this policy */ + safe_free(policy->_data); + memset(policy, 0, sizeof(*policy)); + cbdataFree(policy); +} + +RemovalPolicy * +createRemovalPolicy_lru(wordlist * args) +{ + RemovalPolicy *policy; + LruPolicyData *lru_data; + /* 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); + } + /* Allocate the needed structures */ + lru_data = (LruPolicyData *)xcalloc(1, sizeof(*lru_data)); + policy = cbdataAlloc(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; +}