[PATCH] Remove rwsem limitation of 32k waiters

[PATCH] Remove rwsem limitation of 32k waiters

[Christoph Lameter]

We ran into the limit with the maximum number of waiters at one of our sites.

This patch increases the number of possible waiters from 2^15 to 2^31 by using
a long for the counter in struct rw_semaphore.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.13-rc6/include/asm-ia64/rwsem.h
=================================--- linux-2.6.13-rc6.orig/include/asm-ia64/rwsem.h	2005-08-07 11:18:56.000000000 -0700
+++ linux-2.6.13-rc6/include/asm-ia64/rwsem.h	2005-08-22 12:17:13.000000000 -0700
@@ -3,6 +3,7 @@
  *
  * Copyright (C) 2003 Ken Chen <kenneth.w.chen@intel.com>
  * Copyright (C) 2003 Asit Mallick <asit.k.mallick@intel.com>
+ * Copyright (C) 2005 Christoph Lameter <clameter@sgi.com>
  *
  * Based on asm-i386/rwsem.h and other architecture implementation.
  *
@@ -11,9 +12,9 @@
  *
  * The lock count is initialized to 0 (no active and no waiting lockers).
  *
- * When a writer subtracts WRITE_BIAS, it'll get 0xffff0001 for the case
- * of an uncontended lock. Readers increment by 1 and see a positive value
- * when uncontended, negative if there are writers (and maybe) readers
+ * When a writer subtracts WRITE_BIAS, it'll get 0xffffffff00000001 for
+ * the case of an uncontended lock. Readers increment by 1 and see a positive
+ * value when uncontended, negative if there are writers (and maybe) readers
  * waiting (in which case it goes to sleep).
  */
 
