x86, vdso, pvclock: Cleanups and speedups

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

arch/x86/vdso/vclock_gettime.c +47 -35

@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-	const struct pvclock_vsyscall_time_info *pvti;
+	const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
 	cycle_t ret;
-	u64 last;
-	u32 version;
-	u8 flags;
-	unsigned cpu, cpu1;
-
+	u64 tsc, pvti_tsc;
+	u64 last, delta, pvti_system_time;
+	u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
 	/*
-	 * Note: hypervisor must guarantee that:
-	 * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-	 * 2. that per-CPU pvclock time info is updated if the
-	 *    underlying CPU changes.
-	 * 3. that version is increased whenever underlying CPU
-	 *    changes.
+	 * Note: The kernel and hypervisor must guarantee that cpu ID
+	 * number maps 1:1 to per-CPU pvclock time info.
+	 *
+	 * Because the hypervisor is entirely unaware of guest userspace
+	 * preemption, it cannot guarantee that per-CPU pvclock time
+	 * info is updated if the underlying CPU changes or that that
+	 * version is increased whenever underlying CPU changes.
+	 *
+	 * On KVM, we are guaranteed that pvti updates for any vCPU are
+	 * atomic as seen by *all* vCPUs.  This is an even stronger
+	 * guarantee than we get with a normal seqlock.
 	 *
+	 * On Xen, we don't appear to have that guarantee, but Xen still
+	 * supplies a valid seqlock using the version field.
+
+	 * We only do pvclock vdso timing at all if
+	 * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+	 * mean that all vCPUs have matching pvti and that the TSC is
+	 * synced, so we can just look at vCPU 0's pvti.
 	 */
-	do {
-		cpu = __getcpu() & VGETCPU_CPU_MASK;
-		/* TODO: We can put vcpu id into higher bits of pvti.version.
-		 * This will save a couple of cycles by getting rid of
-		 * __getcpu() calls (Gleb).
-		 */
-
-		pvti = get_pvti(cpu);
-
-		version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-		/*
-		 * Test we're still on the cpu as well as the version.
-		 * We could have been migrated just after the first
-		 * vgetcpu but before fetching the version, so we
-		 * wouldn't notice a version change.
-		 */
-		cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-	} while (unlikely(cpu != cpu1 ||
-			  (pvti->pvti.version & 1) ||
-			  pvti->pvti.version != version));
-
-	if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+	if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
 		*mode = VCLOCK_NONE;
+		return 0;
+	}
+
+	do {
+		version = pvti->version;
+
+		/* This is also a read barrier, so we'll read version first. */
+		rdtsc_barrier();
+		tsc = __native_read_tsc();
+
+		pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+		pvti_tsc_shift = pvti->tsc_shift;
+		pvti_system_time = pvti->system_time;
+		pvti_tsc = pvti->tsc_timestamp;
+
+		/* Make sure that the version double-check is last. */
+		smp_rmb();
+	} while (unlikely((version & 1) || version != pvti->version));
+
+	delta = tsc - pvti_tsc;
+	ret = pvti_system_time +
+		pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+				    pvti_tsc_shift);
 
 	/* refer to tsc.c read_tsc() comment for rationale */
 	last = gtod->cycle_last;

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

arch/x86/vdso/vclock_gettime.c +47 -35

@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-	const struct pvclock_vsyscall_time_info *pvti;
+	const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
 	cycle_t ret;
-	u64 last;
-	u32 version;
-	u8 flags;
-	unsigned cpu, cpu1;
-
+	u64 tsc, pvti_tsc;
+	u64 last, delta, pvti_system_time;
+	u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
 	/*
-	 * Note: hypervisor must guarantee that:
-	 * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-	 * 2. that per-CPU pvclock time info is updated if the
-	 *    underlying CPU changes.
-	 * 3. that version is increased whenever underlying CPU
-	 *    changes.
+	 * Note: The kernel and hypervisor must guarantee that cpu ID
+	 * number maps 1:1 to per-CPU pvclock time info.
+	 *
+	 * Because the hypervisor is entirely unaware of guest userspace
+	 * preemption, it cannot guarantee that per-CPU pvclock time
+	 * info is updated if the underlying CPU changes or that that
+	 * version is increased whenever underlying CPU changes.
+	 *
+	 * On KVM, we are guaranteed that pvti updates for any vCPU are
+	 * atomic as seen by *all* vCPUs.  This is an even stronger
+	 * guarantee than we get with a normal seqlock.
 	 *
+	 * On Xen, we don't appear to have that guarantee, but Xen still
+	 * supplies a valid seqlock using the version field.
+
+	 * We only do pvclock vdso timing at all if
+	 * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+	 * mean that all vCPUs have matching pvti and that the TSC is
+	 * synced, so we can just look at vCPU 0's pvti.
 	 */
-	do {
-		cpu = __getcpu() & VGETCPU_CPU_MASK;
-		/* TODO: We can put vcpu id into higher bits of pvti.version.
-		 * This will save a couple of cycles by getting rid of
-		 * __getcpu() calls (Gleb).
-		 */
-
-		pvti = get_pvti(cpu);
-
-		version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-		/*
-		 * Test we're still on the cpu as well as the version.
-		 * We could have been migrated just after the first
-		 * vgetcpu but before fetching the version, so we
-		 * wouldn't notice a version change.
-		 */
-		cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-	} while (unlikely(cpu != cpu1 ||
-			  (pvti->pvti.version & 1) ||
-			  pvti->pvti.version != version));
-
-	if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+	if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
 		*mode = VCLOCK_NONE;
+		return 0;
+	}
+
+	do {
+		version = pvti->version;
+
+		/* This is also a read barrier, so we'll read version first. */
+		rdtsc_barrier();
+		tsc = __native_read_tsc();
+
+		pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+		pvti_tsc_shift = pvti->tsc_shift;
+		pvti_system_time = pvti->system_time;
+		pvti_tsc = pvti->tsc_timestamp;
+
+		/* Make sure that the version double-check is last. */
+		smp_rmb();
+	} while (unlikely((version & 1) || version != pvti->version));
+
+	delta = tsc - pvti_tsc;
+	ret = pvti_system_time +
+		pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+				    pvti_tsc_shift);
 
 	/* refer to tsc.c read_tsc() comment for rationale */
 	last = gtod->cycle_last;

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
  arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
  1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +24 -35

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
  static notrace cycle_t vread_pvclock(int *mode)
  {
-	const struct pvclock_vsyscall_time_info *pvti;
+	const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
  	cycle_t ret;
-	u64 last;
-	u32 version;
-	u8 flags;
-	unsigned cpu, cpu1;
-
+	u64 tsc, pvti_tsc;
+	u64 last, delta, pvti_system_time;
+	u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
  	/*
-	 * Note: hypervisor must guarantee that:
-	 * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-	 * 2. that per-CPU pvclock time info is updated if the
-	 *    underlying CPU changes.
-	 * 3. that version is increased whenever underlying CPU
-	 *    changes.
+	 * Note: The kernel and hypervisor must guarantee that cpu ID
+	 * number maps 1:1 to per-CPU pvclock time info.
+	 *
+	 * Because the hypervisor is entirely unaware of guest userspace
+	 * preemption, it cannot guarantee that per-CPU pvclock time
+	 * info is updated if the underlying CPU changes or that that
+	 * version is increased whenever underlying CPU changes.
+	 *
+	 * On KVM, we are guaranteed that pvti updates for any vCPU are
+	 * atomic as seen by *all* vCPUs.  This is an even stronger
+	 * guarantee than we get with a normal seqlock.
  	 *
+	 * On Xen, we don't appear to have that guarantee, but Xen still
+	 * supplies a valid seqlock using the version field.
+
+	 * We only do pvclock vdso timing at all if
+	 * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+	 * mean that all vCPUs have matching pvti and that the TSC is
+	 * synced, so we can just look at vCPU 0's pvti.
  	 */
-	do {
-		cpu = __getcpu() & VGETCPU_CPU_MASK;
-		/* TODO: We can put vcpu id into higher bits of pvti.version.
-		 * This will save a couple of cycles by getting rid of
-		 * __getcpu() calls (Gleb).
-		 */
-
-		pvti = get_pvti(cpu);
-
-		version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-		/*
-		 * Test we're still on the cpu as well as the version.
-		 * We could have been migrated just after the first
-		 * vgetcpu but before fetching the version, so we
-		 * wouldn't notice a version change.
-		 */
-		cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-	} while (unlikely(cpu != cpu1 ||
-			  (pvti->pvti.version & 1) ||
-			  pvti->pvti.version != version));
-
-	if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+	if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {

arch/x86/vdso/vclock_gettime.c +14 -0

+
+		pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+		pvti_tsc_shift = pvti->tsc_shift;
+		pvti_system_time = pvti->system_time;
+		pvti_tsc = pvti->tsc_timestamp;
+
+		/* Make sure that the version double-check is last. */
+		smp_rmb();
+	} while (unlikely((version & 1) || version != pvti->version));
+
+	delta = tsc - pvti_tsc;
+	ret = pvti_system_time +
+		pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+				    pvti_tsc_shift);
 
  	/* refer to tsc.c read_tsc() comment for rationale */
  	last = gtod->cycle_last;

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
  arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
  1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +24 -35

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
  static notrace cycle_t vread_pvclock(int *mode)
  {
-	const struct pvclock_vsyscall_time_info *pvti;
+	const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
  	cycle_t ret;
-	u64 last;
-	u32 version;
-	u8 flags;
-	unsigned cpu, cpu1;
-
+	u64 tsc, pvti_tsc;
+	u64 last, delta, pvti_system_time;
+	u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
  	/*
-	 * Note: hypervisor must guarantee that:
-	 * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-	 * 2. that per-CPU pvclock time info is updated if the
-	 *    underlying CPU changes.
-	 * 3. that version is increased whenever underlying CPU
-	 *    changes.
+	 * Note: The kernel and hypervisor must guarantee that cpu ID
+	 * number maps 1:1 to per-CPU pvclock time info.
+	 *
+	 * Because the hypervisor is entirely unaware of guest userspace
+	 * preemption, it cannot guarantee that per-CPU pvclock time
+	 * info is updated if the underlying CPU changes or that that
+	 * version is increased whenever underlying CPU changes.
+	 *
+	 * On KVM, we are guaranteed that pvti updates for any vCPU are
+	 * atomic as seen by *all* vCPUs.  This is an even stronger
+	 * guarantee than we get with a normal seqlock.
  	 *
+	 * On Xen, we don't appear to have that guarantee, but Xen still
+	 * supplies a valid seqlock using the version field.
+
+	 * We only do pvclock vdso timing at all if
+	 * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+	 * mean that all vCPUs have matching pvti and that the TSC is
+	 * synced, so we can just look at vCPU 0's pvti.
  	 */
-	do {
-		cpu = __getcpu() & VGETCPU_CPU_MASK;
-		/* TODO: We can put vcpu id into higher bits of pvti.version.
-		 * This will save a couple of cycles by getting rid of
-		 * __getcpu() calls (Gleb).
-		 */
-
-		pvti = get_pvti(cpu);
-
-		version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-		/*
-		 * Test we're still on the cpu as well as the version.
-		 * We could have been migrated just after the first
-		 * vgetcpu but before fetching the version, so we
-		 * wouldn't notice a version change.
-		 */
-		cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-	} while (unlikely(cpu != cpu1 ||
-			  (pvti->pvti.version & 1) ||
-			  pvti->pvti.version != version));
-
-	if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+	if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {

arch/x86/vdso/vclock_gettime.c +14 -0

+
+		pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+		pvti_tsc_shift = pvti->tsc_shift;
+		pvti_system_time = pvti->system_time;
+		pvti_tsc = pvti->tsc_timestamp;
+
+		/* Make sure that the version double-check is last. */
+		smp_rmb();
+	} while (unlikely((version & 1) || version != pvti->version));
+
+	delta = tsc - pvti_tsc;
+	ret = pvti_system_time +
+		pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+				    pvti_tsc_shift);
 
  	/* refer to tsc.c read_tsc() comment for rationale */
  	last = gtod->cycle_last;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 119

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +6 -0

