Trace Clock v2

This patch selects HAVE_GET_CYCLES and makes sure get_cycles_barrier() and get_cycles_rate() are implemented.

Signed-off-by Mathieu Desnoyers <[email protected]>

CC [email protected]

CC [email protected]

CC David Miller <[email protected]>

CC Linus Torvalds <[email protected]>

CC Andrew Morton <[email protected]>

CC Ingo Molnar <[email protected]>

CC Peter Zijlstra <[email protected]>

CC Thomas Gleixner <[email protected]>

CC Steven Rostedt <[email protected]>

CC [email protected]

---
arch/powerpc/Kconfig | 1 +
arch/powerpc/include/asm/timex.h | 11 +++++++++++

2 files changed, 12 insertions(+)

Index: linux.trees.git/arch/powerpc/Kconfig
===================================================================

Quoted 24 lines · Mathieu Desnoyers

This patch selects HAVE_GET_CYCLES and makes sure get_cycles_barrier() and get_cycles_rate() are implemented.

Signed-off-by Mathieu Desnoyers <[email protected]>

CC [email protected]

CC [email protected]

CC David Miller <[email protected]>

CC Linus Torvalds <[email protected]>

CC Andrew Morton <[email protected]>

CC Ingo Molnar <[email protected]>

CC Peter Zijlstra <[email protected]>

CC Thomas Gleixner <[email protected]>

CC Steven Rostedt <[email protected]>

CC [email protected]

---
arch/powerpc/Kconfig | 1 +
arch/powerpc/include/asm/timex.h | 11 +++++++++++

2 files changed, 12 insertions(+)

Index: linux.trees.git/arch/powerpc/Kconfig
===================================================================

arch/powerpc/Kconfig config PPC · line 124

Quoted 4 lines

arch/powerpc/Kconfig +1 -0

@@ -121,6 +121,7 @@ config PPC
 	select HAVE_DMA_ATTRS if PPC64
 	select USE_GENERIC_SMP_HELPERS if SMP
 	select HAVE_OPROFILE
+	select HAVE_GET_CYCLES if PPC64

So maybe it's just me because it's Friday and I'm on vacation, but I don't see anything overly specific to ppc64 here. In fact, you use get_cycles_rate for all of powerpc in a later patch in the series.

Is there something special about HAVE_GET_CYCLES that I'm missing that would make it only apply to ppc64 and not ppc32?

josh

do you actually use the RCU internals? or do you just reimplement an RCU algorithm?

32 to 64 bits clock extension. Extracts 64 bits tsc from a [1..32] bits counter, kept up to date by periodical timer interrupt. Lockless.

...

+#include <linux/sched.h> /* FIX for m68k local_irq_enable in on_each_cpu */

kernel/trace/trace-clock-32-to-64.c new file +15 -0

