summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorYorhel <git@yorhel.nl>2010-05-03 15:43:15 +0200
committerYorhel <git@yorhel.nl>2010-05-03 15:43:15 +0200
commitb32f207787aedf19ce8d057e193817856c42b89f (patch)
tree4fccb7a6d0c6d474e027a317e2f9ce2046d97645
parenteea8d21d3ff446753c63c88b377767b3ac631365 (diff)
Wrote basic test suite and fixed several bugs along the way
Test suite will have to be expanded to cover more possible situations in which a bug could arrise.
-rw-r--r--.gitignore2
-rw-r--r--Makefile11
-rw-r--r--compll.c41
-rw-r--r--compll.h2
-rw-r--r--test/Makefile20
-rw-r--r--test/func.c146
-rw-r--r--test/provelist13
7 files changed, 210 insertions, 25 deletions
diff --git a/.gitignore b/.gitignore
index a3e5d73..00fa763 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,5 @@
*.o
compll
dump
+test/func-lib
+test/func-nolib
diff --git a/Makefile b/Makefile
index 9218aa1..9bf2ab7 100644
--- a/Makefile
+++ b/Makefile
@@ -1,8 +1,17 @@
+.PHONY: test clean
+
compll.o: compll.c compll.h
- gcc -Wall -Wextra -g compll.c -DDEBUG -o compll
+ gcc -Wall -Wextra -g -c compll.c
+
+compll: compll.c compll.h
+ gcc -Wall -Wextra -g -DDEBUG compll.c -o compll
./compll
clean:
rm -f compll.o compll
+ ${MAKE} -C test clean
+
+test:
+ ${MAKE} -C test test
diff --git a/compll.c b/compll.c
index 064c505..13d1ca0 100644
--- a/compll.c
+++ b/compll.c
@@ -244,6 +244,14 @@ static int block_load(int ab) {
}
+/* invalidate the compressed data of a block */
+#define block_dirty(ab) \
+ if(ablocks[ab].data) { \
+ free(ablocks[ab].data); \
+ ablocks[ab].data = NULL; \
+ }
+
+
/*
* The following is the result of a brainstorm session on how to store the node
@@ -368,7 +376,7 @@ static int block_getfree(short size) {
/* Add the specified node at the correct position in the unused nodes list and
* update ablock.free if necessary */
-static void node_addfree(int ab, unsigned short off) {
+static void node_addfree(int ab, int off) {
unsigned char *dat = ublocks[ablocks[ab].ublock].data;
unsigned short psize = node_head(dat+off) >> 1;
int next, cur = 0;
@@ -446,7 +454,7 @@ static int node_alloc(int ab, unsigned short size) {
/* split this node into another empty node if it is large enough */
free = ((node_head(dat+off) >> 1) - size) << conf_alignment;
- if(free > MIN_NODE_SIZE+2) {
+ if(free >= MIN_NODE_SIZE+2) {
node_head(dat+off) = psize | (node_head(dat+off) & 1);
off2 = off + (size << conf_alignment);
node_head(dat+off2) = ((free >> conf_alignment) << 1) | 1;
@@ -485,6 +493,7 @@ compll_t compll_alloc(unsigned int size) {
off = node_alloc(ab, spack);
assert(off >= 0);
+ block_dirty(ab);
return (((compll_t)ab) << 24) + off;
}
@@ -522,6 +531,7 @@ void compll_free(compll_t node) {
node_usize(dat+off) = node_head(dat+off)>>1;
node_addfree(ab, off);
+ block_dirty(ab);
}
@@ -543,13 +553,7 @@ void *compll_write(compll_t node) {
ub;
if((ub = block_load(ab)) < 0)
return NULL;
-
- /* invalidate the compressed data */
- if(ablocks[ab].data) {
- free(ablocks[ab].data);
- ablocks[ab].data = NULL;
- }
-
+ block_dirty(ab);
return ublocks[ub].data + off;
}
@@ -650,25 +654,16 @@ void dbg_decompress(const unsigned char *src, unsigned int srclen, unsigned char
int main() {
- int i;
- compll_t m;
+ /*int i;
+ compll_t m[10];*/
FILE *f;
- printf("compll_init = %d\n", compll_init(1024, 1, 10, dbg_compress, dbg_decompress));
-
- for(i=4; i<=16; i+=4) {
- m = compll_alloc(i);
- printf("compll_alloc(%d) = %llu (free = %d)\n", i, m, ablocks[0].free);
- memset(compll_write(m), i, i);
- }
+ printf("compll_init = %d\n", compll_init(524288, 16, 1, dbg_compress, dbg_decompress));
- m = compll_alloc(500);
- compll_alloc(10);
- compll_free(m);
- compll_alloc(50);
+ compll_alloc(0x10000);
f = fopen("dump", "w");
- fwrite(ublocks[ablocks[0].ublock].data, conf_blocksize, 1, f);
+ fwrite(ublocks[block_load(0)].data, conf_blocksize, 1, f);
fclose(f);
return 0;
diff --git a/compll.h b/compll.h
index bf1a451..05dca07 100644
--- a/compll.h
+++ b/compll.h
@@ -71,7 +71,7 @@ typedef void * compll_t;
/* nothing has to be initialized,
so the init function is replaced with a no-op */
-#define compll_init(bs, al, cnt, comp, uncomp) {}
+#define compll_init(bs, al, cnt, comp, uncomp) 0
/* allocating a new node is equivalent to calloc() */
#define compll_alloc(size) calloc(size, 1)
diff --git a/test/Makefile b/test/Makefile
new file mode 100644
index 0000000..603293b
--- /dev/null
+++ b/test/Makefile
@@ -0,0 +1,20 @@
+
+COMPLL=../compll.o
+CFLAGS=-I.. -g -Wall -Wextra
+
+test: func-lib func-nolib
+ prove --exec '' - < provelist
+
+func-lib: func.c ../compll.o
+ gcc ${CFLAGS} func.c ${COMPLL} -o func-lib
+
+func-nolib: func.c ../compll.h
+ gcc ${CFLAGS} -DCOMPLL_NOLIB func.c -o func-nolib
+
+../compll.o: ../compll.h ../compll.c
+ ${MAKE} -C .. compll.o
+
+clean:
+ rm -f func-lib func-nolib
+
+
diff --git a/test/func.c b/test/func.c
new file mode 100644
index 0000000..c057ea6
--- /dev/null
+++ b/test/func.c
@@ -0,0 +1,146 @@
+/* This program tests the operation of the library from the perspective of an
+ * application that correctly uses the library. (i.e. this is a high-level
+ * test). Whether the internal state is properly updated and whether all
+ * optimizations are performed is not tested.
+ *
+ * Generates TAP output.
+ */
+
+#include <compll.h>
+
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+
+#define NODENUM 500
+
+#define min(a,b) ((a)>(b)?(b):(a))
+
+int test_num = 0;
+#define isok(ok, exp, args...) printf("%s %d - " exp "\n", (ok) ? "ok" : "not ok", ++test_num, ## args)
+
+
+int blocksize, align, uncomp;
+
+
+/* rather than performing compression, we simply reverse all the bytes and
+ * invert the bits. This makes sure that if, for some reason, the library tries
+ * to interpret the "compressed" data without first calling the decompression
+ * function, things will go wrong and the test will fail. */
+unsigned int dbg_compress(const unsigned char *src, unsigned int srclen, unsigned char *dst, unsigned int dstlen) {
+ unsigned int i;
+ for(i=0; i<min(dstlen, srclen); i++)
+ dst[srclen-i-1] = ~src[i];
+ return srclen;
+}
+void dbg_decompress(const unsigned char *src, unsigned int srclen, unsigned char *dst, unsigned int dstlen) {
+ dbg_compress(src, srclen, dst, dstlen);
+}
+
+
+
+/* this function generates a random sequence of bytes, using the first argument
+ * as seed. Calling this function with the same seed is guaranteed to generate
+ * the same sequence of bytes */
+void randdata(unsigned char *dat, int length, unsigned int seed) {
+ int i;
+ srand(seed);
+ for(i=0; i<length; i++)
+ dat[i] = rand() % 256;
+}
+
+
+
+int main(int argc, char **argv) {
+ compll_t *allocs;
+ int i, s, msize;
+ void *p;
+ char *ndata;
+ compll_t m;
+
+ /* the provided arguments are assumed to be within the specified bounds of the library */
+ if(argc != 4) {
+ printf("%s <blocksize> <align> <uncomp>\n", argv[0]);
+ return 1;
+ }
+ blocksize = atoi(argv[1]);
+ align = atoi(argv[2]);
+ uncomp = atoi(argv[3]);
+ printf("# b/a/u %d/%d/%d\n", blocksize, align, uncomp);
+
+ msize = blocksize-36;
+ printf("1..%d\n", 1 + NODENUM*4 + NODENUM*2 + 10*3);
+
+ i = compll_init(blocksize, align, uncomp, dbg_compress, dbg_decompress);
+ isok(!i, "Initialization");
+ if(i) {
+ printf("Bail out! Initialization failed!\n");
+ return 1;
+ }
+
+ allocs = calloc(sizeof(compll_t), NODENUM+1);
+ ndata = calloc(msize, 1);
+
+ /* allocate NUDENUM nodes of sizes between 1 and msize and perform 3 tests:
+ * 1. compll_alloc() > 0
+ * 2. compll_read(x) != NULL
+ * 3. node data contains zeroes
+ * 4. address is properly aligned
+ */
+ for(i=1; i<=NODENUM; i++) {
+ s = (msize * i) / NODENUM; /* (msize / NODENUM) * i, but with integers */
+ allocs[i] = compll_alloc(s);
+ isok(allocs[i], "compll_alloc(%d)", s);
+ p = (void *) compll_read(allocs[i]);
+ isok(p != NULL, "compll_read()");
+ isok(!memcmp(ndata, p, s), "node data contains zeros");
+ isok(!(((unsigned long long) p) % align), "node pointer is properly aligned");
+ }
+
+ /* loop through the nodes and:
+ * 1. check that compll_write returns a pointer
+ * 2. check that they are still zeroed (i.e. new allocations don't overwrite old data)
+ * 3. write (known) data in the nodes
+ */
+ for(i=1; i<=NODENUM; i++) {
+ s = (msize * i) / NODENUM;
+ p = compll_write(allocs[i]);
+ isok(p != NULL, "compll_write()");
+ isok(!memcmp(ndata, p, s), "node data contains zeros on compll_write()");
+ randdata(p, s, i);
+ }
+
+ /* free some nodes */
+ int freenodes[] = {
+ /* three adjacent nodes (causing two forward merges) */
+ 5, 6, 7,
+ /* same, but causing a backward and forward merge */
+ 10, 9, 11,
+ /* same, but causing a double merge */
+ 15, 13, 14,
+ /* and free some nodes that are guaranteed to fill up an entire block */
+ NODENUM, NODENUM-2, NODENUM-4
+ };
+ for(i=0; i<(int)(sizeof(freenodes)/sizeof(int)); i++) {
+ compll_free(allocs[freenodes[i]]);
+ allocs[freenodes[i]] = 0;
+ }
+
+ /* and allocate a few nodes of random size again, and check that:
+ * 1. compll_alloc() > 0
+ * 2. compll_read(x) != NULL
+ * 3. node data contains zeroes */
+ for(i=0; i<10; i++) {
+ s = rand() % (blocksize/16);
+ m = compll_alloc(s);
+ isok(m, "compll_alloc(%d)", s);
+ p = (void *) compll_read(m);
+ isok(p != NULL, "compll_read()");
+ isok(!memcmp(ndata, p, s), "node data contains zeros");
+ }
+
+ return 0;
+}
+
+
diff --git a/test/provelist b/test/provelist
new file mode 100644
index 0000000..042f451
--- /dev/null
+++ b/test/provelist
@@ -0,0 +1,13 @@
+./func-lib 1024 1 1
+./func-lib 1024 2 1
+./func-lib 1024 4 1
+./func-lib 1024 8 1
+./func-lib 1024 16 1
+./func-lib 1031 4 1
+./func-lib 4933 4 1
+./func-lib 2048 4 5
+./func-lib 2048 4 8
+./func-lib 2048 4 100
+./func-lib 262144 4 1
+./func-lib 524288 4 1
+./func-nolib 2048 4 1