## Clone, configure, build and test M4RI

I’m new to the autotools world, so I was rather helpless when I first looked at M4RI. Say I have patched a file in M4RI. The problem now is figuring out how to configure, build, and test the patched M4RI tree. The solution below was kindly communicated to me by the lead M4RI maintainer Martin Albrecht.

$ hg clone http://bitbucket.org/malb/m4ri $ cd m4ri/ $ autoreconf --install $ ./configure $ make $ make check

## Tools for C development

This post collects free and open source software tools that are useful when you do software development in C. For a survey of software development tools for scientific computation, see A Survey of C and C++ Software Tools for Computational Science by D.J. Worth, C. Greenough and L.S. Chin. See The Art, Science, and Engineering of Software Development by Steve McConnell for some best practices.

**Lint tools**

- Cppcheck: A tool for static C/C++ code analysis.
- Splint: Annotation-assisted lightweight static checking.

**Documentation generators**

- Natural Docs: documentation generator for multiple programming languages.
- ROBODoc
- Sphinx: A tool that makes it easy to create intelligent and beautiful documentation.

**Testing tools**

See A Survey of Software Testing Tools for Computational Science by L.S. Chin, D.J. Worth and C. Greenough.

- CUnit: Unit testing framework for C.
- gcov: A test coverage program. See ggcov for a GUI replacement of gcov.

**Profiling & debugging tools**

- DDD: Graphical front-end for command-line debuggers such as GDB, etc.
- GDB: The GNU Project debugger.
- google-perftools: Fast, multi-threaded malloc() and nifty performance analysis tools.
- gprof: The GNU profiler. For a tutorial on this tool, see Profiling Tutorial: A simple program by DJ Worth, LS Chin, and C Greenough.
- OProfile: Profiler for Linux systems, capable of profiling all running code at low overhead.
- RATS: Rough Auditing Tool for Security.
- Solaris Studio: Formerly Sun Studio, but is now called Oracle Solaris Studio.
- Valgrind: Instrumentation framework for building dynamic analysis tools.

## Parallel testing the Sage library

After compiling a source version of Sage, you can choose to run the test suite on the whole Sage library, on all modules under a given directory, or on a specified module only. For the purposes of this post, I have compiled Sage 4.1.1 from source and the top level Sage directory is

[mvngu@mod sage-4.1.1]$ pwd /scratch/mvngu/build/sage-4.1.1

**Testing a module**

Say you want to run all tests in the sudoku module sage/games/sudoku.py. In a terminal window, first cd to the top level Sage directory of your local Sage installation. Now start doctesting as demonstrated in the following terminal session:

