r14061@tombo: nickm | 2008-02-08 14:30:42 -0500

 Add a couple of (currently disabled) strategies for trying to avoid using too much ram in memory pools: prefer putting new cells in almost-full chunks, and be willing to free the last empty chunk if we have not needed it for a while.  Also add better output to mp_pool_log_status to track how many mallocs a given memory pool strategy is saving us, so we can tune the mempool parameters.


svn:r13428

5 files changed, 130 insertions, 29 deletions

diff --git a/ChangeLog b/ChangeLog
index 9db8a9a231..92c86b4ed6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -12,6 +12,8 @@ Changes in version 0.2.0.19-alpha - 2008-02-??
       bandwidthburst values.
     - Give more descriptive well-formedness errors for out-of-range
       hidden service descriptor/protocol versions.
+    - Make memory debugging output describe more about history of cell
+      allocation.
 
   o Minor features (security):
     - Be slightly more paranoid about overwriting sensitive memory on free,
diff --git a/src/common/mempool.c b/src/common/mempool.c
index 5ec4eaea1c..43f10c1e44 100644
--- a/src/common/mempool.c
+++ b/src/common/mempool.c
@@ -8,10 +8,12 @@
 
 #include <stdlib.h>
 #include <string.h>
-
+#include "torint.h"
 #define MEMPOOL_PRIVATE
 #include "mempool.h"
 
+//#define LAZY_CHUNK_SORT
+
 /* OVERVIEW:
  *
  *     This is an implementation of memory pools for Tor cells.  It may be
@@ -59,7 +61,6 @@
  *     if you need doubles.
  *   - Could probably be optimized a bit; the representation contains
  *     a bit more info than it really needs to have.
- *   - probably, chunks should always be a power of 2.
  */
 
 #if 1
@@ -174,6 +175,9 @@ mp_chunk_new(mp_pool_t *pool)
 #else
   mp_chunk_t *chunk = ALLOC(CHUNK_OVERHEAD + sz);
 #endif
+#ifdef MEMPOOL_STATS
+  ++pool->total_chunks_allocated;
+#endif
   CHECK_ALLOC(chunk);
   memset(chunk, 0, sizeof(mp_chunk_t)); /* Doesn't clear the whole thing. */
   chunk->magic = MP_CHUNK_MAGIC;
@@ -189,6 +193,17 @@ mp_chunk_new(mp_pool_t *pool)
   return chunk;
 }
 
+/** DOCDOC */
+static INLINE void
+add_newly_used_chunk_to_used_list(mp_pool_t *pool, mp_chunk_t *chunk)
+{
+  chunk->next = pool->used_chunks;
+  if (chunk->next)
+    chunk->next->prev = chunk;
+  pool->used_chunks = chunk;
+  ASSERT(!chunk->prev);
+}
+
 /** Return an newly allocated item from <b>pool</b>. */
 void *
 mp_pool_get(mp_pool_t *pool)
@@ -214,10 +229,7 @@ mp_pool_get(mp_pool_t *pool)
       chunk->next->prev = NULL;
 
     /* Put the chunk on the 'used' list*/
-    chunk->next = pool->used_chunks;
-    if (chunk->next)
-      chunk->next->prev = chunk;
-    pool->used_chunks = chunk;
+    add_newly_used_chunk_to_used_list(pool, chunk);
 
     ASSERT(!chunk->prev);
     --pool->n_empty_chunks;
@@ -229,11 +241,7 @@ mp_pool_get(mp_pool_t *pool)
     CHECK_ALLOC(chunk);
 
     /* Add the new chunk to the used list. */
-    chunk->next = pool->used_chunks;
-    if (chunk->next)
-      chunk->next->prev = chunk;
-    pool->used_chunks = chunk;
-    ASSERT(!chunk->prev);
+    add_newly_used_chunk_to_used_list(pool, chunk);
   }
 
   ASSERT(chunk->n_allocated < chunk->capacity);
@@ -258,6 +266,9 @@ mp_pool_get(mp_pool_t *pool)
   }
 
   ++chunk->n_allocated;
+#ifdef MEMPOOL_STATS
+  ++pool->total_items_allocated;
+#endif
 
   if (PREDICT_UNLIKELY(chunk->n_allocated == chunk->capacity)) {
     /* This chunk just became full. */
@@ -275,7 +286,6 @@ mp_pool_get(mp_pool_t *pool)
       chunk->next->prev = chunk;
     pool->full_chunks = chunk;
   }
