time: Add locking to xtime access in get_seconds()

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

However, recently I came across an odd bug where time() access could occasionally be inconsistent, but only on power7 hardware. The

Quoted 5 lines · John Stultz

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

Quoted 2 lines

However, recently I came across an odd bug where time() access could occasionally be inconsistent, but only on power7 hardware. The

Shouldn't a single rmb() be enough to avoid that?

If not then I suspect there's a lot more code buggy on that CPU than just the time.

Quoted 7 lines · Andi Kleen

Quoted 5 lines · John Stultz

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

Quoted 7 lines

Quoted 2 lines

However, recently I came across an odd bug where time() access could occasionally be inconsistent, but only on power7 hardware. The

Shouldn't a single rmb() be enough to avoid that?

If not then I suspect there's a lot more code buggy on that CPU than just the time.

So interestingly, I've found that the issue was not as complex as I first assumed. While the rmb() is probably a good idea for get_seconds(), but it alone does not solve the issue I was seeing, making it clear my theory wasn't correct.

The problem was reported against the 2.6.32-stable kernel, and had not been seen in later kernels. I had assumed the change to logarithmic time accumulation basically reduced the window for for the issue to be seen, but it would likely still show up eventually.

When the rmb() alone did not solve this issue, I looked to see why the locking did resolve it, and then it was clear: The old update_xtime_cache() function doesn't set the xtime_cache values atomically.

Now, the xtime_cache writing is done under the xtime_lock, so the get_seconds() locking resolves the issue, but isn't appropriate since get_seconds() is called from machine check handlers.

So the fix here for the 2.6.32-stable tree is to just update xtime_cache in one go as done with the following patch.

I also added the rmb() for good measure, and the rmb() should probably also go upstream since theoretically there maybe a platform that could do out of order syscalls.

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

Signed-off-by John Stultz <[email protected]>

Index: linux-2.6.32.y/kernel/time/timekeeping.c
===================================================================

kernel/time/timekeeping.c +0 -0

 	return xtime_cache.tv_sec;
 }
 EXPORT_SYMBOL(get_seconds);

Quoted 50 lines · john stultz

Quoted 7 lines · Andi Kleen

Quoted 5 lines · John Stultz

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

Quoted 7 lines

Quoted 2 lines

However, recently I came across an odd bug where time() access could occasionally be inconsistent, but only on power7 hardware. The

Shouldn't a single rmb() be enough to avoid that?

If not then I suspect there's a lot more code buggy on that CPU than just the time.

So interestingly, I've found that the issue was not as complex as I first assumed. While the rmb() is probably a good idea for get_seconds(), but it alone does not solve the issue I was seeing, making it clear my theory wasn't correct.

The problem was reported against the 2.6.32-stable kernel, and had not been seen in later kernels. I had assumed the change to logarithmic time accumulation basically reduced the window for for the issue to be seen, but it would likely still show up eventually.

When the rmb() alone did not solve this issue, I looked to see why the locking did resolve it, and then it was clear: The old update_xtime_cache() function doesn't set the xtime_cache values atomically.

Now, the xtime_cache writing is done under the xtime_lock, so the get_seconds() locking resolves the issue, but isn't appropriate since get_seconds() is called from machine check handlers.

So the fix here for the 2.6.32-stable tree is to just update xtime_cache in one go as done with the following patch.

I also added the rmb() for good measure, and the rmb() should probably also go upstream since theoretically there maybe a platform that could do out of order syscalls.

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

Signed-off-by John Stultz <[email protected]>

kernel/time/timekeeping.c int __read_mostly timekeeping_suspended; · line 171

Quoted 11 lines

Index: linux-2.6.32.y/kernel/time/timekeeping.c
===================================================================

kernel/time/timekeeping.c +1 -2

@@ -168,8 +168,10 @@ int __read_mostly timekeeping_suspended;
 static struct timespec xtime_cache __attribute__ ((aligned (16)));
 void update_xtime_cache(u64 nsec)
 {
-	xtime_cache = xtime;
-	timespec_add_ns(&xtime_cache, nsec);
+	/* use temporary timespec so xtime_cache is updated atomically */

Atomically is not possible on 32bit platform, so this comment is misleading.

What about a comment saying :

	/*
	 * use temporary variable so get_seconds() cannot catch
	 * intermediate value (one second backward)
	 */

Quoted 5 lines

kernel/time/timekeeping.c +3 -0

+	struct timespec ts = xtime;
+	timespec_add_ns(&ts, nsec);
+	xtime_cache = ts;
 }
 

