Skip to contentSkip to conversation

rwsem changes + down_read_unfair() proposal

PATCH In review Michel Lespinasse 3 participants 33 messages May 12, 2010 – May 13, 2010

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

cover rwsem changes + down_read_unfair() proposal

Hi,

I would like to sollicit comments regarding the following changes against 2.6.34-rc7. The motivation for this change was some cluster monitoring software we use at google; which reads /proc/<pid>/maps files for all running processes. When the machines are under load, the mmap_sem is often acquire for reads for long periods of time since do_page_fault() holds it while doing disk accesses; and fair queueing behavior often ends up in the monitoring software making little progress. By introducing unfair behavior in a few selected places, are are able to let the monitoring software make progress without impacting performance for the rest of the system.

In general, I've made sure to implement this proposal without touching the rwsem fast paths. Also, the first 8 patches of this series should be of general applicability even if not taking the down_read_unfair() changes, addressing minor issues such as situations where reader threads can get blocked at the head of the waiting list even though the rwsem is currently owned for reads.

Michel Lespinasse (12):
rwsem: test for no active locks in __rwsem_do_wake undo code
rwsem: use single atomic update for sem count when waking up readers
rwsem: let RWSEM_WAITING_BIAS represent any number of waiting threads
rwsem: consistently use adjustment variable
x86 rwsem: take advantage of new RWSEM_WAITING_BIAS semantics
rwsem: wake queued readers when other readers are active
rwsem: wake queued readers when writer blocks on active read lock
rwsem: smaller wrappers around rwsem_down_failed_common generic rwsem: implement down_read_unfair
rwsem: down_read_unfair infrastructure support
x86 rwsem: down_read_unfair implementation
Use down_read_unfair() for /sys/<pid>/exe and /sys/<pid>/maps files

 arch/x86/include/asm/rwsem.h   |   66 ++++++++++++++-----
 arch/x86/lib/rwsem_64.S        |   14 +++-
 arch/x86/lib/semaphore_32.S    |   21 +++++-
 fs/proc/base.c                 |    2 +-
 fs/proc/task_mmu.c             |    2 +-
 fs/proc/task_nommu.c           |    2 +-
 include/linux/rwsem-spinlock.h |   10 +++-
 include/linux/rwsem.h          |   10 +++
 kernel/rwsem.c                 |   17 +++++
 lib/rwsem-spinlock.c           |   10 ++-
 lib/rwsem.c                    |  145 ++++++++++++++++++++++++---------------
 11 files changed, 213 insertions(+), 86 deletions(-)

Also following here is the down_read_unfair.c test mentionned in last patch of the series:

#include <errno.h>
#include <fcntl.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

struct thread_data {
	unsigned long count_A, count_B, count_C;
	int done;
	int pid;
	char *mapped;
	unsigned long mapped_size;
	int dummy;
	int barrier_count;
	pthread_mutex_t barrier_mutex;
	pthread_cond_t barrier_cond;
};

static void barrier(struct thread_data *data)

{
	pthread_mutex_lock(&data->barrier_mutex);
	if (--(data->barrier_count) == 0)
		pthread_cond_broadcast(&data->barrier_cond);
	while (data->barrier_count)
		pthread_cond_wait(&data->barrier_cond, &data->barrier_mutex);
	pthread_mutex_unlock(&data->barrier_mutex);
}

static void *func_A(void *tmp)

{
	int dummy = 0;
	struct thread_data *data = tmp;

	srand48(time(NULL));
        barrier(data);

	while (!data->done) {
		unsigned long pos = (lrand48() << 31) | lrand48();
		dummy += data->mapped[pos % data->mapped_size];
		data->count_A++;
        }

	data->dummy = dummy;
	return NULL;
}

static void *func_B(void *tmp)

{
	char *dummy;
	struct thread_data *data = tmp;

        barrier(data);

	while (!data->done) {
		dummy = mmap(NULL, 1, PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS,
			     -1, 0);
		if (dummy == MAP_FAILED || munmap(dummy, 1)) break;
		data->count_B++;
	}

	return NULL;
}

static void *func_C(void *tmp)

{
	char procfile[64];
	struct thread_data *data = tmp;
	int fd, size;
	char buf[4096];

	size = sprintf(procfile, "/proc/%d/maps", data->pid);
        barrier(data);
	if (size < 0) return NULL;

	while (!data->done) {
		fd = open(procfile, O_RDONLY);
		if (fd < 0) break;
		do {
			size = read(fd, buf, sizeof buf);
		} while (size == sizeof buf);
		if (close(fd) || size < 0) break;
		data->count_C++;
	}

	return NULL;
}

int main(int argc, char **argv)

{
	int fd;
	struct stat sb;
        char *mapped;
	struct thread_data data;
	pthread_t thread_A, thread_B, thread_C;

	if (argc != 2) {
		fprintf(stderr, "Usage: %s <filename>\n", argv[0]);
		exit(1);
	}

	fd = open(argv[1], O_RDONLY);
	if (fd < 0) {
		fprintf(stderr, "open %s: %s\n", argv[1], strerror(errno));
		exit(1);
	}
	if (fstat(fd, &sb) < 0) {
		fprintf(stderr, "fstat: %s\n", strerror(errno));
		exit(1);
	}
        mapped = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
        if (mapped == MAP_FAILED) {
		fprintf(stderr, "mmap: %s\n", strerror(errno));
		exit(1);
        }
	if (close(fd)) {
		fprintf(stderr, "close: %s\n", strerror(errno));
		exit(1);
	}

	data.count_A = data.count_B = data.count_C = 0;
	data.done = 0;
	data.pid = getpid();
	data.mapped = mapped;
	data.mapped_size = sb.st_size;
	data.dummy = 0;
	data.barrier_count = 4;
        if (pthread_mutex_init(&data.barrier_mutex, NULL) ||
            pthread_cond_init(&data.barrier_cond, NULL)) {
		fprintf(stderr, "pthread_*_init: %s\n", strerror(errno));
		exit(1);
        }

	if (pthread_create(&thread_A, NULL, func_A, &data) ||
	    pthread_create(&thread_B, NULL, func_B, &data) ||
	    pthread_create(&thread_C, NULL, func_C, &data)) {
		fprintf(stderr, "pthread_create: %s\n", strerror(errno));
                exit(1);
	}
        barrier(&data);
	sleep(10);
	data.done = 1;
	if (pthread_join(thread_A, NULL) ||
	    pthread_join(thread_B, NULL) ||
	    pthread_join(thread_C, NULL)) {
		fprintf(stderr, "pthread_join: %s\n", strerror(errno));
	}
	printf ("Counts: %lu A, %lu B, %lu C\n",
		data.count_A, data.count_B, data.count_C);
	return 0;
}
#1 lore raw

PATCH 1/12 rwsem: test for no active locks in __rwsem_do_wake undo code

If there are no active threasd using a semaphore, it is always correct to unqueue blocked threads. This seems to be what was intended in the undo code.

What was done instead, was to look for a sem count of zero - this is an impossible situation, given that at least one thread is known to be queued on the semaphore. The code might be correct as written, but it's hard to reason about and it's not what was intended (otherwise the goto out would have been unconditional).

Go for checking the active count - the alternative is not worth the headache.

---
 lib/rwsem.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
lib/rwsem.c +1 -1
index 3e3365e..8d6a13e 100644
@@ -138,7 +138,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 
 	/* undo the change to count, but check for a transition 1->0 */
  undo:
-	if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) != 0)
+	if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK)
 		goto out;
 	goto try_again;
 }
Signature · 1 line
1.7.0.1
#2 lore raw

Re: [PATCH 01/12] rwsem: test for no active locks in __rwsem_do_wake undo code

Quoted 10 lines · Michel Lespinasse

If there are no active threasd using a semaphore, it is always correct to unqueue blocked threads. This seems to be what was intended in the undo code.

What was done instead, was to look for a sem count of zero - this is an impossible situation, given that at least one thread is known to be queued on the semaphore. The code might be correct as written, but it's hard to reason about and it's not what was intended (otherwise the goto out would have been unconditional).

Go for checking the active count - the alternative is not worth the headache.

I think this is a definite bug fix, so I've sent it upstream in advance.

David

#3 lore raw

PATCH 2/12 rwsem: use single atomic update for sem count when waking up readers.

In reply to Michel Lespinasse

When waking up queued readers, __rwsem_do_wake was using a pair of atomic operations (one before looking at the first queued thread and one after having looped through all readers). Restructure code to use a single atomic operation instead.

---
 lib/rwsem.c |   52 ++++++++++++++++++++++++++--------------------------
 1 files changed, 26 insertions(+), 26 deletions(-)
lib/rwsem.c +26 -26
index 8d6a13e..caee9b7 100644
@@ -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,26 @@ __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;
+		/* Caller's lock is still active, so we can't possibly
+		 * succeed waking writers.
+		 */
+		goto out;
 
-	/* if we came through an up_xxxx() call, we only only wake someone up
+	/* There's a writer at the front of the queue - try to grant it the
+	 * write lock. However, we only only wake someone up
 	 * if we can transition the active part of the count from 0 -> 1
 	 */
- try_again:
+ retry_writer:
 	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_writer;
 
 	/* 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,12 +87,6 @@ __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;
-
 	/* 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
@@ -113,11 +107,12 @@ __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);
+ retry_readers:
+	oldcount = rwsem_atomic_update(woken, sem) - woken;
+	if (!downgrading && (oldcount & RWSEM_ACTIVE_MASK))
+		/* Someone grabbed the sem already */
+		goto undo_readers;
 
 	next = sem->wait_list.next;
 	for (; loop > 0; loop--) {
@@ -137,10 +132,15 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	return sem;
 
 	/* undo the change to count, but check for a transition 1->0 */
- undo:
+ undo_writer:
 	if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK)
 		goto out;
-	goto try_again;
+	goto retry_writer;
+
+ undo_readers:
+	if (rwsem_atomic_update(-woken, sem) & RWSEM_ACTIVE_MASK)
+		goto out;
+	goto retry_readers;
 }
 
 /*
Signature · 1 line
1.7.0.1
#4 lore raw

Re: [PATCH 02/12] rwsem: use single atomic update for sem count when waking up readers.

Quoted 2 lines · Michel Lespinasse

- * - there must be someone on the queue
+ * - there must be someone on the queue

Why did you change this comment? This is still a guarantee up_xxxx() must make about the state of the rwsem.

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) · line 65

Quoted 10 lines
lib/rwsem.c +8 -1
+	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;
+		/* Caller's lock is still active, so we can't possibly
+		 * succeed waking writers.
+		 */
+		goto out;

It's a nice idea to do it this way round - it puts the wake-up-reader path first and puts the downgrader on the slower path.

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) · line 70

Quoted 5 lines
lib/rwsem.c +2 -1
-	/* if we came through an up_xxxx() call, we only only wake someone up
+	/* There's a writer at the front of the queue - try to grant it the
+	 * write lock. However, we only only wake someone up
 	 * if we can transition the active part of the count from 0 -> 1
 	 */

Two spaces after a full stop, please, and can you please adjust the comment so that it fills out to 80 chars. E.g:

	/* There's a writer at the front of the queue - try to grant it the
	 * write lock.  However, we only only wake someone up if we can
	 * transition the active part of the count from 0 -> 1
	 */

instead of:

	/* There's a writer at the front of the queue - try to grant it the
	 * write lock. However, we only only wake someone up
	 * if we can transition the active part of the count from 0 -> 1
	 */

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) · line 113

Quoted 3 lines

+ retry_readers:

lib/rwsem.c +2 -0
+	oldcount = rwsem_atomic_update(woken, sem) - woken;
+	if (!downgrading && (oldcount & RWSEM_ACTIVE_MASK))

The problem with doing this here is that you may just have wasted all the work you did working out what woken is going to be. That may have been quite slow as the CPU may have had to get hold of a bunch of cachelines that weren't in its cache. Furthermore, you are doing this under a spinlock, so you may have lost your right to wake anyone up, and you'll be blocking the CPU that will be allowed to perform the wakeup.

Incrementing the count first nets you a guarantee that you have the right to wake things up.

You may point out that if there's no contention, then what your revised code does doesn't slow anything down. That's true, but on modern CPU's, neither does the old code as the exclusively held cache line will lurk in the CPU's cache until there's contention on it.

David

#5 lore raw

Re: [PATCH 02/12] rwsem: use single atomic update for sem count when waking up readers.

Quoted 7 lines · David Howells
Quoted 2 lines · Michel Lespinasse

- *   - there must be someone on the queue
+ * - there must be someone on the queue

Why did you change this comment?  This is still a guarantee up_xxxx() must make about the state of the rwsem.

What I meant is that we do rely on there being someone on the queue even if not coming from up_xxxx().

Quoted 11 lines
Quoted 3 lines

+ retry_readers:
+     oldcount = rwsem_atomic_update(woken, sem) - woken;
+     if (!downgrading && (oldcount & RWSEM_ACTIVE_MASK))

The problem with doing this here is that you may just have wasted all the work you did working out what woken is going to be.  That may have been quite slow as the CPU may have had to get hold of a bunch of cachelines that weren't in its cache.  Furthermore, you are doing this under a spinlock, so you may have lost your right to wake anyone up, and you'll be blocking the CPU that will be allowed to perform the wakeup.

Quoted 7 lines

Incrementing the count first nets you a guarantee that you have the right to wake things up.

You may point out that if there's no contention, then what your revised code does doesn't slow anything down.  That's true, but on modern CPU's, neither does the old code as the exclusively held cache line will lurk in the CPU's cache until there's contention on it.

My reasoning was more that in all cases except downgrade_write() (which gets an exemption anyway because we know nobody can grab the write lock from it) we've already checked the active count and found it to be zero, so there is not much point checking again at the start of __rwsem_do_wake(). However you are correct that incrementing the active count at that point could be important, just to guarantee that nobody can grab a write lock while we count how many readers we want to wake.

I'll make sure to address this.

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#6 lore raw

Re: [PATCH 02/12] rwsem: use single atomic update for sem count when waking up readers.

In reply to Michel Lespinasse

lib/rwsem.c __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) · line 68

Quoted 1 line · Michel Lespinasse
lib/rwsem.c +1 -0
+	 * write lock. However, we only only wake someone up

Can you get rid of the excess 'only' whilst you're at it?

David

#7 lore raw

PATCH 3/12 rwsem: let RWSEM_WAITING_BIAS represent any number of waiting threads

In reply to Michel Lespinasse

Previously each waiting thread added a bias of RWSEM_WAITING_BIAS. With this change, the bias is added only once when the wait list is non-empty.

This has a few nice properties which will be used in following changes:
- when the mutex 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

---
 lib/rwsem.c |   23 +++++++++++++++--------
 1 files changed, 15 insertions(+), 8 deletions(-)
