Intel teaches machines to build own device drivers
Game theory versus clumsy coders
Intel Labs is working to automate the tedious and error-prone process of writing device drivers and porting them to different operating systems.
Explaining the need for a tool that could synthesize device drivers, Intel Labs software engineer Arun Raghunath told The Reg: "A bunch of studies have shown that the prime cause of crashes in operating systems are device drivers. They're notoriously hard to get right."
Raghunath discussed the challenges of writing device drivers at the company's Research@Intel 2011 event at Mountain View, California's Computer History Museum this Tuesday, and explained what Intel Labs is helping to do to automate the process.
"The task of writing a driver is basically translating OS commands into internal device operations," he said. "What this means is one programmer needs to be an expert in both OS internals as well as know a lot about the device details."
And that's not the only problem. "Second thing is, they are manually interpreting these documents – there's scope for misinterpretation there," he added. "And that, we believe, is the prime cause for many of the bugs in drivers today."
The "we" to which Raghunath refers is the working group in which Intel Labs is participating, with the Australian information and communication technologies research center NICTA's Trustworthy Embedded Systems division (ERTOS), whose device-driver synthesis project is known as Termite. Funding has come in part from a Google Research Award.
According to Raghunath, one key to device-driver synthesis is having a sufficient set of specifications for both the device and the OS of the platform connected to the device. "The goal of this work," he says, "is eventually to have a tool chain that will work from formal specifications and automatically generate driver code that you can directly use."
Device driver synthesis: so simple in concept, so complex in reality (source: NICTA)
Those specifications are provided by the device and OS manufacturers, and aren't a separate synthesis-specific set of standards. "We will reuse the languages that are already being used by hardware developers for their high-level device models," he says. "We want to leverage that. We don't want to create a new standard – I think that's a non-starter."
Raghunath's research is based on what at first blush might seem an odd choice for algorithm development: game theory. "Our current research direction is that we're trying to apply game theory to [bridge] this gap between OS commands to device operations. That's what a driver involves: translating those OS commands to internal device operations. So we are trying to come up with algorithms to span that gap."
Games driver synthesizers play
When asked why his research was employing game theory, Raghunath explained: "You can view this as a game-play situation where, basically, the driver is one of the players in the game, and the environment – which is the OS and the device and whatever else happens there – is the other player."
Raghunath's tool sets the game in motion. "So when the driver makes one move, the environment is trying to push the state of the device in another direction. And so the winning strategy for you is to move in the state space without entering into any state wherein you'd be stuck forever."
As the game proceeds, the tool logs its winning moves and creates the driver from what it learns. But it's not as easy as it may at first seem. "The reason this is difficult is that you're dealing with a complicated state machine and you're dealing with incomplete information," Raghunath explains.
"As far as the driver is concerned, it can – for the most part – access visible registers, but not really look at all of the internal device state space. So how do you deal with this?" he asks. "How do you come up with the winning strategy in such a scenario? So what we found is that there is existing theory in the game-play situation which we could leverage."
The beauty part of this game-theory model is that the device-driver synthesis algorithm is fully independent of both the OS and the device that it's negotiating with. The device-driver synthesis algorithm would play the same game with the same basic rules, just with different "opponents" and different results.
Raghunath points to this device and OS agnosticism as a big win for his model. "The other nice point of this, if you think of the other big bottleneck in driver development, [it's] porting to different operating systems," he says.
"So if you have one device spec for, say, a printer. The nice thing is that once you have a device spec, say that you want to port your driver to BSD or Windows, you just get the corresponding OS spec, run it through the tools, and voilà, you have your driver for that."
That all sounds lovely, but when asked just how detailed the specs needed to be and how available they are, Raghunath said: "Good point. We do need at least all the externally visible interfaces of the device. What we do need in addition is the device behavior in response to a given command that it exposes."
Some cooperation between device manufacturers and platform developers will be required – or, at minimum, helpful. "I think the way we see this being used is – the hardware manufacturer, when they come up with their device, they also emit a spec, they give you a device spec with that, which they can give to platform companies or the OEMs who build the platforms into which these devices will go," he says.
Trade secrects kept secret
Raghunath anticipated the next obvious question: whether device manufacturers would fear that detailed specs would compromise thier intellectual property. "You can use a tool like this to essentially churn out the drivers for those devices without actually giving away intellectual property, that's what you're asking, right?" he guessed before being directly asked.
"Obviously the hardware vendor doesn't want to open up their IP to the whole world and give it away," he said. "But we believe that the level of detail that we need is high-level enough that, without giving their IP, just the high-level model – I think in typical hardware-manufacturer parlance – the high-level model is what we care about, and that's what we would work with."
But even with that high-level model, Raghunath said, "we do need to know some amount of details. What we do need to know is the theory of operations, what is currently specified in the device spec you get today is – say, for a NIC – is 'okay, send out a packet.' In order to send out a packet, the manual says you need to go right to this register, the set this up, set this up, and then go twiddle this bit and the packet will go out. What we need is at least that level of information."
But the device-driver synthesis tool can help. "What we need is a little more detail than that," he said, "because no one is going to tell you the theory of operation here – the tool has to figure out the theory of operation, basically, by looking at the formal device spec. To answer your question, we do need a little more detail, but I believe we don't need all the IP. So therefore we do believe this is viable going forward."
But don't fire your device-driver coders just yet. Raghunath told us that the group has "lots of technical issues still to [figure out]. What we have [now] is actually kind of initial signs of life that we can acually build something.
He also said that even if his first successfully automatically generated device drivers aren't well-optimized, they'd still be a value. "We actually also think that even if we don't get to the most optimized driver, even if we can churn out a functionally working driver, that's a big win, at least at the platform-validation level."
Even a clunky driver wuold save time and effort. "The time that it takes for you to actually just come up with a functional driver that you can then use to validate the rest of your platform," he said, "we can just cut that entire time down to zero – well, or a few minutes."
When asked when his tool wil be able to handle performance optimization, Raghunath chuckled. "We are far from that yet, "he said, but added: "We do believe that we can get pretty close."
For a deep dive into the concepts behind automatic device-driver synthesis, you can dig into a 14-page research paper from a group of NICTA and University of New South Wales boffins, filled with highly detailed nitties and gritties. ®