kernel/time/timekeeping.c EXPORT_SYMBOL_GPL(monotonic_to_bootbased · line 864

Quoted 6 lines

kernel/time/timekeeping.c +1 -0

 /* must hold xtime_lock */

@@ -859,6 +861,7 @@ EXPORT_SYMBOL_GPL(monotonic_to_bootbased
 
 unsigned long get_seconds(void)
 {
+	rmb();

Please dont, this makes no sense, and with no comment anyway.

Would a comment to the effect of "ensure processors don't re-order calls to get_seconds" help, or is it still too opaque (or even still nonsense?).

Quoted 51 lines · Eric Dumazet

Quoted 50 lines · john stultz

Quoted 7 lines · Andi Kleen

Quoted 5 lines · John Stultz

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

Quoted 7 lines

Quoted 2 lines

However, recently I came across an odd bug where time() access could occasionally be inconsistent, but only on power7 hardware. The

Shouldn't a single rmb() be enough to avoid that?

If not then I suspect there's a lot more code buggy on that CPU than just the time.

So interestingly, I've found that the issue was not as complex as I first assumed. While the rmb() is probably a good idea for get_seconds(), but it alone does not solve the issue I was seeing, making it clear my theory wasn't correct.

The problem was reported against the 2.6.32-stable kernel, and had not been seen in later kernels. I had assumed the change to logarithmic time accumulation basically reduced the window for for the issue to be seen, but it would likely still show up eventually.

When the rmb() alone did not solve this issue, I looked to see why the locking did resolve it, and then it was clear: The old update_xtime_cache() function doesn't set the xtime_cache values atomically.

Now, the xtime_cache writing is done under the xtime_lock, so the get_seconds() locking resolves the issue, but isn't appropriate since get_seconds() is called from machine check handlers.

So the fix here for the 2.6.32-stable tree is to just update xtime_cache in one go as done with the following patch.

I also added the rmb() for good measure, and the rmb() should probably also go upstream since theoretically there maybe a platform that could do out of order syscalls.

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

Signed-off-by John Stultz <[email protected]>

Quoted 14 lines

kernel/time/timekeeping.c int __read_mostly timekeeping_suspended; · line 171

Quoted 11 lines

Index: linux-2.6.32.y/kernel/time/timekeeping.c
===================================================================

kernel/time/timekeeping.c +1 -2

@@ -168,8 +168,10 @@ int __read_mostly timekeeping_suspended;
 static struct timespec xtime_cache __attribute__ ((aligned (16)));
 void update_xtime_cache(u64 nsec)
 {
-	xtime_cache = xtime;
-	timespec_add_ns(&xtime_cache, nsec);
+	/* use temporary timespec so xtime_cache is updated atomically */

Atomically is not possible on 32bit platform, so this comment is misleading.

Well, 32bit/64bit, the time_t .tv_sec portion is a long, so it should be written atomically.

Quoted 5 lines

What about a comment saying :

	/*
	 * use temporary variable so get_seconds() cannot catch
	 * intermediate value (one second backward)
	 */

Fair enough. Such a comment is an improvement.

Quoted 5 lines

Quoted 5 lines

kernel/time/timekeeping.c +3 -0

+	struct timespec ts = xtime;
+	timespec_add_ns(&ts, nsec);
+	xtime_cache = ts;
 }
 

Quoted 8 lines

kernel/time/timekeeping.c EXPORT_SYMBOL_GPL(monotonic_to_bootbased · line 864

Quoted 6 lines

kernel/time/timekeeping.c +1 -0

 /* must hold xtime_lock */

@@ -859,6 +861,7 @@ EXPORT_SYMBOL_GPL(monotonic_to_bootbased
 
 unsigned long get_seconds(void)
 {
+	rmb();

Please dont, this makes no sense, and with no comment anyway.

Would a comment to the effect of "ensure processors don't re-order calls to get_seconds" help, or is it still too opaque (or even still nonsense?).

Quoted 92 lines · john stultz

Quoted 51 lines · Eric Dumazet

Quoted 50 lines · john stultz

Quoted 7 lines · Andi Kleen

Quoted 5 lines · John Stultz

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

Quoted 7 lines

Quoted 2 lines

However, recently I came across an odd bug where time() access could occasionally be inconsistent, but only on power7 hardware. The

Shouldn't a single rmb() be enough to avoid that?

If not then I suspect there's a lot more code buggy on that CPU than just the time.

So interestingly, I've found that the issue was not as complex as I first assumed. While the rmb() is probably a good idea for get_seconds(), but it alone does not solve the issue I was seeing, making it clear my theory wasn't correct.

The problem was reported against the 2.6.32-stable kernel, and had not been seen in later kernels. I had assumed the change to logarithmic time accumulation basically reduced the window for for the issue to be seen, but it would likely still show up eventually.

When the rmb() alone did not solve this issue, I looked to see why the locking did resolve it, and then it was clear: The old update_xtime_cache() function doesn't set the xtime_cache values atomically.

Now, the xtime_cache writing is done under the xtime_lock, so the get_seconds() locking resolves the issue, but isn't appropriate since get_seconds() is called from machine check handlers.

So the fix here for the 2.6.32-stable tree is to just update xtime_cache in one go as done with the following patch.

I also added the rmb() for good measure, and the rmb() should probably also go upstream since theoretically there maybe a platform that could do out of order syscalls.

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

Signed-off-by John Stultz <[email protected]>

Quoted 14 lines

kernel/time/timekeeping.c int __read_mostly timekeeping_suspended; · line 171

Quoted 11 lines

Index: linux-2.6.32.y/kernel/time/timekeeping.c
===================================================================

kernel/time/timekeeping.c +1 -2

@@ -168,8 +168,10 @@ int __read_mostly timekeeping_suspended;
 static struct timespec xtime_cache __attribute__ ((aligned (16)));
 void update_xtime_cache(u64 nsec)
 {
-	xtime_cache = xtime;
-	timespec_add_ns(&xtime_cache, nsec);
+	/* use temporary timespec so xtime_cache is updated atomically */

Atomically is not possible on 32bit platform, so this comment is misleading.

Well, 32bit/64bit, the time_t .tv_sec portion is a long, so it should be written atomically.

Quoted 5 lines

What about a comment saying :

	/*
	 * use temporary variable so get_seconds() cannot catch
	 * intermediate value (one second backward)
	 */

Fair enough. Such a comment is an improvement.

Quoted 5 lines

Quoted 5 lines

kernel/time/timekeeping.c +3 -0

+	struct timespec ts = xtime;
+	timespec_add_ns(&ts, nsec);
+	xtime_cache = ts;
 }
 

Quoted 8 lines

kernel/time/timekeeping.c EXPORT_SYMBOL_GPL(monotonic_to_bootbased · line 864

Quoted 6 lines

kernel/time/timekeeping.c +1 -0

 /* must hold xtime_lock */

@@ -859,6 +861,7 @@ EXPORT_SYMBOL_GPL(monotonic_to_bootbased
 
 unsigned long get_seconds(void)
 {
+	rmb();

Please dont, this makes no sense, and with no comment anyway.

Quoted 3 lines

Would a comment to the effect of "ensure processors don't re-order calls to get_seconds" help, or is it still too opaque (or even still nonsense?).

A CPU that reordered syscalls reading from or writing to a given memory location is broken. At least if the CPU does such reordering in a way that lets the software detect it. There is quite a bit of code out there that assumes cache coherence, so I sure hope that CPUs don't require the above memory barrier...

I feel xtime_lock seqlock is abused these days.

seqlock abstraction is somewhat lazy/dangerous because write_sequnlock() does both the seqcount increment and spinlock release.

I am concerned by fact that readers might wait for long times, because writers hold the whole seqlock, while sometime they only want to guard other writers to come in.

Maybe it's time to separate the things (the seqcount and the spinlock) so that writer can manipulate data in different sections :
- Sections while holding spinlock, allowing "readers" to run
- Very small sections enclosed in a pair of seqcount increments, to synchronize with readers.

Quoted 9 lines · Eric Dumazet

I feel xtime_lock seqlock is abused these days.

seqlock abstraction is somewhat lazy/dangerous because write_sequnlock() does both the seqcount increment and spinlock release.

I am concerned by fact that readers might wait for long times, because writers hold the whole seqlock, while sometime they only want to guard other writers to come in.

Quoted 5 lines

Maybe it's time to separate the things (the seqcount and the spinlock) so that writer can manipulate data in different sections :
- Sections while holding spinlock, allowing "readers" to run
- Very small sections enclosed in a pair of seqcount increments, to synchronize with readers.

Well, in the case of timekeeping that might be problematic. I'm not sure whether we can calculate the new values under the spinlock and then update the timekeeper under the seqlock because we might adjust the mult/shift pair which then can result in observabcle time going backwards problems. It might be worth a try, though. John ???

The only thing which really can move right away outside the xtime seqlock region is calc_global_load().

Quoted 17 lines · Thomas Gleixner

Quoted 9 lines · Eric Dumazet

I feel xtime_lock seqlock is abused these days.

seqlock abstraction is somewhat lazy/dangerous because write_sequnlock() does both the seqcount increment and spinlock release.

I am concerned by fact that readers might wait for long times, because writers hold the whole seqlock, while sometime they only want to guard other writers to come in.

Quoted 5 lines

Maybe it's time to separate the things (the seqcount and the spinlock) so that writer can manipulate data in different sections :
- Sections while holding spinlock, allowing "readers" to run
- Very small sections enclosed in a pair of seqcount increments, to synchronize with readers.

Quoted 9 lines

Well, in the case of timekeeping that might be problematic. I'm not sure whether we can calculate the new values under the spinlock and then update the timekeeper under the seqlock because we might adjust the mult/shift pair which then can result in observabcle time going backwards problems. It might be worth a try, though. John ???

The only thing which really can move right away outside the xtime seqlock region is calc_global_load().

That would be a start, but we also could have finer granularity in locks :

update_vsyscall() has its own protection and could be done outside of the seqcount inc pair used for ktime_get().

[ but my patch numbers were for a 32bit kernel, so vsyscall is not accounted for. ]

Another idea would be to prime cache lines to be dirtied in cpu cache before taking locks, and better pack variables to reduce number of cache lines.

Quoted 3 lines

Another idea would be to prime cache lines to be dirtied in cpu cache before taking locks, and better pack variables to reduce number of cache lines.

Most variables are packed already in struct timekeeper, which should be pretty cache hot anyway, so I don't know whether we gain much.

Quoted 6 lines

Quoted 3 lines

Another idea would be to prime cache lines to be dirtied in cpu cache before taking locks, and better pack variables to reduce number of cache lines.

Most variables are packed already in struct timekeeper, which should be pretty cache hot anyway, so I don't know whether we gain much.

There's actually some potential here. I got a moderate speedup in a database benchmark with this patch recently. The biggest win was in the timer interrupt.

All those variables are on separate cache lines.

(needs some cleanups, just for illustration)

-Andi

From: Andi Kleen <[email protected]>
Subject: [PATCH] do prefetches for timer state in timer interrupt

arch/x86/kernel/apic/apic.c +11 -0

index 76b96d7..2704267 100644
@@ -856,6 +856,17 @@ void __irq_entry smp_apic_timer_interrupt(struct pt_regs *regs)
 {
 	struct pt_regs *old_regs = set_irq_regs(regs);
 
+	extern struct timespec xtime;
+	extern struct timespec wall_to_monotonic;
+
+
+	/* Prefetch here to make the ktime_get later faster.
+ 	 * XXX move them all on the same cache line.
+ 	 */
+	prefetch(&xtime_lock);
+	prefetch(&xtime);
+	prefetch(&wall_to_monotonic);
+
 	/*
 	 * NOTE! We'd better ACK the irq immediately,
 	 * because timer handling can be slow.

kernel/time/timekeeping.c +0 -0

index d27c756..0002e9e 100644

Did you tried prefetchw() by any chance ?

Quoted 6 lines

Quoted 3 lines

Another idea would be to prime cache lines to be dirtied in cpu cache before taking locks, and better pack variables to reduce number of cache lines.

Most variables are packed already in struct timekeeper, which should be pretty cache hot anyway, so I don't know whether we gain much.

There's actually some potential here. I got a moderate speedup in a database benchmark with this patch recently. The biggest win

was in the timer interrupt.

All those variables are on separate cache lines.

(needs some cleanups, just for illustration)

Quoted 4 lines · Andi Kleen

Quoted 4 lines

Quoted 3 lines

Another idea would be to prime cache lines to be dirtied in cpu cache before taking locks, and better pack variables to reduce number of cache lines.

Quoted 5 lines

Quoted 2 lines

Most variables are packed already in struct timekeeper, which should be pretty cache hot anyway, so I don't know whether we gain much.

There's actually some potential here. I got a moderate speedup in a database benchmark with this patch recently. The biggest win

Numbers please.

Then precise measurements have to be done on the source of cache misses, the total cost of the timer interrupt, etc.

I.e. this should be analyzed and improved properly, not just sloppily slapping a few prefetches here and there, which wont really *solve* anything ...

Quoted 2 lines

Then precise measurements have to be done on the source of cache misses, the total cost of the timer interrupt, etc.

What we did was profiling the remote node cache misses using raw offcore events, and the xtime code was high up. I cannot share exact numbers for various reasons, but it was an improvement on a hard to improve workload.

Quoted 2 lines

There's actually some potential here. I got a moderate speedup in a database benchmark with this patch recently. The biggest win

Numbers please.

Well, then we should make sure that they are not.

And looking at a few kernel images the interesting variables timekeeper, xtime, wall_to_monotonic are in a consecutive area which is not really surprising. Further all images have xtime and wall_to_monotonic in the same cacheline, just xtime_lock is somewhere else.

Quoted 2 lines

(needs some cleanups, just for illustration)

And how's that cleanup going to look like? Making the timekeeping internal variables global again is not going to happen. And if you

want prefetching those variables in the timer interrupt, then you want to prefetch them in any random code path which ends up touching them.

That's the completely wrong aproach, really. If stuff takes too long, then we need to tackle it at the root of the problem and not solve it by sprinkling magic prefetches all over the place.

On Fri, May 06, 2011 at 12:18:27PM +0200, Thomas Gleixner wrote:

If that code path shows up in profiling. Only the timer interrupt did so far.

Quoted 3 lines

That's the completely wrong aproach, really. If stuff takes too long, then we need to tackle it at the root of the problem and not solve it by sprinkling magic prefetches all over the place.

If you have a better way to make it faster please share it.

Unless I am very mistaken, it cannot explain my original report of up to 24.000 instructions waiting in ktime_get()

BTW, how many consecutive prefetch() a cpu can 'store/execute' before throwing away hints ?

If you have a better way to make it faster please share it.

Quoted 1 line · Andi Kleen

If you have a better way to make it faster please share it.

Ideally we could use RCU :)

Quoted 4 lines · Eric Dumazet

Quoted 1 line · Andi Kleen

If you have a better way to make it faster please share it.

Quoted 1 line

Ideally we could use RCU :)

Hmm, I didn't think my case had a lot of loops in the seqlock -- just expensive cache misses -- but I should double check.

For the lots of loop case we probably need to understand first why you iterate that often.

Quoted 7 lines · Andi Kleen

Quoted 5 lines · Eric Dumazet

Quoted 1 line · Andi Kleen

If you have a better way to make it faster please share it.

Ideally we could use RCU :)

Quoted 5 lines

Hmm, I didn't think my case had a lot of loops in the seqlock -- just expensive cache misses -- but I should double check.

For the lots of loop case we probably need to understand first why you iterate that often.

Yep, I'll try to investigate on this

Quoted 11 lines · Eric Dumazet

Quoted 10 lines · Andi Kleen

Quoted 5 lines · Eric Dumazet

Quoted 1 line · Andi Kleen

If you have a better way to make it faster please share it.

Ideally we could use RCU :)

Hmm, I didn't think my case had a lot of loops in the seqlock -- just expensive cache misses -- but I should double check.

Quoted 5 lines

Quoted 2 lines

For the lots of loop case we probably need to understand first why you iterate that often.

Yep, I'll try to investigate on this

So apparently some calls to tick_do_update_jiffies64() are pretty expensive :

So would the easier solution be to just break out timekeeper locking from the xtime_lock?

So basically we would just add a timekeeper.lock seqlock and use it to protect only the timekeeping code? We can still keep xtime_lock around for the tick/jiffies protection (well, until tglx kills jiffies :), but gettimeofday and friends wouldn't be blocked for so long.

That should be pretty straight forward now that the timekeeper data is completely static to timkeeeping.c.

Quoted 11 lines · john stultz

So would the easier solution be to just break out timekeeper locking from the xtime_lock?

So basically we would just add a timekeeper.lock seqlock and use it to protect only the timekeeping code? We can still keep xtime_lock around for the tick/jiffies protection (well, until tglx kills jiffies :), but gettimeofday and friends wouldn't be blocked for so long.

That should be pretty straight forward now that the timekeeper data is completely static to timkeeeping.c.

Yes :)

I can see many cpus entering tick_do_update_jiffies64() and all are calling write_seqlock(&xtime_lock);

Only first one can perform the work, but all others are waiting on the spinlock, get it, change seqcount, and realize they have nothing to do...

Meanwhile, a reader must wait that all writers are finished, because of all seqcount changes storm.

Following patch helps. Of course we might find out why so many cpus (on my 8 cpus machine !) are calling tick_do_update_jiffies64() at the same time...

This is basically what I said in my first mail :

Separate logical sections to reduce windows where readers are blocked/spinning.

kernel/time/tick-sched.c +0 -0

index d5097c4..251b2fe 100644

Quoted 14 lines · Eric Dumazet

Quoted 11 lines · john stultz

So would the easier solution be to just break out timekeeper locking from the xtime_lock?

So basically we would just add a timekeeper.lock seqlock and use it to protect only the timekeeping code? We can still keep xtime_lock around for the tick/jiffies protection (well, until tglx kills jiffies :), but gettimeofday and friends wouldn't be blocked for so long.

That should be pretty straight forward now that the timekeeper data is completely static to timkeeeping.c.

Quoted 8 lines

Yes :)

I can see many cpus entering tick_do_update_jiffies64() and all are calling write_seqlock(&xtime_lock);

Only first one can perform the work, but all others are waiting on the spinlock, get it, change seqcount, and realize they have nothing to do...

Huh. So who is calling tick_do_update_jiffies64 in your case? I know the sched_tick_timer and tick_nohz_handler checks to make sure tick_do_timer_cpu == cpu to avoid exactly the thundering heard problem on the jiffies update.

There's other spots that call tick_do_update_jiffies64, but I thought those were more rare. So there may be something else wrong going on here.

Quoted 20 lines

Meanwhile, a reader must wait that all writers are finished, because of all seqcount changes storm.

Following patch helps. Of course we might find out why so many cpus (on my 8 cpus machine !) are calling tick_do_update_jiffies64() at the same time...

This is basically what I said in my first mail :

Separate logical sections to reduce windows where readers are blocked/spinning.

kernel/time/tick-sched.c +0 -0

index d5097c4..251b2fe 100644
@@ -56,7 +56,7 @@ static void tick_do_update_jiffies64(ktime_t now)
 		return;
 

kernel/time/tick-sched.c static void tick_do_update_jiffies64(ktime_t now) · line 59

Quoted 3 lines

kernel/time/tick-sched.c +1 -1

 	/* Reevalute with xtime_lock held */
-	write_seqlock(&xtime_lock);
+	spin_lock(&xtime_lock.lock);

Oof.. No, this is too ugly and really just abuses the seqlock structure.

If you really want to untangle what xtime_lock protects, you need to introduce a new lock (I suggest in the timekeeper structure) to protect the timekeeping data.

Then we can refine xtime_lock to also just protect the jiffies/tick management bits as well if needed.

Quoted 8 lines · john stultz

Quoted 6 lines · Eric Dumazet

I can see many cpus entering tick_do_update_jiffies64() and all are calling write_seqlock(&xtime_lock);

Only first one can perform the work, but all others are waiting on the spinlock, get it, change seqcount, and realize they have nothing to do...

Quoted 9 lines

Huh. So who is calling tick_do_update_jiffies64 in your case? I know the sched_tick_timer and tick_nohz_handler checks to make sure tick_do_timer_cpu == cpu to avoid exactly the thundering heard problem on the jiffies update.

There's other spots that call tick_do_update_jiffies64, but I thought those were more rare. So there may be something else wrong going on here.

That I can answer :

(I added do_timestamp1/do_timestamp2) after/before write_seqlock()/write_sequnlock()

         <idle>-0     [003]   920.355377: do_timestamp1 <-tick_do_update_jiffies64
          <idle>-0     [006]   920.355377: tick_do_update_jiffies64 <-tick_sched_timer
          <idle>-0     [003]   920.355378: do_timestamp2 <-tick_do_update_jiffies64
          <idle>-0     [000]   920.355657: tick_do_update_jiffies64 <-tick_check_idle
          <idle>-0     [000]   920.355660: tick_do_update_jiffies64 <-tick_nohz_restart_sched_tick

Quoted 6 lines

Review

Quoted 3 lines

(quoted diff) +1 -1

 	/* Reevalute with xtime_lock held */
-	write_seqlock(&xtime_lock);
+	spin_lock(&xtime_lock.lock);

Oof.. No, this is too ugly and really just abuses the seqlock structure.

That was a hack/POC, of course, but we can cleanup seqlock.h to provide clean thing. A seqlock_t should include a seqcount_t and a spinlock_t.

Quoted 6 lines

If you really want to untangle what xtime_lock protects, you need to introduce a new lock (I suggest in the timekeeper structure) to protect the timekeeping data.

Then we can refine xtime_lock to also just protect the jiffies/tick management bits as well if needed.

For the moment I am trying to understand the code. Its quite complex and uses a monolithic seqlock, defeating seqlock power.

Defeating seqlock power? My thoughts are that seqlocks are nice lightweight reader/writer locks that avoid writer starvation. You seem to be trying to redefine or extend them to be something else which is more subtle.

I agree, the code is complex! I'm just not sure adding more complicated/subtle locking mechanisms is a good solution. Instead I'd suggest simply splitting up the locks (by using new locks) to reduce the amount of data that is being protected by a single lock.

But again, maybe I'm misunderstanding you?

Quoted 5 lines

Defeating seqlock power? My thoughts are that seqlocks are nice lightweight reader/writer locks that avoid writer starvation. You seem to be trying to redefine or extend them to be something else which is more subtle.

All I am trying to explain is that a seqlock is a compound of two things : One spinlock to synchronize writers among themselves, one seqcount to synchronize readers with a writer.

But the API provides only a compound one. Writer uses the whole locking, while it would be nice to be able to separate the two steps. Note that because write_seqlock() and write_sequnlock() are inlined, this would not increase text size.

From bd26d8972130978deb9056a7a6da30b5c049914f Mon Sep 17 00:00:00 2001

Quoted 20 lines · Eric Dumazet

Quoted 8 lines · john stultz

Quoted 6 lines · Eric Dumazet

I can see many cpus entering tick_do_update_jiffies64() and all are calling write_seqlock(&xtime_lock);

Only first one can perform the work, but all others are waiting on the spinlock, get it, change seqcount, and realize they have nothing to do...

Quoted 9 lines

Huh. So who is calling tick_do_update_jiffies64 in your case? I know the sched_tick_timer and tick_nohz_handler checks to make sure tick_do_timer_cpu == cpu to avoid exactly the thundering heard problem on the jiffies update.

There's other spots that call tick_do_update_jiffies64, but I thought those were more rare. So there may be something else wrong going on here.

That I can answer :

[snip]

Quoted 2 lines

(I added do_timestamp1/do_timestamp2) after/before write_seqlock()/write_sequnlock()

Quoted 5 lines

         <idle>-0     [003]   920.355377: do_timestamp1 <-tick_do_update_jiffies64
          <idle>-0     [006]   920.355377: tick_do_update_jiffies64 <-tick_sched_timer
          <idle>-0     [003]   920.355378: do_timestamp2 <-tick_do_update_jiffies64
          <idle>-0     [000]   920.355657: tick_do_update_jiffies64 <-tick_check_idle
          <idle>-0     [000]   920.355660: tick_do_update_jiffies64 <-tick_nohz_restart_sched_tick

Thomas, any clues why this would be getting hammered?

Move the smp_rmb after cpu_relax loop in read_seqlock and add ACCESS_ONCE to make sure the test and return are consistent.

A multi-threaded core in the lab didn't like the update from 2.6.35 to 2.6.36, to the point it would hang during boot when multiple threads were active. Bisection showed af5ab277ded04bd9bc6b048c5a2f0e7d70ef0867 (clockevents:
Remove the per cpu tick skew) as the culprit and it is supported with stack traces showing xtime_lock waits including tick_do_update_jiffies64 and/or update_vsyscall.

Experimentation showed the combination of cpu_relax and smp_rmb was significantly slowing the progress of other threads sharing the core, and this patch is effective in avoiding the hang.

A theory is the rmb is affecting the whole core while the cpu_relax is causing a resource rebalance flush, together they cause an interfernce cadance that is unbroken when the seqlock reader has interrupts disabled.

At first I was confused why the refactor in 3c22cd5709e8143444a6d08682a87f4c57902df3 (kernel: optimise seqlock) didn't affect this patch application, but after some study that affected seqcount not seqlock. The new seqcount was not factored back into the seqlock. I defer that the future.

While the removal of the timer interrupt offset created contention for the xtime lock while a cpu does the additonal work to update the system clock, the seqlock implementation with the tight rmb spin loop goes back much further, and is just waiting for the right trigger.

Cc <[email protected]>

Signed-off-by Milton Miller <[email protected]>

---

To the readers of [RFC] time: xtime_lock is held too long:

I initially thought x86 would not see this because rmb would be a nop, but upon closer inspection X86_PPRO_FENCE will add a lfence for rmb.

milton

Index: common/include/linux/seqlock.h
===================================================================

include/linux/seqlock.h +0 -1

@@ -88,12 +88,12 @@ static __always_inline unsigned read_seq
 	unsigned ret;
 
 repeat:
-	ret = sl->sequence;

Move the smp_rmb after cpu_relax loop in read_seqlock and add ACCESS_ONCE to make sure the test and return are consistent.

A multi-threaded core in the lab didn't like the update

Quoted 1 line · Andi Kleen

If you have a better way to make it faster please share it.

Ideally we could use RCU :)

Have whatever state hold in one structure (possibly big, it doesnt matter) and switch pointer in writer once everything is setup in new structure.

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

Quoted 4 lines

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

On x86 all aligned stores are atomic. So I don't see how this could be a problem ever.

Quoted 7 lines · Andi Kleen

Quoted 4 lines

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

On x86 all aligned stores are atomic. So I don't see how this could be a problem ever.

No no. The issue was with the fact that in update_xtime_cache we modify xtime_cache twice (once setting it possibly backwards to xtime, then adding in the nsec offset).

Since get_seconds does no locking, this issue should be visible anywhere, as long as you manage to hit the race window between the first assignment and the second.

However, in the testing, the issue only showed up on P7, but not P6 or x86.

My guess was that the code:

xtime_cache.sec = xtime.sec
xtime_cache.nsec = xtime.nsec
xtime_cache.sec = xtime_cache.sec
+ div(xtime_cache.nsec + nsec, NSEC_PER_SEC, &rem);
xtime_cache.nsec = rem

Was getting rearranged to:

xtime_cache.sec = xtime.sec
+ div(xtime.nsec + nsec, NSEC_PER_SEC, &rem);
xtime_cache.nsec = rem

Which makes the xtime_cache.sec update atomic.

But its just a guess.

Quoted 35 lines · john stultz

Quoted 7 lines · Andi Kleen

Quoted 4 lines

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

On x86 all aligned stores are atomic. So I don't see how this could be a problem ever.

No no. The issue was with the fact that in update_xtime_cache we modify xtime_cache twice (once setting it possibly backwards to xtime, then adding in the nsec offset).

Since get_seconds does no locking, this issue should be visible anywhere, as long as you manage to hit the race window between the first assignment and the second.

However, in the testing, the issue only showed up on P7, but not P6 or x86.

My guess was that the code:

xtime_cache.sec = xtime.sec
xtime_cache.nsec = xtime.nsec
xtime_cache.sec = xtime_cache.sec
+ div(xtime_cache.nsec + nsec, NSEC_PER_SEC, &rem);
xtime_cache.nsec = rem

Was getting rearranged to:

xtime_cache.sec = xtime.sec
+ div(xtime.nsec + nsec, NSEC_PER_SEC, &rem);
xtime_cache.nsec = rem

Quoted 3 lines

Which makes the xtime_cache.sec update atomic.

But its just a guess.

Sure (disassembly could help to check this), but get_seconds() reads xtime.tv_sec ;)

Currently, yes.
But as I mentioned in an earlier mail, the problem was with 2.6.32-stable.

Quoted 5 lines · Andi Kleen

Quoted 4 lines

I suspect the reason this hasn't been triggered on x86 or power6 is due to compiler or processor optimizations reordering the assignment to in effect make it atomic. Or maybe the timing window to see the issue is harder to observe?

Quoted 2 lines

On x86 all aligned stores are atomic. So I don't see how this could be a problem ever.

No no. The issue was with the fact that in update_xtime_cache we modify xtime_cache twice (once setting it possibly backwards to xtime, then adding in the nsec offset).

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

Quoted 5 lines · John Stultz

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

get_seconds() is used in the x86 machine check handler and there is a comment saying:
/* We hope get_seconds stays lockless */

This needs to be carefully looked at if locking is introduced to get_seconds().

Quoted 5 lines · John Stultz

From: John Stultz <[email protected]>

So get_seconds() has always been lock free, with the assumption that accessing a long will be atomic.

get_seconds() is used in the x86 machine check handler and there is a comment saying:
/* We hope get_seconds stays lockless */

This needs to be carefully looked at if locking is introduced to get_seconds().