Documentation/vm/locking: why not hold two PT locks?

Documentation/vm/locking: why not hold two PT locks?

[Ed L Cashin]

Hi.  Documentation/vm/locking says one must not simultaneously hold
the page table lock on mm A and mm B.  Is that true?  Where is the
danger?

-- 
--Ed L Cashin            |   PGP public key:
  ecashin@uga.edu        |   http://noserose.net/e/pgp/

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: Documentation/vm/locking: why not hold two PT locks?

[Robert Love]

On Sun, 2004-02-08 at 16:18 -0500, Ed L Cashin wrote:

> Hi.  Documentation/vm/locking says one must not simultaneously hold
> the page table lock on mm A and mm B.  Is that true?  Where is the
> danger?

There isn't a proscribed lock ordering hierarchy, so you can deadlock.

Assume thread 1 obtains the lock on mm A.

Assume thread 2 obtains the lock on mm B.

Assume thread 1 now obtains the lock on mm B - it is taken, so spin
waiting.

Assume thread 2 now obtains the lock on mm A - it too is taken, so spin
waiting.

Boom..

	Robert Love




--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: Documentation/vm/locking: why not hold two PT locks?

[Ed L Cashin]

Robert Love <rml@ximian.com> writes:

> On Sun, 2004-02-08 at 16:18 -0500, Ed L Cashin wrote:
>
>> Hi.  Documentation/vm/locking says one must not simultaneously hold
>> the page table lock on mm A and mm B.  Is that true?  Where is the
>> danger?
>
> There isn't a proscribed lock ordering hierarchy, so you can deadlock.
>
> Assume thread 1 obtains the lock on mm A.
>
> Assume thread 2 obtains the lock on mm B.
>
> Assume thread 1 now obtains the lock on mm B - it is taken, so spin
> waiting.
>
> Assume thread 2 now obtains the lock on mm A - it too is taken, so spin
> waiting.
>
> Boom..

