optimize writer path in time_interpolator_get_counter()

When using a time interpolator that is susceptible to jitter there's
potentially contention over a cmpxchg used to prevent time from going backwards. This is unnecessary when the caller holds the xtime write seqlock as all readers will be blocked from returning until the write is complete. We can therefore allow writers to insert a new value and exit rather than fight with CPUs who only hold a reader lock.

diff -r cff8d3633e9c kernel/timer.c
@@ -1428,7 +1428,7 @@
 	}
 }
 
-static inline u64 time_interpolator_get_counter(void)
+static inline u64 time_interpolator_get_counter(int writelock)
 {
 	unsigned int src = time_interpolator->source;
 

@@ -1436,6 +1436,20 @@
 	{
 		u64 lcycle;
 		u64 now;
+
+		if (writelock) {
+			lcycle = time_interpolator->last_cycle;
+			now = time_interpolator_get_cycles(src);
+			if (lcycle && time_after(lcycle, now))
+				return lcycle;
+
+			/* When holding the xtime write lock, there's no need
+			 * to add the overhead of the cmpxchg.  Readers are
+			 * force to retry until the write lock is released.
+			 */
+			time_interpolator->last_cycle = now;
+			return now;
+		}
 
 		do {
 			lcycle = time_interpolator->last_cycle;

@@ -1455,7 +1469,7 @@
 void time_interpolator_reset(void)
 {
 	time_interpolator->offset = 0;
-	time_interpolator->last_counter = time_interpolator_get_counter();
+	time_interpolator->last_counter = time_interpolator_get_counter(1);
 }
 
 #define GET_TI_NSECS(count,i) (((((count) - i->last_counter) & (i)->mask) * (i)->nsec_per_cyc) >> (i)->shift)

@@ -1467,7 +1481,7 @@
 		return 0;
 
 	return time_interpolator->offset +
-		GET_TI_NSECS(time_interpolator_get_counter(), time_interpolator);
+		GET_TI_NSECS(time_interpolator_get_counter(0), time_interpolator);
 }
 
 #define INTERPOLATOR_ADJUST 65536

@@ -1490,7 +1504,7 @@
 	 * and the tuning logic insures that.
          */
 
-	counter = time_interpolator_get_counter();
+	counter = time_interpolator_get_counter(1);
 	offset = time_interpolator->offset + GET_TI_NSECS(counter, time_interpolator);
 
 	if (delta_nsec < 0 || (unsigned long) delta_nsec < offset)

Could we remove some code duplication?

--

When using a time interpolator that is susceptible to jitter there's
potentially contention over a cmpxchg used to prevent time from going backwards. This is unnecessary when the caller holds the xtime write seqlock as all readers will be blocked from returning until the write is complete. We can therefore allow writers to insert a new value and exit rather than fight with CPUs who only hold a reader lock.

Index: linux-2.6/kernel/timer.c
===================================================================
@@ -1428,7 +1428,7 @@
 	}
 }
 
-static inline u64 time_interpolator_get_counter(void)
+static inline u64 time_interpolator_get_counter(int writelock)
 {
 	unsigned int src = time_interpolator->source;
 

@@ -1442,6 +1442,15 @@
 			now = time_interpolator_get_cycles(src);
 			if (lcycle && time_after(lcycle, now))
 				return lcycle;
+
+			/* When holding the xtime write lock, there's no need
+			 * to add the overhead of the cmpxchg.  Readers are
+			 * force to retry until the write lock is released.
+			 */
+			if (writelock) {
+				time_interpolator->last_cycle = now;
+				return now;
+			}
 			/* Keep track of the last timer value returned. The use of cmpxchg here
 			 * will cause contention in an SMP environment.
 			 */

@@ -1455,7 +1464,7 @@
 void time_interpolator_reset(void)
 {
 	time_interpolator->offset = 0;
-	time_interpolator->last_counter = time_interpolator_get_counter();
+	time_interpolator->last_counter = time_interpolator_get_counter(1);
 }
 
 #define GET_TI_NSECS(count,i) (((((count) - i->last_counter) & (i)->mask) * (i)->nsec_per_cyc) >> (i)->shift)

@@ -1467,7 +1476,7 @@
 		return 0;
 
 	return time_interpolator->offset +
-		GET_TI_NSECS(time_interpolator_get_counter(), time_interpolator);
+		GET_TI_NSECS(time_interpolator_get_counter(0), time_interpolator);
 }
 
 #define INTERPOLATOR_ADJUST 65536

