Simultaneity safari: A study of concurrency bugs in device drivers

Concurrency has been an issue in device drivers since the advent of interrupts. The ubiquity of multi-core CPUs increases the urgency to fix errors in the code (since the probability of manifestation increases) and to understand the issues involved as architec-tural priorities change (decreasing the probability that threads block). The particular challenges asso-ciated with concurrent programs, however, have not been handled appropriately in many cases. Since the development of tools to accurately test and debug programs that use concurrency hinges on a deeper level of understanding of concurrency bugs than cur-rently exist, this paper seeks to advance the state of the art by outlining real world examples of these bugs as they appear in device drivers. We have carefully examined the origins, scopes, and mitigation strategies for a collection of 98 real world concurrency bugs drawn from a pool of USB, FireWire, and PCI device drivers. Our study reveals several significant classes of bugs and a selection of interesting anomalies, both of which may be useful in avoiding or addressing concurrency bugs in other sit-uations. Specifically, we found that: (1) Around 20% of the bugs we examined were deadlock bugs, the ma-jority of which could be grouped into certain faulty assumptions which, once recognized, could be avoided in future development; (2) Of the non-deadlock con-currency bugs, nearly 43 % were caused by disconnec-tion event or power management handling sections of the drivers. This indicates that the hot-swappable functionality provided by the USB and FireWire pro-tocols entails a certain challenge particular to device drivers; (3) Although ensuring proper locking proto-col (esp. lock balance and lock initialization) is a well-studied issue in concurrency bug testing, a full 10% of all bugs examined in this study failed to correctly manage their locks