Intel rdrand instruction revisited

A few months ago I did a quick and dirty benchmark of the Intel rdrand instruction found on the new Ivybridge processors.  I did some further analysis a while ago and I've only just got around to writing up my findings. I've improved the test by exercising the Intel Digital Random Number Generator (DRNG) with multiple threads and also re-writing the rdrand wrapper in assembler and ensuring the code is inline'd.  The source code for this test is available here.

So, how does it shape up?  On a i5-3210M (2.5GHz) Ivybridge (2 cores, 4 threads) I get a peak of ~99.6 million 64 bit rdrands per second with 4 threads which equates to ~6.374 billion bits per second.  Not bad at all.

With a 4 threaded i5-3210M CPU we hit maximum rdrand throughput with 4 threads.

..and with a 8 threaded i7-3770 (3.4GHz) Ivybridge (4 cores, 8 threads) we again hit a peak throughput of 99.6 million 64 bit rdrands a second on 3 threads. One can therefore conclude that this is the peak rate of the DNRG on both CPUs tested.  A 2 threaded i3 Ivybridge CPU won't be able to hit the peak rate of the DNRG, and a 4 threaded i5 can only just max out the DNRG with some hand-optimized code.

Now how random is this random data?  There are several tests available; I chose to exercise the DRNG using the dieharder test suite.  The test is relatively simple; install dieharder and do 64 bit rdrand reads and output these as a raw random number stream and pipe this into dieharder:

 sudo apt-get install dieharder  
 ./rdrand-test | dieharder -g 200 -a
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |rands/second|   Seed   |
stdin_input_raw|  3.66e+07  | 639263374|
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.40629140|  PASSED  
      diehard_operm5|   0|   1000000|     100|0.79942347|  PASSED  
  diehard_rank_32x32|   0|     40000|     100|0.35142889|  PASSED  
    diehard_rank_6x8|   0|    100000|     100|0.75739694|  PASSED  
   diehard_bitstream|   0|   2097152|     100|0.65986567|  PASSED  
        diehard_opso|   0|   2097152|     100|0.24791918|  PASSED  
        diehard_oqso|   0|   2097152|     100|0.36850828|  PASSED  
         diehard_dna|   0|   2097152|     100|0.52727856|  PASSED  
diehard_count_1s_str|   0|    256000|     100|0.08299753|  PASSED  
diehard_count_1s_byt|   0|    256000|     100|0.31139908|  PASSED  
 diehard_parking_lot|   0|     12000|     100|0.47786440|  PASSED  
    diehard_2dsphere|   2|      8000|     100|0.93639860|  PASSED  
    diehard_3dsphere|   3|      4000|     100|0.43241488|  PASSED  
     diehard_squeeze|   0|    100000|     100|0.99088862|  PASSED  
        diehard_sums|   0|       100|     100|0.00422846|   WEAK   
        diehard_runs|   0|    100000|     100|0.48432365|  PASSED 
..
        dab_monobit2|  12|  65000000|       1|0.98439048|  PASSED 

..and leave to cook for about 45 minutes.  The -g 200 option specifies that the random numbers come from stdin and the -a option runs all the dieharder tests.  All the tests passed with the exception of the diehard_sums test which produced "weak" results, however, this test is known to be unreliable and recommended not to be used.  Quite honestly, I would be surprised if the tests failed, but you never know until one runs them.

The CA cert research labs have an on-line random number generator analysis website allowing one to submit and test at least 12 MB of random numbers. I submitted 32 MB of data, and I am currently waiting to see if I get any results back.  Watch this space.

Striving for better code quality.

Software is complex and is never bug free, but fortunately there are many different tools and techniques available to help to identify and catch a large class of common and obscure bugs.

Compilers provide build options that can help drive up code quality by being particularly strict to detect questionable code constructions, for example gcc's -Wall and -pedantic flags.  The gcc -Werror flag is useful during code development to ensure compilation halts with an error on warning messages, this ensures the developer will stop and fix code.

Static analysis during compilation is also a very useful technique, tools such as smatch and Concinelle can identify bugs such as deferencing of NULL pointers, checks for return values and ranges,  incorrect use of && and ||, bad use of unsigned or signed values and many more beside.  These tools were aimed for use on the Linux kernel source code, but can be used on C application source too.  Let's take a moment to see how to use smatch when building an application.

Download the dependencies:

 sudo apt-get install libxml2-dev llvm-dev libsqlite3-dev

Download and build smatch:

 mkdir ~/src  
 cd ~/src  
 git clone git://repo.or.cz/smatch  
 cd smatch  
 make  

Now build your application using smatch:

 cd ~/your_source_code  
 make clean  
 make CHECK="~/src/smatch/smatch --full-path" \
   CC=~/src/smatch/cgcc | tee warnings.log  

..and inspect the warnings and errors in the file warnings.log.  Smatch will produce false-positives, so not every warning or error is necessarily buggy code.

Of course, run time profiling of programs also can catch errors.  Valgrind is an excellent run time profiler that I regularly use when developing applications to catch bugs such as memory leaks and incorrect memory read/writes. I recommend starting off using the following valgrind options:

 --leak-check=full --show-possibly-lost=yes --show-reachable=yes --malloc-fill=  

For example:

 valgrind --leak-check=full --show-possibly-lost=yes --show-reachable=yes \
  --malloc-fill=ff your-program  

Since the application is being run on a synthetic software CPU execution can be slow, however it is amazingly thorough and produces detailed output that is extremely helpful in cornering buggy code.

The gcc compiler also provides mechanism to instrument code for run-time analysis.  The -fmudflap family of options instruments risky pointer and array dereferencing operations, some standard library string and heap functions as well as some other range + validity tests.   For threaded applications use -fmudflapth instead of -fmudflap.   The application also needs to be linked with libmudflap.

