[patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

i have released the -V0.7.1 Real-Time Preemption patch, which can be
downloaded from:

    http://redhat.com/~mingo/realtime-preempt/

this release is mainly a merge of -V0.6.9 to 2.6.10-rc2-mm2.

I havent done a proper changelog for a couple of days so here is a list
of bigger changes since -V0.4:

 - implemented a first version of the priority inheritance handling and
   priority inversion avoidance logic. This feature, after some initial
   stability problems, solved the jackd and rtc_wakeup latencies that
   were introduced by the ultra-finegrained locking in the -V series.

   (the -T/U series had a coarser locking scheme triggered much lower
   levels of priority inversion scenarios. The locking in the -V series
   was clearly the tipping point.)

   The new PI code covers all synchronization objects in Linux (on
   PREEMPT_REALTIME): spinlocks, rwlocks, semaphores and rwsems. 
   Feedback on the design of this code would be welcome, and patches as
   well, if you have a better scheme. The code is pretty modular so feel 
   free to experiment with alternative schemes.

 - completely reworked the debugging framework. All lock types
   (spinlocks, rwlocks, semaphores and rwsems) are now tracked, both
   their symbolic name and their place of acquire are traced and printed
   out upon detection of a deadlock. More and better information is
   printed upon a deadlock. Got rid of the 'semaphore owners array' in
   debugging mode, this reduces the footprint of semaphores quite
   significantly and speeds up deadlock detection.

 - got rid of the separate 'counted semaphores' implementation, it was
   too intrusive. Made the core 'generic semaphores' implementation
   compatible with vanilla Linux counted semaphore semantics. This also
   enabled the unrolling of the completion-handling cleanups which,
   while being very nice, were getting intrusive as well.

 - countless build and driver related reports/fixes from lots of people

 - more latency breaks in the remaining critical sections. A
   particularly important one was the irqs-off latency bugfix from
   Thomas Gleixner.

 - sped up the i8259 PIC and the PIT timer hardirq handling routines -
   these are now in the path of the longest latency.

 - cleaned up IRQ and signal preemption - there were missed
   check-rescheds and possibilities for IRQ recursion.

 - made ALSA's ioctl()s not use the BKL - this fixes more jackd
   latencies.

to create a -V0.7.1 tree from scratch, the patching order is:

   http://kernel.org/pub/linux/kernel/v2.6/linux-2.6.9.tar.bz2
   http://kernel.org/pub/linux/kernel/v2.6/testing/patch-2.6.10-rc1.bz2
   http://kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.10-rc1/2.6.10-rc1-mm2/2.6.10-rc1-mm2.bz2
   http://redhat.com/~mingo/realtime-preempt/realtime-preempt-2.6.10-rc1-mm2-V0.7.1

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Lorenzo Allegrucci]

On Wednesday 03 November 2004 11:58, Ingo Molnar wrote:
> 
> i have released the -V0.7.1 Real-Time Preemption patch, which can be
> downloaded from:
> 
>     http://redhat.com/~mingo/realtime-preempt/
> 
> this release is mainly a merge of -V0.6.9 to 2.6.10-rc2-mm2.

  AS      arch/i386/lib/checksum.o
  CC      arch/i386/lib/dec_and_lock.o
  CC      arch/i386/lib/delay.o
  AS      arch/i386/lib/getuser.o
  CC      arch/i386/lib/memcpy.o
  CC      arch/i386/lib/mmx.o
  CC      arch/i386/lib/strstr.o
  CC      arch/i386/lib/usercopy.o
  AR      arch/i386/lib/lib.a
  GEN     .version
  CHK     include/linux/compile.h
  UPD     include/linux/compile.h
  CC      init/version.o
  LD      init/mounts.o
  LD      init/built-in.o
  LD      .tmp_vmlinux1
net/built-in.o(.text+0x1887f): In function `netpoll_setup':
: undefined reference to `rcu_read_lock_up_read'
net/built-in.o(.text+0x188ed): In function `netpoll_setup':
: undefined reference to `rcu_read_lock_up_read'
make: *** [.tmp_vmlinux1] Error 1

CONFIG_NETPOLL=y
# CONFIG_NETPOLL_RX is not set
# CONFIG_NETPOLL_TRAP is not set
CONFIG_NET_POLL_CONTROLLER=y

-- 
I route therefore you are

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Lorenzo Allegrucci <l_allegrucci@yahoo.it> wrote:

>   LD      init/built-in.o
>   LD      .tmp_vmlinux1
> net/built-in.o(.text+0x1887f): In function `netpoll_setup':
> : undefined reference to `rcu_read_lock_up_read'
> net/built-in.o(.text+0x188ed): In function `netpoll_setup':
> : undefined reference to `rcu_read_lock_up_read'
> make: *** [.tmp_vmlinux1] Error 1

fixed in -V0.7.3.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Lorenzo Allegrucci]

