Add ZixRing.

git-svn-id: http://svn.drobilla.net/zix/trunk@13 df6676b4-ccc9-40e5-b5d6-7c4628a128e3

4 files changed, 492 insertions, 6 deletions

diff --git a/src/ring.c b/src/ring.c
new file mode 100644
index 0000000..1553ba5
--- /dev/null
+++ b/src/ring.c
@@ -0,0 +1,224 @@
+/*
+  Copyright 2011 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#ifdef HAVE_MLOCK
+#    include <sys/mman.h>
+#endif
+
+#include "zix/ring.h"
+
+#if defined(__APPLE__)
+#    include <libkern/OSAtomic.h>
+#    define ZIX_FULL_BARRIER() OSMemoryBarrier()
+#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
+#    define ZIX_FULL_BARRIER() __sync_synchronize()
+#else
+#    warning Memory barriers unsupported, possible bugs on SMP systems
+#    define ZIX_FULL_BARRIER()
+#endif
+
+/* No support for any systems with separate read and write barriers */
+#define ZIX_READ_BARRIER() ZIX_FULL_BARRIER()
+#define ZIX_WRITE_BARRIER() ZIX_FULL_BARRIER()
+
+struct ZixRingImpl {
+	uint32_t write_head;  ///< Read index into buf
+	uint32_t read_head;   ///< Write index into buf
+	uint32_t size;        ///< Size (capacity) in bytes
+	uint32_t size_mask;   ///< Mask for fast modulo
+	char*    buf;         ///< Contents
+};
+
+static inline uint32_t
+next_power_of_two(uint32_t size)
+{
+	// http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
+	size--;
+	size |= size >> 1;
+	size |= size >> 2;
+	size |= size >> 4;
+	size |= size >> 8;
+	size |= size >> 16;
+	size++;
+	return size;
+}
+
+ZixRing*
+zix_ring_new(uint32_t size)
+{
+	ZixRing* ring = (ZixRing*)malloc(sizeof(ZixRing));
+	ring->write_head = 0;
+	ring->read_head  = 0;
+	ring->size       = next_power_of_two(size);
+	ring->size_mask  = ring->size - 1;
+	ring->buf        = malloc(ring->size);
+	assert(zix_ring_read_space(ring) == 0);
+	assert(zix_ring_write_space(ring) == ring->size - 1);
+	return ring;
+}
+
+void
+zix_ring_free(ZixRing* ring)
+{
+	free(ring->buf);
+	free(ring);
+}
+
+void
+zix_ring_mlock(ZixRing* ring)
+{
+#ifdef HAVE_MLOCK
+	mlock(ring, sizeof(ZixRing));
+	mlock(ring->buf, ring->size);
+#else
+#    warning Memory locking (via mlock) unsupported
+#endif
+}
+
+void
+zix_ring_reset(ZixRing* ring)
+{
+	ring->write_head = 0;
+	ring->read_head  = 0;
+}
+
+static inline uint32_t
+read_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
+{
+	if (w > r) {
+		return w - r;
+	} else {
+		return (w - r + ring->size) & ring->size_mask;
+	}
+}
+
+uint32_t
+zix_ring_read_space(const ZixRing* ring)
+{
+	return read_space_internal(ring, ring->read_head, ring->write_head);
+}
+
+static inline uint32_t
+write_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
+{
+	if (w > r) {
+		return ((r - w + ring->size) & ring->size_mask) - 1;
+	} else if (w < r) {
+		return (r - w) - 1;
+	} else {
+		return ring->size - 1;
+	}
+}
+
+uint32_t
+zix_ring_write_space(const ZixRing* ring)
+{
+	return write_space_internal(ring, ring->read_head, ring->write_head);
+}
+
+uint32_t
+zix_ring_capacity(const ZixRing* ring)
+{
+	return ring->size - 1;
+}
+
+static inline uint32_t
+peek_internal(const ZixRing* ring, uint32_t r, uint32_t w,
+              uint32_t size, void* dst)
+{
+	if (read_space_internal(ring, r, w) < size) {
+		return 0;
+	}
+
+	if (r + size < ring->size) {
+		memcpy(dst, &ring->buf[r], size);
+	} else {
+		const uint32_t first_size = ring->size - r;
+		memcpy(dst, &ring->buf[r], first_size);
+		memcpy(dst, &ring->buf[0], size - first_size);
+	}
+
+	return size;
+}
+
+uint32_t
+zix_ring_peek(ZixRing* ring, void* dst, uint32_t size)
+{
+	const uint32_t r = ring->read_head;
+	const uint32_t w = ring->write_head;
+
+	return peek_internal(ring, r, w, size, dst);
+}
+
+uint32_t
+zix_ring_read(ZixRing* ring, void* dst, uint32_t size)
+{
+	const uint32_t r = ring->read_head;
+	const uint32_t w = ring->write_head;
+
+	if (peek_internal(ring, r, w, size, dst)) {
+		ZIX_READ_BARRIER();
+		ring->read_head = (r + size) & ring->size_mask;
+		return size;
+	} else {
+		return 0;
+	}
+}
+
+uint32_t
+zix_ring_skip(ZixRing* ring, uint32_t size)
+{
+	const uint32_t r = ring->read_head;
+	const uint32_t w = ring->write_head;
+	if (read_space_internal(ring, r, w) < size) {
+		return 0;
+	}
+
+	ZIX_READ_BARRIER();
+	ring->read_head = (r + size) & ring->size_mask;
+	return size;
+}
+
+uint32_t
+zix_ring_write(ZixRing* ring, const void* src, uint32_t size)
+{
+	const uint32_t r = ring->read_head;
+	const uint32_t w = ring->write_head;
+	if (write_space_internal(ring, r, w) < size) {
+		return 0;
+	}
+
+	if (w + size <= ring->size) {
+		memcpy(&ring->buf[w], src, size);
+		ZIX_WRITE_BARRIER();
+		ring->write_head = (w + size) & ring->size_mask;
+	} else {
+		const uint32_t this_size = ring->size - w;
+		assert(this_size < size);
+		assert(w + this_size <= ring->size);
+		memcpy(&ring->buf[w], src, this_size);
+		memcpy(&ring->buf[0], (char*)src + this_size, size - this_size);
+		ZIX_WRITE_BARRIER();
+		ring->write_head = size - this_size;
+	}
+
+	return size;
+}
diff --git a/test/ring_test.c b/test/ring_test.c
new file mode 100644
index 0000000..6fc0541
--- /dev/null
+++ b/test/ring_test.c
@@ -0,0 +1,145 @@
+/*
+  Copyright 2011 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#include <limits.h>
+#include <pthread.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "zix/ring.h"
+
+#define MSG_SIZE 4
+
+ZixRing* ring       = 0;
+size_t   n_writes   = 0;
+bool     read_error = false;
+
+static int
+gen_msg(int* msg, int start)
+{
+	for (int i = 0; i < MSG_SIZE; ++i) {
+		msg[i] = start;
+		start  = (start + 1) % INT_MAX;
+	}
+	return start;
+}
+
+static int
+cmp_msg(int* msg1, int* msg2)
+{
+	for (int i = 0; i < MSG_SIZE; ++i) {
+		if (msg1[i] != msg2[i]) {
+			fprintf(stderr, "ERROR: %d != %d @ %d\n", msg1[i], msg2[i], i);
+			return 0;
+		}
+	}
+
+	return 1;
+}
+
+static void*
+reader(void* arg)
+{
+	printf("Reader starting\n");
+
+	int    ref_msg[MSG_SIZE];   // Reference generated for comparison
+	int    read_msg[MSG_SIZE];  // Read from ring
+	size_t count = 0;
+	int    start = gen_msg(ref_msg, 0);
+	for (size_t i = 0; i < n_writes; ++i) {
+		if (zix_ring_read_space(ring) >= MSG_SIZE * sizeof(int)) {
+			if (zix_ring_read(ring, read_msg, MSG_SIZE * sizeof(int))) {
+				if (!cmp_msg(ref_msg, read_msg)) {
+					printf("FAIL: Message %zu is corrupt\n", count);
+					read_error = true;
+					return NULL;
+				}
+				start = gen_msg(ref_msg, start);
+				++count;
+			}
+		}
+	}
+
+	printf("Reader finished\n");
+	return NULL;
+}
+
+static void*
+writer(void* arg)
+{
+	printf("Writer starting\n");
+
+	int write_msg[MSG_SIZE];  // Written to ring
+	int start = gen_msg(write_msg, 0);
+	for (size_t i = 0; i < n_writes; ++i) {
+		if (zix_ring_write_space(ring) >= MSG_SIZE * sizeof(int)) {
+			if (zix_ring_write(ring, write_msg, MSG_SIZE * sizeof(int))) {
+				start = gen_msg(write_msg, start);
+			}
+		}
+	}
+
+	printf("Writer finished\n");
+	return NULL;
+}
+
+int
+main(int argc, char** argv)
+{
+	if (argc > 1 && argv[1][0] == '-') {
+		printf("Usage: %s SIZE N_WRITES\n", argv[0]);
+		return 1;
+	}
+
+	int size = 1024;
+	if (argc > 1) {
+		size = atoi(argv[1]);
+	}
+
+	n_writes = size * 1024;
+	if (argc > 2) {
+		n_writes = atoi(argv[2]);
+	}
+
+	printf("Testing %zu writes of %d ints to a %d int ring...\n",
+	       n_writes, MSG_SIZE, size);
+
+	ring = zix_ring_new(size);
+
+	pthread_t reader_thread;
+	if (pthread_create(&reader_thread, NULL, reader, NULL)) {
+		fprintf(stderr, "Failed to create reader thread\n");
+		return 1;
+	}
+
+	pthread_t writer_thread;
+	if (pthread_create(&writer_thread, NULL, writer, NULL)) {
+		fprintf(stderr, "Failed to create writer thread\n");
+		return 1;
+	}
+
+	pthread_join(reader_thread, NULL);
+	pthread_join(writer_thread, NULL);
+
+	if (read_error) {
+		fprintf(stderr, "FAIL: Read error\n");
+		return 1;
+	}
+
+	return 0;
+}
diff --git a/wscript b/wscript
index 754fa2d..d3cc8dc 100644
--- a/wscript
+++ b/wscript
@@ -45,6 +45,12 @@ def configure(conf):
     autowaf.check_pkg(conf, 'glib-2.0', uselib_store='GLIB',
                       atleast_version='2.0.0', mandatory=False)
 
+    # Check for dladdr
+    conf.check(function_name='mlock',
+               header_name='sys/mman.h',
+               define_name='HAVE_MLOCK',
+               mandatory=False)
+
     conf.env['BUILD_TESTS'] = Options.options.build_tests
     if conf.is_defined('HAVE_GLIB'):
         conf.env['BUILD_BENCH'] = Options.options.build_bench
@@ -56,6 +62,8 @@ def configure(conf):
     autowaf.display_msg(conf, "Benchmarks", str(conf.env['BUILD_BENCHx']))
     print('')
 
+tests = ['ring_test', 'sorted_array_test', 'tree_test']
+
 def build(bld):
     # C Headers
     bld.install_files('${INCLUDEDIR}/zix', bld.path.ant_glob('zix/*.h'))
@@ -64,8 +72,9 @@ def build(bld):
     autowaf.build_pc(bld, 'ZIX', ZIX_VERSION, [])
 
     lib_source = '''
-        src/tree.c
+        src/ring.c
         src/sorted_array.c
+        src/tree.c
     '''
 
     # Library
@@ -87,18 +96,18 @@ def build(bld):
         obj.name         = 'libzix_static'
         obj.target       = 'zix_static'
         obj.install_path = ''
-        obj.cflags       = [ '-fprofile-arcs',  '-ftest-coverage' ]
+        obj.cflags       = ['-fprofile-arcs',  '-ftest-coverage' ]
 
         # Unit test programs
-        for i in ['tree_test', 'sorted_array_test']:
+        for i in tests:
             obj = bld(features = 'c cprogram')
             obj.source       = 'test/%s.c' % i
             obj.includes     = ['.']
             obj.use          = 'libzix_static'
-            obj.linkflags    = '-lgcov'
+            obj.linkflags    = ['-lgcov', '-lpthread']
             obj.target       = 'test/%s' % i
             obj.install_path = ''
-            obj.cflags       = [ '-fprofile-arcs',  '-ftest-coverage' ]
+            obj.cflags       = ['-fprofile-arcs',  '-ftest-coverage' ]
 
     if bld.env['BUILD_BENCH']:
         # Benchmark programs
@@ -156,6 +165,6 @@ def upload_docs(ctx):
 
 def test(ctx):
     autowaf.pre_test(ctx, APPNAME)
-    for i in ['tree_test', 'sorted_array_test']:
+    for i in tests:
         autowaf.run_tests(ctx, APPNAME, ['test/%s' % i], dirs=['./src','./test'])
     autowaf.post_test(ctx, APPNAME)
diff --git a/zix/ring.h b/zix/ring.h
new file mode 100644
index 0000000..67b71f5
--- /dev/null
+++ b/zix/ring.h
@@ -0,0 +1,108 @@
+/*
+  Copyright 2011 David Robillard <http://drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#ifndef ZIX_RING_H
+#define ZIX_RING_H
+
+#include <stdint.h>
+
+#include "zix/common.h"
+
+/**
+   A lock-free ring buffer.
+
+   Thread-safe with a single reader and single writer, and realtime safe
+   on both ends.
+*/
+typedef struct ZixRingImpl ZixRing;
+
+/**
+   Create a new ring.
+   @param size Size in bytes (note this may be rounded up).
+*/
+ZixRing*
+zix_ring_new(uint32_t size);
+
+/**
+   Destroy a ring.
+*/
+void
+zix_ring_free(ZixRing* ring);
+
+/**
+   Lock the ring data into physical memory.
+
+   This function is NOT thread safe or real-time safe, but it should be called
+   after zix_ring_new() to lock all ring memory to avoid page faults while
+   using the ring (i.e. this function MUST be called first in order for the
+   ring to be truly real-time safe).
+
+*/
+void
+zix_ring_mlock(ZixRing* ring);
+
+/**
+   Reset (empty) a ring.
+
+   This function is NOT thread-safe, it may only be called when there are no
+   readers or writers.
+*/
+void
+zix_ring_reset(ZixRing* ring);
+
+/**
+   Return the number of bytes of space available for reading.
+*/
+uint32_t
+zix_ring_read_space(const ZixRing* ring);
+
+/**
+   Return the number of bytes of space available for writing.
+*/
+uint32_t
+zix_ring_write_space(const ZixRing* ring);
+
+/**
+   Return the capacity (i.e. total write space when empty).
+*/
+uint32_t
+zix_ring_capacity(const ZixRing* ring);
+
+/**
+   Read from the ring without advancing the read head.
+*/
+uint32_t
+zix_ring_peek(ZixRing* ring, void* dst, uint32_t size);
+
+/**
+   Read from the ring and advance the read head.
+*/
+uint32_t
+zix_ring_read(ZixRing* ring, void* dst, uint32_t size);
+
+/**
+   Skip data in the ring (advance read head without reading).
+*/
+uint32_t
+zix_ring_skip(ZixRing* ring, uint32_t size);
+
+/**
+   Write data to the ring.
+*/
+uint32_t
+zix_ring_write(ZixRing* ring, const void* src, uint32_t size);
+
+#endif  /* ZIX_RING_H */