-
   /* And return the memory portion of the mp_allocated_t. */
   return A2M(allocated);
 }
@@ -393,43 +403,111 @@ mp_pool_new(size_t item_size, size_t chunk_capacity)
   return pool;
 }
 
+#ifdef LAZY_CHUNK_SORT
+/** DOCDOC */
+static int
+mp_pool_sort_used_chunks_helper(const void *_a, const void *_b)
+{
+  mp_chunk_t *a = *(mp_chunk_t**)_a;
+  mp_chunk_t *b = *(mp_chunk_t**)_b;
+  return b->n_allocated - a->n_allocated;
+}
+
+/** DOCDOC */
+static void
+mp_pool_sort_used_chunks(mp_pool_t *pool)
+{
+  int i, n=0, inverted=0;
+  mp_chunk_t **chunks, *chunk;
+  for (chunk = pool->used_chunks; chunk; chunk = chunk->next) {
+    ++n;
+    if (chunk->next && chunk->next->n_allocated > chunk->n_allocated)
+      ++inverted;
+  }
+  if (!inverted)
+    return;
+  ASSERT(n);
+  //printf("Sort %d/%d\n",inverted,n);
+  chunks = ALLOC(sizeof(mp_chunk_t *)*n);
+#ifdef ALLOC_CAN_RETURN_NULL
+  if (PREDICT_UNLIKELY(!chunks)) return;
+#endif
+  for (i=0,chunk = pool->used_chunks; chunk; chunk = chunk->next)
+    chunks[i++] = chunk;
+  qsort(chunks, n, sizeof(mp_chunk_t *), mp_pool_sort_used_chunks_helper);
+  pool->used_chunks = chunks[0];
+  chunks[0]->prev = NULL;
+  for (i=1;i<n;++i) {
+    chunks[i-1]->next = chunks[i];
+    chunks[i]->prev = chunks[i-1];
+  }
+  chunks[n-1]->next = NULL;
+  FREE(chunks);
+#if 0
+  inverted = 0;
+  for (chunk = pool->used_chunks; chunk; chunk = chunk->next) {
+    if (chunk->next) {
+      ASSERT(chunk->next->n_allocated <= chunk->n_allocated);
+    }
+  }
+#endif
+  mp_pool_assert_ok(pool);
+}
+#endif
+
 /** If there are more than <b>n</b> empty chunks in <b>pool</b>, free the
  * excess ones that have been empty for the longest.  (If <b>n</b> is less
  * than zero, free only empty chunks that were not used since the last
- * call to mp_pool_clean(), leaving only -<b>n</b>.) */
+ * call to mp_pool_clean(), leaving only -<b>n</b>.)
+ * DOCDOC Keep_recently_used, n_to_keep
+ * XXXX020 maybe dump negative n_to_keep behavior, if k_r_u turns out to be
+ *   smarter.
+ **/
 void
