fallocate INSERT_RANGE/COLLAPSE_RANGE is completely broken [PATCH]

Bit of previous discussion:
http://thread.gmane.org/gmane.linux.file-systems/101201/

The underlying issue is that we have no mechanism for invalidating a range of the pagecache and then _keeping it invalidated_ while we Do Stuff.

The fallocate INSERT_RANGE/COLLAPSE_RANGE situation seems likely to be worse than I initially thought. I've been digging into this in the course of bcachefs testing - I was hitting assertions that meant state hanging off the page cache (in this case, allocation information, i.e. whether we needed to reserve space on write) was inconsistent with the btree in writepages().

Well, bcachefs isn't the only filesystem that hangs additional state off the pagecache, and the situation today is that an unpriviliged user can cause inconsistencies there by just doing buffered reads concurrently with INSERT_RANGE/COLLAPSE_RANGE. I highly highly doubt this is an issue of just "oops, you corrupted your file because you were doing stupid stuff" - who knows what internal invariants are getting broken here, and I don't particularly care to find out.

I'm pretty certain that ext4 and xfs are both broken here - I haven't dug into the btrfs code. The impression I get from reading the code is that whoever wrote it was cripping off of truncate - except that truncate relies on the i_size change to work; without that there's no way this code can possibly work.

That's the bad news. Good news is, I think it's fixable.

My solution is just to add a lock (per address_space) around adding pages to the pagecache - it's got some funny semantics so as to be usable for dio writes, but it's just a lock. (It's got two states like an rwlock, except that both states are shared and only exclusive with the other states; dio writes don't block other dio writes, buffered IO adding pages to the pagecache does't block other pages being added).

The only tricky bit is the recursion Dave noted in the dio write path - get_user_pages() -> fault(). My solution is to just keep track of what address space we have locked (blocking page adds) in task_struct, then A) don't deadlock in __add_to_page_cache_locked(), and B) don't do readahead in filemap_fault() (which means we can delete another hack from the dio write code).

I don't particularly care for where the add side of the lock is taken - it works, but it means we can't distinguish accidental recursion from intentional. I'm open to ideas there. Also, we made better use of the add side of the lock we could probably delete a lot of fragile code for synchronization with truncate.

Patch below is reliably passing xfstests for me (where previously I was hitting the aforementioned pagecache inconsistency assertions). I've only hooked up bcachefs so far, other filesystems should be pretty trivial (but it does need individual filesystems to be converted).

One issue I haven't dealt with is that dio writes can starve buffered IO/mmapped IO with this lock - not sure if that's worth dealing with.

Patch below includes bcachefs changes, but is otherwise on 4.5. Available in my usual git repo:

https://evilpiepirate.org/git/linux-bcache.git/log/?h=bcache-dev-pagecache-lock

-- >8 --
Subject: [PATCH] mm: pagecache add lock

Add a per address space lock around adding pages to the pagecache - making it possible for fallocate INSERT_RANGE/COLLAPSE_RANGE to work correctly, and also hopefully making truncate and dio a bit saner.

---
 drivers/md/bcache/fs-io.c | 197 +++++++++++++++++++++++++---------------------
 fs/inode.c                |   1 +
 include/linux/fs.h        |  23 ++++++
 include/linux/init_task.h |   1 +
 include/linux/sched.h     |   4 +
 mm/filemap.c              |  85 ++++++++++++++++++--
 6 files changed, 217 insertions(+), 94 deletions(-)