lib/rwsem.c +15 -8
index caee9b7..0fb6e38 100644
@@ -52,7 +52,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	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))
@@ -68,9 +68,12 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	 * write lock. However, we only only wake someone up
 	 * 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;
+
  retry_writer:
-	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_writer;
@@ -106,7 +109,10 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	} while (waiter->flags & RWSEM_WAITING_FOR_READ);
 
 	loop = woken;
-	woken *= RWSEM_ACTIVE_BIAS - RWSEM_WAITING_BIAS;
+	woken *= RWSEM_ACTIVE_READ_BIAS;
+	if (waiter->flags & RWSEM_WAITING_FOR_READ)
+		/* hit end of list above */
+		woken -= RWSEM_WAITING_BIAS;
 
  retry_readers:
 	oldcount = rwsem_atomic_update(woken, sem) - woken;
@@ -133,7 +139,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 
 	/* undo the change to count, but check for a transition 1->0 */
  undo_writer:
-	if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK)
+	if (rwsem_atomic_update(-adjustment, sem) & RWSEM_ACTIVE_MASK)
 		goto out;
 	goto retry_writer;
 
@@ -160,6 +166,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 read-locking */
@@ -193,8 +201,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;
 }
 
@@ -207,7 +214,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;
 }
Signature · 1 line
1.7.0.1
#8 lore raw

PATCH 4/12 rwsem: consistently use adjustment variable

In reply to Michel Lespinasse

Cleanup: previous change introduced an adjustment variable used in waking writers; the code to wake readers can be made nicer by making use of that same variable.

Reducing variable count should hopefully help both humans and compilers looking at this function :)

---
 lib/rwsem.c |   15 +++++++--------
 1 files changed, 7 insertions(+), 8 deletions(-)
lib/rwsem.c +7 -8
index 0fb6e38..92c8f8e 100644
@@ -52,7 +52,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	struct rwsem_waiter *waiter;
 	struct task_struct *tsk;
 	struct list_head *next;
-	signed long oldcount, woken, loop, adjustment;
+	signed long oldcount, loop, adjustment;
 
 	waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
 	if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE))
@@ -96,9 +96,9 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	 *   readers before waking any processes up
 	 */
  readers_only:
-	woken = 0;
+	loop = 0;
 	do {
-		woken++;
+		loop++;
 
 		if (waiter->list.next == &sem->wait_list)
 			break;
@@ -108,14 +108,13 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 
 	} while (waiter->flags & RWSEM_WAITING_FOR_READ);
 
-	loop = woken;
-	woken *= RWSEM_ACTIVE_READ_BIAS;
+	adjustment = loop * RWSEM_ACTIVE_READ_BIAS;
 	if (waiter->flags & RWSEM_WAITING_FOR_READ)
 		/* hit end of list above */
-		woken -= RWSEM_WAITING_BIAS;
+		adjustment -= RWSEM_WAITING_BIAS;
 
  retry_readers:
-	oldcount = rwsem_atomic_update(woken, sem) - woken;
+	oldcount = rwsem_atomic_update(adjustment, sem) - adjustment;
 	if (!downgrading && (oldcount & RWSEM_ACTIVE_MASK))
 		/* Someone grabbed the sem already */
 		goto undo_readers;
@@ -144,7 +143,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	goto retry_writer;
 
  undo_readers:
-	if (rwsem_atomic_update(-woken, sem) & RWSEM_ACTIVE_MASK)
+	if (rwsem_atomic_update(-adjustment, sem) & RWSEM_ACTIVE_MASK)
 		goto out;
 	goto retry_readers;
 }
Signature · 1 line
1.7.0.1
#9 lore raw

Re: [PATCH 04/12] rwsem: consistently use adjustment variable

Quoted 6 lines · Michel Lespinasse

Cleanup: previous change introduced an adjustment variable used in waking writers; the code to wake readers can be made nicer by making use of that same variable.

Reducing variable count should hopefully help both humans and compilers looking at this function :)

Actually, no. The compiler doesn't care. With optimisation, the variable 'woken' would cease to exist after being copied to loop and added into adjustment. What it would probably do is just relabel 'woken' internally as 'loop'.

Quoted 1 line

From a human point of view, I would say keep woken, but use it to initialise

adjustment:

	adjustment = woken * RWSEM_ACTIVE_READ_BIAS;

