x86-64: Micro-optimize vclock_gettime

arch/x86/kernel/tsc.c +19 -9

@@ -767,18 +767,38 @@ static cycle_t read_tsc(struct clocksource *cs)
 static cycle_t __vsyscall_fn vread_tsc(void)
 {
 	cycle_t ret;
-
-	/*
-	 * Surround the RDTSC by barriers, to make sure it's not
-	 * speculated to outside the seqlock critical section and
-	 * does not cause time warps:
+	u64 zero, last;
+
+	/* rdtsc is unordered, and we want it to be ordered like
+	 * a load with respect to other CPUs (and we don't want
+	 * it to execute absurdly early wrt code on this CPU.)
+	 * rdtsc_barrier() is a barrier that provides this ordering
+	 * with respect to *earlier* loads.  (Which barrier to use
+	 * depends on the CPU.)
 	 */
 	rdtsc_barrier();
-	ret = (cycle_t)vget_cycles();
-	rdtsc_barrier();
 
-	return ret >= __vsyscall_gtod_data.clock.cycle_last ?
-		ret : __vsyscall_gtod_data.clock.cycle_last;
+	asm volatile ("rdtsc\n\t"
+		      "shl $0x20,%%rdx\n\t"
+		      "or %%rdx,%%rax\n\t"
+		      "shl $0x20,%%rdx"
+		      : "=a" (ret), "=d" (zero) : : "cc");
+
+	/* zero == 0, but as far as the processor is concerned, zero
+	 * depends on the output of rdtsc.  So we can use it as a
+	 * load barrier by loading something that depends on it.
+	 * x86-64 keeps all loads in order wrt each other, so this
+	 * ensures that rdtsc is ordered wrt all later loads.

arch/x86/kernel/tsc.c +2 -3

-	/* This doesn't multiply 'zero' by anything, which *should*
-	 * generate nicer code, except that gcc cleverly embeds the
-	 * dereference into the cmp and the cmovae.  Oh, well.
+	/* This doesn't multiply 'zero' by anything, which generates
+	 * very slightly nicer code than multiplying it by 8.
 	 */
 	last = *( (cycle_t *)
 		  ((char *)&__vsyscall_gtod_data.clock.cycle_last + zero) );

Quoted 9 lines · Andy Lutomirski

-     /* This doesn't multiply 'zero' by anything, which *should*
-      * generate nicer code, except that gcc cleverly embeds the
-      * dereference into the cmp and the cmovae.  Oh, well.
+     /* This doesn't multiply 'zero' by anything, which generates
+      * very slightly nicer code than multiplying it by 8.
       */
      last = *( (cycle_t *)
                ((char *)&__vsyscall_gtod_data.clock.cycle_last + zero) );

Quoted 9 lines

-     return ret >= last ? ret : last;
+     if (likely(ret >= last))
+             return ret;
+
+     /* GCC likes to generate cmov here, but this branch is extremely
+        predictable (it's just a funciton of time and the likely is
+        very likely) and there's a data dependence, so force GCC
+        to generate a branch instead. */
+     asm volatile ("");

barrier() would do the same, right?

Also, a nit, please use the customary (multi-line) comment style:

 /*
  * Comment .....
  * ...... goes here.
  */

specified in Documentation/CodingStyle.

Thanks,

       Ingo

Quoted 2 lines · Andy Lutomirski

+      /* This address must be kept in sync with arch/x86/vdso/vextern.h */

This is the worst idea ever. Breakage is lurking by making something:
Must be kept in sync ...

Quoted 1 line

+     .vsyscall_gtod_data ADDR(.vsyscall_0) + 3072 + 256:

And this magic constant is what ? Something which will blow up sooner than later.

NAK.

Thanks,

       tglx

Quoted 2 lines · Thomas Gleixner

NAK.

Consider this one withdrawn for now. I'll redo this patch later on and resubmit it on its own.

Any comments on the rest of the series? They're all independent changes, other than touching the same code.

vclock_gettime's do_monotonic helper can't ever generate a negative nsec value, so it doesn't need to check whether it's negative. This saves a single easily-predicted branch.

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

---
 arch/x86/vdso/vclock_gettime.c |   40 ++++++++++++++++++++++------------------
 1 files changed, 22 insertions(+), 18 deletions(-)

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

index ee55754..67d54bb 100644
@@ -56,22 +56,6 @@ notrace static noinline int do_realtime(struct timespec *ts)
 	return 0;
 }
 
