Bill Stoddard wrote:
Not to knock over the apple cart or anything, but had a 15 second chat
with Greg today and he had an idea that sounded good. His idea was to
eliminate the cleanup bit entirely and fold the function it is providing
into the refcount. With the code in HEAD right now, a cache object
sitting in the cache hash table unreferenced by any worker threads has a
refcount of 0. The change is to bump the refcount of a cache object by
1 to reflect that it is being 'referenced' by the hash table. This
simplifies the code quite a bit (assuming I'm not overlooking a hole
that will need plugging). Patch against HEAD on the way.
Bill
Please give this a try and see how it works...
Index: mod_mem_cache.c
===================================================================
RCS file: /home/cvs/httpd-2.0/modules/experimental/mod_mem_cache.c,v
retrieving revision 1.88.2.9
diff -u -r1.88.2.9 mod_mem_cache.c
--- mod_mem_cache.c 26 Aug 2004 16:59:44 -0000 1.88.2.9
+++ mod_mem_cache.c 16 Sep 2004 03:48:02 -0000
@@ -13,6 +13,14 @@
* limitations under the License.
*/
+/*
+ * obj->refcount should only be incremented under protection of the sconf->lock
+ * obj->refcount can be atomically decremented w/o protection of the sconf->lock
+ * obj->refcount is incremented by one when the object is in the cache and once
+ * per thread referencing the object. An object in the cache with no threads
+ * accessing it will have a refcount of 1. When refcount drops to 0, the object
+ * should be garbage collected.
+ */
#define CORE_PRIVATE
#include "mod_cache.h"
#include "cache_pqueue.h"
@@ -142,24 +150,20 @@
return obj->key;
}
/**
- * callback to free an entry
- * There is way too much magic in this code. Right now, this callback
- * is only called out of cache_insert() which is called under protection
- * of the sconf->lock, which means that we do not (and should not)
- * attempt to obtain the lock recursively.
+ * memcache_cache_free()
+ * memcacache_cache_free is a callback that is only invoked during by a thread
+ * running in cache_insert(). cache_insert() runs under protection
+ * of sconf->lock. By the time this function has been entered, the cache_object
+ * has been ejected from the cache. decrement the refcount and if the refcount drop
+ * to 0, cleanup the cache object.
*/
static void memcache_cache_free(void*a)
{
cache_object_t *obj = (cache_object_t *)a;
- /* Cleanup the cache object. Object should be removed from the cache
- * now. Increment the refcount before setting cleanup to avoid a race
- * condition. A similar pattern is used in remove_url()
+ /* Decrement the refcount to account for the object being ejected
+ * from the cache. If the refcount is 0, free the object.
*/
- apr_atomic_inc(&obj->refcount);
-
- obj->cleanup = 1;
-
if (!apr_atomic_dec(&obj->refcount)) {
cleanup_cache_object(obj);
}
@@ -267,31 +271,9 @@
{
cache_object_t *obj = (cache_object_t *) arg;
- /* If obj->complete is not set, the cache update failed and the
- * object needs to be removed from the cache then cleaned up.
- */
- if (!obj->complete) {
- if (sconf->lock) {
- apr_thread_mutex_lock(sconf->lock);
- }
- /* Remember, objects marked for cleanup are, by design, already
- * removed from the cache. remove_url() could have already
- * removed the object from the cache (and set obj->cleanup)
- */
- if (!obj->cleanup) {
- cache_remove(sconf->cache_cache, obj);
- obj->cleanup = 1;
- }
- if (sconf->lock) {
- apr_thread_mutex_unlock(sconf->lock);
- }
- }
-
- /* Cleanup the cache object */
+ /* If the refcount drops to 0, cleanup the cache object */
if (!apr_atomic_dec(&obj->refcount)) {
- if (obj->cleanup) {
- cleanup_cache_object(obj);
- }
+ cleanup_cache_object(obj);
}
return APR_SUCCESS;
}
@@ -312,10 +294,7 @@
}
obj = cache_pop(co->cache_cache);
while (obj) {
- /* Iterate over the cache and clean up each entry */
- /* Free the object if the recount == 0 */
- apr_atomic_inc(&obj->refcount);
- obj->cleanup = 1;
+ /* Iterate over the cache and clean up each unreferenced entry */
if (!apr_atomic_dec(&obj->refcount)) {
cleanup_cache_object(obj);
}
@@ -415,7 +394,6 @@
apr_atomic_set(&obj->refcount, 1);
mobj->total_refs = 1;
obj->complete = 0;
- obj->cleanup = 0;
obj->vobj = mobj;
/* Safe cast: We tested < sconf->max_cache_object_size above */
mobj->m_len = (apr_size_t)len;
@@ -425,7 +403,7 @@
* Note: Perhaps we should wait to put the object in the
* hash table when the object is complete? I add the object here to
* avoid multiple threads attempting to cache the same content only
- * to discover at the very end that only one of them will suceed.
+ * to discover at the very end that only one of them will succeed.
* Furthermore, adding the cache object to the table at the end could
* open up a subtle but easy to exploit DoS hole: someone could request
* a very large file with multiple requests. Better to detect this here
@@ -439,7 +417,12 @@
tmp_obj = (cache_object_t *) cache_find(sconf->cache_cache, key);
if (!tmp_obj) {
- cache_insert(sconf->cache_cache, obj);
+ cache_insert(sconf->cache_cache, obj);
+ /* Add a refcount to account for the reference by the
+ * hashtable in the cache. Refcount should be 2 now, one
+ * for this thread, and one for the cache.
+ */
+ apr_atomic_inc(&obj->refcount);
}
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
@@ -523,25 +506,33 @@
return OK;
}
+/* remove_entity()
+ * Notes:
+ * refcount should be at least 1 upon entry to this function to account
+ * for this thread's reference to the object. If the refcount is 1, then
+ * object has been removed from the cache by another thread and this thread
+ * is the last thread accessing the object.
+ */
static int remove_entity(cache_handle_t *h)
{
cache_object_t *obj = h->cache_obj;
+ cache_object_t *tobj = NULL;
- /* Remove the cache object from the cache under protection */
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- /* If the object is not already marked for cleanup, remove
- * it from the cache and mark it for cleanup. Remember,
- * an object marked for cleanup is by design not in the
- * hash table.
+
+ /* If the entity is still in the cache, remove it and decrement the
+ * refcount. If the entity is not in the cache, do nothing. In both cases
+ * decrement_refcount called by the last thread referencing the object will
+ * trigger the cleanup.
*/
- if (!obj->cleanup) {
+ tobj = cache_find(sconf->cache_cache, obj->key);
+ if (tobj == obj) {
cache_remove(sconf->cache_cache, obj);
- obj->cleanup = 1;
- ap_log_error(APLOG_MARK, APLOG_INFO, 0, NULL, "gcing a cache entry");
+ apr_atomic_dec(&obj->refcount);
}
-
+
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
}
@@ -607,45 +598,34 @@
return APR_SUCCESS;
}
/* Define request processing hook handlers */
+/* remove_url()
+ * Notes:
+ */
static int remove_url(const char *key)
{
cache_object_t *obj;
+ int cleanup = 0;
- /* Order of the operations is important to avoid race conditions.
- * First, remove the object from the cache. Remember, all additions
- * deletions from the cache are protected by sconf->lock.
- * Increment the ref count on the object to indicate our thread
- * is accessing the object. Then set the cleanup flag on the
- * object. Remember, the cleanup flag is NEVER set on an
- * object in the hash table. If an object has the cleanup
- * flag set, it is guaranteed to NOT be in the hash table.
- */
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
obj = cache_find(sconf->cache_cache, key);
if (obj) {
- mem_cache_object_t *mobj;
cache_remove(sconf->cache_cache, obj);
- mobj = (mem_cache_object_t *) obj->vobj;
-
- /* Refcount increment in this case MUST be made under
- * protection of the lock
- */
- apr_atomic_inc(&obj->refcount);
- if (obj) {
- obj->cleanup = 1;
+ if (!apr_atomic_dec(&obj->refcount)) {
+ /* For performance, cleanup cache object after releasing the lock */
+ cleanup = 1;
}
}
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
}
- if (obj) {
- if (!apr_atomic_dec(&obj->refcount)) {
- cleanup_cache_object(obj);
- }
+
+ if (cleanup) {
+ cleanup_cache_object(obj);
}
+
return OK;
}
@@ -808,6 +788,7 @@
{
apr_status_t rv;
cache_object_t *obj = h->cache_obj;
+ cache_object_t *tobj = NULL;
mem_cache_object_t *mobj = (mem_cache_object_t*) obj->vobj;
apr_read_type_e eblock = APR_BLOCK_READ;
apr_bucket *e;
@@ -908,28 +889,39 @@
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- if (obj->cleanup) {
- /* If obj->cleanup is set, the object has been prematurly
- * ejected from the cache by the garbage collector. Add the
- * object back to the cache. If an object with the same key is
- * found in the cache, eject it in favor of the completed obj.
+ /* Has the object been ejected from the cache?
+ */
+ tobj = (cache_object_t *) cache_find(sconf->cache_cache, obj->key);
+ if (tobj == obj) {
+ /* Object is still in the cache, remove it, update the len field
then
+ * replace it under protection of sconf->lock.
*/
- cache_object_t *tmp_obj =
- (cache_object_t *) cache_find(sconf->cache_cache, obj->key);
- if (tmp_obj) {
- cache_remove(sconf->cache_cache, tmp_obj);
- tmp_obj->cleanup = 1;
- if (!tmp_obj->refcount) {
- cleanup_cache_object(tmp_obj);
- }
- }
- obj->cleanup = 0;
- }
- else {
cache_remove(sconf->cache_cache, obj);
+ /* For illustration, cache no longer has reference to the object
+ * so decrement the refcount
+ * apr_atomic_dec(&obj->refcount);
+ */
+ mobj->m_len = obj->count;
+
+ cache_insert(sconf->cache_cache, obj);
+ /* For illustration, cache now has reference to the object, so
+ * increment the refcount
+ * apr_atomic_inc(&obj->refcount);
+ */
}
- mobj->m_len = obj->count;
- cache_insert(sconf->cache_cache, obj);
+ else if (tobj) {
+ /* Different object with the same key found in the cache. Doing
nothing
+ * here will cause the object refcount to drop to 0 in
decrement_refcount
+ * and the object will be cleaned up.
+ */
+
+ } else {
+ /* Object has been ejected from the cache, add it back to the
cache */
+ mobj->m_len = obj->count;
+ cache_insert(sconf->cache_cache, obj);
+ apr_atomic_inc(&obj->refcount);
+ }
+
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
}
? mod_cache.patch1
? mod_cache.patch2
? mod_mem_cache.patch
Index: mod_mem_cache.c
===================================================================
RCS file: /home/cvs/httpd-2.0/modules/experimental/mod_mem_cache.c,v
retrieving revision 1.88.2.9
diff -u -r1.88.2.9 mod_mem_cache.c
--- mod_mem_cache.c 26 Aug 2004 16:59:44 -0000 1.88.2.9
+++ mod_mem_cache.c 16 Sep 2004 03:48:02 -0000
@@ -13,6 +13,14 @@
* limitations under the License.
*/
+/*
+ * obj->refcount should only be incremented under protection of the sconf->lock
+ * obj->refcount can be atomically decremented w/o protection of the sconf->lock
+ * obj->refcount is incremented by one when the object is in the cache and once
+ * per thread referencing the object. An object in the cache with no threads
+ * accessing it will have a refcount of 1. When refcount drops to 0, the object
+ * should be garbage collected.
+ */
#define CORE_PRIVATE
#include "mod_cache.h"
#include "cache_pqueue.h"
@@ -142,24 +150,20 @@
return obj->key;
}
/**
- * callback to free an entry
- * There is way too much magic in this code. Right now, this callback
- * is only called out of cache_insert() which is called under protection
- * of the sconf->lock, which means that we do not (and should not)
- * attempt to obtain the lock recursively.
+ * memcache_cache_free()
+ * memcacache_cache_free is a callback that is only invoked during by a thread
+ * running in cache_insert(). cache_insert() runs under protection
+ * of sconf->lock. By the time this function has been entered, the cache_object
+ * has been ejected from the cache. decrement the refcount and if the refcount drop
+ * to 0, cleanup the cache object.
*/
static void memcache_cache_free(void*a)
{
cache_object_t *obj = (cache_object_t *)a;
- /* Cleanup the cache object. Object should be removed from the cache
- * now. Increment the refcount before setting cleanup to avoid a race
- * condition. A similar pattern is used in remove_url()
+ /* Decrement the refcount to account for the object being ejected
+ * from the cache. If the refcount is 0, free the object.
*/
- apr_atomic_inc(&obj->refcount);
-
- obj->cleanup = 1;
-
if (!apr_atomic_dec(&obj->refcount)) {
cleanup_cache_object(obj);
}
@@ -267,31 +271,9 @@
{
cache_object_t *obj = (cache_object_t *) arg;
- /* If obj->complete is not set, the cache update failed and the
- * object needs to be removed from the cache then cleaned up.
- */
- if (!obj->complete) {
- if (sconf->lock) {
- apr_thread_mutex_lock(sconf->lock);
- }
- /* Remember, objects marked for cleanup are, by design, already
- * removed from the cache. remove_url() could have already
- * removed the object from the cache (and set obj->cleanup)
- */
- if (!obj->cleanup) {
- cache_remove(sconf->cache_cache, obj);
- obj->cleanup = 1;
- }
- if (sconf->lock) {
- apr_thread_mutex_unlock(sconf->lock);
- }
- }
-
- /* Cleanup the cache object */
+ /* If the refcount drops to 0, cleanup the cache object */
if (!apr_atomic_dec(&obj->refcount)) {
- if (obj->cleanup) {
- cleanup_cache_object(obj);
- }
+ cleanup_cache_object(obj);
}
return APR_SUCCESS;
}
@@ -312,10 +294,7 @@
}
obj = cache_pop(co->cache_cache);
while (obj) {
- /* Iterate over the cache and clean up each entry */
- /* Free the object if the recount == 0 */
- apr_atomic_inc(&obj->refcount);
- obj->cleanup = 1;
+ /* Iterate over the cache and clean up each unreferenced entry */
if (!apr_atomic_dec(&obj->refcount)) {
cleanup_cache_object(obj);
}
@@ -415,7 +394,6 @@
apr_atomic_set(&obj->refcount, 1);
mobj->total_refs = 1;
obj->complete = 0;
- obj->cleanup = 0;
obj->vobj = mobj;
/* Safe cast: We tested < sconf->max_cache_object_size above */
mobj->m_len = (apr_size_t)len;
@@ -425,7 +403,7 @@
* Note: Perhaps we should wait to put the object in the
* hash table when the object is complete? I add the object here to
* avoid multiple threads attempting to cache the same content only
- * to discover at the very end that only one of them will suceed.
+ * to discover at the very end that only one of them will succeed.
* Furthermore, adding the cache object to the table at the end could
* open up a subtle but easy to exploit DoS hole: someone could request
* a very large file with multiple requests. Better to detect this here
@@ -439,7 +417,12 @@
tmp_obj = (cache_object_t *) cache_find(sconf->cache_cache, key);
if (!tmp_obj) {
- cache_insert(sconf->cache_cache, obj);
+ cache_insert(sconf->cache_cache, obj);
+ /* Add a refcount to account for the reference by the
+ * hashtable in the cache. Refcount should be 2 now, one
+ * for this thread, and one for the cache.
+ */
+ apr_atomic_inc(&obj->refcount);
}
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
@@ -523,25 +506,33 @@
return OK;
}
+/* remove_entity()
+ * Notes:
+ * refcount should be at least 1 upon entry to this function to account
+ * for this thread's reference to the object. If the refcount is 1, then
+ * object has been removed from the cache by another thread and this thread
+ * is the last thread accessing the object.
+ */
static int remove_entity(cache_handle_t *h)
{
cache_object_t *obj = h->cache_obj;
+ cache_object_t *tobj = NULL;
- /* Remove the cache object from the cache under protection */
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- /* If the object is not already marked for cleanup, remove
- * it from the cache and mark it for cleanup. Remember,
- * an object marked for cleanup is by design not in the
- * hash table.
+
+ /* If the entity is still in the cache, remove it and decrement the
+ * refcount. If the entity is not in the cache, do nothing. In both cases
+ * decrement_refcount called by the last thread referencing the object will
+ * trigger the cleanup.
*/
- if (!obj->cleanup) {
+ tobj = cache_find(sconf->cache_cache, obj->key);
+ if (tobj == obj) {
cache_remove(sconf->cache_cache, obj);
- obj->cleanup = 1;
- ap_log_error(APLOG_MARK, APLOG_INFO, 0, NULL, "gcing a cache entry");
+ apr_atomic_dec(&obj->refcount);
}
-
+
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
}
@@ -607,45 +598,34 @@
return APR_SUCCESS;
}
/* Define request processing hook handlers */
+/* remove_url()
+ * Notes:
+ */
static int remove_url(const char *key)
{
cache_object_t *obj;
+ int cleanup = 0;
- /* Order of the operations is important to avoid race conditions.
- * First, remove the object from the cache. Remember, all additions
- * deletions from the cache are protected by sconf->lock.
- * Increment the ref count on the object to indicate our thread
- * is accessing the object. Then set the cleanup flag on the
- * object. Remember, the cleanup flag is NEVER set on an
- * object in the hash table. If an object has the cleanup
- * flag set, it is guaranteed to NOT be in the hash table.
- */
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
obj = cache_find(sconf->cache_cache, key);
if (obj) {
- mem_cache_object_t *mobj;
cache_remove(sconf->cache_cache, obj);
- mobj = (mem_cache_object_t *) obj->vobj;
-
- /* Refcount increment in this case MUST be made under
- * protection of the lock
- */
- apr_atomic_inc(&obj->refcount);
- if (obj) {
- obj->cleanup = 1;
+ if (!apr_atomic_dec(&obj->refcount)) {
+ /* For performance, cleanup cache object after releasing the lock */
+ cleanup = 1;
}
}
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
}
- if (obj) {
- if (!apr_atomic_dec(&obj->refcount)) {
- cleanup_cache_object(obj);
- }
+
+ if (cleanup) {
+ cleanup_cache_object(obj);
}
+
return OK;
}
@@ -808,6 +788,7 @@
{
apr_status_t rv;
cache_object_t *obj = h->cache_obj;
+ cache_object_t *tobj = NULL;
mem_cache_object_t *mobj = (mem_cache_object_t*) obj->vobj;
apr_read_type_e eblock = APR_BLOCK_READ;
apr_bucket *e;
@@ -908,28 +889,39 @@
if (sconf->lock) {
apr_thread_mutex_lock(sconf->lock);
}
- if (obj->cleanup) {
- /* If obj->cleanup is set, the object has been prematurly
- * ejected from the cache by the garbage collector. Add the
- * object back to the cache. If an object with the same key is
- * found in the cache, eject it in favor of the completed obj.
+ /* Has the object been ejected from the cache?
+ */
+ tobj = (cache_object_t *) cache_find(sconf->cache_cache, obj->key);
+ if (tobj == obj) {
+ /* Object is still in the cache, remove it, update the len field then
+ * replace it under protection of sconf->lock.
*/
- cache_object_t *tmp_obj =
- (cache_object_t *) cache_find(sconf->cache_cache, obj->key);
- if (tmp_obj) {
- cache_remove(sconf->cache_cache, tmp_obj);
- tmp_obj->cleanup = 1;
- if (!tmp_obj->refcount) {
- cleanup_cache_object(tmp_obj);
- }
- }
- obj->cleanup = 0;
- }
- else {
cache_remove(sconf->cache_cache, obj);
+ /* For illustration, cache no longer has reference to the object
+ * so decrement the refcount
+ * apr_atomic_dec(&obj->refcount);
+ */
+ mobj->m_len = obj->count;
+
+ cache_insert(sconf->cache_cache, obj);
+ /* For illustration, cache now has reference to the object, so
+ * increment the refcount
+ * apr_atomic_inc(&obj->refcount);
+ */
}
- mobj->m_len = obj->count;
- cache_insert(sconf->cache_cache, obj);
+ else if (tobj) {
+ /* Different object with the same key found in the cache. Doing nothing
+ * here will cause the object refcount to drop to 0 in decrement_refcount
+ * and the object will be cleaned up.
+ */
+
+ } else {
+ /* Object has been ejected from the cache, add it back to the cache */
+ mobj->m_len = obj->count;
+ cache_insert(sconf->cache_cache, obj);
+ apr_atomic_inc(&obj->refcount);
+ }
+
if (sconf->lock) {
apr_thread_mutex_unlock(sconf->lock);
}
