Bounds checking, leak checks and race conditions check with gcc sanitize

If you are coding since many years in C or C++ you probably hit many tools that helped in finding memory leaks in your code as well as did bounds checking to avoid buffers overrun. Those were PurifyPlus (rational), BoundsChecker (numega). Then valgrind cameout and all linux developers were happy to run valgrind on their code to find leaks and bounds overruns.

Since gcc 4.8 and llvm 3.1 Sanitize has been introduce in the compiler as a compile option which gives you the ability to check for :

  • leak and bounds overrun : -fsanitize=address
  • race conditions : -fsanitize=thread

Using sanitizer in your normal Test environment (we use c++ google test framework to test api code) will drastically change the quality of your software products (C, C++ or GO) by allowing you to spot most of the bounds overrun and leaks during the testing phase, both in your code and in the code that you include not written by you.

In my sample makefiles we build all component that we use in test in debug mode (-g3) and with sanitize settable from outside via an environment variable :

SANITIZE = -fsanitize=address

CXXFLAGS = -std=c++11 -pthread -fpermissive -isystem ../../googletest/include -isystem ../../googletest -DDEBUG -g3 $(SANITIZE)

Compiling a library with sanitize is :

$ make -f libfh.mk debugclean debuglinux
rm -rf fh.do fh.mo libfh-debug.a
cc -DDEBUG -g3 -fsanitize=address -O0 -fPIC --std=c99 -Wall -Wextra -Wcomment -pthread -I . -c fh.c -o fh.do
ar crs libfh-debug.a fh.do

Compiling tests :