+    do {
+        version = pvti->version;
+
+        /* This is also a read barrier, so we'll read version first. */
+        rdtsc_barrier();
+        tsc = __native_read_tsc();

This will cause VMEXIT on Xen with TSC_MODE_ALWAYS_EMULATE which is used, for example, after guest migrated (unless HW is capable of scaling TSC rate).

Quoted 7 lines · Boris Ostrovsky

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +6 -0

+    do {
+        version = pvti->version;
+
+        /* This is also a read barrier, so we'll read version first. */
+        rdtsc_barrier();
+        tsc = __native_read_tsc();

Quoted 3 lines

This will cause VMEXIT on Xen with TSC_MODE_ALWAYS_EMULATE which is used, for example, after guest migrated (unless HW is capable of scaling TSC rate).

So does the __pvclock_read_cycles this is replacing (via pvclock_get_nsec_offset).

Quoted 7 lines · Boris Ostrovsky

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +6 -0

+    do {
+        version = pvti->version;
+
+        /* This is also a read barrier, so we'll read version first. */
+        rdtsc_barrier();
+        tsc = __native_read_tsc();

Quoted 3 lines

This will cause VMEXIT on Xen with TSC_MODE_ALWAYS_EMULATE which is used, for example, after guest migrated (unless HW is capable of scaling TSC rate).

So does the __pvclock_read_cycles this is replacing (via pvclock_get_nsec_offset).

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 119

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +6 -0

+    do {
+        version = pvti->version;
+
+        /* This is also a read barrier, so we'll read version first. */
+        rdtsc_barrier();
+        tsc = __native_read_tsc();

This will cause VMEXIT on Xen with TSC_MODE_ALWAYS_EMULATE which is used, for example, after guest migrated (unless HW is capable of scaling TSC rate).

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +9 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-       const struct pvclock_vsyscall_time_info *pvti;
+       const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
        cycle_t ret;
-       u64 last;
-       u32 version;
-       u8 flags;
-       unsigned cpu, cpu1;
-
+       u64 tsc, pvti_tsc;
+       u64 last, delta, pvti_system_time;
+       u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
        /*
-        * Note: hypervisor must guarantee that:
-        * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-        * 2. that per-CPU pvclock time info is updated if the
-        *    underlying CPU changes.
-        * 3. that version is increased whenever underlying CPU
-        *    changes.
+        * Note: The kernel and hypervisor must guarantee that cpu ID
+        * number maps 1:1 to per-CPU pvclock time info.
+        *
+        * Because the hypervisor is entirely unaware of guest userspace
+        * preemption, it cannot guarantee that per-CPU pvclock time

arch/x86/vdso/vclock_gettime.c +6 -23

+        * We only do pvclock vdso timing at all if
+        * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+        * mean that all vCPUs have matching pvti and that the TSC is
+        * synced, so we can just look at vCPU 0's pvti.
         */
-       do {
-               cpu = __getcpu() & VGETCPU_CPU_MASK;
-               /* TODO: We can put vcpu id into higher bits of pvti.version.
-                * This will save a couple of cycles by getting rid of
-                * __getcpu() calls (Gleb).
-                */
-
-               pvti = get_pvti(cpu);
-
-               version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-               /*
-                * Test we're still on the cpu as well as the version.
-                * We could have been migrated just after the first
-                * vgetcpu but before fetching the version, so we
-                * wouldn't notice a version change.
-                */
-               cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-       } while (unlikely(cpu != cpu1 ||
-                         (pvti->pvti.version & 1) ||
-                         pvti->pvti.version != version));
-
-       if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+       if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {

arch/x86/vdso/vclock_gettime.c +14 -1

+
+               pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+               pvti_tsc_shift = pvti->tsc_shift;
+               pvti_system_time = pvti->system_time;
+               pvti_tsc = pvti->tsc_timestamp;
+
+               /* Make sure that the version double-check is last. */
+               smp_rmb();
+       } while (unlikely((version & 1) || version != pvti->version));
+
+       delta = tsc - pvti_tsc;
+       ret = pvti_system_time +
+               pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                   pvti_tsc_shift);
 
        /* refer to tsc.c read_tsc() comment for rationale */
        last = gtod->cycle_last;
--

2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 47 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +9 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-       const struct pvclock_vsyscall_time_info *pvti;
+       const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
        cycle_t ret;
-       u64 last;
-       u32 version;
-       u8 flags;
-       unsigned cpu, cpu1;
-
+       u64 tsc, pvti_tsc;
+       u64 last, delta, pvti_system_time;
+       u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
        /*
-        * Note: hypervisor must guarantee that:
-        * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-        * 2. that per-CPU pvclock time info is updated if the
-        *    underlying CPU changes.
-        * 3. that version is increased whenever underlying CPU
-        *    changes.
+        * Note: The kernel and hypervisor must guarantee that cpu ID
+        * number maps 1:1 to per-CPU pvclock time info.
+        *
+        * Because the hypervisor is entirely unaware of guest userspace
+        * preemption, it cannot guarantee that per-CPU pvclock time

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 102

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +9 -0

+        * info is updated if the underlying CPU changes or that that
+        * version is increased whenever underlying CPU changes.
+        *
+        * On KVM, we are guaranteed that pvti updates for any vCPU are
+        * atomic as seen by *all* vCPUs.  This is an even stronger
+        * guarantee than we get with a normal seqlock.
         *
+        * On Xen, we don't appear to have that guarantee, but Xen still
+        * supplies a valid seqlock using the version field.
+

Forgotten * here?

Quoted 35 lines

arch/x86/vdso/vclock_gettime.c +10 -23

+        * We only do pvclock vdso timing at all if
+        * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+        * mean that all vCPUs have matching pvti and that the TSC is
+        * synced, so we can just look at vCPU 0's pvti.
         */
-       do {
-               cpu = __getcpu() & VGETCPU_CPU_MASK;
-               /* TODO: We can put vcpu id into higher bits of pvti.version.
-                * This will save a couple of cycles by getting rid of
-                * __getcpu() calls (Gleb).
-                */
-
-               pvti = get_pvti(cpu);
-
-               version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-               /*
-                * Test we're still on the cpu as well as the version.
-                * We could have been migrated just after the first
-                * vgetcpu but before fetching the version, so we
-                * wouldn't notice a version change.
-                */
-               cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-       } while (unlikely(cpu != cpu1 ||
-                         (pvti->pvti.version & 1) ||
-                         pvti->pvti.version != version));
-
-       if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+       if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
                *mode = VCLOCK_NONE;
+               return 0;
+       }
+
+       do {

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 119

Quoted 5 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+               version = pvti->version;
+
+               /* This is also a read barrier, so we'll read version first. */
+               rdtsc_barrier();
+               tsc = __native_read_tsc();

Is there a reason why you read the tsc inside the loop rather than once after the loop?

Quoted 26 lines

arch/x86/vdso/vclock_gettime.c +14 -1

+
+               pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+               pvti_tsc_shift = pvti->tsc_shift;
+               pvti_system_time = pvti->system_time;
+               pvti_tsc = pvti->tsc_timestamp;
+
+               /* Make sure that the version double-check is last. */
+               smp_rmb();
+       } while (unlikely((version & 1) || version != pvti->version));
+
+       delta = tsc - pvti_tsc;
+       ret = pvti_system_time +
+               pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                   pvti_tsc_shift);
 
        /* refer to tsc.c read_tsc() comment for rationale */
        last = gtod->cycle_last;
--

2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 47 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +9 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-       const struct pvclock_vsyscall_time_info *pvti;
+       const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
        cycle_t ret;
-       u64 last;
-       u32 version;
-       u8 flags;
-       unsigned cpu, cpu1;
-
+       u64 tsc, pvti_tsc;
+       u64 last, delta, pvti_system_time;
+       u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
        /*
-        * Note: hypervisor must guarantee that:
-        * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-        * 2. that per-CPU pvclock time info is updated if the
-        *    underlying CPU changes.
-        * 3. that version is increased whenever underlying CPU
-        *    changes.
+        * Note: The kernel and hypervisor must guarantee that cpu ID
+        * number maps 1:1 to per-CPU pvclock time info.
+        *
+        * Because the hypervisor is entirely unaware of guest userspace
+        * preemption, it cannot guarantee that per-CPU pvclock time

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 102

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +9 -0

+        * info is updated if the underlying CPU changes or that that
+        * version is increased whenever underlying CPU changes.
+        *
+        * On KVM, we are guaranteed that pvti updates for any vCPU are
+        * atomic as seen by *all* vCPUs.  This is an even stronger
+        * guarantee than we get with a normal seqlock.
         *
+        * On Xen, we don't appear to have that guarantee, but Xen still
+        * supplies a valid seqlock using the version field.
+

Forgotten * here?

Quoted 35 lines

arch/x86/vdso/vclock_gettime.c +10 -23

+        * We only do pvclock vdso timing at all if
+        * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+        * mean that all vCPUs have matching pvti and that the TSC is
+        * synced, so we can just look at vCPU 0's pvti.
         */
-       do {
-               cpu = __getcpu() & VGETCPU_CPU_MASK;
-               /* TODO: We can put vcpu id into higher bits of pvti.version.
-                * This will save a couple of cycles by getting rid of
-                * __getcpu() calls (Gleb).
-                */
-
-               pvti = get_pvti(cpu);
-
-               version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-               /*
-                * Test we're still on the cpu as well as the version.
-                * We could have been migrated just after the first
-                * vgetcpu but before fetching the version, so we
-                * wouldn't notice a version change.
-                */
-               cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-       } while (unlikely(cpu != cpu1 ||
-                         (pvti->pvti.version & 1) ||
-                         pvti->pvti.version != version));
-
-       if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+       if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
                *mode = VCLOCK_NONE;
+               return 0;
+       }
+
+       do {

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 119

Quoted 5 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+               version = pvti->version;
+
+               /* This is also a read barrier, so we'll read version first. */
+               rdtsc_barrier();
+               tsc = __native_read_tsc();

Is there a reason why you read the tsc inside the loop rather than once after the loop?

Quoted 26 lines

arch/x86/vdso/vclock_gettime.c +14 -1

+
+               pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+               pvti_tsc_shift = pvti->tsc_shift;
+               pvti_system_time = pvti->system_time;
+               pvti_tsc = pvti->tsc_timestamp;
+
+               /* Make sure that the version double-check is last. */
+               smp_rmb();
+       } while (unlikely((version & 1) || version != pvti->version));
+
+       delta = tsc - pvti_tsc;
+       ret = pvti_system_time +
+               pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                   pvti_tsc_shift);
 
        /* refer to tsc.c read_tsc() comment for rationale */
        last = gtod->cycle_last;
