The implementation of expand_array() in tables/apr_hash.c allocatesi

a new bucket array, without making any attempt to release the memory      
allocated for the previous bucket array. That wastes memory: if the
hash table grows exponentially, this strategy wastes O(n) extra memory.
Use a subpool instead.
Submitted by: Neil Conway <nrc cs.berkeley.edu>


git-svn-id: http://svn.apache.org/repos/asf/apr/apr/branches/1.3.x@817810 13f79535-47bb-0310-9956-ffa450edef68

3 files changed, 46 insertions, 14 deletions

diff --git a/CHANGES b/CHANGES
index 142ac4c27..8eda04dc5 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,7 +1,11 @@
                                                      -*- coding: utf-8 -*-
 Changes for APR 1.3.10
 
-
+  *) The implementation of expand_array() in tables/apr_hash.c allocates
+     a new bucket array, without making any attempt to release the memory
+     allocated for the previous bucket array. That wastes memory: if the
+     hash table grows exponentially, this strategy wastes O(n) extra memory.
+     Use a subpool instead. [Neil Conway <nrc cs.berkeley.edu>]
 
 Changes for APR 1.3.9
 
diff --git a/include/apr_hash.h b/include/apr_hash.h
index c033ed15a..cfd347e51 100644
--- a/include/apr_hash.h
+++ b/include/apr_hash.h
@@ -73,7 +73,7 @@ APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *key,
 /**
  * Create a hash table.
  * @param pool The pool to allocate the hash table out of
- * @return The hash table just created
+ * @return The hash table just created, or NULL if memory allocation failed
   */
 APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool);
 
@@ -81,7 +81,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool);
  * Create a hash table with a custom hash function
  * @param pool The pool to allocate the hash table out of
  * @param hash_func A custom hash function.
- * @return The hash table just created
+ * @return The hash table just created, or NULL if memory allocation failed
   */
 APR_DECLARE(apr_hash_t *) apr_hash_make_custom(apr_pool_t *pool, 
                                                apr_hashfunc_t hash_func);
