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.


git-svn-id: https://svn.apache.org/repos/asf/apr/apr/trunk@65572 13f79535-47bb-0310-9956-ffa450edef68

2 files changed, 14 insertions, 1 deletions

diff --git a/CHANGES b/CHANGES
index 5c9112bfa..ea1f5cdcd 100644
--- a/CHANGES
+++ b/CHANGES
@@ -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]
 
diff --git a/tables/apr_hash.c b/tables/apr_hash.c
index 8b8a7f3d1..03bdfd7ce 100644
--- a/tables/apr_hash.c
+++ b/tables/apr_hash.c
@@ -73,6 +73,7 @@ struct apr_hash_t {
     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_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool)
     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 @@ static apr_hash_entry_t **find_entry(apr_hash_t *ht,
         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 @@ APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
                     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 @@ APR_DECLARE(void) apr_hash_set(apr_hash_t *ht,
     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 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
 
     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;