[PATCH] 2.6 timebase synchronization

[PATCH] 2.6 timebase synchronization

[Samuel Rydh]

Hi,

Here is a patch that provides improved generic SMP timebase
synchronization for 2.6.

The calibration error is typically 0 ticks (at least on my machine).
Without this patch, the difference is about 2 * 10^6 ticks...

/Samuel


# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
#	           ChangeSet	1.998   -> 1.999
#	arch/ppc/kernel/Makefile	1.51    -> 1.52
#	arch/ppc/kernel/smp.c	1.35    -> 1.36
#	               (new)	        -> 1.1     arch/ppc/kernel/smp-tbsync.c
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 03/08/08	samuel@ibrium.se	1.999
# SMP timebase synchronization
# --------------------------------------------
#
diff -Nru a/arch/ppc/kernel/Makefile b/arch/ppc/kernel/Makefile
--- a/arch/ppc/kernel/Makefile	Fri Aug  8 01:51:49 2003
+++ b/arch/ppc/kernel/Makefile	Fri Aug  8 01:51:49 2003
@@ -25,7 +25,7 @@
 obj-$(CONFIG_PCI)		+= pci.o
 obj-$(CONFIG_PCI)		+= pci-dma.o
 obj-$(CONFIG_KGDB)		+= ppc-stub.o
-obj-$(CONFIG_SMP)		+= smp.o
+obj-$(CONFIG_SMP)		+= smp.o smp-tbsync.o
 obj-$(CONFIG_TAU)		+= temp.o

 ifdef CONFIG_MATH_EMULATION
