KVM: PPC: Book3S HV: HPT read/write functions for userspace

The mmu_notifier_retry() function, used to test whether any page invalidations are in progress, currently takes a vcpu pointer, though the code only needs the VM's struct kvm pointer. Forthcoming patches to the powerpc Book3S HV code will need to test for retry within a VM ioctl, where a struct kvm pointer is available but a struct vcpu pointer isn't. Therefore this creates a variant of mmu_notifier_retry called kvm_mmu_notifier_retry that takes a struct kvm pointer, and implements mmu_notifier_retry in terms of it.

Quoted 8 lines · Paul Mackerras

The mmu_notifier_retry() function, used to test whether any page invalidations are in progress, currently takes a vcpu pointer, though the code only needs the VM's struct kvm pointer. Forthcoming patches to the powerpc Book3S HV code will need to test for retry within a VM ioctl, where a struct kvm pointer is available but a struct vcpu pointer isn't. Therefore this creates a variant of mmu_notifier_retry called kvm_mmu_notifier_retry that takes a struct kvm pointer, and implements mmu_notifier_retry in terms of it.

Why not change mmu_notifier_retry() and all its callers?

A new ioctl, KVM_PPC_GET_HTAB_FD, returns a file descriptor. Reads on this fd return the contents of the HPT (hashed page table), writes create and/or remove entries in the HPT. There is a new capability, KVM_CAP_PPC_HTAB_FD, to indicate the presence of the ioctl. The ioctl takes an argument structure with the index of the first HPT entry to read out and a set of flags. The flags indicate whether the user is intending to read or write the HPT, and whether to return all entries or only the "bolted" entries (those with the bolted bit, 0x10, set in the first doubleword).

This is intended for use in implementing qemu's savevm/loadvm and for live migration. Therefore, on reads, the first pass returns information about all HPTEs (or all bolted HPTEs). When the first pass reaches the end of the HPT, it returns from the read. Subsequent reads only return information about HPTEs that have changed since they were last read. A read that finds no changed HPTEs in the HPT following where the last read finished will return 0 bytes.

+4.78 KVM_PPC_GET_HTAB_FD

Documentation/virtual/kvm/api.txt +22 -0

+
+Capability: KVM_CAP_PPC_HTAB_FD
+Architectures: powerpc
+Type: vm ioctl
+Parameters: Pointer to struct kvm_get_htab_fd (in)
+Returns: file descriptor number (>= 0) on success, -1 on error
+
+This returns a file descriptor that can be used either to read out the
+entries in the guest's hashed page table (HPT), or to write entries to
+initialize the HPT.  The returned fd can only be written to if the
+KVM_GET_HTAB_WRITE bit is set in the flags field of the argument, and
+can only be read if that bit is clear.  The argument struct looks like
+this:
+
+/* For KVM_PPC_GET_HTAB_FD */
+struct kvm_get_htab_fd {
+	__u64	flags;
+	__u64	start_index;
+};
+
+/* Values for kvm_get_htab_fd.flags */
+#define KVM_GET_HTAB_BOLTED_ONLY	((__u64)0x1)

If read() is called again on the fd, it will start again from

Documentation/virtual/kvm/api.txt +4 -0

+the beginning of the HPT, but will only return HPT entries that have
+changed since they were last read.
+
+Data read or written is structured as a header (8 bytes) followed by a

Quoted 27 lines · Paul Mackerras

+4.78 KVM_PPC_GET_HTAB_FD

Documentation/virtual/kvm/api.txt +26 -0

