2.5: push BKL out of llseek

This patch pushes the BKL out of llseek() and into the individual llseek methods. For generic_file_llseek, I replaced it with the inode semaphore. The lock contention is noticeable even on 2-way systems. Since we simply push the BKL further down the call chain (its the llseek method's responsibilities now) we aren't doing anything hackish or unsafe.

I suspect some (Al) may consider this a suboptimal solution, and I agree. However it is a first step -- tightening the locks -- toward a better locking scheme, which is hopefully devoid of the BKL.

The best scores from a slew of dbench runs:

	(2.5.3-pre6 on 2-way Athlon)
	with patch	133.651	165.575	66.9876	37.5297	24.9436
	without patch	132.541	160.774	60.1174	33.2065	22.0126

Interestingly, the shorter lock times corresponded to an 8.9% reduction in scheduling latency (under the above dbench load) with the preemptible kernel.

Robert Love

diff -urN linux-2.5.3-pre6/Documentation/filesystems/Locking linux/Documentation/filesystems/Locking
@@ -219,7 +219,7 @@
 locking rules:
 	All except ->poll() may block.
 		BKL
-llseek:		yes
+llseek:		yes	(see below)
 read:		no
 write:		no
 readdir:	yes	(see below)

@@ -235,6 +235,10 @@
 readv:		no
 writev:		no
 
+->llseek() locking has moved from llseek to the individual llseek
+implementations.  If your fs is not using generic_file_llseek, you
+need to acquire and release the BKL in your ->llseek().
+
 ->open() locking is in-transit: big lock partially moved into the methods.
 The only exception is ->open() in the instances of file_operations that never
 end up in ->i_fop/->proc_fops, i.e. ones that belong to character devices

diff -urN linux-2.5.3-pre6/fs/block_dev.c linux/fs/block_dev.c
@@ -170,6 +170,8 @@
 	loff_t size = file->f_dentry->d_inode->i_bdev->bd_inode->i_size;
 	loff_t retval;
 
+	lock_kernel();
+
 	switch (origin) {
 		case 2:
 			offset += size;

@@ -186,6 +188,7 @@
 		}
 		retval = offset;
 	}
+	unlock_kernel();
 	return retval;
 }
 	

diff -urN linux-2.5.3-pre6/fs/hfs/file_cap.c linux/fs/hfs/file_cap.c
@@ -91,6 +91,8 @@
 {
 	long long retval;
 
+	lock_kernel();
+
 	switch (origin) {
 		case 2:
 			offset += file->f_dentry->d_inode->i_size;

@@ -106,6 +108,7 @@
 		}
 		retval = offset;
 	}
+	unlock_kernel();
 	return retval;
 }
 

diff -urN linux-2.5.3-pre6/fs/hfs/file_hdr.c linux/fs/hfs/file_hdr.c
@@ -347,6 +347,8 @@
 {
 	long long retval;
 
+	lock_kernel();
+
 	switch (origin) {
 		case 2:
 			offset += file->f_dentry->d_inode->i_size;

@@ -362,6 +364,7 @@
 		}
 		retval = offset;
 	}
+	unlock_kernel();
 	return retval;
 }
 

diff -urN linux-2.5.3-pre6/fs/hpfs/dir.c linux/fs/hpfs/dir.c
@@ -29,6 +29,9 @@
 	struct inode *i = filp->f_dentry->d_inode;
 	struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
 	struct super_block *s = i->i_sb;
+
+	lock_kernel();
+
 	/*printk("dir lseek\n");*/
 	if (new_off == 0 || new_off == 1 || new_off == 11 || new_off == 12 || new_off == 13) goto ok;
 	hpfs_lock_inode(i);

@@ -40,10 +43,12 @@
 	}
 	hpfs_unlock_inode(i);
 	ok:
+	unlock_kernel();
 	return filp->f_pos = new_off;
 	fail:
 	hpfs_unlock_inode(i);
 	/*printk("illegal lseek: %016llx\n", new_off);*/
+	unlock_kernel();
 	return -ESPIPE;
 }
 

diff -urN linux-2.5.3-pre6/fs/proc/generic.c linux/fs/proc/generic.c
@@ -16,6 +16,7 @@
 #include <linux/stat.h>
 #define __NO_VERSION__
 #include <linux/module.h>
