Enhanced cache replacement policies

        I have completed the implementation, testing, validation, and
documentation of our enhancement to the Squid cache replacement policy.
I reported on this work as a work in progress at the recent WCW, and
have updated the document describing the work. The report is at
http://www.hpl.hp.com/personal/John_Dilley/caching/wcw.html and a
description of the replacement policies is documented in an HPL TR,
http://www.hpl.hp.com/techreports/98/HPL-98-173.html.

        I've had a copy of the 2.2.STABLE3 proxy with these policies up
and serving local cache requests for a while now and it is doing fine.
I have also tested the policies with a workload driver and there have
been no crashes or other anomalies (at least not recently :-). Enclosed
below is a shar with the patch to squid-2.2.STABLE3. It includes:

    - The modifications to the source (store*.c mainly).
    - Two new files, include/heap.h and lib/heap.c, that implement a
      heap for the metadata instead of the LRU linked list.
    - Modifications to the squid.conf file to select the policy.

I have not changed the external documentation on the squid web pages,
but at some point that would be useful, if these policies are accepted
by the community as a useful piece of work. So far they have shown to
be more efficient in CPU resource consumption than the LRU list (even
though they are a heap not a linked list), and yield better hit rate
and/or byte hit rate than LRU. I have tested on both Linux and HP-UX.

        Please have a look over this package and let me know if you have
any questions, concerns, or suggestions. I hope this turns out to be a
useful enhancement to Squid! Best regards,

                             -- jad --
                          John Dilley <jad@hpl.hp.com>

#!/bin/sh
# This is HPL_REPL.shar, a shell archive (produced by GNU sharutils 4.2)
# To extract the files from this archive, save it to some FILE, remove
# everything before the `!/bin/sh' line above, then type `sh FILE'.
#
# Made on 1999-06-10 11:09 PDT by <jad@hpl.hp.com>.
# Source directory was `/home/jad/work/Squid/squid-2.2.STABLE3-jad'.
#
# Existing files will *not* be overwritten unless `-c' is specified.
# This format requires very little intelligence at unshar time.
# "if test", "echo", "mkdir", and "sed" may be needed.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 454 -rw-r--r-- jad.README
# 50479 -rw-r--r-- jad.diff
# 4865 -rw-r--r-- include/heap.h
# 13250 -rw-r--r-- lib/heap.c
#
echo=echo
if mkdir _sh02595; then
  $echo 'x -' 'creating lock directory'
else
  $echo 'failed to create lock directory'
  exit 1
fi
# ============= jad.README ==============
if test -f 'jad.README' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'jad.README' '(file already exists)'
else
  $echo 'x -' extracting 'jad.README' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'jad.README' &&
XTo build the version of Squid using the HPL Cache Replacement Policies,
Xfollow these steps:
X - start with a squid-2.2.STABLE3 distribution
X - move the tar file jad.tar into that directory and unpack it to create
X jad.README (this file), jad.diff, include/heap.h, lib/heap.c
X - cd into the squid-2.2.STABLE3 directory
X - run patch -p1 < jad.diff
X - run CFLAGS="-g -O2 -Wall -DHPL_REPL" ./configure
X - touch makefile
X - make clean all
SHAR_EOF
  : || $echo 'restore of' 'jad.README' 'failed'
fi
# ============= jad.diff ==============
if test -f 'jad.diff' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'jad.diff' '(file already exists)'
else
  $echo 'x -' extracting 'jad.diff' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'jad.diff' &&