+
+Capability: KVM_CAP_PPC_HTAB_FD
+Architectures: powerpc
+Type: vm ioctl
+Parameters: Pointer to struct kvm_get_htab_fd (in)
+Returns: file descriptor number (>= 0) on success, -1 on error
+
+This returns a file descriptor that can be used either to read out the
+entries in the guest's hashed page table (HPT), or to write entries to
+initialize the HPT.  The returned fd can only be written to if the
+KVM_GET_HTAB_WRITE bit is set in the flags field of the argument, and
+can only be read if that bit is clear.  The argument struct looks like
+this:
+
+/* For KVM_PPC_GET_HTAB_FD */
+struct kvm_get_htab_fd {
+	__u64	flags;
+	__u64	start_index;
+};
+
+/* Values for kvm_get_htab_fd.flags */
+#define KVM_GET_HTAB_BOLTED_ONLY	((__u64)0x1)
+#define KVM_GET_HTAB_WRITE		((__u64)0x2)
+
+The `start_index' field gives the index in the HPT of the entry at
+which to start reading.  It is ignored when writing.

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm

Quoted 6 lines

Documentation/virtual/kvm/api.txt +6 -0

+
+Reads on the fd will initially supply information about all
+"interesting" HPT entries.  Interesting entries are those with the
+bolted bit set, if the KVM_GET_HTAB_BOLTED_ONLY bit is set, otherwise
+all entries.  When the end of the HPT is reached, the read() will
+return.  

What happens if the read buffer is smaller than the HPT size?

What happens if the read buffer size is not a multiple of entry size?

Does/should the fd support O_NONBLOCK and poll? (=waiting for an entry to change).

Quoted 11 lines

If read() is called again on the fd, it will start again from

Documentation/virtual/kvm/api.txt +10 -0

+the beginning of the HPT, but will only return HPT entries that have
+changed since they were last read.
+
+Data read or written is structured as a header (8 bytes) followed by a
+series of valid HPT entries (16 bytes) each.  The header indicates how
+many valid HPT entries there are and how many invalid entries follow
+the valid entries.  The invalid entries are not represented explicitly
+in the stream.  The header format is:
+
+struct kvm_get_htab_header {

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2120

Quoted 4 lines

Documentation/virtual/kvm/api.txt +4 -0

+	__u32	index;
+	__u16	n_valid;
+	__u16	n_invalid;
+};

This structure forces the kernel to return entries sequentially. Will this block changing the data structure in the future? Or is the hardware spec sufficiently strict that such changes are not realistic?

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2125

Quoted 5 lines

Documentation/virtual/kvm/api.txt +5 -0

+
+Writes to the fd create HPT entries starting at the index given in the
+header; first `n_valid' valid entries with contents from the data
+written, then `n_invalid' invalid entries, invalidating any previously
+valid entries found.

This scheme is a clever, original, and very interesting approach to live migration. That doesn't necessarily mean a NAK, we should see if it makes sense for other migration APIs as well (we currently have difficulties migrating very large/wide guests).

What is the typical number of entries in the HPT? Do you have estimates of the change rate?

Suppose new hardware arrives that supports nesting HPTs, so that kvm is no longer synchronously aware of the guest HPT (similar to how NPT/EPT made kvm unaware of guest virtual->physical translations on x86). How will we deal with that? But I guess this will be a non-guest-transparent and non-userspace-transparent change, unlike NPT/EPT, so a userspace ABI addition will be needed anyway).

Quoted 28 lines · Avi Kivity

Quoted 27 lines · Paul Mackerras

+4.78 KVM_PPC_GET_HTAB_FD

Documentation/virtual/kvm/api.txt +26 -0

+
+Capability: KVM_CAP_PPC_HTAB_FD
+Architectures: powerpc
+Type: vm ioctl
+Parameters: Pointer to struct kvm_get_htab_fd (in)
+Returns: file descriptor number (>= 0) on success, -1 on error
+
+This returns a file descriptor that can be used either to read out the
+entries in the guest's hashed page table (HPT), or to write entries to
+initialize the HPT.  The returned fd can only be written to if the
+KVM_GET_HTAB_WRITE bit is set in the flags field of the argument, and
+can only be read if that bit is clear.  The argument struct looks like
+this:
+
+/* For KVM_PPC_GET_HTAB_FD */
+struct kvm_get_htab_fd {
+	__u64	flags;
+	__u64	start_index;
+};
+
+/* Values for kvm_get_htab_fd.flags */
+#define KVM_GET_HTAB_BOLTED_ONLY	((__u64)0x1)
+#define KVM_GET_HTAB_WRITE		((__u64)0x2)
+
+The `start_index' field gives the index in the HPT of the entry at
+which to start reading.  It is ignored when writing.

Quoted 8 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm

Quoted 6 lines

Documentation/virtual/kvm/api.txt +6 -0