+#include <linux/smp_lock.h>
 #include <asm/bitops.h>
 
 static ssize_t proc_file_read(struct file * file, char * buf,

@@ -140,22 +141,30 @@
 static loff_t
 proc_file_lseek(struct file * file, loff_t offset, int orig)
 {
+    lock_kernel();
+
     switch (orig) {
     case 0:
 	if (offset < 0)
-	    return -EINVAL;    
+	    goto out;
 	file->f_pos = offset;
+	unlock_kernel();
 	return(file->f_pos);
     case 1:
 	if (offset + file->f_pos < 0)
-	    return -EINVAL;    
+	    goto out;
 	file->f_pos += offset;
+	unlock_kernel();
 	return(file->f_pos);
     case 2:
-	return(-EINVAL);
+	goto out;
     default:
-	return(-EINVAL);
+	goto out;
     }
+
+out:
+    unlock_kernel();
+    return -EINVAL;
 }
 
 /*

diff -urN linux-2.5.3-pre6/fs/read_write.c linux/fs/read_write.c
@@ -29,6 +29,8 @@
 {
 	long long retval;
 
+	down(&file->f_dentry->d_inode->i_sem);
+
 	switch (origin) {
 		case 2:
 			offset += file->f_dentry->d_inode->i_size;

@@ -45,6 +47,7 @@
 		}
 		retval = offset;
 	}
+	up(&file->f_dentry->d_inode->i_sem);
 	return retval;
 }
 

@@ -57,6 +60,8 @@
 {
 	long long retval;
 
+	lock_kernel();
+
 	switch (origin) {
 		case 2:
 			offset += file->f_dentry->d_inode->i_size;

@@ -73,6 +78,7 @@
 		}
 		retval = offset;
 	}
+	unlock_kernel();
 	return retval;
 }
 

@@ -84,9 +90,7 @@
 	fn = default_llseek;
 	if (file->f_op && file->f_op->llseek)
 		fn = file->f_op->llseek;
-	lock_kernel();
 	retval = fn(file, offset, origin);
-	unlock_kernel();
 	return retval;
 }
 

diff -urN linux-2.5.3-pre6/fs/ufs/file.c linux/fs/ufs/file.c
@@ -47,6 +47,8 @@
 	long long retval;
 	struct inode *inode = file->f_dentry->d_inode;
 
+	lock_kernel();
+
 	switch (origin) {
 		case 2:
 			offset += inode->i_size;

@@ -64,6 +66,7 @@
 		}
 		retval = offset;
 	}
+	unlock_kernel();
 	return retval;
 }
 

Thinking about that, that actally sounds like the _right_ thing to do even from a correctness standpoint - as llseek() looks at the inode size, so we should have that lock anyway.

So I'd suggest doing the inode semaphore globally, instead of using kernel_lock at all.

Al?

Linus

This was my end result (or some sort of proper finer-grained lock) but I was unsure of how to deal with the other llseek methods that may be oddball. I have no reason to suspect using the inode semaphore won't work.

Another gain from pushing the locks into each method is that we can pick and choose as-needed. If it turns out inode semaphore is a global solution, the following patch is sufficient. Otherwise, we could replace the lock_kernel in each caller with the inode semaphore, as appropriate. Oh Al ??

Robert Love

@@ -84,9 +84,9 @@
 	fn = default_llseek;
 	if (file->f_op && file->f_op->llseek)
 		fn = file->f_op->llseek;
-	lock_kernel();
+	down(&file->f_dentry->d_inode->i_sem);
 	retval = fn(file, offset, origin);
-	unlock_kernel();
+	up(&file->f_dentry->d_inode->i_sem);
 	return retval;
 }
 

Doing it in the low-level filesystem would match how we now do it inside generic_file_write() - ie the locking is done by the low-level filesystem, but most low-level filesystems choose to use a generic helper function.

And I think your patch is slightly wrong:

	file->f_dentry->d_inode->i_mapping->host->i_sem

OK. Hopefully the inode semaphore works ...

Ahh, learn something ;-)

Robert Love

@@ -84,9 +84,9 @@
 	fn = default_llseek;
 	if (file->f_op && file->f_op->llseek)
 		fn = file->f_op->llseek;
-	lock_kernel();
+	down(&file->f_dentry->d_inode->i_mapping->host->i_sem);
 	retval = fn(file, offset, origin);
-	unlock_kernel();
+	up(&file->f_dentry->d_inode->i_mapping->host->i_sem);
 	return retval;
 }
 

I feared this too, but eventually I decided it was worth it and benchmarks backed that up. If nothing else this is yet-another-excuse for locks that can spin-then-sleep.

I posted dbench results, which show a positive gain even on 2-way for multiple client loads.

Robert Love

Yes, but the other factor to consider here is why did the extra schedule take place at all? I think this is a actually a scheduler issue, and I'm hoping that the new scheduler will behave better in this case. A call to schedule() should not happen unless the woken process has a higher priority than the process that did the unlock, but the old scheduler evidently always calculated this to be the case. But we really want the process that did the unlock to continue running (until the end of its timeslice, if not preempted or blocked before then), just as it would when the lock was a spinlock. It would be interesting to see whether the new scheduler gets this right.

Am I remembering the problem correctly?

Nigel Gamble [email protected]
Mountain View, CA, USA. http://www.nrg.org/

I don't think so :)

The problem was that the semaphore was highly contended, so the losing process was explicitly scheduling away.

This doesn't necessarily mean that it was a long-held lock. In this case, it was a short-held lock, but it was also very *frequently*
being held and released. This is a scenario where a spinlock is
heaps more appropriate than a semaphore.

I don't think we need any locking at all in the default lseek() path, btw. Apart from the non-atomic i_size thing, which is only an issue for 32-bit machines.

-

Oh, well in that case, I agree that a spinlock is more appropriate.

Nigel Gamble [email protected]
Mountain View, CA, USA. http://www.nrg.org/

I'd agree, except I doubt there is every much contention on the _same_ file.

The reason llseek() ends up being so clear on the profiles is that it's a very common system call under certain loads _and_ it uses a shared lock for everything.

Also note the correctness issue (ie serialization on i_size), although that is only an issue for SEEK_END (and maybe the lock should only be gotten for that case. I'd love to hear what Al thinks..

Linus

But dbench does lots of seeking against *different* files, so removal of a shared lock will help there.

But an application where multiple CPUs lseek and write the *same* file could take a hit....

(And where's the locking for (non-atomic) i_size in sys_stat())

-

did you benchmark with anything other than dbench ?

| Dave Jones.        http://www.codemonkey.org.uk
| SuSE Labs

No, and I really don't want to hear how dbench is a terrible benchmark. I didn't craft the patch around dbench and I think, here at least, dbench is an OK benchmark. I ran it numerous times over multiple client loads.

I think its clear there won't be a negative impact, because:

- acquiring the inode semaphore isn't any heavier (in the acquire case) than the BKL

- the lock contention on each inode semaphore is relatively zero

- besides just scaling badly with the using a global lock against all inodes, we use the BKL which in such workloads is already highly contested.

That said, I did do some lock profiling and latency tests. Contention was near-zero, but I only did 2-way testing. Under the preemptible kernel, while running dbench, scheduling latency improved 8.9%.

Robert Love

It's OK for regular files and directories, but I'm not sure about devices.

So I'd prefer to do it in two stages - shift BKL into ->llseek() and then see where it can be dropped/replaced with ->i_sem.

     > So I'd prefer to do it in two stages - shift BKL into
     > ->llseek() and then see where it can be dropped/replaced with
     > ->i_sem.

Seconded. There are several filesystems out there for which i_sem does nothing to protect inode->i_size.

Cheers,
Trond

Then the first patch is the way to go. We know generic_file_llseek is safe and perhaps a few other of the llseek methods. The remaining can explicitly grab the bkl on their own, as Al suggested.

Robert Love

Luckily, apache on its own doesn't seem to use lseek() when sending the file - it seems to be an open, mmap, write. (apache 1.3.22)

However, php with apache does do an lseek on the target script. Now remember the /. effect... You'll be accessing the same file from several apache or php processes.

Russell King ([email protected])                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

A great idea, I wonder why someone didnt think of it before?

http://banyan.dlut.edu.cn/news/112801/0186.html

Wow someone did! And the patch basically matches yours including whitespace.

Robert _please_ attribute your sources more carefully.

Anton

I've been informed Anton Blanchard did this same thing back in November:

	http://banyan.dlut.edu.cn/news/112801/0186.html

So credit should go to him.

Robert Love