@@ -1490,7 +1499,7 @@
 	 * and the tuning logic insures that.
          */
 
-	counter = time_interpolator_get_counter();
+	counter = time_interpolator_get_counter(1);
 	offset = time_interpolator->offset + GET_TI_NSECS(counter, time_interpolator);
 
 	if (delta_nsec < 0 || (unsigned long) delta_nsec < offset)

Works for me. Thanks,

Alex

Alex Williamson                             HP Linux & Open Source Lab

+ /* When holding the xtime write lock, there's no need
+ * to add the overhead of the cmpxchg. Readers are
+ * force to retry until the write lock is released.
+ */
+ if (writelock) {
+ time_interpolator->last_cycle = now;
+ return now;
+ }

This is lots prettier that my first suggestion (no surprise, even _I_ didn't like my suggested patch :-)

In theory it looks like it should help a lot as it ought to prevent the worst case spinning when one cpu has the xtime write lock.

Sadly, running my test case (running 1-4 tasks, each bound to a cpu, each pounding on gettimeofday(2)) I'm still seeing significant time spent spinning in this loop. Things are better: worst case time was down to just over 2ms from 34ms ... which is a significant improvement ... but 2ms still sounds ugly.

I'm still seeing the asymmetric behavior where cpu3 sees the really high times, while cpu0,1,2 are seeing peaks of 170us, which is still not pretty.

So this is a very half-hearted ACK for the patch. It does improve things, but I still think that code that does:

	do {
		val = xxx;

		// execute some stuff here
	} while (cmpxchg(&xxx, val, newval) != val);

is badly flawed. If this were in some rare code path that was only likely to see collisions when more than three planets were aligned, then it might be OK, but this is a common path and it is easy for (malicious) users to force multiple cpus into running this code ... making it likely that the cmpxchg will fail repeatedly.

-Tony

P.S. My ugly patch does even less to fix this problem ... times are worse than this.

I think we should be happy about this. Sounds ok for the problematic hardware.

Is this an SMP system? Updates are performed by cpu0 and therefore the cacheline is mostly exclusively owned by that processor and then later forced to become shared by processors 1,2,3.

cmpxchg is the best that one can do in this case. If you would take a spinlock then we would even need more processing.

We can still switch on the nojitter by default if the ITC's are guaranteed to be properly synchronized which will make all this ugliness go away.

I'll settle for an order of magnitude improvement for a first pass :)

How does cpu3's ITC synchronization compare to the others? I suspect
there's some reasonable way that we could do a backoff w/i the do {} while() loop, but I'm not sure what it is. For a while, I was toying around with the idea of how to convert:

	if (lcycle && time_after(lcycle, now))
		return lcycle;

into:

	if (lcycle && time_after(lcycle + min_delta, now))
		return lcycle;

But I don't know how that min_delta would be determined. A "close enough" factor like this would still prevent jitter, but would introduce a minimum granularity increment of gettimeofday(). I think this might be a reasonable performance vs absolute accuracy trade-off. What happens to your worst case time if you (just for a test) hard code a min_delta of something around 20-50? There could be some kind of boot/run time tunable to set this min_delta if there's no good way to calculate it. It should be trivial to add something like this to the fsys path as well and shouldn't disrupt the nojitter path at all. Thanks,

Alex

Alex Williamson                             HP Linux & Open Source Lab

Think about a threaded process that gets time on multiple processors and then compares the times. This means that the time value obtained later on one thread may indicate a time earlier than that obtained on another thread. An essential requirement for time values is that they are monotonically increasing. You are changing that basic nature.

I assure you it is not going to be trivial. IA64 asm instructions bundling and cycle optimization will have to be changed.

Ok, I can see the scenario where that could produce jitter. However,
that implies than any exit through that path could produce jitter as it is. For instance:

CPU0 CPU1
read lcycle
read itc
read lcycle read itc
cmpxchg
oops, lcycle is stale

So the window already exists for this...

Alex

Alex Williamson                             HP Linux & Open Source Lab

Well what is the difference of this approach from booting with "nojitter"? The ITC offsets are fixed right?

Just check that the ITC difference is less than what you want to risk and switch on "nojitter" during bootup if less than the limit. Same effect without changes to the critical timer code patchs.

The main problem occurs as far as I know when execution continues on another processor during time measurement. In that case you may get an earlier time later because the ITC of the processor you migrated to is not there yet.... Similar issues may occur if time information is communicated between threads running on different processor.

You have an awful nest of rats here so if you do this then please at least do a printk that warns people of what is going on.