-/* Copy of the version in kernel/time.c which we cannot directly access */
-notrace static void
-vset_normalized_timespec(struct timespec *ts, long sec, long nsec)
-{
-	while (nsec >= NSEC_PER_SEC) {
-		nsec -= NSEC_PER_SEC;
-		++sec;
-	}
-	while (nsec < 0) {
-		nsec += NSEC_PER_SEC;
-		--sec;
-	}
-	ts->tv_sec = sec;
-	ts->tv_nsec = nsec;
-}
-
 notrace static noinline int do_monotonic(struct timespec *ts)
 {
 	unsigned long seq, ns, secs;

@@ -82,7 +66,17 @@ notrace static noinline int do_monotonic(struct timespec *ts)
 		secs += gtod->wall_to_monotonic.tv_sec;
 		ns += gtod->wall_to_monotonic.tv_nsec;
 	} while (unlikely(read_seqretry(&gtod->lock, seq)));
-	vset_normalized_timespec(ts, secs, ns);
+
+	/* wall_time_nsec, vgetns(), and wall_to_monotonic.tv_nsec
+	 * are all guaranteed to be nonnegative.
+	 */
+	while (ns >= NSEC_PER_SEC) {
+		ns -= NSEC_PER_SEC;
+		++secs;
+	}
+	ts->tv_sec = secs;
+	ts->tv_nsec = ns;
+
 	return 0;
 }
 

@@ -107,7 +101,17 @@ notrace static noinline int do_monotonic_coarse(struct timespec *ts)
 		secs += gtod->wall_to_monotonic.tv_sec;
 		ns += gtod->wall_to_monotonic.tv_nsec;
 	} while (unlikely(read_seqretry(&gtod->lock, seq)));
-	vset_normalized_timespec(ts, secs, ns);
+
+	/* wall_time_nsec and wall_to_monotonic.tv_nsec are

Quoted 62 lines · Andy Lutomirski

vclock_gettime's do_monotonic helper can't ever generate a negative nsec value, so it doesn't need to check whether it's negative.  This saves a single easily-predicted branch.

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

---
 arch/x86/vdso/vclock_gettime.c |   40 ++++++++++++++++++++++------------------

 1 files changed, 22 insertions(+), 18 deletions(-)

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

index ee55754..67d54bb 100644
@@ -56,22 +56,6 @@ notrace static noinline int do_realtime(struct timespec *ts)
       return 0;
  }
 
-/* Copy of the version in kernel/time.c which we cannot directly access */
-notrace static void
-vset_normalized_timespec(struct timespec *ts, long sec, long nsec)
-{
-     while (nsec >= NSEC_PER_SEC) {
-             nsec -= NSEC_PER_SEC;
-             ++sec;
-     }
-     while (nsec < 0) {
-             nsec += NSEC_PER_SEC;
-             --sec;
-     }
-     ts->tv_sec = sec;
-     ts->tv_nsec = nsec;
-}
-
  notrace static noinline int do_monotonic(struct timespec *ts)
  {
       unsigned long seq, ns, secs;

@@ -82,7 +66,17 @@ notrace static noinline int do_monotonic(struct timespec *ts)
               secs += gtod->wall_to_monotonic.tv_sec;
               ns += gtod->wall_to_monotonic.tv_nsec;
       } while (unlikely(read_seqretry(&gtod->lock, seq)));
-     vset_normalized_timespec(ts, secs, ns);
+
+     /* wall_time_nsec, vgetns(), and wall_to_monotonic.tv_nsec
+      * are all guaranteed to be nonnegative.
+      */
+     while (ns >= NSEC_PER_SEC) {
+             ns -= NSEC_PER_SEC;
+             ++secs;
+     }
+     ts->tv_sec = secs;
+     ts->tv_nsec = ns;
+
       return 0;
  }
 

@@ -107,7 +101,17 @@ notrace static noinline int do_monotonic_coarse(struct timespec *ts)
               secs += gtod->wall_to_monotonic.tv_sec;
               ns += gtod->wall_to_monotonic.tv_nsec;
       } while (unlikely(read_seqretry(&gtod->lock, seq)));
-     vset_normalized_timespec(ts, secs, ns);
+
+     /* wall_time_nsec and wall_to_monotonic.tv_nsec are

arch/x86/vdso/vclock_gettime.c notrace static noinline int do_monotonic_coarse(struct timespec *ts) · line 115

Quoted 10 lines

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

+      * guaranteed to be between 0 and NSEC_PER_SEC.
+      */
+     if (ns >= NSEC_PER_SEC) {
+             ns -= NSEC_PER_SEC;
+             ++secs;
+     }
+     ts->tv_sec = secs;
+     ts->tv_nsec = ns;
+
       return 0;

Beyond the change you describe in the changelog, you also uninlined the helper function.

You can use __always_inline instead and still keep the code maintainable.

vread_tsc is short and hot, and it's userspace code so the usual reasons to keep frame pointers around don't apply.

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

