kern/atomic: new module

This module provides a new interface for atomic operations, built on top
of the GCC memory model aware built-in atomic operations.

3 files changed, 181 insertions, 447 deletions

diff --git a/Makefrag.am b/Makefrag.am
index 4cecd3f9..1036aff9 100644
--- a/Makefrag.am
+++ b/Makefrag.am
@@ -8,6 +8,7 @@ x15_SOURCES +=                                              \
 
 x15_SOURCES +=                                              \
 	kern/assert.h                                       \
+	kern/atomic.h                                       \
 	kern/bitmap.c                                       \
 	kern/bitmap.h                                       \
 	kern/bitmap_i.h                                     \
diff --git a/arch/x86/machine/atomic.h b/arch/x86/machine/atomic.h
index 9d2026cb..3deface6 100644
--- a/arch/x86/machine/atomic.h
+++ b/arch/x86/machine/atomic.h
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2012-2017 Richard Braun.
+ * Copyright (c) 2017 Agustina Arzille.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -15,458 +16,70 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  *
  *
- * Atomic operations.
+ * Architecture-specific atomic operations and definitions.
  *
- * When referring to atomic operations, "local" means processor-local.
  */
 
 #ifndef _X86_ATOMIC_H
 #define _X86_ATOMIC_H
 
-#include <stdint.h>
-
-#define ATOMIC_ADD(ptr, delta)                              \
-    asm volatile("lock add %1, %0"                          \
-                 : "+m" (*(ptr))                            \
-                 : "r" (delta))
-
-#define ATOMIC_FETCHADD(ptr, oldval, delta)                 \
-    asm volatile("lock xadd %1, %0"                         \
-                 : "+m" (*(ptr)), "=r" (oldval)             \
-                 : "1" (delta)                              \
-                 : "memory")
-
-#define ATOMIC_AND(ptr, bits)                               \
-    asm volatile("lock and %1, %0"                          \
-                 : "+m" (*(ptr))                            \
-                 : "r" (bits))
-
-#define ATOMIC_OR(ptr, bits)                                \
-    asm volatile("lock or %1, %0"                           \
-                 : "+m" (*(ptr))                            \
-                 : "r" (bits))
-
-#define ATOMIC_XOR(ptr, bits)                               \
-    asm volatile("lock xor %1, %0"                          \
-                 : "+m" (*(ptr))                            \
-                 : "r" (bits))
-
-/* The xchg instruction doesn't need a lock prefix */
-#define ATOMIC_SWAP(ptr, oldval, newval)                    \
-    asm volatile("xchg %1, %0"                              \
-                 : "+m" (*(ptr)), "=r" (oldval)             \
-                 : "1" (newval)                             \
-                 : "memory")
-
-#define ATOMIC_CAS(ptr, oldval, predicate, newval)          \
-    asm volatile("lock cmpxchg %3, %0"                      \
-                 : "+m" (*(ptr)), "=a" (oldval)             \
-                 : "1" (predicate), "r" (newval)            \
-                 : "memory")
-
-#define ATOMIC_LOCAL_ADD(ptr, delta)                        \
-    asm volatile("add %1, %0"                               \
-                 : "+m" (*(ptr))                            \
-                 : "r" (delta))
-
-#define ATOMIC_LOCAL_FETCHADD(ptr, oldval, delta)           \
-    asm volatile("xadd %1, %0"                              \
-                 : "+m" (*(ptr)), "=r" (oldval)             \
-                 : "1" (delta)                              \
-                 : "memory")
-
-#define ATOMIC_LOCAL_AND(ptr, bits)                         \
-    asm volatile("and %1, %0"                               \
-                 : "+m" (*(ptr))                            \
-                 : "r" (bits))
-
-#define ATOMIC_LOCAL_OR(ptr, bits)                          \
-    asm volatile("or %1, %0"                                \
-                 : "+m" (*(ptr))                            \
-                 : "r" (bits))
-
-#define ATOMIC_LOCAL_XOR(ptr, bits)                         \
-    asm volatile("xor %1, %0"                               \
-                 : "+m" (*(ptr))                            \
-                 : "r" (bits))
-
-/* The xchg instruction implies a lock prefix */
-#define ATOMIC_LOCAL_SWAP(ptr, oldval, newval)              \
-    asm volatile("xchg %1, %0"                              \
-                 : "+m" (*(ptr)), "=r" (oldval)             \
-                 : "1" (newval)                             \
-                 : "memory")
-
-#define ATOMIC_LOCAL_CAS(ptr, oldval, predicate, newval)    \
-    asm volatile("cmpxchg %3, %0"                           \
-                 : "+m" (*(ptr)), "=a" (oldval)             \
-                 : "1" (predicate), "r" (newval)            \
-                 : "memory")
-
-static inline void
-atomic_add_uint(volatile unsigned int *ptr, int delta)
-{
-    ATOMIC_ADD(ptr, delta);
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline unsigned int
-atomic_fetchadd_uint(volatile unsigned int *ptr, int delta)
-{
-    unsigned int oldval;
-
-    ATOMIC_FETCHADD(ptr, oldval, delta);
-    return oldval;
-}
-
-static inline void
-atomic_and_uint(volatile unsigned int *ptr, unsigned int bits)
-{
-    ATOMIC_AND(ptr, bits);
-}
-
-static inline void
-atomic_or_uint(volatile unsigned int *ptr, unsigned int bits)
-{
-    ATOMIC_OR(ptr, bits);
-}
-
-static inline void
-atomic_xor_uint(volatile unsigned int *ptr, unsigned int bits)
-{
-    ATOMIC_XOR(ptr, bits);
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline unsigned int
-atomic_swap_uint(volatile unsigned int *ptr, unsigned int newval)
-{
-    unsigned int oldval;
-
-    ATOMIC_SWAP(ptr, oldval, newval);
-    return oldval;
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline unsigned int
-atomic_cas_uint(volatile unsigned int *ptr, unsigned int predicate,
-                unsigned int newval)
-{
-    unsigned int oldval;
-
-    ATOMIC_CAS(ptr, oldval, predicate, newval);
-    return oldval;
-}
-
-static inline void
-atomic_local_add_uint(volatile unsigned int *ptr, int delta)
-{
-    ATOMIC_LOCAL_ADD(ptr, delta);
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline unsigned int
-atomic_local_fetchadd_uint(volatile unsigned int *ptr, int delta)
-{
-    unsigned int oldval;
-
-    ATOMIC_LOCAL_FETCHADD(ptr, oldval, delta);
-    return oldval;
-}
-
-static inline void
-atomic_local_and_uint(volatile unsigned int *ptr, unsigned int bits)
-{
-    ATOMIC_LOCAL_AND(ptr, bits);
-}
-
-static inline void
-atomic_local_or_uint(volatile unsigned int *ptr, unsigned int bits)
-{
-    ATOMIC_LOCAL_OR(ptr, bits);
-}
-
-static inline void
-atomic_local_xor_uint(volatile unsigned int *ptr, unsigned int bits)
-{
-    ATOMIC_LOCAL_XOR(ptr, bits);
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline unsigned int
-atomic_local_swap_uint(volatile unsigned int *ptr, unsigned int newval)
-{
-    unsigned int oldval;
-
-    ATOMIC_LOCAL_SWAP(ptr, oldval, newval);
-    return oldval;
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline unsigned int
-atomic_local_cas_uint(volatile unsigned int *ptr, unsigned int predicate,
-                      unsigned int newval)
-{
-    unsigned int oldval;
-
-    ATOMIC_LOCAL_CAS(ptr, oldval, predicate, newval);
-    return oldval;
-}
-
-static inline void
-atomic_add_ulong(volatile unsigned long *ptr, long delta)
-{
-    ATOMIC_ADD(ptr, delta);
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline unsigned long
-atomic_fetchadd_ulong(volatile unsigned long *ptr, long delta)
-{
-    unsigned long oldval;
-
-    ATOMIC_FETCHADD(ptr, oldval, delta);
-    return oldval;
-}
-
-static inline void
-atomic_and_ulong(volatile unsigned long *ptr, unsigned long bits)
-{
-    ATOMIC_AND(ptr, bits);
-}
-
-static inline void
-atomic_or_ulong(volatile unsigned long *ptr, unsigned long bits)
-{
-    ATOMIC_OR(ptr, bits);
-}
-
-static inline void
-atomic_xor_ulong(volatile unsigned long *ptr, unsigned long bits)
-{
-    ATOMIC_XOR(ptr, bits);
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline unsigned long
-atomic_swap_ulong(volatile unsigned long *ptr, unsigned long newval)
-{
-    unsigned long oldval;
-
-    ATOMIC_SWAP(ptr, oldval, newval);
-    return oldval;
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline unsigned long
-atomic_cas_ulong(volatile unsigned long *ptr, unsigned long predicate,
-                 unsigned long newval)
-{
-    unsigned long oldval;
-
-    ATOMIC_CAS(ptr, oldval, predicate, newval);
-    return oldval;
-}
-
-static inline void
-atomic_local_add_ulong(volatile unsigned long *ptr, long delta)
-{
-    ATOMIC_LOCAL_ADD(ptr, delta);
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline unsigned long
-atomic_local_fetchadd_ulong(volatile unsigned long *ptr, long delta)
-{
-    unsigned long oldval;
-
-    ATOMIC_LOCAL_FETCHADD(ptr, oldval, delta);
-    return oldval;
-}
-
-static inline void
-atomic_local_and_ulong(volatile unsigned long *ptr, unsigned long bits)
-{
-    ATOMIC_LOCAL_AND(ptr, bits);
-}
-
-static inline void
-atomic_local_or_ulong(volatile unsigned long *ptr, unsigned long bits)
-{
-    ATOMIC_LOCAL_OR(ptr, bits);
-}
-
-static inline void
-atomic_local_xor_ulong(volatile unsigned long *ptr, unsigned long bits)
-{
-    ATOMIC_LOCAL_XOR(ptr, bits);
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline unsigned long
-atomic_local_swap_ulong(volatile unsigned long *ptr, unsigned long newval)
-{
-    unsigned long oldval;
-
-    ATOMIC_LOCAL_SWAP(ptr, oldval, newval);
-    return oldval;
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline unsigned long
-atomic_local_cas_ulong(volatile unsigned long *ptr, unsigned long predicate,
-                       unsigned long newval)
-{
-    unsigned long oldval;
-
-    ATOMIC_LOCAL_CAS(ptr, oldval, predicate, newval);
-    return oldval;
-}
-
-static inline void
-atomic_add_uintptr(volatile uintptr_t *ptr, intptr_t delta)
-{
-    ATOMIC_ADD(ptr, delta);
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline uintptr_t
-atomic_fetchadd_uintptr(volatile uintptr_t *ptr, intptr_t delta)
-{
-    uintptr_t oldval;
-
-    ATOMIC_FETCHADD(ptr, oldval, delta);
-    return oldval;
-}
-
-static inline void
-atomic_and_uintptr(volatile uintptr_t *ptr, uintptr_t bits)
-{
-    ATOMIC_AND(ptr, bits);
-}
-
-static inline void
-atomic_or_uintptr(volatile uintptr_t *ptr, uintptr_t bits)
-{
-    ATOMIC_OR(ptr, bits);
-}
-
-static inline void
-atomic_xor_uintptr(volatile uintptr_t *ptr, uintptr_t bits)
-{
-    ATOMIC_XOR(ptr, bits);
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline uintptr_t
-atomic_swap_uintptr(volatile uintptr_t *ptr, uintptr_t newval)
-{
-    uintptr_t oldval;
-
-    ATOMIC_SWAP(ptr, oldval, newval);
-    return oldval;
-}
-
-/*
- * Implies a full memory barrier.
- */
-static inline uintptr_t
-atomic_cas_uintptr(volatile uintptr_t *ptr, uintptr_t predicate,
-                   uintptr_t newval)
-{
-    uintptr_t oldval;
-
-    ATOMIC_CAS(ptr, oldval, predicate, newval);
-    return oldval;
-}
-
-static inline void
-atomic_local_add_uintptr(volatile uintptr_t *ptr, intptr_t delta)
-{
-    ATOMIC_LOCAL_ADD(ptr, delta);
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline uintptr_t
-atomic_local_fetchadd_uintptr(volatile uintptr_t *ptr, intptr_t delta)
-{
-    uintptr_t oldval;
-
-    ATOMIC_LOCAL_FETCHADD(ptr, oldval, delta);
-    return oldval;
-}
-
-static inline void
-atomic_local_and_uintptr(volatile uintptr_t *ptr, uintptr_t bits)
-{
-    ATOMIC_LOCAL_AND(ptr, bits);
-}
-
-static inline void
-atomic_local_or_uintptr(volatile uintptr_t *ptr, uintptr_t bits)
-{
-    ATOMIC_LOCAL_OR(ptr, bits);
-}
-
-static inline void
-atomic_local_xor_uintptr(volatile uintptr_t *ptr, uintptr_t bits)
-{
-    ATOMIC_LOCAL_XOR(ptr, bits);
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline uintptr_t
-atomic_local_swap_uintptr(volatile uintptr_t *ptr, uintptr_t newval)
-{
-    uintptr_t oldval;
-
-    ATOMIC_LOCAL_SWAP(ptr, oldval, newval);
-    return oldval;
-}
-
-/*
- * Implies a compiler barrier.
- */
-static inline uintptr_t
-atomic_local_cas_uintptr(volatile uintptr_t *ptr, uintptr_t predicate,
-                         uintptr_t newval)
-{
-    uintptr_t oldval;
-
-    ATOMIC_LOCAL_CAS(ptr, oldval, predicate, newval);
-    return oldval;
-}
+#ifdef __LP64__
+
+#define atomic_load(ptr, mo)         __atomic_load_n((ptr), mo)
+#define atomic_store(ptr, val, mo)   __atomic_store_n((ptr), (val), mo)
+
+#else /* __LP64__ */
+
+/*
+ * On x86, the compiler generates either an FP-stack read/write, or an SSE2
+ * store/load to implement these 64-bit atomic operations. Since that's not
+ * feasible on kernel-land, we fallback to cmpxchg8b. Note that this means
+ * that 'atomic_load' cannot be used on a const pointer. However, if it's
+ * being accessed by an atomic operation, then it's very likely that it can
+ * also be modified, so it should be OK.
+ */
+
+#define atomic_load(ptr, mo)                                              \
+MACRO_BEGIN                                                               \
+    typeof(*(ptr)) ___ret;                                                \
+                                                                          \
+    if (sizeof(___ret) != 8) {                                            \
+        ___ret = __atomic_load_n((ptr), mo);                              \
+    } else {                                                              \
+        ___ret = 0;                                                       \
+        __atomic_compare_exchange_n((uint64_t *)(ptr), &___ret, ___ret,   \
+                                    0, mo, __ATOMIC_RELAXED);             \
+    }                                                                     \
+                                                                          \
+    ___ret;                                                               \
+MACRO_END
+
+#define atomic_store(ptr, val, mo)                                        \
+MACRO_BEGIN                                                               \
+    if (sizeof(*(ptr) != 8)) {                                            \
+        __atomic_store_n((ptr), (val), mo);                               \
+    } else {                                                              \
+        typeof(ptr) ___ptr;                                               \
+        typeof(val) ___val, ___exp;                                       \
+                                                                          \
+        ___ptr = (uint64_t *)(ptr);                                       \
+        ___val = (val);                                                   \
+        ___exp = *___ptr;                                                 \
+                                                                          \
+        while (!__atomic_compare_exchange_n(___ptr, &___exp, ___val, 0,   \
+               momo, __ATOMIC_RELAXED)) {                                 \
+        }                                                                 \
+                                                                          \
+    }                                                                     \
+MACRO_END
+
+#endif /* __LP64__ */
+
+/* Notify the generic header that we implemented loads and stores */
+#define ATOMIC_LOAD_DEFINED
+#define ATOMIC_STORE_DEFINED
+
+/* Both x86 and x86_64 can use atomic operations on 64-bit values */
+#define ATOMIC_HAVE_64B_OPS
 
 #endif /* _X86_ATOMIC_H */
diff --git a/kern/atomic.h b/kern/atomic.h
new file mode 100644
index 00000000..d6338136
--- /dev/null
+++ b/kern/atomic.h
@@ -0,0 +1,120 @@
+/*
+ * Copyright (c) 2017 Agustina Arzille.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_ATOMIC_H
+#define _KERN_ATOMIC_H
+
+#include <machine/atomic.h>
+
+/*
+ * Supported memory orders.
+ */
+
+#define ATOMIC_RELAXED   __ATOMIC_RELAXED
+#define ATOMIC_ACQUIRE   __ATOMIC_ACQUIRE
+#define ATOMIC_RELEASE   __ATOMIC_RELEASE
+#define ATOMIC_ACQ_REL   __ATOMIC_ACQ_REL
+#define ATOMIC_SEQ_CST   __ATOMIC_SEQ_CST
+
+/*
+ * Type-generic atomic operations.
+ */
+
+#define atomic_fetch_add(ptr, val, mo)   __atomic_fetch_add((ptr), (val), mo)
+
+#define atomic_fetch_sub(ptr, val, mo)   __atomic_fetch_sub((ptr), (val), mo)
+
+#define atomic_fetch_and(ptr, val, mo)   __atomic_fetch_and((ptr), (val), mo)
+
+#define atomic_fetch_or(ptr, val, mo)    __atomic_fetch_or((ptr), (val), mo)
+
+#define atomic_fetch_xor(ptr, val, mo)   __atomic_fetch_xor((ptr), (val), mo)
+
+#define atomic_add(ptr, val, mo)   ((void)__atomic_add_fetch((ptr), (val), mo))
+
+#define atomic_sub(ptr, val, mo)   ((void)__atomic_sub_fetch((ptr), (val), mo))
+
+#define atomic_and(ptr, val, mo)   ((void)__atomic_and_fetch((ptr), (val), mo))
+
+#define atomic_or(ptr, val, mo)    ((void)__atomic_or_fetch((ptr), (val), mo))
+
+#define atomic_xor(ptr, val, mo)   ((void)__atomic_xor_fetch((ptr), (val), mo))
+
+#define atomic_swap(ptr, val, mo)   __atomic_exchange_n((ptr), (val), mo)
+
+/*
+ * For compare-and-swap, we deviate a little from the standard, and only
+ * return the value before the comparison, leaving it up to the user to
+ * determine whether the swap was actually performed or not.
+ * Also, note that the memory order in case of failure is relaxed. This is
+ * because atomic CAS is typically used in a loop. However, if a different
+ * code path is taken on failure (rather than retrying), then the user
+ * should be aware that a memory fence might be necessary.
+ */
+
+#define atomic_cas(ptr, exp, nval, mo)                            \
+MACRO_BEGIN                                                       \
+    typeof(*(ptr)) ___exp, ___nval;                               \
+                                                                  \
+    ___exp = (exp);                                               \
+    ___nval = (nval);                                             \
+    __atomic_compare_exchange_n((ptr), &___exp, ___nval, 0, mo,   \
+                                ATOMIC_RELAXED);                  \
+    ___exp;                                                       \
+MACRO_END
+
+/*
+ * Some architectures may need specific definitions for loads and stores,
+ * in order to prevent the compiler from emitting unsupported instructions.
+ * As such, we only define these if the arch header didn't already.
+ */
+
+#ifndef ATOMIC_LOAD_DEFINED
+#define atomic_load(ptr, mo)   __atomic_load_n((ptr), mo)
+#endif /* ATOMIC_LOAD_DEFINED */
+
+#ifndef ATOMIC_STORE_DEFINED
+#define atomic_store(ptr, val, mo)   __atomic_store_n((ptr), (val), mo)
+#endif /* ATOMIC_STORE_DEFINED */
+
+/*
+ * Common shortcuts.
+ */
+
+#define atomic_cas_acquire(ptr, exp, val)   \
+    atomic_cas(ptr, exp, val, ATOMIC_ACQUIRE)
+
+#define atomic_cas_release(ptr, exp, val)   \
+    atomic_cas(ptr, exp, val, ATOMIC_RELEASE)
+
+#define atomic_cas_seq_cst(ptr, exp, val)   \
+    atomic_cas(ptr, exp, val, ATOMIC_SEQ_CST)
+
+#define atomic_swap_acquire(ptr, val)   atomic_swap(ptr, val, ATOMIC_ACQUIRE)
+#define atomic_swap_release(ptr, val)   atomic_swap(ptr, val, ATOMIC_RELEASE)
+#define atomic_swap_seq_cst(ptr, val)   atomic_swap(ptr, val, ATOMIC_SEQ_CST)
+
+#define atomic_fetch_add_acq_rel(ptr, val)   \
+    atomic_fetch_add(ptr, val, ATOMIC_ACQ_REL)
+
+#define atomic_fetch_sub_acq_rel(ptr, val)   \
+    atomic_fetch_sub(ptr, val, ATOMIC_ACQ_REL)
+
+#define atomic_or_acq_rel(ptr, val)    atomic_or(ptr, val, ATOMIC_ACQ_REL)
+#define atomic_and_acq_rel(ptr, val)   atomic_and(ptr, val, ATOMIC_ACQ_REL)
+
+#endif /* _KERN_ATOMIC_H */