+	cpu_synth = &per_cpu(synthetic_tsc, smp_processor_id());
+	tsc = trace_clock_read32();		/* Hardware clocksource read */
+
+	if (tsc < HW_LSB(cpu_synth->tsc[cpu_synth->index].sel.lsb)) {
+		unsigned int new_index = 1 - cpu_synth->index; /* 0 <-> 1 */
+		/*
+		 * Overflow
+		 * Non atomic update of the non current synthetic TSC, followed
+		 * by an atomic index change. There is no write concurrency,
+		 * so the index read/write does not need to be atomic.
+		 */
+		cpu_synth->tsc[new_index].val =
+			(SW_MSB(cpu_synth->tsc[cpu_synth->index].val)
+				| (u64)tsc) + (1ULL << HW_BITS);
+		cpu_synth->index = new_index;	/* atomic change of index */

Quoted 6 lines · On Fri, 07 Nov 2008 00:23:43 -0500 Mathieu Desnoyers…

32 to 64 bits clock extension. Extracts 64 bits tsc from a [1..32] bits counter, kept up to date by periodical timer interrupt. Lockless.

...

+#include <linux/sched.h> /* FIX for m68k local_irq_enable in on_each_cpu */

What's going on here?

kernel/trace/trace-clock-32-to-64.c line 68

Quoted 11 lines

kernel/trace/trace-clock-32-to-64.c new file +11 -0

+struct synthetic_tsc_struct {
+	union {
+		u64 val;
+		struct {
+#ifdef __BIG_ENDIAN
+			u32 msb;
+			u32 lsb;
+#else
+			u32 lsb;
+			u32 msb;
+#endif

One would expect an identifier called "msb" to mean "most significant bit" or possible "most significant byte".

Maybe ms32 and ls32?

kernel/trace/trace-clock-32-to-64.c line 76

Quoted 8 lines

kernel/trace/trace-clock-32-to-64.c new file +8 -0

+		} sel;
+	} tsc[2];
+	unsigned int index;	/* Index of the current synth. tsc. */
+};
+
+static DEFINE_PER_CPU(struct synthetic_tsc_struct, synthetic_tsc);
+
+/* Called from IPI : either in interrupt or process context */

IPI handlers should always be called with local interrupts disabled.

kernel/trace/trace-clock-32-to-64.c line 82

Quoted 6 lines

kernel/trace/trace-clock-32-to-64.c new file +6 -0

+static void update_synthetic_tsc(void)
+{
+	struct synthetic_tsc_struct *cpu_synth;
+	u32 tsc;
+
+	preempt_disable();

which would make this unnecessary.

Quoted 19 lines

kernel/trace/trace-clock-32-to-64.c new file +19 -0

+	cpu_synth = &per_cpu(synthetic_tsc, smp_processor_id());
+	tsc = trace_clock_read32();		/* Hardware clocksource read */
+
+	if (tsc < HW_LSB(cpu_synth->tsc[cpu_synth->index].sel.lsb)) {
+		unsigned int new_index = 1 - cpu_synth->index; /* 0 <-> 1 */
+		/*
+		 * Overflow
+		 * Non atomic update of the non current synthetic TSC, followed
+		 * by an atomic index change. There is no write concurrency,
+		 * so the index read/write does not need to be atomic.
+		 */
+		cpu_synth->tsc[new_index].val =
+			(SW_MSB(cpu_synth->tsc[cpu_synth->index].val)
+				| (u64)tsc) + (1ULL << HW_BITS);
+		cpu_synth->index = new_index;	/* atomic change of index */
+	} else {
+		/*
+		 * No overflow : We know that the only bits changed are
+		 * contained in the 32 LSBs, which can be written to atomically.

kernel/trace/trace-clock-32-to-64.c line 107

Quoted 6 lines

kernel/trace/trace-clock-32-to-64.c new file +6 -0

+		 */
+		cpu_synth->tsc[cpu_synth->index].sel.lsb =
+			SW_MSB(cpu_synth->tsc[cpu_synth->index].sel.lsb) | tsc;
+	}
+	preempt_enable();
+}

Is there something we should be fixing in m68k?

Quoted 2 lines

Is there something we should be fixing in m68k?

Yes, but I fear it's going to go deep into include hell :-(

Quoted 3 lines · On Fri, 7 Nov 2008 01:16:43 -0500 Mathieu Desnoyers…

Quoted 2 lines

Is there something we should be fixing in m68k?

Quoted 1 line

Yes, but I fear it's going to go deep into include hell :-(

Oh, OK. I thought that the comment meant that m68k's on_each_cpu() behaves differently at runtime from other architectures (and wrongly).

If it's just some compile-time #include snafu then that's far less of a concern.

Quoted 7 lines · * Andrew Morton ([email protected]) wrote:

Quoted 4 lines · On Fri, 7 Nov 2008 01:16:43 -0500 Mathieu Desnoyers…

Quoted 2 lines

Is there something we should be fixing in m68k?

Yes, but I fear it's going to go deep into include hell :-(

Quoted 6 lines

Oh, OK. I thought that the comment meant that m68k's on_each_cpu() behaves differently at runtime from other architectures (and wrongly).

If it's just some compile-time #include snafu then that's far less of a concern.

Should I simply remove this comment then ?

Quoted 8 lines · On Fri, 7 Nov 2008 11:12:38 -0500 Mathieu Desnoyers…

Quoted 7 lines · * Andrew Morton ([email protected]) wrote:

Quoted 4 lines · On Fri, 7 Nov 2008 01:16:43 -0500 Mathieu Desnoyers…

Quoted 2 lines

Is there something we should be fixing in m68k?

Yes, but I fear it's going to go deep into include hell :-(

Quoted 9 lines

Quoted 6 lines

Oh, OK. I thought that the comment meant that m68k's on_each_cpu() behaves differently at runtime from other architectures (and wrongly).

If it's just some compile-time #include snafu then that's far less of a concern.

Should I simply remove this comment then ?

umm, it could perhaps be clarified - mention that it's needed for an include order problem.

It's a bit odd. Surely by the time we've included these:

kernel/trace/trace-clock-32-to-64.c new file +10 -0

+#include <linux/module.h>
+#include <linux/init.h>
+#include <linux/delay.h>
+#include <linux/timer.h>
+#include <linux/workqueue.h>
+#include <linux/cpu.h>
+#include <linux/timex.h>
+#include <linux/bitops.h>
+#include <linux/trace-clock.h>
+#include <linux/smp.h>

someone has already included sched.h, and the definition of _LINUX_SCHED_H will cause the later inclusion to not change anything?

Yup, you are right. However, the case where one CPU sees the clock source a little bit off-sync (late) still poses a problem. Example follows :

CPU A B

       read __m_cnt_hi (0x80000000)
       read hw cnt low (0x00000001)
       (wrap detected :
        (s32)(0x80000000 ^ 0x1) < 0)
       write __m_cnt_hi = 0x00000001
       return 0x0000000100000001
                                            read __m_cnt_hi (0x00000001)
                                     (late) read hw cnt low (0xFFFFFFFA)
                                            (wrap detected :
                                             (s32)(0x00000001 ^ 0xFFFFFFFA) <

                                            write __m_cnt_hi = 0x80000001
                                            return 0x80000001FFFFFFFA
                                                                  (time jumps)

A similar situation can be generated by out-of-order hi/low bits reads.

include/linux/cnt32_to_63.h union cnt32_to_63 { · line 81

Quoted 10 lines · On Fri, 07 Nov 2008 00:23:44 -0500 Mathieu Desnoyers…

#define cnt32_to_63(cnt_lo) \
({ \

include/linux/cnt32_to_63.h +2 -1

-	static volatile u32 __m_cnt_hi; \
+	static u32 __m_cnt_hi; \
 	union cnt32_to_63 __x; \
 	__x.hi = __m_cnt_hi; \
+	smp_rmb(); 	/* read __m_cnt_hi before mmio cnt_lo */ \
 	__x.lo = (cnt_lo); \
 	if (unlikely((s32)(__x.hi ^ __x.lo) < 0)) \
 		__m_cnt_hi = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \

Oh dear. We have a macro which secretly maintains per-instantiation-site global state? And doesn't even implement locking to protect that state?

I mean, the darned thing is called from sched_clock(), which can be concurrently called on separate CPUs and which can be called from interrupt context (with an arbitrary nesting level!) while it was running in process context.

/*
* Caller must provide locking to protect *caller_state */

Quoted 16 lines · Andrew Morton

include/linux/cnt32_to_63.h union cnt32_to_63 { · line 81

Quoted 10 lines · On Fri, 07 Nov 2008 00:23:44 -0500 Mathieu Desnoyers…

#define cnt32_to_63(cnt_lo) \
({ \

include/linux/cnt32_to_63.h +2 -1

-	static volatile u32 __m_cnt_hi; \
+	static u32 __m_cnt_hi; \
 	union cnt32_to_63 __x; \
 	__x.hi = __m_cnt_hi; \
+	smp_rmb(); 	/* read __m_cnt_hi before mmio cnt_lo */ \
 	__x.lo = (cnt_lo); \
 	if (unlikely((s32)(__x.hi ^ __x.lo) < 0)) \
 		__m_cnt_hi = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \

Oh dear. We have a macro which secretly maintains per-instantiation-site global state? And doesn't even implement locking to protect that state?

Please do me a favor and look for those very unfrequent posts I've sent to lkml lately.

I've explained it all at least 3 times so far, to Peter
Zijlstra, to David Howells, to Mathieu Desnoyers, and now to you.

Quoted 4 lines

I mean, the darned thing is called from sched_clock(), which can be concurrently called on separate CPUs and which can be called from interrupt context (with an arbitrary nesting level!) while it was running in process context.

Yes! And this is so on *purpose*. Please take some time to read the comment that goes along with it,

and if you're still not convinced then
look for those explanation emails I've already posted.

Quoted 3 lines

/*
* Caller must provide locking to protect *caller_state */

NO! This is meant to be LOCK FREE!

We have a macro which must only have a single usage in any particular kernel build (and nothing to detect a violation of that).

It apparently tries to avoid races via ordering tricks, as long as it is called with sufficient frequency. But nothing guarantees that it _is_ called sufficiently frequently?

There is absolutely no reason why the first two of these quite bad things needed to be done. In fact there is no reason why it needed to be implemented as a macro at all.

As I said in the text which you deleted and ignored, this would be better if it was implemented as a C function which requires that the caller explicitly pass in a reference to the state storage.

Quoted 3 lines · Andrew Morton

As I said in the text which you deleted and ignored, this would be better if it was implemented as a C function which requires that the caller explicitly pass in a reference to the state storage.

I'd be quite happy if it was:

	static inline u64 cnt32_to_63(u32 cnt_lo, u32 *__m_cnt_hi)
	{
		union cnt32_to_63 __x;
		__x.hi = *__m_cnt_hi;
		__x.lo = cnt_lo;
		if (unlikely((s32)(__x.hi ^ __x.lo) < 0))
			*__m_cnt_hi =
				__x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31);
		return __x.val;
	}

I imagine this would compile pretty much the same as the macro.

I think it
would make it more obvious about the independence of the storage.

Alternatively, perhaps Nicolas just needs to mention this in the comment more clearly.

Quoted 5 lines · David Howells

Quoted 3 lines · Andrew Morton

As I said in the text which you deleted and ignored, this would be better if it was implemented as a C function which requires that the caller explicitly pass in a reference to the state storage.

The whole purpose of that thing is to be utterly fast and lightweight.

Having an out of line C call would trash the major advantage of this code.

Quoted 13 lines

I'd be quite happy if it was:

	static inline u64 cnt32_to_63(u32 cnt_lo, u32 *__m_cnt_hi)
	{
		union cnt32_to_63 __x;
		__x.hi = *__m_cnt_hi;
		__x.lo = cnt_lo;
		if (unlikely((s32)(__x.hi ^ __x.lo) < 0))
			*__m_cnt_hi =
				__x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31);
		return __x.val;
	}

Quoted 1 line

I imagine this would compile pretty much the same as the macro.

Depends. As everybody has noticed now, the read ordering is important, and if gcc decides to not inline this

for whatever reason then the
ordering is lost.

This is why this was a macro to start with.

Quoted 2 lines

I think it
would make it more obvious about the independence of the storage.

I don't think having the associated storage be outside the macro make any sense either. There is simply no valid reason for having it shared between multiple invokations of the macro, as well as making its interface more complex for no gain.

Quoted 2 lines

Alternatively, perhaps Nicolas just needs to mention this in the comment more clearly.

I wrote that code so to me it is cristal clear already. Any suggestions as to how this could be improved?

If gcc did that then it would need to generate static instances of inlined functions within individual compilation units. It would be a disaster for the kernel. For a start, functions which are "inlined" in kernel modules wouldn't be able to access their static storage and modprobing them would fail.

Does mn10300's get_cycles() really count backwards?

The first two callsites I looked at (crypto/tcrypt.c and fs/ext4/mballoc.c) assume that it is an upcounter.

Quoted 5 lines · Andrew Morton

If gcc did that then it would need to generate static instances of inlined functions within individual compilation units. It would be a disaster for the kernel. For a start, functions which are "inlined" in kernel modules wouldn't be able to access their static storage and modprobing them would fail.

Do you expect a static inline function that lives in a header file and that has a static variable in it to share that static variable over all instances of that function in a program? Or do you expect the static variable to be limited at the file level? Or just at the invocation level?

I'd expect it to behave in the same way as it would if the function was implemented out-of-line.

But it occurs to me that the modrobe-doesnt-work thing would happen if the function _is_ inlined anyway, so we won't be doing that.

Whatever. Killing this many puppies because gcc may do something so bizarrely wrong isn't justifiable.

Quoted 8 lines · Andrew Morton

I'd expect it to behave in the same way as it would if the function was implemented out-of-line.

But it occurs to me that the modrobe-doesnt-work thing would happen if the function _is_ inlined anyway, so we won't be doing that.

Whatever. Killing this many puppies because gcc may do something so bizarrely wrong isn't justifiable.

With gcc, you get one instance of the static variable from inside a static (inline or outofline) function per .o file that invokes it, and these do not merge even though they're common symbols. I asked around and the opinion seems to be that this is correct C. I suppose it's the equivalent of cutting and pasting a function between several files - why should the compiler assume it's the same function in each?

Quoted 12 lines · On Fri, 07 Nov 2008 17:10:00 +0000 David Howells <[email protected]> wrote:

Quoted 8 lines · Andrew Morton

I'd expect it to behave in the same way as it would if the function was implemented out-of-line.

But it occurs to me that the modrobe-doesnt-work thing would happen if the function _is_ inlined anyway, so we won't be doing that.

Whatever. Killing this many puppies because gcc may do something so bizarrely wrong isn't justifiable.

Quoted 7 lines

With gcc, you get one instance of the static variable from inside a static (inline or outofline) function per .o file that invokes it, and these do not merge even though they're common symbols. I asked around and the opinion seems to be that this is correct C. I suppose it's the equivalent of cutting and pasting a function between several files - why should the compiler assume it's the same function in each?

OK, thanks, I guess that makes sense. For static inline. I wonder if extern inline' or plain old inline' should change it.

It's one of those things I hope I never need to know about, but perhaps we do somewhere have static storage in an inline. Wouldn't surprise me, and I bet that if we do, it's a bug.

Quoted 22 lines · * Andrew Morton ([email protected]) wrote:

Quoted 19 lines · On Fri, 07 Nov 2008 17:10:00 +0000 David Howells <[email protected]> wrote:

Quoted 8 lines · Andrew Morton

I'd expect it to behave in the same way as it would if the function was implemented out-of-line.

But it occurs to me that the modrobe-doesnt-work thing would happen if the function _is_ inlined anyway, so we won't be doing that.

Whatever. Killing this many puppies because gcc may do something so bizarrely wrong isn't justifiable.

With gcc, you get one instance of the static variable from inside a static (inline or outofline) function per .o file that invokes it, and these do not merge even though they're common symbols. I asked around and the opinion seems to be that this is correct C. I suppose it's the equivalent of cutting and pasting a function between several files - why should the compiler assume it's the same function in each?

Quoted 6 lines

OK, thanks, I guess that makes sense. For static inline. I wonder if extern inline' or plain old inline' should change it.

It's one of those things I hope I never need to know about, but perhaps we do somewhere have static storage in an inline. Wouldn't surprise me, and I bet that if we do, it's a bug.

Tracepoints actually use that.

It could be changed so they use :

DECLARE_TRACE() (in include/trace/group.h) DEFINE_TRACE() (in the appropriate kernel c file) trace_somename(); (in the code)

instead. That would actually make more sense and remove the need for multiple declarations when the same tracepoint name is used in many spots (this is a problem kmemtrace has, it generates a lot of tracepoint declarations).

Quoted 4 lines · On Fri, 7 Nov 2008 13:00:41 -0500 Mathieu Desnoyers…

Quoted 3 lines

It's one of those things I hope I never need to know about, but perhaps we do somewhere have static storage in an inline. Wouldn't surprise me, and I bet that if we do, it's a bug.

Quoted 1 line

Tracepoints actually use that.

Referring to include/linux/tracepoint.h:DEFINE_TRACE()?

It does look a bit fragile. Does every .c file which included include/trace/block.h get a copy of __tracepoint_block_rq_issue, whether or not it used that tracepoint? Hopefully not.

Quoted 10 lines

It could be changed so they use :

DECLARE_TRACE() (in include/trace/group.h) DEFINE_TRACE() (in the appropriate kernel c file) trace_somename(); (in the code)

instead. That would actually make more sense and remove the need for multiple declarations when the same tracepoint name is used in many spots (this is a problem kmemtrace has, it generates a lot of tracepoint declarations).

Quoted 6 lines · Andrew Morton

Quoted 4 lines · On Fri, 7 Nov 2008 13:00:41 -0500 Mathieu Desnoyers…

Quoted 3 lines

It's one of those things I hope I never need to know about, but perhaps we do somewhere have static storage in an inline. Wouldn't surprise me, and I bet that if we do, it's a bug.

Quoted 18 lines

Quoted 1 line

Tracepoints actually use that.

Referring to include/linux/tracepoint.h:DEFINE_TRACE()?

It does look a bit fragile. Does every .c file which included include/trace/block.h get a copy of __tracepoint_block_rq_issue, whether or not it used that tracepoint? Hopefully not.

Quoted 10 lines

It could be changed so they use :

DECLARE_TRACE() (in include/trace/group.h) DEFINE_TRACE() (in the appropriate kernel c file) trace_somename(); (in the code)

instead. That would actually make more sense and remove the need for multiple declarations when the same tracepoint name is used in many spots (this is a problem kmemtrace has, it generates a lot of tracepoint declarations).

Could this scheme also help with the thousands of sparse warnings that kmemtrace produces because of the current arrangement, all of the form:

include/linux/kmemtrace.h:33:2: warning: Initializer entry defined twice
include/linux/kmemtrace.h:33:2: also defined here

As you could have unique names for the tracepoints now, rather than the 'unique' static storage? Or am I off-base here?

Harvey

Quoted 30 lines · On Fri, 7 Nov 2008 13:00:41 -0500 Mathieu Desnoyers…

Quoted 28 lines · * Andrew Morton ([email protected]) wrote:

Quoted 12 lines · On Fri, 07 Nov 2008 17:10:00 +0000 David Howells <[email protected]> wrote:

Quoted 8 lines · Andrew Morton

I'd expect it to behave in the same way as it would if the function was implemented out-of-line.

But it occurs to me that the modrobe-doesnt-work thing would happen if the function _is_ inlined anyway, so we won't be doing that.

Whatever. Killing this many puppies because gcc may do something so bizarrely wrong isn't justifiable.

Quoted 7 lines

With gcc, you get one instance of the static variable from inside a static (inline or outofline) function per .o file that invokes it, and these do not merge even though they're common symbols. I asked around and the opinion seems to be that this is correct C. I suppose it's the equivalent of cutting and pasting a function between several files - why should the compiler assume it's the same function in each?

OK, thanks, I guess that makes sense. For static inline. I wonder if extern inline' or plain old inline' should change it.

It's one of those things I hope I never need to know about, but perhaps we do somewhere have static storage in an inline. Wouldn't surprise me, and I bet that if we do, it's a bug.

Quoted 1 line

Tracepoints actually use that.

Referring to include/linux/tracepoint.h:DEFINE_TRACE()?

It does look a bit fragile. Does every .c file which included include/trace/block.h get a copy of __tracepoint_block_rq_issue, whether or not it used that tracepoint? Hopefully not.

Quoted 10 lines

It could be changed so they use :

DECLARE_TRACE() (in include/trace/group.h) DEFINE_TRACE() (in the appropriate kernel c file) trace_somename(); (in the code)

instead. That would actually make more sense and remove the need for multiple declarations when the same tracepoint name is used in many spots (this is a problem kmemtrace has, it generates a lot of tracepoint declarations).

I'm unsure of the requirements here. Do you _want_ each call to trace_block_rq_issue() to share some in-memory state? If so then yes, there's a problem with calls to trace_block_rq_issue() from within separate compilation units.

otoh, if all calls to trace_block_rq_issue() are supposed to have independent state (which seems to be the case) then that could be addressed by making trace_block_rq_issue() a macro which defines static storage, as cnt32_to_63() shouldn't have done ;)

Referring to include/linux/tracepoint.h:DEFINE_TRACE()?

It does look a bit fragile. Does every .c file which included include/trace/block.h get a copy of __tracepoint_block_rq_issue, whether or not it used that tracepoint? Hopefully not.

Quoted 6 lines · Andrew Morton

Referring to include/linux/tracepoint.h:DEFINE_TRACE()?

It does look a bit fragile. Does every .c file which included include/trace/block.h get a copy of __tracepoint_block_rq_issue, whether or not it used that tracepoint? Hopefully not.

Look at "ratelimit()" too. Broken, broken.

Of course, I don't think it's
actually _used_ anywhere, so..

Quoted 4 lines · On Fri, 07 Nov 2008 10:01:01 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 2 lines · David Howells

Andrew Morton <[email protected]> wrote:

Quoted 5 lines

Quoted 3 lines

Quoted 3 lines

As I said in the text which you deleted and ignored, this would be better if it was implemented as a C function which requires that the caller explicitly pass in a reference to the state storage.

The whole purpose of that thing is to be utterly fast and lightweight.

Well I'm glad it wasn't designed to demonstrate tastefulness.

btw, do you know how damned irritating and frustrating it is for a code reviewer to have his comments deliberately ignored and deleted in replies?

Quoted 2 lines

Having an out of line C call would trash the major advantage of this code.

Not really.

Quoted 4 lines

Quoted 1 line

I imagine this would compile pretty much the same as the macro.

Depends. As everybody has noticed now, the read ordering is important, and if gcc decides to not inline this

If gcc did that then it would need to generate static instances of inlined functions within individual compilation units. It would be a disaster for the kernel. For a start, functions which are "inlined" in kernel modules wouldn't be able to access their static storage and modprobing them would fail.

Quoted 2 lines

for whatever reason then the
ordering is lost.

Uninlining won't affect any ordering I can see.

Quoted 9 lines

This is why this was a macro to start with.

Quoted 2 lines

I think it
would make it more obvious about the independence of the storage.

I don't think having the associated storage be outside the macro make any sense either. There is simply no valid reason for having it shared between multiple invokations of the macro, as well as making its interface more complex for no gain.

oh god.

Quoted 6 lines

Quoted 2 lines

Alternatively, perhaps Nicolas just needs to mention this in the comment more clearly.

I wrote that code so to me it is cristal clear already. Any suggestions as to how this could be improved?

Does mn10300's get_cycles() really count backwards? The first two callsites I looked at (crypto/tcrypt.c and fs/ext4/mballoc.c) assume that it is an upcounter.

Quoted 1 line

Well I'm glad it wasn't designed to demonstrate tastefulness.

Fast tricks aren't always meant to be beautiful. That,s why we have abstraction layers.

I know nothing about mn10300.

Quoted 3 lines

btw, do you know how damned irritating and frustrating it is for a code reviewer to have his comments deliberately ignored and deleted in replies?

Do you know how irritating and frustrating it is when reviewers don't care reading the damn comments along with the code?

Quoted 6 lines · On Fri, 07 Nov 2008 11:47:47 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 3 lines

btw, do you know how damned irritating and frustrating it is for a code reviewer to have his comments deliberately ignored and deleted in replies?

Do you know how irritating and frustrating it is when reviewers don't care reading the damn comments along with the code?

As you still seek to ignore it, I shall repeat my earlier question. Please do not delete it again.

It apparently tries to avoid races via ordering tricks, as long as it is called with sufficient frequency. But nothing guarantees that it _is_ called sufficiently frequently?

Things like tickless kernels and SCHED_RR can surely cause sched_clock() to not be called for arbitrary periods.

Userspace cli() will definitely do this, but it is expected to break stuff and is not as legitiate a thing to do.

I'm just giving up on the tastefulness issue.

The whole purpose of that thing is to be utterly fast and lightweight. Having an out of line C call would trash the major advantage of this code.

Quoted 1 line

I imagine this would compile pretty much the same as the macro.

Depends. As everybody has noticed now, the read ordering is important, and if gcc decides to not inline this for whatever reason then the ordering is lost. This is why this was a macro to start with.

I don't think having the associated storage be outside the macro make any sense either.

Quoted 2 lines

Alternatively, perhaps Nicolas just needs to mention this in the comment more clearly.

I wrote that code so to me it is cristal clear already. Any suggestions as to how this could be improved?

Quoted 2 lines · Andrew Morton

We have a macro which must only have a single usage in any particular kernel build (and nothing to detect a violation of that).

That's not true. It's a macro containing a _static_ local variable, therefore the macro may be used multiple times, and each time it's used the compiler will allocate a new piece of storage.

Quoted 3 lines

It apparently tries to avoid races via ordering tricks, as long as it is called with sufficient frequency. But nothing guarantees that it _is_ called sufficiently frequently?

The comment attached to it clearly states this restriction. Therefore the caller must guarantee it. That is something Mathieu's code and my code must deal with, not Nicolas's.

Quoted 3 lines

There is absolutely no reason why the first two of these quite bad things needed to be done. In fact there is no reason why it needed to be implemented as a macro at all.

There's a very good reason to implement it as either a macro or an inline
function: it's faster. Moving the whole thing out of line would impose an additional function call overhead - with a 64-bit return value on 32-bit platforms. For my case - sched_clock() - I'm willing to burn a bit of extra space to get the extra speed.

Quoted 3 lines

As I said in the text which you deleted and ignored, this would be better if it was implemented as a C function which requires that the caller explicitly pass in a reference to the state storage.

I'd be quite happy if it was:

	static inline u64 cnt32_to_63(u32 cnt_lo, u32 *__m_cnt_hi)
	{
		union cnt32_to_63 __x;
		__x.hi = *__m_cnt_hi;
		__x.lo = cnt_lo;
		if (unlikely((s32)(__x.hi ^ __x.lo) < 0))
			*__m_cnt_hi =
				__x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31);
		return __x.val;
	}

I imagine this would compile pretty much the same as the macro. I think it would make it more obvious about the independence of the storage.

Alternatively, perhaps Nicolas just needs to mention this in the comment more clearly.

David

First off, using this macro with get_cycles() is simply buggy, because the macro expects _perfect_ order of timestamps, no skew whatsoever, or otherwise time could jump.

	__x.lo = readl(cnt_lo); /* mmio read */

Quoted 3 lines · Mathieu Desnoyers

First off, using this macro with get_cycles() is simply buggy, because the macro expects _perfect_ order of timestamps, no skew whatsoever, or otherwise time could jump.

Erm... Why can't I pass it get_cycles()? Are you saying that sched_clock() in MN10300 is wrong for it's use of get_cycles() with cnt32_to_63()?

Quoted 1 line

	__x.lo = readl(cnt_lo); /* mmio read */

readl() might insert an extra barrier instruction. Not only that, io_addr must be unsigned long.

David

Yes. Do you think the synchronization of the cycles counters is _perfect_ across CPUs so that there is no possible way whatsoever that two cycle counter values appear to go backward between CPUs ? (also taking in account delays in __m_cnt_hi write-back...)

If we expect the only correct use-case to be with readl(), I don't see the problem with added synchronization.

But any get_cycles() user of cnt32_to_63() should be shot down. The bright side is : there is no way get_cycles() can be used with this new code. :)

e.g. of incorrect users for arm (unless they are UP only, but that seems like a weird design argument) :

mach-sa1100/include/mach/SA-1100.h:#define OSCR __REG(0x90000010)
/* OS timer Counter Reg. */
mach-sa1100/generic.c: unsigned long long v = cnt32_to_63(OSCR);
mach-pxa/include/mach/pxa-regs.h:#define OSCR __REG(0x40A00010) /* OS
Timer Counter Register */
mach-pxa/time.c: unsigned long long v = cnt32_to_63(OSCR);

Quoted 7 lines · Mathieu Desnoyers

But any get_cycles() user of cnt32_to_63() should be shot down. The bright side is : there is no way get_cycles() can be used with this new code. :)

e.g. of incorrect users for arm (unless they are UP only, but that seems like a weird design argument) :

Quoted 6 lines

mach-sa1100/include/mach/SA-1100.h:#define OSCR __REG(0x90000010)
/* OS timer Counter Reg. */
mach-sa1100/generic.c: unsigned long long v = cnt32_to_63(OSCR);
mach-pxa/include/mach/pxa-regs.h:#define OSCR __REG(0x40A00010) /* OS
Timer Counter Register */
mach-pxa/time.c: unsigned long long v = cnt32_to_63(OSCR);

It's strange for you to make that assertion when PXA was the exact platform that Nicolas created this code for - and that's a platform where preempt has been widely used.

The two you mention are both ARMv5 or older architectures, and the first real SMP ARM architecture is ARMv6. So architecturally they are UP only.

So, tell me why you say "unless they are UP only, but that seems like a weird design argument"? If the platforms can only ever be UP only, what's wrong with UP only code being used with them? (Not that I'm saying anything there about cnt32_to_63.)

I'd like to see you modify the silicon of a PXA or SA11x0 SoC to add more than one processor to the chip - maybe you could use evostick to glue two dies together and a microscope to aid bonding wires between the two? (Of course, you'd need to design something to ensure cache coherence as well, and arbitrate the internal bus between the two dies.) ;)

