From dc1e2dec0ca62fd71aecdb85195e60f8adc483ef Mon Sep 17 00:00:00 2001 From: Ian Holsman Date: Thu, 6 Jun 2002 19:07:09 +0000 Subject: [PATCH] implement a fixed size cache in mod_mem_cache using a priority queue PR: Obtained from: Submitted by: Reviewed by: git-svn-id: https://svn.apache.org/repos/asf/httpd/httpd/trunk@95551 13f79535-47bb-0310-9956-ffa450edef68 --- CHANGES | 3 + modules/experimental/cache_cache.c | 155 +++++++++++++++ modules/experimental/cache_cache.h | 154 ++++++++++++++ modules/experimental/cache_pqueue.c | 287 +++++++++++++++++++++++++++ modules/experimental/cache_pqueue.h | 187 +++++++++++++++++ modules/experimental/config.m4 | 2 + modules/experimental/mod_cache.imp | 42 ++-- modules/experimental/mod_mem_cache.c | 232 ++++++++++++++++++---- 8 files changed, 999 insertions(+), 63 deletions(-) create mode 100644 modules/experimental/cache_cache.c create mode 100644 modules/experimental/cache_cache.h create mode 100644 modules/experimental/cache_pqueue.c create mode 100644 modules/experimental/cache_pqueue.h diff --git a/CHANGES b/CHANGES index f7c275ef27..7b63feca76 100644 --- a/CHANGES +++ b/CHANGES @@ -1,5 +1,8 @@ Changes with Apache 2.0.37 + *) Implement a fixed size memory cache using a priority queue + [Ian Holsman] + *) Fix apxs to allow "apxs -q installbuilddir" and to allow querying certain other variables from config_vars.mk. PR 9316 [Jeff Trawick] diff --git a/modules/experimental/cache_cache.c b/modules/experimental/cache_cache.c new file mode 100644 index 0000000000..4fc027431e --- /dev/null +++ b/modules/experimental/cache_cache.c @@ -0,0 +1,155 @@ +/* cache.c */ +#include "apr_general.h" + +#include "mod_cache.h" +#include "cache_hash.h" +#include "cache_pqueue.h" +#include "cache_cache.h" + +#if APR_HAVE_STDLIB_H +#include +#endif +#if APR_HAVE_STRING_H +#include +#endif + +struct cache_cache_t { + int max_entries; + apr_size_t max_size; + apr_size_t current_size; + int total_purges; + long queue_clock; + cache_hash_t *ht; + cache_pqueue_t *pq; + cache_pqueue_set_priority* set_pri; + cache_pqueue_get_priority* get_pri; + cache_cache_inc_frequency *inc_entry; + cache_cache_get_size *size_entry; + cache_cache_get_key *key_entry; + cache_cache_free *free_entry; +}; + +CACHE_DECLARE(cache_cache_t *)cache_init(int max_entries, + apr_size_t max_size, + cache_pqueue_get_priority *get_pri, + cache_pqueue_set_priority *set_pri, + cache_pqueue_getpos get_pos, + cache_pqueue_setpos set_pos, + cache_cache_inc_frequency *inc_entry, + cache_cache_get_size *size_entry, + cache_cache_get_key* key_entry, + cache_cache_free *free_entry) +{ + cache_cache_t *tmp; + tmp = malloc(sizeof(cache_cache_t)); + tmp->max_entries = max_entries; + tmp->max_size = max_size; + tmp->current_size = 0; + tmp->total_purges = 0; + tmp->queue_clock = 0; + tmp->get_pri = get_pri; + tmp->set_pri = set_pri; + tmp->inc_entry = inc_entry; + tmp->size_entry = size_entry; + tmp->key_entry = key_entry; + tmp->free_entry = free_entry; + + tmp->ht = cache_hash_make(max_entries); + tmp->pq = cache_pq_init(max_entries, get_pri, get_pos, set_pos); + + return tmp; +} + +CACHE_DECLARE(void) cache_free(cache_cache_t *c) +{ + cache_pq_free(c->pq); + cache_hash_free(c->ht); + free(c); +} + + +CACHE_DECLARE(void*) cache_find(cache_cache_t* c, const char *key) +{ + void *e; + + e = cache_hash_get(c->ht, key, CACHE_HASH_KEY_STRING); + if (!e) + return NULL; + + return e; +} + +CACHE_DECLARE(void) cache_update(cache_cache_t* c, void *entry) +{ + long old_priority; + long new_priority; + + old_priority = c->set_pri(c->queue_clock, entry); + c->inc_entry(entry); + new_priority = c->set_pri(c->queue_clock, entry); + cache_pq_change_priority(c->pq, old_priority, new_priority, entry); +} + +CACHE_DECLARE(void) cache_insert(cache_cache_t* c, void *entry) +{ + void *ejected = NULL; + long priority; + + c->set_pri(c->queue_clock, entry); + /* FIX: check if priority of bottom item is greater than inserted one */ + while ((cache_pq_size(c->pq) >= c->max_entries) || + ((c->current_size + c->size_entry(entry)) > c->max_size)) { + + ejected = cache_pq_pop(c->pq); + priority = c->get_pri(ejected); + + if (c->queue_clock < priority) + c->queue_clock = priority; + + cache_hash_set(c->ht, + c->key_entry(ejected), + CACHE_HASH_KEY_STRING, + NULL); + + ap_log_error(APLOG_MARK, APLOG_DEBUG, 0, NULL, "Cache Purge of %s",c->key_entry(ejected)); + c->current_size -= c->size_entry(ejected); + c->free_entry(ejected); + c->total_purges++; + } + c->current_size += c->size_entry(entry); + + cache_pq_insert(c->pq, entry); + cache_hash_set(c->ht, c->key_entry(entry), CACHE_HASH_KEY_STRING, entry); +} + +CACHE_DECLARE(void *) cache_pop(cache_cache_t *c) +{ + void *entry; + + if (!c) + return NULL; + + entry = cache_pq_pop(c->pq); + + if (!entry) + return NULL; + + c->current_size -= c->size_entry(entry); + cache_hash_set(c->ht, c->key_entry(entry), CACHE_HASH_KEY_STRING, NULL); + + return entry; +} + +CACHE_DECLARE(apr_status_t) cache_remove(cache_cache_t *c, void *entry) +{ + apr_size_t entry_size = c->size_entry(entry); + apr_status_t rc; + rc = cache_pq_remove(c->pq, entry); + if (rc != APR_SUCCESS) + return rc; + + cache_hash_set(c->ht, c->key_entry(entry), CACHE_HASH_KEY_STRING, NULL); + c->current_size -= entry_size; + + return APR_SUCCESS; +} diff --git a/modules/experimental/cache_cache.h b/modules/experimental/cache_cache.h new file mode 100644 index 0000000000..c6078ac86b --- /dev/null +++ b/modules/experimental/cache_cache.h @@ -0,0 +1,154 @@ +/* ==================================================================== + * The Apache Software License, Version 1.1 + * + * Copyright (c) 2000-2002 The Apache Software Foundation. All rights + * reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. The end-user documentation included with the redistribution, + * if any, must include the following acknowledgment: + * "This product includes software developed by the + * Apache Software Foundation (http://www.apache.org/)." + * Alternately, this acknowledgment may appear in the software itself, + * if and wherever such third-party acknowledgments normally appear. + * + * 4. The names "Apache" and "Apache Software Foundation" must + * not be used to endorse or promote products derived from this + * software without prior written permission. For written + * permission, please contact apache@apache.org. + * + * 5. Products derived from this software may not be called "Apache", + * nor may "Apache" appear in their name, without prior written + * permission of the Apache Software Foundation. + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * ==================================================================== + * + * This software consists of voluntary contributions made by many + * individuals on behalf of the Apache Software Foundation. For more + * information on the Apache Software Foundation, please see + * . + * + * Portions of this software are based upon public domain software + * originally written at the National Center for Supercomputing Applications, + * University of Illinois, Urbana-Champaign. + */ + +#ifndef CACHE_CACHE_H +#define CACHE_CACHE_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include "mod_cache.h" + +/** + * @file cache_hash.h + * @brief Cache Cache Functions + */ + +/** + * @defgroup Cache_cache Cache Functions + * @ingroup CACHE + * @{ + */ +/** ADT for the cache */ +typedef struct cache_cache_t cache_cache_t; + +/** callback to increment the frequency of a item */ +typedef void cache_cache_inc_frequency(void*a); +/** callback to get the size of a item */ +typedef apr_size_t cache_cache_get_size(void*a); +/** callback to get the key of a item */ +typedef const char* cache_cache_get_key(void *a); +/** callback to free an entry */ +typedef void cache_cache_free(void *a); + +/** + * initialize the cache ADT + * @param max_entries the number of entries in the cache + * @param max_size the size of the cache + * @param get_pri callback to get a priority of a entry + * @param set_pri callback to set a priority of a entry + * @param get_pos callback to get the position of a entry in the cache + * @param set_pos callback to set the position of a entry in the cache + * @param inc_entry callback to increment the frequency of a entry + * @param size_entry callback to get the size of a entry + * @param key_entry callback to get the key of a entry + * @param free_entry callback to free an entry + */ +CACHE_DECLARE(cache_cache_t *)cache_init(int max_entries, + apr_size_t max_size, + cache_pqueue_get_priority *get_pri, + cache_pqueue_set_priority *set_pri, + cache_pqueue_getpos get_pos, + cache_pqueue_setpos set_pos, + cache_cache_inc_frequency *inc_entry, + cache_cache_get_size *size_entry, + cache_cache_get_key *key_entry, + cache_cache_free *free_entry); + +/** + * free up the cache + * @param c the cache + */ +CACHE_DECLARE(void) cache_free(cache_cache_t *c); +/** + * find a entry in the cache, incrementing the frequency if found + * @param c the cache + * @param key the key + */ +CACHE_DECLARE(void*) cache_find(cache_cache_t* c, const char *key); +/** + * insert a entry into the cache + * @param c the cache + * @param entry the entry + */ +CACHE_DECLARE(void) cache_update(cache_cache_t* c, void *entry); +/** + * insert a entry into the cache + * @param c the cache + * @param entry the entry + */ +CACHE_DECLARE(void) cache_insert(cache_cache_t* c, void *entry); +/** + * pop the lowest priority item off + * @param c the cache + * @returns the entry or NULL + */ +CACHE_DECLARE(void *)cache_pop(cache_cache_t* c); +/** + * remove an item from the cache + * @param c the cache + * @param entry the actual entry (from a find) + */ +CACHE_DECLARE(apr_status_t) cache_remove(cache_cache_t* c, void *entry); +/** @} */ +#ifdef __cplusplus +} +#endif + +#endif /* !CACHE_CACHE_H */ diff --git a/modules/experimental/cache_pqueue.c b/modules/experimental/cache_pqueue.c new file mode 100644 index 0000000000..e14076ab32 --- /dev/null +++ b/modules/experimental/cache_pqueue.c @@ -0,0 +1,287 @@ +#include "apr_general.h" + +#if APR_HAVE_STDLIB_H +#include +#endif +#if APR_HAVE_STDIO_H +#include +#endif + +#if APR_HAVE_STRING_H +#include +#endif + +#include "cache_pqueue.h" +#define left(i) (2*(i)) +#define right(i) ((2*i)+1) +#define parent(i) (i/2) +/* + * Priority queue structure + */ +struct cache_pqueue_t +{ + apr_ssize_t size; + apr_ssize_t avail; + apr_ssize_t step; + cache_pqueue_get_priority* pri; + cache_pqueue_getpos* get; + cache_pqueue_setpos* set; + void **d; +}; + +cache_pqueue_t *cache_pq_init(apr_ssize_t n, + cache_pqueue_get_priority* pri, + cache_pqueue_getpos get, + cache_pqueue_setpos set) +{ + cache_pqueue_t *q; + + if (!(q = malloc(sizeof(cache_pqueue_t)))) { + return NULL; + } + + if (!(q->d = malloc(sizeof(void*) * n))) { + free(q); + return NULL; + } + q->avail = q->step = n; + q->pri = pri; + q->size = 1; + q->get = get; + q->set = set; + return q; +} +/* + * cleanup + */ +void cache_pq_free(cache_pqueue_t *q) +{ + free(q->d); + free(q); +} +/* + * pqsize: size of the queue. + */ +apr_ssize_t cache_pq_size(cache_pqueue_t *q) +{ + return q->size; +} + +static void cache_pq_bubble_up(cache_pqueue_t*q, apr_ssize_t i) +{ + apr_ssize_t parent_node; + parent_node = parent(i); + + while (i > 1 && q->pri(q->d[parent_node]) < q->pri(q->d[i])) { + void *tmp; + tmp = q->d[i]; + + q->d[i] = q->d[parent_node]; + q->d[parent_node] = tmp; + q->set(q->d[i], i); + q->set(q->d[parent_node], parent_node); + i = parent_node; + parent_node = parent(i); + } +} + +static apr_ssize_t minchild(cache_pqueue_t *q, apr_ssize_t i) +{ + apr_ssize_t y, minc; + minc = left(i); + if (minc >= q->size) + return -1; + + for (y = minc + 1; y <= right(i) && y < q->size; y++) { + if (q->pri(q->d[y]) > q->pri(q->d[minc])) + minc = y; + } + return minc; +} + +static void cache_pq_percolate_down(cache_pqueue_t*q, apr_ssize_t i) +{ + apr_ssize_t cx = minchild(q, i); + while ((cx != -1) && (q->pri(q->d[cx]) > q->pri(q->d[i]))) + { + void *tmp; + + tmp = q->d[i]; + q->d[i] = q->d[cx]; + q->d[cx] = tmp; + q->set(q->d[i], i); + q->set(q->d[cx], cx); + i = cx; + cx = minchild(q, i); + } +} + +apr_status_t cache_pq_insert(cache_pqueue_t *q, void* d) +{ + void *tmp; + apr_ssize_t i; + apr_ssize_t parent_node; + apr_ssize_t newsize; + + if (!q) return APR_EGENERAL; + + /* allocate more memory if necessary */ + if (q->size >= q->avail) { + newsize = q->size + q->step; + if (!(tmp = realloc(q->d, sizeof(void*) * newsize))) { + return APR_EGENERAL; + }; + q->d = tmp; + q->avail = newsize; + } + + /* insert item */ + i = q->size++; + parent_node = parent(i); + /* + * this is an optimization of the bubble-up as it doesn't + * have to swap the member around + */ + while ((i > 1) && q->pri(q->d[parent_node]) < q->pri(d)) { + q->d[i] = q->d[parent_node]; + q->set(q->d[i], i); + i = parent_node; + parent_node = parent(i); + } + q->d[i] = d; + q->set(q->d[i], i); + return APR_SUCCESS; +} + +/* + * move a existing entry to a new priority + */ +void cache_pq_change_priority(cache_pqueue_t*q, + long old_priority, + long new_priority, + void *d) +{ + apr_ssize_t posn; + + posn = q->get(d); + if (new_priority > old_priority) + cache_pq_bubble_up(q, posn); + else + cache_pq_percolate_down(q, posn); +} + +apr_status_t cache_pq_remove(cache_pqueue_t *q, void* d) +{ + apr_ssize_t posn; + void *popped = NULL; + long pri_popped; + long pri_removed; + + posn = q->get(d); + popped = cache_pq_pop(q); + + if (!popped) + return APR_EGENERAL; + + if (d == popped) { + return APR_SUCCESS; + } + pri_popped = q->pri(popped); + pri_removed = q->pri(d); + + q->d[posn] = popped; + q->set(popped,posn); + if (pri_popped > pri_removed) + cache_pq_bubble_up(q, posn); + else + cache_pq_percolate_down(q, posn); + + return APR_SUCCESS; +} + +void *cache_pq_pop(cache_pqueue_t *q) +{ + void *tmp; + void *d; + int i = 1; + int j; + + if (!q || q->size == 1) + return NULL; + + d = q->d[1]; + tmp = q->d[--q->size]; + while (i <= q->size / 2) { + j = 2 * i; + if (j < q->size && q->pri(q->d[j]) < q->pri(q->d[j + 1])) { + j++; + } + if (q->pri(q->d[j]) <= q->pri(tmp)) { + break; + } + q->d[i] = q->d[j]; + q->set(d, i); + i = j; + } + q->d[i] = tmp; + q->set(d, i); + return d; +} + +void *cache_pq_peek(cache_pqueue_t *q) +{ + void *d; + if (!q || q->size == 1) + return NULL; + d = q->d[1]; + return d; +} + +static void cache_pq_set_null( void*d, int val) +{ + /* do nothing */ +} +/* + * this is a debug function.. so it's EASY not fast + */ +void cache_pq_dump(cache_pqueue_t *q, + FILE*out, + cache_pqueue_print_entry print) +{ + int i; + + fprintf(stdout,"posn\tleft\tright\tparent\tminchild\t...\n"); + for (i = 1; i < q->size ;i++) { + fprintf(stdout, + "%d\t%d\t%d\t%d\t%d\t", + i, + left(i), right(i), parent(i), + minchild(q, i)); + print(out, q->d[i]); + } +} +/* + * this is a debug function.. so it's EASY not fast + */ +void cache_pq_print(cache_pqueue_t *q, + FILE*out, + cache_pqueue_print_entry print) +{ + cache_pqueue_t *dup; + dup = cache_pq_init(q->size, q->pri, q->get, cache_pq_set_null); + dup->size = q->size; + dup->avail = q->avail; + dup->step = q->step; + + memcpy(dup->d, q->d, q->size*sizeof(void*)); + + while (cache_pq_size(dup) > 1) { + void *e = NULL; + e = cache_pq_pop(dup); + if (e) + print(out, e); + else + break; + } + cache_pq_free(dup); +} diff --git a/modules/experimental/cache_pqueue.h b/modules/experimental/cache_pqueue.h new file mode 100644 index 0000000000..286d6b94a7 --- /dev/null +++ b/modules/experimental/cache_pqueue.h @@ -0,0 +1,187 @@ +/* ==================================================================== + * The Apache Software License, Version 1.1 + * + * Copyright (c) 2000-2002 The Apache Software Foundation. All rights + * reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. The end-user documentation included with the redistribution, + * if any, must include the following acknowledgment: + * "This product includes software developed by the + * Apache Software Foundation (http://www.apache.org/)." + * Alternately, this acknowledgment may appear in the software itself, + * if and wherever such third-party acknowledgments normally appear. + * + * 4. The names "Apache" and "Apache Software Foundation" must + * not be used to endorse or promote products derived from this + * software without prior written permission. For written + * permission, please contact apache@apache.org. + * + * 5. Products derived from this software may not be called "Apache", + * nor may "Apache" appear in their name, without prior written + * permission of the Apache Software Foundation. + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * ==================================================================== + * + * This software consists of voluntary contributions made by many + * individuals on behalf of the Apache Software Foundation. For more + * information on the Apache Software Foundation, please see + * . + * + * Portions of this software are based upon public domain software + * originally written at the National Center for Supercomputing Applications, + * University of Illinois, Urbana-Champaign. + */ + +#ifndef CACHE_PQUEUE_H +#define CACHE_PQUEUE_H + +#ifdef __cplusplus +extern "C" { +#endif + +/** the cache priority queue handle */ +typedef struct cache_pqueue_t cache_pqueue_t; + +/** + * callback function to assign a priority for a element + * @param a the element + * @return the score (the lower the score the longer it is kept int the queue) + */ +typedef long cache_pqueue_set_priority(long queue_clock, void*a); +typedef long cache_pqueue_get_priority(void*a); + +/** callback function to get a position of a element */ +typedef apr_ssize_t cache_pqueue_getpos(void *a); + +/** + * callback function to set a position of a element + * @param a the element + * @param pos the position to set it to + */ +typedef void cache_pqueue_setpos(void *a, apr_ssize_t pos); + +/** debug callback function to print a entry */ +typedef void cache_pqueue_print_entry(FILE *out, void *a); + +/** + * initialize the queue + * + * @param n the intial estimate of the number of queue items for which memory + * should be preallocated + * @param pri the callback function to run to assign a score to a element + * @param get the callback function to get the current element's position + * @param set the callback function to set the current element's position + * + * @Return the handle or NULL for insufficent memory + */ +cache_pqueue_t *cache_pq_init(apr_ssize_t n, + cache_pqueue_get_priority* pri, + cache_pqueue_getpos get, + cache_pqueue_setpos set); +/** + * free all memory used by the queue + * @param q the queue + */ +void cache_pq_free(cache_pqueue_t *q); +/** + * return the size of the queue. + * @param q the queue + */ +apr_ssize_t cache_pq_size(cache_pqueue_t *q); + +/** + * insert an item into the queue. + * @param q the queue + * @param d the item + * @return APR_SUCCESS on success + */ +apr_status_t cache_pq_insert(cache_pqueue_t *q, void* d); + +/* + * move a existing entry to a different priority + * @param q the queue + * @param old the old priority + * @param d the entry + */ +void cache_pq_change_priority(cache_pqueue_t *q, + long old_priority, + long new_priority, + void *d); + +/** + * pop the highest-ranking item from the queue. + * @param p the queue + * @param d where to copy the entry to + * @return NULL on error, otherwise the entry + */ +void *cache_pq_pop(cache_pqueue_t *q); + +/** + * remove an item from the queue. + * @param p the queue + * @param d the entry + * @return APR_SUCCESS on success + */ +apr_status_t cache_pq_remove(cache_pqueue_t *q, void *d); + +/** + * access highest-ranking item without removing it. + * @param q the queue + * @param d the entry + * @return NULL on error, otherwise the entry + */ +void *cache_pq_peek(cache_pqueue_t *q); + +/** + * print the queue + * @internal + * DEBUG function only + * @param q the queue + * @param out the output handle + * @param the callback function to print the entry + */ +void cache_pq_print(cache_pqueue_t *q, + FILE *out, + cache_pqueue_print_entry print); + +/** + * dump the queue and it's internal structure + * @internal + * debug function only + * @param q the queue + * @param out the output handle + * @param the callback function to print the entry + */ +void cache_pq_dump(cache_pqueue_t *q, + FILE *out, + cache_pqueue_print_entry print); + +#ifdef __cplusplus +} +#endif + +#endif /* !CACHE_PQUEUE_H */ diff --git a/modules/experimental/config.m4 b/modules/experimental/config.m4 index 9eeceacbce..eb5e7e34a3 100644 --- a/modules/experimental/config.m4 +++ b/modules/experimental/config.m4 @@ -18,6 +18,8 @@ cache_util.lo dnl dnl # list of object files for mod_mem_cache mem_cache_objs="dnl mod_mem_cache.lo dnl +cache_cache.lo dnl +cache_pqueue.lo dnl cache_hash.lo dnl " APACHE_MODULE(cache, dynamic file caching, $cache_objs, , no) diff --git a/modules/experimental/mod_cache.imp b/modules/experimental/mod_cache.imp index 2d0590252f..11b0bce79f 100644 --- a/modules/experimental/mod_cache.imp +++ b/modules/experimental/mod_cache.imp @@ -1,21 +1,21 @@ - (MODCACHE) - ap_cache_request_is_conditional, - ap_cache_reset_output_filters, - ap_cache_get_cachetype, - ap_cache_liststr, - ap_cache_tokstr, - ap_cache_hex2usec, - ap_cache_usec2hex, - generate_name, - cache_hook_create_entity, - cache_hook_open_entity, - cache_hook_remove_url, - cache_hash_set, - cache_hash_this, - cache_hash_first, - cache_hash_make, - cache_hash_get, - cache_hash_next, - cache_hash_count, - cache_hash_free, - + (MODCACHE) + ap_cache_request_is_conditional, + ap_cache_reset_output_filters, + ap_cache_get_cachetype, + ap_cache_liststr, + ap_cache_tokstr, + ap_cache_hex2usec, + ap_cache_usec2hex, + generate_name, + cache_hook_create_entity, + cache_hook_open_entity, + cache_hook_remove_url, + cache_hash_set, + cache_hash_this, + cache_hash_first, + cache_hash_make, + cache_hash_get, + cache_hash_next, + cache_hash_count, + cache_hash_free, + diff --git a/modules/experimental/mod_mem_cache.c b/modules/experimental/mod_mem_cache.c index bf6441edd8..82f78f4385 100644 --- a/modules/experimental/mod_mem_cache.c +++ b/modules/experimental/mod_mem_cache.c @@ -58,7 +58,8 @@ #define CORE_PRIVATE #include "mod_cache.h" -#include "cache_hash.h" +#include "cache_pqueue.h" +#include "cache_cache.h" #include "ap_mpm.h" #include "apr_thread_mutex.h" #if APR_HAVE_UNISTD_H @@ -95,11 +96,14 @@ typedef struct mem_cache_object { apr_size_t m_len; void *m; apr_os_file_t fd; + long priority; /**< the priority of this entry */ + long total_refs; /**< total number of references this entry has had */ + apr_ssize_t pos; /**< the position of this entry in the cache */ } mem_cache_object_t; typedef struct { apr_thread_mutex_t *lock; - cache_hash_t *cacheht; + cache_cache_t *cache_cache; apr_size_t cache_size; apr_size_t object_cnt; @@ -108,6 +112,7 @@ typedef struct { apr_size_t max_cache_object_size; /* in bytes */ apr_size_t max_cache_size; /* in bytes */ apr_size_t max_object_cnt; + cache_pqueue_set_priority *cache_remove_algorithm; } mem_cache_conf; static mem_cache_conf *sconf; @@ -125,6 +130,102 @@ static apr_status_t write_body(cache_handle_t *h, request_rec *r, apr_bucket_bri static apr_status_t read_headers(cache_handle_t *h, request_rec *r); static apr_status_t read_body(cache_handle_t *h, apr_pool_t *p, apr_bucket_brigade *bb); +static void cleanup_cache_object(cache_object_t *obj); + +static long memcache_get_priority(void*a) +{ + cache_object_t *obj = (cache_object_t *)a; + mem_cache_object_t *mobj = obj->vobj; + +#ifdef USE_ATOMICS + return (long)apr_atomic_read(&mobj->priority); +#else + return mobj->priority; +#endif + +} + +static void memcache_inc_frequency(void*a) +{ + cache_object_t *obj = (cache_object_t *)a; + mem_cache_object_t *mobj = obj->vobj; + + mobj->total_refs++; + mobj->priority = 0; +} + +static void memcache_set_pos(void *a, apr_ssize_t pos) +{ + cache_object_t *obj = (cache_object_t *)a; + mem_cache_object_t *mobj = obj->vobj; + +#ifdef USE_ATOMICS + apr_atomic_set(&mobj->pos, pos); +#else + mobj->pos = pos; +#endif +} +static apr_ssize_t memcache_get_pos(void *a) +{ + cache_object_t *obj = (cache_object_t *)a; + mem_cache_object_t *mobj = obj->vobj; + +#ifdef USE_ATOMICS + return apr_atomic_read(&mobj->pos); +#else + return mobj->pos; +#endif +} + +static apr_size_t memcache_cache_get_size(void*a) +{ + cache_object_t *obj = (cache_object_t *)a; + mem_cache_object_t *mobj = obj->vobj; + return mobj->m_len; +} +/** callback to get the key of a item */ +static const char* memcache_cache_get_key(void*a) +{ + cache_object_t *obj = (cache_object_t *)a; + return obj->key; +} +/** + * callback to free an entry + * XXX: just call cleanup_cache_object ? + */ +static void memcache_cache_free(void*a) +{ + cache_object_t *obj = (cache_object_t *)a; + cleanup_cache_object(obj); +} +/* + * functions return a 'negative' score as lower is better in a priority Q + */ +static long memcache_lru_algorithm(long queue_clock, void *a) +{ + cache_object_t *obj = (cache_object_t *)a; + mem_cache_object_t *mobj = obj->vobj; + if (mobj->priority == 0) + mobj->priority = ((long)(queue_clock + mobj->total_refs)); + + /* + * a 'proper' LRU function would just be + * mobj->priority = mobj->total_refs; + */ + return -1*mobj->priority; +} + +static long memcache_gdsf_algorithm(long queue_clock, void *a) +{ + cache_object_t *obj = (cache_object_t *)a; + mem_cache_object_t *mobj = obj->vobj; + + if (mobj->priority == 0) + mobj->priority = queue_clock + (long)(mobj->total_refs*1000 / mobj->m_len); + + return -1*mobj->priority; +} + static void cleanup_cache_object(cache_object_t *obj) { mem_cache_object_t *mobj = obj->vobj; @@ -188,7 +289,6 @@ static void cleanup_cache_object(cache_object_t *obj) } free(mobj); } - return; } static apr_status_t decrement_refcount(void *arg) { @@ -207,7 +307,7 @@ static apr_status_t decrement_refcount(void *arg) * removed the object from the cache (and set obj->cleanup) */ if (!obj->cleanup) { - cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), NULL); + cache_remove(sconf->cache_cache, obj); sconf->object_cnt--; sconf->cache_size -= mobj->m_len; obj->cleanup = 1; @@ -244,39 +344,37 @@ static apr_status_t decrement_refcount(void *arg) static apr_status_t cleanup_cache_mem(void *sconfv) { cache_object_t *obj; - cache_hash_index_t *hi; mem_cache_conf *co = (mem_cache_conf*) sconfv; if (!co) { return APR_SUCCESS; } + if (!co->cache_cache) { + return APR_SUCCESS; + } if (sconf->lock) { apr_thread_mutex_lock(sconf->lock); } - /* Iterate over the cache and clean up each entry */ - while ((hi = cache_hash_first(co->cacheht)) != NULL) { - /* Fetch the object from the cache */ - cache_hash_this(hi, NULL, NULL, (void **)&obj); - if (obj) { - /* Remove the object from the cache */ - cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), NULL); - /* Free the object if the recount == 0 */ + obj = cache_pop(co->cache_cache); + while (obj) { + /* Iterate over the cache and clean up each entry */ + /* Free the object if the recount == 0 */ #ifdef USE_ATOMICS - apr_atomic_inc(&obj->refcount); - obj->cleanup = 1; - if (!apr_atomic_dec(&obj->refcount)) { + apr_atomic_inc(&obj->refcount); + obj->cleanup = 1; + if (!apr_atomic_dec(&obj->refcount)) { #else - obj->cleanup = 1; - if (!obj->refcount) { + obj->cleanup = 1; + if (!obj->refcount) { #endif - cleanup_cache_object(obj); - } + cleanup_cache_object(obj); } + obj = cache_pop(co->cache_cache); } /* Cache is empty, free the cache table */ - cache_hash_free(co->cacheht); + cache_free(co->cache_cache); if (sconf->lock) { apr_thread_mutex_unlock(sconf->lock); @@ -298,6 +396,8 @@ static void *create_cache_config(apr_pool_t *p, server_rec *s) /* Size of the cache in bytes */ sconf->max_cache_size = DEFAULT_MAX_CACHE_SIZE; sconf->cache_size = 0; + sconf->cache_cache = NULL; + sconf->cache_remove_algorithm = memcache_gdsf_algorithm; return sconf; } @@ -325,19 +425,27 @@ static int create_entity(cache_handle_t *h, request_rec *r, * TODO: Get smarter about managing the cache size. If the cache is * full, we need to garbage collect stale/infrequently referenced * objects. - */ + * we have a self-sizing cache now if (sconf->object_cnt >= sconf->max_object_cnt) { return DECLINED; } + */ if (type_e == CACHE_TYPE_HEAP) { /* We can safely ignore these measures when caching open fds */ if (len < sconf->min_cache_object_size || len > sconf->max_cache_object_size) { + ap_log_error(APLOG_MARK, APLOG_DEBUG, 0, r->server, + "cache_mem: URL %s failed the size check, " + "or is incomplete", + key); return DECLINED; } + /* + * not needed now we have a self-sizing cache. if ((sconf->cache_size + len) > sconf->max_cache_size) { return DECLINED; } + */ } else { /* CACHE_TYPE_FILE is only valid for local content * handled by the default handler? @@ -361,6 +469,7 @@ static int create_entity(cache_handle_t *h, request_rec *r, strncpy(obj->key, key, strlen(key) + 1); obj->info.len = len; + /* Allocate and init mem_cache_object_t */ mobj = calloc(1, sizeof(*mobj)); if (!mobj) { @@ -374,6 +483,7 @@ static int create_entity(cache_handle_t *h, request_rec *r, #else obj->refcount = 1; #endif + mobj->total_refs = 1; obj->complete = 0; obj->cleanup = 0; obj->vobj = mobj; @@ -395,11 +505,10 @@ static int create_entity(cache_handle_t *h, request_rec *r, if (sconf->lock) { apr_thread_mutex_lock(sconf->lock); } - tmp_obj = (cache_object_t *) cache_hash_get(sconf->cacheht, - key, - CACHE_HASH_KEY_STRING); + tmp_obj = (cache_object_t *) cache_find(sconf->cache_cache, key); + if (!tmp_obj) { - cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), obj); + cache_insert(sconf->cache_cache, obj); sconf->object_cnt++; sconf->cache_size += len; } @@ -441,17 +550,18 @@ static int open_entity(cache_handle_t *h, request_rec *r, const char *type, cons if (sconf->lock) { apr_thread_mutex_lock(sconf->lock); } - obj = (cache_object_t *) cache_hash_get(sconf->cacheht, key, - CACHE_HASH_KEY_STRING); + obj = (cache_object_t *) cache_find(sconf->cache_cache, key); if (obj) { if (obj->complete) { request_rec *rmain=r, *rtmp; - #ifdef USE_ATOMICS apr_atomic_inc(&obj->refcount); #else obj->refcount++; #endif + /* cache is worried about overall counts, not 'open' ones */ + cache_update(sconf->cache_cache, obj); + /* If this is a subrequest, register the cleanup against * the main request. This will prevent the cache object * from being cleaned up from under the request after the @@ -504,7 +614,7 @@ static int remove_entity(cache_handle_t *h) */ if (!obj->cleanup) { mem_cache_object_t *mobj = (mem_cache_object_t *) obj->vobj; - cache_hash_set(sconf->cacheht, obj->key, strlen(obj->key), NULL); + cache_remove(sconf->cache_cache, obj); sconf->object_cnt--; sconf->cache_size -= mobj->m_len; obj->cleanup = 1; @@ -594,11 +704,12 @@ static int remove_url(const char *type, const char *key) if (sconf->lock) { apr_thread_mutex_lock(sconf->lock); } - /* This call will return a pointer to the cache_object just removed */ - obj = cache_hash_set(sconf->cacheht, key, CACHE_HASH_KEY_STRING, NULL); + + obj = cache_find(sconf->cache_cache, key); if (obj) { - /* obj has been removed from the cache */ - mem_cache_object_t *mobj = (mem_cache_object_t *) obj->vobj; + mem_cache_object_t *mobj; + cache_remove(sconf->cache_cache, obj); + mobj = (mem_cache_object_t *) obj->vobj; sconf->object_cnt--; sconf->cache_size -= mobj->m_len; @@ -635,11 +746,13 @@ static apr_status_t read_headers(cache_handle_t *h, request_rec *r) int rc; mem_cache_object_t *mobj = (mem_cache_object_t*) h->cache_obj->vobj; cache_info *info = &(h->cache_obj->info); - + info->req_hdrs = apr_table_make(r->pool, mobj->num_req_hdrs); - r->headers_out = apr_table_make(r->pool,mobj->num_header_out); + + r->headers_out = apr_table_make(r->pool, mobj->num_header_out); r->subprocess_env = apr_table_make(r->pool, mobj->num_subprocess_env); r->notes = apr_table_make(r->pool, mobj->num_notes); + rc = unserialize_table(mobj->req_hdrs, mobj->num_req_hdrs, info->req_hdrs); @@ -689,7 +802,7 @@ static apr_status_t write_headers(cache_handle_t *h, request_rec *r, cache_info cache_object_t *obj = h->cache_obj; mem_cache_object_t *mobj = (mem_cache_object_t*) obj->vobj; int rc; - + /* * The cache needs to keep track of the following information: * - Date, LastMod, Version, ReqTime, RespTime, ContentLength @@ -703,6 +816,8 @@ static apr_status_t write_headers(cache_handle_t *h, request_rec *r, cache_info if (rc != APR_SUCCESS) { return rc; } + + /* Precompute how much storage we need to hold the headers */ rc = serialize_table(&mobj->header_out, &mobj->num_header_out, r->headers_out); @@ -861,7 +976,7 @@ static apr_status_t write_body(cache_handle_t *h, request_rec *r, apr_bucket_bri /* This should not happen, but if it does, we are in BIG trouble * cause we just stomped all over the heap. */ - AP_DEBUG_ASSERT(obj->count > mobj->m_len); + AP_DEBUG_ASSERT(obj->count >= mobj->m_len); } return APR_SUCCESS; } @@ -876,12 +991,26 @@ static int mem_cache_post_config(apr_pool_t *p, apr_pool_t *plog, if (threaded_mpm) { apr_thread_mutex_create(&sconf->lock, APR_THREAD_MUTEX_DEFAULT, p); } - sconf->cacheht = cache_hash_make(sconf->max_object_cnt); + + sconf->cache_cache = cache_init(sconf->max_object_cnt, + sconf->max_cache_size, + memcache_get_priority, + sconf->cache_remove_algorithm, + memcache_get_pos, + memcache_set_pos, + memcache_inc_frequency, + memcache_cache_get_size, + memcache_cache_get_key, + memcache_cache_free); apr_pool_cleanup_register(p, sconf, cleanup_cache_mem, apr_pool_cleanup_null); - return OK; -} + if (sconf->cache_cache) + return OK; + return -1; + +} + static const char *set_max_cache_size(cmd_parms *parms, void *in_struct_ptr, const char *arg) { @@ -927,6 +1056,23 @@ static const char return NULL; } +static const char +*set_cache_removal_algorithm(cmd_parms *parms, void *name, const char *arg) +{ + if (strcasecmp("LRU", arg)) { + sconf->cache_remove_algorithm = memcache_lru_algorithm; + } + else { + if (strcasecmp("GDSF", arg)) { + sconf->cache_remove_algorithm = memcache_gdsf_algorithm; + } + else { + return "currently implemented algorithms are LRU and GDSF"; + } + } + return NULL; +} + static const command_rec cache_cmds[] = { AP_INIT_TAKE1("MCacheSize", set_max_cache_size, NULL, RSRC_CONF, @@ -937,6 +1083,8 @@ static const command_rec cache_cmds[] = "The minimum size (in bytes) of an object to be placed in the cache"), AP_INIT_TAKE1("MCacheMaxObjectSize", set_max_cache_object_size, NULL, RSRC_CONF, "The maximum size (in bytes) of an object to be placed in the cache"), + AP_INIT_TAKE1("MCacheRemovalAlgorithm", set_cache_removal_algorithm, NULL, RSRC_CONF, + "The algorithm used to remove entries from the cache (default: GDSF)"), {NULL} }; @@ -944,7 +1092,7 @@ static void register_hooks(apr_pool_t *p) { ap_hook_post_config(mem_cache_post_config, NULL, NULL, APR_HOOK_MIDDLE); /* cache initializer */ - /* cache_hook_cache_init(cache_init, NULL, NULL, AP_HOOK_FIRST); */ + /* cache_hook_init(cache_mem_init, NULL, NULL, APR_HOOK_MIDDLE); */ cache_hook_create_entity(create_entity, NULL, NULL, APR_HOOK_MIDDLE); cache_hook_open_entity(open_entity, NULL, NULL, APR_HOOK_MIDDLE); cache_hook_remove_url(remove_url, NULL, NULL, APR_HOOK_MIDDLE); -- 2.40.0