[PATCH 1/5] VFS: Do (nearly) lockless generic_file_llseek

[PATCH 1/5] VFS: Do (nearly) lockless generic_file_llseek

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

The i_mutex locking of generic _file_llseek hurts currently. It means
that independent processes who just access the same file still
synchronize. Under high utilization this can cause llseek to scale
very poorly on larger systems.

First the 64bit f_pos is not necessarily atomic without locks
on 32bit systems. This can already cause races with read() today.
This was discussed on linux-kernel in the past and deemed acceptable.

The different seek modi:

SEEK_SET: Doesn't really need any locking.
If there's a race one writer wins, the other loses.

For 32bit the non atomic update races against read()
stay the same. Without a lock they can also happen
against write() now.  The read() race was deemed
acceptable in past discussions, and I think if it's
ok for read it's not ok for write too.

Don't need a lock.

SEEK_END: This behaves like SEEK_SET plus it reads
the maximum size too. Reading the maximum size would have the
32bit atomic problem. But luckily we already have a way to read
the maximum size without locking (i_size_read), so we
can just use that instead.

Without i_mutex there is no synchronization with write() anymore,
however since the write() update is atomic on 64bit it just behaves
like another racy SEEK_SET.  On non atomic 32bit it's the same
as SEEK_SET.

Don't need a lock, but need to use i_size_read()

SEEK_CUR: This has a read-modify-write race window
on the same file. One could argue that any application
doing unsynchronized seeks on the same file is already broken.
But for the sake of not adding a regression here I'm
using the file->f_lock to synchronize this. Using this
lock is much better than the inode mutex because it doesn't
synchronize between processes.

So still need a lock, but can use a cheap local one.

This patch implements this new scheme in generic_file_llseek.
I dropped generic_file_llseek_unlocked and changed all callers.

Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 fs/gfs2/file.c     |    4 ++--
 fs/nfs/file.c      |    5 +++--
 fs/read_write.c    |   33 ++++++---------------------------
 include/linux/fs.h |    2 --
 4 files changed, 11 insertions(+), 33 deletions(-)

diff --git a/fs/gfs2/file.c b/fs/gfs2/file.c
index a9f5cbe..5590c0f 100644
--- a/fs/gfs2/file.c
+++ b/fs/gfs2/file.c
@@ -63,11 +63,11 @@ static loff_t gfs2_llseek(struct file *file, loff_t offset, int origin)
 		error = gfs2_glock_nq_init(ip->i_gl, LM_ST_SHARED, LM_FLAG_ANY,
 					   &i_gh);
 		if (!error) {
-			error = generic_file_llseek_unlocked(file, offset, origin);
+			error = generic_file_llseek(file, offset, origin);
 			gfs2_glock_dq_uninit(&i_gh);
 		}
 	} else
-		error = generic_file_llseek_unlocked(file, offset, origin);
+		error = generic_file_llseek(file, offset, origin);
 
 	return error;
 }
diff --git a/fs/nfs/file.c b/fs/nfs/file.c
index 2f093ed..6b52b09 100644
--- a/fs/nfs/file.c
+++ b/fs/nfs/file.c
@@ -195,11 +195,12 @@ static loff_t nfs_file_llseek(struct file *filp, loff_t offset, int origin)
 		if (retval < 0)
 			return (loff_t)retval;
 
+		/* AK: should drop this lock. Unlikely to be needed. */
 		spin_lock(&inode->i_lock);
-		loff = generic_file_llseek_unlocked(filp, offset, origin);
+		loff = generic_file_llseek(filp, offset, origin);
 		spin_unlock(&inode->i_lock);
 	} else
-		loff = generic_file_llseek_unlocked(filp, offset, origin);
+		loff = generic_file_llseek(filp, offset, origin);
 	return loff;
 }
 
diff --git a/fs/read_write.c b/fs/read_write.c
index 5520f8a..9bd5d23 100644
--- a/fs/read_write.c
+++ b/fs/read_write.c
@@ -36,22 +36,23 @@ static inline int unsigned_offsets(struct file *file)
 }
 
 /**
- * generic_file_llseek_unlocked - lockless generic llseek implementation
+ * generic_file_llseek - generic llseek implementation for regular files
  * @file:	file structure to seek on
  * @offset:	file offset to seek to
  * @origin:	type of seek
  *
- * Updates the file offset to the value specified by @offset and @origin.
- * Locking must be provided by the caller.
+ * This is a generic implemenation of ->llseek useable for all normal local
+ * filesystems.  It just updates the file offset to the value specified by
+ * @offset and @origin under i_mutex.
  */
 loff_t
