The origin of this series: When Nick Piggin posted his first suggestion for ticket spinlocks on LKML, I immediately liked the idea. For details check LWN [1], in a nutshell: This algorithm enforces strict FIFO order for the admission to contended spinlocks, thus it improves the determinism on SMP systems with more than 2 CPUs.
Meanwhile, ticket spinlocks are mainline (2.6.25). But that version has to drawbacks for us: it doesn't support nesting like xnlock does, and it is x86-only so far. So I designed a version for Xenomai which is both nestable and arch-independent. It is certainly not as optimal as mainline's version, but our code path stresses the locking code differently anyway, and no one denies us to introduce per-arch optimized variants later on (if this lock implementation gains broader relevance). Survived heavy testing on a 4-way box (15, 20, 25, and 30 us latency instances across the cores). [1] http://lwn.net/Articles/267331
---
include/asm-generic/bits/pod.h | 4 -
include/asm-generic/system.h | 122 +++++++++++++++++++++++++++++++++++++----
ksrc/nucleus/Kconfig | 12 ++++
3 files changed, 126 insertions(+), 12 deletions(-)
Index: b/include/asm-generic/system.h
===================================================================
--- a/include/asm-generic/system.h
+++ b/include/asm-generic/system.h
@@ -104,7 +104,12 @@ typedef struct {
typedef struct {
+#ifdef CONFIG_XENO_OPT_TICKET_LOCK
+ atomic_t fifo;
+ int owner;
+#else
atomic_t owner;
+#endif
const char *file;
const char *function;
unsigned line;
@@ -115,7 +120,7 @@ typedef struct {
} xnlock_t;
#define XNARCH_LOCK_UNLOCKED (xnlock_t) { \
- { ~0 }, \
+ XNLOCK_INIT_VALUE, \
NULL, \
NULL, \
0, \
@@ -167,6 +172,8 @@ xnlock_dbg_acquired(xnlock_t *lock, int
lock->cpu = cpu;
}
+static inline int xnlock_owner(xnlock_t *lock);
+
static inline int xnlock_dbg_release(xnlock_t *lock)
{
extern xnlockinfo_t xnlock_stats[];
@@ -174,7 +181,7 @@ static inline int xnlock_dbg_release(xnl
int cpu = xnarch_current_cpu();
xnlockinfo_t *stats = &xnlock_stats[cpu];
- if (unlikely(atomic_read(&lock->owner) != cpu)) {
+ if (unlikely(xnlock_owner(lock) != cpu)) {
rthal_emergency_console();
printk(KERN_ERR "Xenomai: unlocking unlocked nucleus lock %p"
" on CPU #%d\n"
@@ -199,9 +206,18 @@ static inline int xnlock_dbg_release(xnl
#else /* !(CONFIG_SMP && XENO_DEBUG(NUCLEUS)) */
+#ifdef CONFIG_XENO_OPT_TICKET_LOCK
+typedef struct {
+
+ atomic_t fifo;
+ int owner;
+
+} xnlock_t;
+#else
typedef struct { atomic_t owner; } xnlock_t;
+#endif
-#define XNARCH_LOCK_UNLOCKED (xnlock_t) { { ~0 } }
+#define XNARCH_LOCK_UNLOCKED (xnlock_t) { XNLOCK_INIT_VALUE }
#define XNLOCK_DBG_CONTEXT
#define XNLOCK_DBG_CONTEXT_ARGS
@@ -313,11 +329,6 @@ static inline int xnarch_setimask (int i
#define xnlock_clear_irqoff(lock) xnlock_put_irqrestore(lock, 1)
#define xnlock_clear_irqon(lock) xnlock_put_irqrestore(lock, 0)
-static inline void xnlock_init (xnlock_t *lock)
-{
- *lock = XNARCH_LOCK_UNLOCKED;
-}
-
#define DECLARE_XNLOCK(lock) xnlock_t lock
#define DECLARE_EXTERN_XNLOCK(lock) extern xnlock_t lock
#define DEFINE_XNLOCK(lock) xnlock_t lock = XNARCH_LOCK_UNLOCKED
@@ -325,12 +336,97 @@ static inline void xnlock_init (xnlock_t
void __xnlock_spin(xnlock_t *lock /*, */ XNLOCK_DBG_CONTEXT_ARGS);
+#ifdef CONFIG_XENO_OPT_TICKET_LOCK
+/* Note: We assume atomic_t is at least 32-bit wide. */
+#define XNLOCK_HEAD_MASK 0x000000FF
+#define XNLOCK_HEAD_INC 0x00000001
+#define XNLOCK_TAIL_MASK 0xFF000000
+#define XNLOCK_TAIL_SHIFT 24
+#define XNLOCK_TAIL_INC 0x01000000
+#define XNLOCK_TICKET_MASK (XNLOCK_HEAD_MASK | XNLOCK_TAIL_MASK)
+#define XNLOCK_INIT_VALUE { 0x00000001 }, ~0
+
+static inline int xnlock_owner(xnlock_t *lock)
+{
+ return lock->owner;
+}
+
+static inline int __xnlock_get(xnlock_t *lock /*, */ XNLOCK_DBG_CONTEXT_ARGS)
+{
+ unsigned long long start;
+ int cpu = xnarch_current_cpu();
+ u32 fifo;
+ u8 ticket;
+
+ if (xnlock_owner(lock) == cpu)
+ return 1;
+
+ xnlock_dbg_prepare_acquire(&start);
+
+ fifo = atomic_add_return(XNLOCK_TAIL_INC, &lock->fifo);
+ ticket = fifo >> XNLOCK_TAIL_SHIFT;
+
+ /* First check if we are already the owner (head == tail). */
+ if (unlikely((u8)fifo != ticket)) {
+ unsigned int spin_limit;
+
+ xnlock_dbg_prepare_spin(&spin_limit);
+
+ /*
+ * Spin until head equals our ticket. In this case,
+ * moving out-of-line does not pay off.
+ */
+ do {
+ cpu_relax();
+ xnlock_dbg_spinning(lock, cpu, &spin_limit /*, */
+ XNLOCK_DBG_PASS_CONTEXT);
+ } while ((u8)atomic_read(&lock->fifo) != ticket);
+ }
+ lock->owner = cpu;
+
+ xnlock_dbg_acquired(lock, cpu, &start /*, */ XNLOCK_DBG_PASS_CONTEXT);
+
+ return 0;
+}
+
+static inline void xnlock_put(xnlock_t *lock)
+{
+ u32 fifo = atomic_read(&lock->fifo);
+
+ if (xnlock_dbg_release(lock))
+ return;
+
+ lock->owner = ~0;
+
+ /*
+ * Make sure all data written inside the lock is visible to
+ * other CPUs before we release the lock.
+ */
+ xnarch_memory_barrier();
+
+ /*
+ * Carefully calculate the addend so that we confine the
+ * XNLOCK_HEAD_INC just to the first byte of fifo.
+ */
+ atomic_add(((fifo + XNLOCK_HEAD_INC) & XNLOCK_TICKET_MASK) - fifo,
+ &lock->fifo);
+}
+
+#else /* ! CONFIG_XENO_OPT_TICKET_LOCK */
+
+#define XNLOCK_INIT_VALUE { ~0 }
+
+static inline int xnlock_owner(xnlock_t *lock)
+{
+ return atomic_read(&lock->owner);
+}
+
static inline int __xnlock_get(xnlock_t *lock /*, */ XNLOCK_DBG_CONTEXT_ARGS)
{
unsigned long long start;
int cpu = xnarch_current_cpu();
- if (atomic_read(&lock->owner) == cpu)
+ if (xnlock_owner(lock) == cpu)
return 1;
xnlock_dbg_prepare_acquire(&start);
@@ -356,6 +452,12 @@ static inline void xnlock_put(xnlock_t *
atomic_set(&lock->owner, ~0);
}
+#endif /* ! CONFIG_XENO_OPT_TICKET_LOCK */
+
+static inline void xnlock_init(xnlock_t *lock)
+{
+ *lock = XNARCH_LOCK_UNLOCKED;
+}
static inline spl_t
__xnlock_get_irqsave(xnlock_t *lock /*, */ XNLOCK_DBG_CONTEXT_ARGS)
@@ -386,7 +488,7 @@ static inline int xnarch_send_ipi(xnarch
static inline int xnlock_is_owner(xnlock_t *lock)
{
- return atomic_read(&lock->owner) == xnarch_current_cpu();
+ return xnlock_owner(lock) == xnarch_current_cpu();
}
#else /* !CONFIG_SMP */
Index: b/ksrc/nucleus/Kconfig
===================================================================
--- a/ksrc/nucleus/Kconfig
+++ b/ksrc/nucleus/Kconfig
@@ -340,6 +340,18 @@ config XENO_OPT_TIMER_WHEEL_STEP
Set the duration in ns of a timer wheel step. At each step,
the timer wheel use the next hash bucket.
+config XENO_OPT_TICKET_LOCK
+ bool "FIFO ticket spinlocks"
+ depends on SMP
+ help
+
+ Uses a ticket spinlock algorithm which enforces strict FIFO
+ admission order on contended locks, improving the determinism
+ of lock acquisitions on large SMP systems. The ticket spinlock
+ has a higher overhead than the unordered algorithm and should
+ therefore only be used if there are more than two CPUs, thus
+ more than one waiter in the worst case.
+
endmenu
endif
Index: b/include/asm-generic/bits/pod.h
===================================================================
--- a/include/asm-generic/bits/pod.h
+++ b/include/asm-generic/bits/pod.h
@@ -295,7 +295,7 @@ unsigned long long xnarch_get_cpu_time(v
EXPORT_SYMBOL(xnarch_get_cpu_time);
-#ifdef CONFIG_SMP
+#if defined(CONFIG_SMP) && !defined(CONFIG_XENO_OPT_TICKET_LOCK)
void __xnlock_spin(xnlock_t *lock /*, */ XNLOCK_DBG_CONTEXT_ARGS)
{
unsigned int spin_limit;
@@ -311,6 +311,6 @@ void __xnlock_spin(xnlock_t *lock /*, */
} while(atomic_read(&lock->owner) != ~0);
}
EXPORT_SYMBOL(__xnlock_spin);
-#endif /* CONFIG_SMP */
+#endif /* CONFIG_SMP && !CONFIG_XENO_OPT_TICKET_LOCK */
#endif /* !_XENO_ASM_GENERIC_BITS_POD_H */
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Xenomai-core mailing list Xenomai-core@gna.org https://mail.gna.org/listinfo/xenomai-core