--

2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +9 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-       const struct pvclock_vsyscall_time_info *pvti;
+       const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
        cycle_t ret;
-       u64 last;
-       u32 version;
-       u8 flags;
-       unsigned cpu, cpu1;
-
+       u64 tsc, pvti_tsc;
+       u64 last, delta, pvti_system_time;
+       u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
        /*
-        * Note: hypervisor must guarantee that:
-        * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-        * 2. that per-CPU pvclock time info is updated if the
-        *    underlying CPU changes.
-        * 3. that version is increased whenever underlying CPU
-        *    changes.
+        * Note: The kernel and hypervisor must guarantee that cpu ID
+        * number maps 1:1 to per-CPU pvclock time info.
+        *
+        * Because the hypervisor is entirely unaware of guest userspace
+        * preemption, it cannot guarantee that per-CPU pvclock time

arch/x86/vdso/vclock_gettime.c +6 -23

+        * We only do pvclock vdso timing at all if
+        * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+        * mean that all vCPUs have matching pvti and that the TSC is
+        * synced, so we can just look at vCPU 0's pvti.
         */
-       do {
-               cpu = __getcpu() & VGETCPU_CPU_MASK;
-               /* TODO: We can put vcpu id into higher bits of pvti.version.
-                * This will save a couple of cycles by getting rid of
-                * __getcpu() calls (Gleb).
-                */
-
-               pvti = get_pvti(cpu);
-
-               version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-               /*
-                * Test we're still on the cpu as well as the version.
-                * We could have been migrated just after the first
-                * vgetcpu but before fetching the version, so we
-                * wouldn't notice a version change.
-                */
-               cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-       } while (unlikely(cpu != cpu1 ||
-                         (pvti->pvti.version & 1) ||
-                         pvti->pvti.version != version));
-
-       if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+       if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {

arch/x86/vdso/vclock_gettime.c +14 -1

+
+               pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+               pvti_tsc_shift = pvti->tsc_shift;
+               pvti_system_time = pvti->system_time;
+               pvti_tsc = pvti->tsc_timestamp;
+
+               /* Make sure that the version double-check is last. */
+               smp_rmb();
+       } while (unlikely((version & 1) || version != pvti->version));
+
+       delta = tsc - pvti_tsc;
+       ret = pvti_system_time +
+               pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                   pvti_tsc_shift);
 
        /* refer to tsc.c read_tsc() comment for rationale */
        last = gtod->cycle_last;
--

2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +14 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-	const struct pvclock_vsyscall_time_info *pvti;
+	const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
 	cycle_t ret;
-	u64 last;
-	u32 version;
-	u8 flags;
-	unsigned cpu, cpu1;
-
+	u64 tsc, pvti_tsc;
+	u64 last, delta, pvti_system_time;
+	u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
 	/*
-	 * Note: hypervisor must guarantee that:
-	 * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-	 * 2. that per-CPU pvclock time info is updated if the
-	 *    underlying CPU changes.
-	 * 3. that version is increased whenever underlying CPU
-	 *    changes.
+	 * Note: The kernel and hypervisor must guarantee that cpu ID
+	 * number maps 1:1 to per-CPU pvclock time info.
+	 *
+	 * Because the hypervisor is entirely unaware of guest userspace
+	 * preemption, it cannot guarantee that per-CPU pvclock time
+	 * info is updated if the underlying CPU changes or that that
+	 * version is increased whenever underlying CPU changes.
+	 *
+	 * On KVM, we are guaranteed that pvti updates for any vCPU are
+	 * atomic as seen by *all* vCPUs.  This is an even stronger

arch/x86/vdso/vclock_gettime.c +0 -18

-	do {
-		cpu = __getcpu() & VGETCPU_CPU_MASK;
-		/* TODO: We can put vcpu id into higher bits of pvti.version.
-		 * This will save a couple of cycles by getting rid of
-		 * __getcpu() calls (Gleb).
-		 */
-
-		pvti = get_pvti(cpu);
-
-		version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-		/*
-		 * Test we're still on the cpu as well as the version.
-		 * We could have been migrated just after the first
-		 * vgetcpu but before fetching the version, so we
-		 * wouldn't notice a version change.
-		 */
-		cpu1 = __getcpu() & VGETCPU_CPU_MASK;

arch/x86/vdso/vclock_gettime.c +11 -0

+
+	do {
+		version = pvti->version;
+
+		/* This is also a read barrier, so we'll read version first. */
+		rdtsc_barrier();
+		tsc = __native_read_tsc();
+
+		pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+		pvti_tsc_shift = pvti->tsc_shift;
+		pvti_system_time = pvti->system_time;

Quoted 56 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +17 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-     const struct pvclock_vsyscall_time_info *pvti;
+     const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
      cycle_t ret;
-     u64 last;
-     u32 version;
-     u8 flags;
-     unsigned cpu, cpu1;
-
+     u64 tsc, pvti_tsc;
+     u64 last, delta, pvti_system_time;
+     u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
      /*
-      * Note: hypervisor must guarantee that:
-      * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-      * 2. that per-CPU pvclock time info is updated if the
-      *    underlying CPU changes.
-      * 3. that version is increased whenever underlying CPU
-      *    changes.
+      * Note: The kernel and hypervisor must guarantee that cpu ID
+      * number maps 1:1 to per-CPU pvclock time info.
+      *
+      * Because the hypervisor is entirely unaware of guest userspace
+      * preemption, it cannot guarantee that per-CPU pvclock time
+      * info is updated if the underlying CPU changes or that that
+      * version is increased whenever underlying CPU changes.
+      *
+      * On KVM, we are guaranteed that pvti updates for any vCPU are
+      * atomic as seen by *all* vCPUs.  This is an even stronger
+      * guarantee than we get with a normal seqlock.
       *
+      * On Xen, we don't appear to have that guarantee, but Xen still
+      * supplies a valid seqlock using the version field.

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 107

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+
+      * We only do pvclock vdso timing at all if
+      * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+      * mean that all vCPUs have matching pvti and that the TSC is
+      * synced, so we can just look at vCPU 0's pvti.
       */

Can Xen guarantee that ?

Quoted 23 lines

arch/x86/vdso/vclock_gettime.c +0 -22

-     do {
-             cpu = __getcpu() & VGETCPU_CPU_MASK;
-             /* TODO: We can put vcpu id into higher bits of pvti.version.
-              * This will save a couple of cycles by getting rid of
-              * __getcpu() calls (Gleb).
-              */
-
-             pvti = get_pvti(cpu);
-
-             version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-             /*
-              * Test we're still on the cpu as well as the version.
-              * We could have been migrated just after the first
-              * vgetcpu but before fetching the version, so we
-              * wouldn't notice a version change.
-              */
-             cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-     } while (unlikely(cpu != cpu1 ||
-                       (pvti->pvti.version & 1) ||
-                       pvti->pvti.version != version));
-

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 112

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +4 -1

-     if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+     if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
              *mode = VCLOCK_NONE;
+             return 0;
+     }

