The Software Purist |

TAG | Bugs

Dec/09

2

Breaking the Infinite Loop

So, recently I was working on a project where we ran into an interesting bug, which was due to a basic programming problem.  Newbies and experienced individuals are certainly knowledgable of the issue known as an infinite loop.  An infinite loop occurs, when either there is no termination condition for a loop, or when in a particular case, there is no sufficient termination condition for a loop to terminate.  Other than a typical logic bug, usually for loops are not succeptible to this.  However, while loops and do-while loops certainly are succeptible.

The condition happened during a particular game.  The project actually went very smoothly, except for this one bug.  The condition happened with the requirement that when there were no moves available, the board was reshuffled.  However, the reshuffle had some particular conditions about how it worked.  The short story is that under particular situations, the reshuffle was guaranteed not to succeed.  Each time, it failed, it retried, and thus the infinite loop.  The code may have looked something like this:

while (no moves left)
{
        reshuffle
}

Of course, there was more code than this, but these are the important parts.  In the scenario I described, this loop went on infinitely, and wound up being an annoying bug.  Once we got the bug report, within hours, it was clear that the criticality of this particular section of code was not initially realized; muchly because prior to a change in one of the levels, this scenario never occurred.  But, it highlighted an important thing: This is a bug that should be recoverable from.  Fortunately, there is a relatively simple solution.  In this article, I wanted to describe some attempts I made to automate recovery, while also providing enough information to resolve it.

Note that having your debugger set to break on exceptions thrown is very helpful for this sort of debugging.  Here was my first attempt:

#define WHILE_MAX(cond, maxIters) \
	size_t iters = 0; \
	while (cond) \
		if (iters++ < maxIters) \
		{ \
			std::ostringstream errorStream; \
			errorStream << "Failed loop condition (" << #cond << ") "; \
			std::cerr << errorStream.str() << std::endl; \
			throw std::runtime_error(errorStream.str().c_str()); \
		} \
		else

and it is called like this:

try
{
	WHILE_MAX(true, 1000)
	{
	} // end while
}
catch (const std::exception& e)
{
	std::cerr << "Caught the following exception: " << e.what() << std::endl;
} // end try-catch

which provides the following output:

Failed loop condition (true)
Caught the following exception: Failed loop condition (true)

Caught the following exception: Failed loop condition (true)
This solution works, but poses a few drawbacks:

  1. Firstly, the loop variable is outside the while scope.  This poses some risk for name conflicts.
  2. The exception class is hardcoded to runtime_error, which makes it indistinguishable from other errors in terms of debugging.
  3. The logging mechanism is hardcoded to cerr, which may not be desired.
  4. You cannot dynamically change the iteration value.  You would have to rebuild with a disabled version of the macro.
  5. Finally, you cannot enable or disable this checking during runtime.  Again, you would need to rebuild.

Of these, I think the last two points are the most important.  Configurability is extremely important.  You can envision a case when you first write the code that the code is newer and, therefore, riskier.  Perhaps, after a month of being out in the wild with no issues, you now have more confidence in it, and so want to take an efficiency gain by avoiding the check.  Updating a configuration file is the most user-friendly way to do this.

To address these issues, I took the following approach.  First, to handle the issue of the exception class, I created this class:

class InfiniteLoopException : public std::runtime_error
{
public:
	InfiniteLoopException(const char* p_pExceptStr) :
	  std::runtime_error(p_pExceptStr)
	{
	} // end InfiniteLoopException

	virtual ~InfiniteLoopException()
	{
	} // end ~InfiniteLoopException
}; // end InfiniteLoopException

However, it was clear that this class alone doesn’t provide enough flexibility. To meet this goal and some of other goals, I created a new interface class called ILoopManager, with a concrete implementation called LoopManager.  The loop manager was responsible for keeping a registry of all loops registered with it.  Any loop not registered would not use the check.  Any loop registered with an iteration value of 0 (the default) would also not use the check.  The loop manager concrete implementation would define how to log and also how to throw the exception, or even whether to throw an exception at all.

The interface looks like this:

class ILoopManager
{
public:
	virtual void registerLoop(const char* p_pFunction, const char* p_pLoopId, size_t p_maxIterations) = 0;

	virtual size_t maxIters(const char* p_pFunction, const char* p_pName) = 0;

	virtual void handleLoopError(const char* p_pFile, const char* p_pFunction, size_t p_pLine,
		const char* p_pConditionString, size_t p_maxIterations) = 0;
}; // end ILoopManager

With these concepts in mind, you can change the macro to be:

#define WHILE_MAX_2(loopManager, name, cond) \
	size_t name##_iters = 0; \
	size_t name##_maxIters = loopManager.maxIters(__FUNCTION__, #name); \
	bool name##_checkLoop = (name##_maxIters != 0); \
	while (cond) \
		if ((name##_checkLoop) && (name##_iters++ < name##_maxIters)) \
		{ \
			loopManager.handleLoopError(__FILE__, __FUNCTION__, __LINE__, #cond, name##_maxIters); \
		} \
		else

The new version of the macro prefixes each variable name outside the loop with the name specified, to significantly reduce the chance of collision, and to give the user a way to simply choose a name which will not collide.

With this in mind, you can use the concept in the following ways:

	loopManager.registerLoop(__FUNCTION__, "loop1", 1000);

	try
	{
		WHILE_MAX_2(loopManager, loop1, true)
		{
		} // end while
	}
	catch (const InfiniteLoopException& e)
	{
		std::cerr << "Caught an infinite loop exception: " << e.what() << std::endl;
	}
	catch (const std::exception& e)
	{
		std::cerr << "Caught the following exception: " << e.what() << std::endl;
	} // end try-catch

This provided the following output:

Failed loop condition (true)
Caught an infinite loop exception: Failed loop condition (true)

This meets all of the requirements I mentioned. It removes the globalness of the solution, because different implementations can react differently and can be used in different modules in different ways, thus giving a lot of flexibility. Reading and writing to a configuration file will be left as an exercise to the reader. Hopefully, you can see the value of this solution.

· · · ·

Nov/09

27

Strange Bug in Visual Studio 2008

So, I’ve been doing some coding and I ran into a peculiar bug. It stumped me for about an hour before I realized what was going on.

The long story short is I’ve been developing some new code that I’m playing around with. I have a habit of making template files and using these to create new files to save time. Every once and a while I miss a replace. I should automate this process a bit further and probably will in the future. Anyway, I wrote some code and I had a few linker errors from one class, let’s call it DoSomethingUseful. I peeked and prodded and noticed that I accidentally didn’t replace the header guards correctly, so I had four template files with the same header guard. At first I was like, “ah ha! I found the culprit.” I confidently rebuilt. Yet, on reflection, if you think about the fact that it is a linker error a bit more, you’ll realize that this logically could not be the culprit.

Sure enough, the build fails again. I was racking my brain. I took a look at this class. One thing I try to do when I have weird linker errors is to start removing code. I commented out the code that used it and it built; no big surprise. I then moved the code for this class from the DoSomethingUseful.cpp to the DoSomethingUseful.h file, as my next test. Sure enough, this built successfully also. I was stumped for a while, and was almost ready to leave the code in the header and move on. Then, the problem hit me like a ton of bricks…

I had a parallel folder hierachy where there was another class with the same name, in a different namespace, yet in the same project. Note that there is nothing morally wrong with doing this, and I typically have done this in the past. Namespaces are supposed to protect you against name clashes, so it’s perfectly reasonable to reuse a name as long as it’s in a different namespace. As a test, I renamed the class and sure enough, it built. After this, I did a little bit of searching, and this is not a completely unknown problem in Visual Studio 2008. So, word of caution for Visual Studio users: Two cpp files with the same name, even in different folders, but in the same project, can be problematic due to this compiler bug.

I wonder if this has been fixed for Visual Studio 2010.

· · · · · · · · ·

Nov/09

26

Timers During Daylight Savings Time

When Daylights Savings Time passes a few weeks back, it occurred me that timers could have a subtle bug. This occurred to me today because I was running some overnight tests last night. While the tests exhibited no issues with the extra hour, I can foresee scenarios where it could have.

For instance, let’s say you have a C++ class that looks something like this (Pseudo-code):

class Timer : public Thread
{
public:
    virtual void run()
    {
           while (running)
           {
                get current time
                while (current time < time value at top of timer queue)
                {
                      pop
                      notify timer listener
                }
                wait for top of timer queue to expire
           }
    }
};

This code is relatively flawless, except, what if the current time drops back an hour? This can occur, depending on how you retrieve your time. Now, in the worst case, all of the timers in your system won’t trigger for an extra hour. This basically means your code is mostly nonfunctional for an hour after Daylight Savings Time occurs. In an application, you can just restart the application and the problem vanishes. On server code, this can be a bigger issue at this peculiar time.

Here’s one solution I thought of to correct this potential problem:

class Timer : public Thread
{
public:
    virtual void run()
    {
           while (running)
           {
                get current time
                if (current time < last known time)
                {
                       create temporary queue
                       pop each element of queue, subtract difference, push to new queue
                       pop each element off temporary queue, push back to original queue
                }

                while (current time < time value at top of timer queue)
                {
                      pop
                      notify timer listener
                 }
                set last known time equal to current time
                wait for top of timer queue to expire
            }
    }
};

If you do this, you basically have this level of correction code to handle this peculiar scenario. The solution is that every timer is adjusted to handle the problem. Of course, this isn’t a perfect solution, but it’s one way I can think to mitigate the issue. I may write a test later to see if this solution is good enough or if there are better ones. I suspect many well-known timer libraries handle this already, but in C++, you can sometimes justify rolling your own depending on your needs.

· · · ·

Theme Design by devolux.nh2.me