From thommay@apache.org  Sun Nov 14 02:33:08 2004
Return-Path: <thommay@apache.org>
Mailing-List: contact commits-help@apr.apache.org; run by ezmlm
Delivered-To: mailing list commits@apr.apache.org
Received: (qmail 36506 invoked by uid 99); 14 Nov 2004 02:33:08 -0000
X-ASF-Spam-Status: No, hits=-10.0 required=10.0
	tests=ALL_TRUSTED,NO_REAL_NAME
X-Spam-Check-By: apache.org
Received: from [209.237.227.194] (HELO minotaur.apache.org) (209.237.227.194)
  by apache.org (qpsmtpd/0.28) with SMTP; Sat, 13 Nov 2004 18:33:08 -0800
Received: (qmail 85445 invoked by uid 65534); 14 Nov 2004 02:33:07 -0000
Date: 14 Nov 2004 02:33:07 -0000
Message-ID: <20041114023307.85441.qmail@minotaur.apache.org>
From: thommay@apache.org
To: commits@apr.apache.org
Subject: svn commit: rev 65572 - in apr/apr/trunk: . tables
X-Virus-Checked: Checked

Author: thommay
Date: Sat Nov 13 18:33:07 2004
New Revision: 65572

Modified:
   apr/apr/trunk/CHANGES
   apr/apr/trunk/tables/apr_hash.c
Log:
Prevent unbounded memory use during repeated operations on a hash table.

The hash table was allocating new memory for each new insertion of an entry,
and not reclaiming it on deletions, so repetition of (insert, delete) caused
the memory use to keep growing.  This fix causes the memory freed by a deletion
to be reused by a subsequent insertion, so that the memory used by the hash
table is proportional to the maximum number of entries that it has ever held
simultaneously, rather than the number of insertions that have been performed.

* apr/tables/apr_hash.c:
  (apr_hash_t): Add new field "free", a free-list.
  (apr_hash_make, apr_hash_copy, apr_hash_merge): Initialise the free-list.
  (find_entry): Use an entry from the free-list if there is one.
  (apr_hash_set): Return a deleted entry to the free-list.


Modified: apr/apr/trunk/CHANGES
==============================================================================
--- apr/apr/trunk/CHANGES	(original)
+++ apr/apr/trunk/CHANGES	Sat Nov 13 18:33:07 2004
@@ -1,5 +1,8 @@
 Changes for APR 1.1 [Deferring these features when 1.0 is rolled out.]
 
+  *) Prevent unbounded memory use during repeated operations on a hash table.
+     [Julian Foad <julianfoad btopenworld.com>
+
   *) Moved repository to SVN
      [Hackathon]
 

Modified: apr/apr/trunk/tables/apr_hash.c
==============================================================================
--- apr/apr/trunk/tables/apr_hash.c	(original)
+++ apr/apr/trunk/tables/apr_hash.c	Sat Nov 13 18:33:07 2004
@@ -73,6 +73,7 @@
     apr_hash_index_t     iterator;  /* For apr_hash_first(NULL, ...) */
     unsigned int         count, max;
     apr_hashfunc_t       hash_func;
+    apr_hash_entry_t    *free;  /* List of recycled entries */
 };
 
 #define INITIAL_MAX 15 /* tunable == 2^n - 1 */
@@ -92,6 +93,7 @@
     apr_hash_t *ht;
     ht = apr_palloc(pool, sizeof(apr_hash_t));
     ht->pool = pool;
+    ht->free = NULL;
     ht->count = 0;
     ht->max = INITIAL_MAX;
     ht->array = alloc_array(ht, ht->max);
@@ -264,7 +266,10 @@
         return hep;
 
     /* add a new entry for non-NULL values */
-    he = apr_palloc(ht->pool, sizeof(*he));
+    if (he = ht->free)
+        ht->free = he->next;
+    else
+        he = apr_palloc(ht->pool, sizeof(*he));
     he->next = NULL;
     he->hash = hash;
     he->key  = key;
@@ -286,6 +291,7 @@
                     sizeof(*ht->array) * (orig->max + 1) +
                     sizeof(apr_hash_entry_t) * orig->count);
     ht->pool = pool;
+    ht->free = NULL;
     ht->count = orig->count;
     ht->max = orig->max;
     ht->hash_func = orig->hash_func;
@@ -333,7 +339,10 @@
     if (*hep) {
         if (!val) {
             /* delete entry */
+            apr_hash_entry_t *old = *hep;
             *hep = (*hep)->next;
+            old->next = ht->free;
+            ht->free = old;
             --ht->count;
         }
         else {
@@ -396,6 +405,7 @@
 
     res = apr_palloc(p, sizeof(apr_hash_t));
     res->pool = p;
+    res->free = NULL;
     res->hash_func = base->hash_func;
     res->count = base->count;
     res->max = (overlay->max > base->max) ? overlay->max : base->max;