This check must be performed after reading a stable pvti.

Quoted 11 lines

arch/x86/vdso/vclock_gettime.c +11 -0

+
+     do {
+             version = pvti->version;
+
+             /* This is also a read barrier, so we'll read version first. */
+             rdtsc_barrier();
+             tsc = __native_read_tsc();
+
+             pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+             pvti_tsc_shift = pvti->tsc_shift;
+             pvti_system_time = pvti->system_time;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 133

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +10 -0

+             pvti_tsc = pvti->tsc_timestamp;
+
+             /* Make sure that the version double-check is last. */
+             smp_rmb();
+     } while (unlikely((version & 1) || version != pvti->version));
+
+     delta = tsc - pvti_tsc;
+     ret = pvti_system_time +
+             pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                 pvti_tsc_shift);

The following is possible:

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Quoted 8 lines

Quoted 8 lines

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 4 lines

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable? Otherwise the vdso could could just as easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

Quoted 8 lines

Quoted 8 lines

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 4 lines

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable? Otherwise the vdso could could just as easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

Quoted 57 lines · Marcelo Tosatti

Quoted 56 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +17 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-     const struct pvclock_vsyscall_time_info *pvti;
+     const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
      cycle_t ret;
-     u64 last;
-     u32 version;
-     u8 flags;
-     unsigned cpu, cpu1;
-
+     u64 tsc, pvti_tsc;
+     u64 last, delta, pvti_system_time;
+     u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
      /*
-      * Note: hypervisor must guarantee that:
-      * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-      * 2. that per-CPU pvclock time info is updated if the
-      *    underlying CPU changes.
-      * 3. that version is increased whenever underlying CPU
-      *    changes.
+      * Note: The kernel and hypervisor must guarantee that cpu ID
+      * number maps 1:1 to per-CPU pvclock time info.
+      *
+      * Because the hypervisor is entirely unaware of guest userspace
+      * preemption, it cannot guarantee that per-CPU pvclock time
+      * info is updated if the underlying CPU changes or that that
+      * version is increased whenever underlying CPU changes.
+      *
+      * On KVM, we are guaranteed that pvti updates for any vCPU are
+      * atomic as seen by *all* vCPUs.  This is an even stronger
+      * guarantee than we get with a normal seqlock.
       *
+      * On Xen, we don't appear to have that guarantee, but Xen still
+      * supplies a valid seqlock using the version field.

Quoted 8 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 107

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+
+      * We only do pvclock vdso timing at all if
+      * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+      * mean that all vCPUs have matching pvti and that the TSC is
+      * synced, so we can just look at vCPU 0's pvti.
       */

Can Xen guarantee that ?

I think so, vacuously. Xen doesn't seem to set PVCLOCK_TSC_STABLE_BIT at all. I have no idea going forward, though.

Xen people?

Quoted 23 lines

Quoted 23 lines

arch/x86/vdso/vclock_gettime.c +0 -22

-     do {
-             cpu = __getcpu() & VGETCPU_CPU_MASK;
-             /* TODO: We can put vcpu id into higher bits of pvti.version.
-              * This will save a couple of cycles by getting rid of
-              * __getcpu() calls (Gleb).
-              */
-
-             pvti = get_pvti(cpu);
-
-             version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-             /*
-              * Test we're still on the cpu as well as the version.
-              * We could have been migrated just after the first
-              * vgetcpu but before fetching the version, so we
-              * wouldn't notice a version change.
-              */
-             cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-     } while (unlikely(cpu != cpu1 ||
-                       (pvti->pvti.version & 1) ||
-                       pvti->pvti.version != version));
-

Quoted 9 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 112

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +4 -1

-     if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+     if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
              *mode = VCLOCK_NONE;
+             return 0;
+     }

This check must be performed after reading a stable pvti.

We can even read it in the middle, guarded by the version checks. I'll do that for v2.

Quoted 32 lines

Quoted 11 lines

arch/x86/vdso/vclock_gettime.c +11 -0

+
+     do {
+             version = pvti->version;
+
+             /* This is also a read barrier, so we'll read version first. */
+             rdtsc_barrier();
+             tsc = __native_read_tsc();
+
+             pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+             pvti_tsc_shift = pvti->tsc_shift;
+             pvti_system_time = pvti->system_time;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 133

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +10 -0

+             pvti_tsc = pvti->tsc_timestamp;
+
+             /* Make sure that the version double-check is last. */
+             smp_rmb();
+     } while (unlikely((version & 1) || version != pvti->version));
+
+     delta = tsc - pvti_tsc;
+     ret = pvti_system_time +
+             pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                 pvti_tsc_shift);

The following is possible:

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable?

Otherwise the vdso could could just as
easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

Quoted 140 lines · Andy Lutomirski

Quoted 57 lines · Marcelo Tosatti

Quoted 56 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +17 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-     const struct pvclock_vsyscall_time_info *pvti;
+     const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
      cycle_t ret;
-     u64 last;
-     u32 version;
-     u8 flags;
-     unsigned cpu, cpu1;
-
+     u64 tsc, pvti_tsc;
+     u64 last, delta, pvti_system_time;
+     u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
      /*
-      * Note: hypervisor must guarantee that:
-      * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-      * 2. that per-CPU pvclock time info is updated if the
-      *    underlying CPU changes.
-      * 3. that version is increased whenever underlying CPU
-      *    changes.
+      * Note: The kernel and hypervisor must guarantee that cpu ID
+      * number maps 1:1 to per-CPU pvclock time info.
+      *
+      * Because the hypervisor is entirely unaware of guest userspace
+      * preemption, it cannot guarantee that per-CPU pvclock time
+      * info is updated if the underlying CPU changes or that that
+      * version is increased whenever underlying CPU changes.
+      *
+      * On KVM, we are guaranteed that pvti updates for any vCPU are
+      * atomic as seen by *all* vCPUs.  This is an even stronger
+      * guarantee than we get with a normal seqlock.
       *
+      * On Xen, we don't appear to have that guarantee, but Xen still
+      * supplies a valid seqlock using the version field.

Quoted 8 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 107

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+
+      * We only do pvclock vdso timing at all if
+      * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+      * mean that all vCPUs have matching pvti and that the TSC is
+      * synced, so we can just look at vCPU 0's pvti.
       */

Can Xen guarantee that ?

I think so, vacuously. Xen doesn't seem to set PVCLOCK_TSC_STABLE_BIT at all. I have no idea going forward, though.

Xen people?

Quoted 23 lines

Quoted 23 lines

arch/x86/vdso/vclock_gettime.c +0 -22

-     do {
-             cpu = __getcpu() & VGETCPU_CPU_MASK;
-             /* TODO: We can put vcpu id into higher bits of pvti.version.
-              * This will save a couple of cycles by getting rid of
-              * __getcpu() calls (Gleb).
-              */
-
-             pvti = get_pvti(cpu);
-
-             version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-             /*
-              * Test we're still on the cpu as well as the version.
-              * We could have been migrated just after the first
-              * vgetcpu but before fetching the version, so we
-              * wouldn't notice a version change.
-              */
-             cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-     } while (unlikely(cpu != cpu1 ||
-                       (pvti->pvti.version & 1) ||
-                       pvti->pvti.version != version));
-

Quoted 9 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 112

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +4 -1

-     if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+     if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
              *mode = VCLOCK_NONE;
+             return 0;
+     }

This check must be performed after reading a stable pvti.

We can even read it in the middle, guarded by the version checks. I'll do that for v2.

Quoted 32 lines

Quoted 11 lines

arch/x86/vdso/vclock_gettime.c +11 -0

+
+     do {
+             version = pvti->version;
+
+             /* This is also a read barrier, so we'll read version first. */
+             rdtsc_barrier();
+             tsc = __native_read_tsc();
+
+             pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+             pvti_tsc_shift = pvti->tsc_shift;
+             pvti_system_time = pvti->system_time;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 133

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +10 -0

+             pvti_tsc = pvti->tsc_timestamp;
+
+             /* Make sure that the version double-check is last. */
+             smp_rmb();
+     } while (unlikely((version & 1) || version != pvti->version));
+
+     delta = tsc - pvti_tsc;
+     ret = pvti_system_time +
+             pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                 pvti_tsc_shift);

The following is possible:

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 7 lines

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable?

Yes. It will VM-enter after pvti is updated.

Quoted 3 lines

Otherwise the vdso could could just as
easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

Right.

Quoted 3 lines

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

The update is performed as follows:

- Stop guest instruction execution on every vCPU, parking them in the host.
- Request KVMCLOCK update for every vCPU.
- Resume guest instruction execution.

The KVMCLOCK update (==pvti update) is guaranteed to be performed before guest instructions are executed again.

But there is no guarantee that vCPU-N has updated its pvti when vCPU-M resumes guest instruction execution.

So the cost this patch removes is mainly from __getcpu (==RDTSCP?) ?

Perhaps you can use Gleb's idea to stick vcpu id into version field ?

Quoted 170 lines · Marcelo Tosatti

Quoted 140 lines · Andy Lutomirski

Quoted 57 lines · Marcelo Tosatti

Quoted 56 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +17 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-     const struct pvclock_vsyscall_time_info *pvti;
+     const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
      cycle_t ret;
