reader-writer livelock problem

This is a follow-up to the email thread I started on July 29th. See http://www.cs.helsinki.fi/linux/linux-kernel/2002-30/0446.html
and the following discussion on LKML.

I'll summarize the problem again to refresh the issue. Again, this is a correctness issue, not a performance one.

I am seeing a problem on medium-sized SMPs where user programs are able to livelock the Linux kernel to such an extent that the system appears dead. With the help of some hardware debugging tools, I was able to determine that the problem is caused by the reader-preference reader/writer locks in the Linux kernel. Under "heavy" reader contention, it is possible for the writer to _never_ be able to acquire the lock since the read count never drops to zero (since some reader always loses the cacheline after acquiring the lock, and before it can release the lock, by which time another reader has the lock).

I have seen this occur with at least two different reader locks, without _trying_ to cause the problem, and I believe every reader lock that is acquired by a system call is susceptible to this problem, if the writer lock needs to be acquired by a processor.

A simple test-case is to run a process on every cpu in a gettimeofday() loop. With 16 IA64 processors doing this, the timer code takes longer to acquire the writer lock than the 1ms between the 1KHz clock ticks, which causes all the other interrupts directed to the BSP to get queued up (since the timer is higher priority). When this occurs, time "stands still" -- calling gettimeofday() takes 0 time.

My initial suggestion was to make reader/writer locks "fair" by setting a writer-pending bit. However, that proposal was not satisfactory for Linux because Linux *requires* reader-preference reader locks because reader locks can be acquired recursively, either through an explicit call-graph or an interrupt handler, since interrupts are not disabled while holding a reader lock if the interrupt handler only acquires a read lock.

There are quite a few options; I would like to hash these issues out and determine the "best" solution. The solutions, as I see them, are:

1) Implement "fair" locks while providing the required semantics. This would require pre-processor storage for the reference count, so that a processor can acquire the reader lock if it already has it (to prevent deadlock), and otherwise wait for a pending writer.
Costs: per-processor storage. Writer has to wait for all the reader reference counts to hit zero before proceeding (currently only has to wait for the one "global" reference count).

2) Implement "scalable reader-writer locks". See Wilson Hsieh's paper at http://www.psg.lcs.mit.edu/papers/RWlocks.ps
This approach also requires per-processor storage, but solves the problem in a slightly different (probably better) way.

Note that 1 and 2, in essence, convert every reader/writer lock into a "big" reader/writer lock (see lib/brlock).

The downside here, of course, is that each lock is allocated based on the compile-time constant for the maximum number of processors in the system. If a 128-byte cacheline is allocated for every processor, that results in 4KB for each reader/writer lock with just 32 processors. While the memory consumption does not disturb me, it does bother me that a driver compiled for NR_CPUS would not work with a kernel compiled with NR_CPUS2 (if there are > 16 CPUs).

The upside is that for read-mostly locks (> 99%) there is a performance improvement. Downside is that writers become more expensive in the uncontested/lightly contested case.

3) Change the kernel to not allow reader locks to be acquired recursively. This change would bring Linux into line with most other Unix-like operating systems, but requires a change in the locking mentality and could be difficult to get right at this stage. Long term, it is the most appealing to me, even though it makes reader locks more expensive because interrupts have to be disabled more frequently.

4) Change the reader/writer locks to be a recursive spinlock:
have a reference count and an "owner". Processor can only acquire the lock if a) reference count is 0, or b) reference count is > 0 but it is the owner.

This change would only allow a single processor to be in the critical section, but would allow it to recursively reenter. This approach would not increase the storage requirements, and would eliminate parallelism, but would guarantee fairness (and slow is better than never).

5) Combination of 3&4: have "compatible" reader/writer locks that act as #4, and new reader-writer locks that are fair (#3), but cannot be acquired recursivly.

6) Some heuristic "hack" involving exponential backoff if a writer is pending. Not "guaranteed" to work. If a writer is pending, wait before trying to acquire the lock. Problem is that a cpu that already holds the reader lock will also delay before acquiring the lock, even though it is the reason the writer cannot acquire the lock.

The delays to use are going to be highly platform-specific and also depend on the size of the critical section.

Other heuristics, such as using a per-processor reader-lock count, fall apart when the contended lock is not the first one acquired by the processor.

7) ???

