I have a function which makes use of memory on the heap and it will go badly wrong if it is called before another instance of the same function has completed. How can I prevent this from happening at compile time?
-
28Don't write a recursive call? How hard can it be to avoid doing this?– anonFeb 4, 2010 at 15:51
-
10The title of the question seems misleading... you do not intend on the function not being called recursively, but rather concurrently. If I understood the text of the question, that is. If so, please edit the question title.– David Rodríguez - dribeasFeb 4, 2010 at 15:51
-
10Just for clarity: in your context you're talking about reenterability, not recursion.– Igor KorkhovFeb 4, 2010 at 15:54
-
2@Neil: Assume you call some third party module, which could, theoretically call you, your function we be called recursively without you explicitly doing a recursive call.– falstroFeb 4, 2010 at 15:55
-
5@j coe The solution (assuming you are in some callback scenario) is to document the fact that the function must not be called from the callback. If users then do so, that is their problem. You cannot prevent all possible bad use cases, and it is simply not worth trying.– anonFeb 4, 2010 at 15:58
12 Answers
Detecting recursion with any amount determinism of at compile-time is going to be quite difficult. Some static code analysis tools might be able to do it, but even then you can get in to run-time scenarios involving threads that code analyzers won't be able to detect.
You need to detect recursion at run-time. Fundamentally, it's very simple to do this:
bool MyFnSimple()
{
static bool entered = false;
if( entered )
{
cout << "Re-entered function!" << endl;
return false;
}
entered = true;
// ...
entered = false;
return true;
}
The biggest problem with this, of course, is it is not thread safe. There are a couple of ways to make it thread safe, the simplest being to use a critical section and block the second entry until the first has left. Windows code (no error handling included):
bool MyFnCritSecBlocking()
{
static HANDLE cs = CreateMutex(0, 0, 0);
WaitForSingleObject(cs, INFINITE);
// ... do stuff
ReleaseMutex(cs);
return true;
}
If you want the function to return an error when a function has been reentered, you can first test the critsec before grabbing it:
bool MyFnCritSecNonBlocking()
{
static HANDLE cs = CreateMutex(0, 0, 0);
DWORD ret = WaitForSingleObject(cs, 0);
if( WAIT_TIMEOUT == ret )
return false; // someone's already in here
// ... do stuff
ReleaseMutex(cs);
return true;
}
There are probably an infinite ways to skin this cat other than the use of static bools and critsecs. One that comes to mind is a combination of testing a local value with one of the Interlocked functions in Windows:
bool MyFnInterlocked()
{
static LONG volatile entered = 0;
LONG ret = InterlockedCompareExchange(&entered, 1, 0);
if( ret == 1 )
return false; // someone's already in here
// ... do stuff
InterlockedExchange(&entered, 0);
return false;
}
And, of course, you have to think about exception safety and deadlocks. You don't want a failure in your function to leave it un-enterable by any code. You can wrap any of the constructs above in RAII in order to ensure the release of a lock when an exception or early exit occurs in your function.
UPDATE:
After readong comments I realized I could have included code that illustrates how to implement an RAII solution, since any real code you write is going to use RAII to handle errors. Here is a simple RAII implementation that also illustrates what happens at runtime when things go wrong:
#include <windows.h>
#include <cstdlib>
#include <stdexcept>
#include <iostream>
class CritSecLock
{
public:
CritSecLock(HANDLE cs) : cs_(cs)
{
DWORD ret = WaitForSingleObject(cs_, INFINITE);
if( ret != WAIT_OBJECT_0 )
throw std::runtime_error("Unable To Acquire Mutex");
std::cout << "Locked" << std::endl;
}
~CritSecLock()
{
std::cout << "Unlocked" << std::endl;
ReleaseMutex(cs_);
}
private:
HANDLE cs_;
};
bool MyFnPrimitiveRAII()
{
static HANDLE cs = CreateMutex(0, 0, 0);
try
{
CritSecLock lock(cs);
// ... do stuff
throw std::runtime_error("kerflewy!");
return true;
}
catch(...)
{
// something went wrong
// either with the CritSecLock instantiation
// or with the 'do stuff' code
std::cout << "ErrorDetected" << std::endl;
return false;
}
}
int main()
{
MyFnPrimitiveRAII();
return 0;
}
-
3I find almost shocking that you mention RAII as a second thought and it does not appear anywhere in the code :( Feb 4, 2010 at 17:43
-
1@Matthieu: I was trying to illustrate the principles behind detecting re-entry, not RAII. You do not need RAII in order to implement a solution to detect re-entry, although in real code you would use RAII or some other construct for error and exception handling just as you would do more rigorous checking of return values etc. But one principle at a time. I might also point out that even though I was the only one who even mentioned RAII, you didn't seem to mind that nobody else had it in their code. Feb 4, 2010 at 17:54
-
That is to say, RAII does not enable the idioms I demonstrated for detecting re-entrancy. Feb 4, 2010 at 17:54
-
@John: I did mind, but that you mentioned it and did not applied it felt strange, I'm usually looking forward to your answers whenever I encounter them and felt a bit let down there :) Feb 5, 2010 at 7:24
-
@Matthieu: After re-reading this and your comments the next day I realize you are right. I should have added code to illustrate how to implement RAII. The natural arc of my post seems to lead there. Edited. Cheers. Feb 5, 2010 at 13:45
Your question is unclear, do you mean in a single-threaded scenario (recursion or mutual recursion) or a multi-threaded scenario (re-entrancy)?
In a multi-threaded scenario, there is no way to prevent this at compile time, since the compiler has no knoweldge of threads.
In a single-threaded scenario, I don't know of a way to prevent a recursive call at compile time other than using your brain. As long as you can analyze the control flow and prove that your function doesn't call itself and that none of the functions it calls will call it back, you should be safe.
-
3+1 for the brain! "There is one solution at compile time - to think". Feb 4, 2010 at 15:59
You cannot do it at compile-time without static analysis. Here is an exception-safe recursive assertion:
#include <cassert>
class simple_lock
{
public:
simple_lock(bool& pLock):
mLock(pLock)
{
assert(!mLock && "recursive call");
mLock = true;
}
~simple_lock(void)
{
mLock = false;
}
private:
simple_lock(const simple_lock&);
simple_lock& operator=(const simple_lock&);
bool& mLock;
};
#define ASSERT_RECURSION static bool _lockFlag = false; \
simple_lock _lock(_lockFlag)
void foo(void)
{
ASSERT_RECURSION;
foo();
}
int main(void)
{
foo();
//foo();
}
Without some sort of static analyser, you cannot do this at compile time. However, a simple run-time check for this will work:
Note: for preventing multi-threaded concurrent but non-recursive invocation you need something a bit more robust.
void myFunc() {
static int locked = 0;
if (locked++)
{
printf("recursion detected\n!");
}
....
locked--;
}
Note: you should place this function in a .c
or .cc
file, not in a header.
If you do have multi-threading, I suggest you use pthread locks to control access to the shared variables it references.
-
+1. @j coe, it is not possible to prevent the calling itself at compile time. Write defensive code in the function itself as this answer suggests. Feb 4, 2010 at 15:53
-
@Daniel In which case, the correct answer is "you can't do that"– anonFeb 4, 2010 at 15:55
That problem is undecidable in any turing complete language. I can't prove it though. I just know.
-
9Want a proof? If it were decidable, then you could write a function
void f() {if (!recurses(f)) f();}
which recurses if and only if it doesn't recurse. Feb 4, 2010 at 16:07 -
The function call stack is created at runtime, At compile time you can only check if your function is recursive itself or not i.e does it calls itself?.
c++-faq-lite has some nice advice in similar cases: write a comment that you expect problems when doing such a thing:
// We'll fire you if you try recursion here
I haven't looked whether the advice was also for recursion
Your best bet is to use a mutex. You could use a semaphore, but personally I prefer mutexs here. This will allow you to prevent it from being called by other threads.
* edit *
Ah you want it to happen at compile time?
You're on a hiding to nothing there my friend.
-
Bit of a typo there. Well spotted. I had meant "you don't want it to happen at runtime?" but for some reason my fingers typed "compile".– ChrisBDFeb 5, 2010 at 7:40
You can't do it at compile-time, you'd need to follow the complete control flow of the whole application to accomplish this (what if the function calls another function which invokes another function which invoes another function which in turn invokes the original function again ...).
Do it at think time instead. Add a huge comment to the function's documentation. Plus maybe one of the runtime solutions presented by the other responses - for debug builds.
Just to add another one: use a static mutex to protect the function body (boost's scoped_lock would greatly simplify it).
This compiles
#include <stdio.h>
int testFunc() {
#define testFunc
printf("Ok\n");
}
#undef testFunc
int main() { testFunc(); }
This doesn't
#include <stdio.h>
int testFunc() {
#define testFunc
printf("Ok\n");
testFunc();
}
#undef testFunc
int main() { testFunc(); }
Error: test.c:7: error: expected expression before ‘)’ token
It works on multi-function recursion too:
#include <stdio.h>
int testFunc1() {
#define testFunc1
printf("1\n");
testFunc2();
}
int testFunc2() {
#define testFunc2
printf("2\n");
//uncomment to cause error: `test.c:13: error: expected expression before ‘)’ token`
//testFunc1();
}
#undef testFunc1
#undef testFunc2
int main() { testFunc1(); }
-
Apart from being ugly: it does not work with a 3rd party module to which you pass a callback function... Feb 4, 2010 at 17:46
Here is my solution for single threaded reentry prevention using RAII:
struct NestingTracker
{
NestingTracker(uint32_t &cnt) : _cnt(cnt) { ++_cnt; }
~NestingTracker() { assert(_cnt); --_cnt; }
uint32_t& _cnt;
};
#define NO_REENTRY(x) \
static uint32_t cur_nesting = 0; \
if (cur_nesting) \
return (x); \
NestingTracker nesting_track(cur_nesting)
use as
void f(...)
{
NO_REENTRY(void());
...
}
The only way to do this is to make sure that client code has no way to reference the function you don't want to be reentered. This can be accomplished by making the function static
or in an anonymous namespace or some similar technique.
Unfortunately, in order for this to be certain of working, all functions leading from main
to your function must also be declared in this fashion, and that situation becomes really difficult to manage really quickly.
And, while C++ technically says that calls to main
from your code are undefined and you shouldn't do them, most implementations will happily recurse main
for you. And main
has to have a name that is accessible from anywhere else in your program.
So, in reality it isn't really possible.
And I expected you wanted the compiler to give you an error when you tried anyway instead of just making sure there simple wasn't any possible way you could do it.