[6model/c] initial refcount memory manager with tests

jnthn · Sep 1, 2011 · b19eb80 · b19eb80
1 parent 816dda0
commit b19eb80
Show file tree

Hide file tree

Showing 8 changed files with 688 additions and 11 deletions.
diff --git a/c/src/mem.c b/c/src/mem.c
diff --git a/c/src/mem.h b/c/src/mem.h
@@ -0,0 +1,81 @@
+/* mem.h */
+
+/* For initial testing while the harder bits are still incomplete, */
+/* uncomment the following #define.  It makes the code the simplest */
+/* thing that could possibly work, but it leaks reference cycles. */
+
+#define REFCOUNT_ONLY 1 /* Warning - commenting out now causes errors */
+
+
+/* mem_block */
+struct mem_block {
+    /* The size field has special meanings for certain values: */
+    /* 0 to INT_MAX: size in bytes, any scalar opaque data (like malloc) */
+    /* -1: scalar pointer (reference) to another object */
+    /* -2: list of pointers (references) to other objects */
+    int size;
+    struct mem_node * node;
+    #if defined(REFCOUNT_ONLY)
+        struct mem_rootdata * rootdata;
+        int refcount;
+    #else
+        struct mem_node * rootnode;
+        struct mem_node * referrers;
+        struct mem_node * ref_next;
+        int level;    /* number of hops from root */
+    #endif
+};
+
+
+/* mem_node */
+/* Connectivity information about each memory object. */
+struct mem_node {
+    struct mem_block * block;
+    struct mem_node * rootnode;
+    struct mem_node * referrers;
+    struct mem_node * ref_next;
+    #if ! defined(REFCOUNT_ONLY)
+        int level;    /* number of hops from root */
+    #endif
+};
+
+
+/* mem_listblock */
+/* Stationary base for list contents */
+struct mem_listblock {
+    int listsize;
+    void ** list;
+};
+
+
+/* mem_rootdata */
+struct mem_rootdata {
+    #if defined(REFCOUNT_ONLY)
+        struct mem_block * blocknext;
+        struct mem_block * blockprev;
+    #else
+        struct mem_node * first;
+        struct mem_node * last;
+    #endif
+    int  totalobjects;
+    long totalbytes;
+};
+
+
+/* Function declarations (same whether REFCOUNT_ONLY defined or not) */
+void mem_refdel(void * referrer, void * allocation);
+
+void * mem_init();
+void   mem_final(void * root, int freeflag);
+void * mem_scalar_new(void * parent, int size);
+void * mem_scalar_resize(void * object, int newsize);
+void   mem_scalar_set_ref(void * object, void * target);
+void * mem_scalar_get_ref(void * object);
+void * mem_list_new(void * parent);
+void   mem_list_put(void * list, int item, void * target);
+void * mem_list_get(void * list, int item);
+int    mem_size(void * object);
+long   mem_bytes(void * root);
+int    mem_objects(void * root);
+
+/* end of mem.h */
diff --git a/c/src/threads.c b/c/src/threads.c
@@ -42,8 +42,8 @@ thread_join(struct thread_info * info)
 /* Caution - bear in mind the time required to create and synchronize */
 /* threads.  See for example the HPL-2004-209 report below, stating */
 /* that some of the machine code instructions took over 100 machine */
-/* cycles on a Pentium 4.  More detailed and recent measurements are */
+/* cycles on a Pentium 4.  More recent and detailed measurements are */
-/* very welcome. */
+/* welcome. */
 
 /* See also: */
 /* Lawrence Livermore National Laboratory tutorials: */
@@ -55,4 +55,13 @@ thread_join(struct thread_info * info)
 /* Ross Bencina - Some notes on lock-free and wait-free algorithms */
 /*   http://www.rossbencina.com/code/lockfree */
 