diff -Nru a/arch/ppc/kernel/smp-tbsync.c b/arch/ppc/kernel/smp-tbsync.c
--- /dev/null	Wed Dec 31 16:00:00 1969
+++ b/arch/ppc/kernel/smp-tbsync.c	Fri Aug  8 01:51:49 2003
@@ -0,0 +1,187 @@
+/*
+ * Smp timebase synchronization for ppc.
+ *
+ * Copyright (C) 2003 Samuel Rydh (samuel@ibrium.se)
+ *
+ */
+
+#include <linux/config.h>
+#include <linux/kernel.h>
+#include <linux/sched.h>
+#include <linux/smp.h>
+#include <linux/unistd.h>
+#include <linux/init.h>
+#include <asm/atomic.h>
+#include <asm/smp.h>
+#include <asm/time.h>
+
+#define NUM_ITER		300
+
+enum {
+	kExit=0, kSetAndTest, kTest
+};
+
+/* keep things aligned in order to avoid cache ping-pong */
+struct tbsync_vars {
+	/* CPU0 write */
+	volatile int		tbu;
+	volatile int		tbl;
+	volatile int		mark;
+	volatile int		handshake;
+	volatile int		cmd;
+	int			filler1[3+8];
+
+	/* CPU0 and CPU1 write */
+	atomic_t		contest;
+};
+
+static volatile int		tbsync_ack;
+static volatile int		running;
+
+static struct tbsync_vars	*tbsync;
+
+
+#define I_SYNC()		asm volatile("sync; isync");
+#define CONTEST_CACHE_FLUSH()	asm volatile("dcbf 0,%0 ; sync ; isync" : : \
+						"r" (&tbsync->contest) );
+
+
+static int __devinit
+enter_contest( int mark, int add )
+{
+	while( (int)(get_tbl() - mark) < 0 )
+		;
+	return atomic_add_return( add, &tbsync->contest );
+}
+
+void __devinit
+smp_generic_take_timebase( void )
+{
+	int cmd, tbl;
+
+	while( !running )
+		;
+	for( ;; ) {
+		tbsync_ack = 1;
+		while( !tbsync->handshake )
+			;
+
+		I_SYNC();
+
+		cmd = tbsync->cmd;
+		tbl = tbsync->tbl;
+		tbsync_ack = 0;
+		if( cmd == kExit )
+			return;
+
+		while( tbsync->handshake )
+			;
+		if( cmd == kSetAndTest ) {
+			asm volatile ("isync");
+			asm volatile ("mttbl %0" :: "r" (tbl) );
+			asm volatile ("mttbu %0" :: "r" (tbsync->tbu) );
+		}
+		(void) enter_contest( tbsync->mark, 2 );
+
+		CONTEST_CACHE_FLUSH();
+	}
+}
+
+static int __devinit
+start_contest( int cmd, int offset, int num )
+{
+	int i, tbu, tbl, mark, result, score=0;
+
+	tbsync->cmd = cmd;
+
+	for( i=-3; i<num; ) {
+		atomic_set( &tbsync->contest, 0 );
+		CONTEST_CACHE_FLUSH();
+
+		tbl = get_tbl() + 2000;
+		tbsync->tbu = tbu = get_tbu();
+		tbsync->tbl = tbl + offset;
+		tbsync->mark = mark = tbl + 500;
+
+		I_SYNC();
+
+		tbsync->handshake = 1;
+		while( tbsync_ack )
+			;
+
+		while( (int)(get_tbl() - tbl) <= 0 )
+			;
+		tbsync->handshake = 0;
+		result = enter_contest( mark, -1 );
+
+		while( !tbsync_ack )
+			;
+
+		if( tbsync->tbu != get_tbu() || ((tbsync->tbl ^ get_tbl()) & 0x80000000) )
+			continue;
+
+		if( i++ > 0 )
+			score += result;
+	}
+	return score;
+}
+
+void __devinit
+smp_generic_give_timebase( void )
+{
+	int i, offset, score, min=0, max=5000, next_offset=1000;
+	int best=10000, best_offset;
+
+	printk("Synchronizing timebase\n");
+
+	/* if this fails then this kernel won't work anyway... */
+	tbsync = kmalloc( sizeof(*tbsync), GFP_KERNEL );
+	memset( tbsync, 0, sizeof(*tbsync) );
+	I_SYNC();
+	running = 1;
+	while( !tbsync_ack )
+		;
+
+	/* binary search for optimal offset */
+	do {
+		offset = next_offset;
+		score = start_contest( kSetAndTest, offset, NUM_ITER );
+
+		printk("score %d, offset %d [%d..%d]\n", score, offset, min, max );
+
+		if( score > 0 )
+			max = offset;
+		else {
+			min = offset;
+			score = -score;
+		}
+		if( score < best ) {
+			best_offset = offset;
+			best = score;
+		}
+		next_offset = (min + max)/2;
+	} while( offset != next_offset );
+
+	/* guard against inaccurate mttb */
+	for( i=0; i<10; i++ ) {
+		if( (score=start_contest(kTest, best_offset, NUM_ITER)) < 0 )
+			score = -score;
+		if( score <= best || score < 20 )
+			break;
+		start_contest( kSetAndTest, best_offset, NUM_ITER/10 );
+	}
+	printk("Final timbase offset: %d (%d/%d)\n", best_offset, score, NUM_ITER );
+
+	/* exiting */
+	tbsync->cmd = kExit;
+	I_SYNC();
+	tbsync->handshake = 1;
+	while( tbsync_ack )
+		;
+	tbsync->handshake = 0;
+	kfree( tbsync );
+	tbsync = NULL;
+
+	/* all done */
+	smp_tb_synchronized = 1;
+}
diff -Nru a/arch/ppc/kernel/smp.c b/arch/ppc/kernel/smp.c
--- a/arch/ppc/kernel/smp.c	Fri Aug  8 01:51:49 2003
+++ b/arch/ppc/kernel/smp.c	Fri Aug  8 01:51:49 2003
@@ -58,10 +58,6 @@
 /* all cpu mappings are 1-1 -- Cort */
 volatile unsigned long cpu_callin_map[NR_CPUS];

-#define TB_SYNC_PASSES 4
-volatile unsigned long __initdata tb_sync_flag = 0;
-volatile unsigned long __initdata tb_offset = 0;
-
 int start_secondary(void *);
 extern int cpu_idle(void *unused);
 void smp_call_function_interrupt(void);
@@ -288,41 +284,6 @@
 		atomic_inc(&call_data->finished);
 }