and use it to initialise 'loop':

	for (loop = woken; loop > 0; loop--) {

or just ditch 'loop' and use 'woken' directly, since the number of processes to be woken goes down as the loop iterates.

Whatever, the compiler won't care, since loop and woken will just be names for the same value.

David

#10 lore raw

Re: [PATCH 04/12] rwsem: consistently use adjustment variable

Quoted 8 lines · David Howells

From a human point of view, I would say keep woken, but use it to initialise adjustment:

       adjustment = woken * RWSEM_ACTIVE_READ_BIAS;

and use it to initialise 'loop':

       for (loop = woken; loop > 0; loop--) {

Sounds good. I'll have it in next version.

(Arguably 'woken' might be confusing too given that we only wake the threads later on. But I don't care much either way).

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#11 lore raw

PATCH 5/12 x86 rwsem: take advantage of new RWSEM_WAITING_BIAS semantics

In reply to Michel Lespinasse

Now that an arbitrary number of waiting threads are represented by a single RWSEM_WAITING_BIAS, the up_read and up_write code paths can be slightly simplified by checking for waiting threads and no active threads all at once.

---
 arch/x86/include/asm/rwsem.h |   23 ++++++++++++++---------
 arch/x86/lib/rwsem_64.S      |    4 +---
 arch/x86/lib/semaphore_32.S  |    4 +---
 3 files changed, 16 insertions(+), 15 deletions(-)
arch/x86/include/asm/rwsem.h +14 -9
index 606ede1..a15b84d 100644
@@ -118,7 +118,7 @@ static inline void __down_read(struct rw_semaphore *sem)
 {
 	asm volatile("# beginning down_read\n\t"
 		     LOCK_PREFIX _ASM_INC "(%1)\n\t"
-		     /* adds 0x00000001, returns the old value */
+		     /* adds 0x00000001 */
 		     "  jns        1f\n"
 		     "  call call_rwsem_down_read_failed\n"
 		     "1:\n\t"
@@ -160,7 +160,7 @@ static inline void __down_write_nested(struct rw_semaphore *sem, int subclass)
 	tmp = RWSEM_ACTIVE_WRITE_BIAS;
 	asm volatile("# beginning down_write\n\t"
 		     LOCK_PREFIX "  xadd      %1,(%2)\n\t"
-		     /* subtract 0x0000ffff, returns the old value */
+		     /* adds 0xffff0001, returns the old value */
 		     "  test      %1,%1\n\t"
 		     /* was the count 0 before? */
 		     "  jz        1f\n"
@@ -199,12 +199,15 @@ static inline void __up_read(struct rw_semaphore *sem)
 	asm volatile("# beginning __up_read\n\t"
 		     LOCK_PREFIX "  xadd      %1,(%2)\n\t"
 		     /* subtracts 1, returns the old value */
-		     "  jns        1f\n\t"
+		     "  cmp        %4,%1\n\t"
+		     /* are there waiting threads and no active threads ? */
+		     "  jne        1f\n"
 		     "  call call_rwsem_wake\n"
 		     "1:\n"
 		     "# ending __up_read\n"
 		     : "+m" (sem->count), "=d" (tmp)
-		     : "a" (sem), "1" (tmp)
+		     : "a" (sem), "1" (tmp),
+		       "er" (RWSEM_WAITING_BIAS + RWSEM_ACTIVE_READ_BIAS)
 		     : "memory", "cc");
 }
 
@@ -213,17 +216,19 @@ static inline void __up_read(struct rw_semaphore *sem)
  */
 static inline void __up_write(struct rw_semaphore *sem)
 {
-	rwsem_count_t tmp;
+	rwsem_count_t tmp = -RWSEM_ACTIVE_WRITE_BIAS;
 	asm volatile("# beginning __up_write\n\t"
 		     LOCK_PREFIX "  xadd      %1,(%2)\n\t"
-		     /* tries to transition
-			0xffff0001 -> 0x00000000 */
-		     "  jz       1f\n"
+		     /* substracts 0xffff0001, returns the old value */
+		     "  cmp      %4,%1\n\t"
+		     /* are there waiting threads and no active threads ? */
+		     "  jne      1f\n"
 		     "  call call_rwsem_wake\n"
 		     "1:\n\t"
 		     "# ending __up_write\n"
 		     : "+m" (sem->count), "=d" (tmp)
-		     : "a" (sem), "1" (-RWSEM_ACTIVE_WRITE_BIAS)
+		     : "a" (sem), "1" (tmp),
+		       "er" (RWSEM_WAITING_BIAS + RWSEM_ACTIVE_WRITE_BIAS)
 		     : "memory", "cc");
 }
 
arch/x86/lib/rwsem_64.S +1 -3
index 41fcf00..770a387 100644
@@ -60,13 +60,11 @@ ENTRY(call_rwsem_down_write_failed)
 	ENDPROC(call_rwsem_down_write_failed)
 
 ENTRY(call_rwsem_wake)
-	decl %edx	/* do nothing if still outstanding active readers */
-	jnz 1f
 	save_common_regs
 	movq %rax,%rdi
 	call rwsem_wake
 	restore_common_regs
-1:	ret
+	ret
 	ENDPROC(call_rwsem_wake)
 
 /* Fix up special calling conventions */
arch/x86/lib/semaphore_32.S +1 -3
index 648fe47..63dbf75 100644
@@ -103,15 +103,13 @@ ENTRY(call_rwsem_down_write_failed)
 
 ENTRY(call_rwsem_wake)
 	CFI_STARTPROC
-	decw %dx    /* do nothing if still outstanding active readers */
-	jnz 1f
 	push %ecx
 	CFI_ADJUST_CFA_OFFSET 4
 	CFI_REL_OFFSET ecx,0
 	call rwsem_wake
 	pop %ecx
 	CFI_ADJUST_CFA_OFFSET -4
-1:	ret
+	ret
 	CFI_ENDPROC
 	ENDPROC(call_rwsem_wake)
 
Signature · 1 line
1.7.0.1
#12 lore raw

Re: [PATCH 05/12] x86 rwsem: take advantage of new RWSEM_WAITING_BIAS semantics

arch/x86/include/asm/rwsem.h static inline void __up_read(struct rw_semaphore *sem) · line 226

Quoted 12 lines · Michel Lespinasse

static inline void __up_write(struct rw_semaphore *sem) {
...

arch/x86/include/asm/rwsem.h +4 -3
 		     LOCK_PREFIX "  xadd      %1,(%2)\n\t"
-		     /* tries to transition
-			0xffff0001 -> 0x00000000 */
-		     "  jz       1f\n"
+		     /* substracts 0xffff0001, returns the old value */
+		     "  cmp      %4,%1\n\t"
+		     /* are there waiting threads and no active threads ? */
+		     "  jne      1f\n"
 		     "  call call_rwsem_wake\n"

It looks like you're betting on there being fast-path contention. If the common case is no fast-path contention, then you'd be better off putting the comparison out of line in the medium-path and retaining the JZ instruction.

The same goes for __up_read(): you could retain the JNS there and put the comparison out of line into the medium-path.

Doing this also saves you some code space.

David

#13 lore raw

PATCH 6/12 rwsem: wake queued readers when other readers are active

In reply to Michel Lespinasse

This change addresses the following situation:

- Thread A holds the rwsem for write
- Thread B tries to acquire the rwsem for read; blocks & gets queued
- Thread A releases the rwsem, notices active count goes back to 0
- Thread C acquires the rwsem for read
- Thread A acquires the spinlock & tries to wake thread B, but fails because active count is not zero anymore.

In this situation, it would be perfectly fine to let threads B and C work in parallel as they each only want a read acquire on the rwsem. We can recognize this situation and let A wake B as long as there are no active writers on the rwsem.

---
 lib/rwsem.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)
lib/rwsem.c +3 -3
index 92c8f8e..9d0899b 100644
@@ -115,8 +115,8 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 
  retry_readers:
 	oldcount = rwsem_atomic_update(adjustment, sem) - adjustment;
-	if (!downgrading && (oldcount & RWSEM_ACTIVE_MASK))
-		/* Someone grabbed the sem already */
+	if (!downgrading && (oldcount < RWSEM_WAITING_BIAS))
+		/* Someone grabbed the sem for write already */
 		goto undo_readers;
 
 	next = sem->wait_list.next;
@@ -143,7 +143,7 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	goto retry_writer;
 
  undo_readers:
-	if (rwsem_atomic_update(-adjustment, sem) & RWSEM_ACTIVE_MASK)
+	if (rwsem_atomic_update(-adjustment, sem) < RWSEM_WAITING_BIAS)
 		goto out;
 	goto retry_readers;
 }
Signature · 1 line
1.7.0.1
#14 lore raw

Re: [PATCH 06/12] rwsem: wake queued readers when other readers are active

Quoted 4 lines · Michel Lespinasse

In this situation, it would be perfectly fine to let threads B and C work in parallel as they each only want a read acquire on the rwsem. We can recognize this situation and let A wake B as long as there are no active writers on the rwsem.

There can't be any active writers on the rwsem. An active writer must have just been upped and is in the process of waking the first sleeper up.

David

#15 lore raw

Re: [PATCH 06/12] rwsem: wake queued readers when other readers are active

Quoted 9 lines · David Howells
Quoted 4 lines · Michel Lespinasse

In this situation, it would be perfectly fine to let threads B and C work in parallel as they each only want a read acquire on the rwsem. We can recognize this situation and let A wake B as long as there are no active writers on the rwsem.

There can't be any active writers on the rwsem.  An active writer must have just been upped and is in the process of waking the first sleeper up.

Yes. My point is that by the point thread A (the writer that just got upped) gets around to waking B (a blocked reader), another reader C might have gotten active already. We don't want the nonzero active count (due to C) to prevent B from getting woken.

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#16 lore raw

Re: [PATCH 06/12] rwsem: wake queued readers when other readers are active

Quoted 8 lines · Michel Lespinasse
Quoted 7 lines · David Howells
Quoted 4 lines · Michel Lespinasse

In this situation, it would be perfectly fine to let threads B and C work in parallel as they each only want a read acquire on the rwsem. We can recognize this situation and let A wake B as long as there are no active writers on the rwsem.

Quoted 7 lines
Quoted 2 lines

There can't be any active writers on the rwsem.  An active writer must have just been upped and is in the process of waking the first sleeper up.

Yes. My point is that by the point thread A (the writer that just got upped) gets around to waking B (a blocked reader), another reader C might have gotten active already. We don't want the nonzero active count (due to C) to prevent B from getting woken.

My bad - this is actually fine. C will notice there are still waiting threads, so it will run rwsem_down_read_failed and queue itself. At this point the active count will go back down to 0 and B and C will both get woken.

I'll merge this back into change 7 since change 7 does require this in order to work.

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#17 lore raw

PATCH 7/12 rwsem: wake queued readers when writer blocks on active read lock

In reply to Michel Lespinasse

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.

---
 lib/rwsem.c |   32 ++++++++++++++++++++++----------
 1 files changed, 22 insertions(+), 10 deletions(-)
lib/rwsem.c +22 -10
index 9d0899b..84bbc55 100644
@@ -36,6 +36,10 @@ struct rwsem_waiter {
 #define RWSEM_WAITING_FOR_WRITE	0x00000002
 };
 
+#define RWSEM_WAKE_ANY        0 /* Wake whatever's at head of wait list */
+#define RWSEM_WAKE_READERS    1 /* Sem is read owned by other thread */
+#define RWSEM_WAKE_READ_OWNED 2 /* Sem is read owned by caller thread */
+
 /*
  * handle the lock release when processes blocked on it that can now run
  * - if we come here from up_xxxx(), then:
@@ -46,8 +50,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,9 +62,9 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 	if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE))
 		goto readers_only;
 
-	if (downgrading)
-		/* Caller's lock is still active, so we can't possibly
-		 * succeed waking writers.
+	if (wake_type != RWSEM_WAKE_ANY)
+		/* Another active reader was observed, so wakeup is not
+		 * likely to succeed. Save the atomic op.
 		 */
 		goto out;
 
@@ -115,7 +119,8 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
 
  retry_readers:
 	oldcount = rwsem_atomic_update(adjustment, sem) - adjustment;
-	if (!downgrading && (oldcount < RWSEM_WAITING_BIAS))
+	if (wake_type != RWSEM_WAKE_READ_OWNED &&
+	    oldcount < RWSEM_WAITING_BIAS)
 		/* Someone grabbed the sem for write already */
 		goto undo_readers;
 
@@ -172,9 +177,16 @@ rwsem_down_failed_common(struct rw_semaphore *sem,
 	/* we're now waiting on the lock, but no longer actively read-locking */
 	count = rwsem_atomic_update(adjustment, sem);
 
-	/* if there are no active locks, wake the front queued process(es) up */
+	/* if there are no active locks, wake the front queued process(es) up.
+	 *
+	 * or if we're called from a failed down_write(), and there were
+	 * already threads queued before us, and there are no active writers,
+	 * the lock must be read owned; try to wake any read locks that were
+	 * queued ahead of us. */
 	if (!(count & RWSEM_ACTIVE_MASK))
-		sem = __rwsem_do_wake(sem, 0);
+		sem = __rwsem_do_wake(sem, RWSEM_WAKE_ANY);
+	else if (adjustment > 0 && count > RWSEM_WAITING_BIAS)
+		sem = __rwsem_do_wake(sem, RWSEM_WAKE_READERS);
 
 	spin_unlock_irq(&sem->wait_lock);
 
@@ -230,7 +242,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);
 
@@ -250,7 +262,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);
 
Signature · 1 line
1.7.0.1
#18 lore raw

Re: [PATCH 07/12] rwsem: wake queued readers when writer blocks on active read lock

lib/rwsem.c rwsem_down_failed_common(struct rw_semaphore *sem, · line 185

Quoted 6 lines · Michel Lespinasse
lib/rwsem.c +6 -0
+	/* if there are no active locks, wake the front queued process(es) up.
+	 *
+	 * or if we're called from a failed down_write(), and there were
+	 * already threads queued before us, and there are no active writers,
+	 * the lock must be read owned; try to wake any read locks that were
+	 * queued ahead of us. */

That looks weird. Can I suggest rewriting it thus:

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

David

#19 lore raw

PATCH 8/12 rwsem: smaller wrappers around rwsem_down_failed_common

In reply to Michel Lespinasse

More code can be pushed from rwsem_down_read_failed and rwsem_down_write_failed into rwsem_down_failed_common.

Following change also enjoys having flags available in a register rather than having to fish it out in the struct rwsem_waiter...

---
 lib/rwsem.c |   23 +++++++++--------------
 1 files changed, 9 insertions(+), 14 deletions(-)
lib/rwsem.c +9 -14
index 84bbc55..1702524 100644
@@ -158,8 +158,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;
 
@@ -167,7 +168,8 @@ 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))
@@ -192,7 +194,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);
@@ -209,11 +211,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);
 }
 
 /*
@@ -222,12 +221,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);
 }
 
 /*
Signature · 1 line
1.7.0.1
#20 lore raw

Re: [PATCH 08/12] rwsem: smaller wrappers around rwsem_down_failed_common

Have you tried compiling this patch?

lib/rwsem.c: In function 'rwsem_down_failed_common':
lib/rwsem.c:177: error: invalid type argument of '->' (have 'struct rwsem_waiter')

There's a list_add_tail() that refers to waiter->list

David

#21 lore raw

Re: [PATCH 08/12] rwsem: smaller wrappers around rwsem_down_failed_common

In reply to Michel Lespinasse
Quoted 2 lines · Michel Lespinasse

Following change also enjoys having flags available in a register rather than having to fish it out in the struct rwsem_waiter...

So what? It doesn't use flags in rwsem_down_failed_common().

David

#22 lore raw

Re: [PATCH 08/12] rwsem: smaller wrappers around rwsem_down_failed_common

Quoted 6 lines · David Howells
Quoted 2 lines · Michel Lespinasse

Following change also enjoys having flags available in a register rather than having to fish it out in the struct rwsem_waiter...

So what?  It doesn't use flags in rwsem_down_failed_common().

I meant patch 10 wants to use the flags in order to know whether to queue at the head or tail of the waiter list.

Apologies for the compile error, patches 8 and 10 used to be a single change and were split off relatively late. :/

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#23 lore raw

PATCH 9/12 generic rwsem: implement down_read_unfair

In reply to Michel Lespinasse

Add down_read_unfair() API.

This is similar to down_read() with the following changes:
- when the rwsem is read owned with queued writers, down_read_unfair() callers are allowed to acquire the rwsem for read without queueing;
- when the rwsem is write owned, down_read_unfair() callers get queued in front of threads trying to acquire the rwsem by other means.

---
 include/linux/rwsem-spinlock.h |   10 +++++++++-
 include/linux/rwsem.h          |   10 ++++++++++
 kernel/rwsem.c                 |   17 +++++++++++++++++
 lib/rwsem-spinlock.c           |   10 +++++++---
 4 files changed, 43 insertions(+), 4 deletions(-)
include/linux/rwsem-spinlock.h +9 -1
index bdfcc25..dc849d9 100644
@@ -60,7 +60,15 @@ do {								\
 	__init_rwsem((sem), #sem, &__key);			\
 } while (0)
 
-extern void __down_read(struct rw_semaphore *sem);
+#define __HAVE_DOWN_READ_UNFAIR
+
+static inline void __down_read(struct rw_semaphore *sem)
+	{ __down_read_internal(sem, 0); }
+
+static inline void __sched __down_read_unfair(struct rw_semaphore *sem)
+	{ __down_read_internal(sem, 1);	}
+
+extern void __down_read_internal(struct rw_semaphore *sem, int unfair);
 extern int __down_read_trylock(struct rw_semaphore *sem);
 extern void __down_write(struct rw_semaphore *sem);
 extern void __down_write_nested(struct rw_semaphore *sem, int subclass);
include/linux/rwsem.h +10 -0
index efd348f..365e47b 100644
@@ -28,6 +28,16 @@ struct rw_semaphore;
 extern void down_read(struct rw_semaphore *sem);
 
 /*
+ * lock for reading - skip waiting writers
+ */
+#ifdef __HAVE_DOWN_READ_UNFAIR
+extern void down_read_unfair(struct rw_semaphore *sem);
+#else
+static inline void down_read_unfair(struct rw_semaphore *sem)
+	{ down_read(sem); }
+#endif
+
+/*
  * trylock for reading -- returns 1 if successful, 0 if contention
  */
 extern int down_read_trylock(struct rw_semaphore *sem);
