AIM7 40% regression with 2.6.26-rc1

Comparing with kernel 2.6.25, AIM7 (use tmpfs) has more than 40% with 2.6.26-rc1 on my 8-core stoakley, 16-core tigerton, and Itanium Montecito. Bisect located below patch.

64ac24e738823161693bf791f87adc802cf529ff is first bad commit commit 64ac24e738823161693bf791f87adc802cf529ff

Author: Matthew Wilcox <[email protected]>
Date:   Fri Mar 7 21:55:58 2008 -0500

Generic semaphore implementation

After I manually reverted the patch against 2.6.26-rc1 while fixing lots of conflictions/errors, aim7 regression became less than 2%.

-yanmin

40%?! That's shocking. Can you tell which semaphore was heavily contended? I have a horrible feeling that it's the BKL.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

hm, which exact semaphore would that be due to?

My first blind guess would be the BKL - there's not much other semaphore use left in the core kernel otherwise that would affect AIM7 normally. The VFS still makes frequent use of the BKL and AIM7 is very VFS intense. Getting rid of that BKL use from the VFS might be useful to performance anyway.

Could you try to check that it's indeed the BKL?

Easiest way to check it would be to run AIM7 it on sched-devel.git/latest and do scheduler tracing via:

http://people.redhat.com/mingo/sched-devel.git/readme-tracer.txt

by doing:

echo stacktrace > /debug/tracing/iter_ctl

you could get exact backtraces of all scheduling points in the trace. If the BKL's down() shows up in those traces then it's definitely the BKL that causes this. The backtraces will also tell us exactly which BKL use is the most frequent one.

To keep tracing overhead low on SMP i'd also suggest to only trace a single CPU, via:

echo 1 > /debug/tracing/tracing_cpumask

Ingo

That's slightly slanderous to the VFS ;-) The BKL really isn't used that much any more. So little that I've gone through and produced a list of places it's used:

fs/block_dev.c opening and closing a block device. Unlikely to be
provoked by AIM7.
fs/char_dev.c chrdev_open. Unlikely to be provoked by AIM7.
fs/compat.c mount. Unlikely to be provoked by AIM7.
fs/compat_ioctl.c held around calls to ioctl translator.
fs/exec.c coredump. If this is a contention problem ...
fs/fcntl.c held around call to ->fasync.
fs/ioctl.c held around f_op ->ioctl call (tmpfs doesn't have
ioctl). ditto bmap. there's fasync, as previously mentioned.
fs/locks.c hellhole. I hope AIM7 doesn't use locks.
fs/namespace.c mount, umount. Unlikely to be provoked by AIM7.
fs/read_write.c llseek. tmpfs uses the unlocked version.
fs/super.c shtdown, remount. Unlikely to be provoked by AIM7.

So the only likely things I can see are:

- file locks
- fasync

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

I've wanted to fix file locks for a while. Here's a first attempt. It was done quickly, so I concede that it may well have bugs in it. I found (and fixed) one with LTP.

It takes *no account* of nfsd, nor remote filesystems. We need to have a serious discussion about their requirements.

index 663c069..cb09765 100644
@@ -140,6 +140,8 @@ int lease_break_time = 45;
 #define for_each_lock(inode, lockp) \
 	for (lockp = &inode->i_flock; *lockp != NULL; lockp = &(*lockp)->fl_next)
 
+static DEFINE_SPINLOCK(file_lock_lock);
+
 static LIST_HEAD(file_lock_list);
 static LIST_HEAD(blocked_list);
 

@@ -510,9 +512,9 @@ static void __locks_delete_block(struct file_lock *waiter)
  */
 static void locks_delete_block(struct file_lock *waiter)
 {
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	__locks_delete_block(waiter);
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 }
 
 /* Insert waiter into blocker's block list.

@@ -649,7 +651,7 @@ posix_test_lock(struct file *filp, struct file_lock *fl)
 {
 	struct file_lock *cfl;
 
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	for (cfl = filp->f_path.dentry->d_inode->i_flock; cfl; cfl = cfl->fl_next) {
 		if (!IS_POSIX(cfl))
 			continue;

@@ -662,7 +664,7 @@ posix_test_lock(struct file *filp, struct file_lock *fl)
 			fl->fl_pid = pid_vnr(cfl->fl_nspid);
 	} else
 		fl->fl_type = F_UNLCK;
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 	return;
 }
 EXPORT_SYMBOL(posix_test_lock);

@@ -735,18 +737,21 @@ static int flock_lock_file(struct file *filp, struct file_lock *request)
 	int error = 0;
 	int found = 0;
 
-	lock_kernel();
-	if (request->fl_flags & FL_ACCESS)
+	if (request->fl_flags & FL_ACCESS) {
+		spin_lock(&file_lock_lock);
 		goto find_conflict;
+	}
 
 	if (request->fl_type != F_UNLCK) {
 		error = -ENOMEM;
+		
 		new_fl = locks_alloc_lock();
 		if (new_fl == NULL)
-			goto out;
+			goto out_unlocked;
 		error = 0;
 	}
 
+	spin_lock(&file_lock_lock);
 	for_each_lock(inode, before) {
 		struct file_lock *fl = *before;
 		if (IS_POSIX(fl))

@@ -772,10 +777,13 @@ static int flock_lock_file(struct file *filp, struct file_lock *request)
 	 * If a higher-priority process was blocked on the old file lock,
 	 * give it the opportunity to lock the file.
 	 */
-	if (found)
+	if (found) {
+		spin_unlock(&file_lock_lock);
 		cond_resched();
+		spin_lock(&file_lock_lock);
+	}
 
-find_conflict:
+ find_conflict:
 	for_each_lock(inode, before) {
 		struct file_lock *fl = *before;
 		if (IS_POSIX(fl))

@@ -796,8 +804,9 @@ find_conflict:
 	new_fl = NULL;
 	error = 0;
 
-out:
-	unlock_kernel();
+ out:
+	spin_unlock(&file_lock_lock);
+ out_unlocked:
 	if (new_fl)
 		locks_free_lock(new_fl);
 	return error;

@@ -826,7 +835,7 @@ static int __posix_lock_file(struct inode *inode, struct file_lock *request, str
 		new_fl2 = locks_alloc_lock();
 	}
 
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	if (request->fl_type != F_UNLCK) {
 		for_each_lock(inode, before) {
 			fl = *before;

@@ -994,7 +1003,7 @@ static int __posix_lock_file(struct inode *inode, struct file_lock *request, str
 		locks_wake_up_blocks(left);
 	}
  out:
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 	/*
 	 * Free any unused locks.
 	 */

@@ -1069,14 +1078,14 @@ int locks_mandatory_locked(struct inode *inode)
 	/*
 	 * Search the lock list for this inode for any POSIX locks.
 	 */
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
 		if (!IS_POSIX(fl))
 			continue;
 		if (fl->fl_owner != owner)
 			break;
 	}
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 	return fl ? -EAGAIN : 0;
 }
 

@@ -1190,7 +1199,7 @@ int __break_lease(struct inode *inode, unsigned int mode)
 
 	new_fl = lease_alloc(NULL, mode & FMODE_WRITE ? F_WRLCK : F_RDLCK);
 
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 
 	time_out_leases(inode);
 

@@ -1251,8 +1260,10 @@ restart:
 			break_time++;
 	}
 	locks_insert_block(flock, new_fl);
+	spin_unlock(&file_lock_lock);
 	error = wait_event_interruptible_timeout(new_fl->fl_wait,
 						!new_fl->fl_next, break_time);
+	spin_lock(&file_lock_lock);
 	__locks_delete_block(new_fl);
 	if (error >= 0) {
 		if (error == 0)

@@ -1266,8 +1277,8 @@ restart:
 		error = 0;
 	}
 
-out:
-	unlock_kernel();
+ out:
+	spin_unlock(&file_lock_lock);
 	if (!IS_ERR(new_fl))
 		locks_free_lock(new_fl);
 	return error;

@@ -1323,7 +1334,7 @@ int fcntl_getlease(struct file *filp)
 	struct file_lock *fl;
 	int type = F_UNLCK;
 
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	time_out_leases(filp->f_path.dentry->d_inode);
 	for (fl = filp->f_path.dentry->d_inode->i_flock; fl && IS_LEASE(fl);
 			fl = fl->fl_next) {

@@ -1332,7 +1343,7 @@ int fcntl_getlease(struct file *filp)
 			break;
 		}
 	}
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 	return type;
 }
 

@@ -1363,6 +1374,7 @@ int generic_setlease(struct file *filp, long arg, struct file_lock **flp)
 	if (error)
 		return error;
 
+	spin_lock(&file_lock_lock);
 	time_out_leases(inode);
 
 	BUG_ON(!(*flp)->fl_lmops->fl_break);

@@ -1370,10 +1382,11 @@ int generic_setlease(struct file *filp, long arg, struct file_lock **flp)
 	lease = *flp;
 
 	if (arg != F_UNLCK) {
+		spin_unlock(&file_lock_lock);
 		error = -ENOMEM;
 		new_fl = locks_alloc_lock();
 		if (new_fl == NULL)
-			goto out;
+			goto out_unlocked;
 
 		error = -EAGAIN;
 		if ((arg == F_RDLCK) && (atomic_read(&inode->i_writecount) > 0))

@@ -1382,6 +1395,7 @@ int generic_setlease(struct file *filp, long arg, struct file_lock **flp)
 		    && ((atomic_read(&dentry->d_count) > 1)
 			|| (atomic_read(&inode->i_count) > 1)))
 			goto out;
+		spin_lock(&file_lock_lock);
 	}
 
 	/*

@@ -1429,11 +1443,14 @@ int generic_setlease(struct file *filp, long arg, struct file_lock **flp)
 
 	locks_copy_lock(new_fl, lease);
 	locks_insert_lock(before, new_fl);
+	spin_unlock(&file_lock_lock);
 
 	*flp = new_fl;
 	return 0;
 
-out:
+ out:
+	spin_unlock(&file_lock_lock);
+ out_unlocked:
 	if (new_fl != NULL)
 		locks_free_lock(new_fl);
 	return error;

@@ -1471,12 +1488,10 @@ int vfs_setlease(struct file *filp, long arg, struct file_lock **lease)
 {
 	int error;
 
-	lock_kernel();
 	if (filp->f_op && filp->f_op->setlease)
 		error = filp->f_op->setlease(filp, arg, lease);
 	else
 		error = generic_setlease(filp, arg, lease);
-	unlock_kernel();
 
 	return error;
 }

@@ -1503,12 +1518,11 @@ int fcntl_setlease(unsigned int fd, struct file *filp, long arg)
 	if (error)
 		return error;
 
-	lock_kernel();
-
 	error = vfs_setlease(filp, arg, &flp);
 	if (error || arg == F_UNLCK)
-		goto out_unlock;
+		return error;
 
+	lock_kernel();
 	error = fasync_helper(fd, filp, 1, &flp->fl_fasync);
 	if (error < 0) {
 		/* remove lease just inserted by setlease */

@@ -1519,7 +1533,7 @@ int fcntl_setlease(unsigned int fd, struct file *filp, long arg)
 	}
 
 	error = __f_setown(filp, task_pid(current), PIDTYPE_PID, 0);
-out_unlock:
+ out_unlock:
 	unlock_kernel();
 	return error;
 }