I did implement #2 (without the gate MCS lock) on 2.4.x for IA64; combined with the NMCS patch from IBM, I was unable to "hang" the system. For my prototype, I converted the big reader locks into "normal" reader locks, since the regular locks now provided the big-reader functionality. There is still a lot of low-hanging fruit in the prototype, but I just wanted to get something working.

The performance impact was negligible for a single processor, where gettimeofday() ran about as fast, while stat() was around 0.2us (10%) slower. However, with 16 processors, gettimeofday did not kill the clock, and stat() performance increased more than 5X, but the big win was that the execution time was bounded: no enormous outliers. Note that with one processor, gettimeofday() was called around 1200 times between clock ticks, and about the same as a 16X (each call took longer on average) with the new locking code.

Kevin Van Maren

The normal way of solving this fairness problem is to make pending write locks block read lock attempts, so that the reader count is guaranteed to drop to zero as read locks are released. I haven't looked at the Linux implementation of rwlocks, so I don't know how hard this is to do. Or perhaps there's some other reason for not implementing it this way?

J

There's another reason for not doing it that way: allowing readers to keep interrupts on even in the presense of interrupt uses of readers.

If you do the "pending writes stop readers" approach, you get

cpu1 cpu2

read_lock() - get

write_lock_irq() - pending

irq happens
- read_lock() - deadlock

and that means that you need to make readers protect against interrupts even if the interrupts only read themselves.

NOTE! I'm not saying the existing practice is necessarily a good tradeoff, and maybe we should just make sure to find all such cases and turn the read_lock() calls into read_lock_irqsave() and then make the rw-locks block readers on pending writers. But it's certainly more work and cause for subtler problems than just naively changing the rw implementation.

Linus

Actually, giving this som emore thought, I really suspect that the simplest solution is to alloc a separate "fair_read_lock()", and paths that need to care about fairness (and know they don't have the irq issue) can use that, slowly porting users over one by one...

Linus

Actually implementing a fair spinlocks and fair rwlocks on the x86 arch are very easy (at least, if you have XADD it is). Any arch which has CMPXCHG can also do it, just not so easily.

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).

David

typedef struct fairlock {
	u8	curr;
	u8	ticket;
} fairlock_t;

static inline init_fairlock(fairlock_t *lock)

{
	memset(lock,0,sizeof(*lock));
}

/*
* 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)

{
	u8 number;

	__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");
}

/* rwlock.c: fair read/write spinlocks
*
* Copyright (c) 2002 David Howells ([email protected]).
*/

#include <linux/types.h>

typedef unsigned char u8;
typedef unsigned int u32;

#define LOCK_PREFIX "lock;"

typedef struct rwlock {

/* 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))) rwlock_t;

#define RWLOCK_UNLOCKED (rwlock_t) { 0, 0, 0, 0 }

#define rwlock_debug(LOCK,WHERE) \

do {											\
	printf(WHERE"{%02x,%02x,%02x}\n",LOCK->rd_curr,LOCK->curr,LOCK->ticket);	\
} while(0)

/*
* 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 write_lock(rwlock_t *lock)

{
	u32 eax;

	rwlock_debug(lock,"-->write_lock");

	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"
		);

	rwlock_debug(lock,"<--write_lock");
}

/*
* 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 write_unlock(rwlock_t *lock)

{
	u32 eax;

	rwlock_debug(lock,"-->write_unlock");

	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"
		);

	rwlock_debug(lock,"<--write_unlock");
}

/*
* 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 read_lock(rwlock_t *lock)

{
	u32 eax;

	rwlock_debug(lock,"-->read_lock");

	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"
		);

	rwlock_debug(lock,"<--read_lock");
}

/*
* release a read lock
* - just advance the lock->curr count so that any spinning write lock can happen */
static inline void read_unlock(rwlock_t *lock)

{
	rwlock_debug(lock,"-->read_unlock");

	asm volatile(
		"	# begin read_unlock	\n"
LOCK_PREFIX	"	incb	%0		\n"	/* lock->curr++ */
		"	# end read_unlock	\n"
		: "=m"(lock->curr)
		: "m"(lock->curr)
		: "cc"
		);

	rwlock_debug(lock,"<--read_unlock");
}

/*****************************************************************************/ /*
* testing stuff
*/
rwlock_t mylock = RWLOCK_UNLOCKED;

#define wibble() asm("nop")

void get_read_lock(void)

{
	wibble();
	read_lock(&mylock);
	read_lock(&mylock);
	read_unlock(&mylock);
	wibble();
	read_lock(&mylock);
	read_unlock(&mylock);
	read_unlock(&mylock);
	wibble();
}

void get_write_lock(void)

{
	wibble();
	write_lock(&mylock);
	wibble();
	write_unlock(&mylock);
	wibble();
}

int main()

{
	get_read_lock();
	get_write_lock();
	get_write_lock();
	get_read_lock();
	return 0;
}

Even without interrupts that would be a bug. It isn't ever safe to attempt to retake a read lock if you already hold it, because you may deadlock with a pending writer. Fair multi-reader locks aren't recursive locks.

Yes, I'd agree. It would definitely be a behavioural change with respect to the legality of retaking a lock for reading, which would probably be quite irritating to find (since they'd only cause a problem if they actually coincide with an attempted write lock).