[-- Attachment #1: Type: text/plain, Size: 616 bytes --]

On Wednesday 03 November 2004 14:46, Ingo Molnar wrote:
> 
> * Lorenzo Allegrucci <l_allegrucci@yahoo.it> wrote:
> 
> >   LD      init/built-in.o
> >   LD      .tmp_vmlinux1
> > net/built-in.o(.text+0x1887f): In function `netpoll_setup':
> > : undefined reference to `rcu_read_lock_up_read'
> > net/built-in.o(.text+0x188ed): In function `netpoll_setup':
> > : undefined reference to `rcu_read_lock_up_read'
> > make: *** [.tmp_vmlinux1] Error 1
> 
> fixed in -V0.7.3.

I've just tried V0.7.3 but my PS/2 mouse and keyboard don't work.
No message from the kernel.  I attach my .config

-- 
I route therefore you are

[-- Attachment #2: config.gz --]
[-- Type: application/x-gzip, Size: 8427 bytes --]

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

>i have released the -V0.7.1 Real-Time Preemption patch, which can be
>downloaded from:
>
>    http://redhat.com/~mingo/realtime-preempt/

V0.7.1 had build problems but after applying V0.7.7, I got a clean build
and was able to do some testing.

 - single user and telnet 5 were uneventful

 - preempt_wakeup_timing (PWT) is still generating false positives on SMP

 - after disabling PWT, I ran for over an hour without any latency
traces > 200 usec.

 - no crashes, lockups, or other fatal behavior in that same period

 - X test was generally OK. A few bursts of high overhead (> 1 msec)
on the CPU task and worst case was > 2 msec.

 - top test was a little cleaner, but its worst case was much worse
(over 17 msec).

 - network tests were similar, with even longer worst cases (21 msec and
32 msec)

 - disk I/O tests had some really odd results. The write test was much
cleaner than read / copy. All tests had > 25 msec worst cases. The read
test also had a pretty consistent variation on CPU overhead, about 500 usec
range (compared to 1160 usec nominal duration) in CPU loop timing.

A few other things I noticed:
 - whenever the real time test was active, responses to ping from another
system would basically stop until the real time test was done. In one case
about 25 ping packets were returned after a huge delay. From that, it
appears they were received but the return was delayed.
 - cat /proc/interrupts showed that LOC was increasing on both CPU's
during the tests.
 - the scheduler seems to prefer run my cpu_burn (nice'd) task instead
of updating the X display, doing the latency timing checks, ping responses,
and anything else that does useful work.
 - the disk write test was REALLY SLOW, perhaps hundreds of Kbytes per
second instead of what I normally see. I took much longer than the real
time audio test. I checked with top and noticed that "fam" was taking
near 100% of CPU time. I closed my konqueror window (just happened to be
looking at my test directory) and fam usage went away and the disk writes
sped up considerably. I don't recall seeing this symptom on -T3 or
previous tests, may try that later today to see if this is an old problem
or not.

This appears to be more stable than anything else since -T3 but the
odd spikes and scheduling symptoms are quite troubling.
  --Mark

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[john cooper]

Ingo Molnar wrote:

>    The new PI code covers all synchronization objects in Linux (on
>    PREEMPT_REALTIME): spinlocks, rwlocks, semaphores and rwsems. 
>    Feedback on the design of this code would be welcome, and patches as
>    well, if you have a better scheme. The code is pretty modular so feel 
>    free to experiment with alternative schemes.

I didn't see closure being performed of a possible blocked-owner
dependency chain, but only promotion of the immediate owner.  It
is possible for a mutex owner to itself be blocked on another mutex
requiring promotion of the latter mutex owner(s).

-- 
john.cooper@timesys.com

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

I reran my tests on -T3 to see if the same symptoms I saw with -V0.7.7
were present with the older (preempt, not RT) patches.

> - whenever the real time test was active, responses to ping from another
>system would basically stop until the real time test was done. In one case
>about 25 ping packets were returned after a huge delay. From that, it
>appears they were received but the return was delayed.
Same with -T3. What's really odd is that it stopped during the network
tests as well; may indicate that the network tests don't actually run
during the real time audio test. Hmm. Will modify the stress_neti and
stress_neto scripts I use to dump after each file transfer & see if
this is true or not. That certainly was not the case on 2.4 kernels
so this looks like a serious regression.

> - cat /proc/interrupts showed that LOC was increasing on both CPU's
>during the tests.
Did not check this, but I wasn't seeing the severe lockups of the display
on -T3 either. Yes - it is sometimes slow to update, but not stopping
display updates for extended periods.

> - the scheduler seems to prefer run my cpu_burn (nice'd) task instead
>of updating the X display, doing the latency timing checks, ping
responses,
>and anything else that does useful work.
To some extent, I see this symptom too. I watched the system with top
during the network and disk tests and it would stop updating for several
seconds (should be one second updates) during the test (and usually show
cpu_burn at > 90% CPU), then do a flurry of updates, and then sometimes
settle down to the one per second update for several seconds in a row.

> - the disk write test was REALLY SLOW, perhaps hundreds of Kbytes per
>second instead of what I normally see. I took much longer than the real
>time audio test. I checked with top and noticed that "fam" was taking
>near 100% of CPU time. I closed my konqueror window (just happened to be
>looking at my test directory) and fam usage went away and the disk writes
>sped up considerably.
This was much less severe in -T3. What I saw was that fam would show up
for several seconds and then disappear from the top list for several
seconds. The disk transfer speed also appeared to be much faster on -T3
than -V0.7.7 when fam was active. (based on how much clock time the
test took to perform)

--Mark H Johnson
  <mailto:Mark_H_Johnson@raytheon.com>

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Lorenzo Allegrucci]

On Wednesday 03 November 2004 18:53, Lorenzo Allegrucci wrote:
> On Wednesday 03 November 2004 14:46, Ingo Molnar wrote:
> > 
> > * Lorenzo Allegrucci <l_allegrucci@yahoo.it> wrote:
> > 
> > >   LD      init/built-in.o
> > >   LD      .tmp_vmlinux1
> > > net/built-in.o(.text+0x1887f): In function `netpoll_setup':
> > > : undefined reference to `rcu_read_lock_up_read'
> > > net/built-in.o(.text+0x188ed): In function `netpoll_setup':
> > > : undefined reference to `rcu_read_lock_up_read'
> > > make: *** [.tmp_vmlinux1] Error 1
> > 
> > fixed in -V0.7.3.
> 
> I've just tried V0.7.3 but my PS/2 mouse and keyboard don't work.
> No message from the kernel.  I attach my .config

Problem solved disabling ACPI.

-- 
I route therefore you are

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Lorenzo Allegrucci <l_allegrucci@yahoo.it> wrote:

> On Wednesday 03 November 2004 18:53, Lorenzo Allegrucci wrote:
> > On Wednesday 03 November 2004 14:46, Ingo Molnar wrote:
> > > 
> > > * Lorenzo Allegrucci <l_allegrucci@yahoo.it> wrote:
> > > 
> > > >   LD      init/built-in.o
> > > >   LD      .tmp_vmlinux1
> > > > net/built-in.o(.text+0x1887f): In function `netpoll_setup':
> > > > : undefined reference to `rcu_read_lock_up_read'
> > > > net/built-in.o(.text+0x188ed): In function `netpoll_setup':
> > > > : undefined reference to `rcu_read_lock_up_read'
> > > > make: *** [.tmp_vmlinux1] Error 1
> > > 
> > > fixed in -V0.7.3.
> > 
> > I've just tried V0.7.3 but my PS/2 mouse and keyboard don't work.
> > No message from the kernel.  I attach my .config
> 
> Problem solved disabling ACPI.

does the same problem happen in vanilla 2.6.10-rc1-mm2 too?

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Lorenzo Allegrucci]

On Wednesday 03 November 2004 21:43, Ingo Molnar wrote:
> 
> * Lorenzo Allegrucci <l_allegrucci@yahoo.it> wrote:
> 
> > On Wednesday 03 November 2004 18:53, Lorenzo Allegrucci wrote:
> > > On Wednesday 03 November 2004 14:46, Ingo Molnar wrote:
> > > > 
> > > > * Lorenzo Allegrucci <l_allegrucci@yahoo.it> wrote:
> > > > 
> > > > >   LD      init/built-in.o
> > > > >   LD      .tmp_vmlinux1
> > > > > net/built-in.o(.text+0x1887f): In function `netpoll_setup':
> > > > > : undefined reference to `rcu_read_lock_up_read'
> > > > > net/built-in.o(.text+0x188ed): In function `netpoll_setup':
> > > > > : undefined reference to `rcu_read_lock_up_read'
> > > > > make: *** [.tmp_vmlinux1] Error 1
> > > > 
> > > > fixed in -V0.7.3.
> > > 
> > > I've just tried V0.7.3 but my PS/2 mouse and keyboard don't work.
> > > No message from the kernel.  I attach my .config
> > 
> > Problem solved disabling ACPI.
> 
> does the same problem happen in vanilla 2.6.10-rc1-mm2 too?

No it doesn't.

-- 
I route therefore you are

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Magnus Naeslund(t)]

Ingo Molnar wrote:
> i have released the -V0.7.1 Real-Time Preemption patch, which can be
> downloaded from:
> 
>     http://redhat.com/~mingo/realtime-preempt/
> 
> this release is mainly a merge of -V0.6.9 to 2.6.10-rc2-mm2.
> 
[snip]

I just wanted to tell you that my network problems with the e100 driver 
disappeared. I still get the BUG in enable_irq, but now the network 
works. I dunno if this is due to 2.6.10-rc2-mm2 fixes or your own fixes, 
but i'm now happy :)

I'm going to try this patch on a network game server, that's pretty 
latency demanding.

Regards,
Magnus

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Magnus Naeslund(t) <mag@fbab.net> wrote:

> Ingo Molnar wrote:
> >i have released the -V0.7.1 Real-Time Preemption patch, which can be
> >downloaded from:
> >
> >    http://redhat.com/~mingo/realtime-preempt/
> >
> >this release is mainly a merge of -V0.6.9 to 2.6.10-rc2-mm2.
> >
> [snip]
> 
> I just wanted to tell you that my network problems with the e100
> driver disappeared. I still get the BUG in enable_irq, but now the
> network works. I dunno if this is due to 2.6.10-rc2-mm2 fixes or your
> own fixes, but i'm now happy :)

while doing the merge i noticed and removed an older hack i added to the
e100 driver (and the rtl8139 driver) - possibly this could be related.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

Let me follow up briefly on the regression I noticed yesterday on ping
responses from an SMP system with one real time task running. Two systems
were used for the tests, both dual 866 Mhz Pentium III systems, identical
except for the software. The "old" machine is running Red Hat 7.3 with a
2.4.24 preempt, low latency kernel. The "new" machine is running Fedora
Core 2 with a 2.6 kernel as indicated below. The other difference that may
be significant is the "old" system uses OSS and the new one uses ALSA for
the audio output (source of latencytest application is unchanged for all
three tests).

The data below is from using another machine to ping the system under test.

2.4.24 preempt + low latency on "old" machine

430 seconds for the complete series of tests
0 lost packets
0.248, 0.322, 2.82, 0.145 (min, average, max, deviation)

2.6.5-1.358smp [from fedora core 2] on "new" machine

658 seconds for the complete series of tests
0 lost packets
0.148, 0.207, 1.952, 0.097 (min, average, max, deviation)
This system also lost the mouse (screaming interrupts, IRQ 10 disabled).

2.6.9-rc3-mm3-VP-T3 on "new machine"

955 seconds for the complete series of tests
539 lost packets
0.215, 17971, 287799, 63054 (min, average, max, deviation)

I did not repeat the tests on -V0.7.7, but I expect them to come out
similar to -T3 above based on what I saw yesterday. In any case, the loss
of network data appears significant with both the voluntary preempt &
realtime preempt patches on 2.6 kernels.

--Mark H Johnson
  <mailto:Mark_H_Johnson@raytheon.com>

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Mark_H_Johnson@raytheon.com <Mark_H_Johnson@raytheon.com> wrote:

> Let me follow up briefly on the regression I noticed yesterday on ping
> responses from an SMP system with one real time task running. [...]

icmp/ping replies are handled by ksoftirqd. Once a networking request
has been handed to ksoftirqd it cannot be redirected to another CPU,
because softirq processing is fundamentally per-CPU. So if the network
interrupt hits the CPU where the RT-task is running then the RT task
will starve that ksoftirq instance (and hence the reply) even if another
CPU in the system is idle.

i agree that this is an SMP/RT artifact that should be fixed. hardirq
workload can be redirected to other CPUs because it's single-threaded,
but it's not that easy for softirq workload.

i suspect the same phenomenon causes some of the other scheduling
artifacts ('frozen' X) you've noticed.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> icmp/ping replies are handled by ksoftirqd. Once a networking request
> has been handed to ksoftirqd it cannot be redirected to another CPU,
> because softirq processing is fundamentally per-CPU. So if the network
> interrupt hits the CPU where the RT-task is running then the RT task
> will starve that ksoftirq instance (and hence the reply) even if
> another CPU in the system is idle.
> 
> i agree that this is an SMP/RT artifact that should be fixed. hardirq
> workload can be redirected to other CPUs because it's single-threaded,
> but it's not that easy for softirq workload.
> 
> i suspect the same phenomenon causes some of the other scheduling
> artifacts ('frozen' X) you've noticed.

does the ping phenomenon go away if you chrt both the networking IRQ
thread and both ksoftirqd's to above the RT task's priority? (this
doesnt solve the problem though - that task has RT priority for a reason
and on an SMP box the kernel should be able to schedule work without
getting into this starvation scenario.)

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

>does the ping phenomenon go away if you chrt both the networking IRQ
>thread and both ksoftirqd's to above the RT task's priority?

For the most part, yes. I reran the test with -V0.7.7 and had continuous
ping responses until the system locked up with yet another deadlock. This
did NOT fix the display / mouse movement lockups. All IRQ and ksoftirqd
tasks were RT 99 priority for this test. latencytest ran at RT 30 priority.

The response time while RT was active looked like this...

# ping dws77
PING dws77 (192.52.216.87) from 192.52.215.17 : 56(84) bytes of data.
64 bytes from dws77 (192.52.216.87): icmp_seq=1 ttl=63 time=0.590 ms
64 bytes from dws77 (192.52.216.87): icmp_seq=2 ttl=63 time=0.468 ms
64 bytes from dws77 (192.52.216.87): icmp_seq=3 ttl=63 time=0.542 ms
64 bytes from dws77 (192.52.216.87): icmp_seq=4 ttl=63 time=0.492 ms

Note the response times are about 2x what I saw with the other kernels.
The max delay was about 200 msec.

The deadlock was between the two ksoftirqd tasks...

===============================================
BUG: circular semaphore deadlock detected!
-----------------------------------------------
ksoftirqd/1/6 is deadlocking current task ksoftirqd/0/3


1) ksoftirqd/0/3 is trying to acquire this lock:
 [cb4640c0] {r:0,a:-1,&((sk)->sk_lock.slock)}
