page->flags corruption fix

Not all arches have atomic_set_mask() and atomic_clear_mask(). asm-arm
asm-arm26
asm-h8300
asm-i386
asm-m68k
asm-m68knommu
asm-ppc
asm-s390
asm-sh
asm-v850
asm-x86_64

do.

There definitely is when RMAP is present - we've reproduced it repeatedly in our labs.

We've seen a similar failure with the RHEL2.1 kernel w/o RMAP patches too. So we fully believe it's possible in stock 2.4.x.

Thanks,
Matt

Matt Domsch
Sr. Software Engineer, Lead Engineer
Dell Linux Solutions www.dell.com/linux
Linux on Dell mailing lists @ http://lists.us.dell.com

That would be an argument for changing the rmap patch.

A similar failure - but what exactly?
And what is the actual race which would account for it?

I don't mind you and Rik fixing bugs!
I'd just like to understand the bug before it's fixed.

Hugh

1) cpu A adds page P to the swap cache, loading page->flags and modifying it locally

2) a second thread scans a page table entry and sees that the page was accessed, so cpu B moves page P to the active list

3) cpu A undoes the PG_inactive -> PG_active bit change, corrupting the page->flags of P

The -rmap VM doesn't do anything to this bug, except making it easy to trigger due to some side effects.

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Right, the add_to_swap_cache in try_to_swap_out.

Right, the mark_page_accessed in try_to_swap_out (I don't see any other mark_page_accessed as problematic). Or the del_page_from_active_list in refill_inactive.

(Mainline is easier than -rmap since no separate PG_inactive bit.)

Thanks a lot for explaining, I see it now. Personally I'd prefer a lighter weight patch, either pagemap_lru_lock within add_to_swap_cache, or better moving the PG_flags clearing from __add_to_page_cache into __free_pages_ok, where I still believe it can be done non-atomically.

But you've proved your point, and I understand you preferring a more straightforward and future-proof way. I'm not writing an alternative patch, don't let me stand in the way of progress...

A little of the above explanation in the change comment would be nice.

Thanks,
Hugh

Maybe comments on top of the code?

Rik? :)

Here you are:

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher. # This patch includes the following deltas:
# ChangeSet 1.1193 -> 1.1194
# mm/filemap.c 1.89 -> 1.90
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 03/10/08 [email protected] 1.1194

