Today I’d like to talk about a functionality of Xen you may not have heard of, but might have actually used without even knowing it. If you use memory ballooning to resize your guests, you’ve likely used “populate-on-demand” at some point. 

As you may know, ballooning is a technique used to dynamically adjust the physical memory in use by a guest. It involves having a driver in the guest OS, called a balloon driver, allocate pages from the guest OS and then hand those pages back to Xen. From the guest OS perspective, it still has all the memory that it started with; it just has a device driver that’s a real memory hog. But from Xen’s perspective, the memory which the device driver asked for is no longer real memory — it’s just empty space (hence “balloon”). When the administrator wants to give memory back to the VM, the balloon driver will ask Xen to fill the empty space with memory again (shrinking or “deflating” the balloon), and then “free” the resulting pages back to the guest OS (making the memory available for use again).
While this can be used to shrink guest memory and then expand it again, this technique has an important limitation: It can never grow the memory above the starting size of the VM. This is because the only way to grow guest memory is to “deflate” the balloon. Once it gets back to the starting size of the VM, the balloon is entirely deflated and no additional memory can be added by the balloon driver.
To see why this is important, consider the following scenario.
Host A and B both have 4GiB of RAM, and 2 VMs with 2GiB of RAM each. Suppose you want to reboot host B to do some hardware maintenance. You could do the following:

• Balloon all 4 VMs down to 1GiB
• Migrate the 2 VMs from host B onto host A
• Shut down host B to do your maintenance
• Bring up host B
• Migrate the 2 VMs originally on host B back
• Balloon all 4 VMs back up to 2GiB

All well and good. But suppose that while you had one of those VMs ballooned down to 1GiB, you needed to reboot one. Now you have a problem: Most operating systems will only check how much memory is available at boot time. You only have 1GiB of free memory. If you boot with 1GiB of memory, you will be able to balloon *smaller* than 1GiB, but you will not be able to balloon back up to 2GiB when the maintenance of host B is done.
This is where populate-on-demand comes in. It allows a VM to boot with a maximum memory larger than its current target memory. It enables a guest that thinks it has 2GiB of RAM to boot while only actually using 1GiB of RAM. It can do this because it only needs to allow the guest to run until the balloon driver can start. Once the balloon driver starts, it will “inflate” the balloon to the proper size. At that point, there is nothing special to do; the VM looks like it did when we shut it down (guest thinks it has 2GiB of RAM, but 1GiB is allocated to the balloon driver and not accessed). When host B comes back up and more memory is free, the balloon driver can deflate the balloon, bringing the total memory back up to 2GiB.
Populate-on-demand comes into play in Xen whenever you start an HVM guest with maxmem and memory set to different values. In that case, the guest will be told it has maxmem RAM, but will only have memory allocated to it; the populate-on-demand code will allow the guest to run in this mode until the balloon driver comes up and hands “frees” maxmem-memory back to Xen.

Virtualizing memory: A primer

In order to desrcibe how populate-on-demand works, I’ll need to explain a bit more about how Xen virtualizes memory. On real hardware, the actual hardware memory is referred to as physical memory; and it is typically divided into 4k-chunks called physical frames. These frames are addressed by their physical frame number, or pfn. In the x86 world, pfns typically start at 0, and are mostly contiguous (with the occasional “hole” for IO devices). Historically, on x86 platforms, a description of which pfns are available for use by memory is in something called the E820 map, provided by the BIOS to operating systems at boot.
When we virtualize, we need to provide the guest with virtual “physical address space,” described in the virtual E820 map provided to the guest. These are called guest physical frame numbers, or gpfns. But of course there is still real hardware backing this memory; in the virtualization world, it is common to refer to these as machine frames, or mfns. Every useable gpfn must have a mfn behind it.
But the gpfns have to start at 0 and be contiguous, while the mfns which back them may come from anywhere in Xen’s memory. So every VM has a physical to machine translation table, or p2m table, which maps the gpfn space onto the mfn space. Each gpfn will have an entry in the table, and every useable bit of RAM has an mfn behind it. Normally this is done by the domain builder in domain 0, which will ask Xen to fill the p2m table appropriately (including any holes for IO devices if necessary).
Ballooning then works like this. To inflate the balloon, the balloon driver will ask the guest OS for a free page. After allocating the page, it puts it on its list of pages and finds the gpfn for that page. It then tells Xen it can take the memory behind the gpfn back. Xen will replace the mfn in that gpfn space with “invalid entry,” and put the mfn on its own free list (available to be given to another VM). If the guest were to attempt to read or write this memory now, it would crash; but it won’t, because the guest OS thinks the page is in use by the balloon driver. The balloon driver won’t touch it, and the OS won’t use it for anything else.
To deflate the balloon, the balloon driver will choose one of the pages on its list that it has allocated, and then asks Xen to put some memory behind the gpfn. If Xen determines that the guest is allowed to increase its memory, and there is free memory available, then it will allocate an mfn and put it in the p2m table behing that gpfn. Now the gpfn is useable again; the balloon driver then frees the page back to the guest OS, which will put it on its own free list to use for whatever needs memory.

Populate on Demand: The Basics