kernel/rwsem.c +17 -0
index cae050b..0cef726 100644
@@ -26,6 +26,23 @@ void __sched down_read(struct rw_semaphore *sem)
 
 EXPORT_SYMBOL(down_read);
 
+#ifdef __HAVE_DOWN_READ_UNFAIR
+
+/*
+ * lock for reading - skip waiting writers
+ */
+void __sched down_read_unfair(struct rw_semaphore *sem)
+{
+	might_sleep();
+	rwsem_acquire_read(&sem->dep_map, 0, 0, _RET_IP_);
+
+	LOCK_CONTENDED(sem, __down_read_trylock, __down_read_unfair);
+}
+
+EXPORT_SYMBOL(down_read_unfair);
+
+#endif
+
 /*
  * trylock for reading -- returns 1 if successful, 0 if contention
  */
lib/rwsem-spinlock.c +7 -3
index ffc9fc7..b2fd5fb 100644
@@ -139,7 +139,7 @@ __rwsem_wake_one_writer(struct rw_semaphore *sem)
 /*
  * get a read lock on the semaphore
  */
-void __sched __down_read(struct rw_semaphore *sem)
+void __sched __down_read_internal(struct rw_semaphore *sem, int unfair)
 {
 	struct rwsem_waiter waiter;
 	struct task_struct *tsk;
@@ -147,7 +147,7 @@ void __sched __down_read(struct rw_semaphore *sem)
 
 	spin_lock_irqsave(&sem->wait_lock, flags);
 
-	if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
+	if (sem->activity >= 0 && (unfair || list_empty(&sem->wait_list))) {
 		/* granted */
 		sem->activity++;
 		spin_unlock_irqrestore(&sem->wait_lock, flags);
@@ -162,7 +162,11 @@ void __sched __down_read(struct rw_semaphore *sem)
 	waiter.flags = RWSEM_WAITING_FOR_READ;
 	get_task_struct(tsk);
 
-	list_add_tail(&waiter.list, &sem->wait_list);
+	if (unfair) {
+		list_add(&waiter.list, &sem->wait_list);
+	} else {
+		list_add_tail(&waiter.list, &sem->wait_list);
+	}
 
 	/* we don't need to touch the semaphore struct anymore */
 	spin_unlock_irqrestore(&sem->wait_lock, flags);
Signature · 1 line
1.7.0.1
#24 lore raw

Re: [PATCH 09/12] generic rwsem: implement down_read_unfair

Quoted 3 lines · Michel Lespinasse

/*
+ * lock for reading - skip waiting writers
+ */

They may also skip waiting readers, if such are queued behind a writer.

David

#25 lore raw

PATCH 10/12 rwsem: down_read_unfair infrastructure support

In reply to Michel Lespinasse

Add rwsem_down_read_unfair_failed() function in the non-generic rwsem library code, similar to rwsem_down_read_failed() except that blocked threads are placed at the head of the queue.

---
 lib/rwsem.c |   22 +++++++++++++++++++++-
 1 files changed, 21 insertions(+), 1 deletions(-)
lib/rwsem.c +21 -1
index 1702524..689d4a2 100644
@@ -34,6 +34,7 @@ struct rwsem_waiter {
 	unsigned int flags;
 #define RWSEM_WAITING_FOR_READ	0x00000001
 #define RWSEM_WAITING_FOR_WRITE	0x00000002
+#define RWSEM_UNFAIR            0x00000004
 };
 
 #define RWSEM_WAKE_ANY        0 /* Wake whatever's at head of wait list */
@@ -174,7 +175,11 @@ rwsem_down_failed_common(struct rw_semaphore *sem,
 
 	if (list_empty(&sem->wait_list))
 		adjustment += RWSEM_WAITING_BIAS;
-	list_add_tail(&waiter->list, &sem->wait_list);
+
+	if (flags & RWSEM_UNFAIR)
+		list_add(&waiter.list, &sem->wait_list);
+	else
+		list_add_tail(&waiter.list, &sem->wait_list);
 
 	/* we're now waiting on the lock, but no longer actively read-locking */
 	count = rwsem_atomic_update(adjustment, sem);
@@ -215,6 +220,21 @@ rwsem_down_read_failed(struct rw_semaphore *sem)
 					-RWSEM_ACTIVE_READ_BIAS);
 }
 
+#ifdef __HAVE_DOWN_READ_UNFAIR
+
+/*
+ * wait for the read lock to be granted - skip waiting writers
+ */
+asmregparm struct rw_semaphore __sched *
+rwsem_down_read_unfair_failed(struct rw_semaphore *sem)
+{
+	return rwsem_down_failed_common(sem,
+					RWSEM_WAITING_FOR_READ | RWSEM_UNFAIR,
+					-RWSEM_ACTIVE_READ_BIAS);
+}
+
+#endif
+
 /*
  * wait for the write lock to be granted
  */
Signature · 1 line
1.7.0.1
#26 lore raw

PATCH 11/12 x86 rwsem: down_read_unfair implementation

In reply to Michel Lespinasse

RWSEM_ACTIVE_WRITE_BIAS is set to be 'more negative' than RWSEM_WAITING_BIAS so that down_read_unfair() can check for active writers by comparing the rwsem count against RWSEM_WAITING_BIAS.

---
 arch/x86/include/asm/rwsem.h |   43 ++++++++++++++++++++++++++++++++++-------
 arch/x86/lib/rwsem_64.S      |   10 +++++++++
 arch/x86/lib/semaphore_32.S  |   17 ++++++++++++++++
 3 files changed, 62 insertions(+), 8 deletions(-)
arch/x86/include/asm/rwsem.h +35 -8
index a15b84d..0b3a924 100644
@@ -16,11 +16,10 @@
  * if there are writers (and maybe) readers waiting (in which case it goes to
  * sleep).
  *
- * The value of WAITING_BIAS supports up to 32766 waiting processes. This can
- * be extended to 65534 by manually checking the whole MSW rather than relying
- * on the S flag.
+ * The WRITE_BIAS value supports up to 32767 processes simultaneously
+ * trying to acquire a write lock.
  *
- * The value of ACTIVE_BIAS supports up to 65535 active processes.
+ * The value of ACTIVE_BIAS supports up to 32767 active processes.
  *
  * This should be totally fair - if anything is waiting, a process that wants a
  * lock will go to the back of the queue. When the currently active lock is
@@ -48,6 +47,8 @@ struct rwsem_waiter;
 extern asmregparm struct rw_semaphore *
  rwsem_down_read_failed(struct rw_semaphore *sem);
 extern asmregparm struct rw_semaphore *
+ rwsem_down_read_unfair_failed(struct rw_semaphore *sem);
+extern asmregparm struct rw_semaphore *
  rwsem_down_write_failed(struct rw_semaphore *sem);
 extern asmregparm struct rw_semaphore *
  rwsem_wake(struct rw_semaphore *);
@@ -63,16 +64,19 @@ extern asmregparm struct rw_semaphore *
  */
 
 #ifdef CONFIG_X86_64
-# define RWSEM_ACTIVE_MASK		0xffffffffL
+# define RWSEM_ACTIVE_MASK		0x7fffffffL
 #else
-# define RWSEM_ACTIVE_MASK		0x0000ffffL
+# define RWSEM_ACTIVE_MASK		0x00007fffL
 #endif
 
 #define RWSEM_UNLOCKED_VALUE		0x00000000L
 #define RWSEM_ACTIVE_BIAS		0x00000001L
 #define RWSEM_WAITING_BIAS		(-RWSEM_ACTIVE_MASK-1)
 #define RWSEM_ACTIVE_READ_BIAS		RWSEM_ACTIVE_BIAS
-#define RWSEM_ACTIVE_WRITE_BIAS		(RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
+#define RWSEM_ACTIVE_WRITE_BIAS		(2 * RWSEM_WAITING_BIAS + \
+					 RWSEM_ACTIVE_BIAS)
+
+#define __HAVE_DOWN_READ_UNFAIR
 
 typedef signed long rwsem_count_t;
 