-generic_file_llseek_unlocked(struct file *file, loff_t offset, int origin)
+generic_file_llseek(struct file *file, loff_t offset, int origin)
 {
 	struct inode *inode = file->f_mapping->host;
 
 	switch (origin) {
 	case SEEK_END:
-		offset += inode->i_size;
+		offset += i_size_read(inode);
 		break;
 	case SEEK_CUR:
 		/*
@@ -79,28 +80,6 @@ generic_file_llseek_unlocked(struct file *file, loff_t offset, int origin)
 
 	return offset;
 }
-EXPORT_SYMBOL(generic_file_llseek_unlocked);
-
-/**
- * generic_file_llseek - generic llseek implementation for regular files
- * @file:	file structure to seek on
- * @offset:	file offset to seek to
- * @origin:	type of seek
- *
- * This is a generic implemenation of ->llseek useable for all normal local
- * filesystems.  It just updates the file offset to the value specified by
- * @offset and @origin under i_mutex.
- */
-loff_t generic_file_llseek(struct file *file, loff_t offset, int origin)
-{
-	loff_t rval;
-
-	mutex_lock(&file->f_dentry->d_inode->i_mutex);
-	rval = generic_file_llseek_unlocked(file, offset, origin);
-	mutex_unlock(&file->f_dentry->d_inode->i_mutex);
-
-	return rval;
-}
 EXPORT_SYMBOL(generic_file_llseek);
 
 /**
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 1c77787..deec2cd 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -2335,8 +2335,6 @@ file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping);
 extern loff_t noop_llseek(struct file *file, loff_t offset, int origin);
 extern loff_t no_llseek(struct file *file, loff_t offset, int origin);
 extern loff_t generic_file_llseek(struct file *file, loff_t offset, int origin);
-extern loff_t generic_file_llseek_unlocked(struct file *file, loff_t offset,
-			int origin);
 extern int generic_file_open(struct inode * inode, struct file * filp);
 extern int nonseekable_open(struct inode * inode, struct file * filp);
 
-- 
1.7.4.4

[PATCH 2/5] VFS: Use f_lock for SEEK_SET

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 fs/read_write.c    |   44 ++++++++++++++++++++++++++++++--------------
 include/linux/fs.h |    3 ++-
 2 files changed, 32 insertions(+), 15 deletions(-)

diff --git a/fs/read_write.c b/fs/read_write.c
index 9bd5d23..0b1d4ca 100644
--- a/fs/read_write.c
+++ b/fs/read_write.c
@@ -35,6 +35,20 @@ static inline int unsigned_offsets(struct file *file)
 	return file->f_mode & FMODE_UNSIGNED_OFFSET;
 }
 
+static loff_t lseek_execute(struct file *file, struct inode *inode, loff_t offset)
+{
+	if (offset < 0 && !unsigned_offsets(file))
+		return -EINVAL;
+	if (offset > inode->i_sb->s_maxbytes)
+		return -EINVAL;
+
+	if (offset != file->f_pos) {
+		file->f_pos = offset;
+		file->f_version = 0;
+	}	
+	return offset;
+}
+
 /**
  * generic_file_llseek - generic llseek implementation for regular files
  * @file:	file structure to seek on
@@ -44,6 +58,12 @@ static inline int unsigned_offsets(struct file *file)
  * This is a generic implemenation of ->llseek useable for all normal local
  * filesystems.  It just updates the file offset to the value specified by
  * @offset and @origin under i_mutex.
+ * 
+ * Synchronization: 
+ * SEEK_SET is unsynchronized (but atomic on 64bit platforms)
+ * SEEK_CUR is synchronized against other SEEK_CURs, but not read/writes.
+ * read/writes behave like SEEK_SET against seeks.
+ * SEEK_END 
  */
 loff_t
 generic_file_llseek(struct file *file, loff_t offset, int origin)
@@ -63,22 +83,18 @@ generic_file_llseek(struct file *file, loff_t offset, int origin)
 		 */
 		if (offset == 0)
 			return file->f_pos;
-		offset += file->f_pos;
-		break;
-	}
-
-	if (offset < 0 && !unsigned_offsets(file))
-		return -EINVAL;
-	if (offset > inode->i_sb->s_maxbytes)
-		return -EINVAL;
-
-	/* Special lock needed here? */
-	if (offset != file->f_pos) {
-		file->f_pos = offset;
-		file->f_version = 0;
+		/* 
+		 * f_lock protects against read/modify/write race with other
+		 * SEEK_CURs. Note that parallel writes and reads behave
+		 * like SEEK_SET.
+		 */
+		spin_lock(&file->f_lock);
+		offset = lseek_execute(file, inode, offset + file->f_pos);
+		spin_unlock(&file->f_lock);
+		return offset;
 	}
 
-	return offset;
+	return lseek_execute(file, inode, offset);
 }
 EXPORT_SYMBOL(generic_file_llseek);
 