# comment on why the atomic updates are needed, on request
# --------------------------------------------
#
diff -Nru a/mm/filemap.c b/mm/filemap.c
--- a/mm/filemap.c	Wed Oct  8 13:47:12 2003
+++ b/mm/filemap.c	Wed Oct  8 13:47:12 2003
@@ -654,6 +654,12 @@
 	struct address_space *mapping, unsigned long offset,
 	struct page **hash)
 {
+	/*
+	 * Yes this is inefficient, however it is needed.  The problem
+	 * is that we could be adding a page to the swap cache while
+	 * another CPU is also modifying page->flags, so the updates
+	 * really do need to be atomic.  -- Rik
+	 */
 	ClearPageUptodate(page);
 	ClearPageError(page);
 	ClearPageDirty(page);

I believe the more correct fix is to hold the pagemap_lru_lock during __add_to_page_cache. The race exists between pages with PG_lru set (in the lru) that are being added to the pagecache/swapcache. Holding both spinlocks really avoids the race, your patch sounds less obviously safe (since the race still happens but it's more "controlled") and a single spinlock should be more efficient than the flood of atomic bitops anyways. Comments? Hugh?

I also can't see why you care about the page->flags in __free_pages_ok. by that time, if the page is still visible anywhere that's a _real_ huge bug, so that second part really looks wrong and it should be backed out IMHO. For sure at that time the page can't be in any lru list, at least in my tree, see what the correct code is there, this's the only way to handle that case right (the in_interrupt() part is needed only if you've aio like in your tree like in my tree). So your changes in free_pages are definitely superflous in page_alloc.c, and I guess they're not closing all the bugs in your tree too (you need the below too, if you allow anon pages to be freed while in the lru still with asynchronous io).

The first part of your patch I agree fixes the race, but I'd prefer just taking one more spinlock to avoid the race at all, instead of trying to control it with a flood of bitops.

static void __free_pages_ok (struct page *page, unsigned int order)

{
	unsigned long index, page_idx, mask, flags;
	free_area_t *area;
	struct page *base;
	zone_t *zone;
#ifdef CONFIG_SMP
	per_cpu_pages_t *per_cpu_pages;

#endif

	/*
	 * Yes, think what happens when other parts of the kernel take 
	 * a reference to a page in order to pin it for io. -ben
	 */
	if (PageLRU(page)) {
		if (unlikely(in_interrupt())) {
			unsigned long flags;

			spin_lock_irqsave(&free_pages_ok_no_irq_lock, flags);

			page->next_hash = free_pages_ok_no_irq_head;
			free_pages_ok_no_irq_head = page;
			page->index = order;

			spin_unlock_irqrestore(&free_pages_ok_no_irq_lock, flags);

			schedule_task(&free_pages_ok_no_irq_task);
			return;
		}
		lru_cache_del(page);
	}

[..]

Andrea - If you prefer relying on open source software, check these links:

	    rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.[45]/
	    http://www.cobite.com/cvsps/

basically the race could only happen by running __add_to_page_cache on a page that was in the lru already. So it could happen with anon pages and shm too, never with plain pagecache. It's all about the PG_lru and PG_active bitflag. Both of them can only be changed inside the pagemap_lru_lock. So taking the pagemap_lru_lock will avoid the race. Can anybody see any race with this patch applied on top of 2.4.23pre7?

	http://www.us.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.23pre7/anon-lru-race-better-fix-1

I believe this is cleaner and faster than the flood of bitops, since it's 2 atomic instructions only and it only happens in the paths where the race had a chance to trigger, so all the critical pagecache paths aren't affected at all anymore by the slowdown.

For the page_alloc.c changes, they must not make a difference so I backed them out.

Comments welcome, thanks.

side note: this won't break any architectural code.

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/include/linux/mm.h race/include/linux/mm.h
@@ -322,11 +322,9 @@ typedef struct page {
 #define TryLockPage(page)	test_and_set_bit(PG_locked, &(page)->flags)
 #define PageChecked(page)	test_bit(PG_checked, &(page)->flags)
 #define SetPageChecked(page)	set_bit(PG_checked, &(page)->flags)
-#define ClearPageChecked(page)	clear_bit(PG_checked, &(page)->flags)
 #define PageLaunder(page)	test_bit(PG_launder, &(page)->flags)
 #define SetPageLaunder(page)	set_bit(PG_launder, &(page)->flags)
 #define ClearPageLaunder(page)	clear_bit(PG_launder, &(page)->flags)
-#define ClearPageArch1(page)	clear_bit(PG_arch_1, &(page)->flags)
 
 /*
  * The zone field is never updated after free_area_init_core()

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/mm/filemap.c race/mm/filemap.c
@@ -656,19 +656,10 @@ static inline void __add_to_page_cache(s
 	struct address_space *mapping, unsigned long offset,
 	struct page **hash)
 {
-	/*
-	 * Yes this is inefficient, however it is needed.  The problem
-	 * is that we could be adding a page to the swap cache while
-	 * another CPU is also modifying page->flags, so the updates
-	 * really do need to be atomic.  -- Rik
-	 */
-	ClearPageUptodate(page);
-	ClearPageError(page);
-	ClearPageDirty(page);
-	ClearPageReferenced(page);
-	ClearPageArch1(page);
-	ClearPageChecked(page);
-	LockPage(page);
+	unsigned long flags;
+
+	flags = page->flags & ~(1 << PG_uptodate | 1 << PG_error | 1 << PG_dirty | 1 << PG_referenced | 1 << PG_arch_1 | 1 << PG_checked);
+	page->flags = flags | (1 << PG_locked);
 	page_cache_get(page);
 	page->index = offset;
 	add_page_to_inode_queue(mapping, page);

@@ -690,6 +681,7 @@ int add_to_page_cache_unique(struct page
 	int err;
 	struct page *alias;
 
+	spin_lock(&pagemap_lru_lock);
 	spin_lock(&pagecache_lock);
 	alias = __find_page_nolock(mapping, offset, *hash);
 

@@ -700,6 +692,7 @@ int add_to_page_cache_unique(struct page
 	}
 
 	spin_unlock(&pagecache_lock);
+	spin_unlock(&pagemap_lru_lock);
 	if (!err)
 		lru_cache_add(page);
 	return err;

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/mm/page_alloc.c race/mm/page_alloc.c
@@ -109,8 +109,7 @@ static void __free_pages_ok (struct page
 		BUG();
 	if (PageActive(page))
 		BUG();
-	ClearPageReferenced(page);
-	ClearPageDirty(page);
+	page->flags &= ~((1<<PG_referenced) | (1<<PG_dirty));
 
 	if (current->flags & PF_FREE_PAGES)
 		goto local_freelist;

Andrea - If you prefer relying on open source software, check these links:

	    rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.[45]/
	    http://www.cobite.com/cvsps/

I agree. (I imagine some processors might implement that atomic flood quite efficiently, but most not.)

I believe your patch is correct, and prefer it to the atomic flood.

But I thought it almost coincidental that the racy cases happen to use add_to_page_cache_unique rather than add_to_page_cache, and deserved
comment: until I noticed _nothing_ now uses add_to_page_cache, so please just delete it from filemap.c and pagemap.h - it wasn't exported, so no issue with out-of-tree modules (sorry, looks like cleanup I should have done when I updated shmem.c in 2.4.22).

And maybe add __lru_cache_add (inline? FASTCALL?) for the

		if (!TestSetPageLRU(page))
			add_page_to_inactive_list(page);

so you don't have to drop pagemap_lru_lock before lru_cache_add.

I agree on that too: I think Rik did it for atomicity throughout, to make the safety obvious; but in practice it was already safe.

However, I'm still not satisfied by your patch. The patch which will satisfy me is to remove all that bit clearing from __add_to_page_cache, leaving just a LockPage, doing the clearing in one go in __free_pages_ok. In most cases, a page cannot be added to page cache more than once before it's freed, so in those cases it doesn't matter which stage we clear them.

The exceptions are normal swap (being deleted from swap cache under pressure then readded later) and tmpfs: but __add_to_page_cache's clearing does not help those cases, they compensate for it as much as benefit. PG_arch_1 needs more checking than I've time for now (though I think it'll turn out okay), and probably -pre8 is the wrong point for a change of this kind.

Hugh

Hi Hugh,

correct, nothing uses it. I also found it in the process and yes it's not exported.

agreed. I didn't touch it because it was not related to this bug, likely gcc drops it during linking anyways. But I can clean it up of course.

I thought about it too, I just didn't think it was a big issue, if we already took the lock, it'll be still in l1 cache since the unlock and relock are immediate (and even in cpus using load locked store conditional for all atomic ops, 1 single additional additional spinlock didn't sound like a painful thing). But I can optimize this bit agreed (this is especially useful in my tree with the vm_anon_lru sysctl set to 0 by default).

Agreed.

;) Well, this goes well beyond the scope of this race condition, I agree but I didn't consider merging those changes in the same patch ;)

yes, I think pre8 isn't the best point, and this change has nothing to do with the race condition in question anyways.

So I would suggest to cook a patch for this orthogonal optimization during 2.4.24pre.

So this is a new patch addressing the removal of add_to_page_cache, and the microoptimization to avoid a suprious unlock/relock cycle and I added some commentary.

	http://www.us.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.23pre7/anon-lru-race-better-fix-2

I would be very interested if Dell could test this (so far untested ;) patch, to be sure this really fixes all the troubles they've experienced in practice.

Thanks,

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/include/linux/mm.h race/include/linux/mm.h
@@ -322,11 +322,9 @@ typedef struct page {
 #define TryLockPage(page)	test_and_set_bit(PG_locked, &(page)->flags)
 #define PageChecked(page)	test_bit(PG_checked, &(page)->flags)
 #define SetPageChecked(page)	set_bit(PG_checked, &(page)->flags)
-#define ClearPageChecked(page)	clear_bit(PG_checked, &(page)->flags)
 #define PageLaunder(page)	test_bit(PG_launder, &(page)->flags)
 #define SetPageLaunder(page)	set_bit(PG_launder, &(page)->flags)
 #define ClearPageLaunder(page)	clear_bit(PG_launder, &(page)->flags)
-#define ClearPageArch1(page)	clear_bit(PG_arch_1, &(page)->flags)
 
 /*
  * The zone field is never updated after free_area_init_core()

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/include/linux/pagemap.h race/include/linux/pagemap.h
@@ -85,7 +85,6 @@ extern void FASTCALL(unlock_page(struct 
 	__find_lock_page(mapping, index, page_hash(mapping, index))
 extern struct page *find_trylock_page(struct address_space *, unsigned long);
 
-extern void add_to_page_cache(struct page * page, struct address_space *mapping, unsigned long index);
 extern void add_to_page_cache_locked(struct page * page, struct address_space *mapping, unsigned long index);
 extern int add_to_page_cache_unique(struct page * page, struct address_space *mapping, unsigned long index, struct page **hash);
 

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/include/linux/swap.h race/include/linux/swap.h
@@ -103,6 +103,7 @@ struct sysinfo;
 struct zone_t;
 
 /* linux/mm/swap.c */
+extern void FASTCALL(__lru_cache_add(struct page *));
 extern void FASTCALL(lru_cache_add(struct page *));
 extern void FASTCALL(__lru_cache_del(struct page *));
 extern void FASTCALL(lru_cache_del(struct page *));

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/mm/page_alloc.c race/mm/page_alloc.c
@@ -109,8 +109,7 @@ static void __free_pages_ok (struct page
 		BUG();
 	if (PageActive(page))
 		BUG();
-	ClearPageReferenced(page);
-	ClearPageDirty(page);
+	page->flags &= ~((1<<PG_referenced) | (1<<PG_dirty));
 
 	if (current->flags & PF_FREE_PAGES)
 		goto local_freelist;

diff -urNp --exclude CVS --exclude BitKeeper --exclude {arch} --exclude .arch-ids 2.4.23pre7/mm/swap.c race/mm/swap.c
@@ -54,6 +54,19 @@ void activate_page(struct page * page)
 /**
  * lru_cache_add: add a page to the page lists
  * @page: the page to add
+ *
+ * This function is for when the caller already holds
+ * the pagemap_lru_lock.
+ */
+void __lru_cache_add(struct page * page)
+{
+	if (!PageLRU(page) && !TestSetPageLRU(page))
+		add_page_to_inactive_list(page);
+}
+
+/**
+ * lru_cache_add: add a page to the page lists
+ * @page: the page to add
  */
 void lru_cache_add(struct page * page)
 {

Andrea - If you prefer relying on open source software, check these links:

	    rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.[45]/
	    http://www.cobite.com/cvsps/

Also to keep this fix future proof. Who knows whether a super-optimised patch that masks just this particular race condition will still be safe when XFS is merged ?

I really don't like keeping the code fragile and making it easy to reintroduce bugs.

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

free_pages as said if it's buggy, then it can still trigger no matter whatever you do there, at that deep point of free_pages a alloc_page user will be able to get the page and corrupt it anyways, so it can't help and it will never be able to help no matter what xfs or whatever else gets merged. If that makes a difference alloc_page users will still break it.

we can argue about the filemap.c part, but I'm sure the page_alloc.c part can't make any sense ever.

Andrea - If you prefer relying on open source software, check these links:

	    rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.[45]/
	    http://www.cobite.com/cvsps/

Agreed, the __free_pages_ok() change can almost certainly be undone and made more efficient.

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

ok great, many thanks for double checking.

Andrea - If you prefer relying on open source software, check these links:

	    rsync.kernel.org::pub/scm/linux/kernel/bkcvs/linux-2.[45]/
	    http://www.cobite.com/cvsps/