@@ -129,6 +133,28 @@ static inline void __down_read(struct rw_semaphore *sem)
 }
 
 /*
+ * lock for reading - skip waiting writers
+ */
+static inline void __down_read_unfair(struct rw_semaphore *sem)
+{
+	rwsem_count_t tmp;
+
+	tmp = RWSEM_ACTIVE_READ_BIAS;
+	asm volatile("# beginning down_read_unfair\n\t"
+		     LOCK_PREFIX "  xadd      %1,(%2)\n\t"
+		     /* adds 0x00000001, returns the old value */
+		     "  cmp       %4,%1\n\t"
+		     /* was the count >= RWSEM_WAITING_BIAS before? */
+		     "  jge       1f\n"
+		     "  call call_rwsem_down_read_unfair_failed\n"
+		     "1:\n"
+		     "# ending down_read_unfair"
+		     : "+m" (sem->count), "=r" (tmp)
+		     : "a" (sem), "1" (tmp), "re" (RWSEM_WAITING_BIAS)
+		     : "memory", "cc");
+}
+
+/*
  * trylock for reading -- returns 1 if successful, 0 if contention
  */
 static inline int __down_read_trylock(struct rw_semaphore *sem)
@@ -248,7 +274,8 @@ static inline void __downgrade_write(struct rw_semaphore *sem)
 		     "1:\n\t"
 		     "# ending __downgrade_write\n"
 		     : "+m" (sem->count)
