Conditional Critical Regions: Implementing (or not) in C++

Two notes. First I'm using embedded gists for the code examples. This may not work in RSS. Secondly, I thought this would be two parts but it's getting long so it's going to be three.

First let's set the stage. This code is written with C++11 in mind, I assume lambda support. I also assume C++11 type mutex/condition_variable support, but since I didn't actually have that I wrote my own, so in this code their not explicitly in the std namespace. You should be able to to use std ones or boost ones or what have you by dropping in the appropriate using declarations. I also whipped up a simple scope guard doodad.

	struct at_scope_exit : private std::function<void()> {
	at_scope_exit(std::function<void()> do_this) : std::function<void()>(do_this)
	{}
	~at_scope_exit()
	{
	(*this)();
	}
	};

view raw gistfile1.cpp hosted with ❤ by GitHub

Before I forget, you probably should have read the last post. So let's start with the simple versions of these, the with r do and the with r when Condition do.

	class resource {
	mutex m_;
	condition_variable cv_;
	public:
	resource() {}
	void with_do(std::function<void()> body)
	{
	m_.lock();
	at_scope_exit u( [&]() { cv_.notify_all(); m_.unlock(); } );
	body();
	}
	void with_when_do(std::function<bool()> cond, std::function<void()> body)
	{
	with_do( [&]() {
	while( !cond() )
	{
	cv_.wait(m_);
	}
	body(); });
	}
	private:
	resource(const resource&);
	resource& operator=(resource);
	};

view raw gistfile1.cpp hosted with ❤ by GitHub

That's actually not bad at all, no? Lambdas and std::function make this all a bit smoother than the C++ of yore would have. Ok, let's talk about problems. What happens when we nest? Actually, not at all what I expected! This blog post might turn out to be about compiler bugs.

 

	struct counter : resource { int c; } r;
	r.with_do([&]()
	{
	r.c += 1;
	r.with_do([&]() { r.c += 1; });
	});

view raw gistfile1.cpp hosted with ❤ by GitHub

So what happens when we compile this? We get a compiler error (I'm using VS2010): error C2872: ' ?? A0xc6bc40fc' : ambiguous symbol. Oops. Your C++ is showing. Intellisense has a better message, telling me that it's an "Invalid reference to a outer-scope local variable in a lambda body". My first instinct was to believe the compiler error and try and disambiguate it:

	r.with_do([&]()
	{
	r.c += 1;
	counter& shadow = r;
	r.with_do([&]() { shadow.c += 1; });
	});

view raw gistfile1.cpp hosted with ❤ by GitHub

I should have listened to Intellisense.


fatal error C1001: An internal error has occurred in the compiler.
1>  (compiler file 'msc1.cpp', line 1420)
1>   To work around this problem, try simplifying or changing the program near the locations listed above.
1>  Please choose the Technical Support command on the Visual C++ 
1>   Help menu, or open the Technical Support help file for more information


I broke my compiler :(. Anyway, I suppose this is what happens when we try to point out a specific problem with a small example, we find new, different problems. We can solve this problem, and demonstrate what I really wanted to.

	auto incr = [&]() { r.c += 1; };
	r.with_do([&]()
	{
	r.c += 1;
	r.with_do(incr);
	});

view raw gistfile1.cpp hosted with ❤ by GitHub

Take that, lambda nesting! So what is the problem, I was trying to demonstrate? Well it's not necessarily safe for a mutex to be locked multiple times on the same thread, so if we want to support nesting of with blocks on the same resource we'd better make sure that's a recursive_mutex. Simple enough. Now, let's get to the real meat of the matter, the await statement.

	class resource {
	recursive_mutex m_;
	condition_variable cv_;
	public:
	resource() {}
	void with_do(std::function<void()> body)
	{
	m_.lock();
	at_scope_exit u( [&]() { cv_.notify_all(); m_.unlock(); } );
	body();
	}
	void with_when_do(std::function<bool()> cond, std::function<void()> body)
	{
	with_do( [&]() {
	while( !cond() )
	{
	cv_.wait(m_);
	}
	body(); });
	}
	void await(std::function<bool()> cond)
	{
	while(!cond())
	{
	cv_.wait(m_);
	}
	}
	private:
	resource(const resource&);
	resource& operator=(resource);
	};

view raw gistfile1.txt hosted with ❤ by GitHub

So above is the naive implementation of await. So what's wrong with it?

r.await( [&r]() { return r.c != 0; });

view raw gistfile1.cpp hosted with ❤ by GitHub

Oops. It's not legal to wait if we don't have the lock. Well, that's fine, we're using a recursive_mutex now, we can fix this.

	void await(std::function<bool()> cond)
	{
	with_when_do(cond, []() { });
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

Warning: notation abuse. There's still a problem here. It's unsatisfying from a correctness standpoint in at least two scenarios. Before your bug would do something weird, not it has a defined semantic, but it probably wasn't what you wanted. And now you can write this:

	struct counter : resource { int c; } r;
	counter r2;
	std::function<bool(int&)> is7 = [](int& x) -> bool { return x == 7; };
	r2.with_do([&]() {
	if( r2.c != 7 )
	{
	std::cout << "Waiting for c to become 7.\n";
	}
	r.await(std::bind(is7, std::ref(r2.c))); // r != r2
	std::cout << "c is 7!\n";
	});

view raw gistfile1.cpp hosted with ❤ by GitHub

The limitations of nesting lambdas is really making this uglier than I intended. What do we want? We want a version of await that we can only call in the right circumstances. We can of course check these things at runtime, and throw exceptions, but I'd much rather await not even mention the resource, in other words be impossible to be incorrect. Of course if we make await a free function we can do that, but then we're back to runtime detection in the case when we're not inside a block at all. This is the real problem I want to solve, and we'll look at some approaches next time.