Here is a simple example:

 int main(int argc, char **argv)  
 {  
     static int x[100];  
     return x[100];  
 }  

Compile with:

 gcc example.c -o example -fmudflap -lmudflap  

..and mudflap detects the error:

 ./example   
 *******  
 mudflap violation 1 (check/read): time=1347817180.586313 ptr=0x701080 size=404  
 pc=0x7f98d3d17f01 location=`example.c:5:2 (main)'  
    /usr/lib/x86_64-linux-gnu/libmudflap.so.0(__mf_check+0x41) [0x7f98d3d17f01]  
    ./example(main+0x7a) [0x4009c6]  
    /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xed) [0x7f98d397276d]  
 Nearby object 1: checked region begins 0B into and ends 4B after  
 mudflap object 0x190a370: name=`example.c:3:13 x'  
 bounds=[0x701080,0x70120f] size=400 area=static check=3r/0w liveness=3  
 alloc time=1347817180.586261 pc=0x7f98d3d175f1  
 number of nearby objects: 1  

These are just a few examples, however there are many other options too. Electric Fence is a useful malloc debugger, and gcc's -fstack-protector produces extra code to check for buffer overflows, for example in stack smashing. Tools like bfbtester allow us to brute force check command line overflows - this is useful as I don't know many developers who try to thoroughly validate all the options in their command line utilities.

No doubt there are many more tools and techniques available.  If we use these wisely and regularly we can reduce bugs and drive up code quality.

Virgin Media Super Hub and ssh timeouts

After upgrading to a new "shiny" Virgin Media Super Hub I started to get annoying ssh timeouts on idle connections.  After some Googling around I discovered that it suffers from TCP connection timeouts and some users have suggested that there isn't much memory in the device, so it can't save much session data.

Well, how does one workaround this issue?  Setting the keep alive probe down to 50 seconds and then resending it every 10 seconds seems to do the trick for me. I also tweaked the TCP settings so that if no ACK response is received for 5 consecutive times, the connection is marked as broken.  Here's the quick one-liner fix:
 

 sudo sysctl -w net.ipv4.tcp_keepalive_time=50 \
 net.ipv4.tcp_keepalive_intvl=10 \
 net.ipv4.tcp_keepalive_probes=5  

Of course, to make these settings persistent across reboots, add them to /etc/sysctl.conf

I'm not sure if these settings are "optimal", but they do the trick. You're mileage may vary.

Testing eCryptfs

Over the past several months I've been occasionally back-porting a bunch of eCryptfs patches onto older Ubuntu releases.  Each back-ported fix needs to be properly sanity checked and so I've been writing test cases for each one and adding them to the eCryptfs test suite.

To get hold of the test suite, check it out using bzr:

 bzr checkout lp:ecryptfs  

and install the dependencies so one can build the test suite:

 sudo apt-get install debhelper autotools-dev autoconf automake \
 intltool libtool libgcrypt11-dev libglib2.0-dev libkeyutils-dev \
 libnss3-dev libpam0g-dev pkg-config python-dev swig acl \
 ecryptfs-utils libattr1-dev

If you want to test eCrytpfs with xfs and btrfs as the lower file system onto which eCryptfs is mounted, then one needs to also install the tools for these:

 sudo apt-get install xfsprogs btrfs-tools  

And then build the test programs:

 cd ecryptfs  
 autoreconf -ivf  
 intltoolize -c -f  
 ./configure --enable-tests --disable-pywrap  
 make  

To run the tests, one needs to create lower and upper mount points. The tests allow one to create ext2, ext3, ext4, xfs or btrfs loop-back mounted file systems on the lower mount point, and then eCryptfs is mounted on the upper mount point on top.   To create these, use something like:

 sudo mkdir /lower /upper  

The loop-back file system image needs to be placed somewhere too, I generally place mine in a directory /tmp/image, so this needs creating too:

 mkdir /tmp/image  

There are two categories of tests, "safe" and "destructive".  Safe tests should run in such a ways as to not lock up the machine.  Destructive tests try hard to force bugs that can cause kernel oopses or panics. One specifies the test category with the -c option.  Now to run the tests, use:

 sudo ./tests/run_tests.sh -K -c safe -b 1000000 -D /tmp/image -l /lower -u /upper  

The -K option tells the test suite to run the kernel specific tests. These are the ones I am generally interested in since I'm testing kernel patches.

The -b option specifies the size in 1K blocks of the loop-back mounted /lower file system size.  I generally use 1000000 blocks as a minimum.

The -D option specifies the path where the temporary loop-back mounted image is kept and the -l and -u options specified the paths of the lower and upper mount points.

By default the tests will use an ext4 lower filesystem. One can also run specify which file systems to run the tests on using the -f option, this can be a comma separated list of one or more file systems, for example:

 sudo ./tests/run_tests.sh -K -c safe -b 1000000 -D /tmp/image -l /lower -u /upper \
 -f ext2,ext3,ext4,xfs  

And also, instead of running a bunch of tests, one can just a particular test using the -t option:

 sudo ./tests/run_tests.sh -K -c safe -b 1000000 -D /tmp/image -l /lower -u /upper \
 -f ext2,ext3,ext4,xfs -t lp-926292.sh

..which tests the fix for LaunchPad bug 926292
 
We also run these tests regularly on new kernel images to ensure we don't introduce and regressions.   As it stands, I'm currently adding in tests for each bug fix that we back-port and for most new bugs that require a thorough test. I hope to expand the breadth of the tests to ensure we get better general test coverage.

And finally, thanks to Tyler Hicks for writing the test framework and for his valuable help in describing how to construct a bunch of these tests.