@@ -2024,7 +2038,7 @@ void locks_remove_flock(struct file *filp)
 			fl.fl_ops->fl_release_private(&fl);
 	}
 
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	before = &inode->i_flock;
 
 	while ((fl = *before) != NULL) {

@@ -2042,7 +2056,7 @@ void locks_remove_flock(struct file *filp)
  		}
 		before = &fl->fl_next;
 	}
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 }
 
 /**

@@ -2057,12 +2071,12 @@ posix_unblock_lock(struct file *filp, struct file_lock *waiter)
 {
 	int status = 0;
 
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	if (waiter->fl_next)
 		__locks_delete_block(waiter);
 	else
 		status = -ENOENT;
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 	return status;
 }
 

@@ -2175,7 +2189,7 @@ static int locks_show(struct seq_file *f, void *v)
 
 static void *locks_start(struct seq_file *f, loff_t *pos)
 {
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	f->private = (void *)1;
 	return seq_list_start(&file_lock_list, *pos);
 }

@@ -2187,7 +2201,7 @@ static void *locks_next(struct seq_file *f, void *v, loff_t *pos)
 
 static void locks_stop(struct seq_file *f, void *v)
 {
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 }
 
 struct seq_operations locks_seq_operations = {

@@ -2215,7 +2229,7 @@ int lock_may_read(struct inode *inode, loff_t start, unsigned long len)
 {
 	struct file_lock *fl;
 	int result = 1;
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
 		if (IS_POSIX(fl)) {
 			if (fl->fl_type == F_RDLCK)

@@ -2232,7 +2246,7 @@ int lock_may_read(struct inode *inode, loff_t start, unsigned long len)
 		result = 0;
 		break;
 	}
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 	return result;
 }
 

@@ -2255,7 +2269,7 @@ int lock_may_write(struct inode *inode, loff_t start, unsigned long len)
 {
 	struct file_lock *fl;
 	int result = 1;
-	lock_kernel();
+	spin_lock(&file_lock_lock);
 	for (fl = inode->i_flock; fl != NULL; fl = fl->fl_next) {
 		if (IS_POSIX(fl)) {
 			if ((fl->fl_end < start) || (fl->fl_start > (start + len)))

@@ -2270,7 +2284,7 @@ int lock_may_write(struct inode *inode, loff_t start, unsigned long len)
 		result = 0;
 		break;
 	}
-	unlock_kernel();
+	spin_unlock(&file_lock_lock);
 	return result;
 }
 

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Hmm. Wouldn't it be nicer to make the lock be a per-inode thing? Or is there some user that doesn't have the inode info, or does anything that might cross inode boundaries?

This does seem to drop all locking around the "setlease()" calls down to the filesystem, which worries me. That said, we clearly do need to do this. Probably should have done it a long time ago.

Also, why do people do this:

Hmm?

Linus

/proc/locks and deadlock detection both cross inode boundaries (and even filesystem boundaries). The BKL-removal brigade tried this back in 2.4 and the locking ended up scaling worse than just plonking a single spinlock around the whole thing.

The only filesystems that are going to have their own setlease methods will be remote ones (nfs, smbfs, etc). They're going to need to sleep while the server responds to them. So holding a spinlock while we call them is impolite at best.

So that find_conflict doesn't end up in the first column, which causes diff to treat it as a function name for the purposes of the @@ lines.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Please can we just fix the tools not mangle the kernel to work around silly bugs ?

The people who control the tools refuse to fix them.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

That would be their problem. We should refuse to mash the kernel up because they aren't doing their job. If need be someone can fork a private git-patch.

That's just plain bullocks.

First off, that "@@" line thing in diffs is not important enough to screw up the source code for. Ever. It's just a small hint to make it somewhat easier to see more context for humans.

Second, it's not even that bad to show the last label there, rather than the function name.

Third, you seem to be a git user, so if you actually really care that much about the @@ line, then git actually lets you set your very own pattern for those things.

In fact, you can even do it on a per-file basis based on things like filename rules (ie you can have different patterns for what to trigger on for a *.c file and for a *.S file, since in a *.S file the 'name:' thing _is_ the right pattern).

So not only are you making idiotic changes just for irrelevant tool usage, you're also apparently lying about people "refusing to fix" things as an excuse.

You can play with it. It's documented in gitattributes (see "Defining a custom hunk header"), and the default one is just the same one that GNU diff uses for "-p". I think.

You can add something like this to your ~/.gitconfig:

	[diff "default"]
		funcname=^[a-zA-Z_$].*(.*$

to only trigger the funcname pattern on a line that starts with a valid C identifier hing, and contains a '('.

And you can just override the default like the above (that way you don't have to specify attributes), but if you want to do things differently for *.c files than from *.S files, you can edit your .git/info/attributes file and make it contain something like

	*.S	diff=assembler
	*.c	diff=C

and now you can make your ~/.gitconfig actually show them differently, ie something like

	[diff "C"]
		funcname=^[a-zA-Z_$].*(.*$

	[diff "assembler"]
		funcname=^[a-zA-Z_$].*:

etc.

Of course, there is a real cost to this, but it's cheap enough in practice that you'll never notice.

Linus

Ok, no worries. Just as long as I know why it's a single lock. Looks ok to me, apart from the need for testing (and talking to NFS etc people).

Linus

The deadlock detection crosses inode boundaries.

--b.

Do we actually know that the locks code is implicated in this regression?

I'd initially thought "lseek" but afaict tmpfs doesn't hit default_llseek() or remote_llseek().

tmpfs tends to do weird stuff - it would be interesting to know if the regression is also present on ramfs or ext2/ext3/xfs/etc.

It would be interesting to see if the context switch rate has increased.

Finally: how come we regressed by swapping the semaphore implementation anyway? We went from one sleeping lock implementation to another - I'd have expected performance to be pretty much the same.

<looks at the implementation>

down(), down_interruptible() and down_try() should use spin_lock_irq(), not irqsave.

up() seems to be doing wake-one, FIFO which is nice. Did the implementation which we just removed also do that? Was it perhaps accidentally doing LIFO or something like that?

Not yet. We don't even know it's the BKL. It's just my best guess. We're waiting for the original reporter to run some tests Ingo pointed him at.

Correct.

We talked about this ... the BKL actually requires that you be able to acquire it with interrupts disabled. Maybe we should make lock_kernel do this:

	if (likely(!depth)) {
		unsigned long flags;
		local_save_flags(flags);
		down();
		local_irq_restore(flags);
	}

But tweaking down() is not worth it -- we should be eliminating users of both the BKL and semaphores instead.

That's a question for someone who knows x86 assembler, I think.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

hm, where does it require it, besides the early bootup code? (which should just be fixed)

down_trylock() is OK as irqsave/irqrestore for legacy reasons, but that is fundamentally atomic anyway.

the assembly is mostly just for the fastpath - and a 40% regression cannot be about fastpath differences. In the old code the scheduling happens in lib/semaphore-sleeper.c, and from the looks of it it appears to be a proper FIFO as well. (plus this small wakeup weirdness it has)

i reviewed the new code in kernel/semaphore.c as well and can see nothing bad in it - it does proper wake-up, FIFO queueing, like the mutex code.

Ingo

Yeah, the early bootup code. The kernel does accidental lock_kernel()s in various places and if that renables interrupts then powerpc goeth crunch.

Matthew, that seemingly-unneeded irqsave in lib/semaphore.c is a prime site for /* one of these things */, no?

yes, trylock should be made irq-safe.

There's the weird wakeup in down() which I understood for about five minutes five years ago. Perhaps that accidentally sped something up. Oh well, more investigation needed..

I was just reviewing the code and I came across one of these:

/*
* Some notes on the implementation:
*
* The spinlock controls access to the other members of the semaphore.
* down_trylock() and up() can be called from interrupt context, so we
* have to disable interrupts when taking the lock. It turns out various
* parts of the kernel expect to be able to use down() on a semaphore in
* interrupt context when they know it will succeed, so we have to use
* irqsave variants for down(), down_interruptible() and down_killable()
* too.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

i just checked the old implementation on x86. It used lib/semaphore-sleepers.c which does one weird thing:

- __down() when it returns wakes up yet another task via

    wake_up_locked().

i.e. we'll always keep yet another task in flight. This can mask wakeup latencies especially when it takes time.

The patch (hack) below tries to emulate this weirdness - it 'kicks' another task as well and keeps it busy. Most of the time this just causes extra scheduling, but if AIM7 is _just_ saturating the number of CPUs, it might make a difference. Yanmin, does the patch below make any difference to the AIM7 results?

( it would be useful data to get a meaningful context switch trace from
the whole regressed workload, and compare it to a context switch trace with the revert added. )

Ingo

---
 kernel/semaphore.c |   10 ++++++++++
 1 file changed, 10 insertions(+)

Index: linux/kernel/semaphore.c
===================================================================
@@ -261,4 +261,14 @@ static noinline void __sched __up(struct
 	list_del(&waiter->list);
 	waiter->up = 1;
 	wake_up_process(waiter->task);
+
+	if (likely(list_empty(&sem->wait_list)))
+		return;
+	/*
+	 * Opportunistically wake up another task as well but do not
+	 * remove it from the list:
+	 */
+	waiter = list_first_entry(&sem->wait_list,
+				  struct semaphore_waiter, list);
+	wake_up_process(waiter->task);
 }

I tested it on my 8-core stoakley and the result is 12% worse than the one of pure 2.6.26-rc1.

-yanmin

down_trylock() is used in atomic code. See for example kernel/printk.c. So no, that one needs to be irqsafe.

Linus

If heavily contended, it could do this.

up() would increment sem->count and cal __up() which would call wake_up() down() would decrement sem->count.
The unlucky task woken by __up would lose the race and go back to sleep.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

It doesn' have to be heavily contended - if it's just hot and a bit lucky, it would potentially never schedule at all, because it would never take the spinlock and serialize the callers.

It doesn't even need "unfairness" to work that way. The old semaphore implementation was very much designed to be lock-free, and if you had one CPU doing a lock while another did an unlock, the *common* situation was that the unlock would succeed first, because the unlocker was also the person who had the spinlock exclusively in its cache!

The above may count as "lucky", but the hot-cache-line thing is a big deal. It likely "lucky" into something that isn't a 50:50 chance, but something that is quite possible to trigger consistently if you just have mostly short holders of the lock.

Which, btw, is probably true. The BKL is normally held for short times, and released (by that thread) for relatively much longer times. Which is when spinlocks tend to work the best, even when they are fair (because it's not so much a fairness issue, it's simply a cost-of-taking-the-lock issue!)

Linus

.. and don't get me wrong: the old semaphores (and the new mutexes) should also have this property when lucky: taking the lock is often a hot-path case.

And the spinlock+generic semaphore thing probably makes that "lucky" behavior be exponentially less likely, because now to hit the lucky case, rather than the hot path having just *one* access to the interesting cache line, it has basically something like 4 accesses (spinlock, count test, count decrement, spinunlock), in addition to various serializing instructions, so I suspect it quite often gets serialized simply because even the "fast path" is actually about ten times as long!

As a result, a slow "fast path" means that the thing gets saturated much more easily, and that in turn means that the "fast path" turns into a "slow path" more easily, which is how you end up in the scheduler rather than just taking the fast path.

This is why sleeping locks are more expensive in general: they have a *huge* cost from when they get contended. Hundreds of times higher than a spinlock. And the faster they are, the longer it takes for them to get contended under load. So slowing them down in the fast path is a double whammy, in that it shows their bad behaviour much earlier.

And the generic semaphores really are slower than the old optimized ones in that fast path. By a *big* amount.

Which is why I'm 100% convinced it's not even worth saving the old code. It needs to use mutexes, or spinlocks. I bet it has *nothing* to do with "slow path" other than the fact that it gets to that slow path much more these days.

Linus

Stupid question: why doesn't lock_kernel() use a mutex?