+
+Reads on the fd will initially supply information about all
+"interesting" HPT entries.  Interesting entries are those with the
+bolted bit set, if the KVM_GET_HTAB_BOLTED_ONLY bit is set, otherwise
+all entries.  When the end of the HPT is reached, the read() will
+return.  

What happens if the read buffer is smaller than the HPT size?

That's fine; the read stops when it has filled the buffer and a subsequent read will continue from where the previous one finished.

Quoted 1 line

What happens if the read buffer size is not a multiple of entry size?

Then we don't use the last few bytes of the buffer. The read() call returns the number of bytes that were filled in, of course. In any case, the header size is 8 bytes and the HPT entry size is 16 bytes, so the number of bytes filled in won't necessarily be a multiple of 16 bytes.

Quoted 3 lines

Does/should the fd support O_NONBLOCK and poll? (=waiting for an entry to change).

No.

Quoted 12 lines

Quoted 12 lines

If read() is called again on the fd, it will start again from

Documentation/virtual/kvm/api.txt +10 -0

+the beginning of the HPT, but will only return HPT entries that have
+changed since they were last read.
+
+Data read or written is structured as a header (8 bytes) followed by a
+series of valid HPT entries (16 bytes) each.  The header indicates how
+many valid HPT entries there are and how many invalid entries follow
+the valid entries.  The invalid entries are not represented explicitly
+in the stream.  The header format is:
+
+struct kvm_get_htab_header {

Quoted 8 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2120

Quoted 4 lines

Documentation/virtual/kvm/api.txt +4 -0

+	__u32	index;
+	__u16	n_valid;
+	__u16	n_invalid;
+};

This structure forces the kernel to return entries sequentially. Will this block changing the data structure in the future? Or is the hardware spec sufficiently strict that such changes are not realistic?

By "data structure", do you mean the stream format on the file descriptor, or the HPT structure? If we want a new stream format, then we would define a bit in the flags field of struct kvm_get_htab_fd to mean "I want the new stream format". The code fails the ioctl if any unknown flag bits are set, so a new userspace that wants to use the new format could then detect that it is running on an old kernel and fall back to the old format.

The HPT entry format is very unlikely to change in size or basic layout (though the architects do redefine some of the bits occasionally).

Quoted 12 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2125

Quoted 6 lines

Documentation/virtual/kvm/api.txt +5 -0

+
+Writes to the fd create HPT entries starting at the index given in the
+header; first `n_valid' valid entries with contents from the data
+written, then `n_invalid' invalid entries, invalidating any previously
+valid entries found.

This scheme is a clever, original, and very interesting approach to live migration. That doesn't necessarily mean a NAK, we should see if it makes sense for other migration APIs as well (we currently have difficulties migrating very large/wide guests).

Quoted 2 lines

What is the typical number of entries in the HPT? Do you have estimates of the change rate?

Typically the HPT would have about a million entries, i.e. it would be 16MiB in size. The usual guideline is to make it about 1/64 of the maximum amount of RAM the guest could ever have, rounded up to a power of two, although we often run with less, say 1/128 or even 1/256.

Because it is a hash table, updates tend to be scattered throughout the whole table, which is another reason why per-page dirty tracking and updates would be pretty inefficient.

As for the change rate, it depends on the application of course, but basically every time the guest changes a PTE in its Linux page tables we do the corresponding change to the corresponding HPT entry, so the rate can be quite high. Workloads that do a lot of fork, exit, mmap, exec, etc. have a high rate of HPT updates.

Quoted 7 lines

Suppose new hardware arrives that supports nesting HPTs, so that kvm is no longer synchronously aware of the guest HPT (similar to how NPT/EPT made kvm unaware of guest virtual->physical translations on x86). How will we deal with that? But I guess this will be a non-guest-transparent and non-userspace-transparent change, unlike NPT/EPT, so a userspace ABI addition will be needed anyway).

Nested HPTs or other changes to the MMU architecture would certainly need new guest kernels and new support in KVM. With a nested approach, the guest-side MMU data structures (HPT or whatever) would presumably be in guest memory and thus be handled along with all the other guest memory, while the host-side MMU data structures would not need to be saved, so from the migration point of view that would make it all a lot simpler.

Quoted 41 lines · Paul Mackerras

Quoted 28 lines · Avi Kivity