Xdiff -r -u squid-2.2.STABLE3/lib/Makefile.in squid-2.2.STABLE3-jad/lib/Makefile.in
X--- squid-2.2.STABLE3/lib/Makefile.in Mon Aug 17 16:01:24 1998
X+++ squid-2.2.STABLE3-jad/lib/Makefile.in Wed Jun 2 15:30:30 1999
X@@ -37,6 +37,7 @@
X Array.o \
X Stack.o \
X hash.o \
X+ heap.o \
X $(LIBOBJS)
X REGEXOBJS = GNUregex.o
X DLMALLOCOBJS = dlmalloc.o
Xdiff -r -u squid-2.2.STABLE3/makefile.in squid-2.2.STABLE3-jad/makefile.in
X--- squid-2.2.STABLE3/makefile.in Fri Jan 29 15:47:41 1999
X+++ squid-2.2.STABLE3-jad/makefile.in Tue Jun 1 10:19:59 1999
X@@ -8,6 +8,7 @@
X INSTALL = @INSTALL@
X INSTALL_PROGRAM = @INSTALL_PROGRAM@
X INSTALL_DATA = @INSTALL_DATA@
X+CFLAGS = @CFLAGS@ -DHPL_REPL
X SHELL = /bin/sh
X
X # Where to install
Xdiff -r -u squid-2.2.STABLE3/src/cache_cf.c squid-2.2.STABLE3-jad/src/cache_cf.c
X--- squid-2.2.STABLE3/src/cache_cf.c Sun Apr 18 17:14:34 1999
X+++ squid-2.2.STABLE3-jad/src/cache_cf.c Fri Jun 4 08:55:37 1999
X@@ -303,10 +303,14 @@
X debug(3, 0) ("WARNING: resetting 'maximum_single_addr_tries to 1\n");
X Config.retry.maxtries = 1;
X }
X+ #ifdef HPL_REPL
X+ /* The non-LRU policies do not use referenceAge */
X+ #else /* HPL_REPL */
X if (Config.referenceAge < 300) {
X debug(3, 0) ("WARNING: resetting 'reference_age' to 1 week\n");
X Config.referenceAge = 86400 * 7;
X }
X+ #endif /* HPL_REPL */
X requirePathnameExists("MIME Config Table", Config.mimeTablePathname);
X requirePathnameExists("cache_dns_program", Config.Program.dnsserver);
X requirePathnameExists("unlinkd_program", Config.Program.unlinkd);
Xdiff -r -u squid-2.2.STABLE3/src/cf.data.pre squid-2.2.STABLE3-jad/src/cf.data.pre
X--- squid-2.2.STABLE3/src/cf.data.pre Fri May 7 14:44:11 1999
X+++ squid-2.2.STABLE3-jad/src/cf.data.pre Sat Jun 5 22:51:47 1999
X@@ -494,12 +494,17 @@
X DEFAULT: 95
X LOC: Config.Swap.highWaterMark
X DOC_START
X- The low- and high-water marks for cache LRU replacement. LRU
X- replacement begins when the high-water mark is reached and ends
X- when enough objects have been removed and the low-water mark is
X- reached. Defaults are 90% and 95%. If you have a large cache, 5%
X- could be hundreds of MB. If this is the case you may wish to
X- set these numbers closer together.
X+
X+ The low- and high-water marks for cache object replacement.
X+ Replacement begins when the swap (disk) usage is above the
X+ low-water mark and attempts to maintain utilization near the
X+ low-water mark. As swap utilization gets close to high-water
X+ mark object eviction becomes more aggressive. If utilization is
X+ close to the low-water mark less replacement is done each time.
X+
X+ Defaults are 90% and 95%. If you have a large cache, 5% could be
X+ hundreds of MB. If this is the case you may wish to set these
X+ numbers closer together.
X
X cache_swap_low 90
X cache_swap_high 95
X@@ -518,6 +523,10 @@
X hits). If you wish to increase speed more than your want to
X save bandwidth you should leave this low.
X
X+ NOTE: if using the LFUDA replacement policy you should increase
X+ this value to maximize the byte hit rate improvement of LFUDA!
X+ See replacement_policy below for a discussion of this policy.
X+
X maximum_object_size 4096 KB
X DOC_END
X
X@@ -1092,6 +1101,49 @@
X DOC_END
X
X
X+NAME: replacement_policy
X+TYPE: string
X+LOC: Config.replPolicy
X+DEFAULT: LFUDA
X+IFDEF: HPL_REPL
X+DOC_START
X+ The cache replacement policy parameter determines which objects
X+ are evicted (replaced) when disk space is needed. Squid used to
X+ have only a single replacement policy, LRU. But when built with
X+ -DHPL_REPL you can choose between two new, enhanced policies:
X+
X+ GDSF: Greedy-Dual Size Frequency
X+ LFUDA: Least Frequently Used with Dynamic Aging
X+
X+ Both of these policies are frequency based rather than recency
X+ based, and perform better than LRU.
X+
X+ The GDSF policy optimizes object hit rate by keeping smaller
X+ popular objects in cache so it has a better chance of getting a
X+ hit. It achieves a lower byte hit rate than LFUDA though since
X+ it evicts larger (possibly popular) objects.
X+
X+ The LFUDA policy keeps popular objects in cache regardless of
X+ their size and thus optimizes byte hit rate at the expense of
X+ hit rate since one large, popular object will prevent many
X+ smaller, slightly less popular objects from being cached.
X+
X+ Both policies utilize a dynamic aging mechanism that prevents
X+ cache pollution that can otherwise occur with frequency-based
X+ replacement policies.
X+
X+ NOTE: if using the LFUDA replacement policy you should increase
X+ the value of maximum_object_size above its default of 4096 KB to
X+ to maximize the potential byte hit rate improvement of LFUDA.
X+
X+ For more information about these cache replacement policies see
X+ http://www.hpl.hp.com/personal/John_Dilley/caching/wcw.html and
X+ http://fog.hpl.external.hp.com/techreports/98/HPL-98-173.html.
X+
X+replacement_policy LFUDA
X+DOC_END
X+
X+
X NAME: reference_age
X TYPE: time_t
X LOC: Config.referenceAge
X@@ -1113,6 +1165,9 @@
X 3.5 days
X 4 months
X 2.2 hours
X+
X+ NOTE: this parameter is not used when using the enhanced
X+ replacement policies, GDSH or LFUDA.
X
X reference_age 1 month
X DOC_END
Xdiff -r -u squid-2.2.STABLE3/src/client_side.c squid-2.2.STABLE3-jad/src/client_side.c
X--- squid-2.2.STABLE3/src/client_side.c Mon May 10 09:00:40 1999
X+++ squid-2.2.STABLE3-jad/src/client_side.c Tue Jun 1 09:47:56 1999
X@@ -46,6 +46,9 @@
X #include <ip_nat.h>
X #endif
X
X+#ifdef HPL_REPL
X+#include "heap.h"
X+#endif /* HPL_REPL */
X
X
X #if LINGERING_CLOSE
X@@ -314,6 +317,17 @@
X entry->lastmod = http->old_entry->lastmod;
X debug(33, 5) ("clientProcessExpired: lastmod %d\n", (int) entry->lastmod);
X entry->refcount++; /* EXPIRED CASE */
X+#ifdef HPL_REPL
X+ /*
X+ * Update the position of this object in the store heap and memory
X+ * heap. The cache replacement policy uses refcount to determie the
X+ * priority value of the object.
X+ */
X+ if (entry->node)
X+ heap_update(store_heap, entry->node, entry);
X+ if (entry->mem_obj->node)
X+ heap_update(inmem_heap, entry->mem_obj->node, entry);
X+#endif /* HPL_REPL */
X http->entry = entry;
X http->out.offset = 0;
X fwdStart(http->conn->fd, http->entry, http->request,
X@@ -399,6 +413,13 @@
X storeUnlockObject(entry);
X entry = http->entry = http->old_entry;
X entry->refcount++;
X+#ifdef HPL_REPL
X+ /* Update the position of this object in the store and memory heaps. */
X+ if (entry->node)
X+ heap_update(store_heap, entry->node, entry);
X+ if (entry->mem_obj->node)
X+ heap_update(inmem_heap, entry->mem_obj->node, entry);
X+#endif /* HPL_REPL */
X } else if (STORE_PENDING == entry->store_status && 0 == status) {
X debug(33, 3) ("clientHandleIMSReply: Incomplete headers for '%s'\n", url);
X if (size >= CLIENT_SOCK_SZ) {
X@@ -410,6 +431,13 @@
X storeUnlockObject(entry);
X entry = http->entry = http->old_entry;
X entry->refcount++;
X+#ifdef HPL_REPL
X+ /* Update the position of this object in the store and memory heaps. */
X+ if (entry->node)
X+ heap_update(store_heap, entry->node, entry);
X+ if (entry->mem_obj->node)
X+ heap_update(inmem_heap, entry->mem_obj->node, entry);
X+#endif /* HPL_REPL */
X /* continue */
X } else {
X storeClientCopy(entry,
X@@ -451,6 +479,13 @@
X if (HTTP_NOT_MODIFIED == mem->reply->sline.status) {
X http->old_entry->timestamp = squid_curtime;
X http->old_entry->refcount++;
X+#ifdef HPL_REPL
X+ /* Update the position of this object in the store and memory heaps. */
X+ if (http->old_entry->node)
X+ heap_update(store_heap, http->old_entry->node, http->old_entry);
X+ if (http->old_entry->mem_obj->node)
X+ heap_update(inmem_heap, http->old_entry->mem_obj->node, http->old_entry);
X+#endif /* HPL_REPL */
X http->log_type = LOG_TCP_REFRESH_HIT;
X }
X storeUnregister(http->old_entry, http);
X@@ -1810,6 +1845,13 @@
X delaySetStoreClient(http->entry, http, delayClient(r));
X #endif
X http->entry->refcount++;
X+#ifdef HPL_REPL
X+ /* Update the position of this object in the store and memory heaps. */
X+ if (http->entry->node)
X+ heap_update(store_heap, http->entry->node, http->entry);
X+ if (http->entry->mem_obj->node)
X+ heap_update(inmem_heap, http->entry->mem_obj->node, http->entry);
X+#endif /* HPL_REPL */
X storeClientCopy(http->entry,
X http->out.offset,
X http->out.offset,
X@@ -1865,6 +1907,13 @@
X assert(http->out.offset == 0);
X http->entry = clientCreateStoreEntry(http, r->method, r->flags);
X http->entry->refcount++;
X+#ifdef HPL_REPL
X+ /* Update the position of this object in the store and memory heaps. */
X+ if (http->entry->node)
X+ heap_update(store_heap, http->entry->node, http->entry);
X+ if (http->entry->mem_obj->node)
X+ heap_update(inmem_heap, http->entry->mem_obj->node, http->entry);
X+#endif /* HPL_REPL */
X if (http->redirect.status) {
X HttpReply *rep = httpReplyCreate();
X storeReleaseRequest(http->entry);
Xdiff -r -u squid-2.2.STABLE3/src/globals.h squid-2.2.STABLE3-jad/src/globals.h
X--- squid-2.2.STABLE3/src/globals.h Fri Feb 12 14:32:17 1999
X+++ squid-2.2.STABLE3-jad/src/globals.h Tue Jun 1 09:55:44 1999
X@@ -30,6 +30,9 @@
X * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
X *
X */
X+#ifdef HPL_REPL
X+#include "heap.h"
X+#endif /* HPL_REPL */
X
X extern FILE *debug_log; /* NULL */
X extern FILE *cache_useragent_log; /* NULL */
X@@ -124,7 +127,12 @@
X extern double current_dtime;
X extern int store_hash_buckets; /* 0 */
X extern hash_table *store_table; /* NULL */
X+#ifdef HPL_REPL
X+extern heap_p store_heap;
X+extern heap_p inmem_heap;
X+#else /* HPL_REPL */
X extern dlink_list store_list;
X+#endif /* HPL_REPL */
X extern dlink_list ClientActiveRequests;
X extern const String StringNull; /* { 0, 0, NULL } */
X extern const MemBuf MemBufNull; /* MemBufNULL */
Xdiff -r -u squid-2.2.STABLE3/src/stat.c squid-2.2.STABLE3-jad/src/stat.c
X--- squid-2.2.STABLE3/src/stat.c Wed Apr 7 16:27:31 1999
X+++ squid-2.2.STABLE3-jad/src/stat.c Fri Jun 4 08:57:03 1999
X@@ -489,8 +489,12 @@
X store_swap_size);
X storeAppendPrintf(sentry, "\tStorage Mem size:\t%d KB\n",
X (int) (store_mem_size >> 10));
X+ #ifdef HPL_REPL
X+ /* The non-LRU policies do not use referenceAge */
X+ #else /* HPL_REPL */
X storeAppendPrintf(sentry, "\tStorage LRU Expiration Age:\t%6.2f days\n",
X (double) storeExpiredReferenceAge() / 86400.0);
X+ #endif /* HPL_REPL */
X storeAppendPrintf(sentry, "\tMean Object Size:\t%0.2f KB\n",
X n_disk_objects ? (double) store_swap_size / n_disk_objects : 0.0);
X storeAppendPrintf(sentry, "\tRequests given to unlinkd:\t%d\n",
Xdiff -r -u squid-2.2.STABLE3/src/store.c squid-2.2.STABLE3-jad/src/store.c
X--- squid-2.2.STABLE3/src/store.c Mon May 10 09:02:04 1999
X+++ squid-2.2.STABLE3-jad/src/store.c Sun Jun 6 11:36:31 1999
X@@ -21,12 +21,12 @@
X * it under the terms of the GNU General Public License as published by
X * the Free Software Foundation; either version 2 of the License, or
X * (at your option) any later version.
X- *
X+ *
X * This program is distributed in the hope that it will be useful,
X * but WITHOUT ANY WARRANTY; without even the implied warranty of
X * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
X * GNU General Public License for more details.
X- *
X+ *
X * You should have received a copy of the GNU General Public License
X * along with this program; if not, write to the Free Software
X * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
X@@ -35,6 +35,10 @@
X
X #include "squid.h"
X
X+#ifdef HPL_REPL
X+#include "heap.h"
X+#endif /* HPL_REPL */
X+
X #define REBUILD_TIMESTAMP_DELTA_MAX 2
X
X #define STORE_IN_MEM_BUCKETS (229)
X@@ -92,7 +96,14 @@
X /*
X * local variables
X */
X+#ifdef HPL_REPL
X+/*
X+ * The heap equivalent of inmem_list, inmem_heap, is in globals.c so other
X+ * modules can access it when updating object metadata (e.g., refcount)
X+ */
X+#else /* HPL_REPL */
X static dlink_list inmem_list;
X+#endif /* HPL_REPL */
X static int store_pages_max = 0;
X static int store_swap_high = 0;
X static int store_swap_low = 0;
X@@ -132,7 +143,7 @@
X {
X MemObject *mem = e->mem_obj;
X const Ctx ctx = ctx_enter(mem->url);
X- debug(20, 3) ("destroy_MemObject: destroying %p\n", mem);
X+ debug(20, 4) ("destroy_MemObject: destroying %p\n", mem);
X e->mem_obj = NULL;
X if (!shutting_down)
X assert(mem->swapout.fd == -1);
X@@ -161,7 +172,7 @@
X destroy_StoreEntry(void *data)
X {
X StoreEntry *e = data;
X- debug(20, 3) ("destroy_StoreEntry: destroying %p\n", e);
X+ debug(20, 4) ("destroy_StoreEntry: destroying %p\n", e);
X assert(e != NULL);
X if (e->mem_obj)
X destroy_MemObject(e);
X@@ -175,18 +186,35 @@
X void
X storeHashInsert(StoreEntry * e, const cache_key * key)
X {
X- debug(20, 3) ("storeHashInsert: Inserting Entry %p key '%s'\n",
X+ debug(20, 4) ("storeHashInsert: Inserting Entry %p key '%s'\n",
X e, storeKeyText(key));
X e->key = storeKeyDup(key);
X hash_join(store_table, (hash_link *) e);
X+ #ifdef HPL_REPL
X+ if (EBIT_TEST(e->flags, ENTRY_SPECIAL)) {
X+ debug(20, 4) ("storeHashInsert: not inserting special into store heap\n");
X+ } else {
X+ e->node = heap_insert(store_heap, e);
X+ debug(20, 4) ("storeHashInsert: inserted node 0x%x\n", e->node);
X+ }
X+ #else /* HPL_REPL */
X dlinkAdd(e, &e->lru, &store_list);
X+ #endif /* HPL_REPL */
X }
X
X static void
X storeHashDelete(StoreEntry * e)
X {
X hash_remove_link(store_table, (hash_link *) e);
X+ #ifdef HPL_REPL
X+ if (e->node) {
X+ debug(20, 4) ("storeHashDelete: deleting node 0x%x\n", e->node);
X+ heap_delete(store_heap, e->node);
X+ e->node = 0;
X+ }
X+ #else /* HPL_REPL */
X dlinkDelete(&e->lru, &store_list);
X+ #endif /* HPL_REPL */
X storeKeyFree(e->key);
X e->key = NULL;
X }
X@@ -201,7 +229,7 @@
X {
X if (e->mem_obj == NULL)
X return;
X- debug(20, 3) ("storePurgeMem: Freeing memory-copy of %s\n",
X+ debug(20, 4) ("storePurgeMem: Freeing memory-copy of %s\n",
X storeKeyText(e->key));
X storeSetMemStatus(e, NOT_IN_MEMORY);
X destroy_MemObject(e);
X@@ -213,10 +241,19 @@
X storeLockObject(StoreEntry * e)
X {
X if (e->lock_count++ == 0) {
X+ #ifdef HPL_REPL
X+ /* there is no reason to take any action here.
X+ Squid by default is moving locked objects to the end of the LRU
X+ list to keep them from getting bumped into by the replacement
X+ algorithm. We can't do that so we will just have to handle them.
X+ */
X+ debug(20, 4) ("storeLockObject: just locked node 0x%x\n", e->node);
X+ #else /* HPL_REPL */
X dlinkDelete(&e->lru, &store_list);
X dlinkAdd(e, &e->lru, &store_list);
X+ #endif /* HPL_REPL */
X }
X- debug(20, 3) ("storeLockObject: key '%s' count=%d\n",
X+ debug(20, 4) ("storeLockObject: key '%s' count=%d\n",
X storeKeyText(e->key), (int) e->lock_count);
X e->lastref = squid_curtime;
X }
X@@ -243,7 +280,7 @@
X storeUnlockObject(StoreEntry * e)
X {
X e->lock_count--;
X- debug(20, 3) ("storeUnlockObject: key '%s' count=%d\n",
X+ debug(20, 4) ("storeUnlockObject: key '%s' count=%d\n",
X storeKeyText(e->key), e->lock_count);
X if (e->lock_count)
X return (int) e->lock_count;
X@@ -259,14 +296,22 @@
X } else {
X storePurgeMem(e);
X if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
X+ #ifdef HPL_REPL
X+ /*
X+ * Squid/LRU is moving things around in the linked list in order
X+ * to keep from bumping into them when purging from the LRU list.
X+ */
X+ debug(20, 4) ("storeUnlockObject: purged private node 0x%x\n", e->node);
X+ #else /* HPL_REPL */
X dlinkDelete(&e->lru, &store_list);
X dlinkAddTail(e, &e->lru, &store_list);
X+ #endif /* HPL_REPL */
X }
X }
X return 0;
X }
X
X-/* Lookup an object in the cache.
X+/* Lookup an object in the cache.
X * return just a reference to object, don't start swapping in yet. */
X StoreEntry *
X storeGet(const cache_key * key)
X@@ -332,10 +377,14 @@
X * If RELEASE_REQUEST is set, then ENTRY_CACHABLE should not
X * be set, and storeSetPublicKey() should not be called.
X */
X+#ifdef HPL_REPL_DEBUG
X+ if (EBIT_TEST(e->flags, RELEASE_REQUEST))
X+ debug(20, 1) ("assertion failed: RELEASE key %s, url %s\n", e->key, mem->url);
X+#endif /* HPL_REPL */
X assert(!EBIT_TEST(e->flags, RELEASE_REQUEST));
X newkey = storeKeyPublic(mem->url, mem->method);
X if ((e2 = (StoreEntry *) hash_lookup(store_table, newkey))) {
X- debug(20, 3) ("storeSetPublicKey: Making old '%s' private.\n", mem->url);
X+ debug(20, 4) ("storeSetPublicKey: Making old '%s' private.\n", mem->url);
X storeSetPrivateKey(e2);
X storeRelease(e2);
X newkey = storeKeyPublic(mem->url, mem->method);
X@@ -399,7 +448,7 @@
X assert(len >= 0);
X assert(e->store_status == STORE_PENDING);
X if (len) {
X- debug(20, 5) ("storeAppend: appending %d bytes for '%s'\n",
X+ debug(20, 6) ("storeAppend: appending %d bytes for '%s'\n",
X len,
X storeKeyText(e->key));
X storeGetMemSpace(len);
X@@ -484,25 +533,25 @@
X {
X #if CACHE_ALL_METHODS
X if (e->mem_obj->method != METHOD_GET) {
X- debug(20, 2) ("storeCheckCachable: NO: non-GET method\n");
X+ debug(20, 3) ("storeCheckCachable: NO: non-GET method\n");
X store_check_cachable_hist.no.non_get++;
X } else
X #endif
X if (!EBIT_TEST(e->flags, ENTRY_CACHABLE)) {
X- debug(20, 2) ("storeCheckCachable: NO: not cachable\n");
X+ debug(20, 3) ("storeCheckCachable: NO: not cachable\n");
X store_check_cachable_hist.no.not_entry_cachable++;
X } else if (EBIT_TEST(e->flags, RELEASE_REQUEST)) {
X- debug(20, 2) ("storeCheckCachable: NO: release requested\n");
X+ debug(20, 3) ("storeCheckCachable: NO: release requested\n");
X store_check_cachable_hist.no.release_request++;
X } else if (e->store_status == STORE_OK && EBIT_TEST(e->flags, ENTRY_BAD_LENGTH)) {
X- debug(20, 2) ("storeCheckCachable: NO: wrong content-length\n");
X+ debug(20, 3) ("storeCheckCachable: NO: wrong content-length\n");
X store_check_cachable_hist.no.wrong_content_length++;
X } else if (EBIT_TEST(e->flags, ENTRY_NEGCACHED)) {
X debug(20, 3) ("storeCheckCachable: NO: negative cached\n");
X store_check_cachable_hist.no.negative_cached++;
X return 0; /* avoid release call below */
X } else if (e->mem_obj->inmem_hi > Config.Store.maxObjectSize) {
X- debug(20, 2) ("storeCheckCachable: NO: too big\n");
X+ debug(20, 3) ("storeCheckCachable: NO: too big\n");
X store_check_cachable_hist.no.too_big++;
X } else if (EBIT_TEST(e->flags, KEY_PRIVATE)) {
X debug(20, 3) ("storeCheckCachable: NO: private key\n");
X@@ -515,15 +564,22 @@
X */
X return 1;
X } else if (storeTooManyDiskFilesOpen()) {
X- debug(20, 2) ("storeCheckCachable: NO: too many disk files open\n");
X+ debug(20, 3) ("storeCheckCachable: NO: too many disk files open\n");
X store_check_cachable_hist.no.too_many_open_files++;
X } else if (fdNFree() < RESERVED_FD) {
X- debug(20, 2) ("storeCheckCachable: NO: too many FD's open\n");
X+ debug(20, 3) ("storeCheckCachable: NO: too many FD's open\n");
X store_check_cachable_hist.no.too_many_open_fds++;
X+#ifdef HPL_REPL
X+ /*
X+ * With the HPL replacement policies a low reference age should not
X+ * prevent cacheability of an object. We do not use LRU age at all.
X+ */
X+#else /* HPL_REPL */
X } else if (storeExpiredReferenceAge() < 300) {
X- debug(20, 2) ("storeCheckCachable: NO: LRU Age = %d\n",
X+ debug(20, 3) ("storeCheckCachable: NO: LRU Age = %d\n",
X storeExpiredReferenceAge());
X store_check_cachable_hist.no.lru_age_too_low++;
X+#endif /* HPL_REPL */
X } else {
X store_check_cachable_hist.yes.Default++;
X return 1;
X@@ -566,7 +622,7 @@
X void
X storeComplete(StoreEntry * e)
X {
X- debug(20, 3) ("storeComplete: '%s'\n", storeKeyText(e->key));
X+ debug(20, 4) ("storeComplete: '%s'\n", storeKeyText(e->key));
X if (e->store_status != STORE_PENDING) {
X /*
X * if we're not STORE_PENDING, then probably we got aborted
X@@ -594,7 +650,7 @@
X /*
X * Someone wants to abort this transfer. Set the reason in the
X * request structure, call the server-side callback and mark the
X- * entry for releasing
X+ * entry for releasing
X */
X void
X storeAbort(StoreEntry * e)
X@@ -602,7 +658,7 @@
X MemObject *mem = e->mem_obj;
X assert(e->store_status == STORE_PENDING);
X assert(mem != NULL);
X- debug(20, 6) ("storeAbort: %s\n", storeKeyText(e->key));
X+ debug(20, 7) ("storeAbort: %s\n", storeKeyText(e->key));
X storeLockObject(e); /* lock while aborting */
X storeNegativeCache(e);
X storeReleaseRequest(e);
X@@ -656,17 +712,63 @@
X static time_t last_check = 0;
X int pages_needed;
X dlink_node *m;
X- dlink_node *head;
X dlink_node *prev = NULL;
X+ int locked = 0;
X+ #ifdef HPL_REPL
X+ heap_p heap = inmem_heap;
X+ _HEAPKEY age, min_age = 0;
X+ dlink_list locked_entries;
X+
X+ locked_entries.head = locked_entries.tail = NULL;
X+ #else /* HPL_REPL */
X+ dlink_node *head;
X+ #endif /* HPL_REPL */
X+
X if (squid_curtime == last_check)
X return;
X last_check = squid_curtime;
X pages_needed = (size / SM_PAGE_SIZE) + 1;
X+ debug(20, 3) ("storeGetMemSpace: inuse %d, need %d, have %d\n",
X+ memInUse(MEM_STMEM_BUF), pages_needed, store_pages_max);
X if (memInUse(MEM_STMEM_BUF) + pages_needed < store_pages_max)
X return;
X if (store_rebuilding)
X return;
X debug(20, 2) ("storeGetMemSpace: Starting, need %d pages\n", pages_needed);
X+ #ifdef HPL_REPL
X+ while (heap_nodes(heap) > 0) {
X+ age = heap_peepminkey(heap);
X+ e = heap_extractmin(heap);
X+ e->mem_obj->node = NULL; /* no longer in the heap */
X+ if (storeEntryLocked(e)) {
X+ locked++;
X+ debug(20, 5) ("storeGetMemSpace: locked key %s\n", storeKeyText(e->key));
X+ dlinkAdd(e, &e->lock_list, &locked_entries);
X+ continue;
X+ }
X+ released++;
X+ debug(20, 3) ("Released memory object with key %f size %d refs %d url %s\n",
X+ age, e->swap_file_sz, e->refcount, e->mem_obj->url);
X+ min_age = age;
X+ storePurgeMem(e);
X+ if (memInUse(MEM_STMEM_BUF) + pages_needed < store_pages_max)
X+ break;
X+ }
X+ /*
X+ * Increase the heap age factor.
X+ */
X+ if (min_age > 0)
X+ heap->age = min_age;
X+ /*
X+ * Reinsert all bumped locked entries back into heap...
X+ */
X+ for (m = locked_entries.tail; m; m = prev) {
X+ prev = m->prev;
X+ e = m->data;
X+ e->mem_obj->node = heap_insert(inmem_heap, e);
X+ }
X+
X+ #else /* HPL_REPL */
X head = inmem_list.head;
X for (m = inmem_list.tail; m; m = prev) {
X if (m == head)
X@@ -674,6 +776,7 @@
X prev = m->prev;
X e = m->data;
X if (storeEntryLocked(e)) {
X+ locked++;
X dlinkDelete(m, &inmem_list);
X dlinkAdd(e, m, &inmem_list);
X continue;
X@@ -683,16 +786,19 @@
X if (memInUse(MEM_STMEM_BUF) + pages_needed < store_pages_max)
X break;
X }
X- debug(20, 3) ("storeGetMemSpace stats:\n");
X- debug(20, 3) (" %6d HOT objects\n", hot_obj_count);
X- debug(20, 3) (" %6d were released\n", released);
X+ #endif /* HPL_REPL */
X+ debug(20, 3) ("storeGetMemSpace: released %d/%d locked %d\n",
X+ released, hot_obj_count, locked);
X+ debug(20, 4) ("storeGetMemSpace stats:\n");
X+ debug(20, 4) (" %6d HOT objects\n", hot_obj_count);
X+ debug(20, 4) (" %6d were released\n", released);
X }
X
X /* The maximum objects to scan for maintain storage space */
X #define MAINTAIN_MAX_SCAN 1024
X #define MAINTAIN_MAX_REMOVE 64
X
X-/*
X+/*
X * This routine is to be called by main loop in main.c.
X * It removes expired objects on only one bucket for each time called.
X * returns the number of objects removed
X@@ -712,19 +818,102 @@
X int max_remove;
X double f;
X static time_t last_warn_time = 0;
X+ #ifdef HPL_REPL
X+ heap_p heap = store_heap;
X+ _HEAPKEY age, min_age = 0;
X+ dlink_list locked_entries;
X+
X+ locked_entries.head = locked_entries.tail = NULL;
X+ #ifdef HPL_REPL_DEBUG
X+ if (!verify_heap_property(store_heap)) {
X+ debug(20, 1) ("Heap property violated!\n");
X+ }
X+ #endif /* HPL_REPL_DEBUG */
X+ #endif /* HPL_REPL */
X+
X /* We can't delete objects while rebuilding swap */
X if (store_rebuilding) {
X eventAdd("MaintainSwapSpace", storeMaintainSwapSpace, NULL, 1.0, 1);
X return;
X } else {
X- f = (double) (store_swap_size - store_swap_low) / (store_swap_high - store_swap_low);
X+ f = ((double) (store_swap_size - store_swap_low) /
X+ (store_swap_high - store_swap_low));
X f = f < 0.0 ? 0.0 : f > 1.0 ? 1.0 : f;
X max_scan = (int) (f * 400.0 + 100.0);
X- max_remove = (int) (f * 70.0 + 10.0);
X- eventAdd("MaintainSwapSpace", storeMaintainSwapSpace, NULL, 1.0 - f, 1);
X+ max_remove = (int) (f * 40.0 + 10.0);
X+ eventAdd("MaintainSwapSpace", storeMaintainSwapSpace, NULL, 10*(1.0 - f), 1);
X+ }
X+
X+ if (store_swap_size < store_swap_low) {
X+ /* Just return since we still have enougy memory */
X+ return;
X }
X- debug(20, 3) ("storeMaintainSwapSpace: f=%f, max_scan=%d, max_remove=%d\n",
X+
X+ debug(20, 2) ("storeMaintainSwapSpace: Starting, f=%f, max_scan=%d, max_remove=%d\n",
X f, max_scan, max_remove);
X+
X+#ifdef HPL_REPL
X+
X+ while (heap_nodes(heap) > 0) {
X+ age = heap_peepminkey(heap);
X+ e = heap_extractmin(heap);
X+ e->node = NULL; /* no longer in the heap */
X+ scanned++;
X+ if (storeEntryLocked(e)) {
X+ /*
X+ * Entry is in use ... put it in a linked list to ignore it.
X+ */
X+ if (!EBIT_TEST(e->flags, ENTRY_SPECIAL)) {
X+ /*
X+ * If this was a "SPECIAL" do not add it back into the heap.
X+ * It will always be "SPECIAL" and therefore never removed.
X+ */
X+ debug(20, 4) ("storeMaintainSwapSpace: locked url %s\n",
X+ (e->mem_obj && e->mem_obj->url) ? e->mem_obj->url : storeKeyText(e->key));
X+ dlinkAdd(e, &e->lock_list, &locked_entries);
X+ }
X+ locked++;
X+ continue;
X+ } else if (storeCheckExpired(e)) {
X+ /*
X+ * Note: This will not check the reference age ifdef HPL_REPL,
X+ * but it does some other useful checks...
X+ */
X+ expired++;
X+ debug(20, 3) ("Released store object age %f size %d refs %d key %s\n",
X+ age, e->swap_file_sz, e->refcount, storeKeyText(e->key));
X+ min_age = age;
X+ storeRelease(e);
X+ } else {
X+ /*
X+ * Did not expire the object so we need to add it back into the heap!
X+ */
X+ debug(20, 5) ("storeMaintainSwapSpace: non-expired %s\n", storeKeyText(e->key));
X+ dlinkAdd(e, &e->lock_list, &locked_entries);
X+ continue;
X+ }
X+ if ((store_swap_size < store_swap_low)
X+ || (expired >= max_remove)
X+ || (scanned >= max_scan))
X+ break;
X+ }
X+ /*
X+ * Bump the heap age factor.
X+ */
X+ if (min_age > 0)
X+ heap->age = min_age;
X+
X+ /*
X+ * Reinsert all bumped locked entries back into heap...
X+ */
X+ for (m = locked_entries.tail; m; m = prev) {
X+ prev = m->prev;
X+ e = m->data;
X+ e->node = heap_insert(store_heap, e);
X+ }
X+
X+#else /* HPL_REPL */
X+
X for (m = store_list.tail; m; m = prev) {
X prev = m->prev;
X e = m->data;
X@@ -751,11 +940,16 @@
X if (scanned >= max_scan)
X break;
X }
X- debug(20, 3) ("storeMaintainSwapSpace stats:\n");
X- debug(20, 3) (" %6d objects\n", memInUse(MEM_STOREENTRY));
X- debug(20, 3) (" %6d were scanned\n", scanned);
X- debug(20, 3) (" %6d were locked\n", locked);
X- debug(20, 3) (" %6d were expired\n", expired);
X+
X+#endif /* HPL_REPL */
X+
X+ debug(20, (expired?2:3)) ("storeMaintainSwapSpace: scanned %d/%d removed %d/%d locked %d f=%.03f\n",
X+ scanned, max_scan, expired, max_remove, locked, f);
X+ debug(20, 4) ("storeMaintainSwapSpace stats:\n");
X+ debug(20, 4) (" %6d objects\n", memInUse(MEM_STOREENTRY));
X+ debug(20, 4) (" %6d were scanned\n", scanned);
X+ debug(20, 4) (" %6d were locked\n", locked);
X+ debug(20, 4) (" %6d were expired\n", expired);
X if (store_swap_size < Config.Swap.maxSize)
X return;
X if (squid_curtime - last_warn_time < 10)
X@@ -771,12 +965,12 @@
X void
X storeRelease(StoreEntry * e)
X {
X- debug(20, 3) ("storeRelease: Releasing: '%s'\n", storeKeyText(e->key));
X+ debug(20, 4) ("storeRelease: Releasing: '%s'\n", storeKeyText(e->key));
X /* If, for any reason we can't discard this object because of an
X * outstanding request, mark it for pending release */
X if (storeEntryLocked(e)) {
X storeExpireNow(e);
X- debug(20, 3) ("storeRelease: Only setting RELEASE_REQUEST bit\n");
X+ debug(20, 4) ("storeRelease: Only setting RELEASE_REQUEST bit\n");
X storeReleaseRequest(e);
X return;
X }
X@@ -811,6 +1005,7 @@
X storeDirSwapLog(e, SWAP_LOG_DEL);
X }
X storeSetMemStatus(e, NOT_IN_MEMORY);
X+
X destroy_StoreEntry(e);
X }
X
X@@ -865,25 +1060,25 @@
X const HttpReply *reply;
X assert(e->mem_obj != NULL);
X reply = e->mem_obj->reply;
X- debug(20, 3) ("storeEntryValidLength: Checking '%s'\n", storeKeyText(e->key));
X- debug(20, 5) ("storeEntryValidLength: object_len = %d\n",
X+ debug(20, 4) ("storeEntryValidLength: Checking '%s'\n", storeKeyText(e->key));
X+ debug(20, 6) ("storeEntryValidLength: object_len = %d\n",
X objectLen(e));
X- debug(20, 5) ("storeEntryValidLength: hdr_sz = %d\n",
X+ debug(20, 6) ("storeEntryValidLength: hdr_sz = %d\n",
X reply->hdr_sz);
X- debug(20, 5) ("storeEntryValidLength: content_length = %d\n",
X+ debug(20, 6) ("storeEntryValidLength: content_length = %d\n",
X reply->content_length);
X if (reply->content_length < 0) {
X- debug(20, 5) ("storeEntryValidLength: Unspecified content length: %s\n",
X+ debug(20, 6) ("storeEntryValidLength: Unspecified content length: %s\n",
X storeKeyText(e->key));
X return 1;
X }
X if (reply->hdr_sz == 0) {
X- debug(20, 5) ("storeEntryValidLength: Zero header size: %s\n",
X+ debug(20, 6) ("storeEntryValidLength: Zero header size: %s\n",
X storeKeyText(e->key));
X return 1;
X }
X if (e->mem_obj->method == METHOD_HEAD) {
X- debug(20, 5) ("storeEntryValidLength: HEAD request: %s\n",
X+ debug(20, 6) ("storeEntryValidLength: HEAD request: %s\n",
X storeKeyText(e->key));
X return 1;
X }
X@@ -894,7 +1089,7 @@
X diff = reply->hdr_sz + reply->content_length - objectLen(e);
X if (diff == 0)
X return 1;
X- debug(20, 3) ("storeEntryValidLength: %d bytes too %s; '%s'\n",
X+ debug(20, 4) ("storeEntryValidLength: %d bytes too %s; '%s'\n",
X diff < 0 ? -diff : diff,
X diff < 0 ? "big" : "small",
X storeKeyText(e->key));
X@@ -924,6 +1119,70 @@
X debug(20, 1) ("Max Swap size: %d KB\n", Config.Swap.maxSize);
X }
X
X+#ifdef HPL_REPL
X+
X+/*
X+ * For a description of these cache replacement policies see --
X+ http://www.hpl.hp.com/personal/John_Dilley/caching/wcw.html
X+ */
X+
X+
X+/*
X+ * Key generation function to implement the LFU-DA policy (Least Frequently
X+ * Used with Dynamic Aging). Similar to classical LFU but with aging to
X+ * handle turnover of the popular document set. Maximizes byte hit rate by
X+ * keeping more currently popular objects in cache regardless of size.
X+ * Achieves lower hit rate than GDS because there are more large objects in
X+ * cache (so less room for smaller popular objects).
X+ *
X+ * This version implements a tie-breaker based upon recency (e->lastref):
X+ * for objects that have the same reference count the most recent object
X+ * wins (gets a higher key value).
X+ */
X+double
X+HeapKeyGen_StoreEntry_LFUDA(void * entry, double age)
X+{
X+ StoreEntry * e = entry;
X+ double tie = (e->lastref>1)?(1.0/e->lastref):1;
X+ return age + e->refcount - tie;
X+}
X+
X+
X+/*
X+ * Key generation function to implement the GDS-Frequency policy.
X+ * Similar to Greedy Dual-Size Hits policy, but adds aging of documents to
X+ * prevent pollution. Maximizes object hit rate by keeping more small,
X+ * popular objects in cache. Achieves lower byte hit rate than LFUDA
X+ * because there are fewer large objects in cache.
X+ *
X+ * This version implements a tie-breaker based upon recency (e->lastref):
X+ * for objects that have the same reference count the most recent object
X+ * wins (gets a higher key value).
X+ */
X+double
X+HeapKeyGen_StoreEntry_GDSF(void * entry, double age)
X+{
X+ StoreEntry * e = entry;
X+ double size = e->swap_file_sz ? e->swap_file_sz : 1.0;
X+ double tie = (e->lastref>1)?(1.0/e->lastref):1;
X+ return age + ((double)e->refcount / size) - tie;
X+}
X+
X+/*
X+ * Key generation function to implement the LRU policy. Normally one would
X+ * not do this with a heap -- use the linked list instead. For testing and
X+ * performance characterization it was useful. Don't use it unless you are
X+ * trying to compare performance among heap-based replacement policies...
X+ */
X+double
X+HeapKeyGen_StoreEntry_LRU(void * entry, double age)
X+{
X+ StoreEntry * e = entry;
X+ return e->lastref;
X+}
X+
X+#endif /* HPL_REPL */
X+
X void
X storeInit(void)
X {
X@@ -942,8 +1201,45 @@
X fatal(tmp_error_buf);
X }
X storeDirOpenSwapLogs();
X+
X+ #ifdef HPL_REPL
X+ /*
X+ * Create new heaps with cache replacement policies attached to them.
X+ * The cache replacement policy is specified as either GDSF or LFUDA in
X+ * the squid.conf configuration file. Note that the replacement policy
X+ * applies only to the disk replacement algorithm. Memory replacement
X+ * always uses GDSF since we want to maximize object hit rate.
X+ */
X+ inmem_heap = new_heap(1000, HeapKeyGen_StoreEntry_GDSF);
X+
X+ if (Config.replPolicy) {
X+ if (tolower(Config.replPolicy[0]) == 'g') {
X+ debug(20, 1) ("Using GDSF disk replacement policy\n");
X+ store_heap = new_heap(10000, HeapKeyGen_StoreEntry_GDSF);
X+ } else if (tolower(Config.replPolicy[0]) == 'l') {
X+ if (tolower(Config.replPolicy[1]) == 'f') {
X+ debug(20, 1) ("Using LFUDA disk replacement policy\n");
X+ store_heap = new_heap(10000, HeapKeyGen_StoreEntry_LFUDA);
X+ } else if (tolower(Config.replPolicy[1]) == 'r') {
X+ debug(20, 1) ("Using LRU heap disk replacement policy\n");
X+ store_heap = new_heap(10000, HeapKeyGen_StoreEntry_LRU);
X+ }
X+ } else {
X+ debug(20, 1) ("Unrecognized replacement_policy; using GDSF\n");
X+ store_heap = new_heap(10000, HeapKeyGen_StoreEntry_GDSF);
X+ }
X+ } else {
X+ debug(20, 1) ("Using default disk replacement policy (GDSF)\n");
X+ store_heap = new_heap(10000, HeapKeyGen_StoreEntry_GDSF);
X+ }
X+
X+ #else /* HPL_REPL */
X+
X store_list.head = store_list.tail = NULL;
X inmem_list.head = inmem_list.tail = NULL;
X+
X+ #endif /* HPL_REPL */
X+
X stackInit(&LateReleaseStack);
X eventAdd("storeLateRelease", storeLateRelease, NULL, 1.0, 1);
X storeRebuildStart();
X@@ -986,12 +1282,25 @@
X return 1;
X if (EBIT_TEST(e->flags, ENTRY_NEGCACHED) && squid_curtime >= e->expires)
X return 1;
X+#ifdef HPL_REPL
X+ /*
X+ * With HPL_REPL we are not using the LRU reference age, the heap
X+ * controls the replacement of objects.
X+ */
X+ return 1;
X+#else /* HPL_REPL */
X if (squid_curtime - e->lastref > storeExpiredReferenceAge())
X return 1;
X return 0;
X+#endif /* HPL_REPL */
X }
X
X-/*
X+#ifdef HPL_REPL
X+/*
X+ * The non-LRU cache replacement policies do not use LRU referenceAge
X+ */
X+#else /* HPL_REPL */
X+/*
X * storeExpiredReferenceAge
X *
X * The LRU age is scaled exponentially between 1 minute and
X@@ -1018,6 +1327,7 @@
X age = 31536000;
X return age;
X }
X+#endif /* HPL_REPL */
X
X void
X storeNegativeCache(StoreEntry * e)
X@@ -1153,10 +1463,33 @@
X assert(mem != NULL);
X if (new_status == IN_MEMORY) {
X assert(mem->inmem_lo == 0);
X+ #ifdef HPL_REPL
X+ if (mem->node == NULL) {
X+ if (EBIT_TEST(e->flags, ENTRY_SPECIAL)) {
X+ debug(20, 4) ("storeSetMemStatus: not inserting special %s\n", mem->url);
X+ } else {
X+ mem->node = heap_insert(inmem_heap, e);
X+ debug(20, 4) ("storeSetMemStatus: inserted mem node 0x%x\n", mem->node);
X+ }
X+ }
X+ #else /* HPL_REPL */
X dlinkAdd(e, &mem->lru, &inmem_list);
X+ #endif /* HPL_REPL */
X hot_obj_count++;
X } else {
X+ #ifdef HPL_REPL
X+ /*
X+ * It's being removed from the memory heap; is it already gone?
X+ */
X+ if (mem->node) {
X+ heap_delete(inmem_heap, mem->node);
X+ debug(20, 4) ("storeSetMemStatus: deleted mem node 0x%x\n",
X+ mem->node);
X+ mem->node = 0;
X+ }
X+ #else /* HPL_REPL */
X dlinkDelete(&mem->lru, &inmem_list);
X+ #endif /* HPL_REPL */
X hot_obj_count--;
X }
X e->mem_status = new_status;
X@@ -1200,7 +1533,7 @@
X void
X storeUnlinkFileno(int fileno)
X {
X- debug(20, 5) ("storeUnlinkFileno: %08X\n", fileno);
X+ debug(20, 6) ("storeUnlinkFileno: %08X\n", fileno);
X #if USE_ASYNC_IO
X safeunlink(storeSwapFullPath(fileno, NULL), 1);
X #else
X@@ -1237,7 +1570,7 @@
X storeEntryReset(StoreEntry * e)
X {
X MemObject *mem = e->mem_obj;
X- debug(20, 3) ("storeEntryReset: %s\n", storeUrl(e));
X+ debug(20, 4) ("storeEntryReset: %s\n", storeUrl(e));
X assert(mem->swapout.fd == -1);
X stmemFree(&mem->data_hdr);
X mem->inmem_hi = mem->inmem_lo = 0;
Xdiff -r -u squid-2.2.STABLE3/src/store_client.c squid-2.2.STABLE3-jad/src/store_client.c
X--- squid-2.2.STABLE3/src/store_client.c Wed May 12 11:49:21 1999
X+++ squid-2.2.STABLE3-jad/src/store_client.c Fri Jun 4 14:49:23 1999
X@@ -141,7 +141,7 @@
X storeClientCopyEvent(void *data)
X {
X store_client *sc = data;
X- debug(20, 3) ("storeClientCopyEvent: Running\n");
X+ debug(20, 4) ("storeClientCopyEvent: Running\n");
X sc->flags.copy_event_pending = 0;
X if (!sc->callback)
X return;
X@@ -160,7 +160,7 @@
X {
X store_client *sc;
X assert(!EBIT_TEST(e->flags, ENTRY_ABORTED));
X- debug(20, 3) ("storeClientCopy: %s, seen %d, want %d, size %d, cb %p, cbdata %p\n",
X+ debug(20, 4) ("storeClientCopy: %s, seen %d, want %d, size %d, cb %p, cbdata %p\n",
X storeKeyText(e->key),
X (int) seen_offset,
X (int) copy_offset,
X@@ -215,13 +215,13 @@
X }
X if (sc->flags.store_copying) {
X sc->flags.copy_event_pending = 1;
X- debug(20, 3) ("storeClientCopy2: Queueing storeClientCopyEvent()\n");
X+ debug(20, 4) ("storeClientCopy2: Queueing storeClientCopyEvent()\n");
X eventAdd("storeClientCopyEvent", storeClientCopyEvent, sc, 0.0, 0);
X return;
X }
X cbdataLock(sc); /* ick, prevent sc from getting freed */
X sc->flags.store_copying = 1;
X- debug(20, 3) ("storeClientCopy2: %s\n", storeKeyText(e->key));
X+ debug(20, 4) ("storeClientCopy2: %s\n", storeKeyText(e->key));
X assert(callback != NULL);
X /*
X * We used to check for ENTRY_ABORTED here. But there were some
X@@ -245,10 +245,10 @@
X callback(sc->callback_data, sc->copy_buf, 0);
X } else if (e->store_status == STORE_PENDING && sc->seen_offset >= mem->inmem_hi) {
X /* client has already seen this, wait for more */
X- debug(20, 3) ("storeClientCopy2: Waiting for more\n");
X+ debug(20, 4) ("storeClientCopy2: Waiting for more\n");
X } else if (sc->copy_offset >= mem->inmem_lo && sc->copy_offset < mem->inmem_hi) {
X /* What the client wants is in memory */
X- debug(20, 3) ("storeClientCopy2: Copying from memory\n");
X+ debug(20, 4) ("storeClientCopy2: Copying from memory\n");
X sz = stmemCopy(&mem->data_hdr, sc->copy_offset, sc->copy_buf, sc->copy_size);
X #if USE_ASYNC_IO
X if (sc->flags.disk_io_pending) {
X@@ -262,7 +262,7 @@
X sc->callback = NULL;
X callback(sc->callback_data, sc->copy_buf, sz);
X } else if (sc->swapin_fd < 0) {
X- debug(20, 3) ("storeClientCopy2: Need to open swap in file\n");
X+ debug(20, 4) ("storeClientCopy2: Need to open swap in file\n");
X assert(sc->type == STORE_DISK_CLIENT);
X /* gotta open the swapin file */
X if (storeTooManyDiskFilesOpen()) {
X@@ -276,7 +276,7 @@
X debug(20, 2) ("storeClientCopy2: Averted multiple fd operation\n");
X }
X } else {
X- debug(20, 3) ("storeClientCopy: reading from disk FD %d\n",
X+ debug(20, 4) ("storeClientCopy: reading from disk FD %d\n",
X sc->swapin_fd);
X assert(sc->type == STORE_DISK_CLIENT);
X if (!sc->flags.disk_io_pending) {
X@@ -295,7 +295,7 @@
X store_client *sc = data;
X STCB *callback = sc->callback;
X if (fd < 0) {
X- debug(20, 3) ("storeClientFileOpened: failed\n");
X+ debug(20, 4) ("storeClientFileOpened: failed\n");
X sc->flags.disk_io_pending = 0;
X sc->callback = NULL;
X callback(sc->callback_data, sc->copy_buf, -1);
X@@ -344,7 +344,7 @@
X assert(sc->flags.disk_io_pending);
X sc->flags.disk_io_pending = 0;
X assert(sc->callback != NULL);
X- debug(20, 3) ("storeClientReadBody: FD %d, len %d\n", fd, len);
X+ debug(20, 4) ("storeClientReadBody: FD %d, len %d\n", fd, len);
X if (sc->copy_offset == 0 && len > 0 && mem->reply->sline.status == 0)
X httpReplyParse(mem->reply, sc->copy_buf);
X sc->callback = NULL;
X@@ -365,9 +365,9 @@
X assert(sc->flags.disk_io_pending);
X sc->flags.disk_io_pending = 0;
X assert(sc->callback != NULL);
X- debug(20, 3) ("storeClientReadHeader: FD %d, len %d\n", fd, len);
X+ debug(20, 4) ("storeClientReadHeader: FD %d, len %d\n", fd, len);
X if (len < 0) {
X- debug(20, 3) ("storeClientReadHeader: FD %d: %s\n", fd, xstrerror());
X+ debug(20, 4) ("storeClientReadHeader: FD %d: %s\n", fd, xstrerror());
X sc->callback = NULL;
X callback(sc->callback_data, sc->copy_buf, len);
X return;
X@@ -396,7 +396,7 @@
X * we have (part of) what they want
X */
X copy_sz = XMIN(sc->copy_size, body_sz);
X- debug(20, 3) ("storeClientReadHeader: copying %d bytes of body\n",
X+ debug(20, 4) ("storeClientReadHeader: copying %d bytes of body\n",
X copy_sz);
X xmemmove(sc->copy_buf, sc->copy_buf + swap_hdr_sz, copy_sz);
X if (sc->copy_offset == 0 && len > 0 && mem->reply->sline.status == 0)
X@@ -433,7 +433,7 @@
X STCB *callback;
X if (mem == NULL)
X return 0;
X- debug(20, 3) ("storeUnregister: called for '%s'\n", storeKeyText(e->key));
X+ debug(20, 4) ("storeUnregister: called for '%s'\n", storeKeyText(e->key));
X for (S = &mem->clients; (sc = *S) != NULL; S = &(*S)->next) {
X if (sc->callback_data == data)
X break;
X@@ -464,7 +464,7 @@
X #endif
X if ((callback = sc->callback) != NULL) {
X /* callback with ssize = -1 to indicate unexpected termination */
X- debug(20, 3) ("storeUnregister: store_client for %s has a callback\n",
X+ debug(20, 4) ("storeUnregister: store_client for %s has a callback\n",
X mem->url);
X sc->callback = NULL;
X callback(sc->callback_data, sc->copy_buf, -1);
X@@ -507,11 +507,11 @@
X store_client *sc;
X store_client *nx = NULL;
X assert(mem->clients != NULL || mem->nclients == 0);
X- debug(20, 3) ("InvokeHandlers: %s\n", storeKeyText(e->key));
X+ debug(20, 4) ("InvokeHandlers: %s\n", storeKeyText(e->key));
X /* walk the entire list looking for valid callbacks */
X for (sc = mem->clients; sc; sc = nx) {
X nx = sc->next;
X- debug(20, 3) ("InvokeHandlers: checking client #%d\n", i++);
X+ debug(20, 4) ("InvokeHandlers: checking client #%d\n", i++);
X if (sc->callback_data == NULL)
X continue;
X if (sc->callback == NULL)
X@@ -525,7 +525,7 @@
X {
X MemObject *mem = e->mem_obj;
X int npend = NULL == mem ? 0 : mem->nclients;
X- debug(20, 3) ("storePendingNClients: returning %d\n", npend);
X+ debug(20, 4) ("storePendingNClients: returning %d\n", npend);
X return npend;
X }
X
X@@ -538,43 +538,43 @@
X int expectlen;
X MemObject *mem = entry->mem_obj;
X assert(mem);
X- debug(20, 3) ("CheckQuickAbort2: entry=%p, mem=%p\n", entry, mem);
X+ debug(20, 4) ("CheckQuickAbort2: entry=%p, mem=%p\n", entry, mem);
X if (mem->request && !mem->request->flags.cachable) {
X- debug(20, 3) ("CheckQuickAbort2: YES !mem->request->flags.cachable\n");
X+ debug(20, 4) ("CheckQuickAbort2: YES !mem->request->flags.cachable\n");
X return 1;
X }
X if (EBIT_TEST(entry->flags, KEY_PRIVATE)) {
X- debug(20, 3) ("CheckQuickAbort2: YES KEY_PRIVATE\n");
X+ debug(20, 4) ("CheckQuickAbort2: YES KEY_PRIVATE\n");
X return 1;
X }
X expectlen = mem->reply->content_length + mem->reply->hdr_sz;
X curlen = (int) mem->inmem_hi;
X minlen = (int) Config.quickAbort.min << 10;
X if (minlen < 0) {
X- debug(20, 3) ("CheckQuickAbort2: NO disabled\n");
X+ debug(20, 4) ("CheckQuickAbort2: NO disabled\n");
X return 0;
X }
X if (curlen > expectlen) {
X- debug(20, 3) ("CheckQuickAbort2: YES bad content length\n");
X+ debug(20, 4) ("CheckQuickAbort2: YES bad content length\n");
X return 1;
X }
X if ((expectlen - curlen) < minlen) {
X- debug(20, 3) ("CheckQuickAbort2: NO only little more left\n");
X+ debug(20, 4) ("CheckQuickAbort2: NO only little more left\n");
X return 0;
X }
X if ((expectlen - curlen) > (Config.quickAbort.max << 10)) {
X- debug(20, 3) ("CheckQuickAbort2: YES too much left to go\n");
X+ debug(20, 4) ("CheckQuickAbort2: YES too much left to go\n");
X return 1;
X }
X if (expectlen < 100) {
X- debug(20, 3) ("CheckQuickAbort2: NO avoid FPE\n");
X+ debug(20, 4) ("CheckQuickAbort2: NO avoid FPE\n");
X return 0;
X }
X if ((curlen / (expectlen / 100)) > Config.quickAbort.pct) {
X- debug(20, 3) ("CheckQuickAbort2: NO past point of no return\n");
X+ debug(20, 4) ("CheckQuickAbort2: NO past point of no return\n");
X return 0;
X }
X- debug(20, 3) ("CheckQuickAbort2: YES default, returning 1\n");
X+ debug(20, 4) ("CheckQuickAbort2: YES default, returning 1\n");
X return 1;
X }
X
Xdiff -r -u squid-2.2.STABLE3/src/store_dir.c squid-2.2.STABLE3-jad/src/store_dir.c
X--- squid-2.2.STABLE3/src/store_dir.c Sat Feb 13 16:23:11 1999
X+++ squid-2.2.STABLE3-jad/src/store_dir.c Fri Jun 4 10:37:50 1999
X@@ -662,11 +662,16 @@
X char **cln;
X int dirn;
X int N = Config.cacheSwap.n_configured;
X- dlink_node *m;
X char **outbuf;
X off_t *outbufoffset;
X storeSwapLogData s;
X size_t ss = sizeof(storeSwapLogData);
X+ #ifdef HPL_REPL
X+ int node;
X+ #else /* HPL_REPL */
X+ dlink_node *m;
X+ #endif /* HPL_REPL */
X+
X if (store_rebuilding) {
X debug(20, 1) ("Not currently OK to rewrite swap log.\n");
X debug(20, 1) ("storeDirWriteCleanLogs: Operation aborted.\n");
X@@ -707,8 +712,17 @@
X outbuf[dirn] = xcalloc(CLEAN_BUF_SZ, 1);
X outbufoffset[dirn] = 0;
X }
X- for (m = store_list.tail; m; m = m->prev) {
X+ #ifdef HPL_REPL
X+ for (node=0; node < heap_nodes(store_heap); node++)
X+ #else /* HPL_REPL */
X+ for (m = store_list.tail; m; m = m->prev)
X+ #endif /* HPL_REPL */
X+ {
X+ #ifdef HPL_REPL
X+ e = (StoreEntry*)heap_peep(store_heap, node);
X+ #else /* HPL_REPL */
X e = m->data;
X+ #endif /* HPL_REPL */
X if (e->swap_file_number < 0)
X continue;
X if (e->swap_status != SWAPOUT_DONE)
Xdiff -r -u squid-2.2.STABLE3/src/store_rebuild.c squid-2.2.STABLE3-jad/src/store_rebuild.c
X--- squid-2.2.STABLE3/src/store_rebuild.c Tue Apr 27 14:54:24 1999
X+++ squid-2.2.STABLE3-jad/src/store_rebuild.c Fri Jun 4 14:44:01 1999
X@@ -119,7 +119,7 @@
X tlv *tlv_list;
X tlv *t;
X assert(d != NULL);
X- debug(20, 3) ("storeRebuildFromDirectory: DIR #%d\n", d->dirn);
X+ debug(20, 2) ("storeRebuildFromDirectory: DIR #%d\n", d->dirn);
X for (count = 0; count < d->speed; count++) {
X assert(fd == -1);
X fd = storeGetNextFile(d, &sfileno, &size);
X@@ -327,6 +327,14 @@
X e->lastmod = s.lastmod;
X e->flags = s.flags;
X e->refcount += s.refcount;
X+#ifdef HPL_REPL
X+ /* Update the position of this object in the store and memory heaps. */
X+ if (e->node)
X+ heap_update(store_heap, e->node, e);
X+ if (e->mem_obj->node)
X+ heap_update(inmem_heap, e->mem_obj->node, e);
X+#endif /* HPL_REPL */
X+
X } else {
X debug_trap("storeRebuildFromSwapLog: bad condition");
X debug(20, 1) ("\tSee %s:%d\n", __FILE__, __LINE__);
X@@ -565,7 +573,6 @@
X e->swap_file_number = file_number;
X e->swap_file_sz = swap_file_sz;
X e->lock_count = 0;
X- e->refcount = 0;
X e->lastref = lastref;
X e->timestamp = timestamp;
X e->expires = expires;
Xdiff -r -u squid-2.2.STABLE3/src/store_swapout.c squid-2.2.STABLE3-jad/src/store_swapout.c
X--- squid-2.2.STABLE3/src/store_swapout.c Fri Jan 29 09:36:37 1999
X+++ squid-2.2.STABLE3-jad/src/store_swapout.c Tue Jun 1 09:47:56 1999
X@@ -114,6 +114,13 @@
X debug(20, 5) ("storeSwapOutHandle: SwapOut complete: '%s' to %s.\n",
X storeUrl(e), storeSwapFullPath(e->swap_file_number, NULL));
X e->swap_file_sz = objectLen(e) + mem->swap_hdr_sz;
X+#ifdef HPL_REPL
X+ /* Update the position of this object in the store and memory heaps. */
X+ if (e->node)
X+ heap_update(store_heap, e->node, e);
X+ if (e->mem_obj->node)
X+ heap_update(inmem_heap, e->mem_obj->node, e);
X+#endif /* HPL_REPL */
X e->swap_status = SWAPOUT_DONE;
X storeDirUpdateSwapSize(e->swap_file_number, e->swap_file_sz, 1);
X if (storeCheckCachable(e)) {
Xdiff -r -u squid-2.2.STABLE3/src/structs.h squid-2.2.STABLE3-jad/src/structs.h
X--- squid-2.2.STABLE3/src/structs.h Fri Feb 19 14:35:36 1999
X+++ squid-2.2.STABLE3-jad/src/structs.h Fri Jun 4 10:35:15 1999
X@@ -231,6 +231,13 @@
X int pct;
X size_t max;
X } quickAbort;
X+#ifdef HPL_REPL
X+ char * replPolicy;
X+#endif /* HPL_REPL */
X+ /*
X+ * Note: the non-LRU policies do not use referenceAge, but we cannot
X+ * remove it until we find out how to implement #else for cf_parser.c
X+ */
X time_t referenceAge;
X time_t negativeTtl;
X time_t negativeDnsTtl;
X@@ -1195,6 +1202,9 @@
X #endif
X };
X
X+#ifdef HPL_REPL
X+#include "heap.h"
X+#endif /* HPL_REPL */
X
X /* This structure can be freed while object is purged out from memory */
X struct _MemObject {
X@@ -1222,7 +1232,14 @@
X void *data;
X } abort;
X char *log_url;
X+ #ifdef HPL_REPL
X+ /*
X+ * A MemObject knows where it is in the in-memory heap.
X+ */
X+ heap_node_p node;
X+ #else /* HPL_REPL */
X dlink_node lru;
X+ #endif /* HPL_REPL */
X int id;
X ssize_t object_sz;
X size_t swap_hdr_sz;
X@@ -1241,7 +1258,12 @@
X u_short refcount;
X u_short flags;
X int swap_file_number;
X+ #ifdef HPL_REPL
X+ heap_node_p node;
X+ dlink_node lock_list;
X+ #else /* HPL_REPL */
X dlink_node lru;
X+ #endif /* HPL_REPL */
X u_short lock_count; /* Assume < 65536! */
X mem_status_t mem_status:3;
X ping_status_t ping_status:3;
Xdiff -r -u squid-2.2.STABLE3/src/tools.c squid-2.2.STABLE3-jad/src/tools.c
X--- squid-2.2.STABLE3/src/tools.c Tue May 11 13:37:20 1999
X+++ squid-2.2.STABLE3-jad/src/tools.c Tue Jun 1 09:47:56 1999
X@@ -211,12 +211,17 @@
X }
X
X
X+
X+
X void
X PrintRusage(void)
X {
X struct rusage rusage;
X squid_getrusage(&rusage);
X- fprintf(debug_log, "CPU Usage: %.3f seconds\n", rusage_cputime(&rusage));
X+ fprintf(debug_log, "CPU Usage: %.3f seconds = %.3f user + %.3f sys\n",
X+ rusage_cputime(&rusage),
X+ rusage.ru_utime.tv_sec + ((double) rusage.ru_utime.tv_usec / 1000000.0),
X+ rusage.ru_stime.tv_sec + ((double) rusage.ru_stime.tv_usec / 1000000.0));
X fprintf(debug_log, "Maximum Resident Size: %d KB\n",
X rusage_maxrss(&rusage));
X fprintf(debug_log, "Page faults with physical i/o: %d\n",
SHAR_EOF
  : || $echo 'restore of' 'jad.diff' 'failed'
fi
# ============= include/heap.h ==============
if test ! -d 'include'; then
  $echo 'x -' 'creating directory' 'include'
  mkdir 'include'
fi
if test -f 'include/heap.h' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'include/heap.h' '(file already exists)'
else
  $echo 'x -' extracting 'include/heap.h' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'include/heap.h' &&
X/****************************************************************************
X * Heap data structure. Used to store objects for cache replacement. The
X * heap is implemented as a contiguous array in memory. Heap sort and heap
X * update are done in-place. The heap is ordered with the smallest value at
X * the top of the heap (as in the smallest object key value). Child nodes
X * are larger than their parent.
X ****************************************************************************/
X
X#ifndef _heap_h_INCLUDED
X#define _heap_h_INCLUDED
X
X/*
X * Typdefs for non-synchronized heap implementation.
X */
Xtypedef unsigned long mutex_t;
X# define mutex_lock(m) (void)0
X# define mutex_unlock(m) (void)0
X# define mutex_trylock(m) (void)0
X# define mutex_init(m) ((m)=123456)
X
X/*
X * Function for generating heap keys. The first argument will typically be
X * a dws_md_p passed in as a void *. Should find a way to get type safety
X * without having heap know all about metadata objects... The second arg is
X * the current aging factor for the heap.
X */
X# define _HEAPTYPE void *
X# define _HEAPKEY double
X
Xtypedef _HEAPKEY (*key_func) (_HEAPTYPE, _HEAPKEY);
X
X
X/*
X * Heap node. Has a key value generated by a key_func, id (array index) so
X * it can be quickly found in its heap, and a pointer to a data object that
X * key_func can generate a key from.
X */
Xtypedef struct _heap_node {
X _HEAPKEY key;
X unsigned long id;
X _HEAPTYPE data;
X} heap_node, *heap_node_p;
X
X
X/*
X * Heap object. Holds an array of heap_node objects along with a heap size
X * (array length), the index of the last heap element, and a key generation
X * function. Also stores aging factor for this heap.
X */
Xtypedef struct _heap {
X mutex_t lock;
X unsigned long size;
X unsigned long last;
X key_func gen_key; /* key generator for heap */
X _HEAPKEY age; /* aging factor for heap */
X heap_node ** nodes;
X} heap, *heap_p;
X
X/****************************************************************************
X * Public functions
X ****************************************************************************/
X
X/*
X * Create and initialize a new heap.
X */
Xextern heap_p new_heap(int init_size, key_func gen_key);
X
X/*
X * Delete a heap and clean up its memory. Does not delete what the heap
X * nodes are pointing to!
X */
Xextern void delete_heap(heap_p);
X
X/*
X * Insert a new node into a heap, returning a pointer to it. The heap_node
X * object returned is used to update or delete a heap object. Nothing else
X * should be done with this data structure (especially modifying it!) The
X * heap does not assume ownership of the data passed to it.
X */
Xextern heap_node_p heap_insert(heap_p, _HEAPTYPE dat);
X
X/*
X * Delete a node out of a heap. Returns the heap data from the deleted
X * node. The caller is responsible for freeing this data.
X */
Xextern _HEAPTYPE heap_delete(heap_p, heap_node_p elm);
X
X/*
X * The semantics of this routine is the same as the followings:
X * heap_delete(hp, elm);
X * heap_insert(hp, dat);
X * Returns the old data object from elm (the one being replaced). The
X * caller must free this as necessary.
X */
Xextern _HEAPTYPE heap_update(heap_p, heap_node* elm, _HEAPTYPE dat);
X
X/*
X * Generate a heap key for a given data object. Alternative macro form:
X */
X#ifdef MACRO_DEBUG
Xextern _HEAPKEY heap_gen_key(heap_p hp, _HEAPTYPE dat);
X#else
X# define heap_gen_key(hp,md) ((hp)->gen_key((md),(hp)->age))
X#endif /* MACRO_DEBUG */
X
X
X/*
X * Extract the minimum (root) element and maintain the heap property.
X * Returns the data pointed to by the root node, which the caller must
X * free as necessary.
X */
Xextern _HEAPTYPE heap_extractmin(heap_p);
X
X/*
X * Extract the last leaf node (does not change the heap property).
X * Returns the data that had been in the heap which the caller must free if
X * necessary. Note that the last node is guaranteed to be less than its
X * parent, but may not be less than any of the other (leaf or parent) notes
X * in the tree. This operation is fast but imprecise.
X */
Xextern _HEAPTYPE heap_extractlast(heap_p hp);
X
X/*
X * Get the root key, the nth key, the root (smallest) element, or the nth
X * element. None of these operations modify the heap.
X */
Xextern _HEAPKEY heap_peepminkey(heap_p);
Xextern _HEAPKEY heap_peepkey(heap_p, int n);
X
Xextern _HEAPTYPE heap_peepmin(heap_p);
Xextern _HEAPTYPE heap_peep(heap_p, int n);
X
X/*
X * Is the heap empty? How many nodes (data objects) are in it?
X */
X#ifdef MACRO_DEBUG
Xextern int heap_empty(heap_p);
Xextern int heap_nodes(heap_p);
X#else /* MACRO_DEBUG */
X# define heap_nodes(heap) ((heap)->last)
X# define heap_empty(heap) (((heap)->last <= 0) ? 1 : 0)
X#endif /* MACRO_DEBUG */
X
X/*
X * Print the heap or a node in the heap.
X */
Xextern void heap_print(heap_p);
Xextern void heap_printnode(char *msg, heap_node_p elm);
X
Xextern int verify_heap_property(heap_p);
X
X#endif /* _heap_h_INCLUDED */
SHAR_EOF
  : || $echo 'restore of' 'include/heap.h' 'failed'
fi
# ============= lib/heap.c ==============
if test ! -d 'lib'; then
  $echo 'x -' 'creating directory' 'lib'
  mkdir 'lib'
fi
if test -f 'lib/heap.c' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'lib/heap.c' '(file already exists)'
else
  $echo 'x -' extracting 'lib/heap.c' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'lib/heap.c' &&
X/****************************************************************************
X * Heap implementation
X ****************************************************************************/
X
X#include <stdlib.h>
X#include "malloc.h"
X#include <assert.h>
X#include <string.h>
X#include <stdio.h>
X
X#include "heap.h"
X
X/*
X * Private function prototypes.
X */
Xstatic void _heap_ify_up(heap_p hp, heap_node_p elm);
Xstatic void _heap_ify_down(heap_p hp, heap_node_p elm);
Xstatic int _heap_should_grow(heap_p hp);
Xstatic void _heap_grow(heap_p hp);
Xstatic void _heap_swap_element(heap_p hp, heap_node_p elm1, heap_node_p elm2);
Xstatic int _heap_node_exist(heap_p hp, int id);
X
X#ifdef HEAP_DEBUG
Xvoid _heap_print_tree(heap_p hp, heap_node_p node);
X#endif /* HEAP_DEBUG */
X
X#define Left(x) (2 * (x) + 1)
X#define Right(x) (2 * (x) + 2)
X#define Parent(x) ((int)((x)-1)/2)
X
X#define Threshold 10000
X#define NormalRate 2
X#define SlowRate 1.5
X#define MinSize 32
X
X/****************************************************************************
X * Public functions
X ****************************************************************************/
X
X/*
X * Return a newly created heap. INITSIZE is the initial size of the heap.
X */
Xheap_p
Xnew_heap(int initSize, key_func gen_key)
X{
X heap_p hp = (heap_p) malloc(sizeof(heap));
X assert(hp != NULL);
X
X hp->nodes = (heap_node_p *)calloc(initSize, sizeof(heap_node_p));
X assert(hp->nodes != NULL);
X
X if (initSize <= 0)
X initSize = MinSize;
X hp->size = initSize;
X hp->last = 0;
X hp->gen_key = gen_key;
X hp->age = 0;
X
X return hp;
X}
X
X
X/*
X * Free memory used by a heap. Does not free the metadata pointed to by the
X * heap nodes, only the heap's internal memory.
X */
Xvoid
Xdelete_heap(heap_p hp)
X{
X int i;
X assert(hp);
X for (i = 0; i < hp->last; i++) {
X free(hp->nodes[i]);
X }
X free(hp->nodes);
X free(hp);
X}
X
X/*
X * Insert DAT based on KY into HP maintaining the heap property. Return the
X * newly inserted heap node. The fields of ELM other than ID are never
X * changed until ELM is deleted from HP, i.e. caller can assume that the
X * heap node always exist at the same place in memory unless heap_delete or
X * heap_extractmin is called on that node. This function exposes the heap's
X * internal data structure to the caller. This is required in order to do
X * O(lgN) deletion.
X */
Xheap_node_p
Xheap_insert(heap_p hp, void * dat)
X{
X heap_node* elm = (heap_node*)malloc(sizeof(heap_node));
X
X elm->key = heap_gen_key(hp, dat);
X elm->data = dat;
X
X if (_heap_should_grow(hp))
X _heap_grow(hp);
X
X hp->nodes[hp->last] = elm;
X elm->id = hp->last;
X hp->last += 1;
X
X _heap_ify_up(hp, elm);
X
X /*
X * Set the pointer in the metadata to point to this heap node.
X */
X #ifdef HPL_REPL
X /* The following must be done immediately upon return! */
X #else /* HPL_REPL */
X md_set_node(dat, elm);
X #endif /* HPL_REPL */
X
X return elm;
X}
X
X
X/*
X * Delete ELM while maintaining the heap property. ELM may be modified.
X * Assumes that ELM is not NULL and frees it. Returns the data pointed to
X * in, which the caller must free if necessary.
X */
X_HEAPTYPE
Xheap_delete(heap_p hp, heap_node_p elm)
X{
X heap_node_p lastNode;
X _HEAPTYPE data = elm->data;
X
X assert(_heap_node_exist(hp, hp->last - 1));
X
X lastNode = hp->nodes[hp->last - 1];
X _heap_swap_element(hp, lastNode, elm);
X heap_extractlast(hp);
X
X if (hp->last > 0) {
X if (lastNode->key < hp->nodes[Parent(lastNode->id)]->key)
X _heap_ify_up(hp, lastNode); /* COOL! */
X _heap_ify_down(hp, lastNode);
X }
X
X /*
X * Remove the pointer back to the heap from the metadata.
X * Then free the element that was just deleted.
X */
X #ifdef HPL_REPL
X /* The following must be done immediately upon return! */
X #else /* HPL_REPL */
X md_set_node(data, NULL);
X #endif /* HPL_REPL */
X
X return data;
X}
X
X/*
X * Delete the last element (leaf) out of the heap. Does not require a
X * heapify operation.
X */
X
X#ifndef heap_gen_key
X/*
X * Function to generate keys. See macro definition in heap.h.
X */
X_HEAPKEY
Xheap_gen_key(heap_p hp, _HEAPTYPE dat)
X{
X return hp->gen_key(dat, hp->age);
X}
X#endif /* heap_gen_key */
X
X
X/*
X * Returns the data of the node with the largest KEY value and removes that
X * node from the heap. Returns NULL if the heap was empty.
X */
X_HEAPTYPE
Xheap_extractmin(heap_p hp)
X{
X _HEAPTYPE data;
X
X if (hp->last <= 0)
X return NULL;
X
X mutex_lock(hp->lock);
X
X data = hp->nodes[0]->data;
X heap_delete(hp, hp->nodes[0]); /* Delete the root */
X
X mutex_unlock(hp->lock);
X
X return data;
X}
X
X
X/*
X * Remove the last node in HP. Frees the heap internal structure and
X * returns the data pointes to by the last node.
X */
X_HEAPTYPE
Xheap_extractlast(heap_p hp)
X{
X _HEAPTYPE data;
X assert (_heap_node_exist(hp, hp->last -1));
X hp->last -= 1;
X data = hp->nodes[hp->last]->data;
X free(hp->nodes[hp->last]);
X return data;
X}
X
X
X/*
X * The semantics of this routine is the same as the followings:
X * heap_delete(hp, elm);
X * heap_insert(hp, dat);
X * Returns the old data object from elm (the one being replaced). The
X * caller must free this as necessary.
X */
X_HEAPTYPE
Xheap_update(heap_p hp, heap_node* elm, void* dat)
X{
X _HEAPTYPE old = elm->data;
X _HEAPKEY ky = heap_gen_key(hp, dat);
X
X elm->key = ky;
X elm->data = dat;
X
X if (elm->key < hp->nodes[Parent(elm->id)]->key)
X _heap_ify_up(hp, elm);
X _heap_ify_down(hp, elm);
X
X return old;
X}
X
X
X/*
X * A pointer to the root node's DATA.
X */
Xvoid*
Xheap_peepmin(heap_p hp)
X{
X assert(_heap_node_exist(hp, 0));
X return hp->nodes[0]->data;
X}
X
X
X/*
X * The KEY of the root node.
X */
X_HEAPKEY
Xheap_peepminkey(heap_p hp)
X{
X assert(_heap_node_exist(hp, 0));
X return hp->nodes[0]->key;
X}
X
X
X/*
X * Same as heap_peep except that this return the KEY of the node.
X * Only meant for iteration.
X */
X_HEAPKEY
Xheap_peepkey(heap_p hp, int n)
X{
X assert(_heap_node_exist(hp, n));
X return hp->nodes[n]->key;
X}
X
X
X/*
X * A pointer to Nth node's DATA. The caller can iterate through HP by
X * calling this routine. eg. Caller can execute the following code:
X * for(i = 0; i < heap_nodes(hp); i++)
X * data = heap_peep(hp, i);
X */
Xvoid*
Xheap_peep(heap_p hp, int n)
X{
X void* data;
X assert(_heap_node_exist(hp, n));
X data = hp->nodes[n]->data;
X return data;
X}
X
X
X#ifndef heap_nodes
X/*
X * Current number of nodes in HP.
X */
Xint
Xheap_nodes(heap_p hp)
X{
X return hp->last;
X}
X#endif /* heap_nodes */
X
X
X#ifndef heap_empty
X/*
X * Determine if the heap is empty. Returns 1 if HP has no elements and 0
X * otherwise.
X */
Xint
Xheap_empty(heap_p hp)
X{
X return (hp->last <= 0) ? 1 : 0;
X}
X#endif /* heap_empty */
X
X/****************** Private Functions *******************/
X
X/*
X * Maintain the heap order property (parent is smaller than children) which
X * may only be violated at ELM downwards. Assumes caller has locked the heap.
X */
Xstatic void
X_heap_ify_down(heap_p hp, heap_node_p elm)
X{
X heap_node* kid;
X int left = 0, right = 0;
X int true = 1;
X while (true) {
X left = Left(elm->id);
X right = Right(elm->id);
X if (! _heap_node_exist(hp, left)) { // At the bottom of the heap (no child).
X assert(!_heap_node_exist(hp, right));
X break;
X }
X else if (! _heap_node_exist(hp, right)) // Only left child exists.
X kid = hp->nodes[left];
X else {
X if (hp->nodes[right]->key < hp->nodes[left]->key)
X kid = hp->nodes[right];
X else
X kid = hp->nodes[left];
X }
X if (elm->key <= kid->key)
X break;
X _heap_swap_element(hp, kid, elm);
X }
X}
X
X
X/*
X * Maintain the heap property above ELM. Caller has locked the heap.
X */
Xstatic void
X_heap_ify_up(heap_p hp, heap_node_p elm)
X{
X heap_node_p parentNode;
X while (elm->id > 0) {
X parentNode = hp->nodes[Parent(elm->id)];
X if (parentNode->key <= elm->key)
X break;
X _heap_swap_element(hp, parentNode, elm); /* Demote the parent. */
X }
X}
X
X
X/*
X * Swap the position of ELM1 and ELM2 in heap structure. Their IDs are also
X * swapped.
X */
Xstatic void
X_heap_swap_element(heap_p hp, heap_node_p elm1, heap_node_p elm2)
X{
X int elm1Id = elm1->id;
X elm1->id = elm2->id;
X elm2->id = elm1Id;
X hp->nodes[elm1->id] = elm1;
X hp->nodes[elm2->id] = elm2;
X}
X
X
X
X#ifdef NOTDEF
X/*
X * Copy KEY and DATA fields of SRC to DEST. ID field is NOT copied.
X */
Xstatic void
X_heap_copy_element(heap_node_p src, heap_node_p dest)
X{
X dest->key = src->key;
X dest->data = src->data;
X}
X#endif /* NOTDEF */
X
X
X/*
X * True if HP needs to be grown in size.
X */
Xstatic int
X_heap_should_grow(heap_p hp)
X{
X if (hp->size <= hp->last)
X return 1;
X return 0;
X}
X
X
X/*
X * Grow HP.
X */
Xstatic void
X_heap_grow(heap_p hp)
X{
X int newSize;
X //heap_node_p * newNodes;
X
X if (hp->size > Threshold)
X newSize = hp->size * SlowRate;
X else
X newSize = hp->size * NormalRate;
X
X hp->nodes = (heap_node_p *)realloc(hp->nodes, newSize * sizeof(heap_node_p));
X //for(i = 0; i < hp->size; i++)
X //newNodes[i] = hp->nodes[i];
X //free(hp->nodes);
X //hp->nodes = newNodes;
X hp->size = newSize;
X}
X
X
X/*
X * True if a node with ID exists in HP.
X */
Xstatic int
X_heap_node_exist(heap_p hp, int id)
X{
X if ((id >= hp->last) || (id < 0) || (hp->nodes[id] == NULL))
X return 0;
X return 1;
X}
X
X/****************************************************************************
X * Printing and debug functions
X ****************************************************************************/
X
X/*
X * Print the heap in element order, id..last.
X */
Xvoid
Xheap_print_inorder(heap_p hp, int id)
X{
X while (id < hp->last) {
X printf("%d\tKey = %.04f\n", id, hp->nodes[id]->key);
X id++;
X }
X}
X
X/*
X * Returns 1 if HP maintians the heap property and 0 otherwise.
X */
Xint
Xverify_heap_property(heap_p hp)
X{
X int i = 0;
X int correct = 1;
X for(i = 0; i < hp->last / 2; i++) {
X correct = 1;
X if (_heap_node_exist(hp, Left(i)))
X if (hp->nodes[i]->key > hp->nodes[Left(i)]->key)
X correct = 0;
X if (_heap_node_exist(hp, Right(i)))
X if (hp->nodes[i]->key > hp->nodes[Right(i)]->key)
X correct = 0;
X if (!correct) {
X printf("verifyHeap: violated at %d", i);
X heap_print_inorder(hp, 0);
X break;
X }
X }
X return correct;
X}
X
X#ifdef MEASURE_HEAP_SKEW
X
X/****************************************************************************
X * Heap skew computation
X ****************************************************************************/
X
Xint
Xcompare_heap_keys(const void * a, const void * b)
X{
X heap_node ** an = (heap_node**)a;
X heap_node ** bn = (heap_node**)b;
X float cmp = (*an)->key - (*bn)->key;
X if (cmp < 0)
X return -1;
X else
X return 1;
X}
X
X/*
X * Compute the heap skew for HEAP, a measure of how out-of-order the
X * elements in the heap are. The skew of a heap node is the difference
X * between its current position in the heap and where it would be if the
X * heap were in sorted order. To compute this we have to sort the heap. At
X * the end if the flag REPLACE is non-zero the heap will be returned in
X * sorted order (with skew == 0). Note: using REPLACE does not help the
X * performance of the heap, so only do this if you really want to have a
X * sorted heap. It is faster not to replace.
X */
Xfloat
Xcalc_heap_skew(heap_p heap, int replace)
X{
X heap_node ** nodes;
X long id, diff, skew = 0;
X #ifdef HEAP_DEBUG_SKEW
X long skewsq = 0;
X #endif /* HEAP_DEBUG_SKEW */
X float norm = 0;
X unsigned long max;
X
X /*
X * Lock the heap to copy it. If replacing it need to keep the heap locked
X * until we are all done.
X */
X mutex_lock(hp->lock);
X
X max = heap_nodes(heap);
X
X /*
X * Copy the heap nodes to a new storage area for offline sorting.
X */
X nodes = (heap_node **)malloc(max * sizeof(heap_node *));
X memcpy(nodes, heap->nodes, max * sizeof(heap_node *));
X
X if (replace == 0) {
X /*
X * Unlock the heap to allow updates from other threads before the sort.
X * This allows other heap operations to proceed concurrently with the
X * heap skew computation on the heap at the time of the call ...
X */
X mutex_unlock(hp->lock);
X }
X
X qsort(nodes, max, sizeof(heap_node *), compare_heap_keys);
X
X for (id=0; id < max; id++) {
X diff = id - nodes[id]->id;
X skew += abs(diff);
X
X #ifdef HEAP_DEBUG_SKEW
X skewsq += diff*diff;
X #ifdef HEAP_DEBUG_ALL
X printf("%d\tKey = %f, diff = %d\n", id, nodes[id]->key, diff);
X #endif /* HEAP_DEBUG */
X #endif /* HEAP_DEBUG_SKEW */
X }
X
X if (replace != 0) {
X /*
X * Replace the original heap with the newly sorted heap and let it
X * continue. Then compute the skew using the copy of the previous heap
X * which we maintain as private data.
X */
X memcpy(heap->nodes, nodes, max * sizeof(heap_node *));
X
X for (id = 0; id < max; id++) {
X /*
X * Fix up all the ID values in the copied nodes.
X */
X heap->nodes[id]->id = id;
X }
X
X mutex_unlock(hp->lock);
X }
X
X /*
X * The skew value is normalized to a range of [0..1]; the distribution
X * appears to be a skewed Gaussian distribution. For random insertions
X * into a heap the normalized skew will be slightly less than 0.5. The
X * maximum value of skew/N^2 (for any value of N) is about 0.39 and is
X * fairly stable.
X */
X norm = skew*2.56/(max*max);
X
X /*
X * Free the nodes array; note this is just an array of pointers, not data!
X */
X free(nodes);
X return norm;
X}
X
X#endif /* MEASURE_HEAP_SKEW */
SHAR_EOF
  : || $echo 'restore of' 'lib/heap.c' 'failed'
fi
rm -fr _sh02595
exit 0
Received on Tue Jul 29 2003 - 13:15:58 MDT