-     u64 last;
-     u32 version;
-     u8 flags;
-     unsigned cpu, cpu1;
-
+     u64 tsc, pvti_tsc;
+     u64 last, delta, pvti_system_time;
+     u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
      /*
-      * Note: hypervisor must guarantee that:
-      * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-      * 2. that per-CPU pvclock time info is updated if the
-      *    underlying CPU changes.
-      * 3. that version is increased whenever underlying CPU
-      *    changes.
+      * Note: The kernel and hypervisor must guarantee that cpu ID
+      * number maps 1:1 to per-CPU pvclock time info.
+      *
+      * Because the hypervisor is entirely unaware of guest userspace
+      * preemption, it cannot guarantee that per-CPU pvclock time
+      * info is updated if the underlying CPU changes or that that
+      * version is increased whenever underlying CPU changes.
+      *
+      * On KVM, we are guaranteed that pvti updates for any vCPU are
+      * atomic as seen by *all* vCPUs.  This is an even stronger
+      * guarantee than we get with a normal seqlock.
       *
+      * On Xen, we don't appear to have that guarantee, but Xen still
+      * supplies a valid seqlock using the version field.

Quoted 8 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 107

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+
+      * We only do pvclock vdso timing at all if
+      * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+      * mean that all vCPUs have matching pvti and that the TSC is
+      * synced, so we can just look at vCPU 0's pvti.
       */

Can Xen guarantee that ?

I think so, vacuously. Xen doesn't seem to set PVCLOCK_TSC_STABLE_BIT at all. I have no idea going forward, though.

Xen people?

Quoted 23 lines

Quoted 23 lines

arch/x86/vdso/vclock_gettime.c +0 -22

-     do {
-             cpu = __getcpu() & VGETCPU_CPU_MASK;
-             /* TODO: We can put vcpu id into higher bits of pvti.version.
-              * This will save a couple of cycles by getting rid of
-              * __getcpu() calls (Gleb).
-              */
-
-             pvti = get_pvti(cpu);
-
-             version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-             /*
-              * Test we're still on the cpu as well as the version.
-              * We could have been migrated just after the first
-              * vgetcpu but before fetching the version, so we
-              * wouldn't notice a version change.
-              */
-             cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-     } while (unlikely(cpu != cpu1 ||
-                       (pvti->pvti.version & 1) ||
-                       pvti->pvti.version != version));
-

Quoted 9 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 112

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +4 -1

-     if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+     if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
              *mode = VCLOCK_NONE;
+             return 0;
+     }

This check must be performed after reading a stable pvti.

We can even read it in the middle, guarded by the version checks. I'll do that for v2.

Quoted 32 lines

Quoted 11 lines

arch/x86/vdso/vclock_gettime.c +11 -0

+
+     do {
+             version = pvti->version;
+
+             /* This is also a read barrier, so we'll read version first. */
+             rdtsc_barrier();
+             tsc = __native_read_tsc();
+
+             pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+             pvti_tsc_shift = pvti->tsc_shift;
+             pvti_system_time = pvti->system_time;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 133

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +10 -0

+             pvti_tsc = pvti->tsc_timestamp;
+
+             /* Make sure that the version double-check is last. */
+             smp_rmb();
+     } while (unlikely((version & 1) || version != pvti->version));
+
+     delta = tsc - pvti_tsc;
+     ret = pvti_system_time +
+             pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                 pvti_tsc_shift);

The following is possible:

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 7 lines

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable?

Yes. It will VM-enter after pvti is updated.

Quoted 3 lines

Otherwise the vdso could could just as
easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

Right.

Quoted 3 lines

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

The update is performed as follows:

- Stop guest instruction execution on every vCPU, parking them in the host.
- Request KVMCLOCK update for every vCPU.
- Resume guest instruction execution.

The KVMCLOCK update (==pvti update) is guaranteed to be performed before guest instructions are executed again.

Quoted 2 lines

But there is no guarantee that vCPU-N has updated its pvti when vCPU-M resumes guest instruction execution.

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Quoted 1 line

So the cost this patch removes is mainly from __getcpu (==RDTSCP?) ?

It removes a whole bunch of code, an extra barrier, and two __getcpus.

Quoted 1 line

Perhaps you can use Gleb's idea to stick vcpu id into version field ?

I don't understand how that's useful at all. If you're reading pvti, you clearly know the vcpu id.

Quoted 174 lines · Andy Lutomirski

Quoted 172 lines · Marcelo Tosatti

Quoted 140 lines · Andy Lutomirski

Quoted 57 lines · Marcelo Tosatti

Quoted 56 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +17 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-     const struct pvclock_vsyscall_time_info *pvti;
+     const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
      cycle_t ret;
-     u64 last;
-     u32 version;
-     u8 flags;
-     unsigned cpu, cpu1;
-
+     u64 tsc, pvti_tsc;
+     u64 last, delta, pvti_system_time;
+     u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
      /*
-      * Note: hypervisor must guarantee that:
-      * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-      * 2. that per-CPU pvclock time info is updated if the
-      *    underlying CPU changes.
-      * 3. that version is increased whenever underlying CPU
-      *    changes.
+      * Note: The kernel and hypervisor must guarantee that cpu ID
+      * number maps 1:1 to per-CPU pvclock time info.
+      *
+      * Because the hypervisor is entirely unaware of guest userspace
+      * preemption, it cannot guarantee that per-CPU pvclock time
+      * info is updated if the underlying CPU changes or that that
+      * version is increased whenever underlying CPU changes.
+      *
+      * On KVM, we are guaranteed that pvti updates for any vCPU are
+      * atomic as seen by *all* vCPUs.  This is an even stronger
+      * guarantee than we get with a normal seqlock.
       *
+      * On Xen, we don't appear to have that guarantee, but Xen still
+      * supplies a valid seqlock using the version field.

Quoted 8 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 107

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+
+      * We only do pvclock vdso timing at all if
+      * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+      * mean that all vCPUs have matching pvti and that the TSC is
+      * synced, so we can just look at vCPU 0's pvti.
       */

Can Xen guarantee that ?

I think so, vacuously. Xen doesn't seem to set PVCLOCK_TSC_STABLE_BIT at all. I have no idea going forward, though.

Xen people?

Quoted 23 lines

Quoted 23 lines

arch/x86/vdso/vclock_gettime.c +0 -22

-     do {
-             cpu = __getcpu() & VGETCPU_CPU_MASK;
-             /* TODO: We can put vcpu id into higher bits of pvti.version.
-              * This will save a couple of cycles by getting rid of
-              * __getcpu() calls (Gleb).
-              */
-
-             pvti = get_pvti(cpu);
-
-             version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-             /*
-              * Test we're still on the cpu as well as the version.
-              * We could have been migrated just after the first
-              * vgetcpu but before fetching the version, so we
-              * wouldn't notice a version change.
-              */
-             cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-     } while (unlikely(cpu != cpu1 ||
-                       (pvti->pvti.version & 1) ||
-                       pvti->pvti.version != version));
-

Quoted 9 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 112

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +4 -1

-     if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+     if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
              *mode = VCLOCK_NONE;
+             return 0;
+     }

This check must be performed after reading a stable pvti.

We can even read it in the middle, guarded by the version checks. I'll do that for v2.

Quoted 32 lines

Quoted 11 lines

arch/x86/vdso/vclock_gettime.c +11 -0

+
+     do {
+             version = pvti->version;
+
+             /* This is also a read barrier, so we'll read version first. */
+             rdtsc_barrier();
+             tsc = __native_read_tsc();
+
+             pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+             pvti_tsc_shift = pvti->tsc_shift;
+             pvti_system_time = pvti->system_time;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 133

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +10 -0

+             pvti_tsc = pvti->tsc_timestamp;
+
+             /* Make sure that the version double-check is last. */
+             smp_rmb();
+     } while (unlikely((version & 1) || version != pvti->version));
+
+     delta = tsc - pvti_tsc;
+     ret = pvti_system_time +
+             pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                 pvti_tsc_shift);

The following is possible:

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 7 lines

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable?

Yes. It will VM-enter after pvti is updated.

Quoted 3 lines

Otherwise the vdso could could just as
easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

Right.

Quoted 3 lines

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

The update is performed as follows:

- Stop guest instruction execution on every vCPU, parking them in the host.
- Request KVMCLOCK update for every vCPU.
- Resume guest instruction execution.

The KVMCLOCK update (==pvti update) is guaranteed to be performed before guest instructions are executed again.

But there is no guarantee that vCPU-N has updated its pvti when vCPU-M resumes guest instruction execution.

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

Quoted 9 lines

Quoted 2 lines

So the cost this patch removes is mainly from __getcpu (==RDTSCP?) ?

It removes a whole bunch of code, an extra barrier, and two __getcpus.

Quoted 1 line

Perhaps you can use Gleb's idea to stick vcpu id into version field ?

I don't understand how that's useful at all. If you're reading pvti, you clearly know the vcpu id.

Replace the return value of __getcpus by value read from pvti.version.

Quoted 174 lines · Andy Lutomirski

Quoted 172 lines · Marcelo Tosatti

Quoted 140 lines · Andy Lutomirski

Quoted 57 lines · Marcelo Tosatti

Quoted 56 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +17 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-     const struct pvclock_vsyscall_time_info *pvti;
+     const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
      cycle_t ret;
-     u64 last;
-     u32 version;
-     u8 flags;
-     unsigned cpu, cpu1;
-
+     u64 tsc, pvti_tsc;
+     u64 last, delta, pvti_system_time;
+     u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
      /*
-      * Note: hypervisor must guarantee that:
-      * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-      * 2. that per-CPU pvclock time info is updated if the
-      *    underlying CPU changes.
-      * 3. that version is increased whenever underlying CPU
-      *    changes.
+      * Note: The kernel and hypervisor must guarantee that cpu ID
+      * number maps 1:1 to per-CPU pvclock time info.
+      *
+      * Because the hypervisor is entirely unaware of guest userspace
+      * preemption, it cannot guarantee that per-CPU pvclock time
+      * info is updated if the underlying CPU changes or that that
+      * version is increased whenever underlying CPU changes.
+      *
+      * On KVM, we are guaranteed that pvti updates for any vCPU are
+      * atomic as seen by *all* vCPUs.  This is an even stronger
+      * guarantee than we get with a normal seqlock.
       *
+      * On Xen, we don't appear to have that guarantee, but Xen still
+      * supplies a valid seqlock using the version field.

Quoted 8 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 107

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+
+      * We only do pvclock vdso timing at all if
+      * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+      * mean that all vCPUs have matching pvti and that the TSC is
+      * synced, so we can just look at vCPU 0's pvti.
       */

