Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Paul McKenney]

> > I see your point here, but need to think about it.  One question:
> > isn't it the case that the alternative to using synchronize_kernel()
> > is to protect the read side with explicit locks, which will themselves
> > suppress preemption?  If so, why not just suppress preemption on the
read
> > side in preemptible kernels, and thus gain the simpler implementation
> > of synchronize_kernel()?  You are not losing any preemption latency
> > compared to a kernel that uses traditional locks, in fact, you should
> > improve latency a bit since the lock operations are more expensive than
> > are simple increments and decrements.  As usual, what am I missing
> > here?  ;-)
>
> Already preempted tasks.

But if you are suppressing preemption in all read-side critical sections,
then wouldn't any already-preempted tasks be guaranteed to -not- be in
a read-side critical section, and therefore be guaranteed to be unaffected
by the update (in other words, wouldn't such tasks not need to be waited
for)?

> > Another approach would be to define a "really low" priority that noone
> > other than synchronize_kernel() was allowed to use.  Then the UP
> > implementation of synchronize_kernel() could drop its priority to
> > this level, yield the CPU, and know that all preempted tasks must
> > have obtained and voluntarily yielded the CPU before synchronize_kernel
()
> > gets it back again.
>
> Or "never", because I'm running RC5 etc. 8(.

Ummmm...  Good point!  Never mind use of low priorities in UP kernels
for synchronize_kernel()...

                                   Thanx, Paul

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Rusty Russell]

In message <OF42269F5F.CDF56B0F-ON88256A27.0083566F@LocalDomain> you write:
> > Already preempted tasks.
> 
> But if you are suppressing preemption in all read-side critical sections,
> then wouldn't any already-preempted tasks be guaranteed to -not- be in
> a read-side critical section, and therefore be guaranteed to be unaffected
> by the update (in other words, wouldn't such tasks not need to be waited
> for)?

Ah, if you want to inc and dec all the time, yes.  But even if the
performance isn't hurt, it's unneccessary, and something else people
have to remember to do.

Simplicity is very nice.  And in the case of module unload, gives us
the ability to avoid the distinction between "am I calling into a
module?" and "is this fixed in the kernel?" at runtime.  A very good
thing 8)

Rusty.
--
Premature optmztion is rt of all evl. --DK

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Paul McKenney]

> > But if you are suppressing preemption in all read-side critical
sections,
> > then wouldn't any already-preempted tasks be guaranteed to -not- be in
> > a read-side critical section, and therefore be guaranteed to be
unaffected
> > by the update (in other words, wouldn't such tasks not need to be
waited
> > for)?
>
> Ah, if you want to inc and dec all the time, yes.  But even if the
> performance isn't hurt, it's unneccessary, and something else people
> have to remember to do.

I must admit that free is a very good price.

> Simplicity is very nice.  And in the case of module unload, gives us
> the ability to avoid the distinction between "am I calling into a
> module?" and "is this fixed in the kernel?" at runtime.  A very good
> thing 8)

Is it also desireable to avoid the distinction between "the currently
executing code is in a module" and "the currently executing code is
fixed in the kernel"?

> Rusty.

                              Thanx, Paul

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Paul McKenney]

> On Tue, 10 Apr 2001, Paul McKenney wrote:
> > The algorithms we have been looking at need to have absolute guarantees
> > that earlier activity has completed.  The most straightforward way to
> > guarantee this is to have the critical-section activity run with
preemption
> > disabled.  Most of these code segments either take out locks or run
> > with interrupts disabled anyway, so there is little or no degradation
of
> > latency in this case.  In fact, in many cases, latency would actually
be
> > improved due to removal of explicit locking primitives.
> >
> > I believe that one of the issues that pushes in this direction is the
> > discovery that "synchronize_kernel()" could not be a nop in a UP kernel
> > unless the read-side critical sections disable preemption (either in
> > the natural course of events, or artificially if need be).  Andi or
> > Rusty can correct me if I missed something in the previous exchange...
> >
> > The read-side code segments are almost always quite short, and, again,
> > they would almost always otherwise need to be protected by a lock of
> > some sort, which would disable preemption in any event.
> >
> > Thoughts?
>
> Disabling preemption is a possible solution if the critical section is
short
> - less than 100us - otherwise preemption latencies become a problem.

