From: Tobias C. R. <tc...@fr...> - 2010-03-12 09:56:44
|
I have code I know is not thread-safe, but it's nearly impossible to write test cases that exhibit a bug reliably (or even just with a certain percentage) because the window of interruption to trigger the bug is just one, or two instructions. If I insert an explicit (thread-yield) at the right place, a test case is very easy to write. Now I wonder how easy/difficult it would be to make the compiler insert calls to (thread-yield) randomly. Inserting on instruction granularity sounds difficult to do if the compiler architecture wasn't made for it -- especially because SBCL does not have a peephole optimizer --, but perhaps between vops? (That's also where an manual insertion of (thread-yield) could go, so..) If a feature like that was available, I hope that making my test suite recompile the system again and again (to trigger different placement of the calls to (thread-yield), and running the test suite again and again, would result in exhibiting such bugs in say one out of 100, or 1000 runs. Does anyone happen to know of prior art? -T. |
From: Rudi S. <ru...@co...> - 2010-03-12 10:30:05
|
On Mar 12, 2010, at 10:56 AM, Tobias C. Rittweiler wrote: [...] > Now I wonder how easy/difficult it would be to make the compiler insert > calls to (thread-yield) randomly. Inserting on instruction granularity > sounds difficult to do if the compiler architecture wasn't made for it > -- especially because SBCL does not have a peephole optimizer --, but > perhaps between vops? (That's also where an manual insertion of > (thread-yield) could go, so..) > > If a feature like that was available, I hope that making my test suite > recompile the system again and again (to trigger different placement of > the calls to (thread-yield), and running the test suite again and again, > would result in exhibiting such bugs in say one out of 100, or 1000 > runs. > > Does anyone happen to know of prior art? Yes, for example http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.8467 where they do a similar thing for Java programs. The surprising underlying phenomenon is that OS schedulers are more-or-less deterministic, i.e. re-running your program will get you the same result w.r.t. scheduling, but another OS / heavy process load / phase-of-the-moon might trigger another, equally deterministic behavior, causing the app to fail on the deployment server because a race-condition is uncovered. Cheers, Rudi |
From: Pascal J. B. <pj...@in...> - 2010-03-12 10:33:03
|
On 2010/03/12, at 10:56 , Tobias C. Rittweiler wrote: > > I have code I know is not thread-safe, but it's nearly impossible to > write test cases that exhibit a bug reliably (or even just with a > certain percentage) because the window of interruption to trigger the > bug is just one, or two instructions. > > If I insert an explicit (thread-yield) at the right place, a test case > is very easy to write. > > Now I wonder how easy/difficult it would be to make the compiler > insert > calls to (thread-yield) randomly. Inserting on instruction granularity > sounds difficult to do if the compiler architecture wasn't made for it > -- especially because SBCL does not have a peephole optimizer --, but > perhaps between vops? (That's also where an manual insertion of > (thread-yield) could go, so..) > > If a feature like that was available, I hope that making my test suite > recompile the system again and again (to trigger different placement > of > the calls to (thread-yield), and running the test suite again and > again, > would result in exhibiting such bugs in say one out of 100, or 1000 > runs. > > Does anyone happen to know of prior art? If such a bug exists, I'd bet valgrind or a tool similar could detect it. That is, it should mean that some memory is accessed from several threads without proper locking, which is what valgrind helgind tool can detect. You could try to run sbcl with valgrind (but you'd detect sbcl bugs too), or you could implement a tool similar to valgrind for lisp programs. -- __Pascal Bourguignon__ http://www.informatimago.com |
From: <dhe...@te...> - 2010-03-14 04:02:49
|
> > I have code I know is not thread-safe, but it's nearly impossible to > write test cases that exhibit a bug reliably (or even just with a > certain percentage) because the window of interruption to trigger the > bug is just one, or two instructions. > > If I insert an explicit (thread-yield) at the right place, a test case > is very easy to write. > > Now I wonder how easy/difficult it would be to make the compiler insert > calls to (thread-yield) randomly. Inserting on instruction granularity > sounds difficult to do if the compiler architecture wasn't made for it > -- especially because SBCL does not have a peephole optimizer --, but > perhaps between vops? (That's also where an manual insertion of > (thread-yield) could go, so..) > > If a feature like that was available, I hope that making my test suite > recompile the system again and again (to trigger different placement of > the calls to (thread-yield), and running the test suite again and again, > would result in exhibiting such bugs in say one out of 100, or 1000 > runs. > > Does anyone happen to know of prior art? This is driving me batty; a few months ago I found a similar toolkit for C++, but the link is at work. Can't seem to find it. Basically, the user wrapped all atomic accesses and other suspected race points in a special template. Then when you run your program, each wrapped access is synchronized to a master thread. The master thread records the access orders, tries forcing different thread orders, detects deadlocks, watches for unsafe access, etc. It doesn't prove correctness, but could catch a large class of errors. - Daniel |
From: Daniel H. <dhe...@te...> - 2010-04-08 05:36:47
|
On Sat, 13 Mar 2010, dhe...@te... wrote: >> I have code I know is not thread-safe, but it's nearly impossible to >> write test cases that exhibit a bug reliably (or even just with a >> certain percentage) because the window of interruption to trigger the >> bug is just one, or two instructions. >> >> If I insert an explicit (thread-yield) at the right place, a test case >> is very easy to write. >> >> Now I wonder how easy/difficult it would be to make the compiler insert >> calls to (thread-yield) randomly. Inserting on instruction granularity >> sounds difficult to do if the compiler architecture wasn't made for it >> -- especially because SBCL does not have a peephole optimizer --, but >> perhaps between vops? (That's also where an manual insertion of >> (thread-yield) could go, so..) >> >> If a feature like that was available, I hope that making my test suite >> recompile the system again and again (to trigger different placement of >> the calls to (thread-yield), and running the test suite again and again, >> would result in exhibiting such bugs in say one out of 100, or 1000 >> runs. >> >> Does anyone happen to know of prior art? > > This is driving me batty; a few months ago I found a similar toolkit for > C++, but the link is at work. Can't seem to find it. What's a month? Here's the project: Relacy Race Detector http://groups.google.com/group/relacy http://groups.google.com/group/relacy/web - Daniel |