[or-cvs] r9938: Unit tests and debugging for memory pool implementation. (in tor/trunk: . src/common src/or)

[nickm@xxxxxxxx]

Author: nickm
Date: 2007-04-10 20:30:25 -0400 (Tue, 10 Apr 2007)
New Revision: 9938

Modified:
   tor/trunk/
   tor/trunk/src/common/mempool.c
   tor/trunk/src/common/mempool.h
   tor/trunk/src/or/test.c
Log:
 r12336@catbus:  nickm | 2007-04-10 17:34:25 -0400
 Unit tests and debugging for memory pool implementation.



Property changes on: tor/trunk
___________________________________________________________________
 svk:merge ticket from /tor/branches/mempool [r12336] on 8246c3cf-6607-4228-993b-4d95d33730f1

Modified: tor/trunk/src/common/mempool.c
===================================================================
--- tor/trunk/src/common/mempool.c	2007-04-11 00:30:22 UTC (rev 9937)
+++ tor/trunk/src/common/mempool.c	2007-04-11 00:30:25 UTC (rev 9938)
@@ -56,6 +56,8 @@
 /** DOCDOC */
 #define MIN_CHUNK 4096
 
+typedef struct mp_allocated_t mp_allocated_t;
+
 /** DOCDOC */
 struct mp_allocated_t {
   mp_chunk_t *in_chunk;
@@ -67,15 +69,29 @@
 };
 
 /** DOCDOC */
+struct mp_chunk_t {
+  unsigned long magic;
+  mp_chunk_t *next;
+  mp_chunk_t *prev;
+  mp_pool_t *pool;
+  mp_allocated_t *first_free;
+  int n_allocated;
+  int capacity;
+  size_t mem_size;
+  char *next_mem;
+  char mem[1];
+};
+
+/** DOCDOC */
 #define MP_CHUNK_MAGIC 0x09870123
 
 /** DOCDOC */
 #define CHUNK_OVERHEAD (sizeof(mp_chunk_t)-1)
 
 /** DOCDOC */
-#define A2M(a) (&(a)->mem)
+#define A2M(a) (&(a)->mem[0])
 /** DOCDOC */
-#define M2A(p) ( ((char*)p) - STRUCT_OFFSET(mp_chunk_t, mem) )
+#define M2A(p) ( ((char*)p) - STRUCT_OFFSET(mp_allocated_t, mem) )
 
 /* INVARIANT: every chunk can hold 2 or more items. */
 
@@ -113,6 +129,7 @@
       chunk->next->prev = chunk;
     pool->used_chunks = chunk;
     ASSERT(!chunk->prev);
+    --pool->n_empty_chunks;
   } else {
     /* Allocate a new chunk and add it to the used list. */
     chunk = mp_chunk_new(pool);
@@ -130,7 +147,7 @@
     chunk->first_free = allocated->next_free;
     allocated->next_free = NULL; /* debugging */
   } else {
-    ASSERT(chunk->next_mem + pool->item_alloc_size <
+    ASSERT(chunk->next_mem + pool->item_alloc_size <=
            chunk->mem + chunk->mem_size);
     allocated = (void*)chunk->next_mem;
     chunk->next_mem += pool->item_alloc_size;
@@ -147,7 +164,8 @@
       chunk->next->prev = NULL;
 
     chunk->next = pool->full_chunks;
-    pool->full_chunks->prev = chunk;
+    if (chunk->next)
+      chunk->next->prev = chunk;
     pool->full_chunks = chunk;
   }
 
@@ -245,7 +263,7 @@
   if (chunk_capacity < MIN_CHUNK) /* Guess system page size. */
     chunk_capacity = MIN_CHUNK;
 
-  pool->new_chunk_capacity = (chunk_capacity-CHUNK_OVERHEAD / alloc_size);
+  pool->new_chunk_capacity = (chunk_capacity-CHUNK_OVERHEAD) / alloc_size;
   pool->item_alloc_size = alloc_size;
 
   return pool;
@@ -291,3 +309,54 @@
   FREE(pool);
 }
 
+static int
+assert_chunks_ok(mp_pool_t *pool, mp_chunk_t *chunk, int empty, int full)
+{
+  mp_allocated_t *allocated;
+  int n = 0;
+  if (chunk)
+    ASSERT(chunk->prev == NULL);
+
+  while (chunk) {
+    n++;
+    ASSERT(chunk->magic == MP_CHUNK_MAGIC);
+    ASSERT(chunk->pool == pool);
+    for (allocated = chunk->first_free; allocated;
+         allocated = allocated->next_free) {
+      ASSERT(allocated->in_chunk == chunk);
+    }
+    if (empty)
+      ASSERT(chunk->n_allocated == 0);
+    else if (full)
+      ASSERT(chunk->n_allocated == chunk->capacity);
+    else
+      ASSERT(chunk->n_allocated > 0 && chunk->n_allocated < chunk->capacity);
+
+    ASSERT(chunk->capacity == pool->new_chunk_capacity);
+
+    ASSERT(chunk->mem_size ==
+           pool->new_chunk_capacity * pool->item_alloc_size);
+
+    ASSERT(chunk->next_mem >= chunk->mem &&
+           chunk->next_mem <= chunk->mem + chunk->mem_size);
+
+    if (chunk->next)
+      ASSERT(chunk->next->prev == chunk);
+
+    chunk = chunk->next;
+  }
+  return n;
+}
+
+void
+mp_pool_assert_ok(mp_pool_t *pool)
+{
+  int n_empty;
+
+  n_empty = assert_chunks_ok(pool, pool->empty_chunks, 1, 0);
+  assert_chunks_ok(pool, pool->full_chunks, 0, 1);
+  assert_chunks_ok(pool, pool->used_chunks, 0, 0);
+
+  ASSERT(pool->n_empty_chunks == n_empty);
+}
+

