[2.5] asm-generic/atomic.h and changes to arm, parisc, mips, m68k, sh, cris to use it

This patch provides an atomic.h implementation without any knowledge of the CPU instruction set.
On UP, it disables interrupts around atomic ops with the exception of non-testing ops on m68k.
On SMP it uses a global spinlock cache taken from parisc.

As a side effect, it fixes cris, mips/ISA-level-1 and sh that were broken due to the local_irq* renaming.

It also fixes the lack of some primitives that many of the changed archs suffered from (e.g. atomic_{add,sub}_return) and reduces the total amount of code.

diffstat:

 include/asm-generic/atomic.h |  159 +++++++++++++++++++++++++++++++++++++++++++
 include/asm-cris/atomic.h    |  149 ----------------------------------------
 include/asm-arm/atomic.h     |  114 ------------------------------
 include/asm-parisc/atomic.h  |  104 ----------------------------
 include/asm-sh/atomic.h      |  103 ---------------------------
 include/asm-mips/atomic.h    |   83 ++--------------------
 include/asm-m68k/atomic.h    |   50 +------------
 arch/parisc/lib/bitops.c     |    6 -
 init/main.c                  |    1 
 9 files changed, 178 insertions(+), 591 deletions(-)

diff --exclude-from=/home/ldb/src/linux-exclude -urNd --exclude=asm-i386 a/arch/parisc/lib/bitops.c b/arch/parisc/lib/bitops.c
@@ -9,12 +9,6 @@
 #include <asm/system.h>
 #include <asm/atomic.h>
 
-#ifdef CONFIG_SMP
-spinlock_t __atomic_hash[ATOMIC_HASH_SIZE] = {
-	[0 ... (ATOMIC_HASH_SIZE-1)]  = SPIN_LOCK_UNLOCKED
-};
-#endif
-
 spinlock_t __atomic_lock = SPIN_LOCK_UNLOCKED;
 
 #ifndef __LP64__

diff --exclude-from=/home/ldb/src/linux-exclude -urNd --exclude=asm-i386 a/init/main.c b/init/main.c
@@ -10,6 +10,7 @@
  */
 
 #define __KERNEL_SYSCALLS__
+#define __INIT_GLOBAL__
 
 #include <linux/config.h>
 #include <linux/proc_fs.h>

Hi,

Why did you change m68k? It was fine before.

bye, Roman

- Didn't implement atomic_{add,sub,inc,dec}_return. This is currently not used in the generic kernel but it can be useful.
- Had inline assembly for things the compiler should be able to generate on its own
- Didn't work on SMP (irrelevant in practice, but we already need that in asm-generic/atomic.h for parisc so m68k gets it for free)

The actual assembly generated should be the same and the header is shorter.

The only problem is that it may introduce bugs. Does it work on m68k?

The compiler is free to generate them several other ways

Doesn't matter

Possibly not - volatile doesnt guarantee the compiler won't do

x = 1
add *p into x
store x into *p

The general idea looks fine, but you can't drop asm stuff for volatile C and be sure you will get away with it. On M68K it works because the instructions it forces are those guaranteed to be indivisible relative to an interrupt. You lose that assumption.

Er, AIUI 'volatile' guarantees that '*p++' will do precisely that. It's a load, an add and a store, and the rules about volatile mean that the load and the store _must_ be separate.

--
dwmw2

