Manual dynamic memory management might make debugging easier

Published on Tue 08 January 2013. Filed under . Tags .

Dynamic memory allocation has an important use in real world programs: data like input lines has no fixed size, so robust programs shouldn’t allocate fixed buffers for it. Writing a homework program I found another reason for it: it leads to more errors that tools like Valgrind can detect.

Using static allocation for such programs has its advantages: all size limits are specified, so it won’t cause errors like truncating input; it’s easy to declare static arrays of structures in C; it’s faster and doesn’t require many additional lines of code for deallocation of the structure nor thinking where to free the objects.

However, this approach makes debugging harder: static memory is valid for the whole run of the program. Tools like Valgrind’s Memcheck won’t complain about uninitialized values being read or memory being accessed after being freed. (There are problems that occur only with dynamic memory, like double frees or frees of unallocated memory, I don’t consider them as common or as hard as the issues that don’t depend on memory allocation style.)

(In real world programs another reason to use dynamic memory is that some of it might be returned to the operating system before the program finishes. This would be useful in long-lived processes doing big allocations for quick computations, although it won’t occur in all cases due to the way how malloc-style routines work.)

The program that motivated me to write this article implemented monotone polygon triangulation using the DCEL structure to represent the polygon. (This structure is not needed for this algorithm. Using it leads to having more bugs, therefore it is educationally useful.) The code managed half-edges to run an algorithm designed for vertices. Storing triangulated parts of the polygon was not needed, so they were deallocated immediately after printing their representation. This resulted in a use-after-free error detected by Valgrind, fixing it corrected an incorrect result on a different polygon. The code added diagonals between half-edges, the resulting graph wasn’t a correct triangulation if the diagonals were added between half-edges of different polygons: some of which were completely triangulated in some cases and thus deallocated before adding the faulty diagonal.

For nearly all mine other programs I use languages with automatic memory management (and I don’t use data structures as complex as DCEL), so there would be no error with the deallocation delayed after the final use of the object. Previously I thought that all such errors would be introduced by incorrect placement of free or delete calls. This program helped me realize that the delete operator can be useful in detecting otherwise incorrect code.


Comments

Submit comments on this post to <mtjm@mtjm.eu>.