Gimme Hardware/Software Interface.

Ch-ch-changes.

2009-07-14T10:13:00.001-07:00

As some of you know, I'm no longer at VMware. It feels a bit like leaving home. VMware took a chance on me as a new college grad way back in 2000, and taught me a lot along the way. I will miss my colleagues, many of whom are excellent, and will always be proud of what we accomplished together. I expect VMware will continue to be successful both technically and as a business, and they treated me very well. I did not leave due to a long list of complaints; it simply had been nine years, and I had decided it was time to try something different.

I've been waiting to update this blog until I had a clear idea of what that "something different" was. My long fast in the woods is over: I'm working in the search team at facebook, trying to make a whole lot of data available to a whole lot of users. You might think that the title of this blog is less relevant than it once was; search sounds, initially, like an application, pretty high up the abstraction stack from the hardware. This is true, but search is also a special application, enormously demanding in computational resources. We're pushing the hardware close to its limits in several dimensions simultaneously, and some knotty systems issues arise. I'm not ready to talk about them in any depth yet, not out of secrecy, but ignorance. I'm still learning the ropes here, and any attempt to drop science at this point would just be silly.

Irfan's blogging.

2009-02-13T09:16:00.000-08:00

My colleague over in VMkernel Irfan Ahmad has a blog. Irfan often has good ideas, and is a clear and effective writer; if you find the content here interesting, you might enjoy him. I've added a link to this blog's marginalia.

VProbes community forum

2009-02-10T13:57:00.000-08:00

VMware is now hosting a community forum for VProbes. Come party with us.

Cantrill and Bonwick get all concurrent-y up in there...

2008-11-04T15:32:00.000-08:00

Bryan Cantrill and Jeff Bonwick of Sun Microsystems co-authored an excellent position piece on concurrency in the ACM Queue. It's about time someone stood up to those short-selling concurrency bears. Take heart, young coders! Correct concurrent software does appear out there from time to time, no matter what your grad TA tells you!

The section on hard-won lessons from developing concurrent software warmed my heart; VMware's virtual machine monitor team has learned the same lessons, and I for one can endorse their list wholeheartedly.

With any legit publication like this, the authors struggle to balance completeness and concision, and some things did not make the cut. So, don't take it as criticism that I would add just one item to their list, that has powerfully increased our ability to ship concurrent code (drumroll): lock ranks. Huh? Lock ranks! We have imposed an explicit, compiled-in partial order on the locks in our system. Acquiring locks out of order causes a runtime failure in debug builds. I've seen some engineers regard this discipline as a sort of "training wheels" for concurrency, but it has benefits even for seasoned vets.

Ranks force developers to think about layering before writing synchronization code. Will this subsystem be touching guest memory? Will it require synchronous remote execution on other CPUs? Will the user-level portion of our software ever need to acquire this lock? Etc.
This has strangled many a rare deadlock in the crib. I agree with Bryan and Jeff that, in practice, a deadlock is not too hard to debug post-mortem; however, post-mortem is too late if the core comes from a customer site. A rank violation is much, much easier to catch in testing than a deadlock, since it only depends on the single-threaded path leading an order violation, as opposed to a concurrent race. This performs the magic trick of reducing a concurrent QA problem (exercise every lock interleaving) to a serial QA problem (cover every path that acquires a lock).
The same discipline can be applied to other synchronous services in the system. For instance, like many other concurrent systems, our VMM has a "crosscall" primitive, which lets a caller synchronously run code in a remote VCPU. This can lead to lock-like dependency cycles, where, e.g., VCPU 0 holds lock A and crosscalls VCPU 1 which is blocked waiting for A. To prevent this, we encorce the rank metaphor for crosscalls, too; a crosscall while holding dangerous locks fails just as a misorder lock acquisition would.

While the rank discipline was initially adopted for deadlock avoidance, the structure it imposes on the system is even more valuable. The lock ranks, in isolation, provide a succinct description of the system's organization. If you take the partial order of the lock ranks, associate them with their controlling subsystems, you can construct a "wedding cake" chart of the system automatically. I.e., if subsystem A relies on subsystem B, then locks protecting A's data will always have lower rank than B's. The top of the cake are "pure" clients, which are never entered from other subsystems; the tippy-top layer of frosting are the handful of points that we enter the VMM from the guest, where we always know that no VMM locks are held. The bottom of the cake, corresponding to the highest ranked, "leaf" locks, from which no other code is reachable, correspond to the most basic, omnipresent life-support facilities: logging, deferring work to a less pressing time, panic'ing, etc.

Bryan advertised the article in an excellent (though more in-character) blog post. Out here in the wild wild web, Bryan lets the invective against transactional memory advocates ("shysters", in his estimation) flow a bit more freely. I am not sure the hype surrounding TM is malicious; I suspect it is your garden-variety, low-grade academic over-enthusiasm, born partly from needing to exaggerate in grant proposals and paper abstracts, and partly from honest optimism. Think "microkernels," not "laetril."

Hey, remember microkernels? For about a decade, systems journals were dominated by papers that took for granted that microkernels would dominate general purpose OS'es. This religious belief that running parts of the operating system in separate address spaces would make everything easier and better begat all sorts of meaty sub-problems, like doing fast synchronous cross-address-space RPC, and building little IDL compilers that provide binary compatibility for clients when driver binaries change and ... so on. I suspect TM will take a similar course, dying not with a bang, but a whimper, and ten years hence.

It's interesting to me that, as with microkernels, one of the principle reasons TM will fail is the messy, messy reality of peripheral devices. One of the claims made by microkernel proponents is that, since microkernel drivers are "just user-level processes", they'll survive driver failures. And this is almost true, for some definition of "survive." Suppose you're a microkernel, and you restart a failed user-level driver; the new driver instance has no way of knowing what state the borked-out driver left the actual, physical hardware in. Sometimes, a blind reset procedure can safely be carried out, but sometimes it can't. Also, the devices being driven are DMA masters, so they might very well have done something horrible to the kernel even though the buggy driver was "just a user-level app." And if there were I/Os in flight at failure time, have they happened, or not? Remember, they might not be idempotent... I'm not saying that some best-effort way of dealing with many of these problems is impossible, just that it's unclear that moving the driver into userspace has helped the situation at all.

Similarly, peripherals are a gotcha for TM, because, as Bryan and Jeff point out, they're not memory. There will never be a way to make TM transactions persist across system calls, unless you find a way to untransmit network packets. That means that TM is now and always will be* useful only for raw computation: AVL trees, mp3 encoding, sort, and whatnot. Those are important facilities, but they're also the sort of thing that are coded once, by an expert, and used forever thence from a library, so "ease of programming" is not the highest priority. Even if "ease of programming mp3 encoders" is your metric, it's unclear that TM is an across-the-board win. What happens when you set a debug watchpoint on memory that's accessed transactionally? Oh, sorry! Didn't mean to spoil the punchline from someone's PhD thesis...

Not so simple anymore, eh?. If you can remember way back to your undergrad days, locks probably seemed easy at first, too.

* I'm exhausted with that weasel phrase "current TM implementations"; transactions will never, bloody ever span I/Os, and that's the relevant limitation.

Done projecting. Time to reflect?

2008-10-08T10:00:00.000-07:00

Well, I've been back from U of I for over a month, so it's more than about time I got to writing it up. Interacting with people who are just as passionate about computing, but looking at it from completely different perspectives, is a soothing tonic for a systems person. It reminds me that these systems we build don't just blink in datacenters anonymously; when they function right, they do real, useful things that matter deeply to others.

I think my talk went fine, as things go. If I'd had one thing to do over, I would probably not have pounced so furiously on Crispin Cowan's Q&A flamebait about how everybody knows VMs are slow; Crispin, that's one for you, there.

Reflections|Projections 2008

2008-10-03T07:56:00.000-07:00

I'm going to be at Reflections|Projections 2008 this weekend. I'll be talking about the role virtual machine monitors can play in systems research, using VProbes as both an example and exploratory tool. It's an honor to have my name on the same web page as some of my fellow speakers. Curious parties should swing on by UIUC's1404 Siebel at 4pm Saturday.

Why I am not a C++ programmer: ten years on.

2008-08-01T15:55:00.000-07:00

As a far-too-full-of-myself CS undergrad, I wrote, "Many C++ critiques are available online, but none of them address what I regard as C++'s fundamental failure..." Man, it's painful linking the above. I wrote it ten years ago, as a TA for a course that had previously been taught in C++. Despite trying way too hard to project an unearned air of worldly cool, in most ways I stand by my claims. C++ is a broken notation: its attempts at being high level make it inappropriate for serious systems work, and its attempts at being low level make it even worse for applications. Incidentally, it has a truly unfortunate culture attached to it, rife with books, tutorials, even conferences which purport to be about "design," but are in fact about about "delegation," "factories," etc., and Cartesian products thereof. None for me, thanks.

Why the stroll down memory lane? Because today a coworker introduced me to Yossi Kreinin's C++ Frequently Questioned Answers. I can no longer claim that "none of [the C++ critiques online] address ... C++'s fundamental failure," as Yossi's kills them all. Folks, we are in the presence of greatness. I feel as Salieri must have upon first encountering the works of Mozart.

What is VProbes' relationship to DTrace?

2008-07-24T12:45:00.000-07:00

VProbes has a similar set of design goals to DTrace: to be safe-yet-programmable, and be of global scope. DTrace is permissively licensed open source, that pre-dates the existence of VProbes, so why in heaven's name don't they share code?

The short version: virtual machine monitors aren't kernels, even though they run at CPL 0. Those curious about the hair, though, please read on...

Before breaking ground on what would eventually become VProbes, I investigated a straight port of DTrace. I went so far as meeting with VMware legal to figure out whether the CDDL said what it appeared to say ("steal this code and make a fortune selling it for all we care, as long as you're not Linux"). However, there are some daunting impedance mismatches between DTrace as it exists today and the world in which our VMM must live. An incomplete list of gotchas includes:

Our VMM needs to fit in 4MB of virtual address space, about 3 of which are needed for the translation cache. So, we care passionately about code and data size in ways that would be simply moronic for any other software project. Our internal mailing list regularly has knock-down, drag-out arguments about changes that bloat the monitor by 700 bytes; unless you're developing firmware, you should not even waste the time worrying about anything that impacts real-world memory usage by less than a MB or so.

VProbes' current runtime impact is around 50KB, and we frankly consider it slightly overweight. Perhaps DTrace's data structures could be trimmed to fit in this environment, but text is more challenging. That's not to imply that DTrace should be tinier; DTrace is bigger for all the right reasons, mostly that it does more than VProbes does.

Our VMM does not provide any dynamic allocation facilities. This is one of the major reasons that efforts to port third-party software, even kernel software, to the VMM fails. Reading the BigAdmin discussion, DTrace appears to self-tune many of its buffers' capacities automagically, which is great, and makes DTrace better for its users; however, it's just not feasible for our constrained environment.

We care about applications where probes are always enabled. VMware's VMM doesn't have any third-party extension mechanism, safe or otherwise, at present. VProbes provides a few toeholds for programmatic extension. This "extension" use of VProbes is different from the "monitoring" use that it shares with DTrace. It drives performance trade-offs that would simply be inappropriate for DTrace. E.g., rather than interpret bytecodes, VProbes compiles user probes to x86-64 machine code. Assuming you're on an x86 makes perfect sense for VMware, and would be completely insane for a system that also needs to work on sparc.

Of course, DTrace, being software, is infintely malleable, and you could probably start with a tarball extracted from the OpenSolaris project and eventually end up with something that satisfies all of the constraints our VMM imposes. But the result would be ... un-DTrace-like. Suppose you contort DTrace so that it doesn't care whether interrupts are enabled, sacrifices some speed, flexibility and features so that it fits in less than 100KB of virtual address space, and picks (tiny) static buffer sizes. How interested would the upstream DTrace developers, and ports of DTrace to other kernels, be in integrating my diffs? How hard would it be to integrate the stream of bug-fixes from DTrace-at-large into our heavily hacked code base? Would DTrace's owners even consider bugs that only arose in my insanely contorted set-up to be "bugs"? It seemed we'd be a dead-end fork of DTrace, neither able to help the parent project, nor selfishly benefit from its further development.

Some have said that rolling our own runtime is an instance of not-invented-here syndrome; I take the charge seriously, and can see how it would seem that way from the outside. I strongly disagree. I realize that good work happens outside VMware, and consider DTrace shining example of such. I agonized over this decision, not least because I respect Bryan, Mike and Adam both as engineers and human beings. I am no Torvalds-esque DTrace hater. There are things that DTrace will continue to be hugely superior at. Then again, not having to wait for Microsoft to port DTrace to Windows is pretty neat too...

VProbe demo

2008-06-13T15:27:00.000-07:00

Can you tell I'm not used to giving talks sitting down? Sorry about the continual side-to-side oscillation; I promise to insist on standing up in the future.

If this VProbe stuff looks fun to you, perhaps it's timeyou got beta'ed up?

Windows Host Quoting Gotcha, and the VProbe Toolkit

2008-06-13T10:04:00.000-07:00

Workstation 6.5 is now in public beta. It includes experimental support for VProbes in the guest, virtual machine monitor, and a few spots in the virtual hardware. We'd like to invite anybody curious about vprobes to give it a whirl.

A common problem came up on the forums yesterday: if you're using VProbes from Windows' native command-line, you'll soon notice that the following:

C:\> vmrun vprobeLoad foo.vmx '(vprobe VMM1Hz (printf "greetings windows\n"))'

produces the cryptic error message:

vprobeLoad: error: unknown ident windows\n
vprobeLoad: 0 warnings, 1 errors

What gives? In short, cmd's weird quoting. As far as I can tell, single quotes are basically the same as double-quotes, except cmd will only nest like-with like, so cmd ends up passing along the string '(vprobe VMM1Hz (printf greetings windows\n))'. Check the forum post for the band-aid solution for cmd; I predict you'll only be able to tolerate the syntax for cmd one-liners so long before you give up and install cygwin.

