After talking with Gregory Haskins about how they implemented his
version of adaptive spinlocks and before I actually looked at their
code, I was thinking about it while lying in bed.

I always thought that adaptive spinlocks were to spin for a short
period of time based off of some heuristic and then sleep. This idea
is totally bogus. No heuristic can account for a bunch of different
activities. But Gregory mentioned something to me that made a hell of a lot
of sense. And that is to only spin while the owner is running.

If the owner is running, then it would seem that it would be quicker to
spin then to take the scheduling hit. While lying awake in bed, it dawned
on me that we could simply spin in the fast lock and never touch the
"has waiters" flag, which would keep the owner from going into the
slow path. Also, the task itself is preemptible while spinning so this
would not affect latencies.

The only trick was to not have the owner get freed between the time
you saw the owner and the time you check its run queue. This was
easily solved by simply grabing the RCU read lock because freeing
of a task must happen after a grace period.

I first tried to stay only in the fast path. This works fine until you want
to guarantee that the highest prio task gets the lock next. I tried all
sorts of hackeries and found that there was too many cases where we can
miss. I finally concurred with Gregory, and decided that going into the
slow path was the way to go.

I then started looking into what the guys over at Novell did. The had the
basic idea correct, but went way overboard in the implementation, making
it far more complex than it needed to be. I rewrote their work using the
ideas from my original patch, and simplified it quite a bit.

This is the patch that they wanted to do ;-)

Special thanks goes out to Gregory Haskins, Sven Dietrich and
Peter Morreale, for proving that adaptive spin locks certainly *can*
make a difference.
Signed-off-by: Steven Rostedt <srostedt@redhat.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>