Seems like a reasonable restriction.  Of course, this same limit applies
to locks and interrupt disabling, right?

> The implementation of synchronize_kernel() that Rusty and I discussed
> earlier in this thread would work in other cases, such as module
> unloading, where there was a concern that it was not practical to have
> any sort of lock in the read-side code path and the write side was not
> time critical.

True, but only if the synchronize_kernel() implementation is applied to UP
kernels, also.

                    Thanx, Paul

> Nigel Gamble                                    nigel@nrg.org
> Mountain View, CA, USA.                         http://www.nrg.org/
>
> MontaVista Software                             nigel@mvista.com

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[yodaiken]

On Tue, Apr 10, 2001 at 09:08:16PM -0700, Paul McKenney wrote:
> > Disabling preemption is a possible solution if the critical section is
> short
> > - less than 100us - otherwise preemption latencies become a problem.
> 
> Seems like a reasonable restriction.  Of course, this same limit applies
> to locks and interrupt disabling, right?

So supposing 1/2 us per update
	lock process list
		for every process update pgd
	unlock process list

is ok if #processes <  200, but can cause some unspecified system failure
due to a dependency on the 100us limit otherwise?

And on a slower machine or with some heavy I/O possibilities ....

We have a tiny little kernel to worry about inRTLinux and it's quite 
hard for us to keep track of all possible delays in such cases. How's this
going to work for Linux?

	
-- 
---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Nigel Gamble]

On Tue, 10 Apr 2001 yodaiken@fsmlabs.com wrote:
> On Tue, Apr 10, 2001 at 09:08:16PM -0700, Paul McKenney wrote:
> > > Disabling preemption is a possible solution if the critical section is
> > short
> > > - less than 100us - otherwise preemption latencies become a problem.
> > 
> > Seems like a reasonable restriction.  Of course, this same limit applies
> > to locks and interrupt disabling, right?
> 
> So supposing 1/2 us per update
> 	lock process list
> 		for every process update pgd
> 	unlock process list
> 
> is ok if #processes <  200, but can cause some unspecified system failure
> due to a dependency on the 100us limit otherwise?

Only to a hard real-time system.

> And on a slower machine or with some heavy I/O possibilities ....

I'm mostly interested in Linux in embedded systems, where we have a lot
of control over the overall system, such as how many processes are
running.  This makes it easier to control latencies than on a
general purpose computer.

> We have a tiny little kernel to worry about inRTLinux and it's quite 
> hard for us to keep track of all possible delays in such cases. How's this
> going to work for Linux?

The same way everything works for Linux:  with enough people around the
world interested in and working on these problems, they will be fixed.

Nigel Gamble                                    nigel@nrg.org
Mountain View, CA, USA.                         http://www.nrg.org/

MontaVista Software                             nigel@mvista.com

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Nigel Gamble]

On Tue, 10 Apr 2001, Paul McKenney wrote:
> > Disabling preemption is a possible solution if the critical section
> > is
> short
> > - less than 100us - otherwise preemption latencies become a problem.
> 
> Seems like a reasonable restriction.  Of course, this same limit
> applies to locks and interrupt disabling, right?

That's the goal I'd like to see us achieve in 2.5.  Interrupts are
already in this range (with a few notable exceptions), but there is
still the big kernel lock and a few other long held spin locks to deal
with.  So I want to make sure that any new locking scheme like the ones
under discussion play nicely with the efforts to achieve low-latency
Linux such as the preemptible kernel.

> > The implementation of synchronize_kernel() that Rusty and I
> > discussed earlier in this thread would work in other cases, such as
> > module unloading, where there was a concern that it was not
> > practical to have any sort of lock in the read-side code path and
> > the write side was not time critical.
> 
> True, but only if the synchronize_kernel() implementation is applied
> to UP kernels, also.

Yes, that is the idea.

Nigel Gamble                                    nigel@nrg.org
Mountain View, CA, USA.                         http://www.nrg.org/

