The sleeping locks implementation based on rtmutexes can miss wakeups
for two reasons:

1) The unconditional usage TASK_UNINTERRUPTIBLE for the blocking state

   Results in missed wakeups from wake_up_interruptible*()

   state = TASK_INTERRUPTIBLE;
   blocks_on_lock()
     state = TASK_UNINTERRUPTIBLE;
     schedule();
     ....
     acquires_lock();
     restore_state();

   Until the waiter has restored its state wake_up_interruptible*() will
   fail.

2) The rtmutex wakeup intermediate state TASK_RUNNING_MUTEX

   Results in missed wakeups from wake_up*()

   waiter is woken by mutex wakeup
   	  waiter->state = TASK_RUNNING_MUTEX;
   ....
   acquires_lock();
   restore_state();

   Until the waiter has restored its state wake_up*() will fail.

Solution:

Instead of setting the state to TASK_RUNNING_MUTEX in the mutex wakeup
case we logically OR TASK_RUNNING_MUTEX to the current waiter
state. This keeps the original bits (TASK_INTERRUPTIBLE /
TASK_UNINTERRUPTIBLE) intact and lets wakeups succeed. When a task
blocks on a lock in state TASK_INTERRUPTIBLE and is woken up by a real
wakeup, then we store the state = TASK_RUNNING for the restore and can
safely use TASK_UNINTERRUPTIBLE from that point to avoid further
wakeups which just let us loop in the lock code.

This also removes the extra TASK_RUNNING_MUTEX flags from the
wakeup_process*() functions as they are not longer necessary.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

The adaptive spin patches introduced an overdesigned optimization for
the adaptive path. This avoidance of those code pathes is not worth
the extra conditionals and furthermore it is inconsistent in itself.

Remove it and use the same mechanism as the other lock pathes. That
way we have a consistent state manipulation scheme and less extra
cases.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

The manipulation of the waiter task state is copied all over the place
with slightly different details. Use one set of functions to reduce
duplicated code and make the handling consistent for all instances.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

Lock stealing and non cmpxchg will always go into the slow path.
This patch detects the fact that we didn't go through the work of
blocking and will exit early.
Signed-off-by: Steven Rostedt <srostedt@redhat.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

[ The following text is in the "utf-8" character set. ]
    [ Your display is set for the "iso-8859-1" character set.  ]
    [ Some characters may be displayed incorrectly. ]

From: Peter W. Morreale <pmorreale@novell.com>

Remove the redundant attempt to get the lock.  While it is true that the
exit path with this patch adds an un-necessary xchg (in the event the
lock is granted without further traversal in the loop) experimentation
shows that we almost never encounter this situation.
Signed-off-by: Peter W. Morreale <pmorreale@novell.com>
Signed-off-by: Gregory Haskins <ghaskins@novell.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

[ The following text is in the "utf-8" character set. ]
    [ Your display is set for the "iso-8859-1" character set.  ]
    [ Some characters may be displayed incorrectly. ]

From: Peter W.Morreale <pmorreale@novell.com>

In wakeup_next_waiter(), we take the pi_lock, and then find out whether
we have another waiter to add to the pending owner.  We can reduce
contention on the pi_lock for the pending owner if we first obtain the
pointer to the next waiter outside of the pi_lock.
Signed-off-by: Peter W. Morreale <pmorreale@novell.com>
Signed-off-by: Gregory Haskins <ghaskins@novell.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

[ The following text is in the "utf-8" character set. ]
    [ Your display is set for the "iso-8859-1" character set.  ]
    [ Some characters may be displayed incorrectly. ]

It is redundant to wake the grantee task if it is already running, and
the call to wake_up_process is relatively expensive.  If we can safely
skip it we can measurably improve the performance of the adaptive-locks.

Credit goes to Peter Morreale for the general idea.
Signed-off-by: Gregory Haskins <ghaskins@novell.com>
Signed-off-by: Peter Morreale <pmorreale@novell.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

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>

No reason to update current if we are running. We'll do that when we exit
the loop.
Signed-off-by: Steven Rostedt <srostedt@redhat.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

The current logic makes rather coarse adjustments to current->state since
it is planning on sleeping anyway.  We want to eventually move to an
adaptive (e.g. optional sleep) algorithm, so we tighten the scope of the
adjustments to bracket the schedule().  This should yield correct behavior
with or without the adaptive features that are added later in the series.
We add it here as a separate patch for greater review clarity on smaller
changes.
Signed-off-by: Gregory Haskins <ghaskins@novell.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