Do you mean have a separate lock type, or have two different read_lock operations on the current type?

J

Yes, that was one of the options I suggested in the original post to the IA64 list. I'll bounce it to LKML for reference, now that the discussion has moved there.

In my proposal, however, I proposed making (the current) reader locks recursive spinlocks (to eliminate the starvation problem, at the expense of eliminating reader parallelism), which would have the added benefit of "encouraging" people to move to the fair locks. But your proposal is probably at least as good.

Of course, normal spinlocks do not scale either, since they currently require N cache-cache transfers for a processor to drop the lock, which results in N^2 cache transfers for each processor to acquire/release the lock once. So with 32 processors contending for the lock, at 1us per cache-cache transfer (picked for easy math, but that is reasonable for large systems), it takes 1ms for each processor to acquire the spinlock and hold it for 10 cpu cycles.

So I'd _also_ like to see an MCS lock implementation replace the current spinlock code (IBM "NMCS" lock patch can be trivially used to replace all spinlocks).

Kevin

-----Original Message-----
From: Linus Torvalds
To: Jeremy Fitzhardinge
Cc: William Lee Irwin III; Van Maren, Kevin; [email protected]; Linux Kernel List; [email protected]; [email protected]; [email protected]
Sent: 11/8/02 12:28 PM
Subject: Re: [Linux-ia64] reader-writer livelock problem

tradeoff,

cause

