Documentation/vm/locking: why not hold two PT locks?
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?
Signature · 8 lines
--Ed L Cashin | PGP public key: [email protected] | http://noserose.net/e/pgp/ -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 3 lines · Ed L Cashin
Hi.
Documentation/vm/lockingsays 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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 12 lines · Robert Love
Quoted 3 lines · Ed L Cashin
Hi.
Documentation/vm/lockingsays 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.
Quoted 7 lines
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?
Signature · 7 lines
--Ed L Cashin PGP public key: http://noserose.net/e/pgp/ -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 5 lines · Ed L Cashin
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_semandpage_table_lock. Every call path that can get to my code takes S before getting themmap_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.
Quoted 3 lines
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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 28 lines · --- Robert Love
Quoted 1 line · Ed L Cashin
If that's all there is to it, then in my case, I
have imposed a
Quoted 1 line
locking hierarchy on my own code, so that wouldn't
happen in my code.
Quoted 1 line
I have a semaphore "S" outside of
mmap_semand
page_table_lock. EveryQuoted 1 line
call path that can get to my code takes S before
getting the
Quoted 1 line
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.
Quoted 1 line
So it looks like my code is safe but not so
efficient, since T2 has to
Quoted 1 line
sleep when it doesn't get the semaphore S. Is
there some other
Quoted 1 line
complication I'm missing?
Quoted 8 lines
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
Quoted 9 lines
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Kanoj Sarcar <[email protected]> writes:
...
Quoted 7 lines
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?
Signature · 7 lines
--Ed L Cashin PGP public key: http://noserose.net/e/pgp/ -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 30 lines · --- Ed L Cashin
Kanoj Sarcar <[email protected]> writes:
...
Quoted 2 lines
Its been a while since I wrote up those rules in the "locking" file, but the example that Robert
has
Quoted 5 lines
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 holdkernel_lock
to protect against a bunch of races."The only page stealing code that I can find is in
rmap.candvmscan.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 alock_kernel
call that I could find. Instead, they use trylocks and get the page
table lock before stealing a page.
Quoted 2 lines
Are there other page stealers?
Hi,
When "locking" came into being, vmscan was the only page stealer.
Thanks.
Kanoj
Quoted 12 lines
Signature · 11 lines
--Ed L Cashin PGP public key: http://noserose.net/e/pgp/ -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Kanoj Sarcar <[email protected]> writes:
...
Quoted 2 lines
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.
vm/locking renamed from vm/locking.orig +11 -13
@@ -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
Signature · 8 lines
--Ed L Cashin | PGP public key: [email protected] | http://noserose.net/e/pgp/ -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>