Language support for Linux device driver programming

Abstract

The success of any commodity operating system is determined by the quality of device driver support. Over the last decades, the computer hardware industry has been advancing at a rapid pace, putting high pressure on device driver developers. About 52% of the Linux kernel code is comprised by device drivers, accounting for close to 7.4 million lines of code. While managing such a huge code base is a challenge on its own, Linux device driver developers have to overcome additional obstacles. The complex, multithreaded programming model of the kernel creates a high potential for bugs and many of them result in kernel crashes. Device drivers constitute the largest and most unreliable component of the kernel.<br />This thesis analyses the root causes of the device driver reliability problem, and demonstrates how the current driver programming model can be improved to assist programmers in creating better driver code. To examine and test feasible improvements, a prototype language (called CiD) based on a subset of C was designed with the special requirements on Linux device driver development in mind. CiD features syntactical additions for three essential device driver code aspects: concurrency, synchronization and hardware communication.<br />The compiler is programmed with basic rules of the concurrency model of the kernel and is able to detect simple but common mistakes that lead to deadlocks. Additional consistency checks support the programmer in generating correct hardware I/O code.<br />Two device drivers have been converted into CiD code to test the language extensions and the implementation of the compiler. The results for concurrency and synchronization are satisfying:<br />race conditions in the data-flow are reported with a false positive rate of 6% to 21%.<br />The compiler also generates correct concurrency and synchronization code, thus mitigating the potential for deadlocks. The results show that hardware I/O generator leaves much room for improvement, since it generates 1.5 times more I/O operations than the original driver. Related approaches show that further optimizations can reduce the gap.<br />In conclusion, we find that device driver programming can be made more robust with only minor alterations to the existing programming model and little compiler complexity.

Die immer rasanter fortschreitende Entwicklung der Computerhardwareindustrie macht die Gerätetreiberentwicklung zu einer großen, wenn nicht der größten, Herausforderung in der Betriebssystementwicklung.<br />Der aktuelle Linuxkernel umfasst mittlerweile 7.4 Millionen Zeilen Gerätetreibercode, das sind in etwa 52% des Gesamtcodes. Während die Wartung von Gerätetreibern durch die enorme Codegröße zu einer Herausforderung wird, ist schon die Entwicklung eines einzelnen Gerätetreibers oftmals eine schwierige Angelegenheit. Neben der prinzipiellen Schwierigkeit von hardwarenaher Programmierung, verkompliziert das zugrundeliegende Programmiermodell die Treiberentwicklung. So ist Gerätetreibercode unter Linux hochgradig nebenläufig, wobei Programmierer auf zusätzliche Linux-spezifische Regeln achten müssen, um häufig auftrentede Fehler, wie Deadlocks und Race Conditions zu vermeiden.<br />Gerätetreiber sind somit die unzuverlässigste Komponente des Kernels.<br />Im Zuge dieser Arbeit wurde CiD, eine Erweiterung der Programmiersprache C, sowie der zugehörige Compiler, implementiert, um die Gerätetreiberentwicklung robuster zu gestalten. CiD bietet Sprachkonstrukte für Nebenläufigkeit, Synchronisation und Hardwarekommunikation. Der Compiler wurde mit Regeln des Treiberprogrammiermodells versehen, um häufig auftretende Fehler wie z.B. Deadlocks während der Entwicklung zu erkennen.<br />Um die Sprache und den Compiler zu testen, wurden zwei Gerätetreiber konvertiert. Die Ergebnisse sind großteils zufriedenstellend: Race conditions im Datenfluss eines Treibers werden mit einer "False-Positive"-Rate von 6% bis 21% erkannt. Durch die korrekte Generierung von Synchronisationscode werden häufig auftretende Ursachen für Deadlocks vermieden. Die Hardwarekommunikation bedarf einer Überarbeitung: Der Codegenerator erzeugt zwar korrekten Code, allerdings werden 1.5 mal mehr Hardwareoperationen im Vergleich zum ursprünglichen Code erzeugt. Verwandte Arbeiten zeigen jedoch, dass zukünftige Verbesserungen möglich sind.<br />Zusammenfassend lässt sich das Programmiermodell mit einfachen Mitteln robuster gestalten, wobei der Implementierungsaufwand für die Erweiterungen sehr moderat ist.<br />v