Practical Testing: 27 - Fixing things...

Previously on "Practical Testing"... To deal with some specific usage scenarios of a piece of general purpose code I'm in the process of implementing a timer wheel that matches the interface to the timer queue that I previously developed in this series of articles. Last time I left myself with a failing test. The problem is that setting a new timer on the timer wheel sets a timer that's relative to the time that timer wheel thinks is 'now' and the timer wheel's view of the current time could be slightly behind reality; see the previous entry for a diagram that explains the problem.

This kind of problem wouldn't exist if the timer wheel was operating on a hard real time system where each tick of the hardware clock caused the timer wheel to 'rotate' and process timers that have expired. Unfortunately since we just have a normal thread to process timers the wheel can get slightly behind reality. There are two ways to solve this problem and both have drawbacks. The first is to cause the wheel to be processed before any new timer is set, this would mean that the wheel is always up to date and therefore the timer insertion would be correct. Unfortunately this leads to timers being handled on any thread that calls SetTimer() which may not be ideal for users of the wheel, it also means that setting a timer is no longer O(1)... The second approach is to simply set the timer based on the current time and allow for the difference between the current time and the timer wheel's view of the current time when the timer is inserted into the wheel. The disadvantage with this approach is that the maximum timeout that can be set will fluctuate around the lag between 'now' and the timer wheel's view of 'now'. You can work around this fluctuation by making the wheel have a maximum timeout that is larger than the actual maximum timeout that you wish to set and the expected lag...

I've taken the second approach as non O(1) timer setting and 'random thread timer dispatch' are not desirable qualities for the usage scenarios that I'm currently targeting. This means that the timer wheel now queries the tick count provider when you call SetTimer() but it's easy to adjust the tests for this due to the test traits that I introduced a while back.

Now that SetTimer() works correctly we can move on to implementing the remaining functions. Unfortunately though, before we do that we need to deal with a memory leak bug in the CCallbackTimerQueueBase class which the tests can't detect and which I missed due to not running BoundsChecker after each set of changes... The leak was introduced when I switched from using the std::multimap to using a std::deque back in part 21. Unfortunately I missed out a couple of delete statements to clear up the new structure that we allocate to store in the std::deque when we set timers. This just goes to show that it doesn't matter how many tests you have and how good your coverage is, it's never enough to prove that the code is without bugs. Running BoundsChecker showed the bug quite clearly but it's a pity that it needs to be a separate stage of testing. Instrumenting memory allocation within the test would help and is something that I might look into... Anyway, the fixes are to add a loop which cleans up the allocated memory in the queue's destructor and to clean up blocks of timers as they expire in HandleTimeouts().

The code can be found here and the previous rules apply.

Leave a comment