(stupid answer: it'll trigger might_sleep() checks when we do it early in boot with irqs disabled, but we can fix that)

(And __might_sleep()'s system_state check might even save us from that)

Of course, we shouldn't change anything until we've worked out why the new semaphores got slower.

Not stupid.

The only reason some code didn't get turned over to mutexes was literally that they didn't want the debugging because they were doing intentionally bad things.

I think the BKL is one of them (the console semaphore was another, iirc).

Linus

i think your theory should be easy to test: Yanmin, could you turn on CONFIG_MUTEX_DEBUG=y and check by how much AIM7 regresses?

Because in the CONFIG_MUTEX_DEBUG=y case the mutex debug code does exactly that: it doesnt use the single-instruction fastpath [it uses asm-generic/mutex-null.h] but always drops into the slowpath (to be able to access debug state). That debug code is about as expensive as the generic semaphore code's current fastpath. (perhaps even more expensive.)

There's far more normal mutex fastpath use during an AIM7 run than any BKL use. So if it's due to any direct fastpath overhead and the resulting widening of the window for the real slowdown, we should see a severe slowdown on AIM7 with CONFIG_MUTEX_DEBUG=y. Agreed?

Ingo

my own guesstimate about AIM7 performance impact resulting out of CONFIG_MUTEX_DEBUG=y: performance overhead will not be measurable, or will at most be in the sub-1% range. But i've been badly wrong before :)

Ingo

Not agreed.

The BKL is special because it is a *single* lock.

All the "normal" mutex code use fine-grained locking, so even if you slow down the fast path, that won't cause the same kind of fastpath->slowpath increase.

In order to see the fastpath->slowpath thing, you do need to have many threads hitting the same lock: ie the slowdown has to result in real contention.

Almost no mutexes have any potential for contention what-so-ever, except for things that very consciously try to hit it (multiple threads doing readdir and/or file creation on the *same* directory etc).

The BKL really is special.

Linus

Put another way: let's say that the "good fastpath" is basically a single locked instruction - ~12 cycles on AMD, ~35 Core 2. That's the no-bouncing, no-contention case.

Doing it with debugging (call overhead, spinlocks, local irq saving rtc) will probably easily triple it or more, but we're not changing anything else. There's no "downstream" effect: the behaviour itself doesn't change. It doesn't get more bouncing, it doesn't start sleeping.

But what happens if the lock has the *potential* for conflicts is different.

There, a "longish pause + fast lock + short average code sequece + fast unlock" is quite likely to stay uncontended for a fair amount of time, and while it will be much slower than the no-contention-at-all case (because you do get a pretty likely cacheline event at the "fast lock" part), with a fairly low number of CPU's and a long enough pause, you *also* easily get into a pattern where the thing that got the lock will likely also get to unlock without dropping the cacheline.

So far so good.

But that basically depends on the fact that "lock + work + unlock" is _much_ shorter than the "longish pause" in between, so that even if you have <n> CPU's all doing the same thing, their pauses between the locked section are still bigger than <n> times that short time.

Once that is no longer true, you now start to bounce both at the lock *and* the unlock, and now that whole sequence got likely ten times slower. *AND* because it now actually has real contention, it actually got even
worse: if the lock is a sleeping one, you get *another* order of magnitude just because you now started doing scheduling overhead too!

So the thing is, it just breaks down very badly. A spinlock that gets contention probably gets ten times slower due to bouncing the cacheline. A semaphore that gets contention probably gets a *hundred* times slower, or more.

And so my bet is that both the old and the new semaphores had the same bad break-down situation, but the new semaphores just are a lot easier to trigger it because they are at least three times costlier than the old ones, so you just hit the bad behaviour with much lower loads (or fewer number of CPU's).

But spinlocks really do behave much better when contended, because at least they don't get the even bigger hit of also hitting the scheduler. So the old semaphores would have behaved badly too *eventually*, they just needed a more extreme case to show that bad behavior.

Linus

ok, indeed my suggestion is wrong and this would not be a good comparison.

another idea: my trial-baloon patch should test your theory too, because the generic down_trylock() is still the 'fat' version, it does:

        spin_lock_irqsave(&sem->lock, flags);
        count = sem->count - 1;
        if (likely(count >= 0))
                sem->count = count;
        spin_unlock_irqrestore(&sem->lock, flags);

if there is a noticeable performance difference between your trial-ballon patch and mine, then the micro-cost of the BKL very much matters to this workload. Agreed about that?

but i'd be _hugely_ surprised about it. The tty code's BKL use should i think only happen when a task exits and releases the tty - and a task exit - even if this is a threaded test (which AIM7 can be - not sure which exact parameters Yanmin used) - the costs of thread creation and thread exit are just not in the same ballpark as any BKL micro-costs. Dunno, maybe i overlooked some high-freq BKL user. (but any such site would have shown up before) Even assuming a widening of the critical path and some catastrophic domino effect (that does show up as increased scheduling) i've never seen a 40% drop like this.

this regression, to me, has "different scheduling behavior" written all over it - but that's just an impression. I'm not going to bet against you though ;-)

Ingo

I agree that your trial-balloon should likely get rid of the big regression, since it avoids the scheduler.

So with your patch, lock_kernel() ends up being just a rather expensive spinlock. And yes, I'd expect that it should get rid of the 40% cost, because while it makes lock_kernel() more expensive than a spinlock and you might end up having a few more cacheline bounces on the lock due to that, that's still the "small" expense compared to going through the whole scheduler on conflicts.

So I'd expect that realistically the performance difference between your version and just plain spinlocks shouldn't be *that* big. I'd expect it to be visible, but in the (low) single-digit percentage range rather than in any 40% range. That's just a guess.

Linus

third attempt - the patch below ontop of v2.6.25 should be quite similar fastpath atomic overhead to what generic semaphores do? So if Yanmin tests this patch ontop of v2.6.25, we should see the direct fastpath overhead - without any changes to the semaphore wakeup/scheduling logic otherwise.

[ this patch should in fact be a bit worse, because there's two more
atomics in the fastpath - the fastpath atomics of the old semaphore code. ]

Ingo

------------------>
Subject: v2.6.25 BKL: add atomic overhead
From: Ingo Molnar <[email protected]>
Date: Wed May 07 20:09:13 CEST 2008

---
 lib/kernel_lock.c |   13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

Index: linux-2.6.25/lib/kernel_lock.c
===================================================================
@@ -24,6 +24,7 @@
  * Don't use in new code.
  */
 static DECLARE_MUTEX(kernel_sem);
+static DEFINE_SPINLOCK(global_lock);
 
 /*
  * Re-acquire the kernel semaphore.

@@ -47,6 +48,9 @@ int __lockfunc __reacquire_kernel_lock(v
 
 	down(&kernel_sem);
 
+	spin_lock(&global_lock);
+	spin_unlock(&global_lock);
+
 	preempt_disable();
 	task->lock_depth = saved_lock_depth;
 

@@ -55,6 +59,9 @@ int __lockfunc __reacquire_kernel_lock(v
 
 void __lockfunc __release_kernel_lock(void)
 {
+	spin_lock(&global_lock);
+	spin_unlock(&global_lock);
+
 	up(&kernel_sem);
 }
 

@@ -66,12 +73,16 @@ void __lockfunc lock_kernel(void)
 	struct task_struct *task = current;
 	int depth = task->lock_depth + 1;
 
-	if (likely(!depth))
+	if (likely(!depth)) {
 		/*
 		 * No recursion worries - we set up lock_depth _after_
 		 */
 		down(&kernel_sem);
 
+		spin_lock(&global_lock);
+		spin_unlock(&global_lock);
+	}
+
 	task->lock_depth = depth;
 }
 

Well, it doesn't have the irq stuff, which is also pretty costly. Also, it doesn't nest the accesses the same way (with the counts being *inside* the spinlock and serialized against each other), so I'm not 100% sure you'd get the same behaviour.

But yes, it certainly has the potential to show the same slowdown. But it's not a very good patch, since not showing it doesn't really prove much.

Linus

ok, the one below does irq ops and the counter behavior - and because the critical section also has the old-semaphore atomics i think this should definitely be a more expensive fastpath than what the new generic code introduces. So if this patch produces a 40% AIM7 slowdown on v2.6.25 it's the fastpath overhead (and its effects on slowpath probability) that makes the difference.

Ingo

------------------->
Subject: add BKL atomic overhead
From: Ingo Molnar <[email protected]>
Date: Wed May 07 20:09:13 CEST 2008

---
 lib/kernel_lock.c |   18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

Index: linux-2.6.25/lib/kernel_lock.c
===================================================================
@@ -24,6 +24,8 @@
  * Don't use in new code.
  */
 static DECLARE_MUTEX(kernel_sem);
+static int global_count;
+static DEFINE_SPINLOCK(global_lock);
 
 /*
  * Re-acquire the kernel semaphore.

@@ -39,6 +41,7 @@ int __lockfunc __reacquire_kernel_lock(v
 {
 	struct task_struct *task = current;
 	int saved_lock_depth = task->lock_depth;
+	unsigned long flags;
 
 	BUG_ON(saved_lock_depth < 0);
 

@@ -47,6 +50,10 @@ int __lockfunc __reacquire_kernel_lock(v
 
 	down(&kernel_sem);
 
+	spin_lock_irqsave(&global_lock, flags);
+	global_count++;
+	spin_unlock_irqrestore(&global_lock, flags);
+
 	preempt_disable();
 	task->lock_depth = saved_lock_depth;
 

@@ -55,6 +62,10 @@ int __lockfunc __reacquire_kernel_lock(v
 
 void __lockfunc __release_kernel_lock(void)
 {
+	spin_lock_irqsave(&global_lock, flags);
+	global_count--;
+	spin_unlock_irqrestore(&global_lock, flags);
+
 	up(&kernel_sem);
 }
 

@@ -66,12 +77,17 @@ void __lockfunc lock_kernel(void)
 	struct task_struct *task = current;
 	int depth = task->lock_depth + 1;
 
-	if (likely(!depth))
+	if (likely(!depth)) {
 		/*
 		 * No recursion worries - we set up lock_depth _after_
 		 */
 		down(&kernel_sem);
 
+		spin_lock_irqsave(&global_lock, flags);
+		global_count++;
+		spin_unlock_irqrestore(&global_lock, flags);
+	}
+
 	task->lock_depth = depth;
 }
 

No it doesn't. The counter isn't used for any actual *testing*, so the locking around it and the serialization of it has absolutely no impact on the scheduling behaviour!

