How to (unit) test if a function is lock free ?

Question

I would like to add several unit tests to my code, also as I load plug ins I don't always have access to the code I'm running. The test I would really like to check is if the function I'm calling is lock free ?

Is there any hook, or way to test if between a point A and B in my program there was a call to a non lock free function ?

Another less complicated function is how to hook all calls to locking functions (like locks, system calls ...). I know how to hook calls to malloc on windows but nothing else.

Thank you for your help

Answer 1

You can't.

You could substitute a different implementation of pthread_lock but code could make direct calls to e.g. futex, and if you replace that the code could still call it directly with syscall(SYS_futex,...). You could profile the code or use something like strace to detect all such calls, but that still wouldn't tell you if the code implements its own custom spinlock in assembly.

Answer 2

I'm pretty sure you can't do that without instrumenting the locks, or something similar.

One could come up with a lot of scenarios where the call of a locking function causes different behaviour in testing [possibly only when "special test-mode for identifying testing" is enabled] than in production code - for example, add a sleep for 100ms into the lock method, and try to use another locked function and compare the time with "no competiton for the lock.

Or we could keep a count of calls to lock, and see if the count before and after the function is the same (or has increased by the expected amount, if the function is supposed to call lock a certain number of times).

But a generic way that isn't intrusive into the locking mechanism, I'm pretty sure it's impossible.

Of course, code-review and clear documentation as to what code calls locks and which doesn't would also be useful - and good reviewers that spot errors.

Answer 3

As the others have already answered it is not possible to test whether the algorithm is lock-free or not. However, it is possible to test that it behaves consistently in a multi-threaded environment. My experience in this area is only using a lock-free queue (which I wrote myself, but based on an academic paper) so my tests are based around a queue which may or may not be useful to you.

I used multiple threads to test to hammer the queue.

1. Thread Safety: the queue must not crash under heavy loads
2. Speed: how does the response times vary under a heavy load
3. Consistency: the queue mustn't loose items.

In my test, I also varied the number of readers and writers. The queue will behave differently depending on the ratio of readers to writers. More readers than writers will generally result in a nearly empty queue, whereas the inverse will result in a queue that continually expands until the writers stop writing.

Point 2 might be of interest to you as you can you can generally tell if the algorithm is lock-free or not based on the variance of response times under a heavy load. If response times remain fast under a heavy load then you can infer that the algorithm is lock-free. Or at least if it isn't it behaves as it if is.