From 345af7bf3304410634c21ada4664fda83d4d9a16 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 9 Aug 2010 17:21:15 -0700 Subject: rwsem: fully separate code paths to wake writers vs readers This is in preparation for later changes in the series. In __rwsem_do_wake(), the first queued waiter is checked first in order to determine whether it's a writer or a reader. The code paths diverge at this point. The code that checks and increments the rwsem active count is duplicated on both sides - the point is that later changes in the series will be able to independently modify both sides. Signed-off-by: Michel Lespinasse Acked-by: David Howells Cc: Mike Waychison Cc: Suleiman Souhlal Cc: Ying Han Cc: Ingo Molnar Cc: Thomas Gleixner Cc: "H. Peter Anvin" Cc: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rwsem.c | 61 ++++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 34 insertions(+), 27 deletions(-) (limited to 'lib/rwsem.c') diff --git a/lib/rwsem.c b/lib/rwsem.c index ceba8e28807a..917fd946b495 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -41,7 +41,7 @@ struct rwsem_waiter { * - if we come here from up_xxxx(), then: * - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed) * - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so) - * - there must be someone on the queue + * - there must be someone on the queue * - the spinlock must be held by the caller * - woken process blocks are discarded from the list after having task zeroed * - writers are only woken if downgrading is false @@ -54,26 +54,23 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) struct list_head *next; signed long oldcount, woken, loop; + waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list); + if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE)) + goto readers_only; + if (downgrading) - goto dont_wake_writers; + goto out; - /* if we came through an up_xxxx() call, we only only wake someone up - * if we can transition the active part of the count from 0 -> 1 + /* There's a writer at the front of the queue - try to grant it the + * write lock. However, we only wake this writer if we can transition + * the active part of the count from 0 -> 1 */ - try_again: + try_again_write: oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem) - RWSEM_ACTIVE_BIAS; if (oldcount & RWSEM_ACTIVE_MASK) - goto undo; - - waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list); - - /* try to grant a single write lock if there's a writer at the front - * of the queue - note we leave the 'active part' of the count - * incremented by 1 and the waiting part incremented by 0x00010000 - */ - if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE)) - goto readers_only; + /* Someone grabbed the sem already */ + goto undo_write; /* We must be careful not to touch 'waiter' after we set ->task = NULL. * It is an allocated on the waiter's stack and may become invalid at @@ -87,18 +84,24 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) put_task_struct(tsk); goto out; - /* don't want to wake any writers */ - dont_wake_writers: - waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list); - if (waiter->flags & RWSEM_WAITING_FOR_WRITE) - goto out; + readers_only: + if (downgrading) + goto wake_readers; + + /* if we came through an up_xxxx() call, we only only wake someone up + * if we can transition the active part of the count from 0 -> 1 */ + try_again_read: + oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem) + - RWSEM_ACTIVE_BIAS; + if (oldcount & RWSEM_ACTIVE_MASK) + /* Someone grabbed the sem already */ + goto undo_read; - /* grant an infinite number of read locks to the readers at the front - * of the queue - * - note we increment the 'active part' of the count by the number of - * readers before waking any processes up + wake_readers: + /* Grant an infinite number of read locks to the readers at the front + * of the queue. Note we increment the 'active part' of the count by + * the number of readers before waking any processes up. */ - readers_only: woken = 0; do { woken++; @@ -138,10 +141,14 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) /* undo the change to the active count, but check for a transition * 1->0 */ - undo: + undo_write: + if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK) + goto out; + goto try_again_write; + undo_read: if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK) goto out; - goto try_again; + goto try_again_read; } /* -- cgit v1.2.2 From 70bdc6e0644f3535e93bac5c364ca199397e507e Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 9 Aug 2010 17:21:17 -0700 Subject: rwsem: lighter active count checks when waking up readers In __rwsem_do_wake(), we can skip the active count check unless we come there from up_xxxx(). Also when checking the active count, it is not actually necessary to increment it; this allows us to get rid of the read side undo code and simplify the calculation of the final rwsem count adjustment once we've counted the reader threads to wake. The basic observation is the following. When there are waiter threads on a rwsem and the spinlock is held, other threads can only increment the active count by trying to grab the rwsem in down_xxxx(). However down_xxxx() will notice there are waiter threads and take the down_failed path, blocking to acquire the spinlock on the way there. Therefore, a thread observing an active count of zero with waiters queued and the spinlock held, is protected against other threads acquiring the rwsem until it wakes the last waiter or releases the spinlock. Signed-off-by: Michel Lespinasse Acked-by: David Howells Cc: Mike Waychison Cc: Suleiman Souhlal Cc: Ying Han Cc: Ingo Molnar Cc: Thomas Gleixner Cc: "H. Peter Anvin" Cc: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rwsem.c | 57 ++++++++++++++++++++++++++++++++------------------------- 1 file changed, 32 insertions(+), 25 deletions(-) (limited to 'lib/rwsem.c') diff --git a/lib/rwsem.c b/lib/rwsem.c index 917fd946b495..94f2d7a9dc4f 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -36,6 +36,14 @@ struct rwsem_waiter { #define RWSEM_WAITING_FOR_WRITE 0x00000002 }; +/* Wake types for __rwsem_do_wake(). Note that RWSEM_WAKE_NO_ACTIVE and + * RWSEM_WAKE_READ_OWNED imply that the spinlock must have been kept held + * since the rwsem value was observed. + */ +#define RWSEM_WAKE_ANY 0 /* Wake whatever's at head of wait list */ +#define RWSEM_WAKE_NO_ACTIVE 1 /* rwsem was observed with no active thread */ +#define RWSEM_WAKE_READ_OWNED 2 /* rwsem was observed to be read owned */ + /* * handle the lock release when processes blocked on it that can now run * - if we come here from up_xxxx(), then: @@ -46,8 +54,8 @@ struct rwsem_waiter { * - woken process blocks are discarded from the list after having task zeroed * - writers are only woken if downgrading is false */ -static inline struct rw_semaphore * -__rwsem_do_wake(struct rw_semaphore *sem, int downgrading) +static struct rw_semaphore * +__rwsem_do_wake(struct rw_semaphore *sem, int wake_type) { struct rwsem_waiter *waiter; struct task_struct *tsk; @@ -58,7 +66,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE)) goto readers_only; - if (downgrading) + if (wake_type == RWSEM_WAKE_READ_OWNED) goto out; /* There's a writer at the front of the queue - try to grant it the @@ -85,19 +93,25 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) goto out; readers_only: - if (downgrading) - goto wake_readers; - - /* if we came through an up_xxxx() call, we only only wake someone up - * if we can transition the active part of the count from 0 -> 1 */ - try_again_read: - oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem) - - RWSEM_ACTIVE_BIAS; - if (oldcount & RWSEM_ACTIVE_MASK) + /* If we come here from up_xxxx(), another thread might have reached + * rwsem_down_failed_common() before we acquired the spinlock and + * woken up a waiter, making it now active. We prefer to check for + * this first in order to not spend too much time with the spinlock + * held if we're not going to be able to wake up readers in the end. + * + * Note that we do not need to update the rwsem count: any writer + * trying to acquire rwsem will run rwsem_down_write_failed() due + * to the waiting threads and block trying to acquire the spinlock. + * + * We use a dummy atomic update in order to acquire the cache line + * exclusively since we expect to succeed and run the final rwsem + * count adjustment pretty soon. + */ + if (wake_type == RWSEM_WAKE_ANY && + (rwsem_atomic_update(0, sem) & RWSEM_ACTIVE_MASK)) /* Someone grabbed the sem already */ - goto undo_read; + goto out; - wake_readers: /* Grant an infinite number of read locks to the readers at the front * of the queue. Note we increment the 'active part' of the count by * the number of readers before waking any processes up. @@ -116,9 +130,6 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) loop = woken; woken *= RWSEM_ACTIVE_BIAS - RWSEM_WAITING_BIAS; - if (!downgrading) - /* we'd already done one increment earlier */ - woken -= RWSEM_ACTIVE_BIAS; rwsem_atomic_add(woken, sem); @@ -145,10 +156,6 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK) goto out; goto try_again_write; - undo_read: - if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK) - goto out; - goto try_again_read; } /* @@ -170,12 +177,12 @@ rwsem_down_failed_common(struct rw_semaphore *sem, list_add_tail(&waiter->list, &sem->wait_list); - /* we're now waiting on the lock, but no longer actively read-locking */ + /* we're now waiting on the lock, but no longer actively locking */ count = rwsem_atomic_update(adjustment, sem); /* if there are no active locks, wake the front queued process(es) up */ if (!(count & RWSEM_ACTIVE_MASK)) - sem = __rwsem_do_wake(sem, 0); + sem = __rwsem_do_wake(sem, RWSEM_WAKE_NO_ACTIVE); spin_unlock_irq(&sem->wait_lock); @@ -232,7 +239,7 @@ asmregparm struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) /* do nothing if list empty */ if (!list_empty(&sem->wait_list)) - sem = __rwsem_do_wake(sem, 0); + sem = __rwsem_do_wake(sem, RWSEM_WAKE_ANY); spin_unlock_irqrestore(&sem->wait_lock, flags); @@ -252,7 +259,7 @@ asmregparm struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem) /* do nothing if list empty */ if (!list_empty(&sem->wait_list)) - sem = __rwsem_do_wake(sem, 1); + sem = __rwsem_do_wake(sem, RWSEM_WAKE_READ_OWNED); spin_unlock_irqrestore(&sem->wait_lock, flags); -- cgit v1.2.2 From fd41b33435ada87323cc86b50959fbffe35192c8 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 9 Aug 2010 17:21:18 -0700 Subject: rwsem: let RWSEM_WAITING_BIAS represent any number of waiting threads Previously each waiting thread added a bias of RWSEM_WAITING_BIAS. With this change, the bias is added only once to indicate that the wait list is non-empty. This has a few nice properties which will be used in following changes: - when the spinlock is held and the waiter list is known to be non-empty, count < RWSEM_WAITING_BIAS <=> there is an active writer on that sem - count == RWSEM_WAITING_BIAS <=> there are waiting threads and no active readers/writers on that sem Signed-off-by: Michel Lespinasse Acked-by: David Howells Cc: Mike Waychison Cc: Suleiman Souhlal Cc: Ying Han Cc: Ingo Molnar Cc: Thomas Gleixner Cc: "H. Peter Anvin" Cc: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rwsem.c | 28 +++++++++++++++++----------- 1 file changed, 17 insertions(+), 11 deletions(-) (limited to 'lib/rwsem.c') diff --git a/lib/rwsem.c b/lib/rwsem.c index 94f2d7a9dc4f..a3e68bf5932e 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -60,7 +60,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) struct rwsem_waiter *waiter; struct task_struct *tsk; struct list_head *next; - signed long oldcount, woken, loop; + signed long oldcount, woken, loop, adjustment; waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list); if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE)) @@ -73,9 +73,12 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) * write lock. However, we only wake this writer if we can transition * the active part of the count from 0 -> 1 */ + adjustment = RWSEM_ACTIVE_WRITE_BIAS; + if (waiter->list.next == &sem->wait_list) + adjustment -= RWSEM_WAITING_BIAS; + try_again_write: - oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem) - - RWSEM_ACTIVE_BIAS; + oldcount = rwsem_atomic_update(adjustment, sem) - adjustment; if (oldcount & RWSEM_ACTIVE_MASK) /* Someone grabbed the sem already */ goto undo_write; @@ -128,13 +131,15 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) } while (waiter->flags & RWSEM_WAITING_FOR_READ); - loop = woken; - woken *= RWSEM_ACTIVE_BIAS - RWSEM_WAITING_BIAS; + adjustment = woken * RWSEM_ACTIVE_READ_BIAS; + if (waiter->flags & RWSEM_WAITING_FOR_READ) + /* hit end of list above */ + adjustment -= RWSEM_WAITING_BIAS; - rwsem_atomic_add(woken, sem); + rwsem_atomic_add(adjustment, sem); next = sem->wait_list.next; - for (; loop > 0; loop--) { + for (loop = woken; loop > 0; loop--) { waiter = list_entry(next, struct rwsem_waiter, list); next = waiter->list.next; tsk = waiter->task; @@ -153,7 +158,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) /* undo the change to the active count, but check for a transition * 1->0 */ undo_write: - if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK) + if (rwsem_atomic_update(-adjustment, sem) & RWSEM_ACTIVE_MASK) goto out; goto try_again_write; } @@ -175,6 +180,8 @@ rwsem_down_failed_common(struct rw_semaphore *sem, waiter->task = tsk; get_task_struct(tsk); + if (list_empty(&sem->wait_list)) + adjustment += RWSEM_WAITING_BIAS; list_add_tail(&waiter->list, &sem->wait_list); /* we're now waiting on the lock, but no longer actively locking */ @@ -208,8 +215,7 @@ rwsem_down_read_failed(struct rw_semaphore *sem) struct rwsem_waiter waiter; waiter.flags = RWSEM_WAITING_FOR_READ; - rwsem_down_failed_common(sem, &waiter, - RWSEM_WAITING_BIAS - RWSEM_ACTIVE_BIAS); + rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_READ_BIAS); return sem; } @@ -222,7 +228,7 @@ rwsem_down_write_failed(struct rw_semaphore *sem) struct rwsem_waiter waiter; waiter.flags = RWSEM_WAITING_FOR_WRITE; - rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_BIAS); + rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_WRITE_BIAS); return sem; } -- cgit v1.2.2 From 424acaaeb3a3932d64a9b4bd59df6cf72c22d8f3 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 9 Aug 2010 17:21:19 -0700 Subject: rwsem: wake queued readers when writer blocks on active read lock This change addresses the following situation: - Thread A acquires the rwsem for read - Thread B tries to acquire the rwsem for write, notices there is already an active owner for the rwsem. - Thread C tries to acquire the rwsem for read, notices that thread B already tried to acquire it. - Thread C grabs the spinlock and queues itself on the wait queue. - Thread B grabs the spinlock and queues itself behind C. At this point A is the only remaining active owner on the rwsem. In this situation thread B could notice that it was the last active writer on the rwsem, and decide to wake C to let it proceed in parallel with A since they both only want the rwsem for read. Signed-off-by: Michel Lespinasse Acked-by: David Howells Cc: Mike Waychison Cc: Suleiman Souhlal Cc: Ying Han Cc: Ingo Molnar Cc: Thomas Gleixner Cc: "H. Peter Anvin" Cc: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rwsem.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) (limited to 'lib/rwsem.c') diff --git a/lib/rwsem.c b/lib/rwsem.c index a3e68bf5932e..318d435dcebb 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -67,6 +67,9 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) goto readers_only; if (wake_type == RWSEM_WAKE_READ_OWNED) + /* Another active reader was observed, so wakeup is not + * likely to succeed. Save the atomic op. + */ goto out; /* There's a writer at the front of the queue - try to grant it the @@ -111,8 +114,8 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) * count adjustment pretty soon. */ if (wake_type == RWSEM_WAKE_ANY && - (rwsem_atomic_update(0, sem) & RWSEM_ACTIVE_MASK)) - /* Someone grabbed the sem already */ + rwsem_atomic_update(0, sem) < RWSEM_WAITING_BIAS) + /* Someone grabbed the sem for write already */ goto out; /* Grant an infinite number of read locks to the readers at the front @@ -187,9 +190,17 @@ rwsem_down_failed_common(struct rw_semaphore *sem, /* we're now waiting on the lock, but no longer actively locking */ count = rwsem_atomic_update(adjustment, sem); - /* if there are no active locks, wake the front queued process(es) up */ - if (!(count & RWSEM_ACTIVE_MASK)) + /* If there are no active locks, wake the front queued process(es) up. + * + * Alternatively, if we're called from a failed down_write(), there + * were already threads queued before us and there are no active + * writers, the lock must be read owned; so we try to wake any read + * locks that were queued ahead of us. */ + if (count == RWSEM_WAITING_BIAS) sem = __rwsem_do_wake(sem, RWSEM_WAKE_NO_ACTIVE); + else if (count > RWSEM_WAITING_BIAS && + adjustment == -RWSEM_ACTIVE_WRITE_BIAS) + sem = __rwsem_do_wake(sem, RWSEM_WAKE_READ_OWNED); spin_unlock_irq(&sem->wait_lock); -- cgit v1.2.2 From a8618a0e8a06f75c6efec2a5477861d704d48b28 Mon Sep 17 00:00:00 2001 From: Michel Lespinasse Date: Mon, 9 Aug 2010 17:21:20 -0700 Subject: rwsem: smaller wrappers around rwsem_down_failed_common More code can be pushed from rwsem_down_read_failed and rwsem_down_write_failed into rwsem_down_failed_common. Following change adding down_read_critical infrastructure support also enjoys having flags available in a register rather than having to fish it out in the struct rwsem_waiter... Signed-off-by: Michel Lespinasse Acked-by: David Howells Cc: Mike Waychison Cc: Suleiman Souhlal Cc: Ying Han Cc: Ingo Molnar Cc: Thomas Gleixner Cc: "H. Peter Anvin" Cc: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rwsem.c | 25 ++++++++++--------------- 1 file changed, 10 insertions(+), 15 deletions(-) (limited to 'lib/rwsem.c') diff --git a/lib/rwsem.c b/lib/rwsem.c index 318d435dcebb..f236d7cd5cf3 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -171,8 +171,9 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wake_type) */ static struct rw_semaphore __sched * rwsem_down_failed_common(struct rw_semaphore *sem, - struct rwsem_waiter *waiter, signed long adjustment) + unsigned int flags, signed long adjustment) { + struct rwsem_waiter waiter; struct task_struct *tsk = current; signed long count; @@ -180,12 +181,13 @@ rwsem_down_failed_common(struct rw_semaphore *sem, /* set up my own style of waitqueue */ spin_lock_irq(&sem->wait_lock); - waiter->task = tsk; + waiter.task = tsk; + waiter.flags = flags; get_task_struct(tsk); if (list_empty(&sem->wait_list)) adjustment += RWSEM_WAITING_BIAS; - list_add_tail(&waiter->list, &sem->wait_list); + list_add_tail(&waiter.list, &sem->wait_list); /* we're now waiting on the lock, but no longer actively locking */ count = rwsem_atomic_update(adjustment, sem); @@ -206,7 +208,7 @@ rwsem_down_failed_common(struct rw_semaphore *sem, /* wait to be given the lock */ for (;;) { - if (!waiter->task) + if (!waiter.task) break; schedule(); set_task_state(tsk, TASK_UNINTERRUPTIBLE); @@ -223,11 +225,8 @@ rwsem_down_failed_common(struct rw_semaphore *sem, asmregparm struct rw_semaphore __sched * rwsem_down_read_failed(struct rw_semaphore *sem) { - struct rwsem_waiter waiter; - - waiter.flags = RWSEM_WAITING_FOR_READ; - rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_READ_BIAS); - return sem; + return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_READ, + -RWSEM_ACTIVE_READ_BIAS); } /* @@ -236,12 +235,8 @@ rwsem_down_read_failed(struct rw_semaphore *sem) asmregparm struct rw_semaphore __sched * rwsem_down_write_failed(struct rw_semaphore *sem) { - struct rwsem_waiter waiter; - - waiter.flags = RWSEM_WAITING_FOR_WRITE; - rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_WRITE_BIAS); - - return sem; + return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_WRITE, + -RWSEM_ACTIVE_WRITE_BIAS); } /* -- cgit v1.2.2