Since the big slowdown was clearly accompanied by sleeping behaviour (the processes who didn't get the lock end up sleeping!), that is a *big* part of the slowdown.

Is it possible that your patch gets similar behaviour? Absolutely. But you're missing the whole point here. Anybody can make code behave badly and perform worse. But if you want to just verify that it's about the sleeping behaviour and timings of the BKL, then you need to do exactly
that: emulate the sleeping behavior, not just the timings _outside_ of the sleeping behavior.

The thing is, we definitely are interested to see whether it's the BKL or some other semaphore that is the problem. But the best way to test that is to just try my patch that *guarantees* that the BKL doesn't have any semaphore behaviour AT ALL.

Could it be something else entirely? Yes. We know it's semaphore- related. We don't know for a fact that it's the BKL itself. There could be other semaphores that are that hot. It sounds unlikely, but quite frankly, regardless, I don't really see the point of your patches.

If Yanmin tries my patch, it is *guaranteed* to show something. It either shows that it's about the BKL (and that we absolutely have to do the BKL as something _else_ than a generic semaphore), or it shows that it's not about the BKL (and that _all_ the patches in this discussion are likely pointless).

In contrast, these "try to emulate bad behavior with the old known-ok semaphores" don't show anything AT ALL. We already know it's related to semaphores. And your patches aren't even guaranteed to show the same issue.

Linus

yeah, i was just trying to come up with patches to probe which one of the following two possibilities is actually the case:

- if the regression is due to the difference in scheduling behavior of new semaphores (different wakeup patterns, etc.), that's fixable in the new semaphore code => then the BKL code need not change.

- if the regression is due due to difference in the fastpath cost, then the new semaphores can probably not be improved (much of their appeal comes from them not being complex and not being in assembly) => then the BKL code needs to change to become cheaper [i.e. then we want your patch].

Ingo

One patch I'd still like Yanmin to test is my one from yesterday which removes the BKL from fs/locks.c.

http://marc.info/?l=linux-fsdevel&m=121009123427437&w=2

Obviously, it won't help if the problem isn't the BKL.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

And I'd personally rather have the network-fs people test and comment on that one ;)

I think that patch is worth looking at regardless, but the problems with that one aren't about performance, but about what the implications are for the filesystems (if any)...

Linus

Oh, well, they don't seem interested.

I can comment on some of the problems though.

fs/lockd/svcsubs.c, fs/nfs/delegation.c, fs/nfs/nfs4state.c, fs/nfsd/nfs4state.c all walk the i_flock list under the BKL. That won't protect them against locks.c any more. That's probably OK for fs/nfs/* since they'll be protected by their own data structures (Someone please check me on that?), but it's a bad idea for lockd/nfsd which are walking the lists for filesystems.

Are we going to have to export the file_lock_lock? I'd rather not. But we need to keep nfsd/lockd from tripping over locks.c.

Maybe we could come up with a decent API that lockd could use? It all seems a bit complex at the moment ... maybe lockd should be keeping track of the locks it owns anyway (since surely the posix deadlock detection code can't work properly if it's just passing all the locks through).

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Poor timing: we're all preparing for and travelling to the annual Connectathon interoperability testing conference which starts tomorrow.

Yes. fs/nfs is just reusing the code in fs/locks.c in order to track the locks it holds on the server. We could alternatively have coded a private lock implementation, but this seemed easier.

I'm not sure what you mean when you talk about lockd keeping track of the locks it owns. It has to keep those locks on inode->i_flock in order to make them visible to the host filesystem...

All lockd really needs, is the ability to find a lock it owns, and then obtain a copy. As for the nfs client, I suspect we can make do with something similar...

Cheers
Trond

So, assuming nfs is taking care of its own locking (I don't know if that's right), that leaves nlm_traverse_locks() and nlm_file_inuse() (both in fs/lockd/svcsubs.c) as the problem spots.

That sounds right.

--b.

I tested it on 8-core stoakley. aim7 result becomes 23% worse than the one of pure 2.6.26-rc1.

I replied this email in case you have many patches and I might test what you don't expect.

-yanmin

Ouch. That's really odd. The BKL->spinlock conversion looks really obvious, so it shouldn't be that noticeably slower.

The *one* difference is that the BKL has the whole "you can take it recursively and you can sleep without dropping it because the scheduler will drop it for you" thing. The spinlock conversion changed all of that into explicit "drop and retake" locks, and maybe that causes some issues.

But 23% worse? That sounds really odd/extreme.

Can you do a oprofile run or something?

Linus

I collected oprofile data. It looks not useful, as cpu idle is more than 50%.

samples  %        app name                 symbol name
270157    9.4450  multitask                add_long
266419    9.3143  multitask                add_int
238934    8.3534  multitask                add_double
187184    6.5442  multitask                mul_double
159448    5.5745  multitask                add_float
156312    5.4649  multitask                sieve
148081    5.1771  multitask                mul_float
127192    4.4468  multitask                add_short
80480     2.8137  multitask                string_rtns_1
57520     2.0110  vmlinux                  clear_page_c
53935     1.8856  multitask                div_long
48753     1.7045  libc-2.6.90.so           strncat
40825     1.4273  multitask                array_rtns
32807     1.1470  vmlinux                  __copy_user_nocache
31995     1.1186  multitask                div_int
31143     1.0888  multitask                div_float
28821     1.0076  multitask                div_double
26400     0.9230  vmlinux                  find_lock_page
26159     0.9146  vmlinux                  unmap_vmas
25249     0.8827  multitask                div_short
21509     0.7520  vmlinux                  native_read_tsc
18865     0.6595  vmlinux                  copy_user_generic_string
17993     0.6291  vmlinux                  copy_page_c
16367     0.5722  vmlinux                  system_call
14616     0.5110  libc-2.6.90.so           msort_with_tmp
13630     0.4765  vmlinux                  native_sched_clock
12952     0.4528  vmlinux                  copy_page_range
12817     0.4481  libc-2.6.90.so           strcat
12708     0.4443  vmlinux                  calc_delta_mine
12611     0.4409  libc-2.6.90.so           memset
11631     0.4066  bash                     (no symbols)
9991      0.3493  vmlinux                  update_curr
9328      0.3261  vmlinux                  unlock_page

Ahh, so it's probably still the BKL that is the problem, it's just not in the file locking code. The changes to fs/locks.c probably didn't matter all that much, and the additional regression was likely just some perturbation.

So it's probably fasync that AIM7 tests. Quite possibly coupled with /dev/tty etc. No file locking.

Linus

Thank you guys for the quick response. I ran into many regressions with 2.6.26-rc1, but just reported 2 of them because I located the patches. My machine is locating the root cause of 30% regression of sysbench+mysql(oltp readonly) now. Bisect is not so qucik because either kernel hang with testing or compilation fails.

Another specjbb2005 on Montvale is also under investigation.

Let me figure out how to clone your tree quickly as the network speed is very slow.

One clear weird behavior of aim7 is cpu idle is 0% with 2.6.25, but is more than 50% with 2.6.26-rc1. I have a patch to collect schedule info.

With my patch+gprof, I collected some data. Below was outputed by gprof.

index % time self children called name

                0.00    0.00       2/223305376     __down_write_nested [22749]
                0.00    0.00       3/223305376     journal_commit_transaction [10526]
                0.00    0.00       6/223305376     __down_read [22745]
                0.00    0.00       8/223305376     start_this_handle [19167]
                0.00    0.00      15/223305376     sys_pause [19808]
                0.00    0.00      17/223305376     log_wait_commit [11047]
                0.00    0.00      20/223305376     futex_wait [8122]
                0.00    0.00      64/223305376     pdflush [14335]
                0.00    0.00      71/223305376     do_get_write_access [5367]
                0.00    0.00      84/223305376     pipe_wait [14460]
                0.00    0.00     111/223305376     kjournald [10726]
                0.00    0.00     116/223305376     int_careful [9634]
                0.00    0.00     224/223305376     do_nanosleep [5418]
                0.00    0.00    1152/223305376     watchdog [22065]
                0.00    0.00    4087/223305376     worker_thread [22076]
                0.00    0.00    5003/223305376     __mutex_lock_killable_slowpath [23305]
                0.00    0.00    7810/223305376     ksoftirqd [10831]
                0.00    0.00    9389/223305376     __mutex_lock_slowpath [23306]
                0.00    0.00   10642/223305376     io_schedule [9813]
                0.00    0.00   23544/223305376     migration_thread [11495]
                0.00    0.00   35319/223305376     __cond_resched [22673]
                0.00    0.00   49065/223305376     retint_careful [16146]
                0.00    0.00  119757/223305376     sysret_careful [20074]
                0.00    0.00  151717/223305376     do_wait [5545]
                0.00    0.00  250221/223305376     do_exit [5356]
                0.00    0.00  303836/223305376     cpu_idle [4350]
                0.00    0.00 222333093/223305376     schedule_timeout [2]
[1]      0.0    0.00    0.00 223305376         schedule [1]
-----------------------------------------------
                0.00    0.00       2/222333093     io_schedule_timeout [9814]
                0.00    0.00       4/222333093     journal_stop [10588]
                0.00    0.00       8/222333093     cifs_oplock_thread [3760]
                0.00    0.00      14/222333093     do_sys_poll [5513]
                0.00    0.00      20/222333093     cifs_dnotify_thread [3733]
                0.00    0.00      32/222333093     read_chan [15648]
                0.00    0.00      47/222333093     wait_for_common [22017]
                0.00    0.00     658/222333093     do_select [5479]
                0.00    0.00    2000/222333093     inet_stream_connect [9324]
                0.00    0.00 222330308/222333093     __down [22577]
[2]      0.0    0.00    0.00 222333093         schedule_timeout [2]
                0.00    0.00 222333093/223305376     schedule [1]
-----------------------------------------------
                0.00    0.00       1/165565      flock_lock_file_wait [7735]
                0.00    0.00       7/165565      __posix_lock_file [23371]
                0.00    0.00     203/165565      de_put [4665]
                0.00    0.00     243/165565      opost [13633]
                0.00    0.00     333/165565      proc_root_readdir [14982]
                0.00    0.00     358/165565      write_chan [22090]
                0.00    0.00    6222/165565      proc_lookup_de [14908]
                0.00    0.00   32081/165565      sys_fcntl [19687]
                0.00    0.00   36045/165565      vfs_ioctl [21822]
                0.00    0.00   42025/165565      tty_release [20818]
                0.00    0.00   48047/165565      chrdev_open [3702]
[3]      0.0    0.00    0.00  165565         lock_kernel [3]
                0.00    0.00  152987/153190      down [4]
-----------------------------------------------
                0.00    0.00     203/153190      __reacquire_kernel_lock [23420]
                0.00    0.00  152987/153190      lock_kernel [3]
[4]      0.0    0.00    0.00  153190         down [4]
                0.00    0.00  153190/153190      __down [22577]
-----------------------------------------------
                0.00    0.00  153190/153190      down [4]
[22577   0.0    0.00    0.00  153190         __down [22577]
                0.00    0.00 222330308/222333093     schedule_timeout [2]

As system idle is more than 50%, so the schedule/schedule_timeout caller is important information.
1) lock_kernel causes most schedule/schedule_timeout;
2) When lock_kernel calls down, then __down, __down calls schedule_timeout for lots of times in a loop;
3) Caller of lcok_kernel are sys_fcntl/vfs_ioctl/tty_release/chrdev_open.

-yanmin

Really? Are you sure? That would imply that we keep on waking up tasks which then fail to acquire the lock. But the code pretty plainly doesn't do that.

Odd.

Still :(

Yes, totally based on the data.
The data means the calling times among functions. Initially , I just collected the caller of schedule and schedule_timeout. Then I found most schedule/schedule_timeout are called by __down which is called down. Then, I changes kernel to collect more functions' calling info.

If comparing the calling times of down, __down and schedule_timeout, we could find schedule_timeout is called by __down for 222330308, but __down is called only for 153190.

Yes. The data has an error difference, but the difference is small. My patch doesn't use lock to protect data in case it might introduces too much overhead.

that's one often-forgotten BKL site: about 1000 ioctls are still running under the BKL. The TTY one is hurting the most. To make sure it's only that BKL acquire/release that hurts, could you try the hack patch below, does it make any difference to performance?

but even if taking the BKL does hurt, it's quite unexpected to cause a 40% drop. Perhaps AIM7 has tons of threads that exit at once and all try to release their controlling terminal or something like that?

Ingo

------------------------>
Subject: DANGEROUS tty hack: no BKL
From: Ingo Molnar <[email protected]>
Date: Wed May 07 08:21:22 CEST 2008

---
 drivers/char/tty_io.c |    5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

Index: linux/drivers/char/tty_io.c
===================================================================
@@ -2844,9 +2844,10 @@ out:
 
 static int tty_release(struct inode *inode, struct file *filp)
 {
-	lock_kernel();
+	/* DANGEROUS - can crash your kernel! */
+//	lock_kernel();
 	release_dev(filp);
-	unlock_kernel();
+//	unlock_kernel();
 	return 0;
 }
 

although it's an unlocked_ioctl() now in 2.6.26, so all the BKL locking has been nicely pushed down to deep inside the tty code.

if you use a serial console you will need the updated patch below.

Ingo

---------------------->
Subject: no: tty bkl
From: Ingo Molnar <[email protected]>
Date: Wed May 07 08:21:22 CEST 2008

---
 drivers/char/tty_io.c        |    5 +++--
 drivers/serial/serial_core.c |    2 +-
 2 files changed, 4 insertions(+), 3 deletions(-)

Index: linux/drivers/char/tty_io.c
===================================================================
@@ -2844,9 +2844,10 @@ out:
 
 static int tty_release(struct inode *inode, struct file *filp)
 {
-	lock_kernel();
+	/* DANGEROUS - can crash your kernel! */
+//	lock_kernel();
 	release_dev(filp);
-	unlock_kernel();
+//	unlock_kernel();
 	return 0;
 }
 

