Testing of the C Algorithms library
When writing a set of general purpose data structures, correctness of the
implementation is particularly important. If the foundations on which a program
is based are unsound, how can we have any confidence in its correctness or
reliability?
Edsger Dijkstra remarked
that testing can never prove the absence of errors, only their presence.
However, somewhat paradoxically, we can never have any confidence in a
program unless it has been tested; as Donald Knuth once humorously
commented:
"beware of bugs in the above code; I have only proved it correct, not tested
it".
A dual approach is used to gain confidence in the correctness of the C
Algorithms library. Firstly, the code is structured to be as simple as
possible in order to be obviously correct. Secondly, the library includes an
extensive test suite.
Coverage analysis
For a test suite to be useful, it must test the entire program. If the test
exercises some sections of the program but not others, we can only have a
limited degree of confidence in the program as a whole.
For this reason, code
coverage analysis of the source code is performed, using
GNU gcov. This
provides a quantitative measure of the coverage providded by the test suite.
The aim is for 100% test coverage. The current version of the library comes very
close to this; see here for the coverage report
for the v1.2.0 release.
Code coverage is disabled by default, but can be enabled by passing the
--enable-coverage parameter to the configure script.
Memory allocation testing
The C programming language uses manual memory management. As a large number of
software bugs result from memory management errors, the test suite incorporates
a framework
for testing memory allocation. This consists of a header file that redirects
all use of memory management functions test wrapper functions that track
memory allocated during the test. As a result, it is possible to detect memory
leaks, doubly freed memory blocks, and memory that is used without being
properly initialised.
A secondary function of the memory testing framework is the ability to
deliberately trigger memory allocation failures. It can therefore be confirmed
that the library acts correctly in failure scenarios.
Valgrind
Valgrind is an award-winning program for
detecting memory errors. The entire test suite can be run in Valgrind and it is
used routinely during development.
Valgrind is disabled by default; to run the test suite in Valgrind, pass the
--enable-valgrind command-line option to the configure script.
Send comments to Simon Howard.