apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ben Collins-Sussman <suss...@collab.net>
Subject [PATCH] Pools space-time tradeoff
Date Wed, 22 May 2002 17:15:42 GMT

[crossposted to APR and SVN dev lists.]

Hi, all.  I've been working with Sander to resolve some pool problems.

** Here's the problem:

We have two use-cases in Subversion now that literally run out of
memory; the application footprint grows without bound until the OS
kills things.  Here they are:

  1.  'svn checkout file:///repository -r HEAD'
  2.  'svnadmin dump repository > dumpfile'

These use-cases, it turns out, are nearly identical.  They both simply
walk over a repository tree and push data at a vtable, which in turn
writes the data to disk (either as a working copy, or as a dumpfile).
The pools are controlled by our filesystem-walker, and we're being
*extremely* careful about controlling pool lifetimes and clearing subpools
in loops.  (Gstein has pounded these concepts into our heads.  :-))

  [Note: 'svn checkout http://...' works fine, because svn is doing an
   independent GET request for each file... which means a separate
   pool created and destroyed by httpd for each item.]

It turns out that the real issue here is that our current pool
implementation always grows forever, until the entire pool hierarchy
is destroyed when the main() process exits.  I believe that when Mike
Pilato stat'ed our pools, we were actually only using a few
megs... but we were still creating a memory footprint of 200M+ !


** Here's the solution:

Sander whipped out two of his pool patches that have been previously
ignored up till now.  He combined them into a single patch.  Here's
what they do:

  1.  Keep each pool's list of 'old' active blocks sorted by size.  If
      a request comes in that won't fit in the current active block,
      then try to alloc the request in the largest 'old' active block
      (instead of alloc'ing a completely new active block).
      Effectively, we get some memory re-use now.

  2.  When a pool is destroyed or cleared, normally all of its
      inactive blocks are given back to a 'global free list' in the
      pool hierarchy.  We now have a threshold size that can be set:
      if the global-free-list ever grows larger than the threshold,
      then the 'extra' inactive blocks are actually free()d.  We've
      set the maximum free-list size at 4M for now.

Anyway, I've included the patches below for people to look at.
Apparently Sander posted these before, but nobody had a reason to
care.  Well, now Subversion *really* needs these features.

I've tested this patch on our two use cases: the memory footprint for
'svn checkout' bounces up and down, but eventually plateaus around
25M.  The footprint for 'svnadmin dump' also bounces around, but
plateaus around 17M.  A huge difference! 

Sander is worried about possible pool-performance hits from these
changes, so he's hoping folks might be able to do some timing stats.
(Personally, via my sophisticated use of the unix 'time' command, I
find no noticeable difference.)

The patch affects two APR files (apr_allocator.h, apr_pools.c), and
one svn file (svn_error.c)... assuming svn users want to take
advantage of the new pool features.  I've posted the patch below.

Assuming nobody objects, Sander plans to apply these changes in a day
or two.  We just want to give people time to look them over.


Index: include/apr_allocator.h
===================================================================
RCS file: /home/cvs/apr/include/apr_allocator.h,v
retrieving revision 1.4
diff -u -r1.4 apr_allocator.h
--- include/apr_allocator.h	9 Apr 2002 06:56:55 -0000	1.4
+++ include/apr_allocator.h	22 May 2002 16:11:50 -0000
@@ -83,7 +83,9 @@
 
 struct apr_memnode_t {
     apr_memnode_t *next;
+    apr_memnode_t **ref;
     apr_uint32_t   index;
+    apr_uint32_t   free_index;
     char          *first_avail;
     char          *endp;
 };
@@ -150,6 +152,16 @@
  * @param allocator The allocator to get the owner from
  */
 APR_DECLARE(apr_pool_t *) apr_allocator_get_owner(apr_allocator_t *allocator);
+
+
+/**
+ * Set the current threshold at which the allocator should start
+ * giving blocks back to the system.
+ * @param allocator The allocator the set the threshold on
+ * @param size The threshold.  0 == unlimited.
+ */
+APR_DECLARE(void) apr_allocator_set_max_free(apr_allocator_t *allocator,
+                                             apr_size_t size);
 
 #include "apr_thread_mutex.h"
 
Index: memory/unix/apr_pools.c
===================================================================
RCS file: /home/cvs/apr/memory/unix/apr_pools.c,v
retrieving revision 1.167
diff -u -r1.167 apr_pools.c
--- memory/unix/apr_pools.c	5 May 2002 22:24:41 -0000	1.167
+++ memory/unix/apr_pools.c	22 May 2002 16:11:55 -0000
@@ -93,6 +93,8 @@
 
 struct apr_allocator_t {
     apr_uint32_t        max_index;
+    apr_uint32_t        max_free_index;
+    apr_uint32_t        current_free_index;
 #if APR_HAS_THREADS
     apr_thread_mutex_t *mutex;
 #endif /* APR_HAS_THREADS */
@@ -166,6 +168,32 @@
     return allocator->owner;
 }
 
+APR_DECLARE(void) apr_allocator_set_max_free(apr_allocator_t *allocator,
+                                             apr_size_t size)
+{
+    apr_uint32_t max_free_index;
+
+#if APR_HAS_THREADS
+    apr_thread_mutex_t *mutex;
+
+    mutex = apr_allocator_get_mutex(allocator);
+    if (mutex != NULL)
+        apr_thread_mutex_lock(mutex);
+#endif /* APR_HAS_THREADS */
+
+    max_free_index = APR_ALIGN(size, BOUNDARY_SIZE) >> BOUNDARY_INDEX;
+    allocator->current_free_index += max_free_index;
+    allocator->current_free_index -= allocator->max_free_index;
+    allocator->max_free_index = max_free_index;
+    if (allocator->current_free_index > max_free_index)
+        allocator->current_free_index = max_free_index;
+
+#if APR_HAS_THREADS
+    if (mutex != NULL)
+        apr_thread_mutex_unlock(mutex);
+#endif
+}
+
 APR_INLINE
 APR_DECLARE(apr_memnode_t *) apr_allocator_alloc(apr_allocator_t *allocator,
                                                  apr_size_t size)
@@ -228,6 +256,10 @@
                 allocator->max_index = max_index;
             }
 