MontaVista Software                             nigel@mvista.com

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Paul McKenney]

> > As you've observed, with the approach of waiting for all pre-empted
tasks
> > to synchronize, the possibility of a task staying pre-empted for a long
> > time could affect the latency of an update/synchonize (though its hard
for
> > me to judge how likely that is).
>
> It's very unlikely on a system that doesn't already have problems with
> CPU starvation because of runaway real-time tasks or interrupt handlers.

Agreed!

> First, preemption is a comparitively rare event with a mostly
> timesharing load, typically from 1% to 10% of all context switches.

Again, agreed!

> Second, the scheduler should not penalize the preempted task for being
> preempted, so that it should usually get to continue running as soon as
> the preempting task is descheduled, which is at most one timeslice for
> timesharing tasks.

The algorithms we have been looking at need to have absolute guarantees
that earlier activity has completed.  The most straightforward way to
guarantee this is to have the critical-section activity run with preemption
disabled.  Most of these code segments either take out locks or run
with interrupts disabled anyway, so there is little or no degradation of
latency in this case.  In fact, in many cases, latency would actually be
improved due to removal of explicit locking primitives.

I believe that one of the issues that pushes in this direction is the
discovery that "synchronize_kernel()" could not be a nop in a UP kernel
unless the read-side critical sections disable preemption (either in
the natural course of events, or artificially if need be).  Andi or
Rusty can correct me if I missed something in the previous exchange...

The read-side code segments are almost always quite short, and, again,
they would almost always otherwise need to be protected by a lock of
some sort, which would disable preemption in any event.

Thoughts?

                              Thanx, Paul

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Nigel Gamble]

On Tue, 10 Apr 2001, Paul McKenney wrote:
> The algorithms we have been looking at need to have absolute guarantees
> that earlier activity has completed.  The most straightforward way to
> guarantee this is to have the critical-section activity run with preemption
> disabled.  Most of these code segments either take out locks or run
> with interrupts disabled anyway, so there is little or no degradation of
> latency in this case.  In fact, in many cases, latency would actually be
> improved due to removal of explicit locking primitives.
>
> I believe that one of the issues that pushes in this direction is the
> discovery that "synchronize_kernel()" could not be a nop in a UP kernel
> unless the read-side critical sections disable preemption (either in
> the natural course of events, or artificially if need be).  Andi or
> Rusty can correct me if I missed something in the previous exchange...
> 
> The read-side code segments are almost always quite short, and, again,
> they would almost always otherwise need to be protected by a lock of
> some sort, which would disable preemption in any event.
> 
> Thoughts?

Disabling preemption is a possible solution if the critical section is short
- less than 100us - otherwise preemption latencies become a problem.

The implementation of synchronize_kernel() that Rusty and I discussed
earlier in this thread would work in other cases, such as module
unloading, where there was a concern that it was not practical to have
any sort of lock in the read-side code path and the write side was not
time critical.

Nigel Gamble                                    nigel@nrg.org
Mountain View, CA, USA.                         http://www.nrg.org/

MontaVista Software                             nigel@mvista.com

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[bsuparna]

>One question:
>isn't it the case that the alternative to using synchronize_kernel()
>is to protect the read side with explicit locks, which will themselves
>suppress preemption?  If so, why not just suppress preemption on the read
>side in preemptible kernels, and thus gain the simpler implementation
>of synchronize_kernel()?  You are not losing any preemption latency
>compared to a kernel that uses traditional locks, in fact, you should
>improve latency a bit since the lock operations are more expensive than
>are simple increments and decrements.  As usual, what am I missing
>here?  ;-)
>...
>...
>I still prefer suppressing preemption on the read side, though I
>suppose one could claim that this is only because I am -really-
>used to it.  ;-)

Since this point has come up , I just wanted to mention that it may still
be nice to be able to do without explicit locks on the read-side. This is
not so much for performance reasons (I agree with your assessment on that
point) as for convinience / flexibility in the kind of situations where
this concept (i.e. synchronize_kernel or read-copy-update) could be used.