-		     : "a" (sem), "er" (-RWSEM_WAITING_BIAS)
+		     : "a" (sem),
+		       "er" (RWSEM_ACTIVE_READ_BIAS - RWSEM_ACTIVE_WRITE_BIAS)
 		     : "memory", "cc");
 }
 
arch/x86/lib/rwsem_64.S +10 -0
index 770a387..328ef64 100644
@@ -51,6 +51,16 @@ ENTRY(call_rwsem_down_read_failed)
 	ret
 	ENDPROC(call_rwsem_down_read_failed)
 
+ENTRY(call_rwsem_down_read_unfair_failed)
+	save_common_regs
+	pushq %rdx
+	movq %rax,%rdi
+	call rwsem_down_read_unfair_failed
+	popq %rdx
+	restore_common_regs
+	ret
+	ENDPROC(call_rwsem_down_read_failed)
+
 ENTRY(call_rwsem_down_write_failed)
 	save_common_regs
 	movq %rax,%rdi
arch/x86/lib/semaphore_32.S +17 -0
index 63dbf75..115d2ad 100644
@@ -89,6 +89,23 @@ ENTRY(call_rwsem_down_read_failed)
 	CFI_ENDPROC
 	ENDPROC(call_rwsem_down_read_failed)
 
+ENTRY(call_rwsem_down_read_unfair_failed)
+	CFI_STARTPROC
+	push %ecx
+	CFI_ADJUST_CFA_OFFSET 4
+	CFI_REL_OFFSET ecx,0
+	push %edx
+	CFI_ADJUST_CFA_OFFSET 4
+	CFI_REL_OFFSET edx,0
+	call rwsem_down_read_unfair_failed
+	pop %edx
+	CFI_ADJUST_CFA_OFFSET -4
+	pop %ecx
+	CFI_ADJUST_CFA_OFFSET -4
+	ret
+	CFI_ENDPROC
+	ENDPROC(call_rwsem_down_read_failed)
+
 ENTRY(call_rwsem_down_write_failed)
 	CFI_STARTPROC
 	push %ecx
Signature · 1 line
1.7.0.1
#27 lore raw

Re: [PATCH 11/12] x86 rwsem: down_read_unfair implementation

arch/x86/include/asm/rwsem.h extern asmregparm struct rw_semaphore * · line 77

Quoted 4 lines · Michel Lespinasse

#define RWSEM_WAITING_BIAS (-RWSEM_ACTIVE_MASK-1)
#define RWSEM_ACTIVE_READ_BIAS RWSEM_ACTIVE_BIAS

arch/x86/include/asm/rwsem.h +2 -0
+#define RWSEM_ACTIVE_WRITE_BIAS		(2 * RWSEM_WAITING_BIAS + \
+					 RWSEM_ACTIVE_BIAS)

These are getting a bit meaningless. Can you replace them with hex numbers to make it clearer what's going on? Putting a worked example in the patch description would be good too.

David

#28 lore raw

PATCH 12/12 Use down_read_unfair() for /sys/<pid>/exe and /sys/<pid>/maps files

In reply to Michel Lespinasse

This helps in the following situation:
- Thread A takes a page fault while reading or writing memory. do_page_fault() acquires the mmap_sem for read and blocks on disk (either reading the page from file, or hitting swap) for a long time.
- Thread B does an mmap call and blocks trying to acquire the mmap_sem for write
- Thread C is a monitoring process trying to read every /proc/pid/maps in the system. This requires acquiring the mmap_sem for read. Thread C blocks behind B, waiting for A to release the rwsem. If thread C could be allowed to run in parallel with A, it would probably get done long before thread A's disk access completes, thus not actually slowing down thread B.

Test results with down_read_unfair_test (10 seconds):

2.6.33.3:
threadA completes ~600 faults threadB completes ~300 mmap/munmap cycles threadC completes ~600 /proc/pid/maps reads

2.6.33.3 + down_read_unfair:
threadA completes ~600 faults
threadB completes ~300 mmap/munmap cycles threadC completes ~160000 /proc/pid/maps reads

---
 fs/proc/base.c       |    2 +-
 fs/proc/task_mmu.c   |    2 +-
 fs/proc/task_nommu.c |    2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)
fs/proc/base.c +1 -1
index 8418fcc..9132488 100644
@@ -1367,7 +1367,7 @@ struct file *get_mm_exe_file(struct mm_struct *mm)
 
 	/* We need mmap_sem to protect against races with removal of
 	 * VM_EXECUTABLE vmas */
-	down_read(&mm->mmap_sem);
+	down_read_unfair(&mm->mmap_sem);
 	exe_file = mm->exe_file;
 	if (exe_file)
 		get_file(exe_file);
