From commits-return-10847-apmail-apr-commits-archive=apr.apache.org@apr.apache.org Tue Sep 22 20:08:35 2009 Return-Path: Delivered-To: apmail-apr-commits-archive@www.apache.org Received: (qmail 5431 invoked from network); 22 Sep 2009 20:08:35 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 22 Sep 2009 20:08:35 -0000 Received: (qmail 68904 invoked by uid 500); 22 Sep 2009 20:08:35 -0000 Delivered-To: apmail-apr-commits-archive@apr.apache.org Received: (qmail 68831 invoked by uid 500); 22 Sep 2009 20:08:34 -0000 Mailing-List: contact commits-help@apr.apache.org; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: Reply-To: dev@apr.apache.org List-Id: Delivered-To: mailing list commits@apr.apache.org Received: (qmail 68822 invoked by uid 99); 22 Sep 2009 20:08:34 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 22 Sep 2009 20:08:34 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 22 Sep 2009 20:08:23 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id C96AE2388873; Tue, 22 Sep 2009 20:08:03 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r817810 - in /apr/apr/branches/1.3.x: CHANGES include/apr_hash.h tables/apr_hash.c Date: Tue, 22 Sep 2009 20:07:57 -0000 To: commits@apr.apache.org From: minfrin@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20090922200803.C96AE2388873@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: minfrin Date: Tue Sep 22 20:07:53 2009 New Revision: 817810 URL: http://svn.apache.org/viewvc?rev=817810&view=rev Log: 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 Modified: apr/apr/branches/1.3.x/CHANGES apr/apr/branches/1.3.x/include/apr_hash.h apr/apr/branches/1.3.x/tables/apr_hash.c Modified: apr/apr/branches/1.3.x/CHANGES URL: http://svn.apache.org/viewvc/apr/apr/branches/1.3.x/CHANGES?rev=817810&r1=817809&r2=817810&view=diff ============================================================================== --- apr/apr/branches/1.3.x/CHANGES [utf-8] (original) +++ apr/apr/branches/1.3.x/CHANGES [utf-8] Tue Sep 22 20:07:53 2009 @@ -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 Modified: apr/apr/branches/1.3.x/include/apr_hash.h URL: http://svn.apache.org/viewvc/apr/apr/branches/1.3.x/include/apr_hash.h?rev=817810&r1=817809&r2=817810&view=diff ============================================================================== --- apr/apr/branches/1.3.x/include/apr_hash.h (original) +++ apr/apr/branches/1.3.x/include/apr_hash.h Tue Sep 22 20:07:53 2009 @@ -73,7 +73,7 @@ /** * 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 @@ * 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 @@ * 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 @@ * @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 @@ * 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, Modified: apr/apr/branches/1.3.x/tables/apr_hash.c URL: http://svn.apache.org/viewvc/apr/apr/branches/1.3.x/tables/apr_hash.c?rev=817810&r1=817809&r2=817810&view=diff ============================================================================== --- apr/apr/branches/1.3.x/tables/apr_hash.c (original) +++ apr/apr/branches/1.3.x/tables/apr_hash.c Tue Sep 22 20:07:53 2009 @@ -67,12 +67,15 @@ /* * 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 @@ 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 @@ 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 @@ } 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 @@ 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 @@ 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 @@ } #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;