diff --git a/include/linux/fs.h b/include/linux/fs.h
index deec2cd..a19d164 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -946,7 +946,8 @@ struct file {
 #define f_dentry	f_path.dentry
 #define f_vfsmnt	f_path.mnt
 	const struct file_operations	*f_op;
-	spinlock_t		f_lock;  /* f_ep_links, f_flags, no IRQ */
+	spinlock_t		f_lock;  /* f_ep_links, f_flags, no IRQ, 
+					    SEEK_SET */
 #ifdef CONFIG_SMP
 	int			f_sb_list_cpu;
 #endif
-- 
1.7.4.4

[PATCH 3/5] VFS: Add generic_file_llseek_size

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

Add a generic_file_llseek variant to the VFS that allows passing in
the current file size, instead of always using inode->i_size.
This can be used to eliminate some cut'n'paste seek code in ext4.

Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 fs/read_write.c    |   20 ++++++++++++++++++++
 include/linux/fs.h |    2 ++
 2 files changed, 22 insertions(+), 0 deletions(-)

diff --git a/fs/read_write.c b/fs/read_write.c
index 0b1d4ca..4924602 100644
--- a/fs/read_write.c
+++ b/fs/read_write.c
@@ -99,6 +99,26 @@ generic_file_llseek(struct file *file, loff_t offset, int origin)
 EXPORT_SYMBOL(generic_file_llseek);
 
 /**
+ * generic_file_llseek_size - generic llseek implementation for regular files
+ * @file:	file structure to seek on
+ * @offset:	file offset to seek to
+ * @origin:	type of seek
+ * 
+ * Variant of generic_file_llseek_size that allows passing in a custom
+ * file size.
+ */
+loff_t generic_file_llseek_size(struct file *file, loff_t offset, int origin, 
+				loff_t size)
+{
+	struct inode *inode = file->f_mapping->host;
+
+	if (origin == SEEK_END)
+		return lseek_execute(file, inode, offset + size);
+	return generic_file_llseek(file, offset, origin);
+}
+EXPORT_SYMBOL(generic_file_llseek_size);
+
+/**
  * noop_llseek - No Operation Performed llseek implementation
  * @file:	file structure to seek on
  * @offset:	file offset to seek to
diff --git a/include/linux/fs.h b/include/linux/fs.h
index a19d164..0642821 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -2336,6 +2336,8 @@ file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping);
 extern loff_t noop_llseek(struct file *file, loff_t offset, int origin);
 extern loff_t no_llseek(struct file *file, loff_t offset, int origin);
 extern loff_t generic_file_llseek(struct file *file, loff_t offset, int origin);
+extern loff_t generic_file_llseek_size(struct file *file, loff_t offset, int origin, 
+				       loff_t size);
 extern int generic_file_open(struct inode * inode, struct file * filp);
 extern int nonseekable_open(struct inode * inode, struct file * filp);
 
-- 
1.7.4.4

[PATCH 4/5] EXT4: Replace cut'n'pasted llseek code with generic_file_llseek_size

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

This gives ext4 the benefits of unlocked llseek.

Cc: tytso@mit.edu
Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 fs/ext4/file.c |   26 +-------------------------
 1 files changed, 1 insertions(+), 25 deletions(-)

diff --git a/fs/ext4/file.c b/fs/ext4/file.c
index 2c09723..ce40447 100644
--- a/fs/ext4/file.c
+++ b/fs/ext4/file.c
@@ -224,32 +224,8 @@ loff_t ext4_llseek(struct file *file, loff_t offset, int origin)
 		maxbytes = EXT4_SB(inode->i_sb)->s_bitmap_maxbytes;
 	else
 		maxbytes = inode->i_sb->s_maxbytes;
-	mutex_lock(&inode->i_mutex);
-	switch (origin) {
-	case SEEK_END:
-		offset += inode->i_size;
-		break;
-	case SEEK_CUR:
-		if (offset == 0) {
-			mutex_unlock(&inode->i_mutex);
-			return file->f_pos;
-		}
-		offset += file->f_pos;
-		break;
-	}
-
-	if (offset < 0 || offset > maxbytes) {
-		mutex_unlock(&inode->i_mutex);
-		return -EINVAL;
-	}
-
-	if (offset != file->f_pos) {
-		file->f_pos = offset;
-		file->f_version = 0;
-	}
-	mutex_unlock(&inode->i_mutex);
 
-	return offset;
+	return generic_file_llseek_size(file, offset, origin, maxbytes);
 }
 
 const struct file_operations ext4_file_operations = {
-- 
1.7.4.4

[PATCH 5/5] NFS: Drop unnecessary locking in llseek

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

This makes NFS follow the standard generic_file_llseek locking scheme.

Cc: Trond.Myklebust@netapp.com
Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 fs/nfs/file.c |   11 ++---------
 1 files changed, 2 insertions(+), 9 deletions(-)

diff --git a/fs/nfs/file.c b/fs/nfs/file.c
index 6b52b09..371f33f 100644
--- a/fs/nfs/file.c
+++ b/fs/nfs/file.c
@@ -180,8 +180,6 @@ force_reval:
 
 static loff_t nfs_file_llseek(struct file *filp, loff_t offset, int origin)
 {
-	loff_t loff;
-
 	dprintk("NFS: llseek file(%s/%s, %lld, %d)\n",
 			filp->f_path.dentry->d_parent->d_name.name,
 			filp->f_path.dentry->d_name.name,
@@ -194,14 +192,9 @@ static loff_t nfs_file_llseek(struct file *filp, loff_t offset, int origin)
 		int retval = nfs_revalidate_file_size(inode, filp);
 		if (retval < 0)
 			return (loff_t)retval;
+	}
 
-		/* AK: should drop this lock. Unlikely to be needed. */
-		spin_lock(&inode->i_lock);
-		loff = generic_file_llseek(filp, offset, origin);
-		spin_unlock(&inode->i_lock);
-	} else
-		loff = generic_file_llseek(filp, offset, origin);
-	return loff;
+	return generic_file_llseek(filp, offset, origin);
 }
 
 /*
-- 
1.7.4.4

Re: [PATCH 1/5] VFS: Do (nearly) lockless generic_file_llseek

[Arnd Bergmann]

On Thursday 16 June 2011 23:07:18 Andi Kleen wrote:
> So still need a lock, but can use a cheap local one.
> 
> This patch implements this new scheme in generic_file_llseek.
> I dropped generic_file_llseek_unlocked and changed all callers.

What about default_llseek? If you change generic_file_llseek, you should
probably change that, too.

	Arnd

Re: [PATCH 1/5] VFS: Do (nearly) lockless generic_file_llseek

[Andi Kleen]

On Fri, Jun 17, 2011 at 02:40:14PM +0200, Arnd Bergmann wrote:
> On Thursday 16 June 2011 23:07:18 Andi Kleen wrote:
> > So still need a lock, but can use a cheap local one.
> > 
> > This patch implements this new scheme in generic_file_llseek.
> > I dropped generic_file_llseek_unlocked and changed all callers.
> 
> What about default_llseek? If you change generic_file_llseek, you should
> probably change that, too.

That's used by a lot of drivers, and since I cannot audit them
all I chose to be conservative. not sure it's ever performance
critical anyways?

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH 1/5] VFS: Do (nearly) lockless generic_file_llseek

[Arnd Bergmann]

On Friday 17 June 2011 19:42:39 Andi Kleen wrote:
> On Fri, Jun 17, 2011 at 02:40:14PM +0200, Arnd Bergmann wrote:
> > On Thursday 16 June 2011 23:07:18 Andi Kleen wrote:
> > > So still need a lock, but can use a cheap local one.
> > > 
> > > This patch implements this new scheme in generic_file_llseek.
> > > I dropped generic_file_llseek_unlocked and changed all callers.
> > 
> > What about default_llseek? If you change generic_file_llseek, you should
> > probably change that, too.
> 
> That's used by a lot of drivers, and since I cannot audit them
> all I chose to be conservative. not sure it's ever performance
> critical anyways?

Probably not. Note that all uses of default_llseek were introduced
in the conversion from an implicit default_llseek when they did not
set the operation before the BKL conversion. There were also patches
floating around to merge generic_file_llseek and default_llseek.

There was not a single case of a driver that relied on the BKL to
lock against default_llseek before I changed it to i_mutex.

	Arnd