I noticed that while testing how rmk's code behaved differently than mine (and corrected in the v2 patch).
Before that, I just assumed that since the CPU must anyway issue a separate load and store, the compiler would use the faster instruction (that's why there is a LOCK prefix in the i386 instruction set).

Hi,

m68k has a cmpxchg like instruction, which can be used for that.

The compiler can cache the value in a register, the assembly forces that into memory. __ARCH_ATOMIC_HAVE_MEMORY_OPERANDS won't work because of that.

bye, Roman

It shouldn't since it is volatile and the machine has instructions with memory operands.

Anyway, let's ignore the m68k-specific parts of the patch.

I'm curious what part of C99 guarantees that it must generate

add 1 to memory

not

load memory
add 1
store memory

It certainly guarantees not to cache it for use next statement, but does it actually persuade the compiler to use direct operations on memory ?

I'm not a C99 language lawyer but genuinely curious

No, I don't claim it is standard behavior (I also don't claim it isn't and unfortunately the C99 standard is not free so I cannot check it).

I just claim that if the value isn't going to be reused, using the instruction with memory operands should be faster, because otherwise there would have been little reason to include it in the instruction set (except code size optimization, but it seems very unlikely that a CPU would include CISC instructions just for that).
So a working GCC with optimization enabled should generate it and especially should always generate it if it generates it in one compilation (because of volatility).

Of course there is a risk of failure, but it seems small enough to not worry about it unless there are other good reasons for the compiler to behave differently.

However OTOH if it fails it would fail subtly so maybe it's better to do it safely with inline assembly.

Followup to:  <[email protected]>
By author:    Alan Cox <[email protected]>
In newsgroup: linux.dev.kernel

C99 basically doesn't guarantee *anything* about "volatile", except that it works as a keyword. It really can't, since the C standard doesn't have a model for either hardware I/O or multithreaded execution, effectively the two cases for which "volatile" matters; the exact wording in the standard is § 6.7.3.6:

An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3. Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by the unknown factors mentioned previously.114) What constitutes an access to an object that has volatile-qualified type is implementation-defined.

114) A volatile declaration may be used to describe an object corresponding to a memory-mapped input/output port or an object accessed by an asynchronously interrupting function. Actions on
objects so declared shall not be optimized out by an
implementation or reordered except as permitted by the rules for evaluating expressions.

It therefore becomes a quality of implementation issue, assuming there are instructions that do that. Even so, it's iffy... should it generate "lock incl" on x86, for example?

*In practice*, what can be safely assumed for a volatile object is that:

a) A store to the volatile location will correspond to exactly one "store" hardware operations (note that multiple stores to the same object between sequence points are illegal in C);

b) If there is exactly one read reference to a volatile object between sequence points, it will correspond to exactly one "load" operation in hardware. If there is are n read references to the same volatile objects between adjacent sequence points, it will correspond to some number m "load" operations such that 1 <= m <= n.

c) For either of these, if the volatile object is too large or has the wrong alignment to handle atomically in hardware, it will in effect be treated like some number of smaller atomic objects.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt	<[email protected]>

Hi,

volatile is no guarantee for that:

volatile int x;

void f(int y)

{
        x += y;
}

becomes:

	move.l x,%d0
	add.l 8(%a6),%d0
	move.l %d0,x

I agree that volatile should avoid caching, but it does not guarantee an atomic modify.

bye, Roman

Please don't do this for ARM.

Russell King ([email protected])                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Sorry, the patch I sent was total crap.

Not only the simple operations were unsafe, but they also didn't work because GCC splits volatile read-change-writes... Furthermore the complex operation caused two loads of v->counter still beacuse of volatile.

The following patch replaces the asm-generic and asm-m68k parts of the original patch with hopefully decent code.