Modified: tor/trunk/src/common/mempool.h
===================================================================
--- tor/trunk/src/common/mempool.h	2007-04-11 00:30:22 UTC (rev 9937)
+++ tor/trunk/src/common/mempool.h	2007-04-11 00:30:25 UTC (rev 9938)
@@ -17,32 +17,18 @@
 mp_pool_t *mp_pool_new(size_t item_size, unsigned int n_per_chunk);
 void mp_pool_clean(mp_pool_t *pool);
 void mp_pool_destroy(mp_pool_t *pool);
+void mp_pool_assert_ok(mp_pool_t *pool);
 
 #ifdef MEMPOOL_PRIVATE
-typedef struct mp_allocated_t mp_allocated_t;
 typedef struct mp_chunk_t mp_chunk_t;
 
 /** DOCDOC */
-struct mp_chunk_t {
-  unsigned long magic;
-  mp_chunk_t *next;
-  mp_chunk_t *prev;
-  mp_pool_t *pool;
-  mp_allocated_t *first_free;
-  int n_allocated;
-  int capacity;
-  size_t mem_size;
-  char *next_mem;
-  char mem[1];
-};
-
-/** DOCDOC */
 struct mp_pool_t {
   mp_chunk_t *empty_chunks;
   mp_chunk_t *used_chunks;
   mp_chunk_t *full_chunks;
   int n_empty_chunks;
-  size_t new_chunk_capacity;
+  int new_chunk_capacity;
   size_t item_alloc_size;
 };
 #endif

Modified: tor/trunk/src/or/test.c
===================================================================
--- tor/trunk/src/or/test.c	2007-04-11 00:30:22 UTC (rev 9937)
+++ tor/trunk/src/or/test.c	2007-04-11 00:30:25 UTC (rev 9938)
@@ -23,9 +23,12 @@
 #include <dirent.h>
 #endif
 
+#define MEMPOOL_PRIVATE
+
 #include "or.h"
 #include "../common/test.h"
 #include "../common/torgzip.h"
+#include "../common/mempool.h"
 
 int have_failed = 0;
 
@@ -2104,6 +2107,52 @@
   crypto_free_cipher_env(c);
 }
 
+static void
+test_mempool(void)
+{
+  mp_pool_t *pool;
+  smartlist_t *allocated;
+  int i;
+
+  pool = mp_pool_new(1, 100);
+  test_assert(pool->new_chunk_capacity >= 100);
+  test_assert(pool->item_alloc_size >= sizeof(void*)+1);
+  mp_pool_destroy(pool);
+
+  pool = mp_pool_new(241, 10);
+  test_assert(pool->new_chunk_capacity >= 10);
+  test_assert(pool->item_alloc_size >= sizeof(void*)+241);
+  test_eq(pool->item_alloc_size & 0x03, 0);
+  test_assert(pool->new_chunk_capacity < 60);
+
+  allocated = smartlist_create();
+  for (i = 0; i < 100000; ++i) {
+    if (smartlist_len(allocated) < 20 || crypto_rand_int(2)) {
+      void *m = mp_pool_get(pool);
+      memset(m, 0x09, 241);
+      smartlist_add(allocated, m);
+      //printf("%d: %p\n", i, m);
+      //mp_pool_assert_ok(pool);
+    } else {
+      int idx = crypto_rand_int(smartlist_len(allocated));
+      void *m = smartlist_get(allocated, idx);
+      //printf("%d: free %p\n", i, m);
+      smartlist_del(allocated, idx);
+      mp_pool_release(m);
+      //mp_pool_assert_ok(pool);
+    }
+    if (crypto_rand_int(777)==0)
+      mp_pool_clean(pool);
+
+    if (i % 777)
+      mp_pool_assert_ok(pool);
+  }
+  SMARTLIST_FOREACH(allocated, void *, m, mp_pool_release(m));
+  mp_pool_assert_ok(pool);
+  mp_pool_destroy(pool);
+  smartlist_free(allocated);
+}
+
 int
 main(int c, char**v)
 {
@@ -2145,6 +2194,7 @@
   test_gzip();
   test_util();
   test_smartlist();
+  test_mempool();
   test_strmap();
   test_control_formats();
   test_pqueue();