Can Xen guarantee that ?

I think so, vacuously. Xen doesn't seem to set PVCLOCK_TSC_STABLE_BIT at all. I have no idea going forward, though.

Xen people?

Quoted 23 lines

Quoted 23 lines

arch/x86/vdso/vclock_gettime.c +0 -22

-     do {
-             cpu = __getcpu() & VGETCPU_CPU_MASK;
-             /* TODO: We can put vcpu id into higher bits of pvti.version.
-              * This will save a couple of cycles by getting rid of
-              * __getcpu() calls (Gleb).
-              */
-
-             pvti = get_pvti(cpu);
-
-             version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-             /*
-              * Test we're still on the cpu as well as the version.
-              * We could have been migrated just after the first
-              * vgetcpu but before fetching the version, so we
-              * wouldn't notice a version change.
-              */
-             cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-     } while (unlikely(cpu != cpu1 ||
-                       (pvti->pvti.version & 1) ||
-                       pvti->pvti.version != version));
-

Quoted 9 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 112

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +4 -1

-     if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+     if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
              *mode = VCLOCK_NONE;
+             return 0;
+     }

This check must be performed after reading a stable pvti.

We can even read it in the middle, guarded by the version checks. I'll do that for v2.

Quoted 32 lines

Quoted 11 lines

arch/x86/vdso/vclock_gettime.c +11 -0

+
+     do {
+             version = pvti->version;
+
+             /* This is also a read barrier, so we'll read version first. */
+             rdtsc_barrier();
+             tsc = __native_read_tsc();
+
+             pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+             pvti_tsc_shift = pvti->tsc_shift;
+             pvti_system_time = pvti->system_time;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 133

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +10 -0

+             pvti_tsc = pvti->tsc_timestamp;
+
+             /* Make sure that the version double-check is last. */
+             smp_rmb();
+     } while (unlikely((version & 1) || version != pvti->version));
+
+     delta = tsc - pvti_tsc;
+     ret = pvti_system_time +
+             pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                 pvti_tsc_shift);

The following is possible:

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 7 lines

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable?

Yes. It will VM-enter after pvti is updated.

Quoted 3 lines

Otherwise the vdso could could just as
easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

Right.

Quoted 3 lines

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

The update is performed as follows:

- Stop guest instruction execution on every vCPU, parking them in the host.
- Request KVMCLOCK update for every vCPU.
- Resume guest instruction execution.

The KVMCLOCK update (==pvti update) is guaranteed to be performed before guest instructions are executed again.

But there is no guarantee that vCPU-N has updated its pvti when vCPU-M resumes guest instruction execution.

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

Quoted 9 lines

Quoted 2 lines

So the cost this patch removes is mainly from __getcpu (==RDTSCP?) ?

It removes a whole bunch of code, an extra barrier, and two __getcpus.

Quoted 1 line

Perhaps you can use Gleb's idea to stick vcpu id into version field ?

I don't understand how that's useful at all. If you're reading pvti, you clearly know the vcpu id.

Replace the return value of __getcpus by value read from pvti.version.

Quoted 8 lines

Quoted 8 lines

Quoted 2 lines

Quoted 2 lines

But there is no guarantee that vCPU-N has updated its pvti when vCPU-M resumes guest instruction execution.

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

--Andy

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

Quoted 86 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

Quoted 1 line

with possible smp_wmb() in there to keep the compiler from messing around?

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

What is the point with the new flags bit though?

Quoted 4 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

If the version "seqlock" works properly across vCPUs, why do you need STABLE_BIT "properly atomic" ?

Please define what you mean by "properly atomic".

Quoted 1 line

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Quoted 9 lines

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

If the version "seqlock" works properly across vCPUs, why do you need STABLE_BIT "properly atomic" ?

Please define what you mean by "properly atomic".

I'd like to be able to rely using vCPU 0's pvti even from other vCPUs in the vdso if the stable bit is set. That means that the host should avoid doing things like migrating the guest, clearing the stable bit for vCPU 1, resuming vCPU 1, and waiting long enough to clear the stable bit for vCPU 0 that vCPU 1's vdso code could see invalid data and return a bad timestamp.

Maybe this scenario is impossible, but getting rid of any getcpu-like operation in the vdso has really nice benefits.

It's faster and it
lets us guarantee that the vdso's pvti data fits in a single page. The latter means that we can easily make it work like the hpet mapping, which gets us 32-bit support and will *finally* let us turn off user access to the fixmap if vsyscall=none.

(We can, of course, still do this if the pvti data needs to be an array, but it's messier.)

--Andy

Quoted 4 lines · Andy Lutomirski

Quoted 1 line

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Don't think so. Just fix the host bug.

Quoted 17 lines

Quoted 9 lines

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

If the version "seqlock" works properly across vCPUs, why do you need STABLE_BIT "properly atomic" ?

Please define what you mean by "properly atomic".

I'd like to be able to rely using vCPU 0's pvti even from other vCPUs in the vdso if the stable bit is set. That means that the host should avoid doing things like migrating the guest, clearing the stable bit for vCPU 1, resuming vCPU 1, and waiting long enough to clear the stable bit for vCPU 0 that vCPU 1's vdso code could see invalid data and return a bad timestamp.

Quoted 2 lines

Maybe this scenario is impossible, but getting rid of any getcpu-like operation in the vdso has really nice benefits.

You can park every vCPU in host while updating vCPU-0's timestamp.

See kvm_gen_update_masterclock:

Quoted 10 lines

It's faster and it
lets us guarantee that the vdso's pvti data fits in a single page. The latter means that we can easily make it work like the hpet mapping, which gets us 32-bit support and will *finally* let us turn off user access to the fixmap if vsyscall=none.

(We can, of course, still do this if the pvti data needs to be an array, but it's messier.)

--Andy

Quoted 4 lines · Andy Lutomirski

Quoted 1 line

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Don't think so. Just fix the host bug.

Quoted 17 lines

Quoted 9 lines

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

If the version "seqlock" works properly across vCPUs, why do you need STABLE_BIT "properly atomic" ?

Please define what you mean by "properly atomic".

I'd like to be able to rely using vCPU 0's pvti even from other vCPUs in the vdso if the stable bit is set. That means that the host should avoid doing things like migrating the guest, clearing the stable bit for vCPU 1, resuming vCPU 1, and waiting long enough to clear the stable bit for vCPU 0 that vCPU 1's vdso code could see invalid data and return a bad timestamp.

Quoted 2 lines

Maybe this scenario is impossible, but getting rid of any getcpu-like operation in the vdso has really nice benefits.

You can park every vCPU in host while updating vCPU-0's timestamp.

See kvm_gen_update_masterclock:

Quoted 10 lines

It's faster and it
lets us guarantee that the vdso's pvti data fits in a single page. The latter means that we can easily make it work like the hpet mapping, which gets us 32-bit support and will *finally* let us turn off user access to the fixmap if vsyscall=none.

(We can, of course, still do this if the pvti data needs to be an array, but it's messier.)

--Andy

Quoted 1 line

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Quoted 9 lines

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

If the version "seqlock" works properly across vCPUs, why do you need STABLE_BIT "properly atomic" ?

Please define what you mean by "properly atomic".

I'd like to be able to rely using vCPU 0's pvti even from other vCPUs in the vdso if the stable bit is set. That means that the host should avoid doing things like migrating the guest, clearing the stable bit for vCPU 1, resuming vCPU 1, and waiting long enough to clear the stable bit for vCPU 0 that vCPU 1's vdso code could see invalid data and return a bad timestamp.

Maybe this scenario is impossible, but getting rid of any getcpu-like operation in the vdso has really nice benefits.

It's faster and it
lets us guarantee that the vdso's pvti data fits in a single page. The latter means that we can easily make it work like the hpet mapping, which gets us 32-bit support and will *finally* let us turn off user access to the fixmap if vsyscall=none.

(We can, of course, still do this if the pvti data needs to be an array, but it's messier.)

--Andy

Quoted 89 lines · Marcelo Tosatti

Quoted 87 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Quoted 4 lines

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Quoted 93 lines · Andy Lutomirski

Quoted 92 lines · Marcelo Tosatti

Quoted 80 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Quoted 7 lines

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

Quoted 4 lines

Quoted 1 line

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Andy,

Are you going to submit the fix or should i?

Quoted 99 lines · Marcelo Tosatti

Quoted 97 lines · Andy Lutomirski

Quoted 87 lines · Marcelo Tosatti

Quoted 86 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

Quoted 6 lines

Quoted 1 line

with possible smp_wmb() in there to keep the compiler from messing around?

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Quoted 4 lines

Andy,

Are you going to submit the fix or should i?

I'd prefer if you did it. I'm not familiar enough with the KVM memory management stuff to do it confidently. Feel free to mooch from my patch if it's helpful.

--Andy

--
Andy Lutomirski
AMA Capital Management, LLC

Quoted 99 lines · Marcelo Tosatti

Quoted 97 lines · Andy Lutomirski

Quoted 87 lines · Marcelo Tosatti

Quoted 86 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

Quoted 6 lines

Quoted 1 line

with possible smp_wmb() in there to keep the compiler from messing around?

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Quoted 4 lines

Andy,

Are you going to submit the fix or should i?

I'd prefer if you did it. I'm not familiar enough with the KVM memory management stuff to do it confidently. Feel free to mooch from my patch if it's helpful.

--Andy

--
Andy Lutomirski
AMA Capital Management, LLC

Quoted 93 lines · Andy Lutomirski

Quoted 92 lines · Marcelo Tosatti

Quoted 80 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Quoted 7 lines

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

Quoted 4 lines

Quoted 1 line

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Andy,

Are you going to submit the fix or should i?

Quoted 89 lines · Marcelo Tosatti

Quoted 87 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Quoted 4 lines

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

What is the point with the new flags bit though?

To try to work around the problem on old hosts. I'm not at all convinced that this is worthwhile or that it helps, though.

Quoted 86 lines · Andy Lutomirski

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

Quoted 1 line

with possible smp_wmb() in there to keep the compiler from messing around?

Correct. Could just as well follow the protocol and use odd/even, which is what your patch does.

What is the point with the new flags bit though?

Quoted 4 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

If the version "seqlock" works properly across vCPUs, why do you need STABLE_BIT "properly atomic" ?

Please define what you mean by "properly atomic".

Quoted 70 lines · Marcelo Tosatti

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 8 lines

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

Don't you stil need:

version++;
write the rest;
version++;

with possible smp_wmb() in there to keep the compiler from messing around?

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

Quoted 69 lines · Andy Lutomirski

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

Quoted 1 line

--Andy

I suppose that separating the version write from the rest of the pvclock structure is sufficient, as that would guarantee the writes are not reordered even with fast string REP MOVS.

Thanks for catching this Andy!

Quoted 21 lines · Paolo Bonzini

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

Quoted 9 lines

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

Off-topic note: rdtscp doesn't need a barrier at all. AIUI AMD specified it that way and both AMD and Intel implement it correctly. (rdtsc, on the other hand, definitely needs the barrier beforehand.)

Quoted 6 lines

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Still no good. We can migrate a bunch of times so we see the same CPU all three times and *still* don't get a consistent read, unless we play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

I don't suppose that you and Marcelo could agree on what the actual semantics that KVM provides are and could write it down in a way that people who haven't spent a long time staring at the request code understand? And maybe you could even fix the implementation while you're at it if the implementation is, indeed, broken. I have ugly patches to fix it here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=3b718a050cba52563d831febc2e1ca184c02bac0

but I'm not thrilled with them.

--Andy

Still no good. We can migrate a bunch of times so we see the same CPU all three times

Quoted 5 lines

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Quoted 1 line

        cpu = get_cpu();

and *still* don't get a consistent read, unless we
play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Quoted 2 lines · Andy Lutomirski

Still no good. We can migrate a bunch of times so we see the same CPU all three times

There are no three times. The CPU you see here:

Quoted 5 lines

Quoted 5 lines

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

is the same you read here:

Quoted 1 line

Quoted 1 line

        cpu = get_cpu();

The algorithm is:

1) get a consistent (cpu, version, tsc)

1.a) get cpu

   1.b) get pvti[cpu]->version, ignoring low bit

   1.c) get (tsc, cpu)

