From: David Howells <dhowells@cambridge.redhat.com>
To: David Howells <dhowells@cambridge.redhat.com>
Cc: Jeremy Fitzhardinge <jeremy@goop.org>,
William Lee Irwin III <wli@holomorphy.com>,
"Van Maren, Kevin" <kevin.vanmaren@unisys.com>,
linux-ia64@linuxia64.org,
Linux Kernel List <linux-kernel@vger.kernel.org>,
rusty@rustcorp.com.au, dhowells@redhat.com, mingo@elte.hu,
Linus Torvalds <torvalds@transmeta.com>
Subject: Re: [Linux-ia64] reader-writer livelock problem
Date: Fri, 08 Nov 2002 17:54:15 +0000 [thread overview]
Message-ID: <19288.1036778055@warthog.cambridge.redhat.com> (raw)
In-Reply-To: Message from David Howells <dhowells@cambridge.redhat.com> of "Fri, 08 Nov 2002 17:34:43 GMT." <18894.1036776883@warthog.cambridge.redhat.com>
> 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>
/*
next prev parent reply other threads:[~2002-11-08 17:47 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <3FAD1088D4556046AEC48D80B47B478C0101F4E7@usslc-exch-4.slc.unisys.com>
2002-11-08 3:51 ` [Linux-ia64] reader-writer livelock problem William Lee Irwin III
2002-11-08 17:13 ` Jeremy Fitzhardinge
2002-11-08 17:25 ` Linus Torvalds
2002-11-08 17:28 ` Linus Torvalds
2002-11-08 17:38 ` Jeremy Fitzhardinge
2002-11-08 17:43 ` David Howells
2002-11-08 17:57 ` Linus Torvalds
2002-11-09 2:48 ` Rusty Russell
2002-11-09 4:36 ` William Lee Irwin III
[not found] ` <3DCFDAE9.6D359448@email.mot.com>
2002-11-11 19:22 ` David Mosberger
2002-11-12 1:39 ` your mail Rik van Riel
2002-11-08 17:34 ` [Linux-ia64] reader-writer livelock problem David Howells
2002-11-08 17:54 ` David Howells [this message]
2002-11-08 17:55 ` Stephen Hemminger
2002-11-08 17:41 Van Maren, Kevin
2002-11-08 17:52 ` Matthew Wilcox
2002-11-08 18:05 Van Maren, Kevin
2002-11-08 19:19 ` Matthew Wilcox
2002-11-08 19:26 ` David Mosberger
2002-11-08 20:17 Van Maren, Kevin
2002-11-08 20:39 ` Matthew Wilcox
2002-11-08 20:24 Van Maren, Kevin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=19288.1036778055@warthog.cambridge.redhat.com \
--to=dhowells@cambridge.redhat.com \
--cc=dhowells@redhat.com \
--cc=jeremy@goop.org \
--cc=kevin.vanmaren@unisys.com \
--cc=linux-ia64@linuxia64.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@elte.hu \
--cc=rusty@rustcorp.com.au \
--cc=torvalds@transmeta.com \
--cc=wli@holomorphy.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).