WAN optimization

I've wondered how "WAN optimization" magic works, and I just came across a page to explain it in (a little) more detail than marketing. I hadn't heard of it until a couple years ago, when some Cisco people mentioned that their WAASrouters embed KVM for virtualization.

Why would they do that? Because if your branch office uses an Active Directory server in your centralized data center, and your WAN link dies, work at the branch office ceases. From what I understand, Cisco's WAAS routers run an Active Directory server inside a virtual machine on the router itself, to mitigate that problem. A little googling reveals that similar approaches may be taken by their competition, 3Com and Riverbed.

In general, I expect we'll see much more virtualization in this area in the future. For example, today Cisco's Application Extension Platform (AXP) products are physical x86 cards you stick into a router to run server workloads. It would be plain silly not to take advantage of the well-known consolidation benefits of virtualization to accomplish the same thing. (That's pure speculation, but as I said... silly.)

package management and embedded Linux distributions

A while back, when it looked like the Kuro Box would actually go somewhere, I bought the original model. Among other things, this consists of a 200MHz Freescale e300 core (similar to PowerPC 603e) and 64MB of RAM. No serial port even, but through u-boot it has netconsole and netboot support. I had a decrepit version of Debian installed, and Debian's package management tools frustrate me to the point that I was helpless to get the thing upgraded (something about packages mysteriously "being held back").

For a system like this, the real value of a Linux distribution is the frequency of its security updates. There are some embedded distributions I could have messed with, but I have no idea how reliable their updates are, and I really don't want to be responsible for that myself. I started looking for a "normal" Linux distribution to install. (Unfortunately, the number of mainstream Linux distributions with PowerPC support are shrinking...)

I'm really a Fedora guy. Back in university I did some packaging for LinuxPPC and Yellow Dog Linux (both of which were Red Hat variants), and I'm comfortable enough with RPM to bootstrap a system from just about nothing. So I tried the Fedora installer, and when anaconda failed miserably with netconsole, I painfully installed it package by package.

Long story short, yum (the Fedora software installer) requires an absurd amount of RAM... way more than the 64MB my little Kuro has. The simplest yum operation was taking hours, and I could see I was well into swap. So after all that work, the box was still useless. I ran out of play time, unplugged the thing (since I couldn't install any security updates for it), and there it has sat for another 6 months.

Today I ran across a blog post comparing the speed and memory consumption of yum and zypper (OpenSUSE's package software installer). I don't know much about OpenSUSE, but I will be trying it next...

leveraging Linux for virtualization: the dark side

I work on KVM, which is a relatively small kernel module that transforms the Linux kernel into a hypervisor. A hypervisor really is a kernel: it contains a scheduler (at least the good ones do ;), device drivers (at least interrupt controller, probably console, maybe more), memory management, interrupt handlers, bootstrap code, etc.

This is the key observation behind KVM's design. "Hmm, we need a kernel... and hey, we've already got one!" We just need to add some code to make it schedule kernels instead of userspace tasks. In fact, one of the major technical faults of the Xen project was that it needed to duplicate — often copy outright — Linux code, for features such as power management, NUMA support, an ACPI interpreter, PIC drivers, etc. By integrating with Linux, KVM gets all that for free.

There is a drawback to leveraging Linux though.

pro	con
use Linux's scheduler	stuck with Linux's scheduler
use Linux's large page support	stuck with Linux's large page support
get lots of fancy Linux features	stuck with the footprint of Linux's fancy features

Seeing a theme here? Let me share a little anecdote:

My team had been doing early development on KVM for PowerPC 440, and we were scheduled to do a demo at the Power.org Developer's Conference back in 2007. Unfortunately we weren't able to get Linux booting as a guest in time, but we had a simple standalone application we used instead. So when I say "early development" I mean "barely working."

A friend of mine walked up to the demo station and asked "Does nice work?" Now remember, basic functionality was missing. We couldn't even boot Linux. The only IO was a serial console. We had never touched a line of scheduler code, and certainly hadn't tested scheduling priorities. Despite all that, nice just worked because we were leveraging the Linux scheduler.

There's a down-side though. The Linux scheduler is famously tricky, and almost nobody wants to touch it because even slight tweaks can cause disastrous regressions for other workloads. The Linux scheduler does not support gang scheduling, where all threads of a particular task must be scheduled at once (or not at all).

Gang scheduling is very interesting for SMP guests using spinlocks. One virtual CPU could take a spinlock and then be de-scheduled by the host. Unaware of this important information, all the other virtual CPUs could spin waiting for the lock to be released, resulting in a lot of wasted CPU time. Gang scheduling is one way to avoid this problem by scheduling all virtual CPUs at once.

Since Linux doesn't support gang scheduling, and only a handful of people in the world have the technical skill and reputation to change that, that's basically a closed door.

This is just one example, but I think you can see that re-purposing Linux for virtualization is a tradeoff between functionality and control. If one were to write a new scheduler for a hypervisor, they'd need to implement nice themselves... but they would also be free to implement gang scheduling.

Wind River Linux 3.0 adds KVM

Wind River recently released Wind River Linux 3.0, including KVM support (on x86 systems of course).

Wind River is better known for their VxWorks embedded RTOS, which traditionally has been one of the dominant operating systems in the embedded industry, and still is today. After criticizing Linux and the GPL (as VxWorks competition) for years, in 2003 the company gave in and started moving towards Linux support, including its own Linux distribution. Today Wind River Linux is appearing in more and more places in the embedded Linux market. I think it's considered #2 after MontaVista, though I admit I don't know the relative market shares there.

In some ways, KVM support in Wind River Linux isn't a big surprise, because we already know that Wind River believes in embedded virtualization so much they're writing their own hypervisor.

In other ways, it is a surprise, because KVM is a hypervisor too, and as such might compete with their own hypervisor. I suppose they will have lots of internal conversations about market positioning and how to convince the world they're not competing with themselves, but I guess every sufficiently large company has the exact same issue.

Anyways, the one big takeaway from all this is that Wind River seems to be saying that KVM is good enough for embedded systems. Since I've been saying the same thing for a while to a sometimes-skeptical audience, I'll take it. ;)

design tradeoffs in hardware virtualization

I mentioned that the Power ISA version 2.06 was published recently, which added a model for hardware virtualization on "Book E" embedded processors. (The model for hardware virtualization in server processors, such as POWER4, has been around for years.)

The only reason to add hardware support at all (for anything, not just virtualization) is to improve performance. You can do pretty much anything in software; it's just faster to do it in hardware. For example, people have run emulators and JVMs for years, and that gives you a virtual machine without hardware support. We've even demonstrated virtualization without hardware support with KVM on PowerPC 440.

So the goal for virtualization hardware support, to allow the guest kernel to access as much hardware state as possible without host intervention. In an ideal world we could just duplicate all processor state and allow the guest free access to its own copy... but hardware costs power, heat, and die space.

As a compromise, the Book E virtualization architecture duplicates only the state accessed in the fast path of normal guest operation. So there are guest-writable copies of registers like SRR0-1, SPRG0-3, ESR, and DEAR, which are heavily used by the guest in its interrupt vectors. However, registers which are only used for hardware initialization are not duplicated: when the guest tries to access these registers, a privilege fault occurs and the host/hypervisor emulates the instruction. Slow, but (hopefully) only for operations that don't need to be fast. Similarly, some interrupt vectors (such as alignment interrupts) are only delivered to the host, and at that point it is software's responsibility to implement interrupts delivery to the guest.

In contrast, the virtualization architecture for x86 doesn't duplicate register state, but rather provides instructions for atomically transferring a boatload of register state to and from memory. This definitely does not fit with the RISCish philosophy of the Power architecture, where memory accesses are performed only by load and store instructions. I'm not a hardware person, but I can guess that implementing the x86 technique is rather difficult... and I guess that's the whole point of CISC and RISC. :) I can say that I really appreciate the flexibility when hardware provides simple tools and software can use them how it likes.

Anyways, I can't judge one way as better than the other because I don't understand the hardware implications, but that's really the point I'm trying to make: implementing functionality like this is all about design tradeoffs between hardware and software.

VirtualLogix virtualization on Atom

Right now there are two embedded cores from Intel called "Atom": Silverthorne, which implements VT virtualization support, and Diamondville, which doesn't.

VirtualLogix just announced a port of VLX to Atom Z530, which is a Silverthorne core, though I have no firsthand knowledge if they use VT or not (too technical for a press release I guess). I would assume they do, since that's the only way to virtualize Windows, which they advertise elsewhere on their site.

Interestingly, Intel reported at KVM Forum 2008 that they had run Xen and KVM on Atom (Silverthorne) without problem. (I guess that's the value of a common instruction set...) The biggest issue they faced was at the system level: some Atom systems just don't have enough RAM to run more than one or two guests.

real-time hypervisors

Chuck Yoo from Korea University presented at the Xen Summit last week about Real-time Xen for Embedded Devices (a video of the presentation is also available). He seems to be particularly interested in mobile phones, so his motivation was running the radio stack separate from the user interface.

One of his observations is that interrupts interfere with predictability. To mitigate this, one can disable interrupts completely (poll), or defer interrupt handling so it occurs mostly in schedulable tasks (that way the RT scheduler can prioritize RT tasks over interrupt handling).

I guess that makes sense if your primary objective is scheduling. I'm not really a real-time person, but the real-time metric I hear about the most is "interrupt latency" -- the time between interrupt delivery and running the interrupt handler (lower is better). In this regard, the fact that Xen has no "hypervisor threads" is terrible, because it means that a Xen code path cannot be paused due to interrupt.

In contrast, because KVM is based on the Linux kernel, which can preempt kernel threads (to defer interrupt handlers), this is not an issue.

On the subject of scheduling determinism, Chuck makes the key point that the host scheduler must also have visibility into the real-time characteristics of guest tasks, and he suggests "aggregation" as a way for the host scheduler to account for real-time tasks in multiple guests.

Chuck later observes that Xen's IO model (asynchronous non-deterministic communication with dom0) is also a huge obstacle. As a workaround, he proposes giving RT domains direct access to dedicated hardware.

In contrast, KVM schedules guests and qemu (which provides the virtual IO services) as a single unit. When the guest needs IO services, that means qemu is "already running", and the scheduler doesn't get involved. (I will admit things are becoming a little more fuzzy with qemu's adoption of IO threads, but qemu is shared between Xen and KVM anyways.)

At any rate, a very interesting presentation, though I believe that by starting with Xen, Chuck and his students are needlessly handicapping themselves. Unfortunately I think many embedded systems people are lured to Xen by the promise of a "tiny hypervisor kernel," without realizing the depth of dependencies on the Linux dom0...