The code is now equivalent to the old ARM one (I have separated the add/sub from the counter store for more clarity, but this shouldn't have any adverse effect) and m68k continues to use its inline assembly but uses asm-generic/atomic.h for basic definitions, barriers and complex operations.

diff --exclude-from=/home/ldb/src/linux-exclude -urNd --exclude=asm-sh --exclude=asm-cris --exclude=asm-arm --exclude=asm-parisc --exclude=parisc --exclude=asm-mips --exclude=asm-i386 a/include/asm-generic/atomic.h b/include/asm-generic/atomic.h
@@ -0,0 +1,167 @@
+/*
+ *  linux/include/asm-generic/atomic.h
+ *
+ *  Copyright (c) 2002 Luca Barbieri.
+ *  Portions Copyright (C) 2000 Philipp Rumpf <[email protected]>.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ */
+#ifndef __ASM_GENERIC_ATOMIC_H
+#define __ASM_GENERIC_ATOMIC_H
+
+#include <linux/config.h>
+
+#ifndef __ARCH_ATOMIC_HAVE_BASIC
+typedef struct {
+	volatile int counter;
+} atomic_t;
+#endif
+
+#ifdef __KERNEL__
+
+#ifndef __ARCH_ATOMIC_HAVE_BASIC
+#define ATOMIC_INIT(i)	{ (i) }
+
+#define atomic_read(v)   ((v)->counter)
+#define atomic_set(v, i) (((v)->counter) = (i))
+#endif
+
+#ifndef __ARCH_ATOMIC_HAVE_LOCK
+#ifndef CONFIG_SMP
+#include <asm/system.h>
+
+#define atomic_lock(v)   do {unsigned long flags; local_irq_save(flags);
+#define atomic_unlock(v) local_irq_restore(flags);} while(0)
+
+#else
+
+#include <linux/spinlock.h>
+
+#ifndef atomic_to_spinlock
+/* we have an array of spinlocks for our atomic_ts, and a hash function
+ * to get the right index */
+/* NOTE: unless there are really a lot of CPUs ATOMIC_HASH_SIZE = 1 is
+         probably the fastest
+*/
+#ifndef ATOMIC_HASH_SIZE
+#define ATOMIC_HASH_SIZE 1
+#endif
+
+#ifdef __INIT_GLOBAL__
+spinlock_t __atomic_hash[ATOMIC_HASH_SIZE] = {
+	[0 ... (ATOMIC_HASH_SIZE-1)]  = SPIN_LOCK_UNLOCKED
+};
+#else
+extern spinlock_t __atomic_hash[ATOMIC_HASH_SIZE];
+#endif
+
+#if ATOMIC_HASH_SIZE > 1
+/* This can probably be greatly improved. */
+#include <linux/cache.h>
+#define atomic_to_spinlock(v) (&__atomic_hash[(((unsigned long)v / sizeof(struct atomic_t)) + ((unsigned long)v / L1_CACHE_BYTES)) % ATOMIC_HASH_SIZE])
+#else
+#define atomic_to_spinlock(v) (&__atomic_hash[0])
+#endif
+#endif
+
+#define atomic_lock(v)   do {unsigned long flags; spin_lock_irqsave(atomic_to_spinlock(v), flags)
+#define atomic_unlock(v) spin_unlock_irqrestore(atomic_to_spinlock(v), flags); } while(0)
+#endif 
+#endif /* CONFIG_SMP */
+
+#ifndef __ARCH_ATOMIC_HAVE_SIMPLE
+static inline void atomic_add(int i, atomic_t *v)
+{
+	atomic_lock(v);
+	v->counter += i;
+	atomic_unlock(v);
+}
+
+static inline void atomic_sub(int i, atomic_t *v)
+{
+	atomic_lock(v);
+	v->counter -= i;
+	atomic_unlock(v);
+}
+
+#define atomic_inc(v) atomic_add(1, (v))
+#define atomic_dec(v) atomic_sub(1, (v))
+#endif
+
+#ifndef __ARCH_ATOMIC_HAVE_COMPLEX
+static inline int atomic_add_return(int i, atomic_t *v)
+{
+	int new;
+
+	atomic_lock(v);
+	new = v->counter;
+	new += i;
+	v->counter = new;
+	atomic_unlock(v);
+
+	return new;
+}
+
+static inline int atomic_sub_return(int i, atomic_t *v)
+{
+	int new;
+
+	atomic_lock(v);
+	new = v->counter;
+	new -= i;
+	v->counter = new;
+	atomic_unlock(v);
+
+	return new;
+}
+
+#define atomic_dec_return(v) atomic_sub_return(1, (v))
+#define atomic_inc_return(v) atomic_add_return(1, (v))
+
+#define atomic_sub_and_test(i,v) (atomic_sub_return((i), (v)) == 0)
+#define atomic_add_and_test(i,v) (atomic_add_return((i), (v)) == 0)
+#define atomic_dec_and_test(v)  (atomic_dec_return((v)) == 0)
+#define atomic_inc_and_test(v)  (atomic_inc_return((v)) == 0)
+
+#define atomic_add_negative(i,v) (atomic_add_return(i, v) < 0)
+#define atomic_sub_negative(i,v) (atomic_sub_return(i, v) < 0)
+#endif
+
+#if !defined(CONFIG_SMP) && !defined(__ARCH_ATOMIC_HAVE_MASK)
+#define atomic_lock_mask(v)   atomic_lock(0)
+#define atomic_unlock_mask(v) atomic_unlock(0)
+
+static inline void atomic_clear_mask(unsigned long mask, unsigned long *addr)
+{
+	atomic_lock_mask(addr);
+	*addr &= ~mask;
+	atomic_unlock_mask(addr);
+}
+
+static inline void atomic_set_mask(unsigned long mask, unsigned long *addr)
+{
+	atomic_lock_mask(addr);
+	*addr |= mask;
+	atomic_unlock_mask(addr);
+}
+
+static inline void atomic_change_mask(unsigned long mask, unsigned long *addr)
+{
+	atomic_lock_mask(addr);
+	*addr ^= mask;
+	atomic_unlock_mask(addr);
+}
+#endif
+
+#ifndef __ARCH_ATOMIC_HAVE_BARRIERS
+#define smp_mb__before_atomic_dec()	barrier()
+#define smp_mb__after_atomic_dec()	barrier()
+#define smp_mb__before_atomic_inc()	barrier()
+#define smp_mb__after_atomic_inc()	barrier()
+#endif
+
+#endif
+#endif

diff --exclude-from=/home/ldb/src/linux-exclude -urNd --exclude=asm-sh --exclude=asm-cris --exclude=asm-arm --exclude=asm-parisc --exclude=parisc --exclude=asm-mips --exclude=asm-i386 a/include/asm-m68k/atomic.h b/include/asm-m68k/atomic.h
@@ -10,11 +10,10 @@
  * We do not have SMP m68k systems, so we don't have to deal with that.
  */
 
-typedef struct { int counter; } atomic_t;
-#define ATOMIC_INIT(i)	{ (i) }
-
-#define atomic_read(v)		((v)->counter)
-#define atomic_set(v, i)	(((v)->counter) = i)
+#define __ARCH_ATOMIC_HAVE_SIMPLE
+#define __ARCH_ATOMIC_HAVE_MASK
+#include <asm-generic/atomic.h>
+#undef atomic_dec_and_test
 
 static __inline__ void atomic_add(int i, atomic_t *v)
 {

@@ -49,10 +48,4 @@
 #define atomic_set_mask(mask, v) \
 	__asm__ __volatile__("orl %1,%0" : "=m" (*v) : "id" (mask),"0"(*v))
 
-/* Atomic operations are already serializing */
-#define smp_mb__before_atomic_dec()	barrier()
-#define smp_mb__after_atomic_dec()	barrier()
-#define smp_mb__before_atomic_inc()	barrier()
-#define smp_mb__after_atomic_inc()	barrier()
-
 #endif /* __ARCH_M68K_ATOMIC __ */

diff --exclude-from=/home/ldb/src/linux-exclude -urNd --exclude=asm-sh --exclude=asm-cris --exclude=asm-arm --exclude=asm-parisc --exclude=parisc --exclude=asm-mips --exclude=asm-i386 a/init/main.c b/init/main.c
@@ -10,6 +10,7 @@
  */
 
 #define __KERNEL_SYSCALLS__
+#define __INIT_GLOBAL__
 
 #include <linux/config.h>
 #include <linux/proc_fs.h>