+/* Atomic operations with various C compilers: */
+/* http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html */
+/* http://msdn.microsoft.com/en-us/library/ms684122%28v=VS.85%29.aspx */
+
+/* Lock-free concurrent queue algorithms */
+/* http://www.cs.rochester.edu/u/michael/PODC96.html */
+/* ftp://ftp.cs.rochester.edu/pub/packages/sched_conscious_synch/ */
+/* http://developer.amd.com/documentation/articles/pages/125200689.aspx */
+
 /* end of threads.c */
diff --git a/c/t/02-components/02c-mem.t.c b/c/t/02-components/02c-mem.t.c
@@ -0,0 +1,104 @@
+/* 02c-mem.t.c */
+/* Test memory management, check for memory leaks in blocks and lists */
+
+#include <stdio.h>   /* printf */
+#include <string.h>  /* strcpy strlen */
+#include "../../src/mem.h"
+#include "../Test.h"  /* is_ii i_ll ok plan */
+
+#define TESTOBJECTCOUNT 10000
+#define LINEBUFFERSIZE 128
+
+
+/* test1_7scalars */
+/* Creates many strings, resizes them all, then deletes them. */
+void
+test1_7scalars()
+{
+    int i, totalblocks = 0;
+    long totalbytes = 0L;
+    void *  rootblock;
+    void ** testobjects;
+    char line[LINEBUFFERSIZE];
+
+    rootblock = mem_init();
+    ok(rootblock!=NULL, "create root node");  /* test 1 */
+
+    testobjects = mem_scalar_new(rootblock, TESTOBJECTCOUNT * sizeof(void *));
+    totalbytes += TESTOBJECTCOUNT * sizeof(void *);
+    totalblocks++;
+    sprintf(line, "allocated array for %d test scalars", TESTOBJECTCOUNT);
+    ok(testobjects!=NULL, line);  /* test 2 */
+
+    /* Create TESTOBJECTCOUNT objects on the heap */
+    for (i=0; i<TESTOBJECTCOUNT; ++i) {
+        testobjects[i] = mem_scalar_new(rootblock, 100+i);
+        totalbytes += 100+i;
+        totalblocks++;
+    }
+    sprintf(line, "%d total scalar blocks", totalblocks);
+    is_ii(mem_objects(rootblock), totalblocks, line);  /* test 3 */
+    sprintf(line, "%ld total scalar bytes", totalbytes);
+    is_ll(mem_bytes(rootblock), totalbytes, line);  /* test 4 */
+
+    /* Resize the even numbered objects up and the odd ones down */
+    for (i=0; i<TESTOBJECTCOUNT; ++i) {
+        testobjects[i] = mem_scalar_resize(testobjects[i], 20+2*i );
+        totalbytes += -(100+i) + (20+2*i);
+    }
+    sprintf(line, "after reallocation %ld total bytes", totalbytes);
+    is_ll(mem_bytes(rootblock), totalbytes, line);  /* test 5 */
+
+    /* Unreference all the objects that were created on the heap */
+    /* This is how you "free" memory allocations */
+    for (i=0; i<TESTOBJECTCOUNT; ++i) {
+        mem_refdel(rootblock, testobjects[i]);
+        totalbytes -= (20+2*i);
+        totalblocks--;
+    }
+    sprintf(line, "release array leaves %ld total bytes", totalbytes);
+    is_ll(mem_bytes(rootblock), totalbytes, line);  /* test 6 */
+    sprintf(line, "release array leaves %d total nodes", totalblocks);
+    is_ii(mem_objects(rootblock), totalblocks, line);  /* test 7 */
+
+    /* Release the array containing the test objects */
+    mem_refdel(rootblock, testobjects);
+
+    mem_final(rootblock, 1);
+}
+
+
+/* test8_9lists */
+/* Create and use a list containing two integers and two strings. */
+void
+test8_9lists_of_lists()
+{
+    void * root, * list0, * list1, * scalar0, * scalar1;
+    char * answer = "forty-two";
+    root = mem_init();
+    scalar0 = mem_scalar_new(root, sizeof(int));
+    * (int *) scalar0 = 42;
+    scalar1 = mem_scalar_new(root, strlen(answer)+1);
+    strcpy(scalar1, answer);
+    list0 = mem_list_new(root);
+    mem_list_put(list0, 0, scalar0);
+    mem_list_put(list0, 1, scalar1);
+    is_ii(* (int *) mem_list_get(list0, 0), 42, "list0[0] is 42" );
+    is_ss((char *) mem_list_get(list0, 1), answer, "list0[1] is \"forty-two\"" );
+    /* Unreference the memory to let garbage collection recycle it. */
+    mem_refdel(root, list0);
+    mem_final(root, 1);
+}
+
+
+/* main */
+int
+main(int argc, char * argv[])
+{
+    plan(9);
+    test1_7scalars();
+    test8_9lists_of_lists();
+    return 0;  /* aftwerwards Valgrind should find no memory leaks */
+}
+
+/* end of 02c-mem.t.c */
diff --git a/c/t/Test.h b/c/t/Test.h
@@ -27,6 +27,7 @@ TODO: done_testing();
 
 
 #include <stdio.h>  /* printf */