+            allocator->current_free_index += node->index;
+            if (allocator->current_free_index > allocator->max_free_index)
+                allocator->current_free_index = allocator->max_free_index;
+
 #if APR_HAS_THREADS
             if (allocator->mutex)
                 apr_thread_mutex_unlock(allocator->mutex);
@@ -264,6 +296,10 @@
         if (node) {
             *ref = node->next;
 
+            allocator->current_free_index += node->index;
+            if (allocator->current_free_index > allocator->max_free_index)
+                allocator->current_free_index = allocator->max_free_index;
+
 #if APR_HAS_THREADS
             if (allocator->mutex)
                 apr_thread_mutex_unlock(allocator->mutex);
@@ -299,8 +335,9 @@
 APR_DECLARE(void) apr_allocator_free(apr_allocator_t *allocator,
                                      apr_memnode_t *node)
 {
-    apr_memnode_t *next;
+    apr_memnode_t *next, *freelist = NULL;
     apr_uint32_t index, max_index;
+    apr_uint32_t max_free_index, current_free_index;
 
 #if APR_HAS_THREADS
     if (allocator->mutex)
@@ -308,6 +345,8 @@
 #endif /* APR_HAS_THREADS */
 
     max_index = allocator->max_index;
+    max_free_index = allocator->max_free_index;
+    current_free_index = allocator->current_free_index;
 
     /* Walk the list of submitted nodes and free them one by one,
      * shoving them in the right 'size' buckets as we go.
@@ -316,7 +355,11 @@
         next = node->next;
         index = node->index;
 
-        if (index < MAX_INDEX) {
+        if (max_free_index != 0 && index > current_free_index) {
+            node->next = freelist;
+            freelist = node;
+        }
+        else if (index < MAX_INDEX) {
             /* Add the node to the appropiate 'size' bucket.  Adjust
              * the max_index when appropiate.
              */
@@ -325,6 +368,7 @@
                 max_index = index;
             }
             allocator->free[index] = node;
+            current_free_index -= index;
         }
         else {
             /* This node is too large to keep in a specific size bucket,
@@ -332,15 +376,23 @@
              */
             node->next = allocator->free[0];
             allocator->free[0] = node;
+            current_free_index -= index;
         }
     } while ((node = next) != NULL);
 
     allocator->max_index = max_index;
+    allocator->current_free_index = current_free_index;
 
 #if APR_HAS_THREADS
     if (allocator->mutex)
         apr_thread_mutex_unlock(allocator->mutex);
 #endif /* APR_HAS_THREADS */
+
+    while (freelist != NULL) {
+        node = freelist;
+        freelist = node->next;
+        free(node);
+    }
 }
 
 
@@ -544,6 +596,7 @@
     apr_memnode_t *active, *node;
     void *mem;
     char *endp;
+    apr_uint32_t free_index;
 
     size = APR_ALIGN_DEFAULT(size);
     active = pool->active;
@@ -557,17 +610,52 @@
         return mem;
     }
 