1.d) if cpu from 1.a and 1.c do not match, loop 1.e) if pvti[cpu] was being updated, we'll loop later

2) compute nanoseconds from pvti[cpu] and tsc

3) if pvti[cpu] changed under our feet during (2), i.e. version doesn't match, retry.

As long as the CPU is consistent between get_cpu() and rdtscp(), there is no problem with migration, because pvti is always accessed for that one CPU. If there were any problem, it would be caught by the version check. Writing it down with two nested do...whiles makes it clearer IMHO.

Quoted 9 lines

and *still* don't get a consistent read, unless we
play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Quoted 5 lines

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Where am I saying that?

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

That would be nice if you want to make the pvclock area fit in a single page. However, it would have to be a separate flag bit, or a separate CPUID feature.

Paolo

Quoted 7 lines

Quoted 7 lines

Quoted 5 lines

Quoted 5 lines

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Where am I saying that?

I thought the conclusion from what you and Marcelo pointed out about the code was that, once the first vCPU updated its pvti, it could start running guest code while the other vCPUs are still updating pvti, so its guest code can observe the other vCPUs mid-update.

Quoted 7 lines

Quoted 7 lines

Quoted 5 lines

Quoted 5 lines

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Where am I saying that?

I thought the conclusion from what you and Marcelo pointed out about the code was that, once the first vCPU updated its pvti, it could start running guest code while the other vCPUs are still updating pvti, so its guest code can observe the other vCPUs mid-update.

Quoted 14 lines · Paolo Bonzini

Quoted 2 lines · Andy Lutomirski

Still no good. We can migrate a bunch of times so we see the same CPU all three times

There are no three times. The CPU you see here:

Quoted 5 lines

Quoted 5 lines

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Quoted 5 lines

is the same you read here:

Quoted 1 line

Quoted 1 line

        cpu = get_cpu();

The algorithm is:

I still don't see why this is safe, and I think that the issue is that you left out part of the loop.

Quoted 4 lines

1) get a consistent (cpu, version, tsc)

1.a) get cpu

Suppose we observe cpu 0.

Quoted 1 line

   1.b) get pvti[cpu]->version, ignoring low bit

Missing step, presumably here: read pvti[cpu]->tsc_timestamp, scale, etc. This could all execute on vCPU 1. We could read values that are inconsistent with each other.

Quoted 1 line

   1.c) get (tsc, cpu)

Now we could end up back on vCPU 0.

Quoted 5 lines

1.d) if cpu from 1.a and 1.c do not match, loop 1.e) if pvti[cpu] was being updated, we'll loop later

2) compute nanoseconds from pvti[cpu] and tsc

Quoted 7 lines

3) if pvti[cpu] changed under our feet during (2), i.e. version doesn't match, retry.

As long as the CPU is consistent between get_cpu() and rdtscp(), there is no problem with migration, because pvti is always accessed for that one CPU. If there were any problem, it would be caught by the version check. Writing it down with two nested do...whiles makes it clearer IMHO.

Why exactly would it be caught by the version check?

My ugly patch tries to make the argument that, at any point at which we observe ourselves to be on a given vCPU, that vCPU won't be updating pvti. That means that, if version doesn't change between two consecutive observations that we're on that vCPU, then we're okay. This IMO sucks. It's fragile, it's hard to make a coherent argument about correctness, and it requires at least two getcpu-like operations to read the time. Those operations are *slow*. One is much better than two, and zero is much better than one.

Quoted 9 lines

Quoted 9 lines

and *still* don't get a consistent read, unless we
play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Quoted 7 lines

Quoted 5 lines

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Where am I saying that?

I thought the conclusion from what you and Marcelo pointed out about the code was that, once the first vCPU updated its pvti, it could start running guest code while the other vCPUs are still updating pvti, so its guest code can observe the other vCPUs mid-update.

Quoted 4 lines

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

Quoted 3 lines

That would be nice if you want to make the pvclock area fit in a single page. However, it would have to be a separate flag bit, or a separate CPUID feature.

It would be nice to have. Although I think that fixing the host to increment version pre-update and post-update may actually be good enough. Is there any case in which it would fail in practice if we made that fix and always looked at pvti 0?

--Andy

Quoted 2 lines

Paolo

Signature · 2 lines

Andy Lutomirski
AMA Capital Management, LLC

Quoted 14 lines · Paolo Bonzini

Quoted 2 lines · Andy Lutomirski

Still no good. We can migrate a bunch of times so we see the same CPU all three times

There are no three times. The CPU you see here:

Quoted 5 lines

Quoted 5 lines

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Quoted 5 lines

is the same you read here:

Quoted 1 line

Quoted 1 line

        cpu = get_cpu();

The algorithm is:

I still don't see why this is safe, and I think that the issue is that you left out part of the loop.

Quoted 4 lines

1) get a consistent (cpu, version, tsc)

1.a) get cpu

Suppose we observe cpu 0.

Quoted 1 line

   1.b) get pvti[cpu]->version, ignoring low bit

Missing step, presumably here: read pvti[cpu]->tsc_timestamp, scale, etc. This could all execute on vCPU 1. We could read values that are inconsistent with each other.

Quoted 1 line

   1.c) get (tsc, cpu)

Now we could end up back on vCPU 0.

Quoted 5 lines

1.d) if cpu from 1.a and 1.c do not match, loop 1.e) if pvti[cpu] was being updated, we'll loop later

2) compute nanoseconds from pvti[cpu] and tsc

Quoted 7 lines

3) if pvti[cpu] changed under our feet during (2), i.e. version doesn't match, retry.

As long as the CPU is consistent between get_cpu() and rdtscp(), there is no problem with migration, because pvti is always accessed for that one CPU. If there were any problem, it would be caught by the version check. Writing it down with two nested do...whiles makes it clearer IMHO.

Why exactly would it be caught by the version check?

My ugly patch tries to make the argument that, at any point at which we observe ourselves to be on a given vCPU, that vCPU won't be updating pvti. That means that, if version doesn't change between two consecutive observations that we're on that vCPU, then we're okay. This IMO sucks. It's fragile, it's hard to make a coherent argument about correctness, and it requires at least two getcpu-like operations to read the time. Those operations are *slow*. One is much better than two, and zero is much better than one.

Quoted 9 lines

Quoted 9 lines

and *still* don't get a consistent read, unless we
play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Quoted 7 lines

Quoted 5 lines

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Where am I saying that?

I thought the conclusion from what you and Marcelo pointed out about the code was that, once the first vCPU updated its pvti, it could start running guest code while the other vCPUs are still updating pvti, so its guest code can observe the other vCPUs mid-update.

Quoted 4 lines

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

Quoted 3 lines

That would be nice if you want to make the pvclock area fit in a single page. However, it would have to be a separate flag bit, or a separate CPUID feature.

It would be nice to have. Although I think that fixing the host to increment version pre-update and post-update may actually be good enough. Is there any case in which it would fail in practice if we made that fix and always looked at pvti 0?

--Andy

Quoted 2 lines

Paolo

Signature · 2 lines

Andy Lutomirski
AMA Capital Management, LLC

Quoted 2 lines · Andy Lutomirski

Still no good. We can migrate a bunch of times so we see the same CPU all three times

There are no three times. The CPU you see here:

Quoted 5 lines

Quoted 5 lines

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

is the same you read here:

Quoted 1 line

Quoted 1 line

        cpu = get_cpu();

The algorithm is:

1) get a consistent (cpu, version, tsc)

1.a) get cpu

   1.b) get pvti[cpu]->version, ignoring low bit

   1.c) get (tsc, cpu)