Quoted 27 lines · Paul Mackerras

+4.78 KVM_PPC_GET_HTAB_FD

Documentation/virtual/kvm/api.txt +26 -0

+
+Capability: KVM_CAP_PPC_HTAB_FD
+Architectures: powerpc
+Type: vm ioctl
+Parameters: Pointer to struct kvm_get_htab_fd (in)
+Returns: file descriptor number (>= 0) on success, -1 on error
+
+This returns a file descriptor that can be used either to read out the
+entries in the guest's hashed page table (HPT), or to write entries to
+initialize the HPT.  The returned fd can only be written to if the
+KVM_GET_HTAB_WRITE bit is set in the flags field of the argument, and
+can only be read if that bit is clear.  The argument struct looks like
+this:
+
+/* For KVM_PPC_GET_HTAB_FD */
+struct kvm_get_htab_fd {
+	__u64	flags;
+	__u64	start_index;
+};
+
+/* Values for kvm_get_htab_fd.flags */
+#define KVM_GET_HTAB_BOLTED_ONLY	((__u64)0x1)
+#define KVM_GET_HTAB_WRITE		((__u64)0x2)
+
+The `start_index' field gives the index in the HPT of the entry at
+which to start reading.  It is ignored when writing.

Quoted 8 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm

Quoted 6 lines

Documentation/virtual/kvm/api.txt +6 -0

+
+Reads on the fd will initially supply information about all
+"interesting" HPT entries.  Interesting entries are those with the
+bolted bit set, if the KVM_GET_HTAB_BOLTED_ONLY bit is set, otherwise
+all entries.  When the end of the HPT is reached, the read() will
+return.  

What happens if the read buffer is smaller than the HPT size?

That's fine; the read stops when it has filled the buffer and a subsequent read will continue from where the previous one finished.

Quoted 7 lines

Quoted 1 line

What happens if the read buffer size is not a multiple of entry size?

Then we don't use the last few bytes of the buffer. The read() call returns the number of bytes that were filled in, of course. In any case, the header size is 8 bytes and the HPT entry size is 16 bytes, so the number of bytes filled in won't necessarily be a multiple of 16 bytes.

That's sane and expected, but it should be documented.

Quoted 1 line

Quoted 4 lines

Quoted 2 lines

Does/should the fd support O_NONBLOCK and poll? (=waiting for an entry to change).

No.

This forces userspace to dedicate a thread for the HPT.

Quoted 28 lines

Quoted 11 lines

Quoted 11 lines

If read() is called again on the fd, it will start again from

Documentation/virtual/kvm/api.txt +10 -0

+the beginning of the HPT, but will only return HPT entries that have
+changed since they were last read.
+
+Data read or written is structured as a header (8 bytes) followed by a
+series of valid HPT entries (16 bytes) each.  The header indicates how
+many valid HPT entries there are and how many invalid entries follow
+the valid entries.  The invalid entries are not represented explicitly
+in the stream.  The header format is:
+
+struct kvm_get_htab_header {

Quoted 8 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2120

Quoted 4 lines

Documentation/virtual/kvm/api.txt +4 -0

+	__u32	index;
+	__u16	n_valid;
+	__u16	n_invalid;
+};

This structure forces the kernel to return entries sequentially. Will this block changing the data structure in the future? Or is the hardware spec sufficiently strict that such changes are not realistic?

By "data structure", do you mean the stream format on the file descriptor, or the HPT structure? If we want a new stream format, then we would define a bit in the flags field of struct kvm_get_htab_fd to mean "I want the new stream format". The code fails the ioctl if any unknown flag bits are set, so a new userspace that wants to use the new format could then detect that it is running on an old kernel and fall back to the old format.

Quoted 3 lines

The HPT entry format is very unlikely to change in size or basic layout (though the architects do redefine some of the bits occasionally).

I meant the internal data structure that holds HPT entries.

I guess I don't understand the index. Do we expect changes to be in contiguous ranges? And invalid entries to be contiguous as well? That doesn't fit with how hash tables work. Does the index represent the position of the entry within the table, or something else?

Quoted 15 lines

Quoted 14 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2125

Quoted 6 lines

Documentation/virtual/kvm/api.txt +5 -0

+
+Writes to the fd create HPT entries starting at the index given in the
+header; first `n_valid' valid entries with contents from the data
+written, then `n_invalid' invalid entries, invalidating any previously
+valid entries found.

This scheme is a clever, original, and very interesting approach to live migration. That doesn't necessarily mean a NAK, we should see if it makes sense for other migration APIs as well (we currently have difficulties migrating very large/wide guests).

What is the typical number of entries in the HPT? Do you have estimates of the change rate?

Quoted 4 lines

Typically the HPT would have about a million entries, i.e. it would be 16MiB in size. The usual guideline is to make it about 1/64 of the maximum amount of RAM the guest could ever have, rounded up to a power of two, although we often run with less, say 1/128 or even 1/256.

16MiB is transferred in ~0.15 sec on GbE, much faster with 10GbE. Does it warrant a live migration protocol?

Quoted 3 lines

Because it is a hash table, updates tend to be scattered throughout the whole table, which is another reason why per-page dirty tracking and updates would be pretty inefficient.

This suggests a stream format that includes the index in every entry.

Quoted 1 line

Quoted 5 lines

As for the change rate, it depends on the application of course, but basically every time the guest changes a PTE in its Linux page tables we do the corresponding change to the corresponding HPT entry, so the rate can be quite high. Workloads that do a lot of fork, exit, mmap, exec, etc. have a high rate of HPT updates.

If the rate is high enough, then there's no point in a live update.

Quoted 9 lines

Quoted 8 lines

Suppose new hardware arrives that supports nesting HPTs, so that kvm is no longer synchronously aware of the guest HPT (similar to how NPT/EPT made kvm unaware of guest virtual->physical translations on x86). How will we deal with that? But I guess this will be a non-guest-transparent and non-userspace-transparent change, unlike NPT/EPT, so a userspace ABI addition will be needed anyway).

Quoted 7 lines

Nested HPTs or other changes to the MMU architecture would certainly need new guest kernels and new support in KVM. With a nested approach, the guest-side MMU data structures (HPT or whatever) would presumably be in guest memory and thus be handled along with all the other guest memory, while the host-side MMU data structures would not need to be saved, so from the migration point of view that would make it all a lot simpler.

Yeah.

Signature · 1 line

error compiling committee.c: too many arguments to function

Quoted 2 lines

This forces userspace to dedicate a thread for the HPT.

If no changes are available, does read return a size > 0? I don't think it's necessary to support polling. The kernel should always be able to respond to userspace here. The only catch is whether to return !0 read sizes when there are no changes.

At any case, I can't see why a dedicated thread is needed. QEMU is going to poll HPT based on how fast we can send data over the wire.

Quoted 5 lines · Paul Mackerras

Quoted 2 lines · Avi Kivity

Does/should the fd support O_NONBLOCK and poll? (=waiting for an entry to change).

No.

This forces userspace to dedicate a thread for the HPT.

Quoted 28 lines

Quoted 11 lines

Quoted 11 lines

If read() is called again on the fd, it will start again from

Documentation/virtual/kvm/api.txt +10 -0

+the beginning of the HPT, but will only return HPT entries that have
+changed since they were last read.
+
+Data read or written is structured as a header (8 bytes) followed by a
+series of valid HPT entries (16 bytes) each.  The header indicates how
+many valid HPT entries there are and how many invalid entries follow
+the valid entries.  The invalid entries are not represented explicitly
+in the stream.  The header format is:
+
+struct kvm_get_htab_header {

Quoted 8 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2120

Quoted 4 lines

Documentation/virtual/kvm/api.txt +4 -0

+	__u32	index;
+	__u16	n_valid;
+	__u16	n_invalid;
+};

This structure forces the kernel to return entries sequentially. Will this block changing the data structure in the future? Or is the hardware spec sufficiently strict that such changes are not realistic?

By "data structure", do you mean the stream format on the file descriptor, or the HPT structure? If we want a new stream format, then we would define a bit in the flags field of struct kvm_get_htab_fd to mean "I want the new stream format". The code fails the ioctl if any unknown flag bits are set, so a new userspace that wants to use the new format could then detect that it is running on an old kernel and fall back to the old format.

Quoted 3 lines

The HPT entry format is very unlikely to change in size or basic layout (though the architects do redefine some of the bits occasionally).

I meant the internal data structure that holds HPT entries.

I guess I don't understand the index. Do we expect changes to be in contiguous ranges? And invalid entries to be contiguous as well? That doesn't fit with how hash tables work. Does the index represent the position of the entry within the table, or something else?

Quoted 14 lines

Quoted 13 lines

Documentation/virtual/kvm/api.txt KVM_S390_INT_EXTERNAL_CALL (vcpu) - sigp external call; source cpu in parm · line 2125

Quoted 5 lines

Documentation/virtual/kvm/api.txt +5 -0

+
+Writes to the fd create HPT entries starting at the index given in the
+header; first `n_valid' valid entries with contents from the data
+written, then `n_invalid' invalid entries, invalidating any previously
+valid entries found.

This scheme is a clever, original, and very interesting approach to live migration. That doesn't necessarily mean a NAK, we should see if it makes sense for other migration APIs as well (we currently have difficulties migrating very large/wide guests).

What is the typical number of entries in the HPT? Do you have estimates of the change rate?

Quoted 4 lines

Typically the HPT would have about a million entries, i.e. it would be 16MiB in size. The usual guideline is to make it about 1/64 of the maximum amount of RAM the guest could ever have, rounded up to a power of two, although we often run with less, say 1/128 or even 1/256.

16MiB is transferred in ~0.15 sec on GbE, much faster with 10GbE. Does it warrant a live migration protocol?

Quoted 3 lines

Because it is a hash table, updates tend to be scattered throughout the whole table, which is another reason why per-page dirty tracking and updates would be pretty inefficient.

This suggests a stream format that includes the index in every entry.

Quoted 6 lines

As for the change rate, it depends on the application of course, but basically every time the guest changes a PTE in its Linux page tables we do the corresponding change to the corresponding HPT entry, so the rate can be quite high. Workloads that do a lot of fork, exit, mmap, exec, etc. have a high rate of HPT updates.

If the rate is high enough, then there's no point in a live update.

Quoted 8 lines · Avi Kivity

Quoted 5 lines · Paul Mackerras

Quoted 2 lines · Avi Kivity

Does/should the fd support O_NONBLOCK and poll? (=waiting for an entry to change).

No.

This forces userspace to dedicate a thread for the HPT.

Why? Reads never block in any case.

Quoted 2 lines

I meant the internal data structure that holds HPT entries.

Oh, that's just an array, and userspace already knows how big it is.

Quoted 4 lines

I guess I don't understand the index. Do we expect changes to be in contiguous ranges? And invalid entries to be contiguous as well? That doesn't fit with how hash tables work. Does the index represent the position of the entry within the table, or something else?

The index is just the position in the array. Typically, in each group of 8 it will tend to be the low-numbered ones that are valid, since creating an entry usually uses the first empty slot. So I expect that on the first pass, most of the records will represent 8 HPTEs. On subsequent passes, probably most records will represent a single HPTE.

Quoted 3 lines

16MiB is transferred in ~0.15 sec on GbE, much faster with 10GbE. Does it warrant a live migration protocol?

The qemu people I talked to seemed to think so.

Quoted 5 lines

Quoted 3 lines

Because it is a hash table, updates tend to be scattered throughout the whole table, which is another reason why per-page dirty tracking and updates would be pretty inefficient.

This suggests a stream format that includes the index in every entry.

That would amount to dropping the n_valid and n_invalid fields from the current header format. That would be less efficient for the initial pass (assuming we achieve an average n_valid of at least 2 on the initial pass), and probably less efficient for the incremental updates, since a newly-invalidated entry would have to be represented as 16 zero bytes rather than just an 8-byte header with n_valid=0 and n_invalid=1. I'm assuming here that the initial pass would omit invalid entries.

Quoted 9 lines

Quoted 7 lines

As for the change rate, it depends on the application of course, but basically every time the guest changes a PTE in its Linux page tables we do the corresponding change to the corresponding HPT entry, so the rate can be quite high. Workloads that do a lot of fork, exit, mmap, exec, etc. have a high rate of HPT updates.

If the rate is high enough, then there's no point in a live update.

True, but doesn't that argument apply to memory pages as well?