+#include <string.h> /* strcmp */
 
 int _test_number=0; /* yes, namespace pollution. patches welcome ;-) */
 

diff --git a/c/tools/build/Configure.c b/c/tools/build/Configure.c
@@ -13,10 +13,12 @@
 /* New software emerges, environments and tools evolve, users make */
 /* unforeseen choices.  Monitor the changes through regular testing. */
 
-/* Currently verified to work with:
+/* This project uses only a standard C compiler, currently verified to
- * GNU C compiler on Linux, OS X and Windows (as MinGW).
+ * work with:
+ * GCC, the GNU Compiler Collection on Linux and OS X.
+ * http://www.gnu.org/software/gcc/
  *
- * MinGW
+ * MinGW, Minimalist GNU for Windows
  * http://mingw.org/
  * Currently based on GCC 4.5.2, 85MB disk.
  * Targets Win32 libraries, no Posix emulation or dlopen.
@@ -107,8 +109,8 @@ detection(void)
     printf("  OpenMP: ");
     #if defined( _OPENMP )
         processors = omp_get_num_procs();
-        printf("v%d max processors/threads %d/%d\n", _OPENMP,
+            printf("v%d max processors/threads %d/%d %.9lfs ticks\n",
-            processors, omp_get_max_threads());
+            _OPENMP, processors, omp_get_max_threads(), omp_get_wtick());
         config[OPENMP] =
         #if defined( __GNUC__ )
             "-fopenmp";

diff --git a/c/tools/build/Makefile.in b/c/tools/build/Makefile.in
@@ -64,7 +64,7 @@ test01: t/01-toolchain/01a-cc.t.exe t/01-toolchain/01b-timing.t.exe \
 
 # The test02 target validates the internal libraries of 6model/c
 test02: t/02-components/02a-threads.t.exe t/02-components/02b-hashtable.t.exe \
-		 tools/build/prove$(EXE)
+		t/02-components/02c-mem.t.exe tools/build/prove$(EXE)
 	tools/build/prove -e "" --ext ".exe" t/02-components
 
 # Miscellaneous targets

diff --git a/c/tools/build/prove.c b/c/tools/build/prove.c
@@ -390,8 +390,9 @@ TAP_Parser(FILE * program_output)
             printf("\b");
         fflush(stdout);
     }
-    printf("%d/%d %sok", passed, passed+failed,
+    printf("%d/%d %sok", passed,
-        (passed!=planned || failed!=0) ? "*NOT* " : "");
+        (planned > passed+failed ? planned : passed+failed),
+        (passed!=planned || failed!=0) ? "some not " : "");
     if (planned != passed + failed ) {
         printf(" (%d planned)", planned);
     }
@@ -468,7 +469,7 @@ main(int argc, char * argv[])
 }
 
 /* See also: */
-/* perldoc prove, TAP::Harness, TAP::Parser::Aggregator */
+/* perldoc prove, TAP::Harness, TAP::Parser::Aggregator, */
 /* TAP::Parser::Grammar, TAP::Formatter::Console */
 
 /* end of prove.c */