From mboxrd@z Thu Jan 1 00:00:00 1970 Subject: Documentation/vm/locking: why not hold two PT locks? From: Ed L Cashin Date: Sun, 08 Feb 2004 16:18:41 -0500 Message-ID: <8765ehe0cu.fsf@uga.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-linux-mm@kvack.org Return-Path: To: linux-mm@kvack.org List-ID: 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: aart@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Subject: Re: Documentation/vm/locking: why not hold two PT locks? From: Robert Love In-Reply-To: <8765ehe0cu.fsf@uga.edu> References: <8765ehe0cu.fsf@uga.edu> Content-Type: text/plain Message-Id: <1076275778.5608.1.camel@localhost> Mime-Version: 1.0 Date: Sun, 08 Feb 2004 16:29:38 -0500 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org Return-Path: To: Ed L Cashin Cc: linux-mm@kvack.org List-ID: 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: aart@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Subject: Re: Documentation/vm/locking: why not hold two PT locks? From: Ed L Cashin Date: Sun, 08 Feb 2004 16:47:13 -0500 In-Reply-To: <1076275778.5608.1.camel@localhost> (Robert Love's message of "Sun, 08 Feb 2004 16:29:38 -0500") Message-ID: <87ekt5ckgu.fsf@cs.uga.edu> References: <8765ehe0cu.fsf@uga.edu> <1076275778.5608.1.camel@localhost> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-linux-mm@kvack.org Return-Path: To: Robert Love Cc: linux-mm@kvack.org List-ID: Robert Love 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: aart@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Subject: Re: Documentation/vm/locking: why not hold two PT locks? From: Robert Love In-Reply-To: <87ekt5ckgu.fsf@cs.uga.edu> References: <8765ehe0cu.fsf@uga.edu> <1076275778.5608.1.camel@localhost> <87ekt5ckgu.fsf@cs.uga.edu> Content-Type: text/plain Message-Id: <1076278320.6015.1.camel@localhost> Mime-Version: 1.0 Date: Sun, 08 Feb 2004 17:12:00 -0500 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org Return-Path: To: Ed L Cashin Cc: linux-mm@kvack.org List-ID: 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: aart@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: <20040209074409.32804.qmail@web14306.mail.yahoo.com> Date: Sun, 8 Feb 2004 23:44:09 -0800 (PST) From: Kanoj Sarcar Subject: Re: Documentation/vm/locking: why not hold two PT locks? In-Reply-To: <1076278320.6015.1.camel@localhost> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-linux-mm@kvack.org Return-Path: To: Robert Love , Ed L Cashin Cc: linux-mm@kvack.org List-ID: --- Robert Love 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: > aart@kvack.org __________________________________ 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: aart@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Subject: Re: Documentation/vm/locking: why not hold two PT locks? From: Ed L Cashin Date: Mon, 09 Feb 2004 11:19:09 -0500 In-Reply-To: <20040209074409.32804.qmail@web14306.mail.yahoo.com> (Kanoj Sarcar's message of "Sun, 8 Feb 2004 23:44:09 -0800 (PST)") Message-ID: <87r7x4ns3m.fsf@cs.uga.edu> References: <20040209074409.32804.qmail@web14306.mail.yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-linux-mm@kvack.org Return-Path: To: Kanoj Sarcar Cc: Robert Love , linux-mm@kvack.org List-ID: Kanoj Sarcar 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: aart@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: <20040209182013.59140.qmail@web14302.mail.yahoo.com> Date: Mon, 9 Feb 2004 10:20:13 -0800 (PST) From: Kanoj Sarcar Subject: Re: Documentation/vm/locking: why not hold two PT locks? In-Reply-To: <87r7x4ns3m.fsf@cs.uga.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-linux-mm@kvack.org Return-Path: To: Ed L Cashin Cc: Robert Love , linux-mm@kvack.org List-ID: --- Ed L Cashin wrote: > Kanoj Sarcar 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: > aart@kvack.org __________________________________ 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: aart@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Subject: Re: Documentation/vm/locking: why not hold two PT locks? From: Ed L Cashin Date: Mon, 09 Feb 2004 16:17:34 -0500 In-Reply-To: <20040209182013.59140.qmail@web14302.mail.yahoo.com> (Kanoj Sarcar's message of "Mon, 9 Feb 2004 10:20:13 -0800 (PST)") Message-ID: <871xp49clt.fsf@uga.edu> References: <20040209182013.59140.qmail@web14302.mail.yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-linux-mm@kvack.org Return-Path: To: Kanoj Sarcar Cc: linux-mm@kvack.org List-ID: Kanoj Sarcar 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: aart@kvack.org