$ make -f libfh-test.mk testclean testlinux
rm -rf TestMain.o TestThread.o TestFH.o CommandLineParams.o testfh *.gcda *.gcno gtest-all.o ../../*_test_results.xml
g++ -std=c++11 -pthread -fpermissive -isystem ../../googletest/include -isystem ../../googletest -DDEBUG -g3 -fsanitize=address -I.. -I ../../libutil/src -c -o TestMain.o TestMain.cpp
g++ -std=c++11 -pthread -fpermissive -isystem ../../googletest/include -isystem ../../googletest -DDEBUG -g3 -fsanitize=address -I.. -I ../../libutil/src -c -o TestThread.o TestThread.cpp
g++ -std=c++11 -pthread -fpermissive -isystem ../../googletest/include -isystem ../../googletest -DDEBUG -g3 -fsanitize=address -I.. -I ../../libutil/src -c -o TestFH.o TestFH.cpp
g++ -std=c++11 -pthread -fpermissive -isystem ../../googletest/include -isystem ../../googletest -DDEBUG -g3 -fsanitize=address -I.. -I ../../libutil/src -c -o CommandLineParams.o CommandLineParams.cpp
g++ -isystem ../../googletest/include -I ../../googletest/ -pthread -c ../../googletest/src/gtest-all.cc
g++ -o testfh -fsanitize=address TestMain.o TestThread.o TestFH.o CommandLineParams.o gtest-all.o -L ../ -lfh-debug -lpthread

Now let’s run a test (after having introduced a bug) :


paul@paul-bigdesk:~/git/clibs/libfh/test$ ./testfh --gtest_filter=*hash_with_struct*
Running main() in file c-libraries/libfh/test/TestMain.cpp
Now running test executable: ./testfh
Note: Google Test filter = *hash_with_struct*
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from FH
[ RUN ] FH.hash_with_struct
=================================================================
==23907==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000eb5f at pc 0x7f37a13bc964 bp 0x7fff66eca0b0 sp 0x7fff66ec9858
WRITE of size 16 at 0x60200000eb5f thread T0
#0 0x7f37a13bc963 in __asan_memcpy (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x8c963)
#1 0x466298 in fh_insert /home/paul/git/clibs/libfh/fh.c:390
#2 0x414ed5 in FH_hash_with_struct_Test::TestBody() /home/paul/git/clibs/libfh/test/TestFH.cpp:486
#3 0x45683e in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x45683e)
#4 0x44fdf6 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x44fdf6)
#5 0x433737 in testing::Test::Run() (/home/paul/git/clibs/libfh/test/testfh+0x433737)
#6 0x4340cf in testing::TestInfo::Run() (/home/paul/git/clibs/libfh/test/testfh+0x4340cf)
#7 0x4347c2 in testing::TestCase::Run() (/home/paul/git/clibs/libfh/test/testfh+0x4347c2)
#8 0x43b8b5 in testing::internal::UnitTestImpl::RunAllTests() (/home/paul/git/clibs/libfh/test/testfh+0x43b8b5)
#9 0x457e16 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x457e16)
#10 0x450c6e in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x450c6e)
#11 0x43a35b in testing::UnitTest::Run() (/home/paul/git/clibs/libfh/test/testfh+0x43a35b)
#12 0x406819 in main /home/paul/git/clibs/libfh/test/TestMain.cpp:38
#13 0x7f37a07c582f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#14 0x406538 in _start (/home/paul/git/clibs/libfh/test/testfh+0x406538)

0x60200000eb5f is located 0 bytes to the right of 15-byte region [0x60200000eb50,0x60200000eb5f)
allocated by thread T0 here:
#0 0x7f37a13c8662 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x98662)
#1 0x466222 in fh_insert /home/paul/git/clibs/libfh/fh.c:384
#2 0x414ed5 in FH_hash_with_struct_Test::TestBody() /home/paul/git/clibs/libfh/test/TestFH.cpp:486
#3 0x45683e in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x45683e)
#4 0x44fdf6 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x44fdf6)
#5 0x433737 in testing::Test::Run() (/home/paul/git/clibs/libfh/test/testfh+0x433737)
#6 0x4340cf in testing::TestInfo::Run() (/home/paul/git/clibs/libfh/test/testfh+0x4340cf)
#7 0x4347c2 in testing::TestCase::Run() (/home/paul/git/clibs/libfh/test/testfh+0x4347c2)
#8 0x43b8b5 in testing::internal::UnitTestImpl::RunAllTests() (/home/paul/git/clibs/libfh/test/testfh+0x43b8b5)
#9 0x457e16 in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x457e16)
#10 0x450c6e in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) (/home/paul/git/clibs/libfh/test/testfh+0x450c6e)
#11 0x43a35b in testing::UnitTest::Run() (/home/paul/git/clibs/libfh/test/testfh+0x43a35b)
#12 0x406819 in main /home/paul/git/clibs/libfh/test/TestMain.cpp:38
#13 0x7f37a07c582f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: heap-buffer-overflow ??:0 __asan_memcpy
Shadow bytes around the buggy address:
0x0c047fff9d10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff9d20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff9d30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff9d40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff9d50: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c047fff9d60: fa fa fa fa fa fa fa fa fa fa 00[07]fa fa 05 fa
0x0c047fff9d70: fa fa 00 00 fa fa 00 00 fa fa 00 fa fa fa 00 fa
0x0c047fff9d80: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff9d90: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff9da0: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff9db0: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Heap right redzone: fb
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack partial redzone: f4
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
==23907==ABORTING

You easily get to were the bug is fh.c line 390; we decremented the allocated size by 1:

new_opaque_obj = malloc(fh->h_datalen-1);

Easily you can switch to race conditions checking my using

$ make SANITIZE=-fsanitize=thread -f libfh-test.mk testclean testlinux

 

Design for simplicity : software options

xkcd.com

(I was highly inspired by Evan Martin post before trying to recap in this post)
Think twice before adding an option to a software; options are :

  • bad user experience : good software just works without asking to many things to the user.
  •  a maintenance cost : an option is a feature you have to maintain/test for the lifetime of the software
  • documentation cost : every option, even the most cryptical, should be documented to the user, explained and you should provide some examples of use. When you normally try to do this you end up removing the option from documentation
  • normally options are a way to delegate to user a decision that the designer failed to take : “shall we open on the last opened document or shall put an options ‘always open on blank document’ ?
  • remember the paradox of choice
  • options setting generates bad GUIs : they are hard to present, group or organize.

On the other hand consider that any change you make will probably break someone’s workflow, no doubt, so the temptation to create an option to enable the previous operational mode is high.

The old windows search wizard, awesome, read this : https://www.joelonsoftware.com/2000/04/12/choices/

WTF/Minute : code quality measure unit

 Some day your code will be reviewed, modified or even just read to understand the underlying algorithm by someone else that is not you that wrote the code….

My point here is that readability/maintainability of code is by far the biggest quality of a piece of software. Being able to read the code and understand it rapidly makes everything easier, either bugfixing or modifying/enhancing the code. Think that the next one that might be reading the code might not be as experienced as you with that language so

  • avoid using  unnecessarily complicated constructs that feed you coder ego but slow down the maintenance activity. You are a good coder, no doubt, but if your code is not readable by the average coder that will have to then you are not making a good service to your colleagues
  • Make clear what your code is doing and, if necessary use a comment to clarify what is not evident from the code (I’m not a huge fan of comments because most of them don’t tell anything more than the code). Use comments to refer to a requirement/user-story that is being implemented.
  • Stick to the language style guidelines that were set for your team/company
  • Tests are code too and often are read/reviewed more than real code : don’t fuck up in tests code just because “this is just a test, this code will not run in production”

I’m sure I have more of these but for know I’ll stop here.

Comic comes from here

 

Hash functions – efficency and speed

hash function is any function that can be used to map data of arbitrary size to data of a fixed size. The values returned by a hash function are called hash valueshash codesdigests, or simply hashes. Hash functions are often used in combination with a hash table, a common data structure used in computer software for rapid data lookup.

If you happen to need a non cryptographic hash function (and you might need it even if your are using languages that have builtin hashtables like java or c++ ) here are some references taken from various parts:

Interesting comparison of different hash tables :

http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

Some more hashfunctions here :

http://www.cse.yorku.ca/~oz/hash.html

Some really interesting benchmarks here by Peter Kankowsky.

And again hash benchmarks here.

Some (a mininum set) benchmarks ran using User-Agents as keys, 1.5 multiply factor on hash size, next power of 2 hash sizes :

Keys 3130591, Average fh_default_hash(8388608) time in nanosecs : 292.56
Total collisions 517939, longest chain 6, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average djb_hash(8388608) time in nanosecs : 181.24
Total collisions 517445, longest chain 7, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average sax_hash(8388608) time in nanosecs : 244.49
Total collisions 517431, longest chain 7, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average jsw_hash(8388608) time in nanosecs : 141.39
Total collisions 522951, longest chain 14, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average jen_hash(8388608) time in nanosecs : 148.54
Total collisions 518565, longest chain 7, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average djb2_hash(8388608) time in nanosecs : 182.37
Total collisions 516405, longest chain 7, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average sdbm_hash(8388608) time in nanosecs : 238.93
Total collisions 525513, longest chain 7, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average fnv_hash(8388608) time in nanosecs : 237.01
Total collisions 517530, longest chain 7, hash_dim_factor 1.500000
----------------------
Keys 3130591, Average oat_hash(8388608) time in nanosecs : 294.78
Total collisions 517939, longest chain 6, hash_dim_factor 1.500000
----------------------


Tests done with the hashtable code you can find here

And last a research study (which I’m still working on) for SIMD optimized hash functions : here  some theory and code here. The all use the vector extensions present in gcc.

 

Code benchmarks : how can I measure how fast my software is (and make it faster) ?

You probably heard many times a coder say “this way is faster” : nothing can be more wrong nowadays unless you prove your statement by measuring the same piece of code running with algorithm A and algorithm B (the faster one). And there were times when you could measure the speed of the execution time of a program 1, 2 or 10 times without noticeable variability : those times are gone. Measuring how fast a piece of software runs is about getting a set of results with the lowest possible variability.

Variability in computing time in modern computer architectures is just unavoidable; while we can guarantee the results of a computation we cannot guarantee how fast this computation will be :

“Computer can reproduce anwsers, not performance” : Bryce Adelstein Lellback, https://youtu.be/zWxSZcpeS8Q?t=6m45s

Reasons for variance in computation time can be recap in :

  • Hardware jitter : instruction pipelines, cpu frequency scaling and power management, shared caches and many other things
  • OS activities : a huge list of things the kernel can do to screw up your benchmark performance
  • Observer effect : every time we instruments code to measure performance we introduce variance.

Also warming up the cpu seems to have become necessary to get meaningful results. Running hot instead of cold on a single piece of code is well described here :

https://youtu.be/zWxSZcpeS8Q?t=18m51s

This said the process for benchmarking an piece of code is :

  • Write some benchmark code : define a subset of execution (let’s call it op1) in your code and measure how many op1/sec. Do the same for other parts (op2, op3) but be sure that all parts can be run indipendently from each other   
  • Assure that samples population that we get is “normal” distributed

In details I use C code to measure and :

  • Use GNU Scientific Library (gsl) for mean, median, variance, stdev, skew running stats
  • Use CLOCK_MONOTONE clock_gettime() mode. An example code here.
  • Check if the set returned has ‘normal’ distribution : find the algorithm you like here (I use mean-median/max(mean,median) < 1%, not really correct but ok for my purposes).
  • Narrow down as much as possible the size of the code you are measuring
  • Warm up the cpu before taking samples to avoid having too much variability. You do this by running the code you want to measure many times before actually taking samples. Ideally you should run it until you have normal distributed results. If you don’t then probably the piece of code you are measuring is too big and you are experiencing the effects of other perturbations (os ? io ?).
  • Consider using a benchmark framework : google benchmark (c++) is great for this but I’m afraid you will have to measure C++ code.
  • Lock the cpu clock (if you can) on the host you are using for benchmarks.

Prepare to see strange results 🙂

gcc/clang -fsanitize is saving lifes

 There where times when you had to write C/C++ code and find all the bounds errors and memory leaks by hand or with ancient tools (who remembers Purify?). Valgrind introduced a lot of features but sanitize features added in gcc/clang are just awesome (thanks google guys for this). Just add -fsanitize=address both to compilation and link of your unit tests (we use google test framework), execute the test and get valuable info on memory leaks and out of bounds access to data. In detail :

Testing and inclusion of sanitize is under way in our lab : more info on this in a future post. Work from this team led to the inclusion in Golang of the Data Race detector.

 

Self driving is the next big thing

Just a few years ago the idea of a self driving car was seen as a futuristic technology that would take decades to arrive. Now it is only a matter of when it will be available and this thanks to startups that are shaping this segment. Here’s  a list (incomplete) of autonomous driving related companies, hardware, software and services, some of which have recently raised money from vc and investors :

  • lvl5 : computer vision software to crowdsource high-accuracy maps for self-driving cars.
  • starsky robotics , embark : self driving trucks
  • ouster (raised 27M$ ) : best lidar to date
  • AIMotive (raised 38M$ ) : full stack autonomous driving software
  • Nauto (raised 159M$ ) : self driving safety
  • drive.ai (raised 50M$ ) : self driving full stack
  • cruise ( GM bought for 1B$) : self driving full stack
  • pony.ai (raised 112M$ ) : claim safest self driving full stack
  • zoox.com raised 250M$ ) : self driving automaker

Driving a Tesla Model S in Paris

My brother in law owns a Tesla model S in Paris and I had a chance to try it out last week. One of the most exciting experiences (Miles Davis would have added “with my pants on”) of the last times. You are driving with almost no noise ( I know Jeremy Clarkson will hate this but I like it so much) in total comfort on a car that comes from another planet : this is what it looks like.

First of all I must say that I hate cars and what they represent : I’ve always considered them a necessary evil. I spent tons of money around my cars (smashing them so many times when I was in my twenties), doing maintenance and repairing them that I developed what is my personal requirements list for a car :

  1. accident prevention : a car that foresees a potentially dangerous situation and takes control to avoid an accident/crash. With a car like this I would have saved tons of money and a couple of broken ribs
  2. no maintenance or lowest possible : if I have to use a car I want to have the lowest possible maintenance. Brakes, oil and filters, clutch, distribution belts, sparks …. There is always something to do with your car
  3. do not contribute to city air pollution or do it the less possible

Tesla ( and probably other electric cars in the future will )  is matching exactly my requirements for what I want in a car.  Autonomous driving with all the available variants which range from lane/speed/front car distance control to full autonomous driving would make driving safer and reduce accidents and damage to the car.

And electric traction will make maintenance a distant memory : with the Tesla I tried which was set at maximum engine brake I barely never had to use the brake pedal; the cars brakes by using the electric motors as generators so you recharge you battery just by using the engine break

And performance comes last in the sense that I’m not a super car fan but pulling the gas to the floor on the Model S is a breathtaking experience. The picture on the left shows you the warp effect 🙂

Creating logstash development environment for core or plugins

I had to develop a ruby logstash plugin recently and I going to recap all necessary steps to create a clean jruby env for development :

  • i had to uninstall ruby and install a clean jruby only stack. Not saying that this is necessary but in my case it only worked this way
gpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3
curl -sSL https://get.rvm.io | bash -s stable --ruby=jruby-9.1.10.0
rvm alias create default jruby-9.1.10.0
source $HOME/.rvm/scripts/rvm
ruby -v
jruby 9.1.10.0 (2.3.3) 2017-05-25 b09c48a OpenJDK 64-Bit Server VM 25.151-b12 on 1.8.0_151-8u151-b12-0ubuntu0.16.04.2-b12 +jit [linux-x86_64]
  • Install and compile logstash just to see if everything works. Check out logstash and from inside the directory :
jruby -S gem install rake bundler
rake bootstrap
rake plugin:install-default
bin/logstash -e 'input { stdin { } } output { stdout {} }'

  • Now compile the plugin from the plugin folder
bundle install
bundle exec rspec # test it
gem build logstash-filter-<yourplugin>.gemspec
  • Install the plugin gem and test it
bin/logstash-plugin install logstash-filter-<yourplugin>-1.0.0.gem

 

When all 450.000 Tesla model 3 will hit the road …

In a 2 or 3 years all 450.000 model 3 tesla (and probably more) will hit the road and start making an average of 16.550 miles per year. Considering :

this will translate in around 2.5 Tera Wh/year more consumption on the electric grid. Let’s say that in 5 years 10% of all new cars sold are electric. We’ll have an extra 10 TWh per year to reach 1% of all electric consumption in US (in 5 years) and this will just be around 1% of the total number of cars on roads in US. So 1% of electric fleet equals 1% increase over total electricity consumption.