Personally, I think that's highly unlikely.

Signature · 3 lines

Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:

Quoted 19 lines · * Russell King ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

But any get_cycles() user of cnt32_to_63() should be shot down. The bright side is : there is no way get_cycles() can be used with this new code. :)

e.g. of incorrect users for arm (unless they are UP only, but that seems like a weird design argument) :

Quoted 6 lines

mach-sa1100/include/mach/SA-1100.h:#define OSCR __REG(0x90000010)
/* OS timer Counter Reg. */
mach-sa1100/generic.c: unsigned long long v = cnt32_to_63(OSCR);
mach-pxa/include/mach/pxa-regs.h:#define OSCR __REG(0x40A00010) /* OS
Timer Counter Register */
mach-pxa/time.c: unsigned long long v = cnt32_to_63(OSCR);

It's strange for you to make that assertion when PXA was the exact platform that Nicolas created this code for - and that's a platform where preempt has been widely used.

Quoted 3 lines

The two you mention are both ARMv5 or older architectures, and the first real SMP ARM architecture is ARMv6. So architecturally they are UP only.

Ok. And hopefully they do not execute instructions speculatively ?

Because then a instruction sync would be required between the __m_hi_cnt read and get_cycles.

If you design such stuff with portability in mind, you'd use per-cpu variables, which ends up being a single variable in the single-cpu special-case.

