Add managed_ptr for automatic real-time safe garbage collection

4 files changed, 160 insertions, 74 deletions

diff --git a/NEWS b/NEWS
index 3c36ddc..f237d29 100644
--- a/NEWS
+++ b/NEWS
@@ -1,4 +1,4 @@
-raul (0.8.5) unstable;
+raul (0.8.7) unstable;
 
   * Remove glib dpendency
   * Remove boost dependency
@@ -7,13 +7,14 @@ raul (0.8.5) unstable;
   * Remove features now provided by C++11
   * Improve RingBuffer
   * Add ThreadVar, a thread-specific variable class
+  * Add managed_ptr for automatic real-time safe garbage collection
   * Implement Semaphore for Windows
   * Improve test suite
   * Remove several questionable classes
   * Add INSTALL file
   * Update license to GPL3+
 
- -- David Robillard <d@drobilla.net>  Mon, 26 Sep 2016 13:08:52 -0400
+ -- David Robillard <d@drobilla.net>  Sun, 12 Feb 2017 15:08:23 +0100
 
 raul (0.8.0) stable;
 
diff --git a/raul/Maid.hpp b/raul/Maid.hpp
index edefabe..7f5a299 100644
--- a/raul/Maid.hpp
+++ b/raul/Maid.hpp
@@ -1,6 +1,6 @@
 /*
   This file is part of Raul.
-  Copyright 2007-2014 David Robillard <http://drobilla.net>
+  Copyright 2007-2017 David Robillard <http://drobilla.net>
 
   Raul 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
@@ -25,76 +25,77 @@
 
 namespace Raul {
 
-/** Explicit quasi-garbage-collector.
+/** Explicit garbage-collector.
  *
  * This allows objects to be disposed of in a real-time thread, but actually
- * deleted later by another thread which calls cleanup().
+ * deleted later by another thread which calls cleanup().  Disposable objects
+ * may be explicitly disposed by calling dispose(), or automatically managed
+ * with a managed_ptr which can safely be dropped in any thread, including
+ * real-time threads.
  *
  * \ingroup raul
  */
 class Maid : public Noncopyable
 {
 public:
-	/** An object that can be managed by the maid using shared_ptr. */
-	class Manageable : public Deletable {
+	/** An object that can be disposed via Maid::dispose(). */
+	class Disposable : public Deletable {
 	public:
-		Manageable() {}
+		Disposable() : _maid_next(nullptr) {}
 
 	private:
 		friend class Maid;
-		std::shared_ptr<Manageable> _maid_next;
+		Disposable* _maid_next;
 	};
 
-	/** An object that can be disposed via Maid::dispose(). */
-	class Disposable : public Deletable {
+	/** Deleter for Disposable objects. */
+	template<typename T>
+	class Disposer {
 	public:
-		Disposable() : _maid_next(NULL) {}
+		Disposer(Maid& maid) : _maid(&maid) {}
+		Disposer()           : _maid(nullptr) {}
 
-	private:
-		friend class Maid;
-		Disposable* _maid_next;
+		void operator()(T* obj) {
+			if (_maid) { _maid->dispose(obj); }
+		}
+
+		Maid* _maid;
 	};
 
-	Maid() : _disposed(NULL) {}
+	/** A managed pointer that automatically disposes of its contents.
+	 *
+	 * This is a unique_ptr so that it is possible to statically verify that
+	 * code is real-time safe.
+	 */
+	template<typename T> using managed_ptr = std::unique_ptr<T, Disposer<T>>;
+
+	Maid() : _disposed(nullptr) {}
 
-	inline ~Maid() {
-		cleanup();
+	inline ~Maid() { cleanup(); }
+
+	/** Return false iff there is currently no garbage. */
+	inline bool empty() const {
+		return !(bool)_disposed.load(std::memory_order_relaxed);
 	}
 
-	/** Dispose of an object when cleanup() is called next.
+	/** Enqueue an object for deletion when cleanup() is called next.
 	 *
-	 * This is thread safe, and real-time safe assuming reasonably low
-	 * contention.  If real-time threads need to push, do not call this very
-	 * rapidly from many threads.
+	 * This is thread-safe, and real-time safe assuming reasonably low
+	 * contention.
 	 */
 	inline void dispose(Disposable* obj) {
 		if (obj) {
-			while (true) {
-				obj->_maid_next = _disposed.load();
-				if (_disposed.compare_exchange_weak(obj->_maid_next, obj)) {
-					return;
-				}
-			}
+			// Atomically add obj to the head of the disposed list
+			do {
+				obj->_maid_next = _disposed.load(std::memory_order_relaxed);
+			} while (!_disposed.compare_exchange_weak(
+				         obj->_maid_next, obj,
+				         std::memory_order_release,
+				         std::memory_order_relaxed));
 		}
 	}
 
-	/** Manage an object held by a shared pointer.
-	 *
-	 * This will hold a reference to `ptr` ensuring it will not be deleted
-	 * except by cleanup().  This is mainly useful to allow dropping references
-	 * in real-time threads without causing a deletion.
-	 *
-	 * This is not thread-safe.
-	 *
-	 * Note this mechanism scales linearly.  If a very large number of objects
-	 * are managed cleanup() will become very expensive.
-	 */
-	inline void manage(std::shared_ptr<Manageable> ptr) {
-		ptr->_maid_next = _managed;
-		_managed        = ptr;
-	}
-
-	/** Free all dead and managed objects immediately.
+	/** Delete all disposed objects immediately.
 	 *
 	 * Obviously not real-time safe, but may be called while other threads are
 	 * calling dispose().
@@ -102,12 +103,12 @@ public:
 	inline void cleanup() {
 		// Atomically get the head of the disposed list
 		Disposable* disposed;
-		while (true) {
-			disposed = _disposed.load();
-			if (_disposed.compare_exchange_weak(disposed, NULL)) {
-				break;
-			}
-		}
+		do {
+			disposed = _disposed.load(std::memory_order_relaxed);
+		} while (!_disposed.compare_exchange_weak(
+			         disposed, nullptr,
+			         std::memory_order_acquire,
+			         std::memory_order_relaxed));
 
 		// Free the disposed list
 		for (Disposable* obj = disposed; obj;) {
@@ -115,22 +116,22 @@ public:
 			delete obj;
 			obj = next;
 		}
+	}
 
-		// Free the managed list
-		std::shared_ptr<Manageable> managed = _managed;
-		_managed.reset();
-		for (std::shared_ptr<Manageable> obj = managed; obj;) {
-			const std::shared_ptr<Manageable> next = obj->_maid_next;
-			obj->_maid_next.reset();
-			obj = next;
-		}
+	/** Make a unique_ptr that will dispose its object when dropped. */
+	template<class T, class... Args>
+	managed_ptr<T> make_managed(Args&&... args) {
+		T* obj = new T(args...);
+		return std::unique_ptr<T, Disposer<T> >(obj, Disposer<T>(*this));
 	}
 
 private:
-	std::atomic<Disposable*>    _disposed;
-	std::shared_ptr<Manageable> _managed;
+	std::atomic<Disposable*> _disposed;
 };
 
+template<typename T>
+using managed_ptr = Maid::managed_ptr<T>;
+
 } // namespace Raul
 
 #endif // RAUL_MAID_HPP
diff --git a/test/maid_test.cpp b/test/maid_test.cpp
index 73e8f71..dd615ec 100644
--- a/test/maid_test.cpp
+++ b/test/maid_test.cpp
@@ -1,6 +1,6 @@
 /*
   This file is part of Raul.
-  Copyright 2007-2014 David Robillard <http://drobilla.net>
+  Copyright 2007-2017 David Robillard <http://drobilla.net>
 
   Raul 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
@@ -14,26 +14,110 @@
   along with Raul.  If not, see <http://www.gnu.org/licenses/>.
 */
 
+#include <cassert>
+#include <cstdio>
+#include <thread>
+#include <vector>
+
 #include "raul/Maid.hpp"
 
-class DisposableThing : public Raul::Maid::Disposable
-{};
+using Raul::Maid;
 
-class ManageableThing : public Raul::Maid::Manageable
-{};
+static const size_t n_threads         = 8;
+static const size_t n_junk_per_thread = 1 << 18;
 
-int
-main(int argc, char** argv)
+static std::atomic<size_t> n_junk(0);
+static std::atomic<size_t> n_finished_threads(0);
+
+class Junk : public Maid::Disposable {
+public:
+	explicit Junk(int v) : val(v) { ++n_junk; }
+	~Junk() { --n_junk; }
+
+	int val;
+};
+
+static void
+litter(Maid* maid)
 {
-	Raul::Maid maid;
+	for (size_t i = 0; i < n_junk_per_thread; ++i) {
+		Maid::managed_ptr<Junk> a = maid->make_managed<Junk>(i);
+	}
+
+	++n_finished_threads;
+}
+
+static void
+test()
+{
+	Maid maid;
+
+	// Check basic single-threaded correctness
+	{
+		assert(n_junk == 0);
+		Maid::managed_ptr<Junk> a = maid.make_managed<Junk>(1);
+		assert(n_junk == 1);
+		Maid::managed_ptr<Junk> b = maid.make_managed<Junk>(2);
+		assert(n_junk == 2);
+	}
+
+	maid.dispose(nullptr);  // Mustn't crash
+
+	// All referenes dropped, but deletion deferred
+	assert(n_junk == 2);
 
-	DisposableThing* dis = new DisposableThing();
+	// Trigger actual deletion
+	maid.cleanup();
+	assert(n_junk == 0);
+	assert(maid.empty());
+
+	// Create some threads to produce garbage
+	std::vector<std::thread> litterers;
+	for (size_t i = 0; i < n_threads; ++i) {
+		litterers.push_back(std::thread(litter, &maid));
+	}
 
-	std::shared_ptr<ManageableThing> man(new ManageableThing());
+	// Wait for some garbage to show up if necessary (unlikely)
+	size_t initial_n_junk = n_junk;
+	while (maid.empty()) {
+		std::this_thread::sleep_for(std::chrono::milliseconds(1));
+		initial_n_junk = n_junk;
+	}
 
-	maid.manage(man);
-	maid.dispose(dis);
+	printf("Starting with %zu initial bits of junk\n", initial_n_junk);
+
+	// Ensure we're actually cleaning things up concurrently
 	maid.cleanup();
+	assert(n_junk != initial_n_junk);
+
+	// Continue cleaning up as long as threads are running
+	size_t n_cleanup_calls = 1;
+	while (n_finished_threads < n_threads) {
+		maid.cleanup();
+		++n_cleanup_calls;
+	}
 
+	printf("Called cleanup %zu times\n", n_cleanup_calls);
+
+	// Join litterer threads
+	for (auto& t : litterers) {
+		t.join();
+	}
+
+	// Clean up any leftover garbage (unlikely/impossible?)
+	maid.cleanup();
+	assert(n_junk == 0);
+
+	// Allocate a new object, then let it and the Maid go out of scope
+	Maid::managed_ptr<Junk> c = maid.make_managed<Junk>(5);
+	assert(n_junk == 1);
+}
+
+int
+main(int argc, char** argv)
+{
+	assert(n_junk == 0);
+	test();
+	assert(n_junk == 0);
 	return 0;
 }
diff --git a/wscript b/wscript
index 5c63aab..f9f9b25 100644
--- a/wscript
+++ b/wscript
@@ -5,7 +5,7 @@ import waflib.Options as Options
 import waflib.extras.autowaf as autowaf
 
 # Version of this package (even if built as a child)
-RAUL_VERSION = '0.8.6'
+RAUL_VERSION = '0.8.7'
 
 # Library version (UNIX style major, minor, micro)
 # major increment <=> incompatible changes