-mp_pool_clean(mp_pool_t *pool, int n)
+mp_pool_clean(mp_pool_t *pool, int n_to_keep, int keep_recently_used)
 {
-  /* XXXX020 this is stupid.  We shouldn't care about empty chunks if there
-   * is lots of space in used chunks. */
-
   mp_chunk_t *chunk, **first_to_free;
-  if (n < 0) {
+
+#ifdef LAZY_CHUNK_SORT
+  mp_pool_sort_used_chunks(pool);
+#endif
+
+  if (n_to_keep < 0) {
     /* As said in the documentation, "negative n" means "leave an additional
      * -n chunks". So replace n with a positive number. */
-    n = pool->min_empty_chunks + (-n);
-    if (n < pool->n_empty_chunks)
-      pool->min_empty_chunks = n;
+    n_to_keep = pool->min_empty_chunks + (-n_to_keep);
+  }
+  if (keep_recently_used) {
+    int n_recently_used = pool->n_empty_chunks - pool->min_empty_chunks;
+    if (n_to_keep < n_recently_used)
+      n_to_keep = n_recently_used;
   }
-  ASSERT(n>=0);
+
+  ASSERT(n_to_keep >= 0);
 
   first_to_free = &pool->empty_chunks;
-  while (*first_to_free && n > 0) {
+  while (*first_to_free && n_to_keep > 0) {
     first_to_free = &(*first_to_free)->next;
-    --n;
+    --n_to_keep;
   }
-  if (!*first_to_free)
+  if (!*first_to_free) {
+    pool->min_empty_chunks = pool->n_empty_chunks;
     return;
+  }
 
   chunk = *first_to_free;
   while (chunk) {
     mp_chunk_t *next = chunk->next;
     chunk->magic = 0xdeadbeef;
     FREE(chunk);
+#ifdef MEMPOOL_STATS
+    ++pool->total_chunks_freed;
+#endif
     --pool->n_empty_chunks;
     chunk = next;
   }
 
+  pool->min_empty_chunks = pool->n_empty_chunks;
   *first_to_free = NULL;
 }
 
@@ -535,6 +613,8 @@ mp_pool_log_status(mp_pool_t *pool, int severity)
     ++n_used;
     bu += chunk->n_allocated * pool->item_alloc_size;
     ba += chunk->mem_size;
+    log_fn(severity, LD_MM, "   used chunk: %d items allocated",
+           chunk->n_allocated);
   }
   log_fn(severity, LD_MM, U64_FORMAT"/"U64_FORMAT
          " bytes in %d partially full chunks",
@@ -556,6 +636,15 @@ mp_pool_log_status(mp_pool_t *pool, int severity)
   log_fn(severity, LD_MM, "Total: "U64_FORMAT"/"U64_FORMAT" bytes allocated "
          "for cell pools are full.",
          U64_PRINTF_ARG(bytes_used), U64_PRINTF_ARG(bytes_allocated));
+
+#ifdef MEMPOOL_STATS
+  log_fn(severity, LD_MM, U64_FORMAT" cell allocations ever; "
+         U64_FORMAT" chunk allocations ever; "
+         U64_FORMAT" chunk frees ever.",
+         U64_PRINTF_ARG(pool->total_items_allocated),
+         U64_PRINTF_ARG(pool->total_chunks_allocated),
+         U64_PRINTF_ARG(pool->total_chunks_freed));
+#endif
 }
 #endif
 
diff --git a/src/common/mempool.h b/src/common/mempool.h
index 577f5cc653..2c5c925f77 100644
--- a/src/common/mempool.h
+++ b/src/common/mempool.h
@@ -18,11 +18,13 @@ typedef struct mp_pool_t mp_pool_t;
 void *mp_pool_get(mp_pool_t *pool);
 void mp_pool_release(void *item);
 mp_pool_t *mp_pool_new(size_t item_size, size_t chunk_capacity);
-void mp_pool_clean(mp_pool_t *pool, int n);
+void mp_pool_clean(mp_pool_t *pool, int n_to_keep, int keep_recently_used);
 void mp_pool_destroy(mp_pool_t *pool);
 void mp_pool_assert_ok(mp_pool_t *pool);
 void mp_pool_log_status(mp_pool_t *pool, int severity);
 
+#define MEMPOOL_STATS
+
 #ifdef MEMPOOL_PRIVATE
 /* These declarations are only used by mempool.c and test.c */
 
@@ -47,6 +49,14 @@ struct mp_pool_t {
   /** Size to allocate for each item, including overhead and alignment
    * padding. */
   size_t item_alloc_size;
+#ifdef MEMPOOL_STATS
+  /** Total number of items allocated ever */
+  uint64_t total_items_allocated;
+  /** Total number of chunks allocated ever */
+  uint64_t total_chunks_allocated;
+  /** Total number of chunks freed ever */
+  uint64_t total_chunks_freed;
+#endif
 };
 #endif
 
diff --git a/src/or/relay.c b/src/or/relay.c
index 576d6e2cf1..c0e308b983 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -1538,7 +1538,7 @@ void
 clean_cell_pool(void)
 {
   tor_assert(cell_pool);
-  mp_pool_clean(cell_pool, -1);
+  mp_pool_clean(cell_pool, -1, 0);
 }
 
 /** Release storage held by <b>cell</b>. */
diff --git a/src/or/test.c b/src/or/test.c
index c1fa399d6c..4b8081bf0f 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -3120,14 +3120,14 @@ test_util_mempool(void)
       //mp_pool_assert_ok(pool);
     }
     if (crypto_rand_int(777)==0)
-      mp_pool_clean(pool, -1);
+      mp_pool_clean(pool, -1, 0);
 
     if (i % 777)
       mp_pool_assert_ok(pool);
   }
   SMARTLIST_FOREACH(allocated, void *, m, mp_pool_release(m));
   mp_pool_assert_ok(pool);
-  mp_pool_clean(pool, 0);
+  mp_pool_clean(pool, 0, 0);
   mp_pool_assert_ok(pool);
   mp_pool_destroy(pool);
   smartlist_free(allocated);