1.d) if cpu from 1.a and 1.c do not match, loop 1.e) if pvti[cpu] was being updated, we'll loop later

2) compute nanoseconds from pvti[cpu] and tsc

3) if pvti[cpu] changed under our feet during (2), i.e. version doesn't match, retry.

As long as the CPU is consistent between get_cpu() and rdtscp(), there is no problem with migration, because pvti is always accessed for that one CPU. If there were any problem, it would be caught by the version check. Writing it down with two nested do...whiles makes it clearer IMHO.

Quoted 9 lines

and *still* don't get a consistent read, unless we
play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Quoted 5 lines

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Where am I saying that?

Quoted 3 lines

Also, if you do this, can you also make setting and clearing STABLE_BIT properly atomic across all vCPUs? Or at least do something like setting it last and clearing it first on vPCU 0?

That would be nice if you want to make the pvclock area fit in a single page. However, it would have to be a separate flag bit, or a separate CPUID feature.

Paolo

Still no good. We can migrate a bunch of times so we see the same CPU all three times

Quoted 5 lines

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Quoted 1 line

        cpu = get_cpu();

and *still* don't get a consistent read, unless we
play nasty games with lots of version checks (I have a patch for that, but I don't like it very much). The patch is here:

https://git.kernel.org/cgit/linux/kernel/git/luto/linux.git/commit/?h=x86/vdso_paranoia&id=a69754dc5ff33f5187162b5338854ad23dd7be8d

but I don't like it.

Thus far, I've been told unambiguously that a guest can't observe pvti while it's being written, and I think you're now telling me that this isn't true and that a guest *can* observe pvti while it's being written while the low bit of the version field is not set. If so, this is rather strongly incompatible with the spec in the KVM docs.

Quoted 9 lines · Paolo Bonzini

Quoted 6 lines

Quoted 5 lines

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.

Yes.

But then the getcpu test would fail (1->0). Even if you have an ABA situation (1->0->1), it's okay because the pvti that is fetched is the one returned by the first getcpu.

... this case of partial update of pvti, which is caught by the version field, if of course different from the other (extremely unlikely) that Andy pointed out. That is when the getcpus are done on the same vCPU, but the rdtsc is another.

That one can be fixed by rdtscp, like

do {
    // get a consistent (pvti, v, tsc) tuple
    do {
        cpu = get_cpu();
        pvti = get_pvti(cpu);
        v = pvti->version & ~1;
        // also acts as rmb();
        rdtsc_barrier();
        tsc = rdtscp(&cpu1);

        // control dependency, no need for rdtsc_barrier?
    } while(cpu != cpu1);

    // ... compute nanoseconds from pvti and tsc ...
    rmb();
}   while(v != pvti->version);

Quoted 170 lines · Marcelo Tosatti

Quoted 140 lines · Andy Lutomirski

Quoted 57 lines · Marcelo Tosatti

Quoted 56 lines · Andy Lutomirski

The pvclock vdso code was too abstracted to understand easily and excessively paranoid. Simplify it for a huge speedup.

This opens the door for additional simplifications, as the vdso no longer accesses the pvti for any vcpu other than vcpu 0.

Before, vclock_gettime using kvm-clock took about 64ns on my machine. With this change, it takes 19ns, which is almost as fast as the pure TSC implementation.

Signed-off-by Andy Lutomirski <[email protected]>

---
 arch/x86/vdso/vclock_gettime.c | 82 ++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 35 deletions(-)

arch/x86/vdso/vclock_gettime.c +17 -12

index 9793322751e0..f2e0396d5629 100644
@@ -78,47 +78,59 @@ static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu)
 
 static notrace cycle_t vread_pvclock(int *mode)
 {
-     const struct pvclock_vsyscall_time_info *pvti;
+     const struct pvclock_vcpu_time_info *pvti = &get_pvti(0)->pvti;
      cycle_t ret;
-     u64 last;
-     u32 version;
-     u8 flags;
-     unsigned cpu, cpu1;
-
+     u64 tsc, pvti_tsc;
+     u64 last, delta, pvti_system_time;
+     u32 version, pvti_tsc_to_system_mul, pvti_tsc_shift;
 
      /*
-      * Note: hypervisor must guarantee that:
-      * 1. cpu ID number maps 1:1 to per-CPU pvclock time info.
-      * 2. that per-CPU pvclock time info is updated if the
-      *    underlying CPU changes.
-      * 3. that version is increased whenever underlying CPU
-      *    changes.
+      * Note: The kernel and hypervisor must guarantee that cpu ID
+      * number maps 1:1 to per-CPU pvclock time info.
+      *
+      * Because the hypervisor is entirely unaware of guest userspace
+      * preemption, it cannot guarantee that per-CPU pvclock time
+      * info is updated if the underlying CPU changes or that that
+      * version is increased whenever underlying CPU changes.
+      *
+      * On KVM, we are guaranteed that pvti updates for any vCPU are
+      * atomic as seen by *all* vCPUs.  This is an even stronger
+      * guarantee than we get with a normal seqlock.
       *
+      * On Xen, we don't appear to have that guarantee, but Xen still
+      * supplies a valid seqlock using the version field.

Quoted 8 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 107

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +5 -0

+
+      * We only do pvclock vdso timing at all if
+      * PVCLOCK_TSC_STABLE_BIT is set, and we interpret that bit to
+      * mean that all vCPUs have matching pvti and that the TSC is
+      * synced, so we can just look at vCPU 0's pvti.
       */

Can Xen guarantee that ?

I think so, vacuously. Xen doesn't seem to set PVCLOCK_TSC_STABLE_BIT at all. I have no idea going forward, though.

Xen people?

Quoted 23 lines

Quoted 23 lines

arch/x86/vdso/vclock_gettime.c +0 -22

-     do {
-             cpu = __getcpu() & VGETCPU_CPU_MASK;
-             /* TODO: We can put vcpu id into higher bits of pvti.version.
-              * This will save a couple of cycles by getting rid of
-              * __getcpu() calls (Gleb).
-              */
-
-             pvti = get_pvti(cpu);
-
-             version = __pvclock_read_cycles(&pvti->pvti, &ret, &flags);
-
-             /*
-              * Test we're still on the cpu as well as the version.
-              * We could have been migrated just after the first
-              * vgetcpu but before fetching the version, so we
-              * wouldn't notice a version change.
-              */
-             cpu1 = __getcpu() & VGETCPU_CPU_MASK;
-     } while (unlikely(cpu != cpu1 ||
-                       (pvti->pvti.version & 1) ||
-                       pvti->pvti.version != version));
-

Quoted 9 lines

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 112

Quoted 6 lines

arch/x86/vdso/vclock_gettime.c +4 -1

-     if (unlikely(!(flags & PVCLOCK_TSC_STABLE_BIT)))
+
+     if (unlikely(!(pvti->flags & PVCLOCK_TSC_STABLE_BIT))) {
              *mode = VCLOCK_NONE;
+             return 0;
+     }

This check must be performed after reading a stable pvti.

We can even read it in the middle, guarded by the version checks. I'll do that for v2.

Quoted 32 lines

Quoted 11 lines

arch/x86/vdso/vclock_gettime.c +11 -0

+
+     do {
+             version = pvti->version;
+
+             /* This is also a read barrier, so we'll read version first. */
+             rdtsc_barrier();
+             tsc = __native_read_tsc();
+
+             pvti_tsc_to_system_mul = pvti->tsc_to_system_mul;
+             pvti_tsc_shift = pvti->tsc_shift;
+             pvti_system_time = pvti->system_time;

arch/x86/vdso/vclock_gettime.c static notrace const struct pvclock_vsyscall_time_info *get_pvti(int cpu) · line 133

Quoted 10 lines

arch/x86/vdso/vclock_gettime.c +10 -0

+             pvti_tsc = pvti->tsc_timestamp;
+
+             /* Make sure that the version double-check is last. */
+             smp_rmb();
+     } while (unlikely((version & 1) || version != pvti->version));
+
+     delta = tsc - pvti_tsc;
+     ret = pvti_system_time +
+             pvclock_scale_delta(delta, pvti_tsc_to_system_mul,
+                                 pvti_tsc_shift);

The following is possible:

1) State: all pvtis marked as PVCLOCK_TSC_STABLE_BIT.
1) Update request for all vcpus, for a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.
2) vCPU-1 updates its pvti with new values.
3) vCPU-0 still has not updated its pvti with new values.
4) vCPU-1 VM-enters, uses vCPU-0 values, even though it has been notified of a TSC_STABLE_BIT -> ~TSC_STABLE_BIT transition.

Quoted 7 lines

Quoted 4 lines

The update is not actually atomic across all vCPUs, its atomic in the sense of not allowing visibility of distinct system_timestamp/tsc_timestamp values.

Hmm. In step 4, is there a guarantee that vCPU-0 won't VM-enter until it gets marked unstable?

Yes. It will VM-enter after pvti is updated.

Quoted 3 lines

Otherwise the vdso could could just as
easily be called from vCPU-1, migrated to vCPU-0, read the data complete with stale stable bit, and get migrated back to vCPU-1.

Right.

Quoted 3 lines

But I thought that KVM currently froze all vCPUs when updating pvti for any of them. How can this happen? I admit I don't really understand the update request code.

The update is performed as follows:

- Stop guest instruction execution on every vCPU, parking them in the host.
- Request KVMCLOCK update for every vCPU.
- Resume guest instruction execution.

The KVMCLOCK update (==pvti update) is guaranteed to be performed before guest instructions are executed again.

Quoted 2 lines

But there is no guarantee that vCPU-N has updated its pvti when vCPU-M resumes guest instruction execution.

Still confused. So we can freeze all vCPUs in the host, then update pvti 1, then resume vCPU 1, then update pvti 0? In that case, we have a problem, because vCPU 1 can observe pvti 0 mid-update, and KVM doesn't increment the version pre-update, and we can return completely bogus results.