index 69b8b526c1..617c61e070 100644
@@ -345,6 +345,7 @@ void address_space_init_once(struct address_space *mapping)
 {
 	memset(mapping, 0, sizeof(*mapping));
 	INIT_RADIX_TREE(&mapping->page_tree, GFP_ATOMIC);
+	pagecache_lock_init(&mapping->add_lock);
 	spin_lock_init(&mapping->tree_lock);
 	init_rwsem(&mapping->i_mmap_rwsem);
 	INIT_LIST_HEAD(&mapping->private_list);

index ae68100210..a806c09c21 100644
@@ -424,9 +424,32 @@ int pagecache_write_end(struct file *, struct address_space *mapping,
 				loff_t pos, unsigned len, unsigned copied,
 				struct page *page, void *fsdata);
 
+/*
+ * Two-state lock - can be taken for add or block - both states are shared,
+ * like read side of rwsem, but conflict with other state:
+ */
+struct pagecache_lock {
+	atomic_long_t		v;
+	wait_queue_head_t	wait;
+};
+
+static inline void pagecache_lock_init(struct pagecache_lock *lock)
+{
+	atomic_long_set(&lock->v, 0);
+	init_waitqueue_head(&lock->wait);
+}
+
+void pagecache_add_put(struct pagecache_lock *);
+void pagecache_add_get(struct pagecache_lock *);
+void __pagecache_block_put(struct pagecache_lock *);
+void __pagecache_block_get(struct pagecache_lock *);
+void pagecache_block_put(struct pagecache_lock *);
+void pagecache_block_get(struct pagecache_lock *);
+
 struct address_space {
 	struct inode		*host;		/* owner: inode, block_device */
 	struct radix_tree_root	page_tree;	/* radix tree of all pages */
+	struct pagecache_lock	add_lock;	/* protects adding new pages */
 	spinlock_t		tree_lock;	/* and lock protecting it */
 	atomic_t		i_mmap_writable;/* count VM_SHARED mappings */
 	struct rb_root		i_mmap;		/* tree of private and shared mappings */

index f2cb8d4551..1bded65b89 100644
@@ -235,6 +235,7 @@ extern struct task_group root_task_group;
 		.signal = {{0}}},					\
 	.blocked	= {{0}},					\
 	.alloc_lock	= __SPIN_LOCK_UNLOCKED(tsk.alloc_lock),		\
+	.pagecache_lock = NULL,						\
 	.journal_info	= NULL,						\
 	.cpu_timers	= INIT_CPU_TIMERS(tsk.cpu_timers),		\
 	.pi_lock	= __RAW_SPIN_LOCK_UNLOCKED(tsk.pi_lock),	\

index ea5e7c5ce6..48762b6b75 100644
@@ -134,6 +134,7 @@ struct perf_event_context;
 struct blk_plug;
 struct filename;
 struct nameidata;
+struct pagecache_lock;
 
 #define VMACACHE_BITS 2
 #define VMACACHE_SIZE (1U << VMACACHE_BITS)

@@ -1649,6 +1650,9 @@ struct task_struct {
 	unsigned int in_ubsan;
 #endif
 
+	/* currently held lock, for avoiding recursing in fault path: */
+	struct pagecache_lock *pagecache_lock;
+
 /* journalling filesystem info */
 	void *journal_info;
 

2.8.0.rc3

I'd like to see a test case for this. Concurrent IO and/or page faults should not run at the same as fallocate on XFS. Hence I'd like to see the test cases that demonstrate buffered reads are causing corruption during insert/collapse range operations. We use the same locking strategy for fallocate as we use for truncate and all the other internal extent manipulation operations, so if there's something wrong, we need to fix it.

Cheers,

Dave.

Dave Chinner
[email protected]

It's entirely possible I'm wrong about XFS - your fault path locking looked correct, and I did see you had extra locking in your buffered read path but I thought it was a different lock. I'll recheck later, but for the moment I'm just going to assume I misspoke (and tbh always found xfs's locking to be quite rigorous).

ext4 uses the generic code in all the places you're hooking into though - .fault, .read_iter, etc.

The scheme I've got in this patch should perform quite a bit better than what you're doing - only locking in the slow cache miss path, vs. every time you touch the page cache.

There are two locks the XFS_IOLOCK for read/write/splice IO path vs truncate/fallocate exclusion, and XFS_MMAPLOCK for page fault vs truncate/fallocate exclusion.

I'm not sure I follow - how does this work when a fallocate operation use the page cache for, say, zeroing data blocks rather than invalidating them (e.g. FALLOC_FL_ZERO_RANGE can validly zero blocks through the page cache, so can hole punching)? Won't the buffered read then return a mix of real and zeroed data, depending who wins the race to each underlying page lock?

i.e. if the locking only occurs in the page insert slow path, then it doesn't provide sufficient exclusion for extent manipulation operations that use the page cache during their normal operation. IOWs, other, higher level synchronisation methods for fallocate are still necessary....

Cheers,

Dave.

Dave Chinner
[email protected]

Ok, that makes sense then.

Yes, but does that matter? I don't know of any requirement that the entire fallocate be atomic, and writes > PAGE_SIZE aren't generally atomic wrt reads either (but looking at the code it looks like XFS is special there too...)

Well, I would argue it _is_ enough for internal consistency, if you want to provide stronger atomicity guarantees to userspace (not that there's anything wrong with that) I think I'd argue that really that's a different issue.

Also the situation seems to be that XFS provides stronger guarantees than any other Linux filesystem, which is sucky from an application point of view because they don't want to have to depend on running on XFS for correctness. It seems like it'd actually be pretty easy to lift your locking scheme to the generic VFS code, and then possibly even have it be controlled with a per inode flag so that applications that don't need the locking aren't paying for it.

IMO, yes. Do we really want a read returning partial data that might be zeros or even data from different offsets in the file as a shift is in progress?

POSIX says writes should be atomic w.r.t. to other data accesses. i.e. that a concurrent overlapping read should not see data that has been partially written. And, yes, XFS is the only Linux filesystem that actually complies with that requirement - page-based locking does not provide this.

Even though there is no standard to define behaviour, fallocate should behave the same way with respect to user data accesses. Reads that return partial data from fallocate are just as bad as reads that return partial data from write. Imagine if we treated truncate like that...

And therein lies the issue - much of what fallocate does is equivalent to truncate - it can extend files, it can remove data from files, it can move data around in files. This stuff needs to be atomic w.r.t. other user data accesses precisely because of the way they manipulate user data in the file.

And there are other implementation based reasons, too. For example:
we cannot modify the underlying storage mappings to data while there is IO in progress over that range as the moment we free the block, it could be reallocated to something else. Hence if there is IO in flight while we are freeing blocks we have a potential use-after-free race condition. Truncate has this exact same issue, and it really has nothing to do with page cache level interactions.

IOWs, when we directly manipulate the block mapping of an inode outside of the IO path, we have to a) stop data IO submission and page faults, b) wait for existing IO to drain, c) invalidate cached data over the range to be modified, and d) modify the block mapping of the inode, e) commit the change, and finally f) allow IO to restart.

AFAICT, your patches do not completely address a) because they only block page cache insertion (e.g. won't stop direct IO submission) and they don't do b) at all. Hence it doesn't create an IO barrier and so I don't see how it can replace the existing IO vs block map synchronisation mechanisms we already have.

Yes, it will allow us to ensure mmap/direct IO coherency because we can block page faults while DIO is in progress, but AFAICT it doesn't prevent us from submitting more DIO on the inode at the same time...

Sure, but that's the reality that people have lived with for a long time, especially if they have an app that needs direct IO concurrency (e.g. databases) or large amounts of data to be stored...

Slowly, slowly starting to happen:

commit 5955102c9984fa081b2d570cfac75c97eecf8f3b

Author: Al Viro <[email protected]>
Date:   Fri Jan 22 15:40:57 2016 -0500

    wrappers for ->i_mutex access
    
    parallel to mutex_{lock,unlock,trylock,is_locked,lock_nested},
    inode_foo(inode) being mutex_foo(&inode->i_mutex).
    
    Please, use those for access to ->i_mutex; over the coming cycle
    ->i_mutex will become rwsem, with ->lookup() done with it held
    only shared.
    
    Signed-off-by: Al Viro <[email protected]>

Cheers,

Dave.

Dave Chinner
[email protected]