.. held by:       ksoftirqd/1/    6 [dff866f0,   0]
... acquired at:  tcp_delack_timer+0x22/0x220
... trying at:   tcp_v4_rcv+0x69b/0xb00

2) ksoftirqd/1/6 is blocked on this lock:
 [c03c8900] {r:2,a:-1,ptype_lock}
.. held by:       ksoftirqd/0/    3 [dffe8020,   0]
... acquired at:  net_rx_action+0x8e/0x200

------------------------------
| showing all locks held by: |  (ksoftirqd/0/3 [dffe8020,   0]):
------------------------------

#001:             [d84a7c30] {r:0,a:-1,&tp->rx_lock}
... acquired at:  rtl8139_poll+0x48/0x180 [8139too]

------------------------------
| showing all locks held by: |  (ksoftirqd/1/6 [dff866f0,   0]):
------------------------------

#001:             [cb4640c0] {r:0,a:-1,&((sk)->sk_lock.slock)}
... acquired at:  tcp_delack_timer+0x22/0x220

Appears that both were working on network operations concurrently.
Will send the full serial console log separately.

  --Mark

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Mark_H_Johnson@raytheon.com <Mark_H_Johnson@raytheon.com> wrote:

> >does the ping phenomenon go away if you chrt both the networking IRQ
> >thread and both ksoftirqd's to above the RT task's priority?
> 
> For the most part, yes. I reran the test with -V0.7.7 and had
> continuous ping responses until the system locked up with yet another
> deadlock. This did NOT fix the display / mouse movement lockups. All
> IRQ and ksoftirqd tasks were RT 99 priority for this test. latencytest
> ran at RT 30 priority.

