lseek speedup

This is a fairly dopey patch to fix up the i_sem contention in lseek. Better ideas are welcome, but I'm offline until Monday so don't think I'm ignoring them...

We need to decide what we really want to lock in there. If multiple threads are updating f_pos and/or i_size at the same time then they are going to see strange results whatever the kernel does. I'd maintain that the only real obligation which the kernel has in this situation is to not oops, to not munch data and to not return competely outlandish results.

And the only way we can return outlandish results is on 32-bit SMP if one CPU reads i_size or f_pos while another CPU is in the middle of modifying it.

- We only need to take i_sem for reading i_size on 32-bit machines with SMP or preempt, so add the entertaining down32() and up32() functions for that.

- Only take i_sem in the case where we actually need to read i_size:
SEEK_END.

So this patch only speeds up SEEK_SET, SEEK_CUR and SEEK_END on 64-bit. SEEK_END on 32-bit will continue to bounce i_sem around.

- Introduce a new spinlock in struct file. Its scope is currently for providing atomicity to f_pos updates.

This lock could also be used for guarding consistency of the readahead state. But after a close walkthrough the readahead code I don't think readahead needs any locking (apart from the 32-bit reader of i_size!). Any errors in there will be +/- 1 differences in the numbers, and readahead just fixes things like that up anyway.

- Fiddled with the layout of struct file in an attempt to make it more cache-friendly.

 fs/file_table.c    |    1 
 fs/read_write.c    |   86 ++++++++++++++++++++++++++++-------------------------
 include/linux/fs.h |   15 ++++++---
 3 files changed, 57 insertions(+), 45 deletions(-)

@@ -20,53 +20,59 @@ struct file_operations generic_ro_fops =
 	mmap:		generic_file_mmap,
 };
 
