From ae90063afb7ddabcb505f8390b3b90bc7fea96ca Mon Sep 17 00:00:00 2001 From: David Robillard Date: Mon, 22 Jan 2007 04:07:53 +0000 Subject: Added atomic int/pointer classes to Raul. Added multi-writer queue to Raul. Renamed Queue SRSWQueue (single-reader single-writer). Updated patchage/ingen for Raul changes. git-svn-id: http://svn.drobilla.net/lad/raul@264 a436a847-0d15-0410-975c-d299462d15a1 --- raul.pc.in | 4 +- raul/AtomicInt.h | 75 +++++++++++++++++++ raul/AtomicPtr.h | 43 +++++++++++ raul/Makefile.am | 6 +- raul/Queue.h | 159 ---------------------------------------- raul/SRMWQueue.h | 201 +++++++++++++++++++++++++++++++++++++++++++++++++++ raul/SRSWQueue.h | 152 ++++++++++++++++++++++++++++++++++++++ src/Makefile.am | 3 +- tests/Makefile.am | 8 +- tests/queue_test.cpp | 35 +++++---- 10 files changed, 502 insertions(+), 184 deletions(-) create mode 100644 raul/AtomicInt.h create mode 100644 raul/AtomicPtr.h delete mode 100644 raul/Queue.h create mode 100644 raul/SRMWQueue.h create mode 100644 raul/SRSWQueue.h diff --git a/raul.pc.in b/raul.pc.in index b405f37..78a2368 100644 --- a/raul.pc.in +++ b/raul.pc.in @@ -6,5 +6,5 @@ includedir=@includedir@ Name: raul Version: @VERSION@ Description: A C++ convenience library for realtime audio applications -Libs: -L${libdir} -lraul -Cflags: -I${includedir} +Libs: -L${libdir} -lraul @GLIBMM_LIBS@ +Cflags: -I${includedir} @GLIBMM_CFLAGS@ diff --git a/raul/AtomicInt.h b/raul/AtomicInt.h new file mode 100644 index 0000000..ba8e4b0 --- /dev/null +++ b/raul/AtomicInt.h @@ -0,0 +1,75 @@ +/* This file is part of Ingen. Copyright (C) 2007 Dave Robillard. + * + * Ingen is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Ingen is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_ATOMIC_INT_H +#define RAUL_ATOMIC_INT_H + +#include + +class AtomicInt { +public: + + inline AtomicInt(int val) + { g_atomic_int_set(&_val, val); } + + inline AtomicInt(const AtomicInt& copy) + { g_atomic_int_set(&_val, copy.get()); } + + inline int get() const + { return g_atomic_int_get(&_val); } + + inline void operator=(int val) + { g_atomic_int_set(&_val, val); } + + inline void operator+=(int val) + { g_atomic_int_add(&_val, val); } + + inline void operator-=(int val) + { g_atomic_int_add(&_val, -val); } + + inline bool operator==(int val) const + { return get() == val; } + + inline int operator+(int val) const + { return get() + val; } + + inline AtomicInt& operator++() // prefix + { g_atomic_int_inc(&_val); return *this; } + + inline AtomicInt& operator--() // prefix + { g_atomic_int_add(&_val, -1); return *this; } + + /** Set value to newval iff current value is oldval */ + inline bool compare_and_exchange(int oldval, int newval) + { return g_atomic_int_compare_and_exchange(&_val, oldval, newval); } + + /** Add val to value. + * @return value immediately before addition took place. + */ + inline int exchange_and_add(int val) + { return g_atomic_int_exchange_and_add(&_val, val); } + + /** Decrement value. + * @return true if value is now 0, otherwise false. + */ + inline bool decrement_and_test() + { return g_atomic_int_dec_and_test(&_val); } + +private: + volatile int _val; +}; + +#endif // RAUL_ATOMIC_INT_H diff --git a/raul/AtomicPtr.h b/raul/AtomicPtr.h new file mode 100644 index 0000000..8209ca6 --- /dev/null +++ b/raul/AtomicPtr.h @@ -0,0 +1,43 @@ +/* This file is part of Ingen. Copyright (C) 2007 Dave Robillard. + * + * Ingen is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Ingen is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_ATOMIC_PTR_H +#define RAUL_ATOMIC_PTR_H + +#include + +template +class AtomicPtr { +public: + + inline AtomicPtr(const AtomicPtr& copy) + { g_atomic_pointer_set(&_val, copy.get()); } + + inline T* get() const + { return (T*)g_atomic_pointer_get(&_val); } + + inline void operator=(T* val) + { g_atomic_pointer_set(&_val, val); } + + /** Set value to newval iff current value is oldval */ + inline bool compare_and_exchange(int oldval, int newval) + { return g_atomic_pointer_compare_and_exchange(&_val, oldval, newval); } + +private: + volatile T* _val; +}; + +#endif // RAUL_ATOMIC_PTR_H diff --git a/raul/Makefile.am b/raul/Makefile.am index 64cc7ed..a536a0e 100644 --- a/raul/Makefile.am +++ b/raul/Makefile.am @@ -4,7 +4,8 @@ raulinclude_HEADERS = \ SharedPtr.h \ WeakPtr.h \ Path.h \ - Queue.h \ + SRSWQueue.h \ + SRMWQueue.h \ Semaphore.h \ Mutex.h \ Condition.h \ @@ -14,7 +15,8 @@ raulinclude_HEADERS = \ Atom.h \ JackDriver.h \ RDFQuery.h \ - Namespaces.h + Namespaces.h \ + AtomicInt.h if WITH_LIBLO raulinclude_HEADERS += AtomLiblo.h diff --git a/raul/Queue.h b/raul/Queue.h deleted file mode 100644 index 36d1cca..0000000 --- a/raul/Queue.h +++ /dev/null @@ -1,159 +0,0 @@ -/* This file is part of Ingen. Copyright (C) 2006 Dave Robillard. - * - * Ingen is free software; you can redistribute it and/or modify it under the - * terms of the GNU General Public License as published by the Free Software - * Foundation; either version 2 of the License, or (at your option) any later - * version. - * - * Ingen is distributed in the hope that it will be useful, but WITHOUT ANY - * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS - * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#ifndef RAUL_QUEUE_H -#define RAUL_QUEUE_H - -#include -#include -#include - - -/** Realtime-safe single-reader single-writer queue (aka lock-free ringbuffer) - * - * Implemented as a dequeue in a fixed array. This is read/write thread-safe, - * pushing and popping may occur simultaneously by seperate threads, but - * the push and pop operations themselves are not thread-safe. - * - * FIXME: Verify atomicity of everything here. - * - * \ingroup raul - */ -template -class Queue : boost::noncopyable -{ -public: - Queue(size_t size); - ~Queue(); - - inline bool is_empty() const; - inline bool is_full() const; - - inline size_t capacity() const { return m_size-1; } - inline size_t fill() const; - - inline T& front() const; - - inline bool push(T obj); - inline T& pop(); - -private: - volatile size_t m_front; ///< Index to front of queue (circular) - volatile size_t m_back; ///< Index to back of queue (one past last element) (circular) - const size_t m_size; ///< Size of @ref m_objects (you can store m_size-1 objects) - T* const m_objects; ///< Fixed array containing queued elements -}; - - -template -Queue::Queue(size_t size) -: m_front(0), - m_back(0), - m_size(size+1), - m_objects((T*)calloc(m_size, sizeof(T))) -{ - assert(size > 1); -} - - -template -Queue::~Queue() -{ - free(m_objects); -} - - -/** Return whether or not the queue is empty. - */ -template -inline bool -Queue::is_empty() const -{ - return (m_back == m_front); -} - - -/** Return whether or not the queue is full. - */ -template -inline bool -Queue::is_full() const -{ - // FIXME: This can probably be faster - return (fill() == capacity()); -} - - -/** Returns how many elements are currently in the queue. - */ -template -inline size_t -Queue::fill() const -{ - return (m_back + m_size - m_front) % m_size; -} - - -/** Return the element at the front of the queue without removing it - */ -template -inline T& -Queue::front() const -{ - return m_objects[m_front]; -} - - -/** Push an item onto the back of the Queue - realtime-safe, not thread-safe. - * - * @returns true if @a elem was successfully pushed onto the queue, - * false otherwise (queue is full). - */ -template -inline bool -Queue::push(T elem) -{ - if (is_full()) { - return false; - } else { - m_objects[m_back] = elem; - m_back = (m_back + 1) % (m_size); - return true; - } -} - - -/** Pop an item off the front of the queue - realtime-safe, not thread-safe. - * - * It is a fatal error to call pop() when the queue is empty. - * - * @returns the element popped. - */ -template -inline T& -Queue::pop() -{ - assert(!is_empty()); - assert(m_size > 0); - - T& r = m_objects[m_front]; - m_front = (m_front + 1) % (m_size); - - return r; -} - - -#endif // RAUL_QUEUE_H diff --git a/raul/SRMWQueue.h b/raul/SRMWQueue.h new file mode 100644 index 0000000..2a4955c --- /dev/null +++ b/raul/SRMWQueue.h @@ -0,0 +1,201 @@ +/* This file is part of Ingen. Copyright (C) 2006 Dave Robillard. + * + * Ingen is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Ingen is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_SRMW_QUEUE_H +#define RAUL_SRMW_QUEUE_H + +#include +#include +#include +#include "raul/AtomicInt.h" + +#include +using namespace std; + + +/** Realtime-safe single-reader multi-writer queue (aka lock-free ringbuffer) + * + * Implemented as a dequeue in a fixed array. Both push and pop are realtime + * safe, but only push is threadsafe. In other words, multiple threads can push + * data into this queue for a single thread to consume. + * + * The interface is intentionally as similar to std::queue as possible, but + * note the additional thread restrictions imposed (e.g. empty() is only + * legal to call in the read thread). + * + * Obey the threading restrictions documented here, or horrible nasty (possibly + * undetected) errors will occur. + * + * This is slightly more expensive than the SRMWSRMWQueue. Use that if you don't + * require multiple writers. + * + * \ingroup raul + */ +template +class SRMWQueue : boost::noncopyable +{ +public: + SRMWQueue(size_t size); + ~SRMWQueue(); + + + // Any thread: + + inline size_t capacity() const { return _size-1; } + + + // Write thread(s): + + inline bool full() const; + inline bool push(const T& obj); + + + // Read thread: + + inline bool empty() const; + inline T& front() const; + inline void pop(); + +private: + + // Note that _front doesn't need to be an AtomicInt since it's only accessed + // by the (single) reader thread + + int _front; ///< Circular index of element at front of queue (READER ONLY) + AtomicInt _back; ///< Circular index 1 past element at back of queue (WRITERS ONLY) + AtomicInt _space; ///< Remaining free space for new elements (all threads) + const int _size; ///< Size of @ref _objects (you can store _size-1 objects) + T* const _objects; ///< Fixed array containing queued elements +}; + + +template +SRMWQueue::SRMWQueue(size_t size) + : _front(0) + , _back(0) + , _space(size) + , _size(size+1) + , _objects((T*)calloc(_size, sizeof(T))) +{ + assert(size > 1); + assert(_size-1 == _space.get()); +} + + +template +SRMWQueue::~SRMWQueue() +{ + free(_objects); +} + + +/** Return whether the queue is full. + * + * Write thread(s) only. + */ +template +inline bool +SRMWQueue::full() const +{ + return ( _space.get() <= 0 ); +} + + +/** Push an item onto the back of the SRMWQueue - realtime-safe, not thread-safe. + * + * Write thread(s) only. + * + * @returns true if @a elem was successfully pushed onto the queue, + * false otherwise (queue is full). + */ +template +inline bool +SRMWQueue::push(const T& elem) +{ + const int old_space = _space.exchange_and_add(-1); + + const bool already_full = ( old_space <= 0 ); + + /* Technically right here pop could be called in the reader thread and + * make space available, but no harm in failing anyway - this queue + * really isn't designed to be filled... */ + + if (already_full) { + + /* if multiple threads simultaneously get here, _space may be 0 + * or negative. The next call to pop() will set _space back to + * a sane value. Note that _space is not exposed, so this is okay + * (... assuming this code is correct) */ + + return false; + + } else { + + const int write_index = _back.exchange_and_add(1) % _size; + _objects[write_index] = elem; + + return true; + + } +} + + +/** Return whether the queue is empty. + * + * Read thread only. + */ +template +inline bool +SRMWQueue::empty() const +{ + return ( _space == capacity() ); +} + + +/** Return the element at the front of the queue without removing it. + * + * It is a fatal error to call front() when the queue is empty. + * Read thread only. + */ +template +inline T& +SRMWQueue::front() const +{ + return _objects[_front]; +} + + +/** Pop an item off the front of the queue - realtime-safe, NOT thread-safe. + * + * It is a fatal error to call pop() if the queue is empty. + * Read thread only. + * + * @return true if queue is now empty, otherwise false. + */ +template +inline void +SRMWQueue::pop() +{ + _front = (_front + 1) % (_size); + + if (_space.get() < 0) + _space = 1; + else + ++_space; +} + + +#endif // RAUL_SRMW_QUEUE_H diff --git a/raul/SRSWQueue.h b/raul/SRSWQueue.h new file mode 100644 index 0000000..e7dd60d --- /dev/null +++ b/raul/SRSWQueue.h @@ -0,0 +1,152 @@ +/* This file is part of Ingen. Copyright (C) 2006 Dave Robillard. + * + * Ingen is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Ingen is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_SRSW_QUEUE_H +#define RAUL_SRSW_QUEUE_H + +#include +#include +#include +#include "raul/AtomicInt.h" + + +/** Realtime-safe single-reader single-writer queue (aka lock-free ringbuffer) + * + * Implemented as a dequeue in a fixed array. This is read/write thread-safe, + * pushing and popping may occur simultaneously by seperate threads, but + * the push and pop operations themselves are not thread-safe (ie. there can + * be at most 1 read and at most 1 writer thread). + * + * \ingroup raul + */ +template +class SRSWQueue : boost::noncopyable +{ +public: + SRSWQueue(size_t size); + ~SRSWQueue(); + + // Any thread: + + inline size_t capacity() const { return _size-1; } + + + // Write thread(s): + + inline bool full() const; + inline bool push(const T& obj); + + + // Read thread: + + inline bool empty() const; + inline T& front() const; + inline void pop(); + +private: + volatile size_t _front; ///< Index to front of queue (circular) + volatile size_t _back; ///< Index to back of queue (one past last element) (circular) + const size_t _size; ///< Size of @ref _objects (you can store _size-1 objects) + T* const _objects; ///< Fixed array containing queued elements +}; + + +template +SRSWQueue::SRSWQueue(size_t size) +: _front(0), + _back(0), + _size(size+1), + _objects((T*)calloc(_size, sizeof(T))) +{ + assert(size > 1); +} + + +template +SRSWQueue::~SRSWQueue() +{ + free(_objects); +} + + +/** Return whether or not the queue is empty. + */ +template +inline bool +SRSWQueue::empty() const +{ + return (_back == _front); +} + + +/** Return whether or not the queue is full. + */ +template +inline bool +SRSWQueue::full() const +{ + // FIXME: uses both _front and _back - thread safe? + return ( ((_front - _back + _size) % _size) == 1 ); +} + + +/** Return the element at the front of the queue without removing it + */ +template +inline T& +SRSWQueue::front() const +{ + return _objects[_front]; +} + + +/** Push an item onto the back of the SRSWQueue - realtime-safe, not thread-safe. + * + * @returns true if @a elem was successfully pushed onto the queue, + * false otherwise (queue is full). + */ +template +inline bool +SRSWQueue::push(const T& elem) +{ + if (full()) { + return false; + } else { + _objects[_back] = elem; + _back = (_back + 1) % (_size); + return true; + } +} + + +/** Pop an item off the front of the queue - realtime-safe, not thread-safe. + * + * It is a fatal error to call pop() when the queue is empty. + * + * @returns the element popped. + */ +template +inline void +SRSWQueue::pop() +{ + assert(!empty()); + assert(_size > 0); + + _front = (_front + 1) % (_size); +} + + +#endif // RAUL_SRSW_QUEUE_H diff --git a/src/Makefile.am b/src/Makefile.am index 1e9f60d..aa0b2c8 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,5 +1,4 @@ -AM_CXXFLAGS = -I$(top_srcdir) @RAPTOR_CFLAGS@ @RASQAL_CFLAGS@ @GLIBMM_CFLAGS@ @JACK_CFLAGS@ - +libraul_la_CXXFLAGS = -I$(top_srcdir) @RAPTOR_CFLAGS@ @RASQAL_CFLAGS@ @GLIBMM_CFLAGS@ @JACK_CFLAGS@ libraul_la_LIBADD = @RAPTOR_LIBS@ @RASQAL_LIBS@ @GLIBMM_LIBS@ @JACK_LIBS@ lib_LTLIBRARIES = libraul.la diff --git a/tests/Makefile.am b/tests/Makefile.am index 20209d3..9fba352 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -1,16 +1,18 @@ if BUILD_TESTS -AM_CXXFLAGS = -I.. -lpthread @RASQAL_CFLAGS@ -ALL_LIBS = @RASQAL_LIBS@ ../src/libraul.la +AM_CXXFLAGS = -I.. -lpthread @RASQAL_CFLAGS@ @GLIBMM_CFLAGS@ +ALL_LIBS = @RASQAL_LIBS@ @GLIBMM_LIBS@ ../src/libraul.la -bin_PROGRAMS = path_test thread_test queue_test +bin_PROGRAMS = path_test thread_test queue_test atomic_test thread_test_LDADD = $(ALL_LIBS) path_test_LDADD = $(ALL_LIBS) queue_test_LDADD = $(ALL_LIBS) +atomic_test_LDADD = $(ALL_LIBS) path_test_SOURCES = path_test.cpp thread_test_SOURCES = thread_test.cpp queue_test_SOURCES = queue_test.cpp +atomic_test_SOURCES = atomic_test.cpp endif diff --git a/tests/queue_test.cpp b/tests/queue_test.cpp index c39d156..d299995 100644 --- a/tests/queue_test.cpp +++ b/tests/queue_test.cpp @@ -1,45 +1,48 @@ #include #include -#include "raul/Queue.h" +#include "raul/SRSWQueue.h" +#include "raul/SRMWQueue.h" using std::string; using std::cerr; using std::cout; using std::endl; int main() { - Queue q(10); + //SRSWQueue q(10); + SRMWQueue q(10); - cout << "New queue. Should be empty: " << q.is_empty() << endl; + cout << "New queue. Should be empty: " << q.empty() << endl; cout << "Capacity: " << q.capacity() << endl; - cout << "Fill: " << q.fill() << endl; + //cout << "Fill: " << q.fill() << endl; for (uint i=0; i < 5; ++i) { q.push(i); - assert(!q.is_full()); + assert(!q.full()); q.pop(); } - cout << "Pushed and popped 5 elements. Queue should be empty: " << q.is_empty() << endl; - cout << "Fill: " << q.fill() << endl; + cout << "Pushed and popped 5 elements. Queue should be empty: " << q.empty() << endl; + //cout << "Fill: " << q.fill() << endl; for (uint i=10; i < 20; ++i) { - q.push(i); + assert(q.push(i)); } - cout << "Pushed 10 elements. Queue should be full: " << q.is_full() << endl; - cout << "Fill: " << q.fill() << endl; + cout << "Pushed 10 elements. Queue should be full: " << q.full() << endl; + //cout << "Fill: " << q.fill() << endl; cout << "The digits 10->19 should print: " << endl; - while (!q.is_empty()) { - int foo = q.pop(); + while (!q.empty()) { + int foo = q.front(); + q.pop(); cout << "Popped: " << foo << endl; } - cout << "Queue should be empty: " << q.is_empty() << endl; - cout << "Fill: " << q.fill() << endl; + cout << "Queue should be empty: " << q.empty() << endl; + //cout << "Fill: " << q.fill() << endl; cout << "Attempting to add eleven elements to queue of size 10. Only first 10 should succeed:" << endl; for (uint i=20; i <= 39; ++i) { cout << i; - cout << " - Fill: " << q.fill(); - cout << ", is full: " << q.is_full(); + //cout << " - Fill: " << q.fill(); + cout << " - full: " << q.full(); cout << ", succeeded: " << q.push(i) << endl; } -- cgit v1.2.1