You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@apr.apache.org by mi...@apache.org on 2009/09/22 22:06:18 UTC
svn commit: r817809 - in /apr/apr/branches/1.4.x: CHANGES include/apr_hash.h
tables/apr_hash.c
Author: minfrin
Date: Tue Sep 22 20:06:14 2009
New Revision: 817809
URL: http://svn.apache.org/viewvc?rev=817809&view=rev
Log:
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.
Submitted by: Neil Conway <nrc cs.berkeley.edu>
Modified:
apr/apr/branches/1.4.x/CHANGES
apr/apr/branches/1.4.x/include/apr_hash.h
apr/apr/branches/1.4.x/tables/apr_hash.c
Modified: apr/apr/branches/1.4.x/CHANGES
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.4.x/CHANGES?rev=817809&r1=817808&r2=817809&view=diff
==============================================================================
--- apr/apr/branches/1.4.x/CHANGES [utf-8] (original)
+++ apr/apr/branches/1.4.x/CHANGES [utf-8] Tue Sep 22 20:06:14 2009
@@ -5,6 +5,12 @@
Fix overflow in pools and rmm, where size alignment was taking place.
[Matt Lewis <ma...@google.com>, Sander Striker]
+ *) 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>]
+
*) Posix semaphores can now be named and used as named semaphores.
[Jim Jagielski]
Modified: apr/apr/branches/1.4.x/include/apr_hash.h
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.4.x/include/apr_hash.h?rev=817809&r1=817808&r2=817809&view=diff
==============================================================================
--- apr/apr/branches/1.4.x/include/apr_hash.h (original)
+++ apr/apr/branches/1.4.x/include/apr_hash.h Tue Sep 22 20:06:14 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.4.x/tables/apr_hash.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.4.x/tables/apr_hash.c?rev=817809&r1=817808&r2=817809&view=diff
==============================================================================
--- apr/apr/branches/1.4.x/tables/apr_hash.c (original)
+++ apr/apr/branches/1.4.x/tables/apr_hash.c Tue Sep 22 20:06:14 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;
Re: svn commit: r817809 - in /apr/apr/branches/1.4.x: CHANGES include/apr_hash.h tables/apr_hash.c
Posted by Philip Martin <ph...@codematters.co.uk>.
Bojan Smojver <bo...@rexursive.com> writes:
> On Mon, 2012-01-30 at 10:22 +0000, Philip Martin wrote:
>> It was reverted because it means the hash table data is not available
>> in pool cleanup handlers
>
> I guess it should then be reverted on the 1.5.x branch as well.
Yes, I believe so.
--
Philip
Re: svn commit: r817809 - in /apr/apr/branches/1.4.x: CHANGES
include/apr_hash.h tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Mon, 2012-01-30 at 10:22 +0000, Philip Martin wrote:
> It was reverted because it means the hash table data is not available
> in pool cleanup handlers
I guess it should then be reverted on the 1.5.x branch as well.
--
Bojan
Re: svn commit: r817809 - in /apr/apr/branches/1.4.x: CHANGES include/apr_hash.h tables/apr_hash.c
Posted by Philip Martin <ph...@codematters.co.uk>.
Bojan Smojver <bo...@rexursive.com> writes:
> On Tue, 2009-09-22 at 20:06 +0000, minfrin@apache.org wrote:
>> URL: http://svn.apache.org/viewvc?rev=817809&view=rev
>> Log:
>> 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.
>> Submitted by: Neil Conway <nrc cs.berkeley.edu>
>
> Somehow this commit never made it into trunk. It only exists in what is
> now 1.5.x. Anyone knows why?
It was reverted because it means the hash table data is not available in
pool cleanup handlers:
http://mail-archives.apache.org/mod_mbox/apr-dev/201001.mbox/%3C004001ca8fab$c7089b10$5519d130$@qqmail.nl%3E
--
Philip
Re: svn commit: r817809 - in /apr/apr/branches/1.4.x: CHANGES
include/apr_hash.h tables/apr_hash.c
Posted by Bojan Smojver <bo...@rexursive.com>.
On Tue, 2009-09-22 at 20:06 +0000, minfrin@apache.org wrote:
> URL: http://svn.apache.org/viewvc?rev=817809&view=rev
> Log:
> 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.
> Submitted by: Neil Conway <nrc cs.berkeley.edu>
Somehow this commit never made it into trunk. It only exists in what is
now 1.5.x. Anyone knows why?
--
Bojan