The current logic only allows lock stealing to occur if the current task
is of higher priority than the pending owner. We can gain signficant
throughput improvements (200%+) by allowing the lock-stealing code to
include tasks of equal priority.  The theory is that the system will make
faster progress by allowing the task already on the CPU to take the lock
rather than waiting for the system to wake-up a different task.

This does add a degree of unfairness, yes.  But also note that the users
of these locks under non -rt environments have already been using unfair
raw spinlocks anyway so the tradeoff is probably worth it.

The way I like to think of this is that higher priority tasks should
clearly preempt, and lower priority tasks should clearly block.  However,
if tasks have an identical priority value, then we can think of the
scheduler decisions as the tie-breaking parameter. (e.g. tasks that the
scheduler picked to run first have a logically higher priority amoung tasks
of the same prio).  This helps to keep the system "primed" with tasks doing
useful work, and the end result is higher throughput.

Thanks to Steven Rostedt for pointing out that RT tasks should be excluded
to prevent the introduction of an unnatural unbounded latency.

[ Steven Rostedt - removed config option to disable ]
Signed-off-by: Gregory Haskins <ghaskins@novell.com>
Signed-off-by: Steven Rostedt <srostedt@redhat.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Implement the base infrastructure to replace spinlocks for -rt.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Debugging interface.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Necessary for rt_mutex wakeups to preserve the state.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Simplifies the separation of anon_rw_semaphores and rw_semaphores for
-rt.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Triggers the missed preemption check.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

add new, -rt specific IRQ API variants. Maps to the same as before
on non-PREEMPT_RT.

 include/linux/bottom_half.h |    8 ++++++++
 1 file changed, 8 insertions(+)
Signed-off-by: Ingo Molnar <mingo@elte.hu>

Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Make cancellation of a running callback in softirq context safe
against preemption.
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

When softirqs can be preempted we need to make sure that cancelling
the timer from the active thread can not deadlock vs. a running timer
callback. Add a waitqueue to resolve that.
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

The random call introduces high latencies and is almost
unused. Disable it for -rt.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Based on the mainline infrastructure we force thread all interrupts
with per device threads.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Split them into separate threads. One for each softirq
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Migration maks/unmaks interrupts unconditionally. With forced irq
threading thats going to result in an interrupt storm when the
threaded handler has not finished yet.
Signed-off-by: Ingo Molnar <mingo@elte.hu>

RT wants that disctinction for now. We need to revisit this.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Replaced the RW lock for now with atomic_spinlock. We have no
atomic_rwlocks in -rt right now and I doubt that the OF path is
performance critical.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Otherwise the HV magic gets confused if we are preempted.
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

On ARM there is a problem where the interrupt handler stalls when they
are coming faster than the kernel can handle. The problem seems to
occur on RT primarily, but the problem is also valid for non-RT
kernels.

The problem is twofold:
* the handle_simple_irq() mechanism is used for GPIO, but because the GPIO
interrupt source is actually an edge triggered interrupt source, the
handle_edge_irq() mechanism must be used. While using the simple_irq()
mechanisms edges can be missed for either mainline as RT kernels.
The simple_irq mechanism is *never* meant to be used for these types
of interrupts. See the thread at: http://lkml.org/lkml/2007/11/26/73
* The RT kernels has a problem that the interrupt get masked forever while
the interrupt thread is running and a new interrupt arrives.
In the interrupt threads there is masking done in the handle_simple_irq()
path, while a simple_irq typically cannot be masked.

This patch only solves the first bullet, which is enough for AT91, by
moving the GPIO interrupt handler towards the handle_edge_irq().
To solve the problem in the simple_irq() path a seperate fix has to be done,
but as it is no longer used by AT91, that fix will not affect AT91.

Tested on:
* AT91rm9200-ek, and proprietary board
* AT91SAM9261-ek. (This patches also solves the problem that the DM9000 does
                   not work on this board while using PREEMPT-RT)
Signed-off-by: Remy Bohmer <linux@bohmer.net>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

The locking in the get_rate() hook is unnecessary, and causes problems
when used with the -rt patch, since it may be called recursively.
Signed-off-by: Kevin Hilman <khilman@mvista.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>