Here at Runtime Verification, we are spending time developing and improving tools for the K Framework. In particular, one of the projects I have been working on is a new execution engine for concrete execution of programs in K semantics, which compiles to LLVM.
Because we compile to LLVM, we are able to make use of code in any programming language that targets LLVM. In particular, we use Rust for the portion of the runtime which handles operations over lists, maps, and sets.
Yesterday I discovered a very subtle bug in our Rust code which was causing our tests to fail. It was affecting the hash algorithm we use for maps and sets, which in turn caused a map lookup operation to fail even though the key it was supposed to look up was in fact in the map.
See if you can spot the bug below:
Perhaps it will be easier to spot if you compare the code to the version with the bug fixed:
I'm sure you see it now. We forgot to dereference the raw pointer! Of course, one can argue that we should not be using raw pointers in rust at all, and in general, where possible, this is true. However, the reason we were using raw pointers here is because the set pointer is actually coming from LLVM code, and therefore needs to be compatible with the C FFI.
So what is the buggy code actually doing? The answer can be found within the std::hash trait. If you scroll down, you will find the following trait implementation:
If you look at the source of this implementation, you will see that it is merely hashing the bits of the address, rather than following the reference (since it does not require T to implement Hash).
Thus, we were actually hashing the address of the set rather than actually calling the set's hash function. Because this function was only being called in our code when a collection contained another collection as a key, something which had not happened up until now, we managed to avoid detecting this error until now. And it proved quite difficult to track down, as I had to spend several hours narrowing down and confirming the location of the bug before I finally was able to spot it in that method.
Did you spot it on the first glance? Or, like me, did you miss the fact that the wrong implementation for the Hash trait was being called? My advice is, when dealing with traits and raw pointers together, be very careful, because it turns out that raw pointers can themselves implement a number of traits, and you may not get the behavior you intended if you forget to dereference. But you may not get a compiler error either!
Best of luck in your rust coding.
