splice mmap_sem deadlock

I'm fairly sure this is the right patch... but the explicit comment has me thinking I missed something? (there is also a down_write->fault deadlock in the splice code in -mm, however when talking with Jens about that code, we might have an idea for a different approach using preexisting vmas rather than setting them up with splice -- so this patch is just for mainline)

mmap_sem cannot be taken recursively for read, due to the FIFO nature of the rwsem, and the presence of possible write lockers.

process A process B
down_read(mmap_sem); [1]
get_user(); down_write(mmap_sem); [2]
-> page fault
down_read(mmap_sem); [3]

[1] will never be released until [3] can be taken and released, however:
[2] blocks on [1]; [3] blocks on [2].

Signed-off-by Nick Piggin <[email protected]>

---
Index: linux-2.6/fs/splice.c
===================================================================

fs/splice.c +2 -8

@@ -1534,12 +1534,6 @@ static int get_iovec_page_array(const st
 {
 	int buffers = 0, error = 0;
 
-	/*
-	 * It's ok to take the mmap_sem for reading, even
-	 * across a "get_user()".
-	 */
-	down_read(&current->mm->mmap_sem);
-
 	while (nr_vecs) {
 		unsigned long off, npages;
 		void __user *base;

@@ -1583,9 +1577,11 @@ static int get_iovec_page_array(const st
 		if (npages > PIPE_BUFFERS - buffers)
 			npages = PIPE_BUFFERS - buffers;
 
+		down_read(&current->mm->mmap_sem);
 		error = get_user_pages(current, current->mm,
 				       (unsigned long) base, npages, 0, 0,
 				       &pages[buffers], NULL);
+		up_read(&current->mm->mmap_sem);
 
 		if (unlikely(error <= 0))
 			break;

@@ -1624,8 +1620,6 @@ static int get_iovec_page_array(const st
 		iov++;
 	}
 
-	up_read(&current->mm->mmap_sem);
-
 	if (buffers)
 		return buffers;
 

It does looks suspicious. It was actually Linus who originally suggested this approach and wrote that comment - Linus?

Quoted 3 lines · Jens Axboe

It does looks suspicious. It was actually Linus who originally suggested this approach and wrote that comment - Linus?

Well, it used to be true, long time ago. It probably was still true in the original splice patch back way back when. But yeah, rwsemaphores broke that (very useful) trick in the name of fairness ;(

It actually looks like it was buggy from day 1 there, unfortunately. The code is from april 2006 and used down_read() even then.

So can you apply Nicks patch

Quoted 3 lines · Jens Axboe

It actually looks like it was buggy from day 1 there, unfortunately. The code is from april 2006 and used down_read() even then.

I was thinking of my *original* patch from way back when. But that one didn't actually do any of that stuff so no, it wasn't from there.

Quoted 1 line

So can you apply Nicks patch

I don't even have it, I only have a quoted-corrupted version of it. I wasn't originally cc'd.

Hmm, part of me doesn't like this patch, since we now end up beating on mmap_sem for each part of the vec. It's fine for a stable patch, but how about

- prefaulting the iovec
- using __get_user()
- only dropping/regrabbing the lock if we have to fault

So something like the appended might work. Untested.

Quoted 2 lines · Linus Torvalds

So something like the appended might work. Untested.

Btw, it migth be cleaner to separate out this thing as a function of it's own, ie something like

/*
* Do a copy-from-user while holding the mmap_semaphore for reading */
int copy_from_user_mmap_sem(void *dst, const void __user *src, size_t n)

  {
	int partial;

	pagefault_disable();
	partial = __copy_from_user_inatomic(dst, src, n);
	pagefault_enable();

	if (!partial)
		return 0;
	up_read(&current->mm->mmap_sem);
	partial = copy_from_user(dst, src, n);
	down_read(&current->mm->mmap_sem);

	return partial ? -EFAULT : 0;

}

in case anybody else needs it. And even if nobody else does, making it a static inline function in fs/splice.c would at least separate out this thing from the core functionality, and just help keep things clear.

Wanna test that thing?

Quoted 2 lines · Linus Torvalds

So something like the appended might work. Untested.

Btw, it migth be cleaner to separate out this thing as a function of it's own, ie something like

/*
* Do a copy-from-user while holding the mmap_semaphore for reading */
int copy_from_user_mmap_sem(void *dst, const void __user *src, size_t n)

  {
	int partial;

	pagefault_disable();
	partial = __copy_from_user_inatomic(dst, src, n);
	pagefault_enable();

	if (!partial)
		return 0;
	up_read(&current->mm->mmap_sem);
	partial = copy_from_user(dst, src, n);
	down_read(&current->mm->mmap_sem);

	return partial ? -EFAULT : 0;

}

in case anybody else needs it. And even if nobody else does, making it a static inline function in fs/splice.c would at least separate out this thing from the core functionality, and just help keep things clear.

Wanna test that thing?

/*
+ * Do a copy-from-user while holding the mmap_semaphore for reading. If we
+ * have to fault the user page in, we must drop the mmap_sem to avoid a
+ * deadlock in the page fault handling (it wants to grab mmap_sem too, but for
+ * writing). This assumes that we will very rarely hit the partial != 0 path,
+ * or this will not be a win.
+ */

The comment is wrong.

Quoted 8 lines · Jens Axboe

/*
+ * Do a copy-from-user while holding the mmap_semaphore for reading. If we
+ * have to fault the user page in, we must drop the mmap_sem to avoid a
+ * deadlock in the page fault handling (it wants to grab mmap_sem too, but for
+ * writing). This assumes that we will very rarely hit the partial != 0 path,
+ * or this will not be a win.
+ */

Page faulting only grabs it for reading, and having a page fault happen is not problematic in itself. Readers *do* nest.

What is problematic is:

	thread#1			thread#2

	get_iovec_page_array
	down_read()
	.. everything ok so far ..
					mmap()
					down_write()
					.. correctly blocks on the reader ..
					.. everything ok so far ..

	.. pagefault ..
	down_read()
	.. fairness code now blocks on the waiting writer! ..
	.. oops. We're deadlocked ..

So the problem is that while readers do nest nicely, they only do so if no potential writers can possibly exist (which of course never happens: an rwlock with no writers is a no-op ;).

Sounds very similar to the problems we had with CPU hotplug earlier. It's a rwlock locking anti-pattern. I know that recursive locks have been frowned upon earlier, but I wonder if there is a case here. Of-course recursive locks would not be *fair*.

Quoted 4 lines · Balbir Singh

Sounds very similar to the problems we had with CPU hotplug earlier. It's a rwlock locking anti-pattern. I know that recursive locks have been frowned upon earlier, but I wonder if there is a case here. Of-course recursive locks would not be *fair*.

The problem with recursive locks is that they are inevitably done wrong.

For example, the "natural" way to do them is to just save the process ID or something like that. Which is utter crap. Yet, people do it *every* single time (yes, I've done it too, I admit).

The thing is, "recursive" doesn't mean "same CPU" or "same process" or "same thread" or anything like that. It means "same *dependency-chain*". With the very real implication that you literally have to pass the "lock instance" (whether that is a cookie or anything else) around, and thus really generate the proper chain.

For example, in CPU hotplug, the dependency chain really did end up moving between different execution contexts, iirc (eg from process context into kernel workqueues).

So we could add some kind of recursive interface that maintained a list of ownership or whatever, but the fact remains that after 16 years, we still haven't really needed it, except for code that is so ugly and broken that pretty much everybody really feels it should be rewritten (and generally for *other* reasons) anyway.

So I'm not categorically against nesting, but I'm certainly down on it, and I think it's almost always done wrong.

The comment is wrong.

Quoted 8 lines · Jens Axboe

/*
+ * Do a copy-from-user while holding the mmap_semaphore for reading. If we
+ * have to fault the user page in, we must drop the mmap_sem to avoid a
+ * deadlock in the page fault handling (it wants to grab mmap_sem too, but for
+ * writing). This assumes that we will very rarely hit the partial != 0 path,
+ * or this will not be a win.
+ */

Page faulting only grabs it for reading, and having a page fault happen is not problematic in itself. Readers *do* nest.

What is problematic is:

	thread#1			thread#2

	get_iovec_page_array
	down_read()
	.. everything ok so far ..
					mmap()
					down_write()
					.. correctly blocks on the reader ..
					.. everything ok so far ..

	.. pagefault ..
	down_read()
	.. fairness code now blocks on the waiting writer! ..
	.. oops. We're deadlocked ..

So the problem is that while readers do nest nicely, they only do so if no potential writers can possibly exist (which of course never happens: an rwlock with no writers is a no-op ;).

Quoted 5 lines · Jens Axboe

Hmm, part of me doesn't like this patch, since we now end up beating on mmap_sem for each part of the vec. It's fine for a stable patch, but how about

Quoted 3 lines

- prefaulting the iovec
- using __get_user()
- only dropping/regrabbing the lock if we have to fault

"__get_user()" doesn't help any. But we should do the same thing we do for generic_file_write(), or whatever - probe it while in an atomic region.

So something like the appended might work. Untested.

Linus

---
 fs/splice.c |   32 +++++++++++++++++++++-----------
 1 files changed, 21 insertions(+), 11 deletions(-)

fs/splice.c +18 -11

index c010a72..07e880e 100644
@@ -1236,31 +1236,41 @@ static int get_iovec_page_array(const struct iovec __user *iov,
 {
 	int buffers = 0, error = 0;
 
-	/*
-	 * It's ok to take the mmap_sem for reading, even
-	 * across a "get_user()".
-	 */
 	down_read(&current->mm->mmap_sem);
 
 	while (nr_vecs) {
 		unsigned long off, npages;
+		struct iovec entry;
 		void __user *base;
 		size_t len;
 		int i;
 
 		/*
-		 * Get user address base and length for this iovec.
+		 * We do not want to recursively take the mmap_sem semaphore
+		 * on a page fault, since that could deadlock with a writer
+		 * that comes in in the middle. So disable pagefaults, and
+		 * do it the slow way if the copy fails..
 		 */
-		error = get_user(base, &iov->iov_base);
-		if (unlikely(error))
-			break;
-		error = get_user(len, &iov->iov_len);
-		if (unlikely(error))
-			break;
+		pagefault_disable();
+		i = __copy_from_user_inatomic(&entry, iov, sizeof(entry));
+		pagefault_enable();
+
+		if (unlikely(i)) {
+			up_read(&current->mm->mmap_sem);
+			i = copy_from_user(&entry, iov, sizeof(entry));
+			down_read(&current->mm->mmap_sem);
+			error = -EFAULT;
+			if (i)
+				break;
+		}
+

Quoted 15 lines · Linus Torvalds

Quoted 8 lines · Jens Axboe

Hmm, part of me doesn't like this patch, since we now end up beating on mmap_sem for each part of the vec. It's fine for a stable patch, but how about

- prefaulting the iovec
- using __get_user()
- only dropping/regrabbing the lock if we have to fault

"__get_user()" doesn't help any. But we should do the same thing we do for generic_file_write(), or whatever - probe it while in an atomic region.

Quoted 1 line

So something like the appended might work. Untested.

I got an idea for getting rid of mmap_sem from here completely. Which is why I was looking at these callers in the first place.

It would be really convenient and help me play with the idea if mmap_sem is wrapped closely around get_user_pages where possible...

If you're really worried about mmap_sem batching here, can you just avoid this complexity and do all the get_user()s up-front, before taking mmap_sem at all? You only have to save PIPE_BUFFERS number of them.

Quoted 16 lines · Nick Piggin

Quoted 15 lines · Linus Torvalds

Quoted 8 lines · Jens Axboe

Hmm, part of me doesn't like this patch, since we now end up beating on mmap_sem for each part of the vec. It's fine for a stable patch, but how about

- prefaulting the iovec
- using __get_user()
- only dropping/regrabbing the lock if we have to fault

"__get_user()" doesn't help any. But we should do the same thing we do for generic_file_write(), or whatever - probe it while in an atomic region.

Quoted 7 lines

Quoted 1 line

So something like the appended might work. Untested.

I got an idea for getting rid of mmap_sem from here completely. Which is why I was looking at these callers in the first place.

It would be really convenient and help me play with the idea if mmap_sem is wrapped closely around get_user_pages where possible...

Well, move it back there in your first patch? Not a big deal, surely :-)

Quoted 4 lines

If you're really worried about mmap_sem batching here, can you just avoid this complexity and do all the get_user()s up-front, before taking mmap_sem at all? You only have to save PIPE_BUFFERS number of them.

Sure, that is easily doable at the cost of some stack. I have other patches that grow PIPE_BUFFERS dynamically in the pipeline, so I'd prefer not to since that'll then turn into a dynamic allocation.

Quoted 32 lines · Jens Axboe

Quoted 16 lines · Nick Piggin

Quoted 15 lines · Linus Torvalds

Quoted 8 lines · Jens Axboe

Hmm, part of me doesn't like this patch, since we now end up beating on mmap_sem for each part of the vec. It's fine for a stable patch, but how about

- prefaulting the iovec
- using __get_user()
- only dropping/regrabbing the lock if we have to fault

"__get_user()" doesn't help any. But we should do the same thing we do for generic_file_write(), or whatever - probe it while in an atomic region.

Quoted 7 lines

Quoted 1 line

So something like the appended might work. Untested.

I got an idea for getting rid of mmap_sem from here completely. Which is why I was looking at these callers in the first place.

It would be really convenient and help me play with the idea if mmap_sem is wrapped closely around get_user_pages where possible...

Well, move it back there in your first patch? Not a big deal, surely :-)

Quoted 4 lines

If you're really worried about mmap_sem batching here, can you just avoid this complexity and do all the get_user()s up-front, before taking mmap_sem at all? You only have to save PIPE_BUFFERS number of them.

Quoted 3 lines

Sure, that is easily doable at the cost of some stack. I have other patches that grow PIPE_BUFFERS dynamically in the pipeline, so I'd prefer not to since that'll then turn into a dynamic allocation.

You already have much more PIPE_BUFFERS stuff on the stack. If it gets much bigger, you should dynamically allocate all this anyway, no?

Quoted 3 lines · Nick Piggin

You already have much more PIPE_BUFFERS stuff on the stack. If it gets much bigger, you should dynamically allocate all this anyway, no?

Yep, but then it's one more item that has to be dynamically allocated.

Quoted 3 lines · Jens Axboe

It does looks suspicious. It was actually Linus who originally suggested this approach and wrote that comment - Linus?

Well, it used to be true, long time ago. It probably was still true in the original splice patch back way back when. But yeah, rwsemaphores broke that (very useful) trick in the name of fairness ;(