Actually, giving this som emore thought, I really suspect that the simplest solution is to alloc a separate "fair_read_lock()", and paths that need to care about fairness (and know they don't have the irq issue)
can use that, slowly porting users over one by one...

Linus

You'd probably be better off with separate types... that way you can avoid problems with conditionals and also with different tracking fields being required by each grade of lock.

David

if you have 32 processors contending for the same spinlock, you have bigger problems.

Revolutions do not require corporate support.

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
@@ -0,0 +1,210 @@
+/* fairlock.h: fair spinlocks
+ *
+ * Copyright (C) 2002 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells ([email protected])
+ *
+ * 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
@@ -4,6 +4,7 @@
 #include <asm/atomic.h>
 #include <asm/rwlock.h>
 #include <asm/page.h>
+#include <asm/fairlock.h>
 #include <linux/config.h>
 
 /*

There are a selection of similar algorithms here:
http://www.cs.rochester.edu/u/scott/synchronization/pseudocode/rw.html#s_f

How does yours compare?

Absolutely you should minimize the locking contention. However, that isn't always possible, such as when you have 64 processors contending on the same resource. With the current kernel, the trivial example with reader/ writer locks was having them all call gettimeofday(). But try having 64 processors fstat() the same file, which I have also seen happen (application looping, waiting for another process to finish setting up the file so they can all mmap it).

What MCS locks do is they reduce the number of times the cacheline has to be flung around the system in order to get work done: they "scale" much better with the number of processors: O(N) instead of O(N^2).

Kevin

-----Original Message-----
From: Matthew Wilcox
To: Van Maren, Kevin
Cc: 'Linus Torvalds '; 'Jeremy Fitzhardinge '; 'William Lee Irwin III '; '[email protected] '; 'Linux Kernel List '; '[email protected] '; '[email protected] '; '[email protected] '
Sent: 11/8/02 12:52 PM
Subject: Re: [Linux-ia64] reader-writer livelock problem

if you have 32 processors contending for the same spinlock, you have bigger problems.

Revolutions do not require corporate support.

if you've got 64 processors contending on the same resource, maybe you need to split that resource up so they can have a copy each. all that cacheline bouncing can't do your numa boxes any good.

i hear x86-64 has a lockless gettimeofday. maybe that's the solution.

umm.. the call trace:

sys_fstat

|-> vfs_fstat
|   |-> fget
|	|-> read_lock(&files->file_lock)
|   |-> vfs_getattr
|	|-> inode->i_op->getattr
|	|-> generic_fillattr
|-> cp_new_stat64
    |-> memset
    |-> copy_to_user

so you're talking about contention on files->file_lock, right? it's really not the kernel's fault that your app is badly written. that lock's private to process & children, so it's not like another application can hurt you.

yes, but how slow are they in the uncontended case?

Revolutions do not require corporate support.

Matthew> On Fri, Nov 08, 2002 at 12:05:30PM -0600, Van Maren, Kevin

Matthew> if you've got 64 processors contending on the same Matthew> resource, maybe you need to split that resource up so they Matthew> can have a copy each. all that cacheline bouncing can't do Matthew> your numa boxes any good.

Matthew, please understand that this is NOT a performance problem. It's a correctness problem. If livelock can resolut from read-write locks, it's a huge security problem. Period.

	--david

It happens even on our non-NUMA boxes. But that was the reason behind developing MCS locks: they are designed to minimize the cacheline bouncing due to lock contention, and become a win with a very small number of processors contending the same spinlock.

I was using gettimeofday() as ONE example of the problem. Fixing gettimeofday(), such as with frlocks (see, for example,
http://lwn.net/Articles/7388) fixes ONE occurance of the problem.

Every reader/writer lock that an application can force the kernel to acquire can have this problem. If there is enough time between acquires, it may take 32 or 64 processors to hang the system, but livelock WILL occur.

There are MANY other cases where an application can force the kernel to acquire a lock needed by other things. The point is not whether the *application* is badly written, but point is whether a bad application can mess up the kernel by causing a livelock.

Spinlocks are a slightly different story. While there isn't the starvation issue, livelock can still occur if the kernel needs to acquire the spinlock more often that it takes to acquire. This is why replacing the xtime_lock with a spinlock fixes the reader/writer livelock, but not the problem: while the writer can now get the spinlock, it can take an entire clock tick to acquire/release it. So the net behavior is the
same: with a 1KHz timer and with 1us cache-cache latency, 32 processors spinning on gettimeofday() using a spinlock would have a similar result.

Kevin

that's not my point... a resource occupies a number of cachelines; bouncing those cachelines between processors is expensive. if there's a real workload that all the processors are contending for the same resource, it's time to split up that resource.

not true. every reader/writer lock which guards a global resource can have this problem. if the lock only guards your own task's resources, there can be no problem.

and i agree they should be fixed.

right. so spinlocking this resource is also not good enough. did you see the "Voyager subarchitecture for 2.5.46" thread earlier this week which discussed making it per-cpu?
http://www.uwsg.iu.edu/hypermail/linux/kernel/0211.0/1799.html
this seems like the right way to go to me.

Revolutions do not require corporate support.

In message <[email protected]> you write:

That's the point. This is explicitly guaranteed with the current locks, and you are allowed to recurse on them. The netfilter code explicitly uses this to retake the net brlock, since it gets called from different paths.

Implement "read_lock_yield" or "wrlock_t" but don't break existing semantics until 2.7 *please*!

Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

From what I understand this is a huge security risk - any mischevious user can hang the system. Practically speaking its a hard sell to tell any customer that in 2.7 the problem will be fixed and hope that it doesnt happen before then. Is there any way to prevent the user (non-root) from exploiting this weakness? In order for this to happen do all the CPUs have to run at 100%? I know that on some commercial Unix systems there are ways to cap the CPU utilization by user/group ids are there such features/patches available
on Linux?

- Mario.

I took a look and it appears pretty encouraging. I guess the final question would be - with CPU caps imposed on non-root users would that prevent a user from livelocking the system? I don't recall how long
it took for the system to livelock (I erased the original email), there may be an oppertunity for livelock to develop before the PRM policies kick in.

- Mario.