@@ -29,7 +30,7 @@
  * the semaphore definition
  */
 struct rw_semaphore {
-	signed int		count;
+	signed long		count;
 	spinlock_t		wait_lock;
 	struct list_head	wait_list;
 #if RWSEM_DEBUG
@@ -37,10 +38,10 @@ struct rw_semaphore {
 #endif
 };
 
-#define RWSEM_UNLOCKED_VALUE		0x00000000
-#define RWSEM_ACTIVE_BIAS		0x00000001
-#define RWSEM_ACTIVE_MASK		0x0000ffff
-#define RWSEM_WAITING_BIAS		(-0x00010000)
+#define RWSEM_UNLOCKED_VALUE		__IA64_UL_CONST(0x0000000000000000)
+#define RWSEM_ACTIVE_BIAS		__IA64_UL_CONST(0x0000000000000001)
+#define RWSEM_ACTIVE_MASK		__IA64_UL_CONST(0x00000000ffffffff)
+#define RWSEM_WAITING_BIAS		-__IA64_UL_CONST(0x0000000100000000)
 #define RWSEM_ACTIVE_READ_BIAS		RWSEM_ACTIVE_BIAS
 #define RWSEM_ACTIVE_WRITE_BIAS		(RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
 
@@ -83,7 +84,7 @@ init_rwsem (struct rw_semaphore *sem)
 static inline void
 __down_read (struct rw_semaphore *sem)
 {
-	int result = ia64_fetchadd4_acq((unsigned int *)&sem->count, 1);
+	long result = ia64_fetchadd8_acq((unsigned long *)&sem->count, 1);
 
 	if (result < 0)
 		rwsem_down_read_failed(sem);
@@ -95,7 +96,7 @@ __down_read (struct rw_semaphore *sem)
 static inline void
 __down_write (struct rw_semaphore *sem)
 {
-	int old, new;
+	long old, new;
 
 	do {
 		old = sem->count;
@@ -112,7 +113,7 @@ __down_write (struct rw_semaphore *sem)
 static inline void
 __up_read (struct rw_semaphore *sem)
 {
-	int result = ia64_fetchadd4_rel((unsigned int *)&sem->count, -1);
+	long result = ia64_fetchadd8_rel((unsigned long *)&sem->count, -1);
 
 	if (result < 0 && (--result & RWSEM_ACTIVE_MASK) = 0)
 		rwsem_wake(sem);
@@ -124,7 +125,7 @@ __up_read (struct rw_semaphore *sem)
 static inline void
 __up_write (struct rw_semaphore *sem)
 {
-	int old, new;
+	long old, new;
 
 	do {
 		old = sem->count;
@@ -141,7 +142,7 @@ __up_write (struct rw_semaphore *sem)
 static inline int
 __down_read_trylock (struct rw_semaphore *sem)
 {
-	int tmp;
+	long tmp;
 	while ((tmp = sem->count) >= 0) {
 		if (tmp = cmpxchg_acq(&sem->count, tmp, tmp+1)) {
 			return 1;
@@ -156,7 +157,7 @@ __down_read_trylock (struct rw_semaphore
 static inline int
 __down_write_trylock (struct rw_semaphore *sem)
 {
-	int tmp = cmpxchg_acq(&sem->count, RWSEM_UNLOCKED_VALUE,
+	long tmp = cmpxchg_acq(&sem->count, RWSEM_UNLOCKED_VALUE,
 			      RWSEM_ACTIVE_WRITE_BIAS);
 	return tmp = RWSEM_UNLOCKED_VALUE;
 }
@@ -167,7 +168,7 @@ __down_write_trylock (struct rw_semaphor
 static inline void
 __downgrade_write (struct rw_semaphore *sem)
 {
-	int old, new;
+	long old, new;
 
 	do {
 		old = sem->count;
@@ -182,7 +183,7 @@ __downgrade_write (struct rw_semaphore *
  * Implement atomic add functionality.  These used to be "inline" functions, but GCC v3.1
  * doesn't quite optimize this stuff right and ends up with bad calls to fetchandadd.
  */
-#define rwsem_atomic_add(delta, sem)	atomic_add(delta, (atomic_t *)(&(sem)->count))
-#define rwsem_atomic_update(delta, sem)	atomic_add_return(delta, (atomic_t *)(&(sem)->count))
+#define rwsem_atomic_add(delta, sem)	atomic64_add(delta, (atomic64_t *)(&(sem)->count))
+#define rwsem_atomic_update(delta, sem)	atomic64_add_return(delta, (atomic64_t *)(&(sem)->count))
 
 #endif /* _ASM_IA64_RWSEM_H */

Re: [PATCH] Remove rwsem limitation of 32k waiters

[Matthew Wilcox]

On Mon, Aug 22, 2005 at 12:20:13PM -0700, Christoph Lameter wrote:
> We ran into the limit with the maximum number of waiters at one of our sites.
> 
> This patch increases the number of possible waiters from 2^15 to 2^31 by using
> a long for the counter in struct rw_semaphore.

Why not just change the BIAS value to 0x0010000?  As long as you don't
have more than 1024 processors trying to simultaneously acquire the same
write lock (and if you do, you have other problems ...), this won't fail
and gives you 2^19 waiters.

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: [PATCH] Remove rwsem limitation of 32k waiters

[Christoph Lameter]

On Mon, 22 Aug 2005, Matthew Wilcox wrote:

> On Mon, Aug 22, 2005 at 12:20:13PM -0700, Christoph Lameter wrote:
> > We ran into the limit with the maximum number of waiters at one of our sites.
> > 
> > This patch increases the number of possible waiters from 2^15 to 2^31 by using
> > a long for the counter in struct rw_semaphore.
> 
> Why not just change the BIAS value to 0x0010000?  As long as you don't
> have more than 1024 processors trying to simultaneously acquire the same
> write lock (and if you do, you have other problems ...), this won't fail
> and gives you 2^19 waiters.

The same approach was already chosen by s390 and alpha.

Changing the bias value reduces the maximum number of waiting 
processes as you noted. Note "processes" not processors. One processor can 
have multiple processes waiting on semaphores. These are not spinlocks.

Re: [PATCH] Remove rwsem limitation of 32k waiters

[Matthew Wilcox]

On Mon, Aug 22, 2005 at 12:38:45PM -0700, Christoph Lameter wrote:
> On Mon, 22 Aug 2005, Matthew Wilcox wrote:
> > Why not just change the BIAS value to 0x0010000?  As long as you don't
> > have more than 1024 processors trying to simultaneously acquire the same
> > write lock (and if you do, you have other problems ...), this won't fail
> > and gives you 2^19 waiters.
> 
> The same approach was already chosen by s390 and alpha.
> 
> Changing the bias value reduces the maximum number of waiting 
> processes as you noted. Note "processes" not processors. One processor can 
> have multiple processes waiting on semaphores. These are not spinlocks.

No, but you didn't look at the implementation in lib/rwsem.c.

static inline struct rw_semaphore *
rwsem_down_failed_common(struct rw_semaphore *sem,
                        struct rwsem_waiter *waiter, signed long adjustment)
...
        /* we're now waiting on the lock, but no longer actively read-locking */
        count = rwsem_atomic_update(adjustment, sem);

struct rw_semaphore fastcall __sched *
rwsem_down_write_failed(struct rw_semaphore *sem)
...
        rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_BIAS);

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: [PATCH] Remove rwsem limitation of 32k waiters

[Christoph Lameter]

On Mon, 22 Aug 2005, Matthew Wilcox wrote:

> > Changing the bias value reduces the maximum number of waiting 
> > processes as you noted. Note "processes" not processors. One processor can 
> > have multiple processes waiting on semaphores. These are not spinlocks.
> 
> No, but you didn't look at the implementation in lib/rwsem.c.
> 
> static inline struct rw_semaphore *
> rwsem_down_failed_common(struct rw_semaphore *sem,
>                         struct rwsem_waiter *waiter, signed long adjustment)
> ...
>         /* we're now waiting on the lock, but no longer actively read-locking */
>         count = rwsem_atomic_update(adjustment, sem);

The adjustment is RWSEM_WAITING_BIAS - RWSEM_ACTIVE bias. This eliminates
the RWSEM_ACTIVE_BIAS but adds RWSEM_WAITING_BIAS for each waiter.

Re: [PATCH] Remove rwsem limitation of 32k waiters

[Matthew Wilcox]

On Mon, Aug 22, 2005 at 01:26:17PM -0700, Christoph Lameter wrote:
> The adjustment is RWSEM_WAITING_BIAS - RWSEM_ACTIVE bias. This eliminates
> the RWSEM_ACTIVE_BIAS but adds RWSEM_WAITING_BIAS for each waiter.

You're looking at rwsem_down_read_failed() instead of rwsem_down_write_failed()

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: [PATCH] Remove rwsem limitation of 32k waiters

[Christoph Lameter]

On Mon, 22 Aug 2005, Matthew Wilcox wrote:

> On Mon, Aug 22, 2005 at 01:26:17PM -0700, Christoph Lameter wrote:
> > The adjustment is RWSEM_WAITING_BIAS - RWSEM_ACTIVE bias. This eliminates
> > the RWSEM_ACTIVE_BIAS but adds RWSEM_WAITING_BIAS for each waiter.
> 
> You're looking at rwsem_down_read_failed() instead of rwsem_down_write_failed()

down_write already adds RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS in 
include/asm-ia64/rwsem.h. It only removes RW_SEM_WAITING_BIAS when it 
fails. So the net outcome is that a writer also adds RWSEM_WAITING_BIAS to 
count.

RE: [PATCH] Remove rwsem limitation of 32k waiters

[Chen, Kenneth W]

Christoph Lameter wrote on Monday, August 22, 2005 1:34 PM
> On Mon, 22 Aug 2005, Matthew Wilcox wrote:
> > On Mon, Aug 22, 2005 at 01:26:17PM -0700, Christoph Lameter wrote:
> > > The adjustment is RWSEM_WAITING_BIAS - RWSEM_ACTIVE bias. This
eliminates
> > > the RWSEM_ACTIVE_BIAS but adds RWSEM_WAITING_BIAS for each waiter.
> > 
> > You're looking at rwsem_down_read_failed() instead of
rwsem_down_write_failed()
> 
> down_write already adds RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS in 
> include/asm-ia64/rwsem.h. It only removes RW_SEM_WAITING_BIAS when it 
> fails. So the net outcome is that a writer also adds
RWSEM_WAITING_BIAS to 
> count.

The upper bits are used to count number of waiter, and the lower bits
are
used to count number of active locks.  I don't see anything wrong with
Matthew's
earlier suggestion, except the bits were wrong in his original post.
How about:

#define RWSEM_ACTIVE_MASK               0x00000fff
#define RWSEM_WAITING_BIAS              (-0x00001000)

which gives you roughly 20 bits for number of waiter, at the expense of
reducing
number of uncontended reader to 12 bits. Or you can do 18/14 bits
breakdown. Will
that work?

By the way, you must have an app of the devil to trigger the overflow,
at ~64K
rwsem waiter?

- Ken

RE: [PATCH] Remove rwsem limitation of 32k waiters

[Christoph Lameter]

On Tue, 23 Aug 2005, Chen, Kenneth W wrote:

> #define RWSEM_ACTIVE_MASK               0x00000fff
> #define RWSEM_WAITING_BIAS              (-0x00001000)

Correct. Thatis going to shift it the right way.

> which gives you roughly 20 bits for number of waiter, at the expense of
> reducing
> number of uncontended reader to 12 bits. Or you can do 18/14 bits
> breakdown. Will
> that work?

Maybe but this is still cutting it too close for my taste since we have 
ever increasing numbers of processors. s390 and alpha already use a 64bit 
value there and we are 64 bit as well. Lets just adopt the same approach 
to be sure that we wont run into these limitations again.
 
> By the way, you must have an app of the devil to trigger the overflow,
> at ~64K
> rwsem waiter?

Its an extreme case I agree.

The patch is okay?

RE: [PATCH] Remove rwsem limitation of 32k waiters

[Chen, Kenneth W]

Christoph Lameter wrote on Tuesday, August 23, 2005 6:40 AM
> > By the way, you must have an app of the devil to trigger the overflow,
> > at ~64K rwsem waiter?
> 
> Its an extreme case I agree.
> 
> The patch is okay?

Yes, the patch is OK.
Acked-by: Kenneth Chen <kenneth.w.chen@intel.com>

- Ken