@@ -90,7 +90,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_make_custom(apr_pool_t *pool,
  * Make a copy of a hash table
  * @param pool The pool from which to allocate the new hash table
  * @param h The hash table to clone
- * @return The hash table just created
+ * @return The hash table just created, or NULL if memory allocation failed
  * @remark Makes a shallow copy
  */
 APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
@@ -187,7 +187,8 @@ APR_DECLARE(void) apr_hash_clear(apr_hash_t *ht);
  * @param p The pool to use for the new hash table
  * @param overlay The table to add to the initial table
  * @param base The table that represents the initial values of the new table
- * @return A new hash table containing all of the data from the two passed in
+ * @return A new hash table containing all of the data from the two passed in,
+ *         or NULL if memory allocation failed
  */
 APR_DECLARE(apr_hash_t *) apr_hash_overlay(apr_pool_t *p,
                                            const apr_hash_t *overlay, 
@@ -205,7 +206,8 @@ APR_DECLARE(apr_hash_t *) apr_hash_overlay(apr_pool_t *p,
  *  make values from h1 override values from h2 (same semantics as
  *  apr_hash_overlay())
  * @param data Client data to pass to the merger function
- * @return A new hash table containing all of the data from the two passed in
+ * @return A new hash table containing all of the data from the two passed in,
+ *         or NULL if memory allocation failed.
  */
 APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
                                          const apr_hash_t *h1,
diff --git a/tables/apr_hash.c b/tables/apr_hash.c
index 4e3723e19..e6e801f4b 100644
--- a/tables/apr_hash.c
+++ b/tables/apr_hash.c
@@ -67,12 +67,15 @@ struct apr_hash_index_t {
 /*
  * The size of the array is always a power of two. We use the maximum
  * index rather than the size so that we can use bitwise-AND for
- * modular arithmetic.
- * The count of hash entries may be greater depending on the chosen
- * collision rate.
+ * modular arithmetic. The count of hash entries may be greater
+ * depending on the chosen collision rate.
+ *
+ * We allocate the bucket array in a sub-pool, "array_pool". This allows us
+ * to reclaim the old bucket array after an expansion.
  */
 struct apr_hash_t {
     apr_pool_t          *pool;
+    apr_pool_t          *array_pool;
     apr_hash_entry_t   **array;
     apr_hash_index_t     iterator;  /* For apr_hash_first(NULL, ...) */
     unsigned int         count, max;
@@ -89,14 +92,20 @@ struct apr_hash_t {
 
 static apr_hash_entry_t **alloc_array(apr_hash_t *ht, unsigned int max)
 {
-   return apr_pcalloc(ht->pool, sizeof(*ht->array) * (max + 1));
+   return apr_pcalloc(ht->array_pool, sizeof(*ht->array) * (max + 1));
 }
 
 APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool)
 {
+    apr_pool_t *array_pool;
     apr_hash_t *ht;
+
+    if (apr_pool_create(&array_pool, pool) != APR_SUCCESS)
+        return NULL;
+
     ht = apr_palloc(pool, sizeof(apr_hash_t));
     ht->pool = pool;
+    ht->array_pool = array_pool;
     ht->free = NULL;
     ht->count = 0;
     ht->max = INITIAL_MAX;
@@ -163,10 +172,17 @@ APR_DECLARE(void) apr_hash_this(apr_hash_index_t *hi,
 
 static void expand_array(apr_hash_t *ht)
 {
+    apr_pool_t *new_array_pool;
+    apr_pool_t *old_array_pool;
     apr_hash_index_t *hi;
     apr_hash_entry_t **new_array;
     unsigned int new_max;
 
+    if (apr_pool_create(&new_array_pool, ht->pool) != APR_SUCCESS)
+        return; /* Give up and don't try to expand the array */
+    old_array_pool = ht->array_pool;
+    ht->array_pool = new_array_pool;
+
     new_max = ht->max * 2 + 1;
     new_array = alloc_array(ht, new_max);
     for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {
@@ -176,6 +192,8 @@ static void expand_array(apr_hash_t *ht)
     }
     ht->array = new_array;
     ht->max = new_max;
+
+    apr_pool_destroy(old_array_pool);
 }
 
 APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key,
@@ -288,22 +306,25 @@ static apr_hash_entry_t **find_entry(apr_hash_t *ht,
 APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
                                         const apr_hash_t *orig)
 {
+    apr_pool_t *array_pool;
     apr_hash_t *ht;
     apr_hash_entry_t *new_vals;
     unsigned int i, j;
 
+    if (apr_pool_create(&array_pool, ht->pool) != APR_SUCCESS)
+        return NULL;
+
     ht = apr_palloc(pool, sizeof(apr_hash_t) +
-                    sizeof(*ht->array) * (orig->max + 1) +
                     sizeof(apr_hash_entry_t) * orig->count);
     ht->pool = pool;
+    ht->array_pool = array_pool;
     ht->free = NULL;
     ht->count = orig->count;
     ht->max = orig->max;
     ht->hash_func = orig->hash_func;
-    ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
+    ht->array = alloc_array(ht, ht->max);
 
-    new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) +
-                                    sizeof(*ht->array) * (orig->max + 1));
+    new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t));
     j = 0;
     for (i = 0; i <= ht->max; i++) {
         apr_hash_entry_t **new_entry = &(ht->array[i]);
@@ -392,6 +413,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
                                                      const void *data),
                                          const void *data)
 {
+    apr_pool_t *array_pool;
     apr_hash_t *res;
     apr_hash_entry_t *new_vals = NULL;
     apr_hash_entry_t *iter;
@@ -415,8 +437,12 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
     }
 #endif
 
+    if (apr_pool_create(&array_pool, p) != APR_SUCCESS)
+        return NULL;
+
     res = apr_palloc(p, sizeof(apr_hash_t));
     res->pool = p;
+    res->array_pool = array_pool;
     res->free = NULL;
     res->hash_func = base->hash_func;
     res->count = base->count;