Quoted 4 lines

So, tell me why you say "unless they are UP only, but that seems like a weird design argument"? If the platforms can only ever be UP only, what's wrong with UP only code being used with them? (Not that I'm saying anything there about cnt32_to_63.)

That's fine, as long as the code does not end up in include/linux and stays in arch/arm/up-only-subarch/.

When one try to create architecture agnostic code (which is what is likely to be palatable to arch agnostic headers), designing with UP in mind does not make much sense.

Quoted 20 lines · Mathieu Desnoyers

Quoted 19 lines · * Russell King ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

But any get_cycles() user of cnt32_to_63() should be shot down. The bright side is : there is no way get_cycles() can be used with this new code. :)

e.g. of incorrect users for arm (unless they are UP only, but that seems like a weird design argument) :

Quoted 6 lines

mach-sa1100/include/mach/SA-1100.h:#define OSCR __REG(0x90000010)
/* OS timer Counter Reg. */
mach-sa1100/generic.c: unsigned long long v = cnt32_to_63(OSCR);
mach-pxa/include/mach/pxa-regs.h:#define OSCR __REG(0x40A00010) /* OS
Timer Counter Register */
mach-pxa/time.c: unsigned long long v = cnt32_to_63(OSCR);

It's strange for you to make that assertion when PXA was the exact platform that Nicolas created this code for - and that's a platform where preempt has been widely used.

Quoted 5 lines

Quoted 3 lines

The two you mention are both ARMv5 or older architectures, and the first real SMP ARM architecture is ARMv6. So architecturally they are UP only.

Ok. And hopefully they do not execute instructions speculatively ?

Again, that's ARMv6 and later.

Quoted 2 lines

Because then a instruction sync would be required between the __m_hi_cnt read and get_cycles.

What get_cycles? This is the ARM implementation of get_cycles():

static inline cycles_t get_cycles (void)

{
        return 0;
}

Maybe you're using a name for one thing which means something else to other people? Please don't use confusing vocabulary.

Quoted 3 lines

If you design such stuff with portability in mind, you'd use per-cpu variables, which ends up being a single variable in the single-cpu special-case.

Explain how and why sched_clock(), which is a global time source, should use per-cpu variables.

Quoted 7 lines

Quoted 4 lines

So, tell me why you say "unless they are UP only, but that seems like a weird design argument"? If the platforms can only ever be UP only, what's wrong with UP only code being used with them? (Not that I'm saying anything there about cnt32_to_63.)

That's fine, as long as the code does not end up in include/linux and stays in arch/arm/up-only-subarch/.

Well, that's where it was - private to ARM. Then David Howells came along and unilaterally - and without reference to anyone as far as I can see - moved it to include/linux.

Neither Nicolas, nor me had any idea that it was going to move into include/linux - the first we knew of it was when pulling the change from Linus' tree.

Look, if people in the kernel community can't or won't communicate with others (either through malice, purpose or accident), you can expect this kind of crap to happen.

Quoted 3 lines

When one try to create architecture agnostic code (which is what is likely to be palatable to arch agnostic headers), designing with UP in mind does not make much sense.

It wasn't architecture agnostic code. It was ARM specific. We have a "version control system" which stores "comments" for changes to the kernel tree. Please use it to find out the true story. I'll save you the trouble, here's the commits with full comments:

$ git log include/linux/cnt32_to_63.h
commit b4f151ff899362fec952c45d166252c9912c041f
Author: David Howells <[email protected]>
Date:   Wed Sep 24 17:48:26 2008 +0100

MN10300: Move asm-arm/cnt32_to_63.h to include/linux/

Move asm-arm/cnt32_to_63.h to include/linux/ so that MN10300 can make use of it too.

Signed-off-by David Howells <[email protected]>

Signed-off-by Linus Torvalds <[email protected]>

$ git log -- arch/arm/include/asm/cnt32_to_63.h include/asm-arm/cnt32_to_63.h
commit bc173c5789e1fc6065fd378edc815914b40ee86b
Author: David Howells <[email protected]>
Date:   Fri Sep 26 16:22:58 2008 +0100

ARM: Delete ARM's own cnt32_to_63.h

Delete ARM's own cnt32_to_63.h as the copy in include/linux/ should now be used instead.

Signed-off-by David Howells <[email protected]>

Signed-off-by Linus Torvalds <[email protected]>

commit 4baa9922430662431231ac637adedddbb0cfb2d7

Author: Russell King <[email protected]>
Date:   Sat Aug 2 10:55:55 2008 +0100

[ARM] move include/asm-arm to arch/arm/include/asm

Move platform independent header files to arch/arm/include/asm, leaving those in asm/arch* and asm/plat* alone.

Signed-off-by Russell King <[email protected]>

commit 838ccbc35eae5b44d47724e5f694dbec4a26d269

Author: Nicolas Pitre <[email protected]>
Date:   Mon Dec 4 20:19:31 2006 +0100

[ARM] 3978/1: macro to provide a 63-bit value from a 32-bit hardware counter

This is done in a completely lockless fashion. Bits 0 to 31 of the count are provided by the hardware while bits 32 to 62 are stored in memory. The top bit in memory is used to synchronize with the hardware count half-period. When the top bit of both counters (hardware and in memory) differ then the memory is updated with a new value, incrementing it when the hardware counter wraps around. Because a word store in memory is atomic then the incremented value will always be in synch with the top bit indicating to any potential concurrent reader if the value in memory is up to date or not wrt the needed increment. And any race in updating the value in memory is harmless as the same value would be stored more than once.

Signed-off-by Nicolas Pitre <[email protected]>

Signed-off-by Russell King <[email protected]>

So, stop slinging mud onto Nicolas and me over this. The resulting mess is clearly not our creation.

Signature · 3 lines

Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:

Well, that's where it was - private to ARM. Then David Howells came along and unilaterally - and without reference to anyone as far as I can see - moved it to include/linux.

Neither Nicolas, nor me had any idea that it was going to move into include/linux - the first we knew of it was when pulling the change from Linus' tree.

Look, if people in the kernel community can't or won't communicate with others (either through malice, purpose or accident), you can expect this kind of crap to happen.

Quoted 11 lines · Russell King

Well, that's where it was - private to ARM. Then David Howells came along and unilaterally - and without reference to anyone as far as I can see - moved it to include/linux.

Neither Nicolas, nor me had any idea that it was going to move into include/linux - the first we knew of it was when pulling the change from Linus' tree.

Look, if people in the kernel community can't or won't communicate with others (either through malice, purpose or accident), you can expect this kind of crap to happen.

Excuse me, Russell, but I sent Nicolas an email prior to doing so asking him if he had any objections:

To: Nicolas Pitre <[email protected]>
cc: [email protected]
Subject: Moving asm-arm/cnt32_to_63.h to include/linux/
Date: Thu, 31 Jul 2008 16:04:04 +0100

Hi Nicolas,

Mind if I move include/asm-arm/cnt32_to_63.h to include/linux/?

I need to use it for MN10300.

David

He didn't respond. Not only that, but I copied Nicolas on the patch to make the move and the patch to make MN10300 use it when I submitted it to Linus on the 24th September, so it's not like he didn't have plenty of time. He certainly saw that because he joined in the discussion of the second patch. Furthermore, he could've asked Linus to refuse the patch, or to revert it if it had already gone in.

I suppose I should've cc'd the ARM list too... but why should it adversely affect ARM?

It sounds to me as if the right answer is for it to move back to being an ARM private thing with a MN10300 private copy, rather than it pretending to be something everyone can use.

Quoted 28 lines · David Howells

Quoted 11 lines · Russell King

Well, that's where it was - private to ARM. Then David Howells came along and unilaterally - and without reference to anyone as far as I can see - moved it to include/linux.

Neither Nicolas, nor me had any idea that it was going to move into include/linux - the first we knew of it was when pulling the change from Linus' tree.

Look, if people in the kernel community can't or won't communicate with others (either through malice, purpose or accident), you can expect this kind of crap to happen.

Excuse me, Russell, but I sent Nicolas an email prior to doing so asking him if he had any objections:

To: Nicolas Pitre <[email protected]>
cc: [email protected]
Subject: Moving asm-arm/cnt32_to_63.h to include/linux/
Date: Thu, 31 Jul 2008 16:04:04 +0100

Hi Nicolas,

Mind if I move include/asm-arm/cnt32_to_63.h to include/linux/?

I need to use it for MN10300.

Quoted 8 lines

David

He didn't respond. Not only that, but I copied Nicolas on the patch to make the move and the patch to make MN10300 use it when I submitted it to Linus on the 24th September, so it's not like he didn't have plenty of time. He certainly saw that because he joined in the discussion of the second patch. Furthermore, he could've asked Linus to refuse the patch, or to revert it if it had already gone in.

Quoted 2 lines

I suppose I should've cc'd the ARM list too... but why should it adversely affect ARM?

I take back the "Neither Nicolas" bit but the rest of my comment stands and remains valid.

In light of akpm's demands to know how this got into the kernel, I decided I'd put the story forward, especially as people in this thread are confused about what it was designed for, and making random unfounded claiming that its existing ARM uses are buggy when they aren't.

It sounds to me as if the right answer is for it to move back to being an ARM private thing with a MN10300 private copy, rather than it pretending to be something everyone can use.

I think this is OK if not everyone can use this. The main purpose for this code was to provide much increased accuracy for shed_clock() on processors with only a 32-bit hardware counter.

Given that sched_clock() is already used in contexts where preemption is disabled, I don't mind the addition of a precision to the associated comment mentioning that it must be called at least once per half period of the base counter ***and*** not be preempted away for longer than the half period of the counter minus the longest period between two calls. The comment already mention a kernel timer which can be used to control the longest period between two calls. Implicit disabling of preemption is _NOT_ the goal of this code.