+/*
+ * Assume reads and writes of long longs are atomic on 64-bit machines
+ */
+static inline void down32(struct semaphore *sem)
+{
+#if (BITS_PER_LONG != 64) && (defined(CONFIG_SMP) || defined(CONFIG_PREEMPT))
+	down(sem);
+#endif
+}
+
+static inline void up32(struct semaphore *sem)
+{
+#if (BITS_PER_LONG != 64) && (defined(CONFIG_SMP) || defined(CONFIG_PREEMPT))
+	up(sem);
+#endif
+}
+
 loff_t generic_file_llseek(struct file *file, loff_t offset, int origin)
 {
-	long long retval;
+	loff_t retval;
 	struct inode *inode = file->f_dentry->d_inode->i_mapping->host;
 
-	down(&inode->i_sem);
-	switch (origin) {
-		case 2:
-			offset += inode->i_size;
-			break;
-		case 1:
-			offset += file->f_pos;
+	if (origin == 2) {
+		down32(&inode->i_sem);
+		offset += inode->i_size;
+		up32(&inode->i_sem);
+		spin_lock(&file->f_lock);
+	} else if (origin == 1) {
+		spin_lock(&file->f_lock);
+		offset += file->f_pos;
+	} else {
+		spin_lock(&file->f_lock);
 	}
 	retval = -EINVAL;
-	if (offset>=0 && offset<=inode->i_sb->s_maxbytes) {
+	if (offset >= 0 && offset <= inode->i_sb->s_maxbytes) {
 		if (offset != file->f_pos) {
 			file->f_pos = offset;
 			file->f_version = ++event;
 		}
 		retval = offset;
 	}
-	up(&inode->i_sem);
+	spin_unlock(&file->f_lock);
 	return retval;
 }
 
 loff_t remote_llseek(struct file *file, loff_t offset, int origin)
 {
-	long long retval;
+	loff_t ret;
 
 	lock_kernel();
-	switch (origin) {
-		case 2:
-			offset += file->f_dentry->d_inode->i_size;
-			break;
-		case 1:
-			offset += file->f_pos;
-	}
-	retval = -EINVAL;
-	if (offset>=0 && offset<=file->f_dentry->d_inode->i_sb->s_maxbytes) {
-		if (offset != file->f_pos) {
-			file->f_pos = offset;
-			file->f_version = ++event;
-		}
-		retval = offset;
-	}
+	ret = generic_file_llseek(file, offset, origin);
 	unlock_kernel();
-	return retval;
+	return ret;
 }
 
 loff_t no_llseek(struct file *file, loff_t offset, int origin)

@@ -76,15 +82,18 @@ loff_t no_llseek(struct file *file, loff
 
 loff_t default_llseek(struct file *file, loff_t offset, int origin)
 {
+	struct inode *inode = file->f_dentry->d_inode;
 	long long retval;
 
-	lock_kernel();
-	switch (origin) {
-		case 2:
-			offset += file->f_dentry->d_inode->i_size;
-			break;
-		case 1:
-			offset += file->f_pos;
+	if (origin == 2) {
+		down32(&inode->i_sem);
+		offset += inode->i_size;
+		up32(&inode->i_sem);
+	} else if (origin == 1) {
+		spin_lock(&file->f_lock);
+		offset += file->f_pos;
+	} else {
+		spin_lock(&file->f_lock);
 	}
 	retval = -EINVAL;
 	if (offset >= 0) {

@@ -94,18 +103,15 @@ loff_t default_llseek(struct file *file,
 		}
 		retval = offset;
 	}
-	unlock_kernel();
+	spin_unlock(&file->f_lock);
 	return retval;
 }
 
 static inline loff_t llseek(struct file *file, loff_t offset, int origin)
 {
-	loff_t (*fn)(struct file *, loff_t, int);
-
-	fn = default_llseek;
 	if (file->f_op && file->f_op->llseek)
-		fn = file->f_op->llseek;
-	return fn(file, offset, origin);
+		return (*file->f_op->llseek)(file, offset, origin);
+	return default_llseek(file, offset, origin);
 }
 
 asmlinkage off_t sys_lseek(unsigned int fd, off_t offset, unsigned int origin)

@@ -475,20 +475,25 @@ struct file_ra_state {
 };
 
 struct file {
-	struct list_head	f_list;
 	struct dentry		*f_dentry;
+	struct list_head	f_list;
 	struct vfsmount         *f_vfsmnt;
-	struct file_operations	*f_op;
-	atomic_t		f_count;
+
 	unsigned int 		f_flags;
 	mode_t			f_mode;
+	struct file_operations	*f_op;
+	unsigned long		f_version;
+
+	atomic_t		f_count;
+	spinlock_t		f_lock;	/* for f_pos atomicity */
 	loff_t			f_pos;
+
 	struct fown_struct	f_owner;
-	unsigned int		f_uid, f_gid;
+	unsigned int		f_uid;
+	unsigned int		f_gid;
 	int			f_error;
 	struct file_ra_state	f_ra;
 
-	unsigned long		f_version;
 
 	/* needed for tty driver, and maybe others */
 	void			*private_data;

@@ -44,6 +44,7 @@ struct file * get_empty_filp(void)
 	new_one:
 		memset(f, 0, sizeof(*f));
 		atomic_set(&f->f_count,1);
+		spin_lock_init(&f->f_lock);
 		f->f_version = ++event;
 		f->f_uid = current->fsuid;
 		f->f_gid = current->fsgid;

.

I am afraid I don't have any better ideas but I don't think your patch is safe. )-:

That can only be guaranteed by holding i_sem. Since the BKL was taken out of ->readdir(), i_sem is now used for exclusion between ->readdir() and ->llseek() (well NTFS uses it anyway but many other fs which switched to generic_file_llseek() do the same). This exclusion is necessary IMHO.

->readdir() may well blow up or at the very least give "completely outlandish results" if someone modifies f_pos while it is running. Depending on when exactly it happens, ntfs_readdir() is going to be ok as it mostly sets f_pos instead of incrementing it but still, a succeeding ->llseek(), may actually end up in a different position to the one requested because of a concurrent ->readdir().

I know doing the two things at the same time requires a completely crazy multithreaded application, but then again many application developers fall into that category. (-;

I believe it can also happen if ->llseek() is allowed to run concurrently with a ->readdir()...

Best regards,

Anton

  "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cantab.net> (replace at with @)
Linux NTFS Maintainer / IRC: #ntfs on irc.openprojects.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/

It wasn't a very good idea in the first place. Forgot to take the new lock over in the updaters of f_pos.

And it's attempting to cater for a buggy application on a 32-bit machine, SMP, where the fd is shared. It's hard to justify putting any locking in lseek for that. (Then again, people should use pread() more..)

Except for readdir(). Now, why are we taking i_sem for lseek/readdir exclusion and not a per-file lock?

-

Hi Andrew,

Because it also excludes against directory modifications, etc. Just imagine what "rm somefile" or "mv somefile otherfile" or "touch newfile" would do to the directory contents and what a concurrent readdir() would do... A very loud *BANG* is the only thing that springs to mind...

btw. the directory modification locking rules are written up in Documentation/filesystems/directory-locking by our very own VFS maintainer Al Viro himself... (-;

Cheers,

Anton

  "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cantab.net> (replace at with @)
Linux NTFS Maintainer / IRC: #ntfs on irc.openprojects.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/

That's different. i_size, contents of things, yes - i_sem for those.

But protection of struct file should not be via any per-inode thing.

Doesn't cover lseek...

-

Oh, I see. But that would mean adding yet another lock to an existing locking scheme? So both i_sem and the "per file lock" would nead to be held over readdir(). That's doable but it would have to be a semaphore based lock due to readdir()...

Perhaps the f_lock from your patch, changed to a semaphore, and acquiring it in generic_file_llseek&friends, vfs_readdir() (and any other place where f_pos needs protecting) would be able to do the trick. Would that solve the lock contention problems you were seing? It would at least off-load i_sem a bit... but it would only replace one semaphore for another...

Hm, true. I hadn't read it for quite a while...

Anton

  "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cantab.net> (replace at with @)
Linux NTFS Maintainer / IRC: #ntfs on irc.openprojects.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/

Adding a sleeping lock to struct file for this would make sense; using i_sem to protect the innards of struct file ain't right.

However I'm not sure that the VFS needs to be serialising lseek and readdir at all. The fs can do that if it really needs to.

And does it really need to? Setting aside the non-atomic 64-bit read, it may be sufficient for the fs to do what ext2_readdir
does: read f_pos once on entry, write it once on exit and if there was a concurrent lseek then its results get stomped on.

Can you see any problem with that?

Anyway. It's not exactly a top-priority thing. I'll park it for a while and just stop running that test ;)

-

No problem. NTFS can very easily be turned into doing that. It would need to happen to all file systems and perhaps a little documentation in the porting document to say so for out of kernel fs...

Well, I will get ntfs_readdir changed to only read/write f_pos once on entry/exit respectively anyway...

Anton

  "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cantab.net> (replace at with @)
Linux NTFS Maintainer / IRC: #ntfs on irc.openprojects.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/

Why not make use of set_64bit instead of using a spinlock? It might need a companion get_64bit, but at least on 64 bit machines they could be defined to use a direct load/store.

-ben

"You will be reincarnated as a toad; and you will be much happier."

Hi Andrew,

        movl    $default_llseek, %esi
        movl    16(%ebx), %eax
        testl   %eax, %eax
        je      .L1427
        movl    4(%eax), %eax
        testl   %eax, %eax
        cmovne  %eax, %esi
.L1427:
        pushl   48(%esp)
        pushl   %ecx
        pushl   %edx
        pushl   12(%esp)
        call    *%esi

        movl    16(%ebx), %eax
        testl   %eax, %eax
        je      .L1428
        movl    4(%eax), %eax
        testl   %eax, %eax
        je      .L1428
        pushl   64(%esp)
        pushl   %ecx
        pushl   %edx
        pushl   %ebx
        call    *%eax
        jmp     .L1442
        .p2align 4,,7
.L1428:
        pushl   64(%esp)
        pushl   %ecx
        pushl   %edx
        pushl   12(%esp)
        call    default_llseek

  "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cantab.net> (replace at with @)
Linux NTFS Maintainer / IRC: #ntfs on irc.openprojects.net
WWW: http://linux-ntfs.sf.net/ & http://www-stu.christs.cam.ac.uk/~aia21/