From 0ade05af45a20e03acecad9436dcbeb75102a1f0 Mon Sep 17 00:00:00 2001 From: minfrin Date: Tue, 22 Sep 2009 20:07:53 +0000 Subject: 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 git-svn-id: http://svn.apache.org/repos/asf/apr/apr/branches/1.3.x@817810 13f79535-47bb-0310-9956-ffa450edef68 --- CHANGES | 6 +++++- include/apr_hash.h | 12 +++++++----- tables/apr_hash.c | 42 ++++++++++++++++++++++++++++++++++-------- 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 ] 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; -- cgit v1.2.1