I also don't mind having a real barrier for this code to be useful on other platforms. On the platform this was written for, any kind of barrier is defined as a compiler barrier which is perfectly fine and achieve the same effect as the current usage of volatile.

Currently, all existing users of cnt32_to_63() are fine since the CPU architectures where it is used don't do read access reordering, and user mode preemption is disabled already. It is nevertheless a good idea to better elaborate usage requirements wrt preemption, and use an explicit memory barrier for proper results on CPUs that may perform instruction reordering.

Signed-off-by Nicolas Pitre <[email protected]>

---

Quoted 13 lines · Nicolas Pitre

I think this is OK if not everyone can use this. The main purpose for this code was to provide much increased accuracy for shed_clock() on processors with only a 32-bit hardware counter.

Given that sched_clock() is already used in contexts where preemption is disabled, I don't mind the addition of a precision to the associated comment mentioning that it must be called at least once per half period of the base counter ***and*** not be preempted away for longer than the half period of the counter minus the longest period between two calls. The comment already mention a kernel timer which can be used to control the longest period between two calls. Implicit disabling of preemption is _NOT_ the goal of this code.

Quoted 4 lines

I also don't mind having a real barrier for this code to be useful on other platforms. On the platform this was written for, any kind of barrier is defined as a compiler barrier which is perfectly fine and achieve the same effect as the current usage of volatile.

So here it is.

I used a rmb() so this is also safe for mixed usages in and out of interrupt context. On the architecture I care about this is turned into a simple compiler barrier and therefore doesn't make a difference, while smp_rmb() is a noop which isn't right.

I won't make a per_cpu_cnt32_to_63() version myself as I have no need for that. But if someone wants to use this witha per CPU counter which is not coherent between CPUs then be my guest. The usage requirements would be the same but on each used CPU instead of globally.

include/linux/cnt32_to_63.h +15 -6

index 8c0f950..584289d 100644
@@ -53,11 +53,19 @@ union cnt32_to_63 {
  * needed increment.  And any race in updating the value in memory is harmless
  * as the same value would simply be stored more than once.
  *
- * The only restriction for the algorithm to work properly is that this
- * code must be executed at least once per each half period of the 32-bit
- * counter to properly update the state bit in memory. This is usually not a
- * problem in practice, but if it is then a kernel timer could be scheduled
- * to manage for this code to be executed often enough.
+ * The restrictions for the algorithm to work properly are:
+ *
+ * 1) this code must be called at least once per each half period of the
+ *    32-bit counter;
+ *
+ * 2) this code must not be preempted for a duration longer than the
+ *    32-bit counter half period minus the longest period between two
+ *    calls to this code.
+ *
+ * Those requirements ensure proper update to the state bit in memory.
+ * This is usually not a problem in practice, but if it is then a kernel
+ * timer should be scheduled to manage for this code to be executed often
+ * enough.
  *
  * Note that the top bit (bit 63) in the returned value should be considered
  * as garbage.  It is not cleared here because callers are likely to use a