The idea behind populate-on-demand was that the guest didn’t actually need all of its memory to boot up until the balloon driver was active — it only needed a small portion of it. But there was no way for the domain builder to know ahead of time which gpfns the guest OS will actually need to use in order to do that; nor which memory will be given to the balloon driver by the guest OS once it starts up.
So when building a domain in populate-on-demand mode the domain builder tells Xen to allocate the mfns into a special pool, which I will call here the PoD pool, according to how much memory is specified in the memory parameter. (In the Xen code it’s actually called the PoD cache, but it’s not a good name, because in computer science “cache” has a very specific meaning that doesn’t match what the PoD pool does. This will probably be renamed at some point for clarity.)
It then creates the guest’s p2m table as it did before, but instead of filling it with mfns, it fills it with a special PoD entry. The PoD entry is an invalid entry; so as the guest boots, whenever it touches a gpfn backed by a PoD entry, it will trap up into Xen. When Xen sees that the PoD entry, it will take an mfn from the PoD pool and put it in the p2m for that gpfn. It will then return to the guest, at which point the memory access will succeed and the guest can continue.
Thus, rather than populating the p2m table when building the domain, the p2m table is populated on demand; hence the name.
The key reason for having the the PoD pool is that the memory is already allocated to the domain. If you do a domain list it shows up as owned by the domain; and it cannot be allocated to a different domain. If this were instead allocate on demand, where you actually allocated the memory from Xen when you hit an invalid entry, there would be a risk that the memory you needed to boot until the balloon driver could run would already have been allocated to a different domain.
However, the guest can’t run like this for long. There are far more PoD entries in the p2m table than there are mfns in the PoD pool — that was the point. But the guest OS doesn’t know that; as far as it’s concerned, it has maxmem to work with. If the balloon driver doesn’t start, nothing will keep it from trying to use all of its memory. If it uses up all the memory in the PoD pool, the next time Xen hits a PoD entry, there won’t be any mfns in the PoD pool to populate the entry with. At that point, Xen would have no choice but to kill the guest.

Getting back to normal: the balloon driver

The balloon driver, like the guest operating system, knows nothing about populate-on-demand. It just knows that it has maxmem gpfn space, and it needs to hand maxmem–memory back to Xen. So it begins allocating pages from the guest operating system, and freeing the gpfns back to Xen.
What Xen does next depends on a few things. Xen keeps track of both the number of PoD entries in the p2m table, and the number of mfns in the PoD pool.

• If the gpfn is a PoD entry, Xen will simply replace the PoD entry with a normal invalid entry and return. This reduces the number of outstanding PoD entries in the pool.
• If the gpfn has a real mfn behind it, and the number of PoD entries left in the p2m table is more than the number of mfns in the PoD pool, Xen will replace the entry with an invalid entry, and put the mfn back into the PoD pool. This increases the size of the pool.
• If the gpfn has a real mfn behind it, but the number of PoD entries left in the p2m table is equal to the number of mfns in the pool, it will put the mfn back on the free list, ready to be used by another domain.

Eventually, the number of outstanding PoD entries is equal to the number of entries in the PoD pool, and the system is now in a stable state. There is no more risk that the guest will touch a PoD entry and not find memory in the pool; and for an active OS, eventually all pages will be touched, and the VM will be the same as one booted not in PoD mode.

It’s never that simple: Page scrubbing

At a high level, that’s the idea behind populate-on-demand. Unfortunately, the real world is often a bit more messy than we would like.
On real hardware, if you do a soft reboot (or if you do some special trick, like spraying the RAM with liquid nitrogen), the memory when the operating system starts may still contain information from a previous boot. The freshly booting operating system has no idea what may be in there: it may be security sensitive information like someone’s taxes or private data keys.
To avoid any risk that information from the previous boot might leak into untrusted programs which might run this time, most operating systems will scrub the memory at boot — that is, fill all the memory with zeros. This also means that drivers can assume that freshly allocated memory will already be zeroed, and not bother doing it themselves. Doing this all at once, at the beginning, allows the operating system to use more efficient algorithms, and also localizes the processor cache pollution.
For an operating system running under Xen this is unnecessary, because Xen will scrub any memory before giving it to the guest (for pretty much the same potential security issue). However, many operating systems which run on Xen — in particular, proprietary operating systems like Windows — don’t know this, and will do their own scrub of memory anyway. Typically this happens very early in boot, long before it is possible to load the balloon driver. This pretty much guarantees that every gpfn will be written to before the balloon driver loads. How does populate on demand deal with that?
The key is that the state of a gpfn after it has been scrubbed by the operating system is the same as the default initial state of a gpfn just populated by the PoD code. This means that after a gpfn has been scrubbed by the operating system, Xen can reclaim the page: it can replace the mfn in the p2m table with a PoD entry, and put the mfn in the PoD pool. The next time the VM touches the page, it will be replaced with a different zero page from the PoD pool; but to the VM it will look the same.
So the populate-on-demand system has a number of zero-page reclaim techniques. The primary one is that when populating a new PoD entry, we look at recently populated entries and see if they are zero, and if they are, we reclaim them. The effect of this is to have each scrubbing thread only have one outstanging PoD page at a time.
If that fails, there is another technique we call the “emergency sweep.” When Xen hits a PoD entry, but the PoD pool is empty, before crashing the guest, it will search through all of guest memory, looking for zeroed pages to reclaim. Because this method is very slow, it is only used as a last resort.

Conclusion

So that’s populate-on-demand in a nutshell. There are more complexities under the hood (like trying to keep superpages together), but I’ll leave those for another day.