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

> > 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 t

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

In message 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 there

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

On Tue, 10 Apr 2001 [EMAIL PROTECTED] 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 reas

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

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 int

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

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 >

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

> 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

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

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

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

> > 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

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

On Mon, 9 Apr 2001 [EMAIL PROTECTED] 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 th

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

>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 implement

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

> > > > 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 > > > taskq

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

> > 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 >

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

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?

Re: [PATCH for 2.5] preemptible kernel

In message you write: > > 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 cas

Re: [PATCH for 2.5] preemptible kernel

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 t

Re: [PATCH for 2.5] preemptible kernel

Hallo, 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 consider

Re: [PATCH for 2.5] preemptible kernel

Please accept my apologies if I am missing something basic, but... 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? 2. Isn't it possible to get in trouble even on a UP if a t

Re: [PATCH for 2.5] preemptible kernel

In message <[EMAIL PROTECTED]> you write : > > Setting a running task's flags brings races, AFAICT, and checking > > p->state is NOT sufficient, consider wait_event(): you need p->has_cpu > > here I think. > > My thought here was that if p->state is anything other than TASK_RUNNING > or TASK_RUNN

Re: [PATCH for 2.5] preemptible kernel

In message <[EMAIL PROTECTED]> you write: > On a higher level, I think the scanning of the run list to set flags and > counters is a bit off. [snip standard refcnt scheme] For most things, refcnts are great. I use them in connection tracking. But when writes can be insanely slow (eg. once per

Re: [PATCH for 2.5] preemptible kernel

Nigel Gamble wrote: > > On Sat, 31 Mar 2001, george anzinger wrote: > > I think this should be: > > if (p->has_cpu || p->state & TASK_PREEMPTED)) { > > to catch tasks that were preempted with other states. > > But the other states are all part of the state change that happens at

Re: [PATCH for 2.5] preemptible kernel

On Sat, 31 Mar 2001, Rusty Russell wrote: > > if (p->state == TASK_RUNNING || > > (p->state == (TASK_RUNNING|TASK_PREEMPTED))) { > > p->flags |= PF_SYNCING; > > Setting a running task's flags brings races, AFAICT, and checking > p->state

Re: [PATCH for 2.5] preemptible kernel

On Sat, 31 Mar 2001, george anzinger wrote: > I think this should be: > if (p->has_cpu || p->state & TASK_PREEMPTED)) { > to catch tasks that were preempted with other states. But the other states are all part of the state change that happens at a non-preemtive schedule() point, a

Re: [PATCH for 2.5] preemptible kernel

Rusty Russell wrote: > > In message <[EMAIL PROTECTED]> you write: > > Here is an attempt at a possible version of synchronize_kernel() that > > should work on a preemptible kernel. I haven't tested it yet. > > It's close, but... > > Those who suggest that we don't do preemtion on SMP make thi

Re: [PATCH for 2.5] preemptible kernel

In message <[EMAIL PROTECTED]> you write: > Here is an attempt at a possible version of synchronize_kernel() that > should work on a preemptible kernel. I haven't tested it yet. It's close, but... Those who suggest that we don't do preemtion on SMP make this much easier (synchronize_kernel() is

Re: [PATCH for 2.5] preemptible kernel

On Wed, 28 Mar 2001 12:51:02 -0800, george anzinger <[EMAIL PROTECTED]> wrote: >Dipankar Sarma wrote: >> 1. Disable pre-emption during the time when references to data >> structures >> updated using such Two-phase updates are held. > >Doesn't this fly in the face of the whole Two-phase system? I

Re: [PATCH for 2.5] preemptible kernel

On Tue, 20 Mar 2001, Nigel Gamble wrote: > On Tue, 20 Mar 2001, Rusty Russell wrote: > > Thoughts? > > Perhaps synchronize_kernel() could take the run_queue lock, mark all the > tasks on it and count them. Any task marked when it calls schedule() > voluntarily (but not if it is preempted) is unm

Re: [PATCH for 2.5] preemptible kernel

On Wed, Mar 28, 2001 at 12:51:02PM -0800, george anzinger wrote: > Dipankar Sarma wrote: > > > > Also, a task could be preempted and then rescheduled on the same cpu > > making > > the depth counter 0 (right ?), but it could still be holding references > > to data > > structures to be updated usi

Re: [PATCH for 2.5] preemptible kernel

Dipankar Sarma wrote: > > Nigel Gamble wrote: > > > > On Wed, 21 Mar 2001, Keith Owens wrote: > > > I misread the code, but the idea is still correct. Add a preemption > > > depth counter to each cpu, when you schedule and the depth is zero then > > > you know that the cpu is no longer holding a

Re: [PATCH for 2.5] preemptible kernel

Hi George, george anzinger wrote: > > Exactly so. The method does not depend on the sum of preemption being > zip, but on each potential reader (writers take locks) passing thru a > "sync point". Your notion of waiting for each task to arrive > "naturally" at schedule() would work. It is, in

Re: [PATCH for 2.5] preemptible kernel

Nigel Gamble wrote: > > On Wed, 21 Mar 2001, Keith Owens wrote: > > I misread the code, but the idea is still correct. Add a preemption > > depth counter to each cpu, when you schedule and the depth is zero then > > you know that the cpu is no longer holding any references to quiesced > > struct

Re: [PATCH for 2.5] preemptible kernel

On Thu, 22 Mar 2001, Rusty Russell wrote: > Nigel's "traverse the run queue and mark the preempted" solution is > actually pretty nice, and cheap. Since the runqueue lock is grabbed, > it doesn't require icky atomic ops, either. You'd have to mark both the preempted tasks, and the tasks currentl

Re: [PATCH for 2.5] preemptible kernel

In message <[EMAIL PROTECTED]> you write: > > Keith Owens writes: > > Or have I missed something? > > Nope, it is a fundamental problem with such kernel pre-emption > schemes. As a result, it would also break our big-reader locks > (see include/linux/brlock.h). Good point: holding a brlock ha

Re: [PATCH for 2.5] preemptible kernel

In message <[EMAIL PROTECTED]> you write: > Nigel Gamble wrote: > > > > On Wed, 21 Mar 2001, Keith Owens wrote: > > > I misread the code, but the idea is still correct. Add a preemption > > > depth counter to each cpu, when you schedule and the depth is zero then > > > you know that the cpu is n

Re: [PATCH for 2.5] preemptible kernel

On Wed, 21 Mar 2001, Andrew Morton wrote: > It's a problem for uniprocessors as well. > > Example: > > #define current_cpu_data boot_cpu_data > #define pgd_quicklist (current_cpu_data.pgd_quick) > > extern __inline__ void free_pgd_fast(pgd_t *pgd) > { > *(unsigned long *)pgd = (unsigned

Re: [PATCH for 2.5] preemptible kernel

On Wed, 21 Mar 2001, David S. Miller wrote: > Basically, anything which uses smp_processor_id() would need to > be holding some lock so as to not get pre-empted. Not necessarily. Another solution for the smp_processor_id() case is to ensure that the task can only be scheduled on the current CPU

Re: [PATCH for 2.5] preemptible kernel

On Wed, Mar 21, 2001 at 08:19:54PM +1100, Keith Owens wrote: > Ouch. What about all the per cpu structures in the kernel, how do you > handle them if a preempted task can be rescheduled on another cpu? > > int count[NR_CPUS], *p; > p = count+smp_processor_id(); /* start on cpu 0, &count[0] */

Re: [PATCH for 2.5] preemptible kernel

george anzinger writes: > By the by, if a preemption lock is all that is needed the patch defines > it and it is rather fast (an inc going in and a dec & test comming > out). A lot faster than a spin lock with its "LOCK" access. A preempt > lock does not need to be "LOCK"ed because the only

Re: [PATCH for 2.5] preemptible kernel

"David S. Miller" wrote: > > Keith Owens writes: > > Or have I missed something? > > Nope, it is a fundamental problem with such kernel pre-emption > schemes. As a result, it would also break our big-reader locks > (see include/linux/brlock.h). > > Basically, anything which uses smp_processor

Re: [PATCH for 2.5] preemptible kernel

Keith Owens writes: > Or have I missed something? Nope, it is a fundamental problem with such kernel pre-emption schemes. As a result, it would also break our big-reader locks (see include/linux/brlock.h). Basically, anything which uses smp_processor_id() would need to be holding some lock so

Re: [PATCH for 2.5] preemptible kernel

Nigel Gamble wrote: > A task that has been preempted is on the run queue and can be > rescheduled on a different CPU, so I can't see how a per-CPU counter > would work. It seems to me that you would need a per run queue > counter, like the example I gave in a previous posting. Ouch. What about

Re: [PATCH for 2.5] preemptible kernel

On Wed, 21 Mar 2001 00:04:56 -0800, george anzinger <[EMAIL PROTECTED]> wrote: >Exactly so. The method does not depend on the sum of preemption being >zip, but on each potential reader (writers take locks) passing thru a >"sync point". Your notion of waiting for each task to arrive >"naturally"

Re: [PATCH for 2.5] preemptible kernel

Nigel Gamble wrote: > > On Wed, 21 Mar 2001, Keith Owens wrote: > > I misread the code, but the idea is still correct. Add a preemption > > depth counter to each cpu, when you schedule and the depth is zero then > > you know that the cpu is no longer holding any references to quiesced > > struct

Re: [PATCH for 2.5] preemptible kernel

On Wed, 21 Mar 2001, Keith Owens wrote: > I misread the code, but the idea is still correct. Add a preemption > depth counter to each cpu, when you schedule and the depth is zero then > you know that the cpu is no longer holding any references to quiesced > structures. A task that has been preem

Re: [PATCH for 2.5] preemptible kernel

On Tue, 20 Mar 2001 16:48:01 -0800 (PST), Nigel Gamble <[EMAIL PROTECTED]> wrote: >On Tue, 20 Mar 2001, Keith Owens wrote: >> The preemption patch only allows preemption from interrupt and only for >> a single level of preemption. That coexists quite happily with >> synchronize_kernel() which ru

Re: [PATCH for 2.5] preemptible kernel

On Tue, 20 Mar 2001, Keith Owens wrote: > The preemption patch only allows preemption from interrupt and only for > a single level of preemption. That coexists quite happily with > synchronize_kernel() which runs in user context. Just count user > context schedules (preempt_count == 0), not pree

Re: [PATCH for 2.5] preemptible kernel

On Tue, 20 Mar 2001, Rusty Russell wrote: > I can see three problems with this approach, only one of which > is serious. > > The first is code which is already SMP unsafe is now a problem for > everyone, not just the 0.1% of SMP machines. I consider this a good > thing for 2.5 though. So

Re: [PATCH for 2.5] preemptible kernel

Nigel Gamble wrote: > > On Tue, 20 Mar 2001, Roger Larsson wrote: > > One little readability thing I found. > > The prev->state TASK_ value is mostly used as a plain value > > but the new TASK_PREEMPTED is or:ed together with whatever was there. > > Later when we switch to check the state it is c

Re: [PATCH for 2.5] preemptible kernel

On Tue, 20 Mar 2001, Roger Larsson wrote: > One little readability thing I found. > The prev->state TASK_ value is mostly used as a plain value > but the new TASK_PREEMPTED is or:ed together with whatever was there. > Later when we switch to check the state it is checked against TASK_PREEMPTED > o

Re: [PATCH for 2.5] preemptible kernel

Hi, One little readability thing I found. The prev->state TASK_ value is mostly used as a plain value but the new TASK_PREEMPTED is or:ed together with whatever was there. Later when we switch to check the state it is checked against TASK_PREEMPTED only. Since TASK_RUNNING is 0 it works OK but...

Re: [PATCH for 2.5] preemptible kernel

On Tue, 20 Mar 2001 19:43:50 +1100, Rusty Russell <[EMAIL PROTECTED]> wrote: >The third is that preemtivity conflicts with the naive >quiescent-period approach proposed for module unloading in 2.5, and >useful for several other things (eg. hotplugging CPUs). This method >relies on knowing that w

Re: [PATCH for 2.5] preemptible kernel

In message <[EMAIL PROTECTED]> you write: > Kernel preemption is not allowed while spinlocks are held, which means > that this patch alone cannot guarantee low preemption latencies. But > as long held locks (in particular the BKL) are replaced by finer-grained > locks, this patch will enable lowe

Re: [PATCH for 2.5] preemptible kernel

Hi Pavel, Thanks for you comments. On Sat, 17 Mar 2001, Pavel Machek wrote: > > diff -Nur 2.4.2/arch/i386/kernel/traps.c linux/arch/i386/kernel/traps.c > > --- 2.4.2/arch/i386/kernel/traps.c Wed Mar 14 12:16:46 2001 > > +++ linux/arch/i386/kernel/traps.c Wed Mar 14 12:22:45 2001 > > @@ -973,7

Re: [PATCH for 2.5] preemptible kernel

Hi! > Here is the latest preemptible kernel patch. It's much cleaner and > smaller than previous versions, so I've appended it to this mail. This > patch is against 2.4.2, although it's not intended for 2.4. I'd like > comments from anyone interested in a low-latency Linux kernel solution > fo

[PATCH for 2.5] preemptible kernel

Here is the latest preemptible kernel patch. It's much cleaner and smaller than previous versions, so I've appended it to this mail. This patch is against 2.4.2, although it's not intended for 2.4. I'd like comments from anyone interested in a low-latency Linux kernel solution for the 2.5 devel