Index: linux/drivers/serial/serial_core.c
===================================================================
@@ -1241,7 +1241,7 @@ static void uart_close(struct tty_struct
 	struct uart_state *state = tty->driver_data;
 	struct uart_port *port;
 
-	BUG_ON(!kernel_locked());
+//	BUG_ON(!kernel_locked());
 
 	if (!state || !state->port)
 		return;

I tested it on my 8-core stoakley. The result is 4% worse than the one of pure 2.6.26-rc1. Still not good.

I have an older patchkit that introduced unlocked_fnctl for some cases. It was briefly in mm but then dropped. Sounds like it is worth resurrecting?

tty_* is being taken care of by Alan.

chrdev_open is more work.

-Andi (who BTW never quite understood why BKL is a semaphore now and not a spinlock?)

Not sure what you're talking about here, Andi. The only lock_kernel in fcntl.c is around the call to ->fasync. And Yanmin's traces don't show fasync as being a culprit, just the paths in locks.c

See git commit 6478d8800b75253b2a934ddcb734e13ade023ad0

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

I was talking about fasync.

I am aware of that commit, thank you, but the comment was refering to that it came with about zero justification why it was done. For the left over BKL regions which are relatively short surely a spinlock would be better than a semaphore? So PREEMPT_BKL should have been removed, not !PREEMPT_BKL.

If that was done all these regressions would disappear I bet. That said of course it is still better to actually fix the lock_kernel()s, but shorter time just fixing lock_kernel again would be easier.

-Andi

I do agree.

I think turning the BKL into a semaphore was fine per se, but that was when semaphores were fast.

Considering the apparent AIM regressions, we really either need to revert the semaphore consolidation, or we need to fix the kernel lock. And by "fixing", I don't mean removing it - it will happen, but it almost certainly won't happen for 2.6.26.

The easiest approach would seem to just turn the BKL into a mutex instead, which should hopefully be about as optimized as the old semaphores.

But my preferred option would indeed be just turning it back into a spinlock - and screw latency and BKL preemption - and having the RT people who care deeply just work on removing the BKL in the long run.

Is BKL preemption worth it? Sounds very dubious. Sounds even more dubious when we now apparently have even more reason to aim for removing the BKL rather than trying to mess around with it.

Linus

It isn't as if the RT build can't use a different lock type to the default build.

We have some horrible long lasting BKL users left unfortunately.

Alan

Well, considering just *how* bad the new BKL apparently is, I think that's a separate issue. The semaphore implementation is simply not worth it. At a minimum, it should be a mutex.

Quite frankly, maybe we _need_ to have a bad BKL for those to ever get fixed. As it was, people worked on trying to make the BKL behave better, and it was a failure. Rather than spend the effort on trying to make it work better (at a horrible cost), why not just say "Hell no - if you have issues with it, you need to work with people to get rid of the BKL rather than cluge around it".

Linus

Put another way: if we had introduced the BKL-as-semaphore with a known 40% performance drop in AIM7, I would simply never ever have accepted the patch in the first place, regardless of _any_ excuses.

Performance is a feature too.

Now, just because the code is already merged should not be an excuse for it then being shown to be bad. It's not a valid excuse to say "but we already merged it, so we can't unmerge it". We sure as hell _can_ unmerge it.

Linus

Are there really that many long lived BKL holders? I have some doubts. Semaphore makes only sense when the critical region is at least many thousands of cycles to amortize the scheduling overhead.

Ok perhaps this needs some numbers to decide.

but that was

The semaphores should be still nearly as fast in theory, especially for the contended case.

Or figure out what made the semaphore consolidation slower? As Ingo pointed out earlier 40% is unlikely to be a fast path problem, but some algorithmic problem. Surely that is fixable (even for .26)?

Perhaps we were lucky it showed so easily, not in something tricky.

-Andi

Absolutely. Yanmin is apparently showing that each call to __down() results in 1,451 calls to schedule(). wtf?

I can't figure it out either. Unless schedule() is broken somehow ... but that should have shown up with semaphore-sleepers.c, shouldn't it?

One other difference between semaphore-sleepers and the new generic code is that in effect, semaphore-sleepers does a little bit of spinning before it sleeps. That is, if up() and down() are called more-or-less simultaneously, the increment of sem->count will happen before __down calls schedule(). How about something like this:

index 5c2942e..ef83f5a 100644
@@ -211,6 +211,7 @@ static inline int __sched __down_common(struct semaphore *sem, long state,
 	waiter.up = 0;
 
 	for (;;) {
+		int i;
 		if (state == TASK_INTERRUPTIBLE && signal_pending(task))
 			goto interrupted;
 		if (state == TASK_KILLABLE && fatal_signal_pending(task))

@@ -219,7 +220,15 @@ static inline int __sched __down_common(struct semaphore *sem, long state,
 			goto timed_out;
 		__set_task_state(task, state);
 		spin_unlock_irq(&sem->lock);
+
+		for (i = 0; i < 10; i++) {
+			if (waiter.up)
+				goto skip_schedule;
+			cpu_relax();
+		}
+
 		timeout = schedule_timeout(timeout);
+ skip_schedule:
 		spin_lock_irq(&sem->lock);
 		if (waiter.up)
 			return 0;

Maybe it'd be enough to test it once ... or maybe we should use spin_is_locked() ... Ingo?

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Here's a trial balloon patch to do that.

Yanmin - this is not well tested, but the code is fairly obvious, and it would be interesting to hear if this fixes the performance regression. Because if it doesn't, then it's not the BKL, or something totally different is going on.

Now, we should probably also test just converting the thing to a mutex, to see if that perhaps also fixes it.

Linus

---
 arch/mn10300/Kconfig    |   11 ----
 include/linux/hardirq.h |   18 ++++---
 kernel/sched.c          |   27 ++---------
 lib/kernel_lock.c       |  120 +++++++++++++++++++++++++++++++---------------
 4 files changed, 95 insertions(+), 81 deletions(-)

index 6a6409a..e856218 100644
@@ -186,17 +186,6 @@ config PREEMPT
 	  Say Y here if you are building a kernel for a desktop, embedded
 	  or real-time system.  Say N if you are unsure.
 
-config PREEMPT_BKL
-	bool "Preempt The Big Kernel Lock"
-	depends on PREEMPT
-	default y
-	help
-	  This option reduces the latency of the kernel by making the
-	  big kernel lock preemptible.
-
-	  Say Y here if you are building a kernel for a desktop system.
-	  Say N if you are unsure.
-
 config MN10300_CURRENT_IN_E2
 	bool "Hold current task address in E2 register"
 	default y

index 897f723..181006c 100644
@@ -72,6 +72,14 @@
 #define in_softirq()		(softirq_count())
 #define in_interrupt()		(irq_count())
 
+#if defined(CONFIG_PREEMPT)
+# define PREEMPT_INATOMIC_BASE kernel_locked()
+# define PREEMPT_CHECK_OFFSET 1
+#else
+# define PREEMPT_INATOMIC_BASE 0
+# define PREEMPT_CHECK_OFFSET 0
+#endif
+
 /*
  * Are we running in atomic context?  WARNING: this macro cannot
  * always detect atomic context; in particular, it cannot know about

@@ -79,17 +87,11 @@
  * used in the general case to determine whether sleeping is possible.
  * Do not use in_atomic() in driver code.
  */
-#define in_atomic()		((preempt_count() & ~PREEMPT_ACTIVE) != 0)
-
-#ifdef CONFIG_PREEMPT
-# define PREEMPT_CHECK_OFFSET 1
-#else
-# define PREEMPT_CHECK_OFFSET 0
-#endif
+#define in_atomic()	((preempt_count() & ~PREEMPT_ACTIVE) != PREEMPT_INATOMIC_BASE)
 
 /*
  * Check whether we were atomic before we did preempt_disable():
- * (used by the scheduler)
+ * (used by the scheduler, *after* releasing the kernel lock)
  */
 #define in_atomic_preempt_off() \
 		((preempt_count() & ~PREEMPT_ACTIVE) != PREEMPT_CHECK_OFFSET)

index 58fb8af..c51b656 100644
@@ -4567,8 +4567,6 @@ EXPORT_SYMBOL(schedule);
 asmlinkage void __sched preempt_schedule(void)
 {
 	struct thread_info *ti = current_thread_info();
-	struct task_struct *task = current;
-	int saved_lock_depth;
 
 	/*
 	 * If there is a non-zero preempt_count or interrupts are disabled,

@@ -4579,16 +4577,7 @@ asmlinkage void __sched preempt_schedule(void)
 
 	do {
 		add_preempt_count(PREEMPT_ACTIVE);
-
-		/*
-		 * We keep the big kernel semaphore locked, but we
-		 * clear ->lock_depth so that schedule() doesnt
-		 * auto-release the semaphore:
-		 */
-		saved_lock_depth = task->lock_depth;
-		task->lock_depth = -1;
 		schedule();
-		task->lock_depth = saved_lock_depth;
 		sub_preempt_count(PREEMPT_ACTIVE);
 
 		/*

@@ -4609,26 +4598,15 @@ EXPORT_SYMBOL(preempt_schedule);
 asmlinkage void __sched preempt_schedule_irq(void)
 {
 	struct thread_info *ti = current_thread_info();
-	struct task_struct *task = current;
-	int saved_lock_depth;
 
 	/* Catch callers which need to be fixed */
 	BUG_ON(ti->preempt_count || !irqs_disabled());
 
 	do {
 		add_preempt_count(PREEMPT_ACTIVE);
-
-		/*
-		 * We keep the big kernel semaphore locked, but we
-		 * clear ->lock_depth so that schedule() doesnt
-		 * auto-release the semaphore:
-		 */
-		saved_lock_depth = task->lock_depth;
-		task->lock_depth = -1;
 		local_irq_enable();
 		schedule();
 		local_irq_disable();
-		task->lock_depth = saved_lock_depth;
 		sub_preempt_count(PREEMPT_ACTIVE);
 
 		/*

@@ -5853,8 +5831,11 @@ void __cpuinit init_idle(struct task_struct *idle, int cpu)
 	spin_unlock_irqrestore(&rq->lock, flags);
 
 	/* Set the preempt count _outside_ the spinlocks! */
+#if defined(CONFIG_PREEMPT)
+	task_thread_info(idle)->preempt_count = (idle->lock_depth >= 0);
+#else
 	task_thread_info(idle)->preempt_count = 0;
-
+#endif
 	/*
 	 * The idle tasks have their own, simple scheduling class:
 	 */

here's a simpler trial baloon test-patch (well, hack) that is also reasonably well tested. It turns the BKL into a "spin-semaphore". If this resolves the performance problem then it's all due to the BKL's scheduling/preemption properties.

this approach is ugly (it's just a more expensive spinlock), but has an
advantage: the code logic is obviously correct, and it would also make it much easier later on to turn the BKL back into a sleeping lock again
- once the TTY code's BKL use is fixed. (i think Alan said it might happen in the next few months) The BKL is more expensive than a simple spinlock anyway.

Ingo

------------->
Subject: BKL: spin on acquire
From: Ingo Molnar <[email protected]>
Date: Wed May 07 19:05:40 CEST 2008

---
 lib/kernel_lock.c |    9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

Index: linux/lib/kernel_lock.c
===================================================================
@@ -46,7 +46,8 @@ int __lockfunc __reacquire_kernel_lock(v
 	task->lock_depth = -1;
 	preempt_enable_no_resched();
 
-	down(&kernel_sem);
+	while (down_trylock(&kernel_sem))
+		cpu_relax();
 
 	preempt_disable();
 	task->lock_depth = saved_lock_depth;

@@ -67,11 +68,13 @@ void __lockfunc lock_kernel(void)
 	struct task_struct *task = current;
 	int depth = task->lock_depth + 1;
 
-	if (likely(!depth))
+	if (likely(!depth)) {
 		/*
 		 * No recursion worries - we set up lock_depth _after_
 		 */
-		down(&kernel_sem);
+		while (down_trylock(&kernel_sem))
+			cpu_relax();
+	}
 
 	task->lock_depth = depth;
 }

Congratulations! The patch really fixes the regression completely! vmstat showed cpu idle is 0%, just like 2.6.25's.

Some config options in my .config file:

CONFIG_NR_CPUS=32
CONFIG_SCHED_SMT=y
CONFIG_SCHED_MC=y
# CONFIG_PREEMPT_NONE is not set
CONFIG_PREEMPT_VOLUNTARY=y
# CONFIG_PREEMPT is not set
CONFIG_X86_LOCAL_APIC=y
CONFIG_X86_IO_APIC=y

yanmin

Well, that shows that it was the BKL.

That said, "idle 0%" is easy when you spin. Do you also have actual performance numbers? I'd hope that not only do we use full CPU time, it's also at least as fast as the old semaphores were?

While I've been dissing sleeping locks (because their overhead is so high), at least in _theory_ they can get better behavior when not spinning. Now, that's not going to happen with the BKL, I'm 99.99% sure, but I'd still like to hear actual performance numbers too, just to be sure.

Anyway, at least the "was it the BKL or some other semaphore user" question is entirely off the table.

So we need to

- fix the BKL. My patch may be a good starting point, but there are alternatives:

(a) reinstate the old BKL code entirely

Quite frankly, I'd prefer not to. Not only did it have three totally different cases, some of them were apparently broken (ie BKL+regular preempt didn't cond_resched() right), and I just don't think it's worth maintaining three different versions, when distro's are going to pick one anyway. *We* should pick one, and maintain it.

(b) screw the special BKL preemption - it's a spinlock, we don't preempt other spinlocks, but at least fix BKL+preempt+cond_resched thing.

This would be "my patch + fixes" where at least one of the fixes is the known (apparently old) cond_preempt() bug.

(c) Try to keep the 2.6.25 code as closely as possible, but just switch over to mutexes instead.

I dunno. I was never all that enamoured with the BKL as a sleeping lock, so I'm biased against this one, but hey, it's just a personal bias.

- get rid of the BKL anyway, at least in anything that is noticeable.

Matthew's patch to file locking is probably worth doing as-is, simply because I haven't heard any better solutions. The BKL certainly can't be it, and whatever comes out of the NFSD discussion will almost certainly involve just making sure that those leases just use the new fs/locks.c lock.

This is also why I'd actually prefer the simplest possible (non-preempting) spinlock BKL. Because it means that we can get rid of all that "saved_lock_depth" crud (like my patch already did). We shouldn't aim for a clever BKL, we should aim for a BKL that nobody uses.

I'm certainly open to anything. Regardless, we should decide fairly soon, so that we have the choice made before -rc2 is out, and not drag this out, since regardless of the choice it needs to be tested and people comfy with it for the 2.6.26 release.

Linus

Yes. My conclusion is based on the actual number. cpu idle 0% is just a behavior it should be.

Yes.

For sure.

Thanks, that's all I wanted to verify.

I'll leave this overnight, and see if somebody has come up with some smart and wonderful patch. And if not, I think I'll apply mine as "known to fix a regression", and we can perhaps then improve on things further from there.

Linus

hey, i happen to have such a smart and wonderful patch =B-)

i reproduced the AIM7 workload and can confirm Yanmin's findings that -.26-rc1 regresses over .25 - by over 67% here.

Looking at the workload i found and fixed what i believe to be the real bug causing the AIM7 regression: it was inefficient wakeup / scheduling / locking behavior of the new generic semaphore code, causing suboptimal performance.

The problem comes from the following code. The new semaphore code does this on down():

        spin_lock_irqsave(&sem->lock, flags);
        if (likely(sem->count > 0))
                sem->count--;
        else
                __down(sem);
        spin_unlock_irqrestore(&sem->lock, flags);

and this on up():

        spin_lock_irqsave(&sem->lock, flags);
        if (likely(list_empty(&sem->wait_list)))
                sem->count++;
        else
                __up(sem);
        spin_unlock_irqrestore(&sem->lock, flags);

where __up() does:

        list_del(&waiter->list);
        waiter->up = 1;
        wake_up_process(waiter->task);

and where __down() does this in essence:

        list_add_tail(&waiter.list, &sem->wait_list);
        waiter.task = task;
        waiter.up = 0;
        for (;;) {
                [...]
                spin_unlock_irq(&sem->lock);
                timeout = schedule_timeout(timeout);
                spin_lock_irq(&sem->lock);
                if (waiter.up)
                        return 0;
        }

the fastpath looks good and obvious, but note the following property of the contended path: if there's a task on the ->wait_list, the up() of the current owner will "pass over" ownership to that waiting task, in a wake-one manner, via the waiter->up flag and by removing the waiter from the wait list.

That is all and fine in principle, but as implemented in kernel/semaphore.c it also creates a nasty, hidden source of contention!

The contention comes from the following property of the new semaphore
code: the new owner owns the semaphore exclusively, even if it is not running yet.

So if the old owner, even if just a few instructions later, does a down() [lock_kernel()] again, it will be blocked and will have to wait on the new owner to eventually be scheduled (possibly on another CPU)! Or if another other task gets to lock_kernel() sooner than the "new owner" scheduled, it will be blocked unnecessarily and for a very long time when there are 2000 tasks running.

I.e. the implementation of the new semaphores code does wake-one and lock ownership in a very restrictive way - it does not allow opportunistic re-locking of the lock at all and keeps the scheduler from picking task order intelligently.

This kind of scheduling, with 2000 AIM7 processes running, creates awful cross-scheduling between those 2000 tasks, causes reduced parallelism, a throttled runqueue length and a lot of idle time. With increasing number of CPUs it causes an exponentially worse behavior in AIM7, as the chance for a newly woken new-owner task to actually run anytime soon is less and less likely.

Note that it takes just a tiny bit of contention for the 'new-semaphore catastrophy' to happen: the wakeup latencies get added to whatever small contention there is, and quickly snowball out of control!

I believe Yanmin's findings and numbers support this analysis too.

The best fix for this problem is to use the same scheduling logic that the kernel/mutex.c code uses: keep the wake-one behavior (that is OK and wanted because we do not want to over-schedule), but also allow opportunistic locking of the lock even if a wakee is already "in flight".

The patch below implements this new logic. With this patch applied the AIM7 regression is largely fixed on my quad testbox:

  # v2.6.25 vanilla:
  ..................
  Tasks   Jobs/Min        JTI     Real    CPU     Jobs/sec/task
  2000    56096.4         91      207.5   789.7   0.4675
  2000    55894.4         94      208.2   792.7   0.4658

  # v2.6.26-rc1-166-gc0a1811 vanilla:
  ...................................
  Tasks   Jobs/Min        JTI     Real    CPU     Jobs/sec/task
  2000    33230.6         83      350.3   784.5   0.2769
  2000    31778.1         86      366.3   783.6   0.2648

  # v2.6.26-rc1-166-gc0a1811 + semaphore-speedup:
  ...............................................
  Tasks   Jobs/Min        JTI     Real    CPU     Jobs/sec/task
  2000    55707.1         92      209.0   795.6   0.4642
  2000    55704.4         96      209.0   796.0   0.4642

i.e. a 67% speedup. We are now back to within 1% of the v2.6.25 performance levels and have zero idle time during the test, as expected.

Btw., interactivity also improved dramatically with the fix - for example console-switching became almost instantaneous during this workload (which after all is running 2000 tasks at once!), without the patch it was stuck for a minute at times.

I also ran Linus's spinlock-BKL patch as well:

  # v2.6.26-rc1-166-gc0a1811 + Linus-BKL-spinlock-patch:
  ......................................................
  Tasks   Jobs/Min        JTI     Real    CPU     Jobs/sec/task
  2000    55889.0         92      208.3   793.3   0.4657
  2000    55891.7         96      208.3   793.3   0.4658

it is about 0.3% faster - but note that that is within the general noise levels of this test. I'd expect Linus's spinlock-BKL patch to give some small speedup because the BKL acquire times are short and 2000 tasks running all at once really increases the context-switching cost and most BKL contentions are within the cost of context-switching.

But i believe the better solution for that is to remove BKL use from all hotpaths, not to hide some of its costs by reintroducing it as a spinlock. Reintroducing the spinlock based BKL would have other disadvantages as well: it could reintroduce per-CPU-ness assumptions in BKL-using code and other complications as well. It's also not a very realistic workload - with 2000 tasks running the system was barely serviceable.

I'd much rather make BKL costs more apparent and more visible - but 50% regression was of course too much. But 0.3% for a 2000-tasks workload, which is near the noise level ... is acceptable i think - especially as this discussion has now reinvigorated the remove-the-BKL discussions and patches.

Linus, we can do your spinlock-BKL patch too if you feel strongly about it, but i'd rather not - we fought so hard for the preemptible BKL :-)

The spinlock-based-BKL patch only worked around the real problem i believe, because it eliminated the use of the suboptimal new semaphore
code: with spinlocks there's no scheduling at all, so the wakeup/locking bug of the new semaphore code did not apply. It was not about any fastpath overhead AFAICS. [we'd have seen that with the CONFIG_PREEMPT_BKL=y code as well, which has been the default setting since v2.6.8.]

There's another nice side-effect of this speedup patch, the new generic semaphore code got even smaller:

   text    data     bss     dec     hex filename
   1241       0       0    1241     4d9 semaphore.o.before
   1207       0       0    1207     4b7 semaphore.o.after

(because the waiter.up complication got removed.)

Longer-term we should look into using the mutex code for the generic semaphore code as well - but i's not easy due to legacies and it's outside of the scope of v2.6.26 and outside the scope of this patch as well.

Hm?

Ingo

---
 kernel/semaphore.c |   36 ++++++++++++++++--------------------
 1 file changed, 16 insertions(+), 20 deletions(-)

Index: linux/kernel/semaphore.c
===================================================================
@@ -54,10 +54,9 @@ void down(struct semaphore *sem)
 	unsigned long flags;
 
 	spin_lock_irqsave(&sem->lock, flags);
-	if (likely(sem->count > 0))
-		sem->count--;
-	else
+	if (unlikely(sem->count <= 0))
 		__down(sem);
+	sem->count--;
 	spin_unlock_irqrestore(&sem->lock, flags);
 }
 EXPORT_SYMBOL(down);

@@ -77,10 +76,10 @@ int down_interruptible(struct semaphore 
 	int result = 0;
 
 	spin_lock_irqsave(&sem->lock, flags);
-	if (likely(sem->count > 0))
-		sem->count--;
-	else
+	if (unlikely(sem->count <= 0))
 		result = __down_interruptible(sem);
+	if (!result)
+		sem->count--;
 	spin_unlock_irqrestore(&sem->lock, flags);
 
 	return result;

@@ -103,10 +102,10 @@ int down_killable(struct semaphore *sem)
 	int result = 0;
 
 	spin_lock_irqsave(&sem->lock, flags);
-	if (likely(sem->count > 0))
-		sem->count--;
-	else
+	if (unlikely(sem->count <= 0))
 		result = __down_killable(sem);
+	if (!result)
+		sem->count--;
 	spin_unlock_irqrestore(&sem->lock, flags);
 
 	return result;

@@ -157,10 +156,10 @@ int down_timeout(struct semaphore *sem, 
 	int result = 0;
 
 	spin_lock_irqsave(&sem->lock, flags);
-	if (likely(sem->count > 0))
-		sem->count--;
-	else
+	if (unlikely(sem->count <= 0))
 		result = __down_timeout(sem, jiffies);
+	if (!result)
+		sem->count--;
 	spin_unlock_irqrestore(&sem->lock, flags);
 
 	return result;

@@ -179,9 +178,8 @@ void up(struct semaphore *sem)
 	unsigned long flags;
 
 	spin_lock_irqsave(&sem->lock, flags);
-	if (likely(list_empty(&sem->wait_list)))
-		sem->count++;
-	else
+	sem->count++;
+	if (unlikely(!list_empty(&sem->wait_list)))
 		__up(sem);
 	spin_unlock_irqrestore(&sem->lock, flags);
 }

@@ -192,7 +190,6 @@ EXPORT_SYMBOL(up);
 struct semaphore_waiter {
 	struct list_head list;
 	struct task_struct *task;
-	int up;
 };
 
 /*

@@ -206,11 +203,11 @@ static inline int __sched __down_common(
 	struct task_struct *task = current;
 	struct semaphore_waiter waiter;
 
-	list_add_tail(&waiter.list, &sem->wait_list);
 	waiter.task = task;
-	waiter.up = 0;
 
 	for (;;) {
+		list_add_tail(&waiter.list, &sem->wait_list);
+
 		if (state == TASK_INTERRUPTIBLE && signal_pending(task))
 			goto interrupted;
 		if (state == TASK_KILLABLE && fatal_signal_pending(task))

@@ -221,7 +218,7 @@ static inline int __sched __down_common(
 		spin_unlock_irq(&sem->lock);
 		timeout = schedule_timeout(timeout);
 		spin_lock_irq(&sem->lock);
-		if (waiter.up)
+		if (sem->count > 0)
 			return 0;
 	}
 

@@ -259,6 +256,5 @@ static noinline void __sched __up(struct
 	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
 						struct semaphore_waiter, list);
 	list_del(&waiter->list);
-	waiter->up = 1;
 	wake_up_process(waiter->task);
 }

a second update patch, i've further simplified the semaphore wakeup
logic: there's no need for the wakeup to remove the task from the wait list. This will make them a slighly bit more fair, but more importantly, this closes a race in my first patch for the unlikely case of a signal (or a timeout) and an unlock coming in at the same time and the task not getting removed from the wait-list.

( my performance testing with 2000 AIM7 tasks on a quad never hit that
race but x86.git QA actually triggered it after about 30 random kernel bootups and it caused a nasty crash and lockup. )

Ingo

---------------->
Subject: sem: simplify queue management
From: Ingo Molnar <[email protected]>
Date: Tue May 06 19:32:42 CEST 2008

kernel/semaphore.o:

   text	   data	    bss	    dec	    hex	filename
   1040	      0	      0	   1040	    410	semaphore.o.before
    975	      0	      0	    975	    3cf	semaphore.o.after

---
 kernel/semaphore.c |   32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)

Index: linux/kernel/semaphore.c
===================================================================
@@ -202,33 +202,34 @@ static inline int __sched __down_common(
 {
 	struct task_struct *task = current;
 	struct semaphore_waiter waiter;
+	int ret = 0;
 
 	waiter.task = task;
+	list_add_tail(&waiter.list, &sem->wait_list);
 
 	for (;;) {
-		list_add_tail(&waiter.list, &sem->wait_list);
-
-		if (state == TASK_INTERRUPTIBLE && signal_pending(task))
-			goto interrupted;
-		if (state == TASK_KILLABLE && fatal_signal_pending(task))
-			goto interrupted;
-		if (timeout <= 0)
-			goto timed_out;
+		if (state == TASK_INTERRUPTIBLE && signal_pending(task)) {
+			ret = -EINTR;
+			break;
+		}
+		if (state == TASK_KILLABLE && fatal_signal_pending(task)) {
+			ret = -EINTR;
+			break;
+		}
+		if (timeout <= 0) {
+			ret = -ETIME;
+			break;
+		}
 		__set_task_state(task, state);
 		spin_unlock_irq(&sem->lock);
 		timeout = schedule_timeout(timeout);
 		spin_lock_irq(&sem->lock);
 		if (sem->count > 0)
-			return 0;
+			break;
 	}
 
- timed_out:
-	list_del(&waiter.list);
-	return -ETIME;
-
- interrupted:
 	list_del(&waiter.list);
-	return -EINTR;
+	return ret;
 }
 
 static noinline void __sched __down(struct semaphore *sem)

@@ -255,6 +256,5 @@ static noinline void __sched __up(struct
 {
 	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
 						struct semaphore_waiter, list);
-	list_del(&waiter->list);
 	wake_up_process(waiter->task);
 }

ok, it's looking good here so far so here's the scheduler fixes tree that you can pull if my semaphore fix looks good to you too:

git://git.kernel.org/pub/scm/linux/kernel/git/mingo/linux-2.6-sched-fixes.git for-linus

also includes a scheduler arithmetics fix from Mike. Find the shortlog and diff below.

Ingo

------------------>
Ingo Molnar (1):
semaphore: fix

Mike Galbraith (1):
sched: fix weight calculations

 kernel/sched_fair.c |   11 ++++++--
 kernel/semaphore.c  |   64 ++++++++++++++++++++++++---------------------------
 2 files changed, 38 insertions(+), 37 deletions(-)

index c863663..e24ecd3 100644
@@ -662,10 +662,15 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
 	if (!initial) {
 		/* sleeps upto a single latency don't count. */
 		if (sched_feat(NEW_FAIR_SLEEPERS)) {
+			unsigned long thresh = sysctl_sched_latency;
+
+			/*
+			 * convert the sleeper threshold into virtual time
+			 */
 			if (sched_feat(NORMALIZED_SLEEPER))
-				vruntime -= calc_delta_weight(sysctl_sched_latency, se);
-			else
-				vruntime -= sysctl_sched_latency;
+				thresh = calc_delta_fair(thresh, se);
+
+			vruntime -= thresh;
 		}
 
 		/* ensure we never gain time by being placed backwards. */

The commit description says:

<-- snip -->

...

This bug could be related to the regression reported by Yanmin Zhang:

| Comparing with kernel 2.6.25, sysbench+mysql(oltp, readonly) has lots
| of regressions with 2.6.26-rc1:
|
| 1) 8-core stoakley: 28%;
| 2) 16-core tigerton: 20%;
| 3) Itanium Montvale: 50%.

...

<-- snip -->

Can we get that verified and the description updated before it hits Linus' tree?

Otherwise this "could be related" will become unchangable metadata that will stay forever - no matter whether there's any relation at all.

Thanks
Adrian

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

that's not needed. Mike's fix is correct, regardless of whether it fixes the other regression or not.

... and the problem with that is exactly what?

Ingo

Then scrap the part about it possibly fixing a regression and the
Reported-by: line.

It is important that our metadata is as complete and correct as reasonably possible. Our code is not as well documented as it should be, and in my experience often the only way to understand what happens and why it happens is to ask git for the metadata (and I'm actually doing this even for most of my "trivial" patches).

In 3 hours or 3 years someone might look at this commit trying to understand what it does and why it does this.

And there's a big difference between "we do it because it's correct from a theoretical point of view" and "it is supposed to fix a huge performance regression".

cu
Adrian

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Er, I mis-wrote there.

Task A calls up() and wakes up C. Then task B calls up() and wakes up C again because C hasn't removed itself from the list yet. D never receives a wakeup. The solution is for C to pass a wakeup along to the next in line. (The solution remains the same).

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

[...]

This is exactly it. Or rather, it's even simpler. Three tasks involved; A and B call xlog_state_get_iclog_space() and end up calling psema(&log->l_flushsema) [down() by any other name -- the semaphore is initialised to 0; it's really a completion]. Then task C calls xlog_state_do_callback() which does:

        while (flushcnt--)
                vsema(&log->l_flushsema);

[vsema is AKA up()]

It assumes this wakes up both A and B ... but it won't with Ingo's code; it'll wake up A twice.

So I deem my fix "proven by thought experiment". I haven't tried booting it or anything.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

i actually have two fixes, made earlier today. The 'fix3' one has been confirmed by Sven to fix the regression - but i think we need the 'fix #2' one below as well to make it complete.

Ingo

-------------------->
Subject: semaphore: fix3
From: Ingo Molnar <[email protected]>
Date: Sun May 11 09:51:07 CEST 2008

---
 kernel/semaphore.c |    7 +++++++
 1 file changed, 7 insertions(+)

Index: linux/kernel/semaphore.c
===================================================================
@@ -258,5 +258,12 @@ static noinline void __sched __up(struct
 {
 	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
 						struct semaphore_waiter, list);
+
+	/*
+	 * Rotate sleepers - to make sure all of them get woken in case
+	 * of parallel up()s:
+	 */
+	list_move_tail(&waiter->list, &sem->wait_list);
+
 	wake_up_process(waiter->task);
 }

---------------->
Subject: semaphore: fix #2
From: Ingo Molnar <[email protected]>
Date: Thu May 08 11:53:48 CEST 2008

---
 kernel/semaphore.c |   16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

Index: linux/kernel/semaphore.c
===================================================================
@@ -194,6 +194,13 @@ struct semaphore_waiter {
 	struct task_struct *task;
 };
 
+static noinline void __sched __up(struct semaphore *sem)
+{
+	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
+						struct semaphore_waiter, list);
+	wake_up_process(waiter->task);
+}
+
 /*
  * Because this function is inlined, the 'state' parameter will be
  * constant, and thus optimised away by the compiler.  Likewise the

@@ -231,6 +238,9 @@ static inline int __sched __down_common(
 	}
 
 	list_del(&waiter.list);
+	if (unlikely(!list_empty(&sem->wait_list)) && sem->count)
+		__up(sem);
+
 	return ret;
 }
 

@@ -254,9 +264,3 @@ static noinline int __sched __down_timeo
 	return __down_common(sem, TASK_UNINTERRUPTIBLE, jiffies);
 }
 
-static noinline void __sched __up(struct semaphore *sem)
-{
-	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
-						struct semaphore_waiter, list);
-	wake_up_process(waiter->task);
-}

i just combined them into a single fix, see below.

Ingo

--------------------------->
Subject: semaphore: fix #3
From: Ingo Molnar <[email protected]>
Date: Sun May 11 09:51:07 CEST 2008

---
 kernel/semaphore.c |   23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)

Index: linux/kernel/semaphore.c
===================================================================
@@ -194,6 +194,13 @@ struct semaphore_waiter {
 	struct task_struct *task;
 };
 
+static noinline void __sched __up(struct semaphore *sem)
+{
+	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
+						struct semaphore_waiter, list);
+	wake_up_process(waiter->task);
+}
+
 /*
  * Because this function is inlined, the 'state' parameter will be
  * constant, and thus optimised away by the compiler.  Likewise the

@@ -231,6 +238,9 @@ static inline int __sched __down_common(
 	}
 
 	list_del(&waiter.list);
+	if (unlikely(!list_empty(&sem->wait_list)) && sem->count)
+		__up(sem);
+
 	return ret;
 }
 

@@ -254,9 +264,10 @@ static noinline int __sched __down_timeo
 	return __down_common(sem, TASK_UNINTERRUPTIBLE, jiffies);
 }
 
-static noinline void __sched __up(struct semaphore *sem)
-{
-	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
-						struct semaphore_waiter, list);
-	wake_up_process(waiter->task);
-}
+
+	/*
+	 * Rotate sleepers - to make sure all of them get woken in case
+	 * of parallel up()s:
+	 */
+	list_move_tail(&waiter->list, &sem->wait_list);
+