-    if ((node = apr_allocator_alloc(pool->allocator, size)) == NULL) {
-        if (pool->abort_fn)
-            pool->abort_fn(APR_ENOMEM);
-
-        return NULL;
+    node = active->next;
+    endp = node->first_avail + size;
+    if (endp < node->endp) {
+        *node->ref = node->next;
+        node->next->ref = node->ref;
+    }
+    else {
+        if ((node = apr_allocator_alloc(pool->allocator, size)) == NULL) {
+            if (pool->abort_fn)
+                pool->abort_fn(APR_ENOMEM);
+        }
+        endp = node->first_avail + size;
     }
 
-    active->next = pool->active = node;
+    node->free_index = 0;
 
     mem = node->first_avail;
-    node->first_avail += size;
+    node->first_avail = endp;
+
+    node->ref = active->ref;
+    *node->ref = node;
+    node->next = active;
+    active->ref = &node->next;
+
+    pool->active = node;
+
+    free_index = (APR_ALIGN(active->endp - active->first_avail + 1,
+                            BOUNDARY_SIZE) - BOUNDARY_SIZE) >> BOUNDARY_INDEX;
+
+    active->free_index = free_index;
+    node = active->next;
+    if (free_index >= node->free_index)
+        return mem;
+
+    do {
+        node = node->next;
+    }
+    while (free_index < node->free_index);
+
+    *active->ref = active->next;
+    active->next->ref = active->ref;
+
+    active->ref = node->ref;
+    *active->ref = active;
+    active->next = node;
+    node->ref = &active->next;
 
     return mem;
 }
@@ -625,11 +713,13 @@
     active = pool->active = pool->self;
     active->first_avail = pool->self_first_avail;
 
-    if (active->next == NULL)
+    if (active->next == active)
         return;
 
+    *active->ref = NULL;
     apr_allocator_free(pool->allocator, active->next);
-    active->next = NULL;
+    active->next = active;
+    active->ref = &active->next;
 }
 
 APR_DECLARE(void) apr_pool_destroy(apr_pool_t *pool)
@@ -672,6 +762,7 @@
      */
     allocator = pool->allocator;
     active = pool->self;
+    *active->ref = NULL;
 
 #if APR_HAS_THREADS
     if (apr_allocator_get_owner(allocator) == pool) {
@@ -724,6 +815,9 @@
         return APR_ENOMEM;
     }
 
+    node->next = node;
+    node->ref = &node->next;
+
     pool = (apr_pool_t *)node->first_avail;
     node->first_avail = pool->self_first_avail = (char *)pool + SIZEOF_POOL_T;
 
@@ -791,7 +885,7 @@
 struct psprintf_data {
     apr_vformatter_buff_t vbuff;
     apr_memnode_t   *node;
-    apr_allocator_t *allocator;
+    apr_pool_t      *pool;
     apr_byte_t       got_a_new_node;
     apr_memnode_t   *free;
 };
