[patch] scalable timers implementation, 2.4.16, 2.5.0

[patch] scalable timers implementation, 2.4.16, 2.5.0

[Ingo Molnar]

the 'ultra scalable timers' patch, against 2.4.16 or 2.5.0 is available
at:

  http://redhat.com/~mingo/scalable-timers-patches/smptimers-2.4.16-A0

these are the goals of the patch:

the current 2.4 timer implementation uses a global spinlock for
synchronizing access to the global timer lists. This causes excessive
cacheline ping-pongs and visible performance degradation under very high
TCP networking load (and other, timer-intensive operations).

The new implementation introduces per-CPU timer lists and per-CPU
spinlocks that protect them. All timer operations, add_timer(),
del_timer() and mod_timer() are still O(1) and cause no cacheline
contention at all (because all data structures are separated). All
existing semantics of Linux timers are preserved, so the patch is
'transparent' to all other subsystems.

(The patch does not attempt to change the timer interface in any way -
that might be done via different patches. These timers are compatible with
TIMER_BH & cli() methods of synchronization as well.)

	Ingo

Re: [patch] scalable timers implementation, 2.4.16, 2.5.0

[Rusty Russell]

On Tue, 27 Nov 2001 15:57:03 +0100 (CET)
Ingo Molnar <mingo@elte.hu> wrote:

> 
> the 'ultra scalable timers' patch, against 2.4.16 or 2.5.0 is available
> at:
> 
>   http://redhat.com/~mingo/scalable-timers-patches/smptimers-2.4.16-A0

Hi Ingo,

	Hmm... there are some ugly hoops there to make sure that they don't
conflict with bottom halves or cli().  I assume you want to take that out:
what will break if that happens, and do we need a disable_timers() interface
to move code over?

Cheers,
Rusty.
PS.  Also would be nice to #define del_timer del_timer_sync, and have a
     del_timer_async for those (very few) cases who really want this.
--
  Anyone who quotes me is an idiot -- Rusty Russell.

Re: [patch] scalable timers implementation, 2.4.16, 2.5.0

[Andrew Morton]

Rusty Russell wrote:
> 
> PS.  Also would be nice to #define del_timer del_timer_sync, and have a
>      del_timer_async for those (very few) cases who really want this.

That could cause very subtle deadlocks.   I'd prefer to do:

#define del_timer_async	del_timer

and to then put out the word that del_timer is a deprecated
interface and code should use either del_timer_sync or
del_timer_async.

That way, we can grep through the tree and see which code
has not yet been reviewed/fixed.

-

Re: [patch] scalable timers implementation, 2.4.16, 2.5.0

[Rusty Russell]

In message <3C0E9BFD.BC189E17@zip.com.au> you write:
> Rusty Russell wrote:
> > 
> > PS.  Also would be nice to #define del_timer del_timer_sync, and have a
> >      del_timer_async for those (very few) cases who really want this.
> 
> That could cause very subtle deadlocks.   I'd prefer to do:
> 
> #define del_timer_async	del_timer

I'd prefer to audit them all, create a patch, and remove del_timer.
Doing it slowly usually means things just get forgotten, then hacked
around when it finally gets ripped out.

The deadlock you're referring to is, I assume, del_timer_sync() called
inside the timer itself?  Can you think of any other dangerous cases?

Rusty.
--
  Anyone who quotes me is an idiot. -- Rusty Russell.

Re: [patch] scalable timers implementation, 2.4.16, 2.5.0

[Andi Kleen]

Rusty Russell <rusty@rustcorp.com.au> writes:

> The deadlock you're referring to is, I assume, del_timer_sync() called
> inside the timer itself?  Can you think of any other dangerous cases?

Common seems to be: 


	CPU#0                CPU#1

                             timer fires
spinlock()                 
                             spinlock() - spinning
del_timer_sync() 


-> deadlock. 

-Andi

Re: [patch] scalable timers implementation, 2.4.16, 2.5.0

[Andrew Morton]

Rusty Russell wrote:
> 
> In message <3C0E9BFD.BC189E17@zip.com.au> you write:
> > Rusty Russell wrote:
> > >
> > > PS.  Also would be nice to #define del_timer del_timer_sync, and have a
> > >      del_timer_async for those (very few) cases who really want this.
> >
> > That could cause very subtle deadlocks.   I'd prefer to do:
> >
> > #define del_timer_async       del_timer
> 
> I'd prefer to audit them all, create a patch, and remove del_timer.
> Doing it slowly usually means things just get forgotten, then hacked
> around when it finally gets ripped out.

um.  Auditing them all is a big task:

akpm-1:/usr/src/linux-2.4.17-pre4> grep -r del_timer . | wc
    800    2064   48299
akpm-1:/usr/src/linux-2.4.17-pre4> grep -r del_timer_sync . | wc 
     85     245    5384

I tried it, when I was a young man.

One mindset would be to just replace all the del_timer calls
with del_timer_sync by default, and to then look for the below
deadlock pattern.   But if you do this, Alexey shouts at you,
because his code actually gets del_timer right, by looking at
its return value.

I'd urge you to reconsider.  We have a *lot* of timer deletion
races in Linux, and squashing them all in one patch just isn't
feasible.

> The deadlock you're referring to is, I assume, del_timer_sync() called
> inside the timer itself?  Can you think of any other dangerous cases?

Nope.  The deadlock is where the caller of del_timer_sync holds
some lock which would prevent the completion of the timer handler.
It happens, and is sometimes subtle.

drivers/video/txfxfb.c is an unsubtle example.

-

Re: [patch] scalable timers implementation, 2.4.16, 2.5.0

[Alan Cox]

> The deadlock you're referring to is, I assume, del_timer_sync() called
> inside the timer itself?  Can you think of any other dangerous cases?

Any case where the timer handler and the calling code both want the same
lock. So for example timer based I/O completion polling will deadlock
against request code doing a del_timer_sync

Re: [patch] scalable timers implementation, 2.4.16, 2.5.0

[Ingo Molnar]

On Thu, 6 Dec 2001, Rusty Russell wrote:

> 	Hmm... there are some ugly hoops there to make sure that they
> don't conflict with bottom halves or cli().  I assume you want to take
> that out: what will break if that happens, and do we need a
> disable_timers() interface to move code over?

hm, those ugly hoops are really limited in scope - they cause no
scalability or other visible performance impact. So i thought we do the
threading first (and *just* the threading), then we might change the timer
interface. But that is a *huge* task.

	Ingo