what priority does events/0 and events/1 have? keventd handles part of
the mouse/keyboard workload.

> The deadlock was between the two ksoftirqd tasks...

there was one place missing - does the patch below fix this type of
deadlock?

	Ingo

--- linux/net/ipv4/tcp_timer.c.orig2	
+++ linux/net/ipv4/tcp_timer.c	
@@ -208,6 +208,7 @@ static void tcp_delack_timer(unsigned lo
 	struct sock *sk = (struct sock*)data;
 	struct tcp_opt *tp = tcp_sk(sk);
 
+	rcu_read_lock_read(&ptype_lock);
 	bh_lock_sock(sk);
 	if (sock_owned_by_user(sk)) {
 		/* Try again later. */
@@ -261,6 +262,7 @@ out:
 		sk_stream_mem_reclaim(sk);
 out_unlock:
 	bh_unlock_sock(sk);
+	rcu_read_unlock_read(&ptype_lock);
 	sock_put(sk);
 }
 

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Mark_H_Johnson@raytheon.com <Mark_H_Johnson@raytheon.com> wrote:

> >does the ping phenomenon go away if you chrt both the networking IRQ
> >thread and both ksoftirqd's to above the RT task's priority?
> 
> For the most part, yes. I reran the test with -V0.7.7 and had
> continuous ping responses until the system locked up with yet another
> deadlock. This did NOT fix the display / mouse movement lockups. All
> IRQ and ksoftirqd tasks were RT 99 priority for this test. latencytest
> ran at RT 30 priority.

another method would be to set all smp_affinity values in /proc/irq/*/
to 1 (i.e. let CPU#0 handle all IRQs), and start latencytest on CPU#1,
via 'taskset'. In theory this should ensure that no hardirq workload
runs on CPU#1 and thus ksoftirqd would not be active there either. (with
the exception of kernel timers started on that CPU, by latencytest.)

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

>what priority does events/0 and events/1 have? keventd handles part of
>the mouse/keyboard workload.
The default priorities and not RT.

ps -eo pid,pri,rtprio,cmd
...
  6  34    -  [events/0]
  7  34    -  [events/1]
...
I can set those as well but then I'd probably have to follow with
the X server and everything else in the chain. The starvation problem
ripples across the system.

Will try the patch shortly and get back on the results later today.

--Mark H Johnson
  <mailto:Mark_H_Johnson@raytheon.com>

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Mark_H_Johnson@raytheon.com <Mark_H_Johnson@raytheon.com> wrote:

> >what priority does events/0 and events/1 have? keventd handles part of
> >the mouse/keyboard workload.
> The default priorities and not RT.
> 
> ps -eo pid,pri,rtprio,cmd
> ...
>   6  34    -  [events/0]
>   7  34    -  [events/1]
> ...
> I can set those as well but then I'd probably have to follow with
> the X server and everything else in the chain. The starvation problem
> ripples across the system.

X should be scheduled on the other CPU just fine. Only per-CPU kernel
threads (which are affine to their particular CPU) are affected by this
problem - ordinary tasks not. I.e. the system threads that have /0 and
/1 in their name. In theory you should not even need to chrt the hardirq
threads, those should schedule fine too.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> X should be scheduled on the other CPU just fine. Only per-CPU kernel
> threads (which are affine to their particular CPU) are affected by
> this problem - ordinary tasks not. I.e. the system threads that have
> /0 and /1 in their name. In theory you should not even need to chrt
> the hardirq threads, those should schedule fine too.

plus there's the 'priority inheritance dependency-chain closure' bug
noticed by John Cooper - that should only affect the latency of RT tasks
though.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

>> I can set those as well but then I'd probably have to follow with
>> the X server and everything else in the chain. The starvation problem
>> ripples across the system.
>
>X should be scheduled on the other CPU just fine. Only per-CPU kernel
>threads (which are affine to their particular CPU) are affected by this
>problem - ordinary tasks not. I.e. the system threads that have /0 and
>/1 in their name. In theory you should not even need to chrt the hardirq
>threads, those should schedule fine too.
Perhaps "should be fine" but the test I just ran indicates otherwise.
The kernel is -V0.7.7 plus the patch you just sent me.
All IRQ and /# tasks were set to RT priority 99.

Started the X test and the display locked up almost immediately while
ping responses continued to flow on a regular basis. After several seconds
I could see the display update / move the mouse & then the display locked
up again. It went back and forth a couple cycles and did not get unstuck
until the RT audio application quit (over 250000 samples).

I will let it run to see if I can reproduce the deadlock or if the symptoms
change with one of the other tests.

--Mark H Johnson
  <mailto:Mark_H_Johnson@raytheon.com>

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

>Perhaps "should be fine" but the test I just ran indicates otherwise.
>The kernel is -V0.7.7 plus the patch you just sent me.
>All IRQ and /# tasks were set to RT priority 99.

A follow up to my previous message since the test just completed
with the following results:

2.6.10-rc1-mm2-RT-V0.7.7
181 packets lost (5%)
0.343, 2525.872, 213979, 21685 (min, average, max, deviation)
elapsed time was 3090 seconds

There was a burst of lost packets between seq 1777 and 1959,
that appears to cover all the lost ones. There was also a big
delay (up to 27305 msec) at seq 1665 through 1699 but no lost
packets. If I throw out those data points, the max drops to
something like 1800 msec and the average is in the 0.4 to 0.5
msec range.

The display lockup on the top test was a little odd. The window
that should have shown top appeared blank, stayed on the screen
for several seconds and then disappeared by itself. Apparently
top didn't even get enough CPU time to display the first cycle
before its time ran out. The audio test continued to run a while
after than & then stopped itself when the script noticed that top
was done.

The display lockups on the other tests (network and disk I/O)
were much less severe though still present at times.

--Mark H Johnson
  <mailto:Mark_H_Johnson@raytheon.com>

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[john cooper]

Ingo Molnar wrote:
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> 
>>X should be scheduled on the other CPU just fine. Only per-CPU kernel
>>threads (which are affine to their particular CPU) are affected by
>>this problem - ordinary tasks not. I.e. the system threads that have
>>/0 and /1 in their name. In theory you should not even need to chrt
>>the hardirq threads, those should schedule fine too.
> 
> 
> plus there's the 'priority inheritance dependency-chain closure' bug
> noticed by John Cooper - that should only affect the latency of RT tasks
> though.

This is a fairly gnarly problem to address.  The obvious
solution is to hold spinlocks in the mutexes as the dependency
tree is atomically traversed.  However this will deadlock under
MP due to the unpredictable order of mutexes traversed.  If the
dependency chain is not traversed (and semantics applied)
atomically, races exist which cause promotion decisions to be
made on [now] stale data.

The simple solution is a global spinlock which doesn't scale
well under MP.  Another possible solution would be conditional
traversal of the chain where contention within the chain under
foot (from another chain walker) causes the traversal to
abort and retry.  Though this has the down side of being
nondeterministic.

-- 
john.cooper@timesys.com

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Gunther Persoons]

Ingo Molnar wrote:

>i have released the -V0.7.1 Real-Time Preemption patch, which can be
>downloaded from:
>
>    http://redhat.com/~mingo/realtime-preempt/
>
>this release is mainly a merge of -V0.6.9 to 2.6.10-rc2-mm2.
>
>I havent done a proper changelog for a couple of days so here is a list
>of bigger changes since -V0.4:
>
> - implemented a first version of the priority inheritance handling and
>   priority inversion avoidance logic. This feature, after some initial
>   stability problems, solved the jackd and rtc_wakeup latencies that
>   were introduced by the ultra-finegrained locking in the -V series.
>
>   (the -T/U series had a coarser locking scheme triggered much lower
>   levels of priority inversion scenarios. The locking in the -V series
>   was clearly the tipping point.)
>
>   The new PI code covers all synchronization objects in Linux (on
>   PREEMPT_REALTIME): spinlocks, rwlocks, semaphores and rwsems. 
>   Feedback on the design of this code would be welcome, and patches as
>   well, if you have a better scheme. The code is pretty modular so feel 
>   free to experiment with alternative schemes.
>
> - completely reworked the debugging framework. All lock types
>   (spinlocks, rwlocks, semaphores and rwsems) are now tracked, both
>   their symbolic name and their place of acquire are traced and printed
>   out upon detection of a deadlock. More and better information is
>   printed upon a deadlock. Got rid of the 'semaphore owners array' in
>   debugging mode, this reduces the footprint of semaphores quite
>   significantly and speeds up deadlock detection.
>
> - got rid of the separate 'counted semaphores' implementation, it was
>   too intrusive. Made the core 'generic semaphores' implementation
>   compatible with vanilla Linux counted semaphore semantics. This also
>   enabled the unrolling of the completion-handling cleanups which,
>   while being very nice, were getting intrusive as well.
>
> - countless build and driver related reports/fixes from lots of people
>
> - more latency breaks in the remaining critical sections. A
>   particularly important one was the irqs-off latency bugfix from
>   Thomas Gleixner.
>
> - sped up the i8259 PIC and the PIT timer hardirq handling routines -
>   these are now in the path of the longest latency.
>
> - cleaned up IRQ and signal preemption - there were missed
>   check-rescheds and possibilities for IRQ recursion.
>
> - made ALSA's ioctl()s not use the BKL - this fixes more jackd
>   latencies.
>
>to create a -V0.7.1 tree from scratch, the patching order is:
>
>   http://kernel.org/pub/linux/kernel/v2.6/linux-2.6.9.tar.bz2
>   http://kernel.org/pub/linux/kernel/v2.6/testing/patch-2.6.10-rc1.bz2
>   http://kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.10-rc1/2.6.10-rc1-mm2/2.6.10-rc1-mm2.bz2
>   http://redhat.com/~mingo/realtime-preempt/realtime-preempt-2.6.10-rc1-mm2-V0.7.1
>
>	Ingo
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/
>
>  
>
Hey,
I get a lock up with my wireless pcmcia cisco card. When i try to run to 
dhcpcd command or iwconfig it just hangs. Also when
i insert my card at boot time it hangs when running the net init 
scripts. I had this with version V0.7.8 and V0.7.10, have tested any 
other RT patches, i didn't have this problem with VP-T3. Also i can now 
mount and use my reiser4 partition.

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Mark_H_Johnson]

>there was one place missing - does the patch below fix this type of
>deadlock?

A different deadlock this time, same two actors but apparently a
different pair of locks.

Will send the full console log shortly.
  --Mark


===============================================
BUG: circular semaphore deadlock detected!
-----------------------------------------------
ksoftirqd/1/6 is deadlocking current task ksoftirqd/0/3


1) ksoftirqd/0/3 is trying to acquire this lock:
 [dfb5c8a4] {r:0,a:-1,&n->lock}
.. held by:       ksoftirqd/1/    6 [dff886f0,   0]
... acquired at:  arp_solicit+0x167/0x230
... trying at:   neigh_update+0x2a/0x390

2) ksoftirqd/1/6 is blocked on this lock:
 [c03c8900] {r:1,a:-1,ptype_lock}
.. held by:       ksoftirqd/0/    3 [dffe8020,   0]
... acquired at:  net_rx_action+0x8e/0x200

------------------------------
| showing all locks held by: |  (ksoftirqd/0/3 [dffe8020,   0]):
------------------------------

#001:             [d9044c30] {r:0,a:-1,&tp->rx_lock}
... acquired at:  rtl8139_poll+0x48/0x180 [8139too]

------------------------------
| showing all locks held by: |  (ksoftirqd/1/6 [dff886f0,   0]):
------------------------------

#001:             [dfb5c8a4] {r:0,a:-1,&n->lock}
... acquired at:  arp_solicit+0x167/0x230

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* john cooper <john.cooper@timesys.com> wrote:

> > plus there's the 'priority inheritance dependency-chain closure' bug
> > noticed by John Cooper - that should only affect the latency of RT 
> > tasks though.
> 
> This is a fairly gnarly problem to address.  The obvious solution is
> to hold spinlocks in the mutexes as the dependency tree is atomically
> traversed.  However this will deadlock under MP due to the
> unpredictable order of mutexes traversed.  If the dependency chain is
> not traversed (and semantics applied) atomically, races exist which
> cause promotion decisions to be made on [now] stale data.

is the order of locks in the dependency chain really unpredictable? If
two chain walkers get two locks in opposite order, doesnt that mean that
the lock ordering (as attempted by the blocked tasks) is deadlock-prone
already? I.e. this scenario should not happen.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Mark_H_Johnson@raytheon.com <Mark_H_Johnson@raytheon.com> wrote:

> 1) ksoftirqd/0/3 is trying to acquire this lock:
>  [dfb5c8a4] {r:0,a:-1,&n->lock}
> .. held by:       ksoftirqd/1/    6 [dff886f0,   0]
> ... acquired at:  arp_solicit+0x167/0x230
> ... trying at:   neigh_update+0x2a/0x390
> 
> 2) ksoftirqd/1/6 is blocked on this lock:
>  [c03c8900] {r:1,a:-1,ptype_lock}
> .. held by:       ksoftirqd/0/    3 [dffe8020,   0]
> ... acquired at:  net_rx_action+0x8e/0x200

this is a weird one. Note how ptype_lock is not shown to be owned by
ksoftirqd/0/3:

> ------------------------------
> | showing all locks held by: |  (ksoftirqd/0/3 [dffe8020,   0]):
> ------------------------------
> 
> #001:             [d9044c30] {r:0,a:-1,&tp->rx_lock}
> ... acquired at:  rtl8139_poll+0x48/0x180 [8139too]

neither does ptype_lock show up in the other logs you sent.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Chris Friesen]

> Ingo Molnar wrote:

>> - implemented a first version of the priority inheritance handling and
>>   priority inversion avoidance logic. This feature, after some initial
>>   stability problems, solved the jackd and rtc_wakeup latencies that
>>   were introduced by the ultra-finegrained locking in the -V series.

How does this play with Inaky's priority inheritance patch?  Could they be 
combined somehow?

Chris

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[john cooper]

Ingo Molnar wrote:
> * john cooper <john.cooper@timesys.com> wrote:
> 
> 
>>>plus there's the 'priority inheritance dependency-chain closure' bug
>>>noticed by John Cooper - that should only affect the latency of RT 
>>>tasks though.
>>
>>This is a fairly gnarly problem to address.  The obvious solution is
>>to hold spinlocks in the mutexes as the dependency tree is atomically
>>traversed.  However this will deadlock under MP due to the
>>unpredictable order of mutexes traversed.  If the dependency chain is
>>not traversed (and semantics applied) atomically, races exist which
>>cause promotion decisions to be made on [now] stale data.
> 
> 
> is the order of locks in the dependency chain really unpredictable? If
> two chain walkers get two locks in opposite order, doesnt that mean that
> the lock ordering (as attempted by the blocked tasks) is deadlock-prone
> already? I.e. this scenario should not happen.

There does appear to be hope here.  If the per-task mutex ownership
list is maintained in strict order of acquisition sequence and
reader-mutex acquisition sequence is policed this would seem to remove
the possibly of chain traversal deadlock.

As an implementation note, single-owner hard spinlocks seem
excessive for the chain walk.  An approach allowing maximum
concurrency during traversal would be a reader-reference acquired
per node during the walk which would need to upgrade to an exclusive
writer-reference to effect promotion (waiter list priority reorder),
and then downgrade to a reader-reference to continue the traversal.

-john


-- 
john.cooper@timesys.com

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Scott Wood]

On Thu, Nov 04, 2004 at 08:44:16PM +0100, Ingo Molnar wrote:
> 
> * john cooper <john.cooper@timesys.com> wrote:
> > 
> > This is a fairly gnarly problem to address.  The obvious solution is
> > to hold spinlocks in the mutexes as the dependency tree is atomically
> > traversed.  However this will deadlock under MP due to the
> > unpredictable order of mutexes traversed.  If the dependency chain is
> > not traversed (and semantics applied) atomically, races exist which
> > cause promotion decisions to be made on [now] stale data.
> 
> is the order of locks in the dependency chain really unpredictable? If
> two chain walkers get two locks in opposite order, doesnt that mean that
> the lock ordering (as attempted by the blocked tasks) is deadlock-prone
> already? I.e. this scenario should not happen.

It *shouldn't*, but bugs do happen, and it'd be nice if a mutex
deadlock didn't get promoted into a less debuggable spinlock
deadlock.  Plus, if there's any intention of ever exporting this
priority inheritance mechanism to userspace locks, we don't want to
promote a userspace deadlock into a kernel one.

Given how rarely contention should occur, I don't think that a single
lock would be a bottleneck except for obscenely large SMP machines.

-Scott

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Bill Huey]

On Fri, Nov 05, 2004 at 04:42:38PM -0500, Scott Wood wrote:
> On Thu, Nov 04, 2004 at 08:44:16PM +0100, Ingo Molnar wrote:
> > is the order of locks in the dependency chain really unpredictable? If
> > two chain walkers get two locks in opposite order, doesnt that mean that
> > the lock ordering (as attempted by the blocked tasks) is deadlock-prone
> > already? I.e. this scenario should not happen.
> 
> It *shouldn't*, but bugs do happen, and it'd be nice if a mutex
> deadlock didn't get promoted into a less debuggable spinlock
> deadlock.  Plus, if there's any intention of ever exporting this
> priority inheritance mechanism to userspace locks, we don't want to
> promote a userspace deadlock into a kernel one.
> 
> Given how rarely contention should occur, I don't think that a single
> lock would be a bottleneck except for obscenely large SMP machines.

Places that are surround by rcu locks are possibilities that could
hit the kind of contention. There's numerous places in the kernel
that use it, but nothing can be said until there's stats on how these
things content against each other, dcache_lock, I believe and others.

I think of an RT kernel with N threads in terms where it's an SMP
machine with same N number of processors. If you have N threads
pounding on the same critical sections, it's effectively N physical
processors hitting as well.

Correct me if I'm wrong, vague, etc...  but that's how I understand
the problem and that's how I think it should be addressed. Ideally,
the kernel should be so efficient that these collision should never
happen and the use of priority propagation should be very shallow
to prevent irregularities with scheduling resulting from priority
boosting lock chains. Only a statically gathering of how this system
behaves will show the technical direction that this project should
direct itself.

BTW, we're working getting a single super-mutex that right now
internally that can possibly be used for proper priority propagation,
for all blocking type locks. Hopefully, with testing we'll see how
well it and the rest of the kernel performs with it. Correctness is
is the highest priority, but overall behavior of the system is very
important and should be next in ranking IMO.

bill

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Scott Wood <scott@timesys.com> wrote:

> > is the order of locks in the dependency chain really unpredictable? If
> > two chain walkers get two locks in opposite order, doesnt that mean that
> > the lock ordering (as attempted by the blocked tasks) is deadlock-prone
> > already? I.e. this scenario should not happen.
> 
> It *shouldn't*, but bugs do happen, and it'd be nice if a mutex
> deadlock didn't get promoted into a less debuggable spinlock deadlock.
> [...]

well, deadlock detection happens at lock-acquire time, so the deadlock
will be detected _first_, any PI spinlock-locking will happen on already
blocked (== no deadlock detected) tasks. This would also serve as a nice
secondary check for the deadlock detector.

> [...] Plus, if there's any intention of ever exporting this priority
> inheritance mechanism to userspace locks, we don't want to promote a
> userspace deadlock into a kernel one.

agreed.

> Given how rarely contention should occur, I don't think that a single
> lock would be a bottleneck except for obscenely large SMP machines.

well, blocking on a mutex happens quite frequently. But i dont have a
problem with the big lock other than the usual "if we can do better then
we should do better" attitude :-)

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Esben Nielsen]

On Fri, 5 Nov 2004, Bill Huey wrote:

> [...] 
> I think of an RT kernel with N threads in terms where it's an SMP
> machine with same N number of processors. If you have N threads
> pounding on the same critical sections, it's effectively N physical
> processors hitting as well.
> 

Not quite. On a UP RT system you know that all lower priority tasks are
not running when your task is running. This gives some nice
properties. If you take care not to sleep your high priority task
effectively blocks all preemption by the lower priority tasks.

On a SMB system you don't have these nice properties. You always have to
take into account that N processes are really running at the same time.

On UP RT systems it is legal to think like this: The processor can
only do one thing. For the overall performance I can just as well lock the
rest out with one big mutex and get my work done in a hurry. This gives
simpler code and it is more efficient since locking/unlocking sections 
takes time. It doesn't destroy the latency of the subsystem as long as you
can verify that the maximum locking time is less than the required latency
for that subsystem. If I can even keep my locking time below the maximum
allowed interrupt latency I can optimize it further by using 
interrupt disable/enable instead of a mutex!

On SMB systems, on the other hand, this gives bad performance to have such
big locking sections. Especially if you use the equivalent of interrupt
disable/enable (spinlocks) you are not only slowing down your own
subsystem but the whole system.

In short: For SMB you have to think of parellization much more than on a
UP RT system. Ofcourse to think of UP RT system as a SMB system doesn't
make your system fail, but it might give you a suboptimal system. On the
other hand a system running on a UP with full preemption might not be
portable to a SMB system as you might be saved by "the nice properties". 
So if you want to be portable, think of it as a SMB system :-)

> [...]
> 
> bill
> 

Esben

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> On a SMP system you don't have these nice properties. You always have
> to take into account that N processes are really running at the same
> time.

not necessarily. In theory we could introduce the notion of
"hyper-high-priority tasks" (e.g. SCHED_HYPER_FIFO), which tasks not
only get preempted on one CPU immediately, but cause the kernel to stop
and loop on all other CPUs as well. That way the same 'nice' properties
of UP kernels get carried over to the SMP system as well, at the cost of
serializing all execution while the hyper-high-prio task is running. 
Once the task stops running, the other CPUs can continue as well.

	Ingo

Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[Bill Huey]

On Mon, Nov 08, 2004 at 03:35:38PM +0100, Esben Nielsen wrote:
> Not quite. On a UP RT system you know that all lower priority tasks are
> not running when your task is running. This gives some nice
> properties. If you take care not to sleep your high priority task
> effectively blocks all preemption by the lower priority tasks.
... 
> In short: For SMB you have to think of parellization much more than on a
> UP RT system. Ofcourse to think of UP RT system as a SMB system doesn't
> make your system fail, but it might give you a suboptimal system. On the
> other hand a system running on a UP with full preemption might not be
> portable to a SMB system as you might be saved by "the nice properties". 
> So if you want to be portable, think of it as a SMB system :-)

Yeah, good points. I know, I'm being paranoid intentionally since much 
of the kernel is so SMP oriented. I'm thinking in terms of large scale
concurrency since the structures of the kernel are fundamentally SMP and
which is tightly related to RT performance. There's a lot of overlap
between both world as it concerns locking structures, fine grainedness.

The really appealing aspect of this project that the same things that
make Linux such a high performance SMP system out of the box is exactly
what will also give it outstanding RT performance in both UP and SMP
configurations. The fine grained locking issues seem to be largely done
and this work is going to push those boundaries even more.

I know what you're saying about thread run subsets with relation to
priority (again good points), but I'm looking at large picture issues
and how this system is going to behave as all parts work together. We
haven't done this just yet and it's too immature a system to do so
until it becomes more stable and popular. It's a different point of 
view than what you're talking about. :)

bill