-/* FIXME: Do this properly for all archs --RR */
-static spinlock_t timebase_lock = SPIN_LOCK_UNLOCKED;
-static unsigned int timebase_upper = 0, timebase_lower = 0;
-
-void __devinit
-smp_generic_give_timebase(void)
-{
-	spin_lock(&timebase_lock);
-	do {
-		timebase_upper = get_tbu();
-		timebase_lower = get_tbl();
-	} while (timebase_upper != get_tbu());
-	spin_unlock(&timebase_lock);
-
-	while (timebase_upper || timebase_lower)
-		rmb();
-}
-
-void __devinit
-smp_generic_take_timebase(void)
-{
-	int done = 0;
-
-	while (!done) {
-		spin_lock(&timebase_lock);
-		if (timebase_upper || timebase_lower) {
-			set_tb(timebase_upper, timebase_lower);
-			timebase_upper = 0;
-			timebase_lower = 0;
-			done = 1;
-		}
-		spin_unlock(&timebase_lock);
-	}
-}
-
 static void __devinit smp_store_cpu_info(int id)
 {
         struct cpuinfo_PPC *c = &cpu_data[id];
@@ -423,7 +384,7 @@

 	/* wake up cpu */
 	smp_ops->kick_cpu(cpu);
-
+
 	/*
 	 * wait to see if the cpu made a callin (is actually up).
 	 * use this value that I found through experimentation.


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Re: [PATCH] 2.6 timebase synchronization

[Samuel Rydh]

On Fri, Aug 08, 2003 at 02:15:23AM +0200, Samuel Rydh wrote:
>
> Hi,
>
> Here is a patch that provides improved generic SMP timebase
> synchronization for 2.6.
>

Attached is an improved version of the patch.

/Samuel



diff -Nru a/arch/ppc/kernel/Makefile b/arch/ppc/kernel/Makefile
--- a/arch/ppc/kernel/Makefile	Sat Aug  9 03:10:58 2003
+++ b/arch/ppc/kernel/Makefile	Sat Aug  9 03:10:58 2003
@@ -25,7 +25,7 @@
 obj-$(CONFIG_PCI)		+= pci.o
 obj-$(CONFIG_PCI)		+= pci-dma.o
 obj-$(CONFIG_KGDB)		+= ppc-stub.o
-obj-$(CONFIG_SMP)		+= smp.o
+obj-$(CONFIG_SMP)		+= smp.o smp-tbsync.o
 obj-$(CONFIG_TAU)		+= temp.o

 ifdef CONFIG_MATH_EMULATION
diff -Nru a/arch/ppc/kernel/smp-tbsync.c b/arch/ppc/kernel/smp-tbsync.c
--- /dev/null	Wed Dec 31 16:00:00 1969
+++ b/arch/ppc/kernel/smp-tbsync.c	Sat Aug  9 03:10:58 2003
@@ -0,0 +1,181 @@
+/*
+ * Smp timebase synchronization for ppc.
+ *
+ * Copyright (C) 2003 Samuel Rydh (samuel@ibrium.se)
+ *
+ */
+
+#include <linux/config.h>
+#include <linux/kernel.h>
+#include <linux/sched.h>
+#include <linux/smp.h>
+#include <linux/unistd.h>
+#include <linux/init.h>
+#include <asm/atomic.h>
+#include <asm/smp.h>
+#include <asm/time.h>
+
+#define NUM_ITER		300
+
+enum {
+	kExit=0, kSetAndTest, kTest
+};
+
+static struct {
+	volatile int		tbu;
+	volatile int		tbl;
+	volatile int		mark;
+	volatile int		cmd;
+	volatile int		handshake;
+	int			filler[3];
+
+	volatile int		ack;
+	int			filler2[7];
+
+	volatile int		race_result;
+} *tbsync;
+
+static volatile int		running;
+
+static void __devinit
+enter_contest( int mark, int add )
+{
+	while( (int)(get_tbl() - mark) < 0 )
+		tbsync->race_result = add;
+}
+
+void __devinit
+smp_generic_take_timebase( void )
+{
+	int cmd, tbl, tbu;
+
+	local_irq_disable();
+	while( !running )
+		;
+	rmb();
+
+	for( ;; ) {
+		tbsync->ack = 1;
+		while( !tbsync->handshake )
+			;
+		rmb();
+
+		cmd = tbsync->cmd;
+		tbl = tbsync->tbl;
+		tbu = tbsync->tbu;
+		tbsync->ack = 0;
+		if( cmd == kExit )
+			return;
+
+		if( cmd == kSetAndTest ) {
+			while( tbsync->handshake )
+				;
+			asm volatile ("mttbl %0" :: "r" (tbl) );
+			asm volatile ("mttbu %0" :: "r" (tbu) );
+		} else {
+			while( tbsync->handshake )
+				;
+		}
+		enter_contest( tbsync->mark, -1 );
+	}
+	local_irq_enable();
+}
+
+static int __devinit
+start_contest( int cmd, int offset, int num )
+{
+	int i, tbu, tbl, mark, score=0;
+
+	tbsync->cmd = cmd;
+
+	local_irq_disable();
+	for( i=-3; i<num; ) {
+		tbl = get_tbl() + 400;
+		tbsync->tbu = tbu = get_tbu();
+		tbsync->tbl = tbl + offset;
+		tbsync->mark = mark = tbl + 400;
+
+		wmb();
+
+		tbsync->handshake = 1;
+		while( tbsync->ack )
+			;
+
+		while( (int)(get_tbl() - tbl) <= 0 )
+			;
+		tbsync->handshake = 0;
+		enter_contest( mark, 1 );
+
+		while( !tbsync->ack )
+			;
+
+		if( tbsync->tbu != get_tbu() || ((tbsync->tbl ^ get_tbl()) & 0x80000000) )
+			continue;
+		if( i++ > 0 )
+			score += tbsync->race_result;
+	}
+	local_irq_enable();
+	return score;
+}
+
+void __devinit
+smp_generic_give_timebase( void )
+{
+	int i, score, score2, old, min=0, max=5000, offset=1000;
+
+	printk("Synchronizing timebase\n");
+
+	/* if this fails then this kernel won't work anyway... */
+	tbsync = kmalloc( sizeof(*tbsync), GFP_KERNEL );
+	memset( tbsync, 0, sizeof(*tbsync) );
+	mb();
+	running = 1;
+
+	while( !tbsync->ack )
+		;
+
+	/* binary search */
+	for( old=-1 ; old != offset ; offset=(min+max)/2 ) {
+		score = start_contest( kSetAndTest, offset, NUM_ITER );
+
+		printk("score %d, offset %d\n", score, offset );
+
+		if( score > 0 )
+			max = offset;
+		else
+			min = offset;
+		old = offset;
+	}
+	score = start_contest( kSetAndTest, min, NUM_ITER );
+	score2 = start_contest( kSetAndTest, max, NUM_ITER );
+
+	printk( "Min %d (score %d), Max %d (score %d)\n", min, score, max, score2 );
+	score = abs( score );
+	score2 = abs( score2 );
+	offset = (score < score2) ? min : max;
+
+	/* guard against inaccurate mttb */
+	for( i=0; i<10; i++ ) {
+		start_contest( kSetAndTest, offset, NUM_ITER/10 );
+
+		if( (score2=start_contest(kTest, offset, NUM_ITER)) < 0 )
+			score2 = -score2;
+		if( score2 <= score || score2 < 20 )
+			break;
+	}
+	printk("Final offset: %d (%d/%d)\n", offset, score2, NUM_ITER );
+
+	/* exiting */
+	tbsync->cmd = kExit;
+	wmb();
+	tbsync->handshake = 1;
+	while( tbsync->ack )
+		;
+	tbsync->handshake = 0;
+	kfree( tbsync );
+	tbsync = NULL;
+	running = 0;
+
+	/* all done */
+	smp_tb_synchronized = 1;
+}
diff -Nru a/arch/ppc/kernel/smp.c b/arch/ppc/kernel/smp.c
--- a/arch/ppc/kernel/smp.c	Sat Aug  9 03:10:58 2003
+++ b/arch/ppc/kernel/smp.c	Sat Aug  9 03:10:58 2003
@@ -58,10 +58,6 @@
 /* all cpu mappings are 1-1 -- Cort */
 volatile unsigned long cpu_callin_map[NR_CPUS];

-#define TB_SYNC_PASSES 4
-volatile unsigned long __initdata tb_sync_flag = 0;
-volatile unsigned long __initdata tb_offset = 0;
-
 int start_secondary(void *);
 extern int cpu_idle(void *unused);
 void smp_call_function_interrupt(void);
@@ -288,41 +284,6 @@
 		atomic_inc(&call_data->finished);
 }

