fix swapin race condition

From: Andrea Arcangeli <[email protected]>

The pte_same check is reliable only if the swap entry remains pinned (by the page lock on swapcache). We've also to ensure the swapcache isn't removed before we take the lock as try_to_free_swap won't care about the page pin.

---

@@ -16,6 +16,9 @@
 struct stable_node;
 struct mem_cgroup;
 
+struct page *ksm_does_need_to_copy(struct page *page,
+			struct vm_area_struct *vma, unsigned long address);
+
 #ifdef CONFIG_KSM
 int ksm_madvise(struct vm_area_struct *vma, unsigned long start,
 		unsigned long end, int advice, unsigned long *vm_flags);

@@ -70,19 +73,14 @@ static inline void set_page_stable_node(
  * We'd like to make this conditional on vma->vm_flags & VM_MERGEABLE,
  * but what if the vma was unmerged while the page was swapped out?
  */
-struct page *ksm_does_need_to_copy(struct page *page,
-			struct vm_area_struct *vma, unsigned long address);
-static inline struct page *ksm_might_need_to_copy(struct page *page,
+static inline int ksm_might_need_to_copy(struct page *page,
 			struct vm_area_struct *vma, unsigned long address)
 {
 	struct anon_vma *anon_vma = page_anon_vma(page);
 
-	if (!anon_vma ||
-	    (anon_vma->root == vma->anon_vma->root &&
-	     page->index == linear_page_index(vma, address)))
-		return page;
-
-	return ksm_does_need_to_copy(page, vma, address);
+	return anon_vma &&
+		(anon_vma->root != vma->anon_vma->root ||
+		 page->index != linear_page_index(vma, address));
 }
 
 int page_referenced_ksm(struct page *page,

@@ -115,10 +113,10 @@ static inline int ksm_madvise(struct vm_
 	return 0;
 }
 
-static inline struct page *ksm_might_need_to_copy(struct page *page,
+static inline int ksm_might_need_to_copy(struct page *page,
 			struct vm_area_struct *vma, unsigned long address)
 {
-	return page;
+	return 0;
 }
 
 static inline int page_referenced_ksm(struct page *page,

@@ -1518,8 +1518,6 @@ struct page *ksm_does_need_to_copy(struc
 {
 	struct page *new_page;
 
-	unlock_page(page);	/* any racers will COW it, not modify it */
-
 	new_page = alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, address);
 	if (new_page) {
 		copy_user_highpage(new_page, page, address, vma);

@@ -1535,7 +1533,6 @@ struct page *ksm_does_need_to_copy(struc
 			add_page_to_unevictable_list(new_page);
 	}
 
-	page_cache_release(page);
 	return new_page;
 }
 

@@ -2616,7 +2616,7 @@ static int do_swap_page(struct mm_struct
 		unsigned int flags, pte_t orig_pte)
 {
 	spinlock_t *ptl;
-	struct page *page;
+	struct page *page, *swapcache = NULL;
 	swp_entry_t entry;
 	pte_t pte;
 	struct mem_cgroup *ptr = NULL;

@@ -2671,10 +2671,23 @@ static int do_swap_page(struct mm_struct
 	lock_page(page);
 	delayacct_clear_flag(DELAYACCT_PF_SWAPIN);
 
-	page = ksm_might_need_to_copy(page, vma, address);
-	if (!page) {
-		ret = VM_FAULT_OOM;
-		goto out;
+	/*
+	 * Make sure try_to_free_swap didn't release the swapcache
+	 * from under us. The page pin isn't enough to prevent that.
+	 */
+	if (unlikely(!PageSwapCache(page)))
+		goto out_page;
+
+	if (ksm_might_need_to_copy(page, vma, address)) {
+		swapcache = page;
+		page = ksm_does_need_to_copy(page, vma, address);
+
+		if (unlikely(!page)) {
+			ret = VM_FAULT_OOM;
+			page = swapcache;
+			swapcache = NULL;
+			goto out_page;
+		}
 	}
 
 	if (mem_cgroup_try_charge_swapin(mm, page, GFP_KERNEL, &ptr)) {

@@ -2725,6 +2738,18 @@ static int do_swap_page(struct mm_struct
 	if (vm_swap_full() || (vma->vm_flags & VM_LOCKED) || PageMlocked(page))
 		try_to_free_swap(page);
 	unlock_page(page);
+	if (swapcache) {
+		/*
+		 * Hold the lock to avoid the swap entry to be reused
+		 * until we take the PT lock for the pte_same() check
+		 * (to avoid false positives from pte_same). For
+		 * further safety release the lock after the swap_free
+		 * so that the swap count won't change under a
+		 * parallel locked swapcache.
+		 */
+		unlock_page(swapcache);
+		page_cache_release(swapcache);
+	}
 
 	if (flags & FAULT_FLAG_WRITE) {
 		ret |= do_wp_page(mm, vma, address, page_table, pmd, ptl, pte);

@@ -2746,6 +2771,10 @@ out_page:
 	unlock_page(page);
 out_release:
 	page_cache_release(page);
+	if (swapcache) {
+		unlock_page(swapcache);
+		page_cache_release(swapcache);
+	}
 	return ret;
 }
 

--
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>

What were the end-user-observeable effects of this bug?

Do we think the fix should be backported into earlier kernels?

Thanks.

--
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>

Andrew, one of the possible impacts of this patch is that a KSM-shared page can point to the anon_vma of another process, which could exit before the page is freed.

This can leave a page with a pointer to a recycled anon_vma object, or worse, a pointer to something that is no longer an anon_vma.

Backporting this patch to -stable is worthwhile, IMHO.

All rights reversed

--
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>

I found it by code review only.

Considering I didn't see user-observable effects it's up to you.

--
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>

Yes, it's a great little find, and long predates the KSM hooks you've had to adjust. It does upset me (aesthetically) that the KSM case now intrudes into do_swap_swap() much more than it used to; but I have not come up with a better solution, so yes, let's go forward with this.

Thanks,
Hugh

--
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>

I had an afterthought, something I've not thought through fully, but am reminded of by Greg's mail for stable: is your patch incomplete? Just as it's very unlikely but conceivable the pte_same() test is inadequate, isn't the PageSwapCache() test you've added to do_swap_page() inadequate? Doesn't it need a "page_private(page) == entry.val" test too?

Just as it's conceivable that the same swap has got reused (either via try_to_free_swap or via swapoff+swapon) for a COWed version of the page in that pte slot meanwhile, isn't it conceivable that the page we hold while waiting for pagelock, has got freed from swap then reallocated to elsewhere on swap meanwhile? Which, together with your scenario (and I suspect the two unlikelihoods are not actually to be multiplied), would still lead to the wrong result, unless we add the further test.

I apologize if I'm holding up your stable fix, and just vying against you in a "world's most unlikely VM race" competition, but I don't at present see what prevents this variant.

Hugh

--
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>

Yes, before the fix, the page could be removed from swapcache despite being pinned, and the cow copy could reuse the same swap entry and be unmapped again so breaking the pte_same check.

For this to happen the page would need to be removed from swapcache and then added back to swapcache to a different swap entry. But if that happens the "page_table" pointer would be set to a different swap entry too, so failing the pte_same check. If the swap entry of the page changes the page_table will change with it, so the pte_same check will fail in the first place, so at first glance it looks like checking the page_private isn't necessary and the pte_same check on the page_table is enough.

--
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>

I agree that if my scenario happened on its own, the pte_same check would catch it. But if my scenario happens along with your scenario (and I'm thinking that the combination is not that much less likely than either alone), then the PageSwapCache test will succeed and the pte_same test will succeed, but we're still putting the wrong page into the pte, since this page is now represented by a different swap entry (and the page that should be there by our original swap entry).

Hugh

--
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>

Hi Hugh,

If I understood well you're saying that it is possible that this BUG_ON triggers:

   page_table = pte_offset_map_lock(mm, pmd, address, &ptl);
   BUG_ON(page_private(page) != entry.val && pte_same(page_table, orig_pte));
   if (unlikely(!pte_same(*page_table, orig_pte)))

I still don't get it (that doesn't make me right though).

I'll try to rephrase my argument: if the page was swapped in from swapcache by swapoff and then swapon runs again and the page is added to swapcache to a different swap entry, in between the lookup_swap_cache and the lock_page, the pte_same(*page_table, orig_pte) in pte_same should always fail in the first place (so without requiring the page_private(page) != entry.val check).

If the page is found mapped during pte_same the pte_same check will fail (pte_present first of all). If the page got unmapped and page_private(page) != entry.val, the "entry" == "orig_pte" will be different to what we read in *page_table at the above BUG_ON line (the page has to be unmapped before pte_same check can succeed, but if gets unmapped the new swap entry will be written in the page_table and it won't risk to succeed the pte_same check).

If the page wasn't mapped when it was removed from swapcache, it can't be added to swapcache at all because it was pinned: because only free pages (during swapin) or mapped pages (during swapout) can be added to swapcache.

If I'm missing something a trace of the exact scenario would help to clarify your point.

Thanks!
Andrea

--
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>

Also supposing I'm right, I wouldn't mind if you add a VM_BUG_ON(page_private(page) != entry.val) in the "pte_same == true" path, just to be sure the invariant page_private(page) == pte_to_swp_entry(*page_table) doesn't ever break in a unnoticed way in the future (I think it's unlikely to ever break but a VM_BUG_ON is zero cost in production and it'll clarify the invariant). If instead I'm wrong then just ahead fix it and I'll ack :).

--
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>

Yes, I believe so.

Usually yes, but more may have happened in between.

Usually yes, but not necessarily.

Yes, I think that happens to be the case, but does not rule out my scenario. Perhaps there's a page_count test that I've overlooked that makes my scenario impossible, but is_page_cache_freeable() appears to prevent writeout without affecting swap allocation.

Indeed yes: I was being lazy, hoping to get you to do my thinking for me (in my defence, and in your praise, I have to say that that is usually much the quickest strategy :-) Thank you for the time you've spent on it, when I should have tried harder.

Here's what I think can happen: you may shame me by shooting it down immediately, but go ahead!

I've cast it in terms of reuse_swap_page(), but I expect it could be reformulated to rely on try_to_free_swap() instead, or swapoff+swapon.

A, in do_swap_page(): does page1 = lookup_swap_cache(swap1) and comes through the lock_page(page1).

B, a racing thread of same process, also faults into do_swap_page():
does page1 = lookup_swap_cache(swap1) and now waits in lock_page(page1), but for whatever reason is unlucky not to get the lock any time soon.

A carries on through do_swap_page(), a write fault, but cannot reuse the swap page1 (another reference to swap1). Unlocks the page1 (but B doesn't get it yet), does COW in do_wp_page(), page2 now in that pte.

C, perhaps the parent of A+B, comes in and write faults the same swap page1 into its mm, reuse_swap_page() succeeds this time, swap1 is freed.

kswapd comes in after some time (B still unlucky) and swaps out some pages from A+B and C: it allocates the original swap1 to page2 in A+B, and some other swap2 to the original page1 now in C. But does not immediately free page1 (actually it couldn't: B holds a reference), leaving it in swap cache for now.

B at last gets the lock on page1, hooray! Is PageSwapCache(page1)? Yes. Is pte_same(*page_table, orig_pte)? Yes, because page2 has now been given the swap1 which page1 used to have. So B proceeds to insert page1 into A+B's page_table, though its content now belongs to C, quite different from what A wrote there.

B ought to have checked that page1's swap was still swap1.

Hugh

--
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>

Can't shoot it. This definitely helped. My previous scenario only involved threads, so I was only thinking at threads...

It's actually better to formulate in reuse_swap_page terms as it doesn't require swapoff to trigger.

The key is C mm is different from the A/B mm. If C was sharing the same mm (as in the scenario I was thinking of with threads) reuse_swap_cache couldn't run in C because the pte_same check would fail.

I suggest adding the explanation to the patch comment.

Thanks!
Andrea

--
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>

Thanks a lot for going through it.

Absolutely: patch to Linus follows.

Hugh

--
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>

Commit 4969c1192d15afa3389e7ae3302096ff684ba655 "mm: fix swapin race condition" is now agreed to be incomplete. There's a race, not very much less likely than the original race envisaged, in which it is further necessary to check that the swapcache page's swap has not changed.

Here's the reasoning: cast in terms of reuse_swap_page(), but probably could be reformulated to rely on try_to_free_swap() instead, or on swapoff+swapon.

A, faults into do_swap_page(): does page1 = lookup_swap_cache(swap1) and comes through the lock_page(page1).

B, a racing thread of the same process, faults on the same address:
does page1 = lookup_swap_cache(swap1) and now waits in lock_page(page1), but for whatever reason is unlucky not to get the lock any time soon.

A carries on through do_swap_page(), a write fault, but cannot reuse the swap page1 (another reference to swap1). Unlocks the page1 (but B doesn't get it yet), does COW in do_wp_page(), page2 now in that pte.

C, perhaps the parent of A+B, comes in and write faults the same swap page1 into its mm, reuse_swap_page() succeeds this time, swap1 is freed.

kswapd comes in after some time (B still unlucky) and swaps out some pages from A+B and C: it allocates the original swap1 to page2 in A+B, and some other swap2 to the original page1 now in C. But does not immediately free page1 (actually it couldn't: B holds a reference), leaving it in swap cache for now.

B at last gets the lock on page1, hooray! Is PageSwapCache(page1)? Yes. Is pte_same(*page_table, orig_pte)? Yes, because page2 has now been given the swap1 which page1 used to have. So B proceeds to insert page1 into A+B's page_table, though its content now belongs to C, quite different from what A wrote there.

B ought to have checked that page1's swap was still swap1.

---

 mm/memory.c |    8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

@@ -2680,10 +2680,12 @@ static int do_swap_page(struct mm_struct
 	delayacct_clear_flag(DELAYACCT_PF_SWAPIN);
 
 	/*
-	 * Make sure try_to_free_swap didn't release the swapcache
-	 * from under us. The page pin isn't enough to prevent that.
+	 * Make sure try_to_free_swap or reuse_swap_page or swapoff did not
+	 * release the swapcache from under us.  The page pin, and pte_same
+	 * test below, are not enough to exclude that.  Even if it is still
+	 * swapcache, we need to check that the page's swap has not changed.
 	 */
-	if (unlikely(!PageSwapCache(page)))
+	if (unlikely(!PageSwapCache(page) || page_private(page) != entry.val))
 		goto out_page;
 
 	if (ksm_might_need_to_copy(page, vma, address)) {