For example, consider situations where it is an executable code block that
is being protected. The read side is essentially the execution of that code
block - i.e. every entry/exit into the code block.

This is perhaps the case with module unload races. Having to acquire a
read-lock explicitly before every entry point seems to reduce  the
simplicity of the solution, doesn't it ?

This is also the case with kernel code patching, which I agree, may appear
to be a rather unlikely application of this concept to handle races in
multi-byte code patching on a running kernel, a rather difficult problem,
otherwise.  In this case, the read-side is totally unaware of the
possibility of an updater modifying the code, so it isn't even possible for
a read-lock to be acquired explicitly (if we wish to have the flexibility
of being able to patch any portion of the code).

Have been discussing this with Dipankar last week, so I realize that the
above situations were perhaps not what these locking mechanisms were
intended for, but just thought I'd bring up this perspective.

As you've observed, with the approach of waiting for all pre-empted tasks
to synchronize, the possibility of a task staying pre-empted for a long
time could affect the latency of an update/synchonize (though its hard for
me to judge how likely that is). Besides, as Andi pointed out, there
probably are a lot of situations where the readers are not pre-emptible
anyway, so that waiting for all pre-empted tasks may be superfluos.

Given these possibilities, does it make sense to simply let the
updater/synchronize kernel specify an option indicating whether it would
wait for pre-empted tasks or not ?

Regards
Suparna


  Suparna Bhattacharya
  IBM Software Lab, India
  E-mail : bsuparna@in.ibm.com
  Phone : 91-80-5267117, Extn : 2525

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Nigel Gamble]

On Mon, 9 Apr 2001 bsuparna@in.ibm.com wrote:
> As you've observed, with the approach of waiting for all pre-empted tasks
> to synchronize, the possibility of a task staying pre-empted for a long
> time could affect the latency of an update/synchonize (though its hard for
> me to judge how likely that is).

It's very unlikely on a system that doesn't already have problems with
CPU starvation because of runaway real-time tasks or interrupt handlers.

First, preemption is a comparitively rare event with a mostly
timesharing load, typically from 1% to 10% of all context switches.

Second, the scheduler should not penalize the preempted task for being
preempted, so that it should usually get to continue running as soon as
the preempting task is descheduled, which is at most one timeslice for
timesharing tasks.

Nigel Gamble                                    nigel@nrg.org
Mountain View, CA, USA.                         http://www.nrg.org/
MontaVista Software                             nigel@mvista.com

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Paul McKenney]

> > > > 2.   Isn't it possible to get in trouble even on a UP if a task
> > > >      is preempted in a critical region?  For example, suppose the
> > > >      preempting task does a synchronize_kernel()?
> > >
> > > Ugly. I guess one way to solve it would be to readd the 2.2 scheduler
> > > taskqueue, and just queue a scheduler callback in this case.
> >
> > Another approach would be to define a "really low" priority that noone
> > other than synchronize_kernel() was allowed to use.  Then the UP
> > implementation of synchronize_kernel() could drop its priority to
> > this level, yield the CPU, and know that all preempted tasks must
> > have obtained and voluntarily yielded the CPU before synchronize_kernel
()
> > gets it back again.
>
> That just would allow nasty starvation, e.g. when someone runs a cpu
intensive
> screensaver or a seti-at-home.

Good point!  I hereby withdraw my suggested use of ultra-low priorities
for UP implementations of synchronize_kernel().  ;-)

> > I still prefer suppressing preemption on the read side, though I
> > suppose one could claim that this is only because I am -really-
> > used to it.  ;-)
>
> For a lot of reader cases non-preemption by threads is guaranteed anyways
--
> e.g.  anything that runs in interrupts, timers, tasklets and network
softirq.
> I think that already covers a lot of interesting cases.

Good point again!  For example, this does cover most of the TCP/IP
cases, right?

                              Thanx, Paul

Re: [PATCH for 2.5] preemptible kernel

[Paul McKenney]

Andi, thank you for the background!  More comments interspersed...

