Long before smartphones became popular, my cell phone has always been furfilling one important function: waking me up in the morning. Some phones handled this tasks better than the others, but they were all invariably infallible. The Nokia 6600 treated the alarm clock task especially seriously: if the alarm was set, it would go off, no matter what. If the phone was switched off, it would turn itself on and boot up just to play the alarm tune. After the alarm was dismissed, the phone would promptly switch itself off again.
The first phone to fail the alarm clock task was surprisingly a smartphone: the Android-powered Samsung Galaxy 3. I would set the alarm, and it would simply fail to go off in the morning. What made the issue even more baffling was that my sister had exactly the same model, and she reported no problems with the alarm clock at all. Mine was behaving oddly: sometimes the alarm would work, other times it would fail, seemingly at random. Eventually I figured out that the alarm had the best chance of working if I reset it every evening.
As I found out later, the problem had been related to the way memory management is handled in Android. If the device runs out of free memory, the system lists all the running Apps, and decides which one of them should be terminated to reclaim its memory. It would not be a problem, if it wasn't for a little fact: the alarm clock IS an App. Each time the phone runs out of memory, there is a small chance that the system will stop the alarm clock. Once stopped, the alarm clock will always fail to go off until the user re-runs the application by opening the alarm clock settings. My sister did not use as many memory-intensive applications as I did, and that is why she has never encountered this problem.
With the older phones, the alarm clock has always been a part of the operating system. Other than ensuring faultlessness of the alarm functionality, it has also made it possible to have impressive extra functionality, like the Nokia's boot-up-to-play-the-alarm thing.
Unfortunately, ever since the smartphone revolution, everything just has to be an App, and as this example shows, it's not always a good thing.
Setup
Practically all of my recent projects, both for school and otherwise, are done in high level programming languages, like Java or Python. As such I've been missing out on many fun low-level features, such as: manual memory management, pointer arithmetic, lean standard library, and of course, debugging adventures! Therefore, given the option to choose the programming language for my graphs and networks project, I immediately decided to go for the good, old C.
The project is a relatively simple application, that visually demonstrates some graph coloring algorithms, using Allegro 5 for graphics. Since the design goals include reading a lot of data from configuration files, I've also included libconfig, to avoid having to parse the files by myself. One of those files contains an adjacency matrix of unknown size, which I'm storing in a dynamically allocated char array. To avoid having to deal with dynamic two-dimensional arrays, I've implemented it as a 1-D array, with indexing done like this:
char elem = node_matrix[x + (matrix_width*y)];
The pointer to this array is stored in an AppConfig structure along with some other program settings. At this point all was well, and the development was proceeding just fine.
The Hunt
The problem appeared right after adding some code to draw the links between graph vertices: the connections were all wrong. After playing with the drawing code for a few minutes, and finding nothing wrong with it, I've added a function call to print out the adjacency matrix just before drawing the links. Lo, and behold: the matrix was garbled. I've added another call to print the matrix just after reading it from file, and at that point it was fine. By moving those two calls around in the code, I've eventually found a single line that caused the matrix to garble:
config_read_file(cfg, path);
After commenting out the line, the matrix was fine at both points. Putting it back caused the matrix to appear garbled again. Could libconfig be somehow corrupting my program's memory? A quick google search found no mention of any memory problems with the library. As a quick test, I've replaced the offending line with the following:
int *test = malloc (90000 * sizeof(int));
memset(test, 9, 90000 * sizeof(int));
It allocated around 350 kB of memory and filled it all with nines. As I suspected, with this code in place, my matrix had a few rows replaced with all nines. At that point I was certain that my matrix was being stored in an un-allocated memory. How could this happen? I took a quick look at the malloc call that was allocating memory for my matrix, and it looked fine:
ac->node_matrix = malloc( matrix_width * matrix_width * sizeof(char) ); // square matrix
I took another look at the print function, and the indexing was the same as for the code that was setting the values. I took yet another look at the code setting the values, and THEN I saw it!
ac->node_matrix[x + (ac->screen_width * y)] = (char) result;
A true facepalm moment: I've been using the screen width instead of the matrix width for indexing! I suppose that's one argument against storing all your variables in one structure.
Conclusion
The first row was always written in the correct memory, but all the other rows were written wherever the width of the application window caused them to be written, and it was most certainly outside of the allocated memory block. Since the print function and the set function used the same copy-pasted indexing, the array was consistently written to, and read from the wrong place. The values written in the unallocated memory stayed there, until some other piece of code claimed that particular address. In this case, it was the libconfig call, but it could've been anything. In C, writing values outside of the array does not generate an array-out-of-bounds exception. The code 'just works', until suddenly it doesn't. Debugging is so much fun!