@@ -68,9 +76,10 @@ union cnt32_to_63 {
  */
 #define cnt32_to_63(cnt_lo) \
 ({ \
-	static volatile u32 __m_cnt_hi; \
+	static u32 __m_cnt_hi; \
 	union cnt32_to_63 __x; \
 	__x.hi = __m_cnt_hi; \
+ 	rmb(); \
 	__x.lo = (cnt_lo); \
 	if (unlikely((s32)(__x.hi ^ __x.lo) < 0)) \
 		__m_cnt_hi = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \

Quoted 5 lines

I used a rmb() so this is also safe for mixed usages in and out of interrupt context. On the architecture I care about this is turned into a simple compiler barrier and therefore doesn't make a difference, while smp_rmb() is a noop which isn't right.

Hum ? smp_rmb() is turned into a compiler barrier on !SMP architectures. Turning it into a NOP would be broken. Actually, ARM defines it as a barrier().

I *think* that smp_rmb() would be enough, supposing the access to memory is done in program order wrt local interrupts in UP. This is basically Steven's question, which has not received any clear answer yet. I'd like to know what others think about it.

Quoted 4 lines · Mathieu Desnoyers

I *think* that smp_rmb() would be enough, supposing the access to memory is done in program order wrt local interrupts in UP. This is basically Steven's question, which has not received any clear answer yet. I'd like to know what others think about it.

In the mean time a pure rmb() is the safest thing to do now. Once we can convince ourselves that out-of-order reads are always rolled back upon the arrival of an interrupt then this could be relaxed.

Quoted 10 lines · Nicolas Pitre

Quoted 4 lines · Mathieu Desnoyers

I *think* that smp_rmb() would be enough, supposing the access to memory is done in program order wrt local interrupts in UP. This is basically Steven's question, which has not received any clear answer yet. I'd like to know what others think about it.

In the mean time a pure rmb() is the safest thing to do now. Once we can convince ourselves that out-of-order reads are always rolled back upon the arrival of an interrupt then this could be relaxed.

After thinking about it some more, a smp_rmb() must be correct.

On UP, that would be completely insane if an exception didn't resume the whole sequence since the CPU cannot presume anything when returning from it.

If the instruction flows says:

READ A
READ B

And speculative execution makes for B to be read before A, and you get an interrupt after B was read but before A was read, then the program counter may only point at READ A upon returning from the exception and B will be read again. Doing otherwise would require the CPU to remember any reordering that it might have performed upon every exceptions which is completely insane.

So smp_rmb() it shall be.

Currently, all existing users of cnt32_to_63() are fine since the CPU architectures where it is used don't do read access reordering, and user mode preemption is disabled already. It is nevertheless a good idea to better elaborate usage requirements wrt preemption, and use an explicit memory barrier on SMP to avoid different CPUs accessing the counter value in the wrong order. On UP a simple compiler barrier is sufficient.

Signed-off-by Nicolas Pitre <[email protected]>

---

include/linux/cnt32_to_63.h +1 -0

 	union cnt32_to_63 __x; \
 	__x.hi = __m_cnt_hi; \
+ 	smp_rmb(); \
 	__x.lo = (cnt_lo); \
 	if (unlikely((s32)(__x.hi ^ __x.lo) < 0)) \
 		__m_cnt_hi = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \

Quoted 11 lines · * Nicolas Pitre ([email protected]) wrote:

Currently, all existing users of cnt32_to_63() are fine since the CPU architectures where it is used don't do read access reordering, and user mode preemption is disabled already. It is nevertheless a good idea to better elaborate usage requirements wrt preemption, and use an explicit memory barrier on SMP to avoid different CPUs accessing the counter value in the wrong order. On UP a simple compiler barrier is sufficient.

Signed-off-by Nicolas Pitre <[email protected]>

---

...

include/linux/cnt32_to_63.h union cnt32_to_63 { · line 80

Quoted 6 lines

include/linux/cnt32_to_63.h +1 -1

@@ -68,9 +77,10 @@ union cnt32_to_63 {
  */
 #define cnt32_to_63(cnt_lo) \
 ({ \
-	static volatile u32 __m_cnt_hi; \
+	static u32 __m_cnt_hi; \

It's important to get the smp_rmb() here, which this patch provides, so consider this patch to be acked-by me. The added documentation is needed too.

But I also think that declaring the static u32 __m_cnt_hi here is counter-intuitive for developers who wish to use it.

I'd recommend letting the declaration be done outside of cnt32_to_63 so the same variable can be passed as parameter to more than one execution site.

Do you really have such instances where multiple call sites are needed? That sounds even more confusing to me than the current model. Better encapsulate the usage of this macro within some function which has a stronger meaning, such as sched_clock(), and call _that_ from multiple sites instead.

Quoted 13 lines · Mathieu Desnoyers

Quoted 11 lines · * Nicolas Pitre ([email protected]) wrote:

Currently, all existing users of cnt32_to_63() are fine since the CPU architectures where it is used don't do read access reordering, and user mode preemption is disabled already. It is nevertheless a good idea to better elaborate usage requirements wrt preemption, and use an explicit memory barrier on SMP to avoid different CPUs accessing the counter value in the wrong order. On UP a simple compiler barrier is sufficient.

Signed-off-by Nicolas Pitre <[email protected]>

---

...

Quoted 10 lines

include/linux/cnt32_to_63.h union cnt32_to_63 { · line 80

Quoted 6 lines

include/linux/cnt32_to_63.h +1 -1

@@ -68,9 +77,10 @@ union cnt32_to_63 {
  */
 #define cnt32_to_63(cnt_lo) \
 ({ \
-	static volatile u32 __m_cnt_hi; \
+	static u32 __m_cnt_hi; \

It's important to get the smp_rmb() here, which this patch provides, so consider this patch to be acked-by me. The added documentation is needed too.

Thanks.

Quoted 2 lines

But I also think that declaring the static u32 __m_cnt_hi here is counter-intuitive for developers who wish to use it.

I'm rather not convinced of that. And this is a much bigger change affecting all callers so I'd defer such change even if I was convinced of it.

Quoted 3 lines

I'd recommend letting the declaration be done outside of cnt32_to_63 so the same variable can be passed as parameter to more than one execution site.

Do you really have such instances where multiple call sites are needed? That sounds even more confusing to me than the current model. Better encapsulate the usage of this macro within some function which has a stronger meaning, such as sched_clock(), and call _that_ from multiple sites instead.

Nicolas

Quoted 5 lines · * Nicolas Pitre ([email protected]) wrote:

Do you really have such instances where multiple call sites are needed? That sounds even more confusing to me than the current model. Better encapsulate the usage of this macro within some function which has a stronger meaning, such as sched_clock(), and call _that_ from multiple sites instead.

I see a few reasons for it :

- If we want to inline the whole read function so we don't pay the extra runtime cost of a function call, this would become required.

- If we want to create a per cpu timer which updates the value periodically without calling the function. We may want to add some WARN_ON or some sanity tests in this periodic update that would not be part of the standard read code. If we don't have access to this variable outside of the macro, this becomes impossible.

Quoted 7 lines · Mathieu Desnoyers

Quoted 5 lines · * Nicolas Pitre ([email protected]) wrote:

Do you really have such instances where multiple call sites are needed? That sounds even more confusing to me than the current model. Better encapsulate the usage of this macro within some function which has a stronger meaning, such as sched_clock(), and call _that_ from multiple sites instead.

Quoted 4 lines

I see a few reasons for it :

- If we want to inline the whole read function so we don't pay the extra runtime cost of a function call, this would become required.

You can inline it as you want as long as it remains in the same .c file. The static variable is still shared amongst all call sites in that case.

Quoted 14 lines · On Sun, 09 Nov 2008 23:20:00 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 11 lines · Mathieu Desnoyers

Quoted 5 lines · * Nicolas Pitre ([email protected]) wrote:

Do you really have such instances where multiple call sites are needed? That sounds even more confusing to me than the current model. Better encapsulate the usage of this macro within some function which has a stronger meaning, such as sched_clock(), and call _that_ from multiple sites instead.

I see a few reasons for it :

- If we want to inline the whole read function so we don't pay the extra runtime cost of a function call, this would become required.

Quoted 2 lines

You can inline it as you want as long as it remains in the same .c file. The static variable is still shared amongst all call sites in that case.

Please don't rely upon deep compiler behaviour like that. It is unobvious to the reader and it might break if someone uses it incorrectly, or if the compiler implementation changes, or if a non-gcc compiler is used, etc.

It is far better to make the management of the state explicit and at the control of the caller. Get the caller to allocate the state and pass its address into this function. Simple, clear, explicit and robust.

Quoted 4 lines

It is far better to make the management of the state explicit and at the control of the caller. Get the caller to allocate the state and pass its address into this function. Simple, clear, explicit and robust.

Sigh... What about this compromize then?

include/linux/cnt32_to_63.h +3 -3

index 7605fdd..74ce767 100644
@@ -32,8 +32,9 @@ union cnt32_to_63 {
 
 
 /**
- * cnt32_to_63 - Expand a 32-bit counter to a 63-bit counter
+ * __cnt32_to_63 - Expand a 32-bit counter to a 63-bit counter
  * @cnt_lo: The low part of the counter
+ * @cnt_hi_p: Pointer to storage for the extended part of the counter
  *
  * Many hardware clock counters are only 32 bits wide and therefore have
  * a relatively short period making wrap-arounds rather frequent.  This

@@ -75,16 +76,31 @@ union cnt32_to_63 {
  * clear-bit instruction. Otherwise caller must remember to clear the top
  * bit explicitly.
  */
-#define cnt32_to_63(cnt_lo) \
+#define __cnt32_to_63(cnt_lo, cnt_hi_p) \
 ({ \
-	static u32 __m_cnt_hi; \

Quoted 30 lines · On Mon, 10 Nov 2008 16:34:54 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 4 lines

It is far better to make the management of the state explicit and at the control of the caller. Get the caller to allocate the state and pass its address into this function. Simple, clear, explicit and robust.

Sigh... What about this compromize then?

include/linux/cnt32_to_63.h +3 -3

index 7605fdd..74ce767 100644
@@ -32,8 +32,9 @@ union cnt32_to_63 {
 
 
 /**
- * cnt32_to_63 - Expand a 32-bit counter to a 63-bit counter
+ * __cnt32_to_63 - Expand a 32-bit counter to a 63-bit counter
  * @cnt_lo: The low part of the counter
+ * @cnt_hi_p: Pointer to storage for the extended part of the counter
  *
  * Many hardware clock counters are only 32 bits wide and therefore have
  * a relatively short period making wrap-arounds rather frequent.  This

@@ -75,16 +76,31 @@ union cnt32_to_63 {
  * clear-bit instruction. Otherwise caller must remember to clear the top
  * bit explicitly.
  */
-#define cnt32_to_63(cnt_lo) \
+#define __cnt32_to_63(cnt_lo, cnt_hi_p) \
 ({ \
-	static u32 __m_cnt_hi; \

include/linux/cnt32_to_63.h union cnt32_to_63 { · line 88

Quoted 10 lines

include/linux/cnt32_to_63.h +2 -2

 	union cnt32_to_63 __x; \
-	__x.hi = __m_cnt_hi; \
+	__x.hi = *(cnt_hi_p); \
  	smp_rmb(); \
 	__x.lo = (cnt_lo); \
 	if (unlikely((s32)(__x.hi ^ __x.lo) < 0)) \
-		__m_cnt_hi = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \
+		*(cnt_hi_p) = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \
 	__x.val; \
 })

This references its second argument twice, which can cause correctness or efficiency problems.

There is no reason that this had to be implemented in cpp. Implementing it in C will fix the above problem.

Quoted 47 lines · Andrew Morton

Quoted 30 lines · On Mon, 10 Nov 2008 16:34:54 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 4 lines

It is far better to make the management of the state explicit and at the control of the caller. Get the caller to allocate the state and pass its address into this function. Simple, clear, explicit and robust.

Sigh... What about this compromize then?

include/linux/cnt32_to_63.h +3 -3

index 7605fdd..74ce767 100644
@@ -32,8 +32,9 @@ union cnt32_to_63 {
 
 
 /**
- * cnt32_to_63 - Expand a 32-bit counter to a 63-bit counter
+ * __cnt32_to_63 - Expand a 32-bit counter to a 63-bit counter
  * @cnt_lo: The low part of the counter
+ * @cnt_hi_p: Pointer to storage for the extended part of the counter
  *
  * Many hardware clock counters are only 32 bits wide and therefore have
  * a relatively short period making wrap-arounds rather frequent.  This

@@ -75,16 +76,31 @@ union cnt32_to_63 {
  * clear-bit instruction. Otherwise caller must remember to clear the top
  * bit explicitly.
  */
-#define cnt32_to_63(cnt_lo) \
+#define __cnt32_to_63(cnt_lo, cnt_hi_p) \
 ({ \
-	static u32 __m_cnt_hi; \

include/linux/cnt32_to_63.h union cnt32_to_63 { · line 88

Quoted 10 lines

include/linux/cnt32_to_63.h +2 -2

 	union cnt32_to_63 __x; \
-	__x.hi = __m_cnt_hi; \
+	__x.hi = *(cnt_hi_p); \
  	smp_rmb(); \
 	__x.lo = (cnt_lo); \
 	if (unlikely((s32)(__x.hi ^ __x.lo) < 0)) \
-		__m_cnt_hi = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \
+		*(cnt_hi_p) = __x.hi = (__x.hi ^ 0x80000000) + (__x.hi >> 31); \
 	__x.val; \
 })

This references its second argument twice, which can cause correctness or efficiency problems.

Quoted 2 lines

There is no reason that this had to be implemented in cpp. Implementing it in C will fix the above problem.

No, it won't, for correctness and efficiency reasons.

And I've explained why already.

Quoted 7 lines · On Mon, 10 Nov 2008 18:15:32 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 6 lines

This references its second argument twice, which can cause correctness or efficiency problems.

There is no reason that this had to be implemented in cpp. Implementing it in C will fix the above problem.

Quoted 3 lines

No, it won't, for correctness and efficiency reasons.

And I've explained why already.

I'd be very surprised if you've really found a case where a macro is faster than an inlined function. I don't think that has happened before.

Quoted 8 lines · On Mon, 10 Nov 2008 18:15:32 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 5 lines · Andrew Morton

This references its second argument twice, which can cause correctness or efficiency problems.

There is no reason that this had to be implemented in cpp. Implementing it in C will fix the above problem.

Quoted 3 lines

No, it won't, for correctness and efficiency reasons.

And I've explained why already.

I'd be very surprised if you've really found a case where a macro is faster than an inlined function. I don't think that has happened before.

Quoted 11 lines · Andrew Morton

Quoted 8 lines · On Mon, 10 Nov 2008 18:15:32 -0500 (EST) Nicolas Pitre <[email protected]> wrote:

Quoted 5 lines · Andrew Morton

This references its second argument twice, which can cause correctness or efficiency problems.

There is no reason that this had to be implemented in cpp. Implementing it in C will fix the above problem.

Quoted 7 lines

Quoted 3 lines

No, it won't, for correctness and efficiency reasons.

And I've explained why already.

I'd be very surprised if you've really found a case where a macro is faster than an inlined function. I don't think that has happened before.

That hasn't anything to do with "a macro is faster" at all. It's all about the order used to evaluate provided arguments. And the first one might be anything like a memory value, an IO operation, an expression, etc. An inline function would work correctly with pointers only and therefore totally break apart on x86 for example.

Nicolas

Let's see what it gives once implemented. Only compile-tested. Assumes pxa, sa110 and mn10300 are all UP-only. Correct smp_rmb() are used for arm versatile.

Quoted 3 lines · Mathieu Desnoyers

Let's see what it gives once implemented. Only compile-tested. Assumes pxa, sa110 and mn10300 are all UP-only. Correct smp_rmb() are used for arm versatile.

Versatile is also UP only.

The following are results from PXA built with gcc 3.4.3:

1. two additional registers used in sched_clock()
2. 8 additional bytes of code (which are needless if gcc was more inteligent)

both of these I put down to inefficiencies in gcc's register allocation.

3. worse instruction scheduling - two inter-dependent loads next to each other causing a pipeline stall

Actual reading of variables/hardware is unaffected by this patch.

Old code:

   c:   e59f3050        ldr     r3, [pc, #80]   ; load address of oscr2ns_scale
  10:   e59fc050        ldr     ip, [pc, #80]   ; load address of __m_cnt_hi
  14:   e5932000        ldr     r2, [r3]	; read oscr2ns_scale
  18:   e59f304c        ldr     r3, [pc, #76]   ; load address of OSCR
  1c:   e59c1000        ldr     r1, [ip]	; read __m_cnt_hi
  20:   e1a07002        mov     r7, r2
  24:   e3a08000        mov     r8, #0  ; 0x0
  28:   e5933000        ldr     r3, [r3]	; read OSCR register
...
  58:   e1820b04        orr     r0, r2, r4, lsl #22
  5c:   e1a01524        lsr     r1, r4, #10
  60:   e89da9f0        ldm     sp, {r4, r5, r6, r7, r8, fp, sp, pc}

New code:

   c:   e59f0058        ldr     r0, [pc, #88]   ; load address of oscr2ns_scale
  10:   e5901000        ldr     r1, [r0]	; read oscr2ns_scale <= pipeline stall
  14:   e59f3054        ldr     r3, [pc, #84]   ; load address of __m_cnt_hi
  18:   e1a08001        mov     r8, r1
  1c:   e5932000        ldr     r2, [r3]	; read __m_cnt_hi
  20:   e59f304c        ldr     r3, [pc, #76]   ; load address of OSCR
  24:   e1a09002        mov     r9, r2
  28:   e3a0a000        mov     sl, #0  ; 0x0
  2c:   e5933000        ldr     r3, [r3]	; read OSCR
...
  58:   e1825b04        orr     r5, r2, r4, lsl #22
  5c:   e1a06524        lsr     r6, r4, #10
  60:   e1a01006        mov     r1, r6
  64:   e1a00005        mov     r0, r5
  68:   e89daff0        ldm     sp, {r4, r5, r6, r7, r8, r9, sl, fp, sp, pc}

Versatile:

1. 12 additional bytes of code
2. same number of registers
3. worse instruction scheduling causing pipeline stall

Actual reading of variables/hardware is unaffected by this patch.

So, we have two platforms where this patch makes things visibly worse with no material benefit.

I think the added barrier() are causing these pipeline stalls. They don't allow the compiler to read variables such as oscr2ns_scale before the barrier because gcc cannot assume it won't be modified. However, to insure that OSCR read is done after __m_cnt_hi read, this barrier seems required to be safe against gcc optimizations.

Have you compared my patch to Nicolas'patch, which adds a smp_rmb() in the macro or to a vanilla tree ?

Quoted 8 lines · Mathieu Desnoyers

I think the added barrier() are causing these pipeline stalls. They don't allow the compiler to read variables such as oscr2ns_scale before the barrier because gcc cannot assume it won't be modified. However, to insure that OSCR read is done after __m_cnt_hi read, this barrier seems required to be safe against gcc optimizations.

Have you compared my patch to Nicolas'patch, which adds a smp_rmb() in the macro or to a vanilla tree ?

Nicolas' patch compared to unmodified - there's less side effects, which come down to two pipeline stalls whereas we had none with the unmodified code.

One pipeline stall for loading the address of __m_cnt_hi and reading its value, followed by the same thing for oscr2ns_scale.

I think this is showing the problem of compiler barriers - they are indescriminate. They are total and complete barriers - not only do they act on the data but also the compilers ability to emit code for generating the addresses of the data to be loaded.

Clearly, the address of OSCR, __m_cnt_hi nor oscr2ns_scale is ever going to change at run time - their addresses are all stored in the literal pool, but by putting compiler barriers in, the compiler is being prevented from reading from the literal pool at the most appropriate point.

So, I've tried this:

unsigned long long sched_clock(void)
{

(quoted diff) +2 -1

+       unsigned long *oscr2ns_ptr = &oscr2ns_scale;
        unsigned long long v = cnt32_to_63(OSCR);
-       return (v * oscr2ns_scale) >> OSCR2NS_SCALE_FACTOR;
+       return (v * *oscr2ns_ptr) >> OSCR2NS_SCALE_FACTOR;
 }

to try to explicitly code the loads. This unfortunately results in three pipeline stalls. Also tried swapping the two lines starting 'unsigned long' without any improvement on not having those extra hacks to work around the barrier.

So, let's summarise this:

1. the existing code works, is correct on ARM, and is efficient.
2. throwing barriers into the function makes it less efficient.
3. re-engineering the code appears to make things worse.

Quoted 8 lines · * Nicolas Pitre ([email protected]) wrote:

That hasn't anything to do with "a macro is faster" at all. It's all about the order used to evaluate provided arguments. And the first one might be anything like a memory value, an IO operation, an expression, etc. An inline function would work correctly with pointers only and therefore totally break apart on x86 for example.

Nicolas

Let's see what it gives once implemented. Only compile-tested. Assumes pxa, sa110 and mn10300 are all UP-only. Correct smp_rmb() are used for arm versatile.

Turn cnt32_to_63 into an inline function.
Change all callers to new API.
Document barrier usage.

No thank you. If this trend continues I'm going to make it back private to ARM again so you could pessimize your own code as much as you want.

Review unsigned long long sched_clock(void)

Quoted 3 lines · Mathieu Desnoyers

(quoted diff) +1 -0

@@ -52,18 +57,22 @@ unsigned long long sched_clock(void)
...
+	preempt_disable_notrace();

Please, no! sched_clock() is called with preemption or interrupts disabled everywhere except from some debugging code (lock tracing IIRC). If you need to insert this preemption disablement somewhere, please insert it there. At least then sched_clock() will be called consistently.

Quoted 10 lines · David Howells

Review unsigned long long sched_clock(void)

Quoted 3 lines · Mathieu Desnoyers

(quoted diff) +1 -0

@@ -52,18 +57,22 @@ unsigned long long sched_clock(void)
...
+	preempt_disable_notrace();

Please, no! sched_clock() is called with preemption or interrupts disabled everywhere except from some debugging code (lock tracing IIRC). If you need to insert this preemption disablement somewhere, please insert it there. At least then sched_clock() will be called consistently.

Agreed. You could do a WARN_ON(!in_atomic); in sched_clock() depending on DEBUG_PREEMPT or something to ensure this.

Quoted 4 lines

I mean, the darned thing is called from sched_clock(), which can be concurrently called on separate CPUs and which can be called from interrupt context (with an arbitrary nesting level!) while it was running in process context.

Yes! And this is so on *purpose*. Please take some time to read the comment that goes along with it, and if you're still not convinced then look for those explanation emails I've already posted.

Quoted 3 lines

/*
* Caller must provide locking to protect *caller_state */

NO! This is meant to be LOCK FREE!

Quoted 8 lines · Nicolas Pitre

Quoted 4 lines

I mean, the darned thing is called from sched_clock(), which can be concurrently called on separate CPUs and which can be called from interrupt context (with an arbitrary nesting level!) while it was running in process context.

Yes! And this is so on *purpose*. Please take some time to read the comment that goes along with it, and if you're still not convinced then look for those explanation emails I've already posted.

I agree with Nicolas on this. It's abominably clever, but I think he's right.

The one place I remain unconvinced is over the issue of preemption of a process that is in the middle of cnt32_to_63(), where if the preempted process is asleep for long enough, I think it can wind time backwards when it resumes, but that's not a problem for the one place I want to use it (sched_clock()) because that is (almost) always called with preemption disabled in one way or another.

The one place it isn't is a debugging case that I'm not too worried about.

Quoted 5 lines

Quoted 3 lines

/*
* Caller must provide locking to protect *caller_state */

NO! This is meant to be LOCK FREE!

Absolutely.

David

Quoted 19 lines · * David Howells ([email protected]) wrote:

Quoted 8 lines · Nicolas Pitre

Quoted 4 lines

I mean, the darned thing is called from sched_clock(), which can be concurrently called on separate CPUs and which can be called from interrupt context (with an arbitrary nesting level!) while it was running in process context.

Yes! And this is so on *purpose*. Please take some time to read the comment that goes along with it, and if you're still not convinced then look for those explanation emails I've already posted.

I agree with Nicolas on this. It's abominably clever, but I think he's right.

The one place I remain unconvinced is over the issue of preemption of a process that is in the middle of cnt32_to_63(), where if the preempted process is asleep for long enough, I think it can wind time backwards when it resumes, but that's not a problem for the one place I want to use it (sched_clock()) because that is (almost) always called with preemption disabled in one way or another.

Quoted 2 lines

The one place it isn't is a debugging case that I'm not too worried about.

I am also concerned about the non-preemption off case.

Then I think the function should document that it must be called with preempt disabled.

I explained several times already why I disagree. Preemption is not a problem unless you're preempted away for long enough, or IOW if your counter is too fast.

I mean, the darned thing is called from sched_clock(), which can be concurrently called on separate CPUs and which can be called from interrupt context (with an arbitrary nesting level!) while it was running in process context.

Who let that thing into Linux?

Assume the time source is a global clock which insures that time will never *ever* go backward. Use a smp_rmb() to make sure the cnt_lo value is read before __m_cnt_hi.

Quoted 3 lines · Mathieu Desnoyers

Assume the time source is a global clock which insures that time will never *ever* go backward. Use a smp_rmb() to make sure the cnt_lo value is read before __m_cnt_hi.

If you have an smp_rmb(), then don't you need an smp_wmb()/smp_mb() to match it to make it work? And is your assumption valid that smp_rmb() will affect memory vs the I/O access to read the clock? There's no requirement that cnt_lo will have been read from an MMIO location at all.

David

__m_cnt_hi
is read before
mmio cnt_lo read

for the detailed reasons explained in my previous discussion with Nicolas here :
http://lkml.org/lkml/2008/10/21/1

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

The write side is between the hardware counter, which is assumed to increment monotonically between each read, and the value __m_cnt_hi updated by the CPU. I don't see where we could put a wmb() there.

Without barrier, the smp race looks as follow :

CPU A B

                                            read hw cnt low (0xFFFFFFFA)
       read __m_cnt_hi (0x80000000)
       read hw cnt low (0x00000001)
       (wrap detected :
        (s32)(0x80000000 ^ 0x1) < 0)
       write __m_cnt_hi = 0x00000001
                                            read __m_cnt_hi (0x00000001)
       return 0x0000000100000001
                                            (wrap detected :
                                             (s32)(0x00000001 ^ 0xFFFFFFFA) < 0)
                                            write __m_cnt_hi = 0x80000001
                                            return 0x80000001FFFFFFFA
                                                                  (time jumps)

And UP interrupt race :

       Thread context                       Interrupts
       read hw cnt low (0xFFFFFFFA)
                                            read __m_cnt_hi (0x80000000)
                                            read hw cnt low (0x00000001)
                                            (wrap detected :
                                             (s32)(0x80000000 ^ 0x1) < 0)
                                            write __m_cnt_hi = 0x00000001
       read __m_cnt_hi (0x00000001)
                                            return 0x0000000100000001
       (wrap detected :
        (s32)(0x00000001 ^ 0xFFFFFFFA) < 0)
       write __m_cnt_hi = 0x80000001
       return 0x80000001FFFFFFFA
                (time jumps)

Quoted 9 lines · Mathieu Desnoyers

__m_cnt_hi
is read before
mmio cnt_lo read

for the detailed reasons explained in my previous discussion with Nicolas here :
http://lkml.org/lkml/2008/10/21/1

Quoted 2 lines

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

-- Steve

Quoted 40 lines

The write side is between the hardware counter, which is assumed to increment monotonically between each read, and the value __m_cnt_hi updated by the CPU. I don't see where we could put a wmb() there.

Without barrier, the smp race looks as follow :

CPU A B

                                            read hw cnt low (0xFFFFFFFA)
       read __m_cnt_hi (0x80000000)
       read hw cnt low (0x00000001)
       (wrap detected :
        (s32)(0x80000000 ^ 0x1) < 0)
       write __m_cnt_hi = 0x00000001
                                            read __m_cnt_hi (0x00000001)
       return 0x0000000100000001
                                            (wrap detected :
                                             (s32)(0x00000001 ^ 0xFFFFFFFA) < 0)
                                            write __m_cnt_hi = 0x80000001
                                            return 0x80000001FFFFFFFA
                                                                  (time jumps)

And UP interrupt race :

       Thread context                       Interrupts
       read hw cnt low (0xFFFFFFFA)
                                            read __m_cnt_hi (0x80000000)
                                            read hw cnt low (0x00000001)
                                            (wrap detected :
                                             (s32)(0x80000000 ^ 0x1) < 0)
                                            write __m_cnt_hi = 0x00000001
       read __m_cnt_hi (0x00000001)
                                            return 0x0000000100000001
       (wrap detected :
        (s32)(0x00000001 ^ 0xFFFFFFFA) < 0)
       write __m_cnt_hi = 0x80000001
       return 0x80000001FFFFFFFA
                (time jumps)

Quoted 14 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 11 lines · Mathieu Desnoyers

__m_cnt_hi
is read before
mmio cnt_lo read

for the detailed reasons explained in my previous discussion with Nicolas here :
http://lkml.org/lkml/2008/10/21/1

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

Quoted 3 lines

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

Ah, right, preserving program order on UP should be enough. smp_rmb() then.

Quoted 15 lines · Mathieu Desnoyers

Quoted 14 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 11 lines · Mathieu Desnoyers

__m_cnt_hi
is read before
mmio cnt_lo read

for the detailed reasons explained in my previous discussion with Nicolas here :
http://lkml.org/lkml/2008/10/21/1

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

Quoted 6 lines

Quoted 3 lines

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

Ah, right, preserving program order on UP should be enough. smp_rmb() then.

I'm not quite sure I'm following here. Is this a global hardware clock you're reading from multiple cpus, if so, are you sure smp_rmb() will indeed be enough to sync the read?

(In which case the smp_wmb() is provided by the hardware increasing the clock?)

If these are per-cpu clocks then even in the smp case we'd be good with a plain barrier() because you'd only ever want to read your own cpu's clock (and have a separate __m_cnt_hi per cpu).

Or am I totally missing out on something?

Quoted 28 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 15 lines · Mathieu Desnoyers

Quoted 14 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 11 lines · Mathieu Desnoyers

__m_cnt_hi
is read before
mmio cnt_lo read

for the detailed reasons explained in my previous discussion with Nicolas here :
http://lkml.org/lkml/2008/10/21/1

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

Quoted 6 lines

Quoted 3 lines

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

Ah, right, preserving program order on UP should be enough. smp_rmb() then.

I'm not quite sure I'm following here. Is this a global hardware clock you're reading from multiple cpus, if so, are you sure smp_rmb() will indeed be enough to sync the read?

Quoted 9 lines

(In which case the smp_wmb() is provided by the hardware increasing the clock?)

If these are per-cpu clocks then even in the smp case we'd be good with a plain barrier() because you'd only ever want to read your own cpu's clock (and have a separate __m_cnt_hi per cpu).

Or am I totally missing out on something?

This is the global hardware clock scenario.

We have to order an uncached mmio read wrt a cached variable read/write. The uncached mmio read vs smp_rmb() barrier (e.g. lfence instruction) should be insured by program order because the read will skip the cache and go directly to the bus. Luckily we only do a mmio read and no mmio write, so mmiowb() is not required.

You might be right in that it could require more barriers.

Given adequate program order, we can assume the the mmio read will happen "on the spot", but that the cached read may be delayed.

What we want is :

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

With the two reads in the correct order. If we consider two consecutive executions on the same CPU :

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

We might have to order the read/write pair wrt the following readl, such as :

smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr);
barrier(); /* Make sure the compiler leaves mmio read before cached read */ read __m_cnt_hi
write __m_cnt_hi

smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr)
barrier(); /* Make sure the compiler leaves mmio read before cached read */ read __m_cnt_hi
write __m_cnt_hi

Would that make more sense ?

Mathieu

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Quoted 78 lines · * Mathieu Desnoyers ([email protected]) wrote:

Quoted 28 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 15 lines · Mathieu Desnoyers

Quoted 14 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 11 lines · Mathieu Desnoyers

__m_cnt_hi
is read before
mmio cnt_lo read

for the detailed reasons explained in my previous discussion with Nicolas here :
http://lkml.org/lkml/2008/10/21/1

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

Quoted 6 lines

Quoted 3 lines

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

Ah, right, preserving program order on UP should be enough. smp_rmb() then.

I'm not quite sure I'm following here. Is this a global hardware clock you're reading from multiple cpus, if so, are you sure smp_rmb() will indeed be enough to sync the read?

Quoted 9 lines

(In which case the smp_wmb() is provided by the hardware increasing the clock?)

If these are per-cpu clocks then even in the smp case we'd be good with a plain barrier() because you'd only ever want to read your own cpu's clock (and have a separate __m_cnt_hi per cpu).

Or am I totally missing out on something?

This is the global hardware clock scenario.

We have to order an uncached mmio read wrt a cached variable read/write. The uncached mmio read vs smp_rmb() barrier (e.g. lfence instruction) should be insured by program order because the read will skip the cache and go directly to the bus. Luckily we only do a mmio read and no mmio write, so mmiowb() is not required.

You might be right in that it could require more barriers.

Given adequate program order, we can assume the the mmio read will happen "on the spot", but that the cached read may be delayed.

What we want is :

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

With the two reads in the correct order. If we consider two consecutive executions on the same CPU :

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

We might have to order the read/write pair wrt the following readl, such as :

smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr);
barrier(); /* Make sure the compiler leaves mmio read before cached read */ read __m_cnt_hi
write __m_cnt_hi

Quoted 8 lines

smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr)
barrier(); /* Make sure the compiler leaves mmio read before cached read */ read __m_cnt_hi
write __m_cnt_hi

Would that make more sense ?

Oh, actually, I got things reversed in this email : the readl(io_addr) must be done _after_ the __m_cnt_hi read.

Therefore, two consecutive executions would look like :

barrier(); /* Make sure the compiler does not reorder __m_cnt_hi and
previous mmio read. */
read __m_cnt_hi
smp_rmb(); /* Waits for every cached memory reads to complete */

readl(io_addr);
write __m_cnt_hi

barrier(); /* Make sure the compiler does not reorder __m_cnt_hi and
previous mmio read. */
read __m_cnt_hi
smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr);
write __m_cnt_hi

Mathieu

Quoted 5 lines

Mathieu

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Quoted 8 lines

Quoted 2 lines

Would that make more sense ?

Oh, actually, I got things reversed in this email : the readl(io_addr) must be done _after_ the __m_cnt_hi read.

Therefore, two consecutive executions would look like :

Quoted 4 lines

barrier(); /* Make sure the compiler does not reorder __m_cnt_hi and
previous mmio read. */
read __m_cnt_hi
smp_rmb(); /* Waits for every cached memory reads to complete */

If these are MMIO reads, then you need rmb() rather than smp_rmb(), at least on architectures that can reorder writes (Power, Itanium, and I believe also ARM, ...).

Quoted 8 lines · Paul E. McKenney

Quoted 8 lines

Quoted 2 lines

Would that make more sense ?

Oh, actually, I got things reversed in this email : the readl(io_addr) must be done _after_ the __m_cnt_hi read.

Therefore, two consecutive executions would look like :

Quoted 8 lines

Quoted 4 lines

barrier(); /* Make sure the compiler does not reorder __m_cnt_hi and
previous mmio read. */
read __m_cnt_hi
smp_rmb(); /* Waits for every cached memory reads to complete */

If these are MMIO reads, then you need rmb() rather than smp_rmb(), at least on architectures that can reorder writes (Power, Itanium, and I believe also ARM, ...).

The read is from a clock source. The only writes that are happening is by the clock itself.

On a UP system, is a rmb still needed? That is, can you have two reads on the same CPU from the clock source that will produce a backwards clock? That to me sounds like the clock interface is broken.

Quoted 91 lines · Mathieu Desnoyers

Quoted 78 lines · * Mathieu Desnoyers ([email protected]) wrote:

Quoted 28 lines · * Peter Zijlstra ([email protected]) wrote:

Quoted 15 lines · Mathieu Desnoyers

Quoted 14 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 11 lines · Mathieu Desnoyers

__m_cnt_hi
is read before
mmio cnt_lo read

for the detailed reasons explained in my previous discussion with Nicolas here :
http://lkml.org/lkml/2008/10/21/1

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

Quoted 6 lines

Quoted 3 lines

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

Ah, right, preserving program order on UP should be enough. smp_rmb() then.

I'm not quite sure I'm following here. Is this a global hardware clock you're reading from multiple cpus, if so, are you sure smp_rmb() will indeed be enough to sync the read?

Quoted 9 lines

(In which case the smp_wmb() is provided by the hardware increasing the clock?)

If these are per-cpu clocks then even in the smp case we'd be good with a plain barrier() because you'd only ever want to read your own cpu's clock (and have a separate __m_cnt_hi per cpu).

Or am I totally missing out on something?

This is the global hardware clock scenario.

We have to order an uncached mmio read wrt a cached variable read/write. The uncached mmio read vs smp_rmb() barrier (e.g. lfence instruction) should be insured by program order because the read will skip the cache and go directly to the bus. Luckily we only do a mmio read and no mmio write, so mmiowb() is not required.

You might be right in that it could require more barriers.

Given adequate program order, we can assume the the mmio read will happen "on the spot", but that the cached read may be delayed.

What we want is :

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

With the two reads in the correct order. If we consider two consecutive executions on the same CPU :

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

readl(io_addr)
read __m_cnt_hi
write __m_cnt_hi

We might have to order the read/write pair wrt the following readl, such as :

smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr);
barrier(); /* Make sure the compiler leaves mmio read before cached read */ read __m_cnt_hi
write __m_cnt_hi

Quoted 8 lines

smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr)
barrier(); /* Make sure the compiler leaves mmio read before cached read */ read __m_cnt_hi
write __m_cnt_hi

Would that make more sense ?

Oh, actually, I got things reversed in this email : the readl(io_addr) must be done _after_ the __m_cnt_hi read.

Quoted 6 lines

Therefore, two consecutive executions would look like :

barrier(); /* Make sure the compiler does not reorder __m_cnt_hi and
previous mmio read. */
read __m_cnt_hi
smp_rmb(); /* Waits for every cached memory reads to complete */

If these are MMIO reads, then you need rmb() rather than smp_rmb(), at least on architectures that can reorder writes (Power, Itanium, and I believe also ARM, ...).

Thanx, Paul

Quoted 22 lines

readl(io_addr);
write __m_cnt_hi

barrier(); /* Make sure the compiler does not reorder __m_cnt_hi and
previous mmio read. */
read __m_cnt_hi
smp_rmb(); /* Waits for every cached memory reads to complete */ readl(io_addr);
write __m_cnt_hi

Mathieu

Quoted 5 lines

Mathieu

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Quoted 2 lines

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

Quoted 3 lines · Steven Rostedt

Quoted 2 lines

I use smp_rmb() to do this on SMP systems (hrm, actually, a rmb() could be required so it works also on UP systems safely wrt interrupts).

Quoted 2 lines

smp_rmb turns into a compiler barrier on UP and should prevent the below description.

Note that that does not guarantee that the two reads will be done in the order you want. The compiler barrier _only_ affects the compiler. It does not stop the CPU from doing the reads in any order it wants. You need something stronger than smp_rmb() if you need the reads to be so ordered.

Quoted 5 lines

Note that that does not guarantee that the two reads will be done in the order you want. The compiler barrier _only_ affects the compiler. It does not stop the CPU from doing the reads in any order it wants. You need something stronger than smp_rmb() if you need the reads to be so ordered.

For reading hardware devices that can indeed be correct. But for normal memory access on a uniprocessor, if the CPU were to reorder the reads that would effect the actual algorithm then that CPU is broken.

read a
<--- interrupt - should see read a here before read b is done.
read b

Now the fact that one of the reads is a hardware clock, then this statement might not be too strong. But the fact that it is a clock, and not some memory mapped device register, I still think smp_rmb is sufficient.

Quoted 9 lines · Steven Rostedt

Quoted 5 lines

Note that that does not guarantee that the two reads will be done in the order you want. The compiler barrier _only_ affects the compiler. It does not stop the CPU from doing the reads in any order it wants. You need something stronger than smp_rmb() if you need the reads to be so ordered.

For reading hardware devices that can indeed be correct. But for normal memory access on a uniprocessor, if the CPU were to reorder the reads that would effect the actual algorithm then that CPU is broken.

Quoted 4 lines

read a
<--- interrupt - should see read a here before read b is done.
read b

Life isn't that simple. Go and read the section labelled "The things cpus get up to" in Documentation/memory-barriers.txt.

The two reads we're talking about are independent of each other. Independent reads and writes can be reordered and merged at will by the CPU, subject to restrictions imposed by barriers, cacheability attributes, MMIO attributes and suchlike.

You can get read b happening before read a, but in such a case both instructions will be in the CPU's execution pipeline. When an interrupt occurs, the CPU will presumably finish clearing what's in its pipeline before going and servicing the interrupt handler.