@@ -800,29 +894,70 @@
 {
     struct psprintf_data *ps = (struct psprintf_data *)vbuff;
     apr_memnode_t *node, *active;
-    apr_size_t cur_len;
+    apr_size_t cur_len, size;
     char *strp;
-    apr_allocator_t *allocator;
+    apr_pool_t *pool;
+    apr_uint32_t free_index;
 
-    allocator = ps->allocator;
-    node = ps->node;
+    pool = ps->pool;
+    active = ps->node;
     strp = ps->vbuff.curpos;
-    cur_len = strp - node->first_avail;
+    cur_len = strp - active->first_avail;
+    size = cur_len << 1;
 
-    if ((active = apr_allocator_alloc(allocator, cur_len << 1)) == NULL)
-        return -1;
+    node = active->next;
+    if (!ps->got_a_new_node && node->first_avail + size < node->endp)
{
+        *node->ref = node->next;
+        node->next->ref = node->ref;
+
+        node->ref = active->ref;
+        *node->ref = node;
+        node->next = active;
+        active->ref = &node->next;
+
+        node->free_index = 0;
+
+        pool->active = node;
+
+        free_index = (APR_ALIGN(active->endp - active->first_avail + 1,
+                                BOUNDARY_SIZE) - BOUNDARY_SIZE) >> BOUNDARY_INDEX;
+
+        active->free_index = free_index;
+        node = active->next;
+        if (free_index < node->free_index) {
+            do {
+                node = node->next;
+            }
+            while (free_index < node->free_index);
+
+            *active->ref = active->next;
+            active->next->ref = active->ref;
 
-    memcpy(active->first_avail, node->first_avail, cur_len);
+            active->ref = node->ref;
+            *active->ref = active;
+            active->next = node;
+            node->ref = &active->next;
+        }
+ 
+        node = pool->active;
+    }
+    else {
+        if ((node = apr_allocator_alloc (pool->allocator, size)) == NULL)
+            return -1;
+
+        if (ps->got_a_new_node) {
+            active->next = ps->free;
+            ps->free = node; 
+        }
 
-    if (ps->got_a_new_node) {
-        node->next = ps->free;
-        ps->free = node;
+        ps->got_a_new_node = 1;
     }
 
-    ps->node = active;
-    ps->vbuff.curpos = active->first_avail + cur_len;
-    ps->vbuff.endpos = active->endp - 1; /* Save a byte for NUL terminator */
-    ps->got_a_new_node = 1;
+    memcpy(node->first_avail, active->first_avail, cur_len);
+
+    ps->node = node;
+    ps->vbuff.curpos = node->first_avail + cur_len;
+    ps->vbuff.endpos = node->endp - 1; /* Save a byte for NUL terminator */
 
     return 0;
 }
@@ -832,10 +967,11 @@
     struct psprintf_data ps;
     char *strp;
     apr_size_t size;
-    apr_memnode_t *active;
+    apr_memnode_t *active, *node;
+    apr_uint32_t free_index;
 
     ps.node = active = pool->active;
-    ps.allocator = pool->allocator;
+    ps.pool = pool;
     ps.vbuff.curpos  = ps.node->first_avail;
 
     /* Save a byte for the NUL terminator */
@@ -858,15 +994,48 @@
     strp = ps.node->first_avail;
     ps.node->first_avail += size;
 
+   if (ps.free)
+        apr_allocator_free(pool->allocator, ps.free);
+
     /*
      * Link the node in if it's a new one
      */
-    if (ps.got_a_new_node) {
-        active->next = pool->active = ps.node;
+    if (!ps.got_a_new_node)
+        return strp;
+
+    active = pool->active;
+    node = ps.node;
+
+    node->free_index = 0;
+
+    node->ref = active->ref;
+    *node->ref = node;
+    node->next = active;
+    active->ref = &node->next;
+
+    pool->active = node;
+
+    free_index = (APR_ALIGN(active->endp - active->first_avail + 1,
+                            BOUNDARY_SIZE) - BOUNDARY_SIZE) >> BOUNDARY_INDEX;
+
+    active->free_index = free_index;
+    node = active->next;
+
+    if (free_index >= node->free_index)
+        return strp;
+
+    do {
+        node = node->next;
     }
+    while (free_index < node->free_index);
+
+    *active->ref = active->next;
+    active->next->ref = active->ref;
 
-    if (ps.free)
-        apr_allocator_free(ps.allocator, ps.free);
+    active->ref = node->ref;
+    *active->ref = active;
+    active->next = node;
+    node->ref = &active->next;
 
     return strp;
 }


Index: ./subversion/libsvn_subr/svn_error.c
===================================================================
--- ./subversion/libsvn_subr/svn_error.c
+++ ./subversion/libsvn_subr/svn_error.c	Wed May 22 10:39:46 2002
@@ -25,6 +25,7 @@
 #include "apr_pools.h"
 #include "apr_strings.h"
 #include "apr_hash.h"
+#include "apr_allocator.h"
 
 #include "svn_pools.h"
 #include "svn_error.h"
@@ -423,18 +424,46 @@
 SVN_POOL_FUNC_DEFINE(apr_pool_t *, svn_pool_create)
 {
   apr_pool_t *ret_pool;
+  apr_allocator_t *allocator = NULL;
+  apr_status_t apr_err;
+
+  /* For the top level pool we want a seperate allocator */
+  if (pool == NULL)
+    {
+      apr_err = apr_allocator_create (&allocator);
+      if (apr_err)
+        abort_on_pool_failure (apr_err);
+
+      /* Use magic number for testing, 2MB */
+      apr_allocator_set_max_free (allocator, 4096 * 1024);
+    }
 
 #if !APR_POOL_DEBUG
-  apr_pool_create_ex (&ret_pool, pool, abort_on_pool_failure, NULL);
+  apr_pool_create_ex (&ret_pool, pool, abort_on_pool_failure, allocator);
 #else /* APR_POOL_DEBUG */
   apr_pool_create_ex_debug (&ret_pool, pool, abort_on_pool_failure,
-                            NULL, file_line);
+                            allocator, file_line);
 #endif /* APR_POOL_DEBUG */
 
   /* If there is no parent, then initialize ret_pool as the "top". */
   if (pool == NULL)
     {
-      apr_status_t apr_err = svn_error_init_pool (ret_pool);
+#if APR_HAS_THREADS
+      {
+        apr_thread_mutex_t *mutex;
+
+        apr_err = apr_thread_mutex_create (&mutex, APR_THREAD_MUTEX_DEFAULT,
+                                           ret_pool);
+        if (apr_err)
+          abort_on_pool_failure (apr_err);
+
+        apr_allocator_set_mutex (allocator, mutex);
+      }
+#endif /* APR_HAS_THREADS */
+
+      apr_allocator_set_owner (allocator, ret_pool);
+     
+      apr_err = svn_error_init_pool (ret_pool);
       if (apr_err)
         abort_on_pool_failure (apr_err);
     }

Mime
View raw message