diff options
| -rw-r--r-- | src/ring.c | 224 | ||||
| -rw-r--r-- | test/ring_test.c | 145 | ||||
| -rw-r--r-- | wscript | 21 | ||||
| -rw-r--r-- | zix/ring.h | 108 |
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; +} @@ -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 */ |