> On Fri, Apr 06, 2001 at 04:52:25PM -0700, Paul McKenney wrote:
> > 1.   On a busy system, isn't it possible for a preempted task
> >      to stay preempted for a -long- time, especially if there are
> >      lots of real-time tasks in the mix?
>
> The problem you're describing is probably considered too hard to
> solve properly (bad answer, but that is how it is currently)
>
> Yes there is. You can also force a normal (non preemptive) kernel
> into complete livelock by just giving it enough network traffic
> to do, so that it always works in the high priority network
> softirq or doing the same with some other interrupt.
>
> Just when this happens a lot of basic things will stop working (like
> page cleaning, IO flushing etc.), so your callbacks or module unloads
> not running are probably the least of your worries.
>
> The same problem applies to a smaller scale to real time processes;
> kernel services normally do not run real-time, so they can be starved.
>
> Priority inversion is not handled in Linux kernel ATM BTW, there
> are already situations where a realtime task can cause a deadlock
> with some lower priority system thread (I believe there is at least
> one case of this known with realtime ntpd on 2.4)

I see your point here, but need to think about it.  One question:
isn't it the case that the alternative to using synchronize_kernel()
is to protect the read side with explicit locks, which will themselves
suppress preemption?  If so, why not just suppress preemption on the read
side in preemptible kernels, and thus gain the simpler implementation
of synchronize_kernel()?  You are not losing any preemption latency
compared to a kernel that uses traditional locks, in fact, you should
improve latency a bit since the lock operations are more expensive than
are simple increments and decrements.  As usual, what am I missing
here?  ;-)

> > 2.   Isn't it possible to get in trouble even on a UP if a task
> >      is preempted in a critical region?  For example, suppose the
> >      preempting task does a synchronize_kernel()?
>
> Ugly. I guess one way to solve it would be to readd the 2.2 scheduler
> taskqueue, and just queue a scheduler callback in this case.

Another approach would be to define a "really low" priority that noone
other than synchronize_kernel() was allowed to use.  Then the UP
implementation of synchronize_kernel() could drop its priority to
this level, yield the CPU, and know that all preempted tasks must
have obtained and voluntarily yielded the CPU before synchronize_kernel()
gets it back again.

I still prefer suppressing preemption on the read side, though I
suppose one could claim that this is only because I am -really-
used to it.  ;-)

                              Thanx, Paul

Re: [Lse-tech] Re: [PATCH for 2.5] preemptible kernel

[Andi Kleen]

On Fri, Apr 06, 2001 at 06:25:36PM -0700, Paul McKenney wrote:
> I see your point here, but need to think about it.  One question:
> isn't it the case that the alternative to using synchronize_kernel()
> is to protect the read side with explicit locks, which will themselves
> suppress preemption?  If so, why not just suppress preemption on the read
> side in preemptible kernels, and thus gain the simpler implementation
> of synchronize_kernel()?  You are not losing any preemption latency
> compared to a kernel that uses traditional locks, in fact, you should
> improve latency a bit since the lock operations are more expensive than
> are simple increments and decrements.  As usual, what am I missing
> here?  ;-)

You miss nothing I think. In fact it's already used (see below) 

> 
> > > 2.   Isn't it possible to get in trouble even on a UP if a task
> > >      is preempted in a critical region?  For example, suppose the
> > >      preempting task does a synchronize_kernel()?
> >
> > Ugly. I guess one way to solve it would be to readd the 2.2 scheduler
> > taskqueue, and just queue a scheduler callback in this case.
> 
> Another approach would be to define a "really low" priority that noone
> other than synchronize_kernel() was allowed to use.  Then the UP
> implementation of synchronize_kernel() could drop its priority to
> this level, yield the CPU, and know that all preempted tasks must
> have obtained and voluntarily yielded the CPU before synchronize_kernel()
> gets it back again.

That just would allow nasty starvation, e.g. when someone runs a cpu intensive
screensaver or a seti-at-home.

> 
> I still prefer suppressing preemption on the read side, though I
> suppose one could claim that this is only because I am -really-
> used to it.  ;-)

For a lot of reader cases non-preemption by threads is guaranteed anyways -- 
e.g.  anything that runs in interrupts, timers, tasklets and network softirq.  
I think that already covers a lot of interesting cases.


-Andi