Once you embrace cygwin, you might as well go whole-hog and get the vprobe-toolkit. The abstraction level of vp is very low; while the parentheses might remind you of scheme for a while, pretty soon the semantics will remind you of assembly language. This was an intentional choice: since bugs in the vp compiler can nuke your system, we're motivated to keep it as simple as possible. While it's possible to use vp directly for machine-level things (e.g., instruction or stack profilers), for more complex tasks automatic code generation is more appropriate.

Introducing Emmett

Emmett is a small language that provides C-like type, expression, and conditional operators, some syntactic sugar for aggregation, and automatic inference of type for undeclared variables. The vprobe-toolkit provides a wrapper script, named "vprobe", that invokes the Emmett compiler on your input, loads the resulting VP into the target VM, and runs user-specified pretty-printers on your output. E.g., "vprobe -a" pretty-prints sorted aggregates, and "vprobe -s" pretty-prints stacks.

Where in VP, you'd have to write:

(defaggr a 1 1)
(vprobe USEC:1001
 (do
  (aggr a (VCPUID) ((curprocname)) 1)
  (logaggr a )))

Emmett produces the more readable:


USEC:1001
{
  a[VCPUID, curprocname()]++;
  logaggr(a);      # OK, this is a lot of output.
}

There are a bunch of examples in the cookbook subdirectory.

I want to emphasize that Emmett is a replaceable component. If you're a python programmer, and curly braces make your shoulder blades clench with rage, feel free to write your own little language...

Pragmatics

vprobe-toolkit is open source. We've licensed it with a variant of the BSD license, which VMware's lawyers assure me means you can basically do whatever you want with it; if you're feeling paranoid, though, please run the license file past your local lawfolk rather than taking my word for it. You'll notice the link above is to a subversion repository, not a download page. In its current state, it would be inappropriate to expose it to those unwilling to hack a bit; if ws 6.5 is currently in "beta", this is probably somewhere past "prototype" but not really "alpha" yet. Join us!

Herlihy & Shavit: The Art of Multiprocessor Programming

2008-04-05T10:25:00.000-07:00