[mvngu@mod sage-4.1.1]$ ./sage -t devel/sage-main/sage/games/sudoku.py sage -t "devel/sage-main/sage/games/sudoku.py" [6.0 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 6.0 seconds

As you can see, the numbers output by the test tell you that testing the sudoku module takes about six seconds, while testing all the modules you specified took the same amount of time. In this case, you only tested one module so it’s not surprising that the total testing time is approximately the same as the time required to test only that one module. Notice that the syntax is

[mvngu@mod sage-4.1.1]$ ./sage -t devel/sage-main/sage/games/sudoku.py sage -t "devel/sage-main/sage/games/sudoku.py" [5.7 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 5.7 seconds [mvngu@mod sage-4.1.1]$ ./sage -t "devel/sage-main/sage/games/sudoku.py" sage -t "devel/sage-main/sage/games/sudoku.py" [5.4 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 5.4 seconds

and not

[mvngu@mod sage-4.1.1]$ ./sage -t sage/games/sudoku.py ERROR: File ./sage/games/sudoku.py is missing exit code: 1 ---------------------------------------------------------------------- The following tests failed: ./sage/games/sudoku.py Total time for all tests: 0.0 seconds [mvngu@mod sage-4.1.1]$ ./sage -t "sage/games/sudoku.py" ERROR: File ./sage/games/sudoku.py is missing exit code: 1 ---------------------------------------------------------------------- The following tests failed: ./sage/games/sudoku.py Total time for all tests: 0.0 seconds

In all of the above terminal sessions, you use a local installation of Sage to test its own modules. Even if you have a system-wide Sage installation, using that version to doctest the modules of a local installation is a recipe for confusion. For example, in the following session, there is a system-wide Sage. Doctesting using that version doesn’t output anything useful.

[mvngu@mod sage-4.1.1]$ which sage /usr/local/bin/sage [mvngu@mod sage-4.1.1]$ sage devel/sage-main/sage/games/sudoku.py

**Troubleshooting**

If you want to doctest modules of a Sage installation, it is recommended that you first cd to the top level directory of that Sage installation, otherwise known as the SAGE_ROOT of that installation. When you run tests, use that particular Sage installation via the syntax ./sage; notice the “dot-forward-slash” at the front of sage. This is a precaution against confusion that can arise when your system has multiple Sage installations. For example, the following syntax is OK because you explicitly specify the Sage installation in the current SAGE_ROOT:

[mvngu@sage sage-4.1.1]$ ./sage -t devel/sage-main/sage/games/sudoku.py sage -t "devel/sage-main/sage/games/sudoku.py" [5.1 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 5.1 seconds [mvngu@sage sage-4.1.1]$ ./sage -t "devel/sage-main/sage/games/sudoku.py" sage -t "devel/sage-main/sage/games/sudoku.py" [5.0 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 5.0 seconds

If you login as a regular user, the following syntax is not recommended as you are using a system-wide Sage installation (if it exists):

[mvngu@sage sage-4.1.1]$ sage -t devel/sage-main/sage/games/sudoku.py Traceback (most recent call last): File "/usr/local/sage/local/bin/sage-test", line 49, in os.makedirs(TMP) File "/usr/local/sage/local/lib/python/os.py", line 157, in makedirs mkdir(name, mode) OSError: [Errno 13] Permission denied: '/usr/local/sage/tmp/tmp' [mvngu@sage sage-4.1.1]$ sage -t "devel/sage-main/sage/games/sudoku.py" Traceback (most recent call last): File "/usr/local/sage/local/bin/sage-test", line 49, in os.makedirs(TMP) File "/usr/local/sage/local/lib/python/os.py", line 157, in makedirs mkdir(name, mode) OSError: [Errno 13] Permission denied: '/usr/local/sage/tmp/tmp'

In this case, you received a permission error because the system-wide Sage installation attempts to write some data to a system-wide directory using your login privileges. The system-wide directory is a temporary directory under the system-wide SAGE_ROOT. Most likely a system-wide Sage installation was performed by a system administrator using an account with more privileges than a regular user. As a regular user, you cannot write to directories where you don’t have write permission.

The following syntax is also discouraged when you login as a regular user:

[mvngu@sage sage-4.1.1]$ cd [mvngu@sage ~]$ sage -t devel/sage-main/sage/games/sudoku.py Traceback (most recent call last): File "/usr/local/sage/local/bin/sage-test", line 49, in os.makedirs(TMP) File "/usr/local/sage/local/lib/python/os.py", line 157, in makedirs mkdir(name, mode) OSError: [Errno 13] Permission denied: '/usr/local/sage/tmp/tmp' [mvngu@sage ~]$ sage -t "devel/sage-main/sage/games/sudoku.py" Traceback (most recent call last): File "/usr/local/sage/local/bin/sage-test", line 49, in os.makedirs(TMP) File "/usr/local/sage/local/lib/python/os.py", line 157, in makedirs mkdir(name, mode) OSError: [Errno 13] Permission denied: '/usr/local/sage/tmp/tmp'

This is exactly the same as the previous syntax because in both cases you attempted to doctest modules in a system-wide Sage installation using privileges of a regular user. If you don’t have permission to read or write somewhere on your system, you can’t read or write there. As a regular user, you don’t usually have privileges to read the directory /root nor do you have privileges to write to the root directory:

[mvngu@sage sage-4.1.1]$ ls /root/ ls: cannot open directory /root/: Permission denied [mvngu@sage sage-4.1.1]$ cd / [mvngu@sage /]$ touch demo.txt touch: cannot touch `demo.txt': Permission denied

**Parallel testing many modules**

So far you have used a single thread to doctest a module in the Sage library. There are hundreds, even thousands of modules in the Sage library. Testing them all using one thread would take a few hours. Depending on your hardware, this could take up to six hours or more. On a multi-core system, parallel doctesting can significantly reduce the testing time. Unless you also want to use your computer while doctesting in parallel, you can choose to devote all the cores of your system for parallel testing.

Let’s doctest all modules in a directory, first using a single thread and then using two threads. For this example, suppose you want to test all the modules under sage/crypto/. You can use a syntax similar to that shown above to achieve this:

[mvngu@mod sage-4.1.1]$ ./sage -t devel/sage-main/sage/crypto/ sage -t "devel/sage-main/sage/crypto/lfsr.py" [2.5 s] sage -t "devel/sage-main/sage/crypto/cryptosystem.py" [1.9 s] sage -t "devel/sage-main/sage/crypto/block_cipher/miniaes.py" [2.5 s] sage -t "devel/sage-main/sage/crypto/block_cipher/all.py" [0.1 s] sage -t "devel/sage-main/sage/crypto/block_cipher/__init__.py" [0.1 s] sage -t "devel/sage-main/sage/crypto/classical.py" [2.7 s] sage -t "devel/sage-main/sage/crypto/mq/mpolynomialsystem.py" [8.7 s] sage -t "devel/sage-main/sage/crypto/mq/mpolynomialsystemgenerator.py" [1.9 s] sage -t "devel/sage-main/sage/crypto/mq/__init__.py" [0.1 s] sage -t "devel/sage-main/sage/crypto/mq/sbox.py" [2.8 s] sage -t "devel/sage-main/sage/crypto/mq/sr.py" [4.9 s] sage -t "devel/sage-main/sage/crypto/stream_cipher.py" [1.9 s] sage -t "devel/sage-main/sage/crypto/all.py" [0.1 s] sage -t "devel/sage-main/sage/crypto/stream.py" [1.9 s] sage -t "devel/sage-main/sage/crypto/__init__.py" [0.1 s] sage -t "devel/sage-main/sage/crypto/classical_cipher.py" [1.9 s] sage -t "devel/sage-main/sage/crypto/cipher.py" [1.9 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 35.7 seconds

Now let’s do the same thing, but this time let’s also use the optional argument -long:

[mvngu@mod sage-4.1.1]$ ./sage -t -long devel/sage-main/sage/crypto/ sage -t -long "devel/sage-main/sage/crypto/lfsr.py" [1.9 s] sage -t -long "devel/sage-main/sage/crypto/cryptosystem.py" [2.0 s] sage -t -long "devel/sage-main/sage/crypto/block_cipher/miniaes.py" [2.6 s] sage -t -long "devel/sage-main/sage/crypto/block_cipher/all.py" [0.1 s] sage -t -long "devel/sage-main/sage/crypto/block_cipher/__init__.py" [0.1 s] sage -t -long "devel/sage-main/sage/crypto/classical.py" [2.7 s] sage -t -long "devel/sage-main/sage/crypto/mq/mpolynomialsystem.py" [8.7 s] sage -t -long "devel/sage-main/sage/crypto/mq/mpolynomialsystemgenerator.py" [2.2 s] sage -t -long "devel/sage-main/sage/crypto/mq/__init__.py" [0.1 s] sage -t -long "devel/sage-main/sage/crypto/mq/sbox.py" [2.9 s] sage -t -long "devel/sage-main/sage/crypto/mq/sr.py" [56.6 s] sage -t -long "devel/sage-main/sage/crypto/stream_cipher.py" [2.5 s] sage -t -long "devel/sage-main/sage/crypto/all.py" [0.1 s] sage -t -long "devel/sage-main/sage/crypto/stream.py" [1.9 s] sage -t -long "devel/sage-main/sage/crypto/__init__.py" [0.1 s] sage -t -long "devel/sage-main/sage/crypto/classical_cipher.py" [1.9 s] sage -t -long "devel/sage-main/sage/crypto/cipher.py" [1.9 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 88.0 seconds

Notice the time difference between the first set of tests and the second set, which uses the optional argument -long. Many tests in the Sage library are flagged with “# long time” because these are known to take a long time to run through. Without using the optional -long argument, the module sage/crypto/mq/sr.py took about five seconds. With this optional argument, it required 57 seconds to run through all tests in that module. Here is a snippet of a function in the module sage/crypto/mq/sr.py with a doctest that has been flagged as taking a long time:

def test_consistency(max_n=2, **kwargs): r""" Test all combinations of ``r``, ``c``, ``e`` and ``n`` in ``(1, 2)`` for consistency of random encryptions and their polynomial systems. `\GF{2}` and `\GF{2^e}` systems are tested. This test takes a while. INPUT: - ``max_n`` - maximal number of rounds to consider (default: 2) - ``kwargs`` - are passed to the SR constructor TESTS:: sage: from sage.crypto.mq.sr import test_consistency sage: test_consistency(1) # long time -- calling w/ max_n = 2 requires a LOT of RAM (>> 2GB, evidently). Calling w/ max_n = 1 is far more manageable. True The above doctest used to fail on a machine with "only" 2GB RAM. Using ``max_n = 1`` appears to be a more reasonable memory usage. """

Now doctest the same directory in parallel using two threads:

[mvngu@mod sage-4.1.1]$ ./sage -tp 2 devel/sage-main/sage/crypto/ Global iterations: 1 File iterations: 1 Using cached timings to run longest doctests first. Doctesting 17 files doing 2 jobs in parallel sage -t devel/sage-main/sage/crypto/lfsr.py [2.7 s] sage -t devel/sage-main/sage/crypto/cryptosystem.py [2.0 s] sage -t devel/sage-main/sage/crypto/mq/mpolynomialsystem.py [9.4 s] sage -t devel/sage-main/sage/crypto/mq/sr.py [5.2 s] sage -t devel/sage-main/sage/crypto/classical.py [2.8 s] sage -t devel/sage-main/sage/crypto/mq/sbox.py [3.2 s] sage -t devel/sage-main/sage/crypto/block_cipher/miniaes.py [2.6 s] sage -t devel/sage-main/sage/crypto/stream_cipher.py [2.0 s] sage -t devel/sage-main/sage/crypto/mq/mpolynomialsystemgenerator.py [2.0 s] sage -t devel/sage-main/sage/crypto/classical_cipher.py [2.1 s] sage -t devel/sage-main/sage/crypto/cipher.py [2.1 s] sage -t devel/sage-main/sage/crypto/__init__.py [0.1 s] sage -t devel/sage-main/sage/crypto/block_cipher/__init__.py [0.1 s] sage -t devel/sage-main/sage/crypto/mq/__init__.py [0.1 s] sage -t devel/sage-main/sage/crypto/block_cipher/all.py [0.1 s] sage -t devel/sage-main/sage/crypto/stream.py [2.0 s] sage -t devel/sage-main/sage/crypto/all.py [0.1 s] ---------------------------------------------------------------------- All tests passed! Timings have been updated. Total time for all tests: 19.3 seconds [mvngu@mod sage-4.1.1]$ ./sage -tp 2 -long devel/sage-main/sage/crypto/ Global iterations: 1 File iterations: 1 No long cached timings exist; will create upon successful finish. Doctesting 17 files doing 2 jobs in parallel sage -t -long devel/sage-main/sage/crypto/cryptosystem.py [2.7 s] sage -t -long devel/sage-main/sage/crypto/lfsr.py [2.7 s] sage -t -long devel/sage-main/sage/crypto/stream_cipher.py [2.2 s] sage -t -long devel/sage-main/sage/crypto/all.py [0.1 s] sage -t -long devel/sage-main/sage/crypto/classical.py [3.0 s] sage -t -long devel/sage-main/sage/crypto/__init__.py [0.1 s] sage -t -long devel/sage-main/sage/crypto/stream.py [2.1 s] sage -t -long devel/sage-main/sage/crypto/classical_cipher.py [2.1 s] sage -t -long devel/sage-main/sage/crypto/cipher.py [2.1 s] sage -t -long devel/sage-main/sage/crypto/block_cipher/all.py [0.1 s] sage -t -long devel/sage-main/sage/crypto/block_cipher/__init__.py [0.1 s] sage -t -long devel/sage-main/sage/crypto/block_cipher/miniaes.py [2.8 s] sage -t -long devel/sage-main/sage/crypto/mq/mpolynomialsystemgenerator.py [2.0 s] sage -t -long devel/sage-main/sage/crypto/mq/__init__.py [0.1 s] sage -t -long devel/sage-main/sage/crypto/mq/sbox.py [3.1 s] sage -t -long devel/sage-main/sage/crypto/mq/mpolynomialsystem.py [9.1 s] sage -t -long devel/sage-main/sage/crypto/mq/sr.py [56.0 s] ---------------------------------------------------------------------- All tests passed! Timings have been updated. Total time for all tests: 71.8 seconds

As the number of threads increases, the total testing time decreases. To minimize confusion, it’s also a good idea to explicitly specify the path name of the directory you want to doctest and not a symbolic link to that directory. In the above examples, the symbolic link devel/sage points to the directory devel/sage-main, but the actual path to the directory has been specified instead of its symbolic link.

**Parallel testing the whole Sage library**

The main Sage library resides in the directory devel/sage-main/. You can use the syntax described above to doctest the main library using multiple threads. When doing release management or patching the main Sage library, I would parallel test the library using ten threads:

[mvngu@mod sage-4.1.1]$ ./sage -tp 10 -long devel/sage-main/

Another way is to edit the file makefile in the top level Sage directory so that the variable NUM_THREADS is set to 10:

# How many threads should be used when doing parallel testing (and # sometime in the future, parallel building)? NUM_THREADS=10

After saving all changes to makefile, you can parallel test with the -long option using ten threads:

[mvngu@mod sage-4.1.1]$ make ptestlong

Any of the following commands would also doctest the Sage library or one of its clones:

make test make check make testlong make ptest make ptestlong

In each case, testing is performed on the directory that is pointed to by the symbolic link devel/sage.

**Updates** 2010-01-08 — This post is now in the Sage Developers’ Guide.