---

It might be nicer to move vread_tsc into a separate file and change the options directly.

 arch/x86/kernel/tsc.c |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

arch/x86/kernel/tsc.c +2 -0

index a159fba..1aea4a6 100644
@@ -764,6 +764,8 @@ static cycle_t read_tsc(struct clocksource *cs)
 }
 
 #ifdef CONFIG_X86_64
+#pragma GCC push_options
+#pragma GCC optimize ("omit-frame-pointer")
 static cycle_t __vsyscall_fn vread_tsc(void)
 {
 	cycle_t ret;

This series speeds up vclock_gettime(CLOCK_MONOTONIC) on by almost 30% (tested on Sandy Bridge). They're ordered in roughly decreasing order of improvement.

These are meant for 2.6.40, but if anyone wants to take some of them for 2.6.39 I won't object.

The changes and timings (fastest of 20 trials of 100M iters on Sandy Bridge) are:

Unpatched:

CLOCK_MONOTONIC: 22.09ns
CLOCK_REALTIME_COARSE: 4.23ns
CLOCK_MONOTONIC_COARSE: 5.65ns

CLOCK_MONOTONIC: 15.66ns
CLOCK_REALTIME_COARSE: 3.44ns
CLOCK_MONOTONIC_COARSE: 4.23ns

This series speeds up vclock_gettime(CLOCK_MONOTONIC) on by almost 30% (tested on Sandy Bridge). They're ordered in roughly decreasing order of improvement.

These are meant for 2.6.40, but if anyone wants to take some of them for 2.6.39 I won't object.

Quoted 4 lines · Andy Lutomirski

This series speeds up vclock_gettime(CLOCK_MONOTONIC) on by almost 30% (tested on Sandy Bridge).  They're ordered in roughly decreasing order of improvement.

Quoted 2 lines

These are meant for 2.6.40, but if anyone wants to take some of them for 2.6.39 I won't object.

I read all the patchkit and it looks good to me.  I felt a bit uneasy about the barrier changes though, it may be worth running of the paranoid "check monotonicity on lots of cpus" test cases to double check on different CPUs.  The interesting cases are: P4-Prescott, Merom (C2Duo), AMD K8.

Thanks for doing these optimizations again. Before generic clock source these functions used to be somewhat faster, but they regressed significantly back then. It may be worth comparing the current asm code against these old code and see if there's still something obvious missing.

Possible more optimizations if you're still motivated:

- Move all the timer state/seqlock into one cache line and start with a prefetch.
I did a similar attempt recently for the in kernel timers. You won't see any difference in a micro benchmark loop, but you may in a workload that dirties lots of cache between timer calls.

- Replace the indirect call in vread() with a if ( timer == TSC) inline() else indirect_call
(manual devirtualization essentially)

- Replace the sysctl checks with code patching use the new static branch frameworks

I ran Ingo's time-warp-test w/ 6, 7, and 8 threads on Sandy Bridge and on a Xeon 5600 series chip. My C2D laptop thinks that its TSC halts in idle and my only AMD system has unsynchronized TSCs.

Quoted 3 lines

I did a similar attempt recently for the in kernel timers. You won't see any difference in a micro benchmark loop, but you may in a workload that dirties lots of cache between timer calls.

For CLOCK_REALTIME they're already in one cache line. I tried the prefetch and couldn't measure a speedup even after playing with

Agreed. In fact, I could do both in one fell swoop: have a flag for the mode and have one option be "just issue the syscall." Static branch stuff scares me because this stuff runs in userspace and, in theory, userspace might have COWed the page with this code in it.

Quoted 3 lines · Andrew Lutomirski

I ran Ingo's time-warp-test w/ 6, 7, and 8 threads on Sandy Bridge and on a Xeon 5600 series chip.  My C2D laptop thinks that its TSC halts in idle and my only AMD system has unsynchronized TSCs.

I think you should have coverage on more systems. The original problems that motivated the barriers were on older K8 AMD systems.

You can ask people on l-k to run such tests for you if you don't have the hardware.

Quoted 7 lines

Quoted 4 lines

I did a similar attempt recently for the in kernel timers. You won't see any difference in a micro benchmark loop, but you may in a workload that dirties lots of cache between timer calls.

For CLOCK_REALTIME they're already in one cache line.  I tried the prefetch and couldn't measure a speedup even after playing with

Did you run a cache pig between the calls? With a tight loop it's obviously useless.

Quoted 5 lines

Agreed.  In fact, I could do both in one fell swoop: have a flag for the mode and have one option be "just issue the syscall."  Static branch stuff scares me because this stuff runs in userspace and, in theory, userspace might have COWed the page with this code in it.

The vdso is never cowed.