[PATCH] anon_vma list locking bug

[PATCH] anon_vma list locking bug

[Hugh Dickins]

Vladimir Saveliev reported anon_vma_unlink list_del BUG (LKML 24 June).
His testing is still in progress, but we believe it comes from a nasty
locking deficiency I introduced in 2.6.7's anon_vma_prepare.

Andrea's original anon_vma_prepare was fine, it needed no anon_vma lock
because it was always linking a freshly allocated structure; but my
find_mergeable enhancement let it adopt a neighbouring anon_vma, which
of course needs locking against a racing linkage from another mm -
which the earlier adjust_vma fix seems to have made more likely.

Does anon_vma->lock nest inside or outside page_table_lock?  Inside, but
that's not obvious without a lock ordering list: instead of listing the
order here, update the list in filemap.c; but a separate patch because
that's less urgent and more likely to get wrong or provoke controversy.

(Could do it with anon_vma lock after dropping page_table_lock, but
a long comment explaining why some code is safe suggests it's not.)

Signed-off-by: Hugh Dickins <hugh@veritas.com>

--- 2.6.7/mm/rmap.c	2004-06-16 06:21:02.000000000 +0100
+++ linux/mm/rmap.c	2004-06-25 22:15:41.164841904 +0100
@@ -18,14 +18,11 @@
  */
 
 /*
- * Locking:
- * - the page->mapcount field is protected by the PG_maplock bit,
- *   which nests within the mm->page_table_lock,
- *   which nests within the page lock.
- * - because swapout locking is opposite to the locking order
- *   in the page fault path, the swapout path uses trylocks
- *   on the mm->page_table_lock
+ * Locking: see "Lock ordering" summary in filemap.c.
+ * In swapout, page_map_lock is held on entry to page_referenced and
+ * try_to_unmap, so they trylock for i_mmap_lock and page_table_lock.
  */
+
 #include <linux/mm.h>
 #include <linux/pagemap.h>
 #include <linux/swap.h>
@@ -79,8 +76,12 @@ int anon_vma_prepare(struct vm_area_stru
 		/* page_table_lock to protect against threads */
 		spin_lock(&mm->page_table_lock);
 		if (likely(!vma->anon_vma)) {
+			if (!allocated)
+				spin_lock(&anon_vma->lock);
 			vma->anon_vma = anon_vma;
 			list_add(&vma->anon_vma_node, &anon_vma->head);
+			if (!allocated)
+				spin_unlock(&anon_vma->lock);
 			allocated = NULL;
 		}
 		spin_unlock(&mm->page_table_lock);

[PATCH] mm lock ordering summary

[Hugh Dickins]

Update Lock ordering summary in filemap.c, mainly to place page_map_lock
and anon_vma->lock: more helpful to list them here than over in rmap.c.

I couldn't quite understand the earlier groupings, which rather obscure
the ordering: tried to bring them all into one sequence, but i_sem
versus read-write mmap_sem seemed to need spelling out.

Sorry, left out proc_lock and dcache_lock: they just don't belong here.

Signed-off-by: Hugh Dickins <hugh@veritas.com>

--- 2.6.7/mm/filemap.c	2004-06-16 06:20:39.000000000 +0100
+++ linux/mm/filemap.c	2004-06-25 22:19:41.669279672 +0100
@@ -55,41 +55,29 @@
 /*
  * Lock ordering:
  *
- *  ->i_mmap_lock		(vmtruncate)
- *    ->private_lock		(__free_pte->__set_page_dirty_buffers)
- *      ->swap_list_lock
- *        ->swap_device_lock	(exclusive_swap_page, others)
- *          ->mapping->tree_lock
- *
- *  ->i_sem
- *    ->i_mmap_lock		(truncate->unmap_mapping_range)
- *
- *  ->mmap_sem
- *    ->i_mmap_lock
- *      ->page_table_lock	(various places, mainly in mmap.c)
- *        ->mapping->tree_lock	(arch-dependent flush_dcache_mmap_lock)
- *
- *  ->mmap_sem
- *    ->lock_page		(access_process_vm)
- *
- *  ->mmap_sem
- *    ->i_sem			(msync)
- *
- *  ->i_sem
- *    ->i_alloc_sem             (various)
- *
- *  ->inode_lock
- *    ->sb_lock			(fs/fs-writeback.c)
- *    ->mapping->tree_lock	(__sync_single_inode)
- *
- *  ->page_table_lock
- *    ->swap_device_lock	(try_to_unmap_one)
- *    ->private_lock		(try_to_unmap_one)
- *    ->tree_lock		(try_to_unmap_one)
- *    ->zone.lru_lock		(follow_page->mark_page_accessed)
+ * inode->i_sem
+ *   inode->i_alloc_sem
  *
- *  ->task->proc_lock
- *    ->dcache_lock		(proc_pid_lookup)
+ * When a page fault occurs in writing from user to file, down_read
+ * of mmap_sem nests within i_sem; in sys_msync, i_sem nests within
+ * down_read of mmap_sem; i_sem and down_write of mmap_sem are never
+ * taken together; in truncation, i_sem is taken outermost.
+ *
+ * mm->mmap_sem
+ *   page->flags PG_locked (lock_page)
+ *     mapping->i_mmap_lock
+ *       mm->page_table_lock
+ *         swap_list_lock (in swap_free etc's swap_info_get)
+ *         zone->lru_lock (in mark_page_accessed)
+ *         page->flags PG_maplock (page_map_lock)
+ *           anon_vma->lock
+ *             swap_device_lock (in swap_duplicate, swap_info_get)
+ *             mapping->private_lock (in __set_page_dirty_buffers)
+ *             inode_lock (in set_page_dirty's __mark_inode_dirty)
+ *               sb_lock (within inode_lock in fs/fs-writeback.c)
+ *               mapping->tree_lock (widely used, in set_page_dirty,
+ *                         in arch-dependent flush_dcache_mmap_lock,
+ *                         within inode_lock in __sync_single_inode)
  */
 
 /*

Re: [PATCH] mm lock ordering summary

[Andrew Morton]

Hugh Dickins <hugh@veritas.com> wrote:
>
> + * mm->mmap_sem
> + *   page->flags PG_locked (lock_page)
> + *     mapping->i_mmap_lock
> + *       mm->page_table_lock
> + *         swap_list_lock (in swap_free etc's swap_info_get)
> + *         zone->lru_lock (in mark_page_accessed)
> + *         page->flags PG_maplock (page_map_lock)
> + *           anon_vma->lock
> + *             swap_device_lock (in swap_duplicate, swap_info_get)
> + *             mapping->private_lock (in __set_page_dirty_buffers)
> + *             inode_lock (in set_page_dirty's __mark_inode_dirty)
> + *               sb_lock (within inode_lock in fs/fs-writeback.c)
> + *               mapping->tree_lock (widely used, in set_page_dirty,
> + *                         in arch-dependent flush_dcache_mmap_lock,
> + *                         within inode_lock in __sync_single_inode)

What happened to "i_sem nests inside mmap_sem"?

This representation tends to lose information - it implies that all the
above locks are taken at the same time and it makes it harder to capture
information about where in the kernel the particular ranking occurs.

I mean, if some code does:

	down(a);
	down(b);

and some other code does

	down(a);
	down(c);

the appropriate representation is

	a
	-> b

	a
	-> c

Re: [PATCH] mm lock ordering summary

[Hugh Dickins]

On Fri, 25 Jun 2004, Andrew Morton wrote:
> Hugh Dickins <hugh@veritas.com> wrote:
> >
> > + * mm->mmap_sem
> > + *   page->flags PG_locked (lock_page)
> > + *     mapping->i_mmap_lock
> > + *       mm->page_table_lock
> > + *         swap_list_lock (in swap_free etc's swap_info_get)
> > + *         zone->lru_lock (in mark_page_accessed)
> > + *         page->flags PG_maplock (page_map_lock)
> > + *           anon_vma->lock
> > + *             swap_device_lock (in swap_duplicate, swap_info_get)
> > + *             mapping->private_lock (in __set_page_dirty_buffers)
> > + *             inode_lock (in set_page_dirty's __mark_inode_dirty)
> > + *               sb_lock (within inode_lock in fs/fs-writeback.c)
> > + *               mapping->tree_lock (widely used, in set_page_dirty,
> > + *                         in arch-dependent flush_dcache_mmap_lock,
> > + *                         within inode_lock in __sync_single_inode)
> 
> What happened to "i_sem nests inside mmap_sem"?

Well, you tell me, you're the one who's cut it out of what I sent ;)
And it's not as simple as that, either: mmap_sem nests inside i_sem
when faulting, doesn't it?  At first I thought that msync must be
wrong, then realized that down_reads cannot be placed strictly (?).

+ * inode->i_sem
+ *   inode->i_alloc_sem
...
+ * When a page fault occurs in writing from user to file, down_read
+ * of mmap_sem nests within i_sem; in sys_msync, i_sem nests within
+ * down_read of mmap_sem; i_sem and down_write of mmap_sem are never
+ * taken together; in truncation, i_sem is taken outermost.

is what I ended up writing.

> This representation tends to lose information -

I'm inclined to think it loses data, but gives information more easily.

If you want to check your lock ordering (the usual use for this summary),
you have to check through a number of separate blocks in the old format.

The rule I needed to see, that anon_vma->lock nests within page_table_lock,
came from anon_vma->lock within page_map_lock in swapout, and from
page_map_lock within page_table_lock when faulting; and now there's also
anon_vma->lock within page_table_lock in anon_vma_prepare.  But this is
detail which the interested should establish for themselves, I don't
see why the summary need specify it in an arbitrary subset of cases.

And when adding page_map_lock and anon_vma->lock, I just couldn't work
out how to do them in the old layout.  But yes, I made this a separate
patch from the bug fix that begged it, because I realized that you or
others might have other preferences.  Please add page_map_lock and
anon_vma->lock in the fashion that you understand.

> it implies that all the above locks are taken at the same time

I hope not!

> and it makes it harder to capture
> information about where in the kernel the particular ranking occurs.

This is a summary.  In general there are multiple places where the
ranking is enforced, but in odd corners (mainly set_page_dirty) it is
worth clarifying where something comes in, and I've kept such comments.

> I mean, if some code does:
> 
> 	down(a);
> 	down(b);
> 
> and some other code does
> 
> 	down(a);
> 	down(c);
> 
> the appropriate representation is
> 
> 	a
> 	-> b
> 
> 	a
> 	-> c

Well, I've expressed that as
        a
          b
          c

Certainly in principle there are cases where it's just wrong to
represent by a single sequence (and the i_sem/mmap_sem relation
seems to be a fairly simple example of that); but I find a lock
ordering easier to follow than a set of lock orderings.  We differ.

Hugh

Re: [PATCH] mm lock ordering summary

[Andrew Morton]

Hugh Dickins <hugh@veritas.com> wrote:
>
> On Fri, 25 Jun 2004, Andrew Morton wrote:
> > Hugh Dickins <hugh@veritas.com> wrote:
> > >
> > > + * mm->mmap_sem
> > > + *   page->flags PG_locked (lock_page)
> > > + *     mapping->i_mmap_lock
> > > + *       mm->page_table_lock
> > > + *         swap_list_lock (in swap_free etc's swap_info_get)
> > > + *         zone->lru_lock (in mark_page_accessed)
> > > + *         page->flags PG_maplock (page_map_lock)
> > > + *           anon_vma->lock
> > > + *             swap_device_lock (in swap_duplicate, swap_info_get)
> > > + *             mapping->private_lock (in __set_page_dirty_buffers)
> > > + *             inode_lock (in set_page_dirty's __mark_inode_dirty)
> > > + *               sb_lock (within inode_lock in fs/fs-writeback.c)
> > > + *               mapping->tree_lock (widely used, in set_page_dirty,
> > > + *                         in arch-dependent flush_dcache_mmap_lock,
> > > + *                         within inode_lock in __sync_single_inode)
> > 
> ...
> > the appropriate representation is
> > 
> > 	a
> > 	-> b
> > 
> > 	a
> > 	-> c
> 
> Well, I've expressed that as
>         a
>           b
>           c
> 

Yes, but what does

	a
	b
	  c
	  d

mean?

The above graph tells us that one or more of (swap_device_lock,
mapping->private_lock and inode_lock) nests inside one or more of
(swap_list_lock, zone->lru_lock and page->flags PG_maplock).

And has no way of telling us _where_, say, swap_device_lock nests inside
zone->lru_lock.

And it alleges that tree_lock nests inside lru_lock, which isn't so.  Is
it?  These guys used to have no locking relationship.  Hopefully that's
still the case.  But how to represent that?

Re: [PATCH] mm lock ordering summary

[Hugh Dickins]

On Fri, 25 Jun 2004, Andrew Morton wrote:
> 
> Yes, but what does
> 
> 	a
> 	b
> 	  c
> 	  d
> 
> mean?
> 
> The above graph tells us that one or more of (swap_device_lock,
> mapping->private_lock and inode_lock) nests inside one or more of
> (swap_list_lock, zone->lru_lock and page->flags PG_maplock).

Yes.  I think I ordered it so that it meant c and d nest inside b,
and a's a leaf of less interest; but of course it's just good luck
if any such ordering is possible.

> And has no way of telling us _where_, say, swap_device_lock nests inside
> zone->lru_lock.

Hence the comments, or search the source: this is only a summary.

> And it alleges that tree_lock nests inside lru_lock, which isn't so.  Is
> it?  These guys used to have no locking relationship.  Hopefully that's
> still the case.  But how to represent that?

It's alleging that you'll be okay if you write code with tree_lock
nesting inside lru_lock, and you need to worry if you do the reverse.

How is this summary used?  I use it to check whether I've got my locks
in the right order.  Look at the summary and if what I've written fits
with the sequence shown, I'm okay.  If not, I need to enquire further:
think about changing around my new code to fit the ordering shown; if
that's difficult then look through the source to find where those rules
come from, think about changing them around; or, complicate (refine?)
the summary to show that actually my new case is not a problem after all.

I'm suggesting it be a checklist, rather than a declaration of truth:
easier to maintain the checklist.  But I doubt I'm persuading you:
please add page_map_lock and anon_vma->lock (but where and how many?).

Hugh

Re: [PATCH] mm lock ordering summary

[Andrew Morton]

Hugh Dickins <hugh@veritas.com> wrote:
>
>  please add page_map_lock and anon_vma->lock (but where and how many?).

Like this?

There seem to be a few missing bits.



--- 25/mm/filemap.c~lock-ordering-update	2004-06-25 18:37:32.565669464 -0700
+++ 25-akpm/mm/filemap.c	2004-06-25 18:37:32.570668704 -0700
@@ -55,16 +55,17 @@
 /*
  * Lock ordering:
  *
  *  ->i_mmap_lock		(vmtruncate)
  *    ->private_lock		(__free_pte->__set_page_dirty_buffers)
  *      ->swap_list_lock
  *        ->swap_device_lock	(exclusive_swap_page, others)
  *          ->mapping->tree_lock
+ *    ->page_map_lock()		(try_to_unmap_file)
  *
  *  ->i_sem
  *    ->i_mmap_lock		(truncate->unmap_mapping_range)
  *
  *  ->mmap_sem
  *    ->i_mmap_lock
  *      ->page_table_lock	(various places, mainly in mmap.c)
  *        ->mapping->tree_lock	(arch-dependent flush_dcache_mmap_lock)
@@ -82,16 +83,20 @@
  *    ->sb_lock			(fs/fs-writeback.c)
  *    ->mapping->tree_lock	(__sync_single_inode)
  *
  *  ->page_table_lock
  *    ->swap_device_lock	(try_to_unmap_one)
  *    ->private_lock		(try_to_unmap_one)
  *    ->tree_lock		(try_to_unmap_one)
  *    ->zone.lru_lock		(follow_page->mark_page_accessed)
+ *    ->page_map_lock()		(page_add_anon_rmap)
+ *    ->anon_vma.lock		(anon_vma_prepare)
+ *    ->inode_lock		(zap_pte_range->set_page_dirty)
+ *    ->private_lock		(zap_pte_range->__set_page_dirty_buffers)
  *
  *  ->task->proc_lock
  *    ->dcache_lock		(proc_pid_lookup)
  */
 
 /*
  * Remove a page from the page cache and free it. Caller has to make
  * sure the page is locked and that nobody else uses it - or that usage
_