(Disclaimer: I've taken courses from Maurice Herlihy at Brown.)

So! Concurrency's the hot thing. Intel says so. The technical bookshelves are groaning with books about concurrent programming. Most of these books are occult thread package tutorials; they walk you through using Java's monitors, or pthreads' conditions and mutexes, or Windows' Events or what have you, often with the same shopworn collection of toy problems: philosophers producing elves who dine on ... eh.

The Art of Multiprocessor Programming is different. It is, in part, a theory book. Don't panic! The use of formal reasoning is tasteful; a teaspoon or so of actual math is necessary when designing concurrent programs, because our intuitions can fool us. However, the authors don't overwhelm the reader; an undergraduate level background in CS theory is not necessary to appreciate the book. If you can read the word "tuple" without giggling, you'll be fine.

More importantly, though, the actual data structures and algorithms that are highlighted in this book are not the same-old. Sure, mutual exclusion is discussed, but it's with a focus on implementing mutual exclusion, which is a topic dear to me. Most strikingly, the majority of the examples in the book are of lock-free data structures. You'll find lock-free linked lists, hash tables, trees, etc.

In my day job, I treat lock-free concurrent data structures as, well, not quite black magic, but certainly Powerful Medicine. They take a lot of thought, bugs can hide in them for years, reasoning about their performance is non-trivial, even compared to locking, and frankly, not every programmer is up to maintaining such code; but when you need them, you need them. If the multi-core popular press is to be believed, more and more of us will be needing them in the near future. In as much as this is the first off-the-shelf collection of useful, debugged lock-free data structures, it's an invaluable contribution. Go buy it. Even if you never use a counting network, it will make you a better programmer. It's also the most writerly book about programming you'll read all year; Herlihy's deadpan humor is a welcome break from the super-serious tone programming books usual adopt.

However. ...

Reading between the lines a bit, I see this book as part of a larger project, which I refer to as "pop concurrency*". "PC" is a loose confederation of researchers in programming languages, compilers, architecture and operating systems whose implicit goal is to make concurrent programming, well, "easy." Much, much easier, anyway. Of course, sequential programming isn't all that easy. Before the current fashion in concurrency, the "software engineering" community was haranguing us about the expense, difficulty, and intractability of programming. We've made only incremental progress in making sequential programming easier; garbage collectors and safe languages are probably the most important contributions so far, ad they are not order-of-magnitude revolutions over traditional tools.

It's cheap and easy to make negative predictions about ambitious research agendas. E.g., making fun of strong AI people stopped being fun for me about 10 years ago. But at the risk of seeming to make a cheap shot, I am really, really skeptical about how easy we can make concurrent programming. Even if the thicket of hardware and software problems around transactional memory** resolve, I suspect TM only seems easy because it's the devil we don't know. After all, locks sound easy too: just identify the shared data and wrap mutexes around it! Sounds simple enough, doesn't it? It took years, and lots of big systems being constructed this way before problems like priority inversion were framed, and many years thereafter before they were solved. Paraphrasing Fred Brooks, there's no silver bullet; concurrency is hard not because we're Western linear Cartesian dualist squares, or because of bad notation, but because it's actually hard. Like all software, the easy parts are quickly discovered and factored, and the code that's left to be written represents real problems to solve.

* Warning: I made this term up. Do not use it when trying to sound intelligent.
** E.g.: how do you debug a TM program? When you're stepping through a transaction, won't it basically always fail? System calls during transactions? I/O? What if you've DMA'ed into or out of a piece of physical memory that's being transacted-upon? Smarter people than me are thinking about these problems, but man. They are non-trivial.

dtrace.conf(08)

2008-03-15T04:47:00.000-07:00

DTrace's (first?) unconference in San Francisco yesterday was a blast. I attempted a VProbes demo with Thursday morning's Fusion bits from our development branch, which I would rate a qualified success. The VMware Fusion UI crashed right after plugging into the projector, but the VProbe stuff worked. In case it was unclear to anybody in attendance, yes, there really was a Windows VM struggling on in the background; sorry you couldn't see its screen. I'm told video will be up shortly, so stay tuned. In the meantime, I let slip that we're attempting to ship VProbes in Workstation 6.5; all of you ESX users who asked me about VProbes on ESX, I have no official news for you, but yes, we feel your pain.

I enjoyed meeting like-minded folks, putting faces to names, and getting a glimpse of the DTrace community's roadmap. Having slept on it a bit, both of Bryan's demos stand out.

As Bryan admits, distributed DTrace as implemented thus far is nothing that you couldn't do with ssh and a lot of elbow grease. But I'm excited about the implications of this project. A wire format for generalized aggregation could provide a lingua franca between DTrace and other sources of aggregation data (*cough* VProbes). You can actually imagine "aggregation" in this VProbes/DTrace sense overlapping with "aggregation" in the RSS sense: administrators "publish" streams of worthwhile data from individual systems, and trees of aggregators pool together broader and broader summaries of these aggregations by talking the same protocol upstream.

Which brings me to dtrace.conf's well-planned climax, Bryan's graphical DTrace demo.

VProbes' textual UI feels like a throwback to me; when showing it to a skeptic, you can almost read the thought balloon floating over his head: "OK, you just typed something weird into an xterm, and it spit something out. It's 2008. I wonder why he expects me to care. Actually, I wonder what the stock market's doing. Oh, wait, this VProbe guy is still talking." But what can I do? I'm a programmer, it's a programming language; how else do I demonstrate its power and more importantly, its flexibility? But people (quite correctly) expect data to be presented visually, because our visual systems are the most reliable, highest bandwidth way of getting quantitative data our brains.

Most graphical tools, though, have only one trick: plotting some scalar data against time. It's amazing how little we've really improved past xload in this regard. Bryan's demo was the first graphical tool I've seen that captures some of the combinatorial and iterativepower of a dynamic instrumentation system: finding an anomaly, then breaking it down by foo, then by bar, backtracking a bit because foo isn't as important as you initially thought, then keeping only the purple bars, etc. Sure, there will always have to be something like a programming language underneath for full generality, but a tool like this has the potential to capture much of the benefit with much less investment of intellectual energy. We professional programmers tend to, err, overestimate others' passions for learning new languages.

It took courage and generosity of spirit on the part of my hosts to provide a platform for what could be viewed as a competing technology at their conference. So, thanks guys. I would (and did) argue that VProbes and DTrace are complements. Users need visibility into the virtualization stack, and we're going to try to give them as much insight into that layer as possible with VProbes, but we're happy to cede higher levels to OS tools, including DTrace. Consider for example TCP. In the grand scheme of a real application, TCP is a very low layer, but from the virtual hardware's point of view, TCP is a modestly high-level protocol to reconstruct from what's sitting on the wire and in guest memory. DTrace will always provide superior visibility into what is really an OS level of abstraction. In my mind, the interesting question is how to weave together these different instrumentation engines for different levels in the stack. Hopefully we'll have something to show for our efforts at dtrace.conf(09).

MacOS X/DTrace tryst ends in tears.

2008-01-23T09:00:00.000-08:00

See Adam's break-up note. This also got picked up on slashdot.

My thoughts, in no particular order:

Shame on Apple. What is the point of building system-wide infrastructure that any random process can opt out of? Forget about DRM; what about legitimate uses of DTrace for system health monitoring? Won't all malware be sure to set the "don't dtrace me" bit now?
This highlights the value of having system-wide instrumentation at the hardware level. Systems like VProbes do not allow a process, or indeed even a kernel, to "opt out." If the VM's user wants something traced, he gets it traced, by golly.
On the other hand: if code really wants to evade VProbes, DTrace, debuggers, etc., the arms race is heavily stacked in favor of the sneaky code. E.g., suppose you've got some super-s3kr3t, double-plus DRM code that you absolutely don't want instrumented with DTrace's pid provider; on x86's, you could easily checksum the text to find smashed-in int3's. More elaborate evasion/detection schemes are possible too, similar in spirit to the VMM detection techniques summarized in our HOTOS paper about VMM detectors from last year. We concluded that creating a completely invisible VMM is an ill-posed problem, and trying too hard is a waste of time. I believe a similar dynamic is at work with dynamic tracing systems.

Ouch, Theo!

2007-10-25T15:02:00.000-07:00

Slashdot, by way of kerneltrap, picked up a hilarious flamewar over on the OpenBSD mailing list. The short version is that some guy thinks virtualization involves code, and code has bugs, and therefore virtualization is only ever bad. Or something. I'll leave the histrionics to those who think there's a substantial argument lurking in there somewhere, but I just couldn't help myself when I saw the following appeal to authority:

While x86 hardware has the same page-protection hardware that an IBM 390 architecture machine has, modern PC machines are a mess. They are architecturally so dirty, that parts of the video, keyboard, and other IO devices are interfaced with even to do simple things like context switching processes and handling interrupts. Those of us who have experience with the gory bits of the x86 architecture can clearly say that we know what would be involved in virtualizing it, and if it was so simple, we would not still be fixing bugs in the exact same area in our operating system going on 12 years.

I'd like to call "BS" on the above claim of inscrutability. No, you do not dork around with, e.g., the video card, to switch contexts. You may indeed mess about with an I/O device in "handling interrupts," but only because, gee, there's an interrupt to handle. In my seven years of debugging every goofball OS written for the PC on our VMM, I haven't encountered a single task switch that wasn't basically some variation of disabling interrupts, taking a couple spin locks, switching stacks, and changing the page table pointer. You know, kind of like it is on every architecture on the planet.

Denier's Dilemma

2007-09-05T07:44:00.001-07:00

Shankar Vendatam at the Washington Post writes:

The federal Centers for Disease Control and Prevention recently issued a flier to combat myths about the flu vaccine. It recited various commonly held views and labeled them either "true" or "false." Among those identified as false were statements such as "The side effects are worse than the flu" and "Only older people need flu vaccine."
When University of Michigan social psychologist Norbert Schwarz had volunteers read the CDC flier, however, he found that within 30 minutes, older people misremembered 28 percent of the false statements as true. Three days later, they remembered 40 percent of the myths as factual.

...

(By way of the often excellent, and often nutty, Overcoming Bias.) I'm reminded of the difficulty I've had explaining that VMs and security don't really have much to do with one another. Is it possible that, in attempting to explain something really convoluted to a crowd that barely cares, we sometimes do more harm than good? If you find yourself in a situation where you're in possession of a counter-intuitive result, that's really hard to explain, but important none the less, what's the ethical thing to do, given that saying "X" will register in a lot of folks' minds as "not X"?

Presenting VProbes

2007-09-01T11:35:00.000-07:00

VMworld 2007 is coming up, and I'm more excited than usual this time around. Alex Mirgorodskiy, Robert Benson and I will be demonstrating a piece of technology called VProbes.

VProbes was born from an experience that many of you have probably shared: I was wondering why my computer was so slow. I have whiled away many hours over the years investigating this question, and I have rarely gotten a solid answer. Sometimes the slowness is intermittent, and by the time I've developed a theory, it has already disappeared. Other times, the diagnostic tool I want to run (top, or strace, or ltrace, or what have you) isn't installed in the VM, because it's a purpose-built VM with a constrained set of user-land tools. Or, the tools are there, but the system is not in a state to allow me to use them; e.g., it's hung early in boot, and I can't log in to the system. Still other times, I never really scratch the surface of the problem because it's Windows and I don't know my way around.

VProbes attempts to provide a set of tools for answering the question, "What the heck is this computer doing?" It's an open-ended question, so vprobes is accordingly open-ended, as well. In its current form, it provides an interactive, safe way of instrumenting a running VM at any level: from user-level processes down to the kernel, and even into VMware's VMM and hypervisor, if need be.

We also attempt to solve the "unfamiliar tools" problem, by papering over (to the degree possible) the differences among operating systems. There is a broad consensus among Windows and the UNIX flavors about the abstractions that operating systems provide: all major operating systems provide threads, a tree of named processes, named files in a hierarchical namespace with byte contents, sockets, etc. VProbes tries to get by on enough guest-specific knowledge to "wrap" those differences. Thus, for Windows, Linux, and any other operating system that VProbes can be "taught" to understand, the following vprobe script provides a rough and ready approximation of the top UNIX utility:

Guest_TimerIRQ ticks[curprocname()] <- 1;

"Big deal," you might be thinking. "I had top already." Well, you didn't have top on Windows. And you didn't have it while the machine was booting, or shutting down. And you certainly didn't have it if the machine in question was a virtual appliance that doesn't even allow logins.

Anyway, if this sounds interesting to you, please consider attending our VMworld breakout session on the 13th, from 3:30 to 4:30, numbered TA70. I should warn that this is basically a research prototype: we haven't committed to putting VProbes in any upcoming VMware product, and indeed, might never ship it at all. We're putting what we've got in front of the public now because we are at the point where we need feedback from real users to improve VProbes.

In the "credit where it's due" department: we owe an enormous debt in our thinking about this problem to our colleagues at Sun. I've never hidden my admiration for DTrace. We hope to improve on it. First, we are aiming to provide a Dtrace-like tool for other commercially important operating systems than Solaris. Second, VProbes can combine with other virtualization-based techniques in powerful ways. For example, VProbes and deterministic replay combine to make the most potent tool that I'm aware of for debugging intermittent performance anomalies. I'll leave applications to VMotion, snapshots, etc., as tantalizing hints...

Hmm. That's not what I think I wrote...

2007-08-01T09:14:00.000-07:00

I'm perplexed by this peculiar interpretation of our HotOS paper:

Security has been touted as one of the benign by-products of virtualisation – but according to a recent study, that’s no longer the case.

Huh? "Security" is a big concept, covering many possible applications. Our paper is just a tiny footnote in a complicated discusssion about the role of VMMs in providing security; in fact, to the extent we challenge conventional wisdom at all, we suggest that the purported security threat posed by VMM-based rootkits is non-existent. To get out the sock puppets: VMMs are always detectable, which is a good thing.

I think I see where the author got a bit tripped up reading our paper, though. Currently, there is a trend for malware to disable itself in the presence of VMMs. We argue that this trend cannot continue, not because VMMs are becoming undetectable, but because VMMs are becoming too ubiquitous for malware authors to ignore. Note that this current fad among malware authors of refusing to do dirty business in a VM is not an inherent security benefit of VMs!

A nice thought experiment when thinking about security applications of virtual machines is to replace "VM" with "laptop." Suppose, for the sake of argument, security researchers started building honeynets out of laptops, because it was more economical to do so. For a while, malware authors might decide to detect that they're running on a laptop, and refuse to do so, in order to thwart the security researchers. (Note, of course, that it's completely trivial for user-level software to figure out what sort of hardware platform it's running on; this information is intentionally, usefully exposed by, e.g., /proc nodes in Linux, or the \Device directory on NT, etc.). The answer to this situation is not to attempt to cloak the laptop-iness of the hardware platform, though; attempting to do so is a bottomless pit of wasted effort. Instead, we simply observe that there are a lot of laptops out there, and figure that, in the long run, malware that refuses to run on laptops will be giving up too many targets to represent a Nash equilibrium for the black hats.

Honestly, though, I'm not that happy with the paper. We're telling a complicated story, and I'm not sure we tell it clearly enough. Even if Manek Dubash's misinterpretation were intentional*, the fact that it the paper can even be plausibly distorted to read the way he suggests means that, at some basic level, we've failed. Good technical writing is hard.

* Purely speculating, here. I'm not casting aspersions on anyone's intentions; an honest misunderstanding is, sadly, possible.

Overcoming bias

2007-07-12T08:15:00.000-07:00

Not strictly virtualization-related, but overcoming bias is one of the more consistently interesting cross-disciplinary blogs I've come across. The same sorts of cognitive biases that cause people to make bad decisions about their happiness, finances, political preferences, etc., often cause errors in software engineering. Pawing through Wikipedia's list of cognitive biases, I can associate almost every single bias with one (or more) mistakes I've made in my professional life. Optimism bias? Zounds, what engineer isn't guilty of it on a daily bias? Information bias has often led me to waste hours in debugging collecting useless trivia. Some have even entered the lore of computing; ingroup bias is nothing but "NIH syndrome."

While "overcoming bias" is certainly a laudable goal in many professional fields, I wonder about its tractability. These biases are clearly hardwired, and I suspect no amount of mindfulness will prevent us from committing them. Getting rid of one of these well-attested biases would probably require the neurological equivalent of, e.g., making humans able to digest grass, or giving a human the VO2Max of a horse. Oh well; if nothing else, at least being aware of our limitations as thinking machines might prevent us from trying anything too impossibly stupid...

BluePill detection in two easy steps.

2007-07-02T11:09:00.000-07:00

In our HotOS submission, we alluded to a large number of theoretically possible methods of detecting the presence of a hypervisor. I'm not sure which of these many ways the well-publicised BluePill challengers have chosen, but I thought I'd make things a bit more concrete.

In our paper, we outline family of detection methods based on resource consumption. In short, the hypervisor must use cache, memory bandwidth, TLB entries, etc., in the course of multiplexing the CPU. A guest can be made intentionally sensitive to these resources in order to detect a hypervisor. For instance, you can obtain a good estimate of the effective size of the hardware TLB with psuedo-code like the following:


PPN oldPhysPage, newPhysPage = Alloc...();
VA oldVirtAddr = MapSomewhere(oldPhysPage);
VA newVirtAddr = MapSomewhere(newPhysPage);
memset(oldVirtAddr, 0x11, PAGE_SIZE);
memset(newVirtAddr, 0x22, PAGE_SIZE);
PTE=base of hardware page table;
for (i = 0; i < BIGNUM; i++) {
   PTE[i] = MAKE_PTE(oldPhysPage);  // map old page
   (void)*(volatile char*)(i * PAGE_SIZE); // bring it into the TLB
}
/*
* TLB now contains between 0 and BIGNUM old mappings.
* Now modify the PTEs *without* flushing the TLB,
* and wait for the hardware to leak an entry
*/
for (i = 0; i < BIGNUM; i++) {
   PTE[i] = MAKE_PTE(newPhysPage);  // map old page
   if ((*(volatile char*)(i * PAGE_SIZE)) == 0x22) {
      printf("apparent tlb size: %d\n", i);
      break;
   }
}

OK, so you can size the TLB. So what? Well, just run the above loop twice, but the second time, stick an instruction that's guaranteed to trap out to the hypervisor (e.g., CPUID) before the loop. On bare hardware, this inocuous instruction will have no impact on the TLBs. In the presence of a hypervisor, the instruction will either flush the TLB entirely (on current Intel VT implementations), or, if you're on a clever SVM hypervisor that uses the ASID facility to avoid TLB flushes on every hypervisor invocation, at least 1 fewer TLB entry. (Every hypervisor must at least read the VMCB's exit code, requiring 1 data TLB entry. For increased sensitivity, you could also detect the VMM's code footprint by rejiggering the above to measure ITLB entries, an exercise left to the reader. Hint: the return instruction is a single byte on x86.)

This detection technique uses only TLB capacity, but a more sophisticated approach could easily include the hardware eviction policy. We could also apply these same technique to instruction and data caches. (Even the x86's coherent data caches can be sized using the INVD instruction, which discards cache contents without writing back dirty data.) A less naive approach that uses the hardware's event-based performance monitoring support (RDPMC and friends) would have an even richer menu of options for noticing virtualization-induced perturbations.

I've seen zero evidence that Rutkowska has pondered resource-based detection attempts like this, or indeed, any attacks more sophisticated than a "go-slow" loop between reads of the PIT. It is hard for me to imagine a "hypervisor" worthy of the name that doesn't leave noticable traces in resource usage. In fact, to the degree that a hypervisor goes to heroic lengths to prevent such a detection technique, e.g., by running a hardware-accurate cache simulator on every guest memory access, it will only open up wider timing discrepancies for the guest's HV-detector to exploit.

I can only conclude that in 2006 Rutkowska was either naive about the possibilities of such attacks, or that she consciously chose to make an outrageous and indefensible claim ("undetectable malware!!!!111") in order to draw attention to herself and her company. Given the peripheral evidence of Rutkowska's competence, I think the evidence favors the latter, but I'd simply love to hear from her on the subject...

BluePill hype going the way of all flesh

2007-06-29T06:00:00.000-07:00

I'm not alone in my skepticism about BluePill's claims of undetectability. Let's pop some popcorn, folks! This could get good...

Please indulge me...

2007-02-27T16:39:00.000-08:00

I've tried to be fairly disciplined about keeping this blog technical. Never the less, I would ask for your indulgence to announce the birth of Emmett Joseph Adams on February 27th, 2007 at 11:48am.

The little dude is three amazing weeks old now. Everybody is as healthy and happy as can be expected. A few observations from very, very early parenthood:

I'm amazed in the photo below how bloody peppy I look. And that was after being awake all night! I've already come to regard bloodshot eyes, 5 o'clock shadow, and coffee stains on clothes I've slept in as the norm. When I ask other parents when I can expect that to change, they invariably say something smarmy, like, "oh, in about eighteen years."
When I play guitar and sing for him, he kind of zones out for a while and then starts bouncing his legs and arms in time while making these little happy grunts.
Emmett's mother, Jean, is the most amazing person in the world.

OK, back to our regularly scheduled computer stuff!

Microsoft swallows the BluePill

2007-02-22T09:16:00.000-08:00

Why doesn't Microsoft want users to run Vista in a VM? Why, because the presence of a VMM could mean someone has l33tly r00t3d your b0x0r! So nice of Microsoft to protect us shivering, ignorant, childlike customers from choosing how we'd like to run Windows. Ahh, the bliss of having all my decisions made for me. Thank you. I wonder if I should be just as worried about the inherent insecurity of running on a hypervisor once Longhorn ships? Oops, I almost forgot: best not to think of these things! Better to let Microsoft do the worrying for me.

Now that the BluePill pseudo-sploit has been widely publicized for over a year now, I'm still aware of no actual attacks. This, despite the fact that SVM and VT hardware are now extremely common, and getting more so by the day. Why would that be?

Well, first of all, SVM and VT make possible nothing that was not already possible before; VMware's software-only products are an existence proof. The BluePill-istas don't claim that SVM/VT make new exploits possible per se; rather, the claim is that SVM/VT make it possible to cloak the presence of a VMM rootkit completely.

Allow me to go on record: this claim is pure fantasy. In practice, it is always possible to detect the presence of a VMM, via timing attacks. "Aha!", my hand-wringing BluePill interlocutor exclaims: "But the VMM lets us hook RDTSC and the PIT and the APIC timer, etc., so we can show the VM whatever time we want! Or whatever!" The details of getting such an approach right in practice are tough beyond belief. Once you start thinking it through, you quickly realize the deck is stacked in favor of the would-be VMM detector. As a practical example, VMware's software goes to extremely clever lengths in coordinating and manipulating the various virtual time sources just to get certain versions of the linux kernel to boot. It took some smart people years to really drive a stake through the heart of the "pester mingo" boot-time failure in SMP VMs. This was the result of a real, naturally occurring guest code that had nothing to do with VM detection; you can imagine that a dedicated attack on the VMM's virtual time sources could be many orders of magnitude more effective.

So, I'm claiming you can always find out that there's a VMM underneath you. Should that worry us, too? Since some members of the security community are using VMs to study malware, the arms race between malware creators and investigators has temporarily taken a turn wherein some malware refuses to run in a VM. This has led some to think of the detectability of a VMM as a deficiency in the virtualization layer.

I don't see it that way. As VMs become more commonplace, malware that refuses to run in VMs will be naturally selected out. We don't expect, e.g., a Dell laptop to cloak the version of Windows it's running, or which chipset or video card is present, or for that matter which version of Windows is running. It's perfectly legit for software to query these aspects of its execution environment, having an orderly way to enumerate and version them is a valuable thing. As VM proliferation progresses, I suspect that we will come to think of VMMs in the same way: as another facet of the stack of hardware and software on which you happen to be running, whose presence is neither surprising nor secret.

Survived ASPLOS XII!

2006-10-26T08:46:00.000-07:00

Well, I got to present my first conference paper, and lived to tell the tale. Getting to take a question from Dave "AQA" Patterson gave me goosebumps. On Tuesday, a grad student whose name escapes me (sorry!) asked Ole and me, "So, the two of you did all this work yourselves?" Of course not! I'm ashamed to have left that impression on anybody. The VMware VMM group has around 100 alumni at this point; our results, at least as regards the software VMM, stand on the shoulders of many giants. The hardware VMM has also had significant contributions from Jim Mattson, Meenali Rungta, and Michael Ho.

ASPLOS was biking distance from my home this year, so perhaps I'll present a receipt for some chain lube as a travel expense or something. It's amazing how hard it is to get motivated for the "extra-curriculars" at a conference when you can just go home any time you like; instead of going to the welcome reception, I stayed home and made meatloaf. Whatcha gonna do...

Going back to Rhody... Rhody... Rhody...

2006-09-27T08:08:00.000-07:00

I don't think so.

I'm going back to my alma mater to give a talk. I figure I might as well do what little I can to boost attendance, so pretty please, New England virtualizanti, do what you can to make it.

While I'm waxing nostalgic/faux hip-hop about my misspent college youth, it has been pointed out to me that a shout-out is due to my erstwhile CS 169 TA and all-around bad-boy of the hardware/software interface, Bryan Cantrill. Chapeau, Bryan, Adam, and Mike.

As I've pointed out again and again, to the point of eye-rolling boredom on the part of my colleagues, DTrace really is outrageously cool. The improvement in leverage that DTrace yields feels comparable to the improvement going from debugging with printf to a source-level interactive debugger. Those who haven't tried it yet, run, do not walk, to download recent build of OpenSolaris, install it in a VM, and start working your way through the numerous tutorials. You'll be glad you did.

Yes, Virginia. We deliver GP's on control flow transfers at the wrong EIP.

2006-09-20T13:52:00.000-07:00

Busted! This is just one of those tough situations where "perfect" software and "useful" software are in unresolvable conflict. While we could, in theory, get this corner case completely right, no customer would want us to. To patch up this hole we'd have to make all indirect kernel control flow transfers slower. Since literally nothing we've ever run into in the wild cares, we just get this wrong. C'est la vie. Though, interestingly enough, the one piece of software out there that we know relies on this behavior: the VMware VMM itself.

Since there are both architected (the backdoor port) and unarchitected (i.e., the s[gi]dt/lsl instructions) ways of discovering you're in a VM, this isn't really "news," per se, but interesting x86 trivia none the less. If it makes you upset, you have a few options to make the behavior in a VM more like that of real hardware. As Derek discovered, you can tick the "disable acceleration" checkbox in your VM. You can also buy a shiny, new Intel processor and drop "monitor_control.vt32=TRUE" into your config file, but expect lousy performance. (VT32 really only exists as a check on the correctness of our VT implementation; all the VT performance work has been sunk into running 64-bit guests.)

At the end of the day, discovering you're in a VM, in general, is always likely to be easy, just because of timing attacks. These pieces of code that folks write to detect that you're in a VM are sort of modern-day equivalents of the little assembly programs that were used for CPU identification before the CPUID instruction came along; these terribly clever little DOS programs would try to infer the size of the write buffer, time a few instructions, etc., and come up with a "fingerprint" of the CPU. These programs are serious fun to write, and have some educational value. I haven't seen any legitimate, practical uses of the VM detection programs thus far, though. I.e., congratulations, you now know you're on a VMware Workstation 4.5 VM. What are you going to do about it?

Pining for microcode...

2006-09-06T08:12:00.000-07:00

Some synchronization arguments we've been having at work led me to read Lampson and Redell's classic synchronization paper. It's rightly famous for providing the first clear exposition of the priority inversion problem. There's also a good deal of implementation detail about Mesa and Pilot, which were a programming language and operating system, respectively, for PARC's famed Alto workstation.

Most modern readers gloss over this implementation section, since the system described is trivial by modern standards (the OS kernel is 24KLOC) and obsolete in many ways. However, the extremely tight coupling between the OS and the hardware ISA is fascinating to me. The hardware directly supports the kernel's run queue, providing a context switch in a single, one-byte instruction! Faults move the current process straight from the run queue to a hardware-supported "fault queue" and reschedule in hardware. Stacks consist of discontiguous, linked frames allocated and deallocated from a variable-sized "frame heap" maintained in, you guessed it, hardware. When the frame heap is exhausted, a "frame fault" sticks the current process on the fault queue. Not quite as trippy as the StackFrame-as-firstclass Object supported by the SmallTalk system running on the same hardware, but still pretty darned far from the post-RISC, all-C-code-all-the-time machines we're accustomed to.

This tight coupling of ISA to OS was made possible by a writable microcode store, whose internals were exposed to system software. Before I get all starry-eyed about how wonderful a microcode revival would be, I will admit up front that it's 2006. Even if it somehow were practical to expose the microcode stores of modern processors, no sane system software vendor would take advantage. Modern machines' microarchitectures are too complicated to be programmable by non-specialists, and it would be painful beyond belief trying to maintain correct implementations of the same ISA on different microarchitectures. Besides, the whole idea of adapting the ISA to a particular OS seems like a quaint holdover from the CISC days; the Alto folks were working in an environment where the hardware could execute a sequence of microcode instructions much faster than the equivalent sequence of macro-instructions, and that just isn't the world we live in anymore.

So, while writable microcode is probably a stupid thing to wish for if you're writing your own OS, it might still be useful, say, to change the behavior of already existing instructions... It's obvious Intel and AMD are relying on some microcode changes to provide the first generation of VT and SVM in minor revisions of their processors. I've complained that VT/SVM only allow software intervention on the far side of a heavyweight hardware context. Wouldn't it be lovely if, instead of software trap handlers for virtualization-sensitive events, the VMM provided "microcode" handlers for such events? Obviously, it wouldn't really be "microcode" proper; the ISA would have to be "architected", perhaps as a subset of the x86, and run with some vaguely SMM-esque constraints on its behavior. But, if it were possible to arrive at this "pseudo-microcode" in a more expeditious manner than the full context switch out to the VMM, it might provide an opportunity to handle some of the more frivolous exits much more efficiently.

Hi, slashdot!

2006-08-14T09:32:00.000-07:00

Dude. We're famous! Too bad the article write-up calls our paper a "white paper," a term which, for me, carries strong connotations of gradient-bordered, visio-encrusted pdfs in sans serif fonts that use the word "enterprise" more than "and" or "the." For the record, the string "enterprise" appears in our paper only as part of the names of Windows .Net Enterprise and RedHat Enterprise Linux.

"Blue Pill" is quasi-illiterate gibberish.

2006-08-09T11:26:00.000-07:00

I'm surprised at the hullaballoo surrounding the so-called "blue pill" pseudo-exploit. The non-exploit consists of a boot-loaded VT/SVM hypervisor that "undetectably" compromises your chain-loaded host. Recall with me the fundamental theorem of VT/SVM: "VT and SVM make nothing possible that was not possible before." VMware's pre-VT/SVM products are an existence proof.

This case is particularly hilarious, because "cloaking" a rootkit is actually harder to do with VT/SVM than with plain-jane, pre-virtualization x86 technology. Without getting into all the gory details here, malicious code that runs at CPL 0 (a pre-requisite, remember, for the ostensible "attack") can simply map itself in a convenient portion of the kernel address space (say, the top megabyte), modify the limit fields in the running kernel's code and data descriptor table entries, et voila: it's "undetectable", at least in the limited sense in which the blue pill hypervisor was undetectable. Yeah, there are some dots to connect; you have to point the IDT at the rootkit, and you may even ultimately need an x86 emulator if the kernel tries really hard to detect you. But x86 emulators aren't exactly the stuff of science fiction; they're pretty much commodities, which is a handy thing, since you need one in VT/SVM hypervisors, too.

The funny thing is that setting up an IDT and smashing a few GDT entries is actually a good deal simpler than setting up a full-fledged hypervisor, which needs a richer set of trap handlers, its own address space, probably needs to set up a shadow CR3 to protect itself from the guest, certainly needs a GDT and IDT, and so on. Most of that "life support" code can simply be stolen from the exploited host if you take the simpler approach outlined above. I'll go so far as to say that this "blue pill" hype is straightforward attention-whoring; virtualization is hot, and finding some sense in which it might be "bad" seems contrarian and interesting, so people's ears prick up. There's really nothing to see here, though.

DTrace:MacOS X::Chocolate:Peanut Butter

2006-08-08T10:55:00.000-07:00

Whoah. Between this, and the VT-enabled 64-bit Macs, I think Apple just sold me a computer.

(The careful reader might be wondering why the author of a paper that's somewhat critical of VT would be stoked about using VT for virtualization. The answer is: I spent a lot of time on that code, and even if it isn't quite the right approach, running my own code gives me the fun-sies. Plus, those new processors are just outrageously nice pieces of hardware all-around.)

A Comparison of Software and Hardware Techniques for x86 Virtualization

2006-08-07T10:41:00.000-07:00

Our (very early) experiences with VT/SVM, contrasted with VMware's classic VMM. Enjoy. Also linked from the academic program page referenced below.

Secret stash of VMware academic publications

2006-08-02T13:50:00.000-07:00

This page, carefully hidden under the link "Program resources" under the VMware academic program page, contains some published papers that VMware folks have put out over the years. Don't worry about the misleading title "Academic White Papers"; these are no-fooling, intellectually rigorous attempts at sharing knowledge at legit conferences. The odds of you finding this by just clicking around are near nil; I knew it existed, and couldn't figure it out without email from our webmaster. Enjoy!

Microkernel fracas drones on

2006-05-15T11:28:00.000-07:00

I had the pleasure of meeting Andrew Tannenbaum at SOSP 2005. He's a smart man, and anybody who distributes their OS as a VMware VM gets props on that account alone. He's also a refreshingly unreconstructed microkernelist. To hear Andy tell it, the advantages of microkernels in 2006 are a lot like their supposed advantages in 1994: stability, minimality, easy to reason about code, user-level drivers that automagically survive nuclear armageddon, etc. For the most part, I'm willing to stand on the sidelines on the microkernel/megakernel holy war. However, since none of the actual principals of this debate will pay any attention to anything I say, I can attempt the following drive-by cheapshots:

Dr. Tannenbaum is fond of mentioning "self-healing" as a goal of Minix 3. I understand this to mean that, since microkernels enable user-level drivers, failures in hardware and software can be routed around with the same sorts of logging, checkpoint-restore facilities, etc., used for enabling high-availability in other user-level applications.

This has always struck me as a bit too far-fetched to be a short-term goal of a research project. E.g., if your graphics card driver just went down in flames, there's no way in hell a reinstantiated graphics card driver will be able to recover your system seamlessly, because the hardware is in an unknown and, more importantly, unknowable state. When I asked one of Andy's grad students about Minix 3's plans for tackling this problem, I got the cryptic admission that "that's a hard problem." "That's a hard problem" can very occasionally mean, "We have a solution that's entirely too clever to share before I cash some checks from VCs," but it usually means, "We have no freaking clue on earth." Regardless, if you do solve this "incoherent hardware after driver crash" problem, your solution is likely to be just as applicable to a monolithic kernel as to Minix 3, since the problem isn't inherently related to software structure.

If you don't solve this problem, I don't see in what sense your system is self-healing. While a box might continue to "run" with a crashed display driver (or filesystem, storage, your networking driver, etc.), the system is "running" in name only; i.e., it's unlikely to usable for non-trivial work until it's power-cycled. If we're counting that as "self-healing," then all the Linux crashes where I'm still able to ping the machine should be counted, too.
Xen has been carefully, and somewhat silently transmogrifying itself into a microkernel. At some level, this is inherent to the paravirtualization project. Once you liberate the interface between the hypervisor and a "guest" from hardware constraints, you might as well call the "hypervisor" a microkernel and the "guest" a process and be done with it. After all, what is UNIX but a very high-level virtual machine definition, consisting of a set of system calls?

Xen 3.0 is drinking another serving of the microkernel kool-aid by moving all of its drivers into user-level processes (oops, I mean "guests"). I predict that they'll hit the same bumps in the road as the microkernel folks did, and have just as much trouble reaping the supposed benefits.

Treasure trove of hoary Sun OS research

2006-04-28T10:24:00.000-07:00

I ran across this while poking around the opensolaris site yesterday. While I've read some of these papers in the past, seeing them collected together makes you realize just how differently OS'es could have turned out. In 1988, for example, most people were implementing shared libraries (if they were implemented at all) in the kernel, rather than as applications utilizing general facilities like mmap. It makes you wonder what we're doing now that will seem completely archaic and backwards in twenty years.

Intel quietly backing away from VT performance claims

2006-04-12T06:16:00.000-07:00

Intel seems to be resetting expectations about VT performance now that the genie's out of the bottle. I get a lot of questions about VT performance, and the questions usually end with, "How much faster is it?" The answer, of course, is "it depends," and just what it depends on turns out to be the more interesting question. I'm preparing something more satisfying than the usual teases I've been dropping in this blog so far; stay tuned!

Why settle for "privilege" when you can have "hyperprivilege"!

2006-03-21T15:40:00.000-08:00

This "hypervisor" talk has always kind of rubbed me the wrong way. What happens when we want another level of indirection? Do I get a "megavisor"? A "superdupervisor"? I'm rooting for the "ubervisor." IBM actually found it necessary to construct such an ubervisor, to aid hypervisor development, and explicitly supported it in their hardware virtualization extensions to the s/370. I know it sounds like I'm making this up, but I'm not.

Anyway. Sun has released a draft of the hardware and software specs for their virtualization extensions. Check it out. From a technical point of view, it's interesting that they're treating the representation of guest privileged state as a collection of "hyperprivileged" registers, rather than fields in an in-memory, hardware-walked struct, as the x86 hardware assistance initiatives have done. The privileged register approach has the nice property of making nesting work somewhat more cleanly, but also has the unfortunate property of making accesses to guest state slower. (Assuming, of course, that getting at these "hyperprivileged" registers is slower than, say, a load or a store. Take anything I claim about sparc with a big grain of salt, because I, like everyone else, have not done real work on them since college.)

They seem to be taking an IBM-esque approach of viewing the hypervisor as a firmware extension, rather than a shrink-wrapped set of software. This was how virtualization worked back in the Popek and Goldberg era; vendors controlled the entire vertical stack from hardware up to the application. Since all layers of the hardware/software stack were fungible, changes in both hardware and software could be made to accomodate virtualization. Virtualization-motivated changes to the hardware (via VT and SVM) and software (the kids call it paravirtualization these days) are both back with a vengeance, though not because any one company controls the hardware software stack anymore. The hardware changes have been motivated by the popularity of third-party virtualization software, while the software changes have been made possible by the availability of freely modifiable, high quality operating systems like Linux. As with all things virtualization, everything old is new again, but for different reasons.

Did somebody ask for a CHALLENGE????

2006-02-27T08:19:00.000-08:00

No iPods, or free licenses, or t-shirts, or whatever, folks. Make a super-neat virtual machine to run in VMware Player and win stacks and stacks of cold, hard cash. Use your imagination here: what does the world need? What problems have you encountered that could have been better solved with the use of a pre-fabricated VM? Maybe you want to use multiple snapshots to cheat at Zork? The sky's the limit.

I'm kind of blown away at the generosity of the terms of this contest. First prize is $100k! Those are US dollars, folks. We're good for it. There are also various category prizes (e.g., best consumer VM, best developer VM, best VM submitted by a full-time student, etc.) If VMware employees weren't inelligible, I'd totally be taking a few days "sick" to make the ultimate multi-boot AtheOS/OpenStep VM extravaganza...

Microsoft behind the 64-bit virtualization 8-ball

2006-02-12T22:27:00.000-08:00

When my "vmware VT" google alert fired for this story, I exercised a rare bit of journalistic skepticism and didn't post right away. After all, it's basically some guy claiming he spoke to some unnamed guy at our esteemed competitor. This seems a somewhat flimsy basis for concluding that the coming version of Microsoft Virtual Server won't be supporting 64-bit guests. Especially given that English is obviously not the author's first language, the potential for misunderstanding was just too great for any premature showboating. The truth will out itself in time; better for now to maintain a calm, statesmanlike reserve.

Well, after picking through some WinHEC slides, all I've got to say is nyah nyah nyah!!!! It looks as though the MS Virtual Server folks haven't quite managed to square the 64-bit virtualization circle in time for the next release of Virtual Server. Let's see: we have a NaN% price disadvantage when compared with VMware Server, no SMP, and no 64-bit guests. All that leaves Microsoft with is the ability to vaguely hint at the coming hypervisor-based nirvana of Vista nee Longhorn. But in the meantime, why not use VMware VMs? Even if every syllable MS utters about its coming hypervisor is an understatement, common sense suggests they'll try to make it easy to move VMware VMs into the new environment, so what's the risk in choosing a solution that is cheaper, better, and existent?

For extra added irony, check out Microsoft trying real, real hard to make it sound like they're leading the way with all this Buck Rogers Virtumization Technology! OK, OK, in fairness, this is actually a pretty good whiteboard talk. Much of what my Microsoft colleague says is applicable to VMware's VMM as well; it's a good introduction for those curious about the nitty gritty details of running unmodified x86 operating systems. We don't binary patch the windows kernel, though.

VMware Server beans spilled

2006-02-07T10:14:00.000-08:00

We're going to be giving away a server product, to help keep our free desktop product company. This has been covered and talked to death elsewhere; I could blather on about the business strategy behind it, but it's mostly self-explanatory. VMware is still selling ESX Server, and we're betting that the free taste of virtualization goodness will get customers excited enough to start signing POs for our pricier offerings. We'll be selling support for the free products, too.

Perhaps the only widespread misconception I've seen so far is that the existence of both Player and Server as free products means that Workstation is doomed as a for-pay product. It's not necessarily so. While it was true for some earlier releases that Workstation was a strict subset of the GSX product (which is now the free "Server" product), Workstation 5 introduced some features that were not available with GSX. E.g., Workstation lets you organize groups of related VMs into "teams" that power on and off together, share network segments with loss rate and bandwidth properties, etc. There's also a more rich set of abilities for making clones, i.e., copies of the VM, in either a heavyweight ("full clones") or lightweight ("linked clones") mode. So, it's not an absurdity to continue charging for Workstation, even given the sudden availability of other hosted VMware products for free. I'm not saying that we certainly will continue charging for WS, nor that we necessarily won't, don't believe everything you read, there's no Easter Bunny, I don't speak for VMware, and consult a physician before starting any exercise program.

OpenSparc Hypervisor Specification

2006-01-31T07:18:00.000-08:00

As I mentioned here below, Sun is adding hardware virtualization assistance to future Sparc processors. This is deeply weird, because the only two sparc operating systems anybody cares about (Solaris and Linux) are already open source, and hence amenable to paravirt techniques. Given Sun's apparent commitment to Xen, I continue to regard the use of hardware virtualization assistance as a head-scratcher.

Well, now Sun has their own hypervisor API spec, not obviously related to the Xen API. Does this make for yet another competing hypervisor API in the just-getting-started Xen vs. VMware's VMIM fracas? Some sort of hedge on the part of Sun, just in case the Xen romance doesn't pan out? I wonder.

Edit: John Johnson very nicely points out that I'm being an idiot in the comments. Thanks!

Hola amigos!

2006-01-26T10:48:00.000-08:00

I know it's been a long time since I rapped at ya'. Here we are, in '06, more than half-way through the "oughts." How will our decade be remembered? I shudder to think.

It looks like Sun is going to build hardware virtualization support into the newer niagara parts. I must confess that this one is a bit of a head-scratcher for yours truly. The only OS'es of significance that run on sparc are Solaris and Linux. Persons running Linux on sparc hardware for anything other than software development or entertainment purposes are, not to put too fine a point on it, probably out of their cotton-picking minds. So, why does Sun think this will enable them to sell more servers, especially given that their (oh, so horrendously named) BrandZ magic sauce lets most Linux applications run on top of Solaris? Beats me. Perhaps they felt they had to be able to counter Intel's substantial VT hype?

Speaking of which ... Simon Crosby was at Stanford flogging Xen yesterday. While I was unfortunately not able to make it, I perused the slides a tad. With foil titles like "XenSource Delivers Virtualization Value", there isn't much academic veneer on this very business-oriented talk, so, as a non-expert, I can do little to address the projections, pie charts, etc. However, I notice from slide 27 that they're relying on page-table switching to protect virtual kernels from virtual applications on 64-bit architectures. The slide is oddly silent on what a flaming performance disaster this approach constitutes. As if turning every virtual system call into two hardware system calls weren't enough, we're now piling a TLB flush on top of that cost, too. I'll be interested to see how their 64-bit performance fares compared to our offerings. But hey! Who cares about performance when you're "the Open Industry Standard," "Unlocking Platform Innovation"! I'm also tickled at the extended treatment of Xen's newfound live migration capabilities, as if we hadn't shipped the very feature they're aping in 2002.

I know, I know, it's a low blow. VMware has some pretty goofy marketing material out there, too. We're not presenting it in front of the Stanford CS department, though. For the most part. I think.

Graphics and I/O virtualization

2005-12-16T10:50:00.000-08:00

A colleague of mine just pointed out a neat screenshot from Jacob Hansen, whom I had the pleasure of meeting at SOSP. Rich virtualization of I/O in general, and graphics in particular, remains a pretty wide open area. While Workstation 5.5 includes some basic support for passing the host's video hardware through to the guest, the user experience is still recognizably VMware-esqe; i.e., the guest runs in a big opaque rectangle inside a GUI, or in full-screen mode, but the 'in between' possibilities are largely unexplored.

There's also an instructive discussion taking place over on Xen-devel. One of the interesting things about graphics cards is that they present a relatively natural place to exploit paravirtualization techniques; since all OS'es have well-defined graphics driver APIs, and graphics performance has a huge impact on the user experience, the risk/reward of "true virtualization" (e.g., deciding to precisely emulate a Matrox Flibbertigibbet 2000) vs. pseudo-virtualization (emulating some made-up device that makes getting bits out of the guest and onto the host display hardware easy and fast) strongly favors the latter. The same is true, albeit to a lesser extent, with storage controllers and networking adapters.

The downside of making up your own hardware is that guest OS installers can't find a driver for your pseudo-device; since running an installer is often the first experience a user has with VMware, we want to get that guest installed, on the web, and generally looking smooth as quickly as possible. For that reason, we have a "morphing" network card. The network card initially looks like an AMD Lance, and can be driven by the stock Lance drivers available with everything after Windows for Workgroups or so. However, once you install the VMware tools in the guest, we install a driver that colludes with the Lance, to use a more streamlined, paravirt style I/O path.

DTrace for Linux! Sort of!

2005-12-16T08:09:00.000-08:00

My homey/colleague at Sun Adam Leventhal has posted a barn-stormer of an article about the multiplicative power of DTrace and Solaris' new Linux binary compatibility layer (somewhat unfortunately termed "BrandZ"). Adam's post follows the usual script for DTrace demos:

Take some innocent user-level application that mostly performs ok.

Demonstrate a head-scratching anomoly in this mostly-ok performance.

Make the developers look like total idiots.

This last item is a natural consequence of being able to see more deeply into the dynamic behavior of a software system than its creators. Similarly, working on a virtual machine monitor one sees a good deal of unintentional behavior with serious performance consequences. This is not because the people working on top, or glibc, or the Linux kernel for that matter, are idiots. Far from it. (Mostly.) They're just working with inferior tools, like biologists before the invention of the microscope. Creating quality software is one of the most serious untackled technical challenges out there; to the extent that DTrace makes this more possible, it's a real reason to use Solaris.

I've got to hand it to Sun; circa 2000, I thought OS'es were a solved problem. Yeah, we beat our chests over Solaris or Linux or Windows or AIX or whatever, but they're all basically the same junk: processes, users, threads, networking, multiprocessors, filesystems, virtual memory, linkers, etc. While all that stuff is blindingly hard to get right, impelementing it is, at some level, a simple matter of programming. So, props to the boffins at Sun for actively fighting commodification: ZFS and DTrace are real reasons to favor Solaris over other OS'es! For the first time since Mac OS X shipped, there are legitimate, technical reasons for an OS to claim fundamental superiority. Now BrandZ helps overcome excuses for not using Solaris. Of course, Solaris is free, so how they turn this into cash flow is another question.

(And no, smart-alecks, I don't own any SUNW stock or derivatives. Err, I guess I probably do through some index fund somewhere. But you get the point; I'm not randomly text-messaging strangers that "SUNW is gng to $25+++++!!!!!111".)

Lest I get too overheated here, my favorite Linux application won't run under BrandZ, presently. The kernel-level portion of VMware hasn't been ported to Solaris. However, there's at least conceptual hope. We ship the source to vmmon along with the Linux hosted products-- we have to, because there's no such thing as a Linux kernel ABI. Back in the workstation 2.0 days, some intrepid FreeBSD folks took it upon themselves to port vmmon to FreeBSD, and were able to use FreeBSD's linux compatibility layer to run the VMware binary. Perhaps some similarly motivated OpenSolaris folks will get around to doing something similar?

Standing on the shoulders of giants.

2005-12-02T10:37:00.000-08:00

Most folks realize that IBM, DEC, and several other old-school computer manufacturers were thoroughly exploring virtualization around the time my generation was thoroughly exploring our mothers' wombs. Working at VMware for the last six years, I've been constantly aware that much of the ground we're covering was well-worn decades ago. Still, at times, the fidelity of the echos through the generations amazes me.

I've written a lot here about VT, Intel's recently shipped CPU virtualization hardware. I'm pretty intimately familiar with VT's gory guts, as well as those of AMD's Pacifica, after spending a good chunk of my career at VMware extending our VMM to support them. (Sorry to disappoint, AMD/Intel fanboys: the two specifications are pretty much exactly the same, with different instructions and in-memory layouts, etc.)

I was also faintly aware that IBM had done some work to accelerate virtualization "back in the day." But, I was utterly shocked at the familiarity of this paper (Osisek, Jackson, Gum, in IBM Systems Journal, March, 1991). It describes interpretive execution, which is IBM's name for the S/390 virtualization acceleration hardware. What's fascinating is that "interpretive execution" so closely resembles Pacifica, and in turn VT, that you can mechanically translate among them.

What VT calls "non-root mode", and Pacifica calls "guest mode", is known as "interpretive execution" (which, by the way, joins a long list of nuttily technical-sounding, yet completely non-descriptive terms that I associate with IBM; it's right up there with "translation lookaside buffer"). VT's "vmlaunch" instruction is Pacifica's "vmrun" is s/390's Germanic-flavored "sie"; Intel's "VMCS" is AMD's "VMCB" is IBM's "state description" (another hilarious IBM-ism).

The paper also provides something of a crystal ball, describing some interesting extensions that haven't made their way into the x86 vendors' hardware just yet: hardware support for a second level of address translation to support the paged MMU within the guest (which is described, albeit briefly, in the Pacifica spec), hardware SMP guest support (though this might be IBM-specific; it seems to be oriented towards implementing a semi-magical "tlb shootdown" instruction that has no analog on the x86); and I/O acceleration (though again, who knows how applicable this will be to the modern world; the described facilities seem oriented entirely towards pass-through of physical devices, and then only for a single, blessed guest on a given host, which, as Xen demonstrates, can already be implemented today). Everything old is new again...

Workstation 5.5 out the door

2005-11-30T20:46:00.000-08:00

Well, I can stop directing VT experimenters at the Workstation 5.5 beta, now that Workstation 5.5 has shipped. link link.

ZFS emerges from the vapor

2005-11-21T19:37:00.000-08:00

The last few stragglers of Solaris 10 are finally making their way out the door, and look none the worse for their lateness. ZFS seems extremely promising from an administrability point of view; getting rid of LVMs, if it accomplished nothing else, would be a huge usability win, and greatly increase the appeal of pooled storage systems. Clicking around the links Bryan has posted above, I saw some promising things, but a few things struck me as odd.

For instance, Bill Moore shares an anecdote about a large performance win over UFS. The artificial benchmark in question flooded the system's block I/O layer with write requests, so the handfuls of reads lying around to, e.g., page in the root shell so the sysadmin can figure out what the hell just happened take seconds and minutes to complete, and the system is generally ground to dust. How does "ZFS" improve on this? Well, it observes that writes are bufferable, while reads are blocking, and so prioritizes reads over writes. It is therefore much more able to survive storms of write requests. Nice.

So, why am I putting "ZFS" in quotes above? Because it seems to me that any block I/O layer could perform the same optimization. Why is this, as Bryan claims, "a consequence of the end-to-end principle"? Couldn't I do the same thing with extfs in Minix?

Another entry that my virtualization-oriented bias leads me to see differently was some of Bart Smaalders' musings on the consequences of ZFS for the future of Solaris. One of the pieces of extremely clever engineering in ZFS surrounds its treatment of snapshots; they're easy to make, lightweight, first-class, not necessarily read-only, etc., so Bart envisions all sorts of consequences for system upgrades, partitioning, etc. What's interesting to me, as a virtualization dork, is that virtualization (v12n?) makes all of this possible for any file system, under any operating system, with a minuscule fraction of the five-year engineering effort required to create a marvel like ZFS. So, if you find yourself fantasizing about using these snaphost features of ZFS under Windows, consider running that Windows machine in a VMware virtual machine.

But, while it is perhaps lightly overhyped, I truly think ZFS rocks, and wish I could use it on my host right now. Maybe if Janus can follow ZFS out of the vapory mists, I'll make that threat a reality...

VT Coverage: Predictable and Complete Confusion.

2005-11-21T14:48:00.000-08:00

Tragically, this article has been typical of the coverage of Intel's VT release. Put-near all of these articles take the reader on the same wild ride of falsehood and sheer conjecture:

A new era of virtualization has dawned! In short, no. Virtualization is exciting and important, but the era dawned in 1998, and it's now some time in the era's early afternoon. Every single one of the features that these articles describes as gauzy science fiction that Intel's boffins are struggling to bring to life is available right now, today, a phone call away, in a fully supported commercial offering from VMware. VT is nothing but an alternative technique for some of the very low-level parts of VMware's software. It makes possible exactly nothing that was not possible before.
Err. Ok. But, like, hardware is fast and software is slow, so a new era of performant virtualization has dawned! Or something! As episodes like the VAX Call instruction illustrate, attempts to solve complex problems entirely with one, super-general purpose chunk of hardware are not always performance wins; software's flexibility, intelligence, and adaptability often means that it can exploit opportunities that hardware, whose development pipeline is almost an order of magnitude longer than that of software, cannot. Whether VT falls into this category remains to be seen, and we have to cut early implementations some slack, since this is, after all, first generation hardware and software, whereas VMware has been tuning its virtual machine monitor for seven years. But, simply assuming that "hardware is fast" can be ... misleading.
Well. At least a new era of, maybe, more correct virtualization? Or, more simple virtualization? Throw us a bone, here. Maybe, maybe, maybe. But it will take some time to see whether these claims materialize or not.

Flame off. Deep breaths. Now seriously: is it really too much to ask that supposedly technical publications obtain some available hardware, and run some of the available software before breathlessly copying and pasting the Intel press release? Would any other piece of hardware get comparable coverage without the author ever having seen a single physical manifestation of the artifact, let alone run a real application on top of it? Can you imagine a 3D card review like this?

NVidia's new gForce 68802xLxXx has ushered in a shining new era of accelerated gaming. Imagine blowing some stuff up in Doom 7, and it looking really, really, REALLY REAL!!!! And fast. We're hoping to get our hands on one in Q106. Hopefully someone will have written a driver by then.

VT hits the streets

2005-11-14T14:19:00.000-08:00

Intel's Virtualization Technology (VT) has hit the streets. For those just tuning in, VT, like AMD's competing initiative SVM, nee Pacifica, provides hardware support for CPU virtualization in the x86. I've spent a good deal of the last year working on supporting VT in VMware's VMM; this work is currently available in the public beta of VMware Workstation 5.5, so, if you have a really, really new Intel CPU and are curious about how this VT stuff works, please give our code (and Intel's new hardware) a try.

What does this all mean for VMware? Opinions vary, of course. When VT and Pacifica were first announced, there was a lot of knee-jerk slashdot triumphalism of the form, "Ha! We don't need VMware anymore because it will all be in hardware!!!" Of course, there's a lot more to VMware's software than just multiplexing CPUs. There's memory, a chipset, peripherals, undoable disks, virtual networks hooked up in complicated topologies with configurable bitrates and lossiness, and all sorts of other stuff that's hard to imagine doing in hardware.

It is true that Pacifica and VT sidestep the classical impossibility result about x86 virtualization. On the one hand, if VMware hadn't figured out how to square that circle in 1998, I don't think we'd be where we are as a company today. But, on the other hand, we're far past the point where VMware lives and dies by a single systems programming parlor trick. Raw technology solutions for multiplexing an x86 CPU are already freely available. See, for example, QEMU. But, as cool as QEMU is, it doesn't really directly compete with VMware Workstation, because, e.g., you can't sync your ipod with a multiprocessor windows guest running inside of QEMU.

In 1998, VMware Workstation 1.0 was a singing dog: the miracle wasn't that it sang well, but that it sang at all. However, in the intervening seven years, our software has become more than a curiosity. Stretching the analogy far past where wisdom suggests, we've taught that dog to be a colorful, original interpreter of Western music's canon, and we expect that dog to soon shock the world by crafting original, poignant compositions. Who cares if the landscape is cluttered with other mutts practicing their scales?

SGI Prepares to Shuffle Off...

2005-11-02T10:40:00.000-08:00

I interned at SGI, then "Silicon Graphics, Inc.", during a wonderful summer of 1998. IRIX 6.5 was shipping. Linux was still a joke.

I met some amazing engineers, whose influence has continued to guide me. I learned a lot about UNIX internals, big NUMA systems, and how software really works in the process of trying to prove myself to Jeff Heller's real-time/pthreads group. I also began dating the lovely woman who is now Mrs. Adams that summer. So, I'll be spilling a bit of this coming beerbash's NorCal yuppie ale du jour in memoriam. Good bye, SGI. Thanks for all the cool cases.

Xen and RedHat

2005-11-01T08:24:00.000-08:00

These days, when fellow techy sorts find out I work for VMware, they often want to know what I think about Xen. With yesterday's RedHat PR event containing a protracted mash note to Xen, and Slashdot boiling over with the usual speculation, it seems particularly topical today to answer this FAQ. I'd like to especially, super-duper emphasize that this is just me babbling, and has nothing to do with anything officially believed, encouraged, advoctated, etc., by my employer.

For those just tuning in, Xen technically differentiates itself from VMware by the somewhat lugubriously named technique of "paravirtualization." This term refers to co-designing a guest OS along with the virtual machine monitor, to optimize the fit between them. Obviously, this isn't always possible. If you intend to run an OS whose source code is inaccessible, or perhaps doesn't even exist in electronically readable form anymore, paravirtualization is not an option. Paravirtualization constrasts with the "black-box" virtualization practiced by classical VMMs, wherein the OS is carefully kept unaware that the VMM exists, and the VMM in turn has little semantic knowledge about the OS.

Having worked at VMware for a while when I first heard the term, paravirtualization initially struck me as a bit of a hack; i.e., it looks like a way to get some of the advantages of virtual machines, without having to solve some of the ludicrous problems that the x86 presents for classical VMMs. However, after talking to the L4 team a couple years ago, I have been won over, with some qualifications, to the view that paravirtualization can be a legitimate result of conscious system design. In some ways, paravirtualization shows the way towards a unifying scheme for CPU architectures, OS interfaces, "artificial" virtual machines like Java, etc. After all, what is a UNIX process if not a "virtual machine" with some convenient extra capabilities for writing performant applications?

We can classify any software system that wraps underlying hardware along a continuum of levels of abstraction. A purist black-box VMM, which exports a software interface identical to underlying hardware, ala the golden-age IBM VM/360 systems, sits at the lowest level of edge of the universe, while something like a JVM, which exposes no details at all of the underlying hardware, sits at the top.

(Trivia: Note that VMware's ESX Server doesn't quite sit as far near the bottom as the VM/360 machines, because some aspects of the underlying hardware are mutated by the VMware virtualization layer. For instance, the vast diversity of hardware on current PCs are normalized to a basis set of hardware we're comfortable emulating. When easy opportunities to "lightly paravirtualize" the guest, e.g., by using an abstraction of a video or SCSI card, rather than a real hardware model, have arisen, VMware has taken those opportunities. Still, the interface exported by ESX Server is about as close as is practical to that exposed by bare metal.)

Populating the middle ground between JVMs and bare metal, we find a bunch of familiar system-construction paradigms: traditional OS'es, which provide a virtual machine that has high-level semantics (such as files, processes, threads, etc.), but is still machine-language programmable; and microkernels, which provide a slightly less high-level abstraction out of the box. A paravirtualized VMM is simply a different point on this continuum, somewhere between the bare-metal VMM provided by something like VMware ESX Server, and the higher-level (though still pretty low-level) interface provided by an exokernel.

So, that's Xen in a nutshell. It sits at a different space in the continuum of system design than current VMware products do. It offers some of the advantages of VMware products (unmodified application binaries) without offering others (unmodified system-level binaries). The Xen guys are fond of implying that they'll get around to offering those other advantages, perhaps with some coy references to VT and SVM. For various reasons, I think the technical obstacles to achieving parity with VMware's offerings are greater than they realize. Then again, maybe they've started to realize it in the process of slipping Xen 3.0 from August to December. (Not to be too smug; we've slipped releases, too. So has everybody.)

On a personal note, I've had the pleasure of hanging out with various Xen movers and shakers. They're smart people interested in solving problems, and, fairly enough, would like to make a few pounds sterling doing it. They can also really hold their liquor. So, I wish them luck. I've got no problem at all with a little competition. It's good for our customers, good for virtualization as a whole, and keeps my job more interesting. So, bring it on, Xennies! I dare you to make Xen 3.0 as good as you know how.

Gems of SOSP

2005-10-30T06:56:00.000-08:00

Well, it was certainly a stimulating conference. There was a wealth of interesting and well-presented research. Here are some of the papers that interested me most. Insert disclaimer here: I'm just some guy who writes code for a living, what do I know, I'm sure I missed the point of your amazing paper, etc.

Vigilante (Costa et al., Microsoft Research) is a system for automatically detecting internet worms and stopping their spread. While network security is not a field in which I can even attempt to sound intelligent, the paper and talk were very convincing; "OK," I thought at the talk's conclusion, "go ahead and implement this and fix the internet." See an intriguing blog post from someone who might know what they're talking about...

IntroVirt (Joshi, King, Dunlap, and Chen, University of Michigan) is another clever application of virtualization from Peter Chen's group at University of Michigan. They've instrumented user-mode linux so that user-level processes within the UML guest can be instrumented with arbitrary code injected by the administrator of the VM. They present this system in a very narrow light: they use it to detect intrusions in known-vulnerable, but as-yet-unpatched software. It seems to me that the ability to run arbitrary code on arbitrary events in the guest is more generally powerful than this; I suspect the '*Virt*' crowd at Michigan has realized this, too.

Honeyfarm (Vrable et al., UCSD) is another intriguing application of virtualization. The described system uses a virtual machine "fork" primitive to create the external appearance of a very large network of vulnerable "honeypot" machines. Like the UNIX system call, this fork primitive returns twice, once in the calling virtual machine, and once in a newborne virtual machine that is in most respects a copy of its parent. Exploiting copy-on-write techniques and the fact that very few IP addresses are usually active at any given time allows them to achieve a very high virtual-to-physical resource ratio.

Rx (Qin, Tucek, Sundaresen, Zhou, UCSD) is a slightly quirky take on recovering from software failures. They observe that many software failures are easy to observe after the fact (e.g., they cause a SEGV), and that they are frequently caused by a small set of programmer errors (buffer overflows, timing assumptions, uninitialized variables, etc.). Rx does a process-level checkpoint of a server at connection establishment time, and, in the case of failure, reverts to the checkpoint, randomly perturbing the execution environment in the hopes of perturbing away the failure. (A proxy intermediates between client and server to provide the illusion of seamlessness.) According to the paper, this works much better than intuition suggests is possible. It's sort of like failure-oblivious computing, but without the, err, obliviousness.

House -- The Haskell OS

2005-10-25T00:01:00.000-07:00

I'm a systems guy. In my professional life, as per this blog's title, I necessarily am writing software at a pretty grubby level of abstraction, typically in C and assembly. So, it often surprises folks that I carry a torch for functional languages in general, and Haskell in particular. It all dates back to my wasted youth at OGI. I was porting Linux to the i960 on behalf of an active networking project that, to the best of my knowledge, never really got off the ground. My cube was adjacent to the warrens of OGI's fanatical Haskell lovers. While I was too preoccupied with my work at the time, the sheer wild-eyed passion these folks felt about Haskell made a strong impression on me.

Then, they got one of my friends. Michael did a substantial programming project in Haskell, and came away convinced that this was how software ought to be. While I've never created real software in Haskell, I've taken great pleasure in, e.g., fooling around with Haskore. I've often idly wondered whether it made sense to contemplate doing systems programming in Haskell; well, those crazy folks across the way at OGI have beaten me to it. The House poster at SOSP was one of the more popular exhibits, and I for one spent a good twenty minutes or so sputtering half-formed questions such as, "so, like, you can use like, eval in your network drivers!", after which my head exploded.

Update: well, I got the boot floppy image going inside a VM, albeit briefly before the guest hung. So there are some bugs to work out; big freaking deal. Seeing page-table manipulation code as gorgeous as this looks like a cold beer on a hot summer's day to me; and having the OS at large interact with it through this interface makes my heart sing. These guys badly need a e1000 or vmnet ethernet driver; any takers?

Minix3 Available as VM Image

2005-10-24T20:35:00.000-07:00

Andy Tannenbaum's keynote at SOSP was more of the same, "Software is garbage! We should all be ashamed!" hand-wringing that's become fashionable of late. A good chunk of his speech was concerned with plugging the new version of Minix. You might be wondering what's changed with Minix. I am too. T'baum's speech was an unreconstructed rehash of the arguments on behalf of microkernels straight out of 1993: the system will survive driver crashes, because the drivers are just user-level processes!

One of the formats in which minix 3 can be downloaded is as a VMware VM ready to run in the VMware player. I downloaded it to my laptop, and was absolutely gobsmacked by how fast this thing boots. Linux and Windows have conditioned me to think of a reboot as serious computation. It is also neat to see how understandable and clean the system's source is, and how rapidly it is possible to build the entire system from scratch. If you're an OS enthusiast, you owe it to yourself to fool around with this.

Pioneer and Virtualization

2005-10-23T19:26:00.000-07:00

The very first paper in SOSP '05 is a fine example of why a deep understanding of virtualization is now a necessity for doing systems work. A number of folks from CMU (Seshadri, Luk, Shi, Perrig, and Khosla) and one from IBM (van Doorn) describe an enterprising system they name "Pioneer." Pioneer aims to do what AMD's SVM and Intel's LT presume is impossible: reliably measure and attest modern, mostly unmodified kernels. It's a really tough problem, and their approach is novel. However, on reading their paper, I'm convinced VMware's virtual machine monitor is an existence proof of the system's vulnerability. The paper considers this possibility, and rejects it, based on some unfounded assumptions about modern VMMs.

Pioneer's central code-tampering prevention technique is external performance measurement: an external entity challenges the checksum code to attest to the state of the kernel. The external entity not only issues the challenge, but, using very nitty-gritty knowledge about the speed and microimplementation of the challenged host, issues the challenge with a time limit. Executing for longer than the time limit constitutes evidence of tampering, leading the external entity to consider the machine compromised. A corollary of this design is that the checksum function must be micro-architecturally optimal for the hardware on which it is run. If it leaves any spare execution resources unutilized, an attacker might use those parallel execution resources to paper over the holes that he has punched.

The paper goes into much greater detail, but here are some of their responses, paraphrased, to obvious objections:

1. How do you know that the checksum code is checksumming the data it ought to be checksumming? The data is checksummed in a pseudo-random order, and the data pointers themselves are inputs to the checksum. If the kernel is attacked, and the attacker wishes to continue answering challenges, it will have to store the "old code" somewhere to be checked. To manipuate the data pointers within the checksumming code will cause a decrease in performance, which can be detected by the external measuring agent.

Sounds good enough, but I disagree with the assumption that the "old data" and "new data" need to live at different virtual addresses. Why not create a different address space in which to keep the "old kernel" for measurement purposes, while keeping around a primary execution address space containing a compromised kernel? An attacker taking this strategy would intercept (using some memory-invisible technique, like the hardware breakpoint facility) the measurement code to change the pagetable pointer to the innocent-seeming address space on entry and exit. Since the address space switch is outside of the main loop of the checksum code, the odds that the external verifier will notice the performance difference are slim, as page table assignments are lost in the noise when compared to a network I/O. I will be curious to hear the authors' thoughts on this apparent hole in their system. The objection seems so simple and straightforward that I suspect there's something I'm just not getting.

2. What about VMMs? Here's where things get more interesting. Why doesn't running the guest kernel within a hostile VMM constitute a fool-proof attack method? The Pioneer folks consider this prospect in their paper:

"Since we assume a legacy computer system where the CPU does not have support for virtualization, the VM must be created using a software-based virtual machine monitor (VMM) such as VMware*. .... If the adversary tries to cheat by using a software VMM, then each read of the flags register will trap into the VMM or execute dynamically generated code, thereby increasing the adversary's checksum computation time."

...And since the system is very sensitve to changes in checksum execution time, the thinking goes, this attack will fail. They're assuming that writes to eflags.IF will "trap out" or "execute dynamically generated code", and that these will, without further argument, be slower than the native CLI/STI instructions. While this seems intuitively plausible, it's wrong, and I think it's wrong for interesting reasons.

The CLI and STI instructions on modern processors are quite slow, because they have very complex effects on the following instruction stream. For instance, there are OS'es whose idle loop only enables interrupts for a single instruction! All this interrupt stuff in general is exactly the sort of thing that gives today's deep and wide architectures fits, and STI and CLI times of more than 100 cycles are not unheard of on popular x86 implementations.

VMware uses multiple techniques for making forward progress in guest execution. When executing kernels, VMware often runs guest code via a purpose-built binary translator. It's an unusual binary translator, because, rather than translating between two unrelated architectures, it translates supervisor-mode x86 programs to user-mode x86 programs. This means that a whole lot of the dynamic runtime of our translator is spent in memcpy; after all, the vast majority of kernel instructions are the innocent loads, stores, branches, and ALU ops that don't require heavy intervention on the part of a VMM.

The Pioneer folks are right to guess that CLI and STI are not among those innocent instructions: we translate both of them into a small user-level program fragments. These translations basically load the software flags register, perform a single ALU operation on it, clearing or setting the interrupt flag, and then stores it back to memory. The interesting part of this all is that, since the translated code produced by VMware's VMM consists entirely of the bread-and-butter instructions that Intel and AMD go to great lengths to make fast, CLI and STI operations are much, much faster when executing in a VMware VM than on native hardware.

No. Really. Seriously.

Don't believe me? Try it yourself. Here's a kernel module that executes a simple STI benchmark:


#include 
#include 

int
init_module(void)
{
        int i;
        unsigned oldjif = jiffies;

        while (oldjif == jiffies)
                ; /* wait for start of new timer epoch */

        for  (oldjif = jiffies, i = 0; jiffies == oldjif; i++) {
                __asm__ ("sti" : :);
        }
        printk(KERN_ALERT "bogosti: %d hz %d\n", i, HZ);
        return 0;
}



void
cleanup_module(void)
{
}

On my 1.8Ghz pentium M laptop, running the VMware Workstation 5.5 release candidate under a Fedora Core 4 guest, our VMM executes about 200000 iterations in a single millisecond. That works out to around 200 million STIs per second, or something like 9 cycles per iteration. When you look at the code that GCC generated**, you realize that the VMware VMM is executing a STI, two ALU ops, a load, and a predictable branch in about 9 cycles. While I don't have a Linux host on which to test***, I'll go out on a limb and claim we're probably beating hardware by something like 5-10x on this microbenchmark.

Of course, this is a special case. Virtualization can't make all guest kernel code faster, by the old "you can't fit a gallon of milk in a pint bottle" counting argument. But, it's an interesting real-world demonstration of the dangers of making plausible assumptions about performance, especially when it comes to virtualization. Be careful! And if you're resting your security arguments on performance properties of a virtual machine, measure, rather than assert.

* Sic. The first sentence is probably referring to VT and Pacifica, the coming hardware virtualization technologies from Intel and AMD respectively. However, note that in both of those systems, VMs are still "created using a software-based VMM"; VT and Pacifica don't get rid of your software VMM, folks. If they work as planned, they make your VMM radically more simple than VMware's. But the VMM is still sitting there, a big chunk of software that can deceive the guest into thinking almost anything it wants. Note that I take no responsibility for this abuse of our trademark. VMware is a company that makes a VMM among many other things; VMware is not a VMM.

**


  41:   fb                      sti
  42:   83 c1 01                add    $0x1,%ecx
  45:   a1 00 00 00 00          mov    0x0,%eax
  4a:   39 d0                   cmp    %edx,%eax
  4c:   74 f3                   je     41

*** Man, there goes all my UNIX street cred! It's true, it's true; I don't have enough free time to keep WIFI under Linux working. I'll repent, I swear it.

The Inimitable Stimulation of the Foreign

2005-10-23T03:58:00.000-07:00

There's nothing quite as exciting as being in a foreign country. A thousand quotidian details of ones life (how showers work; the direction doorknobs turn; the side of the street on which one drives; the convention about which direction light switches flip) suddenly require conscious effort. The sharp relief thrown on all these details makes one realize just how peculiar any one place's customs are, and fills the mind with the possibilities of the ways things could be, but perhaps just haven't gotten around to being so yet. There's nothing like it.

Being in a foreign country where I actually speak the language is completely new to me. I must have almost killed myself five times this morning stepping off the curb after looking the wrong way. And yet, I can somewhat effortlessly communicate complex, even technical thoughts to the locals, albeit not without betraying my identity as a yank tourist (as if pulling out my camera every 30 seonds to shoot nothing in particular hadn't already given me away).

This morning was a beautifully crisp, see-your-breath-but-still-sweater-without-a-jacket autumn morning, which I whiled away taking in the sights, sounds, and smells of Brighton, the gorgeous seaside vacation destination for wealthy Londoners which is hosting SOSP 2005. My incredibly shallow research, and the incredibly tacky website linked above, had led me to expect a somewhat small town, but my morning walk around revealed a profoundly cosmopolitan retail economy, to the point of mild yuppification. Lots of world food restaurants, continental-style cafes, FCUK storefronts, etc. Before I really knew what had happened, I'd walked for about three hours in this beautiful burg.

I could complain about the usual travel headaches, (e.g., the Brit who got off our plane after getting on in SFO, leading to a typically post-9/11 security freakout that saw us departing an hour late) etc., but what's the point? I'm here now. So far, copious amounts of the delicious espresso is keeping jet lag, and what ought to be a substantial Old Speckled Hen hangover, at bay. We'll see how long that lasts.

I'm off to wander the streets some more. I could do that whole "blogger" thing and tote this poor laptop to a coffee shop, but it seems like it just isn't done here. We'll see if I can scare up the courage to break this convention...

Cor Blimey, Guv!

2005-10-21T14:37:00.000-07:00

I'm going to SOSP. I plan to be blogging the ever-living heck out of that mutha. I've never been to the UK before, so expect some amount of touristic, bewildered-Yank-abroad prose to boot.

VMware Makes VM "Player" App Free

2005-10-21T09:24:00.000-07:00

My employer is going to give away a free application for running VMware virtual machines. Here's Slashdot's reaction, which seems broadly positive. I think if you're a user or developer of a minority OS, this has to be an exciting turn of events. VMware virtual machines are a much, much more attractive delivery vehicle for new OS'es than ISO images. If I'm some Swedish grad student with a hobby OS, I probably am hosting a web page with instructions like:

Download this ISO image.
Burn it to CD-ROM.
Blow the mind of some poor computer sitting in the corner.
Don't forget to back up! Oh, wait, is it too late for that?

Users are much more likely to give it a shot if you just download and double-click a VM image: no rebooting, no burning, no fuss, no muss. I certainly would never have tried Ubuntu, or Solaris 10 were it not for the hygienic nature of VM-based installs.

UPenn Course on Virtualization

2005-10-17T14:29:00.000-07:00

Zachary Ives, E Christopher Lewis, and Milo Martin are teaching a survey course on machine virtualization. The paper collection works its way up from a worthwhile introductory material ( J. E. Smith and Ravi Nair) all the way up to some true exotica (Phil Levis and David Culler: hi, Phil!).

When I started working at VMware in 2000, I was coming straight from undergraduate education and a brief stint as a research assistant. At that time, virtual machines were very much at the fringes of academic interest. Each year, with every passing conference, virtualization has become hotter and hotter. I admit, at this point, that virtualization has probably become a bit of a fad; people apply the term "virtualization," or "virtual machine," to software constructs that could more easily be construed as microkernels, or APIs, or libraries, or P-code, or what have you, because those ideas seem old and busted, while "virtualization" is the new hotness. Our time in the sun will pass, and some of those papers will, in time, look just as head-scratchingly weird as some of the farther-out exokernel papers from the late '90's. Still, it's been really gratifying to see the level of mainstream interest in an idea that's always fascinated me. I'd like to think that my work has, in some small way, contributed to this upswell in interest in virtualization. By showing that full-system virtualization could be practical and efficient, even in a hostile environment, I think VMware helped point the way to this floodgate of interesting ideas.

Lest I let my head get too big: IBM pretty much did all this while my generation was but a gleam in our fathers' eyes. Credit where it's due...

Linux NMIs on Intel 64-bit Hardware

2005-10-13T15:03:00.000-07:00

Why are NMIs cool?

If you are running x86_64 Linux 2.6.x, grep for "NMI" in /proc/interrupts. This line exports a running tally of "non-maskable interrupts" on each CPU since system boot. Just what are these NMI thingies? What is Linux doing with them?

In the x86, "non-maskable interrupts" differ from regular old IRQs not so much in their maskability (they're pretty much maskable, just not by the same methods typically used for IRQs), but in their source (they are signalled to the CPU via a different line than IRQs) and semantics.

The architectural purpose for NMIs is to serve as a sort of "meta-interrupt;" they're interrupts that can interrupt interrupt handlers. This may sound ridiculous initially, but for a kernel developer, judicious use of NMIs makes it possible to port some of the luxuries of user-level development to the kernel. Consider, e.g., profiling. User-level apps typically use SIGPROF, which in turn is driven by the kernel's timer interrupt handler. But what if you're a kernel developer concerned with the performance of the timer interrupt handler itself?

NMIs provide one solution; by setting up periodic NMIs, and gathering execution samples in the NMI handler, you can peer into the performance of kernel critical sections that run with disabled interrupts. We've used this technique to good effect to study the performance of VMware's virtual machine monitor. The oprofile system-wide profiler on Linux leverages the same technique.

Another important application for NMIs is best-effort deadlock detection; an NMI "watchdog" runs perioically and looks for signs of forward progress (e.g., those counts of interrupts in /proc/interrupts rolling forward) has a decent chance of detecting most "hard" kernel hangs. 9 times out of 10, an NMI handler that detects a wedged system can't do much of use for the user. The system will crash, and often do so just as hard as if there were no NMI handler present; however, perhaps it will dump some sort of kernel core file that can be recovered after the inevitable reboot to aid kernel engineers in diagnosing the problem post-mortem. Even something as simple as pretty-printing a register dump and stack-trace to the system console provides a world of improvement in debuggability over a mute, locked-up box.

It's this last application that gets Linux excited. On x86_64, the Linux kernel defaults to building with an NMI watchdog enabled. If you cat /proc/interrupts on a 32-bit x86 system, you'll see the NMI line with a total of zero (unless you've compiled your own kernel with NMIs enabled). So, if NMIs are so nifty, why do we use them for x86_64, and not plain old i386? Good question. I'm not sure why the two architectures are treated differently. Perhaps because x86_64 is a bit more young, and the Linux kernel folks are more concerned with being able to debug hangs? Or perhaps there are architecture-specific differences in other parts of the kernel that make the watchdog less appealing for i386. I don't know.

Too much of a good thing?

So, let's get back to that NMI line in your /proc/interrupts file. If you tap your fingers for a few seconds between inspections of this file, you'll notice the NMI total increasing. However, the rate at which it increases will be dependent on your underlying hardware. If you're running linux-x86_64 on AMD hardware, you'll notice those NMIs ticking up at about 1Hz. This is convenient for the intended purpose; once a second is plenty frequent to check for something as (hopefully) rare as a hard system lock-up.

Now, try the same experiment with an Intel EM64T machine. You'll notice that the NMI interrupts are coming in much, much faster. If you do the math, you'll find they're coming in at 1000Hz, exactly the same rate as the timer interrupts. What gives? And why does Linux want 1000 times more of them on EM64T hardware than on AMD64 hardware?

The answers are buried in nmi.c:nmi_watchdog_default; for AMD64, the kernel uses on-chip performance counters as a source of NMIs, while for all other CPUs (namely, EM64T parts), it uses the timer interrupt. After an initial calibration phase, Linux throttles back the AMD NMIs to a rate of 1Hz. However, on Intel hardware, however, some unusual jiggery-pokey takes place in the legacy PIC and local APICs, so that the very same timer interrupt signal trickles into the kernel via two different routes: once as a normal interrupt, via the IOAPIC and the local APIC's intr pin, and again via the LINT0 line into each local APIC as an NMI. Since the signal generating the NMI is the timer signal, there's little Linux can do but run the NMI interrupt at the same frequency as the timer interrupt.

This arrangement presents a couple of problems. From the point of view of NMI consumers like the aforementioned oprofile, this partially subverts the purpose of NMIs in the first place; by heavily correlating the NMI handler with the running of a particular chunk of kernel code (namely, the plain-jane timer interrupt handler), the distribution of kernel samples can be skewed. This could badly impact the effectiveness of profiling applications (the profile samples would tend to hit near the same place).

There are also performance consequences to this use of the hardware. 64-bit Linux on Intel hardware performs worse than it has to. How much worse? Let's assume a typical P4 needs 1000 cycles at minimum to take an NMI, and execute an IRET instruction to return from it. Then, of course, the software presumably has some work to do, taking at least another 2000 cycles. (Yes, I'm pulling these figures from thin air, but I consider them lower bounds, given that the data and code for the NMI handler are most likely cool in the cache.) So, we've used up 3000 cycles 1000 times every second; on your 3GHz modern processor, that's about 0.1% of the processor's performance dedicated to checking for deadlocks. That figure might not sound damning, but when you consider the blood that kernel folks sweat trying to wring fractional percentages out of a single path, 0.1% shaved right off the top, independent of Amdahl's Law for just the price of a recompile is an absolute dream.

Where do I come in? Well, this NMI overhead is even more pronounced when running atop VMware's virtual machine monitor. The probe effect of NMIs is magnified inside a virtual machine, since we typically must emulate the vectoring of the NMI through the virtual IDT in software. But, what's worse, in SMP VMs, the hardware path Linux is using to deliver NMIs introduces bottlenecks. The PIC and LINT0 line, which Linux uses to deliver NMIs on Intel hardware are (and are constrained by the architecture to be) system-wide global entities, shared by all virtual CPUs in the VM; to manipulate them 1000 times a second induces lots of synchronization-related overheads. (And no, armchair lock granularity second-guessers, there's not just a big "LINT0 lock" we're taking over and over again; it's a cute little lock-free algorithm, but at the end of the day, you can only get so cute before you do more harm than good .)

You multiply these effects together (too many NMIs * NMI overheads in a VM * overheads of delivering NMIs via cross-VCPU hardware in a VM) and you end up with a trivially measurable effect on performance when running Linux in a 64-bit VM. Unfortunately, those second two factors aren't going anywhere; NMIs will have a higher impact in a VM for the foreseeable future, as will using global interrupt hardware like the PIC and LINT0 line. In the long term, the only real improvements are Linux's to make. Linux could either make do with fewer NMIs, as it manages to do on AMD hardware, or use the NMIs via some processor-local hardware, (again, like the performance-counter-based AMD implementation). Luckily, these changes will have real benefits for physical machines, too. It's just the Right Thing (TM). Too bad I don't have enough copious spare time to send Linus a patch; perhaps some of those oft-cited eyeballs have pairs of hands to go with them?

Update: Linux 2.6.12 fixed the NMI-storm-on-EM64T misbehavior chronicled here. Unfortunately, few distributions have picked up such a shiny, new kernel, so the weirdness documented above still affects the majority of users.

The Surprising Endurance of Self-Modifying Code

2005-10-12T13:01:00.000-07:00

I recently had the pleasure of meeting a retrocomputing enthusiast, who has asked me to respect his anonymity. For personal amusement, I'm going to call him "Phil." Phil has done some work on software systems that run old video games -- Ms. PacMan, Asteroids, that sort of thing. While these software systems are often called "emulators", most of the good ones are a fair bit more sophisticated than the simple pseudocode that comes to mind when the term "emulator" is thrown around:

for (;;) {
unsigned char opcode = memory[CPU->programConter];
switch(opcode) {
...
}
}

Many of these systems are binary translators of one form or another. They take your Ms. PacMan ROM image, and produce a translation of Ms. PacMan retargeted to run natively on your machine. Phil had designed and built such a system, and we talked about its internals at some length. After a while, it dawned on me that his system would not be able to handle self-modifying code, and I became convinced I was missing something. Surely, if you're running these incredibly hairy machine-language programs that rely on such intimate machine details as the exact cycle counts of individual instructions, you'd run into lots of self-modifying code. If any emulator in the world has to get self-modifying code right, it would be an emulator for old video games, right? Right??!?

But no, Phil confirmed that the system was completely broken in dealing with self-modifying code. Yet, his system had no problem running all sorts of old games.

Why? In the lore of systems, self-modifying code is exactly the sort of bizaare space- and time-optimization that only makes sense in the semi-mythologically constrained environments of old computers. These games were extremely performance-critical, written in assembly language, under harrowing space constraints, often on 8-bit computers with a single general-purpose register. Yet they apparently didn't mutilate their program text by even a single byte.

After watching me squirm for a while, Phil let me off the hook. These are console games; since these systems would only ever run a single game, the code lived in ROM. It would have been prohibitively expensive to provide enough RAM to copy the code out of ROM, so self-modifying code was, ironically, a luxury unavailable to many old-time assembly language video game hackers, the very group with which most people associate self-modifying code.

Today, most developers regard self-modifying code as an occasionally interesting, but thankfully obsolete curiosity. After all, very little significant software is written in assembly anymore; even when it is, space-constraints are rarely what they used to be, and the performance argument would now go against self-modifying code, since it interferes with the instruction cache and pipeline on modern processors. Yet, if you peak under the hood of your running PC, today, in the year 2005, you'll find gobs of self-modifying code looking up at you. From dynamic linkers to JVM/CLRs, to various system instrumentation frameworks, to debuggers, to profilers, on and on ad infinitum, there's a whole heck of a lot of code getting rewritten in dribs and drabs on a modern system. So, whole-system monitors, like the one I work on, need to deal with self-modifying code correctly. In fact, code modification is so prevalent now that monitor engineers must worry not only about its correctness when running in a VM, but also its performance!

So, the next time you're bored around the coffee machine, bend some of your colleagues' minds by asking them which system is running more self-modifying code: a Z80 running Ms. PacMan, or their Windows XP laptop. As a rule of thumb, the more modern the system, the more self-modifying code you'll find.

Microsoft Changes Server Licensing in VMs

2005-10-11T00:11:00.000-07:00

Microsoft plans to license windows on a per-running VM basis, rather than an absolute per-VM basis. On writing this, I'm not even sure what the latter means. When Callinicos contrasts the new licensing policy with the old, he says, "Instead of licensing every inactive or stored virtual instance of a Windows Server System product, customers can now create and store an unlimited number of instances, including those for back-up and recovery, and only pay for the maximum number of running instances at any given time." So, the old policy appears to be total madness: copy a virtual machine's disk file to a tape drive for backup, even if it happens automatically? Whoah, that's a brand new Windows installation! Better have a license for it!

While this change is probably for the better, not all Windows-in-a-VM customers will be dancing for joy. In the same way virtualization was inflating Windows licensing costs for some folks, for others it was depressing those costs. E.g., if you have a single read-only disk file, shared via a network mount and simultaneously running on N physical machines, my (completely ignorant, so don't take this to the bank or anything) understanding is that under the old licensing rules, you would have needed only a single license. Now, you'll be ponying up for N licenses. I'm not saying this to make Microsoft seem like bad guys; it's perfectly fair for them to expect N licenses, since the customer in this case is essentially getting N installations of Windows. But, most press coverage of this announcement seems to be assuming it's a godsend for customers running Windows in VMs; like so many other things in life, the answer to the question, "Is this a good thing?", is, "It depends."

More SystemTap Thoughts

2005-10-10T21:50:00.000-07:00

I've read the SystemTap architecture paper. My initial reactions, which might be muddied by misunderstandings, misreadings, general ignorance, etc.:

Every script execution invokes the GCC toolchain to produce a kernel module, then loads that module, executes for a time, and unloads the module. This makes implementation more tractable, because the SystemTap folks don't have to write a different back-end for every CPU, nor do they have to define a little bytecode VM for user-level to communicate with the kernel, as DTrace did. However, this compile-link-load cycle may take a user-perceptible chunk of time, especially if a script is invoked repeatedly from some other script. Worrying about this sort of incremental friction might seem like premature optimization, but when you rely for runtime performance on a big piece of software that is not optimized for runtime performance, such as the GCC compile/link cycle (which, after all, is optimized to produce fast binaries, not to produce binaries fast), you're throwing away a lot of flexibility right out of the gate.
I'm not in love with the language. Like D, it uses C's expression syntax. However, unlike D, it doesn't use C's type syntax. This isn't just an inconvenience. D scripts can #include header files right out of a source tree, or the kernel, or wherever, and can use those types in a natural way. This can be very helpful when instrumenting a C application.
On the other hand, when not instrumenting a C application, the architecture doesn't seem to anticipate external sources of probe points. They discuss being able to probe user-level applications, but only in terms of tracing specific program counters. This doesn't always make sense. If, e.g., the target application is a scheme interpreter, the programmer will want to interact with his program's control flow in terms of source-level function entry/exit, rather than random program counters within the interpreter. While the core functionality of SystemTap can be extended via "TapSets," it sounds like these tapsets are stuck on the wrong side of the application being probed to do this sort of thing well. (I.e., instead of the scheme interpreter publishing a semantic interface to its internals, the TapSet has to contain enough knowledge about the scheme interpreter to reverse engineer its current state.)

This last point, if I understand it right, is really unfortunate. It basically limits SystemTap's full powers to the kernel; applications can only be instrumented at the machine-language level. Some of the more powerfully convincing DTrace demos involve following an execution path all the way from application-level into the nittiest-grittiest kernel guts. The ability to telescope from the ethereally high level of a scripted language all the way down to the kernel grovelling around in the APIC and back again is one of the more exciting things about DTrace. I hope the SystemTap folks haven't given up on achieving this for Linux.

Or, of course, maybe I'm just not getting it. Perhaps some SystemTappers out there can set me straight?

SystemTap -- DTrace for Linux?

2005-10-10T17:46:00.000-07:00

DTrace absolutely rocks. It is easily the most powerful general-purpose facility to come along in a long, long while. Skeptical? Give Adam's DTrace Bootcamp a quick glance. It's worth your time.

To badly summarize, DTrace makes it painless and safe to carry out surprisingly deep and wide experiments on a running system, from TLB miss code all the way up to Java method invocations. The improvement in system visibility that DTrace represents is comparable to the improvement of a source-level debugger over printf. I'm serious. If you don't believe me, give it a try. (Full disclosure: I went to school with DTrace's founding trio, but believe me, DTrace is so wig-flippingly great that I'd be just as effusive if I didn't know Adam from Adam).

The only unfortunate thing about DTrace is that it is part of Solaris. Nothing against Solaris, mind you. Most of my colleagues regard me as a Solaris zealot, in fact. It's where I came of age as a programmer, and when I have the all too rare pleasure of using it, Solaris still feels like home (/usr/proc/bin!), even after five years of continuous Linux usage.

But let's not kid ourselves. Solaris is in trouble. Not technically; I still believe it's the gold standard for UNIX excellence in design and implementation, and I'll take the bait from any Linux zealot who'd like to argue this. No, Solaris is troubled because it has been losing users. In spite of its recent reincarnation as opensource software, people still perceive Solaris as Sun's house UNIX. And, for those who've been in North Korea for the last five years, Sun is not a fiscally healthy organism.

So, I was pleased today to learn that RedHat, IBM and Intel are doing the only sensible thing, namely ripping off DTrace with total abandon. More power to them; reimplementing good ideas from industry has a long tradition in OSS and Linux in particular. There are, of course, some differences between DTrace and SystemTap; I haven't gotten deeply enough into the available SystemTap documentation to say just what they are.

Godspeed you, SystemTap! I hope to be using something with all the convenience and power of DTrace on a viable operating system sooner rather than later! In the meantime, I'll fire up my gentoo VM, pull down the CVS sources, and cross my fingers that I can get this all to work...

Salutations

2005-10-10T11:59:00.000-07:00

Greetings, imaginary audience! My name is Keith Adams. I'm an engineer in VMware's Virtual Machine Monitor group. I'll be writing here about the x86, operating systems, the hardware/software interface, virtualization, software development in general, etc.

I've been at VMware since 2000, when I graduated from Brown University's CS Department. Lately, I've been preoccupied with the long list of monitor features in VMware Workstation 5.5: 64-bit, support for Intel's VT, hosted SMP support, etc.