A wise man once said:
Anything that can possibly go wrong, does
— Murphy
Some programmers are wise men, thus a wise programmer once said:
A good programmer is someone who looks both ways before crossing a one-way street.
— Doug Linder
In a perfect world, things work as expected and you may think that it is a good idea to keep consuming things until the end. So the following pattern is found all over in every code base:
Java
for (;;) {
// something
}
C
while (1) {
// something
}
BASIC
Want to see proof?
Search github for while(true) and check out the number of matches:
https://github.com/search?q=while+true&type=Code
Never use possibly infinite loops
There is a very interesting discussion in computer science around the topic of the
“Halting Problem”. The essence of the halting problem as proved by
Alan Turing a long time ago is the fact that it is really undecidable. While humans can quickly assess that the following program will never stop:
… and that the following program will always stop:
… computers cannot decide on such things, and even very experienced humans might not immediately be able to do so when looking at a more complex algorithm.
Learning by doing
In jOOQ, we have recently learned about the halting problem the hard way: By doing.
Before fixing
issue #3696, we worked around a bug (or flaw) in SQL Server’s JDBC driver. The bug resulted in
SQLException
chains not being reported correctly, e.g. when the following trigger raises several errors:
CREATE TRIGGER Employee_Upd_2 ON EMPLOYEE FOR UPDATE
AS
BEGIN
Raiserror('Employee_Upd_2 Trigger called...',16,-1)
Raiserror('Employee_Upd_2 Trigger called...1',16,-1)
Raiserror('Employee_Upd_2 Trigger called...2',16,-1)
Raiserror('Employee_Upd_2 Trigger called...3',16,-1)
Raiserror('Employee_Upd_2 Trigger called...4',16,-1)
Raiserror('Employee_Upd_2 Trigger called...5',16,-1)
END
GO
So, we explicitly consumed those
SQLExceptions
, such that jOOQ users got the same behaviour for all databases:
consumeLoop: for (;;)
try {
if (!stmt.getMoreResults() &&
stmt.getUpdateCount() == -1)
break consumeLoop;
}
catch (SQLException e) {
previous.setNextException(e);
previous = e;
}
This has worked for most of our customers, as the chain of exceptions thus reported is
probably finite, and also
probably rather small. Even the trigger example above is not a real-world one, so the number of actual errors reported might be between 1-5.
Did I just say …
“probably” ?
As our initial wise men said: The number
might be between 1-5. But it
might just as well be 1000. Or 1000000. Or worse, infinite. As in the case of
issue #3696, when a customer used jOOQ with SQL Azure. So, in a perfect world, there cannot be an infinite number of
SQLException
reported, but this isn’t a perfect world and SQL Azure also had a bug (probably still does), which reported the same error again and again, eventually leading to an
OutOfMemoryError
, as jOOQ created a huge
SQLException
chain, which is probably better than looping infinitely. At least the exception was easy to detect and work around. If the loop ran infinitely, the server might have been completely blocked for all users of our customer.
The fix is now essentially this one:
consumeLoop: for (int i = 0; i < 256; i++)
try {
if (!stmt.getMoreResults() &&
stmt.getUpdateCount() == -1)
break consumeLoop;
}
catch (SQLException e) {
previous.setNextException(e);
previous = e;
}
True to the popular saying:
640 KB ought to be enough for anybody
The only exception
So as we’ve seen before, this embarassing example shows that
anything that can possibly go wrong, does. In the context of possibly ininite loops, beware that this kind of bug will take entire servers down.
The Jet Propulsion Laboratory at the California Institute of Technology has made this
an essential rule for their coding standards:
Rule 3 (loop bounds)
All loops shall have a statically determinable upper-bound on the maximum number of loop iterations. It shall be possible for a static compliance checking tool to affirm the existence of the bound. An exception is allowed for the use of a single non-terminating loop per task or thread where requests are received and processed. Such a server loop shall be annotated with the C comment: /* @non-terminating@ */.
So, apart from very few exceptions, you should never expose your code to the risk of infinite loops by not providing upper bounds to loop iterations (the same can be said about recursion, btw.)
Conclusion
Go over your code base today and look for any possible
while (true)
,
for (;;)
,
do {} while (true);
and other statements. Review those statements closely and see if they can halt – e.g. using
break
, or
throw
, or
return
, or
continue
(an outer loop).
Chances are, that you or someone before you who wrote that code was as naive as we were, believing that…
… oh come on, this will never happen
Because, you know what happens when you think that nothing will happen.
Like this:
Like Loading...
Every loop stops. Even infinite loops stop after a while.
Go tell Alan ;)
Or a RegExp breaking a server.
Haha, true! I just today reported a case of such a regex to Eclipse: https://bugs.eclipse.org/bugs/show_bug.cgi?id=457685
Almost got hit by a reversing truck on a one-way street. Bless looking both ways.