Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Fri, 8 Nov 2002 12:47:40 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Fri, 8 Nov 2002 12:47:40 -0500 Received: from dell-paw-3.cambridge.redhat.com ([195.224.55.237]:55037 "EHLO executor.cambridge.redhat.com") by vger.kernel.org with ESMTP id ; Fri, 8 Nov 2002 12:47:35 -0500 To: David Howells Cc: Jeremy Fitzhardinge , William Lee Irwin III , "Van Maren, Kevin" , linux-ia64@linuxia64.org, Linux Kernel List , rusty@rustcorp.com.au, dhowells@redhat.com, mingo@elte.hu, Linus Torvalds Subject: Re: [Linux-ia64] reader-writer livelock problem In-Reply-To: Message from David Howells of "Fri, 08 Nov 2002 17:34:43 GMT." <18894.1036776883@warthog.cambridge.redhat.com> User-Agent: EMH/1.14.1 SEMI/1.14.3 (Ushinoya) FLIM/1.14.3 (=?ISO-8859-4?Q?Unebigory=F2mae?=) APEL/10.3 Emacs/21.2 (i686-pc-linux-gnu) MULE/5.0 (SAKAKI) MIME-Version: 1.0 (generated by SEMI 1.14.3 - "Ushinoya") Content-Type: text/plain; charset=US-ASCII Date: Fri, 08 Nov 2002 17:54:15 +0000 Message-ID: <19288.1036778055@warthog.cambridge.redhat.com> From: David Howells Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 7166 Lines: 240 > 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 +#include +#include + +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 #include #include +#include #include /* - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/