That's mangled ... why did you move __up around?

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Actually, let me just go into this a little further.

In principle, you'd think that we'd want to wake up all the tasks possible as soon as possible. In practice, Dave Chinner has said that the l_flushsema introduces a thundering herd (a few hundred tasks can build up behind it on systems such as Columbia apparently) that then run into a bottleneck as soon as they're unleashed.

Current XFS CVS has a fix from myself and Christoph that gets rid of the l_flushsema and replaces it with a staggered wakeup of each task that's waiting as the previously woken task clears the critical section.

Obviously, generic up() can't possibly do as well, but by staggering the release of tasks from __down_common(), we mitigate the herd somewhat.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

the solution is to reduce semaphore usage by converting them to mutexes. Is anyone working on removing legacy semaphore use from XFS?

Ingo

This race is completely irrelevant to converting semaphores to mutexes. It can only occur for semaphores which /can't/ be converted to mutexes.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

i was not talking about the race. I was just reacting on your comments about thundering herds and staggered wakeups - which is a performance detail. Semaphores should not regress AIM7 by 50% but otherwise they are legacy code and their use should be reduced monotonically, so i was asking why anyone still cares about tuning semaphore details in XFS instead of just working on removing semaphore use from them.

exactly what usecase is that? Perhaps it could be converted to an atomic counter + the wait_event() APIs.

