Re: [Linux-ia64] reader-writer livelock problem

David Howells
2002-11-08T17:47:40Z

> I've attached an implementation of a fair spinlock and an implementation of a
> fair rwlock (which can be compiled and played with in u-space).

For those that prefer patches (or at least something that'll compile without
warnings)...

David

diff -uNr linux-2.5.46/include/asm-i386/fairlock.h linux-fair-2546/include/asm-i386/fairlock.h
--- linux-2.5.46/include/asm-i386/fairlock.h 1970-01-01 01:00:00.000000000 +0100
+++ linux-fair-2546/include/asm-i386/fairlock.h 2002-11-08 17:51:30.000000000 +0000
@@ -0,0 +1,210 @@
+/* fairlock.h: fair spinlocks
+ *
+ * Copyright (C) 2002 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * 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
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#ifndef _ASM_FAIRLOCK_H
+#define _ASM_FAIRLOCK_H
+
+#include <linux/config.h>
+#include <linux/string.h>
+#include <asm/atomic.h>
+
+typedef struct fairlock {
+ u8 curr;
+ u8 ticket;
+} fairlock_t;
+
+static inline void init_fairlock(fairlock_t *lock)
+{
+ memset(lock,0,sizeof(*lock));
+}
+
+typedef struct rwfairlock {
+
+ /* these member variables must be at the beginning and in this order */
+ u8 rd_curr; /* next reader ticket allowed to become active */
+ u8 curr; /* currently active ticket */
+ u8 ticket; /* next ticket to be issued */
+ u8 __pad;
+
+} __attribute__((aligned(4))) rwfairlock_t;
+
+#define RWFAIRLOCK_UNLOCKED (rwfairlock_t) { 0, 0, 0, 0 }
+
+/*****************************************************************************/
+/*
+ * spin lock fairly
+ */
+static inline void fair_lock(fairlock_t *lock)
+{
+ u8 number = 1;
+
+ __asm__ __volatile__(
+ "# beginning fair_lock\n\t"
+LOCK_PREFIX " xaddb %b2,%1\n\t" /* number = lock->ticket; lock->ticket++; */
+ "1:\n\t"
+ " cmpb %b2,%0\n\t"
+ " jne 2f\n\t" /* jump if number!=lock->curr */
+ LOCK_SECTION_START("")
+ "2:\n\t"
+ " rep; nop\n\t"
+ " jmp 1b\n"
+ LOCK_SECTION_END
+ "# ending fair_lock\n\t"
+ : "=m"(lock->curr), "=m"(lock->ticket), "=r"(number)
+ : "r"(lock), "m"(lock->curr), "m"(lock->ticket), "2"(number)
+ : "memory", "cc");
+}
+
+/*****************************************************************************/
+/*
+ * spin trylock fairly
+ */
+static inline void fair_trylock(fairlock_t *lock)
+{
+ u32 tmp;
+
+ __asm__ __volatile__(
+ "# beginning fair_trylock\n\t"
+ " movw (%3),%%ax\n\t" /* AL=curr, AH=ticket */
+ "1:\n\t"
+ " cmpb %%al,%%ah\n\t"
+ " je 3f\n\t" /* jump if maybe we can get it */
+ "2:\n\t"
+ LOCK_SECTION_START("")
+ "3:\n\t"
+ " leaw 1(%ax),%w2\n\t" /* [propose] ticket=ticket+1 */
+LOCK_PREFIX " cmpxchgw %w2,(%3)\n\t"
+ " je 3b\n\t" /* jump if worked */
+ " rep; nop\n\t" /* didn't work; AL & AH have been updated */
+ " jmp 1b\n"
+ LOCK_SECTION_END
+ "# ending fair_trylock\n\t"
+ : "=m"(lock->curr), "=m"(lock->ticket), "=$r"(tmp)
+ : "r"(lock), "m"(lock->curr), "m"(lock->ticket)
+ : "memory", "cc", "eax");
+}
+
+/*****************************************************************************/
+/*
+ * spin unlock fairly
+ */
+static inline void fair_unlock(fairlock_t *lock)
+{
+ __asm__ __volatile__(
+ "# beginning fair_unlock\n\t"
+LOCK_PREFIX " incb %1\n\t" /* lock->curr++; */
+ "# ending fair_unlock\n\t"
+ : "=m"(lock->curr)
+ : "r"(lock), "m"(lock->curr)
+ : "memory", "cc");
+}
+
+/*****************************************************************************/
+/*
+ * obtain a write lock
+ * - pull the next ticket from lock->ticket (which is subsequently incremented)
+ * - spin until lock->curr catches up to the value that lock->ticket had before the XADD
+ * - lock->rd_curr is left equal to the lock->curr (and thus my ticket number) to prevent reads
+ * getting a lock
+ */
+static inline void fair_write_lock(rwfairlock_t *lock)
+{
+ u32 eax;
+
+ asm volatile(
+ " # begin write_lock \n"
+LOCK_PREFIX " xaddw %%ax,1(%3) \n" /* my ticket in AH */
+ "0: cmpb %%al,%%ah \n" /* lock->curr in AL */
+ " jne 2f \n"
+ " .section .text.lock,\"ax\"\n"
+ "2: \n"
+ " rep; nop \n"
+ " movb 1(%3),%%al \n" /* reload AL from lock->curr */
+ " jmp 0b \n"
+ " .previous \n"
+ " # end write_lock \n"
+ : "=m"(lock), "=a"(eax)
+ : "m"(lock), "r"(lock), "a"(0x0100)
+ : "memory", "cc"
+ );
+}
+
+/*****************************************************************************/
+/*
+ * release a write lock
+ * - advance both lock->rd_curr and lock->curr by one to enable the next lock to be granted
+ */
+static inline void fair_write_unlock(rwfairlock_t *lock)
+{
+ u32 eax;
+
+ asm volatile(
+ " # begin write_unlock \n"
+ " movw 0(%3),%%ax \n"
+ " incb %%al \n" /* lock->rd_curr++ */
+ " incb %%ah \n" /* lock->curr++ */
+ " movw %%ax,0(%3) \n"
+ " # end write_unlock \n"
+ : "=m"(lock), "=&a"(eax)
+ : "m"(lock), "r"(lock)
+ : "cc"
+ );
+}
+
+/*****************************************************************************/
+/*
+ * obtain a read lock
+ * - pull the next ticket from lock->ticket (which is subsequently incremented)
+ * - spin until lock->rd_curr catches up to the value that lock->ticket had before the XADD
+ * - lock->rd_curr is then advanced by one to allow the next read lock to be granted
+ * - lock->curr is irrelevant
+ */
+static inline void fair_read_lock(rwfairlock_t *lock)
+{
+ u32 eax;
+
+ asm volatile(
+ " # begin read_lock \n"
+LOCK_PREFIX " xaddb %%ah,2(%3) \n" /* my ticket in AH */
+ "0: movb 0(%3),%%al \n" /* AL = lock->rd_curr */
+ " cmpb %%al,%%ah \n" /* if (ticket!=lock->rd_curr) */
+ " jne 2f \n" /* then jump */
+ " incb 0(%3) \n" /* lock->rd_curr */
+ " .section .text.lock,\"ax\"\n"
+ "2: \n"
+ " rep; nop \n"
+ " jmp 0b \n"
+ " .previous \n"
+ " # end read_lock \n"
+ : "=m"(lock), "=a"(eax)
+ : "m"(lock), "r"(lock), "a"(0x0100)
+ : "memory", "cc"
+ );
+}
+
+/*****************************************************************************/
+/*
+ * release a read lock
+ * - just advance the lock->curr count so that any spinning write lock can happen
+ */
+static inline void read_unlock(rwfairlock_t *lock)
+{
+ asm volatile(
+ " # begin read_unlock \n"
+LOCK_PREFIX " incb %0 \n" /* lock->curr++ */
+ " # end read_unlock \n"
+ : "=m"(lock->curr)
+ : "m"(lock->curr)
+ : "cc"
+ );
+}
+
+#endif /* _ASM_FAIRLOCK_H */
diff -uNr linux-2.5.46/include/asm-i386/spinlock.h linux-fair-2546/include/asm-i386/spinlock.h
--- linux-2.5.46/include/asm-i386/spinlock.h 2002-10-15 10:12:35.000000000 +0100
+++ linux-fair-2546/include/asm-i386/spinlock.h 2002-11-08 17:50:39.000000000 +0000
@@ -4,6 +4,7 @@
#include <asm/atomic.h>
#include <asm/rwlock.h>
#include <asm/page.h>
+#include <asm/fairlock.h>
#include <linux/config.h>

/*