-/* FIXME: Do this properly for all archs --RR */
-static spinlock_t timebase_lock = SPIN_LOCK_UNLOCKED;
-static unsigned int timebase_upper = 0, timebase_lower = 0;
-
-void __devinit
-smp_generic_give_timebase(void)
-{
-	spin_lock(&timebase_lock);
-	do {
-		timebase_upper = get_tbu();
-		timebase_lower = get_tbl();
-	} while (timebase_upper != get_tbu());
-	spin_unlock(&timebase_lock);
-
-	while (timebase_upper || timebase_lower)
-		rmb();
-}
-
-void __devinit
-smp_generic_take_timebase(void)
-{
-	int done = 0;
-
-	while (!done) {
-		spin_lock(&timebase_lock);
-		if (timebase_upper || timebase_lower) {
-			set_tb(timebase_upper, timebase_lower);
-			timebase_upper = 0;
-			timebase_lower = 0;
-			done = 1;
-		}
-		spin_unlock(&timebase_lock);
-	}
-}
-
 static void __devinit smp_store_cpu_info(int id)
 {
         struct cpuinfo_PPC *c = &cpu_data[id];
@@ -423,7 +384,7 @@

 	/* wake up cpu */
 	smp_ops->kick_cpu(cpu);
-
+
 	/*
 	 * wait to see if the cpu made a callin (is actually up).
 	 * use this value that I found through experimentation.

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Re: [PATCH] 2.6 timebase synchronization

[Benjamin Herrenschmidt]

On Sat, 2003-08-09 at 03:13, Samuel Rydh wrote:
> On Fri, Aug 08, 2003 at 02:15:23AM +0200, Samuel Rydh wrote:
> >
> > Hi,
> >
> > Here is a patch that provides improved generic SMP timebase
> > synchronization for 2.6.
> >
>
> Attached is an improved version of the patch.

I'm on vacation now, I can't test it until I'm back, but that
looks quite good overall (except maybe the MacOS-like constant
naming for kXXXX :)

However, does it work with more than 2 CPUs ? It seem to be rather
dual CPU centric from my understanding of the ack mecanism... The TB sync
code is also used on 4 CPU daystar machines and possibly some other chrp
with more than 2 CPUs.

Paul, any comment ?

Ben.


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Re: [PATCH] 2.6 timebase synchronization

[Samuel Rydh]

On Sat, Aug 09, 2003 at 10:58:11AM +0200, Benjamin Herrenschmidt wrote:
> I'm on vacation now, I can't test it until I'm back, but that
> looks quite good overall (except maybe the MacOS-like constant
> naming for kXXXX :)
>
> However, does it work with more than 2 CPUs ?

Yes, it does. The code simply passes the timestamp from CPU0
to the one currently beeing booted (the CPU0 timebase is
not affected).

> It seem to be rather
> dual CPU centric from my understanding of the ack mecanism...

Only a pair of CPUs are synchronized simultaneously, yes. But there
is absolutely no need to synchronize more than two at the same.
Besides, CPU2 is not started until CPU1 has booted...

/Samuel

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Re: [PATCH] 2.6 timebase synchronization

[Paul Mackerras]

Samuel Rydh writes:

> Attached is an improved version of the patch.

How many SMP machines are there where we don't know how to freeze/thaw
the timebase?  We know how to do that on the old powersurge powermacs,
on CHRP systems and on at least some of the recent core99 powermacs
(those that have a timebase-enable property on the cpu device nodes).
What machines are left?

Paul.

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Re: [PATCH] 2.6 timebase synchronization

[Benjamin Herrenschmidt]

On Sun, 2003-08-10 at 04:09, Paul Mackerras wrote:
> Samuel Rydh writes:
>
> > Attached is an improved version of the patch.
>
> How many SMP machines are there where we don't know how to freeze/thaw
> the timebase?  We know how to do that on the old powersurge powermacs,
> on CHRP systems and on at least some of the recent core99 powermacs
> (those that have a timebase-enable property on the cpu device nodes).
> What machines are left?

We know how to do it on some core99, though we don't actually do it
yet ;) We use software sync on all core99 for now.

Remaining are some older core99 machines, the 4-way DayStar oldworld
machines, and afaik, that's all...

Ben.


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Re: [PATCH] 2.6 timebase synchronization

[Mark Guertin]

On 8/10/03 5:39 AM, "Benjamin Herrenschmidt" <benh@kernel.crashing.org>
wrote:

> Remaining are some older core99 machines, the 4-way DayStar oldworld
> machines, and afaik, that's all...

As always, my Daystar quad is around, and if you want/need testing on it
just let me know.  I also have a couple of Powersurge 2-way as well.

Mark (Gerk)


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Re: [PATCH] 2.6 timebase synchronization

[Samuel Rydh]

On Sun, Aug 10, 2003 at 11:39:08AM +0200, Benjamin Herrenschmidt wrote:
>
> On Sun, 2003-08-10 at 04:09, Paul Mackerras wrote:
> > Samuel Rydh writes:
> >
> > > Attached is an improved version of the patch.
> >
> > How many SMP machines are there where we don't know how to freeze/thaw
> > the timebase?  We know how to do that on the old powersurge powermacs,
> > on CHRP systems and on at least some of the recent core99 powermacs
> > (those that have a timebase-enable property on the cpu device nodes).
> > What machines are left?
>
> We know how to do it on some core99, though we don't actually do it
> yet ;) We use software sync on all core99 for now.

Btw, the freeze/thaw timebase setting that is done on psurge is lost
since the generic timebase calibration mechanism is still invoked
afterwards (and at that time, the timebases are ticking).

/Samuel


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/