Ingo

That's what we did. l_flushsema is gone. It actually got replaced with a condition variable, but it's equivalent to a wait_event()

Effectively, it's a completion. It just works better with staggered wakeups than it does with the naive completion.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

So why not transform it to real completions instead? And if our current 'struct completion' abstraction is insufficient for whatever reason, why not extend that instead?

Ingo

My point is that for the only user of counting semaphores and/or semaphores-abused-as-completions that has so far hit this race, the serialised wake-up performs better. You have not pointed at a scenario that _shows_ a parallel wake-up to perform better. Some hand-waving and talking about lofty principles, yes. But no actual data.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

a 50% AIM7 slowdown maybe? With the BKL being a spinlock again it doesnt matter much in practice though.

Ingo

You're not understanding me. This is completely inapplicable to the BKL because only one task can be in wakeup at a time (due to it having a maximum value of 1). There's no way to hit this race with the BKL. The only kind of semaphore that can hit this race is the kind that can have more than one wakeup in progress at a time -- ie one which can have a value >1. Like completions and real counting semaphores.

So the only thing worth talking about (and indeed, it's now entirely moot) is what's the best way to solve this problem /for this kind of semaphore/.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

yes, but even for parallel wakeups for completions it's good in general to keep more tasks in flight than to keep less tasks in flight.

Perhaps the code could throttle them to nr_cpus, but otherwise, as the BKL example has shown it (in another context), we do much better if we overload the scheduler (in which case it can and does batch intelligently) than if we try to second-guess it and under-load it and create lots of scheduling events.

i'd agree with you that are no numbers available pro or contra, so you are right that my 50% point does not apply to your argument.

it's not really moot in terms of improving the completions code i suspect? For XFS i guess performance matters.

Ingo

That might be the case for some users, but it isn't the case for XFS. The first thing that each task does is grab a spinlock, so if you put as much in flight as early as possible, you end up with horrible contention on that spinlock. I have no idea whether this is the common case for multi-valued semaphores or not, it's just the only one I have data for.

I think the completion code is less optimised than the semaphore code today. Clearly the same question does arise, but I don't know what the answer is for completion users either.

Let's do a quick survey. drivers/net has 5 users:

3c527.c -- execution_cmd has a mutex held, so never more than one task waiting anyway. xceiver_cmd is called during open and close which I think are serialised at a higher level. In any case, no performance issue here.

iseries_veth.c -- grabs a spinlock soon after being woken.

plip.c -- called in close, no perf implication.

ppp_synctty.c -- called in close, no perf implication.

ps3_gelic_wireless.c - If this isn't serialised, it's buggy.

Maybe drivers/net is a bad example. Let's look at */*.c:

as-iosched.c -- in exit path.
blk-barrier.c -- completion on stack, so only one waiter. blk-exec.c -- ditto
cfq-iosched.c -- in exit path

crypto/api.c -- in init path
crypto/gcm.c -- in setkey path crypto/tcrypt.c -- crypto testing. Not a perf path.

fs/exec.c -- waiting for coredumps.
kernel/exit.c -- likewise
kernel/fork.c -- completion on stack
kernel/kmod.c -- completion on stack
kernel/kthread.c -- kthread creation and deletion. Shouldn't be a hot path, plus this looks like there's only going to be one task waiting. kernel/rcupdate.c -- one completion on stack, one synchronised by a mutex kernel/rcutorture.c -- doesn't matter
kernel/sched.c -- both completions on stack kernel/stop_machine.c -- completion on stack
kernel/sysctl.c -- completion on stack
kernel/workqueue.c -- completion on stack

lib/klist.c -- This one seems like it could potentially have lots of waiters, if only anything actually used klists.

It seems like most users use completions where it'd be just as easy to use a task pointer and call wake_up_task(). In any case, I think there's no evidence one way or the other about how people are using multi-sleeper completions.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

hm, this sounds like damage that is inflicted on itself by the XFS code.

Why does it signal to its waiters that "resource is available", when in reality that resource is not available but immediately serialized via a lock? (even if the lock might technically be some _other_ object)

I have not looked closely at this but the more natural wakeup flow here would be that if you know there's going to be immediate contention, to signal a _single_ resource to a _single_ waiter, and then once that contention point is over a (hopefully) much more parallel processing phase occurs, to use a multi-value completion there.

in other words: dont tell the scheduler that there is parallelism in the system when in reality there is not. And for the same reason, do not throttle wakeups in a completion mechanism artificially because one given user utilizes it suboptimally. Once throttled it's not possible to regain that lost parallelism.

yeah. I'd guess XFS would be the primary user in this area who cares about performance.

yeah - although i guess in general it's a bit safer to use an explicit completion. With a task pointer you have to be sure the task is still present, etc. (with a completion you are forced to put that completion object _somewhere_, which immediately forces one to think about lifetime issues. A wakeup to a single task pointer is way too easy to get wrong.)

So in general i'd recommend the use of completions.

yeah, that's definitely so.

Ingo

No. You're confusing what a counting semaphore is.

So you have 'n' resources available, and you use a counting semaphore for that resource counting.

But you'd still need a spinlock to actually protect the list of resources themselves. The spinlock protects a different thing than the semaphore. The semaphore isn't about mutual exclusion - it's about counting resources and waiting when there are too many things in flight.

And you seem to think that a counting semaphore is about mutual exclusion. It has nothing what-so-ever to do with that.

Linus

i was reacting to the point that Matthew made:

" The first thing that each task does is grab a spinlock, so if you
put as much in flight as early as possible, you end up with horrible contention on that spinlock. "

We were talking about the case of double, parallel up()s. My point was that the best guess is to put two tasks in flight in the synchronization primitive. Matthew's point was that the wakeups of the two tasks should be chained: one task gets woken first, which then wakes the second task in a chain. [ Matthew, i'm paraphrasing your opinion so please correct me if i'm misinterpreting your point. ]

My argument is that chaining like that in the synchronization primitive is bad for parallelism in general, because wakeup latencies are just too long in general and any action required in the context of the "first waker" throttles parallelism artificially and introduces artificial workload delays.

Even in the simple list+lock case you are talking about it's beneficial to keep as many wakers in flight as possible. The reason is that even with the worst-possible cacheline bouncing imaginable, it's much better to spin a bit on a spinlock (which is "horrible bouncing" only on paper, in practice it's nicely ordered waiting on a FIFO spinlock, with a list op every 100 nsecs or so) than to implement "soft bouncing" of tasks via an artificial chain of wakeups.

That artificial chain of wakeups has a latency of a few microseconds even in the best case - and in the worst-case it can be a delay of milliseconds later - throttling not just the current parallelism of the workload but also hiding potential future parallelism. The hardware is so much faster at messaging. [*] [**]

Ingo

[*] Not without qualifications - maybe not so on 1024 CPU systems, but
certainly so on anything sane up to 16way or so. But if worry about 1024 CPU systems i'd suggest to first take a look at the current practice in kernel/semaphore.c taking the semaphore internal spinlock again _after_ a task has woken up, just to remove itself from the list of waiters. That is rather unnecessary serialization
- at up() time we are already holding the lock, so we should remove the entry there. That's what the mutex code does too.

[**] The only place where i can see staggered/chained wakeups help is in
the specific case when the wakee runs into a heavy lock _right after_ wakeup. XFS might be running into that and my reply above talks about that hypothetical scenario.

If it is so then it is handled incorrectly, because in that case we dont have any true parallelism at the point of up(), and we know it right there. There is no reason to pretend at that point that we have more parallelism, when all we do is we block on a heavy lock right after wakeup.

Instead, the correct implementation in that case would be to have a wait queue for that heavy lock (which in other words can be thought of as a virtual single-resource which is either 'available' or 'unavailable'), and _then_ after that to use a counting semaphore for the rest of the program flow, which is hopefully more parallel.

I.e. precisely map the true parallelism of the code via the synchronization primitives, do not over-synchronize it and do not under-synchronize it. And if there's any doubt which one should be used, under-synchronize it - because while the scheduler is rather good at dealing with too many tasks it cannot conjure runnable tasks out of thin air.

Btw., the AIM7 regression was exactly that: in the 50% regressed workload the semaphore code hid the true parallelism of the workload and we had only had 5 tasks on the runqueue and the scheduler had no chance to saturate all CPUs. In the "good" case (be that spinlock based or proper-semaphores based BKL) there were 2000 runnable tasks on the runqueues, and the scheduler sorted them out and batched the workload just fine!

the gain is rather obvious: two parallel up()s (or just up()s which come close enough after each other) will wake up two tasks in parallel. With your patch, the first guy wakes up and then it wakes up the second guy. I.e. your patch serializes the wakeup chain, mine keeps it parallel.

the cache line dirtying is rather secondary to any solution - the first goal for any locking primitive is to get scheduling precise: to not wake up more tasks than optimal and to not wake up less tasks than optimal.

i.e. can you see any conceptual hole in the patch below?

Ingo

---
 kernel/semaphore.c |    6 ++++++
 1 file changed, 6 insertions(+)

Index: linux/kernel/semaphore.c
===================================================================
@@ -258,5 +258,11 @@ static noinline void __sched __up(struct
 {
 	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
 						struct semaphore_waiter, list);
+	/*
+	 * Rotate sleepers - to make sure all of them get woken in case
+	 * of parallel up()s:
+	 */
+	list_move_tail(&waiter->list, &sem->wait_list);
+
 	wake_up_process(waiter->task);
 }

Yup. I explained why that's actually beneficial in an earlier email.

That's a laudable goal, but ultimately it's secondary to performance (or this thread wouldn't exist).

No conceptual holes, just a performance one.

Either we want your patch below or mine; definitely not both.

index 5e41217..e520ad4 100644
@@ -229,6 +229,11 @@ static inline int __sched __down_common(struct semaphore *sem, long state,
 	}
 
 	list_del(&waiter.list);
+
+	/* It's possible we need to wake up the next task on the list too */
+	if (unlikely(sem->count > 1) && !list_empty(&sem->wait_list))
+		__up(sem);
+
 	return ret;
 }
 

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

but the problem is that by serializing the wakeup chains naively you introduced a more than 50% AIM7 performance regression.

Ingo

That's a different issue. The AIM7 regression is to do with whether a task that is currently running and hits a semaphore that has no current holder but someone else waiting should be allowed to jump the queue. No argument there; performance trumps theoretical fairness.

This issue is whether multiple sleepers should be woken up all-at-once or one-at-a-time. Here, you seem to be arguing for theoretical fairness to trump performance.

(Let's be quite clear; this issue affects *only* multiple sleepers and multiple wakes given to those sleepers. ie semaphores-being-used-as-completions and true counting semaphores).

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

No, the problem is that the BKL shouldn't be a semaphore at all. Performance fixed.

After that, it's *purely* a correctness issue, and then we might as well be fair and not allow the stealing of semaphores from under waiters at ALL. Which is what Matthews original code did.

In other words, current -git is fine, and was already confirmed by Sven to fix the bug (before *any* of your patches were), and was earlier confirmed to fix the AIM7 performance regression (better than *any* of your patches were).

So I fixed the problems last night already. Stop wasting everybody's time.

Linus

Still mangled ... and I don't see how we lose a wakeup. We test for having the semaphore before we check for having been interrupted, and we hold the lock the whole time.

IOW, what I think you're checking for is:

task A task B

			if sem->count >0
				break;
sem->count++
wake_up_process(B)
			if (state == TASK_INTERRUPTIBLE && signal_pending(task))
				break;

which can't happen because of sem->lock.

Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

ok, agreed, that race cannot happen.

Ingo

This one fixes the regression too, after applying it on top of bf726e.

Sven

Why don't we just make it do the same thing that the x86 semaphores used to do: make it signed, and decrement unconditionally. And callt eh slow-path if it became negative.

IOW, make the fast-path be

	spin_lock_irqsave(&sem->lock, flags);
	if (--sem->count < 0)
		__down();
	spin_unlock_irqrestore(&sem->lock, flags);

and now we have an existing known-good implementation to look at?

Rather than making up a totally new and untested thing.

Linus

Ok, after having thought that over, and looked at the code, I think I like your version after all. The old implementation was pretty complex due to the need to be so extra careful about the count that could change outside of the lock, so everything considered, a new implementation that is simpler is probably the better choice.

Ergo, I will just pull your scheduler tree.

Linus

yeah. I thought about that too, the problem i found is this thing in the old lib/semaphore-sleepers.c code's __down() path:

        remove_wait_queue_locked(&sem->wait, &wait);
        wake_up_locked(&sem->wait);
        spin_unlock_irqrestore(&sem->wait.lock, flags);
        tsk->state = TASK_RUNNING;

that mystery wakeup once i understood to be necessary for some weird ordering reason, but it would probably be hard to justify in the new code, because it's done unconditionally, regardless of whether there are sleepers around.

And once we deviate from the old code, we might as well go for the simplest approach - which also happens to be rather close to the mutex code's current slowpath - just with counting property added, legacy semantics and no lockdep coverage.

great! Meanwhile a 100 randconfigs booted fine with that tree so i'd say the implementation is robust.

i also did a quick re-test of AIM7 because the wakeup logic changed a bit from what i tested initially (from round-robin to strict FIFO), and as expected not much changed in the AIM7 results on the quad:

  Tasks   Jobs/Min        JTI     Real    CPU     Jobs/sec/task
  2000    55019.9         96      211.6   806.5   0.4585
  2000    55116.2         90      211.2   804.7   0.4593
  2000    55082.3         82      211.3   805.5   0.4590

this is slightly lower but the test was not fully apples to apples because this also had some tracing active and other small details. It's still very close to the v2.6.25 numbers. I suspect some more performance could be won in this particular workload by getting rid of the BKL dependency altogether.

Ingo

Did somebody have any trace on which BKL taker it is? It apparently wasn't file locking. Was it the tty layer?

Linus

yeah, i captured a trace of all the down()s that happen in the workload, using ftrace/sched_switch + stacktrace + a tracepoint in down(). Here's the semaphore activities in the trace:

# grep lock_kernel /debug/tracing/trace | cut -d: -f2- | sort | \
                                          uniq -c | sort -n | cut -d= -f1-4

      9  down <= lock_kernel <= proc_lookup_de <= proc_lookup <
     12  down <= lock_kernel <= de_put <= proc_delete_inode <
     14  down <= lock_kernel <= proc_lookup_de <= proc_lookup <
     19  down <= lock_kernel <= vfs_ioctl <= do_vfs_ioctl <
     58  down <= lock_kernel <= tty_release <= __fput <
     62  down <= lock_kernel <= chrdev_open <= __dentry_open <
     70  down <= lock_kernel <= sys_fcntl <= system_call_after_swapgs <
   2512  down <= lock_kernel <= opost <= write_chan <
   2574  down <= lock_kernel <= write_chan <= tty_write <

note that this is running the fixed semaphore code, so contended semaphores are really rare in the trace. The histogram above includes all calls to down().

here's the full trace file (from a single CPU, on a dual-core box running aim7):

http://redhat.com/~mingo/misc/aim7-ftrace.txt

some other interesting stats. Top 5 wakeups sources:

 # grep wake_up aim7-ftrace.txt  | cut -d: -f2- | sort | uniq -c | 
                                   sort -n | cut -d= -f1-6 | tail -5
  [...]
    340  default_wake_function <= __wake_up_common <= __wake_up_sync <= unix_write_space <= sock_wfree <= skb_release_all <
    411  default_wake_function <= autoremove_wake_function <= __wake_up_common <= __wake_up_sync <= pipe_read <= do_sync_read <
    924  default_wake_function <= autoremove_wake_function <= __wake_up_common <= __wake_up_sync <= pipe_write <= do_sync_write <
   1301  default_wake_function <= __wake_up_common <= __wake_up <= n_tty_receive_buf <= pty_write <= write_chan <
   2065  wake_up_state <= prepare_signal <= send_signal <= __group_send_sig_info <= group_send_sig_info <= __kill_pgrp_info <

top 10 scheduling points:

# grep -w schedule aim7-ftrace.txt  | cut -d: -f2- | sort |
                            uniq -c | sort -n | cut -d= -f1-4 | tail -10
  [...]
    465  schedule <= __cond_resched <= _cond_resched <= shrink_active_list <
    582  schedule <= cpu_idle <= start_secondary <=  <
    929  schedule <= pipe_wait <= pipe_read <= do_sync_read <
    990  schedule <= __cond_resched <= _cond_resched <= shrink_page_list <
   1034  schedule <= io_schedule <= get_request_wait <= __make_request <
   1140  schedule <= worker_thread <= kthread <= child_rip <
   1512  schedule <= retint_careful <=  <= 0 <
   1571  schedule <= __cond_resched <= _cond_resched <= shrink_active_list <
   2034  schedule <= schedule_timeout <= do_select <= core_sys_select <
   2355  schedule <= sysret_careful <=  <= 0 <

as visible from the trace, this is a CONFIG_PREEMPT_NONE kernel, so most of the preemptions get triggered by wakeups and get executed from the return-from-syscall need_resched check. But there's a fair amount of select() related sleeping as well, and a fair amount of IRQ-hits-userspace driven preemptions as well.

a rather hectic workload, with a surprisingly large amount of TTY related activity.

and here's a few seconds worth of NMI driven readprofile output:

1131 page_fault 70.6875
1181 find_lock_page 8.2014

  1302 __isolate_lru_page                        12.8911
  1344 copy_page_c                               84.0000
  1588 page_lock_anon_vma                        34.5217
  1616 ext3fs_dirhash                             3.4753
  1683 ext3_htree_store_dirent                    6.8975
  1976 str2hashbuf                               12.7484
  1992 copy_user_generic_string                  31.1250
  2362 do_unlinkat                                6.5069
  2969 try_to_unmap                               2.0791
  3031 will_become_orphaned_pgrp                 24.4435
  4009 __copy_user_nocache                       12.3735
  4627 congestion_wait                           34.0221

6624 clear_page_c 414.0000
18711 try_to_unmap_one 30.8254
34447 page_referenced 140.0285
38669 do_filp_open 17.7789
166569 page_referenced_one 886.0053
213361 *unknown*
216021 sync_page 3375.3281
391888 page_check_address 1414.7581
962212 total 0.3039