One of the best parts is that I will have more time and incentive to write blog posts. For those of you who read my post on Linked Lists, I am finally doing a performance benchmark to generate data that proves my points. For those interested in Big Data, I am writing a qualitative and quantitate comparison of different Hadoop distributions out there. Exciting times ahead.

About Flux7 Labs

I have setup Flux7 Labs like a research lab in my home office (aka. garage) where my team and I partner with selected clients to work on innovative and new technologies. Our website (http://www.flux7.com) is WIP but you can visit our LinkedIn profile to learn more (followers and likes will be highly appreciated). The work is focused on measuring and improving performance of Big Data and Cloud Computing. We also teach the same topics as on-site/online corporate or independent trainings.

In the lab, we are working on some very exciting projects about measuring, simulating, and increasing performance of Hadoop, Cassandra, CouchDB,  etc using hardware+software techniques in the context of BioInformatics, Renewable energy, banking, and video analytics applications. Our clients/partners include Xockets Inc., Bioaxial Inc., Horan & Bird, Bank of America, Cloudant Inc, and Automaton Inc.

Broadly, at Flux7 Labs, we accept projects related to:

Any technical or sales/marketing feedback, tips, guidance, introductions, and references will be much appreciated.

Thank you for your time and sorry for putting you through the shameless marketing.

Side note: Shoot me an email if you are in a situation where you are having to decide between your job and venturing into a new career. I made a comparison spreadsheet that you may like. 

The extensions added to both ISAs have a similar scope. Which isn’t surprising since they have the same goals. These goals, first formalized by Popek and Goldberg in 1974, are:

1. A program running under the VMM should exhibit a behavior essentially identical to that demonstrated when running on an equivalent machine directly.
2. The VMM must be in complete control of the virtualized resources.
3. A statistically dominant fraction of machine instructions must be executed without VMM intervention.

The Players
The ARM architecture is owned by ARM. ARM designs its own processors and licenses its architecture to some other chip manufacturers. In the x86 world both Intel and AMD have their own offerings. Intel’s offerings fall under the umbrella marketing term Virtualization Technologies or VT. VT is composed of  VT-x, which encompasses the core side features; VT-d, which encompasses the IOMMU; and VT-c, which covers the network interface. AMD markets its core side virtualization offerings under the label AMD-V while the IOMMU is marketed under AMD-Vi. The Intel and AMD offerings are different in implementation details but are more closely architected to each other than ARM’s offering.

Design Philosophies
The support for virtualization in both architectures is similar but the implementation details are colored by the design philosophies of each architecture. So before we start comparing the specifics of each architecture we need to talk about the general philosophies guiding the design of each.

RISC vs CISC
When we compare x86 virtualization vs ARM virtualization their respective pedigrees as CISC and RISC machines start to be visible. In CISC (Complex Instruction Set Computer), instructions are more powerful and try to bridge the semantic gap between an assembly programmer and the machine. In RISC (Reduced Instruction Set Computer), instructions are simpler giving more flexibility to the software. There are tradeoffs in each philosophy dealing with implementation difficulty, code density, and compiler support.

Backwards Compatibility
The extensions in both ARM and x86 mostly offer backwards compatibility to existing software. Intel has historically gone the extra mile in providing backward compatibility. It is this effort that allows experiments like the one in the video below:

A commitment to backwards compatibility makes software porting significantly easier. But over time it results in cruft in the architecture that make implementation more difficult. It also prevents a major paradigm shift. While ARM provides backwards compatibility, generally ARM is more willing to make major architectural changes.

Ecosystem
A lot of differences between the two architectures stem from the different business models of ARM and Intel. ARM is an IP company that does no manufacturing. It designs an architecture, processor cores, and system IP blocks. Customers may choose to buy all or part of their offerings and customize their SoC according to their needs.

Intel on the other hand manufactures their own core, their own chipset, and provides reference designs to OEMs. There is very little customization and Intel is the owner of all the blocks in the system except for external devices that communicate through a standard interface. AMD for the most part operates in the same manner with a top-down design philosophy.

Feature Implementation Comparison
At a high level the features supported in each architecture are very similar. They all support two stage translations. Intel calls this Extended Page Tables, AMD calls it Rapid Virtualization Indexing. They both support exception and interrupt interception by hypervisor and triggering of interrupts in the guest. They maintain host state separate from the VM state.

Privilege Levels
In x86 the expectation is for the processor to run Windows or any other OS right out of the box without any major changes. The hypervisor needs to be a trusted program that can be installed on the operating system. So the hypervisor works as a part of privileged mode using special virtualization instructions, including instructions for enabling and disabling the hypervisor. Once the hypervisor is enabled a privilege separation is created for host versus VM level.

This is very different from how the privileges are organized in the ARM world. The developers don’t have the same expectations from ARM. Until very recently most of the commercial ARM devices did not allow the user to purchase and use software of their choice. This allowed the device maker to make major changes to the software. When implementing virtualization ARM does not have the same restrictions present in the x86 world. Because of this ARM’s approach to the privilege levels is different from x86.In ARM the hypervisor is a new mode at a higher privilege level than the regular kernel. Using a hypervisor requires changes to the boot code and it is incompatible with running the hypervisor as an application on an unchanged OS.

Virtual Machine Entry
The VT-x enhancement create a memory mapped area called VMCS (Virtual Machine Control State) for each of the VMs. This area is setup with a state for all the registers and a VM Launch instruction is used to mirror this state onto the processor. AMD has similar instructions with a similar data structure.

ARM on the other hand does not make these software simplifications and expects the hypervisor to manually modify any registers it needs to modify. There isn’t even a special instruction to launch a VM. In the ARM architecture to launch a VM the hypervisor sets the Exception Link Register (ELR) to the desired PC (Program Counter, Instruction Pointer in x86) and performs an exception return.

This is in line with ARM being a RISC architecture and x86 being a CISC architecture. Analogous to the launch of a VM, a similar structure is created for handling process details in the x86 world while in ARM it is entirely maintained by the OS.

Exception Intercepts
ARM allows redirecting most exceptions to the hypervisor. The ARM architecture allows intercepting interrupts. There is a special mode that allows running an application directly under the hypervisor and this mode allows intercepting undefined instruction and supervisor call exceptions but enabling this mode disables the kernel level. In the ARM architecture, however, there isn’t a policy for redirecting page faults from the kernel to the hypervisor.

In x86 a page fault can be redirected to the hypervisor. This allows the hypervisor to page out the exception vectors for the guest and helps in providing shadow page tables. This feature is necessary in x86 because when hardware support for virtualization was initially introduced, it did not contain support for a two stage tablewalk. The ARM architecture requires 2-stage tablewalks be implemented when implementing virtualization. Since a 2-stage tablewalk usually has higher performance and is easier to implement than shadow page tables, the lack of this feature isn’t a problem for the ARM architecture.

IOMMU and Devices
Both ARM and x86 chipsets have support for the features we talked about in Post 3. One thing to note is that IOMMU does not need core support so in the ARM world there is a potential for customers to choose their own implementation of IOMMU than to go with ARM’s offering. In addition to the IOMMUs mentioned already there are other important implementations. There is a standard defined for an IOMMU for PCI-Express devices. In addition graphics cards have supported the GART IOMMU since AGP.

Different devices may offer different amounts of support for virtualization. That may include sharing a device between multiple virtual machines. For example, Intel’s VT-c allows the ethernet controller to be shared between multiple virtual machines.

In conclusion both ARM and x86 have similar hardware extensions for virtualization. Which is expected since both of the architectures are competing for the same market. The implementation of each is different in several ways as mentioned and it reflects the pedigree of each architecture. And ARM’s support for virtualization points to an interesting future.

For further reading please check out the links below:

http://support.amd.com/us/Processor_TechDocs/24593_APM_v2.pdf
http://www.intel.com/content/www/us/en/virtualization/virtualization-technology-connectivity-technology-brief.html
http://download.intel.com/products/processor/manual/325462.pdf

The first post in this series had an overview of virtualization. The second post went deeper into the features added to support virtualization in the core. The third post talked about support needed at the system level for virtualization. This post will focus on use cases of virtualization.

Server Space Applications

The biggest impact of virtualization has been in redefining the modern datacenter. Virtualization provides fault tolerance, VM migration, sandboxing. Without virtualization we wouldn’t have services like EC2 that are powering many of the world’s biggest websites. With ARM and Intel rattling sabers for the last few years and the release of the Atom processor line by Intel, it was only a matter of time before ARM had to make a play for the server space, and to do this ARM needed a competing offering in virtualization. This is the biggest reason for providing hardware support for virtualization.

Using Cross Platform Applications

Many of us already use virtualization for this purpose. You can run a different OS on top of the current OS, or just run select services to support the current application. There can be extensions to this idea. A thin OS can be packed with an application to provide compatibility while running on a variety of platforms, similar to running a Java application but not requiring binary translation.

big.LITTLE

You may have heard of Samsung’s Exynos 5 Octa SoC. The highlight of this SoC is it provides a cluster of  four high performance, high power Cortex-A15 cores and a cluster of four low power but low performance Cortex-A7 cores. Most of the time the performance requirements for a cell-phone can be met with the low power Cortex-A7 core. At this time the high power Cortex-A15 cores are powered down. Although this migration can be done without virtualization. Although with virtualization this feature naturally falls into VM migration and is significantly easier to implement in software.

Exynos 5 Octa SoC block diagram

Figure below courtesy of Anandtech gives an idea of the potential power savings from a big.LITTLE configuration. Although this slide gives an idea of the power and performance tradeoffs a few points need to be made about the methodology. The first is the tradeoff we’re measuring is not power vs performance. It is energy vs performance. The energy consumed for completing a task is average power divided by performance for that task provided the core can enter a low power mode once the task is complete.

The second thing that caught my eye in that graph was the use of Dhrystone as a benchmark, as indicated by using the unit DMIPS on the y-axis. Dhrystone is an old synthetic benchmark that no longer reflects real world usage. For example the entire workload fits in the L1 cache so it does not see any performance benefits from the larger L2 cache in the Cortex-A15, yet it also doesn’t reflect the increased power consumption from the L2 cache. There is no right or wrong answer to what is the correct benchmark to use. It always depends on the particular use case, but using SPECint would have been a more realistic indicator of system performance and power consumption.

Separating OS Kernel From Device Drivers

Virtualization can be used to separate the operating system from the underlying hardware. This separation can be done using one of the methods mention in the last post. This separation has several practical applications. The first would be reducing development time and costs by making it easier to port an OS to a newer device. But the more important advantage would be in rolling out OS updates. This is a commonly seen problem with Android. After an Android update is rolled out, each of the device manufacturers have to port the changes to their system. This significantly slows down the delivery of updates. Separating the OS from the underlying hardware can speed up the processing of rolling out the updates.

Separating Business From Pleasure

Our cellphones have become the biggest extension of our identity. Our cellphones have our contacts, our photos, our daily schedules, our emails, our text communications. This mixing of personal and business information can cause problems. Right now we give IT administrators extensive control over our personal information. If IT believes my phone is stolen they have the authority to issue a remote wipe of it. On the flipside IT is still  not able to protect corporate data appropriately. For example, they cannot I can still install a malware app on the system that can compromise the data stored on my phone. This problem can be solved by creating separate VMs for work and personal usage on phones. So compromising a personal VM does not affect the corporate data. This point is discussed in this blog post by ARM (video below):

Allow Different OSes On Same Device

Going back to reducing R&D costs. Manufacturers can also create a single handset that runs different OSes, say Android or Windows Phone 8. Devices sold can come preloaded with installers for both OSes and on first time startup the user can choose what OS they want to use. This would reduce development and deployment cost while causing a slight waste of Flash memory. But the idea can be extended further. A try before you buy policy can be implemented allowing a user to use a different OS than they’re used to and if they don’t enjoy the experience they can revert to the system they are familiar with.

Security Features

The hypervisor provides a layer of privilege higher than the OS. The OS can be excluded from accessing regions of memory by the hypervisor. So the hypervisor can be used to store high security data like keys for financial accounts, hashes for checking application integrity, and yes DRM. While the geek in me protests at walling off parts of the system I paid for, the pragmatist in me accepts that these features improve the user experience of someone like my grandmother and enables features that wouldn’t be implemented otherwise.

The Difficulty Of Virtualizing I/O

Before we talk about the hardware solutions at the system level for virtualization we need to set up a motivation for what is driving these features. To appreciate the problems we have to recognize that in some ways communicating with I/O in a virtualized environment is a paradox. We want to run an operating system in a sandboxed environment where it is oblivious to the the system outside the virtual environment. But I/O cannot be oblivious to the outside environment because it is communicating with that environment. So, understandably virtualizing I/O becomes a difficult problem.

So moving away from the philosophical questions, what is the goal of virtualization and how does I/O fit into that goal?  In my view it is to provide a managed environment for hosting a VM that improves the overall user experience. To achieve this goal, ideally we’d like I/O in a VM to have the following properties:

1. The guest has access to the same I/O devices it would use in a native environment.
2. The guest OS cannot affect the I/O operations or memory of other guests.
3. The software changes to the guest OS must be minimal.
4. The guest OS needs to be able to recover from a failure of the hardware or migration of the VM.
5. The I/O operations on the guest OS should have similar performance to running natively.

In this list we can see how several items on the list are competing with other items on the list. So the final solution will require trade-offs based on the particular use-case. Now, With these goals in mind let us look at the various techniques for implementing I/O virtualization and the problems faced.

Emulated Or Paravirtualized Devices

When implementing full virtualization, one of the simplest options is for the guest OS to emulate a virtual device on the host. The guest communicates with this virtual device and the hypervisor detects the guest’s communication. This can be done using trapping of device accesses, or permissions to certain pages of memory. The hypervisor understands the operations by the guest OS on the virtual device and performs the corresponding operation on the physical device. This technique is called hosted or split I/O.

The advantage of this technique is that since every call goes through the hypervisor, the hypervisor can provide the desired functionality. For example the hypervisor can track every I/O operation the device is presently waiting on. Similarly restricting a guest from affecting other guests becomes simplified because all physical device accesses are managed by the hypervisor. But this technique has a high CPU overhead. The data needs to be copied multiple times, processed through multiple I/O stacks, etc.

The performance can be improved by using paravirtualization. In this case the device drivers in the OS implement an ABI with the hypervisor. The device drivers interface with the hypervisor and the hypervisor directly communicates with the physical device as is shown in the figure below.

This technique provides better performance with similar control but there is still a significant performance overhead, for example, in trapping to the hypervisor. Figure below shows the difference observed by IBM in using an emulated IDE controller vs IBM’s virtio-blk paravirtualized device drivers in KVM.

When looking at this overhead it is important to keep in mind it is very use-case dependent. A CPU bound benchmark will not show much sensitivity to the virtualization of I/O. Alternatively for an I/O heavy benchmark this overhead can be significant. As an example the conjugate-gradient method for solving a system of linear equation spends around 70% of CPU cycles in the user mode and spends the remaining time in the hypervisor kernel engaged in disk I/O.

Passthrough I/O

Passthrough I/O greatly improves performance by remapping the guest page tables to directly write to the physical device. This eliminates most of the overhead in trapping to the hypervisor for every operation. This technique brings the bulk of I/O processing to near-native speeds.

There are several issues that need to be addressed to effectively virtualize I/O using this technique. Consider the case of a guest using DMA accesses to communicate with a device. In this scenario we need to account for the following issues.

Isolation

The goal of virtualization is to to sandbox the guest OS to keep it from accessing the data of other guest OSes. We do this in the guest by adding a second stage translation. However, the DMA devices operate on physical addresses and are not aware of second stage translations. So if a guest is given unrestricted access to a DMA device it can read or write to any physical address in memory and corrupt the memory of other guests. So there needs to be a protection mechanism instituted to make sure a device only directs DMA requests from a particular guest to go to memory associated with that guest.

Furthermore, more than one guest may need to access the same device. The device needs to be able to distinguish between the accesses coming from different devices and redirect them correctly.

Physical Address

To complete the DMA transaction the guest OS needs to provide the device with the proper physical address in memory to find the data. But the guest does not know the physical address of the data, only the Intermediate Physical Address (IPA) which is in essence a virtual address. For the DMA access to work the device must be able to translate the IPA to the correct physical address.

Contiguous Memory Blocks

The problem cannot be solved by just providing the device with the correct PA. The device expects the DMA target region to be located in a contiguous region of memory. In a virtualized environment this is not guaranteed. The hypervisor may allocate guest pages that are not contiguous in as small as 4K blocks. So the device must be able to do this translation for the entire DMA region.

32 Bit Devices In Larger Address Spaces

This problem is similar to the problem with a 32 bit guest on a 64 bit host discussed in the previous post. The system may have older devices that cannot access the complete larger address spaces of newer systems. An address translation is necessary to use these devices with a DMA outside their normal addressable range.

Hardware Support

The problems mentioned above are not easily solved in software and need a hardware solution that correctly maps device addresses to the correct guest. Most platforms have hardware solutions for this. This mechanism is called IOMMU for IO Memory Management Unit. Intel calls their implementation VT-d, AMD calls their implementation AMD-Vi, and ARM calls their implementation SystemMMU.

The basic idea for the IOMMU is simple. An address translation unit is placed in between any devices that may be used by a guest OS. When the hypervisor is setting up second stage page tables for a guest OS to access the device, it sets up the IOMMU too. Similar to tablewalks in the core, address translations are expensive. So TLBs are implemented to  reduce the overhead of address translations.

An example system showing where the System MMU can be located. Transactions with the device are translated through the system MMU.

System MMU

The ARM System MMU is programmed with different translation contexts. It maps each transaction to the corresponding context by matching against expected streams. Based on the context the System MMU may either bypass the translation, cause a fault, or perform a translation. The System MMU in the ARM architecture provides full 2 stage translation support (as described in the previous post) and depending on the context we may either do a first stage translation or a second stage translation. To perform the translation the System MMU has registers analogous to the TTBRs and other control registers for each context.

The system MMU may also receive faults during its translation process or if a context is not setup. Depending on the type of fault and how the System MMU is configured it may take certain actions. A translation fault can trigger an interrupt. This allows an opportunity for the hypervisor to service the interrupt and restart the translation so it can come to completion. The System MMU may also send a BUSERROR to the appropriate requestor. There are syndrome registers present to ease the process of diagnosing and fixing the problem.

Some advantages of System MMU don’t even need virtualization. Since the System MMU enables every device to perform VA to PA translations, I/O operations can be performed by drivers in user-space using VAs. The permission checking and translation maps can ensure one user application does not corrupt the memory of another application . This would eliminate the traps to kernel presently required further reducing I/O overhead. Another problem is dealing with contiguous memory. Many operations result in very large DMA accesses that cannot be allocated a single chunk of memory by the OS. Presently they need to either be split into multiple DMA requests or performed with complex DMA scatter-gather operations. The System MMU enables the device to communicate via a DMA based on a contiguous VA instead of fragmented PAs. This both reduces the CPU overhead and simplifies the software and device.

It should be noted that the System MMU is a part of the platform rather than a part of the core architecture. This means it only affects the drivers. Because of this many features are implementation defined. For example the bits used to match a stream and map it to a context are implementation defined. Since there is no user code that is aware of this part of the system, changes to the system MMU architecture wouldn’t require as many legacy code issues.

So using these techniques the hypervisor can provide an appropriate implementation of virtualized I/O according to the use-case. This concludes the third installment of this series on virtualization. This series continues in the next post discussing the use-cases for virtualization especially the use cases targeted in the mobile space by ARM.

References

For more information check out the following resources.

• http://xpgc.vicp.net/course/svt/TechDoc/ch12-IOArchitecturesForVirtualization.pdf
• http://nowlab.cse.ohio-state.edu/NOW/dissertations/huang.pdf
• http://www.ibm.com/developerworks/linux/library/l-virtio/
• http://pic.dhe.ibm.com/infocenter/lnxinfo/v3r0m0/topic/liaat/liaatbestpractices_pdf.pdf
• http://www.mulix.org/lectures/xen-iommu/xen-io.pdf
• http://developer.amd.com/wordpress/media/2012/10/IOMMU-ben-yehuda.pdf
• http://www.arm.com/files/pdf/System-MMU-Whitepaper-v8.0.pdf
• http://software.intel.com/en-us/articles/intel-virtualization-technology-for-directed-io-vt-d-enhancing-intel-platforms-for-efficient-virtualization-of-io-devices
• http://support.amd.com/us/Processor_TechDocs/48882.pdf

As a note, this post will gloss over parts of the ARM architecture. To go deeper into the details of the implementation you can check out the ARM Architecture Reference Manuals. These can be found at infocenter.arm.com but require a free registration.

“Virtual” Virtual Memory 

Virtualization requires that the guest OS cannot have access to the hypervisor’s memory space. Without virtualization extensions, this requirement is enforced with a technique called “shadow page tables”. In this technique, the OS maintains its page tables but the hypervisor keeps the OS from setting the Memory Management Unit (MMU) registers appropriately. Instead, the hypervisor creates its own page tables with its own mappings. When it sees a page fault, it reads the page tables created by the OS, recognizes the address as being mapped by the OS, and creates the actual mapping for the page tables that is used by the hardware MMU. So only the hypervisor has the true Virtual Address (VA) to Physical Address (PA) translation rather than the guest OS. This approach has two problems: it unnecessarily complicates the hypervisor and has performance overhead.

In ARM Virtualization extensions, the above is performed by hardware. This simplifies the hypervisor while adding functionality and improving performance. In the ARM virtualization extensions, the hypervisor essentially sets the hardware to treat the “physical” addresses generated by the guest OS as virtual addresses and adds another level of translation on these addresses. The ARM terminology for the guest OS address is Intermediate Physical Address (IPA). The translation from IPA to PA is called a stage 2 translation and the translation from VA to IPA is called stage 1 translation.

Figure shows how this translation proceeds.When virtulization is disabled, only stage 1 translation is performed. Stage 1 translation has 1 to 3 levels of tablewalks (depending on the page size, e.g, 4KB pages require 3 levels but 1GB pages require only one level). The first level uses the TTBR and the VA to create the PA/IPA for the first descriptor access. Subsequent levels use the descriptor and the VA to generate the address the of the next level descriptor, until the PA/IPA is known. The unshaded boxes in the figure show this process.

ARM virtual memory translation

When virtualization is enabled, each of the translation levels has two stages. stage 1 works as described above, and outputs an IPA (intermediate physical address). stage 2 takes the IPA, and the VTTBR to create the descriptor address for the stage 2 tablewalk (as shown in figure below). Similar to the stage 1 tablewalk, the stage 2 tablewalk can have 1 to 3 levels.

Stage 2 translation

That’s A Lot Of Descriptors

The indirection added by a second stage tablewalk can quickly get very expensive. Memory accesses are already the most expensive operation and with virtualization we may need up to 16 accesses to get the required data. Without virtulization, to reduce the cost of page tablewalks, the result of translations are saved in Translation Lookaside Buffers (TLBs). With virtualization, the cost of a tablewalk goes up significantly with the additional stage. In a processor with virtualization extensions enabled, not only do the TLBs need to be bigger, partial stages of the tablewalks are saved to accelerate the tablewalks.

You Shall Not Pass

The second stage of translation includes permission controls to fault to the hypervisor. This includes the standard controls for disabling any combination of, reads, writes or execution on a page table by the guest OS or the applications running on it.

Example Use Case

All Memory Is Not Equal

The second stage also allows the hypervisor to modify the memory attributes for a particular location including marking it as device memory. Keep in mind that the ARM architecture only allows memory mapped I/O so isolating I/O operations can be done through the page table mappings. The general rule is that the final attribute of memory is going to be the more restrictive of the first stage and second stage attributes. For example, if the first stage marks memory as device and second stage marks it as normal cacheable, the processor treats the memory as a device memory, i.e., disables caching and enforces the ordering requirements for device memory. The hypervisor can also trigger a trap to the hypervisor when the guest accesses memory that is marked as device memory. The hypervisor can use this trap to communicate with the physical external hardware.

Virtual Interrupts

Dealing with device attributes is the first part of helping a guest OS communicate with the outside world. The next part is properly directing interrupts. The ARM architecture provides multiple ways for dealing with interrupts. The hypervisor can be configured for all interrupts to be redirected to the hypervisor. The hypervisor also has access to bits in the HCR for triggering a virtual interrupt in the guest OS. When an interrupt is asserted in the ARM architecture, the device holds the interrupt pin high until the OS tells the device to lower the interrupt pin. When running the OS, this protocol must be maintained. If the interrupt is triggered by the hypervisor using the HCR, a trap to hypervisor is needed to clear the virtual interrupt.

The hypervisor may handle the interrupt in concert with the Generic Interrupt Controller (GIC, pronounced “gick”). The GIC is implemented as a memory mapped I/O device handling the priority and distribution of all the interrupts coming into the system. Without virtualization, the OS communicates the completion of an interrupt to the GIC. With virtualization, the physical interrupt is rerouted to the hypervisor. The hypervisor determines the correct VM to redirect the interrupt to and sets up the corresponding virtual interface for the GIC. It also sets up the second stage page tables for the guest OS to map to the virtual CPU interface of the GIC. The GIC will from then on know how to reroute that interrupt and does not need hypervisor intervention.

Memory management and interrupt virtualization both scratch the surface of the problems involved with sandboxing a virtual machine and providing the guest OS access to physical devices. The next post in this series discusses extensions to the system to support virtualization.

Resources

http://www.linuxplumbersconf.org/2012/wp-content/uploads/2012/09/2012-lpc-arm-zyngier.pdf

The idea for this blog post stemmed from talking to people that had the impression that ARM’s virtualization support, even with the virtualization extensions in Cortex-A15, is limited. I plan to write a few posts exploring virtualization, and the support for it in the ARM and x86 ISAs. This post will draw heavily on my understanding of the ARM architecture and operating systems.

What is Virtualization?
Before we can look at virtualization, we need to define a few key things. The first is virtualization itself. Virtualization in general is creating an environment in software to emulate something physical. More specifically, when we talk about hardware virtualization, it is running an operating system on a sandboxed virtual machine (VM) as opposed to having access to the physical hardware. This is done through the hypervisor which manages guest operating systems the same way an operating system manages applications.

Virtualization does not require hardware support. It can be performed completely in software. An existing operating system can be patched to work at a lower privilege level and trap to the hypervisor. This is called paravirtualization. The advantage of hardware support is in simplifying the software work for the hypervisor and providing performance improvements. For this post, I want to discuss how hardware can help the hypervisor in performing its functions. Those interested in paravirtualization will find this talk about problems faced while implementing paravirtualization on ARM interesting by VMWare: http://labs.vmware.com/academic/arm-core-virtualization

Let’s explore some of the duties of the hypervisor and how the hardware accomplishes them to better understand hardware-assisted virtualization.

Management Has Its Privileges
To sandbox an OS, the hypervisor has to be at a higher privilege level than the guest OS. ARM, for example, creates a higher privilege level called hypervisor mode. The hypervisor mode has access to its own set of system registers that are analogous to the registers present in the system mode. For example, just like the OS tracks process IDs using an Address Space IDentifier (ASID which is a part of the TTBR), the hypervisor tracks current VM using a VMID (which is a part of the VTTBR).

ARM TTBR bit fields

ARM VTTBR bit fields

The hypervisor also has similar access controls as the supervisor mode. In addition,  the hypervisor can read and write the system control registers for the OS.

Having two layers of access control does create a lot of interesting scenarios where the hypervisor and the guest OS compete for a trap. ARM has gone with the philosophy that a good manager is one that intrudes into your work as little as possible. So, if an exception occurs, the guest OS is typically given the opportunity to service it before the hypervisor because the OS is better equipped to handle the applications’ requirements. Let me explain this with an example. Both the OS and the hypervisor provide a similar feature for disabling access to the floating point and SIMD units, using the CPACR (Coprocessor Access Control Register) and HCPTR (Hypervisor Coprocessor Trap Register) respectively. When an application running in the guest OS is disallowed access by both the CPACR and HCPTR, the CPACR has priority.

This is an interesting design choice. It has two advantages. First, it improves the response time of the exception. Second, it allows the OS to behave as normal. However, it also makes it extremely difficult to provide certain functionality, e.g., making the floating point unit invisible to the guest.

Check out the next post in this series, talking about memory management and interrupt handling in a hypervisor here.

Disclaimers:

1. All opinions expressed here are my own and not of ARM or any other entity.

2. I haven’t implemented a hypervisor or operating system myself so I would love to hear comments from experts in the field.

Resources:
http://en.wikipedia.org/wiki/Virtualization
http://en.wikipedia.org/wiki/Operating_system
http://infocenter.arm.com/help/index.jsp
http://www.linaro.org/documents/download/d7fe510d8eb46775afc3953d217b15224fbb93086598a

Comparison data
(also available as a google spreadsheet):

Disclaimer: This is just the result of my informal research. Please let me know if I am missing your device or have gotten some detail wrong.

What is a pass? 

A pass is in fact a regular zip archive a .pkpass extension. It contains the following files:

1. logo.png (optional): The file to be used as the logo.

2. background.png (optional): The file to be used as the pass’ background.

3. icon.png (optional): The file to be used as the icon.

4. manifest.json (required):This file contains a JSON object with SHA1 hashes of all files in the pass except the signature file (as its generated using manifest.json) and the manifest.json file itself. The file has the following format:

{
  "pass.json" : "<sha1 pf pass.json file>",
  "logo.png" : "sdfqefqefqef",

  ...
}

For reference, the easiest way to create a SHA1 hash in Linux is to use the command:

openssl SHA1 <filename>

5. signature (required): File created by signing the manifest.json file with the certificate

6. pass.json (required): It contains a JSON object which specifies the type, formatting, and the data to be displayed on the pass. Apple’s reference is available here, however, it is far from complete and is missing several important details. The only real way to understand pass.json is trial-and-error:  try to generate lots of passes with different options and see the outputs on iOS6 itself. So, that what I was doing for the last two weeks.I developed a few tools to helps me iterate through these options really fast. First it a C-shell script to generate passes from the command-line and second is a pass designer at iPass.pk that allows you to change the values/labels of fields in a reasonable GUI.

Let me give you a few examples of what I have learned that was not mentioned any where in Apple’s docs.  First, to privde some context, lets take a look at a sample pass file and its JSON object with a description of each field.

Boarding Pass

The most interesting fields are: logoText, and primary, secondary, auxiliary, and header fields.  They are all labelled in this annotated screenshot. I have filled each field with <field type abbreviation><field number in the corresponding fields array>. Thus. P1 implies Primary Filed 1, i.e., the first primary field in the primaryFields array. Similarly S* denotes secondary fields, A* auxiliary fields, and H* header fields. Note their positions, font-sized, and styles. To checkout the other fields, try creating some passes using the following procedure or use the GUI at iPass.pk.

How to generate passes manually?

Step 1: Generate the Apple Developer Certificate

Go to the Apple Developer Portal and request a pass type identifier and your certificate. Export a .p12 file from the Key chain.

Step 2:  Generate key.pem and certificate.pem

openssl pkcs12 -in "My PassKit Cert.p12" -clcerts -nokeys -out certificate.pem
openssl pkcs12 -in "My PassKit Cert.p12" -nocerts -out key.pem

Step 3: Gather files 

Copy pass.json and any logo/icon/background image files in a folder.

Step 4: Generate manifest.json 

The goal is to generate JSON object which contains the SHA1 hashes of all the files your gathered in Step 3. I used the following csh script to generate manifest.json

 set MANIFEST = ../manifest.json
 echo '{' > $MANIFEST
 foreach i (*)
   set sha1 = `openssl sha1 $i | cut -d' ' -f2`
   echo \'$i\' : \'$sha1\', >> $MANIFEST
 end
 echo '}' >> $MANIFEST
 cp $MANIFEST .

Step 5: Generate signature

Execute the following csh commands to get a signature file:

set PASSWORD = xxxx
openssl smime -passin pass:$PASSWORD  -binary -sign -signer $CWD/certificate.pem -inkey $CWD/key.pem -in manifest.json -out signature xs-outform DER

Now email this file to yourself, and open it. Cool?

Step 6: Zip the pass

zip test.pkpass *

Now email test.pkpass to yourself and see the magic.

Let me know if you if you have any questions/comments about passes, this tutorial, iPass.pk, or the shell script.

I have recently been interviewing people at Calxeda, my new employer. There are a few fundamental concepts I expect every engineer/CS major to understand, regardless of what position they are applying for. One of them is the difference between a channel’s throughput and its latency. It is surprising how many candidates get it wrong. I will not only try to explain the concepts of latency and throughput using a simple analogy, but also try to hypothesize why IMO most people get them confused.

Quick background: I was first asked to differentiate between latency and throughput when I was a college sophomore. It was during an internship interview at nVidia Austin in Spring 2002, more than a decade ago. Sure enough, I was not very clear about it myself and the interviewer had to explain it to me. I wish I remembered his name to give him credit since I am using the same analogy that he used.

When you go to buy a water pipe, there are two completely independent parameters that you look at: the diameter of the pipe and its length. The diameter determines the throughput of the pipe and the length determines the latency, i.e., the time it will take for a water droplet to travel across the pipe. Key point to note is that the length and diameter are independent, thus, so are are latency and throughput of a communication channel.

More formally, Throughput is defined as the amount of water entering or leaving the pipe every second and latency is the average time required to for a droplet to travel from one end of the pipe to the other.

Let’s do some math:

For simplicity, assume that our pipe is a 4inch x 4inch square and its length is 12inches. Now assume that each water droplet is a 0.1in x 0.1in x 0.1in cube. Thus, in one cross section of the pipe, I will be able to fit 1600 water droplets. Now assume that water droplets travel at a rate of 1 inch/second.

Throughput: Each set of droplets will move into the pipe in 0.1 seconds. Thus, 10 sets will move in 1 second, i.e., 16000 droplets will enter the pipe per second. Note that this is independent of the length of the pipe.
Latency: At one inch/second, it will take 12 seconds for droplet A to get from one end of the pipe to the other regardless of pipe’s diameter. Hence the latency will be 12 seconds.

Queuing: Note that droplets may be arriving at a rate faster than 16,000/second, say 16,100/second. Since the pipe cannot let more than 16,000 droplets to enter each second, the extra 100 droplets will have to wait. Said another way, they are put in queue where they will get to enter the next second. The time a droplet waits in the queue before entering the pipe is called the queuing delay. 

Possible source of confusion: Since queuing delay is related to throughput –NOT latency– many scientists/engineers confuse queuing delay with latency and conclude that latency is related to throughput — which is wrong. Latency itself is independent of throughput, its the queuing delay which isn’t.

This and many other cool concepts about queuing are explained by Queuing theory.

Below is excerpt and a link to the article. Since the original post doesn’t have space for comments, we can use this post for our discussion.

GNU make is a widely used tool for automating software builds. It is the de facto standard build tool on Unix. It is less popular among Windows developers, but even there it has spawned imitators such as Microsoft’snmake.

Despite its popularity, make is a deeply flawed tool. Its reliability is suspect; its performance is poor, especially for large projects; and its makefile language is arcane and lacks basic language features that we take for granted in other programming languages.

Admittedly, make is not the only automated build tool. Many other tools have been built to address make’s limitations. Some of these tools are clearly better than make, but make’s popularity endures. The goal of this document is, very simply, to educate you about some of the issues with make—to increase awareness of these problems.

 

Read more