If that's all there is to it, then in my case, I have imposed a
locking hierarchy on my own code, so that wouldn't happen in my code.
I have a semaphore "S" outside of mmap_sem and page_table_lock.  Every
call path that can get to my code takes S before getting the
mmap_sem.  

  T1 gets S
  T1 gets mm A's mmap_sem
  T2 sleeps trying for S
  T1 gets A's PT lock
  T1 gets B's PT lock
  T1 clears a PTE in B 
  (I'd like to also be able to safely copy a PTE from B to A here)

  T1 puts B's PT lock
  T1 puts A's PT lock
  T1 puts A's mmap_sem
  T1 puts S

So it looks like my code is safe but not so efficient, since T2 has to
sleep when it doesn't get the semaphore S.  Is there some other
complication I'm missing?

-- 
--Ed L Cashin     PGP public key: http://noserose.net/e/pgp/

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: Documentation/vm/locking: why not hold two PT locks?

[Robert Love]

On Sun, 2004-02-08 at 16:47 -0500, Ed L Cashin wrote:

> If that's all there is to it, then in my case, I have imposed a
> locking hierarchy on my own code, so that wouldn't happen in my code.
> I have a semaphore "S" outside of mmap_sem and page_table_lock.  Every
> call path that can get to my code takes S before getting the
> mmap_sem.  

Well, you don't follow a locking hierarchy either, you just have a
global synchronizer (your semaphore S).  Same effect, sure, you cannot
deadlock.

But anyone else who touches two or more PT's will deadlock.

> So it looks like my code is safe but not so efficient, since T2 has to
> sleep when it doesn't get the semaphore S.  Is there some other
> complication I'm missing?

It could be that _I_ am missing something, and there is another reason
why we don't grab more than one PT concurrently.  But the locking
hierarchy is still a concern.

	Robert Love


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: Documentation/vm/locking: why not hold two PT locks?

[Kanoj Sarcar]

--- Robert Love <rml@ximian.com> wrote:
> On Sun, 2004-02-08 at 16:47 -0500, Ed L Cashin
> wrote:
> 
> > If that's all there is to it, then in my case, I
> have imposed a
> > locking hierarchy on my own code, so that wouldn't
> happen in my code.
> > I have a semaphore "S" outside of mmap_sem and
> page_table_lock.  Every
> > call path that can get to my code takes S before
> getting the
> > mmap_sem.  
> 
> Well, you don't follow a locking hierarchy either,
> you just have a
> global synchronizer (your semaphore S).  Same
> effect, sure, you cannot
> deadlock.
> 
> But anyone else who touches two or more PT's will
> deadlock.
> 
> > So it looks like my code is safe but not so
> efficient, since T2 has to
> > sleep when it doesn't get the semaphore S.  Is
> there some other
> > complication I'm missing?
> 
> It could be that _I_ am missing something, and there
> is another reason
> why we don't grab more than one PT concurrently. 
> But the locking
> hierarchy is still a concern.
> 
> 	Robert Love
>

Hi,

Its been a while since I wrote up those rules in
the "locking" file, but the example that Robert has
pointed out involving two different threads, each 
crabbing one mm lock and trying for the next one,
is the deadlock I had in mind. There may have been
new changes in 2.5 timeframe that also requires
the rule, I am not sure.

Thanks.

Kanoj

> 
> --
> To unsubscribe, send a message with 'unsubscribe
> linux-mm' in
> the body to majordomo@kvack.org.  For more info on
> Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"aart@kvack.org">
> aart@kvack.org </a>


__________________________________
Do you Yahoo!?
Yahoo! Finance: Get your refund fast by filing online.
http://taxes.yahoo.com/filing.html
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: Documentation/vm/locking: why not hold two PT locks?

[Ed L Cashin]

Kanoj Sarcar <kanojsarcar@yahoo.com> writes:

...
> Its been a while since I wrote up those rules in
> the "locking" file, but the example that Robert has
> pointed out involving two different threads, each 
> crabbing one mm lock and trying for the next one,
> is the deadlock I had in mind. There may have been
> new changes in 2.5 timeframe that also requires
> the rule, I am not sure.

Thanks, Kanoj!

After further looking into it, one thing in Documentation/vm/locking
does seem out of date.  It says that "Page stealers hold kernel_lock
to protect against a bunch of races."

The only page stealing code that I can find is in rmap.c and vmscan.c.
When vmscan.c:shrink_caches and its callees need to unmap a page,
rmap.c:try_to_unmap gets called.  But nowhere is there a lock_kernel
call that I could find.  Instead, they use trylocks and get the page
table lock before stealing a page.

Are there other page stealers?

-- 
--Ed L Cashin     PGP public key: http://noserose.net/e/pgp/

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: Documentation/vm/locking: why not hold two PT locks?

[Kanoj Sarcar]

--- Ed L Cashin <ecashin@uga.edu> wrote:
> Kanoj Sarcar <kanojsarcar@yahoo.com> writes:
> 
> ...
> > Its been a while since I wrote up those rules in
> > the "locking" file, but the example that Robert
> has
> > pointed out involving two different threads, each 
> > crabbing one mm lock and trying for the next one,
> > is the deadlock I had in mind. There may have been
> > new changes in 2.5 timeframe that also requires
> > the rule, I am not sure.
> 
> Thanks, Kanoj!
> 
> After further looking into it, one thing in
> Documentation/vm/locking
> does seem out of date.  It says that "Page stealers
> hold kernel_lock
> to protect against a bunch of races."
> 
> The only page stealing code that I can find is in
> rmap.c and vmscan.c.
> When vmscan.c:shrink_caches and its callees need to
> unmap a page,
> rmap.c:try_to_unmap gets called.  But nowhere is
> there a lock_kernel
> call that I could find.  Instead, they use trylocks
> and get the page
> table lock before stealing a page.
> 
> Are there other page stealers?
> 

Hi,

When "locking" came into being, vmscan was the only
page stealer.

Thanks.

Kanoj

> -- 
> --Ed L Cashin     PGP public key:
> http://noserose.net/e/pgp/
> 
> --
> To unsubscribe, send a message with 'unsubscribe
> linux-mm' in
> the body to majordomo@kvack.org.  For more info on
> Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"aart@kvack.org">
> aart@kvack.org </a>


__________________________________
Do you Yahoo!?
Yahoo! Finance: Get your refund fast by filing online.
http://taxes.yahoo.com/filing.html
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: Documentation/vm/locking: why not hold two PT locks?

[Ed L Cashin]

Kanoj Sarcar <kanojsarcar@yahoo.com> writes:

...
> When "locking" came into being, vmscan was the only
> page stealer.

I tried to start a patch to the file, but I realize that I don't
really know how 2.6 is ensuring the existance of the backing store, so
I couldn't put that in.


--- Documentation/vm/locking.orig	Wed Nov 26 15:43:30 2003
+++ Documentation/vm/locking	Mon Feb  9 16:07:45 2004
@@ -7,19 +7,17 @@
 page_table_lock & mmap_sem
 --------------------------------------
 
-Page stealers pick processes out of the process pool and scan for 
-the best process to steal pages from. To guarantee the existence 
-of the victim mm, a mm_count inc and a mmdrop are done in swap_out().
-Page stealers hold kernel_lock to protect against a bunch of races.
-The vma list of the victim mm is also scanned by the stealer, 
-and the page_table_lock is used to preserve list sanity against the
-process adding/deleting to the list. This also guarantees existence
-of the vma. Vma existence is not guaranteed once try_to_swap_out() 
-drops the page_table_lock. To guarantee the existence of the underlying 
-file structure, a get_file is done before the swapout() method is 
-invoked. The page passed into swapout() is guaranteed not to be reused
-for a different purpose because the page reference count due to being
-present in the user's pte is not released till after swapout() returns.
+The page stealer in mm/vmscan.c picks pages out of the page cache and
+scans for the best pages to reclaim.  The mm/rmap.c:try_to_unmap
+function uses trylock to get the page_table_lock for each page table
+that has a mapping to the victim page.  Trylocks are used to avoid the
+deadlock that might otherwise occur, because the mmap_sem is not
+acquired first.
+
+The vma list of the victim mm is also scanned by the stealer, and the
+page_table_lock is used to preserve list sanity against the process
+adding/deleting to the list. This also guarantees existence of the
+vma.
 
 Any code that modifies the vmlist, or the vm_start/vm_end/
 vm_flags:VM_LOCKED/vm_next of any vma *in the list* must prevent 


-- 
--Ed L Cashin            |   PGP public key:
  ecashin@uga.edu        |   http://noserose.net/e/pgp/

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>