fs/proc/task_mmu.c +1 -1
index 0705534..09647ad 100644
@@ -123,7 +123,7 @@ static void *m_start(struct seq_file *m, loff_t *pos)
 	mm = mm_for_maps(priv->task);
 	if (!mm)
 		return NULL;
-	down_read(&mm->mmap_sem);
+	down_read_unfair(&mm->mmap_sem);
 
 	tail_vma = get_gate_vma(priv->task);
 	priv->tail_vma = tail_vma;
fs/proc/task_nommu.c +1 -1
index 46d4b5d..56ca830 100644
@@ -194,7 +194,7 @@ static void *m_start(struct seq_file *m, loff_t *pos)
 		priv->task = NULL;
 		return NULL;
 	}
-	down_read(&mm->mmap_sem);
+	down_read_unfair(&mm->mmap_sem);
 
 	/* start from the Nth VMA */
 	for (p = rb_first(&mm->mm_rb); p; p = rb_next(p))
Signature · 1 line
1.7.0.1
#29 lore raw

Re: [PATCH 12/12] Use down_read_unfair() for /sys/<pid>/exe and /sys/<pid>/maps files

Quoted 6 lines · Michel Lespinasse

- Thread C is a monitoring process trying to read every /proc/pid/maps in the system. This requires acquiring the mmap_sem for read. Thread C blocks behind B, waiting for A to release the rwsem. If thread C could be allowed to run in parallel with A, it would probably get done long before thread A's disk access completes, thus not actually slowing down thread B.

Is it possible for someone to execute a DoS attack on another process using a bunch of threads reading /proc/pid/maps?

David

#30 lore raw

Re: [PATCH 12/12] Use down_read_unfair() for /sys/<pid>/exe and /sys/<pid>/maps files

In reply to Michel Lespinasse
Quoted 20 lines

This helps in the following situation:
- Thread A takes a page fault while reading or writing memory. do_page_fault() acquires the mmap_sem for read and blocks on disk (either reading the page from file, or hitting swap) for a long time.
- Thread B does an mmap call and blocks trying to acquire the mmap_sem for write
- Thread C is a monitoring process trying to read every /proc/pid/maps in the system. This requires acquiring the mmap_sem for read. Thread C blocks behind B, waiting for A to release the rwsem. If thread C could be allowed to run in parallel with A, it would probably get done long before thread A's disk access completes, thus not actually slowing down thread B.

Test results with down_read_unfair_test (10 seconds):

2.6.33.3:
threadA completes ~600 faults
threadB completes ~300 mmap/munmap cycles
threadC completes ~600 /proc/pid/maps reads

Quoted 6 lines

2.6.33.3 + down_read_unfair:
threadA completes ~600 faults
threadB completes ~300 mmap/munmap cycles
threadC completes ~160000 /proc/pid/maps reads

Is it good idea?
So I think /proc shouldn't use unfair thing as backdoor. It doesn't only makes performance improvement, but also DoS chance is there.

Please use this feature only in internal.

Quoted 53 lines
---
 fs/proc/base.c       |    2 +-
 fs/proc/task_mmu.c   |    2 +-
 fs/proc/task_nommu.c |    2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)
fs/proc/base.c +1 -1
index 8418fcc..9132488 100644
@@ -1367,7 +1367,7 @@ struct file *get_mm_exe_file(struct mm_struct *mm)
 
 	/* We need mmap_sem to protect against races with removal of
 	 * VM_EXECUTABLE vmas */
-	down_read(&mm->mmap_sem);
+	down_read_unfair(&mm->mmap_sem);
 	exe_file = mm->exe_file;
 	if (exe_file)
 		get_file(exe_file);
fs/proc/task_mmu.c +1 -1
index 0705534..09647ad 100644
@@ -123,7 +123,7 @@ static void *m_start(struct seq_file *m, loff_t *pos)
 	mm = mm_for_maps(priv->task);
 	if (!mm)
 		return NULL;
-	down_read(&mm->mmap_sem);
+	down_read_unfair(&mm->mmap_sem);
 
 	tail_vma = get_gate_vma(priv->task);
 	priv->tail_vma = tail_vma;
fs/proc/task_nommu.c +1 -1
index 46d4b5d..56ca830 100644
@@ -194,7 +194,7 @@ static void *m_start(struct seq_file *m, loff_t *pos)
 		priv->task = NULL;
 		return NULL;
 	}
-	down_read(&mm->mmap_sem);
+	down_read_unfair(&mm->mmap_sem);
 
 	/* start from the Nth VMA */
 	for (p = rb_first(&mm->mm_rb); p; p = rb_next(p))
Signature · 7 lines
1.7.0.1

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
#31 lore raw

Re: [PATCH 12/12] Use down_read_unfair() for /sys/<pid>/exe and /sys/<pid>/maps files

Quoted 25 lines · KOSAKI Motohiro
Quoted 25 lines

This helps in the following situation:
- Thread A takes a page fault while reading or writing memory. do_page_fault() acquires the mmap_sem for read and blocks on disk (either reading the page from file, or hitting swap) for a long time.
- Thread B does an mmap call and blocks trying to acquire the mmap_sem for write
- Thread C is a monitoring process trying to read every /proc/pid/maps in the system. This requires acquiring the mmap_sem for read. Thread C blocks behind B, waiting for A to release the rwsem.  If thread C could be allowed to run in parallel with A, it would probably get done long before thread A's disk access completes, thus not actually slowing down thread B.

Test results with down_read_unfair_test (10 seconds):

2.6.33.3:
threadA completes ~600 faults threadB completes ~300 mmap/munmap cycles threadC completes ~600 /proc/pid/maps reads

2.6.33.3 + down_read_unfair:
threadA completes ~600 faults
threadB completes ~300 mmap/munmap cycles threadC completes ~160000 /proc/pid/maps reads

Quoted 6 lines
Quoted 1 line

Is it good idea?
So I think /proc shouldn't use unfair thing as backdoor. It doesn't only makes performance improvement, but also DoS chance is there.

I am not entirely surprised that there is some level of opposition to this change (which is in part why it went last in the series).

Besides keeping it internal, would there be ways to make it acceptable to the community ? For example, would it be fine if unfair behavior was only used if the caller thread runs with root priviledge ?

In my opinion the optimal behavior would be if the rwsem could be allowed to be grabbed unfairly only as long as there are still fair readers on it. However, I don't see how to achieve this given that we don't want to slow down the regular, fair code paths.

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#32 lore raw

Re: [PATCH 12/12] Use down_read_unfair() for /sys/<pid>/exe and /sys/<pid>/maps files

Quoted 11 lines
Quoted 4 lines

Is it good idea?
So I think /proc shouldn't use unfair thing as backdoor. It doesn't only makes performance improvement, but also DoS chance is there.

I am not entirely surprised that there is some level of opposition to this change (which is in part why it went last in the series).

Besides keeping it internal, would there be ways to make it acceptable to the community ? For example, would it be fine if unfair behavior was only used if the caller thread runs with root priviledge ?

Umm. seems no good idea.

Why?

In nowadays, root priviledge should be considered to blocked by security module. but this using way can't combinate with any security module. at least we need more proper and security friendly interface.

Quoted 4 lines

In my opinion the optimal behavior would be if the rwsem could be allowed to be grabbed unfairly only as long as there are still fair readers on it. However, I don't see how to achieve this given that we don't want to slow down the regular, fair code paths.

dumb question.
Why do you need to read /proc/<pid>/exec and /proc/<pid>/maps? To make new /proc files makes help?

IOW, do we really need unfair reader? can't we make more fine grained lock?